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,
194 ebbs[i]->depth ? findLoopEndSeq(ebbs[i]->partOfLoop) : 0,
196 ebbs[i]->isLastInLoop);
197 fprintf (of, "\ndefines bitVector :");
198 bitVectDebugOn (ebbs[i]->defSet, of);
199 fprintf (of, "\nlocal defines bitVector :");
200 bitVectDebugOn (ebbs[i]->ldefs, of);
201 fprintf (of, "\npointers Set bitvector :");
202 bitVectDebugOn (ebbs[i]->ptrsSet, of);
203 if (ebbs[i]->isLastInLoop) {
204 fprintf (of, "\nInductions Set bitvector :");
205 bitVectDebugOn (ebbs[i]->linds, of);
207 fprintf (of, "\n----------------------------------------------------------------\n");
208 printiCChain (ebbs[i]->sch, of);
213 /*-----------------------------------------------------------------*/
214 /* iCode2eBBlock - converts a sequnce till label to a ebb */
215 /*-----------------------------------------------------------------*/
217 iCode2eBBlock (iCode * ic)
220 eBBlock *ebb = neweBBlock (); /* a llocate an entry */
222 /* put the first one unconditionally */
225 /* if this is a label then */
227 ebb->entryLabel = ic->argLabel.label;
230 SNPRINTF (buffer, sizeof(buffer), "_eBBlock%d", eBBNum++);
231 ebb->entryLabel = newSymbol (buffer, 1);
232 ebb->entryLabel->key = labelKey++;
237 ic->op == JUMPTABLE ||
244 if ((ic->next && ic->next->op == LABEL) ||
251 /* loop thru till we find one with a label */
252 for (loop = ic->next; loop; loop = loop->next)
255 /* if this is the last one */
258 /* if this is a function call */
259 if (loop->op == CALL || loop->op == PCALL)
263 FUNC_HASFCALL(currFunc->type) = 1;
266 /* if the next one is a label */
267 /* if this is a goto or ifx */
268 if (loop->next->op == LABEL ||
270 loop->op == JUMPTABLE ||
275 /* mark the end of the chain */
281 /*-----------------------------------------------------------------*/
282 /* eBBWithEntryLabel - finds the basic block with the entry label */
283 /*-----------------------------------------------------------------*/
285 eBBWithEntryLabel (eBBlock ** ebbs, symbol * eLabel, int count)
289 for (i = 0; i < count; i++)
291 if (isSymbolEqual (ebbs[i]->entryLabel, eLabel))
299 /*-----------------------------------------------------------------*/
300 /* ifFromIs - will return 1 if the from block matches this */
301 /*-----------------------------------------------------------------*/
302 DEFSETFUNC (ifFromIs)
305 V_ARG (eBBlock *, this);
307 if (ep->from == this)
314 /*-----------------------------------------------------------------*/
315 /* edgesTo - returns a set of edges with to == supplied value */
316 /*-----------------------------------------------------------------*/
318 edgesTo (eBBlock * to)
323 for (loop = setFirstItem (graphEdges); loop; loop = setNextItem (graphEdges))
324 if (loop->to == to && !loop->from->noPath)
325 addSet (&result, loop->from);
331 /*-----------------------------------------------------------------*/
332 /* addiCodeToeBBlock - will add an iCode to the end of a block */
333 /*-----------------------------------------------------------------*/
335 addiCodeToeBBlock (eBBlock * ebp, iCode * ic, iCode * ip)
337 ic->prev = ic->next = NULL;
338 /* if the insert point is given */
341 ic->lineno = ip->lineno;
352 /* if the block has no instructions */
353 if (ebp->ech == NULL)
355 ebp->sch = ebp->ech = ic;
360 /* if the last instruction is a goto */
361 /* we add it just before the goto */
362 if (ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE
363 || ebp->ech->op == RETURN)
365 ic->lineno = ebp->ech->lineno;
366 ic->prev = ebp->ech->prev;
369 if (!ic->prev) /* was the last only on in the block */
376 /* if the last one was a ifx statement we check to see */
377 /* if the condition was defined in the previous instruction */
378 /* if this is true then we put it before the condition else */
379 /* we put it before if, this is to reduce register pressure, */
380 /* we don't have to hold condition too long in a register */
381 if (ebp->ech->op == IFX)
385 /* if ( !ebp->ech->prev ) */
386 /* ipoint = ebp->ech ; */
388 /* if (!IC_RESULT(ebp->ech->prev)) */
389 /* ipoint = ebp->ech ; */
391 /* if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
392 /* ipoint = ebp->ech->prev; */
394 /* ipoint = ebp->ech ; */
396 ic->lineno = ipoint->lineno;
397 ic->prev = ipoint->prev;
407 /* will add it to the very end */
417 /*-----------------------------------------------------------------*/
418 /* remiCodeFromeBBlock - remove an iCode from BBlock */
419 /*-----------------------------------------------------------------*/
421 remiCodeFromeBBlock (eBBlock * ebb, iCode * ic)
423 wassert (ic->seq>=ebb->fSeq && ic->seq<=ebb->lSeq);
425 ic->prev->next = ic->next;
430 ic->next->prev = ic->prev;
435 /*-----------------------------------------------------------------*/
436 /* iCodeBreakDown : breakDown iCode chain to blocks */
437 /*-----------------------------------------------------------------*/
439 iCodeBreakDown (iCode * ic, int *count)
441 eBBlock **ebbs = NULL;
446 /* allocate for the first entry */
448 ebbs = Safe_alloc (sizeof (eBBlock **));
453 /* convert 2 block */
454 eBBlock *ebb = iCode2eBBlock (loop);
455 loop = ebb->ech->next;
457 ebb->ech->next = NULL; /* mark the end of this chain */
460 ebb->bbnum = *count; /* save this block number */
461 /* put it in the array */
462 ebbs[(*count)++] = ebb;
464 /* allocate for the next one. Remember to clear the new */
465 /* pointer at the end, that was created by realloc. */
467 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
471 /* if this one ends in a goto or a conditional */
472 /* branch then check if the block it is going */
473 /* to already exists, if yes then this could */
474 /* be a loop, add a preheader to the block it */
475 /* goes to if it does not already have one */
476 if (ebbs[(*count) - 1]->ech &&
477 (ebbs[(*count) - 1]->ech->op == GOTO ||
478 ebbs[(*count) - 1]->ech->op == IFX))
484 if (ebbs[(*count) - 1]->ech->op == GOTO)
485 label = IC_LABEL (ebbs[(*count) - 1]->ech);
486 else if (!(label = IC_TRUE (ebbs[(*count) - 1]->ech)))
487 label = IC_FALSE (ebbs[(*count) - 1]->ech);
489 if ((destBlock = eBBWithEntryLabel (ebbs, label, (*count))) &&
490 destBlock->preHeader == NULL &&
491 otherPathsPresent (ebbs, destBlock))
494 symbol *preHeaderLabel = newiTempPreheaderLabel ();
498 /* go thru all block replacing the entryLabel with new label */
499 /* till we reach the block , then we insert a new ebblock */
500 for (i = 0; i < (*count); i++)
502 if (ebbs[i] == destBlock)
504 replaceLabel (ebbs[i], label, preHeaderLabel);
509 /* if we have stopped at the block , allocate for an extra one */
511 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
515 /* then move the block down one count */
516 pBlock = ebbs[j = i];
517 for (i += 1; i < (*count); i++)
527 destBlock->preHeader = ebbs[j] = neweBBlock ();
529 ebbs[j]->entryLabel = preHeaderLabel;
530 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto (LABEL, preHeaderLabel);
531 ebbs[j]->sch->lineno = destBlock->sch->lineno;
542 /*-----------------------------------------------------------------*/
543 /* replaceSymBySym : - replace operand by operand in blocks */
544 /* replaces only left & right in blocks */
545 /*-----------------------------------------------------------------*/
547 replaceSymBySym (set * sset, operand * src, operand * dest)
552 /* for all blocks in the set do */
553 for (loop = sset; loop; loop = loop->next)
558 /* for all instructions in this block do */
559 for (ic = rBlock->sch; ic; ic = ic->next)
562 /* if we find usage */
563 if (ic->op == IFX && isOperandEqual (src, IC_COND (ic)))
565 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
566 IC_COND (ic) = operandFromOperand (dest);
567 OP_USES_SET ((dest), bitVectSetBit (OP_USES (dest), ic->key));
571 if (isOperandEqual (IC_RIGHT (ic), src))
573 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
574 IC_RIGHT (ic) = operandFromOperand (dest);
575 IC_RIGHT (ic)->isaddr = 0;
576 OP_USES_SET ((dest), bitVectSetBit (OP_USES (dest), ic->key));
579 if (isOperandEqual (IC_LEFT (ic), src))
581 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
582 if (POINTER_GET (ic) && IS_ITEMP (dest))
584 IC_LEFT (ic) = operandFromOperand (dest);
585 IC_LEFT (ic)->isaddr = 1;
589 IC_LEFT (ic) = operandFromOperand (dest);
590 IC_LEFT (ic)->isaddr = 0;
592 OP_USES_SET ((dest), bitVectSetBit (OP_USES (dest), ic->key));
595 /* special case for pointer sets */
596 if (POINTER_SET (ic) &&
597 isOperandEqual (IC_RESULT (ic), src))
599 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
600 IC_RESULT (ic) = operandFromOperand (dest);
601 IC_RESULT (ic)->isaddr = 1;
602 OP_USES_SET ((dest), bitVectSetBit (OP_USES (dest), ic->key));
608 /*-----------------------------------------------------------------*/
609 /* replaceLabel - replace reference to one label by another */
610 /*-----------------------------------------------------------------*/
612 replaceLabel (eBBlock * ebp, symbol * fromLbl, symbol * toLbl)
619 for (ic = ebp->sch; ic; ic = ic->next)
625 if (isSymbolEqual (IC_LABEL (ic), fromLbl))
626 IC_LABEL (ic) = toLbl;
630 if (IC_TRUE (ic) && isSymbolEqual (IC_TRUE (ic), fromLbl))
631 IC_TRUE (ic) = toLbl;
632 else if (isSymbolEqual (IC_FALSE (ic), fromLbl))
633 IC_FALSE (ic) = toLbl;
643 /*-----------------------------------------------------------------*/
644 /* iCodeFromeBBlock - convert basic block to iCode chain */
645 /*-----------------------------------------------------------------*/
647 iCodeFromeBBlock (eBBlock ** ebbs, int count)
650 iCode *ric = ebbs[0]->sch;
651 iCode *lic = ebbs[0]->ech;
653 for (; i < count; i++)
655 if (ebbs[i]->sch == NULL)
658 if (ebbs[i]->noPath &&
659 (ebbs[i]->entryLabel != entryLabel &&
660 ebbs[i]->entryLabel != returnLabel))
662 werror (W_CODE_UNREACH, ebbs[i]->sch->filename, ebbs[i]->sch->lineno);
666 lic->next = ebbs[i]->sch;
667 lic->next->prev = lic;
674 /*-----------------------------------------------------------------*/
675 /* otherPathsPresent - determines if there is a path from _entry */
676 /* to this block in a half constructed set of blocks */
677 /*-----------------------------------------------------------------*/
679 otherPathsPresent (eBBlock ** ebbs, eBBlock * this)
683 /* for all blocks preceding this block */
684 for (i = 0; i < this->bbnum; i++)
688 /* if there is a reference to the entry label of this block */
689 for (ic = ebbs[i]->sch; ic; ic = ic->next)
694 if (IC_LABEL (ic)->key == this->entryLabel->key)
701 if (IC_TRUE (ic)->key == this->entryLabel->key)
704 else if (IC_FALSE (ic)->key == this->entryLabel->key)
711 /* comes here means we have not found it yet */
712 /* in this case check if the previous block */
713 /* ends in a goto if it does then we have no */
714 /* path else we have a path */
715 if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
716 ebbs[this->bbnum - 1]->ech->op == GOTO)