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");
185 /*-----------------------------------------------------------------*/
186 /* dumpEbbsToFileExt - writeall the basic blocks to a file */
187 /*-----------------------------------------------------------------*/
189 dumpEbbsToFileExt (int id, eBBlock ** ebbs, int count)
197 of=createDumpFile(id);
202 for (i = 0; i < count; i++)
204 fprintf (of, "\n----------------------------------------------------------------\n");
205 fprintf (of, "Basic Block %s (df:%d bb:%d lvl:%d): loopDepth=%d%s%s%s\n",
206 ebbs[i]->entryLabel->name,
207 ebbs[i]->dfnum, ebbs[i]->bbnum, ebbs[i]->entryLabel->level,
209 ebbs[i]->noPath ? " noPath" : "",
210 ebbs[i]->partOfLoop ? " partOfLoop" : "",
211 ebbs[i]->isLastInLoop ? " isLastInLoop" : "");
213 // a --nolabelopt makes this more readable
214 fprintf (of, "\nsuccessors: ");
215 for (bb=setFirstItem(ebbs[i]->succList);
217 bb=setNextItem(ebbs[i]->succList)) {
218 fprintf (of, "%s ", bb->entryLabel->name);
220 fprintf (of, "\npredecessors: ");
221 for (bb=setFirstItem(ebbs[i]->predList);
223 bb=setNextItem(ebbs[i]->predList)) {
224 fprintf (of, "%s ", bb->entryLabel->name);
228 fprintf (of, "\ndominators: ");
229 for (d=0; d<ebbs[i]->domVect->size; d++) {
230 if (bitVectBitValue(ebbs[i]->domVect, d)) {
231 fprintf (of, "%s ", ebbs[d]->entryLabel->name);
237 fprintf (of, "\ndefines bitVector :");
238 bitVectDebugOn (ebbs[i]->defSet, of);
239 fprintf (of, "\nlocal defines bitVector :");
240 bitVectDebugOn (ebbs[i]->ldefs, of);
241 fprintf (of, "\npointers Set bitvector :");
242 bitVectDebugOn (ebbs[i]->ptrsSet, of);
243 if (ebbs[i]->isLastInLoop) {
244 fprintf (of, "\nInductions Set bitvector :");
245 bitVectDebugOn (ebbs[i]->linds, of);
248 fprintf (of, "\ninExprs:");
249 for (cseSet = ebbs[i]->inExprs; cseSet; cseSet=cseSet->next) {
250 cseDef *item=cseSet->item;
251 fprintf (of, " %s(%d)",OP_SYMBOL(item->sym)->name,item->diCode->key);
252 if (item->fromGlobal)
255 fprintf (of, "\noutExprs:");
256 for (cseSet = ebbs[i]->outExprs; cseSet; cseSet=cseSet->next) {
257 cseDef *item=cseSet->item;
258 fprintf (of, " %s(%d)",OP_SYMBOL(item->sym)->name,item->diCode->key);
259 if (item->fromGlobal)
262 fprintf (of, "\nkilledExprs:");
263 for (cseSet = ebbs[i]->killedExprs; cseSet; cseSet=cseSet->next) {
264 cseDef *item=cseSet->item;
265 fprintf (of, " %s(%d)",OP_SYMBOL(item->sym)->name,item->diCode->key);
266 if (item->fromGlobal)
270 fprintf (of, "\n----------------------------------------------------------------\n");
271 printiCChain (ebbs[i]->sch, of);
276 /*-----------------------------------------------------------------*/
277 /* iCode2eBBlock - converts a sequnce till label to a ebb */
278 /*-----------------------------------------------------------------*/
280 iCode2eBBlock (iCode * ic)
283 eBBlock *ebb = neweBBlock (); /* allocate an entry */
285 /* put the first one unconditionally */
288 /* if this is a label then */
290 ebb->entryLabel = ic->label;
293 SNPRINTF (buffer, sizeof(buffer), "_eBBlock%d", eBBNum++);
294 ebb->entryLabel = newSymbol (buffer, 1);
295 ebb->entryLabel->key = labelKey++;
300 ic->op == JUMPTABLE ||
307 /* if this is a function call */
308 if (ic->op == CALL || ic->op == PCALL)
312 FUNC_HASFCALL(currFunc->type) = 1;
315 if ((ic->next && ic->next->op == LABEL) ||
322 /* loop thru till we find one with a label */
323 for (loop = ic->next; loop; loop = loop->next)
326 /* if this is the last one */
329 /* if this is a function call */
330 if (loop->op == CALL || loop->op == PCALL)
334 FUNC_HASFCALL(currFunc->type) = 1;
337 /* if the next one is a label */
338 /* if this is a goto or ifx */
339 if (loop->next->op == LABEL ||
341 loop->op == JUMPTABLE ||
346 /* mark the end of the chain */
352 /*-----------------------------------------------------------------*/
353 /* eBBWithEntryLabel - finds the basic block with the entry label */
354 /*-----------------------------------------------------------------*/
356 eBBWithEntryLabel (eBBlock ** ebbs, symbol * eLabel, int count)
360 for (i = 0; i < count; i++)
362 if (isSymbolEqual (ebbs[i]->entryLabel, eLabel))
370 /*-----------------------------------------------------------------*/
371 /* ifFromIs - will return 1 if the from block matches this */
372 /*-----------------------------------------------------------------*/
373 DEFSETFUNC (ifFromIs)
376 V_ARG (eBBlock *, this);
378 if (ep->from == this)
385 /*-----------------------------------------------------------------*/
386 /* edgesTo - returns a set of edges with to == supplied value */
387 /*-----------------------------------------------------------------*/
389 edgesTo (eBBlock * to)
394 for (loop = setFirstItem (graphEdges); loop; loop = setNextItem (graphEdges))
395 if (loop->to == to && !loop->from->noPath)
396 addSet (&result, loop->from);
402 /*-----------------------------------------------------------------*/
403 /* addiCodeToeBBlock - will add an iCode to the end of a block */
404 /*-----------------------------------------------------------------*/
406 addiCodeToeBBlock (eBBlock * ebp, iCode * ic, iCode * ip)
408 ic->prev = ic->next = NULL;
409 /* if the insert point is given */
412 ic->lineno = ip->lineno;
423 /* if the block has no instructions */
424 if (ebp->ech == NULL)
426 ebp->sch = ebp->ech = ic;
431 /* if the last instruction is a goto */
432 /* we add it just before the goto */
433 if (ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE
434 || ebp->ech->op == RETURN)
436 ic->lineno = ebp->ech->lineno;
437 ic->prev = ebp->ech->prev;
440 if (!ic->prev) /* was the last only on in the block */
447 /* if the last one was a ifx statement we check to see */
448 /* if the condition was defined in the previous instruction */
449 /* if this is true then we put it before the condition else */
450 /* we put it before if, this is to reduce register pressure, */
451 /* we don't have to hold condition too long in a register */
452 if (ebp->ech->op == IFX)
456 /* if ( !ebp->ech->prev ) */
457 /* ipoint = ebp->ech ; */
459 /* if (!IC_RESULT(ebp->ech->prev)) */
460 /* ipoint = ebp->ech ; */
462 /* if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
463 /* ipoint = ebp->ech->prev; */
465 /* ipoint = ebp->ech ; */
467 ic->lineno = ipoint->lineno;
468 ic->prev = ipoint->prev;
478 /* will add it to the very end */
488 /*-----------------------------------------------------------------*/
489 /* remiCodeFromeBBlock - remove an iCode from BBlock */
490 /*-----------------------------------------------------------------*/
492 remiCodeFromeBBlock (eBBlock * ebb, iCode * ic)
494 wassert (ic->seq>=ebb->fSeq && ic->seq<=ebb->lSeq);
496 ic->prev->next = ic->next;
501 ic->next->prev = ic->prev;
506 /*-----------------------------------------------------------------*/
507 /* iCodeBreakDown : breakDown iCode chain to blocks */
508 /*-----------------------------------------------------------------*/
510 iCodeBreakDown (iCode * ic, int *count)
512 eBBlock **ebbs = NULL;
517 /* allocate for the first entry */
519 ebbs = Safe_alloc (sizeof (eBBlock **));
524 /* convert 2 block */
525 eBBlock *ebb = iCode2eBBlock (loop);
526 loop = ebb->ech->next;
528 ebb->ech->next = NULL; /* mark the end of this chain */
531 ebb->bbnum = *count; /* save this block number */
532 /* put it in the array */
533 ebbs[(*count)++] = ebb;
535 /* allocate for the next one. Remember to clear the new */
536 /* pointer at the end, that was created by realloc. */
538 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
542 /* if this one ends in a goto or a conditional */
543 /* branch then check if the block it is going */
544 /* to already exists, if yes then this could */
545 /* be a loop, add a preheader to the block it */
546 /* goes to if it does not already have one */
547 if (ebbs[(*count) - 1]->ech &&
548 (ebbs[(*count) - 1]->ech->op == GOTO ||
549 ebbs[(*count) - 1]->ech->op == IFX))
555 if (ebbs[(*count) - 1]->ech->op == GOTO)
556 label = IC_LABEL (ebbs[(*count) - 1]->ech);
557 else if (!(label = IC_TRUE (ebbs[(*count) - 1]->ech)))
558 label = IC_FALSE (ebbs[(*count) - 1]->ech);
560 if ((destBlock = eBBWithEntryLabel (ebbs, label, (*count))) &&
561 destBlock->preHeader == NULL &&
562 otherPathsPresent (ebbs, destBlock))
565 symbol *preHeaderLabel = newiTempPreheaderLabel ();
569 /* go thru all block replacing the entryLabel with new label */
570 /* till we reach the block , then we insert a new ebblock */
571 for (i = 0; i < (*count); i++)
573 if (ebbs[i] == destBlock)
575 replaceLabel (ebbs[i], label, preHeaderLabel);
580 /* if we have stopped at the block , allocate for an extra one */
582 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
586 /* then move the block down one count */
587 pBlock = ebbs[j = i];
588 for (i += 1; i < (*count); i++)
598 destBlock->preHeader = ebbs[j] = neweBBlock ();
600 ebbs[j]->entryLabel = preHeaderLabel;
601 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto (LABEL, preHeaderLabel);
602 ebbs[j]->sch->lineno = destBlock->sch->lineno;
613 /*-----------------------------------------------------------------*/
614 /* replaceSymBySym : - replace operand by operand in blocks */
615 /* replaces only left & right in blocks */
616 /*-----------------------------------------------------------------*/
618 replaceSymBySym (set * sset, operand * src, operand * dest)
623 /* for all blocks in the set do */
624 for (loop = sset; loop; loop = loop->next)
629 /* for all instructions in this block do */
630 for (ic = rBlock->sch; ic; ic = ic->next)
633 /* if we find usage */
634 if (ic->op == IFX && isOperandEqual (src, IC_COND (ic)))
636 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
637 IC_COND (ic) = operandFromOperand (dest);
638 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
642 if (isOperandEqual (IC_RIGHT (ic), src))
644 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
645 IC_RIGHT (ic) = operandFromOperand (dest);
646 IC_RIGHT (ic)->isaddr = 0;
647 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
650 if (isOperandEqual (IC_LEFT (ic), src))
652 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
653 if (POINTER_GET (ic) && IS_ITEMP (dest))
655 IC_LEFT (ic) = operandFromOperand (dest);
656 IC_LEFT (ic)->isaddr = 1;
660 IC_LEFT (ic) = operandFromOperand (dest);
661 IC_LEFT (ic)->isaddr = 0;
663 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
666 /* special case for pointer sets */
667 if (POINTER_SET (ic) &&
668 isOperandEqual (IC_RESULT (ic), src))
670 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
671 IC_RESULT (ic) = operandFromOperand (dest);
672 IC_RESULT (ic)->isaddr = 1;
673 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
679 /*-----------------------------------------------------------------*/
680 /* replaceLabel - replace reference to one label by another */
681 /*-----------------------------------------------------------------*/
683 replaceLabel (eBBlock * ebp, symbol * fromLbl, symbol * toLbl)
690 for (ic = ebp->sch; ic; ic = ic->next)
696 if (isSymbolEqual (IC_LABEL (ic), fromLbl))
697 IC_LABEL (ic) = toLbl;
701 if (IC_TRUE (ic) && isSymbolEqual (IC_TRUE (ic), fromLbl))
702 IC_TRUE (ic) = toLbl;
703 else if (isSymbolEqual (IC_FALSE (ic), fromLbl))
704 IC_FALSE (ic) = toLbl;
714 /*-----------------------------------------------------------------*/
715 /* iCodeFromeBBlock - convert basic block to iCode chain */
716 /*-----------------------------------------------------------------*/
718 iCodeFromeBBlock (eBBlock ** ebbs, int count)
721 iCode *ric = ebbs[0]->sch;
722 iCode *lic = ebbs[0]->ech;
724 for (; i < count; i++)
726 if (ebbs[i]->sch == NULL)
729 if (ebbs[i]->noPath &&
730 (ebbs[i]->entryLabel != entryLabel &&
731 ebbs[i]->entryLabel != returnLabel))
734 bool foundNonlabel = 0;
743 if (ic==ebbs[i]->ech)
748 if (foundNonlabel && ic)
750 werrorfl (ic->filename, ic->lineno, W_CODE_UNREACH);
755 lic->next = ebbs[i]->sch;
756 lic->next->prev = lic;
764 /*-----------------------------------------------------------------*/
765 /* otherPathsPresent - determines if there is a path from _entry */
766 /* to this block in a half constructed set of blocks */
767 /*-----------------------------------------------------------------*/
769 otherPathsPresent (eBBlock ** ebbs, eBBlock * this)
773 /* for all blocks preceding this block */
774 for (i = 0; i < this->bbnum; i++)
778 /* if there is a reference to the entry label of this block */
779 for (ic = ebbs[i]->sch; ic; ic = ic->next)
784 if (IC_LABEL (ic)->key == this->entryLabel->key)
791 if (IC_TRUE (ic)->key == this->entryLabel->key)
794 else if (IC_FALSE (ic)->key == this->entryLabel->key)
801 /* comes here means we have not found it yet */
802 /* in this case check if the previous block */
803 /* ends in a goto if it does then we have no */
804 /* path else we have a path */
805 if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
806 ebbs[this->bbnum - 1]->ech->op == GOTO)