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 -------------------------------------------------------------------------*/
30 set *graphEdges = NULL; /* list of edges in this flow graph */
32 /*-----------------------------------------------------------------*/
33 /* printEntryLabel - prints entry label of a ebblock */
34 /*-----------------------------------------------------------------*/
35 DEFSETFUNC (printEntryLabel)
39 fprintf (stdout, " %-20s ", bp->entryLabel->name);
43 /*-----------------------------------------------------------------*/
44 /* neweBBlock - allocate & return a new extended basic block */
45 /*-----------------------------------------------------------------*/
51 ebb = Safe_calloc (1, sizeof (eBBlock));
55 /*-----------------------------------------------------------------*/
56 /* newEdge - allocates & initialises an edge to given values */
57 /*-----------------------------------------------------------------*/
59 newEdge (eBBlock * from, eBBlock * to)
63 ep = Safe_calloc (1, sizeof (edge));
70 /*-----------------------------------------------------------------*/
71 /* dumpLiveRanges - dump liverange information into a file */
72 /*-----------------------------------------------------------------*/
74 dumpLiveRanges (char *ext, hTab * liveRanges)
82 /* create the file name */
83 strcpy (buffer, srcFileName);
86 if (!(file = fopen (buffer, "a+")))
88 werror (E_FILE_OPEN_ERR, buffer);
95 for (sym = hTabFirstItem (liveRanges, &k); sym;
96 sym = hTabNextItem (liveRanges, &k))
99 fprintf (file, "%s [k%d lr%d:%d so:%d]{ re%d rm%d}",
100 (sym->rname[0] ? sym->rname : sym->name),
102 sym->liveFrom, sym->liveTo,
104 sym->isreqv, sym->remat
108 printTypeChain (sym->type, file);
109 if (sym->usl.spillLoc)
111 fprintf (file, "}{ sir@ %s", sym->usl.spillLoc->rname);
115 /* if assigned to registers */
121 if (sym->usl.spillLoc)
122 fprintf (file, "[%s]", (sym->usl.spillLoc->rname[0] ?
123 sym->usl.spillLoc->rname :
124 sym->usl.spillLoc->name));
126 fprintf (file, "[err]");
128 fprintf (file, "[remat]");
134 for (i = 0; i < sym->nRegs; i++)
135 fprintf (file, "%s ", port->getRegName (sym->regs[i]));
139 fprintf (file, "\n");
144 /*-----------------------------------------------------------------*/
145 /* dumpEbbsToFileExt - writeall the basic blocks to a file */
146 /*-----------------------------------------------------------------*/
148 dumpEbbsToFileExt (char *ext, eBBlock ** ebbs, int count)
155 /* create the file name */
156 strcpy (buffer, srcFileName);
157 strcat (buffer, ext);
159 if (!(of = fopen (buffer, "a+")))
161 werror (E_FILE_OPEN_ERR, buffer);
168 for (i = 0; i < count; i++)
170 fprintf (of, "\n----------------------------------------------------------------\n");
171 fprintf (of, "Basic Block %s : loop Depth = %d noPath = %d , lastinLoop = %d\n",
172 ebbs[i]->entryLabel->name,
175 ebbs[i]->isLastInLoop);
176 fprintf (of, "\ndefines bitVector :");
177 bitVectDebugOn (ebbs[i]->defSet, of);
178 fprintf (of, "\nlocal defines bitVector :");
179 bitVectDebugOn (ebbs[i]->ldefs, of);
180 fprintf (of, "\npointers Set bitvector :");
181 bitVectDebugOn (ebbs[i]->ptrsSet, of);
182 fprintf (of, "\n----------------------------------------------------------------\n");
183 printiCChain (ebbs[i]->sch, of);
188 /*-----------------------------------------------------------------*/
189 /* iCode2eBBlock - converts a sequnce till label to a ebb */
190 /*-----------------------------------------------------------------*/
192 iCode2eBBlock (iCode * ic)
195 eBBlock *ebb = neweBBlock (); /* a llocate an entry */
197 /* put the first one unconditionally */
200 /* if this is a label then */
202 ebb->entryLabel = ic->argLabel.label;
205 sprintf (buffer, "_eBBlock%d", eBBNum++);
206 ebb->entryLabel = newSymbol (buffer, 1);
207 ebb->entryLabel->key = labelKey++;
212 ic->op == JUMPTABLE ||
219 if ((ic->next && ic->next->op == LABEL) ||
226 /* loop thru till we find one with a label */
227 for (loop = ic->next; loop; loop = loop->next)
230 /* if this is the last one */
233 /* if this is a function call */
234 if (loop->op == CALL || loop->op == PCALL)
238 currFunc->hasFcall = 1;
241 /* if the next one is a label */
242 /* if this is a goto or ifx */
243 if (loop->next->op == LABEL ||
245 loop->op == JUMPTABLE ||
250 /* mark the end of the chain */
256 /*-----------------------------------------------------------------*/
257 /* eBBWithEntryLabel - finds the basic block with the entry label */
258 /*-----------------------------------------------------------------*/
260 eBBWithEntryLabel (eBBlock ** ebbs, symbol * eLabel, int count)
264 for (i = 0; i < count; i++)
266 if (isSymbolEqual (ebbs[i]->entryLabel, eLabel))
274 /*-----------------------------------------------------------------*/
275 /* ifFromIs - will return 1 if the from block matches this */
276 /*-----------------------------------------------------------------*/
277 DEFSETFUNC (ifFromIs)
280 V_ARG (eBBlock *, this);
282 if (ep->from == this)
289 /*-----------------------------------------------------------------*/
290 /* edgesTo - returns a set of edges with to == supplied value */
291 /*-----------------------------------------------------------------*/
293 edgesTo (eBBlock * to)
298 for (loop = setFirstItem (graphEdges); loop; loop = setNextItem (graphEdges))
299 if (loop->to == to && !loop->from->noPath)
300 addSet (&result, loop->from);
306 /*-----------------------------------------------------------------*/
307 /* addiCodeToeBBlock - will add an iCode to the end of a block */
308 /*-----------------------------------------------------------------*/
310 addiCodeToeBBlock (eBBlock * ebp, iCode * ic, iCode * ip)
312 ic->prev = ic->next = NULL;
313 /* if the insert point is given */
316 ic->lineno = ip->lineno;
327 /* if the block has no instructions */
328 if (ebp->ech == NULL)
330 ebp->sch = ebp->ech = ic;
335 /* if the last instruction is a goto */
336 /* we add it just before the goto */
337 if (ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE
338 || ebp->ech->op == RETURN)
340 ic->lineno = ebp->ech->lineno;
341 ic->prev = ebp->ech->prev;
344 if (!ic->prev) /* was the last only on in the block */
351 /* if the last one was a ifx statement we check to see */
352 /* if the condition was defined in the previous instruction */
353 /* if this is true then we put it before the condition else */
354 /* we put it before if, this is to reduce register pressure, */
355 /* we don't have to hold condition too long in a register */
356 if (ebp->ech->op == IFX)
360 /* if ( !ebp->ech->prev ) */
361 /* ipoint = ebp->ech ; */
363 /* if (!IC_RESULT(ebp->ech->prev)) */
364 /* ipoint = ebp->ech ; */
366 /* if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
367 /* ipoint = ebp->ech->prev; */
369 /* ipoint = ebp->ech ; */
371 ic->lineno = ipoint->lineno;
372 ic->prev = ipoint->prev;
382 /* will add it to the very end */
392 /*-----------------------------------------------------------------*/
393 /* remiCodeFromeBBlock - remove an iCode from BBlock */
394 /*-----------------------------------------------------------------*/
396 remiCodeFromeBBlock (eBBlock * ebb, iCode * ic)
399 ic->prev->next = ic->next;
404 ic->next->prev = ic->prev;
409 /*-----------------------------------------------------------------*/
410 /* iCodeBreakDown : breakDown iCode chain to blocks */
411 /*-----------------------------------------------------------------*/
413 iCodeBreakDown (iCode * ic, int *count)
415 eBBlock **ebbs = NULL;
420 /* allocate for the first entry */
422 ebbs = Safe_calloc (1, sizeof (eBBlock **));
427 /* convert 2 block */
428 eBBlock *ebb = iCode2eBBlock (loop);
429 loop = ebb->ech->next;
431 ebb->ech->next = NULL; /* mark the end of this chain */
434 ebb->bbnum = *count; /* save this block number */
435 /* put it in the array */
436 ebbs[(*count)++] = ebb;
438 /* allocate for the next one. Remember to clear the new */
439 /* pointer at the end, that was created by realloc. */
441 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
445 /* if this one ends in a goto or a conditional */
446 /* branch then check if the block it is going */
447 /* to already exists, if yes then this could */
448 /* be a loop, add a preheader to the block it */
449 /* goes to if it does not already have one */
450 if (ebbs[(*count) - 1]->ech &&
451 (ebbs[(*count) - 1]->ech->op == GOTO ||
452 ebbs[(*count) - 1]->ech->op == IFX))
458 if (ebbs[(*count) - 1]->ech->op == GOTO)
459 label = IC_LABEL (ebbs[(*count) - 1]->ech);
460 else if (!(label = IC_TRUE (ebbs[(*count) - 1]->ech)))
461 label = IC_FALSE (ebbs[(*count) - 1]->ech);
463 if ((destBlock = eBBWithEntryLabel (ebbs, label, (*count))) &&
464 destBlock->preHeader == NULL &&
465 otherPathsPresent (ebbs, destBlock))
468 symbol *preHeaderLabel = newiTempPreheaderLabel ();
472 /* go thru all block replacing the entryLabel with new label */
473 /* till we reach the block , then we insert a new ebblock */
474 for (i = 0; i < (*count); i++)
476 if (ebbs[i] == destBlock)
478 replaceLabel (ebbs[i], label, preHeaderLabel);
483 /* if we have stopped at the block , allocate for an extra one */
485 ebbs = Safe_realloc (ebbs, (*count + 1) * sizeof (eBBlock **));
489 /* then move the block down one count */
490 pBlock = ebbs[j = i];
491 for (i += 1; i < (*count); i++)
501 destBlock->preHeader = ebbs[j] = neweBBlock ();
503 ebbs[j]->entryLabel = preHeaderLabel;
504 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto (LABEL, preHeaderLabel);
505 ebbs[j]->sch->lineno = destBlock->sch->lineno;
516 /*-----------------------------------------------------------------*/
517 /* replaceSymBySym : - replace operand by operand in blocks */
518 /* replaces only left & right in blocks */
519 /*-----------------------------------------------------------------*/
521 replaceSymBySym (set * sset, operand * src, operand * dest)
526 /* for all blocks in the set do */
527 for (loop = sset; loop; loop = loop->next)
532 /* for all instructions in this block do */
533 for (ic = rBlock->sch; ic; ic = ic->next)
536 /* if we find usage */
537 if (ic->op == IFX && isOperandEqual (src, IC_COND (ic)))
539 bitVectUnSetBit (OP_USES (IC_COND (ic)), ic->key);
540 IC_COND (ic) = operandFromOperand (dest);
541 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
545 if (isOperandEqual (IC_RIGHT (ic), src))
547 bitVectUnSetBit (OP_USES (IC_RIGHT (ic)), ic->key);
548 IC_RIGHT (ic) = operandFromOperand (dest);
549 IC_RIGHT (ic)->isaddr = 0;
550 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
553 if (isOperandEqual (IC_LEFT (ic), src))
555 bitVectUnSetBit (OP_USES (IC_LEFT (ic)), ic->key);
556 if (POINTER_GET (ic) && IS_ITEMP (dest))
558 IC_LEFT (ic) = operandFromOperand (dest);
559 IC_LEFT (ic)->isaddr = 1;
563 IC_LEFT (ic) = operandFromOperand (dest);
564 IC_LEFT (ic)->isaddr = 0;
566 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
569 /* special case for pointer sets */
570 if (POINTER_SET (ic) &&
571 isOperandEqual (IC_RESULT (ic), src))
573 bitVectUnSetBit (OP_USES (IC_RESULT (ic)), ic->key);
574 IC_RESULT (ic) = operandFromOperand (dest);
575 IC_RESULT (ic)->isaddr = 1;
576 OP_USES (dest) = bitVectSetBit (OP_USES (dest), ic->key);
582 /*-----------------------------------------------------------------*/
583 /* replaceLabel - replace reference to one label by another */
584 /*-----------------------------------------------------------------*/
586 replaceLabel (eBBlock * ebp, symbol * fromLbl, symbol * toLbl)
593 for (ic = ebp->sch; ic; ic = ic->next)
599 if (isSymbolEqual (IC_LABEL (ic), fromLbl))
600 IC_LABEL (ic) = toLbl;
604 if (IC_TRUE (ic) && isSymbolEqual (IC_TRUE (ic), fromLbl))
605 IC_TRUE (ic) = toLbl;
606 else if (isSymbolEqual (IC_FALSE (ic), fromLbl))
607 IC_FALSE (ic) = toLbl;
617 /*-----------------------------------------------------------------*/
618 /* iCodeFromeBBlock - convert basic block to iCode chain */
619 /*-----------------------------------------------------------------*/
621 iCodeFromeBBlock (eBBlock ** ebbs, int count)
624 iCode *ric = ebbs[0]->sch;
625 iCode *lic = ebbs[0]->ech;
627 for (; i < count; i++)
629 if (ebbs[i]->sch == NULL)
632 if (ebbs[i]->noPath &&
633 (ebbs[i]->entryLabel != entryLabel &&
634 ebbs[i]->entryLabel != returnLabel))
636 werror (W_CODE_UNREACH, ebbs[i]->sch->filename, ebbs[i]->sch->lineno);
640 lic->next = ebbs[i]->sch;
641 lic->next->prev = lic;
648 /*-----------------------------------------------------------------*/
649 /* otherPathsPresent - determines if there is a path from _entry */
650 /* to this block in a half constructed set of blocks */
651 /*-----------------------------------------------------------------*/
653 otherPathsPresent (eBBlock ** ebbs, eBBlock * this)
657 /* for all blocks preceding this block */
658 for (i = 0; i < this->bbnum; i++)
662 /* if there is a reference to the entry label of this block */
663 for (ic = ebbs[i]->sch; ic; ic = ic->next)
668 if (IC_LABEL (ic)->key == this->entryLabel->key)
675 if (IC_TRUE (ic)->key == this->entryLabel->key)
678 else if (IC_FALSE (ic)->key == this->entryLabel->key)
685 /* comes here means we have not found it yet */
686 /* in this case check if the previous block */
687 /* ends in a goto if it does then we have no */
688 /* path else we have a path */
689 if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
690 ebbs[this->bbnum - 1]->ech->op == GOTO)