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 /* appendDumpFile - if not already created, create the dump file */
88 /*-----------------------------------------------------------------*/
89 FILE *appendDumpFile (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: appendDumpFile: 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);
124 //dprintf ("closed %s\n", dumpFilesPtr->ext);
129 /*-----------------------------------------------------------------*/
130 /* dumpLiveRanges - dump liverange information into a file */
131 /*-----------------------------------------------------------------*/
133 dumpLiveRanges (int id, hTab * liveRanges)
140 file=appendDumpFile(id);
146 fprintf(file,"------------- Func %s -------------\n",currFunc->name);
147 for (sym = hTabFirstItem (liveRanges, &k); sym;
148 sym = hTabNextItem (liveRanges, &k))
151 fprintf (file, "%s [k%d lr%d:%d so:%d]{ re%d rm%d}",
152 (sym->rname[0] ? sym->rname : sym->name),
154 sym->liveFrom, sym->liveTo,
156 sym->isreqv, sym->remat
160 printTypeChain (sym->type, file);
161 if (sym->usl.spillLoc)
163 fprintf (file, "}{ sir@ %s", sym->usl.spillLoc->rname);
165 fprintf (file, "} clashes with ");
166 bitVectDebugOn(sym->clashes,file);
167 fprintf (file, "\n");
173 /*-----------------------------------------------------------------*/
174 /* dumpEbbsToFileExt - writeall the basic blocks to a file */
175 /*-----------------------------------------------------------------*/
177 dumpEbbsToFileExt (int id, eBBlock ** ebbs, int count)
183 of=appendDumpFile(id);
188 for (i = 0; i < count; i++)
190 fprintf (of, "\n----------------------------------------------------------------\n");
191 fprintf (of, "Basic Block %s : loop Depth(lSeq) = %d(%d) noPath = %d , lastinLoop = %d\n",
192 ebbs[i]->entryLabel->name,
195 ebbs[i]->depth) ? findLoopEndSeq(ebbs[i]->partOfLoop) : 0,
197 ebbs[i]->isLastInLoop);
198 fprintf (of, "\ndefines bitVector :");
199 bitVectDebugOn (ebbs[i]->defSet, of);
200 fprintf (of, "\nlocal defines bitVector :");
201 bitVectDebugOn (ebbs[i]->ldefs, of);
202 fprintf (of, "\npointers Set bitvector :");
203 bitVectDebugOn (ebbs[i]->ptrsSet, of);
204 if (ebbs[i]->isLastInLoop) {
205 fprintf (of, "\nInductions Set bitvector :");
206 bitVectDebugOn (ebbs[i]->linds, of);
208 fprintf (of, "\n----------------------------------------------------------------\n");
209 printiCChain (ebbs[i]->sch, of);
214 /*-----------------------------------------------------------------*/
215 /* iCode2eBBlock - converts a sequnce till label to a ebb */
216 /*-----------------------------------------------------------------*/
218 iCode2eBBlock (iCode * ic)
221 eBBlock *ebb = neweBBlock (); /* a llocate an entry */
223 /* put the first one unconditionally */
226 /* if this is a label then */
228 ebb->entryLabel = ic->argLabel.label;
231 SNPRINTF (buffer, sizeof(buffer), "_eBBlock%d", eBBNum++);
232 ebb->entryLabel = newSymbol (buffer, 1);
233 ebb->entryLabel->key = labelKey++;
238 ic->op == JUMPTABLE ||
245 if ((ic->next && ic->next->op == LABEL) ||
252 /* loop thru till we find one with a label */
253 for (loop = ic->next; loop; loop = loop->next)
256 /* if this is the last one */
259 /* if this is a function call */
260 if (loop->op == CALL || loop->op == PCALL)
264 FUNC_HASFCALL(currFunc->type) = 1;
267 /* if the next one is a label */
268 /* if this is a goto or ifx */
269 if (loop->next->op == LABEL ||
271 loop->op == JUMPTABLE ||
276 /* mark the end of the chain */
282 /*-----------------------------------------------------------------*/
283 /* eBBWithEntryLabel - finds the basic block with the entry label */
284 /*-----------------------------------------------------------------*/
286 eBBWithEntryLabel (eBBlock ** ebbs, symbol * eLabel, int count)
290 for (i = 0; i < count; i++)
292 if (isSymbolEqual (ebbs[i]->entryLabel, eLabel))
300 /*-----------------------------------------------------------------*/
301 /* ifFromIs - will return 1 if the from block matches this */
302 /*-----------------------------------------------------------------*/
303 DEFSETFUNC (ifFromIs)
306 V_ARG (eBBlock *, this);
308 if (ep->from == this)
315 /*-----------------------------------------------------------------*/
316 /* edgesTo - returns a set of edges with to == supplied value */
317 /*-----------------------------------------------------------------*/
319 edgesTo (eBBlock * to)
324 for (loop = setFirstItem (graphEdges); loop; loop = setNextItem (graphEdges))
325 if (loop->to == to && !loop->from->noPath)
326 addSet (&result, loop->from);
332 /*-----------------------------------------------------------------*/
333 /* addiCodeToeBBlock - will add an iCode to the end of a block */
334 /*-----------------------------------------------------------------*/
336 addiCodeToeBBlock (eBBlock * ebp, iCode * ic, iCode * ip)
338 ic->prev = ic->next = NULL;
339 /* if the insert point is given */
342 ic->lineno = ip->lineno;
353 /* if the block has no instructions */
354 if (ebp->ech == NULL)
356 ebp->sch = ebp->ech = ic;
361 /* if the last instruction is a goto */
362 /* we add it just before the goto */
363 if (ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE
364 || ebp->ech->op == RETURN)
366 ic->lineno = ebp->ech->lineno;
367 ic->prev = ebp->ech->prev;
370 if (!ic->prev) /* was the last only on in the block */
377 /* if the last one was a ifx statement we check to see */
378 /* if the condition was defined in the previous instruction */
379 /* if this is true then we put it before the condition else */
380 /* we put it before if, this is to reduce register pressure, */
381 /* we don't have to hold condition too long in a register */
382 if (ebp->ech->op == IFX)
386 /* if ( !ebp->ech->prev ) */
387 /* ipoint = ebp->ech ; */
389 /* if (!IC_RESULT(ebp->ech->prev)) */
390 /* ipoint = ebp->ech ; */
392 /* if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
393 /* ipoint = ebp->ech->prev; */
395 /* ipoint = ebp->ech ; */
397 ic->lineno = ipoint->lineno;
398 ic->prev = ipoint->prev;
408 /* will add it to the very end */
418 /*-----------------------------------------------------------------*/
419 /* remiCodeFromeBBlock - remove an iCode from BBlock */
420 /*-----------------------------------------------------------------*/
422 remiCodeFromeBBlock (eBBlock * ebb, iCode * ic)
424 wassert (ic->seq>=ebb->fSeq && ic->seq<=ebb->lSeq);
426 ic->prev->next = ic->next;
431 ic->next->prev = ic->prev;
436 /*-----------------------------------------------------------------*/
437 /* iCodeBreakDown : breakDown iCode chain to blocks */
438 /*-----------------------------------------------------------------*/
440 iCodeBreakDown (iCode * ic, int *count)
442 eBBlock **ebbs = NULL;
447 /* allocate for the first entry */
449 ebbs = Safe_alloc (sizeof (eBBlock **));
454 /* convert 2 block */
455 eBBlock *ebb = iCode2eBBlock (loop);
456 loop = ebb->ech->next;
458 ebb->ech->next = NULL; /* mark the end of this chain */
461 ebb->bbnum = *count; /* save this block number */
462 /* put it in the array */
463 ebbs[(*count)++] = ebb;
465 /* allocate for the next one. Remember to clear the new */
466 /* pointer at the end, that was created by realloc. */
468 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
472 /* if this one ends in a goto or a conditional */
473 /* branch then check if the block it is going */
474 /* to already exists, if yes then this could */
475 /* be a loop, add a preheader to the block it */
476 /* goes to if it does not already have one */
477 if (ebbs[(*count) - 1]->ech &&
478 (ebbs[(*count) - 1]->ech->op == GOTO ||
479 ebbs[(*count) - 1]->ech->op == IFX))
485 if (ebbs[(*count) - 1]->ech->op == GOTO)
486 label = IC_LABEL (ebbs[(*count) - 1]->ech);
487 else if (!(label = IC_TRUE (ebbs[(*count) - 1]->ech)))
488 label = IC_FALSE (ebbs[(*count) - 1]->ech);
490 if ((destBlock = eBBWithEntryLabel (ebbs, label, (*count))) &&
491 destBlock->preHeader == NULL &&
492 otherPathsPresent (ebbs, destBlock))
495 symbol *preHeaderLabel = newiTempPreheaderLabel ();
499 /* go thru all block replacing the entryLabel with new label */
500 /* till we reach the block , then we insert a new ebblock */
501 for (i = 0; i < (*count); i++)
503 if (ebbs[i] == destBlock)
505 replaceLabel (ebbs[i], label, preHeaderLabel);
510 /* if we have stopped at the block , allocate for an extra one */
512 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
516 /* then move the block down one count */
517 pBlock = ebbs[j = i];
518 for (i += 1; i < (*count); i++)
528 destBlock->preHeader = ebbs[j] = neweBBlock ();
530 ebbs[j]->entryLabel = preHeaderLabel;
531 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto (LABEL, preHeaderLabel);
532 ebbs[j]->sch->lineno = destBlock->sch->lineno;
543 /*-----------------------------------------------------------------*/
544 /* replaceSymBySym : - replace operand by operand in blocks */
545 /* replaces only left & right in blocks */
546 /*-----------------------------------------------------------------*/
548 replaceSymBySym (set * sset, operand * src, operand * dest)
553 /* for all blocks in the set do */
554 for (loop = sset; loop; loop = loop->next)
559 /* for all instructions in this block do */
560 for (ic = rBlock->sch; ic; ic = ic->next)
563 /* if we find usage */
564 if (ic->op == IFX && isOperandEqual (src, IC_COND (ic)))
566 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
567 IC_COND (ic) = operandFromOperand (dest);
568 OP_USES_SET ((dest), bitVectSetBit (OP_USES (dest), ic->key));
572 if (isOperandEqual (IC_RIGHT (ic), src))
574 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
575 IC_RIGHT (ic) = operandFromOperand (dest);
576 IC_RIGHT (ic)->isaddr = 0;
577 OP_USES_SET ((dest), bitVectSetBit (OP_USES (dest), ic->key));
580 if (isOperandEqual (IC_LEFT (ic), src))
582 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
583 if (POINTER_GET (ic) && IS_ITEMP (dest))
585 IC_LEFT (ic) = operandFromOperand (dest);
586 IC_LEFT (ic)->isaddr = 1;
590 IC_LEFT (ic) = operandFromOperand (dest);
591 IC_LEFT (ic)->isaddr = 0;
593 OP_USES_SET ((dest), bitVectSetBit (OP_USES (dest), ic->key));
596 /* special case for pointer sets */
597 if (POINTER_SET (ic) &&
598 isOperandEqual (IC_RESULT (ic), src))
600 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
601 IC_RESULT (ic) = operandFromOperand (dest);
602 IC_RESULT (ic)->isaddr = 1;
603 OP_USES_SET ((dest), bitVectSetBit (OP_USES (dest), ic->key));
609 /*-----------------------------------------------------------------*/
610 /* replaceLabel - replace reference to one label by another */
611 /*-----------------------------------------------------------------*/
613 replaceLabel (eBBlock * ebp, symbol * fromLbl, symbol * toLbl)
620 for (ic = ebp->sch; ic; ic = ic->next)
626 if (isSymbolEqual (IC_LABEL (ic), fromLbl))
627 IC_LABEL (ic) = toLbl;
631 if (IC_TRUE (ic) && isSymbolEqual (IC_TRUE (ic), fromLbl))
632 IC_TRUE (ic) = toLbl;
633 else if (isSymbolEqual (IC_FALSE (ic), fromLbl))
634 IC_FALSE (ic) = toLbl;
644 /*-----------------------------------------------------------------*/
645 /* iCodeFromeBBlock - convert basic block to iCode chain */
646 /*-----------------------------------------------------------------*/
648 iCodeFromeBBlock (eBBlock ** ebbs, int count)
651 iCode *ric = ebbs[0]->sch;
652 iCode *lic = ebbs[0]->ech;
654 for (; i < count; i++)
656 if (ebbs[i]->sch == NULL)
659 if (ebbs[i]->noPath &&
660 (ebbs[i]->entryLabel != entryLabel &&
661 ebbs[i]->entryLabel != returnLabel))
663 werror (W_CODE_UNREACH, ebbs[i]->sch->filename, ebbs[i]->sch->lineno);
667 lic->next = ebbs[i]->sch;
668 lic->next->prev = lic;
675 /*-----------------------------------------------------------------*/
676 /* otherPathsPresent - determines if there is a path from _entry */
677 /* to this block in a half constructed set of blocks */
678 /*-----------------------------------------------------------------*/
680 otherPathsPresent (eBBlock ** ebbs, eBBlock * this)
684 /* for all blocks preceding this block */
685 for (i = 0; i < this->bbnum; i++)
689 /* if there is a reference to the entry label of this block */
690 for (ic = ebbs[i]->sch; ic; ic = ic->next)
695 if (IC_LABEL (ic)->key == this->entryLabel->key)
702 if (IC_TRUE (ic)->key == this->entryLabel->key)
705 else if (IC_FALSE (ic)->key == this->entryLabel->key)
712 /* comes here means we have not found it yet */
713 /* in this case check if the previous block */
714 /* ends in a goto if it does then we have no */
715 /* path else we have a path */
716 if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
717 ebbs[this->bbnum - 1]->ech->op == GOTO)