This is an archive of the discontinued LLVM Phabricator instance.

Differential D54831

[LoopSimplifyCFG] Delete current loop
AbandonedPublic

Authored by mkazantsev on Nov 22 2018, 3:54 AM.

Details

Reviewers
skatkov
apilipenko
anna
reames
Summary

This patch lifts the final limitation posed on LoopSimplifyCFG by
teaching it to delete current loop.

(Not adding reviewers because it needs too many underlying patches merged first).

Diff Detail

Event Timeline

mkazantsev created this revision.Nov 22 2018, 3:54 AM
mkazantsev added a parent revision: D54750: [LoopSimplifyCFG] Support blocks that are live, but no longer a part of current loop.
mkazantsev updated this revision to Diff 175036.Nov 22 2018, 3:57 AM
mkazantsev planned changes to this revision.Nov 22 2018, 4:16 AM

Just setting "Plan changes" to not confuse reviewers too much with amount of patches in progress.

mkazantsev updated this revision to Diff 175440.Nov 27 2018, 3:07 AM

Rebased

mkazantsev planned changes to this revision.Nov 29 2018, 1:11 AM
mkazantsev updated this revision to Diff 187337.Feb 19 2019, 3:11 AM
mkazantsev added reviewers: skatkov, apilipenko, anna, reames.

Rebased.

Herald added a project: Restricted Project. · View Herald TranscriptFeb 19 2019, 3:11 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
reames resigned from this revision.Mar 25 2020, 11:21 AM
mkazantsev abandoned this revision.Sep 24 2020, 3:00 AM

Revision Contents

PathSize
llvm/
lib/
Transforms/
Scalar/
14 lines
test/
Transforms/
LoopSimplifyCFG/
244 lines
8 lines
8 lines
22 lines

Diff 187337

llvm/lib/Transforms/Scalar/LoopSimplifyCFG.cpp

Show First 20 Lines • Show All 514 Lines • ▼ Show 20 Lines void deleteDeadLoopBlocks() {
// The function LI.erase has some invariants that need to be preserved when // The function LI.erase has some invariants that need to be preserved when
// it tries to remove a loop which is not the top-level loop. In particular, // it tries to remove a loop which is not the top-level loop. In particular,
// it requires loop's preheader to be strictly in loop's parent. We cannot // it requires loop's preheader to be strictly in loop's parent. We cannot
// just remove blocks one by one, because after removal of preheader we may // just remove blocks one by one, because after removal of preheader we may
// break this invariant for the dead loop. So we detatch and erase all dead // break this invariant for the dead loop. So we detatch and erase all dead
// loops beforehand. // loops beforehand.
for (auto *BB : DeadLoopBlocks) for (auto *BB : DeadLoopBlocks)
if (LI.isLoopHeader(BB)) { if (LI.isLoopHeader(BB)) {
assert(LI.getLoopFor(BB) != &L && "Attempt to remove current loop!");
Loop *DL = LI.getLoopFor(BB); Loop *DL = LI.getLoopFor(BB);
if (DL->getParentLoop()) { if (DL->getParentLoop()) {
for (auto *PL = DL->getParentLoop(); PL; PL = PL->getParentLoop()) for (auto *PL = DL->getParentLoop(); PL; PL = PL->getParentLoop())
for (auto *BB : DL->getBlocks()) for (auto *BB : DL->getBlocks())
PL->removeBlockFromLoop(BB); PL->removeBlockFromLoop(BB);
DL->getParentLoop()->removeChildLoop(DL); DL->getParentLoop()->removeChildLoop(DL);
LI.addTopLevelLoop(DL); LI.addTopLevelLoop(DL);
} }
LI.erase(DL); LI.erase(DL);
} }
for (auto *BB : DeadLoopBlocks) { for (auto *BB : DeadLoopBlocks) {
assert(BB != L.getHeader() &&
"Header of the current loop cannot be dead!");
LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName() LLVM_DEBUG(dbgs() << "Deleting dead loop block " << BB->getName()
<< "\n"); << "\n");
LI.removeBlock(BB); LI.removeBlock(BB);
} }
DetatchDeadBlocks(DeadLoopBlocks, &DTUpdates, /*KeepOneInputPHIs*/true); DetatchDeadBlocks(DeadLoopBlocks, &DTUpdates, /*KeepOneInputPHIs*/true);
DTU.applyUpdates(DTUpdates); DTU.applyUpdates(DTUpdates);
DTUpdates.clear(); DTUpdates.clear();
▲ Show 20 Lines • Show All 79 Lines • ▼ Show 20 Lines bool run() {
// Nothing to constant-fold. // Nothing to constant-fold.
if (FoldCandidates.empty()) { if (FoldCandidates.empty()) {
LLVM_DEBUG( LLVM_DEBUG(
dbgs() << "No constant terminator folding candidates found in loop " dbgs() << "No constant terminator folding candidates found in loop "
<< Header->getName() << "\n"); << Header->getName() << "\n");
return false; return false;
} }
// TODO: Support deletion of the current loop.
if (DeleteCurrentLoop) {
LLVM_DEBUG(
dbgs()
<< "Give up constant terminator folding in loop " << Header->getName()
<< ": we don't currently support deletion of the current loop.\n");
return false;
}
SE.forgetTopmostLoop(&L); SE.forgetTopmostLoop(&L);
// Dump analysis results. // Dump analysis results.
LLVM_DEBUG(dump()); LLVM_DEBUG(dump());
LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size() LLVM_DEBUG(dbgs() << "Constant-folding " << FoldCandidates.size()
<< " terminators in loop " << Header->getName() << "\n"); << " terminators in loop " << Header->getName() << "\n");
// Make the actual transforms. // Make the actual transforms.
handleDeadExits(); handleDeadExits();
foldTerminators(); foldTerminators();
updateLiveBlocksInfo(); updateLiveBlocksInfo();
if (!DeadLoopBlocks.empty()) { if (!DeadLoopBlocks.empty()) {
LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size() LLVM_DEBUG(dbgs() << "Deleting " << DeadLoopBlocks.size()
<< " dead blocks in loop " << Header->getName() << "\n"); << " dead blocks in loop " << Header->getName() << "\n");
deleteDeadLoopBlocks(); deleteDeadLoopBlocks();
} else { } else {
// If we didn't do updates inside deleteDeadLoopBlocks, do them here. // If we didn't do updates inside deleteDeadLoopBlocks, do them here.
DTU.applyUpdates(DTUpdates); DTU.applyUpdates(DTUpdates);
DTUpdates.clear(); DTUpdates.clear();
if (DeleteCurrentLoop)
LI.erase(&L);
} }
#ifndef NDEBUG #ifndef NDEBUG
// Make sure that we have preserved all data structures after the transform. // Make sure that we have preserved all data structures after the transform.
assert(DT.verify() && "DT broken after transform!"); assert(DT.verify() && "DT broken after transform!");
assert(DT.isReachableFromEntry(Header)); assert(DT.isReachableFromEntry(Header));
LI.verify(DT); LI.verify(DT);
#endif #endif
▲ Show 20 Lines • Show All 149 Lines • Show Last 20 Lines

