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"
39 extern void pCodeInsertAfter(pCode *pc1, pCode *pc2);
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);
45 int total_registers_saved=0;
47 /*-----------------------------------------------------------------*
48 * void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
49 *-----------------------------------------------------------------*/
51 void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
54 if(!reg || ! pcfl || !isPCFL(pcflow))
58 pcfl->registers = newSet();
64 /*-----------------------------------------------------------------*
66 *-----------------------------------------------------------------*/
67 void dbg_regusage(set *fregs)
74 for (reg = setFirstItem(fregs) ; reg ;
75 reg = setNextItem(fregs)) {
77 if(elementsInSet(reg->reglives.usedpCodes)) {
79 fprintf (stderr, "%s addr=0x%03x rIdx=0x%03x",
84 pcfl = setFirstItem(reg->reglives.usedpFlows);
86 fprintf(stderr, "\n used in seq");
89 fprintf(stderr," 0x%03x",pcfl->seq);
90 pcfl = setNextItem(reg->reglives.usedpFlows);
93 pcfl = setFirstItem(reg->reglives.assignedpFlows);
95 fprintf(stderr, "\n assigned in seq");
98 fprintf(stderr," 0x%03x",pcfl->seq);
99 pcfl = setNextItem(reg->reglives.assignedpFlows);
102 pc = setFirstItem(reg->reglives.usedpCodes);
104 fprintf(stderr, "\n used in instructions ");
107 pcfl = PCODE(PCI(pc)->pcflow);
109 fprintf(stderr," 0x%03x:",pcfl->seq);
110 fprintf(stderr,"0x%03x",pc->seq);
112 pc = setNextItem(reg->reglives.usedpCodes);
115 fprintf(stderr, "\n");
120 /*-----------------------------------------------------------------*
122 *-----------------------------------------------------------------*/
123 void dbg_dumpregusage(void)
126 fprintf(stderr,"*** Register Usage ***\n");
127 fprintf(stderr,"InternalRegs:\n");
128 dbg_regusage(dynInternalRegs);
129 fprintf(stderr,"AllocRegs:\n");
130 dbg_regusage(dynAllocRegs);
131 fprintf(stderr,"StackRegs:\n");
132 dbg_regusage(dynStackRegs);
133 fprintf(stderr,"DirectRegs:\n");
134 dbg_regusage(dynDirectRegs);
135 fprintf(stderr,"DirectBitRegs:\n");
136 dbg_regusage(dynDirectBitRegs);
137 fprintf(stderr,"ProcessorRegs:\n");
138 dbg_regusage(dynProcessorRegs);
143 /*-----------------------------------------------------------------*
144 * void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
145 *-----------------------------------------------------------------*/
146 void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
158 pc = findNextInstruction(pcfl->pc.next);
160 while(isPCinFlow(pc,PCODE(pcfl))) {
163 reg = getRegFromInstruction(pc);
167 fprintf(stderr, "flow seq %d, inst seq %d %s ",PCODE(pcfl)->seq,pc->seq,reg->name);
168 fprintf(stderr, "addr = 0x%03x, type = %d rIdx=0x%03x\n",
169 reg->address,reg->type,reg->rIdx);
172 addSetIfnotP(& (PCFL(pcfl)->registers), reg);
174 if((PCC_REGISTER | PCC_LITERAL) & PCI(pc)->inCond)
175 addSetIfnotP(& (reg->reglives.usedpFlows), pcfl);
177 if(PCC_REGISTER & PCI(pc)->outCond)
178 addSetIfnotP(& (reg->reglives.assignedpFlows), pcfl);
180 addSetIfnotP(& (reg->reglives.usedpCodes), pc);
185 pc = findNextInstruction(pc->next);
191 /*-----------------------------------------------------------------*
192 * void pCodeRegMapLiveRanges(pBlock *pb)
193 *-----------------------------------------------------------------*/
194 void pCodeRegMapLiveRanges(pBlock *pb)
198 for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
200 pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
202 if(!isPCFL(pcflow)) {
203 fprintf(stderr, "pCodeRegMapLiveRanges - pcflow is not a flow object ");
206 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
210 for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
212 pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
214 regs *r = setFirstItem(PCFL(pcflow)->registers);
215 fprintf(stderr,"flow seq %d\n", pcflow->seq);
218 fprintf(stderr, " %s\n",r->name);
219 r = setNextItem(PCFL(pcflow)->registers);
226 // dbg_dumpregusage();
231 /*-----------------------------------------------------------------*
233 *-----------------------------------------------------------------*/
234 static void Remove1pcode(pCode *pc, regs *reg)
241 deleteSetItem (&(reg->reglives.usedpCodes),pc);
243 fprintf(stderr,"removing instruction:\n");
244 pc->print(stderr,pc);
247 pcn = findNextInstruction(pc->next);
250 PCI(pcn)->label = pBranchAppend(PCI(pcn)->label,PCI(pc)->label);
255 pcn = findNextInstruction(pc->next);
258 if(PCI(pcn)->cline) {
259 //fprintf(stderr, "source line has been optimized completely out\n");
260 //pc->print(stderr,pc);
262 PCI(pcn)->cline = PCI(pc)->cline;
271 /*-----------------------------------------------------------------*
272 * void RemoveRegsFromSet(set *regset)
274 *-----------------------------------------------------------------*/
275 void RemoveRegsFromSet(set *regset)
282 regset = regset->next;
284 used = elementsInSet(reg->reglives.usedpCodes);
288 //fprintf(stderr," reg %s isfree=%d, wasused=%d\n",reg->name,reg->isFree,reg->wasUsed);
290 //fprintf(stderr," getting rid of reg %s\n",reg->name);
297 pc = setFirstItem(reg->reglives.usedpCodes);
299 if(reg->type == REG_SFR) {
300 //fprintf(stderr, "not removing SFR reg %s even though used only once\n",reg->name);
307 pCode *pcn = findNextInstruction(pc->next);
309 if(pcn && PCI(pcn)->label) {
310 //fprintf(stderr,"can't delete instruction with label...\n");
311 //pc->print(stderr,pc);
314 /* Move the label to the next instruction */
316 PCI(pcn)->label = PCI(pc)->label;
321 regs *r = getRegFromInstruction(pc);
322 fprintf(stderr, "WARNING, a skip instruction is being optimized out\n");
323 pc->print(stderr,pc);
324 fprintf(stderr,"reg %s, type =%d\n",r->name, r->type);
326 //fprintf(stderr," removing reg %s because it is used only once\n",reg->name);
327 Remove1pcode(pc, reg);
330 deleteSetItem (&(reg->reglives.usedpCodes),pc);
334 total_registers_saved++; // debugging stats.
341 /*-----------------------------------------------------------------*
342 * void RemoveUnusedRegisters(void)
344 *-----------------------------------------------------------------*/
345 void RemoveUnusedRegisters(void)
347 /* First, get rid of registers that are used only one time */
349 RemoveRegsFromSet(dynInternalRegs);
350 RemoveRegsFromSet(dynAllocRegs);
351 RemoveRegsFromSet(dynStackRegs);
353 don't do DirectRegs yet - there's a problem with arrays
354 RemoveRegsFromSet(dynDirectRegs);
356 RemoveRegsFromSet(dynDirectBitRegs);
358 if(total_registers_saved) fprintf(stderr, " *** Saved %d registers ***\n", total_registers_saved);
362 /*-----------------------------------------------------------------*
364 *-----------------------------------------------------------------*/
365 static void Remove2pcodes(pCode *pcflow, pCode *pc1, pCode *pc2, regs *reg, int can_free)
371 Remove1pcode(pc1, reg);
374 Remove1pcode(pc2, reg);
375 deleteSetItem (&(PCFL(pcflow)->registers), reg);
384 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
387 /*-----------------------------------------------------------------*
389 *-----------------------------------------------------------------*/
390 int regUsedinRange(pCode *pc1, pCode *pc2, regs *reg)
396 testreg = getRegFromInstruction(pc1);
397 if(testreg && (testreg->rIdx == reg->rIdx)) {
401 pc1 = findNextInstruction(pc1->next);
403 } while (pc1 && (pc1 != pc2) && (i++ < 100)) ;
406 fprintf(stderr, "warning, regUsedinRange searched through too many pcodes\n");
411 /*-----------------------------------------------------------------*
412 * void pCodeOptime2pCodes(pCode *pc1, pCode *pc2)
414 * ADHOC pattern checking
415 * Now look for specific sequences that are easy to optimize.
416 * Many of these sequences are characteristic of the compiler
417 * (i.e. it'd probably be a waste of time to apply these adhoc
418 * checks to hand written assembly.)
421 *-----------------------------------------------------------------*/
422 int pCodeOptime2pCodes(pCode *pc1, pCode *pc2, pCode *pcfl_used, regs *reg, int can_free)
427 int t = total_registers_saved;
429 if(pc2->seq < pc1->seq) {
436 if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_MOVFW) ){
450 //fprintf(stderr, " CLRF/MOVFW. instruction after MOVFW is:\n");
451 pct1 = findNextInstruction(pc2->next);
452 //t->print(stderr,t);
454 if(PCI(pct1)->op == POC_MOVWF) {
455 newpc = newpCode(POC_CLRF, PCI(pct1)->pcop);
456 pct1->destruct(pct1);
458 newpc = newpCode(POC_MOVLW, newpCodeOpLit(0));
461 pCodeInsertAfter(pc2, newpc);
462 PCI(newpc)->pcflow = PCFL(pcfl_used);
463 newpc->seq = pc2->seq;
465 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
466 total_registers_saved++; // debugging stats.
468 } else if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_IORFW) ){
469 //fprintf(stderr, " CLRF/IORFW.\n");
471 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
472 total_registers_saved++; // debugging stats.
474 } else if(PCI(pc1)->op == POC_MOVWF) {
476 pct2 = findNextInstruction(pc2->next);
478 if(PCI(pc2)->op == POC_MOVFW) {
479 //fprintf(stderr, " MOVWF/MOVFW. instruction after MOVFW is:\n");
480 //pct2->print(stderr,pct2);
482 if(PCI(pct2)->op == POC_MOVWF) {
483 reg2 = getRegFromInstruction(pct2);
484 if(reg2 && !regUsedinRange(pc1,pc2,reg2) && (reg2->type != REG_SFR)) {
485 pct2->seq = pc1->seq;
487 pCodeInsertAfter(pc1,pct2);
488 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
489 total_registers_saved++; // debugging stats.
493 fprintf(stderr, " couldn't optimize\n");
495 fprintf(stderr, " %s is used in range\n",reg2->name);
497 fprintf(stderr, " reg2 is NULL\n");
502 pct1 = findPrevInstruction(pc1->prev);
504 (PCI(pct1)->pcflow == PCI(pc1)->pcflow) &&
505 (PCI(pct1)->op == POC_MOVFW)) {
507 reg1 = getRegFromInstruction(pct1);
508 if(reg1 && !regUsedinRange(pc1,pc2,reg1)) {
509 //fprintf(stderr, " MOVF/MOVFW. \n");
517 pct2 = newpCode(PCI(pc2)->op, PCI(pct1)->pcop);
518 pCodeInsertAfter(pc2, pct2);
519 PCI(pct2)->pcflow = PCFL(pcfl_used);
520 pct2->seq = pc2->seq;
522 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
523 Remove2pcodes(pcfl_used, pct1, NULL, reg1, 0);
524 total_registers_saved++; // debugging stats.
532 return (total_registers_saved != t);
535 /*-----------------------------------------------------------------*
536 * void pCodeRegOptimeRegUsage(pBlock *pb)
537 *-----------------------------------------------------------------*/
538 void OptimizeRegUsage(set *fregs, int optimize_multi_uses)
542 pCode *pc1=NULL, *pc2=NULL;
546 pCode *pcfl_used, *pcfl_assigned;
548 /* Step through the set by directly accessing the 'next' pointer.
549 * We could also step through by using the set API, but the
550 * the (debug) calls to print instructions affect the state
551 * of the set pointers */
556 if(reg->type == REG_SFR) {
557 //fprintf(stderr,"skipping SFR: %s\n",reg->name);
561 pcfl_used = setFirstItem(reg->reglives.usedpFlows);
562 pcfl_assigned = setFirstItem(reg->reglives.assignedpFlows);
564 used = elementsInSet(reg->reglives.usedpCodes);
568 * In this section, all registers that are used in only in two
569 * instructions are examined. If possible, they're optimized out.
573 fprintf (stderr, "OptimizeRegUsage: %s addr=0x%03x rIdx=0x%03x type=%d used=%d\n",
576 reg->rIdx, reg->type, used);
578 pc1 = setFirstItem(reg->reglives.usedpCodes);
579 pc2 = setNextItem(reg->reglives.usedpCodes);
581 if(pcfl_used && pcfl_assigned) {
584 expected case - the register has been assigned a value and is
588 //fprintf(stderr," used only twice\n");
589 if(pcfl_used->seq == pcfl_assigned->seq) {
591 //fprintf(stderr, " and used in same flow\n");
593 pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 1);
596 // fprintf(stderr, " and used in different flows\n");
600 } else if(pcfl_used) {
603 register has been used twice without ever being assigned */
604 //fprintf(stderr,"WARNING %s: reg %s used without being assigned\n",__FUNCTION__,reg->name);
607 //fprintf(stderr,"WARNING %s: reg %s assigned without being used\n",__FUNCTION__,reg->name);
608 Remove2pcodes(pcfl_assigned, pc1, pc2, reg, 1);
609 total_registers_saved++; // debugging stats.
613 /* register has been used either once, or more than twice */
615 if(used && !pcfl_used && pcfl_assigned) {
618 //fprintf(stderr,"WARNING %s: reg %s assigned without being used\n",__FUNCTION__,reg->name);
620 pc = setFirstItem(reg->reglives.usedpCodes);
623 pcfl_assigned = PCODE(PCI(pc)->pcflow);
624 Remove1pcode(pc, reg);
626 deleteSetItem (&(PCFL(pcfl_assigned)->registers), reg);
628 deleteSetItem (&(reg->reglives.usedpCodes),pc);
631 pc = setNextItem(reg->reglives.usedpCodes);
638 total_registers_saved++; // debugging stats.
639 } else if( (used > 2) && optimize_multi_uses) {
645 pCodeFlow *pcfl1=NULL, *pcfl2=NULL;
647 /* examine the number of times this register is used */
650 rset1 = reg->reglives.usedpCodes;
651 while(rset1 && searching) {
656 if(pc1 && isPCI(pc1) && ( (pcfl1 = PCI(pc1)->pcflow) != NULL) ) {
658 while(rset2 && searching) {
661 if(pc2 && isPCI(pc2) && ( (pcfl2 = PCI(pc2)->pcflow) != NULL) ) {
664 fprintf(stderr, " two instruction in same flow\n");
665 pc1->print(stderr, pc1);
666 pc2->print(stderr, pc2);
668 //if(pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 1))
685 /*-----------------------------------------------------------------*
686 * void pCodeRegOptimeRegUsage(pBlock *pb)
687 *-----------------------------------------------------------------*/
688 void pCodeRegOptimizeRegUsage(void)
693 int t = total_registers_saved;
694 int optimize_multi = 0;
699 //fprintf(stderr, " multi opti %d\n",optimize_multi);
702 saved = total_registers_saved;
704 /* Identify registers used in one flow sequence */
705 OptimizeRegUsage(dynAllocRegs,optimize_multi);
706 OptimizeRegUsage(dynStackRegs,0);
707 OptimizeRegUsage(dynDirectRegs,0);
709 if(total_registers_saved != saved)
710 fprintf(stderr, " *** Saved %d registers, total saved %d ***\n", total_registers_saved-saved,total_registers_saved);
713 } while( passes-- && (total_registers_saved != saved));
716 } while (optimize_multi < 2);
718 if(total_registers_saved == t)
719 fprintf(stderr, "No registers saved on this pass\n");
723 fprintf(stderr,"dynamically allocated regs:\n");
724 dbg_regusage(dynAllocRegs);
725 fprintf(stderr,"stack regs:\n");
726 dbg_regusage(dynStackRegs);
727 fprintf(stderr,"direct regs:\n");
728 dbg_regusage(dynDirectRegs);
733 /*-----------------------------------------------------------------*
734 * void RegsUnMapLiveRanges(set *regset)
736 *-----------------------------------------------------------------*/
737 void RegsSetUnMapLiveRanges(set *regset)
743 regset = regset->next;
746 deleteSet(®->reglives.usedpCodes);
747 deleteSet(®->reglives.usedpFlows);
748 deleteSet(®->reglives.assignedpFlows);
754 void RegsUnMapLiveRanges(void)
757 RegsSetUnMapLiveRanges(dynAllocRegs);
758 RegsSetUnMapLiveRanges(dynStackRegs);
759 RegsSetUnMapLiveRanges(dynDirectRegs);
760 RegsSetUnMapLiveRanges(dynProcessorRegs);
761 RegsSetUnMapLiveRanges(dynDirectBitRegs);
762 RegsSetUnMapLiveRanges(dynInternalRegs);