Value number stores and memory states so we can detect when memory states are equivalent (IE store of same value to memory). Tests coming.

[• dberlin]

• Add comments and fix a small issue with processed counts.

Updating D28084: Value number stores and memory states so we can detect when memory

states are equivalent (IE store of same value to memory).
Tests coming.

[• dberlin]

lib/Transforms/Scalar/NewGVN.cpp

1304

It would be nice to share this part with performSymbolicPHIEvaluation, but we use a different lookup.
Thoughts welcome.

[davide]

This is very nice. I think I got the latest revision (unless there's an issue with phabricator) and I see many tests in Transform/NewGVN failing, some of them hitting the assertion in updateProcessedCount().
In the meanwhile, some minor comment inline.

lib/Transforms/Scalar/NewGVN.cpp

787

Nit: Comments terminate with a full stop (here and elsewhere).

1304

I agree it's not great to have the logic in two different places, I'll think about it. Maybe we can add a FIXME in the meanwhile?

1320

I think the correct spelling is #ifndef NDEBUG unless you mean something else (I'm not entirely sure there's a DEBUG macro)

1322

This could be DEBUG(dbgs() ...)

1438–1447

Nit: the style guide suggests to uses braces around the else as well.

[davide]

The failures happen only in a Debug+Assert build, FWIW.

[• dberlin]

• Update for review comments, add tests, fix porting bug

Updating D28084: Value number stores and memory states so we can detect when memory

states are equivalent (IE store of same value to memory).
Tests coming.

[• dberlin]

lib/Transforms/Scalar/NewGVN.cpp

1304

I've cleaned up this version, i'll clean up the other version in a followup and see if we can merge them using a template function.

[• dberlin]

• Update for review comments, add tests

Updating D28084: Value number stores and memory states so we can detect when memory

states are equivalent (IE store of same value to memory).
Tests coming.

[davide]

LGTM

[davide]

lib/Transforms/Scalar/NewGVN.cpp

1304

Yeah, feel free to handle it in a follow-up.

lib/Transforms/Scalar/NewGVN.cpp

class NewGVN : public FunctionPass {
   // Congruence class info.
   CongruenceClass *InitialClass;
   std::vector<CongruenceClass *> CongruenceClasses;
   unsigned NextCongruenceNum;
 
   // Value Mappings.
   DenseMap<Value *, CongruenceClass *> ValueToClass;
   DenseMap<Value *, const Expression *> ValueToExpression;
+  DenseMap<MemoryAccess *, MemoryAccess *> MemoryAccessEquiv;
 
   // Expression to class mapping.
   typedef DenseMap<const Expression *, CongruenceClass *> ExpressionClassMap;
   ExpressionClassMap ExpressionToClass;
 
   // Which values have changed as a result of leader changes.
   SmallPtrSet<Value *, 8> ChangedValues;
 

 #ifndef NDEBUG
   // Debugging for how many times each block and instruction got processed.
   DenseMap<const Value *, unsigned> ProcessedCount;
 #endif
 
   // DFS info.
   DenseMap<const BasicBlock *, std::pair<int, int>> DFSDomMap;
   DenseMap<const Value *, unsigned> InstrDFS;
-  std::vector<Instruction *> DFSToInstr;
+  std::vector<Value *> DFSToInstr;
 
   // Deletion info.
   SmallPtrSet<Instruction *, 8> InstructionsToErase;
 
 public:
   static char ID; // Pass identification, replacement for typeid.
   NewGVN() : FunctionPass(ID) {
     initializeNewGVNPass(*PassRegistry::getPassRegistry());
private:
   CongruenceClass *createSingletonCongruenceClass(Value *Member) {
     CongruenceClass *CClass = createCongruenceClass(Member, NULL);
     CClass->Members.insert(Member);
     ValueToClass[Member] = CClass;
     return CClass;
   }
   void initializeCongruenceClasses(Function &F);
 
+  // Value number an Instruction or MemoryPhi.
+  void valueNumberMemoryPhi(MemoryPhi *);
+  void valueNumberInstruction(Instruction *);
+
   // Symbolic evaluation.
   const Expression *checkSimplificationResults(Expression *, Instruction *,
                                                Value *);
   const Expression *performSymbolicEvaluation(Value *, const BasicBlock *);
   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(Value *, const Expression *);
 
   // 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 &,
                                 std::vector<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->RepLeader;
   return V;
 }
 
+MemoryAccess *NewGVN::lookupMemoryAccessEquiv(MemoryAccess *MA) const {
+  MemoryAccess *Result = MemoryAccessEquiv.lookup(MA);
+  return Result ? Result : MA;
+}
+
 LoadExpression *NewGVN::createLoadExpression(Type *LoadType, Value *PointerOp,
                                              LoadInst *LI, MemoryAccess *DA,
                                              const BasicBlock *B) {
   LoadExpression *E = new (ExpressionAllocator) LoadExpression(1, LI, DA);
   E->allocateOperands(ArgRecycler, ExpressionAllocator);
   E->setType(LoadType);
 
   // Give store and loads same opcode so they value number together.
const StoreExpression *NewGVN::createStoreExpression(StoreInst *SI,
   // 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) {
   StoreInst *SI = cast<StoreInst>(I);
-  const Expression *E = createStoreExpression(SI, MSSA->getMemoryAccess(SI), B);
-  return E;
+  // 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.
+  CongruenceClass *CC = ExpressionToClass.lookup(OldStore);
+  if (CC &&
+      CC->RepLeader == lookupOperandLeader(SI->getValueOperand(), SI, B)) {
+    setMemoryAccessEquivTo(StoreAccess, StoreRHS);
+    return OldStore;
+  }
+  return createStoreExpression(SI, StoreAccess, B);
 }
 
 const Expression *NewGVN::performSymbolicLoadEvaluation(Instruction *I,
                                                         const BasicBlock *B) {
   LoadInst *LI = cast<LoadInst>(I);
 
   // We can eliminate in favor of non-simple loads, but we won't be able to
   // eliminate them.
if (!MSSA->isLiveOnEntryDef(DefiningAccess)) {
     if (auto *MD = dyn_cast<MemoryDef>(DefiningAccess)) {
       Instruction *DefiningInst = MD->getMemoryInst();
       // If the defining instruction is not reachable, replace with undef.
       if (!ReachableBlocks.count(DefiningInst->getParent()))
         return createConstantExpression(UndefValue::get(LI->getType()));
     }
   }
 
-  const Expression *E = createLoadExpression(
-      LI->getType(), LI->getPointerOperand(), LI, DefiningAccess, B);
+  const Expression *E =
+      createLoadExpression(LI->getType(), LI->getPointerOperand(), LI,
+                           lookupMemoryAccessEquiv(DefiningAccess), B);
   return E;
 }
 
 // Evaluate read only and pure calls, and create an expression result.
 const Expression *NewGVN::performSymbolicCallEvaluation(Instruction *I,
                                                         const BasicBlock *B) {
   CallInst *CI = cast<CallInst>(I);
   if (AA->doesNotAccessMemory(CI))
     return createCallExpression(CI, nullptr, B);
   else if (AA->onlyReadsMemory(CI))
     return createCallExpression(CI, MSSAWalker->getClobberingMemoryAccess(CI),
                                 B);
   else
     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});
+  bool Changed = false;
+  // If it's already in the table, see if the value changed
+  if (LookupResult.second) {
+    if (To && LookupResult.first->second != To) {
+      // It wasn't equivalent before, and now it is.
+      LookupResult.first->second = To;
+      Changed = true;
+    } else if (!To) {
+      // It used to be equivalent to something, and now it's not.
+      MemoryAccessEquiv.erase(LookupResult.first);
+      Changed = true;
+    }
+  } else if (To) {
+    // It wasn't in the table, but is equivalent to something
+    LookupResult.first->second = To;
+    Changed = true;
+  }
+  return Changed;
+}
 // Evaluate PHI nodes symbolically, and create an expression result.
 const Expression *NewGVN::performSymbolicPHIEvaluation(Instruction *I,
                                                        const BasicBlock *B) {
   PHIExpression *E = cast<PHIExpression>(createPHIExpression(I));
   if (E->ops_empty()) {
     DEBUG(dbgs() << "Simplified PHI node " << *I << " to undef"
                  << "\n");
     E->deallocateOperands(ArgRecycler);
#endif
   BlockInstRange.clear();
   TouchedInstructions.clear();
   DominatedInstRange.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);
+  }
+
   for (auto &I : *B) {
     InstrDFS[&I] = End++;
     DFSToInstr.emplace_back(&I);
   }
 
   // All of the range functions taken half-open ranges (open on the end side).
   // So we do not subtract one from count, because at this point it is one
   // greater than the last instruction.
   return std::make_pair(Start, End);
 }
 
 void NewGVN::updateProcessedCount(Value *V) {
 #ifndef NDEBUG
   if (ProcessedCount.count(V) == 0) {
     ProcessedCount.insert({V, 1});
   } else {
     ProcessedCount[V] += 1;
     assert(ProcessedCount[V] < 100 &&
            "Seem to have processed the same Value a lot\n");
   }
 #endif
 }
