[LoopSimplify] Rebuild LCSSA for the inner loop after separating nested loops.

[mzolotukhin]

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.

[chandlerc]

The only way I can see this needing the recursive side of LCSSA is the following.

Imagine you had L1 nested inside L2 nested inside L3 nested inside L4. And this takes the L1 nested loop and makes it a sibling of L3. Now you have L2 nested inside L3 nested inside L4, and L1 nested inside L4. But my reading a code indicates we don't ever do this transform. But if you see a way we could do something similar, and end up with L in the code pointing at L3 for example, we might miss that L2 suddenly needs an LCSSA phi node in addition to L3 needing one.

test/Transforms/LoopSimplify/pr28272.ll

114 ↗

(On Diff #67269)

It would be really nice to add CHECKs to ensure the particular loop nest structure (after LoopSimplify) is in fact formed... Is that reasonable to do?

[silvas]

FTR, I'm pretty clueless about all this loop stuff, so don't wait on me! But do let me know if there's any testing you'd like me to do.

[mzolotukhin]

Imagine you had l1 nested inside L2 nested inside L3 nested inside L4. And this takes the l1 nested loop and makes it a sibling of L3. Now you have L2 nested inside L3 nested inside L4, and l1 nested inside L4. But my reading a code indicates we don't ever do this transform. But if you see a way we could do something similar, and end up with L in the code pointing at L3 for example, we might miss that L2 suddenly needs an LCSSA phi node in addition to L3 needing one.

In your example the ordering of the loops has changed - from my understanding of the code we don't do this (it'll be more like loop interchange, right?).

My understanding was that recursive invocation is needed to form LCSSA inside enclosing loop (e.g. if one subloop uses values from another), but since we're not changing internals of the loop, it should be preserved. A simple non-recursive run of formLCSSA on the new loop should fix LCSSA for values used outside it, including values defined in inner loops since their blocks are also blocks of the new loop, and that's the only (as far as I see now) place where LCSSA can be broken. Does this logic sound correct?

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

if (any_of(predecessors(ExitBlock),
       rewriteLoopExitBlock(L, ExitBlock, DT, LI, PreserveLCSSA);
     }
   }
 
   if (PreserveLCSSA) {
     // 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<Instruction *, 8> WorklistSet;
-    for (BasicBlock *OuterBB: OuterLoopBlocks) {
-      for (Instruction &I : *OuterBB) {
-        for (Value *Op : I.operands()) {
-          Instruction *OpI = dyn_cast<Instruction>(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<BasicBlock*, 8> ExitBlocks;
-    NewOuter->getExitBlocks(ExitBlocks);
-    for (BasicBlock *ExitBB: ExitBlocks) {
-      for (Instruction &I : *ExitBB) {
-        for (Value *Op : I.operands()) {
-          Instruction *OpI = dyn_cast<Instruction>(Op);
-          if (!OpI || !L->contains(OpI))
-            continue;
-          WorklistSet.insert(OpI);
-        }
-      }
-    }
-
-    SmallVector<Instruction *, 8> Worklist(WorklistSet.begin(),
-                                           WorklistSet.end());
-    formLCSSAForInstructions(Worklist, *DT, *LI);
     assert(NewOuter->isRecursivelyLCSSAForm(*DT) &&
            "LCSSA is broken after separating nested loops!");
   }
 
   return NewOuter;
 }
 
 /// \brief This method is called when the specified loop has more than one

llvm/trunk/test/Transforms/LoopSimplify/pr28272.ll

-; 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
 ; When LoopSimplify separates nested loops, it might break LCSSA form: values
 ; from the original loop might be used in the outer loop. This test invokes
 ; loop-unroll, which calls loop-simplify before itself. If LCSSA is broken
 ; after loop-simplify, we crash on assertion.
 

 
 bb6:
   br i1 undef, label %bb_end, label %bb1
 
 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
+}