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 */
467 /* loop induction sometimes appends a GOTO instruction, */
468 /* it must be at the very end */
469 if (ebp->ech->op == IFX && ic->op != GOTO)
473 /* if ( !ebp->ech->prev ) */
474 /* ipoint = ebp->ech ; */
476 /* if (!IC_RESULT(ebp->ech->prev)) */
477 /* ipoint = ebp->ech ; */
479 /* if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
480 /* ipoint = ebp->ech->prev; */
482 /* ipoint = ebp->ech ; */
484 ic->lineno = ipoint->lineno;
485 ic->prev = ipoint->prev;
495 /* will add it to the very end */
505 /*-----------------------------------------------------------------*/
506 /* remiCodeFromeBBlock - remove an iCode from BBlock */
507 /*-----------------------------------------------------------------*/
509 remiCodeFromeBBlock (eBBlock * ebb, iCode * ic)
511 wassert (ic->seq>=ebb->fSeq && ic->seq<=ebb->lSeq);
513 ic->prev->next = ic->next;
518 ic->next->prev = ic->prev;
523 /*-----------------------------------------------------------------*/
524 /* iCodeBreakDown : breakDown iCode chain to blocks */
525 /*-----------------------------------------------------------------*/
527 iCodeBreakDown (iCode * ic)
529 eBBlock **ebbs = NULL;
533 ebbi = Safe_alloc (sizeof (ebbIndex));
535 ebbi->dfOrder = NULL; /* no depth first order information yet */
537 /* allocate for the first entry */
539 ebbs = Safe_alloc (sizeof (eBBlock *));
540 ebbi->bbOrder = ebbs;
545 /* convert 2 block */
546 eBBlock *ebb = iCode2eBBlock (loop);
547 loop = ebb->ech->next;
549 ebb->ech->next = NULL; /* mark the end of this chain */
552 ebb->bbnum = ebbi->count; /* save this block number */
553 /* put it in the array */
554 ebbs[(ebbi->count)++] = ebb;
556 /* allocate for the next one. Remember to clear the new */
557 /* pointer at the end, that was created by realloc. */
559 ebbs = Safe_realloc (ebbs, (ebbi->count + 1) * sizeof (eBBlock *));
560 ebbi->bbOrder = ebbs;
562 ebbs[ebbi->count] = 0;
564 /* if this one ends in a goto or a conditional */
565 /* branch then check if the block it is going */
566 /* to already exists, if yes then this could */
567 /* be a loop, add a preheader to the block it */
568 /* goes to if it does not already have one */
569 if (ebbs[(ebbi->count) - 1]->ech &&
570 (ebbs[(ebbi->count) - 1]->ech->op == GOTO ||
571 ebbs[(ebbi->count) - 1]->ech->op == IFX))
577 if (ebbs[(ebbi->count) - 1]->ech->op == GOTO)
578 label = IC_LABEL (ebbs[(ebbi->count) - 1]->ech);
579 else if (!(label = IC_TRUE (ebbs[(ebbi->count) - 1]->ech)))
580 label = IC_FALSE (ebbs[(ebbi->count) - 1]->ech);
582 if ((destBlock = eBBWithEntryLabel (ebbi, label)) &&
583 destBlock->preHeader == NULL &&
584 otherPathsPresent (ebbs, destBlock))
587 symbol *preHeaderLabel = newiTempLoopHeaderLabel (1);
591 /* go thru all block replacing the entryLabel with new label */
592 /* till we reach the block , then we insert a new ebblock */
593 for (i = 0; i < (ebbi->count); i++)
595 if (ebbs[i] == destBlock)
597 replaceLabel (ebbs[i], label, preHeaderLabel);
602 /* if we have stopped at the block , allocate for an extra one */
604 ebbs = Safe_realloc (ebbs, (ebbi->count + 1) * sizeof (eBBlock *));
605 ebbi->bbOrder = ebbs;
607 ebbs[ebbi->count] = 0;
609 /* then move the block down one count */
610 pBlock = ebbs[j = i];
611 for (i += 1; i < (ebbi->count); i++)
621 destBlock->preHeader = ebbs[j] = neweBBlock ();
623 ebbs[j]->entryLabel = preHeaderLabel;
624 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto (LABEL, preHeaderLabel);
625 ebbs[j]->sch->lineno = destBlock->sch->lineno;
631 ebbs[ebbi->count] = NULL;
636 /*-----------------------------------------------------------------*/
637 /* replaceSymBySym : - replace operand by operand in blocks */
638 /* replaces only left & right in blocks */
639 /*-----------------------------------------------------------------*/
641 replaceSymBySym (set * sset, operand * src, operand * dest)
646 /* for all blocks in the set do */
647 for (loop = sset; loop; loop = loop->next)
652 /* for all instructions in this block do */
653 for (ic = rBlock->sch; ic; ic = ic->next)
656 /* if we find usage */
657 if (ic->op == IFX && isOperandEqual (src, IC_COND (ic)))
659 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
660 IC_COND (ic) = operandFromOperand (dest);
661 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
665 if (isOperandEqual (IC_RIGHT (ic), src))
667 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
668 IC_RIGHT (ic) = operandFromOperand (dest);
669 IC_RIGHT (ic)->isaddr = 0;
670 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
673 if (isOperandEqual (IC_LEFT (ic), src))
675 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
676 if (POINTER_GET (ic) && IS_ITEMP (dest))
678 IC_LEFT (ic) = operandFromOperand (dest);
679 IC_LEFT (ic)->isaddr = 1;
683 IC_LEFT (ic) = operandFromOperand (dest);
684 IC_LEFT (ic)->isaddr = 0;
686 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
689 /* special case for pointer sets */
690 if (POINTER_SET (ic) &&
691 isOperandEqual (IC_RESULT (ic), src))
693 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
694 IC_RESULT (ic) = operandFromOperand (dest);
695 IC_RESULT (ic)->isaddr = 1;
696 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
702 /*-----------------------------------------------------------------*/
703 /* replaceLabel - replace reference to one label by another */
704 /*-----------------------------------------------------------------*/
706 replaceLabel (eBBlock * ebp, symbol * fromLbl, symbol * toLbl)
713 for (ic = ebp->sch; ic; ic = ic->next)
719 if (isSymbolEqual (IC_LABEL (ic), fromLbl))
720 IC_LABEL (ic) = toLbl;
724 if (IC_TRUE (ic) && isSymbolEqual (IC_TRUE (ic), fromLbl))
725 IC_TRUE (ic) = toLbl;
726 else if (isSymbolEqual (IC_FALSE (ic), fromLbl))
727 IC_FALSE (ic) = toLbl;
737 /*-----------------------------------------------------------------*/
738 /* iCodeFromeBBlock - convert basic block to iCode chain */
739 /*-----------------------------------------------------------------*/
741 iCodeFromeBBlock (eBBlock ** ebbs, int count)
744 iCode *ric = ebbs[0]->sch;
745 iCode *lic = ebbs[0]->ech;
747 for (; i < count; i++)
749 if (ebbs[i]->sch == NULL)
752 if (ebbs[i]->noPath &&
753 (ebbs[i]->entryLabel != entryLabel &&
754 ebbs[i]->entryLabel != returnLabel))
757 bool foundNonlabel = 0;
766 if (ic==ebbs[i]->ech)
771 if (foundNonlabel && ic)
773 werrorfl (ic->filename, ic->lineno, W_CODE_UNREACH);
778 lic->next = ebbs[i]->sch;
779 lic->next->prev = lic;
787 /*-----------------------------------------------------------------*/
788 /* otherPathsPresent - determines if there is a path from _entry */
789 /* to this block in a half constructed set of blocks */
790 /*-----------------------------------------------------------------*/
792 otherPathsPresent (eBBlock ** ebbs, eBBlock * this)
796 /* for all blocks preceding this block */
797 for (i = 0; i < this->bbnum; i++)
801 /* if there is a reference to the entry label of this block */
802 for (ic = ebbs[i]->sch; ic; ic = ic->next)
807 if (IC_LABEL (ic)->key == this->entryLabel->key)
814 if (IC_TRUE (ic)->key == this->entryLabel->key)
817 else if (IC_FALSE (ic)->key == this->entryLabel->key)
824 /* comes here means we have not found it yet */
825 /* in this case check if the previous block */
826 /* ends in a goto if it does then we have no */
827 /* path else we have a path */
828 if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
829 ebbs[this->bbnum - 1]->ech->op == GOTO)