[Attributor][MustExec] Deduce dereferenceable and nonnull attribute using MustBeExecutedContextExplorer

[uenoku]

Summary

In D65186 and related patches, MustBeExecutedContextExplorer is introduced. This enables us to traverse instructions guaranteed to execute from function entry. If we can know the argument is used as dereferenceable or nonnull in these instructions, we can mark dereferenceable or nonnull in the argument definition:

1. Memory instruction (similar to D64258)

Trace memory instruction pointer operand. Currently, only inbounds GEPs are traced.

define i64* @f(i64* %a) {
entry:
  %add.ptr = getelementptr inbounds i64, i64* %a, i64 1
; (because of inbounds GEP we can know that %a is at least dereferenceable(16))
  store i64 1, i64* %add.ptr, align 8
  ret i64* %add.ptr ; dereferenceable 8 (because above instruction stores into it)
}

2. Propagation from callsite (similar to D27855)

If deref or nonnull are known in call site parameter attributes we can also say that argument also that attribute.

declare void @use3(i8* %x, i8* %y, i8* %z);
declare void @use3nonnull(i8* nonnull %x, i8* nonnull %y, i8* nonnull %z);

define void @parent1(i8* %a, i8* %b, i8* %c) {
  call void @use3nonnull(i8* %b, i8* %c, i8* %a) 
; Above instruction is always executed so we can say that@parent1(i8* nonnnull %a, i8* nonnull %b, i8* nonnull %c)
  call void @use3(i8* %c, i8* %a, i8* %b)
  ret void
}

[xbolva00]

What about

memcmp(a,b,16) ? Can we infer that a,b are deref(16)?

If so, D53342 should handle it (I need to update it)

[uenoku]

In D65402#1604695, @xbolva00 wrote:

What about

memcmp(a,b,16) ? Do we infer that a,b are nonnull and deref(16)?

Same for many libc functions..

It can't be inferred in current attributes set.

To infer this, I think we need to introduce a new attribute similar to allocsize something like:
dereferenceable_arg(argno): dereferenceable size depends on argno-th argument value
ex)

declare i32 @memcmp(i8* dereferenceable_arg(2), i8* dereferenceable_arg(2), i64)

If we add this attribute and annotate libc function, I think the deduction is not so hard.

[xbolva00]

Thanks for confirmation that it would be okay to add.

I think we do not need 'dereferenceable_arg' for C libcalls since we can handle only constant sizes (memcmp/memcpy/memmove(p1, p2, C) where C > 0) anyway (if inteested, you can follow older discussion in D53342 :)).

Edit: but as an general idea, dereferenceable_arg seems like a nice idea :)

[jdoerfert]

I thought about this some more. I think you should move the explorer into the InformationCache and expose a query method like this:

void exploreMustExecuteContext(Instruction &I, SmallVectorImpl<Instruction *> &Worklist, std::function <bool(Instruction &I, bool /* MustBeExecutedWith */)> &QueryResultCallback);

The idea is:

• The InformationCache will make sure that the explore iterator is "incremented" if needed, e.g., intiially just run it until there is no more instruction to be found.
• The worklist will be populated by interesting instructions, most of the timer (transitive) users.
• The callback informs of the result and allows to re-populate the worklist. If it returns false, the exploration is aborted.
• The InformationCache will pop an instruction from the worklist, check if the explore iterator "contains" it, potentially increases the explored context, and return the result through the callback.

I think this will work well for most attributes we have now, what are your thoughts?

Also, do this exploration stuff for now only in the initialize method.

llvm/test/Transforms/FunctionAttrs/nosync.ll

100

volatile loads/stores do not imply dereferenceability.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

3027

Similar to D64258, a follow up patch could keep track of all non-inbounds accessed bytes, build a vector that marks each of them starting at the base pointer, and then deriving dereferenceability as the number of consecutive accessed bytes.

[uenoku]

In D65402#1605702, @jdoerfert wrote:

The idea is:

• The InformationCache will make sure that the explore iterator is "incremented" if needed, e.g., intiially just run it until there is no more instruction to be found.
• The worklist will be populated by interesting instructions, most of the timer (transitive) users.
• The callback informs of the result and allows to re-populate the worklist. If it returns false, the exploration is aborted.
• The InformationCache will pop an instruction from the worklist, check if the explore iterator "contains" it, potentially increases the explored context, and return the result through the callback.
  
  I think this will work well for most attributes we have now, what are your thoughts?

I think this is reasonable.

[jdoerfert]

In D65402#1606684, @uenoku wrote:

In D65402#1605702, @jdoerfert wrote:

The idea is:

• The InformationCache will make sure that the explore iterator is "incremented" if needed, e.g., intiially just run it until there is no more instruction to be found.
• The worklist will be populated by interesting instructions, most of the timer (transitive) users.
• The callback informs of the result and allows to re-populate the worklist. If it returns false, the exploration is aborted.
• The InformationCache will pop an instruction from the worklist, check if the explore iterator "contains" it, potentially increases the explored context, and return the result through the callback.
  
  I think this will work well for most attributes we have now, what are your thoughts?

I think this is reasonable.

Alternatively, we could do the following in the explorer (which I now find much nicer):

Given a predicate and an program point PP (=instruction), check if that predicate holds for sure if PP is executed. The nice part would be we move the logic there and we could handle "paths" later.
E.g., pred(A) and pred(B) are true, the method could say true for something like PP; if (...) A; else B;

If you want you could look into this, otherwise I will.

[uenoku]

Address comment.

• Add checkPredicateAfterInstruction in Explorer.
• Add tests in nonnull about path exploration.

[jdoerfert]

One nit, and one problem that can be easily fixed and needs to be tested.
Otherwise, LGTM.

llvm/lib/Transforms/IPO/Attributor.cpp

466

make helpers static, also below. I somehow thought this function exists somewhere but I might be wrong.

3023

This is not correct, I think. We should add a test for sure.

The problem is that there could be bitcasts between base and I which cause the accessed bytes to be less than the base type would suggest.

So

i32* %A
load i8, i8* (bitcast i32* %A to i8*)

should cause deref(1) on %A but not deref(4)

[uenoku]

Alternatively, we could do the following in the explorer (which I now find much nicer):

Given a predicate and an program point PP (=instruction), check if that predicate holds for sure if PP is executed. The nice part would be we move the logic there and we could handle "paths" later.
E.g., pred(A) and pred(B) are true, the method could say true for something like PP; if (...) A; else B;

Regarding this, it seems very interesting and I uploaded a prototype for deduction using paths(D65593).

[uenoku]

Rebase and address comment. A Test is added to dereferenceable.ll.

[xbolva00]

Hi,

So with this patch and enabled Attributor I expect that arguments will be annotated with dereferenceable(16) (propagated from callsite), right?

My IR:

define dso_local void @alias(i8* nocapture %s, i8* nocapture %p) local_unnamed_addr #0 {
entry:

tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* noalias align 1 dereferenceable(16) %s, i8* noalias align 1 dereferenceable(16) %p, i64 16, i1 false)
%0 = load i8, i8* %s, align 1, !tbaa !2
%arrayidx = getelementptr inbounds i8, i8* %p, i64 3
store i8 %0, i8* %arrayidx, align 1, !tbaa !2
%1 = load i8, i8* %s, align 1, !tbaa !2
%arrayidx1 = getelementptr inbounds i8, i8* %p, i64 4
store i8 %1, i8* %arrayidx1, align 1, !tbaa !2
ret void

}

[xbolva00]

(and do you plan to propagate noalias too?)

[uenoku]

@xbolva00
Thank you for your comment!

So with this patch and enabled Attributor I expect that arguments will be annotated with dereferenceable(16) (propagated from callsite), right?

Yes.

(and do you plan to propagate noalias too?)

Yes. I'll do it. I'm going to work on other attributes too but I want to generalize this kind of deduction. I mean, AbstractState in the same MustBeExecutedContext can share their (known) information.

[xbolva00]

Super! Thanks.

[uenoku]

Refactor

• Create accumulatePredOnMustBeExecutedContext as Attributor member function
• Look at known information of Argument in the callsite argument updateImpl. It is not allowed to look at assumption in argument but I think it is sound to look at known information.
• Use AbstractState operator to combine state.

This patch now fails Transforms/FunctionAttrs/read_write_returned_arguments_scc.lldue to Attributor verification.
I think this is because in some case, CallSiteArgumentAttribute reaches pessimistic fixpoint faster than the function ArgumentAttribute gets known information.

To introduce backward propagation of known information, we need to fix this problem.

[jdoerfert]

llvm/include/llvm/Transforms/IPO/Attributor.h

904

Could we call it StateType, make the std::function a function_ref, and PP a reference please.

Also, I think it makes sense to have an early exit. Maybe make the predicate a function_ref<bool(const Instruction &, State &)> which updates the state in place if necessary and returns true as long as it wants to continue exploring.

llvm/lib/Transforms/IPO/Attributor.cpp

564

Very cool, but make it static or put it in an anonymous namespace.

1725

I thought about this some more:

1. Should we do this traversal for nonnull explicitly or just do it for deref and then have nonnull ask the deref attribute if nonnul is implied. (for now most use cases will not have null as a valid pointer)
2. We should not traverse the context of the same instruction multiple times, or at least not in every update. What we could do is run this in the initialize and remember the AA's that would imply the current one (line 1202). In the update we then only check if any of the implied ones is *known* if not we try to determine it the usual way.

( &getAnchorScope().getEntryBlock().front(), will become getCtxI())

llvm/test/Transforms/InferFunctionAttrs/dereferenceable.ll

11

Could we have more versions of this test:

Positive:

• only the access to %arrayidx3 should suffice
• all accesses but without the inbounds keyword

Negative:

• only the access to %arrayidx3 without the inbound keyword

[xbolva00]

Hello folks,

Yesterday I came up with idea to annonate allocation functions with deref_or_null.

malloc(40) -> annotate return value of malloc with deref_or_null(40) -> Good, I will work on this idea.

Now I present some ideas for Attributor (maybe following cases already work.. I didnt check them).

Use case 1:
p = malloc(40) deref_or_null(40)
p[1] = 100; here, we can change deref_or_null(40) to deref(40) since if p was null, it is UB.

Use case 2:
p = malloc(40) // deref_or_null(40)
if (p) {

in this block p is now  deref(40)! cool.

}

Use case 3
p = malloc(40) // deref_or_null(40)
if (someotherbool) {

p[1] = 100; // here, we can change  deref_or_null(40) to  deref(40) since if p was null, it is UB.

}

What do you think? Can attributor do it? I think use case 1 is doable, 2 and 3 a bit harder ones.
Maybe @reames is interested too in this area? Please comment this idea :)

I think precise deref info can enable really neat things, see https://bugs.llvm.org/show_bug.cgi?id=43003.

[jdoerfert]

In D65402#1631204, @xbolva00 wrote:

Hello folks,

Yesterday I came up with idea to annonate allocation functions with deref_or_null.

malloc(40) -> annotate return value of malloc with deref_or_null(40) -> Good, I will work on this idea.

Now I present some ideas for Attributor (maybe following cases already work.. I didnt check them).

Use case 1:
p = malloc(40) deref_or_null(40)
p[1] = 100; here, we can change deref_or_null(40) to deref(40) since if p was null, it is UB.

This should work with these patches, yes. (It will be deref(40) if nullptr is not a valid pointer else it is deref(2).)

Use case 2:
p = malloc(40) // deref_or_null(40)
if (p) {

in this block p is now  deref(40)! cool.

}

Yes, this will work at some point soon, it might already if the nonnull query is already using the "context instruction". However, there might not be a way to annotate the information. Passes will soon (after the series that ends in D66276) be able to build a Attributor and query a single property, e.g., the dereferenceability property of a pointer inside some control. We might also think about better dereferenceability annotations, maybe an intrinsic. This also ties in with the new deref and deref_globally (D61652).

Use case 3
p = malloc(40) // deref_or_null(40)
if (someotherbool) {

p[1] = 100; // here, we can change  deref_or_null(40) to  deref(40) since if p was null, it is UB.

}

Similar to above.

What do you think? Can attributor do it? I think use case 1 is doable, 2 and 3 a bit harder ones.

All are well in the scope of what we (will soon) have.

Maybe @reames is interested too in this area? Please comment this idea :)

I think precise deref info can enable really neat things, see https://bugs.llvm.org/show_bug.cgi?id=43003.

Once these patches are in we need to switch to deref and deref_globally (D61652). We should also consider using deref_globally (or sth similar) to indicate that all existing accesses will be dereferenceable, e.g.,
if we have an alloc or a malloc for which we can show it returns sth dereferenceable and the pointer is not used after the free.

[xbolva00]

Good to know, thanks for info!

[xbolva00]

Hi,
my another question :)
clang -std=c99 -Ofast -DNDEBUG -S -emit-llvm -mllvm -enable-nonnull-arg-prop -mllvm -attributor-disable=false code.c

define dso_local noalias %struct.tHashTableItem* @symbolNewCopy(%struct.tHashTableItem* nocapture readonly %symbol) local_unnamed_addr #2 {
entry:

%call = tail call noalias i8* @malloc(i64 64) #8
%0 = bitcast i8* %call to %struct.tHashTableItem*
%1 = bitcast %struct.tHashTableItem* %symbol to i8*
tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 8 dereferenceable(64) %call, i8* nonnull align 8 dereferenceable(64) %1, i64 64, i1 false)
%cmp = icmp eq i8* %call, null

Curently LLVM fails to propagate attributes to arguments thru bitcasts, it seems. With this patch help with this case?

[xbolva00]

Uhm.

