1 /* src/vm/jit/lsra.h - linear scan register allocator header
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
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 2297 2005-04-13 12:50:07Z christian $
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 #define JOIN_DEST_STACK
45 #define JOIN_DUP_STACK
50 #define USAGE_COUNT /* influence LSRA with usagecount */
51 #define USAGE_PER_INSTR /* divide usagecount by lifetimelength */
63 #define LSRA_PRINTLIFETIMES
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 */
81 #define min(a,b) ((a)<(b)?(a):(b))
82 #define max(a,b) ((a)<(b)?(b):(a))
92 struct _backedge *next;
96 int i_start; /* instruction number of first use */
97 int i_end; /* instruction number of last use */
98 int v_index; /* local variable index or negative for stackslots */
99 int type; /* TYPE_??? or -1 for unused lifetime */
100 long usagecount; /* number of references*/
101 int reg; /* regoffset durch lsra zugewiesen */
104 struct stackslot *local_ss; /* Stackslots for this Lifetime or NULL (=="pure" Local Var) */
109 /* struct lifetime *next; */
114 struct active_lt *next;
132 struct stackslot *next;
135 struct lsra_register {
155 #if defined(LSRA_USES_REG_RES)
156 int reg_res_free[REG_RES_CNT];
158 struct _list **succ; /* CFG successors*/
159 struct _list **pred; /* CFG predecessors */
160 int *num_pred; /* CFG number of predecessors */
161 int *sorted; /* BB sorted in reverse post order */
162 int *sorted_rev; /* BB reverse of sorted */
163 struct _backedge **backedge;
170 int maxlifetimes; /* copy from methodinfo to prevent passing methodinfo as parameter */
171 struct lifetime *lifetime; /* array of lifetimes */
172 int *lt_used; /* index to lifetimearray for used lifetimes */
174 int *lt_int; /* index to lifetimearray for int lifetimes */
176 int *lt_flt; /* index to lifetimearray for float lifetimes */
178 int *lt_rest; /* index to lifetimearray for all lifetimes not to be allocated in registers */
181 struct active_lt *active_tmp, *active_sav;
183 struct lsra_exceptiontable *ex;
192 struct freemem *next;
195 typedef struct lsradata lsradata;
197 /* function prototypes */
198 bool lsra(methodinfo *, codegendata *, registerdata *,t_inlining_globals *);
199 bool lsra_test(methodinfo *, codegendata *);
200 void lsra_init(methodinfo *, codegendata *, t_inlining_globals *, lsradata *);
201 bool lsra_setup(methodinfo *, codegendata *, registerdata *, lsradata *);
202 void lsra_main(methodinfo *, lsradata *, registerdata *, codegendata *);
203 void lsra_clean_Graph( methodinfo *, codegendata *, lsradata *);
206 void lsra_dump_stack(stackptr );
208 #ifdef LSRA_PRINTLIFETIMES
209 void print_lifetimes(registerdata *, lsradata *, int *, int);
212 void test_lifetimes( methodinfo *, lsradata *, registerdata *);
215 void lsra_reg_setup(methodinfo *m ,registerdata *,struct lsra_register *,struct lsra_register * );
218 void lsra_scan_registers_canditates(methodinfo *, lsradata *, int);
220 void lsra_join_lifetimes( methodinfo *, lsradata *, int);
221 void lsra_calc_lifetime_length(methodinfo *, lsradata *, codegendata *);
223 void _lsra_new_stack( lsradata *, stackptr , int , int, int);
224 void _lsra_from_stack(lsradata *, stackptr , int , int, int);
225 void lsra_add_ss(struct lifetime *, stackptr );
226 void lsra_usage_local(lsradata *, s4 , int , int , int , int );
228 void _lsra_main( methodinfo *, lsradata *, int *, int, struct lsra_register *, int *);
229 void lsra_expire_old_intervalls(methodinfo *, lsradata *, struct lifetime *, struct lsra_register *);
230 void _lsra_expire_old_intervalls(methodinfo *, struct lifetime *, struct lsra_register *, struct active_lt **/* , int * */);
231 void spill_at_intervall(methodinfo *, lsradata *, struct lifetime *);
232 void _spill_at_intervall(struct lifetime *, struct active_lt **);
233 void lsra_add_active(struct lifetime *, struct active_lt **);
234 void lsra_alloc(methodinfo *, registerdata *, struct lsradata *, int *, int, int *);
235 int lsra_getmem(struct lifetime *, struct freemem *, int *);
236 struct freemem *lsra_getnewmem(int *);
237 void lsra_align_stackslots(struct lsradata *, stackptr, stackptr);
238 void lsra_setflags(int *, int);
244 * These are local overrides for various environment variables in Emacs.
245 * Please do not remove this and leave it at the end of the file, where
246 * Emacs will automagically detect them.
247 * ---------------------------------------------------------------------
250 * indent-tabs-mode: t