[BasicAA] Don't short-circuit non-capturing arguments

[nikic]

Summary

This is a possible alternative to D153464. BasicAA currently assumes that an unescaped alloca cannot be read through non-nocapture arguments of a call, based on the argument that if the argument were based on the alloca, it would not be unescaped.

This currently fails in the case where the call is an ephemeral value and as such does not count as a capture. It could also happen if CaptureTracking were slightly smarter and continued following captures on call return values.

[fhahn]

Hmm, I am a bit worried that fixing this here rather than marking them as capturing in the CaptureTracker leaves a potential door for mis-use of the general API. Perhaps it would be possible to just consider those calls as capturing, as in
D153577

[aeubanks]

In D153511#4442041, @fhahn wrote:

Hmm, I am a bit worried that fixing this here rather than marking them as capturing in the CaptureTracker leaves a potential door for mis-use of the general API. Perhaps it would be possible to just consider those calls as capturing, as in
D153577

Those calls aren't capturing the pointer though.

Do you mean you're worried about mis-use of the capture tracking API?

I think this makes sense, using capture tracking to infer mod/ref seems backwards. IIUC this analysis depends on AAQI.CI->isNotCapturedBeforeOrAt() agreeing with Call->doesNotCapture(), which seems brittle.

[fhahn]

In D153511#4442108, @aeubanks wrote:

In D153511#4442041, @fhahn wrote:

Hmm, I am a bit worried that fixing this here rather than marking them as capturing in the CaptureTracker leaves a potential door for mis-use of the general API. Perhaps it would be possible to just consider those calls as capturing, as in
D153577

Those calls aren't capturing the pointer though.

Do you mean you're worried about mis-use of the capture tracking API?

I think this makes sense, using capture tracking to infer mod/ref seems backwards. IIUC this analysis depends on AAQI.CI->isNotCapturedBeforeOrAt() agreeing with Call->doesNotCapture(), which seems brittle.

IIUC the capture tracking here is used more to check whether the pointer escapes. We also have the following code which considers calls as capturing: https://github.com/llvm/llvm-project/blob/88f07a311947f88de82ad2de9b2d6a26eba21343/llvm/lib/Analysis/CaptureTracking.cpp#L314 . For the test case, if the result isn't used in an assume, it is considered capturing the pointer.

[nikic]

You don't really need an assume to show the issue, this simpler variant exhibits the same problem: https://llvm.godbolt.org/z/M3K5fG97G The store is removed even though the call reads it.

This just happens to mostly work out fine right now because such calls get DCEd, so we don't observe end-to-end miscompiles. If capture tracking were slightly smarter and followed the return value (as we effectively do in the assume case) we would get observable miscompiles even without ephemeral value interactions.

[fhahn]

In D153511#4442180, @nikic wrote:

You don't really need an assume to show the issue, this simpler variant exhibits the same problem: https://llvm.godbolt.org/z/M3K5fG97G The store is removed even though the call reads it.

This just happens to mostly work out fine right now because such calls get DCEd, so we don't observe end-to-end miscompiles. If capture tracking were slightly smarter and followed the return value (as we effectively do in the assume case) we would get observable miscompiles even without ephemeral value interactions.

Yeah, one issue seems to be that AA uses CaptureTracking as proxy for escaping (e.g. EarliestEscapeInfo by DSE), but in some cases escaping doesn't imply capturing and things go wrong. I *think* tracking escapes (instead of captures) would make sense in general, as this should help to avoid most code-size changes seen by this patch I suspect.

[nikic]

In D153511#4442266, @fhahn wrote:

In D153511#4442180, @nikic wrote:

You don't really need an assume to show the issue, this simpler variant exhibits the same problem: https://llvm.godbolt.org/z/M3K5fG97G The store is removed even though the call reads it.

This just happens to mostly work out fine right now because such calls get DCEd, so we don't observe end-to-end miscompiles. If capture tracking were slightly smarter and followed the return value (as we effectively do in the assume case) we would get observable miscompiles even without ephemeral value interactions.

Yeah, one issue seems to be that AA uses CaptureTracking as proxy for escaping (e.g. EarliestEscapeInfo by DSE), but in some cases escaping doesn't imply capturing and things go wrong. I *think* tracking escapes (instead of captures) would make sense in general, as this should help to avoid most code-size changes seen by this patch I suspect.

CaptureTracking handles both captures and escapes. There is no escape in this case. No escape does not imply that memory is not accessed, just that provenance is not retained after the call.

BasicAA is making assumptions about how the CaptureTracking implementation works here, which goes beyond the actual capture/escape properties. Those assumptions are close, but not quite correct.

[fhahn]

In D153511#4442568, @nikic wrote:

CaptureTracking handles both captures and escapes. There is no escape in this case. No escape does not imply that memory is not accessed, just that provenance is not retained after the call.

BasicAA is making assumptions about how the CaptureTracking implementation works here, which goes beyond the actual capture/escape properties. Those assumptions are close, but not quite correct.

Right, IIUC the code in BasicAA assumes escaping pointers to not be visible outside the current function, which includes not being passed to readonly functions. I was initially (incorrectly) assuming this is what our APIs would consider an escape. It might be worth to have an option to track this property for AA.

[nikic]

In D153511#4442640, @fhahn wrote:

