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