[BasicAA] Improve scalable vector handling

[nikic]

Summary

Currently, DecomposeGEP bails out on the whole decomposition if it encounters a scalable GEP type anywhere. However, it is fine to to still analyze other GEPs that we look through before hitting the scalable GEP. This does means that the decomposed GEP base is no longer required to be the same as the underlying object. However, I don't believe this property is necessary for correctness anymore.

This allows us to compute slightly more precise aliasing results for GEP chains containing scalable vectors, though my primary interest here is simplifying the code.

[fhahn]

This makes sense to me. Are there non-scalable-vector cases where UnderlyingValue[1-2] -> DecompGEP[1-2].Base shows benefits?

[nikic]

In D110511#3047790, @fhahn wrote:

This makes sense to me. Are there non-scalable-vector cases where UnderlyingValue[1-2] -> DecompGEP[1-2].Base shows benefits?

For non-scalable vectors DecompGEP.Base and UnderlyingValue will be the same (at least for now), so this change should be NFC for the non-scalable case.

[nikic]

Rebase

[fhahn]

In D110511#3047826, @nikic wrote:

In D110511#3047790, @fhahn wrote:

This makes sense to me. Are there non-scalable-vector cases where UnderlyingValue[1-2] -> DecompGEP[1-2].Base shows benefits?

For non-scalable vectors DecompGEP.Base and UnderlyingValue will be the same (at least for now), so this change should be NFC for the non-scalable case.

Sounds good, LGTM!

[jeroen.dobbelaere]

In D110511#3047790, @fhahn wrote:

This makes sense to me. Are there non-scalable-vector cases where UnderlyingValue[1-2] -> DecompGEP[1-2].Base shows benefits?

Btw, for the full restrict patches, this is also helpful.

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 
 /// Cutoff after which to stop analysing a set of phi nodes potentially involved
 /// in a cycle. Because we are analysing 'through' phi nodes, we need to be
 /// careful with value equivalence. We use reachability to make sure a value
 /// cannot be involved in a cycle.
 const unsigned MaxNumPhiBBsValueReachabilityCheck = 20;
 
 // The max limit of the search depth in DecomposeGEPExpression() and