+// Evaluate MemoryPhi nodes symbolically, just like PHI nodes
+void NewGVN::valueNumberMemoryPhi(MemoryPhi *MP) {
+  // If all the arguments are the same, the MemoryPhi has the same value as the
+  // argument.
+  MemoryAccess *AllSameValue = nullptr;
+  // See if all arguments are the same, ignoring unreachable arguments
+  for (unsigned i = 0, e = MP->getNumOperands(); i < e; ++i) {
+    BasicBlock *B = MP->getIncomingBlock(i);
+    if (!ReachableBlocks.count(B))
+      continue;
+    MemoryAccess *Operand =
+        lookupMemoryAccessEquiv(cast<MemoryAccess>(MP->getOperand(i)));
+    if (AllSameValue && AllSameValue != Operand) {
+      // Phi node does not have equal arguments, this phi node value numbers to
+      // itself.
+      AllSameValue = nullptr;
+      break;
+    } else if (!AllSameValue) {
+      AllSameValue = Operand;
+    }
+  }
+#ifdef DEBUG
+  if (AllSameValue)
+    dbgs() << "Memory Phi value numbered to " << *AllSameValue << "\n";
+  else
+    dbgs() << "Memory Phi value numbered to itself\n";
+#endif
+
+  if (setMemoryAccessEquivTo(MP, AllSameValue))
+    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");
+  if (I->use_empty() && !I->getType()->isVoidTy()) {
+    DEBUG(dbgs() << "Skipping unused instruction\n");
+    if (isInstructionTriviallyDead(I, TLI))
+      markInstructionForDeletion(I);
+    return;
+  }
+  if (!I->isTerminator()) {
+    const Expression *Symbolized = performSymbolicEvaluation(I, I->getParent());
+    performCongruenceFinding(I, Symbolized);
+  } else {
+    processOutgoingEdges(dyn_cast<TerminatorInst>(I), I->getParent());
+  }
+}
 
 // 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;
