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)
151 /***********************************************************************
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.
158 ***********************************************************************/
162 POC_WILD=-1, /* Wild card - used in the pCode peep hole optimizer
163 * to represent ANY pic opcode */
207 /***********************************************************************
208 * PC_TYPE - pCode Types
209 ***********************************************************************/
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
220 /************************************************/
221 /*************** Structures ********************/
222 /************************************************/
225 /*************************************************
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 *************************************************/
241 typedef struct pBranch
243 struct pCode *pc; // Next pCode in a branch
244 struct pBranch *next; /* If more than one branch
245 * the next one is here */
249 /*************************************************
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
259 'some_register' will be stored/referenced in a pCodeOp
261 *************************************************/
263 typedef struct pCodeOp
270 typedef struct pCodeOpBit
274 unsigned int inBitSpace: 1; /* True if in bit space, else
275 just a bit of a register */
278 typedef struct pCodeOpLit
284 typedef struct pCodeOpLabel
290 typedef struct pCodeOpReg
292 pCodeOp pcop; // Can be either GPR or SFR
293 int rIdx; // Index into the register table
300 /*************************************************
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.
307 **************************************************/
313 struct pCode *prev; // The pCode objects are linked together
314 struct pCode *next; // in doubly linked lists.
316 int seq; // sequence number
318 pBranch *from; // pCodes that execute before this one
319 pBranch *to; // pCodes that execute after
320 pBranch *label; // pCode instructions that have labels
322 struct pBlock *pb; // The pBlock that contains this pCode.
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);
336 /*************************************************
338 **************************************************/
340 typedef struct pCodeComment
349 /*************************************************
352 Here we describe all the facets of a PIC instruction
353 (expansion for the 18cxxx is also provided).
355 **************************************************/
357 typedef struct pCodeInstruction
362 PIC_OPCODE op; // The opcode of the instruction.
364 char *mnemonic; // Pointer to mnemonic string
366 pCodeOp *pcop; // Operand
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;
372 unsigned int inCond; // Input conditions for this instruction
373 unsigned int outCond; // Output conditions for this instruction
378 /*************************************************
380 **************************************************/
382 typedef struct pCodeLabel
392 /*************************************************
394 **************************************************/
396 typedef struct pCodeFunction
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
410 /*************************************************
412 **************************************************/
414 typedef struct pCodeWild
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 */
424 pCodeOp *operand; // Optional operand
425 pCodeOp *label; // Optional label
429 /*************************************************
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
438 **************************************************/
440 typedef struct pBlock
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 */
447 struct pBlock *next; /* The pBlocks will form a doubly linked list */
450 set *function_entries; /* dll of functions in this pblock */
455 unsigned visited:1; /* set true if traversed in call tree */
457 unsigned seq; /* sequence number of this pBlock */
461 /*************************************************
464 The collection of pBlock program snippets are
465 placed into a linked list that is implemented
466 in the pFile structure.
468 The pcode optimizer will parse the pFile.
470 **************************************************/
474 pBlock *pbHead; /* A pointer to the first pBlock */
475 pBlock *pbTail; /* A pointer to the last pBlock */
477 pBranch *functions; /* A SLL of functions in this pFile */
483 /*************************************************
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
493 **************************************************/
494 typedef struct pCodePeep {
496 pBlock *target; // code we'd like to optimize
497 pBlock *replace; // and this is what we'll optimize it with.
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.
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. */
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.
515 unsigned int postFalseCond;
516 unsigned int postTrueCond;
520 typedef struct pCodeOpWild
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 */
534 /*************************************************
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))
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))
551 #define PBR(x) ((pBranch *)(x))
553 /*-----------------------------------------------------------------*
555 *-----------------------------------------------------------------*/
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);
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);
580 /*-----------------------------------------------------------------*
582 *-----------------------------------------------------------------*/
584 extern pCodeOpReg pc_status;
585 extern pCodeOpReg pc_indf;
586 extern pCodeOpReg pc_fsr;
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)
597 #define _ALLOC(x,sz) if (!(x = calloc((sz),1) )) \
599 werror(E_OUT_OF_MEM,__FILE__,(long) sz);\
603 #define _ALLOC_ATOMIC(x,y) if (!((x) = malloc(y))) \
605 werror(E_OUT_OF_MEM,__FILE__,(long) y); \
609 #endif // __PCODE_H__