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 ASBBL:
10 case ARCRL:
11 return 1;
12 case AADDL:
13 case ASUBL:
14 case AJMP:
15 case ARET:
16 case ACALL:
17 return 0;
18 default:
19 if(p->to.type == D_BRANCH)
20 return 0;
21 }
22 p = p->link;
23 }
24 return 0;
25 }
26
27 void
peep(void)28 peep(void)
29 {
30 Reg *r, *r1, *r2;
31 Prog *p, *p1;
32 int t;
33
34 /*
35 * complete R structure
36 */
37 t = 0;
38 for(r=firstr; r!=R; r=r1) {
39 r1 = r->link;
40 if(r1 == R)
41 break;
42 p = r->prog->link;
43 while(p != r1->prog)
44 switch(p->as) {
45 default:
46 r2 = rega();
47 r->link = r2;
48 r2->link = r1;
49
50 r2->prog = p;
51 r2->p1 = r;
52 r->s1 = r2;
53 r2->s1 = r1;
54 r1->p1 = r2;
55
56 r = r2;
57 t++;
58
59 case ADATA:
60 case AGLOBL:
61 case ANAME:
62 case ASIGNAME:
63 p = p->link;
64 }
65 }
66
67 pc = 0; /* speculating it won't kill */
68
69 loop1:
70
71 t = 0;
72 for(r=firstr; r!=R; r=r->link) {
73 p = r->prog;
74 switch(p->as) {
75 case AMOVL:
76 if(regtyp(&p->to))
77 if(regtyp(&p->from)) {
78 if(copyprop(r)) {
79 excise(r);
80 t++;
81 }
82 if(subprop(r) && copyprop(r)) {
83 excise(r);
84 t++;
85 }
86 }
87 break;
88
89 case AMOVBLSX:
90 case AMOVBLZX:
91 case AMOVWLSX:
92 case AMOVWLZX:
93 if(regtyp(&p->to)) {
94 r1 = uniqs(r);
95 if(r1 != R) {
96 p1 = r1->prog;
97 if(p->as == p1->as && p->to.type == p1->from.type)
98 p1->as = AMOVL;
99 }
100 }
101 break;
102 case AADDL:
103 case AADDW:
104 if(p->from.type != D_CONST || needc(p->link))
105 break;
106 if(p->from.offset == -1){
107 if(p->as == AADDL)
108 p->as = ADECL;
109 else
110 p->as = ADECW;
111 p->from = zprog.from;
112 }
113 else if(p->from.offset == 1){
114 if(p->as == AADDL)
115 p->as = AINCL;
116 else
117 p->as = AINCW;
118 p->from = zprog.from;
119 }
120 break;
121 case ASUBL:
122 case ASUBW:
123 if(p->from.type != D_CONST || needc(p->link))
124 break;
125 if(p->from.offset == -1) {
126 if(p->as == ASUBL)
127 p->as = AINCL;
128 else
129 p->as = AINCW;
130 p->from = zprog.from;
131 }
132 else if(p->from.offset == 1){
133 if(p->as == ASUBL)
134 p->as = ADECL;
135 else
136 p->as = ADECW;
137 p->from = zprog.from;
138 }
139 break;
140 }
141 }
142 if(t)
143 goto loop1;
144 }
145
146 void
excise(Reg * r)147 excise(Reg *r)
148 {
149 Prog *p;
150
151 p = r->prog;
152 p->as = ANOP;
153 p->from = zprog.from;
154 p->to = zprog.to;
155 }
156
157 Reg*
uniqp(Reg * r)158 uniqp(Reg *r)
159 {
160 Reg *r1;
161
162 r1 = r->p1;
163 if(r1 == R) {
164 r1 = r->p2;
165 if(r1 == R || r1->p2link != R)
166 return R;
167 } else
168 if(r->p2 != R)
169 return R;
170 return r1;
171 }
172
173 Reg*
uniqs(Reg * r)174 uniqs(Reg *r)
175 {
176 Reg *r1;
177
178 r1 = r->s1;
179 if(r1 == R) {
180 r1 = r->s2;
181 if(r1 == R)
182 return R;
183 } else
184 if(r->s2 != R)
185 return R;
186 return r1;
187 }
188
189 int
regtyp(Adr * a)190 regtyp(Adr *a)
191 {
192 int t;
193
194 t = a->type;
195 if(t >= D_AX && t <= D_DI)
196 return 1;
197 return 0;
198 }
199
200 /*
201 * the idea is to substitute
202 * one register for another
203 * from one MOV to another
204 * MOV a, R0
205 * ADD b, R0 / no use of R1
206 * MOV R0, R1
207 * would be converted to
208 * MOV a, R1
209 * ADD b, R1
210 * MOV R1, R0
211 * hopefully, then the former or latter MOV
212 * will be eliminated by copy propagation.
213 */
214 int
subprop(Reg * r0)215 subprop(Reg *r0)
216 {
217 Prog *p;
218 Adr *v1, *v2;
219 Reg *r;
220 int t;
221
222 p = r0->prog;
223 v1 = &p->from;
224 if(!regtyp(v1))
225 return 0;
226 v2 = &p->to;
227 if(!regtyp(v2))
228 return 0;
229 for(r=uniqp(r0); r!=R; r=uniqp(r)) {
230 if(uniqs(r) == R)
231 break;
232 p = r->prog;
233 switch(p->as) {
234 case ACALL:
235 return 0;
236
237 case AIMULL:
238 case AIMULW:
239 if(p->to.type != D_NONE)
240 break;
241
242 case ADIVB:
243 case ADIVL:
244 case ADIVW:
245 case AIDIVB:
246 case AIDIVL:
247 case AIDIVW:
248 case AIMULB:
249 case AMULB:
250 case AMULL:
251 case AMULW:
252
253 case AROLB:
254 case AROLL:
255 case AROLW:
256 case ARORB:
257 case ARORL:
258 case ARORW:
259 case ASALB:
260 case ASALL:
261 case ASALW:
262 case ASARB:
263 case ASARL:
264 case ASARW:
265 case ASHLB:
266 case ASHLL:
267 case ASHLW:
268 case ASHRB:
269 case ASHRL:
270 case ASHRW:
271
272 case AREP:
273 case AREPN:
274
275 case ACWD:
276 case ACDQ:
277
278 case ASTOSB:
279 case ASTOSL:
280 case AMOVSB:
281 case AMOVSL:
282 case AFSTSW:
283 return 0;
284
285 case AMOVL:
286 if(p->to.type == v1->type)
287 goto gotit;
288 break;
289 }
290 if(copyau(&p->from, v2) ||
291 copyau(&p->to, v2))
292 break;
293 if(copysub(&p->from, v1, v2, 0) ||
294 copysub(&p->to, v1, v2, 0))
295 break;
296 }
297 return 0;
298
299 gotit:
300 copysub(&p->to, v1, v2, 1);
301 if(debug['P']) {
302 print("gotit: %D->%D\n%P", v1, v2, r->prog);
303 if(p->from.type == v2->type)
304 print(" excise");
305 print("\n");
306 }
307 for(r=uniqs(r); r!=r0; r=uniqs(r)) {
308 p = r->prog;
309 copysub(&p->from, v1, v2, 1);
310 copysub(&p->to, v1, v2, 1);
311 if(debug['P'])
312 print("%P\n", r->prog);
313 }
314 t = v1->type;
315 v1->type = v2->type;
316 v2->type = t;
317 if(debug['P'])
318 print("%P last\n", r->prog);
319 return 1;
320 }
321
322 /*
323 * The idea is to remove redundant copies.
324 * v1->v2 F=0
325 * (use v2 s/v2/v1/)*
326 * set v1 F=1
327 * use v2 return fail
328 * -----------------
329 * v1->v2 F=0
330 * (use v2 s/v2/v1/)*
331 * set v1 F=1
332 * set v2 return success
333 */
334 int
copyprop(Reg * r0)335 copyprop(Reg *r0)
336 {
337 Prog *p;
338 Adr *v1, *v2;
339 Reg *r;
340
341 p = r0->prog;
342 v1 = &p->from;
343 v2 = &p->to;
344 if(copyas(v1, v2))
345 return 1;
346 for(r=firstr; r!=R; r=r->link)
347 r->active = 0;
348 return copy1(v1, v2, r0->s1, 0);
349 }
350
351 int
copy1(Adr * v1,Adr * v2,Reg * r,int f)352 copy1(Adr *v1, Adr *v2, Reg *r, int f)
353 {
354 int t;
355 Prog *p;
356
357 if(r->active) {
358 if(debug['P'])
359 print("act set; return 1\n");
360 return 1;
361 }
362 r->active = 1;
363 if(debug['P'])
364 print("copy %D->%D f=%d\n", v1, v2, f);
365 for(; r != R; r = r->s1) {
366 p = r->prog;
367 if(debug['P'])
368 print("%P", p);
369 if(!f && uniqp(r) == R) {
370 f = 1;
371 if(debug['P'])
372 print("; merge; f=%d", f);
373 }
374 t = copyu(p, v2, A);
375 switch(t) {
376 case 2: /* rar, cant split */
377 if(debug['P'])
378 print("; %D rar; return 0\n", v2);
379 return 0;
380
381 case 3: /* set */
382 if(debug['P'])
383 print("; %D set; return 1\n", v2);
384 return 1;
385
386 case 1: /* used, substitute */
387 case 4: /* use and set */
388 if(f) {
389 if(!debug['P'])
390 return 0;
391 if(t == 4)
392 print("; %D used+set and f=%d; return 0\n", v2, f);
393 else
394 print("; %D used and f=%d; return 0\n", v2, f);
395 return 0;
396 }
397 if(copyu(p, v2, v1)) {
398 if(debug['P'])
399 print("; sub fail; return 0\n");
400 return 0;
401 }
402 if(debug['P'])
403 print("; sub %D/%D", v2, v1);
404 if(t == 4) {
405 if(debug['P'])
406 print("; %D used+set; return 1\n", v2);
407 return 1;
408 }
409 break;
410 }
411 if(!f) {
412 t = copyu(p, v1, A);
413 if(!f && (t == 2 || t == 3 || t == 4)) {
414 f = 1;
415 if(debug['P'])
416 print("; %D set and !f; f=%d", v1, f);
417 }
418 }
419 if(debug['P'])
420 print("\n");
421 if(r->s2)
422 if(!copy1(v1, v2, r->s2, f))
423 return 0;
424 }
425 return 1;
426 }
427
428 /*
429 * return
430 * 1 if v only used (and substitute),
431 * 2 if read-alter-rewrite
432 * 3 if set
433 * 4 if set and used
434 * 0 otherwise (not touched)
435 */
436 int
copyu(Prog * p,Adr * v,Adr * s)437 copyu(Prog *p, Adr *v, Adr *s)
438 {
439
440 switch(p->as) {
441
442 default:
443 if(debug['P'])
444 print("unknown op %A\n", p->as);
445 return 2;
446
447 case ANEGB:
448 case ANEGW:
449 case ANEGL:
450 case ANOTB:
451 case ANOTW:
452 case ANOTL:
453 if(copyas(&p->to, v))
454 return 2;
455 break;
456
457 case ALEAL: /* lhs addr, rhs store */
458 if(copyas(&p->from, v))
459 return 2;
460
461
462 case ANOP: /* rhs store */
463 case AMOVL:
464 case AMOVBLSX:
465 case AMOVBLZX:
466 case AMOVWLSX:
467 case AMOVWLZX:
468 if(copyas(&p->to, v)) {
469 if(s != A)
470 return copysub(&p->from, v, s, 1);
471 if(copyau(&p->from, v))
472 return 4;
473 return 3;
474 }
475 goto caseread;
476
477 case AROLB:
478 case AROLL:
479 case AROLW:
480 case ARORB:
481 case ARORL:
482 case ARORW:
483 case ASALB:
484 case ASALL:
485 case ASALW:
486 case ASARB:
487 case ASARL:
488 case ASARW:
489 case ASHLB:
490 case ASHLL:
491 case ASHLW:
492 case ASHRB:
493 case ASHRL:
494 case ASHRW:
495 if(copyas(&p->to, v))
496 return 2;
497 if(copyas(&p->from, v))
498 if(p->from.type == D_CX)
499 return 2;
500 goto caseread;
501
502 case AADDB: /* rhs rar */
503 case AADDL:
504 case AADDW:
505 case AANDB:
506 case AANDL:
507 case AANDW:
508 case ADECL:
509 case ADECW:
510 case AINCL:
511 case AINCW:
512 case ASUBB:
513 case ASUBL:
514 case ASUBW:
515 case AORB:
516 case AORL:
517 case AORW:
518 case AXORB:
519 case AXORL:
520 case AXORW:
521 case AMOVB:
522 case AMOVW:
523
524 case AFMOVB:
525 case AFMOVBP:
526 case AFMOVD:
527 case AFMOVDP:
528 case AFMOVF:
529 case AFMOVFP:
530 case AFMOVL:
531 case AFMOVLP:
532 case AFMOVV:
533 case AFMOVVP:
534 case AFMOVW:
535 case AFMOVWP:
536 case AFMOVX:
537 case AFMOVXP:
538 case AFADDDP:
539 case AFADDW:
540 case AFADDL:
541 case AFADDF:
542 case AFADDD:
543 case AFMULDP:
544 case AFMULW:
545 case AFMULL:
546 case AFMULF:
547 case AFMULD:
548 case AFSUBDP:
549 case AFSUBW:
550 case AFSUBL:
551 case AFSUBF:
552 case AFSUBD:
553 case AFSUBRDP:
554 case AFSUBRW:
555 case AFSUBRL:
556 case AFSUBRF:
557 case AFSUBRD:
558 case AFDIVDP:
559 case AFDIVW:
560 case AFDIVL:
561 case AFDIVF:
562 case AFDIVD:
563 case AFDIVRDP:
564 case AFDIVRW:
565 case AFDIVRL:
566 case AFDIVRF:
567 case AFDIVRD:
568 if(copyas(&p->to, v))
569 return 2;
570 goto caseread;
571
572 case ACMPL: /* read only */
573 case ACMPW:
574 case ACMPB:
575
576 case AFCOMB:
577 case AFCOMBP:
578 case AFCOMD:
579 case AFCOMDP:
580 case AFCOMDPP:
581 case AFCOMF:
582 case AFCOMFP:
583 case AFCOML:
584 case AFCOMLP:
585 case AFCOMW:
586 case AFCOMWP:
587 case AFUCOM:
588 case AFUCOMP:
589 case AFUCOMPP:
590 caseread:
591 if(s != A) {
592 if(copysub(&p->from, v, s, 1))
593 return 1;
594 return copysub(&p->to, v, s, 1);
595 }
596 if(copyau(&p->from, v))
597 return 1;
598 if(copyau(&p->to, v))
599 return 1;
600 break;
601
602 case AJGE: /* no reference */
603 case AJNE:
604 case AJLE:
605 case AJEQ:
606 case AJHI:
607 case AJLS:
608 case AJMI:
609 case AJPL:
610 case AJGT:
611 case AJLT:
612 case AJCC:
613 case AJCS:
614
615 case AADJSP:
616 case AFLDZ:
617 case AWAIT:
618 break;
619
620 case AIMULL:
621 case AIMULW:
622 if(p->to.type != D_NONE) {
623 if(copyas(&p->to, v))
624 return 2;
625 goto caseread;
626 }
627
628 case ADIVB:
629 case ADIVL:
630 case ADIVW:
631 case AIDIVB:
632 case AIDIVL:
633 case AIDIVW:
634 case AIMULB:
635 case AMULB:
636 case AMULL:
637 case AMULW:
638
639 case ACWD:
640 case ACDQ:
641 if(v->type == D_AX || v->type == D_DX)
642 return 2;
643 goto caseread;
644
645 case AREP:
646 case AREPN:
647 if(v->type == D_CX)
648 return 2;
649 goto caseread;
650
651 case AMOVSB:
652 case AMOVSL:
653 if(v->type == D_DI || v->type == D_SI)
654 return 2;
655 goto caseread;
656
657 case ASTOSB:
658 case ASTOSL:
659 if(v->type == D_AX || v->type == D_DI)
660 return 2;
661 goto caseread;
662
663 case AFSTSW:
664 if(v->type == D_AX)
665 return 2;
666 goto caseread;
667
668 case AJMP: /* funny */
669 if(s != A) {
670 if(copysub(&p->to, v, s, 1))
671 return 1;
672 return 0;
673 }
674 if(copyau(&p->to, v))
675 return 1;
676 return 0;
677
678 case ARET: /* funny */
679 if(v->type == REGRET)
680 return 2;
681 if(s != A)
682 return 1;
683 return 3;
684
685 case ACALL: /* funny */
686 if(REGARG>=0 && v->type == REGARG)
687 return 2;
688
689 if(s != A) {
690 if(copysub(&p->to, v, s, 1))
691 return 1;
692 return 0;
693 }
694 if(copyau(&p->to, v))
695 return 4;
696 return 3;
697 }
698 return 0;
699 }
700
701 /*
702 * direct reference,
703 * could be set/use depending on
704 * semantics
705 */
706 int
copyas(Adr * a,Adr * v)707 copyas(Adr *a, Adr *v)
708 {
709 if(a->type != v->type)
710 return 0;
711 if(regtyp(v))
712 return 1;
713 if(v->type == D_AUTO || v->type == D_PARAM)
714 if(v->offset == a->offset)
715 return 1;
716 return 0;
717 }
718
719 /*
720 * either direct or indirect
721 */
722 int
copyau(Adr * a,Adr * v)723 copyau(Adr *a, Adr *v)
724 {
725
726 if(copyas(a, v))
727 return 1;
728 if(regtyp(v)) {
729 if(a->type-D_INDIR == v->type)
730 return 1;
731 if(a->index == v->type)
732 return 1;
733 }
734 return 0;
735 }
736
737 /*
738 * substitute s for v in a
739 * return failure to substitute
740 */
741 int
copysub(Adr * a,Adr * v,Adr * s,int f)742 copysub(Adr *a, Adr *v, Adr *s, int f)
743 {
744 int t;
745
746 if(copyas(a, v)) {
747 t = s->type;
748 if(t >= D_AX && t <= D_DI) {
749 if(f)
750 a->type = t;
751 }
752 return 0;
753 }
754 if(regtyp(v)) {
755 t = v->type;
756 if(a->type == t+D_INDIR) {
757 if(s->type == D_BP && a->index != D_NONE)
758 return 1; /* can't use BP-base with index */
759 if(f)
760 a->type = s->type+D_INDIR;
761 // return 0;
762 }
763 if(a->index == t) {
764 if(f)
765 a->index = s->type;
766 return 0;
767 }
768 return 0;
769 }
770 return 0;
771 }
772