[SCEV] Correct handling of recurrences matched in partially unreachable code (try 2)

[reames]

Summary

(This is, I think, entirely functionally equivalent to https://reviews.llvm.org/D99929. I just preferred this way of framing the fix. The key difference here is focusing on the connection between the loop trip count and the recurrence. I do think we have a recurrence, it's just a trivially one where only the first iteration runs.)

As shown by PR49856 and the reopened test case on PR49768, my first attempt at accounting for unreachable blocks wasn't quite complete. The new approach simply takes what was previously the assert, turns it into a bail out, and adds a comment explaining why it can happen.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

5675

Do we have a guarantee of having no loops in unreachable code?

[reames]

JFYI, planning on pursuing this as a style cleanup over Max's landed change, but distracted due to other events. Will likely be a couple days before I get back to this.

llvm/lib/Analysis/ScalarEvolution.cpp

5675

See LoopInfoBase<>::analyze specififically the line:
DomTree.isReachableFromEntry(Backedge))

Note that the verify routine also checks against a newly constructed LI, so any failure to update should be caught in a expensive asserts run.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

5675

But expensive verification runs between the passes. It is still possible that some pass makes a loop unreachable in the middle of the transform and does not immediately destroy the loop while continuing to use SCEV.

I am still strongly leaning towards not relying on such things, even if they might be correct. It's far from obvious and far from simple.

[reames]

llvm/lib/Analysis/ScalarEvolution.cpp

5675

Passes that rely on running with partially corrupt analyzes are buggy. We should find and fix them.

[mkazantsev]

llvm/lib/Analysis/ScalarEvolution.cpp

5675

It is not a corrupt analysis. It is clearly stated that LI for unreachable blocks is undefined. It may have loops anywhere.

[reames]

I prototyped a couple of alternatives to this, and the resulting interface in matchSimpleRecurrence is ugly and error prone. Based on a survey of the existing users, SCEV is the only place which cares about the mismatch between LoopInfo and reachability.

I'm strongly of the opinion that the loop info approach sketched here is the right one, but given this seems to have stumbled into a much larger issue (with, IMO, incorrect docs and missing asserts) I'm going to set this aside. I already have several major changes in flight and don't have the bandwidth for any more.

llvm/lib/Analysis/ScalarEvolution.cpp

5675

IMO, this is a case where the docs are simply wrong.

The (lack of an) invariant your arguing for here would make it hard to implement any useful analysis based on loops. If we redefined dominance in unreachable code, maybe we could make this work, but with our current domtree semantics not having loopinfo match that is a serious problem.

llvm/lib/Analysis/ScalarEvolution.cpp

getRangeForUnknownRecurrence(const SCEVUnknown *U) {
   if (!P)
     return CR;
 
   BinaryOperator *BO;
   Value *Start, *Step;
   if (!matchSimpleRecurrence(P, BO, Start, Step))
     return CR;
 
-  if (!DT.isReachableFromEntry(P->getParent()) ||
-      !DT.isReachableFromEntry(BO->getParent()))
-    // If either is in unreachable code, dominance collapses and none of our
-    // expected post conditions about loops hold.
-    return CR;
-
   // If we found a recurrence in reachable code, we must be in a loop. Note
   // that BO might be in some subloop of L, and that's completely okay.
   auto *L = LI.getLoopFor(P->getParent());
-  assert(L && L->getHeader() == P->getParent());
-  if (!L->contains(BO->getParent()))
+  if (!L || L->getHeader() != P->getParent())
+    // If we have unreachable blocks involved, then dominance collapses and
+    // we may get trivial recurrences such as:
+    // %phi = phi i64 [%start, %entry], [%step, %unreachable]
+    // %step = add i64 %phi, %step
+    // Or the phi itself may be unreachable.  In such cases, any possible
+    // enclosing loop isn't describing the trip count of the recurrence.
+    return CR;
+
+  if (!L->contains(BO->getParent())) {
     // NOTE: This bailout should be an assert instead.  However, asserting
     // the condition here exposes a case where LoopFusion is querying SCEV
     // with malformed loop information during the midst of the transform.
     // There doesn't appear to be an obvious fix, so for the moment bailout
     // until the caller issue can be fixed.  PR49566 tracks the bug.
     return CR;
+  }
 
   // TODO: Handle ashr and lshr cases to increase minimum value reported
   if (BO->getOpcode() != Instruction::Shl || BO->getOperand(0) != P)
     return CR;
 
   unsigned TC = getSmallConstantMaxTripCount(L);
   if (!TC || TC >= BitWidth)
     return CR;

llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll

 if.then2321:
   ret void
 
 unreachable:
   %sub2629 = sub i32 %p_58.addr.1, 1
   br label %for.cond2295
 }
 
