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