From aae168f9934eaba1898edd987852778aff70cdc4 Mon Sep 17 00:00:00 2001 From: Michael Zolotukhin Date: Tue, 9 Aug 2016 22:44:56 +0000 Subject: [PATCH] [LoopSimplify] Rebuild LCSSA for the inner loop after separating nested loops. Summary: This hopefully fixes PR28825. The problem now was that a value from the original loop was used in a subloop, which became a sibling after separation. While a subloop doesn't need an lcssa phi node, a sibling does, and that's where we broke LCSSA. The most natural way to fix this now is to simply call formLCSSA on the original loop: it'll do what we've been doing before plus it'll cover situations described above. I think we don't need to run formLCSSARecursively here, and we have an assert to verify this (I've tried testing it on LLVM testsuite + SPECs). I'd be happy to be corrected here though. I also changed a run line in the test from '-lcssa -loop-unroll' to '-lcssa -loop-simplify -indvars', because it exercises LCSSA preservation to the same extent, but also makes less unrelated transformation on the CFG, which makes it easier to verify. Reviewers: chandlerc, sanjoy, silvas Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D23288 llvm-svn: 278173 --- llvm/lib/Transforms/Utils/LoopSimplify.cpp | 36 ++++------------------------ llvm/test/Transforms/LoopSimplify/pr28272.ll | 33 ++++++++++++++++++++++++- 2 files changed, 36 insertions(+), 33 deletions(-) diff --git a/llvm/lib/Transforms/Utils/LoopSimplify.cpp b/llvm/lib/Transforms/Utils/LoopSimplify.cpp index d2ccb16..26b59ad 100644 --- a/llvm/lib/Transforms/Utils/LoopSimplify.cpp +++ b/llvm/lib/Transforms/Utils/LoopSimplify.cpp @@ -361,39 +361,11 @@ static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader, // Fix LCSSA form for L. Some values, which previously were only used inside // L, can now be used in NewOuter loop. We need to insert phi-nodes for them // in corresponding exit blocks. + // We don't need to form LCSSA recursively, because there cannot be uses + // inside a newly created loop of defs from inner loops as those would + // already be a use of an LCSSA phi node. + formLCSSA(*L, *DT, LI, SE); - // Go through all instructions in OuterLoopBlocks and check if they are - // using operands from the inner loop. In this case we'll need to fix LCSSA - // for these instructions. - SmallSetVector WorklistSet; - for (BasicBlock *OuterBB: OuterLoopBlocks) { - for (Instruction &I : *OuterBB) { - for (Value *Op : I.operands()) { - Instruction *OpI = dyn_cast(Op); - if (!OpI || !L->contains(OpI)) - continue; - WorklistSet.insert(OpI); - } - } - } - // We also need to check exit blocks of the outer loop - it might be using - // values from what now became an inner loop. - SmallVector ExitBlocks; - NewOuter->getExitBlocks(ExitBlocks); - for (BasicBlock *ExitBB: ExitBlocks) { - for (Instruction &I : *ExitBB) { - for (Value *Op : I.operands()) { - Instruction *OpI = dyn_cast(Op); - if (!OpI || !L->contains(OpI)) - continue; - WorklistSet.insert(OpI); - } - } - } - - SmallVector Worklist(WorklistSet.begin(), - WorklistSet.end()); - formLCSSAForInstructions(Worklist, *DT, *LI); assert(NewOuter->isRecursivelyLCSSAForm(*DT) && "LCSSA is broken after separating nested loops!"); } diff --git a/llvm/test/Transforms/LoopSimplify/pr28272.ll b/llvm/test/Transforms/LoopSimplify/pr28272.ll index e59d763..d4025db 100644 --- a/llvm/test/Transforms/LoopSimplify/pr28272.ll +++ b/llvm/test/Transforms/LoopSimplify/pr28272.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -lcssa -loop-unroll -S | FileCheck %s +; RUN: opt < %s -lcssa -loop-simplify -indvars -S | FileCheck %s target triple = "x86_64-unknown-linux-gnu" ; PR28272, PR28825 @@ -106,3 +106,34 @@ bb_end: %x = getelementptr i32, i32* %b br label %bb_end } + +; When LoopSimplify separates nested loops, it might break LCSSA form: values +; from the original loop might occur in a loop, which is now a sibling of the +; original loop (before separating it was a subloop of the original loop, and +; thus didn't require an lcssa phi nodes). +; CHECK-LABEL: @foo4 +define void @foo4() { +bb1: + br label %bb2 + +; CHECK: bb2.loopexit: +bb2.loopexit: ; preds = %bb3 + %i.ph = phi i32 [ 0, %bb3 ] + br label %bb2 + +; CHECK: bb2.outer: +; CHECK: bb2: +bb2: ; preds = %bb2.loopexit, %bb2, %bb1 + %i = phi i32 [ 0, %bb1 ], [ %i, %bb2 ], [ %i.ph, %bb2.loopexit ] + %x = load i32, i32* undef, align 8 + br i1 undef, label %bb2, label %bb3.preheader + +; CHECK: bb3.preheader: +bb3.preheader: ; preds = %bb2 +; CHECK: %x.lcssa = phi i32 [ %x, %bb2 ] + br label %bb3 + +bb3: ; preds = %bb3.preheader, %bb3 + %y = add i32 2, %x + br i1 true, label %bb2.loopexit, label %bb3 +} -- 2.7.4