Added support for multiplication. Fixed peep hole bugs (and more functionality to...
[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 struct pCodeWildBlock;
244
245 /*************************************************
246   pBranch
247
248   The first step in optimizing pCode is determining
249  the program flow. This information is stored in
250  single-linked lists in the for of 'from' and 'to'
251  objects with in a pcode. For example, most instructions
252  don't involve any branching. So their from branch
253  points to the pCode immediately preceding them and
254  their 'to' branch points to the pcode immediately
255  following them. A skip instruction is an example of
256  a pcode that has multiple (in this case two) elements
257  in the 'to' branch. A 'label' pcode is an where there
258  may be multiple 'from' branches.
259  *************************************************/
260
261 typedef struct pBranch
262 {
263   struct pCode   *pc;    // Next pCode in a branch
264   struct pBranch *next;  /* If more than one branch
265                           * the next one is here */
266
267 } pBranch;
268
269 /*************************************************
270   pCodeOp
271
272   pCode Operand structure.
273   For those assembly instructions that have arguments, 
274   the pCode will have a pCodeOp in which the argument
275   can be stored. For example
276
277     movf   some_register,w
278
279   'some_register' will be stored/referenced in a pCodeOp
280
281  *************************************************/
282
283 typedef struct pCodeOp
284 {
285   PIC_OPTYPE type;
286   char *name;
287   
288 } pCodeOp;
289 #if 0
290 typedef struct pCodeOpBit
291 {
292   pCodeOp pcop;
293   int bit;
294   unsigned int inBitSpace: 1; /* True if in bit space, else
295                                  just a bit of a register */
296 } pCodeOpBit;
297 #endif
298 typedef struct pCodeOpLit
299 {
300   pCodeOp pcop;
301   int lit;
302 } pCodeOpLit;
303
304 typedef struct pCodeOpImmd
305 {
306   pCodeOp pcop;
307   int offset;
308 } pCodeOpImmd;
309
310 typedef struct pCodeOpLabel
311 {
312   pCodeOp pcop;
313   int key;
314 } pCodeOpLabel;
315
316 typedef struct pCodeOpReg
317 {
318   pCodeOp pcop;    // Can be either GPR or SFR
319   int rIdx;        // Index into the register table
320   struct regs *r;
321   int instance;    // byte # of Multi-byte registers
322   struct pBlock *pb;
323 } pCodeOpReg;
324
325 typedef struct pCodeOpRegBit
326 {
327   pCodeOpReg  pcor;       // The Register containing this bit
328   int bit;                // 0-7 bit number.
329   PIC_OPTYPE subtype;     // The type of this register.
330   unsigned int inBitSpace: 1; /* True if in bit space, else
331                                  just a bit of a register */
332 } pCodeOpRegBit;
333
334
335 typedef struct pCodeOpWild
336 {
337   pCodeOp pcop;
338
339   struct pCodeWildBlock *pcwb;
340
341   int id;                 /* index into an array of char *'s that will match
342                            * the wild card. The array is in *pcp. */
343   pCodeOp *subtype;       /* Pointer to the Operand type into which this wild
344                            * card will be expanded */
345   pCodeOp *matched;       /* When a wild matches, we'll store a pointer to the
346                            * opcode we matched */
347
348 } pCodeOpWild;
349
350
351 /*************************************************
352     pCode
353
354     Here is the basic build block of a PIC instruction.
355     Each pic instruction will get allocated a pCode.
356     A linked list of pCodes makes a program.
357
358 **************************************************/
359
360 typedef struct pCode
361 {
362   PC_TYPE    type;
363
364   struct pCode *prev;  // The pCode objects are linked together
365   struct pCode *next;  // in doubly linked lists.
366
367   int seq;             // sequence number
368
369   struct pBlock *pb;   // The pBlock that contains this pCode.
370
371   /* "virtual functions"
372    *  The pCode structure is like a base class
373    * in C++. The subsequent structures that "inherit"
374    * the pCode structure will initialize these function
375    * pointers to something useful */
376   //  void (*analyze) (struct pCode *_this);
377   void (*destruct)(struct pCode *_this);
378   void (*print)  (FILE *of,struct pCode *_this);
379
380 } pCode;
381
382
383 /*************************************************
384     pCodeComment
385 **************************************************/
386
387 typedef struct pCodeComment
388 {
389
390   pCode  pc;
391
392   char *comment;
393
394 } pCodeComment;
395
396 /*************************************************
397     pCodeFlow
398
399   The Flow object is used as marker to separate 
400  the assembly code into contiguous chunks. In other
401  words, everytime an instruction cause or potentially
402  causes a branch, a Flow object will be inserted into
403  the pCode chain to mark the beginning of the next
404  contiguous chunk.
405 **************************************************/
406
407 typedef struct pCodeFlow
408 {
409
410   pCode  pc;
411
412   pCode *end;   /* Last pCode in this flow. Note that
413                    the first pCode is pc.next */
414
415   set **uses;   /* map the pCode instruction inCond and outCond conditions 
416                  * in this array of set's. The reason we allocate an 
417                  * array of pointers instead of declaring each type of 
418                  * usage is because there are port dependent usage definitions */
419   int nuses;    /* number of uses sets */
420
421   set *from;    /* flow blocks that can send control to this flow block */
422   set *to;      /* flow blocks to which this one can send control */
423
424   int inCond;   /* Input conditions - stuff assumed defined at entry */
425   int outCond;  /* Output conditions - stuff modified by flow block */
426
427 } pCodeFlow;
428
429 /*************************************************
430     pCodeInstruction
431
432     Here we describe all the facets of a PIC instruction
433     (expansion for the 18cxxx is also provided).
434
435 **************************************************/
436
437 typedef struct pCodeInstruction
438 {
439
440   pCode  pc;
441
442   PIC_OPCODE op;        // The opcode of the instruction.
443
444   char const * const mnemonic;       // Pointer to mnemonic string
445
446   pBranch *from;       // pCodes that execute before this one
447   pBranch *to;         // pCodes that execute after
448   pBranch *label;      // pCode instructions that have labels
449
450   pCodeOp *pcop;              /* Operand, if this instruction has one */
451
452   pCodeFlow *pcflow;   /* flow block to which this instruction belongs */
453
454   unsigned int num_ops;        /* Number of operands (0,1,2 for mid range pics) */
455   unsigned int isModReg:  1;   /* If destination is W or F, then 1==F */
456   unsigned int isBitInst: 1;   /* e.g. BCF */
457   unsigned int isBranch:  1;   /* True if this is a branching instruction */
458   unsigned int isSkip:    1;   /* True if this is a skip instruction */
459
460   PIC_OPCODE inverted_op;      /* Opcode of instruction that's the opposite of this one */
461   unsigned int inCond;   // Input conditions for this instruction
462   unsigned int outCond;  // Output conditions for this instruction
463
464 } pCodeInstruction;
465
466
467 /*************************************************
468     pCodeLabel
469 **************************************************/
470
471 typedef struct pCodeLabel
472 {
473
474   pCode  pc;
475
476   char *label;
477   int key;
478
479 } pCodeLabel;
480
481 /*************************************************
482     pCodeFunction
483 **************************************************/
484
485 typedef struct pCodeFunction
486 {
487
488   pCode  pc;
489
490   char *modname;
491   char *fname;     /* If NULL, then this is the end of
492                       a function. Otherwise, it's the
493                       start and the name is contained
494                       here */
495
496   pBranch *from;       // pCodes that execute before this one
497   pBranch *to;         // pCodes that execute after
498   pBranch *label;      // pCode instructions that have labels
499
500 } pCodeFunction;
501
502
503 /*************************************************
504     pCodeWild
505 **************************************************/
506
507 typedef struct pCodeWild
508 {
509
510   pCodeInstruction  pci;
511
512   int    id;     /* Index into the wild card array of a peepBlock 
513                   * - this wild card will get expanded into that pCode
514                   *   that is stored at this index */
515
516   /* Conditions on wild pcode instruction */
517   int    mustBeBitSkipInst:1;
518   int    mustNotBeBitSkipInst:1;
519   int    invertBitSkipInst:1;
520
521   pCodeOp *operand;  // Optional operand
522   pCodeOp *label;    // Optional label
523
524 } pCodeWild;
525
526 /*************************************************
527     pBlock
528
529     Here are PIC program snippets. There's a strong
530     correlation between the eBBlocks and pBlocks.
531     SDCC subdivides a C program into managable chunks.
532     Each chunk becomes a eBBlock and ultimately in the
533     PIC port a pBlock.
534
535 **************************************************/
536
537 typedef struct pBlock
538 {
539   memmap *cmemmap;   /* The snippet is from this memmap */
540   char   dbName;     /* if cmemmap is NULL, then dbName will identify the block */
541   pCode *pcHead;     /* A pointer to the first pCode in a link list of pCodes */
542   pCode *pcTail;     /* A pointer to the last pCode in a link list of pCodes */
543
544   struct pBlock *next;      /* The pBlocks will form a doubly linked list */
545   struct pBlock *prev;
546
547   set *function_entries;    /* dll of functions in this pblock */
548   set *function_exits;
549   set *function_calls;
550   set *tregisters;
551
552   unsigned visited:1;       /* set true if traversed in call tree */
553
554   unsigned seq;             /* sequence number of this pBlock */
555
556 } pBlock;
557
558 /*************************************************
559     pFile
560
561     The collection of pBlock program snippets are
562     placed into a linked list that is implemented
563     in the pFile structure.
564
565     The pcode optimizer will parse the pFile.
566
567 **************************************************/
568
569 typedef struct pFile
570 {
571   pBlock *pbHead;     /* A pointer to the first pBlock */
572   pBlock *pbTail;     /* A pointer to the last pBlock */
573
574   pBranch *functions; /* A SLL of functions in this pFile */
575
576 } pFile;
577
578
579
580 /*************************************************
581   pCodeWildBlock
582
583   The pCodeWildBlock object keeps track of the wild
584   variables, operands, and opcodes that exist in
585   a pBlock.
586 **************************************************/
587 typedef struct pCodeWildBlock {
588   pBlock    *pb;
589   struct pCodePeep *pcp;    // pointer back to ... I don't like this...
590
591   int       nvars;          // Number of wildcard registers in target.
592   char    **vars;           // array of pointers to them
593
594   int       nops;           // Number of wildcard operands in target.
595   pCodeOp **wildpCodeOps;   // array of pointers to the pCodeOp's.
596
597   int       nwildpCodes;    // Number of wildcard pCodes in target/replace
598   pCode   **wildpCodes;     // array of pointers to the pCode's.
599
600 } pCodeWildBlock;
601
602 /*************************************************
603   pCodePeep
604
605   The pCodePeep object mimics the peep hole optimizer
606   in the main SDCC src (e.g. SDCCpeeph.c). Essentially
607   there is a target pCode chain and a replacement
608   pCode chain. The target chain is compared to the
609   pCode that is generated by gen.c. If a match is
610   found then the pCode is replaced by the replacement
611   pCode chain.
612 **************************************************/
613 typedef struct pCodePeep {
614   pCodeWildBlock target;     // code we'd like to optimize
615   pCodeWildBlock replace;    // and this is what we'll optimize it with.
616
617   //pBlock *target;
618   //pBlock replace;            // and this is what we'll optimize it with.
619
620
621
622   /* (Note: a wildcard register is a place holder. Any register
623    * can be replaced by the wildcard when the pcode is being 
624    * compared to the target. */
625
626   /* Post Conditions. A post condition is a condition that
627    * must be either true or false before the peep rule is
628    * accepted. For example, a certain rule may be accepted
629    * if and only if the Z-bit is not used as an input to 
630    * the subsequent instructions in a pCode chain.
631    */
632   unsigned int postFalseCond;  
633   unsigned int postTrueCond;
634
635 } pCodePeep;
636
637 /*************************************************
638
639   pCode peep command definitions 
640
641  Here are some special commands that control the
642 way the peep hole optimizer behaves
643
644 **************************************************/
645
646 enum peepCommandTypes{
647   NOTBITSKIP = 0,
648   BITSKIP,
649   INVERTBITSKIP,
650   _LAST_PEEP_COMMAND_
651 };
652
653 /*************************************************
654     peepCommand structure stores the peep commands.
655
656 **************************************************/
657
658 typedef struct peepCommand {
659   int id;
660   char *cmd;
661 } peepCommand;
662
663
664 /*************************************************
665     pCode Macros
666
667 **************************************************/
668 #define PCODE(x)  ((pCode *)(x))
669 #define PCI(x)    ((pCodeInstruction *)(x))
670 #define PCL(x)    ((pCodeLabel *)(x))
671 #define PCF(x)    ((pCodeFunction *)(x))
672 #define PCFL(x)    ((pCodeFlow *)(x))
673 #define PCW(x)    ((pCodeWild *)(x))
674
675 #define PCOP(x)   ((pCodeOp *)(x))
676 //#define PCOB(x)   ((pCodeOpBit *)(x))
677 #define PCOL(x)   ((pCodeOpLit *)(x))
678 #define PCOI(x)   ((pCodeOpImmd *)(x))
679 #define PCOLAB(x) ((pCodeOpLabel *)(x))
680 #define PCOR(x)   ((pCodeOpReg *)(x))
681 #define PCORB(x)  ((pCodeOpRegBit *)(x))
682 #define PCOW(x)   ((pCodeOpWild *)(x))
683
684 #define PBR(x)    ((pBranch *)(x))
685
686 #define PCWB(x)   ((pCodeWildBlock *)(x))
687
688 /*-----------------------------------------------------------------*
689  * pCode functions.
690  *-----------------------------------------------------------------*/
691
692 pCode *newpCode (PIC_OPCODE op, pCodeOp *pcop); // Create a new pCode given an operand
693 pCode *newpCodeCharP(char *cP);              // Create a new pCode given a char *
694 pCode *newpCodeFunction(char *g, char *f);   // Create a new function
695 pCode *newpCodeLabel(char *name,int key);    // Create a new label given a key
696 pBlock *newpCodeChain(memmap *cm,char c, pCode *pc); // Create a new pBlock
697 void printpBlock(FILE *of, pBlock *pb);      // Write a pBlock to a file
698 void printpCode(FILE *of, pCode *pc);        // Write a pCode to a file
699 void addpCode2pBlock(pBlock *pb, pCode *pc); // Add a pCode to a pBlock
700 void addpBlock(pBlock *pb);                  // Add a pBlock to a pFile
701 void copypCode(FILE *of, char dbName);       // Write all pBlocks with dbName to *of
702 void movepBlock2Head(char dbName);           // move pBlocks around
703 void AnalyzepCode(char dbName);
704 void OptimizepCode(char dbName);
705 void printCallTree(FILE *of);
706 void pCodePeepInit(void);
707 void pBlockConvert2ISR(pBlock *pb);
708
709 pCodeOp *newpCodeOpLabel(char *name, int key);
710 pCodeOp *newpCodeOpImmd(char *name, int offset);
711 pCodeOp *newpCodeOpLit(int lit);
712 pCodeOp *newpCodeOpBit(char *name, int bit,int inBitSpace);
713 pCodeOp *newpCodeOpRegFromStr(char *name);
714 pCodeOp *newpCodeOp(char *name, PIC_OPTYPE p);
715 pCodeOp *pCodeOpCopy(pCodeOp *pcop);
716
717 extern void pcode_test(void);
718
719 /*-----------------------------------------------------------------*
720  * pCode objects.
721  *-----------------------------------------------------------------*/
722
723 extern pCodeOpReg pc_status;
724 extern pCodeOpReg pc_intcon;
725 extern pCodeOpReg pc_indf;
726 extern pCodeOpReg pc_fsr;
727 extern pCodeOpReg pc_pcl;
728 extern pCodeOpReg pc_pclath;
729 extern pCodeOpReg pc_kzero;
730 extern pCodeOpReg pc_wsave;     /* wsave and ssave are used to save W and the Status */
731 extern pCodeOpReg pc_ssave;     /* registers during an interrupt */
732
733
734 #endif // __PCODE_H__