This is an archive of the discontinued LLVM Phabricator instance.

Differential D148098

[SCEV] Apply loop guards in willNotOverflow with context
Changes PlannedPublic

Authored by mkazantsev on Apr 12 2023, 2:57 AM.

Details

Reviewers
nikic
lebedev.ri
fhahn
reames
skatkov
Summary

This allows us to support more cases when facts are known from dominating guards.

Diff Detail

Unit TestsFailed

TimeTest
90 msx64 debian > LLVM.Transforms/LoopUnroll/ARM::multi-blocks.ll

Event Timeline

mkazantsev created this revision.Apr 12 2023, 2:57 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 12 2023, 2:57 AM
Herald added subscribers: StephenFan, asbirlea, hiraditya. · View Herald Transcript
mkazantsev requested review of this revision.Apr 12 2023, 2:57 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 12 2023, 2:57 AM
Herald added a subscriber: llvm-commits. · View Herald Transcript
mkazantsev added a parent revision: D148097: [Test] Synergetic test update.Apr 12 2023, 2:57 AM
Harbormaster completed remote builds in B224990: Diff 512733.Apr 12 2023, 4:50 AM
mkazantsev planned changes to this revision.Apr 18 2023, 2:39 AM

Per underlying patches changes, this no longer works. I'll see if I can refresh it.

Revision Contents

PathSize
llvm/
lib/
Analysis/
2 lines
test/
Transforms/
LICM/
18 lines

Diff 512733

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;
if (auto *L = LI.getLoopFor(CtxI->getParent()))
B = applyLoopGuards(B, L);
// If result of operation in wide type is between narrow min/max extended to // If result of operation in wide type is between narrow min/max extended to
// wide type, it means that the computation was without overflow. // wide type, it means that the computation was without overflow.
const SCEV *NarrowMin = const SCEV *NarrowMin =
getConstant(Signed ? APInt::getSignedMinValue(NarrowTy->getBitWidth()) getConstant(Signed ? APInt::getSignedMinValue(NarrowTy->getBitWidth())
: APInt::getMinValue(NarrowTy->getBitWidth())); : APInt::getMinValue(NarrowTy->getBitWidth()));
const SCEV *NarrowMax = const SCEV *NarrowMax =
getConstant(Signed ? APInt::getSignedMaxValue(NarrowTy->getBitWidth()) getConstant(Signed ? APInt::getSignedMaxValue(NarrowTy->getBitWidth())
: APInt::getMaxValue(NarrowTy->getBitWidth())); : APInt::getMaxValue(NarrowTy->getBitWidth()));
▲ Show 20 Lines • Show All 13,077 Lines • Show Last 20 Lines

llvm/test/Transforms/LICM/hoist-add-sub.ll

