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