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 -passes=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, ptr %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, ptr %ptr, i64 %inner.iv
  28   %p = load %pair_t, ptr %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, ptr %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:%.*]], ptr [[PTR:%.*]], i64 [[INNER_IV]]
  58 ; CHECK-NEXT:    [[P:%.*]] = load [[PAIR_T]], ptr [[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, ptr %ptr, i64 %inner.iv
  84   %p = load %pair_t, ptr %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, ptr %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:%.*]], ptr [[PTR:%.*]], i64 [[INNER_IV]]
 113 ; CHECK-NEXT:    [[P:%.*]] = load [[PAIR_T]], ptr [[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, ptr %ptr, i64 %inner.iv
 139   %p = load %pair_t, ptr %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 label [[EXIT:%.*]]
 172 ; CHECK:       exit:
 173 ; CHECK-NEXT:    ret void
 174 ;
 175   br label %loop1
 176
 177 loop1:
 178   br i1 %c1, label %loop1.latch, label %loop2
 179
 180 loop2:
 181   br i1 %c2, label %loop1.latch, label %loop2
 182
 183 loop1.latch:
 184   br i1 false, label %loop1, label %exit
 185
 186 exit:
 187   ret void
 188 }
 189
 190 ; Similar to @inner_loop_may_be_infinite, but the function is marked as
 191 ; mustprogress. The loops can be removed.
 192 define void @inner_loop_may_be_infinite_but_fn_mustprogress(i1 %c1, i1 %c2) mustprogress {
 193 ; CHECK-LABEL: @inner_loop_may_be_infinite_but_fn_mustprogress(
 194 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 195 ; CHECK:       exit:
 196 ; CHECK-NEXT:    ret void
 197 ;
 198   br label %loop1
 199
 200 loop1:
 201   br i1 %c1, label %loop1.latch, label %loop2
 202
 203 loop2:
 204   br i1 %c2, label %loop1.latch, label %loop2
 205
 206 loop1.latch:
 207   br i1 false, label %loop1, label %exit
 208
 209 exit:
 210   ret void
 211 }
 212
 213 ; Similar to @inner_loop_may_be_infinite, but the parent loop loop1 is marked
 214 ; as mustprogress. The loops can be removed.
 215 define void @inner_loop_may_be_infinite_but_top_loop_mustprogress(i1 %c1, i1 %c2) {
 216 ; CHECK-LABEL: @inner_loop_may_be_infinite_but_top_loop_mustprogress(
 217 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 218 ; CHECK:       exit:
 219 ; CHECK-NEXT:    ret void
 220 ;
 221   br label %loop1
 222
 223 loop1:
 224   br i1 %c1, label %loop1.latch, label %loop2
 225
 226 loop2:
 227   br i1 %c2, label %loop1.latch, label %loop2
 228
 229 loop1.latch:
 230   br i1 false, label %loop1, label %exit, !llvm.loop !3
 231
 232 exit:
 233   ret void
 234 }
 235
 236 ; loop3 and loop1 are not marked as mustprogress, but loop2 (parent of loop3)
 237 ; is. The loops can be removed.
 238 define void @loop2_mustprogress_but_not_child_loop_loop3(i1 %c1, i1 %c2, i1 %c3) {
 239 ; CHECK-LABEL: @loop2_mustprogress_but_not_child_loop_loop3(
 240 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 241 ; CHECK:       exit:
 242 ; CHECK-NEXT:    ret void
 243 ;
 244   br label %loop1
 245
 246 loop1:
 247   br i1 %c1, label %loop1.latch, label %loop2
 248
 249 loop2:
 250   br label %loop3
 251
 252 loop3:
 253   br i1 %c2, label %loop2.latch, label %loop3
 254
 255 loop2.latch:
 256   br i1 %c3, label %loop1.latch, label %loop2, !llvm.loop !3
 257
 258 loop1.latch:
 259   br i1 false, label %loop1, label %exit
 260
 261 exit:
 262   ret void
 263 }
 264
 265 ; Cannot remove loop3 or loop1, as they are not mustprogress. loop2 is
 266 ; mustprogress and can be removed.
 267 define void @loop2_mustprogress_but_not_sibling_loop(i1 %c1, i1 %c2, i1 %c3) {
 268 ; CHECK-LABEL: @loop2_mustprogress_but_not_sibling_loop(
 269 ; CHECK-NEXT:    br label [[LOOP1:%.*]]
 270 ; CHECK:       loop1:
 271 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[LOOP1_LATCH:%.*]], label [[LOOP2_PREHEADER:%.*]]
 272 ; CHECK:       loop2.preheader:
 273 ; CHECK-NEXT:    br label [[LOOP3_PREHEADER:%.*]]
 274 ; CHECK:       loop3.preheader:
 275 ; CHECK-NEXT:    br label [[LOOP3:%.*]]
 276 ; CHECK:       loop3:
 277 ; CHECK-NEXT:    br i1 [[C3:%.*]], label [[LOOP1_LATCH_LOOPEXIT:%.*]], label [[LOOP3]]
 278 ; CHECK:       loop1.latch.loopexit:
 279 ; CHECK-NEXT:    br label [[LOOP1_LATCH]]
 280 ; CHECK:       loop1.latch:
 281 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 282 ; CHECK:       exit:
 283 ; CHECK-NEXT:    ret void
 284 ;
 285   br label %loop1
 286
 287 loop1:
 288   br i1 %c1, label %loop1.latch, label %loop2
 289
 290 loop2:
 291   br i1 %c2, label %loop3, label %loop2, !llvm.loop !4
 292
 293 loop3:
 294   br i1 %c3, label %loop1.latch, label %loop3
 295
 296 loop1.latch:
 297   br i1 false, label %loop1, label %exit
 298
 299 exit:
 300   ret void
 301 }
 302
 303 define void @loop2_finite_but_child_is_not(i1 %c1, i1 %c2, i1 %c3) {
 304 ; CHECK-LABEL: @loop2_finite_but_child_is_not(
 305 ; CHECK-NEXT:  entry:
 306 ; CHECK-NEXT:    br label [[LOOP1:%.*]]
 307 ; CHECK:       loop1:
 308 ; CHECK-NEXT:    [[IV1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV1_NEXT:%.*]], [[LOOP1_LATCH:%.*]] ]
 309 ; CHECK-NEXT:    br i1 [[C1:%.*]], label [[LOOP1_LATCH]], label [[LOOP2_PREHEADER:%.*]]
 310 ; CHECK:       loop2.preheader:
 311 ; CHECK-NEXT:    br label [[LOOP2:%.*]]
 312 ; CHECK:       loop2:
 313 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT:%.*]], [[LOOP2_LATCH:%.*]] ], [ 0, [[LOOP2_PREHEADER]] ]
 314 ; CHECK-NEXT:    br label [[LOOP3:%.*]]
 315 ; CHECK:       loop3:
 316 ; CHECK-NEXT:    br i1 [[C2:%.*]], label [[LOOP2_LATCH]], label [[LOOP3]]
 317 ; CHECK:       loop2.latch:
 318 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw i32 [[IV]], 1
 319 ; CHECK-NEXT:    [[C:%.*]] = icmp ugt i32 [[IV]], 200
 320 ; CHECK-NEXT:    br i1 [[C]], label [[LOOP1_LATCH_LOOPEXIT:%.*]], label [[LOOP2]]
 321 ; CHECK:       loop1.latch.loopexit:
 322 ; CHECK-NEXT:    br label [[LOOP1_LATCH]]
 323 ; CHECK:       loop1.latch:
 324 ; CHECK-NEXT:    [[IV1_NEXT]] = add nuw i32 [[IV1]], 1
 325 ; CHECK-NEXT:    [[C4:%.*]] = icmp ult i32 [[IV1_NEXT]], 200
 326 ; CHECK-NEXT:    br i1 [[C4]], label [[LOOP1]], label [[EXIT:%.*]]
 327 ; CHECK:       exit:
 328 ; CHECK-NEXT:    ret void
 329 ;
 330 entry:
 331   br label %loop1
 332
 333 loop1:
 334   %iv1 = phi i32 [ 0, %entry ], [ %iv1.next, %loop1.latch ]
 335   br i1 %c1, label %loop1.latch, label %loop2
 336
 337 loop2:
 338   %iv = phi i32 [ 0, %loop1 ], [ %iv.next, %loop2.latch ]
 339   br label %loop3
 340
 341 loop3:
 342   br i1 %c2, label %loop2.latch, label %loop3
 343
 344 loop2.latch:
 345   %iv.next = add nuw i32 %iv, 1
 346   %c = icmp ugt i32 %iv, 200
 347   br i1 %c, label %loop1.latch, label %loop2
 348
 349 loop1.latch:
 350   %iv1.next = add nuw i32 %iv1, 1
 351   %c4 = icmp ult i32 %iv1.next, 200
 352   br i1 %c4, label %loop1, label %exit
 353
 354 exit:
 355   ret void
 356 }
 357
 358 define void @loop2_finite_and_child_is_mustprogress(i1 %c1, i1 %c2, i1 %c3) {
 359 ; CHECK-LABEL: @loop2_finite_and_child_is_mustprogress(
 360 ; CHECK-NEXT:  entry:
 361 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 362 ; CHECK:       exit:
 363 ; CHECK-NEXT:    ret void
 364 ;
 365 entry:
 366   br label %loop1
 367
 368 loop1:
 369   %iv1 = phi i32 [ 0, %entry ], [ %iv1.next, %loop1.latch ]
 370   br i1 %c1, label %loop1.latch, label %loop2
 371
 372 loop2:
 373   %iv = phi i32 [ 0, %loop1 ], [ %iv.next, %loop2.latch ]
 374   br label %loop3
 375
 376 loop3:
 377   br i1 %c2, label %loop2.latch, label %loop3, !llvm.loop !5
 378
 379 loop2.latch:
 380   %iv.next = add nuw i32 %iv, 1
 381   %c = icmp ugt i32 %iv, 200
 382   br i1 %c, label %loop1.latch, label %loop2
 383
 384 loop1.latch:
 385   %iv1.next = add nuw i32 %iv1, 1
 386   %c4 = icmp ult i32 %iv1.next, 200
 387   br i1 %c4, label %loop1, label %exit
 388
 389 exit:
 390   ret void
 391 }
 392
 393 ; Inner infinite loop hidden behind a call.
 394 define void @not_willreturn() {
 395 ; CHECK-LABEL: @not_willreturn(
 396 ; CHECK-NEXT:  entry:
 397 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 398 ; CHECK:       loop:
 399 ; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
 400 ; CHECK-NEXT:    call void @sideeffect() #[[ATTR2:[0-9]+]]
 401 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw i32 [[IV]], 1
 402 ; CHECK-NEXT:    [[C:%.*]] = icmp ult i32 [[IV]], 100
 403 ; CHECK-NEXT:    br i1 [[C]], label [[LOOP]], label [[EXIT:%.*]]
 404 ; CHECK:       exit:
 405 ; CHECK-NEXT:    ret void
 406 ;
 407 entry:
 408   br label %loop
 409
 410 loop:
 411   %iv = phi i32 [ 0, %entry ], [ %iv.next, %loop ]
 412   call void @sideeffect() nounwind readonly
 413   %iv.next = add nuw i32 %iv, 1
 414   %c = icmp ult i32 %iv, 100
 415   br i1 %c, label %loop, label %exit
 416
 417 exit:
 418   ret void
 419 }
 420
 421 !1 = !{!"llvm.loop.mustprogress"}
 422 !2 = distinct !{!2, !1}
 423 !3 = distinct !{!3, !1}
 424 !4 = distinct !{!4, !1}
 425 !5 = distinct !{!5, !1}