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 */
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_ASMDIR, /* Assembler directive */
246 PC_BAD /* Mark the pCode object as being bad */
249 /************************************************/
250 /*************** Structures ********************/
251 /************************************************/
252 /* These are here as forward references - the
253 * full definition of these are below */
255 struct pCodeWildBlock;
256 struct pCodeRegLives;
258 /*************************************************
261 The first step in optimizing pCode is determining
262 the program flow. This information is stored in
263 single-linked lists in the for of 'from' and 'to'
264 objects with in a pcode. For example, most instructions
265 don't involve any branching. So their from branch
266 points to the pCode immediately preceding them and
267 their 'to' branch points to the pcode immediately
268 following them. A skip instruction is an example of
269 a pcode that has multiple (in this case two) elements
270 in the 'to' branch. A 'label' pcode is an where there
271 may be multiple 'from' branches.
272 *************************************************/
274 typedef struct pBranch
276 struct pCode *pc; // Next pCode in a branch
277 struct pBranch *next; /* If more than one branch
278 * the next one is here */
282 /*************************************************
285 pCode Operand structure.
286 For those assembly instructions that have arguments,
287 the pCode will have a pCodeOp in which the argument
288 can be stored. For example
292 'some_register' will be stored/referenced in a pCodeOp
294 *************************************************/
296 typedef struct pCodeOp
303 typedef struct pCodeOpLit
309 typedef struct pCodeOpImmd
312 int offset; /* low,med, or high byte of immediate value */
313 int index; /* add this to the immediate value */
314 unsigned _const:1; /* is in code space */
315 unsigned _function:1; /* is a (pointer to a) function */
317 int rIdx; /* If this immd points to a register */
318 struct regs *r; /* then this is the reg. */
322 typedef struct pCodeOpLabel
326 int offset; /* low or high byte of label */
329 typedef struct pCodeOpReg
331 pCodeOp pcop; // Can be either GPR or SFR
332 int rIdx; // Index into the register table
334 int instance; // byte # of Multi-byte registers
338 typedef struct pCodeOpRegBit
340 pCodeOpReg pcor; // The Register containing this bit
341 int bit; // 0-7 bit number.
342 PIC_OPTYPE subtype; // The type of this register.
343 unsigned int inBitSpace: 1; /* True if in bit space, else
344 just a bit of a register */
347 typedef struct pCodeOpStr /* Only used here for the name of fn being called or jumped to */
350 unsigned isPublic: 1; /* True if not static ie extern */
353 typedef struct pCodeOpWild
357 struct pCodeWildBlock *pcwb;
359 int id; /* index into an array of char *'s that will match
360 * the wild card. The array is in *pcp. */
361 pCodeOp *subtype; /* Pointer to the Operand type into which this wild
362 * card will be expanded */
363 pCodeOp *matched; /* When a wild matches, we'll store a pointer to the
364 * opcode we matched */
369 /*************************************************
372 Here is the basic build block of a PIC instruction.
373 Each pic instruction will get allocated a pCode.
374 A linked list of pCodes makes a program.
376 **************************************************/
382 struct pCode *prev; // The pCode objects are linked together
383 struct pCode *next; // in doubly linked lists.
385 unsigned id; // unique ID number for all pCodes to assist in debugging
386 int seq; // sequence number
388 struct pBlock *pb; // The pBlock that contains this pCode.
390 /* "virtual functions"
391 * The pCode structure is like a base class
392 * in C++. The subsequent structures that "inherit"
393 * the pCode structure will initialize these function
394 * pointers to something useful */
395 void (*destruct)(struct pCode *_this);
396 void (*print) (FILE *of,struct pCode *_this);
401 /*************************************************
403 **************************************************/
405 typedef struct pCodeComment
415 /*************************************************
417 **************************************************/
419 typedef struct pCodeCSource
431 /*************************************************
434 The Flow object is used as marker to separate
435 the assembly code into contiguous chunks. In other
436 words, everytime an instruction cause or potentially
437 causes a branch, a Flow object will be inserted into
438 the pCode chain to mark the beginning of the next
441 **************************************************/
443 typedef struct pCodeFlow
448 pCode *end; /* Last pCode in this flow. Note that
449 the first pCode is pc.next */
451 set *from; /* flow blocks that can send control to this flow block */
452 set *to; /* flow blocks to which this one can send control */
453 struct pCodeFlow *ancestor; /* The most immediate "single" pCodeFlow object that
454 * executes prior to this one. In many cases, this
455 * will be just the previous */
457 int inCond; /* Input conditions - stuff assumed defined at entry */
458 int outCond; /* Output conditions - stuff modified by flow block */
460 int firstBank; /* The first and last bank flags are the first and last */
461 int lastBank; /* register banks used within one flow object */
466 set *registers;/* Registers used in this flow */
471 /*************************************************
474 The Flow Link object is used to record information
475 about how consecutive excutive Flow objects are related.
476 The pCodeFlow objects demarcate the pCodeInstructions
477 into contiguous chunks. The FlowLink records conflicts
478 in the discontinuities. For example, if one Flow object
479 references a register in bank 0 and the next Flow object
480 references a register in bank 1, then there is a discontinuity
481 in the banking registers.
484 typedef struct pCodeFlowLink
486 pCodeFlow *pcflow; /* pointer to linked pCodeFlow object */
488 int bank_conflict; /* records bank conflicts */
493 /*************************************************
496 Here we describe all the facets of a PIC instruction
497 (expansion for the 18cxxx is also provided).
499 **************************************************/
501 typedef struct pCodeInstruction
506 PIC_OPCODE op; // The opcode of the instruction.
508 char const * const mnemonic; // Pointer to mnemonic string
510 pBranch *from; // pCodes that execute before this one
511 pBranch *to; // pCodes that execute after
512 pBranch *label; // pCode instructions that have labels
514 pCodeOp *pcop; /* Operand, if this instruction has one */
515 pCodeFlow *pcflow; /* flow block to which this instruction belongs */
516 pCodeCSource *cline; /* C Source from which this instruction was derived */
518 unsigned int num_ops; /* Number of operands (0,1,2 for mid range pics) */
519 unsigned int isModReg: 1; /* If destination is W or F, then 1==F */
520 unsigned int isBitInst: 1; /* e.g. BCF */
521 unsigned int isBranch: 1; /* True if this is a branching instruction */
522 unsigned int isSkip: 1; /* True if this is a skip instruction */
523 unsigned int isLit: 1; /* True if this instruction has an literal operand */
525 PIC_OPCODE inverted_op; /* Opcode of instruction that's the opposite of this one */
526 unsigned int inCond; // Input conditions for this instruction
527 unsigned int outCond; // Output conditions for this instruction
532 /*************************************************
534 **************************************************/
536 typedef struct pCodeAsmDir
538 pCodeInstruction pci;
545 /*************************************************
547 **************************************************/
549 typedef struct pCodeLabel
560 /*************************************************
562 **************************************************/
564 typedef struct pCodeFunction
570 char *fname; /* If NULL, then this is the end of
571 a function. Otherwise, it's the
572 start and the name is contained
575 pBranch *from; // pCodes that execute before this one
576 pBranch *to; // pCodes that execute after
577 pBranch *label; // pCode instructions that have labels
579 int ncalled; /* Number of times function is called */
580 unsigned isPublic:1; /* True if the fn is not static and can be called from another module (ie a another c or asm file) */
585 /*************************************************
587 **************************************************/
589 typedef struct pCodeWild
592 pCodeInstruction pci;
594 int id; /* Index into the wild card array of a peepBlock
595 * - this wild card will get expanded into that pCode
596 * that is stored at this index */
598 /* Conditions on wild pcode instruction */
599 int mustBeBitSkipInst:1;
600 int mustNotBeBitSkipInst:1;
601 int invertBitSkipInst:1;
603 pCodeOp *operand; // Optional operand
604 pCodeOp *label; // Optional label
608 /*************************************************
611 Here are PIC program snippets. There's a strong
612 correlation between the eBBlocks and pBlocks.
613 SDCC subdivides a C program into managable chunks.
614 Each chunk becomes a eBBlock and ultimately in the
617 **************************************************/
619 typedef struct pBlock
621 memmap *cmemmap; /* The snippet is from this memmap */
622 char dbName; /* if cmemmap is NULL, then dbName will identify the block */
623 pCode *pcHead; /* A pointer to the first pCode in a link list of pCodes */
624 pCode *pcTail; /* A pointer to the last pCode in a link list of pCodes */
626 struct pBlock *next; /* The pBlocks will form a doubly linked list */
629 set *function_entries; /* dll of functions in this pblock */
635 unsigned visited:1; /* set true if traversed in call tree */
637 unsigned seq; /* sequence number of this pBlock */
641 /*************************************************
644 The collection of pBlock program snippets are
645 placed into a linked list that is implemented
646 in the pFile structure.
648 The pcode optimizer will parse the pFile.
650 **************************************************/
654 pBlock *pbHead; /* A pointer to the first pBlock */
655 pBlock *pbTail; /* A pointer to the last pBlock */
657 pBranch *functions; /* A SLL of functions in this pFile */
663 /*************************************************
666 The pCodeWildBlock object keeps track of the wild
667 variables, operands, and opcodes that exist in
669 **************************************************/
670 typedef struct pCodeWildBlock {
672 struct pCodePeep *pcp; // pointer back to ... I don't like this...
674 int nvars; // Number of wildcard registers in target.
675 char **vars; // array of pointers to them
677 int nops; // Number of wildcard operands in target.
678 pCodeOp **wildpCodeOps; // array of pointers to the pCodeOp's.
680 int nwildpCodes; // Number of wildcard pCodes in target/replace
681 pCode **wildpCodes; // array of pointers to the pCode's.
685 /*************************************************
688 The pCodePeep object mimics the peep hole optimizer
689 in the main SDCC src (e.g. SDCCpeeph.c). Essentially
690 there is a target pCode chain and a replacement
691 pCode chain. The target chain is compared to the
692 pCode that is generated by gen.c. If a match is
693 found then the pCode is replaced by the replacement
695 **************************************************/
696 typedef struct pCodePeep {
697 pCodeWildBlock target; // code we'd like to optimize
698 pCodeWildBlock replace; // and this is what we'll optimize it with.
700 /* (Note: a wildcard register is a place holder. Any register
701 * can be replaced by the wildcard when the pcode is being
702 * compared to the target. */
704 /* Post Conditions. A post condition is a condition that
705 * must be either true or false before the peep rule is
706 * accepted. For example, a certain rule may be accepted
707 * if and only if the Z-bit is not used as an input to
708 * the subsequent instructions in a pCode chain.
710 unsigned int postFalseCond;
711 unsigned int postTrueCond;
715 /*************************************************
717 pCode peep command definitions
719 Here are some special commands that control the
720 way the peep hole optimizer behaves
722 **************************************************/
724 enum peepCommandTypes{
731 /*************************************************
732 peepCommand structure stores the peep commands.
734 **************************************************/
736 typedef struct peepCommand {
741 /*************************************************
744 **************************************************/
745 #define PCODE(x) ((pCode *)(x))
746 #define PCI(x) ((pCodeInstruction *)(x))
747 #define PCL(x) ((pCodeLabel *)(x))
748 #define PCF(x) ((pCodeFunction *)(x))
749 #define PCFL(x) ((pCodeFlow *)(x))
750 #define PCFLINK(x)((pCodeFlowLink *)(x))
751 #define PCW(x) ((pCodeWild *)(x))
752 #define PCCS(x) ((pCodeCSource *)(x))
753 #define PCAD(x) ((pCodeAsmDir *)(x))
755 #define PCOP(x) ((pCodeOp *)(x))
756 #define PCOL(x) ((pCodeOpLit *)(x))
757 #define PCOI(x) ((pCodeOpImmd *)(x))
758 #define PCOLAB(x) ((pCodeOpLabel *)(x))
759 #define PCOR(x) ((pCodeOpReg *)(x))
760 #define PCORB(x) ((pCodeOpRegBit *)(x))
761 #define PCOS(x) ((pCodeOpStr *)(x))
762 #define PCOW(x) ((pCodeOpWild *)(x))
764 #define PBR(x) ((pBranch *)(x))
766 #define PCWB(x) ((pCodeWildBlock *)(x))
768 #define isPCOLAB(x) ((PCOP(x)->type) == PO_LABEL)
769 #define isPCOS(x) ((PCOP(x)->type) == PO_STR)
773 macros for checking pCode types
775 #define isPCI(x) ((PCODE(x)->type == PC_OPCODE))
776 #define isPCFL(x) ((PCODE(x)->type == PC_FLOW))
777 #define isPCF(x) ((PCODE(x)->type == PC_FUNCTION))
778 #define isPCL(x) ((PCODE(x)->type == PC_LABEL))
779 #define isPCW(x) ((PCODE(x)->type == PC_WILD))
780 #define isPCCS(x) ((PCODE(x)->type == PC_CSOURCE))
781 #define isPCASMDIR(x) ((PCODE(x)->type == PC_ASMDIR))
784 macros for checking pCodeInstruction types
786 #define isCALL(x) (isPCI(x) && (PCI(x)->op == POC_CALL))
787 #define isPCI_BRANCH(x) (isPCI(x) && PCI(x)->isBranch)
788 #define isPCI_SKIP(x) (isPCI(x) && PCI(x)->isSkip)
789 #define isPCI_LIT(x) (isPCI(x) && PCI(x)->isLit)
790 #define isPCI_BITSKIP(x)(isPCI_SKIP(x) && PCI(x)->isBitInst)
793 #define isSTATUS_REG(r) ((r)->pc_type == PO_STATUS)
795 /*-----------------------------------------------------------------*
797 *-----------------------------------------------------------------*/
799 pCode *newpCode (PIC_OPCODE op, pCodeOp *pcop); // Create a new pCode given an operand
800 pCode *newpCodeCharP(char *cP); // Create a new pCode given a char *
801 pCode *newpCodeFunction(char *g, char *f,int); // Create a new function
802 pCode *newpCodeLabel(char *name,int key); // Create a new label given a key
803 pCode *newpCodeCSource(int ln, char *f, const char *l); // Create a new symbol line
804 pCode *newpCodeWild(int pCodeID, pCodeOp *optional_operand, pCodeOp *optional_label);
805 pCode *findNextInstruction(pCode *pci);
806 pCode *findPrevInstruction(pCode *pci);
807 pCode *findNextpCode(pCode *pc, PC_TYPE pct);
808 pCode *pCodeInstructionCopy(pCodeInstruction *pci,int invert);
810 pBlock *newpCodeChain(memmap *cm,char c, pCode *pc); // Create a new pBlock
811 void printpBlock(FILE *of, pBlock *pb); // Write a pBlock to a file
812 void printpCode(FILE *of, pCode *pc); // Write a pCode to a file
813 void addpCode2pBlock(pBlock *pb, pCode *pc); // Add a pCode to a pBlock
814 void addpBlock(pBlock *pb); // Add a pBlock to a pFile
815 void unlinkpCode(pCode *pc);
816 void copypCode(FILE *of, char dbName); // Write all pBlocks with dbName to *of
817 void movepBlock2Head(char dbName); // move pBlocks around
818 void AnalyzeBanking(void);
820 void AnalyzepCode(char dbName);
821 void InlinepCode(void);
822 void pCodeInitRegisters(void);
823 void pic14initpCodePeepCommands(void);
824 void pBlockConvert2ISR(pBlock *pb);
825 void pBlockMergeLabels(pBlock *pb);
826 void pCodeInsertAfter(pCode *pc1, pCode *pc2);
827 void pCodeInsertBefore(pCode *pc1, pCode *pc2);
828 void pCodeDeleteChain(pCode *f,pCode *t);
830 pCode *newpCodeAsmDir(char *asdir, char *argfmt, ...);
832 pCodeOp *newpCodeOpLabel(char *name, int key);
833 pCodeOp *newpCodeOpImmd(char *name, int offset, int index, int code_space,int is_func);
834 pCodeOp *newpCodeOpLit(int lit);
835 pCodeOp *newpCodeOpBit(char *name, int bit,int inBitSpace);
836 pCodeOp *newpCodeOpWild(int id, pCodeWildBlock *pcwb, pCodeOp *subtype);
837 pCodeOp *newpCodeOpRegFromStr(char *name);
838 pCodeOp *newpCodeOp(char *name, PIC_OPTYPE p);
839 pCodeOp *pCodeOpCopy(pCodeOp *pcop);
840 pCodeOp *popCopyGPR2Bit(pCodeOp *pc, int bitval);
841 pCodeOp *popCopyReg(pCodeOpReg *pc);
843 pBranch *pBranchAppend(pBranch *h, pBranch *n);
845 struct regs * getRegFromInstruction(pCode *pc);
847 char *get_op(pCodeOp *pcop, char *buff, size_t buf_size);
848 char *pCode2str(char *str, size_t size, pCode *pc);
850 int pCodePeepMatchRule(pCode *pc);
852 void pcode_test(void);
853 void resetpCodeStatistics (void);
854 void dumppCodeStatistics (FILE *of);
856 /*-----------------------------------------------------------------*
858 *-----------------------------------------------------------------*/
860 extern pCodeOpReg pc_status;
861 extern pCodeOpReg pc_intcon;
862 extern pCodeOpReg pc_indf;
863 extern pCodeOpReg pc_fsr;
864 extern pCodeOpReg pc_pcl;
865 extern pCodeOpReg pc_pclath;
866 extern pCodeOpReg pc_wsave; /* wsave, ssave and psave are used to save W, the Status and PCLATH*/
867 extern pCodeOpReg pc_ssave; /* registers during an interrupt */
868 extern pCodeOpReg pc_psave; /* registers during an interrupt */
870 extern pFile *the_pFile;
871 extern pCodeInstruction *pic14Mnemonics[MAX_PIC14MNEMONICS];
876 int getpCode(char *mnem, unsigned dest);
877 int getpCodePeepCommand(char *cmd);
878 int pCodeSearchCondition(pCode *pc, unsigned int cond, int contIfSkip);
880 #endif // __PCODE_H__