Index: lib/Transforms/Scalar/NewGVN.cpp =================================================================== --- lib/Transforms/Scalar/NewGVN.cpp +++ lib/Transforms/Scalar/NewGVN.cpp @@ -87,6 +87,7 @@ "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 @@ -134,6 +135,8 @@ Value *RepLeader = nullptr; // If this is represented by a store, the value. Value *RepStoredValue = nullptr; + // If this class contains MemoryDefs, what is the represented memory state. + MemoryAccess *RepMemoryAccess = nullptr; // Defining Expression. const Expression *DefiningExpr = nullptr; // Actual members of this class. @@ -207,7 +210,7 @@ // 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 MemoryAccessEquiv; + DenseMap MemoryAccessToClass; // Expression to class mapping. using ExpressionClassMap = DenseMap; @@ -327,7 +330,6 @@ const BasicBlock *); const Expression *performSymbolicPHIEvaluation(Instruction *, const BasicBlock *); - bool setMemoryAccessEquivTo(MemoryAccess *From, MemoryAccess *To); const Expression *performSymbolicAggrValueEvaluation(Instruction *, const BasicBlock *); @@ -338,17 +340,22 @@ 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; - MemoryAccess *lookupMemoryAccessEquiv(MemoryAccess *) const; // Elimination. struct ValueDFS; - void convertDenseToDFSOrdered(CongruenceClass::MemberSet &, + void convertDenseToDFSOrdered(const CongruenceClass::MemberSet &, SmallVectorImpl &); + void convertDenseToLoadsAndStores(const CongruenceClass::MemberSet &, + SmallVectorImpl &); bool eliminateInstructions(Function &); void replaceInstruction(Instruction *, Value *); @@ -698,8 +705,22 @@ } MemoryAccess *NewGVN::lookupMemoryAccessEquiv(MemoryAccess *MA) const { - MemoryAccess *Result = MemoryAccessEquiv.lookup(MA); - return Result ? Result : MA; + auto *CC = MemoryAccessToClass.lookup(MA); + if (CC && CC->RepMemoryAccess) + return CC->RepMemoryAccess; + // 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, @@ -755,13 +776,18 @@ // are simple and avoid value numbering them. auto *SI = cast(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 1 + // Get the expression, if any, for the RHS of the MemoryDef. + MemoryAccess *StoreRHS = lookupMemoryAccessEquiv( + cast(StoreAccess)->getDefiningAccess()); + // If we are defined by ourselves, use the live on entry def. + if (StoreRHS == StoreAccess) + StoreRHS = MSSA->getLiveOnEntryDef(); + if (SI->isSimple()) { - // Get the expression, if any, for the RHS of the MemoryDef. - MemoryAccess *StoreRHS = lookupMemoryAccessEquiv( - cast(StoreAccess)->getDefiningAccess()); + // 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 @@ -769,11 +795,22 @@ // 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(CC->DefiningExpr) && + 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(SI->getValueOperand())) { + if ((lookupOperandLeader(LI->getPointerOperand(), LI, LI->getParent()) == + lookupOperandLeader(SI->getPointerOperand(), SI, B)) && + (lookupMemoryAccessEquiv( + MSSA->getMemoryAccess(LI)->getDefiningAccess()) == StoreRHS)) + return createVariableExpression(LI); + } +#endif } - return createStoreExpression(SI, StoreAccess, B); } @@ -823,24 +860,30 @@ // 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) { - DEBUG(dbgs() << "Setting " << *From << " equivalent to "); - if (!To) - DEBUG(dbgs() << "itself"); - else - DEBUG(dbgs() << *To); - DEBUG(dbgs() << "\n"); - auto LookupResult = MemoryAccessEquiv.find(From); +// 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. +bool NewGVN::setMemoryAccessEquivTo(MemoryAccess *From, CongruenceClass *To) { + DEBUG(dbgs() << "Setting " << *From); + if (To) { + DEBUG(dbgs() << " equivalent to congruence class "); + DEBUG(dbgs() << To->ID << " with current memory access leader "); + DEBUG(dbgs() << *To->RepMemoryAccess); + } else { + DEBUG(dbgs() << " equivalent to itself"); + DEBUG(dbgs() << "\n"); + } + + auto LookupResult = MemoryAccessToClass.find(From); bool Changed = false; // If it's already in the table, see if the value changed. - if (LookupResult != MemoryAccessEquiv.end()) { + if (LookupResult != MemoryAccessToClass.end()) { if (To && LookupResult->second != To) { // It wasn't equivalent before, and now it is. LookupResult->second = To; Changed = true; } else if (!To) { // It used to be equivalent to something, and now it's not. - MemoryAccessEquiv.erase(LookupResult); + MemoryAccessToClass.erase(LookupResult); Changed = true; } } else { @@ -1109,11 +1152,20 @@ OldClass->Members.erase(I); NewClass->Members.insert(I); - if (isa(I)) { + MemoryAccess *StoreAccess = nullptr; + if (auto *SI = dyn_cast(I)) { + StoreAccess = MSSA->getMemoryAccess(SI); --OldClass->StoreCount; assert(OldClass->StoreCount >= 0); ++NewClass->StoreCount; assert(NewClass->StoreCount > 0); + if (!NewClass->RepMemoryAccess) { + // If we don't have a representative memory access, it better be the only + // store in there. + assert(NewClass->StoreCount == 1); + NewClass->RepMemoryAccess = StoreAccess; + } + setMemoryAccessEquivTo(StoreAccess, NewClass); } ValueToClass[I] = NewClass; @@ -1132,8 +1184,33 @@ DEBUG(dbgs() << "Leader change!\n"); ++NumGVNLeaderChanges; // Destroy the stored value if there are no more stores to represent it. - if (OldClass->RepStoredValue != nullptr && OldClass->StoreCount == 0) - OldClass->RepStoredValue = nullptr; + if (OldClass->StoreCount == 0) { + if (OldClass->RepStoredValue != nullptr) + OldClass->RepStoredValue = nullptr; + if (OldClass->RepMemoryAccess != nullptr) + OldClass->RepMemoryAccess = nullptr; + } + + // If we destroy the old access leader, we have to effectively destroy the + // congruence class. When it comes to scalars, anything with the same value + // is as good as any other. That means that one leader is as good as + // another, and as long as you have some leader for the value, you are + // good.. When it comes to *memory states*, only one particular thing really + // represents the definition of a given memory state. Once it goes away, we + // need to re-evaluate which pieces of memory are really still + // equivalent. The best way to do this is to re-value number things. The + // only way to really make that happen is to destroy the rest of the class. + // In order to effectively destroy the class, we reset ExpressionToClass for + // each by using the ValueToExpression mapping. The members later get + // marked as touched due to the leader change. We will create new + // congruence classes, and the pieces that are still equivalent will end + // back together in a new class + if (OldClass->StoreCount > 0 && OldClass->RepMemoryAccess == StoreAccess) { + DEBUG(dbgs() << "Kicking everything out of class " << OldClass->ID + << " because memory access leader changed"); + for (auto Member : OldClass->Members) + ExpressionToClass.erase(ValueToExpression.lookup(Member)); + } // We don't need to sort members if there is only 1, and we don't care about // sorting the initial class because everything either gets out of it or is @@ -1192,6 +1269,11 @@ NewClass->RepLeader = SI; NewClass->RepStoredValue = lookupOperandLeader(SI->getValueOperand(), SI, SI->getParent()); +// This gets filled in by the moveValue +#if 0 + // First store is the leading memory access + NewClass->RepMemoryAccess = MSSA->getMemoryAccess(SI); +#endif } else { NewClass->RepLeader = I; } @@ -1227,21 +1309,8 @@ if (ClassChanged) moveValueToNewCongruenceClass(I, IClass, EClass); markUsersTouched(I); - 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. Right now, we only support store - // expressions. - if (!isa(MA) && isa(E) && - EClass->Members.size() != 1) { - auto *DefAccess = cast(E)->getDefiningAccess(); - setMemoryAccessEquivTo(MA, DefAccess != MA ? DefAccess : nullptr); - } else { - setMemoryAccessEquivTo(MA, nullptr); - } + if (MemoryAccess *MA = MSSA->getMemoryAccess(I)) markMemoryUsersTouched(MA); - } } } @@ -1375,9 +1444,10 @@ // Initialize all other instructions to be in INITIAL class. CongruenceClass::MemberSet InitialValues; InitialClass = createCongruenceClass(nullptr, nullptr); + InitialClass->RepMemoryAccess = MSSA->getLiveOnEntryDef(); for (auto &B : F) { if (auto *MP = MSSA->getMemoryAccess(&B)) - MemoryAccessEquiv.insert({MP, MSSA->getLiveOnEntryDef()}); + MemoryAccessToClass[MP] = InitialClass; for (auto &I : B) { InitialValues.insert(&I); @@ -1390,8 +1460,7 @@ // other expression can generate a memory equivalence. If we start // handling memcpy/etc, we can expand this. if (isa(&I)) { - MemoryAccessEquiv.insert( - {MSSA->getMemoryAccess(&I), MSSA->getLiveOnEntryDef()}); + MemoryAccessToClass[MSSA->getMemoryAccess(&I)] = InitialClass; ++InitialClass->StoreCount; assert(InitialClass->StoreCount > 0); } @@ -1432,7 +1501,7 @@ BlockInstRange.clear(); TouchedInstructions.clear(); DominatedInstRange.clear(); - MemoryAccessEquiv.clear(); + MemoryAccessToClass.clear(); } std::pair NewGVN::assignDFSNumbers(BasicBlock *B, @@ -1469,14 +1538,20 @@ 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(U)) != MP && + !isMemoryAccessTop(cast(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. @@ -1499,7 +1574,8 @@ else DEBUG(dbgs() << "Memory Phi value numbered to itself\n"); - if (setMemoryAccessEquivTo(MP, AllEqual ? AllSameValue : nullptr)) + if (setMemoryAccessEquivTo( + MP, AllEqual ? MemoryAccessToClass.lookup(AllSameValue) : nullptr)) markMemoryUsersTouched(MP); } @@ -1576,7 +1652,7 @@ // 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 Pair) { + [&](const std::pair Pair) { bool Result = ReachableBlocks.count(Pair.first->getBlock()); if (!Result) return false; @@ -1585,16 +1661,14 @@ return true; }; - auto Filtered = make_filter_range(MemoryAccessEquiv, ReachableAccessPred); + auto Filtered = make_filter_range(MemoryAccessToClass, 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(KV.first)) { - auto *SecondMUD = dyn_cast(KV.second); + auto *SecondMUD = dyn_cast(KV.second->RepMemoryAccess); if (FirstMUD && SecondMUD) assert((singleReachablePHIPath(FirstMUD, SecondMUD) || ValueToClass.lookup(FirstMUD->getMemoryInst()) == @@ -1890,8 +1964,10 @@ } }; +// 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 &DFSOrderedSet) { for (auto D : Dense) { // First add the value. @@ -1900,7 +1976,6 @@ // 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(); @@ -1913,7 +1988,6 @@ VD.Val = D; } - // If it's an instruction, use the real local dfs number. if (auto *I = dyn_cast(D)) VD.LocalNum = InstrDFS.lookup(I); else @@ -1952,6 +2026,32 @@ } } +// 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 &LoadsAndStores) { + for (auto D : Dense) { + if (!isa(D) && !isa(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(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. @@ -2106,6 +2206,10 @@ } for (CongruenceClass *CC : CongruenceClasses) { + // Track the equivalent store info so we can decide whether to try + // dead store elimination. + SmallVector 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 @@ -2122,15 +2226,12 @@ if (alwaysAvailable(Leader)) { SmallPtrSet 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 @@ -2147,7 +2248,6 @@ } } CC->Members.swap(MembersLeft); - } else { DEBUG(dbgs() << "Eliminating in congruence class " << CC->ID << "\n"); // If this is a singleton, we can skip it. @@ -2165,20 +2265,15 @@ // 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; - } + // We ignore void things because we can't get a value from them. + if (Member && Member->getType()->isVoidTy()) + continue; if (EliminationStack.empty()) { DEBUG(dbgs() << "Elimination Stack is empty\n"); @@ -2265,6 +2360,39 @@ 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(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(Member)) + continue; + assert(!EliminationStack.empty()); + Instruction *Leader = cast(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; Index: test/Transforms/NewGVN/basic-cyclic-opt.ll =================================================================== --- test/Transforms/NewGVN/basic-cyclic-opt.ll +++ test/Transforms/NewGVN/basic-cyclic-opt.ll @@ -169,7 +169,6 @@ ; 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 @@ -228,6 +227,53 @@ 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} Index: test/Transforms/NewGVN/deadstore.ll =================================================================== --- /dev/null +++ test/Transforms/NewGVN/deadstore.ll @@ -0,0 +1,79 @@ +; 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 +} Index: test/Transforms/NewGVN/pr31594.ll =================================================================== --- test/Transforms/NewGVN/pr31594.ll +++ test/Transforms/NewGVN/pr31594.ll @@ -3,7 +3,7 @@ target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128" -define void @patatino(i8* %blah, i32 %choice) { +define i1 @patatino(i8* %blah, i32 %choice) { ; CHECK-LABEL: @patatino( ; CHECK-NEXT: entry: ; CHECK-NEXT: br label [[WHILE_COND:%.*]] @@ -20,8 +20,9 @@ ; CHECK: while.end: ; CHECK-NEXT: store i8 0, i8* [[FOO]], align 1 ; CHECK-NEXT: [[TMP0:%.*]] = load i8, i8* [[BLAH]], align 1 +; CHECK-NEXT: [[LOADED:%.*]] = icmp eq i8 [[TMP0]], 0 ; CHECK-NEXT: store i8 0, i8* [[BLAH]], align 1 -; CHECK-NEXT: ret void +; CHECK-NEXT: ret i1 [[LOADED]] ; entry: br label %while.cond @@ -49,7 +50,7 @@ %0 = load i8, i8* %blah, align 1 %loaded = icmp eq i8 %0, 0 store i8 0, i8* %blah, align 1 - ret void + ret i1 %loaded } Index: test/Transforms/NewGVN/pr31758.ll =================================================================== --- test/Transforms/NewGVN/pr31758.ll +++ test/Transforms/NewGVN/pr31758.ll @@ -1,3 +1,4 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt -newgvn %s -S -o - | FileCheck %s %struct.dipsy = type {} @@ -5,6 +6,17 @@ %struct.patatino = type {} define void @tinkywinky() { +; CHECK-LABEL: @tinkywinky( +; CHECK-NEXT: bb: +; CHECK-NEXT: br label [[BB90:%.*]] +; CHECK: bb90: +; CHECK-NEXT: [[TMP91:%.*]] = bitcast %struct.dipsy** undef to %struct.patatino** +; CHECK-NEXT: [[TMP92:%.*]] = load %struct.patatino*, %struct.patatino** [[TMP91]], align 8 +; CHECK-NEXT: [[TMP136:%.*]] = load %struct.patatino*, %struct.patatino** [[TMP91]], align 8 +; CHECK-NEXT: br label [[BB90]] +; CHECK: bb138: +; CHECK-NEXT: unreachable +; bb: br label %bb90 @@ -22,16 +34,3 @@ %tmp139 = getelementptr inbounds %struct.patatino, %struct.patatino* %tmp136 br label %bb138 } - -; CHECK-LABEL: tinkywinky -; CHECK-NEXT: bb: -; CHECK-NEXT: br label %bb90 -; CHECK-NEXT -; CHECK: bb90: -; CHECK: %tmp91 = bitcast %struct.dipsy** undef to %struct.patatino** -; CHECK-NEXT: %tmp92 = load %struct.patatino*, %struct.patatino** %tmp91, align 8 -; CHECK-NEXT: %tmp136 = load %struct.patatino*, %struct.patatino** %tmp91, align 8 -; CHECK-NEXT: br label %bb90 -; CHECK: bb138: -; CHECK-NEXT: br label %bb138 -; CHECK-NEXT: }