Subversion Repositories planix.SVN

Rev

Rev 2 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 - 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*
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
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
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
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
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);