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