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);
198 //pc = findNextInstruction(pc->next);
205 /*-----------------------------------------------------------------*
206 * void pCodeRegMapLiveRanges(pBlock *pb)
207 *-----------------------------------------------------------------*/
208 void pCodeRegMapLiveRanges(pBlock *pb)
212 for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
214 pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
216 if(!isPCFL(pcflow)) {
217 fprintf(stderr, "pCodeRegMapLiveRanges - pcflow is not a flow object ");
220 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
224 for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
226 pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
228 regs *r = setFirstItem(PCFL(pcflow)->registers);
229 fprintf(stderr,"flow seq %d\n", pcflow->seq);
232 fprintf(stderr, " %s\n",r->name);
233 r = setNextItem(PCFL(pcflow)->registers);
240 // dbg_dumpregusage();
245 /*-----------------------------------------------------------------*
247 *-----------------------------------------------------------------*/
248 static void Remove1pcode(pCode *pc, regs *reg, int debug_code)
256 deleteSetItem (&(reg->reglives.usedpCodes),pc);
259 pcn = findNextInstruction(pc->next);
262 PCI(pcn)->label = pBranchAppend(PCI(pcn)->label,PCI(pc)->label);
267 pcn = findNextInstruction(pc->next);
270 if(PCI(pcn)->cline) {
271 //fprintf(stderr, "source line has been optimized completely out\n");
272 //pc->print(stderr,pc);
274 PCI(pcn)->cline = PCI(pc)->cline;
282 Debug stuff. Comment out the instruction we're about to delete.
288 char *pbuff,**ppbuff;
292 SAFE_snprintf(ppbuff,&size, ";%d", debug_code);
293 pCode2str(*ppbuff, size, pc);
294 pCodeInsertBefore(pc, newpCodeCharP(buff1));
295 //fprintf(stderr,"removing instruction:\n%s\n",buff1);
302 /*-----------------------------------------------------------------*
303 * void RemoveRegsFromSet(set *regset)
305 *-----------------------------------------------------------------*/
306 void RemoveRegsFromSet(set *regset)
313 regset = regset->next;
315 used = elementsInSet(reg->reglives.usedpCodes);
319 //fprintf(stderr," reg %s isfree=%d, wasused=%d\n",reg->name,reg->isFree,reg->wasUsed);
321 //fprintf(stderr," getting rid of reg %s\n",reg->name);
328 pc = setFirstItem(reg->reglives.usedpCodes);
330 if(reg->type == REG_SFR || reg->type == REG_STK || reg->isPublic || reg->isExtern) {
331 //fprintf(stderr, "not removing SFR reg %s even though used only once\n",reg->name);
338 pCode *pcn = findNextInstruction(pc->next);
340 if(pcn && PCI(pcn)->label) {
341 //fprintf(stderr,"can't delete instruction with label...\n");
342 //pc->print(stderr,pc);
345 /* Move the label to the next instruction */
347 PCI(pcn)->label = PCI(pc)->label;
352 regs *r = getRegFromInstruction(pc);
353 fprintf(stderr, "WARNING, a skip instruction is being optimized out\n");
354 pc->print(stderr,pc);
355 fprintf(stderr,"reg %s, type =%d\n",r->name, r->type);
357 //fprintf(stderr," removing reg %s because it is used only once\n",reg->name);
358 Remove1pcode(pc, reg, 1);
361 deleteSetItem (&(reg->reglives.usedpCodes),pc);
365 total_registers_saved++; // debugging stats.
373 void RegsUnMapLiveRanges(void);
374 extern pFile *the_pFile;
375 void pic14_ReMapLiveRanges(void)
378 if (!the_pFile) return;
379 RegsUnMapLiveRanges();
380 for (pb = the_pFile->pbHead; pb; pb = pb->next)
383 pCode *pc = findNextpCode(pb->pcHead, PC_FLOW);
385 pc->print( stderr, pc );
387 fprintf( stderr, "unnamed pBlock\n");
389 pc = findNextInstruction(pb->pcHead);
391 pc->print( stderr, pc );
392 pc = findNextInstruction(pc->next);;
395 pCodeRegMapLiveRanges(pb);
399 /*-----------------------------------------------------------------*
400 * void RemoveUnusedRegisters(void)
402 *-----------------------------------------------------------------*/
403 void RemoveUnusedRegisters(void)
405 /* First, get rid of registers that are used only one time */
406 pic14_ReMapLiveRanges();
408 //RemoveRegsFromSet(dynInternalRegs);
409 RemoveRegsFromSet(dynAllocRegs);
410 RemoveRegsFromSet(dynStackRegs);
412 don't do DirectRegs yet - there's a problem with arrays
413 RemoveRegsFromSet(dynDirectRegs);
415 RemoveRegsFromSet(dynDirectBitRegs);
417 if(total_registers_saved) DFPRINTF((stderr, " *** Saved %d registers ***\n", total_registers_saved));
421 /*-----------------------------------------------------------------*
423 *-----------------------------------------------------------------*/
424 static void Remove2pcodes(pCode *pcflow, pCode *pc1, pCode *pc2, regs *reg, int can_free)
426 static int debug_code=99;
430 fprintf (stderr, "%s:%d(%s): %d (reg:%s)\n", __FILE__, __LINE__, __FUNCTION__, debug_code, reg ? reg->name : "???");
431 printpCode (stderr, pc1);
432 printpCode (stderr, pc2);
435 //fprintf(stderr,"%s\n",__FUNCTION__);
437 Remove1pcode(pc1, reg, debug_code++);
440 Remove1pcode(pc2, reg, debug_code++);
441 deleteSetItem (&(PCFL(pcflow)->registers), reg);
450 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
453 /*-----------------------------------------------------------------*
455 *-----------------------------------------------------------------*/
456 int regUsedinRange(pCode *pc1, pCode *pc2, regs *reg)
462 testreg = getRegFromInstruction(pc1);
463 if(testreg && (testreg->rIdx == reg->rIdx)) {
467 fprintf(stderr, "warning, regUsedinRange searched through too many pcodes\n");
471 pc1 = findNextInstruction(pc1->next);
473 } while (pc1 && (pc1 != pc2)) ;
478 int regIsSpecial (regs *reg, int mayBeGlobal)
482 if (reg->type == REG_SFR || reg->type == REG_STK || (!mayBeGlobal && (reg->isPublic || reg->isExtern))) return 1;
488 static int regIsLocal (regs *reg)
491 /* temporaries are local */
492 if (reg->type == REG_TMP) return 1;
493 /* registers named r0x... are local */
494 if (reg->name && !strncmp(reg->name,"r0x", 3))
496 //fprintf (stderr, "reg %s is not marked REG_TMP...\n", reg->name);
504 /*-----------------------------------------------------------------*
505 * void pCodeOptime2pCodes(pCode *pc1, pCode *pc2)
507 * ADHOC pattern checking
508 * Now look for specific sequences that are easy to optimize.
509 * Many of these sequences are characteristic of the compiler
510 * (i.e. it'd probably be a waste of time to apply these adhoc
511 * checks to hand written assembly.)
514 *-----------------------------------------------------------------*/
515 int pCodeOptime2pCodes(pCode *pc1, pCode *pc2, pCode *pcfl_used, regs *reg, int can_free, int optimize_level)
520 int t = total_registers_saved;
522 if (!isPCI(pc1) || !isPCI(pc2)) return 0;
523 if (PCI(pc1)->pcflow != PCI(pc2)->pcflow) return 0;
525 if(pc2->seq < pc1->seq) {
531 /* disable this optimization for now -- it's buggy */
532 if(pic14_options.disable_df) return 0;
534 //fprintf(stderr,"pCodeOptime2pCodes\n");
535 //pc1->print(stderr,pc1);
536 //pc2->print(stderr,pc2);
538 if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_MOVFW) ){
548 can be replaced with (only if following instructions are not going to use W and reg is not used again later)
553 DFPRINTF((stderr, " optimising CLRF reg ... MOVF reg,W to ... MOVLW 0\n"));
554 pct2 = findNextInstruction(pc2->next);
556 if(pct2 && PCI(pct2)->op == POC_MOVWF) {
557 wSaved = wUsed = 1; /* Maybe able to replace with clrf pc2->next->reg. */
559 wUsed = pCodeSearchCondition(pct2,PCC_W,1) != -1;
561 regUsed = regUsedinRange(pct2,0,reg);
562 if ((regUsed&&wUsed) || (pCodeSearchCondition(pct2,PCC_Z,0) != -1)) {
563 /* Do not optimise as exisiting code is required. */
567 newpc = newpCode(POC_CLRF, PCI(pc1)->pcop);
568 } else if(wSaved && !wUsed) {
569 newpc = newpCode(POC_CLRF, PCI(pct2)->pcop);
570 pct2->destruct(pct2);
572 newpc = newpCode(POC_MOVLW, newpCodeOpLit(0));
575 pCodeInsertAfter(pc2, newpc);
576 PCI(newpc)->pcflow = PCFL(pcfl_used);
577 newpc->seq = pc2->seq;
579 //fprintf (stderr, "%s:%d(%s): Remove2pcodes (CLRF reg, ..., MOVF reg,W)\n", __FILE__, __LINE__, __FUNCTION__);
580 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
581 total_registers_saved++; // debugging stats.
583 } else if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_IORFW) ){
584 DFPRINTF((stderr, " optimising CLRF/IORFW\n"));
586 pct2 = findNextInstruction(pc2->next);
588 /* We must ensure that is destroyed before being read---IORLW must be performed unless this is proven. */
589 if(pCodeSearchCondition(pct2, PCC_Z,0) != -1) {
590 pct2 = newpCode(POC_IORLW, newpCodeOpLit(0));
591 pct2->seq = pc2->seq;
592 PCI(pct2)->pcflow = PCFL(pcfl_used);
593 pCodeInsertAfter(pc1,pct2);
595 //fprintf (stderr, "%s:%d(%s): Remove2pcodes (CLRF/IORFW)\n", __FILE__, __LINE__, __FUNCTION__);
596 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
597 total_registers_saved++; // debugging stats.
599 } else if(PCI(pc1)->op == POC_MOVWF) {
600 // Optimising MOVWF reg ...
602 pct2 = findNextInstruction(pc2->next);
604 if(PCI(pc2)->op == POC_MOVFW) {
605 // Optimising MOVWF reg ... MOVF reg,W
607 if(PCI(pct2)->op == POC_MOVWF) {
616 To: ( as long as 'stuff' does not use reg2 or if following instructions do not use W or reg is not used later)
622 reg2 = getRegFromInstruction(pct2);
623 /* Check reg2 is not used for something else before it is loaded with reg */
624 if (reg2 && !regIsSpecial (reg2, 1) && !regUsedinRange(pc1,pc2,reg2)) {
625 pCode *pct3 = findNextInstruction(pct2->next);
626 /* Check following instructions are not relying on the use of W or the Z flag condiction */
627 /* XXX: We must ensure that this value is destroyed before use---otherwise it might be used in
628 * subsequent flows (checking for < 1 is insufficient). */
629 if ((pCodeSearchCondition(pct3,PCC_Z,0) == -1) && (pCodeSearchCondition(pct3,PCC_W,0) == -1)) {
630 DFPRINTF((stderr, " optimising MOVF reg ... MOVF reg,W MOVWF reg2 to MOVWF reg2 ...\n"));
631 pct2->seq = pc1->seq;
633 pCodeInsertBefore(pc1,pct2);
634 if(regUsedinRange(pct2,0,reg))
636 //fprintf (stderr, "%s:%d(%s): Remove2pcodes IF (MOVWF reg, ..., MOVW reg,W MOVWF reg2)\n", __FILE__, __LINE__, __FUNCTION__);
637 Remove2pcodes(pcfl_used, pc2, NULL, reg, can_free);
639 //fprintf (stderr, "%s:%d(%s): Remove2pcodes ELSE (MOVWF reg, ..., MOVW reg,W MOVWF reg2)\n", __FILE__, __LINE__, __FUNCTION__);
640 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
642 total_registers_saved++; // debugging stats.
649 pct1 = findPrevInstruction(pc1->prev);
650 if(pct1 && (PCI(pct1)->pcflow == PCI(pc1)->pcflow)) {
652 if ( (PCI(pct1)->op == POC_MOVFW) &&
653 (PCI(pc2)->op == POC_MOVFW)) {
655 reg1 = getRegFromInstruction(pct1);
656 if(reg1 && !regIsSpecial (reg1, 0) && !regUsedinRange(pc1,pc2,reg1)) {
657 DFPRINTF((stderr, " optimising MOVF reg1,W MOVWF reg ... MOVF reg,W\n"));
673 Or, if we're not deleting the register then the "To" is:
680 pct2 = newpCode(PCI(pc2)->op, PCI(pct1)->pcop);
681 pCodeInsertAfter(pc2, pct2);
682 PCI(pct2)->pcflow = PCFL(pcfl_used);
683 pct2->seq = pc2->seq;
686 //fprintf (stderr, "%s:%d(%s): Remove2pcodes CANFREE (MOVF reg1,W; MOVWF reg2; MOVF reg2,W)\n", __FILE__, __LINE__, __FUNCTION__);
687 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
689 /* If we're not freeing the register then that means (probably)
690 * the register is needed somewhere else.*/
692 pCodeInsertAfter(pct2, pc1);
694 //fprintf (stderr, "%s:%d(%s): Remove2pcodes ELSE (MOVF reg1,W; MOVWF reg2; MOVF reg2,W)\n", __FILE__, __LINE__, __FUNCTION__);
695 Remove2pcodes(pcfl_used, pc2, NULL, reg, can_free);
698 //fprintf (stderr, "%s:%d(%s): Remove2pcodes ALWAYS (MOVF reg1,W; MOVWF reg2; MOVF reg2,W)\n", __FILE__, __LINE__, __FUNCTION__);
699 Remove2pcodes(pcfl_used, pct1, NULL, reg1, 0);
700 total_registers_saved++; // debugging stats.
707 return (total_registers_saved != t);
710 /*-----------------------------------------------------------------*
711 * void pCodeRegOptimeRegUsage(pBlock *pb)
712 *-----------------------------------------------------------------*/
713 void OptimizeRegUsage(set *fregs, int optimize_multi_uses, int optimize_level)
717 pCode *pc1=NULL, *pc2=NULL;
721 pCode *pcfl_used, *pcfl_assigned;
723 /* Step through the set by directly accessing the 'next' pointer.
724 * We could also step through by using the set API, but the
725 * the (debug) calls to print instructions affect the state
726 * of the set pointers */
731 if (strcmp(reg->name,"_SubState")==0)
732 fprintf(stderr,"Reg: %s\n",reg->name);
735 if(reg->type == REG_SFR || reg->type == REG_STK || reg->isPublic || reg->isExtern|| reg->isFixed) {
736 //fprintf(stderr,"skipping SFR: %s\n",reg->name);
740 pcfl_used = setFirstItem(reg->reglives.usedpFlows);
741 pcfl_assigned = setFirstItem(reg->reglives.assignedpFlows);
743 used = elementsInSet(reg->reglives.usedpCodes);
746 In this section, all registers that are used in only in two
747 instructions are examined. If possible, they're optimized out.
751 fprintf (stderr, "OptimizeRegUsage: %s addr=0x%03x rIdx=0x%03x type=%d used=%d\n",
754 reg->rIdx, reg->type, used);
756 pc1 = setFirstItem(reg->reglives.usedpCodes);
757 pc2 = setNextItem(reg->reglives.usedpCodes);
759 if(pcfl_used && pcfl_assigned) {
761 expected case - the register has been assigned a value and is
765 //fprintf(stderr," used only twice\n");
766 if(pcfl_used->seq == pcfl_assigned->seq) {
768 //fprintf(stderr, " and used in same flow\n");
770 pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 1,optimize_level);
773 // fprintf(stderr, " and used in different flows\n");
777 } else if(pcfl_used) {
779 /* register has been used twice without ever being assigned */
780 fprintf(stderr,"WARNING %s: reg %s used without being assigned\n",__FUNCTION__,reg->name);
783 //fprintf(stderr,"WARNING %s.1: reg %s assigned without being used\n",__FUNCTION__,reg->name);
784 Remove2pcodes(pcfl_assigned, pc1, pc2, reg, 1);
785 total_registers_saved++; // debugging stats.
789 /* register has been used either once, or more than twice */
791 if(used && !pcfl_used && pcfl_assigned) {
794 //fprintf(stderr,"WARNING %s.2: reg %s assigned without being used\n",__FUNCTION__,reg->name);
796 pc = setFirstItem(reg->reglives.usedpCodes);
799 pcfl_assigned = PCODE(PCI(pc)->pcflow);
800 Remove1pcode(pc, reg,2);
802 deleteSetItem (&(PCFL(pcfl_assigned)->registers), reg);
804 deleteSetItem (&(reg->reglives.usedpCodes),pc);
807 pc = setNextItem(reg->reglives.usedpCodes);
814 total_registers_saved++; // debugging stats.
815 } else if( (used > 2) && optimize_multi_uses) {
821 pCodeFlow *pcfl1=NULL, *pcfl2=NULL;
823 /* examine the number of times this register is used */
826 rset1 = reg->reglives.usedpCodes;
827 while(rset1 && searching) {
832 if(pc1 && isPCI(pc1) && ( (pcfl1 = PCI(pc1)->pcflow) != NULL) ) {
834 //while(rset2 && searching) {
838 if(pc2 && isPCI(pc2) && ( (pcfl2 = PCI(pc2)->pcflow) != NULL) ) {
841 if(pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 0,optimize_level))
846 //rset2 = rset2->next;
859 /* The following routines implement pCode optimizations based on
860 * dataflow analysis. The effects should be similar to those
861 * of pCodeOptime2pCodes() but more powerful.
863 * Unfortunately, the current approach (comparing operands by
864 * their associated registers) is seriously flawed:
865 * Some pCodeOps do not provide access to their repsective regs
866 * (PO_DIRs are created from arbitrary strings, immediates need
867 * to take offset and index into account, ...)
869 * This has to be rewritten based on pCodeOps instead of regs...
872 /* ------------------------------------------------------------------
873 Returns TRUE iff reg1 and reg2 are the same registers.
874 ------------------------------------------------------------------ */
876 static int sameRegs (const regs *reg1, const regs *reg2)
878 if (reg1 == reg2) return 1;
879 if (!reg1 || !reg2) return 0;
880 assert (reg1->name && reg2->name);
882 /* Compare names, as rIdx is not unique... */
883 if (!strcmp(reg1->name, reg2->name)) return 1;
885 /* Name mismatch -- not the same register. */
889 /* ------------------------------------------------------------------
890 Returns 1 if the register is live at pc (read in this flow),
891 returns -1 if the register is NOT live at pc (assigned a new value
892 prior to readingi the old value in this flow) or
893 return 0 if the register is not mentioned.
894 ------------------------------------------------------------------ */
896 static int checkRegInFlow (regs **reg, int *cond, pCode *pc)
898 const int verbose = 0;
899 /* find next PCI at or after pc */
900 while (pc && isPCFL(pc)) pc = pc->next;
902 assert (reg && cond);
904 /* remove pseudo flags from cond */
905 *cond &= ~(PCC_REGISTER | PCC_EXAMINE_PCOP);
909 fprintf (stderr, "Checking for reg %s, cond %x on pc ", *reg ? (*reg)->name : "<none>", *cond); pc->print (stderr, pc);
912 while (pc && !isPCFL(pc))
916 fprintf (stderr, " now checking for reg %s, cond %x on pc ", *reg ? (*reg)->name : "<none>", *cond);
917 pc->print (stderr, pc);
925 pcprev = findPrevInstruction (pc);
926 if (pcprev && isPCI_SKIP(pcprev))
929 if ((PCI(pc)->inCond | PCI(pc)->outCond) & PCC_REGISTER)
931 op = getRegFromInstruction (pc);
933 /* pCodeOpRegBits do not provide register information... */
934 //if (!op) { __asm__("int3"); pc->print (stderr, pc); }
939 return 1; /* assume `reg' is alive */
942 /* SPECIAL CASE: jump to unknown destination -- assume everything alive */
943 if (op->type == PO_PCL)
949 if (PCI(pc)->inCond & PCC_REGISTER)
951 /* `op' is live (possibly read) */
952 if (*reg && sameRegs (op, *reg))
956 fprintf (stderr, "reg is read in pc ");
957 pc->print (stderr, pc);
963 /* handle additional implicit operands */
966 case POC_CALL: /* read arguments from WREG, clobbers WREG */
971 fprintf (stderr, "conditions are read at pc ");
972 pc->print (stderr, pc);
978 case POC_RETURN: /* returns WREG to caller */
979 //fprintf (stderr, "reached RETURN, reg %s, cond %x\n", *reg ? (*reg)->name : "<none>", *cond);
984 fprintf (stderr, "conditions are read at pc ");
985 pc->print (stderr, pc);
989 /* afterwards, no condition is alive */
991 /* afterwards, all local registers are dead */
992 if (*reg && regIsLocal (*reg)) *reg = NULL;
995 case POC_RETFIE: /* this does not erturn WREG to the "caller", thus its rather a RETLW */
996 /* this discards WREG */
998 /* afterwards, no condition is alive */
1000 /* afterwards, all local registers are dead */
1001 if (*reg && regIsLocal (*reg)) *reg = NULL;
1004 /* no implicit arguments */
1008 if (PCI(pc)->inCond & (*cond))
1010 /* a condition is read */
1013 fprintf (stderr, "conditions are read at pc ");
1014 pc->print (stderr, pc);
1019 /* remove outConds from `cond' */
1020 (*cond) &= ~(PCI(pc)->outCond);
1022 if (PCI(pc)->outCond & PCC_REGISTER)
1024 /* `op' is (possibly) discarded */
1025 if (*reg && !prevIsSkip && sameRegs (op, *reg))
1029 fprintf (stderr, "reg is assigned (cont'd) at pc ");
1030 pc->print (stderr, pc);
1036 /* have all interesting conditions/registers been discarded? */
1037 if (!(*reg) && !(*cond))
1041 fprintf (stderr, "reg and conditions are discarded after ");
1042 pc->print (stderr, pc);
1051 /* no use of (or only conditional writes to) `reg' found in flow */
1054 fprintf (stderr, "analysis inconclusive: reg %s, cond %x remains\n", *reg ? "remains" : "is void", *cond);
1059 /* ------------------------------------------------------------------
1060 This will return 1 only if
1061 - reg is NULL or of type REG_TMP
1062 - reg is NULL or its value is discarded after pc
1063 - cond is 0 or all conditions are overwritten before being used
1064 ------------------------------------------------------------------ */
1072 df_state_t *df_free_states = NULL;
1075 df_newState (regs *reg, int cond, pCode *pc)
1079 if (df_free_states) {
1080 state = df_free_states;
1081 df_free_states = (df_state_t *)df_free_states->pc;
1083 state = Safe_calloc(1, sizeof(df_state_t));
1092 df_containsState (set *set, df_state_t *state)
1094 /* scan set for presence of `state' */
1096 for (curr = setFirstItem (set); curr; curr = setNextItem (set))
1098 if ((curr->pc == state->pc)
1099 && (curr->reg == state->reg)
1100 && (curr->cond == state->cond))
1110 df_releaseState (df_state_t *state)
1112 state->pc = (pCode *)df_free_states;
1113 df_free_states = (df_state_t *)state;
1122 while (df_free_states)
1124 next = (df_state_t *)df_free_states->pc;
1125 Safe_free(df_free_states);
1126 df_free_states = next;
1130 int regIsDead (regs *reg, int cond, pCode *pc)
1132 set *seenStates = NULL;
1139 if (reg && !regIsLocal (reg)) return 0;
1141 pc = findNextInstruction (pc->next);
1143 addSet (&todo, df_newState(reg, cond, pc));
1145 while ((result == 1) && (state = getSet (&todo)))
1149 if (df_containsState (seenStates, state)) continue;
1150 addSet (&seenStates, state);
1156 //fprintf (stderr, "Checking for reg %s/cond %x at pc ", reg ? reg->name : "<none>", cond);
1157 //curr->print (stderr, curr);
1159 res = checkRegInFlow (®, &cond, curr);
1162 case 1: /* `reg' or `cond' is read---not dead */
1165 case -1: /* `reg' and `cond' are discarded in this flow---need to check other open flows */
1167 default: /* `reg' is not read and (possibly) not assigned---check successor flows */
1170 pCodeFlow *pcfl = PCI(curr)->pcflow;
1171 pCodeFlowLink *link;
1175 for (link = setFirstItem(pcfl->to); link; link = setNextItem (pcfl->to))
1177 /* add the first pCodeInstruction in the new flow to `todo' */
1178 first = findNextInstruction (&link->pcflow->pc);
1179 if (first) addSet (&todo, df_newState (reg, cond, first));
1187 while (NULL != (state = getSet (&todo))) { df_releaseState (state); }
1188 while (NULL != (state = getSet (&seenStates))) { df_releaseState (state); }
1190 /* if result remained 1, `reg' is not even possibly read and thus dead */
1196 /* ------------------------------------------------------------------
1197 Safely remove a pCode.
1198 This needs to check that the previous instruction was no SKIP
1199 (otherwise the SKIP instruction would have to be removed as well,
1200 which may not be done for SFRs (side-effects on read possible)).
1201 ------------------------------------------------------------------ */
1203 extern void unBuildFlow (pBlock *pb);
1204 extern void RegsUnMapLiveRanges ();
1205 extern void BuildFlow (pBlock *pb);
1206 extern void LinkFlow (pBlock *pb);
1207 extern void BuildFlowTree (pBlock *pb);
1208 extern void pCodeRegMapLiveRanges (pBlock *pb);
1209 extern pFile *the_pFile;
1211 static int pCodeRemove (pCode *pc, const char *comment)
1213 pCode *pcprev, *pcnext;
1214 unsigned int result = 0;
1216 /* Sanity checks. */
1218 if (!isPCI(pc)) return 0;
1220 pcprev = findPrevInstruction (pc->prev);
1221 if (pcprev && isPCI_SKIP(pcprev))
1223 /* bail out until we know how to fix the Flow... */
1226 /* we also need to remove the preceeding SKIP instruction(s) */
1227 result = pCodeRemove (pcprev, "=DF= removing preceeding SKIP as well");
1230 /* previous instruction could not be removed -- this cannot be removed as well */
1233 /* FIXME: We now have to update the flow! */
1236 /* do not remove pCodes with SFRs as operands (even reading them might cause side effects) */
1239 reg = getRegFromInstruction (pc);
1240 /* accesses to the STATUS register aer always safe, but others... */
1241 if (reg && reg->type == REG_SFR && reg->pc_type != PO_STATUS) return result;
1244 /* MUST SUCEED FROM NOW ON (or revert the changes done since NOW ;-)) */
1247 if (PCI(pc)->pcflow && PCI(pc)->pcflow->end == pc)
1250 pcprev = findPrevInstruction (pc->prev);
1251 if (PCI(pcprev)->pcflow == PCI(pc)->pcflow)
1253 PCI(pc)->pcflow->end = pcprev;
1255 pBlock *pb = pc->pb;
1256 RegsUnMapLiveRanges();
1261 for (pb = the_pFile->pbHead; pb; pb = pb->next)
1263 pCodeRegMapLiveRanges(pb);
1268 /* attach labels to next instruction */
1269 pcnext = findNextInstruction (pc->next);
1272 PCI(pcnext)->label = pBranchAppend (PCI(pcnext)->label, PCI(pc)->label);
1273 if (!PCI(pcnext)->cline) PCI(pcnext)->cline = PCI(pc)->cline;
1277 fprintf (stderr, "Cannot move a label...\n");
1285 char *pbuff = &buffer[0];
1287 SAFE_snprintf (&pbuff, &size, "; %s:%u(%s): %s", __FILE__, __LINE__, __FUNCTION__, comment);
1288 pCodeInsertAfter(pc->prev, newpCodeCharP (&buffer[0]));
1293 /* replace removed pCode with out-commented version of itself */
1296 char *pbuff = &buffer[0];
1298 SAFE_snprintf (&pbuff, &size, "; %s:%u(%s): ", __FILE__, __LINE__, __FUNCTION__);
1299 pCode2str (pbuff, size, pc);
1300 pCodeInsertAfter(pc->prev, newpCodeCharP (&buffer[0]));
1307 /* ------------------------------------------------------------------
1308 Find and remove dead pCodes.
1309 ------------------------------------------------------------------ */
1311 static int removeIfDeadPCI (pCode *pc)
1313 pCode *pcnext = NULL;
1315 unsigned int outCond;
1316 unsigned int result = 0;
1323 pcnext = findNextInstruction (pc->next);
1324 if (!isPCI(pc)) return 0;
1326 switch (PCI(pc)->op)
1382 /* do not remove unknown PCIs */
1386 /* redundant checks---those instructions may never be removed */
1387 if (isPCI_BRANCH(pc)) return 0;
1388 if (isPCI_SKIP(pc)) return 0;
1390 outCond = PCI(pc)->outCond;
1393 /* unknown operands assigned to, then ignore */
1394 if ((outCond & (PCC_REGISTER | PCC_C | PCC_Z | PCC_DC | PCC_W)) != outCond)
1397 if (outCond & PCC_REGISTER)
1399 dst = getRegFromInstruction (pc);
1403 if (!regIsLocal (dst)) return 0;
1404 if (regIsSpecial (dst,0)) return 0;
1407 //fprintf (stderr, "--> checking for liveness pc "); pc->print (stderr, pc);
1408 if (regIsDead (dst, outCond, pc))
1410 /* no result from pc has been used -- pc is `dead' */
1411 //fprintf (stderr, "--> reg %s and cond %x assumed unused\n", dst ? dst->name : "<none>", outCond);
1412 //fprintf (stderr, "--> removing dead pc "); pc->print (stderr, pc);
1413 result = pCodeRemove (pc, "=DF= removed dead pCode");
1419 /* ------------------------------------------------------------------
1420 This routine is intended to safely replace one pCodeInstruction
1421 with a different pCodeInstruction.
1422 If desired, the replaced pCode will be left in (commented out) for
1424 Further, an optional comment can be inserted to indicate the
1425 reason for the possible removal of the pCode.
1426 ------------------------------------------------------------------ */
1428 static void replace_PCI (pCodeInstruction *pc, pCodeInstruction *newpc, char *comment)
1430 newpc->from = pBranchAppend (newpc->from, pc->from);
1431 newpc->to = pBranchAppend (newpc->to, pc->to);
1432 newpc->label = pBranchAppend (newpc->label, pc->label);
1433 //newpc->pcflow = pc->pcflow; // updated in pCodeInsertAfter, ->pb is as well
1434 newpc->cline = pc->cline;
1436 newpc->pc.seq = pc->pc.seq;
1438 pCodeInsertAfter (&pc->pc, &newpc->pc);
1440 /* FIXME: replacing pc will break the liverange maps (usedpCodes, ...) */
1441 pCodeRegMapLiveRanges( pc->pBlock ); /*FIXME:UNTESTED*/
1445 pCodeInsertAfter (&pc->pc, newpCodeCharP (comment));
1450 /* replace pc with commented out version of itself */
1451 char buffer[1024], buffer2[1024];
1452 char *pbuff = &buffer[0];
1454 pCode2str (&buffer2[0],1024,&pc->pc);
1455 SAFE_snprintf (&pbuff,&size,"%s:%u(%s): removed pCode was %s\t", __FILE__, __LINE__, __FUNCTION__, &buffer2[0]);
1456 pCodeInsertAfter (&pc->pc, newpCodeCharP (&buffer[0]));
1459 pc->pc.destruct (&pc->pc);
1462 /* ------------------------------------------------------------------
1463 Find the first (unique) assignment to `reg' (prior to pc).
1464 ------------------------------------------------------------------ */
1466 pCode *findAssignmentToReg (regs *reg, pCode *pc)
1470 assert (pc && isPCI(pc) && reg);
1472 curr = findPrevInstruction (pc->prev);
1474 while (curr && PCI(curr)->pcflow == PCI(pc)->pcflow)
1476 if (PCI(curr)->outCond & PCC_REGISTER)
1478 regs *op = getRegFromInstruction (curr);
1479 if (op && (sameRegs(op,reg)))
1482 curr = findPrevInstruction (curr->prev);
1485 /* no assignment to reg found */
1489 /* ------------------------------------------------------------------
1490 Find a register that holds the same value as `reg' (an alias).
1491 ------------------------------------------------------------------ */
1493 regs *findRegisterAlias (regs *reg, pCode *pc)
1497 if(!reg) return NULL;
1499 if (regIsSpecial (reg, 0)) return NULL;
1501 curr = findAssignmentToReg (reg, pc);
1503 /* no assignment found --> no alias found */
1504 if (!curr) return NULL;
1506 switch (PCI(curr)->op)
1509 /* find previous assignment to WREG */
1510 while (curr && !(PCI(curr)->outCond & PCC_W))
1511 curr = findPrevInstruction (curr->prev);
1512 if (curr && PCI(curr)->op == POC_MOVFW)
1514 regs *op = getRegFromInstruction (curr);
1515 /* alias must not be changed since assignment... */
1516 if (PCI(curr)->pcop)
1518 switch (PCI(curr)->pcop->type)
1520 case PO_GPR_REGISTER:
1522 /* these operands are ok */
1525 /* not a plain register operand */
1530 if (!op || regIsSpecial (op, 0) || !regIsUnchangedSince (op, pc, curr)) return NULL;
1531 //fprintf (stderr, "found register alias for %s: %s\n", reg->name, op && op->name ? op->name : "<no name>");
1534 /* unknown source to WREG -- unknown register alias */
1540 /* unhandled instruction -- assume unknown source, no alias */
1544 /* no alias found */
1548 /* ------------------------------------------------------------------
1549 Analyze a single pCodeInstruction's dataflow relations and replace
1550 it with a better variant if possible.
1551 ------------------------------------------------------------------ */
1553 void analyzeAndReplacePCI (pCodeInstruction *pci)
1555 regs *op_reg, *alias_reg;
1559 if (!isPCI(pci)) return;
1568 /* try to find a different source register */
1569 op_reg = getRegFromInstruction (&pci->pc);
1570 if (pci->op == POC_MOVFW) /* touches Z */
1572 pCode *assignment = findAssignmentToReg (op_reg, &pci->pc);
1573 if (assignment && isPCI(assignment) && (PCI(assignment)->op == POC_CLRF))
1575 replace_PCI (pci, PCI(newpCode(POC_MOVLW, newpCodeOpLit(0))), "replaced with CLRF");
1580 alias_reg = findRegisterAlias (op_reg, &pci->pc);
1583 replace_PCI (pci, PCI(newpCode(pci->op, newpCodeOpRegFromStr (alias_reg->name))), "=DF= replaced with move from register alias");
1588 /* do not optimize */
1593 extern pFile *the_pFile;
1595 /* ------------------------------------------------------------------
1596 Find and remove dead pCodes.
1597 ------------------------------------------------------------------ */
1599 static int removeDeadPCIs (void)
1602 unsigned int removed = 0;
1604 if (!the_pFile) return removed;
1609 /* iterate over all pBlocks */
1610 for (pb = the_pFile->pbHead; pb; pb = pb->next)
1612 pCode *pc, *pcnext = NULL;
1614 /* iterate over all pCodes */
1615 for (pc = findNextInstruction (pb->pcHead); pc; pc = pcnext)
1617 pcnext = findNextInstruction (pc->next);
1618 removed += removeIfDeadPCI (pc);
1622 fprintf (stderr, "[removed %u dead pCodes]\n", removed);
1628 /* ------------------------------------------------------------------
1629 This routine tries to optimize the dataflow by...
1632 This routine leaves in dead pCodes (assignments whose results are
1633 not used) -- these should be removed in a following sweep phase.
1634 ------------------------------------------------------------------ */
1636 void optimizeDataflow (void)
1640 if (!the_pFile) return;
1642 //fprintf (stderr, "%s:%u(%s): Starting optimization...\n", __FILE__, __LINE__, __FUNCTION__);
1644 /* iterate over all pBlocks */
1645 for (pb = the_pFile->pbHead; pb; pb = pb->next)
1647 pCode *pc, *pcnext = NULL;
1649 /* iterate over all pCodes */
1650 for (pc = findNextInstruction (pb->pcHead); pc; pc = pcnext)
1652 pcnext = findNextInstruction (pc->next);
1653 analyzeAndReplacePCI (PCI(pc));
1657 while (removeDeadPCIs ()) { /* remove dead codes in multiple passes */};
1663 /*-----------------------------------------------------------------*
1664 * void pCodeRegOptimeRegUsage(pBlock *pb)
1665 *-----------------------------------------------------------------*/
1666 void pCodeRegOptimizeRegUsage(int level)
1671 int t = total_registers_saved;
1674 /* This is currently broken (need rewrite to correctly
1675 * hamdle arbitrary pCodeOps instead of registers only). */
1676 if (!pic14_options.disable_df)
1677 optimizeDataflow ();
1680 if(!register_optimization)
1682 #define OPT_PASSES 4
1683 passes = OPT_PASSES;
1686 saved = total_registers_saved;
1688 /* Identify registers used in one flow sequence */
1689 OptimizeRegUsage(dynAllocRegs,level, (OPT_PASSES-passes));
1690 OptimizeRegUsage(dynStackRegs,level, (OPT_PASSES-passes));
1691 OptimizeRegUsage(dynDirectRegs,0, (OPT_PASSES-passes));
1693 if(total_registers_saved != saved)
1694 DFPRINTF((stderr, " *** pass %d, Saved %d registers, total saved %d ***\n",
1695 (1+OPT_PASSES-passes),total_registers_saved-saved,total_registers_saved));
1699 } while( passes && ((total_registers_saved != saved) || (passes==OPT_PASSES-1)) );
1701 if(total_registers_saved == t)
1702 DFPRINTF((stderr, "No registers saved on this pass\n"));
1706 fprintf(stderr,"dynamically allocated regs:\n");
1707 dbg_regusage(dynAllocRegs);
1708 fprintf(stderr,"stack regs:\n");
1709 dbg_regusage(dynStackRegs);
1710 fprintf(stderr,"direct regs:\n");
1711 dbg_regusage(dynDirectRegs);
1716 /*-----------------------------------------------------------------*
1717 * void RegsUnMapLiveRanges(set *regset)
1719 *-----------------------------------------------------------------*/
1720 void RegsSetUnMapLiveRanges(set *regset)
1726 regset = regset->next;
1729 deleteSet(®->reglives.usedpCodes);
1730 deleteSet(®->reglives.usedpFlows);
1731 deleteSet(®->reglives.assignedpFlows);
1737 void RegsUnMapLiveRanges(void)
1740 RegsSetUnMapLiveRanges(dynAllocRegs);
1741 RegsSetUnMapLiveRanges(dynStackRegs);
1742 RegsSetUnMapLiveRanges(dynDirectRegs);
1743 RegsSetUnMapLiveRanges(dynProcessorRegs);
1744 RegsSetUnMapLiveRanges(dynDirectBitRegs);
1745 RegsSetUnMapLiveRanges(dynInternalRegs);