From 4ce4ccfc2eb165c16b1636756493120423a7c170 Mon Sep 17 00:00:00 2001 From: epetrich Date: Tue, 25 Nov 2003 04:57:05 +0000 Subject: [PATCH] Fixed several common-sub-expression bugs (#772861, #768380, & #755323) * src/SDCCdflow.c * src/SDCCcse.c * src/SDCCcse.h * src/SDCCBBlock.h * src/SDCCBBlock.c git-svn-id: https://sdcc.svn.sourceforge.net/svnroot/sdcc/trunk/sdcc@3026 4a8a32a2-be11-0410-ad9d-d568d2c75423 --- ChangeLog | 9 +++++ src/SDCCBBlock.c | 24 ++++++++++++ src/SDCCBBlock.h | 1 + src/SDCCcse.c | 100 ++++++++++++++++++++++++++++++++++++++++++----- src/SDCCcse.h | 3 +- src/SDCCdflow.c | 42 +++++++++++--------- 6 files changed, 151 insertions(+), 28 deletions(-) diff --git a/ChangeLog b/ChangeLog index f9ad25cf..74a856ca 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,12 @@ +2003-11-25 Erik Petrich + + Fixed several common-sub-expression bugs (#772861, #768380, & #755323) + * src/SDCCdflow.c + * src/SDCCcse.c + * src/SDCCcse.h + * src/SDCCBBlock.h + * src/SDCCBBlock.c + 2003-11-23 Klaus Flittner fixed bug #845089 diff --git a/src/SDCCBBlock.c b/src/SDCCBBlock.c index 10053301..660eb907 100644 --- a/src/SDCCBBlock.c +++ b/src/SDCCBBlock.c @@ -178,6 +178,7 @@ dumpEbbsToFileExt (int id, eBBlock ** ebbs, int count) FILE *of; int i; eBBlock *bb; + set *cseSet; if (id) { of=createDumpFile(id); @@ -230,6 +231,29 @@ dumpEbbsToFileExt (int id, eBBlock ** ebbs, int count) fprintf (of, "\nInductions Set bitvector :"); bitVectDebugOn (ebbs[i]->linds, of); } + + fprintf (of, "\ninExprs:"); + for (cseSet = ebbs[i]->inExprs; cseSet; cseSet=cseSet->next) { + cseDef *item=cseSet->item; + fprintf (of, " %s(%d)",OP_SYMBOL(item->sym)->name,item->diCode->key); + if (item->fromGlobal) + fprintf (of, "g"); + } + fprintf (of, "\noutExprs:"); + for (cseSet = ebbs[i]->outExprs; cseSet; cseSet=cseSet->next) { + cseDef *item=cseSet->item; + fprintf (of, " %s(%d)",OP_SYMBOL(item->sym)->name,item->diCode->key); + if (item->fromGlobal) + fprintf (of, "g"); + } + fprintf (of, "\nkilledExprs:"); + for (cseSet = ebbs[i]->killedExprs; cseSet; cseSet=cseSet->next) { + cseDef *item=cseSet->item; + fprintf (of, " %s(%d)",OP_SYMBOL(item->sym)->name,item->diCode->key); + if (item->fromGlobal) + fprintf (of, "g"); + } + fprintf (of, "\n----------------------------------------------------------------\n"); printiCChain (ebbs[i]->sch, of); } diff --git a/src/SDCCBBlock.h b/src/SDCCBBlock.h index 68c29061..8f0429c7 100644 --- a/src/SDCCBBlock.h +++ b/src/SDCCBBlock.h @@ -56,6 +56,7 @@ typedef struct eBBlock /* data flow analysis */ set *inExprs; /* in coming common expressions */ set *outExprs; /* out going common expressions */ + set *killedExprs; /* killed common expressions */ bitVect *inDefs; /* in coming defintions */ bitVect *outDefs; /* out going defintions */ bitVect *defSet; /* symbols defined in block */ diff --git a/src/SDCCcse.c b/src/SDCCcse.c index b6bd46ed..a8b55610 100644 --- a/src/SDCCcse.c +++ b/src/SDCCcse.c @@ -40,10 +40,65 @@ newCseDef (operand * sym, iCode * ic) cdp->sym = sym; cdp->diCode = ic; cdp->key = sym->key; + cdp->ancestors = newBitVect(iCodeKey); + cdp->fromGlobal = 0; + if (ic->op!=IF && ic->op!=JUMPTABLE) + { + if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic))) + { + bitVectSetBit (cdp->ancestors, IC_LEFT (ic)->key); + cdp->fromGlobal |= isOperandGlobal (IC_LEFT (ic)); + } + if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic))) + { + bitVectSetBit (cdp->ancestors, IC_RIGHT (ic)->key); + cdp->fromGlobal |= isOperandGlobal (IC_RIGHT (ic)); + } + } + return cdp; } +void +updateCseDefAncestors(cseDef *cdp, set * cseSet) +{ + cseDef *loop; + set *sl; + iCode *ic = cdp->diCode; + + if (ic->op!=IF && ic->op!=JUMPTABLE) + { + if (IC_LEFT (ic) && IS_SYMOP (IC_LEFT (ic))) + { + bitVectSetBit (cdp->ancestors, IC_LEFT (ic)->key); + for (sl = cseSet; sl; sl = sl->next) + { + loop = sl->item; + if (loop->sym->key == IC_LEFT (ic)->key) + { + cdp->ancestors = bitVectUnion (cdp->ancestors, loop->ancestors); + cdp->fromGlobal |= loop->fromGlobal; + break; + } + } + } + if (IC_RIGHT (ic) && IS_SYMOP (IC_RIGHT (ic))) + { + bitVectSetBit (cdp->ancestors, IC_RIGHT (ic)->key); + for (sl = cseSet; sl; sl = sl->next) + { + loop = sl->item; + if (loop->sym->key == IC_RIGHT (ic)->key) + { + cdp->ancestors = bitVectUnion (cdp->ancestors, loop->ancestors); + cdp->fromGlobal |= loop->fromGlobal; + break; + } + } + } + } +} /*-----------------------------------------------------------------*/ @@ -457,6 +512,16 @@ DEFSETFUNC (ifAssignedFromGlobal) return 0; } +/*-------------------------------------------------------------------*/ +/* ifFromGlobal - if definition is derived from global */ +/*-------------------------------------------------------------------*/ +DEFSETFUNC (ifFromGlobal) +{ + cseDef *cdp = item; + + return cdp->fromGlobal; +} + /*-----------------------------------------------------------------*/ /* ifDefGlobal - if definition is global */ /*-----------------------------------------------------------------*/ @@ -487,7 +552,9 @@ DEFSETFUNC (ifOperandsHave) cseDef *cdp = item; V_ARG (operand *, op); - + if (bitVectBitValue(cdp->ancestors, op->key)) + return 1; + if (IC_LEFT (cdp->diCode) && IS_SYMOP (IC_LEFT (cdp->diCode)) && IC_LEFT (cdp->diCode)->key == op->key) @@ -543,12 +610,17 @@ DEFSETFUNC (ifDefSymIsX) { cseDef *cdp = item; V_ARG (operand *, op); - + int match; + if (op && cdp->sym) - return cdp->sym->key == op->key; + match = cdp->sym->key == op->key; else - return (isOperandEqual (cdp->sym, op)); - + match = (isOperandEqual (cdp->sym, op)); + #if 0 + if (match) + printf("%s ",OP_SYMBOL(cdp->sym)->name); + #endif + return match; } @@ -1548,6 +1620,7 @@ deleteGetPointers (set ** cseSet, set ** pss, operand * op, eBBlock * ebb) { ebb->ptrsSet = bitVectSetBit (ebb->ptrsSet, cop->key); deleteItemIf (cseSet, ifPointerGet, cop); + deleteItemIf (cseSet, ifDefSymIsX, cop); deleteItemIf (pss, ifPointerSet, cop); } } @@ -1679,6 +1752,7 @@ cseBBlock (eBBlock * ebb, int computeOnly, int change = 0; int i; set *ptrSetSet = NULL; + cseDef *expr; /* if this block is not reachable */ if (ebb->noPath) @@ -1719,7 +1793,7 @@ cseBBlock (eBBlock * ebb, int computeOnly, IS_PTR (operandType (IC_RESULT (ic)))) { ptrPostIncDecOpt (ic); - } + } /* clear the def & use chains for the operands involved */ /* in this operation . since it can change due to opts */ @@ -1739,8 +1813,8 @@ cseBBlock (eBBlock * ebb, int computeOnly, since they can be modified by the function call */ deleteItemIf (&cseSet, ifDefGlobal); - /* and also itemps assigned from globals */ - deleteItemIf (&cseSet, ifAssignedFromGlobal); + /* and also itemps derived from globals */ + deleteItemIf (&cseSet, ifFromGlobal); /* delete all getpointer iCodes from cseSet, this should be done only for global arrays & pointers but at this @@ -1973,8 +2047,11 @@ cseBBlock (eBBlock * ebb, int computeOnly, } if (!(POINTER_SET (ic)) && IC_RESULT (ic)) { + cseDef *csed; deleteItemIf (&cseSet, ifDefSymIsX, IC_RESULT (ic)); - addSetHead (&cseSet, newCseDef (IC_RESULT (ic), ic)); + csed = newCseDef (IC_RESULT (ic), ic); + updateCseDefAncestors (csed, cseSet); + addSetHead (&cseSet, csed); } defic = ic; @@ -2076,6 +2153,11 @@ cseBBlock (eBBlock * ebb, int computeOnly, } } + for (expr=setFirstItem (ebb->inExprs); expr; expr=setNextItem (ebb->inExprs)) + if (!isinSetWith (cseSet, expr, isCseDefEqual) && + !isinSetWith (ebb->killedExprs, expr, isCseDefEqual)) { + addSetHead (&ebb->killedExprs, expr); + } setToNull ((void *) &ebb->outExprs); ebb->outExprs = cseSet; ebb->outDefs = bitVectUnion (ebb->outDefs, ebb->defSet); diff --git a/src/SDCCcse.h b/src/SDCCcse.h index 374bb5cf..88684378 100644 --- a/src/SDCCcse.h +++ b/src/SDCCcse.h @@ -34,7 +34,8 @@ typedef struct cseDef unsigned int key; operand *sym; /* defining symbol */ iCode *diCode; /* defining instruction */ - + bitVect *ancestors; /* keys of the symbol's ancestors */ + int fromGlobal:1; /* defining symbol's value computed from a global */ } cseDef; diff --git a/src/SDCCdflow.c b/src/SDCCdflow.c index ab44c752..a4cee93d 100644 --- a/src/SDCCdflow.c +++ b/src/SDCCdflow.c @@ -82,6 +82,10 @@ DEFSETFUNC (ifKilledInBlock) (IS_SYMOP (IC_RIGHT (cdp->diCode)) && bitVectBitsInCommon (src->defSet, OP_DEFS (IC_RIGHT (cdp->diCode)))))) return 1; + + /* kill if cseBBlock() found a case we missed here */ + if (isinSetWith(src->killedExprs, cdp, isCseDefEqual)) + return 1; return 0; } @@ -95,6 +99,8 @@ DEFSETFUNC (mergeInExprs) V_ARG (eBBlock *, dest); V_ARG (int *, firstTime); + dest->killedExprs = unionSets (dest->killedExprs, ebp->killedExprs, THROW_DEST); + /* if in the dominator list then */ if (bitVectBitValue (dest->domVect, ebp->bbnum) && dest != ebp) { @@ -117,26 +123,17 @@ DEFSETFUNC (mergeInExprs) } else { - cseDef *expr; - - /* cseBBlock does a much more thorough analysis than */ - /* ifKilledInBlock. Anything that is listed in inExprs */ - /* but not in outExprs must have been killed somehow. */ - for (expr=setFirstItem(ebp->inExprs); expr; expr=setNextItem(ebp->inExprs)) - if (!isinSet(ebp->outExprs, expr)) - deleteSetItem (&dest->inExprs, expr); - - /* delete only if killed in this block */ + /* delete only if killed in this block*/ deleteItemIf (&dest->inExprs, ifKilledInBlock, ebp); /* union the ndompset with pointers set in this block */ dest->ndompset = bitVectUnion (dest->ndompset, ebp->ptrsSet); } - *firstTime = 0; return 0; } + /*-----------------------------------------------------------------*/ /* mergeInDefs - merge in incoming definitions */ /*-----------------------------------------------------------------*/ @@ -169,10 +166,12 @@ computeDataFlow (eBBlock ** ebbs, int count) { int i; int change = 1; - + + for (i = 0; i < count; i++) + ebbs[i]->killedExprs = NULL; + while (change) { - change = 0; /* for all blocks */ @@ -181,6 +180,7 @@ computeDataFlow (eBBlock ** ebbs, int count) set *pred; set *oldOutExprs = NULL; + set *oldKilledExprs = NULL; bitVect *oldOutDefs = NULL; int firstTime; eBBlock *pBlock; @@ -196,7 +196,10 @@ computeDataFlow (eBBlock ** ebbs, int count) /* make a copy of the outExpressions or outDefs : to be */ /* used for iteration */ if (optimize.global_cse) - oldOutExprs = setFromSet (ebbs[i]->outExprs); + { + oldOutExprs = setFromSet (ebbs[i]->outExprs); + oldKilledExprs = setFromSet (ebbs[i]->killedExprs); + } else oldOutDefs = bitVectCopy (ebbs[i]->outDefs); setToNull ((void *) &ebbs[i]->inDefs); @@ -224,7 +227,7 @@ computeDataFlow (eBBlock ** ebbs, int count) if (idom) addSetHead (&pred, idom); } - + /* figure out the incoming expressions */ /* this is a little more complex */ setToNull ((void *) &ebbs[i]->inExprs); @@ -241,13 +244,16 @@ computeDataFlow (eBBlock ** ebbs, int count) /* if it change we will need to iterate */ if (optimize.global_cse) - change += !isSetsEqualWith (ebbs[i]->outExprs, oldOutExprs, isCseDefEqual); + { + change += !isSetsEqualWith (ebbs[i]->outExprs, oldOutExprs, isCseDefEqual); + change += !isSetsEqualWith (ebbs[i]->killedExprs, oldKilledExprs, isCseDefEqual); + } else change += !bitVectEqual (ebbs[i]->outDefs, oldOutDefs); } - if (!change) /* iterate till no change */ - break; + if (!change) /* iterate till no change */ + break; } return; -- 2.30.2