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 /* When changing these, you must also update the assembler template
26 * in device/lib/libsdcc/macros.inc */
27 #define GPTRTAG_DATA 0x00
28 #define GPTRTAG_CODE 0x80
33 The post code generation is an assembler optimizer. The assembly code
34 produced by all of the previous steps is fully functional. This step
35 will attempt to analyze the flow of the assembly code and agressively
36 optimize it. The peep hole optimizer attempts to do the same thing.
37 As you may recall, the peep hole optimizer replaces blocks of assembly
38 with more optimal blocks (e.g. removing redundant register loads).
39 However, the peep hole optimizer has to be somewhat conservative since
40 an assembly program has implicit state information that's unavailable
41 when only a few instructions are examined.
42 Consider this example:
48 The movf seems redundant since we know that the W register already
49 contains the same value of t1. So a peep hole optimizer is tempted to
50 remove the "movf". However, this is dangerous since the movf affects
51 the flags in the status register (specifically the Z flag) and subsequent
52 code may depend upon this. Look at these two examples:
56 movf t1,w ; Can't remove this movf
62 movf t1,w ; This movf can be removed
63 xorwf t2,w ; since xorwf will over write Z
73 /***********************************************************************
76 * The DFPRINTF macro will call fprintf if PCODE_DEBUG is defined.
77 * The macro is used like:
79 * DPRINTF(("%s #%d\n","test", 1));
81 * The double parenthesis (()) are necessary
83 ***********************************************************************/
87 #define DFPRINTF(args) (fprintf args)
89 #define DFPRINTF(args) ;
93 /***********************************************************************
94 * PIC status bits - this will move into device dependent headers
95 ***********************************************************************/
99 #define PIC_RP0_BIT 5 /* Register Bank select bits RP1:0 : */
100 #define PIC_RP1_BIT 6 /* 00 - bank 0, 01 - bank 1, 10 - bank 2, 11 - bank 3 */
101 #define PIC_IRP_BIT 7 /* Indirect register page select */
103 /***********************************************************************
104 * PIC INTCON bits - this will move into device dependent headers
105 ***********************************************************************/
106 #define PIC_RBIF_BIT 0 /* Port B level has changed flag */
107 #define PIC_INTF_BIT 1 /* Port B bit 0 interrupt on edge flag */
108 #define PIC_T0IF_BIT 2 /* TMR0 has overflowed flag */
109 #define PIC_RBIE_BIT 3 /* Port B level has changed - Interrupt Enable */
110 #define PIC_INTE_BIT 4 /* Port B bit 0 interrupt on edge - Int Enable */
111 #define PIC_T0IE_BIT 5 /* TMR0 overflow Interrupt Enable */
112 #define PIC_PIE_BIT 6 /* Peripheral Interrupt Enable */
113 #define PIC_GIE_BIT 7 /* Global Interrupt Enable */
115 /***********************************************************************
117 ***********************************************************************/
123 /***********************************************************************
125 * PIC_OPTYPE - Operand types that are specific to the PIC architecture
127 * If a PIC assembly instruction has an operand then here is where we
128 * associate a type to it. For example,
132 * The movf has two operands: 'reg' and the W register. 'reg' is some
133 * arbitrary general purpose register, hence it has the type PO_GPR_REGISTER.
134 * The W register, which is the PIC's accumulator, has the type PO_W.
136 ***********************************************************************/
142 PO_NONE=0, // No operand e.g. NOP
143 PO_W, // The 'W' register
144 PO_STATUS, // The 'STATUS' register
145 PO_FSR, // The "file select register" (in 18c it's one of three)
146 PO_INDF, // The Indirect register
147 PO_INTCON, // Interrupt Control register
148 PO_GPR_REGISTER, // A general purpose register
149 PO_GPR_BIT, // A bit of a general purpose register
150 PO_GPR_TEMP, // A general purpose temporary register
151 PO_GPR_POINTER, // A general purpose pointer
152 PO_SFR_REGISTER, // A special function register (e.g. PORTA)
153 PO_PCL, // Program counter Low register
154 PO_PCLATH, // Program counter Latch high register
155 PO_LITERAL, // A constant
156 PO_IMMEDIATE, // (8051 legacy)
157 PO_DIR, // Direct memory (8051 legacy)
158 PO_CRY, // bit memory (8051 legacy)
159 PO_BIT, // bit operand.
160 PO_STR, // (8051 legacy)
162 PO_WILD // Wild card operand in peep optimizer
166 /***********************************************************************
170 * This is not a list of the PIC's opcodes per se, but instead
171 * an enumeration of all of the different types of pic opcodes.
173 ***********************************************************************/
177 POC_WILD=-1, /* Wild card - used in the pCode peep hole optimizer
178 * to represent ANY pic opcode */
235 /***********************************************************************
236 * PC_TYPE - pCode Types
237 ***********************************************************************/
241 PC_COMMENT=0, /* pCode is a comment */
242 PC_INLINE, /* user's inline code */
243 PC_OPCODE, /* PORT dependent opcode */
244 PC_LABEL, /* assembly label */
245 PC_FLOW, /* flow analysis */
246 PC_FUNCTION, /* Function start or end */
247 PC_WILD, /* wildcard - an opcode place holder used
248 * in the pCode peep hole optimizer */
249 PC_CSOURCE, /* C-Source Line */
250 PC_ASMDIR, /* Assembler directive */
251 PC_BAD /* Mark the pCode object as being bad */
254 /************************************************/
255 /*************** Structures ********************/
256 /************************************************/
257 /* These are here as forward references - the
258 * full definition of these are below */
260 struct pCodeWildBlock;
261 struct pCodeRegLives;
263 /*************************************************
266 The first step in optimizing pCode is determining
267 the program flow. This information is stored in
268 single-linked lists in the for of 'from' and 'to'
269 objects with in a pcode. For example, most instructions
270 don't involve any branching. So their from branch
271 points to the pCode immediately preceding them and
272 their 'to' branch points to the pcode immediately
273 following them. A skip instruction is an example of
274 a pcode that has multiple (in this case two) elements
275 in the 'to' branch. A 'label' pcode is an where there
276 may be multiple 'from' branches.
277 *************************************************/
279 typedef struct pBranch
281 struct pCode *pc; // Next pCode in a branch
282 struct pBranch *next; /* If more than one branch
283 * the next one is here */
287 /*************************************************
290 pCode Operand structure.
291 For those assembly instructions that have arguments,
292 the pCode will have a pCodeOp in which the argument
293 can be stored. For example
297 'some_register' will be stored/referenced in a pCodeOp
299 *************************************************/
301 typedef struct pCodeOp
308 typedef struct pCodeOpBit
312 unsigned int inBitSpace: 1; /* True if in bit space, else
313 just a bit of a register */
316 typedef struct pCodeOpLit
322 typedef struct pCodeOpImmd
325 int offset; /* low,med, or high byte of immediate value */
326 int index; /* add this to the immediate value */
327 unsigned _const:1; /* is in code space */
328 unsigned _function:1; /* is a (pointer to a) function */
330 int rIdx; /* If this immd points to a register */
331 struct regs *r; /* then this is the reg. */
335 typedef struct pCodeOpLabel
339 int offset; /* low or high byte of label */
342 typedef struct pCodeOpReg
344 pCodeOp pcop; // Can be either GPR or SFR
345 int rIdx; // Index into the register table
347 int instance; // byte # of Multi-byte registers
351 typedef struct pCodeOpRegBit
353 pCodeOpReg pcor; // The Register containing this bit
354 int bit; // 0-7 bit number.
355 PIC_OPTYPE subtype; // The type of this register.
356 unsigned int inBitSpace: 1; /* True if in bit space, else
357 just a bit of a register */
361 typedef struct pCodeOpRegPtr
363 pCodeOpReg pcor; // The Register containing this bit
365 // PIC_OPTYPE subtype; // The type of this register.
366 // unsigned int inBitSpace: 1; /* True if in bit space, else
370 typedef struct pCodeOpStr /* Only used here for the name of fn being called or jumped to */
373 unsigned isPublic: 1; /* True if not static ie extern */
376 typedef struct pCodeOpWild
380 struct pCodeWildBlock *pcwb;
382 int id; /* index into an array of char *'s that will match
383 * the wild card. The array is in *pcp. */
384 pCodeOp *subtype; /* Pointer to the Operand type into which this wild
385 * card will be expanded */
386 pCodeOp *matched; /* When a wild matches, we'll store a pointer to the
387 * opcode we matched */
392 /*************************************************
395 Here is the basic build block of a PIC instruction.
396 Each pic instruction will get allocated a pCode.
397 A linked list of pCodes makes a program.
399 **************************************************/
405 struct pCode *prev; // The pCode objects are linked together
406 struct pCode *next; // in doubly linked lists.
408 unsigned id; // unique ID number for all pCodes to assist in debugging
409 int seq; // sequence number
411 struct pBlock *pb; // The pBlock that contains this pCode.
413 /* "virtual functions"
414 * The pCode structure is like a base class
415 * in C++. The subsequent structures that "inherit"
416 * the pCode structure will initialize these function
417 * pointers to something useful */
418 // void (*analyze) (struct pCode *_this);
419 void (*destruct)(struct pCode *_this);
420 void (*print) (FILE *of,struct pCode *_this);
425 /*************************************************
427 **************************************************/
429 typedef struct pCodeComment
439 /*************************************************
441 **************************************************/
443 typedef struct pCodeCSource
455 /*************************************************
458 The Flow object is used as marker to separate
459 the assembly code into contiguous chunks. In other
460 words, everytime an instruction cause or potentially
461 causes a branch, a Flow object will be inserted into
462 the pCode chain to mark the beginning of the next
465 **************************************************/
467 typedef struct pCodeFlow
472 pCode *end; /* Last pCode in this flow. Note that
473 the first pCode is pc.next */
475 /* set **uses; * map the pCode instruction inCond and outCond conditions
476 * in this array of set's. The reason we allocate an
477 * array of pointers instead of declaring each type of
478 * usage is because there are port dependent usage definitions */
479 //int nuses; /* number of uses sets */
481 set *from; /* flow blocks that can send control to this flow block */
482 set *to; /* flow blocks to which this one can send control */
483 struct pCodeFlow *ancestor; /* The most immediate "single" pCodeFlow object that
484 * executes prior to this one. In many cases, this
485 * will be just the previous */
487 int inCond; /* Input conditions - stuff assumed defined at entry */
488 int outCond; /* Output conditions - stuff modified by flow block */
490 int firstBank; /* The first and last bank flags are the first and last */
491 int lastBank; /* register banks used within one flow object */
496 set *registers;/* Registers used in this flow */
501 /*************************************************
504 The Flow Link object is used to record information
505 about how consecutive excutive Flow objects are related.
506 The pCodeFlow objects demarcate the pCodeInstructions
507 into contiguous chunks. The FlowLink records conflicts
508 in the discontinuities. For example, if one Flow object
509 references a register in bank 0 and the next Flow object
510 references a register in bank 1, then there is a discontinuity
511 in the banking registers.
514 typedef struct pCodeFlowLink
516 pCodeFlow *pcflow; /* pointer to linked pCodeFlow object */
518 int bank_conflict; /* records bank conflicts */
523 /*************************************************
526 Here we describe all the facets of a PIC instruction
527 (expansion for the 18cxxx is also provided).
529 **************************************************/
531 typedef struct pCodeInstruction
536 PIC_OPCODE op; // The opcode of the instruction.
538 char const * const mnemonic; // Pointer to mnemonic string
540 pBranch *from; // pCodes that execute before this one
541 pBranch *to; // pCodes that execute after
542 pBranch *label; // pCode instructions that have labels
544 pCodeOp *pcop; /* Operand, if this instruction has one */
545 pCodeFlow *pcflow; /* flow block to which this instruction belongs */
546 pCodeCSource *cline; /* C Source from which this instruction was derived */
548 unsigned int num_ops; /* Number of operands (0,1,2 for mid range pics) */
549 unsigned int isModReg: 1; /* If destination is W or F, then 1==F */
550 unsigned int isBitInst: 1; /* e.g. BCF */
551 unsigned int isBranch: 1; /* True if this is a branching instruction */
552 unsigned int isSkip: 1; /* True if this is a skip instruction */
553 unsigned int isLit: 1; /* True if this instruction has an literal operand */
555 PIC_OPCODE inverted_op; /* Opcode of instruction that's the opposite of this one */
556 unsigned int inCond; // Input conditions for this instruction
557 unsigned int outCond; // Output conditions for this instruction
562 /*************************************************
564 **************************************************/
566 typedef struct pCodeAsmDir
568 pCodeInstruction pci;
575 /*************************************************
577 **************************************************/
579 typedef struct pCodeLabel
590 /*************************************************
592 **************************************************/
594 typedef struct pCodeFunction
600 char *fname; /* If NULL, then this is the end of
601 a function. Otherwise, it's the
602 start and the name is contained
605 pBranch *from; // pCodes that execute before this one
606 pBranch *to; // pCodes that execute after
607 pBranch *label; // pCode instructions that have labels
609 int ncalled; /* Number of times function is called */
610 unsigned isPublic:1; /* True if the fn is not static and can be called from another module (ie a another c or asm file) */
615 /*************************************************
617 **************************************************/
619 typedef struct pCodeWild
622 pCodeInstruction pci;
624 int id; /* Index into the wild card array of a peepBlock
625 * - this wild card will get expanded into that pCode
626 * that is stored at this index */
628 /* Conditions on wild pcode instruction */
629 int mustBeBitSkipInst:1;
630 int mustNotBeBitSkipInst:1;
631 int invertBitSkipInst:1;
633 pCodeOp *operand; // Optional operand
634 pCodeOp *label; // Optional label
638 /*************************************************
641 Here are PIC program snippets. There's a strong
642 correlation between the eBBlocks and pBlocks.
643 SDCC subdivides a C program into managable chunks.
644 Each chunk becomes a eBBlock and ultimately in the
647 **************************************************/
649 typedef struct pBlock
651 memmap *cmemmap; /* The snippet is from this memmap */
652 char dbName; /* if cmemmap is NULL, then dbName will identify the block */
653 pCode *pcHead; /* A pointer to the first pCode in a link list of pCodes */
654 pCode *pcTail; /* A pointer to the last pCode in a link list of pCodes */
656 struct pBlock *next; /* The pBlocks will form a doubly linked list */
659 set *function_entries; /* dll of functions in this pblock */
665 unsigned visited:1; /* set true if traversed in call tree */
667 unsigned seq; /* sequence number of this pBlock */
671 /*************************************************
674 The collection of pBlock program snippets are
675 placed into a linked list that is implemented
676 in the pFile structure.
678 The pcode optimizer will parse the pFile.
680 **************************************************/
684 pBlock *pbHead; /* A pointer to the first pBlock */
685 pBlock *pbTail; /* A pointer to the last pBlock */
687 pBranch *functions; /* A SLL of functions in this pFile */
693 /*************************************************
696 The pCodeWildBlock object keeps track of the wild
697 variables, operands, and opcodes that exist in
699 **************************************************/
700 typedef struct pCodeWildBlock {
702 struct pCodePeep *pcp; // pointer back to ... I don't like this...
704 int nvars; // Number of wildcard registers in target.
705 char **vars; // array of pointers to them
707 int nops; // Number of wildcard operands in target.
708 pCodeOp **wildpCodeOps; // array of pointers to the pCodeOp's.
710 int nwildpCodes; // Number of wildcard pCodes in target/replace
711 pCode **wildpCodes; // array of pointers to the pCode's.
715 /*************************************************
718 The pCodePeep object mimics the peep hole optimizer
719 in the main SDCC src (e.g. SDCCpeeph.c). Essentially
720 there is a target pCode chain and a replacement
721 pCode chain. The target chain is compared to the
722 pCode that is generated by gen.c. If a match is
723 found then the pCode is replaced by the replacement
725 **************************************************/
726 typedef struct pCodePeep {
727 pCodeWildBlock target; // code we'd like to optimize
728 pCodeWildBlock replace; // and this is what we'll optimize it with.
731 //pBlock replace; // and this is what we'll optimize it with.
735 /* (Note: a wildcard register is a place holder. Any register
736 * can be replaced by the wildcard when the pcode is being
737 * compared to the target. */
739 /* Post Conditions. A post condition is a condition that
740 * must be either true or false before the peep rule is
741 * accepted. For example, a certain rule may be accepted
742 * if and only if the Z-bit is not used as an input to
743 * the subsequent instructions in a pCode chain.
745 unsigned int postFalseCond;
746 unsigned int postTrueCond;
750 /*************************************************
752 pCode peep command definitions
754 Here are some special commands that control the
755 way the peep hole optimizer behaves
757 **************************************************/
759 enum peepCommandTypes{
766 /*************************************************
767 peepCommand structure stores the peep commands.
769 **************************************************/
771 typedef struct peepCommand {
776 /*************************************************
779 **************************************************/
780 #define PCODE(x) ((pCode *)(x))
781 #define PCI(x) ((pCodeInstruction *)(x))
782 #define PCL(x) ((pCodeLabel *)(x))
783 #define PCF(x) ((pCodeFunction *)(x))
784 #define PCFL(x) ((pCodeFlow *)(x))
785 #define PCFLINK(x)((pCodeFlowLink *)(x))
786 #define PCW(x) ((pCodeWild *)(x))
787 #define PCCS(x) ((pCodeCSource *)(x))
788 #define PCAD(x) ((pCodeAsmDir *)(x))
790 #define PCOP(x) ((pCodeOp *)(x))
791 //#define PCOB(x) ((pCodeOpBit *)(x))
792 #define PCOL(x) ((pCodeOpLit *)(x))
793 #define PCOI(x) ((pCodeOpImmd *)(x))
794 #define PCOLAB(x) ((pCodeOpLabel *)(x))
795 #define PCOR(x) ((pCodeOpReg *)(x))
796 #define PCORB(x) ((pCodeOpRegBit *)(x))
797 #define PCOS(x) ((pCodeOpStr *)(x))
798 #define PCOW(x) ((pCodeOpWild *)(x))
800 #define PBR(x) ((pBranch *)(x))
802 #define PCWB(x) ((pCodeWildBlock *)(x))
804 #define isPCOLAB(x) ((PCOP(x)->type) == PO_LABEL)
805 #define isPCOS(x) ((PCOP(x)->type) == PO_STR)
809 macros for checking pCode types
811 #define isPCI(x) ((PCODE(x)->type == PC_OPCODE))
812 #define isPCFL(x) ((PCODE(x)->type == PC_FLOW))
813 #define isPCF(x) ((PCODE(x)->type == PC_FUNCTION))
814 #define isPCL(x) ((PCODE(x)->type == PC_LABEL))
815 #define isPCW(x) ((PCODE(x)->type == PC_WILD))
816 #define isPCCS(x) ((PCODE(x)->type == PC_CSOURCE))
817 #define isPCASMDIR(x) ((PCODE(x)->type == PC_ASMDIR))
820 macros for checking pCodeInstruction types
822 #define isCALL(x) (isPCI(x) && (PCI(x)->op == POC_CALL))
823 #define isPCI_BRANCH(x) (isPCI(x) && PCI(x)->isBranch)
824 #define isPCI_SKIP(x) (isPCI(x) && PCI(x)->isSkip)
825 #define isPCI_LIT(x) (isPCI(x) && PCI(x)->isLit)
826 #define isPCI_BITSKIP(x)(isPCI_SKIP(x) && PCI(x)->isBitInst)
829 #define isSTATUS_REG(r) ((r)->pc_type == PO_STATUS)
831 /*-----------------------------------------------------------------*
833 *-----------------------------------------------------------------*/
835 pCode *newpCode (PIC_OPCODE op, pCodeOp *pcop); // Create a new pCode given an operand
836 pCode *newpCodeCharP(char *cP); // Create a new pCode given a char *
837 pCode *newpCodeInlineP(char *cP); // Create a new pCode given a char *
838 pCode *newpCodeFunction(char *g, char *f,int); // Create a new function
839 pCode *newpCodeLabel(char *name,int key); // Create a new label given a key
840 pCode *newpCodeCSource(int ln, char *f, const char *l); // Create a new symbol line
841 pCode *findNextInstruction(pCode *pci);
842 pCode *findNextpCode(pCode *pc, PC_TYPE pct);
843 pCode *pCodeInstructionCopy(pCodeInstruction *pci,int invert);
845 pBlock *newpCodeChain(memmap *cm,char c, pCode *pc); // Create a new pBlock
846 void printpBlock(FILE *of, pBlock *pb); // Write a pBlock to a file
847 void printpCode(FILE *of, pCode *pc); // Write a pCode to a file
848 void addpCode2pBlock(pBlock *pb, pCode *pc); // Add a pCode to a pBlock
849 void addpBlock(pBlock *pb); // Add a pBlock to a pFile
850 void copypCode(FILE *of, char dbName); // Write all pBlocks with dbName to *of
851 void movepBlock2Head(char dbName); // move pBlocks around
852 void AnalyzepCode(char dbName);
853 int OptimizepCode(char dbName);
854 void printCallTree(FILE *of);
855 void pCodePeepInit(void);
856 void pBlockConvert2ISR(pBlock *pb);
857 void pCodeInsertAfter(pCode *pc1, pCode *pc2);
858 void pCodeInsertBefore(pCode *pc1, pCode *pc2);
859 void pCodeDeleteChain(pCode *f,pCode *t);
861 pCode *newpCodeAsmDir(char *asdir, char *argfmt, ...);
863 pCodeOp *newpCodeOpLabel(char *name, int key);
864 pCodeOp *newpCodeOpImmd(char *name, int offset, int index, int code_space,int is_func);
865 pCodeOp *newpCodeOpLit(int lit);
866 pCodeOp *newpCodeOpBit(char *name, int bit,int inBitSpace);
867 pCodeOp *newpCodeOpRegFromStr(char *name);
868 pCodeOp *newpCodeOp(char *name, PIC_OPTYPE p);
869 pCodeOp *pCodeOpCopy(pCodeOp *pcop);
870 pCodeOp *popCopyReg(pCodeOpReg *pc);
872 int isPCinFlow(pCode *pc, pCode *pcflow);
873 struct regs * getRegFromInstruction(pCode *pc);
875 extern void pcode_test(void);
876 void resetpCodeStatistics (void);
877 void dumppCodeStatistics (FILE *of);
879 /*-----------------------------------------------------------------*
881 *-----------------------------------------------------------------*/
883 extern pCodeOpReg pc_status;
884 extern pCodeOpReg pc_intcon;
885 extern pCodeOpReg pc_indf;
886 extern pCodeOpReg pc_fsr;
887 extern pCodeOpReg pc_pcl;
888 extern pCodeOpReg pc_pclath;
889 extern pCodeOpReg pc_wsave; /* wsave, ssave and psave are used to save W, the Status and PCLATH*/
890 extern pCodeOpReg pc_ssave; /* registers during an interrupt */
891 extern pCodeOpReg pc_psave; /* registers during an interrupt */
894 #endif // __PCODE_H__