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 -------------------------------------------------------------------------*/
25 The post code generation is an assembler optimizer. The assembly code
26 produced by all of the previous steps is fully functional. This step
27 will attempt to analyze the flow of the assembly code and agressively
28 optimize it. The peep hole optimizer attempts to do the same thing.
29 As you may recall, the peep hole optimizer replaces blocks of assembly
30 with more optimal blocks (e.g. removing redundant register loads).
31 However, the peep hole optimizer has to be somewhat conservative since
32 an assembly program has implicit state information that's unavailable
33 when only a few instructions are examined.
34 Consider this example:
40 The movf seems redundant since we know that the W register already
41 contains the same value of t1. So a peep hole optimizer is tempted to
42 remove the "movf". However, this is dangerous since the movf affects
43 the flags in the status register (specifically the Z flag) and subsequent
44 code may depend upon this. Look at these two examples:
48 movf t1,w ; Can't remove this movf
54 movf t1,w ; This movf can be removed
55 xorwf t2,w ; since xorwf will over write Z
65 /***********************************************************************
66 * PIC status bits - this will move into device dependent headers
67 ***********************************************************************/
72 /***********************************************************************
74 ***********************************************************************/
80 /***********************************************************************
82 * PIC_OPTYPE - Operand types that are specific to the PIC architecture
84 * If a PIC assembly instruction has an operand then here is where we
85 * associate a type to it. For example,
89 * The movf has two operands: 'reg' and the W register. 'reg' is some
90 * arbitrary general purpose register, hence it has the type PO_GPR_REGISTER.
91 * The W register, which is the PIC's accumulator, has the type PO_W.
93 ***********************************************************************/
99 PO_NONE=0, // No operand e.g. NOP
100 PO_W, // The 'W' register
101 PO_STATUS, // The 'STATUS' register
102 PO_FSR, // The "file select register" (in 18c it's one of three)
103 PO_INDF, // The Indirect register
104 PO_GPR_REGISTER, // A general purpose register
105 PO_SFR_REGISTER, // A special function register (e.g. PORTA)
106 PO_LITERAL, // A constant
107 PO_IMMEDIATE, // (8051 legacy)
108 PO_DIR, // Direct memory (8051 legacy)
109 PO_CRY, // bit memory (8051 legacy)
110 PO_BIT, // bit operand.
111 PO_STR, // (8051 legacy)
113 PO_WILD // Wild card operand in peep optimizer
117 /*************************************************
120 * The "conditions" are bit-mapped flags that describe
121 * input and/or output conditions that are affected by
122 * the instructions. For example:
126 * This instruction depends upon 'SOME_REG'. Consequently
127 * it has the input condition PCC_REGISTER set to true.
129 * In addition, this instruction affects the Z bit in the
130 * status register and affects W. Thus the output conditions
131 * are the logical or:
132 * PCC_ZERO_BIT | PCC_W
134 * The conditions are intialized when the pCode for an
135 * instruction is created. They're subsequently used
136 * by the pCode optimizer determine state information
137 * in the program flow.
138 *************************************************/
141 #define PCC_REGISTER (1<<0)
144 #define PCC_DC (1<<3)
147 /***********************************************************************
151 * This is not a list of the PIC's opcodes per se, but instead
152 * an enumeration of all of the different types of pic opcodes.
154 ***********************************************************************/
158 POC_WILD=-1, /* Wild card - used in the pCode peep hole optimizer
159 * to represent ANY pic opcode */
203 /***********************************************************************
204 * PC_TYPE - pCode Types
205 ***********************************************************************/
209 PC_COMMENT=0, // pCode is a comment
210 PC_OPCODE, // PORT dependent opcode
211 PC_LABEL, // assembly label
212 PC_FUNCTION, // Function start or end
213 PC_WILD // wildcard - an opcode place holder
216 /************************************************/
217 /*************** Structures ********************/
218 /************************************************/
221 /*************************************************
224 The first step in optimizing pCode is determining
225 the program flow. This information is stored in
226 single-linked lists in the for of 'from' and 'to'
227 objects with in a pcode. For example, most instructions
228 don't involve any branching. So their from branch
229 points to the pCode immediately preceding them and
230 their 'to' branch points to the pcode immediately
231 following them. A skip instruction is an example of
232 a pcode that has multiple (in this case two) elements
233 in the 'to' branch. A 'label' pcode is an where there
234 may be multiple 'from' branches.
235 *************************************************/
237 typedef struct pBranch
239 struct pCode *pc; // Next pCode in a branch
240 struct pBranch *next; /* If more than one branch
241 * the next one is here */
245 /*************************************************
248 pCode Operand structure.
249 For those assembly instructions that have arguments,
250 the pCode will have a pCodeOp in which the argument
251 can be stored. For example
255 'some_register' will be stored/referenced in a pCodeOp
257 *************************************************/
259 typedef struct pCodeOp
266 typedef struct pCodeOpBit
270 unsigned int inBitSpace: 1; /* True if in bit space, else
271 just a bit of a register */
274 typedef struct pCodeOpLit
280 typedef struct pCodeOpLabel
288 /*************************************************
291 Here is the basic build block of a PIC instruction.
292 Each pic instruction will get allocated a pCode.
293 A linked list of pCodes makes a program.
295 **************************************************/
301 struct pCode *prev; // The pCode objects are linked together
302 struct pCode *next; // in doubly linked lists.
304 pBranch *from; // pCodes that execute before this one
305 pBranch *to; // pCodes that execute after
306 pBranch *label; // pCode instructions that have labels
308 /* "virtual functions"
309 * The pCode structure is like a base class
310 * in C++. The subsequent structures that "inherit"
311 * the pCode structure will initialize these function
312 * pointers to something useful */
313 void (*analyze) (struct pCode *_this);
314 void (*destruct)(struct pCode *_this);
315 void (*print) (FILE *of,struct pCode *_this);
320 /*************************************************
322 **************************************************/
324 typedef struct pCodeComment
333 /*************************************************
336 Here we describe all the facets of a PIC instruction
337 (expansion for the 18cxxx is also provided).
339 **************************************************/
341 typedef struct pCodeInstruction
346 PIC_OPCODE op; // The opcode of the instruction.
348 char *mnemonic; // Pointer to mnemonic string
350 pCodeOp *pcop; // Operand
352 unsigned int num_ops;
353 unsigned int dest: 1; // If destination is W or F, then 1==F
354 unsigned int bit_inst: 1;
356 unsigned int inCond; // Input conditions for this instruction
357 unsigned int outCond; // Output conditions for this instruction
362 /*************************************************
364 **************************************************/
366 typedef struct pCodeLabel
376 /*************************************************
378 **************************************************/
380 typedef struct pCodeFunction
386 char *fname; /* If NULL, then this is the end of
387 a function. Otherwise, it's the
388 start and the name is contained
394 /*************************************************
396 **************************************************/
398 typedef struct pCodeWild
403 int id; /* Index into the wild card array of a peepBlock
404 * - this wild card will get expanded into that pCode
405 * that is stored at this index */
408 pCodeOp *operand; // Optional operand
409 pCodeOp *label; // Optional label
413 /*************************************************
416 Here are PIC program snippets. There's a strong
417 correlation between the eBBlocks and pBlocks.
418 SDCC subdivides a C program into managable chunks.
419 Each chunk becomes a eBBlock and ultimately in the
422 **************************************************/
424 typedef struct pBlock
426 memmap *cmemmap; /* The snippet is from this memmap */
427 pCode *pcHead; /* A pointer to the first pCode in a link list of pCodes */
428 pCode *pcTail; /* A pointer to the last pCode in a link list of pCodes */
430 struct pBlock *next; /* The pBlocks will form a doubly linked list */
435 /*************************************************
438 The collection of pBlock program snippets are
439 placed into a linked list that is implemented
440 in the pFile structure.
442 The pcode optimizer will parse the pFile.
444 **************************************************/
448 pBlock *pbHead; /* A pointer to the first pBlock */
449 pBlock *pbTail; /* A pointer to the last pBlock */
451 pBranch *functions; /* A SLL of functions in this pFile */
457 /*************************************************
460 The pCodePeep object mimics the peep hole optimizer
461 in the main SDCC src (e.g. SDCCpeeph.c). Essentially
462 there is a target pCode chain and a replacement
463 pCode chain. The target chain is compared to the
464 pCode that is generated by gen.c. If a match is
465 found then the pCode is replaced by the replacement
467 **************************************************/
468 typedef struct pCodePeep {
470 pBlock *target; // code we'd like to optimize
471 pBlock *replace; // and this is what we'll optimize it with.
473 int nvars; // Number of wildcard registers in target.
474 char **vars; // array of pointers to them
475 int nwildpCodes; // Number of wildcard pCodes in target/replace
476 pCode **wildpCodes; // array of pointers to the pCodeOp's.
479 /* (Note: a wildcard register is a place holder. Any register
480 * can be replaced by the wildcard when the pcode is being
481 * compared to the target. */
483 /* Post Conditions. A post condition is a condition that
484 * must be either true or false before the peep rule is
485 * accepted. For example, a certain rule may be accepted
486 * if and only if the Z-bit is not used as an input to
487 * the subsequent instructions in a pCode chain.
489 unsigned int postFalseCond;
490 unsigned int postTrueCond;
494 typedef struct pCodeOpWild
497 //PIC_OPTYPE subtype; Wild get's expanded to this by the optimizer
498 pCodePeep *pcp; // pointer to the parent peep block
499 int id; /* index into an array of char *'s that will match
500 * the wild card. The array is in *pcp. */
501 pCodeOp *subtype; /* Pointer to the Operand type into which this wild
502 * card will be expanded */
505 /*************************************************
508 **************************************************/
509 #define PCODE(x) ((pCode *)(x))
510 #define PCI(x) ((pCodeInstruction *)(x))
511 #define PCL(x) ((pCodeLabel *)(x))
512 #define PCF(x) ((pCodeFunction *)(x))
513 #define PCW(x) ((pCodeWild *)(x))
515 #define PCOP(x) ((pCodeOp *)(x))
516 #define PCOB(x) ((pCodeOpBit *)(x))
517 #define PCOL(x) ((pCodeOpLit *)(x))
518 #define PCOLAB(x) ((pCodeOpLabel *)(x))
519 #define PCOW(x) ((pCodeOpWild *)(x))
521 #define PBR(x) ((pBranch *)(x))
523 /*-----------------------------------------------------------------*
525 *-----------------------------------------------------------------*/
527 pCode *newpCode (PIC_OPCODE op, pCodeOp *pcop); // Create a new pCode given an operand
528 pCode *newpCodeCharP(char *cP); // Create a new pCode given a char *
529 pCode *newpCodeFunction(char *g, char *f); // Create a new function
530 pCode *newpCodeLabel(int key); // Create a new label
531 pBlock *newpCodeChain(memmap *cm,pCode *pc); // Create a new pBlock
532 void printpBlock(FILE *of, pBlock *pb); // Write a pBlock to a file
533 void printpCode(FILE *of, pCode *pc); // Write a pCode to a file
534 void addpCode2pBlock(pBlock *pb, pCode *pc); // Add a pCode to a pBlock
535 void addpBlock(pBlock *pb); // Add a pBlock to a pFile
536 void copypCode(FILE *of, char dbName); // Write all pBlocks with dbName to *of
537 void AnalyzepCode(char dbName);
538 void OptimizepCode(char dbName);
539 void printCallTree(FILE *of);
540 void pCodePeepInit(void);
542 pCodeOp *newpCodeOpLabel(int key);
543 pCodeOp *newpCodeOpLit(int lit);
544 pCodeOp *newpCodeOpBit(char *name, int bit);
545 pCodeOp *newpCodeOp(char *name, PIC_OPTYPE p);
546 extern void pcode_test(void);
548 /*-----------------------------------------------------------------*
550 *-----------------------------------------------------------------*/
552 extern pCodeOp pc_status;
553 extern pCodeOp pc_indf;
554 extern pCodeOp pc_fsr;
557 //////////////////// DELETE THIS ///////////////////
558 /*-----------------------------------------------------------------*/
559 /* Allocation macros that replace those in SDCCalloc.h */
560 /* Why? I dunno. I ran across a bug with those macros that */
561 /* I couldn't fix, but I could work around... */
562 /*-----------------------------------------------------------------*/
563 # define GC_malloc(x) calloc((x), 1)
565 #define _ALLOC(x,sz) if (!(x = calloc((sz),1) )) \
567 werror(E_OUT_OF_MEM,__FILE__,(long) sz);\
571 #define _ALLOC_ATOMIC(x,y) if (!((x) = malloc(y))) \
573 werror(E_OUT_OF_MEM,__FILE__,(long) y); \
577 #endif // __PCODE_H__