Index: llvm/include/llvm/Analysis/ScalarEvolution.h =================================================================== --- llvm/include/llvm/Analysis/ScalarEvolution.h +++ llvm/include/llvm/Analysis/ScalarEvolution.h @@ -1561,6 +1561,12 @@ ConstantRange getRangeViaFactoring(const SCEV *Start, const SCEV *Stop, const SCEV *MaxBECount, unsigned BitWidth); + /// If the unknown expression U corresponds to a simple recurrence, return + /// a constant range which represents the entire recurrence. Note that + /// *add* recurrences aren't represented by SCEVUnknowns and thus don't use + /// this mechanism. + ConstantRange getRangeForUnknownRecurrence(const SCEVUnknown *U); + /// We know that there is no SCEV for the specified value. Analyze the /// expression. const SCEV *createSCEV(Value *V); Index: llvm/lib/Analysis/ScalarEvolution.cpp =================================================================== --- llvm/lib/Analysis/ScalarEvolution.cpp +++ llvm/lib/Analysis/ScalarEvolution.cpp @@ -5637,6 +5637,59 @@ } } +ConstantRange ScalarEvolution:: +getRangeForUnknownRecurrence(const SCEVUnknown *U) { + const DataLayout &DL = getDataLayout(); + + unsigned BitWidth = getTypeSizeInBits(U->getType()); + ConstantRange CR(BitWidth, /*isFullSet=*/true); + + // Match a simple recurrence of the form: , and then + // use information about the trip count to improve our available range. Note + // that the trip count independent cases are already handled by known bits. + auto *P = dyn_cast(U->getValue()); + if (!P) + return CR; + auto *L = LI.getLoopFor(P->getParent()); + if (!L || L->getHeader() != P->getParent()) + return CR; + + BinaryOperator *BO; + Value *Start, *Step; + if (!matchSimpleRecurrence(P, BO, Start, Step)) + 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; + + auto KnownStart = computeKnownBits(Start, DL, 0, &AC, nullptr, &DT); + auto KnownStep = computeKnownBits(Step, DL, 0, &AC, nullptr, &DT); + assert(KnownStart.getBitWidth() == BitWidth && + KnownStep.getBitWidth() == BitWidth); + + // Compute total shift amount, being careful of overflow and bitwidths. + auto MaxShiftAmt = KnownStep.getMaxValue(); + bool Overflow = false; + auto TotalShift = MaxShiftAmt.umul_ov(APInt(BitWidth, TC-1, false), Overflow); + if (Overflow) + return CR; + + // Iff no bits are shifted out, value increases on every shift. + auto KnownEnd = KnownBits::shl(KnownStart, + KnownBits::makeConstant(TotalShift)); + if (TotalShift.ult(KnownStart.countMinLeadingZeros())) + CR = CR.intersectWith(ConstantRange(KnownStart.getMinValue(), + KnownEnd.getMaxValue() + 1)); + return CR; +} + + + /// Determine the range for a particular SCEV. If SignHint is /// HINT_RANGE_UNSIGNED (resp. HINT_RANGE_SIGNED) then getRange prefers ranges /// with a "cleaner" unsigned (resp. signed) representation. @@ -5837,12 +5890,19 @@ } if (const SCEVUnknown *U = dyn_cast(S)) { + // Check if the IR explicitly contains !range metadata. Optional MDRange = GetRangeFromMetadata(U->getValue()); if (MDRange.hasValue()) ConservativeResult = ConservativeResult.intersectWith(MDRange.getValue(), RangeType); + // Use facts about recurrences in the underlying IR. Note that add + // recurrences are AddRecExprs and thus don't hit this path. This + // primarily handles shift recurrences. + auto CR = getRangeForUnknownRecurrence(U); + ConservativeResult = ConservativeResult.intersectWith(CR); + // See if ValueTracking can give us a useful range. const DataLayout &DL = getDataLayout(); KnownBits Known = computeKnownBits(U->getValue(), DL, 0, &AC, nullptr, &DT); Index: llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll =================================================================== --- /dev/null +++ llvm/test/Analysis/ScalarEvolution/shift-recurrences.ll @@ -0,0 +1,318 @@ +; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py +; RUN: opt -analyze -enable-new-pm=0 -scalar-evolution < %s | FileCheck %s +; RUN: opt -disable-output "-passes=print" < %s 2>&1 | FileCheck %s + +define void @test_lshr() { +; CHECK-LABEL: 'test_lshr' +; CHECK-NEXT: Classifying expressions for: @test_lshr +; CHECK-NEXT: %iv.lshr = phi i64 [ 1023, %entry ], [ %iv.lshr.next, %loop ] +; CHECK-NEXT: --> %iv.lshr U: [0,1024) S: [0,1024) Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: %iv.lshr.next = lshr i64 %iv.lshr, 1 +; CHECK-NEXT: --> (%iv.lshr /u 2) U: [0,512) S: [0,512) Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: Determining loop execution counts for: @test_lshr +; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. +; CHECK-NEXT: Loop %loop: Unpredictable max backedge-taken count. +; CHECK-NEXT: Loop %loop: Unpredictable predicated backedge-taken count. +; +entry: + br label %loop +loop: + %iv.lshr = phi i64 [1023, %entry], [%iv.lshr.next, %loop] + %iv.lshr.next = lshr i64 %iv.lshr, 1 + br i1 undef, label %exit, label %loop +exit: + ret void +} + +; Deliberate overflow doesn't change range +define void @test_lshr2() { +; CHECK-LABEL: 'test_lshr2' +; CHECK-NEXT: Classifying expressions for: @test_lshr2 +; CHECK-NEXT: %iv.lshr = phi i64 [ 1023, %entry ], [ %iv.lshr.next, %loop ] +; CHECK-NEXT: --> %iv.lshr U: [0,1024) S: [0,1024) Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: %iv.lshr.next = lshr i64 %iv.lshr, 4 +; CHECK-NEXT: --> (%iv.lshr /u 16) U: [0,64) S: [0,64) Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: Determining loop execution counts for: @test_lshr2 +; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. +; CHECK-NEXT: Loop %loop: Unpredictable max backedge-taken count. +; CHECK-NEXT: Loop %loop: Unpredictable predicated backedge-taken count. +; +entry: + br label %loop +loop: + %iv.lshr = phi i64 [1023, %entry], [%iv.lshr.next, %loop] + %iv.lshr.next = lshr i64 %iv.lshr, 4 + br i1 undef, label %exit, label %loop +exit: + ret void +} + + +define void @test_ashr_zeros() { +; CHECK-LABEL: 'test_ashr_zeros' +; CHECK-NEXT: Classifying expressions for: @test_ashr_zeros +; CHECK-NEXT: %iv.ashr = phi i64 [ 1023, %entry ], [ %iv.ashr.next, %loop ] +; CHECK-NEXT: --> %iv.ashr U: [0,1024) S: [0,1024) Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: %iv.ashr.next = ashr i64 %iv.ashr, 1 +; CHECK-NEXT: --> %iv.ashr.next U: [0,512) S: [0,512) Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: Determining loop execution counts for: @test_ashr_zeros +; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. +; CHECK-NEXT: Loop %loop: Unpredictable max backedge-taken count. +; CHECK-NEXT: Loop %loop: Unpredictable predicated backedge-taken count. +; +entry: + br label %loop +loop: + %iv.ashr = phi i64 [1023, %entry], [%iv.ashr.next, %loop] + %iv.ashr.next = ashr i64 %iv.ashr, 1 + br i1 undef, label %exit, label %loop +exit: + ret void +} + +define void @test_ashr_ones() { +; CHECK-LABEL: 'test_ashr_ones' +; CHECK-NEXT: Classifying expressions for: @test_ashr_ones +; CHECK-NEXT: %iv.ashr = phi i64 [ -1023, %entry ], [ %iv.ashr.next, %loop ] +; CHECK-NEXT: --> %iv.ashr U: [-1023,0) S: [-1023,0) Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: %iv.ashr.next = ashr i64 %iv.ashr, 1 +; CHECK-NEXT: --> %iv.ashr.next U: [-512,0) S: [-512,0) Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: Determining loop execution counts for: @test_ashr_ones +; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. +; CHECK-NEXT: Loop %loop: Unpredictable max backedge-taken count. +; CHECK-NEXT: Loop %loop: Unpredictable predicated backedge-taken count. +; +entry: + br label %loop +loop: + %iv.ashr = phi i64 [-1023, %entry], [%iv.ashr.next, %loop] + %iv.ashr.next = ashr i64 %iv.ashr, 1 + br i1 undef, label %exit, label %loop +exit: + ret void +} + +; Same as previous, but swapped operands to phi +define void @test_ashr_ones2() { +; CHECK-LABEL: 'test_ashr_ones2' +; CHECK-NEXT: Classifying expressions for: @test_ashr_ones2 +; CHECK-NEXT: %iv.ashr = phi i64 [ %iv.ashr.next, %loop ], [ -1023, %entry ] +; CHECK-NEXT: --> %iv.ashr U: [-1023,0) S: [-1023,0) Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: %iv.ashr.next = ashr i64 %iv.ashr, 1 +; CHECK-NEXT: --> %iv.ashr.next U: [-512,0) S: [-512,0) Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: Determining loop execution counts for: @test_ashr_ones2 +; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. +; CHECK-NEXT: Loop %loop: Unpredictable max backedge-taken count. +; CHECK-NEXT: Loop %loop: Unpredictable predicated backedge-taken count. +; +entry: + br label %loop +loop: + %iv.ashr = phi i64 [%iv.ashr.next, %loop], [-1023, %entry] + %iv.ashr.next = ashr i64 %iv.ashr, 1 + br i1 undef, label %exit, label %loop +exit: + ret void +} + + +; negative case for when start is unknown +define void @test_ashr_unknown(i64 %start) { +; CHECK-LABEL: 'test_ashr_unknown' +; CHECK-NEXT: Classifying expressions for: @test_ashr_unknown +; CHECK-NEXT: %iv.ashr = phi i64 [ %start, %entry ], [ %iv.ashr.next, %loop ] +; CHECK-NEXT: --> %iv.ashr U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: %iv.ashr.next = ashr i64 %iv.ashr, 1 +; CHECK-NEXT: --> %iv.ashr.next U: [-4611686018427387904,4611686018427387904) S: [-4611686018427387904,4611686018427387904) Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: Determining loop execution counts for: @test_ashr_unknown +; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. +; CHECK-NEXT: Loop %loop: Unpredictable max backedge-taken count. +; CHECK-NEXT: Loop %loop: Unpredictable predicated backedge-taken count. +; +entry: + br label %loop +loop: + %iv.ashr = phi i64 [%start, %entry], [%iv.ashr.next, %loop] + %iv.ashr.next = ashr i64 %iv.ashr, 1 + br i1 undef, label %exit, label %loop +exit: + ret void +} + +; Negative case where we don't have a (shift) recurrence because the operands +; of the ashr are swapped. (This does end up being a divide recurrence.) +define void @test_ashr_wrong_op(i64 %start) { +; CHECK-LABEL: 'test_ashr_wrong_op' +; CHECK-NEXT: Classifying expressions for: @test_ashr_wrong_op +; CHECK-NEXT: %iv.ashr = phi i64 [ %start, %entry ], [ %iv.ashr.next, %loop ] +; CHECK-NEXT: --> %iv.ashr U: full-set S: full-set Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: %iv.ashr.next = ashr i64 1, %iv.ashr +; CHECK-NEXT: --> %iv.ashr.next U: [-2,2) S: [-2,2) Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: Determining loop execution counts for: @test_ashr_wrong_op +; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. +; CHECK-NEXT: Loop %loop: Unpredictable max backedge-taken count. +; CHECK-NEXT: Loop %loop: Unpredictable predicated backedge-taken count. +; +entry: + br label %loop +loop: + %iv.ashr = phi i64 [%start, %entry], [%iv.ashr.next, %loop] + %iv.ashr.next = ashr i64 1, %iv.ashr + br i1 undef, label %exit, label %loop +exit: + ret void +} + + +define void @test_shl() { +; CHECK-LABEL: 'test_shl' +; CHECK-NEXT: Classifying expressions for: @test_shl +; CHECK-NEXT: %iv.shl = phi i64 [ 8, %entry ], [ %iv.shl.next, %loop ] +; CHECK-NEXT: --> %iv.shl U: [0,-7) S: [-9223372036854775808,9223372036854775793) Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: %iv.shl.next = shl i64 %iv.shl, 1 +; CHECK-NEXT: --> (2 * %iv.shl) U: [0,-15) S: [-9223372036854775808,9223372036854775793) Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: Determining loop execution counts for: @test_shl +; CHECK-NEXT: Loop %loop: Unpredictable backedge-taken count. +; CHECK-NEXT: Loop %loop: Unpredictable max backedge-taken count. +; CHECK-NEXT: Loop %loop: Unpredictable predicated backedge-taken count. +; +entry: + br label %loop +loop: + %iv.shl = phi i64 [8, %entry], [%iv.shl.next, %loop] + %iv.shl.next = shl i64 %iv.shl, 1 + br i1 undef, label %exit, label %loop +exit: + ret void +} + +; use trip count to refine +define void @test_shl2() { +; CHECK-LABEL: 'test_shl2' +; CHECK-NEXT: Classifying expressions for: @test_shl2 +; 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 } +; CHECK-NEXT: %iv.shl = phi i64 [ 4, %entry ], [ %iv.shl.next, %loop ] +; CHECK-NEXT: --> %iv.shl U: [4,65) S: [4,65) Exits: 64 LoopDispositions: { %loop: Variant } +; CHECK-NEXT: %iv.next = add i64 %iv, 1 +; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: %iv.shl.next = shl i64 %iv.shl, 1 +; CHECK-NEXT: --> (2 * %iv.shl) U: [8,129) S: [8,129) Exits: 128 LoopDispositions: { %loop: Variant } +; CHECK-NEXT: Determining loop execution counts for: @test_shl2 +; CHECK-NEXT: Loop %loop: backedge-taken count is 4 +; CHECK-NEXT: Loop %loop: max backedge-taken count is 4 +; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is 4 +; CHECK-NEXT: Predicates: +; CHECK: Loop %loop: Trip multiple is 5 +; +entry: + br label %loop +loop: + %iv = phi i64 [0, %entry], [%iv.next, %loop] + %iv.shl = phi i64 [4, %entry], [%iv.shl.next, %loop] + %iv.next = add i64 %iv, 1 + %iv.shl.next = shl i64 %iv.shl, 1 + %cmp = icmp eq i64 %iv, 4 + br i1 %cmp, label %exit, label %loop +exit: + ret void +} + +; Variable shift with a tight upper bound +define void @test_shl3(i1 %c) { +; CHECK-LABEL: 'test_shl3' +; CHECK-NEXT: Classifying expressions for: @test_shl3 +; CHECK-NEXT: %shiftamt = select i1 %c, i64 1, i64 0 +; CHECK-NEXT: --> %shiftamt U: [0,2) S: [0,2) +; 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 } +; CHECK-NEXT: %iv.shl = phi i64 [ 4, %entry ], [ %iv.shl.next, %loop ] +; CHECK-NEXT: --> %iv.shl U: [4,65) S: [4,65) Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: %iv.next = add i64 %iv, 1 +; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,6) S: [1,6) Exits: 5 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: %iv.shl.next = shl i64 %iv.shl, %shiftamt +; CHECK-NEXT: --> %iv.shl.next U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: <> LoopDispositions: { %loop: Variant } +; CHECK-NEXT: Determining loop execution counts for: @test_shl3 +; CHECK-NEXT: Loop %loop: backedge-taken count is 4 +; CHECK-NEXT: Loop %loop: max backedge-taken count is 4 +; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is 4 +; CHECK-NEXT: Predicates: +; CHECK: Loop %loop: Trip multiple is 5 +; +entry: + %shiftamt = select i1 %c, i64 1, i64 0 + br label %loop +loop: + %iv = phi i64 [0, %entry], [%iv.next, %loop] + %iv.shl = phi i64 [4, %entry], [%iv.shl.next, %loop] + %iv.next = add i64 %iv, 1 + %iv.shl.next = shl i64 %iv.shl, %shiftamt + %cmp = icmp eq i64 %iv, 4 + br i1 %cmp, label %exit, label %loop +exit: + ret void +} + +; edge case on max value not overflowing +define void @test_shl4() { +; CHECK-LABEL: 'test_shl4' +; CHECK-NEXT: Classifying expressions for: @test_shl4 +; CHECK-NEXT: %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ] +; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,61) S: [0,61) Exits: 60 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: %iv.shl = phi i64 [ 4, %entry ], [ %iv.shl.next, %loop ] +; CHECK-NEXT: --> %iv.shl U: [4,4611686018427387905) S: [4,4611686018427387905) Exits: 4611686018427387904 LoopDispositions: { %loop: Variant } +; CHECK-NEXT: %iv.next = add i64 %iv, 1 +; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,62) S: [1,62) Exits: 61 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: %iv.shl.next = shl i64 %iv.shl, 1 +; CHECK-NEXT: --> (2 * %iv.shl) U: [8,-9223372036854775807) S: [-9223372036854775808,9223372036854775801) Exits: -9223372036854775808 LoopDispositions: { %loop: Variant } +; CHECK-NEXT: Determining loop execution counts for: @test_shl4 +; CHECK-NEXT: Loop %loop: backedge-taken count is 60 +; CHECK-NEXT: Loop %loop: max backedge-taken count is 60 +; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is 60 +; CHECK-NEXT: Predicates: +; CHECK: Loop %loop: Trip multiple is 61 +; +entry: + br label %loop +loop: + %iv = phi i64 [0, %entry], [%iv.next, %loop] + %iv.shl = phi i64 [4, %entry], [%iv.shl.next, %loop] + %iv.next = add i64 %iv, 1 + %iv.shl.next = shl i64 %iv.shl, 1 + %cmp = icmp eq i64 %iv, 60 + br i1 %cmp, label %exit, label %loop +exit: + ret void +} + +; other side of edge case from previous test +define void @test_shl5() { +; CHECK-LABEL: 'test_shl5' +; CHECK-NEXT: Classifying expressions for: @test_shl5 +; CHECK-NEXT: %iv = phi i64 [ 0, %entry ], [ %iv.next, %loop ] +; CHECK-NEXT: --> {0,+,1}<%loop> U: [0,62) S: [0,62) Exits: 61 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: %iv.shl = phi i64 [ 4, %entry ], [ %iv.shl.next, %loop ] +; CHECK-NEXT: --> %iv.shl U: [0,-3) S: [-9223372036854775808,9223372036854775801) Exits: -9223372036854775808 LoopDispositions: { %loop: Variant } +; CHECK-NEXT: %iv.next = add i64 %iv, 1 +; CHECK-NEXT: --> {1,+,1}<%loop> U: [1,63) S: [1,63) Exits: 62 LoopDispositions: { %loop: Computable } +; CHECK-NEXT: %iv.shl.next = shl i64 %iv.shl, 1 +; CHECK-NEXT: --> (2 * %iv.shl) U: [0,-7) S: [-9223372036854775808,9223372036854775801) Exits: 0 LoopDispositions: { %loop: Variant } +; CHECK-NEXT: Determining loop execution counts for: @test_shl5 +; CHECK-NEXT: Loop %loop: backedge-taken count is 61 +; CHECK-NEXT: Loop %loop: max backedge-taken count is 61 +; CHECK-NEXT: Loop %loop: Predicated backedge-taken count is 61 +; CHECK-NEXT: Predicates: +; CHECK: Loop %loop: Trip multiple is 62 +; +entry: + br label %loop +loop: + %iv = phi i64 [0, %entry], [%iv.next, %loop] + %iv.shl = phi i64 [4, %entry], [%iv.shl.next, %loop] + %iv.next = add i64 %iv, 1 + %iv.shl.next = shl i64 %iv.shl, 1 + %cmp = icmp eq i64 %iv, 61 + br i1 %cmp, label %exit, label %loop +exit: + ret void +}