[ScalarEvolution] Skip values from unreachable bbs for phi ranges.

[fhahn]

Summary

Skip incoming value from unreachable blocks when computing ranges for
phis. Constructing SCEVs for values from unreachable blocks may lead to
violating assumptions based on dominance.

One example is the added LV test case. Here an assertion in GroupByComplexity
is triggered when constructing a SCEV for the incoming value from the unreachable
block because there's no dominance relation between 2 AddRecs.

It removes pr49856.ll because it is already part of
shift-recurrences.ll and needs updating.

Fixes #58811.

[efriedma]

The assertion from the bug report seems several levels removed from the top-level APIs; can we add an assertion somewhere a bit closer to the API misuse? I don't see a problem with this patch, exactly, but I'm not sure why the current code is wrong, as opposed to just being slightly suboptimal.

[mkazantsev]

Do you mind giving more details on what assumption exactly was broken?

[fhahn]

I had another look and this patch didn't address the underlying issue properly, the problem is in the user of SCEV which tries to query partially constructed IR. I started working on a proper fix: D147965

llvm/lib/Analysis/ScalarEvolution.cpp

if (NS > 1)
                         APInt::getSignedMaxValue(BitWidth).ashr(NS - 1) + 1),
           RangeType);
 
     // A range of Phi is a subset of union of all ranges of its input.
     if (const PHINode *Phi = dyn_cast<PHINode>(U->getValue())) {
       // Make sure that we do not run over cycled Phis.
       if (PendingPhiRanges.insert(Phi).second) {
         ConstantRange RangeFromOps(BitWidth, /*isFullSet=*/false);
-        for (const auto &Op : Phi->operands()) {
+        for (const auto [Op, Block]: zip(Phi->operands(), Phi->blocks())) {
+          if (!DT.isReachableFromEntry(Block))
+            continue;
+
           auto OpRange = getRangeRef(getSCEV(Op), SignHint);
           RangeFromOps = RangeFromOps.unionWith(OpRange);
           // No point to continue if we already have a full set.
           if (RangeFromOps.isFullSet())
             break;
         }
         ConservativeResult =
             ConservativeResult.intersectWith(RangeFromOps, RangeType);

llvm/test/Analysis/ScalarEvolution/pr49856.ll

-; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py
-; RUN: opt < %s -disable-output "-passes=print<scalar-evolution>" 2>&1 | FileCheck %s
-
-define void @test() {
-; CHECK-LABEL: 'test'
-; CHECK-NEXT:  Classifying expressions for: @test
-; 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: @test
-;
-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
-}

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

 
 ; 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:    --> %tmp U: [2,3) S: [2,3)
 ; CHECK-NEXT:    %tmp2 = add nuw nsw i32 %tmp, 1
-; CHECK-NEXT:    --> (1 + %tmp)<nuw> U: [1,-2147483647) S: [1,-2147483647)
+; CHECK-NEXT:    --> (1 + %tmp)<nuw><nsw> U: [3,4) S: [3,4)
 ; 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:    --> %tmp U: [2,3) S: [2,3) 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:    --> (1 + %tmp)<nuw><nsw> U: [3,4) S: [3,4) 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
 

llvm/test/Transforms/LoopIdiom/X86/memset-size-compute.ll

 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_BODY_PREHEADER:%.*]]
 ; CHECK:       dead:
 ; CHECK-NEXT:    br label [[FOR_BODY_PREHEADER]]
 ; CHECK:       for.body.preheader:
 ; CHECK-NEXT:    [[LIM_0:%.*]] = phi i32 [ 65, [[ENTRY:%.*]] ], [ 1, [[DEAD:%.*]] ]
 ; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i64, i64* [[PTR:%.*]], i64 1
 ; CHECK-NEXT:    [[SCEVGEP1:%.*]] = bitcast i64* [[SCEVGEP]] to i8*
-; CHECK-NEXT:    [[UMAX:%.*]] = call i32 @llvm.umax.i32(i32 [[LIM_0]], i32 2)
-; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i32 [[UMAX]], -1
+; CHECK-NEXT:    [[TMP0:%.*]] = add nsw i32 [[LIM_0]], -1
 ; CHECK-NEXT:    [[TMP1:%.*]] = zext i32 [[TMP0]] to i64
 ; CHECK-NEXT:    [[TMP2:%.*]] = shl nuw nsw i64 [[TMP1]], 3
 ; CHECK-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 8 [[SCEVGEP1]], i8 0, i64 [[TMP2]], i1 false)
 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[FOR_BODY]] ], [ 1, [[FOR_BODY_PREHEADER]] ]
 ; CHECK-NEXT:    [[IV_EXT:%.*]] = zext i32 [[IV]] to i64
 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr inbounds i64, i64* [[PTR]], i64 [[IV_EXT]]

