[PlaceSafepoints] Remove dependence on LoopSimplify

[reames]

Summary

As a step towards getting rid of internal pass manager hack entirely, remove the need for loop simplify to run in the inner pass manager. The new code does produce slightly different loop structures, so this isn't technically NFC.

[sanjoy]

lib/Transforms/Scalar/PlaceSafepoints.cpp

571 ↗

(On Diff #25259)

std::unique only removes consecutive elements so I don't think it would work with an unsorted array. I think it is sufficient to just move this after the std::sort on PollLocations below.

575 ↗

(On Diff #25259)

LLVM naming conventions say:

auto OrderByBBName = [](Instruction *A, Instruction *A) {

576 ↗

(On Diff #25259)

StringRef has an operator<.

604 ↗

(On Diff #25259)

Side comment, unrelated to this change: this nested loop uses i, the same induction variable as the outer loop which can be confusing. It might be clearer to change both these loops to be range for loops.

616 ↗

(On Diff #25259)

Side comment that has nothing to do with this change: SplitEdge optionally takes a DominatorTree as input -- if the reason for doing that is that SplitEdge updates the dom tree, then we can just pass in the DT to SplitEdge not recalculate it below.

llvm/trunk/lib/Transforms/Scalar/PlaceSafepoints.cpp

 // be hard.  They are not required for correctness - entry safepoints are an
 // alternative - but some GCs may prefer them.  Patches welcome.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Pass.h"
 #include "llvm/IR/LegacyPassManager.h"
 #include "llvm/ADT/SetOperations.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/IR/BasicBlock.h"
struct PlaceBackedgeSafepointsImpl : public LoopPass {
   PlaceBackedgeSafepointsImpl(bool CallSafepoints = false)
       : LoopPass(ID), CallSafepointsEnabled(CallSafepoints) {
     initializePlaceBackedgeSafepointsImplPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnLoop(Loop *, LPPassManager &LPM) override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
-    // needed for determining if the loop is finite
     AU.addRequired<ScalarEvolution>();
-    // to ensure each edge has a single backedge
-    // TODO: is this still required?
-    AU.addRequiredID(LoopSimplifyID);
-
     // 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));
while (!worklist.empty()) {
     worklist.pop_back();
     scanOneBB(&*BB->begin(), end, calls, seen, worklist);
   }
 }
 
 bool PlaceBackedgeSafepointsImpl::runOnLoop(Loop *L, LPPassManager &LPM) {
   ScalarEvolution *SE = &getAnalysis<ScalarEvolution>();
 
-  // Loop through all predecessors of the loop header and identify all
-  // backedges.  We need to place a safepoint on every backedge (potentially).
-  // Note: Due to LoopSimplify there should only be one.  Assert?  Or can we
-  // relax this?
+  // 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();
 
   // TODO: Use the analysis pass infrastructure for this.  There is no reason
   // to recalculate this here.
   DominatorTree DT;
   DT.recalculate(*header->getParent());
 
-  bool modified = false;
-  for (BasicBlock *pred : predecessors(header)) {
-    if (!L->contains(pred)) {
-      // This is not a backedge, it's coming from outside the loop
-      continue;
-    }
+  SmallVector<BasicBlock*, 16> LoopLatches;
+  L->getLoopLatches(LoopLatches);
+  for (BasicBlock *pred : LoopLatches) {
+    assert(L->contains(pred));
 
     // Make a policy decision about whether this loop needs a safepoint or
     // not.  Note that this is about unburdening the optimizer in loops, not
     // avoiding the runtime cost of the actual safepoint.
     if (!AllBackedges) {
       if (mustBeFiniteCountedLoop(L, SE, pred)) {
         if (TraceLSP)
           errs() << "skipping safepoint placement in finite loop\n";
if (!AllBackedges) {
       }
     }
 
     // TODO: We can create an inner loop which runs a finite number of
     // iterations with an outer loop which contains a safepoint.  This would
     // not help runtime performance that much, but it might help our ability to
     // optimize the inner loop.
 
-    // We're unconditionally going to modify this loop.
-    modified = true;
-
     // Safepoint insertion would involve creating a new basic block (as the
     // target of the current backedge) which does the safepoint (of all live
     // variables) and branches to the true header
     TerminatorInst *term = pred->getTerminator();
 
     if (TraceLSP) {
       errs() << "[LSP] terminator instruction: ";
       term->dump();
     }
 
     PollLocations.push_back(term);
   }
 
-  return modified;
+  return false;
 }
 
 static Instruction *findLocationForEntrySafepoint(Function &F,
                                                   DominatorTree &DT) {
 
   // Conceptually, this poll needs to be on method entry, but in
   // practice, we place it as late in the entry block as possible.  We
   // can place it as late as we want as long as it dominates all calls
if (enableBackedgeSafepoints(F)) {
     // 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);
-    // Note: While the analysis pass itself won't modify the IR, LoopSimplify
-    // (which it depends on) may.  i.e. analysis must be recalculated after run
     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;
+
+    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);
+
+    // We can sometimes end up with duplicate poll locations.  This happens if
+    // a single loop is visited more than once.   The fact this happens seems
+    // wrong, but it does happen for the split-backedge.ll test case.
+    PollLocations.erase(std::unique(PollLocations.begin(),
+                                    PollLocations.end()),
+                        PollLocations.end());
+
     // Insert a poll at each point the analysis pass identified
-    for (size_t i = 0; i < PBS->PollLocations.size(); i++) {
+    for (size_t i = 0; i < PollLocations.size(); i++) {
       // We are inserting a poll, the function is modified
       modified = true;
 
       // The poll location must be the terminator of a loop latch block.
-      TerminatorInst *Term = PBS->PollLocations[i];
+      TerminatorInst *Term = PollLocations[i];
 
       std::vector<CallSite> ParsePoints;
       if (SplitBackedge) {
         // Split the backedge of the loop and insert the poll within that new
         // basic block.  This creates a loop with two latches per original
         // latch (which is non-ideal), but this appears to be easier to
         // optimize in practice than inserting the poll immediately before the
         // latch test.
 
         // Since this is a latch, at least one of the successors must dominate
         // it. Its possible that we have a) duplicate edges to the same header
         // and b) edges to distinct loop headers.  We need to insert pools on
-        // each. (Note: This still relies on LoopSimplify.)
-        DenseSet<BasicBlock *> Headers;
+        // each.
+        SetVector<BasicBlock *> Headers;
         for (unsigned i = 0; i < Term->getNumSuccessors(); i++) {
           BasicBlock *Succ = Term->getSuccessor(i);
           if (DT.dominates(Succ, Term->getParent())) {
             Headers.insert(Succ);
           }
         }
         assert(!Headers.empty() && "poll location is not a loop latch?");
 
         // The split loop structure here is so that we only need to recalculate
         // the dominator tree once.  Alternatively, we could just keep it up to
         // date and use a more natural merged loop.
-        DenseSet<BasicBlock *> SplitBackedges;
+        SetVector<BasicBlock *> SplitBackedges;
         for (BasicBlock *Header : Headers) {
           BasicBlock *NewBB = SplitEdge(Term->getParent(), Header, nullptr);
           SplitBackedges.insert(NewBB);
         }
         DT.recalculate(F);
         for (BasicBlock *NewBB : SplitBackedges) {
-          InsertSafepointPoll(DT, NewBB->getTerminator(), ParsePoints);
+          std::vector<CallSite> RuntimeCalls;
+          InsertSafepointPoll(DT, NewBB->getTerminator(), RuntimeCalls);
           NumBackedgeSafepoints++;
+          ParsePointNeeded.insert(ParsePointNeeded.end(), RuntimeCalls.begin(),
+                                  RuntimeCalls.end());
         }
 
       } else {
         // Split the latch block itself, right before the terminator.
-        InsertSafepointPoll(DT, Term, ParsePoints);
+        std::vector<CallSite> RuntimeCalls;
+        InsertSafepointPoll(DT, Term, RuntimeCalls);
         NumBackedgeSafepoints++;
+        ParsePointNeeded.insert(ParsePointNeeded.end(), RuntimeCalls.begin(),
+                                RuntimeCalls.end());
       }
 
       // Record the parse points for later use
       ParsePointNeeded.insert(ParsePointNeeded.end(), ParsePoints.begin(),
                               ParsePoints.end());
     }
   }
 

 char PlaceSafepoints::ID = 0;
 
 ModulePass *llvm::createPlaceSafepointsPass() { return new PlaceSafepoints(); }
 
 INITIALIZE_PASS_BEGIN(PlaceBackedgeSafepointsImpl,
                       "place-backedge-safepoints-impl",
                       "Place Backedge Safepoints", false, false)
 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
-INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
 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)

llvm/trunk/test/Transforms/PlaceSafepoints/split-backedge.ll

 }
 
 ; Test for the case where a single conditional branch jumps to two
 ; different loop header blocks.  Since we're currently using LoopSimplfy
 ; this doesn't hit the interesting case, but once we remove that, we need
 ; to be sure this keeps working.
 define void @test2(i32, i1 %cond) gc "statepoint-example" {
 ; CHECK-LABEL: @test2
-; CHECK-LABE: loop.loopexit.split
-; CHECK: gc.statepoint
-; CHECK-NEXT: br label %loop
-; CHECK-LABEL: loop2.loop2_crit_edge
+; CHECK-LABEL: loop2.loop2_crit_edge:
 ; CHECK: gc.statepoint
 ; CHECK-NEXT: br label %loop2
+; CHECK-LABEL: loop2.loop_crit_edge:
+; CHECK: gc.statepoint
+; CHECK-NEXT: br label %loop
 entry:
   br label %loop
 
 loop:
   br label %loop2
 
 loop2:
   br i1 %cond, label %loop, label %loop2
 }
 
 declare void @do_safepoint()
 define void @gc.safepoint_poll() {
 entry:
   call void @do_safepoint()
   ret void
 }