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 if selects are unfolded properly for jump threading 5; opportunities. There are three different patterns to consider: 6; 1) Both operands are constant and the false branch is unfolded by default 7; 2) One operand is constant and the other is another select to be unfolded. In 8; this case a single select is sunk to a new block to unfold. 9; 3) Both operands are a select, and both should be sunk to new blocks. 10define i32 @test1(i32 %num) { 11; CHECK-LABEL: @test1( 12; CHECK-NEXT: entry: 13; CHECK-NEXT: br label [[FOR_BODY:%.*]] 14; CHECK: for.body: 15; CHECK-NEXT: [[COUNT:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ] 16; CHECK-NEXT: [[STATE:%.*]] = phi i32 [ 1, [[ENTRY]] ], [ poison, [[FOR_INC]] ] 17; CHECK-NEXT: switch i32 [[STATE]], label [[FOR_INC_JT1:%.*]] [ 18; CHECK-NEXT: i32 1, label [[CASE1:%.*]] 19; CHECK-NEXT: i32 2, label [[CASE2:%.*]] 20; CHECK-NEXT: ] 21; CHECK: for.body.jt2: 22; CHECK-NEXT: [[COUNT_JT2:%.*]] = phi i32 [ [[INC_JT2:%.*]], [[FOR_INC_JT2:%.*]] ] 23; CHECK-NEXT: [[STATE_JT2:%.*]] = phi i32 [ [[STATE_NEXT_JT2:%.*]], [[FOR_INC_JT2]] ] 24; CHECK-NEXT: br label [[CASE2]] 25; CHECK: for.body.jt1: 26; CHECK-NEXT: [[COUNT_JT1:%.*]] = phi i32 [ [[INC_JT1:%.*]], [[FOR_INC_JT1]] ] 27; CHECK-NEXT: [[STATE_JT1:%.*]] = phi i32 [ [[STATE_NEXT_JT1:%.*]], [[FOR_INC_JT1]] ] 28; CHECK-NEXT: br label [[CASE1]] 29; CHECK: case1: 30; CHECK-NEXT: [[COUNT2:%.*]] = phi i32 [ [[COUNT_JT1]], [[FOR_BODY_JT1:%.*]] ], [ [[COUNT]], [[FOR_BODY]] ] 31; CHECK-NEXT: br label [[FOR_INC_JT2]] 32; CHECK: case2: 33; CHECK-NEXT: [[COUNT1:%.*]] = phi i32 [ [[COUNT_JT2]], [[FOR_BODY_JT2:%.*]] ], [ [[COUNT]], [[FOR_BODY]] ] 34; CHECK-NEXT: [[CMP:%.*]] = icmp slt i32 [[COUNT1]], 50 35; CHECK-NEXT: br i1 [[CMP]], label [[FOR_INC_JT1]], label [[SI_UNFOLD_FALSE:%.*]] 36; CHECK: si.unfold.false: 37; CHECK-NEXT: br label [[FOR_INC_JT2]] 38; CHECK: for.inc: 39; CHECK-NEXT: [[INC]] = add nsw i32 undef, 1 40; CHECK-NEXT: [[CMP_EXIT:%.*]] = icmp slt i32 [[INC]], [[NUM:%.*]] 41; CHECK-NEXT: br i1 [[CMP_EXIT]], label [[FOR_BODY]], label [[FOR_END:%.*]] 42; CHECK: for.inc.jt2: 43; CHECK-NEXT: [[COUNT4:%.*]] = phi i32 [ [[COUNT1]], [[SI_UNFOLD_FALSE]] ], [ [[COUNT2]], [[CASE1]] ] 44; CHECK-NEXT: [[STATE_NEXT_JT2]] = phi i32 [ 2, [[CASE1]] ], [ 2, [[SI_UNFOLD_FALSE]] ] 45; CHECK-NEXT: [[INC_JT2]] = add nsw i32 [[COUNT4]], 1 46; CHECK-NEXT: [[CMP_EXIT_JT2:%.*]] = icmp slt i32 [[INC_JT2]], [[NUM]] 47; CHECK-NEXT: br i1 [[CMP_EXIT_JT2]], label [[FOR_BODY_JT2]], label [[FOR_END]] 48; CHECK: for.inc.jt1: 49; CHECK-NEXT: [[COUNT3:%.*]] = phi i32 [ [[COUNT1]], [[CASE2]] ], [ [[COUNT]], [[FOR_BODY]] ] 50; CHECK-NEXT: [[STATE_NEXT_JT1]] = phi i32 [ 1, [[CASE2]] ], [ 1, [[FOR_BODY]] ] 51; CHECK-NEXT: [[INC_JT1]] = add nsw i32 [[COUNT3]], 1 52; CHECK-NEXT: [[CMP_EXIT_JT1:%.*]] = icmp slt i32 [[INC_JT1]], [[NUM]] 53; CHECK-NEXT: br i1 [[CMP_EXIT_JT1]], label [[FOR_BODY_JT1]], label [[FOR_END]] 54; CHECK: for.end: 55; CHECK-NEXT: ret i32 0 56; 57entry: 58 br label %for.body 59 60for.body: 61 %count = phi i32 [ 0, %entry ], [ %inc, %for.inc ] 62 %state = phi i32 [ 1, %entry ], [ %state.next, %for.inc ] 63 switch i32 %state, label %for.inc [ 64 i32 1, label %case1 65 i32 2, label %case2 66 ] 67 68case1: 69 br label %for.inc 70 71case2: 72 %cmp = icmp slt i32 %count, 50 73 %sel = select i1 %cmp, i32 1, i32 2 74 br label %for.inc 75 76for.inc: 77 %state.next = phi i32 [ %sel, %case2 ], [ 1, %for.body ], [ 2, %case1 ] 78 %inc = add nsw i32 %count, 1 79 %cmp.exit = icmp slt i32 %inc, %num 80 br i1 %cmp.exit, label %for.body, label %for.end 81 82for.end: 83 ret i32 0 84} 85 86define i32 @test2(i32 %num) { 87; CHECK-LABEL: @test2( 88; CHECK-NEXT: entry: 89; CHECK-NEXT: br label [[FOR_BODY:%.*]] 90; CHECK: for.body: 91; CHECK-NEXT: [[COUNT:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ] 92; CHECK-NEXT: [[STATE:%.*]] = phi i32 [ 1, [[ENTRY]] ], [ poison, [[FOR_INC]] ] 93; CHECK-NEXT: switch i32 [[STATE]], label [[FOR_INC_JT1:%.*]] [ 94; CHECK-NEXT: i32 1, label [[CASE1:%.*]] 95; CHECK-NEXT: i32 2, label [[CASE2:%.*]] 96; CHECK-NEXT: ] 97; CHECK: for.body.jt3: 98; CHECK-NEXT: [[COUNT_JT3:%.*]] = phi i32 [ [[INC_JT3:%.*]], [[FOR_INC_JT3:%.*]] ] 99; CHECK-NEXT: [[STATE_JT3:%.*]] = phi i32 [ [[STATE_NEXT_JT3:%.*]], [[FOR_INC_JT3]] ] 100; CHECK-NEXT: br label [[FOR_INC_JT1]] 101; CHECK: for.body.jt2: 102; CHECK-NEXT: [[COUNT_JT2:%.*]] = phi i32 [ [[INC_JT2:%.*]], [[FOR_INC_JT2:%.*]] ] 103; CHECK-NEXT: [[STATE_JT2:%.*]] = phi i32 [ [[STATE_NEXT_JT2:%.*]], [[FOR_INC_JT2]] ] 104; CHECK-NEXT: br label [[CASE2]] 105; CHECK: for.body.jt1: 106; CHECK-NEXT: [[COUNT_JT1:%.*]] = phi i32 [ [[INC_JT1:%.*]], [[FOR_INC_JT1]] ] 107; CHECK-NEXT: [[STATE_JT1:%.*]] = phi i32 [ [[STATE_NEXT_JT1:%.*]], [[FOR_INC_JT1]] ] 108; CHECK-NEXT: br label [[CASE1]] 109; CHECK: case1: 110; CHECK-NEXT: [[COUNT5:%.*]] = phi i32 [ [[COUNT_JT1]], [[FOR_BODY_JT1:%.*]] ], [ [[COUNT]], [[FOR_BODY]] ] 111; CHECK-NEXT: [[CMP_C1:%.*]] = icmp slt i32 [[COUNT5]], 50 112; CHECK-NEXT: [[CMP2_C1:%.*]] = icmp slt i32 [[COUNT5]], 100 113; CHECK-NEXT: br i1 [[CMP2_C1]], label [[SI_UNFOLD_TRUE:%.*]], label [[FOR_INC_JT3]] 114; CHECK: case2: 115; CHECK-NEXT: [[COUNT3:%.*]] = phi i32 [ [[COUNT_JT2]], [[FOR_BODY_JT2:%.*]] ], [ [[COUNT]], [[FOR_BODY]] ] 116; CHECK-NEXT: [[CMP_C2:%.*]] = icmp slt i32 [[COUNT3]], 50 117; CHECK-NEXT: [[CMP2_C2:%.*]] = icmp sgt i32 [[COUNT3]], 100 118; CHECK-NEXT: br i1 [[CMP2_C2]], label [[FOR_INC_JT3]], label [[SI_UNFOLD_FALSE:%.*]] 119; CHECK: si.unfold.false: 120; CHECK-NEXT: br i1 [[CMP_C2]], label [[FOR_INC_JT1]], label [[SI_UNFOLD_FALSE1:%.*]] 121; CHECK: si.unfold.false1: 122; CHECK-NEXT: br label [[FOR_INC_JT2]] 123; CHECK: si.unfold.true: 124; CHECK-NEXT: br i1 [[CMP_C1]], label [[FOR_INC_JT1]], label [[SI_UNFOLD_FALSE2:%.*]] 125; CHECK: si.unfold.false2: 126; CHECK-NEXT: br label [[FOR_INC_JT2]] 127; CHECK: for.inc: 128; CHECK-NEXT: [[INC]] = add nsw i32 undef, 1 129; CHECK-NEXT: [[CMP_EXIT:%.*]] = icmp slt i32 [[INC]], [[NUM:%.*]] 130; CHECK-NEXT: br i1 [[CMP_EXIT]], label [[FOR_BODY]], label [[FOR_END:%.*]] 131; CHECK: for.inc.jt3: 132; CHECK-NEXT: [[COUNT6:%.*]] = phi i32 [ [[COUNT3]], [[CASE2]] ], [ [[COUNT5]], [[CASE1]] ] 133; CHECK-NEXT: [[STATE_NEXT_JT3]] = phi i32 [ 3, [[CASE1]] ], [ 3, [[CASE2]] ] 134; CHECK-NEXT: [[INC_JT3]] = add nsw i32 [[COUNT6]], 1 135; CHECK-NEXT: [[CMP_EXIT_JT3:%.*]] = icmp slt i32 [[INC_JT3]], [[NUM]] 136; CHECK-NEXT: br i1 [[CMP_EXIT_JT3]], label [[FOR_BODY_JT3:%.*]], label [[FOR_END]] 137; CHECK: for.inc.jt2: 138; CHECK-NEXT: [[COUNT7:%.*]] = phi i32 [ [[COUNT3]], [[SI_UNFOLD_FALSE1]] ], [ [[COUNT5]], [[SI_UNFOLD_FALSE2]] ] 139; CHECK-NEXT: [[STATE_NEXT_JT2]] = phi i32 [ 2, [[SI_UNFOLD_FALSE1]] ], [ 2, [[SI_UNFOLD_FALSE2]] ] 140; CHECK-NEXT: [[INC_JT2]] = add nsw i32 [[COUNT7]], 1 141; CHECK-NEXT: [[CMP_EXIT_JT2:%.*]] = icmp slt i32 [[INC_JT2]], [[NUM]] 142; CHECK-NEXT: br i1 [[CMP_EXIT_JT2]], label [[FOR_BODY_JT2]], label [[FOR_END]] 143; CHECK: for.inc.jt1: 144; CHECK-NEXT: [[COUNT4:%.*]] = phi i32 [ [[COUNT_JT3]], [[FOR_BODY_JT3]] ], [ [[COUNT3]], [[SI_UNFOLD_FALSE]] ], [ [[COUNT5]], [[SI_UNFOLD_TRUE]] ], [ [[COUNT]], [[FOR_BODY]] ] 145; CHECK-NEXT: [[STATE_NEXT_JT1]] = phi i32 [ 1, [[FOR_BODY]] ], [ 1, [[SI_UNFOLD_FALSE]] ], [ 1, [[SI_UNFOLD_TRUE]] ], [ 1, [[FOR_BODY_JT3]] ] 146; CHECK-NEXT: [[INC_JT1]] = add nsw i32 [[COUNT4]], 1 147; CHECK-NEXT: [[CMP_EXIT_JT1:%.*]] = icmp slt i32 [[INC_JT1]], [[NUM]] 148; CHECK-NEXT: br i1 [[CMP_EXIT_JT1]], label [[FOR_BODY_JT1]], label [[FOR_END]] 149; CHECK: for.end: 150; CHECK-NEXT: ret i32 0 151; 152entry: 153 br label %for.body 154 155for.body: 156 %count = phi i32 [ 0, %entry ], [ %inc, %for.inc ] 157 %state = phi i32 [ 1, %entry ], [ %state.next, %for.inc ] 158 switch i32 %state, label %for.inc [ 159 i32 1, label %case1 160 i32 2, label %case2 161 ] 162 163case1: 164 %cmp.c1 = icmp slt i32 %count, 50 165 %cmp2.c1 = icmp slt i32 %count, 100 166 %state1.1 = select i1 %cmp.c1, i32 1, i32 2 167 %state1.2 = select i1 %cmp2.c1, i32 %state1.1, i32 3 168 br label %for.inc 169 170case2: 171 %cmp.c2 = icmp slt i32 %count, 50 172 %cmp2.c2 = icmp sgt i32 %count, 100 173 %state2.1 = select i1 %cmp.c2, i32 1, i32 2 174 %state2.2 = select i1 %cmp2.c2, i32 3, i32 %state2.1 175 br label %for.inc 176 177for.inc: 178 %state.next = phi i32 [ %state1.2, %case1 ], [ %state2.2, %case2 ], [ 1, %for.body ] 179 %inc = add nsw i32 %count, 1 180 %cmp.exit = icmp slt i32 %inc, %num 181 br i1 %cmp.exit, label %for.body, label %for.end 182 183for.end: 184 ret i32 0 185} 186 187define i32 @test3(i32 %num) { 188; CHECK-LABEL: @test3( 189; CHECK-NEXT: entry: 190; CHECK-NEXT: br label [[FOR_BODY:%.*]] 191; CHECK: for.body: 192; CHECK-NEXT: [[COUNT:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_INC:%.*]] ] 193; CHECK-NEXT: [[STATE:%.*]] = phi i32 [ 1, [[ENTRY]] ], [ poison, [[FOR_INC]] ] 194; CHECK-NEXT: switch i32 [[STATE]], label [[FOR_INC_JT1:%.*]] [ 195; CHECK-NEXT: i32 1, label [[CASE1:%.*]] 196; CHECK-NEXT: i32 2, label [[CASE2:%.*]] 197; CHECK-NEXT: ] 198; CHECK: for.body.jt4: 199; CHECK-NEXT: [[COUNT_JT4:%.*]] = phi i32 [ [[INC_JT4:%.*]], [[FOR_INC_JT4:%.*]] ] 200; CHECK-NEXT: [[STATE_JT4:%.*]] = phi i32 [ [[STATE_NEXT_JT4:%.*]], [[FOR_INC_JT4]] ] 201; CHECK-NEXT: br label [[FOR_INC_JT1]] 202; CHECK: for.body.jt3: 203; CHECK-NEXT: [[COUNT_JT3:%.*]] = phi i32 [ [[INC_JT3:%.*]], [[FOR_INC_JT3:%.*]] ] 204; CHECK-NEXT: [[STATE_JT3:%.*]] = phi i32 [ [[STATE_NEXT_JT3:%.*]], [[FOR_INC_JT3]] ] 205; CHECK-NEXT: br label [[FOR_INC_JT1]] 206; CHECK: for.body.jt2: 207; CHECK-NEXT: [[COUNT_JT2:%.*]] = phi i32 [ [[INC_JT2:%.*]], [[FOR_INC_JT2:%.*]] ] 208; CHECK-NEXT: [[STATE_JT2:%.*]] = phi i32 [ [[STATE_NEXT_JT2:%.*]], [[FOR_INC_JT2]] ] 209; CHECK-NEXT: br label [[CASE2]] 210; CHECK: for.body.jt1: 211; CHECK-NEXT: [[COUNT_JT1:%.*]] = phi i32 [ [[INC_JT1:%.*]], [[FOR_INC_JT1]] ] 212; CHECK-NEXT: [[STATE_JT1:%.*]] = phi i32 [ [[STATE_NEXT_JT1:%.*]], [[FOR_INC_JT1]] ] 213; CHECK-NEXT: br label [[CASE1]] 214; CHECK: case1: 215; CHECK-NEXT: [[COUNT5:%.*]] = phi i32 [ [[COUNT_JT1]], [[FOR_BODY_JT1:%.*]] ], [ [[COUNT]], [[FOR_BODY]] ] 216; CHECK-NEXT: br label [[FOR_INC_JT2]] 217; CHECK: case2: 218; CHECK-NEXT: [[COUNT4:%.*]] = phi i32 [ [[COUNT_JT2]], [[FOR_BODY_JT2:%.*]] ], [ [[COUNT]], [[FOR_BODY]] ] 219; CHECK-NEXT: [[CMP_1:%.*]] = icmp slt i32 [[COUNT4]], 50 220; CHECK-NEXT: [[CMP_2:%.*]] = icmp slt i32 [[COUNT4]], 100 221; CHECK-NEXT: [[TMP0:%.*]] = and i32 [[COUNT4]], 1 222; CHECK-NEXT: [[CMP_3:%.*]] = icmp eq i32 [[TMP0]], 0 223; CHECK-NEXT: br i1 [[CMP_3]], label [[SI_UNFOLD_TRUE:%.*]], label [[SI_UNFOLD_FALSE:%.*]] 224; CHECK: si.unfold.true: 225; CHECK-NEXT: br i1 [[CMP_1]], label [[FOR_INC_JT1]], label [[SI_UNFOLD_FALSE2:%.*]] 226; CHECK: si.unfold.false: 227; CHECK-NEXT: br i1 [[CMP_2]], label [[FOR_INC_JT3]], label [[SI_UNFOLD_FALSE1:%.*]] 228; CHECK: si.unfold.false1: 229; CHECK-NEXT: br label [[FOR_INC_JT4]] 230; CHECK: si.unfold.false2: 231; CHECK-NEXT: br label [[FOR_INC_JT2]] 232; CHECK: for.inc: 233; CHECK-NEXT: [[INC]] = add nsw i32 undef, 1 234; CHECK-NEXT: [[CMP_EXIT:%.*]] = icmp slt i32 [[INC]], [[NUM:%.*]] 235; CHECK-NEXT: br i1 [[CMP_EXIT]], label [[FOR_BODY]], label [[FOR_END:%.*]] 236; CHECK: for.inc.jt4: 237; CHECK-NEXT: [[STATE_NEXT_JT4]] = phi i32 [ 4, [[SI_UNFOLD_FALSE1]] ] 238; CHECK-NEXT: [[INC_JT4]] = add nsw i32 [[COUNT4]], 1 239; CHECK-NEXT: [[CMP_EXIT_JT4:%.*]] = icmp slt i32 [[INC_JT4]], [[NUM]] 240; CHECK-NEXT: br i1 [[CMP_EXIT_JT4]], label [[FOR_BODY_JT4:%.*]], label [[FOR_END]] 241; CHECK: for.inc.jt3: 242; CHECK-NEXT: [[STATE_NEXT_JT3]] = phi i32 [ 3, [[SI_UNFOLD_FALSE]] ] 243; CHECK-NEXT: [[INC_JT3]] = add nsw i32 [[COUNT4]], 1 244; CHECK-NEXT: [[CMP_EXIT_JT3:%.*]] = icmp slt i32 [[INC_JT3]], [[NUM]] 245; CHECK-NEXT: br i1 [[CMP_EXIT_JT3]], label [[FOR_BODY_JT3:%.*]], label [[FOR_END]] 246; CHECK: for.inc.jt2: 247; CHECK-NEXT: [[COUNT6:%.*]] = phi i32 [ [[COUNT4]], [[SI_UNFOLD_FALSE2]] ], [ [[COUNT5]], [[CASE1]] ] 248; CHECK-NEXT: [[STATE_NEXT_JT2]] = phi i32 [ 2, [[CASE1]] ], [ 2, [[SI_UNFOLD_FALSE2]] ] 249; CHECK-NEXT: [[INC_JT2]] = add nsw i32 [[COUNT6]], 1 250; CHECK-NEXT: [[CMP_EXIT_JT2:%.*]] = icmp slt i32 [[INC_JT2]], [[NUM]] 251; CHECK-NEXT: br i1 [[CMP_EXIT_JT2]], label [[FOR_BODY_JT2]], label [[FOR_END]] 252; CHECK: for.inc.jt1: 253; CHECK-NEXT: [[COUNT3:%.*]] = phi i32 [ [[COUNT_JT4]], [[FOR_BODY_JT4]] ], [ [[COUNT_JT3]], [[FOR_BODY_JT3]] ], [ [[COUNT4]], [[SI_UNFOLD_TRUE]] ], [ [[COUNT]], [[FOR_BODY]] ] 254; CHECK-NEXT: [[STATE_NEXT_JT1]] = phi i32 [ 1, [[FOR_BODY]] ], [ 1, [[SI_UNFOLD_TRUE]] ], [ 1, [[FOR_BODY_JT3]] ], [ 1, [[FOR_BODY_JT4]] ] 255; CHECK-NEXT: [[INC_JT1]] = add nsw i32 [[COUNT3]], 1 256; CHECK-NEXT: [[CMP_EXIT_JT1:%.*]] = icmp slt i32 [[INC_JT1]], [[NUM]] 257; CHECK-NEXT: br i1 [[CMP_EXIT_JT1]], label [[FOR_BODY_JT1]], label [[FOR_END]] 258; CHECK: for.end: 259; CHECK-NEXT: ret i32 0 260; 261entry: 262 br label %for.body 263 264for.body: 265 %count = phi i32 [ 0, %entry ], [ %inc, %for.inc ] 266 %state = phi i32 [ 1, %entry ], [ %state.next, %for.inc ] 267 switch i32 %state, label %for.inc [ 268 i32 1, label %case1 269 i32 2, label %case2 270 ] 271 272case1: 273 br label %for.inc 274 275case2: 276 %cmp.1 = icmp slt i32 %count, 50 277 %cmp.2 = icmp slt i32 %count, 100 278 %0 = and i32 %count, 1 279 %cmp.3 = icmp eq i32 %0, 0 280 %sel.1 = select i1 %cmp.1, i32 1, i32 2 281 %sel.2 = select i1 %cmp.2, i32 3, i32 4 282 %sel.3 = select i1 %cmp.3, i32 %sel.1, i32 %sel.2 283 br label %for.inc 284 285for.inc: 286 %state.next = phi i32 [ %sel.3, %case2 ], [ 1, %for.body ], [ 2, %case1 ] 287 %inc = add nsw i32 %count, 1 288 %cmp.exit = icmp slt i32 %inc, %num 289 br i1 %cmp.exit, label %for.body, label %for.end 290 291for.end: 292 ret i32 0 293} 294