Even simple case with "-mllvm -enable-nonnull-arg-prop" does not work.. strange. Hopefully with Attributor it would work.

define dso_local noalias %struct.tHashTableItem* @symbolNewCopy(i8* nocapture readonly %s) local_unnamed_addr #0 {
entry:

%call = tail call noalias i8* @calloc(i64 1, i64 64) #8
%call.i = tail call noalias i8* @calloc(i64 1, i64 64) #8
%Index.i = getelementptr inbounds i8, i8* %call.i, i64 24
%0 = bitcast i8* %Index.i to i32*
store i32 -1, i32* %0, align 8, !tbaa !14
%bcmp = tail call i32 @bcmp(i8* nonnull dereferenceable(7) %call.i, i8* nonnull dereferenceable(7) %s, i64 7)

[uenoku]

Address some comments and change to structured deduction. I'll add new test mentioned in the comment later.

[uenoku]

In D65402#1638243, @xbolva00 wrote:

Hi,
my another question :)
clang -std=c99 -Ofast -DNDEBUG -S -emit-llvm -mllvm -enable-nonnull-arg-prop -mllvm -attributor-disable=false code.c

define dso_local noalias %struct.tHashTableItem* @symbolNewCopy(%struct.tHashTableItem* nocapture readonly %symbol) local_unnamed_addr #2 {
entry:

%call = tail call noalias i8* @malloc(i64 64) #8
%0 = bitcast i8* %call to %struct.tHashTableItem*
%1 = bitcast %struct.tHashTableItem* %symbol to i8*
tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 8 dereferenceable(64) %call, i8* nonnull align 8 dereferenceable(64) %1, i64 64, i1 false)
%cmp = icmp eq i8* %call, null

Curently LLVM fails to propagate attributes to arguments thru bitcasts, it seems. With this patch help with this case?

In D65402#1638312, @xbolva00 wrote:

Uhm.

Even simple case with "-mllvm -enable-nonnull-arg-prop" does not work.. strange. Hopefully with Attributor it would work.

define dso_local noalias %struct.tHashTableItem* @symbolNewCopy(i8* nocapture readonly %s) local_unnamed_addr #0 {
entry:

%call = tail call noalias i8* @calloc(i64 1, i64 64) #8
%call.i = tail call noalias i8* @calloc(i64 1, i64 64) #8
%Index.i = getelementptr inbounds i8, i8* %call.i, i64 24
%0 = bitcast i8* %Index.i to i32*
store i32 -1, i32* %0, align 8, !tbaa !14
%bcmp = tail call i32 @bcmp(i8* nonnull dereferenceable(7) %call.i, i8* nonnull dereferenceable(7) %s, i64 7)

These cases are not so complex that I think this patch can handle.

[xbolva00]

Happy to hear :)

[uenoku]

Fix dererefenceable

[uenoku]

Refactor

[uenoku]

llvm/lib/Transforms/IPO/Attributor.cpp

1725

In the current patch, context is traversed only in initialize and collect *interesting* AA. In updateImpl, these AAs will be merged into the state.

[uenoku]

Fix broken patch.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

750

I have the feeling the logic you add here works not only for arguments but other positions too, right? If so, we should make it a helper class that can be reused. In the generic case you can use getIRPosition().getCtxI() for the program point.

I'm also still unsure if we should not somehow "filter" the explored instructions based on the uses of the associated value. Maybe we could do the following:

• In accumulatePredOnMustBeExecutedContext you take another method that yields "interesting" instructions we would like to visit if they are in the must-be-executed-context (MBECtx).
• The function for deref would look at the uses of the associated value and ask for the users. If the user was found, it can transitively ask for its user (if it wants to). If the user was not found, we do not go further (would require path exploration).
• If the asked for user is not in the visited set of the MBECtxIterator, we visit more instructions until we explored the context or we found the instruction we are looking for.

Does this make sense?

[uenoku]

Apply to call site argument or floating value also.

[jdoerfert]

I still think we should try to look only at (transitive) uses of the associated value instead of visiting all instructions and figuring out for each if it is interesting. You know what I mean?

llvm/include/llvm/Analysis/ValueTracking.h

259 ↗

(On Diff #217078)

You can commit this separatly. It looks good to me.

llvm/lib/Transforms/IPO/Attributor.cpp

707

Make this just StateType

758

Why can't we do this in the initialize?

[uenoku]

In D65402#1645907, @jdoerfert wrote:

I still think we should try to look only at (transitive) uses of the associated value instead of visiting all instructions and figuring out for each if it is interesting. You know what I mean?

Tracking transitive uses is also good to me but I'm not sure there is an API to (efficiently) determine whether use of the associated value belongs to the context. Isn't it same to iterator over the instructions in the context?

llvm/lib/Transforms/IPO/Attributor.cpp

758

In the registerAA, AA on-demand created may be overwritten. I'm not sure whether it is intended or bug. Then, I wanted to avoid to store the address of AAs in initialize.

[jdoerfert]

In D65402#1646335, @uenoku wrote:

In D65402#1645907, @jdoerfert wrote:

I still think we should try to look only at (transitive) uses of the associated value instead of visiting all instructions and figuring out for each if it is interesting. You know what I mean?

Tracking transitive uses is also good to me but I'm not sure there is an API to (efficiently) determine whether use of the associated value belongs to the context. Isn't it same to iterator over the instructions in the context?

Given a use U, check if the user is an instruction dyn_cast<Instruction>(U.getUser()) and ask the iterator if it is contained (It.count(...)). If the result is false we can try to explore further but let's start by exploring the context to the fullest and then doing the use & user stuff

[jdoerfert]

Is this blocked on anything right now? I would really like this capability :)

[uenoku]

I got it. I'll rebase it within a week :)

[uenoku]

Rebase and change the way to track (transitive) uses. Some test changes are missing.

[jdoerfert]

I like this version a lot better. Selectively looking into the context is the right choice (I think). I added some comments, when the tests are updated I'll give it a last look over but this looks almost ready to me.

llvm/lib/Transforms/IPO/Attributor.cpp

713

Please describe the type of followUse in more detail here. (what arguments, what do they mean, that the update logic should go in there, what not to do, etc.)

750

I would have though we need to advance the explorer iterator somewhere?

2486

This code looks like the other followUse. Can we have a helper like getKnownNonNullAndDerefBytesForUse which we call from both? (Maybe that also is reusable/combinable with the existing logic we have)

llvm/test/Transforms/FunctionAttrs/dereferenceable.ll

189

I think we lack a return value only test, see below.

define i32* @f7_3() {
; ATTRIBUTOR: define nonnull dereferenceable(4) i32* @f7_3()
  %ptr = tail call i32* @unkown_ptr()
  store i32 10, i32* %ptr, align 16
  ret i32* %ptr
}

[uenoku]

Address comment

[uenoku]

Minor update.

[jdoerfert]

Hopefully last round of comments.

llvm/lib/Transforms/IPO/Attributor.cpp

751

This also only works for the first time the explorer iterator is created, the contains call before was the right way (as long as the explorer works the way it does now).

You can do sth like:

for (const Use *U : Uses) {
  const Instruction *UserI = cast<Instruction>(U->getUser());
  auto EIt = Explorer.begin(CtxI), EEnd = Explorer.end(CtxI);
  bool Found = EIt.contains(UserI);
  while (!Found && ++EIt != EEnd)
     Found = EIt.getCurrentInst() == UserI;
  if (Found && Base::followUse(A, U, UserI))
    for (const Use &Us : UserI->uses())
              Uses.insert(&Us);
}

1553

This is only true, I think, if null is not a valid pointer.

1566

Reading this line it was at first not clear to me that I has to be an access for this to return a base pointer.

1607

Do we want this change or was it just for debugging? Shouldn't it already say "nonnull [fix]" if it is known?

1635

Change is not used. You could check if it is fixed/known after this update and not do the stuff below in that case.

llvm/test/Transforms/FunctionAttrs/dereferenceable.ll

197

Is this derived or not? There is the same string after the FIXME and ATTRIBUTOR, right?

[uenoku]

Address comments.

llvm/lib/Transforms/IPO/Attributor.cpp

1566

What does it mean?

1607

It was just for debugging.

llvm/test/Transforms/FunctionAttrs/dereferenceable.ll

197

This is derived.

[xbolva00]

Nice, +1

Is this the last remaining work before you turn the attributor on?

[jdoerfert]

One minor and one not so minor comment inlined. That is the last problem I found and once fixed this is fine :)

In D65402#1689907, @xbolva00 wrote:

Nice, +1

Is this the last remaining work before you turn the attributor on?

No, tuning is still needed, right now we focused on applicability and aggressive optimizations. I fixed all bugs I found in the TS and SPEC2006 the other day but I'll have to do that again with more benchmarks soon. This patch is important to fix various issues, one of which is the dereferenceability problem we have (D61652). I'll work on tuning and measuring the Attributor over the next two weeks, present results at the Dev-Meeting, and hopefully I'm able to propose to turn it on by then.

llvm/lib/Transforms/IPO/Attributor.cpp

1566

That means we might want to add a comment here or rename getBasePointerOfPointerOperand to something like getBasePointerOfAccessPointerOperand.

1571

Don't we have to check if offset is negative? Do we have a test?

something like A[-2] = 0; should not cause deref bytes. E.g., we might need to use 64 bit and signed version of deref bytes. but non-null can be set as soon as we know there is an access and null is not a valid pointer (probably need tests for these as well).

I thought we have a helper somewhere to deal with this offset and access size logic already?

[uenoku]

Rename method name.

[uenoku]

Minor update.

[uenoku]

Add test for minus index.

[uenoku]

Currently, any use is not tracked so nothing about A[1] or A[-2] is deduced.

This would be solved once making it track gep instruction. But beforehand, I strongly suggest separating deduction for known/assumption respectively.

[jdoerfert]

In D65402#1694872, @uenoku wrote:

Currently, any use is not tracked so nothing about A[1] or A[-2] is deduced.

As long as we have a test that is fine.

This would be solved once making it track gep instruction. But beforehand, I strongly suggest separating deduction for known/assumption respectively.

What do you mean by the separation part?

I inlined one comment, if you agree with that one and the proposed fix, the rest looks good to me. If not, let me know.

llvm/lib/Transforms/IPO/Attributor.cpp

1575

I'm still unsure about this logic, correct me if I'm wrong but we have:

`Base = Offset + I.getPointer()`

and we know due to the access I that there are D dereferenceable bytes with

`D = DL.getTypeStoreSize(getPointerOperand(I)->getType()->getPointerElementType());`

Now, deref from Base should be:

`max(0, D + Offset)`

which is the same we have AADereferenceableFloating::updateImpl, but with an offset in the other direction, I think.

llvm/test/Transforms/FunctionAttrs/dereferenceable.ll

199

I don't think we can deduce much about %p but only about the return, so I would expect

`FIXME: This should be define nonnull dereferenceable(8) i32* @test_for_minus_index(i32* nonnull %p)`

or an explanation why %p is deref.

[uenoku]

In D65402#1695253, @jdoerfert wrote:

In D65402#1694872, @uenoku wrote:

Currently, any use is not tracked so nothing about A[1] or A[-2] is deduced.

As long as we have a test that is fine.

This would be solved once making it track gep instruction. But beforehand, I strongly suggest separating deduction for known/assumption respectively.

What do you mean by the separation part?

I mean, running two different deduction scheme(known, assumption) might cause an unpredictable result.

define i32* @test_for_minus_index(i32* %p) {
  %q = getelementptr inbounds i32, i32* %p, i32 -2
  store i32 1, i32* %q
  ret i32* %q
}

AANonNullArgument is composed of AAArgumentFromCallSiteArguments, AAFromMustBeExecutedContext.
Assume that gep is tracked in followUse.

Iteration 1 :

• AAFromMustBeExecutedContext will traverse uses of %p and prepare uses of %q for next iteration.
• AAArgumentFromCallSiteArguments will call indicatePessimisticFixpoint because the function is not internal function.

AANonNullArgument has already reached to pessimistic fixpoint so nonnull won't be deduced.

This example is so simple that we can debug them but it is hard to debug more complex ones.

[jdoerfert]

In D65402#1696036, @uenoku wrote:

In D65402#1695253, @jdoerfert wrote:

In D65402#1694872, @uenoku wrote:

Currently, any use is not tracked so nothing about A[1] or A[-2] is deduced.

As long as we have a test that is fine.

This would be solved once making it track gep instruction. But beforehand, I strongly suggest separating deduction for known/assumption respectively.

What do you mean by the separation part?

I mean, running two different deduction scheme(known, assumption) might cause an unpredictable result.

define i32* @test_for_minus_index(i32* %p) {
  %q = getelementptr inbounds i32, i32* %p, i32 -2
  store i32 1, i32* %q
  ret i32* %q
}

AANonNullArgument is composed of AAArgumentFromCallSiteArguments, AAFromMustBeExecutedContext.
Assume that gep is tracked in followUse.

Iteration 1 :

• AAFromMustBeExecutedContext will traverse uses of %p and prepare uses of %q for next iteration.
• AAArgumentFromCallSiteArguments will call indicatePessimisticFixpoint because the function is not internal function.

AANonNullArgument has already reached to pessimistic fixpoint so nonnull won't be deduced.

This example is so simple that we can debug them but it is hard to debug more complex ones.

I see. You can explore uses exhaustively though that is a "local" solution to a general problem.
I think we need to keep known & assumed together but we should provide a way for AAs that have multiple deduction strategies to exhaust them seperatly, e.g, AAArgumentFromCallSiteArguments is known to have 2 schemes so we should track their "fixpoints" separate somehow.
In addition, or as an alternative, we could allow updates for AAs in a fixpoint if they opt-in to it. They would do so if they can improve based on known-information around them.

