Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -105,7 +105,7 @@ void initializeDAEPass(PassRegistry&); void initializeDAHPass(PassRegistry&); void initializeDCELegacyPassPass(PassRegistry&); -void initializeDSEPass(PassRegistry&); +void initializeDSELegacyPassPass(PassRegistry&); void initializeDeadInstEliminationPass(PassRegistry&); void initializeDeadMachineInstructionElimPass(PassRegistry&); void initializeDelinearizationPass(PassRegistry &); Index: include/llvm/Transforms/Scalar/DeadStoreElimination.h =================================================================== --- /dev/null +++ include/llvm/Transforms/Scalar/DeadStoreElimination.h @@ -0,0 +1,71 @@ +//===- DeadStoreElimination.h - Fast Dead Store Elimination -------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements a trivial dead store elimination that only considers +// basic-block local redundant stores. +// +// FIXME: This should eventually be extended to be a post-dominator tree +// traversal. Doing so would be pretty trivial. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_DSE_H +#define LLVM_TRANSFORMS_SCALAR_DSE_H + +#include "llvm/ADT/SetVector.h" +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/MemoryDependenceAnalysis.h" +#include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { + +/// A private "module" namespace for types and utilities used by DSE. These +/// are implementation details and should not be used by clients. +namespace dse { +class DSELegacyPass; +} + +/// This class implements a trivial dead store elimination. We consider +/// only the redundant stores that are local to a single Basic Block. +class DSEPass : public PassInfoMixin { +public: + DSEPass() {} + + /// \brief Run the pass over the function. + PreservedAnalyses run(Function &F, AnalysisManager &FAM); + +private: + friend class dse::DSELegacyPass; + + /// Helper used by both the public run method and by the legacy pass. + PreservedAnalyses runImpl(Function &F, AliasAnalysis &RunAA, + MemoryDependenceResults &RunMemDep, + DominatorTree &RunDT, TargetLibraryInfo &RunTLI); + + bool runOnBasicBlock(BasicBlock &BB, AliasAnalysis *AA, + MemoryDependenceResults *MD, DominatorTree *DT, + const TargetLibraryInfo *TLI); + bool MemoryIsNotModifiedBetween(Instruction *FirstI, Instruction *SecondI, + AliasAnalysis *AA); + bool HandleFree(CallInst *F, AliasAnalysis *AA, MemoryDependenceResults *MD, + DominatorTree *DT, const TargetLibraryInfo *TLI); + bool handleEndBlock(BasicBlock &BB, AliasAnalysis *AA, + MemoryDependenceResults *MD, + const TargetLibraryInfo *TLI); + void RemoveAccessedObjects(const MemoryLocation &LoadedLoc, + SmallSetVector &DeadStackObjects, + const DataLayout &DL, AliasAnalysis *AA, + const TargetLibraryInfo *TLI); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_DSE_H Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -63,6 +63,7 @@ #include "llvm/Transforms/PGOInstrumentation.h" #include "llvm/Transforms/Scalar/ADCE.h" #include "llvm/Transforms/Scalar/DCE.h" +#include "llvm/Transforms/Scalar/DeadStoreElimination.h" #include "llvm/Transforms/Scalar/EarlyCSE.h" #include "llvm/Transforms/Scalar/GVN.h" #include "llvm/Transforms/Scalar/LoopRotation.h" Index: lib/Passes/PassRegistry.def =================================================================== --- lib/Passes/PassRegistry.def +++ lib/Passes/PassRegistry.def @@ -109,6 +109,7 @@ FUNCTION_PASS("aa-eval", AAEvaluator()) FUNCTION_PASS("adce", ADCEPass()) FUNCTION_PASS("dce", DCEPass()) +FUNCTION_PASS("dse", DSEPass()) FUNCTION_PASS("early-cse", EarlyCSEPass()) FUNCTION_PASS("instcombine", InstCombinePass()) FUNCTION_PASS("invalidate", InvalidateAllAnalysesPass()) Index: lib/Transforms/Scalar/DeadStoreElimination.cpp =================================================================== --- lib/Transforms/Scalar/DeadStoreElimination.cpp +++ lib/Transforms/Scalar/DeadStoreElimination.cpp @@ -15,7 +15,7 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Scalar/DeadStoreElimination.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/Statistic.h" @@ -36,8 +36,10 @@ #include "llvm/Pass.h" #include "llvm/Support/Debug.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Scalar.h" #include "llvm/Transforms/Utils/Local.h" using namespace llvm; +using namespace llvm::dse; #define DEBUG_TYPE "dse" @@ -45,69 +47,6 @@ STATISTIC(NumFastStores, "Number of stores deleted"); STATISTIC(NumFastOther , "Number of other instrs removed"); -namespace { - struct DSE : public FunctionPass { - AliasAnalysis *AA; - MemoryDependenceResults *MD; - DominatorTree *DT; - const TargetLibraryInfo *TLI; - - static char ID; // Pass identification, replacement for typeid - DSE() : FunctionPass(ID), AA(nullptr), MD(nullptr), DT(nullptr) { - initializeDSEPass(*PassRegistry::getPassRegistry()); - } - - bool runOnFunction(Function &F) override { - if (skipFunction(F)) - return false; - - AA = &getAnalysis().getAAResults(); - MD = &getAnalysis().getMemDep(); - DT = &getAnalysis().getDomTree(); - TLI = &getAnalysis().getTLI(); - - bool Changed = false; - for (BasicBlock &I : F) - // Only check non-dead blocks. Dead blocks may have strange pointer - // cycles that will confuse alias analysis. - if (DT->isReachableFromEntry(&I)) - Changed |= runOnBasicBlock(I); - - AA = nullptr; MD = nullptr; DT = nullptr; - return Changed; - } - - bool runOnBasicBlock(BasicBlock &BB); - bool MemoryIsNotModifiedBetween(Instruction *FirstI, Instruction *SecondI); - bool HandleFree(CallInst *F); - bool handleEndBlock(BasicBlock &BB); - void RemoveAccessedObjects(const MemoryLocation &LoadedLoc, - SmallSetVector &DeadStackObjects, - const DataLayout &DL); - - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.setPreservesCFG(); - AU.addRequired(); - AU.addRequired(); - AU.addRequired(); - AU.addRequired(); - AU.addPreserved(); - AU.addPreserved(); - AU.addPreserved(); - } - }; -} - -char DSE::ID = 0; -INITIALIZE_PASS_BEGIN(DSE, "dse", "Dead Store Elimination", false, false) -INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) -INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) -INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) -INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass) -INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) -INITIALIZE_PASS_END(DSE, "dse", "Dead Store Elimination", false, false) - -FunctionPass *llvm::createDeadStoreEliminationPass() { return new DSE(); } //===----------------------------------------------------------------------===// // Helper functions @@ -507,7 +446,9 @@ // DSE Pass //===----------------------------------------------------------------------===// -bool DSE::runOnBasicBlock(BasicBlock &BB) { +bool DSEPass::runOnBasicBlock(BasicBlock &BB, AliasAnalysis *AA, + MemoryDependenceResults *MD, DominatorTree *DT, + const TargetLibraryInfo *TLI) { const DataLayout &DL = BB.getModule()->getDataLayout(); bool MadeChange = false; @@ -517,7 +458,7 @@ // Handle 'free' calls specially. if (CallInst *F = isFreeCall(Inst, TLI)) { - MadeChange |= HandleFree(F); + MadeChange |= HandleFree(F, AA, MD, DT, TLI); continue; } @@ -547,7 +488,7 @@ if (LoadInst *DepLoad = dyn_cast(SI->getValueOperand())) { if (SI->getPointerOperand() == DepLoad->getPointerOperand() && isRemovable(SI) && - MemoryIsNotModifiedBetween(DepLoad, SI)) { + MemoryIsNotModifiedBetween(DepLoad, SI, AA)) { DEBUG(dbgs() << "DSE: Remove Store Of Load from same pointer:\n " << "LOAD: " << *DepLoad << "\n STORE: " << *SI << '\n'); @@ -566,7 +507,7 @@ GetUnderlyingObject(SI->getPointerOperand(), DL)); if (UnderlyingPointer && isCallocLikeFn(UnderlyingPointer, TLI) && - MemoryIsNotModifiedBetween(UnderlyingPointer, SI)) { + MemoryIsNotModifiedBetween(UnderlyingPointer, SI, AA)) { DEBUG(dbgs() << "DSE: Remove null store to the calloc'ed object:\n DEAD: " << *Inst << "\n OBJECT: " << *UnderlyingPointer << '\n'); @@ -698,7 +639,7 @@ // If this block ends in a return, unwind, or unreachable, all allocas are // dead at its end, which means stores to them are also dead. if (BB.getTerminator()->getNumSuccessors() == 0) - MadeChange |= handleEndBlock(BB); + MadeChange |= handleEndBlock(BB, AA, MD, TLI); return MadeChange; } @@ -707,8 +648,9 @@ /// modified between the first and the second instruction. /// Precondition: Second instruction must be dominated by the first /// instruction. -bool DSE::MemoryIsNotModifiedBetween(Instruction *FirstI, - Instruction *SecondI) { +bool DSEPass::MemoryIsNotModifiedBetween(Instruction *FirstI, + Instruction *SecondI, + AliasAnalysis *AA) { SmallVector WorkList; SmallPtrSet Visited; BasicBlock::iterator FirstBBI(FirstI); @@ -779,7 +721,9 @@ /// HandleFree - Handle frees of entire structures whose dependency is a store /// to a field of that structure. -bool DSE::HandleFree(CallInst *F) { +bool DSEPass::HandleFree(CallInst *F, AliasAnalysis *AA, + MemoryDependenceResults *MD, DominatorTree *DT, + const TargetLibraryInfo *TLI) { bool MadeChange = false; MemoryLocation Loc = MemoryLocation(F->getOperand(0)); @@ -834,7 +778,9 @@ /// ... /// store i32 1, i32* %A /// ret void -bool DSE::handleEndBlock(BasicBlock &BB) { +bool DSEPass::handleEndBlock(BasicBlock &BB, AliasAnalysis *AA, + MemoryDependenceResults *MD, + const TargetLibraryInfo *TLI) { bool MadeChange = false; // Keep track of all of the stack objects that are dead at the end of the @@ -967,7 +913,7 @@ // Remove any allocas from the DeadPointer set that are loaded, as this // makes any stores above the access live. - RemoveAccessedObjects(LoadedLoc, DeadStackObjects, DL); + RemoveAccessedObjects(LoadedLoc, DeadStackObjects, DL, AA, TLI); // If all of the allocas were clobbered by the access then we're not going // to find anything else to process. @@ -981,9 +927,10 @@ /// RemoveAccessedObjects - Check to see if the specified location may alias any /// of the stack objects in the DeadStackObjects set. If so, they become live /// because the location is being loaded. -void DSE::RemoveAccessedObjects(const MemoryLocation &LoadedLoc, - SmallSetVector &DeadStackObjects, - const DataLayout &DL) { +void DSEPass::RemoveAccessedObjects( + const MemoryLocation &LoadedLoc, + SmallSetVector &DeadStackObjects, const DataLayout &DL, + AliasAnalysis *AA, const TargetLibraryInfo *TLI) { const Value *UnderlyingPointer = GetUnderlyingObject(LoadedLoc.Ptr, DL); // A constant can't be in the dead pointer set. @@ -1004,3 +951,79 @@ return !AA->isNoAlias(StackLoc, LoadedLoc); }); } + +PreservedAnalyses DSEPass::run(Function &F, FunctionAnalysisManager &AM) { + return runImpl(F, AM.getResult(F), + AM.getResult(F), + AM.getResult(F), + AM.getResult(F)); +} + +PreservedAnalyses DSEPass::runImpl(Function &F, AliasAnalysis &RunAA, + MemoryDependenceResults &RunMemDep, + DominatorTree &RunDT, + TargetLibraryInfo &RunTLI) { + + bool Changed = false; + for (BasicBlock &I : F) + // Only check non-dead blocks. Dead blocks may have strange pointer + // cycles that will confuse alias analysis. + if (RunDT.isReachableFromEntry(&I)) + Changed |= runOnBasicBlock(I, &RunAA, &RunMemDep, &RunDT, &RunTLI); + + return Changed ? PreservedAnalyses::none() : PreservedAnalyses::all(); +} + +/// A legacy pass for the legacy pass manager that wraps the \c DSE pass. +/// +/// This is in the llvm namespace purely to allow it to be a friend of the \c +/// DSE pass. +class llvm::dse::DSELegacyPass : public FunctionPass { + /// The DSE Implementation + DSEPass Impl; + +public: + DSELegacyPass() : FunctionPass(ID) { + initializeDSELegacyPassPass(*PassRegistry::getPassRegistry()); + } + + bool runOnFunction(Function &F) override { + if (skipFunction(F)) + return false; + + auto PA = + Impl.runImpl(F, getAnalysis().getAAResults(), + getAnalysis().getMemDep(), + getAnalysis().getDomTree(), + getAnalysis().getTLI()); + return !PA.areAllPreserved(); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesCFG(); + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + AU.addPreserved(); + AU.addPreserved(); + AU.addPreserved(); + } + + static char ID; // Pass identification, replacement for typeid +}; + +char DSELegacyPass::ID = 0; +INITIALIZE_PASS_BEGIN(DSELegacyPass, "dse", "Dead Store Elimination", false, + false) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) +INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) +INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_END(DSELegacyPass, "dse", "Dead Store Elimination", false, + false) + +FunctionPass *llvm::createDeadStoreEliminationPass() { + return new DSELegacyPass(); +} Index: lib/Transforms/Scalar/Scalar.cpp =================================================================== --- lib/Transforms/Scalar/Scalar.cpp +++ lib/Transforms/Scalar/Scalar.cpp @@ -40,7 +40,7 @@ initializeDCELegacyPassPass(Registry); initializeDeadInstEliminationPass(Registry); initializeScalarizerPass(Registry); - initializeDSEPass(Registry); + initializeDSELegacyPassPass(Registry); initializeGVNLegacyPassPass(Registry); initializeEarlyCSELegacyPassPass(Registry); initializeFlattenCFGPassPass(Registry); Index: test/Transforms/DeadStoreElimination/simple.ll =================================================================== --- test/Transforms/DeadStoreElimination/simple.ll +++ test/Transforms/DeadStoreElimination/simple.ll @@ -1,4 +1,5 @@ ; RUN: opt < %s -basicaa -dse -S | FileCheck %s +; RUN: opt < %s -aa-pipeline=basic-aa -passes=dse -S | FileCheck %s target datalayout = "E-p:64:64:64-a0:0:8-f32:32:32-f64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-v64:64:64-v128:128:128" declare void @llvm.memset.p0i8.i64(i8* nocapture, i8, i64, i32, i1) nounwind