[LCSSA] Handle PHI insertion in disjoint loops

[bruno]

Summary

Take two disjoint Loops L1 and L2.

LoopSimplify skips to simplify some loops (e.g. when indirect branches are involved). In such situations, it can happen that an exit for L1 is the header of L2. Thus, when we create PHIs in one of such exits we are also inserting PHIs in L2 header.

This could break LCSSA form for L2 because these inserted PHIs can also have uses in L2 exits, which are never handled in the current implementation. Provide a fix for this corner case and test that we don't assert/crash on that.

[bruno]

Ping!

[chandlerc]

lib/Transforms/Utils/LCSSA.cpp

97

Rather than a set pointing into AddedPHIs, just keep a list? We don't put PHI nodes into AddedPHIs more than once, so there is no need for set logic, just a separate list for the ones needing post-processing?

136–137

I would say "LoopSimplify might fail to simplify some loops (...)."

139

"PHIs in such an exit block, we are also inserting PHIs into L2's header." reads a bit better to me.

141

"can also have uses outside of L2."? It doesn't matter where the uses are, the key is that we're inserting a loop value in the form of a PHI node in the header.

182–192

Add a comment that we specifically recurse here?

Note that I can probably blow out the stack here with a suitably horrible crafted IR: simply set up a chain of loops such as this that is arbitrarily long. It's pretty contrived, but at least leave a FIXME that we should really convert this entire thing to a worklist approach where we process a vector of instructions...

[bruno]

Thanks for the review Chandler, patch updated with your suggestions.

[bruno]

Ping!

[chandlerc]

One totally nit-picky comment, and one substantial comment. Feel free to commit once addressed.

lib/Transforms/Utils/LCSSA.cpp

144–146

I would write this as:

if (auto OtherLoop = LI->getLoopFor(ExitBB))
  if (!L.contains(OtherLoop))
    PostProcessPHIs.push_back(PN)

177–181

Ow. This is quadratic in all cases AFAICT. Either we move all remaining elements in PostProcessPHIs down a slot, or we skip over an element in every trip throuh AddedPHIs (AddedPHIs is a superset and ordered the same).

Instead of all this, how about we do the post processing first, and then this loop? You can add a similar guard to skip post processing of phis with empty use lists. That avoids all the complexity here.

[bruno]

lib/Transforms/Utils/LCSSA.cpp

144–146

---

Neat!

177–181

---

Yep, I was trying to avoid it by using SmallPtrSet in the first patch, thought you had noticed the tradeoff, should have made that explicit. But this solution looks better anyway. Thanks again. :-)

include/llvm/Transforms/Utils/LoopUtils.h

 /// 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.
 ///
 /// If ScalarEvolution is passed in, it will be preserved.
 ///
 /// Returns true if any modifications are made to the loop.
-bool formLCSSA(Loop &L, DominatorTree &DT, ScalarEvolution *SE = nullptr);
+bool formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI,
+               ScalarEvolution *SE = nullptr);
 
 /// \brief Put a loop nest into LCSSA form.
 ///
 /// This recursively forms LCSSA for a loop nest.
 ///
 /// LoopInfo and DominatorTree are required and preserved.
 ///
 /// If ScalarEvolution is passed in, it will be preserved.
 ///
 /// Returns true if any modifications are made to the loop.
-bool formLCSSARecursively(Loop &L, DominatorTree &DT,
+bool formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
                           ScalarEvolution *SE = nullptr);
 }
 
 #endif

lib/Transforms/Scalar/LICM.cpp

if (!DisablePromotion && (Preheader || L->hasDedicatedExits())) {
 
     // Once we have promoted values across the loop body we have to recursively
     // reform LCSSA as any nested loop may now have values defined within the
     // loop used in the outer loop.
     // FIXME: This is really heavy handed. It would be a bit better to use an
     // SSAUpdater strategy during promotion that was LCSSA aware and reformed
     // it as it went.
     if (Changed)
-      formLCSSARecursively(*L, *DT, getAnalysisIfAvailable<ScalarEvolution>());
+      formLCSSARecursively(*L, *DT, LI,
+                           getAnalysisIfAvailable<ScalarEvolution>());
   }
 
   // Check that neither this loop nor its parent have had LCSSA broken. LICM is
   // specifically moving instructions across the loop boundary and so it is
   // especially in need of sanity checking here.
   assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!");
   assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) &&
          "Parent loop not left in LCSSA form after LICM!");

