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