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

1311 ↗

(On Diff #82427)

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

793 ↗

(On Diff #82427)

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

1311 ↗

(On Diff #82427)

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?

1327 ↗

(On Diff #82427)

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

1329 ↗

(On Diff #82427)

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

1445–1452 ↗

(On Diff #82427)

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

1311 ↗

(On Diff #82427)

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

1311 ↗

(On Diff #82427)

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

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

 #include "llvm/Transforms/Scalar/NewGVN.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SparseBitVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CFG.h"
class NewGVN : public FunctionPass {
   CongruenceClass *InitialClass;
   std::vector<CongruenceClass *> CongruenceClasses;
   unsigned NextCongruenceNum;
 
   // Value Mappings.
   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<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;
 
   // Reachability info.

 #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->op_empty()) {
     DEBUG(dbgs() << "Simplified PHI node " << *I << " to undef"
                  << "\n");
     E->deallocateOperands(ArgRecycler);
#endif
   DFSDomMap.clear();
   InstrDFS.clear();
   InstructionsToErase.clear();
 
   DFSToInstr.clear();
   BlockInstRange.clear();
   TouchedInstructions.clear();
   DominatedInstRange.clear();
+  MemoryAccessEquiv.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.
+  // Filter out unreachable blocks from our operands.
+  auto Filtered = make_filter_range(MP->operands(), [&](const Use &U) {
+    return ReachableBlocks.count(MP->getIncomingBlock(U));
+  });
+
+  assert(Filtered.begin() != Filtered.end() &&
+         "We should not be processing a MemoryPhi in a completely "
+         "unreachable block");
+
+  // Transform the remaining operands into operand leaders.
+  // FIXME: mapped_iterator should have a range version.
+  auto LookupFunc = [&](const Use &U) {
+    return lookupMemoryAccessEquiv(cast<MemoryAccess>(U));
+  };
+  auto MappedBegin = map_iterator(Filtered.begin(), LookupFunc);
+  auto MappedEnd = map_iterator(Filtered.end(), LookupFunc);
+
+  // and now check if all the elements are equal.
+  // Sadly, we can't use std::equals since these are random access iterators.
+  MemoryAccess *AllSameValue = *MappedBegin;
+  ++MappedBegin;
+  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))
+    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);
-        continue;
-      }
-      updateProcessedCount(I);
 
-      if (!I->isTerminator()) {
-        const Expression *Symbolized = performSymbolicEvaluation(I, CurrBlock);
-        performCongruenceFinding(I, Symbolized);
+      if (MemoryPhi *MP = dyn_cast<MemoryPhi>(V)) {
+        DEBUG(dbgs() << "Processing MemoryPhi " << *MP << "\n");
+        valueNumberMemoryPhi(MP);
+      } else if (Instruction *I = dyn_cast<Instruction>(V)) {
+        valueNumberInstruction(I);
       } else {
-        processOutgoingEdges(dyn_cast<TerminatorInst>(I), CurrBlock);
+        llvm_unreachable("Should have been a MemoryPhi or Instruction");
       }
+      updateProcessedCount(V);
       // Reset after processing (because we may mark ourselves as touched when
       // we propagate equalities).
       TouchedInstructions.reset(InstrNum);
     }
   }
 
   Changed |= eliminateInstructions(F);
 

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

+; RUN: opt -newgvn -S < %s | FileCheck %s
+; RUN: opt -passes=newgvn -S -o - %s | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+;; All the loads in this testcase are useless, but it requires understanding that repeated
+;; stores of the same value do not change the memory state to eliminate them.
+
+define i32 @foo(i32*, i32)  {
+; CHECK-LABEL: @foo
+  store i32 5, i32* %0, align 4
+  %3 = icmp ne i32 %1, 0
+  br i1 %3, label %4, label %7
+
+; <label>:4:                                      ; preds = %2
+; CHECK-NOT: load
+  %5 = load i32, i32* %0, align 4
+; CHECK-NOT: add
+  %6 = add nsw i32 5, %5
+  br label %7
+
+; <label>:7:                                      ; preds = %4, %2
+  %.0 = phi i32 [ %6, %4 ], [ 5, %2 ]
+; CHECK: phi i32 [ 10, %4 ], [ 5, %2 ]
+  store i32 5, i32* %0, align 4
+; CHECK-NOT: icmp
+  %8 = icmp ne i32 %1, 0
+; CHECK: br i1 %3
+  br i1 %8, label %9, label %12
+
+; <label>:9:                                      ; preds = %7
+; CHECK-NOT: load
+  %10 = load i32, i32* %0, align 4
+; CHECK: add nsw i32 %.0, 5
+  %11 = add nsw i32 %.0, %10
+  br label %12
+
+; <label>:12:                                     ; preds = %9, %7
+  %.1 = phi i32 [ %11, %9 ], [ %.0, %7 ]
+  ret i32 %.1
+}
+
+;; This is similar to the above, but it is a conditional store of the same value
+;; which requires value numbering MemoryPhi properly to resolve.
+define i32 @foo2(i32*, i32)  {
+; CHECK-LABEL: @foo2
+  store i32 5, i32* %0, align 4
+  %3 = icmp ne i32 %1, 0
+  br i1 %3, label %4, label %7
+
+; <label>:4:                                      ; preds = %2
+; CHECK-NOT: load
+  %5 = load i32, i32* %0, align 4
+; CHECK-NOT: add
+  %6 = add nsw i32 5, %5
+  br label %8
+
+; <label>:7:                                      ; preds = %2
+  store i32 5, i32* %0, align 4
+  br label %8
+
+; <label>:8:                                      ; preds = %7, %4
+; CHECK: phi i32 [ 10, %4 ], [ 5, %5 ]
+  %.0 = phi i32 [ %6, %4 ], [ 5, %7 ]
+; CHECK-NOT: icmp
+  %9 = icmp ne i32 %1, 0
+; CHECK: br i1 %3
+  br i1 %9, label %10, label %13
+
+; <label>:10:                                     ; preds = %8
+; CHECK-NOT: load
+  %11 = load i32, i32* %0, align 4
+; CHECK: add nsw i32 %.0, 5
+  %12 = add nsw i32 %.0, %11
+  br label %13
+
+; <label>:13:                                     ; preds = %10, %8
+  %.1 = phi i32 [ %12, %10 ], [ %.0, %8 ]
+  ret i32 %.1
+}