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 -------------------------------------------------------------------------*/
28 set *graphEdges = NULL ; /* list of edges in this flow graph */
31 /*-----------------------------------------------------------------*/
32 /* printEntryLabel - prints entry label of a ebblock */
33 /*-----------------------------------------------------------------*/
34 DEFSETFUNC(printEntryLabel)
38 fprintf (stdout," %-20s ",bp->entryLabel->name);
42 /*-----------------------------------------------------------------*/
43 /* neweBBlock - allocate & return a new extended basic block */
44 /*-----------------------------------------------------------------*/
45 eBBlock *neweBBlock ()
49 ALLOC(ebb,sizeof(eBBlock));
53 /*-----------------------------------------------------------------*/
54 /* newEdge - allocates & initialises an edge to given values */
55 /*-----------------------------------------------------------------*/
56 edge *newEdge (eBBlock *from, eBBlock *to)
60 ALLOC(ep,sizeof(edge));
67 /*-----------------------------------------------------------------*/
68 /* dumpEbbsToFileExt - writeall the basic blocks to a file */
69 /*-----------------------------------------------------------------*/
70 void dumpEbbsToFileExt (char *ext,eBBlock **ebbs, int count)
75 /* create the file name */
76 strcpy(buffer,srcFileName);
79 if (!(of = fopen(buffer,"a+"))) {
80 werror(E_FILE_OPEN_ERR,buffer);
84 for (i=0; i < count ; i++ ) {
85 fprintf(of,"\n----------------------------------------------------------------\n");
86 fprintf(of,"Basic Block %s : loop Depth = %d noPath = %d , lastinLoop = %d\n",
87 ebbs[i]->entryLabel->name,
90 ebbs[i]->isLastInLoop);
91 fprintf(of,"\ndefines bitVector :");
92 bitVectDebugOn(ebbs[i]->defSet,of);
93 fprintf(of,"\nlocal defines bitVector :");
94 bitVectDebugOn(ebbs[i]->ldefs,of);
95 fprintf(of,"\npointers Set bitvector :");
96 bitVectDebugOn(ebbs[i]->ptrsSet,of);
97 fprintf(of,"\n----------------------------------------------------------------\n");
98 printiCChain(ebbs[i]->sch,of);
103 /*-----------------------------------------------------------------*/
104 /* iCode2eBBlock - converts a sequnce till label to a ebb */
105 /*-----------------------------------------------------------------*/
106 eBBlock *iCode2eBBlock (iCode *ic)
109 eBBlock *ebb = neweBBlock(); /* a llocate an entry */
111 /* put the first one unconditionally */
114 /* if this is a label then */
116 ebb->entryLabel = ic->argLabel.label ;
118 sprintf(buffer,"_eBBlock%d",eBBNum++);
119 ebb->entryLabel = newSymbol(buffer,1);
120 ebb->entryLabel->key = labelKey++;
125 ic->op == JUMPTABLE ||
131 if ((ic->next && ic->next->op == LABEL) ||
133 ebb->ech = ebb->sch ;
137 /* loop thru till we find one with a label */
138 for ( loop = ic->next ; loop ; loop = loop->next ) {
140 /* if this is the last one */
143 /* if this is a function call */
144 if (loop->op == CALL || loop->op == PCALL) {
147 currFunc->hasFcall = 1;
150 /* if the next one is a label */
151 /* if this is a goto or ifx */
152 if (loop->next->op == LABEL ||
154 loop->op == JUMPTABLE ||
159 /* mark the end of the chain */
165 /*-----------------------------------------------------------------*/
166 /* eBBWithEntryLabel - finds the basic block with the entry label */
167 /*-----------------------------------------------------------------*/
168 eBBlock *eBBWithEntryLabel ( eBBlock **ebbs , symbol *eLabel, int count)
172 for ( i = 0 ; i < count ; i++ ) {
173 if (isSymbolEqual(ebbs[i]->entryLabel,eLabel))
181 /*-----------------------------------------------------------------*/
182 /* ifFromIs - will return 1 if the from block matches this */
183 /*-----------------------------------------------------------------*/
187 V_ARG(eBBlock *,this);
189 if (ep->from == this)
196 /*-----------------------------------------------------------------*/
197 /* edgesTo - returns a set of edges with to == supplied value */
198 /*-----------------------------------------------------------------*/
199 set *edgesTo ( eBBlock *to )
204 for (loop = setFirstItem(graphEdges) ; loop ; loop = setNextItem(graphEdges))
205 if (loop->to == to && !loop->from->noPath)
206 addSet(&result,loop->from);
212 /*-----------------------------------------------------------------*/
213 /* addiCodeToeBBlock - will add an iCode to the end of a block */
214 /*-----------------------------------------------------------------*/
215 void addiCodeToeBBlock ( eBBlock *ebp, iCode *ic , iCode *ip)
217 ic->prev = ic->next = NULL;
218 /* if the insert point is given */
220 ic->lineno = ip->lineno;
231 /* if the block has no instructions */
232 if (ebp->ech == NULL ) {
233 ebp->sch = ebp->ech = ic;
238 /* if the last instruction is a goto */
239 /* we add it just before the goto */
240 if ( ebp->ech->op == GOTO || ebp->ech->op == JUMPTABLE) {
241 ic->lineno = ebp->ech->lineno;
242 ic->prev = ebp->ech->prev;
245 if (!ic->prev) /* was the last only on in the block */
252 /* if the last one was a ifx statement we check to see */
253 /* if the condition was defined in the previous instruction */
254 /* if this is true then we put it before the condition else */
255 /* we put it before if, this is to reduce register pressure,*/
256 /* we don't have to hold condition too long in a register */
257 if ( ebp->ech->op == IFX ) {
260 /* if ( !ebp->ech->prev ) */
261 /* ipoint = ebp->ech ; */
263 /* if (!IC_RESULT(ebp->ech->prev)) */
264 /* ipoint = ebp->ech ; */
266 /* if (IC_COND(ebp->ech)->key == IC_RESULT(ebp->ech->prev)->key) */
267 /* ipoint = ebp->ech->prev; */
269 /* ipoint = ebp->ech ; */
271 ic->lineno = ipoint->lineno;
272 ic->prev = ipoint->prev;
282 /* will add it to the very end */
292 /*-----------------------------------------------------------------*/
293 /* remiCodeFromeBBlock - remove an iCode from BBlock */
294 /*-----------------------------------------------------------------*/
295 void remiCodeFromeBBlock (eBBlock *ebb, iCode *ic)
298 ic->prev->next = ic->next ;
300 ebb->sch = ic->next ;
303 ic->next->prev = ic->prev;
308 /*-----------------------------------------------------------------*/
309 /* iCodeBreakDown : breakDown iCode chain to blocks */
310 /*-----------------------------------------------------------------*/
311 eBBlock **iCodeBreakDown (iCode *ic, int *count)
313 eBBlock **ebbs = NULL ;
318 /* allocate for the first entry */
319 ALLOC(ebbs,sizeof(eBBlock **));
323 /* convert 2 block */
324 eBBlock *ebb = iCode2eBBlock(loop);
325 loop = ebb->ech->next ;
327 ebb->ech->next = NULL ; /* mark the end of this chain */
330 ebb->bbnum = *count ; /* save this block number */
331 /* put it in the array */
332 ebbs[(*count)++] = ebb ;
334 /* allocate for the next one */
335 if (!(ebbs = GC_realloc(ebbs,(*count + 1)*sizeof(eBBlock **)))) {
336 werror(E_OUT_OF_MEM,__FILE__,(*count + 1)*sizeof(eBBlock **));
340 /* if this one ends in a goto or a conditional */
341 /* branch then check if the block it is going */
342 /* to already exists, if yes then this could */
343 /* be a loop, add a preheader to the block it */
344 /* goes to if it does not already have one */
345 if (ebbs[(*count) - 1]->ech &&
346 (ebbs[(*count) - 1]->ech->op == GOTO ||
347 ebbs[(*count) - 1]->ech->op == IFX )) {
352 if (ebbs[(*count) - 1]->ech->op == GOTO)
353 label = IC_LABEL(ebbs[(*count)-1]->ech);
355 if (!(label = IC_TRUE(ebbs[(*count)-1]->ech)))
356 label = IC_FALSE(ebbs[(*count)-1]->ech);
358 if ((destBlock = eBBWithEntryLabel(ebbs,label,(*count))) &&
359 destBlock->preHeader == NULL &&
360 otherPathsPresent(ebbs,destBlock) ) {
362 symbol *preHeaderLabel = newiTempPreheaderLabel();
366 /* go thru all block replacing the entryLabel with new label */
367 /* till we reach the block , then we insert a new ebblock */
368 for ( i = 0 ; i < (*count) ; i++ ) {
369 if ( ebbs[i] == destBlock )
371 replaceLabel(ebbs[i],label,preHeaderLabel);
375 /* if we have stopped at the block , allocate for an extra one */
376 if (!(ebbs = GC_realloc(ebbs,(*count + 1)*sizeof(eBBlock **)))) {
377 werror(E_OUT_OF_MEM,__FILE__,(*count + 1)*sizeof(eBBlock **));
381 /* then move the block down one count */
382 pBlock = ebbs[j = i];
383 for ( i += 1; i < (*count) ; i++ ) {
392 destBlock->preHeader = ebbs[j] = neweBBlock();
394 ebbs[j]->entryLabel = preHeaderLabel ;
395 ebbs[j]->sch = ebbs[j]->ech = newiCodeLabelGoto(LABEL,preHeaderLabel);
396 ebbs[j]->sch->lineno = destBlock->sch->lineno;
402 ebbs[*count] = NULL ;
407 /*-----------------------------------------------------------------*/
408 /* replaceSymBySym : - replace operand by operand in blocks */
409 /* replaces only left & right in blocks */
410 /*-----------------------------------------------------------------*/
411 void replaceSymBySym (set *sset, operand *src, operand *dest)
416 /* for all blocks in the set do */
417 for ( loop = sset ; loop ; loop = loop->next) {
420 rBlock = loop->item ;
421 /* for all instructions in this block do */
422 for ( ic = rBlock->sch ; ic ; ic = ic->next ) {
424 /* if we find usage */
425 if (ic->op == IFX && isOperandEqual(src,IC_COND(ic))) {
426 bitVectUnSetBit (OP_USES(IC_COND(ic)),ic->key);
427 IC_COND(ic) = operandFromOperand(dest);
428 OP_USES(dest) = bitVectSetBit (OP_USES(dest),ic->key);
432 if (isOperandEqual(IC_RIGHT(ic),src)) {
433 bitVectUnSetBit (OP_USES(IC_RIGHT(ic)),ic->key);
434 IC_RIGHT(ic) = operandFromOperand(dest);
435 IC_RIGHT(ic)->isaddr = 0;
436 OP_USES(dest) = bitVectSetBit (OP_USES(dest),ic->key);
439 if (isOperandEqual(IC_LEFT(ic),src)) {
440 bitVectUnSetBit (OP_USES(IC_LEFT(ic)),ic->key);
441 if (POINTER_GET(ic) && IS_ITEMP(dest)) {
442 IC_LEFT(ic) = operandFromOperand(dest);
443 IC_LEFT(ic)->isaddr = 1;
445 IC_LEFT(ic) = operandFromOperand(dest);
446 IC_LEFT(ic)->isaddr = 0;
448 OP_USES(dest) = bitVectSetBit (OP_USES(dest),ic->key);
451 /* special case for pointer sets */
452 if (POINTER_SET(ic) &&
453 isOperandEqual(IC_RESULT(ic),src)) {
454 bitVectUnSetBit (OP_USES(IC_RESULT(ic)),ic->key);
455 IC_RESULT(ic) = operandFromOperand(dest);
456 IC_RESULT(ic)->isaddr = 1;
457 OP_USES(dest) = bitVectSetBit(OP_USES(dest),ic->key);
463 /*-----------------------------------------------------------------*/
464 /* replaceLabel - replace reference to one label by another */
465 /*-----------------------------------------------------------------*/
466 void replaceLabel(eBBlock *ebp, symbol *fromLbl, symbol *toLbl)
473 for (ic = ebp->sch ; ic ; ic = ic->next ) {
477 if (isSymbolEqual(IC_LABEL(ic),fromLbl))
478 IC_LABEL(ic) = toLbl;
482 if (IC_TRUE(ic) && isSymbolEqual(IC_TRUE(ic),fromLbl))
483 IC_TRUE(ic) = toLbl ;
485 if (isSymbolEqual(IC_FALSE(ic),fromLbl))
486 IC_FALSE(ic) = toLbl;
496 /*-----------------------------------------------------------------*/
497 /* iCodeFromeBBlock - convert basic block to iCode chain */
498 /*-----------------------------------------------------------------*/
499 iCode *iCodeFromeBBlock ( eBBlock **ebbs, int count)
502 iCode *ric = ebbs[0]->sch ;
503 iCode *lic = ebbs[0]->ech ;
505 for ( ; i < count; i++ ) {
506 if ( ebbs[i]->sch == NULL)
509 if ( ebbs[i]->noPath &&
510 (ebbs[i]->entryLabel != entryLabel &&
511 ebbs[i]->entryLabel != returnLabel )) {
512 werror(W_CODE_UNREACH,ebbs[i]->sch->filename,ebbs[i]->sch->lineno);
516 lic->next = ebbs[i]->sch ;
517 lic->next->prev = lic;
524 /*-----------------------------------------------------------------*/
525 /* otherPathsPresent - determines if there is a path from _entry */
526 /* to this block in a half constructed set of blocks */
527 /*-----------------------------------------------------------------*/
528 int otherPathsPresent (eBBlock **ebbs, eBBlock *this)
532 /* for all blocks preceding this block */
533 for ( i = 0 ; i < this->bbnum ; i++ ) {
536 /* if there is a reference to the entry label of this block */
537 for ( ic = ebbs[i]->sch ; ic ; ic = ic->next ) {
540 if (IC_LABEL(ic)->key == this->entryLabel->key)
546 if (IC_TRUE(ic)->key == this->entryLabel->key)
549 if (IC_FALSE(ic)->key == this->entryLabel->key)
556 /* comes here means we have not found it yet */
557 /* in this case check if the previous block */
558 /* ends in a goto if it does then we have no */
559 /* path else we have a path */
560 if (this->bbnum && ebbs[this->bbnum - 1]->ech &&
561 ebbs[this->bbnum - 1]->ech->op == GOTO )