[Attributor] Improve noalias preservation using reachability

[pgode]

Summary

Fixme for noalias deduction
(ii) Check whether the value is captured in the scope using AANoCapture.

FIXME: This is conservative though, it is better to look at CFG and
             check only uses possibly executed before this callsite.

Propagates caller argument's noalias attribute to callee.

[jdoerfert]

Thanks for the update. I inlined some comments.

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

855 ↗

(On Diff #234316)

Could we make the Predicate take the same values as for checkForAllUses?
Don't we need to specify (1) the uses of "what", and (2) reachable from "where". The From argument seems to mix these two concepts.

Two combine the two comments above: I guess we could actually make this a special of checkForAllUses. If checkForAllUses is given a Instruction *ReachableFromI argument that is not null, it means filter uses that are not reachable from ReachableFromI.

1707 ↗

(On Diff #234316)

I don't know why we want Values here and why you return assumed, the "worst" state, which is what we need to return until we get a proper updateImpl is true.

llvm/lib/Transforms/IPO/Attributor.cpp

2860–2869

What we need to check here is:

Are there uses of the pointer value that are potentially executed before the use at this call site *and* is the pointer potentially captured at any of those uses.

I think we could do this in two steps:

1. Iterate over all uses of the pointer and collect the uses that may reach the current call instruction. So I think the A.checkForAllUses might actually do as we need to check if the call we are looking at is reachable from the use.
2. For all those uses, ask AANoCapture if they are potentially capturing. The method doesn't exist yet but you can add it to the AANoCapture interface and for now return always true.

[pgode]

Tried addressing the comments in this patch.

• Created new methods for NoCaptureMaybeBeforeInstruction which returns true as of now. Using this method in the checkForAllUses method.
• Added additional parameter to checkForAllUses (initializing to nullptr). If this ptr is not null, then we check if use is reachable till this callsite instruction.
• Predicate checks in which case we should follow for use's user.
• checkForAllUses is called to check uses of argument. If it is valid/reachable use, then noalias deduction should happen.

[pgode]

Addressed the comments in the new diff version.

[jdoerfert]

I think we make progress here. I haven't gone through all test changes because they might change again once you worked on the comments below.

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

848 ↗

(On Diff #235285)

Yes, this looks really useful!

Minor: Please clang format the code.

2090 ↗

(On Diff #235285)

We should default to false in these methods as we don't know. I actually don't think we need them, see my comment at the use site.

llvm/lib/Transforms/IPO/Attributor.cpp

2870–2871

Minor:
You can asssume V has pointer type so you don't need to check it.
To get the CallSiteI directly you can call getCtxI().
I think you should even pass CallSiteI->getNextNode() to checkForAllUses because we don't want to see the uses in the call site.

7439

I don't understand the code after the if (ReachableFromI) condition.
We should not care about the operation here and also not about nocapture because this is a generic utility function.

What you want to check if ReachableFromI is:

• Query the AAReachability for the function (you can do that before the worklist while loop actually).
• Ask AAReachability if UserI is reachable from ReachableFromI, if not skip the UserI.

llvm/test/Transforms/Attributor/noalias.ll

265

The last use should not be noalias because the on before is not nocapure!

[pgode]

llvm/lib/Transforms/IPO/Attributor.cpp

2870–2871

Thanks for the review comments. I didn't understand the part:

I think you should even pass CallSiteI->getNextNode() to checkForAllUses because we don't want to see the uses in the call site.

I thought that, if we don't have any uses of instruction/value passed to CallSite, before the callsite instruction then we can propagate. CallSiteI->getNextNode() gives me next node after the callsite instruction. Not sure about the reason why we should also have additional call to checkForAllUses.

Should we have something like below.

if (!A.checkForAllUses(UsePred, *this, V, getCtxI())  && !A.checkForAllUses(UsePred, *this, V, getCtxI()->getNextNode()) {
.. 
}

[pgode]

Thanks for suggestions. I am learning more.

• Using AAReachability instead of AANoCapture and also removed those functions from AANoCapture.

I think, i need to further understand the test modifications. The noalias.ll change for last function use_nocapture is still not done. Need to further check this.

[jdoerfert]

I did write a confusing comment in the last review, below I tried to clarify.

llvm/lib/Transforms/IPO/Attributor.cpp

2870–2871

First, I got confused myself in the last comment. I'll explain what my thinking was and then why it was not want we want anyway:
I thought:

We have a call `call @foo(%v)` and we want to know if `%v` is used *after* the call.
To do that we would look at used reachable from the instruction after the call because we do not want to see the use of `%v` in the call.
That is however not what we actually want to do.

What we want to do is:

Check if there is any use
   - which is not marked `nocapture`, 
   - which is not the call instruction, and
   - from which we can reach the call instruction.
If such a use exists, the value might have been captured already.
If not, it might only be captured by the call instruction or later.
In the former case we need to give up, in the latter we don't.

To achieve this we need to perform the reachability query in the callback (UsePred above). If the User (= U.getUser()) is an instruction that might cause the value to escape, it is not the call instruction (= getCtxI()), and from the user the call instruction is reachable, we give up. Otherwise we continue scanning.

7436

You need to check both ReachableFromI and ReachabilityAA for null in the outer conditional.
If it is *not* reachable we should skip the user, thus continue, otherwise we fall through and call the predicate below.

We should also split the change to checkForAllUses from the rest and make it a separate review.

[pgode]

llvm/lib/Transforms/IPO/Attributor.cpp

2870–2871

Thanks a lot for clarifying. That make perfect sense to me.
I am working on it and will soon submit the next version.

7436

I agree for the null checks and continue. I missed them both.
Can I keep this and create separate review after this ?
As of now, ReachableFromI not equal nullptr value is passed for noalias deduction only.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

2870–2871

Sounds good! Looking forward to it.

7436

You can split this in two reviews. One for the checkForAllUses code and one for the AANoAlias code.
You will not even need to set ReachableFromI from the NoAlias query but we still should keep the functionality to only visit reachable users. It will be useful soon.

[pgode]

I have tried modifying the patch to include suggestions.

• Added condition to check if use is not marked nocapture.
• Included nullpointer check and reachability check.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

2822

You need to iterate over all uses (not only reachable ones) and then in the UsePred ask if getCtxI() is reachable from the User. If not, the UsePred can return true (=all is OK).

2825

If you want to use the AANoCapture you need the IR position of the use: const IRPosition UseIRP = IRPosition::callsite_argument(CS, CS.getArgumentNo(&U)); not of the outer call site. If you just want to know if it already is marked nocapture you can just ask the call site CS: CS.paramHasAttr(CS.getArgumentNo(&U), Attribute::NoCapture)

You also want to return true (= all is OK) if the argument has a no-capture attribute. If not, you continue with the reachability check we need before // Unknown user for which we can not track uses further.

7421

You need to track dependence here or remember if you excluded a use due to reachability and track the dependence then. For liveness we doe this with the AnyDead flag.

[pgode]

Thanks @jdoerfert for detailed explanation and listing the corrections.

Modifications in this patch are:

• In checkForAllUses, iterating over all uses instead of earlier iterating over reachable ones only. Using AnyUnreachable (similar to AnyDead) to track AA dependencies. Here I just set this flag if UserI and getCtxI() is not reachable and I don't skip this but continue with checking for Pred. I am also recording dependencies as suggested by @jdoerfert .
• Modified the UsePred, to check for nocapture using AANoCapture and checking reachability for UserI and getCtxI.

With this patch 3 tests are modified.

[pgode]

llvm/test/Transforms/Attributor/noalias.ll

265

I am not sure if this case is applicable for noalias propagation.

[jdoerfert]

Sorry for my delay. I hope these are the last problems.

llvm/lib/Transforms/IPO/Attributor.cpp

2836

Move this check before the CallBase conditional.

2862

I don't think you should restrict it to uses reachable from getCtxI here. All uses are interesting and reachability is checked from the uses.

7436

There is a continue missing in the above conditional.

llvm/test/Transforms/Attributor/IPConstantProp/pthreads.ll

40 ↗

(On Diff #235776)

I think only the first noalias is correct. Hopefully with the changes I suggested above this should be fixed.

[pgode]

Thanks for reviewing. I understand as this was during year end.
I will make the changes and update the patch. I tried the changes locally and I think I need to further check why noalias is still propagated for other checks in pthread.ll .

Please help me with one clarification regarding checkForAllUses call.

llvm/lib/Transforms/IPO/Attributor.cpp

2836

I agree. This doesn't depend on CallBase anyway.

2862

Please correct me if I am wrong, I understand that we don't need, where we were checking whether uses of V are reachable from getCtxI().
if (!A.checkForAllUses(UsePred, *this, V, getCtxI()))

Instead, we need the regular call which checks for all uses of V.
if (!A.checkForAllUses(UsePred, *this, V)

And in that case, we won't need the ReachableFromI parameter to 'checkForAllUses'. And thus we can have the reachability check only in Pred instead of having one more check in checkForAllUses.
Only problem with this would be w.r.t. setting AnyUnreachable, which records dependencies.

7436

I agree, for unreachable we don't need to check the predicate.

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

2862

Instead, we need the regular call which checks for all uses of V.
if (!A.checkForAllUses(UsePred, *this, V)

Yes.

And in that case, we won't need the ReachableFromI parameter to 'checkForAllUses'. And thus we can have the reachability check only in Pred instead of having one more check in checkForAllUses.

Yes.

Only problem with this would be w.r.t. setting AnyUnreachable, which records dependencies.

You can split the changes to checkForAllUses into a separate patch. We want the changes but it is not needed for the noalias stuff.

[pgode]

Updated patch which considers the review comments.

The pthreads.ll test still shows noalias for all 4 callsites.
I think, as the Pred is executed recursively for individual use, so the reachability condition satisfies for the other 3 callsites as well.

Should we track the noalias for previous use as well ?
For this we may have to add extra bool to the predicate for noalias tracking i.e.

auto UsePred = [&](const Use &U, bool &Follow, bool &CurrUseNoalias) -> bool {

Then we also need to modify the checkForAllUses definition, to check this value. Not sure we need such mechanism.

[jdoerfert]

I found two minor problems that might solve the test issues we see.

llvm/lib/Transforms/IPO/Attributor.cpp

2824

You need to track dependences here. just remove the parameter for now, e.g. A.getAAFor<AAReachability>(*this, IRPosition::function(*ScopeFn))

2836

Remove the ! here. A use is OK, thus we return true if it is assumed not captured.

[pgode]

Thanks for reviewing further.

• Removed the Dependence flag.
• For the conditions to return 'true', in Pred: I observe that the correct condition should be below. This condition means that callsite_argument should not have nocapture and getCtxI() should be reachable from user. I think this, because for noalias propagation to happen w.r.t. (ii) condition, we should get true from checkForAllUses and Pred as well.

// Doesn't have nocapture but reachable.
if (!NoCaptureAA.isAssumedNoCapture() &&
    ReachabilityAA.isAssumedReachable(UserI, getCtxI()))
  return true;

• For the pthreads.ll test case, are we conservatively assuming that when we propagate 1st noalias attribute then there is potential of it getting

captured and thus we should not have noalias attribute propagation for other 3 cases ?

As per current conditions, as all users are reachable and the  [THREAD] parameter doesn't have nocapture, so noalias propagation will happen and the Pred handles 1 use at a time so not sure (and even with Dependence flag set to true), we can get only 1st user parameter to have noalias.  I apologize as I might be missing something basic.

[jdoerfert]

In D71617#1814061, @pgode wrote:

Thanks for reviewing further.

• Removed the Dependence flag.
• For the conditions to return 'true', in Pred: I observe that the correct condition should be below. This condition means that callsite_argument should not have nocapture and getCtxI() should be reachable from user. I think this, because for noalias propagation to happen w.r.t. (ii) condition, we should get true from checkForAllUses and Pred as well.

// Doesn't have nocapture but reachable.
if (!NoCaptureAA.isAssumedNoCapture() &&
    ReachabilityAA.isAssumedReachable(UserI, getCtxI()))
  return true;

I don't follow, but maybe I'm just to tired. Let me try to explain:
What we want is to argue that the use we look at can not introduce aliasing through "unrelated" pointers. We know this is the case if (1) the use is either a nocapture use, thus nocapture is assumed, *or* (2) it is a use from which the current context instruction is not reachable.
Hence the condition would be:

if (auto *CB = dyn_cast<CallBase>(UserI)) {
  ...
  if (NoCaptureAA.isAssumedNoCapture())
    return true;
}
if (!ReachabilityAA.isAssumedReachable(UserI, getCtxI())))
  return true;
``


> - For the pthreads.ll test case, are we conservatively assuming that when we propagate 1st noalias attribute then there is potential of it getting
> captured and thus we should not have noalias attribute propagation for other 3 cases ?  

Yes, that is basically what I think as well.

>   As per current conditions, as all users are reachable and the  [THREAD] parameter doesn't have nocapture, so noalias propagation will happen and the Pred handles 1 use at a time so not sure (and even with Dependence flag set to true), we can get only 1st user parameter to have noalias.  I apologize as I might be missing something basic.  

I think the condition right now is the problem. What happens if you use my proposal above?

[pgode]

Thanks for the explanation. I thought the exact opposite i.e. even though the use is potentially captured in the callee but the callsite of callee is reachable, so we propagate noalias. I apologize as I had basic incorrect understanding.

When I started working on this, I was looking for noalias propagation for the below test. I was looking for the noalias propagation to happen to parameter of 'strtox' function (it gets called from strtold and strtof). For this function the noalias propagation doesn't happen because of the debug messages, '[Attributor][AANoAliasCSArg] check definition: i8* %s :: [P: {arg:s [s@0]}][noalias][S: fix] [Attributor][AANoAliasCSArg] i8* %s is assumed NoAlias in the definition'. These conditions don't solve this problem so I think I will have to look into another way to solve this.

; Function Attrs: nounwind optsize
define dso_local float @strtof(i8* noalias %s, i8** noalias %p) #0 {
entry:
  %call = tail call fastcc double @strtox(i8* %s, i8** %p, i32 0) #3
  %conv = fptrunc double %call to float
  ret float %conv
}

; Function Attrs: nounwind optsize
define internal fastcc double @strtox(i8* %s, i8** %p, i32 %prec) unnamed_addr #0 {
entry:
  %f = alloca %struct._IO_FILE, align 8
  %0 = bitcast %struct._IO_FILE* %f to i8*
  call void @llvm.lifetime.start.p0i8(i64 144, i8* nonnull %0) #4
  %call = call i32 bitcast (i32 (...)* @sh_fromstring to i32 (%struct._IO_FILE*, i8*)*)(%struct._IO_FILE* nonnull %f, i8* %s) #5
  call void @__shlim(%struct._IO_FILE* nonnull %f, i64 0) #5
  %call1 = call double @__floatscan(%struct._IO_FILE* nonnull %f, i32 %prec, i32 1) #5
  %shcnt = getelementptr inbounds %struct._IO_FILE, %struct._IO_FILE* %f, i32 0, i32 30
  %1 = load i64, i64* %shcnt, align 8, !tbaa !2
...
}
; Function Attrs: nounwind optsize
define dso_local double @strtold(i8* noalias %s, i8** noalias %p) #0 {
entry:
  %call = tail call fastcc double @strtox(i8* %s, i8** %p, i32 2) #3
  ret double %call
}

I had tried these conditions earlier and I do not observe noalias propagation in any of the test case.
Out of the 3 tests, I was expecting the noalias propagation to happen for noalias.ll, test10_helper_1 but it doesn't. (I am not sure of the other 2 tests.)

; TEST 10
; Simple CallSite Test

declare void @test10_helper_1(i8* %a)
define void @test10_helper_2(i8* noalias %a) {
>>>; CHECK:   tail call void @test10_helper_1(i8* noalias %a)
  tail call void @test10_helper_1(i8* %a)
  ret void
}
define void @test10(i8* noalias %a) {
; CHECK: define void @test10(i8* noalias %a)
; FIXME: missing noalias
>>>; CHECK-NEXT:   tail call void @test10_helper_1(i8* noalias %a)
  tail call void @test10_helper_1(i8* %a)

; CHECK-NEXT:   tail call void @test10_helper_2(i8* noalias %a)
  tail call void @test10_helper_2(i8* %a)
  ret void
}

[jdoerfert]

@pgode Are you still looking into this? Do you need feedback from me?

[pgode]

In D71617#1911979, @jdoerfert wrote:

@pgode Are you still looking into this? Do you need feedback from me?

I apologize for not coming back on this as I got tied up with other tasks.

Thank you for patiently clarifying things so far.
I agree to the changes which you suggested but I couldn't create a new test which passes due to this change.

As you had pointed that I was not clear in my logic. Major reason for that was I had incomplete understanding of fixpoint iteration and data flow analysis concepts, which I could get a better understanding now.
Please guide me more on examples or if you think I should work on something else if there is better solution with someone.

Bit more detail on the examples (I am referring) are:

1. I started with wrong example. In the code below, I was questioning noalias attribute propagation to strtox. Here the log message clearly showed that the pointer 's' gets captured by 'sh_fromstring' callsite in strtox.

; Function Attrs: nounwind optsize
  define dso_local float @strtof(i8* noalias %s, i8** noalias %p) #0 {
  entry:
    %call = tail call fastcc double @strtox(i8* %s, i8** %p, i32 0) #3
    %conv = fptrunc double %call to float
    ret float %conv
  }

  ; Function Attrs: nounwind optsize
  define internal fastcc double @strtox(i8* %s, i8** %p, i32 %prec) unnamed_addr #0 {
  entry:
    %f = alloca %struct._IO_FILE, align 8
    %0 = bitcast %struct._IO_FILE* %f to i8*
    call void @llvm.lifetime.start.p0i8(i64 144, i8* nonnull %0) #4
    %call = call i32 bitcast (i32 (...)* @sh_fromstring to i32 (%struct._IO_FILE*, i8*)*)(%struct._IO_FILE* nonnull %f, i8* %s) #5
    call void @__shlim(%struct._IO_FILE* nonnull %f, i64 0) #5
    %call1 = call double @__floatscan(%struct._IO_FILE* nonnull %f, i32 %prec, i32 1) #5
    %shcnt = getelementptr inbounds %struct._IO_FILE, %struct._IO_FILE* %f, i32 0, i32 30
    %1 = load i64, i64* %shcnt, align 8, !tbaa !2
  . . .
  }
  ; Function Attrs: nounwind optsize
  define dso_local double @strtold(i8* noalias %s, i8** noalias %p) #0 {
  entry:
    %call = tail call fastcc double @strtox(i8* %s, i8** %p, i32 2) #3
    ret double %call
  }

2. In the other example as well I got it wrong when I was questioning that the noalias attribute should propagate callsite argument %a to test10_helper_1(). This can't happen because the test10_helper_1 is not defined thus we can't determine noalias correctly even though test10_helper_1 callsite is reachable.

TEST 10
declare void @test10_helper_1(i8* %a)
define void @test10_helper_2(i8* noalias %a) {
  tail call void @test10_helper_1(i8* %a)
  ret void
}
define void @test10(i8* noalias %a) {
  tail call void @test10_helper_1(i8* %a)
  tail call void @test10_helper_2(i8* %a)
  ret void
}

[uenoku]

Please use code block.

[jdoerfert]

In D71617#1912380, @pgode wrote:

In D71617#1911979, @jdoerfert wrote:

@pgode Are you still looking into this? Do you need feedback from me?

I apologize for not coming back on this as I got tied up with other tasks.

No worries.

Thank you for patiently clarifying things so far.
I agree to the changes which you suggested but I couldn't create a new test which passes due to this change.

As you had pointed that I was not clear in my logic. Major reason for that was I had incomplete understanding of fixpoint iteration and data flow analysis concepts, which I could get a better understanding now.
Please guide me more on examples or if you think I should work on something else if there is better solution with someone.

Bit more detail on the examples (I am referring) are:

1. I started with wrong example. In the code below, I was questioning noalias attribute propagation to strtox. Here the log message clearly showed that the pointer 's' gets captured by 'sh_fromstring' callsite in strtox.

; Function Attrs: nounwind optsize
  define dso_local float @strtof(i8* noalias %s, i8** noalias %p) #0 {
  entry:
    %call = tail call fastcc double @strtox(i8* %s, i8** %p, i32 0) #3
    %conv = fptrunc double %call to float
    ret float %conv
  }

  ; Function Attrs: nounwind optsize
  define internal fastcc double @strtox(i8* %s, i8** %p, i32 %prec) unnamed_addr #0 {
  entry:
    %f = alloca %struct._IO_FILE, align 8
    %0 = bitcast %struct._IO_FILE* %f to i8*
    call void @llvm.lifetime.start.p0i8(i64 144, i8* nonnull %0) #4
    %call = call i32 bitcast (i32 (...)* @sh_fromstring to i32 (%struct._IO_FILE*, i8*)*)(%struct._IO_FILE* nonnull %f, i8* %s) #5
    call void @__shlim(%struct._IO_FILE* nonnull %f, i64 0) #5
    %call1 = call double @__floatscan(%struct._IO_FILE* nonnull %f, i32 %prec, i32 1) #5
    %shcnt = getelementptr inbounds %struct._IO_FILE, %struct._IO_FILE* %f, i32 0, i32 30
    %1 = load i64, i64* %shcnt, align 8, !tbaa !2
  ...
  }
  ; Function Attrs: nounwind optsize
  define dso_local double @strtold(i8* noalias %s, i8** noalias %p) #0 {
  entry:
    %call = tail call fastcc double @strtox(i8* %s, i8** %p, i32 2) #3
    ret double %call
  }

