llvm/test/Transforms/IndVarSimplify/strengthen-overflow.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -passes=indvars -S | FileCheck %s
   3
   4 define i32 @test.signed.add.0(ptr %array, i32 %length, i32 %init) {
   5 ; CHECK-LABEL: @test.signed.add.0(
   6 ; CHECK-NEXT:  entry:
   7 ; CHECK-NEXT:    [[UPPER:%.*]] = icmp slt i32 [[INIT:%.*]], [[LENGTH:%.*]]
   8 ; CHECK-NEXT:    br i1 [[UPPER]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
   9 ; CHECK:       loop.preheader:
  10 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  11 ; CHECK:       loop:
  12 ; CHECK-NEXT:    [[CIV:%.*]] = phi i32 [ [[CIV_INC:%.*]], [[LATCH:%.*]] ], [ [[INIT]], [[LOOP_PREHEADER]] ]
  13 ; CHECK-NEXT:    [[CIV_INC]] = add nsw i32 [[CIV]], 1
  14 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[CIV_INC]], [[LENGTH]]
  15 ; CHECK-NEXT:    br i1 [[CMP]], label [[LATCH]], label [[BREAK:%.*]]
  16 ; CHECK:       latch:
  17 ; CHECK-NEXT:    store i32 0, ptr [[ARRAY:%.*]], align 4
  18 ; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[BREAK]]
  19 ; CHECK:       break:
  20 ; CHECK-NEXT:    [[CIV_INC_LCSSA:%.*]] = phi i32 [ [[LENGTH]], [[LATCH]] ], [ [[LENGTH]], [[LOOP]] ]
  21 ; CHECK-NEXT:    ret i32 [[CIV_INC_LCSSA]]
  22 ; CHECK:       exit:
  23 ; CHECK-NEXT:    ret i32 42
  24 ;
  25   entry:
  26   %upper = icmp slt i32 %init, %length
  27   br i1 %upper, label %loop, label %exit
  28
  29   loop:
  30   %civ = phi i32 [ %init, %entry ], [ %civ.inc, %latch ]
  31   %civ.inc = add i32 %civ, 1
  32   %cmp = icmp slt i32 %civ.inc, %length
  33   br i1 %cmp, label %latch, label %break
  34
  35   latch:
  36   store i32 0, ptr %array
  37   %check = icmp slt i32 %civ.inc, %length
  38   br i1 %check, label %loop, label %break
  39
  40   break:
  41   ret i32 %civ.inc
  42
  43   exit:
  44   ret i32 42
  45 }
  46
  47 define i32 @test.signed.add.1(ptr %array, i32 %length, i32 %init) {
  48 ; CHECK-LABEL: @test.signed.add.1(
  49 ; CHECK-NEXT:  entry:
  50 ; CHECK-NEXT:    [[UPPER:%.*]] = icmp sle i32 [[INIT:%.*]], [[LENGTH:%.*]]
  51 ; CHECK-NEXT:    br i1 [[UPPER]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
  52 ; CHECK:       loop.preheader:
  53 ; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[INIT]], 1
  54 ; CHECK-NEXT:    [[SMAX:%.*]] = call i32 @llvm.smax.i32(i32 [[LENGTH]], i32 [[TMP0]])
  55 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  56 ; CHECK:       loop:
  57 ; CHECK-NEXT:    [[CIV:%.*]] = phi i32 [ [[CIV_INC:%.*]], [[LATCH:%.*]] ], [ [[INIT]], [[LOOP_PREHEADER]] ]
  58 ; CHECK-NEXT:    [[CIV_INC]] = add i32 [[CIV]], 1
  59 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[CIV_INC]], [[LENGTH]]
  60 ; CHECK-NEXT:    br i1 [[CMP]], label [[LATCH]], label [[BREAK:%.*]]
  61 ; CHECK:       latch:
  62 ; CHECK-NEXT:    store i32 0, ptr [[ARRAY:%.*]], align 4
  63 ; CHECK-NEXT:    br i1 true, label [[LOOP]], label [[BREAK]]
  64 ; CHECK:       break:
  65 ; CHECK-NEXT:    [[CIV_INC_LCSSA:%.*]] = phi i32 [ [[SMAX]], [[LATCH]] ], [ [[SMAX]], [[LOOP]] ]
  66 ; CHECK-NEXT:    ret i32 [[CIV_INC_LCSSA]]
  67 ; CHECK:       exit:
  68 ; CHECK-NEXT:    ret i32 42
  69 ;
  70   entry:
  71   %upper = icmp sle i32 %init, %length
  72   br i1 %upper, label %loop, label %exit
  73
  74   loop:
  75   %civ = phi i32 [ %init, %entry ], [ %civ.inc, %latch ]
  76   %civ.inc = add i32 %civ, 1
  77   %cmp = icmp slt i32 %civ.inc, %length
  78   br i1 %cmp, label %latch, label %break
  79
  80   latch:
  81   store i32 0, ptr %array
  82   %check = icmp slt i32 %civ.inc, %length
  83   br i1 %check, label %loop, label %break
  84
  85   break:
  86   ret i32 %civ.inc
  87
  88   exit:
  89   ret i32 42
  90 }
  91
  92 define i32 @test.unsigned.add.0(ptr %array, i32 %length, i32 %init) {
  93 ; CHECK-LABEL: @test.unsigned.add.0(
  94 ; CHECK-NEXT:  entry:
  95 ; CHECK-NEXT:    [[UPPER:%.*]] = icmp ult i32 [[INIT:%.*]], [[LENGTH:%.*]]
  96 ; CHECK-NEXT:    br i1 [[UPPER]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
  97 ; CHECK:       loop.preheader:
  98 ; CHECK-NEXT:    br label [[LOOP:%.*]]
  99 ; CHECK:       loop:
 100 ; CHECK-NEXT:    [[CIV:%.*]] = phi i32 [ [[CIV_INC:%.*]], [[LATCH:%.*]] ], [ [[INIT]], [[LOOP_PREHEADER]] ]
 101 ; CHECK-NEXT:    [[CIV_INC]] = add nuw i32 [[CIV]], 1
 102 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[CIV_INC]], [[LENGTH]]
 103 ; CHECK-NEXT:    br i1 [[CMP]], label [[LATCH]], label [[BREAK:%.*]]
 104 ; CHECK:       latch:
 105 ; CHECK-NEXT:    store i32 0, ptr [[ARRAY:%.*]], align 4
 106 ; CHECK-NEXT:    [[CHECK:%.*]] = icmp ult i32 [[CIV_INC]], [[LENGTH]]
 107 ; CHECK-NEXT:    br i1 [[CHECK]], label [[LOOP]], label [[BREAK]]
 108 ; CHECK:       break:
 109 ; CHECK-NEXT:    [[CIV_INC_LCSSA:%.*]] = phi i32 [ [[CIV_INC]], [[LATCH]] ], [ [[CIV_INC]], [[LOOP]] ]
 110 ; CHECK-NEXT:    ret i32 [[CIV_INC_LCSSA]]
 111 ; CHECK:       exit:
 112 ; CHECK-NEXT:    ret i32 42
 113 ;
 114   entry:
 115   %upper = icmp ult i32 %init, %length
 116   br i1 %upper, label %loop, label %exit
 117
 118   loop:
 119   %civ = phi i32 [ %init, %entry ], [ %civ.inc, %latch ]
 120   %civ.inc = add i32 %civ, 1
 121   %cmp = icmp slt i32 %civ.inc, %length
 122   br i1 %cmp, label %latch, label %break
 123
 124   latch:
 125   store i32 0, ptr %array
 126   %check = icmp ult i32 %civ.inc, %length
 127   br i1 %check, label %loop, label %break
 128
 129   break:
 130   ret i32 %civ.inc
 131
 132   exit:
 133   ret i32 42
 134 }
 135
 136 define i32 @test.unsigned.add.1(ptr %array, i32 %length, i32 %init) {
 137 ; CHECK-LABEL: @test.unsigned.add.1(
 138 ; CHECK-NEXT:  entry:
 139 ; CHECK-NEXT:    [[UPPER:%.*]] = icmp ule i32 [[INIT:%.*]], [[LENGTH:%.*]]
 140 ; CHECK-NEXT:    br i1 [[UPPER]], label [[LOOP_PREHEADER:%.*]], label [[EXIT:%.*]]
 141 ; CHECK:       loop.preheader:
 142 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 143 ; CHECK:       loop:
 144 ; CHECK-NEXT:    [[CIV:%.*]] = phi i32 [ [[CIV_INC:%.*]], [[LATCH:%.*]] ], [ [[INIT]], [[LOOP_PREHEADER]] ]
 145 ; CHECK-NEXT:    [[CIV_INC]] = add i32 [[CIV]], 1
 146 ; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[CIV_INC]], [[LENGTH]]
 147 ; CHECK-NEXT:    br i1 [[CMP]], label [[LATCH]], label [[BREAK:%.*]]
 148 ; CHECK:       latch:
 149 ; CHECK-NEXT:    store i32 0, ptr [[ARRAY:%.*]], align 4
 150 ; CHECK-NEXT:    [[CHECK:%.*]] = icmp ult i32 [[CIV_INC]], [[LENGTH]]
 151 ; CHECK-NEXT:    br i1 [[CHECK]], label [[LOOP]], label [[BREAK]]
 152 ; CHECK:       break:
 153 ; CHECK-NEXT:    [[CIV_INC_LCSSA:%.*]] = phi i32 [ [[CIV_INC]], [[LATCH]] ], [ [[CIV_INC]], [[LOOP]] ]
 154 ; CHECK-NEXT:    ret i32 [[CIV_INC_LCSSA]]
 155 ; CHECK:       exit:
 156 ; CHECK-NEXT:    ret i32 42
 157 ;
 158   entry:
 159   %upper = icmp ule i32 %init, %length
 160   br i1 %upper, label %loop, label %exit
 161
 162   loop:
 163   %civ = phi i32 [ %init, %entry ], [ %civ.inc, %latch ]
 164   %civ.inc = add i32 %civ, 1
 165   %cmp = icmp slt i32 %civ.inc, %length
 166   br i1 %cmp, label %latch, label %break
 167
 168   latch:
 169   store i32 0, ptr %array
 170   %check = icmp ult i32 %civ.inc, %length
 171   br i1 %check, label %loop, label %break
 172
 173   break:
 174   ret i32 %civ.inc
 175
 176   exit:
 177   ret i32 42
 178 }
 179
 180 define hidden void @test.shl.exact.equal() {
 181 ; CHECK-LABEL: @test.shl.exact.equal(
 182 ; CHECK-NEXT:  entry:
 183 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 184 ; CHECK:       for.body:
 185 ; CHECK-NEXT:    [[K_021:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
 186 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 1, [[K_021]]
 187 ; CHECK-NEXT:    [[SHR1:%.*]] = ashr exact i32 [[SHL]], 1
 188 ; CHECK-NEXT:    [[SHR2:%.*]] = lshr exact i32 [[SHL]], 1
 189 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[K_021]], 1
 190 ; CHECK-NEXT:    br i1 true, label [[FOR_END:%.*]], label [[FOR_BODY]]
 191 ; CHECK:       for.end:
 192 ; CHECK-NEXT:    ret void
 193 ;
 194 entry:
 195   br label %for.body
 196
 197 for.body:
 198   %k.021 = phi i32 [ 1, %entry ], [ %inc, %for.body ]
 199   %shl = shl i32 1, %k.021
 200   %shr1 = ashr i32 %shl, 1
 201   %shr2 = lshr i32 %shl, 1
 202   %inc = add nuw nsw i32 %k.021, 1
 203   %exitcond = icmp eq i32 %inc, 9
 204   br i1 %exitcond, label %for.end, label %for.body
 205
 206 for.end:
 207   ret void
 208 }
 209
 210 define hidden void @test.shl.exact.greater() {
 211 ; CHECK-LABEL: @test.shl.exact.greater(
 212 ; CHECK-NEXT:  entry:
 213 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 214 ; CHECK:       for.body:
 215 ; CHECK-NEXT:    [[K_021:%.*]] = phi i32 [ 3, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
 216 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 1, [[K_021]]
 217 ; CHECK-NEXT:    [[SHR1:%.*]] = ashr exact i32 [[SHL]], 2
 218 ; CHECK-NEXT:    [[SHR2:%.*]] = lshr exact i32 [[SHL]], 2
 219 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[K_021]], 1
 220 ; CHECK-NEXT:    br i1 true, label [[FOR_END:%.*]], label [[FOR_BODY]]
 221 ; CHECK:       for.end:
 222 ; CHECK-NEXT:    ret void
 223 ;
 224 entry:
 225   br label %for.body
 226
 227 for.body:
 228   %k.021 = phi i32 [ 3, %entry ], [ %inc, %for.body ]
 229   %shl = shl i32 1, %k.021
 230   %shr1 = ashr i32 %shl, 2
 231   %shr2 = lshr i32 %shl, 2
 232   %inc = add nuw nsw i32 %k.021, 1
 233   %exitcond = icmp eq i32 %inc, 9
 234   br i1 %exitcond, label %for.end, label %for.body
 235
 236 for.end:
 237   ret void
 238 }
 239
 240 define hidden void @test.shl.exact.unbound(i32 %arg) {
 241 ; CHECK-LABEL: @test.shl.exact.unbound(
 242 ; CHECK-NEXT:  entry:
 243 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 244 ; CHECK:       for.body:
 245 ; CHECK-NEXT:    [[K_021:%.*]] = phi i32 [ 2, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
 246 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 1, [[K_021]]
 247 ; CHECK-NEXT:    [[SHR1:%.*]] = ashr exact i32 [[SHL]], 2
 248 ; CHECK-NEXT:    [[SHR2:%.*]] = lshr exact i32 [[SHL]], 2
 249 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[K_021]], 1
 250 ; CHECK-NEXT:    br i1 true, label [[FOR_END:%.*]], label [[FOR_BODY]]
 251 ; CHECK:       for.end:
 252 ; CHECK-NEXT:    ret void
 253 ;
 254 entry:
 255   br label %for.body
 256
 257 for.body:
 258   %k.021 = phi i32 [ 2, %entry ], [ %inc, %for.body ]
 259   %shl = shl i32 1, %k.021
 260   %shr1 = ashr i32 %shl, 2
 261   %shr2 = lshr i32 %shl, 2
 262   %inc = add nuw nsw i32 %k.021, 1
 263   %exitcond = icmp eq i32 %inc, %arg
 264   br i1 %exitcond, label %for.end, label %for.body
 265
 266 for.end:
 267   ret void
 268 }
 269
 270 define hidden void @test.shl.nonexact() {
 271 ; CHECK-LABEL: @test.shl.nonexact(
 272 ; CHECK-NEXT:  entry:
 273 ; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
 274 ; CHECK:       for.body:
 275 ; CHECK-NEXT:    [[K_021:%.*]] = phi i32 [ 2, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_BODY]] ]
 276 ; CHECK-NEXT:    [[SHL:%.*]] = shl i32 1, [[K_021]]
 277 ; CHECK-NEXT:    [[SHR1:%.*]] = ashr i32 [[SHL]], 3
 278 ; CHECK-NEXT:    [[SHR2:%.*]] = lshr i32 [[SHL]], 3
 279 ; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[K_021]], 1
 280 ; CHECK-NEXT:    br i1 true, label [[FOR_END:%.*]], label [[FOR_BODY]]
 281 ; CHECK:       for.end:
 282 ; CHECK-NEXT:    ret void
 283 ;
 284 entry:
 285   br label %for.body
 286
 287 for.body:
 288   %k.021 = phi i32 [ 2, %entry ], [ %inc, %for.body ]
 289   %shl = shl i32 1, %k.021
 290   %shr1 = ashr i32 %shl, 3
 291   %shr2 = lshr i32 %shl, 3
 292   %inc = add nuw nsw i32 %k.021, 1
 293   %exitcond = icmp eq i32 %inc, 9
 294   br i1 %exitcond, label %for.end, label %for.body
 295
 296 for.end:
 297   ret void
 298 }
 299
 300 define void @test_infer_nsw(ptr %p) {
 301 ; CHECK-LABEL: @test_infer_nsw(
 302 ; CHECK-NEXT:  bb:
 303 ; CHECK-NEXT:    [[FREEZE:%.*]] = freeze i32 poison
 304 ; CHECK-NEXT:    br label [[BB1:%.*]]
 305 ; CHECK:       bb1:
 306 ; CHECK-NEXT:    [[PHI:%.*]] = phi i32 [ [[ADD:%.*]], [[BB2:%.*]] ], [ 0, [[BB:%.*]] ]
 307 ; CHECK-NEXT:    [[SUB:%.*]] = sub nuw nsw i32 [[FREEZE]], [[PHI]]
 308 ; CHECK-NEXT:    [[ICMP:%.*]] = icmp sgt i32 [[SUB]], 1
 309 ; CHECK-NEXT:    br i1 [[ICMP]], label [[BB2]], label [[BB3:%.*]]
 310 ; CHECK:       bb2:
 311 ; CHECK-NEXT:    store i16 1, ptr [[P:%.*]], align 2
 312 ; CHECK-NEXT:    [[ADD]] = add nuw i32 [[PHI]], 2
 313 ; CHECK-NEXT:    br label [[BB1]]
 314 ; CHECK:       bb3:
 315 ; CHECK-NEXT:    ret void
 316 ;
 317 bb:
 318   %freeze = freeze i32 poison
 319   br label %bb1
 320
 321 bb1:                                              ; preds = %bb2, %bb
 322   %phi = phi i32 [ %add, %bb2 ], [ 0, %bb ]
 323   %sub = sub i32 %freeze, %phi
 324   %icmp = icmp sgt i32 %sub, 1
 325   br i1 %icmp, label %bb2, label %bb3
 326
 327 bb2:                                              ; preds = %bb1
 328   store i16 1, ptr %p, align 2
 329   %add = add nuw i32 %phi, 2
 330   br label %bb1
 331
 332 bb3:                                              ; preds = %bb1
 333   ret void
 334 }
 335
 336 !0 = !{i32 0, i32 2}
 337 !1 = !{i32 0, i32 42}