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 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
 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     while (r) {
 217       //fprintf(stderr, "  %s\n",r->name);
 218       r = setNextItem(PCFL(pcflow)->registers);
 219
 220     }
 221
 222   }
 223
 224 //  dbg_dumpregusage();
 225
 226 }
 227
 228
 229 /*-----------------------------------------------------------------*
 230  *
 231  *-----------------------------------------------------------------*/
 232 static void Remove1pcode(pCode *pc, regs *reg)
 233 {
 234   pCode *pcn=NULL;
 235
 236   if(!reg || !pc)
 237     return;
 238
 239   deleteSetItem (&(reg->reglives.usedpCodes),pc);
 240 /*
 241   fprintf(stderr,"removing instruction:\n");
 242   pc->print(stderr,pc);
 243 */
 244   if(PCI(pc)->label) {
 245     pcn = findNextInstruction(pc->next);
 246
 247     if(pcn)
 248       PCI(pcn)->label = pBranchAppend(PCI(pcn)->label,PCI(pc)->label);
 249   }
 250
 251   if(PCI(pc)->cline) {
 252     if(!pcn)
 253       pcn = findNextInstruction(pc->next);
 254
 255     if(pcn) {
 256       if(PCI(pcn)->cline) {
 257         //fprintf(stderr, "source line has been optimized completely out\n");
 258         //pc->print(stderr,pc);
 259       } else {
 260         PCI(pcn)->cline = PCI(pc)->cline;
 261       }
 262     }
 263   }
 264
 265   pc->destruct(pc);
 266
 267 }
 268
 269 /*-----------------------------------------------------------------*
 270  * void RemoveRegsFromSet(set *regset)
 271  *
 272  *-----------------------------------------------------------------*/
 273 void  RemoveRegsFromSet(set *regset)
 274 {
 275   regs *reg;
 276   int used;
 277
 278   while(regset) {
 279     reg = regset->item;
 280     regset = regset->next;
 281
 282 /*
 283   for (reg = setFirstItem(regset) ; reg ;
 284        reg = setNextItem(regset)) {
 285 */
 286     used = elementsInSet(reg->reglives.usedpCodes);
 287
 288     if(used <= 1) {
 289
 290       //fprintf(stderr," reg %s isfree=%d, wasused=%d\n",reg->name,reg->isFree,reg->wasUsed);
 291       if(used == 0) {
 292         //fprintf(stderr," getting rid of reg %s\n",reg->name);
 293         reg->isFree = 1;
 294         reg->wasUsed = 0;
 295       } else {
 296         pCode *pc;
 297
 298
 299         pc = setFirstItem(reg->reglives.usedpCodes);
 300
 301         if(reg->type == REG_SFR) {
 302           //fprintf(stderr, "not removing SFR reg %s even though used only once\n",reg->name);
 303           continue;
 304         }
 305
 306
 307         if(isPCI(pc)) {
 308           if(PCI(pc)->label) {
 309             pCode *pcn = findNextInstruction(pc->next);
 310
 311             if(pcn && PCI(pcn)->label) {
 312               //fprintf(stderr,"can't delete instruction with label...\n");
 313               //pc->print(stderr,pc);
 314               continue;
 315             }
 316             /* Move the label to the next instruction */
 317
 318             PCI(pcn)->label = PCI(pc)->label;
 319
 320           }
 321
 322           if(isPCI_SKIP(pc)) {
 323             regs *r = getRegFromInstruction(pc);
 324             fprintf(stderr, "WARNING, a skip instruction is being optimized out\n");
 325             pc->print(stderr,pc);
 326             fprintf(stderr,"reg %s, type =%d\n",r->name, r->type);
 327           }
 328           //fprintf(stderr," removing reg %s because it is used only once\n",reg->name);
 329           Remove1pcode(pc, reg);
 330           /*
 331             unlinkpCode(pc);
 332             deleteSetItem (&(reg->reglives.usedpCodes),pc);
 333           */
 334           reg->isFree = 1;
 335           reg->wasUsed = 0;
 336           total_registers_saved++;  // debugging stats.
 337         }
 338       }
 339     }
 340
 341   }
 342 }
 343 /*-----------------------------------------------------------------*
 344  * void RemoveUnusedRegisters(void)
 345  *
 346  *-----------------------------------------------------------------*/
 347 void RemoveUnusedRegisters(void)
 348 {
 349   /* First, get rid of registers that are used only one time */
 350
 351
 352   RemoveRegsFromSet(dynInternalRegs);
 353   RemoveRegsFromSet(dynAllocRegs);
 354   RemoveRegsFromSet(dynStackRegs);
 355   /*
 356     don't do DirectRegs yet - there's a problem with arrays
 357   RemoveRegsFromSet(dynDirectRegs);
 358   */
 359   RemoveRegsFromSet(dynDirectBitRegs);
 360
 361   if(total_registers_saved) fprintf(stderr, " *** Saved %d registers ***\n", total_registers_saved);
 362 }
 363
 364
 365 /*-----------------------------------------------------------------*
 366  *
 367  *-----------------------------------------------------------------*/
 368 static void Remove2pcodes(pCode *pcflow, pCode *pc1, pCode *pc2, regs *reg)
 369 {
 370   if(!reg)
 371     return;
 372
 373   if(pc1)
 374     Remove1pcode(pc1, reg);
 375
 376   if(pc2) {
 377     Remove1pcode(pc2, reg);
 378     deleteSetItem (&(PCFL(pcflow)->registers), reg);
 379
 380     reg->isFree = 1;
 381     reg->wasUsed = 0;
 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 pCodeRegOptimeRegUsage(pBlock *pb)
 414  *-----------------------------------------------------------------*/
 415 void OptimizeRegUsage(set *fregs)
 416 {
 417   regs *reg;
 418   int used;
 419
 420
 421   while(fregs) {
 422       pCode *pcfl_used, *pcfl_assigned;
 423
 424     /* Step through the set by directly accessing the 'next' pointer.
 425      * We could also step through by using the set API, but the
 426      * the (debug) calls to print instructions affect the state
 427      * of the set pointers */
 428
 429     reg = fregs->item;
 430     fregs = fregs->next;
 431
 432     if(reg->type == REG_SFR) {
 433       //fprintf(stderr,"skipping SFR: %s\n",reg->name);
 434       continue;
 435     }
 436
 437     pcfl_used = setFirstItem(reg->reglives.usedpFlows);
 438     pcfl_assigned = setFirstItem(reg->reglives.assignedpFlows);
 439
 440     used = elementsInSet(reg->reglives.usedpCodes);
 441     if(used == 2) {
 442
 443       /*
 444        * In this section, all registers that are used in only in two
 445        * instructions are examined. If possible, they're optimized out.
 446        */
 447
 448       pCode *pc1, *pc2;
 449       pCode *pct1, *pct2; /* two temporaries */
 450       regs  *reg1, *reg2;
 451
 452 /*
 453       fprintf (stderr, "OptimizeRegUsage: %s  addr=0x%03x rIdx=0x%03x type=%d used=%d\n",
 454                reg->name,
 455                reg->address,
 456                reg->rIdx, reg->type, used);
 457 */
 458       pc1 = setFirstItem(reg->reglives.usedpCodes);
 459       pc2 = setNextItem(reg->reglives.usedpCodes);
 460
 461       if(pcfl_used && pcfl_assigned) {
 462
 463         /*
 464            expected case - the register has been assigned a value and is
 465            subsequently used
 466         */
 467
 468         //fprintf(stderr," used only twice\n");
 469         if(pcfl_used->seq == pcfl_assigned->seq) {
 470
 471           //fprintf(stderr, "  and used in same flow\n");
 472           if(pc2->seq < pc1->seq) {
 473             pct1 = pc2;
 474             pc2 = pc1;
 475             pc1 = pct1;
 476           }
 477
 478           //pc1->print(stderr,pc1);
 479           //pc2->print(stderr,pc2);
 480
 481
 482           /* ADHOC pattern checking
 483            * Now look for specific sequences that are easy to optimize.
 484            * Many of these sequences are characteristic of the compiler
 485            * (i.e. it'd probably be a waste of time to apply these adhoc
 486            * checks to hand written assembly.)
 487            *
 488            */
 489           if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_MOVFW) ){
 490
 491             /*
 492                  clrf  reg
 493                  stuff...
 494                  movf  reg,w
 495
 496                  can be replaced with
 497
 498                  stuff...
 499                  movlw 0
 500             */
 501
 502             pCode *newpc;
 503             //fprintf(stderr, "   CLRF/MOVFW. instruction after MOVFW is:\n");
 504             pct1 = findNextInstruction(pc2->next);
 505             //t->print(stderr,t);
 506
 507             if(PCI(pct1)->op == POC_MOVWF) {
 508               newpc = newpCode(POC_CLRF, PCI(pct1)->pcop);
 509               pct1->destruct(pct1);
 510             } else {
 511               newpc = newpCode(POC_MOVLW, newpCodeOpLit(0));
 512             }
 513
 514             pCodeInsertAfter(pc2, newpc);
 515             PCI(newpc)->pcflow = PCFL(pcfl_used);
 516             newpc->seq = pc2->seq;
 517
 518             Remove2pcodes(pcfl_used, pc1, pc2, reg);
 519             total_registers_saved++;  // debugging stats.
 520
 521           } else if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_IORFW) ){
 522             //fprintf(stderr, "   CLRF/IORWF.\n");
 523
 524             Remove2pcodes(pcfl_used, pc1, pc2, reg);
 525             total_registers_saved++;  // debugging stats.
 526
 527           }  else if(PCI(pc1)->op == POC_MOVWF) {
 528
 529             pct2 = findNextInstruction(pc2->next);
 530
 531             if(PCI(pc2)->op == POC_MOVFW) {
 532               //fprintf(stderr, "   MOVWF/MOVFW. instruction after MOVFW is:\n");
 533               // t->print(stderr,t);
 534
 535               if(PCI(pct2)->op == POC_MOVWF) {
 536                 reg2 = getRegFromInstruction(pct2);
 537                 if(reg2 && !regUsedinRange(pc1,pc2,reg2)) {
 538                   pct2->seq = pc1->seq;
 539                   unlinkpCode(pct2);
 540                   pCodeInsertAfter(pc1,pct2);
 541                   Remove2pcodes(pcfl_used, pc1, pc2, reg);
 542                   total_registers_saved++;  // debugging stats.
 543                   continue;
 544                 }
 545               }
 546             }
 547
 548             pct1 = findPrevInstruction(pc1->prev);
 549             if(pct1 &&
 550                (PCI(pct1)->pcflow == PCI(pc1)->pcflow) &&
 551                (PCI(pct1)->op == POC_MOVFW)) {
 552
 553               reg1 = getRegFromInstruction(pct1);
 554               if(reg1 && !regUsedinRange(pc1,pc2,reg1)) {
 555                 //fprintf(stderr, "   MOVF/MOVFW. \n");
 556               /*
 557                 movf   reg1,w
 558                 movwf  reg
 559
 560                 stuff...
 561                 opcode reg,w
 562               */
 563                 pct2 = newpCode(PCI(pc2)->op, PCI(pct1)->pcop);
 564                 pCodeInsertAfter(pc2, pct2);
 565                 PCI(pct2)->pcflow = PCFL(pcfl_used);
 566                 pct2->seq = pc2->seq;
 567
 568                 Remove2pcodes(pcfl_used, pc1, pc2, reg);
 569                 Remove2pcodes(pcfl_used, pct1, NULL, reg1);
 570                 total_registers_saved++;  // debugging stats.
 571
 572               }
 573             }
 574
 575
 576           }
 577
 578         } else {
 579           // fprintf(stderr, "  and used in different flows\n");
 580
 581           //pc1->print(stderr,pc1);
 582           //pc2->print(stderr,pc2);
 583         }
 584
 585       } else if(pcfl_used) {
 586
 587         /*
 588           register has been used twice without ever being assigned */
 589         //fprintf(stderr,"WARNING %s: reg %s used without being assigned\n",__FUNCTION__,reg->name);
 590
 591       } else {
 592         //fprintf(stderr,"WARNING %s: reg %s assigned without being used\n",__FUNCTION__,reg->name);
 593         Remove2pcodes(pcfl_assigned, pc1, pc2, reg);
 594         total_registers_saved++;  // debugging stats.
 595       }
 596     } else {
 597
 598       if(used && !pcfl_used && pcfl_assigned) {
 599         pCode *pc;
 600
 601         //fprintf(stderr,"WARNING %s: reg %s assigned without being used\n",__FUNCTION__,reg->name);
 602
 603         pc = setFirstItem(reg->reglives.usedpCodes);
 604         while(pc) {
 605
 606           pcfl_assigned = PCODE(PCI(pc)->pcflow);
 607           Remove1pcode(pc, reg);
 608
 609           deleteSetItem (&(PCFL(pcfl_assigned)->registers), reg);
 610           /*
 611           deleteSetItem (&(reg->reglives.usedpCodes),pc);
 612           pc->destruct(pc);
 613           */
 614           pc = setNextItem(reg->reglives.usedpCodes);
 615         }
 616
 617
 618         reg->isFree = 1;
 619         reg->wasUsed = 0;
 620
 621         total_registers_saved++;  // debugging stats.
 622       }
 623
 624     }
 625
 626   }
 627
 628 }
 629 /*-----------------------------------------------------------------*
 630  * void pCodeRegOptimeRegUsage(pBlock *pb)
 631  *-----------------------------------------------------------------*/
 632 void pCodeRegOptimizeRegUsage(void)
 633 {
 634
 635   int passes = 4;
 636   int saved = 0;
 637
 638   do {
 639     saved = total_registers_saved;
 640
 641     /* Identify registers used in one flow sequence */
 642     OptimizeRegUsage(dynAllocRegs);
 643     OptimizeRegUsage(dynStackRegs);
 644     OptimizeRegUsage(dynDirectRegs);
 645
 646     if(total_registers_saved != saved)
 647       fprintf(stderr, " *** Saved %d registers, total saved %d ***\n", total_registers_saved-saved,total_registers_saved);
 648
 649
 650   } while( passes-- && (total_registers_saved != saved));
 651 /*
 652   fprintf(stderr,"dynamically allocated regs:\n");
 653   dbg_regusage(dynAllocRegs);
 654   fprintf(stderr,"stack regs:\n");
 655   dbg_regusage(dynStackRegs);
 656   fprintf(stderr,"direct regs:\n");
 657   dbg_regusage(dynDirectRegs);
 658 */
 659
 660
 661 }