Index: include/llvm/Analysis/PostDominators.h =================================================================== --- include/llvm/Analysis/PostDominators.h +++ include/llvm/Analysis/PostDominators.h @@ -18,98 +18,85 @@ namespace llvm { -/// PostDominatorTree Class - Concrete subclass of DominatorTree that is used to -/// compute the post-dominator tree. -/// -struct PostDominatorTree : public FunctionPass { - static char ID; // Pass identification, replacement for typeid - DominatorTreeBase* DT; - - PostDominatorTree() : FunctionPass(ID) { - initializePostDominatorTreePass(*PassRegistry::getPassRegistry()); - DT = new DominatorTreeBase(true); - } - - ~PostDominatorTree() override; +/// PostDominatorTree Class - Concrete subclass of DominatorTreeBase that is +/// used to compute the post-dominator tree. +struct PostDominatorTree : public DominatorTreeBase { +public: + typedef DominatorTreeBase Base; - bool runOnFunction(Function &F) override; + PostDominatorTree() : DominatorTreeBase(true) {} - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.setPreservesAll(); + PostDominatorTree(PostDominatorTree &&Arg) + : Base(std::move(static_cast(Arg))) {} + PostDominatorTree &operator=(PostDominatorTree &&RHS) { + Base::operator=(std::move(static_cast(RHS))); + return *this; } +}; - inline const std::vector &getRoots() const { - return DT->getRoots(); - } +FunctionPass *createPostDomTree(); - inline DomTreeNode *getRootNode() const { +template <> +struct GraphTraits : public GraphTraits { + static NodeType *getEntryNode(PostDominatorTree *DT) { return DT->getRootNode(); } - inline DomTreeNode *operator[](BasicBlock *BB) const { - return DT->getNode(BB); + static nodes_iterator nodes_begin(PostDominatorTree *N) { + if (getEntryNode(N)) + return df_begin(getEntryNode(N)); + else + return df_end(getEntryNode(N)); } - inline DomTreeNode *getNode(BasicBlock *BB) const { - return DT->getNode(BB); + static nodes_iterator nodes_end(PostDominatorTree *N) { + return df_end(getEntryNode(N)); } +}; - inline bool dominates(DomTreeNode* A, DomTreeNode* B) const { - return DT->dominates(A, B); - } +/// \brief Analysis pass which computes a \c PostDominatorTree. +class PostDominatorTreeAnalysis { +public: + /// \brief Provide the result typedef for this analysis pass. + typedef PostDominatorTree Result; - inline bool dominates(const BasicBlock* A, const BasicBlock* B) const { - return DT->dominates(A, B); - } + /// \brief Opaque, unique identifier for this analysis pass. + static void *ID() { return (void *)&PassID; } - inline bool properlyDominates(const DomTreeNode* A, DomTreeNode* B) const { - return DT->properlyDominates(A, B); - } + /// \brief Run the analysis pass over a function and produce a post-dominator + /// tree. + PostDominatorTree run(Function &F); - inline bool properlyDominates(BasicBlock* A, BasicBlock* B) const { - return DT->properlyDominates(A, B); - } + /// \brief Provide access to a name for this pass for debugging purposes. + static StringRef name() { return "PostDominatorTreeAnalysis"; } - inline BasicBlock *findNearestCommonDominator(BasicBlock *A, BasicBlock *B) { - return DT->findNearestCommonDominator(A, B); - } +private: + static char PassID; +}; - inline const BasicBlock *findNearestCommonDominator(const BasicBlock *A, - const BasicBlock *B) { - return DT->findNearestCommonDominator(A, B); - } +/// \brief Legacy analysis pass which computes a \c PostDominatorTree. +class PostDominatorTreePass : public FunctionPass { + PostDominatorTree PDT; - /// Get all nodes post-dominated by R, including R itself. - void getDescendants(BasicBlock *R, - SmallVectorImpl &Result) const { - DT->getDescendants(R, Result); - } +public: + static char ID; - void releaseMemory() override { - DT->releaseMemory(); + PostDominatorTreePass() : FunctionPass(ID) { + initializePostDominatorTreePassPass(*PassRegistry::getPassRegistry()); } - void print(raw_ostream &OS, const Module*) const override; -}; + PostDominatorTree &getDomTree() { return PDT; } + const PostDominatorTree &getDomTree() const { return PDT; } -FunctionPass* createPostDomTree(); + bool runOnFunction(Function &F) override; -template <> struct GraphTraits - : public GraphTraits { - static NodeType *getEntryNode(PostDominatorTree *DT) { - return DT->getRootNode(); + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesAll(); } - static nodes_iterator nodes_begin(PostDominatorTree *N) { - if (getEntryNode(N)) - return df_begin(getEntryNode(N)); - else - return df_end(getEntryNode(N)); - } + void releaseMemory() override { PDT.releaseMemory(); } - static nodes_iterator nodes_end(PostDominatorTree *N) { - return df_end(getEntryNode(N)); - } + void print(raw_ostream &OS, const Module *) const override; }; } // End llvm namespace Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -224,7 +224,7 @@ void initializePostDomOnlyViewerPass(PassRegistry&); void initializePostDomPrinterPass(PassRegistry&); void initializePostDomViewerPass(PassRegistry&); -void initializePostDominatorTreePass(PassRegistry&); +void initializePostDominatorTreePassPass(PassRegistry &); void initializePostRASchedulerPass(PassRegistry&); void initializePostMachineSchedulerPass(PassRegistry&); void initializePrintFunctionPassWrapperPass(PassRegistry&); Index: include/llvm/Transforms/Utils/Local.h =================================================================== --- include/llvm/Transforms/Utils/Local.h +++ include/llvm/Transforms/Utils/Local.h @@ -15,6 +15,7 @@ #ifndef LLVM_TRANSFORMS_UTILS_LOCAL_H #define LLVM_TRANSFORMS_UTILS_LOCAL_H +#include "llvm/Analysis/PostDominators.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/GetElementPtrTypeIterator.h" #include "llvm/IR/IRBuilder.h" @@ -136,7 +137,8 @@ /// the basic block that was pointed to. /// bool SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, - unsigned BonusInstThreshold, AssumptionCache *AC = nullptr); + unsigned BonusInstThreshold, AssumptionCache *AC = nullptr, + PostDominatorTree *PDT = nullptr); /// FlatternCFG - This function is used to flatten a CFG. For /// example, it uses parallel-and and parallel-or mode to collapse Index: lib/Analysis/Analysis.cpp =================================================================== --- lib/Analysis/Analysis.cpp +++ lib/Analysis/Analysis.cpp @@ -58,7 +58,7 @@ initializeMemDerefPrinterPass(Registry); initializeMemoryDependenceAnalysisPass(Registry); initializeModuleDebugInfoPrinterPass(Registry); - initializePostDominatorTreePass(Registry); + initializePostDominatorTreePassPass(Registry); initializeRegionInfoPassPass(Registry); initializeRegionViewerPass(Registry); initializeRegionPrinterPass(Registry); Index: lib/Analysis/DivergenceAnalysis.cpp =================================================================== --- lib/Analysis/DivergenceAnalysis.cpp +++ lib/Analysis/DivergenceAnalysis.cpp @@ -94,7 +94,7 @@ void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); - AU.addRequired(); + AU.addRequired(); AU.setPreservesAll(); } @@ -119,7 +119,7 @@ INITIALIZE_PASS_BEGIN(DivergenceAnalysis, "divergence", "Divergence Analysis", false, true) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) -INITIALIZE_PASS_DEPENDENCY(PostDominatorTree) +INITIALIZE_PASS_DEPENDENCY(PostDominatorTreePass) INITIALIZE_PASS_END(DivergenceAnalysis, "divergence", "Divergence Analysis", false, true) @@ -302,9 +302,9 @@ return false; DivergentValues.clear(); - DivergencePropagator DP(F, TTI, - getAnalysis().getDomTree(), - getAnalysis(), DivergentValues); + DivergencePropagator DP( + F, TTI, getAnalysis().getDomTree(), + getAnalysis().getDomTree(), DivergentValues); DP.populateWithSourcesOfDivergence(); DP.propagate(); return false; Index: lib/Analysis/DomPrinter.cpp =================================================================== --- lib/Analysis/DomPrinter.cpp +++ lib/Analysis/DomPrinter.cpp @@ -87,6 +87,12 @@ } }; +struct PostDominatorTreePassAnalysisGraphTraits { + static PostDominatorTree *getGraph(PostDominatorTreePass *PDTP) { + return &PDTP->getDomTree(); + } +}; + struct DomViewer : public DOTGraphTraitsViewer< DominatorTreeWrapperPass, false, DominatorTree *, DominatorTreeWrapperPassAnalysisGraphTraits> { @@ -111,22 +117,28 @@ } }; -struct PostDomViewer - : public DOTGraphTraitsViewer { +struct PostDomViewer : public DOTGraphTraitsViewer< + PostDominatorTreePass, false, PostDominatorTree *, + PostDominatorTreePassAnalysisGraphTraits> { static char ID; - PostDomViewer() : - DOTGraphTraitsViewer("postdom", ID){ + PostDomViewer() + : DOTGraphTraitsViewer( + "postdom", ID) { initializePostDomViewerPass(*PassRegistry::getPassRegistry()); } }; -struct PostDomOnlyViewer - : public DOTGraphTraitsViewer { +struct PostDomOnlyViewer : public DOTGraphTraitsViewer< + PostDominatorTreePass, true, PostDominatorTree *, + PostDominatorTreePassAnalysisGraphTraits> { static char ID; - PostDomOnlyViewer() : - DOTGraphTraitsViewer("postdomonly", ID){ - initializePostDomOnlyViewerPass(*PassRegistry::getPassRegistry()); - } + PostDomOnlyViewer() + : DOTGraphTraitsViewer( + "postdomonly", ID) { + initializePostDomOnlyViewerPass(*PassRegistry::getPassRegistry()); + } }; } // end anonymous namespace @@ -174,20 +186,27 @@ } }; -struct PostDomPrinter - : public DOTGraphTraitsPrinter { +struct PostDomPrinter : public DOTGraphTraitsPrinter< + PostDominatorTreePass, false, PostDominatorTree *, + PostDominatorTreePassAnalysisGraphTraits> { static char ID; - PostDomPrinter() : - DOTGraphTraitsPrinter("postdom", ID) { + PostDomPrinter() + : DOTGraphTraitsPrinter( + "postdom", ID) { initializePostDomPrinterPass(*PassRegistry::getPassRegistry()); } }; struct PostDomOnlyPrinter - : public DOTGraphTraitsPrinter { + : public DOTGraphTraitsPrinter { static char ID; - PostDomOnlyPrinter() : - DOTGraphTraitsPrinter("postdomonly", ID) { + PostDomOnlyPrinter() + : DOTGraphTraitsPrinter( + "postdomonly", ID) { initializePostDomOnlyPrinterPass(*PassRegistry::getPassRegistry()); } }; Index: lib/Analysis/PostDominators.cpp =================================================================== --- lib/Analysis/PostDominators.cpp +++ lib/Analysis/PostDominators.cpp @@ -26,25 +26,29 @@ // PostDominatorTree Implementation //===----------------------------------------------------------------------===// -char PostDominatorTree::ID = 0; -INITIALIZE_PASS(PostDominatorTree, "postdomtree", +char PostDominatorTreePass::ID = 0; +INITIALIZE_PASS(PostDominatorTreePass, "postdomtree", "Post-Dominator Tree Construction", true, true) -bool PostDominatorTree::runOnFunction(Function &F) { - DT->recalculate(F); +bool PostDominatorTreePass::runOnFunction(Function &F) { + PDT.recalculate(F); return false; } -PostDominatorTree::~PostDominatorTree() { - delete DT; +void PostDominatorTreePass::print(raw_ostream &OS, const Module *) const { + PDT.print(OS); } -void PostDominatorTree::print(raw_ostream &OS, const Module *) const { - DT->print(OS); -} +FunctionPass *llvm::createPostDomTree() { return new PostDominatorTreePass(); } +//===----------------------------------------------------------------------===// +// PostDominatorTreeAnalysis Implementation +//===----------------------------------------------------------------------===// -FunctionPass* llvm::createPostDomTree() { - return new PostDominatorTree(); +PostDominatorTree PostDominatorTreeAnalysis::run(Function &F) { + PostDominatorTree PDT; + PDT.recalculate(F); + return PDT; } +char PostDominatorTreeAnalysis::PassID; Index: lib/Analysis/RegionInfo.cpp =================================================================== --- lib/Analysis/RegionInfo.cpp +++ lib/Analysis/RegionInfo.cpp @@ -119,7 +119,7 @@ releaseMemory(); auto DT = &getAnalysis().getDomTree(); - auto PDT = &getAnalysis(); + auto PDT = &getAnalysis().getDomTree(); auto DF = &getAnalysis(); RI.recalculate(F, DT, PDT, DF); @@ -137,7 +137,7 @@ void RegionInfoPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequiredTransitive(); - AU.addRequired(); + AU.addRequired(); AU.addRequired(); } @@ -156,7 +156,7 @@ INITIALIZE_PASS_BEGIN(RegionInfoPass, "regions", "Detect single entry single exit regions", true, true) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) -INITIALIZE_PASS_DEPENDENCY(PostDominatorTree) +INITIALIZE_PASS_DEPENDENCY(PostDominatorTreePass) INITIALIZE_PASS_DEPENDENCY(DominanceFrontier) INITIALIZE_PASS_END(RegionInfoPass, "regions", "Detect single entry single exit regions", true, true) Index: lib/CodeGen/MachineRegionInfo.cpp =================================================================== --- lib/CodeGen/MachineRegionInfo.cpp +++ lib/CodeGen/MachineRegionInfo.cpp @@ -104,7 +104,7 @@ void MachineRegionInfoPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequiredTransitive(); - AU.addRequired(); + AU.addRequired(); AU.addRequired(); } Index: lib/Passes/PassBuilder.cpp =================================================================== --- lib/Passes/PassBuilder.cpp +++ lib/Passes/PassBuilder.cpp @@ -20,6 +20,7 @@ #include "llvm/Analysis/CGSCCPassManager.h" #include "llvm/Analysis/LazyCallGraph.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/TargetLibraryInfo.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/IR/Dominators.h" Index: lib/Passes/PassRegistry.def =================================================================== --- lib/Passes/PassRegistry.def +++ lib/Passes/PassRegistry.def @@ -52,6 +52,7 @@ #endif FUNCTION_ANALYSIS("assumptions", AssumptionAnalysis()) FUNCTION_ANALYSIS("domtree", DominatorTreeAnalysis()) +FUNCTION_ANALYSIS("postdomtree", PostDominatorTreeAnalysis()) FUNCTION_ANALYSIS("loops", LoopAnalysis()) FUNCTION_ANALYSIS("no-op-function", NoOpFunctionAnalysis()) FUNCTION_ANALYSIS("targetlibinfo", TargetLibraryAnalysis()) Index: lib/Transforms/Scalar/SampleProfile.cpp =================================================================== --- lib/Transforms/Scalar/SampleProfile.cpp +++ lib/Transforms/Scalar/SampleProfile.cpp @@ -97,7 +97,7 @@ AU.setPreservesCFG(); AU.addRequired(); AU.addRequired(); - AU.addRequired(); + AU.addRequired(); } protected: @@ -364,7 +364,7 @@ // class by making BB2's equivalence class be BB1. DominatedBBs.clear(); DT->getDescendants(BB1, DominatedBBs); - findEquivalencesFor(BB1, DominatedBBs, PDT->DT); + findEquivalencesFor(BB1, DominatedBBs, PDT); // Repeat the same logic for all the blocks post-dominated by BB1. // We are looking for every basic block BB2 such that: @@ -732,7 +732,7 @@ INITIALIZE_PASS_BEGIN(SampleProfileLoader, "sample-profile", "Sample Profile loader", false, false) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) -INITIALIZE_PASS_DEPENDENCY(PostDominatorTree) +INITIALIZE_PASS_DEPENDENCY(PostDominatorTreePass) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(AddDiscriminators) INITIALIZE_PASS_END(SampleProfileLoader, "sample-profile", @@ -763,7 +763,7 @@ return false; DT = &getAnalysis().getDomTree(); - PDT = &getAnalysis(); + PDT = &getAnalysis().getDomTree(); LI = &getAnalysis().getLoopInfo(); Ctx = &F.getParent()->getContext(); Samples = Reader->getSamplesFor(F); Index: lib/Transforms/Scalar/SimplifyCFGPass.cpp =================================================================== --- lib/Transforms/Scalar/SimplifyCFGPass.cpp +++ lib/Transforms/Scalar/SimplifyCFGPass.cpp @@ -27,6 +27,7 @@ #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/TargetTransformInfo.h" +#include "llvm/Analysis/PostDominators.h" #include "llvm/IR/Attributes.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" @@ -127,7 +128,7 @@ /// iterativelySimplifyCFG - Call SimplifyCFG on all the blocks in the function, /// iterating until no more changes are made. static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI, - AssumptionCache *AC, + AssumptionCache *AC, PostDominatorTree *PDT, unsigned BonusInstThreshold) { bool Changed = false; bool LocalChange = true; @@ -137,7 +138,7 @@ // Loop over all of the basic blocks and remove them if they are unneeded... // for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) { - if (SimplifyCFG(BBIt++, TTI, BonusInstThreshold, AC)) { + if (SimplifyCFG(BBIt++, TTI, BonusInstThreshold, AC, PDT)) { LocalChange = true; ++NumSimpl; } @@ -148,10 +149,11 @@ } static bool simplifyFunctionCFG(Function &F, const TargetTransformInfo &TTI, - AssumptionCache *AC, int BonusInstThreshold) { + AssumptionCache *AC, PostDominatorTree *PDT, + int BonusInstThreshold) { bool EverChanged = removeUnreachableBlocks(F); EverChanged |= mergeEmptyReturnBlocks(F); - EverChanged |= iterativelySimplifyCFG(F, TTI, AC, BonusInstThreshold); + EverChanged |= iterativelySimplifyCFG(F, TTI, AC, PDT, BonusInstThreshold); // If neither pass changed anything, we're done. if (!EverChanged) return false; @@ -165,7 +167,7 @@ return true; do { - EverChanged = iterativelySimplifyCFG(F, TTI, AC, BonusInstThreshold); + EverChanged = iterativelySimplifyCFG(F, TTI, AC, PDT, BonusInstThreshold); EverChanged |= removeUnreachableBlocks(F); } while (EverChanged); @@ -182,8 +184,9 @@ AnalysisManager *AM) { auto &TTI = AM->getResult(F); auto &AC = AM->getResult(F); + auto &PDT = AM->getResult(F); - if (!simplifyFunctionCFG(F, TTI, &AC, BonusInstThreshold)) + if (!simplifyFunctionCFG(F, TTI, &AC, &PDT, BonusInstThreshold)) return PreservedAnalyses::none(); return PreservedAnalyses::all(); @@ -205,12 +208,14 @@ &getAnalysis().getAssumptionCache(F); const TargetTransformInfo &TTI = getAnalysis().getTTI(F); - return simplifyFunctionCFG(F, TTI, AC, BonusInstThreshold); + PostDominatorTree *PDT = &getAnalysis().getDomTree(); + return simplifyFunctionCFG(F, TTI, AC, PDT, BonusInstThreshold); } void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); AU.addRequired(); + AU.addRequired(); } }; } @@ -220,6 +225,7 @@ false) INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) +INITIALIZE_PASS_DEPENDENCY(PostDominatorTreePass) INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG", false, false) Index: lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- lib/Transforms/Utils/SimplifyCFG.cpp +++ lib/Transforms/Utils/SimplifyCFG.cpp @@ -20,6 +20,7 @@ #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/InstructionSimplify.h" +#include "llvm/Analysis/PostDominators.h" #include "llvm/Analysis/TargetTransformInfo.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/IR/CFG.h" @@ -80,6 +81,7 @@ STATISTIC(NumTableCmpReuses, "Number of reused switch table lookup compares"); STATISTIC(NumSinkCommons, "Number of common instructions sunk down to the end block"); STATISTIC(NumSpeculations, "Number of speculative executed instructions"); +STATISTIC(NumCmpReplaced, "Number of comparison instructions replaced"); namespace { // The first field contains the value that the switch produces when a certain @@ -113,6 +115,7 @@ const DataLayout &DL; unsigned BonusInstThreshold; AssumptionCache *AC; + PostDominatorTree *PDT; Value *isValueEqualityComparison(TerminatorInst *TI); BasicBlock *GetValueEqualityComparisonCases(TerminatorInst *TI, std::vector &Cases); @@ -132,8 +135,10 @@ public: SimplifyCFGOpt(const TargetTransformInfo &TTI, const DataLayout &DL, - unsigned BonusInstThreshold, AssumptionCache *AC) - : TTI(TTI), DL(DL), BonusInstThreshold(BonusInstThreshold), AC(AC) {} + unsigned BonusInstThreshold, AssumptionCache *AC, + PostDominatorTree *PDT) + : TTI(TTI), DL(DL), BonusInstThreshold(BonusInstThreshold), AC(AC), + PDT(PDT) {} bool run(BasicBlock *BB); }; } @@ -2700,7 +2705,7 @@ static bool TryToSimplifyUncondBranchWithICmpInIt( ICmpInst *ICI, IRBuilder<> &Builder, const DataLayout &DL, const TargetTransformInfo &TTI, unsigned BonusInstThreshold, - AssumptionCache *AC) { + AssumptionCache *AC, PostDominatorTree *PDT) { BasicBlock *BB = ICI->getParent(); // If the block has any PHIs in it or the icmp has multiple uses, it is too @@ -2733,7 +2738,7 @@ ICI->eraseFromParent(); } // BB is now empty, so it is likely to simplify away. - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; } // Ok, the block is reachable from the default dest. If the constant we're @@ -2749,7 +2754,7 @@ ICI->replaceAllUsesWith(V); ICI->eraseFromParent(); // BB is now empty, so it is likely to simplify away. - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; } // The use of the icmp has to be in the 'end' block, by the only PHI node in @@ -4279,12 +4284,12 @@ // see if that predecessor totally determines the outcome of this switch. if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) if (SimplifyEqualityComparisonWithOnlyPredecessor(SI, OnlyPred, Builder)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; Value *Cond = SI->getCondition(); if (SelectInst *Select = dyn_cast(Cond)) if (SimplifySwitchOnSelect(SI, Select)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; // If the block only contains the switch, see if we can fold the block // away into any preds. @@ -4294,25 +4299,25 @@ ++BBI; if (SI == &*BBI) if (FoldValueComparisonIntoPredecessors(SI, Builder)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; } // Try to transform the switch into an icmp and a branch. if (TurnSwitchRangeIntoICmp(SI, Builder)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; // Remove unreachable cases. if (EliminateDeadSwitchCases(SI, AC, DL)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; if (SwitchToSelect(SI, Builder, AC, DL)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; if (ForwardSwitchConditionToPHI(SI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; if (SwitchToLookupTable(SI, Builder, DL, TTI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; return false; } @@ -4349,7 +4354,7 @@ if (SelectInst *SI = dyn_cast(IBI->getAddress())) { if (SimplifyIndirectBrOnSelect(IBI, SI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; } return Changed; } @@ -4450,7 +4455,7 @@ ; if (I->isTerminator() && TryToSimplifyUncondBranchWithICmpInIt(ICI, Builder, DL, TTI, - BonusInstThreshold, AC)) + BonusInstThreshold, AC, PDT)) return true; } @@ -4468,7 +4473,7 @@ // predecessor and use logical operations to update the incoming value // for PHI nodes in common successor. if (FoldBranchToCommonDest(BI, BonusInstThreshold)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; return false; } @@ -4483,7 +4488,7 @@ // switch. if (BasicBlock *OnlyPred = BB->getSinglePredecessor()) if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; // This block must be empty, except for the setcond inst, if it exists. // Ignore dbg intrinsics. @@ -4493,14 +4498,14 @@ ++I; if (&*I == BI) { if (FoldValueComparisonIntoPredecessors(BI, Builder)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; } else if (&*I == cast(BI->getCondition())){ ++I; // Ignore dbg intrinsics. while (isa(I)) ++I; if (&*I == BI && FoldValueComparisonIntoPredecessors(BI, Builder)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; } } @@ -4512,7 +4517,7 @@ // branches to us and one of our successors, fold the comparison into the // predecessor and use logical operations to pick the right destination. if (FoldBranchToCommonDest(BI, BonusInstThreshold)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; // We have a conditional branch to two blocks that are only reachable // from BI. We know that the condbr dominates the two blocks, so see if @@ -4521,7 +4526,7 @@ if (BI->getSuccessor(0)->getSinglePredecessor()) { if (BI->getSuccessor(1)->getSinglePredecessor()) { if (HoistThenElseCodeToIf(BI, TTI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; } else { // If Successor #1 has multiple preds, we may be able to conditionally // execute Successor #0 if it branches to Successor #1. @@ -4529,7 +4534,7 @@ if (Succ0TI->getNumSuccessors() == 1 && Succ0TI->getSuccessor(0) == BI->getSuccessor(1)) if (SpeculativelyExecuteBB(BI, BI->getSuccessor(0), TTI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; } } else if (BI->getSuccessor(1)->getSinglePredecessor()) { // If Successor #0 has multiple preds, we may be able to conditionally @@ -4538,7 +4543,7 @@ if (Succ1TI->getNumSuccessors() == 1 && Succ1TI->getSuccessor(0) == BI->getSuccessor(0)) if (SpeculativelyExecuteBB(BI, BI->getSuccessor(1), TTI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; } // If this is a branch on a phi node in the current block, thread control @@ -4546,14 +4551,14 @@ if (PHINode *PN = dyn_cast(BI->getCondition())) if (PN->getParent() == BI->getParent()) if (FoldCondBranchOnPHI(BI, DL)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; // Scan predecessor blocks for conditional branches. for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) if (BranchInst *PBI = dyn_cast((*PI)->getTerminator())) if (PBI != BI && PBI->isConditional()) if (SimplifyCondBranchToCondBranch(PBI, BI)) - return SimplifyCFG(BB, TTI, BonusInstThreshold, AC) | true; + return SimplifyCFG(BB, TTI, BonusInstThreshold, AC, PDT) | true; return false; } @@ -4601,7 +4606,8 @@ /// If BB has an incoming value that will always trigger undefined behavior /// (eg. null pointer dereference), remove the branch leading here. -static bool removeUndefIntroducingPredecessor(BasicBlock *BB) { +static bool removeUndefIntroducingPredecessor(BasicBlock *BB, + PostDominatorTree *PDT) { for (BasicBlock::iterator i = BB->begin(); PHINode *PHI = dyn_cast(i); ++i) for (unsigned i = 0, e = PHI->getNumIncomingValues(); i != e; ++i) @@ -4610,13 +4616,26 @@ IRBuilder<> Builder(T); if (BranchInst *BI = dyn_cast(T)) { BB->removePredecessor(PHI->getIncomingBlock(i)); - // Turn uncoditional branches into unreachables and remove the dead + // Turn unconditional branches into unreachables and remove the dead // destination from conditional branches. if (BI->isUnconditional()) Builder.CreateUnreachable(); - else - Builder.CreateBr(BI->getSuccessor(0) == BB ? BI->getSuccessor(1) : - BI->getSuccessor(0)); + else { + bool PickFirst = BI->getSuccessor(1) == BB; + Builder.CreateBr(PickFirst ? BI->getSuccessor(0) + : BI->getSuccessor(1)); + if (PDT) { + auto Cond = dyn_cast(BI->getCondition()); + if (PDT->dominates(BB, Cond->getParent())) { + // Inline the result of the conditional check downstream as a + // constant, and then get rid of it if possible. + Value *Const = ConstantInt::get(Cond->getType(), PickFirst); + Cond->replaceAllUsesWith(Const); + RecursivelyDeleteTriviallyDeadInstructions(Cond); + NumCmpReplaced++; + } + } + } BI->eraseFromParent(); return true; } @@ -4650,7 +4669,7 @@ Changed |= EliminateDuplicatePHINodes(BB); // Check for and remove branches that will always cause undefined behavior. - Changed |= removeUndefIntroducingPredecessor(BB); + Changed |= removeUndefIntroducingPredecessor(BB, PDT); // Merge basic blocks into their predecessor if there is only one distinct // pred, and if there is only one distinct successor of the predecessor, and @@ -4697,7 +4716,8 @@ /// of the CFG. It returns true if a modification was made. /// bool llvm::SimplifyCFG(BasicBlock *BB, const TargetTransformInfo &TTI, - unsigned BonusInstThreshold, AssumptionCache *AC) { + unsigned BonusInstThreshold, AssumptionCache *AC, + PostDominatorTree *PDT) { return SimplifyCFGOpt(TTI, BB->getModule()->getDataLayout(), - BonusInstThreshold, AC).run(BB); + BonusInstThreshold, AC, PDT).run(BB); } Index: test/Transforms/SimplifyCFG/load-means-not-null.ll =================================================================== --- /dev/null +++ test/Transforms/SimplifyCFG/load-means-not-null.ll @@ -0,0 +1,45 @@ +; RUN: opt < %s -simplifycfg -S | FileCheck %s + +declare void @g(i8) + +; CHECK-LABEL: @test_postdominate +; CHECK-NEXT: a: +; CHECK-NEXT: call void @g(i8 0) +; CHECK: ret i1 true +define i1 @test_postdominate(i8* %mem) { + %test = icmp eq i8* %mem, null + br i1 %test, label %a, label %b +a: + call void @g(i8 0) + br label %c +b: + br label %c +c: + %join = phi i8* [ %mem, %a ], [ null, %b ] + %gep = getelementptr i8, i8* %join, i64 4 + %res = load i8, i8* %gep + ret i1 %test +} + +; CHECK-LABEL: @test_doesnt_postdominate +; CHECK: ret i1 %test +define i1 @test_doesnt_postdominate(i8* %mem, i1 %bool) { + %test = icmp eq i8* %mem, null + br i1 %bool, label %start, label %return + +start: + br i1 %test, label %a, label %b +a: + call void @g(i8 0) + br label %c +b: + br label %c +c: + %join = phi i8* [ %mem, %a ], [ null, %b ] + %gep = getelementptr i8, i8* %join, i64 4 + %res = load i8, i8* %gep + br label %return + +return: + ret i1 %test +} Index: test/Transforms/SimplifyCFG/phi-undef-loadstore.ll =================================================================== --- test/Transforms/SimplifyCFG/phi-undef-loadstore.ll +++ test/Transforms/SimplifyCFG/phi-undef-loadstore.ll @@ -25,10 +25,9 @@ ret i32 %tmp9 ; CHECK-LABEL: @test1( -; CHECK: if.else: -; CHECK: br label %if.end7 - -; CHECK: phi i32* [ %a, %if.then ], [ %c, %if.else ] +; CHECK: tail call void @bar() +; CHECK: %c.a = select i1 %tobool, i32* %c, i32* %a +; CHECK: %tmp9 = load i32, i32* %c.a } define i32 @test2(i32* %a, i32 %b, i32* %c, i32 %d) nounwind { @@ -53,9 +52,8 @@ %tmp9 = load i32, i32* %x.0 ret i32 %tmp9 ; CHECK-LABEL: @test2( -; CHECK: if.else: -; CHECK: unreachable - +; CHECK: tail call void @bar() +; CHECK: %tmp9 = load i32, i32* %a ; CHECK-NOT: phi }