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