1 /* src/vm/jit/optimizing/lsra.h - linear scan register allocator header
3 Copyright (C) 2005, 2006 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
8 This file is part of CACAO.
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.
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.
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
25 Contact: cacao@complang.tuwien.ac.at
27 Authors: Christian Ullrich
29 $Id: lsra.h,v 1.17 2005/11/22 14:36:16 christian Exp $
37 #include "toolbox/bitvector.h"
42 # define LSRA_DEBUG_CHECK
43 # define LSRA_DEBUG_VERBOSE
46 #ifdef LSRA_DEBUG_CHECK
47 # define _LSRA_CHECK_BOUNDS(i,l,h) assert( ((i) >= (l)) && ((i) < (h)));
48 # define _LSRA_ASSERT(a) assert((a));
50 # define _LSRA_CHECK_BOUNDS(i,l,h)
51 # define _LSRA_ASSERT(a)
54 /* let LSRA allocate reserved registers (REG_ITMP[1|2|3]) */
56 /* #define LSRA_USES_REG_RES */
57 /* # include "vm/jit/i386/icmd_uses_reg_res.inc.h" */
60 /* #define LSRA_SAVEDVAR */
61 /* #define LSRA_MEMORY */
63 #define USAGE_COUNT /* influence LSRA with usagecount */
64 /* #define USAGE_PER_INSTR */ /* divide usagecount by lifetimelength */
68 #define min(a,b) ((a)<(b)?(a):(b))
69 #define max(a,b) ((a)<(b)?(b):(a))
78 int i_start; /* instruction number of first use */
79 int i_end; /* instruction number of last use */
80 int v_index; /* local variable index or negative for stackslots */
81 int type; /* TYPE_XXX or -1 for unused lifetime */
82 long usagecount; /* number of references*/
83 int regoff; /* regoffset allocated by lsra*/
86 /* struct stackslot *local_ss; */ /* Stackslots for this Lifetime or NULL ( == */
87 /* "pure" Local Var) */
95 struct site *last_use;
104 struct lsra_register {
118 int varcount; /* size of vars array */
119 int ssavarcount; /* ls->vars[0..ssavarcount[ are all locals and iovars */
120 /* they are regarded for ssa renaming */
121 /* the rest (ls->vars[ssavarcount..varcount[ are */
122 /* TEMP or PREALLOC vars with just on definition and */
123 /* use within one basicblock -> not of interest for */
124 /* ssa renaming procedures */
125 int vartop; /* next free var */
126 int varcount_with_indices;
127 int *new_varindex; /* new_varindex[0..jd->varcount[ points to the new */
128 /* unique index of ls->vars(maps jd->vars to ls->vars)*/
130 int *var_0; /* [0..ls->varcount] */
131 /* var_0[a] with a in [0..ls->varcount[ holds the */
133 /* var_0[ls->varcount] holds the number of vars with */
136 int *sorted; /* BB sorted in reverse post order */
137 int *sorted_rev; /* BB reverse lookup of sorted */
139 long *nesting; /* Nesting level of BB*/
141 struct lifetime *lifetime; /* array of lifetimes */
142 int lifetimecount; /* number of lifetimes */
143 int *lt_used; /* index to lifetimearray for used lifetimes */
144 int *lt_int; /* index to lifetimearray for int lifetimes */
145 int lt_int_count; /* number of int/[lng]/[adr] lifetimes */
146 int *lt_flt; /* index to lifetimearray for float lifetimes */
147 int lt_flt_count; /* number of float/double lifetimes */
148 int *lt_mem; /* index to lifetimearray for all lifetimes */
149 /* not to be allocated in registers */
150 int lt_mem_count; /* number of this other lifetimes */
152 struct lifetime **active_tmp, **active_sav;
153 int active_tmp_top, active_sav_top;
155 struct lsra_exceptiontable *ex;
158 bitvector *var_def; /* LocalVar Definition Bitvector [0..ls->bbcount] */
159 /* Bitvector holds ls->max_vars Bits */
160 bitvector *use_sites; /* LocalVar Use Bitvector[0..ls->maxvars] */
161 int **num_var_use; /* count of var_use[bb][var_index] */
162 int **var; /* [0..cd->maxlocal+cd->maxstack[[0..4] */
163 /* ssa_set_local_def and ssa_set_interface (called from analyse_stack) */
164 /* set var[local_index][local_type] and var[jd->maxlocals+stack_depth] */
165 /* [stack_type] to a unique type independend index [0..ls->max_vars[ */
166 /* unused entries are set to -1 */
168 int max_vars_with_indices;
169 int *num_defs; /* counts definitions of variables */
170 /* [0..jd->maxlocals*5+cd->maxstack*5[ */
171 /* valid for [0..ls->max_vars[ */
174 int *local_0; /* [0..ls->max_locals] */
175 /* local_0[a] with a in [0..ls->max_locals[ holds the */
177 /* local_0[ls->maxlocals] holds the number of local */
178 /* vars with indices */
179 int *interface_0; /* same here, just with interfaces */
181 int *var_to_index; /* var index to interface (<0) or local (>=0) index */
182 /* [0..jd->maxlocals*5+cd->maxstack*5[ */
183 /* valid for [0..ls->max_vars[ */
184 /* holds var_index or the negative interface index */
185 /* in ssa_Rename_init the indices are changed to the */
186 /* index of the corresponding first Var with index;) */
187 /* (== local_0[] or interface_0[] */
193 basicblock **basicblocks;
194 /* [0..ls->basicblockcount[[0..ls->max_locals[[0..ls->num_pre[bb]] */
195 /* 3rd index represents the the var involved in the phi function */
196 /* a0 = phi(a1,a2,...,a(ls->num_pre[bb]-1)) */
197 int ***phi; /* [0..ls->basicblockcount[[0..ls->max_vars[[0,1] */
198 /* if no phi function for a Basic Block and var exists */
199 /* phi[bb][a] == NULL */
201 int ***phi_moves; /* phi_moves[block_index][0..num_phi_moves[bi][0..1] */
205 int *count; /* Helpers for ssa_Rename */
215 struct freemem *next;
218 typedef struct lsradata lsradata;
220 /* function prototypes */
221 void lsra(jitdata *);
226 * These are local overrides for various environment variables in Emacs.
227 * Please do not remove this and leave it at the end of the file, where
228 * Emacs will automagically detect them.
229 * ---------------------------------------------------------------------
232 * indent-tabs-mode: t