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 -------------------------------------------------------------------------*/
30 set *graphEdges = NULL; /* list of edges in this flow graph */
32 struct _dumpFiles dumpFiles[] = {
33 {DUMP_RAW0, ".dumpraw0", NULL},
34 {DUMP_RAW1, ".dumpraw1", NULL},
35 {DUMP_CSE, ".dumpcse", NULL},
36 {DUMP_DFLOW, ".dumpdflow", NULL},
37 {DUMP_GCSE, ".dumpgcse", NULL},
38 {DUMP_DEADCODE, ".dumpdeadcode", NULL},
39 {DUMP_LOOP, ".dumploop", NULL},
40 {DUMP_LOOPG, ".dumploopg", NULL},
41 {DUMP_LOOPD, ".dumploopd", NULL},
42 {DUMP_RANGE, ".dumprange", NULL},
43 {DUMP_PACK, ".dumppack", NULL},
44 {DUMP_RASSGN, ".dumprassgn", NULL},
45 {DUMP_LRANGE, ".dumplrange", NULL},
49 /*-----------------------------------------------------------------*/
50 /* printEntryLabel - prints entry label of a ebblock */
51 /*-----------------------------------------------------------------*/
52 DEFSETFUNC (printEntryLabel)
56 fprintf (stdout, " %-20s ", bp->entryLabel->name);
60 /*-----------------------------------------------------------------*/
61 /* neweBBlock - allocate & return a new extended basic block */
62 /*-----------------------------------------------------------------*/
68 ebb = Safe_calloc (1, sizeof (eBBlock));
72 /*-----------------------------------------------------------------*/
73 /* newEdge - allocates & initialises an edge to given values */
74 /*-----------------------------------------------------------------*/
76 newEdge (eBBlock * from, eBBlock * to)
80 ep = Safe_calloc (1, sizeof (edge));
87 /*-----------------------------------------------------------------*/
88 /* appendDumpFile - if not already created, create the dump file */
89 /*-----------------------------------------------------------------*/
90 FILE *appendDumpFile (int id) {
91 struct _dumpFiles *dumpFilesPtr=dumpFiles;
93 while (dumpFilesPtr->id) {
94 if (dumpFilesPtr->id==id)
99 if (!dumpFilesPtr->id) {
100 fprintf (stdout, "internal error: appendDumpFile: unknown dump file.\n");
104 if (!dumpFilesPtr->filePtr) {
105 // not used before, create it
106 strcpy (scratchFileName, srcFileName);
107 strcat (scratchFileName, dumpFilesPtr->ext);
108 if (!(dumpFilesPtr->filePtr = fopen (scratchFileName, "w"))) {
109 werror (E_FILE_OPEN_ERR, scratchFileName);
113 return dumpFilesPtr->filePtr;
116 /*-----------------------------------------------------------------*/
117 /* closeDumpFiles - close possible opened dumpfiles */
118 /*-----------------------------------------------------------------*/
119 void closeDumpFiles() {
120 struct _dumpFiles *dumpFilesPtr;
122 for (dumpFilesPtr=dumpFiles; dumpFilesPtr->id; dumpFilesPtr++) {
123 if (dumpFilesPtr->filePtr) {
124 fclose (dumpFilesPtr->filePtr);
125 //dprintf ("closed %s\n", dumpFilesPtr->ext);
130 /*-----------------------------------------------------------------*/
131 /* dumpLiveRanges - dump liverange information into a file */
132 /*-----------------------------------------------------------------*/
134 dumpLiveRanges (int id, hTab * liveRanges)
141 file=appendDumpFile(id);
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);
166 /* if assigned to registers */
172 if (sym->usl.spillLoc)
173 fprintf (file, "[%s]", (sym->usl.spillLoc->rname[0] ?
174 sym->usl.spillLoc->rname :
175 sym->usl.spillLoc->name));
177 fprintf (file, "[err]");
179 fprintf (file, "[remat]");
185 for (i = 0; i < sym->nRegs; i++)
186 fprintf (file, "%s ", port->getRegName (sym->regs[i]));
190 fprintf (file, "\n");
196 /*-----------------------------------------------------------------*/
197 /* dumpEbbsToFileExt - writeall the basic blocks to a file */
198 /*-----------------------------------------------------------------*/
200 dumpEbbsToFileExt (int id, eBBlock ** ebbs, int count)
206 of=appendDumpFile(id);
211 for (i = 0; i < count; i++)
213 fprintf (of, "\n----------------------------------------------------------------\n");
214 fprintf (of, "Basic Block %s : loop Depth = %d noPath = %d , lastinLoop = %d\n",
215 ebbs[i]->entryLabel->name,
218 ebbs[i]->isLastInLoop);
219 fprintf (of, "\ndefines bitVector :");
220 bitVectDebugOn (ebbs[i]->defSet, of);
221 fprintf (of, "\nlocal defines bitVector :");
222 bitVectDebugOn (ebbs[i]->ldefs, of);
223 fprintf (of, "\npointers Set bitvector :");
224 bitVectDebugOn (ebbs[i]->ptrsSet, of);
225 fprintf (of, "\n----------------------------------------------------------------\n");
226 printiCChain (ebbs[i]->sch, of);
231 /*-----------------------------------------------------------------*/
232 /* iCode2eBBlock - converts a sequnce till label to a ebb */
233 /*-----------------------------------------------------------------*/
235 iCode2eBBlock (iCode * ic)
238 eBBlock *ebb = neweBBlock (); /* a llocate an entry */
240 /* put the first one unconditionally */
243 /* if this is a label then */
245 ebb->entryLabel = ic->argLabel.label;
248 sprintf (buffer, "_eBBlock%d", eBBNum++);
249 ebb->entryLabel = newSymbol (buffer, 1);
250 ebb->entryLabel->key = labelKey++;
255 ic->op == JUMPTABLE ||
262 if ((ic->next && ic->next->op == LABEL) ||
269 /* loop thru till we find one with a label */
270 for (loop = ic->next; loop; loop = loop->next)
273 /* if this is the last one */
276 /* if this is a function call */
277 if (loop->op == CALL || loop->op == PCALL)
281 currFunc->hasFcall = 1;
284 /* if the next one is a label */
285 /* if this is a goto or ifx */
286 if (loop->next->op == LABEL ||
288 loop->op == JUMPTABLE ||
293 /* mark the end of the chain */
299 /*-----------------------------------------------------------------*/
300 /* eBBWithEntryLabel - finds the basic block with the entry label */
301 /*-----------------------------------------------------------------*/
303 eBBWithEntryLabel (eBBlock ** ebbs, symbol * eLabel, int count)
307 for (i = 0; i < count; i++)
309 if (isSymbolEqual (ebbs[i]->entryLabel, eLabel))
317 /*-----------------------------------------------------------------*/
318 /* ifFromIs - will return 1 if the from block matches this */
319 /*-----------------------------------------------------------------*/
320 DEFSETFUNC (ifFromIs)
323 V_ARG (eBBlock *, this);
325 if (ep->from == this)
332 /*-----------------------------------------------------------------*/
333 /* edgesTo - returns a set of edges with to == supplied value */
334 /*-----------------------------------------------------------------*/
336 edgesTo (eBBlock * to)
341 for (loop = setFirstItem (graphEdges); loop; loop = setNextItem (graphEdges))
342 if (loop->to == to && !loop->from->noPath)
343 addSet (&result, loop->from);
349 /*-----------------------------------------------------------------*/
350 /* addiCodeToeBBlock - will add an iCode to the end of a block */
351 /*-----------------------------------------------------------------*/
353 addiCodeToeBBlock (eBBlock * ebp, iCode * ic, iCode * ip)
355 ic->prev = ic->next = NULL;
356 /* if the insert point is given */
359 ic->lineno = ip->lineno;
370 /* if the block has no instructions */
371 if (ebp->ech == NULL)
373 ebp->sch = ebp->ech = ic;
378 /* if the last instruction is a goto */
379 /* we add it just before the goto */
380 if (ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE
381 || ebp->ech->op == RETURN)
383 ic->lineno = ebp->ech->lineno;
384 ic->prev = ebp->ech->prev;
387 if (!ic->prev) /* was the last only on in the block */
394 /* if the last one was a ifx statement we check to see */
395 /* if the condition was defined in the previous instruction */
396 /* if this is true then we put it before the condition else */
397 /* we put it before if, this is to reduce register pressure, */
398 /* we don't have to hold condition too long in a register */
399 if (ebp->ech->op == IFX)
403 /* if ( !ebp->ech->prev ) */
404 /* ipoint = ebp->ech ; */
406 /* if (!IC_RESULT(ebp->ech->prev)) */
407 /* ipoint = ebp->ech ; */
409 /* if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
410 /* ipoint = ebp->ech->prev; */
412 /* ipoint = ebp->ech ; */
414 ic->lineno = ipoint->lineno;
415 ic->prev = ipoint->prev;
425 /* will add it to the very end */
435 /*-----------------------------------------------------------------*/
436 /* remiCodeFromeBBlock - remove an iCode from BBlock */
437 /*-----------------------------------------------------------------*/
439 remiCodeFromeBBlock (eBBlock * ebb, iCode * ic)
442 ic->prev->next = ic->next;
447 ic->next->prev = ic->prev;
452 /*-----------------------------------------------------------------*/
453 /* iCodeBreakDown : breakDown iCode chain to blocks */
454 /*-----------------------------------------------------------------*/
456 iCodeBreakDown (iCode * ic, int *count)
458 eBBlock **ebbs = NULL;
463 /* allocate for the first entry */
465 ebbs = Safe_calloc (1, sizeof (eBBlock **));
470 /* convert 2 block */
471 eBBlock *ebb = iCode2eBBlock (loop);
472 loop = ebb->ech->next;
474 ebb->ech->next = NULL; /* mark the end of this chain */
477 ebb->bbnum = *count; /* save this block number */
478 /* put it in the array */
479 ebbs[(*count)++] = ebb;
481 /* allocate for the next one. Remember to clear the new */
482 /* pointer at the end, that was created by realloc. */
484 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
488 /* if this one ends in a goto or a conditional */
489 /* branch then check if the block it is going */
490 /* to already exists, if yes then this could */
491 /* be a loop, add a preheader to the block it */
492 /* goes to if it does not already have one */
493 if (ebbs[(*count) - 1]->ech &&
494 (ebbs[(*count) - 1]->ech->op == GOTO ||
495 ebbs[(*count) - 1]->ech->op == IFX))
501 if (ebbs[(*count) - 1]->ech->op == GOTO)
502 label = IC_LABEL (ebbs[(*count) - 1]->ech);
503 else if (!(label = IC_TRUE (ebbs[(*count) - 1]->ech)))
504 label = IC_FALSE (ebbs[(*count) - 1]->ech);
506 if ((destBlock = eBBWithEntryLabel (ebbs, label, (*count))) &&
507 destBlock->preHeader == NULL &&
508 otherPathsPresent (ebbs, destBlock))
511 symbol *preHeaderLabel = newiTempPreheaderLabel ();
515 /* go thru all block replacing the entryLabel with new label */
516 /* till we reach the block , then we insert a new ebblock */
517 for (i = 0; i < (*count); i++)
519 if (ebbs[i] == destBlock)
521 replaceLabel (ebbs[i], label, preHeaderLabel);
526 /* if we have stopped at the block , allocate for an extra one */
528 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
532 /* then move the block down one count */
533 pBlock = ebbs[j = i];
534 for (i += 1; i < (*count); i++)
544 destBlock->preHeader = ebbs[j] = neweBBlock ();
546 ebbs[j]->entryLabel = preHeaderLabel;
547 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto (LABEL, preHeaderLabel);
548 ebbs[j]->sch->lineno = destBlock->sch->lineno;
559 /*-----------------------------------------------------------------*/
560 /* replaceSymBySym : - replace operand by operand in blocks */
561 /* replaces only left & right in blocks */
562 /*-----------------------------------------------------------------*/
564 replaceSymBySym (set * sset, operand * src, operand * dest)
569 /* for all blocks in the set do */
570 for (loop = sset; loop; loop = loop->next)
575 /* for all instructions in this block do */
576 for (ic = rBlock->sch; ic; ic = ic->next)
579 /* if we find usage */
580 if (ic->op == IFX && isOperandEqual (src, IC_COND (ic)))
582 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
583 IC_COND (ic) = operandFromOperand (dest);
584 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
588 if (isOperandEqual (IC_RIGHT (ic), src))
590 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
591 IC_RIGHT (ic) = operandFromOperand (dest);
592 IC_RIGHT (ic)->isaddr = 0;
593 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
596 if (isOperandEqual (IC_LEFT (ic), src))
598 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
599 if (POINTER_GET (ic) && IS_ITEMP (dest))
601 IC_LEFT (ic) = operandFromOperand (dest);
602 IC_LEFT (ic)->isaddr = 1;
606 IC_LEFT (ic) = operandFromOperand (dest);
607 IC_LEFT (ic)->isaddr = 0;
609 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
612 /* special case for pointer sets */
613 if (POINTER_SET (ic) &&
614 isOperandEqual (IC_RESULT (ic), src))
616 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
617 IC_RESULT (ic) = operandFromOperand (dest);
618 IC_RESULT (ic)->isaddr = 1;
619 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
625 /*-----------------------------------------------------------------*/
626 /* replaceLabel - replace reference to one label by another */
627 /*-----------------------------------------------------------------*/
629 replaceLabel (eBBlock * ebp, symbol * fromLbl, symbol * toLbl)
636 for (ic = ebp->sch; ic; ic = ic->next)
642 if (isSymbolEqual (IC_LABEL (ic), fromLbl))
643 IC_LABEL (ic) = toLbl;
647 if (IC_TRUE (ic) && isSymbolEqual (IC_TRUE (ic), fromLbl))
648 IC_TRUE (ic) = toLbl;
649 else if (isSymbolEqual (IC_FALSE (ic), fromLbl))
650 IC_FALSE (ic) = toLbl;
660 /*-----------------------------------------------------------------*/
661 /* iCodeFromeBBlock - convert basic block to iCode chain */
662 /*-----------------------------------------------------------------*/
664 iCodeFromeBBlock (eBBlock ** ebbs, int count)
667 iCode *ric = ebbs[0]->sch;
668 iCode *lic = ebbs[0]->ech;
670 for (; i < count; i++)
672 if (ebbs[i]->sch == NULL)
675 if (ebbs[i]->noPath &&
676 (ebbs[i]->entryLabel != entryLabel &&
677 ebbs[i]->entryLabel != returnLabel))
679 werror (W_CODE_UNREACH, ebbs[i]->sch->filename, ebbs[i]->sch->lineno);
683 lic->next = ebbs[i]->sch;
684 lic->next->prev = lic;
691 /*-----------------------------------------------------------------*/
692 /* otherPathsPresent - determines if there is a path from _entry */
693 /* to this block in a half constructed set of blocks */
694 /*-----------------------------------------------------------------*/
696 otherPathsPresent (eBBlock ** ebbs, eBBlock * this)
700 /* for all blocks preceding this block */
701 for (i = 0; i < this->bbnum; i++)
705 /* if there is a reference to the entry label of this block */
706 for (ic = ebbs[i]->sch; ic; ic = ic->next)
711 if (IC_LABEL (ic)->key == this->entryLabel->key)
718 if (IC_TRUE (ic)->key == this->entryLabel->key)
721 else if (IC_FALSE (ic)->key == this->entryLabel->key)
728 /* comes here means we have not found it yet */
729 /* in this case check if the previous block */
730 /* ends in a goto if it does then we have no */
731 /* path else we have a path */
732 if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
733 ebbs[this->bbnum - 1]->ech->op == GOTO)