1 // Derived from Inferno utils/6c/peep.c
2 // http://code.google.com/p/inferno-os/source/browse/utils/6c/peep.c
3 //
4 // Copyright © 1994-1999 Lucent Technologies Inc. All rights reserved.
5 // Portions Copyright © 1995-1997 C H Forsyth (forsyth@terzarima.net)
6 // Portions Copyright © 1997-1999 Vita Nuova Limited
7 // Portions Copyright © 2000-2007 Vita Nuova Holdings Limited (www.vitanuova.com)
8 // Portions Copyright © 2004,2006 Bruce Ellis
9 // Portions Copyright © 2005-2007 C H Forsyth (forsyth@terzarima.net)
10 // Revisions Copyright © 2000-2007 Lucent Technologies Inc. and others
11 // Portions Copyright © 2009 The Go Authors. All rights reserved.
12 //
13 // Permission is hereby granted, free of charge, to any person obtaining a copy
14 // of this software and associated documentation files (the "Software"), to deal
15 // in the Software without restriction, including without limitation the rights
16 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
17 // copies of the Software, and to permit persons to whom the Software is
18 // furnished to do so, subject to the following conditions:
19 //
20 // The above copyright notice and this permission notice shall be included in
21 // all copies or substantial portions of the Software.
22 //
23 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
24 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
25 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
26 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
27 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
28 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
29 // THE SOFTWARE.
30
31 #include "gg.h"
32 #include "opt.h"
33
34 #define REGEXT 0
35
36 static void conprop(Reg *r);
37
38 // do we need the carry bit
39 static int
40 needc(Prog *p)
41 {
42 while(p != P) {
43 switch(p->as) {
44 case AADCL:
45 case ASBBL:
46 case ARCRL:
47 return 1;
48 case AADDL:
49 case ASUBL:
50 case AJMP:
51 case ARET:
52 case ACALL:
53 return 0;
54 default:
55 if(p->to.type == D_BRANCH)
56 return 0;
57 }
58 p = p->link;
59 }
60 return 0;
61 }
62
63 static Reg*
64 rnops(Reg *r)
65 {
66 Prog *p;
67 Reg *r1;
68
69 if(r != R)
70 for(;;) {
71 p = r->prog;
72 if(p->as != ANOP || p->from.type != D_NONE || p->to.type != D_NONE)
73 break;
74 r1 = uniqs(r);
75 if(r1 == R)
76 break;
77 r = r1;
78 }
79 return r;
80 }
81
82 void
83 peep(void)
84 {
85 Reg *r, *r1, *r2;
86 Prog *p, *p1;
87 int t;
88
89 /*
90 * complete R structure
91 */
92 t = 0;
93 for(r=firstr; r!=R; r=r1) {
94 r1 = r->link;
95 if(r1 == R)
96 break;
97 p = r->prog->link;
98 while(p != r1->prog)
99 switch(p->as) {
100 default:
101 r2 = rega();
102 r->link = r2;
103 r2->link = r1;
104
105 r2->prog = p;
106 p->reg = r2;
107
108 r2->p1 = r;
109 r->s1 = r2;
110 r2->s1 = r1;
111 r1->p1 = r2;
112
113 r = r2;
114 t++;
115
116 case ADATA:
117 case AGLOBL:
118 case ANAME:
119 case ASIGNAME:
120 p = p->link;
121 }
122 }
123
124 // movb elimination.
125 // movb is simulated by the linker
126 // when a register other than ax, bx, cx, dx
127 // is used, so rewrite to other instructions
128 // when possible. a movb into a register
129 // can smash the entire 32-bit register without
130 // causing any trouble.
131 for(r=firstr; r!=R; r=r->link) {
132 p = r->prog;
133 if(p->as == AMOVB && regtyp(&p->to)) {
134 // movb into register.
135 // from another register or constant can be movl.
136 if(regtyp(&p->from) || p->from.type == D_CONST)
137 p->as = AMOVL;
138 else
139 p->as = AMOVBLZX;
140 }
141 }
142
143 // constant propagation
144 // find MOV $con,R followed by
145 // another MOV $con,R without
146 // setting R in the interim
147 for(r=firstr; r!=R; r=r->link) {
148 p = r->prog;
149 switch(p->as) {
150 case ALEAL:
151 if(regtyp(&p->to))
152 if(p->from.sym != S)
153 conprop(r);
154 break;
155
156 case AMOVB:
157 case AMOVW:
158 case AMOVL:
159 if(regtyp(&p->to))
160 if(p->from.type == D_CONST)
161 conprop(r);
162 break;
163 }
164 }
165
166 loop1:
167 if(debug['P'] && debug['v'])
168 dumpit("loop1", firstr);
169
170 t = 0;
171 for(r=firstr; r!=R; r=r->link) {
172 p = r->prog;
173 switch(p->as) {
174 case AMOVB:
175 case AMOVW:
176 case AMOVL:
177 if(regtyp(&p->to))
178 if(regtyp(&p->from)) {
179 if(copyprop(r)) {
180 excise(r);
181 t++;
182 } else
183 if(subprop(r) && copyprop(r)) {
184 excise(r);
185 t++;
186 }
187 }
188 break;
189
190 case AMOVBLZX:
191 case AMOVWLZX:
192 case AMOVBLSX:
193 case AMOVWLSX:
194 if(regtyp(&p->to)) {
195 r1 = rnops(uniqs(r));
196 if(r1 != R) {
197 p1 = r1->prog;
198 if(p->as == p1->as && p->to.type == p1->from.type){
199 p1->as = AMOVL;
200 t++;
201 }
202 }
203 }
204 break;
205
206 case AADDB:
207 case AADDL:
208 case AADDW:
209 if(p->from.type != D_CONST || needc(p->link))
210 break;
211 if(p->from.offset == -1){
212 if(p->as == AADDL)
213 p->as = ADECL;
214 else
215 p->as = ADECW;
216 p->from = zprog.from;
217 break;
218 }
219 if(p->from.offset == 1){
220 if(p->as == AADDL)
221 p->as = AINCL;
222 else
223 p->as = AINCW;
224 p->from = zprog.from;
225 break;
226 }
227 break;
228
229 case ASUBB:
230 case ASUBL:
231 case ASUBW:
232 if(p->from.type != D_CONST || needc(p->link))
233 break;
234 if(p->from.offset == -1) {
235 if(p->as == ASUBL)
236 p->as = AINCL;
237 else
238 p->as = AINCW;
239 p->from = zprog.from;
240 break;
241 }
242 if(p->from.offset == 1){
243 if(p->as == ASUBL)
244 p->as = ADECL;
245 else
246 p->as = ADECW;
247 p->from = zprog.from;
248 break;
249 }
250 break;
251 }
252 }
253 if(t)
254 goto loop1;
255 }
256
257 void
258 excise(Reg *r)
259 {
260 Prog *p;
261
262 p = r->prog;
263 if(debug['P'] && debug['v'])
264 print("%P ===delete===\n", p);
265
266 p->as = ANOP;
267 p->from = zprog.from;
268 p->to = zprog.to;
269
270 ostats.ndelmov++;
271 }
272
273 Reg*
274 uniqp(Reg *r)
275 {
276 Reg *r1;
277
278 r1 = r->p1;
279 if(r1 == R) {
280 r1 = r->p2;
281 if(r1 == R || r1->p2link != R)
282 return R;
283 } else
284 if(r->p2 != R)
285 return R;
286 return r1;
287 }
288
289 Reg*
290 uniqs(Reg *r)
291 {
292 Reg *r1;
293
294 r1 = r->s1;
295 if(r1 == R) {
296 r1 = r->s2;
297 if(r1 == R)
298 return R;
299 } else
300 if(r->s2 != R)
301 return R;
302 return r1;
303 }
304
305 int
306 regtyp(Adr *a)
307 {
308 int t;
309
310 t = a->type;
311 if(t >= D_AX && t <= D_DI)
312 return 1;
313 return 0;
314 }
315
316 /*
317 * the idea is to substitute
318 * one register for another
319 * from one MOV to another
320 * MOV a, R0
321 * ADD b, R0 / no use of R1
322 * MOV R0, R1
323 * would be converted to
324 * MOV a, R1
325 * ADD b, R1
326 * MOV R1, R0
327 * hopefully, then the former or latter MOV
328 * will be eliminated by copy propagation.
329 */
330 int
331 subprop(Reg *r0)
332 {
333 Prog *p;
334 Adr *v1, *v2;
335 Reg *r;
336 int t;
337
338 p = r0->prog;
339 v1 = &p->from;
340 if(!regtyp(v1))
341 return 0;
342 v2 = &p->to;
343 if(!regtyp(v2))
344 return 0;
345 for(r=uniqp(r0); r!=R; r=uniqp(r)) {
346 if(uniqs(r) == R)
347 break;
348 p = r->prog;
349 switch(p->as) {
350 case ACALL:
351 return 0;
352
353 case AIMULL:
354 case AIMULW:
355 if(p->to.type != D_NONE)
356 break;
357
358 case ADIVB:
359 case ADIVL:
360 case ADIVW:
361 case AIDIVB:
362 case AIDIVL:
363 case AIDIVW:
364 case AIMULB:
365 case AMULB:
366 case AMULL:
367 case AMULW:
368
369 case ARCLB:
370 case ARCLL:
371 case ARCLW:
372 case ARCRB:
373 case ARCRL:
374 case ARCRW:
375 case AROLB:
376 case AROLL:
377 case AROLW:
378 case ARORB:
379 case ARORL:
380 case ARORW:
381 case ASALB:
382 case ASALL:
383 case ASALW:
384 case ASARB:
385 case ASARL:
386 case ASARW:
387 case ASHLB:
388 case ASHLL:
389 case ASHLW:
390 case ASHRB:
391 case ASHRL:
392 case ASHRW:
393
394 case AREP:
395 case AREPN:
396
397 case ACWD:
398 case ACDQ:
399
400 case ASTOSB:
401 case ASTOSL:
402 case AMOVSB:
403 case AMOVSL:
404 return 0;
405
406 case AMOVB:
407 case AMOVW:
408 case AMOVL:
409 if(p->to.type == v1->type)
410 goto gotit;
411 break;
412 }
413 if(copyau(&p->from, v2) ||
414 copyau(&p->to, v2))
415 break;
416 if(copysub(&p->from, v1, v2, 0) ||
417 copysub(&p->to, v1, v2, 0))
418 break;
419 }
420 return 0;
421
422 gotit:
423 copysub(&p->to, v1, v2, 1);
424 if(debug['P']) {
425 print("gotit: %D->%D\n%P", v1, v2, r->prog);
426 if(p->from.type == v2->type)
427 print(" excise");
428 print("\n");
429 }
430 for(r=uniqs(r); r!=r0; r=uniqs(r)) {
431 p = r->prog;
432 copysub(&p->from, v1, v2, 1);
433 copysub(&p->to, v1, v2, 1);
434 if(debug['P'])
435 print("%P\n", r->prog);
436 }
437 t = v1->type;
438 v1->type = v2->type;
439 v2->type = t;
440 if(debug['P'])
441 print("%P last\n", r->prog);
442 return 1;
443 }
444
445 /*
446 * The idea is to remove redundant copies.
447 * v1->v2 F=0
448 * (use v2 s/v2/v1/)*
449 * set v1 F=1
450 * use v2 return fail
451 * -----------------
452 * v1->v2 F=0
453 * (use v2 s/v2/v1/)*
454 * set v1 F=1
455 * set v2 return success
456 */
457 int
458 copyprop(Reg *r0)
459 {
460 Prog *p;
461 Adr *v1, *v2;
462 Reg *r;
463
464 p = r0->prog;
465 v1 = &p->from;
466 v2 = &p->to;
467 if(copyas(v1, v2))
468 return 1;
469 for(r=firstr; r!=R; r=r->link)
470 r->active = 0;
471 return copy1(v1, v2, r0->s1, 0);
472 }
473
474 int
475 copy1(Adr *v1, Adr *v2, Reg *r, int f)
476 {
477 int t;
478 Prog *p;
479
480 if(r->active) {
481 if(debug['P'])
482 print("act set; return 1\n");
483 return 1;
484 }
485 r->active = 1;
486 if(debug['P'])
487 print("copy %D->%D f=%d\n", v1, v2, f);
488 for(; r != R; r = r->s1) {
489 p = r->prog;
490 if(debug['P'])
491 print("%P", p);
492 if(!f && uniqp(r) == R) {
493 f = 1;
494 if(debug['P'])
495 print("; merge; f=%d", f);
496 }
497 t = copyu(p, v2, A);
498 switch(t) {
499 case 2: /* rar, cant split */
500 if(debug['P'])
501 print("; %D rar; return 0\n", v2);
502 return 0;
503
504 case 3: /* set */
505 if(debug['P'])
506 print("; %D set; return 1\n", v2);
507 return 1;
508
509 case 1: /* used, substitute */
510 case 4: /* use and set */
511 if(f) {
512 if(!debug['P'])
513 return 0;
514 if(t == 4)
515 print("; %D used+set and f=%d; return 0\n", v2, f);
516 else
517 print("; %D used and f=%d; return 0\n", v2, f);
518 return 0;
519 }
520 if(copyu(p, v2, v1)) {
521 if(debug['P'])
522 print("; sub fail; return 0\n");
523 return 0;
524 }
525 if(debug['P'])
526 print("; sub %D/%D", v2, v1);
527 if(t == 4) {
528 if(debug['P'])
529 print("; %D used+set; return 1\n", v2);
530 return 1;
531 }
532 break;
533 }
534 if(!f) {
535 t = copyu(p, v1, A);
536 if(!f && (t == 2 || t == 3 || t == 4)) {
537 f = 1;
538 if(debug['P'])
539 print("; %D set and !f; f=%d", v1, f);
540 }
541 }
542 if(debug['P'])
543 print("\n");
544 if(r->s2)
545 if(!copy1(v1, v2, r->s2, f))
546 return 0;
547 }
548 return 1;
549 }
550
551 /*
552 * return
553 * 1 if v only used (and substitute),
554 * 2 if read-alter-rewrite
555 * 3 if set
556 * 4 if set and used
557 * 0 otherwise (not touched)
558 */
559 int
560 copyu(Prog *p, Adr *v, Adr *s)
561 {
562
563 switch(p->as) {
564
565 default:
566 if(debug['P'])
567 print("unknown op %A\n", p->as);
568 /* SBBL; ADCL; FLD1; SAHF */
569 return 2;
570
571
572 case ANEGB:
573 case ANEGW:
574 case ANEGL:
575 case ANOTB:
576 case ANOTW:
577 case ANOTL:
578 if(copyas(&p->to, v))
579 return 2;
580 break;
581
582 case ALEAL: /* lhs addr, rhs store */
583 if(copyas(&p->from, v))
584 return 2;
585
586
587 case ANOP: /* rhs store */
588 case AMOVB:
589 case AMOVW:
590 case AMOVL:
591 case AMOVBLSX:
592 case AMOVBLZX:
593 case AMOVWLSX:
594 case AMOVWLZX:
595 if(copyas(&p->to, v)) {
596 if(s != A)
597 return copysub(&p->from, v, s, 1);
598 if(copyau(&p->from, v))
599 return 4;
600 return 3;
601 }
602 goto caseread;
603
604 case ARCLB:
605 case ARCLL:
606 case ARCLW:
607 case ARCRB:
608 case ARCRL:
609 case ARCRW:
610 case AROLB:
611 case AROLL:
612 case AROLW:
613 case ARORB:
614 case ARORL:
615 case ARORW:
616 case ASALB:
617 case ASALL:
618 case ASALW:
619 case ASARB:
620 case ASARL:
621 case ASARW:
622 case ASHLB:
623 case ASHLL:
624 case ASHLW:
625 case ASHRB:
626 case ASHRL:
627 case ASHRW:
628 if(copyas(&p->to, v))
629 return 2;
630 if(copyas(&p->from, v))
631 if(p->from.type == D_CX)
632 return 2;
633 goto caseread;
634
635 case AADDB: /* rhs rar */
636 case AADDL:
637 case AADDW:
638 case AANDB:
639 case AANDL:
640 case AANDW:
641 case ADECL:
642 case ADECW:
643 case AINCL:
644 case AINCW:
645 case ASUBB:
646 case ASUBL:
647 case ASUBW:
648 case AORB:
649 case AORL:
650 case AORW:
651 case AXORB:
652 case AXORL:
653 case AXORW:
654 if(copyas(&p->to, v))
655 return 2;
656 goto caseread;
657
658 case ACMPL: /* read only */
659 case ACMPW:
660 case ACMPB:
661 caseread:
662 if(s != A) {
663 if(copysub(&p->from, v, s, 1))
664 return 1;
665 return copysub(&p->to, v, s, 1);
666 }
667 if(copyau(&p->from, v))
668 return 1;
669 if(copyau(&p->to, v))
670 return 1;
671 break;
672
673 case AJGE: /* no reference */
674 case AJNE:
675 case AJLE:
676 case AJEQ:
677 case AJHI:
678 case AJLS:
679 case AJMI:
680 case AJPL:
681 case AJGT:
682 case AJLT:
683 case AJCC:
684 case AJCS:
685
686 case AADJSP:
687 case AWAIT:
688 case ACLD:
689 break;
690
691 case AIMULL:
692 case AIMULW:
693 if(p->to.type != D_NONE) {
694 if(copyas(&p->to, v))
695 return 2;
696 goto caseread;
697 }
698
699 case ADIVB:
700 case ADIVL:
701 case ADIVW:
702 case AIDIVB:
703 case AIDIVL:
704 case AIDIVW:
705 case AIMULB:
706 case AMULB:
707 case AMULL:
708 case AMULW:
709
710 case ACWD:
711 case ACDQ:
712 if(v->type == D_AX || v->type == D_DX)
713 return 2;
714 goto caseread;
715
716 case AREP:
717 case AREPN:
718 if(v->type == D_CX)
719 return 2;
720 goto caseread;
721
722 case AMOVSB:
723 case AMOVSL:
724 if(v->type == D_DI || v->type == D_SI)
725 return 2;
726 goto caseread;
727
728 case ASTOSB:
729 case ASTOSL:
730 if(v->type == D_AX || v->type == D_DI)
731 return 2;
732 goto caseread;
733
734 case AJMP: /* funny */
735 if(s != A) {
736 if(copysub(&p->to, v, s, 1))
737 return 1;
738 return 0;
739 }
740 if(copyau(&p->to, v))
741 return 1;
742 return 0;
743
744 case ARET: /* funny */
745 if(v->type == REGRET || v->type == FREGRET)
746 return 2;
747 if(s != A)
748 return 1;
749 return 3;
750
751 case ACALL: /* funny */
752 if(REGEXT && v->type <= REGEXT && v->type > exregoffset)
753 return 2;
754 if(REGARG >= 0 && v->type == (uchar)REGARG)
755 return 2;
756
757 if(s != A) {
758 if(copysub(&p->to, v, s, 1))
759 return 1;
760 return 0;
761 }
762 if(copyau(&p->to, v))
763 return 4;
764 return 3;
765
766 case ATEXT: /* funny */
767 if(REGARG >= 0 && v->type == (uchar)REGARG)
768 return 3;
769 return 0;
770 }
771 return 0;
772 }
773
774 /*
775 * direct reference,
776 * could be set/use depending on
777 * semantics
778 */
779 int
780 copyas(Adr *a, Adr *v)
781 {
782 if(a->type != v->type)
783 return 0;
784 if(regtyp(v))
785 return 1;
786 if(v->type == D_AUTO || v->type == D_PARAM)
787 if(v->offset == a->offset)
788 return 1;
789 return 0;
790 }
791
792 /*
793 * either direct or indirect
794 */
795 int
796 copyau(Adr *a, Adr *v)
797 {
798
799 if(copyas(a, v))
800 return 1;
801 if(regtyp(v)) {
802 if(a->type-D_INDIR == v->type)
803 return 1;
804 if(a->index == v->type)
805 return 1;
806 }
807 return 0;
808 }
809
810 /*
811 * substitute s for v in a
812 * return failure to substitute
813 */
814 int
815 copysub(Adr *a, Adr *v, Adr *s, int f)
816 {
817 int t;
818
819 if(copyas(a, v)) {
820 t = s->type;
821 if(t >= D_AX && t <= D_DI) {
822 if(f)
823 a->type = t;
824 }
825 return 0;
826 }
827 if(regtyp(v)) {
828 t = v->type;
829 if(a->type == t+D_INDIR) {
830 if((s->type == D_BP) && a->index != D_NONE)
831 return 1; /* can't use BP-base with index */
832 if(f)
833 a->type = s->type+D_INDIR;
834 // return 0;
835 }
836 if(a->index == t) {
837 if(f)
838 a->index = s->type;
839 return 0;
840 }
841 return 0;
842 }
843 return 0;
844 }
845
846 static void
847 conprop(Reg *r0)
848 {
849 Reg *r;
850 Prog *p, *p0;
851 int t;
852 Adr *v0;
853
854 p0 = r0->prog;
855 v0 = &p0->to;
856 r = r0;
857
858 loop:
859 r = uniqs(r);
860 if(r == R || r == r0)
861 return;
862 if(uniqp(r) == R)
863 return;
864
865 p = r->prog;
866 t = copyu(p, v0, A);
867 switch(t) {
868 case 0: // miss
869 case 1: // use
870 goto loop;
871
872 case 2: // rar
873 case 4: // use and set
874 break;
875
876 case 3: // set
877 if(p->as == p0->as)
878 if(p->from.type == p0->from.type)
879 if(p->from.sym == p0->from.sym)
880 if(p->from.offset == p0->from.offset)
881 if(p->from.scale == p0->from.scale)
882 if(p->from.dval == p0->from.dval)
883 if(p->from.index == p0->from.index) {
884 excise(r);
885 t++;
886 goto loop;
887 }
888 break;
889 }
890 }