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 */
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 /*-----------------------------------------------------------------*/
46 eBBlock *neweBBlock ()
50 ALLOC(ebb,sizeof(eBBlock));
54 /*-----------------------------------------------------------------*/
55 /* newEdge - allocates & initialises an edge to given values */
56 /*-----------------------------------------------------------------*/
57 edge *newEdge (eBBlock *from, eBBlock *to)
61 ALLOC(ep,sizeof(edge));
68 /*-----------------------------------------------------------------*/
69 /* dumpEbbsToFileExt - writeall the basic blocks to a file */
70 /*-----------------------------------------------------------------*/
71 void dumpEbbsToFileExt (char *ext,eBBlock **ebbs, int count)
76 /* create the file name */
77 strcpy(buffer,srcFileName);
80 if (!(of = fopen(buffer,"a+"))) {
81 werror(E_FILE_OPEN_ERR,buffer);
85 for (i=0; i < count ; i++ ) {
86 fprintf(of,"\n----------------------------------------------------------------\n");
87 fprintf(of,"Basic Block %s : loop Depth = %d noPath = %d , lastinLoop = %d\n",
88 ebbs[i]->entryLabel->name,
91 ebbs[i]->isLastInLoop);
92 fprintf(of,"\ndefines bitVector :");
93 bitVectDebugOn(ebbs[i]->defSet,of);
94 fprintf(of,"\nlocal defines bitVector :");
95 bitVectDebugOn(ebbs[i]->ldefs,of);
96 fprintf(of,"\npointers Set bitvector :");
97 bitVectDebugOn(ebbs[i]->ptrsSet,of);
98 fprintf(of,"\n----------------------------------------------------------------\n");
99 printiCChain(ebbs[i]->sch,of);
104 /*-----------------------------------------------------------------*/
105 /* iCode2eBBlock - converts a sequnce till label to a ebb */
106 /*-----------------------------------------------------------------*/
107 eBBlock *iCode2eBBlock (iCode *ic)
110 eBBlock *ebb = neweBBlock(); /* a llocate an entry */
112 /* put the first one unconditionally */
115 /* if this is a label then */
117 ebb->entryLabel = ic->argLabel.label ;
119 sprintf(buffer,"_eBBlock%d",eBBNum++);
120 ebb->entryLabel = newSymbol(buffer,1);
121 ebb->entryLabel->key = labelKey++;
126 ic->op == JUMPTABLE ||
132 if ((ic->next && ic->next->op == LABEL) ||
134 ebb->ech = ebb->sch ;
138 /* loop thru till we find one with a label */
139 for ( loop = ic->next ; loop ; loop = loop->next ) {
141 /* if this is the last one */
144 /* if this is a function call */
145 if (loop->op == CALL || loop->op == PCALL) {
148 currFunc->hasFcall = 1;
151 /* if the next one is a label */
152 /* if this is a goto or ifx */
153 if (loop->next->op == LABEL ||
155 loop->op == JUMPTABLE ||
160 /* mark the end of the chain */
166 /*-----------------------------------------------------------------*/
167 /* eBBWithEntryLabel - finds the basic block with the entry label */
168 /*-----------------------------------------------------------------*/
169 eBBlock *eBBWithEntryLabel ( eBBlock **ebbs , symbol *eLabel, int count)
173 for ( i = 0 ; i < count ; i++ ) {
174 if (isSymbolEqual(ebbs[i]->entryLabel,eLabel))
182 /*-----------------------------------------------------------------*/
183 /* ifFromIs - will return 1 if the from block matches this */
184 /*-----------------------------------------------------------------*/
188 V_ARG(eBBlock *,this);
190 if (ep->from == this)
197 /*-----------------------------------------------------------------*/
198 /* edgesTo - returns a set of edges with to == supplied value */
199 /*-----------------------------------------------------------------*/
200 set *edgesTo ( eBBlock *to )
205 for (loop = setFirstItem(graphEdges) ; loop ; loop = setNextItem(graphEdges))
206 if (loop->to == to && !loop->from->noPath)
207 addSet(&result,loop->from);
213 /*-----------------------------------------------------------------*/
214 /* addiCodeToeBBlock - will add an iCode to the end of a block */
215 /*-----------------------------------------------------------------*/
216 void addiCodeToeBBlock ( eBBlock *ebp, iCode *ic , iCode *ip)
218 ic->prev = ic->next = NULL;
219 /* if the insert point is given */
221 ic->lineno = ip->lineno;
232 /* if the block has no instructions */
233 if (ebp->ech == NULL ) {
234 ebp->sch = ebp->ech = ic;
239 /* if the last instruction is a goto */
240 /* we add it just before the goto */
241 if ( ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE) {
242 ic->lineno = ebp->ech->lineno;
243 ic->prev = ebp->ech->prev;
246 if (!ic->prev) /* was the last only on in the block */
253 /* if the last one was a ifx statement we check to see */
254 /* if the condition was defined in the previous instruction */
255 /* if this is true then we put it before the condition else */
256 /* we put it before if, this is to reduce register pressure,*/
257 /* we don't have to hold condition too long in a register */
258 if ( ebp->ech->op == IFX ) {
261 /* if ( !ebp->ech->prev ) */
262 /* ipoint = ebp->ech ; */
264 /* if (!IC_RESULT(ebp->ech->prev)) */
265 /* ipoint = ebp->ech ; */
267 /* if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
268 /* ipoint = ebp->ech->prev; */
270 /* ipoint = ebp->ech ; */
272 ic->lineno = ipoint->lineno;
273 ic->prev = ipoint->prev;
283 /* will add it to the very end */
293 /*-----------------------------------------------------------------*/
294 /* remiCodeFromeBBlock - remove an iCode from BBlock */
295 /*-----------------------------------------------------------------*/
296 void remiCodeFromeBBlock (eBBlock *ebb, iCode *ic)
299 ic->prev->next = ic->next ;
301 ebb->sch = ic->next ;
304 ic->next->prev = ic->prev;
309 /*-----------------------------------------------------------------*/
310 /* iCodeBreakDown : breakDown iCode chain to blocks */
311 /*-----------------------------------------------------------------*/
312 eBBlock **iCodeBreakDown (iCode *ic, int *count)
314 eBBlock **ebbs = NULL ;
319 /* allocate for the first entry */
320 ALLOC(ebbs,sizeof(eBBlock **));
324 /* convert 2 block */
325 eBBlock *ebb = iCode2eBBlock(loop);
326 loop = ebb->ech->next ;
328 ebb->ech->next = NULL ; /* mark the end of this chain */
331 ebb->bbnum = *count ; /* save this block number */
332 /* put it in the array */
333 ebbs[(*count)++] = ebb ;
335 /* allocate for the next one */
336 if (!(ebbs = GC_realloc(ebbs,(*count + 1)*sizeof(eBBlock **)))) {
337 werror(E_OUT_OF_MEM,__FILE__,(*count + 1)*sizeof(eBBlock **));
341 /* if this one ends in a goto or a conditional */
342 /* branch then check if the block it is going */
343 /* to already exists, if yes then this could */
344 /* be a loop, add a preheader to the block it */
345 /* goes to if it does not already have one */
346 if (ebbs[(*count) - 1]->ech &&
347 (ebbs[(*count) - 1]->ech->op == GOTO ||
348 ebbs[(*count) - 1]->ech->op == IFX )) {
353 if (ebbs[(*count) - 1]->ech->op == GOTO)
354 label = IC_LABEL(ebbs[(*count)-1]->ech);
356 if (!(label = IC_TRUE(ebbs[(*count)-1]->ech)))
357 label = IC_FALSE(ebbs[(*count)-1]->ech);
359 if ((destBlock = eBBWithEntryLabel(ebbs,label,(*count))) &&
360 destBlock->preHeader == NULL &&
361 otherPathsPresent(ebbs,destBlock) ) {
363 symbol *preHeaderLabel = newiTempPreheaderLabel();
367 /* go thru all block replacing the entryLabel with new label */
368 /* till we reach the block , then we insert a new ebblock */
369 for ( i = 0 ; i < (*count) ; i++ ) {
370 if ( ebbs[i] == destBlock )
372 replaceLabel(ebbs[i],label,preHeaderLabel);
376 /* if we have stopped at the block , allocate for an extra one */
377 if (!(ebbs = GC_realloc(ebbs,(*count + 1)*sizeof(eBBlock **)))) {
378 werror(E_OUT_OF_MEM,__FILE__,(*count + 1)*sizeof(eBBlock **));
382 /* then move the block down one count */
383 pBlock = ebbs[j = i];
384 for ( i += 1; i < (*count) ; i++ ) {
393 destBlock->preHeader = ebbs[j] = neweBBlock();
395 ebbs[j]->entryLabel = preHeaderLabel ;
396 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto(LABEL,preHeaderLabel);
397 ebbs[j]->sch->lineno = destBlock->sch->lineno;
403 ebbs[*count] = NULL ;
408 /*-----------------------------------------------------------------*/
409 /* replaceSymBySym : - replace operand by operand in blocks */
410 /* replaces only left & right in blocks */
411 /*-----------------------------------------------------------------*/
412 void replaceSymBySym (set *sset, operand *src, operand *dest)
417 /* for all blocks in the set do */
418 for ( loop = sset ; loop ; loop = loop->next) {
421 rBlock = loop->item ;
422 /* for all instructions in this block do */
423 for ( ic = rBlock->sch ; ic ; ic = ic->next ) {
425 /* if we find usage */
426 if (ic->op == IFX && isOperandEqual(src,IC_COND(ic))) {
427 bitVectUnSetBit (OP_USES(IC_COND(ic)),ic->key);
428 IC_COND(ic) = operandFromOperand(dest);
429 OP_USES(dest) = bitVectSetBit (OP_USES(dest),ic->key);
433 if (isOperandEqual(IC_RIGHT(ic),src)) {
434 bitVectUnSetBit (OP_USES(IC_RIGHT(ic)),ic->key);
435 IC_RIGHT(ic) = operandFromOperand(dest);
436 IC_RIGHT(ic)->isaddr = 0;
437 OP_USES(dest) = bitVectSetBit (OP_USES(dest),ic->key);
440 if (isOperandEqual(IC_LEFT(ic),src)) {
441 bitVectUnSetBit (OP_USES(IC_LEFT(ic)),ic->key);
442 if (POINTER_GET(ic) && IS_ITEMP(dest)) {
443 IC_LEFT(ic) = operandFromOperand(dest);
444 IC_LEFT(ic)->isaddr = 1;
446 IC_LEFT(ic) = operandFromOperand(dest);
447 IC_LEFT(ic)->isaddr = 0;
449 OP_USES(dest) = bitVectSetBit (OP_USES(dest),ic->key);
452 /* special case for pointer sets */
453 if (POINTER_SET(ic) &&
454 isOperandEqual(IC_RESULT(ic),src)) {
455 bitVectUnSetBit (OP_USES(IC_RESULT(ic)),ic->key);
456 IC_RESULT(ic) = operandFromOperand(dest);
457 IC_RESULT(ic)->isaddr = 1;
458 OP_USES(dest) = bitVectSetBit(OP_USES(dest),ic->key);
464 /*-----------------------------------------------------------------*/
465 /* replaceLabel - replace reference to one label by another */
466 /*-----------------------------------------------------------------*/
467 void replaceLabel(eBBlock *ebp, symbol *fromLbl, symbol *toLbl)
474 for (ic = ebp->sch ; ic ; ic = ic->next ) {
478 if (isSymbolEqual(IC_LABEL(ic),fromLbl))
479 IC_LABEL(ic) = toLbl;
483 if (IC_TRUE(ic) && isSymbolEqual(IC_TRUE(ic),fromLbl))
484 IC_TRUE(ic) = toLbl ;
486 if (isSymbolEqual(IC_FALSE(ic),fromLbl))
487 IC_FALSE(ic) = toLbl;
497 /*-----------------------------------------------------------------*/
498 /* iCodeFromeBBlock - convert basic block to iCode chain */
499 /*-----------------------------------------------------------------*/
500 iCode *iCodeFromeBBlock ( eBBlock **ebbs, int count)
503 iCode *ric = ebbs[0]->sch ;
504 iCode *lic = ebbs[0]->ech ;
506 for ( ; i < count; i++ ) {
507 if ( ebbs[i]->sch == NULL)
510 if ( ebbs[i]->noPath &&
511 (ebbs[i]->entryLabel != entryLabel &&
512 ebbs[i]->entryLabel != returnLabel )) {
513 werror(W_CODE_UNREACH,ebbs[i]->sch->filename,ebbs[i]->sch->lineno);
517 lic->next = ebbs[i]->sch ;
518 lic->next->prev = lic;
525 /*-----------------------------------------------------------------*/
526 /* otherPathsPresent - determines if there is a path from _entry */
527 /* to this block in a half constructed set of blocks */
528 /*-----------------------------------------------------------------*/
529 int otherPathsPresent (eBBlock **ebbs, eBBlock *this)
533 /* for all blocks preceding this block */
534 for ( i = 0 ; i < this->bbnum ; i++ ) {
537 /* if there is a reference to the entry label of this block */
538 for ( ic = ebbs[i]->sch ; ic ; ic = ic->next ) {
541 if (IC_LABEL(ic)->key == this->entryLabel->key)
547 if (IC_TRUE(ic)->key == this->entryLabel->key)
550 if (IC_FALSE(ic)->key == this->entryLabel->key)
557 /* comes here means we have not found it yet */
558 /* in this case check if the previous block */
559 /* ends in a goto if it does then we have no */
560 /* path else we have a path */
561 if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
562 ebbs[this->bbnum - 1]->ech->op == GOTO )