git.gag.com Git - fw/sdcc/blob - src/pic/pcodepeep.c

   1 /*-------------------------------------------------------------------------
   2
   3    pcodepeep.c - post code generation
   4    Written By -  Scott Dattalo scott@dattalo.com
   5
   6    This program is free software; you can redistribute it and/or modify it
   7    under the terms of the GNU General Public License as published by the
   8    Free Software Foundation; either version 2, or (at your option) any
   9    later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program; if not, write to the Free Software
  18    Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  19 -------------------------------------------------------------------------*/
  20
  21 #include <stdio.h>
  22
  23 #include "common.h"   // Include everything in the SDCC src directory
  24 #include "newalloc.h"
  25
  26
  27 #include "pcode.h"
  28 #include "ralloc.h"
  29
  30
  31 pCodeOp *newpCodeOpWild(int id, pCodePeep *pcp, pCodeOp *subtype);
  32 pCode *newpCodeWild(int pCodeID, pCodeOp *optional_operand, pCodeOp *optional_label);
  33 pCode * findNextInstruction(pCode *pc);
  34 char *Safe_strdup(char *str);
  35
  36
  37 /****************************************************************/
  38 /*
  39  * rootRules - defined in SDCCpeep.c
  40  *  This is a pointer to the (parsed) peephole rules that are
  41  * defined in peep.def.
  42  */
  43
  44 extern peepRule *rootRules;
  45
  46
  47 /****************************************************************/
  48 /****************************************************************/
  49 typedef struct _DLL {
  50   struct _DLL *prev;
  51   struct _DLL *next;
  52   //  void *data;
  53 } _DLL;
  54
  55
  56 typedef struct pCodePeepSnippets
  57 {
  58   _DLL dll;
  59   pCodePeep *peep;
  60 } pCodePeepSnippets;
  61
  62
  63 static pCodePeepSnippets  *peepSnippets=NULL;
  64
  65
  66 void printpCodeString(FILE *of, pCode *pc, int max)
  67 {
  68   int i=0;
  69
  70   while(pc && (i++<max)) {
  71     pc->print(of,pc);
  72     pc = pc->next;
  73   }
  74 }
  75
  76 /*-----------------------------------------------------------------*/
  77 /* _DLL * DLL_append                                               */
  78 /*                                                                 */
  79 /*  Append a _DLL object to the end of a _DLL (doubly linked list) */
  80 /* If The list to which we want to append is non-existant then one */
  81 /* is created. Other wise, the end of the list is sought out and   */
  82 /* a new DLL object is appended to it. In either case, the void    */
  83 /* *data is added to the newly created DLL object.                 */
  84 /*-----------------------------------------------------------------*/
  85
  86 static void * DLL_append(_DLL *list, _DLL *next)
  87 {
  88   _DLL *b;
  89
  90
  91   /* If there's no list, then create one: */
  92   if(!list) {
  93     next->next = next->prev = NULL;
  94     return next;
  95   }
  96
  97
  98   /* Search for the end of the list. */
  99   b = list;
 100   while(b->next)
 101     b = b->next;
 102
 103   /* Now append the new DLL object */
 104   b->next = next;
 105   b->next->prev = b;
 106   b = b->next;
 107   b->next = NULL;
 108
 109   return list;
 110
 111 }
 112
 113
 114 /*-----------------------------------------------------------------
 115
 116   pCode peephole optimization
 117
 118
 119   The pCode "peep hole" optimization is not too unlike the peep hole
 120   optimization in SDCCpeeph.c. The major difference is that here we
 121   use pCode's whereas there we use ASCII strings. The advantage with
 122   pCode's is that we can ascertain flow information in the instructions
 123   being optimized.
 124
 125
 126 <FIX ME> - elaborate...
 127
 128   -----------------------------------------------------------------*/
 129
 130 #if 0
 131 /*-----------------------------------------------------------------*/
 132 /* pCodePeep */
 133 /*-----------------------------------------------------------------*/
 134 int pCodePeepCompare(pCode *pc, pCodePeep *pcp)
 135 {
 136   pCode *pcfrom,*pcto;
 137
 138   pcfrom = pc;
 139   for( pcto=pcp->target; pcto; pcto=pcto->next) {
 140
 141     pcfrom = findNextInstruction(pcfrom);
 142
 143     if( pcfrom &&
 144         (PCI(pcfrom)->op == PCI(pcto)->op ||
 145          PCI(pcto)->op == POC_WILD))
 146       continue;
 147     return 0;
 148   }
 149   return 0;
 150 }
 151
 152 /*-----------------------------------------------------------------*/
 153 /* pCodePeep */
 154 /*-----------------------------------------------------------------*/
 155 void pCodePeepSearch(pCodePeep *snippet)
 156 {
 157   pBlock *pb;
 158   pCode *pc;
 159
 160   if(!the_pFile)
 161     return;
 162
 163   /* compare the chain to the pCode that we've
 164      got so far. If a match is found, then replace
 165      the pCode chain.
 166   */
 167   for(pb = the_pFile->pbHead; pb; pb = pb->next) {
 168     for(pc = pb->pcHead; pc; pc = pc->next) {
 169       pCodePeepCompare(pc,snippet);
 170     }
 171   }
 172
 173 }
 174 #endif
 175
 176 #if 0
 177 pBlock *pBlockAppend(pBlock *pb1, pBlock *pb2)
 178 {
 179   pBlock *pb;
 180
 181   if(!pb1->tail)
 182     return pb2;
 183
 184   pb = pb1->tail;
 185
 186   pb2->head = pb1;
 187   pb2->tail = NULL;
 188   pb1->tail = pb2;
 189
 190 }
 191
 192 #endif
 193
 194 void pCodePeepInit(void)
 195 {
 196   pBlock *pb;
 197   //  pCode *pc;
 198   pCodePeep *pcp;
 199   pCodePeepSnippets *pcps;
 200
 201   /* Declare a peep code snippet */
 202   /* <FIXME> do I really need a separate struct just to DLL the snippets? */
 203   /* e.g. I could put the DLL into the pCodePeep structure */
 204   pcps = Safe_calloc(1,sizeof(pCodePeepSnippets));
 205   pcp = pcps->peep  = Safe_calloc(1,sizeof(pCodePeep));
 206   peepSnippets = DLL_append((_DLL*)peepSnippets,(_DLL*)pcps);
 207
 208
 209   pb = newpCodeChain(NULL, 'W', newpCode(POC_MOVWF, newpCodeOpWild(0,pcp,newpCodeOp(NULL,PO_GPR_REGISTER))) );
 210   addpCode2pBlock( pb,     newpCode(POC_MOVFW, newpCodeOpWild(0,pcp,newpCodeOp(NULL,PO_GPR_REGISTER))) );
 211
 212   pcp->target = pb;
 213
 214   pcp->replace = newpCodeChain(NULL, 'W',newpCode(POC_MOVWF, newpCodeOpWild(0,pcp,newpCodeOp(NULL,PO_GPR_REGISTER))) );
 215
 216   /* Allocate space to store pointers to the wildcard variables */
 217   pcp->nvars = 1;
 218   pcp->vars  = Safe_calloc(pcp->nvars, sizeof(char *));
 219   pcp->nwildpCodes = 0;
 220   pcp->wildpCodes  = NULL;
 221
 222   pcp->postFalseCond = PCC_Z;
 223   pcp->postTrueCond  = PCC_NONE;
 224
 225   fprintf(stderr,"Peep rule\nTarget:\n");
 226   printpCodeString(stderr,pcp->target->pcHead, 10);
 227   fprintf(stderr,"Replaced with:\n");
 228   printpCodeString(stderr,pcp->replace->pcHead, 10);
 229
 230   /* Now for another peep example */
 231   pcps = Safe_calloc(1,sizeof(pCodePeepSnippets));
 232   pcp = pcps->peep  = Safe_calloc(1,sizeof(pCodePeep));
 233   peepSnippets = DLL_append((_DLL*)peepSnippets,(_DLL*)pcps);
 234
 235   {
 236     pCodeOp *pcl;
 237     pCodeOp *pcw;
 238     pCodeOp *pcwb;
 239
 240     pcwb =  newpCodeOpWild(0,pcp,newpCodeOpBit(NULL,-1));
 241     pb = newpCodeChain(NULL, 'W',newpCode(POC_BTFSC,pcwb));
 242
 243     pcl = newpCodeOpLabel(-1);
 244     pcw = newpCodeOpWild(1, pcp, pcl);
 245     addpCode2pBlock( pb,     newpCode(POC_GOTO,  pcw));
 246     addpCode2pBlock( pb,     newpCodeWild(0,NULL,NULL));
 247     addpCode2pBlock( pb,     newpCodeWild(1,NULL,pcw));
 248
 249
 250     pcp->target = pb;
 251
 252     pb = newpCodeChain(NULL, 'W',newpCode(POC_BTFSS, pcwb));
 253     addpCode2pBlock( pb,     newpCodeWild(0,NULL,NULL));
 254     addpCode2pBlock( pb,     newpCodeWild(1,NULL,pcw));
 255
 256     pcp->replace = pb;
 257
 258     /* Allocate space to store pointers to the wildcard variables */
 259     pcp->nvars = 2;
 260     pcp->vars = Safe_calloc(pcp->nvars, sizeof(char *));
 261     pcp->nwildpCodes = 2;
 262     pcp->wildpCodes = Safe_calloc(pcp->nwildpCodes, sizeof(pCode *));
 263
 264     pcp->postFalseCond = PCC_NONE;
 265     pcp->postTrueCond  = PCC_NONE;
 266   }
 267
 268
 269
 270
 271
 272
 273
 274
 275
 276
 277   //-------------
 278
 279   /* Now for another peep example */
 280   pcps = Safe_calloc(1,sizeof(pCodePeepSnippets));
 281   pcp = pcps->peep  = Safe_calloc(1,sizeof(pCodePeep));
 282   peepSnippets = DLL_append((_DLL*)peepSnippets,(_DLL*)pcps);
 283
 284   {
 285     pCodeOp *pcw;
 286
 287     pcw = newpCodeOpWild(0,pcp,newpCodeOp(NULL,PO_GPR_REGISTER));
 288
 289     pb = newpCodeChain(NULL, 'W', newpCode(POC_MOVWF, pcw));
 290     addpCode2pBlock( pb,     newpCode(POC_MOVWF, pcw));
 291
 292     pcp->target = pb;
 293
 294     pb = newpCodeChain(NULL, 'W',newpCode(POC_MOVWF, pcw));
 295
 296     pcp->replace = pb;
 297
 298     /* Allocate space to store pointers to the wildcard variables */
 299     pcp->nvars = 1;
 300     pcp->vars = Safe_calloc(pcp->nvars, sizeof(char *));
 301     pcp->nwildpCodes = 0;
 302     pcp->wildpCodes = NULL;
 303
 304     pcp->postFalseCond = PCC_NONE;
 305     pcp->postTrueCond  = PCC_NONE;
 306   }
 307
 308
 309
 310
 311 }
 312
 313 /*-----------------------------------------------------------------*/
 314 /* pCodeSearchCondition - Search a pCode chain for a 'condition'   */
 315 /*                                                                 */
 316 /* return conditions                                               */
 317 /*  1 - The Condition was found for a pCode's input                */
 318 /*  0 - No matching condition was found for the whole chain        */
 319 /* -1 - The Condition was found for a pCode's output               */
 320 /*                                                                 */
 321 /*-----------------------------------------------------------------*/
 322 int pCodeSearchCondition(pCode *pc, unsigned int cond)
 323 {
 324
 325   while(pc) {
 326
 327     /* If we reach a function end (presumably an end since we most
 328        probably began the search in the middle of a function), then
 329        the condition was not found. */
 330     if(pc->type == PC_FUNCTION)
 331       return 0;
 332
 333     if(pc->type == PC_OPCODE) {
 334       if(PCI(pc)->inCond & cond)
 335         return 1;
 336       if(PCI(pc)->outCond & cond)
 337         return -1;
 338     }
 339
 340     pc = pc->next;
 341   }
 342
 343   return 0;
 344 }
 345 /*-----------------------------------------------------------------*/
 346 /* pCodePeepMatchLine - Compare source and destination pCodes to   */
 347 /*                      see they're the same.                      */
 348 /*-----------------------------------------------------------------*/
 349 int pCodePeepMatchLine(pCodePeep *peepBlock, pCode *pcs, pCode *pcd)
 350 {
 351   int index;   // index into wild card arrays
 352
 353   if(pcs->type == pcd->type) {
 354
 355     if(pcs->type == PC_OPCODE) {
 356
 357       /* If the opcodes don't match then the line doesn't match */
 358       if(PCI(pcs)->op != PCI(pcd)->op)
 359         return 0;
 360
 361       fprintf(stderr,"%s comparing\n",__FUNCTION__);
 362       pcs->print(stderr,pcs);
 363       pcd->print(stderr,pcd);
 364
 365       /* Compare the operands */
 366       if(PCI(pcd)->pcop) {
 367         if (PCI(pcd)->pcop->type == PO_WILD) {
 368           index = PCOW(PCI(pcd)->pcop)->id;
 369
 370           fprintf(stderr,"destination is wild\n");
 371 #ifdef DEBUG_PCODEPEEP
 372           if (index > peepBlock->nvars) {
 373             fprintf(stderr,"%s - variables exceeded\n",__FUNCTION__);
 374             exit(1);
 375           }
 376 #endif
 377           PCOW(PCI(pcd)->pcop)->matched = PCI(pcs)->pcop;
 378           {
 379             char *n;
 380
 381             if(PCI(pcs)->pcop->type == PO_GPR_TEMP)
 382               n = PCOR(PCI(pcs)->pcop)->r->name;
 383             else
 384               n = PCI(pcs)->pcop->name;
 385
 386             if(peepBlock->vars[index])
 387               return  (strcmp(peepBlock->vars[index],n) == 0);
 388             else {
 389               peepBlock->vars[index] = n; //PCI(pcs)->pcop->name;
 390               return 1;
 391             }
 392           }
 393         }
 394       } else
 395         /* The pcd has no operand. Lines match if pcs has no operand either*/
 396         return (PCI(pcs)->pcop == NULL);
 397     }
 398   }
 399
 400
 401   if((pcd->type == PC_WILD) && (pcs->type == PC_OPCODE)) {
 402
 403     int labindex;
 404
 405     index = PCW(pcd)->id;
 406
 407     fprintf(stderr,"%s comparing wild cards\n",__FUNCTION__);
 408     pcs->print(stderr,pcs);
 409     pcd->print(stderr,pcd);
 410
 411     peepBlock->wildpCodes[PCW(pcd)->id] = pcs;
 412
 413     /* Check for a label associated with this wild pCode */
 414     // If the wild card has a label, make sure the source code does too.
 415     if(PCW(pcd)->label) {
 416       if(!pcs->label)
 417         return 0;
 418
 419       labindex = PCOW(PCW(pcd)->label)->id;
 420       if(peepBlock->vars[labindex] == NULL) {
 421         // First time to encounter this label
 422         peepBlock->vars[labindex] = PCL(pcs->label->pc)->label;
 423         fprintf(stderr,"first time for a label\n");
 424       } else {
 425         if(strcmp(peepBlock->vars[labindex],PCL(pcs->label->pc)->label) != 0) {
 426           fprintf(stderr,"labels don't match\n");
 427           return 0;
 428         }
 429         fprintf(stderr,"matched a label\n");
 430       }
 431
 432     }
 433
 434     if(PCW(pcd)->operand) {
 435       PCOW(PCI(pcd)->pcop)->matched = PCI(pcs)->pcop;
 436       if(peepBlock->vars[index]) {
 437         int i = (strcmp(peepBlock->vars[index],PCI(pcs)->pcop->name) == 0);
 438         if(i)
 439           fprintf(stderr," (matched)\n");
 440         else {
 441           fprintf(stderr," (no match: wild card operand mismatch\n");
 442           fprintf(stderr,"  peepblock= %s,  pcodeop= %s\n",
 443                   peepBlock->vars[index],
 444                   PCI(pcs)->pcop->name);
 445         }
 446         return i;
 447       } else {
 448         peepBlock->vars[index] = PCI(pcs)->pcop->name;
 449         return 1;
 450       }
 451     }
 452
 453     pcs = findNextInstruction(pcs->next);
 454     if(pcs) {
 455       fprintf(stderr," (next to match)\n");
 456       pcs->print(stderr,pcs);
 457     }
 458
 459     return 1; /*  wild card matches */
 460   }
 461
 462   return 0;
 463 }
 464
 465 /*-----------------------------------------------------------------*/
 466 /*-----------------------------------------------------------------*/
 467 void pCodePeepClrVars(pCodePeep *pcp)
 468 {
 469
 470   int i;
 471
 472   for(i=0;i<pcp->nvars; i++)
 473     pcp->vars[i] = NULL;
 474
 475 }
 476
 477 /*-----------------------------------------------------------------*/
 478 /*-----------------------------------------------------------------*/
 479 void pCodeInsertAfter(pCode *pc1, pCode *pc2)
 480 {
 481
 482   if(!pc1 || !pc2)
 483     return;
 484
 485   pc2->next = pc1->next;
 486   if(pc1->next)
 487     pc1->next->prev = pc2;
 488
 489   pc2->prev = pc1;
 490   pc1->next = pc2;
 491
 492 }
 493
 494 /*-----------------------------------------------------------------*/
 495 /* pCodeOpCopy - copy a pcode operator                             */
 496 /*-----------------------------------------------------------------*/
 497 static pCodeOp *pCodeOpCopy(pCodeOp *pcop)
 498 {
 499   pCodeOp *pcopnew=NULL;
 500
 501   if(!pcop)
 502     return NULL;
 503
 504   switch(pcop->type) {
 505   case PO_CRY:
 506   case PO_BIT:
 507     pcopnew = Safe_calloc(1,sizeof(pCodeOpBit) );
 508     PCOB(pcopnew)->bit = PCOB(pcop)->bit;
 509     PCOB(pcopnew)->inBitSpace = PCOB(pcop)->inBitSpace;
 510
 511     break;
 512
 513   case PO_WILD:
 514     /* Here we expand the wild card into the appropriate type: */
 515     /* By recursively calling pCodeOpCopy */
 516     if(PCOW(pcop)->matched)
 517       pcopnew = pCodeOpCopy(PCOW(pcop)->matched);
 518     else {
 519       // Probably a label
 520       pcopnew = pCodeOpCopy(PCOW(pcop)->subtype);
 521       pcopnew->name = Safe_strdup(PCOW(pcop)->pcp->vars[PCOW(pcop)->id]);
 522       fprintf(stderr,"copied a wild op named %s\n",pcopnew->name);
 523     }
 524
 525     return pcopnew;
 526     break;
 527
 528   case PO_LABEL:
 529     pcopnew = Safe_calloc(1,sizeof(pCodeOpLabel) );
 530     PCOLAB(pcopnew)->key =  PCOLAB(pcop)->key;
 531     break;
 532
 533   case PO_LITERAL:
 534   case PO_IMMEDIATE:
 535     pcopnew = Safe_calloc(1,sizeof(pCodeOpLit) );
 536     PCOL(pcopnew)->lit = PCOL(pcop)->lit;
 537     break;
 538
 539   case PO_GPR_REGISTER:
 540   case PO_GPR_TEMP:
 541   case PO_SFR_REGISTER:
 542   case PO_DIR:
 543   case PO_STR:
 544   case PO_NONE:
 545   case PO_W:
 546   case PO_STATUS:
 547   case PO_FSR:
 548   case PO_INDF:
 549
 550     pcopnew = Safe_calloc(1,sizeof(pCodeOp) );
 551
 552   }
 553
 554   pcopnew->type = pcop->type;
 555   pcopnew->name = Safe_strdup(pcop->name);
 556
 557   return pcopnew;
 558 }
 559
 560 #if 0
 561 /*-----------------------------------------------------------------*/
 562 /* pCodeCopy - copy a pcode                                        */
 563 /*-----------------------------------------------------------------*/
 564 static pCode *pCodeCopy(pCode *pc)
 565 {
 566
 567   pCode *pcnew;
 568
 569   pcnew = newpCode(pc->type,pc->pcop);
 570 }
 571 #endif
 572 /*-----------------------------------------------------------------*/
 573 /*-----------------------------------------------------------------*/
 574 void pCodeDeleteChain(pCode *f,pCode *t)
 575 {
 576   pCode *pc;
 577
 578   while(f && f!=t) {
 579     fprintf(stderr,"delete pCode:\n");
 580     pc = f->next;
 581     f->print(stderr,f);
 582     //f->delete(f);
 583     f = pc;
 584   }
 585
 586 }
 587 /*-----------------------------------------------------------------*/
 588 /*-----------------------------------------------------------------*/
 589 int pCodePeepMatchRule(pCode *pc)
 590 {
 591   pCodePeep *peepBlock;
 592   pCode *pct, *pcin;
 593   _DLL *peeprules;
 594   int matched;
 595
 596   peeprules = (_DLL *)peepSnippets;
 597
 598   while(peeprules) {
 599     peepBlock = ((pCodePeepSnippets*)peeprules)->peep;
 600     pCodePeepClrVars(peepBlock);
 601
 602     pcin = pc;
 603     pct = peepBlock->target->pcHead;
 604     matched = 0;
 605     while(pct && pcin) {
 606
 607       if(! (matched = pCodePeepMatchLine(peepBlock, pcin,pct)))
 608         break;
 609
 610       pcin = findNextInstruction(pcin->next);
 611       pct = pct->next;
 612       //debug:
 613       fprintf(stderr,"    matched\n");
 614       if(!pcin)
 615         fprintf(stderr," end of code\n");
 616       if(!pct)
 617         fprintf(stderr," end of rule\n");
 618     }
 619
 620     if(matched && pcin) {
 621
 622       /* So far we matched the rule up to the point of the conditions .
 623        * In other words, all of the opcodes match. Now we need to see
 624        * if the post conditions are satisfied.
 625        * First we check the 'postFalseCond'. This means that we check
 626        * to see if any of the subsequent pCode's in the pCode chain
 627        * following the point just past where we have matched depend on
 628        * the `postFalseCond' as input then we abort the match
 629        */
 630       fprintf(stderr,"    matched rule so far, now checking conditions\n");
 631       if (peepBlock->postFalseCond &&
 632           (pCodeSearchCondition(pcin,peepBlock->postFalseCond) > 0) )
 633         matched = 0;
 634     }
 635
 636     if(matched && pcin) {
 637
 638       pCode *pcprev;
 639       pCode *pcr;
 640
 641
 642       /* We matched a rule! Now we have to go through and remove the
 643          inefficient code with the optimized version */
 644
 645       fprintf(stderr, "Found a pcode peep match:\nRule:\n");
 646       printpCodeString(stderr,peepBlock->target->pcHead,10);
 647       fprintf(stderr,"first thing matched\n");
 648       pc->print(stderr,pc);
 649       fprintf(stderr,"last thing matched\n");
 650       pcin->print(stderr,pcin);
 651
 652       /* Unlink the original code */
 653       pcprev = pc->prev;
 654       pcprev->next = pcin;
 655       pcin->prev = pc->prev;
 656       pCodeDeleteChain(pc,pcin);
 657
 658       /* Generate the replacement code */
 659       pc = pcprev;
 660       pcr = peepBlock->replace->pcHead;  // This is the replacement code
 661       while (pcr) {
 662         pCodeOp *pcop=NULL;
 663         /* If the replace pcode is an instruction with an operand, */
 664         /* then duplicate the operand (and expand wild cards in the process). */
 665         if(pcr->type == PC_OPCODE) {
 666           if(PCI(pcr)->pcop)
 667             pcop = pCodeOpCopy(PCI(pcr)->pcop);
 668
 669           pCodeInsertAfter(pc, newpCode(PCI(pcr)->op,pcop));
 670         } else if (pcr->type == PC_WILD) {
 671           pCodeInsertAfter(pc,peepBlock->wildpCodes[PCW(pcr)->id]);
 672         }
 673
 674
 675         pc = pc->next;
 676         pc->print(stderr,pc);
 677         pcr = pcr->next;
 678       }
 679
 680       return 1;
 681     }
 682
 683     peeprules = peeprules->next;
 684   }
 685
 686   return 0;
 687 }