Fixed seg fault for empty programs. Added more register optimizations.
[fw/sdcc] / src / pic / pcoderegs.c
1 /*-------------------------------------------------------------------------
2
3    pcoderegs.c - post code generation register optimizations
4
5    Written By -  Scott Dattalo scott@dattalo.com
6
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
10    later version.
11    
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.
16    
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.
20    
21 -------------------------------------------------------------------------*/
22
23 /*
24   pcoderegs.c
25
26   The purpose of the code in this file is to optimize the register usage.
27
28 */
29 #include <stdio.h>
30
31 #include "common.h"   // Include everything in the SDCC src directory
32 #include "newalloc.h"
33 #include "ralloc.h"
34 #include "device.h"
35 #include "pcode.h"
36 #include "pcoderegs.h"
37 #include "pcodeflow.h"
38
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);
44
45 int total_registers_saved=0;
46
47 /*-----------------------------------------------------------------*
48  * void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
49  *-----------------------------------------------------------------*/
50 /*
51 void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
52 {
53
54   if(!reg || ! pcfl || !isPCFL(pcflow))
55     return;
56
57   if(!pcfl->registers) 
58     pcfl->registers =  newSet();
59
60 }
61 */
62
63
64 /*-----------------------------------------------------------------*
65  * 
66  *-----------------------------------------------------------------*/
67 void dbg_regusage(set *fregs)
68 {
69   regs *reg;
70   pCode *pcfl;
71   pCode *pc;
72
73
74   for (reg = setFirstItem(fregs) ; reg ;
75        reg = setNextItem(fregs)) {
76
77     if(elementsInSet(reg->reglives.usedpCodes)) {
78     
79       fprintf (stderr, "%s  addr=0x%03x rIdx=0x%03x",
80                reg->name,
81                reg->address,
82                reg->rIdx);
83
84       pcfl = setFirstItem(reg->reglives.usedpFlows);
85       if(pcfl)
86         fprintf(stderr, "\n   used in seq");
87
88       while(pcfl) {
89         fprintf(stderr," 0x%03x",pcfl->seq);
90         pcfl = setNextItem(reg->reglives.usedpFlows);
91       }
92
93       pcfl = setFirstItem(reg->reglives.assignedpFlows);
94       if(pcfl)
95         fprintf(stderr, "\n   assigned in seq");
96
97       while(pcfl) {
98         fprintf(stderr," 0x%03x",pcfl->seq);
99         pcfl = setNextItem(reg->reglives.assignedpFlows);
100       }
101
102       pc = setFirstItem(reg->reglives.usedpCodes);
103       if(pc)
104         fprintf(stderr, "\n   used in instructions ");
105
106       while(pc) {
107         pcfl = PCODE(PCI(pc)->pcflow);
108         if(pcfl)
109           fprintf(stderr," 0x%03x:",pcfl->seq);
110         fprintf(stderr,"0x%03x",pc->seq);
111
112         pc = setNextItem(reg->reglives.usedpCodes);
113       }
114
115       fprintf(stderr, "\n");
116     }
117   }
118 }
119
120 /*-----------------------------------------------------------------*
121  * 
122  *-----------------------------------------------------------------*/
123 void dbg_dumpregusage(void)
124 {
125
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);
139
140 }
141
142
143 /*-----------------------------------------------------------------*
144  * void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
145  *-----------------------------------------------------------------*/
146 void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
147 {
148
149   pCode *pc=NULL;
150   pCode *pcprev=NULL;
151
152   regs *reg;
153
154   if(!pcfl)
155     return;
156
157
158   pc = findNextInstruction(pcfl->pc.next);
159
160   while(isPCinFlow(pc,PCODE(pcfl))) {
161
162
163     reg = getRegFromInstruction(pc);
164
165     if(reg) {
166 /*
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);
170 */
171
172       addSetIfnotP(& (PCFL(pcfl)->registers), reg);
173
174       if((PCC_REGISTER | PCC_LITERAL) & PCI(pc)->inCond)
175         addSetIfnotP(& (reg->reglives.usedpFlows), pcfl);
176
177       if(PCC_REGISTER & PCI(pc)->outCond)
178         addSetIfnotP(& (reg->reglives.assignedpFlows), pcfl);
179
180       addSetIfnotP(& (reg->reglives.usedpCodes), pc);
181     }
182
183
184     pcprev = pc;
185     pc = findNextInstruction(pc->next);
186
187   }
188
189 }
190
191 /*-----------------------------------------------------------------*
192  * void pCodeRegMapLiveRanges(pBlock *pb) 
193  *-----------------------------------------------------------------*/
194 void pCodeRegMapLiveRanges(pBlock *pb)
195 {
196   pCode *pcflow;
197
198   for( pcflow = findNextpCode(pb->pcHead, PC_FLOW); 
199        pcflow != NULL;
200        pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
201
202     if(!isPCFL(pcflow)) {
203       fprintf(stderr, "pCodeRegMapLiveRanges - pcflow is not a flow object ");
204       continue;
205     }
206     pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
207   }
208
209 #if 0
210   for( pcflow = findNextpCode(pb->pcHead, PC_FLOW); 
211        pcflow != NULL;
212        pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
213
214     regs *r = setFirstItem(PCFL(pcflow)->registers);
215     fprintf(stderr,"flow seq %d\n", pcflow->seq);
216
217     while (r) {
218       fprintf(stderr, "  %s\n",r->name);
219       r = setNextItem(PCFL(pcflow)->registers);
220
221     }
222
223   }
224 #endif
225
226 //  dbg_dumpregusage();
227
228 }
229
230
231 /*-----------------------------------------------------------------*
232  *
233  *-----------------------------------------------------------------*/
234 static void Remove1pcode(pCode *pc, regs *reg)
235 {
236   pCode *pcn=NULL;
237
238   if(!reg || !pc)
239     return;
240
241   deleteSetItem (&(reg->reglives.usedpCodes),pc);
242 /*
243   fprintf(stderr,"removing instruction:\n");
244   pc->print(stderr,pc);
245 */
246   if(PCI(pc)->label) {
247     pcn = findNextInstruction(pc->next);
248
249     if(pcn)
250       PCI(pcn)->label = pBranchAppend(PCI(pcn)->label,PCI(pc)->label);
251   }
252
253   if(PCI(pc)->cline) {
254     if(!pcn)
255       pcn = findNextInstruction(pc->next);
256
257     if(pcn) {
258       if(PCI(pcn)->cline) {
259         //fprintf(stderr, "source line has been optimized completely out\n");
260         //pc->print(stderr,pc);
261       } else {
262         PCI(pcn)->cline = PCI(pc)->cline;
263       }
264     }
265   }
266
267   pc->destruct(pc);
268
269 }
270
271 /*-----------------------------------------------------------------*
272  * void RemoveRegsFromSet(set *regset)
273  *
274  *-----------------------------------------------------------------*/
275 void  RemoveRegsFromSet(set *regset)
276 {
277   regs *reg;
278   int used;
279
280   while(regset) {
281     reg = regset->item;
282     regset = regset->next;
283
284     used = elementsInSet(reg->reglives.usedpCodes);
285
286     if(used <= 1) {
287
288       //fprintf(stderr," reg %s isfree=%d, wasused=%d\n",reg->name,reg->isFree,reg->wasUsed);
289       if(used == 0) {
290         //fprintf(stderr," getting rid of reg %s\n",reg->name);
291         reg->isFree = 1;
292         reg->wasUsed = 0;
293       } else {
294         pCode *pc;
295
296
297         pc = setFirstItem(reg->reglives.usedpCodes);
298
299         if(reg->type == REG_SFR) {
300           //fprintf(stderr, "not removing SFR reg %s even though used only once\n",reg->name);
301           continue;
302         }
303
304
305         if(isPCI(pc)) {
306           if(PCI(pc)->label) {
307             pCode *pcn = findNextInstruction(pc->next);
308
309             if(pcn && PCI(pcn)->label) {
310               //fprintf(stderr,"can't delete instruction with label...\n");
311               //pc->print(stderr,pc);
312               continue;
313             } 
314             /* Move the label to the next instruction */
315
316             PCI(pcn)->label = PCI(pc)->label;
317
318           }
319
320           if(isPCI_SKIP(pc)) {
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);
325           }
326           //fprintf(stderr," removing reg %s because it is used only once\n",reg->name);
327           Remove1pcode(pc, reg);
328           /*
329             unlinkpCode(pc);
330             deleteSetItem (&(reg->reglives.usedpCodes),pc);
331           */
332           reg->isFree = 1;
333           reg->wasUsed = 0;
334           total_registers_saved++;  // debugging stats.
335         }
336       }
337     }
338
339   }
340 }
341 /*-----------------------------------------------------------------*
342  * void RemoveUnusedRegisters(void)
343  *
344  *-----------------------------------------------------------------*/
345 void RemoveUnusedRegisters(void)
346 {
347   /* First, get rid of registers that are used only one time */
348
349
350   RemoveRegsFromSet(dynInternalRegs);
351   RemoveRegsFromSet(dynAllocRegs);
352   RemoveRegsFromSet(dynStackRegs);
353   /*
354     don't do DirectRegs yet - there's a problem with arrays
355   RemoveRegsFromSet(dynDirectRegs);
356   */
357   RemoveRegsFromSet(dynDirectBitRegs);
358
359   if(total_registers_saved) fprintf(stderr, " *** Saved %d registers ***\n", total_registers_saved);
360 }
361
362
363 /*-----------------------------------------------------------------*
364  *
365  *-----------------------------------------------------------------*/
366 static void Remove2pcodes(pCode *pcflow, pCode *pc1, pCode *pc2, regs *reg, int can_free)
367 {
368   if(!reg)
369     return;
370
371   if(pc1)
372     Remove1pcode(pc1, reg);
373
374   if(pc2) {
375     Remove1pcode(pc2, reg);
376     deleteSetItem (&(PCFL(pcflow)->registers), reg);
377
378     if(can_free) {
379       reg->isFree = 1;
380       reg->wasUsed = 0;
381     }
382
383   }
384
385   pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
386 }
387
388 /*-----------------------------------------------------------------*
389  *
390  *-----------------------------------------------------------------*/
391 int regUsedinRange(pCode *pc1, pCode *pc2, regs *reg)
392 {
393   int i=0;
394   regs *testreg;
395
396   do {
397     testreg = getRegFromInstruction(pc1);
398     if(testreg && (testreg->rIdx == reg->rIdx)) {
399       return 1;
400     }
401
402     pc1 = findNextInstruction(pc1->next);
403
404   } while (pc1 && (pc1 != pc2) && (i++ < 100)) ;
405
406   if(i >= 100)
407     fprintf(stderr, "warning, regUsedinRange searched through too many pcodes\n");
408
409   return 0;
410 }
411
412 /*-----------------------------------------------------------------*
413  * void pCodeOptime2pCodes(pCode *pc1, pCode *pc2) 
414  *
415  * ADHOC pattern checking 
416  * Now look for specific sequences that are easy to optimize.
417  * Many of these sequences are characteristic of the compiler
418  * (i.e. it'd probably be a waste of time to apply these adhoc
419  * checks to hand written assembly.)
420  * 
421  *
422  *-----------------------------------------------------------------*/
423 void pCodeOptime2pCodes(pCode *pc1, pCode *pc2, pCode *pcfl_used, regs *reg, int can_free)
424 {
425   pCode *pct1, *pct2;
426   regs  *reg1, *reg2;
427
428   if(pc2->seq < pc1->seq) {
429     pct1 = pc2;
430     pc2 = pc1;
431     pc1 = pct1;
432   }
433
434
435   if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_MOVFW) ){
436
437     /*
438       clrf  reg
439       stuff...
440       movf  reg,w
441
442       can be replaced with
443
444       stuff...
445       movlw 0
446     */
447
448     pCode *newpc;
449     //fprintf(stderr, "   CLRF/MOVFW. instruction after MOVFW is:\n");
450     pct1 = findNextInstruction(pc2->next);
451     //t->print(stderr,t);
452
453     if(PCI(pct1)->op == POC_MOVWF) {
454       newpc = newpCode(POC_CLRF, PCI(pct1)->pcop);
455       pct1->destruct(pct1);
456     } else {
457       newpc = newpCode(POC_MOVLW, newpCodeOpLit(0));
458     }
459
460     pCodeInsertAfter(pc2, newpc);
461     PCI(newpc)->pcflow = PCFL(pcfl_used);
462     newpc->seq = pc2->seq;
463
464     Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
465     total_registers_saved++;  // debugging stats.
466
467   } else if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_IORFW) ){
468     //fprintf(stderr, "   CLRF/IORFW.\n");
469
470     Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
471     total_registers_saved++;  // debugging stats.
472
473   }  else if(PCI(pc1)->op == POC_MOVWF) {
474
475     pct2 = findNextInstruction(pc2->next);
476
477     if(PCI(pc2)->op == POC_MOVFW) {
478       //fprintf(stderr, "   MOVWF/MOVFW. instruction after MOVFW is:\n");
479       //pct2->print(stderr,pct2);
480
481       if(PCI(pct2)->op == POC_MOVWF) {
482         reg2 = getRegFromInstruction(pct2);
483         if(reg2 && !regUsedinRange(pc1,pc2,reg2)) {
484           pct2->seq = pc1->seq;
485           unlinkpCode(pct2);
486           pCodeInsertAfter(pc1,pct2);
487           Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
488           total_registers_saved++;  // debugging stats.
489           return;
490         }
491 /*
492         fprintf(stderr, " couldn't optimize\n");
493         if(reg2)
494           fprintf(stderr, " %s is used in range\n",reg2->name);
495         else
496           fprintf(stderr, " reg2 is NULL\n");
497 */
498       }
499     }
500
501     pct1 = findPrevInstruction(pc1->prev);
502     if(pct1 && 
503        (PCI(pct1)->pcflow == PCI(pc1)->pcflow) && 
504        (PCI(pct1)->op == POC_MOVFW)) {
505
506       reg1 = getRegFromInstruction(pct1);
507       if(reg1 && !regUsedinRange(pc1,pc2,reg1)) {
508         //fprintf(stderr, "   MOVF/MOVFW. \n");
509         /*
510           movf   reg1,w
511           movwf  reg
512
513           stuff...
514           opcode reg,w
515         */
516         pct2 = newpCode(PCI(pc2)->op, PCI(pct1)->pcop);
517         pCodeInsertAfter(pc2, pct2);
518         PCI(pct2)->pcflow = PCFL(pcfl_used);
519         pct2->seq = pc2->seq;
520
521         Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
522         Remove2pcodes(pcfl_used, pct1, NULL, reg1, 0);
523         total_registers_saved++;  // debugging stats.
524
525       }
526     }
527
528
529   }
530
531 }
532
533 /*-----------------------------------------------------------------*
534  * void pCodeRegOptimeRegUsage(pBlock *pb) 
535  *-----------------------------------------------------------------*/
536 void OptimizeRegUsage(set *fregs)
537 {
538   regs *reg;
539   int used;
540
541
542   while(fregs) {
543     pCode *pcfl_used, *pcfl_assigned;
544
545     /* Step through the set by directly accessing the 'next' pointer.
546      * We could also step through by using the set API, but the 
547      * the (debug) calls to print instructions affect the state
548      * of the set pointers */
549
550     reg = fregs->item;
551     fregs = fregs->next;
552
553     if(reg->type == REG_SFR) {
554       //fprintf(stderr,"skipping SFR: %s\n",reg->name);
555       continue;
556     }
557
558     pcfl_used = setFirstItem(reg->reglives.usedpFlows);
559     pcfl_assigned = setFirstItem(reg->reglives.assignedpFlows);
560
561     used = elementsInSet(reg->reglives.usedpCodes);
562     if(used == 2) { 
563
564       /*
565        * In this section, all registers that are used in only in two 
566        * instructions are examined. If possible, they're optimized out.
567        */
568
569       pCode *pc1, *pc2;
570 /*
571       fprintf (stderr, "OptimizeRegUsage: %s  addr=0x%03x rIdx=0x%03x type=%d used=%d\n",
572                reg->name,
573                reg->address,
574                reg->rIdx, reg->type, used);
575 */
576       pc1 = setFirstItem(reg->reglives.usedpCodes);
577       pc2 = setNextItem(reg->reglives.usedpCodes);
578
579       if(pcfl_used && pcfl_assigned) {
580
581         /* 
582            expected case - the register has been assigned a value and is
583            subsequently used 
584         */
585
586         //fprintf(stderr," used only twice\n");
587         if(pcfl_used->seq == pcfl_assigned->seq) {
588
589           //fprintf(stderr, "  and used in same flow\n");
590
591           pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 1);
592
593         } else {
594           // fprintf(stderr, "  and used in different flows\n");
595
596         }
597
598       } else if(pcfl_used) {
599
600         /*
601           register has been used twice without ever being assigned */
602         //fprintf(stderr,"WARNING %s: reg %s used without being assigned\n",__FUNCTION__,reg->name);
603
604       } else {
605         //fprintf(stderr,"WARNING %s: reg %s assigned without being used\n",__FUNCTION__,reg->name);
606         Remove2pcodes(pcfl_assigned, pc1, pc2, reg, 1);
607         total_registers_saved++;  // debugging stats.
608       }
609     } else {
610
611       /* register has been used either once, or more than twice */
612
613       if(used && !pcfl_used && pcfl_assigned) {
614         pCode *pc;
615
616         //fprintf(stderr,"WARNING %s: reg %s assigned without being used\n",__FUNCTION__,reg->name);
617
618         pc = setFirstItem(reg->reglives.usedpCodes);
619         while(pc) {
620
621           pcfl_assigned = PCODE(PCI(pc)->pcflow);
622           Remove1pcode(pc, reg);
623
624           deleteSetItem (&(PCFL(pcfl_assigned)->registers), reg);
625           /*
626           deleteSetItem (&(reg->reglives.usedpCodes),pc);
627           pc->destruct(pc);
628           */
629           pc = setNextItem(reg->reglives.usedpCodes);
630         }
631
632
633         reg->isFree = 1;
634         reg->wasUsed = 0;
635
636         total_registers_saved++;  // debugging stats.
637       } else if(used > 2) {
638
639         /* examine the number of times this register is used */
640
641       }
642     }
643
644   }
645
646 }
647 /*-----------------------------------------------------------------*
648  * void pCodeRegOptimeRegUsage(pBlock *pb) 
649  *-----------------------------------------------------------------*/
650 void pCodeRegOptimizeRegUsage(void)
651 {
652
653   int passes = 4;
654   int saved = 0;
655   int t = total_registers_saved;
656
657   do {
658     saved = total_registers_saved;
659
660     /* Identify registers used in one flow sequence */
661     OptimizeRegUsage(dynAllocRegs);
662     OptimizeRegUsage(dynStackRegs);
663     OptimizeRegUsage(dynDirectRegs);
664
665     if(total_registers_saved != saved)
666       fprintf(stderr, " *** Saved %d registers, total saved %d ***\n", total_registers_saved-saved,total_registers_saved);
667
668
669   } while( passes-- && (total_registers_saved != saved));
670
671   if(total_registers_saved == t) 
672     fprintf(stderr, "No registers saved on this pass\n");
673
674
675 /*
676   fprintf(stderr,"dynamically allocated regs:\n");
677   dbg_regusage(dynAllocRegs);
678   fprintf(stderr,"stack regs:\n");
679   dbg_regusage(dynStackRegs);
680   fprintf(stderr,"direct regs:\n");
681   dbg_regusage(dynDirectRegs);
682 */
683 }
684
685
686 /*-----------------------------------------------------------------*
687  * void RegsUnMapLiveRanges(set *regset)
688  *
689  *-----------------------------------------------------------------*/
690 void  RegsSetUnMapLiveRanges(set *regset)
691 {
692   regs *reg;
693
694   while(regset) {
695     reg = regset->item;
696     regset = regset->next;
697
698     
699     deleteSet(&reg->reglives.usedpCodes);
700     deleteSet(&reg->reglives.usedpFlows);
701     deleteSet(&reg->reglives.assignedpFlows);
702
703   }
704
705 }
706
707 void  RegsUnMapLiveRanges(void)
708 {
709
710   RegsSetUnMapLiveRanges(dynAllocRegs);
711   RegsSetUnMapLiveRanges(dynStackRegs);
712   RegsSetUnMapLiveRanges(dynDirectRegs);
713   RegsSetUnMapLiveRanges(dynProcessorRegs);
714   RegsSetUnMapLiveRanges(dynDirectBitRegs);
715   RegsSetUnMapLiveRanges(dynInternalRegs);
716
717 }