1 /*-
2 * Copyright (c) 1980 The Regents of the University of California.
3 * All rights reserved.
4 *
5 * %sccs.include.proprietary.c%
6 */
7
8 #ifndef lint
9 static char sccsid[] = "@(#)bb.c 5.3 (Berkeley) 04/12/91";
10 #endif /* not lint */
11
12 /*
13 * bb.c
14 *
15 * Basic block optimizations.
16 *
17 * University of Utah CS Dept modification history:
18 *
19 * Revision 2.1 84/07/19 12:01:20 donn
20 * Changed comment headers for UofU.
21 *
22 * Revision 1.2 84/04/02 14:22:49 donn
23 * Bug in copy propagation missed places where temporaries are assigned to
24 * by OPSTAREQ or OPPLUSEQ, e.g. exponentiation with an integer constant
25 * power, expanded inline.
26 *
27 */
28
29 #include "defs.h"
30 #include "optim.h"
31
32 /*
33 * This file contains code for determination of basic blocks,
34 * as well as some other optimization supporting routines
35 * [including the main routine 'optimize()'].
36 *
37 * The compiler's general debugging flag ['debugflag'] has been
38 * extended to provide the capability of having multiple flags
39 * which are contained in an array. If the option -d is used,
40 * then the flag debugflag[0] is set. If a sequence of one or more
41 * numbers are given (e.g, -d3,7,12), then the flags debugflag[3],
42 * debugflag[7], and debugflag[12] are set. The maximum number of
43 * flags available is specified in the defines.h file.
44 */
45
46
47 Bblockp firstblock = NULL; /* first block in buffer */
48 Bblockp lastblock = NULL; /* last block in buffer */
49
50 expptr tempalloc();
51
52
optimize()53 optimize ()
54
55 {
56 Bblockp bb;
57 Slotp sl,nextsl;
58
59 if (debugflag[2]) showbuffer ();
60
61 optloops ();
62
63 if (debugflag[3]) showbuffer ();
64
65 formbblock ();
66 optcse ();
67
68 if (debugflag[4]) showbuffer ();
69
70 if (! debugflag[7])
71 copyprop ();
72
73 if (debugflag[9]) showbuffer ();
74
75 for (sl = firstslot; sl; sl = nextsl)
76 {
77 nextsl = sl->next;
78 if (sl->type == SKFRTEMP)
79 {
80 templist = mkchain (sl->expr,templist);
81 sl->expr = NULL;
82 delslot (sl);
83 }
84 else
85 sl->expr = tempalloc (sl->expr);
86 }
87
88 if (! debugflag[10])
89 regalloc ();
90
91 flushopt ();
92 }
93
94
95
96 /*
97 * creates a new basic block record
98 */
99
newblock(sl)100 LOCAL Bblockp newblock (sl)
101 Slotp sl;
102
103 {
104 register Bblockp bb;
105
106 bb = ALLOC( bblock );
107 bb->next = NULL ;
108 if (lastblock)
109 {
110 bb->prev = lastblock;
111 lastblock->next = bb;
112 lastblock = bb;
113 }
114 else
115 {
116 firstblock = lastblock = bb;
117 bb->prev = NULL;
118 }
119
120 bb->first = sl;
121 return (bb);
122 }
123
124
125
126 /*
127 * scans slot buffer, creating basic block records
128 */
129
formbblock()130 formbblock ()
131
132 {
133 Slotp sl;
134 field type;
135 Bblockp newbb;
136
137 newbb = NULL;
138 for (sl = firstslot; sl; sl = sl->next)
139 {
140 type = sl->type;
141 switch (type)
142 {
143 case SKEQ:
144 if (!newbb)
145 newbb = newblock(sl);
146 if (containscall(sl->expr))
147 {
148 newbb->last = sl;
149 newbb = NULL;
150 }
151 break;
152 case SKNULL:
153 case SKASSIGN:
154 case SKFRTEMP:
155 if (!newbb)
156 newbb = newblock(sl);
157 break;
158 case SKPAUSE:
159 case SKSTOP:
160 case SKIFN:
161 case SKGOTO:
162 case SKCMGOTO:
163 case SKARIF:
164 case SKASGOTO:
165 case SKIOIFN:
166 case SKCALL:
167 case SKRETURN:
168 if (!newbb)
169 newbb = newblock(sl);
170 newbb->last = sl;
171 newbb = NULL;
172 break;
173 case SKLABEL:
174 if (newbb)
175 newbb->last = sl->prev;
176 newbb = newblock(sl);
177 break;
178 case SKDOHEAD:
179 case SKENDDO:
180 if (!newbb)
181 newbb = newblock(sl);
182 break;
183 default:
184 badthing("SKtype", "formbblock", type);
185 break;
186 }
187 }
188 if (newbb)
189 newbb->last = lastslot;
190 }
191
192
193
194 /*
195 * frees all basic block records
196 * as well as the id and value node chains hanging off the bb and their
197 * respective cross link chains (IDlist, DUPlist and NODElist structs)
198 */
199
clearbb()200 clearbb ()
201 {
202 Bblockp bb,next;
203
204 for (bb = firstblock; bb; bb = next)
205 {
206 next = bb->next;
207 {
208 idptr idp,next;
209 for(idp = bb->headid; idp; idp = next)
210 {
211 next = idp->next;
212 {
213 nodelptr nodelp, next;
214 for(nodelp = idp->headnodelist; nodelp; nodelp = next)
215 {
216 next = nodelp->next;
217 free( (charptr) nodelp);
218 }
219 }
220 free( (charptr) idp);
221 }
222 }
223 {
224 valuen vp,next;
225 for(vp = bb->headnode; vp; vp = next)
226 {
227 next = vp->next;
228 {
229 idlptr idlp, next;
230 for(idlp = vp->headdeplist; idlp; idlp = next)
231 {
232 next = idlp->next;
233 free( (charptr) idlp);
234 }
235 }
236 {
237 duplptr duplp, next;
238 for(duplp = vp->headduplist; duplp; duplp = next)
239 {
240 next = duplp->next;
241 free( (charptr) duplp);
242 }
243 }
244 free( (charptr) vp);
245 }
246 }
247 free ( (charptr) bb);
248 }
249 firstblock = lastblock = NULL;
250 }
251
252
253 /* structure for maintaining records on copy statements */
254
255 typedef struct Subrec {
256 Addrp lmem;
257 Addrp rmem;
258 int sets;
259 } *Subrecp;
260
261
262 LOCAL chainp sublist; /* list of copy statements */
263 LOCAL int prop1count; /* count of number of temporaries eliminated */
264 LOCAL int prop2count; /* count of number of uses of temporaries replaced */
265
266 expptr rmcommaop();
267 Addrp subfor();
268
269
270
271 /*
272 * eliminates copy statements of the form T1 = T2 from the intermediate
273 * code, where T1 and T2 are temporary variables which are each
274 * set only once; eliminates the copy statement and replaces each
275 * use of T1 by T2 (T1 is therefore totally eliminated).
276 */
277
copyprop()278 LOCAL copyprop ()
279
280 {
281 Slotp sl,nextsl;
282 expptr expr;
283 Tempp lp,rp;
284
285 for (sl = firstslot; sl; sl = sl->next)
286 sl->expr = rmcommaop (sl->expr,sl);
287
288 prop1count = prop2count = 0;
289 findcopies ();
290
291 for (sl = firstslot; sl; sl = nextsl)
292 {
293 nextsl = sl->next;
294 expr = sl->expr;
295
296 if ((sl->type == SKFRTEMP) && subfor (expr))
297 {
298 delslot (sl);
299 expr = ENULL;
300 }
301 else if (expr && expr->tag == TEXPR &&
302 expr->exprblock.opcode == OPASSIGN)
303 {
304 lp = (Tempp) expr->exprblock.leftp;
305 rp = (Tempp) expr->exprblock.rightp;
306 if (lp->tag == TTEMP && rp->tag == TTEMP)
307 if (subfor(lp->memalloc) == rp->memalloc
308 && !subfor (rp->memalloc))
309 {
310 frexpr (expr);
311 expr = sl->expr = ENULL;
312 prop1count++;
313 }
314 }
315
316 propagate (expr);
317 }
318
319 if (debugflag[0])
320 fprintf (diagfile,
321 "%d temporarie%s replaced by copy propagation (%d use%s)\n",
322 prop1count,(prop1count==1 ? "" : "s"),
323 prop2count,(prop2count==1 ? "" : "s") );
324 }
325
326
327
328 /*
329 * finds copy statements and enters information in table
330 */
331
findcopies()332 LOCAL findcopies ()
333
334 {
335 Slotp sl;
336 expptr expr;
337 chainp cp;
338
339 for (sl = firstslot; sl; sl = sl->next)
340 {
341 expr = sl->expr;
342 if (expr) switch (expr->tag)
343 {
344 case TEXPR:
345 ckexpr (expr);
346 break;
347
348 case TLIST:
349 for (cp = expr->listblock.listp; cp; cp = cp->nextp)
350 {
351 expr = (expptr) cp->datap;
352 ckexpr (expr);
353 }
354 break;
355
356 default:
357 break;
358 }
359 }
360 }
361
362
363
364 /*
365 * checks an individual expression
366 */
367
ckexpr(expr)368 ckexpr (expr)
369 expptr expr;
370
371 {
372 Tempp lp,rp;
373 int oc = expr->exprblock.opcode;
374
375 if (oc == OPASSIGN || oc == OPPLUSEQ || oc == OPSTAREQ)
376 {
377 lp = (Tempp) expr->exprblock.leftp;
378 rp = (Tempp) expr->exprblock.rightp;
379 if (lp->tag == TTEMP)
380 if (rp->tag == TTEMP && oc == OPASSIGN)
381 enter (lp->memalloc, rp->memalloc);
382 else
383 enter (lp->memalloc, ENULL);
384 }
385 }
386
387
388
389 /*
390 * Enters the given memalloc values in the table (or update if they
391 * are already there), for the assignment statement m1 = m2.
392 * If m2 is NULL, this indicates that the assignment is not a copy
393 * statement.
394 */
395
enter(m1,m2)396 LOCAL enter (m1,m2)
397 Addrp m1,m2;
398
399 {
400 chainp cp;
401 Subrecp old,new;
402
403 for (cp = sublist; cp; cp = cp->nextp)
404 {
405 old = (Subrecp) cp->datap;
406 if (old->lmem == m1)
407 {
408 old->sets++;
409 return;
410 }
411 }
412
413 new = ALLOC (Subrec);
414 new->lmem = m1;
415 new->rmem = m2;
416 new->sets = 1;
417 sublist = mkchain (new, sublist);
418 }
419
420
421
422 /*
423 * looks for record for the given memalloc value
424 */
425
lookup(mem)426 LOCAL Subrecp lookup (mem)
427 Addrp mem;
428
429 {
430 chainp cp;
431 Subrecp rec;
432
433 for (cp = sublist; cp; cp = cp->nextp)
434 {
435 rec = (Subrecp) cp->datap;
436 if (rec->lmem == mem)
437 return rec;
438 }
439
440 return NULL;
441 }
442
443
444
445 /*
446 * checks to see if there is a substitute for given memalloc value
447 */
448
subfor(mem)449 LOCAL Addrp subfor (mem)
450 Addrp mem;
451
452 {
453 Subrecp rec,rec2;
454 Addrp sub;
455
456 rec = lookup (mem);
457 if (rec && rec->sets == 1)
458 {
459 sub = rec->rmem;
460 rec2 = lookup(sub);
461 if (rec2 && rec2->sets == 1)
462 return sub;
463 }
464
465 return NULL;
466 }
467
468
469
470 /*
471 * actually propagates the information
472 */
473
propagate(expr)474 LOCAL propagate (expr)
475 expptr expr;
476
477 {
478 chainp t;
479 Addrp new;
480
481 if (! expr) return;
482
483 switch (expr->tag)
484 {
485 case TEXPR:
486 propagate (expr->exprblock.leftp);
487 propagate (expr->exprblock.rightp);
488 break;
489
490 case TADDR:
491 propagate (expr->addrblock.vleng);
492 propagate (expr->addrblock.memoffset);
493 break;
494
495 case TLIST:
496 for (t = expr->listblock.listp; t; t = t->nextp)
497 propagate (t->datap);
498 break;
499
500 case TTEMP:
501 new = subfor (expr->tempblock.memalloc);
502 if (new)
503 {
504 expr->tempblock.memalloc = new;
505 prop2count++;
506 }
507 break;
508
509 default:
510 break;
511 }
512 }
513
514
515
516 /*
517 * allocates ADDR blocks for each TEMP in the expression
518 */
519
tempalloc(expr)520 LOCAL expptr tempalloc (expr)
521 expptr expr;
522
523 {
524 chainp t;
525
526 if (! expr)
527 return NULL;
528
529 switch (expr->tag)
530 {
531 case TEXPR:
532 expr->exprblock.leftp = tempalloc (expr->exprblock.leftp);
533 expr->exprblock.rightp = tempalloc (expr->exprblock.rightp);
534 break;
535
536 case TADDR:
537 expr->addrblock.vleng = tempalloc (expr->addrblock.vleng);
538 expr->addrblock.memoffset = tempalloc (expr->addrblock.memoffset);
539 break;
540
541 case TLIST:
542 for (t = expr->listblock.listp; t; t = t->nextp)
543 t->datap = (tagptr) tempalloc (t->datap);
544 break;
545
546 case TTEMP:
547 return (expptr) cpexpr (altmpn (expr));
548 break;
549
550 default:
551 break;
552 }
553 return expr;
554 }
555
556
557 /********************* debugging routines *********************/
558
559
560
Announce(s,q)561 Announce (s,q)
562 char *s;
563 expptr q;
564
565 {
566 fprintf (diagfile,"\nAn expression [%s]----->\n",s);
567 showexpr(q,0);
568 fprintf (diagfile,"\n-------------end of expr--------------\n");
569 }
570
571
572
573 /*
574 * dump the basic block buffer, including expressions, mnemonically
575 */
576
showbuffer()577 showbuffer ()
578
579 {
580 Slotp sl;
581 Bblockp bb;
582 int i;
583
584 fprintf (diagfile,"Basic blocks with first and last slots ----------\n");
585 for (i=1, bb = firstblock; bb; i++, bb = bb->next)
586 fprintf (diagfile,"%2d. %d %d\n",i,bb->first,bb->last);
587 fprintf (diagfile,"\n");
588
589 fprintf (diagfile,"Slots and expressions ----------\n");
590
591 fprintf (diagfile,"tag pointer vtype vclass vstg vleng\n");
592 fprintf (diagfile," ADDR memno memoffset istemp ntempelt varleng\n");
593 fprintf (diagfile," TEMP memalloc istemp ntempelt varleng\n");
594 fprintf (diagfile," EXPR opcode leftp rightp\n");
595 fprintf (diagfile," LIST type listp\n");
596 fprintf (diagfile,"\n");
597
598 for (i=1, sl = firstslot; sl; i++, sl = sl->next)
599 {
600 fprintf (diagfile,"%2d. ",i);
601 showslt (sl);
602 }
603 fprintf (diagfile,"---------- End of showbuffer ----------\n");
604 }
605
606
607
608 /*
609 * dumps a single slot in the code buffer
610 */
611
612 LOCAL charptr Zslot[] = {"NULL",
613 "IFN","GOTO","LABEL","EQ","CALL","CMGOTO","STOP","DOHEAD",
614 "ENDDO","ARIF","RETURN","ASGOTO","PAUSE","ASSIGN","IOIFN","FRTEMP"};
615
616
617
showslt(sl)618 showslt (sl)
619 Slotp sl;
620
621 {
622 fprintf (diagfile,"(%2d) %d %s %d\n",
623 sl->lineno,sl,Zslot[sl->type],sl->label);
624 showexpr (sl->expr,0);
625 fprintf (diagfile,"\n");
626 }
627
628
629
showslottype(type)630 showslottype (type)
631 int type;
632
633 {
634 fprintf (diagfile,"%s\n",Zslot[type]);
635 }
636
637
638
639 /*
640 * displays the given expression at the given indentation, showing
641 * its subexpressions at further indentations
642 */
643
644 LOCAL charptr Ztag[] = {"----",
645 "NAME","CONST","EXPR","ADDR","TEMP","PRIM","LIST","IMPLDO","ERROR"};
646 LOCAL charptr Zstg[] = {"unk",
647 "ARG","AUTO","BSS","INIT","CONST","EXT","INTR","STFUNCT",
648 "COMMON","EQUIV","REG","LENG","NULL","PREG"};
649 LOCAL charptr Zclass[] = {"unk",
650 "PARAM","VAR","ENTRY","MAIN","BLOCK","PROC","NAMELIST"};
651 LOCAL charptr Zop[] = {"----",
652 "PLUS","MINUS","STAR","SLASH","POWER","NEG","OR","AND","EQV",
653 "NEQV","NOT","CONCAT","LT","EQ","GT","LE","NE","GE","CALL",
654 "CCALL","ASSIGN","PLUSEQ","STAREQ","CONV","LSHIFT","MOD",
655 "COMMA","QUEST","COLON","ABS","MIN","MAX","ADDR","INDIRECT",
656 "BITOR","BITAND","BITXOR","BITNOT","RSHIFT","PAREN"};
657 LOCAL charptr Ztype[] = {"unk",
658 "ADDR","SHORT","LONG","REAL","DREAL","COMPLEX","DCOMPLEX",
659 "LOGICAL","CHAR","SUBR","ERROR"};
660
661
showexpr(p,indent)662 showexpr(p,indent)
663 tagptr p;
664 int indent;
665
666 {
667 int i;
668 int type;
669 chainp q;
670
671 #define PRHEAD(q) fprintf(diagfile,"%s %d %s %s %s %d", \
672 Ztag[q->tag], q, Ztype[q->headblock.vtype], \
673 Zclass[q->headblock.vclass], Zstg[q->headblock.vstg], \
674 q->headblock.vleng);
675 #define SHOWEXPR(p) showexpr(p,indent+2)
676
677
678
679 if(p == NULL)
680 return;
681
682 for (i=0; i<indent; i++)
683 putc(' ',diagfile);
684
685 switch(p->tag)
686 {
687 case TCONST:
688 PRHEAD(p);
689
690 type=p->constblock.vtype;
691 if (ISCHAR(p))
692 {
693 fprintf(diagfile," ISCHAR ccp= %d\n",
694 p->constblock.constant.ccp);
695 SHOWEXPR(p->constblock.vleng);
696 }
697 else if( ISINT(type) )
698 fprintf(diagfile," ci= %d\n",p->constblock.constant.ci);
699 else if( ISREAL(type) )
700 fprintf(diagfile,
701 " cd[0]= %e\n",p->constblock.constant.cd[0]);
702 else fprintf(diagfile," cd[0]= %e cd[1]= %e\n",
703 p->constblock.constant.cd[0],
704 p->constblock.constant.cd[1] );
705 break;
706
707 case TADDR:
708 PRHEAD(p);
709 fprintf(diagfile,
710 " memno= %d %d %d %d %d\n",
711 p->addrblock.memno,p->addrblock.memoffset,p->addrblock.istemp,
712 p->addrblock.ntempelt,p->addrblock.varleng);
713 SHOWEXPR(p->addrblock.vleng);
714 SHOWEXPR(p->addrblock.memoffset);
715 break;
716
717 case TTEMP:
718 fprintf(diagfile,"%s %d %s %s %d",
719 Ztag[p->tag], p, Ztype[p->headblock.vtype],
720 Zclass[p->headblock.vclass],
721 p->headblock.vleng);
722 fprintf(diagfile,
723 " memalloc= %d %d %d %d\n",
724 p->tempblock.memalloc,p->tempblock.istemp,
725 p->tempblock.ntempelt,p->tempblock.varleng);
726 SHOWEXPR(p->tempblock.vleng);
727 SHOWEXPR(p->tempblock.memalloc);
728 break;
729
730 case TERROR:
731 fprintf(diagfile,"ERROR %d\n",p);
732 break;
733
734 case TNAME:
735 fprintf(diagfile,"NAME %d\n",p);
736 return;
737
738 case TPRIM:
739 fprintf(diagfile,"PRIM %d --- not implemented\n",p);
740 break;
741
742 case TEXPR:
743 PRHEAD(p);
744 fprintf(diagfile," opcode= %s %d %d\n",
745 Zop[p->exprblock.opcode],p->exprblock.leftp,
746 p->exprblock.rightp);
747 SHOWEXPR(p->exprblock.leftp);
748 if(p->exprblock.rightp)
749 SHOWEXPR(p->exprblock.rightp);
750 break;
751
752 case TLIST:
753 fprintf(diagfile,"LIST %d %s %d\n",p,
754 Ztype[p->listblock.vtype],p->listblock.listp);
755 for(q= p->listblock.listp ; q ; q = q->nextp)
756 SHOWEXPR(q->datap);
757 for (i=0; i<indent; i++)
758 putc (' ',diagfile);
759 fprintf(diagfile,"END LIST %d\n",p);
760 break;
761
762 default:
763 fprintf(diagfile,"showexpr BAD TAG= %d at %d \n",p->tag,p);
764 }
765 }
766
767
768
selective()769 selective()/************************************/
770 {
771 int i;
772 Slotp sl;
773
774 i=0;
775 fprintf (stderr,"SELECTIVE OUTPUT\n");
776 for (sl=firstslot;sl;sl=sl->next)
777 {
778 i++;
779 /*
780 if (i>=176 && i<184)
781 */
782 {
783 fprintf (stderr,"%d. ",i);
784 showslt(sl);
785 }
786 }
787 }
788
789
790
791
containscall(p)792 LOCAL containscall(p)
793 expptr p;
794 {
795 chainp cp;
796
797 if (p == NULL)
798 return NO;
799
800 switch (p->tag)
801 {
802 case TADDR:
803 if (containscall(p->addrblock.vleng)
804 || containscall(p->addrblock.memoffset))
805 return YES;
806 else
807 return NO;
808
809 case TCONST:
810 return NO;
811
812 case TERROR:
813 return NO;
814
815 case TEXPR:
816 if (p->exprblock.opcode == OPCALL ||
817 p->exprblock.opcode == OPCCALL)
818 return YES;
819 if (containscall(p->exprblock.vleng) ||
820 containscall(p->exprblock.leftp) ||
821 containscall(p->exprblock.rightp))
822 return YES;
823 else
824 return NO;
825
826 case TLIST:
827 cp = p->listblock.listp;
828 while (cp)
829 {
830 if (containscall(cp->datap))
831 return YES;
832 cp = cp->nextp;
833 }
834 return NO;
835
836 default:
837 return YES;
838 }
839 }
840