src/vm/jit/lsra.h

   1 /* jit/lsra.inc - linear scan register allocator header
   2
   3    Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
   4    Institut f. Computersprachen, TU Wien
   5    R. Grafl, A. Krall, C. Kruegel, C. Oates, R. Obermaisser, M. Probst,
   6    S. Ring, E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich,
   7    J. Wenninger, C. Ullrich
   8
   9    This file is part of CACAO.
  10
  11    This program is free software; you can redistribute it and/or
  12    modify it under the terms of the GNU General Public License as
  13    published by the Free Software Foundation; either version 2, or (at
  14    your option) any later version.
  15
  16    This program is distributed in the hope that it will be useful, but
  17    WITHOUT ANY WARRANTY; without even the implied warranty of
  18    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19    General Public License for more details.
  20
  21    You should have received a copy of the GNU General Public License
  22    along with this program; if not, write to the Free Software
  23    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  24    02111-1307, USA.
  25
  26    Contact: cacao@complang.tuwien.ac.at
  27
  28    Authors: Christian Ullrich
  29
  30    $Id: lsra.h 1953 2005-02-17 13:42:23Z christian $
  31
  32 */
  33
  34
  35 #ifndef _LSRA_H
  36 #define _LSRA_H
  37
  38 #include "vm/jit/loop/loop.h"
  39
  40 /* #define LSRA_DEBUG */
  41 /* #define LSRA_SAVEDVAR */
  42 /* #define LSRA_MEMORY */
  43 /* #define LSRA_PRINTLIFETIMES */
  44 /* #define LSRA_EDX */
  45 /* #define LSRA_TESTLT */ /* not to be used with register allocation - only INMEMORY */
  46 /* #define LSRA_DUMP_LOOPDATA */
  47
  48
  49 #ifdef LSRA_DEBUG
  50 #define LSRA_PRINTLIFETIMES
  51 #endif
  52
  53 #define LSRA_STORE 1
  54 #define LSRA_LOAD 0
  55 #define LSRA_POP -1
  56
  57 struct lifetime {
  58         int i_start; /* instruction number of first use */
  59         int i_end; /* instruction number of last use */
  60         int v_index; /* local variable index or negative for stackslots */
  61         int type;
  62         int usagecount; /* number of references*/
  63         int reg; /* regoffset durch lsra zugewiesen */
  64         int savedvar;
  65         struct stackslot *passthrough; /* List of Stackslots in Lifetime, which are passed through a Basic Block */
  66         struct stackslot *local_ss; /* Stackslots for this Lifetime or NULL (=="pure" Local Var) */
  67         struct _i_list *i_list; /* list of instructions with references to var */
  68         struct lifetime *next;
  69 };
  70
  71 struct active_lt {
  72         struct lifetime *lt;
  73         struct active_lt *next;
  74 };
  75
  76 struct l_loop {
  77         int b_first;
  78         int b_last;
  79         int nesting;
  80 };
  81
  82 struct b_loop {
  83         int loop;
  84         int instr;
  85 };
  86
  87 struct _i_list {
  88         int b_index;
  89         int instr;
  90         int store;
  91         struct _i_list *next;
  92 };
  93
  94 struct stackslot {
  95         stackptr s;
  96         int bb;
  97         struct stackslot *next;
  98 };
  99
 100 struct lsra_reg {
 101         int reg_index;
 102         int use;
 103 };
 104
 105 struct lsradata {
 106         struct lifetime **ss_lifetimes;
 107         struct lifetime **locals_lifetimes;
 108         struct lifetime *lifetimes;
 109         struct stackslot *stackslots;
 110         struct active_lt *active_tmp, *active_sav;
 111         int active_sav_count, active_tmp_count;
 112         struct lsra_exceptiontable *ex;
 113         int icount_max;
 114 };
 115
 116 struct freemem {
 117         int off;
 118         int end;
 119         struct freemem *next;
 120 };
 121
 122 struct dup {
 123         struct stackslot *ss;
 124         struct dup *next;
 125 };
 126
 127 struct tmp_reg {
 128         int eax;
 129         int ecx;
 130         int edx;
 131 };
 132
 133 struct lsra_exceptiontable {
 134         int handler_min;
 135         int handler_max;
 136         int guarded_min;
 137         int guarded_max;
 138 };
 139
 140 typedef struct lsradata lsradata;
 141
 142 /* function prototypes */
 143 bool lsra(methodinfo *, codegendata *, registerdata *, loopdata *, t_inlining_globals *);
 144 bool lsra_test(methodinfo *, codegendata *);
 145 void lsra_init(methodinfo *, codegendata *, t_inlining_globals *, lsradata *);
 146 bool lsra_setup(methodinfo *, codegendata *, registerdata *, lsradata *, loopdata *);
 147 void lsra_main(methodinfo *, lsradata *, registerdata *, codegendata *, loopdata *ld);
 148 void lsra_clean_Graph( methodinfo *, codegendata *, lsradata *, loopdata *);
 149
 150 #if defined(LSRA_DEBUG) || defined(LSRA_DUMP_LOOPDATA)
 151 void lsra_dump_Graph(methodinfo *, struct depthElement **);
 152 #endif
 153 #ifdef LSRA_DEBUG
 154 void lsra_dump_stack(stackptr );
 155 #endif
 156 #ifdef LSRA_PRINTLIFETIMES
 157 void print_lifetimes(registerdata *, lsradata *, struct lifetime *);
 158 #endif
 159
 160 int lsra_get_sbr_end(methodinfo *, loopdata *, int , int *);
 161 void lsra_mark_blocks(methodinfo *,struct depthElement **, int *, int , int *);
 162 int lsra_get_exmaxblock(methodinfo *, loopdata *, int );
 163 void lsra_setup_exceptiontable( methodinfo *, codegendata *, loopdata *, lsradata *);
 164 void _df( struct depthElement **, int , bool *, int *, bool *, int *);
 165
 166 void lsra_scan_registers_canditates(methodinfo *, loopdata *, lsradata *);
 167 void lsra_jump( methodinfo *, loopdata *, int, int );
 168 void lsra_jump_init( methodinfo *, loopdata *);
 169 void lsra_sbr_call ( int , int );
 170 void lsra_sbr_ret( int );
 171
 172 void lsra_join_lifetimes( methodinfo *, codegendata *, lsradata *, loopdata *);
 173 void lsra_calc_lifetime_length(methodinfo *, lsradata *, codegendata *, loopdata *);
 174
 175 void lsra_merge_i_lists(struct lifetime *, struct lifetime *);
 176 void lsra_merge_local_ss(struct lifetime *, struct lifetime *);
 177
 178 void _lsra_new_stack( lsradata *, stackptr , int , int, int);
 179 void _lsra_from_stack(lsradata *, stackptr , int , int, int);
 180 void lsra_add_ss(struct lifetime *, stackptr );
 181 void lsra_usage_local(lsradata *, s4 , int , int , int , int );
 182 void lsra_new_local(lsradata *, s4 , int );
 183 struct _i_list *lsra_add_i_list(struct _i_list *, int, int ,int );
 184
 185 void lsra_sort_lt(struct lifetime **);
 186 void _lsra_main( methodinfo *, lsradata *, struct lifetime *, struct lsra_reg *, int , int , int *, int *);
 187 void lsra_expire_old_intervalls(lsradata *, struct lifetime *, struct lsra_reg *);
 188 void _lsra_expire_old_intervalls(struct lifetime *, struct lsra_reg *, struct active_lt **, int *);
 189 void spill_at_intervall(lsradata *, struct lifetime *);
 190 void _spill_at_intervall(struct lifetime *, struct active_lt **, int *);
 191 void lsra_add_active(struct lifetime *, struct active_lt **, int *);
 192 void lsra_alloc(methodinfo *, registerdata *, struct lifetime *, int *);
 193 int lsra_getmem(struct lifetime *, struct freemem *, int *);
 194 struct freemem *lsra_getnewmem(int *);
 195 void lsra_align_stackslots(struct lsradata *, stackptr, stackptr);
 196 void lsra_setflags(int *, int);
 197
 198 #ifdef LSRA_TESTLT
 199 void test_lifetimes( methodinfo *m, loopdata *ld, lsradata *ls, struct lifetime *lifet, codegendata *cd);
 200 int _test_lifetimes(methodinfo *m, loopdata *ld, lsradata *ls, int b_index, int *values, bool* bb_visited, struct lifetime *lifet);
 201 #endif
 202
 203 #endif /* _LSRA_H */
 204
 205
 206 /*
 207  * These are local overrides for various environment variables in Emacs.
 208  * Please do not remove this and leave it at the end of the file, where
 209  * Emacs will automagically detect them.
 210  * ---------------------------------------------------------------------
 211  * Local variables:
 212  * mode: c
 213  * indent-tabs-mode: t
 214  * c-basic-offset: 4
 215  * tab-width: 4
 216  * End:
 217  */