NewGVN: Fix PR31480, PR31483, PR31499, by rewriting how memory congruence handling works.

[• dberlin]

Summary

Previously, we tried to fix up the equivalences during symbolic evaluation. This does not work. Now, we change the equivalences during congruence finding, where it belongs. We also initialize the equivalence table to give a maximal answer.

[davide]

Thanks for working on this! Some initial comments inline.

lib/Transforms/Scalar/NewGVN.cpp

776–781 ↗

(On Diff #82757)

This can maybe be expressed using a one-liner with the ternary operator, I find it slightly better, if you think this version is more readable you can keep it as is (I don't have a strong opinion).

1056–1064 ↗

(On Diff #82757)

These two changes look like they can be committed in isolation (the improved debug message && the assertion), unless the latter fires without this change.

1104–1110 ↗

(On Diff #82757)

This comment looks formatted in a strange way -- it could just be phab, in that case please ignore.

1114 ↗

(On Diff #82757)

s/expresion/expressions/

1591–1594 ↗

(On Diff #82757)

Yay for the verifier. We should keep this under NDEBUG anyway as there's no bot handling LLVM_EXPENSIVE_CHECKS (because, such a shame, there are still tests failing in that configuration).

[• dberlin]

Ugh.
Sorry, i dcommitted the wrong branch.
Fixes coming!

[• dberlin]

Comments should be addressed in r290820, please feel free to add any more and i'll happily keep addressing them.

[• dberlin]

the testcase is on the other branch, i'll move it over.

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

private:
   void handleNewInstruction(Instruction *){};
   void markUsersTouched(Value *);
   void markMemoryUsersTouched(MemoryAccess *);
 
   // Utilities.
   void cleanupTables();
   std::pair<unsigned, unsigned> assignDFSNumbers(BasicBlock *, unsigned);
   void updateProcessedCount(Value *V);
+  void verifyMemoryCongruency();
 };
 
 char NewGVN::ID = 0;
 
 // createGVNPass - The public interface to this file.
 FunctionPass *llvm::createNewGVNPass() { return new NewGVN(); }
 
 template <typename T>
const StoreExpression *NewGVN::createStoreExpression(StoreInst *SI,
   // TODO: Value number heap versions. We may be able to discover
   // things alias analysis can't on it's own (IE that a store and a
   // load have the same value, and thus, it isn't clobbering the load).
   return E;
 }
 
 const Expression *NewGVN::performSymbolicStoreEvaluation(Instruction *I,
                                                          const BasicBlock *B) {
+  // Unlike loads, we never try to eliminate stores, so we do not check if they
+  // are simple and avoid value numbering them.
   auto *SI = cast<StoreInst>(I);
   // If this store's memorydef stores the same value as the last store, the
   // memory accesses are equivalent.
   // Get the expression, if any, for the RHS of the MemoryDef.
   MemoryAccess *StoreAccess = MSSA->getMemoryAccess(SI);
   MemoryAccess *StoreRHS = lookupMemoryAccessEquiv(
       cast<MemoryDef>(StoreAccess)->getDefiningAccess());
   const Expression *OldStore = createStoreExpression(SI, StoreRHS, B);
   // See if this store expression already has a value, and it's the same as our
-  // current store.
+  // current store.  FIXME: Right now, we only do this for simple stores.
+  if (SI->isSimple()) {
     CongruenceClass *CC = ExpressionToClass.lookup(OldStore);
-  if (CC &&
-      CC->RepLeader == lookupOperandLeader(SI->getValueOperand(), SI, B)) {
-    setMemoryAccessEquivTo(StoreAccess, StoreRHS);
-    return OldStore;
+    if (CC && CC->DefiningExpr && isa<StoreExpression>(CC->DefiningExpr) &&
+        CC->RepLeader == lookupOperandLeader(SI->getValueOperand(), SI, B))
+      return createStoreExpression(SI, StoreRHS, B);
   }
+
   return createStoreExpression(SI, StoreAccess, B);
 }
 
 const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I,
                                                         const BasicBlock *B) {
   auto *LI = cast<LoadInst>(I);
 
   // We can eliminate in favor of non-simple loads, but we won't be able to
-  // eliminate them.
+  // eliminate the loads themselves.
   if (!LI->isSimple())
     return nullptr;
 
   Value *LoadAddressLeader = lookupOperandLeader(LI->getPointerOperand(), I, B);
   // Load of undef is undef.
   if (isa<UndefValue>(LoadAddressLeader))
     return createConstantExpression(UndefValue::get(LI->getType()));
 
if (AA->onlyReadsMemory(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) {
-  auto LookupResult = MemoryAccessEquiv.insert({From, nullptr});
+  DEBUG(dbgs() << "Setting " << *From << " equivalent to ");
+  if (!To)
+    DEBUG(dbgs() << "itself");
+  else
+    DEBUG(dbgs() << *To);
+  DEBUG(dbgs() << "\n");
+  auto LookupResult = MemoryAccessEquiv.find(From);
   bool Changed = false;
   // If it's already in the table, see if the value changed.
-  if (LookupResult.second) {
-    if (To && LookupResult.first->second != To) {
+  if (LookupResult != MemoryAccessEquiv.end()) {
+    if (To && LookupResult->second != To) {
       // It wasn't equivalent before, and now it is.
-      LookupResult.first->second = To;
+      LookupResult->second = To;
       Changed = true;
     } else if (!To) {
       // It used to be equivalent to something, and now it's not.
-      MemoryAccessEquiv.erase(LookupResult.first);
+      MemoryAccessEquiv.erase(LookupResult);
       Changed = true;
     }
-  } else if (To) {
-    // It wasn't in the table, but is equivalent to something.
-    LookupResult.first->second = To;
-    Changed = true;
+  } else {
+    assert(!To &&
+           "Memory equivalence should never change from nothing to something");
   }
+
   return Changed;
 }
 // Evaluate PHI nodes symbolically, and create an expression result.
 const Expression *NewGVN::performSymbolicPHIEvaluation(Instruction *I,
                                                        const BasicBlock *B) {
   auto *E = cast<PHIExpression>(createPHIExpression(I));
   if (E->op_empty()) {
     DEBUG(dbgs() << "Simplified PHI node " << *I << " to undef"
if (lookupResult.second) {
       else if (const auto *SE = dyn_cast<StoreExpression>(E))
         NewClass->RepLeader = SE->getStoreInst()->getValueOperand();
       else
         NewClass->RepLeader = V;
 
       EClass = NewClass;
       DEBUG(dbgs() << "Created new congruence class for " << *V
                    << " using expression " << *E << " at " << NewClass->ID
-                   << "\n");
+                   << " and leader " << *(NewClass->RepLeader) << "\n");
       DEBUG(dbgs() << "Hash value was " << E->getHashValue() << "\n");
     } else {
       EClass = lookupResult.first->second;
+      if (isa<ConstantExpression>(E))
+        assert(isa<Constant>(EClass->RepLeader) &&
+               "Any class with a constant expression should have a "
+               "constant leader");
+
       assert(EClass && "Somehow don't have an eclass");
 
       assert(!EClass->Dead && "We accidentally looked up a dead class");
     }
   }
   bool WasInChanged = ChangedValues.erase(V);
   if (VClass != EClass || WasInChanged) {
     DEBUG(dbgs() << "Found class " << EClass->ID << " for expression " << E
if (VClass != EClass) {
         VClass->RepLeader = *(VClass->Members.begin());
         for (auto M : VClass->Members) {
           if (auto *I = dyn_cast<Instruction>(M))
             TouchedInstructions.set(InstrDFS[I]);
           ChangedValues.insert(M);
         }
       }
     }
+
     markUsersTouched(V);
-    if (auto *I = dyn_cast<Instruction>(V))
-      if (MemoryAccess *MA = MSSA->getMemoryAccess(I))
+    if (auto *I = dyn_cast<Instruction>(V)) {
+      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. Note that currently, we do not guarantee the
+        // "different" memory state dominates us.  The goal is to make things
+        // that are congruent look congruent, not ensure we can eliminate one in
+        // favor of the other.
+        // Right now, the only way they can be equivalent is for store
+        // expresions.
+        if (!isa<MemoryUse>(MA)) {
+          if (E && isa<StoreExpression>(E) && EClass->Members.size() != 1) {
+            auto *DefAccess = cast<StoreExpression>(E)->getDefiningAccess();
+            setMemoryAccessEquivTo(MA, DefAccess != MA ? DefAccess : nullptr);
+          } else {
+            setMemoryAccessEquivTo(MA, nullptr);
+          }
+        }
         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) {
       DEBUG(dbgs() << "Block " << getBlockName(To) << " marked reachable\n");
       const auto &InstRange = BlockInstRange.lookup(To);
       TouchedInstructions.set(InstRange.first, InstRange.second);
     } else {
       DEBUG(dbgs() << "Block " << getBlockName(To)
                    << " was reachable, but new edge {" << getBlockName(From)
                    << "," << getBlockName(To) << "} to it found\n");
 
       // We've made an edge reachable to an existing block, which may
       // impact predicates. Otherwise, only mark the phi nodes as touched, as
       // they are the only thing that depend on new edges. Anything using their
       // values will get propagated to if necessary.
+      if (MemoryAccess *MemPhi = MSSA->getMemoryAccess(To))
+        TouchedInstructions.set(InstrDFS[MemPhi]);
+
       auto BI = To->begin();
       while (isa<PHINode>(BI)) {
         TouchedInstructions.set(InstrDFS[&*BI]);
         ++BI;
       }
     }
   }
 }
if ((BR = dyn_cast<BranchInst>(TI)) && BR->isConditional()) {
     }
   } else {
     // Otherwise this is either unconditional, or a type we have no
     // idea about. Just mark successors as reachable.
     for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
       BasicBlock *TargetBlock = TI->getSuccessor(i);
       updateReachableEdge(B, TargetBlock);
     }
+
+    // This also may be a memory defining terminator, in which case, set it
+    // equivalent to nothing.
+    if (MemoryAccess *MA = MSSA->getMemoryAccess(TI))
+      setMemoryAccessEquivTo(MA, nullptr);
   }
 }
 
 // The algorithm initially places the values of the routine in the INITIAL
 // congruence
 // 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);
-  for (auto &B : F)
+  for (auto &B : F) {
+    if (auto *MP = MSSA->getMemoryAccess(&B))
+      MemoryAccessEquiv.insert({MP, MSSA->getLiveOnEntryDef()});
+
     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()});
+    }
   InitialClass->Members.swap(InitialValues);
 
   // Initialize arguments to be in their own unique congruence classes
   for (auto &FA : F.args())
     createSingletonCongruenceClass(&FA);
 }
 
 void NewGVN::cleanupTables() {
void NewGVN::valueNumberInstruction(Instruction *I) {
   if (!I->isTerminator()) {
     const Expression *Symbolized = performSymbolicEvaluation(I, I->getParent());
     performCongruenceFinding(I, Symbolized);
   } else {
     processOutgoingEdges(dyn_cast<TerminatorInst>(I), I->getParent());
   }
 }
 
+// Verify the that the memory equivalence table makes sense relative to the
+// congruence classes.
+void NewGVN::verifyMemoryCongruency() {
+  // 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) {
+        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);
+  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);
+      if (FirstMUD && SecondMUD) {
+        auto *FirstInst = FirstMUD->getMemoryInst();
+        auto *SecondInst = SecondMUD->getMemoryInst();
+        assert(
+            ValueToClass.lookup(FirstInst) == ValueToClass.lookup(SecondInst) &&
+            "The instructions for these memory operations should have been in "
+            "the same congruence class");
+      }
+    } else if (auto *FirstMP = dyn_cast<MemoryPhi>(KV.first)) {
+
+      // We can only sanely verify that MemoryDefs in the operand list all have
+      // the same class.
+      auto ReachableOperandPred = [&](const Use &U) {
+        return ReachableBlocks.count(FirstMP->getIncomingBlock(U)) &&
+               isa<MemoryDef>(U);
+
+      };
+      // All arguments should in the same class, ignoring unreachable arguments
+      auto FilteredPhiArgs =
+          make_filter_range(FirstMP->operands(), ReachableOperandPred);
+      SmallVector<const CongruenceClass *, 16> PhiOpClasses;
+      std::transform(FilteredPhiArgs.begin(), FilteredPhiArgs.end(),
+                     std::back_inserter(PhiOpClasses), [&](const Use &U) {
+                       const MemoryDef *MD = cast<MemoryDef>(U);
+                       return ValueToClass.lookup(MD->getMemoryInst());
+                     });
+      assert(std::equal(PhiOpClasses.begin(), PhiOpClasses.end(),
+                        PhiOpClasses.begin()) &&
+             "All MemoryPhi arguments should be in the same class");
+    }
+  }
+}
+
 // This is the main transformation entry point.
 bool NewGVN::runGVN(Function &F, DominatorTree *_DT, AssumptionCache *_AC,
                     TargetLibraryInfo *_TLI, AliasAnalysis *_AA,
                     MemorySSA *_MSSA) {
   bool Changed = false;
   DT = _DT;
   AC = _AC;
   TLI = _TLI;
for (int InstrNum = TouchedInstructions.find_first(); InstrNum != -1;
       }
       updateProcessedCount(V);
       // Reset after processing (because we may mark ourselves as touched when
       // we propagate equalities).
       TouchedInstructions.reset(InstrNum);
     }
   }
 
+// FIXME: Move this to expensive checks when we are satisfied with NewGVN
+#ifndef NDEBUG
+  verifyMemoryCongruency();
+#endif
   Changed |= eliminateInstructions(F);
 
   // Delete all instructions marked for deletion.
   for (Instruction *ToErase : InstructionsToErase) {
     if (!ToErase->use_empty())
       ToErase->replaceAllUsesWith(UndefValue::get(ToErase->getType()));
 
     ToErase->eraseFromParent();