284 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; c) (x & (-1 >> 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:%.*]] = lshr i32 -1, [[NBITS:%.*]]21; CHECK-NEXT: [[T1:%.*]] = and i32 [[T0]], [[X:%.*]]22; CHECK-NEXT: call void @use32(i32 [[T0]])23; CHECK-NEXT: call void @use32(i32 [[T1]])24; CHECK-NEXT: [[T2:%.*]] = shl i32 [[X]], [[NBITS]]25; CHECK-NEXT: ret i32 [[T2]]26;27 %t0 = lshr i32 -1, %nbits28 %t1 = and i32 %t0, %x29 call void @use32(i32 %t0)30 call void @use32(i32 %t1)31 %t2 = shl i32 %t1, %nbits32 ret i32 %t233}34 35define i32 @t1_bigger_shift(i32 %x, i32 %nbits) {36; CHECK-LABEL: @t1_bigger_shift(37; CHECK-NEXT: [[T0:%.*]] = lshr i32 -1, [[NBITS:%.*]]38; CHECK-NEXT: [[T1:%.*]] = and i32 [[T0]], [[X:%.*]]39; CHECK-NEXT: [[T2:%.*]] = add i32 [[NBITS]], 140; CHECK-NEXT: call void @use32(i32 [[T0]])41; CHECK-NEXT: call void @use32(i32 [[T1]])42; CHECK-NEXT: call void @use32(i32 [[T2]])43; CHECK-NEXT: [[T3:%.*]] = shl i32 [[X]], [[T2]]44; CHECK-NEXT: ret i32 [[T3]]45;46 %t0 = lshr i32 -1, %nbits47 %t1 = and i32 %t0, %x48 %t2 = add i32 %nbits, 149 call void @use32(i32 %t0)50 call void @use32(i32 %t1)51 call void @use32(i32 %t2)52 %t3 = shl i32 %t1, %t253 ret i32 %t354}55 56; Vectors57 58declare void @use3xi32(<3 x i32>)59 60define <3 x i32> @t2_vec_splat(<3 x i32> %x, <3 x i32> %nbits) {61; CHECK-LABEL: @t2_vec_splat(62; CHECK-NEXT: [[T0:%.*]] = lshr <3 x i32> splat (i32 -1), [[NBITS:%.*]]63; CHECK-NEXT: [[T1:%.*]] = and <3 x i32> [[T0]], [[X:%.*]]64; CHECK-NEXT: [[T2:%.*]] = add <3 x i32> [[NBITS]], splat (i32 1)65; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T0]])66; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T1]])67; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T2]])68; CHECK-NEXT: [[T3:%.*]] = shl <3 x i32> [[X]], [[T2]]69; CHECK-NEXT: ret <3 x i32> [[T3]]70;71 %t0 = lshr <3 x i32> <i32 -1, i32 -1, i32 -1>, %nbits72 %t1 = and <3 x i32> %t0, %x73 %t2 = add <3 x i32> %nbits, <i32 1, i32 1, i32 1>74 call void @use3xi32(<3 x i32> %t0)75 call void @use3xi32(<3 x i32> %t1)76 call void @use3xi32(<3 x i32> %t2)77 %t3 = shl <3 x i32> %t1, %t278 ret <3 x i32> %t379}80 81define <3 x i32> @t3_vec_nonsplat(<3 x i32> %x, <3 x i32> %nbits) {82; CHECK-LABEL: @t3_vec_nonsplat(83; CHECK-NEXT: [[T0:%.*]] = lshr <3 x i32> splat (i32 -1), [[NBITS:%.*]]84; CHECK-NEXT: [[T1:%.*]] = and <3 x i32> [[T0]], [[X:%.*]]85; CHECK-NEXT: [[T2:%.*]] = add <3 x i32> [[NBITS]], <i32 1, i32 0, i32 2>86; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T0]])87; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T1]])88; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T2]])89; CHECK-NEXT: [[T3:%.*]] = shl <3 x i32> [[X]], [[T2]]90; CHECK-NEXT: ret <3 x i32> [[T3]]91;92 %t0 = lshr <3 x i32> <i32 -1, i32 -1, i32 -1>, %nbits93 %t1 = and <3 x i32> %t0, %x94 %t2 = add <3 x i32> %nbits, <i32 1, i32 0, i32 2>95 call void @use3xi32(<3 x i32> %t0)96 call void @use3xi32(<3 x i32> %t1)97 call void @use3xi32(<3 x i32> %t2)98 %t3 = shl <3 x i32> %t1, %t299 ret <3 x i32> %t3100}101 102define <3 x i32> @t4_vec_poison(<3 x i32> %x, <3 x i32> %nbits) {103; CHECK-LABEL: @t4_vec_poison(104; CHECK-NEXT: [[T0:%.*]] = lshr <3 x i32> <i32 -1, i32 poison, i32 -1>, [[NBITS:%.*]]105; CHECK-NEXT: [[T1:%.*]] = and <3 x i32> [[T0]], [[X:%.*]]106; CHECK-NEXT: [[T2:%.*]] = add <3 x i32> [[NBITS]], <i32 1, i32 poison, i32 1>107; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T0]])108; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T1]])109; CHECK-NEXT: call void @use3xi32(<3 x i32> [[T2]])110; CHECK-NEXT: [[T3:%.*]] = shl <3 x i32> [[X]], [[T2]]111; CHECK-NEXT: ret <3 x i32> [[T3]]112;113 %t0 = lshr <3 x i32> <i32 -1, i32 poison, i32 -1>, %nbits114 %t1 = and <3 x i32> %t0, %x115 %t2 = add <3 x i32> %nbits, <i32 1, i32 poison, i32 1>116 call void @use3xi32(<3 x i32> %t0)117 call void @use3xi32(<3 x i32> %t1)118 call void @use3xi32(<3 x i32> %t2)119 %t3 = shl <3 x i32> %t1, %t2120 ret <3 x i32> %t3121}122 123; Commutativity124 125declare i32 @gen32()126 127define i32 @t5_commutativity0(i32 %nbits) {128; CHECK-LABEL: @t5_commutativity0(129; CHECK-NEXT: [[X:%.*]] = call i32 @gen32()130; CHECK-NEXT: [[T0:%.*]] = lshr i32 -1, [[NBITS:%.*]]131; CHECK-NEXT: [[T1:%.*]] = and i32 [[X]], [[T0]]132; CHECK-NEXT: call void @use32(i32 [[T0]])133; CHECK-NEXT: call void @use32(i32 [[T1]])134; CHECK-NEXT: [[T2:%.*]] = shl i32 [[X]], [[NBITS]]135; CHECK-NEXT: ret i32 [[T2]]136;137 %x = call i32 @gen32()138 %t0 = lshr i32 -1, %nbits139 %t1 = and i32 %x, %t0 ; swapped140 call void @use32(i32 %t0)141 call void @use32(i32 %t1)142 %t2 = shl i32 %t1, %nbits143 ret i32 %t2144}145 146define i32 @t6_commutativity1(i32 %nbits0, i32 %nbits1) {147; CHECK-LABEL: @t6_commutativity1(148; CHECK-NEXT: [[T0:%.*]] = lshr i32 -1, [[NBITS0:%.*]]149; CHECK-NEXT: [[T1:%.*]] = lshr i32 -1, [[NBITS1:%.*]]150; CHECK-NEXT: [[T2:%.*]] = and i32 [[T0]], [[T1]]151; CHECK-NEXT: call void @use32(i32 [[T0]])152; CHECK-NEXT: call void @use32(i32 [[T1]])153; CHECK-NEXT: call void @use32(i32 [[T2]])154; CHECK-NEXT: [[T3:%.*]] = shl i32 [[T1]], [[NBITS0]]155; CHECK-NEXT: ret i32 [[T3]]156;157 %t0 = lshr i32 -1, %nbits0158 %t1 = lshr i32 -1, %nbits1159 %t2 = and i32 %t0, %t1 ; both hands of 'and' could be mask..160 call void @use32(i32 %t0)161 call void @use32(i32 %t1)162 call void @use32(i32 %t2)163 %t3 = shl i32 %t2, %nbits0164 ret i32 %t3165}166define i32 @t7_commutativity2(i32 %nbits0, i32 %nbits1) {167; CHECK-LABEL: @t7_commutativity2(168; CHECK-NEXT: [[T0:%.*]] = lshr i32 -1, [[NBITS0:%.*]]169; CHECK-NEXT: [[T1:%.*]] = lshr i32 -1, [[NBITS1:%.*]]170; CHECK-NEXT: [[T2:%.*]] = and i32 [[T0]], [[T1]]171; CHECK-NEXT: call void @use32(i32 [[T0]])172; CHECK-NEXT: call void @use32(i32 [[T1]])173; CHECK-NEXT: call void @use32(i32 [[T2]])174; CHECK-NEXT: [[T3:%.*]] = shl i32 [[T2]], [[NBITS1]]175; CHECK-NEXT: ret i32 [[T3]]176;177 %t0 = lshr i32 -1, %nbits0178 %t1 = lshr i32 -1, %nbits1179 %t2 = and i32 %t0, %t1 ; both hands of 'and' could be mask..180 call void @use32(i32 %t0)181 call void @use32(i32 %t1)182 call void @use32(i32 %t2)183 %t3 = shl i32 %t2, %nbits1184 ret i32 %t3185}186 187; Fast-math flags. We must not preserve them!188 189define i32 @t8_nuw(i32 %x, i32 %nbits) {190; CHECK-LABEL: @t8_nuw(191; CHECK-NEXT: [[T0:%.*]] = lshr i32 -1, [[NBITS:%.*]]192; CHECK-NEXT: [[T1:%.*]] = and i32 [[T0]], [[X:%.*]]193; CHECK-NEXT: call void @use32(i32 [[T0]])194; CHECK-NEXT: call void @use32(i32 [[T1]])195; CHECK-NEXT: [[T2:%.*]] = shl i32 [[X]], [[NBITS]]196; CHECK-NEXT: ret i32 [[T2]]197;198 %t0 = lshr i32 -1, %nbits199 %t1 = and i32 %t0, %x200 call void @use32(i32 %t0)201 call void @use32(i32 %t1)202 %t2 = shl nuw i32 %t1, %nbits203 ret i32 %t2204}205 206define i32 @t9_nsw(i32 %x, i32 %nbits) {207; CHECK-LABEL: @t9_nsw(208; CHECK-NEXT: [[T0:%.*]] = lshr i32 -1, [[NBITS:%.*]]209; CHECK-NEXT: [[T1:%.*]] = and i32 [[T0]], [[X:%.*]]210; CHECK-NEXT: call void @use32(i32 [[T0]])211; CHECK-NEXT: call void @use32(i32 [[T1]])212; CHECK-NEXT: [[T2:%.*]] = shl i32 [[X]], [[NBITS]]213; CHECK-NEXT: ret i32 [[T2]]214;215 %t0 = lshr i32 -1, %nbits216 %t1 = and i32 %t0, %x217 call void @use32(i32 %t0)218 call void @use32(i32 %t1)219 %t2 = shl nsw i32 %t1, %nbits220 ret i32 %t2221}222 223define i32 @t10_nuw_nsw(i32 %x, i32 %nbits) {224; CHECK-LABEL: @t10_nuw_nsw(225; CHECK-NEXT: [[T0:%.*]] = lshr i32 -1, [[NBITS:%.*]]226; CHECK-NEXT: [[T1:%.*]] = and i32 [[T0]], [[X:%.*]]227; CHECK-NEXT: call void @use32(i32 [[T0]])228; CHECK-NEXT: call void @use32(i32 [[T1]])229; CHECK-NEXT: [[T2:%.*]] = shl i32 [[X]], [[NBITS]]230; CHECK-NEXT: ret i32 [[T2]]231;232 %t0 = lshr i32 -1, %nbits233 %t1 = and i32 %t0, %x234 call void @use32(i32 %t0)235 call void @use32(i32 %t1)236 %t2 = shl nuw nsw i32 %t1, %nbits237 ret i32 %t2238}239 240; Special test241 242declare void @llvm.assume(i1 %cond)243 244; We can't simplify (%shiftnbits-%masknbits) but we have an assumption.245define i32 @t11_assume_uge(i32 %x, i32 %masknbits, i32 %shiftnbits) {246; CHECK-LABEL: @t11_assume_uge(247; CHECK-NEXT: [[CMP:%.*]] = icmp uge i32 [[SHIFTNBITS:%.*]], [[MASKNBITS:%.*]]248; CHECK-NEXT: call void @llvm.assume(i1 [[CMP]])249; CHECK-NEXT: [[T0:%.*]] = lshr i32 -1, [[MASKNBITS]]250; CHECK-NEXT: [[T1:%.*]] = and i32 [[T0]], [[X:%.*]]251; CHECK-NEXT: call void @use32(i32 [[T0]])252; CHECK-NEXT: call void @use32(i32 [[T1]])253; CHECK-NEXT: [[T2:%.*]] = shl i32 [[T1]], [[SHIFTNBITS]]254; CHECK-NEXT: ret i32 [[T2]]255;256 %cmp = icmp uge i32 %shiftnbits, %masknbits257 call void @llvm.assume(i1 %cmp)258 %t0 = lshr i32 -1, %masknbits259 %t1 = and i32 %t0, %x260 call void @use32(i32 %t0)261 call void @use32(i32 %t1)262 %t2 = shl i32 %t1, %shiftnbits263 ret i32 %t2264}265 266; Negative tests267 268define i32 @n12_not_minus_one(i32 %x, i32 %nbits) {269; CHECK-LABEL: @n12_not_minus_one(270; CHECK-NEXT: [[T0:%.*]] = lshr i32 -2, [[NBITS:%.*]]271; CHECK-NEXT: [[T1:%.*]] = and i32 [[T0]], [[X:%.*]]272; CHECK-NEXT: call void @use32(i32 [[T0]])273; CHECK-NEXT: call void @use32(i32 [[T1]])274; CHECK-NEXT: [[T2:%.*]] = shl i32 [[T1]], [[NBITS]]275; CHECK-NEXT: ret i32 [[T2]]276;277 %t0 = lshr i32 -2, %nbits ; shifting not '-1'278 %t1 = and i32 %t0, %x279 call void @use32(i32 %t0)280 call void @use32(i32 %t1)281 %t2 = shl i32 %t1, %nbits282 ret i32 %t2283}284