1 /* vm/jit/loop/loop.h - array bound removal header
3 Copyright (C) 1996-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: Christopher Kruegel
29 Changes: Christian Thalinger
31 $Id: loop.h 4357 2006-01-22 23:33:38Z twisti $
42 #include "vm/global.h"
43 #include "vm/method.h"
44 #include "vm/jit/jit.h"
47 /* Different types for struct Trace */
48 #define TRACE_UNKNOWN 0 /* unknown */
49 #define TRACE_ICONST 1 /* integer constant value */
50 #define TRACE_ALENGTH 2 /* array length value */
51 #define TRACE_IVAR 3 /* integer variable reference */
52 #define TRACE_AVAR 4 /* object (array) reference */
54 /* The ways a variable can be used in a loop */
55 #define ARRAY_INDEX 0 /* var used as array index */
56 #define VAR_MOD 1 /* var changes its value */
58 /* The way, integer variables change their values */
59 #define D_UP 0 /* var is only increased */
60 #define D_DOWN 1 /* var is only decreased */
61 #define D_UNKNOWN 2 /* not known */
63 /* The different types of operators in loop conditions */
64 #define OP_EQ 0 /* operator: == */
65 #define OP_LT 1 /* operator: < */
66 #define OP_GE 2 /* operator: >= */
67 #define OP_UNKNOWN 3 /* operator: unknown */
69 /* Possible types of static tests (constraints) in struct Constraint */
71 #define TEST_ZERO 0 /* check variable against const. lower bound*/
72 #define TEST_ALENGTH 1 /* check variable against array length */
73 #define TEST_CONST_ZERO 2 /* check constant against const. lower bound*/
74 #define TEST_CONST_ALENGTH 3 /* check variable against array length */
75 #define TEST_UNMOD_ZERO 4 /* check var. that is constant in loop against*/
76 /* constant lower bound */
77 #define TEST_UNMOD_ALENGTH 5 /* check var. that is constant in loop against*/
79 #define TEST_RS_ZERO 6 /* check constant part of loop condition against*/
80 /* constant lower bound */
81 #define TEST_RS_ALENGTH 7 /* check constant part of loop condition against*/
84 /* Possible types of bound check optimizations */
85 #define OPT_UNCHECKED 0 /* access not checked yet - first visit */
86 #define OPT_NONE 1 /* no optimization */
87 #define OPT_FULL 2 /* fully remove bound check */
88 #define OPT_LOWER 3 /* remove check againt zero */
89 #define OPT_UPPER 4 /* remove check against array length */
91 /* The different ways, remove_boundcheck(.) can be called */
92 #define BOUNDCHECK_REGULAR 0 /* perform regular optimization */
93 #define BOUNDCHECK_SPECIAL 1 /* only optimize header node - and ignore */
94 /* information from loop condition */
96 #define LOOP_PART 0x1 /* a flag that marks a BB part of a loop */
97 #define HANDLER_PART 0x2 /* a flag that marks a BB part of ex-handler */
98 #define HANDLER_VISITED 0x4 /* flag to prevent loop if copying catch blocks */
101 typedef struct LoopElement LoopElement;
102 typedef struct LoopContainer LoopContainer;
103 typedef struct loopdata loopdata;
106 /* This struct records information about interesting vars (vars that are modified
107 or used as an array index in loops.
110 int value; /* reference to array of local variables */
111 int modified; /* set if value of var is changed */
112 int index; /* set if var is used as array index */
113 int static_l; /* var is never decremented -> static lower */
115 int static_u; /* var is never incremented -> static upper */
118 int dynamic_l_v; /* variable is left side of loop condition in */
119 /* variable + dynamic_l >= right side */
121 int dynamic_u_v; /* variable is left side of loop condition in */
122 /* variable + dynamic_u < right side */
123 struct LoopVar *next; /* list pointer */
127 /* This struct records the needed static test of variables before loop entry. */
129 int type; /* type of test to perform */
130 int arrayRef; /* array reference involved in test (if any) */
131 int varRef; /* which variable to test (if involved) */
132 int constant; /* which constant to test (if involved) */
133 struct Constraint *next; /* list pointer */
137 /* This structure is used to record variables that change their value in loops. */
139 int var; /* variable involved */
140 int lower_bound; /* a minimum lower bound that is guaranteed */
141 int upper_bound; /* a maximum upper bound that is guaranteed */
142 /* IMPORTANT: if lower_bound > upper_bound */
143 /* there are no guarantees at all */
147 /* This struct is used to build the control flow graph and stores the variable
148 changes at the beginning of each basic block.
150 struct depthElement {
151 int value; /* number of successor of this block */
152 struct depthElement *next; /* list pointer */
153 struct Changes **changes; /* pointer to array of variable changes */
157 /* Used to build a list of all basicblock, the loop consists of */
167 This structure stores informations about a single loop
169 struct LoopContainer {
170 s4 toOpt; /* does this loop need optimization */
171 LoopElement *nodes; /* list of BBs this loop consists of */
173 s4 in_degree; /* needed to topological sort loops to*/
174 /* get the order of optimizing them */
175 LoopContainer *next; /* list pointer */
176 LoopContainer *parent; /* points to parent loop, if this BB */
177 /* is head of a loop */
178 LoopContainer *tree_right; /* used for tree hierarchie of loops */
179 LoopContainer *tree_down;
180 exceptiontable *exceptions; /* list of exception in that loop */
185 /* modified by graph.c */
187 int *c_defnum; /* array that stores a number for each node when*/
188 /* control flow graph is traveres depth first */
189 int *c_parent; /* for each node that array stores its parent */
190 int *c_reverse; /* for each def number that array stores the */
191 /* corresponding node */
192 int c_globalCount; /* counter for def numbering */
193 int *c_numPre; /* array that stores for each node its number */
195 int **c_pre; /* array of array that stores predecessors */
196 int c_last_jump; /* stores the source node of the last jsr instr */
197 struct basicblock *c_last_target; /* stores the source BB of the last jsr instr */
199 struct depthElement **c_dTable; /* adjacency list for control flow graph */
200 struct depthElement **c_exceptionGraph; /* adjacency list for exception graph */
202 struct LoopContainer *c_allLoops; /* list of all loops */
203 struct LoopContainer *c_loop_root; /* root of loop hierarchie tree */
205 int *c_exceptionVisit; /* array that stores a flag for each node part */
206 /* of the exception graph */
208 /* modified by loop.c */
210 int *c_semi_dom; /* store for each node its semi dominator */
211 int *c_idom; /* store for each node its dominator */
212 int *c_same_dom; /* temp array to hold nodes with same dominator */
213 int *c_ancestor; /* store for each node its ancestor with lowest */
218 int *c_contains; /* store for each node whether it's part of loop*/
219 int *c_stack; /* a simple stack as array */
220 int c_stackPointer; /* stackpointer */
223 /* modified by analyze.c */
225 struct LoopContainer *root; /* the root pointer for the hierarchie tree of */
226 /* all loops in that procedure */
228 int c_needed_instr; /* number of instructions that have to be */
229 /* inserted before loop header to make sure */
230 /* array optimization is legal */
231 int c_rs_needed_instr; /* number of instructions needed to load the */
232 /* value ofthe right side of the loop condition */
233 int *c_nestedLoops; /* store for each node the header node of the */
234 /* loop this node belongs to, -1 for none */
235 int *c_hierarchie; /* store a loop hierarchie */
236 int *c_toVisit; /* set for each node that is part of the loop */
238 int *c_current_loop; /* for each node: */
239 /* store 0: node is not part of loop */
240 /* store 1: node is loop header */
241 /* store 2: node is in loop but not part of any */
243 /* store 3: node is part of nested loop */
245 int c_current_head; /* store number of node that is header of loop */
246 int *c_var_modified; /* store for each local variable whether its */
247 /* value is changed in the loop */
249 struct Trace *c_rightside; /* right side of loop condition */
250 struct Constraint **c_constraints;
251 /* array that stores for each variable a list */
252 /* static tests (constraints) that have to be */
253 /* performed before loop entry */
254 /* IMPORTANT: c_constraints[maxlocals] stores */
255 /* the tests for constants and the */
256 /* right side of loop condition */
258 struct LoopVar *c_loopvars; /* a list of all intersting variables of the */
259 /* current loop (variables that are modified or */
260 /* used as array index */
262 struct basicblock *c_first_block_copied; /* pointer to the first block, that is copied */
263 /* during loop duplication */
265 struct basicblock *c_last_block_copied; /* last block, that is copied during loop */
268 int *c_null_check; /* array to store for local vars, whether they */
269 /* need to be checked against the null reference*/
270 /* in the loop head */
272 bool c_needs_redirection; /* if a loop header is inserted as first block */
273 /* into the global BB list, this is set to true */
275 struct basicblock *c_newstart; /* if a loop header is inserted as first block */
276 /* into the gloal BB list, this pointer is the */
278 int c_old_xtablelength; /* used to store the original tablelength */
284 /* declare statistic variables */
285 #ifdef ENABLE_STATISTICS
287 int c_stat_num_loops; /* number of loops */
289 /* statistics per loop */
290 int c_stat_array_accesses; /* number of array accesses */
292 int c_stat_full_opt; /* number of fully optimized accesses */
293 int c_stat_no_opt; /* number of not optimized accesses */
294 int c_stat_lower_opt; /* number of accesses where check against zero */
296 int c_stat_upper_opt; /* number of accesses where check against array */
297 /* lengh is removed */
298 int c_stat_or; /* set if optimization is cancelled because of */
299 /* or in loop condition */
300 int c_stat_exception; /* set if optimization is cancelled because of */
301 /* index var modified in catch block */
303 /* statistics per procedure */
304 int c_stat_sum_accesses; /* number of array accesses */
306 int c_stat_sum_full; /* number of fully optimized accesses */
307 int c_stat_sum_no; /* number of not optimized accesses */
308 int c_stat_sum_lower; /* number of accesses where check against zero */
310 int c_stat_sum_upper; /* number of accesses where check against array */
311 /* lengh is removed */
312 int c_stat_sum_or; /* set if optimization is cancelled because of */
313 /* or in loop condition */
314 int c_stat_sum_exception; /* set if optimization is cancelled because of */
320 /* function prototypes ********************************************************/
322 void analyseGraph(methodinfo *m, loopdata *ld);
323 void c_mem_error(void);
329 * These are local overrides for various environment variables in Emacs.
330 * Please do not remove this and leave it at the end of the file, where
331 * Emacs will automagically detect them.
332 * ---------------------------------------------------------------------
335 * indent-tabs-mode: t