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 strcpy (scratchFileName, srcFileName);
106 strcat (scratchFileName, dumpFilesPtr->ext);
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 = %d noPath = %d , lastinLoop = %d\n",
192 ebbs[i]->entryLabel->name,
195 ebbs[i]->isLastInLoop);
196 fprintf (of, "\ndefines bitVector :");
197 bitVectDebugOn (ebbs[i]->defSet, of);
198 fprintf (of, "\nlocal defines bitVector :");
199 bitVectDebugOn (ebbs[i]->ldefs, of);
200 fprintf (of, "\npointers Set bitvector :");
201 bitVectDebugOn (ebbs[i]->ptrsSet, of);
202 if (ebbs[i]->isLastInLoop) {
203 fprintf (of, "\nInductions Set bitvector :");
204 bitVectDebugOn (ebbs[i]->linds, of);
206 fprintf (of, "\n----------------------------------------------------------------\n");
207 printiCChain (ebbs[i]->sch, of);
212 /*-----------------------------------------------------------------*/
213 /* iCode2eBBlock - converts a sequnce till label to a ebb */
214 /*-----------------------------------------------------------------*/
216 iCode2eBBlock (iCode * ic)
219 eBBlock *ebb = neweBBlock (); /* a llocate an entry */
221 /* put the first one unconditionally */
224 /* if this is a label then */
226 ebb->entryLabel = ic->argLabel.label;
229 sprintf (buffer, "_eBBlock%d", eBBNum++);
230 ebb->entryLabel = newSymbol (buffer, 1);
231 ebb->entryLabel->key = labelKey++;
236 ic->op == JUMPTABLE ||
243 if ((ic->next && ic->next->op == LABEL) ||
250 /* loop thru till we find one with a label */
251 for (loop = ic->next; loop; loop = loop->next)
254 /* if this is the last one */
257 /* if this is a function call */
258 if (loop->op == CALL || loop->op == PCALL)
262 FUNC_HASFCALL(currFunc->type) = 1;
265 /* if the next one is a label */
266 /* if this is a goto or ifx */
267 if (loop->next->op == LABEL ||
269 loop->op == JUMPTABLE ||
274 /* mark the end of the chain */
280 /*-----------------------------------------------------------------*/
281 /* eBBWithEntryLabel - finds the basic block with the entry label */
282 /*-----------------------------------------------------------------*/
284 eBBWithEntryLabel (eBBlock ** ebbs, symbol * eLabel, int count)
288 for (i = 0; i < count; i++)
290 if (isSymbolEqual (ebbs[i]->entryLabel, eLabel))
298 /*-----------------------------------------------------------------*/
299 /* ifFromIs - will return 1 if the from block matches this */
300 /*-----------------------------------------------------------------*/
301 DEFSETFUNC (ifFromIs)
304 V_ARG (eBBlock *, this);
306 if (ep->from == this)
313 /*-----------------------------------------------------------------*/
314 /* edgesTo - returns a set of edges with to == supplied value */
315 /*-----------------------------------------------------------------*/
317 edgesTo (eBBlock * to)
322 for (loop = setFirstItem (graphEdges); loop; loop = setNextItem (graphEdges))
323 if (loop->to == to && !loop->from->noPath)
324 addSet (&result, loop->from);
330 /*-----------------------------------------------------------------*/
331 /* addiCodeToeBBlock - will add an iCode to the end of a block */
332 /*-----------------------------------------------------------------*/
334 addiCodeToeBBlock (eBBlock * ebp, iCode * ic, iCode * ip)
336 ic->prev = ic->next = NULL;
337 /* if the insert point is given */
340 ic->lineno = ip->lineno;
351 /* if the block has no instructions */
352 if (ebp->ech == NULL)
354 ebp->sch = ebp->ech = ic;
359 /* if the last instruction is a goto */
360 /* we add it just before the goto */
361 if (ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE
362 || ebp->ech->op == RETURN)
364 ic->lineno = ebp->ech->lineno;
365 ic->prev = ebp->ech->prev;
368 if (!ic->prev) /* was the last only on in the block */
375 /* if the last one was a ifx statement we check to see */
376 /* if the condition was defined in the previous instruction */
377 /* if this is true then we put it before the condition else */
378 /* we put it before if, this is to reduce register pressure, */
379 /* we don't have to hold condition too long in a register */
380 if (ebp->ech->op == IFX)
384 /* if ( !ebp->ech->prev ) */
385 /* ipoint = ebp->ech ; */
387 /* if (!IC_RESULT(ebp->ech->prev)) */
388 /* ipoint = ebp->ech ; */
390 /* if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
391 /* ipoint = ebp->ech->prev; */
393 /* ipoint = ebp->ech ; */
395 ic->lineno = ipoint->lineno;
396 ic->prev = ipoint->prev;
406 /* will add it to the very end */
416 /*-----------------------------------------------------------------*/
417 /* remiCodeFromeBBlock - remove an iCode from BBlock */
418 /*-----------------------------------------------------------------*/
420 remiCodeFromeBBlock (eBBlock * ebb, iCode * ic)
423 ic->prev->next = ic->next;
428 ic->next->prev = ic->prev;
433 /*-----------------------------------------------------------------*/
434 /* iCodeBreakDown : breakDown iCode chain to blocks */
435 /*-----------------------------------------------------------------*/
437 iCodeBreakDown (iCode * ic, int *count)
439 eBBlock **ebbs = NULL;
444 /* allocate for the first entry */
446 ebbs = Safe_alloc (sizeof (eBBlock **));
451 /* convert 2 block */
452 eBBlock *ebb = iCode2eBBlock (loop);
453 loop = ebb->ech->next;
455 ebb->ech->next = NULL; /* mark the end of this chain */
458 ebb->bbnum = *count; /* save this block number */
459 /* put it in the array */
460 ebbs[(*count)++] = ebb;
462 /* allocate for the next one. Remember to clear the new */
463 /* pointer at the end, that was created by realloc. */
465 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
469 /* if this one ends in a goto or a conditional */
470 /* branch then check if the block it is going */
471 /* to already exists, if yes then this could */
472 /* be a loop, add a preheader to the block it */
473 /* goes to if it does not already have one */
474 if (ebbs[(*count) - 1]->ech &&
475 (ebbs[(*count) - 1]->ech->op == GOTO ||
476 ebbs[(*count) - 1]->ech->op == IFX))
482 if (ebbs[(*count) - 1]->ech->op == GOTO)
483 label = IC_LABEL (ebbs[(*count) - 1]->ech);
484 else if (!(label = IC_TRUE (ebbs[(*count) - 1]->ech)))
485 label = IC_FALSE (ebbs[(*count) - 1]->ech);
487 if ((destBlock = eBBWithEntryLabel (ebbs, label, (*count))) &&
488 destBlock->preHeader == NULL &&
489 otherPathsPresent (ebbs, destBlock))
492 symbol *preHeaderLabel = newiTempPreheaderLabel ();
496 /* go thru all block replacing the entryLabel with new label */
497 /* till we reach the block , then we insert a new ebblock */
498 for (i = 0; i < (*count); i++)
500 if (ebbs[i] == destBlock)
502 replaceLabel (ebbs[i], label, preHeaderLabel);
507 /* if we have stopped at the block , allocate for an extra one */
509 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
513 /* then move the block down one count */
514 pBlock = ebbs[j = i];
515 for (i += 1; i < (*count); i++)
525 destBlock->preHeader = ebbs[j] = neweBBlock ();
527 ebbs[j]->entryLabel = preHeaderLabel;
528 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto (LABEL, preHeaderLabel);
529 ebbs[j]->sch->lineno = destBlock->sch->lineno;
540 /*-----------------------------------------------------------------*/
541 /* replaceSymBySym : - replace operand by operand in blocks */
542 /* replaces only left & right in blocks */
543 /*-----------------------------------------------------------------*/
545 replaceSymBySym (set * sset, operand * src, operand * dest)
550 /* for all blocks in the set do */
551 for (loop = sset; loop; loop = loop->next)
556 /* for all instructions in this block do */
557 for (ic = rBlock->sch; ic; ic = ic->next)
560 /* if we find usage */
561 if (ic->op == IFX && isOperandEqual (src, IC_COND (ic)))
563 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
564 IC_COND (ic) = operandFromOperand (dest);
565 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
569 if (isOperandEqual (IC_RIGHT (ic), src))
571 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
572 IC_RIGHT (ic) = operandFromOperand (dest);
573 IC_RIGHT (ic)->isaddr = 0;
574 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
577 if (isOperandEqual (IC_LEFT (ic), src))
579 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
580 if (POINTER_GET (ic) && IS_ITEMP (dest))
582 IC_LEFT (ic) = operandFromOperand (dest);
583 IC_LEFT (ic)->isaddr = 1;
587 IC_LEFT (ic) = operandFromOperand (dest);
588 IC_LEFT (ic)->isaddr = 0;
590 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
593 /* special case for pointer sets */
594 if (POINTER_SET (ic) &&
595 isOperandEqual (IC_RESULT (ic), src))
597 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
598 IC_RESULT (ic) = operandFromOperand (dest);
599 IC_RESULT (ic)->isaddr = 1;
600 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
606 /*-----------------------------------------------------------------*/
607 /* replaceLabel - replace reference to one label by another */
608 /*-----------------------------------------------------------------*/
610 replaceLabel (eBBlock * ebp, symbol * fromLbl, symbol * toLbl)
617 for (ic = ebp->sch; ic; ic = ic->next)
623 if (isSymbolEqual (IC_LABEL (ic), fromLbl))
624 IC_LABEL (ic) = toLbl;
628 if (IC_TRUE (ic) && isSymbolEqual (IC_TRUE (ic), fromLbl))
629 IC_TRUE (ic) = toLbl;
630 else if (isSymbolEqual (IC_FALSE (ic), fromLbl))
631 IC_FALSE (ic) = toLbl;
641 /*-----------------------------------------------------------------*/
642 /* iCodeFromeBBlock - convert basic block to iCode chain */
643 /*-----------------------------------------------------------------*/
645 iCodeFromeBBlock (eBBlock ** ebbs, int count)
648 iCode *ric = ebbs[0]->sch;
649 iCode *lic = ebbs[0]->ech;
651 for (; i < count; i++)
653 if (ebbs[i]->sch == NULL)
656 if (ebbs[i]->noPath &&
657 (ebbs[i]->entryLabel != entryLabel &&
658 ebbs[i]->entryLabel != returnLabel))
660 werror (W_CODE_UNREACH, ebbs[i]->sch->filename, ebbs[i]->sch->lineno);
664 lic->next = ebbs[i]->sch;
665 lic->next->prev = lic;
672 /*-----------------------------------------------------------------*/
673 /* otherPathsPresent - determines if there is a path from _entry */
674 /* to this block in a half constructed set of blocks */
675 /*-----------------------------------------------------------------*/
677 otherPathsPresent (eBBlock ** ebbs, eBBlock * this)
681 /* for all blocks preceding this block */
682 for (i = 0; i < this->bbnum; i++)
686 /* if there is a reference to the entry label of this block */
687 for (ic = ebbs[i]->sch; ic; ic = ic->next)
692 if (IC_LABEL (ic)->key == this->entryLabel->key)
699 if (IC_TRUE (ic)->key == this->entryLabel->key)
702 else if (IC_FALSE (ic)->key == this->entryLabel->key)
709 /* comes here means we have not found it yet */
710 /* in this case check if the previous block */
711 /* ends in a goto if it does then we have no */
712 /* path else we have a path */
713 if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
714 ebbs[this->bbnum - 1]->ech->op == GOTO)