[uenoku]

In D65402#1696345, @jdoerfert wrote:

In D65402#1696036, @uenoku wrote:

In D65402#1695253, @jdoerfert wrote:

In D65402#1694872, @uenoku wrote:

Currently, any use is not tracked so nothing about A[1] or A[-2] is deduced.

As long as we have a test that is fine.

This would be solved once making it track gep instruction. But beforehand, I strongly suggest separating deduction for known/assumption respectively.

What do you mean by the separation part?

I mean, running two different deduction scheme(known, assumption) might cause an unpredictable result.

define i32* @test_for_minus_index(i32* %p) {
  %q = getelementptr inbounds i32, i32* %p, i32 -2
  store i32 1, i32* %q
  ret i32* %q
}

AANonNullArgument is composed of AAArgumentFromCallSiteArguments, AAFromMustBeExecutedContext.
Assume that gep is tracked in followUse.

Iteration 1 :

• AAFromMustBeExecutedContext will traverse uses of %p and prepare uses of %q for next iteration.
• AAArgumentFromCallSiteArguments will call indicatePessimisticFixpoint because the function is not internal function.

AANonNullArgument has already reached to pessimistic fixpoint so nonnull won't be deduced.

This example is so simple that we can debug them but it is hard to debug more complex ones.

I see. You can explore uses exhaustively though that is a "local" solution to a general problem.
I think we need to keep known & assumed together but we should provide a way for AAs that have multiple deduction strategies to exhaust them seperatly, e.g, AAArgumentFromCallSiteArguments is known to have 2 schemes so we should track their "fixpoints" separate somehow.
In addition, or as an alternative, we could allow updates for AAs in a fixpoint if they opt-in to it. They would do so if they can improve based on known-information around them.

Looks good. Anyway, the current code maintains soundness ( "general" solution might not be reached) so I'll commit it if there is no problem.

[uenoku]

Rebase.

[uenoku]

Address the last comments.

llvm/lib/Transforms/IPO/Attributor.cpp

1575

I agree.

llvm/test/Transforms/FunctionAttrs/dereferenceable.ll

199

It is my mistake. Fixed.

[xbolva00]

dereferenceable attribute is not added to the arguments?

define dso_local void @_Z3fooPaS_S_ii(i8* noalias nocapture writeonly %0, i8* noalias nocapture readnone %1, i8* noalias nocapture readonly %2, i32 %3, i32 %4) local_unnamed_addr #0 {

tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* noalias nocapture nonnull writeonly align 1 dereferenceable(16) %0, i8* noalias nocapture nonnull readonly align 1 dereferenceable(16) %2, i64 16, i1 false) #2
ret void

}

I would expect

define dso_local void @_Z3fooPaS_S_ii(i8* noalias nocapture writeonly dereferenceable(16) %0, i8* noalias nocapture readnone %1, i8* noalias nocapture readonly dereferenceable(16) %2, i32 %3, i32 %4) local_unnamed_addr #0 {

tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* noalias nocapture nonnull writeonly align 1 dereferenceable(16) %0, i8* noalias nocapture nonnull readonly align 1 dereferenceable(16) %2, i64 16, i1 false) #2
ret void

}

https://godbolt.org/z/if9rle

[uenoku]

In D65402#1701550, @xbolva00 wrote:

dereferenceable attribute is not added to the arguments?

define dso_local void @_Z3fooPaS_S_ii(i8* noalias nocapture writeonly %0, i8* noalias nocapture readnone %1, i8* noalias nocapture readonly %2, i32 %3, i32 %4) local_unnamed_addr #0 {

tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* noalias nocapture nonnull writeonly align 1 dereferenceable(16) %0, i8* noalias nocapture nonnull readonly align 1 dereferenceable(16) %2, i64 16, i1 false) #2
ret void

}

I would expect

define dso_local void @_Z3fooPaS_S_ii(i8* noalias nocapture writeonly dereferenceable(16) %0, i8* noalias nocapture readnone %1, i8* noalias nocapture readonly dereferenceable(16) %2, i32 %3, i32 %4) local_unnamed_addr #0 {

tail call void @llvm.memcpy.p0i8.p0i8.i64(i8* noalias nocapture nonnull writeonly align 1 dereferenceable(16) %0, i8* noalias nocapture nonnull readonly align 1 dereferenceable(16) %2, i64 16, i1 false) #2
ret void

}

https://godbolt.org/z/if9rle

Actually, dereferenceable is added to the arguments if opt is executed for the above IR. https://godbolt.org/z/CItEJG

As far as I see the log, the problem is that InstCombine is located after Attributor Pass in -O3. Therefore, dereferenceable is not propagated.
Please take a look at the stderr output in https://godbolt.org/z/l_6aVE.

Solutions are to change the order or to run the Attributor several times.

[xbolva00]

This comment was removed by xbolva00.

[xbolva00]

Yeah, you probably want to run it multiple times.

@jdoerfert