Show First 20 Lines • Show All 209 Lines • ▼ Show 20 Lines
exit: exit:
ret i32 %iv.next ret i32 %iv.next
out_of_bounds: out_of_bounds:
ret i32 -1 ret i32 -1
} }
; TODO: x + iv < 4 ==> iv < 4 - x ; x + iv < 4 ==> iv < 4 - x
define i32 @test_02a(ptr %p, ptr %x_p, ptr %length_p) { define i32 @test_02a(ptr %p, ptr %x_p, ptr %length_p) {
; CHECK-LABEL: define i32 @test_02a ; CHECK-LABEL: define i32 @test_02a
; CHECK-SAME: (ptr [[P:%.*]], ptr [[X_P:%.*]], ptr [[LENGTH_P:%.*]]) { ; CHECK-SAME: (ptr [[P:%.*]], ptr [[X_P:%.*]], ptr [[LENGTH_P:%.*]]) {
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[X:%.*]] = load i32, ptr [[X_P]], align 4 ; CHECK-NEXT: [[X:%.*]] = load i32, ptr [[X_P]], align 4
; CHECK-NEXT: [[LENGTH:%.*]] = load i32, ptr [[LENGTH_P]], align 4 ; CHECK-NEXT: [[LENGTH:%.*]] = load i32, ptr [[LENGTH_P]], align 4
; CHECK-NEXT: [[PRECOND_1:%.*]] = icmp sge i32 [[X]], 0 ; CHECK-NEXT: [[PRECOND_1:%.*]] = icmp sge i32 [[X]], 0
; CHECK-NEXT: [[PRECOND_2:%.*]] = icmp sge i32 [[LENGTH]], 0 ; CHECK-NEXT: [[PRECOND_2:%.*]] = icmp sge i32 [[LENGTH]], 0
; CHECK-NEXT: [[PRECOND:%.*]] = and i1 [[PRECOND_1]], [[PRECOND_2]] ; CHECK-NEXT: [[PRECOND:%.*]] = and i1 [[PRECOND_1]], [[PRECOND_2]]
; CHECK-NEXT: br i1 [[PRECOND]], label [[LOOP_PREHEADER:%.*]], label [[FAILED:%.*]] ; CHECK-NEXT: br i1 [[PRECOND]], label [[LOOP_PREHEADER:%.*]], label [[FAILED:%.*]]
; CHECK: loop.preheader: ; CHECK: loop.preheader:
; CHECK-NEXT: [[INVARIANT_OP:%.*]] = sub nsw i32 4, [[X]]
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
; CHECK-NEXT: [[ARITH:%.*]] = add nsw i32 [[X]], [[IV]] ; CHECK-NEXT: [[X_CHECK:%.*]] = icmp slt i32 [[IV]], [[INVARIANT_OP]]
; CHECK-NEXT: [[X_CHECK:%.*]] = icmp slt i32 [[ARITH]], 4
; CHECK-NEXT: br i1 [[X_CHECK]], label [[OUT_OF_BOUNDS:%.*]], label [[BACKEDGE]] ; CHECK-NEXT: br i1 [[X_CHECK]], label [[OUT_OF_BOUNDS:%.*]], 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: store i32 1, ptr [[EL_PTR]], align 4 ; CHECK-NEXT: store i32 1, ptr [[EL_PTR]], align 4
; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4 ; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4
; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]] ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]]
; 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 20 Lines • Show All 80 Lines • ▼ Show 20 Lines
exit: exit:
ret i32 %iv.next ret i32 %iv.next
out_of_bounds: out_of_bounds:
ret i32 -1 ret i32 -1
} }
; TODO: iv - x < 4 ==> iv < 4 + x ; iv - x < 4 ==> iv < 4 + x
define i32 @test_03a(ptr %p, ptr %x_p, ptr %length_p) { define i32 @test_03a(ptr %p, ptr %x_p, ptr %length_p) {
; CHECK-LABEL: define i32 @test_03a ; CHECK-LABEL: define i32 @test_03a
; CHECK-SAME: (ptr [[P:%.*]], ptr [[X_P:%.*]], ptr [[LENGTH_P:%.*]]) { ; CHECK-SAME: (ptr [[P:%.*]], ptr [[X_P:%.*]], ptr [[LENGTH_P:%.*]]) {
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[X:%.*]] = load i32, ptr [[X_P]], align 4 ; CHECK-NEXT: [[X:%.*]] = load i32, ptr [[X_P]], align 4
; CHECK-NEXT: [[LENGTH:%.*]] = load i32, ptr [[LENGTH_P]], align 4 ; CHECK-NEXT: [[LENGTH:%.*]] = load i32, ptr [[LENGTH_P]], align 4
; CHECK-NEXT: [[PRECOND_1:%.*]] = icmp ult i32 [[X]], 2147483640 ; CHECK-NEXT: [[PRECOND_1:%.*]] = icmp ult i32 [[X]], 2147483640
; CHECK-NEXT: [[PRECOND_2:%.*]] = icmp sge i32 [[LENGTH]], 0 ; CHECK-NEXT: [[PRECOND_2:%.*]] = icmp sge i32 [[LENGTH]], 0
; CHECK-NEXT: [[PRECOND:%.*]] = and i1 [[PRECOND_1]], [[PRECOND_2]] ; CHECK-NEXT: [[PRECOND:%.*]] = and i1 [[PRECOND_1]], [[PRECOND_2]]
; CHECK-NEXT: br i1 [[PRECOND]], label [[LOOP_PREHEADER:%.*]], label [[FAILED:%.*]] ; CHECK-NEXT: br i1 [[PRECOND]], label [[LOOP_PREHEADER:%.*]], label [[FAILED:%.*]]
; CHECK: loop.preheader: ; CHECK: loop.preheader:
; CHECK-NEXT: [[INVARIANT_OP:%.*]] = add nsw i32 4, [[X]]
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
; CHECK-NEXT: [[ARITH:%.*]] = sub nsw i32 [[IV]], [[X]] ; CHECK-NEXT: [[X_CHECK:%.*]] = icmp slt i32 [[IV]], [[INVARIANT_OP]]
; CHECK-NEXT: [[X_CHECK:%.*]] = icmp slt i32 [[ARITH]], 4
; CHECK-NEXT: br i1 [[X_CHECK]], label [[OUT_OF_BOUNDS:%.*]], label [[BACKEDGE]] ; CHECK-NEXT: br i1 [[X_CHECK]], label [[OUT_OF_BOUNDS:%.*]], 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: store i32 1, ptr [[EL_PTR]], align 4 ; CHECK-NEXT: store i32 1, ptr [[EL_PTR]], align 4
; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4 ; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4
; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]] ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]]
; 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 20 Lines • Show All 80 Lines • ▼ Show 20 Lines
exit: exit:
ret i32 %iv.next ret i32 %iv.next
out_of_bounds: out_of_bounds:
ret i32 -1 ret i32 -1
} }
; TODO: iv + x < 4 ==> iv < 4 - x ; iv + x < 4 ==> iv < 4 - x
define i32 @test_04a(ptr %p, ptr %x_p, ptr %length_p) { define i32 @test_04a(ptr %p, ptr %x_p, ptr %length_p) {
; CHECK-LABEL: define i32 @test_04a ; CHECK-LABEL: define i32 @test_04a
; CHECK-SAME: (ptr [[P:%.*]], ptr [[X_P:%.*]], ptr [[LENGTH_P:%.*]]) { ; CHECK-SAME: (ptr [[P:%.*]], ptr [[X_P:%.*]], ptr [[LENGTH_P:%.*]]) {
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: [[X:%.*]] = load i32, ptr [[X_P]], align 4 ; CHECK-NEXT: [[X:%.*]] = load i32, ptr [[X_P]], align 4
; CHECK-NEXT: [[LENGTH:%.*]] = load i32, ptr [[LENGTH_P]], align 4 ; CHECK-NEXT: [[LENGTH:%.*]] = load i32, ptr [[LENGTH_P]], align 4
; CHECK-NEXT: [[PRECOND_1:%.*]] = icmp sge i32 [[X]], 0 ; CHECK-NEXT: [[PRECOND_1:%.*]] = icmp sge i32 [[X]], 0
; CHECK-NEXT: [[PRECOND_2:%.*]] = icmp sge i32 [[LENGTH]], 0 ; CHECK-NEXT: [[PRECOND_2:%.*]] = icmp sge i32 [[LENGTH]], 0
; CHECK-NEXT: [[PRECOND:%.*]] = and i1 [[PRECOND_1]], [[PRECOND_2]] ; CHECK-NEXT: [[PRECOND:%.*]] = and i1 [[PRECOND_1]], [[PRECOND_2]]
; CHECK-NEXT: br i1 [[PRECOND]], label [[LOOP_PREHEADER:%.*]], label [[FAILED:%.*]] ; CHECK-NEXT: br i1 [[PRECOND]], label [[LOOP_PREHEADER:%.*]], label [[FAILED:%.*]]
; CHECK: loop.preheader: ; CHECK: loop.preheader:
; CHECK-NEXT: [[INVARIANT_OP:%.*]] = sub nsw i32 4, [[X]]
; CHECK-NEXT: br label [[LOOP:%.*]] ; CHECK-NEXT: br label [[LOOP:%.*]]
; CHECK: loop: ; CHECK: loop:
; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ] ; CHECK-NEXT: [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ], [ 0, [[LOOP_PREHEADER]] ]
; CHECK-NEXT: [[ARITH:%.*]] = add nsw i32 [[IV]], [[X]] ; CHECK-NEXT: [[X_CHECK:%.*]] = icmp slt i32 [[IV]], [[INVARIANT_OP]]
; CHECK-NEXT: [[X_CHECK:%.*]] = icmp slt i32 [[ARITH]], 4
; CHECK-NEXT: br i1 [[X_CHECK]], label [[OUT_OF_BOUNDS:%.*]], label [[BACKEDGE]] ; CHECK-NEXT: br i1 [[X_CHECK]], label [[OUT_OF_BOUNDS:%.*]], 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: store i32 1, ptr [[EL_PTR]], align 4 ; CHECK-NEXT: store i32 1, ptr [[EL_PTR]], align 4
; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4 ; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 4
; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]] ; CHECK-NEXT: [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], [[LENGTH]]
; 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 40 Lines