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