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)
183 of=createDumpFile(id);
188 for (i = 0; i < count; i++)
190 fprintf (of, "\n----------------------------------------------------------------\n");
191 fprintf (of, "Basic Block %s (df:%d bb:%d lvl:%d): loopDepth=%d%s%s%s\n",
192 ebbs[i]->entryLabel->name,
193 ebbs[i]->dfnum, ebbs[i]->bbnum, ebbs[i]->entryLabel->level,
195 ebbs[i]->noPath ? " noPath" : "",
196 ebbs[i]->partOfLoop ? " partOfLoop" : "",
197 ebbs[i]->isLastInLoop ? " isLastInLoop" : "");
199 // a --nolabelopt makes this more readable
200 fprintf (of, "\nsuccessors: ");
201 for (bb=setFirstItem(ebbs[i]->succList);
203 bb=setNextItem(ebbs[i]->succList)) {
204 fprintf (of, "%s ", bb->entryLabel->name);
206 fprintf (of, "\npredecessors: ");
207 for (bb=setFirstItem(ebbs[i]->predList);
209 bb=setNextItem(ebbs[i]->predList)) {
210 fprintf (of, "%s ", bb->entryLabel->name);
214 fprintf (of, "\ndominators: ");
215 for (d=0; d<ebbs[i]->domVect->size; d++) {
216 if (bitVectBitValue(ebbs[i]->domVect, d)) {
217 fprintf (of, "%s ", ebbs[d]->entryLabel->name);
223 fprintf (of, "\ndefines bitVector :");
224 bitVectDebugOn (ebbs[i]->defSet, of);
225 fprintf (of, "\nlocal defines bitVector :");
226 bitVectDebugOn (ebbs[i]->ldefs, of);
227 fprintf (of, "\npointers Set bitvector :");
228 bitVectDebugOn (ebbs[i]->ptrsSet, of);
229 if (ebbs[i]->isLastInLoop) {
230 fprintf (of, "\nInductions Set bitvector :");
231 bitVectDebugOn (ebbs[i]->linds, of);
233 fprintf (of, "\n----------------------------------------------------------------\n");
234 printiCChain (ebbs[i]->sch, of);
239 /*-----------------------------------------------------------------*/
240 /* iCode2eBBlock - converts a sequnce till label to a ebb */
241 /*-----------------------------------------------------------------*/
243 iCode2eBBlock (iCode * ic)
246 eBBlock *ebb = neweBBlock (); /* allocate an entry */
248 /* put the first one unconditionally */
251 /* if this is a label then */
253 ebb->entryLabel = ic->label;
256 SNPRINTF (buffer, sizeof(buffer), "_eBBlock%d", eBBNum++);
257 ebb->entryLabel = newSymbol (buffer, 1);
258 ebb->entryLabel->key = labelKey++;
263 ic->op == JUMPTABLE ||
270 /* if this is a function call */
271 if (ic->op == CALL || ic->op == PCALL)
275 FUNC_HASFCALL(currFunc->type) = 1;
278 if ((ic->next && ic->next->op == LABEL) ||
285 /* loop thru till we find one with a label */
286 for (loop = ic->next; loop; loop = loop->next)
289 /* if this is the last one */
292 /* if this is a function call */
293 if (loop->op == CALL || loop->op == PCALL)
297 FUNC_HASFCALL(currFunc->type) = 1;
300 /* if the next one is a label */
301 /* if this is a goto or ifx */
302 if (loop->next->op == LABEL ||
304 loop->op == JUMPTABLE ||
309 /* mark the end of the chain */
315 /*-----------------------------------------------------------------*/
316 /* eBBWithEntryLabel - finds the basic block with the entry label */
317 /*-----------------------------------------------------------------*/
319 eBBWithEntryLabel (eBBlock ** ebbs, symbol * eLabel, int count)
323 for (i = 0; i < count; i++)
325 if (isSymbolEqual (ebbs[i]->entryLabel, eLabel))
333 /*-----------------------------------------------------------------*/
334 /* ifFromIs - will return 1 if the from block matches this */
335 /*-----------------------------------------------------------------*/
336 DEFSETFUNC (ifFromIs)
339 V_ARG (eBBlock *, this);
341 if (ep->from == this)
348 /*-----------------------------------------------------------------*/
349 /* edgesTo - returns a set of edges with to == supplied value */
350 /*-----------------------------------------------------------------*/
352 edgesTo (eBBlock * to)
357 for (loop = setFirstItem (graphEdges); loop; loop = setNextItem (graphEdges))
358 if (loop->to == to && !loop->from->noPath)
359 addSet (&result, loop->from);
365 /*-----------------------------------------------------------------*/
366 /* addiCodeToeBBlock - will add an iCode to the end of a block */
367 /*-----------------------------------------------------------------*/
369 addiCodeToeBBlock (eBBlock * ebp, iCode * ic, iCode * ip)
371 ic->prev = ic->next = NULL;
372 /* if the insert point is given */
375 ic->lineno = ip->lineno;
386 /* if the block has no instructions */
387 if (ebp->ech == NULL)
389 ebp->sch = ebp->ech = ic;
394 /* if the last instruction is a goto */
395 /* we add it just before the goto */
396 if (ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE
397 || ebp->ech->op == RETURN)
399 ic->lineno = ebp->ech->lineno;
400 ic->prev = ebp->ech->prev;
403 if (!ic->prev) /* was the last only on in the block */
410 /* if the last one was a ifx statement we check to see */
411 /* if the condition was defined in the previous instruction */
412 /* if this is true then we put it before the condition else */
413 /* we put it before if, this is to reduce register pressure, */
414 /* we don't have to hold condition too long in a register */
415 if (ebp->ech->op == IFX)
419 /* if ( !ebp->ech->prev ) */
420 /* ipoint = ebp->ech ; */
422 /* if (!IC_RESULT(ebp->ech->prev)) */
423 /* ipoint = ebp->ech ; */
425 /* if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
426 /* ipoint = ebp->ech->prev; */
428 /* ipoint = ebp->ech ; */
430 ic->lineno = ipoint->lineno;
431 ic->prev = ipoint->prev;
441 /* will add it to the very end */
451 /*-----------------------------------------------------------------*/
452 /* remiCodeFromeBBlock - remove an iCode from BBlock */
453 /*-----------------------------------------------------------------*/
455 remiCodeFromeBBlock (eBBlock * ebb, iCode * ic)
457 wassert (ic->seq>=ebb->fSeq && ic->seq<=ebb->lSeq);
459 ic->prev->next = ic->next;
464 ic->next->prev = ic->prev;
469 /*-----------------------------------------------------------------*/
470 /* iCodeBreakDown : breakDown iCode chain to blocks */
471 /*-----------------------------------------------------------------*/
473 iCodeBreakDown (iCode * ic, int *count)
475 eBBlock **ebbs = NULL;
480 /* allocate for the first entry */
482 ebbs = Safe_alloc (sizeof (eBBlock **));
487 /* convert 2 block */
488 eBBlock *ebb = iCode2eBBlock (loop);
489 loop = ebb->ech->next;
491 ebb->ech->next = NULL; /* mark the end of this chain */
494 ebb->bbnum = *count; /* save this block number */
495 /* put it in the array */
496 ebbs[(*count)++] = ebb;
498 /* allocate for the next one. Remember to clear the new */
499 /* pointer at the end, that was created by realloc. */
501 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
505 /* if this one ends in a goto or a conditional */
506 /* branch then check if the block it is going */
507 /* to already exists, if yes then this could */
508 /* be a loop, add a preheader to the block it */
509 /* goes to if it does not already have one */
510 if (ebbs[(*count) - 1]->ech &&
511 (ebbs[(*count) - 1]->ech->op == GOTO ||
512 ebbs[(*count) - 1]->ech->op == IFX))
518 if (ebbs[(*count) - 1]->ech->op == GOTO)
519 label = IC_LABEL (ebbs[(*count) - 1]->ech);
520 else if (!(label = IC_TRUE (ebbs[(*count) - 1]->ech)))
521 label = IC_FALSE (ebbs[(*count) - 1]->ech);
523 if ((destBlock = eBBWithEntryLabel (ebbs, label, (*count))) &&
524 destBlock->preHeader == NULL &&
525 otherPathsPresent (ebbs, destBlock))
528 symbol *preHeaderLabel = newiTempPreheaderLabel ();
532 /* go thru all block replacing the entryLabel with new label */
533 /* till we reach the block , then we insert a new ebblock */
534 for (i = 0; i < (*count); i++)
536 if (ebbs[i] == destBlock)
538 replaceLabel (ebbs[i], label, preHeaderLabel);
543 /* if we have stopped at the block , allocate for an extra one */
545 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
549 /* then move the block down one count */
550 pBlock = ebbs[j = i];
551 for (i += 1; i < (*count); i++)
561 destBlock->preHeader = ebbs[j] = neweBBlock ();
563 ebbs[j]->entryLabel = preHeaderLabel;
564 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto (LABEL, preHeaderLabel);
565 ebbs[j]->sch->lineno = destBlock->sch->lineno;
576 /*-----------------------------------------------------------------*/
577 /* replaceSymBySym : - replace operand by operand in blocks */
578 /* replaces only left & right in blocks */
579 /*-----------------------------------------------------------------*/
581 replaceSymBySym (set * sset, operand * src, operand * dest)
586 /* for all blocks in the set do */
587 for (loop = sset; loop; loop = loop->next)
592 /* for all instructions in this block do */
593 for (ic = rBlock->sch; ic; ic = ic->next)
596 /* if we find usage */
597 if (ic->op == IFX && isOperandEqual (src, IC_COND (ic)))
599 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
600 IC_COND (ic) = operandFromOperand (dest);
601 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
605 if (isOperandEqual (IC_RIGHT (ic), src))
607 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
608 IC_RIGHT (ic) = operandFromOperand (dest);
609 IC_RIGHT (ic)->isaddr = 0;
610 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
613 if (isOperandEqual (IC_LEFT (ic), src))
615 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
616 if (POINTER_GET (ic) && IS_ITEMP (dest))
618 IC_LEFT (ic) = operandFromOperand (dest);
619 IC_LEFT (ic)->isaddr = 1;
623 IC_LEFT (ic) = operandFromOperand (dest);
624 IC_LEFT (ic)->isaddr = 0;
626 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
629 /* special case for pointer sets */
630 if (POINTER_SET (ic) &&
631 isOperandEqual (IC_RESULT (ic), src))
633 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
634 IC_RESULT (ic) = operandFromOperand (dest);
635 IC_RESULT (ic)->isaddr = 1;
636 OP_USES(dest)=bitVectSetBit (OP_USES (dest), ic->key);
642 /*-----------------------------------------------------------------*/
643 /* replaceLabel - replace reference to one label by another */
644 /*-----------------------------------------------------------------*/
646 replaceLabel (eBBlock * ebp, symbol * fromLbl, symbol * toLbl)
653 for (ic = ebp->sch; ic; ic = ic->next)
659 if (isSymbolEqual (IC_LABEL (ic), fromLbl))
660 IC_LABEL (ic) = toLbl;
664 if (IC_TRUE (ic) && isSymbolEqual (IC_TRUE (ic), fromLbl))
665 IC_TRUE (ic) = toLbl;
666 else if (isSymbolEqual (IC_FALSE (ic), fromLbl))
667 IC_FALSE (ic) = toLbl;
677 /*-----------------------------------------------------------------*/
678 /* iCodeFromeBBlock - convert basic block to iCode chain */
679 /*-----------------------------------------------------------------*/
681 iCodeFromeBBlock (eBBlock ** ebbs, int count)
684 iCode *ric = ebbs[0]->sch;
685 iCode *lic = ebbs[0]->ech;
687 for (; i < count; i++)
689 if (ebbs[i]->sch == NULL)
692 if (ebbs[i]->noPath &&
693 (ebbs[i]->entryLabel != entryLabel &&
694 ebbs[i]->entryLabel != returnLabel))
697 bool foundNonlabel = 0;
706 if (ic==ebbs[i]->ech)
711 if (foundNonlabel && ic)
713 werror (W_CODE_UNREACH, ic->filename, ic->lineno);
718 lic->next = ebbs[i]->sch;
719 lic->next->prev = lic;
727 /*-----------------------------------------------------------------*/
728 /* otherPathsPresent - determines if there is a path from _entry */
729 /* to this block in a half constructed set of blocks */
730 /*-----------------------------------------------------------------*/
732 otherPathsPresent (eBBlock ** ebbs, eBBlock * this)
736 /* for all blocks preceding this block */
737 for (i = 0; i < this->bbnum; i++)
741 /* if there is a reference to the entry label of this block */
742 for (ic = ebbs[i]->sch; ic; ic = ic->next)
747 if (IC_LABEL (ic)->key == this->entryLabel->key)
754 if (IC_TRUE (ic)->key == this->entryLabel->key)
757 else if (IC_FALSE (ic)->key == this->entryLabel->key)
764 /* comes here means we have not found it yet */
765 /* in this case check if the previous block */
766 /* ends in a goto if it does then we have no */
767 /* path else we have a path */
768 if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
769 ebbs[this->bbnum - 1]->ech->op == GOTO)