Page MenuHomePhabricator

[SimplifyLibCalls] Mark known arguments with nonnull
ClosedPublic

Authored by xbolva00 on Oct 16 2018, 2:39 PM.

Diff Detail

Repository
rL LLVM

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes

annotate snprintf if N is C > 0.

xbolva00 updated this revision to Diff 215916.Aug 19 2019, 8:48 AM

I added initial comments, will have to go through again though.

lib/Transforms/Utils/SimplifyLibCalls.cpp
518 ↗(On Diff #171003)

I'm confused, here and before, you annotate and later, under some condition, remove the annotation again. This seems risky.

Here for example, Len = 0 will not remove the attribute but an unknown Len will. I doubt that is intentional.

214 ↗(On Diff #215916)

Maybe make it clear that this annotates nonnull only if it is not a valid pointer, e.g., name this annotateNonNullBasedOnAccess or sth.

217 ↗(On Diff #215916)

Please do not use this method, it is super confusing. I'd argue you should use the getCallee anyway but if you think the surrounding function is the one you need, I'd prefer getCaller.

225 ↗(On Diff #215916)

If you do not keep track (=statistics), there is probably no need to check first, as below, I think.

232 ↗(On Diff #215916)

I don't think you need to check first.

518 ↗(On Diff #215916)

What about this one?

678 ↗(On Diff #215916)

I would argue we actually want to annotate deref all the time but do also do nonnull while we are at it. (The Attributor derives nonnull from deref if appropriate.) Long story short, why do we derive nonnull but not deref(1) here and in other places where we expect a \0 char?

(We could also add deref(N) if we already computed the static string size.)

2381 ↗(On Diff #215916)

We could even use "isKnownNonZero" or other helper functions here.

xbolva00 marked 2 inline comments as done.Aug 19 2019, 10:20 AM
xbolva00 added inline comments.
lib/Transforms/Utils/SimplifyLibCalls.cpp
518 ↗(On Diff #171003)

Len = 0 means we return Dst;

I need to reorder the code here a bit..

678 ↗(On Diff #215916)

deref(N) for string constants?

  • useless, no?

And, isn't it a attributor's work? get GEP with bound N and infer deref(N)


I agree with deref(1).

xbolva00 marked an inline comment as done.Aug 19 2019, 10:33 AM
xbolva00 added inline comments.
lib/Transforms/Utils/SimplifyLibCalls.cpp
217 ↗(On Diff #215916)

Ok, getCaller.

CallInst has no getCallee.

jdoerfert added inline comments.Aug 19 2019, 11:16 AM
lib/Transforms/Utils/SimplifyLibCalls.cpp
518 ↗(On Diff #171003)

Oh, this is all confusing (as I said).

217 ↗(On Diff #215916)

getCallee -> getCalledFunction

I still think the callee is what is important here (conceptually), though I doubt it makes a difference in practice.

678 ↗(On Diff #215916)

deref(N) for string constants?

Yes, or more general, for everything we know a minimal "length".

Useless?

I don't think so, but see below.

Strictly needed?

No. Though, we do already call GetStringLength all the time here, why not manifest the information?

And, isn't it a attributor's work? get GEP with bound N and infer deref(N)

It does, yes.

nonnull -> deref(1)

That doesn't happen in the Attributor right now but it should because deref(1) can be combined (e.g., in a phi) with null to deref_or_null(1) while nonnull cannot be combined with null to anything.

xbolva00 marked an inline comment as done.Aug 19 2019, 3:20 PM
xbolva00 added inline comments.
lib/Transforms/Utils/SimplifyLibCalls.cpp
2381 ↗(On Diff #215916)

This is true but since we we need to compute “N” anyway, I think isKnownNonZero is a overkill a bit, since it computes what we already have - “N”. - should I use it even here?

But I could use it in some places, yes, (memcpy/memmove/memset)..

jdoerfert added inline comments.Aug 19 2019, 10:09 PM
lib/Transforms/Utils/SimplifyLibCalls.cpp
2381 ↗(On Diff #215916)

For a lot of calls a nonnull size implies other stuff, especially, noalias, deref_or_null.
I think this is worth a separate patch but doing better nonnull checks makes sense because any value (not necessarily a constant) that is not zero will allow us to infer (1) nonnull, (2) noalias, (3) deref_or_null. If we want the constant size for some other transformations we should first look for a constant and only as a fallback call isknownnonzero.

xbolva00 marked an inline comment as done.EditedAug 20 2019, 4:52 AM

Found a bug in LLVM.

We do not copy attributes, it seems.

define i8* @memset_size_select4(i1 %b, i8* %ptr) {
; CHECK-LABEL: @memset_size_select4(
; CHECK-NEXT: [[SIZE:%.*]] = select i1 [[B:%.*]], i32 10, i32 50
; CHECK-NEXT: call void @llvm.memset.p0i8.i32(i8* align 1 [[PTR:%.*]], i8 0, i32 [[SIZE]], i1 false)
; CHECK-NEXT: ret i8* [[PTR]]
;

%size = select i1 %b, i32 10, i32 50
%memset = tail call i8* @memset(i8* nonnull dereferenceable_or_null(40) %ptr, i32 0, i32 %size)
ret i8* %memset

}

Fixed with

CallInst *NewCI = B.CreateMemSet(CI->getArgOperand(0), Val, Size, 1);
NewCI->setAttributes(CI->getAttributes());

I will update this patch soon.

lib/Transforms/Utils/SimplifyLibCalls.cpp
2381 ↗(On Diff #215916)

Until I start heavy mechanical work here I would like to know if this approch is acceptable.

Value *LibCallSimplifier::optimizeMemSet(CallInst *CI, IRBuilder<> &B,

                                       bool isIntrinsic) {
Value *Size = CI->getArgOperand(2);
if (ConstantInt *LenC = dyn_cast<ConstantInt>(Size)) {
  annotateDereferenceableBytes(CI, {0}, LenC->getZExtValue());
  annotateNonNull(CI, {0});
} else if (isKnownNonZero(Size, DL)) {
  annotateDereferenceableBytes(CI, {0}, 1);
  annotateNonNull(CI, {0});
} else if (!isIntrinsic) {
  removeNonNull(CI, {0});
}

Now we catch even this case :)
define i8* @memset_size_select(i1 %b, i8* %ptr) {
; CHECK-LABEL: @memset_size_select(
; CHECK-NEXT: [[SIZE:%.*]] = select i1 [[B:%.*]], i32 10, i32 50
; CHECK-NEXT: call void @llvm.memset.p0i8.i32(i8* nonnull align 1 dereferenceable(1) [[PTR:%.*]], i8 0, i32 [[SIZE]], i1 false)
; CHECK-NEXT: ret i8* [[PTR]]
;

%size = select i1 %b, i32 10, i32 50
%memset = tail call i8* @memset(i8* nonnull %ptr, i32 0, i32 %size) #1
ret i8* %memset

}

define i8* @memset_size_select_or(i1 %b, i8* %ptr, i32 %v) {
; CHECK-LABEL: @memset_size_select_or(
; CHECK-NEXT: [[SIZE:%.*]] = ashr i32 -2, [[V:%.*]]
; CHECK-NEXT: call void @llvm.memset.p0i8.i32(i8* nonnull align 1 dereferenceable(1) [[PTR:%.*]], i8 0, i32 [[SIZE]], i1 false)
; CHECK-NEXT: ret i8* [[PTR]]
;

%size = ashr i32 -2, %v
%memset = tail call i8* @memset(i8* nonnull %ptr, i32 0, i32 %size) #1
ret i8* %memset

}

for select of constants we can do better job than deref(1)

if (ConstantInt *LenC = dyn_cast<ConstantInt>(Size)) {

  annotateDereferenceableBytes(CI, {0}, LenC->getZExtValue());
  annotateNonNull(CI, {0});
} else if (isKnownNonZero(Size, DL)) {
  const  APInt *X, *Y;
  uint64_t DerefMin = 1;
  if (match(Size, m_Select(m_Value(), m_APInt(X), m_APInt(Y)))) {
    Min = std::min(X->getZExtValue(), Y->getZExtValue());
        annotateDereferenceableBytes(CI, {0}, DerefMin);

}

  annotateNonNull(CI, {0});
} else if (!isIntrinsic) {
  removeNonNull(CI, {0});
}

Ok?

Can you use ` (three backticks) to enclose the code regions for better formatting?

xbolva00 updated this revision to Diff 216194.Aug 20 2019, 10:49 AM

New implementation.

xbolva00 updated this revision to Diff 216195.Tue, Aug 20, 11:15 AM
xbolva00 marked an inline comment as done.
xbolva00 updated this revision to Diff 216197.Tue, Aug 20, 11:19 AM
xbolva00 added a comment.EditedTue, Aug 20, 11:31 AM

For some cases I would like to copy just attributes for argno 0 - but I dont know to do it :(

I mean something like this:
NewCI->setAttrubutes(0, CI->getAttributes(0))

Maybe you can help me?

test/Transforms/InstCombine/mem-deref-bytes.ll
76 ↗(On Diff #216194)

@jdoerfert please check this "side-effect" improvement while working on nonnull annotation..

if "null-pointer-is-valid"="true" and "nonnull dereferenceable_or_null(40)" -> nonnull dereferenceable(40) is ok?

if nonnull is missing, see memcmp_const_size_update_deref6,

See newly added "CI->paramHasAttr(ArgNo, Attribute::NonNull) check" in annotateDereferenceableBytes.

For some cases I would like to copy just attributes for argno 0 - but I dont know to do it :(

I mean something like this:

NewCI->setAttrubutes(0, CI->getAttributes(0))

Maybe you can help me?

Take the attribute list (getAttributes()) then getParamAttributes(ArgNo), then probably foreach addParamAttr(NewArgNo), and then set the attribute list. Make sure to always check that you update the list properly.

jdoerfert added inline comments.Tue, Aug 20, 11:53 AM
test/Transforms/InstCombine/mem-deref-bytes.ll
76 ↗(On Diff #216194)

This looks fine to me, also test6. nonnull + dereferenceable_or_null(X) is always dereferenceable(X) regardless of the validity of null.

xbolva00 updated this revision to Diff 216212.Tue, Aug 20, 12:20 PM

Copy arg attributes.

Ok, thanks.

In terms of scope of annotations, I think it is good enough.

Now we have to check if all test changes are OK.

xbolva00 marked an inline comment as done.Tue, Aug 20, 12:24 PM
xbolva00 added inline comments.
test/Transforms/InstCombine/mem-deref-bytes.ll
76 ↗(On Diff #216194)

Thanks!

xbolva00 updated this revision to Diff 216214.Tue, Aug 20, 12:31 PM

Fixed off by one bug.

xbolva00 updated this revision to Diff 216217.Tue, Aug 20, 12:38 PM

Passes test suite.

xbolva00 updated this revision to Diff 216222.Tue, Aug 20, 1:03 PM

I think I can tag many libc functions without size argument with nonnull args directly in “BuildLibCalls” - better approach.

New patch soon.

I think I can tag many libc functions without size argument with nonnull args directly in “BuildLibCalls” - better approach.

New patch soon.

Or should we assume if NullPointerIsDefined = true that strlen could work with null pointer?

Anway if libc tags with nonnull, like int memcmp(void * nonnull dst, void * nonnull src, size_t n) this applies to function signature, not to specific callsites so this fix will not work, indeed. We need drop nonnull from signatures in BuildLibCalls.

I think we just doing shitty workarounds and gcc 4.9 optimizes it fully since ptr cannot be null even if size is 0.
And we have sanitizer check to do that:
https://reviews.llvm.org/D9673?id=25492

Jakub Jelinek at GCC Bugzilla:

C says e.g. for memchr:
"The memchr function locates the first occurrence of c (converted to an unsigned
char) in the initial n characters (each interpreted as unsigned char) of the object pointed to by s."
and elsewhere:
"If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function."
As memchr first argument must point to an object and NULL does not point to any object, NULL is not a valid value. It is similar to memcpy (NULL, NULL, 0) or memset (NULL, 0, 0) etc. being invalid.”

Sanitizer warns so I dont know why se should permit UB.

xbolva00 added a subscriber: aaron.ballman.EditedWed, Aug 21, 12:38 AM

Maybe @aaron.ballman could help us

  • whether Jakub Jelinek is right
  • whether memcpy/memmove/memset with NULL dst/src pointers is UB (even for size = 0)
xbolva00 added a comment.EditedWed, Aug 21, 3:37 AM

memcpy(0,0,0) is UB after all

https://stackoverflow.com/questions/5243012/is-it-guaranteed-to-be-safe-to-perform-memcpy0-0-0

So we can move nonnull annotation to BuildLibCalls.

joerg added a subscriber: joerg.Wed, Aug 21, 4:30 AM

Take a look at the list archives for the discussion about attribute nonnull and nullable a while ago. The short version is that the library interface specification might have a wildcard clause that NULL pointers are invalid unless explicitly allowed, but it works perfectly fine on any sensible implementation except the ds9k. When the combination of glibc annotations and aggressive gcc optimizations started, it pointlessly broke a lot of code for no good reason.

xbolva00 added a comment.EditedWed, Aug 21, 4:56 AM

It is still a UB and UBSanitizer warns. If somebody uses (typical combo) clang and gcc, one may be very surprised why debug/dev (with clang) builds work and release (with gcc) builds not.

While in 2014 or so there was no way to find this UB in codebases, we have now UB Sanitizer. In 2019 there is no excuse "it is a UB but it still kinda work (except gcc, ds9k, ..)". Add simple "if" - problem solved. For general case, anybody can send a paper to specify this behaviour to C committee.

Now, because of "memcpy(NULL, NULL, 0) fans" we cannot optimize null checks (imagine you have safe wrapper (which always check if nonnull ptrs) above standard string functions..) - "no good reason". ?
I see a lot of opportunity from nonnull/dereferenceable annotation so I dont see why we should not to do it (ok, few codes may break - any sane codebase is checked by sanitizers anyway).

joerg added a comment.Wed, Aug 21, 5:59 AM

Please read the discussion. The general consensus was and likely is that this is at least somewhat bogus in the standard at best and the cost of not artificially breaking code is much higher than the benefit. Yes, GCC made different choices, but that's no excuse.

xbolva00 added a comment.EditedWed, Aug 21, 6:16 AM

And nobody wrote a paper to fix “the bogus”.

@jdoerfert what do you think?

As I see, annotating callsites is atm pointless since FunctionAttrs/Attributor cannot propagate it - they do only if “function signature (decl)” contains nonnull. I would continue to work on this current “safe” approach if there is a small promise that Attributor will handle this kind of propagation too :)

I would like to hear @hfinkel’s opinion too :)

And nobody wrote a paper to fix “the bogus”.

@jdoerfert what do you think?

As I see, annotating callsites is atm pointless since FunctionAttrs/Attributor cannot propagate it - they do only if “function signature (decl)” contains nonnull. I would continue to work on this current “safe” approach if there is a small promise that Attributor will handle this kind of propagation too :)

@uenoku informed me that Attributor will handle it with a WIP patch which is not yet commited. Good.

So this patch has a sense in terms of global scope. PTAL as I finished here all annotation work.

I would like to hear @hfinkel’s opinion too :)

As I recall, there are two issues. One is: do we add the attributes based on the function names. The second is: What to do with the attributes that already exist in, e.g., some glibc header files.

My opinion is that:

  1. We should definitely have this optimization capability
  2. But we should have this after we filter out the annotations from memcpy/memset (etc.) in Clang (when the size is dynamic or zero). There should be a flag to turn off the filtering, but at least for now, it should be on by default.
  3. We should have a function attribute reflecting the same filtering setting to appropriately control adding the attributes in the optimizer.

Yes, NULL pointers with memcpy/memset are UB from the standards perspective, but it's unclear to me that the value in exploiting this UB outweighs the potential problems introduced. While I generally agree with the viewpoint that says that people should use sanitizers, etc., and believe that they should in this case as well, because memcpy/memset are *so* common, because there's a wide-spread and reasonable disagreement as to whether this behavior should be undefined at all, and because there's no strong and broad case for performance improvements (unlike, for example, exploiting the lack of signed-integer overflow), I think that we should filter.

do we add the attributes based on the function names.

I dont see this as a problem - reserved names.

What to do with the attributes that already exist in, e.g., some glibc header files.

Can you point me on real example/OS/glibc version where this actually happens?

I have Ubuntu 18 LTS and glibc and I see no such attributes in IR.

But we should have this after we filter out the annotations from memcpy/memset (etc.) in Clang (when the size is dynamic or zero)

I dont think we want add/remove attributes in Clang based on size argument. It seems just bad to look at function names in Clang and go thru Clang AST to inspect size argument.

Either drop all and possibly add it back here in instcombine or leave it and drop it in eg. BuildLibCalls?

  • these are libc functions and almost all C code is compiled by gcc, I think if the code triggered UB, gcc 4.9 and newer already exploited this UB -> UB releaved by “miscompile” or GCC UB sanitizer
  • small percentange of C code which is compiled only by clang is hopefully tested with sanitizer -> UB revealed

On the other side the cost of patching Clang and llvm (+ maintenance) to keep this UB working in the user code (I would be very interested to see how many % of all code it could broken in 2019 - I believe very very small percentange) seems quite high.

do we add the attributes based on the function names.

I dont see this as a problem - reserved names.

What to do with the attributes that already exist in, e.g., some glibc header files.

Can you point me on real example/OS/glibc version where this actually happens?

I have Ubuntu 18 LTS and glibc and I see no such attributes in IR.

The glibc header files have the attributes, AFAIKT: https://github.com/bminor/glibc/blob/master/string/string.h - and this looks like the header on the Fedora 27 system that I just checked.

/* Copy N bytes of SRC to DEST.  */
extern void *memcpy (void *__restrict __dest, const void *__restrict __src,
                     size_t __n) __THROW __nonnull ((1, 2));

If you're not seeing the attributes in the IR, and I'm not seeing them either, we might just not be adding them to avoid this issue. I do see them in Clang's AST:

|-FunctionDecl x </usr/include/string.h:42:1, /usr/include/sys/cdefs.h:289:63> /usr/include/string.h:42:14 used memcpy 'void *(void *restrict, const void *restrict, size_t)' extern
| |-ParmVarDecl x <col:22, col:39> col:39 __dest 'void *restrict'
| |-ParmVarDecl x <col:47, col:70> col:70 __src 'const void *restrict'
| |-ParmVarDecl x <line:43:8, col:15> col:15 __n 'size_t':'unsigned long'
| |-NoThrowAttr x </usr/include/sys/cdefs.h:55:35>
| `-NonNullAttr x <line:289:44, /usr/include/string.h:43:44> 1 2
  • these are libc functions and almost all C code is compiled by gcc, I think if the code triggered UB, gcc 4.9 and newer already exploited this UB -> UB releaved by “miscompile” or GCC UB sanitizer
  • small percentange of C code which is compiled only by clang is hopefully tested with sanitizer -> UB revealed

    On the other side the cost of patching Clang and llvm (+ maintenance) to keep this UB working in the user code (I would be very interested to see how many % of all code it could broken in 2019 - I believe very very small percentange) seems quite high.

You seem to be assuming that it would be obvious that a given program would be negatively affected by this, and I don't think this would be obvious at all. Sanitizers are great tools for debugging problems, but they're dynamic tools, so they only test the code paths and the parts of the configuration space that the instrumented program actually executes. Best practice may be to fuzz test all code with sanitizers, which can provide more confidence in finding problems like this, but only a very small percentage of the code that exists has been tested in this way (or has been subjected to any suitable, effective static analysis).

I look at this as something about which reasonable people can disagree. No one really has data on this, AFAIK, and so I just have my judgement. I suspect that the percentage of affected programs here is small, but not tiny. memcpy is a very-commonly-used function, and so I suspect we're in a situation where a small (but not tiny) percentage of a very large amount of code yields a large number of affected programs.

If Clang already drops it [0], that is good, then this patch is totally fine.

[0] @aaron.ballman, @rsmith, @rjmcall - can you tell us more what Clang actually does here?

If Clang already drops it [0], that is good, then this patch is totally fine.

But this patch would add the nonnull attributes back, no? I'm not sure that's fine.

xbolva00 added a comment.EditedFri, Aug 23, 5:50 AM

Yes, but only when size is constant non zero (isKnownNonZero)

Yes, but only when size is constant non zero (isKnownNonZero)

Ah. Indeed. I missed that part of the logic rearrangement. I agree, that's fine.

BlackAngel35 rescinded a token.
BlackAngel35 awarded a token.

Rebased, @jdoerfert please take a look :)

We should ditch “removeNonNull” handling since Clang never annotates callsites (Clang only annotates function signatures - currently nonnull is dropped, great!)

We should ditch “removeNonNull” handling since Clang never annotates callsites (Clang only annotates function signatures - currently nonnull is dropped, great!)

What do you think, @jdoerfert ? removeNonNull sometimes caused instcombine’s infinite loop + i think we dont need removeNonNull at all.

I would like to move forward here..

Sorry for the delay but it will take me a while to look through all the changes and make sure we did not overlook sth.

jdoerfert accepted this revision.Fri, Sep 13, 9:34 PM

Some minor nits, two questions that you could clarify or resolve, other than that I think this is fine.

lib/Transforms/Utils/SimplifyLibCalls.cpp
638 ↗(On Diff #218260)

Somewhere above and somewhere below you copy all attributes, here only the param 0 attributes, is there a reason why?

1084 ↗(On Diff #218260)

Leftover call.

2693 ↗(On Diff #218260)

Move to the beginning of the function, puts has often no users (IMHO).

3111 ↗(On Diff #218260)

Is there a reason this is not happening for the two functions below?

test/Transforms/InstCombine/strstr-1.ll
91 ↗(On Diff #218260)

Add a newline at the end.

This revision is now accepted and ready to land.Fri, Sep 13, 9:34 PM
xbolva00 marked 2 inline comments as done.Sat, Sep 14, 11:26 AM
xbolva00 added inline comments.
lib/Transforms/Utils/SimplifyLibCalls.cpp
638 ↗(On Diff #218260)

I think it crashed for me. I will check it again.

3111 ↗(On Diff #218260)

Oops, thanks! I will adjust those places too.

Btw

We should ditch “removeNonNull” handling since Clang never annotates callsites (Clang only annotates function signatures - currently nonnull is dropped, great!)

I will go this way and remove it. removeNonNull may pessimize things / create compiler infinite loops. Some other may infer that pointer X is nonnull and then InstCombine would remove it in strncpy(D, X, N); // non const N

Imagine
%add.ptr = getelementptr inbounds i8, i8* %string_literal, i64 1

%call2 = call i64 @strlen(i8* nonnull dereferenceable(1) %string_literal) #7
%sub3 = add i64 %call2, -2
%call4 = call i8* @strncpy(i8* nonnull %call1, i8* nonnull %add.ptr, i64 %sub3) #8

This is IR which cause instcombine infinite loop. InstCombine sees that sub3 is not "known zero" and will remove nonnull from add.ptr. As I noted, I am not worried if we remove "removeNonNull", since Clang does not annotate call sites, Clang just emit function signatures (and these do not contain "nonnulls").

xbolva00 updated this revision to Diff 220229.Sat, Sep 14, 12:13 PM

Addressed review comments.

xbolva00 updated this revision to Diff 220230.Sat, Sep 14, 12:16 PM

Removed left over call.

This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptTue, Sep 17, 2:33 AM