1 /* src/vm/jit/allocator/lsra.h - linear scan register allocator header
3 Copyright (C) 2005, 2006 R. Grafl, A. Krall, C. Kruegel,
4 C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
5 E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
6 J. Wenninger, 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., 51 Franklin Street, Fifth Floor, Boston, MA
25 Contact: cacao@cacaojvm.org
27 Authors: Christian Ullrich
29 Changes: Edwin Steiner
41 # define LSRA_DEBUG_CHECK
42 # define LSRA_DEBUG_VERBOSE
45 #ifdef SSA_DEBUG_CHECK
46 # define _LSRA_CHECK_BOUNDS(i,l,h) assert( ((i) >= (l)) && ((i) < (h)));
47 # define _LSRA_ASSERT(a) assert((a));
49 # define _LSRA_CHECK_BOUNDS(i,l,h)
50 # define _LSRA_ASSERT(a)
53 /* #define LSRA_DEBUG */ /* lsra debug messages */
54 /* #define LSRA_SAVEDVAR */
55 /* #define LSRA_MEMORY */
56 #if defined(__I386__) || defined(__X86_64__)
57 #define JOIN_DEST_STACK /* The destination stackslot gets the same */
58 /* register as one of the src stackslots. Important for i386 & X86_64 */
59 /* since they do not have "3 operand" arithmetic instructions to */
60 /* prevent usage of a reserved register (REG_ITMPX) */
62 #define JOIN_DUP_STACK /* join "identical" stackslots created by dup* */
64 #define USAGE_COUNT /* influence LSRA with usagecount */
65 #define USEAGE_COUNT_EXACT /* search all active lifetimes and regard */
67 #define USAGE_PER_INSTR /* divide usagecount by lifetimelength */
75 /* join types and flags*/
76 #define JOIN 0 /* joins that are not in any way dangerous */
77 #define JOIN_BB 1 /* join Stackslots over Basic Block Boundaries */
78 #define JOIN_DUP 2 /* join of two possibly concurring lifeteimes through DUP* */
79 #define JOIN_OP 4 /* join of src operand with dst operand on i386 and x86_64 */
81 /* JOIN_DUP and JOIN_OP is mutually exclusive as JOIN_OP */
83 #define JOINING 8 /* set while joining for DUP or OP to prevent assignement */
84 /* to a REG_RES before all involved lifetimes have been */
87 #define min(a,b) ((a)<(b)?(a):(b))
88 #define max(a,b) ((a)<(b)?(b):(a))
99 struct _backedge *next;
103 int i_start; /* instruction number of first use */
104 int i_end; /* instruction number of last use */
105 int v_index; /* local variable index or negative for stackslots */
106 int type; /* TYPE_* or -1 for unused lifetime */
107 long usagecount; /* number of references*/
108 int reg; /* regoffset allocated by lsra*/
111 struct stackslot *local_ss; /* Stackslots for this Lifetime or NULL ( == */
112 /* "pure" Local Var) */
134 struct stackslot *next;
137 struct lsra_register {
151 int header; /* BB Index of subroutine start (SBR_HEADER) */
152 struct _list *ret; /* List of possible return BB indizes */
157 #if defined(LSRA_USES_REG_RES)
158 int reg_res_free[REG_RES_CNT];
160 struct _list **succ; /* CFG successors*/
161 struct _list **pred; /* CFG predecessors */
162 int *num_pred; /* CFG number of predecessors */
163 int *sorted; /* BB sorted in reverse post order */
164 int *sorted_rev; /* BB reverse lookup of sorted */
166 struct _backedge **backedge; /* backedge data structure */
167 int backedge_count; /* number of backedges */
169 struct _sbr sbr; /* list of subroutines, sorted by header */
171 long *nesting; /* Nesting level of BB*/
173 int maxlifetimes; /* copy from methodinfo to prevent passing methodinfo */
176 struct lifetime *lifetime; /* array of lifetimes */
177 int lifetimecount; /* number of lifetimes */
178 int *lt_used; /* index to lifetimearray for used lifetimes */
179 int *lt_int; /* index to lifetimearray for int lifetimes */
180 int lt_int_count; /* number of int/[lng]/[adr] lifetimes */
181 int *lt_flt; /* index to lifetimearray for float lifetimes */
182 int lt_flt_count; /* number of float/double lifetimes */
183 int *lt_mem; /* index to lifetimearray for all lifetimes */
184 /* not to be allocated in registers */
185 int lt_mem_count; /* number of this other lifetimes */
187 struct lifetime **active_tmp, **active_sav;
188 int active_tmp_top, active_sav_top;
190 struct lsra_exceptiontable *ex;
191 int v_index; /* next free index for stack slot lifetimes */
192 /* decrements from -1 */
199 struct freemem *next;
202 typedef struct lsradata lsradata;
205 /* function prototypes ********************************************************/
207 bool lsra(jitdata *jd);
213 * These are local overrides for various environment variables in Emacs.
214 * Please do not remove this and leave it at the end of the file, where
215 * Emacs will automagically detect them.
216 * ---------------------------------------------------------------------
219 * indent-tabs-mode: t
223 * vim:noexpandtab:sw=4:ts=4: