[SCEV] Fix false-positive recognition of simple recurrences. PR49856

[mkazantsev]

Summary

A value from reachable block may come to a Phi node as its input from
unreachable block. This may confuse matchSimpleRecurrence which
has no access to DomTree and can falsely recognize something as a recurrency
because of this effect, as the attached test shows.

Patch ae7b1e deals with half of this problem, but it only accounts from
the case when an unreachable instruction comes to Phi as an input.

This patch provides a generalization by checking that no Phi block's
predecessor is unreachable (no matter what the input is).

[mkazantsev]

Trivialized test.

[reames]

I posted an alternate fix here: https://reviews.llvm.org/D100004. Let me know what you think. Stylistically, I prefer that one, but yours appears to be correct as well.

Given that, I'm LGTMing this, but asking you not to land unless you spot a problem with the one I linked to. If you do, feel free to land this, and I can work on top of it. I don't want to delay the correctness fix over a debatable style issue.

[mkazantsev]

I can't say if the alternative a correct solution because I don't know if we guarantee to destroy all loops immediately after some block contained in them has become urneachable. If not, then the alternative solution also contains this bug. If yes, this is not obvious and I'm not sure where it is asserted. We can go with it if we have the answers to these questions. I don't see any problems with having a loop in fully unreachable code, or having extra unreachable predecessors to loop blocks.

llvm/lib/Analysis/ScalarEvolution.cpp

getRangeForUnknownRecurrence(const SCEVUnknown *U) {
   // the one used by AddRec (and thus most of this file).  Step is allowed to
   // be arbitrarily loop varying here, where AddRec allows only loop invariant
   // and other addrecs in the same loop (for non-affine addrecs).  The code
   // below intentionally handles the case where step is not loop invariant.
   auto *P = dyn_cast<PHINode>(U->getValue());
   if (!P)
     return CR;
 
+  // Make sure that no Phi input comes from an unreachable block. Otherwise,
+  // even the values that are not available in these blocks may come from them,
+  // and this leads to false-positive recurrence test.
+  for (auto *Pred : predecessors(P->getParent()))
+    if (!DT.isReachableFromEntry(Pred))
+      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()))
     // 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.

llvm/test/Analysis/ScalarEvolution/pr49856.ll

+; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
+; RUN: opt < %s -analyze -enable-new-pm=0 -scalar-evolution | FileCheck %s
+; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128-ni:1-p2:32:8:8:32-ni:2"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @test() {
+; CHECK-LABEL: 'test'
+; CHECK-NEXT:  Classifying expressions for: @test
+; CHECK-NEXT:    %tmp = phi i32 [ 2, %bb1 ], [ %tmp6, %bb9 ]
+; CHECK-NEXT:    --> %tmp U: [1,-2147483648) S: [0,-2147483648)
+; CHECK-NEXT:    %tmp6 = add nuw nsw i32 %tmp, 1
+; CHECK-NEXT:    --> (1 + %tmp)<nuw> U: [1,-2147483647) S: [1,-2147483647)
+; CHECK-NEXT:    %tmp15 = phi i32 [ %tmp16, %bb14 ], [ undef, %bb13 ]
+; CHECK-NEXT:    --> {undef,+,1}<nsw><%bb14> U: full-set S: full-set Exits: (-1 + (26 smax (1 + undef)))<nsw> LoopDispositions: { %bb14: Computable }
+; CHECK-NEXT:    %tmp16 = add nsw i32 %tmp15, 1
+; CHECK-NEXT:    --> {(1 + undef),+,1}<nsw><%bb14> U: full-set S: full-set Exits: (26 smax (1 + undef)) LoopDispositions: { %bb14: Computable }
+; CHECK-NEXT:  Determining loop execution counts for: @test
+; CHECK-NEXT:  Loop %bb14: backedge-taken count is (-1 + (-1 * undef) + (26 smax (1 + undef)))
+; CHECK-NEXT:  Loop %bb14: max backedge-taken count is -2147483622
+; CHECK-NEXT:  Loop %bb14: Predicated backedge-taken count is (-1 + (-1 * undef) + (26 smax (1 + undef)))
+; CHECK-NEXT:   Predicates:
+; CHECK:       Loop %bb14: Trip multiple is 1
+;
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb
+  br label %bb5
+
+bb2:                                              ; preds = %bb2
+  br label %bb2
+
+bb3:                                              ; preds = %bb3
+  br label %bb3
+
+bb4:                                              ; preds = %bb4
+  br label %bb4
+
+bb5:                                              ; preds = %bb9, %bb1
+  %tmp = phi i32 [ 2, %bb1 ], [ %tmp6, %bb9 ]
+  %tmp6 = add nuw nsw i32 %tmp, 1
+  %tmp7 = icmp ult i32 %tmp6, undef
+  br i1 %tmp7, label %bb13, label %bb18
+
+bb8:                                              ; preds = %bb8
+  br label %bb8
+
+bb9:                                              ; No predecessors!
+  br label %bb5
+
+bb10:                                             ; preds = %bb10
+  br label %bb10
+
+bb11:                                             ; preds = %bb11
+  br label %bb11
+
+bb12:                                             ; preds = %bb12
+  br label %bb12
+
+bb13:                                             ; preds = %bb5
+  br label %bb14
+
+bb14:                                             ; preds = %bb14, %bb13
+  %tmp15 = phi i32 [ %tmp16, %bb14 ], [ undef, %bb13 ]
+  %tmp16 = add nsw i32 %tmp15, 1
+  %tmp17 = icmp sgt i32 %tmp16, 25
+  br i1 %tmp17, label %bb19, label %bb14
+
+bb18:                                             ; preds = %bb5
+  unreachable
+
+bb19:                                             ; preds = %bb14
+  ret void
+}