This is an archive of the discontinued LLVM Phabricator instance.

Differential D154188

[IRCE] Implement runtime overflow check for computed range's end
ClosedPublic

Authored by aleksandr.popov on Jun 30 2023, 12:12 AM.

Details

Reviewers
skatkov
apilipenko
anna
DaniilSuchkov
mkazantsev
Commits
rGcdcefd2f9a2d: [IRCE] Implement runtime overflow check for computed range's end
Summary

Here is activated check elimination which was parsed previously in
https://reviews.llvm.org/D154069

  • Added runtime check that computed range's boundary doesn't overflow in

terms of range type.

  • From the statement INT_MIN <= END <= INT_MAX is inferred check:

isNonNegative(INT_MAX - END) * isNonNegative(END - INT_MIN).

  • If overflow happens, check will return 0 and the safe interval will be

empty.

Diff Detail

Event Timeline

aleksandr.popov created this revision.Jun 30 2023, 12:12 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 30 2023, 12:12 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
aleksandr.popov requested review of this revision.Jun 30 2023, 12:12 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 30 2023, 12:12 AM
Herald added a subscriber: llvm-commits. · View Herald Transcript
aleksandr.popov added a parent revision: D154069: [IRCE] Parse range checks in the form of "LHS - RHS vs Limit".Jun 30 2023, 12:12 AM
aleksandr.popov added a parent revision: D154062: [IRCE][Tests] Add tests with range checks in the form of 'iv + offset vs limit'.
Harbormaster completed remote builds in B242341: Diff 536126.Jun 30 2023, 12:13 AM
aleksandr.popov added reviewers: skatkov, apilipenko, anna, DaniilSuchkov, mkazantsev.Jun 30 2023, 12:26 AM
Herald added a subscriber: StephenFan. · View Herald TranscriptJun 30 2023, 12:26 AM
aleksandr.popov updated this revision to Diff 538051.Jul 7 2023, 2:59 AM
aleksandr.popov edited the summary of this revision. (Show Details)

Rebased

skatkov accepted this revision.Jul 7 2023, 3:18 AM
skatkov added inline comments.
llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
1741

bool NeedEndOverlowRuntimeCheck = EndType->getBitWidth() > RCType->getBitWidth();
if (NeedEndOverlowRuntimeCheck)

?

This revision is now accepted and ready to land.Jul 7 2023, 3:18 AM
Harbormaster completed remote builds in B243714: Diff 538051.Jul 7 2023, 4:00 AM
aleksandr.popov updated this revision to Diff 538221.Jul 7 2023, 11:52 AM

Refactored

Harbormaster completed remote builds in B243830: Diff 538221.Jul 7 2023, 2:14 PM
Closed by commit rGcdcefd2f9a2d: [IRCE] Implement runtime overflow check for computed range's end (authored by aleksandr.popov). · Explain WhyJul 12 2023, 2:20 AM
This revision was automatically updated to reflect the committed changes.
aleksandr.popov added a commit: rGcdcefd2f9a2d: [IRCE] Implement runtime overflow check for computed range's end.

Revision Contents

PathSize
llvm/
lib/
Transforms/
Scalar/
73 lines
test/
Transforms/
IRCE/
213 lines

Diff 539435

llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

