returned - BasicAA should look through functions with returned arguments

[hfinkel]

Summary

Motivated by the work on the llvm.noalias intrinsic, teach BasicAA to look through returned-argument functions when answering queries. This is essential so that we don't loose all other AA information when supplementing with llvm.noalias.

[hfinkel]

Also, the ability to optionally strip llvm.noalias calls as pointer casts added here is also used in several later patches.

[• dberlin]

include/llvm/IR/Value.h

404

So, is there actually a place you plan on not passing true here, or are you just trying to keep existing logic where you haven't explicitly modified it?

(Because i am having a bit of trouble seeing where you would want to pass false. At the point you are stripping, why is noalias more magical to not strip than anything else that can appear here?)

[hfinkel]

include/llvm/IR/Value.h

404

In some sense both, but I also wanted to keep the default not to strip them.

At least in theory, looking through casts and stripping llvm.noalias calls could lead to rewriting the pointer in terms of some underlying object (thus removing the aliasing information) -- SROA might do this for example -- and so I thought it would be easier to vet specific uses that we know won't do this.

Generically, I thought that "I added restrict and my code slowed down" will be easier to correct than "I added restrict and my code did not speed up as it should have".

We could certainly change the default (and thus remove the need for several of the patches in this series ;) ). I don't have a strong opinion.

[• dberlin]

include/llvm/IR/Value.h

404

After thinking about this a lot, i'm strongly of the opinion we should just change the default. I think anything else is likely to create a mess :)

In fact, i'd go further, and say this shouldn't be a parameter at all. If someone wants a function that stops at noalias, they should write a new strip function. I don't think noalias is special enough, and can't think of a real use case, for wanting to stop there.

[reames]

Resigning as a reviewer to get a very stale review off my list of blocking tasks in phabricator. Please reopen when desired.

[hfinkel]

Rebased. As Danny requested, the Boolean parameters to stripPointerCasts have been removed; they now always look through the noalias intrinsics. This means that we need to prevent InstCombine and friends from removing the noalias intrinsics from the pointer-value use-def chains some other way. As a result, this particular patch is now much simpler.

[majnemer]

LGTM

lib/IR/Value.cpp

418

auto *I

477

Ditto.

[hfinkel]

Changed from being specific to llvm.noalias to applying to all returned-argument functions.

[majnemer]

Nice, thanks!

include/llvm/IR/Value.h

public:
 
   /// \brief Return true if there is metadata referencing this value.
   bool isUsedByMetadata() const { return NameAndIsUsedByMD.getInt(); }
 
   /// \brief Strip off pointer casts, all-zero GEPs, and aliases.
   ///
   /// Returns the original uncasted value.  If this is called on a non-pointer
   /// value, it returns 'this'.
-  Value *stripPointerCasts();
-  const Value *stripPointerCasts() const {
-    return const_cast<Value*>(this)->stripPointerCasts();
+  Value *stripPointerCasts(bool LookThroughNoAlias = false);
+  const Value *stripPointerCasts(bool LookThroughNoAlias = false) const {
+    return const_cast<Value*>(this)->stripPointerCasts(LookThroughNoAlias);
   }
 
   /// \brief Strip off pointer casts and all-zero GEPs.
   ///
   /// Returns the original uncasted value.  If this is called on a non-pointer
   /// value, it returns 'this'.
-  Value *stripPointerCastsNoFollowAliases();
-  const Value *stripPointerCastsNoFollowAliases() const {
-    return const_cast<Value*>(this)->stripPointerCastsNoFollowAliases();
+  Value *stripPointerCastsNoFollowAliases(bool LookThroughNoAlias = false);
+  const Value *stripPointerCastsNoFollowAliases(
+                 bool LookThroughNoAlias = false) const {
+    return const_cast<Value*>(this)->
+      stripPointerCastsNoFollowAliases(LookThroughNoAlias);
   }
 
   /// \brief Strip off pointer casts and all-constant inbounds GEPs.
   ///
   /// Returns the original pointer value.  If this is called on a non-pointer
   /// value, it returns 'this'.
-  Value *stripInBoundsConstantOffsets();
-  const Value *stripInBoundsConstantOffsets() const {
-    return const_cast<Value*>(this)->stripInBoundsConstantOffsets();
+  Value *stripInBoundsConstantOffsets(bool LookThroughNoAlias = false);
+  const Value *stripInBoundsConstantOffsets(
+                 bool LookThroughNoAlias = false) const {
+    return const_cast<Value*>(this)->
+      stripInBoundsConstantOffsets(LookThroughNoAlias);
   }
 
   /// \brief Accumulate offsets from \a stripInBoundsConstantOffsets().
   ///
   /// Stores the resulting constant offset stripped into the APInt provided.
   /// The provided APInt will be extended or truncated as needed to be the
   /// correct bitwidth for an offset of this pointer type.
   ///
   /// If this is called on a non-pointer value, it returns 'this'.
   Value *stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL,
-                                                   APInt &Offset);
+           APInt &Offset, bool LookThroughNoAlias = false);
   const Value *stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL,
-                                                         APInt &Offset) const {
+                 APInt &Offset, bool LookThroughNoAlias = false) const {
     return const_cast<Value *>(this)
-        ->stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
+        ->stripAndAccumulateInBoundsConstantOffsets(DL, Offset,
+                                                    LookThroughNoAlias);
   }
 
   /// \brief Strip off pointer casts and inbounds GEPs.
   ///
   /// Returns the original pointer value.  If this is called on a non-pointer
   /// value, it returns 'this'.
