NewGVN: Add basic dead store elimination

[• dberlin]

Summary

This adds basic dead store elimination to NewGVN. Unlike our current
DSE, it will happily do cross-block DSE if it meets our requirements.

We get a bunch of DSE's simple.ll cases, and some stuff it doesn't.
Unlike DSE, however, we only try to eliminate stores of the same value
to the same memory location, not just general stores to the same
memory location.

[• dberlin]

lib/Transforms/Scalar/NewGVN.cpp

2223

I'll remove the {'s.

2273

This is leftover from when i was trying to only walk the members once, but harmless.
removing it.

[• dberlin]

This version is slightly busted, it's missing the hasMemberOtherThanUs check, which it turns out we do need.
Posting updated patch in a second.

[efriedma]

Not sure I would call this dead store elimination; you aren't proving the store is dead, just that it's redundant.

[• dberlin]

In D29149#656853, @efriedma wrote:

Not sure I would call this dead store elimination; you aren't proving the store is dead, just that it's redundant.

We actually prove both in some cases?
Happy to call it whatever.

Most value numbering implementations call it dead store elimination.

Note that our current DSE is the same in some cases. Some stores it proves dead, some redundant.

See, e.g, eliminateNoopStore

[efriedma]

Most value numbering implementations call it dead store elimination.

That's a good reason to continue using that name.

[davide]

The logic is sound, I left some comments inline while I try on my tests and see how it performs =)

lib/Transforms/Scalar/NewGVN.cpp

90

I would use "dead/redundant stores eliminated" here, but up to you.

351–352

This constness is independent? Probably it's not worth changing it separately, just checking.

1496–1503

Is there a way to test this behaviour? (self-referencing phis)

1972–1979

Add a comment (at the top of the function) to explain what this function is doing?

1986

This comment can be probably removed, as it *must* be an instruction =)

2126

Spurious newline? Here and the next two)

2154–2156

I still prefer the explicit type here as it's not obvious which is (well the name implies, but still). Anyway, up to you.

2273

Thanks.

[• dberlin]

This now depends on a fix for 31761 to be committed, but otherwise shoudl be in good shape once i added the self-reference testcase.

lib/Transforms/Scalar/NewGVN.cpp

90

fixed

351–352

yes

1496–1503

It's hard to get it to occur naturall
I believe i can add an irreducible testcase where the phis are in a cycle that resolves to themselves.

1972–1979

Done

2126

Killed

2154–2156

I put it back

[• dberlin]

Depends on PR31761 fix now, and rebased on top of it.
- Update for review comments
- Add testcase for being optimistic on self-phis

[davide]

LGTM (left some nits inline). You marked some earlier comments as done but the old code still shows up, probably you updated an earlier diff. Anyway, this can go in without a new round of review with the comments addressed.

lib/Transforms/Scalar/NewGVN.cpp

763–769

This #if 1 can go away, I think.

1214–1218

This can go away, no?

2342

Typo: s/dominater/dominated/

test/Transforms/NewGVN/basic-cyclic-opt.ll

230–243 ↗

(On Diff #85950)

thank you very much =)

test/Transforms/NewGVN/pr31758.ll

1–19 ↗

