[DAGCombiner] Add target hook function to decide folding (mul (add x, c1), c2)
[llvm-project.git] / llvm / test / Transforms / AggressiveInstCombine / popcount.ll
blob2b4c03cd88c67a58fa3ef1d215b022579fab6c46
1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2 ; RUN: opt < %s -aggressive-instcombine -S | FileCheck %s
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]]
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 
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;
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]]
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
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;
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]]
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
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;
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]]
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 
134 ;vector unsigned char popcount8vec(vector unsigned char i)
136 ;  i = i - ((i>> 1) & 0x55);
137 ;  i = (i & 0x33) + ((i >> 2) & 0x33);
138 ;  i = ((i + (i >> 4)) & 0x0F);
139 ;  return (i * 0x01);
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]]
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
168 ;vector unsigned int popcount32vec(vector unsigned int i)
170 ;  i = i - ((i>> 1) & 0x55555555);
171 ;  i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
172 ;  i = ((i + (i >> 4)) & 0x0F0F0F0F);
173 ;  return (i * 0x01010101) >> 24;
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]]
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