[BatchAA] Reset entry when relying on cycle detection.

[asbirlea]

Summary

WIP
Do not cache values that rely on cycle detection, as this information cannot be carried from one query to the next.

[nikic]

I've just pushed an extended test case in https://github.com/llvm/llvm-project/commit/1b65a51af80a9375ef85cb8fa6ec9ec3c68b3549, that shows that this problem is not BatchAA specific. We need to deal with this even for single queries, as results might have already been cached before we reach the phi.

[asbirlea]

Got it, thank you for the test and for catching this!

[asbirlea]

Abandoning in favor of D90066.

llvm/include/llvm/Analysis/AliasAnalysis.h

 public:
   using LocPair = std::pair<MemoryLocation, MemoryLocation>;
   using AliasCacheT = SmallDenseMap<LocPair, AliasResult, 8>;
   AliasCacheT AliasCache;
 
   using IsCapturedCacheT = SmallDenseMap<const Value *, bool, 8>;
   IsCapturedCacheT IsCapturedCache;
 
+  bool BatchMode = false;
+  bool Reset = false;
+
   AAQueryInfo() : AliasCache(), IsCapturedCache() {}
 
+  AAQueryInfo(bool BatchMode) : AliasCache(), IsCapturedCache() {
+    this->BatchMode = BatchMode;
+  }
+
+  void erase(const MemoryLocation &LocA, const MemoryLocation &LocB) {
+    AliasCache.erase(LocPair(LocA, LocB));
+  }
+
   AliasResult updateResult(const LocPair &Locs, AliasResult Result) {
     auto It = AliasCache.find(Locs);
     assert(It != AliasCache.end() && "Entry must have existed");
     return It->second = Result;
   }
 };
 
 class BatchAAResults;

 /// esentially making AA work in "batch mode". The internal state cannot be
 /// cleared, so to go "out-of-batch-mode", the user must either use AAResults,
 /// or create a new BatchAAResults.
 class BatchAAResults {
   AAResults &AA;
   AAQueryInfo AAQI;
 
 public:
-  BatchAAResults(AAResults &AAR) : AA(AAR), AAQI() {}
+  BatchAAResults(AAResults &AAR) : AA(AAR), AAQI(true) {}
   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB) {
     return AA.alias(LocA, LocB, AAQI);
   }
   bool pointsToConstantMemory(const MemoryLocation &Loc, bool OrLocal = false) {
     return AA.pointsToConstantMemory(Loc, AAQI, OrLocal);
   }
   ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc) {
     return AA.getModRefInfo(Call, Loc, AAQI);

llvm/include/llvm/Analysis/BasicAliasAnalysis.h

private:
   /// != zext(%x) + zext(1) if the arithmetic overflows. GetLinearExpression
   /// will therefore conservatively refuse to decompose these expressions.
   /// However, we know that, for all %x, zext(%x) != zext(%x + 1), even if
   /// the addition overflows.
   bool
   constantOffsetHeuristic(const SmallVectorImpl<VariableGEPIndex> &VarIndices,
                           LocationSize V1Size, LocationSize V2Size,
                           const APInt &BaseOffset, AssumptionCache *AC,
-                          DominatorTree *DT);
+                          DominatorTree *DT, AAQueryInfo &AAQI);
 
-  bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2);
+  bool isValueEqualInPotentialCycles(const Value *V1, const Value *V2,
+                                     AAQueryInfo &AAQI);
 
   void GetIndexDifference(SmallVectorImpl<VariableGEPIndex> &Dest,
-                          const SmallVectorImpl<VariableGEPIndex> &Src);
+                          const SmallVectorImpl<VariableGEPIndex> &Src,
+                          AAQueryInfo &AAQI);
 
   AliasResult aliasGEP(const GEPOperator *V1, LocationSize V1Size,
                        const AAMDNodes &V1AAInfo, const Value *V2,
                        LocationSize V2Size, const AAMDNodes &V2AAInfo,
                        const Value *UnderlyingV1, const Value *UnderlyingV2,
                        AAQueryInfo &AAQI);
 
   AliasResult aliasPHI(const PHINode *PN, LocationSize PNSize,

llvm/lib/Analysis/BasicAliasAnalysis.cpp

if (CacheIt != AAQI.AliasCache.end())
     return CacheIt->second;
 
   CacheIt = AAQI.AliasCache.find(AAQueryInfo::LocPair(LocB, LocA));
   if (CacheIt != AAQI.AliasCache.end())
     return CacheIt->second;
 
   AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr,
                                  LocB.Size, LocB.AATags, AAQI);