I think we should be able to propagate noalias to %p in @strtox. Please add this as a test.

2. In the other example as well I got it wrong when I was questioning that the noalias attribute should propagate callsite argument %a to test10_helper_1(). This can't happen because the test10_helper_1 is not defined thus we can't determine noalias correctly even though test10_helper_1 callsite is reachable.

TEST 10
declare void @test10_helper_1(i8* %a)
define void @test10_helper_2(i8* noalias %a) {
  tail call void @test10_helper_1(i8* %a)
  ret void
}
define void @test10(i8* noalias %a) {
  tail call void @test10_helper_1(i8* %a)
  tail call void @test10_helper_2(i8* %a)
  ret void
}

I think both call sites of @test10_helper_1 can have noalias. In both cases there is no escaping use that reaches the call site (except the call site itself).

llvm/lib/Transforms/IPO/Attributor.cpp

2819

I think you need to allow UserI to be getCtx(). That is, if the user is the current instruction we ignore the use but follow if there are subsequent uses!

[pgode]

Additional conditions are included. Added new test.

Please guide on why nonull.ll shows additional noalias propagation. I see that the caller doesn't have noalias attribute but it has derived it.

[uenoku]

Please guide on why nonull.ll shows additional noalias propagation. I see that the caller doesn't have noalias attribute but it has derived it.

