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