llvm/test/Transforms/LoopDeletion/noop-loops-with-subloops.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -loop-deletion -verify-dom-info -S | FileCheck %s
   3
   4 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64"
   5
   6 %pair_t = type { i64, i64 }
   7
   8 ; The loop %inner cannot be removed, because it has outgoing values. But the
   9 ; outer loop is a no-op and can be removed.
  10 define void @test1(i64 %N, i64 %M, %pair_t* %ptr) willreturn {
  11 ; CHECK-LABEL: @test1(
  12 ; CHECK-NEXT:  entry:
  13 ; CHECK-NEXT:    br label [[EXIT:%.*]]
  14 ; CHECK:       exit:
  15 ; CHECK-NEXT:    ret void
  16 ;
  17 entry:
  18   br label %outer.header
  19
  20 outer.header:
  21   %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
  22
  23   br label %inner
  24
  25 inner:
  26   %inner.iv = phi i64 [ 0, %outer.header ], [ %inner.iv.next, %inner ]
  27   %gep = getelementptr %pair_t, %pair_t* %ptr, i64 %inner.iv
  28   %p = load %pair_t, %pair_t* %gep
  29   %v.0 = extractvalue %pair_t %p, 0
  30   %v.1 = extractvalue %pair_t %p, 1
  31   %inner.ec = icmp ult i64 %v.0, %v.1
  32   %inner.iv.next = add i64 %inner.iv, 1
  33   br i1 %inner.ec, label %outer.latch, label %inner
  34
  35 outer.latch:
  36   %lcssa = phi i64 [ %v.1, %inner ]
  37   %outer.ec = icmp ult i64 %outer.iv, %lcssa
  38   %outer.iv.next = add i64 %outer.iv, 1
  39   br i1 %outer.ec, label %exit, label %outer.header
  40
  41 exit:
  42   ret void
  43 }
  44
  45 declare void @sideeffect()
  46
  47 ; Same as @test1, but with a call in the outer loop. Nothing can be deleted.
  48 define void @test2_sideeffect_in_outer(i64 %N, i64 %M, %pair_t* %ptr) willreturn {
  49 ; CHECK-LABEL: @test2_sideeffect_in_outer(
  50 ; CHECK-NEXT:  entry:
  51 ; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
  52 ; CHECK:       outer.header:
  53 ; CHECK-NEXT:    [[OUTER_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_IV_NEXT:%.*]], [[OUTER_LATCH:%.*]] ]
  54 ; CHECK-NEXT:    br label [[INNER:%.*]]
  55 ; CHECK:       inner:
  56 ; CHECK-NEXT:    [[INNER_IV:%.*]] = phi i64 [ 0, [[OUTER_HEADER]] ], [ [[INNER_IV_NEXT:%.*]], [[INNER]] ]
  57 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr [[PAIR_T:%.*]], %pair_t* [[PTR:%.*]], i64 [[INNER_IV]]
  58 ; CHECK-NEXT:    [[P:%.*]] = load [[PAIR_T]], %pair_t* [[GEP]], align 4
  59 ; CHECK-NEXT:    [[V_0:%.*]] = extractvalue [[PAIR_T]] [[P]], 0
  60 ; CHECK-NEXT:    [[V_1:%.*]] = extractvalue [[PAIR_T]] [[P]], 1
  61 ; CHECK-NEXT:    [[INNER_EC:%.*]] = icmp ult i64 [[V_0]], [[V_1]]
  62 ; CHECK-NEXT:    [[INNER_IV_NEXT]] = add i64 [[INNER_IV]], 1
  63 ; CHECK-NEXT:    br i1 [[INNER_EC]], label [[OUTER_LATCH]], label [[INNER]]
  64 ; CHECK:       outer.latch:
  65 ; CHECK-NEXT:    [[LCSSA:%.*]] = phi i64 [ [[V_1]], [[INNER]] ]
  66 ; CHECK-NEXT:    [[OUTER_EC:%.*]] = icmp ult i64 [[OUTER_IV]], [[LCSSA]]
  67 ; CHECK-NEXT:    [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1
  68 ; CHECK-NEXT:    call void @sideeffect()
  69 ; CHECK-NEXT:    br i1 [[OUTER_EC]], label [[EXIT:%.*]], label [[OUTER_HEADER]]
  70 ; CHECK:       exit:
  71 ; CHECK-NEXT:    ret void
  72 ;
  73 entry:
  74   br label %outer.header
  75
  76 outer.header:
  77   %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
  78
  79   br label %inner
  80
  81 inner:
  82   %inner.iv = phi i64 [ 0, %outer.header ], [ %inner.iv.next, %inner ]
  83   %gep = getelementptr %pair_t, %pair_t* %ptr, i64 %inner.iv
  84   %p = load %pair_t, %pair_t* %gep
  85   %v.0 = extractvalue %pair_t %p, 0
  86   %v.1 = extractvalue %pair_t %p, 1
  87   %inner.ec = icmp ult i64 %v.0, %v.1
  88   %inner.iv.next = add i64 %inner.iv, 1
  89   br i1 %inner.ec, label %outer.latch, label %inner
  90
  91 outer.latch:
  92   %lcssa = phi i64 [ %v.1, %inner ]
  93   %outer.ec = icmp ult i64 %outer.iv, %lcssa
  94   %outer.iv.next = add i64 %outer.iv, 1
  95   call void @sideeffect()
  96   br i1 %outer.ec, label %exit, label %outer.header
  97
  98 exit:
  99   ret void
 100 }
 101
 102 ; Same as @test1, but with a call in the inner loop. Nothing can be deleted.
 103 define void @test3_sideeffect_in_inner(i64 %N, i64 %M, %pair_t* %ptr) willreturn {
 104 ; CHECK-LABEL: @test3_sideeffect_in_inner(
 105 ; CHECK-NEXT:  entry:
 106 ; CHECK-NEXT:    br label [[OUTER_HEADER:%.*]]
 107 ; CHECK:       outer.header:
 108 ; CHECK-NEXT:    [[OUTER_IV:%.*]] = phi i64 [ 0, [[ENTRY:%.*]] ], [ [[OUTER_IV_NEXT:%.*]], [[OUTER_LATCH:%.*]] ]
 109 ; CHECK-NEXT:    br label [[INNER:%.*]]
 110 ; CHECK:       inner:
 111 ; CHECK-NEXT:    [[INNER_IV:%.*]] = phi i64 [ 0, [[OUTER_HEADER]] ], [ [[INNER_IV_NEXT:%.*]], [[INNER]] ]
 112 ; CHECK-NEXT:    [[GEP:%.*]] = getelementptr [[PAIR_T:%.*]], %pair_t* [[PTR:%.*]], i64 [[INNER_IV]]
 113 ; CHECK-NEXT:    [[P:%.*]] = load [[PAIR_T]], %pair_t* [[GEP]], align 4
 114 ; CHECK-NEXT:    [[V_0:%.*]] = extractvalue [[PAIR_T]] [[P]], 0
 115 ; CHECK-NEXT:    [[V_1:%.*]] = extractvalue [[PAIR_T]] [[P]], 1
 116 ; CHECK-NEXT:    [[INNER_EC:%.*]] = icmp ult i64 [[V_0]], [[V_1]]
 117 ; CHECK-NEXT:    [[INNER_IV_NEXT]] = add i64 [[INNER_IV]], 1
 118 ; CHECK-NEXT:    call void @sideeffect()
 119 ; CHECK-NEXT:    br i1 [[INNER_EC]], label [[OUTER_LATCH]], label [[INNER]]
 120 ; CHECK:       outer.latch:
 121 ; CHECK-NEXT:    [[LCSSA:%.*]] = phi i64 [ [[V_1]], [[INNER]] ]
 122 ; CHECK-NEXT:    [[OUTER_EC:%.*]] = icmp ult i64 [[OUTER_IV]], [[LCSSA]]
 123 ; CHECK-NEXT:    [[OUTER_IV_NEXT]] = add i64 [[OUTER_IV]], 1
 124 ; CHECK-NEXT:    br i1 [[OUTER_EC]], label [[EXIT:%.*]], label [[OUTER_HEADER]]
 125 ; CHECK:       exit:
 126 ; CHECK-NEXT:    ret void
 127 ;
 128 entry:
 129   br label %outer.header
 130
 131 outer.header:
 132   %outer.iv = phi i64 [ 0, %entry ], [ %outer.iv.next, %outer.latch ]
 133
 134   br label %inner
 135
 136 inner:
 137   %inner.iv = phi i64 [ 0, %outer.header ], [ %inner.iv.next, %inner ]
 138   %gep = getelementptr %pair_t, %pair_t* %ptr, i64 %inner.iv
 139   %p = load %pair_t, %pair_t* %gep
 140   %v.0 = extractvalue %pair_t %p, 0
 141   %v.1 = extractvalue %pair_t %p, 1
 142   %inner.ec = icmp ult i64 %v.0, %v.1
 143   %inner.iv.next = add i64 %inner.iv, 1
 144   call void @sideeffect()
 145   br i1 %inner.ec, label %outer.latch, label %inner
 146
 147 outer.latch:
 148   %lcssa = phi i64 [ %v.1, %inner ]
 149   %outer.ec = icmp ult i64 %outer.iv, %lcssa
 150   %outer.iv.next = add i64 %outer.iv, 1
 151   br i1 %outer.ec, label %exit, label %outer.header
 152
 153 exit:
 154   ret void
 155 }
 156
 157 ; The inner loop may not terminate, so we cannot remove it, unless the
 158 ; function/loop is mustprogress. Test case from PR50511.
 159 define void @inner_loop_may_be_infinite(i1 %c1, i1 %c2) {
 160 ; CHECK-LABEL: @inner_loop_may_be_infinite(
 161 ; CHECK-NEXT:    br label [[LOOP1:%.*]]
 162 ; CHECK:       loop1:
 163 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[LOOP1_LATCH:%.*]], label [[LOOP2_PREHEADER:%.*]]
 164 ; CHECK:       loop2.preheader:
 165 ; CHECK-NEXT:    br label [[LOOP2:%.*]]
 166 ; CHECK:       loop2:
 167 ; CHECK-NEXT:    br i1 [[C2:%.*]], label [[LOOP1_LATCH_LOOPEXIT:%.*]], label [[LOOP2]]
 168 ; CHECK:       loop1.latch.loopexit:
 169 ; CHECK-NEXT:    br label [[LOOP1_LATCH]]
 170 ; CHECK:       loop1.latch:
 171 ; CHECK-NEXT:    br i1 false, label [[LOOP1_LATCH_LOOP1_CRIT_EDGE:%.*]], label [[EXIT:%.*]]
 172 ; CHECK:       loop1.latch.loop1_crit_edge:
 173 ; CHECK-NEXT:    unreachable
 174 ; CHECK:       exit:
 175 ; CHECK-NEXT:    ret void
 176 ;
 177   br label %loop1
 178
 179 loop1:
 180   br i1 %c1, label %loop1.latch, label %loop2
 181
 182 loop2:
 183   br i1 %c2, label %loop1.latch, label %loop2
 184
 185 loop1.latch:
 186   br i1 false, label %loop1, label %exit
 187
 188 exit:
 189   ret void
 190 }
 191
 192 ; Similar to @inner_loop_may_be_infinite, but the function is marked as
 193 ; mustprogress. The loops can be removed.
 194 define void @inner_loop_may_be_infinite_but_fn_mustprogress(i1 %c1, i1 %c2) mustprogress {
 195 ; CHECK-LABEL: @inner_loop_may_be_infinite_but_fn_mustprogress(
 196 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 197 ; CHECK:       exit:
 198 ; CHECK-NEXT:    ret void
 199 ;
 200   br label %loop1
 201
 202 loop1:
 203   br i1 %c1, label %loop1.latch, label %loop2
 204
 205 loop2:
 206   br i1 %c2, label %loop1.latch, label %loop2
 207
 208 loop1.latch:
 209   br i1 false, label %loop1, label %exit
 210
 211 exit:
 212   ret void
 213 }
 214
 215 ; Similar to @inner_loop_may_be_infinite, but the parent loop loop1 is marked
 216 ; as mustprogress. The loops can be removed.
 217 define void @inner_loop_may_be_infinite_but_top_loop_mustprogress(i1 %c1, i1 %c2) {
 218 ; CHECK-LABEL: @inner_loop_may_be_infinite_but_top_loop_mustprogress(
 219 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 220 ; CHECK:       exit:
 221 ; CHECK-NEXT:    ret void
 222 ;
 223   br label %loop1
 224
 225 loop1:
 226   br i1 %c1, label %loop1.latch, label %loop2
 227
 228 loop2:
 229   br i1 %c2, label %loop1.latch, label %loop2
 230
 231 loop1.latch:
 232   br i1 false, label %loop1, label %exit, !llvm.loop !3
 233
 234 exit:
 235   ret void
 236 }
 237
 238 ; loop3 and loop1 are not marked as mustprogress, but loop2 (parent of loop3)
 239 ; is. The loops can be removed.
 240 define void @loop2_mustprogress_but_not_child_loop_loop3(i1 %c1, i1 %c2, i1 %c3) {
 241 ; CHECK-LABEL: @loop2_mustprogress_but_not_child_loop_loop3(
 242 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 243 ; CHECK:       exit:
 244 ; CHECK-NEXT:    ret void
 245 ;
 246   br label %loop1
 247
 248 loop1:
 249   br i1 %c1, label %loop1.latch, label %loop2
 250
 251 loop2:
 252   br label %loop3
 253
 254 loop3:
 255   br i1 %c2, label %loop2.latch, label %loop3
 256
 257 loop2.latch:
 258   br i1 %c3, label %loop1.latch, label %loop2, !llvm.loop !3
 259
 260 loop1.latch:
 261   br i1 false, label %loop1, label %exit
 262
 263 exit:
 264   ret void
 265 }
 266
 267 ; Cannot remove loop3 or loop1, as they are not mustprogress. loop2 is
 268 ; mustprogress and can be removed.
 269 define void @loop2_mustprogress_but_not_sibling_loop(i1 %c1, i1 %c2, i1 %c3) {
 270 ; CHECK-LABEL: @loop2_mustprogress_but_not_sibling_loop(
 271 ; CHECK-NEXT:    br label [[LOOP1:%.*]]
 272 ; CHECK:       loop1:
 273 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[LOOP1_LATCH:%.*]], label [[LOOP2_PREHEADER:%.*]]
 274 ; CHECK:       loop2.preheader:
 275 ; CHECK-NEXT:    br label [[LOOP3_PREHEADER:%.*]]
 276 ; CHECK:       loop3.preheader:
 277 ; CHECK-NEXT:    br label [[LOOP3:%.*]]
 278 ; CHECK:       loop3:
 279 ; CHECK-NEXT:    br i1 [[C3:%.*]], label [[LOOP1_LATCH_LOOPEXIT:%.*]], label [[LOOP3]]
 280 ; CHECK:       loop1.latch.loopexit:
 281 ; CHECK-NEXT:    br label [[LOOP1_LATCH]]
 282 ; CHECK:       loop1.latch:
 283 ; CHECK-NEXT:    br i1 false, label [[LOOP1_LATCH_LOOP1_CRIT_EDGE:%.*]], label [[EXIT:%.*]]
 284 ; CHECK:       loop1.latch.loop1_crit_edge:
 285 ; CHECK-NEXT:    unreachable
 286 ; CHECK:       exit:
 287 ; CHECK-NEXT:    ret void
 288 ;
 289   br label %loop1
 290
 291 loop1:
 292   br i1 %c1, label %loop1.latch, label %loop2
 293
 294 loop2:
 295   br i1 %c2, label %loop3, label %loop2, !llvm.loop !4
 296
 297 loop3:
 298   br i1 %c3, label %loop1.latch, label %loop3
 299
 300 loop1.latch:
 301   br i1 false, label %loop1, label %exit
 302
 303 exit:
 304   ret void
 305 }
 306
 307 define void @loop2_finite_but_child_is_not(i1 %c1, i1 %c2, i1 %c3) {
 308 ; CHECK-LABEL: @loop2_finite_but_child_is_not(
 309 ; CHECK-NEXT:  entry:
 310 ; CHECK-NEXT:    br label [[LOOP1:%.*]]
 311 ; CHECK:       loop1:
 312 ; CHECK-NEXT:    [[IV1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV1_NEXT:%.*]], [[LOOP1_LATCH:%.*]] ]
 313 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[LOOP1_LATCH]], label [[LOOP2_PREHEADER:%.*]]
 314 ; CHECK:       loop2.preheader:
 315 ; CHECK-NEXT:    br label [[LOOP2:%.*]]
 316 ; CHECK:       loop2:
 317 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[LOOP2_LATCH:%.*]] ], [ 0, [[LOOP2_PREHEADER]] ]
 318 ; CHECK-NEXT:    br label [[LOOP3:%.*]]
 319 ; CHECK:       loop3:
 320 ; CHECK-NEXT:    br i1 [[C2:%.*]], label [[LOOP2_LATCH]], label [[LOOP3]]
 321 ; CHECK:       loop2.latch:
 322 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw i32 [[IV]], 1
 323 ; CHECK-NEXT:    [[C:%.*]] = icmp ugt i32 [[IV]], 200
 324 ; CHECK-NEXT:    br i1 [[C]], label [[LOOP1_LATCH_LOOPEXIT:%.*]], label [[LOOP2]]
 325 ; CHECK:       loop1.latch.loopexit:
 326 ; CHECK-NEXT:    br label [[LOOP1_LATCH]]
 327 ; CHECK:       loop1.latch:
 328 ; CHECK-NEXT:    [[IV1_NEXT]] = add nuw i32 [[IV1]], 1
 329 ; CHECK-NEXT:    [[C4:%.*]] = icmp ult i32 [[IV1_NEXT]], 200
 330 ; CHECK-NEXT:    br i1 [[C4]], label [[LOOP1]], label [[EXIT:%.*]]
 331 ; CHECK:       exit:
 332 ; CHECK-NEXT:    ret void
 333 ;
 334 entry:
 335   br label %loop1
 336
 337 loop1:
 338   %iv1 = phi i32 [ 0, %entry ], [ %iv1.next, %loop1.latch ]
 339   br i1 %c1, label %loop1.latch, label %loop2
 340
 341 loop2:
 342   %iv = phi i32 [ 0, %loop1 ], [ %iv.next, %loop2.latch ]
 343   br label %loop3
 344
 345 loop3:
 346   br i1 %c2, label %loop2.latch, label %loop3
 347
 348 loop2.latch:
 349   %iv.next = add nuw i32 %iv, 1
 350   %c = icmp ugt i32 %iv, 200
 351   br i1 %c, label %loop1.latch, label %loop2
 352
 353 loop1.latch:
 354   %iv1.next = add nuw i32 %iv1, 1
 355   %c4 = icmp ult i32 %iv1.next, 200
 356   br i1 %c4, label %loop1, label %exit
 357
 358 exit:
 359   ret void
 360 }
 361
 362 define void @loop2_finite_and_child_is_mustprogress(i1 %c1, i1 %c2, i1 %c3) {
 363 ; CHECK-LABEL: @loop2_finite_and_child_is_mustprogress(
 364 ; CHECK-NEXT:  entry:
 365 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 366 ; CHECK:       exit:
 367 ; CHECK-NEXT:    ret void
 368 ;
 369 entry:
 370   br label %loop1
 371
 372 loop1:
 373   %iv1 = phi i32 [ 0, %entry ], [ %iv1.next, %loop1.latch ]
 374   br i1 %c1, label %loop1.latch, label %loop2
 375
 376 loop2:
 377   %iv = phi i32 [ 0, %loop1 ], [ %iv.next, %loop2.latch ]
 378   br label %loop3
 379
 380 loop3:
 381   br i1 %c2, label %loop2.latch, label %loop3, !llvm.loop !5
 382
 383 loop2.latch:
 384   %iv.next = add nuw i32 %iv, 1
 385   %c = icmp ugt i32 %iv, 200
 386   br i1 %c, label %loop1.latch, label %loop2
 387
 388 loop1.latch:
 389   %iv1.next = add nuw i32 %iv1, 1
 390   %c4 = icmp ult i32 %iv1.next, 200
 391   br i1 %c4, label %loop1, label %exit
 392
 393 exit:
 394   ret void
 395 }
 396
 397 ; Inner infinite loop hidden behind a call.
 398 define void @not_willreturn() {
 399 ; CHECK-LABEL: @not_willreturn(
 400 ; CHECK-NEXT:  entry:
 401 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 402 ; CHECK:       loop:
 403 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 404 ; CHECK-NEXT:    call void @sideeffect() #[[ATTR2:[0-9]+]]
 405 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw i32 [[IV]], 1
 406 ; CHECK-NEXT:    [[C:%.*]] = icmp ult i32 [[IV]], 100
 407 ; CHECK-NEXT:    br i1 [[C]], label [[LOOP]], label [[EXIT:%.*]]
 408 ; CHECK:       exit:
 409 ; CHECK-NEXT:    ret void
 410 ;
 411 entry:
 412   br label %loop
 413
 414 loop:
 415   %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
 416   call void @sideeffect() nounwind readonly
 417   %iv.next = add nuw i32 %iv, 1
 418   %c = icmp ult i32 %iv, 100
 419   br i1 %c, label %loop, label %exit
 420
 421 exit:
 422   ret void
 423 }
 424
 425 !1 = !{!"llvm.loop.mustprogress"}
 426 !2 = distinct !{!2, !1}
 427 !3 = distinct !{!3, !1}
 428 !4 = distinct !{!4, !1}
 429 !5 = distinct !{!5, !1}