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 //static int sameRegs (const regs *reg1, const regs *reg2);
48 int total_registers_saved=0;
49 int register_optimization=1;
51 /*-----------------------------------------------------------------*
52 * void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
53 *-----------------------------------------------------------------*/
55 void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
58 if(!reg || ! pcfl || !isPCFL(pcflow))
62 pcfl->registers = newSet();
68 /*-----------------------------------------------------------------*
70 *-----------------------------------------------------------------*/
71 void dbg_regusage(set *fregs)
78 for (reg = setFirstItem(fregs) ; reg ;
79 reg = setNextItem(fregs)) {
81 if(elementsInSet(reg->reglives.usedpCodes)) {
83 fprintf (stderr, "%s addr=0x%03x rIdx=0x%03x",
88 pcfl = setFirstItem(reg->reglives.usedpFlows);
90 fprintf(stderr, "\n used in seq");
93 fprintf(stderr," 0x%03x",pcfl->seq);
94 pcfl = setNextItem(reg->reglives.usedpFlows);
97 pcfl = setFirstItem(reg->reglives.assignedpFlows);
99 fprintf(stderr, "\n assigned in seq");
102 fprintf(stderr," 0x%03x",pcfl->seq);
103 pcfl = setNextItem(reg->reglives.assignedpFlows);
106 pc = setFirstItem(reg->reglives.usedpCodes);
108 fprintf(stderr, "\n used in instructions ");
111 pcfl = PCODE(PCI(pc)->pcflow);
113 fprintf(stderr," 0x%03x:",pcfl->seq);
114 fprintf(stderr,"0x%03x",pc->seq);
116 pc = setNextItem(reg->reglives.usedpCodes);
119 fprintf(stderr, "\n");
124 /*-----------------------------------------------------------------*
126 *-----------------------------------------------------------------*/
127 void dbg_dumpregusage(void)
130 fprintf(stderr,"*** Register Usage ***\n");
131 fprintf(stderr,"InternalRegs:\n");
132 dbg_regusage(dynInternalRegs);
133 fprintf(stderr,"AllocRegs:\n");
134 dbg_regusage(dynAllocRegs);
135 fprintf(stderr,"StackRegs:\n");
136 dbg_regusage(dynStackRegs);
137 fprintf(stderr,"DirectRegs:\n");
138 dbg_regusage(dynDirectRegs);
139 fprintf(stderr,"DirectBitRegs:\n");
140 dbg_regusage(dynDirectBitRegs);
141 fprintf(stderr,"ProcessorRegs:\n");
142 dbg_regusage(dynProcessorRegs);
147 /*-----------------------------------------------------------------*
148 * void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
149 *-----------------------------------------------------------------*/
150 void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
161 pc = findNextInstruction(pcfl->pc.next);
163 while(pc && !isPCFL(pc)) {
164 while (pc && !isPCI(pc) && !isPCFL(pc))
168 if (!pc || isPCFL(pc)) continue;
171 reg = getRegFromInstruction(pc);
173 pc->print(stderr, pc);
174 fprintf( stderr, "--> reg %p (%s,%u), inCond/outCond: %x/%x\n",
175 reg, reg ? reg->name : "(null)", reg ? reg->rIdx : -1,
176 PCI(pc)->inCond, PCI(pc)->outCond );
180 fprintf(stderr, "flow seq %d, inst seq %d %s ",PCODE(pcfl)->seq,pc->seq,reg->name);
181 fprintf(stderr, "addr = 0x%03x, type = %d rIdx=0x%03x\n",
182 reg->address,reg->type,reg->rIdx);
185 addSetIfnotP(& (PCFL(pcfl)->registers), reg);
187 if(PCC_REGISTER & PCI(pc)->inCond)
188 addSetIfnotP(& (reg->reglives.usedpFlows), pcfl);
190 if(PCC_REGISTER & PCI(pc)->outCond)
191 addSetIfnotP(& (reg->reglives.assignedpFlows), pcfl);
193 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.
291 SNPRINTF(pbuff, size, ";%d", debug_code);
292 size -= strlen(pbuff);
293 pbuff += strlen(pbuff);
294 pCode2str(pbuff, size, pc);
295 pCodeInsertBefore(pc, newpCodeCharP(buff1));
296 //fprintf(stderr,"removing instruction:\n%s\n",buff1);
303 /*-----------------------------------------------------------------*
304 * void RemoveRegsFromSet(set *regset)
306 *-----------------------------------------------------------------*/
307 void RemoveRegsFromSet(set *regset)
314 regset = regset->next;
316 used = elementsInSet(reg->reglives.usedpCodes);
320 //fprintf(stderr," reg %s isfree=%d, wasused=%d\n",reg->name,reg->isFree,reg->wasUsed);
322 //fprintf(stderr," getting rid of reg %s\n",reg->name);
329 pc = setFirstItem(reg->reglives.usedpCodes);
331 if(reg->type == REG_SFR || reg->type == REG_STK || reg->isPublic || reg->isExtern) {
332 //fprintf(stderr, "not removing SFR reg %s even though used only once\n",reg->name);
339 pCode *pcn = findNextInstruction(pc->next);
341 if(pcn && PCI(pcn)->label) {
342 //fprintf(stderr,"can't delete instruction with label...\n");
343 //pc->print(stderr,pc);
346 /* Move the label to the next instruction */
348 PCI(pcn)->label = PCI(pc)->label;
353 regs *r = getRegFromInstruction(pc);
354 fprintf(stderr, "WARNING, a skip instruction is being optimized out\n");
355 pc->print(stderr,pc);
356 fprintf(stderr,"reg %s, type =%d\n",r->name, r->type);
358 //fprintf(stderr," removing reg %s because it is used only once\n",reg->name);
359 Remove1pcode(pc, reg, 1);
362 deleteSetItem (&(reg->reglives.usedpCodes),pc);
366 total_registers_saved++; // debugging stats.
374 void RegsUnMapLiveRanges(void);
375 extern pFile *the_pFile;
376 void pic14_ReMapLiveRanges(void)
379 if (!the_pFile) return;
380 RegsUnMapLiveRanges();
381 for (pb = the_pFile->pbHead; pb; pb = pb->next)
384 pCode *pc = findNextpCode(pb->pcHead, PC_FLOW);
386 pc->print( stderr, pc );
388 fprintf( stderr, "unnamed pBlock\n");
390 pc = findNextInstruction(pb->pcHead);
392 pc->print( stderr, pc );
393 pc = findNextInstruction(pc->next);;
396 pCodeRegMapLiveRanges(pb);
400 /*-----------------------------------------------------------------*
401 * void RemoveUnusedRegisters(void)
403 *-----------------------------------------------------------------*/
404 void RemoveUnusedRegisters(void)
406 /* First, get rid of registers that are used only one time */
407 pic14_ReMapLiveRanges();
409 //RemoveRegsFromSet(dynInternalRegs);
410 RemoveRegsFromSet(dynAllocRegs);
411 RemoveRegsFromSet(dynStackRegs);
413 don't do DirectRegs yet - there's a problem with arrays
414 RemoveRegsFromSet(dynDirectRegs);
416 RemoveRegsFromSet(dynDirectBitRegs);
418 if(total_registers_saved) DFPRINTF((stderr, " *** Saved %d registers ***\n", total_registers_saved));
422 /*-----------------------------------------------------------------*
424 *-----------------------------------------------------------------*/
425 static void Remove2pcodes(pCode *pcflow, pCode *pc1, pCode *pc2, regs *reg, int can_free)
427 static int debug_code=99;
431 fprintf (stderr, "%s:%d(%s): %d (reg:%s)\n", __FILE__, __LINE__, __FUNCTION__, debug_code, reg ? reg->name : "???");
432 printpCode (stderr, pc1);
433 printpCode (stderr, pc2);
436 //fprintf(stderr,"%s\n",__FUNCTION__);
438 Remove1pcode(pc1, reg, debug_code++);
441 Remove1pcode(pc2, reg, debug_code++);
442 deleteSetItem (&(PCFL(pcflow)->registers), reg);
451 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
454 /*-----------------------------------------------------------------*
456 *-----------------------------------------------------------------*/
457 int regUsedinRange(pCode *pc1, pCode *pc2, regs *reg)
463 testreg = getRegFromInstruction(pc1);
464 if(testreg && (testreg->rIdx == reg->rIdx)) {
468 fprintf(stderr, "warning, regUsedinRange searched through too many pcodes\n");
472 pc1 = findNextInstruction(pc1->next);
474 } while (pc1 && (pc1 != pc2)) ;
479 int regIsSpecial (regs *reg, int mayBeGlobal)
483 if (reg->type == REG_SFR || reg->type == REG_STK || (!mayBeGlobal && (reg->isPublic || reg->isExtern))) return 1;
489 static int regIsLocal (regs *reg)
492 /* temporaries are local */
493 if (reg->type == REG_TMP) return 1;
494 /* registers named r0x... are local */
495 if (reg->name && !strncmp(reg->name,"r0x", 3))
497 //fprintf (stderr, "reg %s is not marked REG_TMP...\n", reg->name);
505 /*-----------------------------------------------------------------*
506 * void pCodeOptime2pCodes(pCode *pc1, pCode *pc2)
508 * ADHOC pattern checking
509 * Now look for specific sequences that are easy to optimize.
510 * Many of these sequences are characteristic of the compiler
511 * (i.e. it'd probably be a waste of time to apply these adhoc
512 * checks to hand written assembly.)
515 *-----------------------------------------------------------------*/
516 int pCodeOptime2pCodes(pCode *pc1, pCode *pc2, pCode *pcfl_used, regs *reg, int can_free, int optimize_level)
521 int t = total_registers_saved;
523 if (!isPCI(pc1) || !isPCI(pc2)) return 0;
524 if (PCI(pc1)->pcflow != PCI(pc2)->pcflow) return 0;
526 if (pc2->seq < pc1->seq) {
532 /* disable this optimization for now -- it's buggy */
533 if (pic14_options.disable_df) return 0;
535 //fprintf(stderr,"pCodeOptime2pCodes\n");
536 //pc1->print(stderr,pc1);
537 //pc2->print(stderr,pc2);
539 if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_MOVFW) ){
543 * MOVWF does not touch Z
544 * MOVLW does not touch Z
552 can be replaced with (only if following instructions are not going to use W and reg is not used again later)
557 DFPRINTF((stderr, " optimising CLRF reg ... MOVF reg,W to ... MOVLW 0\n"));
558 pct2 = findNextInstruction(pc2->next);
559 if (pCodeSearchCondition(pct2, PCC_Z, 0) == -1) {
560 /* Z is definitely overwritten before use */
561 newpc = newpCode(POC_MOVLW, newpCodeOpLit(0));
563 pCodeInsertAfter(pc2, newpc);
564 PCI(newpc)->pcflow = PCFL(pcfl_used);
565 newpc->seq = pc2->seq;
567 //fprintf (stderr, "%s:%d(%s): Remove2pcodes (CLRF reg, ..., MOVF reg,W)\n", __FILE__, __LINE__, __FUNCTION__);
568 //Remove2pcodes(pcfl_used, pc2, NULL, reg, 0);
570 //total_registers_saved++; // debugging stats.
572 } else if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_IORFW) ){
573 DFPRINTF((stderr, " optimising CLRF/IORFW\n"));
575 pct2 = findNextInstruction(pc2->next);
577 /* We must ensure that Z is destroyed before being read---IORLW must be performed unless this is proven. */
578 if (pCodeSearchCondition(pct2, PCC_Z, 0) != -1) {
579 pct2 = newpCode(POC_IORLW, newpCodeOpLit(0));
580 pct2->seq = pc2->seq;
581 PCI(pct2)->pcflow = PCFL(pcfl_used);
582 pCodeInsertAfter(pc1,pct2);
584 //fprintf (stderr, "%s:%d(%s): Remove2pcodes (CLRF/IORFW)\n", __FILE__, __LINE__, __FUNCTION__);
585 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
586 total_registers_saved++; // debugging stats.
588 } else if(PCI(pc1)->op == POC_MOVWF) {
589 // Optimising MOVWF reg ...
591 pct2 = findNextInstruction(pc2->next);
593 if(PCI(pc2)->op == POC_MOVFW) {
594 // Optimising MOVWF reg ... MOVF reg,W
596 if(PCI(pct2)->op == POC_MOVWF) {
605 To: ( as long as 'stuff' does not use reg2 or if following instructions do not use W or reg is not used later)
611 reg2 = getRegFromInstruction(pct2);
612 /* Check reg2 is not used for something else before it is loaded with reg */
613 if (reg2 && !regIsSpecial (reg2, 1) && !regUsedinRange(pc1,pc2,reg2)) {
614 pCode *pct3 = findNextInstruction(pct2->next);
615 /* Check following instructions are not relying on the use of W or the Z flag condiction */
616 /* XXX: We must ensure that this value is destroyed before use---otherwise it might be used in
617 * subsequent flows (checking for < 1 is insufficient). */
618 if ((pCodeSearchCondition(pct3,PCC_Z,0) == -1) && (pCodeSearchCondition(pct3,PCC_W,0) == -1)) {
619 DFPRINTF((stderr, " optimising MOVF reg ... MOVF reg,W MOVWF reg2 to MOVWF reg2 ...\n"));
620 pct2->seq = pc1->seq;
622 pCodeInsertBefore(pc1,pct2);
623 if(regUsedinRange(pct2,0,reg))
625 //fprintf (stderr, "%s:%d(%s): Remove2pcodes IF (MOVWF reg, ..., MOVW reg,W MOVWF reg2)\n", __FILE__, __LINE__, __FUNCTION__);
626 Remove2pcodes(pcfl_used, pc2, NULL, reg, can_free);
628 //fprintf (stderr, "%s:%d(%s): Remove2pcodes ELSE (MOVWF reg, ..., MOVW reg,W MOVWF reg2)\n", __FILE__, __LINE__, __FUNCTION__);
629 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
631 total_registers_saved++; // debugging stats.
638 pct1 = findPrevInstruction(pc1->prev);
639 if(pct1 && (PCI(pct1)->pcflow == PCI(pc1)->pcflow)) {
641 if ( (PCI(pct1)->op == POC_MOVFW) &&
642 (PCI(pc2)->op == POC_MOVFW)) {
644 reg1 = getRegFromInstruction(pct1);
645 if(reg1 && !regIsSpecial (reg1, 0) && !regUsedinRange(pc1,pc2,reg1)) {
646 DFPRINTF((stderr, " optimising MOVF reg1,W MOVWF reg ... MOVF reg,W\n"));
662 Or, if we're not deleting the register then the "To" is:
669 pct2 = newpCode(PCI(pc2)->op, PCI(pct1)->pcop);
670 pCodeInsertAfter(pc2, pct2);
671 PCI(pct2)->pcflow = PCFL(pcfl_used);
672 pct2->seq = pc2->seq;
675 //fprintf (stderr, "%s:%d(%s): Remove2pcodes CANFREE (MOVF reg1,W; MOVWF reg2; MOVF reg2,W)\n", __FILE__, __LINE__, __FUNCTION__);
676 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
678 /* If we're not freeing the register then that means (probably)
679 * the register is needed somewhere else.*/
681 pCodeInsertAfter(pct2, pc1);
683 //fprintf (stderr, "%s:%d(%s): Remove2pcodes ELSE (MOVF reg1,W; MOVWF reg2; MOVF reg2,W)\n", __FILE__, __LINE__, __FUNCTION__);
684 Remove2pcodes(pcfl_used, pc2, NULL, reg, can_free);
687 //fprintf (stderr, "%s:%d(%s): Remove2pcodes ALWAYS (MOVF reg1,W; MOVWF reg2; MOVF reg2,W)\n", __FILE__, __LINE__, __FUNCTION__);
688 Remove2pcodes(pcfl_used, pct1, NULL, reg1, 0);
689 total_registers_saved++; // debugging stats.
696 return (total_registers_saved != t);
699 /*-----------------------------------------------------------------*
700 * void pCodeRegOptimeRegUsage(pBlock *pb)
701 *-----------------------------------------------------------------*/
702 void OptimizeRegUsage(set *fregs, int optimize_multi_uses, int optimize_level)
706 pCode *pc1=NULL, *pc2=NULL;
710 pCode *pcfl_used, *pcfl_assigned;
712 /* Step through the set by directly accessing the 'next' pointer.
713 * We could also step through by using the set API, but the
714 * the (debug) calls to print instructions affect the state
715 * of the set pointers */
720 if (strcmp(reg->name,"_SubState")==0)
721 fprintf(stderr,"Reg: %s\n",reg->name);
724 /* Catch inconsistently set-up live ranges
725 * (see tracker items #1469504 + #1474602)
726 * FIXME: Actually we should rather fix the
727 * computation of the liveranges instead...
729 if (!reg || !reg->reglives.usedpFlows
730 || !reg->reglives.assignedpFlows)
732 //fprintf( stderr, "skipping reg w/o liveranges: %s\n", reg ? reg->name : "(unknown)");
736 if(reg->type == REG_SFR || reg->type == REG_STK || reg->isPublic || reg->isExtern|| reg->isFixed) {
737 //fprintf(stderr,"skipping SFR: %s\n",reg->name);
741 pcfl_used = setFirstItem(reg->reglives.usedpFlows);
742 pcfl_assigned = setFirstItem(reg->reglives.assignedpFlows);
744 used = elementsInSet(reg->reglives.usedpCodes);
747 In this section, all registers that are used in only in two
748 instructions are examined. If possible, they're optimized out.
752 fprintf (stderr, "OptimizeRegUsage: %s addr=0x%03x rIdx=0x%03x type=%d used=%d\n",
755 reg->rIdx, reg->type, used);
757 pc1 = setFirstItem(reg->reglives.usedpCodes);
758 pc2 = setNextItem(reg->reglives.usedpCodes);
760 if(pcfl_used && pcfl_assigned) {
762 expected case - the register has been assigned a value and is
766 //fprintf(stderr," used only twice\n");
767 if(pcfl_used->seq == pcfl_assigned->seq) {
769 //fprintf(stderr, " and used in same flow\n");
771 pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 1,optimize_level);
774 // fprintf(stderr, " and used in different flows\n");
778 } else if(pcfl_used) {
780 /* register has been used twice without ever being assigned */
781 fprintf(stderr,"WARNING %s: reg %s used without being assigned\n",__FUNCTION__,reg->name);
784 //fprintf(stderr,"WARNING %s.1: reg %s assigned without being used\n",__FUNCTION__,reg->name);
785 Remove2pcodes(pcfl_assigned, pc1, pc2, reg, 1);
786 total_registers_saved++; // debugging stats.
790 /* register has been used either once, or more than twice */
792 if(used && !pcfl_used && pcfl_assigned) {
795 //fprintf(stderr,"WARNING %s.2: reg %s assigned without being used\n",__FUNCTION__,reg->name);
797 pc = setFirstItem(reg->reglives.usedpCodes);
800 pcfl_assigned = PCODE(PCI(pc)->pcflow);
801 Remove1pcode(pc, reg,2);
803 deleteSetItem (&(PCFL(pcfl_assigned)->registers), reg);
805 deleteSetItem (&(reg->reglives.usedpCodes),pc);
808 pc = setNextItem(reg->reglives.usedpCodes);
815 total_registers_saved++; // debugging stats.
816 } else if( (used > 2) && optimize_multi_uses) {
822 pCodeFlow *pcfl1=NULL, *pcfl2=NULL;
824 /* examine the number of times this register is used */
827 rset1 = reg->reglives.usedpCodes;
828 while(rset1 && searching) {
833 if(pc1 && isPCI(pc1) && ( (pcfl1 = PCI(pc1)->pcflow) != NULL) ) {
835 //while(rset2 && searching) {
839 if(pc2 && isPCI(pc2) && ( (pcfl2 = PCI(pc2)->pcflow) != NULL) ) {
842 if(pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 0,optimize_level))
847 //rset2 = rset2->next;
860 /* The following routines implement pCode optimizations based on
861 * dataflow analysis. The effects should be similar to those
862 * of pCodeOptime2pCodes() but more powerful.
864 * Unfortunately, the current approach (comparing operands by
865 * their associated registers) is seriously flawed:
866 * Some pCodeOps do not provide access to their repsective regs
867 * (PO_DIRs are created from arbitrary strings, immediates need
868 * to take offset and index into account, ...)
870 * This has to be rewritten based on pCodeOps instead of regs...
873 /* ------------------------------------------------------------------
874 Returns TRUE iff reg1 and reg2 are the same registers.
875 ------------------------------------------------------------------ */
877 static int sameRegs (const regs *reg1, const regs *reg2)
879 if (reg1 == reg2) return 1;
880 if (!reg1 || !reg2) return 0;
881 assert (reg1->name && reg2->name);
883 /* Compare names, as rIdx is not unique... */
884 if (!strcmp(reg1->name, reg2->name)) return 1;
886 /* Name mismatch -- not the same register. */
890 /* ------------------------------------------------------------------
891 Returns 1 if the register is live at pc (read in this flow),
892 returns -1 if the register is NOT live at pc (assigned a new value
893 prior to readingi the old value in this flow) or
894 return 0 if the register is not mentioned.
895 ------------------------------------------------------------------ */
897 static int checkRegInFlow (regs **reg, int *cond, pCode *pc)
899 const int verbose = 0;
900 /* find next PCI at or after pc */
901 while (pc && isPCFL(pc)) pc = pc->next;
903 assert (reg && cond);
905 /* remove pseudo flags from cond */
906 *cond &= ~(PCC_REGISTER | PCC_EXAMINE_PCOP);
910 fprintf (stderr, "Checking for reg %s, cond %x on pc ", *reg ? (*reg)->name : "<none>", *cond); pc->print (stderr, pc);
913 while (pc && !isPCFL(pc))
917 fprintf (stderr, " now checking for reg %s, cond %x on pc ", *reg ? (*reg)->name : "<none>", *cond);
918 pc->print (stderr, pc);
926 pcprev = findPrevInstruction (pc);
927 if (pcprev && isPCI_SKIP(pcprev))
930 if ((PCI(pc)->inCond | PCI(pc)->outCond) & PCC_REGISTER)
932 op = getRegFromInstruction (pc);
934 /* pCodeOpRegBits do not provide register information... */
935 //if (!op) { __asm__("int3"); pc->print (stderr, pc); }
940 return 1; /* assume `reg' is alive */
943 /* SPECIAL CASE: jump to unknown destination -- assume everything alive */
944 if (op->type == PO_PCL)
950 if (PCI(pc)->inCond & PCC_REGISTER)
952 /* `op' is live (possibly read) */
953 if (*reg && sameRegs (op, *reg))
957 fprintf (stderr, "reg is read in pc ");
958 pc->print (stderr, pc);
964 /* handle additional implicit operands */
967 case POC_CALL: /* read arguments from WREG, clobbers WREG */
972 fprintf (stderr, "conditions are read at pc ");
973 pc->print (stderr, pc);
979 case POC_RETURN: /* returns WREG to caller */
980 //fprintf (stderr, "reached RETURN, reg %s, cond %x\n", *reg ? (*reg)->name : "<none>", *cond);
985 fprintf (stderr, "conditions are read at pc ");
986 pc->print (stderr, pc);
990 /* afterwards, no condition is alive */
992 /* afterwards, all local registers are dead */
993 if (*reg && regIsLocal (*reg)) *reg = NULL;
996 case POC_RETFIE: /* this does not erturn WREG to the "caller", thus its rather a RETLW */
997 /* this discards WREG */
999 /* afterwards, no condition is alive */
1001 /* afterwards, all local registers are dead */
1002 if (*reg && regIsLocal (*reg)) *reg = NULL;
1005 /* no implicit arguments */
1009 if (PCI(pc)->inCond & (*cond))
1011 /* a condition is read */
1014 fprintf (stderr, "conditions are read at pc ");
1015 pc->print (stderr, pc);
1020 /* remove outConds from `cond' */
1021 (*cond) &= ~(PCI(pc)->outCond);
1023 if (PCI(pc)->outCond & PCC_REGISTER)
1025 /* `op' is (possibly) discarded */
1026 if (*reg && !prevIsSkip && sameRegs (op, *reg))
1030 fprintf (stderr, "reg is assigned (cont'd) at pc ");
1031 pc->print (stderr, pc);
1037 /* have all interesting conditions/registers been discarded? */
1038 if (!(*reg) && !(*cond))
1042 fprintf (stderr, "reg and conditions are discarded after ");
1043 pc->print (stderr, pc);
1052 /* no use of (or only conditional writes to) `reg' found in flow */
1055 fprintf (stderr, "analysis inconclusive: reg %s, cond %x remains\n", *reg ? "remains" : "is void", *cond);
1060 /* ------------------------------------------------------------------
1061 This will return 1 only if
1062 - reg is NULL or of type REG_TMP
1063 - reg is NULL or its value is discarded after pc
1064 - cond is 0 or all conditions are overwritten before being used
1065 ------------------------------------------------------------------ */
1073 df_state_t *df_free_states = NULL;
1076 df_newState (regs *reg, int cond, pCode *pc)
1080 if (df_free_states) {
1081 state = df_free_states;
1082 df_free_states = (df_state_t *)df_free_states->pc;
1084 state = Safe_calloc(1, sizeof(df_state_t));
1093 df_containsState (set *set, df_state_t *state)
1095 /* scan set for presence of `state' */
1097 for (curr = setFirstItem (set); curr; curr = setNextItem (set))
1099 if ((curr->pc == state->pc)
1100 && (curr->reg == state->reg)
1101 && (curr->cond == state->cond))
1111 df_releaseState (df_state_t *state)
1113 state->pc = (pCode *)df_free_states;
1114 df_free_states = (df_state_t *)state;
1123 while (df_free_states)
1125 next = (df_state_t *)df_free_states->pc;
1126 Safe_free(df_free_states);
1127 df_free_states = next;
1131 int regIsDead (regs *reg, int cond, pCode *pc)
1133 set *seenStates = NULL;
1140 if (reg && !regIsLocal (reg)) return 0;
1142 pc = findNextInstruction (pc->next);
1144 addSet (&todo, df_newState(reg, cond, pc));
1146 while ((result == 1) && (state = getSet (&todo)))
1150 if (df_containsState (seenStates, state)) continue;
1151 addSet (&seenStates, state);
1157 //fprintf (stderr, "Checking for reg %s/cond %x at pc ", reg ? reg->name : "<none>", cond);
1158 //curr->print (stderr, curr);
1160 res = checkRegInFlow (®, &cond, curr);
1163 case 1: /* `reg' or `cond' is read---not dead */
1166 case -1: /* `reg' and `cond' are discarded in this flow---need to check other open flows */
1168 default: /* `reg' is not read and (possibly) not assigned---check successor flows */
1171 pCodeFlow *pcfl = PCI(curr)->pcflow;
1172 pCodeFlowLink *link;
1176 for (link = setFirstItem(pcfl->to); link; link = setNextItem (pcfl->to))
1178 /* add the first pCodeInstruction in the new flow to `todo' */
1179 first = findNextInstruction (&link->pcflow->pc);
1180 if (first) addSet (&todo, df_newState (reg, cond, first));
1188 while (NULL != (state = getSet (&todo))) { df_releaseState (state); }
1189 while (NULL != (state = getSet (&seenStates))) { df_releaseState (state); }
1191 /* if result remained 1, `reg' is not even possibly read and thus dead */
1197 /* ------------------------------------------------------------------
1198 Safely remove a pCode.
1199 This needs to check that the previous instruction was no SKIP
1200 (otherwise the SKIP instruction would have to be removed as well,
1201 which may not be done for SFRs (side-effects on read possible)).
1202 ------------------------------------------------------------------ */
1204 extern void unBuildFlow (pBlock *pb);
1205 extern void RegsUnMapLiveRanges ();
1206 extern void BuildFlow (pBlock *pb);
1207 extern void LinkFlow (pBlock *pb);
1208 extern void BuildFlowTree (pBlock *pb);
1209 extern void pCodeRegMapLiveRanges (pBlock *pb);
1210 extern pFile *the_pFile;
1212 static int pCodeRemove (pCode *pc, const char *comment)
1214 pCode *pcprev, *pcnext;
1215 unsigned int result = 0;
1217 /* Sanity checks. */
1219 if (!isPCI(pc)) return 0;
1221 pcprev = findPrevInstruction (pc->prev);
1222 if (pcprev && isPCI_SKIP(pcprev))
1224 /* bail out until we know how to fix the Flow... */
1227 /* we also need to remove the preceeding SKIP instruction(s) */
1228 result = pCodeRemove (pcprev, "=DF= removing preceeding SKIP as well");
1231 /* previous instruction could not be removed -- this cannot be removed as well */
1234 /* FIXME: We now have to update the flow! */
1237 /* do not remove pCodes with SFRs as operands (even reading them might cause side effects) */
1240 reg = getRegFromInstruction (pc);
1241 /* accesses to the STATUS register aer always safe, but others... */
1242 if (reg && reg->type == REG_SFR && reg->pc_type != PO_STATUS) return result;
1245 /* MUST SUCEED FROM NOW ON (or revert the changes done since NOW ;-)) */
1248 if (PCI(pc)->pcflow && PCI(pc)->pcflow->end == pc)
1251 pcprev = findPrevInstruction (pc->prev);
1252 if (PCI(pcprev)->pcflow == PCI(pc)->pcflow)
1254 PCI(pc)->pcflow->end = pcprev;
1256 pBlock *pb = pc->pb;
1257 RegsUnMapLiveRanges();
1262 for (pb = the_pFile->pbHead; pb; pb = pb->next)
1264 pCodeRegMapLiveRanges(pb);
1269 /* attach labels to next instruction */
1270 pcnext = findNextInstruction (pc->next);
1273 PCI(pcnext)->label = pBranchAppend (PCI(pcnext)->label, PCI(pc)->label);
1274 if (!PCI(pcnext)->cline) PCI(pcnext)->cline = PCI(pc)->cline;
1278 fprintf (stderr, "Cannot move a label...\n");
1286 char *pbuff = &buffer[0];
1288 SNPRINTF (pbuff, size, "; %s:%u(%s): %s", __FILE__, __LINE__, __FUNCTION__, comment);
1289 pCodeInsertAfter(pc->prev, newpCodeCharP (&buffer[0]));
1294 /* replace removed pCode with out-commented version of itself */
1297 char *pbuff = &buffer[0];
1299 SNPRINTF (pbuff, size, "; %s:%u(%s): ", __FILE__, __LINE__, __FUNCTION__);
1300 size -= strlen(pbuff);
1301 pbuff += strlen(pbuff);
1302 pCode2str (pbuff, size, pc);
1303 pCodeInsertAfter(pc->prev, newpCodeCharP (&buffer[0]));
1310 /* ------------------------------------------------------------------
1311 Find and remove dead pCodes.
1312 ------------------------------------------------------------------ */
1314 static int removeIfDeadPCI (pCode *pc)
1316 pCode *pcnext = NULL;
1318 unsigned int outCond;
1319 unsigned int result = 0;
1326 pcnext = findNextInstruction (pc->next);
1327 if (!isPCI(pc)) return 0;
1329 switch (PCI(pc)->op)
1385 /* do not remove unknown PCIs */
1389 /* redundant checks---those instructions may never be removed */
1390 if (isPCI_BRANCH(pc)) return 0;
1391 if (isPCI_SKIP(pc)) return 0;
1393 outCond = PCI(pc)->outCond;
1396 /* unknown operands assigned to, then ignore */
1397 if ((outCond & (PCC_REGISTER | PCC_C | PCC_Z | PCC_DC | PCC_W)) != outCond)
1400 if (outCond & PCC_REGISTER)
1402 dst = getRegFromInstruction (pc);
1406 if (!regIsLocal (dst)) return 0;
1407 if (regIsSpecial (dst,0)) return 0;
1410 //fprintf (stderr, "--> checking for liveness pc "); pc->print (stderr, pc);
1411 if (regIsDead (dst, outCond, pc))
1413 /* no result from pc has been used -- pc is `dead' */
1414 //fprintf (stderr, "--> reg %s and cond %x assumed unused\n", dst ? dst->name : "<none>", outCond);
1415 //fprintf (stderr, "--> removing dead pc "); pc->print (stderr, pc);
1416 result = pCodeRemove (pc, "=DF= removed dead pCode");
1422 /* ------------------------------------------------------------------
1423 This routine is intended to safely replace one pCodeInstruction
1424 with a different pCodeInstruction.
1425 If desired, the replaced pCode will be left in (commented out) for
1427 Further, an optional comment can be inserted to indicate the
1428 reason for the possible removal of the pCode.
1429 ------------------------------------------------------------------ */
1431 static void replace_PCI (pCodeInstruction *pc, pCodeInstruction *newpc, char *comment)
1433 newpc->from = pBranchAppend (newpc->from, pc->from);
1434 newpc->to = pBranchAppend (newpc->to, pc->to);
1435 newpc->label = pBranchAppend (newpc->label, pc->label);
1436 //newpc->pcflow = pc->pcflow; // updated in pCodeInsertAfter, ->pb is as well
1437 newpc->cline = pc->cline;
1439 newpc->pc.seq = pc->pc.seq;
1441 pCodeInsertAfter (&pc->pc, &newpc->pc);
1443 /* FIXME: replacing pc will break the liverange maps (usedpCodes, ...) */
1444 pCodeRegMapLiveRanges( pc->pBlock ); /*FIXME:UNTESTED*/
1448 pCodeInsertAfter (&pc->pc, newpCodeCharP (comment));
1453 /* replace pc with commented out version of itself */
1454 char buffer[1024], buffer2[1024];
1455 char *pbuff = &buffer[0];
1457 pCode2str (&buffer2[0],1024,&pc->pc);
1458 SNPRINTF (pbuff,size,"%s:%u(%s): removed pCode was %s\t", __FILE__, __LINE__, __FUNCTION__, &buffer2[0]);
1459 pCodeInsertAfter (&pc->pc, newpCodeCharP (&buffer[0]));
1462 pc->pc.destruct (&pc->pc);
1465 /* ------------------------------------------------------------------
1466 Find the first (unique) assignment to `reg' (prior to pc).
1467 ------------------------------------------------------------------ */
1469 pCode *findAssignmentToReg (regs *reg, pCode *pc)
1473 assert (pc && isPCI(pc) && reg);
1475 curr = findPrevInstruction (pc->prev);
1477 while (curr && PCI(curr)->pcflow == PCI(pc)->pcflow)
1479 if (PCI(curr)->outCond & PCC_REGISTER)
1481 regs *op = getRegFromInstruction (curr);
1482 if (op && (sameRegs(op,reg)))
1485 curr = findPrevInstruction (curr->prev);
1488 /* no assignment to reg found */
1492 /* ------------------------------------------------------------------
1493 Find a register that holds the same value as `reg' (an alias).
1494 ------------------------------------------------------------------ */
1496 regs *findRegisterAlias (regs *reg, pCode *pc)
1500 if(!reg) return NULL;
1502 if (regIsSpecial (reg, 0)) return NULL;
1504 curr = findAssignmentToReg (reg, pc);
1506 /* no assignment found --> no alias found */
1507 if (!curr) return NULL;
1509 switch (PCI(curr)->op)
1512 /* find previous assignment to WREG */
1513 while (curr && !(PCI(curr)->outCond & PCC_W))
1514 curr = findPrevInstruction (curr->prev);
1515 if (curr && PCI(curr)->op == POC_MOVFW)
1517 regs *op = getRegFromInstruction (curr);
1518 /* alias must not be changed since assignment... */
1519 if (PCI(curr)->pcop)
1521 switch (PCI(curr)->pcop->type)
1523 case PO_GPR_REGISTER:
1525 /* these operands are ok */
1528 /* not a plain register operand */
1533 if (!op || regIsSpecial (op, 0) || !regIsUnchangedSince (op, pc, curr)) return NULL;
1534 //fprintf (stderr, "found register alias for %s: %s\n", reg->name, op && op->name ? op->name : "<no name>");
1537 /* unknown source to WREG -- unknown register alias */
1543 /* unhandled instruction -- assume unknown source, no alias */
1547 /* no alias found */
1551 /* ------------------------------------------------------------------
1552 Analyze a single pCodeInstruction's dataflow relations and replace
1553 it with a better variant if possible.
1554 ------------------------------------------------------------------ */
1556 void analyzeAndReplacePCI (pCodeInstruction *pci)
1558 regs *op_reg, *alias_reg;
1562 if (!isPCI(pci)) return;
1571 /* try to find a different source register */
1572 op_reg = getRegFromInstruction (&pci->pc);
1573 if (pci->op == POC_MOVFW) /* touches Z */
1575 pCode *assignment = findAssignmentToReg (op_reg, &pci->pc);
1576 if (assignment && isPCI(assignment) && (PCI(assignment)->op == POC_CLRF))
1578 replace_PCI (pci, PCI(newpCode(POC_MOVLW, newpCodeOpLit(0))), "replaced with CLRF");
1583 alias_reg = findRegisterAlias (op_reg, &pci->pc);
1586 replace_PCI (pci, PCI(newpCode(pci->op, newpCodeOpRegFromStr (alias_reg->name))), "=DF= replaced with move from register alias");
1591 /* do not optimize */
1596 extern pFile *the_pFile;
1598 /* ------------------------------------------------------------------
1599 Find and remove dead pCodes.
1600 ------------------------------------------------------------------ */
1602 static int removeDeadPCIs (void)
1605 unsigned int removed = 0;
1607 if (!the_pFile) return removed;
1612 /* iterate over all pBlocks */
1613 for (pb = the_pFile->pbHead; pb; pb = pb->next)
1615 pCode *pc, *pcnext = NULL;
1617 /* iterate over all pCodes */
1618 for (pc = findNextInstruction (pb->pcHead); pc; pc = pcnext)
1620 pcnext = findNextInstruction (pc->next);
1621 removed += removeIfDeadPCI (pc);
1625 fprintf (stderr, "[removed %u dead pCodes]\n", removed);
1631 /* ------------------------------------------------------------------
1632 This routine tries to optimize the dataflow by...
1635 This routine leaves in dead pCodes (assignments whose results are
1636 not used) -- these should be removed in a following sweep phase.
1637 ------------------------------------------------------------------ */
1639 void optimizeDataflow (void)
1643 if (!the_pFile) return;
1645 //fprintf (stderr, "%s:%u(%s): Starting optimization...\n", __FILE__, __LINE__, __FUNCTION__);
1647 /* iterate over all pBlocks */
1648 for (pb = the_pFile->pbHead; pb; pb = pb->next)
1650 pCode *pc, *pcnext = NULL;
1652 /* iterate over all pCodes */
1653 for (pc = findNextInstruction (pb->pcHead); pc; pc = pcnext)
1655 pcnext = findNextInstruction (pc->next);
1656 analyzeAndReplacePCI (PCI(pc));
1660 while (removeDeadPCIs ()) { /* remove dead codes in multiple passes */};
1666 /*-----------------------------------------------------------------*
1667 * void pCodeRegOptimeRegUsage(pBlock *pb)
1668 *-----------------------------------------------------------------*/
1669 void pCodeRegOptimizeRegUsage(int level)
1674 int t = total_registers_saved;
1677 /* This is currently broken (need rewrite to correctly
1678 * handle arbitrary pCodeOps instead of registers only). */
1679 if (!pic14_options.disable_df)
1680 optimizeDataflow ();
1683 if(!register_optimization)
1685 #define OPT_PASSES 4
1686 passes = OPT_PASSES;
1689 saved = total_registers_saved;
1691 /* Identify registers used in one flow sequence */
1692 OptimizeRegUsage(dynAllocRegs,level, (OPT_PASSES-passes));
1693 OptimizeRegUsage(dynStackRegs,level, (OPT_PASSES-passes));
1694 OptimizeRegUsage(dynDirectRegs,0, (OPT_PASSES-passes));
1696 if(total_registers_saved != saved)
1697 DFPRINTF((stderr, " *** pass %d, Saved %d registers, total saved %d ***\n",
1698 (1+OPT_PASSES-passes),total_registers_saved-saved,total_registers_saved));
1702 } while( passes && ((total_registers_saved != saved) || (passes==OPT_PASSES-1)) );
1704 if(total_registers_saved == t)
1705 DFPRINTF((stderr, "No registers saved on this pass\n"));
1709 fprintf(stderr,"dynamically allocated regs:\n");
1710 dbg_regusage(dynAllocRegs);
1711 fprintf(stderr,"stack regs:\n");
1712 dbg_regusage(dynStackRegs);
1713 fprintf(stderr,"direct regs:\n");
1714 dbg_regusage(dynDirectRegs);
1719 /*-----------------------------------------------------------------*
1720 * void RegsUnMapLiveRanges(set *regset)
1722 *-----------------------------------------------------------------*/
1723 void RegsSetUnMapLiveRanges(set *regset)
1729 regset = regset->next;
1732 deleteSet(®->reglives.usedpCodes);
1733 deleteSet(®->reglives.usedpFlows);
1734 deleteSet(®->reglives.assignedpFlows);
1740 void RegsUnMapLiveRanges(void)
1743 RegsSetUnMapLiveRanges(dynAllocRegs);
1744 RegsSetUnMapLiveRanges(dynStackRegs);
1745 RegsSetUnMapLiveRanges(dynDirectRegs);
1746 RegsSetUnMapLiveRanges(dynProcessorRegs);
1747 RegsSetUnMapLiveRanges(dynDirectBitRegs);
1748 RegsSetUnMapLiveRanges(dynInternalRegs);