llvm/test/Transforms/IndVarSimplify/monotonic_checks.ll

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