1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt -S -dfa-jump-threading %s | FileCheck %s 3 4; These tests check that the DFA jump threading transformation is applied 5; properly to two CFGs. It checks that blocks are cloned, branches are updated, 6; and SSA form is restored. 7define i32 @test1(i32 %num) { 8; CHECK-LABEL: @test1( 9; CHECK-NEXT: entry: 10; CHECK-NEXT: br label [[FOR_BODY:%.*]] 11; CHECK: for.body: 12; CHECK-NEXT: [[COUNT:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ] 13; CHECK-NEXT: [[STATE:%.*]] = phi i32 [ 1, [[ENTRY]] ], [ poison, [[FOR_INC]] ] 14; CHECK-NEXT: switch i32 [[STATE]], label [[FOR_INC_JT1:%.*]] [ 15; CHECK-NEXT: i32 1, label [[CASE1:%.*]] 16; CHECK-NEXT: i32 2, label [[CASE2:%.*]] 17; CHECK-NEXT: ] 18; CHECK: for.body.jt2: 19; CHECK-NEXT: [[COUNT_JT2:%.*]] = phi i32 [ [[INC_JT2:%.*]], [[FOR_INC_JT2:%.*]] ] 20; CHECK-NEXT: [[STATE_JT2:%.*]] = phi i32 [ [[STATE_NEXT_JT2:%.*]], [[FOR_INC_JT2]] ] 21; CHECK-NEXT: br label [[CASE2]] 22; CHECK: for.body.jt1: 23; CHECK-NEXT: [[COUNT_JT1:%.*]] = phi i32 [ [[INC_JT1:%.*]], [[FOR_INC_JT1]] ] 24; CHECK-NEXT: [[STATE_JT1:%.*]] = phi i32 [ [[STATE_NEXT_JT1:%.*]], [[FOR_INC_JT1]] ] 25; CHECK-NEXT: br label [[CASE1]] 26; CHECK: case1: 27; CHECK-NEXT: [[COUNT2:%.*]] = phi i32 [ [[COUNT_JT1]], [[FOR_BODY_JT1:%.*]] ], [ [[COUNT]], [[FOR_BODY]] ] 28; CHECK-NEXT: br label [[FOR_INC_JT2]] 29; CHECK: case2: 30; CHECK-NEXT: [[COUNT1:%.*]] = phi i32 [ [[COUNT_JT2]], [[FOR_BODY_JT2:%.*]] ], [ [[COUNT]], [[FOR_BODY]] ] 31; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[COUNT1]], 50 32; CHECK-NEXT: br i1 [[CMP]], label [[FOR_INC_JT1]], label [[SI_UNFOLD_FALSE:%.*]] 33; CHECK: si.unfold.false: 34; CHECK-NEXT: br label [[FOR_INC_JT2]] 35; CHECK: for.inc: 36; CHECK-NEXT: [[INC]] = add nsw i32 undef, 1 37; CHECK-NEXT: [[CMP_EXIT:%.*]] = icmp slt i32 [[INC]], [[NUM:%.*]] 38; CHECK-NEXT: br i1 [[CMP_EXIT]], label [[FOR_BODY]], label [[FOR_END:%.*]] 39; CHECK: for.inc.jt2: 40; CHECK-NEXT: [[COUNT4:%.*]] = phi i32 [ [[COUNT1]], [[SI_UNFOLD_FALSE]] ], [ [[COUNT2]], [[CASE1]] ] 41; CHECK-NEXT: [[STATE_NEXT_JT2]] = phi i32 [ 2, [[CASE1]] ], [ 2, [[SI_UNFOLD_FALSE]] ] 42; CHECK-NEXT: [[INC_JT2]] = add nsw i32 [[COUNT4]], 1 43; CHECK-NEXT: [[CMP_EXIT_JT2:%.*]] = icmp slt i32 [[INC_JT2]], [[NUM]] 44; CHECK-NEXT: br i1 [[CMP_EXIT_JT2]], label [[FOR_BODY_JT2]], label [[FOR_END]] 45; CHECK: for.inc.jt1: 46; CHECK-NEXT: [[COUNT3:%.*]] = phi i32 [ [[COUNT1]], [[CASE2]] ], [ [[COUNT]], [[FOR_BODY]] ] 47; CHECK-NEXT: [[STATE_NEXT_JT1]] = phi i32 [ 1, [[CASE2]] ], [ 1, [[FOR_BODY]] ] 48; CHECK-NEXT: [[INC_JT1]] = add nsw i32 [[COUNT3]], 1 49; CHECK-NEXT: [[CMP_EXIT_JT1:%.*]] = icmp slt i32 [[INC_JT1]], [[NUM]] 50; CHECK-NEXT: br i1 [[CMP_EXIT_JT1]], label [[FOR_BODY_JT1]], label [[FOR_END]] 51; CHECK: for.end: 52; CHECK-NEXT: ret i32 0 53; 54entry: 55 br label %for.body 56 57for.body: 58 %count = phi i32 [ 0, %entry ], [ %inc, %for.inc ] 59 %state = phi i32 [ 1, %entry ], [ %state.next, %for.inc ] 60 switch i32 %state, label %for.inc [ 61 i32 1, label %case1 62 i32 2, label %case2 63 ] 64 65case1: 66 br label %for.inc 67 68case2: 69 %cmp = icmp eq i32 %count, 50 70 %sel = select i1 %cmp, i32 1, i32 2 71 br label %for.inc 72 73for.inc: 74 %state.next = phi i32 [ %sel, %case2 ], [ 1, %for.body ], [ 2, %case1 ] 75 %inc = add nsw i32 %count, 1 76 %cmp.exit = icmp slt i32 %inc, %num 77 br i1 %cmp.exit, label %for.body, label %for.end 78 79for.end: 80 ret i32 0 81} 82 83 84define i32 @test2(i32 %init) { 85; CHECK-LABEL: @test2( 86; CHECK-NEXT: entry: 87; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[INIT:%.*]], 0 88; CHECK-NEXT: br i1 [[CMP]], label [[LOOP_1:%.*]], label [[SI_UNFOLD_FALSE1:%.*]] 89; CHECK: si.unfold.false: 90; CHECK-NEXT: br label [[LOOP_1]] 91; CHECK: si.unfold.false.jt2: 92; CHECK-NEXT: br label [[LOOP_1_JT2:%.*]] 93; CHECK: si.unfold.false.jt4: 94; CHECK-NEXT: br label [[LOOP_1_JT4:%.*]] 95; CHECK: si.unfold.false1: 96; CHECK-NEXT: br label [[LOOP_1]] 97; CHECK: loop.1: 98; CHECK-NEXT: [[STATE_1:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ undef, [[SI_UNFOLD_FALSE:%.*]] ], [ 2, [[SI_UNFOLD_FALSE1]] ] 99; CHECK-NEXT: br label [[LOOP_2:%.*]] 100; CHECK: loop.1.jt2: 101; CHECK-NEXT: [[STATE_1_JT2:%.*]] = phi i32 [ [[STATE_1_BE_JT2:%.*]], [[SI_UNFOLD_FALSE_JT2:%.*]] ] 102; CHECK-NEXT: br label [[LOOP_2_JT2:%.*]] 103; CHECK: loop.1.jt4: 104; CHECK-NEXT: [[STATE_1_JT4:%.*]] = phi i32 [ [[STATE_1_BE_JT4:%.*]], [[SI_UNFOLD_FALSE_JT4:%.*]] ] 105; CHECK-NEXT: br label [[LOOP_2_JT4:%.*]] 106; CHECK: loop.1.jt1: 107; CHECK-NEXT: [[STATE_1_JT1:%.*]] = phi i32 [ 1, [[LOOP_1_BACKEDGE:%.*]] ], [ 1, [[LOOP_1_BACKEDGE_JT4:%.*]] ], [ 1, [[LOOP_1_BACKEDGE_JT2:%.*]] ] 108; CHECK-NEXT: br label [[LOOP_2_JT1:%.*]] 109; CHECK: loop.2: 110; CHECK-NEXT: [[STATE_2:%.*]] = phi i32 [ [[STATE_1]], [[LOOP_1]] ], [ poison, [[LOOP_2_BACKEDGE:%.*]] ] 111; CHECK-NEXT: br label [[LOOP_3:%.*]] 112; CHECK: loop.2.jt2: 113; CHECK-NEXT: [[STATE_2_JT2:%.*]] = phi i32 [ [[STATE_1_JT2]], [[LOOP_1_JT2]] ] 114; CHECK-NEXT: br label [[LOOP_3_JT2:%.*]] 115; CHECK: loop.2.jt3: 116; CHECK-NEXT: [[STATE_2_JT3:%.*]] = phi i32 [ [[STATE_2_BE_JT3:%.*]], [[LOOP_2_BACKEDGE_JT3:%.*]] ] 117; CHECK-NEXT: br label [[LOOP_3_JT3:%.*]] 118; CHECK: loop.2.jt0: 119; CHECK-NEXT: [[STATE_2_JT0:%.*]] = phi i32 [ [[STATE_2_BE_JT0:%.*]], [[LOOP_2_BACKEDGE_JT0:%.*]] ] 120; CHECK-NEXT: br label [[LOOP_3_JT0:%.*]] 121; CHECK: loop.2.jt4: 122; CHECK-NEXT: [[STATE_2_JT4:%.*]] = phi i32 [ [[STATE_1_JT4]], [[LOOP_1_JT4]] ] 123; CHECK-NEXT: br label [[LOOP_3_JT4:%.*]] 124; CHECK: loop.2.jt1: 125; CHECK-NEXT: [[STATE_2_JT1:%.*]] = phi i32 [ [[STATE_1_JT1]], [[LOOP_1_JT1:%.*]] ] 126; CHECK-NEXT: br label [[LOOP_3_JT1:%.*]] 127; CHECK: loop.3: 128; CHECK-NEXT: [[STATE:%.*]] = phi i32 [ [[STATE_2]], [[LOOP_2]] ] 129; CHECK-NEXT: switch i32 [[STATE]], label [[INFLOOP_I:%.*]] [ 130; CHECK-NEXT: i32 2, label [[CASE2:%.*]] 131; CHECK-NEXT: i32 3, label [[CASE3:%.*]] 132; CHECK-NEXT: i32 4, label [[CASE4:%.*]] 133; CHECK-NEXT: i32 0, label [[CASE0:%.*]] 134; CHECK-NEXT: i32 1, label [[CASE1:%.*]] 135; CHECK-NEXT: ] 136; CHECK: loop.3.jt2: 137; CHECK-NEXT: [[STATE_JT2:%.*]] = phi i32 [ [[STATE_2_JT2]], [[LOOP_2_JT2]] ] 138; CHECK-NEXT: br label [[CASE2]] 139; CHECK: loop.3.jt0: 140; CHECK-NEXT: [[STATE_JT0:%.*]] = phi i32 [ [[STATE_2_JT0]], [[LOOP_2_JT0:%.*]] ] 141; CHECK-NEXT: br label [[CASE0]] 142; CHECK: loop.3.jt4: 143; CHECK-NEXT: [[STATE_JT4:%.*]] = phi i32 [ [[STATE_2_JT4]], [[LOOP_2_JT4]] ] 144; CHECK-NEXT: br label [[CASE4]] 145; CHECK: loop.3.jt1: 146; CHECK-NEXT: [[STATE_JT1:%.*]] = phi i32 [ [[STATE_2_JT1]], [[LOOP_2_JT1]] ] 147; CHECK-NEXT: br label [[CASE1]] 148; CHECK: loop.3.jt3: 149; CHECK-NEXT: [[STATE_JT3:%.*]] = phi i32 [ 3, [[CASE2]] ], [ [[STATE_2_JT3]], [[LOOP_2_JT3:%.*]] ] 150; CHECK-NEXT: br label [[CASE3]] 151; CHECK: case2: 152; CHECK-NEXT: br i1 [[CMP]], label [[LOOP_3_JT3]], label [[LOOP_1_BACKEDGE_JT4]] 153; CHECK: case3: 154; CHECK-NEXT: br i1 [[CMP]], label [[LOOP_2_BACKEDGE_JT0]], label [[CASE4]] 155; CHECK: case4: 156; CHECK-NEXT: br i1 [[CMP]], label [[LOOP_2_BACKEDGE_JT3]], label [[LOOP_1_BACKEDGE_JT2]] 157; CHECK: loop.1.backedge: 158; CHECK-NEXT: br i1 [[CMP]], label [[LOOP_1_JT1]], label [[SI_UNFOLD_FALSE]] 159; CHECK: loop.1.backedge.jt2: 160; CHECK-NEXT: [[STATE_1_BE_JT2]] = phi i32 [ 2, [[CASE4]] ] 161; CHECK-NEXT: br i1 [[CMP]], label [[LOOP_1_JT1]], label [[SI_UNFOLD_FALSE_JT2]] 162; CHECK: loop.1.backedge.jt4: 163; CHECK-NEXT: [[STATE_1_BE_JT4]] = phi i32 [ 4, [[CASE2]] ] 164; CHECK-NEXT: br i1 [[CMP]], label [[LOOP_1_JT1]], label [[SI_UNFOLD_FALSE_JT4]] 165; CHECK: loop.2.backedge: 166; CHECK-NEXT: br label [[LOOP_2]] 167; CHECK: loop.2.backedge.jt3: 168; CHECK-NEXT: [[STATE_2_BE_JT3]] = phi i32 [ 3, [[CASE4]] ] 169; CHECK-NEXT: br label [[LOOP_2_JT3]] 170; CHECK: loop.2.backedge.jt0: 171; CHECK-NEXT: [[STATE_2_BE_JT0]] = phi i32 [ 0, [[CASE3]] ] 172; CHECK-NEXT: br label [[LOOP_2_JT0]] 173; CHECK: case0: 174; CHECK-NEXT: br label [[EXIT:%.*]] 175; CHECK: case1: 176; CHECK-NEXT: br label [[EXIT]] 177; CHECK: infloop.i: 178; CHECK-NEXT: br label [[INFLOOP_I]] 179; CHECK: exit: 180; CHECK-NEXT: ret i32 0 181; 182entry: 183 %cmp = icmp eq i32 %init, 0 184 %sel = select i1 %cmp, i32 0, i32 2 185 br label %loop.1 186 187loop.1: 188 %state.1 = phi i32 [ %sel, %entry ], [ %state.1.be2, %loop.1.backedge ] 189 br label %loop.2 190 191loop.2: 192 %state.2 = phi i32 [ %state.1, %loop.1 ], [ %state.2.be, %loop.2.backedge ] 193 br label %loop.3 194 195loop.3: 196 %state = phi i32 [ %state.2, %loop.2 ], [ 3, %case2 ] 197 switch i32 %state, label %infloop.i [ 198 i32 2, label %case2 199 i32 3, label %case3 200 i32 4, label %case4 201 i32 0, label %case0 202 i32 1, label %case1 203 ] 204 205case2: 206 br i1 %cmp, label %loop.3, label %loop.1.backedge 207 208case3: 209 br i1 %cmp, label %loop.2.backedge, label %case4 210 211case4: 212 br i1 %cmp, label %loop.2.backedge, label %loop.1.backedge 213 214loop.1.backedge: 215 %state.1.be = phi i32 [ 2, %case4 ], [ 4, %case2 ] 216 %state.1.be2 = select i1 %cmp, i32 1, i32 %state.1.be 217 br label %loop.1 218 219loop.2.backedge: 220 %state.2.be = phi i32 [ 3, %case4 ], [ 0, %case3 ] 221 br label %loop.2 222 223case0: 224 br label %exit 225 226case1: 227 br label %exit 228 229infloop.i: 230 br label %infloop.i 231 232exit: 233 ret i32 0 234} 235