[LCSSA] Cache LoopExits to avoid wasted work

[reames]

Summary

When looking at the scribus_1.3 example from https://llvm.org/bugs/show_bug.cgi?id=10584, I noticed that we were spending a large amount of time computing loop exits in LCSSA. This code appears to be written with the assumption that LoopExits are stored in the Loop and thus cheap to query. This is not true, so we should cache the result across the potentially long running loop which tends to visit a small handful of Loops.

On the particular example from 10584, this change drops the time spent in LCSSA computation by about 80%.

[reames]

ping

[chandlerc]

LGTM, Feel free to submit with the tweak below.

lib/Transforms/Utils/LCSSA.cpp

70–73

Nice!

What about using a SmallDenseMap and TinyPtrVector here with a small size of 4 or so? Seems likely to make the common case a bit lighter weight.

[reames]

lib/Transforms/Utils/LCSSA.cpp

70–73

FYI: I ended up using a SmallDenseMap<Loop*, SmallVector<BasicBlock *,1>>. Trying to use the TinyPtrVector didn't work out well because the getExitBlocks function takes a SmallVectorImpl.

Honestly, it also seems like TinyPtrVector should be an implementation detail of SmallVector<T, 1>.

lib/Transforms/Utils/LCSSA.cpp

 }
 
 /// For every instruction from the worklist, check to see if it has any uses
 /// that are outside the current loop.  If so, insert LCSSA PHI nodes and
 /// rewrite the uses.
 bool llvm::formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
                                     DominatorTree &DT, LoopInfo &LI) {
   SmallVector<Use *, 16> UsesToRewrite;
-  SmallVector<BasicBlock *, 8> ExitBlocks;
   SmallSetVector<PHINode *, 16> PHIsToRemove;
   PredIteratorCache PredCache;
   bool Changed = false;
 
+  // Cache the Loop ExitBlocks across this loop.  We expect to get a lot of
+  // instructions within the same loops, computing the exit blocks is
+  // expensive, and we're not mutating the loop structure.
+  DenseMap<Loop*, SmallVector<BasicBlock *, 8>> LoopExitBlocks;
+
   while (!Worklist.empty()) {
     UsesToRewrite.clear();
-    ExitBlocks.clear();
 
     Instruction *I = Worklist.pop_back_val();
     BasicBlock *InstBB = I->getParent();
     Loop *L = LI.getLoopFor(InstBB);
-    L->getExitBlocks(ExitBlocks);
+    if (!LoopExitBlocks.count(L))   
+      L->getExitBlocks(LoopExitBlocks[L]);
+    assert(LoopExitBlocks.count(L));
+    const SmallVector<BasicBlock *, 8> &ExitBlocks = LoopExitBlocks[L];
 
     if (ExitBlocks.empty())
       continue;
 
     // Tokens cannot be used in PHI nodes, so we skip over them.
     // We can run into tokens which are live out of a loop with catchswitch
     // instructions in Windows EH if the catchswitch has one catchpad which
     // is inside the loop and another which is not.