395 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt -S -passes=instcombine < %s | FileCheck %s3 4;5; Tests to show cases where computeKnownBits should be able to determine6; 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 i3221; CHECK-NEXT: ret i32 [[TRUNC]]22;23entry:24 %y = call i64 @llvm.ctpop.i64(i64 %x)25 %trunc = trunc i64 %y to i3226 br label %body27body:28 br i1 %c, label %end, label %body29end:30 %phi = phi i32 [ %trunc, %body ]31 %res = and i32 %phi, 12732 ret i32 %res33}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 i3241; 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]], 25547; CHECK-NEXT: ret i32 [[RES]]48;49entry:50 %y = call i64 @llvm.ctpop.i64(i64 %x)51 %trunc = trunc i64 %y to i3252 br i1 %c, label %end, label %body53body:54 br label %end55end:56 %phi = phi i32 [ %trunc, %entry ], [ 255, %body ]57 %res = and i32 %phi, 25558 ret i32 %res59}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 i3266; 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 i3270; 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]], 25574; CHECK-NEXT: ret i32 [[RES]]75;76entry:77 %y = call i64 @llvm.ctpop.i64(i64 %x)78 %trunc = trunc i64 %y to i3279 br i1 %c, label %end, label %body80body:81 %y2 = call i64 @llvm.ctpop.i64(i64 %x2)82 %trunc2 = trunc i64 %y2 to i3283 br label %end84end:85 %phi = phi i32 [ %trunc, %entry ], [ %trunc2, %body ]86 %res = and i32 %phi, 25587 ret i32 %res88}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 i3295; 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]], 1103; CHECK-NEXT: br label [[END]]104; CHECK: two:105; CHECK-NEXT: [[B:%.*]] = add nuw nsw i32 [[TRUNC]], 2106; CHECK-NEXT: br label [[END]]107; CHECK: three:108; CHECK-NEXT: [[C:%.*]] = add nuw nsw i32 [[TRUNC]], 3109; CHECK-NEXT: br label [[END]]110; CHECK: four:111; CHECK-NEXT: [[D:%.*]] = add nuw nsw i32 [[TRUNC]], 4112; 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]], 255116; CHECK-NEXT: ret i32 [[RES]]117;118entry:119 %y = call i64 @llvm.ctpop.i64(i64 %x)120 %trunc = trunc i64 %y to i32121 switch i32 %trunc, label %end [122 i32 1, label %one123 i32 2, label %two124 i32 3, label %three125 i32 4, label %four126 ]127one:128 %a = add i32 %trunc, 1129 br label %end130two:131 %b = add i32 %trunc, 2132 br label %end133three:134 %c = add i32 %trunc, 3135 br label %end136four:137 %d = add i32 %trunc, 4138 br label %end139end:140 %phi = phi i32 [ %trunc, %entry ], [ %a, %one ], [ %b, %two ], [ %c, %three ], [ %d, %four ]141 %res = and i32 %phi, 255142 ret i32 %res143}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 i64161; CHECK-NEXT: [[GEP1:%.*]] = getelementptr inbounds i16, ptr [[P2:%.*]], i64 [[EXT]]162; CHECK-NEXT: [[LOAD1:%.*]] = load i16, ptr [[GEP1]], align 2163; CHECK-NEXT: [[MASK:%.*]] = and i16 [[LOAD1]], 8192164; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i16 [[MASK]], 0165; CHECK-NEXT: br i1 [[CMP1]], label [[BB2]], label [[BB1]]166; CHECK: bb1:167; CHECK-NEXT: [[CMP2:%.*]] = icmp ne i32 [[INDVAR4]], 0168; CHECK-NEXT: [[CMP3:%.*]] = icmp ne i32 [[INDVAR5]], 0169; 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]], 39173; CHECK-NEXT: [[EXT2:%.*]] = zext i1 [[CMP4]] to i32174; CHECK-NEXT: [[INDVAR4_NEXT]] = xor i32 [[INDVAR4]], [[EXT2]]175; CHECK-NEXT: [[CMP6:%.*]] = icmp eq i8 [[INDVAR1]], 34176; CHECK-NEXT: [[EXT3:%.*]] = zext i1 [[CMP6]] to i32177; CHECK-NEXT: [[INDVAR5_NEXT]] = xor i32 [[INDVAR5]], [[EXT3]]178; CHECK-NEXT: [[INDVAR3_NEXT]] = getelementptr inbounds nuw i8, ptr [[INDVAR3]], i64 1179; CHECK-NEXT: [[LOAD2]] = load i8, ptr [[INDVAR3_NEXT]], align 1180; CHECK-NEXT: br label [[LOOP]]181; CHECK: exit:182; CHECK-NEXT: ret i32 [[INDVAR5]]183;184entry:185 br label %loop186 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 %exit195 i8 59, label %bb1196 i8 35, label %bb1197 ]198 199default:200 %ext = sext i8 %indvar1 to i64201 %gep1 = getelementptr inbounds i16, ptr %p2, i64 %ext202 %load1 = load i16, ptr %gep1, align 2203 %mask = and i16 %load1, 8192204 %cmp1 = icmp eq i16 %mask, 0205 br i1 %cmp1, label %bb2, label %bb1206 207bb1:208 %cmp2 = icmp ne i32 %indvar4, 0209 %cmp3 = icmp ne i32 %indvar5, 0210 %or.cond = select i1 %cmp2, i1 true, i1 %cmp3211 br i1 %or.cond, label %bb2, label %exit212 213bb2:214 %cmp4 = icmp eq i8 %indvar1, 39215 %cmp5 = icmp eq i32 %indvar4, 0216 %ext2 = zext i1 %cmp5 to i32217 %indvar4.next = select i1 %cmp4, i32 %ext2, i32 %indvar4218 %cmp6 = icmp eq i8 %indvar1, 34219 %cmp7 = icmp eq i32 %indvar5, 0220 %ext3 = zext i1 %cmp7 to i32221 %indvar5.next = select i1 %cmp6, i32 %ext3, i32 %indvar5222 %indvar3.next = getelementptr inbounds i8, ptr %indvar3, i64 1223 %indvar2.next = add i64 %indvar2, 1224 %load2 = load i8, ptr %indvar3.next, align 1225 br label %loop226 227exit:228 ret i32 %indvar5229}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 %loop246 247loop:248 %indvar = phi i8 [ 0, %entry ], [ %contain, %loop ]249 %cond0 = call i1 @cond()250 %contain = select i1 %cond0, i8 1, i8 %indvar251 %cond1 = call i1 @cond()252 br i1 %cond1, label %exit, label %loop253 254exit:255 %bool = and i8 %contain, 1256 ret i8 %bool257}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: [[COND0:%.*]] = call i1 @cond()265; CHECK-NEXT: [[COND1:%.*]] = call i1 @cond()266; CHECK-NEXT: br i1 [[COND1]], label [[EXIT:%.*]], label [[LOOP]]267; CHECK: exit:268; CHECK-NEXT: ret i8 1269;270entry:271 br label %loop272 273loop:274 %indvar = phi i8 [ 0, %entry ], [ %contain, %loop ]275 %cond0 = call i1 @cond()276 %contain = call i8 @llvm.umax.i8(i8 1, i8 %indvar)277 %cond1 = call i1 @cond()278 br i1 %cond1, label %exit, label %loop279 280exit:281 %bool = and i8 %contain, 1282 ret i8 %bool283}284 285define i8 @knownbits_phi_phi_test() {286; CHECK-LABEL: @knownbits_phi_phi_test(287; CHECK-NEXT: entry:288; CHECK-NEXT: br label [[LOOP:%.*]]289; CHECK: loop:290; CHECK-NEXT: [[INDVAR:%.*]] = phi i8 [ 0, [[ENTRY:%.*]] ], [ [[CONTAIN:%.*]], [[LOOP_BB1:%.*]] ]291; CHECK-NEXT: [[COND0:%.*]] = call i1 @cond()292; CHECK-NEXT: br i1 [[COND0]], label [[LOOP_BB0:%.*]], label [[LOOP_BB1]]293; CHECK: loop.bb0:294; CHECK-NEXT: call void @side.effect()295; CHECK-NEXT: br label [[LOOP_BB1]]296; CHECK: loop.bb1:297; CHECK-NEXT: [[CONTAIN]] = phi i8 [ 1, [[LOOP_BB0]] ], [ [[INDVAR]], [[LOOP]] ]298; CHECK-NEXT: [[COND1:%.*]] = call i1 @cond()299; CHECK-NEXT: br i1 [[COND1]], label [[EXIT:%.*]], label [[LOOP]]300; CHECK: exit:301; CHECK-NEXT: ret i8 [[CONTAIN]]302;303entry:304 br label %loop305 306loop:307 %indvar = phi i8 [ 0, %entry ], [ %contain, %loop.bb1 ]308 %cond0 = call i1 @cond()309 br i1 %cond0, label %loop.bb0, label %loop.bb1310loop.bb0:311 call void @side.effect()312 br label %loop.bb1313loop.bb1:314 %contain = phi i8 [ 1, %loop.bb0 ], [ %indvar, %loop ]315 %cond1 = call i1 @cond()316 br i1 %cond1, label %exit, label %loop317 318exit:319 %bool = and i8 %contain, 1320 ret i8 %bool321}322 323 324define i1 @known_non_zero_phi_phi_test() {325; CHECK-LABEL: @known_non_zero_phi_phi_test(326; CHECK-NEXT: entry:327; CHECK-NEXT: br label [[LOOP:%.*]]328; CHECK: loop:329; CHECK-NEXT: [[INDVAR:%.*]] = phi i8 [ 2, [[ENTRY:%.*]] ], [ [[CONTAIN:%.*]], [[LOOP_BB1:%.*]] ]330; CHECK-NEXT: [[COND0:%.*]] = call i1 @cond()331; CHECK-NEXT: br i1 [[COND0]], label [[LOOP_BB0:%.*]], label [[LOOP_BB1]]332; CHECK: loop.bb0:333; CHECK-NEXT: call void @side.effect()334; CHECK-NEXT: br label [[LOOP_BB1]]335; CHECK: loop.bb1:336; CHECK-NEXT: [[CONTAIN]] = phi i8 [ 1, [[LOOP_BB0]] ], [ [[INDVAR]], [[LOOP]] ]337; CHECK-NEXT: [[COND1:%.*]] = call i1 @cond()338; CHECK-NEXT: br i1 [[COND1]], label [[EXIT:%.*]], label [[LOOP]]339; CHECK: exit:340; CHECK-NEXT: [[BOOL:%.*]] = icmp eq i8 [[CONTAIN]], 0341; CHECK-NEXT: ret i1 [[BOOL]]342;343entry:344 br label %loop345 346loop:347 %indvar = phi i8 [ 2, %entry ], [ %contain, %loop.bb1 ]348 %cond0 = call i1 @cond()349 br i1 %cond0, label %loop.bb0, label %loop.bb1350loop.bb0:351 call void @side.effect()352 br label %loop.bb1353loop.bb1:354 %contain = phi i8 [ 1, %loop.bb0 ], [ %indvar, %loop ]355 %cond1 = call i1 @cond()356 br i1 %cond1, label %exit, label %loop357 358exit:359 %bool = icmp eq i8 %contain, 0360 ret i1 %bool361}362 363define i1 @known_non_zero_phi_select_test() {364; CHECK-LABEL: @known_non_zero_phi_select_test(365; CHECK-NEXT: entry:366; CHECK-NEXT: br label [[LOOP:%.*]]367; CHECK: loop:368; CHECK-NEXT: [[INDVAR:%.*]] = phi i8 [ 2, [[ENTRY:%.*]] ], [ [[CONTAIN:%.*]], [[LOOP]] ]369; CHECK-NEXT: [[COND0:%.*]] = call i1 @cond()370; CHECK-NEXT: [[CONTAIN]] = select i1 [[COND0]], i8 1, i8 [[INDVAR]]371; CHECK-NEXT: [[COND1:%.*]] = call i1 @cond()372; CHECK-NEXT: br i1 [[COND1]], label [[EXIT:%.*]], label [[LOOP]]373; CHECK: exit:374; CHECK-NEXT: [[BOOL:%.*]] = icmp eq i8 [[CONTAIN]], 0375; CHECK-NEXT: ret i1 [[BOOL]]376;377entry:378 br label %loop379 380loop:381 %indvar = phi i8 [ 2, %entry ], [ %contain, %loop ]382 %cond0 = call i1 @cond()383 %contain = select i1 %cond0, i8 1, i8 %indvar384 %cond1 = call i1 @cond()385 br i1 %cond1, label %exit, label %loop386 387exit:388 %bool = icmp eq i8 %contain, 0389 ret i1 %bool390}391 392declare i1 @cond()393declare void @side.effect()394 395