xref: /inferno-os/utils/qc/reg.c (revision e57c7e16a3789cd4de1a3c2560d49b1ee39cd10a) 
1 #include "gc.h"
2 
3 Reg*
4 rega(void)
5 {
6 	Reg *r;
7 
8 	r = freer;
9 	if(r == R) {
10 		r = alloc(sizeof(*r));
11 	} else
12 		freer = r->link;
13 
14 	*r = zreg;
15 	return r;
16 }
17 
18 int
19 rcmp(void *a1, void *a2)
20 {
21 	Rgn *p1, *p2;
22 	int c1, c2;
23 
24 	p1 = a1;
25 	p2 = a2;
26 	c1 = p2->cost;
27 	c2 = p1->cost;
28 	if(c1 -= c2)
29 		return c1;
30 	return p2->varno - p1->varno;
31 }
32 
33 void
34 regopt(Prog *p)
35 {
36 	Reg *r, *r1, *r2;
37 	Prog *p1;
38 	int i, z;
39 	long initpc, val, npc;
40 	ulong vreg;
41 	Bits bit;
42 	struct
43 	{
44 		long	m;
45 		long	c;
46 		Reg*	p;
47 	} log5[6], *lp;
48 
49 	firstr = R;
50 	lastr = R;
51 	nvar = 0;
52 	regbits = 0;
53 	for(z=0; z<BITS; z++) {
54 		externs.b[z] = 0;
55 		params.b[z] = 0;
56 		consts.b[z] = 0;
57 		addrs.b[z] = 0;
58 	}
59 
60 	/*
61 	 * pass 1
62 	 * build aux data structure
63 	 * allocate pcs
64 	 * find use and set of variables
65 	 */
66 	val = 5L * 5L * 5L * 5L * 5L;
67 	lp = log5;
68 	for(i=0; i<5; i++) {
69 		lp->m = val;
70 		lp->c = 0;
71 		lp->p = R;
72 		val /= 5L;
73 		lp++;
74 	}
75 	val = 0;
76 	for(; p != P; p = p->link) {
77 		switch(p->as) {
78 		case ADATA:
79 		case AGLOBL:
80 		case ANAME:
81 		case ASIGNAME:
82 			continue;
83 		}
84 		r = rega();
85 		if(firstr == R) {
86 			firstr = r;
87 			lastr = r;
88 		} else {
89 			lastr->link = r;
90 			r->p1 = lastr;
91 			lastr->s1 = r;
92 			lastr = r;
93 		}
94 		r->prog = p;
95 		r->pc = val;
96 		val++;
97 
98 		lp = log5;
99 		for(i=0; i<5; i++) {
100 			lp->c--;
101 			if(lp->c <= 0) {
102 				lp->c = lp->m;
103 				if(lp->p != R)
104 					lp->p->log5 = r;
105 				lp->p = r;
106 				(lp+1)->c = 0;
107 				break;
108 			}
109 			lp++;
110 		}
111 
112 		r1 = r->p1;
113 		if(r1 != R)
114 		switch(r1->prog->as) {
115 		case ARETURN:
116 		case ABR:
117 		case ARFI:
118 			r->p1 = R;
119 			r1->s1 = R;
120 		}
121 
122 		/*
123 		 * left side always read
124 		 */
125 		bit = mkvar(&p->from, p->as==AMOVW);
126 		for(z=0; z<BITS; z++)
127 			r->use1.b[z] |= bit.b[z];
128 
129 		/*
130 		 * right side depends on opcode
131 		 */
132 		bit = mkvar(&p->to, 0);
133 		if(bany(&bit))
134 		switch(p->as) {
135 		default:
136 			diag(Z, "reg: unknown asop: %A", p->as);
137 			break;
138 
139 		/*
140 		 * right side write
141 		 */
142 		case ANOP:
143 		case AMOVB:
144 		case AMOVBU:
145 		case AMOVBZ:
146 		case AMOVBZU:
147 		case AMOVH:
148 		case AMOVHBR:
149 		case AMOVHU:
150 		case AMOVHZ:
151 		case AMOVHZU:
152 		case AMOVW:
153 		case AMOVWU:
154 		case AFMOVD:
155 		case AFMOVDCC:
156 		case AFMOVDU:
157 		case AFMOVS:
158 		case AFMOVSU:
159 		case AFRSP:
160 			for(z=0; z<BITS; z++)
161 				r->set.b[z] |= bit.b[z];
162 			break;
163 
164 		/*
165 		 * funny
166 		 */
167 		case ABL:
168 			for(z=0; z<BITS; z++)
169 				addrs.b[z] |= bit.b[z];
170 			break;
171 		}
172 	}
173 	if(firstr == R)
174 		return;
175 	initpc = pc - val;
176 	npc = val;
177 
178 	/*
179 	 * pass 2
180 	 * turn branch references to pointers
181 	 * build back pointers
182 	 */
183 	for(r = firstr; r != R; r = r->link) {
184 		p = r->prog;
185 		if(p->to.type == D_BRANCH) {
186 			val = p->to.offset - initpc;
187 			r1 = firstr;
188 			while(r1 != R) {
189 				r2 = r1->log5;
190 				if(r2 != R && val >= r2->pc) {
191 					r1 = r2;
192 					continue;
193 				}
194 				if(r1->pc == val)
195 					break;
196 				r1 = r1->link;
197 			}
198 			if(r1 == R) {
199 				nearln = p->lineno;
200 				diag(Z, "ref not found\n%P", p);
201 				continue;
202 			}
203 			if(r1 == r) {
204 				nearln = p->lineno;
205 				diag(Z, "ref to self\n%P", p);
206 				continue;
207 			}
208 			r->s2 = r1;
209 			r->p2link = r1->p2;
210 			r1->p2 = r;
211 		}
212 	}
213 	if(debug['R']) {
214 		p = firstr->prog;
215 		print("\n%L %D\n", p->lineno, &p->from);
216 	}
217 
218 	/*
219 	 * pass 2.5
220 	 * find looping structure
221 	 */
222 	for(r = firstr; r != R; r = r->link)
223 		r->active = 0;
224 	change = 0;
225 	loopit(firstr, npc);
226 	if(debug['R'] && debug['v']) {
227 		print("\nlooping structure:\n");
228 		for(r = firstr; r != R; r = r->link) {
229 			print("%ld:%P", r->loop, r->prog);
230 			for(z=0; z<BITS; z++)
231 				bit.b[z] = r->use1.b[z] |
232 					r->use2.b[z] | r->set.b[z];
233 			if(bany(&bit)) {
234 				print("\t");
235 				if(bany(&r->use1))
236 					print(" u1=%B", r->use1);
237 				if(bany(&r->use2))
238 					print(" u2=%B", r->use2);
239 				if(bany(&r->set))
240 					print(" st=%B", r->set);
241 			}
242 			print("\n");
243 		}
244 	}
245 
246 	/*
247 	 * pass 3
248 	 * iterate propagating usage
249 	 * 	back until flow graph is complete
250 	 */
251 loop1:
252 	change = 0;
253 	for(r = firstr; r != R; r = r->link)
254 		r->active = 0;
255 	for(r = firstr; r != R; r = r->link)
256 		if(r->prog->as == ARETURN)
257 			prop(r, zbits, zbits);
258 loop11:
259 	/* pick up unreachable code */
260 	i = 0;
261 	for(r = firstr; r != R; r = r1) {
262 		r1 = r->link;
263 		if(r1 && r1->active && !r->active) {
264 			prop(r, zbits, zbits);
265 			i = 1;
266 		}
267 	}
268 	if(i)
269 		goto loop11;
270 	if(change)
271 		goto loop1;
272 
273 
274 	/*
275 	 * pass 4
276 	 * iterate propagating register/variable synchrony
277 	 * 	forward until graph is complete
278 	 */
279 loop2:
280 	change = 0;
281 	for(r = firstr; r != R; r = r->link)
282 		r->active = 0;
283 	synch(firstr, zbits);
284 	if(change)
285 		goto loop2;
286 
287 
288 	/*
289 	 * pass 5
290 	 * isolate regions
291 	 * calculate costs (paint1)
292 	 */
293 	r = firstr;
294 	if(r) {
295 		for(z=0; z<BITS; z++)
296 			bit.b[z] = (r->refahead.b[z] | r->calahead.b[z]) &
297 			  ~(externs.b[z] | params.b[z] | addrs.b[z] | consts.b[z]);
298 		if(bany(&bit)) {
299 			nearln = r->prog->lineno;
300 			warn(Z, "used and not set: %B", bit);
301 			if(debug['R'] && !debug['w'])
302 				print("used and not set: %B\n", bit);
303 		}
304 	}
305 	if(debug['R'] && debug['v'])
306 		print("\nprop structure:\n");
307 	for(r = firstr; r != R; r = r->link)
308 		r->act = zbits;
309 	rgp = region;
310 	nregion = 0;
311 	for(r = firstr; r != R; r = r->link) {
312 		if(debug['R'] && debug['v'])
313 			print("%P\n	set = %B; rah = %B; cal = %B\n",
314 				r->prog, r->set, r->refahead, r->calahead);
315 		for(z=0; z<BITS; z++)
316 			bit.b[z] = r->set.b[z] &
317 			  ~(r->refahead.b[z] | r->calahead.b[z] | addrs.b[z]);
318 		if(bany(&bit)) {
319 			nearln = r->prog->lineno;
320 			warn(Z, "set and not used: %B", bit);
321 			if(debug['R'])
322 				print("set an not used: %B\n", bit);
323 			excise(r);
324 		}
325 		for(z=0; z<BITS; z++)
326 			bit.b[z] = LOAD(r) & ~(r->act.b[z] | addrs.b[z]);
327 		while(bany(&bit)) {
328 			i = bnum(bit);
329 			rgp->enter = r;
330 			rgp->varno = i;
331 			change = 0;
332 			if(debug['R'] && debug['v'])
333 				print("\n");
334 			paint1(r, i);
335 			bit.b[i/32] &= ~(1L<<(i%32));
336 			if(change <= 0) {
337 				if(debug['R'])
338 					print("%L$%d: %B\n",
339 						r->prog->lineno, change, blsh(i));
340 				continue;
341 			}
342 			rgp->cost = change;
343 			nregion++;
344 			if(nregion >= NRGN) {
345 				warn(Z, "too many regions");
346 				goto brk;
347 			}
348 			rgp++;
349 		}
350 	}
351 brk:
352 	qsort(region, nregion, sizeof(region[0]), rcmp);
353 
354 	/*
355 	 * pass 6
356 	 * determine used registers (paint2)
357 	 * replace code (paint3)
358 	 */
359 	rgp = region;
360 	for(i=0; i<nregion; i++) {
361 		bit = blsh(rgp->varno);
362 		vreg = paint2(rgp->enter, rgp->varno);
363 		vreg = allreg(vreg, rgp);
364 		if(debug['R']) {
365 			if(rgp->regno >= NREG)
366 				print("%L$%d F%d: %B\n",
367 					rgp->enter->prog->lineno,
368 					rgp->cost,
369 					rgp->regno-NREG,
370 					bit);
371 			else
372 				print("%L$%d R%d: %B\n",
373 					rgp->enter->prog->lineno,
374 					rgp->cost,
375 					rgp->regno,
376 					bit);
377 		}
378 		if(rgp->regno != 0)
379 			paint3(rgp->enter, rgp->varno, vreg, rgp->regno);
380 		rgp++;
381 	}
382 	/*
383 	 * pass 7
384 	 * peep-hole on basic block
385 	 */
386 	if(!debug['R'] || debug['P'])
387 		peep();
388 
389 	/*
390 	 * pass 8
391 	 * recalculate pc
392 	 */
393 	val = initpc;
394 	for(r = firstr; r != R; r = r1) {
395 		r->pc = val;
396 		p = r->prog;
397 		p1 = P;
398 		r1 = r->link;
399 		if(r1 != R)
400 			p1 = r1->prog;
401 		for(; p != p1; p = p->link) {
402 			switch(p->as) {
403 			default:
404 				val++;
405 				break;
406 
407 			case ANOP:
408 			case ADATA:
409 			case AGLOBL:
410 			case ANAME:
411 			case ASIGNAME:
412 				break;
413 			}
414 		}
415 	}
416 	pc = val;
417 
418 	/*
419 	 * fix up branches
420 	 */
421 	if(debug['R'])
422 		if(bany(&addrs))
423 			print("addrs: %B\n", addrs);
424 
425 	r1 = 0; /* set */
426 	for(r = firstr; r != R; r = r->link) {
427 		p = r->prog;
428 		if(p->to.type == D_BRANCH)
429 			p->to.offset = r->s2->pc;
430 		r1 = r;
431 	}
432 
433 	/*
434 	 * last pass
435 	 * eliminate nops
436 	 * free aux structures
437 	 */
438 	for(p = firstr->prog; p != P; p = p->link){
439 		while(p->link && p->link->as == ANOP)
440 			p->link = p->link->link;
441 	}
442 	if(r1 != R) {
443 		r1->link = freer;
444 		freer = firstr;
445 	}
446 }
447 
448 /*
449  * add mov b,rn
450  * just after r
451  */
452 void
453 addmove(Reg *r, int bn, int rn, int f)
454 {
455 	Prog *p, *p1;
456 	Adr *a;
457 	Var *v;
458 
459 	p1 = alloc(sizeof(*p1));
460 	*p1 = zprog;
461 	p = r->prog;
462 
463 	p1->link = p->link;
464 	p->link = p1;
465 	p1->lineno = p->lineno;
466 
467 	v = var + bn;
468 
469 	a = &p1->to;
470 	a->sym = v->sym;
471 	a->name = v->name;
472 	a->offset = v->offset;
473 	a->etype = v->etype;
474 	a->type = D_OREG;
475 	if(a->etype == TARRAY || a->sym == S)
476 		a->type = D_CONST;
477 
478 	p1->as = AMOVW;
479 	if(v->etype == TCHAR || v->etype == TUCHAR)
480 		p1->as = AMOVB;
481 	if(v->etype == TSHORT || v->etype == TUSHORT)
482 		p1->as = AMOVH;
483 	if(v->etype == TFLOAT)
484 		p1->as = AFMOVS;
485 	if(v->etype == TDOUBLE)
486 		p1->as = AFMOVD;
487 
488 	p1->from.type = D_REG;
489 	p1->from.reg = rn;
490 	if(rn >= NREG) {
491 		p1->from.type = D_FREG;
492 		p1->from.reg = rn-NREG;
493 	}
494 	if(!f) {
495 		p1->from = *a;
496 		*a = zprog.from;
497 		a->type = D_REG;
498 		a->reg = rn;
499 		if(rn >= NREG) {
500 			a->type = D_FREG;
501 			a->reg = rn-NREG;
502 		}
503 		if(v->etype == TUCHAR)
504 			p1->as = AMOVBZ;
505 		if(v->etype == TUSHORT)
506 			p1->as = AMOVHZ;
507 	}
508 	if(debug['R'])
509 		print("%P\t.a%P\n", p, p1);
510 }
511 
512 Bits
513 mkvar(Adr *a, int docon)
514 {
515 	Var *v;
516 	int i, t, n, et, z;
517 	long o;
518 	Bits bit;
519 	Sym *s;
520 
521 	t = a->type;
522 	if(t == D_REG && a->reg != NREG)
523 		regbits |= RtoB(a->reg);
524 	if(t == D_FREG && a->reg != NREG)
525 		regbits |= FtoB(a->reg);
526 	s = a->sym;
527 	o = a->offset;
528 	et = a->etype;
529 	if(s == S) {
530 		if(t != D_CONST || !docon || a->reg != NREG)
531 			goto none;
532 		et = TLONG;
533 	}
534 	if(t == D_CONST) {
535 		if(s == S && sval(o))
536 			goto none;
537 	}
538 	n = a->name;
539 	v = var;
540 	for(i=0; i<nvar; i++) {
541 		if(s == v->sym)
542 		if(n == v->name)
543 		if(o == v->offset)
544 			goto out;
545 		v++;
546 	}
547 	if(s)
548 		if(s->name[0] == '.')
549 			goto none;
550 	if(nvar >= NVAR) {
551 		if(debug['w'] > 1 && s)
552 			warn(Z, "variable not optimized: %s", s->name);
553 		goto none;
554 	}
555 	i = nvar;
556 	nvar++;
557 	v = &var[i];
558 	v->sym = s;
559 	v->offset = o;
560 	v->etype = et;
561 	v->name = n;
562 	if(debug['R'])
563 		print("bit=%2d et=%2d %D\n", i, et, a);
564 out:
565 	bit = blsh(i);
566 	if(n == D_EXTERN || n == D_STATIC)
567 		for(z=0; z<BITS; z++)
568 			externs.b[z] |= bit.b[z];
569 	if(n == D_PARAM)
570 		for(z=0; z<BITS; z++)
571 			params.b[z] |= bit.b[z];
572 	if(v->etype != et || !typechlpfd[et])	/* funny punning */
573 		for(z=0; z<BITS; z++)
574 			addrs.b[z] |= bit.b[z];
575 	if(t == D_CONST) {
576 		if(s == S) {
577 			for(z=0; z<BITS; z++)
578 				consts.b[z] |= bit.b[z];
579 			return bit;
580 		}
581 		if(et != TARRAY)
582 			for(z=0; z<BITS; z++)
583 				addrs.b[z] |= bit.b[z];
584 		for(z=0; z<BITS; z++)
585 			params.b[z] |= bit.b[z];
586 		return bit;
587 	}
588 	if(t == D_OREG)
589 		return bit;
590 
591 none:
592 	return zbits;
593 }
594 
595 void
596 prop(Reg *r, Bits ref, Bits cal)
597 {
598 	Reg *r1, *r2;
599 	int z;
600 
601 	for(r1 = r; r1 != R; r1 = r1->p1) {
602 		for(z=0; z<BITS; z++) {
603 			ref.b[z] |= r1->refahead.b[z];
604 			if(ref.b[z] != r1->refahead.b[z]) {
605 				r1->refahead.b[z] = ref.b[z];
606 				change++;
607 			}
608 			cal.b[z] |= r1->calahead.b[z];
609 			if(cal.b[z] != r1->calahead.b[z]) {
610 				r1->calahead.b[z] = cal.b[z];
611 				change++;
612 			}
613 		}
614 		switch(r1->prog->as) {
615 		case ABL:
616 			for(z=0; z<BITS; z++) {
617 				cal.b[z] |= ref.b[z] | externs.b[z];
618 				ref.b[z] = 0;
619 			}
620 			break;
621 
622 		case ATEXT:
623 			for(z=0; z<BITS; z++) {
624 				cal.b[z] = 0;
625 				ref.b[z] = 0;
626 			}
627 			break;
628 
629 		case ARETURN:
630 			for(z=0; z<BITS; z++) {
631 				cal.b[z] = externs.b[z];
632 				ref.b[z] = 0;
633 			}
634 		}
635 		for(z=0; z<BITS; z++) {
636 			ref.b[z] = (ref.b[z] & ~r1->set.b[z]) |
637 				r1->use1.b[z] | r1->use2.b[z];
638 			cal.b[z] &= ~(r1->set.b[z] | r1->use1.b[z] | r1->use2.b[z]);
639 			r1->refbehind.b[z] = ref.b[z];
640 			r1->calbehind.b[z] = cal.b[z];
641 		}
642 		if(r1->active)
643 			break;
644 		r1->active = 1;
645 	}
646 	for(; r != r1; r = r->p1)
647 		for(r2 = r->p2; r2 != R; r2 = r2->p2link)
648 			prop(r2, r->refbehind, r->calbehind);
649 }
650 
651 /*
652  * find looping structure
653  *
654  * 1) find reverse postordering
655  * 2) find approximate dominators,
656  *	the actual dominators if the flow graph is reducible
657  *	otherwise, dominators plus some other non-dominators.
658  *	See Matthew S. Hecht and Jeffrey D. Ullman,
659  *	"Analysis of a Simple Algorithm for Global Data Flow Problems",
660  *	Conf.  Record of ACM Symp. on Principles of Prog. Langs, Boston, Massachusetts,
661  *	Oct. 1-3, 1973, pp.  207-217.
662  * 3) find all nodes with a predecessor dominated by the current node.
663  *	such a node is a loop head.
664  *	recursively, all preds with a greater rpo number are in the loop
665  */
666 long
667 postorder(Reg *r, Reg **rpo2r, long n)
668 {
669 	Reg *r1;
670 
671 	r->rpo = 1;
672 	r1 = r->s1;
673 	if(r1 && !r1->rpo)
674 		n = postorder(r1, rpo2r, n);
675 	r1 = r->s2;
676 	if(r1 && !r1->rpo)
677 		n = postorder(r1, rpo2r, n);
678 	rpo2r[n] = r;
679 	n++;
680 	return n;
681 }
682 
683 long
684 rpolca(long *idom, long rpo1, long rpo2)
685 {
686 	long t;
687 
688 	if(rpo1 == -1)
689 		return rpo2;
690 	while(rpo1 != rpo2){
691 		if(rpo1 > rpo2){
692 			t = rpo2;
693 			rpo2 = rpo1;
694 			rpo1 = t;
695 		}
696 		while(rpo1 < rpo2){
697 			t = idom[rpo2];
698 			if(t >= rpo2)
699 				fatal(Z, "bad idom");
700 			rpo2 = t;
701 		}
702 	}
703 	return rpo1;
704 }
705 
706 int
707 doms(long *idom, long r, long s)
708 {
709 	while(s > r)
710 		s = idom[s];
711 	return s == r;
712 }
713 
714 int
715 loophead(long *idom, Reg *r)
716 {
717 	long src;
718 
719 	src = r->rpo;
720 	if(r->p1 != R && doms(idom, src, r->p1->rpo))
721 		return 1;
722 	for(r = r->p2; r != R; r = r->p2link)
723 		if(doms(idom, src, r->rpo))
724 			return 1;
725 	return 0;
726 }
727 
728 void
729 loopmark(Reg **rpo2r, long head, Reg *r)
730 {
731 	if(r->rpo < head || r->active == head)
732 		return;
733 	r->active = head;
734 	r->loop += LOOP;
735 	if(r->p1 != R)
736 		loopmark(rpo2r, head, r->p1);
737 	for(r = r->p2; r != R; r = r->p2link)
738 		loopmark(rpo2r, head, r);
739 }
740 
741 void
742 loopit(Reg *r, long nr)
743 {
744 	Reg *r1;
745 	long i, d, me;
746 
747 	if(nr > maxnr) {
748 		rpo2r = alloc(nr * sizeof(Reg*));
749 		idom = alloc(nr * sizeof(long));
750 		maxnr = nr;
751 	}
752 
753 	d = postorder(r, rpo2r, 0);
754 	if(d > nr)
755 		fatal(Z, "too many reg nodes");
756 	nr = d;
757 	for(i = 0; i < nr / 2; i++){
758 		r1 = rpo2r[i];
759 		rpo2r[i] = rpo2r[nr - 1 - i];
760 		rpo2r[nr - 1 - i] = r1;
761 	}
762 	for(i = 0; i < nr; i++)
763 		rpo2r[i]->rpo = i;
764 
765 	idom[0] = 0;
766 	for(i = 0; i < nr; i++){
767 		r1 = rpo2r[i];
768 		me = r1->rpo;
769 		d = -1;
770 		if(r1->p1 != R && r1->p1->rpo < me)
771 			d = r1->p1->rpo;
772 		for(r1 = r1->p2; r1 != nil; r1 = r1->p2link)
773 			if(r1->rpo < me)
774 				d = rpolca(idom, d, r1->rpo);
775 		idom[i] = d;
776 	}
777 
778 	for(i = 0; i < nr; i++){
779 		r1 = rpo2r[i];
780 		r1->loop++;
781 		if(r1->p2 != R && loophead(idom, r1))
782 			loopmark(rpo2r, i, r1);
783 	}
784 }
785 
786 void
787 synch(Reg *r, Bits dif)
788 {
789 	Reg *r1;
790 	int z;
791 
792 	for(r1 = r; r1 != R; r1 = r1->s1) {
793 		for(z=0; z<BITS; z++) {
794 			dif.b[z] = (dif.b[z] &
795 				~(~r1->refbehind.b[z] & r1->refahead.b[z])) |
796 					r1->set.b[z] | r1->regdiff.b[z];
797 			if(dif.b[z] != r1->regdiff.b[z]) {
798 				r1->regdiff.b[z] = dif.b[z];
799 				change++;
800 			}
801 		}
802 		if(r1->active)
803 			break;
804 		r1->active = 1;
805 		for(z=0; z<BITS; z++)
806 			dif.b[z] &= ~(~r1->calbehind.b[z] & r1->calahead.b[z]);
807 		if(r1->s2 != R)
808 			synch(r1->s2, dif);
809 	}
810 }
811 
812 ulong
813 allreg(ulong b, Rgn *r)
814 {
815 	Var *v;
816 	int i;
817 
818 	v = var + r->varno;
819 	r->regno = 0;
820 	switch(v->etype) {
821 
822 	default:
823 		diag(Z, "unknown etype %d/%d", bitno(b), v->etype);
824 		break;
825 
826 	case TCHAR:
827 	case TUCHAR:
828 	case TSHORT:
829 	case TUSHORT:
830 	case TINT:
831 	case TUINT:
832 	case TLONG:
833 	case TULONG:
834 	case TIND:
835 	case TARRAY:
836 		i = BtoR(~b);
837 		if(i && r->cost > 0) {
838 			r->regno = i;
839 			return RtoB(i);
840 		}
841 		break;
842 
843 	case TDOUBLE:
844 	case TFLOAT:
845 		i = BtoF(~b);
846 		if(i && r->cost > 0) {
847 			r->regno = i+NREG;
848 			return FtoB(i);
849 		}
850 		break;
851 	}
852 	return 0;
853 }
854 
855 void
856 paint1(Reg *r, int bn)
857 {
858 	Reg *r1;
859 	Prog *p;
860 	int z;
861 	ulong bb;
862 
863 	z = bn/32;
864 	bb = 1L<<(bn%32);
865 	if(r->act.b[z] & bb)
866 		return;
867 	for(;;) {
868 		if(!(r->refbehind.b[z] & bb))
869 			break;
870 		r1 = r->p1;
871 		if(r1 == R)
872 			break;
873 		if(!(r1->refahead.b[z] & bb))
874 			break;
875 		if(r1->act.b[z] & bb)
876 			break;
877 		r = r1;
878 	}
879 
880 	if(LOAD(r) & ~(r->set.b[z]&~(r->use1.b[z]|r->use2.b[z])) & bb) {
881 		change -= CLOAD * r->loop;
882 		if(debug['R'] && debug['v'])
883 			print("%ld%P\tld %B $%d\n", r->loop,
884 				r->prog, blsh(bn), change);
885 	}
886 	for(;;) {
887 		r->act.b[z] |= bb;
888 		p = r->prog;
889 
890 		if(r->use1.b[z] & bb) {
891 			change += CREF * r->loop;
892 			if(p->to.type == D_FREG && p->as == AMOVW)
893 				change = -CINF;		/* cant go Rreg to Freg */
894 			if(debug['R'] && debug['v'])
895 				print("%ld%P\tu1 %B $%d\n", r->loop,
896 					p, blsh(bn), change);
897 		}
898 
899 		if((r->use2.b[z]|r->set.b[z]) & bb) {
900 			change += CREF * r->loop;
901 			if(p->from.type == D_FREG && p->as == AMOVW)
902 				change = -CINF;		/* cant go Rreg to Freg */
903 			if(debug['R'] && debug['v'])
904 				print("%ld%P\tu2 %B $%d\n", r->loop,
905 					p, blsh(bn), change);
906 		}
907 
908 		if(STORE(r) & r->regdiff.b[z] & bb) {
909 			change -= CLOAD * r->loop;
910 			if(debug['R'] && debug['v'])
911 				print("%ld%P\tst %B $%d\n", r->loop,
912 					p, blsh(bn), change);
913 		}
914 
915 		if(r->refbehind.b[z] & bb)
916 			for(r1 = r->p2; r1 != R; r1 = r1->p2link)
917 				if(r1->refahead.b[z] & bb)
918 					paint1(r1, bn);
919 
920 		if(!(r->refahead.b[z] & bb))
921 			break;
922 		r1 = r->s2;
923 		if(r1 != R)
924 			if(r1->refbehind.b[z] & bb)
925 				paint1(r1, bn);
926 		r = r->s1;
927 		if(r == R)
928 			break;
929 		if(r->act.b[z] & bb)
930 			break;
931 		if(!(r->refbehind.b[z] & bb))
932 			break;
933 	}
934 }
935 
936 ulong
937 paint2(Reg *r, int bn)
938 {
939 	Reg *r1;
940 	int z;
941 	ulong bb, vreg;
942 
943 	z = bn/32;
944 	bb = 1L << (bn%32);
945 	vreg = regbits;
946 	if(!(r->act.b[z] & bb))
947 		return vreg;
948 	for(;;) {
949 		if(!(r->refbehind.b[z] & bb))
950 			break;
951 		r1 = r->p1;
952 		if(r1 == R)
953 			break;
954 		if(!(r1->refahead.b[z] & bb))
955 			break;
956 		if(!(r1->act.b[z] & bb))
957 			break;
958 		r = r1;
959 	}
960 	for(;;) {
961 		r->act.b[z] &= ~bb;
962 
963 		vreg |= r->regu;
964 
965 		if(r->refbehind.b[z] & bb)
966 			for(r1 = r->p2; r1 != R; r1 = r1->p2link)
967 				if(r1->refahead.b[z] & bb)
968 					vreg |= paint2(r1, bn);
969 
970 		if(!(r->refahead.b[z] & bb))
971 			break;
972 		r1 = r->s2;
973 		if(r1 != R)
974 			if(r1->refbehind.b[z] & bb)
975 				vreg |= paint2(r1, bn);
976 		r = r->s1;
977 		if(r == R)
978 			break;
979 		if(!(r->act.b[z] & bb))
980 			break;
981 		if(!(r->refbehind.b[z] & bb))
982 			break;
983 	}
984 	return vreg;
985 }
986 
987 void
988 paint3(Reg *r, int bn, long rb, int rn)
989 {
990 	Reg *r1;
991 	Prog *p;
992 	int z;
993 	ulong bb;
994 
995 	z = bn/32;
996 	bb = 1L << (bn%32);
997 	if(r->act.b[z] & bb)
998 		return;
999 	for(;;) {
1000 		if(!(r->refbehind.b[z] & bb))
1001 			break;
1002 		r1 = r->p1;
1003 		if(r1 == R)
1004 			break;
1005 		if(!(r1->refahead.b[z] & bb))
1006 			break;
1007 		if(r1->act.b[z] & bb)
1008 			break;
1009 		r = r1;
1010 	}
1011 
1012 	if(LOAD(r) & ~(r->set.b[z] & ~(r->use1.b[z]|r->use2.b[z])) & bb)
1013 		addmove(r, bn, rn, 0);
1014 	for(;;) {
1015 		r->act.b[z] |= bb;
1016 		p = r->prog;
1017 
1018 		if(r->use1.b[z] & bb) {
1019 			if(debug['R'])
1020 				print("%P", p);
1021 			addreg(&p->from, rn);
1022 			if(debug['R'])
1023 				print("\t.c%P\n", p);
1024 		}
1025 		if((r->use2.b[z]|r->set.b[z]) & bb) {
1026 			if(debug['R'])
1027 				print("%P", p);
1028 			addreg(&p->to, rn);
1029 			if(debug['R'])
1030 				print("\t.c%P\n", p);
1031 		}
1032 
1033 		if(STORE(r) & r->regdiff.b[z] & bb)
1034 			addmove(r, bn, rn, 1);
1035 		r->regu |= rb;
1036 
1037 		if(r->refbehind.b[z] & bb)
1038 			for(r1 = r->p2; r1 != R; r1 = r1->p2link)
1039 				if(r1->refahead.b[z] & bb)
1040 					paint3(r1, bn, rb, rn);
1041 
1042 		if(!(r->refahead.b[z] & bb))
1043 			break;
1044 		r1 = r->s2;
1045 		if(r1 != R)
1046 			if(r1->refbehind.b[z] & bb)
1047 				paint3(r1, bn, rb, rn);
1048 		r = r->s1;
1049 		if(r == R)
1050 			break;
1051 		if(r->act.b[z] & bb)
1052 			break;
1053 		if(!(r->refbehind.b[z] & bb))
1054 			break;
1055 	}
1056 }
1057 
1058 void
1059 addreg(Adr *a, int rn)
1060 {
1061 
1062 	a->sym = 0;
1063 	a->name = D_NONE;
1064 	a->type = D_REG;
1065 	a->reg = rn;
1066 	if(rn >= NREG) {
1067 		a->type = D_FREG;
1068 		a->reg = rn-NREG;
1069 	}
1070 }
1071 
1072 /*
1073  * track register variables including external registers:
1074  *	bit	reg
1075  *	0	R7
1076  *	1	R8
1077  *	...	...
1078  *	21	R28
1079  */
1080 long
1081 RtoB(int r)
1082 {
1083 
1084 	if(r >= REGMIN && r <= REGMAX)
1085 		return 1L << (r-REGMIN);
1086 	return 0;
1087 }
1088 
1089 int
1090 BtoR(long b)
1091 {
1092 	b &= 0x001fffffL;
1093 	if(b == 0)
1094 		return 0;
1095 	return bitno(b) + REGMIN;
1096 }
1097 
1098 /*
1099  *	bit	reg
1100  *	22	F17
1101  *	23	F18
1102  *	...	...
1103  *	31	F26
1104  */
1105 long
1106 FtoB(int f)
1107 {
1108 	if(f < FREGMIN || f > FREGEXT)
1109 		return 0;
1110 	return 1L << (f - FREGMIN + 22);
1111 }
1112 
1113 int
1114 BtoF(long b)
1115 {
1116 
1117 	b &= 0xffc00000L;
1118 	if(b == 0)
1119 		return 0;
1120 	return bitno(b) - 22 + FREGMIN;
1121 }
1122