1 ; RUN: opt < %s -S -loop-unroll -verify-loop-info | FileCheck %s 2 ; 3 ; Unit tests for LoopInfo::updateUnloop. 4 5 declare i1 @check() nounwind 6 7 ; Ensure that tail->inner is removed and rely on verify-loopinfo to 8 ; check soundness. 9 ; 10 ; CHECK-LABEL: @skiplevelexit( 11 ; CHECK: tail: 12 ; CHECK-NOT: br 13 ; CHECK: ret void 14 define void @skiplevelexit() nounwind { 15 entry: 16 br label %outer 17 18 outer: 19 br label %inner 20 21 inner: 22 %iv = phi i32 [ 0, %outer ], [ %inc, %tail ] 23 %inc = add i32 %iv, 1 24 call zeroext i1 @check() 25 br i1 true, label %outer.backedge, label %tail 26 27 tail: 28 br i1 false, label %inner, label %exit 29 30 outer.backedge: 31 br label %outer 32 33 exit: 34 ret void 35 } 36 37 ; Remove the middle loop of a triply nested loop tree. 38 ; Ensure that only the middle loop is removed and rely on verify-loopinfo to 39 ; check soundness. 40 ; 41 ; CHECK-LABEL: @unloopNested( 42 ; Outer loop control. 43 ; CHECK: while.body: 44 ; CHECK: br i1 %cmp3, label %if.then, label %if.end 45 ; Inner loop control. 46 ; CHECK: while.end14.i: 47 ; CHECK: br i1 %call15.i, label %if.end.i, label %exit 48 ; Middle loop control should no longer reach %while.cond. 49 ; Now it is the outer loop backedge. 50 ; CHECK: exit: 51 ; CHECK: br label %while.cond.outer 52 define void @unloopNested() { 53 entry: 54 br label %while.cond.outer 55 56 while.cond.outer: 57 br label %while.cond 58 59 while.cond: 60 %cmp = call zeroext i1 @check() 61 br i1 %cmp, label %while.body, label %while.end 62 63 while.body: 64 %cmp3 = call zeroext i1 @check() 65 br i1 %cmp3, label %if.then, label %if.end 66 67 if.then: 68 br label %return 69 70 if.end: 71 %cmp.i48 = call zeroext i1 @check() 72 br i1 %cmp.i48, label %if.then.i, label %if.else20.i 73 74 if.then.i: 75 %cmp8.i = call zeroext i1 @check() 76 br i1 %cmp8.i, label %merge, label %if.else.i 77 78 if.else.i: 79 br label %merge 80 81 if.else20.i: 82 %cmp25.i = call zeroext i1 @check() 83 br i1 %cmp25.i, label %merge, label %if.else28.i 84 85 if.else28.i: 86 br label %merge 87 88 merge: 89 br label %while.cond2.i 90 91 while.cond2.i: 92 %cmp.i = call zeroext i1 @check() 93 br i1 %cmp.i, label %while.cond2.backedge.i, label %while.end.i 94 95 while.cond2.backedge.i: 96 br label %while.cond2.i 97 98 while.end.i: 99 %cmp1114.i = call zeroext i1 @check() 100 br i1 %cmp1114.i, label %while.body12.lr.ph.i, label %while.end14.i 101 102 while.body12.lr.ph.i: 103 br label %while.end14.i 104 105 while.end14.i: 106 %call15.i = call zeroext i1 @check() 107 br i1 %call15.i, label %if.end.i, label %exit 108 109 if.end.i: 110 br label %while.cond2.backedge.i 111 112 exit: 113 br i1 false, label %while.cond, label %if.else 114 115 if.else: 116 br label %while.cond.outer 117 118 while.end: 119 br label %return 120 121 return: 122 ret void 123 } 124 125 ; Remove the middle loop of a deeply nested loop tree. 126 ; Ensure that only the middle loop is removed and rely on verify-loopinfo to 127 ; check soundness. 128 ; 129 ; This test must be disabled until trip count computation can be optimized... 130 ; rdar:14038809 [SCEV]: Optimize trip count computation for multi-exit loops. 131 ; CHECKFIXME-LABEL: @unloopDeepNested( 132 ; Inner-inner loop control. 133 ; CHECKFIXME: while.cond.us.i: 134 ; CHECKFIXME: br i1 %cmp.us.i, label %next_data.exit, label %while.body.us.i 135 ; CHECKFIXME: if.then.us.i: 136 ; CHECKFIXME: br label %while.cond.us.i 137 ; Inner loop tail. 138 ; CHECKFIXME: if.else.i: 139 ; CHECKFIXME: br label %while.cond.outer.i 140 ; Middle loop control (removed). 141 ; CHECKFIXME: valid_data.exit: 142 ; CHECKFIXME-NOT: br 143 ; CHECKFIXME: %cmp = call zeroext i1 @check() 144 ; Outer loop control. 145 ; CHECKFIXME: copy_data.exit: 146 ; CHECKFIXME: br i1 %cmp38, label %if.then39, label %while.cond.outer 147 ; Outer-outer loop tail. 148 ; CHECKFIXME: while.cond.outer.outer.backedge: 149 ; CHECKFIXME: br label %while.cond.outer.outer 150 define void @unloopDeepNested() nounwind { 151 for.cond8.preheader.i: 152 %cmp113.i = call zeroext i1 @check() 153 br i1 %cmp113.i, label %make_data.exit, label %for.body13.lr.ph.i 154 155 for.body13.lr.ph.i: 156 br label %make_data.exit 157 158 make_data.exit: 159 br label %while.cond.outer.outer 160 161 while.cond.outer.outer: 162 br label %while.cond.outer 163 164 while.cond.outer: 165 br label %while.cond 166 167 while.cond: 168 br label %while.cond.outer.i 169 170 while.cond.outer.i: 171 %tmp192.ph.i = call zeroext i1 @check() 172 br i1 %tmp192.ph.i, label %while.cond.outer.split.us.i, label %while.body.loopexit 173 174 while.cond.outer.split.us.i: 175 br label %while.cond.us.i 176 177 while.cond.us.i: 178 %cmp.us.i = call zeroext i1 @check() 179 br i1 %cmp.us.i, label %next_data.exit, label %while.body.us.i 180 181 while.body.us.i: 182 %cmp7.us.i = call zeroext i1 @check() 183 br i1 %cmp7.us.i, label %if.then.us.i, label %if.else.i 184 185 if.then.us.i: 186 br label %while.cond.us.i 187 188 if.else.i: 189 br label %while.cond.outer.i 190 191 next_data.exit: 192 %tmp192.ph.i.lcssa28 = call zeroext i1 @check() 193 br i1 %tmp192.ph.i.lcssa28, label %while.end, label %while.body 194 195 while.body.loopexit: 196 br label %while.body 197 198 while.body: 199 br label %while.cond.i 200 201 while.cond.i: 202 %cmp.i = call zeroext i1 @check() 203 br i1 %cmp.i, label %valid_data.exit, label %while.body.i 204 205 while.body.i: 206 %cmp7.i = call zeroext i1 @check() 207 br i1 %cmp7.i, label %valid_data.exit, label %if.end.i 208 209 if.end.i: 210 br label %while.cond.i 211 212 valid_data.exit: 213 br i1 true, label %if.then, label %while.cond 214 215 if.then: 216 %cmp = call zeroext i1 @check() 217 br i1 %cmp, label %if.then12, label %if.end 218 219 if.then12: 220 br label %if.end 221 222 if.end: 223 %tobool3.i = call zeroext i1 @check() 224 br i1 %tobool3.i, label %copy_data.exit, label %while.body.lr.ph.i 225 226 while.body.lr.ph.i: 227 br label %copy_data.exit 228 229 copy_data.exit: 230 %cmp38 = call zeroext i1 @check() 231 br i1 %cmp38, label %if.then39, label %while.cond.outer 232 233 if.then39: 234 %cmp5.i = call zeroext i1 @check() 235 br i1 %cmp5.i, label %while.cond.outer.outer.backedge, label %for.cond8.preheader.i8.thread 236 237 for.cond8.preheader.i8.thread: 238 br label %while.cond.outer.outer.backedge 239 240 while.cond.outer.outer.backedge: 241 br label %while.cond.outer.outer 242 243 while.end: 244 ret void 245 } 246 247 ; Remove a nested loop with irreducible control flow. 248 ; Ensure that only the middle loop is removed and rely on verify-loopinfo to 249 ; check soundness. 250 ; 251 ; CHECK-LABEL: @unloopIrreducible( 252 ; Irreducible loop. 253 ; CHECK: for.inc117: 254 ; CHECK: br label %for.cond103t 255 ; Nested loop (removed). 256 ; CHECK: for.inc159: 257 ; CHECK: br label %for.inc163 258 define void @unloopIrreducible() nounwind { 259 260 entry: 261 br label %for.body 262 263 for.body: 264 %cmp2113 = call zeroext i1 @check() 265 br i1 %cmp2113, label %for.body22.lr.ph, label %for.inc163 266 267 for.body22.lr.ph: 268 br label %for.body22 269 270 for.body22: 271 br label %for.body33 272 273 for.body33: 274 br label %for.end 275 276 for.end: 277 %cmp424 = call zeroext i1 @check() 278 br i1 %cmp424, label %for.body43.lr.ph, label %for.end93 279 280 for.body43.lr.ph: 281 br label %for.end93 282 283 for.end93: 284 %cmp96 = call zeroext i1 @check() 285 br i1 %cmp96, label %if.then97, label %for.cond103 286 287 if.then97: 288 br label %for.cond103t 289 290 for.cond103t: 291 br label %for.cond103 292 293 for.cond103: 294 %cmp105 = call zeroext i1 @check() 295 br i1 %cmp105, label %for.body106, label %for.end120 296 297 for.body106: 298 %cmp108 = call zeroext i1 @check() 299 br i1 %cmp108, label %if.then109, label %for.inc117 300 301 if.then109: 302 br label %for.inc117 303 304 for.inc117: 305 br label %for.cond103t 306 307 for.end120: 308 br label %for.inc159 309 310 for.inc159: 311 br i1 false, label %for.body22, label %for.cond15.for.inc163_crit_edge 312 313 for.cond15.for.inc163_crit_edge: 314 br label %for.inc163 315 316 for.inc163: 317 %cmp12 = call zeroext i1 @check() 318 br i1 %cmp12, label %for.body, label %for.end166 319 320 for.end166: 321 ret void 322 323 } 324 325 ; Remove a loop whose exit branches into a sibling loop. 326 ; Ensure that only the loop is removed and rely on verify-loopinfo to 327 ; check soundness. 328 ; 329 ; CHECK-LABEL: @unloopCriticalEdge( 330 ; CHECK: while.cond.outer.i.loopexit.split: 331 ; CHECK: br label %while.body 332 ; CHECK: while.body: 333 ; CHECK: br label %for.end78 334 define void @unloopCriticalEdge() nounwind { 335 entry: 336 br label %for.cond31 337 338 for.cond31: 339 br i1 undef, label %for.body35, label %for.end94 340 341 for.body35: 342 br label %while.cond.i.preheader 343 344 while.cond.i.preheader: 345 br i1 undef, label %while.cond.i.preheader.split, label %while.cond.outer.i.loopexit.split 346 347 while.cond.i.preheader.split: 348 br label %while.cond.i 349 350 while.cond.i: 351 br i1 true, label %while.cond.i, label %while.cond.outer.i.loopexit 352 353 while.cond.outer.i.loopexit: 354 br label %while.cond.outer.i.loopexit.split 355 356 while.cond.outer.i.loopexit.split: 357 br i1 false, label %while.cond.i.preheader, label %Func2.exit 358 359 Func2.exit: 360 br label %while.body 361 362 while.body: 363 br i1 false, label %while.body, label %while.end 364 365 while.end: 366 br label %for.end78 367 368 for.end78: 369 br i1 undef, label %Proc2.exit, label %for.cond.i.preheader 370 371 for.cond.i.preheader: 372 br label %for.cond.i 373 374 for.cond.i: 375 br label %for.cond.i 376 377 Proc2.exit: 378 br label %for.cond31 379 380 for.end94: 381 ret void 382 } 383 384 ; Test UnloopUpdater::removeBlocksFromAncestors. 385 ; 386 ; Check that the loop backedge is removed from the middle loop 1699, 387 ; but not the inner loop 1676. 388 ; CHECK: while.body1694: 389 ; CHECK: br label %while.cond1676 390 ; CHECK: while.end1699: 391 ; CHECK: br label %sw.default1711 392 define void @removeSubloopBlocks() nounwind { 393 entry: 394 br label %tryagain.outer 395 396 tryagain.outer: ; preds = %sw.bb304, %entry 397 br label %tryagain 398 399 tryagain: ; preds = %while.end1699, %tryagain.outer 400 br i1 undef, label %sw.bb1669, label %sw.bb304 401 402 sw.bb304: ; preds = %tryagain 403 br i1 undef, label %return, label %tryagain.outer 404 405 sw.bb1669: ; preds = %tryagain 406 br i1 undef, label %sw.default1711, label %while.cond1676 407 408 while.cond1676: ; preds = %while.body1694, %sw.bb1669 409 br i1 undef, label %while.end1699, label %while.body1694 410 411 while.body1694: ; preds = %while.cond1676 412 br label %while.cond1676 413 414 while.end1699: ; preds = %while.cond1676 415 br i1 false, label %tryagain, label %sw.default1711 416 417 sw.default1711: ; preds = %while.end1699, %sw.bb1669, %tryagain 418 br label %defchar 419 420 defchar: ; preds = %sw.default1711, %sw.bb376 421 br i1 undef, label %if.end2413, label %if.then2368 422 423 if.then2368: ; preds = %defchar 424 unreachable 425 426 if.end2413: ; preds = %defchar 427 unreachable 428 429 return: ; preds = %sw.bb304 430 ret void 431 } 432 433 ; PR11335: the most deeply nested block should be removed from the outer loop. 434 ; CHECK-LABEL: @removeSubloopBlocks2( 435 ; CHECK: for.cond3: 436 ; CHECK-NOT: br 437 ; CHECK: ret void 438 define void @removeSubloopBlocks2() nounwind { 439 entry: 440 %tobool.i = icmp ne i32 undef, 0 441 br label %lbl_616 442 443 lbl_616.loopexit: ; preds = %for.cond 444 br label %lbl_616 445 446 lbl_616: ; preds = %lbl_616.loopexit, %entry 447 br label %for.cond 448 449 for.cond: ; preds = %for.cond3, %lbl_616 450 br i1 false, label %for.cond1.preheader, label %lbl_616.loopexit 451 452 for.cond1.preheader: ; preds = %for.cond 453 br label %for.cond1 454 455 for.cond1.loopexit: ; preds = %for.cond.i 456 br label %for.cond1 457 458 for.cond1: ; preds = %for.cond1.loopexit, %for.cond1.preheader 459 br i1 false, label %for.body2, label %for.cond3 460 461 for.body2: ; preds = %for.cond1 462 br label %for.cond.i 463 464 for.cond.i: ; preds = %for.cond.i, %for.body2 465 br i1 %tobool.i, label %for.cond.i, label %for.cond1.loopexit 466 467 for.cond3: ; preds = %for.cond1 468 br i1 false, label %for.cond, label %if.end 469 470 if.end: ; preds = %for.cond3 471 ret void 472 } 473
