1 /* loop.h **********************************************************************
3 Copyright (c) 1997 A. Krall, R. Grafl, M. Gschwind, M. Probst
5 See file COPYRIGHT for information on usage and disclaimer of warranties.
7 Main header file for array bound removal files
9 Authors: Christopher Kruegel EMAIL: cacao@complang.tuwien.ac.at
11 Last Change: 1998/17/02
13 *******************************************************************************/
15 #ifndef __C_ARRAYBOUND_
16 #define __C_ARRAYBOUND_
18 /* #define LOOP_DEBUG */
23 /* Different types for struct Trace */
24 #define TRACE_UNKNOWN 0 /* unknown */
25 #define TRACE_ICONST 1 /* integer constant value */
26 #define TRACE_ALENGTH 2 /* array length value */
27 #define TRACE_IVAR 3 /* integer variable reference */
28 #define TRACE_AVAR 4 /* object (array) reference */
30 /* The ways a variable can be used in a loop */
31 #define ARRAY_INDEX 0 /* var used as array index */
32 #define VAR_MOD 1 /* var changes its value */
34 /* The way, integer variables change their values */
35 #define D_UP 0 /* var is only increased */
36 #define D_DOWN 1 /* var is only decreased */
37 #define D_UNKNOWN 2 /* not known */
39 /* The different types of operators in loop conditions */
40 #define OP_EQ 0 /* operator: == */
41 #define OP_LT 1 /* operator: < */
42 #define OP_GE 2 /* operator: >= */
43 #define OP_UNKNOWN 3 /* operator: unknown */
45 /* Possible types of static tests (constraints) in struct Constraint */
47 #define TEST_ZERO 0 /* check variable against const. lower bound */
48 #define TEST_ALENGTH 1 /* check variable against array length */
49 #define TEST_CONST_ZERO 2 /* check constant against const. lower bound */
50 #define TEST_CONST_ALENGTH 3 /* check variable against array length */
51 #define TEST_UNMOD_ZERO 4 /* check var. that is constant in loop against */
52 /* constant lower bound */
53 #define TEST_UNMOD_ALENGTH 5 /* check var. that is constant in loop against */
55 #define TEST_RS_ZERO 6 /* check constant part of loop condition against*/
56 /* constant lower bound */
57 #define TEST_RS_ALENGTH 7 /* check constant part of loop condition against*/
60 /* Possible types of bound check optimizations */
61 #define OPT_UNCHECKED 0 /* access not checked yet - first visit */
62 #define OPT_NONE 1 /* no optimization */
63 #define OPT_FULL 2 /* fully remove bound check */
64 #define OPT_LOWER 3 /* remove check againt zero */
65 #define OPT_UPPER 4 /* remove check against array length */
67 /* The different ways, remove_boundcheck(.) can be called */
68 #define BOUNDCHECK_REGULAR 0 /* perform regular optimization */
69 #define BOUNDCHECK_SPECIAL 1 /* only optimize header node - and ignore */
70 /* information from loop condition */
72 #define LOOP_PART 0x1 /* a flag that marks a BB part of a loop */
73 #define HANDLER_PART 0x2 /* a flag that marks a BB part of ex-handler */
74 #define HANDLER_VISITED 0x4 /* flag to prevent loop if copying catch blocks */
76 /* STRUCT DEFINITIONS */
78 /* This struct records information about interesting vars (vars that are modified
79 or used as an array index in loops.
83 int value; /* reference to array of local variables */
85 int modified; /* set if value of var is changed */
86 int index; /* set if var is used as array index */
88 int static_l; /* var is never decremented -> static lower */
90 int static_u; /* var is never incremented -> static upper */
93 int dynamic_l_v; /* variable is left side of loop condition in */
94 /* variable + dynamic_l >= right side */
96 int dynamic_u_v; /* variable is left side of loop condition in */
97 /* variable + dynamic_u < right side */
98 struct LoopVar *next; /* list pointer */
101 /* This struct records the needed static test of variables before loop entry. */
104 int type; /* type of test to perform */
106 int arrayRef; /* array reference involved in test (if any) */
107 int varRef; /* which variable to test (if involved) */
108 int constant; /* which constant to test (if involved) */
110 struct Constraint *next; /* list pointer */
113 /* This structure is used to record variables that change their value in loops. */
116 int var; /* variable involved */
117 int lower_bound; /* a minimum lower bound that is guaranteed */
118 int upper_bound; /* a maximum upper bound that is guaranteed */
119 /* IMPORTANT: if lower_bound > upper_bound */
120 /* there are no guarantees at all */
123 /* This struct is used to build the control flow graph and stores the variable
124 changes at the beginning of each basic block.
128 int value; /* number of successor of this block */
129 struct depthElement *next; /* list pointer */
130 struct Changes **changes; /* pointer to array of variable changes */
133 /* Used to build a list of all basicblock, the loop consists of
139 struct LoopElement *next;
142 /* This structure stores informations about a single loop
146 int toOpt; /* does this loop need optimization */
148 struct LoopElement *nodes; /* list of BBs this loop consists of */
150 int in_degree; /* needed to topological sort loops to */
151 /* get the order of optimizing them */
153 struct LoopContainer *next; /* list pointer */
154 struct LoopContainer *parent; /* points to parent loop, if this BB */
155 /* is head of a loop */
157 struct LoopContainer *tree_right; /* used for tree hierarchie of loops */
158 struct LoopContainer *tree_down;
160 xtable *exceptions; /* list of exception in that loop */
163 /* This struct is needed to record the source of operands of intermediate code
164 instructions. The instructions are scanned backwards and the stack is
165 analyzed in order to determine the type of operand.
169 int type; /* the type of the operand */
171 int neg; /* set if negated */
173 int var; /* variable reference for IVAR */
174 /* array reference for AVAR/ARRAY */
175 int nr; /* instruction number in the basic block, where */
176 /* the trace is defined */
177 int constant; /* constant value for ICONST */
178 /* modifiers for IVAR */
187 printf("C_ERROR: Not enough memeory\n");
193 int c_debug_nr; /* a counter to number all BB with an unique */
196 /* modified by graph.c */
198 int *c_defnum; /* array that stores a number for each node when*/
199 /* control flow graph is traveres depth first */
200 int *c_parent; /* for each node that array stores its parent */
201 int *c_reverse; /* for each def number that array stores the */
202 /* corresponding node */
203 int c_globalCount; /* counter for def numbering */
204 int *c_numPre; /* array that stores for each node its number */
206 int **c_pre; /* array of array that stores predecessors */
207 int c_last_jump; /* stores the source node of the last jsr instr */
208 basicblock *c_last_target; /* stores the source BB of the last jsr instr */
210 struct depthElement **c_dTable; /* adjacency list for control flow graph */
211 struct depthElement **c_exceptionGraph; /* adjacency list for exception graph */
213 struct LoopContainer *c_allLoops; /* list of all loops */
214 struct LoopContainer *c_loop_root; /* root of loop hierarchie tree */
216 int *c_exceptionVisit; /* array that stores a flag for each node part */
217 /* of the exception graph */
219 /* modified by loop.c */
221 int *c_semi_dom; /* store for each node its semi dominator */
222 int *c_idom; /* store for each node its dominator */
223 int *c_same_dom; /* temp array to hold nodes with same dominator */
224 int *c_ancestor; /* store for each node its ancestor with lowest */
229 int *c_contains; /* store for each node whether it's part of loop*/
230 int *c_stack; /* a simple stack as array */
231 int c_stackPointer; /* stackpointer */
234 /* modified by analyze.c */
236 struct LoopContainer *root; /* the root pointer for the hierarchie tree of */
237 /* all loops in that procedure */
239 int c_needed_instr; /* number of instructions that have to be */
240 /* inserted before loop header to make sure */
241 /* array optimization is legal */
242 int c_rs_needed_instr; /* number of instructions needed to load the */
243 /* value ofthe right side of the loop condition */
244 int *c_nestedLoops; /* store for each node the header node of the */
245 /* loop this node belongs to, -1 for none */
246 int *c_hierarchie; /* store a loop hierarchie */
247 int *c_toVisit; /* set for each node that is part of the loop */
249 int *c_current_loop; /* for each node:
250 /* store 0: node is not part of loop */
251 /* store 1: node is loop header */
252 /* store 2: node is in loop but not part of any */
254 /* store 3: node is part of nested loop */
256 int c_current_head; /* store number of node that is header of loop */
257 int *c_var_modified; /* store for each local variable whether its */
258 /* value is changed in the loop */
260 struct Trace *c_rightside; /* right side of loop condition */
261 struct Constraint **c_constraints;
262 /* array that stores for each variable a list */
263 /* static tests (constraints) that have to be */
264 /* performed before loop entry */
265 /* IMPORTANT: c_constraints[maxlocals] stores */
266 /* the tests for constants and the */
267 /* right side of loop condition */
269 struct LoopVar *c_loopvars; /* a list of all intersting variables of the */
270 /* current loop (variables that are modified or */
271 /* used as array index */
273 basicblock *c_first_block_copied; /* pointer to the first block, that is copied */
274 /* during loop duplication */
276 basicblock *c_last_block_copied; /* last block, that is copied during loop */
279 int *c_null_check; /* array to store for local vars, whether they */
280 /* need to be checked against the null reference*/
281 /* in the loop head */
283 bool c_needs_redirection; /* if a loop header is inserted as first block */
284 /* into the global BB list, this is set to true */
286 basicblock *c_newstart; /* if a loop header is inserted as first block */
287 /* into the gloal BB list, this pointer is the */
289 int c_old_xtablelength; /* used to store the original tablelength */
295 /* declare statistic variables */
298 int c_stat_num_loops; /* number of loops */
300 /* statistics per loop */
301 int c_stat_array_accesses; /* number of array accesses */
303 int c_stat_full_opt; /* number of fully optimized accesses */
304 int c_stat_no_opt; /* number of not optimized accesses */
305 int c_stat_lower_opt; /* number of accesses where check against zero */
307 int c_stat_upper_opt; /* number of accesses where check against array */
308 /* lengh is removed */
309 int c_stat_or; /* set if optimization is cancelled because of */
310 /* or in loop condition */
311 int c_stat_exception; /* set if optimization is cancelled because of */
312 /* index var modified in catch block */
314 /* statistics per procedure */
315 int c_stat_sum_accesses; /* number of array accesses */
317 int c_stat_sum_full; /* number of fully optimized accesses */
318 int c_stat_sum_no; /* number of not optimized accesses */
319 int c_stat_sum_lower; /* number of accesses where check against zero */
321 int c_stat_sum_upper; /* number of accesses where check against array */
322 /* lengh is removed */
323 int c_stat_sum_or; /* set if optimization is cancelled because of */
324 /* or in loop condition */
325 int c_stat_sum_exception; /* set if optimization is cancelled because of */
332 * These are local overrides for various environment variables in Emacs.
333 * Please do not remove this and leave it at the end of the file, where
334 * Emacs will automagically detect them.
335 * ---------------------------------------------------------------------
338 * indent-tabs-mode: t