1 /*-------------------------------------------------------------------------
3 pcode.h - post code generation
4 Written By - Scott Dattalo scott@dattalo.com
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
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.
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.
20 -------------------------------------------------------------------------*/
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:
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:
50 movf t1,w ; Can't remove this movf
56 movf t1,w ; This movf can be removed
57 xorwf t2,w ; since xorwf will over write Z
67 /***********************************************************************
68 * PIC status bits - this will move into device dependent headers
69 ***********************************************************************/
74 /***********************************************************************
76 ***********************************************************************/
82 /***********************************************************************
84 * PIC_OPTYPE - Operand types that are specific to the PIC architecture
86 * If a PIC assembly instruction has an operand then here is where we
87 * associate a type to it. For example,
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.
95 ***********************************************************************/
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)
116 PO_WILD // Wild card operand in peep optimizer
120 /*************************************************
123 * The "conditions" are bit-mapped flags that describe
124 * input and/or output conditions that are affected by
125 * the instructions. For example:
129 * This instruction depends upon 'SOME_REG'. Consequently
130 * it has the input condition PCC_REGISTER set to true.
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
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 *************************************************/
144 #define PCC_REGISTER (1<<0)
147 #define PCC_DC (1<<3)
150 /***********************************************************************
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.
157 ***********************************************************************/
161 POC_WILD=-1, /* Wild card - used in the pCode peep hole optimizer
162 * to represent ANY pic opcode */
206 /***********************************************************************
207 * PC_TYPE - pCode Types
208 ***********************************************************************/
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
219 /************************************************/
220 /*************** Structures ********************/
221 /************************************************/
224 /*************************************************
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 *************************************************/
240 typedef struct pBranch
242 struct pCode *pc; // Next pCode in a branch
243 struct pBranch *next; /* If more than one branch
244 * the next one is here */
248 /*************************************************
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
258 'some_register' will be stored/referenced in a pCodeOp
260 *************************************************/
262 typedef struct pCodeOp
269 typedef struct pCodeOpBit
273 unsigned int inBitSpace: 1; /* True if in bit space, else
274 just a bit of a register */
277 typedef struct pCodeOpLit
283 typedef struct pCodeOpLabel
289 typedef struct pCodeOpReg
291 pCodeOp pcop; // Can be either GPR or SFR
292 int rIdx; // Index into the register table
299 /*************************************************
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.
306 **************************************************/
312 struct pCode *prev; // The pCode objects are linked together
313 struct pCode *next; // in doubly linked lists.
315 int seq; // sequence number
317 pBranch *from; // pCodes that execute before this one
318 pBranch *to; // pCodes that execute after
319 pBranch *label; // pCode instructions that have labels
321 struct pBlock *pb; // The pBlock that contains this pCode.
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);
335 /*************************************************
337 **************************************************/
339 typedef struct pCodeComment
348 /*************************************************
351 Here we describe all the facets of a PIC instruction
352 (expansion for the 18cxxx is also provided).
354 **************************************************/
356 typedef struct pCodeInstruction
361 PIC_OPCODE op; // The opcode of the instruction.
363 char *mnemonic; // Pointer to mnemonic string
365 pCodeOp *pcop; // Operand
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;
371 unsigned int inCond; // Input conditions for this instruction
372 unsigned int outCond; // Output conditions for this instruction
377 /*************************************************
379 **************************************************/
381 typedef struct pCodeLabel
391 /*************************************************
393 **************************************************/
395 typedef struct pCodeFunction
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
409 /*************************************************
411 **************************************************/
413 typedef struct pCodeWild
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 */
423 pCodeOp *operand; // Optional operand
424 pCodeOp *label; // Optional label
428 /*************************************************
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
437 **************************************************/
439 typedef struct pBlock
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 */
446 struct pBlock *next; /* The pBlocks will form a doubly linked list */
449 set *function_entries; /* dll of functions in this pblock */
454 unsigned visited:1; /* set true if traversed in call tree */
456 unsigned seq; /* sequence number of this pBlock */
460 /*************************************************
463 The collection of pBlock program snippets are
464 placed into a linked list that is implemented
465 in the pFile structure.
467 The pcode optimizer will parse the pFile.
469 **************************************************/
473 pBlock *pbHead; /* A pointer to the first pBlock */
474 pBlock *pbTail; /* A pointer to the last pBlock */
476 pBranch *functions; /* A SLL of functions in this pFile */
482 /*************************************************
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
492 **************************************************/
493 typedef struct pCodePeep {
495 pBlock *target; // code we'd like to optimize
496 pBlock *replace; // and this is what we'll optimize it with.
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.
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. */
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.
514 unsigned int postFalseCond;
515 unsigned int postTrueCond;
519 typedef struct pCodeOpWild
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 */
533 /*************************************************
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))
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))
550 #define PBR(x) ((pBranch *)(x))
552 /*-----------------------------------------------------------------*
554 *-----------------------------------------------------------------*/
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);
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);
579 /*-----------------------------------------------------------------*
581 *-----------------------------------------------------------------*/
583 extern pCodeOp pc_status;
584 extern pCodeOp pc_indf;
585 extern pCodeOp pc_fsr;
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)
596 #define _ALLOC(x,sz) if (!(x = calloc((sz),1) )) \
598 werror(E_OUT_OF_MEM,__FILE__,(long) sz);\
602 #define _ALLOC_ATOMIC(x,y) if (!((x) = malloc(y))) \
604 werror(E_OUT_OF_MEM,__FILE__,(long) y); \
608 #endif // __PCODE_H__