+; Was pr49856.  We can match the recurrence without a loop
+; since dominance collapses in unreachable code.  Conceptually,
+; this is a recurrence which only executes one iteration.
+define void @nonloop_recurrence() {
+; CHECK-LABEL: 'nonloop_recurrence'
+; CHECK-NEXT:  Classifying expressions for: @nonloop_recurrence
+; CHECK-NEXT:    %tmp = phi i32 [ 2, %bb ], [ %tmp2, %bb3 ]
+; CHECK-NEXT:    --> %tmp U: [1,-2147483648) S: [0,-2147483648)
+; CHECK-NEXT:    %tmp2 = add nuw nsw i32 %tmp, 1
+; CHECK-NEXT:    --> (1 + %tmp)<nuw> U: [1,-2147483647) S: [1,-2147483647)
+; CHECK-NEXT:  Determining loop execution counts for: @nonloop_recurrence
+;
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb3, %bb
+  %tmp = phi i32 [ 2, %bb ], [ %tmp2, %bb3 ]
+  %tmp2 = add nuw nsw i32 %tmp, 1
+  ret void
+
+bb3:                                              ; No predecessors!
+  br label %bb1
+}
+
+; Tweak of pr49856 test case - analogous, but there is a loop
+; it's trip count simply doesn't relate to the single iteration
+; "recurrence" we found.
+define void @nonloop_recurrence_2() {
+; CHECK-LABEL: 'nonloop_recurrence_2'
+; CHECK-NEXT:  Classifying expressions for: @nonloop_recurrence_2
+; CHECK-NEXT:    %tmp = phi i32 [ 2, %loop ], [ %tmp2, %bb3 ]
+; CHECK-NEXT:    --> %tmp U: [1,-2147483648) S: [0,-2147483648) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    %tmp2 = add nuw nsw i32 %tmp, 1
+; CHECK-NEXT:    --> (1 + %tmp)<nuw> U: [1,-2147483647) S: [1,-2147483647) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:  Determining loop execution counts for: @nonloop_recurrence_2
+; CHECK-NEXT:  Loop %loop: <multiple exits> Unpredictable backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable max backedge-taken count.
+; CHECK-NEXT:  Loop %loop: Unpredictable predicated backedge-taken count.
+;
+bb:
+  br label %loop
+
+loop:
+  br label %bb1
+bb1:                                              ; preds = %bb3, %loop
+  %tmp = phi i32 [ 2, %loop ], [ %tmp2, %bb3 ]
+  %tmp2 = add nuw nsw i32 %tmp, 1
+  br label %loop
+
+bb3:                                              ; No predecessors!
+  br label %bb1
+}
+
+
 ; Next batch of tests show where we can get tighter ranges on ashr/lshr
 ; by using the trip count information on the loop.
 
 define void @test_ashr_tc_positive() {
 ; CHECK-LABEL: 'test_ashr_tc_positive'
 ; CHECK-NEXT:  Classifying expressions for: @test_ashr_tc_positive
 ; CHECK-NEXT:    %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ]
 ; CHECK-NEXT:    --> {0,+,1}<%loop> U: [0,5) S: [0,5) Exits: 4 LoopDispositions: { %loop: Computable }