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);
145 for (sym = hTabFirstItem (liveRanges, &k); sym;
146 sym = hTabNextItem (liveRanges, &k))
149 fprintf (file, "%s [k%d lr%d:%d so:%d]{ re%d rm%d}",
150 (sym->rname[0] ? sym->rname : sym->name),
152 sym->liveFrom, sym->liveTo,
154 sym->isreqv, sym->remat
158 printTypeChain (sym->type, file);
159 if (sym->usl.spillLoc)
161 fprintf (file, "}{ sir@ %s", sym->usl.spillLoc->rname);
164 fprintf (file, "\n");
170 /*-----------------------------------------------------------------*/
171 /* dumpEbbsToFileExt - writeall the basic blocks to a file */
172 /*-----------------------------------------------------------------*/
174 dumpEbbsToFileExt (int id, eBBlock ** ebbs, int count)
180 of=appendDumpFile(id);
185 for (i = 0; i < count; i++)
187 fprintf (of, "\n----------------------------------------------------------------\n");
188 fprintf (of, "Basic Block %s : loop Depth = %d noPath = %d , lastinLoop = %d\n",
189 ebbs[i]->entryLabel->name,
192 ebbs[i]->isLastInLoop);
193 fprintf (of, "\ndefines bitVector :");
194 bitVectDebugOn (ebbs[i]->defSet, of);
195 fprintf (of, "\nlocal defines bitVector :");
196 bitVectDebugOn (ebbs[i]->ldefs, of);
197 fprintf (of, "\npointers Set bitvector :");
198 bitVectDebugOn (ebbs[i]->ptrsSet, of);
199 if (ebbs[i]->isLastInLoop) {
200 fprintf (of, "\nInductions Set bitvector :");
201 bitVectDebugOn (ebbs[i]->linds, of);
203 fprintf (of, "\n----------------------------------------------------------------\n");
204 printiCChain (ebbs[i]->sch, of);
209 /*-----------------------------------------------------------------*/
210 /* iCode2eBBlock - converts a sequnce till label to a ebb */
211 /*-----------------------------------------------------------------*/
213 iCode2eBBlock (iCode * ic)
216 eBBlock *ebb = neweBBlock (); /* a llocate an entry */
218 /* put the first one unconditionally */
221 /* if this is a label then */
223 ebb->entryLabel = ic->argLabel.label;
226 sprintf (buffer, "_eBBlock%d", eBBNum++);
227 ebb->entryLabel = newSymbol (buffer, 1);
228 ebb->entryLabel->key = labelKey++;
233 ic->op == JUMPTABLE ||
240 if ((ic->next && ic->next->op == LABEL) ||
247 /* loop thru till we find one with a label */
248 for (loop = ic->next; loop; loop = loop->next)
251 /* if this is the last one */
254 /* if this is a function call */
255 if (loop->op == CALL || loop->op == PCALL)
259 FUNC_HASFCALL(currFunc->type) = 1;
262 /* if the next one is a label */
263 /* if this is a goto or ifx */
264 if (loop->next->op == LABEL ||
266 loop->op == JUMPTABLE ||
271 /* mark the end of the chain */
277 /*-----------------------------------------------------------------*/
278 /* eBBWithEntryLabel - finds the basic block with the entry label */
279 /*-----------------------------------------------------------------*/
281 eBBWithEntryLabel (eBBlock ** ebbs, symbol * eLabel, int count)
285 for (i = 0; i < count; i++)
287 if (isSymbolEqual (ebbs[i]->entryLabel, eLabel))
295 /*-----------------------------------------------------------------*/
296 /* ifFromIs - will return 1 if the from block matches this */
297 /*-----------------------------------------------------------------*/
298 DEFSETFUNC (ifFromIs)
301 V_ARG (eBBlock *, this);
303 if (ep->from == this)
310 /*-----------------------------------------------------------------*/
311 /* edgesTo - returns a set of edges with to == supplied value */
312 /*-----------------------------------------------------------------*/
314 edgesTo (eBBlock * to)
319 for (loop = setFirstItem (graphEdges); loop; loop = setNextItem (graphEdges))
320 if (loop->to == to && !loop->from->noPath)
321 addSet (&result, loop->from);
327 /*-----------------------------------------------------------------*/
328 /* addiCodeToeBBlock - will add an iCode to the end of a block */
329 /*-----------------------------------------------------------------*/
331 addiCodeToeBBlock (eBBlock * ebp, iCode * ic, iCode * ip)
333 ic->prev = ic->next = NULL;
334 /* if the insert point is given */
337 ic->lineno = ip->lineno;
348 /* if the block has no instructions */
349 if (ebp->ech == NULL)
351 ebp->sch = ebp->ech = ic;
356 /* if the last instruction is a goto */
357 /* we add it just before the goto */
358 if (ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE
359 || ebp->ech->op == RETURN)
361 ic->lineno = ebp->ech->lineno;
362 ic->prev = ebp->ech->prev;
365 if (!ic->prev) /* was the last only on in the block */
372 /* if the last one was a ifx statement we check to see */
373 /* if the condition was defined in the previous instruction */
374 /* if this is true then we put it before the condition else */
375 /* we put it before if, this is to reduce register pressure, */
376 /* we don't have to hold condition too long in a register */
377 if (ebp->ech->op == IFX)
381 /* if ( !ebp->ech->prev ) */
382 /* ipoint = ebp->ech ; */
384 /* if (!IC_RESULT(ebp->ech->prev)) */
385 /* ipoint = ebp->ech ; */
387 /* if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
388 /* ipoint = ebp->ech->prev; */
390 /* ipoint = ebp->ech ; */
392 ic->lineno = ipoint->lineno;
393 ic->prev = ipoint->prev;
403 /* will add it to the very end */
413 /*-----------------------------------------------------------------*/
414 /* remiCodeFromeBBlock - remove an iCode from BBlock */
415 /*-----------------------------------------------------------------*/
417 remiCodeFromeBBlock (eBBlock * ebb, iCode * ic)
420 ic->prev->next = ic->next;
425 ic->next->prev = ic->prev;
430 /*-----------------------------------------------------------------*/
431 /* iCodeBreakDown : breakDown iCode chain to blocks */
432 /*-----------------------------------------------------------------*/
434 iCodeBreakDown (iCode * ic, int *count)
436 eBBlock **ebbs = NULL;
441 /* allocate for the first entry */
443 ebbs = Safe_alloc (sizeof (eBBlock **));
448 /* convert 2 block */
449 eBBlock *ebb = iCode2eBBlock (loop);
450 loop = ebb->ech->next;
452 ebb->ech->next = NULL; /* mark the end of this chain */
455 ebb->bbnum = *count; /* save this block number */
456 /* put it in the array */
457 ebbs[(*count)++] = ebb;
459 /* allocate for the next one. Remember to clear the new */
460 /* pointer at the end, that was created by realloc. */
462 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
466 /* if this one ends in a goto or a conditional */
467 /* branch then check if the block it is going */
468 /* to already exists, if yes then this could */
469 /* be a loop, add a preheader to the block it */
470 /* goes to if it does not already have one */
471 if (ebbs[(*count) - 1]->ech &&
472 (ebbs[(*count) - 1]->ech->op == GOTO ||
473 ebbs[(*count) - 1]->ech->op == IFX))
479 if (ebbs[(*count) - 1]->ech->op == GOTO)
480 label = IC_LABEL (ebbs[(*count) - 1]->ech);
481 else if (!(label = IC_TRUE (ebbs[(*count) - 1]->ech)))
482 label = IC_FALSE (ebbs[(*count) - 1]->ech);
484 if ((destBlock = eBBWithEntryLabel (ebbs, label, (*count))) &&
485 destBlock->preHeader == NULL &&
486 otherPathsPresent (ebbs, destBlock))
489 symbol *preHeaderLabel = newiTempPreheaderLabel ();
493 /* go thru all block replacing the entryLabel with new label */
494 /* till we reach the block , then we insert a new ebblock */
495 for (i = 0; i < (*count); i++)
497 if (ebbs[i] == destBlock)
499 replaceLabel (ebbs[i], label, preHeaderLabel);
504 /* if we have stopped at the block , allocate for an extra one */
506 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
510 /* then move the block down one count */
511 pBlock = ebbs[j = i];
512 for (i += 1; i < (*count); i++)
522 destBlock->preHeader = ebbs[j] = neweBBlock ();
524 ebbs[j]->entryLabel = preHeaderLabel;
525 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto (LABEL, preHeaderLabel);
526 ebbs[j]->sch->lineno = destBlock->sch->lineno;
537 /*-----------------------------------------------------------------*/
538 /* replaceSymBySym : - replace operand by operand in blocks */
539 /* replaces only left & right in blocks */
540 /*-----------------------------------------------------------------*/
542 replaceSymBySym (set * sset, operand * src, operand * dest)
547 /* for all blocks in the set do */
548 for (loop = sset; loop; loop = loop->next)
553 /* for all instructions in this block do */
554 for (ic = rBlock->sch; ic; ic = ic->next)
557 /* if we find usage */
558 if (ic->op == IFX && isOperandEqual (src, IC_COND (ic)))
560 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
561 IC_COND (ic) = operandFromOperand (dest);
562 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
566 if (isOperandEqual (IC_RIGHT (ic), src))
568 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
569 IC_RIGHT (ic) = operandFromOperand (dest);
570 IC_RIGHT (ic)->isaddr = 0;
571 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
574 if (isOperandEqual (IC_LEFT (ic), src))
576 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
577 if (POINTER_GET (ic) && IS_ITEMP (dest))
579 IC_LEFT (ic) = operandFromOperand (dest);
580 IC_LEFT (ic)->isaddr = 1;
584 IC_LEFT (ic) = operandFromOperand (dest);
585 IC_LEFT (ic)->isaddr = 0;
587 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
590 /* special case for pointer sets */
591 if (POINTER_SET (ic) &&
592 isOperandEqual (IC_RESULT (ic), src))
594 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
595 IC_RESULT (ic) = operandFromOperand (dest);
596 IC_RESULT (ic)->isaddr = 1;
597 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
603 /*-----------------------------------------------------------------*/
604 /* replaceLabel - replace reference to one label by another */
605 /*-----------------------------------------------------------------*/
607 replaceLabel (eBBlock * ebp, symbol * fromLbl, symbol * toLbl)
614 for (ic = ebp->sch; ic; ic = ic->next)
620 if (isSymbolEqual (IC_LABEL (ic), fromLbl))
621 IC_LABEL (ic) = toLbl;
625 if (IC_TRUE (ic) && isSymbolEqual (IC_TRUE (ic), fromLbl))
626 IC_TRUE (ic) = toLbl;
627 else if (isSymbolEqual (IC_FALSE (ic), fromLbl))
628 IC_FALSE (ic) = toLbl;
638 /*-----------------------------------------------------------------*/
639 /* iCodeFromeBBlock - convert basic block to iCode chain */
640 /*-----------------------------------------------------------------*/
642 iCodeFromeBBlock (eBBlock ** ebbs, int count)
645 iCode *ric = ebbs[0]->sch;
646 iCode *lic = ebbs[0]->ech;
648 for (; i < count; i++)
650 if (ebbs[i]->sch == NULL)
653 if (ebbs[i]->noPath &&
654 (ebbs[i]->entryLabel != entryLabel &&
655 ebbs[i]->entryLabel != returnLabel))
657 werror (W_CODE_UNREACH, ebbs[i]->sch->filename, ebbs[i]->sch->lineno);
661 lic->next = ebbs[i]->sch;
662 lic->next->prev = lic;
669 /*-----------------------------------------------------------------*/
670 /* otherPathsPresent - determines if there is a path from _entry */
671 /* to this block in a half constructed set of blocks */
672 /*-----------------------------------------------------------------*/
674 otherPathsPresent (eBBlock ** ebbs, eBBlock * this)
678 /* for all blocks preceding this block */
679 for (i = 0; i < this->bbnum; i++)
683 /* if there is a reference to the entry label of this block */
684 for (ic = ebbs[i]->sch; ic; ic = ic->next)
689 if (IC_LABEL (ic)->key == this->entryLabel->key)
696 if (IC_TRUE (ic)->key == this->entryLabel->key)
699 else if (IC_FALSE (ic)->key == this->entryLabel->key)
706 /* comes here means we have not found it yet */
707 /* in this case check if the previous block */
708 /* ends in a goto if it does then we have no */
709 /* path else we have a path */
710 if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
711 ebbs[this->bbnum - 1]->ech->op == GOTO)