1 #include "gc.h"
2
3 void
peep(void)4 peep(void)
5 {
6 Reg *r, *r1, *r2;
7 Prog *p, *p1;
8 int t;
9 /*
10 * complete R structure
11 */
12 t = 0;
13 for(r=firstr; r!=R; r=r1) {
14 r1 = r->link;
15 if(r1 == R)
16 break;
17 p = r->prog->link;
18 while(p != r1->prog)
19 switch(p->as) {
20 default:
21 r2 = rega();
22 r->link = r2;
23 r2->link = r1;
24
25 r2->prog = p;
26 r2->p1 = r;
27 r->s1 = r2;
28 r2->s1 = r1;
29 r1->p1 = r2;
30
31 r = r2;
32 t++;
33
34 case ADATA:
35 case AGLOBL:
36 case ANAME:
37 case ASIGNAME:
38 p = p->link;
39 }
40 }
41
42 loop1:
43 t = 0;
44 for(r=firstr; r!=R; r=r->link) {
45 p = r->prog;
46 if(p->as == AMOVW || p->as == AMOVF || p->as == AMOVD)
47 if(regtyp(&p->to)) {
48 if(p->from.type == D_CONST)
49 constprop(&p->from, &p->to, r->s1);
50 else if(regtyp(&p->from))
51 if(p->from.type == p->to.type) {
52 if(copyprop(r)) {
53 excise(r);
54 t++;
55 } else
56 if(subprop(r) && copyprop(r)) {
57 excise(r);
58 t++;
59 }
60 }
61 }
62 }
63 if(t)
64 goto loop1;
65 /*
66 * look for MOVB x,R; MOVB R,R
67 */
68 for(r=firstr; r!=R; r=r->link) {
69 p = r->prog;
70 switch(p->as) {
71 default:
72 continue;
73 case AEOR:
74 /*
75 * EOR -1,x,y => MVN x,y
76 */
77 if(p->from.type == D_CONST && p->from.offset == -1) {
78 p->as = AMVN;
79 p->from.type = D_REG;
80 if(p->reg != NREG)
81 p->from.reg = p->reg;
82 else
83 p->from.reg = p->to.reg;
84 p->reg = NREG;
85 }
86 continue;
87 case AMOVH:
88 case AMOVHU:
89 case AMOVB:
90 case AMOVBU:
91 if(p->to.type != D_REG)
92 continue;
93 break;
94 }
95 r1 = r->link;
96 if(r1 == R)
97 continue;
98 p1 = r1->prog;
99 if(p1->as != p->as)
100 continue;
101 if(p1->from.type != D_REG || p1->from.reg != p->to.reg)
102 continue;
103 if(p1->to.type != D_REG || p1->to.reg != p->to.reg)
104 continue;
105 excise(r1);
106 }
107 }
108
109 void
excise(Reg * r)110 excise(Reg *r)
111 {
112 Prog *p;
113
114 p = r->prog;
115 p->as = ANOP;
116 p->from = zprog.from;
117 p->to = zprog.to;
118 p->reg = zprog.reg; /**/
119 }
120
121 Reg*
uniqp(Reg * r)122 uniqp(Reg *r)
123 {
124 Reg *r1;
125
126 r1 = r->p1;
127 if(r1 == R) {
128 r1 = r->p2;
129 if(r1 == R || r1->p2link != R)
130 return R;
131 } else
132 if(r->p2 != R)
133 return R;
134 return r1;
135 }
136
137 Reg*
uniqs(Reg * r)138 uniqs(Reg *r)
139 {
140 Reg *r1;
141
142 r1 = r->s1;
143 if(r1 == R) {
144 r1 = r->s2;
145 if(r1 == R)
146 return R;
147 } else
148 if(r->s2 != R)
149 return R;
150 return r1;
151 }
152
153 int
regtyp(Adr * a)154 regtyp(Adr *a)
155 {
156
157 if(a->type == D_REG)
158 return 1;
159 if(a->type == D_FREG)
160 return 1;
161 return 0;
162 }
163
164 /*
165 * the idea is to substitute
166 * one register for another
167 * from one MOV to another
168 * MOV a, R0
169 * ADD b, R0 / no use of R1
170 * MOV R0, R1
171 * would be converted to
172 * MOV a, R1
173 * ADD b, R1
174 * MOV R1, R0
175 * hopefully, then the former or latter MOV
176 * will be eliminated by copy propagation.
177 */
178 int
subprop(Reg * r0)179 subprop(Reg *r0)
180 {
181 Prog *p;
182 Adr *v1, *v2;
183 Reg *r;
184 int t;
185
186 p = r0->prog;
187 v1 = &p->from;
188 if(!regtyp(v1))
189 return 0;
190 v2 = &p->to;
191 if(!regtyp(v2))
192 return 0;
193 for(r=uniqp(r0); r!=R; r=uniqp(r)) {
194 if(uniqs(r) == R)
195 break;
196 p = r->prog;
197 switch(p->as) {
198 case ABL:
199 case ABX:
200 return 0;
201
202 // case ACMP:
203 // case ACMN:
204 case AADD:
205 case ASUB:
206 // case ASLL:
207 // case ASRL:
208 // case ASRA:
209 // case AORR:
210 // case AAND:
211 // case AEOR:
212 // case AMUL:
213 // case ADIV:
214 // case ADIVU:
215
216 // case ACMPF:
217 // case ACMPD:
218 // case AADDD:
219 // case AADDF:
220 // case ASUBD:
221 // case ASUBF:
222 // case AMULD:
223 // case AMULF:
224 // case ADIVD:
225 // case ADIVF:
226 if(p->to.type == v1->type)
227 if(p->to.reg == v1->reg) {
228 if(p->reg == NREG)
229 p->reg = p->to.reg;
230 goto gotit;
231 }
232 break;
233
234 case AMOVF:
235 case AMOVD:
236 case AMOVW:
237 if(p->to.type == v1->type)
238 if(p->to.reg == v1->reg)
239 goto gotit;
240 break;
241
242 case AMOVM:
243 t = 1<<v2->reg;
244 if((p->from.type == D_CONST && (p->from.offset&t)) ||
245 (p->to.type == D_CONST && (p->to.offset&t)))
246 return 0;
247 break;
248 }
249 if(copyau(&p->from, v2) ||
250 copyau1(p, v2) ||
251 copyau(&p->to, v2))
252 break;
253 if(copysub(&p->from, v1, v2, 0) ||
254 copysub1(p, v1, v2, 0) ||
255 copysub(&p->to, v1, v2, 0))
256 break;
257 }
258 return 0;
259
260 gotit:
261 copysub(&p->to, v1, v2, 1);
262 if(debug['P']) {
263 print("gotit: %D->%D\n%P", v1, v2, r->prog);
264 if(p->from.type == v2->type)
265 print(" excise");
266 print("\n");
267 }
268 for(r=uniqs(r); r!=r0; r=uniqs(r)) {
269 p = r->prog;
270 copysub(&p->from, v1, v2, 1);
271 copysub1(p, v1, v2, 1);
272 copysub(&p->to, v1, v2, 1);
273 if(debug['P'])
274 print("%P\n", r->prog);
275 }
276 t = v1->reg;
277 v1->reg = v2->reg;
278 v2->reg = t;
279 if(debug['P'])
280 print("%P last\n", r->prog);
281 return 1;
282 }
283
284 /*
285 * The idea is to remove redundant copies.
286 * v1->v2 F=0
287 * (use v2 s/v2/v1/)*
288 * set v1 F=1
289 * use v2 return fail
290 * -----------------
291 * v1->v2 F=0
292 * (use v2 s/v2/v1/)*
293 * set v1 F=1
294 * set v2 return success
295 */
296 int
copyprop(Reg * r0)297 copyprop(Reg *r0)
298 {
299 Prog *p;
300 Adr *v1, *v2;
301 Reg *r;
302
303 p = r0->prog;
304 v1 = &p->from;
305 v2 = &p->to;
306 if(copyas(v1, v2))
307 return 1;
308 for(r=firstr; r!=R; r=r->link)
309 r->active = 0;
310 return copy1(v1, v2, r0->s1, 0);
311 }
312
313 int
copy1(Adr * v1,Adr * v2,Reg * r,int f)314 copy1(Adr *v1, Adr *v2, Reg *r, int f)
315 {
316 int t;
317 Prog *p;
318
319 if(r->active) {
320 if(debug['P'])
321 print("act set; return 1\n");
322 return 1;
323 }
324 r->active = 1;
325 if(debug['P'])
326 print("copy %D->%D f=%d\n", v1, v2, f);
327 for(; r != R; r = r->s1) {
328 p = r->prog;
329 if(debug['P'])
330 print("%P", p);
331 if(!f && uniqp(r) == R) {
332 f = 1;
333 if(debug['P'])
334 print("; merge; f=%d", f);
335 }
336 t = copyu(p, v2, A);
337 switch(t) {
338 case 2: /* rar, cant split */
339 if(debug['P'])
340 print("; %Drar; return 0\n", v2);
341 return 0;
342
343 case 3: /* set */
344 if(debug['P'])
345 print("; %Dset; return 1\n", v2);
346 return 1;
347
348 case 1: /* used, substitute */
349 case 4: /* use and set */
350 if(f) {
351 if(!debug['P'])
352 return 0;
353 if(t == 4)
354 print("; %Dused+set and f=%d; return 0\n", v2, f);
355 else
356 print("; %Dused and f=%d; return 0\n", v2, f);
357 return 0;
358 }
359 if(copyu(p, v2, v1)) {
360 if(debug['P'])
361 print("; sub fail; return 0\n");
362 return 0;
363 }
364 if(debug['P'])
365 print("; sub%D/%D", v2, v1);
366 if(t == 4) {
367 if(debug['P'])
368 print("; %Dused+set; return 1\n", v2);
369 return 1;
370 }
371 break;
372 }
373 if(!f) {
374 t = copyu(p, v1, A);
375 if(!f && (t == 2 || t == 3 || t == 4)) {
376 f = 1;
377 if(debug['P'])
378 print("; %Dset and !f; f=%d", v1, f);
379 }
380 }
381 if(debug['P'])
382 print("\n");
383 if(r->s2)
384 if(!copy1(v1, v2, r->s2, f))
385 return 0;
386 }
387 return 1;
388 }
389
390 /*
391 * The idea is to remove redundant constants.
392 * $c1->v1
393 * ($c1->v2 s/$c1/v1)*
394 * set v1 return
395 * The v1->v2 should be eliminated by copy propagation.
396 */
397 void
constprop(Adr * c1,Adr * v1,Reg * r)398 constprop(Adr *c1, Adr *v1, Reg *r)
399 {
400 Prog *p;
401
402 if(debug['C'])
403 print("constprop %D->%D\n", c1, v1);
404 for(; r != R; r = r->s1) {
405 p = r->prog;
406 if(debug['C'])
407 print("%P", p);
408 if(uniqp(r) == R) {
409 if(debug['C'])
410 print("; merge; return\n");
411 return;
412 }
413 if(p->as == AMOVW && copyas(&p->from, c1)) {
414 if(debug['C'])
415 print("; sub%D/%D", &p->from, v1);
416 p->from = *v1;
417 } else if(copyu(p, v1, A) > 1) {
418 if(debug['C'])
419 print("; %Dset; return\n", v1);
420 return;
421 }
422 if(debug['C'])
423 print("\n");
424 if(r->s2)
425 constprop(c1, v1, r->s2);
426 }
427 }
428
429 /*
430 * return
431 * 1 if v only used (and substitute),
432 * 2 if read-alter-rewrite
433 * 3 if set
434 * 4 if set and used
435 * 0 otherwise (not touched)
436 */
437 int
copyu(Prog * p,Adr * v,Adr * s)438 copyu(Prog *p, Adr *v, Adr *s)
439 {
440
441 switch(p->as) {
442
443 default:
444 if(debug['P'])
445 print(" (?)");
446 return 2;
447
448 case AMOVM:
449 if(v->type != D_REG)
450 return 0;
451 if(p->from.type == D_CONST) { /* read reglist, read/rar */
452 if(s != A) {
453 if(p->from.offset&(1<<v->reg))
454 return 1;
455 if(copysub(&p->to, v, s, 1))
456 diag(Z, "movm dst being replaced"); // was return 1;
457 return 0;
458 }
459 if(copyau(&p->to, v))
460 return 2; // register updated in thumb // was return 1;
461 if(p->from.offset&(1<<v->reg))
462 return 1;
463 } else { /* read/rar, write reglist */
464 if(s != A) {
465 if(p->to.offset&(1<<v->reg))
466 return 1;
467 if(copysub(&p->from, v, s, 1))
468 diag(Z, "movm src being replaced"); // was return 1;
469 return 0;
470 }
471 if(copyau(&p->from, v)) {
472 // if(p->to.offset&(1<<v->reg))
473 // return 4;
474 return 2; // register updated in thumb // was return 1;
475 }
476 if(p->to.offset&(1<<v->reg))
477 return 3;
478 }
479 return 0;
480
481 case ANOP: /* read, write */
482 case AMOVW:
483 case AMOVF:
484 case AMOVD:
485 case AMOVH:
486 case AMOVHU:
487 case AMOVB:
488 case AMOVBU:
489 case AMOVDW:
490 case AMOVWD:
491 case AMOVFD:
492 case AMOVDF:
493 if(s != A) {
494 if(copysub(&p->from, v, s, 1))
495 return 1;
496 if(!copyas(&p->to, v))
497 if(copysub(&p->to, v, s, 1))
498 return 1;
499 return 0;
500 }
501 if(copyas(&p->to, v)) {
502 if(copyau(&p->from, v))
503 return 4;
504 return 3;
505 }
506 if(copyau(&p->from, v))
507 return 1;
508 if(copyau(&p->to, v))
509 return 1;
510 return 0;
511
512 case ASLL:
513 case ASRL:
514 case ASRA:
515 case AORR:
516 case AAND:
517 case AEOR:
518 case AMUL:
519 case ADIV:
520 case ADIVU:
521 case AADDF:
522 case AADDD:
523 case ASUBF:
524 case ASUBD:
525 case AMULF:
526 case AMULD:
527 case ADIVF:
528 case ADIVD:
529 case ACMPF:
530 case ACMPD:
531 case ACMP:
532 case ACMN:
533 if(copyas(&p->to, v))
534 return 2;
535 /*FALLTHROUGH*/
536
537 case AADD: /* read, read, write */
538 case ASUB:
539 if(s != A) {
540 if(copysub(&p->from, v, s, 1))
541 return 1;
542 if(copysub1(p, v, s, 1))
543 return 1;
544 if(!copyas(&p->to, v))
545 if(copysub(&p->to, v, s, 1))
546 return 1;
547 return 0;
548 }
549 if(copyas(&p->to, v)) {
550 if(p->reg == NREG)
551 p->reg = p->to.reg;
552 if(copyau(&p->from, v))
553 return 4;
554 if(copyau1(p, v))
555 return 4;
556 return 3;
557 }
558 if(copyau(&p->from, v))
559 return 1;
560 if(copyau1(p, v))
561 return 1;
562 if(copyau(&p->to, v))
563 return 1;
564 return 0;
565
566 case ABEQ: /* read, read */
567 case ABNE:
568 case ABCS:
569 case ABHS:
570 case ABCC:
571 case ABLO:
572 case ABMI:
573 case ABPL:
574 case ABVS:
575 case ABVC:
576 case ABHI:
577 case ABLS:
578 case ABGE:
579 case ABLT:
580 case ABGT:
581 case ABLE:
582 if(s != A) {
583 if(copysub(&p->from, v, s, 1))
584 return 1;
585 return copysub1(p, v, s, 1);
586 }
587 if(copyau(&p->from, v))
588 return 1;
589 if(copyau1(p, v))
590 return 1;
591 return 0;
592
593 case AB: /* funny */
594 if(s != A) {
595 if(copysub(&p->to, v, s, 1))
596 return 1;
597 return 0;
598 }
599 if(copyau(&p->to, v))
600 return 1;
601 return 0;
602
603 case ARET: /* funny */
604 if(v->type == D_REG)
605 if(v->reg == REGRET)
606 return 2;
607 if(v->type == D_FREG)
608 if(v->reg == FREGRET)
609 return 2;
610
611 case ABL: /* funny */
612 case ABX:
613 if(v->type == D_REG) {
614 if(v->reg <= REGEXT && v->reg > exregoffset)
615 return 2;
616 if(v->reg == REGARG)
617 return 2;
618 }
619 if(v->type == D_FREG)
620 if(v->reg <= FREGEXT && v->reg > exfregoffset)
621 return 2;
622
623 if(s != A) {
624 if(copysub(&p->to, v, s, 1))
625 return 1;
626 return 0;
627 }
628 if(copyau(&p->to, v))
629 return 4;
630 return 3;
631
632 case ATEXT: /* funny */
633 if(v->type == D_REG)
634 if(v->reg == REGARG)
635 return 3;
636 return 0;
637 }
638 /* not reached */
639 }
640
641 int
a2type(Prog * p)642 a2type(Prog *p)
643 {
644
645 switch(p->as) {
646
647 case ACMP:
648 case ACMN:
649
650 case AADD:
651 case ASUB:
652 case ASLL:
653 case ASRL:
654 case ASRA:
655 case AORR:
656 case AAND:
657 case AEOR:
658 case AMUL:
659 case ADIV:
660 case ADIVU:
661 return D_REG;
662
663 case ACMPF:
664 case ACMPD:
665
666 case AADDF:
667 case AADDD:
668 case ASUBF:
669 case ASUBD:
670 case AMULF:
671 case AMULD:
672 case ADIVF:
673 case ADIVD:
674 return D_FREG;
675 }
676 return D_NONE;
677 }
678
679 /*
680 * direct reference,
681 * could be set/use depending on
682 * semantics
683 */
684 int
copyas(Adr * a,Adr * v)685 copyas(Adr *a, Adr *v)
686 {
687
688 if(regtyp(v)) {
689 if(a->type == v->type)
690 if(a->reg == v->reg)
691 return 1;
692 } else if(v->type == D_CONST) { /* for constprop */
693 if(a->type == v->type)
694 if(a->name == v->name)
695 if(a->sym == v->sym)
696 if(a->reg == v->reg)
697 if(a->offset == v->offset)
698 return 1;
699 }
700 return 0;
701 }
702
703 /*
704 * either direct or indirect
705 */
706 int
copyau(Adr * a,Adr * v)707 copyau(Adr *a, Adr *v)
708 {
709
710 if(copyas(a, v))
711 return 1;
712 if(v->type == D_REG) {
713 if(a->type == D_OREG) {
714 if(v->reg == a->reg)
715 return 1;
716 }
717 }
718 return 0;
719 }
720
721 int
copyau1(Prog * p,Adr * v)722 copyau1(Prog *p, Adr *v)
723 {
724
725 if(regtyp(v)) {
726 if(a2type(p) == v->type)
727 if(p->reg == v->reg) {
728 if(a2type(p) != v->type)
729 print("botch a2type %P\n", p);
730 return 1;
731 }
732 }
733 return 0;
734 }
735
736 /*
737 * substitute s for v in a
738 * return failure to substitute
739 */
740 int
copysub(Adr * a,Adr * v,Adr * s,int f)741 copysub(Adr *a, Adr *v, Adr *s, int f)
742 {
743
744 if(f)
745 if(copyau(a, v)) {
746 a->reg = s->reg;
747 }
748 return 0;
749 }
750
751 int
copysub1(Prog * p1,Adr * v,Adr * s,int f)752 copysub1(Prog *p1, Adr *v, Adr *s, int f)
753 {
754
755 if(f)
756 if(copyau1(p1, v))
757 p1->reg = s->reg;
758 return 0;
759 }
760