This is an archive of the discontinued LLVM Phabricator instance.

Differential D148618

[SCEV] Support sub in and negative constants willNotOverflow
ClosedPublic

Authored by mkazantsev on Apr 18 2023, 1:51 AM.

Details

Reviewers
nikic
fhahn
reames
dmakogon
lebedev.ri
skatkov
Commits
rGab07cbe4377a: [SCEV] Support sub in and negative constants willNotOverflow
Summary

This lifts two TODOs from this function, allowing us to prove
no-overflow whether it happens through max int (up) or through
min int (down) for both and and sub.

Diff Detail

Event Timeline

mkazantsev created this revision.Apr 18 2023, 1:51 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 18 2023, 1:51 AM
Herald added subscribers: StephenFan, hiraditya. · View Herald Transcript
mkazantsev requested review of this revision.Apr 18 2023, 1:51 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 18 2023, 1:51 AM
Herald added a subscriber: llvm-commits. · View Herald Transcript
mkazantsev added a child revision: D148621: [SCEV] Support negative constant in willNotOverflow.Apr 18 2023, 2:27 AM
Harbormaster completed remote builds in B226332: Diff 514565.Apr 18 2023, 2:48 AM
mkazantsev planned changes to this revision.Apr 18 2023, 8:41 AM

Internal testing found a bug, investigating.

mkazantsev added a comment.Apr 18 2023, 8:42 AM

Ah ok, it is only legal for signed.

mkazantsev updated this revision to Diff 514873.Apr 19 2023, 2:45 AM
mkazantsev retitled this revision from [SCEV] Support sub in willNotOverflow to [SCEV] Support sub in and negative constants willNotOverflow.
mkazantsev edited the summary of this revision. (Show Details)

Bug fixed, logic expanded.

mkazantsev added a child revision: D148097: [Test] Synergetic test update.Apr 19 2023, 2:46 AM
mkazantsev removed a child revision: D148621: [SCEV] Support negative constant in willNotOverflow.
Harbormaster completed remote builds in B226552: Diff 514873.Apr 19 2023, 3:47 AM
mkazantsev mentioned this in D148322: [SCEV] Infer NSW when subtracting expressions with the same signs.Apr 21 2023, 1:53 AM
mkazantsev added a reviewer: skatkov.Apr 23 2023, 10:20 PM
dmakogon accepted this revision.Apr 25 2023, 12:16 AM

LGTM

This revision is now accepted and ready to land.Apr 25 2023, 12:16 AM
dmakogon added inline comments.Apr 25 2023, 12:54 AM
llvm/lib/Analysis/ScalarEvolution.cpp
2372

You don't need this else after return

mkazantsev added inline comments.Apr 25 2023, 2:30 AM
llvm/lib/Analysis/ScalarEvolution.cpp
2372

Indeed.

mkazantsev added inline comments.Apr 25 2023, 2:40 AM
llvm/lib/Analysis/ScalarEvolution.cpp
2372

I just want to keep it that way because it is so perfectly aligned one under one.

This revision was landed with ongoing or failed builds.Apr 25 2023, 3:08 AM
Closed by commit rGab07cbe4377a: [SCEV] Support sub in and negative constants willNotOverflow (authored by mkazantsev). · Explain Why
This revision was automatically updated to reflect the committed changes.
mkazantsev added a commit: rGab07cbe4377a: [SCEV] Support sub in and negative constants willNotOverflow.

Revision Contents

PathSize
llvm/
lib/
Analysis/
39 lines
test/
Transforms/
IndVarSimplify/
24 lines

Diff 516728

llvm/lib/Analysis/ScalarEvolution.cpp

  • This file is larger than 256 KB, so syntax highlighting is disabled by default.
