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