llvm/test/Transforms/AggressiveInstCombine/popcount.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
   2 ; RUN: opt < %s -aggressive-instcombine -S | FileCheck %s
   3
   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 ;}
  10 define signext i32 @popcount8(i8 zeroext %0) {
  11 ; CHECK-LABEL: @popcount8(
  12 ; CHECK-NEXT:    [[TMP2:%.*]] = lshr i8 [[TMP0:%.*]], 1
  13 ; CHECK-NEXT:    [[TMP3:%.*]] = and i8 [[TMP2]], 85
  14 ; CHECK-NEXT:    [[TMP4:%.*]] = sub i8 [[TMP0]], [[TMP3]]
  15 ; CHECK-NEXT:    [[TMP5:%.*]] = and i8 [[TMP4]], 51
  16 ; CHECK-NEXT:    [[TMP6:%.*]] = lshr i8 [[TMP4]], 2
  17 ; CHECK-NEXT:    [[TMP7:%.*]] = and i8 [[TMP6]], 51
  18 ; CHECK-NEXT:    [[TMP8:%.*]] = add nuw nsw i8 [[TMP7]], [[TMP5]]
  19 ; CHECK-NEXT:    [[TMP9:%.*]] = lshr i8 [[TMP8]], 4
  20 ; CHECK-NEXT:    [[TMP10:%.*]] = add nuw nsw i8 [[TMP9]], [[TMP8]]
  21 ; CHECK-NEXT:    [[TMP11:%.*]] = and i8 [[TMP10]], 15
  22 ; CHECK-NEXT:    [[TMP12:%.*]] = zext i8 [[TMP11]] to i32
  23 ; CHECK-NEXT:    ret i32 [[TMP12]]
  24 ;
  25   %2 = lshr i8 %0, 1
  26   %3 = and i8 %2, 85
  27   %4 = sub i8 %0, %3
  28   %5 = and i8 %4, 51
  29   %6 = lshr i8 %4, 2
  30   %7 = and i8 %6, 51
  31   %8 = add nuw nsw i8 %7, %5
  32   %9 = lshr i8 %8, 4
  33   %10 = add nuw nsw i8 %9, %8
  34   %11 = and i8 %10, 15
  35   %12 = zext i8 %11 to i32
  36   ret i32 %12
  37 }
  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 ;}
  45 define 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, 1
  51   %3 = and i32 %2, 1431655765
  52   %4 = sub i32 %0, %3
  53   %5 = and i32 %4, 858993459
  54   %6 = lshr i32 %4, 2
  55   %7 = and i32 %6, 858993459
  56   %8 = add nuw nsw i32 %7, %5
  57   %9 = lshr i32 %8, 4
  58   %10 = add nuw nsw i32 %9, %8
  59   %11 = and i32 %10, 252645135
  60   %12 = mul i32 %11, 16843009
  61   %13 = lshr i32 %12, 24
  62   ret i32 %13
  63 }
  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 ;}
  71 define 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 i32
  75 ; CHECK-NEXT:    ret i32 [[TMP3]]
  76 ;
  77   %2 = lshr i64 %0, 1
  78   %3 = and i64 %2, 6148914691236517205
  79   %4 = sub i64 %0, %3
  80   %5 = and i64 %4, 3689348814741910323
  81   %6 = lshr i64 %4, 2
  82   %7 = and i64 %6, 3689348814741910323
  83   %8 = add nuw nsw i64 %7, %5
  84   %9 = lshr i64 %8, 4
  85   %10 = add nuw nsw i64 %9, %8
  86   %11 = and i64 %10, 1085102592571150095
  87   %12 = mul i64 %11, 72340172838076673
  88   %13 = lshr i64 %12, 56
  89   %14 = trunc i64 %13 to i32
  90   ret i32 %14
  91 }
  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 ;}
 112 define 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 i32
 116 ; CHECK-NEXT:    ret i32 [[TMP3]]
 117 ;
 118   %2 = lshr i128 %0, 1
 119   %3 = and i128 %2, 113427455640312821154458202477256070485
 120   %4 = sub i128 %0, %3
 121   %5 = and i128 %4, 68056473384187692692674921486353642291
 122   %6 = lshr i128 %4, 2
 123   %7 = and i128 %6, 68056473384187692692674921486353642291
 124   %8 = add nuw nsw i128 %7, %5
 125   %9 = lshr i128 %8, 4
 126   %10 = add nuw nsw i128 %9, %8
 127   %11 = and i128 %10, 20016609818878733144904388672456953615
 128   %12 = mul i128 %11, 1334440654591915542993625911497130241
 129   %13 = lshr i128 %12, 120
 130   %14 = trunc i128 %13 to i32
 131   ret i32 %14
 132 }
 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 ;}
 141 define <16 x i8> @popcount8vec(<16 x i8> %0) {
 142 ; CHECK-LABEL: @popcount8vec(
 143 ; 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>
 144 ; 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>
 145 ; CHECK-NEXT:    [[TMP4:%.*]] = sub <16 x i8> [[TMP0]], [[TMP3]]
 146 ; 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>
 147 ; 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>
 148 ; 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>
 149 ; CHECK-NEXT:    [[TMP8:%.*]] = add nuw nsw <16 x i8> [[TMP7]], [[TMP5]]
 150 ; 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>
 151 ; CHECK-NEXT:    [[TMP10:%.*]] = add nuw nsw <16 x i8> [[TMP9]], [[TMP8]]
 152 ; 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>
 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, %3
 158   %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, %5
 162   %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, %8
 164   %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> %11
 166 }
 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 ;}
 175 define <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, %3
 183   %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, %5
 187   %9 = lshr <4 x i32> %8, <i32 4, i32 4, i32 4, i32 4>
 188   %10 = add nuw nsw <4 x i32> %9, %8
 189   %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> %13
 193 }