c0a8bee399914a06996926f88bb28f1a164cdb73
[fw/sdcc] / src / pic / pcode.h
1 /*-------------------------------------------------------------------------
2
3    pcode.h - post code generation
4    Written By -  Scott Dattalo scott@dattalo.com
5
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
9    later version.
10    
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.
15    
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.
19    
20 -------------------------------------------------------------------------*/
21
22 //#include "ralloc.h"
23 struct regs;
24
25 /*
26    Post code generation
27
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:
38
39    example1:
40      movwf  t1
41      movf   t1,w
42
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:
48
49    example2:
50      movwf  t1
51      movf   t1,w     ; Can't remove this movf
52      skpz
53       return
54
55    example3:
56      movwf  t1
57      movf   t1,w     ; This  movf can be removed
58      xorwf  t2,w     ; since xorwf will over write Z 
59      skpz
60       return
61
62 */
63
64
65 #ifndef __PCODE_H__
66 #define __PCODE_H__
67
68 /***********************************************************************
69  * debug stuff
70  * 
71  * The DFPRINTF macro will call fprintf if PCODE_DEBUG is defined.
72  * The macro is used like:
73  *
74  * DPRINTF(("%s #%d\n","test", 1));
75  *
76  * The double parenthesis (()) are necessary
77  * 
78  ***********************************************************************/
79 //#define PCODE_DEBUG
80
81 #ifdef PCODE_DEBUG
82 #define DFPRINTF(args) (fprintf args)
83 #else
84 #define DFPRINTF(args) ;
85 #endif
86
87
88 /***********************************************************************
89  *  PIC status bits - this will move into device dependent headers
90  ***********************************************************************/
91 #define PIC_C_BIT    0
92 #define PIC_DC_BIT   1
93 #define PIC_Z_BIT    2
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 */
97
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 */
109
110 /***********************************************************************
111  *  Operand types 
112  ***********************************************************************/
113 #define POT_RESULT  0
114 #define POT_LEFT    1
115 #define POT_RIGHT   2
116
117
118 /***********************************************************************
119  *
120  *  PIC_OPTYPE - Operand types that are specific to the PIC architecture
121  *
122  *  If a PIC assembly instruction has an operand then here is where we
123  *  associate a type to it. For example,
124  *
125  *     movf    reg,W
126  *
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.
130  *
131  ***********************************************************************/
132
133
134
135 typedef enum 
136 {
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)
155   PO_LABEL,
156   PO_WILD            // Wild card operand in peep optimizer
157 } PIC_OPTYPE;
158
159
160 /***********************************************************************
161  *
162  *  PIC_OPCODE
163  *
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. 
166  *
167  ***********************************************************************/
168
169 typedef enum
170 {
171   POC_WILD=-1,   /* Wild card - used in the pCode peep hole optimizer
172                   * to represent ANY pic opcode */
173   POC_ADDLW=0,
174   POC_ADDWF,
175   POC_ADDFW,
176   POC_ANDLW,
177   POC_ANDWF,
178   POC_ANDFW,
179   POC_BCF,
180   POC_BSF,
181   POC_BTFSC,
182   POC_BTFSS,
183   POC_CALL,
184   POC_COMF,
185   POC_COMFW,
186   POC_CLRF,
187   POC_CLRW,
188   POC_DECF,
189   POC_DECFW,
190   POC_DECFSZ,
191   POC_DECFSZW,
192   POC_GOTO,
193   POC_INCF,
194   POC_INCFW,
195   POC_INCFSZ,
196   POC_INCFSZW,
197   POC_IORLW,
198   POC_IORWF,
199   POC_IORFW,
200   POC_MOVF,
201   POC_MOVFW,
202   POC_MOVLW,
203   POC_MOVWF,
204   POC_NOP,
205   POC_RETLW,
206   POC_RETURN,
207   POC_RETFIE,
208   POC_RLF,
209   POC_RLFW,
210   POC_RRF,
211   POC_RRFW,
212   POC_SUBLW,
213   POC_SUBWF,
214   POC_SUBFW,
215   POC_SWAPF,
216   POC_SWAPFW,
217   POC_TRIS,
218   POC_XORLW,
219   POC_XORWF,
220   POC_XORFW
221 } PIC_OPCODE;
222
223
224 /***********************************************************************
225  *  PC_TYPE  - pCode Types
226  ***********************************************************************/
227
228 typedef enum
229 {
230   PC_COMMENT=0,   /* pCode is a comment     */
231   PC_OPCODE,      /* PORT dependent opcode  */
232   PC_LABEL,       /* assembly label         */
233   PC_FLOW,        /* flow analysis          */
234   PC_FUNCTION,    /* Function start or end  */
235   PC_WILD         /* wildcard - an opcode place holder used 
236                    * in the pCode peep hole optimizer */
237 } PC_TYPE;
238
239 /************************************************/
240 /***************  Structures ********************/
241 /************************************************/
242 struct pCode;
243
244 /*************************************************
245   pBranch
246
247   The first step in optimizing pCode is determining
248  the program flow. This information is stored in
249  single-linked lists in the for of 'from' and 'to'
250  objects with in a pcode. For example, most instructions
251  don't involve any branching. So their from branch
252  points to the pCode immediately preceding them and
253  their 'to' branch points to the pcode immediately
254  following them. A skip instruction is an example of
255  a pcode that has multiple (in this case two) elements
256  in the 'to' branch. A 'label' pcode is an where there
257  may be multiple 'from' branches.
258  *************************************************/
259
260 typedef struct pBranch
261 {
262   struct pCode   *pc;    // Next pCode in a branch
263   struct pBranch *next;  /* If more than one branch
264                           * the next one is here */
265
266 } pBranch;
267
268 /*************************************************
269   pCodeOp
270
271   pCode Operand structure.
272   For those assembly instructions that have arguments, 
273   the pCode will have a pCodeOp in which the argument
274   can be stored. For example
275
276     movf   some_register,w
277
278   'some_register' will be stored/referenced in a pCodeOp
279
280  *************************************************/
281
282 typedef struct pCodeOp
283 {
284   PIC_OPTYPE type;
285   char *name;
286   
287 } pCodeOp;
288 #if 0
289 typedef struct pCodeOpBit
290 {
291   pCodeOp pcop;
292   int bit;
293   unsigned int inBitSpace: 1; /* True if in bit space, else
294                                  just a bit of a register */
295 } pCodeOpBit;
296 #endif
297 typedef struct pCodeOpLit
298 {
299   pCodeOp pcop;
300   int lit;
301 } pCodeOpLit;
302
303 typedef struct pCodeOpImmd
304 {
305   pCodeOp pcop;
306   int offset;
307 } pCodeOpImmd;
308
309 typedef struct pCodeOpLabel
310 {
311   pCodeOp pcop;
312   int key;
313 } pCodeOpLabel;
314
315 typedef struct pCodeOpReg
316 {
317   pCodeOp pcop;    // Can be either GPR or SFR
318   int rIdx;        // Index into the register table
319   struct regs *r;
320   int instance;    // byte # of Multi-byte registers
321   struct pBlock *pb;
322 } pCodeOpReg;
323
324 typedef struct pCodeOpRegBit
325 {
326   pCodeOpReg  pcor;       // The Register containing this bit
327   int bit;                // 0-7 bit number.
328   PIC_OPTYPE subtype;     // The type of this register.
329   unsigned int inBitSpace: 1; /* True if in bit space, else
330                                  just a bit of a register */
331 } pCodeOpRegBit;
332
333
334 /*************************************************
335     pCode
336
337     Here is the basic build block of a PIC instruction.
338     Each pic instruction will get allocated a pCode.
339     A linked list of pCodes makes a program.
340
341 **************************************************/
342
343 typedef struct pCode
344 {
345   PC_TYPE    type;
346
347   struct pCode *prev;  // The pCode objects are linked together
348   struct pCode *next;  // in doubly linked lists.
349
350   int seq;             // sequence number
351
352   struct pBlock *pb;   // The pBlock that contains this pCode.
353
354   /* "virtual functions"
355    *  The pCode structure is like a base class
356    * in C++. The subsequent structures that "inherit"
357    * the pCode structure will initialize these function
358    * pointers to something useful */
359   //  void (*analyze) (struct pCode *_this);
360   void (*destruct)(struct pCode *_this);
361   void (*print)  (FILE *of,struct pCode *_this);
362
363 } pCode;
364
365
366 /*************************************************
367     pCodeComment
368 **************************************************/
369
370 typedef struct pCodeComment
371 {
372
373   pCode  pc;
374
375   char *comment;
376
377 } pCodeComment;
378
379 /*************************************************
380     pCodeFlow
381
382   The Flow object is used as marker to separate 
383  the assembly code into contiguous chunks. In other
384  words, everytime an instruction cause or potentially
385  causes a branch, a Flow object will be inserted into
386  the pCode chain to mark the beginning of the next
387  contiguous chunk.
388 **************************************************/
389
390 typedef struct pCodeFlow
391 {
392
393   pCode  pc;
394
395   pCode *end;   /* Last pCode in this flow. Note that
396                    the first pCode is pc.next */
397
398   set **uses;   /* map the pCode instruction inCond and outCond conditions 
399                  * in this array of set's. The reason we allocate an 
400                  * array of pointers instead of declaring each type of 
401                  * usage is because there are port dependent usage definitions */
402   int nuses;    /* number of uses sets */
403
404   set *from;    /* flow blocks that can send control to this flow block */
405   set *to;      /* flow blocks to which this one can send control */
406
407   int inCond;   /* Input conditions - stuff assumed defined at entry */
408   int outCond;  /* Output conditions - stuff modified by flow block */
409
410 } pCodeFlow;
411
412 /*************************************************
413     pCodeInstruction
414
415     Here we describe all the facets of a PIC instruction
416     (expansion for the 18cxxx is also provided).
417
418 **************************************************/
419
420 typedef struct pCodeInstruction
421 {
422
423   pCode  pc;
424
425   PIC_OPCODE op;        // The opcode of the instruction.
426
427   char const * const mnemonic;       // Pointer to mnemonic string
428
429   pBranch *from;       // pCodes that execute before this one
430   pBranch *to;         // pCodes that execute after
431   pBranch *label;      // pCode instructions that have labels
432
433   pCodeOp *pcop;              /* Operand, if this instruction has one */
434
435   pCodeFlow *pcflow;   /* flow block to which this instruction belongs */
436
437   unsigned int num_ops;        /* Number of operands (0,1,2 for mid range pics) */
438   unsigned int isModReg:  1;   /* If destination is W or F, then 1==F */
439   unsigned int isBitInst: 1;   /* e.g. BCF */
440   unsigned int isBranch:  1;   /* True if this is a branching instruction */
441   unsigned int isSkip:    1;   /* True if this is a skip instruction */
442
443   unsigned int inCond;   // Input conditions for this instruction
444   unsigned int outCond;  // Output conditions for this instruction
445
446 } pCodeInstruction;
447
448
449 /*************************************************
450     pCodeLabel
451 **************************************************/
452
453 typedef struct pCodeLabel
454 {
455
456   pCode  pc;
457
458   char *label;
459   int key;
460
461 } pCodeLabel;
462
463 /*************************************************
464     pCodeFunction
465 **************************************************/
466
467 typedef struct pCodeFunction
468 {
469
470   pCode  pc;
471
472   char *modname;
473   char *fname;     /* If NULL, then this is the end of
474                       a function. Otherwise, it's the
475                       start and the name is contained
476                       here */
477
478   pBranch *from;       // pCodes that execute before this one
479   pBranch *to;         // pCodes that execute after
480   pBranch *label;      // pCode instructions that have labels
481
482 } pCodeFunction;
483
484
485 /*************************************************
486     pCodeWild
487 **************************************************/
488
489 typedef struct pCodeWild
490 {
491
492   pCodeInstruction  pci;
493
494   int    id;     /* Index into the wild card array of a peepBlock 
495                   * - this wild card will get expanded into that pCode
496                   *   that is stored at this index */
497
498
499   pCodeOp *operand;  // Optional operand
500   pCodeOp *label;    // Optional label
501
502 } pCodeWild;
503
504 /*************************************************
505     pBlock
506
507     Here are PIC program snippets. There's a strong
508     correlation between the eBBlocks and pBlocks.
509     SDCC subdivides a C program into managable chunks.
510     Each chunk becomes a eBBlock and ultimately in the
511     PIC port a pBlock.
512
513 **************************************************/
514
515 typedef struct pBlock
516 {
517   memmap *cmemmap;   /* The snippet is from this memmap */
518   char   dbName;     /* if cmemmap is NULL, then dbName will identify the block */
519   pCode *pcHead;     /* A pointer to the first pCode in a link list of pCodes */
520   pCode *pcTail;     /* A pointer to the last pCode in a link list of pCodes */
521
522   struct pBlock *next;      /* The pBlocks will form a doubly linked list */
523   struct pBlock *prev;
524
525   set *function_entries;    /* dll of functions in this pblock */
526   set *function_exits;
527   set *function_calls;
528   set *tregisters;
529
530   unsigned visited:1;       /* set true if traversed in call tree */
531
532   unsigned seq;             /* sequence number of this pBlock */
533
534 } pBlock;
535
536 /*************************************************
537     pFile
538
539     The collection of pBlock program snippets are
540     placed into a linked list that is implemented
541     in the pFile structure.
542
543     The pcode optimizer will parse the pFile.
544
545 **************************************************/
546
547 typedef struct pFile
548 {
549   pBlock *pbHead;     /* A pointer to the first pBlock */
550   pBlock *pbTail;     /* A pointer to the last pBlock */
551
552   pBranch *functions; /* A SLL of functions in this pFile */
553
554 } pFile;
555
556
557
558 /*************************************************
559   pCodePeep
560
561   The pCodePeep object mimics the peep hole optimizer
562   in the main SDCC src (e.g. SDCCpeeph.c). Essentially
563   there is a target pCode chain and a replacement
564   pCode chain. The target chain is compared to the
565   pCode that is generated by gen.c. If a match is
566   found then the pCode is replaced by the replacement
567   pCode chain.
568 **************************************************/
569 typedef struct pCodePeep {
570
571   pBlock *target;    // code we'd like to optimize
572   pBlock *replace;   // and this is what we'll optimize it with.
573
574   int     nvars;       // Number of wildcard registers in target.
575   char  **vars;        // array of pointers to them
576   int     nops;             // Number of wildcard operands in target.
577   pCodeOp **wildpCodeOps;   // array of pointers to the pCodeOp's.
578
579   int     nwildpCodes; // Number of wildcard pCodes in target/replace
580   pCode **wildpCodes;  // array of pointers to the pCode's.
581
582
583   /* (Note: a wildcard register is a place holder. Any register
584    * can be replaced by the wildcard when the pcode is being 
585    * compared to the target. */
586
587   /* Post Conditions. A post condition is a condition that
588    * must be either true or false before the peep rule is
589    * accepted. For example, a certain rule may be accepted
590    * if and only if the Z-bit is not used as an input to 
591    * the subsequent instructions in a pCode chain.
592    */
593   unsigned int postFalseCond;  
594   unsigned int postTrueCond;
595
596 } pCodePeep;
597
598 typedef struct pCodeOpWild
599 {
600   pCodeOp pcop;
601   //PIC_OPTYPE subtype;      Wild get's expanded to this by the optimizer
602   pCodePeep *pcp;         // pointer to the parent peep block 
603   int id;                 /* index into an array of char *'s that will match
604                            * the wild card. The array is in *pcp. */
605   pCodeOp *subtype;       /* Pointer to the Operand type into which this wild
606                            * card will be expanded */
607   pCodeOp *matched;       /* When a wild matches, we'll store a pointer to the
608                            * opcode we matched */
609
610 } pCodeOpWild;
611
612 /*************************************************
613     pCode Macros
614
615 **************************************************/
616 #define PCODE(x)  ((pCode *)(x))
617 #define PCI(x)    ((pCodeInstruction *)(x))
618 #define PCL(x)    ((pCodeLabel *)(x))
619 #define PCF(x)    ((pCodeFunction *)(x))
620 #define PCFL(x)    ((pCodeFlow *)(x))
621 #define PCW(x)    ((pCodeWild *)(x))
622
623 #define PCOP(x)   ((pCodeOp *)(x))
624 //#define PCOB(x)   ((pCodeOpBit *)(x))
625 #define PCOL(x)   ((pCodeOpLit *)(x))
626 #define PCOI(x)   ((pCodeOpImmd *)(x))
627 #define PCOLAB(x) ((pCodeOpLabel *)(x))
628 #define PCOR(x)   ((pCodeOpReg *)(x))
629 #define PCORB(x)  ((pCodeOpRegBit *)(x))
630 #define PCOW(x)   ((pCodeOpWild *)(x))
631
632 #define PBR(x)    ((pBranch *)(x))
633
634 /*-----------------------------------------------------------------*
635  * pCode functions.
636  *-----------------------------------------------------------------*/
637
638 pCode *newpCode (PIC_OPCODE op, pCodeOp *pcop); // Create a new pCode given an operand
639 pCode *newpCodeCharP(char *cP);              // Create a new pCode given a char *
640 pCode *newpCodeFunction(char *g, char *f);   // Create a new function
641 pCode *newpCodeLabel(char *name,int key);    // Create a new label given a key
642 pBlock *newpCodeChain(memmap *cm,char c, pCode *pc); // Create a new pBlock
643 void printpBlock(FILE *of, pBlock *pb);      // Write a pBlock to a file
644 void printpCode(FILE *of, pCode *pc);        // Write a pCode to a file
645 void addpCode2pBlock(pBlock *pb, pCode *pc); // Add a pCode to a pBlock
646 void addpBlock(pBlock *pb);                  // Add a pBlock to a pFile
647 void copypCode(FILE *of, char dbName);       // Write all pBlocks with dbName to *of
648 void movepBlock2Head(char dbName);           // move pBlocks around
649 void AnalyzepCode(char dbName);
650 void OptimizepCode(char dbName);
651 void printCallTree(FILE *of);
652 void pCodePeepInit(void);
653 void pBlockConvert2ISR(pBlock *pb);
654
655 pCodeOp *newpCodeOpLabel(char *name, int key);
656 pCodeOp *newpCodeOpImmd(char *name, int offset);
657 pCodeOp *newpCodeOpLit(int lit);
658 pCodeOp *newpCodeOpBit(char *name, int bit,int inBitSpace);
659 pCodeOp *newpCodeOpRegFromStr(char *name);
660 pCodeOp *newpCodeOp(char *name, PIC_OPTYPE p);
661 extern void pcode_test(void);
662
663 /*-----------------------------------------------------------------*
664  * pCode objects.
665  *-----------------------------------------------------------------*/
666
667 extern pCodeOpReg pc_status;
668 extern pCodeOpReg pc_intcon;
669 extern pCodeOpReg pc_indf;
670 extern pCodeOpReg pc_fsr;
671 extern pCodeOpReg pc_pcl;
672 extern pCodeOpReg pc_pclath;
673 extern pCodeOpReg pc_kzero;
674 extern pCodeOpReg pc_wsave;     /* wsave and ssave are used to save W and the Status */
675 extern pCodeOpReg pc_ssave;     /* registers during an interrupt */
676
677
678 #endif // __PCODE_H__