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 -------------------------------------------------------------------------*/
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:
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:
51 movf t1,w ; Can't remove this movf
57 movf t1,w ; This movf can be removed
58 xorwf t2,w ; since xorwf will over write Z
68 /***********************************************************************
69 * PIC status bits - this will move into device dependent headers
70 ***********************************************************************/
75 /***********************************************************************
77 ***********************************************************************/
83 /***********************************************************************
85 * PIC_OPTYPE - Operand types that are specific to the PIC architecture
87 * If a PIC assembly instruction has an operand then here is where we
88 * associate a type to it. For example,
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.
96 ***********************************************************************/
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)
117 PO_WILD // Wild card operand in peep optimizer
121 /*************************************************
124 * The "conditions" are bit-mapped flags that describe
125 * input and/or output conditions that are affected by
126 * the instructions. For example:
130 * This instruction depends upon 'SOME_REG'. Consequently
131 * it has the input condition PCC_REGISTER set to true.
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
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 *************************************************/
145 #define PCC_REGISTER (1<<0)
148 #define PCC_DC (1<<3)
150 #define PCC_EXAMINE_PCOP (1<<5)
152 /***********************************************************************
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.
159 ***********************************************************************/
163 POC_WILD=-1, /* Wild card - used in the pCode peep hole optimizer
164 * to represent ANY pic opcode */
208 /***********************************************************************
209 * PC_TYPE - pCode Types
210 ***********************************************************************/
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
221 /************************************************/
222 /*************** Structures ********************/
223 /************************************************/
226 /*************************************************
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 *************************************************/
242 typedef struct pBranch
244 struct pCode *pc; // Next pCode in a branch
245 struct pBranch *next; /* If more than one branch
246 * the next one is here */
250 /*************************************************
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
260 'some_register' will be stored/referenced in a pCodeOp
262 *************************************************/
264 typedef struct pCodeOp
271 typedef struct pCodeOpBit
275 unsigned int inBitSpace: 1; /* True if in bit space, else
276 just a bit of a register */
279 typedef struct pCodeOpLit
285 typedef struct pCodeOpLabel
291 typedef struct pCodeOpReg
293 pCodeOp pcop; // Can be either GPR or SFR
294 int rIdx; // Index into the register table
301 /*************************************************
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.
308 **************************************************/
314 struct pCode *prev; // The pCode objects are linked together
315 struct pCode *next; // in doubly linked lists.
317 int seq; // sequence number
319 pBranch *from; // pCodes that execute before this one
320 pBranch *to; // pCodes that execute after
321 pBranch *label; // pCode instructions that have labels
323 struct pBlock *pb; // The pBlock that contains this pCode.
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);
337 /*************************************************
339 **************************************************/
341 typedef struct pCodeComment
350 /*************************************************
353 Here we describe all the facets of a PIC instruction
354 (expansion for the 18cxxx is also provided).
356 **************************************************/
358 typedef struct pCodeInstruction
363 PIC_OPCODE op; // The opcode of the instruction.
365 char const * const mnemonic; // Pointer to mnemonic string
367 pCodeOp *pcop; // Operand
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;
373 unsigned int inCond; // Input conditions for this instruction
374 unsigned int outCond; // Output conditions for this instruction
379 /*************************************************
381 **************************************************/
383 typedef struct pCodeLabel
393 /*************************************************
395 **************************************************/
397 typedef struct pCodeFunction
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
411 /*************************************************
413 **************************************************/
415 typedef struct pCodeWild
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 */
425 pCodeOp *operand; // Optional operand
426 pCodeOp *label; // Optional label
430 /*************************************************
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
439 **************************************************/
441 typedef struct pBlock
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 */
448 struct pBlock *next; /* The pBlocks will form a doubly linked list */
451 set *function_entries; /* dll of functions in this pblock */
456 unsigned visited:1; /* set true if traversed in call tree */
458 unsigned seq; /* sequence number of this pBlock */
462 /*************************************************
465 The collection of pBlock program snippets are
466 placed into a linked list that is implemented
467 in the pFile structure.
469 The pcode optimizer will parse the pFile.
471 **************************************************/
475 pBlock *pbHead; /* A pointer to the first pBlock */
476 pBlock *pbTail; /* A pointer to the last pBlock */
478 pBranch *functions; /* A SLL of functions in this pFile */
484 /*************************************************
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
494 **************************************************/
495 typedef struct pCodePeep {
497 pBlock *target; // code we'd like to optimize
498 pBlock *replace; // and this is what we'll optimize it with.
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.
505 int nwildpCodes; // Number of wildcard pCodes in target/replace
506 pCode **wildpCodes; // array of pointers to the pCode's.
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. */
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.
519 unsigned int postFalseCond;
520 unsigned int postTrueCond;
524 typedef struct pCodeOpWild
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 */
538 /*************************************************
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))
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))
555 #define PBR(x) ((pBranch *)(x))
557 /*-----------------------------------------------------------------*
559 *-----------------------------------------------------------------*/
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);
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);
584 /*-----------------------------------------------------------------*
586 *-----------------------------------------------------------------*/
588 extern pCodeOpReg pc_status;
589 extern pCodeOpReg pc_indf;
590 extern pCodeOpReg pc_fsr;
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)
601 #define _ALLOC(x,sz) if (!(x = calloc((sz),1) )) \
603 werror(E_OUT_OF_MEM,__FILE__,(long) sz);\
607 #define _ALLOC_ATOMIC(x,y) if (!((x) = malloc(y))) \
609 werror(E_OUT_OF_MEM,__FILE__,(long) y); \
613 #endif // __PCODE_H__