git.gag.com Git - fw/sdcc/blob - 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 void unlinkpCode(pCode *pc);
  42
  43 int total_registers_saved=0;
  44
  45 /*-----------------------------------------------------------------*
  46  * void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
  47  *-----------------------------------------------------------------*/
  48 /*
  49 void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
  50 {
  51
  52   if(!reg || ! pcfl || !isPCFL(pcflow))
  53     return;
  54
  55   if(!pcfl->registers)
  56     pcfl->registers =  newSet();
  57
  58 }
  59 */
  60
  61
  62 /*-----------------------------------------------------------------*
  63  *
  64  *-----------------------------------------------------------------*/
  65 void dbg_regusage(set *fregs)
  66 {
  67   regs *reg;
  68   pCode *pcfl;
  69   pCode *pc;
  70
  71
  72   for (reg = setFirstItem(fregs) ; reg ;
  73        reg = setNextItem(fregs)) {
  74
  75     fprintf (stderr, "%s  addr=0x%03x rIdx=0x%03x",
  76              reg->name,
  77              reg->address,
  78              reg->rIdx);
  79
  80     pcfl = setFirstItem(reg->reglives.usedpFlows);
  81     if(pcfl)
  82       fprintf(stderr, "\n   used in seq");
  83
  84     while(pcfl) {
  85       fprintf(stderr," 0x%03x",pcfl->seq);
  86       pcfl = setNextItem(reg->reglives.usedpFlows);
  87     }
  88
  89     pcfl = setFirstItem(reg->reglives.assignedpFlows);
  90     if(pcfl)
  91       fprintf(stderr, "\n   assigned in seq");
  92
  93     while(pcfl) {
  94       fprintf(stderr," 0x%03x",pcfl->seq);
  95       pcfl = setNextItem(reg->reglives.assignedpFlows);
  96     }
  97
  98     pc = setFirstItem(reg->reglives.usedpCodes);
  99     if(pc)
 100       fprintf(stderr, "\n   used in instructions ");
 101
 102     while(pc) {
 103       pcfl = PCODE(PCI(pc)->pcflow);
 104       if(pcfl)
 105         fprintf(stderr," 0x%03x:",pcfl->seq);
 106       fprintf(stderr,"0x%03x",pc->seq);
 107
 108       pc = setNextItem(reg->reglives.usedpCodes);
 109     }
 110
 111     fprintf(stderr, "\n");
 112
 113   }
 114 }
 115
 116 /*-----------------------------------------------------------------*
 117  *
 118  *-----------------------------------------------------------------*/
 119 void dbg_dumpregusage(void)
 120 {
 121
 122   fprintf(stderr,"***  Register Usage  ***\n");
 123   fprintf(stderr,"InternalRegs:\n");
 124   dbg_regusage(dynInternalRegs);
 125   fprintf(stderr,"AllocRegs:\n");
 126   dbg_regusage(dynAllocRegs);
 127   fprintf(stderr,"StackRegs:\n");
 128   dbg_regusage(dynStackRegs);
 129   fprintf(stderr,"DirectRegs:\n");
 130   dbg_regusage(dynDirectRegs);
 131   fprintf(stderr,"DirectBitRegs:\n");
 132   dbg_regusage(dynDirectBitRegs);
 133   fprintf(stderr,"ProcessorRegs:\n");
 134   dbg_regusage(dynProcessorRegs);
 135
 136 }
 137
 138
 139 /*-----------------------------------------------------------------*
 140  * void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
 141  *-----------------------------------------------------------------*/
 142 void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
 143 {
 144
 145   pCode *pc=NULL;
 146   pCode *pcprev=NULL;
 147
 148   regs *reg;
 149
 150   if(!pcfl)
 151     return;
 152
 153
 154   pc = findNextInstruction(pcfl->pc.next);
 155
 156   while(isPCinFlow(pc,PCODE(pcfl))) {
 157
 158
 159     reg = getRegFromInstruction(pc);
 160
 161     if(reg) {
 162 /*
 163       fprintf(stderr, "flow seq %d, inst seq %d  %s  ",PCODE(pcfl)->seq,pc->seq,reg->name);
 164       fprintf(stderr, "addr = 0x%03x, type = %d  rIdx=0x%03x\n",
 165               reg->address,reg->type,reg->rIdx);
 166 */
 167
 168       addSetIfnotP(& (PCFL(pcfl)->registers), reg);
 169
 170       if(PCC_REGISTER & PCI(pc)->inCond)
 171         addSetIfnotP(& (reg->reglives.usedpFlows), pcfl);
 172
 173       if(PCC_REGISTER & PCI(pc)->outCond)
 174         addSetIfnotP(& (reg->reglives.assignedpFlows), pcfl);
 175
 176       addSetIfnotP(& (reg->reglives.usedpCodes), pc);
 177     }
 178
 179
 180     pcprev = pc;
 181     pc = findNextInstruction(pc->next);
 182
 183   }
 184
 185 }
 186
 187 /*-----------------------------------------------------------------*
 188  * void pCodeRegMapLiveRanges(pBlock *pb)
 189  *-----------------------------------------------------------------*/
 190 void pCodeRegMapLiveRanges(pBlock *pb)
 191 {
 192   pCode *pcflow;
 193
 194   for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
 195        pcflow != NULL;
 196        pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
 197
 198     if(!isPCFL(pcflow)) {
 199       fprintf(stderr, "pCodeRegMapLiveRanges - pcflow is not a flow object ");
 200       continue;
 201     }
 202     pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
 203   }
 204
 205
 206   for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
 207        pcflow != NULL;
 208        pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
 209
 210     regs *r = setFirstItem(PCFL(pcflow)->registers);
 211     //fprintf(stderr,"flow seq %d\n", pcflow->seq);
 212     while (r) {
 213       //fprintf(stderr, "  %s\n",r->name);
 214       r = setNextItem(PCFL(pcflow)->registers);
 215
 216     }
 217
 218   }
 219
 220   //dbg_dumpregusage();
 221
 222 }
 223
 224
 225 /*-----------------------------------------------------------------*
 226  * void RemoveRegsFromSet(set *regset)
 227  *
 228  *-----------------------------------------------------------------*/
 229 void  RemoveRegsFromSet(set *regset)
 230 {
 231   regs *reg;
 232   int used;
 233   for (reg = setFirstItem(regset) ; reg ;
 234        reg = setNextItem(regset)) {
 235
 236
 237     used = elementsInSet(reg->reglives.usedpCodes);
 238
 239     if(used <= 1) {
 240
 241       //fprintf(stderr," reg %s isfree=%d, wasused=%d\n",reg->name,reg->isFree,reg->wasUsed);
 242
 243       if(used == 0) {
 244         //fprintf(stderr," getting rid of reg %s\n",reg->name);
 245         reg->isFree = 1;
 246         reg->wasUsed = 0;
 247       } else {
 248         pCode *pc;
 249
 250
 251         pc = setFirstItem(reg->reglives.usedpCodes);
 252         if(isPCI(pc)) {
 253           if(PCI(pc)->label) {
 254             pCode *pcn = findNextInstruction(pc->next);
 255
 256             if(pcn && PCI(pcn)->label) {
 257               //fprintf(stderr,"can't delete instruction with label...\n");
 258               //pc->print(stderr,pc);
 259               continue;
 260             }
 261             /* Move the label to the next instruction */
 262
 263             PCI(pcn)->label = PCI(pc)->label;
 264
 265           }
 266
 267           if(isPCI_SKIP(pc))
 268             fprintf(stderr, "WARNING, a skip instruction is being optimized out\n");
 269
 270           //fprintf(stderr," removing reg %s because it is used only once\n",reg->name);
 271           unlinkpCode(pc);
 272           deleteSetItem (&(reg->reglives.usedpCodes),pc);
 273           reg->isFree = 1;
 274           reg->wasUsed = 0;
 275           total_registers_saved++;  // debugging stats.
 276         }
 277       }
 278     }
 279
 280   }
 281 }
 282 /*-----------------------------------------------------------------*
 283  * void RemoveUnusedRegisters(void)
 284  *
 285  *-----------------------------------------------------------------*/
 286 void RemoveUnusedRegisters(void)
 287 {
 288   /* First, get rid of registers that are used only one time */
 289
 290
 291   RemoveRegsFromSet(dynInternalRegs);
 292   RemoveRegsFromSet(dynAllocRegs);
 293   RemoveRegsFromSet(dynStackRegs);
 294   /*
 295     don't do DirectRegs yet - there's a problem with arrays
 296   RemoveRegsFromSet(dynDirectRegs);
 297   */
 298   RemoveRegsFromSet(dynDirectBitRegs);
 299
 300   if(total_registers_saved) fprintf(stderr, " *** Saved %d registers ***\n", total_registers_saved);
 301 }
 302
 303
 304 /*-----------------------------------------------------------------*
 305  *
 306  *-----------------------------------------------------------------*/
 307 static void Remove2pcodes(pCode *pcflow, pCode *pc1, pCode *pc2, regs *reg)
 308 {
 309
 310   deleteSetItem (&(reg->reglives.usedpCodes),pc1);
 311   deleteSetItem (&(reg->reglives.usedpCodes),pc2);
 312   deleteSetItem (&(PCFL(pcflow)->registers), reg);
 313
 314   pc1->destruct(pc1);
 315   pc2->destruct(pc2);
 316
 317   reg->isFree = 1;
 318   reg->wasUsed = 0;
 319   pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
 320 }
 321
 322 /*-----------------------------------------------------------------*
 323  *
 324  *-----------------------------------------------------------------*/
 325 int regUsedinRange(pCode *pc1, pCode *pc2, regs *reg)
 326 {
 327   int i=0;
 328   regs *testreg;
 329
 330   do {
 331     testreg = getRegFromInstruction(pc1);
 332     if(testreg && (testreg->rIdx == reg->rIdx)) {
 333       return 1;
 334     }
 335
 336     pc1 = findNextInstruction(pc1->next);
 337
 338   } while (pc1 && (pc1 != pc2) && (i++ < 100)) ;
 339
 340   if(i >= 100)
 341     fprintf(stderr, "warning, regUsedinRange searched through too many pcodes\n");
 342
 343   return 0;
 344 }
 345
 346 /*-----------------------------------------------------------------*
 347  * void pCodeRegOptimeRegUsage(pBlock *pb)
 348  *-----------------------------------------------------------------*/
 349 void OptimizeRegUsage(set *fregs)
 350 {
 351   regs *reg;
 352   int used;
 353
 354
 355   while(fregs) {
 356
 357     /* Step through the set by directly accessing the 'next' pointer.
 358      * We could also step through by using the set API, but the
 359      * the (debug) calls to print instructions affect the state
 360      * of the set pointers */
 361
 362     reg = fregs->item;
 363     fregs = fregs->next;
 364
 365     used = elementsInSet(reg->reglives.usedpCodes);
 366
 367     if(used == 2) {
 368
 369       pCode *pcfl_used, *pcfl_assigned;
 370       pCode *pc1, *pc2;
 371       pCode *t;
 372
 373       /* This register has only been used twice. Chances are we can
 374          get rid of it */
 375 /*
 376       fprintf (stderr, "OptimizeRegUsage: %s  addr=0x%03x rIdx=0x%03x  used=%d\n",
 377                reg->name,
 378                reg->address,
 379                reg->rIdx, used);
 380 */
 381       pcfl_used = setFirstItem(reg->reglives.usedpFlows);
 382       pcfl_assigned = setFirstItem(reg->reglives.assignedpFlows);
 383
 384       pc1 = setFirstItem(reg->reglives.usedpCodes);
 385       pc2 = setNextItem(reg->reglives.usedpCodes);
 386
 387       if(pcfl_used && pcfl_assigned) {
 388
 389         /*
 390            expected case - the register has been assigned a value and is
 391            subsequently used
 392         */
 393         //fprintf(stderr," used only twice\n");
 394         if(pcfl_used->seq == pcfl_assigned->seq) {
 395
 396           //fprintf(stderr, "  and used in same flow\n");
 397           if(pc2->seq < pc1->seq) {
 398             t = pc2;
 399             pc2 = pc1;
 400             pc1 = t;
 401           }
 402
 403           //pc1->print(stderr,pc1);
 404           //pc2->print(stderr,pc2);
 405
 406
 407           /* ADHOC pattern checking */
 408           if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_MOVFW) ){
 409             pCode *newpc;
 410             //fprintf(stderr, "   CLRF/MOVFW. instruction after MOVFW is:\n");
 411             t = findNextInstruction(pc2->next);
 412             //t->print(stderr,t);
 413
 414             if(PCI(t)->op == POC_MOVWF) {
 415               newpc = newpCode(POC_CLRF, PCI(t)->pcop);
 416             } else {
 417               newpc = newpCode(POC_MOVLW, newpCodeOpLit(0));
 418             }
 419
 420             PCI(newpc)->pcflow = PCFL(pcfl_used);
 421             newpc->seq = t->seq;
 422
 423             pCodeInsertAfter(t, newpc);
 424
 425             t->destruct(t);
 426             Remove2pcodes(pcfl_used, pc1, pc2, reg);
 427             total_registers_saved++;  // debugging stats.
 428
 429           } else if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_IORFW) ){
 430             //fprintf(stderr, "   CLRF/IORWF.\n");
 431
 432             Remove2pcodes(pcfl_used, pc1, pc2, reg);
 433             total_registers_saved++;  // debugging stats.
 434
 435           }  else if((PCI(pc1)->op == POC_MOVWF) && (PCI(pc2)->op == POC_MOVFW) ){
 436             //fprintf(stderr, "   MOVWF/MOVFW. instruction after MOVFW is:\n");
 437             t = findNextInstruction(pc2->next);
 438             // t->print(stderr,t);
 439
 440             if(PCI(t)->op == POC_MOVWF) {
 441               regs *nextreg = getRegFromInstruction(t);
 442               if(nextreg && !regUsedinRange(pc1,pc2,nextreg)) {
 443                 t->seq = pc1->seq;
 444                 unlinkpCode(t);
 445                 pCodeInsertAfter(pc1,t);
 446                 Remove2pcodes(pcfl_used, pc1, pc2, reg);
 447                 total_registers_saved++;  // debugging stats.
 448               }
 449             }
 450           }
 451
 452         } else {
 453           // fprintf(stderr, "  and used in different flows\n");
 454
 455           //pc1->print(stderr,pc1);
 456           //pc2->print(stderr,pc2);
 457         }
 458
 459       } else if(pcfl_used) {
 460
 461         /*
 462           register has been used twice without ever being assigned */
 463         fprintf(stderr,"WARNING %s: reg %s used without being assigned\n",__FUNCTION__,reg->name);
 464       } else {
 465         fprintf(stderr,"WARNING %s: reg %s assigned without being used\n",__FUNCTION__,reg->name);
 466       }
 467     } else {
 468       //if(used) fprintf (stderr, "  over used OptimizeRegUsage: %s  used=%d\n", reg->name, used);
 469
 470     }
 471
 472   }
 473
 474 #if 0
 475     pcfl = setFirstItem(reg->reglives.usedpFlows);
 476     if(pcfl)
 477       fprintf(stderr, "\n   used in seq");
 478
 479     while(pcfl) {
 480       fprintf(stderr," 0x%03x",pcfl->seq);
 481       pcfl = setNextItem(reg->reglives.usedpFlows);
 482     }
 483
 484     pcfl = setFirstItem(reg->reglives.assignedpFlows);
 485     if(pcfl)
 486       fprintf(stderr, "\n   assigned in seq");
 487
 488     while(pcfl) {
 489       fprintf(stderr," 0x%03x",pcfl->seq);
 490       pcfl = setNextItem(reg->reglives.assignedpFlows);
 491     }
 492
 493     pc = setFirstItem(reg->reglives.usedpCodes);
 494     if(pc)
 495       fprintf(stderr, "\n   used in instructions ");
 496
 497     while(pc) {
 498       pcfl = PCODE(PCI(pc)->pcflow);
 499       if(pcfl)
 500         fprintf(stderr," 0x%03x:",pcfl->seq);
 501       fprintf(stderr,"0x%03x",pc->seq);
 502
 503       pc = setNextItem(reg->reglives.usedpCodes);
 504     }
 505
 506     fprintf(stderr, "\n");
 507
 508   }
 509 #endif
 510 }
 511 /*-----------------------------------------------------------------*
 512  * void pCodeRegOptimeRegUsage(pBlock *pb)
 513  *-----------------------------------------------------------------*/
 514 void pCodeRegOptimizeRegUsage(void)
 515 {
 516
 517   int passes = 4;
 518   int saved = 0;
 519
 520   do {
 521     saved = total_registers_saved;
 522
 523     /* Identify registers used in one flow sequence */
 524     OptimizeRegUsage(dynAllocRegs);
 525
 526     if(total_registers_saved != saved)
 527       fprintf(stderr, " *** Saved %d registers, total saved %d ***\n", total_registers_saved-saved,total_registers_saved);
 528
 529
 530   } while( passes-- && (total_registers_saved != saved));
 531
 532 }