lib/Transforms/Utils/LCSSA.cpp

static bool isExitBlock(BasicBlock *BB,
   return false;
 }
 
 /// 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) {
+                               PredIteratorCache &PredCache, LoopInfo *LI) {
   SmallVector<Use *, 16> UsesToRewrite;
 
   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))
static bool processInstruction(Loop &L, Instruction &Inst, DominatorTree &DT,
   // effectively where the value is first usable.
   BasicBlock *DomBB = Inst.getParent();
   if (InvokeInst *Inv = dyn_cast<InvokeInst>(&Inst))
     DomBB = Inv->getNormalDest();
 
   DomTreeNode *DomNode = DT.getNode(DomBB);
 
   SmallVector<PHINode *, 16> AddedPHIs;
+  SmallPtrSet<PHINode *, 8> PostProcessPHIs;
 
   SSAUpdater SSAUpdate;
   SSAUpdate.Initialize(Inst.getType(), Inst.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 (SmallVectorImpl<BasicBlock *>::const_iterator BBI = ExitBlocks.begin(),
                                                      BBE = ExitBlocks.end();
for (BasicBlock **PI = PredCache.GetPreds(ExitBB); *PI; ++PI) {
             &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 skip 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 one of such exits we are also inserting PHIs in L2 header. This
+    // could break LCSSA form for L2 because these inserted PHIs can also have
+    // uses in L2 exits. Remember all PHIs in such situation as to revisit than
+    // later on.  FIXME: Remove this if indirectbr support into LoopSimplify
+    // gets improved.
+    Loop *OtherLoop = LI->getLoopFor(ExitBB);
+    if (OtherLoop && !L.contains(OtherLoop))
+      PostProcessPHIs.insert(PN);
   }
 
   // Rewrite all uses outside the loop in terms of the new PHIs we just
   // inserted.
   for (unsigned i = 0, e = UsesToRewrite.size(); i != e; ++i) {
     // 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
for (unsigned i = 0, e = UsesToRewrite.size(); i != e; ++i) {
     }
 
     // Otherwise, do full PHI insertion.
     SSAUpdate.RewriteUse(*UsesToRewrite[i]);
   }
 
   // Remove PHI nodes that did not have any uses rewritten.
   for (unsigned i = 0, e = AddedPHIs.size(); i != e; ++i) {
-    if (AddedPHIs[i]->use_empty())
-      AddedPHIs[i]->eraseFromParent();
+    if (!AddedPHIs[i]->use_empty())
+      continue;
+    if (PostProcessPHIs.count(AddedPHIs[i]) != 0)
+      PostProcessPHIs.erase(AddedPHIs[i]);
   }
 
+  // Post process PHI instructions that were inserted into another disjoint loop
+  // and update their exits properly.
+  for (auto *I : PostProcessPHIs) {
+    BasicBlock *PHIBB = I->getParent();
+    Loop *OtherLoop = LI->getLoopFor(PHIBB);
+    SmallVector<BasicBlock *, 8> EBs;
+    OtherLoop->getExitBlocks(EBs);
+    if (EBs.empty())
+      continue;
+    processInstruction(*OtherLoop, *I, DT, EBs, PredCache, LI);
+  }
+
   return true;
 }
 
 /// 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) {
   DomTreeNode *DomNode = DT.getNode(BB);
   for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
     if (DT.dominates(DomNode, DT.getNode(ExitBlocks[i])))
       return true;
 
   return false;
 }
 
-bool llvm::formLCSSA(Loop &L, DominatorTree &DT, ScalarEvolution *SE) {
+bool llvm::formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI,
+                     ScalarEvolution *SE) {
   bool Changed = false;
 
   // Get the set of exiting blocks.
   SmallVector<BasicBlock *, 8> ExitBlocks;
   L.getExitBlocks(ExitBlocks);
 
   if (ExitBlocks.empty())
     return false;
for (Loop::block_iterator BBI = L.block_begin(), BBE = L.block_end();
     for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
       // 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);
+      Changed |= processInstruction(L, *I, DT, ExitBlocks, PredCache, 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));
 
   return Changed;
 }
 
 /// Process a loop nest depth first.
-bool llvm::formLCSSARecursively(Loop &L, DominatorTree &DT,
+bool llvm::formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
                                 ScalarEvolution *SE) {
   bool Changed = false;
 
   // Recurse depth-first through inner loops.
-  for (Loop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI)
-    Changed |= formLCSSARecursively(**LI, DT, SE);
+  for (Loop::iterator I = L.begin(), E = L.end(); I != E; ++I)
+    Changed |= formLCSSARecursively(**I, DT, LI, SE);
 
-  Changed |= formLCSSA(L, DT, SE);
+  Changed |= formLCSSA(L, DT, LI, SE);
   return Changed;
 }
 
 namespace {
 struct LCSSA : public FunctionPass {
   static char ID; // Pass identification, replacement for typeid
   LCSSA() : FunctionPass(ID) {
     initializeLCSSAPass(*PassRegistry::getPassRegistry());

 bool LCSSA::runOnFunction(Function &F) {
   bool Changed = false;
   LI = &getAnalysis<LoopInfo>();
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   SE = getAnalysisIfAvailable<ScalarEvolution>();
 
   // Simplify each loop nest in the function.
   for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I)
-    Changed |= formLCSSARecursively(**I, *DT, SE);
+    Changed |= formLCSSARecursively(**I, *DT, LI, SE);
 
   return Changed;
 }
 
 static void verifyLoop(Loop &L, DominatorTree &DT) {
   // Recurse depth-first through inner loops.
   for (Loop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI)
     verifyLoop(**LI, DT);

lib/Transforms/Utils/LoopUnroll.cpp

if (OuterL) {
       // LCSSA must be performed on the outermost affected loop. The unrolled
       // loop's last loop latch is guaranteed to be in the outermost loop after
       // deleteLoopFromQueue updates LoopInfo.
       Loop *LatchLoop = LI->getLoopFor(Latches.back());
       if (!OuterL->contains(LatchLoop))
         while (OuterL->getParentLoop() != LatchLoop)
           OuterL = OuterL->getParentLoop();
 
-      formLCSSARecursively(*OuterL, *DT, SE);
+      formLCSSARecursively(*OuterL, *DT, LI, SE);
     }
   }
 
   return true;
 }

test/Transforms/LCSSA/indirectbr.ll

-; RUN: opt < %s -lcssa -verify-loop-info -verify-dom-info -disable-output
-; PR5437
+; RUN: opt < %s -loop-simplify -lcssa -verify-loop-info -verify-dom-info -S | FileCheck %s
 
 ; LCSSA should work correctly in the case of an indirectbr that exits
 ; the loop, and the loop has exits with predecessors not within the loop
 ; (and btw these edges are unsplittable due to the indirectbr).
-
-define i32 @js_Interpret() nounwind {
+; PR5437
+define i32 @test0() nounwind {
+; CHECK-LABEL: @test0
 entry:
   br i1 undef, label %"4", label %"3"
 
 "3":                                              ; preds = %entry
   ret i32 0
 
 "4":                                              ; preds = %entry
   br i1 undef, label %"6", label %"5"
"1861":                                           ; preds = %"23", %"23"
   unreachable
 
 "41":                                             ; preds = %"23", %"23"
   unreachable
 
 "1862":                                           ; preds = %"1836", %"692"
   unreachable
 }
+
+; An exit for Loop L1 may be the header of a disjoint Loop L2.  Thus, when we
+; create PHIs in one of such exits we are also inserting PHIs in L2 header. This
+; could break LCSSA form for L2 because these inserted PHIs can also have uses
+; in L2 exits. Test that we don't assert/crash on that.
+define void @test1() {
+; CHECK-LABEL: @test1
+  br label %lab1
+
+lab1:
+  %tmp21 = add i32 undef, 677038203
+  br i1 undef, label %lab2, label %exit
+
+lab2:
+  indirectbr i8* undef, [label %lab1, label %lab3]
+
+lab3:
+; CHECK: %tmp21.lcssa1 = phi i32 [ %tmp21.lcssa1, %lab4 ], [ %tmp21, %lab2 ]
+  %tmp12 = phi i32 [ %tmp21, %lab2 ], [ %tmp12, %lab4 ]
+  br i1 undef, label %lab5, label %lab4
+
+lab4:
+  br label %lab3
+
+lab5:
+; CHECK:  %tmp21.lcssa1.lcssa = phi i32 [ %tmp21.lcssa1, %lab3 ]
+  %tmp15 = add i32 %tmp12, undef
+  br label %exit
+
+exit:
+  ret void
+}