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 extern pBranch * pBranchAppend(pBranch *h, pBranch *n);
43 void unlinkpCode(pCode *pc);
45 int total_registers_saved=0;
47 /*-----------------------------------------------------------------*
48 * void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
49 *-----------------------------------------------------------------*/
51 void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
54 if(!reg || ! pcfl || !isPCFL(pcflow))
58 pcfl->registers = newSet();
64 /*-----------------------------------------------------------------*
66 *-----------------------------------------------------------------*/
67 void dbg_regusage(set *fregs)
74 for (reg = setFirstItem(fregs) ; reg ;
75 reg = setNextItem(fregs)) {
77 if(elementsInSet(reg->reglives.usedpCodes)) {
79 fprintf (stderr, "%s addr=0x%03x rIdx=0x%03x",
84 pcfl = setFirstItem(reg->reglives.usedpFlows);
86 fprintf(stderr, "\n used in seq");
89 fprintf(stderr," 0x%03x",pcfl->seq);
90 pcfl = setNextItem(reg->reglives.usedpFlows);
93 pcfl = setFirstItem(reg->reglives.assignedpFlows);
95 fprintf(stderr, "\n assigned in seq");
98 fprintf(stderr," 0x%03x",pcfl->seq);
99 pcfl = setNextItem(reg->reglives.assignedpFlows);
102 pc = setFirstItem(reg->reglives.usedpCodes);
104 fprintf(stderr, "\n used in instructions ");
107 pcfl = PCODE(PCI(pc)->pcflow);
109 fprintf(stderr," 0x%03x:",pcfl->seq);
110 fprintf(stderr,"0x%03x",pc->seq);
112 pc = setNextItem(reg->reglives.usedpCodes);
115 fprintf(stderr, "\n");
120 /*-----------------------------------------------------------------*
122 *-----------------------------------------------------------------*/
123 void dbg_dumpregusage(void)
126 fprintf(stderr,"*** Register Usage ***\n");
127 fprintf(stderr,"InternalRegs:\n");
128 dbg_regusage(dynInternalRegs);
129 fprintf(stderr,"AllocRegs:\n");
130 dbg_regusage(dynAllocRegs);
131 fprintf(stderr,"StackRegs:\n");
132 dbg_regusage(dynStackRegs);
133 fprintf(stderr,"DirectRegs:\n");
134 dbg_regusage(dynDirectRegs);
135 fprintf(stderr,"DirectBitRegs:\n");
136 dbg_regusage(dynDirectBitRegs);
137 fprintf(stderr,"ProcessorRegs:\n");
138 dbg_regusage(dynProcessorRegs);
143 /*-----------------------------------------------------------------*
144 * void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
145 *-----------------------------------------------------------------*/
146 void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
158 pc = findNextInstruction(pcfl->pc.next);
160 while(isPCinFlow(pc,PCODE(pcfl))) {
163 reg = getRegFromInstruction(pc);
167 fprintf(stderr, "flow seq %d, inst seq %d %s ",PCODE(pcfl)->seq,pc->seq,reg->name);
168 fprintf(stderr, "addr = 0x%03x, type = %d rIdx=0x%03x\n",
169 reg->address,reg->type,reg->rIdx);
172 addSetIfnotP(& (PCFL(pcfl)->registers), reg);
174 if((PCC_REGISTER | PCC_LITERAL) & PCI(pc)->inCond)
175 addSetIfnotP(& (reg->reglives.usedpFlows), pcfl);
177 if(PCC_REGISTER & PCI(pc)->outCond)
178 addSetIfnotP(& (reg->reglives.assignedpFlows), pcfl);
180 addSetIfnotP(& (reg->reglives.usedpCodes), pc);
185 pc = findNextInstruction(pc->next);
191 /*-----------------------------------------------------------------*
192 * void pCodeRegMapLiveRanges(pBlock *pb)
193 *-----------------------------------------------------------------*/
194 void pCodeRegMapLiveRanges(pBlock *pb)
198 for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
200 pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
202 if(!isPCFL(pcflow)) {
203 fprintf(stderr, "pCodeRegMapLiveRanges - pcflow is not a flow object ");
206 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
210 for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
212 pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
214 regs *r = setFirstItem(PCFL(pcflow)->registers);
215 //fprintf(stderr,"flow seq %d\n", pcflow->seq);
217 //fprintf(stderr, " %s\n",r->name);
218 r = setNextItem(PCFL(pcflow)->registers);
224 // dbg_dumpregusage();
229 /*-----------------------------------------------------------------*
231 *-----------------------------------------------------------------*/
232 static void Remove1pcode(pCode *pc, regs *reg)
239 deleteSetItem (&(reg->reglives.usedpCodes),pc);
241 fprintf(stderr,"removing instruction:\n");
242 pc->print(stderr,pc);
245 pcn = findNextInstruction(pc->next);
248 PCI(pcn)->label = pBranchAppend(PCI(pcn)->label,PCI(pc)->label);
253 pcn = findNextInstruction(pc->next);
256 if(PCI(pcn)->cline) {
257 //fprintf(stderr, "source line has been optimized completely out\n");
258 //pc->print(stderr,pc);
260 PCI(pcn)->cline = PCI(pc)->cline;
269 /*-----------------------------------------------------------------*
270 * void RemoveRegsFromSet(set *regset)
272 *-----------------------------------------------------------------*/
273 void RemoveRegsFromSet(set *regset)
280 regset = regset->next;
283 for (reg = setFirstItem(regset) ; reg ;
284 reg = setNextItem(regset)) {
286 used = elementsInSet(reg->reglives.usedpCodes);
290 //fprintf(stderr," reg %s isfree=%d, wasused=%d\n",reg->name,reg->isFree,reg->wasUsed);
292 //fprintf(stderr," getting rid of reg %s\n",reg->name);
299 pc = setFirstItem(reg->reglives.usedpCodes);
301 if(reg->type == REG_SFR) {
302 //fprintf(stderr, "not removing SFR reg %s even though used only once\n",reg->name);
309 pCode *pcn = findNextInstruction(pc->next);
311 if(pcn && PCI(pcn)->label) {
312 //fprintf(stderr,"can't delete instruction with label...\n");
313 //pc->print(stderr,pc);
316 /* Move the label to the next instruction */
318 PCI(pcn)->label = PCI(pc)->label;
323 regs *r = getRegFromInstruction(pc);
324 fprintf(stderr, "WARNING, a skip instruction is being optimized out\n");
325 pc->print(stderr,pc);
326 fprintf(stderr,"reg %s, type =%d\n",r->name, r->type);
328 //fprintf(stderr," removing reg %s because it is used only once\n",reg->name);
329 Remove1pcode(pc, reg);
332 deleteSetItem (&(reg->reglives.usedpCodes),pc);
336 total_registers_saved++; // debugging stats.
343 /*-----------------------------------------------------------------*
344 * void RemoveUnusedRegisters(void)
346 *-----------------------------------------------------------------*/
347 void RemoveUnusedRegisters(void)
349 /* First, get rid of registers that are used only one time */
352 RemoveRegsFromSet(dynInternalRegs);
353 RemoveRegsFromSet(dynAllocRegs);
354 RemoveRegsFromSet(dynStackRegs);
356 don't do DirectRegs yet - there's a problem with arrays
357 RemoveRegsFromSet(dynDirectRegs);
359 RemoveRegsFromSet(dynDirectBitRegs);
361 if(total_registers_saved) fprintf(stderr, " *** Saved %d registers ***\n", total_registers_saved);
365 /*-----------------------------------------------------------------*
367 *-----------------------------------------------------------------*/
368 static void Remove2pcodes(pCode *pcflow, pCode *pc1, pCode *pc2, regs *reg)
374 Remove1pcode(pc1, reg);
377 Remove1pcode(pc2, reg);
378 deleteSetItem (&(PCFL(pcflow)->registers), reg);
385 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
388 /*-----------------------------------------------------------------*
390 *-----------------------------------------------------------------*/
391 int regUsedinRange(pCode *pc1, pCode *pc2, regs *reg)
397 testreg = getRegFromInstruction(pc1);
398 if(testreg && (testreg->rIdx == reg->rIdx)) {
402 pc1 = findNextInstruction(pc1->next);
404 } while (pc1 && (pc1 != pc2) && (i++ < 100)) ;
407 fprintf(stderr, "warning, regUsedinRange searched through too many pcodes\n");
412 /*-----------------------------------------------------------------*
413 * void pCodeRegOptimeRegUsage(pBlock *pb)
414 *-----------------------------------------------------------------*/
415 void OptimizeRegUsage(set *fregs)
422 pCode *pcfl_used, *pcfl_assigned;
424 /* Step through the set by directly accessing the 'next' pointer.
425 * We could also step through by using the set API, but the
426 * the (debug) calls to print instructions affect the state
427 * of the set pointers */
432 if(reg->type == REG_SFR) {
433 //fprintf(stderr,"skipping SFR: %s\n",reg->name);
437 pcfl_used = setFirstItem(reg->reglives.usedpFlows);
438 pcfl_assigned = setFirstItem(reg->reglives.assignedpFlows);
440 used = elementsInSet(reg->reglives.usedpCodes);
444 * In this section, all registers that are used in only in two
445 * instructions are examined. If possible, they're optimized out.
449 pCode *pct1, *pct2; /* two temporaries */
453 fprintf (stderr, "OptimizeRegUsage: %s addr=0x%03x rIdx=0x%03x type=%d used=%d\n",
456 reg->rIdx, reg->type, used);
458 pc1 = setFirstItem(reg->reglives.usedpCodes);
459 pc2 = setNextItem(reg->reglives.usedpCodes);
461 if(pcfl_used && pcfl_assigned) {
464 expected case - the register has been assigned a value and is
468 //fprintf(stderr," used only twice\n");
469 if(pcfl_used->seq == pcfl_assigned->seq) {
471 //fprintf(stderr, " and used in same flow\n");
472 if(pc2->seq < pc1->seq) {
478 //pc1->print(stderr,pc1);
479 //pc2->print(stderr,pc2);
482 /* ADHOC pattern checking
483 * Now look for specific sequences that are easy to optimize.
484 * Many of these sequences are characteristic of the compiler
485 * (i.e. it'd probably be a waste of time to apply these adhoc
486 * checks to hand written assembly.)
489 if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_MOVFW) ){
503 //fprintf(stderr, " CLRF/MOVFW. instruction after MOVFW is:\n");
504 pct1 = findNextInstruction(pc2->next);
505 //t->print(stderr,t);
507 if(PCI(pct1)->op == POC_MOVWF) {
508 newpc = newpCode(POC_CLRF, PCI(pct1)->pcop);
509 pct1->destruct(pct1);
511 newpc = newpCode(POC_MOVLW, newpCodeOpLit(0));
514 pCodeInsertAfter(pc2, newpc);
515 PCI(newpc)->pcflow = PCFL(pcfl_used);
516 newpc->seq = pc2->seq;
518 Remove2pcodes(pcfl_used, pc1, pc2, reg);
519 total_registers_saved++; // debugging stats.
521 } else if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_IORFW) ){
522 //fprintf(stderr, " CLRF/IORWF.\n");
524 Remove2pcodes(pcfl_used, pc1, pc2, reg);
525 total_registers_saved++; // debugging stats.
527 } else if(PCI(pc1)->op == POC_MOVWF) {
529 pct2 = findNextInstruction(pc2->next);
531 if(PCI(pc2)->op == POC_MOVFW) {
532 //fprintf(stderr, " MOVWF/MOVFW. instruction after MOVFW is:\n");
533 // t->print(stderr,t);
535 if(PCI(pct2)->op == POC_MOVWF) {
536 reg2 = getRegFromInstruction(pct2);
537 if(reg2 && !regUsedinRange(pc1,pc2,reg2)) {
538 pct2->seq = pc1->seq;
540 pCodeInsertAfter(pc1,pct2);
541 Remove2pcodes(pcfl_used, pc1, pc2, reg);
542 total_registers_saved++; // debugging stats.
548 pct1 = findPrevInstruction(pc1->prev);
550 (PCI(pct1)->pcflow == PCI(pc1)->pcflow) &&
551 (PCI(pct1)->op == POC_MOVFW)) {
553 reg1 = getRegFromInstruction(pct1);
554 if(reg1 && !regUsedinRange(pc1,pc2,reg1)) {
555 //fprintf(stderr, " MOVF/MOVFW. \n");
563 pct2 = newpCode(PCI(pc2)->op, PCI(pct1)->pcop);
564 pCodeInsertAfter(pc2, pct2);
565 PCI(pct2)->pcflow = PCFL(pcfl_used);
566 pct2->seq = pc2->seq;
568 Remove2pcodes(pcfl_used, pc1, pc2, reg);
569 Remove2pcodes(pcfl_used, pct1, NULL, reg1);
570 total_registers_saved++; // debugging stats.
579 // fprintf(stderr, " and used in different flows\n");
581 //pc1->print(stderr,pc1);
582 //pc2->print(stderr,pc2);
585 } else if(pcfl_used) {
588 register has been used twice without ever being assigned */
589 //fprintf(stderr,"WARNING %s: reg %s used without being assigned\n",__FUNCTION__,reg->name);
592 //fprintf(stderr,"WARNING %s: reg %s assigned without being used\n",__FUNCTION__,reg->name);
593 Remove2pcodes(pcfl_assigned, pc1, pc2, reg);
594 total_registers_saved++; // debugging stats.
598 if(used && !pcfl_used && pcfl_assigned) {
601 //fprintf(stderr,"WARNING %s: reg %s assigned without being used\n",__FUNCTION__,reg->name);
603 pc = setFirstItem(reg->reglives.usedpCodes);
606 pcfl_assigned = PCODE(PCI(pc)->pcflow);
607 Remove1pcode(pc, reg);
609 deleteSetItem (&(PCFL(pcfl_assigned)->registers), reg);
611 deleteSetItem (&(reg->reglives.usedpCodes),pc);
614 pc = setNextItem(reg->reglives.usedpCodes);
621 total_registers_saved++; // debugging stats.
629 /*-----------------------------------------------------------------*
630 * void pCodeRegOptimeRegUsage(pBlock *pb)
631 *-----------------------------------------------------------------*/
632 void pCodeRegOptimizeRegUsage(void)
639 saved = total_registers_saved;
641 /* Identify registers used in one flow sequence */
642 OptimizeRegUsage(dynAllocRegs);
643 OptimizeRegUsage(dynStackRegs);
644 OptimizeRegUsage(dynDirectRegs);
646 if(total_registers_saved != saved)
647 fprintf(stderr, " *** Saved %d registers, total saved %d ***\n", total_registers_saved-saved,total_registers_saved);
650 } while( passes-- && (total_registers_saved != saved));
652 fprintf(stderr,"dynamically allocated regs:\n");
653 dbg_regusage(dynAllocRegs);
654 fprintf(stderr,"stack regs:\n");
655 dbg_regusage(dynStackRegs);
656 fprintf(stderr,"direct regs:\n");
657 dbg_regusage(dynDirectRegs);