Fix aliasing of launder.invariant.group

[Prazek]

Summary

Patch for capture tracking broke
bootstrap of clang with -fstict-vtable-pointers
which resulted in debbugging nightmare. It was fixed
https://reviews.llvm.org/D46900 but as it turned
out, there were other parts like inliner (computing of
noalias metadata) that I found after bootstraping with enabled
assertions.

[kuhar]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

135 ↗

(On Diff #147597)

Why was the previous change reverted here?

llvm/test/Transforms/Inline/launder.invariant.group.ll

5 ↗

(On Diff #147597)

nit: its

[Prazek]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

135 ↗

(On Diff #147597)

Because it is not needed now, check comment I left on line 1625

1625 ↗

(On Diff #147597)

We never go to this branch, because O1 and O2 are the same by changing GetUnderlyingObject

[kuhar]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

135 ↗

(On Diff #147597)

Makes sense, thanks

[hfinkel]

Is there some general principle we can outline to describe where these updates are needed?

[Prazek]

In D47088#1105258, @hfinkel wrote:

Is there some general principle we can outline to describe where these updates are needed?

I am not sure how to do it right since I am not that familiar with this codebase. Maybe we can make function like

// This function can be used only for aliasing properties. You CAN'T use it to replace
// one value with another!
bool getArgumentAliasingToReturnedPointer(Function *F) {
  if (Value *RV = CS.getReturnedArgOperand())
      return RV;
  if (CS.getIntrinsicID() == Intrinsic::launder_invariant_group)
      return CS.getArgOperand(0);

  return nullptr;    
}

And use it in the places that I modified. Unfortunately it will not change CaptureTracking, because it goes top-down instead of bottom-up.

How does it sound to you?

[hfinkel]

In D47088#1105280, @Prazek wrote:

In D47088#1105258, @hfinkel wrote:

Is there some general principle we can outline to describe where these updates are needed?

I am not sure how to do it right since I am not that familiar with this codebase. Maybe we can make function like

// This function can be used only for aliasing properties. You CAN'T use it to replace
// one value with another!
bool getArgumentAliasingToReturnedPointer(Function *F) {
  if (Value *RV = CS.getReturnedArgOperand())
      return RV;
  if (CS.getIntrinsicID() == Intrinsic::launder_invariant_group)
      return CS.getArgOperand(0);

  return nullptr;    
}

I think this refactoring makes sense. However...

And use it in the places that I modified.

What I want to know is: how did you decide what had to be modified? Did you just look for every place that handles returned arguments? If you had to describe to someone how to find the places that need modification, how would you do it? (because that's what we need in the comment).

Unfortunately it will not change CaptureTracking, because it goes top-down instead of bottom-up.

How does it sound to you?

[Prazek]

In D47088#1105338, @hfinkel wrote:

What I want to know is: how did you decide what had to be modified? Did you just look for every place that handles returned arguments? If you had to describe to someone how to find the places that need modification, how would you do it? (because that's what we need in the comment).

Yes, I pretty much checked every place that uses CaptureTracking and looked for special handling of calls or uses of getUnerlyingObject.

[hfinkel]

In D47088#1105350, @Prazek wrote:

In D47088#1105338, @hfinkel wrote:

What I want to know is: how did you decide what had to be modified? Did you just look for every place that handles returned arguments? If you had to describe to someone how to find the places that need modification, how would you do it? (because that's what we need in the comment).

Yes, I pretty much checked every place that uses CaptureTracking and looked for special handling of calls or uses of getUnerlyingObject.

Okay.

[Prazek]

Refactored code to getArgumentAliasingToReturnedPointer and added few comments.
Please check out isKnownNonZero, as I think it could also use getArgumentAliasingToReturnedPointer.

[hfinkel]

Some of these changes are required for correctness, right? For those, please specifically add a comment near those explaining why.

llvm/include/llvm/Analysis/ValueTracking.h

580 ↗

(On Diff #147626)

Extra whitespace change?

[Prazek]

Added comments

[amharc]

Of course, you should wait for an LGTM from someone more competent than me ;)

llvm/lib/Analysis/CaptureTracking.cpp

255 ↗

(On Diff #147656)

nit: do not capture

[Prazek]

• Fixed nit

[xbolva00]

llvm/lib/Analysis/ValueTracking.cpp

3389 ↗

(On Diff #147657)

Why assert here?

[Prazek]

llvm/lib/Analysis/ValueTracking.cpp

3389 ↗

(On Diff #147657)

It is possible that this funciton would return nullptr if passed null CS,
but such function would be harder to reason about. In this case I assume that caller checked the the instruction is a CallSite, the same way as is done with different functions.

[xbolva00]

llvm/lib/Analysis/ValueTracking.cpp

3389 ↗

(On Diff #147657)

Can you add a info message into assert then?
assert (CS && "...");

[Prazek]

• use getArgumentAliasingToReturnedPointer as it does not change behavior

llvm/lib/Analysis/ValueTracking.cpp

3389 ↗

(On Diff #147657)

sure, make sense

[hfinkel]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

435 ↗

(On Diff #147658)

Please explain here *how* this keeps this in sync. There's no obvious use of CaptureTracking here.

llvm/lib/Analysis/ValueTracking.cpp

3445 ↗

(On Diff #147658)

Same here. Please explain how this helps to keep tings in sync with CaptureTracking. There's some implicit contract here between these functions that we need to document explicitly.

[Prazek]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

435 ↗

(On Diff #147658)

I updated the comment, but I have a new idea how to make it better. I will refactor the list of intrinsic to some other function, to make it always in sync.

[Prazek]

• small refactor

llvm/lib/Analysis/ValueTracking.cpp

3399 ↗

(On Diff #147685)

Note that llvm.strip.invariant.group will be added in this patch
https://reviews.llvm.org/D47103

[Prazek]

fix name

[hfinkel]

llvm/lib/Analysis/BasicAliasAnalysis.cpp

435 ↗

(On Diff #147658)

That's good, but doesn't explain why keeping these in sync is necessary for correctness. To put it another way, please explain what does wrong if these are not in sync.

[Prazek]

• Add more comments

[hfinkel]

LGTM

This is still a bit convoluted, but I think that someone can now figure out what's going on from the comments. They also raise an interesting point of whether we should somehow separate out the capture-only-by-return case from the more-general case (although that's nothing to be addressed here).

llvm/trunk/include/llvm/Analysis/ValueTracking.h

class Value;
   /// it.
   bool getConstantStringInfo(const Value *V, StringRef &Str,
                              uint64_t Offset = 0, bool TrimAtNul = true);
 
   /// If we can compute the length of the string pointed to by the specified
   /// pointer, return 'len+1'.  If we can't, return 0.
   uint64_t GetStringLength(const Value *V, unsigned CharSize = 8);
 
+  /// This function returns call pointer argument that is considered the same by
+  /// aliasing rules. You CAN'T use it to replace one value with another.
+  const Value *getArgumentAliasingToReturnedPointer(ImmutableCallSite CS);
+  inline Value *getArgumentAliasingToReturnedPointer(CallSite CS) {
+    return const_cast<Value *>(
+        getArgumentAliasingToReturnedPointer(ImmutableCallSite(CS)));
+  }
+
+  // {launder,strip}.invariant.group returns pointer that aliases its argument,
+  // and it only captures pointer by returning it.
+  // These intrinsics are not marked as nocapture, because returning is
+  // considered as capture. The arguments are not marked as returned neither,
+  // because it would make it useless.
+  bool isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(
+      ImmutableCallSite CS);
+
   /// This method strips off any GEP address adjustments and pointer casts from
   /// the specified value, returning the original object being addressed. Note
   /// that the returned value has pointer type if the specified value does. If
   /// the MaxLookup value is non-zero, it limits the number of instructions to
   /// be stripped off.
   Value *GetUnderlyingObject(Value *V, const DataLayout &DL,
                              unsigned MaxLookup = 6);
   inline const Value *GetUnderlyingObject(const Value *V, const DataLayout &DL,

llvm/trunk/lib/Analysis/BasicAliasAnalysis.cpp

if (A->hasByValAttr() || A->hasNoAliasAttr())
       return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true);
 
   return false;
 }
 
 /// Returns true if the pointer is one which would have been considered an
 /// escape by isNonEscapingLocalObject.
 static bool isEscapeSource(const Value *V) {
-  if (auto CS = ImmutableCallSite(V)) {
-    // launder_invariant_group captures its argument only by returning it,
-    // so it might not be considered an escape by isNonEscapingLocalObject.
-    // Note that adding similar special cases for intrinsics in CaptureTracking
-    // requires handling them here too.
-    if (CS.getIntrinsicID() == Intrinsic::launder_invariant_group)
-      return false;
-
+  if (ImmutableCallSite(V))
     return true;
-  }
 
   if (isa<Argument>(V))
     return true;
 
   // The load case works because isNonEscapingLocalObject considers all
   // stores to be escapes (it passes true for the StoreCaptures argument
   // to PointerMayBeCaptured).
   if (isa<LoadInst>(V))
do {
     if (Op->getOpcode() == Instruction::BitCast ||
         Op->getOpcode() == Instruction::AddrSpaceCast) {
       V = Op->getOperand(0);
       continue;
     }
 
     const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op);
     if (!GEPOp) {
-      if (auto CS = ImmutableCallSite(V))
-        if (const Value *RV = CS.getReturnedArgOperand()) {
-          V = RV;
+      if (auto CS = ImmutableCallSite(V)) {
+        // Note: getArgumentAliasingToReturnedPointer keeps it in sync with
+        // CaptureTracking, which is needed for correctness.  This is because
+        // some intrinsics like launder.invariant.group returns pointers that
+        // are aliasing it's argument, which is known to CaptureTracking.
+        // If AliasAnalysis does not use the same information, it could assume
+        // that pointer returned from launder does not alias it's argument
+        // because launder could not return it if the pointer was not captured.
+        if (auto *RP = getArgumentAliasingToReturnedPointer(CS)) {
+          V = RP;
           continue;
         }
+      }
 
       // If it's not a GEP, hand it off to SimplifyInstruction to see if it
       // can come up with something. This matches what GetUnderlyingObject does.
       if (const Instruction *I = dyn_cast<Instruction>(V))
         // TODO: Get a DominatorTree and AssumptionCache and use them here
         // (these are both now available in this function, but this should be
         // updated when GetUnderlyingObject is updated). TLI should be
         // provided also.

llvm/trunk/lib/Analysis/CaptureTracking.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/OrderedBasicBlock.h"
+#include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 
 using namespace llvm;
 
while (!Worklist.empty()) {
     case Instruction::Invoke: {
       CallSite CS(I);
       // Not captured if the callee is readonly, doesn't return a copy through
       // its return value and doesn't unwind (a readonly function can leak bits
       // by throwing an exception or not depending on the input value).
       if (CS.onlyReadsMemory() && CS.doesNotThrow() && I->getType()->isVoidTy())
         break;
 
-      // launder.invariant.group only captures pointer by returning it,
-      // so the pointer wasn't captured if returned pointer is not captured.
-      // Note that adding similar special cases for intrinsics requires handling
-      // them in 'isEscapeSource' in BasicAA.
-      if (CS.getIntrinsicID() == Intrinsic::launder_invariant_group) {
+      // The pointer is not captured if returned pointer is not captured.
+      // NOTE: CaptureTracking users should not assume that only functions
+      // marked with nocapture do not capture. This means that places like
+      // GetUnderlyingObject in ValueTracking or DecomposeGEPExpression
+      // in BasicAA also need to know about this property.
+      if (isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(CS)) {
         AddUses(I);
         break;
       }
 
       // Volatile operations effectively capture the memory location that they
       // load and store to.
       if (auto *MI = dyn_cast<MemIntrinsic>(I))
         if (MI->isVolatile())

llvm/trunk/lib/Analysis/Loads.cpp

static bool isDereferenceableAndAlignedPointer(
   if (const GCRelocateInst *RelocateInst = dyn_cast<GCRelocateInst>(V))
     return isDereferenceableAndAlignedPointer(
         RelocateInst->getDerivedPtr(), Align, Size, DL, CtxI, DT, Visited);
 
   if (const AddrSpaceCastInst *ASC = dyn_cast<AddrSpaceCastInst>(V))
     return isDereferenceableAndAlignedPointer(ASC->getOperand(0), Align, Size,
                                               DL, CtxI, DT, Visited);
 
-  if (auto CS = ImmutableCallSite(V)) {
-    if (const Value *RV = CS.getReturnedArgOperand())
-      return isDereferenceableAndAlignedPointer(RV, Align, Size, DL, CtxI, DT,
+  if (auto CS = ImmutableCallSite(V))
+    if (auto *RP = getArgumentAliasingToReturnedPointer(CS))
+      return isDereferenceableAndAlignedPointer(RP, Align, Size, DL, CtxI, DT,
                                                 Visited);
-    if (CS.getIntrinsicID() == Intrinsic::launder_invariant_group)
-      return isDereferenceableAndAlignedPointer(CS->getOperand(0), Align, Size,
-                                                DL, CtxI, DT, Visited);
-  }
+
   // If we don't know, assume the worst.
   return false;
 }
 
 bool llvm::isDereferenceableAndAlignedPointer(const Value *V, unsigned Align,
                                               const APInt &Size,
                                               const DataLayout &DL,
                                               const Instruction *CtxI,

llvm/trunk/lib/Analysis/ValueTracking.cpp

if (V->getType()->isPointerTy()) {
     // A Load tagged with nonnull metadata is never null.
     if (const LoadInst *LI = dyn_cast<LoadInst>(V))
       if (LI->getMetadata(LLVMContext::MD_nonnull))
         return true;
 
     if (auto CS = ImmutableCallSite(V)) {
       if (CS.isReturnNonNull())
         return true;
-      if (CS.getIntrinsicID() == Intrinsic::ID::launder_invariant_group)
-        return isKnownNonZero(CS->getOperand(0), Depth + 1, Q);
+      if (const auto *RP = getArgumentAliasingToReturnedPointer(CS))
+        return isKnownNonZero(RP, Depth + 1, Q);
     }
   }
 
   // The remaining tests are all recursive, so bail out if we hit the limit.
   if (Depth++ >= MaxDepth)
     return false;
 
   // Check for recursive pointer simplifications.
uint64_t llvm::GetStringLength(const Value *V, unsigned CharSize) {
 
   SmallPtrSet<const PHINode*, 32> PHIs;
   uint64_t Len = GetStringLengthH(V, PHIs, CharSize);
   // If Len is ~0ULL, we had an infinite phi cycle: this is dead code, so return
   // an empty string as a length.
   return Len == ~0ULL ? 1 : Len;
 }
 
+const Value *llvm::getArgumentAliasingToReturnedPointer(ImmutableCallSite CS) {
+  assert(CS &&
+         "getArgumentAliasingToReturnedPointer only works on nonnull CallSite");
+  if (const Value *RV = CS.getReturnedArgOperand())
+    return RV;
+  // This can be used only as a aliasing property.
+  if (isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(CS))
+    return CS.getArgOperand(0);
+  return nullptr;
+}
+
+bool llvm::isIntrinsicReturningPointerAliasingArgumentWithoutCapturing(
+      ImmutableCallSite CS) {
+  return CS.getIntrinsicID() == Intrinsic::launder_invariant_group;
+}
+
 /// \p PN defines a loop-variant pointer to an object.  Check if the
 /// previous iteration of the loop was referring to the same object as \p PN.
 static bool isSameUnderlyingObjectInLoop(const PHINode *PN,
                                          const LoopInfo *LI) {
   // Find the loop-defined value.
   Loop *L = LI->getLoopFor(PN->getParent());
   if (PN->getNumIncomingValues() != 2)
     return true;
for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) {
     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
       if (GA->isInterposable())
         return V;
       V = GA->getAliasee();
     } else if (isa<AllocaInst>(V)) {
       // An alloca can't be further simplified.
       return V;
     } else {
-      if (auto CS = CallSite(V))
-        if (Value *RV = CS.getReturnedArgOperand()) {
-          V = RV;
+      if (auto CS = CallSite(V)) {
+        // Note: getArgumentAliasingToReturnedPointer keeps it in sync with
+        // CaptureTracking, which is needed for correctness.  This is because
+        // some intrinsics like launder.invariant.group returns pointers that
+        // are aliasing it's argument, which is known to CaptureTracking.
+        // If AliasAnalysis does not use the same information, it could assume
+        // that pointer returned from launder does not alias it's argument
+        // because launder could not return it if the pointer was not captured.
+        if (auto *RP = getArgumentAliasingToReturnedPointer(CS)) {
+          V = RP;
           continue;
         }
+      }
 
       // See if InstructionSimplify knows any relevant tricks.
       if (Instruction *I = dyn_cast<Instruction>(V))
         // TODO: Acquire a DominatorTree and AssumptionCache and use them.
         if (Value *Simplified = SimplifyInstruction(I, {DL, I})) {
           V = Simplified;
           continue;
         }

llvm/trunk/test/Analysis/ValueTracking/known-nonnull-at.ll

cont:
   ret i1 %null_check
 
 exc:
   %lp = landingpad { i8*, i32 }
     filter [0 x i8*] zeroinitializer
   unreachable
 }
 
+declare i8* @returningPtr(i8* returned %p)
+
+define i1 @nonnullReturnTest(i8* nonnull %x) {
+; CHECK-LABEL: @nonnullReturnTest(
+; CHECK-NEXT:    %x2 = call i8* @returningPtr(i8* %x)
+; CHECK-NEXT:    ret i1 false
+  %x2 = call i8* @returningPtr(i8* %x)
+  %null_check = icmp eq i8* %x2, null
+  ret i1 %null_check
+}
+
+define i1 @unknownReturnTest(i8* %x) {
+; CHECK-LABEL: @unknownReturnTest(
+; CHECK-NEXT:    %x2 = call i8* @returningPtr(i8* %x)
+; CHECK-NEXT:    %null_check = icmp eq i8* %x2, null
+; CHECK-NEXT:    ret i1 %null_check
+  %x2 = call i8* @returningPtr(i8* %x)
+  %null_check = icmp eq i8* %x2, null
+  ret i1 %null_check
+}
+

llvm/trunk/test/Transforms/Inline/launder.invariant.group.ll

+; RUN: opt -S -inline < %s | FileCheck %s
+; RUN: opt -S -O3 < %s | FileCheck %s
+
+; This test checks if value returned from the launder is considered aliasing
+; with its argument.  Due to bug caused by handling launder in capture tracking
+; sometimes it would be considered noalias.
+
+%struct.A = type <{ i32 (...)**, i32, [4 x i8] }>
+
+; CHECK: define i32 @bar(%struct.A* noalias
+define i32 @bar(%struct.A* noalias) {
+; CHECK-NOT: noalias
+  %2 = bitcast %struct.A* %0 to i8*
+  %3 = call i8* @llvm.launder.invariant.group.p0i8(i8* %2)
+  %4 = getelementptr inbounds i8, i8* %3, i64 8
+  %5 = bitcast i8* %4 to i32*
+  store i32 42, i32* %5, align 8
+  %6 = getelementptr inbounds %struct.A, %struct.A* %0, i64 0, i32 1
+  %7 = load i32, i32* %6, align 8
+  ret i32 %7
+}
+
+; CHECK-LABEL: define i32 @foo(%struct.A* noalias
+define i32 @foo(%struct.A* noalias)  {
+  ; CHECK-NOT: call i32 @bar(
+  ; CHECK-NOT: noalias
+  %2 = tail call i32 @bar(%struct.A* %0)
+  ret i32 %2
+}
+
+declare i8* @llvm.launder.invariant.group.p0i8(i8*)