; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt < %s -passes=aggressive-instcombine -S | FileCheck %s

;int popcount8(unsigned char i) {
;  i = i - ((i >> 1) & 0x55);
;  i = (i & 0x33) + ((i >> 2) & 0x33);
;  i = ((i + (i >> 4)) & 0x0F);
; return (i * 0x01010101);
;}
define signext i32 @popcount8(i8 zeroext %0) {
; CHECK-LABEL: @popcount8(
; CHECK-NEXT:    [[TMP2:%.*]] = lshr i8 [[TMP0:%.*]], 1
; CHECK-NEXT:    [[TMP3:%.*]] = and i8 [[TMP2]], 85
; CHECK-NEXT:    [[TMP4:%.*]] = sub i8 [[TMP0]], [[TMP3]]
; CHECK-NEXT:    [[TMP5:%.*]] = and i8 [[TMP4]], 51
; CHECK-NEXT:    [[TMP6:%.*]] = lshr i8 [[TMP4]], 2
; CHECK-NEXT:    [[TMP7:%.*]] = and i8 [[TMP6]], 51
; CHECK-NEXT:    [[TMP8:%.*]] = add nuw nsw i8 [[TMP7]], [[TMP5]]
; CHECK-NEXT:    [[TMP9:%.*]] = lshr i8 [[TMP8]], 4
; CHECK-NEXT:    [[TMP10:%.*]] = add nuw nsw i8 [[TMP9]], [[TMP8]]
; CHECK-NEXT:    [[TMP11:%.*]] = and i8 [[TMP10]], 15
; CHECK-NEXT:    [[TMP12:%.*]] = zext i8 [[TMP11]] to i32 
; CHECK-NEXT:    ret i32 [[TMP12]]
;
  %2 = lshr i8 %0, 1
  %3 = and i8 %2, 85
  %4 = sub i8 %0, %3
  %5 = and i8 %4, 51
  %6 = lshr i8 %4, 2
  %7 = and i8 %6, 51
  %8 = add nuw nsw i8 %7, %5
  %9 = lshr i8 %8, 4
  %10 = add nuw nsw i8 %9, %8
  %11 = and i8 %10, 15
  %12 = zext i8 %11 to i32 
  ret i32 %12 
}

;int popcount32(unsigned i) {
;  i = i - ((i >> 1) & 0x55555555);
;  i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
;  i = ((i + (i >> 4)) & 0x0F0F0F0F);
; return (i * 0x01010101) >> 24;
;}
define signext i32 @popcount32(i32 zeroext %0) {
; CHECK-LABEL: @popcount32(
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.ctpop.i32(i32 [[TMP0:%.*]])
; CHECK-NEXT:    ret i32 [[TMP2]]
;
  %2 = lshr i32 %0, 1
  %3 = and i32 %2, 1431655765
  %4 = sub i32 %0, %3
  %5 = and i32 %4, 858993459
  %6 = lshr i32 %4, 2
  %7 = and i32 %6, 858993459
  %8 = add nuw nsw i32 %7, %5
  %9 = lshr i32 %8, 4
  %10 = add nuw nsw i32 %9, %8
  %11 = and i32 %10, 252645135
  %12 = mul i32 %11, 16843009
  %13 = lshr i32 %12, 24
  ret i32 %13
}

;int popcount64(unsigned long long i) {
;  i = i - ((i >> 1) & 0x5555555555555555);
;  i = (i & 0x3333333333333333) + ((i >> 2) & 0x3333333333333333);
;  i = ((i + (i >> 4)) & 0x0F0F0F0F0F0F0F0F);
; return (i * 0x0101010101010101) >> 56;
;}
define signext i32 @popcount64(i64 %0) {
; CHECK-LABEL: @popcount64(
; CHECK-NEXT:    [[TMP2:%.*]] = call i64 @llvm.ctpop.i64(i64 [[TMP0:%.*]])
; CHECK-NEXT:    [[TMP3:%.*]] = trunc i64 [[TMP2]] to i32
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %2 = lshr i64 %0, 1
  %3 = and i64 %2, 6148914691236517205
  %4 = sub i64 %0, %3
  %5 = and i64 %4, 3689348814741910323
  %6 = lshr i64 %4, 2
  %7 = and i64 %6, 3689348814741910323
  %8 = add nuw nsw i64 %7, %5
  %9 = lshr i64 %8, 4
  %10 = add nuw nsw i64 %9, %8
  %11 = and i64 %10, 1085102592571150095
  %12 = mul i64 %11, 72340172838076673
  %13 = lshr i64 %12, 56
  %14 = trunc i64 %13 to i32
  ret i32 %14
}

;int popcount128(__uint128_t i) {
;  __uint128_t x = 0x5555555555555555;
;  x <<= 64;
;  x |= 0x5555555555555555;
;  __uint128_t y = 0x3333333333333333;
;  y <<= 64;
;  y |= 0x3333333333333333;
;  __uint128_t z = 0x0f0f0f0f0f0f0f0f;
;  z <<= 64; 
;  z |= 0x0f0f0f0f0f0f0f0f;
;  __uint128_t a = 0x0101010101010101;
;  a <<= 64;
;  a |= 0x0101010101010101;
;  unsigned mask = 120;
;  i = i - ((i >> 1) & x);
;  i = (i & y) + ((i >> 2) & y);
;  i = ((i + (i >> 4)) & z);
;  return (i * a) >> mask;
;}
define signext i32 @popcount128(i128 %0) {
; CHECK-LABEL: @popcount128(
; CHECK-NEXT:    [[TMP2:%.*]] = call i128 @llvm.ctpop.i128(i128 [[TMP0:%.*]])
; CHECK-NEXT:    [[TMP3:%.*]] = trunc i128 [[TMP2]] to i32 
; CHECK-NEXT:    ret i32 [[TMP3]]
;
  %2 = lshr i128 %0, 1
  %3 = and i128 %2, 113427455640312821154458202477256070485
  %4 = sub i128 %0, %3
  %5 = and i128 %4, 68056473384187692692674921486353642291
  %6 = lshr i128 %4, 2
  %7 = and i128 %6, 68056473384187692692674921486353642291
  %8 = add nuw nsw i128 %7, %5
  %9 = lshr i128 %8, 4
  %10 = add nuw nsw i128 %9, %8
  %11 = and i128 %10, 20016609818878733144904388672456953615
  %12 = mul i128 %11, 1334440654591915542993625911497130241
  %13 = lshr i128 %12, 120 
  %14 = trunc i128 %13 to i32 
  ret i32 %14 
}

;vector unsigned char popcount8vec(vector unsigned char i)
;{
;  i = i - ((i>> 1) & 0x55);
;  i = (i & 0x33) + ((i >> 2) & 0x33);
;  i = ((i + (i >> 4)) & 0x0F);
;  return (i * 0x01);
;}
define <16 x i8> @popcount8vec(<16 x i8> %0) {
; CHECK-LABEL: @popcount8vec(
; CHECK-NEXT:    [[TMP2:%.*]] = lshr <16 x i8> [[TMP0:%.*]], <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>
; CHECK-NEXT:    [[TMP3:%.*]] = and <16 x i8> [[TMP2]], <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>
; CHECK-NEXT:    [[TMP4:%.*]] = sub <16 x i8> [[TMP0]], [[TMP3]]
; CHECK-NEXT:    [[TMP5:%.*]] = and <16 x i8> [[TMP4]], <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>
; CHECK-NEXT:    [[TMP6:%.*]] = lshr <16 x i8> [[TMP4]], <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>
; CHECK-NEXT:    [[TMP7:%.*]] = and <16 x i8> [[TMP6]], <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>
; CHECK-NEXT:    [[TMP8:%.*]] = add nuw nsw <16 x i8> [[TMP7]], [[TMP5]]
; CHECK-NEXT:    [[TMP9:%.*]] = lshr <16 x i8> [[TMP8]], <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>
; CHECK-NEXT:    [[TMP10:%.*]] = add nuw nsw <16 x i8> [[TMP9]], [[TMP8]]
; CHECK-NEXT:    [[TMP11:%.*]] = and <16 x i8> [[TMP10]], <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>
; CHECK-NEXT:    ret <16 x i8> [[TMP11]]
;
  %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>
  %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>
  %4 = sub <16 x i8> %0, %3
  %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>
  %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>
  %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>
  %8 = add nuw nsw <16 x i8> %7, %5
  %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>
  %10 = add nuw nsw <16 x i8> %9, %8
  %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>
  ret <16 x i8> %11
}

;vector unsigned int popcount32vec(vector unsigned int i)
;{
;  i = i - ((i>> 1) & 0x55555555);
;  i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
;  i = ((i + (i >> 4)) & 0x0F0F0F0F);
;  return (i * 0x01010101) >> 24;
;}
define <4 x i32> @popcount32vec(<4 x i32> %0) {
; CHECK-LABEL: @popcount32vec(
; CHECK-NEXT:    [[TMP2:%.*]] = call <4 x i32> @llvm.ctpop.v4i32(<4 x i32> [[TMP0:%.*]])
; CHECK-NEXT:    ret <4 x i32> [[TMP2]]
;
  %2 = lshr <4 x i32> %0, <i32 1, i32 1, i32 1, i32 1>
  %3 = and <4 x i32> %2, <i32 1431655765, i32 1431655765, i32 1431655765, i32 1431655765>
  %4 = sub <4 x i32> %0, %3
  %5 = and <4 x i32> %4, <i32 858993459, i32 858993459, i32 858993459, i32 858993459>
  %6 = lshr <4 x i32> %4, <i32 2, i32 2, i32 2, i32 2>
  %7 = and <4 x i32> %6, <i32 858993459, i32 858993459, i32 858993459, i32 858993459>
  %8 = add nuw nsw <4 x i32> %7, %5
  %9 = lshr <4 x i32> %8, <i32 4, i32 4, i32 4, i32 4>
  %10 = add nuw nsw <4 x i32> %9, %8
  %11 = and <4 x i32> %10, <i32 252645135, i32 252645135, i32 252645135, i32 252645135>
  %12 = mul <4 x i32> %11, <i32 16843009, i32 16843009, i32 16843009, i32 16843009>
  %13 = lshr <4 x i32> %12, <i32 24, i32 24, i32 24, i32 24>
  ret <4 x i32> %13
}