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;
91 static int dumpIndex=0;
92 static char dumpIndexStr[32];
94 while (dumpFilesPtr->id) {
95 if (dumpFilesPtr->id==id)
100 if (!dumpFilesPtr->id) {
101 fprintf (stdout, "internal error: createDumpFile: unknown dump file.\n");
105 sprintf(dumpIndexStr, ".%d", dumpIndex);
108 if (!dumpFilesPtr->filePtr) {
109 // not used before, create it
110 strncpyz (scratchFileName, dstFileName, PATH_MAX);
112 strncatz (scratchFileName, dumpIndexStr, PATH_MAX);
114 strncatz (scratchFileName, dumpFilesPtr->ext, PATH_MAX);
115 if (!(dumpFilesPtr->filePtr = fopen (scratchFileName, "w"))) {
116 werror (E_FILE_OPEN_ERR, scratchFileName);
122 fprintf(dumpFilesPtr->filePtr, "Dump file index: %d\n", dumpIndex);
125 return dumpFilesPtr->filePtr;
128 /*-----------------------------------------------------------------*/
129 /* closeDumpFiles - close possible opened dumpfiles */
130 /*-----------------------------------------------------------------*/
131 void closeDumpFiles() {
132 struct _dumpFiles *dumpFilesPtr;
134 for (dumpFilesPtr=dumpFiles; dumpFilesPtr->id; dumpFilesPtr++) {
135 if (dumpFilesPtr->filePtr) {
136 fclose (dumpFilesPtr->filePtr);
141 /*-----------------------------------------------------------------*/
142 /* dumpLiveRanges - dump liverange information into a file */
143 /*-----------------------------------------------------------------*/
145 dumpLiveRanges (int id, hTab * liveRanges)
152 file=createDumpFile(id);
158 fprintf(file,"------------- Func %s -------------\n",currFunc->name);
159 for (sym = hTabFirstItem (liveRanges, &k); sym;
160 sym = hTabNextItem (liveRanges, &k))
163 fprintf (file, "%s [k%d lr%d:%d so:%d]{ re%d rm%d}",
164 (sym->rname[0] ? sym->rname : sym->name),
166 sym->liveFrom, sym->liveTo,
168 sym->isreqv, sym->remat
172 printTypeChain (sym->type, file);
173 if (sym->usl.spillLoc)
175 fprintf (file, "}{ sir@ %s", sym->usl.spillLoc->rname);
177 fprintf (file, "} clashes with ");
178 bitVectDebugOn(sym->clashes,file);
179 fprintf (file, "\n");
186 /*-----------------------------------------------------------------*/
187 /* dumpEbbsToFileExt - writeall the basic blocks to a file */
188 /*-----------------------------------------------------------------*/
190 dumpEbbsToFileExt (int id, ebbIndex * ebbi)
196 eBBlock ** ebbs = ebbi->dfOrder ? ebbi->dfOrder : ebbi->bbOrder;
197 int count = ebbi->count;
200 of=createDumpFile(id);
205 for (i = 0; i < count; i++)
207 fprintf (of, "\n----------------------------------------------------------------\n");
208 fprintf (of, "Basic Block %s (df:%d bb:%d lvl:%d): loopDepth=%d%s%s%s\n",
209 ebbs[i]->entryLabel->name,
210 ebbs[i]->dfnum, ebbs[i]->bbnum, ebbs[i]->entryLabel->level,
212 ebbs[i]->noPath ? " noPath" : "",
213 ebbs[i]->partOfLoop ? " partOfLoop" : "",
214 ebbs[i]->isLastInLoop ? " isLastInLoop" : "");
216 // a --nolabelopt makes this more readable
217 fprintf (of, "\nsuccessors: ");
218 for (bb=setFirstItem(ebbs[i]->succList);
220 bb=setNextItem(ebbs[i]->succList)) {
221 fprintf (of, "%s ", bb->entryLabel->name);
223 fprintf (of, "\npredecessors: ");
224 for (bb=setFirstItem(ebbs[i]->predList);
226 bb=setNextItem(ebbs[i]->predList)) {
227 fprintf (of, "%s ", bb->entryLabel->name);
231 fprintf (of, "\ndominators: ");
232 for (d=0; d<ebbs[i]->domVect->size; d++) {
233 if (bitVectBitValue(ebbs[i]->domVect, d)) {
234 fprintf (of, "%s ", ebbi->bbOrder[d]->entryLabel->name); //ebbs[d]->entryLabel->name);
240 fprintf (of, "\ndefines bitVector :");
241 bitVectDebugOn (ebbs[i]->defSet, of);
242 fprintf (of, "\nlocal defines bitVector :");
243 bitVectDebugOn (ebbs[i]->ldefs, of);
244 fprintf (of, "\npointers Set bitvector :");
245 bitVectDebugOn (ebbs[i]->ptrsSet, of);
246 if (ebbs[i]->isLastInLoop) {
247 fprintf (of, "\nInductions Set bitvector :");
248 bitVectDebugOn (ebbs[i]->linds, of);
251 fprintf (of, "\ninExprs:");
252 for (cseSet = ebbs[i]->inExprs; cseSet; cseSet=cseSet->next) {
253 cseDef *item=cseSet->item;
254 fprintf (of, " %s(%d)",OP_SYMBOL(item->sym)->name,item->diCode->key);
255 if (item->fromGlobal)
258 fprintf (of, "\noutExprs:");
259 for (cseSet = ebbs[i]->outExprs; cseSet; cseSet=cseSet->next) {
260 cseDef *item=cseSet->item;
261 fprintf (of, " %s(%d)",OP_SYMBOL(item->sym)->name,item->diCode->key);
262 if (item->fromGlobal)
265 fprintf (of, "\nkilledExprs:");
266 for (cseSet = ebbs[i]->killedExprs; cseSet; cseSet=cseSet->next) {
267 cseDef *item=cseSet->item;
268 fprintf (of, " %s(%d)",OP_SYMBOL(item->sym)->name,item->diCode->key);
269 if (item->fromGlobal)
273 fprintf (of, "\n----------------------------------------------------------------\n");
274 printiCChain (ebbs[i]->sch, of);
279 /*-----------------------------------------------------------------*/
280 /* iCode2eBBlock - converts a sequnce till label to a ebb */
281 /*-----------------------------------------------------------------*/
283 iCode2eBBlock (iCode * ic)
286 eBBlock *ebb = neweBBlock (); /* allocate an entry */
288 /* put the first one unconditionally */
291 /* if this is a label then */
293 ebb->entryLabel = ic->label;
296 SNPRINTF (buffer, sizeof(buffer), "_eBBlock%d", eBBNum++);
297 ebb->entryLabel = newSymbol (buffer, 1);
298 ebb->entryLabel->key = labelKey++;
303 ic->op == JUMPTABLE ||
310 /* if this is a function call */
311 if (ic->op == CALL || ic->op == PCALL)
315 FUNC_HASFCALL(currFunc->type) = 1;
318 if ((ic->next && ic->next->op == LABEL) ||
325 /* loop thru till we find one with a label */
326 for (loop = ic->next; loop; loop = loop->next)
329 /* if this is the last one */
332 /* if this is a function call */
333 if (loop->op == CALL || loop->op == PCALL)
337 FUNC_HASFCALL(currFunc->type) = 1;
340 /* if the next one is a label */
341 /* if this is a goto or ifx */
342 if (loop->next->op == LABEL ||
344 loop->op == JUMPTABLE ||
349 /* mark the end of the chain */
355 /*-----------------------------------------------------------------*/
356 /* eBBWithEntryLabel - finds the basic block with the entry label */
357 /*-----------------------------------------------------------------*/
359 eBBWithEntryLabel (ebbIndex * ebbi, symbol * eLabel)
361 eBBlock ** ebbs = ebbi->bbOrder;
362 int count = ebbi->count;
365 for (i = 0; i < count; i++)
367 if (isSymbolEqual (ebbs[i]->entryLabel, eLabel))
375 /*-----------------------------------------------------------------*/
376 /* ifFromIs - will return 1 if the from block matches this */
377 /*-----------------------------------------------------------------*/
378 DEFSETFUNC (ifFromIs)
381 V_ARG (eBBlock *, this);
383 if (ep->from == this)
390 /*-----------------------------------------------------------------*/
391 /* edgesTo - returns a set of edges with to == supplied value */
392 /*-----------------------------------------------------------------*/
394 edgesTo (eBBlock * to)
399 for (loop = setFirstItem (graphEdges); loop; loop = setNextItem (graphEdges))
400 if (loop->to == to && !loop->from->noPath)
401 addSet (&result, loop->from);
407 /*-----------------------------------------------------------------*/
408 /* addiCodeToeBBlock - will add an iCode to the end of a block */
409 /*-----------------------------------------------------------------*/
411 addiCodeToeBBlock (eBBlock * ebp, iCode * ic, iCode * ip)
413 ic->prev = ic->next = NULL;
414 /* if the insert point is given */
417 ic->lineno = ip->lineno;
428 /* if the block has no instructions */
429 if (ebp->ech == NULL)
431 ebp->sch = ebp->ech = ic;
436 /* if the last instruction is a goto */
437 /* we add it just before the goto */
438 if (ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE
439 || ebp->ech->op == RETURN)
441 ic->lineno = ebp->ech->lineno;
442 ic->prev = ebp->ech->prev;
445 if (!ic->prev) /* was the last only on in the block */
452 /* if the last one was a ifx statement we check to see */
453 /* if the condition was defined in the previous instruction */
454 /* if this is true then we put it before the condition else */
455 /* we put it before if, this is to reduce register pressure, */
456 /* we don't have to hold condition too long in a register */
457 if (ebp->ech->op == IFX)
461 /* if ( !ebp->ech->prev ) */
462 /* ipoint = ebp->ech ; */
464 /* if (!IC_RESULT(ebp->ech->prev)) */
465 /* ipoint = ebp->ech ; */
467 /* if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
468 /* ipoint = ebp->ech->prev; */
470 /* ipoint = ebp->ech ; */
472 ic->lineno = ipoint->lineno;
473 ic->prev = ipoint->prev;
483 /* will add it to the very end */
493 /*-----------------------------------------------------------------*/
494 /* remiCodeFromeBBlock - remove an iCode from BBlock */
495 /*-----------------------------------------------------------------*/
497 remiCodeFromeBBlock (eBBlock * ebb, iCode * ic)
499 wassert (ic->seq>=ebb->fSeq && ic->seq<=ebb->lSeq);
501 ic->prev->next = ic->next;
506 ic->next->prev = ic->prev;
511 /*-----------------------------------------------------------------*/
512 /* iCodeBreakDown : breakDown iCode chain to blocks */
513 /*-----------------------------------------------------------------*/
515 iCodeBreakDown (iCode * ic)
517 eBBlock **ebbs = NULL;
521 ebbi = Safe_alloc (sizeof (ebbIndex));
523 ebbi->dfOrder = NULL; /* no depth first order information yet */
525 /* allocate for the first entry */
527 ebbs = Safe_alloc (sizeof (eBBlock *));
528 ebbi->bbOrder = ebbs;
533 /* convert 2 block */
534 eBBlock *ebb = iCode2eBBlock (loop);
535 loop = ebb->ech->next;
537 ebb->ech->next = NULL; /* mark the end of this chain */
540 ebb->bbnum = ebbi->count; /* save this block number */
541 /* put it in the array */
542 ebbs[(ebbi->count)++] = ebb;
544 /* allocate for the next one. Remember to clear the new */
545 /* pointer at the end, that was created by realloc. */
547 ebbs = Safe_realloc (ebbs, (ebbi->count + 1) * sizeof (eBBlock *));
548 ebbi->bbOrder = ebbs;
550 ebbs[ebbi->count] = 0;
552 /* if this one ends in a goto or a conditional */
553 /* branch then check if the block it is going */
554 /* to already exists, if yes then this could */
555 /* be a loop, add a preheader to the block it */
556 /* goes to if it does not already have one */
557 if (ebbs[(ebbi->count) - 1]->ech &&
558 (ebbs[(ebbi->count) - 1]->ech->op == GOTO ||
559 ebbs[(ebbi->count) - 1]->ech->op == IFX))
565 if (ebbs[(ebbi->count) - 1]->ech->op == GOTO)
566 label = IC_LABEL (ebbs[(ebbi->count) - 1]->ech);
567 else if (!(label = IC_TRUE (ebbs[(ebbi->count) - 1]->ech)))
568 label = IC_FALSE (ebbs[(ebbi->count) - 1]->ech);
570 if ((destBlock = eBBWithEntryLabel (ebbi, label)) &&
571 destBlock->preHeader == NULL &&
572 otherPathsPresent (ebbs, destBlock))
575 symbol *preHeaderLabel = newiTempPreheaderLabel ();
579 /* go thru all block replacing the entryLabel with new label */
580 /* till we reach the block , then we insert a new ebblock */
581 for (i = 0; i < (ebbi->count); i++)
583 if (ebbs[i] == destBlock)
585 replaceLabel (ebbs[i], label, preHeaderLabel);
590 /* if we have stopped at the block , allocate for an extra one */
592 ebbs = Safe_realloc (ebbs, (ebbi->count + 1) * sizeof (eBBlock *));
593 ebbi->bbOrder = ebbs;
595 ebbs[ebbi->count] = 0;
597 /* then move the block down one count */
598 pBlock = ebbs[j = i];
599 for (i += 1; i < (ebbi->count); i++)
609 destBlock->preHeader = ebbs[j] = neweBBlock ();
611 ebbs[j]->entryLabel = preHeaderLabel;
612 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto (LABEL, preHeaderLabel);
613 ebbs[j]->sch->lineno = destBlock->sch->lineno;
619 ebbs[ebbi->count] = NULL;
624 /*-----------------------------------------------------------------*/
625 /* replaceSymBySym : - replace operand by operand in blocks */
626 /* replaces only left & right in blocks */
627 /*-----------------------------------------------------------------*/
629 replaceSymBySym (set * sset, operand * src, operand * dest)
634 /* for all blocks in the set do */
635 for (loop = sset; loop; loop = loop->next)
640 /* for all instructions in this block do */
641 for (ic = rBlock->sch; ic; ic = ic->next)
644 /* if we find usage */
645 if (ic->op == IFX && isOperandEqual (src, IC_COND (ic)))
647 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
648 IC_COND (ic) = operandFromOperand (dest);
649 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
653 if (isOperandEqual (IC_RIGHT (ic), src))
655 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
656 IC_RIGHT (ic) = operandFromOperand (dest);
657 IC_RIGHT (ic)->isaddr = 0;
658 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
661 if (isOperandEqual (IC_LEFT (ic), src))
663 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
664 if (POINTER_GET (ic) && IS_ITEMP (dest))
666 IC_LEFT (ic) = operandFromOperand (dest);
667 IC_LEFT (ic)->isaddr = 1;
671 IC_LEFT (ic) = operandFromOperand (dest);
672 IC_LEFT (ic)->isaddr = 0;
674 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
677 /* special case for pointer sets */
678 if (POINTER_SET (ic) &&
679 isOperandEqual (IC_RESULT (ic), src))
681 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
682 IC_RESULT (ic) = operandFromOperand (dest);
683 IC_RESULT (ic)->isaddr = 1;
684 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
690 /*-----------------------------------------------------------------*/
691 /* replaceLabel - replace reference to one label by another */
692 /*-----------------------------------------------------------------*/
694 replaceLabel (eBBlock * ebp, symbol * fromLbl, symbol * toLbl)
701 for (ic = ebp->sch; ic; ic = ic->next)
707 if (isSymbolEqual (IC_LABEL (ic), fromLbl))
708 IC_LABEL (ic) = toLbl;
712 if (IC_TRUE (ic) && isSymbolEqual (IC_TRUE (ic), fromLbl))
713 IC_TRUE (ic) = toLbl;
714 else if (isSymbolEqual (IC_FALSE (ic), fromLbl))
715 IC_FALSE (ic) = toLbl;
725 /*-----------------------------------------------------------------*/
726 /* iCodeFromeBBlock - convert basic block to iCode chain */
727 /*-----------------------------------------------------------------*/
729 iCodeFromeBBlock (eBBlock ** ebbs, int count)
732 iCode *ric = ebbs[0]->sch;
733 iCode *lic = ebbs[0]->ech;
735 for (; i < count; i++)
737 if (ebbs[i]->sch == NULL)
740 if (ebbs[i]->noPath &&
741 (ebbs[i]->entryLabel != entryLabel &&
742 ebbs[i]->entryLabel != returnLabel))
745 bool foundNonlabel = 0;
754 if (ic==ebbs[i]->ech)
759 if (foundNonlabel && ic)
761 werrorfl (ic->filename, ic->lineno, W_CODE_UNREACH);
766 lic->next = ebbs[i]->sch;
767 lic->next->prev = lic;
775 /*-----------------------------------------------------------------*/
776 /* otherPathsPresent - determines if there is a path from _entry */
777 /* to this block in a half constructed set of blocks */
778 /*-----------------------------------------------------------------*/
780 otherPathsPresent (eBBlock ** ebbs, eBBlock * this)
784 /* for all blocks preceding this block */
785 for (i = 0; i < this->bbnum; i++)
789 /* if there is a reference to the entry label of this block */
790 for (ic = ebbs[i]->sch; ic; ic = ic->next)
795 if (IC_LABEL (ic)->key == this->entryLabel->key)
802 if (IC_TRUE (ic)->key == this->entryLabel->key)
805 else if (IC_FALSE (ic)->key == this->entryLabel->key)
812 /* comes here means we have not found it yet */
813 /* in this case check if the previous block */
814 /* ends in a goto if it does then we have no */
815 /* path else we have a path */
816 if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
817 ebbs[this->bbnum - 1]->ech->op == GOTO)