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