NewGVN: Fix bug exposed by PR31761

[• dberlin]

Summary

This does not actually fix the testcase in PR31761 (discussion is
ongoing on the testcase), but does fix a bug it exposes, where stores
were not properly clobbering loads.

We accomplish this by unifying the memory equivalence infratructure
back into the normal congruence infrastructure, and then properly
destroying congruence classes when memory state leaders disappear.

[davide]

I reviewed this as part of https://reviews.llvm.org/D29149 (duplicated the comments here)

lib/Transforms/Scalar/NewGVN.cpp

707–711 ↗

(On Diff #85952)

*sigh*.

768 ↗

(On Diff #85952)

#if 1 can go away.

1168–1182 ↗

(On Diff #85952)

Thanks for this very explicative comment, I think it's very useful. Nit, dot at the end of the last sentence.

1247–1252 ↗

(On Diff #85952)

This can be removed.

[• dberlin]

lib/Transforms/Scalar/NewGVN.cpp

707–711 ↗

(On Diff #85952)

Yeah, i think i'm going to try to push that in, because i think this invariant may discover more bugs.

Additionally, it *should* us turn back on a much simpler invariant for the memory accesses:
back in the day, we wanted to turn on the invariant that two stores with equivalent memory states must be in the same congruence class, and that is now true again (AFAIK)

Except for the above case :(

768 ↗

(On Diff #85952)

Yup

llvm/trunk/lib/Transforms/Scalar/NewGVN.cpp

 //
 struct CongruenceClass {
   using MemberSet = SmallPtrSet<Value *, 4>;
   unsigned ID;
   // Representative leader.
   Value *RepLeader = nullptr;
   // If this is represented by a store, the value.
   Value *RepStoredValue = nullptr;
+  // If this class contains MemoryDefs, what is the represented memory state.
+  MemoryAccess *RepMemoryAccess = nullptr;
   // Defining Expression.
   const Expression *DefiningExpr = nullptr;
   // Actual members of this class.
   MemberSet Members;
 
   // True if this class has no members left.  This is mainly used for assertion
   // purposes, and for skipping empty classes.
   bool Dead = false;
class NewGVN : public FunctionPass {
   DenseMap<Value *, CongruenceClass *> ValueToClass;
   DenseMap<Value *, const Expression *> ValueToExpression;
 
   // A table storing which memorydefs/phis represent a memory state provably
   // equivalent to another memory state.
   // We could use the congruence class machinery, but the MemoryAccess's are
   // abstract memory states, so they can only ever be equivalent to each other,
   // and not to constants, etc.
-  DenseMap<const MemoryAccess *, MemoryAccess *> MemoryAccessEquiv;
+  DenseMap<const MemoryAccess *, CongruenceClass *> MemoryAccessToClass;
 
   // Expression to class mapping.
   using ExpressionClassMap = DenseMap<const Expression *, CongruenceClass *>;
   ExpressionClassMap ExpressionToClass;
 
   // Which values have changed as a result of leader changes.
   SmallPtrSet<Value *, 8> LeaderChanges;
 
private:
   const Expression *performSymbolicLoadEvaluation(Instruction *,
                                                   const BasicBlock *);
   const Expression *performSymbolicStoreEvaluation(Instruction *,
                                                    const BasicBlock *);
   const Expression *performSymbolicCallEvaluation(Instruction *,
                                                   const BasicBlock *);
   const Expression *performSymbolicPHIEvaluation(Instruction *,
                                                  const BasicBlock *);
-  bool setMemoryAccessEquivTo(MemoryAccess *From, MemoryAccess *To);
   const Expression *performSymbolicAggrValueEvaluation(Instruction *,
                                                        const BasicBlock *);
 
   // Congruence finding.
   // Templated to allow them to work both on BB's and BB-edges.
   template <class T>
   Value *lookupOperandLeader(Value *, const User *, const T &) const;
   void performCongruenceFinding(Instruction *, const Expression *);
   void moveValueToNewCongruenceClass(Instruction *, CongruenceClass *,
                                      CongruenceClass *);
+  bool setMemoryAccessEquivTo(MemoryAccess *From, CongruenceClass *To);
+  MemoryAccess *lookupMemoryAccessEquiv(MemoryAccess *) const;
+
   // Reachability handling.
   void updateReachableEdge(BasicBlock *, BasicBlock *);
   void processOutgoingEdges(TerminatorInst *, BasicBlock *);
   bool isOnlyReachableViaThisEdge(const BasicBlockEdge &) const;
   Value *findConditionEquivalence(Value *, BasicBlock *) const;
-  MemoryAccess *lookupMemoryAccessEquiv(MemoryAccess *) const;
 
   // Elimination.
   struct ValueDFS;
   void convertDenseToDFSOrdered(CongruenceClass::MemberSet &,
                                 SmallVectorImpl<ValueDFS> &);
 
   bool eliminateInstructions(Function &);
   void replaceInstruction(Instruction *, Value *);

 Value *NewGVN::lookupOperandLeader(Value *V, const User *U, const T &B) const {
   CongruenceClass *CC = ValueToClass.lookup(V);
   if (CC && (CC != InitialClass))
     return CC->RepStoredValue ? CC->RepStoredValue : CC->RepLeader;
   return V;
 }
 
 MemoryAccess *NewGVN::lookupMemoryAccessEquiv(MemoryAccess *MA) const {
-  MemoryAccess *Result = MemoryAccessEquiv.lookup(MA);
-  return Result ? Result : MA;
+  auto *CC = MemoryAccessToClass.lookup(MA);
+  if (CC && CC->RepMemoryAccess)
+    return CC->RepMemoryAccess;
+  // FIXME: We need to audit all the places that current set a nullptr To, and
+  // fix them.  There should always be *some* congruence class, even if it is
+  // singular.  Right now, we don't bother setting congruence classes for
+  // anything but stores, which means we have to return the original access
+  // here.  Otherwise, this should be unreachable.
+  return MA;
 }
 
 LoadExpression *NewGVN::createLoadExpression(Type *LoadType, Value *PointerOp,
                                              LoadInst *LI, MemoryAccess *DA,
                                              const BasicBlock *B) {
   auto *E = new (ExpressionAllocator) LoadExpression(1, LI, DA);
   E->allocateOperands(ArgRecycler, ExpressionAllocator);
   E->setType(LoadType);
MemoryAccess *StoreRHS = lookupMemoryAccessEquiv(
         cast<MemoryDef>(StoreAccess)->getDefiningAccess());
     const Expression *OldStore = createStoreExpression(SI, StoreRHS, B);
     CongruenceClass *CC = ExpressionToClass.lookup(OldStore);
     // Basically, check if the congruence class the store is in is defined by a
     // store that isn't us, and has the same value.  MemorySSA takes care of
     // ensuring the store has the same memory state as us already.
     // The RepStoredValue gets nulled if all the stores disappear in a class, so
     // we don't need to check if the class contains a store besides us.
-    if (CC && CC->DefiningExpr && isa<StoreExpression>(CC->DefiningExpr) &&
+    if (CC &&
         CC->RepStoredValue == lookupOperandLeader(SI->getValueOperand(), SI, B))
       return createStoreExpression(SI, StoreRHS, B);
   }
 
   return createStoreExpression(SI, StoreAccess, B);
 }
 
 const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I,
if (AA->onlyReadsMemory(CI)) {
     MemoryAccess *DefiningAccess = MSSAWalker->getClobberingMemoryAccess(CI);
     return createCallExpression(CI, lookupMemoryAccessEquiv(DefiningAccess), B);
   }
   return nullptr;
 }
 
 // Update the memory access equivalence table to say that From is equal to To,
 // and return true if this is different from what already existed in the table.
-bool NewGVN::setMemoryAccessEquivTo(MemoryAccess *From, MemoryAccess *To) {
-  DEBUG(dbgs() << "Setting " << *From << " equivalent to ");
-  if (!To)
-    DEBUG(dbgs() << "itself");
-  else
-    DEBUG(dbgs() << *To);
+// FIXME: We need to audit all the places that current set a nullptr To, and fix
+// them. There should always be *some* congruence class, even if it is singular.
+bool NewGVN::setMemoryAccessEquivTo(MemoryAccess *From, CongruenceClass *To) {
+  DEBUG(dbgs() << "Setting " << *From);
+  if (To) {
+    DEBUG(dbgs() << " equivalent to congruence class ");
+    DEBUG(dbgs() << To->ID << " with current memory access leader ");
+    DEBUG(dbgs() << *To->RepMemoryAccess);
+  } else {
+    DEBUG(dbgs() << " equivalent to itself");
     DEBUG(dbgs() << "\n");
-  auto LookupResult = MemoryAccessEquiv.find(From);
+  }
+
+  auto LookupResult = MemoryAccessToClass.find(From);
   bool Changed = false;
   // If it's already in the table, see if the value changed.
-  if (LookupResult != MemoryAccessEquiv.end()) {
+  if (LookupResult != MemoryAccessToClass.end()) {
     if (To && LookupResult->second != To) {
       // It wasn't equivalent before, and now it is.
       LookupResult->second = To;
       Changed = true;
     } else if (!To) {
       // It used to be equivalent to something, and now it's not.
-      MemoryAccessEquiv.erase(LookupResult);
+      MemoryAccessToClass.erase(LookupResult);
       Changed = true;
     }
   } else {
     assert(!To &&
            "Memory equivalence should never change from nothing to something");
   }
 
   return Changed;
void NewGVN::moveValueToNewCongruenceClass(Instruction *I,
   if (NewClass->RepLeader != I) {
     auto DFSNum = InstrDFS.lookup(I);
     if (DFSNum < NewClass->NextLeader.second)
       NewClass->NextLeader = {I, DFSNum};
   }
 
   OldClass->Members.erase(I);
   NewClass->Members.insert(I);
-  if (isa<StoreInst>(I)) {
+  MemoryAccess *StoreAccess = nullptr;
+  if (auto *SI = dyn_cast<StoreInst>(I)) {
+    StoreAccess = MSSA->getMemoryAccess(SI);
     --OldClass->StoreCount;
     assert(OldClass->StoreCount >= 0);
     ++NewClass->StoreCount;
     assert(NewClass->StoreCount > 0);
+    if (!NewClass->RepMemoryAccess) {
+      // If we don't have a representative memory access, it better be the only
+      // store in there.
+      assert(NewClass->StoreCount == 1);
+      NewClass->RepMemoryAccess = StoreAccess;
+    }
+    setMemoryAccessEquivTo(StoreAccess, NewClass);
   }
 
   ValueToClass[I] = NewClass;
   // See if we destroyed the class or need to swap leaders.
   if (OldClass->Members.empty() && OldClass != InitialClass) {
     if (OldClass->DefiningExpr) {
       OldClass->Dead = true;
       DEBUG(dbgs() << "Erasing expression " << OldClass->DefiningExpr
                    << " from table\n");
       ExpressionToClass.erase(OldClass->DefiningExpr);
     }
   } else if (OldClass->RepLeader == I) {
     // When the leader changes, the value numbering of
     // everything may change due to symbolization changes, so we need to
     // reprocess.
     DEBUG(dbgs() << "Leader change!\n");
     ++NumGVNLeaderChanges;
     // Destroy the stored value if there are no more stores to represent it.
-    if (OldClass->RepStoredValue != nullptr && OldClass->StoreCount == 0)
+    if (OldClass->StoreCount == 0) {
+      if (OldClass->RepStoredValue != nullptr)
         OldClass->RepStoredValue = nullptr;
+      if (OldClass->RepMemoryAccess != nullptr)
+        OldClass->RepMemoryAccess = nullptr;
+    }
+
+    // If we destroy the old access leader, we have to effectively destroy the
+    // congruence class.  When it comes to scalars, anything with the same value
+    // is as good as any other.  That means that one leader is as good as
+    // another, and as long as you have some leader for the value, you are
+    // good.. When it comes to *memory states*, only one particular thing really
+    // represents the definition of a given memory state.  Once it goes away, we
+    // need to re-evaluate which pieces of memory are really still
+    // equivalent. The best way to do this is to re-value number things.  The
+    // only way to really make that happen is to destroy the rest of the class.
+    // In order to effectively destroy the class, we reset ExpressionToClass for
+    // each by using the ValueToExpression mapping.  The members later get
+    // marked as touched due to the leader change.  We will create new
+    // congruence classes, and the pieces that are still equivalent will end
+    // back together in a new class.  If this becomes too expensive, it is
+    // possible to use a versioning scheme for the congruence classes to avoid
+    // the expressions finding this old class.
+    if (OldClass->StoreCount > 0 && OldClass->RepMemoryAccess == StoreAccess) {
+      DEBUG(dbgs() << "Kicking everything out of class " << OldClass->ID
+                   << " because memory access leader changed");
+      for (auto Member : OldClass->Members)
+        ExpressionToClass.erase(ValueToExpression.lookup(Member));
+    }
 
     // We don't need to sort members if there is only 1, and we don't care about
     // sorting the initial class because everything either gets out of it or is
     // unreachable.
     if (OldClass->Members.size() == 1 || OldClass == InitialClass) {
       OldClass->RepLeader = *(OldClass->Members.begin());
     } else if (OldClass->NextLeader.first) {
       ++NumGVNAvoidedSortedLeaderChanges;
if (lookupResult.second) {
       // Constants and variables should always be made the leader.
       if (const auto *CE = dyn_cast<ConstantExpression>(E)) {
         NewClass->RepLeader = CE->getConstantValue();
       } else if (const auto *SE = dyn_cast<StoreExpression>(E)) {
         StoreInst *SI = SE->getStoreInst();
         NewClass->RepLeader = SI;
         NewClass->RepStoredValue =
             lookupOperandLeader(SI->getValueOperand(), SI, SI->getParent());
+        // The RepMemoryAccess field will be filled in properly by the
+        // moveValueToNewCongruenceClass call.
       } else {
         NewClass->RepLeader = I;
       }
       assert(!isa<VariableExpression>(E) &&
              "VariableExpression should have been handled already");
 
       EClass = NewClass;
       DEBUG(dbgs() << "Created new congruence class for " << *I
void NewGVN::performCongruenceFinding(Instruction *I, const Expression *E) {
   bool LeaderChanged = LeaderChanges.erase(I);
   if (ClassChanged || LeaderChanged) {
     DEBUG(dbgs() << "Found class " << EClass->ID << " for expression " << E
                  << "\n");
 
     if (ClassChanged)
       moveValueToNewCongruenceClass(I, IClass, EClass);
     markUsersTouched(I);
-    if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) {
-      // If this is a MemoryDef, we need to update the equivalence table. If
-      // we determined the expression is congruent to a different memory
-      // state, use that different memory state.  If we determined it didn't,
-      // we update that as well.  Right now, we only support store
-      // expressions.
-      if (!isa<MemoryUse>(MA) && isa<StoreExpression>(E) &&
-          EClass->Members.size() != 1) {
-        auto *DefAccess = cast<StoreExpression>(E)->getDefiningAccess();
-        setMemoryAccessEquivTo(MA, DefAccess != MA ? DefAccess : nullptr);
-      } else {
-        setMemoryAccessEquivTo(MA, nullptr);
-      }
+    if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
       markMemoryUsersTouched(MA);
-    }
-  }
-}
 
 // Process the fact that Edge (from, to) is reachable, including marking
 // any newly reachable blocks and instructions for processing.
 void NewGVN::updateReachableEdge(BasicBlock *From, BasicBlock *To) {
   // Check if the Edge was reachable before.
   if (ReachableEdges.insert({From, To}).second) {
     // If this block wasn't reachable before, all instructions are touched.
     if (ReachableBlocks.insert(To).second) {

 // class. The leader of INITIAL is the undetermined value `TOP`.
 // When the algorithm has finished, values still in INITIAL are unreachable.
 void NewGVN::initializeCongruenceClasses(Function &F) {
   // FIXME now i can't remember why this is 2
   NextCongruenceNum = 2;
   // Initialize all other instructions to be in INITIAL class.
   CongruenceClass::MemberSet InitialValues;
   InitialClass = createCongruenceClass(nullptr, nullptr);
+  InitialClass->RepMemoryAccess = MSSA->getLiveOnEntryDef();
   for (auto &B : F) {
     if (auto *MP = MSSA->getMemoryAccess(&B))
-      MemoryAccessEquiv.insert({MP, MSSA->getLiveOnEntryDef()});
+      MemoryAccessToClass[MP] = InitialClass;
 
     for (auto &I : B) {
       InitialValues.insert(&I);
       ValueToClass[&I] = InitialClass;
       // All memory accesses are equivalent to live on entry to start. They must
       // be initialized to something so that initial changes are noticed. For
       // the maximal answer, we initialize them all to be the same as
       // liveOnEntry.  Note that to save time, we only initialize the
       // MemoryDef's for stores and all MemoryPhis to be equal.  Right now, no
       // other expression can generate a memory equivalence.  If we start
       // handling memcpy/etc, we can expand this.
       if (isa<StoreInst>(&I)) {
-        MemoryAccessEquiv.insert(
-            {MSSA->getMemoryAccess(&I), MSSA->getLiveOnEntryDef()});
+        MemoryAccessToClass[MSSA->getMemoryAccess(&I)] = InitialClass;
         ++InitialClass->StoreCount;
         assert(InitialClass->StoreCount > 0);
       }
     }
   }
   InitialClass->Members.swap(InitialValues);
 
   // Initialize arguments to be in their own unique congruence classes

 #endif
   InstrDFS.clear();
   InstructionsToErase.clear();
 
   DFSToInstr.clear();
   BlockInstRange.clear();
   TouchedInstructions.clear();
   DominatedInstRange.clear();
-  MemoryAccessEquiv.clear();
+  MemoryAccessToClass.clear();
 }
 
 std::pair<unsigned, unsigned> NewGVN::assignDFSNumbers(BasicBlock *B,
                                                        unsigned Start) {
   unsigned End = Start;
   if (MemoryAccess *MemPhi = MSSA->getMemoryAccess(B)) {
     InstrDFS[MemPhi] = End++;
     DFSToInstr.emplace_back(MemPhi);
bool AllEqual = std::all_of(
       MappedBegin, MappedEnd,
       [&AllSameValue](const MemoryAccess *V) { return V == AllSameValue; });
 
   if (AllEqual)
     DEBUG(dbgs() << "Memory Phi value numbered to " << *AllSameValue << "\n");
   else
     DEBUG(dbgs() << "Memory Phi value numbered to itself\n");
 
-  if (setMemoryAccessEquivTo(MP, AllEqual ? AllSameValue : nullptr))
+  if (setMemoryAccessEquivTo(
+          MP, AllEqual ? MemoryAccessToClass.lookup(AllSameValue) : nullptr))
     markMemoryUsersTouched(MP);
 }
 
 // Value number a single instruction, symbolically evaluating, performing
 // congruence finding, and updating mappings.
 void NewGVN::valueNumberInstruction(Instruction *I) {
   DEBUG(dbgs() << "Processing instruction " << *I << "\n");
 

 // testing/debugging.
 void NewGVN::verifyMemoryCongruency() const {
   // Anything equivalent in the memory access table should be in the same
   // congruence class.
 
   // Filter out the unreachable and trivially dead entries, because they may
   // never have been updated if the instructions were not processed.
   auto ReachableAccessPred =
-      [&](const std::pair<const MemoryAccess *, MemoryAccess *> Pair) {
+      [&](const std::pair<const MemoryAccess *, CongruenceClass *> Pair) {
         bool Result = ReachableBlocks.count(Pair.first->getBlock());
         if (!Result)
           return false;
         if (auto *MemDef = dyn_cast<MemoryDef>(Pair.first))
           return !isInstructionTriviallyDead(MemDef->getMemoryInst());
         return true;
       };
 
-  auto Filtered = make_filter_range(MemoryAccessEquiv, ReachableAccessPred);
+  auto Filtered = make_filter_range(MemoryAccessToClass, ReachableAccessPred);
   for (auto KV : Filtered) {
-    assert(KV.first != KV.second &&
-           "We added a useless equivalence to the memory equivalence table");
     // Unreachable instructions may not have changed because we never process
     // them.
     if (!ReachableBlocks.count(KV.first->getBlock()))
       continue;
     if (auto *FirstMUD = dyn_cast<MemoryUseOrDef>(KV.first)) {
-      auto *SecondMUD = dyn_cast<MemoryUseOrDef>(KV.second);
+      auto *SecondMUD = dyn_cast<MemoryUseOrDef>(KV.second->RepMemoryAccess);
       if (FirstMUD && SecondMUD)
         assert((singleReachablePHIPath(FirstMUD, SecondMUD) ||
                 ValueToClass.lookup(FirstMUD->getMemoryInst()) ==
                     ValueToClass.lookup(SecondMUD->getMemoryInst())) &&
                "The instructions for these memory operations should have "
                "been in the same congruence class or reachable through"
                "a single argument phi");
     } else if (auto *FirstMP = dyn_cast<MemoryPhi>(KV.first)) {

llvm/trunk/test/Transforms/NewGVN/pr31594.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt < %s -basicaa -newgvn -S | FileCheck %s
 
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
-define void @patatino(i8* %blah, i32 %choice) {
+define i1 @patatino(i8* %blah, i32 %choice) {
 ; CHECK-LABEL: @patatino(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
 ; CHECK:       while.cond:
 ; CHECK-NEXT:    [[FOO:%.*]] = phi i8* [ [[BLAH:%.*]], [[ENTRY:%.*]] ], [ null, [[WHILE_BODY:%.*]] ]
 ; CHECK-NEXT:    switch i32 [[CHOICE:%.*]], label [[WHILE_BODY]] [
 ; CHECK-NEXT:    i32 -1, label [[WHILE_END:%.*]]
 ; CHECK-NEXT:    i32 40, label [[LAND_END:%.*]]
 ; CHECK-NEXT:    ]
 ; CHECK:       land.end:
 ; CHECK-NEXT:    br label [[WHILE_END]]
 ; CHECK:       while.body:
 ; CHECK-NEXT:    br label [[WHILE_COND]]
 ; CHECK:       while.end:
 ; CHECK-NEXT:    store i8 0, i8* [[FOO]], align 1
 ; CHECK-NEXT:    [[TMP0:%.*]] = load i8, i8* [[BLAH]], align 1
+; CHECK-NEXT:    [[LOADED:%.*]] = icmp eq i8 [[TMP0]], 0
 ; CHECK-NEXT:    store i8 0, i8* [[BLAH]], align 1
-; CHECK-NEXT:    ret void
+; CHECK-NEXT:    ret i1 [[LOADED]]
 ;
 entry:
   br label %while.cond
 
 while.cond:
   %foo = phi i8* [ %blah, %entry ], [ null, %while.body ]
   switch i32 %choice, label %while.body [
   i32 -1, label %while.end

 ;; These two stores will initially be considered equivalent, but then proven not.
 ;; the second store would previously end up deciding it's equivalent to a previous
 ;; store, but it was really just finding an optimistic version of itself
 ;; in the congruence class.
   store i8 0, i8* %foo.lcssa, align 1
   %0 = load i8, i8* %blah, align 1
   %loaded = icmp eq i8 %0, 0
   store i8 0, i8* %blah, align 1
-  ret void
+  ret i1 %loaded
 }
 
 
 ;; This is an example of a case where the memory states are equivalent solely due to unreachability,
 ;; but the stores are not equal.
 define void @foo(i8* %arg) {
 ; CHECK-LABEL: @foo(
 ; CHECK-NEXT:  bb: