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