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