llvm/test/Transforms/IndVarSimplify/monotonic_checks.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt -passes=indvars -S < %s | FileCheck %s
   3
   4 ; Monotonic decrementing iv. we should be able to prove that %iv.next <s len
   5 ; basing on its nsw and the fact that its starting value <s len.
   6 define i32 @test_01(ptr %p) {
   7 ; CHECK-LABEL: @test_01(
   8 ; CHECK-NEXT:  entry:
   9 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, [[RNG0:!range !.*]]
  10 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  11 ; CHECK:       loop:
  12 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
  13 ; CHECK-NEXT:    [[IV_NEXT]] = add nsw i32 [[IV]], -1
  14 ; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
  15 ; CHECK:       backedge:
  16 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 0
  17 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
  18 ; CHECK:       fail:
  19 ; CHECK-NEXT:    ret i32 -1
  20 ; CHECK:       exit:
  21 ; CHECK-NEXT:    ret i32 0
  22 ;
  23 entry:
  24   %len = load i32, ptr %p, !range !0
  25   br label %loop
  26
  27 loop:
  28   %iv = phi i32 [%len, %entry], [%iv.next, %backedge]
  29   %iv.next = add i32 %iv, -1
  30   %rc = icmp slt i32 %iv.next, %len
  31   br i1 %rc, label %backedge, label %fail
  32
  33 backedge:
  34   %loop.cond = icmp ne i32 %iv, 0
  35   br i1 %loop.cond, label %loop, label %exit
  36
  37 fail:
  38   ret i32 -1
  39
  40 exit:
  41   ret i32 0
  42 }
  43
  44 ; We should not remove this range check because signed overflow is possible here (start at len = 0).
  45 define i32 @test_01_neg(ptr %p) {
  46 ; CHECK-LABEL: @test_01_neg(
  47 ; CHECK-NEXT:  entry:
  48 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, [[RNG0]]
  49 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  50 ; CHECK:       loop:
  51 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
  52 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], -1
  53 ; CHECK-NEXT:    [[RC:%.*]] = icmp slt i32 [[IV_NEXT]], [[LEN]]
  54 ; CHECK-NEXT:    br i1 [[RC]], label [[BACKEDGE]], label [[FAIL:%.*]]
  55 ; CHECK:       backedge:
  56 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 1
  57 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
  58 ; CHECK:       fail:
  59 ; CHECK-NEXT:    ret i32 -1
  60 ; CHECK:       exit:
  61 ; CHECK-NEXT:    ret i32 0
  62 ;
  63 entry:
  64   %len = load i32, ptr %p, !range !0
  65   br label %loop
  66
  67 loop:
  68   %iv = phi i32 [%len, %entry], [%iv.next, %backedge]
  69   %iv.next = add i32 %iv, -1
  70   %rc = icmp slt i32 %iv.next, %len
  71   br i1 %rc, label %backedge, label %fail
  72
  73 backedge:
  74   %loop.cond = icmp ne i32 %iv, 1
  75   br i1 %loop.cond, label %loop, label %exit
  76
  77 fail:
  78   ret i32 -1
  79
  80 exit:
  81   ret i32 0
  82 }
  83
  84 ; Monotonic incrementing iv. we should be able to prove that %iv.next >s len
  85 ; basing on its nsw and the fact that its starting value >s len.
  86 define i32 @test_02(ptr %p) {
  87 ; CHECK-LABEL: @test_02(
  88 ; CHECK-NEXT:  entry:
  89 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, [[RNG1:!range !.*]]
  90 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  91 ; CHECK:       loop:
  92 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
  93 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
  94 ; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
  95 ; CHECK:       backedge:
  96 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 0
  97 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
  98 ; CHECK:       fail:
  99 ; CHECK-NEXT:    ret i32 -1
 100 ; CHECK:       exit:
 101 ; CHECK-NEXT:    ret i32 0
 102 ;
 103 entry:
 104   %len = load i32, ptr %p, !range !1
 105   br label %loop
 106
 107 loop:
 108   %iv = phi i32 [%len, %entry], [%iv.next, %backedge]
 109   %iv.next = add i32 %iv, 1
 110   %rc = icmp sgt i32 %iv.next, %len
 111   br i1 %rc, label %backedge, label %fail
 112
 113 backedge:
 114   %loop.cond = icmp ne i32 %iv, 0
 115   br i1 %loop.cond, label %loop, label %exit
 116
 117 fail:
 118   ret i32 -1
 119
 120 exit:
 121   ret i32 0
 122 }
 123
 124 ; We should not remove this range check because signed overflow is possible here (start at len = -1).
 125 define i32 @test_02_neg(ptr %p) {
 126 ; CHECK-LABEL: @test_02_neg(
 127 ; CHECK-NEXT:  entry:
 128 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, [[RNG1]]
 129 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 130 ; CHECK:       loop:
 131 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 132 ; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
 133 ; CHECK-NEXT:    [[RC:%.*]] = icmp sgt i32 [[IV_NEXT]], [[LEN]]
 134 ; CHECK-NEXT:    br i1 [[RC]], label [[BACKEDGE]], label [[FAIL:%.*]]
 135 ; CHECK:       backedge:
 136 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], -2
 137 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 138 ; CHECK:       fail:
 139 ; CHECK-NEXT:    ret i32 -1
 140 ; CHECK:       exit:
 141 ; CHECK-NEXT:    ret i32 0
 142 ;
 143 entry:
 144   %len = load i32, ptr %p, !range !1
 145   br label %loop
 146
 147 loop:
 148   %iv = phi i32 [%len, %entry], [%iv.next, %backedge]
 149   %iv.next = add i32 %iv, 1
 150   %rc = icmp sgt i32 %iv.next, %len
 151   br i1 %rc, label %backedge, label %fail
 152
 153 backedge:
 154   %loop.cond = icmp ne i32 %iv, -2
 155   br i1 %loop.cond, label %loop, label %exit
 156
 157 fail:
 158   ret i32 -1
 159
 160 exit:
 161   ret i32 0
 162 }
 163
 164 define i32 @test_03(ptr %p) {
 165 ; CHECK-LABEL: @test_03(
 166 ; CHECK-NEXT:  entry:
 167 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, [[RNG2:!range !.*]]
 168 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 169 ; CHECK:       loop:
 170 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 171 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 172 ; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
 173 ; CHECK:       backedge:
 174 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 1000
 175 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 176 ; CHECK:       fail:
 177 ; CHECK-NEXT:    ret i32 -1
 178 ; CHECK:       exit:
 179 ; CHECK-NEXT:    ret i32 0
 180 ;
 181 entry:
 182   %len = load i32, ptr %p, !range !2
 183   br label %loop
 184
 185 loop:
 186   %iv = phi i32 [%len, %entry], [%iv.next, %backedge]
 187   %iv.next = add i32 %iv, 1
 188   %rc = icmp sgt i32 %iv.next, %len
 189   br i1 %rc, label %backedge, label %fail
 190
 191 backedge:
 192   %loop.cond = icmp ne i32 %iv, 1000
 193   br i1 %loop.cond, label %loop, label %exit
 194
 195 fail:
 196   ret i32 -1
 197
 198 exit:
 199   ret i32 0
 200 }
 201
 202 define i32 @test_04(ptr %p) {
 203 ; CHECK-LABEL: @test_04(
 204 ; CHECK-NEXT:  entry:
 205 ; CHECK-NEXT:    [[LEN:%.*]] = load i32, ptr [[P:%.*]], align 4, [[RNG2]]
 206 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 207 ; CHECK:       loop:
 208 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[LEN]], [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
 209 ; CHECK-NEXT:    [[IV_NEXT]] = add nsw i32 [[IV]], -1
 210 ; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[FAIL:%.*]]
 211 ; CHECK:       backedge:
 212 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[IV]], 0
 213 ; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
 214 ; CHECK:       fail:
 215 ; CHECK-NEXT:    ret i32 -1
 216 ; CHECK:       exit:
 217 ; CHECK-NEXT:    ret i32 0
 218 ;
 219 entry:
 220   %len = load i32, ptr %p, !range !2
 221   br label %loop
 222
 223 loop:
 224   %iv = phi i32 [%len, %entry], [%iv.next, %backedge]
 225   %iv.next = add i32 %iv, -1
 226   %rc = icmp slt i32 %iv.next, %len
 227   br i1 %rc, label %backedge, label %fail
 228
 229 backedge:
 230   %loop.cond = icmp ne i32 %iv, 0
 231   br i1 %loop.cond, label %loop, label %exit
 232
 233 fail:
 234   ret i32 -1
 235
 236 exit:
 237   ret i32 0
 238 }
 239
 240 !0 = !{i32 0, i32 2147483647}
 241 !1 = !{i32 -2147483648, i32 0}
 242 !2 = !{i32 0, i32 1000}