Index: include/llvm/Transforms/Utils/LoopUtils.h =================================================================== --- include/llvm/Transforms/Utils/LoopUtils.h +++ include/llvm/Transforms/Utils/LoopUtils.h @@ -49,7 +49,8 @@ /// 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. /// @@ -60,7 +61,7 @@ /// 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); } Index: lib/Transforms/Scalar/LICM.cpp =================================================================== --- lib/Transforms/Scalar/LICM.cpp +++ lib/Transforms/Scalar/LICM.cpp @@ -316,7 +316,8 @@ // SSAUpdater strategy during promotion that was LCSSA aware and reformed // it as it went. if (Changed) - formLCSSARecursively(*L, *DT, getAnalysisIfAvailable()); + formLCSSARecursively(*L, *DT, LI, + getAnalysisIfAvailable()); } // Check that neither this loop nor its parent have had LCSSA broken. LICM is Index: lib/Transforms/Utils/LCSSA.cpp =================================================================== --- lib/Transforms/Utils/LCSSA.cpp +++ lib/Transforms/Utils/LCSSA.cpp @@ -61,7 +61,7 @@ /// uses. static bool processInstruction(Loop &L, Instruction &Inst, DominatorTree &DT, const SmallVectorImpl &ExitBlocks, - PredIteratorCache &PredCache) { + PredIteratorCache &PredCache, LoopInfo *LI) { SmallVector UsesToRewrite; BasicBlock *InstBB = Inst.getParent(); @@ -94,6 +94,7 @@ DomTreeNode *DomNode = DT.getNode(DomBB); SmallVector AddedPHIs; + SmallVector PostProcessPHIs; SSAUpdater SSAUpdate; SSAUpdate.Initialize(Inst.getType(), Inst.getName()); @@ -131,6 +132,18 @@ // 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. + Loop *OtherLoop = LI->getLoopFor(ExitBB); + if (OtherLoop && !L.contains(OtherLoop)) + PostProcessPHIs.push_back(PN); } // Rewrite all uses outside the loop in terms of the new PHIs we just @@ -159,8 +172,30 @@ // 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; + for (unsigned j = 0, ee = PostProcessPHIs.size(); j != ee; ++j) + if (PostProcessPHIs[j] == AddedPHIs[i]) { + PostProcessPHIs.erase(PostProcessPHIs.begin()+j); + break; + } + AddedPHIs[i]->eraseFromParent(); + } + + // 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 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); } return true; @@ -180,7 +215,8 @@ 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. @@ -212,7 +248,7 @@ !isa(I->user_back()))) continue; - Changed |= processInstruction(L, *I, DT, ExitBlocks, PredCache); + Changed |= processInstruction(L, *I, DT, ExitBlocks, PredCache, LI); } } @@ -228,15 +264,15 @@ } /// 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; } @@ -291,7 +327,7 @@ // 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; } Index: lib/Transforms/Utils/LoopUnroll.cpp =================================================================== --- lib/Transforms/Utils/LoopUnroll.cpp +++ lib/Transforms/Utils/LoopUnroll.cpp @@ -544,7 +544,7 @@ while (OuterL->getParentLoop() != LatchLoop) OuterL = OuterL->getParentLoop(); - formLCSSARecursively(*OuterL, *DT, SE); + formLCSSARecursively(*OuterL, *DT, LI, SE); } } Index: test/Transforms/LCSSA/indirectbr.ll =================================================================== --- test/Transforms/LCSSA/indirectbr.ll +++ test/Transforms/LCSSA/indirectbr.ll @@ -1,11 +1,11 @@ -; 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" @@ -540,3 +540,35 @@ "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 +}