Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -265,6 +265,7 @@ void initializeOptimizationRemarkEmitterWrapperPassPass(PassRegistry&); void initializeOptimizePHIsPass(PassRegistry&); void initializePAEvalPass(PassRegistry &); +void initializePDSELegacyPassPass(PassRegistry &); void initializePEIPass(PassRegistry&); void initializePGOIndirectCallPromotionLegacyPassPass(PassRegistry&); void initializePGOInstrumentationGenLegacyPassPass(PassRegistry&); Index: include/llvm/Transforms/Scalar/PDSE.h =================================================================== --- /dev/null +++ include/llvm/Transforms/Scalar/PDSE.h @@ -0,0 +1,27 @@ +//===- PDSE.h - PartialDead Store Elimination -----------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass eliminates fully and partially dead stores in a global and sparse +// manner. Consult the header comment in PDSE.cpp for further details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_TRANSFORMS_SCALAR_PDSE_H +#define LLVM_TRANSFORMS_SCALAR_PDSE_H + +#include "llvm/IR/Function.h" +#include "llvm/IR/PassManager.h" + +namespace llvm { +struct PDSEPass : public PassInfoMixin { + PreservedAnalyses run(Function &, FunctionAnalysisManager &); +}; +} + +#endif // LLVM_TRANSFORMS_SCALAR_PDSE_H Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -120,6 +120,7 @@ #include "llvm/Transforms/Scalar/NaryReassociate.h" #include "llvm/Transforms/Scalar/NewGVN.h" #include "llvm/Transforms/Scalar/PartiallyInlineLibCalls.h" +#include "llvm/Transforms/Scalar/PDSE.h" #include "llvm/Transforms/Scalar/Reassociate.h" #include "llvm/Transforms/Scalar/SCCP.h" #include "llvm/Transforms/Scalar/SROA.h" Index: lib/Passes/PassRegistry.def =================================================================== --- lib/Passes/PassRegistry.def +++ lib/Passes/PassRegistry.def @@ -173,6 +173,7 @@ FUNCTION_PASS("loop-load-elim", LoopLoadEliminationPass()) FUNCTION_PASS("loop-distribute", LoopDistributePass()) FUNCTION_PASS("loop-vectorize", LoopVectorizePass()) +FUNCTION_PASS("pdse", PDSEPass()) FUNCTION_PASS("print", PrintFunctionPass(dbgs())) FUNCTION_PASS("print", AssumptionPrinterPass(dbgs())) FUNCTION_PASS("print", BlockFrequencyPrinterPass(dbgs())) Index: lib/Transforms/Scalar/CMakeLists.txt =================================================================== --- lib/Transforms/Scalar/CMakeLists.txt +++ lib/Transforms/Scalar/CMakeLists.txt @@ -45,6 +45,7 @@ MergedLoadStoreMotion.cpp NaryReassociate.cpp NewGVN.cpp + PDSE.cpp PartiallyInlineLibCalls.cpp PlaceSafepoints.cpp Reassociate.cpp Index: lib/Transforms/Scalar/PDSE.cpp =================================================================== --- /dev/null +++ lib/Transforms/Scalar/PDSE.cpp @@ -0,0 +1,132 @@ +//===- PDSE.cpp - Partial 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 pass performs a variation of partial dead store elimination as described +// in: +// +// Register Promotion Sparse Partial Redundancy Elimination of Loads and Store +// https://doi.org/10.1145/277650.277659 +// +// "Partial" refers to the ability to transform partial store redundancies into +// full redundancies by inserting stores at appropriate split points. For +// instance: +// +// bb0: +// store i8 undef, i8* %x +// br i1 undef label %true, label %false +// true: +// store i8 undef, i8* %x +// br label %exit +// false: +// br label %exit +// exit: +// ret void +// +// The store in bb0 counts as partially redundant (with respect to the store in +// the true block) and can be made fully redundant by inserting a copy into the +// false block. +// +// For a gentler introduction to PRE, see: +// +// Partial Redundancy Elimination in SSA Form +// https://doi.org/10.1145/319301.319348 +// +// Differences between the papers and this implementation: +// - May-throw instructions count as killing occurrences in the factored +// redundancy graph of escaping stores; +// - TODO: Figure out partial overwrite tracking. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/AliasAnalysis.h" +#include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/PostDominators.h" +#include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/Pass.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Scalar/PDSE.h" + +#define DEBUG_TYPE "pdse" + +// TODO: Require BreakCriticalEdges to ensure that lambdas (resp. phis) dominate +// (resp. post-dominate) their successor (resp. predecessor) blocks (SSAPRE +// assumes this condition). + +using namespace llvm; + +static cl::opt + PrintFRG("print-frg", cl::init(false), cl::Hidden, + cl::desc("Print the factored redundancy graph of stores.")); + +namespace { +bool runPDSE(Function &F, AliasAnalysis &AA, const PostDominatorTree &PDT, + const TargetLibraryInfo &TLI) { + if (PrintFRG) { + DEBUG(dbgs() << "TODO: Print factored redundancy graph.\n"); + return false; + } else { + DEBUG(dbgs() << "Dummy PDSE pass.\n"); + } + return false; +} + +class PDSELegacyPass : public FunctionPass { +public: + PDSELegacyPass() : FunctionPass(ID) { + initializePDSELegacyPassPass(*PassRegistry::getPassRegistry()); + } + + bool runOnFunction(Function &F) override { + if (skipFunction(F)) + return false; + + return runPDSE(F, getAnalysis().getAAResults(), + getAnalysis().getPostDomTree(), + getAnalysis().getTLI()); + } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + + AU.setPreservesCFG(); + AU.addPreserved(); + AU.addPreserved(); + } + + static char ID; // Pass identification, replacement for typeid +}; +} // end anonymous namespace + +char PDSELegacyPass::ID = 0; + +INITIALIZE_PASS_BEGIN(PDSELegacyPass, "pdse", "Partial Dead Store Elimination", + false, false) +INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass) +INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) +INITIALIZE_PASS_END(PDSELegacyPass, "pdse", "Partial Dead Store Elimination", + false, false) + +namespace llvm { +PreservedAnalyses PDSEPass::run(Function &F, FunctionAnalysisManager &AM) { + if (!runPDSE(F, AM.getResult(F), + AM.getResult(F), + AM.getResult(F))) + return PreservedAnalyses::all(); + + PreservedAnalyses PA; + PA.preserveSet(); + PA.preserve(); + PA.preserve(); + return PA; +} +} // end namespace llvm Index: lib/Transforms/Scalar/Scalar.cpp =================================================================== --- lib/Transforms/Scalar/Scalar.cpp +++ lib/Transforms/Scalar/Scalar.cpp @@ -74,6 +74,7 @@ initializeMergedLoadStoreMotionLegacyPassPass(Registry); initializeNaryReassociateLegacyPassPass(Registry); initializePartiallyInlineLibCallsLegacyPassPass(Registry); + initializePDSELegacyPassPass(Registry); initializeReassociateLegacyPassPass(Registry); initializeRegToMemPass(Registry); initializeRewriteStatepointsForGCPass(Registry);