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 == 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 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 AJAL:
213 return 0;
214
215 case ASGT:
216 case ASGTU:
217
218 case AADD:
219 case AADDU:
220 case ASUB:
221 case ASUBU:
222 case ASLL:
223 case ASRL:
224 case ASRA:
225 case AOR:
226 case AAND:
227 case AXOR:
228 case AMUL:
229 case AMULU:
230 case ADIV:
231 case ADIVU:
232
233 case AADDD:
234 case AADDF:
235 case ASUBD:
236 case ASUBF:
237 case AMULD:
238 case AMULF:
239 case ADIVD:
240 case ADIVF:
241 if(p->to.type == v1->type)
242 if(p->to.reg == v1->reg) {
243 if(p->reg == NREG)
244 p->reg = p->to.reg;
245 goto gotit;
246 }
247 break;
248
249 case AMOVF:
250 case AMOVD:
251 case AMOVW:
252 if(p->to.type == v1->type)
253 if(p->to.reg == v1->reg)
254 goto gotit;
255 break;
256 }
257 if(copyau(&p->from, v2) ||
258 copyau1(p, v2) ||
259 copyau(&p->to, v2))
260 break;
261 if(copysub(&p->from, v1, v2, 0) ||
262 copysub1(p, v1, v2, 0) ||
263 copysub(&p->to, v1, v2, 0))
264 break;
265 }
266 return 0;
267
268 gotit:
269 copysub(&p->to, v1, v2, 1);
270 if(debug['P']) {
271 print("gotit: %D->%D\n%P", v1, v2, r->prog);
272 if(p->from.type == v2->type)
273 print(" excise");
274 print("\n");
275 }
276 for(r=uniqs(r); r!=r0; r=uniqs(r)) {
277 p = r->prog;
278 copysub(&p->from, v1, v2, 1);
279 copysub1(p, v1, v2, 1);
280 copysub(&p->to, v1, v2, 1);
281 if(debug['P'])
282 print("%P\n", r->prog);
283 }
284 t = v1->reg;
285 v1->reg = v2->reg;
286 v2->reg = t;
287 if(debug['P'])
288 print("%P last\n", r->prog);
289 return 1;
290 }
291
292 /*
293 * The idea is to remove redundant copies.
294 * v1->v2 F=0
295 * (use v2 s/v2/v1/)*
296 * set v1 F=1
297 * use v2 return fail
298 * -----------------
299 * v1->v2 F=0
300 * (use v2 s/v2/v1/)*
301 * set v1 F=1
302 * set v2 return success
303 */
304 int
copyprop(Reg * r0)305 copyprop(Reg *r0)
306 {
307 Prog *p;
308 Adr *v1, *v2;
309 Reg *r;
310
311 p = r0->prog;
312 v1 = &p->from;
313 v2 = &p->to;
314 if(copyas(v1, v2))
315 return 1;
316 for(r=firstr; r!=R; r=r->link)
317 r->active = 0;
318 return copy1(v1, v2, r0->s1, 0);
319 }
320
321 int
copy1(Adr * v1,Adr * v2,Reg * r,int f)322 copy1(Adr *v1, Adr *v2, Reg *r, int f)
323 {
324 int t;
325 Prog *p;
326
327 if(r->active) {
328 if(debug['P'])
329 print("act set; return 1\n");
330 return 1;
331 }
332 r->active = 1;
333 if(debug['P'])
334 print("copy %D->%D f=%d\n", v1, v2, f);
335 for(; r != R; r = r->s1) {
336 p = r->prog;
337 if(debug['P'])
338 print("%P", p);
339 if(!f && uniqp(r) == R) {
340 f = 1;
341 if(debug['P'])
342 print("; merge; f=%d", f);
343 }
344 t = copyu(p, v2, A);
345 switch(t) {
346 case 2: /* rar, cant split */
347 if(debug['P'])
348 print("; %Drar; return 0\n", v2);
349 return 0;
350
351 case 3: /* set */
352 if(debug['P'])
353 print("; %Dset; return 1\n", v2);
354 return 1;
355
356 case 1: /* used, substitute */
357 case 4: /* use and set */
358 if(f) {
359 if(!debug['P'])
360 return 0;
361 if(t == 4)
362 print("; %Dused+set and f=%d; return 0\n", v2, f);
363 else
364 print("; %Dused and f=%d; return 0\n", v2, f);
365 return 0;
366 }
367 if(copyu(p, v2, v1)) {
368 if(debug['P'])
369 print("; sub fail; return 0\n");
370 return 0;
371 }
372 if(debug['P'])
373 print("; sub%D/%D", v2, v1);
374 if(t == 4) {
375 if(debug['P'])
376 print("; %Dused+set; return 1\n", v2);
377 return 1;
378 }
379 break;
380 }
381 if(!f) {
382 t = copyu(p, v1, A);
383 if(!f && (t == 2 || t == 3 || t == 4)) {
384 f = 1;
385 if(debug['P'])
386 print("; %Dset and !f; f=%d", v1, f);
387 }
388 }
389 if(debug['P'])
390 print("\n");
391 if(r->s2)
392 if(!copy1(v1, v2, r->s2, f))
393 return 0;
394 }
395 return 1;
396 }
397
398 /*
399 * return
400 * 1 if v only used (and substitute),
401 * 2 if read-alter-rewrite
402 * 3 if set
403 * 4 if set and used
404 * 0 otherwise (not touched)
405 */
copyu(Prog * p,Adr * v,Adr * s)406 copyu(Prog *p, Adr *v, Adr *s)
407 {
408
409 switch(p->as) {
410
411 default:
412 if(debug['P'])
413 print(" (???)");
414 return 2;
415
416
417 case ANOP: /* read, write */
418 case AMOVW:
419 case AMOVF:
420 case AMOVD:
421 case AMOVH:
422 case AMOVHU:
423 case AMOVB:
424 case AMOVBU:
425 case AMOVDW:
426 case AMOVWD:
427 case AMOVFD:
428 case AMOVDF:
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 ASGT: /* read, read, write */
449 case ASGTU:
450
451 case AADD:
452 case AADDU:
453 case ASUB:
454 case ASUBU:
455 case ASLL:
456 case ASRL:
457 case ASRA:
458 case AOR:
459 case ANOR:
460 case AAND:
461 case AXOR:
462 case AMUL:
463 case AMULU:
464 case ADIV:
465 case ADIVU:
466
467 case AADDF:
468 case AADDD:
469 case ASUBF:
470 case ASUBD:
471 case AMULF:
472 case AMULD:
473 case ADIVF:
474 case ADIVD:
475 if(s != A) {
476 if(copysub(&p->from, v, s, 1))
477 return 1;
478 if(copysub1(p, v, s, 1))
479 return 1;
480 if(!copyas(&p->to, v))
481 if(copysub(&p->to, v, s, 1))
482 return 1;
483 return 0;
484 }
485 if(copyas(&p->to, v)) {
486 if(p->reg == NREG)
487 p->reg = p->to.reg;
488 if(copyau(&p->from, v))
489 return 4;
490 if(copyau1(p, v))
491 return 4;
492 return 3;
493 }
494 if(copyau(&p->from, v))
495 return 1;
496 if(copyau1(p, v))
497 return 1;
498 if(copyau(&p->to, v))
499 return 1;
500 return 0;
501
502 case ABEQ: /* read, read */
503 case ABNE:
504 case ABGTZ:
505 case ABGEZ:
506 case ABLTZ:
507 case ABLEZ:
508
509 case ACMPEQD:
510 case ACMPEQF:
511 case ACMPGED:
512 case ACMPGEF:
513 case ACMPGTD:
514 case ACMPGTF:
515 case ABFPF:
516 case ABFPT:
517 if(s != A) {
518 if(copysub(&p->from, v, s, 1))
519 return 1;
520 return copysub1(p, v, s, 1);
521 }
522 if(copyau(&p->from, v))
523 return 1;
524 if(copyau1(p, v))
525 return 1;
526 return 0;
527
528 case AJMP: /* funny */
529 if(s != A) {
530 if(copysub(&p->to, v, s, 1))
531 return 1;
532 return 0;
533 }
534 if(copyau(&p->to, v))
535 return 1;
536 return 0;
537
538 case ARET: /* funny */
539 if(v->type == D_REG)
540 if(v->reg == REGRET)
541 return 2;
542 if(v->type == D_FREG)
543 if(v->reg == FREGRET)
544 return 2;
545
546 case AJAL: /* funny */
547 if(v->type == D_REG) {
548 if(v->reg <= REGEXT && v->reg > exregoffset)
549 return 2;
550 if(REGARG && v->reg == REGARG)
551 return 2;
552 }
553 if(v->type == D_FREG)
554 if(v->reg <= FREGEXT && v->reg > exfregoffset)
555 return 2;
556
557 if(s != A) {
558 if(copysub(&p->to, v, s, 1))
559 return 1;
560 return 0;
561 }
562 if(copyau(&p->to, v))
563 return 4;
564 return 3;
565
566 case ATEXT: /* funny */
567 if(v->type == D_REG)
568 if(v->reg == REGARG)
569 return 3;
570 return 0;
571 }
572 }
573
574 int
a2type(Prog * p)575 a2type(Prog *p)
576 {
577
578 switch(p->as) {
579 case ABEQ:
580 case ABNE:
581 case ABGTZ:
582 case ABGEZ:
583 case ABLTZ:
584 case ABLEZ:
585
586 case ASGT:
587 case ASGTU:
588
589 case AADD:
590 case AADDU:
591 case ASUB:
592 case ASUBU:
593 case ASLL:
594 case ASRL:
595 case ASRA:
596 case AOR:
597 case AAND:
598 case AXOR:
599 case AMUL:
600 case AMULU:
601 case ADIV:
602 case ADIVU:
603 return D_REG;
604
605 case ACMPEQD:
606 case ACMPEQF:
607 case ACMPGED:
608 case ACMPGEF:
609 case ACMPGTD:
610 case ACMPGTF:
611
612 case AADDF:
613 case AADDD:
614 case ASUBF:
615 case ASUBD:
616 case AMULF:
617 case AMULD:
618 case ADIVF:
619 case ADIVD:
620 return D_FREG;
621 }
622 return D_NONE;
623 }
624
625 /*
626 * direct reference,
627 * could be set/use depending on
628 * semantics
629 */
630 int
copyas(Adr * a,Adr * v)631 copyas(Adr *a, Adr *v)
632 {
633
634 if(regtyp(v))
635 if(a->type == v->type)
636 if(a->reg == v->reg)
637 return 1;
638 return 0;
639 }
640
641 /*
642 * either direct or indirect
643 */
644 int
copyau(Adr * a,Adr * v)645 copyau(Adr *a, Adr *v)
646 {
647
648 if(copyas(a, v))
649 return 1;
650 if(v->type == D_REG)
651 if(a->type == D_OREG)
652 if(v->reg == a->reg)
653 return 1;
654 return 0;
655 }
656
657 int
copyau1(Prog * p,Adr * v)658 copyau1(Prog *p, Adr *v)
659 {
660
661 if(regtyp(v))
662 if(p->from.type == v->type || p->to.type == v->type)
663 if(p->reg == v->reg) {
664 if(a2type(p) != v->type)
665 print("botch a2type %P\n", p);
666 return 1;
667 }
668 return 0;
669 }
670
671 /*
672 * substitute s for v in a
673 * return failure to substitute
674 */
675 int
copysub(Adr * a,Adr * v,Adr * s,int f)676 copysub(Adr *a, Adr *v, Adr *s, int f)
677 {
678
679 if(f)
680 if(copyau(a, v))
681 a->reg = s->reg;
682 return 0;
683 }
684
685 int
copysub1(Prog * p1,Adr * v,Adr * s,int f)686 copysub1(Prog *p1, Adr *v, Adr *s, int f)
687 {
688
689 if(f)
690 if(copyau1(p1, v))
691 p1->reg = s->reg;
692 return 0;
693 }
694