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"
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);
44 extern int pCodeSearchCondition(pCode *pc, unsigned int cond, int contIfSkip);
45 char *pCode2str(char *str, int size, pCode *pc);
46 void SAFE_snprintf(char **str, size_t *size, const char *format, ...);
47 //static int sameRegs (const regs *reg1, const regs *reg2);
49 int total_registers_saved=0;
50 int register_optimization=1;
52 /*-----------------------------------------------------------------*
53 * void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
54 *-----------------------------------------------------------------*/
56 void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
59 if(!reg || ! pcfl || !isPCFL(pcflow))
63 pcfl->registers = newSet();
69 /*-----------------------------------------------------------------*
71 *-----------------------------------------------------------------*/
72 void dbg_regusage(set *fregs)
79 for (reg = setFirstItem(fregs) ; reg ;
80 reg = setNextItem(fregs)) {
82 if(elementsInSet(reg->reglives.usedpCodes)) {
84 fprintf (stderr, "%s addr=0x%03x rIdx=0x%03x",
89 pcfl = setFirstItem(reg->reglives.usedpFlows);
91 fprintf(stderr, "\n used in seq");
94 fprintf(stderr," 0x%03x",pcfl->seq);
95 pcfl = setNextItem(reg->reglives.usedpFlows);
98 pcfl = setFirstItem(reg->reglives.assignedpFlows);
100 fprintf(stderr, "\n assigned in seq");
103 fprintf(stderr," 0x%03x",pcfl->seq);
104 pcfl = setNextItem(reg->reglives.assignedpFlows);
107 pc = setFirstItem(reg->reglives.usedpCodes);
109 fprintf(stderr, "\n used in instructions ");
112 pcfl = PCODE(PCI(pc)->pcflow);
114 fprintf(stderr," 0x%03x:",pcfl->seq);
115 fprintf(stderr,"0x%03x",pc->seq);
117 pc = setNextItem(reg->reglives.usedpCodes);
120 fprintf(stderr, "\n");
125 /*-----------------------------------------------------------------*
127 *-----------------------------------------------------------------*/
128 void dbg_dumpregusage(void)
131 fprintf(stderr,"*** Register Usage ***\n");
132 fprintf(stderr,"InternalRegs:\n");
133 dbg_regusage(dynInternalRegs);
134 fprintf(stderr,"AllocRegs:\n");
135 dbg_regusage(dynAllocRegs);
136 fprintf(stderr,"StackRegs:\n");
137 dbg_regusage(dynStackRegs);
138 fprintf(stderr,"DirectRegs:\n");
139 dbg_regusage(dynDirectRegs);
140 fprintf(stderr,"DirectBitRegs:\n");
141 dbg_regusage(dynDirectBitRegs);
142 fprintf(stderr,"ProcessorRegs:\n");
143 dbg_regusage(dynProcessorRegs);
148 /*-----------------------------------------------------------------*
149 * void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
150 *-----------------------------------------------------------------*/
151 void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
162 pc = findNextInstruction(pcfl->pc.next);
164 while(pc && !isPCFL(pc)) {
165 while (pc && !isPCI(pc) && !isPCFL(pc))
169 if (!pc || isPCFL(pc)) continue;
172 reg = getRegFromInstruction(pc);
174 pc->print(stderr, pc);
175 fprintf( stderr, "--> reg %p (%s,%u), inCond/outCond: %x/%x\n",
176 reg, reg ? reg->name : "(null)", reg ? reg->rIdx : -1,
177 PCI(pc)->inCond, PCI(pc)->outCond );
181 fprintf(stderr, "flow seq %d, inst seq %d %s ",PCODE(pcfl)->seq,pc->seq,reg->name);
182 fprintf(stderr, "addr = 0x%03x, type = %d rIdx=0x%03x\n",
183 reg->address,reg->type,reg->rIdx);
186 addSetIfnotP(& (PCFL(pcfl)->registers), reg);
188 if(PCC_REGISTER & PCI(pc)->inCond)
189 addSetIfnotP(& (reg->reglives.usedpFlows), pcfl);
191 if(PCC_REGISTER & PCI(pc)->outCond)
192 addSetIfnotP(& (reg->reglives.assignedpFlows), pcfl);
194 addSetIfnotP(& (reg->reglives.usedpCodes), pc);
199 //pc = findNextInstruction(pc->next);
206 /*-----------------------------------------------------------------*
207 * void pCodeRegMapLiveRanges(pBlock *pb)
208 *-----------------------------------------------------------------*/
209 void pCodeRegMapLiveRanges(pBlock *pb)
213 for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
215 pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
217 if(!isPCFL(pcflow)) {
218 fprintf(stderr, "pCodeRegMapLiveRanges - pcflow is not a flow object ");
221 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
225 for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
227 pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
229 regs *r = setFirstItem(PCFL(pcflow)->registers);
230 fprintf(stderr,"flow seq %d\n", pcflow->seq);
233 fprintf(stderr, " %s\n",r->name);
234 r = setNextItem(PCFL(pcflow)->registers);
241 // dbg_dumpregusage();
246 /*-----------------------------------------------------------------*
248 *-----------------------------------------------------------------*/
249 static void Remove1pcode(pCode *pc, regs *reg, int debug_code)
257 deleteSetItem (&(reg->reglives.usedpCodes),pc);
260 pcn = findNextInstruction(pc->next);
263 PCI(pcn)->label = pBranchAppend(PCI(pcn)->label,PCI(pc)->label);
268 pcn = findNextInstruction(pc->next);
271 if(PCI(pcn)->cline) {
272 //fprintf(stderr, "source line has been optimized completely out\n");
273 //pc->print(stderr,pc);
275 PCI(pcn)->cline = PCI(pc)->cline;
283 Debug stuff. Comment out the instruction we're about to delete.
289 char *pbuff,**ppbuff;
293 SAFE_snprintf(ppbuff,&size, ";%d", debug_code);
294 pCode2str(*ppbuff, size, pc);
295 pCodeInsertBefore(pc, newpCodeCharP(buff1));
296 //fprintf(stderr,"removing instruction:\n%s\n",buff1);
303 /*-----------------------------------------------------------------*
304 * void RemoveRegsFromSet(set *regset)
306 *-----------------------------------------------------------------*/
307 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," getting rid of reg %s\n",reg->name);
329 pc = setFirstItem(reg->reglives.usedpCodes);
331 if(reg->type == REG_SFR || reg->type == REG_STK || reg->isPublic || reg->isExtern) {
332 //fprintf(stderr, "not removing SFR reg %s even though used only once\n",reg->name);
339 pCode *pcn = 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 = 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," removing reg %s because it is used only once\n",reg->name);
359 Remove1pcode(pc, reg, 1);
362 deleteSetItem (&(reg->reglives.usedpCodes),pc);
366 total_registers_saved++; // debugging stats.
374 void RegsUnMapLiveRanges(void);
375 extern pFile *the_pFile;
376 void pic14_ReMapLiveRanges(void)
379 if (!the_pFile) return;
380 RegsUnMapLiveRanges();
381 for (pb = the_pFile->pbHead; pb; pb = pb->next)
384 pCode *pc = findNextpCode(pb->pcHead, PC_FLOW);
386 pc->print( stderr, pc );
388 fprintf( stderr, "unnamed pBlock\n");
390 pc = findNextInstruction(pb->pcHead);
392 pc->print( stderr, pc );
393 pc = findNextInstruction(pc->next);;
396 pCodeRegMapLiveRanges(pb);
400 /*-----------------------------------------------------------------*
401 * void RemoveUnusedRegisters(void)
403 *-----------------------------------------------------------------*/
404 void RemoveUnusedRegisters(void)
406 /* First, get rid of registers that are used only one time */
407 pic14_ReMapLiveRanges();
409 //RemoveRegsFromSet(dynInternalRegs);
410 RemoveRegsFromSet(dynAllocRegs);
411 RemoveRegsFromSet(dynStackRegs);
413 don't do DirectRegs yet - there's a problem with arrays
414 RemoveRegsFromSet(dynDirectRegs);
416 RemoveRegsFromSet(dynDirectBitRegs);
418 if(total_registers_saved) DFPRINTF((stderr, " *** Saved %d registers ***\n", total_registers_saved));
422 /*-----------------------------------------------------------------*
424 *-----------------------------------------------------------------*/
425 static void Remove2pcodes(pCode *pcflow, pCode *pc1, pCode *pc2, regs *reg, int can_free)
427 static int debug_code=99;
431 fprintf (stderr, "%s:%d(%s): %d (reg:%s)\n", __FILE__, __LINE__, __FUNCTION__, debug_code, reg ? reg->name : "???");
432 printpCode (stderr, pc1);
433 printpCode (stderr, pc2);
436 //fprintf(stderr,"%s\n",__FUNCTION__);
438 Remove1pcode(pc1, reg, debug_code++);
441 Remove1pcode(pc2, reg, debug_code++);
442 deleteSetItem (&(PCFL(pcflow)->registers), reg);
451 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
454 /*-----------------------------------------------------------------*
456 *-----------------------------------------------------------------*/
457 int regUsedinRange(pCode *pc1, pCode *pc2, regs *reg)
463 testreg = getRegFromInstruction(pc1);
464 if(testreg && (testreg->rIdx == reg->rIdx)) {
468 fprintf(stderr, "warning, regUsedinRange searched through too many pcodes\n");
472 pc1 = findNextInstruction(pc1->next);
474 } while (pc1 && (pc1 != pc2)) ;
479 int regIsSpecial (regs *reg, int mayBeGlobal)
483 if (reg->type == REG_SFR || reg->type == REG_STK || (!mayBeGlobal && (reg->isPublic || reg->isExtern))) return 1;
489 static int regIsLocal (regs *reg)
492 /* temporaries are local */
493 if (reg->type == REG_TMP) return 1;
494 /* registers named r0x... are local */
495 if (reg->name && !strncmp(reg->name,"r0x", 3))
497 //fprintf (stderr, "reg %s is not marked REG_TMP...\n", reg->name);
505 /*-----------------------------------------------------------------*
506 * void pCodeOptime2pCodes(pCode *pc1, pCode *pc2)
508 * ADHOC pattern checking
509 * Now look for specific sequences that are easy to optimize.
510 * Many of these sequences are characteristic of the compiler
511 * (i.e. it'd probably be a waste of time to apply these adhoc
512 * checks to hand written assembly.)
515 *-----------------------------------------------------------------*/
516 int pCodeOptime2pCodes(pCode *pc1, pCode *pc2, pCode *pcfl_used, regs *reg, int can_free, int optimize_level)
521 int t = total_registers_saved;
523 if (!isPCI(pc1) || !isPCI(pc2)) return 0;
524 if (PCI(pc1)->pcflow != PCI(pc2)->pcflow) return 0;
526 if (pc2->seq < pc1->seq) {
532 /* disable this optimization for now -- it's buggy */
533 if (pic14_options.disable_df) return 0;
535 //fprintf(stderr,"pCodeOptime2pCodes\n");
536 //pc1->print(stderr,pc1);
537 //pc2->print(stderr,pc2);
539 if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_MOVFW) ){
543 * MOVWF does not touch Z
544 * MOVLW does not touch Z
552 can be replaced with (only if following instructions are not going to use W and reg is not used again later)
557 DFPRINTF((stderr, " optimising CLRF reg ... MOVF reg,W to ... MOVLW 0\n"));
558 pct2 = findNextInstruction(pc2->next);
559 if (pCodeSearchCondition(pct2, PCC_Z, 0) == -1) {
560 /* Z is definitely overwritten before use */
561 newpc = newpCode(POC_MOVLW, newpCodeOpLit(0));
563 pCodeInsertAfter(pc2, newpc);
564 PCI(newpc)->pcflow = PCFL(pcfl_used);
565 newpc->seq = pc2->seq;
567 //fprintf (stderr, "%s:%d(%s): Remove2pcodes (CLRF reg, ..., MOVF reg,W)\n", __FILE__, __LINE__, __FUNCTION__);
568 //Remove2pcodes(pcfl_used, pc2, NULL, reg, 0);
570 //total_registers_saved++; // debugging stats.
572 } else if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_IORFW) ){
573 DFPRINTF((stderr, " optimising CLRF/IORFW\n"));
575 pct2 = findNextInstruction(pc2->next);
577 /* We must ensure that Z is destroyed before being read---IORLW must be performed unless this is proven. */
578 if (pCodeSearchCondition(pct2, PCC_Z, 0) != -1) {
579 pct2 = newpCode(POC_IORLW, newpCodeOpLit(0));
580 pct2->seq = pc2->seq;
581 PCI(pct2)->pcflow = PCFL(pcfl_used);
582 pCodeInsertAfter(pc1,pct2);
584 //fprintf (stderr, "%s:%d(%s): Remove2pcodes (CLRF/IORFW)\n", __FILE__, __LINE__, __FUNCTION__);
585 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
586 total_registers_saved++; // debugging stats.
588 } else if(PCI(pc1)->op == POC_MOVWF) {
589 // Optimising MOVWF reg ...
591 pct2 = findNextInstruction(pc2->next);
593 if(PCI(pc2)->op == POC_MOVFW) {
594 // Optimising MOVWF reg ... MOVF reg,W
596 if(PCI(pct2)->op == POC_MOVWF) {
605 To: ( as long as 'stuff' does not use reg2 or if following instructions do not use W or reg is not used later)
611 reg2 = getRegFromInstruction(pct2);
612 /* Check reg2 is not used for something else before it is loaded with reg */
613 if (reg2 && !regIsSpecial (reg2, 1) && !regUsedinRange(pc1,pc2,reg2)) {
614 pCode *pct3 = findNextInstruction(pct2->next);
615 /* Check following instructions are not relying on the use of W or the Z flag condiction */
616 /* XXX: We must ensure that this value is destroyed before use---otherwise it might be used in
617 * subsequent flows (checking for < 1 is insufficient). */
618 if ((pCodeSearchCondition(pct3,PCC_Z,0) == -1) && (pCodeSearchCondition(pct3,PCC_W,0) == -1)) {
619 DFPRINTF((stderr, " optimising MOVF reg ... MOVF reg,W MOVWF reg2 to MOVWF reg2 ...\n"));
620 pct2->seq = pc1->seq;
622 pCodeInsertBefore(pc1,pct2);
623 if(regUsedinRange(pct2,0,reg))
625 //fprintf (stderr, "%s:%d(%s): Remove2pcodes IF (MOVWF reg, ..., MOVW reg,W MOVWF reg2)\n", __FILE__, __LINE__, __FUNCTION__);
626 Remove2pcodes(pcfl_used, pc2, NULL, reg, can_free);
628 //fprintf (stderr, "%s:%d(%s): Remove2pcodes ELSE (MOVWF reg, ..., MOVW reg,W MOVWF reg2)\n", __FILE__, __LINE__, __FUNCTION__);
629 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
631 total_registers_saved++; // debugging stats.
638 pct1 = findPrevInstruction(pc1->prev);
639 if(pct1 && (PCI(pct1)->pcflow == PCI(pc1)->pcflow)) {
641 if ( (PCI(pct1)->op == POC_MOVFW) &&
642 (PCI(pc2)->op == POC_MOVFW)) {
644 reg1 = getRegFromInstruction(pct1);
645 if(reg1 && !regIsSpecial (reg1, 0) && !regUsedinRange(pc1,pc2,reg1)) {
646 DFPRINTF((stderr, " optimising MOVF reg1,W MOVWF reg ... MOVF reg,W\n"));
662 Or, if we're not deleting the register then the "To" is:
669 pct2 = newpCode(PCI(pc2)->op, PCI(pct1)->pcop);
670 pCodeInsertAfter(pc2, pct2);
671 PCI(pct2)->pcflow = PCFL(pcfl_used);
672 pct2->seq = pc2->seq;
675 //fprintf (stderr, "%s:%d(%s): Remove2pcodes CANFREE (MOVF reg1,W; MOVWF reg2; MOVF reg2,W)\n", __FILE__, __LINE__, __FUNCTION__);
676 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
678 /* If we're not freeing the register then that means (probably)
679 * the register is needed somewhere else.*/
681 pCodeInsertAfter(pct2, pc1);
683 //fprintf (stderr, "%s:%d(%s): Remove2pcodes ELSE (MOVF reg1,W; MOVWF reg2; MOVF reg2,W)\n", __FILE__, __LINE__, __FUNCTION__);
684 Remove2pcodes(pcfl_used, pc2, NULL, reg, can_free);
687 //fprintf (stderr, "%s:%d(%s): Remove2pcodes ALWAYS (MOVF reg1,W; MOVWF reg2; MOVF reg2,W)\n", __FILE__, __LINE__, __FUNCTION__);
688 Remove2pcodes(pcfl_used, pct1, NULL, reg1, 0);
689 total_registers_saved++; // debugging stats.
696 return (total_registers_saved != t);
699 /*-----------------------------------------------------------------*
700 * void pCodeRegOptimeRegUsage(pBlock *pb)
701 *-----------------------------------------------------------------*/
702 void OptimizeRegUsage(set *fregs, int optimize_multi_uses, int optimize_level)
706 pCode *pc1=NULL, *pc2=NULL;
710 pCode *pcfl_used, *pcfl_assigned;
712 /* Step through the set by directly accessing the 'next' pointer.
713 * We could also step through by using the set API, but the
714 * the (debug) calls to print instructions affect the state
715 * of the set pointers */
720 if (strcmp(reg->name,"_SubState")==0)
721 fprintf(stderr,"Reg: %s\n",reg->name);
724 /* Catch inconsistently set-up live ranges
725 * (see tracker items #1469504 + #1474602)
726 * FIXME: Actually we should rather fix the
727 * computation of the liveranges instead...
729 if (!reg || !reg->reglives.usedpFlows
730 || !reg->reglives.assignedpFlows)
732 //fprintf( stderr, "skipping reg w/o liveranges: %s\n", reg ? reg->name : "(unknown)");
736 if(reg->type == REG_SFR || reg->type == REG_STK || reg->isPublic || reg->isExtern|| reg->isFixed) {
737 //fprintf(stderr,"skipping SFR: %s\n",reg->name);
741 pcfl_used = setFirstItem(reg->reglives.usedpFlows);
742 pcfl_assigned = setFirstItem(reg->reglives.assignedpFlows);
744 used = elementsInSet(reg->reglives.usedpCodes);
747 In this section, all registers that are used in only in two
748 instructions are examined. If possible, they're optimized out.
752 fprintf (stderr, "OptimizeRegUsage: %s addr=0x%03x rIdx=0x%03x type=%d used=%d\n",
755 reg->rIdx, reg->type, used);
757 pc1 = setFirstItem(reg->reglives.usedpCodes);
758 pc2 = setNextItem(reg->reglives.usedpCodes);
760 if(pcfl_used && pcfl_assigned) {
762 expected case - the register has been assigned a value and is
766 //fprintf(stderr," used only twice\n");
767 if(pcfl_used->seq == pcfl_assigned->seq) {
769 //fprintf(stderr, " and used in same flow\n");
771 pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 1,optimize_level);
774 // fprintf(stderr, " and used in different flows\n");
778 } else if(pcfl_used) {
780 /* register has been used twice without ever being assigned */
781 fprintf(stderr,"WARNING %s: reg %s used without being assigned\n",__FUNCTION__,reg->name);
784 //fprintf(stderr,"WARNING %s.1: reg %s assigned without being used\n",__FUNCTION__,reg->name);
785 Remove2pcodes(pcfl_assigned, pc1, pc2, reg, 1);
786 total_registers_saved++; // debugging stats.
790 /* register has been used either once, or more than twice */
792 if(used && !pcfl_used && pcfl_assigned) {
795 //fprintf(stderr,"WARNING %s.2: reg %s assigned without being used\n",__FUNCTION__,reg->name);
797 pc = setFirstItem(reg->reglives.usedpCodes);
800 pcfl_assigned = PCODE(PCI(pc)->pcflow);
801 Remove1pcode(pc, reg,2);
803 deleteSetItem (&(PCFL(pcfl_assigned)->registers), reg);
805 deleteSetItem (&(reg->reglives.usedpCodes),pc);
808 pc = setNextItem(reg->reglives.usedpCodes);
815 total_registers_saved++; // debugging stats.
816 } else if( (used > 2) && optimize_multi_uses) {
822 pCodeFlow *pcfl1=NULL, *pcfl2=NULL;
824 /* examine the number of times this register is used */
827 rset1 = reg->reglives.usedpCodes;
828 while(rset1 && searching) {
833 if(pc1 && isPCI(pc1) && ( (pcfl1 = PCI(pc1)->pcflow) != NULL) ) {
835 //while(rset2 && searching) {
839 if(pc2 && isPCI(pc2) && ( (pcfl2 = PCI(pc2)->pcflow) != NULL) ) {
842 if(pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 0,optimize_level))
847 //rset2 = rset2->next;
860 /* The following routines implement pCode optimizations based on
861 * dataflow analysis. The effects should be similar to those
862 * of pCodeOptime2pCodes() but more powerful.
864 * Unfortunately, the current approach (comparing operands by
865 * their associated registers) is seriously flawed:
866 * Some pCodeOps do not provide access to their repsective regs
867 * (PO_DIRs are created from arbitrary strings, immediates need
868 * to take offset and index into account, ...)
870 * This has to be rewritten based on pCodeOps instead of regs...
873 /* ------------------------------------------------------------------
874 Returns TRUE iff reg1 and reg2 are the same registers.
875 ------------------------------------------------------------------ */
877 static int sameRegs (const regs *reg1, const regs *reg2)
879 if (reg1 == reg2) return 1;
880 if (!reg1 || !reg2) return 0;
881 assert (reg1->name && reg2->name);
883 /* Compare names, as rIdx is not unique... */
884 if (!strcmp(reg1->name, reg2->name)) return 1;
886 /* Name mismatch -- not the same register. */
890 /* ------------------------------------------------------------------
891 Returns 1 if the register is live at pc (read in this flow),
892 returns -1 if the register is NOT live at pc (assigned a new value
893 prior to readingi the old value in this flow) or
894 return 0 if the register is not mentioned.
895 ------------------------------------------------------------------ */
897 static int checkRegInFlow (regs **reg, int *cond, pCode *pc)
899 const int verbose = 0;
900 /* find next PCI at or after pc */
901 while (pc && isPCFL(pc)) pc = pc->next;
903 assert (reg && cond);
905 /* remove pseudo flags from cond */
906 *cond &= ~(PCC_REGISTER | PCC_EXAMINE_PCOP);
910 fprintf (stderr, "Checking for reg %s, cond %x on pc ", *reg ? (*reg)->name : "<none>", *cond); pc->print (stderr, pc);
913 while (pc && !isPCFL(pc))
917 fprintf (stderr, " now checking for reg %s, cond %x on pc ", *reg ? (*reg)->name : "<none>", *cond);
918 pc->print (stderr, pc);
926 pcprev = findPrevInstruction (pc);
927 if (pcprev && isPCI_SKIP(pcprev))
930 if ((PCI(pc)->inCond | PCI(pc)->outCond) & PCC_REGISTER)
932 op = getRegFromInstruction (pc);
934 /* pCodeOpRegBits do not provide register information... */
935 //if (!op) { __asm__("int3"); pc->print (stderr, pc); }
940 return 1; /* assume `reg' is alive */
943 /* SPECIAL CASE: jump to unknown destination -- assume everything alive */
944 if (op->type == PO_PCL)
950 if (PCI(pc)->inCond & PCC_REGISTER)
952 /* `op' is live (possibly read) */
953 if (*reg && sameRegs (op, *reg))
957 fprintf (stderr, "reg is read in pc ");
958 pc->print (stderr, pc);
964 /* handle additional implicit operands */
967 case POC_CALL: /* read arguments from WREG, clobbers WREG */
972 fprintf (stderr, "conditions are read at pc ");
973 pc->print (stderr, pc);
979 case POC_RETURN: /* returns WREG to caller */
980 //fprintf (stderr, "reached RETURN, reg %s, cond %x\n", *reg ? (*reg)->name : "<none>", *cond);
985 fprintf (stderr, "conditions are read at pc ");
986 pc->print (stderr, pc);
990 /* afterwards, no condition is alive */
992 /* afterwards, all local registers are dead */
993 if (*reg && regIsLocal (*reg)) *reg = NULL;
996 case POC_RETFIE: /* this does not erturn WREG to the "caller", thus its rather a RETLW */
997 /* this discards WREG */
999 /* afterwards, no condition is alive */
1001 /* afterwards, all local registers are dead */
1002 if (*reg && regIsLocal (*reg)) *reg = NULL;
1005 /* no implicit arguments */
1009 if (PCI(pc)->inCond & (*cond))
1011 /* a condition is read */
1014 fprintf (stderr, "conditions are read at pc ");
1015 pc->print (stderr, pc);
1020 /* remove outConds from `cond' */
1021 (*cond) &= ~(PCI(pc)->outCond);
1023 if (PCI(pc)->outCond & PCC_REGISTER)
1025 /* `op' is (possibly) discarded */
1026 if (*reg && !prevIsSkip && sameRegs (op, *reg))
1030 fprintf (stderr, "reg is assigned (cont'd) at pc ");
1031 pc->print (stderr, pc);
1037 /* have all interesting conditions/registers been discarded? */
1038 if (!(*reg) && !(*cond))
1042 fprintf (stderr, "reg and conditions are discarded after ");
1043 pc->print (stderr, pc);
1052 /* no use of (or only conditional writes to) `reg' found in flow */
1055 fprintf (stderr, "analysis inconclusive: reg %s, cond %x remains\n", *reg ? "remains" : "is void", *cond);
1060 /* ------------------------------------------------------------------
1061 This will return 1 only if
1062 - reg is NULL or of type REG_TMP
1063 - reg is NULL or its value is discarded after pc
1064 - cond is 0 or all conditions are overwritten before being used
1065 ------------------------------------------------------------------ */
1073 df_state_t *df_free_states = NULL;
1076 df_newState (regs *reg, int cond, pCode *pc)
1080 if (df_free_states) {
1081 state = df_free_states;
1082 df_free_states = (df_state_t *)df_free_states->pc;
1084 state = Safe_calloc(1, sizeof(df_state_t));
1093 df_containsState (set *set, df_state_t *state)
1095 /* scan set for presence of `state' */
1097 for (curr = setFirstItem (set); curr; curr = setNextItem (set))
1099 if ((curr->pc == state->pc)
1100 && (curr->reg == state->reg)
1101 && (curr->cond == state->cond))
1111 df_releaseState (df_state_t *state)
1113 state->pc = (pCode *)df_free_states;
1114 df_free_states = (df_state_t *)state;
1123 while (df_free_states)
1125 next = (df_state_t *)df_free_states->pc;
1126 Safe_free(df_free_states);
1127 df_free_states = next;
1131 int regIsDead (regs *reg, int cond, pCode *pc)
1133 set *seenStates = NULL;
1140 if (reg && !regIsLocal (reg)) return 0;
1142 pc = findNextInstruction (pc->next);
1144 addSet (&todo, df_newState(reg, cond, pc));
1146 while ((result == 1) && (state = getSet (&todo)))
1150 if (df_containsState (seenStates, state)) continue;
1151 addSet (&seenStates, state);
1157 //fprintf (stderr, "Checking for reg %s/cond %x at pc ", reg ? reg->name : "<none>", cond);
1158 //curr->print (stderr, curr);
1160 res = checkRegInFlow (®, &cond, curr);
1163 case 1: /* `reg' or `cond' is read---not dead */
1166 case -1: /* `reg' and `cond' are discarded in this flow---need to check other open flows */
1168 default: /* `reg' is not read and (possibly) not assigned---check successor flows */
1171 pCodeFlow *pcfl = PCI(curr)->pcflow;
1172 pCodeFlowLink *link;
1176 for (link = setFirstItem(pcfl->to); link; link = setNextItem (pcfl->to))
1178 /* add the first pCodeInstruction in the new flow to `todo' */
1179 first = findNextInstruction (&link->pcflow->pc);
1180 if (first) addSet (&todo, df_newState (reg, cond, first));
1188 while (NULL != (state = getSet (&todo))) { df_releaseState (state); }
1189 while (NULL != (state = getSet (&seenStates))) { df_releaseState (state); }
1191 /* if result remained 1, `reg' is not even possibly read and thus dead */
1197 /* ------------------------------------------------------------------
1198 Safely remove a pCode.
1199 This needs to check that the previous instruction was no SKIP
1200 (otherwise the SKIP instruction would have to be removed as well,
1201 which may not be done for SFRs (side-effects on read possible)).
1202 ------------------------------------------------------------------ */
1204 extern void unBuildFlow (pBlock *pb);
1205 extern void RegsUnMapLiveRanges ();
1206 extern void BuildFlow (pBlock *pb);
1207 extern void LinkFlow (pBlock *pb);
1208 extern void BuildFlowTree (pBlock *pb);
1209 extern void pCodeRegMapLiveRanges (pBlock *pb);
1210 extern pFile *the_pFile;
1212 static int pCodeRemove (pCode *pc, const char *comment)
1214 pCode *pcprev, *pcnext;
1215 unsigned int result = 0;
1217 /* Sanity checks. */
1219 if (!isPCI(pc)) return 0;
1221 pcprev = findPrevInstruction (pc->prev);
1222 if (pcprev && isPCI_SKIP(pcprev))
1224 /* bail out until we know how to fix the Flow... */
1227 /* we also need to remove the preceeding SKIP instruction(s) */
1228 result = pCodeRemove (pcprev, "=DF= removing preceeding SKIP as well");
1231 /* previous instruction could not be removed -- this cannot be removed as well */
1234 /* FIXME: We now have to update the flow! */
1237 /* do not remove pCodes with SFRs as operands (even reading them might cause side effects) */
1240 reg = getRegFromInstruction (pc);
1241 /* accesses to the STATUS register aer always safe, but others... */
1242 if (reg && reg->type == REG_SFR && reg->pc_type != PO_STATUS) return result;
1245 /* MUST SUCEED FROM NOW ON (or revert the changes done since NOW ;-)) */
1248 if (PCI(pc)->pcflow && PCI(pc)->pcflow->end == pc)
1251 pcprev = findPrevInstruction (pc->prev);
1252 if (PCI(pcprev)->pcflow == PCI(pc)->pcflow)
1254 PCI(pc)->pcflow->end = pcprev;
1256 pBlock *pb = pc->pb;
1257 RegsUnMapLiveRanges();
1262 for (pb = the_pFile->pbHead; pb; pb = pb->next)
1264 pCodeRegMapLiveRanges(pb);
1269 /* attach labels to next instruction */
1270 pcnext = findNextInstruction (pc->next);
1273 PCI(pcnext)->label = pBranchAppend (PCI(pcnext)->label, PCI(pc)->label);
1274 if (!PCI(pcnext)->cline) PCI(pcnext)->cline = PCI(pc)->cline;
1278 fprintf (stderr, "Cannot move a label...\n");
1286 char *pbuff = &buffer[0];
1288 SAFE_snprintf (&pbuff, &size, "; %s:%u(%s): %s", __FILE__, __LINE__, __FUNCTION__, comment);
1289 pCodeInsertAfter(pc->prev, newpCodeCharP (&buffer[0]));
1294 /* replace removed pCode with out-commented version of itself */
1297 char *pbuff = &buffer[0];
1299 SAFE_snprintf (&pbuff, &size, "; %s:%u(%s): ", __FILE__, __LINE__, __FUNCTION__);
1300 pCode2str (pbuff, size, pc);
1301 pCodeInsertAfter(pc->prev, newpCodeCharP (&buffer[0]));
1308 /* ------------------------------------------------------------------
1309 Find and remove dead pCodes.
1310 ------------------------------------------------------------------ */
1312 static int removeIfDeadPCI (pCode *pc)
1314 pCode *pcnext = NULL;
1316 unsigned int outCond;
1317 unsigned int result = 0;
1324 pcnext = findNextInstruction (pc->next);
1325 if (!isPCI(pc)) return 0;
1327 switch (PCI(pc)->op)
1383 /* do not remove unknown PCIs */
1387 /* redundant checks---those instructions may never be removed */
1388 if (isPCI_BRANCH(pc)) return 0;
1389 if (isPCI_SKIP(pc)) return 0;
1391 outCond = PCI(pc)->outCond;
1394 /* unknown operands assigned to, then ignore */
1395 if ((outCond & (PCC_REGISTER | PCC_C | PCC_Z | PCC_DC | PCC_W)) != outCond)
1398 if (outCond & PCC_REGISTER)
1400 dst = getRegFromInstruction (pc);
1404 if (!regIsLocal (dst)) return 0;
1405 if (regIsSpecial (dst,0)) return 0;
1408 //fprintf (stderr, "--> checking for liveness pc "); pc->print (stderr, pc);
1409 if (regIsDead (dst, outCond, pc))
1411 /* no result from pc has been used -- pc is `dead' */
1412 //fprintf (stderr, "--> reg %s and cond %x assumed unused\n", dst ? dst->name : "<none>", outCond);
1413 //fprintf (stderr, "--> removing dead pc "); pc->print (stderr, pc);
1414 result = pCodeRemove (pc, "=DF= removed dead pCode");
1420 /* ------------------------------------------------------------------
1421 This routine is intended to safely replace one pCodeInstruction
1422 with a different pCodeInstruction.
1423 If desired, the replaced pCode will be left in (commented out) for
1425 Further, an optional comment can be inserted to indicate the
1426 reason for the possible removal of the pCode.
1427 ------------------------------------------------------------------ */
1429 static void replace_PCI (pCodeInstruction *pc, pCodeInstruction *newpc, char *comment)
1431 newpc->from = pBranchAppend (newpc->from, pc->from);
1432 newpc->to = pBranchAppend (newpc->to, pc->to);
1433 newpc->label = pBranchAppend (newpc->label, pc->label);
1434 //newpc->pcflow = pc->pcflow; // updated in pCodeInsertAfter, ->pb is as well
1435 newpc->cline = pc->cline;
1437 newpc->pc.seq = pc->pc.seq;
1439 pCodeInsertAfter (&pc->pc, &newpc->pc);
1441 /* FIXME: replacing pc will break the liverange maps (usedpCodes, ...) */
1442 pCodeRegMapLiveRanges( pc->pBlock ); /*FIXME:UNTESTED*/
1446 pCodeInsertAfter (&pc->pc, newpCodeCharP (comment));
1451 /* replace pc with commented out version of itself */
1452 char buffer[1024], buffer2[1024];
1453 char *pbuff = &buffer[0];
1455 pCode2str (&buffer2[0],1024,&pc->pc);
1456 SAFE_snprintf (&pbuff,&size,"%s:%u(%s): removed pCode was %s\t", __FILE__, __LINE__, __FUNCTION__, &buffer2[0]);
1457 pCodeInsertAfter (&pc->pc, newpCodeCharP (&buffer[0]));
1460 pc->pc.destruct (&pc->pc);
1463 /* ------------------------------------------------------------------
1464 Find the first (unique) assignment to `reg' (prior to pc).
1465 ------------------------------------------------------------------ */
1467 pCode *findAssignmentToReg (regs *reg, pCode *pc)
1471 assert (pc && isPCI(pc) && reg);
1473 curr = findPrevInstruction (pc->prev);
1475 while (curr && PCI(curr)->pcflow == PCI(pc)->pcflow)
1477 if (PCI(curr)->outCond & PCC_REGISTER)
1479 regs *op = getRegFromInstruction (curr);
1480 if (op && (sameRegs(op,reg)))
1483 curr = findPrevInstruction (curr->prev);
1486 /* no assignment to reg found */
1490 /* ------------------------------------------------------------------
1491 Find a register that holds the same value as `reg' (an alias).
1492 ------------------------------------------------------------------ */
1494 regs *findRegisterAlias (regs *reg, pCode *pc)
1498 if(!reg) return NULL;
1500 if (regIsSpecial (reg, 0)) return NULL;
1502 curr = findAssignmentToReg (reg, pc);
1504 /* no assignment found --> no alias found */
1505 if (!curr) return NULL;
1507 switch (PCI(curr)->op)
1510 /* find previous assignment to WREG */
1511 while (curr && !(PCI(curr)->outCond & PCC_W))
1512 curr = findPrevInstruction (curr->prev);
1513 if (curr && PCI(curr)->op == POC_MOVFW)
1515 regs *op = getRegFromInstruction (curr);
1516 /* alias must not be changed since assignment... */
1517 if (PCI(curr)->pcop)
1519 switch (PCI(curr)->pcop->type)
1521 case PO_GPR_REGISTER:
1523 /* these operands are ok */
1526 /* not a plain register operand */
1531 if (!op || regIsSpecial (op, 0) || !regIsUnchangedSince (op, pc, curr)) return NULL;
1532 //fprintf (stderr, "found register alias for %s: %s\n", reg->name, op && op->name ? op->name : "<no name>");
1535 /* unknown source to WREG -- unknown register alias */
1541 /* unhandled instruction -- assume unknown source, no alias */
1545 /* no alias found */
1549 /* ------------------------------------------------------------------
1550 Analyze a single pCodeInstruction's dataflow relations and replace
1551 it with a better variant if possible.
1552 ------------------------------------------------------------------ */
1554 void analyzeAndReplacePCI (pCodeInstruction *pci)
1556 regs *op_reg, *alias_reg;
1560 if (!isPCI(pci)) return;
1569 /* try to find a different source register */
1570 op_reg = getRegFromInstruction (&pci->pc);
1571 if (pci->op == POC_MOVFW) /* touches Z */
1573 pCode *assignment = findAssignmentToReg (op_reg, &pci->pc);
1574 if (assignment && isPCI(assignment) && (PCI(assignment)->op == POC_CLRF))
1576 replace_PCI (pci, PCI(newpCode(POC_MOVLW, newpCodeOpLit(0))), "replaced with CLRF");
1581 alias_reg = findRegisterAlias (op_reg, &pci->pc);
1584 replace_PCI (pci, PCI(newpCode(pci->op, newpCodeOpRegFromStr (alias_reg->name))), "=DF= replaced with move from register alias");
1589 /* do not optimize */
1594 extern pFile *the_pFile;
1596 /* ------------------------------------------------------------------
1597 Find and remove dead pCodes.
1598 ------------------------------------------------------------------ */
1600 static int removeDeadPCIs (void)
1603 unsigned int removed = 0;
1605 if (!the_pFile) return removed;
1610 /* iterate over all pBlocks */
1611 for (pb = the_pFile->pbHead; pb; pb = pb->next)
1613 pCode *pc, *pcnext = NULL;
1615 /* iterate over all pCodes */
1616 for (pc = findNextInstruction (pb->pcHead); pc; pc = pcnext)
1618 pcnext = findNextInstruction (pc->next);
1619 removed += removeIfDeadPCI (pc);
1623 fprintf (stderr, "[removed %u dead pCodes]\n", removed);
1629 /* ------------------------------------------------------------------
1630 This routine tries to optimize the dataflow by...
1633 This routine leaves in dead pCodes (assignments whose results are
1634 not used) -- these should be removed in a following sweep phase.
1635 ------------------------------------------------------------------ */
1637 void optimizeDataflow (void)
1641 if (!the_pFile) return;
1643 //fprintf (stderr, "%s:%u(%s): Starting optimization...\n", __FILE__, __LINE__, __FUNCTION__);
1645 /* iterate over all pBlocks */
1646 for (pb = the_pFile->pbHead; pb; pb = pb->next)
1648 pCode *pc, *pcnext = NULL;
1650 /* iterate over all pCodes */
1651 for (pc = findNextInstruction (pb->pcHead); pc; pc = pcnext)
1653 pcnext = findNextInstruction (pc->next);
1654 analyzeAndReplacePCI (PCI(pc));
1658 while (removeDeadPCIs ()) { /* remove dead codes in multiple passes */};
1664 /*-----------------------------------------------------------------*
1665 * void pCodeRegOptimeRegUsage(pBlock *pb)
1666 *-----------------------------------------------------------------*/
1667 void pCodeRegOptimizeRegUsage(int level)
1672 int t = total_registers_saved;
1675 /* This is currently broken (need rewrite to correctly
1676 * handle arbitrary pCodeOps instead of registers only). */
1677 if (!pic14_options.disable_df)
1678 optimizeDataflow ();
1681 if(!register_optimization)
1683 #define OPT_PASSES 4
1684 passes = OPT_PASSES;
1687 saved = total_registers_saved;
1689 /* Identify registers used in one flow sequence */
1690 OptimizeRegUsage(dynAllocRegs,level, (OPT_PASSES-passes));
1691 OptimizeRegUsage(dynStackRegs,level, (OPT_PASSES-passes));
1692 OptimizeRegUsage(dynDirectRegs,0, (OPT_PASSES-passes));
1694 if(total_registers_saved != saved)
1695 DFPRINTF((stderr, " *** pass %d, Saved %d registers, total saved %d ***\n",
1696 (1+OPT_PASSES-passes),total_registers_saved-saved,total_registers_saved));
1700 } while( passes && ((total_registers_saved != saved) || (passes==OPT_PASSES-1)) );
1702 if(total_registers_saved == t)
1703 DFPRINTF((stderr, "No registers saved on this pass\n"));
1707 fprintf(stderr,"dynamically allocated regs:\n");
1708 dbg_regusage(dynAllocRegs);
1709 fprintf(stderr,"stack regs:\n");
1710 dbg_regusage(dynStackRegs);
1711 fprintf(stderr,"direct regs:\n");
1712 dbg_regusage(dynDirectRegs);
1717 /*-----------------------------------------------------------------*
1718 * void RegsUnMapLiveRanges(set *regset)
1720 *-----------------------------------------------------------------*/
1721 void RegsSetUnMapLiveRanges(set *regset)
1727 regset = regset->next;
1730 deleteSet(®->reglives.usedpCodes);
1731 deleteSet(®->reglives.usedpFlows);
1732 deleteSet(®->reglives.assignedpFlows);
1738 void RegsUnMapLiveRanges(void)
1741 RegsSetUnMapLiveRanges(dynAllocRegs);
1742 RegsSetUnMapLiveRanges(dynStackRegs);
1743 RegsSetUnMapLiveRanges(dynDirectRegs);
1744 RegsSetUnMapLiveRanges(dynProcessorRegs);
1745 RegsSetUnMapLiveRanges(dynDirectBitRegs);
1746 RegsSetUnMapLiveRanges(dynInternalRegs);