src/vm/jit/lsra.h

   1 /* src/vm/jit/lsra.h - linear scan register allocator header
   2
   3    Copyright (C) 1996-2005 R. Grafl, A. Krall, C. Kruegel, C. Oates,
   4    R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
   5    C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
   6    Institut f. Computersprachen - TU Wien
   7
   8    This file is part of CACAO.
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2, or (at
  13    your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful, but
  16    WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  23    02111-1307, USA.
  24
  25    Contact: cacao@complang.tuwien.ac.at
  26
  27    Authors: Christian Ullrich
  28
  29    $Id: lsra.h 3647 2005-11-09 21:40:39Z christian $
  30
  31 */
  32
  33
  34 #ifndef _LSRA_H
  35 #define _LSRA_H
  36
  37 /*  #define LSRA_DEBUG  */
  38 /* #define LSRA_SAVEDVAR */
  39 /* #define LSRA_MEMORY */
  40 /*  #define LSRA_PRINTLIFETIMES  */
  41 /* #define LSRA_USES_REG_RES */ /* is now in i386/codegen.h */
  42 /*  #define LSRA_TESTLT */
  43 /* #define LSRA_LEAF */
  44 #if defined(__I386__) || defined(__X86_64__)
  45 #define JOIN_DEST_STACK           /* The destination stackslot gets the same  */
  46         /* register as one of the src stackslots. Important for i386 & X86_64 */
  47         /* since they do not have "3 operand" arithmetic instructions to      */
  48         /* prevent usage of a reserved register (REG_ITMPX)                   */
  49 #endif
  50 #define JOIN_DUP_STACK         /* join "identical" stackslots created by dup* */
  51
  52 #define USAGE_COUNT        /* influence LSRA with usagecount */
  53 #define USAGE_PER_INSTR    /* divide usagecount by lifetimelength */
  54
  55 #ifdef LSRA_DEBUG
  56 #undef LSRA_LEAF
  57 #endif
  58
  59 #ifdef LSRA_TESTLT
  60 #define VS 999999
  61 #endif
  62
  63
  64 #ifdef LSRA_DEBUG
  65 #define LSRA_PRINTLIFETIMES
  66 #endif
  67
  68 #define LSRA_BB_IN 3
  69 #define LSRA_BB_OUT 2
  70 #define LSRA_STORE 1
  71 #define LSRA_LOAD 0
  72 #define LSRA_POP -1
  73
  74 /* join types and flags*/
  75 #define JOIN     0 /* joins that are not in any way dangerous                 */
  76 #define JOIN_BB  1 /* join Stackslots over Basic Block Boundaries             */
  77 #define JOIN_DUP 2 /* join of two possibly concurring lifeteimes through DUP* */
  78 #define JOIN_OP  4 /* join of src operand with dst operand on i386 and x86_64 */
  79                    /* architecture                                            */
  80                    /* JOIN_DUP and JOIN_OP is mutually exclusive as JOIN_OP   */
  81                    /* and JOIN_BB                                             */
  82 #define JOINING  8 /* set while joining for DUP or OP to prevent assignement  */
  83                    /* to a REG_RES before all involved lifetimes have been    */
  84                    /* seen completely */
  85
  86 #define min(a,b) ((a)<(b)?(a):(b))
  87 #define max(a,b) ((a)<(b)?(b):(a))
  88
  89 struct _list {
  90         int value;
  91         struct _list *next;
  92 };
  93
  94 struct _backedge {
  95         int start;
  96         int end;
  97         struct _backedge *next;
  98 };
  99
 100 struct lifetime {
 101         int i_start;                /* instruction number of first use */
 102         int i_end;                  /* instruction number of last use */
 103         int v_index;           /* local variable index or negative for stackslots */
 104         int type;                   /* TYPE_XXX or -1 for unused lifetime */
 105         long usagecount;            /* number of references*/
 106         int reg;                    /* regoffset allocated by lsra*/
 107         int savedvar;
 108         int flags;
 109         struct stackslot *local_ss; /* Stackslots for this Lifetime or NULL ( ==  */
 110                                 /* "pure" Local Var) */
 111         int bb_last_use;
 112         int i_last_use;
 113         int bb_first_def;
 114         int i_first_def;
 115 };
 116
 117 struct active_lt {
 118         struct lifetime *lt;
 119         struct active_lt *next;
 120 };
 121
 122 struct l_loop {
 123         int b_first;
 124         int b_last;
 125         int nesting;
 126 };
 127
 128 struct b_loop {
 129         int loop;
 130         int instr;
 131 };
 132
 133
 134 struct stackslot {
 135         stackptr s;
 136         int bb;
 137         struct stackslot *next;
 138 };
 139
 140 struct lsra_register {
 141         int *sav_reg;
 142         int *tmp_reg;
 143         int *nregdesc;
 144         int sav_top;
 145         int tmp_top;
 146 };
 147
 148 struct lsra_reg {
 149         int reg_index;
 150         int use;
 151 };
 152
 153 struct _sbr {
 154         int header;          /* BB Index of subroutine start (SBR_HEADER) */
 155         struct _list *ret;   /* List of possible return BB indizes */
 156         struct _sbr *next;
 157 };
 158
 159 struct lsradata {
 160 #if defined(LSRA_USES_REG_RES)
 161         int reg_res_free[REG_RES_CNT];
 162 #endif
 163         struct _list **succ; /* CFG successors*/
 164         struct _list **pred; /* CFG predecessors */
 165         int *num_pred;       /* CFG number of predecessors */
 166         int *sorted;         /* BB sorted in reverse post order */
 167         int *sorted_rev;     /* BB reverse lookup of sorted */
 168
 169         struct _backedge **backedge; /* backedge data structure */
 170         int backedge_count;          /* number of backedges */
 171
 172         struct _sbr sbr;     /* list of subroutines, sorted by header */
 173
 174         long *nesting;    /* Nesting level of BB*/
 175
 176         int maxlifetimes; /* copy from methodinfo to prevent passing methodinfo   */
 177                       /* as parameter */
 178
 179         struct lifetime *lifetime; /* array of lifetimes */
 180         int lifetimecount;         /* number of lifetimes */
 181         int *lt_used;              /* index to lifetimearray for used lifetimes   */
 182         int *lt_int;               /* index to lifetimearray for int lifetimes    */
 183         int lt_int_count;          /* number of int/[lng]/[adr] lifetimes */
 184         int *lt_flt;               /* index to lifetimearray for float lifetimes  */
 185         int lt_flt_count;          /* number of float/double lifetimes */
 186         int *lt_mem;               /* index to lifetimearray for all lifetimes    */
 187                                /* not to be allocated in registers */
 188         int lt_mem_count;          /* number of this other lifetimes */
 189
 190         struct active_lt *active_tmp, *active_sav;
 191
 192         struct lsra_exceptiontable *ex;
 193         int v_index;               /* next free index for stack slot lifetimes    */
 194                                    /* decrements from -1 */
 195 };
 196
 197 struct freemem {
 198         int off;
 199         int end;
 200         struct freemem *next;
 201 };
 202
 203 typedef struct lsradata lsradata;
 204
 205 /* function prototypes */
 206 bool lsra(methodinfo *, codegendata *, registerdata *,t_inlining_globals *);
 207 bool lsra_test(methodinfo *, codegendata *);
 208 void lsra_init(methodinfo *, codegendata *, t_inlining_globals *, lsradata *);
 209 bool lsra_setup(methodinfo *, codegendata *, registerdata *, lsradata *);
 210 void lsra_main(methodinfo *, lsradata *, registerdata *, codegendata *);
 211 void lsra_clean_Graph( methodinfo *, codegendata *, lsradata *);
 212
 213 #ifdef LSRA_DEBUG
 214 void lsra_dump_stack(stackptr );
 215 #endif
 216 #ifdef LSRA_PRINTLIFETIMES
 217 void print_lifetimes(registerdata *, lsradata *, int *, int);
 218 #endif
 219 #ifdef LSRA_TESTLT
 220 void test_lifetimes( methodinfo *, lsradata *, registerdata *);
 221 #endif
 222
 223 void lsra_reg_setup(methodinfo *m ,registerdata *,struct lsra_register *,struct lsra_register * );
 224
 225
 226 void lsra_scan_registers_canditates(methodinfo *,  lsradata *, int);
 227
 228 void lsra_join_lifetimes( methodinfo *, lsradata *, int);
 229 void lsra_calc_lifetime_length(methodinfo *, lsradata *, codegendata *);
 230
 231 void _lsra_new_stack( lsradata *, stackptr , int , int, int);
 232 void _lsra_from_stack(lsradata *, stackptr , int , int, int);
 233 void lsra_add_ss(struct lifetime *, stackptr );
 234 void lsra_usage_local(lsradata *, s4 , int , int , int , int );
 235
 236 void _lsra_main( methodinfo *, lsradata *, int *, int, struct lsra_register *, int *);
 237 void lsra_expire_old_intervalls(methodinfo *, lsradata *, struct lifetime *, struct lsra_register *);
 238 void _lsra_expire_old_intervalls(methodinfo *, struct lifetime *, struct lsra_register *, struct active_lt **/* , int * */);
 239 void spill_at_intervall(methodinfo *, lsradata *, struct lifetime *);
 240 void _spill_at_intervall(struct lifetime *, struct active_lt **);
 241 void lsra_add_active(struct lifetime *, struct active_lt **);
 242 void lsra_alloc(methodinfo *, registerdata *, struct lsradata *, int *, int, int *);
 243 int lsra_getmem(struct lifetime *, struct freemem *, int *);
 244 struct freemem *lsra_getnewmem(int *);
 245 void lsra_align_stackslots(struct lsradata *, stackptr, stackptr);
 246 void lsra_setflags(int *, int);
 247
 248 #endif /* _LSRA_H */
 249
 250
 251 /*
 252  * These are local overrides for various environment variables in Emacs.
 253  * Please do not remove this and leave it at the end of the file, where
 254  * Emacs will automagically detect them.
 255  * ---------------------------------------------------------------------
 256  * Local variables:
 257  * mode: c
 258  * indent-tabs-mode: t
 259  * c-basic-offset: 4
 260  * tab-width: 4
 261  * End:
 262  */