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_GPR_POINTER, // A general purpose pointer
147 PO_SFR_REGISTER, // A special function register (e.g. PORTA)
148 PO_PCL, // Program counter Low register
149 PO_PCLATH, // Program counter Latch high register
150 PO_LITERAL, // A constant
151 PO_IMMEDIATE, // (8051 legacy)
152 PO_DIR, // Direct memory (8051 legacy)
153 PO_CRY, // bit memory (8051 legacy)
154 PO_BIT, // bit operand.
155 PO_STR, // (8051 legacy)
157 PO_WILD // Wild card operand in peep optimizer
161 /***********************************************************************
165 * This is not a list of the PIC's opcodes per se, but instead
166 * an enumeration of all of the different types of pic opcodes.
168 ***********************************************************************/
172 POC_WILD=-1, /* Wild card - used in the pCode peep hole optimizer
173 * to represent ANY pic opcode */
230 /***********************************************************************
231 * PC_TYPE - pCode Types
232 ***********************************************************************/
236 PC_COMMENT=0, /* pCode is a comment */
237 PC_INLINE, /* user's inline code */
238 PC_OPCODE, /* PORT dependent opcode */
239 PC_LABEL, /* assembly label */
240 PC_FLOW, /* flow analysis */
241 PC_FUNCTION, /* Function start or end */
242 PC_WILD, /* wildcard - an opcode place holder used
243 * in the pCode peep hole optimizer */
244 PC_CSOURCE, /* C-Source Line */
245 PC_BAD /* Mark the pCode object as being bad */
248 /************************************************/
249 /*************** Structures ********************/
250 /************************************************/
251 /* These are here as forward references - the
252 * full definition of these are below */
254 struct pCodeWildBlock;
255 struct pCodeRegLives;
257 /*************************************************
260 The first step in optimizing pCode is determining
261 the program flow. This information is stored in
262 single-linked lists in the for of 'from' and 'to'
263 objects with in a pcode. For example, most instructions
264 don't involve any branching. So their from branch
265 points to the pCode immediately preceding them and
266 their 'to' branch points to the pcode immediately
267 following them. A skip instruction is an example of
268 a pcode that has multiple (in this case two) elements
269 in the 'to' branch. A 'label' pcode is an where there
270 may be multiple 'from' branches.
271 *************************************************/
273 typedef struct pBranch
275 struct pCode *pc; // Next pCode in a branch
276 struct pBranch *next; /* If more than one branch
277 * the next one is here */
281 /*************************************************
284 pCode Operand structure.
285 For those assembly instructions that have arguments,
286 the pCode will have a pCodeOp in which the argument
287 can be stored. For example
291 'some_register' will be stored/referenced in a pCodeOp
293 *************************************************/
295 typedef struct pCodeOp
302 typedef struct pCodeOpBit
306 unsigned int inBitSpace: 1; /* True if in bit space, else
307 just a bit of a register */
310 typedef struct pCodeOpLit
316 typedef struct pCodeOpImmd
319 int offset; /* low,med, or high byte of immediate value */
320 int index; /* add this to the immediate value */
321 unsigned _const:1; /* is in code space */
322 unsigned _function:1; /* is a (pointer to a) function */
324 int rIdx; /* If this immd points to a register */
325 struct regs *r; /* then this is the reg. */
329 typedef struct pCodeOpLabel
333 int offset; /* low or high byte of label */
336 typedef struct pCodeOpReg
338 pCodeOp pcop; // Can be either GPR or SFR
339 int rIdx; // Index into the register table
341 int instance; // byte # of Multi-byte registers
345 typedef struct pCodeOpRegBit
347 pCodeOpReg pcor; // The Register containing this bit
348 int bit; // 0-7 bit number.
349 PIC_OPTYPE subtype; // The type of this register.
350 unsigned int inBitSpace: 1; /* True if in bit space, else
351 just a bit of a register */
355 typedef struct pCodeOpRegPtr
357 pCodeOpReg pcor; // The Register containing this bit
359 // PIC_OPTYPE subtype; // The type of this register.
360 // unsigned int inBitSpace: 1; /* True if in bit space, else
364 typedef struct pCodeOpStr /* Only used here for the name of fn being called or jumped to */
367 unsigned isPublic: 1; /* True if not static ie extern */
370 typedef struct pCodeOpWild
374 struct pCodeWildBlock *pcwb;
376 int id; /* index into an array of char *'s that will match
377 * the wild card. The array is in *pcp. */
378 pCodeOp *subtype; /* Pointer to the Operand type into which this wild
379 * card will be expanded */
380 pCodeOp *matched; /* When a wild matches, we'll store a pointer to the
381 * opcode we matched */
386 /*************************************************
389 Here is the basic build block of a PIC instruction.
390 Each pic instruction will get allocated a pCode.
391 A linked list of pCodes makes a program.
393 **************************************************/
399 struct pCode *prev; // The pCode objects are linked together
400 struct pCode *next; // in doubly linked lists.
402 unsigned id; // unique ID number for all pCodes to assist in debugging
403 int seq; // sequence number
405 struct pBlock *pb; // The pBlock that contains this pCode.
407 /* "virtual functions"
408 * The pCode structure is like a base class
409 * in C++. The subsequent structures that "inherit"
410 * the pCode structure will initialize these function
411 * pointers to something useful */
412 // void (*analyze) (struct pCode *_this);
413 void (*destruct)(struct pCode *_this);
414 void (*print) (FILE *of,struct pCode *_this);
419 /*************************************************
421 **************************************************/
423 typedef struct pCodeComment
432 /*************************************************
434 **************************************************/
436 typedef struct pCodeCSource
448 /*************************************************
451 The Flow object is used as marker to separate
452 the assembly code into contiguous chunks. In other
453 words, everytime an instruction cause or potentially
454 causes a branch, a Flow object will be inserted into
455 the pCode chain to mark the beginning of the next
458 **************************************************/
460 typedef struct pCodeFlow
465 pCode *end; /* Last pCode in this flow. Note that
466 the first pCode is pc.next */
468 /* set **uses; * map the pCode instruction inCond and outCond conditions
469 * in this array of set's. The reason we allocate an
470 * array of pointers instead of declaring each type of
471 * usage is because there are port dependent usage definitions */
472 //int nuses; /* number of uses sets */
474 set *from; /* flow blocks that can send control to this flow block */
475 set *to; /* flow blocks to which this one can send control */
476 struct pCodeFlow *ancestor; /* The most immediate "single" pCodeFlow object that
477 * executes prior to this one. In many cases, this
478 * will be just the previous */
480 int inCond; /* Input conditions - stuff assumed defined at entry */
481 int outCond; /* Output conditions - stuff modified by flow block */
483 int firstBank; /* The first and last bank flags are the first and last */
484 int lastBank; /* register banks used within one flow object */
489 set *registers;/* Registers used in this flow */
493 /*************************************************
496 The Flow Link object is used to record information
497 about how consecutive excutive Flow objects are related.
498 The pCodeFlow objects demarcate the pCodeInstructions
499 into contiguous chunks. The FlowLink records conflicts
500 in the discontinuities. For example, if one Flow object
501 references a register in bank 0 and the next Flow object
502 references a register in bank 1, then there is a discontinuity
503 in the banking registers.
506 typedef struct pCodeFlowLink
508 pCodeFlow *pcflow; /* pointer to linked pCodeFlow object */
510 int bank_conflict; /* records bank conflicts */
514 /*************************************************
517 Here we describe all the facets of a PIC instruction
518 (expansion for the 18cxxx is also provided).
520 **************************************************/
522 typedef struct pCodeInstruction
527 PIC_OPCODE op; // The opcode of the instruction.
529 char const * const mnemonic; // Pointer to mnemonic string
531 pBranch *from; // pCodes that execute before this one
532 pBranch *to; // pCodes that execute after
533 pBranch *label; // pCode instructions that have labels
535 pCodeOp *pcop; /* Operand, if this instruction has one */
536 pCodeFlow *pcflow; /* flow block to which this instruction belongs */
537 pCodeCSource *cline; /* C Source from which this instruction was derived */
539 unsigned int num_ops; /* Number of operands (0,1,2 for mid range pics) */
540 unsigned int isModReg: 1; /* If destination is W or F, then 1==F */
541 unsigned int isBitInst: 1; /* e.g. BCF */
542 unsigned int isBranch: 1; /* True if this is a branching instruction */
543 unsigned int isSkip: 1; /* True if this is a skip instruction */
544 unsigned int isLit: 1; /* True if this instruction has an literal operand */
546 PIC_OPCODE inverted_op; /* Opcode of instruction that's the opposite of this one */
547 unsigned int inCond; // Input conditions for this instruction
548 unsigned int outCond; // Output conditions for this instruction
553 /*************************************************
555 **************************************************/
557 typedef struct pCodeLabel
567 /*************************************************
569 **************************************************/
571 typedef struct pCodeFunction
577 char *fname; /* If NULL, then this is the end of
578 a function. Otherwise, it's the
579 start and the name is contained
582 pBranch *from; // pCodes that execute before this one
583 pBranch *to; // pCodes that execute after
584 pBranch *label; // pCode instructions that have labels
586 int ncalled; /* Number of times function is called */
587 unsigned isPublic:1; /* True if the fn is not static and can be called from another module (ie a another c or asm file) */
592 /*************************************************
594 **************************************************/
596 typedef struct pCodeWild
599 pCodeInstruction pci;
601 int id; /* Index into the wild card array of a peepBlock
602 * - this wild card will get expanded into that pCode
603 * that is stored at this index */
605 /* Conditions on wild pcode instruction */
606 int mustBeBitSkipInst:1;
607 int mustNotBeBitSkipInst:1;
608 int invertBitSkipInst:1;
610 pCodeOp *operand; // Optional operand
611 pCodeOp *label; // Optional label
615 /*************************************************
618 Here are PIC program snippets. There's a strong
619 correlation between the eBBlocks and pBlocks.
620 SDCC subdivides a C program into managable chunks.
621 Each chunk becomes a eBBlock and ultimately in the
624 **************************************************/
626 typedef struct pBlock
628 memmap *cmemmap; /* The snippet is from this memmap */
629 char dbName; /* if cmemmap is NULL, then dbName will identify the block */
630 pCode *pcHead; /* A pointer to the first pCode in a link list of pCodes */
631 pCode *pcTail; /* A pointer to the last pCode in a link list of pCodes */
633 struct pBlock *next; /* The pBlocks will form a doubly linked list */
636 set *function_entries; /* dll of functions in this pblock */
642 unsigned visited:1; /* set true if traversed in call tree */
644 unsigned seq; /* sequence number of this pBlock */
648 /*************************************************
651 The collection of pBlock program snippets are
652 placed into a linked list that is implemented
653 in the pFile structure.
655 The pcode optimizer will parse the pFile.
657 **************************************************/
661 pBlock *pbHead; /* A pointer to the first pBlock */
662 pBlock *pbTail; /* A pointer to the last pBlock */
664 pBranch *functions; /* A SLL of functions in this pFile */
670 /*************************************************
673 The pCodeWildBlock object keeps track of the wild
674 variables, operands, and opcodes that exist in
676 **************************************************/
677 typedef struct pCodeWildBlock {
679 struct pCodePeep *pcp; // pointer back to ... I don't like this...
681 int nvars; // Number of wildcard registers in target.
682 char **vars; // array of pointers to them
684 int nops; // Number of wildcard operands in target.
685 pCodeOp **wildpCodeOps; // array of pointers to the pCodeOp's.
687 int nwildpCodes; // Number of wildcard pCodes in target/replace
688 pCode **wildpCodes; // array of pointers to the pCode's.
692 /*************************************************
695 The pCodePeep object mimics the peep hole optimizer
696 in the main SDCC src (e.g. SDCCpeeph.c). Essentially
697 there is a target pCode chain and a replacement
698 pCode chain. The target chain is compared to the
699 pCode that is generated by gen.c. If a match is
700 found then the pCode is replaced by the replacement
702 **************************************************/
703 typedef struct pCodePeep {
704 pCodeWildBlock target; // code we'd like to optimize
705 pCodeWildBlock replace; // and this is what we'll optimize it with.
708 //pBlock replace; // and this is what we'll optimize it with.
712 /* (Note: a wildcard register is a place holder. Any register
713 * can be replaced by the wildcard when the pcode is being
714 * compared to the target. */
716 /* Post Conditions. A post condition is a condition that
717 * must be either true or false before the peep rule is
718 * accepted. For example, a certain rule may be accepted
719 * if and only if the Z-bit is not used as an input to
720 * the subsequent instructions in a pCode chain.
722 unsigned int postFalseCond;
723 unsigned int postTrueCond;
727 /*************************************************
729 pCode peep command definitions
731 Here are some special commands that control the
732 way the peep hole optimizer behaves
734 **************************************************/
736 enum peepCommandTypes{
743 /*************************************************
744 peepCommand structure stores the peep commands.
746 **************************************************/
748 typedef struct peepCommand {
753 /*************************************************
756 **************************************************/
757 #define PCODE(x) ((pCode *)(x))
758 #define PCI(x) ((pCodeInstruction *)(x))
759 #define PCL(x) ((pCodeLabel *)(x))
760 #define PCF(x) ((pCodeFunction *)(x))
761 #define PCFL(x) ((pCodeFlow *)(x))
762 #define PCFLINK(x)((pCodeFlowLink *)(x))
763 #define PCW(x) ((pCodeWild *)(x))
764 #define PCCS(x) ((pCodeCSource *)(x))
766 #define PCOP(x) ((pCodeOp *)(x))
767 //#define PCOB(x) ((pCodeOpBit *)(x))
768 #define PCOL(x) ((pCodeOpLit *)(x))
769 #define PCOI(x) ((pCodeOpImmd *)(x))
770 #define PCOLAB(x) ((pCodeOpLabel *)(x))
771 #define PCOR(x) ((pCodeOpReg *)(x))
772 #define PCORB(x) ((pCodeOpRegBit *)(x))
773 #define PCOS(x) ((pCodeOpStr *)(x))
774 #define PCOW(x) ((pCodeOpWild *)(x))
776 #define PBR(x) ((pBranch *)(x))
778 #define PCWB(x) ((pCodeWildBlock *)(x))
780 #define isPCOLAB(x) ((PCOP(x)->type) == PO_LABEL)
781 #define isPCOS(x) ((PCOP(x)->type) == PO_STR)
785 macros for checking pCode types
787 #define isPCI(x) ((PCODE(x)->type == PC_OPCODE))
788 #define isPCFL(x) ((PCODE(x)->type == PC_FLOW))
789 #define isPCF(x) ((PCODE(x)->type == PC_FUNCTION))
790 #define isPCL(x) ((PCODE(x)->type == PC_LABEL))
791 #define isPCW(x) ((PCODE(x)->type == PC_WILD))
792 #define isPCCS(x) ((PCODE(x)->type == PC_CSOURCE))
795 macros for checking pCodeInstruction types
797 #define isCALL(x) (isPCI(x) && (PCI(x)->op == POC_CALL))
798 #define isPCI_BRANCH(x) (isPCI(x) && PCI(x)->isBranch)
799 #define isPCI_SKIP(x) (isPCI(x) && PCI(x)->isSkip)
800 #define isPCI_LIT(x) (isPCI(x) && PCI(x)->isLit)
801 #define isPCI_BITSKIP(x)(isPCI_SKIP(x) && PCI(x)->isBitInst)
804 #define isSTATUS_REG(r) ((r)->pc_type == PO_STATUS)
806 /*-----------------------------------------------------------------*
808 *-----------------------------------------------------------------*/
810 pCode *newpCode (PIC_OPCODE op, pCodeOp *pcop); // Create a new pCode given an operand
811 pCode *newpCodeCharP(char *cP); // Create a new pCode given a char *
812 pCode *newpCodeInlineP(char *cP); // Create a new pCode given a char *
813 pCode *newpCodeFunction(char *g, char *f,int); // Create a new function
814 pCode *newpCodeLabel(char *name,int key); // Create a new label given a key
815 pCode *newpCodeCSource(int ln, char *f, char *l); // Create a new symbol line
816 pCode *findNextInstruction(pCode *pci);
817 pCode *findNextpCode(pCode *pc, PC_TYPE pct);
818 pCode *pCodeInstructionCopy(pCodeInstruction *pci,int invert);
820 pBlock *newpCodeChain(memmap *cm,char c, pCode *pc); // Create a new pBlock
821 void printpBlock(FILE *of, pBlock *pb); // Write a pBlock to a file
822 void printpCode(FILE *of, pCode *pc); // Write a pCode to a file
823 void addpCode2pBlock(pBlock *pb, pCode *pc); // Add a pCode to a pBlock
824 void addpBlock(pBlock *pb); // Add a pBlock to a pFile
825 void copypCode(FILE *of, char dbName); // Write all pBlocks with dbName to *of
826 void movepBlock2Head(char dbName); // move pBlocks around
827 void AnalyzepCode(char dbName);
828 int OptimizepCode(char dbName);
829 void printCallTree(FILE *of);
830 void pCodePeepInit(void);
831 void pBlockConvert2ISR(pBlock *pb);
832 void pCodeInsertAfter(pCode *pc1, pCode *pc2);
833 void pCodeInsertBefore(pCode *pc1, pCode *pc2);
834 void pCodeDeleteChain(pCode *f,pCode *t);
836 pCodeOp *newpCodeOpLabel(char *name, int key);
837 pCodeOp *newpCodeOpImmd(char *name, int offset, int index, int code_space,int is_func);
838 pCodeOp *newpCodeOpLit(int lit);
839 pCodeOp *newpCodeOpBit(char *name, int bit,int inBitSpace);
840 pCodeOp *newpCodeOpRegFromStr(char *name);
841 pCodeOp *newpCodeOp(char *name, PIC_OPTYPE p);
842 pCodeOp *pCodeOpCopy(pCodeOp *pcop);
843 pCodeOp *popCopyReg(pCodeOpReg *pc);
845 int isPCinFlow(pCode *pc, pCode *pcflow);
846 struct regs * getRegFromInstruction(pCode *pc);
848 extern void pcode_test(void);
850 /*-----------------------------------------------------------------*
852 *-----------------------------------------------------------------*/
854 extern pCodeOpReg pc_status;
855 extern pCodeOpReg pc_intcon;
856 extern pCodeOpReg pc_indf;
857 extern pCodeOpReg pc_fsr;
858 extern pCodeOpReg pc_pcl;
859 extern pCodeOpReg pc_pclath;
860 extern pCodeOpReg pc_wsave; /* wsave, ssave and psave are used to save W, the Status and PCLATH*/
861 extern pCodeOpReg pc_ssave; /* registers during an interrupt */
862 extern pCodeOpReg pc_psave; /* registers during an interrupt */
865 #endif // __PCODE_H__
projects / fw / sdcc / blob