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->filename = ip->filename;
427 ic->lineno = ip->lineno;
438 /* if the block has no instructions */
439 if (ebp->ech == NULL)
441 ebp->sch = ebp->ech = ic;
446 /* if the last instruction is a goto */
447 /* we add it just before the goto */
448 if (ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE
449 || ebp->ech->op == RETURN)
451 ic->filename = ebp->ech->filename;
452 ic->lineno = ebp->ech->lineno;
453 ic->prev = ebp->ech->prev;
456 if (!ic->prev) /* was the last only on in the block */
463 /* if the last one was a ifx statement we check to see */
464 /* if the condition was defined in the previous instruction */
465 /* if this is true then we put it before the condition else */
466 /* we put it before if, this is to reduce register pressure, */
467 /* we don't have to hold condition too long in a register */
469 /* loop induction sometimes appends a GOTO instruction, */
470 /* it must be at the very end */
471 if (ebp->ech->op == IFX && ic->op != GOTO)
475 /* if ( !ebp->ech->prev ) */
476 /* ipoint = ebp->ech ; */
478 /* if (!IC_RESULT(ebp->ech->prev)) */
479 /* ipoint = ebp->ech ; */
481 /* if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
482 /* ipoint = ebp->ech->prev; */
484 /* ipoint = ebp->ech ; */
486 ic->filename = ipoint->filename;
487 ic->lineno = ipoint->lineno;
488 ic->prev = ipoint->prev;
498 /* will add it to the very end */
508 /*-----------------------------------------------------------------*/
509 /* remiCodeFromeBBlock - remove an iCode from BBlock */
510 /*-----------------------------------------------------------------*/
512 remiCodeFromeBBlock (eBBlock * ebb, iCode * ic)
514 wassert (ic->seq>=ebb->fSeq && ic->seq<=ebb->lSeq);
516 ic->prev->next = ic->next;
521 ic->next->prev = ic->prev;
526 /*-----------------------------------------------------------------*/
527 /* iCodeBreakDown : breakDown iCode chain to blocks */
528 /*-----------------------------------------------------------------*/
530 iCodeBreakDown (iCode * ic)
532 eBBlock **ebbs = NULL;
536 ebbi = Safe_alloc (sizeof (ebbIndex));
538 ebbi->dfOrder = NULL; /* no depth first order information yet */
540 /* allocate for the first entry */
542 ebbs = Safe_alloc (sizeof (eBBlock *));
543 ebbi->bbOrder = ebbs;
548 /* convert 2 block */
549 eBBlock *ebb = iCode2eBBlock (loop);
550 loop = ebb->ech->next;
552 ebb->ech->next = NULL; /* mark the end of this chain */
555 ebb->bbnum = ebbi->count; /* save this block number */
556 /* put it in the array */
557 ebbs[(ebbi->count)++] = ebb;
559 /* allocate for the next one. Remember to clear the new */
560 /* pointer at the end, that was created by realloc. */
562 ebbs = Safe_realloc (ebbs, (ebbi->count + 1) * sizeof (eBBlock *));
563 ebbi->bbOrder = ebbs;
565 ebbs[ebbi->count] = 0;
567 /* if this one ends in a goto or a conditional */
568 /* branch then check if the block it is going */
569 /* to already exists, if yes then this could */
570 /* be a loop, add a preheader to the block it */
571 /* goes to if it does not already have one */
572 if (ebbs[(ebbi->count) - 1]->ech &&
573 (ebbs[(ebbi->count) - 1]->ech->op == GOTO ||
574 ebbs[(ebbi->count) - 1]->ech->op == IFX))
580 if (ebbs[(ebbi->count) - 1]->ech->op == GOTO)
581 label = IC_LABEL (ebbs[(ebbi->count) - 1]->ech);
582 else if (!(label = IC_TRUE (ebbs[(ebbi->count) - 1]->ech)))
583 label = IC_FALSE (ebbs[(ebbi->count) - 1]->ech);
585 if ((destBlock = eBBWithEntryLabel (ebbi, label)) &&
586 destBlock->preHeader == NULL &&
587 otherPathsPresent (ebbs, destBlock))
590 symbol *preHeaderLabel = newiTempLoopHeaderLabel (1);
594 /* go thru all block replacing the entryLabel with new label */
595 /* till we reach the block , then we insert a new ebblock */
596 for (i = 0; i < (ebbi->count); i++)
598 if (ebbs[i] == destBlock)
600 replaceLabel (ebbs[i], label, preHeaderLabel);
605 /* if we have stopped at the block , allocate for an extra one */
607 ebbs = Safe_realloc (ebbs, (ebbi->count + 1) * sizeof (eBBlock *));
608 ebbi->bbOrder = ebbs;
610 ebbs[ebbi->count] = 0;
612 /* then move the block down one count */
613 pBlock = ebbs[j = i];
614 for (i += 1; i < (ebbi->count); i++)
624 destBlock->preHeader = ebbs[j] = neweBBlock ();
626 ebbs[j]->entryLabel = preHeaderLabel;
627 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto (LABEL, preHeaderLabel);
628 ebbs[j]->sch->filename = destBlock->sch->filename;
629 ebbs[j]->sch->lineno = destBlock->sch->lineno;
635 ebbs[ebbi->count] = NULL;
640 /*-----------------------------------------------------------------*/
641 /* replaceSymBySym : - replace operand by operand in blocks */
642 /* replaces only left & right in blocks */
643 /*-----------------------------------------------------------------*/
645 replaceSymBySym (set * sset, operand * src, operand * dest)
650 /* for all blocks in the set do */
651 for (loop = sset; loop; loop = loop->next)
656 /* for all instructions in this block do */
657 for (ic = rBlock->sch; ic; ic = ic->next)
660 /* if we find usage */
661 if (ic->op == IFX && isOperandEqual (src, IC_COND (ic)))
663 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
664 IC_COND (ic) = operandFromOperand (dest);
665 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
669 if (isOperandEqual (IC_RIGHT (ic), src))
671 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
672 IC_RIGHT (ic) = operandFromOperand (dest);
673 IC_RIGHT (ic)->isaddr = 0;
674 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
677 if (isOperandEqual (IC_LEFT (ic), src))
679 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
680 if (POINTER_GET (ic) && IS_ITEMP (dest))
682 IC_LEFT (ic) = operandFromOperand (dest);
683 IC_LEFT (ic)->isaddr = 1;
687 IC_LEFT (ic) = operandFromOperand (dest);
688 IC_LEFT (ic)->isaddr = 0;
690 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
693 /* special case for pointer sets */
694 if (POINTER_SET (ic) &&
695 isOperandEqual (IC_RESULT (ic), src))
697 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
698 IC_RESULT (ic) = operandFromOperand (dest);
699 IC_RESULT (ic)->isaddr = 1;
700 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
706 /*-----------------------------------------------------------------*/
707 /* replaceLabel - replace reference to one label by another */
708 /*-----------------------------------------------------------------*/
710 replaceLabel (eBBlock * ebp, symbol * fromLbl, symbol * toLbl)
717 for (ic = ebp->sch; ic; ic = ic->next)
723 if (isSymbolEqual (IC_LABEL (ic), fromLbl))
724 IC_LABEL (ic) = toLbl;
728 if (IC_TRUE (ic) && isSymbolEqual (IC_TRUE (ic), fromLbl))
729 IC_TRUE (ic) = toLbl;
730 else if (isSymbolEqual (IC_FALSE (ic), fromLbl))
731 IC_FALSE (ic) = toLbl;
741 /*-----------------------------------------------------------------*/
742 /* iCodeFromeBBlock - convert basic block to iCode chain */
743 /*-----------------------------------------------------------------*/
745 iCodeFromeBBlock (eBBlock ** ebbs, int count)
748 iCode *ric = ebbs[0]->sch;
749 iCode *lic = ebbs[0]->ech;
751 for (; i < count; i++)
753 if (ebbs[i]->sch == NULL)
756 if (ebbs[i]->noPath &&
757 (ebbs[i]->entryLabel != entryLabel &&
758 ebbs[i]->entryLabel != returnLabel))
761 bool foundNonlabel = 0;
770 if (ic==ebbs[i]->ech)
775 if (foundNonlabel && ic)
777 werrorfl (ic->filename, ic->lineno, W_CODE_UNREACH);
782 lic->next = ebbs[i]->sch;
783 lic->next->prev = lic;
791 /*-----------------------------------------------------------------*/
792 /* otherPathsPresent - determines if there is a path from _entry */
793 /* to this block in a half constructed set of blocks */
794 /*-----------------------------------------------------------------*/
796 otherPathsPresent (eBBlock ** ebbs, eBBlock * this)
800 /* for all blocks preceding this block */
801 for (i = 0; i < this->bbnum; i++)
805 /* if there is a reference to the entry label of this block */
806 for (ic = ebbs[i]->sch; ic; ic = ic->next)
811 if (IC_LABEL (ic)->key == this->entryLabel->key)
818 if (IC_TRUE (ic)->key == this->entryLabel->key)
821 else if (IC_FALSE (ic)->key == this->entryLabel->key)
828 /* comes here means we have not found it yet */
829 /* in this case check if the previous block */
830 /* ends in a goto if it does then we have no */
831 /* path else we have a path */
832 if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
833 ebbs[this->bbnum - 1]->ech->op == GOTO)