[PlaceSafepoints] Use the analysis infrastructure rather than an inner pass manager

[reames]

Summary

I would really appreciate careful review on the analysis update logic in the newly added function.

PlaceSafepoints was previously using an inner pass manager to run an analysis pass *after* modifying the IR to remove unreachable blocks. In an effort to get rid of the inner pass manager (and the various dominator tree recalcs it implied), I switched to using the analysis infrastructure to actually get the various analysis needed and convert the inner pass manager stuff into a small non-pass helper class.

However, I couldn't figure out how to keep the analysis results up to date over a call to removeUnreachableBlocks. That routine freely modifies the CFG in non-trivial ways with no provisions for updating any of dominator tree, or loop info. Instead, I introduced a new helper function which *only* removes blocks which aren't reachable from the function entry according to the dominator tree. This version supports analysis updating for DT, LI, and (implicitly) SE.

After making the change for PlaceSafepoints, I noticed that RewriteSafepointsForGC had a related invalidation bug. If there was an unreachable statepoint, the analysis results were out of sync with the function being processed after unreachable code was removed.

I suspect - but have not investigated in great depth - that other callers of removeUnreachableBlocks might have similar invalidation bugs. In particular, I'm extremely suspicious of CodeGen/WinEHPrepare.

[igor-laevsky]

include/llvm/Transforms/Utils/Local.h

285–290

Can you please add an example on when differences between "removeBlocksNotReachableFromEntry" and "removeUnreachableBlocks" do matter?

[pgavlin]

include/llvm/Transforms/Utils/Local.h

285–290

+1 to this. The code looks good to me, but it would be nice to have some examples--ideally in the form of tests--of the properties of removeBlocksNotReachableFromEntry.

[reames]

The work that was blocking has been resolved differently and I don't have time to work through all the analysis invalidation issues.

Note to reader: Much of the context of this review didn't make it into phabricator. The blocking comments were by Danny B w.r.t. fixing the existing code to preserve analysis results.

include/llvm/Transforms/Utils/Local.h

 class AssumptionCache;
 class ConstantExpr;
 class DataLayout;
 class TargetLibraryInfo;
 class TargetTransformInfo;
 class DIBuilder;
 class AliasAnalysis;
 class DominatorTree;
+class LoopInfo;
 
 template<typename T> class SmallVectorImpl;
 
 //===----------------------------------------------------------------------===//
 //  Local constant propagation.
 //
 
 /// ConstantFoldTerminator - If a terminator instruction is predicated on a

 bool replaceDbgDeclareForAlloca(AllocaInst *AI, Value *NewAllocaAddress,
                                 DIBuilder &Builder, bool Deref);
 
 /// \brief Remove all blocks that can not be reached from the function's entry.
 ///
 /// 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
 void combineMetadata(Instruction *K, const Instruction *J, ArrayRef<unsigned> KnownIDs);
 
 } // End llvm namespace
 
 #endif

lib/Transforms/Scalar/PlaceSafepoints.cpp

 static cl::opt<bool> SplitBackedge("spp-split-backedge", cl::Hidden,
                                    cl::init(false));
 
 // Print tracing output
 static cl::opt<bool> TraceLSP("spp-trace", cl::Hidden, cl::init(false));
 
 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<TerminatorInst *> PollLocations;
 
   /// True unless we're running spp-no-calls in which case we need to disable
   /// 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) {
     // Visit all the subloops
     for (auto I = L->begin(), E = L->end(); I != E; I++)
       runOnLoopAndSubLoops(*I);
     runOnLoop(L);
   }
 
-  bool runOnFunction(Function &F) override {
-    SE = &getAnalysis<ScalarEvolution>();
-    DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-    LI = &getAnalysis<LoopInfoWrapperPass>().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<DominatorTreeWrapperPass>();
-    AU.addRequired<ScalarEvolution>();
-    AU.addRequired<LoopInfoWrapperPass>();
-    // We no longer modify the IR at all in this pass.  Thus all
-    // analysis are preserved.
-    AU.setPreservesAll();
-  }
 };
 }
 
 static cl::opt<bool> NoEntry("spp-no-entry", cl::Hidden, cl::init(false));
 static cl::opt<bool> NoCall("spp-no-call", cl::Hidden, cl::init(false));
 static cl::opt<bool> NoBackedge("spp-no-backedge", cl::Hidden, cl::init(false));
 
 namespace {
 struct PlaceSafepoints : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
 
   PlaceSafepoints() : FunctionPass(ID) {
     initializePlaceSafepointsPass(*PassRegistry::getPassRegistry());
   }
   bool runOnFunction(Function &F) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<DominatorTreeWrapperPass>();
+    AU.addRequired<ScalarEvolution>();
+    AU.addRequired<LoopInfoWrapperPass>();
+
     // 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
   }
 };
 }
 
 // Insert a safepoint poll immediately before the given instruction.  Does
