870 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 52; RUN: opt < %s -passes='fix-irreducible,verify<loops>' -S | FileCheck %s3; RUN: opt < %s -passes='verify<loops>,fix-irreducible,verify<loops>' -S | FileCheck %s4; RUN: opt < %s -passes='print<cycles>' -disable-output 2>&1 | FileCheck %s --check-prefix CYCLES-BEFORE5; RUN: opt < %s -passes='fix-irreducible,print<cycles>' -disable-output 2>&1 | FileCheck %s --check-prefix CYCLES-AFTER6 7; CYCLES-BEFORE: CycleInfo for function: callbr_entry8; CYCLES-BEFORE-NEXT: depth=1: entries(indirect fallthrough)9; CYCLES-AFTER: CycleInfo for function: callbr_entry10; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard) indirect fallthrough11 12; CYCLES-BEFORE-NEXT: CycleInfo for function: callbr_entry_targets_with_phi_nodes13; CYCLES-BEFORE-NEXT: depth=1: entries(block1 block)14; CYCLES-AFTER-NEXT: CycleInfo for function: callbr_entry_targets_with_phi_nodes15; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard) block1 block16 17; CYCLES-BEFORE-NEXT: CycleInfo for function: callbr_entry_multiple_indirect_targets18; CYCLES-BEFORE-NEXT: depth=1: entries(indirect fallthrough)19; CYCLES-AFTER-NEXT: CycleInfo for function: callbr_entry_multiple_indirect_targets20; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard) indirect fallthrough21 22; CYCLES-BEFORE-NEXT: CycleInfo for function: callbr_entry_multiple_indirect_targets123; CYCLES-BEFORE-NEXT: depth=1: entries(indirect1 indirect fallthrough)24; CYCLES-BEFORE-NEXT: depth=2: entries(indirect fallthrough)25; CYCLES-AFTER-NEXT: CycleInfo for function: callbr_entry_multiple_indirect_targets126; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard) indirect1 indirect fallthrough irr.guard1 irr.guard227; CYCLES-AFTER-NEXT: depth=2: entries(irr.guard2) indirect fallthrough28 29; CYCLES-BEFORE-NEXT: CycleInfo for function: callbr_header_no_indirect30; CYCLES-BEFORE-NEXT: depth=1: entries(fallthrough callbr)31; CYCLES-AFTER-NEXT: CycleInfo for function: callbr_header_no_indirect32; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard) fallthrough callbr callbr.target.fallthrough33 34; CYCLES-BEFORE-NEXT: CycleInfo for function: callbr_header35; CYCLES-BEFORE-NEXT: depth=1: entries(fallthrough callbr)36; CYCLES-AFTER-NEXT: CycleInfo for function: callbr_header37; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard) fallthrough callbr callbr.target.fallthrough38 39; CYCLES-BEFORE-NEXT: CycleInfo for function: callbr_header_multiple_indirect_targets40; CYCLES-BEFORE-NEXT: depth=1: entries(fallthrough callbr) indirect141; CYCLES-BEFORE-NEXT: depth=2: entries(callbr) indirect142; CYCLES-AFTER-NEXT: CycleInfo for function: callbr_header_multiple_indirect_targets43; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard) fallthrough callbr indirect1 callbr.target.fallthrough44; CYCLES-AFTER-NEXT: depth=2: entries(callbr) indirect145 46; CYCLES-BEFORE-NEXT: CycleInfo for function: callbr_regular47; CYCLES-BEFORE-NEXT: depth=1: entries(fallthrough2 fallthrough1)48; CYCLES-BEFORE-NEXT: depth=1: entries(indirect2 indirect1)49; CYCLES-BEFORE-NEXT: depth=1: entries(nocallbr2 nocallbr1)50; CYCLES-AFTER-NEXT: CycleInfo for function: callbr_regular51; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard) fallthrough2 fallthrough152; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard1) indirect2 indirect153; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard2) nocallbr2 nocallbr154 55; CYCLES-BEFORE-NEXT: CycleInfo for function: callbr_regular156; CYCLES-BEFORE-NEXT: depth=1: entries(callbr nocallbr)57; CYCLES-AFTER-NEXT: CycleInfo for function: callbr_regular158; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard) callbr nocallbr59 60; CYCLES-BEFORE-NEXT: CycleInfo for function: callbr_regular261; CYCLES-BEFORE-NEXT: depth=1: entries(callbr nocallbr)62; CYCLES-AFTER-NEXT: CycleInfo for function: callbr_regular263; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard) callbr nocallbr64 65; CYCLES-BEFORE-NEXT: CycleInfo for function: callbr_header_and_regular66; CYCLES-BEFORE-NEXT: depth=1: entries(callbr_header) callbr_regular mid67; CYCLES-BEFORE-NEXT: depth=2: entries(callbr_regular mid)68; CYCLES-AFTER-NEXT: CycleInfo for function: callbr_header_and_regular69; CYCLES-AFTER-NEXT: depth=1: entries(callbr_header) callbr_regular mid callbr_header.target.mid callbr_header.target.callbr_regular irr.guard70; CYCLES-AFTER-NEXT: depth=2: entries(irr.guard) callbr_regular mid71 72; CYCLES-BEFORE-NEXT: CycleInfo for function: callbr_only73; CYCLES-BEFORE-NEXT: depth=1: entries(callbr_block callbr_header)74; CYCLES-AFTER-NEXT: CycleInfo for function: callbr_only75; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard) callbr_block callbr_header callbr_header.target.callbr_block76 77; CYCLES-BEFORE-NEXT: CycleInfo for function: entry_multiple_callbr78; CYCLES-BEFORE-NEXT: depth=1: entries(cb2 block block1)79; CYCLES-BEFORE-NEXT: depth=2: entries(block block1)80; CYCLES-AFTER-NEXT: CycleInfo for function: entry_multiple_callbr81; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard) cb2 block block1 irr.guard1 cb2.target.block1 cb2.target.block irr.guard282; CYCLES-AFTER-NEXT: depth=2: entries(irr.guard2) block block183 84; CYCLES-BEFORE-NEXT: CycleInfo for function: callbr_exit_with_separate_entries85; CYCLES-BEFORE-NEXT: depth=1: entries(l2 l1) cb86; CYCLES-BEFORE-NEXT: depth=2: entries(l1 cb)87; CYCLES-AFTER-NEXT: CycleInfo for function: callbr_exit_with_separate_entries88; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard) l2 l1 cb cb.target.l1 irr.guard189; CYCLES-AFTER-NEXT: depth=2: entries(irr.guard1) l1 cb cb.target.l190 91; CYCLES-BEFORE-NEXT: CycleInfo for function: callbr_exit_with_separate_entries192; CYCLES-BEFORE-NEXT: depth=1: entries(loop2 loop1) cb93; CYCLES-AFTER-NEXT: CycleInfo for function: callbr_exit_with_separate_entries194; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard) loop2 loop1 cb cb.target.loop295 96; CYCLES-BEFORE-NEXT: CycleInfo for function: callbr_only_multiple97; CYCLES-BEFORE-NEXT: depth=1: entries(cb3 cb1 cb2)98; CYCLES-BEFORE-NEXT: depth=2: entries(cb1 cb2)99; CYCLES-AFTER-NEXT: CycleInfo for function: callbr_only_multiple100; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard) cb3 cb1 cb2 cb2.target.cb3 cb1.target.cb3 irr.guard1 cb2.target.cb1 cb3.target.cb1 irr.guard2101; CYCLES-AFTER-NEXT: depth=2: entries(irr.guard2) cb1 cb2 cb2.target.cb1102 103; CYCLES-BEFORE-NEXT: CycleInfo for function: callbr_bypass104; CYCLES-BEFORE-NEXT: depth=1: entries(l1 cb) l2105; CYCLES-BEFORE-NEXT: depth=2: entries(cb l2)106; CYCLES-AFTER-NEXT: CycleInfo for function: callbr_bypass107; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard) l1 cb l2 cb.target.l1 irr.guard1108; CYCLES-AFTER-NEXT: depth=2: entries(irr.guard1) cb l2109 110; CYCLES-BEFORE-NEXT: CycleInfo for function: callbr_multiple_with_exit111; CYCLES-BEFORE-NEXT: depth=1: entries(l3 l1 l2)112; CYCLES-BEFORE-NEXT: depth=2: entries(l1 l2)113; CYCLES-AFTER-NEXT: CycleInfo for function: callbr_multiple_with_exit114; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard) l3 l1 l2 irr.guard1 irr.guard2115; CYCLES-AFTER-NEXT: depth=2: entries(irr.guard2) l1 l2116 117; CYCLES-BEFORE-NEXT: CycleInfo for function: callbr_nested118; CYCLES-BEFORE-NEXT: depth=1: entries(bb bh)119; CYCLES-BEFORE-NEXT: depth=1: entries(b h)120; CYCLES-AFTER-NEXT: CycleInfo for function: callbr_nested121; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard) bb bh122; CYCLES-AFTER-NEXT: depth=1: entries(irr.guard1) b h123 124; Fix the irreducible loop in which callbr is the entry (see description at the125; top of FixIrreducible.cpp).126define void @callbr_entry(i1 %c) {127; CHECK-LABEL: define void @callbr_entry(128; CHECK-SAME: i1 [[C:%.*]]) {129; CHECK-NEXT: [[CALLBR:.*:]]130; CHECK-NEXT: callbr void asm "", "!i"()131; CHECK-NEXT: to label %[[CALLBR_TARGET_FALLTHROUGH:.*]] [label %callbr.target.indirect]132; CHECK: [[FALLTHROUGH:.*]]:133; CHECK-NEXT: br i1 [[C]], label %[[IRR_GUARD:.*]], label %[[RET:.*]]134; CHECK: [[INDIRECT:.*]]:135; CHECK-NEXT: br label %[[FALLTHROUGH]]136; CHECK: [[RET]]:137; CHECK-NEXT: ret void138; CHECK: [[CALLBR_TARGET_FALLTHROUGH]]:139; CHECK-NEXT: br label %[[IRR_GUARD]]140; CHECK: [[CALLBR_TARGET_INDIRECT:.*]]:141; CHECK-NEXT: br label %[[IRR_GUARD]]142; CHECK: [[IRR_GUARD]]:143; CHECK-NEXT: [[GUARD_INDIRECT:%.*]] = phi i1 [ true, %[[FALLTHROUGH]] ], [ false, %[[CALLBR_TARGET_FALLTHROUGH]] ], [ true, %[[CALLBR_TARGET_INDIRECT]] ]144; CHECK-NEXT: br i1 [[GUARD_INDIRECT]], label %[[INDIRECT]], label %[[FALLTHROUGH]]145;146callbr:147 callbr void asm "", "!i"() to label %fallthrough [label %indirect]148fallthrough:149 br i1 %c, label %indirect, label %ret150indirect:151 br label %fallthrough152ret:153 ret void154}155 156define i32 @callbr_entry_targets_with_phi_nodes(i1 %c) {157; CHECK-LABEL: define i32 @callbr_entry_targets_with_phi_nodes(158; CHECK-SAME: i1 [[C:%.*]]) {159; CHECK-NEXT: [[ENTRY:.*:]]160; CHECK-NEXT: callbr void asm "", "!i"()161; CHECK-NEXT: to label %[[ENTRY_TARGET_BLOCK:.*]] [label %entry.target.block1]162; CHECK: [[BLOCK:.*]]:163; CHECK-NEXT: [[A:%.*]] = phi i32 [ 1, %[[BLOCK1:.*]] ], [ [[A_MOVED:%.*]], %[[IRR_GUARD:.*]] ]164; CHECK-NEXT: br label %[[IRR_GUARD]]165; CHECK: [[BLOCK1]]:166; CHECK-NEXT: br i1 [[C]], label %[[BLOCK]], label %[[RET:.*]]167; CHECK: [[RET]]:168; CHECK-NEXT: ret i32 [[B_MOVED:%.*]]169; CHECK: [[ENTRY_TARGET_BLOCK]]:170; CHECK-NEXT: br label %[[IRR_GUARD]]171; CHECK: [[ENTRY_TARGET_BLOCK1:.*]]:172; CHECK-NEXT: br label %[[IRR_GUARD]]173; CHECK: [[IRR_GUARD]]:174; CHECK-NEXT: [[A_MOVED]] = phi i32 [ poison, %[[BLOCK]] ], [ 42, %[[ENTRY_TARGET_BLOCK]] ], [ poison, %[[ENTRY_TARGET_BLOCK1]] ]175; CHECK-NEXT: [[B_MOVED]] = phi i32 [ [[A]], %[[BLOCK]] ], [ poison, %[[ENTRY_TARGET_BLOCK]] ], [ 43, %[[ENTRY_TARGET_BLOCK1]] ]176; CHECK-NEXT: [[GUARD_BLOCK1:%.*]] = phi i1 [ true, %[[BLOCK]] ], [ false, %[[ENTRY_TARGET_BLOCK]] ], [ true, %[[ENTRY_TARGET_BLOCK1]] ]177; CHECK-NEXT: br i1 [[GUARD_BLOCK1]], label %[[BLOCK1]], label %[[BLOCK]]178;179entry:180 callbr void asm "", "!i"() to label %block [label %block1]181block:182 %a = phi i32 [42, %entry], [1, %block1]183 br label %block1184block1:185 %b = phi i32 [43, %entry], [%a, %block]186 br i1 %c, label %block, label %ret187ret:188 ret i32 %b189}190 191define void @callbr_entry_multiple_indirect_targets(i1 %c) {192; CHECK-LABEL: define void @callbr_entry_multiple_indirect_targets(193; CHECK-SAME: i1 [[C:%.*]]) {194; CHECK-NEXT: [[CALLBR:.*:]]195; CHECK-NEXT: callbr void asm "", "!i,!i,!i"()196; CHECK-NEXT: to label %[[CALLBR_TARGET_FALLTHROUGH:.*]] [label %[[CALLBR_TARGET_INDIRECT:.*]], label %[[INDIRECT1:.*]], label %indirect2]197; CHECK: [[INDIRECT3:.*]]:198; CHECK-NEXT: br i1 [[C]], label %[[IRR_GUARD:.*]], label %[[RET:.*]]199; CHECK: [[INDIRECT:.*]]:200; CHECK-NEXT: br label %[[INDIRECT3]]201; CHECK: [[INDIRECT1]]:202; CHECK-NEXT: br label %[[IRR_GUARD]]203; CHECK: [[INDIRECT2:.*:]]204; CHECK-NEXT: br label %[[RET]]205; CHECK: [[RET]]:206; CHECK-NEXT: ret void207; CHECK: [[CALLBR_TARGET_FALLTHROUGH]]:208; CHECK-NEXT: br label %[[IRR_GUARD]]209; CHECK: [[CALLBR_TARGET_INDIRECT]]:210; CHECK-NEXT: br label %[[IRR_GUARD]]211; CHECK: [[IRR_GUARD]]:212; CHECK-NEXT: [[GUARD_INDIRECT:%.*]] = phi i1 [ true, %[[INDIRECT3]] ], [ true, %[[INDIRECT1]] ], [ false, %[[CALLBR_TARGET_FALLTHROUGH]] ], [ true, %[[CALLBR_TARGET_INDIRECT]] ]213; CHECK-NEXT: br i1 [[GUARD_INDIRECT]], label %[[INDIRECT]], label %[[INDIRECT3]]214;215callbr:216 callbr void asm "", "!i,!i,!i"() to label %fallthrough [label %indirect, label %indirect1, label %indirect2]217fallthrough:218 br i1 %c, label %indirect, label %ret219indirect:220 br label %fallthrough221indirect1:222 br label %indirect223indirect2:224 br label %ret225ret:226 ret void227}228 229define void @callbr_entry_multiple_indirect_targets1(i1 %c, i1 %d) {230; CHECK-LABEL: define void @callbr_entry_multiple_indirect_targets1(231; CHECK-SAME: i1 [[C:%.*]], i1 [[D:%.*]]) {232; CHECK-NEXT: [[CALLBR:.*:]]233; CHECK-NEXT: callbr void asm "", "!i,!i,!i"()234; CHECK-NEXT: to label %[[CALLBR_TARGET_FALLTHROUGH:.*]] [label %[[CALLBR_TARGET_INDIRECT:.*]], label %[[CALLBR_TARGET_INDIRECT1:.*]], label %indirect2]235; CHECK: [[INDIRECT3:.*]]:236; CHECK-NEXT: br i1 [[C]], label %[[IRR_GUARD2:.*]], label %[[RET:.*]]237; CHECK: [[INDIRECT:.*]]:238; CHECK-NEXT: br i1 [[D]], label %[[INDIRECT3]], label %[[IRR_GUARD:.*]]239; CHECK: [[INDIRECT1:.*]]:240; CHECK-NEXT: br label %[[IRR_GUARD2]]241; CHECK: [[INDIRECT2:.*:]]242; CHECK-NEXT: br label %[[RET]]243; CHECK: [[RET]]:244; CHECK-NEXT: ret void245; CHECK: [[CALLBR_TARGET_FALLTHROUGH]]:246; CHECK-NEXT: br label %[[IRR_GUARD]]247; CHECK: [[CALLBR_TARGET_INDIRECT]]:248; CHECK-NEXT: br label %[[IRR_GUARD]]249; CHECK: [[CALLBR_TARGET_INDIRECT1]]:250; CHECK-NEXT: br label %[[IRR_GUARD]]251; CHECK: [[IRR_GUARD]]:252; CHECK-NEXT: [[GUARD_INDIRECT1:%.*]] = phi i1 [ true, %[[INDIRECT]] ], [ false, %[[CALLBR_TARGET_FALLTHROUGH]] ], [ false, %[[CALLBR_TARGET_INDIRECT]] ], [ true, %[[CALLBR_TARGET_INDIRECT1]] ]253; CHECK-NEXT: [[GUARD_FALLTHROUGH:%.*]] = phi i1 [ false, %[[INDIRECT]] ], [ true, %[[CALLBR_TARGET_FALLTHROUGH]] ], [ false, %[[CALLBR_TARGET_INDIRECT]] ], [ false, %[[CALLBR_TARGET_INDIRECT1]] ]254; CHECK-NEXT: [[GUARD_FALLTHROUGH_INV:%.*]] = xor i1 [[GUARD_FALLTHROUGH]], true255; CHECK-NEXT: br i1 [[GUARD_INDIRECT1]], label %[[INDIRECT1]], label %[[IRR_GUARD1:.*]]256; CHECK: [[IRR_GUARD1]]:257; CHECK-NEXT: br label %[[IRR_GUARD2]]258; CHECK: [[IRR_GUARD2]]:259; CHECK-NEXT: [[GUARD_INDIRECT:%.*]] = phi i1 [ true, %[[INDIRECT3]] ], [ [[GUARD_FALLTHROUGH_INV]], %[[IRR_GUARD1]] ], [ true, %[[INDIRECT1]] ]260; CHECK-NEXT: br i1 [[GUARD_INDIRECT]], label %[[INDIRECT]], label %[[INDIRECT3]]261;262callbr:263 callbr void asm "", "!i,!i,!i"() to label %fallthrough [label %indirect, label %indirect1, label %indirect2]264fallthrough:265 br i1 %c, label %indirect, label %ret266indirect:267 br i1 %d, label %fallthrough, label %indirect1268indirect1:269 br label %indirect270indirect2:271 br label %ret272ret:273 ret void274}275 276; Fix the irreducible loop in which callbr is the header (see the example at the277; top of FixIrreducible.cpp).278define void @callbr_header_no_indirect(i1 %c, i1 %d) {279; CHECK-LABEL: define void @callbr_header_no_indirect(280; CHECK-SAME: i1 [[C:%.*]], i1 [[D:%.*]]) {281; CHECK-NEXT: [[D_INV:%.*]] = xor i1 [[D]], true282; CHECK-NEXT: br label %[[IRR_GUARD:.*]]283; CHECK: [[CALLBR:.*]]:284; CHECK-NEXT: callbr void asm "", ""()285; CHECK-NEXT: to label %[[CALLBR_TARGET_FALLTHROUGH:.*]] []286; CHECK: [[FALLTHROUGH:.*]]:287; CHECK-NEXT: br i1 [[C]], label %[[CALLBR]], label %[[RET:.*]]288; CHECK: [[RET]]:289; CHECK-NEXT: ret void290; CHECK: [[CALLBR_TARGET_FALLTHROUGH]]:291; CHECK-NEXT: br label %[[IRR_GUARD]]292; CHECK: [[IRR_GUARD]]:293; CHECK-NEXT: [[GUARD_FALLTHROUGH:%.*]] = phi i1 [ true, %[[CALLBR_TARGET_FALLTHROUGH]] ], [ [[D_INV]], [[TMP0:%.*]] ]294; CHECK-NEXT: br i1 [[GUARD_FALLTHROUGH]], label %[[FALLTHROUGH]], label %[[CALLBR]]295;296 br i1 %d, label %callbr, label %fallthrough297callbr:298 callbr void asm "", ""() to label %fallthrough []299fallthrough:300 br i1 %c, label %callbr, label %ret301ret:302 ret void303}304 305; Fix the irreducible loop in which callbr is the header.306define void @callbr_header(i1 %c, i1 %d) {307; CHECK-LABEL: define void @callbr_header(308; CHECK-SAME: i1 [[C:%.*]], i1 [[D:%.*]]) {309; CHECK-NEXT: [[D_INV:%.*]] = xor i1 [[D]], true310; CHECK-NEXT: br label %[[IRR_GUARD:.*]]311; CHECK: [[CALLBR:.*]]:312; CHECK-NEXT: callbr void asm "", "!i"()313; CHECK-NEXT: to label %[[CALLBR_TARGET_FALLTHROUGH:.*]] [label %indirect]314; CHECK: [[INDIRECT:.*:]]315; CHECK-NEXT: br label %[[RET:.*]]316; CHECK: [[FALLTHROUGH:.*]]:317; CHECK-NEXT: br i1 [[C]], label %[[CALLBR]], label %[[RET]]318; CHECK: [[RET]]:319; CHECK-NEXT: ret void320; CHECK: [[CALLBR_TARGET_FALLTHROUGH]]:321; CHECK-NEXT: br label %[[IRR_GUARD]]322; CHECK: [[IRR_GUARD]]:323; CHECK-NEXT: [[GUARD_FALLTHROUGH:%.*]] = phi i1 [ true, %[[CALLBR_TARGET_FALLTHROUGH]] ], [ [[D_INV]], [[TMP0:%.*]] ]324; CHECK-NEXT: br i1 [[GUARD_FALLTHROUGH]], label %[[FALLTHROUGH]], label %[[CALLBR]]325;326 br i1 %d, label %callbr, label %fallthrough327callbr:328 callbr void asm "", "!i"() to label %fallthrough [label %indirect]329indirect:330 br label %ret331fallthrough:332 br i1 %c, label %callbr, label %ret333ret:334 ret void335}336 337define void @callbr_header_multiple_indirect_targets(i1 %c, i1 %d) {338; CHECK-LABEL: define void @callbr_header_multiple_indirect_targets(339; CHECK-SAME: i1 [[C:%.*]], i1 [[D:%.*]]) {340; CHECK-NEXT: [[D_INV:%.*]] = xor i1 [[D]], true341; CHECK-NEXT: br label %[[IRR_GUARD:.*]]342; CHECK: [[CALLBR:.*]]:343; CHECK-NEXT: callbr void asm "", "!i,!i"()344; CHECK-NEXT: to label %[[CALLBR_TARGET_FALLTHROUGH:.*]] [label %[[INDIRECT1:.*]], label %indirect1]345; CHECK: [[INDIRECT1]]:346; CHECK-NEXT: br label %[[RET:.*]]347; CHECK: [[INDIRECT2:.*:]]348; CHECK-NEXT: br label %[[CALLBR]]349; CHECK: [[FALLTHROUGH:.*]]:350; CHECK-NEXT: br i1 [[C]], label %[[CALLBR]], label %[[RET]]351; CHECK: [[RET]]:352; CHECK-NEXT: ret void353; CHECK: [[CALLBR_TARGET_FALLTHROUGH]]:354; CHECK-NEXT: br label %[[IRR_GUARD]]355; CHECK: [[IRR_GUARD]]:356; CHECK-NEXT: [[GUARD_FALLTHROUGH:%.*]] = phi i1 [ true, %[[CALLBR_TARGET_FALLTHROUGH]] ], [ [[D_INV]], [[TMP0:%.*]] ]357; CHECK-NEXT: br i1 [[GUARD_FALLTHROUGH]], label %[[FALLTHROUGH]], label %[[CALLBR]]358;359 br i1 %d, label %callbr, label %fallthrough360callbr:361 callbr void asm "", "!i,!i"() to label %fallthrough [label %indirect, label %indirect1]362indirect:363 br label %ret364indirect1:365 br label %callbr366fallthrough:367 br i1 %c, label %callbr, label %ret368ret:369 ret void370}371 372; Fix the three usual irreducible loops (callbr isn't a part of one of them):373; - fallthrough, fallthrough1, fallthrough2374; - indirect, indirect1, indirect2375; - nocallbr, nocallbr1, nocallbr2376define void @callbr_regular(i1 %c, i1 %d) {377; CHECK-LABEL: define void @callbr_regular(378; CHECK-SAME: i1 [[C:%.*]], i1 [[D:%.*]]) {379; CHECK-NEXT: [[C_INV:%.*]] = xor i1 [[C]], true380; CHECK-NEXT: br i1 [[D]], label %[[CALLBR:.*]], label %[[NOCALLBR:.*]]381; CHECK: [[CALLBR]]:382; CHECK-NEXT: callbr void asm "", "!i"()383; CHECK-NEXT: to label %[[FALLTHROUGH:.*]] [label %indirect]384; CHECK: [[FALLTHROUGH]]:385; CHECK-NEXT: br label %[[IRR_GUARD:.*]]386; CHECK: [[FALLTHROUGH1:.*]]:387; CHECK-NEXT: br label %[[IRR_GUARD]]388; CHECK: [[FALLTHROUGH2:.*]]:389; CHECK-NEXT: br i1 [[D]], label %[[FALLTHROUGH1]], label %[[RET:.*]]390; CHECK: [[INDIRECT:.*]]:391; CHECK-NEXT: br label %[[IRR_GUARD1:.*]]392; CHECK: [[INDIRECT1:.*]]:393; CHECK-NEXT: br label %[[IRR_GUARD1]]394; CHECK: [[INDIRECT2:.*]]:395; CHECK-NEXT: br i1 [[D]], label %[[INDIRECT1]], label %[[RET]]396; CHECK: [[NOCALLBR]]:397; CHECK-NEXT: br label %[[IRR_GUARD2:.*]]398; CHECK: [[NOCALLBR1:.*]]:399; CHECK-NEXT: br label %[[IRR_GUARD2]]400; CHECK: [[NOCALLBR2:.*]]:401; CHECK-NEXT: br i1 [[D]], label %[[NOCALLBR1]], label %[[RET]]402; CHECK: [[RET]]:403; CHECK-NEXT: ret void404; CHECK: [[IRR_GUARD]]:405; CHECK-NEXT: [[GUARD_FALLTHROUGH2:%.*]] = phi i1 [ true, %[[FALLTHROUGH1]] ], [ [[C_INV]], %[[FALLTHROUGH]] ]406; CHECK-NEXT: br i1 [[GUARD_FALLTHROUGH2]], label %[[FALLTHROUGH2]], label %[[FALLTHROUGH1]]407; CHECK: [[IRR_GUARD1]]:408; CHECK-NEXT: [[GUARD_INDIRECT2:%.*]] = phi i1 [ true, %[[INDIRECT1]] ], [ [[C_INV]], %[[INDIRECT]] ]409; CHECK-NEXT: br i1 [[GUARD_INDIRECT2]], label %[[INDIRECT2]], label %[[INDIRECT1]]410; CHECK: [[IRR_GUARD2]]:411; CHECK-NEXT: [[GUARD_NOCALLBR2:%.*]] = phi i1 [ true, %[[NOCALLBR1]] ], [ [[C_INV]], %[[NOCALLBR]] ]412; CHECK-NEXT: br i1 [[GUARD_NOCALLBR2]], label %[[NOCALLBR2]], label %[[NOCALLBR1]]413;414 br i1 %d, label %callbr, label %nocallbr415callbr:416 callbr void asm "", "!i"() to label %fallthrough [label %indirect]417fallthrough:418 br i1 %c, label %fallthrough1, label %fallthrough2419fallthrough1:420 br label %fallthrough2421fallthrough2:422 br i1 %d, label %fallthrough1, label %ret423indirect:424 br i1 %c, label %indirect1, label %indirect2425indirect1:426 br label %indirect2427indirect2:428 br i1 %d, label %indirect1, label %ret429nocallbr:430 br i1 %c, label %nocallbr1, label %nocallbr2431nocallbr1:432 br label %nocallbr2433nocallbr2:434 br i1 %d, label %nocallbr1, label %ret435ret:436 ret void437}438 439; Fix an irreducible loop in which callbr is a regular block (neither entry nor440; header). See the example at the top of FixIrreducible.cpp.441define void @callbr_regular1(i1 %c) {442; CHECK-LABEL: define void @callbr_regular1(443; CHECK-SAME: i1 [[C:%.*]]) {444; CHECK-NEXT: [[C_INV:%.*]] = xor i1 [[C]], true445; CHECK-NEXT: br label %[[IRR_GUARD:.*]]446; CHECK: [[NOCALLBR:.*]]:447; CHECK-NEXT: br label %[[IRR_GUARD]]448; CHECK: [[CALLBR:.*]]:449; CHECK-NEXT: callbr void asm "", "!i"()450; CHECK-NEXT: to label %[[RET:.*]] [label %nocallbr]451; CHECK: [[RET]]:452; CHECK-NEXT: ret void453; CHECK: [[IRR_GUARD]]:454; CHECK-NEXT: [[GUARD_CALLBR:%.*]] = phi i1 [ true, %[[NOCALLBR]] ], [ [[C_INV]], [[TMP0:%.*]] ]455; CHECK-NEXT: br i1 [[GUARD_CALLBR]], label %[[CALLBR]], label %[[NOCALLBR]]456;457 br i1 %c, label %nocallbr, label %callbr458nocallbr:459 br label %callbr460callbr:461 callbr void asm "", "!i"() to label %ret [label %nocallbr]462ret:463 ret void464}465 466; Fix an irreducible loop in which callbr is a regular block (neither entry nor467; header). See the example at the top of FixIrreducible.cpp.468define void @callbr_regular2(i1 %c) {469; CHECK-LABEL: define void @callbr_regular2(470; CHECK-SAME: i1 [[C:%.*]]) {471; CHECK-NEXT: [[C_INV:%.*]] = xor i1 [[C]], true472; CHECK-NEXT: br label %[[IRR_GUARD:.*]]473; CHECK: [[NOCALLBR:.*]]:474; CHECK-NEXT: br label %[[IRR_GUARD]]475; CHECK: [[CALLBR:.*]]:476; CHECK-NEXT: callbr void asm "", "!i"()477; CHECK-NEXT: to label %[[NOCALLBR]] [label %ret]478; CHECK: [[RET:.*:]]479; CHECK-NEXT: ret void480; CHECK: [[IRR_GUARD]]:481; CHECK-NEXT: [[GUARD_CALLBR:%.*]] = phi i1 [ true, %[[NOCALLBR]] ], [ [[C_INV]], [[TMP0:%.*]] ]482; CHECK-NEXT: br i1 [[GUARD_CALLBR]], label %[[CALLBR]], label %[[NOCALLBR]]483;484 br i1 %c, label %nocallbr, label %callbr485nocallbr:486 br label %callbr487callbr:488 callbr void asm "", "!i"() to label %nocallbr [label %ret]489ret:490 ret void491}492 493; Fix an irreducible loop with two callbr blocks, one as header and one as regular block.494define void @callbr_header_and_regular(i1 %c) {495; CHECK-LABEL: define void @callbr_header_and_regular(496; CHECK-SAME: i1 [[C:%.*]]) {497; CHECK-NEXT: br label %[[CALLBR_HEADER:.*]]498; CHECK: [[CALLBR_HEADER]]:499; CHECK-NEXT: callbr void asm "", "!i"()500; CHECK-NEXT: to label %[[CALLBR_HEADER_TARGET_MID:.*]] [label %callbr_header.target.callbr_regular]501; CHECK: [[MID:.*]]:502; CHECK-NEXT: br i1 [[C]], label %[[IRR_GUARD:.*]], label %[[RET:.*]]503; CHECK: [[CALLBR_REGULAR:.*]]:504; CHECK-NEXT: callbr void asm "", "!i"()505; CHECK-NEXT: to label %[[CALLBR_HEADER]] [label %mid]506; CHECK: [[RET]]:507; CHECK-NEXT: ret void508; CHECK: [[CALLBR_HEADER_TARGET_MID]]:509; CHECK-NEXT: br label %[[IRR_GUARD]]510; CHECK: [[CALLBR_HEADER_TARGET_CALLBR_REGULAR:.*]]:511; CHECK-NEXT: br label %[[IRR_GUARD]]512; CHECK: [[IRR_GUARD]]:513; CHECK-NEXT: [[GUARD_CALLBR_REGULAR:%.*]] = phi i1 [ true, %[[MID]] ], [ false, %[[CALLBR_HEADER_TARGET_MID]] ], [ true, %[[CALLBR_HEADER_TARGET_CALLBR_REGULAR]] ]514; CHECK-NEXT: br i1 [[GUARD_CALLBR_REGULAR]], label %[[CALLBR_REGULAR]], label %[[MID]]515;516 br label %callbr_header517callbr_header:518 callbr void asm "", "!i"() to label %mid [label %callbr_regular]519mid:520 br i1 %c, label %callbr_regular, label %ret521callbr_regular:522 callbr void asm "", "!i"() to label %callbr_header [label %mid]523ret:524 ret void525}526 527; Fix an irreducible loop consisting only of callbr blocks (and ret). See the528; example at the top of FixIrreducible.cpp.529define void @callbr_only(i1 %c) {530; CHECK-LABEL: define void @callbr_only(531; CHECK-SAME: i1 [[C:%.*]]) {532; CHECK-NEXT: [[CALLBR:.*:]]533; CHECK-NEXT: callbr void asm "", "!i"()534; CHECK-NEXT: to label %[[CALLBR_ENTRY_TARGET_CALLBR_HEADER:.*]] [label %callbr_entry.target.callbr_block]535; CHECK: [[CALLBR_HEADER:.*]]:536; CHECK-NEXT: callbr void asm "", ""()537; CHECK-NEXT: to label %[[CALLBR_HEADER_TARGET_CALLBR_BLOCK:.*]] []538; CHECK: [[CALLBR_BLOCK:.*]]:539; CHECK-NEXT: callbr void asm "", "!i"()540; CHECK-NEXT: to label %[[CALLBR_HEADER]] [label %ret]541; CHECK: [[RET:.*:]]542; CHECK-NEXT: ret void543; CHECK: [[CALLBR_HEADER_TARGET_CALLBR_BLOCK]]:544; CHECK-NEXT: br label %[[IRR_GUARD:.*]]545; CHECK: [[CALLBR_ENTRY_TARGET_CALLBR_HEADER]]:546; CHECK-NEXT: br label %[[IRR_GUARD]]547; CHECK: [[CALLBR_ENTRY_TARGET_CALLBR_BLOCK:.*]]:548; CHECK-NEXT: br label %[[IRR_GUARD]]549; CHECK: [[IRR_GUARD]]:550; CHECK-NEXT: [[GUARD_CALLBR_BLOCK:%.*]] = phi i1 [ true, %[[CALLBR_HEADER_TARGET_CALLBR_BLOCK]] ], [ false, %[[CALLBR_ENTRY_TARGET_CALLBR_HEADER]] ], [ true, %[[CALLBR_ENTRY_TARGET_CALLBR_BLOCK]] ]551; CHECK-NEXT: br i1 [[GUARD_CALLBR_BLOCK]], label %[[CALLBR_BLOCK]], label %[[CALLBR_HEADER]]552;553callbr_entry:554 callbr void asm "", "!i"() to label %callbr_header [label %callbr_block]555callbr_header:556 callbr void asm "", ""() to label %callbr_block []557callbr_block:558 callbr void asm "", "!i"() to label %callbr_header [label %ret]559ret:560 ret void561}562 563; Irreducible loop: entry leading to multiple callbr blocks.564define void @entry_multiple_callbr(i1 %a, i1 %b, i1 %c) {565; CHECK-LABEL: define void @entry_multiple_callbr(566; CHECK-SAME: i1 [[A:%.*]], i1 [[B:%.*]], i1 [[C:%.*]]) {567; CHECK-NEXT: [[ENTRY:.*]]:568; CHECK-NEXT: br i1 [[A]], label %[[CB1:.*]], label %[[IRR_GUARD:.*]]569; CHECK: [[CB1]]:570; CHECK-NEXT: callbr void asm "", "!i,!i"()571; CHECK-NEXT: to label %[[CB1_TARGET_BLOCK:.*]] [label %[[CB1_TARGET_CB2:.*]], label %cb1.target.block1]572; CHECK: [[BLOCK:.*]]:573; CHECK-NEXT: br i1 [[B]], label %[[IRR_GUARD]], label %[[BLOCK1:.*]]574; CHECK: [[CB2:.*]]:575; CHECK-NEXT: callbr void asm "", "!i"()576; CHECK-NEXT: to label %[[CB2_TARGET_BLOCK1:.*]] [label %cb2.target.block]577; CHECK: [[BLOCK1]]:578; CHECK-NEXT: br i1 [[C]], label %[[IRR_GUARD2:.*]], label %[[EXIT:.*]]579; CHECK: [[EXIT]]:580; CHECK-NEXT: ret void581; CHECK: [[CB1_TARGET_BLOCK]]:582; CHECK-NEXT: br label %[[IRR_GUARD]]583; CHECK: [[CB1_TARGET_CB2]]:584; CHECK-NEXT: br label %[[IRR_GUARD]]585; CHECK: [[CB1_TARGET_BLOCK1:.*]]:586; CHECK-NEXT: br label %[[IRR_GUARD]]587; CHECK: [[IRR_GUARD]]:588; CHECK-NEXT: [[GUARD_CB2:%.*]] = phi i1 [ true, %[[BLOCK]] ], [ false, %[[CB1_TARGET_BLOCK]] ], [ true, %[[CB1_TARGET_CB2]] ], [ false, %[[CB1_TARGET_BLOCK1]] ], [ true, %[[ENTRY]] ]589; CHECK-NEXT: [[GUARD_BLOCK:%.*]] = phi i1 [ false, %[[BLOCK]] ], [ true, %[[CB1_TARGET_BLOCK]] ], [ false, %[[CB1_TARGET_CB2]] ], [ false, %[[CB1_TARGET_BLOCK1]] ], [ false, %[[ENTRY]] ]590; CHECK-NEXT: br i1 [[GUARD_CB2]], label %[[CB2]], label %[[IRR_GUARD1:.*]]591; CHECK: [[IRR_GUARD1]]:592; CHECK-NEXT: br label %[[IRR_GUARD2]]593; CHECK: [[CB2_TARGET_BLOCK1]]:594; CHECK-NEXT: br label %[[IRR_GUARD2]]595; CHECK: [[CB2_TARGET_BLOCK:.*]]:596; CHECK-NEXT: br label %[[IRR_GUARD2]]597; CHECK: [[IRR_GUARD2]]:598; CHECK-NEXT: [[GUARD_BLOCK3:%.*]] = phi i1 [ true, %[[BLOCK1]] ], [ [[GUARD_BLOCK]], %[[IRR_GUARD1]] ], [ false, %[[CB2_TARGET_BLOCK1]] ], [ true, %[[CB2_TARGET_BLOCK]] ]599; CHECK-NEXT: br i1 [[GUARD_BLOCK3]], label %[[BLOCK]], label %[[BLOCK1]]600;601entry:602 br i1 %a, label %cb1, label %cb2603cb1:604 callbr void asm "", "!i,!i"() to label %block [label %cb2, label %block1]605block:606 br i1 %b, label %cb2, label %block1607cb2:608 callbr void asm "", "!i"() to label %block1 [label %block]609block1:610 br i1 %c, label %block, label %exit611exit:612 ret void613}614 615; Irreducible loop: callbr as loop exit, with multiple entries616define void @callbr_exit_with_separate_entries(i1 %a, i1 %b, i1 %c) {617; CHECK-LABEL: define void @callbr_exit_with_separate_entries(618; CHECK-SAME: i1 [[A:%.*]], i1 [[B:%.*]], i1 [[C:%.*]]) {619; CHECK-NEXT: [[ENTRY:.*]]:620; CHECK-NEXT: [[C_INV:%.*]] = xor i1 [[C]], true621; CHECK-NEXT: [[A_INV:%.*]] = xor i1 [[A]], true622; CHECK-NEXT: br label %[[IRR_GUARD:.*]]623; CHECK: [[L1:.*]]:624; CHECK-NEXT: br i1 [[B]], label %[[CB:.*]], label %[[IRR_GUARD]]625; CHECK: [[L2:.*]]:626; CHECK-NEXT: br label %[[IRR_GUARD1:.*]]627; CHECK: [[CB]]:628; CHECK-NEXT: callbr void asm "", "!i"()629; CHECK-NEXT: to label %[[EXIT:.*]] [label %cb.target.l1]630; CHECK: [[EXIT]]:631; CHECK-NEXT: ret void632; CHECK: [[IRR_GUARD]]:633; CHECK-NEXT: [[GUARD_L2:%.*]] = phi i1 [ true, %[[L1]] ], [ [[A_INV]], %[[ENTRY]] ]634; CHECK-NEXT: br i1 [[GUARD_L2]], label %[[L2]], label %[[IRR_GUARD1]]635; CHECK: [[CB_TARGET_L1:.*]]:636; CHECK-NEXT: br label %[[IRR_GUARD1]]637; CHECK: [[IRR_GUARD1]]:638; CHECK-NEXT: [[GUARD_L1:%.*]] = phi i1 [ true, %[[CB_TARGET_L1]] ], [ true, %[[IRR_GUARD]] ], [ [[C_INV]], %[[L2]] ]639; CHECK-NEXT: br i1 [[GUARD_L1]], label %[[L1]], label %[[CB]]640;641entry:642 br i1 %a, label %l1, label %l2643l1:644 br i1 %b, label %cb, label %l2645l2:646 br i1 %c, label %cb, label %l1647cb:648 callbr void asm "", "!i"() to label %exit [label %l1]649exit:650 ret void651}652 653define void @callbr_exit_with_separate_entries1(i1 %a, i1 %b) {654; CHECK-LABEL: define void @callbr_exit_with_separate_entries1(655; CHECK-SAME: i1 [[A:%.*]], i1 [[B:%.*]]) {656; CHECK-NEXT: [[ENTRY:.*]]:657; CHECK-NEXT: [[A_INV:%.*]] = xor i1 [[A]], true658; CHECK-NEXT: br label %[[IRR_GUARD:.*]]659; CHECK: [[LOOP1:.*]]:660; CHECK-NEXT: br i1 [[B]], label %[[CB:.*]], label %[[IRR_GUARD]]661; CHECK: [[LOOP2:.*]]:662; CHECK-NEXT: br label %[[LOOP1]]663; CHECK: [[CB]]:664; CHECK-NEXT: callbr void asm "", "!i"()665; CHECK-NEXT: to label %[[EXIT:.*]] [label %cb.target.loop2]666; CHECK: [[EXIT]]:667; CHECK-NEXT: ret void668; CHECK: [[CB_TARGET_LOOP2:.*]]:669; CHECK-NEXT: br label %[[IRR_GUARD]]670; CHECK: [[IRR_GUARD]]:671; CHECK-NEXT: [[GUARD_LOOP2:%.*]] = phi i1 [ true, %[[CB_TARGET_LOOP2]] ], [ true, %[[LOOP1]] ], [ [[A_INV]], %[[ENTRY]] ]672; CHECK-NEXT: br i1 [[GUARD_LOOP2]], label %[[LOOP2]], label %[[LOOP1]]673;674entry:675 br i1 %a, label %loop1, label %loop2676loop1:677 br i1 %b, label %cb, label %loop2678loop2:679 br label %loop1680cb:681 callbr void asm "", "!i"() to label %exit [label %loop2]682exit:683 ret void684}685 686; Irreducible loop: all blocks are callbrs, with cross-edges687define void @callbr_only_multiple(i1 %a, i1 %b, i1 %c) {688; CHECK-LABEL: define void @callbr_only_multiple(689; CHECK-SAME: i1 [[A:%.*]], i1 [[B:%.*]], i1 [[C:%.*]]) {690; CHECK-NEXT: [[ENTRY:.*:]]691; CHECK-NEXT: callbr void asm "", "!i,!i"()692; CHECK-NEXT: to label %[[ENTRY_TARGET_CB1:.*]] [label %[[ENTRY_TARGET_CB2:.*]], label %entry.target.cb3]693; CHECK: [[CB1:.*]]:694; CHECK-NEXT: callbr void asm "", "!i"()695; CHECK-NEXT: to label %[[CB2:.*]] [label %cb1.target.cb3]696; CHECK: [[CB2]]:697; CHECK-NEXT: callbr void asm "", "!i"()698; CHECK-NEXT: to label %[[CB2_TARGET_CB3:.*]] [label %cb2.target.cb1]699; CHECK: [[CB3:.*]]:700; CHECK-NEXT: callbr void asm "", "!i"()701; CHECK-NEXT: to label %[[CB3_TARGET_CB1:.*]] [label %exit]702; CHECK: [[EXIT:.*:]]703; CHECK-NEXT: ret void704; CHECK: [[CB2_TARGET_CB3]]:705; CHECK-NEXT: br label %[[IRR_GUARD:.*]]706; CHECK: [[CB1_TARGET_CB3:.*]]:707; CHECK-NEXT: br label %[[IRR_GUARD]]708; CHECK: [[ENTRY_TARGET_CB1]]:709; CHECK-NEXT: br label %[[IRR_GUARD]]710; CHECK: [[ENTRY_TARGET_CB2]]:711; CHECK-NEXT: br label %[[IRR_GUARD]]712; CHECK: [[ENTRY_TARGET_CB3:.*]]:713; CHECK-NEXT: br label %[[IRR_GUARD]]714; CHECK: [[IRR_GUARD]]:715; CHECK-NEXT: [[GUARD_CB3:%.*]] = phi i1 [ true, %[[CB2_TARGET_CB3]] ], [ true, %[[CB1_TARGET_CB3]] ], [ false, %[[ENTRY_TARGET_CB1]] ], [ false, %[[ENTRY_TARGET_CB2]] ], [ true, %[[ENTRY_TARGET_CB3]] ]716; CHECK-NEXT: [[GUARD_CB1:%.*]] = phi i1 [ false, %[[CB2_TARGET_CB3]] ], [ false, %[[CB1_TARGET_CB3]] ], [ true, %[[ENTRY_TARGET_CB1]] ], [ false, %[[ENTRY_TARGET_CB2]] ], [ false, %[[ENTRY_TARGET_CB3]] ]717; CHECK-NEXT: br i1 [[GUARD_CB3]], label %[[CB3]], label %[[IRR_GUARD1:.*]]718; CHECK: [[IRR_GUARD1]]:719; CHECK-NEXT: br label %[[IRR_GUARD2:.*]]720; CHECK: [[CB2_TARGET_CB1:.*]]:721; CHECK-NEXT: br label %[[IRR_GUARD2]]722; CHECK: [[CB3_TARGET_CB1]]:723; CHECK-NEXT: br label %[[IRR_GUARD2]]724; CHECK: [[IRR_GUARD2]]:725; CHECK-NEXT: [[GUARD_CB13:%.*]] = phi i1 [ true, %[[CB2_TARGET_CB1]] ], [ [[GUARD_CB1]], %[[IRR_GUARD1]] ], [ true, %[[CB3_TARGET_CB1]] ]726; CHECK-NEXT: br i1 [[GUARD_CB13]], label %[[CB1]], label %[[CB2]]727;728entry:729 callbr void asm "", "!i,!i"() to label %cb1 [label %cb2, label %cb3]730cb1:731 callbr void asm "", "!i"() to label %cb2 [label %cb3]732cb2:733 callbr void asm "", "!i"() to label %cb3 [label %cb1]734cb3:735 callbr void asm "", "!i"() to label %cb1 [label %exit]736exit:737 ret void738}739 740; Irreducible loop: callbr as a "bypass" block741define void @callbr_bypass(i1 %a, i1 %b, i1 %c) {742; CHECK-LABEL: define void @callbr_bypass(743; CHECK-SAME: i1 [[A:%.*]], i1 [[B:%.*]], i1 [[C:%.*]]) {744; CHECK-NEXT: [[ENTRY:.*]]:745; CHECK-NEXT: [[B_INV:%.*]] = xor i1 [[B]], true746; CHECK-NEXT: [[A_INV:%.*]] = xor i1 [[A]], true747; CHECK-NEXT: br label %[[IRR_GUARD:.*]]748; CHECK: [[CB:.*]]:749; CHECK-NEXT: callbr void asm "", "!i"()750; CHECK-NEXT: to label %[[L2:.*]] [label %cb.target.l1]751; CHECK: [[L1:.*]]:752; CHECK-NEXT: br label %[[IRR_GUARD1:.*]]753; CHECK: [[L2]]:754; CHECK-NEXT: br i1 [[C]], label %[[IRR_GUARD1]], label %[[EXIT:.*]]755; CHECK: [[EXIT]]:756; CHECK-NEXT: ret void757; CHECK: [[CB_TARGET_L1:.*]]:758; CHECK-NEXT: br label %[[IRR_GUARD]]759; CHECK: [[IRR_GUARD]]:760; CHECK-NEXT: [[GUARD_L1:%.*]] = phi i1 [ true, %[[CB_TARGET_L1]] ], [ [[A_INV]], %[[ENTRY]] ]761; CHECK-NEXT: br i1 [[GUARD_L1]], label %[[L1]], label %[[IRR_GUARD1]]762; CHECK: [[IRR_GUARD1]]:763; CHECK-NEXT: [[GUARD_CB:%.*]] = phi i1 [ true, %[[L2]] ], [ true, %[[IRR_GUARD]] ], [ [[B_INV]], %[[L1]] ]764; CHECK-NEXT: br i1 [[GUARD_CB]], label %[[CB]], label %[[L2]]765;766entry:767 br i1 %a, label %cb, label %l1768cb:769 callbr void asm "", "!i"() to label %l2 [label %l1]770l1:771 br i1 %b, label %l2, label %cb772l2:773 br i1 %c, label %cb, label %exit774exit:775 ret void776}777 778; Irreducible loop: callbr with multiple indirect targets, some looping, some exiting779define void @callbr_multiple_with_exit(i1 %a, i1 %b, i1 %c) {780; CHECK-LABEL: define void @callbr_multiple_with_exit(781; CHECK-SAME: i1 [[A:%.*]], i1 [[B:%.*]], i1 [[C:%.*]]) {782; CHECK-NEXT: [[ENTRY:.*:]]783; CHECK-NEXT: callbr void asm "", "!i,!i,!i"()784; CHECK-NEXT: to label %[[ENTRY_TARGET_L1:.*]] [label %[[ENTRY_TARGET_L2:.*]], label %[[EXIT:.*]], label %entry.target.l3]785; CHECK: [[L1:.*]]:786; CHECK-NEXT: br i1 [[A]], label %[[L2:.*]], label %[[IRR_GUARD:.*]]787; CHECK: [[L2]]:788; CHECK-NEXT: br i1 [[B]], label %[[IRR_GUARD2:.*]], label %[[EXIT]]789; CHECK: [[L3:.*]]:790; CHECK-NEXT: br i1 [[C]], label %[[IRR_GUARD2]], label %[[EXIT]]791; CHECK: [[EXIT]]:792; CHECK-NEXT: ret void793; CHECK: [[ENTRY_TARGET_L1]]:794; CHECK-NEXT: br label %[[IRR_GUARD]]795; CHECK: [[ENTRY_TARGET_L2]]:796; CHECK-NEXT: br label %[[IRR_GUARD]]797; CHECK: [[ENTRY_TARGET_L3:.*]]:798; CHECK-NEXT: br label %[[IRR_GUARD]]799; CHECK: [[IRR_GUARD]]:800; CHECK-NEXT: [[GUARD_L3:%.*]] = phi i1 [ true, %[[L1]] ], [ false, %[[ENTRY_TARGET_L1]] ], [ false, %[[ENTRY_TARGET_L2]] ], [ true, %[[ENTRY_TARGET_L3]] ]801; CHECK-NEXT: [[GUARD_L1:%.*]] = phi i1 [ false, %[[L1]] ], [ true, %[[ENTRY_TARGET_L1]] ], [ false, %[[ENTRY_TARGET_L2]] ], [ false, %[[ENTRY_TARGET_L3]] ]802; CHECK-NEXT: br i1 [[GUARD_L3]], label %[[L3]], label %[[IRR_GUARD1:.*]]803; CHECK: [[IRR_GUARD1]]:804; CHECK-NEXT: br label %[[IRR_GUARD2]]805; CHECK: [[IRR_GUARD2]]:806; CHECK-NEXT: [[GUARD_L13:%.*]] = phi i1 [ true, %[[L2]] ], [ [[GUARD_L1]], %[[IRR_GUARD1]] ], [ true, %[[L3]] ]807; CHECK-NEXT: br i1 [[GUARD_L13]], label %[[L1]], label %[[L2]]808;809entry:810 callbr void asm "", "!i,!i,!i"() to label %l1 [label %l2, label %exit, label %l3]811l1:812 br i1 %a, label %l2, label %l3813l2:814 br i1 %b, label %l1, label %exit815l3:816 br i1 %c, label %l1, label %exit817exit:818 ret void819}820 821define void @callbr_nested(i1 %c, i1 %d) {822; CHECK-LABEL: define void @callbr_nested(823; CHECK-SAME: i1 [[C:%.*]], i1 [[D:%.*]]) {824; CHECK-NEXT: [[ENTRY:.*:]]825; CHECK-NEXT: callbr void asm "", "!i"()826; CHECK-NEXT: to label %[[ENTRY_TARGET_H:.*]] [label %entry.target.b]827; CHECK: [[H:.*]]:828; CHECK-NEXT: br label %[[IRR_GUARD1:.*]]829; CHECK: [[B:.*]]:830; CHECK-NEXT: callbr void asm "", "!i,!i"()831; CHECK-NEXT: to label %[[H]] [label %[[B_TARGET_BH:.*]], label %b.target.bb]832; CHECK: [[BH:.*]]:833; CHECK-NEXT: br label %[[IRR_GUARD:.*]]834; CHECK: [[BB:.*]]:835; CHECK-NEXT: br i1 [[C]], label %[[BH]], label %[[RET:.*]]836; CHECK: [[RET]]:837; CHECK-NEXT: ret void838; CHECK: [[B_TARGET_BH]]:839; CHECK-NEXT: br label %[[IRR_GUARD]]840; CHECK: [[B_TARGET_BB:.*]]:841; CHECK-NEXT: br label %[[IRR_GUARD]]842; CHECK: [[IRR_GUARD]]:843; CHECK-NEXT: [[GUARD_BB:%.*]] = phi i1 [ true, %[[BH]] ], [ false, %[[B_TARGET_BH]] ], [ true, %[[B_TARGET_BB]] ]844; CHECK-NEXT: br i1 [[GUARD_BB]], label %[[BB]], label %[[BH]]845; CHECK: [[ENTRY_TARGET_H]]:846; CHECK-NEXT: br label %[[IRR_GUARD1]]847; CHECK: [[ENTRY_TARGET_B:.*]]:848; CHECK-NEXT: br label %[[IRR_GUARD1]]849; CHECK: [[IRR_GUARD1]]:850; CHECK-NEXT: [[GUARD_B:%.*]] = phi i1 [ true, %[[H]] ], [ false, %[[ENTRY_TARGET_H]] ], [ true, %[[ENTRY_TARGET_B]] ]851; CHECK-NEXT: br i1 [[GUARD_B]], label %[[B]], label %[[H]]852;853entry:854 callbr void asm "","!i"() to label %h [label %b]855h:856 br label %b857b:858 callbr void asm "","!i,!i"() to label %h [label %bh, label %bb]859bh:860 br label %bb861bb:862 br i1 %c, label %bh, label %ret863ret:864 ret void865}866 867;; NOTE: These prefixes are unused and the list is autogenerated. Do not add tests below this line:868; LOOPS-AFTER: {{.*}}869; LOOPS-BEFORE: {{.*}}870