[LoopDeletion] Handle inner loops w/untaken backedges

[reames]

Summary

This builds on the restricted after initial revert form of D93906, and adds back support for breaking backedges of inner loops. It turns out the original invalidation logic wasn't quite right, specifically around the handling of LCSSA.

When breaking the backedge of an inner loop, we can cause blocks which were in the outer loop only because they were also included in a sub-loop to be removed from both loops. This results in the exit block set for our original parent loop changing, and thus a need for new LCSSA phi nodes.

This case happens when the inner loop has an exit block which is also an exit block of the parent, and there's a block in the child which reaches an exit to said block without also reaching an exit to the parent loop.

(I'm describing this in terms of the immediate parent, but the problem is general for any transitive parent in the nest.)

At a high level, we seem to have two choices. Either a) rebuild lcssa if needed, or b) restrict the transformation such that an lcssa rebuild isn't needed.

The lcssa rebuild approach is potentially expensive in the worst case. Each rebuild is potentially O(N^2) in the number of instructions in the loop being rebuilt. At worst, we could have N sub-loops (since each must contain at least one instruction), resulting in a worst case example of a whole forest of loops w/zero btc resulting in O(N^3). We have lots of precedent for this being an acceptable expense, but I want to explicit raise the issue for review. Thoughts?

[reames]

ping

[jdoerfert]

The logic seems sound. I have no idea about the practical impact. Should we do some compile time testing (@fhahn @nikic) ?

[fhahn]

Here's the compile-time numbers for the patch: http://llvm-compile-time-tracker.com/compare.php?from=e377c8eeb4aa2eb239a651f1fe12c27fc77deda3&to=8a40070dec65fe8b716cbfbf134f405fc3d26f8a&stat=instructions

The only notable thing is mafft 52035M 52077M (+0.08%),. Perhaps some noise as there are no binary changes and IIUC it should only trigger if the transformation fires. Or perhaps a different optimzation later on gives the same result.

[fhahn]

llvm/lib/Transforms/Utils/LoopUtils.cpp

805

From the arguments, it seems like changeToUnreachable at least tries to preserve LCSSA, but clearly misses the case at hand. I've not looked at the details on what exactly needs updating Do you think it would be possible to directly fix the values broken after removing the block?

[reames]

llvm/lib/Transforms/Utils/LoopUtils.cpp

805

We're introducing a whole new set of exit blocks which used to be inside the loop. We either have to scan all defs in the loop (which this does), or all uses in the blocks removed from the loop. Is the later any better than the former? The former has the benefit that we can reuse existing code. (Remember we have to do this for all loop levels, so it's slightly tricky.)

[fhahn]

LGTM, thanks!

llvm/lib/Transforms/Utils/LoopUtils.cpp

805

Is the later any better than the former?

I have no idea. Let's use the existing infrastructure and take another look if there are any issues reported.

[uabelho]

Hi,

I wrote
https://bugs.llvm.org/show_bug.cgi?id=49802
about a problem that started happening with this commit.

Since there are already two somewhat similar PRs perhaps this patch just exposes an already existing problem but I thought I'd give a heads-up here about it anyway.

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

breakBackedgeIfNotTaken(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
 
   if (!L->getLoopLatch())
     return LoopDeletionResult::Unmodified;
 
   auto *BTC = SE.getBackedgeTakenCount(L);
   if (!BTC->isZero())
     return LoopDeletionResult::Unmodified;
 
-  // For non-outermost loops, the tricky case is that we can drop blocks
-  // out of both inner and outer loops at the same time.  This results in
-  // new exiting block for the outer loop appearing, and possibly needing
-  // an lcssa phi inserted.  (See loop_nest_lcssa test case in zero-btc.ll)
-  // TODO: We can handle a bunch of cases here without much work, revisit.
-  if (!L->isOutermost())
-    return LoopDeletionResult::Unmodified;
-
   breakLoopBackedge(L, DT, SE, LI, MSSA);
   return LoopDeletionResult::Deleted;
 }
 
 /// Remove a loop if it is dead.
 ///
 /// A loop is considered dead either if it does not impact the observable
 /// behavior of the program other than finite running time, or if it is