-// getUnderlyingObject(), both functions need to use the same search
-// depth otherwise the algorithm in aliasGEP will assert.
+// getUnderlyingObject().
 static const unsigned MaxLookupSearchDepth = 6;
 
 bool BasicAAResult::invalidate(Function &Fn, const PreservedAnalyses &PA,
                                FunctionAnalysisManager::Invalidator &Inv) {
   // We don't care if this analysis itself is preserved, it has no state. But
   // we need to check that the analyses it depends on have been. Note that we
   // may be created without handles to some analyses and in that case don't
   // depend on them.

 // constant offsets, and variable scaled indices.
 struct BasicAAResult::DecomposedGEP {
   // Base pointer of the GEP
   const Value *Base;
   // Total constant offset from base.
   APInt Offset;
   // Scaled variable (non-constant) indices.
   SmallVector<VariableGEPIndex, 4> VarIndices;
-  // Is GEP index scale compile-time constant.
-  bool HasCompileTimeConstantScale;
   // Are all operations inbounds GEPs or non-indexing operations?
   // (None iff expression doesn't involve any geps)
   Optional<bool> InBounds;
 
   void dump() const {
     print(dbgs());
     dbgs() << "\n";
   }
   void print(raw_ostream &OS) const {
     OS << "(DecomposedGEP Base=" << Base->getName()
        << ", Offset=" << Offset
        << ", VarIndices=[";
     for (size_t i = 0; i < VarIndices.size(); i++) {
       if (i != 0)
         OS << ", ";
       VarIndices[i].print(OS);
     }
-    OS << "], HasCompileTimeConstantScale=" << HasCompileTimeConstantScale
-       << ")";
+    OS << "])";
   }
 };
 
 
 /// If V is a symbolic pointer expression, decompose it into a base pointer
 /// with a constant offset and a number of scaled symbolic offsets.
 ///
 /// The scaled symbolic offsets (represented by pairs of a Value* and a scale
 /// in the VarIndices vector) are Value*'s that are known to be scaled by the
 /// specified amount, but which may have other unrepresented high bits. As
 /// such, the gep cannot necessarily be reconstructed from its decomposed form.
-///
-/// This function is capable of analyzing everything that getUnderlyingObject
-/// can look through. To be able to do that getUnderlyingObject and
-/// DecomposeGEPExpression must use the same search depth
-/// (MaxLookupSearchDepth).
 BasicAAResult::DecomposedGEP
 BasicAAResult::DecomposeGEPExpression(const Value *V, const DataLayout &DL,
                                       AssumptionCache *AC, DominatorTree *DT) {
   // Limit recursion depth to limit compile time in crazy cases.
   unsigned MaxLookup = MaxLookupSearchDepth;
   SearchTimes++;
   const Instruction *CxtI = dyn_cast<Instruction>(V);
 
   unsigned MaxPointerSize = DL.getMaxPointerSizeInBits();
   DecomposedGEP Decomposed;
   Decomposed.Offset = APInt(MaxPointerSize, 0);
-  Decomposed.HasCompileTimeConstantScale = true;
   do {
     // See if this is a bitcast or GEP.
     const Operator *Op = dyn_cast<Operator>(V);
     if (!Op) {
       // The only non-operator case we can handle are GlobalAliases.
       if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
         if (!GA->isInterposable()) {
           V = GA->getAliasee();
else if (!GEPOp->isInBounds())
       Decomposed.InBounds = false;
 
     assert(GEPOp->getSourceElementType()->isSized() && "GEP must be sized");
 
     // Don't attempt to analyze GEPs if index scale is not a compile-time
     // constant.
     if (isa<ScalableVectorType>(GEPOp->getSourceElementType())) {
       Decomposed.Base = V;
-      Decomposed.HasCompileTimeConstantScale = false;
       return Decomposed;
     }
 
     unsigned AS = GEPOp->getPointerAddressSpace();
     // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices.
     gep_type_iterator GTI = gep_type_begin(GEPOp);
     unsigned PointerSize = DL.getPointerSizeInBits(AS);
     // Assume all GEP operands are constants until proven otherwise.
AliasResult BaseAlias = getBestAAResults().alias(
         MemoryLocation::getBeforeOrAfter(UnderlyingV2), AAQI);
     return BaseAlias == AliasResult::NoAlias ? AliasResult::NoAlias
                                              : AliasResult::MayAlias;
   }
 
   DecomposedGEP DecompGEP1 = DecomposeGEPExpression(GEP1, DL, &AC, DT);
   DecomposedGEP DecompGEP2 = DecomposeGEPExpression(V2, DL, &AC, DT);
 
-  // Don't attempt to analyze the decomposed GEP if index scale is not a
-  // compile-time constant.
-  if (!DecompGEP1.HasCompileTimeConstantScale ||
-      !DecompGEP2.HasCompileTimeConstantScale)
+  // Bail if we were not able to decompose anything.
+  if (DecompGEP1.Base == GEP1 && DecompGEP2.Base == V2)
     return AliasResult::MayAlias;
 
-  assert(DecompGEP1.Base == UnderlyingV1 && DecompGEP2.Base == UnderlyingV2 &&
-         "DecomposeGEPExpression returned a result different from "
-         "getUnderlyingObject");
-
   // Subtract the GEP2 pointer from the GEP1 pointer to find out their
   // symbolic difference.
   subtractDecomposedGEPs(DecompGEP1, DecompGEP2);
 
   // If an inbounds GEP would have to start from an out of bounds address
   // for the two to alias, then we can assume noalias.
   if (*DecompGEP1.InBounds && DecompGEP1.VarIndices.empty() &&
       V2Size.hasValue() && DecompGEP1.Offset.sge(V2Size.getValue()) &&

llvm/test/Analysis/BasicAA/vscale.ll

 ; getelementptr recursion
 
 ; CHECK-LABEL: gep_recursion_level_1
 ; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %p, i32* %a
 ; CHECK-DAG:  MayAlias:     i32* %a, i32* %gep
 ; CHECK-DAG:  MayAlias:     i32* %a, i32* %gep_rec_1
 ; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %p, i32* %gep
 ; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %p, i32* %gep_rec_1
-; CHECK-DAG:  MayAlias:     i32* %gep, i32* %gep_rec_1
+; CHECK-DAG:  NoAlias:      i32* %gep, i32* %gep_rec_1
 define void @gep_recursion_level_1(i32* %a, <vscale x 4 x i32>* %p) {
   %gep = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %p, i64 1, i64 2
   %gep_rec_1 = getelementptr i32, i32* %gep, i64 1
   ret void
 }
 
 ; CHECK-LABEL: gep_recursion_level_1_bitcast
 ; CHECK-DAG:  MustAlias:    <vscale x 4 x i32>* %p, i32* %a
 ; CHECK-DAG:  MayAlias:     i32* %a, i32* %gep
 ; CHECK-DAG:  MayAlias:     i32* %a, i32* %gep_rec_1
 ; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %p, i32* %gep
 ; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %p, i32* %gep_rec_1
-; CHECK-DAG:  MayAlias:     i32* %gep, i32* %gep_rec_1
+; CHECK-DAG:  NoAlias:      i32* %gep, i32* %gep_rec_1
 define void @gep_recursion_level_1_bitcast(i32* %a) {
   %p = bitcast i32* %a to <vscale x 4 x i32>*
   %gep = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %p, i64 1, i64 2
   %gep_rec_1 = getelementptr i32, i32* %gep, i64 1
   ret void
 }
 
 ; CHECK-LABEL: gep_recursion_level_2
 ; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %p, i32* %a
 ; CHECK-DAG:  MayAlias:     i32* %a, i32* %gep
 ; CHECK-DAG:  MayAlias:     i32* %a, i32* %gep_rec_1
 ; CHECK-DAG:  MayAlias:     i32* %a, i32* %gep_rec_2
 ; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %p, i32* %gep
 ; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %p, i32* %gep_rec_1
 ; CHECK-DAG:  MayAlias:     <vscale x 4 x i32>* %p, i32* %gep_rec_2
-; CHECK-DAG:  MayAlias:     i32* %gep, i32* %gep_rec_1
-; CHECK-DAG:  MayAlias:     i32* %gep, i32* %gep_rec_2
-; CHECK-DAG:  MayAlias:     i32* %gep_rec_1, i32* %gep_rec_2
+; CHECK-DAG:  NoAlias:      i32* %gep, i32* %gep_rec_1
+; CHECK-DAG:  NoAlias:      i32* %gep, i32* %gep_rec_2
+; CHECK-DAG:  NoAlias:      i32* %gep_rec_1, i32* %gep_rec_2
 define void @gep_recursion_level_2(i32* %a, <vscale x 4 x i32>* %p) {
   %gep = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %p, i64 1, i64 2
   %gep_rec_1 = getelementptr i32, i32* %gep, i64 1
   %gep_rec_2 = getelementptr i32, i32* %gep_rec_1, i64 1
   ret void
 }
 
 ; CHECK-LABEL: gep_recursion_max_lookup_depth_reached
 ; CHECK-DAG: MayAlias:     <vscale x 4 x i32>* %p, i32* %a
 ; CHECK-DAG: MayAlias:     i32* %a, i32* %gep
 ; CHECK-DAG: MayAlias:     i32* %a, i32* %gep_rec_1
 ; CHECK-DAG: MayAlias:     i32* %a, i32* %gep_rec_2
 ; CHECK-DAG: MayAlias:     i32* %a, i32* %gep_rec_3
 ; CHECK-DAG: MayAlias:     i32* %a, i32* %gep_rec_4
 ; CHECK-DAG: MayAlias:     i32* %a, i32* %gep_rec_5
 ; CHECK-DAG: MayAlias:     i32* %a, i32* %gep_rec_6
 ; CHECK-DAG: MayAlias:     <vscale x 4 x i32>* %p, i32* %gep
 ; CHECK-DAG: MayAlias:     <vscale x 4 x i32>* %p, i32* %gep_rec_1
 ; CHECK-DAG: MayAlias:     <vscale x 4 x i32>* %p, i32* %gep_rec_2
 ; CHECK-DAG: MayAlias:     <vscale x 4 x i32>* %p, i32* %gep_rec_3
 ; CHECK-DAG: MayAlias:     <vscale x 4 x i32>* %p, i32* %gep_rec_4
 ; CHECK-DAG: MayAlias:     <vscale x 4 x i32>* %p, i32* %gep_rec_5
 ; CHECK-DAG: MayAlias:     <vscale x 4 x i32>* %p, i32* %gep_rec_6
-; CHECK-DAG: MayAlias:     i32* %gep, i32* %gep_rec_1
-; CHECK-DAG: MayAlias:     i32* %gep, i32* %gep_rec_2
-; CHECK-DAG: MayAlias:     i32* %gep, i32* %gep_rec_3
-; CHECK-DAG: MayAlias:     i32* %gep, i32* %gep_rec_4
-; CHECK-DAG: MayAlias:     i32* %gep, i32* %gep_rec_5
-; CHECK-DAG: MayAlias:     i32* %gep, i32* %gep_rec_6
-; CHECK-DAG: MayAlias:     i32* %gep_rec_1, i32* %gep_rec_2
-; CHECK-DAG: MayAlias:     i32* %gep_rec_1, i32* %gep_rec_3
-; CHECK-DAG: MayAlias:     i32* %gep_rec_1, i32* %gep_rec_4
-; CHECK-DAG: MayAlias:     i32* %gep_rec_1, i32* %gep_rec_5
-; CHECK-DAG: MayAlias:     i32* %gep_rec_1, i32* %gep_rec_6
-; CHECK-DAG: MayAlias:     i32* %gep_rec_2, i32* %gep_rec_3
-; CHECK-DAG: MayAlias:     i32* %gep_rec_2, i32* %gep_rec_4
-; CHECK-DAG: MayAlias:     i32* %gep_rec_2, i32* %gep_rec_5
-; CHECK-DAG: MayAlias:     i32* %gep_rec_2, i32* %gep_rec_6
-; CHECK-DAG: MayAlias:     i32* %gep_rec_3, i32* %gep_rec_4
-; CHECK-DAG: MayAlias:     i32* %gep_rec_3, i32* %gep_rec_5
-; CHECK-DAG: MayAlias:     i32* %gep_rec_3, i32* %gep_rec_6
-; CHECK-DAG: MayAlias:     i32* %gep_rec_4, i32* %gep_rec_5
-; CHECK-DAG: MayAlias:     i32* %gep_rec_4, i32* %gep_rec_6
-; CHECK-DAG: MayAlias:     i32* %gep_rec_5, i32* %gep_rec_6
+; CHECK-DAG: NoAlias:      i32* %gep, i32* %gep_rec_1
+; CHECK-DAG: NoAlias:      i32* %gep, i32* %gep_rec_2
+; CHECK-DAG: NoAlias:      i32* %gep, i32* %gep_rec_3
+; CHECK-DAG: NoAlias:      i32* %gep, i32* %gep_rec_4
+; CHECK-DAG: NoAlias:      i32* %gep, i32* %gep_rec_5
+; CHECK-DAG: NoAlias:      i32* %gep, i32* %gep_rec_6
+; CHECK-DAG: NoAlias:      i32* %gep_rec_1, i32* %gep_rec_2
+; CHECK-DAG: NoAlias:      i32* %gep_rec_1, i32* %gep_rec_3
+; CHECK-DAG: NoAlias:      i32* %gep_rec_1, i32* %gep_rec_4
+; CHECK-DAG: NoAlias:      i32* %gep_rec_1, i32* %gep_rec_5
+; CHECK-DAG: NoAlias:      i32* %gep_rec_1, i32* %gep_rec_6
+; CHECK-DAG: NoAlias:      i32* %gep_rec_2, i32* %gep_rec_3
+; CHECK-DAG: NoAlias:      i32* %gep_rec_2, i32* %gep_rec_4
+; CHECK-DAG: NoAlias:      i32* %gep_rec_2, i32* %gep_rec_5
+; CHECK-DAG: NoAlias:      i32* %gep_rec_2, i32* %gep_rec_6
+; CHECK-DAG: NoAlias:      i32* %gep_rec_3, i32* %gep_rec_4
+; CHECK-DAG: NoAlias:      i32* %gep_rec_3, i32* %gep_rec_5
+; CHECK-DAG: NoAlias:      i32* %gep_rec_3, i32* %gep_rec_6
+; CHECK-DAG: NoAlias:      i32* %gep_rec_4, i32* %gep_rec_5
+; CHECK-DAG: NoAlias:      i32* %gep_rec_4, i32* %gep_rec_6
+; CHECK-DAG: NoAlias:      i32* %gep_rec_5, i32* %gep_rec_6
 ; GEP max lookup depth was set to 6.
 define void @gep_recursion_max_lookup_depth_reached(i32* %a, <vscale x 4 x i32>* %p) {
   %gep = getelementptr <vscale x 4 x i32>, <vscale x 4 x i32>* %p, i64 1, i64 2
   %gep_rec_1 = getelementptr i32, i32* %gep, i64 1
   %gep_rec_2 = getelementptr i32, i32* %gep_rec_1, i64 1
   %gep_rec_3 = getelementptr i32, i32* %gep_rec_2, i64 1
   %gep_rec_4 = getelementptr i32, i32* %gep_rec_3, i64 1
   %gep_rec_5 = getelementptr i32, i32* %gep_rec_4, i64 1
   %gep_rec_6 = getelementptr i32, i32* %gep_rec_5, i64 1
   ret void
 }