1 #include "gc.h"
2
3 typedef struct Malg Malg;
4 typedef struct Mparam Mparam;
5
6 struct Malg
7 {
8 char vals[10];
9 };
10
11 struct Mparam
12 {
13 ulong value;
14 char alg;
15 char neg;
16 char shift;
17 char arg;
18 char off;
19 };
20
21 static Mparam multab[32];
22 static int mulptr;
23
24 static Malg malgs[] =
25 {
26 {0, 100},
27 {-1, 1, 100},
28 {-9, -5, -3, 3, 5, 9, 100},
29 {6, 10, 12, 18, 20, 24, 36, 40, 72, 100},
30 {-8, -4, -2, 2, 4, 8, 100},
31 };
32
33 /*
34 * return position of lowest 1
35 */
36 int
lowbit(ulong v)37 lowbit(ulong v)
38 {
39 int s, i;
40 ulong m;
41
42 s = 0;
43 m = 0xFFFFFFFFUL;
44 for(i = 16; i > 0; i >>= 1) {
45 m >>= i;
46 if((v & m) == 0) {
47 v >>= i;
48 s += i;
49 }
50 }
51 return s;
52 }
53
54 void
genmuladd(Node * d,Node * s,int m,Node * a)55 genmuladd(Node *d, Node *s, int m, Node *a)
56 {
57 Node nod;
58
59 nod.op = OINDEX;
60 nod.left = a;
61 nod.right = s;
62 nod.scale = m;
63 nod.type = types[TIND];
64 nod.xoffset = 0;
65 xcom(&nod);
66 gopcode(OADDR, d->type, &nod, d);
67 }
68
69 void
mulparam(ulong m,Mparam * mp)70 mulparam(ulong m, Mparam *mp)
71 {
72 int c, i, j, n, o, q, s;
73 int bc, bi, bn, bo, bq, bs, bt;
74 char *p;
75 long u;
76 ulong t;
77
78 bc = bq = 10;
79 bi = bn = bo = bs = bt = 0;
80 for(i = 0; i < nelem(malgs); i++) {
81 for(p = malgs[i].vals, j = 0; (o = p[j]) < 100; j++)
82 for(s = 0; s < 2; s++) {
83 c = 10;
84 q = 10;
85 u = m - o;
86 if(u == 0)
87 continue;
88 if(s) {
89 o = -o;
90 if(o > 0)
91 continue;
92 u = -u;
93 }
94 n = lowbit(u);
95 t = (ulong)u >> n;
96 switch(i) {
97 case 0:
98 if(t == 1) {
99 c = s + 1;
100 q = 0;
101 break;
102 }
103 switch(t) {
104 case 3:
105 case 5:
106 case 9:
107 c = s + 1;
108 if(n)
109 c++;
110 q = 0;
111 break;
112 }
113 if(s)
114 break;
115 switch(t) {
116 case 15:
117 case 25:
118 case 27:
119 case 45:
120 case 81:
121 c = 2;
122 if(n)
123 c++;
124 q = 1;
125 break;
126 }
127 break;
128 case 1:
129 if(t == 1) {
130 c = 3;
131 q = 3;
132 break;
133 }
134 switch(t) {
135 case 3:
136 case 5:
137 case 9:
138 c = 3;
139 q = 2;
140 break;
141 }
142 break;
143 case 2:
144 if(t == 1) {
145 c = 3;
146 q = 2;
147 break;
148 }
149 break;
150 case 3:
151 if(s)
152 break;
153 if(t == 1) {
154 c = 3;
155 q = 1;
156 break;
157 }
158 break;
159 case 4:
160 if(t == 1) {
161 c = 3;
162 q = 0;
163 break;
164 }
165 break;
166 }
167 if(c < bc || (c == bc && q > bq)) {
168 bc = c;
169 bi = i;
170 bn = n;
171 bo = o;
172 bq = q;
173 bs = s;
174 bt = t;
175 }
176 }
177 }
178 mp->value = m;
179 if(bc <= 3) {
180 mp->alg = bi;
181 mp->shift = bn;
182 mp->off = bo;
183 mp->neg = bs;
184 mp->arg = bt;
185 }
186 else
187 mp->alg = -1;
188 }
189
190 int
m0(int a)191 m0(int a)
192 {
193 switch(a) {
194 case -2:
195 case 2:
196 return 2;
197 case -3:
198 case 3:
199 return 2;
200 case -4:
201 case 4:
202 return 4;
203 case -5:
204 case 5:
205 return 4;
206 case 6:
207 return 2;
208 case -8:
209 case 8:
210 return 8;
211 case -9:
212 case 9:
213 return 8;
214 case 10:
215 return 4;
216 case 12:
217 return 2;
218 case 15:
219 return 2;
220 case 18:
221 return 8;
222 case 20:
223 return 4;
224 case 24:
225 return 2;
226 case 25:
227 return 4;
228 case 27:
229 return 2;
230 case 36:
231 return 8;
232 case 40:
233 return 4;
234 case 45:
235 return 4;
236 case 72:
237 return 8;
238 case 81:
239 return 8;
240 }
241 diag(Z, "bad m0");
242 return 0;
243 }
244
245 int
m1(int a)246 m1(int a)
247 {
248 switch(a) {
249 case 15:
250 return 4;
251 case 25:
252 return 4;
253 case 27:
254 return 8;
255 case 45:
256 return 8;
257 case 81:
258 return 8;
259 }
260 diag(Z, "bad m1");
261 return 0;
262 }
263
264 int
m2(int a)265 m2(int a)
266 {
267 switch(a) {
268 case 6:
269 return 2;
270 case 10:
271 return 2;
272 case 12:
273 return 4;
274 case 18:
275 return 2;
276 case 20:
277 return 4;
278 case 24:
279 return 8;
280 case 36:
281 return 4;
282 case 40:
283 return 8;
284 case 72:
285 return 8;
286 }
287 diag(Z, "bad m2");
288 return 0;
289 }
290
291 void
shiftit(Type * t,Node * s,Node * d)292 shiftit(Type *t, Node *s, Node *d)
293 {
294 long c;
295
296 c = (long)s->vconst & 31;
297 switch(c) {
298 case 0:
299 break;
300 case 1:
301 gopcode(OADD, t, d, d);
302 break;
303 default:
304 gopcode(OASHL, t, s, d);
305 }
306 }
307
308 static int
mulgen1(ulong v,Node * n)309 mulgen1(ulong v, Node *n)
310 {
311 int i, o;
312 Mparam *p;
313 Node nod, nods;
314
315 for(i = 0; i < nelem(multab); i++) {
316 p = &multab[i];
317 if(p->value == v)
318 goto found;
319 }
320
321 p = &multab[mulptr];
322 if(++mulptr == nelem(multab))
323 mulptr = 0;
324
325 mulparam(v, p);
326
327 found:
328 // print("v=%.lx a=%d n=%d s=%d g=%d o=%d \n", p->value, p->alg, p->neg, p->shift, p->arg, p->off);
329 if(p->alg < 0)
330 return 0;
331
332 nods = *nodconst(p->shift);
333
334 o = OADD;
335 if(p->alg > 0) {
336 regalloc(&nod, n, Z);
337 if(p->off < 0)
338 o = OSUB;
339 }
340
341 switch(p->alg) {
342 case 0:
343 switch(p->arg) {
344 case 1:
345 shiftit(n->type, &nods, n);
346 break;
347 case 15:
348 case 25:
349 case 27:
350 case 45:
351 case 81:
352 genmuladd(n, n, m1(p->arg), n);
353 /* fall thru */
354 case 3:
355 case 5:
356 case 9:
357 genmuladd(n, n, m0(p->arg), n);
358 shiftit(n->type, &nods, n);
359 break;
360 default:
361 goto bad;
362 }
363 if(p->neg == 1)
364 gins(ANEGL, Z, n);
365 break;
366 case 1:
367 switch(p->arg) {
368 case 1:
369 gmove(n, &nod);
370 shiftit(n->type, &nods, &nod);
371 break;
372 case 3:
373 case 5:
374 case 9:
375 genmuladd(&nod, n, m0(p->arg), n);
376 shiftit(n->type, &nods, &nod);
377 break;
378 default:
379 goto bad;
380 }
381 if(p->neg)
382 gopcode(o, n->type, &nod, n);
383 else {
384 gopcode(o, n->type, n, &nod);
385 gmove(&nod, n);
386 }
387 break;
388 case 2:
389 genmuladd(&nod, n, m0(p->off), n);
390 shiftit(n->type, &nods, n);
391 goto comop;
392 case 3:
393 genmuladd(&nod, n, m0(p->off), n);
394 shiftit(n->type, &nods, n);
395 genmuladd(n, &nod, m2(p->off), n);
396 break;
397 case 4:
398 genmuladd(&nod, n, m0(p->off), nodconst(0));
399 shiftit(n->type, &nods, n);
400 goto comop;
401 default:
402 diag(Z, "bad mul alg");
403 break;
404 comop:
405 if(p->neg) {
406 gopcode(o, n->type, n, &nod);
407 gmove(&nod, n);
408 }
409 else
410 gopcode(o, n->type, &nod, n);
411 }
412
413 if(p->alg > 0)
414 regfree(&nod);
415
416 return 1;
417
418 bad:
419 diag(Z, "mulgen botch");
420 return 1;
421 }
422
423 void
mulgen(Type * t,Node * r,Node * n)424 mulgen(Type *t, Node *r, Node *n)
425 {
426 if(!mulgen1(r->vconst, n))
427 gopcode(OMUL, t, r, n);
428 }
429