From 14da287e18846ea86e45b421dc47f78ecc5aa7cb Mon Sep 17 00:00:00 2001 From: Florian Hahn Date: Thu, 28 Jan 2021 16:34:09 +0000 Subject: [PATCH] [ConstraintElimination] Extend test coverage. This patch adds a lot of additional tests, focusing on loops and GEP arithmetic. Some of the tests expose existing problems, which will be fixed soon. --- .../Transforms/ConstraintElimination/add-nuw.ll | 67 +- llvm/test/Transforms/ConstraintElimination/add.ll | 1 - llvm/test/Transforms/ConstraintElimination/and.ll | 27 + .../ConstraintElimination/gep-arithmetic.ll | 783 +++++++++++++++++++++ llvm/test/Transforms/ConstraintElimination/geps.ll | 145 +++- .../loops-bottom-tested-base.ll | 98 +++ .../loops-bottom-tested-pointer-cmps.ll | 223 ++++++ .../loops-header-tested-base.ll | 437 ++++++++++++ .../loops-header-tested-pointer-cmps.ll | 764 ++++++++++++++++++++ .../loops-header-tested-pointer-iv.ll | 128 ++++ .../test/Transforms/ConstraintElimination/loops.ll | 1 - .../Transforms/ConstraintElimination/sub-nuw.ll | 2 - llvm/test/Transforms/ConstraintElimination/sub.ll | 1 - .../ConstraintElimination/vector-compares.ll | 70 ++ .../ConstraintElimination/wrapping-math.ll | 73 ++ 15 files changed, 2813 insertions(+), 7 deletions(-) create mode 100644 llvm/test/Transforms/ConstraintElimination/gep-arithmetic.ll create mode 100644 llvm/test/Transforms/ConstraintElimination/loops-bottom-tested-base.ll create mode 100644 llvm/test/Transforms/ConstraintElimination/loops-bottom-tested-pointer-cmps.ll create mode 100644 llvm/test/Transforms/ConstraintElimination/loops-header-tested-base.ll create mode 100644 llvm/test/Transforms/ConstraintElimination/loops-header-tested-pointer-cmps.ll create mode 100644 llvm/test/Transforms/ConstraintElimination/loops-header-tested-pointer-iv.ll create mode 100644 llvm/test/Transforms/ConstraintElimination/vector-compares.ll create mode 100644 llvm/test/Transforms/ConstraintElimination/wrapping-math.ll diff --git a/llvm/test/Transforms/ConstraintElimination/add-nuw.ll b/llvm/test/Transforms/ConstraintElimination/add-nuw.ll index 1792516..0fd9828 100644 --- a/llvm/test/Transforms/ConstraintElimination/add-nuw.ll +++ b/llvm/test/Transforms/ConstraintElimination/add-nuw.ll @@ -335,5 +335,70 @@ if.end: ; preds = %entry } +define i1 @test_n_must_ule_1_due_to_nuw(i8 %n, i8 %i) { +entry: + %sub.n.1 = add nuw i8 %n, -1 + %add = add nuw i8 %i, %sub.n.1 + %c.1 = icmp uge i8 %i, %add + br i1 %c.1, label %if.then, label %if.end + +if.then: ; preds = %entry + %t = icmp ule i8 %n, 1 + ret i1 %t + +if.end: ; preds = %entry + %f = icmp ule i8 %n, 1 + ret i1 %f +} + + +define i1 @test_n_unknown_missing_nuw(i8 %n, i8 %i) { +entry: + %sub.n.1 = add i8 %n, -1 + %add = add i8 %i, %sub.n.1 + %c.1 = icmp uge i8 %i, %add + br i1 %c.1, label %if.then, label %if.end + +if.then: ; preds = %entry + %t = icmp ule i8 %n, 1 + ret i1 %t + +if.end: ; preds = %entry + %f = icmp ule i8 %n, 1 + ret i1 %f +} + +define i1 @test_n_must_ule_2_due_to_nuw(i8 %n, i8 %i) { +entry: + %sub.n.1 = add nuw i8 %n, -2 + %add = add nuw i8 %i, %sub.n.1 + %c.1 = icmp uge i8 %i, %add + br i1 %c.1, label %if.then, label %if.end + +if.then: ; preds = %entry + %t = icmp ule i8 %n, 2 + ret i1 %t + +if.end: ; preds = %entry + %f = icmp ule i8 %n, 2 + ret i1 %f +} + + +define i1 @test_n_unknown_missing_nuw2(i8 %n, i8 %i) { +entry: + %sub.n.1 = add i8 %n, -2 + %add = add i8 %i, %sub.n.1 + %c.1 = icmp uge i8 %i, %add + br i1 %c.1, label %if.then, label %if.end + +if.then: ; preds = %entry + %t = icmp ule i8 %n, 1 + ret i1 %t + +if.end: ; preds = %entry + %f = icmp ule i8 %n, 1 + ret i1 %f +} + declare void @use(i1) -declare void @llvm.trap() diff --git a/llvm/test/Transforms/ConstraintElimination/add.ll b/llvm/test/Transforms/ConstraintElimination/add.ll index ac82722..d57a67d 100644 --- a/llvm/test/Transforms/ConstraintElimination/add.ll +++ b/llvm/test/Transforms/ConstraintElimination/add.ll @@ -239,4 +239,3 @@ if.end: ; preds = %entry declare void @use(i1) -declare void @llvm.trap() diff --git a/llvm/test/Transforms/ConstraintElimination/and.ll b/llvm/test/Transforms/ConstraintElimination/and.ll index e1ec849..8558ea9 100644 --- a/llvm/test/Transforms/ConstraintElimination/and.ll +++ b/llvm/test/Transforms/ConstraintElimination/and.ll @@ -135,3 +135,30 @@ exit: ret i32 20 } + +define i4 @and_compare_undef(i16 %N, i16 %step) { +; CHECK-LABEL: @and_compare_undef( +; CHECK-NEXT: step.check: +; CHECK-NEXT: [[STEP_POS:%.*]] = icmp uge i16 [[STEP:%.*]], 0 +; CHECK-NEXT: [[B1:%.*]] = add i16 undef, -1 +; CHECK-NEXT: [[STEP_ULT_N:%.*]] = icmp ult i16 [[B1]], [[N:%.*]] +; CHECK-NEXT: [[AND_STEP:%.*]] = and i1 [[STEP_POS]], [[STEP_ULT_N]] +; CHECK-NEXT: br i1 [[AND_STEP]], label [[PTR_CHECK:%.*]], label [[EXIT:%.*]] +; CHECK: ptr.check: +; CHECK-NEXT: br label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret i4 3 +; +step.check: + %step.pos = icmp uge i16 %step, 0 + %B1 = add i16 undef, -1 + %step.ult.N = icmp ult i16 %B1, %N + %and.step = and i1 %step.pos, %step.ult.N + br i1 %and.step, label %ptr.check, label %exit + +ptr.check: + br label %exit + +exit: + ret i4 3 +} diff --git a/llvm/test/Transforms/ConstraintElimination/gep-arithmetic.ll b/llvm/test/Transforms/ConstraintElimination/gep-arithmetic.ll new file mode 100644 index 0000000..08af75a --- /dev/null +++ b/llvm/test/Transforms/ConstraintElimination/gep-arithmetic.ll @@ -0,0 +1,783 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -constraint-elimination -S %s | FileCheck %s + +declare void @llvm.assume(i1) + +define i1 @n_unknown(i32* %dst, i32 %n, i32 %i) { +; CHECK-LABEL: @n_unknown( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SUB:%.*]] = add i32 [[N:%.*]], -1 +; CHECK-NEXT: [[IDXPROM:%.*]] = zext i32 [[SUB]] to i64 +; CHECK-NEXT: [[PTR_N_SUB_1:%.*]] = getelementptr i32, i32* [[DST:%.*]], i64 [[IDXPROM]] +; CHECK-NEXT: [[CMP_PTR_DST:%.*]] = icmp uge i32* [[PTR_N_SUB_1]], [[DST]] +; CHECK-NEXT: br i1 [[CMP_PTR_DST]], label [[PRE_BB_2:%.*]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret i1 false +; CHECK: pre.bb.2: +; CHECK-NEXT: [[PRE_2:%.*]] = icmp uge i32 [[I:%.*]], 0 +; CHECK-NEXT: br i1 [[PRE_2]], label [[TGT_BB:%.*]], label [[EXIT]] +; CHECK: tgt.bb: +; CHECK-NEXT: [[CMP1:%.*]] = icmp ult i32 [[I]], [[N]] +; CHECK-NEXT: ret i1 [[CMP1]] +; +entry: + %sub = add i32 %n, -1 + %idxprom = zext i32 %sub to i64 + %ptr.n.sub.1 = getelementptr i32, i32* %dst, i64 %idxprom + %cmp.ptr.dst = icmp uge i32* %ptr.n.sub.1, %dst + br i1 %cmp.ptr.dst, label %pre.bb.2, label %exit + +exit: + ret i1 false + +pre.bb.2: + %pre.2 = icmp uge i32 %i, 0 + br i1 %pre.2, label %tgt.bb, label %exit + +tgt.bb: + %cmp1 = icmp ult i32 %i, %n + ret i1 %cmp1 +} + +define i1 @n_known_zero_due_to_nuw(i32* %dst, i32 %n, i32 %i) { +; CHECK-LABEL: @n_known_zero_due_to_nuw( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SUB:%.*]] = add i32 [[N:%.*]], -1 +; CHECK-NEXT: [[IDXPROM:%.*]] = zext i32 [[SUB]] to i64 +; CHECK-NEXT: [[PTR_N_SUB_1:%.*]] = getelementptr i32, i32* [[DST:%.*]], i64 [[IDXPROM]] +; CHECK-NEXT: [[CMP_PTR_DST:%.*]] = icmp uge i32* [[PTR_N_SUB_1]], [[DST]] +; CHECK-NEXT: br i1 [[CMP_PTR_DST]], label [[PRE_BB_2:%.*]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret i1 false +; CHECK: pre.bb.2: +; CHECK-NEXT: [[PRE_2:%.*]] = icmp uge i32 [[I:%.*]], 0 +; CHECK-NEXT: br i1 [[PRE_2]], label [[TGT_BB:%.*]], label [[EXIT]] +; CHECK: tgt.bb: +; CHECK-NEXT: [[CMP1:%.*]] = icmp ult i32 [[I]], [[N]] +; CHECK-NEXT: ret i1 [[CMP1]] +; +entry: + %sub = add i32 %n, -1 + %idxprom = zext i32 %sub to i64 + %ptr.n.sub.1 = getelementptr i32, i32* %dst, i64 %idxprom + %cmp.ptr.dst = icmp uge i32* %ptr.n.sub.1, %dst + br i1 %cmp.ptr.dst, label %pre.bb.2, label %exit + +exit: + ret i1 false + +pre.bb.2: + %pre.2 = icmp uge i32 %i, 0 + br i1 %pre.2, label %tgt.bb, label %exit + +tgt.bb: + %cmp1 = icmp ult i32 %i, %n + ret i1 %cmp1 +} + +define i4 @ptr_N_signed_positive_explicit_check_constant_step(i8* %src, i8* %lower, i8* %upper, i16 %N, i16 %step) { +; CHECK-LABEL: @ptr_N_signed_positive_explicit_check_constant_step( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[N_POS:%.*]] = icmp sge i16 [[N:%.*]], 0 +; CHECK-NEXT: br i1 [[N_POS]], label [[ENTRY_1:%.*]], label [[TRAP_BB:%.*]] +; CHECK: entry.1: +; CHECK-NEXT: [[SRC_END:%.*]] = getelementptr inbounds i8, i8* [[SRC:%.*]], i16 [[N]] +; CHECK-NEXT: [[CMP_SRC_START:%.*]] = icmp ult i8* [[SRC]], [[LOWER:%.*]] +; CHECK-NEXT: [[CMP_SRC_END:%.*]] = icmp uge i8* [[SRC_END]], [[UPPER:%.*]] +; CHECK-NEXT: [[OR_PRECOND_0:%.*]] = or i1 [[CMP_SRC_START]], [[CMP_SRC_END]] +; CHECK-NEXT: br i1 [[OR_PRECOND_0]], label [[TRAP_BB]], label [[STEP_CHECK:%.*]] +; CHECK: trap.bb: +; CHECK-NEXT: ret i4 2 +; CHECK: step.check: +; CHECK-NEXT: [[STEP_ULT_N:%.*]] = icmp ult i16 1, [[N]] +; CHECK-NEXT: br i1 [[STEP_ULT_N]], label [[PTR_CHECK:%.*]], label [[EXIT:%.*]] +; CHECK: ptr.check: +; CHECK-NEXT: [[SRC_STEP:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i16 1 +; CHECK-NEXT: [[CMP_STEP_START:%.*]] = icmp ult i8* [[SRC_STEP]], [[LOWER]] +; CHECK-NEXT: [[CMP_STEP_END:%.*]] = icmp uge i8* [[SRC_STEP]], [[UPPER]] +; CHECK-NEXT: [[OR_CHECK:%.*]] = or i1 false, false +; CHECK-NEXT: br i1 [[OR_CHECK]], label [[TRAP_BB]], label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret i4 3 +; + +entry: + %N.pos = icmp sge i16 %N, 0 + br i1 %N.pos, label %entry.1, label %trap.bb + +entry.1: + %src.end = getelementptr inbounds i8, i8* %src, i16 %N + %cmp.src.start = icmp ult i8* %src, %lower + %cmp.src.end = icmp uge i8* %src.end, %upper + %or.precond.0 = or i1 %cmp.src.start, %cmp.src.end + br i1 %or.precond.0, label %trap.bb, label %step.check + +trap.bb: + ret i4 2 + +step.check: + %step.ult.N = icmp ult i16 1, %N + br i1 %step.ult.N, label %ptr.check, label %exit + +ptr.check: + %src.step = getelementptr inbounds i8, i8* %src, i16 1 + %cmp.step.start = icmp ult i8* %src.step, %lower + %cmp.step.end = icmp uge i8* %src.step, %upper + %or.check = or i1 %cmp.step.start, %cmp.step.end + br i1 %or.check, label %trap.bb, label %exit + +exit: + ret i4 3 +} + +; Same as ptr_N_signed_positive_explicit_check_constant_step, but without inbounds. +define i4 @ptr_N_signed_positive_explicit_check_constant_step_no_inbonds(i8* %src, i8* %lower, i8* %upper, i16 %N, i16 %step) { +; CHECK-LABEL: @ptr_N_signed_positive_explicit_check_constant_step_no_inbonds( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[N_POS:%.*]] = icmp sge i16 [[N:%.*]], 0 +; CHECK-NEXT: br i1 [[N_POS]], label [[ENTRY_1:%.*]], label [[TRAP_BB:%.*]] +; CHECK: entry.1: +; CHECK-NEXT: [[SRC_END:%.*]] = getelementptr i8, i8* [[SRC:%.*]], i16 [[N]] +; CHECK-NEXT: [[CMP_SRC_START:%.*]] = icmp ult i8* [[SRC]], [[LOWER:%.*]] +; CHECK-NEXT: [[CMP_SRC_END:%.*]] = icmp uge i8* [[SRC_END]], [[UPPER:%.*]] +; CHECK-NEXT: [[OR_PRECOND_0:%.*]] = or i1 [[CMP_SRC_START]], [[CMP_SRC_END]] +; CHECK-NEXT: br i1 [[OR_PRECOND_0]], label [[TRAP_BB]], label [[STEP_CHECK:%.*]] +; CHECK: trap.bb: +; CHECK-NEXT: ret i4 2 +; CHECK: step.check: +; CHECK-NEXT: [[STEP_ULT_N:%.*]] = icmp ult i16 1, [[N]] +; CHECK-NEXT: br i1 [[STEP_ULT_N]], label [[PTR_CHECK:%.*]], label [[EXIT:%.*]] +; CHECK: ptr.check: +; CHECK-NEXT: [[SRC_STEP:%.*]] = getelementptr i8, i8* [[SRC]], i16 1 +; CHECK-NEXT: [[CMP_STEP_START:%.*]] = icmp ult i8* [[SRC_STEP]], [[LOWER]] +; CHECK-NEXT: [[CMP_STEP_END:%.*]] = icmp uge i8* [[SRC_STEP]], [[UPPER]] +; CHECK-NEXT: [[OR_CHECK:%.*]] = or i1 false, false +; CHECK-NEXT: br i1 [[OR_CHECK]], label [[TRAP_BB]], label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret i4 3 +; + +entry: + %N.pos = icmp sge i16 %N, 0 + br i1 %N.pos, label %entry.1, label %trap.bb + +entry.1: + %src.end = getelementptr i8, i8* %src, i16 %N + %cmp.src.start = icmp ult i8* %src, %lower + %cmp.src.end = icmp uge i8* %src.end, %upper + %or.precond.0 = or i1 %cmp.src.start, %cmp.src.end + br i1 %or.precond.0, label %trap.bb, label %step.check + +trap.bb: + ret i4 2 + +step.check: + %step.ult.N = icmp ult i16 1, %N + br i1 %step.ult.N, label %ptr.check, label %exit + +ptr.check: + %src.step = getelementptr i8, i8* %src, i16 1 + %cmp.step.start = icmp ult i8* %src.step, %lower + %cmp.step.end = icmp uge i8* %src.step, %upper + %or.check = or i1 %cmp.step.start, %cmp.step.end + br i1 %or.check, label %trap.bb, label %exit + +exit: + ret i4 3 +} + +define i4 @ptr_N_and_step_signed_positive_explicit_check_constant_step(i8* %src, i8* %lower, i8* %upper, i16 %N, i16 %step) { +; CHECK-LABEL: @ptr_N_and_step_signed_positive_explicit_check_constant_step( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[N_POS:%.*]] = icmp sge i16 [[N:%.*]], 0 +; CHECK-NEXT: [[STEP_POS:%.*]] = icmp sge i16 [[STEP:%.*]], 0 +; CHECK-NEXT: [[AND_1:%.*]] = and i1 [[N_POS]], [[STEP_POS]] +; CHECK-NEXT: br i1 [[AND_1]], label [[ENTRY_1:%.*]], label [[TRAP_BB:%.*]] +; CHECK: entry.1: +; CHECK-NEXT: [[SRC_END:%.*]] = getelementptr inbounds i8, i8* [[SRC:%.*]], i16 [[N]] +; CHECK-NEXT: [[CMP_SRC_START:%.*]] = icmp ult i8* [[SRC]], [[LOWER:%.*]] +; CHECK-NEXT: [[CMP_SRC_END:%.*]] = icmp uge i8* [[SRC_END]], [[UPPER:%.*]] +; CHECK-NEXT: [[OR_PRECOND_0:%.*]] = or i1 [[CMP_SRC_START]], [[CMP_SRC_END]] +; CHECK-NEXT: br i1 [[OR_PRECOND_0]], label [[TRAP_BB]], label [[STEP_CHECK:%.*]] +; CHECK: trap.bb: +; CHECK-NEXT: ret i4 2 +; CHECK: step.check: +; CHECK-NEXT: [[STEP_UGE_0:%.*]] = icmp uge i16 [[STEP]], 0 +; CHECK-NEXT: [[STEP_ULT_N:%.*]] = icmp ult i16 [[STEP]], [[N]] +; CHECK-NEXT: [[AND_2:%.*]] = and i1 [[STEP_UGE_0]], [[STEP_ULT_N]] +; CHECK-NEXT: br i1 [[AND_2]], label [[PTR_CHECK:%.*]], label [[EXIT:%.*]] +; CHECK: ptr.check: +; CHECK-NEXT: [[SRC_STEP:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i16 1 +; CHECK-NEXT: [[CMP_STEP_START:%.*]] = icmp ult i8* [[SRC_STEP]], [[LOWER]] +; CHECK-NEXT: [[CMP_STEP_END:%.*]] = icmp uge i8* [[SRC_STEP]], [[UPPER]] +; CHECK-NEXT: [[OR_CHECK:%.*]] = or i1 false, false +; CHECK-NEXT: br i1 [[OR_CHECK]], label [[TRAP_BB]], label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret i4 3 +; + +entry: + %N.pos = icmp sge i16 %N, 0 + %step.pos = icmp sge i16 %step, 0 + %and.1 = and i1 %N.pos, %step.pos + br i1 %and.1, label %entry.1, label %trap.bb + +entry.1: + %src.end = getelementptr inbounds i8, i8* %src, i16 %N + %cmp.src.start = icmp ult i8* %src, %lower + %cmp.src.end = icmp uge i8* %src.end, %upper + %or.precond.0 = or i1 %cmp.src.start, %cmp.src.end + br i1 %or.precond.0, label %trap.bb, label %step.check + +trap.bb: + ret i4 2 + +step.check: + %step.uge.0 = icmp uge i16 %step, 0 + %step.ult.N = icmp ult i16 %step, %N + %and.2 = and i1 %step.uge.0, %step.ult.N + br i1 %and.2, label %ptr.check, label %exit + +ptr.check: + %src.step = getelementptr inbounds i8, i8* %src, i16 1 + %cmp.step.start = icmp ult i8* %src.step, %lower + %cmp.step.end = icmp uge i8* %src.step, %upper + %or.check = or i1 %cmp.step.start, %cmp.step.end + br i1 %or.check, label %trap.bb, label %exit + +exit: + ret i4 3 +} + +define i4 @ptr_N_and_step_signed_positive_unsigned_checks_only(i8* %src, i8* %lower, i8* %upper, i16 %N, i16 %step) { +; CHECK-LABEL: @ptr_N_and_step_signed_positive_unsigned_checks_only( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SRC_END:%.*]] = getelementptr inbounds i8, i8* [[SRC:%.*]], i16 [[N:%.*]] +; CHECK-NEXT: [[NO_OVERFLOW:%.*]] = icmp ule i8* [[SRC]], [[SRC_END]] +; CHECK-NEXT: br i1 [[NO_OVERFLOW]], label [[ENTRY_1:%.*]], label [[TRAP_BB:%.*]] +; CHECK: entry.1: +; CHECK-NEXT: [[CMP_SRC_START:%.*]] = icmp ult i8* [[SRC]], [[LOWER:%.*]] +; CHECK-NEXT: [[CMP_SRC_END:%.*]] = icmp uge i8* [[SRC_END]], [[UPPER:%.*]] +; CHECK-NEXT: [[OR_PRECOND_0:%.*]] = or i1 [[CMP_SRC_START]], [[CMP_SRC_END]] +; CHECK-NEXT: br i1 [[OR_PRECOND_0]], label [[TRAP_BB]], label [[STEP_CHECK:%.*]] +; CHECK: trap.bb: +; CHECK-NEXT: ret i4 2 +; CHECK: step.check: +; CHECK-NEXT: [[STEP_UGE_0:%.*]] = icmp uge i16 [[STEP:%.*]], 0 +; CHECK-NEXT: [[STEP_ULT_N:%.*]] = icmp ult i16 [[STEP]], [[N]] +; CHECK-NEXT: [[AND_2:%.*]] = and i1 [[STEP_UGE_0]], [[STEP_ULT_N]] +; CHECK-NEXT: br i1 [[AND_2]], label [[PTR_CHECK:%.*]], label [[EXIT:%.*]] +; CHECK: ptr.check: +; CHECK-NEXT: [[SRC_STEP:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i16 1 +; CHECK-NEXT: [[CMP_STEP_START:%.*]] = icmp ult i8* [[SRC_STEP]], [[LOWER]] +; CHECK-NEXT: [[CMP_STEP_END:%.*]] = icmp uge i8* [[SRC_STEP]], [[UPPER]] +; CHECK-NEXT: [[OR_CHECK:%.*]] = or i1 false, false +; CHECK-NEXT: br i1 [[OR_CHECK]], label [[TRAP_BB]], label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret i4 3 +; +entry: + %src.end = getelementptr inbounds i8, i8* %src, i16 %N + %no.overflow = icmp ule i8* %src, %src.end + br i1 %no.overflow, label %entry.1, label %trap.bb + +entry.1: + %cmp.src.start = icmp ult i8* %src, %lower + %cmp.src.end = icmp uge i8* %src.end, %upper + %or.precond.0 = or i1 %cmp.src.start, %cmp.src.end + br i1 %or.precond.0, label %trap.bb, label %step.check + +trap.bb: + ret i4 2 + +step.check: + %step.uge.0 = icmp uge i16 %step, 0 + %step.ult.N = icmp ult i16 %step, %N + %and.2 = and i1 %step.uge.0, %step.ult.N + br i1 %and.2, label %ptr.check, label %exit + +ptr.check: + %src.step = getelementptr inbounds i8, i8* %src, i16 1 + %cmp.step.start = icmp ult i8* %src.step, %lower + %cmp.step.end = icmp uge i8* %src.step, %upper + %or.check = or i1 %cmp.step.start, %cmp.step.end + br i1 %or.check, label %trap.bb, label %exit + +exit: + ret i4 3 +} + +define i4 @ptr_N_signed_positive(i8* %src, i8* %lower, i8* %upper, i16 %N, i16 %step) { +; CHECK-LABEL: @ptr_N_signed_positive( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SRC_END:%.*]] = getelementptr inbounds i8, i8* [[SRC:%.*]], i16 [[N:%.*]] +; CHECK-NEXT: [[CMP_SRC_START:%.*]] = icmp ult i8* [[SRC]], [[LOWER:%.*]] +; CHECK-NEXT: [[CMP_SRC_END:%.*]] = icmp uge i8* [[SRC_END]], [[UPPER:%.*]] +; CHECK-NEXT: [[N_NEG:%.*]] = icmp slt i16 [[N]], 0 +; CHECK-NEXT: [[OR_PRECOND_0:%.*]] = or i1 [[CMP_SRC_START]], [[CMP_SRC_END]] +; CHECK-NEXT: [[OR_PRECOND_1:%.*]] = or i1 [[OR_PRECOND_0]], [[N_NEG]] +; CHECK-NEXT: br i1 [[OR_PRECOND_1]], label [[TRAP_BB:%.*]], label [[STEP_CHECK:%.*]] +; CHECK: trap.bb: +; CHECK-NEXT: ret i4 2 +; CHECK: step.check: +; CHECK-NEXT: [[STEP_POS:%.*]] = icmp uge i16 [[STEP:%.*]], 0 +; CHECK-NEXT: [[STEP_ULT_N:%.*]] = icmp ult i16 [[STEP]], [[N]] +; CHECK-NEXT: [[AND_STEP:%.*]] = and i1 [[STEP_POS]], [[STEP_ULT_N]] +; CHECK-NEXT: br i1 [[AND_STEP]], label [[PTR_CHECK:%.*]], label [[EXIT:%.*]] +; CHECK: ptr.check: +; CHECK-NEXT: [[SRC_STEP:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i16 [[STEP]] +; CHECK-NEXT: [[CMP_STEP_START:%.*]] = icmp ult i8* [[SRC_STEP]], [[LOWER]] +; CHECK-NEXT: [[CMP_STEP_END:%.*]] = icmp uge i8* [[SRC_STEP]], [[UPPER]] +; CHECK-NEXT: [[OR_CHECK:%.*]] = or i1 [[CMP_STEP_START]], [[CMP_STEP_END]] +; CHECK-NEXT: br i1 [[OR_CHECK]], label [[TRAP_BB]], label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret i4 3 +; +entry: + %src.end = getelementptr inbounds i8, i8* %src, i16 %N + %cmp.src.start = icmp ult i8* %src, %lower + %cmp.src.end = icmp uge i8* %src.end, %upper + %N.neg = icmp slt i16 %N, 0 + %or.precond.0 = or i1 %cmp.src.start, %cmp.src.end + %or.precond.1 = or i1 %or.precond.0, %N.neg + br i1 %or.precond.1, label %trap.bb, label %step.check + +trap.bb: + ret i4 2 + +step.check: + %step.pos = icmp uge i16 %step, 0 + %step.ult.N = icmp ult i16 %step, %N + %and.step = and i1 %step.pos, %step.ult.N + br i1 %and.step, label %ptr.check, label %exit + +ptr.check: + %src.step = getelementptr inbounds i8, i8* %src, i16 %step + %cmp.step.start = icmp ult i8* %src.step, %lower + %cmp.step.end = icmp uge i8* %src.step, %upper + %or.check = or i1 %cmp.step.start, %cmp.step.end + br i1 %or.check, label %trap.bb, label %exit + +exit: + ret i4 3 +} + +define i4 @ptr_N_could_be_negative(i8* %src, i8* %lower, i8* %upper, i16 %N, i16 %step) { +; CHECK-LABEL: @ptr_N_could_be_negative( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SRC_END:%.*]] = getelementptr inbounds i8, i8* [[SRC:%.*]], i16 [[N:%.*]] +; CHECK-NEXT: [[CMP_SRC_START:%.*]] = icmp ult i8* [[SRC]], [[LOWER:%.*]] +; CHECK-NEXT: [[CMP_SRC_END:%.*]] = icmp uge i8* [[SRC_END]], [[UPPER:%.*]] +; CHECK-NEXT: [[OR_PRECOND_0:%.*]] = or i1 [[CMP_SRC_START]], [[CMP_SRC_END]] +; CHECK-NEXT: br i1 [[OR_PRECOND_0]], label [[TRAP_BB:%.*]], label [[STEP_CHECK:%.*]] +; CHECK: trap.bb: +; CHECK-NEXT: ret i4 2 +; CHECK: step.check: +; CHECK-NEXT: [[STEP_POS:%.*]] = icmp uge i16 [[STEP:%.*]], 0 +; CHECK-NEXT: [[STEP_ULT_N:%.*]] = icmp ult i16 [[STEP]], [[N]] +; CHECK-NEXT: [[AND_STEP:%.*]] = and i1 [[STEP_POS]], [[STEP_ULT_N]] +; CHECK-NEXT: br i1 [[AND_STEP]], label [[PTR_CHECK:%.*]], label [[EXIT:%.*]] +; CHECK: ptr.check: +; CHECK-NEXT: [[SRC_STEP:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i16 [[STEP]] +; CHECK-NEXT: [[CMP_STEP_START:%.*]] = icmp ult i8* [[SRC_STEP]], [[LOWER]] +; CHECK-NEXT: [[CMP_STEP_END:%.*]] = icmp uge i8* [[SRC_STEP]], [[UPPER]] +; CHECK-NEXT: [[OR_CHECK:%.*]] = or i1 false, false +; CHECK-NEXT: br i1 [[OR_CHECK]], label [[TRAP_BB]], label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret i4 3 +; +entry: + %src.end = getelementptr inbounds i8, i8* %src, i16 %N + %cmp.src.start = icmp ult i8* %src, %lower + %cmp.src.end = icmp uge i8* %src.end, %upper + %or.precond.0 = or i1 %cmp.src.start, %cmp.src.end + br i1 %or.precond.0, label %trap.bb, label %step.check + +trap.bb: + ret i4 2 + +step.check: + %step.pos = icmp uge i16 %step, 0 + %step.ult.N = icmp ult i16 %step, %N + %and.step = and i1 %step.pos, %step.ult.N + br i1 %and.step, label %ptr.check, label %exit + +ptr.check: + %src.step = getelementptr inbounds i8, i8* %src, i16 %step + %cmp.step.start = icmp ult i8* %src.step, %lower + %cmp.step.end = icmp uge i8* %src.step, %upper + %or.check = or i1 %cmp.step.start, %cmp.step.end + br i1 %or.check, label %trap.bb, label %exit + +exit: + ret i4 3 +} + +define i4 @ptr_src_uge_end(i8* %src, i8* %lower, i8* %upper, i16 %N, i16 %step) { +; CHECK-LABEL: @ptr_src_uge_end( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SRC_END:%.*]] = getelementptr inbounds i8, i8* [[SRC:%.*]], i16 [[N:%.*]] +; CHECK-NEXT: [[CMP_SRC_START:%.*]] = icmp ult i8* [[SRC]], [[LOWER:%.*]] +; CHECK-NEXT: [[CMP_SRC_END:%.*]] = icmp uge i8* [[SRC_END]], [[UPPER:%.*]] +; CHECK-NEXT: [[CMP_OVERFLOW:%.*]] = icmp ugt i8* [[SRC]], [[SRC_END]] +; CHECK-NEXT: [[OR_PRECOND_0:%.*]] = or i1 [[CMP_SRC_START]], [[CMP_SRC_END]] +; CHECK-NEXT: [[OR_PRECOND_1:%.*]] = or i1 [[OR_PRECOND_0]], [[CMP_OVERFLOW]] +; CHECK-NEXT: br i1 [[OR_PRECOND_1]], label [[TRAP_BB:%.*]], label [[STEP_CHECK:%.*]] +; CHECK: trap.bb: +; CHECK-NEXT: ret i4 2 +; CHECK: step.check: +; CHECK-NEXT: [[STEP_POS:%.*]] = icmp uge i16 [[STEP:%.*]], 0 +; CHECK-NEXT: [[STEP_ULT_N:%.*]] = icmp ult i16 [[STEP]], [[N]] +; CHECK-NEXT: [[AND_STEP:%.*]] = and i1 [[STEP_POS]], [[STEP_ULT_N]] +; CHECK-NEXT: br i1 [[AND_STEP]], label [[PTR_CHECK:%.*]], label [[EXIT:%.*]] +; CHECK: ptr.check: +; CHECK-NEXT: [[SRC_STEP:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i16 [[STEP]] +; CHECK-NEXT: [[CMP_STEP_START:%.*]] = icmp ult i8* [[SRC_STEP]], [[LOWER]] +; CHECK-NEXT: [[CMP_STEP_END:%.*]] = icmp uge i8* [[SRC_STEP]], [[UPPER]] +; CHECK-NEXT: [[OR_CHECK:%.*]] = or i1 [[CMP_STEP_START]], [[CMP_STEP_END]] +; CHECK-NEXT: br i1 [[OR_CHECK]], label [[TRAP_BB]], label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret i4 3 +; +entry: + %src.end = getelementptr inbounds i8, i8* %src, i16 %N + %cmp.src.start = icmp ult i8* %src, %lower + %cmp.src.end = icmp uge i8* %src.end, %upper + %cmp.overflow = icmp ugt i8* %src, %src.end + %or.precond.0 = or i1 %cmp.src.start, %cmp.src.end + %or.precond.1 = or i1 %or.precond.0, %cmp.overflow + br i1 %or.precond.1, label %trap.bb, label %step.check + +trap.bb: + ret i4 2 + +step.check: + %step.pos = icmp uge i16 %step, 0 + %step.ult.N = icmp ult i16 %step, %N + %and.step = and i1 %step.pos, %step.ult.N + br i1 %and.step, label %ptr.check, label %exit + +ptr.check: + %src.step = getelementptr inbounds i8, i8* %src, i16 %step + %cmp.step.start = icmp ult i8* %src.step, %lower + %cmp.step.end = icmp uge i8* %src.step, %upper + %or.check = or i1 %cmp.step.start, %cmp.step.end + br i1 %or.check, label %trap.bb, label %exit + +exit: + ret i4 3 +} + +define i4 @inc_ptr_N_could_be_negative(i8* %src, i8* %lower, i8* %upper, i16 %N, i16 %step) { +; CHECK-LABEL: @inc_ptr_N_could_be_negative( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SRC_END:%.*]] = getelementptr inbounds i8, i8* [[SRC:%.*]], i16 [[N:%.*]] +; CHECK-NEXT: [[CMP_SRC_START:%.*]] = icmp ult i8* [[SRC]], [[LOWER:%.*]] +; CHECK-NEXT: [[CMP_SRC_END:%.*]] = icmp uge i8* [[SRC_END]], [[UPPER:%.*]] +; CHECK-NEXT: [[OR_PRECOND_0:%.*]] = or i1 [[CMP_SRC_START]], [[CMP_SRC_END]] +; CHECK-NEXT: br i1 [[OR_PRECOND_0]], label [[TRAP_BB:%.*]], label [[STEP_CHECK:%.*]] +; CHECK: trap.bb: +; CHECK-NEXT: ret i4 2 +; CHECK: step.check: +; CHECK-NEXT: [[STEP_POS:%.*]] = icmp uge i16 [[STEP:%.*]], 0 +; CHECK-NEXT: [[NEXT:%.*]] = add nuw nsw i16 [[STEP]], 2 +; CHECK-NEXT: [[STEP_ULT_N:%.*]] = icmp ult i16 [[NEXT]], [[N]] +; CHECK-NEXT: [[AND_STEP:%.*]] = and i1 [[STEP_POS]], [[STEP_ULT_N]] +; CHECK-NEXT: br i1 [[AND_STEP]], label [[PTR_CHECK:%.*]], label [[EXIT:%.*]] +; CHECK: ptr.check: +; CHECK-NEXT: [[SRC_STEP:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i16 [[STEP]] +; CHECK-NEXT: [[CMP_STEP_START:%.*]] = icmp ult i8* [[SRC_STEP]], [[LOWER]] +; CHECK-NEXT: [[CMP_STEP_END:%.*]] = icmp uge i8* [[SRC_STEP]], [[UPPER]] +; CHECK-NEXT: [[OR_CHECK:%.*]] = or i1 false, false +; CHECK-NEXT: br i1 [[OR_CHECK]], label [[TRAP_BB]], label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret i4 3 +; +entry: + %src.end = getelementptr inbounds i8, i8* %src, i16 %N + %cmp.src.start = icmp ult i8* %src, %lower + %cmp.src.end = icmp uge i8* %src.end, %upper + %or.precond.0 = or i1 %cmp.src.start, %cmp.src.end + br i1 %or.precond.0, label %trap.bb, label %step.check + +trap.bb: + ret i4 2 + +step.check: + %step.pos = icmp uge i16 %step, 0 + %next = add nsw nuw i16 %step, 2 + %step.ult.N = icmp ult i16 %next, %N + %and.step = and i1 %step.pos, %step.ult.N + br i1 %and.step, label %ptr.check, label %exit + +ptr.check: + %src.step = getelementptr inbounds i8, i8* %src, i16 %step + %cmp.step.start = icmp ult i8* %src.step, %lower + %cmp.step.end = icmp uge i8* %src.step, %upper + %or.check = or i1 %cmp.step.start, %cmp.step.end + br i1 %or.check, label %trap.bb, label %exit + +exit: + ret i4 3 +} + +define i4 @inc_ptr_src_uge_end(i8* %src, i8* %lower, i8* %upper, i16 %N, i16 %step) { +; CHECK-LABEL: @inc_ptr_src_uge_end( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SRC_END:%.*]] = getelementptr inbounds i8, i8* [[SRC:%.*]], i16 [[N:%.*]] +; CHECK-NEXT: [[CMP_SRC_START:%.*]] = icmp ult i8* [[SRC]], [[LOWER:%.*]] +; CHECK-NEXT: [[CMP_SRC_END:%.*]] = icmp uge i8* [[SRC_END]], [[UPPER:%.*]] +; CHECK-NEXT: [[CMP_OVERFLOW:%.*]] = icmp ugt i8* [[SRC]], [[SRC_END]] +; CHECK-NEXT: [[OR_PRECOND_0:%.*]] = or i1 [[CMP_SRC_START]], [[CMP_SRC_END]] +; CHECK-NEXT: [[OR_PRECOND_1:%.*]] = or i1 [[OR_PRECOND_0]], [[CMP_OVERFLOW]] +; CHECK-NEXT: br i1 [[OR_PRECOND_1]], label [[TRAP_BB:%.*]], label [[STEP_CHECK:%.*]] +; CHECK: trap.bb: +; CHECK-NEXT: ret i4 2 +; CHECK: step.check: +; CHECK-NEXT: [[STEP_POS:%.*]] = icmp uge i16 [[STEP:%.*]], 0 +; CHECK-NEXT: [[NEXT:%.*]] = add nuw nsw i16 [[STEP]], 2 +; CHECK-NEXT: [[STEP_ULT_N:%.*]] = icmp ult i16 [[NEXT]], [[N]] +; CHECK-NEXT: [[AND_STEP:%.*]] = and i1 [[STEP_POS]], [[STEP_ULT_N]] +; CHECK-NEXT: br i1 [[AND_STEP]], label [[PTR_CHECK:%.*]], label [[EXIT:%.*]] +; CHECK: ptr.check: +; CHECK-NEXT: [[SRC_STEP:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i16 [[STEP]] +; CHECK-NEXT: [[CMP_STEP_START:%.*]] = icmp ult i8* [[SRC_STEP]], [[LOWER]] +; CHECK-NEXT: [[CMP_STEP_END:%.*]] = icmp uge i8* [[SRC_STEP]], [[UPPER]] +; CHECK-NEXT: [[OR_CHECK:%.*]] = or i1 [[CMP_STEP_START]], [[CMP_STEP_END]] +; CHECK-NEXT: br i1 [[OR_CHECK]], label [[TRAP_BB]], label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret i4 3 +; +entry: + %src.end = getelementptr inbounds i8, i8* %src, i16 %N + %cmp.src.start = icmp ult i8* %src, %lower + %cmp.src.end = icmp uge i8* %src.end, %upper + %cmp.overflow = icmp ugt i8* %src, %src.end + %or.precond.0 = or i1 %cmp.src.start, %cmp.src.end + %or.precond.1 = or i1 %or.precond.0, %cmp.overflow + br i1 %or.precond.1, label %trap.bb, label %step.check + +trap.bb: + ret i4 2 + +step.check: + %step.pos = icmp uge i16 %step, 0 + %next = add nsw nuw i16 %step, 2 + %step.ult.N = icmp ult i16 %next, %N + %and.step = and i1 %step.pos, %step.ult.N + br i1 %and.step, label %ptr.check, label %exit + +ptr.check: + %src.step = getelementptr inbounds i8, i8* %src, i16 %step + %cmp.step.start = icmp ult i8* %src.step, %lower + %cmp.step.end = icmp uge i8* %src.step, %upper + %or.check = or i1 %cmp.step.start, %cmp.step.end + br i1 %or.check, label %trap.bb, label %exit + +exit: + ret i4 3 +} + +define i4 @inc_ptr_src_uge_end_no_nsw_add(i8* %src, i8* %lower, i8* %upper, i16 %idx, i16 %N, i16 %step) { +; CHECK-LABEL: @inc_ptr_src_uge_end_no_nsw_add( +; CHECK-NEXT: entry.1: +; CHECK-NEXT: [[IDX_POS:%.*]] = icmp sge i16 [[IDX:%.*]], 0 +; CHECK-NEXT: br i1 [[IDX_POS]], label [[ENTRY:%.*]], label [[TRAP_BB:%.*]] +; CHECK: entry: +; CHECK-NEXT: [[SRC_IDX:%.*]] = getelementptr inbounds i8, i8* [[SRC:%.*]], i16 [[IDX]] +; CHECK-NEXT: [[CMP_SRC_START:%.*]] = icmp ult i8* [[SRC_IDX]], [[LOWER:%.*]] +; CHECK-NEXT: br i1 [[CMP_SRC_START]], label [[TRAP_BB]], label [[STEP_CHECK:%.*]] +; CHECK: trap.bb: +; CHECK-NEXT: ret i4 2 +; CHECK: step.check: +; CHECK-NEXT: [[NEXT:%.*]] = add i16 [[IDX]], 2 +; CHECK-NEXT: [[SRC_STEP:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i16 [[NEXT]] +; CHECK-NEXT: [[CMP_STEP_START:%.*]] = icmp ult i8* [[SRC_STEP]], [[LOWER]] +; CHECK-NEXT: [[CMP_STEP_END:%.*]] = icmp uge i8* [[SRC_STEP]], [[UPPER:%.*]] +; CHECK-NEXT: [[OR_CHECK:%.*]] = or i1 [[CMP_STEP_START]], [[CMP_STEP_END]] +; CHECK-NEXT: br i1 [[OR_CHECK]], label [[TRAP_BB]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret i4 3 +; +entry.1: + %idx.pos = icmp sge i16 %idx, 0 + br i1 %idx.pos, label %entry, label %trap.bb + +entry: + %src.idx = getelementptr inbounds i8, i8* %src, i16 %idx + %cmp.src.start = icmp ult i8* %src.idx, %lower + br i1 %cmp.src.start, label %trap.bb, label %step.check + +trap.bb: + ret i4 2 + +step.check: + %next = add i16 %idx, 2 + %src.step = getelementptr inbounds i8, i8* %src, i16 %next + %cmp.step.start = icmp ult i8* %src.step, %lower + %cmp.step.end = icmp uge i8* %src.step, %upper + %or.check = or i1 %cmp.step.start, %cmp.step.end + br i1 %or.check, label %trap.bb, label %exit + +exit: + ret i4 3 +} + +define i4 @inc_ptr_src_uge_end_no_nsw_add_sge_0(i8* %src, i8* %lower, i8* %upper, i16 %idx, i16 %N, i16 %step) { +; CHECK-LABEL: @inc_ptr_src_uge_end_no_nsw_add_sge_0( +; CHECK-NEXT: entry.1: +; CHECK-NEXT: [[IDX_POS:%.*]] = icmp sge i16 [[IDX:%.*]], 0 +; CHECK-NEXT: br i1 [[IDX_POS]], label [[ENTRY:%.*]], label [[TRAP_BB:%.*]] +; CHECK: entry: +; CHECK-NEXT: [[SRC_IDX:%.*]] = getelementptr inbounds i8, i8* [[SRC:%.*]], i16 [[IDX]] +; CHECK-NEXT: [[CMP_SRC_START:%.*]] = icmp ult i8* [[SRC_IDX]], [[LOWER:%.*]] +; CHECK-NEXT: br i1 [[CMP_SRC_START]], label [[TRAP_BB]], label [[STEP_CHECK:%.*]] +; CHECK: trap.bb: +; CHECK-NEXT: ret i4 2 +; CHECK: step.check: +; CHECK-NEXT: [[NEXT:%.*]] = add i16 [[IDX]], 2 +; CHECK-NEXT: [[SRC_STEP:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i16 [[NEXT]] +; CHECK-NEXT: [[CMP_STEP_START:%.*]] = icmp ult i8* [[SRC_STEP]], [[LOWER]] +; CHECK-NEXT: [[CMP_STEP_END:%.*]] = icmp uge i8* [[SRC_STEP]], [[UPPER:%.*]] +; CHECK-NEXT: [[OR_CHECK:%.*]] = or i1 [[CMP_STEP_START]], [[CMP_STEP_END]] +; CHECK-NEXT: br i1 [[OR_CHECK]], label [[TRAP_BB]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret i4 3 +; +entry.1: + %idx.pos = icmp sge i16 %idx, 0 + br i1 %idx.pos, label %entry, label %trap.bb + +entry: + %src.idx = getelementptr inbounds i8, i8* %src, i16 %idx + %cmp.src.start = icmp ult i8* %src.idx, %lower + br i1 %cmp.src.start, label %trap.bb, label %step.check + +trap.bb: + ret i4 2 + +step.check: + %next = add i16 %idx, 2 + %src.step = getelementptr inbounds i8, i8* %src, i16 %next + %cmp.step.start = icmp ult i8* %src.step, %lower + %cmp.step.end = icmp uge i8* %src.step, %upper + %or.check = or i1 %cmp.step.start, %cmp.step.end + br i1 %or.check, label %trap.bb, label %exit + +exit: + ret i4 3 +} + + + + +; N might be negative, meaning %src.end could be < %src! Cannot remove checks! +define i4 @ptr_N_unsigned_positive(i8* %src, i8* %lower, i8* %upper, i16 %N, i16 %step) { +; CHECK-LABEL: @ptr_N_unsigned_positive( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SRC_END:%.*]] = getelementptr inbounds i8, i8* [[SRC:%.*]], i16 [[N:%.*]] +; CHECK-NEXT: [[CMP_SRC_START:%.*]] = icmp ult i8* [[SRC]], [[LOWER:%.*]] +; CHECK-NEXT: [[CMP_SRC_END:%.*]] = icmp uge i8* [[SRC_END]], [[UPPER:%.*]] +; CHECK-NEXT: [[N_NEG:%.*]] = icmp ult i16 [[N]], 0 +; CHECK-NEXT: [[OR_PRECOND_0:%.*]] = or i1 [[CMP_SRC_START]], [[CMP_SRC_END]] +; CHECK-NEXT: [[OR_PRECOND_1:%.*]] = or i1 [[OR_PRECOND_0]], [[N_NEG]] +; CHECK-NEXT: br i1 [[OR_PRECOND_1]], label [[TRAP_BB:%.*]], label [[STEP_CHECK:%.*]] +; CHECK: trap.bb: +; CHECK-NEXT: ret i4 2 +; CHECK: step.check: +; CHECK-NEXT: [[STEP_POS:%.*]] = icmp uge i16 [[STEP:%.*]], 0 +; CHECK-NEXT: [[STEP_ULT_N:%.*]] = icmp ult i16 [[STEP]], [[N]] +; CHECK-NEXT: [[AND_STEP:%.*]] = and i1 [[STEP_POS]], [[STEP_ULT_N]] +; CHECK-NEXT: br i1 [[AND_STEP]], label [[PTR_CHECK:%.*]], label [[EXIT:%.*]] +; CHECK: ptr.check: +; CHECK-NEXT: [[SRC_STEP:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i16 [[STEP]] +; CHECK-NEXT: [[CMP_STEP_START:%.*]] = icmp ult i8* [[SRC_STEP]], [[LOWER]] +; CHECK-NEXT: [[CMP_STEP_END:%.*]] = icmp uge i8* [[SRC_STEP]], [[UPPER]] +; CHECK-NEXT: [[OR_CHECK:%.*]] = or i1 [[CMP_STEP_START]], [[CMP_STEP_END]] +; CHECK-NEXT: br i1 [[OR_CHECK]], label [[TRAP_BB]], label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret i4 3 +; +entry: + %src.end = getelementptr inbounds i8, i8* %src, i16 %N + %cmp.src.start = icmp ult i8* %src, %lower + %cmp.src.end = icmp uge i8* %src.end, %upper + %N.neg = icmp ult i16 %N, 0 + %or.precond.0 = or i1 %cmp.src.start, %cmp.src.end + %or.precond.1 = or i1 %or.precond.0, %N.neg + br i1 %or.precond.1, label %trap.bb, label %step.check + +trap.bb: + ret i4 2 + +step.check: + %step.pos = icmp uge i16 %step, 0 + %step.ult.N = icmp ult i16 %step, %N + %and.step = and i1 %step.pos, %step.ult.N + br i1 %and.step, label %ptr.check, label %exit + +ptr.check: + %src.step = getelementptr inbounds i8, i8* %src, i16 %step + %cmp.step.start = icmp ult i8* %src.step, %lower + %cmp.step.end = icmp uge i8* %src.step, %upper + %or.check = or i1 %cmp.step.start, %cmp.step.end + br i1 %or.check, label %trap.bb, label %exit + +exit: + ret i4 3 +} + +define i4 @ptr_N_signed_positive_assume(i8* %src, i8* %lower, i8* %upper, i16 %N, i16 %step) { +; CHECK-LABEL: @ptr_N_signed_positive_assume( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SRC_END:%.*]] = getelementptr inbounds i8, i8* [[SRC:%.*]], i16 [[N:%.*]] +; CHECK-NEXT: [[CMP_SRC_START:%.*]] = icmp ult i8* [[SRC]], [[LOWER:%.*]] +; CHECK-NEXT: [[CMP_SRC_END:%.*]] = icmp uge i8* [[SRC_END]], [[UPPER:%.*]] +; CHECK-NEXT: [[N_NEG:%.*]] = icmp slt i16 [[N]], 0 +; CHECK-NEXT: call void @llvm.assume(i1 [[N_NEG]]) +; CHECK-NEXT: [[OR_PRECOND_0:%.*]] = or i1 [[CMP_SRC_START]], [[CMP_SRC_END]] +; CHECK-NEXT: br i1 [[OR_PRECOND_0]], label [[TRAP_BB:%.*]], label [[STEP_CHECK:%.*]] +; CHECK: trap.bb: +; CHECK-NEXT: ret i4 2 +; CHECK: step.check: +; CHECK-NEXT: [[STEP_POS:%.*]] = icmp uge i16 [[STEP:%.*]], 0 +; CHECK-NEXT: [[STEP_ULT_N:%.*]] = icmp ult i16 [[STEP]], [[N]] +; CHECK-NEXT: [[AND_STEP:%.*]] = and i1 [[STEP_POS]], [[STEP_ULT_N]] +; CHECK-NEXT: br i1 [[AND_STEP]], label [[PTR_CHECK:%.*]], label [[EXIT:%.*]] +; CHECK: ptr.check: +; CHECK-NEXT: [[SRC_STEP:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i16 [[STEP]] +; CHECK-NEXT: [[CMP_STEP_START:%.*]] = icmp ult i8* [[SRC_STEP]], [[LOWER]] +; CHECK-NEXT: [[CMP_STEP_END:%.*]] = icmp uge i8* [[SRC_STEP]], [[UPPER]] +; CHECK-NEXT: [[OR_CHECK:%.*]] = or i1 false, false +; CHECK-NEXT: br i1 [[OR_CHECK]], label [[TRAP_BB]], label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret i4 3 +; +entry: + %src.end = getelementptr inbounds i8, i8* %src, i16 %N + %cmp.src.start = icmp ult i8* %src, %lower + %cmp.src.end = icmp uge i8* %src.end, %upper + %N.neg = icmp slt i16 %N, 0 + call void @llvm.assume(i1 %N.neg) + %or.precond.0 = or i1 %cmp.src.start, %cmp.src.end + br i1 %or.precond.0, label %trap.bb, label %step.check + +trap.bb: + ret i4 2 + +step.check: + %step.pos = icmp uge i16 %step, 0 + %step.ult.N = icmp ult i16 %step, %N + %and.step = and i1 %step.pos, %step.ult.N + br i1 %and.step, label %ptr.check, label %exit + +ptr.check: + %src.step = getelementptr inbounds i8, i8* %src, i16 %step + %cmp.step.start = icmp ult i8* %src.step, %lower + %cmp.step.end = icmp uge i8* %src.step, %upper + %or.check = or i1 %cmp.step.start, %cmp.step.end + br i1 %or.check, label %trap.bb, label %exit + +exit: + ret i4 3 +} diff --git a/llvm/test/Transforms/ConstraintElimination/geps.ll b/llvm/test/Transforms/ConstraintElimination/geps.ll index a380d52..0693a5c 100644 --- a/llvm/test/Transforms/ConstraintElimination/geps.ll +++ b/llvm/test/Transforms/ConstraintElimination/geps.ll @@ -91,6 +91,98 @@ exit: ; preds = %check.2.max ret i32 %add9 } +; Same as test.ult, but without inbounds. +define i32 @test.ult_no_inbounds(i32* readonly %src, i32* readnone %min, i32* readnone %max) { +; CHECK-LABEL: @test.ult_no_inbounds( +; CHECK-NEXT: check.0.min: +; CHECK-NEXT: [[C_MIN_0:%.*]] = icmp ult i32* [[SRC:%.*]], [[MIN:%.*]] +; CHECK-NEXT: br i1 [[C_MIN_0]], label [[TRAP:%.*]], label [[CHECK_0_MAX:%.*]] +; CHECK: trap: +; CHECK-NEXT: ret i32 10 +; CHECK: check.0.max: +; CHECK-NEXT: [[C_MAX_0:%.*]] = icmp ult i32* [[SRC]], [[MAX:%.*]] +; CHECK-NEXT: br i1 [[C_MAX_0]], label [[CHECK_3_MIN:%.*]], label [[TRAP]] +; CHECK: check.3.min: +; CHECK-NEXT: [[L0:%.*]] = load i32, i32* [[SRC]], align 4 +; CHECK-NEXT: [[ADD_PTR_I36:%.*]] = getelementptr i32, i32* [[SRC]], i64 3 +; CHECK-NEXT: [[C_3_MIN:%.*]] = icmp ult i32* [[ADD_PTR_I36]], [[MIN]] +; CHECK-NEXT: br i1 false, label [[TRAP]], label [[CHECK_3_MAX:%.*]] +; CHECK: check.3.max: +; CHECK-NEXT: [[C_3_MAX:%.*]] = icmp ult i32* [[ADD_PTR_I36]], [[MAX]] +; CHECK-NEXT: br i1 [[C_3_MAX]], label [[CHECK_1_MIN:%.*]], label [[TRAP]] +; CHECK: check.1.min: +; CHECK-NEXT: [[L1:%.*]] = load i32, i32* [[ADD_PTR_I36]], align 4 +; CHECK-NEXT: [[ADD_PTR_I29:%.*]] = getelementptr i32, i32* [[SRC]], i64 1 +; CHECK-NEXT: [[C_1_MIN:%.*]] = icmp ult i32* [[ADD_PTR_I29]], [[MIN]] +; CHECK-NEXT: br i1 false, label [[TRAP]], label [[CHECK_1_MAX:%.*]] +; CHECK: check.1.max: +; CHECK-NEXT: [[C_1_MAX:%.*]] = icmp ult i32* [[ADD_PTR_I29]], [[MAX]] +; CHECK-NEXT: br i1 true, label [[CHECK_2_MIN:%.*]], label [[TRAP]] +; CHECK: check.2.min: +; CHECK-NEXT: [[L2:%.*]] = load i32, i32* [[ADD_PTR_I29]], align 4 +; CHECK-NEXT: [[ADD_PTR_I:%.*]] = getelementptr i32, i32* [[SRC]], i64 2 +; CHECK-NEXT: [[C_2_MIN:%.*]] = icmp ult i32* [[ADD_PTR_I]], [[MIN]] +; CHECK-NEXT: br i1 false, label [[TRAP]], label [[CHECK_2_MAX:%.*]] +; CHECK: check.2.max: +; CHECK-NEXT: [[C_2_MAX:%.*]] = icmp ult i32* [[ADD_PTR_I]], [[MAX]] +; CHECK-NEXT: br i1 true, label [[EXIT:%.*]], label [[TRAP]] +; CHECK: exit: +; CHECK-NEXT: [[L3:%.*]] = load i32, i32* [[ADD_PTR_I]], align 4 +; CHECK-NEXT: [[ADD:%.*]] = add nsw i32 [[L1]], [[L0]] +; CHECK-NEXT: [[ADD8:%.*]] = add nsw i32 [[ADD]], [[L2]] +; CHECK-NEXT: [[ADD9:%.*]] = add nsw i32 [[ADD8]], [[L3]] +; CHECK-NEXT: ret i32 [[ADD9]] +; +check.0.min: + %c.min.0 = icmp ult i32* %src, %min + br i1 %c.min.0, label %trap, label %check.0.max + +trap: ; preds = %check.2.max, %check.2.min, %check.1.max, %check.1.min, %check.3.max, %check.3.min, %check.0.max, %check.0.min + ret i32 10 + +check.0.max: ; preds = %check.0.min + %c.max.0 = icmp ult i32* %src, %max + br i1 %c.max.0, label %check.3.min, label %trap + +check.3.min: ; preds = %check.0.max + %l0 = load i32, i32* %src, align 4 + %add.ptr.i36 = getelementptr i32, i32* %src, i64 3 + %c.3.min = icmp ult i32* %add.ptr.i36, %min + br i1 %c.3.min, label %trap, label %check.3.max + +check.3.max: ; preds = %check.3.min + %c.3.max = icmp ult i32* %add.ptr.i36, %max + br i1 %c.3.max, label %check.1.min, label %trap + +check.1.min: ; preds = %check.3.max + %l1 = load i32, i32* %add.ptr.i36, align 4 + %add.ptr.i29 = getelementptr i32, i32* %src, i64 1 + %c.1.min = icmp ult i32* %add.ptr.i29, %min + br i1 %c.1.min, label %trap, label %check.1.max + +check.1.max: ; preds = %check.1.min + %c.1.max = icmp ult i32* %add.ptr.i29, %max + br i1 %c.1.max, label %check.2.min, label %trap + +check.2.min: ; preds = %check.1.max + %l2 = load i32, i32* %add.ptr.i29, align 4 + %add.ptr.i = getelementptr i32, i32* %src, i64 2 + %c.2.min = icmp ult i32* %add.ptr.i, %min + br i1 %c.2.min, label %trap, label %check.2.max + +check.2.max: ; preds = %check.2.min + %c.2.max = icmp ult i32* %add.ptr.i, %max + br i1 %c.2.max, label %exit, label %trap + +exit: ; preds = %check.2.max + %l3 = load i32, i32* %add.ptr.i, align 4 + %add = add nsw i32 %l1, %l0 + %add8 = add nsw i32 %add, %l2 + %add9 = add nsw i32 %add8, %l3 + ret i32 %add9 +} + + define void @test.not.uge.ult(i8* %start, i8* %low, i8* %high) { ; CHECK-LABEL: @test.not.uge.ult( ; CHECK-NEXT: entry: @@ -142,6 +234,58 @@ if.end: ; preds = %entry ret void } +; Same as test.not.uge.ult, but without inbounds GEPs. +define void @test.not.uge.ult_no_inbounds(i8* %start, i8* %low, i8* %high) { +; CHECK-LABEL: @test.not.uge.ult_no_inbounds( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[ADD_PTR_I:%.*]] = getelementptr i8, i8* [[START:%.*]], i64 3 +; CHECK-NEXT: [[C_1:%.*]] = icmp uge i8* [[ADD_PTR_I]], [[HIGH:%.*]] +; CHECK-NEXT: br i1 [[C_1]], label [[IF_THEN:%.*]], label [[IF_END:%.*]] +; CHECK: if.then: +; CHECK-NEXT: ret void +; CHECK: if.end: +; CHECK-NEXT: [[T_0:%.*]] = icmp ult i8* [[START]], [[HIGH]] +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: [[START_1:%.*]] = getelementptr i8, i8* [[START]], i64 1 +; CHECK-NEXT: [[T_1:%.*]] = icmp ult i8* [[START_1]], [[HIGH]] +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: [[START_2:%.*]] = getelementptr i8, i8* [[START]], i64 2 +; CHECK-NEXT: [[T_2:%.*]] = icmp ult i8* [[START_2]], [[HIGH]] +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: [[START_3:%.*]] = getelementptr i8, i8* [[START]], i64 3 +; CHECK-NEXT: [[T_3:%.*]] = icmp ult i8* [[START_3]], [[HIGH]] +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: [[START_4:%.*]] = getelementptr i8, i8* [[START]], i64 4 +; CHECK-NEXT: [[C_4:%.*]] = icmp ult i8* [[START_4]], [[HIGH]] +; CHECK-NEXT: call void @use(i1 [[C_4]]) +; CHECK-NEXT: ret void +; +entry: + %add.ptr.i = getelementptr i8, i8* %start, i64 3 + %c.1 = icmp uge i8* %add.ptr.i, %high + br i1 %c.1, label %if.then, label %if.end + +if.then: ; preds = %entry + ret void + +if.end: ; preds = %entry + %t.0 = icmp ult i8* %start, %high + call void @use(i1 %t.0) + %start.1 = getelementptr i8, i8* %start, i64 1 + %t.1 = icmp ult i8* %start.1, %high + call void @use(i1 %t.1) + %start.2 = getelementptr i8, i8* %start, i64 2 + %t.2 = icmp ult i8* %start.2, %high + call void @use(i1 %t.2) + %start.3 = getelementptr i8, i8* %start, i64 3 + %t.3 = icmp ult i8* %start.3, %high + call void @use(i1 %t.3) + %start.4 = getelementptr i8, i8* %start, i64 4 + %c.4 = icmp ult i8* %start.4, %high + call void @use(i1 %c.4) + ret void +} + define void @test.not.uge.ule(i8* %start, i8* %low, i8* %high) { ; CHECK-LABEL: @test.not.uge.ule( ; CHECK-NEXT: entry: @@ -503,4 +647,3 @@ check.max: ; preds = %check.0.min } declare void @use(i1) -declare void @llvm.trap() diff --git a/llvm/test/Transforms/ConstraintElimination/loops-bottom-tested-base.ll b/llvm/test/Transforms/ConstraintElimination/loops-bottom-tested-base.ll new file mode 100644 index 0000000..ca103c2 --- /dev/null +++ b/llvm/test/Transforms/ConstraintElimination/loops-bottom-tested-base.ll @@ -0,0 +1,98 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -constraint-elimination -S %s | FileCheck %s + +declare void @use(i1) + +define void @loop_iv_cond_variable_bound(i32 %n) { +; CHECK-LABEL: @loop_iv_cond_variable_bound( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ] +; CHECK-NEXT: [[T_1:%.*]] = icmp ule i32 [[IV]], [[N:%.*]] +; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: [[T_2:%.*]] = icmp sge i32 [[IV]], 0 +; CHECK-NEXT: call void @use(i1 [[T_2]]) +; CHECK-NEXT: [[T_3:%.*]] = icmp sge i32 [[IV]], -1 +; CHECK-NEXT: call void @use(i1 [[T_3]]) +; CHECK-NEXT: [[C_1:%.*]] = icmp ult i32 [[IV]], [[N]] +; CHECK-NEXT: call void @use(i1 [[C_1]]) +; CHECK-NEXT: [[C_2:%.*]] = icmp ugt i32 [[IV]], 1 +; CHECK-NEXT: call void @use(i1 [[C_2]]) +; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[IV]], [[N]] +; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 +; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ] + %t.1 = icmp ule i32 %iv, %n + call void @use(i1 %t.1) + %t.2 = icmp sge i32 %iv, 0 + call void @use(i1 %t.2) + %t.3 = icmp sge i32 %iv, -1 + call void @use(i1 %t.3) + + %c.1 = icmp ult i32 %iv, %n + call void @use(i1 %c.1) + %c.2 = icmp ugt i32 %iv, 1 + call void @use(i1 %c.2) + + %cmp = icmp ult i32 %iv, %n + %iv.next = add nuw nsw i32 %iv, 1 + br i1 %cmp, label %loop, label %exit + +exit: + ret void +} + +define void @loop_iv_cond_constant_bound() { +; CHECK-LABEL: @loop_iv_cond_constant_bound( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP:%.*]] +; CHECK: loop: +; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ] +; CHECK-NEXT: [[T_1:%.*]] = icmp ule i32 [[IV]], 2 +; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: [[T_2:%.*]] = icmp sge i32 [[IV]], 0 +; CHECK-NEXT: call void @use(i1 [[T_2]]) +; CHECK-NEXT: [[T_3:%.*]] = icmp sge i32 [[IV]], -1 +; CHECK-NEXT: call void @use(i1 [[T_3]]) +; CHECK-NEXT: [[C_1:%.*]] = icmp ult i32 [[IV]], 2 +; CHECK-NEXT: call void @use(i1 [[C_1]]) +; CHECK-NEXT: [[C_2:%.*]] = icmp ugt i32 [[IV]], 1 +; CHECK-NEXT: call void @use(i1 [[C_2]]) +; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[IV]], 2 +; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 +; CHECK-NEXT: br i1 [[CMP]], label [[LOOP]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop + +loop: + %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ] + %t.1 = icmp ule i32 %iv, 2 + call void @use(i1 %t.1) + %t.2 = icmp sge i32 %iv, 0 + call void @use(i1 %t.2) + %t.3 = icmp sge i32 %iv, -1 + call void @use(i1 %t.3) + + %c.1 = icmp ult i32 %iv, 2 + call void @use(i1 %c.1) + %c.2 = icmp ugt i32 %iv, 1 + call void @use(i1 %c.2) + + %cmp = icmp ult i32 %iv, 2 + %iv.next = add nuw nsw i32 %iv, 1 + br i1 %cmp, label %loop, label %exit + +exit: + ret void +} diff --git a/llvm/test/Transforms/ConstraintElimination/loops-bottom-tested-pointer-cmps.ll b/llvm/test/Transforms/ConstraintElimination/loops-bottom-tested-pointer-cmps.ll new file mode 100644 index 0000000..d703a5f --- /dev/null +++ b/llvm/test/Transforms/ConstraintElimination/loops-bottom-tested-pointer-cmps.ll @@ -0,0 +1,223 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -constraint-elimination -S %s | FileCheck %s + +declare void @use(i1) +define void @checks_in_loops_removable(i8* %ptr, i8* %lower, i8* %upper, i32 %n) { +; CHECK-LABEL: @checks_in_loops_removable( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CMP_PTR_LOWER:%.*]] = icmp ult i8* [[PTR:%.*]], [[LOWER:%.*]] +; CHECK-NEXT: br i1 [[CMP_PTR_LOWER]], label [[TRAP:%.*]], label [[PRE_1:%.*]] +; CHECK: pre.1: +; CHECK-NEXT: [[IDX_EXT:%.*]] = zext i32 [[N:%.*]] to i64 +; CHECK-NEXT: [[PTR_N:%.*]] = getelementptr inbounds i8, i8* [[PTR]], i64 [[IDX_EXT]] +; CHECK-NEXT: [[CMP_PTR_N_UPPER:%.*]] = icmp ult i8* [[PTR_N]], [[UPPER:%.*]] +; CHECK-NEXT: br i1 [[CMP_PTR_N_UPPER]], label [[PRE_2:%.*]], label [[TRAP]] +; CHECK: pre.2: +; CHECK-NEXT: [[CMP_N_NOT_ZERO:%.*]] = icmp eq i32 [[N]], 0 +; CHECK-NEXT: br i1 [[CMP_N_NOT_ZERO]], label [[EXIT:%.*]], label [[LOOP_HEADER:%.*]] +; CHECK: trap: +; CHECK-NEXT: ret void +; CHECK: loop.header: +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[PRE_2]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ] +; CHECK-NEXT: [[PTR_IV:%.*]] = getelementptr inbounds i8, i8* [[PTR]], i64 [[IV]] +; CHECK-NEXT: [[CMP_PTR_IV_LOWER:%.*]] = icmp ugt i8* [[LOWER]], [[PTR_IV]] +; CHECK-NEXT: [[CMP_PTR_IV_UPPER:%.*]] = icmp ule i8* [[UPPER]], [[PTR_IV]] +; CHECK-NEXT: [[OR:%.*]] = or i1 [[CMP_PTR_IV_LOWER]], [[CMP_PTR_IV_UPPER]] +; CHECK-NEXT: br i1 [[OR]], label [[TRAP]], label [[LOOP_LATCH]] +; CHECK: loop.latch: +; CHECK-NEXT: store i8 0, i8* [[PTR_IV]], align 4 +; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1 +; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i64 [[IV_NEXT]], [[IDX_EXT]] +; CHECK-NEXT: br i1 [[EXITCOND]], label [[LOOP_HEADER]], label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + %cmp.ptr.lower = icmp ult i8* %ptr, %lower + br i1 %cmp.ptr.lower, label %trap, label %pre.1 + +pre.1: + %idx.ext = zext i32 %n to i64 + %ptr.n = getelementptr inbounds i8, i8* %ptr, i64 %idx.ext + %cmp.ptr.n.upper = icmp ult i8* %ptr.n, %upper + br i1 %cmp.ptr.n.upper, label %pre.2, label %trap + +pre.2: + %cmp.n.not.zero = icmp eq i32 %n, 0 + br i1 %cmp.n.not.zero, label %exit, label %loop.header + +trap: + ret void + +loop.header: + %iv = phi i64 [ 0, %pre.2 ], [ %iv.next, %loop.latch ] + %ptr.iv = getelementptr inbounds i8, i8* %ptr, i64 %iv + %cmp.ptr.iv.lower = icmp ugt i8* %lower, %ptr.iv + %cmp.ptr.iv.upper = icmp ule i8* %upper, %ptr.iv + %or = or i1 %cmp.ptr.iv.lower, %cmp.ptr.iv.upper + br i1 %or, label %trap, label %loop.latch + +loop.latch: + store i8 0, i8* %ptr.iv, align 4 + %iv.next = add nuw nsw i64 %iv, 1 + %exitcond = icmp ne i64 %iv.next, %idx.ext + br i1 %exitcond, label %loop.header, label %exit + +exit: + ret void +} + +define void @some_checks_in_loops_removable(i8* %ptr, i8* %lower, i8* %upper, i32 %n) { +; CHECK-LABEL: @some_checks_in_loops_removable( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CMP_PTR_LOWER:%.*]] = icmp ult i8* [[PTR:%.*]], [[LOWER:%.*]] +; CHECK-NEXT: br i1 [[CMP_PTR_LOWER]], label [[TRAP:%.*]], label [[PRE_1:%.*]] +; CHECK: pre.1: +; CHECK-NEXT: [[IDX_EXT:%.*]] = zext i32 [[N:%.*]] to i64 +; CHECK-NEXT: [[PTR_N:%.*]] = getelementptr inbounds i8, i8* [[PTR]], i64 [[IDX_EXT]] +; CHECK-NEXT: [[CMP_PTR_N_UPPER:%.*]] = icmp ult i8* [[PTR_N]], [[UPPER:%.*]] +; CHECK-NEXT: br i1 [[CMP_PTR_N_UPPER]], label [[PRE_2:%.*]], label [[TRAP]] +; CHECK: pre.2: +; CHECK-NEXT: [[CMP_N_NOT_ZERO:%.*]] = icmp eq i32 [[N]], 0 +; CHECK-NEXT: br i1 [[CMP_N_NOT_ZERO]], label [[EXIT:%.*]], label [[LOOP_HEADER:%.*]] +; CHECK: trap: +; CHECK-NEXT: ret void +; CHECK: loop.header: +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[PRE_2]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ] +; CHECK-NEXT: [[PTR_IV:%.*]] = getelementptr inbounds i8, i8* [[PTR]], i64 [[IV]] +; CHECK-NEXT: [[CMP_PTR_IV_LOWER:%.*]] = icmp ugt i8* [[LOWER]], [[PTR_IV]] +; CHECK-NEXT: [[CMP_PTR_IV_UPPER:%.*]] = icmp ule i8* [[UPPER]], [[PTR_IV]] +; CHECK-NEXT: [[OR:%.*]] = or i1 [[CMP_PTR_IV_LOWER]], [[CMP_PTR_IV_UPPER]] +; CHECK-NEXT: br i1 [[OR]], label [[TRAP]], label [[LOOP_BODY:%.*]] +; CHECK: loop.body: +; CHECK-NEXT: [[IV_1:%.*]] = add nuw nsw i64 [[IV]], 1 +; CHECK-NEXT: [[PTR_IV_1:%.*]] = getelementptr inbounds i8, i8* [[PTR]], i64 [[IV_1]] +; CHECK-NEXT: [[CMP_PTR_IV_1_LOWER:%.*]] = icmp ugt i8* [[LOWER]], [[PTR_IV_1]] +; CHECK-NEXT: [[CMP_PTR_IV_1_UPPER:%.*]] = icmp ule i8* [[UPPER]], [[PTR_IV_1]] +; CHECK-NEXT: [[OR_1:%.*]] = or i1 [[CMP_PTR_IV_1_LOWER]], [[CMP_PTR_IV_1_UPPER]] +; CHECK-NEXT: br i1 [[OR]], label [[TRAP]], label [[LOOP_LATCH]] +; CHECK: loop.latch: +; CHECK-NEXT: store i8 0, i8* [[PTR_IV]], align 4 +; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1 +; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i64 [[IV_NEXT]], [[IDX_EXT]] +; CHECK-NEXT: br i1 [[EXITCOND]], label [[LOOP_HEADER]], label [[EXIT]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + %cmp.ptr.lower = icmp ult i8* %ptr, %lower + br i1 %cmp.ptr.lower, label %trap, label %pre.1 + +pre.1: + %idx.ext = zext i32 %n to i64 + %ptr.n = getelementptr inbounds i8, i8* %ptr, i64 %idx.ext + %cmp.ptr.n.upper = icmp ult i8* %ptr.n, %upper + br i1 %cmp.ptr.n.upper, label %pre.2, label %trap + +pre.2: + %cmp.n.not.zero = icmp eq i32 %n, 0 + br i1 %cmp.n.not.zero, label %exit, label %loop.header + +trap: + ret void + +loop.header: + %iv = phi i64 [ 0, %pre.2 ], [ %iv.next, %loop.latch ] + %ptr.iv = getelementptr inbounds i8, i8* %ptr, i64 %iv + %cmp.ptr.iv.lower = icmp ugt i8* %lower, %ptr.iv + %cmp.ptr.iv.upper = icmp ule i8* %upper, %ptr.iv + %or = or i1 %cmp.ptr.iv.lower, %cmp.ptr.iv.upper + br i1 %or, label %trap, label %loop.body + +loop.body: + %iv.1 = add nuw nsw i64 %iv, 1 + %ptr.iv.1 = getelementptr inbounds i8, i8* %ptr, i64 %iv.1 + %cmp.ptr.iv.1.lower = icmp ugt i8* %lower, %ptr.iv.1 + %cmp.ptr.iv.1.upper = icmp ule i8* %upper, %ptr.iv.1 + %or.1 = or i1 %cmp.ptr.iv.1.lower, %cmp.ptr.iv.1.upper + br i1 %or, label %trap, label %loop.latch + +loop.latch: + store i8 0, i8* %ptr.iv, align 4 + %iv.next = add nuw nsw i64 %iv, 1 + %exitcond = icmp ne i64 %iv.next, %idx.ext + br i1 %exitcond, label %loop.header, label %exit + +exit: + ret void +} + + +; N might be zero, cannot remove upper checks. +define void @no_checks_in_loops_removable(i8* %ptr, i8* %lower, i8* %upper, i32 %n) { +; CHECK-LABEL: @no_checks_in_loops_removable( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CMP_PTR_LOWER:%.*]] = icmp ult i8* [[PTR:%.*]], [[LOWER:%.*]] +; CHECK-NEXT: br i1 [[CMP_PTR_LOWER]], label [[TRAP:%.*]], label [[PRE_1:%.*]] +; CHECK: pre.1: +; CHECK-NEXT: [[IDX_EXT:%.*]] = zext i32 [[N:%.*]] to i64 +; CHECK-NEXT: [[PTR_N:%.*]] = getelementptr inbounds i8, i8* [[PTR]], i64 [[IDX_EXT]] +; CHECK-NEXT: [[CMP_PTR_N_UPPER:%.*]] = icmp ult i8* [[PTR_N]], [[UPPER:%.*]] +; CHECK-NEXT: br i1 [[CMP_PTR_N_UPPER]], label [[LOOP_HEADER:%.*]], label [[TRAP]] +; CHECK: trap: +; CHECK-NEXT: ret void +; CHECK: loop.header: +; CHECK-NEXT: [[IV:%.*]] = phi i64 [ 0, [[PRE_1]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ] +; CHECK-NEXT: [[PTR_IV:%.*]] = getelementptr inbounds i8, i8* [[PTR]], i64 [[IV]] +; CHECK-NEXT: [[CMP_PTR_IV_LOWER:%.*]] = icmp ugt i8* [[LOWER]], [[PTR_IV]] +; CHECK-NEXT: [[CMP_PTR_IV_UPPER:%.*]] = icmp ule i8* [[UPPER]], [[PTR_IV]] +; CHECK-NEXT: [[OR:%.*]] = or i1 [[CMP_PTR_IV_LOWER]], [[CMP_PTR_IV_UPPER]] +; CHECK-NEXT: br i1 [[OR]], label [[TRAP]], label [[LOOP_BODY:%.*]] +; CHECK: loop.body: +; CHECK-NEXT: [[IV_1:%.*]] = add nuw nsw i64 [[IV]], 1 +; CHECK-NEXT: [[PTR_IV_1:%.*]] = getelementptr inbounds i8, i8* [[PTR]], i64 [[IV_1]] +; CHECK-NEXT: [[CMP_PTR_IV_1_LOWER:%.*]] = icmp ugt i8* [[LOWER]], [[PTR_IV_1]] +; CHECK-NEXT: [[CMP_PTR_IV_1_UPPER:%.*]] = icmp ule i8* [[UPPER]], [[PTR_IV_1]] +; CHECK-NEXT: [[OR_1:%.*]] = or i1 [[CMP_PTR_IV_1_LOWER]], [[CMP_PTR_IV_1_UPPER]] +; CHECK-NEXT: br i1 [[OR]], label [[TRAP]], label [[LOOP_LATCH]] +; CHECK: loop.latch: +; CHECK-NEXT: store i8 0, i8* [[PTR_IV]], align 4 +; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i64 [[IV]], 1 +; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i64 [[IV_NEXT]], [[IDX_EXT]] +; CHECK-NEXT: br i1 [[EXITCOND]], label [[LOOP_HEADER]], label [[EXIT:%.*]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + %cmp.ptr.lower = icmp ult i8* %ptr, %lower + br i1 %cmp.ptr.lower, label %trap, label %pre.1 + +pre.1: + %idx.ext = zext i32 %n to i64 + %ptr.n = getelementptr inbounds i8, i8* %ptr, i64 %idx.ext + %cmp.ptr.n.upper = icmp ult i8* %ptr.n, %upper + br i1 %cmp.ptr.n.upper, label %loop.header, label %trap + +trap: + ret void + +loop.header: + %iv = phi i64 [ 0, %pre.1 ], [ %iv.next, %loop.latch ] + %ptr.iv = getelementptr inbounds i8, i8* %ptr, i64 %iv + %cmp.ptr.iv.lower = icmp ugt i8* %lower, %ptr.iv + %cmp.ptr.iv.upper = icmp ule i8* %upper, %ptr.iv + %or = or i1 %cmp.ptr.iv.lower, %cmp.ptr.iv.upper + br i1 %or, label %trap, label %loop.body + +loop.body: + %iv.1 = add nuw nsw i64 %iv, 1 + %ptr.iv.1 = getelementptr inbounds i8, i8* %ptr, i64 %iv.1 + %cmp.ptr.iv.1.lower = icmp ugt i8* %lower, %ptr.iv.1 + %cmp.ptr.iv.1.upper = icmp ule i8* %upper, %ptr.iv.1 + %or.1 = or i1 %cmp.ptr.iv.1.lower, %cmp.ptr.iv.1.upper + br i1 %or, label %trap, label %loop.latch + +loop.latch: + store i8 0, i8* %ptr.iv, align 4 + %iv.next = add nuw nsw i64 %iv, 1 + %exitcond = icmp ne i64 %iv.next, %idx.ext + br i1 %exitcond, label %loop.header, label %exit + +exit: + ret void +} diff --git a/llvm/test/Transforms/ConstraintElimination/loops-header-tested-base.ll b/llvm/test/Transforms/ConstraintElimination/loops-header-tested-base.ll new file mode 100644 index 0000000..b9e8e6f --- /dev/null +++ b/llvm/test/Transforms/ConstraintElimination/loops-header-tested-base.ll @@ -0,0 +1,437 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -constraint-elimination -S %s | FileCheck %s + +declare void @use(i1) + +define void @loop_phi_pos_start_value(i32 %y, i1 %c, i32 %n) { +; CHECK-LABEL: @loop_phi_pos_start_value( +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 [[C:%.*]], label [[LOOP_HEADER:%.*]], label [[EXIT:%.*]] +; CHECK: loop.header: +; CHECK-NEXT: [[X:%.*]] = phi i32 [ 10, [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP_LATCH:%.*]] ] +; CHECK-NEXT: [[C_1:%.*]] = icmp slt i32 [[X]], [[N:%.*]] +; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_LATCH]], label [[EXIT]] +; CHECK: loop.latch: +; CHECK-NEXT: [[F_1:%.*]] = icmp sle i32 [[X]], [[N]] +; CHECK-NEXT: call void @use(i1 [[F_1]]) +; CHECK-NEXT: [[T_1:%.*]] = icmp sgt i32 [[X]], [[N]] +; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: [[T_2:%.*]] = icmp sge i32 [[X]], 10 +; CHECK-NEXT: call void @use(i1 [[T_2]]) +; CHECK-NEXT: [[C_2:%.*]] = icmp sle i32 [[X]], 9 +; CHECK-NEXT: call void @use(i1 [[C_2]]) +; CHECK-NEXT: [[C_3:%.*]] = icmp sgt i32 [[X]], 9 +; CHECK-NEXT: call void @use(i1 [[C_3]]) +; CHECK-NEXT: [[C_4:%.*]] = icmp sge i32 [[X]], 0 +; CHECK-NEXT: call void @use(i1 [[C_4]]) +; CHECK-NEXT: [[C_5:%.*]] = icmp sge i32 [[X]], 9 +; CHECK-NEXT: call void @use(i1 [[C_5]]) +; CHECK-NEXT: [[X_NEXT]] = add nsw i32 [[X]], 1 +; CHECK-NEXT: br label [[LOOP_HEADER]] +; CHECK: exit: +; CHECK-NEXT: [[C_6:%.*]] = icmp sgt i32 [[Y:%.*]], 10 +; CHECK-NEXT: call void @use(i1 [[C_6]]) +; CHECK-NEXT: ret void +; +entry: + br i1 %c, label %loop.header, label %exit + +loop.header: + %x = phi i32 [ 10, %entry ], [ %x.next, %loop.latch ] + %c.1 = icmp slt i32 %x, %n + br i1 %c.1, label %loop.latch, label %exit + +loop.latch: + %f.1 = icmp sle i32 %x, %n + call void @use(i1 %f.1) + %t.1 = icmp sgt i32 %x, %n + call void @use(i1 %t.1) + %t.2 = icmp sge i32 %x, 10 + call void @use(i1 %t.2) + + %c.2 = icmp sle i32 %x, 9 + call void @use(i1 %c.2) + %c.3 = icmp sgt i32 %x, 9 + call void @use(i1 %c.3) + %c.4 = icmp sge i32 %x, 0 + call void @use(i1 %c.4) + %c.5 = icmp sge i32 %x, 9 + call void @use(i1 %c.5) + + %x.next = add nsw i32 %x, 1 + br label %loop.header + +exit: + %c.6 = icmp sgt i32 %y, 10 + call void @use(i1 %c.6) + ret void +} + +define void @loop_phi_neg_start_value(i32 %y, i1 %c, i32 %n) { +; CHECK-LABEL: @loop_phi_neg_start_value( +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 [[C:%.*]], label [[LOOP_HEADER:%.*]], label [[EXIT:%.*]] +; CHECK: loop.header: +; CHECK-NEXT: [[X:%.*]] = phi i32 [ -10, [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP_LATCH:%.*]] ] +; CHECK-NEXT: [[C_1:%.*]] = icmp slt i32 [[X]], [[N:%.*]] +; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_LATCH]], label [[EXIT]] +; CHECK: loop.latch: +; CHECK-NEXT: [[F_1:%.*]] = icmp sle i32 [[X]], [[N]] +; CHECK-NEXT: call void @use(i1 [[F_1]]) +; CHECK-NEXT: [[T_1:%.*]] = icmp sgt i32 [[X]], [[N]] +; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: [[T_2:%.*]] = icmp sge i32 [[X]], -10 +; CHECK-NEXT: call void @use(i1 [[T_2]]) +; CHECK-NEXT: [[C_2:%.*]] = icmp sle i32 [[X]], 9 +; CHECK-NEXT: call void @use(i1 [[C_2]]) +; CHECK-NEXT: [[C_3:%.*]] = icmp sgt i32 [[X]], 9 +; CHECK-NEXT: call void @use(i1 [[C_3]]) +; CHECK-NEXT: [[C_4:%.*]] = icmp sge i32 [[X]], 0 +; CHECK-NEXT: call void @use(i1 [[C_4]]) +; CHECK-NEXT: [[C_5:%.*]] = icmp sge i32 [[X]], 9 +; CHECK-NEXT: call void @use(i1 [[C_5]]) +; CHECK-NEXT: [[X_NEXT]] = add nsw i32 [[X]], 1 +; CHECK-NEXT: br label [[LOOP_HEADER]] +; CHECK: exit: +; CHECK-NEXT: [[C_6:%.*]] = icmp sgt i32 [[Y:%.*]], 10 +; CHECK-NEXT: call void @use(i1 [[C_6]]) +; CHECK-NEXT: ret void +; +entry: + br i1 %c, label %loop.header, label %exit + +loop.header: + %x = phi i32 [ -10, %entry ], [ %x.next, %loop.latch ] + %c.1 = icmp slt i32 %x, %n + br i1 %c.1, label %loop.latch, label %exit + +loop.latch: + %f.1 = icmp sle i32 %x, %n + call void @use(i1 %f.1) + %t.1 = icmp sgt i32 %x, %n + call void @use(i1 %t.1) + %t.2 = icmp sge i32 %x, -10 + call void @use(i1 %t.2) + + %c.2 = icmp sle i32 %x, 9 + call void @use(i1 %c.2) + %c.3 = icmp sgt i32 %x, 9 + call void @use(i1 %c.3) + %c.4 = icmp sge i32 %x, 0 + call void @use(i1 %c.4) + %c.5 = icmp sge i32 %x, 9 + call void @use(i1 %c.5) + + %x.next = add nsw i32 %x, 1 + br label %loop.header + +exit: + %c.6 = icmp sgt i32 %y, 10 + call void @use(i1 %c.6) + ret void +} + +define void @loop_count_down(i32 %y, i1 %c, i32 %n) { +; CHECK-LABEL: @loop_count_down( +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 [[C:%.*]], label [[LOOP_HEADER:%.*]], label [[EXIT:%.*]] +; CHECK: loop.header: +; CHECK-NEXT: [[X:%.*]] = phi i32 [ [[N:%.*]], [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP_LATCH:%.*]] ] +; CHECK-NEXT: [[C_1:%.*]] = icmp sge i32 [[X]], 0 +; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_LATCH]], label [[EXIT]] +; CHECK: loop.latch: +; CHECK-NEXT: [[F_1:%.*]] = icmp sle i32 [[X]], [[N]] +; CHECK-NEXT: call void @use(i1 [[F_1]]) +; CHECK-NEXT: [[T_1:%.*]] = icmp sgt i32 [[X]], [[N]] +; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: [[T_2:%.*]] = icmp sge i32 [[X]], 0 +; CHECK-NEXT: call void @use(i1 [[T_2]]) +; CHECK-NEXT: [[T_3:%.*]] = icmp sge i32 [[X]], -1 +; CHECK-NEXT: call void @use(i1 [[T_3]]) +; CHECK-NEXT: [[C_2:%.*]] = icmp sle i32 [[X]], 9 +; CHECK-NEXT: call void @use(i1 [[C_2]]) +; CHECK-NEXT: [[C_3:%.*]] = icmp sgt i32 [[X]], 9 +; CHECK-NEXT: call void @use(i1 [[C_3]]) +; CHECK-NEXT: [[C_4:%.*]] = icmp sge i32 [[X]], 1 +; CHECK-NEXT: call void @use(i1 [[C_4]]) +; CHECK-NEXT: [[C_5:%.*]] = icmp sge i32 [[X]], 2 +; CHECK-NEXT: call void @use(i1 [[C_5]]) +; CHECK-NEXT: [[X_NEXT]] = add nsw i32 [[X]], 1 +; CHECK-NEXT: br label [[LOOP_HEADER]] +; CHECK: exit: +; CHECK-NEXT: [[C_6:%.*]] = icmp sgt i32 [[Y:%.*]], 10 +; CHECK-NEXT: call void @use(i1 [[C_6]]) +; CHECK-NEXT: ret void +; +entry: + br i1 %c, label %loop.header, label %exit + +loop.header: + %x = phi i32 [ %n, %entry ], [ %x.next, %loop.latch ] + %c.1 = icmp sge i32 %x, 0 + br i1 %c.1, label %loop.latch, label %exit + +loop.latch: + %f.1 = icmp sle i32 %x, %n + call void @use(i1 %f.1) + %t.1 = icmp sgt i32 %x, %n + call void @use(i1 %t.1) + %t.2 = icmp sge i32 %x, 0 + call void @use(i1 %t.2) + %t.3 = icmp sge i32 %x, -1 + call void @use(i1 %t.3) + + %c.2 = icmp sle i32 %x, 9 + call void @use(i1 %c.2) + %c.3 = icmp sgt i32 %x, 9 + call void @use(i1 %c.3) + %c.4 = icmp sge i32 %x, 1 + call void @use(i1 %c.4) + %c.5 = icmp sge i32 %x, 2 + call void @use(i1 %c.5) + + %x.next = add nsw i32 %x, 1 + br label %loop.header + +exit: + %c.6 = icmp sgt i32 %y, 10 + call void @use(i1 %c.6) + ret void +} + +define void @loop_latch_may_not_executed(i32 %y, i1 %c, i32 %n) { +; CHECK-LABEL: @loop_latch_may_not_executed( +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 [[C:%.*]], label [[LOOP_HEADER:%.*]], label [[EXIT:%.*]] +; CHECK: loop.header: +; CHECK-NEXT: [[X:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP_LATCH:%.*]] ] +; CHECK-NEXT: [[C_1:%.*]] = icmp ugt i32 [[X]], [[N:%.*]] +; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_LATCH]], label [[EXIT]] +; CHECK: loop.latch: +; CHECK-NEXT: [[F_1:%.*]] = icmp ule i32 [[X]], [[N]] +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: [[T_1:%.*]] = icmp ugt i32 [[X]], [[N]] +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: [[C_2:%.*]] = icmp ule i32 [[X]], 9 +; CHECK-NEXT: call void @use(i1 [[C_2]]) +; CHECK-NEXT: [[C_3:%.*]] = icmp ugt i32 [[X]], 9 +; CHECK-NEXT: call void @use(i1 [[C_3]]) +; CHECK-NEXT: [[X_NEXT]] = add i32 [[X]], 1 +; CHECK-NEXT: br label [[LOOP_HEADER]] +; CHECK: exit: +; CHECK-NEXT: [[C_4:%.*]] = icmp ugt i32 [[Y:%.*]], 10 +; CHECK-NEXT: call void @use(i1 [[C_4]]) +; CHECK-NEXT: ret void +; +entry: + br i1 %c, label %loop.header, label %exit + +loop.header: + %x = phi i32 [ 0, %entry ], [ %x.next, %loop.latch ] + %c.1 = icmp ugt i32 %x, %n + br i1 %c.1, label %loop.latch, label %exit + +loop.latch: + %f.1 = icmp ule i32 %x, %n + call void @use(i1 %f.1) + %t.1 = icmp ugt i32 %x, %n + call void @use(i1 %t.1) + + %c.2 = icmp ule i32 %x, 9 + call void @use(i1 %c.2) + %c.3 = icmp ugt i32 %x, 9 + call void @use(i1 %c.3) + + %x.next = add i32 %x, 1 + br label %loop.header + +exit: + %c.4 = icmp ugt i32 %y, 10 + call void @use(i1 %c.4) + ret void +} + +define void @loop_latch_not_executed_constant_bound(i32 %y, i1 %c) { +; CHECK-LABEL: @loop_latch_not_executed_constant_bound( +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 [[C:%.*]], label [[LOOP_HEADER:%.*]], label [[EXIT:%.*]] +; CHECK: loop.header: +; CHECK-NEXT: [[X:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[X_NEXT:%.*]], [[LOOP_LATCH:%.*]] ] +; CHECK-NEXT: [[C_1:%.*]] = icmp ugt i32 [[X]], 10 +; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_LATCH]], label [[EXIT]] +; CHECK: loop.latch: +; CHECK-NEXT: [[T_1:%.*]] = icmp ule i32 [[X]], 10 +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: [[F_1:%.*]] = icmp ugt i32 [[X]], 10 +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: [[C_2:%.*]] = icmp ule i32 [[X]], 9 +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: [[C_3:%.*]] = icmp ugt i32 [[X]], 9 +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: [[X_NEXT]] = add i32 [[X]], 1 +; CHECK-NEXT: br label [[LOOP_HEADER]] +; CHECK: exit: +; CHECK-NEXT: [[C_4:%.*]] = icmp ugt i32 [[Y:%.*]], 10 +; CHECK-NEXT: call void @use(i1 [[C_4]]) +; CHECK-NEXT: ret void +; +entry: + br i1 %c, label %loop.header, label %exit + +loop.header: + %x = phi i32 [ 0, %entry ], [ %x.next, %loop.latch ] + %c.1 = icmp ugt i32 %x, 10 + br i1 %c.1, label %loop.latch, label %exit + +loop.latch: + %t.1 = icmp ule i32 %x, 10 + call void @use(i1 %t.1) + %f.1 = icmp ugt i32 %x, 10 + call void @use(i1 %f.1) + + %c.2 = icmp ule i32 %x, 9 + call void @use(i1 %c.2) + %c.3 = icmp ugt i32 %x, 9 + call void @use(i1 %c.3) + + %x.next = add i32 %x, 1 + br label %loop.header + +exit: + %c.4 = icmp ugt i32 %y, 10 + call void @use(i1 %c.4) + ret void +} + + +define void @loop_iv_cond_variable_bound(i32 %n) { +; CHECK-LABEL: @loop_iv_cond_variable_bound( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP_HEADER:%.*]] +; CHECK: loop.header: +; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ] +; CHECK-NEXT: [[T_1:%.*]] = icmp ule i32 [[IV]], [[N:%.*]] +; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: [[T_2:%.*]] = icmp sge i32 [[IV]], 0 +; CHECK-NEXT: call void @use(i1 [[T_2]]) +; CHECK-NEXT: [[T_3:%.*]] = icmp sge i32 [[IV]], -1 +; CHECK-NEXT: call void @use(i1 [[T_3]]) +; CHECK-NEXT: [[C_1:%.*]] = icmp ult i32 [[IV]], [[N]] +; CHECK-NEXT: call void @use(i1 [[C_1]]) +; CHECK-NEXT: [[C_2:%.*]] = icmp ugt i32 [[IV]], 1 +; CHECK-NEXT: call void @use(i1 [[C_2]]) +; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[IV]], [[N]] +; CHECK-NEXT: br i1 [[CMP]], label [[LOOP_LATCH]], label [[EXIT:%.*]] +; CHECK: loop.latch: +; CHECK-NEXT: [[T_4:%.*]] = icmp ule i32 [[IV]], [[N]] +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: [[C_3:%.*]] = icmp ult i32 [[IV]], 2 +; CHECK-NEXT: call void @use(i1 [[C_3]]) +; CHECK-NEXT: [[C_4:%.*]] = icmp ugt i32 [[IV]], 1 +; CHECK-NEXT: call void @use(i1 [[C_4]]) +; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 +; CHECK-NEXT: br label [[LOOP_HEADER]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop.header + +loop.header: + %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] + %t.1 = icmp ule i32 %iv, %n + call void @use(i1 %t.1) + %t.2 = icmp sge i32 %iv, 0 + call void @use(i1 %t.2) + %t.3 = icmp sge i32 %iv, -1 + call void @use(i1 %t.3) + + %c.1 = icmp ult i32 %iv, %n + call void @use(i1 %c.1) + %c.2 = icmp ugt i32 %iv, 1 + call void @use(i1 %c.2) + + %cmp = icmp ult i32 %iv, %n + br i1 %cmp, label %loop.latch, label %exit + +loop.latch: + %t.4 = icmp ule i32 %iv, %n + call void @use(i1 %t.4) + + %c.3 = icmp ult i32 %iv, 2 + call void @use(i1 %c.3) + %c.4 = icmp ugt i32 %iv, 1 + call void @use(i1 %c.4) + + %iv.next = add nuw nsw i32 %iv, 1 + br label %loop.header + +exit: + ret void +} + +define void @loop_iv_cond_constant_bound() { +; CHECK-LABEL: @loop_iv_cond_constant_bound( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP_HEADER:%.*]] +; CHECK: loop.header: +; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ] +; CHECK-NEXT: [[T_1:%.*]] = icmp ule i32 [[IV]], 2 +; CHECK-NEXT: call void @use(i1 [[T_1]]) +; CHECK-NEXT: [[T_2:%.*]] = icmp sge i32 [[IV]], 0 +; CHECK-NEXT: call void @use(i1 [[T_2]]) +; CHECK-NEXT: [[T_3:%.*]] = icmp sge i32 [[IV]], -1 +; CHECK-NEXT: call void @use(i1 [[T_3]]) +; CHECK-NEXT: [[C_1:%.*]] = icmp ult i32 [[IV]], 2 +; CHECK-NEXT: call void @use(i1 [[C_1]]) +; CHECK-NEXT: [[C_2:%.*]] = icmp ugt i32 [[IV]], 1 +; CHECK-NEXT: call void @use(i1 [[C_2]]) +; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[IV]], 2 +; CHECK-NEXT: br i1 [[CMP]], label [[LOOP_LATCH]], label [[EXIT:%.*]] +; CHECK: loop.latch: +; CHECK-NEXT: [[T_4:%.*]] = icmp ule i32 [[IV]], 2 +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: [[C_3:%.*]] = icmp ult i32 [[IV]], 2 +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: [[C_4:%.*]] = icmp ugt i32 [[IV]], 1 +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1 +; CHECK-NEXT: br label [[LOOP_HEADER]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop.header + +loop.header: + %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop.latch ] + %t.1 = icmp ule i32 %iv, 2 + call void @use(i1 %t.1) + %t.2 = icmp sge i32 %iv, 0 + call void @use(i1 %t.2) + %t.3 = icmp sge i32 %iv, -1 + call void @use(i1 %t.3) + + %c.1 = icmp ult i32 %iv, 2 + call void @use(i1 %c.1) + %c.2 = icmp ugt i32 %iv, 1 + call void @use(i1 %c.2) + + %cmp = icmp ult i32 %iv, 2 + br i1 %cmp, label %loop.latch, label %exit + +loop.latch: + %t.4 = icmp ule i32 %iv, 2 + call void @use(i1 %t.4) + + %c.3 = icmp ult i32 %iv, 2 + call void @use(i1 %c.3) + %c.4 = icmp ugt i32 %iv, 1 + call void @use(i1 %c.4) + + %iv.next = add nuw nsw i32 %iv, 1 + br label %loop.header + +exit: + ret void +} diff --git a/llvm/test/Transforms/ConstraintElimination/loops-header-tested-pointer-cmps.ll b/llvm/test/Transforms/ConstraintElimination/loops-header-tested-pointer-cmps.ll new file mode 100644 index 0000000..23d70e3 --- /dev/null +++ b/llvm/test/Transforms/ConstraintElimination/loops-header-tested-pointer-cmps.ll @@ -0,0 +1,764 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -constraint-elimination -S %s | FileCheck %s + +declare void @use(i1) + +define void @test1(i8* %src, i8* noundef %lower, i8* noundef %upper, i8 %N) { +; CHECK-LABEL: @test1( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SRC_END:%.*]] = getelementptr inbounds i8, i8* [[SRC:%.*]], i8 [[N:%.*]] +; CHECK-NEXT: [[CMP_SRC_START:%.*]] = icmp ult i8* [[SRC]], [[LOWER:%.*]] +; CHECK-NEXT: [[CMP_SRC_END:%.*]] = icmp uge i8* [[SRC_END]], [[UPPER:%.*]] +; CHECK-NEXT: [[OR_0:%.*]] = or i1 [[CMP_SRC_START]], [[CMP_SRC_END]] +; CHECK-NEXT: br i1 [[OR_0]], label [[TRAP_BB:%.*]], label [[LOOP_HEADER:%.*]] +; CHECK: trap.bb: +; CHECK-NEXT: ret void +; CHECK: loop.header: +; CHECK-NEXT: [[IV:%.*]] = phi i8 [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ], [ 0, [[ENTRY:%.*]] ] +; CHECK-NEXT: [[EC:%.*]] = icmp uge i8 [[IV]], [[N]] +; CHECK-NEXT: br i1 [[EC]], label [[EXIT:%.*]], label [[LOOP_BODY:%.*]] +; CHECK: loop.body: +; CHECK-NEXT: [[SRC_IV:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i8 [[IV]] +; CHECK-NEXT: [[CMP_IV_START:%.*]] = icmp ult i8* [[SRC_IV]], [[LOWER]] +; CHECK-NEXT: [[CMP_IV_END:%.*]] = icmp uge i8* [[SRC_IV]], [[UPPER]] +; CHECK-NEXT: [[OR_1:%.*]] = or i1 [[CMP_IV_START]], false +; CHECK-NEXT: br i1 [[OR_1]], label [[TRAP_BB]], label [[LOOP_BODY_1:%.*]] +; CHECK: loop.body.1: +; CHECK-NEXT: [[PTR_SRC_IV:%.*]] = bitcast i8* [[SRC_IV]] to i32* +; CHECK-NEXT: store i32 0, i32* [[PTR_SRC_IV]], align 4 +; CHECK-NEXT: [[ADD_1:%.*]] = add nuw nsw i8 [[IV]], 1 +; CHECK-NEXT: [[SRC_IV_1:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i8 [[ADD_1]] +; CHECK-NEXT: [[CMP_IV_1_START:%.*]] = icmp ult i8* [[SRC_IV_1]], [[LOWER]] +; CHECK-NEXT: [[CMP_IV_1_END:%.*]] = icmp uge i8* [[SRC_IV_1]], [[UPPER]] +; CHECK-NEXT: [[OR_2:%.*]] = or i1 [[CMP_IV_1_START]], [[CMP_IV_1_END]] +; CHECK-NEXT: br i1 [[OR_2]], label [[TRAP_BB]], label [[LOOP_BODY_2:%.*]] +; CHECK: loop.body.2: +; CHECK-NEXT: [[PTR_SRC_IV_1:%.*]] = bitcast i8* [[SRC_IV_1]] to i32* +; CHECK-NEXT: store i32 0, i32* [[PTR_SRC_IV_1]], align 4 +; CHECK-NEXT: [[ADD_2:%.*]] = add nuw nsw i8 [[IV]], 2 +; CHECK-NEXT: [[SRC_IV_2:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i8 [[ADD_2]] +; CHECK-NEXT: [[CMP_IV_2_START:%.*]] = icmp ult i8* [[SRC_IV_2]], [[LOWER]] +; CHECK-NEXT: [[CMP_IV_2_END:%.*]] = icmp uge i8* [[SRC_IV_2]], [[UPPER]] +; CHECK-NEXT: [[OR_3:%.*]] = or i1 [[CMP_IV_2_START]], [[CMP_IV_2_END]] +; CHECK-NEXT: br i1 [[OR_3]], label [[TRAP_BB]], label [[LOOP_LATCH]] +; CHECK: loop.latch: +; CHECK-NEXT: [[PTR_SRC_IV_2:%.*]] = bitcast i8* [[SRC_IV_2]] to i32* +; CHECK-NEXT: store i32 0, i32* [[PTR_SRC_IV_2]], align 4 +; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i8 [[IV]], 1 +; CHECK-NEXT: br label [[LOOP_HEADER]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + %src.end = getelementptr inbounds i8, i8* %src, i8 %N + %cmp.src.start = icmp ult i8* %src, %lower + %cmp.src.end = icmp uge i8* %src.end, %upper + %or.0 = or i1 %cmp.src.start, %cmp.src.end + br i1 %or.0, label %trap.bb, label %loop.header + +trap.bb: + ret void + +loop.header: + %iv = phi i8 [ %iv.next, %loop.latch ], [ 0, %entry ] + %ec = icmp uge i8 %iv, %N + br i1 %ec, label %exit, label %loop.body + +loop.body: + %src.iv = getelementptr inbounds i8, i8* %src, i8 %iv + %cmp.iv.start = icmp ult i8* %src.iv, %lower + %cmp.iv.end = icmp uge i8* %src.iv, %upper + %or.1 = or i1 %cmp.iv.start, %cmp.iv.end + br i1 %or.1, label %trap.bb, label %loop.body.1 + +loop.body.1: + %ptr.src.iv = bitcast i8* %src.iv to i32* + store i32 0, i32* %ptr.src.iv, align 4 + %add.1 = add nuw nsw i8 %iv, 1 + %src.iv.1 = getelementptr inbounds i8, i8* %src, i8 %add.1 + %cmp.iv.1.start = icmp ult i8* %src.iv.1, %lower + %cmp.iv.1.end = icmp uge i8* %src.iv.1, %upper + %or.2 = or i1 %cmp.iv.1.start, %cmp.iv.1.end + br i1 %or.2, label %trap.bb, label %loop.body.2 + +loop.body.2: + %ptr.src.iv.1 = bitcast i8* %src.iv.1 to i32* + store i32 0, i32* %ptr.src.iv.1, align 4 + %add.2 = add nuw nsw i8 %iv, 2 + %src.iv.2 = getelementptr inbounds i8, i8* %src, i8 %add.2 + %cmp.iv.2.start = icmp ult i8* %src.iv.2, %lower + %cmp.iv.2.end = icmp uge i8* %src.iv.2, %upper + %or.3 = or i1 %cmp.iv.2.start, %cmp.iv.2.end + br i1 %or.3, label %trap.bb, label %loop.latch + + +loop.latch: + %ptr.src.iv.2 = bitcast i8* %src.iv.2 to i32* + store i32 0, i32* %ptr.src.iv.2, align 4 + %iv.next = add nuw nsw i8 %iv, 1 + br label %loop.header + +exit: + ret void +} + +define void @test2(i8* %src, i8* %lower, i8* %upper, i8 %N) { +; CHECK-LABEL: @test2( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SRC_END:%.*]] = getelementptr inbounds i8, i8* [[SRC:%.*]], i8 [[N:%.*]] +; CHECK-NEXT: [[CMP_SRC_START:%.*]] = icmp ult i8* [[SRC]], [[LOWER:%.*]] +; CHECK-NEXT: [[CMP_SRC_END:%.*]] = icmp uge i8* [[SRC_END]], [[UPPER:%.*]] +; CHECK-NEXT: [[CMP_OVERFLOW:%.*]] = icmp ugt i8* [[SRC]], [[SRC_END]] +; CHECK-NEXT: [[OR_0:%.*]] = or i1 [[CMP_SRC_START]], [[CMP_SRC_END]] +; CHECK-NEXT: [[OR_11:%.*]] = or i1 [[OR_0]], [[CMP_OVERFLOW]] +; CHECK-NEXT: br i1 [[OR_11]], label [[TRAP_BB:%.*]], label [[LOOP_HEADER:%.*]] +; CHECK: trap.bb: +; CHECK-NEXT: ret void +; CHECK: loop.header: +; CHECK-NEXT: [[IV:%.*]] = phi i8 [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ], [ 1, [[ENTRY:%.*]] ] +; CHECK-NEXT: [[NEXT:%.*]] = add nuw nsw i8 [[IV]], 2 +; CHECK-NEXT: [[EC:%.*]] = icmp uge i8 [[NEXT]], [[N]] +; CHECK-NEXT: br i1 [[EC]], label [[EXIT:%.*]], label [[LOOP_BODY:%.*]] +; CHECK: loop.body: +; CHECK-NEXT: [[SRC_IV:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i8 [[IV]] +; CHECK-NEXT: [[CMP_IV_START:%.*]] = icmp ult i8* [[SRC_IV]], [[LOWER]] +; CHECK-NEXT: [[CMP_IV_END:%.*]] = icmp uge i8* [[SRC_IV]], [[UPPER]] +; CHECK-NEXT: [[OR_1:%.*]] = or i1 [[CMP_IV_START]], [[CMP_IV_END]] +; CHECK-NEXT: br i1 [[OR_1]], label [[TRAP_BB]], label [[LOOP_BODY_1:%.*]] +; CHECK: loop.body.1: +; CHECK-NEXT: [[ADD_1:%.*]] = add nuw nsw i8 [[IV]], 1 +; CHECK-NEXT: [[SRC_IV_1:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i8 [[ADD_1]] +; CHECK-NEXT: [[CMP_IV_1_START:%.*]] = icmp ult i8* [[SRC_IV_1]], [[LOWER]] +; CHECK-NEXT: [[CMP_IV_1_END:%.*]] = icmp uge i8* [[SRC_IV_1]], [[UPPER]] +; CHECK-NEXT: [[OR_2:%.*]] = or i1 [[CMP_IV_1_START]], [[CMP_IV_1_END]] +; CHECK-NEXT: br i1 [[OR_2]], label [[TRAP_BB]], label [[LOOP_BODY_2:%.*]] +; CHECK: loop.body.2: +; CHECK-NEXT: [[ADD_2:%.*]] = add nuw nsw i8 [[IV]], 2 +; CHECK-NEXT: [[SRC_IV_2:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i8 [[ADD_2]] +; CHECK-NEXT: [[CMP_IV_2_START:%.*]] = icmp ult i8* [[SRC_IV_2]], [[LOWER]] +; CHECK-NEXT: [[CMP_IV_2_END:%.*]] = icmp uge i8* [[SRC_IV_2]], [[UPPER]] +; CHECK-NEXT: [[OR_3:%.*]] = or i1 [[CMP_IV_2_START]], [[CMP_IV_2_END]] +; CHECK-NEXT: br i1 [[OR_3]], label [[TRAP_BB]], label [[LOOP_LATCH]] +; CHECK: loop.latch: +; CHECK-NEXT: [[PTR:%.*]] = bitcast i8* [[SRC_IV]] to i32* +; CHECK-NEXT: store i32 0, i32* [[PTR]], align 4 +; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i8 [[IV]], 1 +; CHECK-NEXT: br label [[LOOP_HEADER]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + %src.end = getelementptr inbounds i8, i8* %src, i8 %N + %cmp.src.start = icmp ult i8* %src, %lower + %cmp.src.end = icmp uge i8* %src.end, %upper + %cmp.overflow = icmp ugt i8* %src, %src.end + %or.0 = or i1 %cmp.src.start, %cmp.src.end + %or.11 = or i1 %or.0, %cmp.overflow + br i1 %or.11, label %trap.bb, label %loop.header + +trap.bb: + ret void + +loop.header: + %iv = phi i8 [ %iv.next, %loop.latch ], [ 1, %entry ] + %next = add nsw nuw i8 %iv, 2 + %ec = icmp uge i8 %next, %N + br i1 %ec, label %exit, label %loop.body + +loop.body: + %src.iv = getelementptr inbounds i8, i8* %src, i8 %iv + %cmp.iv.start = icmp ult i8* %src.iv, %lower + %cmp.iv.end = icmp uge i8* %src.iv, %upper + %or.1 = or i1 %cmp.iv.start, %cmp.iv.end + br i1 %or.1, label %trap.bb, label %loop.body.1 + +loop.body.1: + %add.1 = add nsw nuw i8 %iv, 1 + %src.iv.1 = getelementptr inbounds i8, i8* %src, i8 %add.1 + %cmp.iv.1.start = icmp ult i8* %src.iv.1, %lower + %cmp.iv.1.end = icmp uge i8* %src.iv.1, %upper + %or.2 = or i1 %cmp.iv.1.start, %cmp.iv.1.end + br i1 %or.2, label %trap.bb, label %loop.body.2 + +loop.body.2: + %add.2 = add nsw nuw i8 %iv, 2 + %src.iv.2 = getelementptr inbounds i8, i8* %src, i8 %add.2 + %cmp.iv.2.start = icmp ult i8* %src.iv.2, %lower + %cmp.iv.2.end = icmp uge i8* %src.iv.2, %upper + %or.3 = or i1 %cmp.iv.2.start, %cmp.iv.2.end + br i1 %or.3, label %trap.bb, label %loop.latch + +loop.latch: + %ptr = bitcast i8* %src.iv to i32* + store i32 0, i32* %ptr, align 4 + %iv.next = add nuw nsw i8 %iv, 1 + br label %loop.header + +exit: + ret void +} + +define void @test2_with_ne(i8* %src, i8* %lower, i8* %upper, i8 %N) { +; CHECK-LABEL: @test2_with_ne( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SRC_END:%.*]] = getelementptr inbounds i8, i8* [[SRC:%.*]], i8 [[N:%.*]] +; CHECK-NEXT: [[CMP_SRC_START:%.*]] = icmp ult i8* [[SRC]], [[LOWER:%.*]] +; CHECK-NEXT: [[CMP_SRC_END:%.*]] = icmp uge i8* [[SRC_END]], [[UPPER:%.*]] +; CHECK-NEXT: [[CMP_OVERFLOW:%.*]] = icmp ugt i8* [[SRC]], [[SRC_END]] +; CHECK-NEXT: [[OR_0:%.*]] = or i1 [[CMP_SRC_START]], [[CMP_SRC_END]] +; CHECK-NEXT: [[OR_11:%.*]] = or i1 [[OR_0]], [[CMP_OVERFLOW]] +; CHECK-NEXT: br i1 [[OR_11]], label [[TRAP_BB:%.*]], label [[LOOP_HEADER:%.*]] +; CHECK: trap.bb: +; CHECK-NEXT: ret void +; CHECK: loop.header: +; CHECK-NEXT: [[IV:%.*]] = phi i8 [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ], [ 1, [[ENTRY:%.*]] ] +; CHECK-NEXT: [[NEXT:%.*]] = add nuw nsw i8 [[IV]], 1 +; CHECK-NEXT: [[EC:%.*]] = icmp eq i8 [[NEXT]], [[N]] +; CHECK-NEXT: br i1 [[EC]], label [[EXIT:%.*]], label [[LOOP_BODY:%.*]] +; CHECK: loop.body: +; CHECK-NEXT: [[SRC_IV:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i8 [[IV]] +; CHECK-NEXT: [[CMP_IV_START:%.*]] = icmp ult i8* [[SRC_IV]], [[LOWER]] +; CHECK-NEXT: [[CMP_IV_END:%.*]] = icmp uge i8* [[SRC_IV]], [[UPPER]] +; CHECK-NEXT: [[OR_1:%.*]] = or i1 [[CMP_IV_START]], [[CMP_IV_END]] +; CHECK-NEXT: br i1 [[OR_1]], label [[TRAP_BB]], label [[LOOP_BODY_1:%.*]] +; CHECK: loop.body.1: +; CHECK-NEXT: [[ADD_1:%.*]] = add nuw nsw i8 [[IV]], 1 +; CHECK-NEXT: [[SRC_IV_1:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i8 [[ADD_1]] +; CHECK-NEXT: [[CMP_IV_1_START:%.*]] = icmp ult i8* [[SRC_IV_1]], [[LOWER]] +; CHECK-NEXT: [[CMP_IV_1_END:%.*]] = icmp uge i8* [[SRC_IV_1]], [[UPPER]] +; CHECK-NEXT: [[OR_2:%.*]] = or i1 [[CMP_IV_1_START]], [[CMP_IV_1_END]] +; CHECK-NEXT: br i1 [[OR_2]], label [[TRAP_BB]], label [[LOOP_BODY_2:%.*]] +; CHECK: loop.body.2: +; CHECK-NEXT: [[ADD_2:%.*]] = add nuw nsw i8 [[IV]], 2 +; CHECK-NEXT: [[SRC_IV_2:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i8 [[ADD_2]] +; CHECK-NEXT: [[CMP_IV_2_START:%.*]] = icmp ult i8* [[SRC_IV_2]], [[LOWER]] +; CHECK-NEXT: [[CMP_IV_2_END:%.*]] = icmp uge i8* [[SRC_IV_2]], [[UPPER]] +; CHECK-NEXT: [[OR_3:%.*]] = or i1 [[CMP_IV_2_START]], [[CMP_IV_2_END]] +; CHECK-NEXT: br i1 [[OR_3]], label [[TRAP_BB]], label [[LOOP_LATCH]] +; CHECK: loop.latch: +; CHECK-NEXT: [[PTR:%.*]] = bitcast i8* [[SRC_IV]] to i32* +; CHECK-NEXT: store i32 0, i32* [[PTR]], align 4 +; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i8 [[IV]], 1 +; CHECK-NEXT: br label [[LOOP_HEADER]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + %src.end = getelementptr inbounds i8, i8* %src, i8 %N + %cmp.src.start = icmp ult i8* %src, %lower + %cmp.src.end = icmp uge i8* %src.end, %upper + %cmp.overflow = icmp ugt i8* %src, %src.end + %or.0 = or i1 %cmp.src.start, %cmp.src.end + %or.11 = or i1 %or.0, %cmp.overflow + br i1 %or.11, label %trap.bb, label %loop.header + +trap.bb: + ret void + +loop.header: + %iv = phi i8 [ %iv.next, %loop.latch ], [ 1, %entry ] + %next = add nsw nuw i8 %iv, 1 + %ec = icmp eq i8 %next, %N + br i1 %ec, label %exit, label %loop.body + +loop.body: + %src.iv = getelementptr inbounds i8, i8* %src, i8 %iv + %cmp.iv.start = icmp ult i8* %src.iv, %lower + %cmp.iv.end = icmp uge i8* %src.iv, %upper + %or.1 = or i1 %cmp.iv.start, %cmp.iv.end + br i1 %or.1, label %trap.bb, label %loop.body.1 + +loop.body.1: + %add.1 = add nsw nuw i8 %iv, 1 + %src.iv.1 = getelementptr inbounds i8, i8* %src, i8 %add.1 + %cmp.iv.1.start = icmp ult i8* %src.iv.1, %lower + %cmp.iv.1.end = icmp uge i8* %src.iv.1, %upper + %or.2 = or i1 %cmp.iv.1.start, %cmp.iv.1.end + br i1 %or.2, label %trap.bb, label %loop.body.2 + +loop.body.2: + %add.2 = add nsw nuw i8 %iv, 2 + %src.iv.2 = getelementptr inbounds i8, i8* %src, i8 %add.2 + %cmp.iv.2.start = icmp ult i8* %src.iv.2, %lower + %cmp.iv.2.end = icmp uge i8* %src.iv.2, %upper + %or.3 = or i1 %cmp.iv.2.start, %cmp.iv.2.end + br i1 %or.3, label %trap.bb, label %loop.latch + +loop.latch: + %ptr = bitcast i8* %src.iv to i32* + store i32 0, i32* %ptr, align 4 + %iv.next = add nuw nsw i8 %iv, 1 + br label %loop.header + +exit: + ret void +} + + +define void @test3(i8* %src, i8* %lower, i8* %upper, i8 %N) { +; CHECK-LABEL: @test3( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SRC_END:%.*]] = getelementptr inbounds i8, i8* [[SRC:%.*]], i8 [[N:%.*]] +; CHECK-NEXT: [[CMP_SRC_START:%.*]] = icmp ult i8* [[SRC]], [[LOWER:%.*]] +; CHECK-NEXT: [[CMP_SRC_END:%.*]] = icmp uge i8* [[SRC_END]], [[UPPER:%.*]] +; CHECK-NEXT: [[CMP_OVERFLOW:%.*]] = icmp ugt i8* [[SRC]], [[SRC_END]] +; CHECK-NEXT: [[OR_0:%.*]] = or i1 [[CMP_SRC_START]], [[CMP_SRC_END]] +; CHECK-NEXT: [[OR_11:%.*]] = or i1 [[OR_0]], [[CMP_OVERFLOW]] +; CHECK-NEXT: br i1 [[OR_11]], label [[TRAP_BB:%.*]], label [[LOOP_HEADER:%.*]] +; CHECK: trap.bb: +; CHECK-NEXT: ret void +; CHECK: loop.header: +; CHECK-NEXT: [[IV:%.*]] = phi i8 [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ], [ 1, [[ENTRY:%.*]] ] +; CHECK-NEXT: [[NEXT:%.*]] = or i8 [[IV]], 1 +; CHECK-NEXT: [[EC:%.*]] = icmp ult i8 [[NEXT]], [[N]] +; CHECK-NEXT: br i1 [[EC]], label [[LOOP_BODY:%.*]], label [[EXIT:%.*]] +; CHECK: loop.body: +; CHECK-NEXT: [[SRC_IV:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i8 [[IV]] +; CHECK-NEXT: [[CMP_IV_START:%.*]] = icmp ult i8* [[SRC_IV]], [[LOWER]] +; CHECK-NEXT: [[CMP_IV_END:%.*]] = icmp uge i8* [[SRC_IV]], [[UPPER]] +; CHECK-NEXT: [[OR_1:%.*]] = or i1 [[CMP_IV_START]], [[CMP_IV_END]] +; CHECK-NEXT: br i1 [[OR_1]], label [[TRAP_BB]], label [[LOOP_BODY_1:%.*]] +; CHECK: loop.body.1: +; CHECK-NEXT: [[SRC_IV_1:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i8 [[NEXT]] +; CHECK-NEXT: [[CMP_IV_1_START:%.*]] = icmp ult i8* [[SRC_IV_1]], [[LOWER]] +; CHECK-NEXT: [[CMP_IV_1_END:%.*]] = icmp uge i8* [[SRC_IV_1]], [[UPPER]] +; CHECK-NEXT: [[OR_2:%.*]] = or i1 [[CMP_IV_1_START]], [[CMP_IV_1_END]] +; CHECK-NEXT: br i1 [[OR_2]], label [[TRAP_BB]], label [[LOOP_BODY_2:%.*]] +; CHECK: loop.body.2: +; CHECK-NEXT: [[ADD_2:%.*]] = add nuw nsw i8 [[IV]], 2 +; CHECK-NEXT: [[SRC_IV_2:%.*]] = getelementptr inbounds i8, i8* [[SRC]], i8 [[ADD_2]] +; CHECK-NEXT: [[CMP_IV_2_START:%.*]] = icmp ult i8* [[SRC_IV_2]], [[LOWER]] +; CHECK-NEXT: [[CMP_IV_2_END:%.*]] = icmp uge i8* [[SRC_IV_2]], [[UPPER]] +; CHECK-NEXT: [[OR_3:%.*]] = or i1 [[CMP_IV_2_START]], [[CMP_IV_2_END]] +; CHECK-NEXT: br i1 [[OR_3]], label [[TRAP_BB]], label [[LOOP_LATCH]] +; CHECK: loop.latch: +; CHECK-NEXT: [[PTR:%.*]] = bitcast i8* [[SRC_IV]] to i32* +; CHECK-NEXT: store i32 0, i32* [[PTR]], align 4 +; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i8 [[IV]], 1 +; CHECK-NEXT: br label [[LOOP_HEADER]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + %src.end = getelementptr inbounds i8, i8* %src, i8 %N + %cmp.src.start = icmp ult i8* %src, %lower + %cmp.src.end = icmp uge i8* %src.end, %upper + %cmp.overflow = icmp ugt i8* %src, %src.end + %or.0 = or i1 %cmp.src.start, %cmp.src.end + %or.11 = or i1 %or.0, %cmp.overflow + br i1 %or.11, label %trap.bb, label %loop.header + +trap.bb: + ret void + +loop.header: + %iv = phi i8 [ %iv.next, %loop.latch ], [ 1, %entry ] + %next = or i8 %iv, 1 + %ec = icmp ult i8 %next, %N + br i1 %ec, label %loop.body, label %exit + +loop.body: + %src.iv = getelementptr inbounds i8, i8* %src, i8 %iv + %cmp.iv.start = icmp ult i8* %src.iv, %lower + %cmp.iv.end = icmp uge i8* %src.iv, %upper + %or.1 = or i1 %cmp.iv.start, %cmp.iv.end + br i1 %or.1, label %trap.bb, label %loop.body.1 + +loop.body.1: + %src.iv.1 = getelementptr inbounds i8, i8* %src, i8 %next + %cmp.iv.1.start = icmp ult i8* %src.iv.1, %lower + %cmp.iv.1.end = icmp uge i8* %src.iv.1, %upper + %or.2 = or i1 %cmp.iv.1.start, %cmp.iv.1.end + br i1 %or.2, label %trap.bb, label %loop.body.2 + +loop.body.2: + %add.2 = add nsw nuw i8 %iv, 2 + %src.iv.2 = getelementptr inbounds i8, i8* %src, i8 %add.2 + %cmp.iv.2.start = icmp ult i8* %src.iv.2, %lower + %cmp.iv.2.end = icmp uge i8* %src.iv.2, %upper + %or.3 = or i1 %cmp.iv.2.start, %cmp.iv.2.end + br i1 %or.3, label %trap.bb, label %loop.latch + +loop.latch: + %ptr = bitcast i8* %src.iv to i32* + store i32 0, i32* %ptr, align 4 + %iv.next = add nuw nsw i8 %iv, 1 + br label %loop.header + +exit: + ret void +} + +; Cannot remove checks, because %n may be negative. +define void @ne_check_in_loop_no_zext_n_may_be_negative(i8* %ptr, i8* %lower, i8* %upper, i16 %n) { +; CHECK-LABEL: @ne_check_in_loop_no_zext_n_may_be_negative( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CMP_PTR_LOWER:%.*]] = icmp ult i8* [[PTR:%.*]], [[LOWER:%.*]] +; CHECK-NEXT: br i1 [[CMP_PTR_LOWER]], label [[TRAP:%.*]], label [[PRE:%.*]] +; CHECK: pre: +; CHECK-NEXT: [[ADD_PTR:%.*]] = getelementptr inbounds i8, i8* [[PTR]], i16 [[N:%.*]] +; CHECK-NEXT: [[CMP_PTR_N_UPPER:%.*]] = icmp ult i8* [[ADD_PTR]], [[UPPER:%.*]] +; CHECK-NEXT: br i1 [[CMP_PTR_N_UPPER]], label [[FOR_COND_PREHEADER:%.*]], label [[TRAP]] +; CHECK: for.cond.preheader: +; CHECK-NEXT: br label [[FOR_HEADER:%.*]] +; CHECK: trap: +; CHECK-NEXT: ret void +; CHECK: for.header: +; CHECK-NEXT: [[IV:%.*]] = phi i16 [ 0, [[FOR_COND_PREHEADER]] ], [ [[IV_NEXT:%.*]], [[FOR_LATCH:%.*]] ] +; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i16 [[IV]], [[N]] +; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]] +; CHECK: for.body: +; CHECK-NEXT: [[GEP_IV:%.*]] = getelementptr inbounds i8, i8* [[PTR]], i16 [[IV]] +; CHECK-NEXT: [[CMP_IV_LOWER:%.*]] = icmp ugt i8* [[LOWER]], [[GEP_IV]] +; CHECK-NEXT: [[CMP_IV_UPPER:%.*]] = icmp ule i8* [[UPPER]], [[GEP_IV]] +; CHECK-NEXT: [[OR:%.*]] = or i1 [[CMP_IV_LOWER]], [[CMP_IV_UPPER]] +; CHECK-NEXT: br i1 [[OR]], label [[TRAP]], label [[FOR_BODY_1:%.*]] +; CHECK: for.body.1: +; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i16 [[IV]], 1 +; CHECK-NEXT: [[GEP_IV_1:%.*]] = getelementptr inbounds i8, i8* [[PTR]], i16 [[ADD]] +; CHECK-NEXT: [[CMP_IV_1_LOWER:%.*]] = icmp ugt i8* [[LOWER]], [[GEP_IV_1]] +; CHECK-NEXT: [[CMP_IV_1_UPPER:%.*]] = icmp ule i8* [[UPPER]], [[GEP_IV_1]] +; CHECK-NEXT: [[OR_1:%.*]] = or i1 [[CMP_IV_1_LOWER]], [[CMP_IV_1_UPPER]] +; CHECK-NEXT: br i1 [[OR_1]], label [[TRAP]], label [[FOR_LATCH]] +; CHECK: for.latch: +; CHECK-NEXT: store i8 0, i8* [[GEP_IV]], align 4 +; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i16 [[IV]], 1 +; CHECK-NEXT: br label [[FOR_HEADER]] +; CHECK: for.end: +; CHECK-NEXT: ret void +; +entry: + %cmp.ptr.lower = icmp ult i8* %ptr, %lower + br i1 %cmp.ptr.lower, label %trap, label %pre + +pre: + %add.ptr = getelementptr inbounds i8, i8* %ptr, i16 %n + %cmp.ptr.n.upper = icmp ult i8* %add.ptr, %upper + br i1 %cmp.ptr.n.upper, label %for.cond.preheader, label %trap + +for.cond.preheader: + br label %for.header + +trap: + ret void + +for.header: + %iv = phi i16 [ 0, %for.cond.preheader ], [ %iv.next, %for.latch ] + %exitcond = icmp ne i16 %iv, %n + br i1 %exitcond, label %for.body, label %for.end + +for.body: + %gep.iv = getelementptr inbounds i8, i8* %ptr, i16 %iv + %cmp.iv.lower = icmp ugt i8* %lower, %gep.iv + %cmp.iv.upper = icmp ule i8* %upper, %gep.iv + %or = or i1 %cmp.iv.lower, %cmp.iv.upper + br i1 %or, label %trap, label %for.body.1 + +for.body.1: + %add = add nuw nsw i16 %iv, 1 + %gep.iv.1 = getelementptr inbounds i8, i8* %ptr, i16 %add + %cmp.iv.1.lower = icmp ugt i8* %lower, %gep.iv.1 + %cmp.iv.1.upper = icmp ule i8* %upper, %gep.iv.1 + %or.1 = or i1 %cmp.iv.1.lower, %cmp.iv.1.upper + br i1 %or.1, label %trap, label %for.latch + +for.latch: + store i8 0, i8* %gep.iv, align 4 + %iv.next = add nuw nsw i16 %iv, 1 + br label %for.header + +for.end: + ret void +} + +; Should be able to remove the checks in the loop, because %n is signed positive. +define void @ne_check_in_loop_no_zext_n_positive_check(i8* %ptr, i8* %lower, i8* %upper, i16 %n) { +; CHECK-LABEL: @ne_check_in_loop_no_zext_n_positive_check( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[N_SIGNED_POSITIVE:%.*]] = icmp slt i16 [[N:%.*]], 0 +; CHECK-NEXT: [[CMP_PTR_LOWER:%.*]] = icmp ult i8* [[PTR:%.*]], [[LOWER:%.*]] +; CHECK-NEXT: [[OR_T:%.*]] = or i1 [[N_SIGNED_POSITIVE]], [[CMP_PTR_LOWER]] +; CHECK-NEXT: br i1 [[OR_T]], label [[TRAP:%.*]], label [[PRE:%.*]] +; CHECK: pre: +; CHECK-NEXT: [[ADD_PTR:%.*]] = getelementptr inbounds i8, i8* [[PTR]], i16 [[N]] +; CHECK-NEXT: [[CMP_PTR_N_UPPER:%.*]] = icmp ult i8* [[ADD_PTR]], [[UPPER:%.*]] +; CHECK-NEXT: br i1 [[CMP_PTR_N_UPPER]], label [[FOR_COND_PREHEADER:%.*]], label [[TRAP]] +; CHECK: for.cond.preheader: +; CHECK-NEXT: br label [[FOR_HEADER:%.*]] +; CHECK: trap: +; CHECK-NEXT: ret void +; CHECK: for.header: +; CHECK-NEXT: [[IV:%.*]] = phi i16 [ 0, [[FOR_COND_PREHEADER]] ], [ [[IV_NEXT:%.*]], [[FOR_LATCH:%.*]] ] +; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i16 [[IV]], [[N]] +; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]] +; CHECK: for.body: +; CHECK-NEXT: [[GEP_IV:%.*]] = getelementptr inbounds i8, i8* [[PTR]], i16 [[IV]] +; CHECK-NEXT: [[CMP_IV_LOWER:%.*]] = icmp ugt i8* [[LOWER]], [[GEP_IV]] +; CHECK-NEXT: [[CMP_IV_UPPER:%.*]] = icmp ule i8* [[UPPER]], [[GEP_IV]] +; CHECK-NEXT: [[OR:%.*]] = or i1 [[CMP_IV_LOWER]], [[CMP_IV_UPPER]] +; CHECK-NEXT: br i1 [[OR]], label [[TRAP]], label [[FOR_BODY_1:%.*]] +; CHECK: for.body.1: +; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i16 [[IV]], 1 +; CHECK-NEXT: [[GEP_IV_1:%.*]] = getelementptr inbounds i8, i8* [[PTR]], i16 [[ADD]] +; CHECK-NEXT: [[CMP_IV_1_LOWER:%.*]] = icmp ugt i8* [[LOWER]], [[GEP_IV_1]] +; CHECK-NEXT: [[CMP_IV_1_UPPER:%.*]] = icmp ule i8* [[UPPER]], [[GEP_IV_1]] +; CHECK-NEXT: [[OR_1:%.*]] = or i1 [[CMP_IV_1_LOWER]], [[CMP_IV_1_UPPER]] +; CHECK-NEXT: br i1 [[OR_1]], label [[TRAP]], label [[FOR_LATCH]] +; CHECK: for.latch: +; CHECK-NEXT: store i8 0, i8* [[GEP_IV]], align 4 +; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i16 [[IV]], 1 +; CHECK-NEXT: br label [[FOR_HEADER]] +; CHECK: for.end: +; CHECK-NEXT: ret void +; +entry: + %n.signed.positive = icmp slt i16 %n, 0 + %cmp.ptr.lower = icmp ult i8* %ptr, %lower + %or.t = or i1 %n.signed.positive, %cmp.ptr.lower + br i1 %or.t, label %trap, label %pre + +pre: + %add.ptr = getelementptr inbounds i8, i8* %ptr, i16 %n + %cmp.ptr.n.upper = icmp ult i8* %add.ptr, %upper + br i1 %cmp.ptr.n.upper, label %for.cond.preheader, label %trap + +for.cond.preheader: + br label %for.header + +trap: + ret void + +for.header: + %iv = phi i16 [ 0, %for.cond.preheader ], [ %iv.next, %for.latch ] + %exitcond = icmp ne i16 %iv, %n + br i1 %exitcond, label %for.body, label %for.end + +for.body: + %gep.iv = getelementptr inbounds i8, i8* %ptr, i16 %iv + %cmp.iv.lower = icmp ugt i8* %lower, %gep.iv + %cmp.iv.upper = icmp ule i8* %upper, %gep.iv + %or = or i1 %cmp.iv.lower, %cmp.iv.upper + br i1 %or, label %trap, label %for.body.1 + +for.body.1: + %add = add nuw nsw i16 %iv, 1 + %gep.iv.1 = getelementptr inbounds i8, i8* %ptr, i16 %add + %cmp.iv.1.lower = icmp ugt i8* %lower, %gep.iv.1 + %cmp.iv.1.upper = icmp ule i8* %upper, %gep.iv.1 + %or.1 = or i1 %cmp.iv.1.lower, %cmp.iv.1.upper + br i1 %or.1, label %trap, label %for.latch + +for.latch: + store i8 0, i8* %gep.iv, align 4 + %iv.next = add nuw nsw i16 %iv, 1 + br label %for.header + +for.end: + ret void +} + +; Make sure icmp ne of the induction variable in the loop body can be handled +; and is treated as ule. +define void @ne_check_in_loop_with_zext(i8* %ptr, i8* %lower, i8* %upper, i8 %n) { +; CHECK-LABEL: @ne_check_in_loop_with_zext( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[CMP_PTR_LOWER:%.*]] = icmp ult i8* [[PTR:%.*]], [[LOWER:%.*]] +; CHECK-NEXT: br i1 [[CMP_PTR_LOWER]], label [[TRAP:%.*]], label [[PRE:%.*]] +; CHECK: pre: +; CHECK-NEXT: [[IDX_EXT:%.*]] = zext i8 [[N:%.*]] to i16 +; CHECK-NEXT: [[ADD_PTR:%.*]] = getelementptr inbounds i8, i8* [[PTR]], i16 [[IDX_EXT]] +; CHECK-NEXT: [[CMP_PTR_N_UPPER:%.*]] = icmp ult i8* [[ADD_PTR]], [[UPPER:%.*]] +; CHECK-NEXT: br i1 [[CMP_PTR_N_UPPER]], label [[FOR_COND_PREHEADER:%.*]], label [[TRAP]] +; CHECK: for.cond.preheader: +; CHECK-NEXT: br label [[FOR_HEADER:%.*]] +; CHECK: trap: +; CHECK-NEXT: ret void +; CHECK: for.header: +; CHECK-NEXT: [[IV:%.*]] = phi i16 [ 0, [[FOR_COND_PREHEADER]] ], [ [[IV_NEXT:%.*]], [[FOR_LATCH:%.*]] ] +; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i16 [[IV]], [[IDX_EXT]] +; CHECK-NEXT: br i1 [[EXITCOND]], label [[FOR_BODY:%.*]], label [[FOR_END:%.*]] +; CHECK: for.body: +; CHECK-NEXT: [[GEP_IV:%.*]] = getelementptr inbounds i8, i8* [[PTR]], i16 [[IV]] +; CHECK-NEXT: [[CMP_IV_LOWER:%.*]] = icmp ugt i8* [[LOWER]], [[GEP_IV]] +; CHECK-NEXT: [[CMP_IV_UPPER:%.*]] = icmp ule i8* [[UPPER]], [[GEP_IV]] +; CHECK-NEXT: [[OR:%.*]] = or i1 [[CMP_IV_LOWER]], [[CMP_IV_UPPER]] +; CHECK-NEXT: br i1 [[OR]], label [[TRAP]], label [[FOR_BODY_1:%.*]] +; CHECK: for.body.1: +; CHECK-NEXT: [[ADD:%.*]] = add nuw nsw i16 [[IV]], 1 +; CHECK-NEXT: [[GEP_IV_1:%.*]] = getelementptr inbounds i8, i8* [[PTR]], i16 [[ADD]] +; CHECK-NEXT: [[CMP_IV_1_LOWER:%.*]] = icmp ugt i8* [[LOWER]], [[GEP_IV_1]] +; CHECK-NEXT: [[CMP_IV_1_UPPER:%.*]] = icmp ule i8* [[UPPER]], [[GEP_IV_1]] +; CHECK-NEXT: [[OR_1:%.*]] = or i1 [[CMP_IV_1_LOWER]], [[CMP_IV_1_UPPER]] +; CHECK-NEXT: br i1 [[OR_1]], label [[TRAP]], label [[FOR_LATCH]] +; CHECK: for.latch: +; CHECK-NEXT: store i8 0, i8* [[GEP_IV]], align 4 +; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw i16 [[IV]], 1 +; CHECK-NEXT: br label [[FOR_HEADER]] +; CHECK: for.end: +; CHECK-NEXT: ret void +; +entry: + %cmp.ptr.lower = icmp ult i8* %ptr, %lower + br i1 %cmp.ptr.lower, label %trap, label %pre + +pre: + %idx.ext = zext i8 %n to i16 + %add.ptr = getelementptr inbounds i8, i8* %ptr, i16 %idx.ext + %cmp.ptr.n.upper = icmp ult i8* %add.ptr, %upper + br i1 %cmp.ptr.n.upper, label %for.cond.preheader, label %trap + +for.cond.preheader: + br label %for.header + +trap: + ret void + +for.header: + %iv = phi i16 [ 0, %for.cond.preheader ], [ %iv.next, %for.latch ] + %exitcond = icmp ne i16 %iv, %idx.ext + br i1 %exitcond, label %for.body, label %for.end + +for.body: + %gep.iv = getelementptr inbounds i8, i8* %ptr, i16 %iv + %cmp.iv.lower = icmp ugt i8* %lower, %gep.iv + %cmp.iv.upper = icmp ule i8* %upper, %gep.iv + %or = or i1 %cmp.iv.lower, %cmp.iv.upper + br i1 %or, label %trap, label %for.body.1 + +for.body.1: + %add = add nuw nsw i16 %iv, 1 + %gep.iv.1 = getelementptr inbounds i8, i8* %ptr, i16 %add + %cmp.iv.1.lower = icmp ugt i8* %lower, %gep.iv.1 + %cmp.iv.1.upper = icmp ule i8* %upper, %gep.iv.1 + %or.1 = or i1 %cmp.iv.1.lower, %cmp.iv.1.upper + br i1 %or.1, label %trap, label %for.latch + +for.latch: + store i8 0, i8* %gep.iv, align 4 + %iv.next = add nuw nsw i16 %iv, 1 + br label %for.header + +for.end: + ret void +} + +define void @test_ptr_need_one_upper_check(i32* readonly %src, i32* %dst, i32 %n) { +; CHECK-LABEL: @test_ptr_need_one_upper_check( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP_HEADER:%.*]] +; CHECK: loop.header: +; CHECK-NEXT: [[I_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ADD:%.*]], [[LOOP_LATCH_2:%.*]] ] +; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[I_0]], [[N:%.*]] +; CHECK-NEXT: br i1 [[CMP]], label [[LOOP_CHECK_1:%.*]], label [[EXIT:%.*]] +; CHECK: loop.check.1: +; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[N]] to i64 +; CHECK-NEXT: [[SRC_UPPER:%.*]] = getelementptr i32, i32* [[SRC:%.*]], i64 [[TMP0]] +; CHECK-NEXT: [[ADD]] = add nuw nsw i32 [[I_0]], 2 +; CHECK-NEXT: [[IDXPROM:%.*]] = zext i32 [[ADD]] to i64 +; CHECK-NEXT: [[SRC_IDX:%.*]] = getelementptr inbounds i32, i32* [[SRC]], i64 [[IDXPROM]] +; CHECK-NEXT: [[CMP_SRC_IDX_UPPER:%.*]] = icmp ult i32* [[SRC_IDX]], [[SRC_UPPER]] +; CHECK-NEXT: call void @use(i1 [[CMP_SRC_IDX_UPPER]]) +; CHECK-NEXT: br i1 [[CMP_SRC_IDX_UPPER]], label [[LOOP_LATCH:%.*]], label [[EXIT]] +; CHECK: loop.latch: +; CHECK-NEXT: [[DST_UPPER:%.*]] = getelementptr i32, i32* [[DST:%.*]], i64 [[TMP0]] +; CHECK-NEXT: [[DST_IDX:%.*]] = getelementptr inbounds i32, i32* [[DST]], i64 [[IDXPROM]] +; CHECK-NEXT: [[CMP_DST_IDX_UPPER:%.*]] = icmp ult i32* [[DST_IDX]], [[DST_UPPER]] +; CHECK-NEXT: call void @use(i1 [[CMP_DST_IDX_UPPER]]) +; CHECK-NEXT: br i1 [[CMP_DST_IDX_UPPER]], label [[LOOP_LATCH_2]], label [[EXIT]] +; CHECK: loop.latch.2: +; CHECK-NEXT: br label [[LOOP_HEADER]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop.header + +loop.header: + %i.0 = phi i32 [ 0, %entry ], [ %add, %loop.latch.2 ] + %cmp = icmp ult i32 %i.0, %n + br i1 %cmp, label %loop.check.1, label %exit + +loop.check.1: + %0 = zext i32 %n to i64 + %src.upper = getelementptr i32, i32* %src, i64 %0 + %add = add nuw nsw i32 %i.0, 2 + %idxprom = zext i32 %add to i64 + %src.idx = getelementptr inbounds i32, i32* %src, i64 %idxprom + %cmp.src.idx.upper = icmp ult i32* %src.idx, %src.upper + call void @use(i1 %cmp.src.idx.upper) + br i1 %cmp.src.idx.upper, label %loop.latch, label %exit + +loop.latch: + %dst.upper = getelementptr i32, i32* %dst, i64 %0 + %dst.idx = getelementptr inbounds i32, i32* %dst, i64 %idxprom + %cmp.dst.idx.upper = icmp ult i32* %dst.idx, %dst.upper + call void @use(i1 %cmp.dst.idx.upper) + br i1 %cmp.dst.idx.upper, label %loop.latch.2, label %exit + +loop.latch.2: + br label %loop.header + +exit: + ret void +} + +; Same as test_ptr_need_one_upper_check, but without inbounds GEP. +define void @test_ptr_need_one_upper_check_no_inbounds(i32* readonly %src, i32* %dst, i32 %n) { +; CHECK-LABEL: @test_ptr_need_one_upper_check_no_inbounds( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP_HEADER:%.*]] +; CHECK: loop.header: +; CHECK-NEXT: [[I_0:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ADD:%.*]], [[LOOP_LATCH_2:%.*]] ] +; CHECK-NEXT: [[CMP:%.*]] = icmp ult i32 [[I_0]], [[N:%.*]] +; CHECK-NEXT: br i1 [[CMP]], label [[LOOP_CHECK_1:%.*]], label [[EXIT:%.*]] +; CHECK: loop.check.1: +; CHECK-NEXT: [[TMP0:%.*]] = zext i32 [[N]] to i64 +; CHECK-NEXT: [[SRC_UPPER:%.*]] = getelementptr i32, i32* [[SRC:%.*]], i64 [[TMP0]] +; CHECK-NEXT: [[ADD]] = add nuw nsw i32 [[I_0]], 2 +; CHECK-NEXT: [[IDXPROM:%.*]] = zext i32 [[ADD]] to i64 +; CHECK-NEXT: [[SRC_IDX:%.*]] = getelementptr inbounds i32, i32* [[SRC]], i64 [[IDXPROM]] +; CHECK-NEXT: [[CMP_SRC_IDX_UPPER:%.*]] = icmp ult i32* [[SRC_IDX]], [[SRC_UPPER]] +; CHECK-NEXT: call void @use(i1 [[CMP_SRC_IDX_UPPER]]) +; CHECK-NEXT: br i1 [[CMP_SRC_IDX_UPPER]], label [[LOOP_LATCH:%.*]], label [[EXIT]] +; CHECK: loop.latch: +; CHECK-NEXT: [[DST_UPPER:%.*]] = getelementptr i32, i32* [[DST:%.*]], i64 [[TMP0]] +; CHECK-NEXT: [[DST_IDX:%.*]] = getelementptr inbounds i32, i32* [[DST]], i64 [[IDXPROM]] +; CHECK-NEXT: [[CMP_DST_IDX_UPPER:%.*]] = icmp ult i32* [[DST_IDX]], [[DST_UPPER]] +; CHECK-NEXT: call void @use(i1 [[CMP_DST_IDX_UPPER]]) +; CHECK-NEXT: br i1 [[CMP_DST_IDX_UPPER]], label [[LOOP_LATCH_2]], label [[EXIT]] +; CHECK: loop.latch.2: +; CHECK-NEXT: br label [[LOOP_HEADER]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop.header + +loop.header: + %i.0 = phi i32 [ 0, %entry ], [ %add, %loop.latch.2 ] + %cmp = icmp ult i32 %i.0, %n + br i1 %cmp, label %loop.check.1, label %exit + +loop.check.1: + %0 = zext i32 %n to i64 + %src.upper = getelementptr i32, i32* %src, i64 %0 + %add = add nuw nsw i32 %i.0, 2 + %idxprom = zext i32 %add to i64 + %src.idx = getelementptr inbounds i32, i32* %src, i64 %idxprom + %cmp.src.idx.upper = icmp ult i32* %src.idx, %src.upper + call void @use(i1 %cmp.src.idx.upper) + br i1 %cmp.src.idx.upper, label %loop.latch, label %exit + +loop.latch: + %dst.upper = getelementptr i32, i32* %dst, i64 %0 + %dst.idx = getelementptr inbounds i32, i32* %dst, i64 %idxprom + %cmp.dst.idx.upper = icmp ult i32* %dst.idx, %dst.upper + call void @use(i1 %cmp.dst.idx.upper) + br i1 %cmp.dst.idx.upper, label %loop.latch.2, label %exit + +loop.latch.2: + br label %loop.header + +exit: + ret void +} diff --git a/llvm/test/Transforms/ConstraintElimination/loops-header-tested-pointer-iv.ll b/llvm/test/Transforms/ConstraintElimination/loops-header-tested-pointer-iv.ll new file mode 100644 index 0000000..081057e --- /dev/null +++ b/llvm/test/Transforms/ConstraintElimination/loops-header-tested-pointer-iv.ll @@ -0,0 +1,128 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -constraint-elimination -S %s | FileCheck %s + +declare void @use(i1) + +define void @loop_pointer_iv(i8* %start, i8* %end, i8* %upper) { +; CHECK-LABEL: @loop_pointer_iv( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[END_LT_UPPER:%.*]] = icmp ult i8* [[END:%.*]], [[UPPER:%.*]] +; CHECK-NEXT: br i1 [[END_LT_UPPER]], label [[LOOP_HEADER:%.*]], label [[EXIT:%.*]] +; CHECK: loop.header: +; CHECK-NEXT: [[IV:%.*]] = phi i8* [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ] +; CHECK-NEXT: [[C_2:%.*]] = icmp ule i8* [[IV]], [[END]] +; CHECK-NEXT: call void @use(i1 [[C_2]]) +; CHECK-NEXT: [[T_2:%.*]] = icmp uge i8* [[IV]], [[START]] +; CHECK-NEXT: call void @use(i1 [[T_2]]) +; CHECK-NEXT: [[C_1:%.*]] = icmp ule i8* [[IV]], [[END]] +; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_LATCH]], label [[EXIT]] +; CHECK: loop.latch: +; CHECK-NEXT: [[T_1:%.*]] = icmp ult i8* [[IV]], [[UPPER]] +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: [[IV_NEXT]] = getelementptr inbounds i8, i8* [[IV]], i8 1 +; CHECK-NEXT: br label [[LOOP_HEADER]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + %end.lt.upper = icmp ult i8* %end, %upper + br i1 %end.lt.upper, label %loop.header, label %exit + +loop.header: + %iv = phi i8* [ %start, %entry ], [ %iv.next, %loop.latch ] + %c.2 = icmp ule i8* %iv, %end + call void @use(i1 %c.2) + + %t.2 = icmp uge i8* %iv, %start + call void @use(i1 %t.2) + + %c.1 = icmp ule i8* %iv, %end + br i1 %c.1, label %loop.latch, label %exit + +loop.latch: + %t.1 = icmp ult i8* %iv, %upper + call void @use(i1 %t.1) + + %iv.next = getelementptr inbounds i8, i8* %iv, i8 1 + br label %loop.header + +exit: + ret void +} + +define void @loop_pointer_iv_null_start(i8* %end, i8* %upper) { +; CHECK-LABEL: @loop_pointer_iv_null_start( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[END_LT_UPPER:%.*]] = icmp ult i8* [[END:%.*]], [[UPPER:%.*]] +; CHECK-NEXT: br i1 [[END_LT_UPPER]], label [[LOOP_HEADER:%.*]], label [[EXIT:%.*]] +; CHECK: loop.header: +; CHECK-NEXT: [[IV:%.*]] = phi i8* [ null, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ] +; CHECK-NEXT: [[C_1:%.*]] = icmp ule i8* [[IV]], [[END]] +; CHECK-NEXT: call void @use(i1 [[C_1]]) +; CHECK-NEXT: [[C_2:%.*]] = icmp uge i8* [[IV]], null +; CHECK-NEXT: call void @use(i1 [[C_2]]) +; CHECK-NEXT: [[C_3:%.*]] = icmp ule i8* [[IV]], [[END]] +; CHECK-NEXT: br i1 [[C_3]], label [[LOOP_LATCH]], label [[EXIT]] +; CHECK: loop.latch: +; CHECK-NEXT: [[C_4:%.*]] = icmp ult i8* [[IV]], [[UPPER]] +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: [[IV_NEXT]] = getelementptr inbounds i8, i8* [[IV]], i8 1 +; CHECK-NEXT: br label [[LOOP_HEADER]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + %end.lt.upper = icmp ult i8* %end, %upper + br i1 %end.lt.upper, label %loop.header, label %exit + +loop.header: + %iv = phi i8* [ null, %entry ], [ %iv.next, %loop.latch ] + %c.1 = icmp ule i8* %iv, %end + call void @use(i1 %c.1) + + %c.2 = icmp uge i8* %iv, null + call void @use(i1 %c.2) + + %c.3 = icmp ule i8* %iv, %end + br i1 %c.3, label %loop.latch, label %exit + +loop.latch: + %c.4 = icmp ult i8* %iv, %upper + call void @use(i1 %c.4) + + %iv.next = getelementptr inbounds i8, i8* %iv, i8 1 + br label %loop.header + +exit: + ret void +} + +define void @test_start_null_cmp_null(i8* %start) { +; CHECK-LABEL: @test_start_null_cmp_null( +; CHECK-NEXT: entry: +; CHECK-NEXT: br label [[LOOP_HEADER:%.*]] +; CHECK: loop.header: +; CHECK-NEXT: [[IV:%.*]] = phi i8* [ null, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ] +; CHECK-NEXT: [[CMP_I_I122:%.*]] = icmp eq i8* [[IV]], null +; CHECK-NEXT: br i1 [[CMP_I_I122]], label [[LOOP_LATCH]], label [[EXIT:%.*]] +; CHECK: loop.latch: +; CHECK-NEXT: [[IV_NEXT]] = getelementptr inbounds i8, i8* [[IV]], i64 1 +; CHECK-NEXT: br label [[LOOP_HEADER]] +; CHECK: exit: +; CHECK-NEXT: ret void +; +entry: + br label %loop.header + +loop.header: + %iv = phi i8* [ null, %entry ], [ %iv.next, %loop.latch ] + %cmp.i.i122 = icmp eq i8* %iv, null + br i1 %cmp.i.i122, label %loop.latch, label %exit + +loop.latch: + %iv.next = getelementptr inbounds i8, i8* %iv, i64 1 + br label %loop.header + +exit: + ret void +} diff --git a/llvm/test/Transforms/ConstraintElimination/loops.ll b/llvm/test/Transforms/ConstraintElimination/loops.ll index a0289ab..85c949e 100644 --- a/llvm/test/Transforms/ConstraintElimination/loops.ll +++ b/llvm/test/Transforms/ConstraintElimination/loops.ll @@ -155,7 +155,6 @@ exit: ret i32 20 } - define void @loop_header_dom_or(i32 %y, i1 %c) { ; CHECK-LABEL: @loop_header_dom_or( ; CHECK-NEXT: entry: diff --git a/llvm/test/Transforms/ConstraintElimination/sub-nuw.ll b/llvm/test/Transforms/ConstraintElimination/sub-nuw.ll index 7912c3c..f233a31 100644 --- a/llvm/test/Transforms/ConstraintElimination/sub-nuw.ll +++ b/llvm/test/Transforms/ConstraintElimination/sub-nuw.ll @@ -237,6 +237,4 @@ if.end: ; preds = %entry ret void } - declare void @use(i1) -declare void @llvm.trap() diff --git a/llvm/test/Transforms/ConstraintElimination/sub.ll b/llvm/test/Transforms/ConstraintElimination/sub.ll index bd78f9a..6705771 100644 --- a/llvm/test/Transforms/ConstraintElimination/sub.ll +++ b/llvm/test/Transforms/ConstraintElimination/sub.ll @@ -239,4 +239,3 @@ if.end: ; preds = %entry declare void @use(i1) -declare void @llvm.trap() diff --git a/llvm/test/Transforms/ConstraintElimination/vector-compares.ll b/llvm/test/Transforms/ConstraintElimination/vector-compares.ll new file mode 100644 index 0000000..ea29874 --- /dev/null +++ b/llvm/test/Transforms/ConstraintElimination/vector-compares.ll @@ -0,0 +1,70 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -constraint-elimination -S %s | FileCheck %s + +declare void @use(i1) + +; Make sure we do not crash when trying to inject info about vector values from SCEV. +define void @test_vector_iv(i32 %x, i1 %c) { +; CHECK-LABEL: @test_vector_iv( +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 [[C:%.*]], label [[PRE:%.*]], label [[BB2:%.*]] +; CHECK: pre: +; CHECK-NEXT: [[C_1:%.*]] = icmp ule i32 [[X:%.*]], 10 +; CHECK-NEXT: br i1 [[C_1]], label [[LOOP:%.*]], label [[BB2]] +; CHECK: loop: +; CHECK-NEXT: [[IV:%.*]] = phi <4 x i8> [ zeroinitializer, [[PRE]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ] +; CHECK-NEXT: [[T_1:%.*]] = icmp ule i32 [[X]], 10 +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: [[F_1:%.*]] = icmp ugt i32 [[X]], 10 +; CHECK-NEXT: call void @use(i1 false) +; CHECK-NEXT: [[C_2:%.*]] = icmp ule i32 [[X]], 9 +; CHECK-NEXT: call void @use(i1 [[C_2]]) +; CHECK-NEXT: [[C_3:%.*]] = icmp ugt i32 [[X]], 9 +; CHECK-NEXT: call void @use(i1 [[C_3]]) +; CHECK-NEXT: [[IV_NEXT]] = add nuw nsw <4 x i8> [[IV]], +; CHECK-NEXT: [[E:%.*]] = extractelement <4 x i8> [[IV_NEXT]], i8 2 +; CHECK-NEXT: [[EC:%.*]] = icmp eq i8 [[E]], 100 +; CHECK-NEXT: br i1 [[EC]], label [[EXIT:%.*]], label [[LOOP]] +; CHECK: exit: +; CHECK-NEXT: [[C_4:%.*]] = icmp ule i32 [[X]], 10 +; CHECK-NEXT: call void @use(i1 true) +; CHECK-NEXT: ret void +; CHECK: bb2: +; CHECK-NEXT: [[C_5:%.*]] = icmp ugt i32 [[X]], 10 +; CHECK-NEXT: call void @use(i1 [[C_5]]) +; CHECK-NEXT: ret void +; +entry: + br i1 %c, label %pre, label %bb2 + +pre: + %c.1 = icmp ule i32 %x, 10 + br i1 %c.1, label %loop, label %bb2 + +loop: + %iv = phi <4 x i8> [ zeroinitializer, %pre ], [ %iv.next, %loop ] + %t.1 = icmp ule i32 %x, 10 + call void @use(i1 %t.1) + %f.1 = icmp ugt i32 %x, 10 + call void @use(i1 %f.1) + + %c.2 = icmp ule i32 %x, 9 + call void @use(i1 %c.2) + %c.3 = icmp ugt i32 %x, 9 + call void @use(i1 %c.3) + + %iv.next = add nuw nsw <4 x i8> %iv, + %e = extractelement <4 x i8> %iv.next, i8 2 + %ec = icmp eq i8 %e, 100 + br i1 %ec, label %exit, label %loop + +exit: + %c.4 = icmp ule i32 %x, 10 + call void @use(i1 %c.4) + ret void + +bb2: + %c.5 = icmp ugt i32 %x, 10 + call void @use(i1 %c.5) + ret void +} diff --git a/llvm/test/Transforms/ConstraintElimination/wrapping-math.ll b/llvm/test/Transforms/ConstraintElimination/wrapping-math.ll new file mode 100644 index 0000000..fcab0c8 --- /dev/null +++ b/llvm/test/Transforms/ConstraintElimination/wrapping-math.ll @@ -0,0 +1,73 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt -constraint-elimination -S %s | FileCheck %s + +define i1 @wrapping_add_unknown_1(i8 %a) { +; CHECK-LABEL: @wrapping_add_unknown_1( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[SUB:%.*]] = add i8 [[A:%.*]], -1 +; CHECK-NEXT: [[CMP:%.*]] = icmp eq i8 [[SUB]], 0 +; CHECK-NEXT: ret i1 [[CMP]] +; +entry: + %sub = add i8 %a, -1 + %cmp = icmp eq i8 %sub, 0 + ret i1 %cmp +} + +define i1 @wrapping_add_known_1(i8 %a) { +; CHECK-LABEL: @wrapping_add_known_1( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[PRE:%.*]] = icmp eq i8 [[A:%.*]], 1 +; CHECK-NEXT: br i1 [[PRE]], label [[THEN:%.*]], label [[ELSE:%.*]] +; CHECK: then: +; CHECK-NEXT: [[SUB_1:%.*]] = add i8 [[A]], -1 +; CHECK-NEXT: [[C_1:%.*]] = icmp eq i8 [[SUB_1]], 0 +; CHECK-NEXT: ret i1 [[C_1]] +; CHECK: else: +; CHECK-NEXT: [[SUB_2:%.*]] = add i8 [[A]], -1 +; CHECK-NEXT: [[C_2:%.*]] = icmp eq i8 [[SUB_2]], 0 +; CHECK-NEXT: ret i1 [[C_2]] +; +entry: + %pre = icmp eq i8 %a, 1 + br i1 %pre, label %then, label %else + +then: + %sub.1 = add i8 %a, -1 + %c.1 = icmp eq i8 %sub.1, 0 + ret i1 %c.1 + +else: + %sub.2 = add i8 %a, -1 + %c.2 = icmp eq i8 %sub.2, 0 + ret i1 %c.2 +} + +define i1 @wrapping_add_unknown_2(i8 %a) { +; CHECK-LABEL: @wrapping_add_unknown_2( +; CHECK-NEXT: entry: +; CHECK-NEXT: [[PRE:%.*]] = icmp eq i8 [[A:%.*]], 0 +; CHECK-NEXT: br i1 [[PRE]], label [[THEN:%.*]], label [[ELSE:%.*]] +; CHECK: then: +; CHECK-NEXT: [[SUB_1:%.*]] = add i8 [[A]], -1 +; CHECK-NEXT: [[C_1:%.*]] = icmp eq i8 [[SUB_1]], 0 +; CHECK-NEXT: ret i1 [[C_1]] +; CHECK: else: +; CHECK-NEXT: [[SUB_2:%.*]] = add i8 [[A]], -1 +; CHECK-NEXT: [[C_2:%.*]] = icmp eq i8 [[SUB_2]], 0 +; CHECK-NEXT: ret i1 [[C_2]] +; +entry: + %pre = icmp eq i8 %a, 0 + br i1 %pre, label %then, label %else + +then: + %sub.1 = add i8 %a, -1 + %c.1 = icmp eq i8 %sub.1, 0 + ret i1 %c.1 + +else: + %sub.2 = add i8 %a, -1 + %c.2 = icmp eq i8 %sub.2, 0 + ret i1 %c.2 +} -- 2.7.4