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 pCodeInsertBefore(pCode *pc1, pCode *pc2);
41 extern void dbg_dumpregusage(void);
42 extern pCode * findPrevInstruction(pCode *pci);
43 extern pBranch * pBranchAppend(pBranch *h, pBranch *n);
44 void unlinkpCode(pCode *pc);
45 extern int pCodeSearchCondition(pCode *pc, unsigned int cond);
46 char *pCode2str(char *str, int size, pCode *pc);
47 void SAFE_snprintf(char **str, size_t *size, const char *format, ...);
48 int total_registers_saved=0;
49 int register_optimization=1;
51 /*-----------------------------------------------------------------*
52 * void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
53 *-----------------------------------------------------------------*/
55 void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
58 if(!reg || ! pcfl || !isPCFL(pcflow))
62 pcfl->registers = newSet();
68 /*-----------------------------------------------------------------*
70 *-----------------------------------------------------------------*/
71 void dbg_regusage(set *fregs)
78 for (reg = setFirstItem(fregs) ; reg ;
79 reg = setNextItem(fregs)) {
81 if(elementsInSet(reg->reglives.usedpCodes)) {
83 fprintf (stderr, "%s addr=0x%03x rIdx=0x%03x",
88 pcfl = setFirstItem(reg->reglives.usedpFlows);
90 fprintf(stderr, "\n used in seq");
93 fprintf(stderr," 0x%03x",pcfl->seq);
94 pcfl = setNextItem(reg->reglives.usedpFlows);
97 pcfl = setFirstItem(reg->reglives.assignedpFlows);
99 fprintf(stderr, "\n assigned in seq");
102 fprintf(stderr," 0x%03x",pcfl->seq);
103 pcfl = setNextItem(reg->reglives.assignedpFlows);
106 pc = setFirstItem(reg->reglives.usedpCodes);
108 fprintf(stderr, "\n used in instructions ");
111 pcfl = PCODE(PCI(pc)->pcflow);
113 fprintf(stderr," 0x%03x:",pcfl->seq);
114 fprintf(stderr,"0x%03x",pc->seq);
116 pc = setNextItem(reg->reglives.usedpCodes);
119 fprintf(stderr, "\n");
124 /*-----------------------------------------------------------------*
126 *-----------------------------------------------------------------*/
127 void dbg_dumpregusage(void)
130 fprintf(stderr,"*** Register Usage ***\n");
131 fprintf(stderr,"InternalRegs:\n");
132 dbg_regusage(dynInternalRegs);
133 fprintf(stderr,"AllocRegs:\n");
134 dbg_regusage(dynAllocRegs);
135 fprintf(stderr,"StackRegs:\n");
136 dbg_regusage(dynStackRegs);
137 fprintf(stderr,"DirectRegs:\n");
138 dbg_regusage(dynDirectRegs);
139 fprintf(stderr,"DirectBitRegs:\n");
140 dbg_regusage(dynDirectBitRegs);
141 fprintf(stderr,"ProcessorRegs:\n");
142 dbg_regusage(dynProcessorRegs);
147 /*-----------------------------------------------------------------*
148 * void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
149 *-----------------------------------------------------------------*/
150 void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
162 pc = findNextInstruction(pcfl->pc.next);
164 while(isPCinFlow(pc,PCODE(pcfl))) {
167 reg = getRegFromInstruction(pc);
171 fprintf(stderr, "flow seq %d, inst seq %d %s ",PCODE(pcfl)->seq,pc->seq,reg->name);
172 fprintf(stderr, "addr = 0x%03x, type = %d rIdx=0x%03x\n",
173 reg->address,reg->type,reg->rIdx);
176 addSetIfnotP(& (PCFL(pcfl)->registers), reg);
178 if((PCC_REGISTER | PCC_LITERAL) & PCI(pc)->inCond)
179 addSetIfnotP(& (reg->reglives.usedpFlows), pcfl);
181 if(PCC_REGISTER & PCI(pc)->outCond)
182 addSetIfnotP(& (reg->reglives.assignedpFlows), pcfl);
184 addSetIfnotP(& (reg->reglives.usedpCodes), pc);
189 pc = findNextInstruction(pc->next);
195 /*-----------------------------------------------------------------*
196 * void pCodeRegMapLiveRanges(pBlock *pb)
197 *-----------------------------------------------------------------*/
198 void pCodeRegMapLiveRanges(pBlock *pb)
202 for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
204 pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
206 if(!isPCFL(pcflow)) {
207 fprintf(stderr, "pCodeRegMapLiveRanges - pcflow is not a flow object ");
210 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
214 for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
216 pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
218 regs *r = setFirstItem(PCFL(pcflow)->registers);
219 fprintf(stderr,"flow seq %d\n", pcflow->seq);
222 fprintf(stderr, " %s\n",r->name);
223 r = setNextItem(PCFL(pcflow)->registers);
230 // dbg_dumpregusage();
235 /*-----------------------------------------------------------------*
237 *-----------------------------------------------------------------*/
238 static void Remove1pcode(pCode *pc, regs *reg, int debug_code)
246 deleteSetItem (&(reg->reglives.usedpCodes),pc);
249 pcn = findNextInstruction(pc->next);
252 PCI(pcn)->label = pBranchAppend(PCI(pcn)->label,PCI(pc)->label);
257 pcn = findNextInstruction(pc->next);
260 if(PCI(pcn)->cline) {
261 //fprintf(stderr, "source line has been optimized completely out\n");
262 //pc->print(stderr,pc);
264 PCI(pcn)->cline = PCI(pc)->cline;
272 Debug stuff. Comment out the instruction we're about to delete.
278 char *pbuff,**ppbuff;
282 SAFE_snprintf(ppbuff,&size, ";%d", debug_code);
283 pCode2str(*ppbuff, size, pc);
284 pCodeInsertBefore(pc, newpCodeCharP(buff1));
285 fprintf(stderr,"removing instruction:\n%s\n",buff1);
292 /*-----------------------------------------------------------------*
293 * void RemoveRegsFromSet(set *regset)
295 *-----------------------------------------------------------------*/
296 void RemoveRegsFromSet(set *regset)
303 regset = regset->next;
305 used = elementsInSet(reg->reglives.usedpCodes);
309 //fprintf(stderr," reg %s isfree=%d, wasused=%d\n",reg->name,reg->isFree,reg->wasUsed);
311 //fprintf(stderr," getting rid of reg %s\n",reg->name);
318 pc = setFirstItem(reg->reglives.usedpCodes);
320 if(reg->type == REG_SFR) {
321 //fprintf(stderr, "not removing SFR reg %s even though used only once\n",reg->name);
328 pCode *pcn = findNextInstruction(pc->next);
330 if(pcn && PCI(pcn)->label) {
331 //fprintf(stderr,"can't delete instruction with label...\n");
332 //pc->print(stderr,pc);
335 /* Move the label to the next instruction */
337 PCI(pcn)->label = PCI(pc)->label;
342 regs *r = getRegFromInstruction(pc);
343 fprintf(stderr, "WARNING, a skip instruction is being optimized out\n");
344 pc->print(stderr,pc);
345 fprintf(stderr,"reg %s, type =%d\n",r->name, r->type);
347 fprintf(stderr," removing reg %s because it is used only once\n",reg->name);
348 Remove1pcode(pc, reg, 1);
351 deleteSetItem (&(reg->reglives.usedpCodes),pc);
355 total_registers_saved++; // debugging stats.
362 /*-----------------------------------------------------------------*
363 * void RemoveUnusedRegisters(void)
365 *-----------------------------------------------------------------*/
366 void RemoveUnusedRegisters(void)
368 /* First, get rid of registers that are used only one time */
370 //RemoveRegsFromSet(dynInternalRegs);
371 RemoveRegsFromSet(dynAllocRegs);
372 RemoveRegsFromSet(dynStackRegs);
374 don't do DirectRegs yet - there's a problem with arrays
375 RemoveRegsFromSet(dynDirectRegs);
377 RemoveRegsFromSet(dynDirectBitRegs);
379 if(total_registers_saved) fprintf(stderr, " *** Saved %d registers ***\n", total_registers_saved);
383 /*-----------------------------------------------------------------*
385 *-----------------------------------------------------------------*/
386 static void Remove2pcodes(pCode *pcflow, pCode *pc1, pCode *pc2, regs *reg, int can_free)
388 static int debug_code=99;
392 fprintf(stderr,"%s\n",__FUNCTION__);
394 Remove1pcode(pc1, reg, debug_code++);
397 Remove1pcode(pc2, reg, debug_code++);
398 deleteSetItem (&(PCFL(pcflow)->registers), reg);
407 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
410 /*-----------------------------------------------------------------*
412 *-----------------------------------------------------------------*/
413 int regUsedinRange(pCode *pc1, pCode *pc2, regs *reg)
419 testreg = getRegFromInstruction(pc1);
420 if(testreg && (testreg->rIdx == reg->rIdx)) {
424 pc1 = findNextInstruction(pc1->next);
426 } while (pc1 && (pc1 != pc2) && (i++ < 100)) ;
429 fprintf(stderr, "warning, regUsedinRange searched through too many pcodes\n");
434 /*-----------------------------------------------------------------*
435 * void pCodeOptime2pCodes(pCode *pc1, pCode *pc2)
437 * ADHOC pattern checking
438 * Now look for specific sequences that are easy to optimize.
439 * Many of these sequences are characteristic of the compiler
440 * (i.e. it'd probably be a waste of time to apply these adhoc
441 * checks to hand written assembly.)
444 *-----------------------------------------------------------------*/
445 int pCodeOptime2pCodes(pCode *pc1, pCode *pc2, pCode *pcfl_used, regs *reg, int can_free, int optimize_level)
450 int t = total_registers_saved;
452 if(pc2->seq < pc1->seq) {
458 fprintf(stderr,"pCodeOptime2pCodes\n");
459 pc1->print(stderr,pc1);
460 pc2->print(stderr,pc2);
462 if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_MOVFW) ){
476 fprintf(stderr, " CLRF/MOVFW. instruction after MOVFW is:\n");
477 pct1 = findNextInstruction(pc2->next);
479 if(PCI(pct1)->op == POC_MOVWF) {
480 newpc = newpCode(POC_CLRF, PCI(pct1)->pcop);
481 pct1->destruct(pct1);
483 newpc = newpCode(POC_MOVLW, newpCodeOpLit(0));
486 pCodeInsertAfter(pc2, newpc);
487 PCI(newpc)->pcflow = PCFL(pcfl_used);
488 newpc->seq = pc2->seq;
490 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
491 total_registers_saved++; // debugging stats.
493 } else if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_IORFW) ){
494 fprintf(stderr, " CLRF/IORFW.\n");
496 pct2 = findNextInstruction(pc2->next);
498 if(pCodeSearchCondition(pct2, PCC_Z) > 0) {
499 pct2 = newpCode(POC_IORLW, newpCodeOpLit(0));
500 pct2->seq = pc2->seq;
501 PCI(pct2)->pcflow = PCFL(pcfl_used);
502 pCodeInsertAfter(pc1,pct2);
504 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
505 total_registers_saved++; // debugging stats.
507 } else if(PCI(pc1)->op == POC_MOVWF) {
509 pct2 = findNextInstruction(pc2->next);
511 if(PCI(pc2)->op == POC_MOVFW) {
513 fprintf(stderr, " MOVWF/MOVFW. instruction after MOVFW is:\n");
514 pct2->print(stderr,pct2);
517 if(PCI(pct2)->op == POC_MOVWF) {
532 reg2 = getRegFromInstruction(pct2);
533 //if(reg2 && !regUsedinRange(pc1,pc2,reg2) && (reg2->type != REG_SFR)) {
534 if(reg2 && !regUsedinRange(pc1,pc2,reg2)) {
536 if(pCodeSearchCondition(pct2, PCC_Z) < 1) {
537 pCode *pct3 = findNextInstruction(pct2->next);
538 fprintf(stderr,"ABCD\n");
539 pct2->seq = pc1->seq;
541 pCodeInsertAfter(findPrevInstruction(pc1->prev),pct2);
543 #define usesW(x) ((x) && (isPCI(x)) && ( (PCI(x)->inCond & PCC_W) != 0))
546 ; // Remove2pcodes(pcfl_used, pc1, NULL, reg, can_free);
548 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
550 total_registers_saved++; // debugging stats.
553 //fprintf(stderr,"didn't optimize because Z bit is used\n");
557 fprintf(stderr, " couldn't optimize\n");
559 fprintf(stderr, " %s is used in range\n",reg2->name);
561 fprintf(stderr, " reg2 is NULL\n");
566 pct1 = findPrevInstruction(pc1->prev);
567 if(pct1 && (PCI(pct1)->pcflow == PCI(pc1)->pcflow)) {
569 if ( (PCI(pct1)->op == POC_MOVFW) &&
570 (PCI(pc2)->op == POC_MOVFW)) {
572 reg1 = getRegFromInstruction(pct1);
573 if(reg1 && !regUsedinRange(pc1,pc2,reg1)) {
575 fprintf(stderr, " MOVF/MOVFW. \n");
576 fprintf(stderr, " ...optimizing\n");
594 Or, if we're not deleting the register then the "To" is:
603 pct2 = newpCode(PCI(pc2)->op, PCI(pct1)->pcop);
604 pCodeInsertAfter(pc2, pct2);
605 PCI(pct2)->pcflow = PCFL(pcfl_used);
606 pct2->seq = pc2->seq;
609 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
611 /* If we're not freeing the register then that means (probably)
612 * the register is needed somewhere else.*/
614 pCodeInsertAfter(pct2, pc1);
616 Remove2pcodes(pcfl_used, pc2, NULL, reg, can_free);
619 Remove2pcodes(pcfl_used, pct1, NULL, reg1, 0);
620 total_registers_saved++; // debugging stats.
623 } else if ( (PCI(pct1)->op == POC_MOVWF) &&
624 (PCI(pc2)->op == POC_MOVFW)) {
625 //fprintf(stderr,"movwf MOVWF/MOVFW\n");
626 if(optimize_level > 1 && can_free) {
627 pct2 = newpCode(POC_MOVFW, PCI(pc1)->pcop);
628 pCodeInsertAfter(pc2, pct2);
629 Remove2pcodes(pcfl_used, pc1, pc2, reg, 1);
630 total_registers_saved++; // debugging stats.
639 return (total_registers_saved != t);
642 /*-----------------------------------------------------------------*
643 * void pCodeRegOptimeRegUsage(pBlock *pb)
644 *-----------------------------------------------------------------*/
645 void OptimizeRegUsage(set *fregs, int optimize_multi_uses, int optimize_level)
649 pCode *pc1=NULL, *pc2=NULL;
653 pCode *pcfl_used, *pcfl_assigned;
655 /* Step through the set by directly accessing the 'next' pointer.
656 * We could also step through by using the set API, but the
657 * the (debug) calls to print instructions affect the state
658 * of the set pointers */
663 if(reg->type == REG_SFR) {
664 //fprintf(stderr,"skipping SFR: %s\n",reg->name);
668 pcfl_used = setFirstItem(reg->reglives.usedpFlows);
669 pcfl_assigned = setFirstItem(reg->reglives.assignedpFlows);
671 used = elementsInSet(reg->reglives.usedpCodes);
675 * In this section, all registers that are used in only in two
676 * instructions are examined. If possible, they're optimized out.
680 fprintf (stderr, "OptimizeRegUsage: %s addr=0x%03x rIdx=0x%03x type=%d used=%d\n",
683 reg->rIdx, reg->type, used);
685 pc1 = setFirstItem(reg->reglives.usedpCodes);
686 pc2 = setNextItem(reg->reglives.usedpCodes);
688 if(pcfl_used && pcfl_assigned) {
691 expected case - the register has been assigned a value and is
695 //fprintf(stderr," used only twice\n");
696 if(pcfl_used->seq == pcfl_assigned->seq) {
698 //fprintf(stderr, " and used in same flow\n");
700 pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 1,optimize_level);
703 // fprintf(stderr, " and used in different flows\n");
707 } else if(pcfl_used) {
710 register has been used twice without ever being assigned */
711 fprintf(stderr,"WARNING %s: reg %s used without being assigned\n",__FUNCTION__,reg->name);
714 fprintf(stderr,"WARNING %s: reg %s assigned without being used\n",__FUNCTION__,reg->name);
715 Remove2pcodes(pcfl_assigned, pc1, pc2, reg, 1);
716 total_registers_saved++; // debugging stats.
720 /* register has been used either once, or more than twice */
722 if(used && !pcfl_used && pcfl_assigned) {
725 fprintf(stderr,"WARNING %s: reg %s assigned without being used\n",__FUNCTION__,reg->name);
727 pc = setFirstItem(reg->reglives.usedpCodes);
730 pcfl_assigned = PCODE(PCI(pc)->pcflow);
731 Remove1pcode(pc, reg,2);
733 deleteSetItem (&(PCFL(pcfl_assigned)->registers), reg);
735 deleteSetItem (&(reg->reglives.usedpCodes),pc);
738 pc = setNextItem(reg->reglives.usedpCodes);
745 total_registers_saved++; // debugging stats.
746 } else if( (used > 2) && optimize_multi_uses) {
752 pCodeFlow *pcfl1=NULL, *pcfl2=NULL;
754 /* examine the number of times this register is used */
757 rset1 = reg->reglives.usedpCodes;
758 while(rset1 && searching) {
763 if(pc1 && isPCI(pc1) && ( (pcfl1 = PCI(pc1)->pcflow) != NULL) ) {
765 //while(rset2 && searching) {
769 if(pc2 && isPCI(pc2) && ( (pcfl2 = PCI(pc2)->pcflow) != NULL) ) {
772 if(pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 0,optimize_level))
777 //rset2 = rset2->next;
789 /*-----------------------------------------------------------------*
790 * void pCodeRegOptimeRegUsage(pBlock *pb)
791 *-----------------------------------------------------------------*/
792 void pCodeRegOptimizeRegUsage(int level)
797 int t = total_registers_saved;
799 if(!register_optimization)
805 saved = total_registers_saved;
807 /* Identify registers used in one flow sequence */
808 OptimizeRegUsage(dynAllocRegs,level, (OPT_PASSES-passes));
809 OptimizeRegUsage(dynStackRegs,level, (OPT_PASSES-passes));
810 OptimizeRegUsage(dynDirectRegs,0, (OPT_PASSES-passes));
812 if(total_registers_saved != saved)
813 fprintf(stderr, " *** pass %d, Saved %d registers, total saved %d ***\n",
814 (1+OPT_PASSES-passes),total_registers_saved-saved,total_registers_saved);
818 } while( passes && ((total_registers_saved != saved) || (passes==OPT_PASSES-1)) );
820 if(total_registers_saved == t)
821 fprintf(stderr, "No registers saved on this pass\n");
825 fprintf(stderr,"dynamically allocated regs:\n");
826 dbg_regusage(dynAllocRegs);
827 fprintf(stderr,"stack regs:\n");
828 dbg_regusage(dynStackRegs);
829 fprintf(stderr,"direct regs:\n");
830 dbg_regusage(dynDirectRegs);
835 /*-----------------------------------------------------------------*
836 * void RegsUnMapLiveRanges(set *regset)
838 *-----------------------------------------------------------------*/
839 void RegsSetUnMapLiveRanges(set *regset)
845 regset = regset->next;
848 deleteSet(®->reglives.usedpCodes);
849 deleteSet(®->reglives.usedpFlows);
850 deleteSet(®->reglives.assignedpFlows);
856 void RegsUnMapLiveRanges(void)
859 RegsSetUnMapLiveRanges(dynAllocRegs);
860 RegsSetUnMapLiveRanges(dynStackRegs);
861 RegsSetUnMapLiveRanges(dynDirectRegs);
862 RegsSetUnMapLiveRanges(dynProcessorRegs);
863 RegsSetUnMapLiveRanges(dynDirectBitRegs);
864 RegsSetUnMapLiveRanges(dynInternalRegs);