+  if (AAQI.Reset)
+    AAQI.erase(LocA, LocB);
 
   assert(VisitedPhiBBs.empty());
   return Alias;
 }
 
 /// Checks to see if the specified callsite can clobber the specified memory
 /// object.
 ///

 ///
 /// We know that V1 is a GEP, but we don't know anything about V2.
 /// UnderlyingV1 is getUnderlyingObject(GEP1), UnderlyingV2 is the same for
 /// V2.
 AliasResult BasicAAResult::aliasGEP(
     const GEPOperator *GEP1, LocationSize V1Size, const AAMDNodes &V1AAInfo,
     const Value *V2, LocationSize V2Size, const AAMDNodes &V2AAInfo,
     const Value *UnderlyingV1, const Value *UnderlyingV2, AAQueryInfo &AAQI) {
+
   DecomposedGEP DecompGEP1, DecompGEP2;
   unsigned MaxPointerSize = getMaxPointerSize(DL);
   DecompGEP1.StructOffset = DecompGEP1.OtherOffset = APInt(MaxPointerSize, 0);
   DecompGEP2.StructOffset = DecompGEP2.OtherOffset = APInt(MaxPointerSize, 0);
   DecompGEP1.HasCompileTimeConstantScale =
       DecompGEP2.HasCompileTimeConstantScale = true;
 
   bool GEP1MaxLookupReached =
if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) {
 
     // If the max search depth is reached, the result is undefined
     if (GEP2MaxLookupReached || GEP1MaxLookupReached)
       return MayAlias;
 
     // Subtract the GEP2 pointer from the GEP1 pointer to find out their
     // symbolic difference.
     GEP1BaseOffset -= GEP2BaseOffset;
-    GetIndexDifference(DecompGEP1.VarIndices, DecompGEP2.VarIndices);
+    GetIndexDifference(DecompGEP1.VarIndices, DecompGEP2.VarIndices, AAQI);
 
   } else {
     // Check to see if these two pointers are related by the getelementptr
     // instruction.  If one pointer is a GEP with a non-zero index of the other
     // pointer, we know they cannot alias.
 
     // If both accesses are unknown size, we can't do anything useful here.
     if (V1Size == LocationSize::unknown() && V2Size == LocationSize::unknown())
if (!DecompGEP1.VarIndices.empty()) {
     // If GEP1BasePtr > V2 (GEP1BaseOffset > 0) then we know the pointers
     // don't alias if V2Size can fit in the gap between V2 and GEP1BasePtr.
     if (AllPositive && GEP1BaseOffset.sgt(0) &&
         V2Size != LocationSize::unknown() &&
         GEP1BaseOffset.uge(V2Size.getValue()))
       return NoAlias;
 
     if (constantOffsetHeuristic(DecompGEP1.VarIndices, V1Size, V2Size,
-                                GEP1BaseOffset, &AC, DT))
+                                GEP1BaseOffset, &AC, DT, AAQI))
       return NoAlias;
   }
 
   // Statically, we can see that the base objects are the same, but the
   // pointers have dynamic offsets which we can't resolve. And none of our
   // little tricks above worked.
   return MayAlias;
 }
if (isa<UndefValue>(V1) || isa<UndefValue>(V2))
     return NoAlias;
 
   // 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))
+  if (isValueEqualInPotentialCycles(V1, V2, AAQI))
     return MustAlias;
 
   if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy())
     return NoAlias; // Scalars cannot alias each other
 
   // Figure out what objects these things are pointing to if we can.
   if (O1 == nullptr)
     O1 = getUnderlyingObject(V1, MaxLookupSearchDepth);

 /// Check whether two Values can be considered equivalent.
 ///
 /// In addition to pointer equivalence of \p V1 and \p V2 this checks whether
 /// they can not be part of a cycle in the value graph by looking at all
 /// visited phi nodes an making sure that the phis cannot reach the value. We
 /// have to do this because we are looking through phi nodes (That is we say
 /// noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB).
 bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
