1 /*-------------------------------------------------------------------------
3 SDCCBBlock.c - routines to manipulate basic Blocks
5 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
7 This program is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 2, or (at your option) any
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
21 In other words, you are welcome to use, share and improve this program.
22 You are forbidden to forbid anyone else to use, share and improve
23 what you give them. Help stamp out software-hoarding!
24 -------------------------------------------------------------------------*/
29 set *graphEdges = NULL; /* list of edges in this flow graph */
31 struct _dumpFiles dumpFiles[] = {
32 {DUMP_RAW0, ".dumpraw0", NULL},
33 {DUMP_RAW1, ".dumpraw1", NULL},
34 {DUMP_CSE, ".dumpcse", NULL},
35 {DUMP_DFLOW, ".dumpdflow", NULL},
36 {DUMP_GCSE, ".dumpgcse", NULL},
37 {DUMP_DEADCODE, ".dumpdeadcode", NULL},
38 {DUMP_LOOP, ".dumploop", NULL},
39 {DUMP_LOOPG, ".dumploopg", NULL},
40 {DUMP_LOOPD, ".dumploopd", NULL},
41 {DUMP_RANGE, ".dumprange", NULL},
42 {DUMP_PACK, ".dumppack", NULL},
43 {DUMP_RASSGN, ".dumprassgn", NULL},
44 {DUMP_LRANGE, ".dumplrange", NULL},
48 /*-----------------------------------------------------------------*/
49 /* printEntryLabel - prints entry label of a ebblock */
50 /*-----------------------------------------------------------------*/
51 DEFSETFUNC (printEntryLabel)
55 fprintf (stdout, " %-20s ", bp->entryLabel->name);
59 /*-----------------------------------------------------------------*/
60 /* neweBBlock - allocate & return a new extended basic block */
61 /*-----------------------------------------------------------------*/
67 ebb = Safe_alloc (sizeof (eBBlock));
71 /*-----------------------------------------------------------------*/
72 /* newEdge - allocates & initialises an edge to given values */
73 /*-----------------------------------------------------------------*/
75 newEdge (eBBlock * from, eBBlock * to)
79 ep = Safe_alloc (sizeof (edge));
86 /*-----------------------------------------------------------------*/
87 /* createDumpFile - create the dump file */
88 /*-----------------------------------------------------------------*/
89 FILE *createDumpFile (int id) {
90 struct _dumpFiles *dumpFilesPtr=dumpFiles;
92 while (dumpFilesPtr->id) {
93 if (dumpFilesPtr->id==id)
98 if (!dumpFilesPtr->id) {
99 fprintf (stdout, "internal error: createDumpFile: unknown dump file.\n");
103 if (!dumpFilesPtr->filePtr) {
104 // not used before, create it
105 strncpyz (scratchFileName, dstFileName, PATH_MAX);
106 strncatz (scratchFileName, dumpFilesPtr->ext, PATH_MAX);
107 if (!(dumpFilesPtr->filePtr = fopen (scratchFileName, "w"))) {
108 werror (E_FILE_OPEN_ERR, scratchFileName);
112 return dumpFilesPtr->filePtr;
115 /*-----------------------------------------------------------------*/
116 /* closeDumpFiles - close possible opened dumpfiles */
117 /*-----------------------------------------------------------------*/
118 void closeDumpFiles() {
119 struct _dumpFiles *dumpFilesPtr;
121 for (dumpFilesPtr=dumpFiles; dumpFilesPtr->id; dumpFilesPtr++) {
122 if (dumpFilesPtr->filePtr) {
123 fclose (dumpFilesPtr->filePtr);
128 /*-----------------------------------------------------------------*/
129 /* dumpLiveRanges - dump liverange information into a file */
130 /*-----------------------------------------------------------------*/
132 dumpLiveRanges (int id, hTab * liveRanges)
139 file=createDumpFile(id);
145 fprintf(file,"------------- Func %s -------------\n",currFunc->name);
146 for (sym = hTabFirstItem (liveRanges, &k); sym;
147 sym = hTabNextItem (liveRanges, &k))
150 fprintf (file, "%s [k%d lr%d:%d so:%d]{ re%d rm%d}",
151 (sym->rname[0] ? sym->rname : sym->name),
153 sym->liveFrom, sym->liveTo,
155 sym->isreqv, sym->remat
159 printTypeChain (sym->type, file);
160 if (sym->usl.spillLoc)
162 fprintf (file, "}{ sir@ %s", sym->usl.spillLoc->rname);
164 fprintf (file, "} clashes with ");
165 bitVectDebugOn(sym->clashes,file);
166 fprintf (file, "\n");
172 /*-----------------------------------------------------------------*/
173 /* dumpEbbsToFileExt - writeall the basic blocks to a file */
174 /*-----------------------------------------------------------------*/
176 dumpEbbsToFileExt (int id, eBBlock ** ebbs, int count)
183 of=createDumpFile(id);
188 for (i = 0; i < count; i++)
190 fprintf (of, "\n----------------------------------------------------------------\n");
191 fprintf (of, "Basic Block %s (df:%d bb:%d): loop Depth = %d noPath = %d lastinLoop = %d\n",
192 ebbs[i]->entryLabel->name,
193 ebbs[i]->dfnum, ebbs[i]->bbnum,
196 ebbs[i]->isLastInLoop);
198 // a --nolabelopt makes this more readable
199 fprintf (of, "\nsuccessors: ");
200 for (bb=setFirstItem(ebbs[i]->succList);
202 bb=setNextItem(ebbs[i]->succList)) {
203 fprintf (of, "%s ", bb->entryLabel->name);
205 fprintf (of, "\npredecessors: ");
206 for (bb=setFirstItem(ebbs[i]->predList);
208 bb=setNextItem(ebbs[i]->predList)) {
209 fprintf (of, "%s ", bb->entryLabel->name);
213 fprintf (of, "\ndominators: ");
214 for (d=0; d<ebbs[i]->domVect->size; d++) {
215 if (bitVectBitValue(ebbs[i]->domVect, d)) {
216 fprintf (of, "%s ", ebbs[d]->entryLabel->name);
222 fprintf (of, "\ndefines bitVector :");
223 bitVectDebugOn (ebbs[i]->defSet, of);
224 fprintf (of, "\nlocal defines bitVector :");
225 bitVectDebugOn (ebbs[i]->ldefs, of);
226 fprintf (of, "\npointers Set bitvector :");
227 bitVectDebugOn (ebbs[i]->ptrsSet, of);
228 if (ebbs[i]->isLastInLoop) {
229 fprintf (of, "\nInductions Set bitvector :");
230 bitVectDebugOn (ebbs[i]->linds, of);
232 fprintf (of, "\n----------------------------------------------------------------\n");
233 printiCChain (ebbs[i]->sch, of);
238 /*-----------------------------------------------------------------*/
239 /* iCode2eBBlock - converts a sequnce till label to a ebb */
240 /*-----------------------------------------------------------------*/
242 iCode2eBBlock (iCode * ic)
245 eBBlock *ebb = neweBBlock (); /* allocate an entry */
247 /* put the first one unconditionally */
250 /* if this is a label then */
252 ebb->entryLabel = ic->label;
255 SNPRINTF (buffer, sizeof(buffer), "_eBBlock%d", eBBNum++);
256 ebb->entryLabel = newSymbol (buffer, 1);
257 ebb->entryLabel->key = labelKey++;
262 ic->op == JUMPTABLE ||
269 if ((ic->next && ic->next->op == LABEL) ||
276 /* loop thru till we find one with a label */
277 for (loop = ic->next; loop; loop = loop->next)
280 /* if this is the last one */
283 /* if this is a function call */
284 if (loop->op == CALL || loop->op == PCALL)
288 FUNC_HASFCALL(currFunc->type) = 1;
291 /* if the next one is a label */
292 /* if this is a goto or ifx */
293 if (loop->next->op == LABEL ||
295 loop->op == JUMPTABLE ||
300 /* mark the end of the chain */
306 /*-----------------------------------------------------------------*/
307 /* eBBWithEntryLabel - finds the basic block with the entry label */
308 /*-----------------------------------------------------------------*/
310 eBBWithEntryLabel (eBBlock ** ebbs, symbol * eLabel, int count)
314 for (i = 0; i < count; i++)
316 if (isSymbolEqual (ebbs[i]->entryLabel, eLabel))
324 /*-----------------------------------------------------------------*/
325 /* ifFromIs - will return 1 if the from block matches this */
326 /*-----------------------------------------------------------------*/
327 DEFSETFUNC (ifFromIs)
330 V_ARG (eBBlock *, this);
332 if (ep->from == this)
339 /*-----------------------------------------------------------------*/
340 /* edgesTo - returns a set of edges with to == supplied value */
341 /*-----------------------------------------------------------------*/
343 edgesTo (eBBlock * to)
348 for (loop = setFirstItem (graphEdges); loop; loop = setNextItem (graphEdges))
349 if (loop->to == to && !loop->from->noPath)
350 addSet (&result, loop->from);
356 /*-----------------------------------------------------------------*/
357 /* addiCodeToeBBlock - will add an iCode to the end of a block */
358 /*-----------------------------------------------------------------*/
360 addiCodeToeBBlock (eBBlock * ebp, iCode * ic, iCode * ip)
362 ic->prev = ic->next = NULL;
363 /* if the insert point is given */
366 ic->lineno = ip->lineno;
377 /* if the block has no instructions */
378 if (ebp->ech == NULL)
380 ebp->sch = ebp->ech = ic;
385 /* if the last instruction is a goto */
386 /* we add it just before the goto */
387 if (ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE
388 || ebp->ech->op == RETURN)
390 ic->lineno = ebp->ech->lineno;
391 ic->prev = ebp->ech->prev;
394 if (!ic->prev) /* was the last only on in the block */
401 /* if the last one was a ifx statement we check to see */
402 /* if the condition was defined in the previous instruction */
403 /* if this is true then we put it before the condition else */
404 /* we put it before if, this is to reduce register pressure, */
405 /* we don't have to hold condition too long in a register */
406 if (ebp->ech->op == IFX)
410 /* if ( !ebp->ech->prev ) */
411 /* ipoint = ebp->ech ; */
413 /* if (!IC_RESULT(ebp->ech->prev)) */
414 /* ipoint = ebp->ech ; */
416 /* if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
417 /* ipoint = ebp->ech->prev; */
419 /* ipoint = ebp->ech ; */
421 ic->lineno = ipoint->lineno;
422 ic->prev = ipoint->prev;
432 /* will add it to the very end */
442 /*-----------------------------------------------------------------*/
443 /* remiCodeFromeBBlock - remove an iCode from BBlock */
444 /*-----------------------------------------------------------------*/
446 remiCodeFromeBBlock (eBBlock * ebb, iCode * ic)
448 wassert (ic->seq>=ebb->fSeq && ic->seq<=ebb->lSeq);
450 ic->prev->next = ic->next;
455 ic->next->prev = ic->prev;
460 /*-----------------------------------------------------------------*/
461 /* iCodeBreakDown : breakDown iCode chain to blocks */
462 /*-----------------------------------------------------------------*/
464 iCodeBreakDown (iCode * ic, int *count)
466 eBBlock **ebbs = NULL;
471 /* allocate for the first entry */
473 ebbs = Safe_alloc (sizeof (eBBlock **));
478 /* convert 2 block */
479 eBBlock *ebb = iCode2eBBlock (loop);
480 loop = ebb->ech->next;
482 ebb->ech->next = NULL; /* mark the end of this chain */
485 ebb->bbnum = *count; /* save this block number */
486 /* put it in the array */
487 ebbs[(*count)++] = ebb;
489 /* allocate for the next one. Remember to clear the new */
490 /* pointer at the end, that was created by realloc. */
492 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
496 /* if this one ends in a goto or a conditional */
497 /* branch then check if the block it is going */
498 /* to already exists, if yes then this could */
499 /* be a loop, add a preheader to the block it */
500 /* goes to if it does not already have one */
501 if (ebbs[(*count) - 1]->ech &&
502 (ebbs[(*count) - 1]->ech->op == GOTO ||
503 ebbs[(*count) - 1]->ech->op == IFX))
509 if (ebbs[(*count) - 1]->ech->op == GOTO)
510 label = IC_LABEL (ebbs[(*count) - 1]->ech);
511 else if (!(label = IC_TRUE (ebbs[(*count) - 1]->ech)))
512 label = IC_FALSE (ebbs[(*count) - 1]->ech);
514 if ((destBlock = eBBWithEntryLabel (ebbs, label, (*count))) &&
515 destBlock->preHeader == NULL &&
516 otherPathsPresent (ebbs, destBlock))
519 symbol *preHeaderLabel = newiTempPreheaderLabel ();
523 /* go thru all block replacing the entryLabel with new label */
524 /* till we reach the block , then we insert a new ebblock */
525 for (i = 0; i < (*count); i++)
527 if (ebbs[i] == destBlock)
529 replaceLabel (ebbs[i], label, preHeaderLabel);
534 /* if we have stopped at the block , allocate for an extra one */
536 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
540 /* then move the block down one count */
541 pBlock = ebbs[j = i];
542 for (i += 1; i < (*count); i++)
552 destBlock->preHeader = ebbs[j] = neweBBlock ();
554 ebbs[j]->entryLabel = preHeaderLabel;
555 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto (LABEL, preHeaderLabel);
556 ebbs[j]->sch->lineno = destBlock->sch->lineno;
567 /*-----------------------------------------------------------------*/
568 /* replaceSymBySym : - replace operand by operand in blocks */
569 /* replaces only left & right in blocks */
570 /*-----------------------------------------------------------------*/
572 replaceSymBySym (set * sset, operand * src, operand * dest)
577 /* for all blocks in the set do */
578 for (loop = sset; loop; loop = loop->next)
583 /* for all instructions in this block do */
584 for (ic = rBlock->sch; ic; ic = ic->next)
587 /* if we find usage */
588 if (ic->op == IFX && isOperandEqual (src, IC_COND (ic)))
590 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
591 IC_COND (ic) = operandFromOperand (dest);
592 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
596 if (isOperandEqual (IC_RIGHT (ic), src))
598 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
599 IC_RIGHT (ic) = operandFromOperand (dest);
600 IC_RIGHT (ic)->isaddr = 0;
601 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
604 if (isOperandEqual (IC_LEFT (ic), src))
606 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
607 if (POINTER_GET (ic) && IS_ITEMP (dest))
609 IC_LEFT (ic) = operandFromOperand (dest);
610 IC_LEFT (ic)->isaddr = 1;
614 IC_LEFT (ic) = operandFromOperand (dest);
615 IC_LEFT (ic)->isaddr = 0;
617 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
620 /* special case for pointer sets */
621 if (POINTER_SET (ic) &&
622 isOperandEqual (IC_RESULT (ic), src))
624 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
625 IC_RESULT (ic) = operandFromOperand (dest);
626 IC_RESULT (ic)->isaddr = 1;
627 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
633 /*-----------------------------------------------------------------*/
634 /* replaceLabel - replace reference to one label by another */
635 /*-----------------------------------------------------------------*/
637 replaceLabel (eBBlock * ebp, symbol * fromLbl, symbol * toLbl)
644 for (ic = ebp->sch; ic; ic = ic->next)
650 if (isSymbolEqual (IC_LABEL (ic), fromLbl))
651 IC_LABEL (ic) = toLbl;
655 if (IC_TRUE (ic) && isSymbolEqual (IC_TRUE (ic), fromLbl))
656 IC_TRUE (ic) = toLbl;
657 else if (isSymbolEqual (IC_FALSE (ic), fromLbl))
658 IC_FALSE (ic) = toLbl;
668 /*-----------------------------------------------------------------*/
669 /* iCodeFromeBBlock - convert basic block to iCode chain */
670 /*-----------------------------------------------------------------*/
672 iCodeFromeBBlock (eBBlock ** ebbs, int count)
675 iCode *ric = ebbs[0]->sch;
676 iCode *lic = ebbs[0]->ech;
678 for (; i < count; i++)
680 if (ebbs[i]->sch == NULL)
683 if (ebbs[i]->noPath &&
684 (ebbs[i]->entryLabel != entryLabel &&
685 ebbs[i]->entryLabel != returnLabel))
687 werror (W_CODE_UNREACH, ebbs[i]->sch->filename, ebbs[i]->sch->lineno);
691 lic->next = ebbs[i]->sch;
692 lic->next->prev = lic;
699 /*-----------------------------------------------------------------*/
700 /* otherPathsPresent - determines if there is a path from _entry */
701 /* to this block in a half constructed set of blocks */
702 /*-----------------------------------------------------------------*/
704 otherPathsPresent (eBBlock ** ebbs, eBBlock * this)
708 /* for all blocks preceding this block */
709 for (i = 0; i < this->bbnum; i++)
713 /* if there is a reference to the entry label of this block */
714 for (ic = ebbs[i]->sch; ic; ic = ic->next)
719 if (IC_LABEL (ic)->key == this->entryLabel->key)
726 if (IC_TRUE (ic)->key == this->entryLabel->key)
729 else if (IC_FALSE (ic)->key == this->entryLabel->key)
736 /* comes here means we have not found it yet */
737 /* in this case check if the previous block */
738 /* ends in a goto if it does then we have no */
739 /* path else we have a path */
740 if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
741 ebbs[this->bbnum - 1]->ech->op == GOTO)