From b078b0f4acc141630d9590672ef1e06d4a850d1b Mon Sep 17 00:00:00 2001 From: bernhardheld Date: Fri, 3 Oct 2003 22:11:42 +0000 Subject: [PATCH] Applied liferange patch from Klaus Flittner git-svn-id: https://sdcc.svn.sourceforge.net/svnroot/sdcc/trunk/sdcc@2919 4a8a32a2-be11-0410-ad9d-d568d2c75423 --- ChangeLog | 8 +++++++ src/SDCCBBlock.h | 2 +- src/SDCCloop.c | 60 ++++++++++++++++++++++++++++++++++++++++++++---- src/SDCCloop.h | 11 +++++---- src/SDCClrange.c | 55 +++++++++++++++++++++++++++++--------------- 5 files changed, 107 insertions(+), 29 deletions(-) diff --git a/ChangeLog b/ChangeLog index 6f865770..414919f6 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,11 @@ +2003-10-04 Bernhard Held + + Applied liferange patch from Klaus Flittner + * src/SDCCBBlock.h + * src/SDCCloop.c + * src/SDCCloop.h + * src/SDCClrange.c + 2003-10-03 Erik Petrich * src/z80/gen.h, diff --git a/src/SDCCBBlock.h b/src/SDCCBBlock.h index 68c29061..6ccd0a7c 100644 --- a/src/SDCCBBlock.h +++ b/src/SDCCBBlock.h @@ -45,7 +45,7 @@ typedef struct eBBlock iCode *ech; /* pointer to last of code chain */ struct eBBlock *preHeader; /* preheader if this is a loop entry */ - struct region *partOfLoop; /* pointer to the loop region this block is part of */ + set *partOfLoop; /* set of loop regions this block is part of */ /* control flow analysis */ set *succList; /* list eBBlocks which are successors */ diff --git a/src/SDCCloop.c b/src/SDCCloop.c index d04b717c..6e6b26a6 100644 --- a/src/SDCCloop.c +++ b/src/SDCCloop.c @@ -236,10 +236,8 @@ DEFSETFUNC (addToExitsMarkDepth) ebp->depth = depth; /* put the loop region info in the block */ - /* NOTE: here we will update only the inner most loop - that it is a part of */ - if (!ebp->partOfLoop) - ebp->partOfLoop = lr; + if (!isinSet (ebp->partOfLoop, lr)) + addSetHead (&ebp->partOfLoop, lr); /* if any of the successors go out of the loop then */ /* we add this one to the exits */ @@ -1216,3 +1214,57 @@ loopOptimizations (hTab * orderedLoops, eBBlock ** ebbs, int count) return change; } + +/*-----------------------------------------------------------------*/ +/* addLoopBlocks - will add all blocks inside a loop to this loop */ +/* this should fix most of the liverange problems */ +/*-----------------------------------------------------------------*/ +void +addLoopBlocks (eBBlock ** ebbs, int count) +{ + region *aloop; + struct eBBlock *block; + int seqMin, seqMax; + int i, j; + + for (i = 0; i < count; i++) + { + if (!ebbs[i]->partOfLoop) + continue; + + /* for all loops this block belongs to */ + /* add inner block not already marked as part of this loop */ + aloop = setFirstItem (ebbs[i]->partOfLoop); + for (; aloop; aloop = setNextItem (ebbs[i]->partOfLoop)) + { + + if (aloop->visited) + continue; + + aloop->visited = 1; + + /* set max & min Seq for loopRegion */ + block = setFirstItem (aloop->regBlocks); + seqMax = block->lSeq; + seqMin = block->fSeq; + for (; block; block = setNextItem (aloop->regBlocks)) + { + if (block->lSeq > seqMax) + seqMax = block->lSeq; + if (block->fSeq < seqMin) + seqMin = block->fSeq; + } + + /* add all blocks between seqMin, seqMax to loop */ + for (j = 0; j < count; j++) + { + if (ebbs[j]->fSeq > seqMin && ebbs[j]->lSeq < seqMax && + !isinSet (aloop->regBlocks, ebbs[j])) + { + if (!isinSet (ebbs[i]->partOfLoop, aloop)) + addSetHead (&ebbs[j]->partOfLoop, aloop); + } + } + } + } +} diff --git a/src/SDCCloop.h b/src/SDCCloop.h index 1027b4a1..65f35731 100644 --- a/src/SDCCloop.h +++ b/src/SDCCloop.h @@ -8,19 +8,19 @@ under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. - + This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. - + You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. - + In other words, you are welcome to use, share and improve this program. You are forbidden to forbid anyone else to use, share and improve - what you give them. Help stamp out software-hoarding! + what you give them. Help stamp out software-hoarding! -------------------------------------------------------------------------*/ #include "SDCCBBlock.h" #include "SDCCcse.h" @@ -32,6 +32,7 @@ typedef struct region { unsigned int merged:1; + unsigned int visited:1; eBBlock *entry; /* entry Block */ int containsLoops; /* contains other loops */ set *regBlocks; /* set of all blocks */ @@ -59,6 +60,6 @@ hTab *createLoopRegions (eBBlock **, int); iCode *findDefInRegion (set *, operand *, eBBlock **); int hasIncomingDefs (region *, operand *); int findLoopEndSeq (region *); - +void addLoopBlocks (eBBlock ** ebbs, int count); #endif diff --git a/src/SDCClrange.c b/src/SDCClrange.c index a85c5ff1..b34565bc 100644 --- a/src/SDCClrange.c +++ b/src/SDCClrange.c @@ -124,10 +124,14 @@ isLastUse (operand * op, eBBlock * ebp, iCode * ic, if (usedInRemaining (op, ic)) return 0; - /* if not then check any of the successor blocks use it */ - for (i = 0; i < count; ebbs[i++]->visited = 0); - if (applyToSet (ebp->succList, isOpAlive, op, ebp, ic)) - return 0; + /* if not then check any of the following blocks use it */ + for (i = 0; i < count; i++) + { + if (ebbs[i]->fSeq <= ebp->fSeq) + continue; + if (usedInRemaining (op, ebbs[i]->sch)) + return 0; + } /* this is the last use */ return 1; @@ -307,23 +311,33 @@ operandLUse (operand * op, eBBlock ** ebbs, /* if this is a SEND then the toRange should be extended to the call */ - if (ic->op == SEND) { + if (ic->op == SEND) + { iCode *lic ; - for (lic = ic->next ; lic ; lic = lic->next) { - if (lic->op == CALL || lic->op == PCALL) break; - } + for (lic = ic->next ; lic ; lic = lic->next) + { + if (lic->op == CALL || lic->op == PCALL) + break; + } /* found it : mark */ - if (lic) torange = lic->prev->seq; - } - /* if this is the last use then if this block belongs - to a loop & some definition comes into the loop + if (lic) + torange = lic->prev->seq; + } + /* if this is the last use then if this block belongs + to a loop & some definition comes into the loop then extend the live range to the end of the loop */ - if (ebp->partOfLoop - && hasIncomingDefs (ebp->partOfLoop, op)) - { - torange = findLoopEndSeq (ebp->partOfLoop); + if (ebp->partOfLoop) + { + region *aloop; + + aloop = setFirstItem (ebp->partOfLoop); + for (; aloop; aloop = setNextItem (ebp->partOfLoop)) + { + if (hasIncomingDefs (aloop, op)) + torange = findLoopEndSeq (aloop); + } } - + op = operandFromOperand (op); setToRange (op, torange, FALSE); } @@ -702,8 +716,8 @@ void computeLiveRanges (eBBlock ** ebbs, int count) { int i = 0; - /* sequence the code the live ranges are computed - in terms of this sequence additionally the + /* sequence the code the live ranges are computed + in terms of this sequence additionally the routine will also create a hashtable of instructions */ iCodeSeq = 0; setToNull ((void **) &iCodehTab); @@ -712,6 +726,9 @@ computeLiveRanges (eBBlock ** ebbs, int count) iCodeSeqhTab = newHashTable (iCodeKey); sequenceiCode (ebbs, count); + /* add blocks between loop blocks as part of that loop */ + addLoopBlocks (ebbs, count); + /* call routine to mark the from & to live ranges for variables used */ setToNull ((void **) &liveRanges); -- 2.47.2