(On Diff #85950)

It seems this test is unrelated (no stores) and you already committed it, FWIW.

[• dberlin]

Sorry, most of the issues here are because arc picked up the rebase, and isn't showing the fix for 31761 as the base.
(the fix is what contains the #if blocks, etc)

lib/Transforms/Scalar/NewGVN.cpp

 STATISTIC(NumGVNMaxIterations,
           "Maximum Number of iterations it took to converge GVN");
 STATISTIC(NumGVNLeaderChanges, "Number of leader changes");
 STATISTIC(NumGVNSortedLeaderChanges, "Number of sorted leader changes");
 STATISTIC(NumGVNAvoidedSortedLeaderChanges,
           "Number of avoided sorted leader changes");
 STATISTIC(NumGVNNotMostDominatingLeader,
           "Number of times a member dominated it's new classes' leader");
+STATISTIC(NumGVNDeadStores, "Number of dead stores eliminated");
 
 //===----------------------------------------------------------------------===//
 //                                GVN Pass
 //===----------------------------------------------------------------------===//
 
 // Anchor methods.
 namespace llvm {
 namespace GVNExpression {
private:
   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 &,
+  void convertDenseToDFSOrdered(const CongruenceClass::MemberSet &,
+                                SmallVectorImpl<ValueDFS> &);
+  void convertDenseToLoadsAndStores(const CongruenceClass::MemberSet &,
                                     SmallVectorImpl<ValueDFS> &);
 
   bool eliminateInstructions(Function &);
   void replaceInstruction(Instruction *, Value *);
   void markInstructionForDeletion(Instruction *);
   void deleteInstructionsInBlock(BasicBlock *);
 
   // New instruction creation.
   void handleNewInstruction(Instruction *){};

 }
 
 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);
   MemoryAccess *StoreAccess = MSSA->getMemoryAccess(SI);
-  // See if we are defined by a previous store expression, it already has a
-  // value, and it's the same value as our current store. FIXME: Right now, we
-  // only do this for simple stores, we should expand to cover memcpys, etc.
-  if (SI->isSimple()) {
-    // Get the expression, if any, for the RHS of the MemoryDef.
-    MemoryAccess *StoreRHS = lookupMemoryAccessEquiv(
-        cast<MemoryDef>(StoreAccess)->getDefiningAccess());
+  // If we are defined by ourselves, use the live on entry def.
+  if (StoreRHS == StoreAccess)
+    StoreRHS = MSSA->getLiveOnEntryDef();
+
+  if (SI->isSimple()) {
+    // See if we are defined by a previous store expression, it already has a
+    // value, and it's the same value as our current store. FIXME: Right now, we
+    // only do this for simple stores, we should expand to cover memcpys, etc.
     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) &&
         CC->RepStoredValue == lookupOperandLeader(SI->getValueOperand(), SI, B))
       return createStoreExpression(SI, StoreRHS, B);
+    // Also check if our value operand is defined by a load of the same memory
+    // location, and the memory state is the same as it was then
+    // (otherwise, it could have been overwritten later. See test32 in
+    // transforms/DeadStoreElimination/simple.ll)
+    if (LoadInst *LI = dyn_cast<LoadInst>(SI->getValueOperand())) {
+      if ((lookupOperandLeader(LI->getPointerOperand(), LI, LI->getParent()) ==
+           lookupOperandLeader(SI->getPointerOperand(), SI, B)) &&
+          (lookupMemoryAccessEquiv(
+               MSSA->getMemoryAccess(LI)->getDefiningAccess()) == StoreRHS))
+        return createVariableExpression(LI);
+    }
   }
-
   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
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());
       } else {
         NewClass->RepLeader = I;
       }
       assert(!isa<VariableExpression>(E) &&
              "VariableExpression should have been handled already");
 
       EClass = NewClass;
       DEBUG(dbgs() << "Created new congruence class for " << *I
                    << " using expression " << *E << " at " << NewClass->ID
                    << " and leader " << *(NewClass->RepLeader));
       if (NewClass->RepStoredValue)
         DEBUG(dbgs() << " and stored value " << *(NewClass->RepStoredValue));
       DEBUG(dbgs() << "\n");
assert(ProcessedCount[V] < 100 &&
            "Seem to have processed the same Value a lot");
   }
 #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.
+  // Filter out unreachable blocks and self phis from our operands.
   auto Filtered = make_filter_range(MP->operands(), [&](const Use &U) {
-    return ReachableBlocks.count(MP->getIncomingBlock(U));
+    return lookupMemoryAccessEquiv(cast<MemoryAccess>(U)) != MP &&
+           ReachableBlocks.count(MP->getIncomingBlock(U));
   });
-
-  assert(Filtered.begin() != Filtered.end() &&
-         "We should not be processing a MemoryPhi in a completely "
-         "unreachable block");
+  // If all that is left is nothing, our memoryphi is undef.
+  // Note: The only case this should happen is if we have at least one
+  // self-argument.
+  if (Filtered.begin() == Filtered.end()) {
+    if (setMemoryAccessEquivTo(MP, MSSA->getLiveOnEntryDef()))
+      markMemoryUsersTouched(MP);
+    return;
+  }
 
   // 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);
