[BasicAA] Replace VisitedPhiBBs with a single flag

[nikic]

Summary

When looking through phis, BasicAA has to guard against the possibility that values from two separate cycle iterations are being compared -- in this case, even though the SSA values may be the same, they cannot be considered as equal.

This is currently done by keeping a set of VisitedPhiBBs for any phis we looked through, and then checking whether the relevant instruction is reachable from one of the phis.

This patch replaces this set with a single flag. If the flag is set, then we will not assume equality for any instruction part of a cycle. While this is nominally less accurate, it makes essentially no difference in practice. Here are the AA stats for test-suite:

aa.NumMayAlias  |   3072005 |  3072016
aa.NumMustAlias |    337858 |   337854
aa.NumNoAlias   |  13255345 | 13255349

The motivation for the change is to expose the MayBeCrossIteration flag to AA users, which will allow fixing miscompiles related to incorrect handling of cross-iteration AA queries.

[reames]

LGTM

I'm surprised at the lack of precision loss here, but well, the numbers speak for themselves.

llvm/include/llvm/Analysis/BasicAliasAnalysis.h

public:
 
   /// Returns the behavior when calling the given function. For use when the
   /// call site is not known.
   MemoryEffects getMemoryEffects(const Function *Fn);
 
 private:
   struct DecomposedGEP;
 
-  /// Tracks phi nodes we have visited.
+  /// Tracks whether the accesses may be on different cycle iterations.
   ///
   /// When interpret "Value" pointer equality as value equality we need to make
   /// sure that the "Value" is not part of a cycle. Otherwise, two uses could
   /// come from different "iterations" of a cycle and see different values for
   /// the same "Value" pointer.
   ///
   /// The following example shows the problem:
   ///   %p = phi(%alloca1, %addr2)
   ///   %l = load %ptr
   ///   %addr1 = gep, %alloca2, 0, %l
   ///   %addr2 = gep  %alloca2, 0, (%l + 1)
   ///      alias(%p, %addr1) -> MayAlias !
   ///   store %l, ...
-  SmallPtrSet<const BasicBlock *, 8> VisitedPhiBBs;
+  bool MayBeCrossIteration = false;
 
   /// Tracks instructions visited by pointsToConstantMemory.
   SmallPtrSet<const Value *, 16> Visited;
 
   static DecomposedGEP
   DecomposeGEPExpression(const Value *V, const DataLayout &DL,
                          AssumptionCache *AC, DominatorTree *DT);
 

llvm/lib/Analysis/BasicAliasAnalysis.cpp

 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/KnownBits.h"
+#include "llvm/Support/SaveAndRestore.h"
 #include <cassert>
 #include <cstdint>
 #include <cstdlib>
 #include <utility>
 
 #define DEBUG_TYPE "basicaa"
 
 using namespace llvm;