llvm/lib/Transforms/Utils/LoopUtils.cpp

if (Loop *ParentLoop = L->getParentLoop()) {
       Loop::iterator I = find(*LI, L);
       assert(I != LI->end() && "Couldn't find loop");
       LI->removeLoop(I);
     }
     LI->destroy(L);
   }
 }
 
+static Loop *getOutermostLoop(Loop *L) {
+  while (Loop *Parent = L->getParentLoop())
+    L = Parent;
+  return L;
+}
+
 void llvm::breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
                              LoopInfo &LI, MemorySSA *MSSA) {
-
-  assert(L->isOutermost() && "Can't yet preserve LCSSA for this case");
   auto *Latch = L->getLoopLatch();
   assert(Latch && "multiple latches not yet supported");
   auto *Header = L->getHeader();
+  Loop *OutermostLoop = getOutermostLoop(L);
 
   SE.forgetLoop(L);
 
   // Note: By splitting the backedge, and then explicitly making it unreachable
   // we gracefully handle corner cases such as non-bottom tested loops and the
   // like.  We also have the benefit of being able to reuse existing well tested
   // code.  It might be worth special casing the common bottom tested case at
   // some point to avoid code churn.
 
   std::unique_ptr<MemorySSAUpdater> MSSAU;
   if (MSSA)
     MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
 
   auto *BackedgeBB = SplitEdge(Latch, Header, &DT, &LI, MSSAU.get());
 
   DomTreeUpdater DTU(&DT, DomTreeUpdater::UpdateStrategy::Eager);
   (void)changeToUnreachable(BackedgeBB->getTerminator(), /*UseTrap*/false,
                             /*PreserveLCSSA*/true, &DTU, MSSAU.get());
 
   // Erase (and destroy) this loop instance.  Handles relinking sub-loops
   // and blocks within the loop as needed.
   LI.erase(L);
+
+  // If the loop we broke had a parent, then changeToUnreachable might have
+  // caused a block to be removed from the parent loop (see loop_nest_lcssa
+  // test case in zero-btc.ll for an example), thus changing the parent's
+  // exit blocks.  If that happened, we need to rebuild LCSSA on the outermost
+  // loop which might have a had a block removed.
+  if (OutermostLoop != L)
+    formLCSSARecursively(*OutermostLoop, DT, &LI, &SE);
 }
 
 
 /// Checks if \p L has single exit through latch block except possibly
 /// "deoptimizing" exits. Returns branch instruction terminating the loop
 /// latch if above check is successful, nullptr otherwise.
 static BranchInst *getExpectedExitLoopLatchBranch(Loop *L) {
   BasicBlock *Latch = L->getLoopLatch();

llvm/test/Transforms/IndVarSimplify/X86/pr45360.ll

 @e = dso_local global i32 0, align 4
 
 define dso_local i32 @main() {
 ; CHECK-LABEL: @main(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[I6:%.*]] = load i32, i32* @a, align 4
 ; CHECK-NEXT:    [[I24:%.*]] = load i32, i32* @b, align 4
 ; CHECK-NEXT:    [[D_PROMOTED9:%.*]] = load i32, i32* @d, align 4
-; CHECK-NEXT:    br label [[BB1:%.*]]
-; CHECK:       bb1:
+; CHECK-NEXT:    br label [[BB13_PREHEADER:%.*]]
+; CHECK:       bb13.preheader:
 ; CHECK-NEXT:    [[I8_LCSSA10:%.*]] = phi i32 [ [[D_PROMOTED9]], [[BB:%.*]] ], [ [[I8:%.*]], [[BB19_PREHEADER:%.*]] ]
 ; CHECK-NEXT:    [[I8]] = and i32 [[I8_LCSSA10]], [[I6]]
 ; CHECK-NEXT:    [[I21:%.*]] = icmp eq i32 [[I8]], 0
 ; CHECK-NEXT:    br i1 [[I21]], label [[BB13_PREHEADER_BB27_THREAD_SPLIT_CRIT_EDGE:%.*]], label [[BB19_PREHEADER]]
 ; CHECK:       bb19.preheader:
 ; CHECK-NEXT:    [[I26:%.*]] = urem i32 [[I24]], [[I8]]
 ; CHECK-NEXT:    store i32 [[I26]], i32* @e, align 4
 ; CHECK-NEXT:    [[I30_NOT:%.*]] = icmp eq i32 [[I26]], 0
-; CHECK-NEXT:    br i1 [[I30_NOT]], label [[BB32_LOOPEXIT:%.*]], label [[BB1]]
+; CHECK-NEXT:    br i1 [[I30_NOT]], label [[BB32_LOOPEXIT:%.*]], label [[BB13_PREHEADER]]
 ; CHECK:       bb13.preheader.bb27.thread.split_crit_edge:
 ; CHECK-NEXT:    store i32 -1, i32* @f, align 4
 ; CHECK-NEXT:    store i32 0, i32* @d, align 4
 ; CHECK-NEXT:    store i32 0, i32* @c, align 4
 ; CHECK-NEXT:    br label [[BB32:%.*]]
 ; CHECK:       bb32.loopexit:
 ; CHECK-NEXT:    store i32 -1, i32* @f, align 4
 ; CHECK-NEXT:    store i32 [[I8]], i32* @d, align 4

llvm/test/Transforms/LoopDeletion/zero-btc.ll

 ; CHECK-LABEL: @test_live_outer(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_INC:%.*]], [[LATCH:%.*]] ]
 ; CHECK-NEXT:    br label [[INNER:%.*]]
 ; CHECK:       inner:
 ; CHECK-NEXT:    store i32 0, i32* @G, align 4
