1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt -S -lowerswitch -structurizecfg %s -o - | FileCheck %s 3 4; This test have an outer loop containing an inner loop, 5; for which there is an interleaved post-order traversal. 6; 7; This used to produce incorrect code. 8; For example %outer.loop.body used to branched to %inner.loop.end 9; (instead of %inner.loop.header). 10 11define i1 @test_nested(i32 %x, i1 %b1, i1 %b2, i1 %b3) { 12; CHECK-LABEL: @test_nested( 13; CHECK-NEXT: entry: 14; CHECK-NEXT: [[B3_INV:%.*]] = xor i1 [[B3:%.*]], true 15; CHECK-NEXT: br label [[OUTER_LOOP_HEADER:%.*]] 16; CHECK: Flow12: 17; CHECK-NEXT: br i1 [[TMP3:%.*]], label [[EXIT_TRUE:%.*]], label [[FLOW13:%.*]] 18; CHECK: exit.true: 19; CHECK-NEXT: br label [[FLOW13]] 20; CHECK: Flow13: 21; CHECK-NEXT: [[TMP0:%.*]] = phi i1 [ true, [[EXIT_TRUE]] ], [ undef, [[FLOW12:%.*]] ] 22; CHECK-NEXT: br i1 [[TMP2:%.*]], label [[EXIT_FALSE:%.*]], label [[EXIT:%.*]] 23; CHECK: exit.false: 24; CHECK-NEXT: br label [[EXIT]] 25; CHECK: outer.loop.header: 26; CHECK-NEXT: br i1 [[B1:%.*]], label [[OUTER_LOOP_BODY:%.*]], label [[FLOW3:%.*]] 27; CHECK: outer.loop.body: 28; CHECK-NEXT: br label [[INNER_LOOP_HEADER:%.*]] 29; CHECK: Flow3: 30; CHECK-NEXT: [[TMP1:%.*]] = phi i1 [ [[TMP16:%.*]], [[FLOW11:%.*]] ], [ true, [[OUTER_LOOP_HEADER]] ] 31; CHECK-NEXT: [[TMP2]] = phi i1 [ [[TMP12:%.*]], [[FLOW11]] ], [ false, [[OUTER_LOOP_HEADER]] ] 32; CHECK-NEXT: [[TMP3]] = phi i1 [ false, [[FLOW11]] ], [ true, [[OUTER_LOOP_HEADER]] ] 33; CHECK-NEXT: br i1 [[TMP1]], label [[FLOW12]], label [[OUTER_LOOP_HEADER]] 34; CHECK: inner.loop.header: 35; CHECK-NEXT: [[TMP4:%.*]] = phi i1 [ [[TMP8:%.*]], [[FLOW4:%.*]] ], [ false, [[OUTER_LOOP_BODY]] ] 36; CHECK-NEXT: br i1 [[B2:%.*]], label [[INNER_LOOP_BODY:%.*]], label [[FLOW4]] 37; CHECK: Flow6: 38; CHECK-NEXT: [[TMP5:%.*]] = phi i1 [ false, [[INNER_LOOP_LATCH:%.*]] ], [ true, [[LEAFBLOCK:%.*]] ] 39; CHECK-NEXT: br label [[FLOW5:%.*]] 40; CHECK: Flow7: 41; CHECK-NEXT: br i1 [[TMP10:%.*]], label [[INNER_LOOP_END:%.*]], label [[FLOW8:%.*]] 42; CHECK: inner.loop.end: 43; CHECK-NEXT: br label [[FLOW8]] 44; CHECK: inner.loop.body: 45; CHECK-NEXT: br i1 [[B3_INV]], label [[INNER_LOOP_BODY_ELSE:%.*]], label [[FLOW:%.*]] 46; CHECK: inner.loop.body.else: 47; CHECK-NEXT: br label [[FLOW]] 48; CHECK: Flow: 49; CHECK-NEXT: [[TMP6:%.*]] = phi i1 [ false, [[INNER_LOOP_BODY_ELSE]] ], [ true, [[INNER_LOOP_BODY]] ] 50; CHECK-NEXT: br i1 [[TMP6]], label [[INNER_LOOP_BODY_THEN:%.*]], label [[INNER_LOOP_COND:%.*]] 51; CHECK: inner.loop.body.then: 52; CHECK-NEXT: br label [[INNER_LOOP_COND]] 53; CHECK: Flow4: 54; CHECK-NEXT: [[TMP7:%.*]] = phi i1 [ [[TMP17:%.*]], [[FLOW5]] ], [ true, [[INNER_LOOP_HEADER]] ] 55; CHECK-NEXT: [[TMP8]] = phi i1 [ [[TMP18:%.*]], [[FLOW5]] ], [ [[TMP4]], [[INNER_LOOP_HEADER]] ] 56; CHECK-NEXT: [[TMP9:%.*]] = phi i1 [ [[TMP19:%.*]], [[FLOW5]] ], [ false, [[INNER_LOOP_HEADER]] ] 57; CHECK-NEXT: [[TMP10]] = phi i1 [ false, [[FLOW5]] ], [ true, [[INNER_LOOP_HEADER]] ] 58; CHECK-NEXT: br i1 [[TMP7]], label [[FLOW7:%.*]], label [[INNER_LOOP_HEADER]] 59; CHECK: inner.loop.cond: 60; CHECK-NEXT: br label [[NODEBLOCK:%.*]] 61; CHECK: NodeBlock: 62; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i32 [[X:%.*]], 1 63; CHECK-NEXT: br i1 [[PIVOT]], label [[LEAFBLOCK]], label [[FLOW5]] 64; CHECK: Flow8: 65; CHECK-NEXT: [[TMP11:%.*]] = phi i1 [ true, [[INNER_LOOP_END]] ], [ false, [[FLOW7]] ] 66; CHECK-NEXT: br i1 [[TMP9]], label [[LEAFBLOCK1:%.*]], label [[FLOW9:%.*]] 67; CHECK: LeafBlock1: 68; CHECK-NEXT: [[SWITCHLEAF2:%.*]] = icmp eq i32 [[X]], 1 69; CHECK-NEXT: br i1 [[SWITCHLEAF2]], label [[INNER_LOOP_BREAK:%.*]], label [[FLOW10:%.*]] 70; CHECK: LeafBlock: 71; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[X]], 0 72; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[INNER_LOOP_LATCH]], label [[FLOW6:%.*]] 73; CHECK: Flow9: 74; CHECK-NEXT: [[TMP12]] = phi i1 [ [[TMP14:%.*]], [[FLOW10]] ], [ [[TMP8]], [[FLOW8]] ] 75; CHECK-NEXT: [[TMP13:%.*]] = phi i1 [ [[TMP15:%.*]], [[FLOW10]] ], [ [[TMP11]], [[FLOW8]] ] 76; CHECK-NEXT: br i1 [[TMP13]], label [[OUTER_LOOP_CLEANUP:%.*]], label [[FLOW11]] 77; CHECK: inner.loop.break: 78; CHECK-NEXT: br label [[FLOW10]] 79; CHECK: Flow10: 80; CHECK-NEXT: [[TMP14]] = phi i1 [ false, [[INNER_LOOP_BREAK]] ], [ true, [[LEAFBLOCK1]] ] 81; CHECK-NEXT: [[TMP15]] = phi i1 [ true, [[INNER_LOOP_BREAK]] ], [ [[TMP11]], [[LEAFBLOCK1]] ] 82; CHECK-NEXT: br label [[FLOW9]] 83; CHECK: outer.loop.cleanup: 84; CHECK-NEXT: br label [[OUTER_LOOP_LATCH:%.*]] 85; CHECK: Flow11: 86; CHECK-NEXT: [[TMP16]] = phi i1 [ false, [[OUTER_LOOP_LATCH]] ], [ true, [[FLOW9]] ] 87; CHECK-NEXT: br label [[FLOW3]] 88; CHECK: outer.loop.latch: 89; CHECK-NEXT: br label [[FLOW11]] 90; CHECK: Flow5: 91; CHECK-NEXT: [[TMP17]] = phi i1 [ [[TMP5]], [[FLOW6]] ], [ true, [[NODEBLOCK]] ] 92; CHECK-NEXT: [[TMP18]] = phi i1 [ [[TMP5]], [[FLOW6]] ], [ [[TMP4]], [[NODEBLOCK]] ] 93; CHECK-NEXT: [[TMP19]] = phi i1 [ false, [[FLOW6]] ], [ true, [[NODEBLOCK]] ] 94; CHECK-NEXT: br label [[FLOW4]] 95; CHECK: inner.loop.latch: 96; CHECK-NEXT: br label [[FLOW6]] 97; CHECK: exit: 98; CHECK-NEXT: [[R:%.*]] = phi i1 [ [[TMP0]], [[FLOW13]] ], [ false, [[EXIT_FALSE]] ] 99; CHECK-NEXT: ret i1 [[R]] 100; 101entry: 102 br label %outer.loop.header 103 104exit.true: ; preds = %outer.loop.header 105 br label %exit 106 107exit.false: ; preds = %inner.loop.cond 108 br label %exit 109 110outer.loop.header: ; preds = %outer.loop.latch, %entry 111 br i1 %b1, label %outer.loop.body, label %exit.true 112 113outer.loop.body: ; preds = %outer.loop.header 114 br label %inner.loop.header 115 116inner.loop.header: ; preds = %inner.loop.latch, %outer.loop.body 117 br i1 %b2, label %inner.loop.body, label %inner.loop.end 118 119inner.loop.end: ; preds = %inner.loop.header 120 br label %outer.loop.cleanup 121 122inner.loop.body: ; preds = %inner.loop.header 123 br i1 %b3, label %inner.loop.body.then, label %inner.loop.body.else 124 125inner.loop.body.else: ; preds = %inner.loop.body 126 br label %inner.loop.cond 127 128inner.loop.body.then: ; preds = %inner.loop.body 129 br label %inner.loop.cond 130 131inner.loop.cond: ; preds = %inner.loop.body.then, %inner.loop.body.else 132 switch i32 %x, label %exit.false [ 133 i32 0, label %inner.loop.latch 134 i32 1, label %inner.loop.break 135 ] 136 137inner.loop.break: ; preds = %inner.loop.cond 138 br label %outer.loop.cleanup 139 140outer.loop.cleanup: ; preds = %inner.loop.break, %inner.loop.end 141 br label %outer.loop.latch 142 143outer.loop.latch: ; preds = %outer.loop.cleanup 144 br label %outer.loop.header 145 146inner.loop.latch: ; preds = %inner.loop.cond 147 br label %inner.loop.header 148 149exit: ; preds = %exit.false, %exit.true 150 %r = phi i1 [ true, %exit.true ], [ false, %exit.false ] 151 ret i1 %r 152} 153 154; This test checks sibling loops that by default have an 155; interleaved post-order traversal. 156 157define void @test_siblings(i1 %b1, i1 %b2, i1 %b3, i1 %b4, i1 %b5, i1 %b6, i1 %b7, i1 %b8, i1 %b9) { 158; CHECK-LABEL: @test_siblings( 159; CHECK-NEXT: entry: 160; CHECK-NEXT: [[B9_INV:%.*]] = xor i1 [[B9:%.*]], true 161; CHECK-NEXT: [[B6_INV:%.*]] = xor i1 [[B6:%.*]], true 162; CHECK-NEXT: [[B2_INV:%.*]] = xor i1 [[B2:%.*]], true 163; CHECK-NEXT: [[B8_INV:%.*]] = xor i1 [[B8:%.*]], true 164; CHECK-NEXT: [[B5_INV:%.*]] = xor i1 [[B5:%.*]], true 165; CHECK-NEXT: [[B3_INV:%.*]] = xor i1 [[B3:%.*]], true 166; CHECK-NEXT: [[B4_INV:%.*]] = xor i1 [[B4:%.*]], true 167; CHECK-NEXT: [[B1_INV:%.*]] = xor i1 [[B1:%.*]], true 168; CHECK-NEXT: br i1 [[B1_INV]], label [[IF_ELSE:%.*]], label [[FLOW:%.*]] 169; CHECK: if.else: 170; CHECK-NEXT: br label [[FLOW]] 171; CHECK: Flow: 172; CHECK-NEXT: [[TMP0:%.*]] = phi i1 [ [[TMP0]], [[FLOW1:%.*]] ], [ [[B2]], [[IF_ELSE]] ], [ false, [[ENTRY:%.*]] ] 173; CHECK-NEXT: [[TMP1:%.*]] = phi i1 [ [[TMP5:%.*]], [[FLOW1]] ], [ [[B2_INV]], [[IF_ELSE]] ], [ false, [[ENTRY]] ] 174; CHECK-NEXT: [[TMP2:%.*]] = phi i1 [ false, [[FLOW1]] ], [ false, [[IF_ELSE]] ], [ true, [[ENTRY]] ] 175; CHECK-NEXT: br i1 [[TMP2]], label [[LOOP1_HEADER:%.*]], label [[FLOW1]] 176; CHECK: loop1.header: 177; CHECK-NEXT: br i1 [[B3_INV]], label [[LOOP1_BODY:%.*]], label [[FLOW2:%.*]] 178; CHECK: Flow2: 179; CHECK-NEXT: [[TMP3:%.*]] = phi i1 [ true, [[LOOP1_BODY]] ], [ [[TMP1]], [[LOOP1_HEADER]] ] 180; CHECK-NEXT: [[TMP4:%.*]] = phi i1 [ [[B5_INV]], [[LOOP1_BODY]] ], [ [[B3]], [[LOOP1_HEADER]] ] 181; CHECK-NEXT: br i1 [[TMP4]], label [[LOOP1_LATCH:%.*]], label [[FLOW3:%.*]] 182; CHECK: loop1.latch: 183; CHECK-NEXT: br label [[FLOW3]] 184; CHECK: Flow1: 185; CHECK-NEXT: [[TMP5]] = phi i1 [ [[TMP6:%.*]], [[FLOW3]] ], [ [[TMP1]], [[FLOW]] ] 186; CHECK-NEXT: br i1 true, label [[FLOW4:%.*]], label [[FLOW]] 187; CHECK: loop1.body: 188; CHECK-NEXT: br label [[FLOW2]] 189; CHECK: Flow3: 190; CHECK-NEXT: [[TMP6]] = phi i1 [ false, [[LOOP1_LATCH]] ], [ [[TMP3]], [[FLOW2]] ] 191; CHECK-NEXT: br label [[FLOW1]] 192; CHECK: Flow4: 193; CHECK-NEXT: [[TMP7:%.*]] = phi i1 [ false, [[FLOW5:%.*]] ], [ [[TMP5]], [[FLOW1]] ] 194; CHECK-NEXT: br i1 [[TMP7]], label [[LOOP2_HEADER:%.*]], label [[FLOW5]] 195; CHECK: loop2.header: 196; CHECK-NEXT: br i1 [[B6_INV]], label [[LOOP2_BODY:%.*]], label [[FLOW6:%.*]] 197; CHECK: Flow5: 198; CHECK-NEXT: [[TMP8:%.*]] = phi i1 [ [[TMP11:%.*]], [[FLOW7:%.*]] ], [ false, [[FLOW4]] ] 199; CHECK-NEXT: br i1 true, label [[FLOW8:%.*]], label [[FLOW4]] 200; CHECK: loop2.body: 201; CHECK-NEXT: br label [[FLOW6]] 202; CHECK: Flow6: 203; CHECK-NEXT: [[TMP9:%.*]] = phi i1 [ true, [[LOOP2_BODY]] ], [ false, [[LOOP2_HEADER]] ] 204; CHECK-NEXT: [[TMP10:%.*]] = phi i1 [ [[B7:%.*]], [[LOOP2_BODY]] ], [ [[B6]], [[LOOP2_HEADER]] ] 205; CHECK-NEXT: br i1 [[TMP10]], label [[LOOP2_LATCH:%.*]], label [[FLOW7]] 206; CHECK: loop2.latch: 207; CHECK-NEXT: br label [[FLOW7]] 208; CHECK: Flow7: 209; CHECK-NEXT: [[TMP11]] = phi i1 [ false, [[LOOP2_LATCH]] ], [ [[TMP9]], [[FLOW6]] ] 210; CHECK-NEXT: br label [[FLOW5]] 211; CHECK: Flow8: 212; CHECK-NEXT: [[TMP12:%.*]] = phi i1 [ false, [[FLOW10:%.*]] ], [ [[TMP0]], [[FLOW5]] ] 213; CHECK-NEXT: [[TMP13:%.*]] = phi i1 [ false, [[FLOW10]] ], [ [[TMP8]], [[FLOW5]] ] 214; CHECK-NEXT: br i1 [[TMP13]], label [[LOOP3_HEADER:%.*]], label [[FLOW9:%.*]] 215; CHECK: loop3.header: 216; CHECK-NEXT: br label [[FLOW9]] 217; CHECK: Flow9: 218; CHECK-NEXT: [[TMP14:%.*]] = phi i1 [ true, [[LOOP3_HEADER]] ], [ [[TMP12]], [[FLOW8]] ] 219; CHECK-NEXT: br i1 [[TMP14]], label [[LOOP3_LATCH:%.*]], label [[FLOW10]] 220; CHECK: loop3.latch: 221; CHECK-NEXT: br label [[FLOW10]] 222; CHECK: Flow10: 223; CHECK-NEXT: br i1 true, label [[EXIT:%.*]], label [[FLOW8]] 224; CHECK: exit: 225; CHECK-NEXT: ret void 226; 227entry: 228 br i1 %b1, label %loop1.header, label %if.else 229 230if.else: 231 br i1 %b2, label %loop3.latch, label %loop2.header 232 233loop1.header: 234 br i1 %b3, label %loop1.latch, label %loop1.body 235 236loop1.latch: 237 br i1 %b4, label %loop1.header, label %exit 238 239loop1.body: 240 br i1 %b5, label %loop2.header, label %loop1.latch 241 242loop2.header: 243 br i1 %b6, label %loop2.latch, label %loop2.body 244 245loop2.body: 246 br i1 %b7, label %loop2.latch, label %loop3.header 247 248loop2.latch: 249 br i1 %b8, label %loop2.header, label %exit 250 251loop3.header: 252 br label %loop3.latch 253 254loop3.latch: 255 br i1 %b9, label %loop3.header, label %exit 256 257exit: 258 ret void 259} 260