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 -------------------------------------------------------------------------*/
27 /* When changing these, you must also update the assembler template
28 * in device/lib/libsdcc/macros.inc */
29 #define GPTRTAG_DATA 0x00
30 #define GPTRTAG_CODE 0x80
32 /* Cyclic dependency with ralloc.h: */
38 The post code generation is an assembler optimizer. The assembly code
39 produced by all of the previous steps is fully functional. This step
40 will attempt to analyze the flow of the assembly code and agressively
41 optimize it. The peep hole optimizer attempts to do the same thing.
42 As you may recall, the peep hole optimizer replaces blocks of assembly
43 with more optimal blocks (e.g. removing redundant register loads).
44 However, the peep hole optimizer has to be somewhat conservative since
45 an assembly program has implicit state information that's unavailable
46 when only a few instructions are examined.
47 Consider this example:
53 The movf seems redundant since we know that the W register already
54 contains the same value of t1. So a peep hole optimizer is tempted to
55 remove the "movf". However, this is dangerous since the movf affects
56 the flags in the status register (specifically the Z flag) and subsequent
57 code may depend upon this. Look at these two examples:
61 movf t1,w ; Can't remove this movf
67 movf t1,w ; This movf can be removed
68 xorwf t2,w ; since xorwf will over write Z
75 /***********************************************************************
78 * The DFPRINTF macro will call fprintf if PCODE_DEBUG is defined.
79 * The macro is used like:
81 * DPRINTF(("%s #%d\n","test", 1));
83 * The double parenthesis (()) are necessary
85 ***********************************************************************/
89 #define DFPRINTF(args) (fprintf args)
91 #define DFPRINTF(args) ((void)0)
95 /***********************************************************************
96 * PIC status bits - this will move into device dependent headers
97 ***********************************************************************/
101 #define PIC_RP0_BIT 5 /* Register Bank select bits RP1:0 : */
102 #define PIC_RP1_BIT 6 /* 00 - bank 0, 01 - bank 1, 10 - bank 2, 11 - bank 3 */
103 #define PIC_IRP_BIT 7 /* Indirect register page select */
105 /***********************************************************************
106 * PIC INTCON bits - this will move into device dependent headers
107 ***********************************************************************/
108 #define PIC_RBIF_BIT 0 /* Port B level has changed flag */
109 #define PIC_INTF_BIT 1 /* Port B bit 0 interrupt on edge flag */
110 #define PIC_T0IF_BIT 2 /* TMR0 has overflowed flag */
111 #define PIC_RBIE_BIT 3 /* Port B level has changed - Interrupt Enable */
112 #define PIC_INTE_BIT 4 /* Port B bit 0 interrupt on edge - Int Enable */
113 #define PIC_T0IE_BIT 5 /* TMR0 overflow Interrupt Enable */
114 #define PIC_PIE_BIT 6 /* Peripheral Interrupt Enable */
115 #define PIC_GIE_BIT 7 /* Global Interrupt Enable */
117 /***********************************************************************
119 ***********************************************************************/
125 /***********************************************************************
127 * PIC_OPTYPE - Operand types that are specific to the PIC architecture
129 * If a PIC assembly instruction has an operand then here is where we
130 * associate a type to it. For example,
134 * The movf has two operands: 'reg' and the W register. 'reg' is some
135 * arbitrary general purpose register, hence it has the type PO_GPR_REGISTER.
136 * The W register, which is the PIC's accumulator, has the type PO_W.
138 ***********************************************************************/
144 PO_NONE=0, // No operand e.g. NOP
145 PO_W, // The 'W' register
146 PO_STATUS, // The 'STATUS' register
147 PO_FSR, // The "file select register" (in 18c it's one of three)
148 PO_INDF, // The Indirect register
149 PO_INTCON, // Interrupt Control register
150 PO_GPR_REGISTER, // A general purpose register
151 PO_GPR_BIT, // A bit of a general purpose register
152 PO_GPR_TEMP, // A general purpose temporary register
153 PO_GPR_POINTER, // A general purpose pointer
154 PO_SFR_REGISTER, // A special function register (e.g. PORTA)
155 PO_PCL, // Program counter Low register
156 PO_PCLATH, // Program counter Latch high register
157 PO_LITERAL, // A constant
158 PO_IMMEDIATE, // (8051 legacy)
159 PO_DIR, // Direct memory (8051 legacy)
160 PO_CRY, // bit memory (8051 legacy)
161 PO_BIT, // bit operand.
162 PO_STR, // (8051 legacy)
164 PO_WILD // Wild card operand in peep optimizer
168 /***********************************************************************
172 * This is not a list of the PIC's opcodes per se, but instead
173 * an enumeration of all of the different types of pic opcodes.
175 ***********************************************************************/
179 POC_WILD=-1, /* Wild card - used in the pCode peep hole optimizer
180 * to represent ANY pic opcode */
237 /***********************************************************************
238 * PC_TYPE - pCode Types
239 ***********************************************************************/
243 PC_COMMENT=0, /* pCode is a comment */
244 PC_INLINE, /* user's inline code */
245 PC_OPCODE, /* PORT dependent opcode */
246 PC_LABEL, /* assembly label */
247 PC_FLOW, /* flow analysis */
248 PC_FUNCTION, /* Function start or end */
249 PC_WILD, /* wildcard - an opcode place holder used
250 * in the pCode peep hole optimizer */
251 PC_CSOURCE, /* C-Source Line */
252 PC_ASMDIR, /* Assembler directive */
253 PC_BAD /* Mark the pCode object as being bad */
256 /************************************************/
257 /*************** Structures ********************/
258 /************************************************/
259 /* These are here as forward references - the
260 * full definition of these are below */
262 struct pCodeWildBlock;
263 struct pCodeRegLives;
265 /*************************************************
268 The first step in optimizing pCode is determining
269 the program flow. This information is stored in
270 single-linked lists in the for of 'from' and 'to'
271 objects with in a pcode. For example, most instructions
272 don't involve any branching. So their from branch
273 points to the pCode immediately preceding them and
274 their 'to' branch points to the pcode immediately
275 following them. A skip instruction is an example of
276 a pcode that has multiple (in this case two) elements
277 in the 'to' branch. A 'label' pcode is an where there
278 may be multiple 'from' branches.
279 *************************************************/
281 typedef struct pBranch
283 struct pCode *pc; // Next pCode in a branch
284 struct pBranch *next; /* If more than one branch
285 * the next one is here */
289 /*************************************************
292 pCode Operand structure.
293 For those assembly instructions that have arguments,
294 the pCode will have a pCodeOp in which the argument
295 can be stored. For example
299 'some_register' will be stored/referenced in a pCodeOp
301 *************************************************/
303 typedef struct pCodeOp
310 typedef struct pCodeOpBit
314 unsigned int inBitSpace: 1; /* True if in bit space, else
315 just a bit of a register */
318 typedef struct pCodeOpLit
324 typedef struct pCodeOpImmd
327 int offset; /* low,med, or high byte of immediate value */
328 int index; /* add this to the immediate value */
329 unsigned _const:1; /* is in code space */
330 unsigned _function:1; /* is a (pointer to a) function */
332 int rIdx; /* If this immd points to a register */
333 struct regs *r; /* then this is the reg. */
337 typedef struct pCodeOpLabel
341 int offset; /* low or high byte of label */
344 typedef struct pCodeOpReg
346 pCodeOp pcop; // Can be either GPR or SFR
347 int rIdx; // Index into the register table
349 int instance; // byte # of Multi-byte registers
353 typedef struct pCodeOpRegBit
355 pCodeOpReg pcor; // The Register containing this bit
356 int bit; // 0-7 bit number.
357 PIC_OPTYPE subtype; // The type of this register.
358 unsigned int inBitSpace: 1; /* True if in bit space, else
359 just a bit of a register */
363 typedef struct pCodeOpRegPtr
365 pCodeOpReg pcor; // The Register containing this bit
367 // PIC_OPTYPE subtype; // The type of this register.
368 // unsigned int inBitSpace: 1; /* True if in bit space, else
372 typedef struct pCodeOpStr /* Only used here for the name of fn being called or jumped to */
375 unsigned isPublic: 1; /* True if not static ie extern */
378 typedef struct pCodeOpWild
382 struct pCodeWildBlock *pcwb;
384 int id; /* index into an array of char *'s that will match
385 * the wild card. The array is in *pcp. */
386 pCodeOp *subtype; /* Pointer to the Operand type into which this wild
387 * card will be expanded */
388 pCodeOp *matched; /* When a wild matches, we'll store a pointer to the
389 * opcode we matched */
394 /*************************************************
397 Here is the basic build block of a PIC instruction.
398 Each pic instruction will get allocated a pCode.
399 A linked list of pCodes makes a program.
401 **************************************************/
407 struct pCode *prev; // The pCode objects are linked together
408 struct pCode *next; // in doubly linked lists.
410 unsigned id; // unique ID number for all pCodes to assist in debugging
411 int seq; // sequence number
413 struct pBlock *pb; // The pBlock that contains this pCode.
415 /* "virtual functions"
416 * The pCode structure is like a base class
417 * in C++. The subsequent structures that "inherit"
418 * the pCode structure will initialize these function
419 * pointers to something useful */
420 // void (*analyze) (struct pCode *_this);
421 void (*destruct)(struct pCode *_this);
422 void (*print) (FILE *of,struct pCode *_this);
427 /*************************************************
429 **************************************************/
431 typedef struct pCodeComment
441 /*************************************************
443 **************************************************/
445 typedef struct pCodeCSource
457 /*************************************************
460 The Flow object is used as marker to separate
461 the assembly code into contiguous chunks. In other
462 words, everytime an instruction cause or potentially
463 causes a branch, a Flow object will be inserted into
464 the pCode chain to mark the beginning of the next
467 **************************************************/
469 typedef struct pCodeFlow
474 pCode *end; /* Last pCode in this flow. Note that
475 the first pCode is pc.next */
477 /* set **uses; * map the pCode instruction inCond and outCond conditions
478 * in this array of set's. The reason we allocate an
479 * array of pointers instead of declaring each type of
480 * usage is because there are port dependent usage definitions */
481 //int nuses; /* number of uses sets */
483 set *from; /* flow blocks that can send control to this flow block */
484 set *to; /* flow blocks to which this one can send control */
485 struct pCodeFlow *ancestor; /* The most immediate "single" pCodeFlow object that
486 * executes prior to this one. In many cases, this
487 * will be just the previous */
489 int inCond; /* Input conditions - stuff assumed defined at entry */
490 int outCond; /* Output conditions - stuff modified by flow block */
492 int firstBank; /* The first and last bank flags are the first and last */
493 int lastBank; /* register banks used within one flow object */
498 set *registers;/* Registers used in this flow */
503 /*************************************************
506 The Flow Link object is used to record information
507 about how consecutive excutive Flow objects are related.
508 The pCodeFlow objects demarcate the pCodeInstructions
509 into contiguous chunks. The FlowLink records conflicts
510 in the discontinuities. For example, if one Flow object
511 references a register in bank 0 and the next Flow object
512 references a register in bank 1, then there is a discontinuity
513 in the banking registers.
516 typedef struct pCodeFlowLink
518 pCodeFlow *pcflow; /* pointer to linked pCodeFlow object */
520 int bank_conflict; /* records bank conflicts */
525 /*************************************************
528 Here we describe all the facets of a PIC instruction
529 (expansion for the 18cxxx is also provided).
531 **************************************************/
533 typedef struct pCodeInstruction
538 PIC_OPCODE op; // The opcode of the instruction.
540 char const * const mnemonic; // Pointer to mnemonic string
542 pBranch *from; // pCodes that execute before this one
543 pBranch *to; // pCodes that execute after
544 pBranch *label; // pCode instructions that have labels
546 pCodeOp *pcop; /* Operand, if this instruction has one */
547 pCodeFlow *pcflow; /* flow block to which this instruction belongs */
548 pCodeCSource *cline; /* C Source from which this instruction was derived */
550 unsigned int num_ops; /* Number of operands (0,1,2 for mid range pics) */
551 unsigned int isModReg: 1; /* If destination is W or F, then 1==F */
552 unsigned int isBitInst: 1; /* e.g. BCF */
553 unsigned int isBranch: 1; /* True if this is a branching instruction */
554 unsigned int isSkip: 1; /* True if this is a skip instruction */
555 unsigned int isLit: 1; /* True if this instruction has an literal operand */
557 PIC_OPCODE inverted_op; /* Opcode of instruction that's the opposite of this one */
558 unsigned int inCond; // Input conditions for this instruction
559 unsigned int outCond; // Output conditions for this instruction
564 /*************************************************
566 **************************************************/
568 typedef struct pCodeAsmDir
570 pCodeInstruction pci;
577 /*************************************************
579 **************************************************/
581 typedef struct pCodeLabel
592 /*************************************************
594 **************************************************/
596 typedef struct pCodeFunction
602 char *fname; /* If NULL, then this is the end of
603 a function. Otherwise, it's the
604 start and the name is contained
607 pBranch *from; // pCodes that execute before this one
608 pBranch *to; // pCodes that execute after
609 pBranch *label; // pCode instructions that have labels
611 int ncalled; /* Number of times function is called */
612 unsigned isPublic:1; /* True if the fn is not static and can be called from another module (ie a another c or asm file) */
617 /*************************************************
619 **************************************************/
621 typedef struct pCodeWild
624 pCodeInstruction pci;
626 int id; /* Index into the wild card array of a peepBlock
627 * - this wild card will get expanded into that pCode
628 * that is stored at this index */
630 /* Conditions on wild pcode instruction */
631 int mustBeBitSkipInst:1;
632 int mustNotBeBitSkipInst:1;
633 int invertBitSkipInst:1;
635 pCodeOp *operand; // Optional operand
636 pCodeOp *label; // Optional label
640 /*************************************************
643 Here are PIC program snippets. There's a strong
644 correlation between the eBBlocks and pBlocks.
645 SDCC subdivides a C program into managable chunks.
646 Each chunk becomes a eBBlock and ultimately in the
649 **************************************************/
651 typedef struct pBlock
653 memmap *cmemmap; /* The snippet is from this memmap */
654 char dbName; /* if cmemmap is NULL, then dbName will identify the block */
655 pCode *pcHead; /* A pointer to the first pCode in a link list of pCodes */
656 pCode *pcTail; /* A pointer to the last pCode in a link list of pCodes */
658 struct pBlock *next; /* The pBlocks will form a doubly linked list */
661 set *function_entries; /* dll of functions in this pblock */
667 unsigned visited:1; /* set true if traversed in call tree */
669 unsigned seq; /* sequence number of this pBlock */
673 /*************************************************
676 The collection of pBlock program snippets are
677 placed into a linked list that is implemented
678 in the pFile structure.
680 The pcode optimizer will parse the pFile.
682 **************************************************/
686 pBlock *pbHead; /* A pointer to the first pBlock */
687 pBlock *pbTail; /* A pointer to the last pBlock */
689 pBranch *functions; /* A SLL of functions in this pFile */
695 /*************************************************
698 The pCodeWildBlock object keeps track of the wild
699 variables, operands, and opcodes that exist in
701 **************************************************/
702 typedef struct pCodeWildBlock {
704 struct pCodePeep *pcp; // pointer back to ... I don't like this...
706 int nvars; // Number of wildcard registers in target.
707 char **vars; // array of pointers to them
709 int nops; // Number of wildcard operands in target.
710 pCodeOp **wildpCodeOps; // array of pointers to the pCodeOp's.
712 int nwildpCodes; // Number of wildcard pCodes in target/replace
713 pCode **wildpCodes; // array of pointers to the pCode's.
717 /*************************************************
720 The pCodePeep object mimics the peep hole optimizer
721 in the main SDCC src (e.g. SDCCpeeph.c). Essentially
722 there is a target pCode chain and a replacement
723 pCode chain. The target chain is compared to the
724 pCode that is generated by gen.c. If a match is
725 found then the pCode is replaced by the replacement
727 **************************************************/
728 typedef struct pCodePeep {
729 pCodeWildBlock target; // code we'd like to optimize
730 pCodeWildBlock replace; // and this is what we'll optimize it with.
733 //pBlock replace; // and this is what we'll optimize it with.
737 /* (Note: a wildcard register is a place holder. Any register
738 * can be replaced by the wildcard when the pcode is being
739 * compared to the target. */
741 /* Post Conditions. A post condition is a condition that
742 * must be either true or false before the peep rule is
743 * accepted. For example, a certain rule may be accepted
744 * if and only if the Z-bit is not used as an input to
745 * the subsequent instructions in a pCode chain.
747 unsigned int postFalseCond;
748 unsigned int postTrueCond;
752 /*************************************************
754 pCode peep command definitions
756 Here are some special commands that control the
757 way the peep hole optimizer behaves
759 **************************************************/
761 enum peepCommandTypes{
768 /*************************************************
769 peepCommand structure stores the peep commands.
771 **************************************************/
773 typedef struct peepCommand {
778 /*************************************************
781 **************************************************/
782 #define PCODE(x) ((pCode *)(x))
783 #define PCI(x) ((pCodeInstruction *)(x))
784 #define PCL(x) ((pCodeLabel *)(x))
785 #define PCF(x) ((pCodeFunction *)(x))
786 #define PCFL(x) ((pCodeFlow *)(x))
787 #define PCFLINK(x)((pCodeFlowLink *)(x))
788 #define PCW(x) ((pCodeWild *)(x))
789 #define PCCS(x) ((pCodeCSource *)(x))
790 #define PCAD(x) ((pCodeAsmDir *)(x))
792 #define PCOP(x) ((pCodeOp *)(x))
793 //#define PCOB(x) ((pCodeOpBit *)(x))
794 #define PCOL(x) ((pCodeOpLit *)(x))
795 #define PCOI(x) ((pCodeOpImmd *)(x))
796 #define PCOLAB(x) ((pCodeOpLabel *)(x))
797 #define PCOR(x) ((pCodeOpReg *)(x))
798 #define PCORB(x) ((pCodeOpRegBit *)(x))
799 #define PCOS(x) ((pCodeOpStr *)(x))
800 #define PCOW(x) ((pCodeOpWild *)(x))
802 #define PBR(x) ((pBranch *)(x))
804 #define PCWB(x) ((pCodeWildBlock *)(x))
806 #define isPCOLAB(x) ((PCOP(x)->type) == PO_LABEL)
807 #define isPCOS(x) ((PCOP(x)->type) == PO_STR)
811 macros for checking pCode types
813 #define isPCI(x) ((PCODE(x)->type == PC_OPCODE))
814 #define isPCFL(x) ((PCODE(x)->type == PC_FLOW))
815 #define isPCF(x) ((PCODE(x)->type == PC_FUNCTION))
816 #define isPCL(x) ((PCODE(x)->type == PC_LABEL))
817 #define isPCW(x) ((PCODE(x)->type == PC_WILD))
818 #define isPCCS(x) ((PCODE(x)->type == PC_CSOURCE))
819 #define isPCASMDIR(x) ((PCODE(x)->type == PC_ASMDIR))
822 macros for checking pCodeInstruction types
824 #define isCALL(x) (isPCI(x) && (PCI(x)->op == POC_CALL))
825 #define isPCI_BRANCH(x) (isPCI(x) && PCI(x)->isBranch)
826 #define isPCI_SKIP(x) (isPCI(x) && PCI(x)->isSkip)
827 #define isPCI_LIT(x) (isPCI(x) && PCI(x)->isLit)
828 #define isPCI_BITSKIP(x)(isPCI_SKIP(x) && PCI(x)->isBitInst)
831 #define isSTATUS_REG(r) ((r)->pc_type == PO_STATUS)
833 /*-----------------------------------------------------------------*
835 *-----------------------------------------------------------------*/
837 pCode *newpCode (PIC_OPCODE op, pCodeOp *pcop); // Create a new pCode given an operand
838 pCode *newpCodeCharP(char *cP); // Create a new pCode given a char *
839 pCode *newpCodeFunction(char *g, char *f,int); // Create a new function
840 pCode *newpCodeLabel(char *name,int key); // Create a new label given a key
841 pCode *newpCodeCSource(int ln, char *f, const char *l); // Create a new symbol line
842 pCode *newpCodeWild(int pCodeID, pCodeOp *optional_operand, pCodeOp *optional_label);
843 pCode *findNextInstruction(pCode *pci);
844 pCode *findPrevInstruction(pCode *pci);
845 pCode *findNextpCode(pCode *pc, PC_TYPE pct);
846 pCode *pCodeInstructionCopy(pCodeInstruction *pci,int invert);
848 pBlock *newpCodeChain(memmap *cm,char c, pCode *pc); // Create a new pBlock
849 void printpBlock(FILE *of, pBlock *pb); // Write a pBlock to a file
850 void printpCode(FILE *of, pCode *pc); // Write a pCode to a file
851 void addpCode2pBlock(pBlock *pb, pCode *pc); // Add a pCode to a pBlock
852 void addpBlock(pBlock *pb); // Add a pBlock to a pFile
853 void unlinkpCode(pCode *pc);
854 void copypCode(FILE *of, char dbName); // Write all pBlocks with dbName to *of
855 void movepBlock2Head(char dbName); // move pBlocks around
856 void AnalyzeBanking(void);
858 void AnalyzepCode(char dbName);
859 void InlinepCode(void);
860 void pCodeInitRegisters(void);
861 void pic14initpCodePeepCommands(void);
862 void pBlockConvert2ISR(pBlock *pb);
863 void pBlockMergeLabels(pBlock *pb);
864 void pCodeInsertAfter(pCode *pc1, pCode *pc2);
865 void pCodeInsertBefore(pCode *pc1, pCode *pc2);
866 void pCodeDeleteChain(pCode *f,pCode *t);
868 pCode *newpCodeAsmDir(char *asdir, char *argfmt, ...);
870 pCodeOp *newpCodeOpLabel(char *name, int key);
871 pCodeOp *newpCodeOpImmd(char *name, int offset, int index, int code_space,int is_func);
872 pCodeOp *newpCodeOpLit(int lit);
873 pCodeOp *newpCodeOpBit(char *name, int bit,int inBitSpace);
874 pCodeOp *newpCodeOpWild(int id, pCodeWildBlock *pcwb, pCodeOp *subtype);
875 pCodeOp *newpCodeOpRegFromStr(char *name);
876 pCodeOp *newpCodeOp(char *name, PIC_OPTYPE p);
877 pCodeOp *pCodeOpCopy(pCodeOp *pcop);
878 pCodeOp *popCopyGPR2Bit(pCodeOp *pc, int bitval);
879 pCodeOp *popCopyReg(pCodeOpReg *pc);
881 pBranch *pBranchAppend(pBranch *h, pBranch *n);
883 struct regs * getRegFromInstruction(pCode *pc);
885 char *get_op(pCodeOp *pcop, char *buff, size_t buf_size);
886 char *pCode2str(char *str, size_t size, pCode *pc);
888 int pCodePeepMatchRule(pCode *pc);
890 void pcode_test(void);
891 void resetpCodeStatistics (void);
892 void dumppCodeStatistics (FILE *of);
894 /*-----------------------------------------------------------------*
896 *-----------------------------------------------------------------*/
898 extern pCodeOpReg pc_status;
899 extern pCodeOpReg pc_intcon;
900 extern pCodeOpReg pc_indf;
901 extern pCodeOpReg pc_fsr;
902 extern pCodeOpReg pc_pcl;
903 extern pCodeOpReg pc_pclath;
904 extern pCodeOpReg pc_wsave; /* wsave, ssave and psave are used to save W, the Status and PCLATH*/
905 extern pCodeOpReg pc_ssave; /* registers during an interrupt */
906 extern pCodeOpReg pc_psave; /* registers during an interrupt */
908 extern pFile *the_pFile;
909 extern pCodeInstruction *pic14Mnemonics[MAX_PIC14MNEMONICS];
914 int getpCode(char *mnem, unsigned dest);
915 int getpCodePeepCommand(char *cmd);
916 int pCodeSearchCondition(pCode *pc, unsigned int cond, int contIfSkip);
918 #endif // __PCODE_H__