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 /***********************************************************************
71 * The DFPRINTF macro will call fprintf if PCODE_DEBUG is defined.
72 * The macro is used like:
74 * DPRINTF(("%s #%d\n","test", 1));
76 * The double parenthesis (()) are necessary
78 ***********************************************************************/
82 #define DFPRINTF(args) (fprintf args)
84 #define DFPRINTF(args) ;
88 /***********************************************************************
89 * PIC status bits - this will move into device dependent headers
90 ***********************************************************************/
94 #define PIC_RP0_BIT 5 /* Register Bank select bits RP1:0 : */
95 #define PIC_RP1_BIT 6 /* 00 - bank 0, 01 - bank 1, 10 - bank 2, 11 - bank 3 */
96 #define PIC_IRP_BIT 7 /* Indirect register page select */
98 /***********************************************************************
99 * PIC INTCON bits - this will move into device dependent headers
100 ***********************************************************************/
101 #define PIC_RBIF_BIT 0 /* Port B level has changed flag */
102 #define PIC_INTF_BIT 1 /* Port B bit 0 interrupt on edge flag */
103 #define PIC_T0IF_BIT 2 /* TMR0 has overflowed flag */
104 #define PIC_RBIE_BIT 3 /* Port B level has changed - Interrupt Enable */
105 #define PIC_INTE_BIT 4 /* Port B bit 0 interrupt on edge - Int Enable */
106 #define PIC_T0IE_BIT 5 /* TMR0 overflow Interrupt Enable */
107 #define PIC_PIE_BIT 6 /* Peripheral Interrupt Enable */
108 #define PIC_GIE_BIT 7 /* Global Interrupt Enable */
110 /***********************************************************************
112 ***********************************************************************/
118 /***********************************************************************
120 * PIC_OPTYPE - Operand types that are specific to the PIC architecture
122 * If a PIC assembly instruction has an operand then here is where we
123 * associate a type to it. For example,
127 * The movf has two operands: 'reg' and the W register. 'reg' is some
128 * arbitrary general purpose register, hence it has the type PO_GPR_REGISTER.
129 * The W register, which is the PIC's accumulator, has the type PO_W.
131 ***********************************************************************/
137 PO_NONE=0, // No operand e.g. NOP
138 PO_W, // The 'W' register
139 PO_STATUS, // The 'STATUS' register
140 PO_FSR, // The "file select register" (in 18c it's one of three)
141 PO_INDF, // The Indirect register
142 PO_INTCON, // Interrupt Control register
143 PO_GPR_REGISTER, // A general purpose register
144 PO_GPR_BIT, // A bit of a general purpose register
145 PO_GPR_TEMP, // A general purpose temporary register
146 PO_SFR_REGISTER, // A special function register (e.g. PORTA)
147 PO_PCL, // Program counter Low register
148 PO_PCLATH, // Program counter Latch high register
149 PO_LITERAL, // A constant
150 PO_IMMEDIATE, // (8051 legacy)
151 PO_DIR, // Direct memory (8051 legacy)
152 PO_CRY, // bit memory (8051 legacy)
153 PO_BIT, // bit operand.
154 PO_STR, // (8051 legacy)
156 PO_WILD // Wild card operand in peep optimizer
160 /***********************************************************************
164 * This is not a list of the PIC's opcodes per se, but instead
165 * an enumeration of all of the different types of pic opcodes.
167 ***********************************************************************/
171 POC_WILD=-1, /* Wild card - used in the pCode peep hole optimizer
172 * to represent ANY pic opcode */
224 /***********************************************************************
225 * PC_TYPE - pCode Types
226 ***********************************************************************/
230 PC_COMMENT=0, /* pCode is a comment */
231 PC_OPCODE, /* PORT dependent opcode */
232 PC_LABEL, /* assembly label */
233 PC_FLOW, /* flow analysis */
234 PC_FUNCTION, /* Function start or end */
235 PC_WILD /* wildcard - an opcode place holder used
236 * in the pCode peep hole optimizer */
239 /************************************************/
240 /*************** Structures ********************/
241 /************************************************/
244 /*************************************************
247 The first step in optimizing pCode is determining
248 the program flow. This information is stored in
249 single-linked lists in the for of 'from' and 'to'
250 objects with in a pcode. For example, most instructions
251 don't involve any branching. So their from branch
252 points to the pCode immediately preceding them and
253 their 'to' branch points to the pcode immediately
254 following them. A skip instruction is an example of
255 a pcode that has multiple (in this case two) elements
256 in the 'to' branch. A 'label' pcode is an where there
257 may be multiple 'from' branches.
258 *************************************************/
260 typedef struct pBranch
262 struct pCode *pc; // Next pCode in a branch
263 struct pBranch *next; /* If more than one branch
264 * the next one is here */
268 /*************************************************
271 pCode Operand structure.
272 For those assembly instructions that have arguments,
273 the pCode will have a pCodeOp in which the argument
274 can be stored. For example
278 'some_register' will be stored/referenced in a pCodeOp
280 *************************************************/
282 typedef struct pCodeOp
289 typedef struct pCodeOpBit
293 unsigned int inBitSpace: 1; /* True if in bit space, else
294 just a bit of a register */
297 typedef struct pCodeOpLit
303 typedef struct pCodeOpImmd
309 typedef struct pCodeOpLabel
315 typedef struct pCodeOpReg
317 pCodeOp pcop; // Can be either GPR or SFR
318 int rIdx; // Index into the register table
320 int instance; // byte # of Multi-byte registers
324 typedef struct pCodeOpRegBit
326 pCodeOpReg pcor; // The Register containing this bit
327 int bit; // 0-7 bit number.
328 PIC_OPTYPE subtype; // The type of this register.
329 unsigned int inBitSpace: 1; /* True if in bit space, else
330 just a bit of a register */
334 /*************************************************
337 Here is the basic build block of a PIC instruction.
338 Each pic instruction will get allocated a pCode.
339 A linked list of pCodes makes a program.
341 **************************************************/
347 struct pCode *prev; // The pCode objects are linked together
348 struct pCode *next; // in doubly linked lists.
350 int seq; // sequence number
352 struct pBlock *pb; // The pBlock that contains this pCode.
354 /* "virtual functions"
355 * The pCode structure is like a base class
356 * in C++. The subsequent structures that "inherit"
357 * the pCode structure will initialize these function
358 * pointers to something useful */
359 // void (*analyze) (struct pCode *_this);
360 void (*destruct)(struct pCode *_this);
361 void (*print) (FILE *of,struct pCode *_this);
366 /*************************************************
368 **************************************************/
370 typedef struct pCodeComment
379 /*************************************************
382 The Flow object is used as marker to separate
383 the assembly code into contiguous chunks. In other
384 words, everytime an instruction cause or potentially
385 causes a branch, a Flow object will be inserted into
386 the pCode chain to mark the beginning of the next
388 **************************************************/
390 typedef struct pCodeFlow
395 pCode *end; /* Last pCode in this flow. Note that
396 the first pCode is pc.next */
398 set **uses; /* map the pCode instruction inCond and outCond conditions
399 * in this array of set's. The reason we allocate an
400 * array of pointers instead of declaring each type of
401 * usage is because there are port dependent usage definitions */
402 int nuses; /* number of uses sets */
404 set *from; /* flow blocks that can send control to this flow block */
405 set *to; /* flow blocks to which this one can send control */
407 int inCond; /* Input conditions - stuff assumed defined at entry */
408 int outCond; /* Output conditions - stuff modified by flow block */
412 /*************************************************
415 Here we describe all the facets of a PIC instruction
416 (expansion for the 18cxxx is also provided).
418 **************************************************/
420 typedef struct pCodeInstruction
425 PIC_OPCODE op; // The opcode of the instruction.
427 char const * const mnemonic; // Pointer to mnemonic string
429 pBranch *from; // pCodes that execute before this one
430 pBranch *to; // pCodes that execute after
431 pBranch *label; // pCode instructions that have labels
433 pCodeOp *pcop; /* Operand, if this instruction has one */
435 pCodeFlow *pcflow; /* flow block to which this instruction belongs */
437 unsigned int num_ops; /* Number of operands (0,1,2 for mid range pics) */
438 unsigned int isModReg: 1; /* If destination is W or F, then 1==F */
439 unsigned int isBitInst: 1; /* e.g. BCF */
440 unsigned int isBranch: 1; /* True if this is a branching instruction */
441 unsigned int isSkip: 1; /* True if this is a skip instruction */
443 unsigned int inCond; // Input conditions for this instruction
444 unsigned int outCond; // Output conditions for this instruction
449 /*************************************************
451 **************************************************/
453 typedef struct pCodeLabel
463 /*************************************************
465 **************************************************/
467 typedef struct pCodeFunction
473 char *fname; /* If NULL, then this is the end of
474 a function. Otherwise, it's the
475 start and the name is contained
478 pBranch *from; // pCodes that execute before this one
479 pBranch *to; // pCodes that execute after
480 pBranch *label; // pCode instructions that have labels
485 /*************************************************
487 **************************************************/
489 typedef struct pCodeWild
492 pCodeInstruction pci;
494 int id; /* Index into the wild card array of a peepBlock
495 * - this wild card will get expanded into that pCode
496 * that is stored at this index */
499 pCodeOp *operand; // Optional operand
500 pCodeOp *label; // Optional label
504 /*************************************************
507 Here are PIC program snippets. There's a strong
508 correlation between the eBBlocks and pBlocks.
509 SDCC subdivides a C program into managable chunks.
510 Each chunk becomes a eBBlock and ultimately in the
513 **************************************************/
515 typedef struct pBlock
517 memmap *cmemmap; /* The snippet is from this memmap */
518 char dbName; /* if cmemmap is NULL, then dbName will identify the block */
519 pCode *pcHead; /* A pointer to the first pCode in a link list of pCodes */
520 pCode *pcTail; /* A pointer to the last pCode in a link list of pCodes */
522 struct pBlock *next; /* The pBlocks will form a doubly linked list */
525 set *function_entries; /* dll of functions in this pblock */
530 unsigned visited:1; /* set true if traversed in call tree */
532 unsigned seq; /* sequence number of this pBlock */
536 /*************************************************
539 The collection of pBlock program snippets are
540 placed into a linked list that is implemented
541 in the pFile structure.
543 The pcode optimizer will parse the pFile.
545 **************************************************/
549 pBlock *pbHead; /* A pointer to the first pBlock */
550 pBlock *pbTail; /* A pointer to the last pBlock */
552 pBranch *functions; /* A SLL of functions in this pFile */
558 /*************************************************
561 The pCodePeep object mimics the peep hole optimizer
562 in the main SDCC src (e.g. SDCCpeeph.c). Essentially
563 there is a target pCode chain and a replacement
564 pCode chain. The target chain is compared to the
565 pCode that is generated by gen.c. If a match is
566 found then the pCode is replaced by the replacement
568 **************************************************/
569 typedef struct pCodePeep {
571 pBlock *target; // code we'd like to optimize
572 pBlock *replace; // and this is what we'll optimize it with.
574 int nvars; // Number of wildcard registers in target.
575 char **vars; // array of pointers to them
576 int nops; // Number of wildcard operands in target.
577 pCodeOp **wildpCodeOps; // array of pointers to the pCodeOp's.
579 int nwildpCodes; // Number of wildcard pCodes in target/replace
580 pCode **wildpCodes; // array of pointers to the pCode's.
583 /* (Note: a wildcard register is a place holder. Any register
584 * can be replaced by the wildcard when the pcode is being
585 * compared to the target. */
587 /* Post Conditions. A post condition is a condition that
588 * must be either true or false before the peep rule is
589 * accepted. For example, a certain rule may be accepted
590 * if and only if the Z-bit is not used as an input to
591 * the subsequent instructions in a pCode chain.
593 unsigned int postFalseCond;
594 unsigned int postTrueCond;
598 typedef struct pCodeOpWild
601 //PIC_OPTYPE subtype; Wild get's expanded to this by the optimizer
602 pCodePeep *pcp; // pointer to the parent peep block
603 int id; /* index into an array of char *'s that will match
604 * the wild card. The array is in *pcp. */
605 pCodeOp *subtype; /* Pointer to the Operand type into which this wild
606 * card will be expanded */
607 pCodeOp *matched; /* When a wild matches, we'll store a pointer to the
608 * opcode we matched */
612 /*************************************************
615 **************************************************/
616 #define PCODE(x) ((pCode *)(x))
617 #define PCI(x) ((pCodeInstruction *)(x))
618 #define PCL(x) ((pCodeLabel *)(x))
619 #define PCF(x) ((pCodeFunction *)(x))
620 #define PCFL(x) ((pCodeFlow *)(x))
621 #define PCW(x) ((pCodeWild *)(x))
623 #define PCOP(x) ((pCodeOp *)(x))
624 //#define PCOB(x) ((pCodeOpBit *)(x))
625 #define PCOL(x) ((pCodeOpLit *)(x))
626 #define PCOI(x) ((pCodeOpImmd *)(x))
627 #define PCOLAB(x) ((pCodeOpLabel *)(x))
628 #define PCOR(x) ((pCodeOpReg *)(x))
629 #define PCORB(x) ((pCodeOpRegBit *)(x))
630 #define PCOW(x) ((pCodeOpWild *)(x))
632 #define PBR(x) ((pBranch *)(x))
634 /*-----------------------------------------------------------------*
636 *-----------------------------------------------------------------*/
638 pCode *newpCode (PIC_OPCODE op, pCodeOp *pcop); // Create a new pCode given an operand
639 pCode *newpCodeCharP(char *cP); // Create a new pCode given a char *
640 pCode *newpCodeFunction(char *g, char *f); // Create a new function
641 pCode *newpCodeLabel(char *name,int key); // Create a new label given a key
642 pBlock *newpCodeChain(memmap *cm,char c, pCode *pc); // Create a new pBlock
643 void printpBlock(FILE *of, pBlock *pb); // Write a pBlock to a file
644 void printpCode(FILE *of, pCode *pc); // Write a pCode to a file
645 void addpCode2pBlock(pBlock *pb, pCode *pc); // Add a pCode to a pBlock
646 void addpBlock(pBlock *pb); // Add a pBlock to a pFile
647 void copypCode(FILE *of, char dbName); // Write all pBlocks with dbName to *of
648 void movepBlock2Head(char dbName); // move pBlocks around
649 void AnalyzepCode(char dbName);
650 void OptimizepCode(char dbName);
651 void printCallTree(FILE *of);
652 void pCodePeepInit(void);
653 void pBlockConvert2ISR(pBlock *pb);
655 pCodeOp *newpCodeOpLabel(char *name, int key);
656 pCodeOp *newpCodeOpImmd(char *name, int offset);
657 pCodeOp *newpCodeOpLit(int lit);
658 pCodeOp *newpCodeOpBit(char *name, int bit,int inBitSpace);
659 pCodeOp *newpCodeOpRegFromStr(char *name);
660 pCodeOp *newpCodeOp(char *name, PIC_OPTYPE p);
661 extern void pcode_test(void);
663 /*-----------------------------------------------------------------*
665 *-----------------------------------------------------------------*/
667 extern pCodeOpReg pc_status;
668 extern pCodeOpReg pc_intcon;
669 extern pCodeOpReg pc_indf;
670 extern pCodeOpReg pc_fsr;
671 extern pCodeOpReg pc_pcl;
672 extern pCodeOpReg pc_pclath;
673 extern pCodeOpReg pc_kzero;
674 extern pCodeOpReg pc_wsave; /* wsave and ssave are used to save W and the Status */
675 extern pCodeOpReg pc_ssave; /* registers during an interrupt */
678 #endif // __PCODE_H__