Make processInstruction from LCSSA.cpp externally available.

[mzolotukhin]

Summary

When a pass tries to keep LCSSA form it's often convenient to be able to update
LCSSA for one instruction rather than for the entire loop. This patch makes the
processInstruction from LCSSA externally available under a name
formLCSSAForInstruction. The API is almost unchanged, and I'm open to
suggestions how to make it better. Currently for instance we have a couple of
arguments whose purpose might be not obvious for the routine user.

[chandlerc]

Should the declaration for this go into LCSSA.h instead of into LoopUtils.h?

include/llvm/Transforms/Utils/LoopUtils.h

326 ↗

(On Diff #64029)

No need for '\brief'.

332–334 ↗

(On Diff #64029)

They aren't just preserved. The CFG isn't mutated, and it might be useful to explicitly call that out.

lib/Transforms/Utils/LCSSA.cpp

191–194 ↗

(On Diff #64029)

At least for the one caller of this here, fixing this FIXME would also eliminate the need for the exit blocks and pred cache parameters. Would it eliminate the need for them in the other call sites you have in mind?

[mzolotukhin]

• Replace recursion with a worklist.
• Rebase on ToT.
• Remove no longer needed arguments.
• Remove \brief.

[mzolotukhin]

Hi Chandler,

Thanks for taking a look! I updated the patch: now we need less arguments and don't have that recursion.

Michael

[chandlerc]

I think you need to accept the worklist as an argument, so that the cache (and exit blocks) can be shared across what are in this patch repeated top-level invocations (in addition to the recursive aspect).

Essentially, we should walk the loop push each instruction into a worklist, and then call this routine on that to process it until all the instructions are in LCSSA form.

[mzolotukhin]

• Accept worklist of instructions instead of a single instruction as an argument.
• Some formatting fixes.

[chandlerc]

LGTM with a tweak below. Also see my note about the exit blocks.

lib/Transforms/Utils/LCSSA.cpp

69–70 ↗

(On Diff #64088)

Hoist these outside the loop and clear them on each iteration?

74–75 ↗

(On Diff #64088)

Wow, I really didn't think about how costly this'll end up being...

I think your patch is probably fine as-is because the exit blocks lists are probably pretty small in practice.

But I think in a follow-up patch we should change this to use a better API. The fact that the LoopInfo analysis just populates a small vector is pretty horrible. We should add a nice iterator that just walks the exit blocks and use that so there is no copying or churn here. Then I think the worklist becomes a complete win. It should also mean you can do stuff across multiple loops if useful here without really stressing about it.

Does that make sense to you?

llvm/trunk/include/llvm/Transforms/Utils/LoopUtils.h

private:
   InductionKind IK;
   /// Step value.
   const SCEV *Step;
 };
 
 BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
                                    bool PreserveLCSSA);
 
+/// Ensures LCSSA form for every instruction from the Worklist in the scope of
+/// innermost containing loop.
+///
+/// For the given instruction which have uses outside of the loop, an LCSSA PHI
+/// node is inserted and the uses outside the loop are rewritten to use this
+/// node.
+///
+/// LoopInfo and DominatorTree are required and, since the routine makes no
+/// changes to CFG, preserved.
+///
+/// Returns true if any modifications are made.
+bool formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
+                              DominatorTree &DT, LoopInfo &LI);
+
 /// \brief Put loop into LCSSA form.
 ///
 /// Looks at all instructions in the loop which have uses outside of the
 /// current loop. For each, an LCSSA PHI node is inserted and the uses outside
 /// the loop are rewritten to use this node.
 ///
 /// LoopInfo and DominatorTree are required and preserved.
 ///

llvm/trunk/lib/Transforms/Utils/LCSSA.cpp

 STATISTIC(NumLCSSA, "Number of live out of a loop variables");
 
 /// Return true if the specified block is in the list.
 static bool isExitBlock(BasicBlock *BB,
                         const SmallVectorImpl<BasicBlock *> &ExitBlocks) {
   return find(ExitBlocks, BB) != ExitBlocks.end();
 }
 
-/// Given an instruction in the loop, check to see if it has any uses that are
-/// outside the current loop.  If so, insert LCSSA PHI nodes and rewrite the
-/// uses.
-static bool processInstruction(Loop &L, Instruction &Inst, DominatorTree &DT,
-                               const SmallVectorImpl<BasicBlock *> &ExitBlocks,
-                               PredIteratorCache &PredCache, LoopInfo *LI) {
+/// 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;
+  PredIteratorCache PredCache;
+  bool Changed = false;
+
+  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 (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.
-  if (Inst.getType()->isTokenTy())
-    return false;
-
-  BasicBlock *InstBB = Inst.getParent();
+    if (I->getType()->isTokenTy())
+      continue;
 
-  for (Use &U : Inst.uses()) {
+    for (Use &U : I->uses()) {
       Instruction *User = cast<Instruction>(U.getUser());
       BasicBlock *UserBB = User->getParent();
       if (PHINode *PN = dyn_cast<PHINode>(User))
         UserBB = PN->getIncomingBlock(U);
 
-    if (InstBB != UserBB && !L.contains(UserBB))
+      if (InstBB != UserBB && !L->contains(UserBB))
         UsesToRewrite.push_back(&U);
     }
 
     // If there are no uses outside the loop, exit with no change.
     if (UsesToRewrite.empty())
-    return false;
+      continue;
 
     ++NumLCSSA; // We are applying the transformation
 
-  // Invoke instructions are special in that their result value is not available
-  // along their unwind edge. The code below tests to see whether DomBB
-  // dominates the value, so adjust DomBB to the normal destination block,
-  // which is effectively where the value is first usable.
-  BasicBlock *DomBB = Inst.getParent();
-  if (InvokeInst *Inv = dyn_cast<InvokeInst>(&Inst))
+    // Invoke instructions are special in that their result value is not
+    // available along their unwind edge. The code below tests to see whether
+    // DomBB dominates the value, so adjust DomBB to the normal destination
+    // block, which is effectively where the value is first usable.
+    BasicBlock *DomBB = InstBB;
+    if (InvokeInst *Inv = dyn_cast<InvokeInst>(I))
       DomBB = Inv->getNormalDest();
 
     DomTreeNode *DomNode = DT.getNode(DomBB);
 
     SmallVector<PHINode *, 16> AddedPHIs;
     SmallVector<PHINode *, 8> PostProcessPHIs;
 
     SSAUpdater SSAUpdate;
-  SSAUpdate.Initialize(Inst.getType(), Inst.getName());
+    SSAUpdate.Initialize(I->getType(), I->getName());
 
     // Insert the LCSSA phi's into all of the exit blocks dominated by the
     // value, and add them to the Phi's map.
     for (BasicBlock *ExitBB : ExitBlocks) {
       if (!DT.dominates(DomNode, DT.getNode(ExitBB)))
         continue;
 
       // If we already inserted something for this BB, don't reprocess it.
       if (SSAUpdate.HasValueForBlock(ExitBB))
         continue;
 
-    PHINode *PN = PHINode::Create(Inst.getType(), PredCache.size(ExitBB),
-                                  Inst.getName() + ".lcssa", &ExitBB->front());
+      PHINode *PN = PHINode::Create(I->getType(), PredCache.size(ExitBB),
+                                    I->getName() + ".lcssa", &ExitBB->front());
 
       // Add inputs from inside the loop for this PHI.
       for (BasicBlock *Pred : PredCache.get(ExitBB)) {
-      PN->addIncoming(&Inst, Pred);
+        PN->addIncoming(I, Pred);
 
         // If the exit block has a predecessor not within the loop, arrange for
         // the incoming value use corresponding to that predecessor to be
         // rewritten in terms of a different LCSSA PHI.
-      if (!L.contains(Pred))
+        if (!L->contains(Pred))
           UsesToRewrite.push_back(
               &PN->getOperandUse(PN->getOperandNumForIncomingValue(
                   PN->getNumIncomingValues() - 1)));
       }
 
       AddedPHIs.push_back(PN);
 
       // Remember that this phi makes the value alive in this block.
       SSAUpdate.AddAvailableValue(ExitBB, PN);
 
       // LoopSimplify might fail to simplify some loops (e.g. when indirect
-    // branches are involved). In such situations, it might happen that an exit
-    // for Loop L1 is the header of a disjoint Loop L2. Thus, when we create
-    // PHIs in such an exit block, we are also inserting PHIs into L2's header.
-    // This could break LCSSA form for L2 because these inserted PHIs can also
-    // have uses outside of L2. Remember all PHIs in such situation as to
-    // revisit than later on. FIXME: Remove this if indirectbr support into
-    // LoopSimplify gets improved.
-    if (auto *OtherLoop = LI->getLoopFor(ExitBB))
-      if (!L.contains(OtherLoop))
+      // branches are involved). In such situations, it might happen that an
+      // exit for Loop L1 is the header of a disjoint Loop L2. Thus, when we
+      // create PHIs in such an exit block, we are also inserting PHIs into L2's
+      // header. This could break LCSSA form for L2 because these inserted PHIs
+      // can also have uses outside of L2. Remember all PHIs in such situation
+      // as to revisit than later on. FIXME: Remove this if indirectbr support
+      // into LoopSimplify gets improved.
+      if (auto *OtherLoop = LI.getLoopFor(ExitBB))
+        if (!L->contains(OtherLoop))
           PostProcessPHIs.push_back(PN);
     }
 
     // Rewrite all uses outside the loop in terms of the new PHIs we just
     // inserted.
     for (Use *UseToRewrite : UsesToRewrite) {
       // If this use is in an exit block, rewrite to use the newly inserted PHI.
-    // This is required for correctness because SSAUpdate doesn't handle uses in
-    // the same block.  It assumes the PHI we inserted is at the end of the
+      // This is required for correctness because SSAUpdate doesn't handle uses
+      // in the same block.  It assumes the PHI we inserted is at the end of the
       // block.
       Instruction *User = cast<Instruction>(UseToRewrite->getUser());
       BasicBlock *UserBB = User->getParent();
       if (PHINode *PN = dyn_cast<PHINode>(User))
         UserBB = PN->getIncomingBlock(*UseToRewrite);
 
       if (isa<PHINode>(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) {
         // Tell the VHs that the uses changed. This updates SCEV's caches.
         if (UseToRewrite->get()->hasValueHandle())
           ValueHandleBase::ValueIsRAUWd(*UseToRewrite, &UserBB->front());
         UseToRewrite->set(&UserBB->front());
         continue;
       }
 
       // Otherwise, do full PHI insertion.
       SSAUpdate.RewriteUse(*UseToRewrite);
     }
 
-  // Post process PHI instructions that were inserted into another disjoint loop
-  // and update their exits properly.
-  for (auto *I : PostProcessPHIs) {
-    if (I->use_empty())
-      continue;
-
-    BasicBlock *PHIBB = I->getParent();
-    Loop *OtherLoop = LI->getLoopFor(PHIBB);
-    SmallVector<BasicBlock *, 8> EBs;
-    OtherLoop->getExitBlocks(EBs);
-    if (EBs.empty())
+    // Post process PHI instructions that were inserted into another disjoint
+    // loop and update their exits properly.
+    for (auto *PostProcessPN : PostProcessPHIs) {
+      if (PostProcessPN->use_empty())
         continue;
 
-    // Recurse and re-process each PHI instruction. FIXME: we should really
-    // convert this entire thing to a worklist approach where we process a
-    // vector of instructions...
-    processInstruction(*OtherLoop, *I, DT, EBs, PredCache, LI);
+      // Reprocess each PHI instruction.
+      Worklist.push_back(PostProcessPN);
     }
 
     // Remove PHI nodes that did not have any uses rewritten.
     for (PHINode *PN : AddedPHIs)
       if (PN->use_empty())
         PN->eraseFromParent();
 
-  return true;
+    Changed = true;
+  }
+  return Changed;
 }
 
 /// Return true if the specified block dominates at least
 /// one of the blocks in the specified list.
 static bool
 blockDominatesAnExit(BasicBlock *BB,
                      DominatorTree &DT,
                      const SmallVectorImpl<BasicBlock *> &ExitBlocks) {
bool llvm::formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI,
 
   // Get the set of exiting blocks.
   SmallVector<BasicBlock *, 8> ExitBlocks;
   L.getExitBlocks(ExitBlocks);
 
   if (ExitBlocks.empty())
     return false;
 
-  PredIteratorCache PredCache;
+  SmallVector<Instruction *, 8> Worklist;
 
   // Look at all the instructions in the loop, checking to see if they have uses
-  // outside the loop.  If so, rewrite those uses.
+  // outside the loop.  If so, put them into the worklist to rewrite those uses.
   for (BasicBlock *BB : L.blocks()) {
     // For large loops, avoid use-scanning by using dominance information:  In
     // particular, if a block does not dominate any of the loop exits, then none
     // of the values defined in the block could be used outside the loop.
     if (!blockDominatesAnExit(BB, DT, ExitBlocks))
       continue;
 
     for (Instruction &I : *BB) {
       // Reject two common cases fast: instructions with no uses (like stores)
       // and instructions with one use that is in the same block as this.
       if (I.use_empty() ||
           (I.hasOneUse() && I.user_back()->getParent() == BB &&
            !isa<PHINode>(I.user_back())))
         continue;
 
-      Changed |= processInstruction(L, I, DT, ExitBlocks, PredCache, LI);
+      Worklist.push_back(&I);
     }
   }
+  Changed = formLCSSAForInstructions(Worklist, DT, *LI);
 
   // If we modified the code, remove any caches about the loop from SCEV to
   // avoid dangling entries.
   // FIXME: This is a big hammer, can we clear the cache more selectively?
   if (SE && Changed)
     SE->forgetLoop(&L);
 
   assert(L.isLCSSAForm(DT));