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 #include "main.h"
  39
  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 extern int pCodeSearchCondition(pCode *pc, unsigned int cond, int contIfSkip);
  45 char *pCode2str(char *str, int size, pCode *pc);
  46 void SAFE_snprintf(char **str, size_t *size, const  char  *format, ...);
  47 //static int sameRegs (const regs *reg1, const regs *reg2);
  48
  49 int total_registers_saved=0;
  50 int register_optimization=1;
  51
  52 /*-----------------------------------------------------------------*
  53 * void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
  54 *-----------------------------------------------------------------*/
  55 /*
  56 void AddRegToFlow(regs *reg, pCodeFlow *pcfl)
  57 {
  58
  59         if(!reg || ! pcfl || !isPCFL(pcflow))
  60         return;
  61
  62         if(!pcfl->registers)
  63         pcfl->registers =  newSet();
  64
  65 }
  66 */
  67
  68
  69 /*-----------------------------------------------------------------*
  70 *
  71 *-----------------------------------------------------------------*/
  72 void dbg_regusage(set *fregs)
  73 {
  74         regs *reg;
  75         pCode *pcfl;
  76         pCode *pc;
  77
  78
  79         for (reg = setFirstItem(fregs) ; reg ;
  80         reg = setNextItem(fregs)) {
  81
  82                 if(elementsInSet(reg->reglives.usedpCodes)) {
  83
  84                         fprintf (stderr, "%s  addr=0x%03x rIdx=0x%03x",
  85                                 reg->name,
  86                                 reg->address,
  87                                 reg->rIdx);
  88
  89                         pcfl = setFirstItem(reg->reglives.usedpFlows);
  90                         if(pcfl)
  91                                 fprintf(stderr, "\n   used in seq");
  92
  93                         while(pcfl) {
  94                                 fprintf(stderr," 0x%03x",pcfl->seq);
  95                                 pcfl = setNextItem(reg->reglives.usedpFlows);
  96                         }
  97
  98                         pcfl = setFirstItem(reg->reglives.assignedpFlows);
  99                         if(pcfl)
 100                                 fprintf(stderr, "\n   assigned in seq");
 101
 102                         while(pcfl) {
 103                                 fprintf(stderr," 0x%03x",pcfl->seq);
 104                                 pcfl = setNextItem(reg->reglives.assignedpFlows);
 105                         }
 106
 107                         pc = setFirstItem(reg->reglives.usedpCodes);
 108                         if(pc)
 109                                 fprintf(stderr, "\n   used in instructions ");
 110
 111                         while(pc) {
 112                                 pcfl = PCODE(PCI(pc)->pcflow);
 113                                 if(pcfl)
 114                                         fprintf(stderr," 0x%03x:",pcfl->seq);
 115                                 fprintf(stderr,"0x%03x",pc->seq);
 116
 117                                 pc = setNextItem(reg->reglives.usedpCodes);
 118                         }
 119
 120                         fprintf(stderr, "\n");
 121                 }
 122         }
 123 }
 124
 125 /*-----------------------------------------------------------------*
 126 *
 127 *-----------------------------------------------------------------*/
 128 void dbg_dumpregusage(void)
 129 {
 130
 131         fprintf(stderr,"***  Register Usage  ***\n");
 132         fprintf(stderr,"InternalRegs:\n");
 133         dbg_regusage(dynInternalRegs);
 134         fprintf(stderr,"AllocRegs:\n");
 135         dbg_regusage(dynAllocRegs);
 136         fprintf(stderr,"StackRegs:\n");
 137         dbg_regusage(dynStackRegs);
 138         fprintf(stderr,"DirectRegs:\n");
 139         dbg_regusage(dynDirectRegs);
 140         fprintf(stderr,"DirectBitRegs:\n");
 141         dbg_regusage(dynDirectBitRegs);
 142         fprintf(stderr,"ProcessorRegs:\n");
 143         dbg_regusage(dynProcessorRegs);
 144
 145 }
 146
 147
 148 /*-----------------------------------------------------------------*
 149 * void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
 150 *-----------------------------------------------------------------*/
 151 void pCodeRegMapLiveRangesInFlow(pCodeFlow *pcfl)
 152 {
 153
 154         pCode *pc=NULL;
 155
 156         regs *reg;
 157
 158         if(!pcfl)
 159                 return;
 160
 161
 162         pc = findNextInstruction(pcfl->pc.next);
 163
 164         while(pc && !isPCFL(pc)) {
 165                 while (pc && !isPCI(pc) && !isPCFL(pc))
 166                 {
 167                         pc = pc->next;
 168                 } // while
 169                 if (!pc || isPCFL(pc)) continue;
 170                 assert( isPCI(pc) );
 171
 172                 reg = getRegFromInstruction(pc);
 173                 #if 0
 174                 pc->print(stderr, pc);
 175                 fprintf( stderr, "--> reg %p (%s,%u), inCond/outCond: %x/%x\n",
 176                         reg, reg ? reg->name : "(null)", reg ? reg->rIdx : -1,
 177                         PCI(pc)->inCond, PCI(pc)->outCond );
 178                 #endif
 179                 if(reg) {
 180                 /*
 181                 fprintf(stderr, "flow seq %d, inst seq %d  %s  ",PCODE(pcfl)->seq,pc->seq,reg->name);
 182                 fprintf(stderr, "addr = 0x%03x, type = %d  rIdx=0x%03x\n",
 183                 reg->address,reg->type,reg->rIdx);
 184                         */
 185
 186                         addSetIfnotP(& (PCFL(pcfl)->registers), reg);
 187
 188                         if(PCC_REGISTER & PCI(pc)->inCond)
 189                                 addSetIfnotP(& (reg->reglives.usedpFlows), pcfl);
 190
 191                         if(PCC_REGISTER & PCI(pc)->outCond)
 192                                 addSetIfnotP(& (reg->reglives.assignedpFlows), pcfl);
 193
 194                         addSetIfnotP(& (reg->reglives.usedpCodes), pc);
 195                         reg->wasUsed = 1;
 196                 }
 197
 198
 199                 //pc = findNextInstruction(pc->next);
 200                 pc = pc->next;
 201
 202         }
 203
 204 }
 205
 206 /*-----------------------------------------------------------------*
 207 * void pCodeRegMapLiveRanges(pBlock *pb)
 208 *-----------------------------------------------------------------*/
 209 void pCodeRegMapLiveRanges(pBlock *pb)
 210 {
 211         pCode *pcflow;
 212
 213         for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
 214         pcflow != NULL;
 215         pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
 216
 217                 if(!isPCFL(pcflow)) {
 218                         fprintf(stderr, "pCodeRegMapLiveRanges - pcflow is not a flow object ");
 219                         continue;
 220                 }
 221                 pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
 222         }
 223
 224 #if 0
 225         for( pcflow = findNextpCode(pb->pcHead, PC_FLOW);
 226         pcflow != NULL;
 227         pcflow = findNextpCode(pcflow->next, PC_FLOW) ) {
 228
 229                 regs *r = setFirstItem(PCFL(pcflow)->registers);
 230                 fprintf(stderr,"flow seq %d\n", pcflow->seq);
 231
 232                 while (r) {
 233                         fprintf(stderr, "  %s\n",r->name);
 234                         r = setNextItem(PCFL(pcflow)->registers);
 235
 236                 }
 237
 238         }
 239 #endif
 240
 241         //  dbg_dumpregusage();
 242
 243 }
 244
 245
 246 /*-----------------------------------------------------------------*
 247 *
 248 *-----------------------------------------------------------------*/
 249 static void Remove1pcode(pCode *pc, regs *reg, int debug_code)
 250 {
 251
 252         pCode *pcn=NULL;
 253
 254         if(!reg || !pc)
 255                 return;
 256
 257         deleteSetItem (&(reg->reglives.usedpCodes),pc);
 258
 259         if(PCI(pc)->label) {
 260                 pcn = findNextInstruction(pc->next);
 261
 262                 if(pcn)
 263                         PCI(pcn)->label = pBranchAppend(PCI(pcn)->label,PCI(pc)->label);
 264         }
 265
 266         if(PCI(pc)->cline) {
 267                 if(!pcn)
 268                         pcn = findNextInstruction(pc->next);
 269
 270                 if(pcn) {
 271                         if(PCI(pcn)->cline) {
 272                                 //fprintf(stderr, "source line has been optimized completely out\n");
 273                                 //pc->print(stderr,pc);
 274                         } else {
 275                                 PCI(pcn)->cline = PCI(pc)->cline;
 276                         }
 277                 }
 278         }
 279
 280
 281         if(1){
 282         /*
 283         Debug stuff. Comment out the instruction we're about to delete.
 284                 */
 285
 286                 char buff1[256];
 287                 size_t size = 256;
 288
 289                 char *pbuff,**ppbuff;
 290                 pbuff = buff1;
 291                 ppbuff = &pbuff;
 292
 293                 SAFE_snprintf(ppbuff,&size, ";%d", debug_code);
 294                 pCode2str(*ppbuff, size, pc);
 295                 pCodeInsertBefore(pc, newpCodeCharP(buff1));
 296                 //fprintf(stderr,"removing instruction:\n%s\n",buff1);
 297         }
 298
 299         pc->destruct(pc);
 300
 301 }
 302
 303 /*-----------------------------------------------------------------*
 304 * void RemoveRegsFromSet(set *regset)
 305 *
 306 *-----------------------------------------------------------------*/
 307 void  RemoveRegsFromSet(set *regset)
 308 {
 309         regs *reg;
 310         int used;
 311
 312         while(regset) {
 313                 reg = regset->item;
 314                 regset = regset->next;
 315
 316                 used = elementsInSet(reg->reglives.usedpCodes);
 317
 318                 if(used <= 1) {
 319
 320                         //fprintf(stderr," reg %s isfree=%d, wasused=%d\n",reg->name,reg->isFree,reg->wasUsed);
 321                         if(used == 0) {
 322                                 //fprintf(stderr," getting rid of reg %s\n",reg->name);
 323                                 reg->isFree = 1;
 324                                 reg->wasUsed = 0;
 325                         } else {
 326                                 pCode *pc;
 327
 328
 329                                 pc = setFirstItem(reg->reglives.usedpCodes);
 330
 331                                 if(reg->type == REG_SFR || reg->type == REG_STK || reg->isPublic || reg->isExtern) {
 332                                         //fprintf(stderr, "not removing SFR reg %s even though used only once\n",reg->name);
 333                                         continue;
 334                                 }
 335
 336
 337                                 if(isPCI(pc)) {
 338                                         if(PCI(pc)->label) {
 339                                                 pCode *pcn = findNextInstruction(pc->next);
 340
 341                                                 if(pcn && PCI(pcn)->label) {
 342                                                         //fprintf(stderr,"can't delete instruction with label...\n");
 343                                                         //pc->print(stderr,pc);
 344                                                         continue;
 345                                                 }
 346                                                 /* Move the label to the next instruction */
 347
 348                                                 PCI(pcn)->label = PCI(pc)->label;
 349
 350                                         }
 351
 352                                         if(isPCI_SKIP(pc)) {
 353                                                 regs *r = getRegFromInstruction(pc);
 354                                                 fprintf(stderr, "WARNING, a skip instruction is being optimized out\n");
 355                                                 pc->print(stderr,pc);
 356                                                 fprintf(stderr,"reg %s, type =%d\n",r->name, r->type);
 357                                         }
 358                                         //fprintf(stderr," removing reg %s because it is used only once\n",reg->name);
 359                                         Remove1pcode(pc, reg, 1);
 360                                         /*
 361                                         unlinkpCode(pc);
 362                                         deleteSetItem (&(reg->reglives.usedpCodes),pc);
 363                                         */
 364                                         reg->isFree = 1;
 365                                         reg->wasUsed = 0;
 366                                         total_registers_saved++;  // debugging stats.
 367                                 }
 368                         }
 369                 }
 370
 371         }
 372 }
 373
 374 void RegsUnMapLiveRanges(void);
 375 extern pFile *the_pFile;
 376 void pic14_ReMapLiveRanges(void)
 377 {
 378         pBlock *pb;
 379         if (!the_pFile) return;
 380         RegsUnMapLiveRanges();
 381         for (pb = the_pFile->pbHead; pb; pb = pb->next)
 382         {
 383         #if 0
 384                 pCode *pc = findNextpCode(pb->pcHead, PC_FLOW);
 385                 if (pc) {
 386                         pc->print( stderr, pc );
 387                 } else {
 388                         fprintf( stderr, "unnamed pBlock\n");
 389                 }
 390                 pc = findNextInstruction(pb->pcHead);
 391                 while (pc) {
 392                   pc->print( stderr, pc );
 393                   pc = findNextInstruction(pc->next);;
 394                 }
 395         #endif
 396                 pCodeRegMapLiveRanges(pb);
 397         } // for
 398 }
 399
 400 /*-----------------------------------------------------------------*
 401 * void RemoveUnusedRegisters(void)
 402 *
 403 *-----------------------------------------------------------------*/
 404 void RemoveUnusedRegisters(void)
 405 {
 406         /* First, get rid of registers that are used only one time */
 407         pic14_ReMapLiveRanges();
 408
 409         //RemoveRegsFromSet(dynInternalRegs);
 410         RemoveRegsFromSet(dynAllocRegs);
 411         RemoveRegsFromSet(dynStackRegs);
 412         /*
 413         don't do DirectRegs yet - there's a problem with arrays
 414         RemoveRegsFromSet(dynDirectRegs);
 415         */
 416         RemoveRegsFromSet(dynDirectBitRegs);
 417
 418         if(total_registers_saved) DFPRINTF((stderr, " *** Saved %d registers ***\n", total_registers_saved));
 419 }
 420
 421
 422 /*-----------------------------------------------------------------*
 423 *
 424 *-----------------------------------------------------------------*/
 425 static void Remove2pcodes(pCode *pcflow, pCode *pc1, pCode *pc2, regs *reg, int can_free)
 426 {
 427         static int debug_code=99;
 428         if(!reg)
 429                 return;
 430 #if 0
 431         fprintf (stderr, "%s:%d(%s): %d (reg:%s)\n", __FILE__, __LINE__, __FUNCTION__, debug_code, reg ? reg->name : "???");
 432         printpCode (stderr, pc1);
 433         printpCode (stderr, pc2);
 434 #endif
 435
 436         //fprintf(stderr,"%s\n",__FUNCTION__);
 437         if(pc1)
 438                 Remove1pcode(pc1, reg, debug_code++);
 439
 440         if(pc2) {
 441                 Remove1pcode(pc2, reg, debug_code++);
 442                 deleteSetItem (&(PCFL(pcflow)->registers), reg);
 443
 444                 if(can_free) {
 445                         reg->isFree = 1;
 446                         reg->wasUsed = 0;
 447                 }
 448
 449         }
 450
 451         pCodeRegMapLiveRangesInFlow(PCFL(pcflow));
 452 }
 453
 454 /*-----------------------------------------------------------------*
 455 *
 456 *-----------------------------------------------------------------*/
 457 int regUsedinRange(pCode *pc1, pCode *pc2, regs *reg)
 458 {
 459         int i=0;
 460         regs *testreg;
 461
 462         do {
 463                 testreg = getRegFromInstruction(pc1);
 464                 if(testreg && (testreg->rIdx == reg->rIdx)) {
 465                         return 1;
 466                 }
 467                 if (i++ > 1000) {
 468                         fprintf(stderr, "warning, regUsedinRange searched through too many pcodes\n");
 469                         return 0;
 470                 }
 471
 472                 pc1 = findNextInstruction(pc1->next);
 473
 474         } while (pc1 && (pc1 != pc2)) ;
 475
 476         return 0;
 477 }
 478
 479 int regIsSpecial (regs *reg, int mayBeGlobal)
 480 {
 481   if (!reg) return 0;
 482
 483   if (reg->type == REG_SFR || reg->type == REG_STK || (!mayBeGlobal && (reg->isPublic || reg->isExtern))) return 1;
 484
 485   return 0;
 486 }
 487
 488 #if 0
 489 static int regIsLocal (regs *reg)
 490 {
 491         if (!reg) return 1;
 492         /* temporaries are local */
 493         if (reg->type == REG_TMP) return 1;
 494         /* registers named r0x... are local */
 495         if (reg->name && !strncmp(reg->name,"r0x", 3))
 496         {
 497                 //fprintf (stderr, "reg %s is not marked REG_TMP...\n", reg->name);
 498                 return 1;
 499         }
 500
 501         return 0;
 502 }
 503 #endif
 504
 505 /*-----------------------------------------------------------------*
 506 * void pCodeOptime2pCodes(pCode *pc1, pCode *pc2)
 507 *
 508 * ADHOC pattern checking
 509 * Now look for specific sequences that are easy to optimize.
 510 * Many of these sequences are characteristic of the compiler
 511 * (i.e. it'd probably be a waste of time to apply these adhoc
 512 * checks to hand written assembly.)
 513 *
 514 *
 515 *-----------------------------------------------------------------*/
 516 int pCodeOptime2pCodes(pCode *pc1, pCode *pc2, pCode *pcfl_used, regs *reg, int can_free, int optimize_level)
 517 {
 518         pCode *pct1, *pct2;
 519         regs  *reg1, *reg2;
 520
 521         int t = total_registers_saved;
 522
 523         if (!isPCI(pc1) || !isPCI(pc2)) return 0;
 524         if (PCI(pc1)->pcflow != PCI(pc2)->pcflow) return 0;
 525
 526         if(pc2->seq < pc1->seq) {
 527                 pct1 = pc2;
 528                 pc2 = pc1;
 529                 pc1 = pct1;
 530         }
 531
 532         /* disable this optimization for now -- it's buggy */
 533         if(pic14_options.disable_df) return 0;
 534
 535         //fprintf(stderr,"pCodeOptime2pCodes\n");
 536         //pc1->print(stderr,pc1);
 537         //pc2->print(stderr,pc2);
 538
 539         if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_MOVFW) ){
 540                 pCode *newpc;
 541                 int regUsed = 0;
 542                 int wUsed   = 0;
 543                 int wSaved  = 0;
 544                 /*
 545                 clrf  reg    ; pc1
 546                 stuff...
 547                 movf  reg,w  ; pc2
 548
 549                   can be replaced with (only if following instructions are not going to use W and reg is not used again later)
 550
 551                         stuff...
 552                         movlw 0 or clrf  reg
 553                 */
 554                 DFPRINTF((stderr, "   optimising CLRF reg ... MOVF reg,W to ... MOVLW 0\n"));
 555                 pct2 = findNextInstruction(pc2->next);
 556
 557                 if(pct2 && PCI(pct2)->op == POC_MOVWF) {
 558                         wSaved = wUsed = 1; /* Maybe able to replace with clrf pc2->next->reg. */
 559                 } else {
 560                         wUsed = pCodeSearchCondition(pct2,PCC_W,1) != -1;
 561                 }
 562                 regUsed = regUsedinRange(pct2,0,reg);
 563                 if ((regUsed&&wUsed) || (pCodeSearchCondition(pct2,PCC_Z,0) != -1)) {
 564                         /* Do not optimise as exisiting code is required. */
 565                 } else {
 566                         /* Can optimise. */
 567                         if(regUsed) {
 568                                 newpc = newpCode(POC_CLRF, PCI(pc1)->pcop);
 569                         } else if(wSaved && !wUsed) {
 570                                 newpc = newpCode(POC_CLRF, PCI(pct2)->pcop);
 571                                 pct2->destruct(pct2);
 572                         } else {
 573                                 newpc = newpCode(POC_MOVLW, newpCodeOpLit(0));
 574                         }
 575
 576                         pCodeInsertAfter(pc2, newpc);
 577                         PCI(newpc)->pcflow = PCFL(pcfl_used);
 578                         newpc->seq = pc2->seq;
 579
 580                         //fprintf (stderr, "%s:%d(%s): Remove2pcodes (CLRF reg, ..., MOVF reg,W)\n", __FILE__, __LINE__, __FUNCTION__);
 581                         Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
 582                         total_registers_saved++;  // debugging stats.
 583                 }
 584         } else if((PCI(pc1)->op == POC_CLRF) && (PCI(pc2)->op == POC_IORFW) ){
 585                 DFPRINTF((stderr, "   optimising CLRF/IORFW\n"));
 586
 587                 pct2 = findNextInstruction(pc2->next);
 588
 589                 /* We must ensure that is destroyed before being read---IORLW must be performed unless this is proven. */
 590                 if(pCodeSearchCondition(pct2, PCC_Z,0) != -1) {
 591                         pct2 = newpCode(POC_IORLW, newpCodeOpLit(0));
 592                         pct2->seq = pc2->seq;
 593                         PCI(pct2)->pcflow = PCFL(pcfl_used);
 594                         pCodeInsertAfter(pc1,pct2);
 595                 }
 596                 //fprintf (stderr, "%s:%d(%s): Remove2pcodes (CLRF/IORFW)\n", __FILE__, __LINE__, __FUNCTION__);
 597                 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
 598                 total_registers_saved++;  // debugging stats.
 599
 600         }  else if(PCI(pc1)->op == POC_MOVWF) {
 601                 // Optimising MOVWF reg ...
 602
 603                 pct2 = findNextInstruction(pc2->next);
 604
 605                 if(PCI(pc2)->op == POC_MOVFW) {
 606                         // Optimising MOVWF reg ... MOVF reg,W
 607
 608                         if(PCI(pct2)->op == POC_MOVWF) {
 609                         /*
 610                         Change:
 611
 612                           movwf   reg    ; pc1
 613                           stuff...
 614                           movf    reg,w  ; pc2
 615                           movwf   reg2   ; pct2
 616
 617                                 To: ( as long as 'stuff' does not use reg2 or if following instructions do not use W or reg is not used later)
 618
 619                                   movwf   reg2
 620                                   stuff...
 621
 622                                 */
 623                                 reg2 = getRegFromInstruction(pct2);
 624                                 /* Check reg2 is not used for something else before it is loaded with reg */
 625                                 if (reg2 && !regIsSpecial (reg2, 1) && !regUsedinRange(pc1,pc2,reg2)) {
 626                                         pCode *pct3 = findNextInstruction(pct2->next);
 627                                         /* Check following instructions are not relying on the use of W or the Z flag condiction */
 628                                         /* XXX: We must ensure that this value is destroyed before use---otherwise it might be used in
 629                                          *      subsequent flows (checking for < 1 is insufficient). */
 630                                         if ((pCodeSearchCondition(pct3,PCC_Z,0) == -1) && (pCodeSearchCondition(pct3,PCC_W,0) == -1)) {
 631                                                 DFPRINTF((stderr, "   optimising MOVF reg ... MOVF reg,W MOVWF reg2 to MOVWF reg2 ...\n"));
 632                                                 pct2->seq = pc1->seq;
 633                                                 unlinkpCode(pct2);
 634                                                 pCodeInsertBefore(pc1,pct2);
 635                                                 if(regUsedinRange(pct2,0,reg))
 636                                                 {
 637                                                         //fprintf (stderr, "%s:%d(%s): Remove2pcodes IF (MOVWF reg, ..., MOVW reg,W  MOVWF reg2)\n", __FILE__, __LINE__, __FUNCTION__);
 638                                                         Remove2pcodes(pcfl_used, pc2, NULL, reg, can_free);
 639                                                 } else {
 640                                                         //fprintf (stderr, "%s:%d(%s): Remove2pcodes ELSE (MOVWF reg, ..., MOVW reg,W  MOVWF reg2)\n", __FILE__, __LINE__, __FUNCTION__);
 641                                                         Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
 642                                                 }
 643                                                 total_registers_saved++;  // debugging stats.
 644                                                 return 1;
 645                                         }
 646                                 }
 647                         }
 648                 }
 649
 650                 pct1 = findPrevInstruction(pc1->prev);
 651                 if(pct1 && (PCI(pct1)->pcflow == PCI(pc1)->pcflow)) {
 652
 653                         if ( (PCI(pct1)->op == POC_MOVFW) &&
 654                                 (PCI(pc2)->op == POC_MOVFW)) {
 655
 656                                 reg1 = getRegFromInstruction(pct1);
 657                                 if(reg1 && !regIsSpecial (reg1, 0) && !regUsedinRange(pc1,pc2,reg1)) {
 658                                         DFPRINTF((stderr, "   optimising MOVF reg1,W MOVWF reg ... MOVF reg,W\n"));
 659                                         /*
 660                                         Change:
 661
 662                                                 movf   reg1,w
 663                                                 movwf  reg
 664
 665                                                 stuff...
 666                                                 movf   reg,w
 667
 668                                         To:
 669
 670                                                 stuff...
 671
 672                                                 movf   reg1,w
 673
 674                                         Or, if we're not deleting the register then the "To" is:
 675
 676                                                 stuff...
 677
 678                                                 movf   reg1,w
 679                                                 movwf  reg
 680                                         */
 681                                         pct2 = newpCode(PCI(pc2)->op, PCI(pct1)->pcop);
 682                                         pCodeInsertAfter(pc2, pct2);
 683                                         PCI(pct2)->pcflow = PCFL(pcfl_used);
 684                                         pct2->seq = pc2->seq;
 685
 686                                         if(can_free) {
 687                                                 //fprintf (stderr, "%s:%d(%s): Remove2pcodes CANFREE (MOVF reg1,W; MOVWF reg2; MOVF reg2,W)\n", __FILE__, __LINE__, __FUNCTION__);
 688                                                 Remove2pcodes(pcfl_used, pc1, pc2, reg, can_free);
 689                                         } else {
 690                                         /* If we're not freeing the register then that means (probably)
 691                                                 * the register is needed somewhere else.*/
 692                                                 unlinkpCode(pc1);
 693                                                 pCodeInsertAfter(pct2, pc1);
 694
 695                                                 //fprintf (stderr, "%s:%d(%s): Remove2pcodes ELSE (MOVF reg1,W; MOVWF reg2; MOVF reg2,W)\n", __FILE__, __LINE__, __FUNCTION__);
 696                                                 Remove2pcodes(pcfl_used, pc2, NULL, reg, can_free);
 697                                         }
 698
 699                                         //fprintf (stderr, "%s:%d(%s): Remove2pcodes ALWAYS (MOVF reg1,W; MOVWF reg2; MOVF reg2,W)\n", __FILE__, __LINE__, __FUNCTION__);
 700                                         Remove2pcodes(pcfl_used, pct1, NULL, reg1, 0);
 701                                         total_registers_saved++;  // debugging stats.
 702
 703                                 }
 704                         }
 705                 }
 706   }
 707
 708   return (total_registers_saved != t);
 709 }
 710
 711 /*-----------------------------------------------------------------*
 712 * void pCodeRegOptimeRegUsage(pBlock *pb)
 713 *-----------------------------------------------------------------*/
 714 void OptimizeRegUsage(set *fregs, int optimize_multi_uses, int optimize_level)
 715 {
 716         regs *reg;
 717         int used;
 718         pCode *pc1=NULL, *pc2=NULL;
 719
 720
 721         while(fregs) {
 722                 pCode *pcfl_used, *pcfl_assigned;
 723
 724                 /* Step through the set by directly accessing the 'next' pointer.
 725                 * We could also step through by using the set API, but the
 726                 * the (debug) calls to print instructions affect the state
 727                 * of the set pointers */
 728
 729                 reg = fregs->item;
 730                 fregs = fregs->next;
 731                 /*
 732                 if (strcmp(reg->name,"_SubState")==0)
 733                 fprintf(stderr,"Reg: %s\n",reg->name);
 734                 */
 735
 736                 /* Catch inconsistently set-up live ranges
 737                  * (see tracker items #1469504 + #1474602)
 738                  * FIXME: Actually we should rather fix the
 739                  * computation of the liveranges instead...
 740                  */
 741                 if (!reg || !reg->reglives.usedpFlows
 742                         || !reg->reglives.assignedpFlows)
 743                 {
 744                   //fprintf( stderr, "skipping reg w/o liveranges: %s\n", reg ? reg->name : "(unknown)");
 745                   continue;
 746                 }
 747
 748                 if(reg->type == REG_SFR || reg->type == REG_STK || reg->isPublic || reg->isExtern|| reg->isFixed) {
 749                         //fprintf(stderr,"skipping SFR: %s\n",reg->name);
 750                         continue;
 751                 }
 752
 753                 pcfl_used = setFirstItem(reg->reglives.usedpFlows);
 754                 pcfl_assigned = setFirstItem(reg->reglives.assignedpFlows);
 755
 756                 used = elementsInSet(reg->reglives.usedpCodes);
 757                 if(used == 2) {
 758                         /*
 759                         In this section, all registers that are used in only in two
 760                         instructions are examined. If possible, they're optimized out.
 761                         */
 762
 763                         /*
 764                         fprintf (stderr, "OptimizeRegUsage: %s  addr=0x%03x rIdx=0x%03x type=%d used=%d\n",
 765                         reg->name,
 766                         reg->address,
 767                         reg->rIdx, reg->type, used);
 768                         */
 769                         pc1 = setFirstItem(reg->reglives.usedpCodes);
 770                         pc2 = setNextItem(reg->reglives.usedpCodes);
 771
 772                         if(pcfl_used && pcfl_assigned) {
 773                                 /*
 774                                 expected case - the register has been assigned a value and is
 775                                 subsequently used
 776                                 */
 777
 778                                 //fprintf(stderr," used only twice\n");
 779                                 if(pcfl_used->seq == pcfl_assigned->seq) {
 780
 781                                         //fprintf(stderr, "  and used in same flow\n");
 782
 783                                         pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 1,optimize_level);
 784
 785                                 } else {
 786                                         // fprintf(stderr, "  and used in different flows\n");
 787
 788                                 }
 789
 790                         } else if(pcfl_used) {
 791
 792                                 /* register has been used twice without ever being assigned */
 793                                 fprintf(stderr,"WARNING %s: reg %s used without being assigned\n",__FUNCTION__,reg->name);
 794
 795                         } else {
 796                                 //fprintf(stderr,"WARNING %s.1: reg %s assigned without being used\n",__FUNCTION__,reg->name);
 797                                 Remove2pcodes(pcfl_assigned, pc1, pc2, reg, 1);
 798                                 total_registers_saved++;  // debugging stats.
 799                         }
 800                 } else {
 801
 802                         /* register has been used either once, or more than twice */
 803
 804                         if(used && !pcfl_used && pcfl_assigned) {
 805                                 pCode *pc;
 806
 807                                 //fprintf(stderr,"WARNING %s.2: reg %s assigned without being used\n",__FUNCTION__,reg->name);
 808
 809                                 pc = setFirstItem(reg->reglives.usedpCodes);
 810                                 while(pc) {
 811
 812                                         pcfl_assigned = PCODE(PCI(pc)->pcflow);
 813                                         Remove1pcode(pc, reg,2);
 814
 815                                         deleteSetItem (&(PCFL(pcfl_assigned)->registers), reg);
 816                                         /*
 817                                         deleteSetItem (&(reg->reglives.usedpCodes),pc);
 818                                         pc->destruct(pc);
 819                                         */
 820                                         pc = setNextItem(reg->reglives.usedpCodes);
 821                                 }
 822
 823
 824                                 reg->isFree = 1;
 825                                 reg->wasUsed = 0;
 826
 827                                 total_registers_saved++;  // debugging stats.
 828                         } else if( (used > 2) && optimize_multi_uses) {
 829
 830                                 set *rset1=NULL;
 831                                 set *rset2=NULL;
 832                                 int searching=1;
 833
 834                                 pCodeFlow *pcfl1=NULL, *pcfl2=NULL;
 835
 836                                 /* examine the number of times this register is used */
 837
 838
 839                                 rset1 = reg->reglives.usedpCodes;
 840                                 while(rset1 && searching) {
 841
 842                                         pc1 = rset1->item;
 843                                         rset2 = rset1->next;
 844
 845                                         if(pc1 && isPCI(pc1) &&  ( (pcfl1 = PCI(pc1)->pcflow) != NULL) ) {
 846
 847                                                 //while(rset2 && searching) {
 848                                                 if(rset2) {
 849
 850                                                         pc2 = rset2->item;
 851                                                         if(pc2 && isPCI(pc2)  &&  ( (pcfl2 = PCI(pc2)->pcflow) != NULL) )  {
 852                                                                 if(pcfl2 == pcfl1) {
 853
 854                                                                         if(pCodeOptime2pCodes(pc1, pc2, pcfl_used, reg, 0,optimize_level))
 855                                                                                 searching = 0;
 856                                                                 }
 857                                                         }
 858
 859                                                         //rset2 = rset2->next;
 860
 861                                                 }
 862                                         }
 863                                         rset1 = rset1->next;
 864                                 }
 865                         }
 866                 }
 867         }
 868 }
 869
 870 #if 0
 871
 872 /* The following routines implement pCode optimizations based on
 873  * dataflow analysis. The effects should be similar to those
 874  * of pCodeOptime2pCodes() but more powerful.
 875  *
 876  * Unfortunately, the current approach (comparing operands by
 877  * their associated registers) is seriously flawed:
 878  * Some pCodeOps do not provide access to their repsective regs
 879  * (PO_DIRs are created from arbitrary strings, immediates need
 880  * to take offset and index into account, ...)
 881  *
 882  * This has to be rewritten based on pCodeOps instead of regs...
 883  */
 884
 885 /* ------------------------------------------------------------------
 886    Returns TRUE iff reg1 and reg2 are the same registers.
 887    ------------------------------------------------------------------ */
 888
 889 static int sameRegs (const regs *reg1, const regs *reg2)
 890 {
 891         if (reg1 == reg2) return 1;
 892         if (!reg1 || !reg2) return 0;
 893         assert (reg1->name && reg2->name);
 894
 895         /* Compare names, as rIdx is not unique... */
 896         if (!strcmp(reg1->name, reg2->name)) return 1;
 897
 898         /* Name mismatch -- not the same register. */
 899         return 0;
 900 }
 901
 902 /* ------------------------------------------------------------------
 903    Returns 1 if the register is live at pc (read in this flow),
 904    returns -1 if the register is NOT live at pc (assigned a new value
 905    prior to readingi the old value in this flow) or
 906    return 0 if the register is not mentioned.
 907    ------------------------------------------------------------------ */
 908
 909 static int checkRegInFlow (regs **reg, int *cond, pCode *pc)
 910 {
 911         const int verbose = 0;
 912         /* find next PCI at or after pc */
 913         while (pc && isPCFL(pc)) pc = pc->next;
 914
 915         assert (reg && cond);
 916
 917         /* remove pseudo flags from cond */
 918         *cond &= ~(PCC_REGISTER | PCC_EXAMINE_PCOP);
 919
 920         if (verbose && pc)
 921         {
 922                 fprintf (stderr, "Checking for reg %s, cond %x on pc ", *reg ? (*reg)->name : "<none>", *cond); pc->print (stderr, pc);
 923         }
 924
 925         while (pc && !isPCFL(pc))
 926         {
 927                 if (verbose)
 928                 {
 929                         fprintf (stderr, "        now checking for reg %s, cond %x on pc ", *reg ? (*reg)->name : "<none>", *cond);
 930                         pc->print (stderr, pc);
 931                 }
 932                 if (isPCI(pc))
 933                 {
 934                         pCode *pcprev;
 935                         regs *op = NULL;
 936                         int prevIsSkip = 0;
 937
 938                         pcprev = findPrevInstruction (pc);
 939                         if (pcprev && isPCI_SKIP(pcprev))
 940                                 prevIsSkip = 1;
 941
 942                         if ((PCI(pc)->inCond | PCI(pc)->outCond) & PCC_REGISTER)
 943                         {
 944                                 op = getRegFromInstruction (pc);
 945
 946                                 /* pCodeOpRegBits do not provide register information... */
 947                                 //if (!op) { __asm__("int3"); pc->print (stderr, pc); }
 948                                 //assert (op);
 949                                 if (!op)
 950                                 {
 951                                         if (reg)
 952                                                 return 1; /* assume `reg' is alive */
 953                                 }
 954
 955                                 /* SPECIAL CASE: jump to unknown destination -- assume everything alive */
 956                                 if (op->type == PO_PCL)
 957                                 {
 958                                         return 1;
 959                                 }
 960                         } // if
 961
 962                         if (PCI(pc)->inCond & PCC_REGISTER)
 963                         {
 964                                 /* `op' is live (possibly read) */
 965                                 if (*reg && sameRegs (op, *reg))
 966                                 {
 967                                         if (verbose)
 968                                         {
 969                                                 fprintf (stderr, "reg is read in pc ");
 970                                                 pc->print (stderr, pc);
 971                                         }
 972                                         return 1;
 973                                 }
 974                         }
 975
 976                         /* handle additional implicit operands */
 977                         switch (PCI(pc)->op)
 978                         {
 979                         case POC_CALL: /* read arguments from WREG, clobbers WREG */
 980                                 if (*cond & PCC_W)
 981                                 {
 982                                         if (verbose)
 983                                         {
 984                                                 fprintf (stderr, "conditions are read at pc ");
 985                                                 pc->print (stderr, pc);
 986                                         }
 987                                         return 1;
 988                                 }
 989                                 *cond &= ~PCC_W;
 990                                 break;
 991                         case POC_RETURN: /* returns WREG to caller */
 992                                 //fprintf (stderr, "reached RETURN, reg %s, cond %x\n", *reg ? (*reg)->name : "<none>", *cond);
 993                                 if (*cond & PCC_W)
 994                                 {
 995                                         if (verbose)
 996                                         {
 997                                                 fprintf (stderr, "conditions are read at pc ");
 998                                                 pc->print (stderr, pc);
 999                                         }
1000                                         return 1;
1001                                 }
1002                                 /* afterwards, no condition is alive */
1003                                 *cond = 0;
1004                                 /* afterwards, all local registers are dead */
1005                                 if (*reg && regIsLocal (*reg)) *reg = NULL;
1006                                 break;
1007                         case POC_RETLW:
1008                         case POC_RETFIE: /* this does not erturn WREG to the "caller", thus its rather a RETLW */
1009                                 /* this discards WREG */
1010                                 *cond &= ~PCC_W;
1011                                 /* afterwards, no condition is alive */
1012                                 *cond = 0;
1013                                 /* afterwards, all local registers are dead */
1014                                 if (*reg && regIsLocal (*reg)) *reg = NULL;
1015                                 break;
1016                         default:
1017                                 /* no implicit arguments */
1018                                 break;
1019                         }
1020
1021                         if (PCI(pc)->inCond & (*cond))
1022                         {
1023                                 /* a condition is read */
1024                                 if (verbose)
1025                                 {
1026                                         fprintf (stderr, "conditions are read at pc ");
1027                                         pc->print (stderr, pc);
1028                                 }
1029                                 return 1;
1030                         }
1031
1032                         /* remove outConds from `cond' */
1033                         (*cond) &= ~(PCI(pc)->outCond);
1034
1035                         if (PCI(pc)->outCond & PCC_REGISTER)
1036                         {
1037                                 /* `op' is (possibly) discarded */
1038                                 if (*reg && !prevIsSkip && sameRegs (op, *reg))
1039                                 {
1040                                         if (verbose)
1041                                         {
1042                                                 fprintf (stderr, "reg is assigned (cont'd) at pc ");
1043                                                 pc->print (stderr, pc);
1044                                         }
1045                                         *reg = NULL;
1046                                 }
1047                         }
1048
1049                         /* have all interesting conditions/registers been discarded? */
1050                         if (!(*reg) && !(*cond))
1051                         {
1052                                 if (verbose)
1053                                 {
1054                                         fprintf (stderr, "reg and conditions are discarded after ");
1055                                         pc->print (stderr, pc);
1056                                 }
1057                                 return -1;
1058                         }
1059                 } // if
1060
1061                 pc = pc->next;
1062         } // while
1063
1064         /* no use of (or only conditional writes to) `reg' found in flow */
1065         if (verbose)
1066         {
1067                 fprintf (stderr, "analysis inconclusive: reg %s, cond %x remains\n", *reg ? "remains" : "is void", *cond);
1068         }
1069         return 0;
1070 }
1071
1072 /* ------------------------------------------------------------------
1073    This will return 1 only if
1074    - reg is NULL or of type REG_TMP
1075    - reg is NULL or its value is discarded after pc
1076    - cond is 0 or all conditions are overwritten before being used
1077    ------------------------------------------------------------------ */
1078
1079 typedef struct {
1080   pCode *pc;
1081   regs *reg;
1082   int cond;
1083 } df_state_t;
1084
1085 df_state_t *df_free_states = NULL;
1086
1087 static df_state_t *
1088 df_newState (regs *reg, int cond, pCode *pc)
1089 {
1090         df_state_t *state;
1091
1092         if (df_free_states) {
1093           state = df_free_states;
1094           df_free_states = (df_state_t *)df_free_states->pc;
1095         } else {
1096           state = Safe_calloc(1, sizeof(df_state_t));
1097         }
1098         state->pc = pc;
1099         state->reg = reg;
1100         state->cond = cond;
1101         return state;
1102 }
1103
1104 static int
1105 df_containsState (set *set, df_state_t *state)
1106 {
1107         /* scan set for presence of `state' */
1108         df_state_t *curr;
1109         for (curr = setFirstItem (set); curr; curr = setNextItem (set))
1110         {
1111                 if ((curr->pc == state->pc)
1112                         && (curr->reg == state->reg)
1113                         && (curr->cond == state->cond))
1114                 {
1115                         /* `state' found */
1116                         return 1;
1117                 }
1118         }
1119         return 0;
1120 }
1121
1122 static void
1123 df_releaseState (df_state_t *state)
1124 {
1125         state->pc = (pCode *)df_free_states;
1126         df_free_states = (df_state_t *)state;
1127         state->reg = NULL;
1128         state->cond = 0;
1129 }
1130
1131 static void
1132 df_removeStates ()
1133 {
1134         df_state_t *next;
1135         while (df_free_states)
1136         {
1137                 next = (df_state_t *)df_free_states->pc;
1138                 Safe_free(df_free_states);
1139                 df_free_states = next;
1140         } // while
1141 }
1142
1143 int regIsDead (regs *reg, int cond, pCode *pc)
1144 {
1145         set *seenStates = NULL;
1146         set *todo = NULL;
1147         pCode *curr;
1148         df_state_t *state;
1149         int result = 1;
1150
1151         /* sanity checks */
1152         if (reg && !regIsLocal (reg)) return 0;
1153
1154         pc = findNextInstruction (pc->next);
1155
1156         addSet (&todo, df_newState(reg, cond, pc));
1157
1158         while ((result == 1) && (state = getSet (&todo)))
1159         {
1160                 int res;
1161
1162                 if (df_containsState (seenStates, state)) continue;
1163                 addSet (&seenStates, state);
1164
1165                 curr = state->pc;
1166                 reg = state->reg;
1167                 cond = state->cond;
1168
1169                 //fprintf (stderr, "Checking for reg %s/cond %x at pc ", reg ? reg->name : "<none>", cond);
1170                 //curr->print (stderr, curr);
1171
1172                 res = checkRegInFlow (&reg, &cond, curr);
1173                 switch (res)
1174                 {
1175                 case 1: /* `reg' or `cond' is read---not dead */
1176                         result = 0;
1177                         break;
1178                 case -1: /* `reg' and `cond' are discarded in this flow---need to check other open flows */
1179                         break;
1180                 default: /* `reg' is not read and (possibly) not assigned---check successor flows */
1181                         if (curr)
1182                         {
1183                                 pCodeFlow *pcfl = PCI(curr)->pcflow;
1184                                 pCodeFlowLink *link;
1185                                 pCode *first;
1186                                 assert (pcfl);
1187
1188                                 for (link = setFirstItem(pcfl->to); link; link = setNextItem (pcfl->to))
1189                                 {
1190                                         /* add the first pCodeInstruction in the new flow to `todo' */
1191                                         first = findNextInstruction (&link->pcflow->pc);
1192                                         if (first) addSet (&todo, df_newState (reg, cond, first));
1193                                 } // for
1194                         }
1195                         break;
1196                 } // switch
1197         } // while
1198
1199         /* clean up */
1200         while (NULL != (state = getSet (&todo))) { df_releaseState (state); }
1201         while (NULL != (state = getSet (&seenStates))) { df_releaseState (state); }
1202
1203         /* if result remained 1, `reg' is not even possibly read and thus dead */
1204         return result;
1205 }
1206
1207
1208
1209 /* ------------------------------------------------------------------
1210    Safely remove a pCode.
1211    This needs to check that the previous instruction was no SKIP
1212    (otherwise the SKIP instruction would have to be removed as well,
1213    which may not be done for SFRs (side-effects on read possible)).
1214    ------------------------------------------------------------------ */
1215
1216 extern void unBuildFlow (pBlock *pb);
1217 extern void RegsUnMapLiveRanges ();
1218 extern void BuildFlow (pBlock *pb);
1219 extern void LinkFlow (pBlock *pb);
1220 extern void BuildFlowTree (pBlock *pb);
1221 extern void pCodeRegMapLiveRanges (pBlock *pb);
1222 extern pFile *the_pFile;
1223
1224 static int pCodeRemove (pCode *pc, const char *comment)
1225 {
1226         pCode *pcprev, *pcnext;
1227         unsigned int result = 0;
1228
1229         /* Sanity checks. */
1230         if (!pc) return 0;
1231         if (!isPCI(pc)) return 0;
1232
1233         pcprev = findPrevInstruction (pc->prev);
1234         if (pcprev && isPCI_SKIP(pcprev))
1235         {
1236                 /* bail out until we know how to fix the Flow... */
1237                 //return 0;
1238
1239                 /* we also need to remove the preceeding SKIP instruction(s) */
1240                 result = pCodeRemove (pcprev, "=DF= removing preceeding SKIP as well");
1241                 if (!result)
1242                 {
1243                         /* previous instruction could not be removed -- this cannot be removed as well */
1244                         return result;
1245                 }
1246                 /* FIXME: We now have to update the flow! */
1247         } // if
1248
1249         /* do not remove pCodes with SFRs as operands (even reading them might cause side effects) */
1250         {
1251                 regs *reg;
1252                 reg = getRegFromInstruction (pc);
1253                 /* accesses to the STATUS register aer always safe, but others... */
1254                 if (reg && reg->type == REG_SFR && reg->pc_type != PO_STATUS) return result;
1255         }
1256
1257         /* MUST SUCEED FROM NOW ON (or revert the changes done since NOW ;-)) */
1258
1259         /* fix flow */
1260         if (PCI(pc)->pcflow && PCI(pc)->pcflow->end == pc)
1261         {
1262                 pCode *pcprev;
1263                 pcprev = findPrevInstruction (pc->prev);
1264                 if (PCI(pcprev)->pcflow == PCI(pc)->pcflow)
1265                 {
1266                         PCI(pc)->pcflow->end = pcprev;
1267                 } else {
1268                         pBlock *pb = pc->pb;
1269                         RegsUnMapLiveRanges();
1270                         unBuildFlow(pb);
1271                         BuildFlow(pb);
1272                         LinkFlow(pb);
1273                         BuildFlowTree(pb);
1274                         for (pb = the_pFile->pbHead; pb; pb = pb->next)
1275                         {
1276                                 pCodeRegMapLiveRanges(pb);
1277                         }
1278                 }
1279         }
1280
1281         /* attach labels to next instruction */
1282         pcnext = findNextInstruction (pc->next);
1283         if (pcnext)
1284         {
1285                 PCI(pcnext)->label = pBranchAppend (PCI(pcnext)->label, PCI(pc)->label);
1286                 if (!PCI(pcnext)->cline) PCI(pcnext)->cline = PCI(pc)->cline;
1287         }
1288         else
1289         {
1290                 fprintf (stderr, "Cannot move a label...\n");
1291                 exit(EXIT_FAILURE);
1292         }
1293
1294         if (comment)
1295         {
1296                 char buffer[512];
1297                 int size = 512;
1298                 char *pbuff = &buffer[0];
1299
1300                 SAFE_snprintf (&pbuff, &size, "; %s:%u(%s): %s", __FILE__, __LINE__, __FUNCTION__, comment);
1301                 pCodeInsertAfter(pc->prev, newpCodeCharP (&buffer[0]));
1302         } // if
1303
1304         if (1)
1305         {
1306                 /* replace removed pCode with out-commented version of itself */
1307                 char buffer[512];
1308                 int size = 512;
1309                 char *pbuff = &buffer[0];
1310
1311                 SAFE_snprintf (&pbuff, &size, "; %s:%u(%s): ", __FILE__, __LINE__, __FUNCTION__);
1312                 pCode2str (pbuff, size, pc);
1313                 pCodeInsertAfter(pc->prev, newpCodeCharP (&buffer[0]));
1314         }
1315
1316         pc->destruct (pc);
1317         return result+1;
1318 }
1319
1320 /* ------------------------------------------------------------------
1321    Find and remove dead pCodes.
1322    ------------------------------------------------------------------ */
1323
1324 static int removeIfDeadPCI (pCode *pc)
1325 {
1326         pCode *pcnext = NULL;
1327         pCode *curr;
1328         unsigned int outCond;
1329         unsigned int result = 0;
1330         regs *dst;
1331
1332         if (!pc) return 0;
1333         dst = NULL;
1334
1335         /* skip non-PCIs */
1336         pcnext = findNextInstruction (pc->next);
1337         if (!isPCI(pc)) return 0;
1338
1339         switch (PCI(pc)->op)
1340         {
1341         case POC_ADDLW:
1342         case POC_ADDWF:
1343         case POC_ADDFW:
1344         case POC_ANDLW:
1345         case POC_ANDWF:
1346         case POC_ANDFW:
1347         case POC_BCF:
1348         case POC_BSF:
1349         //case POC_BTFSC:
1350         //case POC_BTFSS:
1351         //case POC_CALL:
1352         case POC_COMF:
1353         case POC_COMFW:
1354         case POC_CLRF:
1355         case POC_CLRW:
1356         //case POC_CLRWDT:
1357         case POC_DECF:
1358         case POC_DECFW:
1359         //case POC_DECFSZ:
1360         //case POC_DECFSZW:
1361         //case POC_GOTO:
1362         case POC_INCF:
1363         case POC_INCFW:
1364         //case POC_INCFSZ:
1365         //case POC_INCFSZW:
1366         case POC_IORLW:
1367         case POC_IORWF:
1368         case POC_IORFW:
1369         case POC_MOVF:
1370         case POC_MOVFW:
1371         case POC_MOVLW:
1372         case POC_MOVWF:
1373         case POC_NOP:
1374         //case POC_RETLW:
1375         //case POC_RETURN:
1376         //case POC_RETFIE:
1377         case POC_RLF:
1378         case POC_RLFW:
1379         case POC_RRF:
1380         case POC_RRFW:
1381         case POC_SUBLW:
1382         case POC_SUBWF:
1383         case POC_SUBFW:
1384         case POC_SWAPF:
1385         case POC_SWAPFW:
1386         //case POC_TRIS:
1387         case POC_XORLW:
1388         case POC_XORWF:
1389         case POC_XORFW:
1390         //case POC_BANKSEL:
1391         //case POC_PAGESEL:
1392                 break;
1393
1394         default:
1395                 /* do not remove unknown PCIs */
1396                 return 0;
1397         } // switch
1398
1399         /* redundant checks---those instructions may never be removed */
1400         if (isPCI_BRANCH(pc)) return 0;
1401         if (isPCI_SKIP(pc)) return 0;
1402
1403         outCond = PCI(pc)->outCond;
1404         curr = pcnext;
1405
1406         /* unknown operands assigned to, then ignore */
1407         if ((outCond & (PCC_REGISTER | PCC_C | PCC_Z | PCC_DC | PCC_W)) != outCond)
1408                 return 0;
1409
1410         if (outCond & PCC_REGISTER)
1411         {
1412                 dst = getRegFromInstruction (pc);
1413                 if (!dst) return 0;
1414
1415                 /* special reg? */
1416                 if (!regIsLocal (dst)) return 0;
1417                 if (regIsSpecial (dst,0)) return 0;
1418         }
1419
1420         //fprintf (stderr, "--> checking for liveness pc "); pc->print (stderr, pc);
1421         if (regIsDead (dst, outCond, pc))
1422         {
1423                 /* no result from pc has been used -- pc is `dead' */
1424                 //fprintf (stderr, "--> reg %s and cond %x assumed unused\n", dst ? dst->name : "<none>", outCond);
1425                 //fprintf (stderr, "--> removing dead pc "); pc->print (stderr, pc);
1426                 result = pCodeRemove (pc, "=DF= removed dead pCode");
1427         }
1428
1429         return result;
1430 }
1431
1432 /* ------------------------------------------------------------------
1433    This routine is intended to safely replace one pCodeInstruction
1434    with a different pCodeInstruction.
1435    If desired, the replaced pCode will be left in (commented out) for
1436    debugging.
1437    Further, an optional comment can be inserted to indicate the
1438    reason for the possible removal of the pCode.
1439    ------------------------------------------------------------------ */
1440
1441 static void replace_PCI (pCodeInstruction *pc, pCodeInstruction *newpc, char *comment)
1442 {
1443   newpc->from =  pBranchAppend (newpc->from, pc->from);
1444   newpc->to = pBranchAppend (newpc->to, pc->to);
1445   newpc->label = pBranchAppend (newpc->label, pc->label);
1446   //newpc->pcflow = pc->pcflow; // updated in pCodeInsertAfter, ->pb is as well
1447   newpc->cline = pc->cline;
1448
1449   newpc->pc.seq = pc->pc.seq;
1450
1451   pCodeInsertAfter (&pc->pc, &newpc->pc);
1452
1453   /* FIXME: replacing pc will break the liverange maps (usedpCodes, ...) */
1454   pCodeRegMapLiveRanges( pc->pBlock ); /*FIXME:UNTESTED*/
1455
1456   if (comment)
1457   {
1458     pCodeInsertAfter (&pc->pc, newpCodeCharP (comment));
1459   } // if
1460
1461   if (1)
1462   {
1463     /* replace pc with commented out version of itself */
1464     char buffer[1024], buffer2[1024];
1465     char *pbuff = &buffer[0];
1466     int size=1024;
1467     pCode2str (&buffer2[0],1024,&pc->pc);
1468     SAFE_snprintf (&pbuff,&size,"%s:%u(%s): removed pCode was %s\t", __FILE__, __LINE__, __FUNCTION__, &buffer2[0]);
1469     pCodeInsertAfter (&pc->pc, newpCodeCharP (&buffer[0]));
1470   } // if
1471
1472   pc->pc.destruct (&pc->pc);
1473 }
1474
1475 /* ------------------------------------------------------------------
1476    Find the first (unique) assignment to `reg' (prior to pc).
1477    ------------------------------------------------------------------ */
1478
1479 pCode *findAssignmentToReg (regs *reg, pCode *pc)
1480 {
1481         pCode *curr;
1482
1483         assert (pc && isPCI(pc) && reg);
1484
1485         curr = findPrevInstruction (pc->prev);
1486
1487         while (curr && PCI(curr)->pcflow == PCI(pc)->pcflow)
1488         {
1489                 if (PCI(curr)->outCond & PCC_REGISTER)
1490                 {
1491                         regs *op = getRegFromInstruction (curr);
1492                         if (op && (sameRegs(op,reg)))
1493                                 return curr;
1494                 } // if
1495                 curr = findPrevInstruction (curr->prev);
1496         } // while
1497
1498         /* no assignment to reg found */
1499         return NULL;
1500 }
1501
1502 /* ------------------------------------------------------------------
1503    Find a register that holds the same value as `reg' (an alias).
1504    ------------------------------------------------------------------ */
1505
1506 regs *findRegisterAlias (regs *reg, pCode *pc)
1507 {
1508         pCode *curr;
1509
1510         if(!reg) return NULL;
1511
1512         if (regIsSpecial (reg, 0)) return NULL;
1513
1514         curr = findAssignmentToReg (reg, pc);
1515
1516         /* no assignment found --> no alias found */
1517         if (!curr) return NULL;
1518
1519         switch (PCI(curr)->op)
1520         {
1521         case POC_MOVWF:
1522                 /* find previous assignment to WREG */
1523                 while (curr && !(PCI(curr)->outCond & PCC_W))
1524                         curr = findPrevInstruction (curr->prev);
1525                 if (curr && PCI(curr)->op == POC_MOVFW)
1526                 {
1527                         regs *op = getRegFromInstruction (curr);
1528                         /* alias must not be changed since assignment... */
1529                         if (PCI(curr)->pcop)
1530                         {
1531                                 switch (PCI(curr)->pcop->type)
1532                                 {
1533                                 case PO_GPR_REGISTER:
1534                                 case PO_GPR_TEMP:
1535                                         /* these operands are ok */
1536                                         break;
1537                                 default:
1538                                         /* not a plain register operand */
1539                                         return NULL;
1540                                         break;
1541                                 }
1542                         }
1543                         if (!op || regIsSpecial (op, 0) || !regIsUnchangedSince (op, pc, curr)) return NULL;
1544                         //fprintf (stderr, "found register alias for %s: %s\n", reg->name, op && op->name ? op->name : "<no name>");
1545                         return op;
1546                 } else {
1547                         /* unknown source to WREG -- unknown register alias */
1548                         return NULL;
1549                 }
1550                 break;
1551
1552         default:
1553                 /* unhandled instruction -- assume unknown source, no alias */
1554                 return NULL;
1555         }
1556
1557         /* no alias found */
1558         return NULL;
1559 }
1560
1561 /* ------------------------------------------------------------------
1562    Analyze a single pCodeInstruction's dataflow relations and replace
1563    it with a better variant if possible.
1564    ------------------------------------------------------------------ */
1565
1566 void analyzeAndReplacePCI (pCodeInstruction *pci)
1567 {
1568         regs *op_reg, *alias_reg;
1569
1570         assert (pci);
1571
1572         if (!isPCI(pci)) return;
1573
1574         switch (pci->op)
1575         {
1576         case POC_MOVFW:
1577         case POC_ADDFW:
1578         case POC_ANDFW:
1579         case POC_IORFW:
1580         case POC_XORFW:
1581                 /* try to find a different source register */
1582                 op_reg = getRegFromInstruction (&pci->pc);
1583                 if (pci->op == POC_MOVFW) /* touches Z */
1584                 {
1585                         pCode *assignment = findAssignmentToReg (op_reg, &pci->pc);
1586                         if (assignment && isPCI(assignment) && (PCI(assignment)->op == POC_CLRF))
1587                         {
1588                                 replace_PCI (pci, PCI(newpCode(POC_MOVLW, newpCodeOpLit(0))), "replaced with CLRF");
1589                                 return;
1590                         }
1591                 }
1592
1593                 alias_reg = findRegisterAlias (op_reg, &pci->pc);
1594                 if (alias_reg)
1595                 {
1596                         replace_PCI (pci, PCI(newpCode(pci->op, newpCodeOpRegFromStr (alias_reg->name))), "=DF= replaced with move from register alias");
1597                 }
1598                 break;
1599
1600         default:
1601                 /* do not optimize */
1602                 break;
1603         } // switch
1604 }
1605
1606 extern pFile *the_pFile;
1607
1608 /* ------------------------------------------------------------------
1609    Find and remove dead pCodes.
1610    ------------------------------------------------------------------ */
1611
1612 static int removeDeadPCIs (void)
1613 {
1614         pBlock *pb;
1615         unsigned int removed = 0;
1616
1617         if (!the_pFile) return removed;
1618
1619         do {
1620                 removed = 0;
1621
1622                 /* iterate over all pBlocks */
1623                 for (pb = the_pFile->pbHead; pb; pb = pb->next)
1624                 {
1625                         pCode *pc, *pcnext = NULL;
1626
1627                         /* iterate over all pCodes */
1628                         for (pc = findNextInstruction (pb->pcHead); pc; pc = pcnext)
1629                         {
1630                                 pcnext = findNextInstruction (pc->next);
1631                                 removed += removeIfDeadPCI (pc);
1632                         } // while
1633                 } // for pb
1634
1635                 fprintf (stderr, "[removed %u dead pCodes]\n", removed);
1636         } while (removed);
1637
1638         return 0;
1639 }
1640
1641 /* ------------------------------------------------------------------
1642    This routine tries to optimize the dataflow by...
1643    (1)
1644
1645    This routine leaves in dead pCodes (assignments whose results are
1646    not used) -- these should be removed in a following sweep phase.
1647    ------------------------------------------------------------------ */
1648
1649 void optimizeDataflow (void)
1650 {
1651         pBlock *pb;
1652
1653         if (!the_pFile) return;
1654
1655         //fprintf (stderr, "%s:%u(%s): Starting optimization...\n", __FILE__, __LINE__, __FUNCTION__);
1656
1657         /* iterate over all pBlocks */
1658         for (pb = the_pFile->pbHead; pb; pb = pb->next)
1659         {
1660                 pCode *pc, *pcnext = NULL;
1661
1662                 /* iterate over all pCodes */
1663                 for (pc = findNextInstruction (pb->pcHead); pc; pc = pcnext)
1664                 {
1665                         pcnext = findNextInstruction (pc->next);
1666                         analyzeAndReplacePCI (PCI(pc));
1667                 } // while
1668         } // for pb
1669
1670         while (removeDeadPCIs ()) { /* remove dead codes in multiple passes */};
1671         df_removeStates ();
1672 }
1673
1674 #endif
1675
1676 /*-----------------------------------------------------------------*
1677 * void pCodeRegOptimeRegUsage(pBlock *pb)
1678 *-----------------------------------------------------------------*/
1679 void pCodeRegOptimizeRegUsage(int level)
1680 {
1681
1682         int passes;
1683         int saved = 0;
1684         int t = total_registers_saved;
1685
1686 #if 0
1687         /* This is currently broken (need rewrite to correctly
1688          * handle arbitrary pCodeOps instead of registers only). */
1689         if (!pic14_options.disable_df)
1690                 optimizeDataflow ();
1691 #endif
1692
1693         if(!register_optimization)
1694                 return;
1695 #define OPT_PASSES 4
1696         passes = OPT_PASSES;
1697
1698         do {
1699                 saved = total_registers_saved;
1700
1701                 /* Identify registers used in one flow sequence */
1702                 OptimizeRegUsage(dynAllocRegs,level, (OPT_PASSES-passes));
1703                 OptimizeRegUsage(dynStackRegs,level, (OPT_PASSES-passes));
1704                 OptimizeRegUsage(dynDirectRegs,0, (OPT_PASSES-passes));
1705
1706                 if(total_registers_saved != saved)
1707                         DFPRINTF((stderr, " *** pass %d, Saved %d registers, total saved %d ***\n",
1708                         (1+OPT_PASSES-passes),total_registers_saved-saved,total_registers_saved));
1709
1710                 passes--;
1711
1712         } while( passes && ((total_registers_saved != saved) || (passes==OPT_PASSES-1)) );
1713
1714         if(total_registers_saved == t)
1715                 DFPRINTF((stderr, "No registers saved on this pass\n"));
1716
1717
1718         /*
1719                 fprintf(stderr,"dynamically allocated regs:\n");
1720                 dbg_regusage(dynAllocRegs);
1721                 fprintf(stderr,"stack regs:\n");
1722                 dbg_regusage(dynStackRegs);
1723                 fprintf(stderr,"direct regs:\n");
1724                 dbg_regusage(dynDirectRegs);
1725         */
1726 }
1727
1728
1729 /*-----------------------------------------------------------------*
1730 * void RegsUnMapLiveRanges(set *regset)
1731 *
1732 *-----------------------------------------------------------------*/
1733 void  RegsSetUnMapLiveRanges(set *regset)
1734 {
1735         regs *reg;
1736
1737         while(regset) {
1738                 reg = regset->item;
1739                 regset = regset->next;
1740
1741
1742                 deleteSet(&reg->reglives.usedpCodes);
1743                 deleteSet(&reg->reglives.usedpFlows);
1744                 deleteSet(&reg->reglives.assignedpFlows);
1745
1746         }
1747
1748 }
1749
1750 void  RegsUnMapLiveRanges(void)
1751 {
1752
1753         RegsSetUnMapLiveRanges(dynAllocRegs);
1754         RegsSetUnMapLiveRanges(dynStackRegs);
1755         RegsSetUnMapLiveRanges(dynDirectRegs);
1756         RegsSetUnMapLiveRanges(dynProcessorRegs);
1757         RegsSetUnMapLiveRanges(dynDirectBitRegs);
1758         RegsSetUnMapLiveRanges(dynInternalRegs);
1759
1760 }