Don't recompute LCSSA after loop-unrolling when possible.

[mzolotukhin]

Summary

Currently we always recompute LCSSA for outer loops after unrolling an
inner loop. That leads to compile time problem when we have big loop
nests, and we can solve it by avoiding unnecessary work. For instance,
if w eonly do partial unrolling, we don't break LCSSA, so we don't need
to rebuild it. Also, if all exits from the inner loop are inside the
enclosing loop, then complete unrolling won't break LCSSA either.

I replaced unconditional LCSSA recomputation with conditional recomputation +
unconditional assert and added several tests, which were failing when I
experimented with it.

Soon I plan to follow up with a similar patch for recalculation of dominators
tree.

[mehdi_amini]

lib/Transforms/Utils/LoopUnroll.cpp

233 ↗

(On Diff #39782)

LI->getLoopFor(BB) != ParentL; could be written ParentL->contains(BB);

Also, as an alternative to the raw loop:

bool AllExitsAreInsideParentLoop = std::all_of(ExitBlocks.begin(), ExitBlocks.end(), [&] (BasicBlock *BB) { return ParentL->contains(BB); })

567 ↗

(On Diff #39782)

Are we sure that there is no case where partial unrolling can break the LCSSA form for the enclosing loop? I don't think so but not sure why or if it is an implementation guarantee that can be lost?
Also, are we allowed to break LCSSA for the current loop in case of partial unrolling? I.e. if I have a pass manager that contains unrolling + another loop pass, and the second expect LCSSA form for every loop, it seems your patch could change that (unless partial unrolling guarantee LCSSA on the partially unrolled loop as well).

[mzolotukhin]

Hi Mehdi,

Thanks for the remarks, replies below:

Michael

lib/Transforms/Utils/LoopUnroll.cpp

233 ↗

(On Diff #39782)

Good idea, thanks!

567 ↗

(On Diff #39782)

AFAIU, partial unrolling shouldn't break LCSSA. The reason is that we don't change loops structure and don't add/remove exits from loops. Provided LCSSA was valid before partial unrolling, it should remain valid as all LCSSA phis would stay in correct places, and we won't create new in-loop definitions with uses outside the loop and those phis.
Complete loop unrolling, in contrast, changes loop structure and might change exits even for an outer loop - that's why we usually need to rebuild LCSSA after it. However, if all loop exits are inside the parent loop, then full unrolling of the inner loop shouldn't change exits for outer loops, and we won't create definitions inside the loop with uses outside (since outside uses would be in phis, which are located in exits, which are inside the enclosing loop). Thus, in this case there is also no need to rebuild LCSSA.
If my logic is flawed anywhere, I'd appreciate to be corrected!

[mzolotukhin]

• Address review remarks.

[hfinkel]

lib/Transforms/Utils/LoopUnroll.cpp

229 ↗

(On Diff #39865)

Can't ParentL be nullptr here for a top-level loop?

[mzolotukhin]

lib/Transforms/Utils/LoopUnroll.cpp

229 ↗

(On Diff #39865)

It can, and that explains failures I see in testing after this change:) I'll fix this by adding !ParentL || before the std::all_of call.

[mzolotukhin]

• Don't fail if ParentL is nullptr.

[mehdi_amini]

lib/Transforms/Utils/LoopUnroll.cpp

227 ↗

(On Diff #40186)

It seems you didn't update the test, if it was passing before it means this is not tested in the non-regression suite?

[mzolotukhin]

lib/Transforms/Utils/LoopUnroll.cpp

227 ↗

(On Diff #40186)

I didn't wait for test-suite when I made this change as I erroneously considered it NFC. However, with it even compiler-rt failed to build, so we definitely have tests for this case.

[chandlerc]

LGTM as soon as you have a test case for the top-most loop!

lib/Transforms/Utils/LoopUnroll.cpp

227 ↗

(On Diff #40186)

I still think we should have a regression test that exercises this situation.

563–567 ↗

(On Diff #40186)

I agree with your reasoning, and the assert is a good way to stay confident that we don't break this going forward.

test/Transforms/LoopUnroll/rebuild_lcssa.ll

19 ↗

(On Diff #40186)

All of the function attrs comments seem stale (the attrs are gone).

24 ↗

(On Diff #40186)

I'd really prefer to strip all the predecessor comments. It makes it a lot harder to update IMO.

78 ↗

(On Diff #40186)

It'd be good to check the structure here (ie, that its a single-entry phi from the exiting block).

[mzolotukhin]

Thanks! Committed in r253126.

I didn't add a test for outermost loop, since any test with a single loop checks it and we have plenty of such tests already (currently we have 38 loop-unroll tests that'll fail if we remove !ParentL ||). If we you believe we still need a separate test for it, I can commit it as a follow-up.

Michael

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

if (TripCount == 0 && Count < 2)
     return false;
 
   assert(Count > 0);
   assert(TripMultiple > 0);
   assert(TripCount == 0 || TripCount % TripMultiple == 0);
 
   // Are we eliminating the loop control altogether?
   bool CompletelyUnroll = Count == TripCount;
+  SmallVector<BasicBlock *, 4> ExitBlocks;
+  L->getExitBlocks(ExitBlocks);
+  Loop *ParentL = L->getParentLoop();
+  bool AllExitsAreInsideParentLoop = !ParentL ||
+      std::all_of(ExitBlocks.begin(), ExitBlocks.end(),
+                  [&](BasicBlock *BB) { return ParentL->contains(BB); });
 
   // We assume a run-time trip count if the compiler cannot
   // figure out the loop trip count and the unroll-runtime
   // flag is specified.
   bool RuntimeTripCount = (TripCount == 0 && Count > 0 && AllowRuntime);
 
   if (RuntimeTripCount &&
       !UnrollRuntimeLoopProlog(L, Count, AllowExpensiveTripCount, LI, LPM))
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();
 
+      if (CompletelyUnroll && !AllExitsAreInsideParentLoop)
         formLCSSARecursively(*OuterL, *DT, LI, SE);
+      else
+        assert(OuterL->isLCSSAForm(*DT) &&
+               "Loops should be in LCSSA form after loop-unroll.");
     }
   }
 
   return true;
 }
 
 /// Given an llvm.loop loop id metadata node, returns the loop hint metadata
 /// node with the given name (for example, "llvm.loop.unroll.count"). If no

llvm/trunk/test/Transforms/LoopUnroll/rebuild_lcssa.ll

+; RUN: opt < %s -loop-unroll -S | FileCheck %s
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+; This test shows how unrolling an inner loop could break LCSSA for an outer
+; loop, and there is no cheap way to recover it.
+;
+; In this case the inner loop, L3, is being unrolled. It only runs one
+; iteration, so unrolling basically means replacing
+;   br i1 true, label %exit, label %L3_header
+; with
+;   br label %exit
+;
+; However, this change messes up the loops structure: for instance, block
+; L3_body no longer belongs to L2. It becomes an exit block for L2, so LCSSA
+; phis for definitions in L2 should now be placed there. In particular, we need
+; to insert such a definition for %y1.
+
+; CHECK-LABEL: @foo1
+define void @foo1() {
+entry:
+  br label %L1_header
+
+L1_header:
+  br label %L2_header
+
+L2_header:
+  %y1 = phi i64 [ undef, %L1_header ], [ %x.lcssa, %L2_latch ]
+  br label %L3_header
+
+L3_header:
+  %y2 = phi i64 [ 0, %L3_latch ], [ %y1, %L2_header ]
+  %x = add i64 undef, -1
+  br i1 true, label %L2_latch, label %L3_body
+
+L2_latch:
+  %x.lcssa = phi i64 [ %x, %L3_header ]
+  br label %L2_header
+
+; CHECK:      L3_body:
+; CHECK-NEXT:   %y1.lcssa = phi i64 [ %y1, %L3_header ]
+L3_body:
+  store i64 %y1, i64* undef
+  br i1 false, label %L3_latch, label %L1_latch
+
+L3_latch:
+  br i1 true, label %exit, label %L3_header
+
+L1_latch:
+  %y.lcssa = phi i64 [ %y2, %L3_body ]
+  br label %L1_header
+
+exit:
+  ret void
+}
+
+; Additional tests for some corner cases.
+;
+; CHECK-LABEL: @foo2
+define void @foo2() {
+entry:
+  br label %L1_header
+
+L1_header:
+  br label %L2_header
+
+L2_header:
+  %a = phi i64 [ undef, %L1_header ], [ %dec_us, %L3_header ]
+  br label %L3_header
+
+L3_header:
+  %b = phi i64 [ 0, %L3_latch ], [ %a, %L2_header ]
+  %dec_us = add i64 undef, -1
+  br i1 true, label %L2_header, label %L3_break_to_L1
+
+; CHECK:      L3_break_to_L1:
+; CHECK-NEXT:   %a.lcssa = phi i64 [ %a, %L3_header ]
+L3_break_to_L1:
+  br i1 false, label %L3_latch, label %L1_latch
+
+L1_latch:
+  %b_lcssa = phi i64 [ %b, %L3_break_to_L1 ]
+  br label %L1_header
+
+L3_latch:
+  br i1 true, label %Exit, label %L3_header
+
+Exit:
+  ret void
+}
+
+; CHECK-LABEL: @foo3
+define void @foo3() {
+entry:
+  br label %L1_header
+
+L1_header:
+  %a = phi i8* [ %b, %L1_latch ], [ null, %entry ]
+  br i1 undef, label %L2_header, label %L1_latch
+
+L2_header:
+  br i1 undef, label %L2_latch, label %L1_latch
+
+; CHECK:      L2_latch:
+; CHECK-NEXT:   %a.lcssa = phi i8* [ %a, %L2_header ]
+L2_latch:
+  br i1 true, label %L2_exit, label %L2_header
+
+L1_latch:
+  %b = phi i8* [ undef, %L1_header ], [ null, %L2_header ]
+  br label %L1_header
+
+L2_exit:
+  %a_lcssa1 = phi i8* [ %a, %L2_latch ]
+  br label %Exit
+
+Exit:
+  %a_lcssa2 = phi i8* [ %a_lcssa1, %L2_exit ]
+  ret void
+}