364 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt < %s -passes=instcombine -S | FileCheck %s3 4; If we have some pattern that leaves only some low bits set, and then performs5; left-shift of those bits, if none of the bits that are left after the final6; shift are modified by the mask, we can omit the mask.7 8; There are many variants to this pattern:9; d) (x & ((-1 << maskNbits) >> maskNbits)) << shiftNbits10; simplify to:11; x << shiftNbits12; iff (shiftNbits-maskNbits) s>= 0 (i.e. shiftNbits u>= maskNbits)13 14; Simple tests. We don't care about extra uses.15 16declare void @use32(i32)17 18define i32 @t0_basic(i32 %x, i32 %nbits) {19; CHECK-LABEL: @t0_basic(20; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]21; CHECK-NEXT: [[T1:%.*]] = lshr i32 -1, [[NBITS]]22; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X:%.*]]23; CHECK-NEXT: call void @use32(i32 [[T0]])24; CHECK-NEXT: call void @use32(i32 [[T1]])25; CHECK-NEXT: call void @use32(i32 [[T2]])26; CHECK-NEXT: [[T4:%.*]] = shl i32 [[X]], [[NBITS]]27; CHECK-NEXT: ret i32 [[T4]]28;29 %t0 = shl i32 -1, %nbits30 %t1 = lshr i32 %t0, %nbits31 %t2 = and i32 %t1, %x32 call void @use32(i32 %t0)33 call void @use32(i32 %t1)34 call void @use32(i32 %t2)35 %t4 = shl i32 %t2, %nbits36 ret i32 %t437}38 39define i32 @t1_bigger_shift(i32 %x, i32 %nbits) {40; CHECK-LABEL: @t1_bigger_shift(41; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]42; CHECK-NEXT: [[T1:%.*]] = lshr i32 -1, [[NBITS]]43; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X:%.*]]44; CHECK-NEXT: [[T3:%.*]] = add i32 [[NBITS]], 145; CHECK-NEXT: call void @use32(i32 [[T0]])46; CHECK-NEXT: call void @use32(i32 [[T1]])47; CHECK-NEXT: call void @use32(i32 [[T2]])48; CHECK-NEXT: call void @use32(i32 [[T3]])49; CHECK-NEXT: [[T4:%.*]] = shl i32 [[X]], [[T3]]50; CHECK-NEXT: ret i32 [[T4]]51;52 %t0 = shl i32 -1, %nbits53 %t1 = lshr i32 %t0, %nbits54 %t2 = and i32 %t1, %x55 %t3 = add i32 %nbits, 156 call void @use32(i32 %t0)57 call void @use32(i32 %t1)58 call void @use32(i32 %t2)59 call void @use32(i32 %t3)60 %t4 = shl i32 %t2, %t361 ret i32 %t462}63 64; Vectors65 66declare void @use3xi32(<3 x i32>)67 68define <3 x i32> @t2_vec_splat(<3 x i32> %x, <3 x i32> %nbits) {69; CHECK-LABEL: @t2_vec_splat(70; CHECK-NEXT: [[T0:%.*]] = shl nsw <3 x i32> splat (i32 -1), [[NBITS:%.*]]71; CHECK-NEXT: [[T1:%.*]] = lshr <3 x i32> splat (i32 -1), [[NBITS]]72; CHECK-NEXT: [[T2:%.*]] = and <3 x i32> [[T1]], [[X:%.*]]73; CHECK-NEXT: [[T3:%.*]] = add <3 x i32> [[NBITS]], splat (i32 1)74; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T0]])75; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T1]])76; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T2]])77; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T3]])78; CHECK-NEXT: [[T4:%.*]] = shl <3 x i32> [[X]], [[T3]]79; CHECK-NEXT: ret <3 x i32> [[T4]]80;81 %t0 = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, %nbits82 %t1 = lshr <3 x i32> %t0, %nbits83 %t2 = and <3 x i32> %t1, %x84 %t3 = add <3 x i32> %nbits, <i32 1, i32 1, i32 1>85 call void @use3xi32(<3 x i32> %t0)86 call void @use3xi32(<3 x i32> %t1)87 call void @use3xi32(<3 x i32> %t2)88 call void @use3xi32(<3 x i32> %t3)89 %t4 = shl <3 x i32> %t2, %t390 ret <3 x i32> %t491}92 93define <3 x i32> @t3_vec_nonsplat(<3 x i32> %x, <3 x i32> %nbits) {94; CHECK-LABEL: @t3_vec_nonsplat(95; CHECK-NEXT: [[T0:%.*]] = shl nsw <3 x i32> splat (i32 -1), [[NBITS:%.*]]96; CHECK-NEXT: [[T1:%.*]] = lshr <3 x i32> splat (i32 -1), [[NBITS]]97; CHECK-NEXT: [[T2:%.*]] = and <3 x i32> [[T1]], [[X:%.*]]98; CHECK-NEXT: [[T3:%.*]] = add <3 x i32> [[NBITS]], <i32 1, i32 0, i32 2>99; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T0]])100; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T1]])101; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T2]])102; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T3]])103; CHECK-NEXT: [[T4:%.*]] = shl <3 x i32> [[X]], [[T3]]104; CHECK-NEXT: ret <3 x i32> [[T4]]105;106 %t0 = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, %nbits107 %t1 = lshr <3 x i32> %t0, %nbits108 %t2 = and <3 x i32> %t1, %x109 %t3 = add <3 x i32> %nbits, <i32 1, i32 0, i32 2>110 call void @use3xi32(<3 x i32> %t0)111 call void @use3xi32(<3 x i32> %t1)112 call void @use3xi32(<3 x i32> %t2)113 call void @use3xi32(<3 x i32> %t3)114 %t4 = shl <3 x i32> %t2, %t3115 ret <3 x i32> %t4116}117 118define <3 x i32> @t4_vec_poison(<3 x i32> %x, <3 x i32> %nbits) {119; CHECK-LABEL: @t4_vec_poison(120; CHECK-NEXT: [[T0:%.*]] = shl nsw <3 x i32> <i32 -1, i32 poison, i32 -1>, [[NBITS:%.*]]121; CHECK-NEXT: [[T1:%.*]] = lshr <3 x i32> splat (i32 -1), [[NBITS]]122; CHECK-NEXT: [[T2:%.*]] = and <3 x i32> [[T1]], [[X:%.*]]123; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T0]])124; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T1]])125; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T2]])126; CHECK-NEXT: call void @use3xi32(<3 x i32> [[NBITS]])127; CHECK-NEXT: [[T4:%.*]] = shl <3 x i32> [[X]], [[NBITS]]128; CHECK-NEXT: ret <3 x i32> [[T4]]129;130 %t0 = shl <3 x i32> <i32 -1, i32 poison, i32 -1>, %nbits131 %t1 = lshr <3 x i32> %t0, %nbits132 %t2 = and <3 x i32> %t1, %x133 %t3 = add <3 x i32> %nbits, <i32 0, i32 poison, i32 0>134 call void @use3xi32(<3 x i32> %t0)135 call void @use3xi32(<3 x i32> %t1)136 call void @use3xi32(<3 x i32> %t2)137 call void @use3xi32(<3 x i32> %t3)138 %t4 = shl <3 x i32> %t2, %t3139 ret <3 x i32> %t4140}141 142; Commutativity143 144declare i32 @gen32()145 146define i32 @t5_commutativity0(i32 %nbits) {147; CHECK-LABEL: @t5_commutativity0(148; CHECK-NEXT: [[X:%.*]] = call i32 @gen32()149; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]150; CHECK-NEXT: [[T1:%.*]] = lshr i32 -1, [[NBITS]]151; CHECK-NEXT: [[T2:%.*]] = and i32 [[X]], [[T1]]152; CHECK-NEXT: call void @use32(i32 [[T0]])153; CHECK-NEXT: call void @use32(i32 [[T1]])154; CHECK-NEXT: call void @use32(i32 [[T2]])155; CHECK-NEXT: [[T3:%.*]] = shl i32 [[X]], [[NBITS]]156; CHECK-NEXT: ret i32 [[T3]]157;158 %x = call i32 @gen32()159 %t0 = shl i32 -1, %nbits160 %t1 = lshr i32 %t0, %nbits161 %t2 = and i32 %x, %t1 ; swapped order162 call void @use32(i32 %t0)163 call void @use32(i32 %t1)164 call void @use32(i32 %t2)165 %t3 = shl i32 %t2, %nbits166 ret i32 %t3167}168 169define i32 @t6_commutativity1(i32 %nbits0, i32 %nbits1) {170; CHECK-LABEL: @t6_commutativity1(171; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS0:%.*]]172; CHECK-NEXT: [[T1:%.*]] = lshr i32 -1, [[NBITS0]]173; CHECK-NEXT: [[T2:%.*]] = shl nsw i32 -1, [[NBITS1:%.*]]174; CHECK-NEXT: [[T3:%.*]] = lshr i32 [[T0]], [[NBITS1]]175; CHECK-NEXT: [[T4:%.*]] = and i32 [[T3]], [[T1]]176; CHECK-NEXT: call void @use32(i32 [[T0]])177; CHECK-NEXT: call void @use32(i32 [[T1]])178; CHECK-NEXT: call void @use32(i32 [[T2]])179; CHECK-NEXT: call void @use32(i32 [[T3]])180; CHECK-NEXT: call void @use32(i32 [[T4]])181; CHECK-NEXT: [[T5:%.*]] = shl i32 [[T3]], [[NBITS0]]182; CHECK-NEXT: ret i32 [[T5]]183;184 %t0 = shl i32 -1, %nbits0185 %t1 = lshr i32 %t0, %nbits0186 %t2 = shl i32 -1, %nbits1187 %t3 = lshr i32 %t0, %nbits1188 %t4 = and i32 %t3, %t1 ; both hands of 'and' could be mask..189 call void @use32(i32 %t0)190 call void @use32(i32 %t1)191 call void @use32(i32 %t2)192 call void @use32(i32 %t3)193 call void @use32(i32 %t4)194 %t5 = shl i32 %t4, %nbits0195 ret i32 %t5196}197define i32 @t7_commutativity2(i32 %nbits0, i32 %nbits1) {198; CHECK-LABEL: @t7_commutativity2(199; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS0:%.*]]200; CHECK-NEXT: [[T1:%.*]] = lshr i32 -1, [[NBITS0]]201; CHECK-NEXT: [[T2:%.*]] = shl nsw i32 -1, [[NBITS1:%.*]]202; CHECK-NEXT: [[T3:%.*]] = lshr i32 [[T0]], [[NBITS1]]203; CHECK-NEXT: [[T4:%.*]] = and i32 [[T3]], [[T1]]204; CHECK-NEXT: call void @use32(i32 [[T0]])205; CHECK-NEXT: call void @use32(i32 [[T1]])206; CHECK-NEXT: call void @use32(i32 [[T2]])207; CHECK-NEXT: call void @use32(i32 [[T3]])208; CHECK-NEXT: call void @use32(i32 [[T4]])209; CHECK-NEXT: [[T5:%.*]] = shl i32 [[T4]], [[NBITS1]]210; CHECK-NEXT: ret i32 [[T5]]211;212 %t0 = shl i32 -1, %nbits0213 %t1 = lshr i32 %t0, %nbits0214 %t2 = shl i32 -1, %nbits1215 %t3 = lshr i32 %t0, %nbits1216 %t4 = and i32 %t3, %t1 ; both hands of 'and' could be mask..217 call void @use32(i32 %t0)218 call void @use32(i32 %t1)219 call void @use32(i32 %t2)220 call void @use32(i32 %t3)221 call void @use32(i32 %t4)222 %t5 = shl i32 %t4, %nbits1223 ret i32 %t5224}225 226; Fast-math flags. We must not preserve them!227 228define i32 @t8_nuw(i32 %x, i32 %nbits) {229; CHECK-LABEL: @t8_nuw(230; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]231; CHECK-NEXT: [[T1:%.*]] = lshr i32 -1, [[NBITS]]232; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X:%.*]]233; CHECK-NEXT: call void @use32(i32 [[T0]])234; CHECK-NEXT: call void @use32(i32 [[T1]])235; CHECK-NEXT: call void @use32(i32 [[T2]])236; CHECK-NEXT: [[T3:%.*]] = shl i32 [[X]], [[NBITS]]237; CHECK-NEXT: ret i32 [[T3]]238;239 %t0 = shl i32 -1, %nbits240 %t1 = lshr i32 %t0, %nbits241 %t2 = and i32 %t1, %x242 call void @use32(i32 %t0)243 call void @use32(i32 %t1)244 call void @use32(i32 %t2)245 %t3 = shl nuw i32 %t2, %nbits246 ret i32 %t3247}248 249define i32 @t9_nsw(i32 %x, i32 %nbits) {250; CHECK-LABEL: @t9_nsw(251; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]252; CHECK-NEXT: [[T1:%.*]] = lshr i32 -1, [[NBITS]]253; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X:%.*]]254; CHECK-NEXT: call void @use32(i32 [[T0]])255; CHECK-NEXT: call void @use32(i32 [[T1]])256; CHECK-NEXT: call void @use32(i32 [[T2]])257; CHECK-NEXT: [[T3:%.*]] = shl i32 [[X]], [[NBITS]]258; CHECK-NEXT: ret i32 [[T3]]259;260 %t0 = shl i32 -1, %nbits261 %t1 = lshr i32 %t0, %nbits262 %t2 = and i32 %t1, %x263 call void @use32(i32 %t0)264 call void @use32(i32 %t1)265 call void @use32(i32 %t2)266 %t3 = shl nsw i32 %t2, %nbits267 ret i32 %t3268}269 270define i32 @t10_nuw_nsw(i32 %x, i32 %nbits) {271; CHECK-LABEL: @t10_nuw_nsw(272; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]273; CHECK-NEXT: [[T1:%.*]] = lshr i32 -1, [[NBITS]]274; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X:%.*]]275; CHECK-NEXT: call void @use32(i32 [[T0]])276; CHECK-NEXT: call void @use32(i32 [[T1]])277; CHECK-NEXT: call void @use32(i32 [[T2]])278; CHECK-NEXT: [[T3:%.*]] = shl i32 [[X]], [[NBITS]]279; CHECK-NEXT: ret i32 [[T3]]280;281 %t0 = shl i32 -1, %nbits282 %t1 = lshr i32 %t0, %nbits283 %t2 = and i32 %t1, %x284 call void @use32(i32 %t0)285 call void @use32(i32 %t1)286 call void @use32(i32 %t2)287 %t3 = shl nuw nsw i32 %t2, %nbits288 ret i32 %t3289}290 291; Special test292 293declare void @llvm.assume(i1 %cond)294 295; We can't simplify (%shiftnbits-%masknbits) but we have an assumption.296define i32 @t11_assume_uge(i32 %x, i32 %masknbits, i32 %shiftnbits) {297; CHECK-LABEL: @t11_assume_uge(298; CHECK-NEXT: [[CMP:%.*]] = icmp uge i32 [[SHIFTNBITS:%.*]], [[MASKNBITS:%.*]]299; CHECK-NEXT: call void @llvm.assume(i1 [[CMP]])300; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[MASKNBITS]]301; CHECK-NEXT: [[T1:%.*]] = lshr i32 -1, [[MASKNBITS]]302; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X:%.*]]303; CHECK-NEXT: call void @use32(i32 [[T0]])304; CHECK-NEXT: call void @use32(i32 [[T1]])305; CHECK-NEXT: call void @use32(i32 [[T2]])306; CHECK-NEXT: [[T4:%.*]] = shl i32 [[T2]], [[SHIFTNBITS]]307; CHECK-NEXT: ret i32 [[T4]]308;309 %cmp = icmp uge i32 %shiftnbits, %masknbits310 call void @llvm.assume(i1 %cmp)311 %t0 = shl i32 -1, %masknbits312 %t1 = lshr i32 %t0, %masknbits313 %t2 = and i32 %t1, %x314 call void @use32(i32 %t0)315 call void @use32(i32 %t1)316 call void @use32(i32 %t2)317 %t4 = shl i32 %t2, %shiftnbits318 ret i32 %t4319}320 321; Negative tests322 323define i32 @n12_different_shamts0(i32 %x, i32 %nbits0, i32 %nbits1) {324; CHECK-LABEL: @n12_different_shamts0(325; CHECK-NEXT: [[T0:%.*]] = shl i32 [[X:%.*]], [[NBITS0:%.*]]326; CHECK-NEXT: [[T1:%.*]] = lshr i32 [[T0]], [[NBITS1:%.*]]327; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X]]328; CHECK-NEXT: call void @use32(i32 [[T0]])329; CHECK-NEXT: call void @use32(i32 [[T1]])330; CHECK-NEXT: call void @use32(i32 [[T2]])331; CHECK-NEXT: [[T3:%.*]] = shl i32 [[T2]], [[NBITS0]]332; CHECK-NEXT: ret i32 [[T3]]333;334 %t0 = shl i32 %x, %nbits0 ; different shift amts335 %t1 = lshr i32 %t0, %nbits1 ; different shift amts336 %t2 = and i32 %t1, %x337 call void @use32(i32 %t0)338 call void @use32(i32 %t1)339 call void @use32(i32 %t2)340 %t3 = shl i32 %t2, %nbits0341 ret i32 %t3342}343 344define i32 @n13_different_shamts1(i32 %x, i32 %nbits0, i32 %nbits1) {345; CHECK-LABEL: @n13_different_shamts1(346; CHECK-NEXT: [[T0:%.*]] = shl i32 [[X:%.*]], [[NBITS0:%.*]]347; CHECK-NEXT: [[T1:%.*]] = lshr i32 [[T0]], [[NBITS1:%.*]]348; CHECK-NEXT: [[T2:%.*]] = and i32 [[T1]], [[X]]349; CHECK-NEXT: call void @use32(i32 [[T0]])350; CHECK-NEXT: call void @use32(i32 [[T1]])351; CHECK-NEXT: call void @use32(i32 [[T2]])352; CHECK-NEXT: [[T3:%.*]] = shl i32 [[T2]], [[NBITS1]]353; CHECK-NEXT: ret i32 [[T3]]354;355 %t0 = shl i32 %x, %nbits0 ; different shift amts356 %t1 = lshr i32 %t0, %nbits1 ; different shift amts357 %t2 = and i32 %t1, %x358 call void @use32(i32 %t0)359 call void @use32(i32 %t1)360 call void @use32(i32 %t2)361 %t3 = shl i32 %t2, %nbits1362 ret i32 %t3363}364