Show First 20 Lines • Show All 2,334 Lines • ▼ Show 20 Linesbool ScalarEvolution::willNotOverflow(Instruction::BinaryOps BinOp, bool Signed,
const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0); const SCEV *LHSB = (this->*Extension)(LHS, WideTy, 0);
const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0); const SCEV *RHSB = (this->*Extension)(RHS, WideTy, 0);
const SCEV *B = (this->*Operation)(LHSB, RHSB, SCEV::FlagAnyWrap, 0); const SCEV *B = (this->*Operation)(LHSB, RHSB, SCEV::FlagAnyWrap, 0);
if (A == B) if (A == B)
return true; return true;
// Can we use context to prove the fact we need? // Can we use context to prove the fact we need?
if (!CtxI) if (!CtxI)
return false; return false;
// We can prove that add(x, constant) doesn't wrap if isKnownPredicateAt can // TODO: Support mul.
// guarantee that x <= max_int - constant at the given context. if (BinOp == Instruction::Mul)
// TODO: Support other operations.
if (BinOp != Instruction::Add)
return false; return false;
auto *RHSC = dyn_cast<SCEVConstant>(RHS); auto *RHSC = dyn_cast<SCEVConstant>(RHS);
// TODO: Lift this limitation. // TODO: Lift this limitation.
if (!RHSC) if (!RHSC)
return false; return false;
APInt C = RHSC->getAPInt(); APInt C = RHSC->getAPInt();
// TODO: Also lift this limitation.
if (Signed && C.isNegative())
return false;
unsigned NumBits = C.getBitWidth(); unsigned NumBits = C.getBitWidth();
APInt Max = bool IsSub = (BinOp == Instruction::Sub);
Signed ? APInt::getSignedMaxValue(NumBits) : APInt::getMaxValue(NumBits); bool IsNegativeConst = (Signed && C.isNegative());
APInt Limit = Max - C; // Compute the direction and magnitude by which we need to check overflow.
bool OverflowDown = IsSub ^ IsNegativeConst;
APInt Magnitude = C;
if (IsNegativeConst) {
if (C == APInt::getSignedMinValue(NumBits))
// TODO: SINT_MIN on inversion gives the same negative value, we don't
// want to deal with that.
return false;
Magnitude = -C;
}
ICmpInst::Predicate Pred = Signed ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE; ICmpInst::Predicate Pred = Signed ? ICmpInst::ICMP_SLE : ICmpInst::ICMP_ULE;
if (OverflowDown) {
// To avoid overflow down, we need to make sure that MIN + Magnitude <= LHS.
APInt Min = Signed ? APInt::getSignedMinValue(NumBits)
: APInt::getMinValue(NumBits);
APInt Limit = Min + Magnitude;
return isKnownPredicateAt(Pred, getConstant(Limit), LHS, CtxI);
} else {
dmakogonUnsubmitted
Not Done
ReplyInline Actions

You don't need this else after return

dmakogon: You don't need this `else` after return
mkazantsevAuthorUnsubmitted
Done
ReplyInline Actions

Indeed.

mkazantsev: Indeed.
mkazantsevAuthorUnsubmitted
Done
ReplyInline Actions

I just want to keep it that way because it is so perfectly aligned one under one.

mkazantsev: I just want to keep it that way because it is so perfectly aligned one under one.
// To avoid overflow up, we need to make sure that LHS <= MAX - Magnitude.
APInt Max = Signed ? APInt::getSignedMaxValue(NumBits)
: APInt::getMaxValue(NumBits);
APInt Limit = Max - Magnitude;
return isKnownPredicateAt(Pred, LHS, getConstant(Limit), CtxI); return isKnownPredicateAt(Pred, LHS, getConstant(Limit), CtxI);
} }
}
std::optional<SCEV::NoWrapFlags> std::optional<SCEV::NoWrapFlags>
ScalarEvolution::getStrengthenedNoWrapFlagsFromBinOp( ScalarEvolution::getStrengthenedNoWrapFlagsFromBinOp(
const OverflowingBinaryOperator *OBO) { const OverflowingBinaryOperator *OBO) {
// It cannot be done any better. // It cannot be done any better.
if (OBO->hasNoUnsignedWrap() && OBO->hasNoSignedWrap()) if (OBO->hasNoUnsignedWrap() && OBO->hasNoSignedWrap())
return std::nullopt; return std::nullopt;
▲ Show 20 Lines • Show All 13,035 Lines • Show Last 20 Lines

llvm/test/Transforms/IndVarSimplify/predicated_ranges.ll

Show All 13 Lines
; CHECK-NEXT: preheader: ; CHECK-NEXT: preheader:
; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, !range [[RNG0:![0-9]+]] ; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, !range [[RNG0:![0-9]+]]
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0 ; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]] ; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
; CHECK: range_check_block: ; CHECK: range_check_block:
; CHECK-NEXT: [[IV_NEXT]] = sub i32 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = sub nuw nsw i32 [[IV]], 1
; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]] ; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
; CHECK: backedge: ; CHECK: backedge:
; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]] ; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4 ; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4
; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0 ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0
; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]] ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: ret void ; CHECK-NEXT: ret void
Show All 32 Lines
; CHECK-NEXT: preheader: ; CHECK-NEXT: preheader:
; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, !range [[RNG0]] ; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, !range [[RNG0]]
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0 ; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]] ; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
; CHECK: range_check_block: ; CHECK: range_check_block:
; CHECK-NEXT: [[IV_NEXT]] = sub i32 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = sub nuw nsw i32 [[IV]], 1
; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]] ; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
; CHECK: backedge: ; CHECK: backedge:
; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]] ; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4 ; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4
; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0 ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0
; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]] ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: ret void ; CHECK-NEXT: ret void
▲ Show 20 Lines • Show All 392 Lines • ▼ Show 20 Lines
; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[LEN]], -1 ; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[LEN]], -1
; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN]] ; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN]]
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0 ; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]] ; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
; CHECK: range_check_block: ; CHECK: range_check_block:
; CHECK-NEXT: [[IV_NEXT]] = sub i32 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = sub nuw i32 [[IV]], 1
; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[BACKEDGE]], label [[FAIL:%.*]] ; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[BACKEDGE]], label [[FAIL:%.*]]
; CHECK: backedge: ; CHECK: backedge:
; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]] ; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4 ; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4
; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0 ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0
; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]] ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: ret void ; CHECK-NEXT: ret void
Show All 34 Lines
; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[LEN]], -1 ; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[LEN]], -1
; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN]] ; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN]]
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0 ; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]] ; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
; CHECK: range_check_block: ; CHECK: range_check_block:
; CHECK-NEXT: [[IV_NEXT]] = sub i32 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = sub nuw i32 [[IV]], 1
; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[FAIL:%.*]], label [[BACKEDGE]] ; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[FAIL:%.*]], label [[BACKEDGE]]
; CHECK: backedge: ; CHECK: backedge:
; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]] ; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4 ; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4
; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0 ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0
; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]] ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: ret void ; CHECK-NEXT: ret void
Show All 33 Lines
; CHECK-NEXT: preheader: ; CHECK-NEXT: preheader:
; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4 ; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[LEN]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0 ; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]] ; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
; CHECK: range_check_block: ; CHECK: range_check_block:
; CHECK-NEXT: [[IV_NEXT]] = sub i32 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = sub nuw i32 [[IV]], 1
; CHECK-NEXT: [[RANGE_CHECK:%.*]] = icmp slt i32 [[IV_NEXT]], [[LEN]] ; CHECK-NEXT: [[RANGE_CHECK:%.*]] = icmp slt i32 [[IV_NEXT]], [[LEN]]
; CHECK-NEXT: br i1 [[RANGE_CHECK]], label [[BACKEDGE]], label [[FAIL:%.*]] ; CHECK-NEXT: br i1 [[RANGE_CHECK]], label [[BACKEDGE]], label [[FAIL:%.*]]
; CHECK: backedge: ; CHECK: backedge:
; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]] ; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4 ; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4
; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0 ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0
; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]] ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]]
; CHECK: exit: ; CHECK: exit:
Show All 36 Lines
; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[LEN]], -1 ; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[LEN]], -1
; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN]] ; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN]]
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[START]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[START]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i64 [[IV]], 0 ; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i64 [[IV]], 0
; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]] ; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
; CHECK: range_check_block: ; CHECK: range_check_block:
; CHECK-NEXT: [[IV_NEXT]] = sub nsw i64 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = sub nuw nsw i64 [[IV]], 1
; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[BACKEDGE]], label [[FAIL:%.*]] ; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[BACKEDGE]], label [[FAIL:%.*]]
; CHECK: backedge: ; CHECK: backedge:
; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i64 [[IV]] ; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i64 [[IV]]
; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4 ; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4
; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0 ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0
; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]] ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: ret void ; CHECK-NEXT: ret void
Show All 37 Lines
; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[LEN]], -1 ; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[LEN]], -1
; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN]] ; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN]]
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[START]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[START]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i64 [[IV]], 0 ; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i64 [[IV]], 0
; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]] ; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
; CHECK: range_check_block: ; CHECK: range_check_block:
; CHECK-NEXT: [[IV_NEXT]] = sub nsw i64 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = sub nuw nsw i64 [[IV]], 1
; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[FAIL:%.*]], label [[BACKEDGE]] ; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[FAIL:%.*]], label [[BACKEDGE]]
; CHECK: backedge: ; CHECK: backedge:
; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i64 [[IV]] ; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i64 [[IV]]
; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4 ; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4
; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0 ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0
; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]] ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: ret void ; CHECK-NEXT: ret void
Show All 34 Lines
; CHECK-NEXT: preheader: ; CHECK-NEXT: preheader:
; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4 ; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[START:%.*]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[START:%.*]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i64 [[IV]], 0 ; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i64 [[IV]], 0
; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]] ; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
; CHECK: range_check_block: ; CHECK: range_check_block:
; CHECK-NEXT: [[IV_NEXT]] = sub i64 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = sub nuw i64 [[IV]], 1
; CHECK-NEXT: [[NARROW:%.*]] = trunc i64 [[IV_NEXT]] to i32 ; CHECK-NEXT: [[NARROW:%.*]] = trunc i64 [[IV_NEXT]] to i32
; CHECK-NEXT: [[RANGE_CHECK:%.*]] = icmp ult i32 [[NARROW]], [[LEN]] ; CHECK-NEXT: [[RANGE_CHECK:%.*]] = icmp ult i32 [[NARROW]], [[LEN]]
; CHECK-NEXT: br i1 [[RANGE_CHECK]], label [[BACKEDGE]], label [[FAIL:%.*]] ; CHECK-NEXT: br i1 [[RANGE_CHECK]], label [[BACKEDGE]], label [[FAIL:%.*]]
; CHECK: backedge: ; CHECK: backedge:
; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i64 [[IV]] ; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i64 [[IV]]
; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4 ; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4
; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0 ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0
; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]] ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]]
Show All 35 Lines
; CHECK-NEXT: preheader: ; CHECK-NEXT: preheader:
; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4 ; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[START:%.*]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i64 [ [[START:%.*]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i64 [[IV]], 0 ; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i64 [[IV]], 0
; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]] ; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
; CHECK: range_check_block: ; CHECK: range_check_block:
; CHECK-NEXT: [[IV_NEXT]] = sub i64 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = sub nuw i64 [[IV]], 1
; CHECK-NEXT: [[NARROW:%.*]] = trunc i64 [[IV_NEXT]] to i32 ; CHECK-NEXT: [[NARROW:%.*]] = trunc i64 [[IV_NEXT]] to i32
; CHECK-NEXT: [[RANGE_CHECK:%.*]] = icmp uge i32 [[NARROW]], [[LEN]] ; CHECK-NEXT: [[RANGE_CHECK:%.*]] = icmp uge i32 [[NARROW]], [[LEN]]
; CHECK-NEXT: br i1 [[RANGE_CHECK]], label [[FAIL:%.*]], label [[BACKEDGE]] ; CHECK-NEXT: br i1 [[RANGE_CHECK]], label [[FAIL:%.*]], label [[BACKEDGE]]
; CHECK: backedge: ; CHECK: backedge:
; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i64 [[IV]] ; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[ARR:%.*]], i64 [[IV]]
; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4 ; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4
; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0 ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0
; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]] ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]]
Show All 37 Lines
; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[START:%.*]], -1 ; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[START:%.*]], -1
; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN]] ; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp ult i32 [[TMP0]], [[LEN]]
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0 ; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]] ; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
; CHECK: range_check_block: ; CHECK: range_check_block:
; CHECK-NEXT: [[IV_NEXT]] = sub i32 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = sub nuw i32 [[IV]], 1
; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[BACKEDGE]], label [[FAIL:%.*]] ; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[BACKEDGE]], label [[FAIL:%.*]]
; CHECK: backedge: ; CHECK: backedge:
; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]] ; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4 ; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4
; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0 ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0
; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]] ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: ret void ; CHECK-NEXT: ret void
Show All 34 Lines
; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[START:%.*]], -1 ; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[START:%.*]], -1
; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN]] ; CHECK-NEXT: [[RANGE_CHECK_FIRST_ITER:%.*]] = icmp uge i32 [[TMP0]], [[LEN]]
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0 ; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]] ; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
; CHECK: range_check_block: ; CHECK: range_check_block:
; CHECK-NEXT: [[IV_NEXT]] = sub i32 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = sub nuw i32 [[IV]], 1
; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[FAIL:%.*]], label [[BACKEDGE]] ; CHECK-NEXT: br i1 [[RANGE_CHECK_FIRST_ITER]], label [[FAIL:%.*]], label [[BACKEDGE]]
; CHECK: backedge: ; CHECK: backedge:
; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]] ; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4 ; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4
; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0 ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0
; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]] ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: ret void ; CHECK-NEXT: ret void
Show All 33 Lines
; CHECK-NEXT: preheader: ; CHECK-NEXT: preheader:
; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4 ; CHECK-NEXT: [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START:%.*]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[START:%.*]], [[PREHEADER:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0 ; CHECK-NEXT: [[ZERO_COND:%.*]] = icmp eq i32 [[IV]], 0
; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]] ; CHECK-NEXT: br i1 [[ZERO_COND]], label [[EXIT:%.*]], label [[RANGE_CHECK_BLOCK:%.*]]
; CHECK: range_check_block: ; CHECK: range_check_block:
; CHECK-NEXT: [[IV_NEXT]] = sub i32 [[IV]], 1 ; CHECK-NEXT: [[IV_NEXT]] = sub nuw i32 [[IV]], 1
; CHECK-NEXT: [[RANGE_CHECK:%.*]] = icmp slt i32 [[IV_NEXT]], [[LEN]] ; CHECK-NEXT: [[RANGE_CHECK:%.*]] = icmp slt i32 [[IV_NEXT]], [[LEN]]
; CHECK-NEXT: br i1 [[RANGE_CHECK]], label [[BACKEDGE]], label [[FAIL:%.*]] ; CHECK-NEXT: br i1 [[RANGE_CHECK]], label [[BACKEDGE]], label [[FAIL:%.*]]
; CHECK: backedge: ; CHECK: backedge:
; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]] ; CHECK-NEXT: [[EL_PTR:%.*]] = getelementptr i32, ptr [[P]], i32 [[IV]]
; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4 ; CHECK-NEXT: [[EL:%.*]] = load i32, ptr [[EL_PTR]], align 4
; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0 ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp eq i32 [[EL]], 0
; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]] ; CHECK-NEXT: br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT]]
; CHECK: exit: ; CHECK: exit:
Show All 32 Lines