bool operator<(const ValueDFS &Other) const {
     // You will always end up with the same IR, and this is guaranteed.
     return std::tie(DFSIn, DFSOut, LocalNum, Val, U) <
            std::tie(Other.DFSIn, Other.DFSOut, Other.LocalNum, Other.Val,
                     Other.U);
   }
 };
 
 void NewGVN::convertDenseToDFSOrdered(
-    CongruenceClass::MemberSet &Dense,
+    const CongruenceClass::MemberSet &Dense,
     SmallVectorImpl<ValueDFS> &DFSOrderedSet) {
   for (auto D : Dense) {
     // First add the value.
     BasicBlock *BB = getBlockForValue(D);
     // Constants are handled prior to ever calling this function, so
     // we should only be left with instructions as members.
     assert(BB && "Should have figured out a basic block for value");
     ValueDFS VD;
-
     DomTreeNode *DomNode = DT->getNode(BB);
     VD.DFSIn = DomNode->getDFSNumIn();
     VD.DFSOut = DomNode->getDFSNumOut();
     // If it's a store, use the leader of the value operand.
     if (auto *SI = dyn_cast<StoreInst>(D)) {
       auto Leader =
           lookupOperandLeader(SI->getValueOperand(), SI, SI->getParent());
       VD.Val = alwaysAvailable(Leader) ? Leader : SI->getValueOperand();
for (auto &U : D->uses()) {
         VD.DFSOut = DomNode->getDFSNumOut();
         VD.U = &U;
         DFSOrderedSet.emplace_back(VD);
       }
     }
   }
 }
 
+void NewGVN::convertDenseToLoadsAndStores(
+    const CongruenceClass::MemberSet &Dense,
+    SmallVectorImpl<ValueDFS> &LoadsAndStores) {
+  for (auto D : Dense) {
+    if (!isa<LoadInst>(D) && !isa<StoreInst>(D))
+      continue;
+
+    BasicBlock *BB = getBlockForValue(D);
+    ValueDFS VD;
+    DomTreeNode *DomNode = DT->getNode(BB);
+    VD.DFSIn = DomNode->getDFSNumIn();
+    VD.DFSOut = DomNode->getDFSNumOut();
+    VD.Val = D;
+
+    // If it's an instruction, use the real local dfs number.
+    if (auto *I = dyn_cast<Instruction>(D))
+      VD.LocalNum = InstrDFS.lookup(I);
+    else
+      llvm_unreachable("Should have been an instruction");
+
+    LoadsAndStores.emplace_back(VD);
+  }
+}
+
 static void patchReplacementInstruction(Instruction *I, Value *Repl) {
   // Patch the replacement so that it is not more restrictive than the value
   // being replaced.
   auto *Op = dyn_cast<BinaryOperator>(I);
   auto *ReplOp = dyn_cast<BinaryOperator>(Repl);
 
   if (Op && ReplOp)
     ReplOp->andIRFlags(Op);
if (!ReachableBlocks.count(&B)) {
           for (auto &Operand : Phi.incoming_values())
             if (Phi.getIncomingBlock(Operand) == &B)
               Operand.set(UndefValue::get(Phi.getType()));
         }
       }
     }
   }
 