Show First 20 Lines • Show All 1,732 Lines • ▼ Show 20 LinesInductiveRangeCheck::computeSafeIterationSpace(ScalarEvolution &SE,
auto *RCType = dyn_cast<IntegerType>(getBegin()->getType()); auto *RCType = dyn_cast<IntegerType>(getBegin()->getType());
auto *EndType = dyn_cast<IntegerType>(getEnd()->getType()); auto *EndType = dyn_cast<IntegerType>(getEnd()->getType());
// Do not work with pointer types. // Do not work with pointer types.
if (!IVType || !RCType) if (!IVType || !RCType)
return std::nullopt; return std::nullopt;
if (IVType->getBitWidth() > RCType->getBitWidth()) if (IVType->getBitWidth() > RCType->getBitWidth())
return std::nullopt; return std::nullopt;
auto PrintRangeCheck = [&](raw_ostream &OS) {
auto L = IndVar->getLoop();
OS << "irce: in function ";
OS << L->getHeader()->getParent()->getName();
OS << ", in ";
L->print(OS);
OS << "there is range check with scaled boundary:\n";
print(OS);
};
if (EndType->getBitWidth() > RCType->getBitWidth()) {
assert(EndType->getBitWidth() == RCType->getBitWidth() * 2);
if (PrintScaledBoundaryRangeChecks)
PrintRangeCheck(errs());
// End is computed with extended type but will be truncated to a narrow one
// type of range check. Therefore we need a check that the result will not
// overflow in terms of narrow type.
// TODO: Support runtime overflow check for End
return std::nullopt;
}
// IndVar is of the form "A + B * I" (where "I" is the canonical induction // IndVar is of the form "A + B * I" (where "I" is the canonical induction
skatkovUnsubmitted
Not Done
ReplyInline Actions

bool NeedEndOverlowRuntimeCheck = EndType->getBitWidth() > RCType->getBitWidth();
if (NeedEndOverlowRuntimeCheck)

?

skatkov: bool NeedEndOverlowRuntimeCheck = EndType->getBitWidth() > RCType->getBitWidth(); if…
// variable, that may or may not exist as a real llvm::Value in the loop) and // variable, that may or may not exist as a real llvm::Value in the loop) and
// this inductive range check is a range check on the "C + D * I" ("C" is // this inductive range check is a range check on the "C + D * I" ("C" is
// getBegin() and "D" is getStep()). We rewrite the value being range // getBegin() and "D" is getStep()). We rewrite the value being range
// checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA". // checked to "M + N * IndVar" where "N" = "D * B^(-1)" and "M" = "C - NA".
// //
// The actual inequalities we solve are of the form // The actual inequalities we solve are of the form
// //
// 0 <= M + 1 * IndVar < L given L >= 0 (i.e. N == 1) // 0 <= M + 1 * IndVar < L given L >= 0 (i.e. N == 1)
Show All 21 LinesInductiveRangeCheck::computeSafeIterationSpace(ScalarEvolution &SE,
const SCEV *C = getBegin(); const SCEV *C = getBegin();
const SCEVConstant *D = dyn_cast<SCEVConstant>(getStep()); const SCEVConstant *D = dyn_cast<SCEVConstant>(getStep());
if (D != B) if (D != B)
return std::nullopt; return std::nullopt;
assert(!D->getValue()->isZero() && "Recurrence with zero step?"); assert(!D->getValue()->isZero() && "Recurrence with zero step?");
unsigned BitWidth = RCType->getBitWidth(); unsigned BitWidth = RCType->getBitWidth();
const SCEV *SIntMax = SE.getConstant(APInt::getSignedMaxValue(BitWidth)); const SCEV *SIntMax = SE.getConstant(APInt::getSignedMaxValue(BitWidth));
const SCEV *SIntMin = SE.getConstant(APInt::getSignedMinValue(BitWidth));
// Subtract Y from X so that it does not go through border of the IV // Subtract Y from X so that it does not go through border of the IV
// iteration space. Mathematically, it is equivalent to: // iteration space. Mathematically, it is equivalent to:
// //
// ClampedSubtract(X, Y) = min(max(X - Y, INT_MIN), INT_MAX). [1] // ClampedSubtract(X, Y) = min(max(X - Y, INT_MIN), INT_MAX). [1]
// //
// In [1], 'X - Y' is a mathematical subtraction (result is not bounded to // In [1], 'X - Y' is a mathematical subtraction (result is not bounded to
// any width of bit grid). But after we take min/max, the result is // any width of bit grid). But after we take min/max, the result is
Show All 35 Lines if (IsLatchSigned) {
return SE.getMinusSCEV(X, SE.getSMinExpr(X, Y), SCEV::FlagNUW); return SE.getMinusSCEV(X, SE.getSMinExpr(X, Y), SCEV::FlagNUW);
}; };
const SCEV *M = SE.getMinusSCEV(C, A); const SCEV *M = SE.getMinusSCEV(C, A);
const SCEV *Zero = SE.getZero(M->getType()); const SCEV *Zero = SE.getZero(M->getType());
// This function returns SCEV equal to 1 if X is non-negative 0 otherwise. // This function returns SCEV equal to 1 if X is non-negative 0 otherwise.
auto SCEVCheckNonNegative = [&](const SCEV *X) { auto SCEVCheckNonNegative = [&](const SCEV *X) {
const Loop *L = IndVar->getLoop(); const Loop *L = IndVar->getLoop();
const SCEV *Zero = SE.getZero(X->getType());
const SCEV *One = SE.getOne(X->getType()); const SCEV *One = SE.getOne(X->getType());
// Can we trivially prove that X is a non-negative or negative value? // Can we trivially prove that X is a non-negative or negative value?
if (isKnownNonNegativeInLoop(X, L, SE)) if (isKnownNonNegativeInLoop(X, L, SE))
return One; return One;
else if (isKnownNegativeInLoop(X, L, SE)) else if (isKnownNegativeInLoop(X, L, SE))
return Zero; return Zero;
// If not, we will have to figure it out during the execution. // If not, we will have to figure it out during the execution.
// Function smax(smin(X, 0), -1) + 1 equals to 1 if X >= 0 and 0 if X < 0. // Function smax(smin(X, 0), -1) + 1 equals to 1 if X >= 0 and 0 if X < 0.
const SCEV *NegOne = SE.getNegativeSCEV(One); const SCEV *NegOne = SE.getNegativeSCEV(One);
return SE.getAddExpr(SE.getSMaxExpr(SE.getSMinExpr(X, Zero), NegOne), One); return SE.getAddExpr(SE.getSMaxExpr(SE.getSMinExpr(X, Zero), NegOne), One);
}; };
// This function returns SCEV equal to 1 if X will not overflow in terms of
// range check type, 0 otherwise.
auto SCEVCheckWillNotOverflow = [&](const SCEV *X) {
// X doesn't overflow if SINT_MAX >= X.
// Then if (SINT_MAX - X) >= 0, X doesn't overflow
const SCEV *SIntMaxExt = SE.getSignExtendExpr(SIntMax, X->getType());
const SCEV *OverflowCheck =
SCEVCheckNonNegative(SE.getMinusSCEV(SIntMaxExt, X));
// X doesn't underflow if X >= SINT_MIN.
// Then if (X - SINT_MIN) >= 0, X doesn't underflow
const SCEV *SIntMinExt = SE.getSignExtendExpr(SIntMin, X->getType());
const SCEV *UnderflowCheck =
SCEVCheckNonNegative(SE.getMinusSCEV(X, SIntMinExt));
return SE.getMulExpr(OverflowCheck, UnderflowCheck);
};
// FIXME: Current implementation of ClampedSubtract implicitly assumes that // FIXME: Current implementation of ClampedSubtract implicitly assumes that
// X is non-negative (in sense of a signed value). We need to re-implement // X is non-negative (in sense of a signed value). We need to re-implement
// this function in a way that it will correctly handle negative X as well. // this function in a way that it will correctly handle negative X as well.
// We use it twice: for X = 0 everything is fine, but for X = getEnd() we can // We use it twice: for X = 0 everything is fine, but for X = getEnd() we can
// end up with a negative X and produce wrong results. So currently we ensure // end up with a negative X and produce wrong results. So currently we ensure
// that if getEnd() is negative then both ends of the safe range are zero. // that if getEnd() is negative then both ends of the safe range are zero.
// Note that this may pessimize elimination of unsigned range checks against // Note that this may pessimize elimination of unsigned range checks against
// negative values. // negative values.
const SCEV *REnd = getEnd(); const SCEV *REnd = getEnd();
const SCEV *EndIsNonNegative = SCEVCheckNonNegative(REnd); const SCEV *EndWillNotOverflow = SE.getOne(RCType);
auto PrintRangeCheck = [&](raw_ostream &OS) {
auto L = IndVar->getLoop();
OS << "irce: in function ";
OS << L->getHeader()->getParent()->getName();
OS << ", in ";
L->print(OS);
OS << "there is range check with scaled boundary:\n";
print(OS);
};
if (EndType->getBitWidth() > RCType->getBitWidth()) {
assert(EndType->getBitWidth() == RCType->getBitWidth() * 2);
if (PrintScaledBoundaryRangeChecks)
PrintRangeCheck(errs());
// End is computed with extended type but will be truncated to a narrow one
// type of range check. Therefore we need a check that the result will not
// overflow in terms of narrow type.
EndWillNotOverflow =
SE.getTruncateExpr(SCEVCheckWillNotOverflow(REnd), RCType);
REnd = SE.getTruncateExpr(REnd, RCType);
}
const SCEV *RuntimeChecks =
SE.getMulExpr(SCEVCheckNonNegative(REnd), EndWillNotOverflow);
const SCEV *Begin = SE.getMulExpr(ClampedSubtract(Zero, M), RuntimeChecks);
const SCEV *End = SE.getMulExpr(ClampedSubtract(REnd, M), RuntimeChecks);
const SCEV *Begin = SE.getMulExpr(ClampedSubtract(Zero, M), EndIsNonNegative);
const SCEV *End = SE.getMulExpr(ClampedSubtract(REnd, M), EndIsNonNegative);
return InductiveRangeCheck::Range(Begin, End); return InductiveRangeCheck::Range(Begin, End);
} }
static std::optional<InductiveRangeCheck::Range> static std::optional<InductiveRangeCheck::Range>
IntersectSignedRange(ScalarEvolution &SE, IntersectSignedRange(ScalarEvolution &SE,
const std::optional<InductiveRangeCheck::Range> &R1, const std::optional<InductiveRangeCheck::Range> &R1,
const InductiveRangeCheck::Range &R2) { const InductiveRangeCheck::Range &R2) {
if (R2.isEmpty(SE, /* IsSigned */ true)) if (R2.isEmpty(SE, /* IsSigned */ true))
▲ Show 20 Lines • Show All 250 Lines • Show Last 20 Lines

llvm/test/Transforms/IRCE/iv-plus-offset-range-check.ll

Show All 16 Lines
; CHECK-NEXT: irce: in function test_overflow_check_runtime, in Loop at depth 1 containing: %loop<header><exiting>,%inbounds<latch><exiting> ; CHECK-NEXT: irce: in function test_overflow_check_runtime, in Loop at depth 1 containing: %loop<header><exiting>,%inbounds<latch><exiting>
; CHECK-NEXT: there is range check with scaled boundary: ; CHECK-NEXT: there is range check with scaled boundary:
; CHECK-NEXT: InductiveRangeCheck: ; CHECK-NEXT: InductiveRangeCheck:
; CHECK-NEXT: Begin: 0 Step: 1 End: (3 + (zext i8 %n to i16))<nuw><nsw> ; CHECK-NEXT: Begin: 0 Step: 1 End: (3 + (zext i8 %n to i16))<nuw><nsw>
; CHECK-NEXT: CheckUse: br i1 %check, label %inbounds, label %out_of_bounds Operand: 0 ; CHECK-NEXT: CheckUse: br i1 %check, label %inbounds, label %out_of_bounds Operand: 0
; IV = 0; IV <s limit; IV += 1; ; IV = 0; IV <s limit; IV += 1;
; Check(N - IV >= 2) ; Check(N - IV >= 2)
; TODO: IRCE is allowed. ; IRCE is allowed.
define i8 @test1(i8 %limit, i8 %n) { define i8 @test1(i8 %limit, i8 %n) {
; CHECK-LABEL: define i8 @test1 ; CHECK-LABEL: define i8 @test1
; CHECK-SAME: (i8 [[LIMIT:%.*]], i8 [[N:%.*]]) { ; CHECK-SAME: (i8 [[LIMIT:%.*]], i8 [[N:%.*]]) {
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0 ; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0
; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
; CHECK: loop.preheader: ; CHECK: loop.preheader:
; CHECK-NEXT: [[TMP0:%.*]] = add i8 [[N]], -1
; CHECK-NEXT: [[TMP1:%.*]] = add i8 [[N]], -128
; CHECK-NEXT: [[SMAX:%.*]] = call i8 @llvm.smax.i8(i8 [[TMP1]], i8 0)
; CHECK-NEXT: [[TMP2:%.*]] = sub i8 [[TMP0]], [[SMAX]]
; CHECK-NEXT: [[SMIN:%.*]] = call i8 @llvm.smin.i8(i8 [[TMP0]], i8 0)
; CHECK-NEXT: [[SMAX2:%.*]] = call i8 @llvm.smax.i8(i8 [[SMIN]], i8 -1)
; CHECK-NEXT: [[TMP3:%.*]] = add nsw i8 [[SMAX2]], 1
; CHECK-NEXT: [[TMP4:%.*]] = mul i8 [[TMP2]], [[TMP3]]
; CHECK-NEXT: [[TMP5:%.*]] = sext i8 [[N]] to i16
; CHECK-NEXT: [[TMP6:%.*]] = add nsw i16 [[TMP5]], 127
; CHECK-NEXT: [[SMIN3:%.*]] = call i16 @llvm.smin.i16(i16 [[TMP6]], i16 0)
; CHECK-NEXT: [[TMP7:%.*]] = trunc i16 [[SMIN3]] to i8
; CHECK-NEXT: [[TMP8:%.*]] = add nsw i8 [[TMP7]], 1
; CHECK-NEXT: [[TMP9:%.*]] = mul i8 [[TMP4]], [[TMP8]]
; CHECK-NEXT: [[SMIN4:%.*]] = call i8 @llvm.smin.i8(i8 [[LIMIT]], i8 [[TMP9]])
; CHECK-NEXT: [[EXIT_MAINLOOP_AT:%.*]] = call i8 @llvm.smax.i8(i8 [[SMIN4]], i8 0)
; CHECK-NEXT: [[TMP10:%.*]] = icmp slt i8 0, [[EXIT_MAINLOOP_AT]]
; CHECK-NEXT: br i1 [[TMP10]], label [[LOOP_PREHEADER7:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
; CHECK: loop.preheader7:
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] ; CHECK-NEXT: [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER7]] ]
; CHECK-NEXT: [[SUB:%.*]] = sub i8 [[N]], [[IDX]] ; CHECK-NEXT: [[SUB:%.*]] = sub i8 [[N]], [[IDX]]
; CHECK-NEXT: [[CHECK:%.*]] = icmp sge i8 [[SUB]], 2 ; CHECK-NEXT: [[CHECK:%.*]] = icmp sge i8 [[SUB]], 2
; CHECK-NEXT: br i1 [[CHECK]], label [[INBOUNDS]], label [[OUT_OF_BOUNDS:%.*]] ; CHECK-NEXT: br i1 true, label [[INBOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT8:%.*]]
; CHECK: inbounds: ; CHECK: inbounds:
; CHECK-NEXT: [[IDX_NEXT]] = add nuw i8 [[IDX]], 1 ; CHECK-NEXT: [[IDX_NEXT]] = add nuw i8 [[IDX]], 1
; CHECK-NEXT: [[CMP:%.*]] = icmp slt i8 [[IDX_NEXT]], [[LIMIT]] ; CHECK-NEXT: [[CMP:%.*]] = icmp slt i8 [[IDX_NEXT]], [[LIMIT]]
; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]] ; CHECK-NEXT: [[TMP11:%.*]] = icmp slt i8 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
; CHECK-NEXT: br i1 [[TMP11]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
; CHECK: main.exit.selector:
; CHECK-NEXT: [[IDX_NEXT_LCSSA:%.*]] = phi i8 [ [[IDX_NEXT]], [[INBOUNDS]] ]
; CHECK-NEXT: [[IDX_LCSSA6:%.*]] = phi i8 [ [[IDX]], [[INBOUNDS]] ]
; CHECK-NEXT: [[TMP12:%.*]] = icmp slt i8 [[IDX_NEXT_LCSSA]], [[LIMIT]]
; CHECK-NEXT: br i1 [[TMP12]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
; CHECK: main.pseudo.exit:
; CHECK-NEXT: [[IDX_COPY:%.*]] = phi i8 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
; CHECK-NEXT: [[INDVAR_END:%.*]] = phi i8 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
; CHECK-NEXT: br label [[POSTLOOP:%.*]]
; CHECK: exit.loopexit.loopexit:
; CHECK-NEXT: [[IDX_LCSSA1_PH:%.*]] = phi i8 [ [[IDX_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP:%.*]] ]
; CHECK-NEXT: br label [[EXIT_LOOPEXIT]]
; CHECK: exit.loopexit: ; CHECK: exit.loopexit:
; CHECK-NEXT: [[IDX_LCSSA1:%.*]] = phi i8 [ [[IDX]], [[INBOUNDS]] ] ; CHECK-NEXT: [[IDX_LCSSA1:%.*]] = phi i8 [ [[IDX_LCSSA6]], [[MAIN_EXIT_SELECTOR]] ], [ [[IDX_LCSSA1_PH]], [[EXIT_LOOPEXIT_LOOPEXIT:%.*]] ]
; CHECK-NEXT: br label [[EXIT]] ; CHECK-NEXT: br label [[EXIT]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: [[RES:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[IDX_LCSSA1]], [[EXIT_LOOPEXIT]] ] ; CHECK-NEXT: [[RES:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[IDX_LCSSA1]], [[EXIT_LOOPEXIT]] ]
; CHECK-NEXT: ret i8 [[RES]] ; CHECK-NEXT: ret i8 [[RES]]
; CHECK: out_of_bounds.loopexit:
; CHECK-NEXT: [[IDX_LCSSA_PH:%.*]] = phi i8 [ [[IDX_POSTLOOP]], [[LOOP_POSTLOOP:%.*]] ]
; CHECK-NEXT: br label [[OUT_OF_BOUNDS:%.*]]
; CHECK: out_of_bounds.loopexit8:
; CHECK-NEXT: [[IDX_LCSSA_PH9:%.*]] = phi i8 [ [[IDX]], [[LOOP]] ]
; CHECK-NEXT: br label [[OUT_OF_BOUNDS]]
; CHECK: out_of_bounds: ; CHECK: out_of_bounds:
; CHECK-NEXT: [[IDX_LCSSA:%.*]] = phi i8 [ [[IDX]], [[LOOP]] ] ; CHECK-NEXT: [[IDX_LCSSA:%.*]] = phi i8 [ [[IDX_LCSSA_PH]], [[OUT_OF_BOUNDS_LOOPEXIT:%.*]] ], [ [[IDX_LCSSA_PH9]], [[OUT_OF_BOUNDS_LOOPEXIT8]] ]
; CHECK-NEXT: ret i8 [[IDX_LCSSA]] ; CHECK-NEXT: ret i8 [[IDX_LCSSA]]
; CHECK: postloop:
; CHECK-NEXT: br label [[LOOP_POSTLOOP]]
; CHECK: loop.postloop:
; CHECK-NEXT: [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
; CHECK-NEXT: [[SUB_POSTLOOP:%.*]] = sub i8 [[N]], [[IDX_POSTLOOP]]
; CHECK-NEXT: [[CHECK_POSTLOOP:%.*]] = icmp sge i8 [[SUB_POSTLOOP]], 2
; CHECK-NEXT: br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]]
; CHECK: inbounds.postloop:
; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
; CHECK-NEXT: [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
; CHECK-NEXT: br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP0:![0-9]+]], !irce.loop.clone [[META5:![0-9]+]]
; ;
entry: entry:
%precheck = icmp sgt i8 %limit, 0 %precheck = icmp sgt i8 %limit, 0
br i1 %precheck, label %loop, label %exit br i1 %precheck, label %loop, label %exit
loop: loop:
%idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ] %idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ]
%sub = sub i8 %n, %idx %sub = sub i8 %n, %idx
Show All 16 Lines
; IV = 0; IV <s limit; IV += 1; ; IV = 0; IV <s limit; IV += 1;
; Check(N - IV >= 2) ; Check(N - IV >= 2)
; N is known to be non-negative. ; N is known to be non-negative.
; TODO: IRCE is allowed. ; TODO: IRCE is allowed.
define i8 @test1a(i8 %limit, ptr %p) { define i8 @test1a(i8 %limit, ptr %p) {
; CHECK-LABEL: define i8 @test1a ; CHECK-LABEL: define i8 @test1a
; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) { ; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG0:![0-9]+]] ; CHECK-NEXT: [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG6:![0-9]+]]
; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0 ; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0
; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
; CHECK: loop.preheader: ; CHECK: loop.preheader:
; CHECK-NEXT: [[TMP0:%.*]] = add nsw i8 [[N]], -1 ; CHECK-NEXT: [[TMP0:%.*]] = add nsw i8 [[N]], -1
; CHECK-NEXT: [[SMIN:%.*]] = call i8 @llvm.smin.i8(i8 [[TMP0]], i8 0) ; CHECK-NEXT: [[SMIN:%.*]] = call i8 @llvm.smin.i8(i8 [[TMP0]], i8 0)
; CHECK-NEXT: [[TMP1:%.*]] = add nsw i8 [[SMIN]], 1 ; CHECK-NEXT: [[TMP1:%.*]] = add nsw i8 [[SMIN]], 1
; CHECK-NEXT: [[TMP2:%.*]] = mul i8 [[TMP0]], [[TMP1]] ; CHECK-NEXT: [[TMP2:%.*]] = mul i8 [[TMP0]], [[TMP1]]
; CHECK-NEXT: [[SMIN2:%.*]] = call i8 @llvm.smin.i8(i8 [[LIMIT]], i8 [[TMP2]]) ; CHECK-NEXT: [[SMIN2:%.*]] = call i8 @llvm.smin.i8(i8 [[LIMIT]], i8 [[TMP2]])
▲ Show 20 Lines • Show All 44 Lines • ▼ Show 20 Lines
; CHECK: loop.postloop: ; CHECK: loop.postloop:
; CHECK-NEXT: [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ] ; CHECK-NEXT: [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
; CHECK-NEXT: [[SUB_POSTLOOP:%.*]] = sub i8 [[N]], [[IDX_POSTLOOP]] ; CHECK-NEXT: [[SUB_POSTLOOP:%.*]] = sub i8 [[N]], [[IDX_POSTLOOP]]
; CHECK-NEXT: [[CHECK_POSTLOOP:%.*]] = icmp sge i8 [[SUB_POSTLOOP]], 2 ; CHECK-NEXT: [[CHECK_POSTLOOP:%.*]] = icmp sge i8 [[SUB_POSTLOOP]], 2
; CHECK-NEXT: br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]] ; CHECK-NEXT: br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]]
; CHECK: inbounds.postloop: ; CHECK: inbounds.postloop:
; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1 ; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
; CHECK-NEXT: [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]] ; CHECK-NEXT: [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
; CHECK-NEXT: br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP1:![0-9]+]], !irce.loop.clone [[META6:![0-9]+]] ; CHECK-NEXT: br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP7:![0-9]+]], !irce.loop.clone [[META5]]
; ;
entry: entry:
%n = load i8, ptr %p, !range !0 %n = load i8, ptr %p, !range !0
%precheck = icmp sgt i8 %limit, 0 %precheck = icmp sgt i8 %limit, 0
br i1 %precheck, label %loop, label %exit br i1 %precheck, label %loop, label %exit
loop: loop:
%idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ] %idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ]
▲ Show 20 Lines • Show All 70 Lines • ▼ Show 20 Lines
; IV = 0; IV <s limit; IV += 1; ; IV = 0; IV <s limit; IV += 1;
; Check(IV - N <= -2) ; Check(IV - N <= -2)
; N is known to be non-negative. ; N is known to be non-negative.
; TODO: IRCE is allowed. ; TODO: IRCE is allowed.
define i8 @test2a(i8 %limit, ptr %p) { define i8 @test2a(i8 %limit, ptr %p) {
; CHECK-LABEL: define i8 @test2a ; CHECK-LABEL: define i8 @test2a
; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) { ; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG0]] ; CHECK-NEXT: [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG6]]
; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0 ; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0
; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
; CHECK: loop.preheader: ; CHECK: loop.preheader:
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] ; CHECK-NEXT: [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
; CHECK-NEXT: [[SUB:%.*]] = sub i8 [[IDX]], [[N]] ; CHECK-NEXT: [[SUB:%.*]] = sub i8 [[IDX]], [[N]]
; CHECK-NEXT: [[CHECK:%.*]] = icmp sle i8 [[SUB]], -2 ; CHECK-NEXT: [[CHECK:%.*]] = icmp sle i8 [[SUB]], -2
▲ Show 20 Lines • Show All 92 Lines • ▼ Show 20 Lines
; IV = 0; IV <s limit; IV += 1; ; IV = 0; IV <s limit; IV += 1;
; Check(IV + 2 <= N) ; Check(IV + 2 <= N)
; N is known to be non-negative. ; N is known to be non-negative.
; IRCE is allowed. ; IRCE is allowed.
define i8 @test3a(i8 %limit, ptr %p) { define i8 @test3a(i8 %limit, ptr %p) {
; CHECK-LABEL: define i8 @test3a ; CHECK-LABEL: define i8 @test3a
; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) { ; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG0]] ; CHECK-NEXT: [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG6]]
; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0 ; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0
; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
; CHECK: loop.preheader: ; CHECK: loop.preheader:
; CHECK-NEXT: [[TMP0:%.*]] = add nsw i8 [[N]], -1 ; CHECK-NEXT: [[TMP0:%.*]] = add nsw i8 [[N]], -1
; CHECK-NEXT: [[SMIN:%.*]] = call i8 @llvm.smin.i8(i8 [[LIMIT]], i8 [[TMP0]]) ; CHECK-NEXT: [[SMIN:%.*]] = call i8 @llvm.smin.i8(i8 [[LIMIT]], i8 [[TMP0]])
; CHECK-NEXT: [[EXIT_MAINLOOP_AT:%.*]] = call i8 @llvm.smax.i8(i8 [[SMIN]], i8 0) ; CHECK-NEXT: [[EXIT_MAINLOOP_AT:%.*]] = call i8 @llvm.smax.i8(i8 [[SMIN]], i8 0)
; CHECK-NEXT: [[TMP1:%.*]] = icmp slt i8 0, [[EXIT_MAINLOOP_AT]] ; CHECK-NEXT: [[TMP1:%.*]] = icmp slt i8 0, [[EXIT_MAINLOOP_AT]]
; CHECK-NEXT: br i1 [[TMP1]], label [[LOOP_PREHEADER3:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]] ; CHECK-NEXT: br i1 [[TMP1]], label [[LOOP_PREHEADER3:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
▲ Show 20 Lines • Show All 41 Lines • ▼ Show 20 Lines
; CHECK: loop.postloop: ; CHECK: loop.postloop:
; CHECK-NEXT: [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ] ; CHECK-NEXT: [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
; CHECK-NEXT: [[ADD_POSTLOOP:%.*]] = add i8 [[IDX_POSTLOOP]], 2 ; CHECK-NEXT: [[ADD_POSTLOOP:%.*]] = add i8 [[IDX_POSTLOOP]], 2
; CHECK-NEXT: [[CHECK_POSTLOOP:%.*]] = icmp sle i8 [[ADD_POSTLOOP]], [[N]] ; CHECK-NEXT: [[CHECK_POSTLOOP:%.*]] = icmp sle i8 [[ADD_POSTLOOP]], [[N]]
; CHECK-NEXT: br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]] ; CHECK-NEXT: br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]]
; CHECK: inbounds.postloop: ; CHECK: inbounds.postloop:
; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1 ; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
; CHECK-NEXT: [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]] ; CHECK-NEXT: [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
; CHECK-NEXT: br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP7:![0-9]+]], !irce.loop.clone [[META6]] ; CHECK-NEXT: br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP8:![0-9]+]], !irce.loop.clone [[META5]]
; ;
entry: entry:
%n = load i8, ptr %p, !range !0 %n = load i8, ptr %p, !range !0
%precheck = icmp sgt i8 %limit, 0 %precheck = icmp sgt i8 %limit, 0
br i1 %precheck, label %loop, label %exit br i1 %precheck, label %loop, label %exit
loop: loop:
%idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ] %idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ]
Show All 11 Linesexit:
ret i8 %res ret i8 %res
out_of_bounds: out_of_bounds:
ret i8 %idx; ret i8 %idx;
} }
; IV = 0; IV <s limit; IV += 1; ; IV = 0; IV <s limit; IV += 1;
; Check(N - IV > 2) ; Check(N - IV > 2)
; TODO: IRCE is allowed. ; IRCE is allowed.
define i8 @test4(i8 %limit, i8 %n) { define i8 @test4(i8 %limit, i8 %n) {
; CHECK-LABEL: define i8 @test4 ; CHECK-LABEL: define i8 @test4
; CHECK-SAME: (i8 [[LIMIT:%.*]], i8 [[N:%.*]]) { ; CHECK-SAME: (i8 [[LIMIT:%.*]], i8 [[N:%.*]]) {
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0 ; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0
; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
; CHECK: loop.preheader: ; CHECK: loop.preheader:
; CHECK-NEXT: [[TMP0:%.*]] = add i8 [[N]], -2
; CHECK-NEXT: [[TMP1:%.*]] = add i8 [[N]], 127
; CHECK-NEXT: [[SMAX:%.*]] = call i8 @llvm.smax.i8(i8 [[TMP1]], i8 0)
; CHECK-NEXT: [[TMP2:%.*]] = sub i8 [[TMP0]], [[SMAX]]
; CHECK-NEXT: [[SMIN:%.*]] = call i8 @llvm.smin.i8(i8 [[TMP0]], i8 0)
; CHECK-NEXT: [[SMAX2:%.*]] = call i8 @llvm.smax.i8(i8 [[SMIN]], i8 -1)
; CHECK-NEXT: [[TMP3:%.*]] = add nsw i8 [[SMAX2]], 1
; CHECK-NEXT: [[TMP4:%.*]] = mul i8 [[TMP2]], [[TMP3]]
; CHECK-NEXT: [[TMP5:%.*]] = sext i8 [[N]] to i16
; CHECK-NEXT: [[TMP6:%.*]] = add nsw i16 [[TMP5]], 126
; CHECK-NEXT: [[SMIN3:%.*]] = call i16 @llvm.smin.i16(i16 [[TMP6]], i16 0)
; CHECK-NEXT: [[SMAX4:%.*]] = call i16 @llvm.smax.i16(i16 [[SMIN3]], i16 -1)
; CHECK-NEXT: [[TMP7:%.*]] = trunc i16 [[SMAX4]] to i8
; CHECK-NEXT: [[TMP8:%.*]] = add nsw i8 [[TMP7]], 1
; CHECK-NEXT: [[TMP9:%.*]] = mul i8 [[TMP4]], [[TMP8]]
; CHECK-NEXT: [[SMIN5:%.*]] = call i8 @llvm.smin.i8(i8 [[LIMIT]], i8 [[TMP9]])
; CHECK-NEXT: [[EXIT_MAINLOOP_AT:%.*]] = call i8 @llvm.smax.i8(i8 [[SMIN5]], i8 0)
; CHECK-NEXT: [[TMP10:%.*]] = icmp slt i8 0, [[EXIT_MAINLOOP_AT]]
; CHECK-NEXT: br i1 [[TMP10]], label [[LOOP_PREHEADER8:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
; CHECK: loop.preheader8:
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] ; CHECK-NEXT: [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER8]] ]
; CHECK-NEXT: [[SUB:%.*]] = sub i8 [[N]], [[IDX]] ; CHECK-NEXT: [[SUB:%.*]] = sub i8 [[N]], [[IDX]]
; CHECK-NEXT: [[CHECK:%.*]] = icmp sgt i8 [[SUB]], 2 ; CHECK-NEXT: [[CHECK:%.*]] = icmp sgt i8 [[SUB]], 2
; CHECK-NEXT: br i1 [[CHECK]], label [[INBOUNDS]], label [[OUT_OF_BOUNDS:%.*]] ; CHECK-NEXT: br i1 true, label [[INBOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT9:%.*]]
; CHECK: inbounds: ; CHECK: inbounds:
; CHECK-NEXT: [[IDX_NEXT]] = add nuw i8 [[IDX]], 1 ; CHECK-NEXT: [[IDX_NEXT]] = add nuw i8 [[IDX]], 1
; CHECK-NEXT: [[CMP:%.*]] = icmp slt i8 [[IDX_NEXT]], [[LIMIT]] ; CHECK-NEXT: [[CMP:%.*]] = icmp slt i8 [[IDX_NEXT]], [[LIMIT]]
; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]] ; CHECK-NEXT: [[TMP11:%.*]] = icmp slt i8 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
; CHECK-NEXT: br i1 [[TMP11]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
; CHECK: main.exit.selector:
; CHECK-NEXT: [[IDX_NEXT_LCSSA:%.*]] = phi i8 [ [[IDX_NEXT]], [[INBOUNDS]] ]
; CHECK-NEXT: [[IDX_LCSSA7:%.*]] = phi i8 [ [[IDX]], [[INBOUNDS]] ]
; CHECK-NEXT: [[TMP12:%.*]] = icmp slt i8 [[IDX_NEXT_LCSSA]], [[LIMIT]]
; CHECK-NEXT: br i1 [[TMP12]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
; CHECK: main.pseudo.exit:
; CHECK-NEXT: [[IDX_COPY:%.*]] = phi i8 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
; CHECK-NEXT: [[INDVAR_END:%.*]] = phi i8 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
; CHECK-NEXT: br label [[POSTLOOP:%.*]]
; CHECK: exit.loopexit.loopexit:
; CHECK-NEXT: [[IDX_LCSSA1_PH:%.*]] = phi i8 [ [[IDX_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP:%.*]] ]
; CHECK-NEXT: br label [[EXIT_LOOPEXIT]]
; CHECK: exit.loopexit: ; CHECK: exit.loopexit:
; CHECK-NEXT: [[IDX_LCSSA1:%.*]] = phi i8 [ [[IDX]], [[INBOUNDS]] ] ; CHECK-NEXT: [[IDX_LCSSA1:%.*]] = phi i8 [ [[IDX_LCSSA7]], [[MAIN_EXIT_SELECTOR]] ], [ [[IDX_LCSSA1_PH]], [[EXIT_LOOPEXIT_LOOPEXIT:%.*]] ]
; CHECK-NEXT: br label [[EXIT]] ; CHECK-NEXT: br label [[EXIT]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: [[RES:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[IDX_LCSSA1]], [[EXIT_LOOPEXIT]] ] ; CHECK-NEXT: [[RES:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[IDX_LCSSA1]], [[EXIT_LOOPEXIT]] ]
; CHECK-NEXT: ret i8 [[RES]] ; CHECK-NEXT: ret i8 [[RES]]
; CHECK: out_of_bounds.loopexit:
; CHECK-NEXT: [[IDX_LCSSA_PH:%.*]] = phi i8 [ [[IDX_POSTLOOP]], [[LOOP_POSTLOOP:%.*]] ]
; CHECK-NEXT: br label [[OUT_OF_BOUNDS:%.*]]
; CHECK: out_of_bounds.loopexit9:
; CHECK-NEXT: [[IDX_LCSSA_PH10:%.*]] = phi i8 [ [[IDX]], [[LOOP]] ]
; CHECK-NEXT: br label [[OUT_OF_BOUNDS]]
; CHECK: out_of_bounds: ; CHECK: out_of_bounds:
; CHECK-NEXT: [[IDX_LCSSA:%.*]] = phi i8 [ [[IDX]], [[LOOP]] ] ; CHECK-NEXT: [[IDX_LCSSA:%.*]] = phi i8 [ [[IDX_LCSSA_PH]], [[OUT_OF_BOUNDS_LOOPEXIT:%.*]] ], [ [[IDX_LCSSA_PH10]], [[OUT_OF_BOUNDS_LOOPEXIT9]] ]
; CHECK-NEXT: ret i8 [[IDX_LCSSA]] ; CHECK-NEXT: ret i8 [[IDX_LCSSA]]
; CHECK: postloop:
; CHECK-NEXT: br label [[LOOP_POSTLOOP]]
; CHECK: loop.postloop:
; CHECK-NEXT: [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
; CHECK-NEXT: [[SUB_POSTLOOP:%.*]] = sub i8 [[N]], [[IDX_POSTLOOP]]
; CHECK-NEXT: [[CHECK_POSTLOOP:%.*]] = icmp sgt i8 [[SUB_POSTLOOP]], 2
; CHECK-NEXT: br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]]
; CHECK: inbounds.postloop:
; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
; CHECK-NEXT: [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
; CHECK-NEXT: br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP9:![0-9]+]], !irce.loop.clone [[META5]]
; ;
entry: entry:
%precheck = icmp sgt i8 %limit, 0 %precheck = icmp sgt i8 %limit, 0
br i1 %precheck, label %loop, label %exit br i1 %precheck, label %loop, label %exit
loop: loop:
%idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ] %idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ]
%sub = sub i8 %n, %idx %sub = sub i8 %n, %idx
Show All 16 Lines
; IV = 0; IV <s limit; IV += 1; ; IV = 0; IV <s limit; IV += 1;
; Check(N - IV > 2) ; Check(N - IV > 2)
; N is known to be non-negative. ; N is known to be non-negative.
; TODO: IRCE is allowed. ; TODO: IRCE is allowed.
define i8 @test4a(i8 %limit, ptr %p) { define i8 @test4a(i8 %limit, ptr %p) {
; CHECK-LABEL: define i8 @test4a ; CHECK-LABEL: define i8 @test4a
; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) { ; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG0]] ; CHECK-NEXT: [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG6]]
; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0 ; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0
; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
; CHECK: loop.preheader: ; CHECK: loop.preheader:
; CHECK-NEXT: [[TMP0:%.*]] = add i8 [[N]], -2 ; CHECK-NEXT: [[TMP0:%.*]] = add i8 [[N]], -2
; CHECK-NEXT: [[TMP1:%.*]] = add nuw i8 [[N]], 127 ; CHECK-NEXT: [[TMP1:%.*]] = add nuw i8 [[N]], 127
; CHECK-NEXT: [[SMAX:%.*]] = call i8 @llvm.smax.i8(i8 [[TMP1]], i8 0) ; CHECK-NEXT: [[SMAX:%.*]] = call i8 @llvm.smax.i8(i8 [[TMP1]], i8 0)
; CHECK-NEXT: [[TMP2:%.*]] = sub i8 [[TMP0]], [[SMAX]] ; CHECK-NEXT: [[TMP2:%.*]] = sub i8 [[TMP0]], [[SMAX]]
; CHECK-NEXT: [[TMP3:%.*]] = add nsw i8 [[N]], -2 ; CHECK-NEXT: [[TMP3:%.*]] = add nsw i8 [[N]], -2
▲ Show 20 Lines • Show All 49 Lines • ▼ Show 20 Lines
; CHECK: loop.postloop: ; CHECK: loop.postloop:
; CHECK-NEXT: [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ] ; CHECK-NEXT: [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
; CHECK-NEXT: [[SUB_POSTLOOP:%.*]] = sub i8 [[N]], [[IDX_POSTLOOP]] ; CHECK-NEXT: [[SUB_POSTLOOP:%.*]] = sub i8 [[N]], [[IDX_POSTLOOP]]
; CHECK-NEXT: [[CHECK_POSTLOOP:%.*]] = icmp sgt i8 [[SUB_POSTLOOP]], 2 ; CHECK-NEXT: [[CHECK_POSTLOOP:%.*]] = icmp sgt i8 [[SUB_POSTLOOP]], 2
; CHECK-NEXT: br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]] ; CHECK-NEXT: br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]]
; CHECK: inbounds.postloop: ; CHECK: inbounds.postloop:
; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1 ; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
; CHECK-NEXT: [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]] ; CHECK-NEXT: [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
; CHECK-NEXT: br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP8:![0-9]+]], !irce.loop.clone [[META6]] ; CHECK-NEXT: br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP10:![0-9]+]], !irce.loop.clone [[META5]]
; ;
entry: entry:
%n = load i8, ptr %p, !range !0 %n = load i8, ptr %p, !range !0
%precheck = icmp sgt i8 %limit, 0 %precheck = icmp sgt i8 %limit, 0
br i1 %precheck, label %loop, label %exit br i1 %precheck, label %loop, label %exit
loop: loop:
%idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ] %idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ]
▲ Show 20 Lines • Show All 70 Lines • ▼ Show 20 Lines
; IV = 0; IV <s limit; IV += 1; ; IV = 0; IV <s limit; IV += 1;
; Check(IV - N < -2) ; Check(IV - N < -2)
; N is known to be non-negative. ; N is known to be non-negative.
; TODO: IRCE is allowed. ; TODO: IRCE is allowed.
define i8 @test5a(i8 %limit, ptr %p) { define i8 @test5a(i8 %limit, ptr %p) {
; CHECK-LABEL: define i8 @test5a ; CHECK-LABEL: define i8 @test5a
; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) { ; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG0]] ; CHECK-NEXT: [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG6]]
; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0 ; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0
; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
; CHECK: loop.preheader: ; CHECK: loop.preheader:
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] ; CHECK-NEXT: [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
; CHECK-NEXT: [[SUB:%.*]] = sub i8 [[IDX]], [[N]] ; CHECK-NEXT: [[SUB:%.*]] = sub i8 [[IDX]], [[N]]
; CHECK-NEXT: [[CHECK:%.*]] = icmp slt i8 [[SUB]], -2 ; CHECK-NEXT: [[CHECK:%.*]] = icmp slt i8 [[SUB]], -2
▲ Show 20 Lines • Show All 101 Lines • ▼ Show 20 Lines
; CHECK: loop.postloop: ; CHECK: loop.postloop:
; CHECK-NEXT: [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ] ; CHECK-NEXT: [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
; CHECK-NEXT: [[ADD_POSTLOOP:%.*]] = add i8 [[IDX_POSTLOOP]], 2 ; CHECK-NEXT: [[ADD_POSTLOOP:%.*]] = add i8 [[IDX_POSTLOOP]], 2
; CHECK-NEXT: [[CHECK_POSTLOOP:%.*]] = icmp slt i8 [[ADD_POSTLOOP]], [[N]] ; CHECK-NEXT: [[CHECK_POSTLOOP:%.*]] = icmp slt i8 [[ADD_POSTLOOP]], [[N]]
; CHECK-NEXT: br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]] ; CHECK-NEXT: br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]]
; CHECK: inbounds.postloop: ; CHECK: inbounds.postloop:
; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1 ; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
; CHECK-NEXT: [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]] ; CHECK-NEXT: [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
; CHECK-NEXT: br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP9:![0-9]+]], !irce.loop.clone [[META6]] ; CHECK-NEXT: br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP11:![0-9]+]], !irce.loop.clone [[META5]]
; ;
entry: entry:
%precheck = icmp sgt i8 %limit, 0 %precheck = icmp sgt i8 %limit, 0
br i1 %precheck, label %loop, label %exit br i1 %precheck, label %loop, label %exit
loop: loop:
%idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ] %idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ]
%add = add i8 %idx, 2 %add = add i8 %idx, 2
Show All 16 Lines
; IV = 0; IV <s limit; IV += 1; ; IV = 0; IV <s limit; IV += 1;
; Check(IV + 2 < N) ; Check(IV + 2 < N)
; N is known to be non-negative. ; N is known to be non-negative.
; IRCE is allowed. ; IRCE is allowed.
define i8 @test6a(i8 %limit, ptr %p) { define i8 @test6a(i8 %limit, ptr %p) {
; CHECK-LABEL: define i8 @test6a ; CHECK-LABEL: define i8 @test6a
; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) { ; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG0]] ; CHECK-NEXT: [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG6]]
; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0 ; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0
; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
; CHECK: loop.preheader: ; CHECK: loop.preheader:
; CHECK-NEXT: [[TMP0:%.*]] = add nsw i8 [[N]], -2 ; CHECK-NEXT: [[TMP0:%.*]] = add nsw i8 [[N]], -2
; CHECK-NEXT: [[SMIN:%.*]] = call i8 @llvm.smin.i8(i8 [[LIMIT]], i8 [[TMP0]]) ; CHECK-NEXT: [[SMIN:%.*]] = call i8 @llvm.smin.i8(i8 [[LIMIT]], i8 [[TMP0]])
; CHECK-NEXT: [[EXIT_MAINLOOP_AT:%.*]] = call i8 @llvm.smax.i8(i8 [[SMIN]], i8 0) ; CHECK-NEXT: [[EXIT_MAINLOOP_AT:%.*]] = call i8 @llvm.smax.i8(i8 [[SMIN]], i8 0)
; CHECK-NEXT: [[TMP1:%.*]] = icmp slt i8 0, [[EXIT_MAINLOOP_AT]] ; CHECK-NEXT: [[TMP1:%.*]] = icmp slt i8 0, [[EXIT_MAINLOOP_AT]]
; CHECK-NEXT: br i1 [[TMP1]], label [[LOOP_PREHEADER3:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]] ; CHECK-NEXT: br i1 [[TMP1]], label [[LOOP_PREHEADER3:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
▲ Show 20 Lines • Show All 41 Lines • ▼ Show 20 Lines
; CHECK: loop.postloop: ; CHECK: loop.postloop:
; CHECK-NEXT: [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ] ; CHECK-NEXT: [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
; CHECK-NEXT: [[ADD_POSTLOOP:%.*]] = add i8 [[IDX_POSTLOOP]], 2 ; CHECK-NEXT: [[ADD_POSTLOOP:%.*]] = add i8 [[IDX_POSTLOOP]], 2
; CHECK-NEXT: [[CHECK_POSTLOOP:%.*]] = icmp slt i8 [[ADD_POSTLOOP]], [[N]] ; CHECK-NEXT: [[CHECK_POSTLOOP:%.*]] = icmp slt i8 [[ADD_POSTLOOP]], [[N]]
; CHECK-NEXT: br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]] ; CHECK-NEXT: br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]]
; CHECK: inbounds.postloop: ; CHECK: inbounds.postloop:
; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1 ; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
; CHECK-NEXT: [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]] ; CHECK-NEXT: [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
; CHECK-NEXT: br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP10:![0-9]+]], !irce.loop.clone [[META6]] ; CHECK-NEXT: br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP12:![0-9]+]], !irce.loop.clone [[META5]]
; ;
entry: entry:
%n = load i8, ptr %p, !range !0 %n = load i8, ptr %p, !range !0
%precheck = icmp sgt i8 %limit, 0 %precheck = icmp sgt i8 %limit, 0
br i1 %precheck, label %loop, label %exit br i1 %precheck, label %loop, label %exit
loop: loop:
%idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ] %idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ]
Show All 19 Lines
; ;
; IRCE is allowed. ; IRCE is allowed.
; IRCE will reassociate this range check to the 'IV < N + 2', ; IRCE will reassociate this range check to the 'IV < N + 2',
; since N < 126 no-overflow fact is provable at compile time. ; since N < 126 no-overflow fact is provable at compile time.
define i8 @test_overflow_check_compile_time(i8 %limit, ptr %p) { define i8 @test_overflow_check_compile_time(i8 %limit, ptr %p) {
; CHECK-LABEL: define i8 @test_overflow_check_compile_time ; CHECK-LABEL: define i8 @test_overflow_check_compile_time
; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) { ; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG11:![0-9]+]] ; CHECK-NEXT: [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG13:![0-9]+]]
; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0 ; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0
; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
; CHECK: loop.preheader: ; CHECK: loop.preheader:
; CHECK-NEXT: [[TMP0:%.*]] = add nuw nsw i8 [[N]], 2 ; CHECK-NEXT: [[TMP0:%.*]] = add nuw nsw i8 [[N]], 2
; CHECK-NEXT: [[SMIN:%.*]] = call i8 @llvm.smin.i8(i8 [[LIMIT]], i8 [[TMP0]]) ; CHECK-NEXT: [[SMIN:%.*]] = call i8 @llvm.smin.i8(i8 [[LIMIT]], i8 [[TMP0]])
; CHECK-NEXT: [[EXIT_MAINLOOP_AT:%.*]] = call i8 @llvm.smax.i8(i8 [[SMIN]], i8 0) ; CHECK-NEXT: [[EXIT_MAINLOOP_AT:%.*]] = call i8 @llvm.smax.i8(i8 [[SMIN]], i8 0)
; CHECK-NEXT: [[TMP1:%.*]] = icmp slt i8 0, [[EXIT_MAINLOOP_AT]] ; CHECK-NEXT: [[TMP1:%.*]] = icmp slt i8 0, [[EXIT_MAINLOOP_AT]]
; CHECK-NEXT: br i1 [[TMP1]], label [[LOOP_PREHEADER3:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]] ; CHECK-NEXT: br i1 [[TMP1]], label [[LOOP_PREHEADER3:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
▲ Show 20 Lines • Show All 41 Lines • ▼ Show 20 Lines
; CHECK: loop.postloop: ; CHECK: loop.postloop:
; CHECK-NEXT: [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ] ; CHECK-NEXT: [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
; CHECK-NEXT: [[SUB_POSTLOOP:%.*]] = sub i8 [[N]], [[IDX_POSTLOOP]] ; CHECK-NEXT: [[SUB_POSTLOOP:%.*]] = sub i8 [[N]], [[IDX_POSTLOOP]]
; CHECK-NEXT: [[CHECK_POSTLOOP:%.*]] = icmp sgt i8 [[SUB_POSTLOOP]], -2 ; CHECK-NEXT: [[CHECK_POSTLOOP:%.*]] = icmp sgt i8 [[SUB_POSTLOOP]], -2
; CHECK-NEXT: br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]] ; CHECK-NEXT: br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]]
; CHECK: inbounds.postloop: ; CHECK: inbounds.postloop:
; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1 ; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
; CHECK-NEXT: [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]] ; CHECK-NEXT: [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
; CHECK-NEXT: br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP12:![0-9]+]], !irce.loop.clone [[META6]] ; CHECK-NEXT: br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP14:![0-9]+]], !irce.loop.clone [[META5]]
; ;
entry: entry:
%n = load i8, ptr %p, !range !1 %n = load i8, ptr %p, !range !1
%precheck = icmp sgt i8 %limit, 0 %precheck = icmp sgt i8 %limit, 0
br i1 %precheck, label %loop, label %exit br i1 %precheck, label %loop, label %exit
loop: loop:
%idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ] %idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ]
Show All 12 Lines
out_of_bounds: out_of_bounds:
ret i8 %idx; ret i8 %idx;
} }
; IV = 0; IV <s limit; IV += 1; ; IV = 0; IV <s limit; IV += 1;
; Check(N - IV >= -2) ; Check(N - IV >= -2)
; ;
; TODO: IRCE is allowed. ; IRCE is allowed.
; IRCE will reassociate this range check to the 'IV < (N + 2) + 1', ; IRCE will reassociate this range check to the 'IV < (N + 2) + 1',
; since N < 126 no-overflow fact is NOT provable at compile time and ; since N < 126 no-overflow fact is NOT provable at compile time and
; runtime overflow check is required. ; runtime overflow check is required.
define i8 @test_overflow_check_runtime(i8 %limit, ptr %p) { define i8 @test_overflow_check_runtime(i8 %limit, ptr %p) {
; CHECK-LABEL: define i8 @test_overflow_check_runtime ; CHECK-LABEL: define i8 @test_overflow_check_runtime
; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) { ; CHECK-SAME: (i8 [[LIMIT:%.*]], ptr [[P:%.*]]) {
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG11]] ; CHECK-NEXT: [[N:%.*]] = load i8, ptr [[P]], align 1, !range [[RNG13]]
; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0 ; CHECK-NEXT: [[PRECHECK:%.*]] = icmp sgt i8 [[LIMIT]], 0
; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[PRECHECK]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
; CHECK: loop.preheader: ; CHECK: loop.preheader:
; CHECK-NEXT: [[TMP0:%.*]] = add i8 [[N]], 3
; CHECK-NEXT: [[TMP1:%.*]] = add nsw i8 [[N]], -124
; CHECK-NEXT: [[SMAX:%.*]] = call i8 @llvm.smax.i8(i8 [[TMP1]], i8 0)
; CHECK-NEXT: [[TMP2:%.*]] = sub i8 [[TMP0]], [[SMAX]]
; CHECK-NEXT: [[TMP3:%.*]] = add nuw i8 [[N]], 3
; CHECK-NEXT: [[SMIN:%.*]] = call i8 @llvm.smin.i8(i8 [[TMP3]], i8 0)
; CHECK-NEXT: [[SMAX2:%.*]] = call i8 @llvm.smax.i8(i8 [[SMIN]], i8 -1)
; CHECK-NEXT: [[TMP4:%.*]] = add nsw i8 [[SMAX2]], 1
; CHECK-NEXT: [[TMP5:%.*]] = mul i8 [[TMP2]], [[TMP4]]
; CHECK-NEXT: [[TMP6:%.*]] = zext i8 [[N]] to i16
; CHECK-NEXT: [[TMP7:%.*]] = sub i16 124, [[TMP6]]
; CHECK-NEXT: [[SMIN3:%.*]] = call i16 @llvm.smin.i16(i16 [[TMP7]], i16 0)
; CHECK-NEXT: [[TMP8:%.*]] = trunc i16 [[SMIN3]] to i8
; CHECK-NEXT: [[TMP9:%.*]] = add nsw i8 [[TMP8]], 1
; CHECK-NEXT: [[TMP10:%.*]] = mul i8 [[TMP5]], [[TMP9]]
; CHECK-NEXT: [[SMIN4:%.*]] = call i8 @llvm.smin.i8(i8 [[LIMIT]], i8 [[TMP10]])
; CHECK-NEXT: [[EXIT_MAINLOOP_AT:%.*]] = call i8 @llvm.smax.i8(i8 [[SMIN4]], i8 0)
; CHECK-NEXT: [[TMP11:%.*]] = icmp slt i8 0, [[EXIT_MAINLOOP_AT]]
; CHECK-NEXT: br i1 [[TMP11]], label [[LOOP_PREHEADER7:%.*]], label [[MAIN_PSEUDO_EXIT:%.*]]
; CHECK: loop.preheader7:
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] ; CHECK-NEXT: [[IDX:%.*]] = phi i8 [ [[IDX_NEXT:%.*]], [[INBOUNDS:%.*]] ], [ 0, [[LOOP_PREHEADER7]] ]
; CHECK-NEXT: [[SUB:%.*]] = sub i8 [[N]], [[IDX]] ; CHECK-NEXT: [[SUB:%.*]] = sub i8 [[N]], [[IDX]]
; CHECK-NEXT: [[CHECK:%.*]] = icmp sge i8 [[SUB]], -2 ; CHECK-NEXT: [[CHECK:%.*]] = icmp sge i8 [[SUB]], -2
; CHECK-NEXT: br i1 [[CHECK]], label [[INBOUNDS]], label [[OUT_OF_BOUNDS:%.*]] ; CHECK-NEXT: br i1 true, label [[INBOUNDS]], label [[OUT_OF_BOUNDS_LOOPEXIT8:%.*]]
; CHECK: inbounds: ; CHECK: inbounds:
; CHECK-NEXT: [[IDX_NEXT]] = add nuw i8 [[IDX]], 1 ; CHECK-NEXT: [[IDX_NEXT]] = add nuw i8 [[IDX]], 1
; CHECK-NEXT: [[CMP:%.*]] = icmp slt i8 [[IDX_NEXT]], [[LIMIT]] ; CHECK-NEXT: [[CMP:%.*]] = icmp slt i8 [[IDX_NEXT]], [[LIMIT]]
; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT_LOOPEXIT:%.*]] ; CHECK-NEXT: [[TMP12:%.*]] = icmp slt i8 [[IDX_NEXT]], [[EXIT_MAINLOOP_AT]]
; CHECK-NEXT: br i1 [[TMP12]], label [[LOOP]], label [[MAIN_EXIT_SELECTOR:%.*]]
; CHECK: main.exit.selector:
; CHECK-NEXT: [[IDX_NEXT_LCSSA:%.*]] = phi i8 [ [[IDX_NEXT]], [[INBOUNDS]] ]
; CHECK-NEXT: [[IDX_LCSSA6:%.*]] = phi i8 [ [[IDX]], [[INBOUNDS]] ]
; CHECK-NEXT: [[TMP13:%.*]] = icmp slt i8 [[IDX_NEXT_LCSSA]], [[LIMIT]]
; CHECK-NEXT: br i1 [[TMP13]], label [[MAIN_PSEUDO_EXIT]], label [[EXIT_LOOPEXIT:%.*]]
; CHECK: main.pseudo.exit:
; CHECK-NEXT: [[IDX_COPY:%.*]] = phi i8 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
; CHECK-NEXT: [[INDVAR_END:%.*]] = phi i8 [ 0, [[LOOP_PREHEADER]] ], [ [[IDX_NEXT_LCSSA]], [[MAIN_EXIT_SELECTOR]] ]
; CHECK-NEXT: br label [[POSTLOOP:%.*]]
; CHECK: exit.loopexit.loopexit:
; CHECK-NEXT: [[IDX_LCSSA1_PH:%.*]] = phi i8 [ [[IDX_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP:%.*]] ]
; CHECK-NEXT: br label [[EXIT_LOOPEXIT]]
; CHECK: exit.loopexit: ; CHECK: exit.loopexit:
; CHECK-NEXT: [[IDX_LCSSA1:%.*]] = phi i8 [ [[IDX]], [[INBOUNDS]] ] ; CHECK-NEXT: [[IDX_LCSSA1:%.*]] = phi i8 [ [[IDX_LCSSA6]], [[MAIN_EXIT_SELECTOR]] ], [ [[IDX_LCSSA1_PH]], [[EXIT_LOOPEXIT_LOOPEXIT:%.*]] ]
; CHECK-NEXT: br label [[EXIT]] ; CHECK-NEXT: br label [[EXIT]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: [[RES:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[IDX_LCSSA1]], [[EXIT_LOOPEXIT]] ] ; CHECK-NEXT: [[RES:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[IDX_LCSSA1]], [[EXIT_LOOPEXIT]] ]
; CHECK-NEXT: ret i8 [[RES]] ; CHECK-NEXT: ret i8 [[RES]]
; CHECK: out_of_bounds.loopexit:
; CHECK-NEXT: [[IDX_LCSSA_PH:%.*]] = phi i8 [ [[IDX_POSTLOOP]], [[LOOP_POSTLOOP:%.*]] ]
; CHECK-NEXT: br label [[OUT_OF_BOUNDS:%.*]]
; CHECK: out_of_bounds.loopexit8:
; CHECK-NEXT: [[IDX_LCSSA_PH9:%.*]] = phi i8 [ [[IDX]], [[LOOP]] ]
; CHECK-NEXT: br label [[OUT_OF_BOUNDS]]
; CHECK: out_of_bounds: ; CHECK: out_of_bounds:
; CHECK-NEXT: [[IDX_LCSSA:%.*]] = phi i8 [ [[IDX]], [[LOOP]] ] ; CHECK-NEXT: [[IDX_LCSSA:%.*]] = phi i8 [ [[IDX_LCSSA_PH]], [[OUT_OF_BOUNDS_LOOPEXIT:%.*]] ], [ [[IDX_LCSSA_PH9]], [[OUT_OF_BOUNDS_LOOPEXIT8]] ]
; CHECK-NEXT: ret i8 [[IDX_LCSSA]] ; CHECK-NEXT: ret i8 [[IDX_LCSSA]]
; CHECK: postloop:
; CHECK-NEXT: br label [[LOOP_POSTLOOP]]
; CHECK: loop.postloop:
; CHECK-NEXT: [[IDX_POSTLOOP]] = phi i8 [ [[IDX_NEXT_POSTLOOP:%.*]], [[INBOUNDS_POSTLOOP]] ], [ [[IDX_COPY]], [[POSTLOOP]] ]
; CHECK-NEXT: [[SUB_POSTLOOP:%.*]] = sub i8 [[N]], [[IDX_POSTLOOP]]
; CHECK-NEXT: [[CHECK_POSTLOOP:%.*]] = icmp sge i8 [[SUB_POSTLOOP]], -2
; CHECK-NEXT: br i1 [[CHECK_POSTLOOP]], label [[INBOUNDS_POSTLOOP]], label [[OUT_OF_BOUNDS_LOOPEXIT]]
; CHECK: inbounds.postloop:
; CHECK-NEXT: [[IDX_NEXT_POSTLOOP]] = add nuw i8 [[IDX_POSTLOOP]], 1
; CHECK-NEXT: [[CMP_POSTLOOP:%.*]] = icmp slt i8 [[IDX_NEXT_POSTLOOP]], [[LIMIT]]
; CHECK-NEXT: br i1 [[CMP_POSTLOOP]], label [[LOOP_POSTLOOP]], label [[EXIT_LOOPEXIT_LOOPEXIT]], !llvm.loop [[LOOP15:![0-9]+]], !irce.loop.clone [[META5]]
; ;
entry: entry:
%n = load i8, ptr %p, !range !1 %n = load i8, ptr %p, !range !1
%precheck = icmp sgt i8 %limit, 0 %precheck = icmp sgt i8 %limit, 0
br i1 %precheck, label %loop, label %exit br i1 %precheck, label %loop, label %exit
loop: loop:
%idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ] %idx = phi i8 [ %idx.next, %inbounds ], [ 0, %entry ]
Show All 19 Lines