1 #include "gc.h"
2
3 /*
4 * code sequences for multiply by constant.
5 * [a-l][0-3]
6 * lsl $(A-'a'),r0,r1
7 * [+][0-7]
8 * add r0,r1,r2
9 * [-][0-7]
10 * sub r0,r1,r2
11 */
12
13 static int multabp;
14 static long mulval;
15 static char* mulcp;
16 static long valmax;
17 static int shmax;
18
19 static int docode(char *hp, char *cp, int r0, int r1);
20 static int gen1(int len);
21 static int gen2(int len, long r1);
22 static int gen3(int len, long r0, long r1, int flag);
23 enum
24 {
25 SR1 = 1<<0, /* r1 has been shifted */
26 SR0 = 1<<1, /* r0 has been shifted */
27 UR1 = 1<<2, /* r1 has not been used */
28 UR0 = 1<<3 /* r0 has not been used */
29 };
30
31 Multab*
mulcon0(Node * n,long v)32 mulcon0(Node *n, long v)
33 {
34 int a1, a2, g;
35 Multab *m, *m1;
36 char hint[10];
37
38 if(v < 0)
39 v = -v;
40
41 /*
42 * look in cache
43 */
44 m = multab;
45 for(g=0; g<nelem(multab); g++) {
46 if(m->val == v) {
47 if(m->code[0] == 0)
48 return 0;
49 return m;
50 }
51 m++;
52 }
53
54 /*
55 * select a spot in cache to overwrite
56 */
57 multabp++;
58 if(multabp < 0 || multabp >= nelem(multab))
59 multabp = 0;
60 m = multab+multabp;
61 m->val = v;
62 mulval = v;
63
64 /*
65 * look in execption hint table
66 */
67 a1 = 0;
68 a2 = hintabsize;
69 for(;;) {
70 if(a1 >= a2)
71 goto no;
72 g = (a2 + a1)/2;
73 if(v < hintab[g].val) {
74 a2 = g;
75 continue;
76 }
77 if(v > hintab[g].val) {
78 a1 = g+1;
79 continue;
80 }
81 break;
82 }
83
84 if(docode(hintab[g].hint, m->code, 1, 0))
85 return m;
86 print("%L: multiply table failure %ld\n", n->lineno, v);
87 m->code[0] = 0;
88 return 0;
89
90 no:
91 /*
92 * try to search
93 */
94 hint[0] = 0;
95 for(g=1; g<=6; g++) {
96 if(g >= 6 && v >= 65535)
97 break;
98 mulcp = hint+g;
99 *mulcp = 0;
100 if(gen1(g)) {
101 if(docode(hint, m->code, 1, 0))
102 return m;
103 print("%L: multiply table failure (g=%d h=%s) %ld\n",
104 n->lineno, g, hint, v);
105 break;
106 }
107 }
108
109 /*
110 * try a recur followed by a shift
111 */
112 g = 0;
113 while(!(v & 1)) {
114 g++;
115 v >>= 1;
116 }
117 if(g) {
118 m1 = mulcon0(n, v);
119 if(m1) {
120 strcpy(m->code, m1->code);
121 sprint(strchr(m->code, 0), "%c0", g+'a');
122 return m;
123 }
124 }
125 m->code[0] = 0;
126 return 0;
127 }
128
129 static int
docode(char * hp,char * cp,int r0,int r1)130 docode(char *hp, char *cp, int r0, int r1)
131 {
132 int c, i;
133
134 c = *hp++;
135 *cp = c;
136 cp += 2;
137 switch(c) {
138 default:
139 c -= 'a';
140 if(c < 1 || c >= 30)
141 break;
142 for(i=0; i<4; i++) {
143 switch(i) {
144 case 0:
145 if(docode(hp, cp, r0<<c, r1))
146 goto out;
147 break;
148 case 1:
149 if(docode(hp, cp, r1<<c, r1))
150 goto out;
151 break;
152 case 2:
153 if(docode(hp, cp, r0, r0<<c))
154 goto out;
155 break;
156 case 3:
157 if(docode(hp, cp, r0, r1<<c))
158 goto out;
159 break;
160 }
161 }
162 break;
163
164 case '+':
165 for(i=0; i<8; i++) {
166 cp[-1] = i+'0';
167 switch(i) {
168 case 1:
169 if(docode(hp, cp, r0+r1, r1))
170 goto out;
171 break;
172 case 5:
173 if(docode(hp, cp, r0, r0+r1))
174 goto out;
175 break;
176 }
177 }
178 break;
179
180 case '-':
181 for(i=0; i<8; i++) {
182 cp[-1] = i+'0';
183 switch(i) {
184 case 1:
185 if(docode(hp, cp, r0-r1, r1))
186 goto out;
187 break;
188 case 2:
189 if(docode(hp, cp, r1-r0, r1))
190 goto out;
191 break;
192 case 5:
193 if(docode(hp, cp, r0, r0-r1))
194 goto out;
195 break;
196 case 6:
197 if(docode(hp, cp, r0, r1-r0))
198 goto out;
199 break;
200 }
201 }
202 break;
203
204 case 0:
205 if(r0 == mulval)
206 return 1;
207 }
208 return 0;
209
210 out:
211 cp[-1] = i+'0';
212 return 1;
213 }
214
215 static int
gen1(int len)216 gen1(int len)
217 {
218 int i;
219
220 for(shmax=1; shmax<30; shmax++) {
221 valmax = 1<<shmax;
222 if(valmax >= mulval)
223 break;
224 }
225 if(mulval == 1)
226 return 1;
227
228 len--;
229 for(i=1; i<=shmax; i++)
230 if(gen2(len, 1<<i)) {
231 *--mulcp = 'a'+i;
232 return 1;
233 }
234 return 0;
235 }
236
237 static int
gen2(int len,long r1)238 gen2(int len, long r1)
239 {
240 int i;
241
242 if(len <= 0) {
243 if(r1 == mulval)
244 return 1;
245 return 0;
246 }
247
248 len--;
249 if(len == 0)
250 goto calcr0;
251
252 if(gen3(len, r1, r1+1, UR1)) {
253 i = '+';
254 goto out;
255 }
256 if(gen3(len, r1-1, r1, UR0)) {
257 i = '-';
258 goto out;
259 }
260 if(gen3(len, 1, r1+1, UR1)) {
261 i = '+';
262 goto out;
263 }
264 if(gen3(len, 1, r1-1, UR1)) {
265 i = '-';
266 goto out;
267 }
268
269 return 0;
270
271 calcr0:
272 if(mulval == r1+1) {
273 i = '+';
274 goto out;
275 }
276 if(mulval == r1-1) {
277 i = '-';
278 goto out;
279 }
280 return 0;
281
282 out:
283 *--mulcp = i;
284 return 1;
285 }
286
287 static int
gen3(int len,long r0,long r1,int flag)288 gen3(int len, long r0, long r1, int flag)
289 {
290 int i, f1, f2;
291 long x;
292
293 if(r0 <= 0 ||
294 r0 >= r1 ||
295 r1 > valmax)
296 return 0;
297
298 len--;
299 if(len == 0)
300 goto calcr0;
301
302 if(!(flag & UR1)) {
303 f1 = UR1|SR1;
304 for(i=1; i<=shmax; i++) {
305 x = r0<<i;
306 if(x > valmax)
307 break;
308 if(gen3(len, r0, x, f1)) {
309 i += 'a';
310 goto out;
311 }
312 }
313 }
314
315 if(!(flag & UR0)) {
316 f1 = UR1|SR1;
317 for(i=1; i<=shmax; i++) {
318 x = r1<<i;
319 if(x > valmax)
320 break;
321 if(gen3(len, r1, x, f1)) {
322 i += 'a';
323 goto out;
324 }
325 }
326 }
327
328 if(!(flag & SR1)) {
329 f1 = UR1|SR1|(flag&UR0);
330 for(i=1; i<=shmax; i++) {
331 x = r1<<i;
332 if(x > valmax)
333 break;
334 if(gen3(len, r0, x, f1)) {
335 i += 'a';
336 goto out;
337 }
338 }
339 }
340
341 if(!(flag & SR0)) {
342 f1 = UR0|SR0|(flag&(SR1|UR1));
343
344 f2 = UR1|SR1;
345 if(flag & UR1)
346 f2 |= UR0;
347 if(flag & SR1)
348 f2 |= SR0;
349
350 for(i=1; i<=shmax; i++) {
351 x = r0<<i;
352 if(x > valmax)
353 break;
354 if(x > r1) {
355 if(gen3(len, r1, x, f2)) {
356 i += 'a';
357 goto out;
358 }
359 } else
360 if(gen3(len, x, r1, f1)) {
361 i += 'a';
362 goto out;
363 }
364 }
365 }
366
367 x = r1+r0;
368 if(gen3(len, r0, x, UR1)) {
369 i = '+';
370 goto out;
371 }
372
373 if(gen3(len, r1, x, UR1)) {
374 i = '+';
375 goto out;
376 }
377
378 x = r1-r0;
379 if(gen3(len, x, r1, UR0)) {
380 i = '-';
381 goto out;
382 }
383
384 if(x > r0) {
385 if(gen3(len, r0, x, UR1)) {
386 i = '-';
387 goto out;
388 }
389 } else
390 if(gen3(len, x, r0, UR0)) {
391 i = '-';
392 goto out;
393 }
394
395 return 0;
396
397 calcr0:
398 f1 = flag & (UR0|UR1);
399 if(f1 == UR1) {
400 for(i=1; i<=shmax; i++) {
401 x = r1<<i;
402 if(x >= mulval) {
403 if(x == mulval) {
404 i += 'a';
405 goto out;
406 }
407 break;
408 }
409 }
410 }
411
412 if(mulval == r1+r0) {
413 i = '+';
414 goto out;
415 }
416 if(mulval == r1-r0) {
417 i = '-';
418 goto out;
419 }
420
421 return 0;
422
423 out:
424 *--mulcp = i;
425 return 1;
426 }
427
428 /*
429 * hint table has numbers that
430 * the search algorithm fails on.
431 * <1000:
432 * all numbers
433 * <5000:
434 * ÷ by 5
435 * <10000:
436 * ÷ by 50
437 * <65536:
438 * ÷ by 250
439 */
440 Hintab hintab[] =
441 {
442 683, "b++d+e+",
443 687, "b+e++e-",
444 691, "b++d+e+",
445 731, "b++d+e+",
446 811, "b++d+i+",
447 821, "b++e+e+",
448 843, "b+d++e+",
449 851, "b+f-+e-",
450 853, "b++e+e+",
451 877, "c++++g-",
452 933, "b+c++g-",
453 981, "c-+e-d+",
454 1375, "b+c+b+h-",
455 1675, "d+b++h+",
456 2425, "c++f-e+",
457 2675, "c+d++f-",
458 2750, "b+d-b+h-",
459 2775, "c-+g-e-",
460 3125, "b++e+g+",
461 3275, "b+c+g+e+",
462 3350, "c++++i+",
463 3475, "c-+e-f-",
464 3525, "c-+d+g-",
465 3625, "c-+e-j+",
466 3675, "b+d+d+e+",
467 3725, "b+d-+h+",
468 3925, "b+d+f-d-",
469 4275, "b+g++e+",
470 4325, "b+h-+d+",
471 4425, "b+b+g-j-",
472 4525, "b+d-d+f+",
473 4675, "c++d-g+",
474 4775, "b+d+b+g-",
475 4825, "c+c-+i-",
476 4850, "c++++i-",
477 4925, "b++e-g-",
478 4975, "c+f++e-",
479 5500, "b+g-c+d+",
480 6700, "d+b++i+",
481 9700, "d++++j-",
482 11000, "b+f-c-h-",
483 11750, "b+d+g+j-",
484 12500, "b+c+e-k+",
485 13250, "b+d+e-f+",
486 13750, "b+h-c-d+",
487 14250, "b+g-c+e-",
488 14500, "c+f+j-d-",
489 14750, "d-g--f+",
490 16750, "b+e-d-n+",
491 17750, "c+h-b+e+",
492 18250, "d+b+h-d+",
493 18750, "b+g-++f+",
494 19250, "b+e+b+h+",
495 19750, "b++h--f-",
496 20250, "b+e-l-c+",
497 20750, "c++bi+e-",
498 21250, "b+i+l+c+",
499 22000, "b+e+d-g-",
500 22250, "b+d-h+k-",
501 22750, "b+d-e-g+",
502 23250, "b+c+h+e-",
503 23500, "b+g-c-g-",
504 23750, "b+g-b+h-",
505 24250, "c++g+m-",
506 24750, "b+e+e+j-",
507 25000, "b++dh+g+",
508 25250, "b+e+d-g-",
509 25750, "b+e+b+j+",
510 26250, "b+h+c+e+",
511 26500, "b+h+c+g+",
512 26750, "b+d+e+g-",
513 27250, "b+e+e+f+",
514 27500, "c-i-c-d+",
515 27750, "b+bd++j+",
516 28250, "d-d-++i-",
517 28500, "c+c-h-e-",
518 29000, "b+g-d-f+",
519 29500, "c+h+++e-",
520 29750, "b+g+f-c+",
521 30250, "b+f-g-c+",
522 33500, "c-f-d-n+",
523 33750, "b+d-b+j-",
524 34250, "c+e+++i+",
525 35250, "e+b+d+k+",
526 35500, "c+e+d-g-",
527 35750, "c+i-++e+",
528 36250, "b+bh-d+e+",
529 36500, "c+c-h-e-",
530 36750, "d+e--i+",
531 37250, "b+g+g+b+",
532 37500, "b+h-b+f+",
533 37750, "c+be++j-",
534 38500, "b+e+b+i+",
535 38750, "d+i-b+d+",
536 39250, "b+g-l-+d+",
537 39500, "b+g-c+g-",
538 39750, "b+bh-c+f-",
539 40250, "b+bf+d+g-",
540 40500, "b+g-c+g+",
541 40750, "c+b+i-e+",
542 41250, "d++bf+h+",
543 41500, "b+j+c+d-",
544 41750, "c+f+b+h-",
545 42500, "c+h++g+",
546 42750, "b+g+d-f-",
547 43250, "b+l-e+d-",
548 43750, "c+bd+h+f-",
549 44000, "b+f+g-d-",
550 44250, "b+d-g--f+",
551 44500, "c+e+c+h+",
552 44750, "b+e+d-h-",
553 45250, "b++g+j-g+",
554 45500, "c+d+e-g+",
555 45750, "b+d-h-e-",
556 46250, "c+bd++j+",
557 46500, "b+d-c-j-",
558 46750, "e-e-b+g-",
559 47000, "b+c+d-j-",
560 47250, "b+e+e-g-",
561 47500, "b+g-c-h-",
562 47750, "b+f-c+h-",
563 48250, "d--h+n-",
564 48500, "b+c-g+m-",
565 48750, "b+e+e-g+",
566 49500, "c-f+e+j-",
567 49750, "c+c+g++f-",
568 50000, "b+e+e+k+",
569 50250, "b++i++g+",
570 50500, "c+g+f-i+",
571 50750, "b+e+d+k-",
572 51500, "b+i+c-f+",
573 51750, "b+bd+g-e-",
574 52250, "b+d+g-j+",
575 52500, "c+c+f+g+",
576 52750, "b+c+e+i+",
577 53000, "b+i+c+g+",
578 53500, "c+g+g-n+",
579 53750, "b+j+d-c+",
580 54250, "b+d-g-j-",
581 54500, "c-f+e+f+",
582 54750, "b+f-+c+g+",
583 55000, "b+g-d-g-",
584 55250, "b+e+e+g+",
585 55500, "b+cd++j+",
586 55750, "b+bh-d-f-",
587 56250, "c+d-b+j-",
588 56500, "c+d+c+i+",
589 56750, "b+e+d++h-",
590 57000, "b+d+g-f+",
591 57250, "b+f-m+d-",
592 57750, "b+i+c+e-",
593 58000, "b+e+d+h+",
594 58250, "c+b+g+g+",
595 58750, "d-e-j--e+",
596 59000, "d-i-+e+",
597 59250, "e--h-m+",
598 59500, "c+c-h+f-",
599 59750, "b+bh-e+i-",
600 60250, "b+bh-e-e-",
601 60500, "c+c-g-g-",
602 60750, "b+e-l-e-",
603 61250, "b+g-g-c+",
604 61750, "b+g-c+g+",
605 62250, "f--+c-i-",
606 62750, "e+f--+g+",
607 64750, "b+f+d+p-",
608 };
609 int hintabsize = nelem(hintab);
610