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 ↗

(On Diff #24717)

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 ↗

(On Diff #24717)

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 ↗

(On Diff #24717)

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

467

auto *I

522

Ditto.

[hfinkel]

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

[majnemer]

Nice, thanks!

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 (auto CS = ImmutableCallSite(V))
+        if (const Value *RV = CS.getReturnedArgOperand()) {
+          V = RV;
+          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 =

 /// Provide ad-hoc rules to disambiguate accesses through two GEP operators,
 /// both having the exact same pointer operand.
 static 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() ==
+         GEP2->getPointerOperand()->stripPointerCasts() &&
+         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 MayAlias;
if (BaseAlias != MustAlias)
       return BaseAlias;
 
     // Otherwise, we have a MustAlias.  Since the base pointers alias each other
     // exactly, see if the computed offset from the common pointer tells us
     // about the relation of the resulting pointer.
     // 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 (GEP1->getPointerOperand() == GEP2->getPointerOperand()) {
+    if (GEP1->getPointerOperand()->stripPointerCasts() ==
+        GEP2->getPointerOperand()->stripPointerCasts() &&
+        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)

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->isInterposable())
         return V;
       V = GA->getAliasee();
     } else {
+      if (auto CS = CallSite(V))
+        if (Value *RV = CS.getReturnedArgOperand()) {
+          V = RV;
+          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

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->isInterposable())
         return V;
       V = GA->getAliasee();
     } else {
+      if (auto CS = CallSite(V))
+        if (Value *RV = CS.getReturnedArgOperand()) {
+          V = RV;
+          continue;
+        }
+
       return V;
     }
     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
   } while (Visited.insert(V).second);
 
   return V;
 }
 } // end anonymous namespace
if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) {
         return V;
       Offset = GEPOffset;
       V = GEP->getPointerOperand();
     } else if (Operator::getOpcode(V) == Instruction::BitCast) {
       V = cast<Operator>(V)->getOperand(0);
     } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
       V = GA->getAliasee();
     } else {
+      if (auto CS = CallSite(V))
+        if (Value *RV = CS.getReturnedArgOperand()) {
+          V = RV;
+          continue;
+        }
+
       return V;
     }
     assert(V->getType()->isPointerTy() && "Unexpected operand type!");
   } while (Visited.insert(V).second);
 
   return V;
 }
 

test/Analysis/BasicAA/returned.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* @func2(%struct* %st)
+  %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* @func1(i32* %y)
+  %y_8 = bitcast i32* %ya to i64*
+  ret void
+}
+
+declare i32* @func1(i32* returned) nounwind
+declare %struct* @func2(%struct* returned) nounwind
+