1 #include "gc.h"
2
3 static int
needc(Prog * p)4 needc(Prog *p)
5 {
6 while(p != P) {
7 switch(p->as) {
8 case AADCL:
9 case AADCQ:
10 case ASBBL:
11 case ASBBQ:
12 case ARCRL:
13 case ARCRQ:
14 return 1;
15 case AADDL:
16 case AADDQ:
17 case ASUBL:
18 case ASUBQ:
19 case AJMP:
20 case ARET:
21 case ACALL:
22 return 0;
23 default:
24 if(p->to.type == D_BRANCH)
25 return 0;
26 }
27 p = p->link;
28 }
29 return 0;
30 }
31
32 static Reg*
rnops(Reg * r)33 rnops(Reg *r)
34 {
35 Prog *p;
36 Reg *r1;
37
38 if(r != R)
39 for(;;){
40 p = r->prog;
41 if(p->as != ANOP || p->from.type != D_NONE || p->to.type != D_NONE)
42 break;
43 r1 = uniqs(r);
44 if(r1 == R)
45 break;
46 r = r1;
47 }
48 return r;
49 }
50
51 void
peep(void)52 peep(void)
53 {
54 Reg *r, *r1, *r2;
55 Prog *p, *p1;
56 int t;
57
58 /*
59 * complete R structure
60 */
61 t = 0;
62 for(r=firstr; r!=R; r=r1) {
63 r1 = r->link;
64 if(r1 == R)
65 break;
66 p = r->prog->link;
67 while(p != r1->prog)
68 switch(p->as) {
69 default:
70 r2 = rega();
71 r->link = r2;
72 r2->link = r1;
73
74 r2->prog = p;
75 r2->p1 = r;
76 r->s1 = r2;
77 r2->s1 = r1;
78 r1->p1 = r2;
79
80 r = r2;
81 t++;
82
83 case ADATA:
84 case AGLOBL:
85 case ANAME:
86 case ASIGNAME:
87 p = p->link;
88 }
89 }
90
91 pc = 0; /* speculating it won't kill */
92
93 loop1:
94
95 t = 0;
96 for(r=firstr; r!=R; r=r->link) {
97 p = r->prog;
98 switch(p->as) {
99 case AMOVL:
100 case AMOVQ:
101 case AMOVSS:
102 case AMOVSD:
103 if(regtyp(&p->to))
104 if(regtyp(&p->from)) {
105 if(copyprop(r)) {
106 excise(r);
107 t++;
108 } else
109 if(subprop(r) && copyprop(r)) {
110 excise(r);
111 t++;
112 }
113 }
114 break;
115
116 case AMOVBLZX:
117 case AMOVWLZX:
118 case AMOVBLSX:
119 case AMOVWLSX:
120 case AMOVQL:
121 if(regtyp(&p->to)) {
122 r1 = rnops(uniqs(r));
123 if(r1 != R) {
124 p1 = r1->prog;
125 if(p->as == p1->as && p->to.type == p1->from.type){
126 p1->as = AMOVL;
127 t++;
128 }
129 }
130 }
131 break;
132
133 case AMOVBQSX:
134 case AMOVBQZX:
135 case AMOVWQSX:
136 case AMOVWQZX:
137 case AMOVLQSX:
138 case AMOVLQZX:
139 if(regtyp(&p->to)) {
140 r1 = rnops(uniqs(r));
141 if(r1 != R) {
142 p1 = r1->prog;
143 if(p->as == p1->as && p->to.type == p1->from.type){
144 p1->as = AMOVQ;
145 t++;
146 }
147 }
148 }
149 break;
150
151 case AADDL:
152 case AADDQ:
153 case AADDW:
154 if(p->from.type != D_CONST || needc(p->link))
155 break;
156 if(p->from.offset == -1){
157 if(p->as == AADDQ)
158 p->as = ADECQ;
159 else if(p->as == AADDL)
160 p->as = ADECL;
161 else
162 p->as = ADECW;
163 p->from = zprog.from;
164 }
165 else if(p->from.offset == 1){
166 if(p->as == AADDQ)
167 p->as = AINCQ;
168 else if(p->as == AADDL)
169 p->as = AINCL;
170 else
171 p->as = AINCW;
172 p->from = zprog.from;
173 }
174 break;
175
176 case ASUBL:
177 case ASUBQ:
178 case ASUBW:
179 if(p->from.type != D_CONST || needc(p->link))
180 break;
181 if(p->from.offset == -1) {
182 if(p->as == ASUBQ)
183 p->as = AINCQ;
184 else if(p->as == ASUBL)
185 p->as = AINCL;
186 else
187 p->as = AINCW;
188 p->from = zprog.from;
189 }
190 else if(p->from.offset == 1){
191 if(p->as == ASUBQ)
192 p->as = ADECQ;
193 else if(p->as == ASUBL)
194 p->as = ADECL;
195 else
196 p->as = ADECW;
197 p->from = zprog.from;
198 }
199 break;
200 }
201 }
202 if(t)
203 goto loop1;
204 }
205
206 void
excise(Reg * r)207 excise(Reg *r)
208 {
209 Prog *p;
210
211 p = r->prog;
212 p->as = ANOP;
213 p->from = zprog.from;
214 p->to = zprog.to;
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 int t;
253
254 t = a->type;
255 if(t >= D_AX && t <= D_R15)
256 return 1;
257 if(t >= D_X0 && t <= D_X0+15)
258 return 1;
259 return 0;
260 }
261
262 /*
263 * the idea is to substitute
264 * one register for another
265 * from one MOV to another
266 * MOV a, R0
267 * ADD b, R0 / no use of R1
268 * MOV R0, R1
269 * would be converted to
270 * MOV a, R1
271 * ADD b, R1
272 * MOV R1, R0
273 * hopefully, then the former or latter MOV
274 * will be eliminated by copy propagation.
275 */
276 int
subprop(Reg * r0)277 subprop(Reg *r0)
278 {
279 Prog *p;
280 Adr *v1, *v2;
281 Reg *r;
282 int t;
283
284 p = r0->prog;
285 v1 = &p->from;
286 if(!regtyp(v1))
287 return 0;
288 v2 = &p->to;
289 if(!regtyp(v2))
290 return 0;
291 for(r=uniqp(r0); r!=R; r=uniqp(r)) {
292 if(uniqs(r) == R)
293 break;
294 p = r->prog;
295 switch(p->as) {
296 case ACALL:
297 return 0;
298
299 case AIMULL:
300 case AIMULQ:
301 case AIMULW:
302 if(p->to.type != D_NONE)
303 break;
304
305 case ADIVB:
306 case ADIVL:
307 case ADIVQ:
308 case ADIVW:
309 case AIDIVB:
310 case AIDIVL:
311 case AIDIVQ:
312 case AIDIVW:
313 case AIMULB:
314 case AMULB:
315 case AMULL:
316 case AMULQ:
317 case AMULW:
318
319 case AROLB:
320 case AROLL:
321 case AROLQ:
322 case AROLW:
323 case ARORB:
324 case ARORL:
325 case ARORQ:
326 case ARORW:
327 case ASALB:
328 case ASALL:
329 case ASALQ:
330 case ASALW:
331 case ASARB:
332 case ASARL:
333 case ASARQ:
334 case ASARW:
335 case ASHLB:
336 case ASHLL:
337 case ASHLQ:
338 case ASHLW:
339 case ASHRB:
340 case ASHRL:
341 case ASHRQ:
342 case ASHRW:
343
344 case AREP:
345 case AREPN:
346
347 case ACWD:
348 case ACDQ:
349 case ACQO:
350
351 case ASTOSB:
352 case ASTOSL:
353 case ASTOSQ:
354 case AMOVSB:
355 case AMOVSL:
356 case AMOVSQ:
357 case AMOVQL:
358 return 0;
359
360 case AMOVL:
361 case AMOVQ:
362 if(p->to.type == v1->type)
363 goto gotit;
364 break;
365 }
366 if(copyau(&p->from, v2) ||
367 copyau(&p->to, v2))
368 break;
369 if(copysub(&p->from, v1, v2, 0) ||
370 copysub(&p->to, v1, v2, 0))
371 break;
372 }
373 return 0;
374
375 gotit:
376 copysub(&p->to, v1, v2, 1);
377 if(debug['P']) {
378 print("gotit: %D->%D\n%P", v1, v2, r->prog);
379 if(p->from.type == v2->type)
380 print(" excise");
381 print("\n");
382 }
383 for(r=uniqs(r); r!=r0; r=uniqs(r)) {
384 p = r->prog;
385 copysub(&p->from, v1, v2, 1);
386 copysub(&p->to, v1, v2, 1);
387 if(debug['P'])
388 print("%P\n", r->prog);
389 }
390 t = v1->type;
391 v1->type = v2->type;
392 v2->type = t;
393 if(debug['P'])
394 print("%P last\n", r->prog);
395 return 1;
396 }
397
398 /*
399 * The idea is to remove redundant copies.
400 * v1->v2 F=0
401 * (use v2 s/v2/v1/)*
402 * set v1 F=1
403 * use v2 return fail
404 * -----------------
405 * v1->v2 F=0
406 * (use v2 s/v2/v1/)*
407 * set v1 F=1
408 * set v2 return success
409 */
410 int
copyprop(Reg * r0)411 copyprop(Reg *r0)
412 {
413 Prog *p;
414 Adr *v1, *v2;
415 Reg *r;
416
417 p = r0->prog;
418 v1 = &p->from;
419 v2 = &p->to;
420 if(copyas(v1, v2))
421 return 1;
422 for(r=firstr; r!=R; r=r->link)
423 r->active = 0;
424 return copy1(v1, v2, r0->s1, 0);
425 }
426
427 int
copy1(Adr * v1,Adr * v2,Reg * r,int f)428 copy1(Adr *v1, Adr *v2, Reg *r, int f)
429 {
430 int t;
431 Prog *p;
432
433 if(r->active) {
434 if(debug['P'])
435 print("act set; return 1\n");
436 return 1;
437 }
438 r->active = 1;
439 if(debug['P'])
440 print("copy %D->%D f=%d\n", v1, v2, f);
441 for(; r != R; r = r->s1) {
442 p = r->prog;
443 if(debug['P'])
444 print("%P", p);
445 if(!f && uniqp(r) == R) {
446 f = 1;
447 if(debug['P'])
448 print("; merge; f=%d", f);
449 }
450 t = copyu(p, v2, A);
451 switch(t) {
452 case 2: /* rar, cant split */
453 if(debug['P'])
454 print("; %D rar; return 0\n", v2);
455 return 0;
456
457 case 3: /* set */
458 if(debug['P'])
459 print("; %D set; return 1\n", v2);
460 return 1;
461
462 case 1: /* used, substitute */
463 case 4: /* use and set */
464 if(f) {
465 if(!debug['P'])
466 return 0;
467 if(t == 4)
468 print("; %D used+set and f=%d; return 0\n", v2, f);
469 else
470 print("; %D used and f=%d; return 0\n", v2, f);
471 return 0;
472 }
473 if(copyu(p, v2, v1)) {
474 if(debug['P'])
475 print("; sub fail; return 0\n");
476 return 0;
477 }
478 if(debug['P'])
479 print("; sub %D/%D", v2, v1);
480 if(t == 4) {
481 if(debug['P'])
482 print("; %D used+set; return 1\n", v2);
483 return 1;
484 }
485 break;
486 }
487 if(!f) {
488 t = copyu(p, v1, A);
489 if(!f && (t == 2 || t == 3 || t == 4)) {
490 f = 1;
491 if(debug['P'])
492 print("; %D set and !f; f=%d", v1, f);
493 }
494 }
495 if(debug['P'])
496 print("\n");
497 if(r->s2)
498 if(!copy1(v1, v2, r->s2, f))
499 return 0;
500 }
501 return 1;
502 }
503
504 /*
505 * return
506 * 1 if v only used (and substitute),
507 * 2 if read-alter-rewrite
508 * 3 if set
509 * 4 if set and used
510 * 0 otherwise (not touched)
511 */
512 int
copyu(Prog * p,Adr * v,Adr * s)513 copyu(Prog *p, Adr *v, Adr *s)
514 {
515
516 switch(p->as) {
517
518 default:
519 if(debug['P'])
520 print("unknown op %A\n", p->as);
521 /* SBBL; ADCL; FLD1; SAHF */
522 return 2;
523
524
525 case ANEGB:
526 case ANEGW:
527 case ANEGL:
528 case ANEGQ:
529 case ANOTB:
530 case ANOTW:
531 case ANOTL:
532 case ANOTQ:
533 if(copyas(&p->to, v))
534 return 2;
535 break;
536
537 case ALEAL: /* lhs addr, rhs store */
538 case ALEAQ:
539 if(copyas(&p->from, v))
540 return 2;
541
542
543 case ANOP: /* rhs store */
544 case AMOVL:
545 case AMOVQ:
546 case AMOVBLSX:
547 case AMOVBLZX:
548 case AMOVBQSX:
549 case AMOVBQZX:
550 case AMOVLQSX:
551 case AMOVLQZX:
552 case AMOVWLSX:
553 case AMOVWLZX:
554 case AMOVWQSX:
555 case AMOVWQZX:
556 case AMOVQL:
557
558 case AMOVSS:
559 case AMOVSD:
560 case ACVTSD2SL:
561 case ACVTSD2SQ:
562 case ACVTSD2SS:
563 case ACVTSL2SD:
564 case ACVTSL2SS:
565 case ACVTSQ2SD:
566 case ACVTSQ2SS:
567 case ACVTSS2SD:
568 case ACVTSS2SL:
569 case ACVTSS2SQ:
570 case ACVTTSD2SL:
571 case ACVTTSD2SQ:
572 case ACVTTSS2SL:
573 case ACVTTSS2SQ:
574 if(copyas(&p->to, v)) {
575 if(s != A)
576 return copysub(&p->from, v, s, 1);
577 if(copyau(&p->from, v))
578 return 4;
579 return 3;
580 }
581 goto caseread;
582
583 case AROLB:
584 case AROLL:
585 case AROLQ:
586 case AROLW:
587 case ARORB:
588 case ARORL:
589 case ARORQ:
590 case ARORW:
591 case ASALB:
592 case ASALL:
593 case ASALQ:
594 case ASALW:
595 case ASARB:
596 case ASARL:
597 case ASARQ:
598 case ASARW:
599 case ASHLB:
600 case ASHLL:
601 case ASHLQ:
602 case ASHLW:
603 case ASHRB:
604 case ASHRL:
605 case ASHRQ:
606 case ASHRW:
607 if(copyas(&p->to, v))
608 return 2;
609 if(copyas(&p->from, v))
610 if(p->from.type == D_CX)
611 return 2;
612 goto caseread;
613
614 case AADDB: /* rhs rar */
615 case AADDL:
616 case AADDQ:
617 case AADDW:
618 case AANDB:
619 case AANDL:
620 case AANDQ:
621 case AANDW:
622 case ADECL:
623 case ADECQ:
624 case ADECW:
625 case AINCL:
626 case AINCQ:
627 case AINCW:
628 case ASUBB:
629 case ASUBL:
630 case ASUBQ:
631 case ASUBW:
632 case AORB:
633 case AORL:
634 case AORQ:
635 case AORW:
636 case AXORB:
637 case AXORL:
638 case AXORQ:
639 case AXORW:
640 case AMOVB:
641 case AMOVW:
642
643 case AADDSD:
644 case AADDSS:
645 case ACMPSD:
646 case ACMPSS:
647 case ADIVSD:
648 case ADIVSS:
649 case AMAXSD:
650 case AMAXSS:
651 case AMINSD:
652 case AMINSS:
653 case AMULSD:
654 case AMULSS:
655 case ARCPSS:
656 case ARSQRTSS:
657 case ASQRTSD:
658 case ASQRTSS:
659 case ASUBSD:
660 case ASUBSS:
661 case AXORPD:
662 if(copyas(&p->to, v))
663 return 2;
664 goto caseread;
665
666 case ACMPL: /* read only */
667 case ACMPW:
668 case ACMPB:
669 case ACMPQ:
670
671 case ACOMISD:
672 case ACOMISS:
673 case AUCOMISD:
674 case AUCOMISS:
675 caseread:
676 if(s != A) {
677 if(copysub(&p->from, v, s, 1))
678 return 1;
679 return copysub(&p->to, v, s, 1);
680 }
681 if(copyau(&p->from, v))
682 return 1;
683 if(copyau(&p->to, v))
684 return 1;
685 break;
686
687 case AJGE: /* no reference */
688 case AJNE:
689 case AJLE:
690 case AJEQ:
691 case AJHI:
692 case AJLS:
693 case AJMI:
694 case AJPL:
695 case AJGT:
696 case AJLT:
697 case AJCC:
698 case AJCS:
699
700 case AADJSP:
701 case AWAIT:
702 case ACLD:
703 break;
704
705 case AIMULL:
706 case AIMULQ:
707 case AIMULW:
708 if(p->to.type != D_NONE) {
709 if(copyas(&p->to, v))
710 return 2;
711 goto caseread;
712 }
713
714 case ADIVB:
715 case ADIVL:
716 case ADIVQ:
717 case ADIVW:
718 case AIDIVB:
719 case AIDIVL:
720 case AIDIVQ:
721 case AIDIVW:
722 case AIMULB:
723 case AMULB:
724 case AMULL:
725 case AMULQ:
726 case AMULW:
727
728 case ACWD:
729 case ACDQ:
730 case ACQO:
731 if(v->type == D_AX || v->type == D_DX)
732 return 2;
733 goto caseread;
734
735 case AREP:
736 case AREPN:
737 if(v->type == D_CX)
738 return 2;
739 goto caseread;
740
741 case AMOVSB:
742 case AMOVSL:
743 case AMOVSQ:
744 if(v->type == D_DI || v->type == D_SI)
745 return 2;
746 goto caseread;
747
748 case ASTOSB:
749 case ASTOSL:
750 case ASTOSQ:
751 if(v->type == D_AX || v->type == D_DI)
752 return 2;
753 goto caseread;
754
755 case AJMP: /* funny */
756 if(s != A) {
757 if(copysub(&p->to, v, s, 1))
758 return 1;
759 return 0;
760 }
761 if(copyau(&p->to, v))
762 return 1;
763 return 0;
764
765 case ARET: /* funny */
766 if(v->type == REGRET || v->type == FREGRET)
767 return 2;
768 if(s != A)
769 return 1;
770 return 3;
771
772 case ACALL: /* funny */
773 if(REGEXT && v->type <= REGEXT && v->type > exregoffset)
774 return 2;
775 if(REGARG && v->type == REGARG)
776 return 2;
777
778 if(s != A) {
779 if(copysub(&p->to, v, s, 1))
780 return 1;
781 return 0;
782 }
783 if(copyau(&p->to, v))
784 return 4;
785 return 3;
786
787 case ATEXT: /* funny */
788 if(REGARG && v->type == REGARG)
789 return 3;
790 return 0;
791 }
792 return 0;
793 }
794
795 /*
796 * direct reference,
797 * could be set/use depending on
798 * semantics
799 */
800 int
copyas(Adr * a,Adr * v)801 copyas(Adr *a, Adr *v)
802 {
803 if(a->type != v->type)
804 return 0;
805 if(regtyp(v))
806 return 1;
807 if(v->type == D_AUTO || v->type == D_PARAM)
808 if(v->offset == a->offset)
809 return 1;
810 return 0;
811 }
812
813 /*
814 * either direct or indirect
815 */
816 int
copyau(Adr * a,Adr * v)817 copyau(Adr *a, Adr *v)
818 {
819
820 if(copyas(a, v))
821 return 1;
822 if(regtyp(v)) {
823 if(a->type-D_INDIR == v->type)
824 return 1;
825 if(a->index == v->type)
826 return 1;
827 }
828 return 0;
829 }
830
831 /*
832 * substitute s for v in a
833 * return failure to substitute
834 */
835 int
copysub(Adr * a,Adr * v,Adr * s,int f)836 copysub(Adr *a, Adr *v, Adr *s, int f)
837 {
838 int t;
839
840 if(copyas(a, v)) {
841 t = s->type;
842 if(t >= D_AX && t <= D_R15 || t >= D_X0 && t <= D_X0+15) {
843 if(f)
844 a->type = t;
845 }
846 return 0;
847 }
848 if(regtyp(v)) {
849 t = v->type;
850 if(a->type == t+D_INDIR) {
851 if((s->type == D_BP || s->type == D_R13) && a->index != D_NONE)
852 return 1; /* can't use BP-base with index */
853 if(f)
854 a->type = s->type+D_INDIR;
855 // return 0;
856 }
857 if(a->index == t) {
858 if(f)
859 a->index = s->type;
860 return 0;
861 }
862 return 0;
863 }
864 return 0;
865 }
866