-  Value *stripInBoundsOffsets();
-  const Value *stripInBoundsOffsets() const {
-    return const_cast<Value*>(this)->stripInBoundsOffsets();
+  Value *stripInBoundsOffsets(bool LookThroughNoAlias = false);
+  const Value *stripInBoundsOffsets(bool LookThroughNoAlias = false) const {
+    return const_cast<Value*>(this)->stripInBoundsOffsets(LookThroughNoAlias);
   }
 
   /// \brief Translate PHI node to its predecessor from the given basic block.
   ///
   /// If this value is a PHI node with CurBB as its parent, return the value in
   /// the PHI node corresponding to PredBB.  If not, return ourself.  This is
   /// useful if you want to know the value something has in a predecessor
   /// block.

lib/Analysis/BasicAliasAnalysis.cpp

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 (const IntrinsicInst *I = dyn_cast<IntrinsicInst>(V))
+        if (I->getIntrinsicID() == Intrinsic::noalias) {
+          V = I->getOperand(0);
+          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.
         if (const Value *Simplified =

 
 /// \brief Provide ad-hoc rules to disambiguate accesses through two GEP
 /// operators, both having the exact same pointer operand.
 static AliasAnalysis::AliasResult
 aliasSameBasePointerGEPs(const GEPOperator *GEP1, uint64_t V1Size,
                          const GEPOperator *GEP2, uint64_t V2Size,
                          const DataLayout &DL) {
 
-  assert(GEP1->getPointerOperand() == GEP2->getPointerOperand() &&
+  assert(GEP1->getPointerOperand()->stripPointerCasts(true) ==
+         GEP2->getPointerOperand()->stripPointerCasts(true) &&
+         GEP1->getPointerOperand()->getType() ==
+         GEP2->getPointerOperand()->getType() &&
          "Expected GEPs with the same pointer operand");
 
   // Try to determine whether GEP1 and GEP2 index through arrays, into structs,
   // such that the struct field accesses provably cannot alias.
   // We also need at least two indices (the pointer, and the struct field).
   if (GEP1->getNumIndices() != GEP2->getNumIndices() ||
       GEP1->getNumIndices() < 2)
     return AliasAnalysis::MayAlias;
if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) {
       assert(!DL &&
              "DecomposeGEPExpression and GetUnderlyingObject disagree!");
       return MayAlias;
     }
 
     // If we know the two GEPs are based off of the exact same pointer (and not
     // just the same underlying object), see if that tells us anything about
     // the resulting pointers.
-    if (DL && GEP1->getPointerOperand() == GEP2->getPointerOperand()) {
-      AliasResult R = aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, *DL);
+    if (DL && GEP1->getPointerOperand()->stripPointerCasts(true) ==
+              GEP2->getPointerOperand()->stripPointerCasts(true) &&
+              GEP1->getPointerOperand()->getType() ==
+              GEP2->getPointerOperand()->getType()) {
+      AliasResult R =
+        aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, *DL);
       // If we couldn't find anything interesting, don't abandon just yet.
       if (R != MayAlias)
         return R;
     }
 
     // If the max search depth is reached the result is undefined
     if (GEP2MaxLookupReached || GEP1MaxLookupReached)
       return MayAlias;
BasicAliasAnalysis::aliasCheck(const Value *V1, uint64_t V1Size,
                                const Value *V2, uint64_t V2Size,
                                AAMDNodes V2AAInfo) {
   // If either of the memory references is empty, it doesn't matter what the
   // pointer values are.
   if (V1Size == 0 || V2Size == 0)
     return NoAlias;
 
   // Strip off any casts if they exist.
-  V1 = V1->stripPointerCasts();
-  V2 = V2->stripPointerCasts();
+  V1 = V1->stripPointerCasts(/*LookThroughNoAlias*/true);
+  V2 = V2->stripPointerCasts(/*LookThroughNoAlias*/true);
 
   // Are we checking for alias of the same value?
   // Because we look 'through' phi nodes we could look at "Value" pointers from
   // different iterations. We must therefore make sure that this is not the
   // case. The function isValueEqualInPotentialCycles ensures that this cannot
   // happen by looking at the visited phi nodes and making sure they cannot
   // reach the value.
   if (isValueEqualInPotentialCycles(V1, V2))

lib/Analysis/ValueTracking.cpp

for (unsigned Count = 0; MaxLookup == 0 || Count < MaxLookup; ++Count) {
     } else if (Operator::getOpcode(V) == Instruction::BitCast ||
                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
       V = cast<Operator>(V)->getOperand(0);
     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
       if (GA->mayBeOverridden())
         return V;
       V = GA->getAliasee();
     } else {
+      if (IntrinsicInst *I = dyn_cast<IntrinsicInst>(V))
+        if (I->getIntrinsicID() == Intrinsic::noalias) {
+          V = I->getOperand(0);
+          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, nullptr)) {
           V = Simplified;
           continue;
         }
 

lib/IR/Value.cpp

 enum PointerStripKind {
   PSK_ZeroIndices,
   PSK_ZeroIndicesAndAliases,
   PSK_InBoundsConstantIndices,
   PSK_InBounds
 };
 
 template <PointerStripKind StripKind>
-static Value *stripPointerCastsAndOffsets(Value *V) {
+static Value *stripPointerCastsAndOffsets(Value *V, bool LookThroughNoAlias) {
   if (!V->getType()->isPointerTy())
     return V;
 
   // Even though we don't look through PHI nodes, we could be called on an
   // instruction in an unreachable block, which may be on a cycle.
   SmallPtrSet<Value *, 4> Visited;
 
   Visited.insert(V);
do {
     } else if (Operator::getOpcode(V) == Instruction::BitCast ||
                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
       V = cast<Operator>(V)->getOperand(0);
     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
       if (StripKind == PSK_ZeroIndices || GA->mayBeOverridden())
         return V;
       V = GA->getAliasee();
     } else {
+      if (LookThroughNoAlias)
+        if (IntrinsicInst *I = dyn_cast<IntrinsicInst>(V))
+          if (I->getIntrinsicID() == Intrinsic::noalias) {
+            V = I->getOperand(0);
+            continue;
+          }
+
       return V;
     }
     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
   } while (Visited.insert(V).second);
 
   return V;
 }
 } // namespace
 
-Value *Value::stripPointerCasts() {
-  return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndAliases>(this);
+Value *Value::stripPointerCasts(bool LookThroughNoAlias) {
+  return stripPointerCastsAndOffsets<PSK_ZeroIndicesAndAliases>(
+           this, LookThroughNoAlias);
 }
 
-Value *Value::stripPointerCastsNoFollowAliases() {
-  return stripPointerCastsAndOffsets<PSK_ZeroIndices>(this);
+Value *Value::stripPointerCastsNoFollowAliases(bool LookThroughNoAlias) {
+  return stripPointerCastsAndOffsets<PSK_ZeroIndices>(this, LookThroughNoAlias);
 }
 
-Value *Value::stripInBoundsConstantOffsets() {
-  return stripPointerCastsAndOffsets<PSK_InBoundsConstantIndices>(this);
+Value *Value::stripInBoundsConstantOffsets(bool LookThroughNoAlias) {
+  return stripPointerCastsAndOffsets<PSK_InBoundsConstantIndices>(
+           this, LookThroughNoAlias);
 }
 
 Value *Value::stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL,
-                                                        APInt &Offset) {
+                APInt &Offset, bool LookThroughNoAlias) {
   if (!getType()->isPointerTy())
     return this;
 
   assert(Offset.getBitWidth() == DL.getPointerSizeInBits(cast<PointerType>(
                                      getType())->getAddressSpace()) &&
          "The offset must have exactly as many bits as our pointer.");
 
   // Even though we don't look through PHI nodes, we could be called on an
if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
       Offset = GEPOffset;
       V = GEP->getPointerOperand();
     } else if (Operator::getOpcode(V) == Instruction::BitCast ||
                Operator::getOpcode(V) == Instruction::AddrSpaceCast) {
       V = cast<Operator>(V)->getOperand(0);
     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
       V = GA->getAliasee();
     } else {
+      if (LookThroughNoAlias)
+        if (IntrinsicInst *I = dyn_cast<IntrinsicInst>(V))
+          if (I->getIntrinsicID() == Intrinsic::noalias) {
+            V = I->getOperand(0);
+            continue;
+          }
+
       return V;
     }
     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
   } while (Visited.insert(V).second);
 
   return V;
 }
 
-Value *Value::stripInBoundsOffsets() {
-  return stripPointerCastsAndOffsets<PSK_InBounds>(this);
+Value *Value::stripInBoundsOffsets(bool LookThroughNoAlias) {
+  return stripPointerCastsAndOffsets<PSK_InBounds>(this, LookThroughNoAlias);
 }
 
 Value *Value::DoPHITranslation(const BasicBlock *CurBB,
                                const BasicBlock *PredBB) {
   PHINode *PN = dyn_cast<PHINode>(this);
   if (PN && PN->getParent() == CurBB)
     return PN->getIncomingValueForBlock(PredBB);
   return this;

test/Analysis/BasicAA/noalias.ll

+; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+%struct = type { i32, i32, i32 }
+
+; CHECK-LABEL: test_simple
+
+; CHECK-DAG: MustAlias: %struct* %st, %struct* %sta
+
+; CHECK-DAG: PartialAlias: %struct* %st, i32* %x
+; CHECK-DAG: PartialAlias: %struct* %st, i32* %y
+; CHECK-DAG: PartialAlias: %struct* %st, i32* %z
+
+; CHECK-DAG: NoAlias: i32* %x, i32* %y
+; CHECK-DAG: NoAlias: i32* %x, i32* %z
+; CHECK-DAG: NoAlias: i32* %y, i32* %z
+
+; CHECK-DAG: PartialAlias: %struct* %st, %struct* %y_12
+; CHECK-DAG: PartialAlias: %struct* %y_12, i32* %x
+; CHECK-DAG: PartialAlias: i32* %x, i80* %y_10
+
+; CHECK-DAG: PartialAlias: %struct* %st, i64* %y_8
+; CHECK-DAG: PartialAlias: i32* %z, i64* %y_8
+; CHECK-DAG: NoAlias: i32* %x, i64* %y_8
+
+; CHECK-DAG: MustAlias: %struct* %y_12, i32* %y
+; CHECK-DAG: MustAlias: i32* %y, i64* %y_8
+; CHECK-DAG: MustAlias: i32* %y, i80* %y_10
+
+define void @test_simple(%struct* %st, i64 %i, i64 %j, i64 %k) {
+  %x = getelementptr %struct, %struct* %st, i64 %i, i32 0
+  %y = getelementptr %struct, %struct* %st, i64 %j, i32 1
+  %sta = call %struct* @llvm.noalias.p0struct(%struct* %st, metadata !1)
+  %z = getelementptr %struct, %struct* %sta, i64 %k, i32 2
+  %y_12 = bitcast i32* %y to %struct*
+  %y_10 = bitcast i32* %y to i80*
+  %ya = call i32* @llvm.noalias.p0i32(i32* %y, metadata !1)
+  %y_8 = bitcast i32* %ya to i64*
+  ret void
+}
+
+declare i32* @llvm.noalias.p0i32(i32*, metadata) nounwind
+declare %struct* @llvm.noalias.p0struct(%struct*, metadata) nounwind
+
+!0 = !{!0, !"some domain"}
+!1 = !{!1, !0, !"some scope"}
+