try to extend nonnull-ness of arguments from a callsite back to its parent function

[spatel]

Summary

As discussed here:
http://lists.llvm.org/pipermail/llvm-dev/2016-December/108182.html
...we should be able to propagate 'nonnull' info from a callsite back to its parent.

The original motivation for this patch is our botched optimization of "dyn_cast" (PR28430), but this won't solve that problem alone.

I think this is the strongest nonnull transform of this type because tagging the argument can enable transforms for all other instructions in the function. Possible follow-ups would handle cases where we can use nonnull to directly eliminate an icmp (InstSimplify+ValueTracking), or add llvm.assume to trigger existing transforms.

[majnemer]

lib/Transforms/InstCombine/InstCombineCalls.cpp

2779–2820 ↗

(On Diff #81766)

Any chance this logic could live in llvm::isKnownNonNullAt

[spatel]

lib/Transforms/InstCombine/InstCombineCalls.cpp

2779–2820 ↗

(On Diff #81766)

Hmm...yes, that would probably be better. Today's comments in the earlier linked llvm-dev thread suggest that this approach (adding attributes that enable existing analysis rather than doing more analysis) is not ideal, so we might want to abandon this entirely for simplify/combines that do the work directly.

[mehdi_amini]

Isn't this something that could be part of the "Deduce function attributes" pass?

[spatel]

In D27855#625386, @mehdi_amini wrote:

Isn't this something that could be part of the "Deduce function attributes" pass?

I actually looked at that first, but this (nonnull) is a parameter attribute rather than a function attribute, so it didn't seem like the right place. If I misunderstood the boundary, please let me know.

[efriedma]

lib/Transforms/InstCombine/InstCombineCalls.cpp

2799 ↗

(On Diff #81766)

I don't think this check is sufficient; consider something like this:

void g(int* NONNULL notnull_ptr);
void f(int *ptr, bool ptr_is_nonnull) {
  if (ptr_is_nonnull) g(ptr);
}

I think your check marks the "ptr" argument to f() as nonnull. This deduction gets propagated out to callers of f(), which then assume the pointer isn't null.

[spatel]

lib/Transforms/InstCombine/InstCombineCalls.cpp

2799 ↗

(On Diff #81766)

Nice catch. Yes, that would be wrong. We can only do this if the callsite is in the entry block?

[mkuper]

lib/Transforms/InstCombine/InstCombineCalls.cpp

2799 ↗

(On Diff #81766)

I'd say "if the callsite post-dominates the entry block", except that LLVM's notion of post-dominance isn't really strong enough to be useful, IIRC.

[efriedma]

lib/Transforms/InstCombine/InstCombineCalls.cpp

2799 ↗

(On Diff #81766)

You need to prove that it would be undefined behavior if the argument were in fact null, i.e. the if the function is called, the callsite will be executed.

You can break it down like this: the callsite needs to dominate every exit from the function, and every instruction which might execute before the callsite in question needs to be isGuaranteedToTransferExecutionToSuccessor() . The first is true for every instruction in the entry block, but the second isn't.

[spatel]

In D27855#625390, @spatel wrote:

In D27855#625386, @mehdi_amini wrote:

Isn't this something that could be part of the "Deduce function attributes" pass?

I actually looked at that first, but this (nonnull) is a parameter attribute rather than a function attribute, so it didn't seem like the right place. If I misunderstood the boundary, please let me know.

This time I looked closer, and sure enough we have FunctionAttrs.cpp::addArgumentAttrs(). So there already exists a place where we could splice this in. However, it still seems mismatched in intent because that function is dealing with interprocedural transforms, while this patch is limited to analysis within a single function. If anyone thinks it's better handled there, I'm not opposed, but I haven't thought of a compelling reason for that yet. It seems logical to me to keep this next to the existing InstCombine nonnull transform since this transform can enable that one.

lib/Transforms/InstCombine/InstCombineCalls.cpp

2779–2820 ↗

(On Diff #81766)

I drafted a patch to split some of the code over to isKnownNonNullAt(), but I don't think it belongs there. In this case, we're not asking if the value is known non-null at some point; we're asking if the value is known non-null throughout because of the context instruction. So it feels like a better fit for the plain isKnownNonNull() except it could be expensive to determine this nonnull-ness from there?

I'll post an updated patch with the changes suggested by @efriedma and @mkuper that hopefully makes it clearer.

[spatel]

Patch updated:

1. Add checks for callsite-in-entry-block + isGuaranteedToTransferExecutionToSuccessor().
2. Add tests for those situations.
3. Add comments to this transform and the existing nonnull transform to provide motivational/philosophical context as noted in the llvm-dev thread.

[sanjoy]

Few random unsolicited comments inline.

lib/Transforms/InstCombine/InstCombineCalls.cpp

2784 ↗

(On Diff #81847)

We pass CallSite by value.

2791 ↗

(On Diff #81847)

When can these be false (i.e. when can we have a call site not in a basic block or inside a function)?

2801 ↗

(On Diff #81847)

Maybe use range for here?

for (Instruction &I : make_range(BB->begin(), CS.getInstruction()->getIterator()))

at which point you can just std::all_of over the above.

2827 ↗

(On Diff #81847)

I don't think this is necessary. You've proved that once you enter the caller, you are going to pass the said argument as a nonnull parameter to CS. This means that the incoming value is nonnull too, irrespective of where all it is used.

That is, instead of NonNullParams.push_back(V), you should be able to do:

if (auto *A = dyn_cast<Argument>(V))
  A->addAttr(NonNull);

[spatel]

In D27855#626049, @sanjoy wrote:

Few random unsolicited comments inline.

Always appreciated!

lib/Transforms/InstCombine/InstCombineCalls.cpp

2791 ↗

(On Diff #81847)

Honestly, I don't know. I saw some other code - that I'm not finding now - that scared me into thinking that it's not safe to assume that an instruction is always tied to a block/function. I can make it an assert if we believe it's safe.

2827 ↗

(On Diff #81847)

We have to prove that the first use of the arg is a nonnull use, and so the 'dominates' check is needed. Let me know if I'm not understanding the suggestion.

The first test case was supposed to demonstrate this, but it doesn't fulfill that intent after the addition of the isGuaranteedToTransferExecutionToSuccessor() check. I can add a test case like below to show this possibility.

declare i8 @use1readonly(i8* %x) readonly ; readonly guarantees that execution continues to successor
declare void @use1nonnull(i8* nonnull %x);

define i8 @parent7(i8* %a) {
  %ret = call i8 @use1readonly(i8* %a) ; %a could be null in here
  call void @use1nonnull(i8* %a) ; guaranteed nonnull use, but can't extend nonnull to parent
  ret i8 %ret
}

[silvas]

This transform seems like it is sensitive to the order in which functions are visited when running function passes, which I think we try to avoid. I.e. if the ordering is right, we can propagate across arbitrarily many transitive calls; but if the ordering is wrong (e.g. we visit callers before callees) then we don't be able to propagate as much.

You may want to check with Chandler about whether it makes sense to do this. Based on my understanding of the rules, this is too strong of a transformation (looks at too large of a scope) to be a function pass (the rules as far as I understand them are essentially "we should be able to conceptually process functions in parallel"; and if the order of visitation matters, then our output will suddenly be sensitive to thread execution order; I don't think we meet this bar today, but I think it is a useful guideline / thing to strive for).

[spatel]

lib/Transforms/InstCombine/InstCombineCalls.cpp

2827 ↗

(On Diff #81847)

On 2nd thought, my reply makes no sense. :)
You're right - we're now guaranteeing that the call with nonnull must execute, so the arg must be nonnull for the parent.
I think we still need the extra test case to show this because the first test's call doesn't guarantee execution to successor.

[spatel]

Patch updated based on Sanjoy's suggestions:

1. Pass CallSite by value.
2. Change parent null checks to assert.
3. Use std::all_of()
4. Simplify logic for propagation of null attribute.
5. Add test case with 'readonly' call to show it is ok to propagate nonnull even if the call with nonnull is not first.

[spatel]

In D27855#626136, @silvas wrote:

This transform seems like it is sensitive to the order in which functions are visited when running function passes, which I think we try to avoid. I.e. if the ordering is right, we can propagate across arbitrarily many transitive calls; but if the ordering is wrong (e.g. we visit callers before callees) then we don't be able to propagate as much.

You may want to check with Chandler about whether it makes sense to do this. Based on my understanding of the rules, this is too strong of a transformation (looks at too large of a scope) to be a function pass (the rules as far as I understand them are essentially "we should be able to conceptually process functions in parallel"; and if the order of visitation matters, then our output will suddenly be sensitive to thread execution order; I don't think we meet this bar today, but I think it is a useful guideline / thing to strive for).

This would be a good argument for Mehdi's suggestion? Ie, this should be in FunctionAttrs.cpp?

[silvas]

In D27855#626141, @spatel wrote:

This would be a good argument for Mehdi's suggestion? Ie, this should be in FunctionAttrs.cpp?

Yes. I think that's the natural place to put this.

[spatel]

In D27855#626165, @silvas wrote:

In D27855#626141, @spatel wrote:

This would be a good argument for Mehdi's suggestion? Ie, this should be in FunctionAttrs.cpp?

Yes. I think that's the natural place to put this.

I have a draft of a patch to put this in FunctionAttrs instead of InstCombine which looks straightforward, but there's a problem:

define i1 @bar(i32* nonnull %x) {
  %ld = load i32, i32* %x
  %cmp = icmp eq i32 %ld, 42
  ret i1 %cmp
}

define i1 @foo(i32* %x) { ; we want this param marked 'nonnull'
  %d = call i1 @bar(i32* %x)
  %null_check = icmp eq i32* %x, null ; foo() always returns the result of bar()
  br i1 %null_check, label %t, label %f
t:
  ret i1 1
f:
  ret i1 %d
}

$ ./opt -functionattrs -inline -instcombine -simplifycfg isa12.ll -S
...

define i1 @foo(i32* nonnull readonly %x) #0 {
f:
  %ld.i = load i32, i32* %x, align 4
  %cmp.i = icmp eq i32 %ld.i, 42 ; success! no null check
  ret i1 %cmp.i
}

$ ./opt -O2 isa12.ll -S
...

define i1 @foo(i32* readonly %x) local_unnamed_addr #0 {
t:
  %ld.i = load i32, i32* %x, align 4
  %cmp.i = icmp eq i32 %ld.i, 42
  %null_check = icmp eq i32* %x, null ; FAIL
  %.d = or i1 %null_check, %cmp.i
  ret i1 %.d
}

$ ./opt -O2 -debug-pass=Arguments -S < /dev/null
...
Pass Arguments:
...
-inline -functionattrs

In the -O2 pipeline, -functionattrs is only called once (directly after -inline), so we hit the exact problem that I'm trying to avoid: the information provided by the callsite's arg attribute is gone. Is a change to the -O2 pipeline an acceptable follow-up to this patch?

[spatel]

Patch updated:
Move the logic and test cases from InstCombine to FuncAttrs to avoid sensitivity to function visit ordering, but this exposes a different ordering problem: -functionattrs is currently run after -inline, so this doesn't appear to help the motivating case at all.

[chandlerc]

In D27855#627203, @spatel wrote:

Patch updated:
Move the logic and test cases from InstCombine to FuncAttrs to avoid sensitivity to function visit ordering, but this exposes a different ordering problem: -functionattrs is currently run after -inline, so this doesn't appear to help the motivating case at all.

I don't think this is an issue of pass ordering. IMO, the issue is that we're losing information when inlining rather than preserving it. For example, your patch will catch cases where the called function *isn't* inlined. The patch is doing the correct thing, its just that you need two strategies here, not just one:

1. Handle case where secondary call is inlined.
2. Handle case where secondary call is not inlined.

Your patch handles #2 but not #1.

This is also somewhat abusing functionattrs IMO. You don't need this to be a function attribute at all.

I think the transformation this patch is trying to do is exactly what the "assume" framework tries to do -- you have one point in your code that makes an assumption valid (nonnull) and you want to use it later in that same code. The fact that in some cases you can promote this to an attribute on the argument is kind of incidental.

I think it would be better to teach valuetracking to look at whether a value is passed to an argument attributed 'nonnull' and/or teach the inliner to introduce an assume when inlining a function with a nonnull argument attribute to avoid losing that information.

If you want to keep the functionattrs change to try and propagate this across long distances of procedure calls, I'm all down with that. We should be able to do this kind of bottom-up inference. But it isn't really the right way to solve your proximate use case IMO, you should use that to solve more complex cases further down the road.

[spatel]

In D27855#627211, @chandlerc wrote:

In D27855#627203, @spatel wrote:

Patch updated:
Move the logic and test cases from InstCombine to FuncAttrs to avoid sensitivity to function visit ordering, but this exposes a different ordering problem: -functionattrs is currently run after -inline, so this doesn't appear to help the motivating case at all.

I don't think this is an issue of pass ordering. IMO, the issue is that we're losing information when inlining rather than preserving it. For example, your patch will catch cases where the called function *isn't* inlined. The patch is doing the correct thing, its just that you need two strategies here, not just one:

1. Handle case where secondary call is inlined.
2. Handle case where secondary call is not inlined.

Your patch handles #2 but not #1.

This is also somewhat abusing functionattrs IMO. You don't need this to be a function attribute at all.

I think the transformation this patch is trying to do is exactly what the "assume" framework tries to do -- you have one point in your code that makes an assumption valid (nonnull) and you want to use it later in that same code. The fact that in some cases you can promote this to an attribute on the argument is kind of incidental.

I think it would be better to teach valuetracking to look at whether a value is passed to an argument attributed 'nonnull' and/or teach the inliner to introduce an assume when inlining a function with a nonnull argument attribute to avoid losing that information.

If you want to keep the functionattrs change to try and propagate this across long distances of procedure calls, I'm all down with that. We should be able to do this kind of bottom-up inference. But it isn't really the right way to solve your proximate use case IMO, you should use that to solve more complex cases further down the road.

Thanks for the guidance! I agree that this a special case, but I thought I'd try this one first for the learning experience. On that count at least, progress. :)

On the associated llvm-dev thread, we've discussed related solutions involving llvm.assume and ValueTracking, so yes, I'll see what I can do with those too. And the interplay of analysis and (abuse of) attributes was also nicely explained.

Hopefully, I'll pick this back up in a couple of weeks, but if anyone else is interested (dyn_cast!), feel free to push ahead.

[spatel]

lib/Transforms/IPO/FunctionAttrs.cpp

586–587 ↗

(On Diff #82030)

Side note for reference: this gets in the way of any hoped-for change with the dyn_cast example. Those functions (there are ~25 functions to inline underneath one call to dyn_cast) are marked "linkonce_odr", so we don't even consider them with this patch.

[spatel]

I've spent some more time looking at the dyn_cast motivating case, and it seems we have multiple analysis and transform holes; it's going to take several fixes to correctly propagate and act on the nonnull info.

Related bugs:
https://llvm.org/bugs/show_bug.cgi?id=31512
https://llvm.org/bugs/show_bug.cgi?id=31518

If there isn't moral objection to this patch, I'd like to get this in just so I can cross it off the list of potential places where we might lose the nonnull. If the consensus is that this crosses the line into attribute abuse, I'll abandon and keep chasing the other leads.

[mehdi_amini]

In D27855#625773, @spatel wrote:

In D27855#625390, @spatel wrote:

In D27855#625386, @mehdi_amini wrote:

Isn't this something that could be part of the "Deduce function attributes" pass?

I actually looked at that first, but this (nonnull) is a parameter attribute rather than a function attribute, so it didn't seem like the right place. If I misunderstood the boundary, please let me know.

This time I looked closer, and sure enough we have FunctionAttrs.cpp::addArgumentAttrs(). So there already exists a place where we could splice this in. However, it still seems mismatched in intent because that function is dealing with interprocedural transforms, while this patch is limited to analysis within a single function.

It seems that FunctionAttrs.cpp::addArgumentAttrs() is doing the same level of thing:

In D27855#627211, @chandlerc wrote:

In D27855#627203, @spatel wrote:

Patch updated:
Move the logic and test cases from InstCombine to FuncAttrs to avoid sensitivity to function visit ordering, but this exposes a different ordering problem: -functionattrs is currently run after -inline, so this doesn't appear to help the motivating case at all.

I don't think this is an issue of pass ordering. IMO, the issue is that we're losing information when inlining rather than preserving it. For example, your patch will catch cases where the called function *isn't* inlined. The patch is doing the correct thing, its just that you need two strategies here, not just one:

1. Handle case where secondary call is inlined.
2. Handle case where secondary call is not inlined.

Your patch handles #2 but not #1.

This is also somewhat abusing functionattrs IMO. You don't need this to be a function attribute at all.

Uh? How do you handle 2) without an attribute? It seems fundamentally that we want to do bottom-up inter-procedural propagation here, which is what attributes are for AFAIK.

Are you saying that relying on the inter-procedural analysis for the purpose of intra-procedural analysis is not "the right thing to do"? I'd agree, but that does not invalidate the use case of inter-procedural though, right?

I think it would be better to teach valuetracking to look at whether a value is passed to an argument attributed 'nonnull' and/or teach the inliner to introduce an assume when inlining a function with a nonnull argument attribute to avoid losing that information.

That seems complementary to the "infer attribute approach", or I missed something?

If you want to keep the functionattrs change to try and propagate this across long distances of procedure calls, I'm all down with that. We should be able to do this kind of bottom-up inference. But it isn't really the right way to solve your proximate use case IMO, you should use that to solve more complex cases further down the road.

I think what you're saying here is matching my comments above, but I was not totally sure to parse it correctly.

[chandlerc]

I'll try and get a proper response to this later, but I wanted to very quickly mention that I'm somewhat opposed to us doing *any* stronger optimization on non-null until we teach Clang to strip off that attribute from memcpy, memmove, and memset.

Several versions of glibc have unfortunately added this attribute. There have already been *several* critical security vulnerabilities from optimizing based on on the attribute because code was never written to avoid a null pointer in the case where the *size was zero*.

I really want these optimizations on nonnull to go in, but I'd like to avoid having a (large) window of time where Clang will "miscompile" code using memcpy and friends in this way.

I've spoken with Richard Smith and he's going to send an email to cfe-dev about handling this in Clang. I'm also writing a paper for the C++ committee to standardize on somewhat more sane handling here. But I think we should at least defend users against the known misuses of this attribute and *then* start optimizing it harder. Are folks OK with that?

[spatel]

In D27855#634465, @chandlerc wrote:

I've spoken with Richard Smith and he's going to send an email to cfe-dev about handling this in Clang. I'm also writing a paper for the C++ committee to standardize on somewhat more sane handling here. But I think we should at least defend users against the known misuses of this attribute and *then* start optimizing it harder. Are folks OK with that?

That sounds ok to me. We could add a patch dependency here in phab to this, D28204, D27114 (any others?) once the clang patch is posted.
Given how many places drop the nonnull metadata, I'm surprised we ever get any nullptr optimizations. :)

[mehdi_amini]

Sounds to me like a good motivation indeed to wait for the change in clang first!

[spatel]

The cfe-dev discussion is underway:
http://lists.llvm.org/pipermail/cfe-dev/2017-January/052066.html

[reames]

Minor comments inline. I'm going to defer to Chandler on the clang specific implications here. This will strictly benefit my frontend and I'd like to see it land.

lib/Transforms/IPO/FunctionAttrs.cpp

537 ↗

(On Diff #82030)

I know this was request earlier in the review thread, but there are lots of cases where inlining drops information available at the call site. This isn't specific to this case. Doesn't hurt to call it out, but the wording seems to imply this is unique to this inference which it really isn't.

540 ↗

(On Diff #82030)

minor: call this Changed for consistency with the rest of the code.

547 ↗

(On Diff #82030)

Scanning only the entry block is perfectly reasonable for an initial patch, but could be easily extended, even without dominator information. walking forwards along single target branches or backwards from return points along single predecessor branches would give a more robust analysis.

(I would prefer this be done as a separate patch to make it easier to review.)

[spatel]

Patch updated:

1. Improved code comments and variable name as suggested by Philip.
2. Updated the last test to include 'nounwind' because the implementation of isGuaranteedToTransferExecutionToSuccessor() changed with rL290794.

[spatel]

Ping.

I don't follow cfe closely, but I don't see any cfe-dev posts about the libc work-around since Jan 4. Any updates or progress?

[spatel]

Ping * 2.

[spatel]

Ping * 3.

[mehdi_amini]

Aren't we blocked on clang? Or did it already stop emitting the null attr for memcpy and cie.

[spatel]

In D27855#671451, @mehdi_amini wrote:

Aren't we blocked on clang? Or did it already stop emitting the null attr for memcpy and cie.

That's what I'd like to know. There was no reply to my question here or the pings in D27114. I'm hoping to hear that the clang blocker is in someone's queue?
Apart from that, if there is any other feedback for this patch itself, please let me know. Thanks!

[mehdi_amini]

In D27855#671848, @spatel wrote:

That's what I'd like to know. There was no reply to my question here or the pings in D27114. I'm hoping to hear that the clang blocker is in someone's queue?

I think the blocker is real: we need clang to not annotate a few libc function before optimizing aggressively. At least this is my understanding of the email thread on clang-dev linked above.
(that does not mean that anyone is actively working on it at the moment)

[reames]

So as to unblock this review, I suggest that we introduce this change behind an off by default flag. Separately, we should pursue the clang side changes need to enable this flag by default. As stated previously, this will benefit my frontend and I'd like to see it land so that I can enable it.

Given the above, LGTM w/the off by default flag and minor comments addressed.

lib/Transforms/IPO/FunctionAttrs.cpp

550 ↗

(On Diff #83057)

minor: Should handle an invoke terminator as well.

[mehdi_amini]

In D27855#673633, @reames wrote:

So as to unblock this review, I suggest that we introduce this change behind an off by default flag. Separately, we should pursue the clang side changes need to enable this flag by default. As stated previously, this will benefit my frontend and I'd like to see it land so that I can enable it.

Sounds like a good plan!

[spatel]

Patch updated:

1. Hide the transform behind a disabled-by-default hidden flag.
2. Use CallSite so the transform works for invokes as well as calls.
3. Add a test case with invoke to show that works.

llvm/trunk/lib/Transforms/IPO/FunctionAttrs.cpp

 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
 STATISTIC(NumReturned, "Number of arguments marked returned");
 STATISTIC(NumReadNoneArg, "Number of arguments marked readnone");
 STATISTIC(NumReadOnlyArg, "Number of arguments marked readonly");
 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
 STATISTIC(NumNonNullReturn, "Number of function returns marked nonnull");
 STATISTIC(NumNoRecurse, "Number of functions marked as norecurse");
 
+// FIXME: This is disabled by default to avoid exposing security vulnerabilities
+// in C/C++ code compiled by clang:
+// http://lists.llvm.org/pipermail/cfe-dev/2017-January/052066.html
+static cl::opt<bool> EnableNonnullArgPropagation(
+    "enable-nonnull-arg-prop", cl::Hidden,
+    cl::desc("Try to propagate nonnull argument attributes from callsites to "
+             "caller functions."));
+
 namespace {
 typedef SmallSetVector<Function *, 8> SCCNodeSet;
 }
 
 namespace {
 /// The three kinds of memory access relevant to 'readonly' and
 /// 'readnone' attributes.
 enum MemoryAccessKind {
if (Value *RetArg = FindRetArg()) {
       ++NumReturned;
       Changed = true;
     }
   }
 
   return Changed;
 }
 
+/// If a callsite has arguments that are also arguments to the parent function,
+/// try to propagate attributes from the callsite's arguments to the parent's
+/// arguments. This may be important because inlining can cause information loss
+/// when attribute knowledge disappears with the inlined call.
+static bool addArgumentAttrsFromCallsites(Function &F) {
+  if (!EnableNonnullArgPropagation)
+    return false;
+
+  bool Changed = false;
+
+  // For an argument attribute to transfer from a callsite to the parent, the
+  // call must be guaranteed to execute every time the parent is called.
+  // Conservatively, just check for calls in the entry block that are guaranteed
+  // to execute.
+  // TODO: This could be enhanced by testing if the callsite post-dominates the
+  // entry block or by doing simple forward walks or backward walks to the
+  // callsite.
+  BasicBlock &Entry = F.getEntryBlock();
+  for (Instruction &I : Entry) {
+    if (auto CS = CallSite(&I)) {
+      if (auto *CalledFunc = CS.getCalledFunction()) {
+        for (auto &CSArg : CalledFunc->args()) {
+          if (!CSArg.hasNonNullAttr())
+            continue;
+
+          // If the non-null callsite argument operand is an argument to 'F'
+          // (the caller) and the call is guaranteed to execute, then the value
+          // must be non-null throughout 'F'.
+          auto *FArg = dyn_cast<Argument>(CS.getArgOperand(CSArg.getArgNo()));
+          if (FArg && !FArg->hasNonNullAttr()) {
+            FArg->addAttr(Attribute::NonNull);
+            Changed = true;
+          }
+        }
+      }
+    }
+    if (!isGuaranteedToTransferExecutionToSuccessor(&I))
+      break;
+  }
+  
+  return Changed;
+}
+
 /// Deduce nocapture attributes for the SCC.
 static bool addArgumentAttrs(const SCCNodeSet &SCCNodes) {
   bool Changed = false;
 
   ArgumentGraph AG;
 
   AttrBuilder B;
   B.addAttribute(Attribute::NoCapture);
 
   // Check each function in turn, determining which pointer arguments are not
   // captured.
   for (Function *F : SCCNodes) {
     // We can infer and propagate function attributes only when we know that the
     // definition we'll get at link time is *exactly* the definition we see now.
     // For more details, see GlobalValue::mayBeDerefined.
     if (!F->hasExactDefinition())
       continue;
 
+    Changed |= addArgumentAttrsFromCallsites(*F);
+
     // Functions that are readonly (or readnone) and nounwind and don't return
     // a value can't capture arguments. Don't analyze them.
     if (F->onlyReadsMemory() && F->doesNotThrow() &&
         F->getReturnType()->isVoidTy()) {
       for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A != E;
            ++A) {
         if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) {
           A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B));

llvm/trunk/test/Transforms/FunctionAttrs/nonnull.ll

-; RUN: opt -S -functionattrs %s | FileCheck %s
+; RUN: opt -S -functionattrs -enable-nonnull-arg-prop %s | FileCheck %s
 declare nonnull i8* @ret_nonnull()
 
 ; Return a pointer trivially nonnull (call return attribute)
 define i8* @test1() {
 ; CHECK: define nonnull i8* @test1
   %ret = call i8* @ret_nonnull()
   ret i8* %ret
 }
; CHECK: define nonnull i8* @test6
   br label %loop
 loop:
   %phi = phi i8* [%ret, %entry], [%phi, %loop]
   br i1 undef, label %loop, label %exit
 exit:
   ret i8* %phi
 }
 
+; Test propagation of nonnull callsite args back to caller.
+
+declare void @use1(i8* %x)
+declare void @use2(i8* %x, i8* %y);
+declare void @use3(i8* %x, i8* %y, i8* %z);
+
+declare void @use1nonnull(i8* nonnull %x);
+declare void @use2nonnull(i8* nonnull %x, i8* nonnull %y);
+declare void @use3nonnull(i8* nonnull %x, i8* nonnull %y, i8* nonnull %z);
+
+declare i8 @use1safecall(i8* %x) readonly nounwind ; readonly+nounwind guarantees that execution continues to successor
+
+; Can't extend non-null to parent for any argument because the 2nd call is not guaranteed to execute.
+
+define void @parent1(i8* %a, i8* %b, i8* %c) {
+; CHECK-LABEL: @parent1(i8* %a, i8* %b, i8* %c)
+; CHECK-NEXT:    call void @use3(i8* %c, i8* %a, i8* %b)
+; CHECK-NEXT:    call void @use3nonnull(i8* %b, i8* %c, i8* %a)
+; CHECK-NEXT:    ret void
+;
+  call void @use3(i8* %c, i8* %a, i8* %b)
+  call void @use3nonnull(i8* %b, i8* %c, i8* %a)
+  ret void
+}
+
+; Extend non-null to parent for all arguments.
+
+define void @parent2(i8* %a, i8* %b, i8* %c) {
+; CHECK-LABEL: @parent2(i8* nonnull %a, i8* nonnull %b, i8* nonnull %c)
+; CHECK-NEXT:    call void @use3nonnull(i8* %b, i8* %c, i8* %a)
+; CHECK-NEXT:    call void @use3(i8* %c, i8* %a, i8* %b)
+; CHECK-NEXT:    ret void
+;
+  call void @use3nonnull(i8* %b, i8* %c, i8* %a)
+  call void @use3(i8* %c, i8* %a, i8* %b)
+  ret void
+}
+
+; Extend non-null to parent for 1st argument.
+
+define void @parent3(i8* %a, i8* %b, i8* %c) {
+; CHECK-LABEL: @parent3(i8* nonnull %a, i8* %b, i8* %c)
+; CHECK-NEXT:    call void @use1nonnull(i8* %a)
+; CHECK-NEXT:    call void @use3(i8* %c, i8* %b, i8* %a)
+; CHECK-NEXT:    ret void
+;
+  call void @use1nonnull(i8* %a)
+  call void @use3(i8* %c, i8* %b, i8* %a)
+  ret void
+}
+
+; Extend non-null to parent for last 2 arguments.
+
+define void @parent4(i8* %a, i8* %b, i8* %c) {
+; CHECK-LABEL: @parent4(i8* %a, i8* nonnull %b, i8* nonnull %c)
+; CHECK-NEXT:    call void @use2nonnull(i8* %c, i8* %b)
+; CHECK-NEXT:    call void @use2(i8* %a, i8* %c)
+; CHECK-NEXT:    call void @use1(i8* %b)
+; CHECK-NEXT:    ret void
+;
+  call void @use2nonnull(i8* %c, i8* %b)
+  call void @use2(i8* %a, i8* %c)
+  call void @use1(i8* %b)
+  ret void
+}
+
+; The callsite must execute in order for the attribute to transfer to the parent.
+; It appears benign to extend non-null to the parent in this case, but we can't do that
+; because it would incorrectly propagate the wrong information to its callers.
+
+define void @parent5(i8* %a, i1 %a_is_notnull) {
+; CHECK-LABEL: @parent5(i8* %a, i1 %a_is_notnull)
+; CHECK-NEXT:    br i1 %a_is_notnull, label %t, label %f
+; CHECK:       t:
+; CHECK-NEXT:    call void @use1nonnull(i8* %a)
+; CHECK-NEXT:    ret void
+; CHECK:       f:
+; CHECK-NEXT:    ret void
+;
+  br i1 %a_is_notnull, label %t, label %f
+t:
+  call void @use1nonnull(i8* %a)
+  ret void
+f:
+  ret void
+}
+
+; The callsite must execute in order for the attribute to transfer to the parent.
+; The volatile load might trap, so there's no guarantee that we'll ever get to the call.
+
+define i8 @parent6(i8* %a, i8* %b) {
+; CHECK-LABEL: @parent6(i8* %a, i8* %b)
+; CHECK-NEXT:    [[C:%.*]] = load volatile i8, i8* %b
+; CHECK-NEXT:    call void @use1nonnull(i8* %a)
+; CHECK-NEXT:    ret i8 [[C]]
+;
+  %c = load volatile i8, i8* %b
+  call void @use1nonnull(i8* %a)
+  ret i8 %c
+}
+
+; The nonnull callsite is guaranteed to execute, so the argument must be nonnull throughout the parent.
+
+define i8 @parent7(i8* %a) {
+; CHECK-LABEL: @parent7(i8* nonnull %a)
+; CHECK-NEXT:    [[RET:%.*]] = call i8 @use1safecall(i8* %a)
+; CHECK-NEXT:    call void @use1nonnull(i8* %a)
+; CHECK-NEXT:    ret i8 [[RET]]
+;
+  %ret = call i8 @use1safecall(i8* %a)
+  call void @use1nonnull(i8* %a)
+  ret i8 %ret
+}
+
+; Make sure that an invoke works similarly to a call.
+
+declare i32 @esfp(...)
+
+define i1 @parent8(i8* %a, i8* %bogus1, i8* %b) personality i8* bitcast (i32 (...)* @esfp to i8*){
+; CHECK-LABEL: @parent8(i8* nonnull %a, i8* nocapture readnone %bogus1, i8* nonnull %b)
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    invoke void @use2nonnull(i8* %a, i8* %b)
+; CHECK-NEXT:    to label %cont unwind label %exc
+; CHECK:       cont:
+; CHECK-NEXT:    [[NULL_CHECK:%.*]] = icmp eq i8* %b, null
+; CHECK-NEXT:    ret i1 [[NULL_CHECK]]
+; CHECK:       exc:
+; CHECK-NEXT:    [[LP:%.*]] = landingpad { i8*, i32 }
+; CHECK-NEXT:    filter [0 x i8*] zeroinitializer
+; CHECK-NEXT:    unreachable
+;
+entry:
+  invoke void @use2nonnull(i8* %a, i8* %b)
+  to label %cont unwind label %exc
+
+cont:
+  %null_check = icmp eq i8* %b, null
+  ret i1 %null_check
+
+exc:
+  %lp = landingpad { i8*, i32 }
+  filter [0 x i8*] zeroinitializer
+  unreachable
+}