X-Git-Url: http://wien.tomnetworks.com/gitweb/?a=blobdiff_plain;f=src%2Fvm%2Fjit%2Floop%2Fanalyze.c;h=67f06a1f3b478e6302b60a19772f26b9ea698bb5;hb=9f859ad50d3d5d98c185d40b86b2179bc4dc9aeb;hp=fafc95c5f760b64e55abccf63bdf980c7a0c728b;hpb=7d8c359a29e6cd2db255619a11bb131f6d490557;p=cacao.git diff --git a/src/vm/jit/loop/analyze.c b/src/vm/jit/loop/analyze.c index fafc95c5f..67f06a1f3 100644 --- a/src/vm/jit/loop/analyze.c +++ b/src/vm/jit/loop/analyze.c @@ -1,9 +1,9 @@ -/* 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. @@ -19,28 +19,33 @@ 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 #include #include #include +#include "vm/types.h" + #include "mm/memory.h" #include "toolbox/logging.h" #include "vm/jit/jit.h" @@ -180,7 +185,7 @@ void show_tree(struct LoopContainer *lc, int tabs) #endif -#ifdef STATISTICS +#ifdef ENABLE_STATISTICS void show_loop_statistics(loopdata *ld) { @@ -322,7 +327,7 @@ void insert_exception(methodinfo *m, struct LoopContainer *lc, exceptiontable *e 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 */ @@ -492,8 +497,8 @@ void analyze_nested(methodinfo *m, codegendata *cd, loopdata *ld) 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 */ @@ -837,16 +842,16 @@ int analyze_or_exceptions(methodinfo *m, codegendata *cd, loopdata *ld, int head } 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) @@ -862,7 +867,7 @@ int analyze_or_exceptions(methodinfo *m, codegendata *cd, loopdata *ld, int head /* 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) { @@ -875,11 +880,11 @@ int analyze_or_exceptions(methodinfo *m, codegendata *cd, loopdata *ld, int head /* 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"); */ @@ -927,6 +932,12 @@ void init_constraints(methodinfo *m, loopdata *ld, int head) 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 */ @@ -1192,7 +1203,7 @@ void add_new_constraint(methodinfo *m, codegendata *cd, loopdata *ld, int type, 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) @@ -1208,8 +1219,8 @@ void add_new_constraint(methodinfo *m, codegendata *cd, loopdata *ld, int type, 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 */ @@ -1282,7 +1293,7 @@ void add_new_constraint(methodinfo *m, codegendata *cd, loopdata *ld, int type, /* 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) @@ -1297,8 +1308,8 @@ void add_new_constraint(methodinfo *m, codegendata *cd, loopdata *ld, int type, 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, */ @@ -1315,7 +1326,7 @@ void add_new_constraint(methodinfo *m, codegendata *cd, loopdata *ld, int type, /* 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)) @@ -1333,8 +1344,8 @@ void add_new_constraint(methodinfo *m, codegendata *cd, loopdata *ld, int type, 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 */ @@ -1380,7 +1391,7 @@ int insert_static(methodinfo *m, codegendata *cd, loopdata *ld, int arrayRef, st 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; @@ -1448,28 +1459,28 @@ int insert_static(methodinfo *m, codegendata *cd, loopdata *ld, int arrayRef, st /* 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; @@ -1478,14 +1489,14 @@ int insert_static(methodinfo *m, codegendata *cd, loopdata *ld, int arrayRef, st 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 */ @@ -1495,7 +1506,7 @@ int insert_static(methodinfo *m, codegendata *cd, loopdata *ld, int arrayRef, st 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; @@ -1731,7 +1742,8 @@ stackptr copy_stack_from(stackptr source) { 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); \ } \ } @@ -2308,7 +2320,7 @@ void copy_handler(methodinfo *m, loopdata *ld, struct LoopContainer *lc, basicbl /* 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; @@ -2490,7 +2502,7 @@ void update_internal_exceptions(methodinfo *m, codegendata *cd, loopdata *ld, st memcpy(new, ex, sizeof(exceptiontable)); /* Increase number of exceptions */ - ++cd->exceptiontablelength; + ++jd->exceptiontablelength; ex->next = new; ex->down = new; @@ -2538,7 +2550,7 @@ void update_external_exceptions(methodinfo *m, codegendata *cd, loopdata *ld, st /* Increase number of exceptions */ - ++cd->exceptiontablelength; + ++jd->exceptiontablelength; ex->next = new; ex->down = new; @@ -2579,7 +2591,11 @@ void create_static_checks(methodinfo *m, codegendata *cd, loopdata *ld, struct L stackptr newstack, tos; exceptiontable *ex; -#ifdef STATISTICS + /* prevent some compiler warnings */ + + bptr = NULL; + +#ifdef ENABLE_STATISTICS /* show_loop_statistics(l); */ #endif @@ -2592,7 +2608,7 @@ void create_static_checks(methodinfo *m, codegendata *cd, loopdata *ld, struct L { 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 */ @@ -2626,7 +2642,7 @@ void create_static_checks(methodinfo *m, codegendata *cd, loopdata *ld, struct L /* 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; @@ -2715,7 +2731,7 @@ void create_static_checks(methodinfo *m, codegendata *cd, loopdata *ld, struct L } /* adjust exceptions */ - ex = cd->exceptiontable; + ex = jd->exceptiontable; while (ex != NULL) { /* if an exception covers whole loop and starts at first loop node, it */ @@ -2758,7 +2774,7 @@ void create_static_checks(methodinfo *m, codegendata *cd, loopdata *ld, struct L stackdepth = loop_head->indepth; /* step through all inserted checks and create instructions for them */ - for (i=0; imaxlocals+1; ++i) + for (i=0; imaxlocals+1; ++i) { tc1 = ld->c_constraints[i]; while (tc1 != NULL) @@ -2879,7 +2895,7 @@ struct Changes ** constraints_unrestricted_merge(codegendata *cd, struct Changes printf("C_ERROR: debugging error 0x03\n"); changed = 0; - for (i=0; imaxlocals; ++i) { + for (i=0; imaxlocals; ++i) { if (c1[i] == NULL) { if (c2[i] != NULL) { /* a change in c2 is updated in c1 */ changed = 1; @@ -2928,7 +2944,7 @@ struct Changes ** constraints_merge(codegendata *cd, struct Changes **c1, struct changed = 0; - for (i=0; imaxlocals; ++i) { + for (i=0; imaxlocals; ++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) @@ -2971,10 +2987,10 @@ struct Changes** constraints_clone(codegendata *cd, struct Changes **c) 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; imaxlocals; ++i) { /* for all array elements (vars) do */ + for (i=0; imaxlocals; ++i) { /* for all array elements (vars) do */ if (c[i] == NULL) t[i] = NULL; else { @@ -3076,6 +3092,11 @@ void remove_boundchecks(methodinfo *m, codegendata *cd, loopdata *ld, int node, 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 */ @@ -3162,7 +3183,7 @@ void remove_boundchecks(methodinfo *m, codegendata *cd, loopdata *ld, int node, 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; @@ -3177,7 +3198,7 @@ void remove_boundchecks(methodinfo *m, codegendata *cd, loopdata *ld, int node, 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; @@ -3218,7 +3239,7 @@ void remove_boundchecks(methodinfo *m, codegendata *cd, loopdata *ld, int node, ip->op1 = OPT_FULL; break; case OPT_FULL: -#ifdef STATISTICS +#ifdef ENABLE_STATISTICS ld->c_stat_full_opt++; #endif break; @@ -3233,7 +3254,7 @@ void remove_boundchecks(methodinfo *m, codegendata *cd, loopdata *ld, int node, /* 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; @@ -3274,7 +3295,7 @@ void remove_boundchecks(methodinfo *m, codegendata *cd, loopdata *ld, int node, ip->op1 = OPT_FULL; break; case OPT_FULL: -#ifdef STATISTICS +#ifdef ENABLE_STATISTICS ld->c_stat_full_opt++; #endif break; @@ -3402,14 +3423,14 @@ void optimize_single_loop(methodinfo *m, codegendata *cd, loopdata *ld, LoopCont 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; imaxlocals; ++i) + for (i=0; imaxlocals; ++i) ld->c_null_check[i] = 0; @@ -3426,14 +3447,14 @@ void optimize_single_loop(methodinfo *m, codegendata *cd, loopdata *ld, LoopCont 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; } @@ -3536,7 +3557,7 @@ void optimize_single_loop(methodinfo *m, codegendata *cd, loopdata *ld, LoopCont /* 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; @@ -3558,12 +3579,27 @@ void optimize_single_loop(methodinfo *m, codegendata *cd, loopdata *ld, LoopCont } -/* 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 */ @@ -3595,13 +3631,13 @@ void optimize_loops(methodinfo *m, codegendata *cd, loopdata *ld) /* 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; @@ -3615,7 +3651,7 @@ void optimize_loops(methodinfo *m, codegendata *cd, loopdata *ld) /* 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;