1 /*-------------------------------------------------------------------------
3 pcoderegs.c - post code generation register optimizations
5 Written By - Scott Dattalo scott@dattalo.com
7 This program is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by the
9 Free Software Foundation; either version 2, or (at your option) any
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
21 -------------------------------------------------------------------------*/
26 The purpose of the code in this file is to optimize the register usage.
31 #include "common.h" // Include everything in the SDCC src directory
36 #include "pcoderegs.h"
37 #include "pcodeflow.h"
39 extern void pCodeInsertAfter(pCode *pc1, pCode *pc2);
40 extern void dbg_dumpregusage(void);
41 void unlinkpCode(pCode *pc);
43 int total_registers_saved=0;
45 /*-----------------------------------------------------------------*
46 * void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
47 *-----------------------------------------------------------------*/
49 void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
52 if(!reg || ! pcfl || !isPCFL(pcflow))
56 pcfl->registers = newSet();
62 /*-----------------------------------------------------------------*
64 *-----------------------------------------------------------------*/
65 void dbg_regusage(set *fregs)
72 for (reg = setFirstItem(fregs) ; reg ;
73 reg = setNextItem(fregs)) {
75 fprintf (stderr, "%s addr=0x%03x rIdx=0x%03x",
80 pcfl = setFirstItem(reg->reglives.usedpFlows);
82 fprintf(stderr, "\n used in seq");
85 fprintf(stderr," 0x%03x",pcfl->seq);
86 pcfl = setNextItem(reg->reglives.usedpFlows);
89 pcfl = setFirstItem(reg->reglives.assignedpFlows);
91 fprintf(stderr, "\n assigned in seq");
94 fprintf(stderr," 0x%03x",pcfl->seq);
95 pcfl = setNextItem(reg->reglives.assignedpFlows);
98 pc = setFirstItem(reg->reglives.usedpCodes);
100 fprintf(stderr, "\n used in instructions ");
103 pcfl = PCODE(PCI(pc)->pcflow);
105 fprintf(stderr," 0x%03x:",pcfl->seq);
106 fprintf(stderr,"0x%03x",pc->seq);
108 pc = setNextItem(reg->reglives.usedpCodes);
111 fprintf(stderr, "\n");
116 /*-----------------------------------------------------------------*
118 *-----------------------------------------------------------------*/
119 void dbg_dumpregusage(void)
122 fprintf(stderr,"*** Register Usage ***\n");
123 fprintf(stderr,"InternalRegs:\n");
124 dbg_regusage(dynInternalRegs);
125 fprintf(stderr,"AllocRegs:\n");
126 dbg_regusage(dynAllocRegs);
127 fprintf(stderr,"StackRegs:\n");
128 dbg_regusage(dynStackRegs);
129 fprintf(stderr,"DirectRegs:\n");
130 dbg_regusage(dynDirectRegs);
131 fprintf(stderr,"DirectBitRegs:\n");
132 dbg_regusage(dynDirectBitRegs);
133 fprintf(stderr,"ProcessorRegs:\n");
134 dbg_regusage(dynProcessorRegs);
139 /*-----------------------------------------------------------------*
140 * void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
141 *-----------------------------------------------------------------*/
142 void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
154 pc = findNextInstruction(pcfl->pc.next);
156 while(isPCinFlow(pc,PCODE(pcfl))) {
159 reg = getRegFromInstruction(pc);
163 fprintf(stderr, "flow seq %d, inst seq %d %s ",PCODE(pcfl)->seq,pc->seq,reg->name);
164 fprintf(stderr, "addr = 0x%03x, type = %d rIdx=0x%03x\n",
165 reg->address,reg->type,reg->rIdx);
168 addSetIfnotP(& (PCFL(pcfl)->registers), reg);
170 if(PCC_REGISTER & PCI(pc)->inCond)
171 addSetIfnotP(& (reg->reglives.usedpFlows), pcfl);
173 if(PCC_REGISTER & PCI(pc)->outCond)
174 addSetIfnotP(& (reg->reglives.assignedpFlows), pcfl);
176 addSetIfnotP(& (reg->reglives.usedpCodes), pc);
181 pc = findNextInstruction(pc->next);
187 /*-----------------------------------------------------------------*
188 * void pCodeRegMapLiveRanges(pBlock *pb)
189 *-----------------------------------------------------------------*/
190 void pCodeRegMapLiveRanges(pBlock *pb)
194 for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
196 pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
198 if(!isPCFL(pcflow)) {
199 fprintf(stderr, "pCodeRegMapLiveRanges - pcflow is not a flow object ");
202 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
206 for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
208 pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
210 regs *r = setFirstItem(PCFL(pcflow)->registers);
211 //fprintf(stderr,"flow seq %d\n", pcflow->seq);
213 //fprintf(stderr, " %s\n",r->name);
214 r = setNextItem(PCFL(pcflow)->registers);
220 //dbg_dumpregusage();
225 /*-----------------------------------------------------------------*
226 * void RemoveRegsFromSet(set *regset)
228 *-----------------------------------------------------------------*/
229 void RemoveRegsFromSet(set *regset)
233 for (reg = setFirstItem(regset) ; reg ;
234 reg = setNextItem(regset)) {
237 used = elementsInSet(reg->reglives.usedpCodes);
241 //fprintf(stderr," reg %s isfree=%d, wasused=%d\n",reg->name,reg->isFree,reg->wasUsed);
244 //fprintf(stderr," getting rid of reg %s\n",reg->name);
251 pc = setFirstItem(reg->reglives.usedpCodes);
254 pCode *pcn = findNextInstruction(pc->next);
256 if(pcn && PCI(pcn)->label) {
257 //fprintf(stderr,"can't delete instruction with label...\n");
258 //pc->print(stderr,pc);
261 /* Move the label to the next instruction */
263 PCI(pcn)->label = PCI(pc)->label;
268 fprintf(stderr, "WARNING, a skip instruction is being optimized out\n");
270 //fprintf(stderr," removing reg %s because it is used only once\n",reg->name);
272 deleteSetItem (&(reg->reglives.usedpCodes),pc);
275 total_registers_saved++; // debugging stats.
282 /*-----------------------------------------------------------------*
283 * void RemoveUnusedRegisters(void)
285 *-----------------------------------------------------------------*/
286 void RemoveUnusedRegisters(void)
288 /* First, get rid of registers that are used only one time */
291 RemoveRegsFromSet(dynInternalRegs);
292 RemoveRegsFromSet(dynAllocRegs);
293 RemoveRegsFromSet(dynStackRegs);
295 don't do DirectRegs yet - there's a problem with arrays
296 RemoveRegsFromSet(dynDirectRegs);
298 RemoveRegsFromSet(dynDirectBitRegs);
300 if(total_registers_saved) fprintf(stderr, " *** Saved %d registers ***\n", total_registers_saved);
304 /*-----------------------------------------------------------------*
306 *-----------------------------------------------------------------*/
307 static void Remove2pcodes(pCode *pcflow, pCode *pc1, pCode *pc2, regs *reg)
310 deleteSetItem (&(reg->reglives.usedpCodes),pc1);
311 deleteSetItem (&(reg->reglives.usedpCodes),pc2);
312 deleteSetItem (&(PCFL(pcflow)->registers), reg);
319 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
322 /*-----------------------------------------------------------------*
324 *-----------------------------------------------------------------*/
325 int regUsedinRange(pCode *pc1, pCode *pc2, regs *reg)
331 testreg = getRegFromInstruction(pc1);
332 if(testreg && (testreg->rIdx == reg->rIdx)) {
336 pc1 = findNextInstruction(pc1->next);
338 } while (pc1 && (pc1 != pc2) && (i++ < 100)) ;
341 fprintf(stderr, "warning, regUsedinRange searched through too many pcodes\n");
346 /*-----------------------------------------------------------------*
347 * void pCodeRegOptimeRegUsage(pBlock *pb)
348 *-----------------------------------------------------------------*/
349 void OptimizeRegUsage(set *fregs)
357 /* Step through the set by directly accessing the 'next' pointer.
358 * We could also step through by using the set API, but the
359 * the (debug) calls to print instructions affect the state
360 * of the set pointers */
365 used = elementsInSet(reg->reglives.usedpCodes);
369 pCode *pcfl_used, *pcfl_assigned;
373 /* This register has only been used twice. Chances are we can
376 fprintf (stderr, "OptimizeRegUsage: %s addr=0x%03x rIdx=0x%03x used=%d\n",
381 pcfl_used = setFirstItem(reg->reglives.usedpFlows);
382 pcfl_assigned = setFirstItem(reg->reglives.assignedpFlows);
384 pc1 = setFirstItem(reg->reglives.usedpCodes);
385 pc2 = setNextItem(reg->reglives.usedpCodes);
387 if(pcfl_used && pcfl_assigned) {
390 expected case - the register has been assigned a value and is
393 //fprintf(stderr," used only twice\n");
394 if(pcfl_used->seq == pcfl_assigned->seq) {
396 //fprintf(stderr, " and used in same flow\n");
397 if(pc2->seq < pc1->seq) {
403 //pc1->print(stderr,pc1);
404 //pc2->print(stderr,pc2);
407 /* ADHOC pattern checking */
408 if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_MOVFW) ){
410 //fprintf(stderr, " CLRF/MOVFW. instruction after MOVFW is:\n");
411 t = findNextInstruction(pc2->next);
412 //t->print(stderr,t);
414 if(PCI(t)->op == POC_MOVWF) {
415 newpc = newpCode(POC_CLRF, PCI(t)->pcop);
417 newpc = newpCode(POC_MOVLW, newpCodeOpLit(0));
420 PCI(newpc)->pcflow = PCFL(pcfl_used);
423 pCodeInsertAfter(t, newpc);
426 Remove2pcodes(pcfl_used, pc1, pc2, reg);
427 total_registers_saved++; // debugging stats.
429 } else if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_IORFW) ){
430 //fprintf(stderr, " CLRF/IORWF.\n");
432 Remove2pcodes(pcfl_used, pc1, pc2, reg);
433 total_registers_saved++; // debugging stats.
435 } else if((PCI(pc1)->op == POC_MOVWF) && (PCI(pc2)->op == POC_MOVFW) ){
436 //fprintf(stderr, " MOVWF/MOVFW. instruction after MOVFW is:\n");
437 t = findNextInstruction(pc2->next);
438 // t->print(stderr,t);
440 if(PCI(t)->op == POC_MOVWF) {
441 regs *nextreg = getRegFromInstruction(t);
442 if(nextreg && !regUsedinRange(pc1,pc2,nextreg)) {
445 pCodeInsertAfter(pc1,t);
446 Remove2pcodes(pcfl_used, pc1, pc2, reg);
447 total_registers_saved++; // debugging stats.
453 // fprintf(stderr, " and used in different flows\n");
455 //pc1->print(stderr,pc1);
456 //pc2->print(stderr,pc2);
459 } else if(pcfl_used) {
462 register has been used twice without ever being assigned */
463 fprintf(stderr,"WARNING %s: reg %s used without being assigned\n",__FUNCTION__,reg->name);
465 fprintf(stderr,"WARNING %s: reg %s assigned without being used\n",__FUNCTION__,reg->name);
468 //if(used) fprintf (stderr, " over used OptimizeRegUsage: %s used=%d\n", reg->name, used);
475 pcfl = setFirstItem(reg->reglives.usedpFlows);
477 fprintf(stderr, "\n used in seq");
480 fprintf(stderr," 0x%03x",pcfl->seq);
481 pcfl = setNextItem(reg->reglives.usedpFlows);
484 pcfl = setFirstItem(reg->reglives.assignedpFlows);
486 fprintf(stderr, "\n assigned in seq");
489 fprintf(stderr," 0x%03x",pcfl->seq);
490 pcfl = setNextItem(reg->reglives.assignedpFlows);
493 pc = setFirstItem(reg->reglives.usedpCodes);
495 fprintf(stderr, "\n used in instructions ");
498 pcfl = PCODE(PCI(pc)->pcflow);
500 fprintf(stderr," 0x%03x:",pcfl->seq);
501 fprintf(stderr,"0x%03x",pc->seq);
503 pc = setNextItem(reg->reglives.usedpCodes);
506 fprintf(stderr, "\n");
511 /*-----------------------------------------------------------------*
512 * void pCodeRegOptimeRegUsage(pBlock *pb)
513 *-----------------------------------------------------------------*/
514 void pCodeRegOptimizeRegUsage(void)
521 saved = total_registers_saved;
523 /* Identify registers used in one flow sequence */
524 OptimizeRegUsage(dynAllocRegs);
526 if(total_registers_saved != saved)
527 fprintf(stderr, " *** Saved %d registers, total saved %d ***\n", total_registers_saved-saved,total_registers_saved);
530 } while( passes-- && (total_registers_saved != saved));