385 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; b) (x & (~(-1 << maskNbits))) << shiftNbits10; simplify to:11; x << shiftNbits12; iff (maskNbits+shiftNbits) u>= bitwidth(x)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:%.*]] = xor i32 [[T0]], -122; CHECK-NEXT: [[T2:%.*]] = and i32 [[X:%.*]], [[T1]]23; CHECK-NEXT: [[T3:%.*]] = sub i32 32, [[NBITS]]24; CHECK-NEXT: call void @use32(i32 [[T0]])25; CHECK-NEXT: call void @use32(i32 [[T1]])26; CHECK-NEXT: call void @use32(i32 [[T2]])27; CHECK-NEXT: call void @use32(i32 [[T3]])28; CHECK-NEXT: [[T4:%.*]] = shl i32 [[X]], [[T3]]29; CHECK-NEXT: ret i32 [[T4]]30;31 %t0 = shl i32 -1, %nbits32 %t1 = xor i32 %t0, -133 %t2 = and i32 %t1, %x34 %t3 = sub i32 32, %nbits35 call void @use32(i32 %t0)36 call void @use32(i32 %t1)37 call void @use32(i32 %t2)38 call void @use32(i32 %t3)39 %t4 = shl i32 %t2, %t340 ret i32 %t441}42 43define i32 @t1_bigger_shift(i32 %x, i32 %nbits) {44; CHECK-LABEL: @t1_bigger_shift(45; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]46; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -147; CHECK-NEXT: [[T2:%.*]] = and i32 [[X:%.*]], [[T1]]48; CHECK-NEXT: [[T3:%.*]] = sub i32 33, [[NBITS]]49; CHECK-NEXT: call void @use32(i32 [[T0]])50; CHECK-NEXT: call void @use32(i32 [[T1]])51; CHECK-NEXT: call void @use32(i32 [[T2]])52; CHECK-NEXT: call void @use32(i32 [[T3]])53; CHECK-NEXT: [[T4:%.*]] = shl i32 [[X]], [[T3]]54; CHECK-NEXT: ret i32 [[T4]]55;56 %t0 = shl i32 -1, %nbits57 %t1 = xor i32 %t0, -158 %t2 = and i32 %t1, %x59 %t3 = sub i32 33, %nbits ; subtracting from bitwidth+160 call void @use32(i32 %t0)61 call void @use32(i32 %t1)62 call void @use32(i32 %t2)63 call void @use32(i32 %t3)64 %t4 = shl i32 %t2, %t365 ret i32 %t466}67 68define i32 @t2_bigger_mask(i32 %x, i32 %nbits) {69; CHECK-LABEL: @t2_bigger_mask(70; CHECK-NEXT: [[T0:%.*]] = add i32 [[NBITS:%.*]], 171; CHECK-NEXT: [[T1:%.*]] = shl nsw i32 -1, [[T0]]72; CHECK-NEXT: [[T2:%.*]] = xor i32 [[T1]], -173; CHECK-NEXT: [[T3:%.*]] = and i32 [[X:%.*]], [[T2]]74; CHECK-NEXT: [[T4:%.*]] = sub i32 32, [[NBITS]]75; CHECK-NEXT: call void @use32(i32 [[T0]])76; CHECK-NEXT: call void @use32(i32 [[T1]])77; CHECK-NEXT: call void @use32(i32 [[T2]])78; CHECK-NEXT: call void @use32(i32 [[T3]])79; CHECK-NEXT: call void @use32(i32 [[T4]])80; CHECK-NEXT: [[T5:%.*]] = shl i32 [[X]], [[T4]]81; CHECK-NEXT: ret i32 [[T5]]82;83 %t0 = add i32 %nbits, 184 %t1 = shl i32 -1, %t0 ; shifting by nbits+185 %t2 = xor i32 %t1, -186 %t3 = and i32 %t2, %x87 %t4 = sub i32 32, %nbits88 call void @use32(i32 %t0)89 call void @use32(i32 %t1)90 call void @use32(i32 %t2)91 call void @use32(i32 %t3)92 call void @use32(i32 %t4)93 %t5 = shl i32 %t3, %t494 ret i32 %t595}96 97; Vectors98 99declare void @use3xi32(<3 x i32>)100 101define <3 x i32> @t3_vec_splat(<3 x i32> %x, <3 x i32> %nbits) {102; CHECK-LABEL: @t3_vec_splat(103; CHECK-NEXT: [[T1:%.*]] = shl nsw <3 x i32> splat (i32 -1), [[NBITS:%.*]]104; CHECK-NEXT: [[T2:%.*]] = xor <3 x i32> [[T1]], splat (i32 -1)105; CHECK-NEXT: [[T3:%.*]] = and <3 x i32> [[X:%.*]], [[T2]]106; CHECK-NEXT: [[T4:%.*]] = sub <3 x i32> splat (i32 32), [[NBITS]]107; CHECK-NEXT: call void @use3xi32(<3 x i32> [[NBITS]])108; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T1]])109; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T2]])110; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T3]])111; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T4]])112; CHECK-NEXT: [[T5:%.*]] = shl <3 x i32> [[X]], [[T4]]113; CHECK-NEXT: ret <3 x i32> [[T5]]114;115 %t0 = add <3 x i32> %nbits, <i32 0, i32 0, i32 0>116 %t1 = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, %t0117 %t2 = xor <3 x i32> %t1, <i32 -1, i32 -1, i32 -1>118 %t3 = and <3 x i32> %t2, %x119 %t4 = sub <3 x i32> <i32 32, i32 32, i32 32>, %nbits120 call void @use3xi32(<3 x i32> %t0)121 call void @use3xi32(<3 x i32> %t1)122 call void @use3xi32(<3 x i32> %t2)123 call void @use3xi32(<3 x i32> %t3)124 call void @use3xi32(<3 x i32> %t4)125 %t5 = shl <3 x i32> %t3, %t4126 ret <3 x i32> %t5127}128 129define <3 x i32> @t4_vec_nonsplat(<3 x i32> %x, <3 x i32> %nbits) {130; CHECK-LABEL: @t4_vec_nonsplat(131; CHECK-NEXT: [[T0:%.*]] = add <3 x i32> [[NBITS:%.*]], <i32 -1, i32 0, i32 1>132; CHECK-NEXT: [[T1:%.*]] = shl nsw <3 x i32> splat (i32 -1), [[T0]]133; CHECK-NEXT: [[T2:%.*]] = xor <3 x i32> [[T1]], splat (i32 -1)134; CHECK-NEXT: [[T3:%.*]] = and <3 x i32> [[X:%.*]], [[T2]]135; CHECK-NEXT: [[T4:%.*]] = sub <3 x i32> <i32 33, i32 32, i32 32>, [[NBITS]]136; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T0]])137; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T1]])138; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T2]])139; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T3]])140; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T4]])141; CHECK-NEXT: [[T5:%.*]] = shl <3 x i32> [[X]], [[T4]]142; CHECK-NEXT: ret <3 x i32> [[T5]]143;144 %t0 = add <3 x i32> %nbits, <i32 -1, i32 0, i32 1>145 %t1 = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, %t0146 %t2 = xor <3 x i32> %t1, <i32 -1, i32 -1, i32 -1>147 %t3 = and <3 x i32> %t2, %x148 %t4 = sub <3 x i32> <i32 33, i32 32, i32 32>, %nbits149 call void @use3xi32(<3 x i32> %t0)150 call void @use3xi32(<3 x i32> %t1)151 call void @use3xi32(<3 x i32> %t2)152 call void @use3xi32(<3 x i32> %t3)153 call void @use3xi32(<3 x i32> %t4)154 %t5 = shl <3 x i32> %t3, %t4155 ret <3 x i32> %t5156}157 158define <3 x i32> @t5_vec_poison(<3 x i32> %x, <3 x i32> %nbits) {159; CHECK-LABEL: @t5_vec_poison(160; CHECK-NEXT: [[T1:%.*]] = shl nsw <3 x i32> <i32 -1, i32 poison, i32 -1>, [[NBITS:%.*]]161; CHECK-NEXT: [[T2:%.*]] = xor <3 x i32> [[T1]], <i32 -1, i32 poison, i32 -1>162; CHECK-NEXT: [[T3:%.*]] = and <3 x i32> [[X:%.*]], [[T2]]163; CHECK-NEXT: [[T4:%.*]] = sub <3 x i32> <i32 32, i32 poison, i32 32>, [[NBITS]]164; CHECK-NEXT: call void @use3xi32(<3 x i32> [[NBITS]])165; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T1]])166; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T2]])167; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T3]])168; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T4]])169; CHECK-NEXT: [[T5:%.*]] = shl <3 x i32> [[X]], [[T4]]170; CHECK-NEXT: ret <3 x i32> [[T5]]171;172 %t0 = add <3 x i32> %nbits, <i32 0, i32 poison, i32 0>173 %t1 = shl <3 x i32> <i32 -1, i32 poison, i32 -1>, %t0174 %t2 = xor <3 x i32> %t1, <i32 -1, i32 poison, i32 -1>175 %t3 = and <3 x i32> %t2, %x176 %t4 = sub <3 x i32> <i32 32, i32 poison, i32 32>, %nbits177 call void @use3xi32(<3 x i32> %t0)178 call void @use3xi32(<3 x i32> %t1)179 call void @use3xi32(<3 x i32> %t2)180 call void @use3xi32(<3 x i32> %t3)181 call void @use3xi32(<3 x i32> %t4)182 %t5 = shl <3 x i32> %t3, %t4183 ret <3 x i32> %t5184}185 186; Commutativity187 188declare i32 @gen32()189 190define i32 @t6_commutativity0(i32 %nbits) {191; CHECK-LABEL: @t6_commutativity0(192; CHECK-NEXT: [[X:%.*]] = call i32 @gen32()193; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]194; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1195; CHECK-NEXT: [[T2:%.*]] = and i32 [[X]], [[T1]]196; CHECK-NEXT: [[T3:%.*]] = sub i32 32, [[NBITS]]197; CHECK-NEXT: call void @use32(i32 [[T0]])198; CHECK-NEXT: call void @use32(i32 [[T1]])199; CHECK-NEXT: call void @use32(i32 [[T2]])200; CHECK-NEXT: call void @use32(i32 [[T3]])201; CHECK-NEXT: [[T4:%.*]] = shl i32 [[X]], [[T3]]202; CHECK-NEXT: ret i32 [[T4]]203;204 %x = call i32 @gen32()205 %t0 = shl i32 -1, %nbits206 %t1 = xor i32 %t0, -1207 %t2 = and i32 %x, %t1 ; swapped208 %t3 = sub i32 32, %nbits209 call void @use32(i32 %t0)210 call void @use32(i32 %t1)211 call void @use32(i32 %t2)212 call void @use32(i32 %t3)213 %t4 = shl i32 %t2, %t3214 ret i32 %t4215}216 217define i32 @t7_commutativity1(i32 %nbits0, i32 %nbits1) {218; CHECK-LABEL: @t7_commutativity1(219; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS0:%.*]]220; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1221; CHECK-NEXT: [[T2:%.*]] = shl nsw i32 -1, [[NBITS1:%.*]]222; CHECK-NEXT: [[T3:%.*]] = xor i32 [[T2]], -1223; CHECK-NEXT: [[T4:%.*]] = and i32 [[T3]], [[T1]]224; CHECK-NEXT: [[T5:%.*]] = sub i32 32, [[NBITS0]]225; CHECK-NEXT: call void @use32(i32 [[T0]])226; CHECK-NEXT: call void @use32(i32 [[T1]])227; CHECK-NEXT: call void @use32(i32 [[T2]])228; CHECK-NEXT: call void @use32(i32 [[T3]])229; CHECK-NEXT: call void @use32(i32 [[T4]])230; CHECK-NEXT: call void @use32(i32 [[T5]])231; CHECK-NEXT: [[T6:%.*]] = shl i32 [[T4]], [[T5]]232; CHECK-NEXT: ret i32 [[T6]]233;234 %t0 = shl i32 -1, %nbits0235 %t1 = xor i32 %t0, -1236 %t2 = shl i32 -1, %nbits1237 %t3 = xor i32 %t2, -1238 %t4 = and i32 %t3, %t1 ; both hands of 'and' could be mask..239 %t5 = sub i32 32, %nbits0240 call void @use32(i32 %t0)241 call void @use32(i32 %t1)242 call void @use32(i32 %t2)243 call void @use32(i32 %t3)244 call void @use32(i32 %t4)245 call void @use32(i32 %t5)246 %t6 = shl i32 %t4, %t5247 ret i32 %t6248}249define i32 @t8_commutativity2(i32 %nbits0, i32 %nbits1) {250; CHECK-LABEL: @t8_commutativity2(251; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS0:%.*]]252; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1253; CHECK-NEXT: [[T2:%.*]] = shl nsw i32 -1, [[NBITS1:%.*]]254; CHECK-NEXT: [[T3:%.*]] = xor i32 [[T2]], -1255; CHECK-NEXT: [[T4:%.*]] = and i32 [[T3]], [[T1]]256; CHECK-NEXT: [[T5:%.*]] = sub i32 32, [[NBITS1]]257; CHECK-NEXT: call void @use32(i32 [[T0]])258; CHECK-NEXT: call void @use32(i32 [[T1]])259; CHECK-NEXT: call void @use32(i32 [[T2]])260; CHECK-NEXT: call void @use32(i32 [[T3]])261; CHECK-NEXT: call void @use32(i32 [[T4]])262; CHECK-NEXT: call void @use32(i32 [[T5]])263; CHECK-NEXT: [[T6:%.*]] = shl i32 [[T1]], [[T5]]264; CHECK-NEXT: ret i32 [[T6]]265;266 %t0 = shl i32 -1, %nbits0267 %t1 = xor i32 %t0, -1268 %t2 = shl i32 -1, %nbits1269 %t3 = xor i32 %t2, -1270 %t4 = and i32 %t3, %t1 ; both hands of 'and' could be mask..271 %t5 = sub i32 32, %nbits1272 call void @use32(i32 %t0)273 call void @use32(i32 %t1)274 call void @use32(i32 %t2)275 call void @use32(i32 %t3)276 call void @use32(i32 %t4)277 call void @use32(i32 %t5)278 %t6 = shl i32 %t4, %t5279 ret i32 %t6280}281 282; Fast-math flags. We must not preserve them!283 284define i32 @t9_nuw(i32 %x, i32 %nbits) {285; CHECK-LABEL: @t9_nuw(286; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]287; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1288; CHECK-NEXT: [[T2:%.*]] = and i32 [[X:%.*]], [[T1]]289; CHECK-NEXT: [[T3:%.*]] = sub i32 32, [[NBITS]]290; CHECK-NEXT: call void @use32(i32 [[T0]])291; CHECK-NEXT: call void @use32(i32 [[T1]])292; CHECK-NEXT: call void @use32(i32 [[T2]])293; CHECK-NEXT: call void @use32(i32 [[T3]])294; CHECK-NEXT: [[T4:%.*]] = shl i32 [[X]], [[T3]]295; CHECK-NEXT: ret i32 [[T4]]296;297 %t0 = shl i32 -1, %nbits298 %t1 = xor i32 %t0, -1299 %t2 = and i32 %t1, %x300 %t3 = sub i32 32, %nbits301 call void @use32(i32 %t0)302 call void @use32(i32 %t1)303 call void @use32(i32 %t2)304 call void @use32(i32 %t3)305 %t4 = shl nuw i32 %t2, %t3306 ret i32 %t4307}308 309define i32 @t10_nsw(i32 %x, i32 %nbits) {310; CHECK-LABEL: @t10_nsw(311; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]312; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1313; CHECK-NEXT: [[T2:%.*]] = and i32 [[X:%.*]], [[T1]]314; CHECK-NEXT: [[T3:%.*]] = sub i32 32, [[NBITS]]315; CHECK-NEXT: call void @use32(i32 [[T0]])316; CHECK-NEXT: call void @use32(i32 [[T1]])317; CHECK-NEXT: call void @use32(i32 [[T2]])318; CHECK-NEXT: call void @use32(i32 [[T3]])319; CHECK-NEXT: [[T4:%.*]] = shl i32 [[X]], [[T3]]320; CHECK-NEXT: ret i32 [[T4]]321;322 %t0 = shl i32 -1, %nbits323 %t1 = xor i32 %t0, -1324 %t2 = and i32 %t1, %x325 %t3 = sub i32 32, %nbits326 call void @use32(i32 %t0)327 call void @use32(i32 %t1)328 call void @use32(i32 %t2)329 call void @use32(i32 %t3)330 %t4 = shl nsw i32 %t2, %t3331 ret i32 %t4332}333 334define i32 @t11_nuw_nsw(i32 %x, i32 %nbits) {335; CHECK-LABEL: @t11_nuw_nsw(336; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]337; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1338; CHECK-NEXT: [[T2:%.*]] = and i32 [[X:%.*]], [[T1]]339; CHECK-NEXT: [[T3:%.*]] = sub i32 32, [[NBITS]]340; CHECK-NEXT: call void @use32(i32 [[T0]])341; CHECK-NEXT: call void @use32(i32 [[T1]])342; CHECK-NEXT: call void @use32(i32 [[T2]])343; CHECK-NEXT: call void @use32(i32 [[T3]])344; CHECK-NEXT: [[T4:%.*]] = shl i32 [[X]], [[T3]]345; CHECK-NEXT: ret i32 [[T4]]346;347 %t0 = shl i32 -1, %nbits348 %t1 = xor i32 %t0, -1349 %t2 = and i32 %t1, %x350 %t3 = sub i32 32, %nbits351 call void @use32(i32 %t0)352 call void @use32(i32 %t1)353 call void @use32(i32 %t2)354 call void @use32(i32 %t3)355 %t4 = shl nuw nsw i32 %t2, %t3356 ret i32 %t4357}358 359; Negative tests360 361define i32 @n12_not_minus_one(i32 %x, i32 %nbits) {362; CHECK-LABEL: @n12_not_minus_one(363; CHECK-NEXT: [[T0:%.*]] = shl i32 -2, [[NBITS:%.*]]364; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1365; CHECK-NEXT: [[T2:%.*]] = and i32 [[X:%.*]], [[T1]]366; CHECK-NEXT: [[T3:%.*]] = sub i32 32, [[NBITS]]367; CHECK-NEXT: call void @use32(i32 [[T0]])368; CHECK-NEXT: call void @use32(i32 [[T1]])369; CHECK-NEXT: call void @use32(i32 [[T2]])370; CHECK-NEXT: call void @use32(i32 [[T3]])371; CHECK-NEXT: [[T4:%.*]] = shl i32 [[T2]], [[T3]]372; CHECK-NEXT: ret i32 [[T4]]373;374 %t0 = shl i32 -2, %nbits ; shifting not '-1'375 %t1 = xor i32 %t0, -1376 %t2 = and i32 %t1, %x377 %t3 = sub i32 32, %nbits378 call void @use32(i32 %t0)379 call void @use32(i32 %t1)380 call void @use32(i32 %t2)381 call void @use32(i32 %t3)382 %t4 = shl i32 %t2, %t3383 ret i32 %t4384}385