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 ↗

(On Diff #85808)

I'll remove the {'s.

2273 ↗

(On Diff #85808)

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 ↗

(On Diff #85808)

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

351–352 ↗

(On Diff #85808)

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

1496–1503 ↗

(On Diff #85808)

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

1972–1979 ↗

(On Diff #85808)

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

1986 ↗

(On Diff #85808)

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

2126 ↗

(On Diff #85808)

Spurious newline? Here and the next two)

2154–2156 ↗

(On Diff #85808)

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 ↗

(On Diff #85808)

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 ↗

(On Diff #85808)

fixed

351–352 ↗

(On Diff #85808)

yes

1496–1503 ↗

(On Diff #85808)

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 ↗

(On Diff #85808)

Done

2126 ↗

(On Diff #85808)

Killed

2154–2156 ↗

(On Diff #85808)

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

779 ↗

(On Diff #85950)

This #if 1 can go away, I think.

1272–1276 ↗

(On Diff #85950)

This can go away, no?

2388 ↗

(On Diff #85950)

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)

llvm/trunk/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 redundant/dead stores eliminated");
 
 //===----------------------------------------------------------------------===//
 //                                GVN Pass
 //===----------------------------------------------------------------------===//
 
 // Anchor methods.
 namespace llvm {
 namespace GVNExpression {
private:
   // 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;
+  bool isMemoryAccessTop(const MemoryAccess *) const;
 
   // Reachability handling.
   void updateReachableEdge(BasicBlock *, BasicBlock *);
   void processOutgoingEdges(TerminatorInst *, BasicBlock *);
   bool isOnlyReachableViaThisEdge(const BasicBlockEdge &) const;
   Value *findConditionEquivalence(Value *, BasicBlock *) 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 *){};
MemoryAccess *NewGVN::lookupMemoryAccessEquiv(MemoryAccess *MA) const {
   // 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;
 }
 
+// Return true if the MemoryAccess is really equivalent to everything. This is
+// equivalent to the lattice value "TOP" in most lattices.  This is the initial
+// state of all memory accesses.
+bool NewGVN::isMemoryAccessTop(const MemoryAccess *MA) const {
+  return MemoryAccessToClass.lookup(MA) == InitialClass;
+}
+
 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);
 
   // Give store and loads same opcode so they value number together.

 }
 
 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->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
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 &&
+           !isMemoryAccessTop(cast<MemoryAccess>(U)) &&
+           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. We keep it as
+  // InitialClass.  Note: The only case this should happen is if we have at
+  // least one self-argument.
+  if (Filtered.begin() == Filtered.end()) {
+    if (setMemoryAccessEquivTo(MP, InitialClass))
+      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 {
     // It does not matter what order we replace these operands in.
     // 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);
   }
 };
 
+// This function converts the set of members for a congruence class from values,
+// to sets of defs and uses with associated DFS info.
 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();
     } else {
       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");
 
     DFSOrderedSet.emplace_back(VD);
 
     // Now add the uses.
for (auto &U : D->uses()) {
         VD.DFSOut = DomNode->getDFSNumOut();
         VD.U = &U;
         DFSOrderedSet.emplace_back(VD);
       }
     }
   }
 }
 
+// This function converts the set of members for a congruence class from values,
+// to the set of defs for loads and stores, with associated DFS info.
+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)) {
             if (Phi.getIncomingBlock(Operand) == &B)
               Operand.set(UndefValue::get(Phi.getType()));
         }
       }
     }
   }
 
   for (CongruenceClass *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");
           }
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;
 }

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

 ; CHECK-NEXT:    br i1 [[TMP5]], label [[BB6:%.*]], label [[BB23:%.*]]
 ; CHECK:       bb6:
 ; CHECK-NEXT:    [[TMP7:%.*]] = getelementptr inbounds i32, i32* [[DATA]], i64 2
 ; CHECK-NEXT:    [[TMP9:%.*]] = getelementptr inbounds i32, i32* [[DATA]], i64 5
 ; CHECK-NEXT:    store i32 0, i32* [[TMP9]], align 4
 ; CHECK-NEXT:    [[TMP10:%.*]] = icmp slt i32 [[I_0]], 30
 ; CHECK-NEXT:    br i1 [[TMP10]], label [[BB11:%.*]], label [[BB14:%.*]]
 ; CHECK:       bb11:
-; CHECK-NEXT:    store i32 0, i32* [[TMP9]], align 4
 ; CHECK-NEXT:    br label [[BB14]]
 ; CHECK:       bb14:
 ; CHECK-NEXT:    [[TMP17:%.*]] = getelementptr inbounds i32, i32* [[DATA]], i64 1
 ; CHECK-NEXT:    [[TMP18:%.*]] = load i32, i32* [[TMP17]], align 4
 ; CHECK-NEXT:    [[TMP19]] = add nsw i32 [[N_0]], [[TMP18]]
 ; CHECK-NEXT:    br label [[BB21]]
 ; CHECK:       bb21:
 ; CHECK-NEXT:    [[TMP22]] = add nsw i32 [[I_0]], 1

 bb21:                                             ; preds = %bb14
   %tmp22 = add nsw i32 %i.0, 1
   br label %bb4
 
 bb23:                                             ; preds = %bb4
   ret i32 %p.0
 }
 
+;; This is an irreducible test case that will cause a memoryphi node loop
+;; in the two block.
+;; it's equivalent to something like
+;; *a = 0
+;; if (<....>) goto loopmiddle
+;; loopstart:
+;; loopmiddle:
+;; load *a
+;; *a = 0
+;; if (<....>) goto loopstart otherwise goto loopend
+;; loopend:
+;; load *a
+;; add the results of the loads
+;; return them
+;;
+;; Both loads should equal 0, but it requires being
+;; completely optimistic about MemoryPhis, otherwise
+;; we will not be able to see through the cycle.
+define i8 @quux(i8* noalias %arg, i8* noalias %arg2) {
+; CHECK-LABEL: @quux(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    store i8 0, i8* [[ARG:%.*]]
+; CHECK-NEXT:    br i1 undef, label [[BB2:%.*]], label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB2]]
+; CHECK:       bb2:
+; CHECK-NEXT:    br i1 undef, label [[BB1]], label [[BB3:%.*]]
+; CHECK:       bb3:
+; CHECK-NEXT:    ret i8 0
+;
+bb:
+  store i8 0, i8 *%arg
+  br i1 undef, label %bb2, label %bb1
+
+bb1:                                              ; preds = %bb2, %bb
+  br label %bb2
+
+bb2:                                              ; preds = %bb1, %bb
+  %tmp2 = load i8, i8* %arg
+  store i8 0, i8 *%arg
+  br i1 undef, label %bb1, label %bb3
+
+bb3:                                              ; preds = %bb2
+  %tmp = load i8, i8* %arg
+  %tmp3 = add i8 %tmp, %tmp2
+  ret i8 %tmp3
+}
 attributes #0 = { nounwind ssp uwtable "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-nans-fp-math"="false" "stack-protector-buffer-size"="8" "unsafe-fp-math"="false" "use-soft-float"="false" }
 
 !llvm.ident = !{!0, !0, !0}
 
 !0 = !{!"Apple LLVM version 6.0 (clang-600.0.56) (based on LLVM 3.5svn)"}

llvm/trunk/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
+}