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