In D153511#4442568, @nikic wrote:

CaptureTracking handles both captures and escapes. There is no escape in this case. No escape does not imply that memory is not accessed, just that provenance is not retained after the call.

BasicAA is making assumptions about how the CaptureTracking implementation works here, which goes beyond the actual capture/escape properties. Those assumptions are close, but not quite correct.

Right, IIUC the code in BasicAA assumes escaping pointers to not be visible outside the current function, which includes not being passed to readonly functions.

Not really. A call can access an alloca in one of two ways: Either by the pointer first escaping and the call accessing the escaped pointer, or by the pointer being passed as an argument to the call. BasicAA performs checks for both of these. The first is based on CaptureTracking, and the second based on alias checks on the call arguments. This is the correct way to use the CaptureTracking API.

The only problem is that BasicAA, as an optimization, does not perform the argument check for non-nocapture arguments, on the premise that CaptureTracking will have treated these as an escape and thus failed the first check already.

I was initially (incorrectly) assuming this is what our APIs would consider an escape. It might be worth to have an option to track this property for AA.

I don't think this is really possible. For the "escaped before call" check, we are only interested in escapes, not in accesses by calls. It's okay if the pointer gets accessed by previous calls, as long as it does not escape. For accessed, we only care about the current call. So this would require a call-specific result which is not really compatible with EarliestEscapeInfo.

(As a side note, with the change I'm proposing here, we could replace isNotCapturedBeforeOrAt with isNotCaptureBefore, dropping the "OrAt" part. Not sure whether this would make any practical difference.)

[aeubanks]

makes sense to me

llvm/lib/Analysis/BasicAliasAnalysis.cpp

866–871

can you update this comment with your explanation so it's clearer?

llvm/test/Transforms/PhaseOrdering/dse-ephemeral-value-captures.ll

24–25

remove FIXME

[nikic]

Update comment, remove FIXME.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

if (const CallInst *CI = dyn_cast<CallInst>(Call))
           !CI->getAttributes().hasAttrSomewhere(Attribute::ByVal))
         return ModRefInfo::NoModRef;
 
   // Stack restore is able to modify unescaped dynamic allocas. Assume it may
   // modify them even though the alloca is not escaped.
   if (auto *AI = dyn_cast<AllocaInst>(Object))
     if (!AI->isStaticAlloca() && isIntrinsicCall(Call, Intrinsic::stackrestore))
       return ModRefInfo::Mod;
 
-  // If the pointer is to a locally allocated object that does not escape,
-  // then the call can not mod/ref the pointer unless the call takes the pointer
-  // as an argument, and itself doesn't capture it.
+  // A call can access a locally allocated object either because it is passed as
+  // an argument to the call, or because it has escaped prior to the call.
+  //
+  // Make sure the object has not escaped here, and then check that none of the
+  // call arguments alias the object below.
   if (!isa<Constant>(Object) && Call != Object &&
       AAQI.CI->isNotCapturedBeforeOrAt(Object, Call)) {
 
     // Optimistically assume that call doesn't touch Object and check this
     // assumption in the following loop.
     ModRefInfo Result = ModRefInfo::NoModRef;
 
     unsigned OperandNo = 0;
     for (auto CI = Call->data_operands_begin(), CE = Call->data_operands_end();
          CI != CE; ++CI, ++OperandNo) {
-      // Only look at the no-capture or byval pointer arguments.  If this
-      // pointer were passed to arguments that were neither of these, then it
-      // couldn't be no-capture.
-      if (!(*CI)->getType()->isPointerTy() ||
-          (!Call->doesNotCapture(OperandNo) && OperandNo < Call->arg_size() &&
-           !Call->isByValArgument(OperandNo)))
+      if (!(*CI)->getType()->isPointerTy())
         continue;
 
       // Call doesn't access memory through this operand, so we don't care
       // if it aliases with Object.
       if (Call->doesNotAccessMemory(OperandNo))
         continue;
 
       // If this is a no-capture pointer argument, see if we can tell that it

llvm/test/Transforms/PhaseOrdering/dse-ephemeral-value-captures.ll

 
 then:
   %res = call i1 @cond()
   ret i1 %res
 
 else:
   ret i1 0
 }
 
-; FIXME: At the moment, the function is incorrectly simplified to unreachable.
 define i32 @test() {
 ; CHECK-LABEL: define i32 @test() {
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    unreachable
+; CHECK-NEXT:    br label [[THEN_I:%.*]]
+; CHECK:       then.i:
+; CHECK-NEXT:    [[RES_I:%.*]] = call i1 @cond()
+; CHECK-NEXT:    br label [[CHECK_COND_EXIT:%.*]]
+; CHECK:       check_cond.exit:
+; CHECK-NEXT:    call void @llvm.assume(i1 [[RES_I]])
+; CHECK-NEXT:    ret i32 0
 ;
 entry:
   %a = alloca i32, align 4
   call void @llvm.lifetime.start.p0(i64 4, ptr nonnull %a)
   store i32 1, ptr %a, align 4
   %res = call i1 @check_cond(ptr %a)
   call void @llvm.lifetime.end.p0(i64 4, ptr nonnull %a)
   call void @llvm.assume(i1 %res)
   ret i32 0
 }
 
 attributes #0 = { nounwind readonly willreturn }