1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt -S -passes=instcombine < %s | FileCheck %s 3 4; 5; Tests to show cases where computeKnownBits should be able to determine 6; the known bits of a phi based on limited recursion. 7; 8 9declare i64 @llvm.ctpop.i64(i64) 10 11 12define i32 @single_entry_phi(i64 %x, i1 %c) { 13; CHECK-LABEL: @single_entry_phi( 14; CHECK-NEXT: entry: 15; CHECK-NEXT: br label [[BODY:%.*]] 16; CHECK: body: 17; CHECK-NEXT: br i1 [[C:%.*]], label [[END:%.*]], label [[BODY]] 18; CHECK: end: 19; CHECK-NEXT: [[Y:%.*]] = call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 [[X:%.*]]) 20; CHECK-NEXT: [[TRUNC:%.*]] = trunc nuw nsw i64 [[Y]] to i32 21; CHECK-NEXT: ret i32 [[TRUNC]] 22; 23entry: 24 %y = call i64 @llvm.ctpop.i64(i64 %x) 25 %trunc = trunc i64 %y to i32 26 br label %body 27body: 28 br i1 %c, label %end, label %body 29end: 30 %phi = phi i32 [ %trunc, %body ] 31 %res = and i32 %phi, 127 32 ret i32 %res 33} 34 35 36define i32 @two_entry_phi_with_constant(i64 %x, i1 %c) { 37; CHECK-LABEL: @two_entry_phi_with_constant( 38; CHECK-NEXT: entry: 39; CHECK-NEXT: [[Y:%.*]] = call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 [[X:%.*]]) 40; CHECK-NEXT: [[TRUNC:%.*]] = trunc nuw nsw i64 [[Y]] to i32 41; CHECK-NEXT: br i1 [[C:%.*]], label [[END:%.*]], label [[BODY:%.*]] 42; CHECK: body: 43; CHECK-NEXT: br label [[END]] 44; CHECK: end: 45; CHECK-NEXT: [[PHI:%.*]] = phi i32 [ [[TRUNC]], [[ENTRY:%.*]] ], [ 255, [[BODY]] ] 46; CHECK-NEXT: [[RES:%.*]] = and i32 [[PHI]], 255 47; CHECK-NEXT: ret i32 [[RES]] 48; 49entry: 50 %y = call i64 @llvm.ctpop.i64(i64 %x) 51 %trunc = trunc i64 %y to i32 52 br i1 %c, label %end, label %body 53body: 54 br label %end 55end: 56 %phi = phi i32 [ %trunc, %entry ], [ 255, %body ] 57 %res = and i32 %phi, 255 58 ret i32 %res 59} 60 61define i32 @two_entry_phi_non_constant(i64 %x, i64 %x2, i1 %c) { 62; CHECK-LABEL: @two_entry_phi_non_constant( 63; CHECK-NEXT: entry: 64; CHECK-NEXT: [[Y:%.*]] = call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 [[X:%.*]]) 65; CHECK-NEXT: [[TRUNC:%.*]] = trunc nuw nsw i64 [[Y]] to i32 66; CHECK-NEXT: br i1 [[C:%.*]], label [[END:%.*]], label [[BODY:%.*]] 67; CHECK: body: 68; CHECK-NEXT: [[Y2:%.*]] = call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 [[X2:%.*]]) 69; CHECK-NEXT: [[TRUNC2:%.*]] = trunc nuw nsw i64 [[Y2]] to i32 70; CHECK-NEXT: br label [[END]] 71; CHECK: end: 72; CHECK-NEXT: [[PHI:%.*]] = phi i32 [ [[TRUNC]], [[ENTRY:%.*]] ], [ [[TRUNC2]], [[BODY]] ] 73; CHECK-NEXT: [[RES:%.*]] = and i32 [[PHI]], 255 74; CHECK-NEXT: ret i32 [[RES]] 75; 76entry: 77 %y = call i64 @llvm.ctpop.i64(i64 %x) 78 %trunc = trunc i64 %y to i32 79 br i1 %c, label %end, label %body 80body: 81 %y2 = call i64 @llvm.ctpop.i64(i64 %x2) 82 %trunc2 = trunc i64 %y2 to i32 83 br label %end 84end: 85 %phi = phi i32 [ %trunc, %entry ], [ %trunc2, %body ] 86 %res = and i32 %phi, 255 87 ret i32 %res 88} 89 90define i32 @neg_many_branches(i64 %x) { 91; CHECK-LABEL: @neg_many_branches( 92; CHECK-NEXT: entry: 93; CHECK-NEXT: [[Y:%.*]] = call range(i64 0, 65) i64 @llvm.ctpop.i64(i64 [[X:%.*]]) 94; CHECK-NEXT: [[TRUNC:%.*]] = trunc nuw nsw i64 [[Y]] to i32 95; CHECK-NEXT: switch i32 [[TRUNC]], label [[END:%.*]] [ 96; CHECK-NEXT: i32 1, label [[ONE:%.*]] 97; CHECK-NEXT: i32 2, label [[TWO:%.*]] 98; CHECK-NEXT: i32 3, label [[THREE:%.*]] 99; CHECK-NEXT: i32 4, label [[FOUR:%.*]] 100; CHECK-NEXT: ] 101; CHECK: one: 102; CHECK-NEXT: [[A:%.*]] = add nuw nsw i32 [[TRUNC]], 1 103; CHECK-NEXT: br label [[END]] 104; CHECK: two: 105; CHECK-NEXT: [[B:%.*]] = add nuw nsw i32 [[TRUNC]], 2 106; CHECK-NEXT: br label [[END]] 107; CHECK: three: 108; CHECK-NEXT: [[C:%.*]] = add nuw nsw i32 [[TRUNC]], 3 109; CHECK-NEXT: br label [[END]] 110; CHECK: four: 111; CHECK-NEXT: [[D:%.*]] = add nuw nsw i32 [[TRUNC]], 4 112; CHECK-NEXT: br label [[END]] 113; CHECK: end: 114; CHECK-NEXT: [[PHI:%.*]] = phi i32 [ [[TRUNC]], [[ENTRY:%.*]] ], [ [[A]], [[ONE]] ], [ [[B]], [[TWO]] ], [ [[C]], [[THREE]] ], [ [[D]], [[FOUR]] ] 115; CHECK-NEXT: [[RES:%.*]] = and i32 [[PHI]], 255 116; CHECK-NEXT: ret i32 [[RES]] 117; 118entry: 119 %y = call i64 @llvm.ctpop.i64(i64 %x) 120 %trunc = trunc i64 %y to i32 121 switch i32 %trunc, label %end [ 122 i32 1, label %one 123 i32 2, label %two 124 i32 3, label %three 125 i32 4, label %four 126 ] 127one: 128 %a = add i32 %trunc, 1 129 br label %end 130two: 131 %b = add i32 %trunc, 2 132 br label %end 133three: 134 %c = add i32 %trunc, 3 135 br label %end 136four: 137 %d = add i32 %trunc, 4 138 br label %end 139end: 140 %phi = phi i32 [ %trunc, %entry ], [ %a, %one ], [ %b, %two ], [ %c, %three ], [ %d, %four ] 141 %res = and i32 %phi, 255 142 ret i32 %res 143} 144 145define i32 @knownbits_phi_select_test1(ptr %p1, ptr %p2, i8 %x) { 146; CHECK-LABEL: @knownbits_phi_select_test1( 147; CHECK-NEXT: entry: 148; CHECK-NEXT: br label [[LOOP:%.*]] 149; CHECK: loop: 150; CHECK-NEXT: [[INDVAR1:%.*]] = phi i8 [ [[LOAD2:%.*]], [[BB2:%.*]] ], [ [[X:%.*]], [[ENTRY:%.*]] ] 151; CHECK-NEXT: [[INDVAR3:%.*]] = phi ptr [ [[INDVAR3_NEXT:%.*]], [[BB2]] ], [ [[P1:%.*]], [[ENTRY]] ] 152; CHECK-NEXT: [[INDVAR4:%.*]] = phi i32 [ [[INDVAR4_NEXT:%.*]], [[BB2]] ], [ 0, [[ENTRY]] ] 153; CHECK-NEXT: [[INDVAR5:%.*]] = phi i32 [ [[INDVAR5_NEXT:%.*]], [[BB2]] ], [ 0, [[ENTRY]] ] 154; CHECK-NEXT: switch i8 [[INDVAR1]], label [[DEFAULT:%.*]] [ 155; CHECK-NEXT: i8 0, label [[EXIT:%.*]] 156; CHECK-NEXT: i8 59, label [[BB1:%.*]] 157; CHECK-NEXT: i8 35, label [[BB1]] 158; CHECK-NEXT: ] 159; CHECK: default: 160; CHECK-NEXT: [[EXT:%.*]] = sext i8 [[INDVAR1]] to i64 161; CHECK-NEXT: [[GEP1:%.*]] = getelementptr inbounds i16, ptr [[P2:%.*]], i64 [[EXT]] 162; CHECK-NEXT: [[LOAD1:%.*]] = load i16, ptr [[GEP1]], align 2 163; CHECK-NEXT: [[MASK:%.*]] = and i16 [[LOAD1]], 8192 164; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i16 [[MASK]], 0 165; CHECK-NEXT: br i1 [[CMP1]], label [[BB2]], label [[BB1]] 166; CHECK: bb1: 167; CHECK-NEXT: [[CMP2:%.*]] = icmp ne i32 [[INDVAR4]], 0 168; CHECK-NEXT: [[CMP3:%.*]] = icmp ne i32 [[INDVAR5]], 0 169; CHECK-NEXT: [[OR_COND:%.*]] = select i1 [[CMP2]], i1 true, i1 [[CMP3]] 170; CHECK-NEXT: br i1 [[OR_COND]], label [[BB2]], label [[EXIT]] 171; CHECK: bb2: 172; CHECK-NEXT: [[CMP4:%.*]] = icmp eq i8 [[INDVAR1]], 39 173; CHECK-NEXT: [[EXT2:%.*]] = zext i1 [[CMP4]] to i32 174; CHECK-NEXT: [[INDVAR4_NEXT]] = xor i32 [[INDVAR4]], [[EXT2]] 175; CHECK-NEXT: [[CMP6:%.*]] = icmp eq i8 [[INDVAR1]], 34 176; CHECK-NEXT: [[EXT3:%.*]] = zext i1 [[CMP6]] to i32 177; CHECK-NEXT: [[INDVAR5_NEXT]] = xor i32 [[INDVAR5]], [[EXT3]] 178; CHECK-NEXT: [[INDVAR3_NEXT]] = getelementptr inbounds nuw i8, ptr [[INDVAR3]], i64 1 179; CHECK-NEXT: [[LOAD2]] = load i8, ptr [[INDVAR3_NEXT]], align 1 180; CHECK-NEXT: br label [[LOOP]] 181; CHECK: exit: 182; CHECK-NEXT: ret i32 [[INDVAR5]] 183; 184entry: 185 br label %loop 186 187loop: 188 %indvar1 = phi i8 [ %load2, %bb2 ], [ %x, %entry ] 189 %indvar2 = phi i64 [ %indvar2.next, %bb2 ], [ 0, %entry ] 190 %indvar3 = phi ptr [ %indvar3.next, %bb2 ], [ %p1, %entry ] 191 %indvar4 = phi i32 [ %indvar4.next, %bb2 ], [ 0, %entry ] 192 %indvar5 = phi i32 [ %indvar5.next, %bb2 ], [ 0, %entry ] 193 switch i8 %indvar1, label %default [ 194 i8 0, label %exit 195 i8 59, label %bb1 196 i8 35, label %bb1 197 ] 198 199default: 200 %ext = sext i8 %indvar1 to i64 201 %gep1 = getelementptr inbounds i16, ptr %p2, i64 %ext 202 %load1 = load i16, ptr %gep1, align 2 203 %mask = and i16 %load1, 8192 204 %cmp1 = icmp eq i16 %mask, 0 205 br i1 %cmp1, label %bb2, label %bb1 206 207bb1: 208 %cmp2 = icmp ne i32 %indvar4, 0 209 %cmp3 = icmp ne i32 %indvar5, 0 210 %or.cond = select i1 %cmp2, i1 true, i1 %cmp3 211 br i1 %or.cond, label %bb2, label %exit 212 213bb2: 214 %cmp4 = icmp eq i8 %indvar1, 39 215 %cmp5 = icmp eq i32 %indvar4, 0 216 %ext2 = zext i1 %cmp5 to i32 217 %indvar4.next = select i1 %cmp4, i32 %ext2, i32 %indvar4 218 %cmp6 = icmp eq i8 %indvar1, 34 219 %cmp7 = icmp eq i32 %indvar5, 0 220 %ext3 = zext i1 %cmp7 to i32 221 %indvar5.next = select i1 %cmp6, i32 %ext3, i32 %indvar5 222 %indvar3.next = getelementptr inbounds i8, ptr %indvar3, i64 1 223 %indvar2.next = add i64 %indvar2, 1 224 %load2 = load i8, ptr %indvar3.next, align 1 225 br label %loop 226 227exit: 228 ret i32 %indvar5 229} 230 231define i8 @knownbits_phi_select_test2() { 232; CHECK-LABEL: @knownbits_phi_select_test2( 233; CHECK-NEXT: entry: 234; CHECK-NEXT: br label [[LOOP:%.*]] 235; CHECK: loop: 236; CHECK-NEXT: [[INDVAR:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[CONTAIN:%.*]], [[LOOP]] ] 237; CHECK-NEXT: [[COND0:%.*]] = call i1 @cond() 238; CHECK-NEXT: [[CONTAIN]] = select i1 [[COND0]], i8 1, i8 [[INDVAR]] 239; CHECK-NEXT: [[COND1:%.*]] = call i1 @cond() 240; CHECK-NEXT: br i1 [[COND1]], label [[EXIT:%.*]], label [[LOOP]] 241; CHECK: exit: 242; CHECK-NEXT: ret i8 [[CONTAIN]] 243; 244entry: 245 br label %loop 246 247loop: 248 %indvar = phi i8 [ 0, %entry ], [ %contain, %loop ] 249 %cond0 = call i1 @cond() 250 %contain = select i1 %cond0, i8 1, i8 %indvar 251 %cond1 = call i1 @cond() 252 br i1 %cond1, label %exit, label %loop 253 254exit: 255 %bool = and i8 %contain, 1 256 ret i8 %bool 257} 258 259define i8 @knownbits_umax_select_test() { 260; CHECK-LABEL: @knownbits_umax_select_test( 261; CHECK-NEXT: entry: 262; CHECK-NEXT: br label [[LOOP:%.*]] 263; CHECK: loop: 264; CHECK-NEXT: [[INDVAR:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[CONTAIN:%.*]], [[LOOP]] ] 265; CHECK-NEXT: [[COND0:%.*]] = call i1 @cond() 266; CHECK-NEXT: [[CONTAIN]] = call i8 @llvm.umax.i8(i8 [[INDVAR]], i8 1) 267; CHECK-NEXT: [[COND1:%.*]] = call i1 @cond() 268; CHECK-NEXT: br i1 [[COND1]], label [[EXIT:%.*]], label [[LOOP]] 269; CHECK: exit: 270; CHECK-NEXT: [[BOOL:%.*]] = and i8 [[CONTAIN]], 1 271; CHECK-NEXT: ret i8 [[BOOL]] 272; 273entry: 274 br label %loop 275 276loop: 277 %indvar = phi i8 [ 0, %entry ], [ %contain, %loop ] 278 %cond0 = call i1 @cond() 279 %contain = call i8 @llvm.umax.i8(i8 1, i8 %indvar) 280 %cond1 = call i1 @cond() 281 br i1 %cond1, label %exit, label %loop 282 283exit: 284 %bool = and i8 %contain, 1 285 ret i8 %bool 286} 287 288define i8 @knownbits_phi_phi_test() { 289; CHECK-LABEL: @knownbits_phi_phi_test( 290; CHECK-NEXT: entry: 291; CHECK-NEXT: br label [[LOOP:%.*]] 292; CHECK: loop: 293; CHECK-NEXT: [[INDVAR:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[CONTAIN:%.*]], [[LOOP_BB1:%.*]] ] 294; CHECK-NEXT: [[COND0:%.*]] = call i1 @cond() 295; CHECK-NEXT: br i1 [[COND0]], label [[LOOP_BB0:%.*]], label [[LOOP_BB1]] 296; CHECK: loop.bb0: 297; CHECK-NEXT: call void @side.effect() 298; CHECK-NEXT: br label [[LOOP_BB1]] 299; CHECK: loop.bb1: 300; CHECK-NEXT: [[CONTAIN]] = phi i8 [ 1, [[LOOP_BB0]] ], [ [[INDVAR]], [[LOOP]] ] 301; CHECK-NEXT: [[COND1:%.*]] = call i1 @cond() 302; CHECK-NEXT: br i1 [[COND1]], label [[EXIT:%.*]], label [[LOOP]] 303; CHECK: exit: 304; CHECK-NEXT: ret i8 [[CONTAIN]] 305; 306entry: 307 br label %loop 308 309loop: 310 %indvar = phi i8 [ 0, %entry ], [ %contain, %loop.bb1 ] 311 %cond0 = call i1 @cond() 312 br i1 %cond0, label %loop.bb0, label %loop.bb1 313loop.bb0: 314 call void @side.effect() 315 br label %loop.bb1 316loop.bb1: 317 %contain = phi i8 [ 1, %loop.bb0 ], [ %indvar, %loop ] 318 %cond1 = call i1 @cond() 319 br i1 %cond1, label %exit, label %loop 320 321exit: 322 %bool = and i8 %contain, 1 323 ret i8 %bool 324} 325 326 327define i1 @known_non_zero_phi_phi_test() { 328; CHECK-LABEL: @known_non_zero_phi_phi_test( 329; CHECK-NEXT: entry: 330; CHECK-NEXT: br label [[LOOP:%.*]] 331; CHECK: loop: 332; CHECK-NEXT: [[INDVAR:%.*]] = phi i8 [ 2, [[ENTRY:%.*]] ], [ [[CONTAIN:%.*]], [[LOOP_BB1:%.*]] ] 333; CHECK-NEXT: [[COND0:%.*]] = call i1 @cond() 334; CHECK-NEXT: br i1 [[COND0]], label [[LOOP_BB0:%.*]], label [[LOOP_BB1]] 335; CHECK: loop.bb0: 336; CHECK-NEXT: call void @side.effect() 337; CHECK-NEXT: br label [[LOOP_BB1]] 338; CHECK: loop.bb1: 339; CHECK-NEXT: [[CONTAIN]] = phi i8 [ 1, [[LOOP_BB0]] ], [ [[INDVAR]], [[LOOP]] ] 340; CHECK-NEXT: [[COND1:%.*]] = call i1 @cond() 341; CHECK-NEXT: br i1 [[COND1]], label [[EXIT:%.*]], label [[LOOP]] 342; CHECK: exit: 343; CHECK-NEXT: [[BOOL:%.*]] = icmp eq i8 [[CONTAIN]], 0 344; CHECK-NEXT: ret i1 [[BOOL]] 345; 346entry: 347 br label %loop 348 349loop: 350 %indvar = phi i8 [ 2, %entry ], [ %contain, %loop.bb1 ] 351 %cond0 = call i1 @cond() 352 br i1 %cond0, label %loop.bb0, label %loop.bb1 353loop.bb0: 354 call void @side.effect() 355 br label %loop.bb1 356loop.bb1: 357 %contain = phi i8 [ 1, %loop.bb0 ], [ %indvar, %loop ] 358 %cond1 = call i1 @cond() 359 br i1 %cond1, label %exit, label %loop 360 361exit: 362 %bool = icmp eq i8 %contain, 0 363 ret i1 %bool 364} 365 366define i1 @known_non_zero_phi_select_test() { 367; CHECK-LABEL: @known_non_zero_phi_select_test( 368; CHECK-NEXT: entry: 369; CHECK-NEXT: br label [[LOOP:%.*]] 370; CHECK: loop: 371; CHECK-NEXT: [[INDVAR:%.*]] = phi i8 [ 2, [[ENTRY:%.*]] ], [ [[CONTAIN:%.*]], [[LOOP]] ] 372; CHECK-NEXT: [[COND0:%.*]] = call i1 @cond() 373; CHECK-NEXT: [[CONTAIN]] = select i1 [[COND0]], i8 1, i8 [[INDVAR]] 374; CHECK-NEXT: [[COND1:%.*]] = call i1 @cond() 375; CHECK-NEXT: br i1 [[COND1]], label [[EXIT:%.*]], label [[LOOP]] 376; CHECK: exit: 377; CHECK-NEXT: [[BOOL:%.*]] = icmp eq i8 [[CONTAIN]], 0 378; CHECK-NEXT: ret i1 [[BOOL]] 379; 380entry: 381 br label %loop 382 383loop: 384 %indvar = phi i8 [ 2, %entry ], [ %contain, %loop ] 385 %cond0 = call i1 @cond() 386 %contain = select i1 %cond0, i8 1, i8 %indvar 387 %cond1 = call i1 @cond() 388 br i1 %cond1, label %exit, label %loop 389 390exit: 391 %bool = icmp eq i8 %contain, 0 392 ret i1 %bool 393} 394 395declare i1 @cond() 396declare void @side.effect() 397 398