1; RUN: opt < %s -S -loop-unroll -verify-loop-info | FileCheck %s 2; 3; Unit tests for LoopInfo::markAsRemoved. 4 5declare 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 14define void @skiplevelexit() nounwind { 15entry: 16 br label %outer 17 18outer: 19 br label %inner 20 21inner: 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 27tail: 28 br i1 false, label %inner, label %exit 29 30outer.backedge: 31 br label %outer 32 33exit: 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 52define void @unloopNested() { 53entry: 54 br label %while.cond.outer 55 56while.cond.outer: 57 br label %while.cond 58 59while.cond: 60 %cmp = call zeroext i1 @check() 61 br i1 %cmp, label %while.body, label %while.end 62 63while.body: 64 %cmp3 = call zeroext i1 @check() 65 br i1 %cmp3, label %if.then, label %if.end 66 67if.then: 68 br label %return 69 70if.end: 71 %cmp.i48 = call zeroext i1 @check() 72 br i1 %cmp.i48, label %if.then.i, label %if.else20.i 73 74if.then.i: 75 %cmp8.i = call zeroext i1 @check() 76 br i1 %cmp8.i, label %merge, label %if.else.i 77 78if.else.i: 79 br label %merge 80 81if.else20.i: 82 %cmp25.i = call zeroext i1 @check() 83 br i1 %cmp25.i, label %merge, label %if.else28.i 84 85if.else28.i: 86 br label %merge 87 88merge: 89 br label %while.cond2.i 90 91while.cond2.i: 92 %cmp.i = call zeroext i1 @check() 93 br i1 %cmp.i, label %while.cond2.backedge.i, label %while.end.i 94 95while.cond2.backedge.i: 96 br label %while.cond2.i 97 98while.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 102while.body12.lr.ph.i: 103 br label %while.end14.i 104 105while.end14.i: 106 %call15.i = call zeroext i1 @check() 107 br i1 %call15.i, label %if.end.i, label %exit 108 109if.end.i: 110 br label %while.cond2.backedge.i 111 112exit: 113 br i1 false, label %while.cond, label %if.else 114 115if.else: 116 br label %while.cond.outer 117 118while.end: 119 br label %return 120 121return: 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 150define void @unloopDeepNested() nounwind { 151for.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 155for.body13.lr.ph.i: 156 br label %make_data.exit 157 158make_data.exit: 159 br label %while.cond.outer.outer 160 161while.cond.outer.outer: 162 br label %while.cond.outer 163 164while.cond.outer: 165 br label %while.cond 166 167while.cond: 168 br label %while.cond.outer.i 169 170while.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 174while.cond.outer.split.us.i: 175 br label %while.cond.us.i 176 177while.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 181while.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 185if.then.us.i: 186 br label %while.cond.us.i 187 188if.else.i: 189 br label %while.cond.outer.i 190 191next_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 195while.body.loopexit: 196 br label %while.body 197 198while.body: 199 br label %while.cond.i 200 201while.cond.i: 202 %cmp.i = call zeroext i1 @check() 203 br i1 %cmp.i, label %valid_data.exit, label %while.body.i 204 205while.body.i: 206 %cmp7.i = call zeroext i1 @check() 207 br i1 %cmp7.i, label %valid_data.exit, label %if.end.i 208 209if.end.i: 210 br label %while.cond.i 211 212valid_data.exit: 213 br i1 true, label %if.then, label %while.cond 214 215if.then: 216 %cmp = call zeroext i1 @check() 217 br i1 %cmp, label %if.then12, label %if.end 218 219if.then12: 220 br label %if.end 221 222if.end: 223 %tobool3.i = call zeroext i1 @check() 224 br i1 %tobool3.i, label %copy_data.exit, label %while.body.lr.ph.i 225 226while.body.lr.ph.i: 227 br label %copy_data.exit 228 229copy_data.exit: 230 %cmp38 = call zeroext i1 @check() 231 br i1 %cmp38, label %if.then39, label %while.cond.outer 232 233if.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 237for.cond8.preheader.i8.thread: 238 br label %while.cond.outer.outer.backedge 239 240while.cond.outer.outer.backedge: 241 br label %while.cond.outer.outer 242 243while.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 258define void @unloopIrreducible() nounwind { 259 260entry: 261 br label %for.body 262 263for.body: 264 %cmp2113 = call zeroext i1 @check() 265 br i1 %cmp2113, label %for.body22.lr.ph, label %for.inc163 266 267for.body22.lr.ph: 268 br label %for.body22 269 270for.body22: 271 br label %for.body33 272 273for.body33: 274 br label %for.end 275 276for.end: 277 %cmp424 = call zeroext i1 @check() 278 br i1 %cmp424, label %for.body43.lr.ph, label %for.end93 279 280for.body43.lr.ph: 281 br label %for.end93 282 283for.end93: 284 %cmp96 = call zeroext i1 @check() 285 br i1 %cmp96, label %if.then97, label %for.cond103 286 287if.then97: 288 br label %for.cond103t 289 290for.cond103t: 291 br label %for.cond103 292 293for.cond103: 294 %cmp105 = call zeroext i1 @check() 295 br i1 %cmp105, label %for.body106, label %for.end120 296 297for.body106: 298 %cmp108 = call zeroext i1 @check() 299 br i1 %cmp108, label %if.then109, label %for.inc117 300 301if.then109: 302 br label %for.inc117 303 304for.inc117: 305 br label %for.cond103t 306 307for.end120: 308 br label %for.inc159 309 310for.inc159: 311 br i1 false, label %for.body22, label %for.cond15.for.inc163_crit_edge 312 313for.cond15.for.inc163_crit_edge: 314 br label %for.inc163 315 316for.inc163: 317 %cmp12 = call zeroext i1 @check() 318 br i1 %cmp12, label %for.body, label %for.end166 319 320for.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 334define void @unloopCriticalEdge() nounwind { 335entry: 336 br label %for.cond31 337 338for.cond31: 339 br i1 undef, label %for.body35, label %for.end94 340 341for.body35: 342 br label %while.cond.i.preheader 343 344while.cond.i.preheader: 345 br i1 undef, label %while.cond.i.preheader.split, label %while.cond.outer.i.loopexit.split 346 347while.cond.i.preheader.split: 348 br label %while.cond.i 349 350while.cond.i: 351 br i1 true, label %while.cond.i, label %while.cond.outer.i.loopexit 352 353while.cond.outer.i.loopexit: 354 br label %while.cond.outer.i.loopexit.split 355 356while.cond.outer.i.loopexit.split: 357 br i1 false, label %while.cond.i.preheader, label %Func2.exit 358 359Func2.exit: 360 br label %while.body 361 362while.body: 363 br i1 false, label %while.body, label %while.end 364 365while.end: 366 br label %for.end78 367 368for.end78: 369 br i1 undef, label %Proc2.exit, label %for.cond.i.preheader 370 371for.cond.i.preheader: 372 br label %for.cond.i 373 374for.cond.i: 375 br label %for.cond.i 376 377Proc2.exit: 378 br label %for.cond31 379 380for.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 392define void @removeSubloopBlocks() nounwind { 393entry: 394 br label %tryagain.outer 395 396tryagain.outer: ; preds = %sw.bb304, %entry 397 br label %tryagain 398 399tryagain: ; preds = %while.end1699, %tryagain.outer 400 br i1 undef, label %sw.bb1669, label %sw.bb304 401 402sw.bb304: ; preds = %tryagain 403 br i1 undef, label %return, label %tryagain.outer 404 405sw.bb1669: ; preds = %tryagain 406 br i1 undef, label %sw.default1711, label %while.cond1676 407 408while.cond1676: ; preds = %while.body1694, %sw.bb1669 409 br i1 undef, label %while.end1699, label %while.body1694 410 411while.body1694: ; preds = %while.cond1676 412 br label %while.cond1676 413 414while.end1699: ; preds = %while.cond1676 415 br i1 false, label %tryagain, label %sw.default1711 416 417sw.default1711: ; preds = %while.end1699, %sw.bb1669, %tryagain 418 br label %defchar 419 420defchar: ; preds = %sw.default1711, %sw.bb376 421 br i1 undef, label %if.end2413, label %if.then2368 422 423if.then2368: ; preds = %defchar 424 unreachable 425 426if.end2413: ; preds = %defchar 427 unreachable 428 429return: ; 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 438define void @removeSubloopBlocks2() nounwind { 439entry: 440 %tobool.i = icmp ne i32 undef, 0 441 br label %lbl_616 442 443lbl_616.loopexit: ; preds = %for.cond 444 br label %lbl_616 445 446lbl_616: ; preds = %lbl_616.loopexit, %entry 447 br label %for.cond 448 449for.cond: ; preds = %for.cond3, %lbl_616 450 br i1 false, label %for.cond1.preheader, label %lbl_616.loopexit 451 452for.cond1.preheader: ; preds = %for.cond 453 br label %for.cond1 454 455for.cond1.loopexit: ; preds = %for.cond.i 456 br label %for.cond1 457 458for.cond1: ; preds = %for.cond1.loopexit, %for.cond1.preheader 459 br i1 false, label %for.body2, label %for.cond3 460 461for.body2: ; preds = %for.cond1 462 br label %for.cond.i 463 464for.cond.i: ; preds = %for.cond.i, %for.body2 465 br i1 %tobool.i, label %for.cond.i, label %for.cond1.loopexit 466 467for.cond3: ; preds = %for.cond1 468 br i1 false, label %for.cond, label %if.end 469 470if.end: ; preds = %for.cond3 471 ret void 472} 473