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);
247 fprintf (of, "\nin coming definitions :");
248 bitVectDebugOn (ebbs[i]->inDefs, of);
249 fprintf (of, "\nout going definitions :");
250 bitVectDebugOn (ebbs[i]->outDefs, of);
251 fprintf (of, "\ndefines used :");
252 bitVectDebugOn (ebbs[i]->usesDefs, of);
255 if (ebbs[i]->isLastInLoop) {
256 fprintf (of, "\nInductions Set bitvector :");
257 bitVectDebugOn (ebbs[i]->linds, of);
260 fprintf (of, "\ninExprs:");
261 for (cseSet = ebbs[i]->inExprs; cseSet; cseSet=cseSet->next) {
262 cseDef *item=cseSet->item;
263 fprintf (of, " %s(%d)",OP_SYMBOL(item->sym)->name,item->diCode->key);
264 if (item->fromGlobal)
267 fprintf (of, "\noutExprs:");
268 for (cseSet = ebbs[i]->outExprs; cseSet; cseSet=cseSet->next) {
269 cseDef *item=cseSet->item;
270 fprintf (of, " %s(%d)",OP_SYMBOL(item->sym)->name,item->diCode->key);
271 if (item->fromGlobal)
274 fprintf (of, "\nkilledExprs:");
275 for (cseSet = ebbs[i]->killedExprs; cseSet; cseSet=cseSet->next) {
276 cseDef *item=cseSet->item;
277 fprintf (of, " %s(%d)",OP_SYMBOL(item->sym)->name,item->diCode->key);
278 if (item->fromGlobal)
282 fprintf (of, "\n----------------------------------------------------------------\n");
283 printiCChain (ebbs[i]->sch, of);
288 /*-----------------------------------------------------------------*/
289 /* iCode2eBBlock - converts a sequnce till label to a ebb */
290 /*-----------------------------------------------------------------*/
292 iCode2eBBlock (iCode * ic)
295 eBBlock *ebb = neweBBlock (); /* allocate an entry */
297 /* put the first one unconditionally */
300 /* if this is a label then */
302 ebb->entryLabel = ic->label;
305 SNPRINTF (buffer, sizeof(buffer), "_eBBlock%d", eBBNum++);
306 ebb->entryLabel = newSymbol (buffer, 1);
307 ebb->entryLabel->key = labelKey++;
312 ic->op == JUMPTABLE ||
319 /* if this is a function call */
320 if (ic->op == CALL || ic->op == PCALL)
324 FUNC_HASFCALL(currFunc->type) = 1;
327 if ((ic->next && ic->next->op == LABEL) ||
334 /* loop thru till we find one with a label */
335 for (loop = ic->next; loop; loop = loop->next)
338 /* if this is the last one */
341 /* if this is a function call */
342 if (loop->op == CALL || loop->op == PCALL)
346 FUNC_HASFCALL(currFunc->type) = 1;
349 /* if the next one is a label */
350 /* if this is a goto or ifx */
351 if (loop->next->op == LABEL ||
353 loop->op == JUMPTABLE ||
358 /* mark the end of the chain */
364 /*-----------------------------------------------------------------*/
365 /* eBBWithEntryLabel - finds the basic block with the entry label */
366 /*-----------------------------------------------------------------*/
368 eBBWithEntryLabel (ebbIndex * ebbi, symbol * eLabel)
370 eBBlock ** ebbs = ebbi->bbOrder;
371 int count = ebbi->count;
374 for (i = 0; i < count; i++)
376 if (isSymbolEqual (ebbs[i]->entryLabel, eLabel))
384 /*-----------------------------------------------------------------*/
385 /* ifFromIs - will return 1 if the from block matches this */
386 /*-----------------------------------------------------------------*/
387 DEFSETFUNC (ifFromIs)
390 V_ARG (eBBlock *, this);
392 if (ep->from == this)
399 /*-----------------------------------------------------------------*/
400 /* edgesTo - returns a set of edges with to == supplied value */
401 /*-----------------------------------------------------------------*/
403 edgesTo (eBBlock * to)
408 for (loop = setFirstItem (graphEdges); loop; loop = setNextItem (graphEdges))
409 if (loop->to == to && !loop->from->noPath)
410 addSet (&result, loop->from);
416 /*-----------------------------------------------------------------*/
417 /* addiCodeToeBBlock - will add an iCode to the end of a block */
418 /*-----------------------------------------------------------------*/
420 addiCodeToeBBlock (eBBlock * ebp, iCode * ic, iCode * ip)
422 ic->prev = ic->next = NULL;
423 /* if the insert point is given */
426 ic->lineno = ip->lineno;
437 /* if the block has no instructions */
438 if (ebp->ech == NULL)
440 ebp->sch = ebp->ech = ic;
445 /* if the last instruction is a goto */
446 /* we add it just before the goto */
447 if (ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE
448 || ebp->ech->op == RETURN)
450 ic->lineno = ebp->ech->lineno;
451 ic->prev = ebp->ech->prev;
454 if (!ic->prev) /* was the last only on in the block */
461 /* if the last one was a ifx statement we check to see */
462 /* if the condition was defined in the previous instruction */
463 /* if this is true then we put it before the condition else */
464 /* we put it before if, this is to reduce register pressure, */
465 /* we don't have to hold condition too long in a register */
466 if (ebp->ech->op == IFX)
470 /* if ( !ebp->ech->prev ) */
471 /* ipoint = ebp->ech ; */
473 /* if (!IC_RESULT(ebp->ech->prev)) */
474 /* ipoint = ebp->ech ; */
476 /* if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
477 /* ipoint = ebp->ech->prev; */
479 /* ipoint = ebp->ech ; */
481 ic->lineno = ipoint->lineno;
482 ic->prev = ipoint->prev;
492 /* will add it to the very end */
502 /*-----------------------------------------------------------------*/
503 /* remiCodeFromeBBlock - remove an iCode from BBlock */
504 /*-----------------------------------------------------------------*/
506 remiCodeFromeBBlock (eBBlock * ebb, iCode * ic)
508 wassert (ic->seq>=ebb->fSeq && ic->seq<=ebb->lSeq);
510 ic->prev->next = ic->next;
515 ic->next->prev = ic->prev;
520 /*-----------------------------------------------------------------*/
521 /* iCodeBreakDown : breakDown iCode chain to blocks */
522 /*-----------------------------------------------------------------*/
524 iCodeBreakDown (iCode * ic)
526 eBBlock **ebbs = NULL;
530 ebbi = Safe_alloc (sizeof (ebbIndex));
532 ebbi->dfOrder = NULL; /* no depth first order information yet */
534 /* allocate for the first entry */
536 ebbs = Safe_alloc (sizeof (eBBlock *));
537 ebbi->bbOrder = ebbs;
542 /* convert 2 block */
543 eBBlock *ebb = iCode2eBBlock (loop);
544 loop = ebb->ech->next;
546 ebb->ech->next = NULL; /* mark the end of this chain */
549 ebb->bbnum = ebbi->count; /* save this block number */
550 /* put it in the array */
551 ebbs[(ebbi->count)++] = ebb;
553 /* allocate for the next one. Remember to clear the new */
554 /* pointer at the end, that was created by realloc. */
556 ebbs = Safe_realloc (ebbs, (ebbi->count + 1) * sizeof (eBBlock *));
557 ebbi->bbOrder = ebbs;
559 ebbs[ebbi->count] = 0;
561 /* if this one ends in a goto or a conditional */
562 /* branch then check if the block it is going */
563 /* to already exists, if yes then this could */
564 /* be a loop, add a preheader to the block it */
565 /* goes to if it does not already have one */
566 if (ebbs[(ebbi->count) - 1]->ech &&
567 (ebbs[(ebbi->count) - 1]->ech->op == GOTO ||
568 ebbs[(ebbi->count) - 1]->ech->op == IFX))
574 if (ebbs[(ebbi->count) - 1]->ech->op == GOTO)
575 label = IC_LABEL (ebbs[(ebbi->count) - 1]->ech);
576 else if (!(label = IC_TRUE (ebbs[(ebbi->count) - 1]->ech)))
577 label = IC_FALSE (ebbs[(ebbi->count) - 1]->ech);
579 if ((destBlock = eBBWithEntryLabel (ebbi, label)) &&
580 destBlock->preHeader == NULL &&
581 otherPathsPresent (ebbs, destBlock))
584 symbol *preHeaderLabel = newiTempLoopHeaderLabel (1);
588 /* go thru all block replacing the entryLabel with new label */
589 /* till we reach the block , then we insert a new ebblock */
590 for (i = 0; i < (ebbi->count); i++)
592 if (ebbs[i] == destBlock)
594 replaceLabel (ebbs[i], label, preHeaderLabel);
599 /* if we have stopped at the block , allocate for an extra one */
601 ebbs = Safe_realloc (ebbs, (ebbi->count + 1) * sizeof (eBBlock *));
602 ebbi->bbOrder = ebbs;
604 ebbs[ebbi->count] = 0;
606 /* then move the block down one count */
607 pBlock = ebbs[j = i];
608 for (i += 1; i < (ebbi->count); i++)
618 destBlock->preHeader = ebbs[j] = neweBBlock ();
620 ebbs[j]->entryLabel = preHeaderLabel;
621 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto (LABEL, preHeaderLabel);
622 ebbs[j]->sch->lineno = destBlock->sch->lineno;
628 ebbs[ebbi->count] = NULL;
633 /*-----------------------------------------------------------------*/
634 /* replaceSymBySym : - replace operand by operand in blocks */
635 /* replaces only left & right in blocks */
636 /*-----------------------------------------------------------------*/
638 replaceSymBySym (set * sset, operand * src, operand * dest)
643 /* for all blocks in the set do */
644 for (loop = sset; loop; loop = loop->next)
649 /* for all instructions in this block do */
650 for (ic = rBlock->sch; ic; ic = ic->next)
653 /* if we find usage */
654 if (ic->op == IFX && isOperandEqual (src, IC_COND (ic)))
656 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
657 IC_COND (ic) = operandFromOperand (dest);
658 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
662 if (isOperandEqual (IC_RIGHT (ic), src))
664 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
665 IC_RIGHT (ic) = operandFromOperand (dest);
666 IC_RIGHT (ic)->isaddr = 0;
667 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
670 if (isOperandEqual (IC_LEFT (ic), src))
672 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
673 if (POINTER_GET (ic) && IS_ITEMP (dest))
675 IC_LEFT (ic) = operandFromOperand (dest);
676 IC_LEFT (ic)->isaddr = 1;
680 IC_LEFT (ic) = operandFromOperand (dest);
681 IC_LEFT (ic)->isaddr = 0;
683 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
686 /* special case for pointer sets */
687 if (POINTER_SET (ic) &&
688 isOperandEqual (IC_RESULT (ic), src))
690 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
691 IC_RESULT (ic) = operandFromOperand (dest);
692 IC_RESULT (ic)->isaddr = 1;
693 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
699 /*-----------------------------------------------------------------*/
700 /* replaceLabel - replace reference to one label by another */
701 /*-----------------------------------------------------------------*/
703 replaceLabel (eBBlock * ebp, symbol * fromLbl, symbol * toLbl)
710 for (ic = ebp->sch; ic; ic = ic->next)
716 if (isSymbolEqual (IC_LABEL (ic), fromLbl))
717 IC_LABEL (ic) = toLbl;
721 if (IC_TRUE (ic) && isSymbolEqual (IC_TRUE (ic), fromLbl))
722 IC_TRUE (ic) = toLbl;
723 else if (isSymbolEqual (IC_FALSE (ic), fromLbl))
724 IC_FALSE (ic) = toLbl;
734 /*-----------------------------------------------------------------*/
735 /* iCodeFromeBBlock - convert basic block to iCode chain */
736 /*-----------------------------------------------------------------*/
738 iCodeFromeBBlock (eBBlock ** ebbs, int count)
741 iCode *ric = ebbs[0]->sch;
742 iCode *lic = ebbs[0]->ech;
744 for (; i < count; i++)
746 if (ebbs[i]->sch == NULL)
749 if (ebbs[i]->noPath &&
750 (ebbs[i]->entryLabel != entryLabel &&
751 ebbs[i]->entryLabel != returnLabel))
754 bool foundNonlabel = 0;
763 if (ic==ebbs[i]->ech)
768 if (foundNonlabel && ic)
770 werrorfl (ic->filename, ic->lineno, W_CODE_UNREACH);
775 lic->next = ebbs[i]->sch;
776 lic->next->prev = lic;
784 /*-----------------------------------------------------------------*/
785 /* otherPathsPresent - determines if there is a path from _entry */
786 /* to this block in a half constructed set of blocks */
787 /*-----------------------------------------------------------------*/
789 otherPathsPresent (eBBlock ** ebbs, eBBlock * this)
793 /* for all blocks preceding this block */
794 for (i = 0; i < this->bbnum; i++)
798 /* if there is a reference to the entry label of this block */
799 for (ic = ebbs[i]->sch; ic; ic = ic->next)
804 if (IC_LABEL (ic)->key == this->entryLabel->key)
811 if (IC_TRUE (ic)->key == this->entryLabel->key)
814 else if (IC_FALSE (ic)->key == this->entryLabel->key)
821 /* comes here means we have not found it yet */
822 /* in this case check if the previous block */
823 /* ends in a goto if it does then we have no */
824 /* path else we have a path */
825 if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
826 ebbs[this->bbnum - 1]->ech->op == GOTO)