1 /*-------------------------------------------------------------------------
3 pcode.h - post code generation
4 Written By - Scott Dattalo scott@dattalo.com
6 This program is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software
18 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
20 -------------------------------------------------------------------------*/
28 The post code generation is an assembler optimizer. The assembly code
29 produced by all of the previous steps is fully functional. This step
30 will attempt to analyze the flow of the assembly code and agressively
31 optimize it. The peep hole optimizer attempts to do the same thing.
32 As you may recall, the peep hole optimizer replaces blocks of assembly
33 with more optimal blocks (e.g. removing redundant register loads).
34 However, the peep hole optimizer has to be somewhat conservative since
35 an assembly program has implicit state information that's unavailable
36 when only a few instructions are examined.
37 Consider this example:
43 The movf seems redundant since we know that the W register already
44 contains the same value of t1. So a peep hole optimizer is tempted to
45 remove the "movf". However, this is dangerous since the movf affects
46 the flags in the status register (specifically the Z flag) and subsequent
47 code may depend upon this. Look at these two examples:
51 movf t1,w ; Can't remove this movf
57 movf t1,w ; This movf can be removed
58 xorwf t2,w ; since xorwf will over write Z
68 /***********************************************************************
71 * The DFPRINTF macro will call fprintf if PCODE_DEBUG is defined.
72 * The macro is used like:
74 * DPRINTF(("%s #%d\n","test", 1));
76 * The double parenthesis (()) are necessary
78 ***********************************************************************/
82 #define DFPRINTF(args) (fprintf args)
84 #define DFPRINTF(args) ;
88 /***********************************************************************
89 * PIC status bits - this will move into device dependent headers
90 ***********************************************************************/
94 #define PIC_RP0_BIT 5 /* Register Bank select bits RP1:0 : */
95 #define PIC_RP1_BIT 6 /* 00 - bank 0, 01 - bank 1, 10 - bank 2, 11 - bank 3 */
96 #define PIC_IRP_BIT 7 /* Indirect register page select */
98 /***********************************************************************
99 * PIC INTCON bits - this will move into device dependent headers
100 ***********************************************************************/
101 #define PIC_RBIF_BIT 0 /* Port B level has changed flag */
102 #define PIC_INTF_BIT 1 /* Port B bit 0 interrupt on edge flag */
103 #define PIC_T0IF_BIT 2 /* TMR0 has overflowed flag */
104 #define PIC_RBIE_BIT 3 /* Port B level has changed - Interrupt Enable */
105 #define PIC_INTE_BIT 4 /* Port B bit 0 interrupt on edge - Int Enable */
106 #define PIC_T0IE_BIT 5 /* TMR0 overflow Interrupt Enable */
107 #define PIC_PIE_BIT 6 /* Peripheral Interrupt Enable */
108 #define PIC_GIE_BIT 7 /* Global Interrupt Enable */
110 /***********************************************************************
112 ***********************************************************************/
118 /***********************************************************************
120 * PIC_OPTYPE - Operand types that are specific to the PIC architecture
122 * If a PIC assembly instruction has an operand then here is where we
123 * associate a type to it. For example,
127 * The movf has two operands: 'reg' and the W register. 'reg' is some
128 * arbitrary general purpose register, hence it has the type PO_GPR_REGISTER.
129 * The W register, which is the PIC's accumulator, has the type PO_W.
131 ***********************************************************************/
137 PO_NONE=0, // No operand e.g. NOP
138 PO_W, // The 'W' register
139 PO_STATUS, // The 'STATUS' register
140 PO_FSR, // The "file select register" (in 18c it's one of three)
141 PO_INDF, // The Indirect register
142 PO_INTCON, // Interrupt Control register
143 PO_GPR_REGISTER, // A general purpose register
144 PO_GPR_BIT, // A bit of a general purpose register
145 PO_GPR_TEMP, // A general purpose temporary register
146 PO_SFR_REGISTER, // A special function register (e.g. PORTA)
147 PO_PCL, // Program counter Low register
148 PO_PCLATH, // Program counter Latch high register
149 PO_LITERAL, // A constant
150 PO_IMMEDIATE, // (8051 legacy)
151 PO_DIR, // Direct memory (8051 legacy)
152 PO_CRY, // bit memory (8051 legacy)
153 PO_BIT, // bit operand.
154 PO_STR, // (8051 legacy)
156 PO_WILD // Wild card operand in peep optimizer
160 /***********************************************************************
164 * This is not a list of the PIC's opcodes per se, but instead
165 * an enumeration of all of the different types of pic opcodes.
167 ***********************************************************************/
171 POC_WILD=-1, /* Wild card - used in the pCode peep hole optimizer
172 * to represent ANY pic opcode */
224 /***********************************************************************
225 * PC_TYPE - pCode Types
226 ***********************************************************************/
230 PC_COMMENT=0, /* pCode is a comment */
231 PC_INLINE, /* user's inline code */
232 PC_OPCODE, /* PORT dependent opcode */
233 PC_LABEL, /* assembly label */
234 PC_FLOW, /* flow analysis */
235 PC_FUNCTION, /* Function start or end */
236 PC_WILD, /* wildcard - an opcode place holder used
237 * in the pCode peep hole optimizer */
238 PC_CSOURCE, /* C-Source Line */
239 PC_BAD /* Mark the pCode object as being bad */
242 /************************************************/
243 /*************** Structures ********************/
244 /************************************************/
245 /* These are here as forward references - the
246 * full definition of these are below */
248 struct pCodeWildBlock;
249 struct pCodeRegLives;
251 /*************************************************
254 The first step in optimizing pCode is determining
255 the program flow. This information is stored in
256 single-linked lists in the for of 'from' and 'to'
257 objects with in a pcode. For example, most instructions
258 don't involve any branching. So their from branch
259 points to the pCode immediately preceding them and
260 their 'to' branch points to the pcode immediately
261 following them. A skip instruction is an example of
262 a pcode that has multiple (in this case two) elements
263 in the 'to' branch. A 'label' pcode is an where there
264 may be multiple 'from' branches.
265 *************************************************/
267 typedef struct pBranch
269 struct pCode *pc; // Next pCode in a branch
270 struct pBranch *next; /* If more than one branch
271 * the next one is here */
275 /*************************************************
278 pCode Operand structure.
279 For those assembly instructions that have arguments,
280 the pCode will have a pCodeOp in which the argument
281 can be stored. For example
285 'some_register' will be stored/referenced in a pCodeOp
287 *************************************************/
289 typedef struct pCodeOp
296 typedef struct pCodeOpBit
300 unsigned int inBitSpace: 1; /* True if in bit space, else
301 just a bit of a register */
304 typedef struct pCodeOpLit
310 typedef struct pCodeOpImmd
313 int offset; /* low,med, or high byte of immediat value */
314 int index; /* add this to the immediate value */
315 unsigned _const:1; /* is in code space */
319 typedef struct pCodeOpLabel
325 typedef struct pCodeOpReg
327 pCodeOp pcop; // Can be either GPR or SFR
328 int rIdx; // Index into the register table
330 int instance; // byte # of Multi-byte registers
334 typedef struct pCodeOpRegBit
336 pCodeOpReg pcor; // The Register containing this bit
337 int bit; // 0-7 bit number.
338 PIC_OPTYPE subtype; // The type of this register.
339 unsigned int inBitSpace: 1; /* True if in bit space, else
340 just a bit of a register */
344 typedef struct pCodeOpWild
348 struct pCodeWildBlock *pcwb;
350 int id; /* index into an array of char *'s that will match
351 * the wild card. The array is in *pcp. */
352 pCodeOp *subtype; /* Pointer to the Operand type into which this wild
353 * card will be expanded */
354 pCodeOp *matched; /* When a wild matches, we'll store a pointer to the
355 * opcode we matched */
360 /*************************************************
363 Here is the basic build block of a PIC instruction.
364 Each pic instruction will get allocated a pCode.
365 A linked list of pCodes makes a program.
367 **************************************************/
373 struct pCode *prev; // The pCode objects are linked together
374 struct pCode *next; // in doubly linked lists.
376 int seq; // sequence number
378 struct pBlock *pb; // The pBlock that contains this pCode.
380 /* "virtual functions"
381 * The pCode structure is like a base class
382 * in C++. The subsequent structures that "inherit"
383 * the pCode structure will initialize these function
384 * pointers to something useful */
385 // void (*analyze) (struct pCode *_this);
386 void (*destruct)(struct pCode *_this);
387 void (*print) (FILE *of,struct pCode *_this);
392 /*************************************************
394 **************************************************/
396 typedef struct pCodeComment
405 /*************************************************
407 **************************************************/
409 typedef struct pCodeCSource
421 /*************************************************
424 The Flow object is used as marker to separate
425 the assembly code into contiguous chunks. In other
426 words, everytime an instruction cause or potentially
427 causes a branch, a Flow object will be inserted into
428 the pCode chain to mark the beginning of the next
431 **************************************************/
433 typedef struct pCodeFlow
438 pCode *end; /* Last pCode in this flow. Note that
439 the first pCode is pc.next */
441 set **uses; /* map the pCode instruction inCond and outCond conditions
442 * in this array of set's. The reason we allocate an
443 * array of pointers instead of declaring each type of
444 * usage is because there are port dependent usage definitions */
445 int nuses; /* number of uses sets */
447 set *from; /* flow blocks that can send control to this flow block */
448 set *to; /* flow blocks to which this one can send control */
450 int inCond; /* Input conditions - stuff assumed defined at entry */
451 int outCond; /* Output conditions - stuff modified by flow block */
453 int firstBank; /* The first and last bank flags are the first and last */
454 int lastBank; /* register banks used within one flow object */
459 set *registers;/* Registers used in this flow */
463 /*************************************************
466 The Flow Link object is used to record information
467 about how consecutive excutive Flow objects are related.
468 The pCodeFlow objects demarcate the pCodeInstructions
469 into contiguous chunks. The FlowLink records conflicts
470 in the discontinuities. For example, if one Flow object
471 references a register in bank 0 and the next Flow object
472 references a register in bank 1, then there is a discontinuity
473 in the banking registers.
476 typedef struct pCodeFlowLink
478 pCodeFlow *pcflow; /* pointer to linked pCodeFlow object */
480 int bank_conflict; /* records bank conflicts */
484 /*************************************************
487 Here we describe all the facets of a PIC instruction
488 (expansion for the 18cxxx is also provided).
490 **************************************************/
492 typedef struct pCodeInstruction
497 PIC_OPCODE op; // The opcode of the instruction.
499 char const * const mnemonic; // Pointer to mnemonic string
501 pBranch *from; // pCodes that execute before this one
502 pBranch *to; // pCodes that execute after
503 pBranch *label; // pCode instructions that have labels
505 pCodeOp *pcop; /* Operand, if this instruction has one */
506 pCodeFlow *pcflow; /* flow block to which this instruction belongs */
507 pCodeCSource *cline; /* C Source from which this instruction was derived */
509 unsigned int num_ops; /* Number of operands (0,1,2 for mid range pics) */
510 unsigned int isModReg: 1; /* If destination is W or F, then 1==F */
511 unsigned int isBitInst: 1; /* e.g. BCF */
512 unsigned int isBranch: 1; /* True if this is a branching instruction */
513 unsigned int isSkip: 1; /* True if this is a skip instruction */
515 PIC_OPCODE inverted_op; /* Opcode of instruction that's the opposite of this one */
516 unsigned int inCond; // Input conditions for this instruction
517 unsigned int outCond; // Output conditions for this instruction
522 /*************************************************
524 **************************************************/
526 typedef struct pCodeLabel
536 /*************************************************
538 **************************************************/
540 typedef struct pCodeFunction
546 char *fname; /* If NULL, then this is the end of
547 a function. Otherwise, it's the
548 start and the name is contained
551 pBranch *from; // pCodes that execute before this one
552 pBranch *to; // pCodes that execute after
553 pBranch *label; // pCode instructions that have labels
555 int ncalled; /* Number of times function is called */
560 /*************************************************
562 **************************************************/
564 typedef struct pCodeWild
567 pCodeInstruction pci;
569 int id; /* Index into the wild card array of a peepBlock
570 * - this wild card will get expanded into that pCode
571 * that is stored at this index */
573 /* Conditions on wild pcode instruction */
574 int mustBeBitSkipInst:1;
575 int mustNotBeBitSkipInst:1;
576 int invertBitSkipInst:1;
578 pCodeOp *operand; // Optional operand
579 pCodeOp *label; // Optional label
583 /*************************************************
586 Here are PIC program snippets. There's a strong
587 correlation between the eBBlocks and pBlocks.
588 SDCC subdivides a C program into managable chunks.
589 Each chunk becomes a eBBlock and ultimately in the
592 **************************************************/
594 typedef struct pBlock
596 memmap *cmemmap; /* The snippet is from this memmap */
597 char dbName; /* if cmemmap is NULL, then dbName will identify the block */
598 pCode *pcHead; /* A pointer to the first pCode in a link list of pCodes */
599 pCode *pcTail; /* A pointer to the last pCode in a link list of pCodes */
601 struct pBlock *next; /* The pBlocks will form a doubly linked list */
604 set *function_entries; /* dll of functions in this pblock */
610 unsigned visited:1; /* set true if traversed in call tree */
612 unsigned seq; /* sequence number of this pBlock */
616 /*************************************************
619 The collection of pBlock program snippets are
620 placed into a linked list that is implemented
621 in the pFile structure.
623 The pcode optimizer will parse the pFile.
625 **************************************************/
629 pBlock *pbHead; /* A pointer to the first pBlock */
630 pBlock *pbTail; /* A pointer to the last pBlock */
632 pBranch *functions; /* A SLL of functions in this pFile */
638 /*************************************************
641 The pCodeWildBlock object keeps track of the wild
642 variables, operands, and opcodes that exist in
644 **************************************************/
645 typedef struct pCodeWildBlock {
647 struct pCodePeep *pcp; // pointer back to ... I don't like this...
649 int nvars; // Number of wildcard registers in target.
650 char **vars; // array of pointers to them
652 int nops; // Number of wildcard operands in target.
653 pCodeOp **wildpCodeOps; // array of pointers to the pCodeOp's.
655 int nwildpCodes; // Number of wildcard pCodes in target/replace
656 pCode **wildpCodes; // array of pointers to the pCode's.
660 /*************************************************
663 The pCodePeep object mimics the peep hole optimizer
664 in the main SDCC src (e.g. SDCCpeeph.c). Essentially
665 there is a target pCode chain and a replacement
666 pCode chain. The target chain is compared to the
667 pCode that is generated by gen.c. If a match is
668 found then the pCode is replaced by the replacement
670 **************************************************/
671 typedef struct pCodePeep {
672 pCodeWildBlock target; // code we'd like to optimize
673 pCodeWildBlock replace; // and this is what we'll optimize it with.
676 //pBlock replace; // and this is what we'll optimize it with.
680 /* (Note: a wildcard register is a place holder. Any register
681 * can be replaced by the wildcard when the pcode is being
682 * compared to the target. */
684 /* Post Conditions. A post condition is a condition that
685 * must be either true or false before the peep rule is
686 * accepted. For example, a certain rule may be accepted
687 * if and only if the Z-bit is not used as an input to
688 * the subsequent instructions in a pCode chain.
690 unsigned int postFalseCond;
691 unsigned int postTrueCond;
695 /*************************************************
697 pCode peep command definitions
699 Here are some special commands that control the
700 way the peep hole optimizer behaves
702 **************************************************/
704 enum peepCommandTypes{
711 /*************************************************
712 peepCommand structure stores the peep commands.
714 **************************************************/
716 typedef struct peepCommand {
721 /*************************************************
724 **************************************************/
725 #define PCODE(x) ((pCode *)(x))
726 #define PCI(x) ((pCodeInstruction *)(x))
727 #define PCL(x) ((pCodeLabel *)(x))
728 #define PCF(x) ((pCodeFunction *)(x))
729 #define PCFL(x) ((pCodeFlow *)(x))
730 #define PCW(x) ((pCodeWild *)(x))
731 #define PCCS(x) ((pCodeCSource *)(x))
733 #define PCOP(x) ((pCodeOp *)(x))
734 //#define PCOB(x) ((pCodeOpBit *)(x))
735 #define PCOL(x) ((pCodeOpLit *)(x))
736 #define PCOI(x) ((pCodeOpImmd *)(x))
737 #define PCOLAB(x) ((pCodeOpLabel *)(x))
738 #define PCOR(x) ((pCodeOpReg *)(x))
739 #define PCORB(x) ((pCodeOpRegBit *)(x))
740 #define PCOW(x) ((pCodeOpWild *)(x))
742 #define PBR(x) ((pBranch *)(x))
744 #define PCWB(x) ((pCodeWildBlock *)(x))
748 macros for checking pCode types
750 #define isPCI(x) ((PCODE(x)->type == PC_OPCODE))
751 #define isPCI_BRANCH(x) ((PCODE(x)->type == PC_OPCODE) && PCI(x)->isBranch)
752 #define isPCI_SKIP(x) ((PCODE(x)->type == PC_OPCODE) && PCI(x)->isSkip)
753 #define isPCI_BITSKIP(x)((PCODE(x)->type == PC_OPCODE) && PCI(x)->isSkip && PCI(x)->isBitInst)
754 #define isPCFL(x) ((PCODE(x)->type == PC_FLOW))
755 #define isPCF(x) ((PCODE(x)->type == PC_FUNCTION))
756 #define isPCL(x) ((PCODE(x)->type == PC_LABEL))
757 #define isPCW(x) ((PCODE(x)->type == PC_WILD))
758 #define isPCCS(x) ((PCODE(x)->type == PC_CSOURCE))
760 #define isCALL(x) ((isPCI(x)) && (PCI(x)->op == POC_CALL))
761 #define isSTATUS_REG(r) ((r)->pc_type == PO_STATUS)
763 #define isPCOLAB(x) ((PCOP(x)->type) == PO_LABEL)
765 /*-----------------------------------------------------------------*
767 *-----------------------------------------------------------------*/
769 pCode *newpCode (PIC_OPCODE op, pCodeOp *pcop); // Create a new pCode given an operand
770 pCode *newpCodeCharP(char *cP); // Create a new pCode given a char *
771 pCode *newpCodeInlineP(char *cP); // Create a new pCode given a char *
772 pCode *newpCodeFunction(char *g, char *f); // Create a new function
773 pCode *newpCodeLabel(char *name,int key); // Create a new label given a key
774 pCode *newpCodeCSource(int ln, char *f, char *l); // Create a new symbol line
775 pBlock *newpCodeChain(memmap *cm,char c, pCode *pc); // Create a new pBlock
776 void printpBlock(FILE *of, pBlock *pb); // Write a pBlock to a file
777 void printpCode(FILE *of, pCode *pc); // Write a pCode to a file
778 void addpCode2pBlock(pBlock *pb, pCode *pc); // Add a pCode to a pBlock
779 void addpBlock(pBlock *pb); // Add a pBlock to a pFile
780 void copypCode(FILE *of, char dbName); // Write all pBlocks with dbName to *of
781 void movepBlock2Head(char dbName); // move pBlocks around
782 void AnalyzepCode(char dbName);
783 int OptimizepCode(char dbName);
784 void printCallTree(FILE *of);
785 void pCodePeepInit(void);
786 void pBlockConvert2ISR(pBlock *pb);
788 pCodeOp *newpCodeOpLabel(char *name, int key);
789 pCodeOp *newpCodeOpImmd(char *name, int offset, int index, int code_space);
790 pCodeOp *newpCodeOpLit(int lit);
791 pCodeOp *newpCodeOpBit(char *name, int bit,int inBitSpace);
792 pCodeOp *newpCodeOpRegFromStr(char *name);
793 pCodeOp *newpCodeOp(char *name, PIC_OPTYPE p);
794 pCodeOp *pCodeOpCopy(pCodeOp *pcop);
796 pCode * findNextInstruction(pCode *pci);
797 pCode * findNextpCode(pCode *pc, PC_TYPE pct);
798 int isPCinFlow(pCode *pc, pCode *pcflow);
799 struct regs * getRegFromInstruction(pCode *pc);
801 extern void pcode_test(void);
803 /*-----------------------------------------------------------------*
805 *-----------------------------------------------------------------*/
807 extern pCodeOpReg pc_status;
808 extern pCodeOpReg pc_intcon;
809 extern pCodeOpReg pc_indf;
810 extern pCodeOpReg pc_fsr;
811 extern pCodeOpReg pc_pcl;
812 extern pCodeOpReg pc_pclath;
813 extern pCodeOpReg pc_kzero;
814 extern pCodeOpReg pc_wsave; /* wsave and ssave are used to save W and the Status */
815 extern pCodeOpReg pc_ssave; /* registers during an interrupt */
818 #endif // __PCODE_H__