-                                                  const Value *V2) {
+                                                  const Value *V2,
+                                                  AAQueryInfo &AAQI) {
   if (V != V2)
     return false;
 
   const Instruction *Inst = dyn_cast<Instruction>(V);
   if (!Inst)
     return true;
 
+  if (AAQI.BatchMode)
+    AAQI.Reset = true;
+
   if (VisitedPhiBBs.empty())
     return true;
 
   if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck)
     return false;
 
   // Make sure that the visited phis cannot reach the Value. This ensures that
   // the Values cannot come from different iterations of a potential cycle the
   // phi nodes could be involved in.
   for (auto *P : VisitedPhiBBs)
     if (isPotentiallyReachable(&P->front(), Inst, nullptr, DT, LI))
       return false;
 
   return true;
 }
 
 /// Computes the symbolic difference between two de-composed GEPs.
 ///
 /// Dest and Src are the variable indices from two decomposed GetElementPtr
 /// instructions GEP1 and GEP2 which have common base pointers.
 void BasicAAResult::GetIndexDifference(
     SmallVectorImpl<VariableGEPIndex> &Dest,
-    const SmallVectorImpl<VariableGEPIndex> &Src) {
+    const SmallVectorImpl<VariableGEPIndex> &Src, AAQueryInfo &AAQI) {
   if (Src.empty())
     return;
 
   for (unsigned i = 0, e = Src.size(); i != e; ++i) {
     const Value *V = Src[i].V;
     unsigned ZExtBits = Src[i].ZExtBits, SExtBits = Src[i].SExtBits;
     APInt Scale = Src[i].Scale;
 
     // Find V in Dest.  This is N^2, but pointer indices almost never have more
     // than a few variable indexes.
     for (unsigned j = 0, e = Dest.size(); j != e; ++j) {
-      if (!isValueEqualInPotentialCycles(Dest[j].V, V) ||
+      if (!isValueEqualInPotentialCycles(Dest[j].V, V, AAQI) ||
           Dest[j].ZExtBits != ZExtBits || Dest[j].SExtBits != SExtBits)
         continue;
 
       // If we found it, subtract off Scale V's from the entry in Dest.  If it
       // goes to zero, remove the entry.
       if (Dest[j].Scale != Scale)
         Dest[j].Scale -= Scale;
       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};
       Dest.push_back(Entry);
     }
   }
 }
 
 bool BasicAAResult::constantOffsetHeuristic(
     const SmallVectorImpl<VariableGEPIndex> &VarIndices,
     LocationSize MaybeV1Size, LocationSize MaybeV2Size, const APInt &BaseOffset,
-    AssumptionCache *AC, DominatorTree *DT) {
+    AssumptionCache *AC, DominatorTree *DT, AAQueryInfo &AAQI) {
   if (VarIndices.size() != 2 || MaybeV1Size == LocationSize::unknown() ||
       MaybeV2Size == LocationSize::unknown())
     return false;
 
   const uint64_t V1Size = MaybeV1Size.getValue();
   const uint64_t V2Size = MaybeV2Size.getValue();
 
   const VariableGEPIndex &Var0 = VarIndices[0], &Var1 = VarIndices[1];
bool BasicAAResult::constantOffsetHeuristic(
   const Value *V0 = GetLinearExpression(Var0.V, V0Scale, V0Offset, V0ZExtBits,
                                         V0SExtBits, DL, 0, AC, DT, NSW, NUW);
   NSW = true;
   NUW = true;
   const Value *V1 = GetLinearExpression(Var1.V, V1Scale, V1Offset, V1ZExtBits,
                                         V1SExtBits, DL, 0, AC, DT, NSW, NUW);
 
   if (V0Scale != V1Scale || V0ZExtBits != V1ZExtBits ||
-      V0SExtBits != V1SExtBits || !isValueEqualInPotentialCycles(V0, V1))
+      V0SExtBits != V1SExtBits || !isValueEqualInPotentialCycles(V0, V1, AAQI))
     return false;
 
   // We have a hit - Var0 and Var1 only differ by a constant offset!
 
   // If we've been sext'ed then zext'd the maximum difference between Var0 and
   // Var1 is possible to calculate, but we're just interested in the absolute
   // minimum difference between the two. The minimum distance may occur due to
   // wrapping; consider "add i3 %i, 5": if %i == 7 then 7 + 5 mod 8 == 4, and so

llvm/unittests/Analysis/AliasAnalysisTest.cpp

TEST_F(AliasAnalysisTest, BatchAAPhiCycles) {
   MemoryLocation A2Loc(A2, LocationSize::precise(1));
 
   auto &AA = getAAResults(*F);
   EXPECT_EQ(NoAlias, AA.alias(A1Loc, A2Loc));
   EXPECT_EQ(MayAlias, AA.alias(PhiLoc, A1Loc));
 
   BatchAAResults BatchAA(AA);
   EXPECT_EQ(NoAlias, BatchAA.alias(A1Loc, A2Loc));
-  EXPECT_EQ(NoAlias, BatchAA.alias(PhiLoc, A1Loc)); // TODO: This is wrong.
+  EXPECT_EQ(MayAlias, BatchAA.alias(PhiLoc, A1Loc));
 }
 
 class AAPassInfraTest : public testing::Test {
 protected:
   LLVMContext C;
   SMDiagnostic Err;
   std::unique_ptr<Module> M;