llvm/test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll

Show First 20 Lines • Show All 329 Lines • ▼ Show 20 Lines
} }
; Check that we can completely eliminate the current loop, branch case. ; Check that we can completely eliminate the current loop, branch case.
define i32 @dead_loop_test_branch_loop(i32 %end) { define i32 @dead_loop_test_branch_loop(i32 %end) {
; CHECK-LABEL: @dead_loop_test_branch_loop( ; CHECK-LABEL: @dead_loop_test_branch_loop(
; CHECK-NEXT: preheader: ; CHECK-NEXT: preheader:
; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK-NEXT: br label [[HEADER:%.*]]
; CHECK: header: ; CHECK: header:
; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: br label [[BACKEDGE:%.*]]
; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[DEAD:%.*]]
; CHECK: dead:
; CHECK-NEXT: [[I_2:%.*]] = add i32 [[I]], 1
; CHECK-NEXT: br label [[BACKEDGE]]
; CHECK: backedge: ; CHECK: backedge:
; CHECK-NEXT: [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ] ; CHECK-NEXT: [[I_1:%.*]] = phi i32 [ 0, [[HEADER]] ]
; CHECK-NEXT: [[I_INC]] = add i32 [[I_1]], 1 ; CHECK-NEXT: [[I_INC:%.*]] = add i32 [[I_1]], 1
; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]] ; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
; CHECK-NEXT: br i1 false, label [[HEADER]], label [[EXIT:%.*]] ; CHECK-NEXT: br label [[EXIT:%.*]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] ; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
; CHECK-NEXT: ret i32 [[I_INC_LCSSA]] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA]]
; ;
preheader: preheader:
br label %header br label %header
header: header:
Show All 18 Lines
} }
; Check that we can completely eliminate the current loop, switch case. ; Check that we can completely eliminate the current loop, switch case.
define i32 @dead_loop_test_switch_loop(i32 %end) { define i32 @dead_loop_test_switch_loop(i32 %end) {
; CHECK-LABEL: @dead_loop_test_switch_loop( ; CHECK-LABEL: @dead_loop_test_switch_loop(
; CHECK-NEXT: preheader: ; CHECK-NEXT: preheader:
; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK-NEXT: br label [[HEADER:%.*]]
; CHECK: header: ; CHECK: header:
; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: br label [[BACKEDGE:%.*]]
; CHECK-NEXT: switch i32 1, label [[DEAD:%.*]] [
; CHECK-NEXT: i32 0, label [[DEAD]]
; CHECK-NEXT: i32 1, label [[BACKEDGE]]
; CHECK-NEXT: i32 2, label [[DEAD]]
; CHECK-NEXT: ]
; CHECK: dead:
; CHECK-NEXT: [[I_2:%.*]] = add i32 [[I]], 1
; CHECK-NEXT: br label [[BACKEDGE]]
; CHECK: backedge: ; CHECK: backedge:
; CHECK-NEXT: [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ] ; CHECK-NEXT: [[I_1:%.*]] = phi i32 [ 0, [[HEADER]] ]
; CHECK-NEXT: [[I_INC]] = add i32 [[I_1]], 1 ; CHECK-NEXT: [[I_INC:%.*]] = add i32 [[I_1]], 1
; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]] ; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[I_INC]], [[END:%.*]]
; CHECK-NEXT: br i1 false, label [[HEADER]], label [[EXIT:%.*]] ; CHECK-NEXT: br label [[EXIT:%.*]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ] ; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
; CHECK-NEXT: ret i32 [[I_INC_LCSSA]] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA]]
; ;
preheader: preheader:
br label %header br label %header
header: header:
%i = phi i32 [0, %preheader], [%i.inc, %backedge] %i = phi i32 [0, %preheader], [%i.inc, %backedge]
▲ Show 20 Lines • Show All 521 Lines • ▼ Show 20 Lines
} }
; Check that we can completely delete inner loop and preserve the outer loop. ; Check that we can completely delete inner loop and preserve the outer loop.
define i32 @full_sub_loop_test_branch_loop(i32 %end) { define i32 @full_sub_loop_test_branch_loop(i32 %end) {
; CHECK-LABEL: @full_sub_loop_test_branch_loop( ; CHECK-LABEL: @full_sub_loop_test_branch_loop(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] ; CHECK-NEXT: br label [[OUTER_HEADER:%.*]]
; CHECK: outer_header: ; CHECK: outer_header:
; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_HEADER]] ]
; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK-NEXT: [[MUL:%.*]] = mul i32 0, 0
; CHECK: header: ; CHECK-NEXT: [[I_2:%.*]] = add i32 0, 1
; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[I_INC:%.*]] = add i32 [[I_2]], 1
; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[I]], [[I]]
; CHECK-NEXT: br i1 false, label [[BACKEDGE]], label [[DEAD:%.*]]
; CHECK: dead:
; CHECK-NEXT: [[I_2:%.*]] = add i32 [[I]], 1
; CHECK-NEXT: br label [[BACKEDGE]]
; CHECK: backedge:
; CHECK-NEXT: [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ]
; CHECK-NEXT: [[I_INC]] = add i32 [[I_1]], 1
; CHECK-NEXT: br i1 false, label [[HEADER]], label [[OUTER_BACKEDGE]]
; CHECK: outer_backedge:
; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
; CHECK-NEXT: [[J_INC]] = add i32 [[J]], 1 ; CHECK-NEXT: [[J_INC]] = add i32 [[J]], 1
; CHECK-NEXT: [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]] ; CHECK-NEXT: [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]]
; CHECK-NEXT: br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC_LCSSA]], [[OUTER_BACKEDGE]] ] ; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[OUTER_HEADER]] ]
; CHECK-NEXT: ret i32 [[I_INC_LCSSA_LCSSA]] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA_LCSSA]]
; ;
entry: entry:
br label %outer_header br label %outer_header
outer_header: outer_header:
%j = phi i32 [0, %entry], [%j.inc, %outer_backedge] %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
br label %preheader br label %preheader
Show All 27 Linesexit:
ret i32 %i.inc ret i32 %i.inc
} }
define i32 @full_sub_loop_test_switch_loop(i32 %end) { define i32 @full_sub_loop_test_switch_loop(i32 %end) {
; CHECK-LABEL: @full_sub_loop_test_switch_loop( ; CHECK-LABEL: @full_sub_loop_test_switch_loop(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] ; CHECK-NEXT: br label [[OUTER_HEADER:%.*]]
; CHECK: outer_header: ; CHECK: outer_header:
; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_HEADER]] ]
; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK-NEXT: [[MUL:%.*]] = mul i32 0, 0
; CHECK: header: ; CHECK-NEXT: [[I_2:%.*]] = add i32 0, 1
; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ] ; CHECK-NEXT: [[I_INC:%.*]] = add i32 [[I_2]], 1
; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[I]], [[I]]
; CHECK-NEXT: switch i32 1, label [[DEAD:%.*]] [
; CHECK-NEXT: i32 0, label [[BACKEDGE]]
; CHECK-NEXT: ]
; CHECK: dead:
; CHECK-NEXT: [[I_2:%.*]] = add i32 [[I]], 1
; CHECK-NEXT: br label [[BACKEDGE]]
; CHECK: backedge:
; CHECK-NEXT: [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ]
; CHECK-NEXT: [[I_INC]] = add i32 [[I_1]], 1
; CHECK-NEXT: switch i32 1, label [[OUTER_BACKEDGE]] [
; CHECK-NEXT: i32 0, label [[HEADER]]
; CHECK-NEXT: ]
; CHECK: outer_backedge:
; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
; CHECK-NEXT: [[J_INC]] = add i32 [[J]], 1 ; CHECK-NEXT: [[J_INC]] = add i32 [[J]], 1
; CHECK-NEXT: [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]] ; CHECK-NEXT: [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]]
; CHECK-NEXT: br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC_LCSSA]], [[OUTER_BACKEDGE]] ] ; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[OUTER_HEADER]] ]
; CHECK-NEXT: ret i32 [[I_INC_LCSSA_LCSSA]] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA_LCSSA]]
; ;
entry: entry:
br label %outer_header br label %outer_header
outer_header: outer_header:
%j = phi i32 [0, %entry], [%j.inc, %outer_backedge] %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
br label %preheader br label %preheader
Show All 28 Lines
} }
; Inverted condition in live_part. ; Inverted condition in live_part.
define i32 @full_sub_loop_test_branch_loop_inverse_1(i32 %end) { define i32 @full_sub_loop_test_branch_loop_inverse_1(i32 %end) {
; CHECK-LABEL: @full_sub_loop_test_branch_loop_inverse_1( ; CHECK-LABEL: @full_sub_loop_test_branch_loop_inverse_1(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] ; CHECK-NEXT: br label [[OUTER_HEADER:%.*]]
; CHECK: outer_header: ; CHECK: outer_header:
; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_HEADER]] ]
; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK-NEXT: [[MUL:%.*]] = mul i32 0, 0
; CHECK: header: ; CHECK-NEXT: [[I_INC:%.*]] = add i32 0, 1
; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[I]], [[I]]
; CHECK-NEXT: br i1 true, label [[BACKEDGE]], label [[DEAD:%.*]]
; CHECK: dead:
; CHECK-NEXT: [[I_2:%.*]] = add i32 [[I]], 1
; CHECK-NEXT: br label [[BACKEDGE]]
; CHECK: backedge:
; CHECK-NEXT: [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ]
; CHECK-NEXT: [[I_INC]] = add i32 [[I_1]], 1
; CHECK-NEXT: br i1 false, label [[HEADER]], label [[OUTER_BACKEDGE]]
; CHECK: outer_backedge:
; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
; CHECK-NEXT: [[J_INC]] = add i32 [[J]], 1 ; CHECK-NEXT: [[J_INC]] = add i32 [[J]], 1
; CHECK-NEXT: [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]] ; CHECK-NEXT: [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]]
; CHECK-NEXT: br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC_LCSSA]], [[OUTER_BACKEDGE]] ] ; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[OUTER_HEADER]] ]
; CHECK-NEXT: ret i32 [[I_INC_LCSSA_LCSSA]] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA_LCSSA]]
; ;
entry: entry:
br label %outer_header br label %outer_header
outer_header: outer_header:
%j = phi i32 [0, %entry], [%j.inc, %outer_backedge] %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
br label %preheader br label %preheader
Show All 27 Linesexit:
ret i32 %i.inc ret i32 %i.inc
} }
define i32 @full_sub_loop_test_switch_loop_inverse_1(i32 %end) { define i32 @full_sub_loop_test_switch_loop_inverse_1(i32 %end) {
; CHECK-LABEL: @full_sub_loop_test_switch_loop_inverse_1( ; CHECK-LABEL: @full_sub_loop_test_switch_loop_inverse_1(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] ; CHECK-NEXT: br label [[OUTER_HEADER:%.*]]
; CHECK: outer_header: ; CHECK: outer_header:
; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_HEADER]] ]
; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK-NEXT: [[MUL:%.*]] = mul i32 0, 0
; CHECK: header: ; CHECK-NEXT: [[I_INC:%.*]] = add i32 0, 1
; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[OUTER_HEADER]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[I]], [[I]]
; CHECK-NEXT: switch i32 1, label [[BACKEDGE]] [
; CHECK-NEXT: i32 0, label [[DEAD:%.*]]
; CHECK-NEXT: ]
; CHECK: dead:
; CHECK-NEXT: [[I_2:%.*]] = add i32 [[I]], 1
; CHECK-NEXT: br label [[BACKEDGE]]
; CHECK: backedge:
; CHECK-NEXT: [[I_1:%.*]] = phi i32 [ [[I]], [[HEADER]] ], [ [[I_2]], [[DEAD]] ]
; CHECK-NEXT: [[I_INC]] = add i32 [[I_1]], 1
; CHECK-NEXT: switch i32 1, label [[OUTER_BACKEDGE]] [
; CHECK-NEXT: i32 0, label [[HEADER]]
; CHECK-NEXT: ]
; CHECK: outer_backedge:
; CHECK-NEXT: [[I_INC_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[BACKEDGE]] ]
; CHECK-NEXT: [[J_INC]] = add i32 [[J]], 1 ; CHECK-NEXT: [[J_INC]] = add i32 [[J]], 1
; CHECK-NEXT: [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]] ; CHECK-NEXT: [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]]
; CHECK-NEXT: br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC_LCSSA]], [[OUTER_BACKEDGE]] ] ; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ [[I_INC]], [[OUTER_HEADER]] ]
; CHECK-NEXT: ret i32 [[I_INC_LCSSA_LCSSA]] ; CHECK-NEXT: ret i32 [[I_INC_LCSSA_LCSSA]]
; ;
entry: entry:
br label %outer_header br label %outer_header
outer_header: outer_header:
%j = phi i32 [0, %entry], [%j.inc, %outer_backedge] %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
br label %preheader br label %preheader
Show All 25 Lines
exit: exit:
ret i32 %i.inc ret i32 %i.inc
} }
define i32 @full_sub_loop_test_branch_loop_inverse_2(i32 %end) { define i32 @full_sub_loop_test_branch_loop_inverse_2(i32 %end) {
; CHECK-LABEL: @full_sub_loop_test_branch_loop_inverse_2( ; CHECK-LABEL: @full_sub_loop_test_branch_loop_inverse_2(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: switch i32 0, label [[ENTRY_SPLIT:%.*]] [
; CHECK-NEXT: i32 1, label [[EXIT:%.*]]
; CHECK-NEXT: ]
; CHECK: entry-split:
; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] ; CHECK-NEXT: br label [[OUTER_HEADER:%.*]]
; CHECK: outer_header: ; CHECK: outer_header:
; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY_SPLIT]] ]
; CHECK-NEXT: switch i32 0, label [[PREHEADER_SPLIT:%.*]] [ ; CHECK-NEXT: br label [[PREHEADER:%.*]]
; CHECK-NEXT: i32 1, label [[OUTER_BACKEDGE]] ; CHECK: preheader:
; CHECK-NEXT: ] ; CHECK-NEXT: br label [[PREHEADER_SPLIT:%.*]]
; CHECK: preheader-split: ; CHECK: preheader-split:
; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK-NEXT: br label [[HEADER:%.*]]
; CHECK: header: ; CHECK: header:
; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ] ; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[I]], [[I]] ; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[I]], [[I]]
; CHECK-NEXT: [[I_2:%.*]] = add i32 [[I]], 1 ; CHECK-NEXT: [[I_2:%.*]] = add i32 [[I]], 1
; CHECK-NEXT: [[I_INC]] = add i32 [[I_2]], 1 ; CHECK-NEXT: [[I_INC]] = add i32 [[I_2]], 1
; CHECK-NEXT: br label [[HEADER]] ; CHECK-NEXT: br label [[HEADER]]
; CHECK: outer_backedge:
; CHECK-NEXT: [[J_INC]] = add i32 [[J]], 1
; CHECK-NEXT: [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]]
; CHECK-NEXT: br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ undef, [[OUTER_BACKEDGE]] ] ; CHECK-NEXT: ret i32 undef
; CHECK-NEXT: ret i32 [[I_INC_LCSSA_LCSSA]]
; ;
entry: entry:
br label %outer_header br label %outer_header
outer_header: outer_header:
%j = phi i32 [0, %entry], [%j.inc, %outer_backedge] %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
br label %preheader br label %preheader
Show All 24 Lines
exit: exit:
ret i32 %i.inc ret i32 %i.inc
} }
define i32 @full_sub_loop_test_switch_loop_inverse_2(i32 %end) { define i32 @full_sub_loop_test_switch_loop_inverse_2(i32 %end) {
; CHECK-LABEL: @full_sub_loop_test_switch_loop_inverse_2( ; CHECK-LABEL: @full_sub_loop_test_switch_loop_inverse_2(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: switch i32 0, label [[ENTRY_SPLIT:%.*]] [
; CHECK-NEXT: i32 1, label [[EXIT:%.*]]
; CHECK-NEXT: ]
; CHECK: entry-split:
; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] ; CHECK-NEXT: br label [[OUTER_HEADER:%.*]]
; CHECK: outer_header: ; CHECK: outer_header:
; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY_SPLIT]] ]
; CHECK-NEXT: switch i32 0, label [[PREHEADER_SPLIT:%.*]] [ ; CHECK-NEXT: br label [[PREHEADER:%.*]]
; CHECK-NEXT: i32 1, label [[OUTER_BACKEDGE]] ; CHECK: preheader:
; CHECK-NEXT: ] ; CHECK-NEXT: br label [[PREHEADER_SPLIT:%.*]]
; CHECK: preheader-split: ; CHECK: preheader-split:
; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK-NEXT: br label [[HEADER:%.*]]
; CHECK: header: ; CHECK: header:
; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ] ; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[I]], [[I]] ; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[I]], [[I]]
; CHECK-NEXT: [[I_2:%.*]] = add i32 [[I]], 1 ; CHECK-NEXT: [[I_2:%.*]] = add i32 [[I]], 1
; CHECK-NEXT: [[I_INC]] = add i32 [[I_2]], 1 ; CHECK-NEXT: [[I_INC]] = add i32 [[I_2]], 1
; CHECK-NEXT: br label [[HEADER]] ; CHECK-NEXT: br label [[HEADER]]
; CHECK: outer_backedge:
; CHECK-NEXT: [[J_INC]] = add i32 [[J]], 1
; CHECK-NEXT: [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]]
; CHECK-NEXT: br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ undef, [[OUTER_BACKEDGE]] ] ; CHECK-NEXT: ret i32 undef
; CHECK-NEXT: ret i32 [[I_INC_LCSSA_LCSSA]]
; ;
entry: entry:
br label %outer_header br label %outer_header
outer_header: outer_header:
%j = phi i32 [0, %entry], [%j.inc, %outer_backedge] %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
br label %preheader br label %preheader
Show All 25 Lines
exit: exit:
ret i32 %i.inc ret i32 %i.inc
} }
define i32 @full_sub_loop_test_branch_loop_inverse_3(i32 %end) { define i32 @full_sub_loop_test_branch_loop_inverse_3(i32 %end) {
; CHECK-LABEL: @full_sub_loop_test_branch_loop_inverse_3( ; CHECK-LABEL: @full_sub_loop_test_branch_loop_inverse_3(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: switch i32 0, label [[ENTRY_SPLIT:%.*]] [
; CHECK-NEXT: i32 1, label [[EXIT:%.*]]
; CHECK-NEXT: ]
; CHECK: entry-split:
; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] ; CHECK-NEXT: br label [[OUTER_HEADER:%.*]]
; CHECK: outer_header: ; CHECK: outer_header:
; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY_SPLIT]] ]
; CHECK-NEXT: switch i32 0, label [[PREHEADER_SPLIT:%.*]] [ ; CHECK-NEXT: br label [[PREHEADER:%.*]]
; CHECK-NEXT: i32 1, label [[OUTER_BACKEDGE]] ; CHECK: preheader:
; CHECK-NEXT: ] ; CHECK-NEXT: br label [[PREHEADER_SPLIT:%.*]]
; CHECK: preheader-split: ; CHECK: preheader-split:
; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK-NEXT: br label [[HEADER:%.*]]
; CHECK: header: ; CHECK: header:
; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ] ; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[I]], [[I]] ; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[I]], [[I]]
; CHECK-NEXT: [[I_INC]] = add i32 [[I]], 1 ; CHECK-NEXT: [[I_INC]] = add i32 [[I]], 1
; CHECK-NEXT: br label [[HEADER]] ; CHECK-NEXT: br label [[HEADER]]
; CHECK: outer_backedge:
; CHECK-NEXT: [[J_INC]] = add i32 [[J]], 1
; CHECK-NEXT: [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]]
; CHECK-NEXT: br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ undef, [[OUTER_BACKEDGE]] ] ; CHECK-NEXT: ret i32 undef
; CHECK-NEXT: ret i32 [[I_INC_LCSSA_LCSSA]]
; ;
entry: entry:
br label %outer_header br label %outer_header
outer_header: outer_header:
%j = phi i32 [0, %entry], [%j.inc, %outer_backedge] %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
br label %preheader br label %preheader
Show All 24 Lines
exit: exit:
ret i32 %i.inc ret i32 %i.inc
} }
define i32 @full_sub_loop_test_switch_loop_inverse_3(i32 %end) { define i32 @full_sub_loop_test_switch_loop_inverse_3(i32 %end) {
; CHECK-LABEL: @full_sub_loop_test_switch_loop_inverse_3( ; CHECK-LABEL: @full_sub_loop_test_switch_loop_inverse_3(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: switch i32 0, label [[ENTRY_SPLIT:%.*]] [
; CHECK-NEXT: i32 1, label [[EXIT:%.*]]
; CHECK-NEXT: ]
; CHECK: entry-split:
; CHECK-NEXT: br label [[OUTER_HEADER:%.*]] ; CHECK-NEXT: br label [[OUTER_HEADER:%.*]]
; CHECK: outer_header: ; CHECK: outer_header:
; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[J_INC:%.*]], [[OUTER_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[ENTRY_SPLIT]] ]
; CHECK-NEXT: switch i32 0, label [[PREHEADER_SPLIT:%.*]] [ ; CHECK-NEXT: br label [[PREHEADER:%.*]]
; CHECK-NEXT: i32 1, label [[OUTER_BACKEDGE]] ; CHECK: preheader:
; CHECK-NEXT: ] ; CHECK-NEXT: br label [[PREHEADER_SPLIT:%.*]]
; CHECK: preheader-split: ; CHECK: preheader-split:
; CHECK-NEXT: br label [[HEADER:%.*]] ; CHECK-NEXT: br label [[HEADER:%.*]]
; CHECK: header: ; CHECK: header:
; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ] ; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER_SPLIT]] ], [ [[I_INC:%.*]], [[HEADER]] ]
; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[I]], [[I]] ; CHECK-NEXT: [[MUL:%.*]] = mul i32 [[I]], [[I]]
; CHECK-NEXT: [[I_INC]] = add i32 [[I]], 1 ; CHECK-NEXT: [[I_INC]] = add i32 [[I]], 1
; CHECK-NEXT: br label [[HEADER]] ; CHECK-NEXT: br label [[HEADER]]
; CHECK: outer_backedge:
; CHECK-NEXT: [[J_INC]] = add i32 [[J]], 1
; CHECK-NEXT: [[CMP_J:%.*]] = icmp slt i32 [[J_INC]], [[END:%.*]]
; CHECK-NEXT: br i1 [[CMP_J]], label [[OUTER_HEADER]], label [[EXIT:%.*]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: [[I_INC_LCSSA_LCSSA:%.*]] = phi i32 [ undef, [[OUTER_BACKEDGE]] ] ; CHECK-NEXT: ret i32 undef
; CHECK-NEXT: ret i32 [[I_INC_LCSSA_LCSSA]]
; ;
entry: entry:
br label %outer_header br label %outer_header
outer_header: outer_header:
%j = phi i32 [0, %entry], [%j.inc, %outer_backedge] %j = phi i32 [0, %entry], [%j.inc, %outer_backedge]
br label %preheader br label %preheader
Show All 26 Linesexit:
ret i32 %i.inc ret i32 %i.inc
} }
define i32 @exit_branch_from_inner_to_grandparent(i1 %cond1, i1 %cond2, i32 %N) { define i32 @exit_branch_from_inner_to_grandparent(i1 %cond1, i1 %cond2, i32 %N) {
; CHECK-LABEL: @exit_branch_from_inner_to_grandparent( ; CHECK-LABEL: @exit_branch_from_inner_to_grandparent(
; CHECK-NEXT: preheader: ; CHECK-NEXT: preheader:
; CHECK-NEXT: br label [[LOOP_1:%.*]] ; CHECK-NEXT: br label [[LOOP_1:%.*]]
; CHECK: loop_1: ; CHECK: loop_1:
; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] ]
; CHECK-NEXT: br label [[LOOP_2:%.*]]
; CHECK: loop_2:
; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ]
; CHECK-NEXT: switch i32 0, label [[LOOP_2_SPLIT:%.*]] [
; CHECK-NEXT: i32 1, label [[LOOP_2_BACKEDGE]]
; CHECK-NEXT: ]
; CHECK: loop_2-split:
; CHECK-NEXT: br label [[LOOP_3:%.*]] ; CHECK-NEXT: br label [[LOOP_3:%.*]]
; CHECK: loop_3: ; CHECK: loop_3:
; CHECK-NEXT: [[K:%.*]] = phi i32 [ 0, [[LOOP_2_SPLIT]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[K:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
; CHECK-NEXT: br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] ; CHECK-NEXT: br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[LOOP_1_BACKEDGE_LOOPEXIT]]
; CHECK: loop_3_backedge: ; CHECK: loop_3_backedge:
; CHECK-NEXT: [[K_NEXT]] = add i32 [[K]], 1 ; CHECK-NEXT: [[K_NEXT]] = add i32 [[K]], 1
; CHECK-NEXT: br label [[LOOP_3]] ; CHECK-NEXT: br label [[LOOP_3]]
; CHECK: loop_2_backedge:
; CHECK-NEXT: [[J_NEXT]] = add i32 [[J]], 1
; CHECK-NEXT: [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]]
; CHECK-NEXT: br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]]
; CHECK: loop_1_backedge.loopexit: ; CHECK: loop_1_backedge.loopexit:
; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]]
; CHECK: loop_1_backedge.loopexit1:
; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]]
; CHECK: loop_1_backedge:
; CHECK-NEXT: [[I_NEXT]] = add i32 [[I]], 1 ; CHECK-NEXT: [[I_NEXT]] = add i32 [[I]], 1
; CHECK-NEXT: [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]] ; CHECK-NEXT: [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N:%.*]]
; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ] ; CHECK-NEXT: [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE_LOOPEXIT]] ]
; CHECK-NEXT: ret i32 [[I_LCSSA]] ; CHECK-NEXT: ret i32 [[I_LCSSA]]
; ;
preheader: preheader:
br label %loop_1 br label %loop_1
loop_1: loop_1:
%i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ] %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ]
br label %loop_2 br label %loop_2
Show All 24 Linesexit:
ret i32 %i ret i32 %i
} }
define i32 @exit_switch_from_inner_to_grandparent(i1 %cond1, i1 %cond2, i32 %N) { define i32 @exit_switch_from_inner_to_grandparent(i1 %cond1, i1 %cond2, i32 %N) {
; CHECK-LABEL: @exit_switch_from_inner_to_grandparent( ; CHECK-LABEL: @exit_switch_from_inner_to_grandparent(
; CHECK-NEXT: preheader: ; CHECK-NEXT: preheader:
; CHECK-NEXT: br label [[LOOP_1:%.*]] ; CHECK-NEXT: br label [[LOOP_1:%.*]]
; CHECK: loop_1: ; CHECK: loop_1:
; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_NEXT:%.*]], [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] ]
; CHECK-NEXT: br label [[LOOP_2:%.*]]
; CHECK: loop_2:
; CHECK-NEXT: [[J:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[J_NEXT:%.*]], [[LOOP_2_BACKEDGE:%.*]] ]
; CHECK-NEXT: switch i32 0, label [[LOOP_2_SPLIT:%.*]] [
; CHECK-NEXT: i32 1, label [[LOOP_2_BACKEDGE]]
; CHECK-NEXT: ]
; CHECK: loop_2-split:
; CHECK-NEXT: br label [[LOOP_3:%.*]] ; CHECK-NEXT: br label [[LOOP_3:%.*]]
; CHECK: loop_3: ; CHECK: loop_3:
; CHECK-NEXT: [[K:%.*]] = phi i32 [ 0, [[LOOP_2_SPLIT]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ] ; CHECK-NEXT: [[K:%.*]] = phi i32 [ 0, [[LOOP_1]] ], [ [[K_NEXT:%.*]], [[LOOP_3_BACKEDGE:%.*]] ]
; CHECK-NEXT: br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[LOOP_1_BACKEDGE_LOOPEXIT:%.*]] ; CHECK-NEXT: br i1 [[COND1:%.*]], label [[LOOP_3_BACKEDGE]], label [[LOOP_1_BACKEDGE_LOOPEXIT]]
; CHECK: loop_3_backedge: ; CHECK: loop_3_backedge:
; CHECK-NEXT: [[K_NEXT]] = add i32 [[K]], 1 ; CHECK-NEXT: [[K_NEXT]] = add i32 [[K]], 1
; CHECK-NEXT: br label [[LOOP_3]] ; CHECK-NEXT: br label [[LOOP_3]]
; CHECK: loop_2_backedge:
; CHECK-NEXT: [[J_NEXT]] = add i32 [[J]], 1
; CHECK-NEXT: [[C_2:%.*]] = icmp slt i32 [[J_NEXT]], [[N:%.*]]
; CHECK-NEXT: br i1 [[C_2]], label [[LOOP_2]], label [[LOOP_1_BACKEDGE_LOOPEXIT1:%.*]]
; CHECK: loop_1_backedge.loopexit: ; CHECK: loop_1_backedge.loopexit:
; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]]
; CHECK: loop_1_backedge.loopexit1:
; CHECK-NEXT: br label [[LOOP_1_BACKEDGE]]
; CHECK: loop_1_backedge:
; CHECK-NEXT: [[I_NEXT]] = add i32 [[I]], 1 ; CHECK-NEXT: [[I_NEXT]] = add i32 [[I]], 1
; CHECK-NEXT: [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N]] ; CHECK-NEXT: [[C_1:%.*]] = icmp slt i32 [[I_NEXT]], [[N:%.*]]
; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]] ; CHECK-NEXT: br i1 [[C_1]], label [[LOOP_1]], label [[EXIT:%.*]]
; CHECK: exit: ; CHECK: exit:
; CHECK-NEXT: [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE]] ] ; CHECK-NEXT: [[I_LCSSA:%.*]] = phi i32 [ [[I]], [[LOOP_1_BACKEDGE_LOOPEXIT]] ]
; CHECK-NEXT: ret i32 [[I_LCSSA]] ; CHECK-NEXT: ret i32 [[I_LCSSA]]
; ;
preheader: preheader:
br label %loop_1 br label %loop_1
loop_1: loop_1:
%i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ] %i = phi i32 [ 0, %preheader ], [ %i.next, %loop_1_backedge ]
br label %loop_2 br label %loop_2
▲ Show 20 Lines • Show All 1,206 Lines • Show Last 20 Lines

