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 fprintf (of, "\n----------------------------------------------------------------\n");
200 printiCChain (ebbs[i]->sch, of);
205 /*-----------------------------------------------------------------*/
206 /* iCode2eBBlock - converts a sequnce till label to a ebb */
207 /*-----------------------------------------------------------------*/
209 iCode2eBBlock (iCode * ic)
212 eBBlock *ebb = neweBBlock (); /* a llocate an entry */
214 /* put the first one unconditionally */
217 /* if this is a label then */
219 ebb->entryLabel = ic->argLabel.label;
222 sprintf (buffer, "_eBBlock%d", eBBNum++);
223 ebb->entryLabel = newSymbol (buffer, 1);
224 ebb->entryLabel->key = labelKey++;
229 ic->op == JUMPTABLE ||
236 if ((ic->next && ic->next->op == LABEL) ||
243 /* loop thru till we find one with a label */
244 for (loop = ic->next; loop; loop = loop->next)
247 /* if this is the last one */
250 /* if this is a function call */
251 if (loop->op == CALL || loop->op == PCALL)
255 currFunc->hasFcall = 1;
258 /* if the next one is a label */
259 /* if this is a goto or ifx */
260 if (loop->next->op == LABEL ||
262 loop->op == JUMPTABLE ||
267 /* mark the end of the chain */
273 /*-----------------------------------------------------------------*/
274 /* eBBWithEntryLabel - finds the basic block with the entry label */
275 /*-----------------------------------------------------------------*/
277 eBBWithEntryLabel (eBBlock ** ebbs, symbol * eLabel, int count)
281 for (i = 0; i < count; i++)
283 if (isSymbolEqual (ebbs[i]->entryLabel, eLabel))
291 /*-----------------------------------------------------------------*/
292 /* ifFromIs - will return 1 if the from block matches this */
293 /*-----------------------------------------------------------------*/
294 DEFSETFUNC (ifFromIs)
297 V_ARG (eBBlock *, this);
299 if (ep->from == this)
306 /*-----------------------------------------------------------------*/
307 /* edgesTo - returns a set of edges with to == supplied value */
308 /*-----------------------------------------------------------------*/
310 edgesTo (eBBlock * to)
315 for (loop = setFirstItem (graphEdges); loop; loop = setNextItem (graphEdges))
316 if (loop->to == to && !loop->from->noPath)
317 addSet (&result, loop->from);
323 /*-----------------------------------------------------------------*/
324 /* addiCodeToeBBlock - will add an iCode to the end of a block */
325 /*-----------------------------------------------------------------*/
327 addiCodeToeBBlock (eBBlock * ebp, iCode * ic, iCode * ip)
329 ic->prev = ic->next = NULL;
330 /* if the insert point is given */
333 ic->lineno = ip->lineno;
344 /* if the block has no instructions */
345 if (ebp->ech == NULL)
347 ebp->sch = ebp->ech = ic;
352 /* if the last instruction is a goto */
353 /* we add it just before the goto */
354 if (ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE
355 || ebp->ech->op == RETURN)
357 ic->lineno = ebp->ech->lineno;
358 ic->prev = ebp->ech->prev;
361 if (!ic->prev) /* was the last only on in the block */
368 /* if the last one was a ifx statement we check to see */
369 /* if the condition was defined in the previous instruction */
370 /* if this is true then we put it before the condition else */
371 /* we put it before if, this is to reduce register pressure, */
372 /* we don't have to hold condition too long in a register */
373 if (ebp->ech->op == IFX)
377 /* if ( !ebp->ech->prev ) */
378 /* ipoint = ebp->ech ; */
380 /* if (!IC_RESULT(ebp->ech->prev)) */
381 /* ipoint = ebp->ech ; */
383 /* if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
384 /* ipoint = ebp->ech->prev; */
386 /* ipoint = ebp->ech ; */
388 ic->lineno = ipoint->lineno;
389 ic->prev = ipoint->prev;
399 /* will add it to the very end */
409 /*-----------------------------------------------------------------*/
410 /* remiCodeFromeBBlock - remove an iCode from BBlock */
411 /*-----------------------------------------------------------------*/
413 remiCodeFromeBBlock (eBBlock * ebb, iCode * ic)
416 ic->prev->next = ic->next;
421 ic->next->prev = ic->prev;
426 /*-----------------------------------------------------------------*/
427 /* iCodeBreakDown : breakDown iCode chain to blocks */
428 /*-----------------------------------------------------------------*/
430 iCodeBreakDown (iCode * ic, int *count)
432 eBBlock **ebbs = NULL;
437 /* allocate for the first entry */
439 ebbs = Safe_alloc (sizeof (eBBlock **));
444 /* convert 2 block */
445 eBBlock *ebb = iCode2eBBlock (loop);
446 loop = ebb->ech->next;
448 ebb->ech->next = NULL; /* mark the end of this chain */
451 ebb->bbnum = *count; /* save this block number */
452 /* put it in the array */
453 ebbs[(*count)++] = ebb;
455 /* allocate for the next one. Remember to clear the new */
456 /* pointer at the end, that was created by realloc. */
458 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
462 /* if this one ends in a goto or a conditional */
463 /* branch then check if the block it is going */
464 /* to already exists, if yes then this could */
465 /* be a loop, add a preheader to the block it */
466 /* goes to if it does not already have one */
467 if (ebbs[(*count) - 1]->ech &&
468 (ebbs[(*count) - 1]->ech->op == GOTO ||
469 ebbs[(*count) - 1]->ech->op == IFX))
475 if (ebbs[(*count) - 1]->ech->op == GOTO)
476 label = IC_LABEL (ebbs[(*count) - 1]->ech);
477 else if (!(label = IC_TRUE (ebbs[(*count) - 1]->ech)))
478 label = IC_FALSE (ebbs[(*count) - 1]->ech);
480 if ((destBlock = eBBWithEntryLabel (ebbs, label, (*count))) &&
481 destBlock->preHeader == NULL &&
482 otherPathsPresent (ebbs, destBlock))
485 symbol *preHeaderLabel = newiTempPreheaderLabel ();
489 /* go thru all block replacing the entryLabel with new label */
490 /* till we reach the block , then we insert a new ebblock */
491 for (i = 0; i < (*count); i++)
493 if (ebbs[i] == destBlock)
495 replaceLabel (ebbs[i], label, preHeaderLabel);
500 /* if we have stopped at the block , allocate for an extra one */
502 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
506 /* then move the block down one count */
507 pBlock = ebbs[j = i];
508 for (i += 1; i < (*count); i++)
518 destBlock->preHeader = ebbs[j] = neweBBlock ();
520 ebbs[j]->entryLabel = preHeaderLabel;
521 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto (LABEL, preHeaderLabel);
522 ebbs[j]->sch->lineno = destBlock->sch->lineno;
533 /*-----------------------------------------------------------------*/
534 /* replaceSymBySym : - replace operand by operand in blocks */
535 /* replaces only left & right in blocks */
536 /*-----------------------------------------------------------------*/
538 replaceSymBySym (set * sset, operand * src, operand * dest)
543 /* for all blocks in the set do */
544 for (loop = sset; loop; loop = loop->next)
549 /* for all instructions in this block do */
550 for (ic = rBlock->sch; ic; ic = ic->next)
553 /* if we find usage */
554 if (ic->op == IFX && isOperandEqual (src, IC_COND (ic)))
556 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
557 IC_COND (ic) = operandFromOperand (dest);
558 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
562 if (isOperandEqual (IC_RIGHT (ic), src))
564 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
565 IC_RIGHT (ic) = operandFromOperand (dest);
566 IC_RIGHT (ic)->isaddr = 0;
567 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
570 if (isOperandEqual (IC_LEFT (ic), src))
572 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
573 if (POINTER_GET (ic) && IS_ITEMP (dest))
575 IC_LEFT (ic) = operandFromOperand (dest);
576 IC_LEFT (ic)->isaddr = 1;
580 IC_LEFT (ic) = operandFromOperand (dest);
581 IC_LEFT (ic)->isaddr = 0;
583 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
586 /* special case for pointer sets */
587 if (POINTER_SET (ic) &&
588 isOperandEqual (IC_RESULT (ic), src))
590 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
591 IC_RESULT (ic) = operandFromOperand (dest);
592 IC_RESULT (ic)->isaddr = 1;
593 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
599 /*-----------------------------------------------------------------*/
600 /* replaceLabel - replace reference to one label by another */
601 /*-----------------------------------------------------------------*/
603 replaceLabel (eBBlock * ebp, symbol * fromLbl, symbol * toLbl)
610 for (ic = ebp->sch; ic; ic = ic->next)
616 if (isSymbolEqual (IC_LABEL (ic), fromLbl))
617 IC_LABEL (ic) = toLbl;
621 if (IC_TRUE (ic) && isSymbolEqual (IC_TRUE (ic), fromLbl))
622 IC_TRUE (ic) = toLbl;
623 else if (isSymbolEqual (IC_FALSE (ic), fromLbl))
624 IC_FALSE (ic) = toLbl;
634 /*-----------------------------------------------------------------*/
635 /* iCodeFromeBBlock - convert basic block to iCode chain */
636 /*-----------------------------------------------------------------*/
638 iCodeFromeBBlock (eBBlock ** ebbs, int count)
641 iCode *ric = ebbs[0]->sch;
642 iCode *lic = ebbs[0]->ech;
644 for (; i < count; i++)
646 if (ebbs[i]->sch == NULL)
649 if (ebbs[i]->noPath &&
650 (ebbs[i]->entryLabel != entryLabel &&
651 ebbs[i]->entryLabel != returnLabel))
653 werror (W_CODE_UNREACH, ebbs[i]->sch->filename, ebbs[i]->sch->lineno);
657 lic->next = ebbs[i]->sch;
658 lic->next->prev = lic;
665 /*-----------------------------------------------------------------*/
666 /* otherPathsPresent - determines if there is a path from _entry */
667 /* to this block in a half constructed set of blocks */
668 /*-----------------------------------------------------------------*/
670 otherPathsPresent (eBBlock ** ebbs, eBBlock * this)
674 /* for all blocks preceding this block */
675 for (i = 0; i < this->bbnum; i++)
679 /* if there is a reference to the entry label of this block */
680 for (ic = ebbs[i]->sch; ic; ic = ic->next)
685 if (IC_LABEL (ic)->key == this->entryLabel->key)
692 if (IC_TRUE (ic)->key == this->entryLabel->key)
695 else if (IC_FALSE (ic)->key == this->entryLabel->key)
702 /* comes here means we have not found it yet */
703 /* in this case check if the previous block */
704 /* ends in a goto if it does then we have no */
705 /* path else we have a path */
706 if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
707 ebbs[this->bbnum - 1]->ech->op == GOTO)