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 /* Catch inconsistently set-up live ranges
736 * (see tracker items #1469504 + #1474602)
737 * FIXME: Actually we should rather fix the
738 * computation of the liveranges instead...
740 if (!reg || !reg->reglives.usedpFlows
741 || !reg->reglives.assignedpFlows)
743 //fprintf( stderr, "skipping reg w/o liveranges: %s\n", reg ? reg->name : "(unknown)");
747 if(reg->type == REG_SFR || reg->type == REG_STK || reg->isPublic || reg->isExtern|| reg->isFixed) {
748 //fprintf(stderr,"skipping SFR: %s\n",reg->name);
752 pcfl_used = setFirstItem(reg->reglives.usedpFlows);
753 pcfl_assigned = setFirstItem(reg->reglives.assignedpFlows);
755 used = elementsInSet(reg->reglives.usedpCodes);
758 In this section, all registers that are used in only in two
759 instructions are examined. If possible, they're optimized out.
763 fprintf (stderr, "OptimizeRegUsage: %s addr=0x%03x rIdx=0x%03x type=%d used=%d\n",
766 reg->rIdx, reg->type, used);
768 pc1 = setFirstItem(reg->reglives.usedpCodes);
769 pc2 = setNextItem(reg->reglives.usedpCodes);
771 if(pcfl_used && pcfl_assigned) {
773 expected case - the register has been assigned a value and is
777 //fprintf(stderr," used only twice\n");
778 if(pcfl_used->seq == pcfl_assigned->seq) {
780 //fprintf(stderr, " and used in same flow\n");
782 pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 1,optimize_level);
785 // fprintf(stderr, " and used in different flows\n");
789 } else if(pcfl_used) {
791 /* register has been used twice without ever being assigned */
792 fprintf(stderr,"WARNING %s: reg %s used without being assigned\n",__FUNCTION__,reg->name);
795 //fprintf(stderr,"WARNING %s.1: reg %s assigned without being used\n",__FUNCTION__,reg->name);
796 Remove2pcodes(pcfl_assigned, pc1, pc2, reg, 1);
797 total_registers_saved++; // debugging stats.
801 /* register has been used either once, or more than twice */
803 if(used && !pcfl_used && pcfl_assigned) {
806 //fprintf(stderr,"WARNING %s.2: reg %s assigned without being used\n",__FUNCTION__,reg->name);
808 pc = setFirstItem(reg->reglives.usedpCodes);
811 pcfl_assigned = PCODE(PCI(pc)->pcflow);
812 Remove1pcode(pc, reg,2);
814 deleteSetItem (&(PCFL(pcfl_assigned)->registers), reg);
816 deleteSetItem (&(reg->reglives.usedpCodes),pc);
819 pc = setNextItem(reg->reglives.usedpCodes);
826 total_registers_saved++; // debugging stats.
827 } else if( (used > 2) && optimize_multi_uses) {
833 pCodeFlow *pcfl1=NULL, *pcfl2=NULL;
835 /* examine the number of times this register is used */
838 rset1 = reg->reglives.usedpCodes;
839 while(rset1 && searching) {
844 if(pc1 && isPCI(pc1) && ( (pcfl1 = PCI(pc1)->pcflow) != NULL) ) {
846 //while(rset2 && searching) {
850 if(pc2 && isPCI(pc2) && ( (pcfl2 = PCI(pc2)->pcflow) != NULL) ) {
853 if(pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 0,optimize_level))
858 //rset2 = rset2->next;
871 /* The following routines implement pCode optimizations based on
872 * dataflow analysis. The effects should be similar to those
873 * of pCodeOptime2pCodes() but more powerful.
875 * Unfortunately, the current approach (comparing operands by
876 * their associated registers) is seriously flawed:
877 * Some pCodeOps do not provide access to their repsective regs
878 * (PO_DIRs are created from arbitrary strings, immediates need
879 * to take offset and index into account, ...)
881 * This has to be rewritten based on pCodeOps instead of regs...
884 /* ------------------------------------------------------------------
885 Returns TRUE iff reg1 and reg2 are the same registers.
886 ------------------------------------------------------------------ */
888 static int sameRegs (const regs *reg1, const regs *reg2)
890 if (reg1 == reg2) return 1;
891 if (!reg1 || !reg2) return 0;
892 assert (reg1->name && reg2->name);
894 /* Compare names, as rIdx is not unique... */
895 if (!strcmp(reg1->name, reg2->name)) return 1;
897 /* Name mismatch -- not the same register. */
901 /* ------------------------------------------------------------------
902 Returns 1 if the register is live at pc (read in this flow),
903 returns -1 if the register is NOT live at pc (assigned a new value
904 prior to readingi the old value in this flow) or
905 return 0 if the register is not mentioned.
906 ------------------------------------------------------------------ */
908 static int checkRegInFlow (regs **reg, int *cond, pCode *pc)
910 const int verbose = 0;
911 /* find next PCI at or after pc */
912 while (pc && isPCFL(pc)) pc = pc->next;
914 assert (reg && cond);
916 /* remove pseudo flags from cond */
917 *cond &= ~(PCC_REGISTER | PCC_EXAMINE_PCOP);
921 fprintf (stderr, "Checking for reg %s, cond %x on pc ", *reg ? (*reg)->name : "<none>", *cond); pc->print (stderr, pc);
924 while (pc && !isPCFL(pc))
928 fprintf (stderr, " now checking for reg %s, cond %x on pc ", *reg ? (*reg)->name : "<none>", *cond);
929 pc->print (stderr, pc);
937 pcprev = findPrevInstruction (pc);
938 if (pcprev && isPCI_SKIP(pcprev))
941 if ((PCI(pc)->inCond | PCI(pc)->outCond) & PCC_REGISTER)
943 op = getRegFromInstruction (pc);
945 /* pCodeOpRegBits do not provide register information... */
946 //if (!op) { __asm__("int3"); pc->print (stderr, pc); }
951 return 1; /* assume `reg' is alive */
954 /* SPECIAL CASE: jump to unknown destination -- assume everything alive */
955 if (op->type == PO_PCL)
961 if (PCI(pc)->inCond & PCC_REGISTER)
963 /* `op' is live (possibly read) */
964 if (*reg && sameRegs (op, *reg))
968 fprintf (stderr, "reg is read in pc ");
969 pc->print (stderr, pc);
975 /* handle additional implicit operands */
978 case POC_CALL: /* read arguments from WREG, clobbers WREG */
983 fprintf (stderr, "conditions are read at pc ");
984 pc->print (stderr, pc);
990 case POC_RETURN: /* returns WREG to caller */
991 //fprintf (stderr, "reached RETURN, reg %s, cond %x\n", *reg ? (*reg)->name : "<none>", *cond);
996 fprintf (stderr, "conditions are read at pc ");
997 pc->print (stderr, pc);
1001 /* afterwards, no condition is alive */
1003 /* afterwards, all local registers are dead */
1004 if (*reg && regIsLocal (*reg)) *reg = NULL;
1007 case POC_RETFIE: /* this does not erturn WREG to the "caller", thus its rather a RETLW */
1008 /* this discards WREG */
1010 /* afterwards, no condition is alive */
1012 /* afterwards, all local registers are dead */
1013 if (*reg && regIsLocal (*reg)) *reg = NULL;
1016 /* no implicit arguments */
1020 if (PCI(pc)->inCond & (*cond))
1022 /* a condition is read */
1025 fprintf (stderr, "conditions are read at pc ");
1026 pc->print (stderr, pc);
1031 /* remove outConds from `cond' */
1032 (*cond) &= ~(PCI(pc)->outCond);
1034 if (PCI(pc)->outCond & PCC_REGISTER)
1036 /* `op' is (possibly) discarded */
1037 if (*reg && !prevIsSkip && sameRegs (op, *reg))
1041 fprintf (stderr, "reg is assigned (cont'd) at pc ");
1042 pc->print (stderr, pc);
1048 /* have all interesting conditions/registers been discarded? */
1049 if (!(*reg) && !(*cond))
1053 fprintf (stderr, "reg and conditions are discarded after ");
1054 pc->print (stderr, pc);
1063 /* no use of (or only conditional writes to) `reg' found in flow */
1066 fprintf (stderr, "analysis inconclusive: reg %s, cond %x remains\n", *reg ? "remains" : "is void", *cond);
1071 /* ------------------------------------------------------------------
1072 This will return 1 only if
1073 - reg is NULL or of type REG_TMP
1074 - reg is NULL or its value is discarded after pc
1075 - cond is 0 or all conditions are overwritten before being used
1076 ------------------------------------------------------------------ */
1084 df_state_t *df_free_states = NULL;
1087 df_newState (regs *reg, int cond, pCode *pc)
1091 if (df_free_states) {
1092 state = df_free_states;
1093 df_free_states = (df_state_t *)df_free_states->pc;
1095 state = Safe_calloc(1, sizeof(df_state_t));
1104 df_containsState (set *set, df_state_t *state)
1106 /* scan set for presence of `state' */
1108 for (curr = setFirstItem (set); curr; curr = setNextItem (set))
1110 if ((curr->pc == state->pc)
1111 && (curr->reg == state->reg)
1112 && (curr->cond == state->cond))
1122 df_releaseState (df_state_t *state)
1124 state->pc = (pCode *)df_free_states;
1125 df_free_states = (df_state_t *)state;
1134 while (df_free_states)
1136 next = (df_state_t *)df_free_states->pc;
1137 Safe_free(df_free_states);
1138 df_free_states = next;
1142 int regIsDead (regs *reg, int cond, pCode *pc)
1144 set *seenStates = NULL;
1151 if (reg && !regIsLocal (reg)) return 0;
1153 pc = findNextInstruction (pc->next);
1155 addSet (&todo, df_newState(reg, cond, pc));
1157 while ((result == 1) && (state = getSet (&todo)))
1161 if (df_containsState (seenStates, state)) continue;
1162 addSet (&seenStates, state);
1168 //fprintf (stderr, "Checking for reg %s/cond %x at pc ", reg ? reg->name : "<none>", cond);
1169 //curr->print (stderr, curr);
1171 res = checkRegInFlow (®, &cond, curr);
1174 case 1: /* `reg' or `cond' is read---not dead */
1177 case -1: /* `reg' and `cond' are discarded in this flow---need to check other open flows */
1179 default: /* `reg' is not read and (possibly) not assigned---check successor flows */
1182 pCodeFlow *pcfl = PCI(curr)->pcflow;
1183 pCodeFlowLink *link;
1187 for (link = setFirstItem(pcfl->to); link; link = setNextItem (pcfl->to))
1189 /* add the first pCodeInstruction in the new flow to `todo' */
1190 first = findNextInstruction (&link->pcflow->pc);
1191 if (first) addSet (&todo, df_newState (reg, cond, first));
1199 while (NULL != (state = getSet (&todo))) { df_releaseState (state); }
1200 while (NULL != (state = getSet (&seenStates))) { df_releaseState (state); }
1202 /* if result remained 1, `reg' is not even possibly read and thus dead */
1208 /* ------------------------------------------------------------------
1209 Safely remove a pCode.
1210 This needs to check that the previous instruction was no SKIP
1211 (otherwise the SKIP instruction would have to be removed as well,
1212 which may not be done for SFRs (side-effects on read possible)).
1213 ------------------------------------------------------------------ */
1215 extern void unBuildFlow (pBlock *pb);
1216 extern void RegsUnMapLiveRanges ();
1217 extern void BuildFlow (pBlock *pb);
1218 extern void LinkFlow (pBlock *pb);
1219 extern void BuildFlowTree (pBlock *pb);
1220 extern void pCodeRegMapLiveRanges (pBlock *pb);
1221 extern pFile *the_pFile;
1223 static int pCodeRemove (pCode *pc, const char *comment)
1225 pCode *pcprev, *pcnext;
1226 unsigned int result = 0;
1228 /* Sanity checks. */
1230 if (!isPCI(pc)) return 0;
1232 pcprev = findPrevInstruction (pc->prev);
1233 if (pcprev && isPCI_SKIP(pcprev))
1235 /* bail out until we know how to fix the Flow... */
1238 /* we also need to remove the preceeding SKIP instruction(s) */
1239 result = pCodeRemove (pcprev, "=DF= removing preceeding SKIP as well");
1242 /* previous instruction could not be removed -- this cannot be removed as well */
1245 /* FIXME: We now have to update the flow! */
1248 /* do not remove pCodes with SFRs as operands (even reading them might cause side effects) */
1251 reg = getRegFromInstruction (pc);
1252 /* accesses to the STATUS register aer always safe, but others... */
1253 if (reg && reg->type == REG_SFR && reg->pc_type != PO_STATUS) return result;
1256 /* MUST SUCEED FROM NOW ON (or revert the changes done since NOW ;-)) */
1259 if (PCI(pc)->pcflow && PCI(pc)->pcflow->end == pc)
1262 pcprev = findPrevInstruction (pc->prev);
1263 if (PCI(pcprev)->pcflow == PCI(pc)->pcflow)
1265 PCI(pc)->pcflow->end = pcprev;
1267 pBlock *pb = pc->pb;
1268 RegsUnMapLiveRanges();
1273 for (pb = the_pFile->pbHead; pb; pb = pb->next)
1275 pCodeRegMapLiveRanges(pb);
1280 /* attach labels to next instruction */
1281 pcnext = findNextInstruction (pc->next);
1284 PCI(pcnext)->label = pBranchAppend (PCI(pcnext)->label, PCI(pc)->label);
1285 if (!PCI(pcnext)->cline) PCI(pcnext)->cline = PCI(pc)->cline;
1289 fprintf (stderr, "Cannot move a label...\n");
1297 char *pbuff = &buffer[0];
1299 SAFE_snprintf (&pbuff, &size, "; %s:%u(%s): %s", __FILE__, __LINE__, __FUNCTION__, comment);
1300 pCodeInsertAfter(pc->prev, newpCodeCharP (&buffer[0]));
1305 /* replace removed pCode with out-commented version of itself */
1308 char *pbuff = &buffer[0];
1310 SAFE_snprintf (&pbuff, &size, "; %s:%u(%s): ", __FILE__, __LINE__, __FUNCTION__);
1311 pCode2str (pbuff, size, pc);
1312 pCodeInsertAfter(pc->prev, newpCodeCharP (&buffer[0]));
1319 /* ------------------------------------------------------------------
1320 Find and remove dead pCodes.
1321 ------------------------------------------------------------------ */
1323 static int removeIfDeadPCI (pCode *pc)
1325 pCode *pcnext = NULL;
1327 unsigned int outCond;
1328 unsigned int result = 0;
1335 pcnext = findNextInstruction (pc->next);
1336 if (!isPCI(pc)) return 0;
1338 switch (PCI(pc)->op)
1394 /* do not remove unknown PCIs */
1398 /* redundant checks---those instructions may never be removed */
1399 if (isPCI_BRANCH(pc)) return 0;
1400 if (isPCI_SKIP(pc)) return 0;
1402 outCond = PCI(pc)->outCond;
1405 /* unknown operands assigned to, then ignore */
1406 if ((outCond & (PCC_REGISTER | PCC_C | PCC_Z | PCC_DC | PCC_W)) != outCond)
1409 if (outCond & PCC_REGISTER)
1411 dst = getRegFromInstruction (pc);
1415 if (!regIsLocal (dst)) return 0;
1416 if (regIsSpecial (dst,0)) return 0;
1419 //fprintf (stderr, "--> checking for liveness pc "); pc->print (stderr, pc);
1420 if (regIsDead (dst, outCond, pc))
1422 /* no result from pc has been used -- pc is `dead' */
1423 //fprintf (stderr, "--> reg %s and cond %x assumed unused\n", dst ? dst->name : "<none>", outCond);
1424 //fprintf (stderr, "--> removing dead pc "); pc->print (stderr, pc);
1425 result = pCodeRemove (pc, "=DF= removed dead pCode");
1431 /* ------------------------------------------------------------------
1432 This routine is intended to safely replace one pCodeInstruction
1433 with a different pCodeInstruction.
1434 If desired, the replaced pCode will be left in (commented out) for
1436 Further, an optional comment can be inserted to indicate the
1437 reason for the possible removal of the pCode.
1438 ------------------------------------------------------------------ */
1440 static void replace_PCI (pCodeInstruction *pc, pCodeInstruction *newpc, char *comment)
1442 newpc->from = pBranchAppend (newpc->from, pc->from);
1443 newpc->to = pBranchAppend (newpc->to, pc->to);
1444 newpc->label = pBranchAppend (newpc->label, pc->label);
1445 //newpc->pcflow = pc->pcflow; // updated in pCodeInsertAfter, ->pb is as well
1446 newpc->cline = pc->cline;
1448 newpc->pc.seq = pc->pc.seq;
1450 pCodeInsertAfter (&pc->pc, &newpc->pc);
1452 /* FIXME: replacing pc will break the liverange maps (usedpCodes, ...) */
1453 pCodeRegMapLiveRanges( pc->pBlock ); /*FIXME:UNTESTED*/
1457 pCodeInsertAfter (&pc->pc, newpCodeCharP (comment));
1462 /* replace pc with commented out version of itself */
1463 char buffer[1024], buffer2[1024];
1464 char *pbuff = &buffer[0];
1466 pCode2str (&buffer2[0],1024,&pc->pc);
1467 SAFE_snprintf (&pbuff,&size,"%s:%u(%s): removed pCode was %s\t", __FILE__, __LINE__, __FUNCTION__, &buffer2[0]);
1468 pCodeInsertAfter (&pc->pc, newpCodeCharP (&buffer[0]));
1471 pc->pc.destruct (&pc->pc);
1474 /* ------------------------------------------------------------------
1475 Find the first (unique) assignment to `reg' (prior to pc).
1476 ------------------------------------------------------------------ */
1478 pCode *findAssignmentToReg (regs *reg, pCode *pc)
1482 assert (pc && isPCI(pc) && reg);
1484 curr = findPrevInstruction (pc->prev);
1486 while (curr && PCI(curr)->pcflow == PCI(pc)->pcflow)
1488 if (PCI(curr)->outCond & PCC_REGISTER)
1490 regs *op = getRegFromInstruction (curr);
1491 if (op && (sameRegs(op,reg)))
1494 curr = findPrevInstruction (curr->prev);
1497 /* no assignment to reg found */
1501 /* ------------------------------------------------------------------
1502 Find a register that holds the same value as `reg' (an alias).
1503 ------------------------------------------------------------------ */
1505 regs *findRegisterAlias (regs *reg, pCode *pc)
1509 if(!reg) return NULL;
1511 if (regIsSpecial (reg, 0)) return NULL;
1513 curr = findAssignmentToReg (reg, pc);
1515 /* no assignment found --> no alias found */
1516 if (!curr) return NULL;
1518 switch (PCI(curr)->op)
1521 /* find previous assignment to WREG */
1522 while (curr && !(PCI(curr)->outCond & PCC_W))
1523 curr = findPrevInstruction (curr->prev);
1524 if (curr && PCI(curr)->op == POC_MOVFW)
1526 regs *op = getRegFromInstruction (curr);
1527 /* alias must not be changed since assignment... */
1528 if (PCI(curr)->pcop)
1530 switch (PCI(curr)->pcop->type)
1532 case PO_GPR_REGISTER:
1534 /* these operands are ok */
1537 /* not a plain register operand */
1542 if (!op || regIsSpecial (op, 0) || !regIsUnchangedSince (op, pc, curr)) return NULL;
1543 //fprintf (stderr, "found register alias for %s: %s\n", reg->name, op && op->name ? op->name : "<no name>");
1546 /* unknown source to WREG -- unknown register alias */
1552 /* unhandled instruction -- assume unknown source, no alias */
1556 /* no alias found */
1560 /* ------------------------------------------------------------------
1561 Analyze a single pCodeInstruction's dataflow relations and replace
1562 it with a better variant if possible.
1563 ------------------------------------------------------------------ */
1565 void analyzeAndReplacePCI (pCodeInstruction *pci)
1567 regs *op_reg, *alias_reg;
1571 if (!isPCI(pci)) return;
1580 /* try to find a different source register */
1581 op_reg = getRegFromInstruction (&pci->pc);
1582 if (pci->op == POC_MOVFW) /* touches Z */
1584 pCode *assignment = findAssignmentToReg (op_reg, &pci->pc);
1585 if (assignment && isPCI(assignment) && (PCI(assignment)->op == POC_CLRF))
1587 replace_PCI (pci, PCI(newpCode(POC_MOVLW, newpCodeOpLit(0))), "replaced with CLRF");
1592 alias_reg = findRegisterAlias (op_reg, &pci->pc);
1595 replace_PCI (pci, PCI(newpCode(pci->op, newpCodeOpRegFromStr (alias_reg->name))), "=DF= replaced with move from register alias");
1600 /* do not optimize */
1605 extern pFile *the_pFile;
1607 /* ------------------------------------------------------------------
1608 Find and remove dead pCodes.
1609 ------------------------------------------------------------------ */
1611 static int removeDeadPCIs (void)
1614 unsigned int removed = 0;
1616 if (!the_pFile) return removed;
1621 /* iterate over all pBlocks */
1622 for (pb = the_pFile->pbHead; pb; pb = pb->next)
1624 pCode *pc, *pcnext = NULL;
1626 /* iterate over all pCodes */
1627 for (pc = findNextInstruction (pb->pcHead); pc; pc = pcnext)
1629 pcnext = findNextInstruction (pc->next);
1630 removed += removeIfDeadPCI (pc);
1634 fprintf (stderr, "[removed %u dead pCodes]\n", removed);
1640 /* ------------------------------------------------------------------
1641 This routine tries to optimize the dataflow by...
1644 This routine leaves in dead pCodes (assignments whose results are
1645 not used) -- these should be removed in a following sweep phase.
1646 ------------------------------------------------------------------ */
1648 void optimizeDataflow (void)
1652 if (!the_pFile) return;
1654 //fprintf (stderr, "%s:%u(%s): Starting optimization...\n", __FILE__, __LINE__, __FUNCTION__);
1656 /* iterate over all pBlocks */
1657 for (pb = the_pFile->pbHead; pb; pb = pb->next)
1659 pCode *pc, *pcnext = NULL;
1661 /* iterate over all pCodes */
1662 for (pc = findNextInstruction (pb->pcHead); pc; pc = pcnext)
1664 pcnext = findNextInstruction (pc->next);
1665 analyzeAndReplacePCI (PCI(pc));
1669 while (removeDeadPCIs ()) { /* remove dead codes in multiple passes */};
1675 /*-----------------------------------------------------------------*
1676 * void pCodeRegOptimeRegUsage(pBlock *pb)
1677 *-----------------------------------------------------------------*/
1678 void pCodeRegOptimizeRegUsage(int level)
1683 int t = total_registers_saved;
1686 /* This is currently broken (need rewrite to correctly
1687 * handle arbitrary pCodeOps instead of registers only). */
1688 if (!pic14_options.disable_df)
1689 optimizeDataflow ();
1692 if(!register_optimization)
1694 #define OPT_PASSES 4
1695 passes = OPT_PASSES;
1698 saved = total_registers_saved;
1700 /* Identify registers used in one flow sequence */
1701 OptimizeRegUsage(dynAllocRegs,level, (OPT_PASSES-passes));
1702 OptimizeRegUsage(dynStackRegs,level, (OPT_PASSES-passes));
1703 OptimizeRegUsage(dynDirectRegs,0, (OPT_PASSES-passes));
1705 if(total_registers_saved != saved)
1706 DFPRINTF((stderr, " *** pass %d, Saved %d registers, total saved %d ***\n",
1707 (1+OPT_PASSES-passes),total_registers_saved-saved,total_registers_saved));
1711 } while( passes && ((total_registers_saved != saved) || (passes==OPT_PASSES-1)) );
1713 if(total_registers_saved == t)
1714 DFPRINTF((stderr, "No registers saved on this pass\n"));
1718 fprintf(stderr,"dynamically allocated regs:\n");
1719 dbg_regusage(dynAllocRegs);
1720 fprintf(stderr,"stack regs:\n");
1721 dbg_regusage(dynStackRegs);
1722 fprintf(stderr,"direct regs:\n");
1723 dbg_regusage(dynDirectRegs);
1728 /*-----------------------------------------------------------------*
1729 * void RegsUnMapLiveRanges(set *regset)
1731 *-----------------------------------------------------------------*/
1732 void RegsSetUnMapLiveRanges(set *regset)
1738 regset = regset->next;
1741 deleteSet(®->reglives.usedpCodes);
1742 deleteSet(®->reglives.usedpFlows);
1743 deleteSet(®->reglives.assignedpFlows);
1749 void RegsUnMapLiveRanges(void)
1752 RegsSetUnMapLiveRanges(dynAllocRegs);
1753 RegsSetUnMapLiveRanges(dynStackRegs);
1754 RegsSetUnMapLiveRanges(dynDirectRegs);
1755 RegsSetUnMapLiveRanges(dynProcessorRegs);
1756 RegsSetUnMapLiveRanges(dynDirectBitRegs);
1757 RegsSetUnMapLiveRanges(dynInternalRegs);