[WIP][NFC][Attributor] noalias attribute deduction fixme

[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

2500–2506

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

2507

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.

5199

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

245

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

[pgode]

llvm/lib/Transforms/IPO/Attributor.cpp

2507

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

2507

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.

5196

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

2507

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

5196

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

2507

Sounds good! Looking forward to it.

5196

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

2471

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.

2500

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).

5180

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

245

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

2482

Move this check before the CallBase conditional.

2502

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.

5196

There is a continue missing in the above conditional.

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

40

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

2482

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

2502

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.

5196

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

[jdoerfert]

llvm/lib/Transforms/IPO/Attributor.cpp

2502

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

2470

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

2482

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
}