[BasicAA] Make sure context instruction is symmetric

[nikic]

Summary

D71264 started using a context instruction in a computeKnownBits() call. However, if aliasing between two GEPs is checked, then the choice of context instruction will be different for alias(GEP1, GEP2) and alias(GEP2, GEP1), which is not supposed to happen.

Resolve this by remembering which GEP a certain VarIndex belongs to, and use that as the context instruction. This makes the choice of context instruction symmetric.

[jdoerfert]

Can't we use any dominator for the context? If so, why not use findNearestCommonDominator instead of giving up?

[nikic]

Use different approach: Store which GEP a certain index belongs to and use that as the context instruction. I think this makes more sense than the previous approach, even if it may be fully optimal if one GEP dominates the other.

[nikic]

In D93183#2452415, @jdoerfert wrote:

Can't we use any dominator for the context? If so, why not use findNearestCommonDominator instead of giving up?

Yes, that would be legal as well (but also sub-optimal). Annoyingly we don't have an instruction-level NCD API (D91767 was recently not accepted), though in this case just taking the terminator of the BB NCD should work fine.

Taking a step back though, I think my original direction here probably wasn't the best, and it would make more sense to use whichever GEP the index actually belonged to as context. That may also be non-optimal (if the index is on a dominating GEP), but I think it's more predictable and doesn't have any odd "cliffs". I have updated the patch to that effect.

[nikic]

ping :)

[jdoerfert]

Maybe I don't understand this so I figure I ask: Couldn't we know about V2 at position Ctx1 than we know at Ctx2? If so, would it be correct to use Ctx1 information? I get the feeling that the answers are both "true" but I want to confirm first.

[nikic]

In D93183#2468883, @jdoerfert wrote:

Maybe I don't understand this so I figure I ask: Couldn't we know about V2 at position Ctx1 than we know at Ctx2? If so, would it be correct to use Ctx1 information? I get the feeling that the answers are both "true" but I want to confirm first.

I'm not sure I got the question right, so possibly the answer is way off base...

When considering getModRef() between two instructions, the returned AA information is only (in the general case) valid under the assumption that both instructions have been executed. (This is most obvious for the case of noalias attributes/metadata.) As such, the information can only be valid at program points that are reachable from both instructions. The alias() interface then only considers the stored/loaded operands, rather than the load/store instruction itself, which is a conservative approximation. Once again, the result of the alias API is only valid at program points that are reachable from both operand defs. We can then use either of the operands as context, because the region of validity for the AA result has to be reachable from both. It's once again a conservative approximation. So if we have a VarIndex on GEP1 we could also use GEP2 as context, and the other way around. This patch just picks the GEP it occurs on to ensure the choice is predictable/symmetric.

[jdoerfert]

^ This matches what I was expecting, thanks.

I would like us to (eventually) pick the most precise context but this improves over the status quo and looks correct, so LGTM.

llvm/include/llvm/Analysis/BasicAliasAnalysis.h

struct VariableGEPIndex {
     // with different extensions as different variables in a GEP's linear
     // expression;
     // e.g.: if V == -1, then sext(x) != zext(x).
     unsigned ZExtBits;
     unsigned SExtBits;
 
     APInt Scale;
 
+    // Context instruction to use when querying information about this index.
+    const Instruction *CxtI;
+
     bool operator==(const VariableGEPIndex &Other) const {
       return V == Other.V && ZExtBits == Other.ZExtBits &&
              SExtBits == Other.SExtBits && Scale == Other.Scale;
     }
 
     bool operator!=(const VariableGEPIndex &Other) const {
       return !operator==(Other);
     }

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 /// 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 = getMaxPointerSize(DL);
   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);
for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
         }
       }
 
       // Make sure that we have a scale that makes sense for this target's
       // pointer size.
       Scale = adjustToPointerSize(Scale, PointerSize);
 
       if (!!Scale) {
-        VariableGEPIndex Entry = {Index, ZExtBits, SExtBits, Scale};
+        VariableGEPIndex Entry = {Index, ZExtBits, SExtBits, Scale, CxtI};
         Decomposed.VarIndices.push_back(Entry);
       }
     }
 
     // Take care of wrap-arounds
     if (GepHasConstantOffset)
       Decomposed.Offset = adjustToPointerSize(Decomposed.Offset, PointerSize);
 
for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
       else
         GCD = APIntOps::GreatestCommonDivisor(GCD, Scale.abs());
 
       if (AllNonNegative || AllNonPositive) {
         // If the Value could change between cycles, then any reasoning about
         // the Value this cycle may not hold in the next cycle. We'll just
         // give up if we can't determine conditions that hold for every cycle:
         const Value *V = DecompGEP1.VarIndices[i].V;
+        const Instruction *CxtI = DecompGEP1.VarIndices[i].CxtI;
 
-        KnownBits Known =
-            computeKnownBits(V, DL, 0, &AC, dyn_cast<Instruction>(GEP1), DT);
+        KnownBits Known = computeKnownBits(V, DL, 0, &AC, CxtI, DT);
         bool SignKnownZero = Known.isNonNegative();
         bool SignKnownOne = Known.isNegative();
 
         // Zero-extension widens the variable, and so forces the sign
         // bit to zero.
         bool IsZExt = DecompGEP1.VarIndices[i].ZExtBits > 0 || isa<ZExtInst>(V);
         SignKnownZero |= IsZExt;
         SignKnownOne &= !IsZExt;
for (unsigned j = 0, e = Dest.size(); j != e; ++j) {
       else
         Dest.erase(Dest.begin() + j);
       Scale = 0;
       break;
     }
 
     // If we didn't consume this entry, add it to the end of the Dest list.
     if (!!Scale) {
-      VariableGEPIndex Entry = {V, ZExtBits, SExtBits, -Scale};
+      VariableGEPIndex Entry = {V, ZExtBits, SExtBits, -Scale, Src[i].CxtI};
       Dest.push_back(Entry);
     }
   }
 }
 
 bool BasicAAResult::constantOffsetHeuristic(
     const SmallVectorImpl<VariableGEPIndex> &VarIndices,
     LocationSize MaybeV1Size, LocationSize MaybeV2Size, const APInt &BaseOffset,

llvm/test/Analysis/BasicAA/assume-index-positive.ll

;
   %lv.2 = load <6 x double>, <6 x double>* %col.ptr.2.cast, align 8
   %res.1 = fadd <6 x double> %lv.1, %lv.1
   %res.2 = fadd <6 x double> %lv.2, %lv.2
   store <6 x double> %res.1, <6 x double>* %col.ptr.1, align 8
   store <6 x double> %res.2, <6 x double>* %col.ptr.2.cast, align 8
   ret void
 }
 
+define void @symmetry([0 x i8]* %ptr, i32 %a, i32 %b, i32 %c) {
+; CHECK-LABEL: Function: symmetry
+; CHECK: NoAlias: i8* %gep1, i8* %gep2
+;
+  %b.cmp = icmp slt i32 %b, 0
+  call void @llvm.assume(i1 %b.cmp)
+  %gep1 = getelementptr [0 x i8], [0 x i8]* %ptr, i32 %a, i32 %b
+  call void @barrier()
+  %c.cmp = icmp sgt i32 %c, -1
+  call void @llvm.assume(i1 %c.cmp)
+  %c.off = add nuw nsw i32 %c, 1
+  %gep2 = getelementptr [0 x i8], [0 x i8]* %ptr, i32 %a, i32 %c.off
+  ret void
+}
+
 declare void @llvm.assume(i1 %cond)
+declare void @barrier()