llvm/test/Transforms/LoopVectorize/scev-expansion-unreachable.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -passes=loop-vectorize -force-vector-width=4 -force-vector-interleave=1 -S %s | FileCheck %s
+
+define void @pr58811() {
+; CHECK-LABEL: @pr58811(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP_1_PREHEADER:%.*]]
+; CHECK:       loop.1.preheader:
+; CHECK-NEXT:    [[IV_1_PH:%.*]] = phi i32 [ [[SUB93_2:%.*]], [[UNREACHABLE_BB:%.*]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i32 0, [[IV_1_PH]]
+; CHECK-NEXT:    br label [[LOOP_1:%.*]]
+; CHECK:       loop.1:
+; CHECK-NEXT:    [[INDUCTION_IV:%.*]] = phi i32 [ [[INDUCTION_IV_NEXT:%.*]], [[LOOP_1]] ], [ [[TMP0]], [[LOOP_1_PREHEADER]] ]
+; CHECK-NEXT:    [[IV_1:%.*]] = phi i32 [ [[IV_1_NEXT:%.*]], [[LOOP_1]] ], [ [[IV_1_PH]], [[LOOP_1_PREHEADER]] ]
+; CHECK-NEXT:    [[IV_2:%.*]] = phi i32 [ [[IV_2_NEXT:%.*]], [[LOOP_1]] ], [ 0, [[LOOP_1_PREHEADER]] ]
+; CHECK-NEXT:    [[TMP1:%.*]] = mul nuw nsw i32 [[IV_2]], -1
+; CHECK-NEXT:    [[IV_2_NEXT]] = add i32 [[IV_2]], 1
+; CHECK-NEXT:    [[IV_1_NEXT]] = add i32 [[IV_2]], [[IV_1]]
+; CHECK-NEXT:    [[INDUCTION_IV_NEXT]] = add i32 [[INDUCTION_IV]], [[TMP1]]
+; CHECK-NEXT:    br i1 false, label [[LOOP_1]], label [[LOOP_2_PREHEADER:%.*]]
+; CHECK:       loop.2.preheader:
+; CHECK-NEXT:    [[INDUCTION_IV_LCSSA3:%.*]] = phi i32 [ [[INDUCTION_IV]], [[LOOP_1]] ]
+; CHECK-NEXT:    [[INDUCTION_IV_LCSSA2:%.*]] = phi i32 [ [[INDUCTION_IV]], [[LOOP_1]] ]
+; CHECK-NEXT:    [[INDUCTION_IV_LCSSA:%.*]] = phi i32 [ [[INDUCTION_IV]], [[LOOP_1]] ]
+; CHECK-NEXT:    [[IV_1_LCSSA:%.*]] = phi i32 [ [[IV_1]], [[LOOP_1]] ]
+; CHECK-NEXT:    br i1 false, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
+; CHECK:       vector.ph:
+; CHECK-NEXT:    [[IND_END:%.*]] = mul i32 196, [[INDUCTION_IV_LCSSA]]
+; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
+; CHECK:       vector.body:
+; CHECK-NEXT:    [[INDEX:%.*]] = phi i32 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
+; CHECK-NEXT:    [[OFFSET_IDX:%.*]] = mul i32 [[INDEX]], [[INDUCTION_IV_LCSSA2]]
+; CHECK-NEXT:    [[TMP2:%.*]] = mul i32 0, [[INDUCTION_IV_LCSSA2]]
+; CHECK-NEXT:    [[TMP3:%.*]] = add i32 [[OFFSET_IDX]], [[TMP2]]
+; CHECK-NEXT:    [[TMP4:%.*]] = mul i32 1, [[INDUCTION_IV_LCSSA2]]
+; CHECK-NEXT:    [[TMP5:%.*]] = add i32 [[OFFSET_IDX]], [[TMP4]]
+; CHECK-NEXT:    [[TMP6:%.*]] = mul i32 2, [[INDUCTION_IV_LCSSA2]]
+; CHECK-NEXT:    [[TMP7:%.*]] = add i32 [[OFFSET_IDX]], [[TMP6]]
+; CHECK-NEXT:    [[TMP8:%.*]] = mul i32 3, [[INDUCTION_IV_LCSSA2]]
+; CHECK-NEXT:    [[TMP9:%.*]] = add i32 [[OFFSET_IDX]], [[TMP8]]
+; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i32 [[INDEX]], 4
+; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i32 [[INDEX_NEXT]], 196
+; CHECK-NEXT:    br i1 [[TMP10]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP0:![0-9]+]]
+; CHECK:       middle.block:
+; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i32 199, 196
+; CHECK-NEXT:    [[IND_ESCAPE:%.*]] = mul i32 195, [[INDUCTION_IV_LCSSA3]]
+; CHECK-NEXT:    br i1 [[CMP_N]], label [[LOOP_3_PREHEADER:%.*]], label [[SCALAR_PH]]
+; CHECK:       scalar.ph:
+; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i16 [ 196, [[MIDDLE_BLOCK]] ], [ 0, [[LOOP_2_PREHEADER]] ]
+; CHECK-NEXT:    [[BC_RESUME_VAL1:%.*]] = phi i32 [ [[IND_END]], [[MIDDLE_BLOCK]] ], [ 0, [[LOOP_2_PREHEADER]] ]
+; CHECK-NEXT:    br label [[LOOP_2:%.*]]
+; CHECK:       loop.2:
+; CHECK-NEXT:    [[IV_3:%.*]] = phi i16 [ [[IV_3_NEXT:%.*]], [[LOOP_2]] ], [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ]
+; CHECK-NEXT:    [[IV_4:%.*]] = phi i32 [ [[IV_4_NEXT:%.*]], [[LOOP_2]] ], [ [[BC_RESUME_VAL1]], [[SCALAR_PH]] ]
+; CHECK-NEXT:    [[IV_4_NEXT]] = sub i32 [[IV_4]], [[IV_1_LCSSA]]
+; CHECK-NEXT:    [[IV_3_NEXT]] = add i16 [[IV_3]], 1
+; CHECK-NEXT:    [[CMP88_1:%.*]] = icmp ult i16 [[IV_3]], 198
+; CHECK-NEXT:    br i1 [[CMP88_1]], label [[LOOP_2]], label [[LOOP_3_PREHEADER]], !llvm.loop [[LOOP2:![0-9]+]]
+; CHECK:       loop.3.preheader:
+; CHECK-NEXT:    [[IV_4_LCSSA:%.*]] = phi i32 [ [[IV_4]], [[LOOP_2]] ], [ [[IND_ESCAPE]], [[MIDDLE_BLOCK]] ]
+; CHECK-NEXT:    br label [[LOOP_3:%.*]]
+; CHECK:       loop.3:
+; CHECK-NEXT:    [[IV_5:%.*]] = phi i32 [ [[SUB93_2]], [[LOOP_3]] ], [ 0, [[LOOP_3_PREHEADER]] ]
+; CHECK-NEXT:    [[SUB93_2]] = sub i32 [[IV_5]], [[IV_4_LCSSA]]
+; CHECK-NEXT:    br label [[LOOP_3]]
+; CHECK:       unreachable.bb:
+; CHECK-NEXT:    br label [[LOOP_1_PREHEADER]]
+;
+entry:
+  br label %loop.1.preheader
+
+loop.1.preheader:
+  %iv.1.ph = phi i32 [ %sub93.2, %unreachable.bb ], [ 0, %entry ]
+  br label %loop.1
+
+loop.1:
+  %iv.1 = phi i32 [ %iv.1.next, %loop.1 ], [ %iv.1.ph, %loop.1.preheader ]
+  %iv.2 = phi i32 [ %iv.2.next, %loop.1 ], [ 0, %loop.1.preheader ]
+  %iv.2.next = add i32 %iv.2, 1
+  %iv.1.next = add i32 %iv.2, %iv.1
+  br i1 false, label %loop.1, label %loop.2.preheader
+
+loop.2.preheader:
+  %iv.1.lcssa = phi i32 [ %iv.1, %loop.1 ]
+  br label %loop.2
+
+loop.2:
+  %iv.3 = phi i16 [ %iv.3.next, %loop.2 ], [ 0, %loop.2.preheader ]
+  %iv.4 = phi i32 [ %iv.4.next, %loop.2 ], [ 0, %loop.2.preheader ]
+  %iv.4.next = sub i32 %iv.4, %iv.1.lcssa
+  %iv.3.next = add i16 %iv.3, 1
+  %cmp88.1 = icmp ult i16 %iv.3, 198
+  br i1 %cmp88.1, label %loop.2, label %loop.3.preheader
+
+loop.3.preheader:
+  %iv.4.lcssa = phi i32 [ %iv.4, %loop.2 ]
+  br label %loop.3
+
+loop.3:
+  %iv.5 = phi i32 [ %sub93.2, %loop.3 ], [ 0, %loop.3.preheader ]
+  %sub93.2 = sub i32 %iv.5, %iv.4.lcssa
+  br label %loop.3
+
+unreachable.bb:                                   ; No predecessors!
+  br label %loop.1.preheader
+}