Index: include/llvm/Transforms/Utils/Local.h =================================================================== --- include/llvm/Transforms/Utils/Local.h +++ include/llvm/Transforms/Utils/Local.h @@ -41,6 +41,7 @@ class DIBuilder; class AliasAnalysis; class DominatorTree; +class LoopInfo; template class SmallVectorImpl; @@ -281,6 +282,15 @@ /// Returns true if any basic block was removed. bool removeUnreachableBlocks(Function &F); +/// \brief Remove all blocks which fail the isReachableFromEntry predicate on +/// the provided domtree. This is less aggressive about removing dead code +/// than removeUnreachableBlocks, but is able to keep various analyzes up to +/// date in the process. Calling this function is sufficient to ensure that +/// dominance questions on any remaining instructions return sensical results; +/// no self reference cycles can remain. +bool removeBlocksNotReachableFromEntry(Function &F, DominatorTree &DT, + LoopInfo *LI = nullptr); + /// \brief Combine the metadata of two instructions so that K can replace J /// /// Metadata not listed as known via KnownIDs is removed Index: lib/Transforms/Scalar/PlaceSafepoints.cpp =================================================================== --- lib/Transforms/Scalar/PlaceSafepoints.cpp +++ lib/Transforms/Scalar/PlaceSafepoints.cpp @@ -110,11 +110,9 @@ namespace { -/// An analysis pass whose purpose is to identify each of the backedges in +/// An helper class whose purpose is to identify each of the backedges in /// the function which require a safepoint poll to be inserted. -struct PlaceBackedgeSafepointsImpl : public FunctionPass { - static char ID; - +struct FindBackedgeSafepointsHelper { /// The output of the pass - gives a list of each backedge (described by /// pointing at the branch) which need a poll inserted. std::vector PollLocations; @@ -123,14 +121,13 @@ /// the call dependend placement opts. bool CallSafepointsEnabled; - ScalarEvolution *SE = nullptr; DominatorTree *DT = nullptr; LoopInfo *LI = nullptr; + ScalarEvolution *SE = nullptr; - PlaceBackedgeSafepointsImpl(bool CallSafepoints = false) - : FunctionPass(ID), CallSafepointsEnabled(CallSafepoints) { - initializePlaceBackedgeSafepointsImplPass(*PassRegistry::getPassRegistry()); - } + FindBackedgeSafepointsHelper(bool CallSafepoints, DominatorTree *DT, + LoopInfo *LI, ScalarEvolution *SE) + : CallSafepointsEnabled(CallSafepoints), DT(DT), LI(LI), SE(SE) {} bool runOnLoop(Loop *); void runOnLoopAndSubLoops(Loop *L) { @@ -140,24 +137,12 @@ runOnLoop(L); } - bool runOnFunction(Function &F) override { - SE = &getAnalysis(); - DT = &getAnalysis().getDomTree(); - LI = &getAnalysis().getLoopInfo(); + bool runOnFunction(Function &F) { for (auto I = LI->begin(), E = LI->end(); I != E; I++) { runOnLoopAndSubLoops(*I); } return false; } - - void getAnalysisUsage(AnalysisUsage &AU) const override { - AU.addRequired(); - AU.addRequired(); - AU.addRequired(); - // We no longer modify the IR at all in this pass. Thus all - // analysis are preserved. - AU.setPreservesAll(); - } }; } @@ -175,6 +160,10 @@ bool runOnFunction(Function &F) override; void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.addRequired(); + AU.addRequired(); + AU.addRequired(); + // We modify the graph wholesale (inlining, block insertion, etc). We // preserve nothing at the moment. We could potentially preserve dom tree // if that was worth doing @@ -326,7 +315,7 @@ } } -bool PlaceBackedgeSafepointsImpl::runOnLoop(Loop *L) { +bool FindBackedgeSafepointsHelper::runOnLoop(Loop *L) { // Loop through all loop latches (branches controlling backedges). We need // to place a safepoint on every backedge (potentially). // Note: In common usage, there will be only one edge due to LoopSimplify @@ -553,39 +542,30 @@ bool modified = false; + ScalarEvolution *SE = &getAnalysis(); + DominatorTree &DT = *&getAnalysis().getDomTree(); + LoopInfo *LI = &getAnalysis().getLoopInfo(); + // In various bits below, we rely on the fact that uses are reachable from // defs. When there are basic blocks unreachable from the entry, dominance // and reachablity queries return non-sensical results. Thus, we preprocess - // the function to ensure these properties hold. - modified |= removeUnreachableBlocks(F); + // the function to ensure these properties hold. Note that all of DT, SE, & + // LI are preserved by this call. (SE is handled implicitly via value handle + // callbacks.) + modified = removeBlocksNotReachableFromEntry(F, DT, LI); // STEP 1 - Insert the safepoint polling locations. We do not need to // actually insert parse points yet. That will be done for all polls and // calls in a single pass. - DominatorTree DT; - DT.recalculate(F); - SmallVector PollsNeeded; std::vector ParsePointNeeded; if (enableBackedgeSafepoints(F)) { - // Construct a pass manager to run the LoopPass backedge logic. We - // need the pass manager to handle scheduling all the loop passes - // appropriately. Doing this by hand is painful and just not worth messing - // with for the moment. - legacy::FunctionPassManager FPM(F.getParent()); - bool CanAssumeCallSafepoints = enableCallSafepoints(F); - PlaceBackedgeSafepointsImpl *PBS = - new PlaceBackedgeSafepointsImpl(CanAssumeCallSafepoints); - FPM.add(PBS); - FPM.run(F); - - // We preserve dominance information when inserting the poll, otherwise - // we'd have to recalculate this on every insert - DT.recalculate(F); - - auto &PollLocations = PBS->PollLocations; + FindBackedgeSafepointsHelper PBS(enableCallSafepoints(F), &DT, LI, SE); + PBS.runOnFunction(F); + + auto &PollLocations = PBS.PollLocations; auto OrderByBBName = [](Instruction *a, Instruction *b) { return a->getParent()->getName() < b->getParent()->getName(); @@ -730,25 +710,17 @@ return modified; } -char PlaceBackedgeSafepointsImpl::ID = 0; char PlaceSafepoints::ID = 0; FunctionPass *llvm::createPlaceSafepointsPass() { return new PlaceSafepoints(); } -INITIALIZE_PASS_BEGIN(PlaceBackedgeSafepointsImpl, - "place-backedge-safepoints-impl", - "Place Backedge Safepoints", false, false) +INITIALIZE_PASS_BEGIN(PlaceSafepoints, "place-safepoints", "Place Safepoints", + false, false) INITIALIZE_PASS_DEPENDENCY(ScalarEvolution) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) -INITIALIZE_PASS_END(PlaceBackedgeSafepointsImpl, - "place-backedge-safepoints-impl", - "Place Backedge Safepoints", false, false) - -INITIALIZE_PASS_BEGIN(PlaceSafepoints, "place-safepoints", "Place Safepoints", - false, false) INITIALIZE_PASS_END(PlaceSafepoints, "place-safepoints", "Place Safepoints", false, false) Index: lib/Transforms/Scalar/RewriteStatepointsForGC.cpp =================================================================== --- lib/Transforms/Scalar/RewriteStatepointsForGC.cpp +++ lib/Transforms/Scalar/RewriteStatepointsForGC.cpp @@ -1969,7 +1969,7 @@ // resulting IR less confusing to human readers. Rather than be fancy, we // just reuse a utility function which removes the unreachable blocks. if (HasUnreachableStatepoint) - MadeChange |= removeUnreachableBlocks(F); + MadeChange |= removeBlocksNotReachableFromEntry(F, DT); // Return early if no work to do. if (ParsePointNeeded.empty()) Index: lib/Transforms/Scalar/Scalar.cpp =================================================================== --- lib/Transforms/Scalar/Scalar.cpp +++ lib/Transforms/Scalar/Scalar.cpp @@ -76,7 +76,6 @@ initializeSeparateConstOffsetFromGEPPass(Registry); initializeStraightLineStrengthReducePass(Registry); initializeLoadCombinePass(Registry); - initializePlaceBackedgeSafepointsImplPass(Registry); initializePlaceSafepointsPass(Registry); initializeFloat2IntPass(Registry); } Index: lib/Transforms/Utils/Local.cpp =================================================================== --- lib/Transforms/Utils/Local.cpp +++ lib/Transforms/Utils/Local.cpp @@ -21,6 +21,7 @@ #include "llvm/Analysis/LibCallSemantics.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/ValueTracking.h" +#include "llvm/Analysis/LoopInfo.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DIBuilder.h" @@ -1302,6 +1303,35 @@ return true; } +// Unlike removeUnreachableBlocks, this routine only removes blocks which +// aren't reachable from entry according to the dominator tree. It does not +// otherwise modify the CFG and preserves various analysis passes if provided. +bool llvm::removeBlocksNotReachableFromEntry(Function &F, DominatorTree &DT, + LoopInfo *LI) { + bool Modified = false; + if (LI) + for (BasicBlock &BB : F) + if (!DT.isReachableFromEntry(&BB)) + LI->removeBlock(&BB); + + for (BasicBlock &BB : F) + if (!DT.isReachableFromEntry(&BB)) { + Modified = true; + for (BasicBlock *Succ : successors(&BB)) + // avoid loops and invalidating iterators + if (DT.isReachableFromEntry(Succ)) + Succ->removePredecessor(Succ); + BB.dropAllReferences(); + } + + for (Function::iterator I = ++F.begin(); I != F.end();) + if (!DT.isReachableFromEntry(I)) + I = F.getBasicBlockList().erase(I); + else + ++I; + return Modified; +} + void llvm::combineMetadata(Instruction *K, const Instruction *J, ArrayRef KnownIDs) { SmallVector, 4> Metadata; K->dropUnknownMetadata(KnownIDs);