1 /* src/vm/jit/loop/loop.h - array bound removal header
3 Copyright (C) 1996-2005, 2006, 2007, 2008
4 CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
6 This file is part of CACAO.
8 This program is free software; you can redistribute it and/or
9 modify it under the terms of the GNU General Public License as
10 published by the Free Software Foundation; either version 2, or (at
11 your option) any later version.
13 This program is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
32 #include "vm/global.h"
33 #include "vm/method.hpp"
35 #include "vm/jit/jit.hpp"
38 /* Different types for struct Trace */
39 #define TRACE_UNKNOWN 0 /* unknown */
40 #define TRACE_ICONST 1 /* integer constant value */
41 #define TRACE_ALENGTH 2 /* array length value */
42 #define TRACE_IVAR 3 /* integer variable reference */
43 #define TRACE_AVAR 4 /* object (array) reference */
45 /* The ways a variable can be used in a loop */
46 #define ARRAY_INDEX 0 /* var used as array index */
47 #define VAR_MOD 1 /* var changes its value */
49 /* The way, integer variables change their values */
50 #define D_UP 0 /* var is only increased */
51 #define D_DOWN 1 /* var is only decreased */
52 #define D_UNKNOWN 2 /* not known */
54 /* The different types of operators in loop conditions */
55 #define OP_EQ 0 /* operator: == */
56 #define OP_LT 1 /* operator: < */
57 #define OP_GE 2 /* operator: >= */
58 #define OP_UNKNOWN 3 /* operator: unknown */
60 /* Possible types of static tests (constraints) in struct Constraint */
62 #define TEST_ZERO 0 /* check variable against const. lower bound*/
63 #define TEST_ALENGTH 1 /* check variable against array length */
64 #define TEST_CONST_ZERO 2 /* check constant against const. lower bound*/
65 #define TEST_CONST_ALENGTH 3 /* check variable against array length */
66 #define TEST_UNMOD_ZERO 4 /* check var. that is constant in loop against*/
67 /* constant lower bound */
68 #define TEST_UNMOD_ALENGTH 5 /* check var. that is constant in loop against*/
70 #define TEST_RS_ZERO 6 /* check constant part of loop condition against*/
71 /* constant lower bound */
72 #define TEST_RS_ALENGTH 7 /* check constant part of loop condition against*/
75 /* Possible types of bound check optimizations */
76 #define OPT_UNCHECKED 0 /* access not checked yet - first visit */
77 #define OPT_NONE 1 /* no optimization */
78 #define OPT_FULL 2 /* fully remove bound check */
79 #define OPT_LOWER 3 /* remove check againt zero */
80 #define OPT_UPPER 4 /* remove check against array length */
82 /* The different ways, remove_boundcheck(.) can be called */
83 #define BOUNDCHECK_REGULAR 0 /* perform regular optimization */
84 #define BOUNDCHECK_SPECIAL 1 /* only optimize header node - and ignore */
85 /* information from loop condition */
87 #define LOOP_PART 0x1 /* a flag that marks a BB part of a loop */
88 #define HANDLER_PART 0x2 /* a flag that marks a BB part of ex-handler */
89 #define HANDLER_VISITED 0x4 /* flag to prevent loop if copying catch blocks */
92 typedef struct LoopElement LoopElement;
93 typedef struct LoopContainer LoopContainer;
94 typedef struct loopdata loopdata;
97 /* This struct records information about interesting vars (vars that are modified
98 or used as an array index in loops.
101 int value; /* reference to array of local variables */
102 int modified; /* set if value of var is changed */
103 int index; /* set if var is used as array index */
104 int static_l; /* var is never decremented -> static lower */
106 int static_u; /* var is never incremented -> static upper */
109 int dynamic_l_v; /* variable is left side of loop condition in */
110 /* variable + dynamic_l >= right side */
112 int dynamic_u_v; /* variable is left side of loop condition in */
113 /* variable + dynamic_u < right side */
114 struct LoopVar *next; /* list pointer */
118 /* This struct records the needed static test of variables before loop entry. */
120 int type; /* type of test to perform */
121 int arrayRef; /* array reference involved in test (if any) */
122 int varRef; /* which variable to test (if involved) */
123 int constant; /* which constant to test (if involved) */
124 struct Constraint *next; /* list pointer */
128 /* This structure is used to record variables that change their value in loops. */
130 int var; /* variable involved */
131 int lower_bound; /* a minimum lower bound that is guaranteed */
132 int upper_bound; /* a maximum upper bound that is guaranteed */
133 /* IMPORTANT: if lower_bound > upper_bound */
134 /* there are no guarantees at all */
138 /* This struct is used to build the control flow graph and stores the variable
139 changes at the beginning of each basic block.
141 struct depthElement {
142 int value; /* number of successor of this block */
143 struct depthElement *next; /* list pointer */
144 struct Changes **changes; /* pointer to array of variable changes */
148 /* Used to build a list of all basicblock, the loop consists of */
158 This structure stores informations about a single loop
160 struct LoopContainer {
161 s4 toOpt; /* does this loop need optimization */
162 LoopElement *nodes; /* list of BBs this loop consists of */
164 s4 in_degree; /* needed to topological sort loops to*/
165 /* get the order of optimizing them */
166 LoopContainer *next; /* list pointer */
167 LoopContainer *parent; /* points to parent loop, if this BB */
168 /* is head of a loop */
169 LoopContainer *tree_right; /* used for tree hierarchie of loops */
170 LoopContainer *tree_down;
171 exception_entry *exceptions; /* list of exception in that loop */
176 /* modified by graph.c */
178 int *c_defnum; /* array that stores a number for each node when*/
179 /* control flow graph is traveres depth first */
180 int *c_parent; /* for each node that array stores its parent */
181 int *c_reverse; /* for each def number that array stores the */
182 /* corresponding node */
183 int c_globalCount; /* counter for def numbering */
184 int *c_numPre; /* array that stores for each node its number */
186 int **c_pre; /* array of array that stores predecessors */
187 int c_last_jump; /* stores the source node of the last jsr instr */
188 struct basicblock *c_last_target; /* stores the source BB of the last jsr instr */
190 struct depthElement **c_dTable; /* adjacency list for control flow graph */
191 struct depthElement **c_exceptionGraph; /* adjacency list for exception graph */
193 struct LoopContainer *c_allLoops; /* list of all loops */
194 struct LoopContainer *c_loop_root; /* root of loop hierarchie tree */
196 int *c_exceptionVisit; /* array that stores a flag for each node part */
197 /* of the exception graph */
199 /* modified by loop.c */
201 int *c_semi_dom; /* store for each node its semi dominator */
202 int *c_idom; /* store for each node its dominator */
203 int *c_same_dom; /* temp array to hold nodes with same dominator */
204 int *c_ancestor; /* store for each node its ancestor with lowest */
209 int *c_contains; /* store for each node whether it's part of loop*/
210 int *c_stack; /* a simple stack as array */
211 int c_stackPointer; /* stackpointer */
214 /* modified by analyze.c */
216 struct LoopContainer *root; /* the root pointer for the hierarchie tree of */
217 /* all loops in that procedure */
219 int c_needed_instr; /* number of instructions that have to be */
220 /* inserted before loop header to make sure */
221 /* array optimization is legal */
222 int c_rs_needed_instr; /* number of instructions needed to load the */
223 /* value ofthe right side of the loop condition */
224 int *c_nestedLoops; /* store for each node the header node of the */
225 /* loop this node belongs to, -1 for none */
226 int *c_hierarchie; /* store a loop hierarchie */
227 int *c_toVisit; /* set for each node that is part of the loop */
229 int *c_current_loop; /* for each node: */
230 /* store 0: node is not part of loop */
231 /* store 1: node is loop header */
232 /* store 2: node is in loop but not part of any */
234 /* store 3: node is part of nested loop */
236 int c_current_head; /* store number of node that is header of loop */
237 int *c_var_modified; /* store for each local variable whether its */
238 /* value is changed in the loop */
240 struct Trace *c_rightside; /* right side of loop condition */
241 struct Constraint **c_constraints;
242 /* array that stores for each variable a list */
243 /* static tests (constraints) that have to be */
244 /* performed before loop entry */
245 /* IMPORTANT: c_constraints[maxlocals] stores */
246 /* the tests for constants and the */
247 /* right side of loop condition */
249 struct LoopVar *c_loopvars; /* a list of all intersting variables of the */
250 /* current loop (variables that are modified or */
251 /* used as array index */
253 struct basicblock *c_first_block_copied; /* pointer to the first block, that is copied */
254 /* during loop duplication */
256 struct basicblock *c_last_block_copied; /* last block, that is copied during loop */
259 int *c_null_check; /* array to store for local vars, whether they */
260 /* need to be checked against the null reference*/
261 /* in the loop head */
263 bool c_needs_redirection; /* if a loop header is inserted as first block */
264 /* into the global BB list, this is set to true */
266 struct basicblock *c_newstart; /* if a loop header is inserted as first block */
267 /* into the gloal BB list, this pointer is the */
269 int c_old_xtablelength; /* used to store the original tablelength */
275 /* declare statistic variables */
276 #ifdef ENABLE_STATISTICS
278 int c_stat_num_loops; /* number of loops */
280 /* statistics per loop */
281 int c_stat_array_accesses; /* number of array accesses */
283 int c_stat_full_opt; /* number of fully optimized accesses */
284 int c_stat_no_opt; /* number of not optimized accesses */
285 int c_stat_lower_opt; /* number of accesses where check against zero */
287 int c_stat_upper_opt; /* number of accesses where check against array */
288 /* lengh is removed */
289 int c_stat_or; /* set if optimization is cancelled because of */
290 /* or in loop condition */
291 int c_stat_exception; /* set if optimization is cancelled because of */
292 /* index var modified in catch block */
294 /* statistics per procedure */
295 int c_stat_sum_accesses; /* number of array accesses */
297 int c_stat_sum_full; /* number of fully optimized accesses */
298 int c_stat_sum_no; /* number of not optimized accesses */
299 int c_stat_sum_lower; /* number of accesses where check against zero */
301 int c_stat_sum_upper; /* number of accesses where check against array */
302 /* lengh is removed */
303 int c_stat_sum_or; /* set if optimization is cancelled because of */
304 /* or in loop condition */
305 int c_stat_sum_exception; /* set if optimization is cancelled because of */
311 /* function prototypes ********************************************************/
313 void analyseGraph(jitdata *jd);
314 void c_mem_error(void);
320 * These are local overrides for various environment variables in Emacs.
321 * Please do not remove this and leave it at the end of the file, where
322 * Emacs will automagically detect them.
323 * ---------------------------------------------------------------------
326 * indent-tabs-mode: t