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