-  for (CongruenceClass *CC : CongruenceClasses) {
+  for (auto *CC : CongruenceClasses) {
+    // Track the equivalent store info so we can decide whether to try
+    // dead store elimination.
+    SmallVector<ValueDFS, 8> PossibleDeadStores;
+
     // FIXME: We should eventually be able to replace everything still
     // in the initial class with undef, as they should be unreachable.
     // Right now, initial still contains some things we skip value
     // numbering of (UNREACHABLE's, for example).
     if (CC == InitialClass || CC->Dead)
       continue;
     assert(CC->RepLeader && "We should have had a leader");
 
     // If this is a leader that is always available, and it's a
     // constant or has no equivalences, just replace everything with
     // it. We then update the congruence class with whatever members
     // are left.
     Value *Leader = CC->RepStoredValue ? CC->RepStoredValue : CC->RepLeader;
     if (alwaysAvailable(Leader)) {
       SmallPtrSet<Value *, 4> MembersLeft;
       for (auto M : CC->Members) {
-
         Value *Member = M;
 
         // Void things have no uses we can replace.
         if (Member == CC->RepLeader || Member->getType()->isVoidTy()) {
           MembersLeft.insert(Member);
           continue;
         }
 
         DEBUG(dbgs() << "Found replacement " << *(Leader) << " for " << *Member
                      << "\n");
         // Due to equality propagation, these may not always be
         // instructions, they may be real values.  We don't really
         // care about trying to replace the non-instructions.
         if (auto *I = dyn_cast<Instruction>(Member)) {
           assert(Leader != I && "About to accidentally remove our leader");
           replaceInstruction(I, Leader);
           AnythingReplaced = true;
 
           continue;
         } else {
           MembersLeft.insert(I);
         }
       }
       CC->Members.swap(MembersLeft);
-
     } else {
       DEBUG(dbgs() << "Eliminating in congruence class " << CC->ID << "\n");
       // If this is a singleton, we can skip it.
       if (CC->Members.size() != 1) {
 
         // This is a stack because equality replacement/etc may place
         // constants in the middle of the member list, and we want to use
         // those constant values in preference to the current leader, over
         // the scope of those constants.
         ValueDFSStack EliminationStack;
 
         // Convert the members to DFS ordered sets and then merge them.
         SmallVector<ValueDFS, 8> DFSOrderedSet;
         convertDenseToDFSOrdered(CC->Members, DFSOrderedSet);
 
         // Sort the whole thing.
         std::sort(DFSOrderedSet.begin(), DFSOrderedSet.end());
-
         for (auto &VD : DFSOrderedSet) {
           int MemberDFSIn = VD.DFSIn;
           int MemberDFSOut = VD.DFSOut;
           Value *Member = VD.Val;
           Use *MemberUse = VD.U;
 
-          if (Member) {
-            // We ignore void things because we can't get a value from them.
-            // FIXME: We could actually use this to kill dead stores that are
-            // dominated by equivalent earlier stores.
-            if (Member->getType()->isVoidTy())
-              continue;
+          if (Member && Member->getType()->isVoidTy()) {
           }
 
           if (EliminationStack.empty()) {
             DEBUG(dbgs() << "Elimination Stack is empty\n");
           } else {
             DEBUG(dbgs() << "Elimination Stack Top DFS numbers are ("
                          << EliminationStack.dfs_back().first << ","
                          << EliminationStack.dfs_back().second << ")\n");
if (alwaysAvailable(Leader)) {
             }
           }
 
           // If we get to this point, and the stack is empty we must have a use
           // with nothing we can use to eliminate it, just skip it.
           if (EliminationStack.empty())
             continue;
 
+          // Push any loads onto the dead store stack, so we can possibly
+          // eliminate them later.
+          if (Member && isa<LoadInst>(Member))
+            PossibleDeadStores.push_back(VD);
+
           // Skip the Value's, we only want to eliminate on their uses.
           if (Member)
             continue;
           Value *Result = EliminationStack.back();
 
           // Don't replace our existing users with ourselves.
           if (MemberUse->get() == Result)
             continue;
for (Value *Member : CC->Members) {
           // TODO: Don't mark loads of undefs.
           markInstructionForDeletion(MemberInst);
           continue;
         }
       }
       MembersLeft.insert(Member);
     }
     CC->Members.swap(MembersLeft);
+
+    // If we have possible dead stores to look at, try to eliminate them.
+    if (CC->StoreCount > 0) {
+      convertDenseToLoadsAndStores(CC->Members, PossibleDeadStores);
+      std::sort(PossibleDeadStores.begin(), PossibleDeadStores.end());
+      ValueDFSStack EliminationStack;
+      for (auto &VD : PossibleDeadStores) {
+        int MemberDFSIn = VD.DFSIn;
+        int MemberDFSOut = VD.DFSOut;
+        Instruction *Member = cast<Instruction>(VD.Val);
+        if (EliminationStack.empty() ||
+            !EliminationStack.isInScope(MemberDFSIn, MemberDFSOut)) {
+          // Sync to our current scope.
+          EliminationStack.popUntilDFSScope(MemberDFSIn, MemberDFSOut);
+          if (EliminationStack.empty()) {
+            EliminationStack.push_back(Member, MemberDFSIn, MemberDFSOut);
+            continue;
+          }
+        }
+        // We already did load elimination, so nothing to do here.
+        if (isa<LoadInst>(Member))
+          continue;
+        assert(!EliminationStack.empty());
+        Instruction *Leader = cast<Instruction>(EliminationStack.back());
+        assert(DT->dominates(Leader->getParent(), Member->getParent()));
+        // Member is dominater by Leader, and thus dead
+        DEBUG(dbgs() << "Marking dead store " << *Member
+                     << " that is dominated by " << *Leader << "\n");
+        markInstructionForDeletion(Member);
+        CC->Members.erase(Member);
+        ++NumGVNDeadStores;
+      }
+    }
   }
 
   return AnythingReplaced;
 }

test/Transforms/NewGVN/deadstore.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -basicaa -newgvn -S | FileCheck %s
+
+;; Most of these are borrowed from transforms/DSE/simple.ll
+;; NewGVN should be able to eliminate any stores of the same value that are actually redundnat.
+
+;; tmp5 is store of the same value to the same location as the load.
+define void @test12({ i32, i32 }* %x) nounwind  {
+; CHECK-LABEL: @test12(
+; CHECK-NEXT:    [[TMP4:%.*]] = getelementptr { i32, i32 }, { i32, i32 }* [[X:%.*]], i32 0, i32 0
+; CHECK-NEXT:    [[TMP5:%.*]] = load i32, i32* [[TMP4]], align 4
+; CHECK-NEXT:    [[TMP7:%.*]] = getelementptr { i32, i32 }, { i32, i32 }* [[X]], i32 0, i32 1
+; CHECK-NEXT:    [[TMP8:%.*]] = load i32, i32* [[TMP7]], align 4
+; CHECK-NEXT:    [[TMP17:%.*]] = sub i32 0, [[TMP8]]
+; CHECK-NEXT:    store i32 [[TMP17]], i32* [[TMP7]], align 4
+; CHECK-NEXT:    ret void
+;
+  %tmp4 = getelementptr { i32, i32 }, { i32, i32 }* %x, i32 0, i32 0
+  %tmp5 = load i32, i32* %tmp4, align 4
+  %tmp7 = getelementptr { i32, i32 }, { i32, i32 }* %x, i32 0, i32 1
+  %tmp8 = load i32, i32* %tmp7, align 4
+  %tmp17 = sub i32 0, %tmp8
+  store i32 %tmp5, i32* %tmp4, align 4
+  store i32 %tmp17, i32* %tmp7, align 4
+  ret void
+}
+; Remove redundant store if loaded value is in another block.
+define i32 @test26(i1 %c, i32* %p) {
+; CHECK-LABEL: @test26(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    br i1 [[C:%.*]], label [[BB1:%.*]], label [[BB2:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB3:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br label [[BB3]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  %v = load i32, i32* %p, align 4
+  br i1 %c, label %bb1, label %bb2
+bb1:
+  br label %bb3
+bb2:
+  store i32 %v, i32* %p, align 4
+  br label %bb3
+bb3:
+  ret i32 0
+}
+
+declare void @unknown_func()
+; Remove redundant store, which is in the same loop as the load.
+define i32 @test33(i1 %c, i32* %p, i32 %i) {
+; CHECK-LABEL: @test33(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[V:%.*]] = load i32, i32* [[P:%.*]], align 4
+; CHECK-NEXT:    br label [[BB2:%.*]]
+; CHECK:       bb2:
+; CHECK-NEXT:    call void @unknown_func()
+; CHECK-NEXT:    br i1 undef, label [[BB1]], label [[BB3:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret i32 0
+;
+entry:
+  br label %bb1
+bb1:
+  %v = load i32, i32* %p, align 4
+  br label %bb2
+bb2:
+  store i32 %v, i32* %p, align 4
+  ; Might read and overwrite value at %p, but doesn't matter.
+  call void @unknown_func()
+  br i1 undef, label %bb1, label %bb3
+bb3:
+  ret i32 0
+}