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

No need for '\brief'.

332–334

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

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

77–78

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

84–85

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?

include/llvm/Transforms/Utils/LoopUtils.h

private:
   InductionKind IK;
   /// Step value.
   const SCEV *Step;
 };
 
 BasicBlock *InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI,
                                    bool PreserveLCSSA);
 
+/// \brief Ensures LCSSA form for instruction Inst in the scope of loop L.
+///
+/// For the given instruction in the loop 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 preserved.
+/// ExitBlocks is a vector containing exit blocks of the loop L.
+/// PredCache should be a valid PredIteratorCache object.
+///
+/// ExitBlocks and PredCache are used to avoid redundant recomputations for
+/// every call of this routine.
+///
+/// Returns true if any modifications are made.
+bool formLCSSAForInstruction(Loop &L, Instruction &Inst, DominatorTree &DT,
+                             LoopInfo &LI,
+                             const SmallVectorImpl<BasicBlock *> &ExitBlocks,
+                             PredIteratorCache &PredCache);
+
 /// \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.
 ///

lib/Transforms/Utils/LCSSA.cpp

 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) {
+bool llvm::formLCSSAForInstruction(
+    Loop &L, Instruction &Inst, DominatorTree &DT, LoopInfo &LI,
+    PredIteratorCache &PredCache) {
   SmallVector<Use *, 16> UsesToRewrite;
 
   // 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();
 
   for (Use &U : Inst.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))
       UsesToRewrite.push_back(&U);
   }
 
   // If there are no uses outside the loop, exit with no change.
   if (UsesToRewrite.empty())
     return false;
 
   ++NumLCSSA; // We are applying the transformation
 
for (BasicBlock *ExitBB : ExitBlocks) {
     // 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 (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.
bool llvm::formLCSSAForInstruction(
 
   // 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);
+    Loop *OtherLoop = LI.getLoopFor(PHIBB);
     SmallVector<BasicBlock *, 8> EBs;
     OtherLoop->getExitBlocks(EBs);
     if (EBs.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);
+    formLCSSAForInstruction(*OtherLoop, *I, DT, LI, EBs, PredCache);
   }
 
   // Remove PHI nodes that did not have any uses rewritten.
   for (PHINode *PN : AddedPHIs)
     if (PN->use_empty())
       PN->eraseFromParent();
 
   return true;
for (BasicBlock *BB : L.blocks()) {
     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);
+      Changed |= formLCSSAForInstruction(L, I, DT, *LI, ExitBlocks, PredCache);
     }
   }
 
   // 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);