[LoopRotate] Fix incorrect SCEV invalidation in loop rotation

[mkazantsev]

Summary

LoopRotate only invalidates innermost loops while the changes that it makes may
also affert any of this parents. With patch rL329047, SCEV becomes much smarter
about calculation of exit counts for outer loops, so we cannot assume that they are
not affected.

[mkazantsev]

We've fixed a bunch of bugs of this sort, so I think it's fine to go with.

[chandlerc]

In D45945#1075073, @mkazantsev wrote:

We've fixed a bunch of bugs of this sort, so I think it's fine to go with.

So generally, as a matter of politeness, good to avoid the review if you're gonna go with post-submit.

However I also have a question here -- are we going to have any SCEV left?

We don't re-run SCEV mid-way through the loop pass manager. If we invalidate all outer scevs when we loop rotate, won't that completely defeat SCEVs analysis on outer loops? Or will we lazily rebuild it?

[sanjoy]

In D45945#1075786, @chandlerc wrote:

Or will we lazily rebuild it?

We will lazily rebuild SCEV expressions as needed. Not great for compile time, but we should be functionally correct.

@mkazantsev: IMO this illustrates an architectural problem with SCEV's cache -- ideally the cache would parallel the hierarchy of the loop tree itself so that changing an inner loop does not require us to throw away all of the information computed on the outer loop. Do you have some ideas on how we can fix this architectural issue?

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

262 ↗

