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);
165 fprintf (file, "\n");
171 /*-----------------------------------------------------------------*/
172 /* dumpEbbsToFileExt - writeall the basic blocks to a file */
173 /*-----------------------------------------------------------------*/
175 dumpEbbsToFileExt (int id, eBBlock ** ebbs, int count)
181 of=appendDumpFile(id);
186 for (i = 0; i < count; i++)
188 fprintf (of, "\n----------------------------------------------------------------\n");
189 fprintf (of, "Basic Block %s : loop Depth = %d noPath = %d , lastinLoop = %d\n",
190 ebbs[i]->entryLabel->name,
193 ebbs[i]->isLastInLoop);
194 fprintf (of, "\ndefines bitVector :");
195 bitVectDebugOn (ebbs[i]->defSet, of);
196 fprintf (of, "\nlocal defines bitVector :");
197 bitVectDebugOn (ebbs[i]->ldefs, of);
198 fprintf (of, "\npointers Set bitvector :");
199 bitVectDebugOn (ebbs[i]->ptrsSet, of);
200 fprintf (of, "\n----------------------------------------------------------------\n");
201 printiCChain (ebbs[i]->sch, of);
206 /*-----------------------------------------------------------------*/
207 /* iCode2eBBlock - converts a sequnce till label to a ebb */
208 /*-----------------------------------------------------------------*/
210 iCode2eBBlock (iCode * ic)
213 eBBlock *ebb = neweBBlock (); /* a llocate an entry */
215 /* put the first one unconditionally */
218 /* if this is a label then */
220 ebb->entryLabel = ic->argLabel.label;
223 sprintf (buffer, "_eBBlock%d", eBBNum++);
224 ebb->entryLabel = newSymbol (buffer, 1);
225 ebb->entryLabel->key = labelKey++;
230 ic->op == JUMPTABLE ||
237 if ((ic->next && ic->next->op == LABEL) ||
244 /* loop thru till we find one with a label */
245 for (loop = ic->next; loop; loop = loop->next)
248 /* if this is the last one */
251 /* if this is a function call */
252 if (loop->op == CALL || loop->op == PCALL)
256 currFunc->hasFcall = 1;
259 /* if the next one is a label */
260 /* if this is a goto or ifx */
261 if (loop->next->op == LABEL ||
263 loop->op == JUMPTABLE ||
268 /* mark the end of the chain */
274 /*-----------------------------------------------------------------*/
275 /* eBBWithEntryLabel - finds the basic block with the entry label */
276 /*-----------------------------------------------------------------*/
278 eBBWithEntryLabel (eBBlock ** ebbs, symbol * eLabel, int count)
282 for (i = 0; i < count; i++)
284 if (isSymbolEqual (ebbs[i]->entryLabel, eLabel))
292 /*-----------------------------------------------------------------*/
293 /* ifFromIs - will return 1 if the from block matches this */
294 /*-----------------------------------------------------------------*/
295 DEFSETFUNC (ifFromIs)
298 V_ARG (eBBlock *, this);
300 if (ep->from == this)
307 /*-----------------------------------------------------------------*/
308 /* edgesTo - returns a set of edges with to == supplied value */
309 /*-----------------------------------------------------------------*/
311 edgesTo (eBBlock * to)
316 for (loop = setFirstItem (graphEdges); loop; loop = setNextItem (graphEdges))
317 if (loop->to == to && !loop->from->noPath)
318 addSet (&result, loop->from);
324 /*-----------------------------------------------------------------*/
325 /* addiCodeToeBBlock - will add an iCode to the end of a block */
326 /*-----------------------------------------------------------------*/
328 addiCodeToeBBlock (eBBlock * ebp, iCode * ic, iCode * ip)
330 ic->prev = ic->next = NULL;
331 /* if the insert point is given */
334 ic->lineno = ip->lineno;
345 /* if the block has no instructions */
346 if (ebp->ech == NULL)
348 ebp->sch = ebp->ech = ic;
353 /* if the last instruction is a goto */
354 /* we add it just before the goto */
355 if (ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE
356 || ebp->ech->op == RETURN)
358 ic->lineno = ebp->ech->lineno;
359 ic->prev = ebp->ech->prev;
362 if (!ic->prev) /* was the last only on in the block */
369 /* if the last one was a ifx statement we check to see */
370 /* if the condition was defined in the previous instruction */
371 /* if this is true then we put it before the condition else */
372 /* we put it before if, this is to reduce register pressure, */
373 /* we don't have to hold condition too long in a register */
374 if (ebp->ech->op == IFX)
378 /* if ( !ebp->ech->prev ) */
379 /* ipoint = ebp->ech ; */
381 /* if (!IC_RESULT(ebp->ech->prev)) */
382 /* ipoint = ebp->ech ; */
384 /* if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
385 /* ipoint = ebp->ech->prev; */
387 /* ipoint = ebp->ech ; */
389 ic->lineno = ipoint->lineno;
390 ic->prev = ipoint->prev;
400 /* will add it to the very end */
410 /*-----------------------------------------------------------------*/
411 /* remiCodeFromeBBlock - remove an iCode from BBlock */
412 /*-----------------------------------------------------------------*/
414 remiCodeFromeBBlock (eBBlock * ebb, iCode * ic)
417 ic->prev->next = ic->next;
422 ic->next->prev = ic->prev;
427 /*-----------------------------------------------------------------*/
428 /* iCodeBreakDown : breakDown iCode chain to blocks */
429 /*-----------------------------------------------------------------*/
431 iCodeBreakDown (iCode * ic, int *count)
433 eBBlock **ebbs = NULL;
438 /* allocate for the first entry */
440 ebbs = Safe_calloc (1, sizeof (eBBlock **));
445 /* convert 2 block */
446 eBBlock *ebb = iCode2eBBlock (loop);
447 loop = ebb->ech->next;
449 ebb->ech->next = NULL; /* mark the end of this chain */
452 ebb->bbnum = *count; /* save this block number */
453 /* put it in the array */
454 ebbs[(*count)++] = ebb;
456 /* allocate for the next one. Remember to clear the new */
457 /* pointer at the end, that was created by realloc. */
459 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
463 /* if this one ends in a goto or a conditional */
464 /* branch then check if the block it is going */
465 /* to already exists, if yes then this could */
466 /* be a loop, add a preheader to the block it */
467 /* goes to if it does not already have one */
468 if (ebbs[(*count) - 1]->ech &&
469 (ebbs[(*count) - 1]->ech->op == GOTO ||
470 ebbs[(*count) - 1]->ech->op == IFX))
476 if (ebbs[(*count) - 1]->ech->op == GOTO)
477 label = IC_LABEL (ebbs[(*count) - 1]->ech);
478 else if (!(label = IC_TRUE (ebbs[(*count) - 1]->ech)))
479 label = IC_FALSE (ebbs[(*count) - 1]->ech);
481 if ((destBlock = eBBWithEntryLabel (ebbs, label, (*count))) &&
482 destBlock->preHeader == NULL &&
483 otherPathsPresent (ebbs, destBlock))
486 symbol *preHeaderLabel = newiTempPreheaderLabel ();
490 /* go thru all block replacing the entryLabel with new label */
491 /* till we reach the block , then we insert a new ebblock */
492 for (i = 0; i < (*count); i++)
494 if (ebbs[i] == destBlock)
496 replaceLabel (ebbs[i], label, preHeaderLabel);
501 /* if we have stopped at the block , allocate for an extra one */
503 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
507 /* then move the block down one count */
508 pBlock = ebbs[j = i];
509 for (i += 1; i < (*count); i++)
519 destBlock->preHeader = ebbs[j] = neweBBlock ();
521 ebbs[j]->entryLabel = preHeaderLabel;
522 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto (LABEL, preHeaderLabel);
523 ebbs[j]->sch->lineno = destBlock->sch->lineno;
534 /*-----------------------------------------------------------------*/
535 /* replaceSymBySym : - replace operand by operand in blocks */
536 /* replaces only left & right in blocks */
537 /*-----------------------------------------------------------------*/
539 replaceSymBySym (set * sset, operand * src, operand * dest)
544 /* for all blocks in the set do */
545 for (loop = sset; loop; loop = loop->next)
550 /* for all instructions in this block do */
551 for (ic = rBlock->sch; ic; ic = ic->next)
554 /* if we find usage */
555 if (ic->op == IFX && isOperandEqual (src, IC_COND (ic)))
557 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
558 IC_COND (ic) = operandFromOperand (dest);
559 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
563 if (isOperandEqual (IC_RIGHT (ic), src))
565 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
566 IC_RIGHT (ic) = operandFromOperand (dest);
567 IC_RIGHT (ic)->isaddr = 0;
568 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
571 if (isOperandEqual (IC_LEFT (ic), src))
573 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
574 if (POINTER_GET (ic) && IS_ITEMP (dest))
576 IC_LEFT (ic) = operandFromOperand (dest);
577 IC_LEFT (ic)->isaddr = 1;
581 IC_LEFT (ic) = operandFromOperand (dest);
582 IC_LEFT (ic)->isaddr = 0;
584 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
587 /* special case for pointer sets */
588 if (POINTER_SET (ic) &&
589 isOperandEqual (IC_RESULT (ic), src))
591 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
592 IC_RESULT (ic) = operandFromOperand (dest);
593 IC_RESULT (ic)->isaddr = 1;
594 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
600 /*-----------------------------------------------------------------*/
601 /* replaceLabel - replace reference to one label by another */
602 /*-----------------------------------------------------------------*/
604 replaceLabel (eBBlock * ebp, symbol * fromLbl, symbol * toLbl)
611 for (ic = ebp->sch; ic; ic = ic->next)
617 if (isSymbolEqual (IC_LABEL (ic), fromLbl))
618 IC_LABEL (ic) = toLbl;
622 if (IC_TRUE (ic) && isSymbolEqual (IC_TRUE (ic), fromLbl))
623 IC_TRUE (ic) = toLbl;
624 else if (isSymbolEqual (IC_FALSE (ic), fromLbl))
625 IC_FALSE (ic) = toLbl;
635 /*-----------------------------------------------------------------*/
636 /* iCodeFromeBBlock - convert basic block to iCode chain */
637 /*-----------------------------------------------------------------*/
639 iCodeFromeBBlock (eBBlock ** ebbs, int count)
642 iCode *ric = ebbs[0]->sch;
643 iCode *lic = ebbs[0]->ech;
645 for (; i < count; i++)
647 if (ebbs[i]->sch == NULL)
650 if (ebbs[i]->noPath &&
651 (ebbs[i]->entryLabel != entryLabel &&
652 ebbs[i]->entryLabel != returnLabel))
654 werror (W_CODE_UNREACH, ebbs[i]->sch->filename, ebbs[i]->sch->lineno);
658 lic->next = ebbs[i]->sch;
659 lic->next->prev = lic;
666 /*-----------------------------------------------------------------*/
667 /* otherPathsPresent - determines if there is a path from _entry */
668 /* to this block in a half constructed set of blocks */
669 /*-----------------------------------------------------------------*/
671 otherPathsPresent (eBBlock ** ebbs, eBBlock * this)
675 /* for all blocks preceding this block */
676 for (i = 0; i < this->bbnum; i++)
680 /* if there is a reference to the entry label of this block */
681 for (ic = ebbs[i]->sch; ic; ic = ic->next)
686 if (IC_LABEL (ic)->key == this->entryLabel->key)
693 if (IC_TRUE (ic)->key == this->entryLabel->key)
696 else if (IC_FALSE (ic)->key == this->entryLabel->key)
703 /* comes here means we have not found it yet */
704 /* in this case check if the previous block */
705 /* ends in a goto if it does then we have no */
706 /* path else we have a path */
707 if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
708 ebbs[this->bbnum - 1]->ech->op == GOTO)