llvm/test/Transforms/LoopSimplifyCFG/lcssa.ll

Show First 20 Lines • Show All 49 Lines • ▼ Show 20 Lines
if.end.8: ; preds = %if.end.7 if.end.8: ; preds = %if.end.7
br label %for.cond br label %for.cond
} }
define void @test_01() { define void @test_01() {
; CHECK-LABEL: @test_01( ; CHECK-LABEL: @test_01(
; CHECK-NEXT: entry: ; CHECK-NEXT: entry:
; CHECK-NEXT: br label [[FOR_COND:%.*]] ; CHECK-NEXT: br label [[FOR_COND:%.*]]
; CHECK: for.cond.loopexit:
; CHECK-NEXT: br label [[FOR_COND]]
; CHECK: for.cond: ; CHECK: for.cond:
; CHECK-NEXT: [[INC41_LCSSA3:%.*]] = phi i16 [ undef, [[FOR_COND_LOOPEXIT:%.*]] ], [ undef, [[ENTRY:%.*]] ] ; CHECK-NEXT: [[INC41_LCSSA3:%.*]] = phi i16 [ undef, [[ENTRY:%.*]] ]
; CHECK-NEXT: switch i32 0, label [[FOR_COND_SPLIT:%.*]] [ ; CHECK-NEXT: br label [[FOR_COND_SPLIT:%.*]]
; CHECK-NEXT: i32 1, label [[FOR_COND_LOOPEXIT]]
; CHECK-NEXT: ]
; CHECK: for.cond-split: ; CHECK: for.cond-split:
; CHECK-NEXT: [[INC41_LCSSA3_LCSSA:%.*]] = phi i16 [ [[INC41_LCSSA3]], [[FOR_COND]] ] ; CHECK-NEXT: [[INC41_LCSSA3_LCSSA:%.*]] = phi i16 [ [[INC41_LCSSA3]], [[FOR_COND]] ]
; CHECK-NEXT: br label [[WHILE_COND:%.*]] ; CHECK-NEXT: br label [[WHILE_COND:%.*]]
; CHECK: while.cond: ; CHECK: while.cond:
; CHECK-NEXT: [[INC41:%.*]] = phi i16 [ [[INC4:%.*]], [[WHILE_COND]] ], [ [[INC41_LCSSA3_LCSSA]], [[FOR_COND_SPLIT]] ] ; CHECK-NEXT: [[INC41:%.*]] = phi i16 [ [[INC4:%.*]], [[WHILE_COND]] ], [ [[INC41_LCSSA3_LCSSA]], [[FOR_COND_SPLIT]] ]
; CHECK-NEXT: [[INC4]] = add nsw i16 [[INC41]], 1 ; CHECK-NEXT: [[INC4]] = add nsw i16 [[INC41]], 1
; CHECK-NEXT: br label [[WHILE_COND]] ; CHECK-NEXT: br label [[WHILE_COND]]
; ;
▲ Show 20 Lines • Show All 84 Lines • Show Last 20 Lines

llvm/test/Transforms/LoopSimplifyCFG/live_block_marking.ll

Show All 11 Lines
; CHECK-NEXT: ] ; CHECK-NEXT: ]
; CHECK: entry-split: ; CHECK: entry-split:
; CHECK-NEXT: br label [[OUTER:%.*]] ; CHECK-NEXT: br label [[OUTER:%.*]]
; CHECK: outer: ; CHECK: outer:
; CHECK-NEXT: br i1 [[C:%.*]], label [[TO_FOLD:%.*]], label [[LATCH:%.*]] ; CHECK-NEXT: br i1 [[C:%.*]], label [[TO_FOLD:%.*]], label [[LATCH:%.*]]
; CHECK: to_fold: ; CHECK: to_fold:
; CHECK-NEXT: br i1 [[C]], label [[LATCH]], label [[INNER_PREHEADER:%.*]] ; CHECK-NEXT: br i1 [[C]], label [[LATCH]], label [[INNER_PREHEADER:%.*]]
; CHECK: inner.preheader: ; CHECK: inner.preheader:
; CHECK-NEXT: br label [[INNER:%.*]]
; CHECK: inner:
; CHECK-NEXT: br i1 false, label [[INNER_LATCH:%.*]], label [[UNDEAD:%.*]]
; CHECK: inner_latch:
; CHECK-NEXT: br i1 true, label [[INNER]], label [[LATCH_LOOPEXIT:%.*]]
; CHECK: undead:
; CHECK-NEXT: br label [[LATCH]]
; CHECK: latch.loopexit:
; CHECK-NEXT: br label [[LATCH]] ; CHECK-NEXT: br label [[LATCH]]
; CHECK: latch: ; CHECK: latch:
; CHECK-NEXT: br label [[OUTER]] ; CHECK-NEXT: br label [[OUTER]]
; CHECK: dead_exit: ; CHECK: dead_exit:
; CHECK-NEXT: ret void ; CHECK-NEXT: ret void
; ;
entry: entry:
Show All 27 Lines

llvm/test/Transforms/LoopSimplifyCFG/update_parents.ll

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; REQUIRES: asserts ; REQUIRES: asserts
; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -loop-simplifycfg -debug-only=loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa 2>&1 < %s | FileCheck %s ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -loop-simplifycfg -debug-only=loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa 2>&1 < %s | FileCheck %s
; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -passes='require<domtree>,loop(simplify-cfg)' -debug-only=loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa 2>&1 < %s | FileCheck %s ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -passes='require<domtree>,loop(simplify-cfg)' -debug-only=loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa 2>&1 < %s | FileCheck %s
; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -loop-simplifycfg -enable-mssa-loop-dependency=true -verify-memoryssa -debug-only=loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa 2>&1 < %s | FileCheck %s ; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -loop-simplifycfg -enable-mssa-loop-dependency=true -verify-memoryssa -debug-only=loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa 2>&1 < %s | FileCheck %s
target triple = "x86_64-unknown-linux-gnu" target triple = "x86_64-unknown-linux-gnu"
define void @test() { define void @test() {
; CHECK-LABEL: @test( ; CHECK-LABEL: @test(
; CHECK-NEXT: br label [[BB1:%.*]] ; CHECK-NEXT: br label [[BB1:%.*]]
; CHECK: bb1.loopexit:
; CHECK-NEXT: br label [[BB1]]
; CHECK: bb1: ; CHECK: bb1:
; CHECK-NEXT: br label [[BB1_SPLIT:%.*]]
; CHECK: bb1-split:
; CHECK-NEXT: br label [[BB2:%.*]] ; CHECK-NEXT: br label [[BB2:%.*]]
; CHECK: bb2.loopexit:
; CHECK-NEXT: br label [[BB2]]
; CHECK: bb2: ; CHECK: bb2:
; CHECK-NEXT: switch i32 0, label [[BB2_SPLIT:%.*]] [ ; CHECK-NEXT: br label [[BB2_SPLIT:%.*]]
; CHECK-NEXT: i32 1, label [[BB1_LOOPEXIT:%.*]]
; CHECK-NEXT: i32 2, label [[BB2_LOOPEXIT:%.*]]
; CHECK-NEXT: ]
; CHECK: bb2-split: ; CHECK: bb2-split:
; CHECK-NEXT: br label [[BB3:%.*]] ; CHECK-NEXT: br label [[BB3:%.*]]
; CHECK: bb3: ; CHECK: bb3:
; CHECK-NEXT: br label [[BB3]] ; CHECK-NEXT: br label [[BB3]]
; ;
br label %bb1 br label %bb1
Show All 14 Lines
bb8: ; preds = %bb6 bb8: ; preds = %bb6
br i1 true, label %bb4, label %bb3 br i1 true, label %bb4, label %bb3
} }
define void @test_many_subloops(i1 %c) { define void @test_many_subloops(i1 %c) {
; CHECK-LABEL: @test_many_subloops( ; CHECK-LABEL: @test_many_subloops(
; CHECK-NEXT: br label [[BB1:%.*]] ; CHECK-NEXT: br label [[BB1:%.*]]
; CHECK: bb1.loopexit:
; CHECK-NEXT: br label [[BB1]]
; CHECK: bb1: ; CHECK: bb1:
; CHECK-NEXT: br label [[BB1_SPLIT:%.*]]
; CHECK: bb1-split:
; CHECK-NEXT: br label [[BB2:%.*]] ; CHECK-NEXT: br label [[BB2:%.*]]
; CHECK: bb2.loopexit:
; CHECK-NEXT: br label [[BB2]]
; CHECK: bb2: ; CHECK: bb2:
; CHECK-NEXT: switch i32 0, label [[BB2_SPLIT:%.*]] [ ; CHECK-NEXT: br label [[BB2_SPLIT:%.*]]
; CHECK-NEXT: i32 1, label [[BB1_LOOPEXIT:%.*]]
; CHECK-NEXT: i32 2, label [[BB2_LOOPEXIT:%.*]]
; CHECK-NEXT: ]
; CHECK: bb2-split: ; CHECK: bb2-split:
; CHECK-NEXT: br label [[BB3:%.*]] ; CHECK-NEXT: br label [[BB3:%.*]]
; CHECK: bb3: ; CHECK: bb3:
; CHECK-NEXT: br label [[BB3]] ; CHECK-NEXT: br label [[BB3]]
; ;
br label %bb1 br label %bb1
▲ Show 20 Lines • Show All 48 Lines • Show Last 20 Lines