static void scanInlinedCode(Instruction *start, Instruction *end,
   scanOneBB(start, end, calls, seen, worklist);
   while (!worklist.empty()) {
     BasicBlock *BB = worklist.back();
     worklist.pop_back();
     scanOneBB(&*BB->begin(), end, calls, seen, worklist);
   }
 }
 
-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
   // having run sometime earlier in the pipeline, but this code must be correct
   // w.r.t. loops with multiple backedges.
   BasicBlock *header = L->getHeader();
   SmallVector<BasicBlock*, 16> LoopLatches;
   L->getLoopLatches(LoopLatches);
if (isGCSafepointPoll(F)) {
     return false;
   }
 
   if (!shouldRewriteFunction(F))
     return false;
 
   bool modified = false;
 
+  ScalarEvolution *SE = &getAnalysis<ScalarEvolution>();
+  DominatorTree &DT = *&getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().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<Instruction *, 16> PollsNeeded;
   std::vector<CallSite> 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);
+    FindBackedgeSafepointsHelper PBS(enableCallSafepoints(F), &DT, LI, SE);
+    PBS.runOnFunction(F);
     
-    auto &PollLocations = PBS->PollLocations;
+    auto &PollLocations = PBS.PollLocations;
 
     auto OrderByBBName = [](Instruction *a, Instruction *b) {
       return a->getParent()->getName() < b->getParent()->getName();
     };
     // We need the order of list to be stable so that naming ends up stable
     // when we split edges.  This makes test cases much easier to write.
     std::sort(PollLocations.begin(), PollLocations.end(), OrderByBBName);
 
for (size_t i = 0; i < ParsePointNeeded.size(); i++) {
 
     // Now that we've handled all uses, remove the original call itself
     // Note: The insert point can't be the deleted instruction!
     CS.getInstruction()->eraseFromParent();
   }
   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)
 
 static bool isGCLeafFunction(const CallSite &CS) {
   Instruction *inst = CS.getInstruction();
   if (isa<IntrinsicInst>(inst)) {
     // Most LLVM intrinsics are things which can never take a safepoint.
     // As a result, we don't need to have the stack parsable at the

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

bool RewriteStatepointsForGC::runOnFunction(Function &F) {
 
   bool MadeChange = false;
 
   // Delete any unreachable statepoints so that we don't have unrewritten
   // statepoints surviving this pass.  This makes testing easier and the
   // 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())
     return MadeChange;
 
   // As a prepass, go ahead and aggressively destroy single entry phi nodes.
   // These are created by LCSSA.  They have the effect of increasing the size
   // of liveness sets for no good reason.  It may be harder to do this post

lib/Transforms/Scalar/Scalar.cpp

void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeSROA_SSAUpPass(Registry);
   initializeCFGSimplifyPassPass(Registry);
   initializeStructurizeCFGPass(Registry);
   initializeSinkingPass(Registry);
   initializeTailCallElimPass(Registry);
   initializeSeparateConstOffsetFromGEPPass(Registry);
   initializeStraightLineStrengthReducePass(Registry);
   initializeLoadCombinePass(Registry);
-  initializePlaceBackedgeSafepointsImplPass(Registry);
   initializePlaceSafepointsPass(Registry);
   initializeFloat2IntPass(Registry);
 }
 
 void LLVMInitializeScalarOpts(LLVMPassRegistryRef R) {
   initializeScalarOpts(*unwrap(R));
 }
 

lib/Transforms/Utils/Local.cpp

 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #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"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
for (Function::iterator I = ++F.begin(); I != F.end();)
     if (!Reachable.count(I))
       I = F.getBasicBlockList().erase(I);
     else
       ++I;
 
   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<unsigned> KnownIDs) {
   SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
   K->dropUnknownMetadata(KnownIDs);
   K->getAllMetadataOtherThanDebugLoc(Metadata);
   for (unsigned i = 0, n = Metadata.size(); i < n; ++i) {
     unsigned Kind = Metadata[i].first;
     MDNode *JMD = J->getMetadata(Kind);
     MDNode *KMD = Metadata[i].second;