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) ){
549 can be replaced with (only if following instructions are not going to use W and reg is not used again later)
554 DFPRINTF((stderr, " optimising CLRF reg ... MOVF reg,W to ... MOVLW 0\n"));
555 pct2 = findNextInstruction(pc2->next);
557 if(pct2 && PCI(pct2)->op == POC_MOVWF) {
558 wSaved = wUsed = 1; /* Maybe able to replace with clrf pc2->next->reg. */
560 wUsed = pCodeSearchCondition(pct2,PCC_W,1) != -1;
562 regUsed = regUsedinRange(pct2,0,reg);
563 if ((regUsed&&wUsed) || (pCodeSearchCondition(pct2,PCC_Z,0) != -1)) {
564 /* Do not optimise as exisiting code is required. */
568 newpc = newpCode(POC_CLRF, PCI(pc1)->pcop);
569 } else if(wSaved && !wUsed) {
570 newpc = newpCode(POC_CLRF, PCI(pct2)->pcop);
571 pct2->destruct(pct2);
573 newpc = newpCode(POC_MOVLW, newpCodeOpLit(0));
576 pCodeInsertAfter(pc2, newpc);
577 PCI(newpc)->pcflow = PCFL(pcfl_used);
578 newpc->seq = pc2->seq;
580 //fprintf (stderr, "%s:%d(%s): Remove2pcodes (CLRF reg, ..., MOVF reg,W)\n", __FILE__, __LINE__, __FUNCTION__);
581 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
582 total_registers_saved++; // debugging stats.
584 } else if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_IORFW) ){
585 DFPRINTF((stderr, " optimising CLRF/IORFW\n"));
587 pct2 = findNextInstruction(pc2->next);
589 /* We must ensure that is destroyed before being read---IORLW must be performed unless this is proven. */
590 if(pCodeSearchCondition(pct2, PCC_Z,0) != -1) {
591 pct2 = newpCode(POC_IORLW, newpCodeOpLit(0));
592 pct2->seq = pc2->seq;
593 PCI(pct2)->pcflow = PCFL(pcfl_used);
594 pCodeInsertAfter(pc1,pct2);
596 //fprintf (stderr, "%s:%d(%s): Remove2pcodes (CLRF/IORFW)\n", __FILE__, __LINE__, __FUNCTION__);
597 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
598 total_registers_saved++; // debugging stats.
600 } else if(PCI(pc1)->op == POC_MOVWF) {
601 // Optimising MOVWF reg ...
603 pct2 = findNextInstruction(pc2->next);
605 if(PCI(pc2)->op == POC_MOVFW) {
606 // Optimising MOVWF reg ... MOVF reg,W
608 if(PCI(pct2)->op == POC_MOVWF) {
617 To: ( as long as 'stuff' does not use reg2 or if following instructions do not use W or reg is not used later)
623 reg2 = getRegFromInstruction(pct2);
624 /* Check reg2 is not used for something else before it is loaded with reg */
625 if (reg2 && !regIsSpecial (reg2, 1) && !regUsedinRange(pc1,pc2,reg2)) {
626 pCode *pct3 = findNextInstruction(pct2->next);
627 /* Check following instructions are not relying on the use of W or the Z flag condiction */
628 /* XXX: We must ensure that this value is destroyed before use---otherwise it might be used in
629 * subsequent flows (checking for < 1 is insufficient). */
630 if ((pCodeSearchCondition(pct3,PCC_Z,0) == -1) && (pCodeSearchCondition(pct3,PCC_W,0) == -1)) {
631 DFPRINTF((stderr, " optimising MOVF reg ... MOVF reg,W MOVWF reg2 to MOVWF reg2 ...\n"));
632 pct2->seq = pc1->seq;
634 pCodeInsertBefore(pc1,pct2);
635 if(regUsedinRange(pct2,0,reg))
637 //fprintf (stderr, "%s:%d(%s): Remove2pcodes IF (MOVWF reg, ..., MOVW reg,W MOVWF reg2)\n", __FILE__, __LINE__, __FUNCTION__);
638 Remove2pcodes(pcfl_used, pc2, NULL, reg, can_free);
640 //fprintf (stderr, "%s:%d(%s): Remove2pcodes ELSE (MOVWF reg, ..., MOVW reg,W MOVWF reg2)\n", __FILE__, __LINE__, __FUNCTION__);
641 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
643 total_registers_saved++; // debugging stats.
650 pct1 = findPrevInstruction(pc1->prev);
651 if(pct1 && (PCI(pct1)->pcflow == PCI(pc1)->pcflow)) {
653 if ( (PCI(pct1)->op == POC_MOVFW) &&
654 (PCI(pc2)->op == POC_MOVFW)) {
656 reg1 = getRegFromInstruction(pct1);
657 if(reg1 && !regIsSpecial (reg1, 0) && !regUsedinRange(pc1,pc2,reg1)) {
658 DFPRINTF((stderr, " optimising MOVF reg1,W MOVWF reg ... MOVF reg,W\n"));
674 Or, if we're not deleting the register then the "To" is:
681 pct2 = newpCode(PCI(pc2)->op, PCI(pct1)->pcop);
682 pCodeInsertAfter(pc2, pct2);
683 PCI(pct2)->pcflow = PCFL(pcfl_used);
684 pct2->seq = pc2->seq;
687 //fprintf (stderr, "%s:%d(%s): Remove2pcodes CANFREE (MOVF reg1,W; MOVWF reg2; MOVF reg2,W)\n", __FILE__, __LINE__, __FUNCTION__);
688 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
690 /* If we're not freeing the register then that means (probably)
691 * the register is needed somewhere else.*/
693 pCodeInsertAfter(pct2, pc1);
695 //fprintf (stderr, "%s:%d(%s): Remove2pcodes ELSE (MOVF reg1,W; MOVWF reg2; MOVF reg2,W)\n", __FILE__, __LINE__, __FUNCTION__);
696 Remove2pcodes(pcfl_used, pc2, NULL, reg, can_free);
699 //fprintf (stderr, "%s:%d(%s): Remove2pcodes ALWAYS (MOVF reg1,W; MOVWF reg2; MOVF reg2,W)\n", __FILE__, __LINE__, __FUNCTION__);
700 Remove2pcodes(pcfl_used, pct1, NULL, reg1, 0);
701 total_registers_saved++; // debugging stats.
708 return (total_registers_saved != t);
711 /*-----------------------------------------------------------------*
712 * void pCodeRegOptimeRegUsage(pBlock *pb)
713 *-----------------------------------------------------------------*/
714 void OptimizeRegUsage(set *fregs, int optimize_multi_uses, int optimize_level)
718 pCode *pc1=NULL, *pc2=NULL;
722 pCode *pcfl_used, *pcfl_assigned;
724 /* Step through the set by directly accessing the 'next' pointer.
725 * We could also step through by using the set API, but the
726 * the (debug) calls to print instructions affect the state
727 * of the set pointers */
732 if (strcmp(reg->name,"_SubState")==0)
733 fprintf(stderr,"Reg: %s\n",reg->name);
736 /* Catch inconsistently set-up live ranges
737 * (see tracker items #1469504 + #1474602)
738 * FIXME: Actually we should rather fix the
739 * computation of the liveranges instead...
741 if (!reg || !reg->reglives.usedpFlows
742 || !reg->reglives.assignedpFlows)
744 //fprintf( stderr, "skipping reg w/o liveranges: %s\n", reg ? reg->name : "(unknown)");
748 if(reg->type == REG_SFR || reg->type == REG_STK || reg->isPublic || reg->isExtern|| reg->isFixed) {
749 //fprintf(stderr,"skipping SFR: %s\n",reg->name);
753 pcfl_used = setFirstItem(reg->reglives.usedpFlows);
754 pcfl_assigned = setFirstItem(reg->reglives.assignedpFlows);
756 used = elementsInSet(reg->reglives.usedpCodes);
759 In this section, all registers that are used in only in two
760 instructions are examined. If possible, they're optimized out.
764 fprintf (stderr, "OptimizeRegUsage: %s addr=0x%03x rIdx=0x%03x type=%d used=%d\n",
767 reg->rIdx, reg->type, used);
769 pc1 = setFirstItem(reg->reglives.usedpCodes);
770 pc2 = setNextItem(reg->reglives.usedpCodes);
772 if(pcfl_used && pcfl_assigned) {
774 expected case - the register has been assigned a value and is
778 //fprintf(stderr," used only twice\n");
779 if(pcfl_used->seq == pcfl_assigned->seq) {
781 //fprintf(stderr, " and used in same flow\n");
783 pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 1,optimize_level);
786 // fprintf(stderr, " and used in different flows\n");
790 } else if(pcfl_used) {
792 /* register has been used twice without ever being assigned */
793 fprintf(stderr,"WARNING %s: reg %s used without being assigned\n",__FUNCTION__,reg->name);
796 //fprintf(stderr,"WARNING %s.1: reg %s assigned without being used\n",__FUNCTION__,reg->name);
797 Remove2pcodes(pcfl_assigned, pc1, pc2, reg, 1);
798 total_registers_saved++; // debugging stats.
802 /* register has been used either once, or more than twice */
804 if(used && !pcfl_used && pcfl_assigned) {
807 //fprintf(stderr,"WARNING %s.2: reg %s assigned without being used\n",__FUNCTION__,reg->name);
809 pc = setFirstItem(reg->reglives.usedpCodes);
812 pcfl_assigned = PCODE(PCI(pc)->pcflow);
813 Remove1pcode(pc, reg,2);
815 deleteSetItem (&(PCFL(pcfl_assigned)->registers), reg);
817 deleteSetItem (&(reg->reglives.usedpCodes),pc);
820 pc = setNextItem(reg->reglives.usedpCodes);
827 total_registers_saved++; // debugging stats.
828 } else if( (used > 2) && optimize_multi_uses) {
834 pCodeFlow *pcfl1=NULL, *pcfl2=NULL;
836 /* examine the number of times this register is used */
839 rset1 = reg->reglives.usedpCodes;
840 while(rset1 && searching) {
845 if(pc1 && isPCI(pc1) && ( (pcfl1 = PCI(pc1)->pcflow) != NULL) ) {
847 //while(rset2 && searching) {
851 if(pc2 && isPCI(pc2) && ( (pcfl2 = PCI(pc2)->pcflow) != NULL) ) {
854 if(pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 0,optimize_level))
859 //rset2 = rset2->next;
872 /* The following routines implement pCode optimizations based on
873 * dataflow analysis. The effects should be similar to those
874 * of pCodeOptime2pCodes() but more powerful.
876 * Unfortunately, the current approach (comparing operands by
877 * their associated registers) is seriously flawed:
878 * Some pCodeOps do not provide access to their repsective regs
879 * (PO_DIRs are created from arbitrary strings, immediates need
880 * to take offset and index into account, ...)
882 * This has to be rewritten based on pCodeOps instead of regs...
885 /* ------------------------------------------------------------------
886 Returns TRUE iff reg1 and reg2 are the same registers.
887 ------------------------------------------------------------------ */
889 static int sameRegs (const regs *reg1, const regs *reg2)
891 if (reg1 == reg2) return 1;
892 if (!reg1 || !reg2) return 0;
893 assert (reg1->name && reg2->name);
895 /* Compare names, as rIdx is not unique... */
896 if (!strcmp(reg1->name, reg2->name)) return 1;
898 /* Name mismatch -- not the same register. */
902 /* ------------------------------------------------------------------
903 Returns 1 if the register is live at pc (read in this flow),
904 returns -1 if the register is NOT live at pc (assigned a new value
905 prior to readingi the old value in this flow) or
906 return 0 if the register is not mentioned.
907 ------------------------------------------------------------------ */
909 static int checkRegInFlow (regs **reg, int *cond, pCode *pc)
911 const int verbose = 0;
912 /* find next PCI at or after pc */
913 while (pc && isPCFL(pc)) pc = pc->next;
915 assert (reg && cond);
917 /* remove pseudo flags from cond */
918 *cond &= ~(PCC_REGISTER | PCC_EXAMINE_PCOP);
922 fprintf (stderr, "Checking for reg %s, cond %x on pc ", *reg ? (*reg)->name : "<none>", *cond); pc->print (stderr, pc);
925 while (pc && !isPCFL(pc))
929 fprintf (stderr, " now checking for reg %s, cond %x on pc ", *reg ? (*reg)->name : "<none>", *cond);
930 pc->print (stderr, pc);
938 pcprev = findPrevInstruction (pc);
939 if (pcprev && isPCI_SKIP(pcprev))
942 if ((PCI(pc)->inCond | PCI(pc)->outCond) & PCC_REGISTER)
944 op = getRegFromInstruction (pc);
946 /* pCodeOpRegBits do not provide register information... */
947 //if (!op) { __asm__("int3"); pc->print (stderr, pc); }
952 return 1; /* assume `reg' is alive */
955 /* SPECIAL CASE: jump to unknown destination -- assume everything alive */
956 if (op->type == PO_PCL)
962 if (PCI(pc)->inCond & PCC_REGISTER)
964 /* `op' is live (possibly read) */
965 if (*reg && sameRegs (op, *reg))
969 fprintf (stderr, "reg is read in pc ");
970 pc->print (stderr, pc);
976 /* handle additional implicit operands */
979 case POC_CALL: /* read arguments from WREG, clobbers WREG */
984 fprintf (stderr, "conditions are read at pc ");
985 pc->print (stderr, pc);
991 case POC_RETURN: /* returns WREG to caller */
992 //fprintf (stderr, "reached RETURN, reg %s, cond %x\n", *reg ? (*reg)->name : "<none>", *cond);
997 fprintf (stderr, "conditions are read at pc ");
998 pc->print (stderr, pc);
1002 /* afterwards, no condition is alive */
1004 /* afterwards, all local registers are dead */
1005 if (*reg && regIsLocal (*reg)) *reg = NULL;
1008 case POC_RETFIE: /* this does not erturn WREG to the "caller", thus its rather a RETLW */
1009 /* this discards WREG */
1011 /* afterwards, no condition is alive */
1013 /* afterwards, all local registers are dead */
1014 if (*reg && regIsLocal (*reg)) *reg = NULL;
1017 /* no implicit arguments */
1021 if (PCI(pc)->inCond & (*cond))
1023 /* a condition is read */
1026 fprintf (stderr, "conditions are read at pc ");
1027 pc->print (stderr, pc);
1032 /* remove outConds from `cond' */
1033 (*cond) &= ~(PCI(pc)->outCond);
1035 if (PCI(pc)->outCond & PCC_REGISTER)
1037 /* `op' is (possibly) discarded */
1038 if (*reg && !prevIsSkip && sameRegs (op, *reg))
1042 fprintf (stderr, "reg is assigned (cont'd) at pc ");
1043 pc->print (stderr, pc);
1049 /* have all interesting conditions/registers been discarded? */
1050 if (!(*reg) && !(*cond))
1054 fprintf (stderr, "reg and conditions are discarded after ");
1055 pc->print (stderr, pc);
1064 /* no use of (or only conditional writes to) `reg' found in flow */
1067 fprintf (stderr, "analysis inconclusive: reg %s, cond %x remains\n", *reg ? "remains" : "is void", *cond);
1072 /* ------------------------------------------------------------------
1073 This will return 1 only if
1074 - reg is NULL or of type REG_TMP
1075 - reg is NULL or its value is discarded after pc
1076 - cond is 0 or all conditions are overwritten before being used
1077 ------------------------------------------------------------------ */
1085 df_state_t *df_free_states = NULL;
1088 df_newState (regs *reg, int cond, pCode *pc)
1092 if (df_free_states) {
1093 state = df_free_states;
1094 df_free_states = (df_state_t *)df_free_states->pc;
1096 state = Safe_calloc(1, sizeof(df_state_t));
1105 df_containsState (set *set, df_state_t *state)
1107 /* scan set for presence of `state' */
1109 for (curr = setFirstItem (set); curr; curr = setNextItem (set))
1111 if ((curr->pc == state->pc)
1112 && (curr->reg == state->reg)
1113 && (curr->cond == state->cond))
1123 df_releaseState (df_state_t *state)
1125 state->pc = (pCode *)df_free_states;
1126 df_free_states = (df_state_t *)state;
1135 while (df_free_states)
1137 next = (df_state_t *)df_free_states->pc;
1138 Safe_free(df_free_states);
1139 df_free_states = next;
1143 int regIsDead (regs *reg, int cond, pCode *pc)
1145 set *seenStates = NULL;
1152 if (reg && !regIsLocal (reg)) return 0;
1154 pc = findNextInstruction (pc->next);
1156 addSet (&todo, df_newState(reg, cond, pc));
1158 while ((result == 1) && (state = getSet (&todo)))
1162 if (df_containsState (seenStates, state)) continue;
1163 addSet (&seenStates, state);
1169 //fprintf (stderr, "Checking for reg %s/cond %x at pc ", reg ? reg->name : "<none>", cond);
1170 //curr->print (stderr, curr);
1172 res = checkRegInFlow (®, &cond, curr);
1175 case 1: /* `reg' or `cond' is read---not dead */
1178 case -1: /* `reg' and `cond' are discarded in this flow---need to check other open flows */
1180 default: /* `reg' is not read and (possibly) not assigned---check successor flows */
1183 pCodeFlow *pcfl = PCI(curr)->pcflow;
1184 pCodeFlowLink *link;
1188 for (link = setFirstItem(pcfl->to); link; link = setNextItem (pcfl->to))
1190 /* add the first pCodeInstruction in the new flow to `todo' */
1191 first = findNextInstruction (&link->pcflow->pc);
1192 if (first) addSet (&todo, df_newState (reg, cond, first));
1200 while (NULL != (state = getSet (&todo))) { df_releaseState (state); }
1201 while (NULL != (state = getSet (&seenStates))) { df_releaseState (state); }
1203 /* if result remained 1, `reg' is not even possibly read and thus dead */
1209 /* ------------------------------------------------------------------
1210 Safely remove a pCode.
1211 This needs to check that the previous instruction was no SKIP
1212 (otherwise the SKIP instruction would have to be removed as well,
1213 which may not be done for SFRs (side-effects on read possible)).
1214 ------------------------------------------------------------------ */
1216 extern void unBuildFlow (pBlock *pb);
1217 extern void RegsUnMapLiveRanges ();
1218 extern void BuildFlow (pBlock *pb);
1219 extern void LinkFlow (pBlock *pb);
1220 extern void BuildFlowTree (pBlock *pb);
1221 extern void pCodeRegMapLiveRanges (pBlock *pb);
1222 extern pFile *the_pFile;
1224 static int pCodeRemove (pCode *pc, const char *comment)
1226 pCode *pcprev, *pcnext;
1227 unsigned int result = 0;
1229 /* Sanity checks. */
1231 if (!isPCI(pc)) return 0;
1233 pcprev = findPrevInstruction (pc->prev);
1234 if (pcprev && isPCI_SKIP(pcprev))
1236 /* bail out until we know how to fix the Flow... */
1239 /* we also need to remove the preceeding SKIP instruction(s) */
1240 result = pCodeRemove (pcprev, "=DF= removing preceeding SKIP as well");
1243 /* previous instruction could not be removed -- this cannot be removed as well */
1246 /* FIXME: We now have to update the flow! */
1249 /* do not remove pCodes with SFRs as operands (even reading them might cause side effects) */
1252 reg = getRegFromInstruction (pc);
1253 /* accesses to the STATUS register aer always safe, but others... */
1254 if (reg && reg->type == REG_SFR && reg->pc_type != PO_STATUS) return result;
1257 /* MUST SUCEED FROM NOW ON (or revert the changes done since NOW ;-)) */
1260 if (PCI(pc)->pcflow && PCI(pc)->pcflow->end == pc)
1263 pcprev = findPrevInstruction (pc->prev);
1264 if (PCI(pcprev)->pcflow == PCI(pc)->pcflow)
1266 PCI(pc)->pcflow->end = pcprev;
1268 pBlock *pb = pc->pb;
1269 RegsUnMapLiveRanges();
1274 for (pb = the_pFile->pbHead; pb; pb = pb->next)
1276 pCodeRegMapLiveRanges(pb);
1281 /* attach labels to next instruction */
1282 pcnext = findNextInstruction (pc->next);
1285 PCI(pcnext)->label = pBranchAppend (PCI(pcnext)->label, PCI(pc)->label);
1286 if (!PCI(pcnext)->cline) PCI(pcnext)->cline = PCI(pc)->cline;
1290 fprintf (stderr, "Cannot move a label...\n");
1298 char *pbuff = &buffer[0];
1300 SAFE_snprintf (&pbuff, &size, "; %s:%u(%s): %s", __FILE__, __LINE__, __FUNCTION__, comment);
1301 pCodeInsertAfter(pc->prev, newpCodeCharP (&buffer[0]));
1306 /* replace removed pCode with out-commented version of itself */
1309 char *pbuff = &buffer[0];
1311 SAFE_snprintf (&pbuff, &size, "; %s:%u(%s): ", __FILE__, __LINE__, __FUNCTION__);
1312 pCode2str (pbuff, size, pc);
1313 pCodeInsertAfter(pc->prev, newpCodeCharP (&buffer[0]));
1320 /* ------------------------------------------------------------------
1321 Find and remove dead pCodes.
1322 ------------------------------------------------------------------ */
1324 static int removeIfDeadPCI (pCode *pc)
1326 pCode *pcnext = NULL;
1328 unsigned int outCond;
1329 unsigned int result = 0;
1336 pcnext = findNextInstruction (pc->next);
1337 if (!isPCI(pc)) return 0;
1339 switch (PCI(pc)->op)
1395 /* do not remove unknown PCIs */
1399 /* redundant checks---those instructions may never be removed */
1400 if (isPCI_BRANCH(pc)) return 0;
1401 if (isPCI_SKIP(pc)) return 0;
1403 outCond = PCI(pc)->outCond;
1406 /* unknown operands assigned to, then ignore */
1407 if ((outCond & (PCC_REGISTER | PCC_C | PCC_Z | PCC_DC | PCC_W)) != outCond)
1410 if (outCond & PCC_REGISTER)
1412 dst = getRegFromInstruction (pc);
1416 if (!regIsLocal (dst)) return 0;
1417 if (regIsSpecial (dst,0)) return 0;
1420 //fprintf (stderr, "--> checking for liveness pc "); pc->print (stderr, pc);
1421 if (regIsDead (dst, outCond, pc))
1423 /* no result from pc has been used -- pc is `dead' */
1424 //fprintf (stderr, "--> reg %s and cond %x assumed unused\n", dst ? dst->name : "<none>", outCond);
1425 //fprintf (stderr, "--> removing dead pc "); pc->print (stderr, pc);
1426 result = pCodeRemove (pc, "=DF= removed dead pCode");
1432 /* ------------------------------------------------------------------
1433 This routine is intended to safely replace one pCodeInstruction
1434 with a different pCodeInstruction.
1435 If desired, the replaced pCode will be left in (commented out) for
1437 Further, an optional comment can be inserted to indicate the
1438 reason for the possible removal of the pCode.
1439 ------------------------------------------------------------------ */
1441 static void replace_PCI (pCodeInstruction *pc, pCodeInstruction *newpc, char *comment)
1443 newpc->from = pBranchAppend (newpc->from, pc->from);
1444 newpc->to = pBranchAppend (newpc->to, pc->to);
1445 newpc->label = pBranchAppend (newpc->label, pc->label);
1446 //newpc->pcflow = pc->pcflow; // updated in pCodeInsertAfter, ->pb is as well
1447 newpc->cline = pc->cline;
1449 newpc->pc.seq = pc->pc.seq;
1451 pCodeInsertAfter (&pc->pc, &newpc->pc);
1453 /* FIXME: replacing pc will break the liverange maps (usedpCodes, ...) */
1454 pCodeRegMapLiveRanges( pc->pBlock ); /*FIXME:UNTESTED*/
1458 pCodeInsertAfter (&pc->pc, newpCodeCharP (comment));
1463 /* replace pc with commented out version of itself */
1464 char buffer[1024], buffer2[1024];
1465 char *pbuff = &buffer[0];
1467 pCode2str (&buffer2[0],1024,&pc->pc);
1468 SAFE_snprintf (&pbuff,&size,"%s:%u(%s): removed pCode was %s\t", __FILE__, __LINE__, __FUNCTION__, &buffer2[0]);
1469 pCodeInsertAfter (&pc->pc, newpCodeCharP (&buffer[0]));
1472 pc->pc.destruct (&pc->pc);
1475 /* ------------------------------------------------------------------
1476 Find the first (unique) assignment to `reg' (prior to pc).
1477 ------------------------------------------------------------------ */
1479 pCode *findAssignmentToReg (regs *reg, pCode *pc)
1483 assert (pc && isPCI(pc) && reg);
1485 curr = findPrevInstruction (pc->prev);
1487 while (curr && PCI(curr)->pcflow == PCI(pc)->pcflow)
1489 if (PCI(curr)->outCond & PCC_REGISTER)
1491 regs *op = getRegFromInstruction (curr);
1492 if (op && (sameRegs(op,reg)))
1495 curr = findPrevInstruction (curr->prev);
1498 /* no assignment to reg found */
1502 /* ------------------------------------------------------------------
1503 Find a register that holds the same value as `reg' (an alias).
1504 ------------------------------------------------------------------ */
1506 regs *findRegisterAlias (regs *reg, pCode *pc)
1510 if(!reg) return NULL;
1512 if (regIsSpecial (reg, 0)) return NULL;
1514 curr = findAssignmentToReg (reg, pc);
1516 /* no assignment found --> no alias found */
1517 if (!curr) return NULL;
1519 switch (PCI(curr)->op)
1522 /* find previous assignment to WREG */
1523 while (curr && !(PCI(curr)->outCond & PCC_W))
1524 curr = findPrevInstruction (curr->prev);
1525 if (curr && PCI(curr)->op == POC_MOVFW)
1527 regs *op = getRegFromInstruction (curr);
1528 /* alias must not be changed since assignment... */
1529 if (PCI(curr)->pcop)
1531 switch (PCI(curr)->pcop->type)
1533 case PO_GPR_REGISTER:
1535 /* these operands are ok */
1538 /* not a plain register operand */
1543 if (!op || regIsSpecial (op, 0) || !regIsUnchangedSince (op, pc, curr)) return NULL;
1544 //fprintf (stderr, "found register alias for %s: %s\n", reg->name, op && op->name ? op->name : "<no name>");
1547 /* unknown source to WREG -- unknown register alias */
1553 /* unhandled instruction -- assume unknown source, no alias */
1557 /* no alias found */
1561 /* ------------------------------------------------------------------
1562 Analyze a single pCodeInstruction's dataflow relations and replace
1563 it with a better variant if possible.
1564 ------------------------------------------------------------------ */
1566 void analyzeAndReplacePCI (pCodeInstruction *pci)
1568 regs *op_reg, *alias_reg;
1572 if (!isPCI(pci)) return;
1581 /* try to find a different source register */
1582 op_reg = getRegFromInstruction (&pci->pc);
1583 if (pci->op == POC_MOVFW) /* touches Z */
1585 pCode *assignment = findAssignmentToReg (op_reg, &pci->pc);
1586 if (assignment && isPCI(assignment) && (PCI(assignment)->op == POC_CLRF))
1588 replace_PCI (pci, PCI(newpCode(POC_MOVLW, newpCodeOpLit(0))), "replaced with CLRF");
1593 alias_reg = findRegisterAlias (op_reg, &pci->pc);
1596 replace_PCI (pci, PCI(newpCode(pci->op, newpCodeOpRegFromStr (alias_reg->name))), "=DF= replaced with move from register alias");
1601 /* do not optimize */
1606 extern pFile *the_pFile;
1608 /* ------------------------------------------------------------------
1609 Find and remove dead pCodes.
1610 ------------------------------------------------------------------ */
1612 static int removeDeadPCIs (void)
1615 unsigned int removed = 0;
1617 if (!the_pFile) return removed;
1622 /* iterate over all pBlocks */
1623 for (pb = the_pFile->pbHead; pb; pb = pb->next)
1625 pCode *pc, *pcnext = NULL;
1627 /* iterate over all pCodes */
1628 for (pc = findNextInstruction (pb->pcHead); pc; pc = pcnext)
1630 pcnext = findNextInstruction (pc->next);
1631 removed += removeIfDeadPCI (pc);
1635 fprintf (stderr, "[removed %u dead pCodes]\n", removed);
1641 /* ------------------------------------------------------------------
1642 This routine tries to optimize the dataflow by...
1645 This routine leaves in dead pCodes (assignments whose results are
1646 not used) -- these should be removed in a following sweep phase.
1647 ------------------------------------------------------------------ */
1649 void optimizeDataflow (void)
1653 if (!the_pFile) return;
1655 //fprintf (stderr, "%s:%u(%s): Starting optimization...\n", __FILE__, __LINE__, __FUNCTION__);
1657 /* iterate over all pBlocks */
1658 for (pb = the_pFile->pbHead; pb; pb = pb->next)
1660 pCode *pc, *pcnext = NULL;
1662 /* iterate over all pCodes */
1663 for (pc = findNextInstruction (pb->pcHead); pc; pc = pcnext)
1665 pcnext = findNextInstruction (pc->next);
1666 analyzeAndReplacePCI (PCI(pc));
1670 while (removeDeadPCIs ()) { /* remove dead codes in multiple passes */};
1676 /*-----------------------------------------------------------------*
1677 * void pCodeRegOptimeRegUsage(pBlock *pb)
1678 *-----------------------------------------------------------------*/
1679 void pCodeRegOptimizeRegUsage(int level)
1684 int t = total_registers_saved;
1687 /* This is currently broken (need rewrite to correctly
1688 * handle arbitrary pCodeOps instead of registers only). */
1689 if (!pic14_options.disable_df)
1690 optimizeDataflow ();
1693 if(!register_optimization)
1695 #define OPT_PASSES 4
1696 passes = OPT_PASSES;
1699 saved = total_registers_saved;
1701 /* Identify registers used in one flow sequence */
1702 OptimizeRegUsage(dynAllocRegs,level, (OPT_PASSES-passes));
1703 OptimizeRegUsage(dynStackRegs,level, (OPT_PASSES-passes));
1704 OptimizeRegUsage(dynDirectRegs,0, (OPT_PASSES-passes));
1706 if(total_registers_saved != saved)
1707 DFPRINTF((stderr, " *** pass %d, Saved %d registers, total saved %d ***\n",
1708 (1+OPT_PASSES-passes),total_registers_saved-saved,total_registers_saved));
1712 } while( passes && ((total_registers_saved != saved) || (passes==OPT_PASSES-1)) );
1714 if(total_registers_saved == t)
1715 DFPRINTF((stderr, "No registers saved on this pass\n"));
1719 fprintf(stderr,"dynamically allocated regs:\n");
1720 dbg_regusage(dynAllocRegs);
1721 fprintf(stderr,"stack regs:\n");
1722 dbg_regusage(dynStackRegs);
1723 fprintf(stderr,"direct regs:\n");
1724 dbg_regusage(dynDirectRegs);
1729 /*-----------------------------------------------------------------*
1730 * void RegsUnMapLiveRanges(set *regset)
1732 *-----------------------------------------------------------------*/
1733 void RegsSetUnMapLiveRanges(set *regset)
1739 regset = regset->next;
1742 deleteSet(®->reglives.usedpCodes);
1743 deleteSet(®->reglives.usedpFlows);
1744 deleteSet(®->reglives.assignedpFlows);
1750 void RegsUnMapLiveRanges(void)
1753 RegsSetUnMapLiveRanges(dynAllocRegs);
1754 RegsSetUnMapLiveRanges(dynStackRegs);
1755 RegsSetUnMapLiveRanges(dynDirectRegs);
1756 RegsSetUnMapLiveRanges(dynProcessorRegs);
1757 RegsSetUnMapLiveRanges(dynDirectBitRegs);
1758 RegsSetUnMapLiveRanges(dynInternalRegs);