if (Var.Val.TruncBits == 0 &&
       if (MultiplyByScaleNoWrap(Var)) {
         // If V != 0 then abs(VarIndex) >= abs(Scale).
         MinAbsVarIndex = Var.Scale.abs();
       }
     }
   } else if (DecompGEP1.VarIndices.size() == 2) {
     // VarIndex = Scale*V0 + (-Scale)*V1.
     // If V0 != V1 then abs(VarIndex) >= abs(Scale).
-    // Check that VisitedPhiBBs is empty, to avoid reasoning about
+    // Check that MayBeCrossIteration is false, to avoid reasoning about
     // inequality of values across loop iterations.
     const VariableGEPIndex &Var0 = DecompGEP1.VarIndices[0];
     const VariableGEPIndex &Var1 = DecompGEP1.VarIndices[1];
     if (Var0.Scale == -Var1.Scale && Var0.Val.TruncBits == 0 &&
-        Var0.Val.hasSameCastsAs(Var1.Val) && VisitedPhiBBs.empty() &&
+        Var0.Val.hasSameCastsAs(Var1.Val) && !MayBeCrossIteration &&
         isKnownNonEqual(Var0.Val.V, Var1.Val.V, DL, &AC, /* CxtI */ nullptr,
                         DT))
       MinAbsVarIndex = Var0.Scale.abs();
   }
 
   if (MinAbsVarIndex) {
     // The constant offset will have added at least +/-MinAbsVarIndex to it.
     APInt OffsetLo = DecompGEP1.Offset - *MinAbsVarIndex;
AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize,
 
   // If this PHI node is recursive, indicate that the pointer may be moved
   // across iterations. We can only prove NoAlias if different underlying
   // objects are involved.
   if (isRecursive)
     PNSize = LocationSize::beforeOrAfterPointer();
 
   // In the recursive alias queries below, we may compare values from two
-  // different loop iterations. Keep track of visited phi blocks, which will
-  // be used when determining value equivalence.
-  bool BlockInserted = VisitedPhiBBs.insert(PN->getParent()).second;
-  auto _ = make_scope_exit([&]() {
-    if (BlockInserted)
-      VisitedPhiBBs.erase(PN->getParent());
-  });
+  // different loop iterations.
+  SaveAndRestore<bool> SavedMayBeCrossIteration(MayBeCrossIteration, true);
 
-  // If we inserted a block into VisitedPhiBBs, alias analysis results that
+  // If we enabled the MayBeCrossIteration flag, alias analysis results that
   // have been cached earlier may no longer be valid. Perform recursive queries
   // with a new AAQueryInfo.
   AAQueryInfo NewAAQI = AAQI.withEmptyCache();
-  AAQueryInfo *UseAAQI = BlockInserted ? &NewAAQI : &AAQI;
+  AAQueryInfo *UseAAQI = !SavedMayBeCrossIteration.get() ? &NewAAQI : &AAQI;
 
   AliasResult Alias = AAQI.AAR.alias(MemoryLocation(V1Srcs[0], PNSize),
                                      MemoryLocation(V2, V2Size), *UseAAQI);
 
   // Early exit if the check of the first PHI source against V2 is MayAlias.
   // Other results are not possible.
   if (Alias == AliasResult::MayAlias)
     return AliasResult::MayAlias;
if (V1Size.isPrecise() && V2Size.isPrecise() &&
       return AliasResult::PartialAlias;
   }
 
   return AliasResult::MayAlias;
 }
 
 /// 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
+/// If the values may come from different cycle iterations, this will also
+/// check that the values are not part of cycle. 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) {
   if (V != V2)
     return false;
 
-  const Instruction *Inst = dyn_cast<Instruction>(V);
-  if (!Inst)
+  if (!MayBeCrossIteration)
     return true;
 
-  if (VisitedPhiBBs.empty())
+  // Non-instructions and instructions in the entry block cannot be part of
+  // a loop.
+  const Instruction *Inst = dyn_cast<Instruction>(V);
+  if (!Inst || Inst->getParent()->isEntryBlock())
     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 (const auto *P : VisitedPhiBBs)
-    if (isPotentiallyReachable(&P->front(), Inst, nullptr, DT))
-      return false;
-
-  return true;
+  // Check whether the instruction is part of a cycle, by checking whether the
+  // block can (non-trivially) reach itself.
+  BasicBlock *BB = const_cast<BasicBlock *>(Inst->getParent());
+  SmallVector<BasicBlock *> Succs(successors(BB));
+  return !isPotentiallyReachableFromMany(Succs, BB, nullptr, DT);
 }
 
 /// Computes the symbolic difference between two de-composed GEPs.
 void BasicAAResult::subtractDecomposedGEPs(DecomposedGEP &DestGEP,
                                            const DecomposedGEP &SrcGEP) {
   DestGEP.Offset -= SrcGEP.Offset;
   for (const VariableGEPIndex &Src : SrcGEP.VarIndices) {
     // Find V in Dest.  This is N^2, but pointer indices almost never have more