test/Transforms/IndVarSimplify/loop-invariant-conditions.ll

   1 ; RUN: opt -S -indvars %s | FileCheck %s
   2 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
   3 target triple = "x86_64-unknown-linux-gnu"
   4
   5 define void @test1(i64 %start) {
   6 ; CHECK-LABEL: @test1
   7 entry:
   8   br label %loop
   9
  10 loop:
  11   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
  12   %indvars.iv.next = add nsw i64 %indvars.iv, 1
  13 ; CHECK: %cmp1 = icmp slt i64 %start, -1
  14   %cmp1 = icmp slt i64 %indvars.iv, -1
  15   br i1 %cmp1, label %for.end, label %loop
  16
  17 for.end:                                          ; preds = %if.end, %entry
  18   ret void
  19 }
  20
  21 define void @test2(i64 %start) {
  22 ; CHECK-LABEL: @test2
  23 entry:
  24   br label %loop
  25
  26 loop:
  27   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
  28   %indvars.iv.next = add nsw i64 %indvars.iv, 1
  29 ; CHECK: %cmp1 = icmp sle i64 %start, -1
  30   %cmp1 = icmp sle i64 %indvars.iv, -1
  31   br i1 %cmp1, label %for.end, label %loop
  32
  33 for.end:                                          ; preds = %if.end, %entry
  34   ret void
  35 }
  36
  37 ; As long as the test dominates the backedge, we're good
  38 define void @test3(i64 %start) {
  39 ; CHECK-LABEL: @test3
  40 entry:
  41   br label %loop
  42
  43 loop:
  44   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
  45   %indvars.iv.next = add nsw i64 %indvars.iv, 1
  46   %cmp = icmp eq i64 %indvars.iv.next, 25
  47   br i1 %cmp, label %backedge, label %for.end
  48
  49 backedge:
  50   ; prevent flattening, needed to make sure we're testing what we intend
  51   call void @foo()
  52 ; CHECK: %cmp1 = icmp slt i64 %start, -1
  53   %cmp1 = icmp slt i64 %indvars.iv, -1
  54   br i1 %cmp1, label %for.end, label %loop
  55
  56 for.end:                                          ; preds = %if.end, %entry
  57   ret void
  58 }
  59
  60 define void @test4(i64 %start) {
  61 ; CHECK-LABEL: @test4
  62 entry:
  63   br label %loop
  64
  65 loop:
  66   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
  67   %indvars.iv.next = add nsw i64 %indvars.iv, 1
  68   %cmp = icmp eq i64 %indvars.iv.next, 25
  69   br i1 %cmp, label %backedge, label %for.end
  70
  71 backedge:
  72   ; prevent flattening, needed to make sure we're testing what we intend
  73   call void @foo()
  74 ; CHECK: %cmp1 = icmp sgt i64 %start, -1
  75   %cmp1 = icmp sgt i64 %indvars.iv, -1
  76   br i1 %cmp1, label %loop, label %for.end
  77
  78 for.end:                                          ; preds = %if.end, %entry
  79   ret void
  80 }
  81
  82 define void @test5(i64 %start) {
  83 ; CHECK-LABEL: @test5
  84 entry:
  85   br label %loop
  86
  87 loop:
  88   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
  89   %indvars.iv.next = add nuw i64 %indvars.iv, 1
  90   %cmp = icmp eq i64 %indvars.iv.next, 25
  91   br i1 %cmp, label %backedge, label %for.end
  92
  93 backedge:
  94   ; prevent flattening, needed to make sure we're testing what we intend
  95   call void @foo()
  96 ; CHECK: %cmp1 = icmp ugt i64 %start, 100
  97   %cmp1 = icmp ugt i64 %indvars.iv, 100
  98   br i1 %cmp1, label %loop, label %for.end
  99
 100 for.end:                                          ; preds = %if.end, %entry
 101   ret void
 102 }
 103
 104 define void @test6(i64 %start) {
 105 ; CHECK-LABEL: @test6
 106 entry:
 107   br label %loop
 108
 109 loop:
 110   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
 111   %indvars.iv.next = add nuw i64 %indvars.iv, 1
 112   %cmp = icmp eq i64 %indvars.iv.next, 25
 113   br i1 %cmp, label %backedge, label %for.end
 114
 115 backedge:
 116   ; prevent flattening, needed to make sure we're testing what we intend
 117   call void @foo()
 118 ; CHECK: %cmp1 = icmp ult i64 %start, 100
 119   %cmp1 = icmp ult i64 %indvars.iv, 100
 120   br i1 %cmp1, label %for.end, label %loop
 121
 122 for.end:                                          ; preds = %if.end, %entry
 123   ret void
 124 }
 125
 126 define void @test7(i64 %start, i64* %inc_ptr) {
 127 ; CHECK-LABEL: @test7
 128 entry:
 129   %inc = load i64, i64* %inc_ptr, !range !0
 130   %ok = icmp sge i64 %inc, 0
 131   br i1 %ok, label %loop, label %for.end
 132
 133 loop:
 134   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
 135   %indvars.iv.next = add nsw i64 %indvars.iv, %inc
 136 ; CHECK: %cmp1 = icmp slt i64 %start, -1
 137   %cmp1 = icmp slt i64 %indvars.iv, -1
 138   br i1 %cmp1, label %for.end, label %loop
 139
 140 for.end:                                          ; preds = %if.end, %entry
 141   ret void
 142 }
 143
 144 ; Negative test - we can't show that the internal branch executes, so we can't
 145 ; fold the test to a loop invariant one.
 146 define void @test1_neg(i64 %start) {
 147 ; CHECK-LABEL: @test1_neg
 148 entry:
 149   br label %loop
 150
 151 loop:
 152   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
 153   %indvars.iv.next = add nsw i64 %indvars.iv, 1
 154   %cmp = icmp eq i64 %indvars.iv.next, 25
 155   br i1 %cmp, label %backedge, label %skip
 156 skip:
 157   ; prevent flattening, needed to make sure we're testing what we intend
 158   call void @foo()
 159 ; CHECK: %cmp1 = icmp slt i64 %indvars.iv, -1
 160   %cmp1 = icmp slt i64 %indvars.iv, -1
 161   br i1 %cmp1, label %for.end, label %backedge
 162 backedge:
 163   ; prevent flattening, needed to make sure we're testing what we intend
 164   call void @foo()
 165   br label %loop
 166
 167 for.end:                                          ; preds = %if.end, %entry
 168   ret void
 169 }
 170
 171 ; Slightly subtle version of @test4 where the icmp dominates the backedge,
 172 ; but the exit branch doesn't.
 173 define void @test2_neg(i64 %start) {
 174 ; CHECK-LABEL: @test2_neg
 175 entry:
 176   br label %loop
 177
 178 loop:
 179   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
 180   %indvars.iv.next = add nsw i64 %indvars.iv, 1
 181   %cmp = icmp eq i64 %indvars.iv.next, 25
 182 ; CHECK: %cmp1 = icmp slt i64 %indvars.iv, -1
 183   %cmp1 = icmp slt i64 %indvars.iv, -1
 184   br i1 %cmp, label %backedge, label %skip
 185 skip:
 186   ; prevent flattening, needed to make sure we're testing what we intend
 187   call void @foo()
 188   br i1 %cmp1, label %for.end, label %backedge
 189 backedge:
 190   ; prevent flattening, needed to make sure we're testing what we intend
 191   call void @foo()
 192   br label %loop
 193
 194 for.end:                                          ; preds = %if.end, %entry
 195   ret void
 196 }
 197
 198 ; The branch has to exit the loop if the condition is true
 199 define void @test3_neg(i64 %start) {
 200 ; CHECK-LABEL: @test3_neg
 201 entry:
 202   br label %loop
 203
 204 loop:
 205   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
 206   %indvars.iv.next = add nsw i64 %indvars.iv, 1
 207 ; CHECK: %cmp1 = icmp slt i64 %indvars.iv, -1
 208   %cmp1 = icmp slt i64 %indvars.iv, -1
 209   br i1 %cmp1, label %loop, label %for.end
 210
 211 for.end:                                          ; preds = %if.end, %entry
 212   ret void
 213 }
 214
 215 define void @test4_neg(i64 %start) {
 216 ; CHECK-LABEL: @test4_neg
 217 entry:
 218   br label %loop
 219
 220 loop:
 221   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %backedge ]
 222   %indvars.iv.next = add nsw i64 %indvars.iv, 1
 223   %cmp = icmp eq i64 %indvars.iv.next, 25
 224   br i1 %cmp, label %backedge, label %for.end
 225
 226 backedge:
 227   ; prevent flattening, needed to make sure we're testing what we intend
 228   call void @foo()
 229 ; CHECK: %cmp1 = icmp sgt i64 %indvars.iv, -1
 230   %cmp1 = icmp sgt i64 %indvars.iv, -1
 231
 232 ; %cmp1 can be made loop invariant only if the branch below goes to
 233 ; %the header when %cmp1 is true.
 234   br i1 %cmp1, label %for.end, label %loop
 235
 236 for.end:                                          ; preds = %if.end, %entry
 237   ret void
 238 }
 239
 240 define void @test5_neg(i64 %start, i64 %inc) {
 241 ; CHECK-LABEL: @test5_neg
 242 entry:
 243   br label %loop
 244
 245 loop:
 246   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
 247   %indvars.iv.next = add nsw i64 %indvars.iv, %inc
 248 ; CHECK: %cmp1 = icmp slt i64 %indvars.iv, -1
 249   %cmp1 = icmp slt i64 %indvars.iv, -1
 250   br i1 %cmp1, label %for.end, label %loop
 251
 252 for.end:                                          ; preds = %if.end, %entry
 253   ret void
 254 }
 255
 256 define void @test8(i64 %start, i64* %inc_ptr) {
 257 ; CHECK-LABEL: @test8
 258 entry:
 259   %inc = load i64, i64* %inc_ptr, !range !1
 260   %ok = icmp sge i64 %inc, 0
 261   br i1 %ok, label %loop, label %for.end
 262
 263 loop:
 264   %indvars.iv = phi i64 [ %start, %entry ], [ %indvars.iv.next, %loop ]
 265   %indvars.iv.next = add nsw i64 %indvars.iv, %inc
 266 ; CHECK: %cmp1 = icmp slt i64 %indvars.iv, -1
 267   %cmp1 = icmp slt i64 %indvars.iv, -1
 268   br i1 %cmp1, label %for.end, label %loop
 269
 270 for.end:                                          ; preds = %if.end, %entry
 271   ret void
 272 }
 273
 274 ; check to handle loops without preheaders, but invariant operands
 275 ; (we handle this today by inserting a preheader)
 276 define void @test9(i1 %cnd, i64 %start) {
 277 ; CHECK-LABEL: @test9
 278 ; CHECK-LABEL: loop.preheader:
 279 entry:
 280   br i1 %cnd, label %entry1, label %entry2
 281 entry1:
 282   br label %loop
 283 entry2:
 284   br label %loop
 285 loop:
 286   %indvars.iv = phi i64 [ %start, %entry1 ],[ %start, %entry2 ], [ %indvars.iv.next, %loop ]
 287   %indvars.iv.next = add nsw i64 %indvars.iv, 1
 288 ; CHECK: %cmp1 = icmp slt i64 %start, -1
 289   %cmp1 = icmp slt i64 %indvars.iv, -1
 290   br i1 %cmp1, label %for.end, label %loop
 291
 292 for.end:                                          ; preds = %if.end, %entry
 293   ret void
 294 }
 295
 296 declare void @use(i1 %x)
 297
 298 ; check that we handle conditions with loop invariant operands which
 299 ; *aren't* in the header - this is a very rare and fragile case where
 300 ; we have a "loop" which is known to run exactly one iteration but
 301 ; haven't yet simplified the uses of the IV
 302 define void @test10() {
 303 ; CHECK-LABEL: @test10
 304 entry:
 305   br label %loop
 306
 307 loop:
 308   %phi1 = phi i32 [ %phi2, %latch ], [ 0, %entry ]
 309   %dec = add i32 %phi1, -1
 310   br i1 false, label %left, label %right
 311
 312 left:
 313   br label %latch
 314
 315 right:
 316   br label %latch
 317
 318 latch:
 319   %phi2 = phi i32 [ %phi1, %left ], [ %dec, %right ]
 320   ; CHECK: %cmp = icmp slt i32 -1, undef
 321   %cmp = icmp slt i32 %phi2, undef
 322   br i1 true, label %exit, label %loop
 323
 324 exit:
 325   call void @use(i1 %cmp)
 326   ret void
 327 }
 328
 329 ; check that we can figure out that iv.next > 1 from the facts that iv >= 0 and
 330 ; iv.start != 0.
 331 define void @test11(i64* %inc_ptr) {
 332 ; CHECK-LABEL: @test11
 333 entry:
 334   %inc = load i64, i64* %inc_ptr, !range !0
 335   %ne.cond = icmp ne i64 %inc, 0
 336   br i1 %ne.cond, label %loop, label %exit
 337
 338 loop:
 339   %iv = phi i64 [ %inc, %entry ], [ %iv.next, %backedge ]
 340   %iv.next = add i64 %iv, 1
 341   %brcond = icmp sgt i64 %iv.next, 1
 342   ; CHECK: br i1 true, label %if.true, label %if.false
 343   br i1 %brcond, label %if.true, label %if.false
 344
 345 if.true:
 346   br label %backedge
 347
 348 if.false:
 349   br label %backedge
 350
 351 backedge:
 352   %loopcond = icmp slt i64 %iv, 200
 353   br i1 %loopcond, label %loop, label %exit
 354
 355 exit:
 356   ret void
 357 }
 358
 359 ; check that we can prove that a recurrency is greater than another recurrency
 360 ; in the same loop, with the same step, and with smaller starting value.
 361 define void @test12(i64* %inc_ptr) {
 362 ; CHECK-LABEL: @test12
 363 entry:
 364   %inc = load i64, i64* %inc_ptr, !range !0
 365   %inc.minus.1 = sub i64 %inc, 1
 366   br label %loop
 367
 368 loop:
 369   %iv = phi i64 [ %inc, %entry ], [ %iv.next, %backedge ]
 370   %iv.minus.1 = phi i64 [ %inc.minus.1, %entry ], [ %iv.minus.1.next, %backedge ]
 371   %iv.next = add i64 %iv, 1
 372   %iv.minus.1.next = add i64 %iv.minus.1, 1
 373   %brcond = icmp sgt i64 %iv.next, %iv.minus.1.next
 374   ; CHECK: br i1 true, label %if.true, label %if.false
 375   br i1 %brcond, label %if.true, label %if.false
 376
 377 if.true:
 378   br label %backedge
 379
 380 if.false:
 381   br label %backedge
 382
 383 backedge:
 384   %loopcond = icmp slt i64 %iv, 200
 385   br i1 %loopcond, label %loop, label %exit
 386
 387 exit:
 388   ret void
 389 }
 390
 391 !0 = !{i64 0, i64 100}
 392 !1 = !{i64 -1, i64 100}
 393
 394 declare void @foo()