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 extern pCode * findPrevInstruction(pCode *pci);
42 void unlinkpCode(pCode *pc);
44 int total_registers_saved=0;
46 /*-----------------------------------------------------------------*
47 * void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
48 *-----------------------------------------------------------------*/
50 void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
53 if(!reg || ! pcfl || !isPCFL(pcflow))
57 pcfl->registers = newSet();
63 /*-----------------------------------------------------------------*
65 *-----------------------------------------------------------------*/
66 void dbg_regusage(set *fregs)
73 for (reg = setFirstItem(fregs) ; reg ;
74 reg = setNextItem(fregs)) {
76 if(elementsInSet(reg->reglives.usedpCodes)) {
78 fprintf (stderr, "%s addr=0x%03x rIdx=0x%03x",
83 pcfl = setFirstItem(reg->reglives.usedpFlows);
85 fprintf(stderr, "\n used in seq");
88 fprintf(stderr," 0x%03x",pcfl->seq);
89 pcfl = setNextItem(reg->reglives.usedpFlows);
92 pcfl = setFirstItem(reg->reglives.assignedpFlows);
94 fprintf(stderr, "\n assigned in seq");
97 fprintf(stderr," 0x%03x",pcfl->seq);
98 pcfl = setNextItem(reg->reglives.assignedpFlows);
101 pc = setFirstItem(reg->reglives.usedpCodes);
103 fprintf(stderr, "\n used in instructions ");
106 pcfl = PCODE(PCI(pc)->pcflow);
108 fprintf(stderr," 0x%03x:",pcfl->seq);
109 fprintf(stderr,"0x%03x",pc->seq);
111 pc = setNextItem(reg->reglives.usedpCodes);
114 fprintf(stderr, "\n");
119 /*-----------------------------------------------------------------*
121 *-----------------------------------------------------------------*/
122 void dbg_dumpregusage(void)
125 fprintf(stderr,"*** Register Usage ***\n");
126 fprintf(stderr,"InternalRegs:\n");
127 dbg_regusage(dynInternalRegs);
128 fprintf(stderr,"AllocRegs:\n");
129 dbg_regusage(dynAllocRegs);
130 fprintf(stderr,"StackRegs:\n");
131 dbg_regusage(dynStackRegs);
132 fprintf(stderr,"DirectRegs:\n");
133 dbg_regusage(dynDirectRegs);
134 fprintf(stderr,"DirectBitRegs:\n");
135 dbg_regusage(dynDirectBitRegs);
136 fprintf(stderr,"ProcessorRegs:\n");
137 dbg_regusage(dynProcessorRegs);
142 /*-----------------------------------------------------------------*
143 * void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
144 *-----------------------------------------------------------------*/
145 void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
157 pc = findNextInstruction(pcfl->pc.next);
159 while(isPCinFlow(pc,PCODE(pcfl))) {
162 reg = getRegFromInstruction(pc);
166 fprintf(stderr, "flow seq %d, inst seq %d %s ",PCODE(pcfl)->seq,pc->seq,reg->name);
167 fprintf(stderr, "addr = 0x%03x, type = %d rIdx=0x%03x\n",
168 reg->address,reg->type,reg->rIdx);
171 addSetIfnotP(& (PCFL(pcfl)->registers), reg);
173 if((PCC_REGISTER | PCC_LITERAL) & PCI(pc)->inCond)
174 addSetIfnotP(& (reg->reglives.usedpFlows), pcfl);
176 if(PCC_REGISTER & PCI(pc)->outCond)
177 addSetIfnotP(& (reg->reglives.assignedpFlows), pcfl);
179 addSetIfnotP(& (reg->reglives.usedpCodes), pc);
184 pc = findNextInstruction(pc->next);
190 /*-----------------------------------------------------------------*
191 * void pCodeRegMapLiveRanges(pBlock *pb)
192 *-----------------------------------------------------------------*/
193 void pCodeRegMapLiveRanges(pBlock *pb)
197 for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
199 pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
201 if(!isPCFL(pcflow)) {
202 fprintf(stderr, "pCodeRegMapLiveRanges - pcflow is not a flow object ");
205 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
209 for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
211 pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
213 regs *r = setFirstItem(PCFL(pcflow)->registers);
214 //fprintf(stderr,"flow seq %d\n", pcflow->seq);
216 //fprintf(stderr, " %s\n",r->name);
217 r = setNextItem(PCFL(pcflow)->registers);
223 // dbg_dumpregusage();
228 /*-----------------------------------------------------------------*
229 * void RemoveRegsFromSet(set *regset)
231 *-----------------------------------------------------------------*/
232 void RemoveRegsFromSet(set *regset)
236 for (reg = setFirstItem(regset) ; reg ;
237 reg = setNextItem(regset)) {
240 used = elementsInSet(reg->reglives.usedpCodes);
244 //fprintf(stderr," reg %s isfree=%d, wasused=%d\n",reg->name,reg->isFree,reg->wasUsed);
247 //fprintf(stderr," getting rid of reg %s\n",reg->name);
254 pc = setFirstItem(reg->reglives.usedpCodes);
257 pCode *pcn = findNextInstruction(pc->next);
259 if(pcn && PCI(pcn)->label) {
260 //fprintf(stderr,"can't delete instruction with label...\n");
261 //pc->print(stderr,pc);
264 /* Move the label to the next instruction */
266 PCI(pcn)->label = PCI(pc)->label;
271 fprintf(stderr, "WARNING, a skip instruction is being optimized out\n");
273 //fprintf(stderr," removing reg %s because it is used only once\n",reg->name);
275 deleteSetItem (&(reg->reglives.usedpCodes),pc);
278 total_registers_saved++; // debugging stats.
285 /*-----------------------------------------------------------------*
286 * void RemoveUnusedRegisters(void)
288 *-----------------------------------------------------------------*/
289 void RemoveUnusedRegisters(void)
291 /* First, get rid of registers that are used only one time */
294 RemoveRegsFromSet(dynInternalRegs);
295 RemoveRegsFromSet(dynAllocRegs);
296 RemoveRegsFromSet(dynStackRegs);
298 don't do DirectRegs yet - there's a problem with arrays
299 RemoveRegsFromSet(dynDirectRegs);
301 RemoveRegsFromSet(dynDirectBitRegs);
303 if(total_registers_saved) fprintf(stderr, " *** Saved %d registers ***\n", total_registers_saved);
307 /*-----------------------------------------------------------------*
309 *-----------------------------------------------------------------*/
310 static void Remove2pcodes(pCode *pcflow, pCode *pc1, pCode *pc2, regs *reg)
316 deleteSetItem (&(reg->reglives.usedpCodes),pc1);
321 deleteSetItem (&(reg->reglives.usedpCodes),pc2);
324 deleteSetItem (&(PCFL(pcflow)->registers), reg);
331 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
334 /*-----------------------------------------------------------------*
336 *-----------------------------------------------------------------*/
337 int regUsedinRange(pCode *pc1, pCode *pc2, regs *reg)
343 testreg = getRegFromInstruction(pc1);
344 if(testreg && (testreg->rIdx == reg->rIdx)) {
348 pc1 = findNextInstruction(pc1->next);
350 } while (pc1 && (pc1 != pc2) && (i++ < 100)) ;
353 fprintf(stderr, "warning, regUsedinRange searched through too many pcodes\n");
358 /*-----------------------------------------------------------------*
359 * void pCodeRegOptimeRegUsage(pBlock *pb)
360 *-----------------------------------------------------------------*/
361 void OptimizeRegUsage(set *fregs)
368 pCode *pcfl_used, *pcfl_assigned;
370 /* Step through the set by directly accessing the 'next' pointer.
371 * We could also step through by using the set API, but the
372 * the (debug) calls to print instructions affect the state
373 * of the set pointers */
379 pcfl_used = setFirstItem(reg->reglives.usedpFlows);
380 pcfl_assigned = setFirstItem(reg->reglives.assignedpFlows);
382 used = elementsInSet(reg->reglives.usedpCodes);
386 * In this section, all registers that are used in only in two
387 * instructions are examined. If possible, they're optimized out.
391 pCode *pct1, *pct2; /* two temporaries */
395 fprintf (stderr, "OptimizeRegUsage: %s addr=0x%03x rIdx=0x%03x used=%d\n",
400 pc1 = setFirstItem(reg->reglives.usedpCodes);
401 pc2 = setNextItem(reg->reglives.usedpCodes);
403 if(pcfl_used && pcfl_assigned) {
406 expected case - the register has been assigned a value and is
410 //fprintf(stderr," used only twice\n");
411 if(pcfl_used->seq == pcfl_assigned->seq) {
413 //fprintf(stderr, " and used in same flow\n");
414 if(pc2->seq < pc1->seq) {
420 //pc1->print(stderr,pc1);
421 //pc2->print(stderr,pc2);
424 /* ADHOC pattern checking
425 * Now look for specific sequences that are easy to optimize.
426 * Many of these sequences are characteristic of the compiler
427 * (i.e. it'd probably be a waste of time to apply these adhoc
428 * checks to hand written assembly.)
431 if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_MOVFW) ){
445 //fprintf(stderr, " CLRF/MOVFW. instruction after MOVFW is:\n");
446 pct1 = findNextInstruction(pc2->next);
447 //t->print(stderr,t);
449 if(PCI(pct1)->op == POC_MOVWF) {
450 newpc = newpCode(POC_CLRF, PCI(pct1)->pcop);
451 pct1->destruct(pct1);
453 newpc = newpCode(POC_MOVLW, newpCodeOpLit(0));
456 pCodeInsertAfter(pc2, newpc);
457 PCI(newpc)->pcflow = PCFL(pcfl_used);
458 newpc->seq = pc2->seq;
460 Remove2pcodes(pcfl_used, pc1, pc2, reg);
461 total_registers_saved++; // debugging stats.
463 } else if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_IORFW) ){
464 //fprintf(stderr, " CLRF/IORWF.\n");
466 Remove2pcodes(pcfl_used, pc1, pc2, reg);
467 total_registers_saved++; // debugging stats.
469 } else if(PCI(pc1)->op == POC_MOVWF) {
471 pct2 = findNextInstruction(pc2->next);
473 if(PCI(pc2)->op == POC_MOVFW) {
474 //fprintf(stderr, " MOVWF/MOVFW. instruction after MOVFW is:\n");
475 // t->print(stderr,t);
477 if(PCI(pct2)->op == POC_MOVWF) {
478 reg2 = getRegFromInstruction(pct2);
479 if(reg2 && !regUsedinRange(pc1,pc2,reg2)) {
480 pct2->seq = pc1->seq;
482 pCodeInsertAfter(pc1,pct2);
483 Remove2pcodes(pcfl_used, pc1, pc2, reg);
484 total_registers_saved++; // debugging stats.
490 pct1 = findPrevInstruction(pc1->prev);
492 (PCI(pct1)->pcflow == PCI(pc1)->pcflow) &&
493 (PCI(pct1)->op == POC_MOVFW)) {
495 reg1 = getRegFromInstruction(pct1);
496 if(reg1 && !regUsedinRange(pc1,pc2,reg1)) {
504 pct2 = newpCode(PCI(pc2)->op, PCI(pct1)->pcop);
505 pCodeInsertAfter(pc2, pct2);
506 PCI(pct2)->pcflow = PCFL(pcfl_used);
507 pct2->seq = pc2->seq;
509 Remove2pcodes(pcfl_used, pc1, pc2, reg);
510 Remove2pcodes(pcfl_used, pct1, NULL, reg1);
511 total_registers_saved++; // debugging stats.
520 // fprintf(stderr, " and used in different flows\n");
522 //pc1->print(stderr,pc1);
523 //pc2->print(stderr,pc2);
526 } else if(pcfl_used) {
529 register has been used twice without ever being assigned */
530 fprintf(stderr,"WARNING %s: reg %s used without being assigned\n",__FUNCTION__,reg->name);
533 //fprintf(stderr,"WARNING %s: reg %s assigned without being used\n",__FUNCTION__,reg->name);
534 Remove2pcodes(pcfl_assigned, pc1, pc2, reg);
535 total_registers_saved++; // debugging stats.
539 if(used && !pcfl_used && pcfl_assigned) {
542 //fprintf(stderr,"WARNING %s: reg %s assigned without being used\n",__FUNCTION__,reg->name);
544 pc = setFirstItem(reg->reglives.usedpCodes);
546 pcfl_assigned = PCI(pc)->pcflow;
547 deleteSetItem (&(PCFL(pcfl_assigned)->registers), reg);
548 deleteSetItem (&(reg->reglives.usedpCodes),pc);
551 pc = setNextItem(reg->reglives.usedpCodes);
558 total_registers_saved++; // debugging stats.
566 /*-----------------------------------------------------------------*
567 * void pCodeRegOptimeRegUsage(pBlock *pb)
568 *-----------------------------------------------------------------*/
569 void pCodeRegOptimizeRegUsage(void)
576 saved = total_registers_saved;
578 /* Identify registers used in one flow sequence */
579 OptimizeRegUsage(dynAllocRegs);
580 OptimizeRegUsage(dynStackRegs);
581 OptimizeRegUsage(dynDirectRegs);
583 if(total_registers_saved != saved)
584 fprintf(stderr, " *** Saved %d registers, total saved %d ***\n", total_registers_saved-saved,total_registers_saved);
587 } while( passes-- && (total_registers_saved != saved));
589 fprintf(stderr,"dynamically allocated regs:\n");
590 dbg_regusage(dynAllocRegs);
591 fprintf(stderr,"stack regs:\n");
592 dbg_regusage(dynStackRegs);
593 fprintf(stderr,"direct regs:\n");
594 dbg_regusage(dynDirectRegs);