-; CHECK-NEXT:    br i1 false, label [[INNER]], label [[LATCH]]
+; CHECK-NEXT:    br i1 false, label [[INNER_INNER_CRIT_EDGE:%.*]], label [[LATCH]]
+; CHECK:       inner.inner_crit_edge:
+; CHECK-NEXT:    unreachable
 ; CHECK:       latch:
 ; CHECK-NEXT:    store i32 [[IV]], i32* @G, align 4
 ; CHECK-NEXT:    [[IV_INC]] = add i32 [[IV]], 1
 ; CHECK-NEXT:    [[CND:%.*]] = icmp ult i32 [[IV_INC]], 200
 ; CHECK-NEXT:    br i1 [[CND]], label [[LOOP]], label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
 ;

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 1, 2
 ; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
 ; CHECK:       outer_header:
 ; CHECK-NEXT:    br label [[INNER_HEADER:%.*]]
 ; CHECK:       inner_header:
 ; CHECK-NEXT:    br i1 false, label [[INNER_LATCH:%.*]], label [[OUTER_LATCH:%.*]]
 ; CHECK:       inner_latch:
-; CHECK-NEXT:    br i1 false, label [[INNER_HEADER]], label [[LOOPEXIT:%.*]]
+; CHECK-NEXT:    [[DOTLCSSA:%.*]] = phi i32 [ [[TMP0]], [[INNER_HEADER]] ]
+; CHECK-NEXT:    br i1 false, label [[INNER_LATCH_INNER_HEADER_CRIT_EDGE:%.*]], label [[LOOPEXIT:%.*]]
+; CHECK:       inner_latch.inner_header_crit_edge:
+; CHECK-NEXT:    unreachable
 ; CHECK:       outer_latch:
 ; CHECK-NEXT:    br label [[OUTER_HEADER]]
 ; CHECK:       loopexit:
-; CHECK-NEXT:    [[DOTLCSSA32:%.*]] = phi i32 [ [[TMP0]], [[INNER_LATCH]] ]
+; CHECK-NEXT:    [[DOTLCSSA32:%.*]] = phi i32 [ [[DOTLCSSA]], [[INNER_LATCH]] ]
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   br label %outer_header
 
 outer_header:
   %0 = add i32 1, 2
   br label %inner_header