-/* 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 665 2003-11-21 18:36:43Z jowenn $
-
*/
+#include "config.h"
+
+#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
-#include "analyze.h"
-#include "jit/jit.h"
-#include "loop.h"
-#include "graph.h"
-#include "tracing.h"
-#include "toolbox/loging.h"
-#include "toolbox/memory.h"
+
+#include "vm/types.h"
+
+#include "mm/memory.h"
+#include "toolbox/logging.h"
+#include "vm/jit/jit.h"
+#include "vm/jit/loop/analyze.h"
+#include "vm/jit/loop/graph.h"
+#include "vm/jit/loop/loop.h"
+#include "vm/jit/loop/tracing.h"
#ifdef LOOP_DEBUG
printf("Dynamic\t\t%d/%d\n", lv->dynamic_l, lv->dynamic_u);
}
-void show_right_side()
+void show_right_side(methodinfo *m)
{
int i;
printf("\n *** Head *** \nType:\t");
- show_trace(c_rightside);
+ show_trace(m->loopdata->c_rightside);
printf("\n *** Nested Loops: ***\n");
- for (i=0; i<block_count; ++i)
- printf("%d\t", c_nestedLoops[i]);
+ for (i=0; i<m->basicblockcount; ++i)
+ printf("%d\t", m->loopdata->c_nestedLoops[i]);
printf("\n");
printf("\n *** Hierarchie: ***\n");
- for (i=0; i<block_count; ++i)
- printf("%d\t", c_hierarchie[i]);
+ for (i=0; i<m->basicblockcount; ++i)
+ printf("%d\t", m->loopdata->c_hierarchie[i]);
printf("\n");
printf("\n *** Current Loop ***\n");
- for (i=0; i<block_count; ++i)
- printf("%d\t", c_current_loop[i]);
+ for (i=0; i<m->basicblockcount; ++i)
+ printf("%d\t", m->loopdata->c_current_loop[i]);
printf("\n");
}
-void resultPass3()
+void resultPass3(methodinfo *m)
{
int i;
- struct LoopContainer *lc = c_allLoops;
+ struct LoopContainer *lc = m->loopdata->c_allLoops;
printf("\n\n****** PASS 3 ******\n\n");
}
printf("\nNested Loops:\n");
- for (i=0; i<block_count; ++i)
- printf("%d ", c_nestedLoops[i]);
+ for (i=0; i<m->basicblockcount; ++i)
+ printf("%d ", m->loopdata->c_nestedLoops[i]);
printf("\n");
- for (i=0; i<block_count; ++i)
- printf("%d ", c_hierarchie[i]);
+ for (i=0; i<m->basicblockcount; ++i)
+ printf("%d ", m->loopdata->c_hierarchie[i]);
printf("\n");
fflush(stdout);
}
#endif
-#ifdef STATISTICS
+#ifdef ENABLE_STATISTICS
-void show_loop_statistics()
+void show_loop_statistics(loopdata *ld)
{
printf("\n\n****** LOOP STATISTICS ****** \n\n");
- if (c_stat_or)
+ if (ld->c_stat_or)
printf("Optimization cancelled by or\n");
- else if (c_stat_exception)
+ else if (ld->c_stat_exception)
printf("Optimization cancelled by exception\n");
else {
- printf("Number of array accesses:\t%d\n", c_stat_array_accesses);
- if (c_stat_array_accesses) {
- printf("\nFully optimized:\t%d\n", c_stat_full_opt);
- printf("Not optimized:\t\t%d\n", c_stat_no_opt);
- printf("Upper optimized:\t%d\n", c_stat_upper_opt);
- printf("Lower optimized:\t%d\n", c_stat_lower_opt);
+ printf("Number of array accesses:\t%d\n", ld->c_stat_array_accesses);
+ if (ld->c_stat_array_accesses) {
+ printf("\nFully optimized:\t%d\n", ld->c_stat_full_opt);
+ printf("Not optimized:\t\t%d\n", ld->c_stat_no_opt);
+ printf("Upper optimized:\t%d\n", ld->c_stat_upper_opt);
+ printf("Lower optimized:\t%d\n", ld->c_stat_lower_opt);
}
}
}
-void show_procedure_statistics()
+void show_procedure_statistics(loopdata *ld)
{
printf("\n\n****** PROCEDURE STATISTICS ****** \n\n");
- printf("Number of loops:\t\t%d\n", c_stat_num_loops);
- printf("Number of array accesses:\t%d\n", c_stat_sum_accesses);
- if (c_stat_sum_accesses) {
- printf("\nFully optimized:\t%d\n", c_stat_sum_full);
- printf("Not optimized:\t\t%d\n", c_stat_sum_no);
- printf("Upper optimized:\t%d\n", c_stat_sum_upper);
- printf("Lower optimized:\t%d\n", c_stat_sum_lower);
+ printf("Number of loops:\t\t%d\n", ld->c_stat_num_loops);
+ printf("Number of array accesses:\t%d\n", ld->c_stat_sum_accesses);
+ if (ld->c_stat_sum_accesses) {
+ printf("\nFully optimized:\t%d\n", ld->c_stat_sum_full);
+ printf("Not optimized:\t\t%d\n", ld->c_stat_sum_no);
+ printf("Upper optimized:\t%d\n", ld->c_stat_sum_upper);
+ printf("Lower optimized:\t%d\n", ld->c_stat_sum_lower);
}
- printf("Opt. cancelled by or:\t\t%d\n", c_stat_sum_or);
- printf("Opt. cancelled by exception:\t%d\n", c_stat_sum_exception);
+ printf("Opt. cancelled by or:\t\t%d\n", ld->c_stat_sum_or);
+ printf("Opt. cancelled by exception:\t%d\n", ld->c_stat_sum_exception);
}
#endif
finding algorith sometimes (eg. when loopbody ends with a if-else construct)
reports a single loop as two loops with the same header node.
*/
-void analyze_double_headers()
+void analyze_double_headers(loopdata *ld)
{
int toCheck;
- struct LoopContainer *t1, *t2, *t3;
+ LoopContainer *t1, *t2, *t3;
- t1 = c_allLoops;
+ t1 = ld->c_allLoops;
while (t1 != NULL) { /* for all loops do */
toCheck = t1->loop_head; /* get header node */
into this tree. The exception ex is inserted into the subtree pointed to by
LoopContainer lc.
*/
-void insert_exception(struct LoopContainer *lc, xtable *ex)
+void insert_exception(methodinfo *m, struct LoopContainer *lc, exceptiontable *ex)
{
struct LoopContainer *temp;
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 */
#endif
/* if the start of the exception is part of the loop, the */
/* whole exception must be part of the loop */
- if (le->node == block_index[ex->startpc])
+ if (le->node == m->basicblockindex[ex->startpc])
break;
le = le->next;
}
/* Exception is part of a nested loop (Case 1) -> insert it there */
if (le != NULL) {
- insert_exception(temp, ex);
+ insert_exception(m, temp, ex);
return;
}
- else if ((temp->loop_head >= block_index[ex->startpc]) && (temp->loop_head < block_index[ex->endpc])) {
+ else if ((temp->loop_head >= m->basicblockindex[ex->startpc]) && (temp->loop_head < m->basicblockindex[ex->endpc])) {
/* optimization: if nested loop is part of the exception, the */
/* exception cannot be part of a differnet nested loop. */
Each loop, that is a nested loop, stores its direct surrounding loop as a
parent. Top level loops have no parents.
*/
-void analyze_nested()
+
+void analyze_nested(methodinfo *m, codegendata *cd, loopdata *ld)
{
/* i/count/tmp are counters */
/* toOverwrite is used while loop hierarchie is built (see below) */
struct LoopElement *le;
/* init global structures */
- c_nestedLoops = DMNEW(int, block_count);
- c_hierarchie = DMNEW(int, block_count);
- for (i=0; i<block_count; ++i) {
- c_nestedLoops[i] = -1;
- c_hierarchie[i] = -1;
+ ld->c_nestedLoops = DMNEW(int, m->basicblockcount);
+ ld->c_hierarchie = DMNEW(int, m->basicblockcount);
+ for (i=0; i<m->basicblockcount; ++i) {
+ ld->c_nestedLoops[i] = -1;
+ ld->c_hierarchie[i] = -1;
}
/* if there are no optimizable loops -> return */
- if (c_allLoops == NULL)
+ if (ld->c_allLoops == NULL)
return;
- temp = c_allLoops;
+ temp = ld->c_allLoops;
while (temp != NULL) { /* for all loops, do */
header = temp->loop_head;
/* toOverwrite is number of current parent loop (-1 if none) */
- toOverwrite = c_nestedLoops[header];
+ toOverwrite = ld->c_nestedLoops[header];
- c_hierarchie[header] = toOverwrite;
+ ld->c_hierarchie[header] = toOverwrite;
if (toOverwrite == header) /* check for loops with same header */
printf("C_ERROR: Loops have same header\n");
le = temp->nodes;
while (le != NULL) { /* for all loop nodes, do */
- tmp = c_nestedLoops[le->node];
+ tmp = ld->c_nestedLoops[le->node];
/* if node is part of parent loop -> overwrite it with nested */
if (tmp == toOverwrite)
- c_nestedLoops[le->node] = header;
+ ld->c_nestedLoops[le->node] = header;
else {
- c_hierarchie[tmp] = header;
+ ld->c_hierarchie[tmp] = header;
#ifdef LOOP_DEBUG
/* printf("set head of %d to %d", tmp, header); */
#endif
}
/* init root of hierarchie tree */
- root = DMNEW(struct LoopContainer, 1);
- LoopContainerInit(root, -1);
+ ld->root = DMNEW(struct LoopContainer, 1);
+ LoopContainerInit(m, ld->root, -1);
/* obtain parent pointer and build hierarchie tree */
- start = c_allLoops;
+ start = ld->c_allLoops;
while (start != NULL) {
/* look for parent of loop pointed at by start */
- first = c_allLoops;
+ first = ld->c_allLoops;
while (first != NULL) {
/* the parent of the loop, pointed at by start has been found */
- if (first->loop_head == c_hierarchie[start->loop_head]) {
+ if (first->loop_head == ld->c_hierarchie[start->loop_head]) {
#ifdef LOOP_DEBUG
/* printf("set parent to pointer\n"); */
#endif
/* printf("set parent to root\n"); */
#endif
- start->parent = root;
- start->tree_right = root->tree_down;
- root->tree_down = start;
+ start->parent = ld->root;
+ start->tree_right = ld->root->tree_down;
+ ld->root->tree_down = start;
}
/* if a parent exists, increase this nodes indegree */
else
/* insert exceptions into tree */
#ifdef LOOP_DEBUG
printf("--- Showing tree ---\n");
- show_tree(root, 0);
+ show_tree(ld->root, 0);
printf(" --- End ---\n");
#endif
- for (len = 0; len < exceptiontablelength; ++len)
- insert_exception(root, extable + 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 */
/* init queue */
start = NULL;
- temp = c_allLoops;
+ temp = ld->c_allLoops;
while (temp != NULL) {
/* a loops with indegree == 0 are pushed onto the stack */
/* pop each node from the stack and decrease its parents indegree by one */
/* when the parents indegree reaches zero, push it onto the stack as well */
- if ((last->parent != root) && (--last->parent->in_degree == 0)) {
+ if ((last->parent != ld->root) && (--last->parent->in_degree == 0)) {
last->parent->next = start;
start = last->parent;
}
start = start->next;
last = last->next;
- if ((last->parent != root) && (--last->parent->in_degree == 0)) {
+ if ((last->parent != ld->root) && (--last->parent->in_degree == 0)) {
last->parent->next = start;
start = last->parent;
}
}
last->next = NULL;
- c_allLoops = first;
+ ld->c_allLoops = first;
#ifdef LOOP_DEBUG
printf("*** Hierarchie Results \n");
#endif
}
+
/* This function is used to add variables that occur as index variables in
array accesses (ARRAY_INDEX) or as variables, that change their value (VAR_MOD)
to the list of interesting vars (c_loopvars) for the current loop.
*/
-void add_to_vars(int var, int type, int direction)
+
+void add_to_vars(loopdata *ld, int var, int type, int direction)
{
struct LoopVar *lv;
/* printf("Added to vars %d %d %d\n", var, type, direction); */
- lv = c_loopvars;
+ lv = ld->c_loopvars;
while (lv != NULL) { /* check if var has been previously added */
if (lv->value == var) {
if (type == ARRAY_INDEX)
/* no dynamic bounds have been determined so far */
lv->dynamic_l = lv->dynamic_l_v = lv->dynamic_u = lv->dynamic_u_v = 0;
- lv->next = c_loopvars; /* add var to list */
- c_loopvars = lv;
+ lv->next = ld->c_loopvars; /* add var to list */
+ ld->c_loopvars = lv;
}
+
/* This function checks, whether a given loop with header node contains array
accesses. If so, it returns 1, else it returns 0 and the loops needs no
further consideration in the optimization process. When array accesses are
stored in c_loopvars. For all variables (integer), which values are changed,
a flag in c_var_modified is set.
*/
-int analyze_for_array_access(int node)
+
+int analyze_for_array_access(methodinfo *m, loopdata *ld, int node)
{
basicblock bp;
instruction *ip;
struct depthElement *d;
struct Trace *t;
- if (c_toVisit[node] > 0) { /* node has not been visited yet */
- c_toVisit[node] = 0;
+ if (ld->c_toVisit[node] > 0) { /* node has not been visited yet */
+ ld->c_toVisit[node] = 0;
- bp = block[node]; /* prepare an instruction scan */
+ bp = m->basicblocks[node]; /* prepare an instruction scan */
ip = bp.iinstr;
ic = bp.icount;
if (t->type == TRACE_IVAR) {
/* if it is a variable, add it to list of index variables */
- add_to_vars(t->var, ARRAY_INDEX, D_UNKNOWN);
+ add_to_vars(ld, t->var, ARRAY_INDEX, D_UNKNOWN);
access++;
}
else if (t->type == TRACE_ICONST)
if (t->type == TRACE_IVAR) {
/* if it is a variable, add it to list of index variables */
- add_to_vars(t->var, ARRAY_INDEX, D_UNKNOWN);
+ add_to_vars(ld, t->var, ARRAY_INDEX, D_UNKNOWN);
access++;
}
else if (t->type == TRACE_ICONST)
break;
case ICMD_ISTORE: /* integer store */
- c_var_modified[ip->op1] = 1;
+ ld->c_var_modified[ip->op1] = 1;
/* try to find out, how it was modified */
t = tracing(&bp, i-1, 0);
if (t->type == TRACE_IVAR) {
if ((t->constant > 0) && (t->var == ip->op1))
/* a constant was added to the same var */
- add_to_vars(t->var, VAR_MOD, D_UP);
+ add_to_vars(ld, t->var, VAR_MOD, D_UP);
else if (t->var == ip->op1)
/* a constant was subtracted from the same var */
- add_to_vars(t->var, VAR_MOD, D_DOWN);
+ add_to_vars(ld, t->var, VAR_MOD, D_DOWN);
else
- add_to_vars(t->var, VAR_MOD, D_UNKNOWN);
+ add_to_vars(ld, t->var, VAR_MOD, D_UNKNOWN);
}
else
- add_to_vars(ip->op1, VAR_MOD, D_UNKNOWN);
+ add_to_vars(ld, ip->op1, VAR_MOD, D_UNKNOWN);
break;
case ICMD_IINC: /* simple add/sub of a constant */
- c_var_modified[ip->op1] = 1;
+ ld->c_var_modified[ip->op1] = 1;
if (ip->val.i > 0)
- add_to_vars(ip->op1, VAR_MOD, D_UP);
+ add_to_vars(ld, ip->op1, VAR_MOD, D_UP);
else
- add_to_vars(ip->op1, VAR_MOD, D_DOWN);
+ add_to_vars(ld, ip->op1, VAR_MOD, D_DOWN);
break;
case ICMD_LSTORE:
case ICMD_FSTORE:
case ICMD_DSTORE:
case ICMD_ASTORE:
- c_var_modified[ip->op1] = 1;
+ ld->c_var_modified[ip->op1] = 1;
break;
}
}
- d = c_dTable[node];
+ d = ld->c_dTable[node];
while (d != NULL) { /* check all successors of block */
- access += analyze_for_array_access(d->value);
+ access += analyze_for_array_access(m, ld, d->value);
d = d->next;
}
return 0;
}
+
/* This function scans the exception graph structure to find modifications of
array index variables of the current loop. If any modifications are found,
1 is returned, else 0.
*/
-int quick_scan(int node)
+
+int quick_scan(methodinfo *m, loopdata *ld, int node)
{
basicblock bp;
instruction *ip;
int count, i;
struct LoopVar *lv;
struct depthElement *d;
-
- /* printf("QS: %d - %d\n", node, c_exceptionVisit[node]); */
+
+ /* printf("QS: %d - %d\n", node, ld->c_exceptionVisit[node]); */
- if (c_exceptionVisit[node] > 0) { /* node is part of exception graph */
- c_exceptionVisit[node] = -1;
+ if (ld->c_exceptionVisit[node] > 0) { /* node is part of exception graph */
+ ld->c_exceptionVisit[node] = -1;
- bp = block[node]; /* setup scan of all instructions */
+ bp = m->basicblocks[node]; /* setup scan of all instructions */
ip = bp.iinstr;
count = bp.icount;
case ICMD_ISTORE:
case ICMD_IINC: /* a variable is modified */
- lv = c_loopvars; /* is it an array index var ? */
+ lv = ld->c_loopvars; /* is it an array index var ? */
while (lv != NULL) {
if ((lv->index) && (lv->value == ip->op1))
return 1; /* yes, so return 1 */
}
}
- d = c_exceptionGraph[node]; /* check all successor nodes */
+ d = ld->c_exceptionGraph[node]; /* check all successor nodes */
while (d != NULL) {
- if (quick_scan(d->value) > 0)
+ if (quick_scan(m, ld, d->value) > 0)
return 1; /* if an access is found return 1 */
d = d->next;
}
return 0;
}
+
/* This function returns 1, when the condition of the loop contains
or statements or when an array index variable is modified in any
catch block within the loop.
*/
-int analyze_or_exceptions(int head, struct LoopContainer *lc)
+
+int analyze_or_exceptions(methodinfo *m, codegendata *cd, loopdata *ld, int head, struct LoopContainer *lc)
{
struct depthElement *d;
int i, k, value, flag, count;
struct LoopElement *le;
- d = c_dTable[head];
+ d = ld->c_dTable[head];
count = flag = 0;
/* analyze for or-statements */
}
if ((count > 1) && (flag == 0)){/* if all successors part of the loop, exit */
-#ifdef STATISTICS
- c_stat_or++;
+#ifdef ENABLE_STATISTICS
+ ld->c_stat_or++;
#endif
return 0;
}
/* check for exceptions */
- /* printf("done\n*** Analyze for EXCEPTIONS(%d) . ", exceptiontablelength); */
+ /* printf("done\n*** Analyze for EXCEPTIONS(%d) . ", jd->exceptiontablelength); */
- if (!exceptiontablelength) /* when there are no exceptions, exit */
+ if (!jd->exceptiontablelength) /* when there are no exceptions, exit */
return 1;
- if ((c_exceptionGraph = (struct depthElement **) malloc(sizeof(struct depthElement *) * block_count)) == NULL)
+ if ((ld->c_exceptionGraph = (struct depthElement **) malloc(sizeof(struct depthElement *) * m->basicblockcount)) == NULL)
c_mem_error();
- if ((c_exceptionVisit = (int *) malloc(sizeof(int) * block_count)) == NULL)
+ if ((ld->c_exceptionVisit = (int *) malloc(sizeof(int) * m->basicblockcount)) == NULL)
c_mem_error();
- for (k=0; k<block_count; ++k) {
- c_exceptionVisit[k] = -1;
- c_exceptionGraph[k] = NULL;
+ for (k=0; k<m->basicblockcount; ++k) {
+ ld->c_exceptionVisit[k] = -1;
+ ld->c_exceptionGraph[k] = NULL;
}
/* for all nodes that start catch block check whether they are part of loop */
- for (i = 0; i < c_old_xtablelength; i++) {
- value = block_index[extable[i].startpc];
+ for (i = 0; i < ld->c_old_xtablelength; i++) {
+ 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(-1, block_index[extable[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(block_index[extable[i].handlerpc]) > 0) {
-#ifdef STATISTICS
- c_stat_exception++;
+ 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"); */
return 0;
return 1;
}
+
/* This function sets a flag in c_var_modified for all variables that have
been found as part of an assigment in the loop.
*/
-void scan_global_list()
+
+void scan_global_list(loopdata *ld)
{
struct LoopVar *lv;
- lv = c_loopvars;
+ lv = ld->c_loopvars;
while (lv != NULL) {
if (lv->modified)
- c_var_modified[lv->value] = 1;
+ ld->c_var_modified[lv->value] = 1;
lv = lv->next;
}
}
+
/* This function analyses the condition in the loop header and trys to find
out, whether some dynamic guarantees can be set up.
*/
-void init_constraints(int head)
+
+void init_constraints(methodinfo *m, loopdata *ld, int head)
{
basicblock bp;
instruction *ip;
struct Trace *left, *right, *th;
struct LoopVar *lv_left, *lv_right, *lh;
- bp = block[head];
+ /* 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 */
l_mod = r_mod = 0;
if (left->type == TRACE_IVAR) { /* is a loop variable on left side ? */
- lv_left = c_loopvars;
+ lv_left = ld->c_loopvars;
while (lv_left != NULL) {
if (lv_left->value == left->var) {
l_mod = lv_left->modified; /* yes, but has it been modified ? */
}
if (right->type == TRACE_IVAR){ /* is a loop variable on right side ? */
- lv_right = c_loopvars;
+ lv_right = ld->c_loopvars;
while (lv_right != NULL) {
if (lv_right->value == right->var) {
r_mod = lv_right->modified; /* yes, but has it been modified ? */
}
if ((l_mod - r_mod) == 0) { /* both 1 or both 0 -> no dynamic contraints*/
- c_rightside = NULL; /* possible */
+ ld->c_rightside = NULL; /* possible */
return;
}
/* make sure that right side's value does not change during loop execution */
if (right->type == TRACE_UNKNOWN) {
- c_rightside = NULL;
+ ld->c_rightside = NULL;
return;
}
printf("C_ERROR: debugging error 0x01\n");
}
- c_rightside = right;
+ ld->c_rightside = right;
- switch (c_rightside->type) {
+ switch (ld->c_rightside->type) {
case TRACE_ICONST:
- c_rs_needed_instr = 1;
+ ld->c_rs_needed_instr = 1;
break;
case TRACE_ALENGTH:
- c_rs_needed_instr = 2;
+ ld->c_rs_needed_instr = 2;
break;
case TRACE_IVAR:
- c_rs_needed_instr = 3;
+ ld->c_rs_needed_instr = 3;
break;
default:
printf("C_ERROR: wrong right-side type\n");
}
}
+
/* This function is needed to add and record new static tests (before loop
entry) of variables to make guaratees for index variables. type states
the kind of the test. arrayRef is the array, which length is tested
against, varRef is the variable, that is testes and constant is the
constant value, that is tested.
*/
-void add_new_constraint(int type, int arrayRef, int varRef, int constant)
+
+void add_new_constraint(methodinfo *m, codegendata *cd, loopdata *ld, int type, int arrayRef, int varRef, int constant)
{
struct Constraint *tc;
switch (type) {
case TEST_ZERO: /* a variable is tested against a const */
- tc = c_constraints[varRef]; /* does a test already exist for this var ? */
+ tc = ld->c_constraints[varRef]; /* does a test already exist for this var ? */
while (tc != NULL) {
if (tc->type == TEST_ZERO) {
if (constant < tc->constant)
tc->type = TEST_ZERO;
tc->varRef = varRef;
tc->constant = constant;
- tc->next = c_constraints[varRef];
- c_constraints[varRef] = tc;
- c_needed_instr += 3;
+ tc->next = ld->c_constraints[varRef];
+ ld->c_constraints[varRef] = tc;
+ ld->c_needed_instr += 3;
break;
case TEST_ALENGTH: /* variable is tested against array length */
- tc = c_constraints[varRef]; /* does a test already exist for this var ? */
+ tc = ld->c_constraints[varRef]; /* does a test already exist for this var ? */
while (tc != NULL) {
if ((tc->type == TEST_ALENGTH) && (tc->arrayRef == arrayRef)) {
if (constant > tc->constant)
tc->arrayRef = arrayRef;
tc->varRef = varRef;
tc->constant = constant;
- tc->next = c_constraints[varRef];
- c_constraints[varRef] = tc;
- c_needed_instr += 6;
+ tc->next = ld->c_constraints[varRef];
+ ld->c_constraints[varRef] = tc;
+ ld->c_needed_instr += 6;
/* if arrayRef is not already tested against null, insert that test */
- if (!(c_null_check[arrayRef])) {
- c_null_check[arrayRef] = 1;
- c_needed_instr +=2;
+ if (!(ld->c_null_check[arrayRef])) {
+ ld->c_null_check[arrayRef] = 1;
+ ld->c_needed_instr +=2;
}
break;
case TEST_CONST_ALENGTH: /* a const is tested against array length */
/* does a test already exist for this array */
- tc = c_constraints[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 = c_constraints[maxlocals];
- c_constraints[maxlocals] = tc;
- c_needed_instr += 4;
+ 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 */
- if (!(c_null_check[arrayRef])) {
- c_null_check[arrayRef] = 1;
- c_needed_instr +=2;
+ if (!(ld->c_null_check[arrayRef])) {
+ ld->c_null_check[arrayRef] = 1;
+ ld->c_needed_instr +=2;
}
break;
case TEST_UNMOD_ZERO: /* test unmodified var against constant */
/* search if test already exists */
- tc = c_constraints[varRef];
+ tc = ld->c_constraints[varRef];
while (tc != NULL) {
if (tc->type == TEST_UNMOD_ZERO) {
if (constant < tc->constant)
tc->type = TEST_UNMOD_ZERO;
tc->varRef = varRef;
tc->constant = constant;
- tc->next = c_constraints[varRef];
- c_constraints[varRef] = tc;
- c_needed_instr += 3;
+ tc->next = ld->c_constraints[varRef];
+ ld->c_constraints[varRef] = tc;
+ ld->c_needed_instr += 3;
break;
case TEST_UNMOD_ALENGTH: /* test unmodified var against array length */
/* search if test alreay exists */
- tc = c_constraints[varRef];
+ tc = ld->c_constraints[varRef];
while (tc != NULL) {
if ((tc->type == TEST_UNMOD_ALENGTH) && (tc->arrayRef == arrayRef)) {
if (constant > tc->constant)
tc->varRef = varRef;
tc->arrayRef = arrayRef;
tc->constant = constant;
- tc->next = c_constraints[varRef];
- c_constraints[varRef] = tc;
- c_needed_instr += 6;
+ tc->next = ld->c_constraints[varRef];
+ ld->c_constraints[varRef] = tc;
+ ld->c_needed_instr += 6;
/* if arrayRef is not already tested against null, insert that test */
- if (!(c_null_check[arrayRef])) {
- c_null_check[arrayRef] = 1;
- c_needed_instr +=2;
+ if (!(ld->c_null_check[arrayRef])) {
+ ld->c_null_check[arrayRef] = 1;
+ ld->c_needed_instr +=2;
}
break;
/* checks */
/*!! varRef -> maxlocals */
/* search if test already exists */
- tc = c_constraints[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 = c_constraints[maxlocals];
- c_constraints[maxlocals] = tc;
- c_needed_instr += (2 + c_rs_needed_instr);
+ 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, */
/* insert that test */
- if ((c_rightside->type == TRACE_ALENGTH) && (!(c_null_check[c_rightside->var]))) {
- c_null_check[c_rightside->var] = 1;
- c_needed_instr +=2;
+ if ((ld->c_rightside->type == TRACE_ALENGTH) && (!(ld->c_null_check[ld->c_rightside->var]))) {
+ ld->c_null_check[ld->c_rightside->var] = 1;
+ ld->c_needed_instr +=2;
}
break;
/* checks */
/*!! varRef -> maxlocals */
/* search if test already exists */
- tc = c_constraints[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 = c_constraints[maxlocals];
- c_constraints[maxlocals] = tc;
- c_needed_instr += (3 + c_rs_needed_instr);
+ 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 */
- if (!(c_null_check[arrayRef])) {
- c_null_check[arrayRef] = 1;
- c_needed_instr +=2;
+ if (!(ld->c_null_check[arrayRef])) {
+ ld->c_null_check[arrayRef] = 1;
+ ld->c_needed_instr +=2;
}
/* if arrayRef on right side is not already tested against null, */
/* insert that test */
- if ((c_rightside->type == TRACE_ALENGTH) && (!(c_null_check[c_rightside->var]))) {
- c_null_check[c_rightside->var] = 1;
- c_needed_instr +=2;
+ if ((ld->c_rightside->type == TRACE_ALENGTH) && (!(ld->c_null_check[ld->c_rightside->var]))) {
+ ld->c_null_check[ld->c_rightside->var] = 1;
+ ld->c_needed_instr +=2;
}
break;
}
}
+
/* This functions adds new static (before loop enry) tests of variables to the
program to be able to guarantee certain values for index variables in array
access (to safely remove bound checks).
*/
-int insert_static(int arrayRef, struct Trace *index, struct Changes *varChanges, int special)
+
+int insert_static(methodinfo *m, codegendata *cd, loopdata *ld, int arrayRef, struct Trace *index, struct Changes *varChanges, int special)
{
struct LoopVar *lv;
int varRef;
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
- c_stat_no_opt++;
+#ifdef ENABLE_STATISTICS
+ ld->c_stat_no_opt++;
#endif
return OPT_NONE;
}
varRef = index->var;
high = low = 0;
- if (c_var_modified[varRef]) { /* volatile var */
+ if (ld->c_var_modified[varRef]) { /* volatile var */
- lv = c_loopvars; /* get reference to loop variable */
+ lv = ld->c_loopvars; /* get reference to loop variable */
while ((lv != NULL) && (lv->value != varRef))
lv = lv->next;
/* the var is never decremented, so we add a static test againt */
/* constant */
if (varChanges->lower_bound > varChanges->upper_bound)
- add_new_constraint(TEST_ZERO, arrayRef, varRef, index->constant);
+ add_new_constraint(m, cd, ld, TEST_ZERO, arrayRef, varRef, index->constant);
else
- add_new_constraint(TEST_ZERO, arrayRef, varRef, varChanges->lower_bound+index->constant);
+ add_new_constraint(m, cd, ld, TEST_ZERO, arrayRef, varRef, varChanges->lower_bound+index->constant);
low = 1;
}
else if ((lv->dynamic_l_v) && (!special)) {
/* the variable is decremented, but it is checked against a */
/* bound in the loop condition */
if (varChanges->lower_bound <= varChanges->upper_bound) {
- add_new_constraint(TEST_RS_ZERO, arrayRef, varRef, varChanges->lower_bound+index->constant+lv->dynamic_l);
+ add_new_constraint(m, cd, ld, TEST_RS_ZERO, arrayRef, varRef, varChanges->lower_bound+index->constant+lv->dynamic_l);
low = 1;
}
}
/* the var is never incremented, so we add a static test againt */
/* constant */
if (varChanges->lower_bound > varChanges->upper_bound)
- add_new_constraint(TEST_ALENGTH, arrayRef, varRef, index->constant);
+ add_new_constraint(m, cd, ld, TEST_ALENGTH, arrayRef, varRef, index->constant);
else
- add_new_constraint(TEST_ALENGTH, arrayRef, varRef, varChanges->upper_bound+index->constant);
+ add_new_constraint(m, cd, ld, TEST_ALENGTH, arrayRef, varRef, varChanges->upper_bound+index->constant);
high = 1;
}
else if ((lv->dynamic_u_v) && (!special)) {
/* the variable is decremented, but it is checked against a */
/* bound in the loop condition */
if (varChanges->lower_bound <= varChanges->upper_bound) {
- add_new_constraint(TEST_RS_ALENGTH, arrayRef, varRef, varChanges->upper_bound+index->constant+lv->dynamic_u);
+ add_new_constraint(m, cd, ld, TEST_RS_ALENGTH, arrayRef, varRef, varChanges->upper_bound+index->constant+lv->dynamic_u);
high = 1;
}
}
}
else { /* the var is never modified at all */
- add_new_constraint(TEST_UNMOD_ZERO, arrayRef, index->var, index->constant);
- add_new_constraint(TEST_UNMOD_ALENGTH, arrayRef, index->var, index->constant);
+ add_new_constraint(m, cd, ld, TEST_UNMOD_ZERO, arrayRef, index->var, index->constant);
+ add_new_constraint(m, cd, ld, TEST_UNMOD_ALENGTH, arrayRef, index->var, index->constant);
low = high = 1;
}
/* return the best possible optimization */
if ((high > 0) && (low > 0)) {
/* printf("fully optimzed\n"); */
-#ifdef STATISTICS
- c_stat_full_opt++;
+#ifdef ENABLE_STATISTICS
+ ld->c_stat_full_opt++;
#endif
return OPT_FULL;
}
else if (high > 0) {
/* printf("upper optimzed\n"); */
-#ifdef STATISTICS
- c_stat_upper_opt++;
+#ifdef ENABLE_STATISTICS
+ ld->c_stat_upper_opt++;
#endif
return OPT_UPPER;
}
else if (low > 0) {
/* printf("lower optimzed\n"); */
-#ifdef STATISTICS
- c_stat_lower_opt++;
+#ifdef ENABLE_STATISTICS
+ ld->c_stat_lower_opt++;
#endif
return OPT_LOWER;
}
else {
/* printf("not optimzed\n"); */
-#ifdef STATISTICS
- c_stat_no_opt++;
+#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
- c_stat_no_opt++;
+#ifdef ENABLE_STATISTICS
+ ld->c_stat_no_opt++;
#endif
return OPT_NONE; /* negative index -> bad */
}
else {
- add_new_constraint(TEST_CONST_ALENGTH, arrayRef, 0, index->constant);
-#ifdef STATISTICS
- c_stat_full_opt++;
+ add_new_constraint(m, cd, ld, TEST_CONST_ALENGTH, arrayRef, 0, index->constant);
+#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
- c_stat_no_opt++;
+#ifdef ENABLE_STATISTICS
+ ld->c_stat_no_opt++;
#endif
return OPT_NONE;
}
/* fisrt, the reference must be loaded, then a null-pointer check is inserted */
/* if not already done earlier. Finally an arraylength instruction is added */
#define LOAD_ARRAYLENGTH(a) { \
- if (c_null_check[a]) { \
+ if (ld->c_null_check[a]) { \
LOAD_ADDR(a); \
GOTO_NOOPT_IF_NULL; \
- c_null_check[a] = 0; \
+ ld->c_null_check[a] = 0; \
} \
LOAD_ADDR(a); \
inst->opc = ICMD_ARRAYLENGTH; \
/* Depending of the type of the right side, the apropriate instructions are */
/* created. */
#define LOAD_RIGHT_SIDE { \
- switch (c_rightside->type) { \
+ switch (ld->c_rightside->type) { \
case TRACE_ICONST: \
- LOAD_CONST(c_rightside->constant); \
+ LOAD_CONST(ld->c_rightside->constant); \
break; \
case TRACE_IVAR: \
- LOAD_VAR(c_rightside->var); \
- LOAD_CONST(c_rightside->constant); \
+ LOAD_VAR(ld->c_rightside->var); \
+ LOAD_CONST(ld->c_rightside->constant); \
ADD; \
break; \
case TRACE_ALENGTH: \
- LOAD_ARRAYLENGTH(c_rightside->var); \
+ 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); \
} \
}
}
}
+
/* Add the new header node of a loop that has been duplicated to all parent
loops in nesting hierarchie.
*/
-void header_into_parent_loops(struct LoopContainer *lc, basicblock *to_insert, basicblock *replace, basicblock *after)
+
+void header_into_parent_loops(loopdata *ld, struct LoopContainer *lc, basicblock *to_insert, basicblock *replace, basicblock *after)
{
/* we have to insert the node to_insert before the node after and replace */
/* the pointer of to_insert by the node replace */
struct LoopElement *le, *t;
/* if the top of the tree is reached, then return */
- if ((lc == NULL) || (lc == root))
+ if ((lc == NULL) || (lc == ld->root))
return;
/* create new node, that should be inserted */
}
/* go up one hierarchie level */
- header_into_parent_loops(lc->parent, to_insert, replace, after);
+ header_into_parent_loops(ld, lc->parent, to_insert, replace, after);
}
+
/* Add a new node (not header) of a duplicated loop to all parent loops in
nesting hierarchie
*/
-void node_into_parent_loops(struct LoopContainer *lc, basicblock *to_insert)
+
+void node_into_parent_loops(loopdata *ld, struct LoopContainer *lc, basicblock *to_insert)
{
struct LoopElement *le, *t;
/* if the top of the tree is reached, then return */
- if ((lc == NULL) || (lc == root))
+ if ((lc == NULL) || (lc == ld->root))
return;
/* create new node, that should be inserted */
- t = DMNEW(struct LoopElement, 1);
+ t = DNEW(LoopElement);
t->block = to_insert;
t->node = -1;
le->next = t;
/* go up one hierarchie level */
- node_into_parent_loops(NULL, to_insert);
+ node_into_parent_loops(ld, NULL, to_insert);
}
to redirect internal jumps inside the exception handler to the newly
created (copied) nodes.
*/
+
void patch_handler(struct LoopContainer *lc, basicblock *bptr, basicblock *original_head, basicblock *new_head)
{
instruction *ip;
}
-/* This function copys the exception handler and redirects all jumps from the
+/* copy_handler ****************************************************************
+
+ This function copys the exception handler and redirects all jumps from the
original head to the new head in the original exception handler. All
redirection in the copied exception handler is done in patch_handler(...).
-*/
-void copy_handler(struct LoopContainer *lc, basicblock *bptr, basicblock *original_head, basicblock *new_head)
+
+*******************************************************************************/
+
+void copy_handler(methodinfo *m, loopdata *ld, struct LoopContainer *lc, basicblock *bptr, basicblock *original_head, basicblock *new_head)
{
instruction *ip;
s4 *s4ptr;
void **tptr;
int high, low, count;
struct LoopElement *le;
- basicblock *new;
+ basicblock *new, *temp;
- /* If this node has already been copied, return */
+ /* If this node has already been copied, return */
if (bptr->lflags & HANDLER_PART)
return;
- /* The exception handler exists, when control flow enters loop again */
+ /* The exception handler exists, when control flow enters loop again */
if (bptr->lflags & LOOP_PART)
return;
}
}
- /* mark block as part of handler */
+ /* mark block as part of handler */
bptr->lflags |= HANDLER_PART;
- /* copy node */
+ /* copy node */
new = DMNEW(basicblock, 1);
memcpy(new, bptr, sizeof(basicblock));
- new->debug_nr = c_debug_nr++;
+ new->nr = -1;
- c_last_block_copied = new;
+ ld->c_last_block_copied = new;
- /* copy instructions and allow one more slot for possible GOTO */
+ /* copy instructions and allow one more slot for possible GOTO */
new->iinstr = DMNEW(instruction, bptr->icount + 1);
- memcpy(new->iinstr, bptr->iinstr, bptr->icount*sizeof(instruction));
+ memcpy(new->iinstr, bptr->iinstr, bptr->icount * sizeof(instruction));
- /* update original block */
+ /* update original block */
bptr->copied_to = new;
- /* append block to global list of basic blocks */
- last_block->next = new;
- last_block = new;
+ /* append block to global list of basic blocks */
+ temp = m->basicblocks;
+
+ while (temp->next)
+ temp = temp->next;
+
+ temp->next = new;
new->next = NULL;
/* find next block to copy, depending on last instruction of BB */
if (bptr->icount == 0) {
- copy_handler(lc, bptr->next, original_head, new_head);
+ copy_handler(m, ld, lc, bptr->next, original_head, new_head);
return;
- }
+ }
ip = bptr->iinstr + (bptr->icount - 1);
- switch (ip->opc) {
- case ICMD_RETURN:
- case ICMD_IRETURN:
- case ICMD_LRETURN:
- case ICMD_FRETURN:
- case ICMD_DRETURN:
- case ICMD_ARETURN:
- case ICMD_ATHROW:
- break;
+ switch (ip->opc) {
+ case ICMD_RETURN:
+ case ICMD_IRETURN:
+ case ICMD_LRETURN:
+ case ICMD_FRETURN:
+ case ICMD_DRETURN:
+ case ICMD_ARETURN:
+ case ICMD_ATHROW:
+ break;
- case ICMD_IFEQ:
- case ICMD_IFNE:
- case ICMD_IFLT:
- case ICMD_IFGE:
- case ICMD_IFGT:
- case ICMD_IFLE:
+ case ICMD_IFEQ:
+ case ICMD_IFNE:
+ case ICMD_IFLT:
+ case ICMD_IFGE:
+ case ICMD_IFGT:
+ case ICMD_IFLE:
- case ICMD_IF_LCMPEQ:
- case ICMD_IF_LCMPLT:
- case ICMD_IF_LCMPLE:
- case ICMD_IF_LCMPNE:
- case ICMD_IF_LCMPGT:
- case ICMD_IF_LCMPGE:
+ case ICMD_IF_LCMPEQ:
+ case ICMD_IF_LCMPLT:
+ case ICMD_IF_LCMPLE:
+ case ICMD_IF_LCMPNE:
+ case ICMD_IF_LCMPGT:
+ case ICMD_IF_LCMPGE:
- case ICMD_IF_LEQ:
- case ICMD_IF_LNE:
- case ICMD_IF_LLT:
- case ICMD_IF_LGE:
- case ICMD_IF_LGT:
- case ICMD_IF_LLE:
+ case ICMD_IF_LEQ:
+ case ICMD_IF_LNE:
+ case ICMD_IF_LLT:
+ case ICMD_IF_LGE:
+ case ICMD_IF_LGT:
+ case ICMD_IF_LLE:
- case ICMD_IFNULL:
- case ICMD_IFNONNULL:
+ case ICMD_IFNULL:
+ case ICMD_IFNONNULL:
- case ICMD_IF_ICMPEQ:
- case ICMD_IF_ICMPNE:
- case ICMD_IF_ICMPLT:
- case ICMD_IF_ICMPGE:
- case ICMD_IF_ICMPGT:
- case ICMD_IF_ICMPLE:
- case ICMD_IF_ACMPEQ:
- case ICMD_IF_ACMPNE:
- copy_handler(lc, bptr->next, original_head, new_head);
- /* fall through */
+ case ICMD_IF_ICMPEQ:
+ case ICMD_IF_ICMPNE:
+ case ICMD_IF_ICMPLT:
+ case ICMD_IF_ICMPGE:
+ case ICMD_IF_ICMPGT:
+ case ICMD_IF_ICMPLE:
+ case ICMD_IF_ACMPEQ:
+ case ICMD_IF_ACMPNE:
+ copy_handler(m, ld, lc, bptr->next, original_head, new_head);
+ /* fall through */
- case ICMD_GOTO:
+ case ICMD_GOTO:
- /* redirect jump from original_head to new_head */
- if ((basicblock *) ip->target == original_head)
- ip->target = (void *) new_head;
+ /* redirect jump from original_head to new_head */
+ if ((basicblock *) ip->target == original_head)
+ ip->target = (void *) new_head;
- copy_handler(lc, (basicblock *) (ip->target), original_head, new_head);
+ copy_handler(m, ld, lc, (basicblock *) (ip->target), original_head, new_head);
- break;
+ break;
- case ICMD_TABLESWITCH:
- s4ptr = ip->val.a;
- tptr = (void **) ip->target;
-
- /* default branch */
- if (((basicblock *) *tptr) == original_head)
- tptr[0] = (void *) new_head;
+ case ICMD_TABLESWITCH:
+ s4ptr = ip->val.a;
+ tptr = (void **) ip->target;
- copy_handler(lc, (basicblock *) *tptr, original_head, new_head);
+ /* default branch */
+ if (((basicblock *) *tptr) == original_head)
+ tptr[0] = (void *) new_head;
- s4ptr++;
- low = *s4ptr;
- s4ptr++;
- high = *s4ptr;
+ copy_handler(m, ld, lc, (basicblock *) *tptr, original_head, new_head);
- count = (high-low+1);
+ s4ptr++;
+ low = *s4ptr;
+ s4ptr++;
+ high = *s4ptr;
- while (--count >= 0) {
- tptr++;
- /* redirect jump from original_head to new_head */
- if (((basicblock *) *tptr) == original_head)
- tptr[0] = (void *) new_head;
- copy_handler(lc, (basicblock *) *tptr, original_head, new_head);
- }
- break;
-
- case ICMD_LOOKUPSWITCH:
- s4ptr = ip->val.a;
- tptr = (void **) ip->target;
+ count = (high-low+1);
- /* default branch */
+ while (--count >= 0) {
+ tptr++;
+ /* redirect jump from original_head to new_head */
if (((basicblock *) *tptr) == original_head)
tptr[0] = (void *) new_head;
+ copy_handler(m, ld, lc, (basicblock *) *tptr, original_head, new_head);
+ }
+ break;
+
+ case ICMD_LOOKUPSWITCH:
+ s4ptr = ip->val.a;
+ tptr = (void **) ip->target;
- copy_handler(lc, (basicblock *) *tptr, original_head, new_head);
+ /* default branch */
+ if (((basicblock *) *tptr) == original_head)
+ tptr[0] = (void *) new_head;
- ++s4ptr;
- count = *s4ptr;
+ copy_handler(m, ld, lc, (basicblock *) *tptr, original_head, new_head);
- while (--count >= 0) {
- ++tptr;
- /* redirect jump from original_head to new_head */
- if (((basicblock *) *tptr) == original_head)
- tptr[0] = (void *) new_head;
- copy_handler(lc, (basicblock *) *tptr, original_head, new_head);
- }
- break;
+ ++s4ptr;
+ count = *s4ptr;
+
+ while (--count >= 0) {
+ ++tptr;
+ /* redirect jump from original_head to new_head */
+ if (((basicblock *) *tptr) == original_head)
+ tptr[0] = (void *) new_head;
+ copy_handler(m, ld, lc, (basicblock *) *tptr, original_head, new_head);
+ }
+ break;
- case ICMD_JSR:
- c_last_target = bptr;
- copy_handler(lc, (basicblock *) (ip->target), original_head, new_head);
- break;
+ case ICMD_JSR:
+ ld->c_last_target = bptr;
+ copy_handler(m, ld, lc, (basicblock *) (ip->target), original_head, new_head);
+ break;
- case ICMD_RET:
- copy_handler(lc, c_last_target->next, original_head, new_head);
- break;
+ case ICMD_RET:
+ copy_handler(m, ld, lc, ld->c_last_target->next, original_head, new_head);
+ break;
- default:
- copy_handler(lc, bptr->next, original_head, new_head);
- break;
- }
-
+ default:
+ copy_handler(m, ld, lc, bptr->next, original_head, new_head);
+ break;
+ }
}
have to be duplicated as well. The following function together with the
two helper functions copy_handler and patch_handler perform this task.
*/
-void update_internal_exceptions(struct LoopContainer *lc, basicblock *original_head, basicblock *new_head)
+
+void update_internal_exceptions(methodinfo *m, codegendata *cd, loopdata *ld, struct LoopContainer *lc, basicblock *original_head, basicblock *new_head)
{
- xtable *ex, *new;
+ exceptiontable *ex, *new;
struct LoopContainer *l;
/* Bottom of tree reached -> return */
/* Call update_internal for all nested (=child) loops */
l = lc->tree_down;
while (l != NULL) {
- update_internal_exceptions(l, original_head, new_head);
+ update_internal_exceptions(m, cd, ld, l, original_head, new_head);
l = l->tree_right;
}
while (ex != NULL) {
/* Copy the exception and patch the jumps */
- copy_handler(lc, ex->handler, original_head, new_head);
+ copy_handler(m, ld, lc, ex->handler, original_head, new_head);
patch_handler(lc, ex->handler, original_head, new_head);
/* Insert a new exception into the global exception table */
- new = DMNEW(xtable, 1);
- memcpy(new, ex, sizeof(xtable));
+ new = DNEW(exceptiontable);
+ memcpy(new, ex, sizeof(exceptiontable));
/* Increase number of exceptions */
- ++exceptiontablelength;
+ ++jd->exceptiontablelength;
ex->next = new;
ex->down = new;
}
+
/* If a loop is duplicated, all exceptions that contain this loop have to be
extended to the copied nodes as well. The following function checks for
all exceptions of all parent loops, whether they contain the loop pointed to
by lc. If so, the exceptions are extended to contain all newly created nodes.
*/
-void update_external_exceptions(struct LoopContainer *lc, int loop_head)
+
+void update_external_exceptions(methodinfo *m, codegendata *cd, loopdata *ld, struct LoopContainer *lc, int loop_head)
{
- xtable *ex, *new;
+ exceptiontable *ex, *new;
/* Top of tree reached -> return */
if (lc == NULL)
/* It is possible that the loop contains exceptions that do not protect */
/* the loop just duplicated. It must be checked, if this is the case */
- if ((loop_head >= block_index[ex->startpc]) && (loop_head < block_index[ex->endpc])) {
+ if ((loop_head >= m->basicblockindex[ex->startpc]) && (loop_head < m->basicblockindex[ex->endpc])) {
/* loop is really inside exception, so create new exception entry */
/* in global exception list */
- new = DMNEW(xtable, 1);
- memcpy(new, ex, sizeof(xtable));
+ new = DNEW(exceptiontable);
+ memcpy(new, ex, sizeof(exceptiontable));
/* Increase number of exceptions */
- ++exceptiontablelength;
+ ++jd->exceptiontablelength;
ex->next = new;
ex->down = new;
/* Set new start and end point of this exception */
- new->start = c_first_block_copied;
- new->end = c_last_block_copied;
+ new->start = ld->c_first_block_copied;
+ new->end = ld->c_last_block_copied;
ex = new->next;
}
}
/* Call update_external for parent node */
- update_external_exceptions(lc->parent, loop_head);
+ update_external_exceptions(m, cd, ld, lc->parent, loop_head);
}
-
/* This function is needed to insert the static checks, stored in c_constraints
into the intermediate code.
*/
-void create_static_checks(struct LoopContainer *lc)
+
+void create_static_checks(methodinfo *m, codegendata *cd, loopdata *ld, struct LoopContainer *lc)
{
int i, stackdepth, cnt;
struct Constraint *tc1;
/* tos and newstack are needed by the macros, that insert instructions into */
/* the new loop head */
stackptr newstack, tos;
- xtable *ex;
+ exceptiontable *ex;
+
+ /* prevent some compiler warnings */
-#ifdef STATISTICS
- /* show_loop_statistics(); */
+ bptr = NULL;
+
+#ifdef ENABLE_STATISTICS
+ /* show_loop_statistics(l); */
#endif
- loop_head = &block[c_current_head];
- c_first_block_copied = c_last_block_copied = NULL;
+ loop_head = &m->basicblocks[ld->c_current_head];
+ ld->c_first_block_copied = ld->c_last_block_copied = NULL;
/* the loop nodes are copied */
le = lc->nodes;
{
bptr = DMNEW(basicblock, 1);
memcpy(bptr, le->block, sizeof(basicblock));
- bptr->debug_nr = c_debug_nr++;
+ bptr->nr = -1;
/* determine beginning of copied loop to extend exception handler, that */
/* protect this loop */
- if (c_first_block_copied == NULL)
- c_first_block_copied = bptr;
+ if (ld->c_first_block_copied == NULL)
+ ld->c_first_block_copied = bptr;
/* copy instructions and add one more slot for possible GOTO */
bptr->iinstr = DMNEW(instruction, bptr->icount + 1);
le->block->copied_to = bptr;
/* add block to global list of BBs */
- last_block->next = bptr;
- last_block = bptr;
+ temp = m->basicblocks;
+
+ while (temp->next)
+ temp = temp->next;
+
+ temp->next = bptr;
bptr->next = NULL;
- node_into_parent_loops(lc->parent, bptr);
+ node_into_parent_loops(ld, lc->parent, bptr);
le = le->next;
}
- c_last_block_copied = bptr;
+ ld->c_last_block_copied = bptr;
/* create an additional basicblock for dynamic checks */
original_start = bptr = DMNEW(basicblock, 1);
/* copy current loop header to new basic block */
memcpy(bptr, loop_head, sizeof(basicblock));
- bptr->debug_nr = c_debug_nr++;
+ bptr->nr = -1;
/* insert the new basic block and move header before first loop node */
le = lc->nodes;
}
- temp = block;
+ temp = m->basicblocks;
/* if first loop block is first BB of global list, insert loop_head at */
/* beginning of global BB list */
if (temp == le->block) {
- if (c_newstart == NULL) {
- c_needs_redirection = true;
- c_newstart = loop_head;
- loop_head->next = block;
+ if (ld->c_newstart == NULL) {
+ ld->c_needs_redirection = true;
+ ld->c_newstart = loop_head;
+ loop_head->next = m->basicblocks;
}
else {
- loop_head->next = c_newstart;
- c_newstart = loop_head;
+ loop_head->next = ld->c_newstart;
+ ld->c_newstart = loop_head;
}
}
else {
}
/* adjust exceptions */
- ex = extable;
+ ex = jd->exceptiontable;
while (ex != NULL) {
/* if an exception covers whole loop and starts at first loop node, it */
/* has to be extended to cover the new first node as well */
if (ex->start == le->block) {
- if ((lc->loop_head >= block_index[ex->startpc]) && (lc->loop_head < block_index[ex->endpc]))
+ if ((lc->loop_head >= m->basicblockindex[ex->startpc]) && (lc->loop_head < m->basicblockindex[ex->endpc]))
ex->start = loop_head;
}
/* insert new header node into nodelists of all enclosing loops */
- header_into_parent_loops(lc, loop_head, original_start, le->block);
+ header_into_parent_loops(ld, lc, loop_head, original_start, le->block);
/* prepare instruction array to insert checks */
- inst = loop_head->iinstr = DMNEW(instruction, c_needed_instr + 2);
- loop_head->icount = c_needed_instr + 1;
+ inst = loop_head->iinstr = DMNEW(instruction, ld->c_needed_instr + 2);
+ loop_head->icount = ld->c_needed_instr + 1;
/* init instruction array */
- for (cnt=0; cnt<c_needed_instr + 1; ++cnt) {
+ for (cnt=0; cnt<ld->c_needed_instr + 1; ++cnt) {
inst[0].opc = ICMD_NOP;
inst[0].dst = NULL;
}
stackdepth = loop_head->indepth;
/* step through all inserted checks and create instructions for them */
- for (i=0; i<maxlocals+1; ++i)
+ for (i=0; i<jd->maxlocals+1; ++i)
{
- tc1 = c_constraints[i];
+ tc1 = ld->c_constraints[i];
while (tc1 != NULL)
{
switch (tc1->type)
tc1 = tc1->next;
}
- c_constraints[i] = NULL;
+ ld->c_constraints[i] = NULL;
}
/* if all tests succeed, jump to optimized loop header */
/* if exceptions have to be correct due to loop duplication these two */
/* functions perform this task. */
- update_internal_exceptions(lc, loop_head, original_start);
- update_external_exceptions(lc->parent, lc->loop_head);
+ update_internal_exceptions(m, cd, ld, lc, loop_head, original_start);
+ update_external_exceptions(m, cd, ld, lc->parent, lc->loop_head);
}
represented by its lower bound being higher than the upper bound. The result
of the union is stored in c1.
*/
-struct Changes ** constraints_unrestricted_merge(struct Changes **c1, struct Changes **c2)
+struct Changes ** constraints_unrestricted_merge(codegendata *cd, struct Changes **c1, struct Changes **c2)
{
int i, changed;
printf("C_ERROR: debugging error 0x03\n");
changed = 0;
- for (i=0; i<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;
represented by its lower bound being higher than the upper bound. The result
of the union is stored in c1.
*/
-struct Changes ** constraints_merge(struct Changes **c1, struct Changes **c2)
+struct Changes ** constraints_merge(codegendata *cd, struct Changes **c1, struct Changes **c2)
{
int i, changed;
changed = 0;
- for (i=0; i<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)
/* This function simply copies an array of changes
*/
-struct Changes** constraints_clone(struct Changes **c)
+struct Changes** constraints_clone(codegendata *cd, struct Changes **c)
{
int i;
struct Changes **t;
- if ((t = (struct Changes **) malloc(maxlocals * sizeof(struct Changes *))) == NULL)
+ if ((t = (struct Changes **) malloc(jd->maxlocals * sizeof(struct Changes *))) == NULL)
c_mem_error();
- for (i=0; i<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 {
correctly reflect its bounds the time, it was pushed onto the stack. This
function corrects the situation.
*/
-struct Changes* backtrack_var(int node, int from, int to, int varRef, struct Changes *changes)
+struct Changes* backtrack_var(methodinfo *m, int node, int from, int to, int varRef, struct Changes *changes)
{
struct Changes *tmp;
basicblock bp;
if (tmp->upper_bound < tmp->lower_bound)
return tmp; /* if it is unrestricted no backtracking can happen */
- bp = block[node];
+ bp = m->basicblocks[node];
ip = bp.iinstr + to;
for (; from < to; --to, --ip) { /* scan instructions backwards */
break;
/* it is our variable, so trace its origin */
- t = tracing(&block[node],to, 0);
+ t = tracing(&m->basicblocks[node],to, 0);
switch (t->type) {
case TRACE_IVAR:
return tmp;
}
+
/* This function performs the main task of bound check removal. It removes
all bound-checks in node. change is a pointer to an array of struct Changes
that reflect for all local variables, how their values have changed from
the start of the loop. The special flag is needed to deal with the header
node.
*/
-void remove_boundchecks(int node, int from, struct Changes **change, int special)
+
+void remove_boundchecks(methodinfo *m, codegendata *cd, loopdata *ld, int node, int from, struct Changes **change, int special)
{
basicblock bp;
instruction *ip;
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 */
degrade_checks = 0;
- if (c_current_loop[node] > 0) { /* this node is part of the loop */
- if (c_current_loop[node] > 1) { /* it is not the header node */
+ if (ld->c_current_loop[node] > 0) { /* this node is part of the loop */
+ if (ld->c_current_loop[node] > 1) { /* it is not the header node */
/* get variable changes, already recorded for this node */
- t1 = c_dTable[node]->changes;
+ t1 = ld->c_dTable[node]->changes;
if (t1 != NULL) { /* it is not the first visit */
- if ((c_nestedLoops[node] != c_current_head) && (c_nestedLoops[node] == c_nestedLoops[from])) {
+ if ((ld->c_nestedLoops[node] != ld->c_current_head) && (ld->c_nestedLoops[node] == ld->c_nestedLoops[from])) {
/* we are looping in a nested loop, so made optimizations */
/* need to be reconsidered */
degrade_checks = 1;
- if (constraints_unrestricted_merge(t1, change) == NULL)
+ if (constraints_unrestricted_merge(cd, t1, change) == NULL)
return; /* no changes since previous visit */
/* if there have been changes, they are updated by */
/* constraints_unrestricted_merge in t1 */
}
else {
- if (constraints_merge(t1, change) == NULL)
+ if (constraints_merge(cd, t1, change) == NULL)
return; /* no changes since previous visit */
/* if there have been changes, they are updated by */
/* constraints_merge in t1 */
}
else { /* first visit */
/* printf("first visit - constraints cloned\n"); */
- c_dTable[node]->changes = constraints_clone(change);
+ ld->c_dTable[node]->changes = constraints_clone(cd, change);
}
/* tmp now holds a copy of the updated variable changes */
- tmp = constraints_clone(c_dTable[node]->changes);
+ tmp = constraints_clone(cd, ld->c_dTable[node]->changes);
}
else if (special) { /* header and need special traetment */
/* printf("special treatment called\n"); */
/* tmp now holds a copy of the current new variable changes */
- tmp = constraints_clone(change);
+ tmp = constraints_clone(cd, change);
}
else
return;
- bp = block[node]; /* scan all instructions */
+ bp = m->basicblocks[node]; /* scan all instructions */
count = bp.icount;
ip = bp.iinstr;
ignore = 0;
show_trace(t_index);
*/
-#ifdef STATISTICS
+#ifdef ENABLE_STATISTICS
if (ip->op1 == OPT_UNCHECKED) { /* found new access */
- c_stat_array_accesses++;
+ ld->c_stat_array_accesses++;
ip->op1 = OPT_NONE;
- c_stat_no_opt++;
+ ld->c_stat_no_opt++;
}
#endif
/* can only optimize known arrays that do not change */
- if ((t_array->type != TRACE_AVAR) || (c_var_modified[t_array->var]))
+ if ((t_array->type != TRACE_AVAR) || (ld->c_var_modified[t_array->var]))
break;
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;
case OPT_NONE:
- c_stat_no_opt--;
+ ld->c_stat_no_opt--;
break;
case OPT_FULL:
- c_stat_full_opt--;
+ ld->c_stat_full_opt--;
break;
case OPT_UPPER:
- c_stat_upper_opt--;
+ ld->c_stat_upper_opt--;
break;
case OPT_LOWER:
- c_stat_lower_opt--;
+ ld->c_stat_lower_opt--;
break;
}
#endif
if (degrade_checks) /* replace existing optimization */
- ip->op1 = insert_static(t_array->var, t_index, NULL, special);
+ ip->op1 = insert_static(m, cd, ld, t_array->var, t_index, NULL, special);
else {
/* Check current optimization and try to improve it by */
/* inserting new checks */
switch (ip->op1) {
case OPT_UNCHECKED:
- ip->op1 = insert_static(t_array->var, t_index, NULL, special);
+ ip->op1 = insert_static(m, cd, ld, t_array->var, t_index, NULL, special);
break;
case OPT_NONE:
- ip->op1 = insert_static(t_array->var, t_index, NULL, special);
+ ip->op1 = insert_static(m, cd, ld, t_array->var, t_index, NULL, special);
break;
case OPT_UPPER:
- opt_level = insert_static(t_array->var, t_index, NULL, special);
+ opt_level = insert_static(m, cd, ld, t_array->var, t_index, NULL, special);
if ((opt_level == OPT_FULL) || (opt_level == OPT_LOWER))
ip->op1 = OPT_FULL;
break;
case OPT_LOWER:
- opt_level = insert_static(t_array->var, t_index, NULL, special);
+ opt_level = insert_static(m, cd, ld, t_array->var, t_index, NULL, special);
if ((opt_level == OPT_FULL) || (opt_level == OPT_UPPER))
ip->op1 = OPT_FULL;
break;
case OPT_FULL:
-#ifdef STATISTICS
- c_stat_full_opt++;
+#ifdef ENABLE_STATISTICS
+ ld->c_stat_full_opt++;
#endif
break;
}
/* of the array access and its push onto the stack, we have */
/* to set the changes back to the time, it is pushed onto */
/* the stack as an index variable. */
- t = backtrack_var(node, t_index->nr, i-1, t_index->var, tmp[t_index->var]);
-#ifdef STATISTICS
+ t = backtrack_var(m, node, t_index->nr, i-1, t_index->var, tmp[t_index->var]);
+#ifdef ENABLE_STATISTICS
switch (ip->op1) { /* take back old optimzation */
case OPT_UNCHECKED:
break;
case OPT_NONE:
- c_stat_no_opt--;
+ ld->c_stat_no_opt--;
break;
case OPT_FULL:
- c_stat_full_opt--;
+ ld->c_stat_full_opt--;
break;
case OPT_UPPER:
- c_stat_upper_opt--;
+ ld->c_stat_upper_opt--;
break;
case OPT_LOWER:
- c_stat_lower_opt--;
+ ld->c_stat_lower_opt--;
break;
}
#endif
if (degrade_checks)
- ip->op1 = insert_static(t_array->var, t_index, t, special);
+ ip->op1 = insert_static(m, cd, ld, t_array->var, t_index, t, special);
else {
/* Check current optimization and try to improve it by */
/* insert new check. t reflects var changes for index */
switch (ip->op1) {
case OPT_UNCHECKED:
- ip->op1 = insert_static(t_array->var, t_index, t, special);
+ ip->op1 = insert_static(m, cd, ld, t_array->var, t_index, t, special);
break;
case OPT_NONE:
- ip->op1 = insert_static(t_array->var, t_index, t, special);
+ ip->op1 = insert_static(m, cd, ld, t_array->var, t_index, t, special);
break;
case OPT_UPPER:
- opt_level = insert_static(t_array->var, t_index, t, special);
+ opt_level = insert_static(m, cd, ld, t_array->var, t_index, t, special);
if ((opt_level == OPT_FULL) || (opt_level == OPT_LOWER))
ip->op1 = OPT_FULL;
break;
case OPT_LOWER:
- opt_level = insert_static(t_array->var, t_index, t, special);
+ opt_level = insert_static(m, cd, ld, t_array->var, t_index, t, special);
if ((opt_level == OPT_FULL) || (opt_level == OPT_UPPER))
ip->op1 = OPT_FULL;
break;
case OPT_FULL:
-#ifdef STATISTICS
- c_stat_full_opt++;
+#ifdef ENABLE_STATISTICS
+ ld->c_stat_full_opt++;
#endif
break;
}
} /* for */
if (!special) { /* we are not interested in only the header */
- d = c_dTable[node];
+ d = ld->c_dTable[node];
while (d != NULL) { /* check all sucessors of current node */
- remove_boundchecks(d->value, node, tmp, special);
+ remove_boundchecks(m, cd, ld, d->value, node, tmp, special);
d = d->next;
}
}
} /* if */
}
+
/* This function calls the bound-check removal function for the header node
with a special flag. It is important to notice, that no dynamic
constraint hold in the header node (because the comparison is done at
block end).
*/
-void remove_header_boundchecks(int node, struct Changes **changes)
+
+void remove_header_boundchecks(methodinfo *m, codegendata *cd, loopdata *ld, int node, struct Changes **changes)
{
- remove_boundchecks(node, -1, changes, BOUNDCHECK_SPECIAL);
+ remove_boundchecks(m, cd, ld, node, -1, changes, BOUNDCHECK_SPECIAL);
}
+
/* Marks all basicblocks that are part of the loop
*/
+
void mark_loop_nodes(struct LoopContainer *lc)
{
struct LoopElement *le = lc->nodes;
}
}
+
/* Clears mark for all basicblocks that are part of the loop
*/
-void unmark_loop_nodes(struct LoopContainer *lc)
+void unmark_loop_nodes(LoopContainer *lc)
{
- struct LoopElement *le = lc->nodes;
+ LoopElement *le = lc->nodes;
while (le != NULL) {
le->block->lflags = 0;
le = le->next;
- }
+ }
}
identify array accesses suitable for optimization (bound check removal). The
intermediate code is then modified to reflect these optimizations.
*/
-void optimize_single_loop(struct LoopContainer *lc)
+void optimize_single_loop(methodinfo *m, codegendata *cd, loopdata *ld, LoopContainer *lc)
{
struct LoopElement *le;
struct depthElement *d;
int i, head, node;
struct Changes **changes;
- if ((changes = (struct Changes **) malloc(maxlocals * sizeof(struct Changes *))) == NULL)
+ if ((changes = (struct Changes **) malloc(jd->maxlocals * sizeof(struct Changes *))) == NULL)
c_mem_error();
- head = c_current_head = lc->loop_head;
- c_needed_instr = c_rs_needed_instr = 0;
+ 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<maxlocals; ++i)
- c_null_check[i] = 0;
+ for (i=0; i<jd->maxlocals; ++i)
+ ld->c_null_check[i] = 0;
/* don't optimize root node (it is the main procedure, not a loop) */
return;
/* setup variables with initial values */
- c_loopvars = NULL;
- for (i=0; i < block_count; ++i) {
- c_toVisit[i] = 0;
- c_current_loop[i] = -1;
- if ((d = c_dTable[i]) != NULL)
+ ld->c_loopvars = NULL;
+ for (i=0; i < m->basicblockcount; ++i) {
+ ld->c_toVisit[i] = 0;
+ ld->c_current_loop[i] = -1;
+ if ((d = ld->c_dTable[i]) != NULL)
d->changes = NULL;
}
- for (i=0; i < maxlocals; ++i) {
- c_var_modified[i] = 0;
+ for (i=0; i < jd->maxlocals; ++i) {
+ ld->c_var_modified[i] = 0;
if (changes[i] != NULL) {
changes[i] = NULL;
}
}
- for (i=0; i < (maxlocals+1); ++i) {
- if (c_constraints[i] != NULL) {
- c_constraints[i] = NULL;
+ for (i=0; i < (jd->maxlocals+1); ++i) {
+ if (ld->c_constraints[i] != NULL) {
+ ld->c_constraints[i] = NULL;
}
}
node = le->node;
if (node == head)
- c_current_loop[node] = 1; /* the header node gets 1 */
- else if (c_nestedLoops[node] == head)
- c_current_loop[node] = 2; /* top level nodes get 2 */
+ ld->c_current_loop[node] = 1; /* the header node gets 1 */
+ else if (ld->c_nestedLoops[node] == head)
+ ld->c_current_loop[node] = 2; /* top level nodes get 2 */
else
- c_current_loop[node] = 3; /* nodes, part of nested loop get 3 */
+ ld->c_current_loop[node] = 3; /* nodes, part of nested loop get 3 */
- c_toVisit[node] = 1;
+ ld->c_toVisit[node] = 1;
le = le->next;
}
fflush(stdout);
#endif
- if (analyze_for_array_access(head) > 0) {/* loop contains array access */
+ if (analyze_for_array_access(m, ld, head) > 0) {/* loop contains array access */
#ifdef LOOP_DEBUG
struct LoopVar *lv;
printf("analyze for array access finished and found\n");
fflush(stdout);
- lv = c_loopvars;
+ lv = ld->c_loopvars;
while (lv != NULL) {
if (lv->modified)
printf("Var --> %d\n", lv->value);
/* for performance reasons the list of all interesting loop vars is */
/* scaned and for all modified vars a flag in c_var_modified is set */
- scan_global_list();
+ scan_global_list(ld);
#ifdef LOOP_DEBUG
printf("global list scanned\n");
/* if the loop header contains or-conditions or an index variable */
/* is modified in the catch-block within the loop, a conservative */
/* approach is taken and optimizations are cancelled */
- if (analyze_or_exceptions(head, lc) > 0) {
+ if (analyze_or_exceptions(m, cd, ld, head, lc) > 0) {
#ifdef LOOP_DEBUG
printf("Analyzed for or/exception - no problems \n");
fflush(stdout);
#endif
- init_constraints(head); /* analyze dynamic bounds in header */
+ init_constraints(m, ld, head); /* analyze dynamic bounds in header */
#ifdef LOOP_DEBUG
show_right_side();
#endif
- if (c_rightside == NULL)
+ if (ld->c_rightside == NULL)
return;
/* single pass bound check removal - for all successors, do */
- remove_header_boundchecks(head, changes);
+ remove_header_boundchecks(m, cd, ld, head, changes);
- d = c_dTable[head];
+ d = ld->c_dTable[head];
while (d != NULL) {
- remove_boundchecks(d->value, -1, changes, BOUNDCHECK_REGULAR);
+ remove_boundchecks(m, cd, ld, d->value, -1, changes, BOUNDCHECK_REGULAR);
d = d->next;
}
fflush(stdout);
#endif
- create_static_checks(lc); /* create checks */
+ create_static_checks(m, cd, ld, lc); /* create checks */
#ifdef LOOP_DEBUG
printf("END: create static checks\n");
/* else
printf("No array accesses found\n"); */
-#ifdef STATISTICS
- c_stat_num_loops++; /* increase number of loops */
-
- c_stat_sum_accesses += c_stat_array_accesses;
- c_stat_sum_full += c_stat_full_opt;
- c_stat_sum_no += c_stat_no_opt;
- c_stat_sum_lower += c_stat_lower_opt;
- c_stat_sum_upper += c_stat_upper_opt;
- c_stat_sum_or += c_stat_or;
- c_stat_sum_exception += c_stat_exception;
-
- c_stat_array_accesses = 0;
- c_stat_full_opt = 0;
- c_stat_no_opt = 0;
- c_stat_lower_opt = 0;
- c_stat_upper_opt = 0;
- c_stat_or = c_stat_exception = 0;
+#ifdef ENABLE_STATISTICS
+ ld->c_stat_num_loops++; /* increase number of loops */
+
+ ld->c_stat_sum_accesses += ld->c_stat_array_accesses;
+ ld->c_stat_sum_full += ld->c_stat_full_opt;
+ ld->c_stat_sum_no += ld->c_stat_no_opt;
+ ld->c_stat_sum_lower += ld->c_stat_lower_opt;
+ ld->c_stat_sum_upper += ld->c_stat_upper_opt;
+ ld->c_stat_sum_or += ld->c_stat_or;
+ ld->c_stat_sum_exception += ld->c_stat_exception;
+
+ ld->c_stat_array_accesses = 0;
+ ld->c_stat_full_opt = 0;
+ ld->c_stat_no_opt = 0;
+ ld->c_stat_lower_opt = 0;
+ ld->c_stat_upper_opt = 0;
+ ld->c_stat_or = ld->c_stat_exception = 0;
#endif
}
-/* This function preforms necessary setup work, before the recursive function
- optimize_single loop can be called.
-*/
-void optimize_loops()
+
+/* optimize_loops **************************************************************
+
+ This function preforms necessary setup work, before the recursive
+ function optimize_single loop can be called.
+
+*******************************************************************************/
+
+void optimize_loops(jitdata *jd)
{
- struct LoopContainer *lc = 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 */
fflush(stdout);
#endif
- analyze_double_headers();
+ analyze_double_headers(ld);
/* create array with loop nesting levels - nested loops cause problems, */
/* especially, when they modify index variables used in surrounding loops */
fflush(stdout);
#endif
- analyze_nested();
+ analyze_nested(m,cd, ld);
#ifdef LOOP_DEBUG
printf("analyze nested done\n");
#endif
/* create array with entries for current loop */
- c_current_loop = DMNEW(int, block_count);
- c_toVisit = DMNEW(int, block_count);
- c_var_modified = DMNEW(int, maxlocals);
- c_null_check = DMNEW(int, maxlocals);
+ ld->c_current_loop = DMNEW(int, m->basicblockcount);
+ ld->c_toVisit = DMNEW(int, m->basicblockcount);
+ ld->c_var_modified = DMNEW(int, jd->maxlocals);
+ ld->c_null_check = DMNEW(int, jd->maxlocals);
- if ((c_constraints = (struct Constraint **) malloc((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
- c_stat_num_loops = 0; /* set statistic vars to zero */
- c_stat_array_accesses = c_stat_sum_accesses = 0;
- c_stat_full_opt = c_stat_sum_full = 0;
- c_stat_no_opt = c_stat_sum_no = 0;
- c_stat_lower_opt = c_stat_sum_lower = 0;
- c_stat_upper_opt = c_stat_sum_upper = 0;
- c_stat_or = c_stat_sum_or = 0;
- c_stat_exception = c_stat_sum_exception = 0;
+#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;
+ ld->c_stat_no_opt = ld->c_stat_sum_no = 0;
+ ld->c_stat_lower_opt = ld->c_stat_sum_lower = 0;
+ ld->c_stat_upper_opt = ld->c_stat_sum_upper = 0;
+ ld->c_stat_or = ld->c_stat_sum_or = 0;
+ ld->c_stat_exception = ld->c_stat_sum_exception = 0;
#endif
/* init vars needed by all loops */
- c_needs_redirection = false;
- c_newstart = NULL;
- c_old_xtablelength = exceptiontablelength;
+ ld->c_needs_redirection = false;
+ ld->c_newstart = NULL;
+ ld->c_old_xtablelength = jd->exceptiontablelength;
/* loops have been topologically sorted */
- lc = c_allLoops;
+ lc = ld->c_allLoops;
while (lc != NULL) {
- optimize_single_loop(lc);
+ optimize_single_loop(m, cd, ld, lc);
#ifdef LOOP_DEBUG
printf(" *** Optimized loop *** \n");
#endif
/* if global BB list start is modified, set block to new start */
- if (c_needs_redirection == true)
- block = c_newstart;
+ if (ld->c_needs_redirection == true)
+ m->basicblocks = ld->c_newstart;
}