git.gag.com Git - fw/sdcc/blob - src/pic/pcode.h

   1 /*-------------------------------------------------------------------------
   2
   3    pcode.h - 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
  22 //#include "ralloc.h"
  23 struct regs;
  24
  25 /*
  26    Post code generation
  27
  28    The post code generation is an assembler optimizer. The assembly code
  29    produced by all of the previous steps is fully functional. This step
  30    will attempt to analyze the flow of the assembly code and agressively
  31    optimize it. The peep hole optimizer attempts to do the same thing.
  32    As you may recall, the peep hole optimizer replaces blocks of assembly
  33    with more optimal blocks (e.g. removing redundant register loads).
  34    However, the peep hole optimizer has to be somewhat conservative since
  35    an assembly program has implicit state information that's unavailable
  36    when only a few instructions are examined.
  37      Consider this example:
  38
  39    example1:
  40      movwf  t1
  41      movf   t1,w
  42
  43    The movf seems redundant since we know that the W register already
  44    contains the same value of t1. So a peep hole optimizer is tempted to
  45    remove the "movf". However, this is dangerous since the movf affects
  46    the flags in the status register (specifically the Z flag) and subsequent
  47    code may depend upon this. Look at these two examples:
  48
  49    example2:
  50      movwf  t1
  51      movf   t1,w     ; Can't remove this movf
  52      skpz
  53       return
  54
  55    example3:
  56      movwf  t1
  57      movf   t1,w     ; This  movf can be removed
  58      xorwf  t2,w     ; since xorwf will over write Z
  59      skpz
  60       return
  61
  62 */
  63
  64
  65 #ifndef __PCODE_H__
  66 #define __PCODE_H__
  67
  68 /***********************************************************************
  69  *  PIC status bits - this will move into device dependent headers
  70  ***********************************************************************/
  71 #define PIC_C_BIT    0
  72 #define PIC_DC_BIT   1
  73 #define PIC_Z_BIT    2
  74
  75 /***********************************************************************
  76  *  Operand types
  77  ***********************************************************************/
  78 #define POT_RESULT  0
  79 #define POT_LEFT    1
  80 #define POT_RIGHT   2
  81
  82
  83 /***********************************************************************
  84  *
  85  *  PIC_OPTYPE - Operand types that are specific to the PIC architecture
  86  *
  87  *  If a PIC assembly instruction has an operand then here is where we
  88  *  associate a type to it. For example,
  89  *
  90  *     movf    reg,W
  91  *
  92  *  The movf has two operands: 'reg' and the W register. 'reg' is some
  93  *  arbitrary general purpose register, hence it has the type PO_GPR_REGISTER.
  94  *  The W register, which is the PIC's accumulator, has the type PO_W.
  95  *
  96  ***********************************************************************/
  97
  98
  99
 100 typedef enum
 101 {
 102   PO_NONE=0,         // No operand e.g. NOP
 103   PO_W,              // The 'W' register
 104   PO_STATUS,         // The 'STATUS' register
 105   PO_FSR,            // The "file select register" (in 18c it's one of three)
 106   PO_INDF,           // The Indirect register
 107   PO_GPR_REGISTER,   // A general purpose register
 108   PO_GPR_BIT,        // A bit of a general purpose register
 109   PO_GPR_TEMP,       // A general purpose temporary register
 110   PO_SFR_REGISTER,   // A special function register (e.g. PORTA)
 111   PO_PCL,            // Program counter Low register
 112   PO_PCLATH,         // Program counter Latch high register
 113   PO_LITERAL,        // A constant
 114   PO_IMMEDIATE,      //  (8051 legacy)
 115   PO_DIR,            // Direct memory (8051 legacy)
 116   PO_CRY,            // bit memory (8051 legacy)
 117   PO_BIT,            // bit operand.
 118   PO_STR,            //  (8051 legacy)
 119   PO_LABEL,
 120   PO_WILD            // Wild card operand in peep optimizer
 121 } PIC_OPTYPE;
 122
 123
 124 /*************************************************
 125  * pCode conditions:
 126  *
 127  * The "conditions" are bit-mapped flags that describe
 128  * input and/or output conditions that are affected by
 129  * the instructions. For example:
 130  *
 131  *    MOVF   SOME_REG,W
 132  *
 133  * This instruction depends upon 'SOME_REG'. Consequently
 134  * it has the input condition PCC_REGISTER set to true.
 135  *
 136  * In addition, this instruction affects the Z bit in the
 137  * status register and affects W. Thus the output conditions
 138  * are the logical or:
 139  *  PCC_ZERO_BIT | PCC_W
 140  *
 141  * The conditions are intialized when the pCode for an
 142  * instruction is created. They're subsequently used
 143  * by the pCode optimizer determine state information
 144  * in the program flow.
 145  *************************************************/
 146
 147 #define  PCC_NONE          0
 148 #define  PCC_REGISTER      (1<<0)
 149 #define  PCC_C             (1<<1)
 150 #define  PCC_Z             (1<<2)
 151 #define  PCC_DC            (1<<3)
 152 #define  PCC_W             (1<<4)
 153 #define  PCC_EXAMINE_PCOP  (1<<5)
 154
 155 /***********************************************************************
 156  *
 157  *  PIC_OPCODE
 158  *
 159  *  This is not a list of the PIC's opcodes per se, but instead
 160  *  an enumeration of all of the different types of pic opcodes.
 161  *
 162  ***********************************************************************/
 163
 164 typedef enum
 165 {
 166   POC_WILD=-1,   /* Wild card - used in the pCode peep hole optimizer
 167                   * to represent ANY pic opcode */
 168   POC_ADDLW=0,
 169   POC_ADDWF,
 170   POC_ADDFW,
 171   POC_ANDLW,
 172   POC_ANDWF,
 173   POC_ANDFW,
 174   POC_BCF,
 175   POC_BSF,
 176   POC_BTFSC,
 177   POC_BTFSS,
 178   POC_CALL,
 179   POC_COMF,
 180   POC_COMFW,
 181   POC_CLRF,
 182   POC_CLRW,
 183   POC_DECF,
 184   POC_DECFW,
 185   POC_DECFSZ,
 186   POC_DECFSZW,
 187   POC_GOTO,
 188   POC_INCF,
 189   POC_INCFW,
 190   POC_INCFSZ,
 191   POC_INCFSZW,
 192   POC_IORLW,
 193   POC_IORWF,
 194   POC_IORFW,
 195   POC_MOVF,
 196   POC_MOVFW,
 197   POC_MOVLW,
 198   POC_MOVWF,
 199   POC_NEGF,
 200   POC_RETLW,
 201   POC_RETURN,
 202   POC_RLF,
 203   POC_RLFW,
 204   POC_RRF,
 205   POC_RRFW,
 206   POC_SUBLW,
 207   POC_SUBWF,
 208   POC_SUBFW,
 209   POC_SWAPF,
 210   POC_SWAPFW,
 211   POC_TRIS,
 212   POC_XORLW,
 213   POC_XORWF,
 214   POC_XORFW
 215 } PIC_OPCODE;
 216
 217
 218 /***********************************************************************
 219  *  PC_TYPE  - pCode Types
 220  ***********************************************************************/
 221
 222 typedef enum
 223 {
 224   PC_COMMENT=0,   // pCode is a comment
 225   PC_OPCODE,      // PORT dependent opcode
 226   PC_LABEL,       // assembly label
 227   PC_FUNCTION,    // Function start or end
 228   PC_WILD         // wildcard - an opcode place holder
 229 } PC_TYPE;
 230
 231 /************************************************/
 232 /***************  Structures ********************/
 233 /************************************************/
 234 struct pCode;
 235
 236 /*************************************************
 237   pBranch
 238
 239   The first step in optimizing pCode is determining
 240  the program flow. This information is stored in
 241  single-linked lists in the for of 'from' and 'to'
 242  objects with in a pcode. For example, most instructions
 243  don't involve any branching. So their from branch
 244  points to the pCode immediately preceding them and
 245  their 'to' branch points to the pcode immediately
 246  following them. A skip instruction is an example of
 247  a pcode that has multiple (in this case two) elements
 248  in the 'to' branch. A 'label' pcode is an where there
 249  may be multiple 'from' branches.
 250  *************************************************/
 251
 252 typedef struct pBranch
 253 {
 254   struct pCode   *pc;    // Next pCode in a branch
 255   struct pBranch *next;  /* If more than one branch
 256                           * the next one is here */
 257
 258 } pBranch;
 259
 260 /*************************************************
 261   pCodeOp
 262
 263   pCode Operand structure.
 264   For those assembly instructions that have arguments,
 265   the pCode will have a pCodeOp in which the argument
 266   can be stored. For example
 267
 268     movf   some_register,w
 269
 270   'some_register' will be stored/referenced in a pCodeOp
 271
 272  *************************************************/
 273
 274 typedef struct pCodeOp
 275 {
 276   PIC_OPTYPE type;
 277   char *name;
 278
 279 } pCodeOp;
 280
 281 typedef struct pCodeOpBit
 282 {
 283   pCodeOp pcop;
 284   int bit;
 285   unsigned int inBitSpace: 1; /* True if in bit space, else
 286                                  just a bit of a register */
 287 } pCodeOpBit;
 288
 289 typedef struct pCodeOpLit
 290 {
 291   pCodeOp pcop;
 292   int lit;
 293 } pCodeOpLit;
 294
 295 typedef struct pCodeOpLabel
 296 {
 297   pCodeOp pcop;
 298   int key;
 299 } pCodeOpLabel;
 300
 301 typedef struct pCodeOpReg
 302 {
 303   pCodeOp pcop;    // Can be either GPR or SFR
 304   int rIdx;        // Index into the register table
 305   struct regs *r;
 306   struct pBlock *pb;
 307 } pCodeOpReg;
 308
 309 typedef struct pCodeOpRegBit
 310 {
 311   pCodeOpReg  pcor;       // The Register containing this bit
 312   int bit;                // 0-7 bit number.
 313   PIC_OPTYPE subtype;     // The type of this register.
 314 } pCodeOpRegBit;
 315
 316
 317 /*************************************************
 318     pCode
 319
 320     Here is the basic build block of a PIC instruction.
 321     Each pic instruction will get allocated a pCode.
 322     A linked list of pCodes makes a program.
 323
 324 **************************************************/
 325
 326 typedef struct pCode
 327 {
 328   PC_TYPE    type;
 329
 330   struct pCode *prev;  // The pCode objects are linked together
 331   struct pCode *next;  // in doubly linked lists.
 332
 333   int seq;             // sequence number
 334
 335   pBranch *from;       // pCodes that execute before this one
 336   pBranch *to;         // pCodes that execute after
 337   pBranch *label;      // pCode instructions that have labels
 338
 339   struct pBlock *pb;   // The pBlock that contains this pCode.
 340
 341   /* "virtual functions"
 342    *  The pCode structure is like a base class
 343    * in C++. The subsequent structures that "inherit"
 344    * the pCode structure will initialize these function
 345    * pointers to something useful */
 346   void (*analyze) (struct pCode *_this);
 347   void (*destruct)(struct pCode *_this);
 348   void (*print)  (FILE *of,struct pCode *_this);
 349
 350 } pCode;
 351
 352
 353 /*************************************************
 354     pCodeComment
 355 **************************************************/
 356
 357 typedef struct pCodeComment
 358 {
 359
 360   pCode  pc;
 361
 362   char *comment;
 363
 364 } pCodeComment;
 365
 366 /*************************************************
 367     pCodeInstruction
 368
 369     Here we describe all the facets of a PIC instruction
 370     (expansion for the 18cxxx is also provided).
 371
 372 **************************************************/
 373
 374 typedef struct pCodeInstruction
 375 {
 376
 377   pCode  pc;
 378
 379   PIC_OPCODE op;        // The opcode of the instruction.
 380
 381   char const * const mnemonic;       // Pointer to mnemonic string
 382
 383   pCodeOp *pcop;        // Operand
 384
 385   unsigned int num_ops;
 386   unsigned int dest:     1;       // If destination is W or F, then 1==F
 387   unsigned int bit_inst: 1;
 388
 389   unsigned int inCond;   // Input conditions for this instruction
 390   unsigned int outCond;  // Output conditions for this instruction
 391
 392 } pCodeInstruction;
 393
 394
 395 /*************************************************
 396     pCodeLabel
 397 **************************************************/
 398
 399 typedef struct pCodeLabel
 400 {
 401
 402   pCode  pc;
 403
 404   char *label;
 405   int key;
 406
 407 } pCodeLabel;
 408
 409 /*************************************************
 410     pCodeFunction
 411 **************************************************/
 412
 413 typedef struct pCodeFunction
 414 {
 415
 416   pCode  pc;
 417
 418   char *modname;
 419   char *fname;     /* If NULL, then this is the end of
 420                       a function. Otherwise, it's the
 421                       start and the name is contained
 422                       here */
 423
 424 } pCodeFunction;
 425
 426
 427 /*************************************************
 428     pCodeWild
 429 **************************************************/
 430
 431 typedef struct pCodeWild
 432 {
 433
 434   pCode  pc;
 435
 436   int    id;     /* Index into the wild card array of a peepBlock
 437                   * - this wild card will get expanded into that pCode
 438                   *   that is stored at this index */
 439
 440
 441   pCodeOp *operand;  // Optional operand
 442   pCodeOp *label;    // Optional label
 443
 444 } pCodeWild;
 445
 446 /*************************************************
 447     pBlock
 448
 449     Here are PIC program snippets. There's a strong
 450     correlation between the eBBlocks and pBlocks.
 451     SDCC subdivides a C program into managable chunks.
 452     Each chunk becomes a eBBlock and ultimately in the
 453     PIC port a pBlock.
 454
 455 **************************************************/
 456
 457 typedef struct pBlock
 458 {
 459   memmap *cmemmap;   /* The snippet is from this memmap */
 460   char   dbName;     /* if cmemmap is NULL, then dbName will identify the block */
 461   pCode *pcHead;     /* A pointer to the first pCode in a link list of pCodes */
 462   pCode *pcTail;     /* A pointer to the last pCode in a link list of pCodes */
 463
 464   struct pBlock *next;      /* The pBlocks will form a doubly linked list */
 465   struct pBlock *prev;
 466
 467   set *function_entries;    /* dll of functions in this pblock */
 468   set *function_exits;
 469   set *function_calls;
 470   set *registers;
 471
 472   unsigned visited:1;       /* set true if traversed in call tree */
 473
 474   unsigned seq;             /* sequence number of this pBlock */
 475
 476 } pBlock;
 477
 478 /*************************************************
 479     pFile
 480
 481     The collection of pBlock program snippets are
 482     placed into a linked list that is implemented
 483     in the pFile structure.
 484
 485     The pcode optimizer will parse the pFile.
 486
 487 **************************************************/
 488
 489 typedef struct pFile
 490 {
 491   pBlock *pbHead;     /* A pointer to the first pBlock */
 492   pBlock *pbTail;     /* A pointer to the last pBlock */
 493
 494   pBranch *functions; /* A SLL of functions in this pFile */
 495
 496 } pFile;
 497
 498
 499
 500 /*************************************************
 501   pCodePeep
 502
 503   The pCodePeep object mimics the peep hole optimizer
 504   in the main SDCC src (e.g. SDCCpeeph.c). Essentially
 505   there is a target pCode chain and a replacement
 506   pCode chain. The target chain is compared to the
 507   pCode that is generated by gen.c. If a match is
 508   found then the pCode is replaced by the replacement
 509   pCode chain.
 510 **************************************************/
 511 typedef struct pCodePeep {
 512
 513   pBlock *target;    // code we'd like to optimize
 514   pBlock *replace;   // and this is what we'll optimize it with.
 515
 516   int     nvars;       // Number of wildcard registers in target.
 517   char  **vars;        // array of pointers to them
 518   int     nops;             // Number of wildcard operands in target.
 519   pCodeOp **wildpCodeOps;   // array of pointers to the pCodeOp's.
 520
 521   int     nwildpCodes; // Number of wildcard pCodes in target/replace
 522   pCode **wildpCodes;  // array of pointers to the pCode's.
 523
 524
 525   /* (Note: a wildcard register is a place holder. Any register
 526    * can be replaced by the wildcard when the pcode is being
 527    * compared to the target. */
 528
 529   /* Post Conditions. A post condition is a condition that
 530    * must be either true or false before the peep rule is
 531    * accepted. For example, a certain rule may be accepted
 532    * if and only if the Z-bit is not used as an input to
 533    * the subsequent instructions in a pCode chain.
 534    */
 535   unsigned int postFalseCond;
 536   unsigned int postTrueCond;
 537
 538 } pCodePeep;
 539
 540 typedef struct pCodeOpWild
 541 {
 542   pCodeOp pcop;
 543   //PIC_OPTYPE subtype;      Wild get's expanded to this by the optimizer
 544   pCodePeep *pcp;         // pointer to the parent peep block
 545   int id;                 /* index into an array of char *'s that will match
 546                            * the wild card. The array is in *pcp. */
 547   pCodeOp *subtype;       /* Pointer to the Operand type into which this wild
 548                            * card will be expanded */
 549   pCodeOp *matched;       /* When a wild matches, we'll store a pointer to the
 550                            * opcode we matched */
 551
 552 } pCodeOpWild;
 553
 554 /*************************************************
 555     pCode Macros
 556
 557 **************************************************/
 558 #define PCODE(x)  ((pCode *)(x))
 559 #define PCI(x)    ((pCodeInstruction *)(x))
 560 #define PCL(x)    ((pCodeLabel *)(x))
 561 #define PCF(x)    ((pCodeFunction *)(x))
 562 #define PCW(x)    ((pCodeWild *)(x))
 563
 564 #define PCOP(x)   ((pCodeOp *)(x))
 565 #define PCOB(x)   ((pCodeOpBit *)(x))
 566 #define PCOL(x)   ((pCodeOpLit *)(x))
 567 #define PCOLAB(x) ((pCodeOpLabel *)(x))
 568 #define PCOR(x)   ((pCodeOpReg *)(x))
 569 #define PCORB(x)  ((pCodeOpRegBit *)(x))
 570 #define PCOW(x)   ((pCodeOpWild *)(x))
 571
 572 #define PBR(x)    ((pBranch *)(x))
 573
 574 /*-----------------------------------------------------------------*
 575  * pCode functions.
 576  *-----------------------------------------------------------------*/
 577
 578 pCode *newpCode (PIC_OPCODE op, pCodeOp *pcop); // Create a new pCode given an operand
 579 pCode *newpCodeCharP(char *cP);              // Create a new pCode given a char *
 580 pCode *newpCodeFunction(char *g, char *f);   // Create a new function
 581 pCode *newpCodeLabel(int key);               // Create a new label given a key
 582 pCode *newpCodeLabelStr(char *str);          // Create a new label given a string
 583 pBlock *newpCodeChain(memmap *cm,char c, pCode *pc); // Create a new pBlock
 584 void printpBlock(FILE *of, pBlock *pb);      // Write a pBlock to a file
 585 void printpCode(FILE *of, pCode *pc);        // Write a pCode to a file
 586 void addpCode2pBlock(pBlock *pb, pCode *pc); // Add a pCode to a pBlock
 587 void addpBlock(pBlock *pb);                  // Add a pBlock to a pFile
 588 void copypCode(FILE *of, char dbName);       // Write all pBlocks with dbName to *of
 589 void movepBlock2Head(char dbName);           // move pBlocks around
 590 void AnalyzepCode(char dbName);
 591 void OptimizepCode(char dbName);
 592 void printCallTree(FILE *of);
 593 void pCodePeepInit(void);
 594
 595 pCodeOp *newpCodeOpLabel(int key);
 596 pCodeOp *newpCodeOpLit(int lit);
 597 pCodeOp *newpCodeOpBit(char *name, int bit,int inBitSpace);
 598 pCodeOp *newpCodeOp(char *name, PIC_OPTYPE p);
 599 extern void pcode_test(void);
 600
 601 /*-----------------------------------------------------------------*
 602  * pCode objects.
 603  *-----------------------------------------------------------------*/
 604
 605 extern pCodeOpReg pc_status;
 606 extern pCodeOpReg pc_indf;
 607 extern pCodeOpReg pc_fsr;
 608 extern pCodeOpReg pc_pcl;
 609 extern pCodeOpReg pc_pclath;
 610 extern pCodeOpReg pc_kzero;
 611
 612
 613 ////////////////////   DELETE THIS ///////////////////
 614 /*-----------------------------------------------------------------*/
 615 /* Allocation macros that replace those in SDCCalloc.h             */
 616 /*   Why? I dunno. I ran across a bug with those macros that       */
 617 /*   I couldn't fix, but I could work around...                    */
 618 /*-----------------------------------------------------------------*/
 619 # define GC_malloc(x) calloc((x), 1)
 620
 621 #define  _ALLOC(x,sz) if (!(x = calloc((sz),1) ))      \
 622          {                                          \
 623             werror(E_OUT_OF_MEM,__FILE__,(long) sz);\
 624             exit (1);                               \
 625          }
 626
 627 #define _ALLOC_ATOMIC(x,y) if (!((x) = malloc(y)))   \
 628          {                                               \
 629             werror(E_OUT_OF_MEM,__FILE__,(long) y);     \
 630             exit (1);                                    \
 631          }
 632
 633 #endif // __PCODE_H__