xref: /plan9-contrib/sys/src/cmd/5c/peep.c (revision 40d015479ed36701ae6dcfd8814f849fc6285e8d) 
1 #include "gc.h"
2 
3 int xtramodes(Reg*, Adr*);
4 
5 void
peep(void)6 peep(void)
7 {
8 	Reg *r, *r1, *r2;
9 	Prog *p, *p1;
10 	int t;
11 /*
12  * complete R structure
13  */
14 	t = 0;
15 	for(r=firstr; r!=R; r=r1) {
16 		r1 = r->link;
17 		if(r1 == R)
18 			break;
19 		p = r->prog->link;
20 		while(p != r1->prog)
21 		switch(p->as) {
22 		default:
23 			r2 = rega();
24 			r->link = r2;
25 			r2->link = r1;
26 
27 			r2->prog = p;
28 			r2->p1 = r;
29 			r->s1 = r2;
30 			r2->s1 = r1;
31 			r1->p1 = r2;
32 
33 			r = r2;
34 			t++;
35 
36 		case ADATA:
37 		case AGLOBL:
38 		case ANAME:
39 		case ASIGNAME:
40 			p = p->link;
41 		}
42 	}
43 
44 loop1:
45 	t = 0;
46 	for(r=firstr; r!=R; r=r->link) {
47 		p = r->prog;
48 		if(p->as == ASLL || p->as == ASRL || p->as == ASRA) {
49 			/*
50 			 * elide shift into D_SHIFT operand of subsequent instruction
51 			 */
52 			if(shiftprop(r)) {
53 				excise(r);
54 				t++;
55 			}
56 		}
57 		if(p->as == AMOVW || p->as == AMOVF || p->as == AMOVD)
58 		if(regtyp(&p->to)) {
59 			if(p->from.type == D_CONST)
60 				constprop(&p->from, &p->to, r->s1);
61 			else if(regtyp(&p->from))
62 			if(p->from.type == p->to.type) {
63 				if(copyprop(r)) {
64 					excise(r);
65 					t++;
66 				} else
67 				if(subprop(r) && copyprop(r)) {
68 					excise(r);
69 					t++;
70 				}
71 			}
72 		}
73 	}
74 	if(t)
75 		goto loop1;
76 	/*
77 	 * look for MOVB x,R; MOVB R,R
78 	 */
79 	for(r=firstr; r!=R; r=r->link) {
80 		p = r->prog;
81 		switch(p->as) {
82 		default:
83 			continue;
84 		case AEOR:
85 			/*
86 			 * EOR -1,x,y => MVN x,y
87 			 */
88 			if(p->from.type == D_CONST && p->from.offset == -1) {
89 				p->as = AMVN;
90 				p->from.type = D_REG;
91 				if(p->reg != NREG)
92 					p->from.reg = p->reg;
93 				else
94 					p->from.reg = p->to.reg;
95 				p->reg = NREG;
96 			}
97 			continue;
98 		case AMOVH:
99 		case AMOVHU:
100 		case AMOVB:
101 		case AMOVBU:
102 			if(p->to.type != D_REG)
103 				continue;
104 			break;
105 		}
106 		r1 = r->link;
107 		if(r1 == R)
108 			continue;
109 		p1 = r1->prog;
110 		if(p1->as != p->as)
111 			continue;
112 		if(p1->from.type != D_REG || p1->from.reg != p->to.reg)
113 			continue;
114 		if(p1->to.type != D_REG || p1->to.reg != p->to.reg)
115 			continue;
116 		excise(r1);
117 	}
118 
119 	for(r=firstr; r!=R; r=r->link) {
120 		p = r->prog;
121 		switch(p->as) {
122 		case AMOVW:
123 		case AMOVB:
124 		case AMOVBU:
125 			if(p->from.type == D_OREG && p->from.offset == 0)
126 				xtramodes(r, &p->from);
127 			else if(p->to.type == D_OREG && p->to.offset == 0)
128 				xtramodes(r, &p->to);
129 			else
130 				continue;
131 			break;
132 		case ACMP:
133 			/*
134 			 * elide CMP $0,x if calculation of x can set condition codes
135 			 */
136 			if(p->from.type != D_CONST || p->from.offset != 0)
137 				continue;
138 			r2 = r->s1;
139 			if(r2 == R)
140 				continue;
141 			t = r2->prog->as;
142 			switch(t) {
143 			default:
144 				continue;
145 			case ABEQ:
146 			case ABNE:
147 			case ABMI:
148 			case ABPL:
149 				break;
150 			case ABGE:
151 				t = ABPL;
152 				break;
153 			case ABLT:
154 				t = ABMI;
155 				break;
156 			case ABHI:
157 				t = ABNE;
158 				break;
159 			case ABLS:
160 				t = ABEQ;
161 				break;
162 			}
163 			r1 = r;
164 			do
165 				r1 = uniqp(r1);
166 			while (r1 != R && r1->prog->as == ANOP);
167 			if(r1 == R)
168 				continue;
169 			p1 = r1->prog;
170 			if(p1->to.type != D_REG)
171 				continue;
172 			if(p1->to.reg != p->reg)
173 			if(!(p1->as == AMOVW && p1->from.type == D_REG && p1->from.reg == p->reg))
174 				continue;
175 			switch(p1->as) {
176 			default:
177 				continue;
178 			case AMOVW:
179 				if(p1->from.type != D_REG)
180 					continue;
181 			case AAND:
182 			case AEOR:
183 			case AORR:
184 			case ABIC:
185 			case AMVN:
186 			case ASUB:
187 			case ARSB:
188 			case AADD:
189 			case AADC:
190 			case ASBC:
191 			case ARSC:
192 				break;
193 			}
194 			p1->scond |= C_SBIT;
195 			r2->prog->as = t;
196 			excise(r);
197 			continue;
198 		}
199 	}
200 
201 	predicate();
202 }
203 
204 void
excise(Reg * r)205 excise(Reg *r)
206 {
207 	Prog *p;
208 
209 	p = r->prog;
210 	p->as = ANOP;
211 	p->scond = zprog.scond;
212 	p->from = zprog.from;
213 	p->to = zprog.to;
214 	p->reg = zprog.reg; /**/
215 }
216 
217 Reg*
uniqp(Reg * r)218 uniqp(Reg *r)
219 {
220 	Reg *r1;
221 
222 	r1 = r->p1;
223 	if(r1 == R) {
224 		r1 = r->p2;
225 		if(r1 == R || r1->p2link != R)
226 			return R;
227 	} else
228 		if(r->p2 != R)
229 			return R;
230 	return r1;
231 }
232 
233 Reg*
uniqs(Reg * r)234 uniqs(Reg *r)
235 {
236 	Reg *r1;
237 
238 	r1 = r->s1;
239 	if(r1 == R) {
240 		r1 = r->s2;
241 		if(r1 == R)
242 			return R;
243 	} else
244 		if(r->s2 != R)
245 			return R;
246 	return r1;
247 }
248 
249 int
regtyp(Adr * a)250 regtyp(Adr *a)
251 {
252 
253 	if(a->type == D_REG)
254 		return 1;
255 	if(a->type == D_FREG)
256 		return 1;
257 	return 0;
258 }
259 
260 /*
261  * the idea is to substitute
262  * one register for another
263  * from one MOV to another
264  *	MOV	a, R0
265  *	ADD	b, R0	/ no use of R1
266  *	MOV	R0, R1
267  * would be converted to
268  *	MOV	a, R1
269  *	ADD	b, R1
270  *	MOV	R1, R0
271  * hopefully, then the former or latter MOV
272  * will be eliminated by copy propagation.
273  */
274 int
subprop(Reg * r0)275 subprop(Reg *r0)
276 {
277 	Prog *p;
278 	Adr *v1, *v2;
279 	Reg *r;
280 	int t;
281 
282 	p = r0->prog;
283 	v1 = &p->from;
284 	if(!regtyp(v1))
285 		return 0;
286 	v2 = &p->to;
287 	if(!regtyp(v2))
288 		return 0;
289 	for(r=uniqp(r0); r!=R; r=uniqp(r)) {
290 		if(uniqs(r) == R)
291 			break;
292 		p = r->prog;
293 		switch(p->as) {
294 		case ABL:
295 			return 0;
296 
297 		case ACMP:
298 		case ACMN:
299 		case AADD:
300 		case ASUB:
301 		case ARSB:
302 		case ASLL:
303 		case ASRL:
304 		case ASRA:
305 		case AORR:
306 		case AAND:
307 		case AEOR:
308 		case AMUL:
309 		case AMULU:
310 		case ADIV:
311 		case ADIVU:
312 
313 		case ACMPF:
314 		case ACMPD:
315 		case AADDD:
316 		case AADDF:
317 		case ASUBD:
318 		case ASUBF:
319 		case AMULD:
320 		case AMULF:
321 		case ADIVD:
322 		case ADIVF:
323 			if(p->to.type == v1->type)
324 			if(p->to.reg == v1->reg) {
325 				if(p->reg == NREG)
326 					p->reg = p->to.reg;
327 				goto gotit;
328 			}
329 			break;
330 
331 		case AMOVF:
332 		case AMOVD:
333 		case AMOVW:
334 			if(p->to.type == v1->type)
335 			if(p->to.reg == v1->reg)
336 				goto gotit;
337 			break;
338 
339 		case AMOVM:
340 			t = 1<<v2->reg;
341 			if((p->from.type == D_CONST && (p->from.offset&t)) ||
342 			   (p->to.type == D_CONST && (p->to.offset&t)))
343 				return 0;
344 			break;
345 		}
346 		if(copyau(&p->from, v2) ||
347 		   copyau1(p, v2) ||
348 		   copyau(&p->to, v2))
349 			break;
350 		if(copysub(&p->from, v1, v2, 0) ||
351 		   copysub1(p, v1, v2, 0) ||
352 		   copysub(&p->to, v1, v2, 0))
353 			break;
354 	}
355 	return 0;
356 
357 gotit:
358 	copysub(&p->to, v1, v2, 1);
359 	if(debug['P']) {
360 		print("gotit: %D->%D\n%P", v1, v2, r->prog);
361 		if(p->from.type == v2->type)
362 			print(" excise");
363 		print("\n");
364 	}
365 	for(r=uniqs(r); r!=r0; r=uniqs(r)) {
366 		p = r->prog;
367 		copysub(&p->from, v1, v2, 1);
368 		copysub1(p, v1, v2, 1);
369 		copysub(&p->to, v1, v2, 1);
370 		if(debug['P'])
371 			print("%P\n", r->prog);
372 	}
373 	t = v1->reg;
374 	v1->reg = v2->reg;
375 	v2->reg = t;
376 	if(debug['P'])
377 		print("%P last\n", r->prog);
378 	return 1;
379 }
380 
381 /*
382  * The idea is to remove redundant copies.
383  *	v1->v2	F=0
384  *	(use v2	s/v2/v1/)*
385  *	set v1	F=1
386  *	use v2	return fail
387  *	-----------------
388  *	v1->v2	F=0
389  *	(use v2	s/v2/v1/)*
390  *	set v1	F=1
391  *	set v2	return success
392  */
393 int
copyprop(Reg * r0)394 copyprop(Reg *r0)
395 {
396 	Prog *p;
397 	Adr *v1, *v2;
398 	Reg *r;
399 
400 	p = r0->prog;
401 	v1 = &p->from;
402 	v2 = &p->to;
403 	if(copyas(v1, v2))
404 		return 1;
405 	for(r=firstr; r!=R; r=r->link)
406 		r->active = 0;
407 	return copy1(v1, v2, r0->s1, 0);
408 }
409 
410 int
copy1(Adr * v1,Adr * v2,Reg * r,int f)411 copy1(Adr *v1, Adr *v2, Reg *r, int f)
412 {
413 	int t;
414 	Prog *p;
415 
416 	if(r->active) {
417 		if(debug['P'])
418 			print("act set; return 1\n");
419 		return 1;
420 	}
421 	r->active = 1;
422 	if(debug['P'])
423 		print("copy %D->%D f=%d\n", v1, v2, f);
424 	for(; r != R; r = r->s1) {
425 		p = r->prog;
426 		if(debug['P'])
427 			print("%P", p);
428 		if(!f && uniqp(r) == R) {
429 			f = 1;
430 			if(debug['P'])
431 				print("; merge; f=%d", f);
432 		}
433 		t = copyu(p, v2, A);
434 		switch(t) {
435 		case 2:	/* rar, cant split */
436 			if(debug['P'])
437 				print("; %Drar; return 0\n", v2);
438 			return 0;
439 
440 		case 3:	/* set */
441 			if(debug['P'])
442 				print("; %Dset; return 1\n", v2);
443 			return 1;
444 
445 		case 1:	/* used, substitute */
446 		case 4:	/* use and set */
447 			if(f) {
448 				if(!debug['P'])
449 					return 0;
450 				if(t == 4)
451 					print("; %Dused+set and f=%d; return 0\n", v2, f);
452 				else
453 					print("; %Dused and f=%d; return 0\n", v2, f);
454 				return 0;
455 			}
456 			if(copyu(p, v2, v1)) {
457 				if(debug['P'])
458 					print("; sub fail; return 0\n");
459 				return 0;
460 			}
461 			if(debug['P'])
462 				print("; sub%D/%D", v2, v1);
463 			if(t == 4) {
464 				if(debug['P'])
465 					print("; %Dused+set; return 1\n", v2);
466 				return 1;
467 			}
468 			break;
469 		}
470 		if(!f) {
471 			t = copyu(p, v1, A);
472 			if(!f && (t == 2 || t == 3 || t == 4)) {
473 				f = 1;
474 				if(debug['P'])
475 					print("; %Dset and !f; f=%d", v1, f);
476 			}
477 		}
478 		if(debug['P'])
479 			print("\n");
480 		if(r->s2)
481 			if(!copy1(v1, v2, r->s2, f))
482 				return 0;
483 	}
484 	return 1;
485 }
486 
487 /*
488  * The idea is to remove redundant constants.
489  *	$c1->v1
490  *	($c1->v2 s/$c1/v1)*
491  *	set v1  return
492  * The v1->v2 should be eliminated by copy propagation.
493  */
494 void
constprop(Adr * c1,Adr * v1,Reg * r)495 constprop(Adr *c1, Adr *v1, Reg *r)
496 {
497 	Prog *p;
498 
499 	if(debug['C'])
500 		print("constprop %D->%D\n", c1, v1);
501 	for(; r != R; r = r->s1) {
502 		p = r->prog;
503 		if(debug['C'])
504 			print("%P", p);
505 		if(uniqp(r) == R) {
506 			if(debug['C'])
507 				print("; merge; return\n");
508 			return;
509 		}
510 		if(p->as == AMOVW && copyas(&p->from, c1)) {
511 				if(debug['C'])
512 					print("; sub%D/%D", &p->from, v1);
513 				p->from = *v1;
514 		} else if(copyu(p, v1, A) > 1) {
515 			if(debug['C'])
516 				print("; %Dset; return\n", v1);
517 			return;
518 		}
519 		if(debug['C'])
520 			print("\n");
521 		if(r->s2)
522 			constprop(c1, v1, r->s2);
523 	}
524 }
525 
526 /*
527  * ASLL x,y,w
528  * .. (not use w, not set x y w)
529  * AXXX w,a,b (a != w)
530  * .. (not use w)
531  * (set w)
532  * ----------- changed to
533  * ..
534  * AXXX (x<<y),a,b
535  * ..
536  */
537 #define FAIL(msg) { if(debug['H']) print("\t%s; FAILURE\n", msg); return 0; }
538 int
shiftprop(Reg * r)539 shiftprop(Reg *r)
540 {
541 	Reg *r1;
542 	Prog *p, *p1, *p2;
543 	int n, o;
544 	Adr a;
545 
546 	p = r->prog;
547 	if(p->to.type != D_REG)
548 		FAIL("BOTCH: result not reg");
549 	n = p->to.reg;
550 	a = zprog.from;
551 	if(p->reg != NREG && p->reg != p->to.reg) {
552 		a.type = D_REG;
553 		a.reg = p->reg;
554 	}
555 	if(debug['H'])
556 		print("shiftprop\n%P", p);
557 	r1 = r;
558 	for(;;) {
559 		/* find first use of shift result; abort if shift operands or result are changed */
560 		r1 = uniqs(r1);
561 		if(r1 == R)
562 			FAIL("branch");
563 		if(uniqp(r1) == R)
564 			FAIL("merge");
565 		p1 = r1->prog;
566 		if(debug['H'])
567 			print("\n%P", p1);
568 		switch(copyu(p1, &p->to, A)) {
569 		case 0:	/* not used or set */
570 			if((p->from.type == D_REG && copyu(p1, &p->from, A) > 1) ||
571 			   (a.type == D_REG && copyu(p1, &a, A) > 1))
572 				FAIL("args modified");
573 			continue;
574 		case 3:	/* set, not used */
575 			FAIL("BOTCH: noref");
576 		}
577 		break;
578 	}
579 	/* check whether substitution can be done */
580 	switch(p1->as) {
581 	default:
582 		FAIL("non-dpi");
583 	case AAND:
584 	case AEOR:
585 	case AADD:
586 	case AADC:
587 	case AORR:
588 	case ASUB:
589 	case ARSB:
590 	case ASBC:
591 	case ARSC:
592 		if(p1->reg == n || (p1->reg == NREG && p1->to.type == D_REG && p1->to.reg == n)) {
593 			if(p1->from.type != D_REG)
594 				FAIL("can't swap");
595 			p1->reg = p1->from.reg;
596 			p1->from.reg = n;
597 			switch(p1->as) {
598 			case ASUB:
599 				p1->as = ARSB;
600 				break;
601 			case ARSB:
602 				p1->as = ASUB;
603 				break;
604 			case ASBC:
605 				p1->as = ARSC;
606 				break;
607 			case ARSC:
608 				p1->as = ASBC;
609 				break;
610 			}
611 			if(debug['H'])
612 				print("\t=>%P", p1);
613 		}
614 	case ABIC:
615 	case ACMP:
616 	case ACMN:
617 		if(p1->reg == n)
618 			FAIL("can't swap");
619 		if(p1->reg == NREG && p1->to.reg == n)
620 			FAIL("shift result used twice");
621 	case AMVN:
622 		if(p1->from.type == D_SHIFT)
623 			FAIL("shift result used in shift");
624 		if(p1->from.type != D_REG || p1->from.reg != n)
625 			FAIL("BOTCH: where is it used?");
626 		break;
627 	}
628 	/* check whether shift result is used subsequently */
629 	p2 = p1;
630 	if(p1->to.reg != n)
631 	for (;;) {
632 		r1 = uniqs(r1);
633 		if(r1 == R)
634 			FAIL("inconclusive");
635 		p1 = r1->prog;
636 		if(debug['H'])
637 			print("\n%P", p1);
638 		switch(copyu(p1, &p->to, A)) {
639 		case 0:	/* not used or set */
640 			continue;
641 		case 3: /* set, not used */
642 			break;
643 		default:/* used */
644 			FAIL("reused");
645 		}
646 		break;
647 	}
648 	/* make the substitution */
649 	p2->from.type = D_SHIFT;
650 	p2->from.reg = NREG;
651 	o = p->reg;
652 	if(o == NREG)
653 		o = p->to.reg;
654 	switch(p->from.type){
655 	case D_CONST:
656 		o |= (p->from.offset&0x1f)<<7;
657 		break;
658 	case D_REG:
659 		o |= (1<<4) | (p->from.reg<<8);
660 		break;
661 	}
662 	switch(p->as){
663 	case ASLL:
664 		o |= 0<<5;
665 		break;
666 	case ASRL:
667 		o |= 1<<5;
668 		break;
669 	case ASRA:
670 		o |= 2<<5;
671 		break;
672 	}
673 	p2->from.offset = o;
674 	if(debug['H'])
675 		print("\t=>%P\tSUCCEED\n", p2);
676 	return 1;
677 }
678 
679 Reg*
findpre(Reg * r,Adr * v)680 findpre(Reg *r, Adr *v)
681 {
682 	Reg *r1;
683 
684 	for(r1=uniqp(r); r1!=R; r=r1,r1=uniqp(r)) {
685 		if(uniqs(r1) != r)
686 			return R;
687 		switch(copyu(r1->prog, v, A)) {
688 		case 1: /* used */
689 		case 2: /* read-alter-rewrite */
690 			return R;
691 		case 3: /* set */
692 		case 4: /* set and used */
693 			return r1;
694 		}
695 	}
696 	return R;
697 }
698 
699 Reg*
findinc(Reg * r,Reg * r2,Adr * v)700 findinc(Reg *r, Reg *r2, Adr *v)
701 {
702 	Reg *r1;
703 	Prog *p;
704 
705 
706 	for(r1=uniqs(r); r1!=R && r1!=r2; r=r1,r1=uniqs(r)) {
707 		if(uniqp(r1) != r)
708 			return R;
709 		switch(copyu(r1->prog, v, A)) {
710 		case 0: /* not touched */
711 			continue;
712 		case 4: /* set and used */
713 			p = r1->prog;
714 			if(p->as == AADD)
715 			if(p->from.type == D_CONST)
716 			if(p->from.offset > -4096 && p->from.offset < 4096)
717 				return r1;
718 		default:
719 			return R;
720 		}
721 	}
722 	return R;
723 }
724 
725 int
nochange(Reg * r,Reg * r2,Prog * p)726 nochange(Reg *r, Reg *r2, Prog *p)
727 {
728 	Adr a[3];
729 	int i, n;
730 
731 	if(r == r2)
732 		return 1;
733 	n = 0;
734 	if(p->reg != NREG && p->reg != p->to.reg) {
735 		a[n].type = D_REG;
736 		a[n++].reg = p->reg;
737 	}
738 	switch(p->from.type) {
739 	case D_SHIFT:
740 		a[n].type = D_REG;
741 		a[n++].reg = p->from.offset&0xf;
742 	case D_REG:
743 		a[n].type = D_REG;
744 		a[n++].reg = p->from.reg;
745 	}
746 	if(n == 0)
747 		return 1;
748 	for(; r!=R && r!=r2; r=uniqs(r)) {
749 		p = r->prog;
750 		for(i=0; i<n; i++)
751 			if(copyu(p, &a[i], A) > 1)
752 				return 0;
753 	}
754 	return 1;
755 }
756 
757 int
findu1(Reg * r,Adr * v)758 findu1(Reg *r, Adr *v)
759 {
760 	for(; r != R; r = r->s1) {
761 		if(r->active)
762 			return 0;
763 		r->active = 1;
764 		switch(copyu(r->prog, v, A)) {
765 		case 1: /* used */
766 		case 2: /* read-alter-rewrite */
767 		case 4: /* set and used */
768 			return 1;
769 		case 3: /* set */
770 			return 0;
771 		}
772 		if(r->s2)
773 			if (findu1(r->s2, v))
774 				return 1;
775 	}
776 	return 0;
777 }
778 
779 int
finduse(Reg * r,Adr * v)780 finduse(Reg *r, Adr *v)
781 {
782 	Reg *r1;
783 
784 	for(r1=firstr; r1!=R; r1=r1->link)
785 		r1->active = 0;
786 	return findu1(r, v);
787 }
788 
789 int
xtramodes(Reg * r,Adr * a)790 xtramodes(Reg *r, Adr *a)
791 {
792 	Reg *r1, *r2, *r3;
793 	Prog *p, *p1;
794 	Adr v;
795 
796 	p = r->prog;
797 	if(debug['h'] && p->as == AMOVB && p->from.type == D_OREG)	/* byte load */
798 		return 0;
799 	v = *a;
800 	v.type = D_REG;
801 	r1 = findpre(r, &v);
802 	if(r1 != R) {
803 		p1 = r1->prog;
804 		if(p1->to.type == D_REG && p1->to.reg == v.reg)
805 		switch(p1->as) {
806 		case AADD:
807 			if(p1->from.type == D_REG ||
808 			   (p1->from.type == D_SHIFT && (p1->from.offset&(1<<4)) == 0 &&
809 			    (p->as != AMOVB || (a == &p->from && (p1->from.offset&~0xf) == 0))) ||
810 			   (p1->from.type == D_CONST &&
811 			    p1->from.offset > -4096 && p1->from.offset < 4096))
812 			if(nochange(uniqs(r1), r, p1)) {
813 				if(a != &p->from || v.reg != p->to.reg)
814 				if (finduse(r->s1, &v)) {
815 					if(p1->reg == NREG || p1->reg == v.reg)
816 						/* pre-indexing */
817 						p->scond |= C_WBIT;
818 					else return 0;
819 				}
820 				switch (p1->from.type) {
821 				case D_REG:
822 					/* register offset */
823 					a->type = D_SHIFT;
824 					a->offset = p1->from.reg;
825 					break;
826 				case D_SHIFT:
827 					/* scaled register offset */
828 					a->type = D_SHIFT;
829 				case D_CONST:
830 					/* immediate offset */
831 					a->offset = p1->from.offset;
832 					break;
833 				}
834 				if(p1->reg != NREG)
835 					a->reg = p1->reg;
836 				excise(r1);
837 				return 1;
838 			}
839 			break;
840 		case AMOVW:
841 			if(p1->from.type == D_REG)
842 			if((r2 = findinc(r1, r, &p1->from)) != R) {
843 			for(r3=uniqs(r2); r3->prog->as==ANOP; r3=uniqs(r3))
844 				;
845 			if(r3 == r) {
846 				/* post-indexing */
847 				p1 = r2->prog;
848 				a->reg = p1->to.reg;
849 				a->offset = p1->from.offset;
850 				p->scond |= C_PBIT;
851 				if(!finduse(r, &r1->prog->to))
852 					excise(r1);
853 				excise(r2);
854 				return 1;
855 			}
856 			}
857 			break;
858 		}
859 	}
860 	if(a != &p->from || a->reg != p->to.reg)
861 	if((r1 = findinc(r, R, &v)) != R) {
862 		/* post-indexing */
863 		p1 = r1->prog;
864 		a->offset = p1->from.offset;
865 		p->scond |= C_PBIT;
866 		excise(r1);
867 		return 1;
868 	}
869 	return 0;
870 }
871 
872 /*
873  * return
874  * 1 if v only used (and substitute),
875  * 2 if read-alter-rewrite
876  * 3 if set
877  * 4 if set and used
878  * 0 otherwise (not touched)
879  */
880 int
copyu(Prog * p,Adr * v,Adr * s)881 copyu(Prog *p, Adr *v, Adr *s)
882 {
883 
884 	switch(p->as) {
885 
886 	default:
887 		if(debug['P'])
888 			print(" (???)");
889 		return 2;
890 
891 	case AMOVM:
892 		if(v->type != D_REG)
893 			return 0;
894 		if(p->from.type == D_CONST) {	/* read reglist, read/rar */
895 			if(s != A) {
896 				if(p->from.offset&(1<<v->reg))
897 					return 1;
898 				if(copysub(&p->to, v, s, 1))
899 					return 1;
900 				return 0;
901 			}
902 			if(copyau(&p->to, v)) {
903 				if(p->scond&C_WBIT)
904 					return 2;
905 				return 1;
906 			}
907 			if(p->from.offset&(1<<v->reg))
908 				return 1;
909 		} else {			/* read/rar, write reglist */
910 			if(s != A) {
911 				if(p->to.offset&(1<<v->reg))
912 					return 1;
913 				if(copysub(&p->from, v, s, 1))
914 					return 1;
915 				return 0;
916 			}
917 			if(copyau(&p->from, v)) {
918 				if(p->scond&C_WBIT)
919 					return 2;
920 				if(p->to.offset&(1<<v->reg))
921 					return 4;
922 				return 1;
923 			}
924 			if(p->to.offset&(1<<v->reg))
925 				return 3;
926 		}
927 		return 0;
928 
929 	case ANOP:	/* read, write */
930 	case AMOVW:
931 	case AMOVF:
932 	case AMOVD:
933 	case AMOVH:
934 	case AMOVHU:
935 	case AMOVB:
936 	case AMOVBU:
937 	case AMOVDW:
938 	case AMOVWD:
939 	case AMOVFD:
940 	case AMOVDF:
941 		if(p->scond&(C_WBIT|C_PBIT))
942 		if(v->type == D_REG) {
943 			if(p->from.type == D_OREG || p->from.type == D_SHIFT) {
944 				if(p->from.reg == v->reg)
945 					return 2;
946 			} else {
947 		  		if(p->to.reg == v->reg)
948 				return 2;
949 			}
950 		}
951 		if(s != A) {
952 			if(copysub(&p->from, v, s, 1))
953 				return 1;
954 			if(!copyas(&p->to, v))
955 				if(copysub(&p->to, v, s, 1))
956 					return 1;
957 			return 0;
958 		}
959 		if(copyas(&p->to, v)) {
960 			if(copyau(&p->from, v))
961 				return 4;
962 			return 3;
963 		}
964 		if(copyau(&p->from, v))
965 			return 1;
966 		if(copyau(&p->to, v))
967 			return 1;
968 		return 0;
969 
970 
971 	case AADD:	/* read, read, write */
972 	case ASUB:
973 	case ARSB:
974 	case ASLL:
975 	case ASRL:
976 	case ASRA:
977 	case AORR:
978 	case AAND:
979 	case AEOR:
980 	case AMUL:
981 	case AMULU:
982 	case ADIV:
983 	case ADIVU:
984 	case AADDF:
985 	case AADDD:
986 	case ASUBF:
987 	case ASUBD:
988 	case AMULF:
989 	case AMULD:
990 	case ADIVF:
991 	case ADIVD:
992 
993 	case ACMPF:
994 	case ACMPD:
995 	case ACMP:
996 	case ACMN:
997 	case ACASE:
998 		if(s != A) {
999 			if(copysub(&p->from, v, s, 1))
1000 				return 1;
1001 			if(copysub1(p, v, s, 1))
1002 				return 1;
1003 			if(!copyas(&p->to, v))
1004 				if(copysub(&p->to, v, s, 1))
1005 					return 1;
1006 			return 0;
1007 		}
1008 		if(copyas(&p->to, v)) {
1009 			if(p->reg == NREG)
1010 				p->reg = p->to.reg;
1011 			if(copyau(&p->from, v))
1012 				return 4;
1013 			if(copyau1(p, v))
1014 				return 4;
1015 			return 3;
1016 		}
1017 		if(copyau(&p->from, v))
1018 			return 1;
1019 		if(copyau1(p, v))
1020 			return 1;
1021 		if(copyau(&p->to, v))
1022 			return 1;
1023 		return 0;
1024 
1025 	case ABEQ:	/* read, read */
1026 	case ABNE:
1027 	case ABCS:
1028 	case ABHS:
1029 	case ABCC:
1030 	case ABLO:
1031 	case ABMI:
1032 	case ABPL:
1033 	case ABVS:
1034 	case ABVC:
1035 	case ABHI:
1036 	case ABLS:
1037 	case ABGE:
1038 	case ABLT:
1039 	case ABGT:
1040 	case ABLE:
1041 		if(s != A) {
1042 			if(copysub(&p->from, v, s, 1))
1043 				return 1;
1044 			return copysub1(p, v, s, 1);
1045 		}
1046 		if(copyau(&p->from, v))
1047 			return 1;
1048 		if(copyau1(p, v))
1049 			return 1;
1050 		return 0;
1051 
1052 	case AB:	/* funny */
1053 		if(s != A) {
1054 			if(copysub(&p->to, v, s, 1))
1055 				return 1;
1056 			return 0;
1057 		}
1058 		if(copyau(&p->to, v))
1059 			return 1;
1060 		return 0;
1061 
1062 	case ARET:	/* funny */
1063 		if(v->type == D_REG)
1064 		if(v->reg == REGRET)
1065 			return 2;
1066 		if(v->type == D_FREG)
1067 		if(v->reg == FREGRET)
1068 			return 2;
1069 
1070 	case ABL:	/* funny */
1071 		if(v->type == D_REG) {
1072 			if(v->reg <= REGEXT && v->reg > exregoffset)
1073 				return 2;
1074 			if(v->reg == (uchar)REGARG)
1075 				return 2;
1076 		}
1077 		if(v->type == D_FREG)
1078 			if(v->reg <= FREGEXT && v->reg > exfregoffset)
1079 				return 2;
1080 
1081 		if(s != A) {
1082 			if(copysub(&p->to, v, s, 1))
1083 				return 1;
1084 			return 0;
1085 		}
1086 		if(copyau(&p->to, v))
1087 			return 4;
1088 		return 3;
1089 
1090 	case ATEXT:	/* funny */
1091 		if(v->type == D_REG)
1092 			if(v->reg == (uchar)REGARG)
1093 				return 3;
1094 		return 0;
1095 	}
1096 }
1097 
1098 int
a2type(Prog * p)1099 a2type(Prog *p)
1100 {
1101 
1102 	switch(p->as) {
1103 
1104 	case ACMP:
1105 	case ACMN:
1106 
1107 	case AADD:
1108 	case ASUB:
1109 	case ARSB:
1110 	case ASLL:
1111 	case ASRL:
1112 	case ASRA:
1113 	case AORR:
1114 	case AAND:
1115 	case AEOR:
1116 	case AMUL:
1117 	case AMULU:
1118 	case ADIV:
1119 	case ADIVU:
1120 		return D_REG;
1121 
1122 	case ACMPF:
1123 	case ACMPD:
1124 
1125 	case AADDF:
1126 	case AADDD:
1127 	case ASUBF:
1128 	case ASUBD:
1129 	case AMULF:
1130 	case AMULD:
1131 	case ADIVF:
1132 	case ADIVD:
1133 		return D_FREG;
1134 	}
1135 	return D_NONE;
1136 }
1137 
1138 /*
1139  * direct reference,
1140  * could be set/use depending on
1141  * semantics
1142  */
1143 int
copyas(Adr * a,Adr * v)1144 copyas(Adr *a, Adr *v)
1145 {
1146 
1147 	if(regtyp(v)) {
1148 		if(a->type == v->type)
1149 		if(a->reg == v->reg)
1150 			return 1;
1151 	} else if(v->type == D_CONST) {		/* for constprop */
1152 		if(a->type == v->type)
1153 		if(a->name == v->name)
1154 		if(a->sym == v->sym)
1155 		if(a->reg == v->reg)
1156 		if(a->offset == v->offset)
1157 			return 1;
1158 	}
1159 	return 0;
1160 }
1161 
1162 /*
1163  * either direct or indirect
1164  */
1165 int
copyau(Adr * a,Adr * v)1166 copyau(Adr *a, Adr *v)
1167 {
1168 
1169 	if(copyas(a, v))
1170 		return 1;
1171 	if(v->type == D_REG) {
1172 		if(a->type == D_OREG) {
1173 			if(v->reg == a->reg)
1174 				return 1;
1175 		} else if(a->type == D_SHIFT) {
1176 			if((a->offset&0xf) == v->reg)
1177 				return 1;
1178 			if((a->offset&(1<<4)) && (a->offset>>8) == v->reg)
1179 				return 1;
1180 		}
1181 	}
1182 	return 0;
1183 }
1184 
1185 int
copyau1(Prog * p,Adr * v)1186 copyau1(Prog *p, Adr *v)
1187 {
1188 
1189 	if(regtyp(v)) {
1190 		if(a2type(p) == v->type)
1191 		if(p->reg == v->reg) {
1192 			if(a2type(p) != v->type)
1193 				print("botch a2type %P\n", p);
1194 			return 1;
1195 		}
1196 	}
1197 	return 0;
1198 }
1199 
1200 /*
1201  * substitute s for v in a
1202  * return failure to substitute
1203  */
1204 int
copysub(Adr * a,Adr * v,Adr * s,int f)1205 copysub(Adr *a, Adr *v, Adr *s, int f)
1206 {
1207 
1208 	if(f)
1209 	if(copyau(a, v)) {
1210 		if(a->type == D_SHIFT) {
1211 			if((a->offset&0xf) == v->reg)
1212 				a->offset = (a->offset&~0xf)|s->reg;
1213 			if((a->offset&(1<<4)) && (a->offset>>8) == v->reg)
1214 				a->offset = (a->offset&~(0xf<<8))|(s->reg<<8);
1215 		} else
1216 			a->reg = s->reg;
1217 	}
1218 	return 0;
1219 }
1220 
1221 int
copysub1(Prog * p1,Adr * v,Adr * s,int f)1222 copysub1(Prog *p1, Adr *v, Adr *s, int f)
1223 {
1224 
1225 	if(f)
1226 	if(copyau1(p1, v))
1227 		p1->reg = s->reg;
1228 	return 0;
1229 }
1230 
1231 struct {
1232 	int opcode;
1233 	int notopcode;
1234 	int scond;
1235 	int notscond;
1236 } predinfo[]  = {
1237 	{ ABEQ,	ABNE,	0x0,	0x1, },
1238 	{ ABNE,	ABEQ,	0x1,	0x0, },
1239 	{ ABCS,	ABCC,	0x2,	0x3, },
1240 	{ ABHS,	ABLO,	0x2,	0x3, },
1241 	{ ABCC,	ABCS,	0x3,	0x2, },
1242 	{ ABLO,	ABHS,	0x3,	0x2, },
1243 	{ ABMI,	ABPL,	0x4,	0x5, },
1244 	{ ABPL,	ABMI,	0x5,	0x4, },
1245 	{ ABVS,	ABVC,	0x6,	0x7, },
1246 	{ ABVC,	ABVS,	0x7,	0x6, },
1247 	{ ABHI,	ABLS,	0x8,	0x9, },
1248 	{ ABLS,	ABHI,	0x9,	0x8, },
1249 	{ ABGE,	ABLT,	0xA,	0xB, },
1250 	{ ABLT,	ABGE,	0xB,	0xA, },
1251 	{ ABGT,	ABLE,	0xC,	0xD, },
1252 	{ ABLE,	ABGT,	0xD,	0xC, },
1253 };
1254 
1255 typedef struct {
1256 	Reg *start;
1257 	Reg *last;
1258 	Reg *end;
1259 	int len;
1260 } Joininfo;
1261 
1262 enum {
1263 	Join,
1264 	Split,
1265 	End,
1266 	Branch,
1267 	Setcond,
1268 	Toolong
1269 };
1270 
1271 enum {
1272 	Falsecond,
1273 	Truecond,
1274 	Delbranch,
1275 	Keepbranch
1276 };
1277 
1278 int
isbranch(Prog * p)1279 isbranch(Prog *p)
1280 {
1281 	return (ABEQ <= p->as) && (p->as <= ABLE);
1282 }
1283 
1284 int
predicable(Prog * p)1285 predicable(Prog *p)
1286 {
1287 	if (isbranch(p)
1288 		|| p->as == ANOP
1289 		|| p->as == AXXX
1290 		|| p->as == ADATA
1291 		|| p->as == AGLOBL
1292 		|| p->as == AGOK
1293 		|| p->as == AHISTORY
1294 		|| p->as == ANAME
1295 		|| p->as == ASIGNAME
1296 		|| p->as == ATEXT
1297 		|| p->as == AWORD
1298 		|| p->as == ADYNT
1299 		|| p->as == AINIT
1300 		|| p->as == ABCASE
1301 		|| p->as == ACASE)
1302 		return 0;
1303 	return 1;
1304 }
1305 
1306 /*
1307  * Depends on an analysis of the encodings performed by 5l.
1308  * These seem to be all of the opcodes that lead to the "S" bit
1309  * being set in the instruction encodings.
1310  *
1311  * C_SBIT may also have been set explicitly in p->scond.
1312  */
1313 int
modifiescpsr(Prog * p)1314 modifiescpsr(Prog *p)
1315 {
1316 	return (p->scond&C_SBIT)
1317 		|| p->as == ATST
1318 		|| p->as == ATEQ
1319 		|| p->as == ACMN
1320 		|| p->as == ACMP
1321 		|| p->as == AMULU
1322 		|| p->as == ADIVU
1323 		|| p->as == AMUL
1324 		|| p->as == ADIV
1325 		|| p->as == AMOD
1326 		|| p->as == AMODU
1327 		|| p->as == ABL;
1328 }
1329 
1330 /*
1331  * Find the maximal chain of instructions starting with r which could
1332  * be executed conditionally
1333  */
1334 int
joinsplit(Reg * r,Joininfo * j)1335 joinsplit(Reg *r, Joininfo *j)
1336 {
1337 	j->start = r;
1338 	j->last = r;
1339 	j->len = 0;
1340 	do {
1341 		if (r->p2 && (r->p1 || r->p2->p2link)) {
1342 			j->end = r;
1343 			return Join;
1344 		}
1345 		if (r->s1 && r->s2) {
1346 			j->end = r;
1347 			return Split;
1348 		}
1349 		j->last = r;
1350 		if (r->prog->as != ANOP)
1351 			j->len++;
1352 		if (!r->s1 && !r->s2) {
1353 			j->end = r->link;
1354 			return End;
1355 		}
1356 		if (r->s2) {
1357 			j->end = r->s2;
1358 			return Branch;
1359 		}
1360 		if (modifiescpsr(r->prog)) {
1361 			j->end = r->s1;
1362 			return Setcond;
1363 		}
1364 		r = r->s1;
1365 	} while (j->len < 4);
1366 	j->end = r;
1367 	return Toolong;
1368 }
1369 
1370 Reg *
successor(Reg * r)1371 successor(Reg *r)
1372 {
1373 	if (r->s1)
1374 		return r->s1;
1375 	else
1376 		return r->s2;
1377 }
1378 
1379 void
applypred(Reg * rstart,Joininfo * j,int cond,int branch)1380 applypred(Reg *rstart, Joininfo *j, int cond, int branch)
1381 {
1382 	int pred;
1383 	Reg *r;
1384 
1385 	if(j->len == 0)
1386 		return;
1387 	if (cond == Truecond)
1388 		pred = predinfo[rstart->prog->as - ABEQ].scond;
1389 	else
1390 		pred = predinfo[rstart->prog->as - ABEQ].notscond;
1391 
1392 	for (r = j->start; ; r = successor(r)) {
1393 		if (r->prog->as == AB) {
1394 			if (r != j->last || branch == Delbranch)
1395 				excise(r);
1396 			else {
1397 			  if (cond == Truecond)
1398 				r->prog->as = predinfo[rstart->prog->as - ABEQ].opcode;
1399 			  else
1400 				r->prog->as = predinfo[rstart->prog->as - ABEQ].notopcode;
1401 			}
1402 		}
1403 		else if (predicable(r->prog))
1404 			r->prog->scond = (r->prog->scond&~C_SCOND)|pred;
1405 		if (r->s1 != r->link) {
1406 			r->s1 = r->link;
1407 			r->link->p1 = r;
1408 		}
1409 		if (r == j->last)
1410 			break;
1411 	}
1412 }
1413 
1414 void
predicate(void)1415 predicate(void)
1416 {
1417 	Reg *r;
1418 	int t1, t2;
1419 	Joininfo j1, j2;
1420 
1421 	for(r=firstr; r!=R; r=r->link) {
1422 		if (isbranch(r->prog)) {
1423 			t1 = joinsplit(r->s1, &j1);
1424 			t2 = joinsplit(r->s2, &j2);
1425 			if(j1.last->link != j2.start)
1426 				continue;
1427 			if(j1.end == j2.end)
1428 			if((t1 == Branch && (t2 == Join || t2 == Setcond)) ||
1429 			   (t2 == Join && (t1 == Join || t1 == Setcond))) {
1430 				applypred(r, &j1, Falsecond, Delbranch);
1431 				applypred(r, &j2, Truecond, Delbranch);
1432 				excise(r);
1433 				continue;
1434 			}
1435 			if(t1 == End || t1 == Branch) {
1436 				applypred(r, &j1, Falsecond, Keepbranch);
1437 				excise(r);
1438 				continue;
1439 			}
1440 		}
1441 	}
1442 }
1443