diff --git a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp --- a/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp +++ b/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -46,7 +46,6 @@ #include "llvm/Analysis/MemorySSA.h" #include "llvm/Analysis/MemorySSAUpdater.h" #include "llvm/Analysis/MustExecute.h" -#include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/Argument.h" @@ -100,9 +99,6 @@ STATISTIC(NumFastOther, "Number of other instrs removed"); STATISTIC(NumCompletePartials, "Number of stores dead by later partials"); STATISTIC(NumModifiedStores, "Number of stores modified"); -STATISTIC(NumCFGChecks, "Number of stores modified"); -STATISTIC(NumCFGTries, "Number of stores modified"); -STATISTIC(NumCFGSuccess, "Number of stores modified"); STATISTIC(NumGetDomMemoryDefPassed, "Number of times a valid candidate is returned from getDomMemoryDef"); STATISTIC(NumDomMemDefChecks, @@ -743,7 +739,6 @@ MemorySSA &MSSA; DominatorTree &DT; - PostDominatorTree &PDT; const TargetLibraryInfo &TLI; const DataLayout &DL; const LoopInfo &LI; @@ -763,6 +758,10 @@ DenseMap InvisibleToCallerAfterRet; // Keep track of blocks with throwing instructions not modeled in MemorySSA. SmallPtrSet ThrowingBlocks; + + SmallPtrSet ExitReads; + SmallVector ExitingTerminators; + // Post-order numbers for each basic block. Used to figure out if memory // accesses are executed before another access. DenseMap PostOrderNumbers; @@ -771,15 +770,16 @@ /// basic block. MapVector IOLs; + MemorySSAUpdater Updater; + // Class contains self-reference, make sure it's not copied/moved. DSEState(const DSEState &) = delete; DSEState &operator=(const DSEState &) = delete; DSEState(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, DominatorTree &DT, - PostDominatorTree &PDT, const TargetLibraryInfo &TLI, - const LoopInfo &LI) + const TargetLibraryInfo &TLI, const LoopInfo &LI) : F(F), AA(AA), EI(DT, LI), BatchAA(AA, &EI), MSSA(MSSA), DT(DT), - PDT(PDT), TLI(TLI), DL(F.getParent()->getDataLayout()), LI(LI) { + TLI(TLI), DL(F.getParent()->getDataLayout()), LI(LI), Updater(&MSSA) { // Collect blocks with throwing instructions not modeled in MemorySSA and // alloc-like objects. unsigned PO = 0; @@ -795,6 +795,8 @@ (getLocForWrite(&I) || isMemTerminatorInst(&I))) MemDefs.push_back(MD); } + if (succ_empty(BB)) + ExitingTerminators.push_back(BB->getTerminator()); } // Treat byval or inalloca arguments the same as Allocas, stores to them are @@ -805,6 +807,22 @@ // Collect whether there is any irreducible control flow in the function. ContainsIrreducibleLoops = mayContainIrreducibleControl(F, &LI); + + LLVMContext &Ctx = F.getContext(); + Type *I8Ty = IntegerType::get(Ctx, 8); + + GlobalVariable *Ext = nullptr; + for (Instruction *Term : ExitingTerminators) { + if (!Ext) + Ext = new GlobalVariable( + *F.getParent(), I8Ty, false, GlobalValue::ExternalLinkage, nullptr, + "", nullptr, GlobalValue::NotThreadLocal, None, true); + auto *LI = new LoadInst(I8Ty, Ext, "", Term); + auto *MemUse = cast(Updater.createMemoryAccessInBB( + LI, nullptr, Term->getParent(), MemorySSA::End)); + Updater.insertUse(MemUse); + ExitReads.insert(LI); + } } /// Return 'OW_Complete' if a store to the 'KillingLoc' location (by \p @@ -1150,7 +1168,10 @@ if (auto *CB = dyn_cast(UseInst)) if (CB->onlyAccessesInaccessibleMemory()) return false; - + auto *LI = dyn_cast(UseInst); + if (LI && ExitReads.count(LI)) { + return !isInvisibleToCallerAfterRet(getUnderlyingObject(DefLoc.Ptr)); + } return isRefSet(BatchAA.getModRefInfo(UseInst, DefLoc)); } @@ -1289,6 +1310,7 @@ if (any_of(Current->uses(), [this, &KillingLoc, StartAccess](Use &U) { if (auto *UseOrDef = dyn_cast(U.getUser())) return !MSSA.dominates(StartAccess, UseOrDef) && + !ExitReads.count(UseOrDef->getMemoryInst()) && isReadClobber(KillingLoc, UseOrDef->getMemoryInst()); return false; })) { @@ -1490,69 +1512,6 @@ } } - // For accesses to locations visible after the function returns, make sure - // that the location is dead (=overwritten) along all paths from - // MaybeDeadAccess to the exit. - if (!isInvisibleToCallerAfterRet(KillingUndObj)) { - SmallPtrSet KillingBlocks; - for (Instruction *KD : KillingDefs) - KillingBlocks.insert(KD->getParent()); - assert(!KillingBlocks.empty() && - "Expected at least a single killing block"); - - // Find the common post-dominator of all killing blocks. - BasicBlock *CommonPred = *KillingBlocks.begin(); - for (BasicBlock *BB : llvm::drop_begin(KillingBlocks)) { - if (!CommonPred) - break; - CommonPred = PDT.findNearestCommonDominator(CommonPred, BB); - } - - // If the common post-dominator does not post-dominate MaybeDeadAccess, - // there is a path from MaybeDeadAccess to an exit not going through a - // killing block. - if (!PDT.dominates(CommonPred, MaybeDeadAccess->getBlock())) - return None; - - // If CommonPred itself is in the set of killing blocks, we're done. - if (KillingBlocks.count(CommonPred)) - return {MaybeDeadAccess}; - - SetVector WorkList; - - // If CommonPred is null, there are multiple exits from the function. - // They all have to be added to the worklist. - if (CommonPred) - WorkList.insert(CommonPred); - else - for (BasicBlock *R : PDT.roots()) - WorkList.insert(R); - - NumCFGTries++; - // Check if all paths starting from an exit node go through one of the - // killing blocks before reaching MaybeDeadAccess. - for (unsigned I = 0; I < WorkList.size(); I++) { - NumCFGChecks++; - BasicBlock *Current = WorkList[I]; - if (KillingBlocks.count(Current)) - continue; - if (Current == MaybeDeadAccess->getBlock()) - return None; - - // MaybeDeadAccess is reachable from the entry, so we don't have to - // explore unreachable blocks further. - if (!DT.isReachableFromEntry(Current)) - continue; - - for (BasicBlock *Pred : predecessors(Current)) - WorkList.insert(Pred); - - if (WorkList.size() >= MemorySSAPathCheckLimit) - return None; - } - NumCFGSuccess++; - } - // No aliasing MemoryUses of MaybeDeadAccess found, MaybeDeadAccess is // potentially dead. return {MaybeDeadAccess}; @@ -1560,7 +1519,6 @@ // Delete dead memory defs void deleteDeadInstruction(Instruction *SI) { - MemorySSAUpdater Updater(&MSSA); SmallVector NowDeadInsts; NowDeadInsts.push_back(SI); --NumFastOther; @@ -1744,7 +1702,6 @@ Malloc->getArgOperand(0), IRB, TLI); if (!Calloc) return false; - MemorySSAUpdater Updater(&MSSA); auto *LastDef = cast(Updater.getMemorySSA()->getMemoryAccess(Malloc)); auto *NewAccess = @@ -1915,12 +1872,11 @@ }; static bool eliminateDeadStores(Function &F, AliasAnalysis &AA, MemorySSA &MSSA, - DominatorTree &DT, PostDominatorTree &PDT, - const TargetLibraryInfo &TLI, + DominatorTree &DT, const TargetLibraryInfo &TLI, const LoopInfo &LI) { bool MadeChange = false; - DSEState State(F, AA, MSSA, DT, PDT, TLI, LI); + DSEState State(F, AA, MSSA, DT, TLI, LI); // For each store: for (unsigned I = 0; I < State.MemDefs.size(); I++) { MemoryDef *KillingDef = State.MemDefs[I]; @@ -2087,6 +2043,17 @@ MadeChange |= State.eliminateRedundantStoresOfExistingValues(); MadeChange |= State.eliminateDeadWritesAtEndOfFunction(); + + GlobalVariable *Ext = nullptr; + for (Instruction *Term : State.ExitingTerminators) { + auto *LI = cast(Term->getPrevNode()); + Ext = cast(LI->getPointerOperand()); + State.Updater.removeMemoryAccess(LI); + LI->eraseFromParent(); + } + if (Ext) + Ext->eraseFromParent(); + return MadeChange; } } // end anonymous namespace @@ -2099,10 +2066,9 @@ const TargetLibraryInfo &TLI = AM.getResult(F); DominatorTree &DT = AM.getResult(F); MemorySSA &MSSA = AM.getResult(F).getMSSA(); - PostDominatorTree &PDT = AM.getResult(F); LoopInfo &LI = AM.getResult(F); - bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, TLI, LI); + bool Changed = eliminateDeadStores(F, AA, MSSA, DT, TLI, LI); #ifdef LLVM_ENABLE_STATS if (AreStatisticsEnabled()) @@ -2140,11 +2106,9 @@ const TargetLibraryInfo &TLI = getAnalysis().getTLI(F); MemorySSA &MSSA = getAnalysis().getMSSA(); - PostDominatorTree &PDT = - getAnalysis().getPostDomTree(); LoopInfo &LI = getAnalysis().getLoopInfo(); - bool Changed = eliminateDeadStores(F, AA, MSSA, DT, PDT, TLI, LI); + bool Changed = eliminateDeadStores(F, AA, MSSA, DT, TLI, LI); #ifdef LLVM_ENABLE_STATS if (AreStatisticsEnabled()) @@ -2162,9 +2126,7 @@ AU.addPreserved(); AU.addRequired(); AU.addPreserved(); - AU.addRequired(); AU.addRequired(); - AU.addPreserved(); AU.addPreserved(); AU.addRequired(); AU.addPreserved(); @@ -2178,7 +2140,6 @@ INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false, false) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) -INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass) diff --git a/llvm/test/Other/new-pm-lto-defaults.ll b/llvm/test/Other/new-pm-lto-defaults.ll --- a/llvm/test/Other/new-pm-lto-defaults.ll +++ b/llvm/test/Other/new-pm-lto-defaults.ll @@ -102,7 +102,6 @@ ; CHECK-O23SZ-NEXT: Running analysis: PhiValuesAnalysis on foo ; CHECK-O23SZ-NEXT: Running pass: MemCpyOptPass on foo ; CHECK-O23SZ-NEXT: Running pass: DSEPass on foo -; CHECK-O23SZ-NEXT: Running analysis: PostDominatorTreeAnalysis on foo ; CHECK-O23SZ-NEXT: Running pass: MergedLoadStoreMotionPass on foo ; CHECK-O23SZ-NEXT: Running pass: LoopSimplifyPass on foo ; CHECK-O23SZ-NEXT: Running pass: LCSSAPass on foo @@ -113,6 +112,7 @@ ; CHECK-O23SZ-NEXT: Running pass: LoopVectorizePass on foo ; CHECK-O23SZ-NEXT: Running analysis: BlockFrequencyAnalysis on foo ; CHECK-O23SZ-NEXT: Running analysis: BranchProbabilityAnalysis on foo +; CHECK-O23SZ-NEXT: Running analysis: PostDominatorTreeAnalysis on foo ; CHECK-O23SZ-NEXT: Running analysis: DemandedBitsAnalysis on foo ; CHECK-O23SZ-NEXT: Running pass: LoopUnrollPass on foo ; CHECK-O23SZ-NEXT: WarnMissedTransformationsPass on foo