It was caused by a bug that the dependence track was missing for NoAliasAA so I have pushed the fix. (https://github.com/llvm/llvm-project/commit/d9bf79f4e9952acca1fa353e39bcee89cd69550f)

[pgode]

In D71617#1919565, @uenoku wrote:

It was caused by a bug that the dependence track was missing for NoAliasAA so I have pushed the fix. (https://github.com/llvm/llvm-project/commit/d9bf79f4e9952acca1fa353e39bcee89cd69550f)

Thanks for sharing this. I will update the patch.

[pgode]

Updated the patch on top on Hideto's changes.
Added description to the test in noalias.ll.
Needed to increase the max-iterations for nonnull.ll

[jdoerfert]

LGTM. @uenoku @sstefan1 feel free to comment on this otherwise I'll commit it tomorrow or soon after.

[jdoerfert]

@pgode Thanks a lot for going through with this, I have high hopes that this will make a substantial difference soon :)

[jdoerfert]

@pgode Can you modify the title (this is not a WIP and not a NFC patch).

[uenoku]

LGTM

[pgode]

In D71617#1921067, @jdoerfert wrote:

@pgode Can you modify the title (this is not a WIP and not a NFC patch).

Done .
Thanks for reminding to complete the patch and for the helpful comments.

[uenoku]

I think the title should be more descriptive, like "improve noalias preservation using reachability" or something.

[pgode]

In D71617#1921143, @uenoku wrote:

I think the title should be more descriptive, like "improve noalias preservation using reachability" or something.

Sounds good. Modified the title. Thanks.