242 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt < %s -passes=aggressive-instcombine -S | FileCheck %s3 4;int popcount8(unsigned char i) {5; i = i - ((i >> 1) & 0x55);6; i = (i & 0x33) + ((i >> 2) & 0x33);7; i = ((i + (i >> 4)) & 0x0F);8; return (i * 0x01010101);9;}10define signext i32 @popcount8(i8 zeroext %0) {11; CHECK-LABEL: @popcount8(12; CHECK-NEXT: [[TMP2:%.*]] = lshr i8 [[TMP0:%.*]], 113; CHECK-NEXT: [[TMP3:%.*]] = and i8 [[TMP2]], 8514; CHECK-NEXT: [[TMP4:%.*]] = sub i8 [[TMP0]], [[TMP3]]15; CHECK-NEXT: [[TMP5:%.*]] = and i8 [[TMP4]], 5116; CHECK-NEXT: [[TMP6:%.*]] = lshr i8 [[TMP4]], 217; CHECK-NEXT: [[TMP7:%.*]] = and i8 [[TMP6]], 5118; CHECK-NEXT: [[TMP8:%.*]] = add nuw nsw i8 [[TMP7]], [[TMP5]]19; CHECK-NEXT: [[TMP9:%.*]] = lshr i8 [[TMP8]], 420; CHECK-NEXT: [[TMP10:%.*]] = add nuw nsw i8 [[TMP9]], [[TMP8]]21; CHECK-NEXT: [[TMP11:%.*]] = and i8 [[TMP10]], 1522; CHECK-NEXT: [[TMP12:%.*]] = zext i8 [[TMP11]] to i3223; CHECK-NEXT: ret i32 [[TMP12]]24;25 %2 = lshr i8 %0, 126 %3 = and i8 %2, 8527 %4 = sub i8 %0, %328 %5 = and i8 %4, 5129 %6 = lshr i8 %4, 230 %7 = and i8 %6, 5131 %8 = add nuw nsw i8 %7, %532 %9 = lshr i8 %8, 433 %10 = add nuw nsw i8 %9, %834 %11 = and i8 %10, 1535 %12 = zext i8 %11 to i3236 ret i32 %1237}38 39;int popcount32(unsigned i) {40; i = i - ((i >> 1) & 0x55555555);41; i = (i & 0x33333333) + ((i >> 2) & 0x33333333);42; i = ((i + (i >> 4)) & 0x0F0F0F0F);43; return (i * 0x01010101) >> 24;44;}45define signext i32 @popcount32(i32 zeroext %0) {46; CHECK-LABEL: @popcount32(47; CHECK-NEXT: [[TMP2:%.*]] = call i32 @llvm.ctpop.i32(i32 [[TMP0:%.*]])48; CHECK-NEXT: ret i32 [[TMP2]]49;50 %2 = lshr i32 %0, 151 %3 = and i32 %2, 143165576552 %4 = sub i32 %0, %353 %5 = and i32 %4, 85899345954 %6 = lshr i32 %4, 255 %7 = and i32 %6, 85899345956 %8 = add nuw nsw i32 %7, %557 %9 = lshr i32 %8, 458 %10 = add nuw nsw i32 %9, %859 %11 = and i32 %10, 25264513560 %12 = mul i32 %11, 1684300961 %13 = lshr i32 %12, 2462 ret i32 %1363}64 65;int popcount64(unsigned long long i) {66; i = i - ((i >> 1) & 0x5555555555555555);67; i = (i & 0x3333333333333333) + ((i >> 2) & 0x3333333333333333);68; i = ((i + (i >> 4)) & 0x0F0F0F0F0F0F0F0F);69; return (i * 0x0101010101010101) >> 56;70;}71define signext i32 @popcount64(i64 %0) {72; CHECK-LABEL: @popcount64(73; CHECK-NEXT: [[TMP2:%.*]] = call i64 @llvm.ctpop.i64(i64 [[TMP0:%.*]])74; CHECK-NEXT: [[TMP3:%.*]] = trunc i64 [[TMP2]] to i3275; CHECK-NEXT: ret i32 [[TMP3]]76;77 %2 = lshr i64 %0, 178 %3 = and i64 %2, 614891469123651720579 %4 = sub i64 %0, %380 %5 = and i64 %4, 368934881474191032381 %6 = lshr i64 %4, 282 %7 = and i64 %6, 368934881474191032383 %8 = add nuw nsw i64 %7, %584 %9 = lshr i64 %8, 485 %10 = add nuw nsw i64 %9, %886 %11 = and i64 %10, 108510259257115009587 %12 = mul i64 %11, 7234017283807667388 %13 = lshr i64 %12, 5689 %14 = trunc i64 %13 to i3290 ret i32 %1491}92 93;int popcount128(__uint128_t i) {94; __uint128_t x = 0x5555555555555555;95; x <<= 64;96; x |= 0x5555555555555555;97; __uint128_t y = 0x3333333333333333;98; y <<= 64;99; y |= 0x3333333333333333;100; __uint128_t z = 0x0f0f0f0f0f0f0f0f;101; z <<= 64;102; z |= 0x0f0f0f0f0f0f0f0f;103; __uint128_t a = 0x0101010101010101;104; a <<= 64;105; a |= 0x0101010101010101;106; unsigned mask = 120;107; i = i - ((i >> 1) & x);108; i = (i & y) + ((i >> 2) & y);109; i = ((i + (i >> 4)) & z);110; return (i * a) >> mask;111;}112define signext i32 @popcount128(i128 %0) {113; CHECK-LABEL: @popcount128(114; CHECK-NEXT: [[TMP2:%.*]] = call i128 @llvm.ctpop.i128(i128 [[TMP0:%.*]])115; CHECK-NEXT: [[TMP3:%.*]] = trunc i128 [[TMP2]] to i32116; CHECK-NEXT: ret i32 [[TMP3]]117;118 %2 = lshr i128 %0, 1119 %3 = and i128 %2, 113427455640312821154458202477256070485120 %4 = sub i128 %0, %3121 %5 = and i128 %4, 68056473384187692692674921486353642291122 %6 = lshr i128 %4, 2123 %7 = and i128 %6, 68056473384187692692674921486353642291124 %8 = add nuw nsw i128 %7, %5125 %9 = lshr i128 %8, 4126 %10 = add nuw nsw i128 %9, %8127 %11 = and i128 %10, 20016609818878733144904388672456953615128 %12 = mul i128 %11, 1334440654591915542993625911497130241129 %13 = lshr i128 %12, 120130 %14 = trunc i128 %13 to i32131 ret i32 %14132}133 134;vector unsigned char popcount8vec(vector unsigned char i)135;{136; i = i - ((i>> 1) & 0x55);137; i = (i & 0x33) + ((i >> 2) & 0x33);138; i = ((i + (i >> 4)) & 0x0F);139; return (i * 0x01);140;}141define <16 x i8> @popcount8vec(<16 x i8> %0) {142; CHECK-LABEL: @popcount8vec(143; CHECK-NEXT: [[TMP2:%.*]] = lshr <16 x i8> [[TMP0:%.*]], splat (i8 1)144; CHECK-NEXT: [[TMP3:%.*]] = and <16 x i8> [[TMP2]], splat (i8 85)145; CHECK-NEXT: [[TMP4:%.*]] = sub <16 x i8> [[TMP0]], [[TMP3]]146; CHECK-NEXT: [[TMP5:%.*]] = and <16 x i8> [[TMP4]], splat (i8 51)147; CHECK-NEXT: [[TMP6:%.*]] = lshr <16 x i8> [[TMP4]], splat (i8 2)148; CHECK-NEXT: [[TMP7:%.*]] = and <16 x i8> [[TMP6]], splat (i8 51)149; CHECK-NEXT: [[TMP8:%.*]] = add nuw nsw <16 x i8> [[TMP7]], [[TMP5]]150; CHECK-NEXT: [[TMP9:%.*]] = lshr <16 x i8> [[TMP8]], splat (i8 4)151; CHECK-NEXT: [[TMP10:%.*]] = add nuw nsw <16 x i8> [[TMP9]], [[TMP8]]152; CHECK-NEXT: [[TMP11:%.*]] = and <16 x i8> [[TMP10]], splat (i8 15)153; CHECK-NEXT: ret <16 x i8> [[TMP11]]154;155 %2 = lshr <16 x i8> %0, <i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1, i8 1>156 %3 = and <16 x i8> %2, <i8 85, i8 85, i8 85, i8 85, i8 85, i8 85, i8 85, i8 85, i8 85, i8 85, i8 85, i8 85, i8 85, i8 85, i8 85, i8 85>157 %4 = sub <16 x i8> %0, %3158 %5 = and <16 x i8> %4, <i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51>159 %6 = lshr <16 x i8> %4, <i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2, i8 2>160 %7 = and <16 x i8> %6, <i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51, i8 51>161 %8 = add nuw nsw <16 x i8> %7, %5162 %9 = lshr <16 x i8> %8, <i8 4, i8 4, i8 4, i8 4, i8 4, i8 4, i8 4, i8 4, i8 4, i8 4, i8 4, i8 4, i8 4, i8 4, i8 4, i8 4>163 %10 = add nuw nsw <16 x i8> %9, %8164 %11 = and <16 x i8> %10, <i8 15, i8 15, i8 15, i8 15, i8 15, i8 15, i8 15, i8 15, i8 15, i8 15, i8 15, i8 15, i8 15, i8 15, i8 15, i8 15>165 ret <16 x i8> %11166}167 168;vector unsigned int popcount32vec(vector unsigned int i)169;{170; i = i - ((i>> 1) & 0x55555555);171; i = (i & 0x33333333) + ((i >> 2) & 0x33333333);172; i = ((i + (i >> 4)) & 0x0F0F0F0F);173; return (i * 0x01010101) >> 24;174;}175define <4 x i32> @popcount32vec(<4 x i32> %0) {176; CHECK-LABEL: @popcount32vec(177; CHECK-NEXT: [[TMP2:%.*]] = call <4 x i32> @llvm.ctpop.v4i32(<4 x i32> [[TMP0:%.*]])178; CHECK-NEXT: ret <4 x i32> [[TMP2]]179;180 %2 = lshr <4 x i32> %0, <i32 1, i32 1, i32 1, i32 1>181 %3 = and <4 x i32> %2, <i32 1431655765, i32 1431655765, i32 1431655765, i32 1431655765>182 %4 = sub <4 x i32> %0, %3183 %5 = and <4 x i32> %4, <i32 858993459, i32 858993459, i32 858993459, i32 858993459>184 %6 = lshr <4 x i32> %4, <i32 2, i32 2, i32 2, i32 2>185 %7 = and <4 x i32> %6, <i32 858993459, i32 858993459, i32 858993459, i32 858993459>186 %8 = add nuw nsw <4 x i32> %7, %5187 %9 = lshr <4 x i32> %8, <i32 4, i32 4, i32 4, i32 4>188 %10 = add nuw nsw <4 x i32> %9, %8189 %11 = and <4 x i32> %10, <i32 252645135, i32 252645135, i32 252645135, i32 252645135>190 %12 = mul <4 x i32> %11, <i32 16843009, i32 16843009, i32 16843009, i32 16843009>191 %13 = lshr <4 x i32> %12, <i32 24, i32 24, i32 24, i32 24>192 ret <4 x i32> %13193}194 195define i32 @popcount64_zext(i32 %x) {196; CHECK-LABEL: @popcount64_zext(197; CHECK-NEXT: [[ZEXT:%.*]] = zext i32 [[X:%.*]] to i64198; CHECK-NEXT: [[TMP12:%.*]] = call i64 @llvm.ctpop.i64(i64 [[ZEXT]])199; CHECK-NEXT: [[TMP13:%.*]] = trunc nuw nsw i64 [[TMP12]] to i32200; CHECK-NEXT: ret i32 [[TMP13]]201;202 %zext = zext i32 %x to i64203 %1 = lshr i64 %zext, 1204 %2 = and i64 %1, 1431655765205 %3 = sub nsw i64 %zext, %2206 %4 = and i64 %3, 3689348814741910323207 %5 = lshr i64 %3, 2208 %6 = and i64 %5, 3689348814741910323209 %7 = add nuw nsw i64 %6, %4210 %8 = lshr i64 %7, 4211 %9 = add nuw nsw i64 %8, %7212 %10 = and i64 %9, 1085102592571150095213 %11 = mul i64 %10, 72340172838076673214 %12 = lshr i64 %11, 56215 %13 = trunc nuw nsw i64 %12 to i32216 ret i32 %13217}218 219define i32 @popcount64_mask(i64 %x) {220; CHECK-LABEL: @popcount64_mask(221; CHECK-NEXT: [[MASK:%.*]] = and i64 [[X:%.*]], -281470681808896222; CHECK-NEXT: [[TMP12:%.*]] = call i64 @llvm.ctpop.i64(i64 [[MASK]])223; CHECK-NEXT: [[TMP13:%.*]] = trunc nuw nsw i64 [[TMP12]] to i32224; CHECK-NEXT: ret i32 [[TMP13]]225;226 %mask = and i64 %x, -281470681808896 ; 0xffff0000ffff0000227 %1 = lshr i64 %mask, 1228 %2 = and i64 %1, 6148820867675914240 ; 0x0x5555000055550000229 %3 = sub nsw i64 %mask, %2230 %4 = and i64 %3, 3689348814741910323231 %5 = lshr i64 %3, 2232 %6 = and i64 %5, 3689348814741910323233 %7 = add nuw nsw i64 %6, %4234 %8 = lshr i64 %7, 4235 %9 = add nuw nsw i64 %8, %7236 %10 = and i64 %9, 1085102592571150095237 %11 = mul i64 %10, 72340172838076673238 %12 = lshr i64 %11, 56239 %13 = trunc nuw nsw i64 %12 to i32240 ret i32 %13241}242