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 dbg_dumpregusage(void);
40 extern pCode * findPrevInstruction(pCode *pci);
41 extern pBranch * pBranchAppend(pBranch *h, pBranch *n);
42 void unlinkpCode(pCode *pc);
43 extern int pCodeSearchCondition(pCode *pc, unsigned int cond, int contIfSkip);
44 char *pCode2str(char *str, int size, pCode *pc);
45 void SAFE_snprintf(char **str, size_t *size, const char *format, ...);
46 int total_registers_saved=0;
47 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 *-----------------------------------------------------------------*/
69 void dbg_regusage(set *fregs)
76 for (reg = setFirstItem(fregs) ; reg ;
77 reg = setNextItem(fregs)) {
79 if(elementsInSet(reg->reglives.usedpCodes)) {
81 fprintf (stderr, "%s addr=0x%03x rIdx=0x%03x",
86 pcfl = setFirstItem(reg->reglives.usedpFlows);
88 fprintf(stderr, "\n used in seq");
91 fprintf(stderr," 0x%03x",pcfl->seq);
92 pcfl = setNextItem(reg->reglives.usedpFlows);
95 pcfl = setFirstItem(reg->reglives.assignedpFlows);
97 fprintf(stderr, "\n assigned in seq");
100 fprintf(stderr," 0x%03x",pcfl->seq);
101 pcfl = setNextItem(reg->reglives.assignedpFlows);
104 pc = setFirstItem(reg->reglives.usedpCodes);
106 fprintf(stderr, "\n used in instructions ");
109 pcfl = PCODE(PCI(pc)->pcflow);
111 fprintf(stderr," 0x%03x:",pcfl->seq);
112 fprintf(stderr,"0x%03x",pc->seq);
114 pc = setNextItem(reg->reglives.usedpCodes);
117 fprintf(stderr, "\n");
122 /*-----------------------------------------------------------------*
124 *-----------------------------------------------------------------*/
125 void dbg_dumpregusage(void)
128 fprintf(stderr,"*** Register Usage ***\n");
129 fprintf(stderr,"InternalRegs:\n");
130 dbg_regusage(dynInternalRegs);
131 fprintf(stderr,"AllocRegs:\n");
132 dbg_regusage(dynAllocRegs);
133 fprintf(stderr,"StackRegs:\n");
134 dbg_regusage(dynStackRegs);
135 fprintf(stderr,"DirectRegs:\n");
136 dbg_regusage(dynDirectRegs);
137 fprintf(stderr,"DirectBitRegs:\n");
138 dbg_regusage(dynDirectBitRegs);
139 fprintf(stderr,"ProcessorRegs:\n");
140 dbg_regusage(dynProcessorRegs);
145 /*-----------------------------------------------------------------*
146 * void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
147 *-----------------------------------------------------------------*/
148 void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
160 pc = findNextInstruction(pcfl->pc.next);
162 while(isPCinFlow(pc,PCODE(pcfl))) {
165 reg = getRegFromInstruction(pc);
169 fprintf(stderr, "flow seq %d, inst seq %d %s ",PCODE(pcfl)->seq,pc->seq,reg->name);
170 fprintf(stderr, "addr = 0x%03x, type = %d rIdx=0x%03x\n",
171 reg->address,reg->type,reg->rIdx);
174 addSetIfnotP(& (PCFL(pcfl)->registers), reg);
176 if((PCC_REGISTER | PCC_LITERAL) & PCI(pc)->inCond)
177 addSetIfnotP(& (reg->reglives.usedpFlows), pcfl);
179 if(PCC_REGISTER & PCI(pc)->outCond)
180 addSetIfnotP(& (reg->reglives.assignedpFlows), pcfl);
182 addSetIfnotP(& (reg->reglives.usedpCodes), pc);
187 pc = findNextInstruction(pc->next);
193 /*-----------------------------------------------------------------*
194 * void pCodeRegMapLiveRanges(pBlock *pb)
195 *-----------------------------------------------------------------*/
196 void pCodeRegMapLiveRanges(pBlock *pb)
200 for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
202 pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
204 if(!isPCFL(pcflow)) {
205 fprintf(stderr, "pCodeRegMapLiveRanges - pcflow is not a flow object ");
208 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
212 for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
214 pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
216 regs *r = setFirstItem(PCFL(pcflow)->registers);
217 fprintf(stderr,"flow seq %d\n", pcflow->seq);
220 fprintf(stderr, " %s\n",r->name);
221 r = setNextItem(PCFL(pcflow)->registers);
228 // dbg_dumpregusage();
233 /*-----------------------------------------------------------------*
235 *-----------------------------------------------------------------*/
236 static void Remove1pcode(pCode *pc, regs *reg, int debug_code)
244 deleteSetItem (&(reg->reglives.usedpCodes),pc);
247 pcn = findNextInstruction(pc->next);
250 PCI(pcn)->label = pBranchAppend(PCI(pcn)->label,PCI(pc)->label);
255 pcn = findNextInstruction(pc->next);
258 if(PCI(pcn)->cline) {
259 //fprintf(stderr, "source line has been optimized completely out\n");
260 //pc->print(stderr,pc);
262 PCI(pcn)->cline = PCI(pc)->cline;
270 Debug stuff. Comment out the instruction we're about to delete.
276 char *pbuff,**ppbuff;
280 SAFE_snprintf(ppbuff,&size, ";%d", debug_code);
281 pCode2str(*ppbuff, size, pc);
282 pCodeInsertBefore(pc, newpCodeCharP(buff1));
283 //fprintf(stderr,"removing instruction:\n%s\n",buff1);
290 /*-----------------------------------------------------------------*
291 * void RemoveRegsFromSet(set *regset)
293 *-----------------------------------------------------------------*/
294 void RemoveRegsFromSet(set *regset)
301 regset = regset->next;
303 used = elementsInSet(reg->reglives.usedpCodes);
307 //fprintf(stderr," reg %s isfree=%d, wasused=%d\n",reg->name,reg->isFree,reg->wasUsed);
309 //fprintf(stderr," getting rid of reg %s\n",reg->name);
316 pc = setFirstItem(reg->reglives.usedpCodes);
318 if(reg->type == REG_SFR || reg->type == REG_STK || reg->isPublic || reg->isExtern) {
319 //fprintf(stderr, "not removing SFR reg %s even though used only once\n",reg->name);
326 pCode *pcn = findNextInstruction(pc->next);
328 if(pcn && PCI(pcn)->label) {
329 //fprintf(stderr,"can't delete instruction with label...\n");
330 //pc->print(stderr,pc);
333 /* Move the label to the next instruction */
335 PCI(pcn)->label = PCI(pc)->label;
340 regs *r = getRegFromInstruction(pc);
341 fprintf(stderr, "WARNING, a skip instruction is being optimized out\n");
342 pc->print(stderr,pc);
343 fprintf(stderr,"reg %s, type =%d\n",r->name, r->type);
345 //fprintf(stderr," removing reg %s because it is used only once\n",reg->name);
346 Remove1pcode(pc, reg, 1);
349 deleteSetItem (&(reg->reglives.usedpCodes),pc);
353 total_registers_saved++; // debugging stats.
360 /*-----------------------------------------------------------------*
361 * void RemoveUnusedRegisters(void)
363 *-----------------------------------------------------------------*/
364 void RemoveUnusedRegisters(void)
366 /* First, get rid of registers that are used only one time */
368 //RemoveRegsFromSet(dynInternalRegs);
369 RemoveRegsFromSet(dynAllocRegs);
370 RemoveRegsFromSet(dynStackRegs);
372 don't do DirectRegs yet - there's a problem with arrays
373 RemoveRegsFromSet(dynDirectRegs);
375 RemoveRegsFromSet(dynDirectBitRegs);
377 if(total_registers_saved) DFPRINTF((stderr, " *** Saved %d registers ***\n", total_registers_saved));
381 /*-----------------------------------------------------------------*
383 *-----------------------------------------------------------------*/
384 static void Remove2pcodes(pCode *pcflow, pCode *pc1, pCode *pc2, regs *reg, int can_free)
386 static int debug_code=99;
390 fprintf (stderr, "%s:%d(%s): %d (reg:%s)\n", __FILE__, __LINE__, __FUNCTION__, debug_code, reg ? reg->name : "???");
391 printpCode (stderr, pc1);
392 printpCode (stderr, pc2);
395 //fprintf(stderr,"%s\n",__FUNCTION__);
397 Remove1pcode(pc1, reg, debug_code++);
400 Remove1pcode(pc2, reg, debug_code++);
401 deleteSetItem (&(PCFL(pcflow)->registers), reg);
410 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
413 /*-----------------------------------------------------------------*
415 *-----------------------------------------------------------------*/
416 int regUsedinRange(pCode *pc1, pCode *pc2, regs *reg)
422 testreg = getRegFromInstruction(pc1);
423 if(testreg && (testreg->rIdx == reg->rIdx)) {
427 fprintf(stderr, "warning, regUsedinRange searched through too many pcodes\n");
431 pc1 = findNextInstruction(pc1->next);
433 } while (pc1 && (pc1 != pc2)) ;
438 int regIsSpecial (regs *reg, int mayBeGlobal)
442 if (reg->type == REG_SFR || reg->type == REG_STK || (!mayBeGlobal && (reg->isPublic || reg->isExtern))) return 1;
447 /*-----------------------------------------------------------------*
448 * void pCodeOptime2pCodes(pCode *pc1, pCode *pc2)
450 * ADHOC pattern checking
451 * Now look for specific sequences that are easy to optimize.
452 * Many of these sequences are characteristic of the compiler
453 * (i.e. it'd probably be a waste of time to apply these adhoc
454 * checks to hand written assembly.)
457 *-----------------------------------------------------------------*/
458 int pCodeOptime2pCodes(pCode *pc1, pCode *pc2, pCode *pcfl_used, regs *reg, int can_free, int optimize_level)
463 int t = total_registers_saved;
465 if(pc2->seq < pc1->seq) {
471 //fprintf(stderr,"pCodeOptime2pCodes\n");
472 //pc1->print(stderr,pc1);
473 //pc2->print(stderr,pc2);
475 if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_MOVFW) ){
485 can be replaced with (only if following instructions are not going to use W and reg is not used again later)
490 DFPRINTF((stderr, " optimising CLRF reg ... MOVF reg,W to ... MOVLW 0\n"));
491 pct2 = findNextInstruction(pc2->next);
493 if(pct2 && PCI(pct2)->op == POC_MOVWF) {
494 wSaved = wUsed = 1; /* Maybe able to replace with clrf pc2->next->reg. */
496 wUsed = pCodeSearchCondition(pct2,PCC_W,1) > 0;
498 regUsed = regUsedinRange(pct2,0,reg);
499 if ((regUsed&&wUsed) || (pCodeSearchCondition(pct2,PCC_Z,0) > 1)) {
500 /* Do not optimise as exisiting code is required. */
504 newpc = newpCode(POC_CLRF, PCI(pc1)->pcop);
505 } else if(wSaved && !wUsed) {
506 newpc = newpCode(POC_CLRF, PCI(pct2)->pcop);
507 pct2->destruct(pct2);
509 newpc = newpCode(POC_MOVLW, newpCodeOpLit(0));
512 pCodeInsertAfter(pc2, newpc);
513 PCI(newpc)->pcflow = PCFL(pcfl_used);
514 newpc->seq = pc2->seq;
516 //fprintf (stderr, "%s:%d(%s): Remove2pcodes (CLRF reg, ..., MOVF reg,W)\n", __FILE__, __LINE__, __FUNCTION__);
517 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
518 total_registers_saved++; // debugging stats.
520 } else if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_IORFW) ){
521 DFPRINTF((stderr, " optimising CLRF/IORFW\n"));
523 pct2 = findNextInstruction(pc2->next);
525 if(pCodeSearchCondition(pct2, PCC_Z,0) > 0) {
526 pct2 = newpCode(POC_IORLW, newpCodeOpLit(0));
527 pct2->seq = pc2->seq;
528 PCI(pct2)->pcflow = PCFL(pcfl_used);
529 pCodeInsertAfter(pc1,pct2);
531 //fprintf (stderr, "%s:%d(%s): Remove2pcodes (CLRF/IORFW)\n", __FILE__, __LINE__, __FUNCTION__);
532 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
533 total_registers_saved++; // debugging stats.
535 } else if(PCI(pc1)->op == POC_MOVWF) {
536 // Optimising MOVWF reg ...
538 pct2 = findNextInstruction(pc2->next);
540 if(PCI(pc2)->op == POC_MOVFW) {
541 // Optimising MOVWF reg ... MOVF reg,W
543 if(PCI(pct2)->op == POC_MOVWF) {
552 To: ( as long as 'stuff' does not use reg2 or if following instructions do not use W or reg is not used later)
558 reg2 = getRegFromInstruction(pct2);
559 /* Check reg2 is not used for something else before it is loaded with reg */
560 if (reg2 && !regIsSpecial (reg2, 1) && !regUsedinRange(pc1,pc2,reg2)) {
561 pCode *pct3 = findNextInstruction(pct2->next);
562 /* Check following instructions are not relying on the use of W or the Z flag condiction */
563 if ((pCodeSearchCondition(pct3,PCC_Z,0) < 1) || (pCodeSearchCondition(pct3,PCC_W,0) < 1)) {
564 DFPRINTF((stderr, " optimising MOVF reg ... MOVF reg,W MOVWF reg2 to MOVWF reg2 ...\n"));
565 pct2->seq = pc1->seq;
567 pCodeInsertBefore(pc1,pct2);
568 if(regUsedinRange(pct2,0,reg))
570 //fprintf (stderr, "%s:%d(%s): Remove2pcodes IF (MOVWF reg, ..., MOVW reg,W MOVWF reg2)\n", __FILE__, __LINE__, __FUNCTION__);
571 Remove2pcodes(pcfl_used, pc2, NULL, reg, can_free);
573 //fprintf (stderr, "%s:%d(%s): Remove2pcodes ELSE (MOVWF reg, ..., MOVW reg,W MOVWF reg2)\n", __FILE__, __LINE__, __FUNCTION__);
574 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
576 total_registers_saved++; // debugging stats.
583 pct1 = findPrevInstruction(pc1->prev);
584 if(pct1 && (PCI(pct1)->pcflow == PCI(pc1)->pcflow)) {
586 if ( (PCI(pct1)->op == POC_MOVFW) &&
587 (PCI(pc2)->op == POC_MOVFW)) {
589 reg1 = getRegFromInstruction(pct1);
590 if(reg1 && !regIsSpecial (reg1, 0) && !regUsedinRange(pc1,pc2,reg1)) {
591 DFPRINTF((stderr, " optimising MOVF reg1,W MOVWF reg ... MOVF reg,W\n"));
607 Or, if we're not deleting the register then the "To" is:
614 pct2 = newpCode(PCI(pc2)->op, PCI(pct1)->pcop);
615 pCodeInsertAfter(pc2, pct2);
616 PCI(pct2)->pcflow = PCFL(pcfl_used);
617 pct2->seq = pc2->seq;
620 //fprintf (stderr, "%s:%d(%s): Remove2pcodes CANFREE (MOVF reg1,W; MOVWF reg2; MOVF reg2,W)\n", __FILE__, __LINE__, __FUNCTION__);
621 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
623 /* If we're not freeing the register then that means (probably)
624 * the register is needed somewhere else.*/
626 pCodeInsertAfter(pct2, pc1);
628 //fprintf (stderr, "%s:%d(%s): Remove2pcodes ELSE (MOVF reg1,W; MOVWF reg2; MOVF reg2,W)\n", __FILE__, __LINE__, __FUNCTION__);
629 Remove2pcodes(pcfl_used, pc2, NULL, reg, can_free);
632 //fprintf (stderr, "%s:%d(%s): Remove2pcodes ALWAYS (MOVF reg1,W; MOVWF reg2; MOVF reg2,W)\n", __FILE__, __LINE__, __FUNCTION__);
633 Remove2pcodes(pcfl_used, pct1, NULL, reg1, 0);
634 total_registers_saved++; // debugging stats.
641 return (total_registers_saved != t);
644 /*-----------------------------------------------------------------*
645 * void pCodeRegOptimeRegUsage(pBlock *pb)
646 *-----------------------------------------------------------------*/
647 void OptimizeRegUsage(set *fregs, int optimize_multi_uses, int optimize_level)
651 pCode *pc1=NULL, *pc2=NULL;
655 pCode *pcfl_used, *pcfl_assigned;
657 /* Step through the set by directly accessing the 'next' pointer.
658 * We could also step through by using the set API, but the
659 * the (debug) calls to print instructions affect the state
660 * of the set pointers */
665 if (strcmp(reg->name,"_SubState")==0)
666 fprintf(stderr,"Reg: %s\n",reg->name);
669 if(reg->type == REG_SFR || reg->type == REG_STK || reg->isPublic || reg->isExtern|| reg->isFixed) {
670 //fprintf(stderr,"skipping SFR: %s\n",reg->name);
674 pcfl_used = setFirstItem(reg->reglives.usedpFlows);
675 pcfl_assigned = setFirstItem(reg->reglives.assignedpFlows);
677 used = elementsInSet(reg->reglives.usedpCodes);
680 In this section, all registers that are used in only in two
681 instructions are examined. If possible, they're optimized out.
685 fprintf (stderr, "OptimizeRegUsage: %s addr=0x%03x rIdx=0x%03x type=%d used=%d\n",
688 reg->rIdx, reg->type, used);
690 pc1 = setFirstItem(reg->reglives.usedpCodes);
691 pc2 = setNextItem(reg->reglives.usedpCodes);
693 if(pcfl_used && pcfl_assigned) {
695 expected case - the register has been assigned a value and is
699 //fprintf(stderr," used only twice\n");
700 if(pcfl_used->seq == pcfl_assigned->seq) {
702 //fprintf(stderr, " and used in same flow\n");
704 pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 1,optimize_level);
707 // fprintf(stderr, " and used in different flows\n");
711 } else if(pcfl_used) {
713 /* register has been used twice without ever being assigned */
714 fprintf(stderr,"WARNING %s: reg %s used without being assigned\n",__FUNCTION__,reg->name);
717 //fprintf(stderr,"WARNING %s.1: reg %s assigned without being used\n",__FUNCTION__,reg->name);
718 Remove2pcodes(pcfl_assigned, pc1, pc2, reg, 1);
719 total_registers_saved++; // debugging stats.
723 /* register has been used either once, or more than twice */
725 if(used && !pcfl_used && pcfl_assigned) {
728 //fprintf(stderr,"WARNING %s.2: reg %s assigned without being used\n",__FUNCTION__,reg->name);
730 pc = setFirstItem(reg->reglives.usedpCodes);
733 pcfl_assigned = PCODE(PCI(pc)->pcflow);
734 Remove1pcode(pc, reg,2);
736 deleteSetItem (&(PCFL(pcfl_assigned)->registers), reg);
738 deleteSetItem (&(reg->reglives.usedpCodes),pc);
741 pc = setNextItem(reg->reglives.usedpCodes);
748 total_registers_saved++; // debugging stats.
749 } else if( (used > 2) && optimize_multi_uses) {
755 pCodeFlow *pcfl1=NULL, *pcfl2=NULL;
757 /* examine the number of times this register is used */
760 rset1 = reg->reglives.usedpCodes;
761 while(rset1 && searching) {
766 if(pc1 && isPCI(pc1) && ( (pcfl1 = PCI(pc1)->pcflow) != NULL) ) {
768 //while(rset2 && searching) {
772 if(pc2 && isPCI(pc2) && ( (pcfl2 = PCI(pc2)->pcflow) != NULL) ) {
775 if(pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 0,optimize_level))
780 //rset2 = rset2->next;
791 /*-----------------------------------------------------------------*
792 * void pCodeRegOptimeRegUsage(pBlock *pb)
793 *-----------------------------------------------------------------*/
794 void pCodeRegOptimizeRegUsage(int level)
799 int t = total_registers_saved;
801 if(!register_optimization)
807 saved = total_registers_saved;
809 /* Identify registers used in one flow sequence */
810 OptimizeRegUsage(dynAllocRegs,level, (OPT_PASSES-passes));
811 OptimizeRegUsage(dynStackRegs,level, (OPT_PASSES-passes));
812 OptimizeRegUsage(dynDirectRegs,0, (OPT_PASSES-passes));
814 if(total_registers_saved != saved)
815 DFPRINTF((stderr, " *** pass %d, Saved %d registers, total saved %d ***\n",
816 (1+OPT_PASSES-passes),total_registers_saved-saved,total_registers_saved));
820 } while( passes && ((total_registers_saved != saved) || (passes==OPT_PASSES-1)) );
822 if(total_registers_saved == t)
823 DFPRINTF((stderr, "No registers saved on this pass\n"));
827 fprintf(stderr,"dynamically allocated regs:\n");
828 dbg_regusage(dynAllocRegs);
829 fprintf(stderr,"stack regs:\n");
830 dbg_regusage(dynStackRegs);
831 fprintf(stderr,"direct regs:\n");
832 dbg_regusage(dynDirectRegs);
837 /*-----------------------------------------------------------------*
838 * void RegsUnMapLiveRanges(set *regset)
840 *-----------------------------------------------------------------*/
841 void RegsSetUnMapLiveRanges(set *regset)
847 regset = regset->next;
850 deleteSet(®->reglives.usedpCodes);
851 deleteSet(®->reglives.usedpFlows);
852 deleteSet(®->reglives.assignedpFlows);
858 void RegsUnMapLiveRanges(void)
861 RegsSetUnMapLiveRanges(dynAllocRegs);
862 RegsSetUnMapLiveRanges(dynStackRegs);
863 RegsSetUnMapLiveRanges(dynDirectRegs);
864 RegsSetUnMapLiveRanges(dynProcessorRegs);
865 RegsSetUnMapLiveRanges(dynDirectBitRegs);
866 RegsSetUnMapLiveRanges(dynInternalRegs);