llvm/include/llvm/Transforms/IPO/Attributor.h

 #ifndef LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
 #define LLVM_TRANSFORMS_IPO_ATTRIBUTOR_H
 
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SCCIterator.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CallGraph.h"
+#include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
 struct AbstractAttribute;
 struct InformationCache;

 /// is called.
 ///
 /// If custom abstract attributes, registered manually through
 /// Attributor::registerAA(...), need more information, especially if it is not
 /// reusable, it is advised to inherit from the InformationCache and cast the
 /// instance down in the abstract attributes.
 struct InformationCache {
   InformationCache(const Module &M, AnalysisGetter &AG)
-      : DL(M.getDataLayout()), AG(AG) {
+      : DL(M.getDataLayout()), Explorer(/* ExploreInterBlock */ true), AG(AG) {
 
     CallGraph *CG = AG.getAnalysis<CallGraphAnalysis>(M);
     if (!CG)
       return;
 
     DenseMap<const Function *, unsigned> SccSize;
     for (scc_iterator<CallGraph *> I = scc_begin(CG); !I.isAtEnd(); ++I) {
       for (CallGraphNode *Node : *I)
struct InformationCache {
   /// A vector type to hold instructions.
   using InstructionVectorTy = std::vector<Instruction *>;
 
   /// Return the instructions in \p F that may read or write memory.
   InstructionVectorTy &getReadOrWriteInstsForFunction(const Function &F) {
     return FuncRWInstsMap[&F];
   }
 
+  /// Return MustBeExecutedContextExplorer
+  MustBeExecutedContextExplorer &getMustBeExecutedContextExplorer() {
+    return Explorer;
+  }
+
   /// Return TargetLibraryInfo for function \p F.
   TargetLibraryInfo *getTargetLibraryInfoForFunction(const Function &F) {
     return AG.getAnalysis<TargetLibraryAnalysis>(F);
   }
 
   /// Return AliasAnalysis Result for function \p F.
   AAResults *getAAResultsForFunction(const Function &F) {
     return AG.getAnalysis<AAManager>(F);
private:
   FuncInstOpcodeMapTy FuncInstOpcodeMap;
 
   /// A map from functions to their instructions that may read or write memory.
   FuncRWInstsMapTy FuncRWInstsMap;
 
   /// The datalayout used in the module.
   const DataLayout &DL;
 
+  /// MustBeExecutedContextExplorer
+  MustBeExecutedContextExplorer Explorer;
+
   /// Getters for analysis.
   AnalysisGetter &AG;
 
   /// Cache result for scc size in the call graph
   Optional<DenseMap<const Function *, unsigned>> SccSizeOpt;
 
   /// Give the Attributor access to the members so
   /// Attributor::identifyDefaultAbstractAttributes(...) can initialize them.
bool checkForAllReadWriteInstructions(
       AbstractAttribute &QueryingAA);
 
   /// Return the data layout associated with the anchor scope.
   const DataLayout &getDataLayout() const { return InfoCache.DL; }
 
 private:
 
   /// The private version of getAAFor that allows to omit a querying abstract
   /// attribute. See also the public getAAFor method.
   template <typename AAType>
   const AAType &getOrCreateAAFor(const IRPosition &IRP,
                          const AbstractAttribute *QueryingAA = nullptr,
                          bool TrackDependence = false) {
     if (const AAType *AAPtr =
             lookupAAFor<AAType>(IRP, QueryingAA, TrackDependence))
       return *AAPtr;
 
: public IRAttribute<Attribute::Dereferenceable,
                          StateWrapper<DerefState, AbstractAttribute>> {
   AADereferenceable(const IRPosition &IRP) : IRAttribute(IRP) {}
 
   /// Return true if we assume that the underlying value is nonnull.
   bool isAssumedNonNull() const {
     return NonNullAA && NonNullAA->isAssumedNonNull();
   }
 
+  /// Return true if we know that the underlying value is nonnull.
+  bool isKnownNonNull() const {
+    return NonNullAA && NonNullAA->isKnownNonNull();
+  }
+
   /// Return true if we assume that underlying value is
   /// dereferenceable(_or_null) globally.
   bool isAssumedGlobal() const { return GlobalState.getAssumed(); }
 
   /// Return true if we know that underlying value is
   /// dereferenceable(_or_null) globally.
   bool isKnownGlobal() const { return GlobalState.getKnown(); }
 

llvm/lib/Transforms/IPO/Attributor.cpp

if (Attrs.hasAttribute(AttrIdx, Kind))
         return false;
     Attrs = Attrs.removeAttribute(Ctx, AttrIdx, Kind);
     Attrs = Attrs.addAttribute(Ctx, AttrIdx, Attr);
     return true;
   }
 
   llvm_unreachable("Expected enum or string attribute!");
 }
+static const Value *getPointerOperand(const Instruction *I) {
+  if (auto *LI = dyn_cast<LoadInst>(I))
+    if (!LI->isVolatile())
+      return LI->getPointerOperand();
+
+  if (auto *SI = dyn_cast<StoreInst>(I))
+    if (!SI->isVolatile())
+      return SI->getPointerOperand();
+
+  if (auto *CXI = dyn_cast<AtomicCmpXchgInst>(I))
+    if (!CXI->isVolatile())
+      return CXI->getPointerOperand();
+
+  if (auto *RMWI = dyn_cast<AtomicRMWInst>(I))
+    if (!RMWI->isVolatile())
+      return RMWI->getPointerOperand();
+
+  return nullptr;
+}
+static const Value *getBasePointerOfAccessPointerOperand(const Instruction *I,
+                                                         int64_t &BytesOffset,
+                                                         const DataLayout &DL) {
+  const Value *Ptr = getPointerOperand(I);
+  if (!Ptr)
+    return nullptr;
+
+  return GetPointerBaseWithConstantOffset(Ptr, BytesOffset, DL,
+                                          /*AllowNonInbounds*/ false);
+}
 
 ChangeStatus AbstractAttribute::update(Attributor &A) {
   ChangeStatus HasChanged = ChangeStatus::UNCHANGED;
   if (getState().isAtFixpoint())
     return HasChanged;
 
   LLVM_DEBUG(dbgs() << "[Attributor] Update: " << *this << "\n");
 
for (const IRPosition &EquivIRP : SubsumingPositionIterator(*this)) {
     // are done after the first iteration.
     if (IgnoreSubsumingPositions)
       break;
   }
   return false;
 }
 
 void IRPosition::getAttrs(ArrayRef<Attribute::AttrKind> AKs,
                           SmallVectorImpl<Attribute> &Attrs) const {
   for (const IRPosition &EquivIRP : SubsumingPositionIterator(*this))
     for (Attribute::AttrKind AK : AKs) {
       const Attribute &Attr = EquivIRP.getAttr(AK);
       if (Attr.getKindAsEnum() == AK)
         Attrs.push_back(Attr);
     }
 }
 
LLVM_DEBUG(dbgs() << "[Attributor] Clamp return value states for "
                     << static_cast<const AbstractAttribute &>(QueryingAA)
                     << " into " << S << "\n");
 
   assert((QueryingAA.getIRPosition().getPositionKind() ==
               IRPosition::IRP_RETURNED ||
           QueryingAA.getIRPosition().getPositionKind() ==
               IRPosition::IRP_CALL_SITE_RETURNED) &&
          "Can only clamp returned value states for a function returned or call "
          "site returned position!");
 
   // Use an optional state as there might not be any return values and we want
   // to join (IntegerState::operator&) the state of all there are.
   Optional<StateType> T;
 
   // Callback for each possibly returned value.
   auto CheckReturnValue = [&](Value &RV) -> bool {
     const IRPosition &RVPos = IRPosition::value(RV);
ChangeStatus updateImpl(Attributor &A) override {
     clampCallSiteArgumentStates<AAType, StateType>(A, *this, S);
     // TODO: If we know we visited all incoming values, thus no are assumed
     // dead, we can take the known information from the state T.
     return clampStateAndIndicateChange<StateType>(this->getState(), S);
   }
 };
 
 /// Helper class for generic replication: function returned -> cs returned.
-template <typename AAType, typename Base>
+template <typename AAType, typename Base,
+          typename StateType = typename AAType::StateType>
 struct AACallSiteReturnedFromReturned : public Base {
   AACallSiteReturnedFromReturned(const IRPosition &IRP) : Base(IRP) {}
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
     assert(this->getIRPosition().getPositionKind() ==
                IRPosition::IRP_CALL_SITE_RETURNED &&
            "Can only wrap function returned positions for call site returned "
            "positions!");
     auto &S = this->getState();
 
     const Function *AssociatedFunction =
         this->getIRPosition().getAssociatedFunction();
     if (!AssociatedFunction)
       return S.indicatePessimisticFixpoint();
 
     IRPosition FnPos = IRPosition::returned(*AssociatedFunction);
     const AAType &AA = A.getAAFor<AAType>(*this, FnPos);
     return clampStateAndIndicateChange(
         S, static_cast<const typename AAType::StateType &>(AA.getState()));
   }
 };
 
+/// Helper class for generic deduction using must-be-executed-context
+/// Base class is required to have `followUse` method.
+
+/// bool followUse(Attributor &A, const Use *U, const Instruction *I)
+/// \param U Underlying use.
+/// \param I The user of the \p U.
+/// `followUse` returns true if the value should be tracked transitively.
+
+template <typename AAType, typename Base,
+          typename StateType = typename AAType::StateType>
+struct AAFromMustBeExecutedContext : public Base {
+  AAFromMustBeExecutedContext(const IRPosition &IRP) : Base(IRP) {}
+
+  void initialize(Attributor &A) override {
+    Base::initialize(A);
+    IRPosition &IRP = this->getIRPosition();
+    Instruction *CtxI = IRP.getCtxI();
+
+    if (!CtxI)
+      return;
+
+    for (const Use &U : IRP.getAssociatedValue().uses())
+      Uses.insert(&U);
+  }
+
+  /// See AbstractAttribute::updateImpl(...).
+  ChangeStatus updateImpl(Attributor &A) override {
+    auto BeforeState = this->getState();
+    auto &S = this->getState();
+    Instruction *CtxI = this->getIRPosition().getCtxI();
+    if (!CtxI)
+      return ChangeStatus::UNCHANGED;
+
+    MustBeExecutedContextExplorer &Explorer =
+        A.getInfoCache().getMustBeExecutedContextExplorer();
+
+    SetVector<const Use *> NextUses;
+
+    for (const Use *U : Uses) {
+      if (const Instruction *UserI = dyn_cast<Instruction>(U->getUser())) {
+        auto EIt = Explorer.begin(CtxI), EEnd = Explorer.end(CtxI);
+        bool Found = EIt.count(UserI);
+        while (!Found && ++EIt != EEnd)
+          Found = EIt.getCurrentInst() == UserI;
+        if (Found && Base::followUse(A, U, UserI))
+          for (const Use &Us : UserI->uses())
+            NextUses.insert(&Us);
+      }
+    }
+    for (const Use *U : NextUses)
+      Uses.insert(U);
+
+    return BeforeState == S ? ChangeStatus::UNCHANGED : ChangeStatus::CHANGED;
+  }
+
+private:
+  /// Container for (transitive) uses of the associated value.
+  SetVector<const Use *> Uses;
+};
+
+template <typename AAType, typename Base,
+          typename StateType = typename AAType::StateType>
+using AAArgumentFromCallSiteArgumentsAndMustBeExecutedContext =
+    AAComposeTwoGenericDeduction<AAType, Base, StateType,
+                                 AAFromMustBeExecutedContext,
+                                 AAArgumentFromCallSiteArguments>;
+
+template <typename AAType, typename Base,
+          typename StateType = typename AAType::StateType>
+using AACallSiteReturnedFromReturnedAndMustBeExecutedContext =
+    AAComposeTwoGenericDeduction<AAType, Base, StateType,
+                                 AAFromMustBeExecutedContext,
+                                 AACallSiteReturnedFromReturned>;
+
 /// -----------------------NoUnwind Function Attribute--------------------------
 
 struct AANoUnwindImpl : AANoUnwind {
   AANoUnwindImpl(const IRPosition &IRP) : AANoUnwind(IRP) {}
 
   const std::string getAsStr() const override {
     return getAssumed() ? "nounwind" : "may-unwind";
   }
return clampStateAndIndicateChange(
         getState(), static_cast<const AANoFree::StateType &>(FnAA.getState()));
   }
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override { STATS_DECLTRACK_CS_ATTR(nofree); }
 };
 
 /// ------------------------ NonNull Argument Attribute ------------------------
+static int64_t getKnownNonNullAndDerefBytesForUse(
+    Attributor &A, AbstractAttribute &QueryingAA, Value &AssociatedValue,
+    const Use *U, const Instruction *I, bool &IsNonNull, bool &TrackUse) {
+  // TODO: Add GEP support
+  TrackUse = false;
+
+  const Function *F = I->getFunction();
+  bool NullPointerIsDefined = F ? F->nullPointerIsDefined() : true;
+  const DataLayout &DL = A.getInfoCache().getDL();
+  if (ImmutableCallSite ICS = ImmutableCallSite(I)) {
+    if (ICS.isBundleOperand(U))
+      return 0;
+
+    if (ICS.isCallee(U)) {
+      IsNonNull |= !NullPointerIsDefined;
+      return 0;
+    }
+
+    unsigned ArgNo = ICS.getArgumentNo(U);
+    IRPosition IRP = IRPosition::callsite_argument(ICS, ArgNo);
+    auto &DerefAA = A.getAAFor<AADereferenceable>(QueryingAA, IRP);
+    IsNonNull |= DerefAA.isKnownNonNull();
+    return DerefAA.getKnownDereferenceableBytes();
+  }
+
+  int64_t Offset;
+  if (const Value *Base = getBasePointerOfAccessPointerOperand(I, Offset, DL)) {
+    if (Base == &AssociatedValue) {
+      int64_t DerefBytes =
+          Offset +
+          (int64_t)DL.getTypeStoreSize(
+              getPointerOperand(I)->getType()->getPointerElementType());
+
+      IsNonNull |= !NullPointerIsDefined;
+      return DerefBytes;
+    }
+  }
+
+  return 0;
+}
 struct AANonNullImpl : AANonNull {
   AANonNullImpl(const IRPosition &IRP) : AANonNull(IRP) {}
 
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
     if (hasAttr({Attribute::NonNull, Attribute::Dereferenceable}))
       indicateOptimisticFixpoint();
     else
       AANonNull::initialize(A);
   }
 
+  /// See AAFromMustBeExecutedContext
+  bool followUse(Attributor &A, const Use *U, const Instruction *I) {
+    bool IsNonNull = false;
+    bool TrackUse = false;
+    getKnownNonNullAndDerefBytesForUse(A, *this, getAssociatedValue(), U, I,
+                                       IsNonNull, TrackUse);
+    takeKnownMaximum(IsNonNull);
+    return TrackUse;
+  }
+
   /// See AbstractAttribute::getAsStr().
   const std::string getAsStr() const override {
     return getAssumed() ? "nonnull" : "may-null";
   }
 };
 
 /// NonNull attribute for a floating value.
-struct AANonNullFloating : AANonNullImpl {
-  AANonNullFloating(const IRPosition &IRP) : AANonNullImpl(IRP) {}
+struct AANonNullFloating
+    : AAFromMustBeExecutedContext<AANonNull, AANonNullImpl> {
+  using Base = AAFromMustBeExecutedContext<AANonNull, AANonNullImpl>;
+  AANonNullFloating(const IRPosition &IRP) : Base(IRP) {}
 
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
-    AANonNullImpl::initialize(A);
+    Base::initialize(A);
 
     if (isAtFixpoint())
       return;
 
     const IRPosition &IRP = getIRPosition();
     const Value &V = IRP.getAssociatedValue();
     const DataLayout &DL = A.getDataLayout();
 
     // TODO: This context sensitive query should be removed once we can do
     // context sensitive queries in the genericValueTraversal below.
     if (isKnownNonZero(&V, DL, 0, /* TODO: AC */ nullptr, IRP.getCtxI(),
                        /* TODO: DT */ nullptr))
       indicateOptimisticFixpoint();
   }
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
+    ChangeStatus Change = Base::updateImpl(A);
+    if (isKnownNonNull())
+      return Change;
+
     const DataLayout &DL = A.getDataLayout();
 
     auto VisitValueCB = [&](Value &V, AAAlign::StateType &T,
                             bool Stripped) -> bool {
       const auto &AA = A.getAAFor<AANonNull>(*this, IRPosition::value(V));
       if (!Stripped && this == &AA) {
         if (!isKnownNonZero(&V, DL, 0, /* TODO: AC */ nullptr,
                             /* TODO: CtxI */ nullptr,
AANonNullReturned(const IRPosition &IRP)
       : AAReturnedFromReturnedValues<AANonNull, AANonNullImpl>(IRP) {}
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override { STATS_DECLTRACK_FNRET_ATTR(nonnull) }
 };
 
 /// NonNull attribute for function argument.
 struct AANonNullArgument final
-    : AAArgumentFromCallSiteArguments<AANonNull, AANonNullImpl> {
+    : AAArgumentFromCallSiteArgumentsAndMustBeExecutedContext<AANonNull,
+                                                              AANonNullImpl> {
   AANonNullArgument(const IRPosition &IRP)
-      : AAArgumentFromCallSiteArguments<AANonNull, AANonNullImpl>(IRP) {}
+      : AAArgumentFromCallSiteArgumentsAndMustBeExecutedContext<AANonNull,
+                                                                AANonNullImpl>(
+            IRP) {}
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override { STATS_DECLTRACK_ARG_ATTR(nonnull) }
 };
 
 struct AANonNullCallSiteArgument final : AANonNullFloating {
   AANonNullCallSiteArgument(const IRPosition &IRP) : AANonNullFloating(IRP) {}
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override { STATS_DECLTRACK_CSARG_ATTR(nonnull) }
 };
 
 /// NonNull attribute for a call site return position.
 struct AANonNullCallSiteReturned final
-    : AACallSiteReturnedFromReturned<AANonNull, AANonNullImpl> {
+    : AACallSiteReturnedFromReturnedAndMustBeExecutedContext<AANonNull,
+                                                             AANonNullImpl> {
   AANonNullCallSiteReturned(const IRPosition &IRP)
-      : AACallSiteReturnedFromReturned<AANonNull, AANonNullImpl>(IRP) {}
+      : AACallSiteReturnedFromReturnedAndMustBeExecutedContext<AANonNull,
+                                                               AANonNullImpl>(
+            IRP) {}
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override { STATS_DECLTRACK_CSRET_ATTR(nonnull) }
 };
 
 /// ------------------------ No-Recurse Attributes ----------------------------
 
 struct AANoRecurseImpl : public AANoRecurse {
   AANoRecurseImpl(const IRPosition &IRP) : AANoRecurse(IRP) {}
 
   /// See AbstractAttribute::getAsStr()
   const std::string getAsStr() const override {
     return getAssumed() ? "norecurse" : "may-recurse";
   }
 };
 
 struct AANoRecurseFunction final : AANoRecurseImpl {
   AANoRecurseFunction(const IRPosition &IRP) : AANoRecurseImpl(IRP) {}
 
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
     AANoRecurseImpl::initialize(A);
     if (const Function *F = getAnchorScope())
       if (A.getInfoCache().getSccSize(*F) == 1)
         return;
     indicatePessimisticFixpoint();
   }
struct AADereferenceableImpl : AADereferenceable {
   }
 
   /// See AbstractAttribute::getState()
   /// {
   StateType &getState() override { return *this; }
   const StateType &getState() const override { return *this; }
   /// }
 
+  /// See AAFromMustBeExecutedContext
+  bool followUse(Attributor &A, const Use *U, const Instruction *I) {
+    bool IsNonNull = false;
+    bool TrackUse = false;
+    int64_t DerefBytes = getKnownNonNullAndDerefBytesForUse(
+        A, *this, getAssociatedValue(), U, I, IsNonNull, TrackUse);
+    takeKnownDerefBytesMaximum(DerefBytes);
+    return TrackUse;
+  }
+
   void getDeducedAttributes(LLVMContext &Ctx,
                             SmallVectorImpl<Attribute> &Attrs) const override {
     // TODO: Add *_globally support
     if (isAssumedNonNull())
       Attrs.emplace_back(Attribute::getWithDereferenceableBytes(
           Ctx, getAssumedDereferenceableBytes()));
     else
       Attrs.emplace_back(Attribute::getWithDereferenceableOrNullBytes(
           Ctx, getAssumedDereferenceableBytes()));
   }
 
   /// See AbstractAttribute::getAsStr().
   const std::string getAsStr() const override {
     if (!getAssumedDereferenceableBytes())
       return "unknown-dereferenceable";
     return std::string("dereferenceable") +
            (isAssumedNonNull() ? "" : "_or_null") +
            (isAssumedGlobal() ? "_globally" : "") + "<" +
            std::to_string(getKnownDereferenceableBytes()) + "-" +
            std::to_string(getAssumedDereferenceableBytes()) + ">";
   }
 };
 
 /// Dereferenceable attribute for a floating value.
-struct AADereferenceableFloating : AADereferenceableImpl {
-  AADereferenceableFloating(const IRPosition &IRP)
-      : AADereferenceableImpl(IRP) {}
+struct AADereferenceableFloating
+    : AAFromMustBeExecutedContext<AADereferenceable, AADereferenceableImpl> {
+  using Base =
+      AAFromMustBeExecutedContext<AADereferenceable, AADereferenceableImpl>;
+  AADereferenceableFloating(const IRPosition &IRP) : Base(IRP) {}
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
+    ChangeStatus Change = Base::updateImpl(A);
+
     const DataLayout &DL = A.getDataLayout();
 
     auto VisitValueCB = [&](Value &V, DerefState &T, bool Stripped) -> bool {
       unsigned IdxWidth =
           DL.getIndexSizeInBits(V.getType()->getPointerAddressSpace());
       APInt Offset(IdxWidth, 0);
       const Value *Base =
           V.stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
auto VisitValueCB = [&](Value &V, DerefState &T, bool Stripped) -> bool {
       return T.isValidState();
     };
 
     DerefState T;
     if (!genericValueTraversal<AADereferenceable, DerefState>(
             A, getIRPosition(), *this, T, VisitValueCB))
       return indicatePessimisticFixpoint();
 
-    return clampStateAndIndicateChange(getState(), T);
+    return Change | clampStateAndIndicateChange(getState(), T);
   }
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override {
     STATS_DECLTRACK_FLOATING_ATTR(dereferenceable)
   }
 };
 
 /// Dereferenceable attribute for a return value.
 struct AADereferenceableReturned final
     : AAReturnedFromReturnedValues<AADereferenceable, AADereferenceableImpl,
                                    DerefState> {
   AADereferenceableReturned(const IRPosition &IRP)
       : AAReturnedFromReturnedValues<AADereferenceable, AADereferenceableImpl,
                                      DerefState>(IRP) {}
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override {
     STATS_DECLTRACK_FNRET_ATTR(dereferenceable)
   }
 };
 
 /// Dereferenceable attribute for an argument
 struct AADereferenceableArgument final
-    : AAArgumentFromCallSiteArguments<AADereferenceable, AADereferenceableImpl,
-                                      DerefState> {
-  AADereferenceableArgument(const IRPosition &IRP)
-      : AAArgumentFromCallSiteArguments<AADereferenceable,
-                                        AADereferenceableImpl, DerefState>(
-            IRP) {}
+    : AAArgumentFromCallSiteArgumentsAndMustBeExecutedContext<
+          AADereferenceable, AADereferenceableImpl, DerefState> {
+  using Base = AAArgumentFromCallSiteArgumentsAndMustBeExecutedContext<
+      AADereferenceable, AADereferenceableImpl, DerefState>;
+  AADereferenceableArgument(const IRPosition &IRP) : Base(IRP) {}
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override {
     STATS_DECLTRACK_ARG_ATTR(dereferenceable)
   }
 };
 
 /// Dereferenceable attribute for a call site argument.
 struct AADereferenceableCallSiteArgument final : AADereferenceableFloating {
   AADereferenceableCallSiteArgument(const IRPosition &IRP)
       : AADereferenceableFloating(IRP) {}
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override {
     STATS_DECLTRACK_CSARG_ATTR(dereferenceable)
   }
 };
 
 /// Dereferenceable attribute deduction for a call site return value.
-struct AADereferenceableCallSiteReturned final : AADereferenceableImpl {
-  AADereferenceableCallSiteReturned(const IRPosition &IRP)
-      : AADereferenceableImpl(IRP) {}
+struct AADereferenceableCallSiteReturned final
+    : AACallSiteReturnedFromReturnedAndMustBeExecutedContext<
+          AADereferenceable, AADereferenceableImpl> {
+  using Base = AACallSiteReturnedFromReturnedAndMustBeExecutedContext<
+      AADereferenceable, AADereferenceableImpl>;
+  AADereferenceableCallSiteReturned(const IRPosition &IRP) : Base(IRP) {}
 
   /// See AbstractAttribute::initialize(...).
   void initialize(Attributor &A) override {
-    AADereferenceableImpl::initialize(A);
+    Base::initialize(A);
     Function *F = getAssociatedFunction();
     if (!F)
       indicatePessimisticFixpoint();
   }
 
   /// See AbstractAttribute::updateImpl(...).
   ChangeStatus updateImpl(Attributor &A) override {
     // TODO: Once we have call site specific value information we can provide
     //       call site specific liveness information and then it makes
     //       sense to specialize attributes for call sites arguments instead of
     //       redirecting requests to the callee argument.
+
+    ChangeStatus Change = Base::updateImpl(A);
     Function *F = getAssociatedFunction();
     const IRPosition &FnPos = IRPosition::returned(*F);
     auto &FnAA = A.getAAFor<AADereferenceable>(*this, FnPos);
-    return clampStateAndIndicateChange(
+    return Change |
+           clampStateAndIndicateChange(
                getState(), static_cast<const DerefState &>(FnAA.getState()));
   }
 
   /// See AbstractAttribute::trackStatistics()
   void trackStatistics() const override {
     STATS_DECLTRACK_CS_ATTR(dereferenceable);
   }
 };
 
bool captured(const Use *U) override {
     // Deal with ptr2int by following uses.
     if (isa<PtrToIntInst>(UInst)) {
       LLVM_DEBUG(dbgs() << " - ptr2int assume the worst!\n");
       return valueMayBeCaptured(UInst);
     }
 
     // Explicitly catch return instructions.
     if (isa<ReturnInst>(UInst))
       return isCapturedIn(/* Memory */ false, /* Integer */ false,
                           /* Return */ true);
 
     // For now we only use special logic for call sites. However, the tracker
     // itself knows about a lot of other non-capturing cases already.
     CallSite CS(UInst);
     if (!CS || !CS.isArgOperand(U))
       return isCapturedIn(/* Memory */ true, /* Integer */ true,
                           /* Return */ true);
 
     unsigned ArgNo = CS.getArgumentNo(U);
     const IRPosition &CSArgPos = IRPosition::callsite_argument(CS, ArgNo);
     // If we have a abstract no-capture attribute for the argument we can use

llvm/test/Transforms/FunctionAttrs/align.ll

 define void @test9_traversal(i1 %c, i32* align 4 %B, i32* align 8 %C) {
   %sel = select i1 %c, i32* %B, i32* %C
   call void @test9_helper(i32* %sel)
   ret void
 }
 
 ; FIXME: This will work with an upcoming patch (D66618 or similar)
 ;             define align 32 i32* @test10a(i32* align 32 "no-capture-maybe-returned" %p)
-; ATTRIBUTOR: define i32* @test10a(i32* align 32 "no-capture-maybe-returned" %p)
+; ATTRIBUTOR: define i32* @test10a(i32* nonnull align 32 dereferenceable(4) "no-capture-maybe-returned" %p)
 define i32* @test10a(i32* align 32 %p) {
 ; ATTRIBUTOR: %l = load i32, i32* %p, align 32
   %l = load i32, i32* %p
   %c = icmp eq i32 %l, 0
   br i1 %c, label %t, label %f
 t:
   %r = call i32* @test10a(i32* %p)
 ; FIXME: This will work with an upcoming patch (D66618 or similar)
; ATTRIBUTOR: store i32 -1, i32* %g1
   br label %e
 e:
   %phi = phi i32* [%g0, %t], [%g1, %f]
   ret i32* %phi
 }
 
 ; FIXME: This will work with an upcoming patch (D66618 or similar)
 ;             define align 32 i32* @test10b(i32* align 32 "no-capture-maybe-returned" %p)
-; ATTRIBUTOR: define i32* @test10b(i32* align 32 "no-capture-maybe-returned" %p)
+; ATTRIBUTOR: define i32* @test10b(i32* nonnull align 32 dereferenceable(4) "no-capture-maybe-returned" %p)
 define i32* @test10b(i32* align 32 %p) {
 ; ATTRIBUTOR: %l = load i32, i32* %p, align 32
   %l = load i32, i32* %p
   %c = icmp eq i32 %l, 0
   br i1 %c, label %t, label %f
 t:
   %r = call i32* @test10b(i32* %p)
 ; FIXME: This will work with an upcoming patch (D66618 or similar)

llvm/test/Transforms/FunctionAttrs/arg_nocapture.ll

 ; TEST "captured" only through return
 ;
 ; long *not_captured_but_returned_0(long *a) {
 ;   *a1 = 0;
 ;   return a;
 ; }
 ;
 ; There should *not* be a no-capture attribute on %a
-; CHECK: define i64* @not_captured_but_returned_0(i64* returned writeonly "no-capture-maybe-returned" %a)
+; CHECK: define nonnull dereferenceable(8) i64* @not_captured_but_returned_0(i64* nonnull returned writeonly dereferenceable(8) "no-capture-maybe-returned" %a)
+
 define i64* @not_captured_but_returned_0(i64* %a) #0 {
 entry:
   store i64 0, i64* %a, align 8
   ret i64* %a
 }
 
 ; TEST "captured" only through return
 ;

 ;     return b;
 ;   return unknown();
 ; }
 ;
 ; Verify we do *not* assume b is returned or not captured.
 ;
 ; CHECK:     define i32* @ret_arg_or_unknown(i32* readnone %b)
 ; CHECK:     define i32* @ret_arg_or_unknown_through_phi(i32* readnone %b)
+
 declare i32* @unknown()
 
 define i32* @ret_arg_or_unknown(i32* %b) #0 {
 entry:
   %cmp = icmp eq i32* %b, null
   br i1 %cmp, label %ret_arg, label %ret_unknown
 
 ret_arg:

llvm/test/Transforms/FunctionAttrs/arg_returned.ll

 ; TEST a no-return singleton SCC
 ;
 ; int* rt0(int *a) {
 ;   return *a ? a : rt0(a);
 ; }
 ;
 ; FNATTR:  define i32* @rt0(i32* readonly %a)
 ; BOTH: Function Attrs: nofree noinline noreturn nosync nounwind readonly uwtable
-; BOTH-NEXT:    define noalias nonnull align 536870912 dereferenceable(4294967295) i32* @rt0(i32* nocapture readonly %a)
+; BOTH-NEXT:    define noalias nonnull align 536870912 dereferenceable(4294967295) i32* @rt0(i32* nocapture nonnull readonly dereferenceable(4) %a)
 define i32* @rt0(i32* %a) #0 {
 entry:
   %v = load i32, i32* %a, align 4
   %tobool = icmp ne i32 %v, 0
   %call = call i32* @rt0(i32* %a)
   %sel = select i1 %tobool, i32* %a, i32* %call
   ret i32* %sel
 }
 
 ; TEST a no-return singleton SCC
 ;
 ; int* rt1(int *a) {
 ;   return *a ? undef : rt1(a);
 ; }
 ;
 ; FNATTR:  define noalias i32* @rt1(i32* nocapture readonly %a)
 ; BOTH: Function Attrs: nofree noinline noreturn nosync nounwind readonly uwtable
-; BOTH-NEXT:    define noalias nonnull align 536870912 dereferenceable(4294967295) i32* @rt1(i32* nocapture readonly %a)
+; BOTH-NEXT:    define noalias nonnull align 536870912 dereferenceable(4294967295) i32* @rt1(i32* nocapture nonnull readonly dereferenceable(4) %a)
 define i32* @rt1(i32* %a) #0 {
 entry:
   %v = load i32, i32* %a, align 4
   %tobool = icmp ne i32 %v, 0
   %call = call i32* @rt1(i32* %a)
   %sel = select i1 %tobool, i32* undef, i32* %call
   ret i32* %sel
 }

llvm/test/Transforms/FunctionAttrs/callbacks.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=1 < %s | FileCheck %s
+; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 < %s | FileCheck %s
 ; ModuleID = 'callback_simple.c'
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 
 ; Test 0
 ;
 ; Make sure we propagate information from the caller to the callback callee but
 ; only for arguments that are mapped through the callback metadata. Here, the
 ; first two arguments of the call and the callback callee do not correspond to
 ; each other but argument 3-5 of the transitive call site in the caller match
 ; arguments 2-4 of the callback callee. Here we should see information and value
 ; transfer in both directions.
 ; FIXME: The callee -> call site direction is not working yet.
 
 define void @t0_caller(i32* %a) {
-; CHECK:       @t0_caller(i32* [[A:%.*]])
+; CHECK-LABEL: @t0_caller(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[B:%.*]] = alloca i32, align 32
 ; CHECK-NEXT:    [[C:%.*]] = alloca i32*, align 64
 ; CHECK-NEXT:    [[PTR:%.*]] = alloca i32, align 128
 ; CHECK-NEXT:    [[TMP0:%.*]] = bitcast i32* [[B]] to i8*
 ; CHECK-NEXT:    store i32 42, i32* [[B]], align 32
 ; CHECK-NEXT:    store i32* [[B]], i32** [[C]], align 64
 ; CHECK-NEXT:    call void (i32*, i32*, void (i32*, i32*, ...)*, ...) @t0_callback_broker(i32* null, i32* nonnull align 128 dereferenceable(4) [[PTR]], void (i32*, i32*, ...)* nonnull bitcast (void (i32*, i32*, i32*, i64, i32**)* @t0_callback_callee to void (i32*, i32*, ...)*), i32* [[A:%.*]], i64 99, i32** nonnull align 64 dereferenceable(8) [[C]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %b = alloca i32, align 32
   %c = alloca i32*, align 64
   %ptr = alloca i32, align 128
   %0 = bitcast i32* %b to i8*
   store i32 42, i32* %b, align 4
   store i32* %b, i32** %c, align 8
   call void (i32*, i32*, void (i32*, i32*, ...)*, ...) @t0_callback_broker(i32* null, i32* %ptr, void (i32*, i32*, ...)* bitcast (void (i32*, i32*, i32*, i64, i32**)* @t0_callback_callee to void (i32*, i32*, ...)*), i32* %a, i64 99, i32** %c)
   ret void
 }
 
 ; Note that the first two arguments are provided by the callback_broker according to the callback in !1 below!
 ; The others are annotated with alignment information, amongst others, or even replaced by the constants passed to the call.
 define internal void @t0_callback_callee(i32* %is_not_null, i32* %ptr, i32* %a, i64 %b, i32** %c) {
-; CHECK:       @t0_callback_callee(i32* nocapture writeonly [[IS_NOT_NULL:%.*]], i32* nocapture readonly [[PTR:%.*]], i32* [[A:%.*]], i64 [[B:%.*]], i32** nocapture nonnull readonly align 64 dereferenceable(8) [[C:%.*]])
+; CHECK-LABEL: @t0_callback_callee(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[PTR_VAL:%.*]] = load i32, i32* [[PTR:%.*]], align 8
 ; CHECK-NEXT:    store i32 [[PTR_VAL]], i32* [[IS_NOT_NULL:%.*]]
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i32*, i32** [[C:%.*]], align 64
 ; CHECK-NEXT:    tail call void @t0_check(i32* align 256 [[A:%.*]], i64 99, i32* [[TMP0]])
 ; CHECK-NEXT:    ret void
 ;
 entry:

llvm/test/Transforms/FunctionAttrs/dereferenceable.ll

-; RUN: opt -attributor -attributor-manifest-internal --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=1 -S < %s | FileCheck %s --check-prefixes=ATTRIBUTOR
+; RUN: opt -attributor -attributor-manifest-internal --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 -S < %s | FileCheck %s --check-prefixes=ATTRIBUTOR
 
 
 declare void @deref_phi_user(i32* %a);
 
 ; TEST 1
 ; take mininimum of return values
 ;
 define i32* @test1(i32* dereferenceable(4) %0, double* dereferenceable(8) %1, i1 zeroext %2) local_unnamed_addr {

 for.inc:                                          ; preds = %for.body
   %incdec.ptr = getelementptr inbounds i32, i32* %a.addr.0, i64 1
   %inc = add nuw nsw i32 %i.0, 1
   br label %for.cond
 
 for.end:                                          ; preds = %for.cond.cleanup
   ret void
 }
+
+; TEST 7
+; share known infomation in must-be-executed-context
+declare i32* @unkown_ptr() willreturn nounwind
+declare i32 @unkown_f(i32*) willreturn nounwind
+define i32* @f7_0(i32* %ptr) {
+; ATTRIBUTOR: define nonnull dereferenceable(8) i32* @f7_0(i32* nonnull returned dereferenceable(8) %ptr)
+  %T = tail call i32 @unkown_f(i32* dereferenceable(8) %ptr)
+  ret i32* %ptr
+} 
+
+; ATTRIBUTOR: define void @f7_1(i32* nonnull dereferenceable(4) %ptr, i1 %c) 
+define void @f7_1(i32* %ptr, i1 %c) {
+
+; ATTRIBUTOR:   %A = tail call i32 @unkown_f(i32* nonnull dereferenceable(4) %ptr) 
+  %A = tail call i32 @unkown_f(i32* %ptr)
+
+  %ptr.0 = load i32, i32* %ptr
+  ; deref 4 hold
+
+; FIXME: this should be %B = tail call i32 @unkown_f(i32* nonnull dereferenceable(4) %ptr) 
+; ATTRIBUTOR:   %B = tail call i32 @unkown_f(i32* nonnull dereferenceable(4) %ptr) 
+  %B = tail call i32 @unkown_f(i32* dereferenceable(1) %ptr)
+
+  br i1%c, label %if.true, label %if.false
+if.true:
+; ATTRIBUTOR:   %C = tail call i32 @unkown_f(i32* nonnull dereferenceable(8) %ptr) 
+  %C = tail call i32 @unkown_f(i32* %ptr)
+
+; ATTRIBUTOR:   %D = tail call i32 @unkown_f(i32* nonnull dereferenceable(8) %ptr) 
+  %D = tail call i32 @unkown_f(i32* dereferenceable(8) %ptr)
+
+; FIXME: This should be tail call i32 @unkown_f(i32* nonnull dereferenceable(8) %ptr) 
+;        Making must-be-executed-context backward exploration will fix this.
+; ATTRIBUTOR:   %E = tail call i32 @unkown_f(i32* nonnull dereferenceable(4) %ptr) 
+  %E = tail call i32 @unkown_f(i32* %ptr)
+
+  ret void
+
+if.false:
+  ret void
+}
+
+; ATTRIBUTOR: define void @f7_2(i1 %c) 
+define void @f7_2(i1 %c) {
+
+  %ptr =  tail call i32* @unkown_ptr()
+
+; ATTRIBUTOR:   %A = tail call i32 @unkown_f(i32* nonnull dereferenceable(4) %ptr) 
+  %A = tail call i32 @unkown_f(i32* %ptr)
+
+  %arg_a.0 = load i32, i32* %ptr
+  ; deref 4 hold
+
+; ATTRIBUTOR:   %B = tail call i32 @unkown_f(i32* nonnull dereferenceable(4) %ptr)
+  %B = tail call i32 @unkown_f(i32* dereferenceable(1) %ptr)
+
+  br i1%c, label %if.true, label %if.false
+if.true:
+
+; ATTRIBUTOR:   %C = tail call i32 @unkown_f(i32* nonnull dereferenceable(8) %ptr) 
+  %C = tail call i32 @unkown_f(i32* %ptr)
+
+; ATTRIBUTOR:   %D = tail call i32 @unkown_f(i32* nonnull dereferenceable(8) %ptr) 
+  %D = tail call i32 @unkown_f(i32* dereferenceable(8) %ptr)
+
+  %E = tail call i32 @unkown_f(i32* %ptr)
+; FIXME: This should be @unkown_f(i32* nonnull dereferenceable(8) %ptr) 
+;        Making must-be-executed-context backward exploration will fix this.
+; ATTRIBUTOR:   %E = tail call i32 @unkown_f(i32* nonnull dereferenceable(4) %ptr)
+
+  ret void
+
+if.false:
+  ret void
+}
+
+define i32* @f7_3() {
+; ATTRIBUTOR: define nonnull dereferenceable(4) i32* @f7_3()
+  %ptr = tail call i32* @unkown_ptr()
+  store i32 10, i32* %ptr, align 16
+  ret i32* %ptr
+}
+
+define i32* @test_for_minus_index(i32* %p) {
+; FIXME: This should be define nonnull dereferenceable(8) i32* @test_for_minus_index(i32* nonnull %p)
+; ATTRIBUTOR: define nonnull dereferenceable(8) i32* @test_for_minus_index(i32* writeonly "no-capture-maybe-returned" %p)
+  %q = getelementptr inbounds i32, i32* %p, i32 -2
+  store i32 1, i32* %q
+  ret i32* %q
+}

llvm/test/Transforms/FunctionAttrs/internal-noalias.ll

 ; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=5 < %s | FileCheck %s
 
 define dso_local i32 @visible(i32* noalias %A, i32* noalias %B) #0 {
 entry:
   %call1 = call i32 @noalias_args(i32* %A, i32* %B)
   %call2 = call i32 @noalias_args_argmem(i32* %A, i32* %B)
   %add = add nsw i32 %call1, %call2
   ret i32 %add
 }
 
-; CHECK: define private i32 @noalias_args(i32* nocapture readonly %A, i32* noalias nocapture readonly %B)
+; CHECK: define private i32 @noalias_args(i32* nocapture nonnull readonly dereferenceable(4) %A, i32* noalias nocapture nonnull readonly dereferenceable(4) %B)
 
 define private i32 @noalias_args(i32* %A, i32* %B) #0 {
 entry:
   %0 = load i32, i32* %A, align 4
   %1 = load i32, i32* %B, align 4
   %add = add nsw i32 %0, %1
   %call = call i32 @noalias_args_argmem(i32* %A, i32* %B)
   %add2 = add nsw i32 %add, %call
   ret i32 %add2
 }
 
 
 ; FIXME: Should be something like this.
 ; define internal i32 @noalias_args_argmem(i32* noalias nocapture readonly %A, i32* noalias nocapture readonly %B)
-; CHECK: define internal i32 @noalias_args_argmem(i32* nocapture readonly %A, i32* nocapture readonly %B)
+; CHECK: define internal i32 @noalias_args_argmem(i32* nocapture nonnull readonly dereferenceable(4) %A, i32* nocapture nonnull readonly dereferenceable(4) %B)
+
 ;
 define internal i32 @noalias_args_argmem(i32* %A, i32* %B) #1 {
 entry:
   %0 = load i32, i32* %A, align 4
   %1 = load i32, i32* %B, align 4
   %add = add nsw i32 %0, %1
   ret i32 %add
 }

llvm/test/Transforms/FunctionAttrs/liveness.ll

 
 ; CHECK: Function Attrs: nofree norecurse nounwind uwtable willreturn
 define i32 @volatile_load(i32*) norecurse nounwind uwtable {
   %2 = load volatile i32, i32* %0, align 4
   ret i32 %2
 }
 
 ; CHECK: Function Attrs: nofree norecurse nosync nounwind readonly uwtable willreturn
-; CHECK-NEXT: define internal i32 @internal_load(i32* nocapture nonnull readonly %0)
+; CHECK-NEXT: define internal i32 @internal_load(i32* nocapture nonnull readonly dereferenceable(4) %0)
 define internal i32 @internal_load(i32*) norecurse nounwind uwtable {
   %2 = load i32, i32* %0, align 4
   ret i32 %2
 }
 ; TEST 1: Only first block is live.
 
 ; CHECK: Function Attrs: nofree noreturn nosync nounwind
 ; CHECK-NEXT: define i32 @first_block_no_return(i32 %a, i32* nocapture nonnull readonly %ptr1, i32* nocapture readnone %ptr2)

llvm/test/Transforms/FunctionAttrs/noalias_returned.ll

-; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=1 < %s | FileCheck %s
+; RUN: opt -S -passes=attributor -aa-pipeline='basic-aa' -attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=2 < %s | FileCheck %s
 
 ; TEST 1 - negative.
 
 ; void *G;
 ; void *foo(){
 ;   void *V = malloc(4);
 ;   G = V;
 ;   return V;

llvm/test/Transforms/FunctionAttrs/nocapture.ll

 }
 
 ; EITHER: define void @nc2(i32* nocapture %p, i32* %q)
 define void @nc2(i32* %p, i32* %q) {
   %1 = call i32 @nc1(i32* %q, i32* %p, i1 0)    ; <i32> [#uses=0]
   ret void
 }
 
-; EITHER: define void @nc3(void ()* nocapture %p)
+
+; FNATTR: define void @nc3(void ()* nocapture %p)
+; ATTRIBUTOR: define void @nc3(void ()* nocapture nonnull %p)
 define void @nc3(void ()* %p) {
   call void %p()
   ret void
 }
 
 declare void @external(i8*) readonly nounwind
 ; EITHER: define void @nc4(i8* nocapture readonly %p)
 define void @nc4(i8* %p) {
   call void @external(i8* %p)
   ret void
 }
 
-; EITHER: define void @nc5(void (i8*)* nocapture %f, i8* nocapture %p)
+; FNATTR: define void @nc5(void (i8*)* nocapture %f, i8* nocapture %p)
+; ATTRIBUTOR: define void @nc5(void (i8*)* nocapture nonnull %f, i8* nocapture %p)
 define void @nc5(void (i8*)* %f, i8* %p) {
   call void %f(i8* %p) readonly nounwind
   call void %f(i8* nocapture %p)
   ret void
 }
 
 ; FNATTR:     define void @test1_1(i8* nocapture readnone %x1_1, i8* %y1_1, i1 %c)
 ; ATTRIBUTOR: define void @test1_1(i8* nocapture readnone %x1_1, i8* nocapture readnone %y1_1, i1 %c)

 
 ; EITHER: define void @test6_2(i8* %x6_2, i8* nocapture %y6_2, i8* %z6_2)
 define void @test6_2(i8* %x6_2, i8* %y6_2, i8* %z6_2) {
   call void (i8*, i8*, ...) @test6_1(i8* %x6_2, i8* %y6_2, i8* %z6_2)
   store i32* null, i32** @g
   ret void
 }
 
-; EITHER: define void @test_cmpxchg(i32* nocapture %p)
+; FNATTR: define void @test_cmpxchg(i32* nocapture %p)
+; ATTRIBUTOR: define void @test_cmpxchg(i32* nocapture nonnull dereferenceable(4) %p)
 define void @test_cmpxchg(i32* %p) {
   cmpxchg i32* %p, i32 0, i32 1 acquire monotonic
   ret void
 }
 
-; EITHER: define void @test_cmpxchg_ptr(i32** nocapture %p, i32* %q)
+; FNATTR: define void @test_cmpxchg_ptr(i32** nocapture %p, i32* %q)
+; ATTRIBUTOR: define void @test_cmpxchg_ptr(i32** nocapture nonnull dereferenceable(8) %p, i32* %q)
 define void @test_cmpxchg_ptr(i32** %p, i32* %q) {
   cmpxchg i32** %p, i32* null, i32* %q acquire monotonic
   ret void
 }
 
-; EITHER: define void @test_atomicrmw(i32* nocapture %p)
+; FNATTR: define void @test_atomicrmw(i32* nocapture %p)
+; ATTRIBUTOR: define void @test_atomicrmw(i32* nocapture nonnull dereferenceable(4) %p)
 define void @test_atomicrmw(i32* %p) {
   atomicrmw add i32* %p, i32 1 seq_cst
   ret void
 }
 
 ; EITHER: define void @test_volatile(i32* %x)
 define void @test_volatile(i32* %x) {
 entry:

llvm/test/Transforms/FunctionAttrs/nonnull.ll

 ; TEST 15
 define void @f15(i8* %arg) {
 ; ATTRIBUTOR:   tail call void @use1(i8* nonnull dereferenceable(4) %arg)
 
   tail call void @use1(i8* dereferenceable(4) %arg)
   ret void
 }
 
+declare void @fun0() #1
+declare void @fun1(i8*) #1
+declare void @fun2(i8*, i8*) #1
+declare void @fun3(i8*, i8*, i8*) #1
+; TEST 16 simple path test
+; if(..)
+;   fun2(nonnull %a, nonnull %b)
+; else
+;   fun2(nonnull %a, %b)
+; We can say that %a is nonnull but %b is not.
+define void @f16(i8* %a, i8 * %b, i8 %c) {
+; FIXME: missing nonnull on %a
+; ATTRIBUTOR: define void @f16(i8* %a, i8* %b, i8 %c)
+  %cmp = icmp eq i8 %c, 0
+  br i1 %cmp, label %if.then, label %if.else
+if.then:
+  tail call void @fun2(i8* nonnull %a, i8* nonnull %b)
+  ret void
+if.else:
+  tail call void @fun2(i8* nonnull %a, i8* %b)
+  ret void
+}
+; TEST 17 explore child BB test
+; if(..)
+;    ... (willreturn & nounwind)
+; else
+;    ... (willreturn & nounwind)
+; fun1(nonnull %a)
+; We can say that %a is nonnull
+define void @f17(i8* %a, i8 %c) {
+; FIXME: missing nonnull on %a
+; ATTRIBUTOR: define void @f17(i8* %a, i8 %c)
+  %cmp = icmp eq i8 %c, 0
+  br i1 %cmp, label %if.then, label %if.else
+if.then:
+  tail call void @fun0()
+  br label %cont
+if.else:
+  tail call void @fun0()
+  br label %cont
+cont:
+  tail call void @fun1(i8* nonnull %a)
+  ret void
+}
+; TEST 18 More complex test
+; if(..)
+;    ... (willreturn & nounwind)
+; else
+;    ... (willreturn & nounwind)
+; if(..)
+;    ... (willreturn & nounwind)
+; else
+;    ... (willreturn & nounwind)
+; fun1(nonnull %a)
+
+define void @f18(i8* %a, i8* %b, i8 %c) {
+; FIXME: missing nonnull on %a
+; ATTRIBUTOR: define void @f18(i8* %a, i8* %b, i8 %c)
+  %cmp1 = icmp eq i8 %c, 0
+  br i1 %cmp1, label %if.then, label %if.else
+if.then:
+  tail call void @fun0()
+  br label %cont
+if.else:
+  tail call void @fun0()
+  br label %cont
+cont:
+  %cmp2 = icmp eq i8 %c, 1
+  br i1 %cmp2, label %cont.then, label %cont.else
+cont.then:
+  tail call void @fun1(i8* nonnull %b)
+  br label %cont2
+cont.else:
+  tail call void @fun0()
+  br label %cont2
+cont2:
+  tail call void @fun1(i8* nonnull %a)
+  ret void
+}
+
+; TEST 19: Loop
+
+define void @f19(i8* %a, i8* %b, i8 %c) {
+; FIXME: missing nonnull on %b
+; ATTRIBUTOR: define void @f19(i8* %a, i8* %b, i8 %c)
+  br label %loop.header
+loop.header:
+  %cmp2 = icmp eq i8 %c, 0
+  br i1 %cmp2, label %loop.body, label %loop.exit
+loop.body:
+  tail call void @fun1(i8* nonnull %b)
+  tail call void @fun1(i8* nonnull %a)
+  br label %loop.header
+loop.exit:
+  tail call void @fun1(i8* nonnull %b)
+  ret void
+}
+
 ; 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);

 
 ; Extend non-null to parent for all arguments.
 
 define void @parent2(i8* %a, i8* %b, i8* %c) {
 ; FNATTR-LABEL: @parent2(i8* nonnull %a, i8* nonnull %b, i8* nonnull %c)
 ; FNATTR-NEXT:    call void @use3nonnull(i8* %b, i8* %c, i8* %a)
 ; FNATTR-NEXT:    call void @use3(i8* %c, i8* %a, i8* %b)
 
-; FIXME: missing "nonnull", it should be
-; @parent2(i8* nonnull %a, i8* nonnull %b, i8* nonnull %c)
-;     call void @use3nonnull(i8* nonnull %b, i8* nonnull %c, i8* nonnull %a)
-;     call void @use3(i8* nonnull %c, i8* nonnull %a, i8* nonnull %b)
-
-; ATTRIBUTOR-LABEL: @parent2(i8* %a, i8* %b, i8* %c)
+; ATTRIBUTOR-LABEL: @parent2(i8* nonnull %a, i8* nonnull %b, i8* nonnull %c)
 ; ATTRIBUTOR-NEXT:    call void @use3nonnull(i8* nonnull %b, i8* nonnull %c, i8* nonnull %a)
-; ATTRIBUTOR-NEXT:    call void @use3(i8* %c, i8* %a, i8* %b)
+; ATTRIBUTOR-NEXT:    call void @use3(i8* nonnull %c, i8* nonnull %a, i8* nonnull %b)
 
 ; BOTH-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) {
 ; FNATTR-LABEL: @parent3(i8* nonnull %a, i8* %b, i8* %c)
 ; FNATTR-NEXT:    call void @use1nonnull(i8* %a)
 ; FNATTR-NEXT:    call void @use3(i8* %c, i8* %b, i8* %a)
 
-; FIXME: missing "nonnull", it should be,
-; @parent3(i8* nonnull %a, i8* %b, i8* %c)
-;    call void @use1nonnull(i8* nonnull %a)
-;    call void @use3(i8* %c, i8* %b, i8* nonnull %a)
-; ATTRIBUTOR-LABEL: @parent3(i8* %a, i8* %b, i8* %c)
+; ATTRIBUTOR-LABEL: @parent3(i8* nonnull %a, i8* %b, i8* %c)
 ; ATTRIBUTOR-NEXT:    call void @use1nonnull(i8* nonnull %a)
-; ATTRIBUTOR-NEXT:    call void @use3(i8* %c, i8* %b, i8* %a)
+; ATTRIBUTOR-NEXT:    call void @use3(i8* %c, i8* %b, i8* nonnull %a)
 
 ; BOTH-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)
 
-; FIXME : missing "nonnull", it should be
-; @parent4(i8* %a, i8* nonnull %b, i8* nonnull %c)
-;   call void @use2nonnull(i8* nonnull %c, i8* nonull %b)
-;   call void @use2(i8* %a, i8* nonnull %c)
-;   call void @use1(i8* nonnull %b)
-
-; ATTRIBUTOR-LABEL: @parent4(i8* %a, i8* %b, i8* %c)
+; ATTRIBUTOR-LABEL: @parent4(i8* %a, i8* nonnull %b, i8* nonnull %c)
 ; ATTRIBUTOR-NEXT:    call void @use2nonnull(i8* nonnull %c, i8* nonnull %b)
-; ATTRIBUTOR-NEXT:    call void @use2(i8* %a, i8* %c)
-; ATTRIBUTOR-NEXT:    call void @use1(i8* %b)
+; ATTRIBUTOR-NEXT:    call void @use2(i8* %a, i8* nonnull %c)
+; ATTRIBUTOR-NEXT:    call void @use1(i8* nonnull %b)
 
 ; BOTH: ret void
 
   call void @use2nonnull(i8* %c, i8* %b)
   call void @use2(i8* %a, i8* %c)
   call void @use1(i8* %b)
   ret void
 }
f:
   ret void
 }
 
 ; The callsite must execute in order for the attribute to transfer to the parent.
 ; The volatile load can't trap, so we can guarantee that we'll get to the call.
 
 define i8 @parent6(i8* %a, i8* %b) {
 ; FNATTR-LABEL: @parent6(i8* nonnull %a, i8* %b)
-; FIXME: missing "nonnull"
-; ATTRIBUTOR-LABEL: @parent6(i8* %a, i8* %b)
+; ATTRIBUTOR-LABEL: @parent6(i8* nonnull %a, i8* %b)
 ; BOTH-NEXT:    [[C:%.*]] = load volatile i8, i8* %b
 ; FNATTR-NEXT:    call void @use1nonnull(i8* %a)
 ; ATTRIBUTOR-NEXT:    call void @use1nonnull(i8* nonnull %a)
 ; BOTH-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) {
 ; FNATTR-LABEL: @parent7(i8* nonnull %a)
 ; FNATTR-NEXT:    [[RET:%.*]] = call i8 @use1safecall(i8* %a)
 ; FNATTR-NEXT:    call void @use1nonnull(i8* %a)
 
-; FIXME : missing "nonnull", it should be
-; @parent7(i8* nonnull %a)
-;   [[RET:%.*]] = call i8 @use1safecall(i8* nonnull %a)
-;   call void @use1nonnull(i8* nonnull %a)
-;   ret i8 [[RET]]
 
-; ATTRIBUTOR-LABEL: @parent7(i8* %a)
-; ATTRIBUTOR-NEXT:    [[RET:%.*]] = call i8 @use1safecall(i8* %a)
+; ATTRIBUTOR-LABEL: @parent7(i8* nonnull %a)
+; ATTRIBUTOR-NEXT:    [[RET:%.*]] = call i8 @use1safecall(i8* nonnull %a)
 ; ATTRIBUTOR-NEXT:    call void @use1nonnull(i8* nonnull %a)
 
 ; BOTH-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*){
-; FNATTR-LABEL: @parent8(i8* nonnull %a, i8* nocapture readnone %bogus1, i8* nonnull %b)
-; FIXME : missing "nonnull", it should be @parent8(i8* nonnull %a, i8* %bogus1, i8* nonnull %b)
-; ATTRIBUTOR-LABEL: @parent8(i8* %a, i8* nocapture readnone %bogus1, i8* %b)
+; BOTH-LABEL: @parent8(i8* nonnull %a, i8* nocapture readnone %bogus1, i8* nonnull %b) 
 ; BOTH-NEXT:  entry:
 ; FNATTR-NEXT:    invoke void @use2nonnull(i8* %a, i8* %b)
 ; ATTRIBUTOR-NEXT:    invoke void @use2nonnull(i8* nonnull %a, i8* nonnull %b)
 ; BOTH-NEXT:    to label %cont unwind label %exc
 ; BOTH:       cont:
 ; BOTH-NEXT:    [[NULL_CHECK:%.*]] = icmp eq i8* %b, null
 ; BOTH-NEXT:    ret i1 [[NULL_CHECK]]
 ; BOTH:       exc:

 
 ; Check we do not annotate the function interface of this weak function.
 ; ATTRIBUTOR: define weak_odr void @weak_caller(i32* nonnull %a)
 define weak_odr void @weak_caller(i32* nonnull %a) {
   call void @called_by_weak(i32* %a)
   ret void
 }
 
+
 attributes #0 = { "null-pointer-is-valid"="true" }
+attributes #1 = { nounwind willreturn}

llvm/test/Transforms/FunctionAttrs/norecurse.ll

 ; ATTRIBUTOR-NOT: Function Attrs
 ; ATTRIBUTOR: define linkonce_odr i32 @leaf_redefinable()
 define linkonce_odr i32 @leaf_redefinable() {
   ret i32 1
 }
 
 ; Call through a function pointer
 ; ATTRIBUTOR-NOT: Function Attrs
-; ATTRIBUTOR: define i32 @eval_func(i32 (i32)* nocapture %0, i32 %1)
-define i32 @eval_func(i32 (i32)* , i32) local_unnamed_addr {
+; ATTRIBUTOR: define i32 @eval_func1(i32 (i32)* nocapture nonnull %0, i32 %1)
+define i32 @eval_func1(i32 (i32)* , i32) local_unnamed_addr {
+  %3 = tail call i32 %0(i32 %1) #2
+  ret i32 %3
+}
+
+; ATTRIBUTOR-NOT: Function Attrs
+; ATTRIBUTOR: define i32 @eval_func2(i32 (i32)* nocapture %0, i32 %1)
+define i32 @eval_func2(i32 (i32)* , i32) local_unnamed_addr "null-pointer-is-valid"="true"{
   %3 = tail call i32 %0(i32 %1) #2
   ret i32 %3
 }
 
 declare void @unknown()
 ; Call an unknown function in a dead block.
 ; ATTRIBUTOR: Function Attrs: nofree norecurse nosync nounwind readnone willreturn
 ; ATTRIBUTOR: define i32 @call_unknown_in_dead_block()
 define i32 @call_unknown_in_dead_block() local_unnamed_addr {
   ret i32 0
 Dead:
   tail call void @unknown()
   ret i32 1
 }
 

llvm/test/Transforms/FunctionAttrs/nosync.ll

 ; int load_monotonic(_Atomic int *num) {
 ;   int n = atomic_load_explicit(num, memory_order_relaxed);
 ;   return n;
 ; }
 
 ; FNATTR: Function Attrs: nofree norecurse nounwind uwtable
 ; FNATTR-NEXT: define i32 @load_monotonic(i32* nocapture readonly %0)
 ; ATTRIBUTOR: Function Attrs: nofree norecurse nosync nounwind uwtable
-; ATTRIBUTOR-NEXT: define i32 @load_monotonic(i32* nocapture readonly %0)
+; ATTRIBUTOR-NEXT: define i32 @load_monotonic(i32* nocapture nonnull readonly dereferenceable(4) %0)
 define i32 @load_monotonic(i32* nocapture readonly %0) norecurse nounwind uwtable {
   %2 = load atomic i32, i32* %0 monotonic, align 4
   ret i32 %2
 }
 
 
 ; TEST 3
 ; atomic store with monotonic ordering.
 ; void store_monotonic(_Atomic int *num) {
 ;   atomic_load_explicit(num, memory_order_relaxed);
 ; }
 
 ; FNATTR: Function Attrs: nofree norecurse nounwind uwtable
 ; FNATTR-NEXT: define void @store_monotonic(i32* nocapture %0)
 ; ATTRIBUTOR: Function Attrs: nofree norecurse nosync nounwind uwtable
-; ATTRIBUTOR-NEXT: define void @store_monotonic(i32* nocapture writeonly %0)
+; ATTRIBUTOR-NEXT: define void @store_monotonic(i32* nocapture nonnull writeonly dereferenceable(4) %0) 
 define void @store_monotonic(i32* nocapture %0) norecurse nounwind uwtable {
   store atomic i32 10, i32* %0 monotonic, align 4
   ret void
 }
 
 ; TEST 4 - negative, should not deduce nosync
 ; atomic load with acquire ordering.
 ; int load_acquire(_Atomic int *num) {
 ;   int n = atomic_load_explicit(num, memory_order_acquire);
 ;   return n;
 ; }
 
 ; FNATTR: Function Attrs: nofree norecurse nounwind uwtable
 ; FNATTR-NEXT: define i32 @load_acquire(i32* nocapture readonly %0)
 ; ATTRIBUTOR: Function Attrs: nofree norecurse nounwind uwtable
 ; ATTRIBUTOR-NOT: nosync
-; ATTRIBUTOR-NEXT: define i32 @load_acquire(i32* nocapture readonly %0)
+; ATTRIBUTOR-NEXT: define i32 @load_acquire(i32* nocapture nonnull readonly dereferenceable(4) %0)
 define i32 @load_acquire(i32* nocapture readonly %0) norecurse nounwind uwtable {
   %2 = load atomic i32, i32* %0 acquire, align 4
   ret i32 %2
 }
 
 ; TEST 5 - negative, should not deduce nosync
 ; atomic load with release ordering
 ; void load_release(_Atomic int *num) {
 ;   atomic_store_explicit(num, 10, memory_order_release);
 ; }
 
 ; FNATTR: Function Attrs: nofree norecurse nounwind uwtable
 ; FNATTR-NEXT: define void @load_release(i32* nocapture %0)
 ; ATTRIBUTOR: Function Attrs: nofree norecurse nounwind uwtable
 ; ATTRIBUTOR-NOT: nosync
 ; ATTRIBUTOR-NEXT: define void @load_release(i32* nocapture writeonly %0)
 define void @load_release(i32* nocapture %0) norecurse nounwind uwtable {
   store atomic volatile i32 10, i32* %0 release, align 4
   ret void
 }
 
 ; TEST 6 - negative volatile, relaxed atomic
 
 ; FNATTR: Function Attrs: nofree norecurse nounwind uwtable
 ; FNATTR-NEXT: define void @load_volatile_release(i32* nocapture %0)
 ; ATTRIBUTOR: Function Attrs: nofree norecurse nounwind uwtable
 ; ATTRIBUTOR-NOT: nosync

 ; }
 
 %"struct.std::atomic" = type { %"struct.std::__atomic_base" }
 %"struct.std::__atomic_base" = type { i8 }
 
 ; FNATTR: Function Attrs: nofree norecurse nounwind
 ; FNATTR-NEXT: define void @foo1(i32* nocapture %0, %"struct.std::atomic"* nocapture %1)
 ; ATTRIBUTOR-NOT: nosync
-; ATTRIBUTOR: define void @foo1(i32* nocapture writeonly %0, %"struct.std::atomic"* nocapture writeonly %1)
+; ATTRIBUTOR: define void @foo1(i32* nocapture nonnull writeonly dereferenceable(4) %0, %"struct.std::atomic"* nocapture writeonly %1)
+
 define void @foo1(i32* %0, %"struct.std::atomic"* %1) {
   store i32 100, i32* %0, align 4
   fence release
   %3 = getelementptr inbounds %"struct.std::atomic", %"struct.std::atomic"* %1, i64 0, i32 0, i32 0
   store atomic i8 1, i8* %3 monotonic, align 1
   ret void
 }
 

 8:                                                ; preds = %4
   fence acquire
   ret void
 }
 
 ; TEST 13 - Fence syncscope("singlethread") seq_cst
 ; FNATTR: Function Attrs: nofree norecurse nounwind
 ; FNATTR-NEXT: define void @foo1_singlethread(i32* nocapture %0, %"struct.std::atomic"* nocapture %1)
-; ATTRIBUTOR: Function Attrs: nofree nosync
-; ATTRIBUTOR: define void @foo1_singlethread(i32* nocapture writeonly %0, %"struct.std::atomic"* nocapture writeonly %1)
+; ATTRIBUTOR: Function Attrs: nofree nosync nounwind willreturn
+; ATTRIBUTOR: define void @foo1_singlethread(i32* nocapture nonnull writeonly dereferenceable(4) %0, %"struct.std::atomic"* nocapture writeonly %1)
+
 define void @foo1_singlethread(i32* %0, %"struct.std::atomic"* %1) {
   store i32 100, i32* %0, align 4
   fence syncscope("singlethread") release
   %3 = getelementptr inbounds %"struct.std::atomic", %"struct.std::atomic"* %1, i64 0, i32 0, i32 0
   store atomic i8 1, i8* %3 monotonic, align 1
   ret void
 }
 
 ; FNATTR: Function Attrs: nofree norecurse nounwind
 ; FNATTR-NEXT: define void @bar_singlethread(i32* nocapture readnone %0, %"struct.std::atomic"* nocapture readonly %1)
-; ATTRIBUTOR: Function Attrs: nofree nosync
+; ATTRIBUTOR: Function Attrs: nofree nosync nounwind
 ; ATTRIBUTOR: define void @bar_singlethread(i32* nocapture readnone %0, %"struct.std::atomic"* nocapture readonly %1)
 define void @bar_singlethread(i32* %0, %"struct.std::atomic"* %1) {
   %3 = getelementptr inbounds %"struct.std::atomic", %"struct.std::atomic"* %1, i64 0, i32 0, i32 0
   br label %4
 
 4:                                                ; preds = %4, %2
   %5 = load atomic i8, i8* %3  monotonic, align 1
   %6 = and i8 %5, 1

llvm/test/Transforms/FunctionAttrs/read_write_returned_arguments_scc.ll

if.end:                                           ; preds = %entry
   br label %return
 
 return:                                           ; preds = %if.end, %if.then
   %retval.0 = phi i32* [ %call5, %if.end ], [ %n0, %if.then ]
   ret i32* %retval.0
 }
 
 ; CHECK: Function Attrs: nofree nosync nounwind
-; CHECK-NEXT: define internal i32* @internal_ret1_rrw(i32* %r0, i32* returned %r1, i32* %w0)
+; CHECK-NEXT: define internal i32* @internal_ret1_rrw(i32* nonnull dereferenceable(4) %r0, i32* returned %r1, i32* %w0)
 define internal i32* @internal_ret1_rrw(i32* %r0, i32* %r1, i32* %w0) {
 entry:
   %0 = load i32, i32* %r0, align 4
   %tobool = icmp ne i32 %0, 0
   br i1 %tobool, label %if.end, label %if.then
 
 if.then:                                          ; preds = %entry
   br label %return
if.end:                                           ; preds = %entry
   store i32 %0, i32* %w0, align 4
   br label %return
 
 return:                                           ; preds = %if.end, %if.then
   ret i32* %w0
 }
 
 ; CHECK: Function Attrs: nofree nosync nounwind
-; CHECK-NEXT: define internal i32* @internal_ret1_rw(i32* %r0, i32* returned %w0)
+; CHECK-NEXT: define internal i32* @internal_ret1_rw(i32* nonnull dereferenceable(4) %r0, i32* returned %w0)
 define internal i32* @internal_ret1_rw(i32* %r0, i32* %w0) {
 entry:
   %0 = load i32, i32* %r0, align 4
   %tobool = icmp ne i32 %0, 0
   br i1 %tobool, label %if.end, label %if.then
 
 if.then:                                          ; preds = %entry
   br label %return

llvm/test/Transforms/FunctionAttrs/readattrs.ll

 
 ; CHECK: define void @test4_2(i8* nocapture readonly %p)
 define void @test4_2(i8* %p) {
   call void @test4_1(i8* %p)
   ret void
 }
 
 ; FNATTR: define void @test5(i8** nocapture %p, i8* %q)
-; ATTRIBUTOR: define void @test5(i8** nocapture writeonly %p, i8* %q)
+; ATTRIBUTOR: define void @test5(i8** nocapture nonnull writeonly dereferenceable(8) %p, i8* %q)
 ; Missed optz'n: we could make %q readnone, but don't break test6!
 define void @test5(i8** %p, i8* %q) {
   store i8* %q, i8** %p
   ret void
 }
 
 declare void @test6_1()
 ; FNATTR: define void @test6_2(i8** nocapture %p, i8* %q)
-; ATTRIBUTOR: define void @test6_2(i8** nocapture writeonly %p, i8* %q)
+; ATTRIBUTOR: define void @test6_2(i8** nocapture nonnull writeonly dereferenceable(8) %p, i8* %q)
 ; This is not a missed optz'n.
 define void @test6_2(i8** %p, i8* %q) {
   store i8* %q, i8** %p
   call void @test6_1()
   ret void
 }
 
 ; FNATTR: define void @test7_1(i32* inalloca nocapture %a)

llvm/test/Transforms/InferFunctionAttrs/dereferenceable.ll

 ; RUN: opt < %s -inferattrs -S | FileCheck %s
+; RUN: opt < %s -attributor --attributor-disable=false -S | FileCheck %s --check-prefix=ATTRIBUTOR
+
+
 
 ; Determine dereference-ability before unused loads get deleted:
 ; https://bugs.llvm.org/show_bug.cgi?id=21780
 
 define <4 x double> @PR21780(double* %ptr) {
 ; CHECK-LABEL: @PR21780(double* %ptr)
+; FIXME: this should be @PR21780(double* nonnull dereferenceable(32) %ptr) 
+;        trakcing use of GEP in Attributor would fix this problem.
+; ATTRIBUTOR-LABEL: @PR21780(double* nocapture nonnull readonly dereferenceable(8) %ptr)
+
   ; GEP of index 0 is simplified away.
   %arrayidx1 = getelementptr inbounds double, double* %ptr, i64 1
   %arrayidx2 = getelementptr inbounds double, double* %ptr, i64 2
   %arrayidx3 = getelementptr inbounds double, double* %ptr, i64 3
 
   %t0 = load double, double* %ptr, align 8
   %t1 = load double, double* %arrayidx1, align 8
   %t2 = load double, double* %arrayidx2, align 8
   %t3 = load double, double* %arrayidx3, align 8
 
   %vecinit0 = insertelement <4 x double> undef, double %t0, i32 0
   %vecinit1 = insertelement <4 x double> %vecinit0, double %t1, i32 1
   %vecinit2 = insertelement <4 x double> %vecinit1, double %t2, i32 2
   %vecinit3 = insertelement <4 x double> %vecinit2, double %t3, i32 3
   %shuffle = shufflevector <4 x double> %vecinit3, <4 x double> %vecinit3, <4 x i32> <i32 0, i32 0, i32 2, i32 2>
   ret <4 x double> %shuffle
 }
 
+
+define double @PR21780_only_access3_with_inbounds(double* %ptr) {
+; CHECK-LABEL: @PR21780_only_access3_with_inbounds(double* %ptr)
+; FIXME: this should be @PR21780_only_access3_with_inbounds(double* nonnull dereferenceable(32) %ptr)
+;        trakcing use of GEP in Attributor would fix this problem.
+; ATTRIBUTOR-LABEL: @PR21780_only_access3_with_inbounds(double* nocapture readonly %ptr) 
+
+  %arrayidx3 = getelementptr inbounds double, double* %ptr, i64 3
+  %t3 = load double, double* %arrayidx3, align 8
+  ret double %t3
+}
+
+define double @PR21780_only_access3_without_inbounds(double* %ptr) {
+; CHECK-LABEL: @PR21780_only_access3_without_inbounds(double* %ptr)
+; ATTRIBUTOR-LABEL: @PR21780_only_access3_without_inbounds(double* nocapture readonly %ptr)
+  %arrayidx3 = getelementptr double, double* %ptr, i64 3
+  %t3 = load double, double* %arrayidx3, align 8
+  ret double %t3
+}
+
+define double @PR21780_without_inbounds(double* %ptr) {
+; CHECK-LABEL: @PR21780_without_inbounds(double* %ptr)
+; FIXME: this should be @PR21780_without_inbounds(double* nonnull dereferenceable(32) %ptr)
+; ATTRIBUTOR-LABEL: @PR21780_without_inbounds(double* nocapture nonnull readonly dereferenceable(8) %ptr)
+
+  %arrayidx1 = getelementptr double, double* %ptr, i64 1
+  %arrayidx2 = getelementptr double, double* %ptr, i64 2
+  %arrayidx3 = getelementptr double, double* %ptr, i64 3
+
+  %t0 = load double, double* %ptr, align 8
+  %t1 = load double, double* %arrayidx1, align 8
+  %t2 = load double, double* %arrayidx2, align 8
+  %t3 = load double, double* %arrayidx3, align 8
+
+  ret double %t3
+}
+
 ; Unsimplified, but still valid. Also, throw in some bogus arguments.
 
 define void @gep0(i8* %unused, i8* %other, i8* %ptr) {
 ; CHECK-LABEL: @gep0(i8* %unused, i8* %other, i8* %ptr)
   %arrayidx0 = getelementptr i8, i8* %ptr, i64 0
   %arrayidx1 = getelementptr i8, i8* %ptr, i64 1
   %arrayidx2 = getelementptr i8, i8* %ptr, i64 2
   %t0 = load i8, i8* %arrayidx0