383 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt < %s -passes=instcombine -S | FileCheck %s3 4; std::bit_ceil<uint32_t>(x)5define i32 @bit_ceil_32(i32 %x) {6; CHECK-LABEL: @bit_ceil_32(7; CHECK-NEXT: [[DEC:%.*]] = add i32 [[X:%.*]], -18; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[DEC]], i1 false)9; CHECK-NEXT: [[TMP1:%.*]] = sub nsw i32 0, [[CTLZ]]10; CHECK-NEXT: [[TMP2:%.*]] = and i32 [[TMP1]], 3111; CHECK-NEXT: [[SEL:%.*]] = shl nuw i32 1, [[TMP2]]12; CHECK-NEXT: ret i32 [[SEL]]13;14 %dec = add i32 %x, -115 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %dec, i1 false)16 %sub = sub i32 32, %ctlz17 %shl = shl i32 1, %sub18 %ugt = icmp ugt i32 %x, 119 %sel = select i1 %ugt, i32 %shl, i32 120 ret i32 %sel21}22 23; std::bit_ceil<uint64_t>(x)24define i64 @bit_ceil_64(i64 %x) {25; CHECK-LABEL: @bit_ceil_64(26; CHECK-NEXT: [[DEC:%.*]] = add i64 [[X:%.*]], -127; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i64 0, 65) i64 @llvm.ctlz.i64(i64 [[DEC]], i1 false)28; CHECK-NEXT: [[TMP1:%.*]] = sub nsw i64 0, [[CTLZ]]29; CHECK-NEXT: [[TMP2:%.*]] = and i64 [[TMP1]], 6330; CHECK-NEXT: [[SEL:%.*]] = shl nuw i64 1, [[TMP2]]31; CHECK-NEXT: ret i64 [[SEL]]32;33 %dec = add i64 %x, -134 %ctlz = tail call i64 @llvm.ctlz.i64(i64 %dec, i1 false)35 %sub = sub i64 64, %ctlz36 %shl = shl i64 1, %sub37 %ugt = icmp ugt i64 %x, 138 %sel = select i1 %ugt, i64 %shl, i64 139 ret i64 %sel40}41 42; std::bit_ceil<uint32_t>(x - 1)43define i32 @bit_ceil_32_minus_1(i32 %x) {44; CHECK-LABEL: @bit_ceil_32_minus_1(45; CHECK-NEXT: entry:46; CHECK-NEXT: [[SUB:%.*]] = add i32 [[X:%.*]], -247; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[SUB]], i1 false)48; CHECK-NEXT: [[TMP0:%.*]] = sub nsw i32 0, [[CTLZ]]49; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[TMP0]], 3150; CHECK-NEXT: [[SEL:%.*]] = shl nuw i32 1, [[TMP1]]51; CHECK-NEXT: ret i32 [[SEL]]52;53entry:54 %sub = add i32 %x, -255 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %sub, i1 false)56 %sub2 = sub nuw nsw i32 32, %ctlz57 %shl = shl nuw i32 1, %sub258 %add = add i32 %x, -359 %ult = icmp ult i32 %add, -260 %sel = select i1 %ult, i32 %shl, i32 161 ret i32 %sel62}63 64; std::bit_ceil<uint32_t>(x + 1)65define i32 @bit_ceil_32_plus_1(i32 %x) {66; CHECK-LABEL: @bit_ceil_32_plus_1(67; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[X:%.*]], i1 false)68; CHECK-NEXT: [[TMP1:%.*]] = sub nsw i32 0, [[CTLZ]]69; CHECK-NEXT: [[TMP2:%.*]] = and i32 [[TMP1]], 3170; CHECK-NEXT: [[SEL:%.*]] = shl nuw i32 1, [[TMP2]]71; CHECK-NEXT: ret i32 [[SEL]]72;73 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %x, i1 false)74 %sub = sub i32 32, %ctlz75 %shl = shl i32 1, %sub76 %dec = add i32 %x, -177 %ult = icmp ult i32 %dec, -278 %sel = select i1 %ult, i32 %shl, i32 179 ret i32 %sel80}81 82; std::bit_ceil<uint32_t>(x + 2)83define i32 @bit_ceil_plus_2(i32 %x) {84; CHECK-LABEL: @bit_ceil_plus_2(85; CHECK-NEXT: entry:86; CHECK-NEXT: [[SUB:%.*]] = add i32 [[X:%.*]], 187; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[SUB]], i1 false)88; CHECK-NEXT: [[TMP0:%.*]] = sub nsw i32 0, [[CTLZ]]89; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[TMP0]], 3190; CHECK-NEXT: [[SEL:%.*]] = shl nuw i32 1, [[TMP1]]91; CHECK-NEXT: ret i32 [[SEL]]92;93entry:94 %sub = add i32 %x, 195 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %sub, i1 false)96 %sub2 = sub nuw nsw i32 32, %ctlz97 %shl = shl nuw i32 1, %sub298 %ult = icmp ult i32 %x, -299 %sel = select i1 %ult, i32 %shl, i32 1100 ret i32 %sel101}102 103; std::bit_ceil<uint32_t>(-x)104define i32 @bit_ceil_32_neg(i32 %x) {105; CHECK-LABEL: @bit_ceil_32_neg(106; CHECK-NEXT: entry:107; CHECK-NEXT: [[SUB:%.*]] = xor i32 [[X:%.*]], -1108; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[SUB]], i1 false)109; CHECK-NEXT: [[TMP0:%.*]] = sub nsw i32 0, [[CTLZ]]110; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[TMP0]], 31111; CHECK-NEXT: [[SEL:%.*]] = shl nuw i32 1, [[TMP1]]112; CHECK-NEXT: ret i32 [[SEL]]113;114entry:115 %sub = xor i32 %x, -1116 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %sub, i1 false)117 %sub2 = sub nuw nsw i32 32, %ctlz118 %shl = shl nuw i32 1, %sub2119 %notsub = add i32 %x, -1120 %ult = icmp ult i32 %notsub, -2121 %sel = select i1 %ult, i32 %shl, i32 1122 ret i32 %sel123}124 125; std::bit_ceil<uint32_t>(~x)126define i32 @bit_ceil_not(i32 %x) {127; CHECK-LABEL: @bit_ceil_not(128; CHECK-NEXT: entry:129; CHECK-NEXT: [[SUB:%.*]] = sub i32 -2, [[X:%.*]]130; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[SUB]], i1 false)131; CHECK-NEXT: [[TMP0:%.*]] = sub nsw i32 0, [[CTLZ]]132; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[TMP0]], 31133; CHECK-NEXT: [[SEL:%.*]] = shl nuw i32 1, [[TMP1]]134; CHECK-NEXT: ret i32 [[SEL]]135;136entry:137 %sub = sub i32 -2, %x138 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %sub, i1 false)139 %sub2 = sub nuw nsw i32 32, %ctlz140 %shl = shl nuw i32 1, %sub2141 %ult = icmp ult i32 %x, -2142 %sel = select i1 %ult, i32 %shl, i32 1143 ret i32 %sel144}145 146; Commuted select operands should still be recognized.147define i32 @bit_ceil_commuted_operands(i32 %x) {148; CHECK-LABEL: @bit_ceil_commuted_operands(149; CHECK-NEXT: [[DEC:%.*]] = add i32 [[X:%.*]], -1150; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[DEC]], i1 false)151; CHECK-NEXT: [[SUB:%.*]] = sub nuw nsw i32 32, [[CTLZ]]152; CHECK-NEXT: [[SHL:%.*]] = shl nuw i32 1, [[SUB]]153; CHECK-NEXT: ret i32 [[SHL]]154;155 %dec = add i32 %x, -1156 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %dec, i1 false)157 %sub = sub i32 32, %ctlz158 %shl = shl i32 1, %sub159 %eq = icmp eq i32 %dec, 0160 %sel = select i1 %eq, i32 1, i32 %shl161 ret i32 %sel162}163 164; Negative test: wrong select constant165define i32 @bit_ceil_wrong_select_constant(i32 %x) {166; CHECK-LABEL: @bit_ceil_wrong_select_constant(167; CHECK-NEXT: [[DEC:%.*]] = add i32 [[X:%.*]], -1168; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[DEC]], i1 false)169; CHECK-NEXT: [[SUB:%.*]] = sub nuw nsw i32 32, [[CTLZ]]170; CHECK-NEXT: [[SHL:%.*]] = shl nuw i32 1, [[SUB]]171; CHECK-NEXT: [[UGT_INV:%.*]] = icmp ult i32 [[X]], 2172; CHECK-NEXT: [[SEL:%.*]] = select i1 [[UGT_INV]], i32 2, i32 [[SHL]]173; CHECK-NEXT: ret i32 [[SEL]]174;175 %dec = add i32 %x, -1176 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %dec, i1 false)177 %sub = sub i32 32, %ctlz178 %shl = shl i32 1, %sub179 %ugt = icmp ugt i32 %x, 1180 %sel = select i1 %ugt, i32 %shl, i32 2181 ret i32 %sel182}183 184; Negative test: select condition != false does not guarantee ctlz being either 0 or 32185define i32 @bit_ceil_32_wrong_cond(i32 %x) {186; CHECK-LABEL: @bit_ceil_32_wrong_cond(187; CHECK-NEXT: [[DEC:%.*]] = add i32 [[X:%.*]], -1188; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[DEC]], i1 false)189; CHECK-NEXT: [[SUB:%.*]] = sub nuw nsw i32 32, [[CTLZ]]190; CHECK-NEXT: [[SHL:%.*]] = shl nuw i32 1, [[SUB]]191; CHECK-NEXT: [[UGT:%.*]] = icmp ugt i32 [[X]], 2192; CHECK-NEXT: [[SEL:%.*]] = select i1 [[UGT]], i32 [[SHL]], i32 1193; CHECK-NEXT: ret i32 [[SEL]]194;195 %dec = add i32 %x, -1196 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %dec, i1 false)197 %sub = sub i32 32, %ctlz198 %shl = shl i32 1, %sub199 %ugt = icmp ugt i32 %x, 2200 %sel = select i1 %ugt, i32 %shl, i32 1201 ret i32 %sel202}203 204; Negative test: wrong sub constant205define i32 @bit_ceil_wrong_sub_constant(i32 %x) {206; CHECK-LABEL: @bit_ceil_wrong_sub_constant(207; CHECK-NEXT: [[DEC:%.*]] = add i32 [[X:%.*]], -1208; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[DEC]], i1 false)209; CHECK-NEXT: [[SUB:%.*]] = sub nuw nsw i32 33, [[CTLZ]]210; CHECK-NEXT: [[SHL:%.*]] = shl nuw i32 1, [[SUB]]211; CHECK-NEXT: [[UGT:%.*]] = icmp ugt i32 [[X]], 1212; CHECK-NEXT: [[SEL:%.*]] = select i1 [[UGT]], i32 [[SHL]], i32 1213; CHECK-NEXT: ret i32 [[SEL]]214;215 %dec = add i32 %x, -1216 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %dec, i1 false)217 %sub = sub i32 33, %ctlz218 %shl = shl i32 1, %sub219 %ugt = icmp ugt i32 %x, 1220 %sel = select i1 %ugt, i32 %shl, i32 1221 ret i32 %sel222}223 224; Negative test: the shl result used twice225define i32 @bit_ceil_32_shl_used_twice(i32 %x, ptr %p) {226; CHECK-LABEL: @bit_ceil_32_shl_used_twice(227; CHECK-NEXT: [[DEC:%.*]] = add i32 [[X:%.*]], -1228; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[DEC]], i1 false)229; CHECK-NEXT: [[SUB:%.*]] = sub nuw nsw i32 32, [[CTLZ]]230; CHECK-NEXT: [[SHL:%.*]] = shl nuw i32 1, [[SUB]]231; CHECK-NEXT: [[UGT:%.*]] = icmp ugt i32 [[X]], 1232; CHECK-NEXT: [[SEL:%.*]] = select i1 [[UGT]], i32 [[SHL]], i32 1233; CHECK-NEXT: store i32 [[SHL]], ptr [[P:%.*]], align 4234; CHECK-NEXT: ret i32 [[SEL]]235;236 %dec = add i32 %x, -1237 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %dec, i1 false)238 %sub = sub i32 32, %ctlz239 %shl = shl i32 1, %sub240 %ugt = icmp ugt i32 %x, 1241 %sel = select i1 %ugt, i32 %shl, i32 1242 store i32 %shl, ptr %p, align 4243 ret i32 %sel244}245 246; Negative test: the sub result used twice247define i32 @bit_ceil_32_sub_used_twice(i32 %x, ptr %p) {248; CHECK-LABEL: @bit_ceil_32_sub_used_twice(249; CHECK-NEXT: [[DEC:%.*]] = add i32 [[X:%.*]], -1250; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[DEC]], i1 false)251; CHECK-NEXT: [[SUB:%.*]] = sub nuw nsw i32 32, [[CTLZ]]252; CHECK-NEXT: [[SHL:%.*]] = shl nuw i32 1, [[SUB]]253; CHECK-NEXT: [[UGT:%.*]] = icmp ugt i32 [[X]], 1254; CHECK-NEXT: [[SEL:%.*]] = select i1 [[UGT]], i32 [[SHL]], i32 1255; CHECK-NEXT: store i32 [[SUB]], ptr [[P:%.*]], align 4256; CHECK-NEXT: ret i32 [[SEL]]257;258 %dec = add i32 %x, -1259 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %dec, i1 false)260 %sub = sub i32 32, %ctlz261 %shl = shl i32 1, %sub262 %ugt = icmp ugt i32 %x, 1263 %sel = select i1 %ugt, i32 %shl, i32 1264 store i32 %sub, ptr %p, align 4265 ret i32 %sel266}267 268; a vector version of @bit_ceil_32 above269define <4 x i32> @bit_ceil_v4i32(<4 x i32> %x) {270; CHECK-LABEL: @bit_ceil_v4i32(271; CHECK-NEXT: [[DEC:%.*]] = add <4 x i32> [[X:%.*]], splat (i32 -1)272; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) <4 x i32> @llvm.ctlz.v4i32(<4 x i32> [[DEC]], i1 false)273; CHECK-NEXT: [[TMP1:%.*]] = sub nsw <4 x i32> zeroinitializer, [[CTLZ]]274; CHECK-NEXT: [[TMP2:%.*]] = and <4 x i32> [[TMP1]], splat (i32 31)275; CHECK-NEXT: [[SEL:%.*]] = shl nuw <4 x i32> splat (i32 1), [[TMP2]]276; CHECK-NEXT: ret <4 x i32> [[SEL]]277;278 %dec = add <4 x i32> %x, <i32 -1, i32 -1, i32 -1, i32 -1>279 %ctlz = tail call <4 x i32> @llvm.ctlz.v4i32(<4 x i32> %dec, i1 false)280 %sub = sub <4 x i32> <i32 32, i32 32, i32 32, i32 32>, %ctlz281 %shl = shl <4 x i32> <i32 1, i32 1, i32 1, i32 1>, %sub282 %ugt = icmp ugt <4 x i32> %x, <i32 1, i32 1, i32 1, i32 1>283 %sel = select <4 x i1> %ugt, <4 x i32> %shl, <4 x i32> <i32 1, i32 1, i32 1, i32 1>284 ret <4 x i32> %sel285}286 287define i32 @pr91691(i32 %0) {288; CHECK-LABEL: @pr91691(289; CHECK-NEXT: [[TMP2:%.*]] = sub i32 -2, [[TMP0:%.*]]290; CHECK-NEXT: [[TMP3:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[TMP2]], i1 false)291; CHECK-NEXT: [[TMP4:%.*]] = sub nsw i32 0, [[TMP3]]292; CHECK-NEXT: [[TMP5:%.*]] = and i32 [[TMP4]], 31293; CHECK-NEXT: [[TMP6:%.*]] = shl nuw i32 1, [[TMP5]]294; CHECK-NEXT: ret i32 [[TMP6]]295;296 %2 = sub nuw i32 -2, %0297 %3 = tail call i32 @llvm.ctlz.i32(i32 %2, i1 false)298 %4 = sub i32 32, %3299 %5 = shl i32 1, %4300 %6 = icmp ult i32 %0, -2301 %7 = select i1 %6, i32 %5, i32 1302 ret i32 %7303}304 305define i32 @pr91691_drop_nsw(i32 %0) {306; CHECK-LABEL: @pr91691_drop_nsw(307; CHECK-NEXT: [[TMP2:%.*]] = sub i32 -2, [[TMP0:%.*]]308; CHECK-NEXT: [[TMP3:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[TMP2]], i1 false)309; CHECK-NEXT: [[TMP4:%.*]] = sub nsw i32 0, [[TMP3]]310; CHECK-NEXT: [[TMP5:%.*]] = and i32 [[TMP4]], 31311; CHECK-NEXT: [[TMP6:%.*]] = shl nuw i32 1, [[TMP5]]312; CHECK-NEXT: ret i32 [[TMP6]]313;314 %2 = sub nsw i32 -2, %0315 %3 = tail call i32 @llvm.ctlz.i32(i32 %2, i1 false)316 %4 = sub i32 32, %3317 %5 = shl i32 1, %4318 %6 = icmp ult i32 %0, -2319 %7 = select i1 %6, i32 %5, i32 1320 ret i32 %7321}322 323define i32 @test_drop_range_attr(i32 %x) {324; CHECK-LABEL: @test_drop_range_attr(325; CHECK-NEXT: [[CTLZ:%.*]] = call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[X:%.*]], i1 false)326; CHECK-NEXT: [[TMP1:%.*]] = sub nsw i32 0, [[CTLZ]]327; CHECK-NEXT: [[TMP2:%.*]] = and i32 [[TMP1]], 31328; CHECK-NEXT: [[SEL:%.*]] = shl nuw i32 1, [[TMP2]]329; CHECK-NEXT: ret i32 [[SEL]]330;331 %ctlz = call range(i32 1, 33) i32 @llvm.ctlz.i32(i32 %x, i1 false)332 %sub = sub i32 32, %ctlz333 %shl = shl i32 1, %sub334 %dec = add i32 %x, -1335 %ult = icmp ult i32 %dec, -2336 %sel = select i1 %ult, i32 %shl, i32 1337 ret i32 %sel338}339 340define i32 @bit_ceil_plus_nsw(i32 %x) {341; CHECK-LABEL: @bit_ceil_plus_nsw(342; CHECK-NEXT: entry:343; CHECK-NEXT: [[SUB:%.*]] = add i32 [[X:%.*]], 1344; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[SUB]], i1 false)345; CHECK-NEXT: [[TMP0:%.*]] = sub nsw i32 0, [[CTLZ]]346; CHECK-NEXT: [[TMP1:%.*]] = and i32 [[TMP0]], 31347; CHECK-NEXT: [[SEL:%.*]] = shl nuw i32 1, [[TMP1]]348; CHECK-NEXT: ret i32 [[SEL]]349;350entry:351 %sub = add nsw i32 %x, 1352 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %sub, i1 false)353 %sub2 = sub nuw nsw i32 32, %ctlz354 %shl = shl nuw i32 1, %sub2355 %ult = icmp ult i32 %x, 2147483647356 %sel = select i1 %ult, i32 %shl, i32 1357 ret i32 %sel358}359 360define i32 @bit_ceil_plus_nuw(i32 %x) {361; CHECK-LABEL: @bit_ceil_plus_nuw(362; CHECK-NEXT: entry:363; CHECK-NEXT: [[SUB:%.*]] = add i32 [[X:%.*]], 1364; CHECK-NEXT: [[CTLZ:%.*]] = tail call range(i32 0, 33) i32 @llvm.ctlz.i32(i32 [[SUB]], i1 false)365; CHECK-NEXT: [[TMP0:%.*]] = sub nsw i32 0, [[CTLZ]]366; CHECK-NEXT: [[SUB2:%.*]] = and i32 [[TMP0]], 31367; CHECK-NEXT: [[SHL:%.*]] = shl nuw i32 1, [[SUB2]]368; CHECK-NEXT: ret i32 [[SHL]]369;370entry:371 %sub = add nuw i32 %x, 1372 %ctlz = tail call i32 @llvm.ctlz.i32(i32 %sub, i1 false)373 %sub2 = sub nuw nsw i32 32, %ctlz374 %shl = shl nuw i32 1, %sub2375 %ult = icmp ult i32 %x, 2147483647376 %sel = select i1 %ult, i32 %shl, i32 1377 ret i32 %sel378}379 380declare i32 @llvm.ctlz.i32(i32, i1 immarg)381declare i64 @llvm.ctlz.i64(i64, i1 immarg)382declare <4 x i32> @llvm.ctlz.v4i32(<4 x i32>, i1)383