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