(On Diff #143529)

Can you please add a comment on *how* we can affect parent loops? Rotating an inner loop should not change the trip count of outer loops so right now the statement sounds a bit confusing. Perhaps: "Loop rotation can change the dominance relationships between blocks in the inner loop and blocks in the outer loop. It may also delete blocks from the inner loop. Both of these may end up violating invariants in backedge taken infos cached by SCEV about outer loops."

[mkazantsev]

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

262 ↗

(On Diff #143529)

Done at https://reviews.llvm.org/rL330677

lib/Transforms/Utils/LoopRotationUtils.cpp

bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {
   BasicBlock *OrigPreheader = L->getLoopPreheader();
 
   // If the loop could not be converted to canonical form, it must have an
   // indirectbr in it, just give up.
   if (!OrigPreheader || !L->hasDedicatedExits())
     return false;
 
   // Anything ScalarEvolution may know about this loop or the PHI nodes
-  // in its header will soon be invalidated.
+  // in its header will soon be invalidated, and it can also affect its parent
+  // loops as well.
   if (SE)
-    SE->forgetLoop(L);
+    SE->forgetTopmostLoop(L);
 
   DEBUG(dbgs() << "LoopRotation: rotating "; L->dump());
 
   // Find new Loop header. NewHeader is a Header's one and only successor
   // that is inside loop.  Header's other successor is outside the
   // loop.  Otherwise loop is not suitable for rotation.
   BasicBlock *Exit = BI->getSuccessor(0);
   BasicBlock *NewHeader = BI->getSuccessor(1);
bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) {
   // Now that the CFG and DomTree are in a consistent state again, try to merge
   // the OrigHeader block into OrigLatch.  This will succeed if they are
   // connected by an unconditional branch.  This is just a cleanup so the
   // emitted code isn't too gross in this common case.
   MergeBlockIntoPredecessor(OrigHeader, DT, LI);
 
   DEBUG(dbgs() << "LoopRotation: into "; L->dump());
 
+#ifndef NDEBUG
+  // Make sure that after all our transforms SE is correct.
+  if (SE)
+    SE->verify();
+#endif
+
   ++NumRotated;
   return true;
 }
 
 /// Determine whether the instructions in this range may be safely and cheaply
 /// speculated. This is not an important enough situation to develop complex
 /// heuristics. We handle a single arithmetic instruction along with any type
 /// conversions.

test/Transforms/LoopRotate/pr37205.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S -indvars -verify -loop-rotate -loop-idiom < %s | FileCheck %s
+target triple = "x86_64-unknown-linux-gnu"
+
+; Verify that we invalidate SCEV properly.
+
+define void @test_01() {
+; CHECK-LABEL: @test_01(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LBL1:%.*]]
+; CHECK:       lbl1:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    br i1 false, label [[FOR_BODY3_LR_PH:%.*]], label [[FOR_COND_FOR_END5_CRIT_EDGE:%.*]]
+; CHECK:       for.body3.lr.ph:
+; CHECK-NEXT:    br label [[FOR_BODY3:%.*]]
+; CHECK:       for.cond1:
+; CHECK-NEXT:    br i1 false, label [[FOR_BODY3]], label [[FOR_COND1_FOR_END5_CRIT_EDGE:%.*]]
+; CHECK:       for.body3:
+; CHECK-NEXT:    br i1 false, label [[IF_THEN:%.*]], label [[FOR_COND1:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    br label [[LBL1]]
+; CHECK:       for.cond.for.end5_crit_edge:
+; CHECK-NEXT:    br label [[FOR_END5:%.*]]
+; CHECK:       for.cond1.for.end5_crit_edge:
+; CHECK-NEXT:    br label [[FOR_END5]]
+; CHECK:       for.end5:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %lbl1
+
+lbl1:                                             ; preds = %if.then, %entry
+  br label %for.cond
+
+for.cond:                                         ; preds = %lbl1
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %if.end, %for.cond
+  br i1 false, label %for.body3, label %for.end5
+
+for.body3:                                        ; preds = %for.cond1
+  br i1 false, label %if.then, label %if.end
+
+if.then:                                          ; preds = %for.body3
+  br label %lbl1
+
+if.end:                                           ; preds = %for.body3
+  br label %for.cond1
+
+for.end5:                                         ; preds = %for.cond1
+  ret void
+}
+
+define void @test_02() {
+; CHECK-LABEL: @test_02(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LBL1:%.*]]
+; CHECK:       lbl1:
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    br i1 false, label [[IF_THEN:%.*]], label [[IF_END7:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    br i1 false, label [[FOR_BODY_LR_PH:%.*]], label [[IF_THEN_FOR_END6_CRIT_EDGE:%.*]]
+; CHECK:       for.body.lr.ph:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    br i1 false, label [[IF_THEN3:%.*]], label [[IF_END:%.*]]
+; CHECK:       if.then3:
+; CHECK-NEXT:    br label [[LBL1]]
+; CHECK:       if.end:
+; CHECK-NEXT:    br label [[FOR_COND4:%.*]]
+; CHECK:       for.cond4:
+; CHECK-NEXT:    br i1 false, label [[FOR_BODY]], label [[FOR_COND1_FOR_END6_CRIT_EDGE:%.*]]
+; CHECK:       if.then.for.end6_crit_edge:
+; CHECK-NEXT:    br label [[FOR_END6:%.*]]
+; CHECK:       for.cond1.for.end6_crit_edge:
+; CHECK-NEXT:    br label [[FOR_END6]]
+; CHECK:       for.end6:
+; CHECK-NEXT:    ret void
+; CHECK:       if.end7:
+; CHECK-NEXT:    unreachable
+;
+entry:
+  br label %lbl1
+
+lbl1:                                             ; preds = %if.then3, %entry
+  br label %for.cond
+
+for.cond:                                         ; preds = %lbl1
+  br i1 false, label %if.then, label %if.end7
+
+if.then:                                          ; preds = %for.cond
+  br label %for.cond1
+
+for.cond1:                                        ; preds = %for.cond4, %if.then
+  br i1 undef, label %for.body, label %for.end6
+
+for.body:                                         ; preds = %for.cond1
+  br i1 false, label %if.then3, label %if.end
+
+if.then3:                                         ; preds = %for.body
+  br label %lbl1
+
+if.end:                                           ; preds = %for.body
+  br label %for.cond4
+
+for.cond4:                                        ; preds = %if.end
+  br label %for.cond1
+
+for.end6:                                         ; preds = %for.cond1
+  ret void
+
+if.end7:                                          ; preds = %for.cond
+  unreachable
+}