From 960cb9272de7e7c6e32710463a0de6ec398ece8b Mon Sep 17 00:00:00 2001 From: sdattalo Date: Tue, 2 Jul 2002 15:26:02 +0000 Subject: [PATCH] pCode Register optimization - registers used in only one or two instructions are analyzed and removed if possible. git-svn-id: https://sdcc.svn.sourceforge.net/svnroot/sdcc/trunk/sdcc@2027 4a8a32a2-be11-0410-ad9d-d568d2c75423 --- src/pic/device.c | 36 +++++++ src/pic/pcode.c | 54 +++++++++- src/pic/pcode.h | 4 +- src/pic/pcodepeep.c | 4 +- src/pic/pcoderegs.c | 250 ++++++++++++++++++++++++++++++++++++++++++-- 5 files changed, 331 insertions(+), 17 deletions(-) diff --git a/src/pic/device.c b/src/pic/device.c index b260f6f4..bdb3cf6a 100644 --- a/src/pic/device.c +++ b/src/pic/device.c @@ -113,6 +113,34 @@ memRange p16f877_sfr[] = { {-1, -1, -1, -1} /* end indicator */ }; +/* 16F873 */ +memRange p16f873_mem[] = { + {0x20, 0x7f, 0x100, 0}, + {0xa0, 0xff, 0x100, 1}, + {-1, -1, -1, -1} /* end indicator */ +}; +memRange p16f873_sfr[] = { + {0x00, 0x00, 0x180, 0}, + {0x01, 0x01, 0x100, 0}, + {0x02, 0x04, 0x180, 0}, + {0x05, 0x05, 0x000, 0}, + {0x85, 0x85, 0x000, 1}, + {0x81, 0x81, 0x100, 1}, + {0x06, 0x06, 0x100, 0}, + {0x86, 0x86, 0x100, 1}, + {0x07, 0x09, 0x000, 0}, + {0x87, 0x89, 0x000, 1}, + {0x0a, 0x0b, 0x180, 0}, + {0x0c, 0x1f, 0x000, 0}, + {0x8c, 0x8e, 0x000, 1}, + {0x91, 0x94, 0x000, 1}, + {0x98, 0x99, 0x000, 1}, + {0x9e, 0x9f, 0x000, 1}, + {0x10c, 0x10f, 0x000, 2}, + {0x18c, 0x18f, 0x000, 3}, + + {-1, -1, -1, -1} /* end indicator */ +}; static PIC_device Pics[] = { { @@ -139,6 +167,14 @@ static PIC_device Pics[] = { 0x80, }, + { + {"p16f873", "16f873", "pic16f873", "f873"}, + p16f873_mem, + p16f873_sfr, + 0, + 0x180, + }, + { {"p16f877", "16f877", "pic16f877", "f877"}, p16f877_mem, diff --git a/src/pic/pcode.c b/src/pic/pcode.c index bd5be723..36d2aa7c 100644 --- a/src/pic/pcode.c +++ b/src/pic/pcode.c @@ -70,15 +70,18 @@ static hTab *pic14pCodePeepCommandsHash = NULL; static pFile *the_pFile = NULL; +static pBlock *pb_dead_pcodes = NULL; /* Hardcoded flags to change the behavior of the PIC port */ static int peepOptimizing = 1; /* run the peephole optimizer if nonzero */ static int functionInlining = 1; /* inline functions if nonzero */ static int GpCodeSequenceNumber = 1; -static int GpcFlowSeq = 1; +int GpcFlowSeq = 1; extern void RemoveUnusedRegisters(void); +extern void BuildFlowTree(pBlock *pb); +extern void pCodeRegOptimizeRegUsage(void); /****************************************************************/ /* Forward declarations */ @@ -103,6 +106,7 @@ char *get_op( pCodeOp *pcop,char *buff,int buf_size); int pCodePeepMatchLine(pCodePeep *peepBlock, pCode *pcs, pCode *pcd); int pCodePeepMatchRule(pCode *pc); void pBlockStats(FILE *of, pBlock *pb); +pBlock *newpBlock(void); extern void pCodeInsertAfter(pCode *pc1, pCode *pc2); extern pCodeOp *popCopyReg(pCodeOpReg *pc); pCodeOp *popCopyGPR2Bit(pCodeOp *pc, int bitval); @@ -1228,6 +1232,9 @@ void pCodeInitRegisters(void) pc_wsave.rIdx = IDX_WSAVE; pc_ssave.rIdx = IDX_SSAVE; + /* probably should put this in a separate initialization routine */ + pb_dead_pcodes = newpBlock(); + } /*-----------------------------------------------------------------*/ @@ -1915,6 +1922,7 @@ pBlock *newpBlock(void) PpB->function_entries = PpB->function_exits = PpB->function_calls = NULL; PpB->tregisters = NULL; PpB->visited = 0; + PpB->FlowTree = NULL; return PpB; @@ -2335,13 +2343,34 @@ void unlinkpCode(pCode *pc) pc->prev = pc->next = NULL; } } + +/*-----------------------------------------------------------------*/ +/*-----------------------------------------------------------------*/ + static void genericDestruct(pCode *pc) { - //fprintf(stderr,"warning, calling default pCode destructor\n"); unlinkpCode(pc); - free(pc); + if(isPCI(pc)) { + /* For instructions, tell the register (if there's one used) + * that it's no longer needed */ + regs *reg = getRegFromInstruction(pc); + if(reg) + deleteSetItem (&(reg->reglives.usedpCodes),pc); + } + + /* Instead of deleting the memory used by this pCode, mark + * the object as bad so that if there's a pointer to this pCode + * dangling around somewhere then (hopefully) when the type is + * checked we'll catch it. + */ + + pc->type = PC_BAD; + + addpCode2pBlock(pb_dead_pcodes, pc); + + //free(pc); } @@ -2538,9 +2567,11 @@ char *pCode2str(char *str, int size, pCode *pc) SAFE_snprintf(&s,&size,";\t--FLOW change\n"); break; case PC_CSOURCE: - SAFE_snprintf(&s,&size,";#CSRC\t%s %d\n; %s\n", PCCS(pc)->file_name, PCCS(pc)->line_number, PCCS(pc)->line); + SAFE_snprintf(&s,&size,";#CSRC\t%s %d\n; %s\n", PCCS(pc)->file_name, PCCS(pc)->line_number, PCCS(pc)->line); break; + case PC_BAD: + SAFE_snprintf(&s,&size,";A bad pCode is being used\n"); } return str; @@ -2881,6 +2912,9 @@ static void genericAnalyze(pCode *pc) fprintf(stderr,"analyze PC_FLOW\n"); return; + case PC_BAD: + fprintf(stderr,,";A bad pCode is being used\n"); + } } #endif @@ -4548,6 +4582,15 @@ void AnalyzeBanking(void) for(pb = the_pFile->pbHead; pb; pb = pb->next) LinkFlow(pb); + /* Phase 3 - Flow Analysis - Flow Tree + * + * In this phase, the individual flow blocks are examined + * to determine their order of excution. + */ + /* + for(pb = the_pFile->pbHead; pb; pb = pb->next) + BuildFlowTree(pb); + */ /* Phase x - Flow Analysis - Used Banks * @@ -4573,6 +4616,9 @@ void AnalyzeBanking(void) RemoveUnusedRegisters(); + // for(pb = the_pFile->pbHead; pb; pb = pb->next) + pCodeRegOptimizeRegUsage(); + /* for(pb = the_pFile->pbHead; pb; pb = pb->next) DumpFlow(pb); diff --git a/src/pic/pcode.h b/src/pic/pcode.h index 9e6f9741..7d896723 100644 --- a/src/pic/pcode.h +++ b/src/pic/pcode.h @@ -235,7 +235,8 @@ typedef enum PC_FUNCTION, /* Function start or end */ PC_WILD, /* wildcard - an opcode place holder used * in the pCode peep hole optimizer */ - PC_CSOURCE /* C-Source Line */ + PC_CSOURCE, /* C-Source Line */ + PC_BAD /* Mark the pCode object as being bad */ } PC_TYPE; /************************************************/ @@ -605,6 +606,7 @@ typedef struct pBlock set *function_calls; set *tregisters; + set *FlowTree; unsigned visited:1; /* set true if traversed in call tree */ unsigned seq; /* sequence number of this pBlock */ diff --git a/src/pic/pcodepeep.c b/src/pic/pcodepeep.c index 46a6b1d8..96b334cb 100644 --- a/src/pic/pcodepeep.c +++ b/src/pic/pcodepeep.c @@ -1982,7 +1982,7 @@ int pCodePeepMatchRule(pCode *pc) pcin->prev = pc->prev; - //#if 0 +#if 0 { /* DEBUG */ /* Converted the deleted pCodes into comments */ @@ -2014,7 +2014,7 @@ int pCodePeepMatchRule(pCode *pc) if(pc_cline2) pc_cline2->pc.next = NULL; } - //#endif +#endif if(pcin) pCodeDeleteChain(pc,pcin); diff --git a/src/pic/pcoderegs.c b/src/pic/pcoderegs.c index efbddfa4..5a5ebbff 100644 --- a/src/pic/pcoderegs.c +++ b/src/pic/pcoderegs.c @@ -36,9 +36,12 @@ #include "pcoderegs.h" #include "pcodeflow.h" +extern void pCodeInsertAfter(pCode *pc1, pCode *pc2); extern void dbg_dumpregusage(void); void unlinkpCode(pCode *pc); +int total_registers_saved=0; + /*-----------------------------------------------------------------* * void AddRegToFlow(regs *reg, pCodeFlow *pcfl) *-----------------------------------------------------------------*/ @@ -180,6 +183,7 @@ void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl) } } + /*-----------------------------------------------------------------* * void pCodeRegMapLiveRanges(pBlock *pb) *-----------------------------------------------------------------*/ @@ -213,7 +217,7 @@ void pCodeRegMapLiveRanges(pBlock *pb) } - // dbg_dumpregusage(); + //dbg_dumpregusage(); } @@ -243,7 +247,6 @@ void RemoveRegsFromSet(set *regset) } else { pCode *pc; - //fprintf(stderr," reg %s used only once\n",reg->name); pc = setFirstItem(reg->reglives.usedpCodes); if(isPCI(pc)) { @@ -251,8 +254,8 @@ void RemoveRegsFromSet(set *regset) pCode *pcn = findNextInstruction(pc->next); if(pcn && PCI(pcn)->label) { - fprintf(stderr,"can't delete instruction with label...\n"); - pc->print(stderr,pc); + //fprintf(stderr,"can't delete instruction with label...\n"); + //pc->print(stderr,pc); continue; } /* Move the label to the next instruction */ @@ -264,10 +267,12 @@ void RemoveRegsFromSet(set *regset) if(isPCI_SKIP(pc)) fprintf(stderr, "WARNING, a skip instruction is being optimized out\n"); + //fprintf(stderr," removing reg %s because it is used only once\n",reg->name); unlinkpCode(pc); deleteSetItem (&(reg->reglives.usedpCodes),pc); reg->isFree = 1; reg->wasUsed = 0; + total_registers_saved++; // debugging stats. } } } @@ -280,23 +285,248 @@ void RemoveRegsFromSet(set *regset) *-----------------------------------------------------------------*/ void RemoveUnusedRegisters(void) { + /* First, get rid of registers that are used only one time */ - //fprintf(stderr,"InternalRegs:\n"); RemoveRegsFromSet(dynInternalRegs); - //fprintf(stderr,"AllocRegs:\n"); RemoveRegsFromSet(dynAllocRegs); - //fprintf(stderr,"StackRegs:\n"); RemoveRegsFromSet(dynStackRegs); - /* don't do DirectRegs yet - there's a problem with arrays - //fprintf(stderr,"DirectRegs:\n"); RemoveRegsFromSet(dynDirectRegs); */ - //fprintf(stderr,"DirectBitRegs:\n"); RemoveRegsFromSet(dynDirectBitRegs); + if(total_registers_saved) fprintf(stderr, " *** Saved %d registers ***\n", total_registers_saved); +} + + +/*-----------------------------------------------------------------* + * + *-----------------------------------------------------------------*/ +static void Remove2pcodes(pCode *pcflow, pCode *pc1, pCode *pc2, regs *reg) +{ + + deleteSetItem (&(reg->reglives.usedpCodes),pc1); + deleteSetItem (&(reg->reglives.usedpCodes),pc2); + deleteSetItem (&(PCFL(pcflow)->registers), reg); + + pc1->destruct(pc1); + pc2->destruct(pc2); + + reg->isFree = 1; + reg->wasUsed = 0; + pCodeRegMapLiveRangesInFlow(PCFL(pcflow)); +} + +/*-----------------------------------------------------------------* + * + *-----------------------------------------------------------------*/ +int regUsedinRange(pCode *pc1, pCode *pc2, regs *reg) +{ + int i=0; + regs *testreg; + + do { + testreg = getRegFromInstruction(pc1); + if(testreg && (testreg->rIdx == reg->rIdx)) { + return 1; + } + + pc1 = findNextInstruction(pc1->next); + + } while (pc1 && (pc1 != pc2) && (i++ < 100)) ; + + if(i >= 100) + fprintf(stderr, "warning, regUsedinRange searched through too many pcodes\n"); + + return 0; +} + +/*-----------------------------------------------------------------* + * void pCodeRegOptimeRegUsage(pBlock *pb) + *-----------------------------------------------------------------*/ +void OptimizeRegUsage(set *fregs) +{ + regs *reg; + int used; + + + while(fregs) { + + /* Step through the set by directly accessing the 'next' pointer. + * We could also step through by using the set API, but the + * the (debug) calls to print instructions affect the state + * of the set pointers */ + + reg = fregs->item; + fregs = fregs->next; + + used = elementsInSet(reg->reglives.usedpCodes); + + if(used == 2) { + + pCode *pcfl_used, *pcfl_assigned; + pCode *pc1, *pc2; + pCode *t; + + /* This register has only been used twice. Chances are we can + get rid of it */ +/* + fprintf (stderr, "OptimizeRegUsage: %s addr=0x%03x rIdx=0x%03x used=%d\n", + reg->name, + reg->address, + reg->rIdx, used); +*/ + pcfl_used = setFirstItem(reg->reglives.usedpFlows); + pcfl_assigned = setFirstItem(reg->reglives.assignedpFlows); + + pc1 = setFirstItem(reg->reglives.usedpCodes); + pc2 = setNextItem(reg->reglives.usedpCodes); + + if(pcfl_used && pcfl_assigned) { + + /* + expected case - the register has been assigned a value and is + subsequently used + */ + //fprintf(stderr," used only twice\n"); + if(pcfl_used->seq == pcfl_assigned->seq) { + + //fprintf(stderr, " and used in same flow\n"); + if(pc2->seq < pc1->seq) { + t = pc2; + pc2 = pc1; + pc1 = t; + } + + //pc1->print(stderr,pc1); + //pc2->print(stderr,pc2); + + + /* ADHOC pattern checking */ + if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_MOVFW) ){ + pCode *newpc; + //fprintf(stderr, " CLRF/MOVFW. instruction after MOVFW is:\n"); + t = findNextInstruction(pc2->next); + //t->print(stderr,t); + + if(PCI(t)->op == POC_MOVWF) { + newpc = newpCode(POC_CLRF, PCI(t)->pcop); + } else { + newpc = newpCode(POC_MOVLW, newpCodeOpLit(0)); + } + + PCI(newpc)->pcflow = PCFL(pcfl_used); + newpc->seq = t->seq; + + pCodeInsertAfter(t, newpc); + + t->destruct(t); + Remove2pcodes(pcfl_used, pc1, pc2, reg); + total_registers_saved++; // debugging stats. + + } else if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_IORFW) ){ + //fprintf(stderr, " CLRF/IORWF.\n"); + + Remove2pcodes(pcfl_used, pc1, pc2, reg); + total_registers_saved++; // debugging stats. + + } else if((PCI(pc1)->op == POC_MOVWF) && (PCI(pc2)->op == POC_MOVFW) ){ + //fprintf(stderr, " MOVWF/MOVFW. instruction after MOVFW is:\n"); + t = findNextInstruction(pc2->next); + // t->print(stderr,t); + + if(PCI(t)->op == POC_MOVWF) { + regs *nextreg = getRegFromInstruction(t); + if(nextreg && !regUsedinRange(pc1,pc2,nextreg)) { + t->seq = pc1->seq; + unlinkpCode(t); + pCodeInsertAfter(pc1,t); + Remove2pcodes(pcfl_used, pc1, pc2, reg); + total_registers_saved++; // debugging stats. + } + } + } + + } else { + // fprintf(stderr, " and used in different flows\n"); + + //pc1->print(stderr,pc1); + //pc2->print(stderr,pc2); + } + + } else if(pcfl_used) { + + /* + register has been used twice without ever being assigned */ + fprintf(stderr,"WARNING %s: reg %s used without being assigned\n",__FUNCTION__,reg->name); + } else { + fprintf(stderr,"WARNING %s: reg %s assigned without being used\n",__FUNCTION__,reg->name); + } + } else { + //if(used) fprintf (stderr, " over used OptimizeRegUsage: %s used=%d\n", reg->name, used); + + } + + } + +#if 0 + pcfl = setFirstItem(reg->reglives.usedpFlows); + if(pcfl) + fprintf(stderr, "\n used in seq"); + + while(pcfl) { + fprintf(stderr," 0x%03x",pcfl->seq); + pcfl = setNextItem(reg->reglives.usedpFlows); + } + + pcfl = setFirstItem(reg->reglives.assignedpFlows); + if(pcfl) + fprintf(stderr, "\n assigned in seq"); + + while(pcfl) { + fprintf(stderr," 0x%03x",pcfl->seq); + pcfl = setNextItem(reg->reglives.assignedpFlows); + } + + pc = setFirstItem(reg->reglives.usedpCodes); + if(pc) + fprintf(stderr, "\n used in instructions "); + + while(pc) { + pcfl = PCODE(PCI(pc)->pcflow); + if(pcfl) + fprintf(stderr," 0x%03x:",pcfl->seq); + fprintf(stderr,"0x%03x",pc->seq); + + pc = setNextItem(reg->reglives.usedpCodes); + } + + fprintf(stderr, "\n"); + + } +#endif +} +/*-----------------------------------------------------------------* + * void pCodeRegOptimeRegUsage(pBlock *pb) + *-----------------------------------------------------------------*/ +void pCodeRegOptimizeRegUsage(void) +{ + + int passes = 4; + int saved = 0; + + do { + saved = total_registers_saved; + + /* Identify registers used in one flow sequence */ + OptimizeRegUsage(dynAllocRegs); + + if(total_registers_saved != saved) + fprintf(stderr, " *** Saved %d registers, total saved %d ***\n", total_registers_saved-saved,total_registers_saved); + + } while( passes-- && (total_registers_saved != saved)); } -- 2.30.2