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 2211 2005-04-04 10:39:36Z 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_EDX */
  42 /*  #define LSRA_TESTLT */
  43 /* #define LSRA_LEAF */
  44 #define JOIN_DEST_STACK
  45 #define JOIN_DUP_STACK
  46 #define LSRA_DO_SR
  47 #define LSRA_DO_EX
  48
  49
  50 #define USAGE_COUNT        /* influence LSRA with usagecount */
  51 #define USAGE_PER_INSTR    /* divide usagecount by lifetimelength */
  52
  53 #ifdef LSRA_DEBUG
  54 #undef LSRA_LEAF
  55 #endif
  56
  57 #ifdef LSRA_TESTLT
  58 #define VS 999999
  59 #endif
  60
  61
  62 #ifdef LSRA_DEBUG
  63 #define LSRA_PRINTLIFETIMES
  64 #endif
  65
  66 #define LSRA_BB_IN 3
  67 #define LSRA_BB_OUT 2
  68 #define LSRA_STORE 1
  69 #define LSRA_LOAD 0
  70 #define LSRA_POP -1
  71
  72 /* join types and flags*/
  73 #define JOIN     0           /* join that are not in any way dangerous */
  74 #define JOIN_BB  1           /* join Stackslots over Basic Block Boundaries */
  75 #define JOIN_DUP 2           /* join of two possibly concurring lifeteimes through DUP* */
  76 #define JOIN_OP  4           /* join of src operand with dst operand on i386 and x86_64 architecture */
  77                              /* JOIN_DUP and JOIN_OP is mutually exclusive as JOIN_OP and JOIN_BB    */
  78 #define JOINING  8           /* set while joining for DUP or OP to prevent assignement to a */
  79                              /* REG_RES before all involved lifetimes have been seen fully  */
  80
  81 #define min(a,b) ((a)<(b)?(a):(b))
  82 #define max(a,b) ((a)<(b)?(b):(a))
  83
  84 #if defined(LSRA_EDX)
  85 #define REG_RES_COUNT 3
  86 /* struct tmp_reg { */
  87 /*      int eax; */
  88 /*      int ecx; */
  89 /*      int edx; */
  90 /* }; */
  91
  92 extern int icmd_uses_tmp[256][REG_RES_COUNT+1];
  93 extern int lsra_reg_res[REG_RES_COUNT];
  94 #endif
  95
  96 struct _list {
  97         int value;
  98         struct _list *next;
  99 };
 100
 101 struct _backedge {
 102         int start;
 103         int end;
 104         struct _backedge *next;
 105 };
 106
 107 struct lifetime {
 108         int i_start; /* instruction number of first use */
 109         int i_end; /* instruction number of last use */
 110         int v_index; /* local variable index or negative for stackslots */
 111         int type; /* TYPE_??? or -1 for unused lifetime */
 112         long usagecount; /* number of references*/
 113         int reg; /* regoffset durch lsra zugewiesen */
 114         int savedvar;
 115         int flags;
 116         struct stackslot *local_ss; /* Stackslots for this Lifetime or NULL (=="pure" Local Var) */
 117         int bb_last_use;
 118         int i_last_use;
 119         int bb_first_def;
 120         int i_first_def;
 121 /*      struct lifetime *next; */
 122 };
 123
 124 struct active_lt {
 125         struct lifetime *lt;
 126         struct active_lt *next;
 127 };
 128
 129 struct l_loop {
 130         int b_first;
 131         int b_last;
 132         int nesting;
 133 };
 134
 135 struct b_loop {
 136         int loop;
 137         int instr;
 138 };
 139
 140
 141 struct stackslot {
 142         stackptr s;
 143         int bb;
 144         struct stackslot *next;
 145 };
 146
 147 struct lsra_register {
 148         int *sav_reg;
 149         int *tmp_reg;
 150         int *nregdesc;
 151         int sav_top;
 152         int tmp_top;
 153 };
 154
 155 struct lsra_reg {
 156         int reg_index;
 157         int use;
 158 };
 159
 160 struct _sbr {
 161         int header;
 162         struct _list *ret;
 163         struct _sbr *next;
 164 };
 165
 166 struct lsradata {
 167 #if defined(LSRA_EDX)
 168         int reg_res_free[REG_RES_COUNT];
 169 #endif
 170         struct _list **succ; /* CFG successors*/
 171         struct _list **pred; /* CFG predecessors */
 172         int *num_pred;       /* CFG number of predecessors */
 173         int *sorted;         /* BB sorted in reverse post order */
 174         int *sorted_rev;     /* BB reverse of sorted */
 175         struct _backedge **backedge;
 176         int backedge_count;
 177
 178         struct _sbr sbr;
 179
 180         long *nesting;
 181
 182         int maxlifetimes; /* copy from methodinfo to prevent passing methodinfo as parameter */
 183         struct lifetime *lifetime; /* array of lifetimes */
 184         int *lt_used; /* index to lifetimearray for used lifetimes */
 185         int lifetimecount;
 186         int *lt_int; /* index to lifetimearray for int lifetimes */
 187         int lt_int_count;
 188         int *lt_flt; /* index to lifetimearray for float lifetimes */
 189         int lt_flt_count;
 190         int *lt_rest; /* index to lifetimearray for all lifetimes not to be allocated in registers */
 191         int lt_rest_count;
 192
 193         struct active_lt *active_tmp, *active_sav;
 194
 195         struct lsra_exceptiontable *ex;
 196         int icount_max;
 197         int end_bb;
 198         int v_index;
 199 };
 200
 201 struct freemem {
 202         int off;
 203         int end;
 204         struct freemem *next;
 205 };
 206
 207 typedef struct lsradata lsradata;
 208
 209 /* function prototypes */
 210 bool lsra(methodinfo *, codegendata *, registerdata *,t_inlining_globals *);
 211 bool lsra_test(methodinfo *, codegendata *);
 212 void lsra_init(methodinfo *, codegendata *, t_inlining_globals *, lsradata *);
 213 bool lsra_setup(methodinfo *, codegendata *, registerdata *, lsradata *);
 214 void lsra_main(methodinfo *, lsradata *, registerdata *, codegendata *);
 215 void lsra_clean_Graph( methodinfo *, codegendata *, lsradata *);
 216
 217 #ifdef LSRA_DEBUG
 218 void lsra_dump_stack(stackptr );
 219 #endif
 220 #ifdef LSRA_PRINTLIFETIMES
 221 void print_lifetimes(registerdata *, lsradata *, int *, int);
 222 #endif
 223 #ifdef LSRA_TESTLT
 224 void test_lifetimes( methodinfo *, lsradata *, registerdata *);
 225 #endif
 226
 227 void lsra_reg_setup(methodinfo *m ,registerdata *,struct lsra_register *,struct lsra_register * );
 228
 229
 230 void lsra_scan_registers_canditates(methodinfo *,  lsradata *, int);
 231
 232 void lsra_join_lifetimes( methodinfo *, lsradata *, int);
 233 void lsra_calc_lifetime_length(methodinfo *, lsradata *, codegendata *);
 234
 235 void _lsra_new_stack( lsradata *, stackptr , int , int, int);
 236 void _lsra_from_stack(lsradata *, stackptr , int , int, int);
 237 void lsra_add_ss(struct lifetime *, stackptr );
 238 void lsra_usage_local(lsradata *, s4 , int , int , int , int );
 239
 240 void _lsra_main( methodinfo *, lsradata *, int *, int, struct lsra_register *, int *);
 241 void lsra_expire_old_intervalls(methodinfo *, lsradata *, struct lifetime *, struct lsra_register *);
 242 void _lsra_expire_old_intervalls(methodinfo *, struct lifetime *, struct lsra_register *, struct active_lt **/* , int * */);
 243 void spill_at_intervall(methodinfo *, lsradata *, struct lifetime *);
 244 void _spill_at_intervall(struct lifetime *, struct active_lt **);
 245 void lsra_add_active(struct lifetime *, struct active_lt **);
 246 void lsra_alloc(methodinfo *, registerdata *, struct lsradata *, int *, int, int *);
 247 int lsra_getmem(struct lifetime *, struct freemem *, int *);
 248 struct freemem *lsra_getnewmem(int *);
 249 void lsra_align_stackslots(struct lsradata *, stackptr, stackptr);
 250 void lsra_setflags(int *, int);
 251
 252 #endif /* _LSRA_H */
 253
 254
 255 /*
 256  * These are local overrides for various environment variables in Emacs.
 257  * Please do not remove this and leave it at the end of the file, where
 258  * Emacs will automagically detect them.
 259  * ---------------------------------------------------------------------
 260  * Local variables:
 261  * mode: c
 262  * indent-tabs-mode: t
 263  * c-basic-offset: 4
 264  * tab-width: 4
 265  * End:
 266  */