bool NewGVN::runGVN(Function &F, DominatorTree *_DT, AssumptionCache *_AC,
   initializeCongruenceClasses(F);
 
   // We start out in the entry block.
   BasicBlock *LastBlock = &F.getEntryBlock();
   while (TouchedInstructions.any()) {
     // Walk through all the instructions in all the blocks in RPO.
     for (int InstrNum = TouchedInstructions.find_first(); InstrNum != -1;
          InstrNum = TouchedInstructions.find_next(InstrNum)) {
-      Instruction *I = DFSToInstr[InstrNum];
-      BasicBlock *CurrBlock = I->getParent();
+      Value *V = DFSToInstr[InstrNum];
+      BasicBlock *CurrBlock = nullptr;
+
+      if (Instruction *I = dyn_cast<Instruction>(V))
+        CurrBlock = I->getParent();
+      else if (MemoryPhi *MP = dyn_cast<MemoryPhi>(V))
+        CurrBlock = MP->getBlock();
+      else
+        llvm_unreachable("DFSToInstr gave us an unknown type of instruction");
 
       // If we hit a new block, do reachability processing.
       if (CurrBlock != LastBlock) {
         LastBlock = CurrBlock;
         bool BlockReachable = ReachableBlocks.count(CurrBlock);
         const auto &CurrInstRange = BlockInstRange.lookup(CurrBlock);
 
         // If it's not reachable, erase any touched instructions and move on.
         if (!BlockReachable) {
           TouchedInstructions.reset(CurrInstRange.first, CurrInstRange.second);
           DEBUG(dbgs() << "Skipping instructions in block "
                        << getBlockName(CurrBlock)
                        << " because it is unreachable\n");
           continue;
         }
         updateProcessedCount(CurrBlock);
       }
-      DEBUG(dbgs() << "Processing instruction " << *I << "\n");
-      if (I->use_empty() && !I->getType()->isVoidTy()) {
-        DEBUG(dbgs() << "Skipping unused instruction\n");
-        if (isInstructionTriviallyDead(I, TLI))
-          markInstructionForDeletion(I);
-        TouchedInstructions.reset(InstrNum);
+
+      if (MemoryPhi *MP = dyn_cast<MemoryPhi>(V)) {
+        DEBUG(dbgs() << "Processing MemoryPhi " << *MP << "\n");
+        valueNumberMemoryPhi(MP);
         continue;
-      }
+      } else if (Instruction *I = dyn_cast<Instruction>(V)) {
         updateProcessedCount(I);
-
-      if (!I->isTerminator()) {
-        const Expression *Symbolized = performSymbolicEvaluation(I, CurrBlock);
-        performCongruenceFinding(I, Symbolized);
-      } else {
-        processOutgoingEdges(dyn_cast<TerminatorInst>(I), CurrBlock);
-      }
+        valueNumberInstruction(I);
+      } else
+        llvm_unreachable("Should have been a MemoryPhi or Instruction");
       // Reset after processing (because we may mark ourselves as touched when
       // we propagate equalities).
       TouchedInstructions.reset(InstrNum);
     }
   }
 
   Changed |= eliminateInstructions(F);
 
   // Delete all instructions marked for deletion.