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