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;
92 while (dumpFilesPtr->id) {
93 if (dumpFilesPtr->id==id)
98 if (!dumpFilesPtr->id) {
99 fprintf (stdout, "internal error: createDumpFile: unknown dump file.\n");
103 if (!dumpFilesPtr->filePtr) {
104 // not used before, create it
105 strncpyz (scratchFileName, dstFileName, PATH_MAX);
106 strncatz (scratchFileName, dumpFilesPtr->ext, PATH_MAX);
107 if (!(dumpFilesPtr->filePtr = fopen (scratchFileName, "w"))) {
108 werror (E_FILE_OPEN_ERR, scratchFileName);
112 return dumpFilesPtr->filePtr;
115 /*-----------------------------------------------------------------*/
116 /* closeDumpFiles - close possible opened dumpfiles */
117 /*-----------------------------------------------------------------*/
118 void closeDumpFiles() {
119 struct _dumpFiles *dumpFilesPtr;
121 for (dumpFilesPtr=dumpFiles; dumpFilesPtr->id; dumpFilesPtr++) {
122 if (dumpFilesPtr->filePtr) {
123 fclose (dumpFilesPtr->filePtr);
128 /*-----------------------------------------------------------------*/
129 /* dumpLiveRanges - dump liverange information into a file */
130 /*-----------------------------------------------------------------*/
132 dumpLiveRanges (int id, hTab * liveRanges)
139 file=createDumpFile(id);
145 fprintf(file,"------------- Func %s -------------\n",currFunc->name);
146 for (sym = hTabFirstItem (liveRanges, &k); sym;
147 sym = hTabNextItem (liveRanges, &k))
150 fprintf (file, "%s [k%d lr%d:%d so:%d]{ re%d rm%d}",
151 (sym->rname[0] ? sym->rname : sym->name),
153 sym->liveFrom, sym->liveTo,
155 sym->isreqv, sym->remat
159 printTypeChain (sym->type, file);
160 if (sym->usl.spillLoc)
162 fprintf (file, "}{ sir@ %s", sym->usl.spillLoc->rname);
164 fprintf (file, "} clashes with ");
165 bitVectDebugOn(sym->clashes,file);
166 fprintf (file, "\n");
172 /*-----------------------------------------------------------------*/
173 /* dumpEbbsToFileExt - writeall the basic blocks to a file */
174 /*-----------------------------------------------------------------*/
176 dumpEbbsToFileExt (int id, eBBlock ** ebbs, int count)
184 of=createDumpFile(id);
189 for (i = 0; i < count; i++)
191 fprintf (of, "\n----------------------------------------------------------------\n");
192 fprintf (of, "Basic Block %s (df:%d bb:%d lvl:%d): loopDepth=%d%s%s%s\n",
193 ebbs[i]->entryLabel->name,
194 ebbs[i]->dfnum, ebbs[i]->bbnum, ebbs[i]->entryLabel->level,
196 ebbs[i]->noPath ? " noPath" : "",
197 ebbs[i]->partOfLoop ? " partOfLoop" : "",
198 ebbs[i]->isLastInLoop ? " isLastInLoop" : "");
200 // a --nolabelopt makes this more readable
201 fprintf (of, "\nsuccessors: ");
202 for (bb=setFirstItem(ebbs[i]->succList);
204 bb=setNextItem(ebbs[i]->succList)) {
205 fprintf (of, "%s ", bb->entryLabel->name);
207 fprintf (of, "\npredecessors: ");
208 for (bb=setFirstItem(ebbs[i]->predList);
210 bb=setNextItem(ebbs[i]->predList)) {
211 fprintf (of, "%s ", bb->entryLabel->name);
215 fprintf (of, "\ndominators: ");
216 for (d=0; d<ebbs[i]->domVect->size; d++) {
217 if (bitVectBitValue(ebbs[i]->domVect, d)) {
218 fprintf (of, "%s ", ebbs[d]->entryLabel->name);
224 fprintf (of, "\ndefines bitVector :");
225 bitVectDebugOn (ebbs[i]->defSet, of);
226 fprintf (of, "\nlocal defines bitVector :");
227 bitVectDebugOn (ebbs[i]->ldefs, of);
228 fprintf (of, "\npointers Set bitvector :");
229 bitVectDebugOn (ebbs[i]->ptrsSet, of);
230 if (ebbs[i]->isLastInLoop) {
231 fprintf (of, "\nInductions Set bitvector :");
232 bitVectDebugOn (ebbs[i]->linds, of);
235 fprintf (of, "\ninExprs:");
236 for (cseSet = ebbs[i]->inExprs; cseSet; cseSet=cseSet->next) {
237 cseDef *item=cseSet->item;
238 fprintf (of, " %s(%d)",OP_SYMBOL(item->sym)->name,item->diCode->key);
239 if (item->fromGlobal)
242 fprintf (of, "\noutExprs:");
243 for (cseSet = ebbs[i]->outExprs; cseSet; cseSet=cseSet->next) {
244 cseDef *item=cseSet->item;
245 fprintf (of, " %s(%d)",OP_SYMBOL(item->sym)->name,item->diCode->key);
246 if (item->fromGlobal)
249 fprintf (of, "\nkilledExprs:");
250 for (cseSet = ebbs[i]->killedExprs; cseSet; cseSet=cseSet->next) {
251 cseDef *item=cseSet->item;
252 fprintf (of, " %s(%d)",OP_SYMBOL(item->sym)->name,item->diCode->key);
253 if (item->fromGlobal)
257 fprintf (of, "\n----------------------------------------------------------------\n");
258 printiCChain (ebbs[i]->sch, of);
263 /*-----------------------------------------------------------------*/
264 /* iCode2eBBlock - converts a sequnce till label to a ebb */
265 /*-----------------------------------------------------------------*/
267 iCode2eBBlock (iCode * ic)
270 eBBlock *ebb = neweBBlock (); /* allocate an entry */
272 /* put the first one unconditionally */
275 /* if this is a label then */
277 ebb->entryLabel = ic->label;
280 SNPRINTF (buffer, sizeof(buffer), "_eBBlock%d", eBBNum++);
281 ebb->entryLabel = newSymbol (buffer, 1);
282 ebb->entryLabel->key = labelKey++;
287 ic->op == JUMPTABLE ||
294 /* if this is a function call */
295 if (ic->op == CALL || ic->op == PCALL)
299 FUNC_HASFCALL(currFunc->type) = 1;
302 if ((ic->next && ic->next->op == LABEL) ||
309 /* loop thru till we find one with a label */
310 for (loop = ic->next; loop; loop = loop->next)
313 /* if this is the last one */
316 /* if this is a function call */
317 if (loop->op == CALL || loop->op == PCALL)
321 FUNC_HASFCALL(currFunc->type) = 1;
324 /* if the next one is a label */
325 /* if this is a goto or ifx */
326 if (loop->next->op == LABEL ||
328 loop->op == JUMPTABLE ||
333 /* mark the end of the chain */
339 /*-----------------------------------------------------------------*/
340 /* eBBWithEntryLabel - finds the basic block with the entry label */
341 /*-----------------------------------------------------------------*/
343 eBBWithEntryLabel (eBBlock ** ebbs, symbol * eLabel, int count)
347 for (i = 0; i < count; i++)
349 if (isSymbolEqual (ebbs[i]->entryLabel, eLabel))
357 /*-----------------------------------------------------------------*/
358 /* ifFromIs - will return 1 if the from block matches this */
359 /*-----------------------------------------------------------------*/
360 DEFSETFUNC (ifFromIs)
363 V_ARG (eBBlock *, this);
365 if (ep->from == this)
372 /*-----------------------------------------------------------------*/
373 /* edgesTo - returns a set of edges with to == supplied value */
374 /*-----------------------------------------------------------------*/
376 edgesTo (eBBlock * to)
381 for (loop = setFirstItem (graphEdges); loop; loop = setNextItem (graphEdges))
382 if (loop->to == to && !loop->from->noPath)
383 addSet (&result, loop->from);
389 /*-----------------------------------------------------------------*/
390 /* addiCodeToeBBlock - will add an iCode to the end of a block */
391 /*-----------------------------------------------------------------*/
393 addiCodeToeBBlock (eBBlock * ebp, iCode * ic, iCode * ip)
395 ic->prev = ic->next = NULL;
396 /* if the insert point is given */
399 ic->lineno = ip->lineno;
410 /* if the block has no instructions */
411 if (ebp->ech == NULL)
413 ebp->sch = ebp->ech = ic;
418 /* if the last instruction is a goto */
419 /* we add it just before the goto */
420 if (ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE
421 || ebp->ech->op == RETURN)
423 ic->lineno = ebp->ech->lineno;
424 ic->prev = ebp->ech->prev;
427 if (!ic->prev) /* was the last only on in the block */
434 /* if the last one was a ifx statement we check to see */
435 /* if the condition was defined in the previous instruction */
436 /* if this is true then we put it before the condition else */
437 /* we put it before if, this is to reduce register pressure, */
438 /* we don't have to hold condition too long in a register */
439 if (ebp->ech->op == IFX)
443 /* if ( !ebp->ech->prev ) */
444 /* ipoint = ebp->ech ; */
446 /* if (!IC_RESULT(ebp->ech->prev)) */
447 /* ipoint = ebp->ech ; */
449 /* if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
450 /* ipoint = ebp->ech->prev; */
452 /* ipoint = ebp->ech ; */
454 ic->lineno = ipoint->lineno;
455 ic->prev = ipoint->prev;
465 /* will add it to the very end */
475 /*-----------------------------------------------------------------*/
476 /* remiCodeFromeBBlock - remove an iCode from BBlock */
477 /*-----------------------------------------------------------------*/
479 remiCodeFromeBBlock (eBBlock * ebb, iCode * ic)
481 wassert (ic->seq>=ebb->fSeq && ic->seq<=ebb->lSeq);
483 ic->prev->next = ic->next;
488 ic->next->prev = ic->prev;
493 /*-----------------------------------------------------------------*/
494 /* iCodeBreakDown : breakDown iCode chain to blocks */
495 /*-----------------------------------------------------------------*/
497 iCodeBreakDown (iCode * ic, int *count)
499 eBBlock **ebbs = NULL;
504 /* allocate for the first entry */
506 ebbs = Safe_alloc (sizeof (eBBlock **));
511 /* convert 2 block */
512 eBBlock *ebb = iCode2eBBlock (loop);
513 loop = ebb->ech->next;
515 ebb->ech->next = NULL; /* mark the end of this chain */
518 ebb->bbnum = *count; /* save this block number */
519 /* put it in the array */
520 ebbs[(*count)++] = ebb;
522 /* allocate for the next one. Remember to clear the new */
523 /* pointer at the end, that was created by realloc. */
525 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
529 /* if this one ends in a goto or a conditional */
530 /* branch then check if the block it is going */
531 /* to already exists, if yes then this could */
532 /* be a loop, add a preheader to the block it */
533 /* goes to if it does not already have one */
534 if (ebbs[(*count) - 1]->ech &&
535 (ebbs[(*count) - 1]->ech->op == GOTO ||
536 ebbs[(*count) - 1]->ech->op == IFX))
542 if (ebbs[(*count) - 1]->ech->op == GOTO)
543 label = IC_LABEL (ebbs[(*count) - 1]->ech);
544 else if (!(label = IC_TRUE (ebbs[(*count) - 1]->ech)))
545 label = IC_FALSE (ebbs[(*count) - 1]->ech);
547 if ((destBlock = eBBWithEntryLabel (ebbs, label, (*count))) &&
548 destBlock->preHeader == NULL &&
549 otherPathsPresent (ebbs, destBlock))
552 symbol *preHeaderLabel = newiTempPreheaderLabel ();
556 /* go thru all block replacing the entryLabel with new label */
557 /* till we reach the block , then we insert a new ebblock */
558 for (i = 0; i < (*count); i++)
560 if (ebbs[i] == destBlock)
562 replaceLabel (ebbs[i], label, preHeaderLabel);
567 /* if we have stopped at the block , allocate for an extra one */
569 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
573 /* then move the block down one count */
574 pBlock = ebbs[j = i];
575 for (i += 1; i < (*count); i++)
585 destBlock->preHeader = ebbs[j] = neweBBlock ();
587 ebbs[j]->entryLabel = preHeaderLabel;
588 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto (LABEL, preHeaderLabel);
589 ebbs[j]->sch->lineno = destBlock->sch->lineno;
600 /*-----------------------------------------------------------------*/
601 /* replaceSymBySym : - replace operand by operand in blocks */
602 /* replaces only left & right in blocks */
603 /*-----------------------------------------------------------------*/
605 replaceSymBySym (set * sset, operand * src, operand * dest)
610 /* for all blocks in the set do */
611 for (loop = sset; loop; loop = loop->next)
616 /* for all instructions in this block do */
617 for (ic = rBlock->sch; ic; ic = ic->next)
620 /* if we find usage */
621 if (ic->op == IFX && isOperandEqual (src, IC_COND (ic)))
623 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
624 IC_COND (ic) = operandFromOperand (dest);
625 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
629 if (isOperandEqual (IC_RIGHT (ic), src))
631 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
632 IC_RIGHT (ic) = operandFromOperand (dest);
633 IC_RIGHT (ic)->isaddr = 0;
634 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
637 if (isOperandEqual (IC_LEFT (ic), src))
639 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
640 if (POINTER_GET (ic) && IS_ITEMP (dest))
642 IC_LEFT (ic) = operandFromOperand (dest);
643 IC_LEFT (ic)->isaddr = 1;
647 IC_LEFT (ic) = operandFromOperand (dest);
648 IC_LEFT (ic)->isaddr = 0;
650 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
653 /* special case for pointer sets */
654 if (POINTER_SET (ic) &&
655 isOperandEqual (IC_RESULT (ic), src))
657 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
658 IC_RESULT (ic) = operandFromOperand (dest);
659 IC_RESULT (ic)->isaddr = 1;
660 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
666 /*-----------------------------------------------------------------*/
667 /* replaceLabel - replace reference to one label by another */
668 /*-----------------------------------------------------------------*/
670 replaceLabel (eBBlock * ebp, symbol * fromLbl, symbol * toLbl)
677 for (ic = ebp->sch; ic; ic = ic->next)
683 if (isSymbolEqual (IC_LABEL (ic), fromLbl))
684 IC_LABEL (ic) = toLbl;
688 if (IC_TRUE (ic) && isSymbolEqual (IC_TRUE (ic), fromLbl))
689 IC_TRUE (ic) = toLbl;
690 else if (isSymbolEqual (IC_FALSE (ic), fromLbl))
691 IC_FALSE (ic) = toLbl;
701 /*-----------------------------------------------------------------*/
702 /* iCodeFromeBBlock - convert basic block to iCode chain */
703 /*-----------------------------------------------------------------*/
705 iCodeFromeBBlock (eBBlock ** ebbs, int count)
708 iCode *ric = ebbs[0]->sch;
709 iCode *lic = ebbs[0]->ech;
711 for (; i < count; i++)
713 if (ebbs[i]->sch == NULL)
716 if (ebbs[i]->noPath &&
717 (ebbs[i]->entryLabel != entryLabel &&
718 ebbs[i]->entryLabel != returnLabel))
721 bool foundNonlabel = 0;
730 if (ic==ebbs[i]->ech)
735 if (foundNonlabel && ic)
737 werrorfl (ic->filename, ic->lineno, W_CODE_UNREACH);
742 lic->next = ebbs[i]->sch;
743 lic->next->prev = lic;
751 /*-----------------------------------------------------------------*/
752 /* otherPathsPresent - determines if there is a path from _entry */
753 /* to this block in a half constructed set of blocks */
754 /*-----------------------------------------------------------------*/
756 otherPathsPresent (eBBlock ** ebbs, eBBlock * this)
760 /* for all blocks preceding this block */
761 for (i = 0; i < this->bbnum; i++)
765 /* if there is a reference to the entry label of this block */
766 for (ic = ebbs[i]->sch; ic; ic = ic->next)
771 if (IC_LABEL (ic)->key == this->entryLabel->key)
778 if (IC_TRUE (ic)->key == this->entryLabel->key)
781 else if (IC_FALSE (ic)->key == this->entryLabel->key)
788 /* comes here means we have not found it yet */
789 /* in this case check if the previous block */
790 /* ends in a goto if it does then we have no */
791 /* path else we have a path */
792 if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
793 ebbs[this->bbnum - 1]->ech->op == GOTO)