1 /*-------------------------------------------------------------------------
3 pcoderegs.c - post code generation register optimizations
5 Written By - Scott Dattalo scott@dattalo.com
6 Ported To PIC16 By - m.dubuc@rogers.com
8 This program is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by the
10 Free Software Foundation; either version 2, or (at your option) any
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
22 -------------------------------------------------------------------------*/
27 The purpose of the code in this file is to optimize the register usage.
32 #include "common.h" // Include everything in the SDCC src directory
37 #include "pcoderegs.h"
38 #include "pcodeflow.h"
40 extern void pic16_pCodeInsertAfter(pCode *pc1, pCode *pc2);
41 extern pCode * pic16_findPrevInstruction(pCode *pci);
42 extern pBranch * pic16_pBranchAppend(pBranch *h, pBranch *n);
43 void pic16_unlinkpCode(pCode *pc);
44 extern int pic16_pCodeSearchCondition(pCode *pc, unsigned int cond);
46 static int total_registers_saved=0;
47 static int register_optimization=1;
49 /*-----------------------------------------------------------------*
50 * void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
51 *-----------------------------------------------------------------*/
53 void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
56 if(!reg || ! pcfl || !isPCFL(pcflow))
60 pcfl->registers = newSet();
66 /*-----------------------------------------------------------------*
68 *-----------------------------------------------------------------*/
70 static void dbg_regusage(set *fregs)
77 for (reg = setFirstItem(fregs) ; reg ;
78 reg = setNextItem(fregs)) {
80 if(elementsInSet(reg->reglives.usedpCodes)) {
82 fprintf (stderr, "%s addr=0x%03x rIdx=0x%03x",
87 pcfl = setFirstItem(reg->reglives.usedpFlows);
89 fprintf(stderr, "\n used in seq");
92 fprintf(stderr," 0x%03x",pcfl->seq);
93 pcfl = setNextItem(reg->reglives.usedpFlows);
96 pcfl = setFirstItem(reg->reglives.assignedpFlows);
98 fprintf(stderr, "\n assigned in seq");
101 fprintf(stderr," 0x%03x",pcfl->seq);
102 pcfl = setNextItem(reg->reglives.assignedpFlows);
105 pc = setFirstItem(reg->reglives.usedpCodes);
107 fprintf(stderr, "\n used in instructions ");
110 pcfl = PCODE(PCI(pc)->pcflow);
112 fprintf(stderr," 0x%03x:",pcfl->seq);
113 fprintf(stderr,"0x%03x",pc->seq);
115 pc = setNextItem(reg->reglives.usedpCodes);
118 fprintf(stderr, "\n");
124 /*-----------------------------------------------------------------*
126 *-----------------------------------------------------------------*/
128 static void dbg_dumpregusage(void)
131 fprintf(stderr,"*** Register Usage ***\n");
132 fprintf(stderr,"InternalRegs:\n");
133 dbg_regusage(pic16_dynInternalRegs);
134 fprintf(stderr,"AllocRegs:\n");
135 dbg_regusage(pic16_dynAllocRegs);
136 fprintf(stderr,"StackRegs:\n");
137 dbg_regusage(pic16_dynStackRegs);
138 fprintf(stderr,"DirectRegs:\n");
139 dbg_regusage(pic16_dynDirectRegs);
140 fprintf(stderr,"DirectBitRegs:\n");
141 dbg_regusage(pic16_dynDirectBitRegs);
142 fprintf(stderr,"ProcessorRegs:\n");
143 dbg_regusage(pic16_dynProcessorRegs);
148 /*-----------------------------------------------------------------*
149 * void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
150 *-----------------------------------------------------------------*/
151 static void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
163 pc = pic16_findNextInstruction(pcfl->pc.next);
165 while(pic16_isPCinFlow(pc,PCODE(pcfl))) {
168 reg = pic16_getRegFromInstruction(pc);
173 fprintf(stderr, "reg= %p\n", reg);
174 fprintf(stderr, "flow seq %d, inst seq %d %s ",PCODE(pcfl)->seq,pc->seq,reg->name);
175 fprintf(stderr, "addr = 0x%03x, type = %d rIdx=0x%03x",
176 reg->address,reg->type,reg->rIdx);
177 fprintf(stderr, "command = %s\n", PCI(pc)->mnemonic);
181 addSetIfnotP(& (PCFL(pcfl)->registers), reg);
183 if((PCC_REGISTER | PCC_LITERAL) & PCI(pc)->inCond)
184 addSetIfnotP(& (reg->reglives.usedpFlows), pcfl);
186 if(PCC_REGISTER & PCI(pc)->outCond)
187 addSetIfnotP(& (reg->reglives.assignedpFlows), pcfl);
189 addSetIfnotP(& (reg->reglives.usedpCodes), pc);
192 /* check to see if this pCode has 2 memory operands,
193 and set up the second operand too */
194 if(PCI(pc)->is2MemOp) {
195 reg = pic16_getRegFromInstruction2(pc);
197 // fprintf(stderr, "trying to get second operand from pCode reg= %s\n", reg->name);
198 addSetIfnotP(& (PCFL(pcfl)->registers), reg);
200 if((PCC_REGISTER | PCC_LITERAL) & PCI(pc)->inCond)
201 addSetIfnotP(& (reg->reglives.usedpFlows), pcfl);
203 if(PCC_REGISTER & PCI(pc)->outCond)
204 addSetIfnotP(& (reg->reglives.assignedpFlows), pcfl);
206 addSetIfnotP(& (reg->reglives.usedpCodes), pc);
215 pc = pic16_findNextInstruction(pc->next);
221 /*-----------------------------------------------------------------*
222 * void pic16_pCodeRegMapLiveRanges(pBlock *pb)
223 *-----------------------------------------------------------------*/
224 void pic16_pCodeRegMapLiveRanges(pBlock *pb)
228 for( pcflow = pic16_findNextpCode(pb->pcHead, PC_FLOW);
230 pcflow = pic16_findNextpCode(pcflow->next, PC_FLOW) ) {
232 if(!isPCFL(pcflow)) {
233 fprintf(stderr, "pCodeRegMapLiveRanges - pcflow is not a flow object ");
236 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
240 for( pcflow = pic16_findNextpCode(pb->pcHead, PC_FLOW);
242 pcflow = pic16_findNextpCode(pcflow->next, PC_FLOW) ) {
244 regs *r = setFirstItem(PCFL(pcflow)->registers);
245 fprintf(stderr,"flow seq %d\n", pcflow->seq);
248 fprintf(stderr, " %s\n",r->name);
249 r = setNextItem(PCFL(pcflow)->registers);
256 // dbg_dumpregusage();
261 /*-----------------------------------------------------------------*
263 *-----------------------------------------------------------------*/
264 static void Remove1pcode(pCode *pc, regs *reg)
271 deleteSetItem (&(reg->reglives.usedpCodes),pc);
274 fprintf(stderr,"removing instruction:\n");
275 pc->print(stderr,pc);
279 pcn = pic16_findNextInstruction(pc->next);
282 PCI(pcn)->label = pic16_pBranchAppend(PCI(pcn)->label,PCI(pc)->label);
287 pcn = pic16_findNextInstruction(pc->next);
290 if(PCI(pcn)->cline) {
291 //fprintf(stderr, "source line has been optimized completely out\n");
292 //pc->print(stderr,pc);
294 PCI(pcn)->cline = PCI(pc)->cline;
303 /*-----------------------------------------------------------------*
304 * void RemoveRegsFromSet(set *regset)
306 *-----------------------------------------------------------------*/
307 static void RemoveRegsFromSet(set *regset)
314 regset = regset->next;
316 used = elementsInSet(reg->reglives.usedpCodes);
320 // fprintf(stderr," reg %s isfree=%d, wasused=%d\n",reg->name,reg->isFree,reg->wasUsed);
322 // fprintf(stderr,"%s:%d: getting rid of reg %s\n",__FILE__, __LINE__, reg->name);
329 pc = setFirstItem(reg->reglives.usedpCodes);
331 if(reg->type == REG_SFR) {
332 fprintf(stderr, "not removing SFR reg %s even though used only once\n",reg->name);
339 pCode *pcn = pic16_findNextInstruction(pc->next);
341 if(pcn && PCI(pcn)->label) {
342 //fprintf(stderr,"can't delete instruction with label...\n");
343 //pc->print(stderr,pc);
346 /* Move the label to the next instruction */
348 PCI(pcn)->label = PCI(pc)->label;
353 regs *r = pic16_getRegFromInstruction(pc);
354 fprintf(stderr, "WARNING, a skip instruction is being optimized out\n");
355 pc->print(stderr,pc);
356 fprintf(stderr,"reg %s, type =%d\n",r->name, r->type);
358 // fprintf(stderr,"%s:%d: removing reg %s because it is used only once\n",__FILE__, __LINE__, reg->name);
359 Remove1pcode(pc, reg);
361 pic16_unlinkpCode(pc);
362 deleteSetItem (&(reg->reglives.usedpCodes),pc);
366 total_registers_saved++; // debugging stats.
373 /*-----------------------------------------------------------------*
374 * void pic16_RemoveUnusedRegisters(void)
376 *-----------------------------------------------------------------*/
377 void pic16_RemoveUnusedRegisters(void)
379 /* First, get rid of registers that are used only one time */
381 //RemoveRegsFromSet(pic16_dynInternalRegs);
382 RemoveRegsFromSet(pic16_dynAllocRegs);
383 RemoveRegsFromSet(pic16_dynStackRegs);
385 don't do DirectRegs yet - there's a problem with arrays
386 RemoveRegsFromSet(pic16_dynDirectRegs);
388 RemoveRegsFromSet(pic16_dynDirectBitRegs);
390 if(total_registers_saved && pic16_pcode_verbose)
391 fprintf(stderr, " *** Saved %d registers ***\n", total_registers_saved);
395 /*-----------------------------------------------------------------*
397 *-----------------------------------------------------------------*/
398 static void Remove2pcodes(pCode *pcflow, pCode *pc1, pCode *pc2, regs *reg, int can_free)
404 Remove1pcode(pc1, reg);
407 Remove1pcode(pc2, reg);
408 deleteSetItem (&(PCFL(pcflow)->registers), reg);
417 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
420 /*-----------------------------------------------------------------*
422 *-----------------------------------------------------------------*/
423 static int regUsedinRange(pCode *pc1, pCode *pc2, regs *reg)
429 testreg = pic16_getRegFromInstruction(pc1);
430 if(testreg && (testreg->rIdx == reg->rIdx)) {
434 pc1 = pic16_findNextInstruction(pc1->next);
436 } while (pc1 && (pc1 != pc2) && (i++ < 100)) ;
439 fprintf(stderr, "warning, regUsedinRange searched through too many pcodes\n");
444 /*-----------------------------------------------------------------*
445 * void pCodeOptime2pCodes(pCode *pc1, pCode *pc2)
447 * ADHOC pattern checking
448 * Now look for specific sequences that are easy to optimize.
449 * Many of these sequences are characteristic of the compiler
450 * (i.e. it'd probably be a waste of time to apply these adhoc
451 * checks to hand written assembly.)
454 *-----------------------------------------------------------------*/
455 static int pCodeOptime2pCodes(pCode *pc1, pCode *pc2, pCode *pcfl_used, regs *reg, int can_free, int optimize_level)
460 int t = total_registers_saved;
462 if(pc2->seq < pc1->seq) {
468 fprintf(stderr,"pCodeOptime2pCodes\n");
469 pc1->print(stderr,pc1);
470 pc2->print(stderr,pc2);
472 if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_MOVFW) ){
486 //fprintf(stderr, " CLRF/MOVFW. instruction after MOVFW is:\n");
487 pct1 = pic16_findNextInstruction(pc2->next);
489 if(PCI(pct1)->op == POC_MOVWF) {
490 newpc = pic16_newpCode(POC_CLRF, PCI(pct1)->pcop);
491 pct1->destruct(pct1);
493 newpc = pic16_newpCode(POC_MOVLW, pic16_newpCodeOpLit(0));
496 pic16_pCodeInsertAfter(pc2, newpc);
497 PCI(newpc)->pcflow = PCFL(pcfl_used);
498 newpc->seq = pc2->seq;
500 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
501 total_registers_saved++; // debugging stats.
503 } else if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_IORFW) ){
504 //fprintf(stderr, " CLRF/IORFW.\n");
506 pct2 = pic16_findNextInstruction(pc2->next);
508 if(pic16_pCodeSearchCondition(pct2, PCC_Z) > 0) {
509 pct2 = pic16_newpCode(POC_IORLW, pic16_newpCodeOpLit(0));
510 pct2->seq = pc2->seq;
511 PCI(pct2)->pcflow = PCFL(pcfl_used);
512 pic16_pCodeInsertAfter(pc1,pct2);
514 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
515 total_registers_saved++; // debugging stats.
517 } else if(PCI(pc1)->op == POC_MOVWF) {
519 pct2 = pic16_findNextInstruction(pc2->next);
521 if(PCI(pc2)->op == POC_MOVFW) {
523 fprintf(stderr, " MOVWF/MOVFW. instruction after MOVFW is:\n");
524 pct2->print(stderr,pct2);
527 if(PCI(pct2)->op == POC_MOVWF) {
542 reg2 = pic16_getRegFromInstruction(pct2);
543 //if(reg2 && !regUsedinRange(pc1,pc2,reg2) && (reg2->type != REG_SFR)) {
544 if(reg2 && !regUsedinRange(pc1,pc2,reg2)) {
546 if(pic16_pCodeSearchCondition(pct2, PCC_Z) < 1) {
547 pCode *pct3 = pic16_findNextInstruction(pct2->next);
548 pct2->seq = pc1->seq;
549 pic16_unlinkpCode(pct2);
550 pic16_pCodeInsertAfter(pic16_findPrevInstruction(pc1->prev),pct2);
552 #define usesW(x) ((x) && (isPCI(x)) && ( (PCI(x)->inCond & PCC_W) != 0))
555 ; // Remove2pcodes(pcfl_used, pc1, NULL, reg, can_free);
557 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
559 total_registers_saved++; // debugging stats.
562 //fprintf(stderr,"didn't optimize because Z bit is used\n");
566 fprintf(stderr, " couldn't optimize\n");
568 fprintf(stderr, " %s is used in range\n",reg2->name);
570 fprintf(stderr, " reg2 is NULL\n");
575 pct1 = pic16_findPrevInstruction(pc1->prev);
576 if(pct1 && (PCI(pct1)->pcflow == PCI(pc1)->pcflow)) {
578 if ( (PCI(pct1)->op == POC_MOVFW) &&
579 (PCI(pc2)->op == POC_MOVFW)) {
581 reg1 = pic16_getRegFromInstruction(pct1);
582 if(reg1 && !regUsedinRange(pc1,pc2,reg1)) {
584 fprintf(stderr, " MOVF/MOVFW. \n");
585 fprintf(stderr, " ...optimizing\n");
603 Or, if we're not deleting the register then the "To" is:
612 pct2 = pic16_newpCode(PCI(pc2)->op, PCI(pct1)->pcop);
613 pic16_pCodeInsertAfter(pc2, pct2);
614 PCI(pct2)->pcflow = PCFL(pcfl_used);
615 pct2->seq = pc2->seq;
618 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
620 /* If we're not freeing the register then that means (probably)
621 * the register is needed somewhere else.*/
622 pic16_unlinkpCode(pc1);
623 pic16_pCodeInsertAfter(pct2, pc1);
625 Remove2pcodes(pcfl_used, pc2, NULL, reg, can_free);
628 Remove2pcodes(pcfl_used, pct1, NULL, reg1, 0);
629 total_registers_saved++; // debugging stats.
632 } else if ( (PCI(pct1)->op == POC_MOVWF) &&
633 (PCI(pc2)->op == POC_MOVFW)) {
634 //fprintf(stderr,"movwf MOVWF/MOVFW\n");
635 if(optimize_level > 1 && can_free) {
636 pct2 = pic16_newpCode(POC_MOVFW, PCI(pc1)->pcop);
637 pic16_pCodeInsertAfter(pc2, pct2);
638 Remove2pcodes(pcfl_used, pc1, pc2, reg, 1);
639 total_registers_saved++; // debugging stats.
648 return (total_registers_saved != t);
651 /*-----------------------------------------------------------------*
652 * void pCodeRegOptimeRegUsage(pBlock *pb)
653 *-----------------------------------------------------------------*/
654 static void OptimizeRegUsage(set *fregs, int optimize_multi_uses, int optimize_level)
658 pCode *pc1=NULL, *pc2=NULL;
662 pCode *pcfl_used, *pcfl_assigned;
664 /* Step through the set by directly accessing the 'next' pointer.
665 * We could also step through by using the set API, but the
666 * the (debug) calls to print instructions affect the state
667 * of the set pointers */
672 if(reg->type == REG_SFR) {
673 // fprintf(stderr,"skipping SFR: %s\n",reg->name);
677 pcfl_used = setFirstItem(reg->reglives.usedpFlows);
678 pcfl_assigned = setFirstItem(reg->reglives.assignedpFlows);
680 used = elementsInSet(reg->reglives.usedpCodes);
681 // fprintf(stderr, "%s:%d register %s used %d times in pCode\n", __FILE__, __LINE__, reg->name, used);
685 * In this section, all registers that are used in only in two
686 * instructions are examined. If possible, they're optimized out.
690 fprintf (stderr, "OptimizeRegUsage: %s addr=0x%03x rIdx=0x%03x type=%d used=%d\n",
693 reg->rIdx, reg->type, used);
696 pc1 = setFirstItem(reg->reglives.usedpCodes);
697 pc2 = setNextItem(reg->reglives.usedpCodes);
699 if(pcfl_used && pcfl_assigned) {
702 expected case - the register has been assigned a value and is
706 //fprintf(stderr," used only twice\n");
707 if(pcfl_used->seq == pcfl_assigned->seq) {
709 //fprintf(stderr, " and used in same flow\n");
711 pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 1,optimize_level);
714 // fprintf(stderr, " and used in different flows\n");
718 } else if(pcfl_used) {
721 register has been used twice without ever being assigned */
722 //fprintf(stderr,"WARNING %s: reg %s used without being assigned\n",__FUNCTION__,reg->name);
725 // fprintf(stderr,"WARNING %s: reg %s assigned without being used\n",__FUNCTION__,reg->name);
726 Remove2pcodes(pcfl_assigned, pc1, pc2, reg, 1);
727 total_registers_saved++; // debugging stats.
731 /* register has been used either once, or more than twice */
733 if(used && !pcfl_used && pcfl_assigned) {
736 // fprintf(stderr,"WARNING %s: reg %s assigned without being used\n",__FUNCTION__,reg->name);
738 pc = setFirstItem(reg->reglives.usedpCodes);
741 pcfl_assigned = PCODE(PCI(pc)->pcflow);
742 Remove1pcode(pc, reg);
744 deleteSetItem (&(PCFL(pcfl_assigned)->registers), reg);
746 deleteSetItem (&(reg->reglives.usedpCodes),pc);
749 pc = setNextItem(reg->reglives.usedpCodes);
756 total_registers_saved++; // debugging stats.
757 } else if( (used > 2) && optimize_multi_uses) {
763 pCodeFlow *pcfl1=NULL, *pcfl2=NULL;
765 /* examine the number of times this register is used */
768 rset1 = reg->reglives.usedpCodes;
769 while(rset1 && searching) {
774 if(pc1 && isPCI(pc1) && ( (pcfl1 = PCI(pc1)->pcflow) != NULL) ) {
776 //while(rset2 && searching) {
780 if(pc2 && isPCI(pc2) && ( (pcfl2 = PCI(pc2)->pcflow) != NULL) ) {
783 if(pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 0,optimize_level))
788 //rset2 = rset2->next;
800 /*-----------------------------------------------------------------*
801 * void pic16_pCodeRegOptimeRegUsage(pBlock *pb)
802 *-----------------------------------------------------------------*/
803 void pic16_pCodeRegOptimizeRegUsage(int level)
808 int t = total_registers_saved;
810 if(!register_optimization)
816 saved = total_registers_saved;
818 /* Identify registers used in one flow sequence */
819 OptimizeRegUsage(pic16_dynAllocRegs,level, (OPT_PASSES-passes));
820 OptimizeRegUsage(pic16_dynStackRegs,level, (OPT_PASSES-passes));
821 OptimizeRegUsage(pic16_dynDirectRegs,0, (OPT_PASSES-passes));
823 if((total_registers_saved != saved)
824 && (pic16_pcode_verbose))
825 fprintf(stderr, " *** pass %d, Saved %d registers, total saved %d ***\n",
826 (1+OPT_PASSES-passes),total_registers_saved-saved,total_registers_saved);
830 } while( passes && ((total_registers_saved != saved) || (passes==OPT_PASSES-1)) );
832 if(total_registers_saved == t)
834 if(pic16_debug_verbose)
835 fprintf(stderr, "No registers saved on this pass\n");
839 fprintf(stderr,"dynamically allocated regs:\n");
840 dbg_regusage(pic16_dynAllocRegs);
841 fprintf(stderr,"stack regs:\n");
842 dbg_regusage(pic16_dynStackRegs);
843 fprintf(stderr,"direct regs:\n");
844 dbg_regusage(pic16_dynDirectRegs);
849 /*-----------------------------------------------------------------*
850 * void RegsUnMapLiveRanges(set *regset)
852 *-----------------------------------------------------------------*/
853 static void RegsSetUnMapLiveRanges(set *regset)
859 regset = regset->next;
862 deleteSet(®->reglives.usedpCodes);
863 deleteSet(®->reglives.usedpFlows);
864 deleteSet(®->reglives.assignedpFlows);
870 void pic16_RegsUnMapLiveRanges(void)
873 RegsSetUnMapLiveRanges(pic16_dynAllocRegs);
874 RegsSetUnMapLiveRanges(pic16_dynStackRegs);
875 RegsSetUnMapLiveRanges(pic16_dynDirectRegs);
876 RegsSetUnMapLiveRanges(pic16_dynProcessorRegs);
877 RegsSetUnMapLiveRanges(pic16_dynDirectBitRegs);
878 RegsSetUnMapLiveRanges(pic16_dynInternalRegs);