1 /* vm/jit/loop/loop.h - array bound removal header
3 Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003
4 R. Grafl, A. Krall, C. Kruegel, C. Oates, R. Obermaisser,
5 M. Probst, S. Ring, E. Steiner, C. Thalinger, D. Thuernbeck,
6 P. Tomsich, J. Wenninger
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: Christopher Kruegel
29 $Id: loop.h 1621 2004-11-30 13:06:55Z twisti $
37 #include "vm/global.h"
38 #include "vm/jit/jit.h"
41 /* Different types for struct Trace */
42 #define TRACE_UNKNOWN 0 /* unknown */
43 #define TRACE_ICONST 1 /* integer constant value */
44 #define TRACE_ALENGTH 2 /* array length value */
45 #define TRACE_IVAR 3 /* integer variable reference */
46 #define TRACE_AVAR 4 /* object (array) reference */
48 /* The ways a variable can be used in a loop */
49 #define ARRAY_INDEX 0 /* var used as array index */
50 #define VAR_MOD 1 /* var changes its value */
52 /* The way, integer variables change their values */
53 #define D_UP 0 /* var is only increased */
54 #define D_DOWN 1 /* var is only decreased */
55 #define D_UNKNOWN 2 /* not known */
57 /* The different types of operators in loop conditions */
58 #define OP_EQ 0 /* operator: == */
59 #define OP_LT 1 /* operator: < */
60 #define OP_GE 2 /* operator: >= */
61 #define OP_UNKNOWN 3 /* operator: unknown */
63 /* Possible types of static tests (constraints) in struct Constraint */
65 #define TEST_ZERO 0 /* check variable against const. lower bound*/
66 #define TEST_ALENGTH 1 /* check variable against array length */
67 #define TEST_CONST_ZERO 2 /* check constant against const. lower bound*/
68 #define TEST_CONST_ALENGTH 3 /* check variable against array length */
69 #define TEST_UNMOD_ZERO 4 /* check var. that is constant in loop against*/
70 /* constant lower bound */
71 #define TEST_UNMOD_ALENGTH 5 /* check var. that is constant in loop against*/
73 #define TEST_RS_ZERO 6 /* check constant part of loop condition against*/
74 /* constant lower bound */
75 #define TEST_RS_ALENGTH 7 /* check constant part of loop condition against*/
78 /* Possible types of bound check optimizations */
79 #define OPT_UNCHECKED 0 /* access not checked yet - first visit */
80 #define OPT_NONE 1 /* no optimization */
81 #define OPT_FULL 2 /* fully remove bound check */
82 #define OPT_LOWER 3 /* remove check againt zero */
83 #define OPT_UPPER 4 /* remove check against array length */
85 /* The different ways, remove_boundcheck(.) can be called */
86 #define BOUNDCHECK_REGULAR 0 /* perform regular optimization */
87 #define BOUNDCHECK_SPECIAL 1 /* only optimize header node - and ignore */
88 /* information from loop condition */
90 #define LOOP_PART 0x1 /* a flag that marks a BB part of a loop */
91 #define HANDLER_PART 0x2 /* a flag that marks a BB part of ex-handler */
92 #define HANDLER_VISITED 0x4 /* flag to prevent loop if copying catch blocks */
95 typedef struct LoopElement LoopElement;
96 typedef struct LoopContainer LoopContainer;
97 typedef struct loopdata loopdata;
100 /* This struct records information about interesting vars (vars that are modified
101 or used as an array index in loops.
104 int value; /* reference to array of local variables */
105 int modified; /* set if value of var is changed */
106 int index; /* set if var is used as array index */
107 int static_l; /* var is never decremented -> static lower */
109 int static_u; /* var is never incremented -> static upper */
112 int dynamic_l_v; /* variable is left side of loop condition in */
113 /* variable + dynamic_l >= right side */
115 int dynamic_u_v; /* variable is left side of loop condition in */
116 /* variable + dynamic_u < right side */
117 struct LoopVar *next; /* list pointer */
121 /* This struct records the needed static test of variables before loop entry. */
123 int type; /* type of test to perform */
124 int arrayRef; /* array reference involved in test (if any) */
125 int varRef; /* which variable to test (if involved) */
126 int constant; /* which constant to test (if involved) */
127 struct Constraint *next; /* list pointer */
131 /* This structure is used to record variables that change their value in loops. */
133 int var; /* variable involved */
134 int lower_bound; /* a minimum lower bound that is guaranteed */
135 int upper_bound; /* a maximum upper bound that is guaranteed */
136 /* IMPORTANT: if lower_bound > upper_bound */
137 /* there are no guarantees at all */
141 /* This struct is used to build the control flow graph and stores the variable
142 changes at the beginning of each basic block.
144 struct depthElement {
145 int value; /* number of successor of this block */
146 struct depthElement *next; /* list pointer */
147 struct Changes **changes; /* pointer to array of variable changes */
151 /* Used to build a list of all basicblock, the loop consists of */
161 This structure stores informations about a single loop
163 struct LoopContainer {
164 s4 toOpt; /* does this loop need optimization */
165 LoopElement *nodes; /* list of BBs this loop consists of */
167 s4 in_degree; /* needed to topological sort loops to*/
168 /* get the order of optimizing them */
169 LoopContainer *next; /* list pointer */
170 LoopContainer *parent; /* points to parent loop, if this BB */
171 /* is head of a loop */
172 LoopContainer *tree_right; /* used for tree hierarchie of loops */
173 LoopContainer *tree_down;
174 exceptiontable *exceptions; /* list of exception in that loop */
179 /* modified by graph.c */
181 int *c_defnum; /* array that stores a number for each node when*/
182 /* control flow graph is traveres depth first */
183 int *c_parent; /* for each node that array stores its parent */
184 int *c_reverse; /* for each def number that array stores the */
185 /* corresponding node */
186 int c_globalCount; /* counter for def numbering */
187 int *c_numPre; /* array that stores for each node its number */
189 int **c_pre; /* array of array that stores predecessors */
190 int c_last_jump; /* stores the source node of the last jsr instr */
191 struct basicblock *c_last_target; /* stores the source BB of the last jsr instr */
193 struct depthElement **c_dTable; /* adjacency list for control flow graph */
194 struct depthElement **c_exceptionGraph; /* adjacency list for exception graph */
196 struct LoopContainer *c_allLoops; /* list of all loops */
197 struct LoopContainer *c_loop_root; /* root of loop hierarchie tree */
199 int *c_exceptionVisit; /* array that stores a flag for each node part */
200 /* of the exception graph */
202 /* modified by loop.c */
204 int *c_semi_dom; /* store for each node its semi dominator */
205 int *c_idom; /* store for each node its dominator */
206 int *c_same_dom; /* temp array to hold nodes with same dominator */
207 int *c_ancestor; /* store for each node its ancestor with lowest */
212 int *c_contains; /* store for each node whether it's part of loop*/
213 int *c_stack; /* a simple stack as array */
214 int c_stackPointer; /* stackpointer */
217 /* modified by analyze.c */
219 struct LoopContainer *root; /* the root pointer for the hierarchie tree of */
220 /* all loops in that procedure */
222 int c_needed_instr; /* number of instructions that have to be */
223 /* inserted before loop header to make sure */
224 /* array optimization is legal */
225 int c_rs_needed_instr; /* number of instructions needed to load the */
226 /* value ofthe right side of the loop condition */
227 int *c_nestedLoops; /* store for each node the header node of the */
228 /* loop this node belongs to, -1 for none */
229 int *c_hierarchie; /* store a loop hierarchie */
230 int *c_toVisit; /* set for each node that is part of the loop */
232 int *c_current_loop; /* for each node: */
233 /* store 0: node is not part of loop */
234 /* store 1: node is loop header */
235 /* store 2: node is in loop but not part of any */
237 /* store 3: node is part of nested loop */
239 int c_current_head; /* store number of node that is header of loop */
240 int *c_var_modified; /* store for each local variable whether its */
241 /* value is changed in the loop */
243 struct Trace *c_rightside; /* right side of loop condition */
244 struct Constraint **c_constraints;
245 /* array that stores for each variable a list */
246 /* static tests (constraints) that have to be */
247 /* performed before loop entry */
248 /* IMPORTANT: c_constraints[maxlocals] stores */
249 /* the tests for constants and the */
250 /* right side of loop condition */
252 struct LoopVar *c_loopvars; /* a list of all intersting variables of the */
253 /* current loop (variables that are modified or */
254 /* used as array index */
256 struct basicblock *c_first_block_copied; /* pointer to the first block, that is copied */
257 /* during loop duplication */
259 struct basicblock *c_last_block_copied; /* last block, that is copied during loop */
262 int *c_null_check; /* array to store for local vars, whether they */
263 /* need to be checked against the null reference*/
264 /* in the loop head */
266 bool c_needs_redirection; /* if a loop header is inserted as first block */
267 /* into the global BB list, this is set to true */
269 struct basicblock *c_newstart; /* if a loop header is inserted as first block */
270 /* into the gloal BB list, this pointer is the */
272 int c_old_xtablelength; /* used to store the original tablelength */
278 /* declare statistic variables */
281 int c_stat_num_loops; /* number of loops */
283 /* statistics per loop */
284 int c_stat_array_accesses; /* number of array accesses */
286 int c_stat_full_opt; /* number of fully optimized accesses */
287 int c_stat_no_opt; /* number of not optimized accesses */
288 int c_stat_lower_opt; /* number of accesses where check against zero */
290 int c_stat_upper_opt; /* number of accesses where check against array */
291 /* lengh is removed */
292 int c_stat_or; /* set if optimization is cancelled because of */
293 /* or in loop condition */
294 int c_stat_exception; /* set if optimization is cancelled because of */
295 /* index var modified in catch block */
297 /* statistics per procedure */
298 int c_stat_sum_accesses; /* number of array accesses */
300 int c_stat_sum_full; /* number of fully optimized accesses */
301 int c_stat_sum_no; /* number of not optimized accesses */
302 int c_stat_sum_lower; /* number of accesses where check against zero */
304 int c_stat_sum_upper; /* number of accesses where check against array */
305 /* lengh is removed */
306 int c_stat_sum_or; /* set if optimization is cancelled because of */
307 /* or in loop condition */
308 int c_stat_sum_exception; /* set if optimization is cancelled because of */
314 /* function prototypes */
316 void analyseGraph(methodinfo *m, loopdata *ld);
323 * These are local overrides for various environment variables in Emacs.
324 * Please do not remove this and leave it at the end of the file, where
325 * Emacs will automagically detect them.
326 * ---------------------------------------------------------------------
329 * indent-tabs-mode: t