1 /*-------------------------------------------------------------------------
2 SDCCBBlock.c - routines to manipulate basic Blocks
4 Written By - Sandeep Dutta . sandeep.dutta@usa.net (1998)
6 This program is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
20 In other words, you are welcome to use, share and improve this program.
21 You are forbidden to forbid anyone else to use, share and improve
22 what you give them. Help stamp out software-hoarding!
23 -------------------------------------------------------------------------*/
27 #include "SDCCglobl.h"
31 #include "SDCChasht.h"
34 #include "SDCCicode.h"
35 #include "SDCCBBlock.h"
39 set *graphEdges = NULL ; /* list of edges in this flow graph */
42 /*-----------------------------------------------------------------*/
43 /* printEntryLabel - prints entry label of a ebblock */
44 /*-----------------------------------------------------------------*/
45 DEFSETFUNC(printEntryLabel)
49 fprintf (stdout," %-20s ",bp->entryLabel->name);
53 /*-----------------------------------------------------------------*/
54 /* neweBBlock - allocate & return a new extended basic block */
55 /*-----------------------------------------------------------------*/
56 eBBlock *neweBBlock ()
60 ALLOC(ebb,sizeof(eBBlock));
64 /*-----------------------------------------------------------------*/
65 /* newEdge - allocates & initialises an edge to given values */
66 /*-----------------------------------------------------------------*/
67 edge *newEdge (eBBlock *from, eBBlock *to)
71 ALLOC(ep,sizeof(edge));
78 /*-----------------------------------------------------------------*/
79 /* dumpEbbsToFileExt - writeall the basic blocks to a file */
80 /*-----------------------------------------------------------------*/
81 void dumpEbbsToFileExt (char *ext,eBBlock **ebbs, int count)
86 /* create the file name */
87 strcpy(buffer,srcFileName);
90 if (!(of = fopen(buffer,"a+"))) {
91 werror(E_FILE_OPEN_ERR,buffer);
95 for (i=0; i < count ; i++ ) {
96 fprintf(of,"\n----------------------------------------------------------------\n");
97 fprintf(of,"Basic Block %s : loop Depth = %d noPath = %d , lastinLoop = %d\n",
98 ebbs[i]->entryLabel->name,
101 ebbs[i]->isLastInLoop);
102 fprintf(of,"\ndefines bitVector :");
103 bitVectDebugOn(ebbs[i]->defSet,of);
104 fprintf(of,"\nlocal defines bitVector :");
105 bitVectDebugOn(ebbs[i]->ldefs,of);
106 fprintf(of,"\npointers Set bitvector :");
107 bitVectDebugOn(ebbs[i]->ptrsSet,of);
108 fprintf(of,"\n----------------------------------------------------------------\n");
109 printiCChain(ebbs[i]->sch,of);
114 /*-----------------------------------------------------------------*/
115 /* iCode2eBBlock - converts a sequnce till label to a ebb */
116 /*-----------------------------------------------------------------*/
117 eBBlock *iCode2eBBlock (iCode *ic)
120 eBBlock *ebb = neweBBlock(); /* a llocate an entry */
122 /* put the first one unconditionally */
125 /* if this is a label then */
127 ebb->entryLabel = ic->argLabel.label ;
129 sprintf(buffer,"_eBBlock%d",eBBNum++);
130 ebb->entryLabel = newSymbol(buffer,1);
131 ebb->entryLabel->key = labelKey++;
136 ic->op == JUMPTABLE ||
142 if ((ic->next && ic->next->op == LABEL) ||
144 ebb->ech = ebb->sch ;
148 /* loop thru till we find one with a label */
149 for ( loop = ic->next ; loop ; loop = loop->next ) {
151 /* if this is the last one */
154 /* if this is a function call */
155 if (loop->op == CALL || loop->op == PCALL) {
158 currFunc->hasFcall = 1;
161 /* if the next one is a label */
162 /* if this is a goto or ifx */
163 if (loop->next->op == LABEL ||
165 loop->op == JUMPTABLE ||
170 /* mark the end of the chain */
176 /*-----------------------------------------------------------------*/
177 /* eBBWithEntryLabel - finds the basic block with the entry label */
178 /*-----------------------------------------------------------------*/
179 eBBlock *eBBWithEntryLabel ( eBBlock **ebbs , symbol *eLabel, int count)
183 for ( i = 0 ; i < count ; i++ ) {
184 if (isSymbolEqual(ebbs[i]->entryLabel,eLabel))
192 /*-----------------------------------------------------------------*/
193 /* ifFromIs - will return 1 if the from block matches this */
194 /*-----------------------------------------------------------------*/
198 V_ARG(eBBlock *,this);
200 if (ep->from == this)
207 /*-----------------------------------------------------------------*/
208 /* edgesTo - returns a set of edges with to == supplied value */
209 /*-----------------------------------------------------------------*/
210 set *edgesTo ( eBBlock *to )
215 for (loop = setFirstItem(graphEdges) ; loop ; loop = setNextItem(graphEdges))
216 if (loop->to == to && !loop->from->noPath)
217 addSet(&result,loop->from);
223 /*-----------------------------------------------------------------*/
224 /* addiCodeToeBBlock - will add an iCode to the end of a block */
225 /*-----------------------------------------------------------------*/
226 void addiCodeToeBBlock ( eBBlock *ebp, iCode *ic , iCode *ip)
228 ic->prev = ic->next = NULL;
229 /* if the insert point is given */
231 ic->lineno = ip->lineno;
242 /* if the block has no instructions */
243 if (ebp->ech == NULL ) {
244 ebp->sch = ebp->ech = ic;
249 /* if the last instruction is a goto */
250 /* we add it just before the goto */
251 if ( ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE) {
252 ic->lineno = ebp->ech->lineno;
253 ic->prev = ebp->ech->prev;
256 if (!ic->prev) /* was the last only on in the block */
263 /* if the last one was a ifx statement we check to see */
264 /* if the condition was defined in the previous instruction */
265 /* if this is true then we put it before the condition else */
266 /* we put it before if, this is to reduce register pressure,*/
267 /* we don't have to hold condition too long in a register */
268 if ( ebp->ech->op == IFX ) {
271 /* if ( !ebp->ech->prev ) */
272 /* ipoint = ebp->ech ; */
274 /* if (!IC_RESULT(ebp->ech->prev)) */
275 /* ipoint = ebp->ech ; */
277 /* if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
278 /* ipoint = ebp->ech->prev; */
280 /* ipoint = ebp->ech ; */
282 ic->lineno = ipoint->lineno;
283 ic->prev = ipoint->prev;
293 /* will add it to the very end */
303 /*-----------------------------------------------------------------*/
304 /* remiCodeFromeBBlock - remove an iCode from BBlock */
305 /*-----------------------------------------------------------------*/
306 void remiCodeFromeBBlock (eBBlock *ebb, iCode *ic)
309 ic->prev->next = ic->next ;
311 ebb->sch = ic->next ;
314 ic->next->prev = ic->prev;
319 /*-----------------------------------------------------------------*/
320 /* iCodeBreakDown : breakDown iCode chain to blocks */
321 /*-----------------------------------------------------------------*/
322 eBBlock **iCodeBreakDown (iCode *ic, int *count)
324 eBBlock **ebbs = NULL ;
329 /* allocate for the first entry */
330 ALLOC(ebbs,sizeof(eBBlock **));
334 /* convert 2 block */
335 eBBlock *ebb = iCode2eBBlock(loop);
336 loop = ebb->ech->next ;
338 ebb->ech->next = NULL ; /* mark the end of this chain */
341 ebb->bbnum = *count ; /* save this block number */
342 /* put it in the array */
343 ebbs[(*count)++] = ebb ;
345 /* allocate for the next one */
346 if (!(ebbs = GC_realloc(ebbs,(*count + 1)*sizeof(eBBlock **)))) {
347 werror(E_OUT_OF_MEM,__FILE__,(*count + 1)*sizeof(eBBlock **));
351 /* if this one ends in a goto or a conditional */
352 /* branch then check if the block it is going */
353 /* to already exists, if yes then this could */
354 /* be a loop, add a preheader to the block it */
355 /* goes to if it does not already have one */
356 if (ebbs[(*count) - 1]->ech &&
357 (ebbs[(*count) - 1]->ech->op == GOTO ||
358 ebbs[(*count) - 1]->ech->op == IFX )) {
363 if (ebbs[(*count) - 1]->ech->op == GOTO)
364 label = IC_LABEL(ebbs[(*count)-1]->ech);
366 if (!(label = IC_TRUE(ebbs[(*count)-1]->ech)))
367 label = IC_FALSE(ebbs[(*count)-1]->ech);
369 if ((destBlock = eBBWithEntryLabel(ebbs,label,(*count))) &&
370 destBlock->preHeader == NULL &&
371 otherPathsPresent(ebbs,destBlock) ) {
373 symbol *preHeaderLabel = newiTempPreheaderLabel();
377 /* go thru all block replacing the entryLabel with new label */
378 /* till we reach the block , then we insert a new ebblock */
379 for ( i = 0 ; i < (*count) ; i++ ) {
380 if ( ebbs[i] == destBlock )
382 replaceLabel(ebbs[i],label,preHeaderLabel);
386 /* if we have stopped at the block , allocate for an extra one */
387 if (!(ebbs = GC_realloc(ebbs,(*count + 1)*sizeof(eBBlock **)))) {
388 werror(E_OUT_OF_MEM,__FILE__,(*count + 1)*sizeof(eBBlock **));
392 /* then move the block down one count */
393 pBlock = ebbs[j = i];
394 for ( i += 1; i < (*count) ; i++ ) {
403 destBlock->preHeader = ebbs[j] = neweBBlock();
405 ebbs[j]->entryLabel = preHeaderLabel ;
406 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto(LABEL,preHeaderLabel);
407 ebbs[j]->sch->lineno = destBlock->sch->lineno;
413 ebbs[*count] = NULL ;
418 /*-----------------------------------------------------------------*/
419 /* replaceSymBySym : - replace operand by operand in blocks */
420 /* replaces only left & right in blocks */
421 /*-----------------------------------------------------------------*/
422 void replaceSymBySym (set *sset, operand *src, operand *dest)
427 /* for all blocks in the set do */
428 for ( loop = sset ; loop ; loop = loop->next) {
431 rBlock = loop->item ;
432 /* for all instructions in this block do */
433 for ( ic = rBlock->sch ; ic ; ic = ic->next ) {
435 /* if we find usage */
436 if (ic->op == IFX && isOperandEqual(src,IC_COND(ic))) {
437 bitVectUnSetBit (OP_USES(IC_COND(ic)),ic->key);
438 IC_COND(ic) = operandFromOperand(dest);
439 OP_USES(dest) = bitVectSetBit (OP_USES(dest),ic->key);
443 if (isOperandEqual(IC_RIGHT(ic),src)) {
444 bitVectUnSetBit (OP_USES(IC_RIGHT(ic)),ic->key);
445 IC_RIGHT(ic) = operandFromOperand(dest);
446 IC_RIGHT(ic)->isaddr = 0;
447 OP_USES(dest) = bitVectSetBit (OP_USES(dest),ic->key);
450 if (isOperandEqual(IC_LEFT(ic),src)) {
451 bitVectUnSetBit (OP_USES(IC_LEFT(ic)),ic->key);
452 if (POINTER_GET(ic) && IS_ITEMP(dest)) {
453 IC_LEFT(ic) = operandFromOperand(dest);
454 IC_LEFT(ic)->isaddr = 1;
456 IC_LEFT(ic) = operandFromOperand(dest);
457 IC_LEFT(ic)->isaddr = 0;
459 OP_USES(dest) = bitVectSetBit (OP_USES(dest),ic->key);
462 /* special case for pointer sets */
463 if (POINTER_SET(ic) &&
464 isOperandEqual(IC_RESULT(ic),src)) {
465 bitVectUnSetBit (OP_USES(IC_RESULT(ic)),ic->key);
466 IC_RESULT(ic) = operandFromOperand(dest);
467 IC_RESULT(ic)->isaddr = 1;
468 OP_USES(dest) = bitVectSetBit(OP_USES(dest),ic->key);
474 /*-----------------------------------------------------------------*/
475 /* replaceLabel - replace reference to one label by another */
476 /*-----------------------------------------------------------------*/
477 void replaceLabel(eBBlock *ebp, symbol *fromLbl, symbol *toLbl)
484 for (ic = ebp->sch ; ic ; ic = ic->next ) {
488 if (isSymbolEqual(IC_LABEL(ic),fromLbl))
489 IC_LABEL(ic) = toLbl;
493 if (IC_TRUE(ic) && isSymbolEqual(IC_TRUE(ic),fromLbl))
494 IC_TRUE(ic) = toLbl ;
496 if (isSymbolEqual(IC_FALSE(ic),fromLbl))
497 IC_FALSE(ic) = toLbl;
507 /*-----------------------------------------------------------------*/
508 /* iCodeFromeBBlock - convert basic block to iCode chain */
509 /*-----------------------------------------------------------------*/
510 iCode *iCodeFromeBBlock ( eBBlock **ebbs, int count)
513 iCode *ric = ebbs[0]->sch ;
514 iCode *lic = ebbs[0]->ech ;
516 for ( ; i < count; i++ ) {
517 if ( ebbs[i]->sch == NULL)
520 if ( ebbs[i]->noPath &&
521 (ebbs[i]->entryLabel != entryLabel &&
522 ebbs[i]->entryLabel != returnLabel )) {
523 werror(W_CODE_UNREACH,ebbs[i]->sch->filename,ebbs[i]->sch->lineno);
527 lic->next = ebbs[i]->sch ;
528 lic->next->prev = lic;
535 /*-----------------------------------------------------------------*/
536 /* otherPathsPresent - determines if there is a path from _entry */
537 /* to this block in a half constructed set of blocks */
538 /*-----------------------------------------------------------------*/
539 int otherPathsPresent (eBBlock **ebbs, eBBlock *this)
543 /* for all blocks preceding this block */
544 for ( i = 0 ; i < this->bbnum ; i++ ) {
547 /* if there is a reference to the entry label of this block */
548 for ( ic = ebbs[i]->sch ; ic ; ic = ic->next ) {
551 if (IC_LABEL(ic)->key == this->entryLabel->key)
557 if (IC_TRUE(ic)->key == this->entryLabel->key)
560 if (IC_FALSE(ic)->key == this->entryLabel->key)
567 /* comes here means we have not found it yet */
568 /* in this case check if the previous block */
569 /* ends in a goto if it does then we have no */
570 /* path else we have a path */
571 if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
572 ebbs[this->bbnum - 1]->ech->op == GOTO )