-/* vm/jit/loop/analyze.c - bound check removal functions
+/* src/vm/jit/loop/analyze.c - bound check removal functions
- Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003
- R. Grafl, A. Krall, C. Kruegel, C. Oates, R. Obermaisser,
- M. Probst, S. Ring, E. Steiner, C. Thalinger, D. Thuernbeck,
- P. Tomsich, J. Wenninger
+ Copyright (C) 1996-2005, 2006 R. Grafl, A. Krall, C. Kruegel,
+ C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
+ E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
+ J. Wenninger, Institut f. Computersprachen - TU Wien
This file is part of CACAO.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
- 02111-1307, USA.
+ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA.
- Contact: cacao@complang.tuwien.ac.at
+ Contact: cacao@cacaojvm.org
Authors: Christopher Kruegel
+ Changes: Christian Thalinger
+
Contains the functions which perform the bound check removals. With
the loops identified, these functions scan the code for array
accesses that take place in loops and try to guarantee that their
bounds are never violated. The function to call is
optimize_loops().
- $Id: analyze.c 1621 2004-11-30 13:06:55Z twisti $
-
*/
+#include "config.h"
+
+#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
+#include "vm/types.h"
+
#include "mm/memory.h"
#include "toolbox/logging.h"
#include "vm/jit/jit.h"
#endif
-#ifdef STATISTICS
+#ifdef ENABLE_STATISTICS
void show_loop_statistics(loopdata *ld)
{
struct LoopElement *le;
#ifdef LOOP_DEBUG
- /* printf("insert_exception called with %d-%d and loop %d\n", ex->start->debug_nr, ex->end->debug_nr, lc->loop_head); */
+ /* printf("insert_exception called with %d-%d and loop %d\n", ex->start->nr, ex->end->nr, lc->loop_head); */
#endif
/* if child node is reached immediately insert exception into the tree */
show_tree(ld->root, 0);
printf(" --- End ---\n");
#endif
- for (len = 0; len < cd->exceptiontablelength; ++len)
- insert_exception(m, ld->root, cd->exceptiontable + len);
+ for (len = 0; len < jd->exceptiontablelength; ++len)
+ insert_exception(m, ld->root, jd->exceptiontable + len);
/* determine sequence of loops for optimization by topological sort */
}
if ((count > 1) && (flag == 0)){/* if all successors part of the loop, exit */
-#ifdef STATISTICS
+#ifdef ENABLE_STATISTICS
ld->c_stat_or++;
#endif
return 0;
}
/* check for exceptions */
- /* printf("done\n*** Analyze for EXCEPTIONS(%d) . ", cd->exceptiontablelength); */
+ /* printf("done\n*** Analyze for EXCEPTIONS(%d) . ", jd->exceptiontablelength); */
- if (!cd->exceptiontablelength) /* when there are no exceptions, exit */
+ if (!jd->exceptiontablelength) /* when there are no exceptions, exit */
return 1;
if ((ld->c_exceptionGraph = (struct depthElement **) malloc(sizeof(struct depthElement *) * m->basicblockcount)) == NULL)
/* for all nodes that start catch block check whether they are part of loop */
for (i = 0; i < ld->c_old_xtablelength; i++) {
- value = m->basicblockindex[cd->exceptiontable[i].startpc];
+ value = m->basicblockindex[jd->exceptiontable[i].startpc];
le = lc->nodes;
while (le != NULL) {
/* build a graph structure, that contains all nodes that are */
/* part of the catc block */
- dF_Exception(m, ld, -1, m->basicblockindex[cd->exceptiontable[i].handlerpc]);
+ dF_Exception(m, ld, -1, m->basicblockindex[jd->exceptiontable[i].handlerpc]);
/* if array index variables are modified there, return 0 */
- if (quick_scan(m, ld, m->basicblockindex[cd->exceptiontable[i].handlerpc]) > 0) {
-#ifdef STATISTICS
+ if (quick_scan(m, ld, m->basicblockindex[jd->exceptiontable[i].handlerpc]) > 0) {
+#ifdef ENABLE_STATISTICS
ld->c_stat_exception++;
#endif
/* printf("C_INFO: loopVar modified in exception\n"); */
struct Trace *left, *right, *th;
struct LoopVar *lv_left, *lv_right, *lh;
+ /* prevent some compiler warnings */
+
+ operand = 0;
+ lv_left = NULL;
+ lv_right = NULL;
+
bp = m->basicblocks[head];
ic = bp.icount;
ip = bp.iinstr+(ic-1); /* set ip to last instruction in header node */
case TEST_CONST_ALENGTH: /* a const is tested against array length */
/* does a test already exist for this array */
- tc = ld->c_constraints[cd->maxlocals];
+ tc = ld->c_constraints[jd->maxlocals];
while (tc != NULL) {
if ((tc->type == TEST_CONST_ALENGTH) && (tc->arrayRef == arrayRef)) {
if (constant > tc->constant)
tc->type = TEST_CONST_ALENGTH;
tc->arrayRef = arrayRef;
tc->constant = constant;
- tc->next = ld->c_constraints[cd->maxlocals];
- ld->c_constraints[cd->maxlocals] = tc;
+ tc->next = ld->c_constraints[jd->maxlocals];
+ ld->c_constraints[jd->maxlocals] = tc;
ld->c_needed_instr += 4;
/* if arrayRef is not already tested against null, insert that test */
/* checks */
/*!! varRef -> maxlocals */
/* search if test already exists */
- tc = ld->c_constraints[cd->maxlocals];
+ tc = ld->c_constraints[jd->maxlocals];
while (tc != NULL) {
if (tc->type == TEST_RS_ZERO) {
if (constant < tc->constant)
c_mem_error();
tc->type = TEST_RS_ZERO;
tc->constant = constant;
- tc->next = ld->c_constraints[cd->maxlocals];
- ld->c_constraints[cd->maxlocals] = tc;
+ tc->next = ld->c_constraints[jd->maxlocals];
+ ld->c_constraints[jd->maxlocals] = tc;
ld->c_needed_instr += (2 + ld->c_rs_needed_instr);
/* if arrayRef on right side is not already tested against null, */
/* checks */
/*!! varRef -> maxlocals */
/* search if test already exists */
- tc = ld->c_constraints[cd->maxlocals];
+ tc = ld->c_constraints[jd->maxlocals];
while (tc != NULL)
{
if ((tc->type == TEST_RS_ALENGTH) && (tc->arrayRef == arrayRef))
tc->type = TEST_RS_ALENGTH;
tc->arrayRef = arrayRef;
tc->constant = constant;
- tc->next = ld->c_constraints[cd->maxlocals];
- ld->c_constraints[cd->maxlocals] = tc;
+ tc->next = ld->c_constraints[jd->maxlocals];
+ ld->c_constraints[jd->maxlocals] = tc;
ld->c_needed_instr += (3 + ld->c_rs_needed_instr);
/* if arrayRef is not already tested against null, insert that test */
switch (index->type) { /* check index type */
case TRACE_IVAR: /* it is a variable */
if (index->neg < 0) { /* if it's a negated var, return */
-#ifdef STATISTICS
+#ifdef ENABLE_STATISTICS
ld->c_stat_no_opt++;
#endif
return OPT_NONE;
/* return the best possible optimization */
if ((high > 0) && (low > 0)) {
/* printf("fully optimzed\n"); */
-#ifdef STATISTICS
+#ifdef ENABLE_STATISTICS
ld->c_stat_full_opt++;
#endif
return OPT_FULL;
}
else if (high > 0) {
/* printf("upper optimzed\n"); */
-#ifdef STATISTICS
+#ifdef ENABLE_STATISTICS
ld->c_stat_upper_opt++;
#endif
return OPT_UPPER;
}
else if (low > 0) {
/* printf("lower optimzed\n"); */
-#ifdef STATISTICS
+#ifdef ENABLE_STATISTICS
ld->c_stat_lower_opt++;
#endif
return OPT_LOWER;
}
else {
/* printf("not optimzed\n"); */
-#ifdef STATISTICS
+#ifdef ENABLE_STATISTICS
ld->c_stat_no_opt++;
#endif
return OPT_NONE;
case TRACE_ICONST: /* if it is a constant, optimization is easy */
if (index->constant < 0) {
-#ifdef STATISTICS
+#ifdef ENABLE_STATISTICS
ld->c_stat_no_opt++;
#endif
return OPT_NONE; /* negative index -> bad */
}
else {
add_new_constraint(m, cd, ld, TEST_CONST_ALENGTH, arrayRef, 0, index->constant);
-#ifdef STATISTICS
+#ifdef ENABLE_STATISTICS
ld->c_stat_full_opt++;
#endif
return OPT_FULL; /* else just test constant against array length */
case TRACE_ALENGTH: /* else, no optimizations possible */
case TRACE_UNKNOWN:
case TRACE_AVAR:
-#ifdef STATISTICS
+#ifdef ENABLE_STATISTICS
ld->c_stat_no_opt++;
#endif
return OPT_NONE;
LOAD_ARRAYLENGTH(ld->c_rightside->var); \
break; \
default: \
- panic("C_ERROR: illegal trace on rightside of loop-header"); \
+ log_text("C_ERROR: illegal trace on rightside of loop-header"); \
+ assert(0); \
} \
}
/* copy node */
new = DMNEW(basicblock, 1);
memcpy(new, bptr, sizeof(basicblock));
- new->debug_nr = m->c_debug_nr++;
+ new->nr = -1;
ld->c_last_block_copied = new;
memcpy(new, ex, sizeof(exceptiontable));
/* Increase number of exceptions */
- ++cd->exceptiontablelength;
+ ++jd->exceptiontablelength;
ex->next = new;
ex->down = new;
/* Increase number of exceptions */
- ++cd->exceptiontablelength;
+ ++jd->exceptiontablelength;
ex->next = new;
ex->down = new;
stackptr newstack, tos;
exceptiontable *ex;
-#ifdef STATISTICS
+ /* prevent some compiler warnings */
+
+ bptr = NULL;
+
+#ifdef ENABLE_STATISTICS
/* show_loop_statistics(l); */
#endif
{
bptr = DMNEW(basicblock, 1);
memcpy(bptr, le->block, sizeof(basicblock));
- bptr->debug_nr = m->c_debug_nr++;
+ bptr->nr = -1;
/* determine beginning of copied loop to extend exception handler, that */
/* protect this loop */
/* copy current loop header to new basic block */
memcpy(bptr, loop_head, sizeof(basicblock));
- bptr->debug_nr = m->c_debug_nr++;
+ bptr->nr = -1;
/* insert the new basic block and move header before first loop node */
le = lc->nodes;
}
/* adjust exceptions */
- ex = cd->exceptiontable;
+ ex = jd->exceptiontable;
while (ex != NULL) {
/* if an exception covers whole loop and starts at first loop node, it */
stackdepth = loop_head->indepth;
/* step through all inserted checks and create instructions for them */
- for (i=0; i<cd->maxlocals+1; ++i)
+ for (i=0; i<jd->maxlocals+1; ++i)
{
tc1 = ld->c_constraints[i];
while (tc1 != NULL)
printf("C_ERROR: debugging error 0x03\n");
changed = 0;
- for (i=0; i<cd->maxlocals; ++i) {
+ for (i=0; i<jd->maxlocals; ++i) {
if (c1[i] == NULL) {
if (c2[i] != NULL) { /* a change in c2 is updated in c1 */
changed = 1;
changed = 0;
- for (i=0; i<cd->maxlocals; ++i) {
+ for (i=0; i<jd->maxlocals; ++i) {
if (c1[i] == NULL) {
if (c2[i] != NULL) { /* update changes in c2 in c1 */
if ((c1[i] = (struct Changes *) malloc (sizeof(struct Changes))) == NULL)
int i;
struct Changes **t;
- if ((t = (struct Changes **) malloc(cd->maxlocals * sizeof(struct Changes *))) == NULL)
+ if ((t = (struct Changes **) malloc(jd->maxlocals * sizeof(struct Changes *))) == NULL)
c_mem_error();
- for (i=0; i<cd->maxlocals; ++i) { /* for all array elements (vars) do */
+ for (i=0; i<jd->maxlocals; ++i) { /* for all array elements (vars) do */
if (c[i] == NULL)
t[i] = NULL;
else {
struct Changes **t1, **tmp, *t;
struct Trace *t_array, *t_index;
+ /* prevent some compiler warnings */
+
+ t_array = NULL;
+ t_index = NULL;
+
/* printf("remove_bc called: %d - %d - %d\n", node, from, special); */
/* a flag, that is set, when previous optimzations have to be taken back */
show_trace(t_index);
*/
-#ifdef STATISTICS
+#ifdef ENABLE_STATISTICS
if (ip->op1 == OPT_UNCHECKED) { /* found new access */
ld->c_stat_array_accesses++;
ip->op1 = OPT_NONE;
switch (t_index->type) { /* now we look at the index */
case TRACE_ICONST: /* it is a constant value or an */
case TRACE_ALENGTH: /* array length */
-#ifdef STATISTICS
+#ifdef ENABLE_STATISTICS
switch (ip->op1) { /* take back old optimzation */
case OPT_UNCHECKED:
break;
ip->op1 = OPT_FULL;
break;
case OPT_FULL:
-#ifdef STATISTICS
+#ifdef ENABLE_STATISTICS
ld->c_stat_full_opt++;
#endif
break;
/* to set the changes back to the time, it is pushed onto */
/* the stack as an index variable. */
t = backtrack_var(m, node, t_index->nr, i-1, t_index->var, tmp[t_index->var]);
-#ifdef STATISTICS
+#ifdef ENABLE_STATISTICS
switch (ip->op1) { /* take back old optimzation */
case OPT_UNCHECKED:
break;
ip->op1 = OPT_FULL;
break;
case OPT_FULL:
-#ifdef STATISTICS
+#ifdef ENABLE_STATISTICS
ld->c_stat_full_opt++;
#endif
break;
int i, head, node;
struct Changes **changes;
- if ((changes = (struct Changes **) malloc(cd->maxlocals * sizeof(struct Changes *))) == NULL)
+ if ((changes = (struct Changes **) malloc(jd->maxlocals * sizeof(struct Changes *))) == NULL)
c_mem_error();
head = ld->c_current_head = lc->loop_head;
ld->c_needed_instr = ld->c_rs_needed_instr = 0;
/* init array for null ptr checks */
- for (i=0; i<cd->maxlocals; ++i)
+ for (i=0; i<jd->maxlocals; ++i)
ld->c_null_check[i] = 0;
d->changes = NULL;
}
- for (i=0; i < cd->maxlocals; ++i) {
+ for (i=0; i < jd->maxlocals; ++i) {
ld->c_var_modified[i] = 0;
if (changes[i] != NULL) {
changes[i] = NULL;
}
}
- for (i=0; i < (cd->maxlocals+1); ++i) {
+ for (i=0; i < (jd->maxlocals+1); ++i) {
if (ld->c_constraints[i] != NULL) {
ld->c_constraints[i] = NULL;
}
/* else
printf("No array accesses found\n"); */
-#ifdef STATISTICS
+#ifdef ENABLE_STATISTICS
ld->c_stat_num_loops++; /* increase number of loops */
ld->c_stat_sum_accesses += ld->c_stat_array_accesses;
}
-/* This function preforms necessary setup work, before the recursive function
- optimize_single loop can be called.
-*/
-void optimize_loops(methodinfo *m, codegendata *cd, loopdata *ld)
+/* optimize_loops **************************************************************
+
+ This function preforms necessary setup work, before the recursive
+ function optimize_single loop can be called.
+
+*******************************************************************************/
+
+void optimize_loops(jitdata *jd)
{
- LoopContainer *lc = ld->c_allLoops;
+ methodinfo *m;
+ codegendata *cd;
+ loopdata *ld;
+ LoopContainer *lc;
+
+ /* get required compiler data */
+
+ m = jd->m;
+ cd = jd->cd;
+ ld = jd->ld;
+
+ lc = ld->c_allLoops;
/* first, merge loops with same header node - all loops with the same */
/* header node are optimizied in one pass, because they all depend on the */
/* create array with entries for current loop */
ld->c_current_loop = DMNEW(int, m->basicblockcount);
ld->c_toVisit = DMNEW(int, m->basicblockcount);
- ld->c_var_modified = DMNEW(int, cd->maxlocals);
- ld->c_null_check = DMNEW(int, cd->maxlocals);
+ ld->c_var_modified = DMNEW(int, jd->maxlocals);
+ ld->c_null_check = DMNEW(int, jd->maxlocals);
- if ((ld->c_constraints = (struct Constraint **) malloc((cd->maxlocals+1) * sizeof(struct Constraint *))) == NULL)
+ if ((ld->c_constraints = (struct Constraint **) malloc((jd->maxlocals+1) * sizeof(struct Constraint *))) == NULL)
c_mem_error();
-#ifdef STATISTICS
+#ifdef ENABLE_STATISTICS
ld->c_stat_num_loops = 0; /* set statistic vars to zero */
ld->c_stat_array_accesses = ld->c_stat_sum_accesses = 0;
ld->c_stat_full_opt = ld->c_stat_sum_full = 0;
/* init vars needed by all loops */
ld->c_needs_redirection = false;
ld->c_newstart = NULL;
- ld->c_old_xtablelength = cd->exceptiontablelength;
+ ld->c_old_xtablelength = jd->exceptiontablelength;
/* loops have been topologically sorted */
lc = ld->c_allLoops;
projects / cacao.git / blobdiff