+/* analyze.c *******************************************************************
+
+ Copyright (c) 1997 A. Krall, R. Grafl, M. Gschwind, M. Probst
+
+ See file COPYRIGHT for information on usage and disclaimer of warranties.
+
+ 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().
+
+ Authors: Christopher Kruegel EMAIL: cacao@complang.tuwien.ac.at
+
+ Last Change: 1998/17/02
+
+*******************************************************************************/
+
+#ifdef LOOP_DEBUG
+
+/* Test functions -> will be removed in final release
+*/
+void show_trace(struct Trace *trace)
+{
+ if (trace != NULL) {
+ switch (trace->type) {
+ case TRACE_IVAR:
+ printf("int-var");
+ printf("\nNr.:\t%d", trace->var);
+ printf("\nValue:\t%d", trace->constant);
+ break;
+
+ case TRACE_AVAR:
+ printf("object-var");
+ printf("\nNr.:\t%d", trace->var);
+ break;
+
+ case TRACE_ALENGTH:
+ printf("array-length");
+ printf("\nNr.:\t%d", trace->var);
+ printf("\nValue:\t%d", trace->constant);
+ break;
+
+ case TRACE_ICONST:
+ printf("int-const");
+ printf("\nValue:\t%d", trace->constant);
+ break;
+
+ case TRACE_UNKNOWN:
+ printf("unknown");
+ break;
+ }
+ }
+ else
+ printf("Trace is null");
+
+ printf("\n");
+}
+void show_change(struct Changes *c)
+{
+ printf("*** Changes ***\n");
+ if (c != NULL)
+ printf("Lower/Upper Bound:\t%d/%d\n", c->lower_bound, c->upper_bound);
+ else
+ printf("Unrestricted\n");
+}
+show_varinfo(struct LoopVar *lv)
+{
+ printf(" *** Loop Info ***\n");
+ printf("Value:\t%d\n", lv->value);
+ printf("Static:\t\t%d/%d\n", lv->static_l, lv->static_u);
+ printf("D-Valid:\t%d/%d\n", lv->dynamic_l_v, lv->dynamic_u_v);
+ printf("Dynamic\t\t%d/%d\n", lv->dynamic_l, lv->dynamic_u);
+}
+void show_right_side()
+{
+ int i;
+ printf("\n *** Head *** \nType:\t");
+ show_trace(c_rightside);
+
+ printf("\n *** Nested Loops: ***\n");
+ for (i=0; i<block_count; ++i)
+ printf("%d\t", c_nestedLoops[i]);
+ printf("\n");
+
+ printf("\n *** Hierarchie: ***\n");
+ for (i=0; i<block_count; ++i)
+ printf("%d\t", c_hierarchie[i]);
+ printf("\n");
+
+
+ printf("\n *** Current Loop ***\n");
+ for (i=0; i<block_count; ++i)
+ printf("%d\t", c_current_loop[i]);
+ printf("\n");
+}
+void resultPass3()
+{
+ int i;
+ struct LoopContainer *lc = c_allLoops;
+
+ printf("\n\n****** PASS 3 ******\n\n");
+
+ while (lc != NULL) {
+ printf("Loop Analysis:\n");
+ printf("Optimize:\t%d\n", lc->toOpt);
+ printf("Modified Vars: ");
+ /*
+ for (i=0; i<lc->num_vars; ++i)
+ printf("%d ", lc->vars[i]);
+ printf("\n\n");
+ */
+ lc = lc->next;
+ }
+
+ printf("\nNested Loops:\n");
+ for (i=0; i<block_count; ++i)
+ printf("%d ", c_nestedLoops[i]);
+ printf("\n");
+ for (i=0; i<block_count; ++i)
+ printf("%d ", c_hierarchie[i]);
+ printf("\n");
+ fflush(stdout);
+}
+void show_tree(struct LoopContainer *lc, int tabs)
+{
+ int cnt;
+
+ while (lc != NULL) {
+ for (cnt = 0; cnt < tabs; ++cnt)
+ printf(" ");
+ printf("%d\n", lc->loop_head);
+
+ show_tree(lc->tree_down, tabs+1);
+
+ lc = lc->tree_right;
+ }
+}
+
+#endif
+
+#ifdef STATISTICS
+
+void show_loop_statistics()
+{
+ printf("\n\n****** LOOP STATISTICS ****** \n\n");
+ if (c_stat_or)
+ printf("Optimization cancelled by or\n");
+ else if (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);
+ }
+ }
+}
+void show_procedure_statistics()
+{
+ 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("Opt. cancelled by or:\t\t%d\n", c_stat_sum_or);
+ printf("Opt. cancelled by exception:\t%d\n", c_stat_sum_exception);
+}
+
+#endif
+
+
+/* This function is used to merge two loops with the same header together.
+ A simple merge sort of the lists nodes of both loops is performed.
+*/
+void analyze_merge(struct LoopContainer *l1, struct LoopContainer *l2)
+{
+ struct LoopElement *start, *last, *le1, *le2;
+ /* start and last are pointers to the newly built list, le1 and le2 step */
+ /* step through the lists, that have to be merged. */
+
+ le1 = l1->nodes;
+ le2 = l2->nodes;
+
+ /* start a simple merge sort of the nodes of both loops. These lists are */
+ /* already sorted, so merging is easy. */
+ if (le1->node < le2->node) {
+ start = last = le1;
+ le1 = le1->next;
+ }
+ else if (le1->node == le2->node) {
+ start = last = le1;
+ le1 = le1->next;
+ le2 = le2->next;
+ }
+ else {
+ start = last = le2;
+ le2 = le2->next;
+ }
+
+ /* while the first loop != NULL, depending of the first element of second */
+ /* loop, add new node to result list */
+ while (le1 != NULL) {
+
+ if (le2 == NULL) {
+ last->next = le1;
+ break;
+ }
+ if (le1->node < le2->node) {
+ last->next = le1;
+ le1 = le1->next;
+ }
+ else if (le1->node == le2->node) {
+ last->next = le1;
+ le1 = le1->next;
+ le2 = le2->next;
+ last = last->next;
+ }
+ else {
+ last->next = le2;
+ le2 = le2->next;
+ last = last->next;
+ }
+ }
+
+ last->next = le2;
+}
+
+
+/* This function is used to merge loops with the same header node to a single
+ one. O(n^2) of number of loops. This merginig is necessary, because the loop
+ 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()
+{
+ int toCheck;
+ struct LoopContainer *t1, *t2, *t3;
+
+ t1 = c_allLoops;
+
+ while (t1 != NULL) { /* for all loops do */
+ toCheck = t1->loop_head; /* get header node */
+ t2 = t1->next;
+
+ while (t2 != NULL) { /* compare it to headers of rest */
+ if (t2->loop_head == toCheck) {
+
+ /* found overlapping loops -> merge them together */
+ /* printf("C_INFO: found overlapping loops - merging"); */
+ analyze_merge(t1, t2);
+
+ /* remove second loop from the list of all loops */
+ t3 = t1;
+ while (t3->next != t2)
+ t3 = t3->next;
+ t3->next = t2->next;
+ }
+ t2 = t2->next;
+ }
+
+ t1 = t1->next;
+ }
+}
+
+
+/* After the hierarchie of loops has been built, we have to insert the exceptions
+ into this tree. The exception ex is inserted into the subtree pointed to by
+ LoopContainer lc.
+*/
+void insert_exception(struct LoopContainer *lc, xtable *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); */
+#endif
+
+ /* if child node is reached immediately insert the exception into the tree */
+ if (lc->tree_down == NULL) {
+ ex->next = lc->exceptions;
+ lc->exceptions = ex;
+ }
+ else {
+ /* if we are inside the tree, there are two possibilities: */
+ /* 1. the exception is inside a nested loop or */
+ /* 2. in the loop body of the current loop */
+
+ /* check all children (= nested loops) */
+ temp = lc->tree_down;
+
+ while (temp != NULL) {
+
+ le = temp->nodes;
+ while (le != NULL) {
+
+#ifdef LOOP_DEBUG
+ printf("%d.%d\n", le->node, block_index[ex->startpc]);
+#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])
+ break;
+ le = le->next;
+ }
+
+ /* Exception is part of a nested loop (Case 1) -> insert it there */
+ if (le != NULL) {
+ insert_exception(temp, ex);
+ return;
+ }
+ else if ((temp->loop_head >= block_index[ex->startpc]) && (temp->loop_head < block_index[ex->endpc])) {
+
+ /* optimization: if nested loop is part of the exception, the */
+ /* exception cannot be part of a differnet nested loop. */
+ ex->next = lc->exceptions;
+ lc->exceptions = ex;
+ return;
+ }
+ else
+ temp = temp->tree_right;
+ }
+
+ /* Exception is not contained in any nested loop (Case 2) */
+ if (temp == NULL) {
+ ex->next = lc->exceptions;
+ lc->exceptions = ex;
+ }
+ }
+}
+
+
+/* This function builds a loop hierarchie. The header node of the innermost loop,
+ each basic block belongs to, is stored in the array c_nestedLoops. The array
+ c_hierarchie stores the relationship between differnt loops in as follows:
+ Each loop, that is a nested loop, stores its direct surrounding loop as a
+ parent. Top level loops have no parents.
+*/
+void analyze_nested()
+{
+ /* i/count/tmp are counters */
+ /* toOverwrite is used while loop hierarchie is built (see below) */
+ int i, count, header, toOverwrite, tmp, len;
+
+ /* first/last are used during topological sort to build ordered loop list */
+ struct LoopContainer *first, *last, *start, *t, *temp;
+
+ /* Used to step through all nodes of a loop. */
+ 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;
+ }
+
+ /* if there are no optimizable loops -> return */
+ if (c_allLoops == NULL)
+ return;
+
+ temp = 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];
+
+ 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];
+
+ /* if node is part of parent loop -> overwrite it with nested */
+ if (tmp == toOverwrite)
+ c_nestedLoops[le->node] = header;
+ else {
+ c_hierarchie[tmp] = header;
+#ifdef LOOP_DEBUG
+ /* printf("set head of %d to %d", tmp, header); */
+#endif
+ }
+
+ le = le->next;
+ }
+
+ temp = temp->next;
+ }
+
+ /* init root of hierarchie tree */
+ root = DMNEW(struct LoopContainer, 1);
+ LoopContainerInit(root, -1);
+
+ /* obtain parent pointer and build hierarchie tree */
+ start = c_allLoops;
+ while (start != NULL) {
+
+ /* look for parent of loop pointed at by start */
+ first = 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]) {
+#ifdef LOOP_DEBUG
+ /* printf("set parent to pointer\n"); */
+#endif
+
+ start->parent = first;
+ start->tree_right = first->tree_down;
+ first->tree_down = start;
+
+ break;
+ }
+ first = first->next;
+ }
+
+ /* no parent loop found, set parent to root */
+ if (first == NULL) {
+#ifdef LOOP_DEBUG
+ /* printf("set parent to root\n"); */
+#endif
+
+ start->parent = root;
+ start->tree_right = root->tree_down;
+ root->tree_down = start;
+ }
+ /* if a parent exists, increase this nodes indegree */
+ else
+ start->parent->in_degree += 1;
+
+ start = start->next;
+ }
+
+ /* insert exceptions into tree */
+#ifdef LOOP_DEBUG
+ printf("--- Showing tree ---\n");
+ show_tree(root, 0);
+ printf(" --- End ---\n");
+#endif
+ for (len = 0; len < exceptiontablelength; ++len)
+ insert_exception(root, extable + len);
+
+
+ /* determine sequence of loops for optimization by topological sorting them */
+
+ /* init queue */
+ start = NULL;
+ temp = c_allLoops;
+ while (temp != NULL) {
+
+ /* a loops with indegree == 0 are pushed onto the stack */
+ if (temp->in_degree == 0) {
+ t = temp->next;
+ temp->next = start;
+ start = temp;
+ }
+ else
+ t = temp->next;
+
+ temp = t;
+ }
+
+ /* sort loops */
+ first = last = start;
+ start = start->next;
+
+ if (last == NULL) {
+ printf("C_ERROR: loops are looped\n");
+ exit(-1);
+ }
+
+ /* 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)) {
+ last->parent->next = start;
+ start = last->parent;
+ }
+ while (start != NULL) {
+
+ last->next = start;
+
+ start = start->next;
+ last = last->next;
+
+ if ((last->parent != root) && (--last->parent->in_degree == 0)) {
+ last->parent->next = start;
+ start = last->parent;
+ }
+ }
+
+ last->next = NULL;
+ c_allLoops = first;
+
+#ifdef LOOP_DEBUG
+ printf("*** Hierarchie Results \n");
+ while (first != NULL) {
+ printf("%d ", first->loop_head);
+ first = first->next;
+ }
+ printf("\n");
+ fflush(stdout);
+#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)
+{
+ struct LoopVar *lv;
+
+ /* printf("Added to vars %d %d %d\n", var, type, direction); */
+ lv = c_loopvars;
+ while (lv != NULL) { /* check if var has been previously added */
+ if (lv->value == var) {
+ if (type == ARRAY_INDEX)
+ lv->index = 1; /* var is used as index */
+ else if (type == VAR_MOD) {
+ lv->modified = 1; /* var is used in assignment */
+ switch (direction) { /* how was var modified ? */
+ case D_UP:
+ lv->static_u = 0; /* incremented, no static upper */
+ break; /* bound can be guaranteeed */
+ case D_DOWN:
+ lv->static_l = 0; /* decremented, no static lower */
+ break; /* bound can be guaranteeed */
+ case D_UNKNOWN:
+ lv->static_u = lv->static_l = 0;
+ break; /* no info at all */
+ default:
+ printf("C_ERROR: unknown direction\n");
+ break;
+ }
+ }
+ return;
+ }
+ lv = lv->next;
+ }
+
+ /* variable is not found in list -> add variable to list */
+ lv = DNEW(struct LoopVar);
+
+ lv->value = var;
+ if (type == ARRAY_INDEX) {
+ lv->index = 1;
+ lv->static_u = lv->static_l = 1; /* array index -> var not modified */
+ }
+ else if (type == VAR_MOD) {
+ lv->modified = 1;
+ switch (direction) { /* var is used in assignment -> set */
+ case D_UP: /* proper static bounds */
+ lv->static_u = 0; lv->static_l = 1;
+ break;
+ case D_DOWN:
+ lv->static_u = 1; lv->static_l = 0;
+ break;
+ case D_UNKNOWN:
+ lv->static_u = lv->static_l = 0;
+ break;
+ default:
+ printf("C_ERROR: unknown direction\n");
+ break;
+ }
+ }
+
+ /* !! strange
+ lv->modified = 0;
+ */
+
+ /* 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;
+}
+
+/* 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
+ found, a list of all variables, that are used as array index, is built and
+ 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)
+{
+ basicblock bp;
+ instruction *ip;
+ int ic, i, j, access;
+ struct depthElement *d;
+ struct Trace *t;
+
+ if (c_toVisit[node] > 0) { /* node has not been visited yet */
+ c_toVisit[node] = 0;
+
+ bp = block[node]; /* prepare an instruction scan */
+ ip = bp.iinstr;
+ ic = bp.icount;
+
+ access = 0; /* number of array accesses in loop */
+
+ for (i=0; i<ic; ++i, ++ip) { /* for each instruction, check opcode */
+ switch (ip->opc) {
+ case ICMD_IASTORE: /* array store */
+ case ICMD_LASTORE:
+ case ICMD_FASTORE:
+ case ICMD_DASTORE:
+ case ICMD_AASTORE:
+ case ICMD_BASTORE:
+ case ICMD_CASTORE:
+ case ICMD_SASTORE:
+ t = tracing(&bp, i-1, 1); /* try to identify index variable */
+
+ 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);
+ access++;
+ }
+ else if (t->type == TRACE_ICONST)
+ access++;
+ break;
+
+ case ICMD_IALOAD: /* array load */
+ case ICMD_LALOAD:
+ case ICMD_FALOAD:
+ case ICMD_DALOAD:
+ case ICMD_AALOAD:
+ case ICMD_BALOAD:
+ case ICMD_CALOAD:
+ case ICMD_SALOAD:
+ t = tracing(&bp, i-1, 0); /* try to identify index variable */
+
+ 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);
+ access++;
+ }
+ else if (t->type == TRACE_ICONST)
+ access++;
+ break;
+
+ case ICMD_ISTORE: /* integer store */
+ 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);
+ else if (t->var == ip->op1)
+ /* a constant was subtracted from the same var */
+ add_to_vars(t->var, VAR_MOD, D_DOWN);
+ else
+ add_to_vars(t->var, VAR_MOD, D_UNKNOWN);
+ }
+ else
+ add_to_vars(ip->op1, VAR_MOD, D_UNKNOWN);
+ break;
+
+ case ICMD_IINC: /* simple add/sub of a constant */
+ c_var_modified[ip->op1] = 1;
+
+ if (ip->val.i > 0)
+ add_to_vars(ip->op1, VAR_MOD, D_UP);
+ else
+ add_to_vars(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;
+ break;
+
+ default:
+ }
+ }
+
+ d = c_dTable[node];
+ while (d != NULL) { /* check all successors of block */
+ access += analyze_for_array_access(d->value);
+ d = d->next;
+ }
+
+ return access;
+ }
+ else
+ 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)
+{
+ basicblock bp;
+ instruction *ip;
+ int count, i;
+ struct LoopVar *lv;
+ struct depthElement *d;
+
+ /* printf("QS: %d - %d\n", node, c_exceptionVisit[node]); */
+
+
+ if (c_exceptionVisit[node] > 0) { /* node is part of exception graph */
+ c_exceptionVisit[node] = -1;
+
+ bp = block[node]; /* setup scan of all instructions */
+ ip = bp.iinstr;
+ count = bp.icount;
+
+ for (i=0; i<count; ++i, ++ip) { /* for each instruction do */
+ switch (ip->opc) {
+ case ICMD_ISTORE:
+ case ICMD_IINC: /* a variable is modified */
+
+ lv = c_loopvars; /* is it an array index var ? */
+ while (lv != NULL) {
+ if ((lv->index) && (lv->value == ip->op1))
+ return 1; /* yes, so return 1 */
+ lv = lv->next;
+ }
+ break;
+ }
+ }
+
+ d = c_exceptionGraph[node]; /* check all successor nodes */
+ while (d != NULL) {
+ if (quick_scan(d->value) > 0)
+ return 1; /* if an access is found return 1 */
+ d = d->next;
+ }
+
+ return 0; /* nothing found, so return 0 */
+ }
+ else
+ 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)
+{
+ struct depthElement *d, *tmp, *tmp2;
+ int i, j, k, value, flag, count;
+ struct LoopElement *le;
+
+ d = c_dTable[head];
+ count = flag = 0;
+
+ /* analyze for or-statements */
+#ifdef LOOP_DEBUG
+ printf("*** Analyze for OR ... ");
+ fflush(stdout);
+#endif
+
+ while (d != NULL) { /* for all successor nodes check if they */
+ value = d->value; /* are part of the loop */
+
+ le = lc->nodes;
+
+ while (le != NULL) {
+ if (le->node == value)
+ break;
+ le = le->next;
+ }
+
+ if (le == NULL) /* node is not part of the loop */
+ ++flag;
+
+ d = d->next;
+ ++count;
+ }
+
+ if ((count > 1) && (flag == 0)){/* if all successors part of the loop, exit */
+#ifdef STATISTICS
+ c_stat_or++;
+#endif
+ return 0;
+ }
+
+ /* check for exceptions */
+ /* printf("done\n*** Analyze for EXCEPTIONS(%d) . ", exceptiontablelength); */
+
+ if (!exceptiontablelength) /* when there are no exceptions, exit */
+ return 1;
+
+ if ((c_exceptionGraph = (struct depthElement **) malloc(sizeof(struct depthElement *) * block_count)) == NULL)
+ c_mem_error();
+ if ((c_exceptionVisit = (int *) malloc(sizeof(int) * block_count)) == NULL)
+ c_mem_error();
+
+ for (k=0; k<block_count; ++k) {
+ c_exceptionVisit[k] = -1;
+ 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];
+
+ le = lc->nodes;
+ while (le != NULL) {
+
+ if (le->node == value) { /* exception is in loop */
+#ifdef LOOP_DEBUG
+ printf("C_INFO: Loop contains exception\n");
+ fflush(stdout);
+#endif
+
+ /* build a graph structure, that contains all nodes that are */
+ /* part of the catc block */
+ dF_Exception(-1, block_index[extable[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++;
+#endif
+ /* printf("C_INFO: loopVar modified in exception\n"); */
+ return 0;
+ }
+ }
+ le = le->next;
+ }
+ }
+
+#ifdef LOOP_DEBUG
+ printf("none ... done\n");
+ fflush(stdout);
+#endif
+ 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()
+{
+ struct LoopVar *lv;
+ lv = c_loopvars;
+
+ while (lv != NULL) {
+ if (lv->modified)
+ 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)
+{
+ basicblock bp;
+ instruction *ip;
+ int ic, l_mod, r_mod, changed, operand;
+ struct Trace *left, *right, *th;
+ struct LoopVar *lv_left, *lv_right, *lh;
+
+ bp = block[head];
+ ic = bp.icount;
+ ip = bp.iinstr+(ic-1); /* set ip to last instruction in header node */
+
+ switch (ip->opc) { /* check op-code */
+
+ /* comparison against constant value */
+ case ICMD_IFEQ: /* ..., value ==> ... */
+ case ICMD_IFLT: /* ..., value ==> ... */
+ case ICMD_IFLE: /* ..., value ==> ... */
+ case ICMD_IFGT: /* ..., value ==> ... */
+ case ICMD_IFGE: /* ..., value ==> ... */
+ /* op1 = target JavaVM pc, val.i = constant */
+
+ left = tracing(&bp, ic-2, 0); /* analyse left arg., right is constant */
+ right = create_trace(TRACE_ICONST, -1, ip->val.i, 0);
+ break;
+
+ /* standard comparison */
+ case ICMD_IF_ICMPEQ: /* ..., value, value ==> ... */
+ case ICMD_IF_ICMPLT: /* ..., value, value ==> ... */
+ case ICMD_IF_ICMPGT: /* ..., value, value ==> ... */
+ case ICMD_IF_ICMPLE: /* ..., value, value ==> ... */
+ case ICMD_IF_ICMPGE: /* ..., value, value ==> ... */
+
+ left = tracing(&bp, ic-2, 1); /* get left and right argument */
+ right = tracing(&bp, ic-2, 0);
+ break;
+
+ /* other condition */
+ default:
+ left = create_trace(TRACE_UNKNOWN, -1, 0, 0);
+ right = create_trace(TRACE_UNKNOWN, -1, 0, 0);
+ break;
+ }
+
+ /* analyse left and right side of comparison */
+ l_mod = r_mod = 0;
+
+ if (left->type == TRACE_IVAR) { /* is a loop variable on left side ? */
+ lv_left = c_loopvars;
+ while (lv_left != NULL) {
+ if (lv_left->value == left->var) {
+ l_mod = lv_left->modified; /* yes, but has it been modified ? */
+ break;
+ }
+ lv_left = lv_left->next;
+ }
+ }
+
+ if (right->type == TRACE_IVAR){ /* is a loop variable on right side ? */
+ lv_right = c_loopvars;
+ while (lv_right != NULL) {
+ if (lv_right->value == right->var) {
+ r_mod = lv_right->modified; /* yes, but has it been modified ? */
+ break;
+ }
+ lv_right = lv_right->next;
+ }
+ }
+
+ if ((l_mod - r_mod) == 0) { /* both 1 or both 0 -> no dynamic contraints*/
+ c_rightside = NULL; /* possible */
+ return;
+ }
+
+ /* to simplify processing, make the left side the one, that contains the */
+ /* modified variable */
+ if (r_mod > l_mod) {
+ th = left; left = right; right = th;
+ lh = lv_left; lv_left = lv_right; lv_right = lh;
+ changed = 1; /* set changed to true */
+ }
+ else
+ changed = 0; /* no change needed */
+
+ /* make sure that right side's value does not change during loop execution */
+ if (right->type == TRACE_UNKNOWN) {
+ c_rightside = NULL;
+ return;
+ }
+
+ /* determine operands: */
+ /* for further explaination a is modified, b nonmodified var */
+ switch (ip->opc) { /* check opcode again */
+ case ICMD_IFEQ: /* ..., value ==> ... */
+ case ICMD_IF_ICMPEQ: /* ..., value, value ==> ... */
+ operand = OP_EQ; /* a == b */
+ break;
+
+ case ICMD_IFLE: /* ..., value ==> ... */
+ case ICMD_IF_ICMPLE: /* ..., value, value ==> ... */
+ if (changed)
+ operand = OP_GE; /* b<=a -> a>=b */
+ else {
+ operand = OP_LT; /* a<=b -> a<(b+1) */
+ if (left->constant != 0)
+ left->constant -= 1;
+ else
+ right->constant += 1;
+ }
+ break;
+
+ case ICMD_IFLT: /* ..., value ==> ... */
+ case ICMD_IF_ICMPLT: /* ..., value, value ==> ... */
+ if (changed) {
+ operand = OP_GE; /* b<a -> a>=(b+1) */
+ if (left->constant != 0)
+ left->constant -= 1;
+ else
+ right->constant += 1;
+ }
+ else
+ operand = OP_LT; /* a<b -> a<b */
+ break;
+
+ case ICMD_IFGT: /* ..., value ==> ... */
+ case ICMD_IF_ICMPGT: /* ..., value, value ==> ... */
+ if (changed)
+ operand = OP_LT; /* b>a -> a<b */
+ else {
+ operand = OP_GE; /* a>b -> a>=(b+1) */
+ if (left->constant != 0)
+ left->constant -= 1;
+ else
+ right->constant += 1;
+ }
+ break;
+
+ case ICMD_IFGE: /* ..., value ==> ... */
+ case ICMD_IF_ICMPGE: /* ..., value, value ==> ... */
+ if (changed) {
+ operand = OP_LT; /* b>=a -> a<(b+1) */
+ if (left->constant != 0)
+ left->constant -= 1;
+ else
+ right->constant += 1;
+ }
+ else
+ operand = OP_GE; /* a>=b -> a>=b */
+ break;
+
+ default:
+ printf("C_ERROR: debugging error 0x00\n");
+ }
+
+
+ /* NOW: left/lv_left -> loopVar */
+ /* right/lv_right -> const, nonmod. var, arraylength */
+ switch (operand) { /* check operand */
+ case OP_EQ:
+ lv_left->dynamic_u_v = 1; /* upper + lower bound tested */
+ lv_left->dynamic_l_v = 1;
+
+ lv_left->dynamic_l = lv_left->dynamic_u = left->constant;
+ break;
+
+ case OP_LT:
+ lv_left->dynamic_u_v = 1; /* upper bound tested */
+
+ lv_left->dynamic_u = left->constant;
+ break;
+
+ case OP_GE:
+ lv_left->dynamic_l_v = 1; /* lower bound tested */
+
+ lv_left->dynamic_l = left->constant;
+ break;
+
+ default:
+ printf("C_ERROR: debugging error 0x01\n");
+ }
+
+ c_rightside = right;
+
+ switch (c_rightside->type) {
+ case TRACE_ICONST:
+ c_rs_needed_instr = 1;
+ break;
+ case TRACE_ALENGTH:
+ c_rs_needed_instr = 2;
+ break;
+ case TRACE_IVAR:
+ 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)
+{
+ 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 ? */
+ while (tc != NULL) {
+ if (tc->type == TEST_ZERO) {
+ if (constant < tc->constant)
+ tc->constant = constant;
+ return; /* yes. update constant and return */
+ }
+ tc = tc->next;
+ }
+
+ /* insert a new test for this variable */
+ if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
+ c_mem_error();
+ tc->type = TEST_ZERO;
+ tc->varRef = varRef;
+ tc->constant = constant;
+ tc->next = c_constraints[varRef];
+ c_constraints[varRef] = tc;
+ 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 ? */
+ while (tc != NULL) {
+ if ((tc->type == TEST_ALENGTH) && (tc->arrayRef == arrayRef)) {
+ if (constant > tc->constant)
+ tc->constant = constant;
+ return; /* yes. update constant and return */
+ }
+ tc = tc->next;
+ }
+
+ /* insert a new test for this variable */
+ if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
+ c_mem_error();
+ tc->type = TEST_ALENGTH;
+ tc->arrayRef = arrayRef;
+ tc->varRef = varRef;
+ tc->constant = constant;
+ tc->next = c_constraints[varRef];
+ c_constraints[varRef] = tc;
+ 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;
+ }
+
+ break;
+
+ case TEST_CONST_ZERO:
+ /* done earlier */
+ break;
+
+ case TEST_CONST_ALENGTH: /* a const is tested against array length */
+
+ /* does a test already exist for this array */
+ tc = c_constraints[maxlocals];
+ while (tc != NULL) {
+ if ((tc->type == TEST_CONST_ALENGTH) && (tc->arrayRef == arrayRef)) {
+ if (constant > tc->constant)
+ tc->constant = constant;
+ return; /* yes. update constant and return */
+ }
+ tc = tc->next;
+ }
+
+ /* insert a new test for this array */
+ if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
+ c_mem_error();
+ tc->type = TEST_CONST_ALENGTH;
+ tc->arrayRef = arrayRef;
+ tc->constant = constant;
+ tc->next = c_constraints[maxlocals];
+ c_constraints[maxlocals] = tc;
+ 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;
+ }
+
+ break;
+
+ case TEST_UNMOD_ZERO: /* test unmodified var against constant */
+
+ /* search if test already exists */
+ tc = c_constraints[varRef];
+ while (tc != NULL) {
+ if (tc->type == TEST_UNMOD_ZERO) {
+ if (constant < tc->constant)
+ tc->constant = constant;
+ return; /* yes, so update constant */
+ }
+ tc = tc->next;
+ }
+
+ /* else, a new test is inserted */
+ if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
+ c_mem_error();
+ tc->type = TEST_UNMOD_ZERO;
+ tc->varRef = varRef;
+ tc->constant = constant;
+ tc->next = c_constraints[varRef];
+ c_constraints[varRef] = tc;
+ c_needed_instr += 3;
+
+ break;
+
+ case TEST_UNMOD_ALENGTH: /* test unmodified var against array length */
+
+ /* search if test alreay exists */
+ tc = c_constraints[varRef];
+ while (tc != NULL) {
+ if ((tc->type == TEST_UNMOD_ALENGTH) && (tc->arrayRef == arrayRef)) {
+ if (constant > tc->constant)
+ tc->constant = constant;
+ return; /* yes, so modify constants */
+ }
+ tc = tc->next;
+ }
+
+ /* create new entry */
+ if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
+ c_mem_error();
+ tc->type = TEST_UNMOD_ALENGTH;
+ tc->varRef = varRef;
+ tc->arrayRef = arrayRef;
+ tc->constant = constant;
+ tc->next = c_constraints[varRef];
+ c_constraints[varRef] = tc;
+ 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;
+ }
+
+ break;
+
+ case TEST_RS_ZERO: /* test right side of the loop condition */
+ /* against a constant - needed by dynamic */
+ /* checks */
+ /*!! varRef -> maxlocals */
+ /* search if test already exists */
+ tc = c_constraints[maxlocals];
+ while (tc != NULL) {
+ if (tc->type == TEST_RS_ZERO) {
+ if (constant < tc->constant)
+ tc->constant = constant;
+ return; /* yes, so modify constants */
+ }
+ tc = tc->next;
+ }
+
+ /* create new entry */
+ if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
+ 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);
+
+ /* 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;
+ }
+
+ break;
+
+ case TEST_RS_ALENGTH: /* test right side of the loop condition */
+ /* against array length - needed by dynamic */
+ /* checks */
+ /*!! varRef -> maxlocals */
+ /* search if test already exists */
+ tc = c_constraints[maxlocals];
+ while (tc != NULL)
+ {
+ if ((tc->type == TEST_RS_ALENGTH) && (tc->arrayRef == arrayRef))
+ {
+ if (constant > tc->constant)
+ tc->constant = constant;
+ return; /* yes, so modify constants */
+ }
+ tc = tc->next;
+ }
+
+ /* create new entry */
+ if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
+ c_mem_error();
+ 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);
+
+ /* 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 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;
+ }
+ 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)
+{
+ struct Constraint *tc;
+ struct LoopVar *lv;
+ int varRef;
+ int high, low;
+
+ /* printf("insert static check - %d\n", arrayRef);
+ show_trace(index);
+ show_change(varChanges);
+ */
+
+ if (varChanges == NULL) { /* the variable hasn't changed / const */
+ if ((varChanges = (struct Changes *) malloc(sizeof(struct Changes))) == NULL)
+ c_mem_error();
+ varChanges->lower_bound = varChanges->upper_bound = 0;
+ }
+
+ 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++;
+#endif
+ return OPT_NONE;
+ }
+
+ varRef = index->var;
+ high = low = 0;
+
+ if (c_var_modified[varRef]) { /* volatile var */
+
+ lv = c_loopvars; /* get reference to loop variable */
+
+ while ((lv != NULL) && (lv->value != varRef))
+ lv = lv->next;
+ if (lv == NULL)
+ printf("C_ERROR: debugging error 0x02\n");
+
+ /* show_varinfo(lv); */
+
+ /* check existing static bounds and add new contraints on variable */
+ /* to possibly remove bound checks */
+ if (lv->static_l) {
+ /* 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);
+ else
+ add_new_constraint(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);
+ low = 1;
+ }
+ }
+
+ if (lv->static_u) {
+ /* 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);
+ else
+ add_new_constraint(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);
+ 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);
+ low = high = 1;
+ }
+
+ /* if the addition of new variable tests made guarantees possible, */
+ /* return the best possible optimization */
+ if ((high > 0) && (low > 0)) {
+ /* printf("fully optimzed\n"); */
+#ifdef STATISTICS
+ c_stat_full_opt++;
+#endif
+ return OPT_FULL;
+ }
+ else if (high > 0) {
+ /* printf("upper optimzed\n"); */
+#ifdef STATISTICS
+ c_stat_upper_opt++;
+#endif
+ return OPT_UPPER;
+ }
+ else if (low > 0) {
+ /* printf("lower optimzed\n"); */
+#ifdef STATISTICS
+ c_stat_lower_opt++;
+#endif
+ return OPT_LOWER;
+ }
+ else {
+ /* printf("not optimzed\n"); */
+#ifdef STATISTICS
+ c_stat_no_opt++;
+#endif
+ return OPT_NONE;
+ }
+ break;
+
+ case TRACE_ICONST: /* if it is a constant, optimization is easy */
+ if (index->constant < 0) {
+#ifdef STATISTICS
+ 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++;
+#endif
+ return OPT_FULL; /* else just test constant against array length */
+ }
+ break;
+
+ case TRACE_ALENGTH: /* else, no optimizations possible */
+ case TRACE_UNKNOWN:
+ case TRACE_AVAR:
+#ifdef STATISTICS
+ c_stat_no_opt++;
+#endif
+ return OPT_NONE;
+ }
+}
+
+
+
+/* copy a stack and return the start pointer of the newly created one
+*/
+stackptr copy_stack_from(stackptr source) {
+ stackptr current, top;
+
+ if (source == NULL)
+ return NULL;
+
+ /* copy first element */
+ current = DMNEW(stackelement, 1);
+ current->type = source->type;
+ current->flags = source->flags;
+ current->varkind = source->varkind;
+ current->varnum = source->varnum;
+ current->regoff = source->regoff;
+
+ top = current;
+
+ /* if there exist more, then copy the rest */
+ while (source->prev != NULL) {
+ source = source->prev;
+ current->prev = DMNEW(stackelement, 1);
+ current->type = source->type;
+ current->flags = source->flags;
+ current->varkind = source->varkind;
+ current->varnum = source->varnum;
+ current->regoff = source->regoff;
+ current = current->prev;
+ }
+
+ current->prev = NULL;
+ return top;
+}
+
+
+/* The following defines are used in the procedure void create_static_checks(...)
+ They add a new instruction with its corresponding stack manipulation and
+ are used to build the new loop header of an optimized loop, where we have
+ to check certain variables and constants against values to guarantee that
+ index values in array accesses remain with array bounds.
+
+ inst: pointer to the new instruction
+ tos: stackpointer before this operation is executed
+ newstack: temporary stackptr
+ stackdepth: counts the current stackdepth
+ original start: blockpointer to the head of the new, optimized loop
+*/
+
+/* Load a local integer variable v */
+#define LOAD_VAR(v) { \
+ inst->opc = ICMD_ILOAD; \
+ inst->op1 = v; \
+ newstack = DMNEW(stackelement, 1); \
+ inst->dst = newstack; \
+ newstack->prev = tos; \
+ newstack->type = TYPE_INT; \
+ newstack->flags = 0; \
+ newstack->varkind = LOCALVAR; \
+ newstack->varnum = v; \
+ tos = newstack; \
+ inst++; \
+ stackdepth++; \
+ }
+
+/* Load a constant with value c */
+#define LOAD_CONST(c) { \
+ inst->opc = ICMD_ICONST; \
+ inst->op1 = 0; \
+ inst->val.i = (c); \
+ newstack = DMNEW(stackelement, 1); \
+ newstack->prev = tos; \
+ newstack->type = TYPE_INT; \
+ newstack->flags = 0; \
+ newstack->varkind = UNDEFVAR; \
+ newstack->varnum = stackdepth; \
+ tos = newstack; \
+ inst->dst = tos; \
+ inst++; \
+ stackdepth++; \
+ }
+
+/* Load a local reference (adress) variable a */
+#define LOAD_ADDR(a) { \
+ inst->opc = ICMD_ALOAD; \
+ inst->op1 = a; \
+ newstack = DMNEW(stackelement, 1); \
+ newstack->prev = tos; \
+ newstack->type = TYPE_ADR; \
+ newstack->flags = 0; \
+ newstack->varkind = LOCALVAR; \
+ newstack->varnum = a; \
+ tos = newstack; \
+ inst->dst = tos; \
+ inst++; \
+ stackdepth++; \
+ }
+
+/* Insert a compare greater-or-equal and jump to the unoptimized loop, if the */
+/* comparison is true */
+#define GOTO_NOOPT_IF_GE { \
+ inst->opc = ICMD_IF_ICMPGE; \
+ inst->target = original_start->copied_to; \
+ if (tos->varkind == UNDEFVAR) \
+ tos->varkind = TEMPVAR; \
+ tos = tos->prev; \
+ if (tos->varkind == UNDEFVAR) \
+ tos->varkind = TEMPVAR; \
+ tos = tos->prev; \
+ inst->dst = tos; \
+ inst++; \
+ stackdepth -= 2; \
+ }
+
+/* Insert a compare greater than and jump to the unoptimized loop, if the */
+/* comparison is true */
+#define GOTO_NOOPT_IF_GT { \
+ inst->opc = ICMD_IF_ICMPGT; \
+ inst->target = original_start->copied_to; \
+ if (tos->varkind == UNDEFVAR) \
+ tos->varkind = TEMPVAR; \
+ tos = tos->prev; \
+ if (tos->varkind == UNDEFVAR) \
+ tos->varkind = TEMPVAR; \
+ tos = tos->prev; \
+ inst->dst = tos; \
+ inst++; \
+ stackdepth -= 2; \
+ }
+
+
+/* Insert a compare less-than and jump to the unoptimized loop, if the */
+/* comparison is true */
+#define GOTO_NOOPT_IF_LT { \
+ inst->opc = ICMD_IF_ICMPLT; \
+ inst->target = original_start->copied_to; \
+ if(tos->varkind == UNDEFVAR) \
+ tos->varkind = TEMPVAR; \
+ tos = tos->prev; \
+ if(tos->varkind == UNDEFVAR) \
+ tos->varkind = TEMPVAR; \
+ tos = tos->prev; \
+ inst->dst = tos; \
+ inst++; \
+ stackdepth -= 2; \
+ }
+
+/* Insert a compare if-not-null and jump to the unoptimized loop, if the */
+/* comparison is true */
+#define GOTO_NOOPT_IF_NULL { \
+ inst->opc = ICMD_IFNULL; \
+ inst->target = original_start->copied_to; \
+ if(tos->varkind == UNDEFVAR) \
+ tos->varkind = TEMPVAR; \
+ tos = tos->prev; \
+ inst->dst = tos; \
+ inst++; \
+ stackdepth -= 1; \
+ }
+
+/* Insert an add instruction, that adds two integer values on top of the stack */
+/* together */
+#define ADD { \
+ inst->opc = ICMD_IADD; \
+ if(tos->varkind == UNDEFVAR) \
+ tos->varkind = TEMPVAR; \
+ tos = tos->prev; \
+ if(tos->varkind == UNDEFVAR) \
+ tos->varkind = TEMPVAR; \
+ tos = tos->prev; \
+ newstack = DMNEW(stackelement, 1); \
+ newstack->prev = tos; \
+ newstack->type = TYPE_INT; \
+ newstack->flags = 0; \
+ newstack->varkind = UNDEFVAR; \
+ newstack->varnum = stackdepth; \
+ tos = newstack; \
+ inst->dst = tos; \
+ inst++; \
+ stackdepth--; \
+ }
+
+/* Insert instructions to load the arraylength of an array with reference a */
+/* 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]) { \
+ LOAD_ADDR(a); \
+ GOTO_NOOPT_IF_NULL; \
+ c_null_check[a] = 0; \
+ } \
+ LOAD_ADDR(a); \
+ inst->opc = ICMD_ARRAYLENGTH; \
+ if(tos->varkind == UNDEFVAR) \
+ tos->varkind = TEMPVAR; \
+ tos = tos->prev; \
+ newstack = DMNEW(stackelement, 1); \
+ newstack->prev = tos; \
+ newstack->type = TYPE_INT; \
+ newstack->flags = 0; \
+ newstack->varkind = UNDEFVAR; \
+ newstack->varnum = stackdepth; \
+ tos = newstack; \
+ inst->dst = tos; \
+ inst++; \
+ }
+
+
+/* Inserts the instructions to load the value of the right side of comparison */
+/* Depending of the type of the right side, the apropriate instructions are */
+/* created. */
+#define LOAD_RIGHT_SIDE { \
+ switch (c_rightside->type) { \
+ case TRACE_ICONST: \
+ LOAD_CONST(c_rightside->constant); \
+ break; \
+ case TRACE_IVAR: \
+ LOAD_VAR(c_rightside->var); \
+ LOAD_CONST(c_rightside->constant); \
+ ADD; \
+ break; \
+ case TRACE_ALENGTH: \
+ LOAD_ARRAYLENGTH(c_rightside->var); \
+ break; \
+ default: \
+ printf("C_ERROR: illegal trace on rightside of loop-header\n"); \
+ exit; \
+ } \
+}
+
+/* Patch jumps in original loop and in copied loop, add gotos in copied loop.
+ All jumps in the original loop to the loop head have to be redirected to
+ the newly inserted one. For the copied loop, it is necessay to redirect all
+ jumps inside that loop to the copied nodes. lc points to the current loop,
+ loop_head is a pointer to the newly inserted head and original start was
+ the old head and is now the head of the optimized variant of the loop.
+*/
+void patch_jumps(basicblock *original_start, basicblock *loop_head, struct LoopContainer *lc)
+{
+ /* step through all nodes of a loop */
+ struct LoopElement *le;
+ basicblock *bptr;
+ instruction *inst, *temp_instr;
+ int i;
+
+ le = lc->nodes;
+ while (le != NULL) {
+
+ /* do nothing for new loop head */
+ if (le->block == loop_head) {
+ le = le->next;
+ continue;
+ }
+
+ /* for original version */
+ bptr = le->block;
+ inst = bptr->iinstr;
+ for (i = 0; i < bptr->icount; ++i, ++inst) {
+ switch (inst->opc) {
+
+ case ICMD_IF_ICMPEQ:
+ case ICMD_IF_ICMPLT:
+ case ICMD_IF_ICMPLE:
+ case ICMD_IF_ICMPNE:
+ case ICMD_IF_ICMPGT:
+ case ICMD_IF_ICMPGE:
+
+ 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_ACMPEQ:
+ case ICMD_IF_ACMPNE:
+
+ case ICMD_IFEQ:
+ case ICMD_IFNE:
+ case ICMD_IFLT:
+ case ICMD_IFGE:
+ case ICMD_IFGT:
+ case ICMD_IFLE:
+
+ 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_GOTO:
+ case ICMD_JSR:
+ case ICMD_IFNULL:
+ case ICMD_IFNONNULL:
+
+ /* jump to newly inserted loopheader has to be redirected */
+ if (((basicblock *) inst->target) == loop_head)
+ inst->target = (void *) original_start;
+ break;
+
+ case ICMD_TABLESWITCH:
+ {
+ s4 *s4ptr, l, i;
+ void **tptr;
+
+ tptr = (void **) inst->target;
+
+ s4ptr = inst->val.a;
+ l = s4ptr[1]; /* low */
+ i = s4ptr[2]; /* high */
+
+ i = i - l + 1;
+
+ /* jump to newly inserted loopheader has to be redirected */
+ for (tptr = inst->target; i >= 0; --i, ++tptr) {
+ if (((basicblock *) *tptr) == loop_head)
+ tptr[0] = (void *) original_start;
+ }
+ }
+ break;
+
+ case ICMD_LOOKUPSWITCH:
+ {
+ s4 i, l, val, *s4ptr;
+ void **tptr;
+
+ tptr = (void **) inst->target;
+
+ s4ptr = inst->val.a;
+ l = s4ptr[0]; /* default */
+ i = s4ptr[1]; /* count */
+
+ /* jump to newly inserted loopheader has to be redirected */
+ for (tptr = inst->target; i >= 0; --i, ++tptr) {
+ if (((basicblock *) *tptr) == loop_head)
+ tptr[0] = (void *) original_start;
+ }
+ }
+ break;
+
+ }
+ }
+
+ /* if node is part of loop and has fall through to original start, that */
+ /* must be redirected. Unfortunately the instructions have to be copied */
+
+ if (bptr->next == loop_head) {
+ temp_instr = DMNEW(instruction, bptr->icount + 1);
+ memcpy(temp_instr, bptr->iinstr, sizeof(instruction)*bptr->icount);
+ bptr->iinstr = temp_instr;
+
+ bptr->iinstr[bptr->icount].opc = ICMD_GOTO;
+ bptr->iinstr[bptr->icount].target = original_start;
+ bptr->iinstr[bptr->icount].dst = NULL;
+ ++bptr->icount;
+ }
+
+ /* for copied version - which gets the unoptimized variant */
+ bptr = le->block->copied_to;
+ inst = bptr->iinstr;
+ for (i = 0; i < bptr->icount; ++i, ++inst) {
+
+ switch (inst->opc) {
+
+ case ICMD_IASTORE: /* array store */
+ case ICMD_LASTORE:
+ case ICMD_FASTORE:
+ case ICMD_DASTORE:
+ case ICMD_AASTORE:
+ case ICMD_BASTORE:
+ case ICMD_CASTORE:
+ case ICMD_SASTORE:
+ case ICMD_IALOAD: /* array load */
+ case ICMD_LALOAD:
+ case ICMD_FALOAD:
+ case ICMD_DALOAD:
+ case ICMD_AALOAD:
+ case ICMD_BALOAD:
+ case ICMD_CALOAD:
+ case ICMD_SALOAD:
+
+ /* undo previous optimizations in new loop */
+ inst->op1 = 0;
+ break;
+
+ case ICMD_IF_ICMPEQ:
+ case ICMD_IF_ICMPLT:
+ case ICMD_IF_ICMPLE:
+ case ICMD_IF_ICMPNE:
+ case ICMD_IF_ICMPGT:
+ case ICMD_IF_ICMPGE:
+
+ 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_ACMPEQ:
+ case ICMD_IF_ACMPNE:
+
+ case ICMD_IFEQ:
+ case ICMD_IFNE:
+ case ICMD_IFLT:
+ case ICMD_IFGE:
+ case ICMD_IFGT:
+ case ICMD_IFLE:
+
+ 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_GOTO:
+ case ICMD_JSR:
+ case ICMD_IFNULL:
+ case ICMD_IFNONNULL:
+
+ /* jump to newly inserted loopheader has to be redirected */
+ if (((basicblock *) inst->target) == loop_head)
+ inst->target = (void *) original_start->copied_to;
+ /* jump to loop internal nodes has to be redirected */
+ else if (((basicblock *) inst->target)->lflags & LOOP_PART)
+ inst->target = (void *) ((basicblock *) inst->target)->copied_to;
+ break;
+
+ case ICMD_TABLESWITCH:
+ {
+ s4 *s4ptr, l, i;
+
+ void **copy_ptr, *base_ptr;
+ void **tptr;
+
+ tptr = (void **) inst->target;
+
+ s4ptr = inst->val.a;
+ l = s4ptr[1]; /* low */
+ i = s4ptr[2]; /* high */
+
+ i = i - l + 1;
+
+ copy_ptr = (void**) DMNEW(void*, i+1);
+ base_ptr = (void*) copy_ptr;
+
+ /* Targets for switch instructions are stored in an extra */
+ /* that must be copied for new inserted loop. */
+
+ for (tptr = inst->target; i >= 0; --i, ++tptr, ++copy_ptr) {
+ /* jump to newly inserted loopheader must be redirected */
+ if (((basicblock *) *tptr) == loop_head)
+ copy_ptr[0] = (void *) original_start->copied_to;
+ /* jump to loop internal nodes has to be redirected */
+ else if (((basicblock *) *tptr)->lflags & LOOP_PART)
+ copy_ptr[0] = (void *) ((basicblock *) tptr[0])->copied_to;
+ else
+ copy_ptr[0] = tptr[0];
+ }
+
+ inst->target = base_ptr;
+ }
+ break;
+
+ case ICMD_LOOKUPSWITCH:
+ {
+ s4 i, l, val, *s4ptr;
+
+ void **copy_ptr, **base_ptr;
+ void **tptr;
+
+ tptr = (void **) inst->target;
+
+ s4ptr = inst->val.a;
+ l = s4ptr[0]; /* default */
+ i = s4ptr[1]; /* count */
+
+ copy_ptr = (void**) DMNEW(void*, i+1);
+ base_ptr = (void*) copy_ptr;
+
+ /* Targets for switch instructions are stored in an extra */
+ /* that must be copied for new inserted loop. */
+
+ for (tptr = inst->target; i >= 0; --i, ++tptr, ++copy_ptr) {
+ /* jump to newly inserted loopheader must be redirected */
+ if (((basicblock *) *tptr) == loop_head)
+ copy_ptr[0] = (void *) original_start->copied_to;
+ /* jump to loop internal nodes has to be redirected */
+ else if (((basicblock *) *tptr)->lflags & LOOP_PART)
+ copy_ptr[0] = (void *) ((basicblock *) tptr[0])->copied_to;
+ else
+ copy_ptr[0] = tptr[0];
+ }
+
+ inst->target = base_ptr;
+ }
+ break;
+
+ }
+ }
+
+ /* if fall through exits loop, goto is needed */
+ if (!(le->block->next->lflags & LOOP_PART)) {
+ bptr->iinstr[bptr->icount].opc = ICMD_GOTO;
+ bptr->iinstr[bptr->icount].dst = NULL;
+ bptr->iinstr[bptr->icount].target = le->block->next;
+ bptr->icount++;
+ }
+
+ le = le->next;
+ }
+}
+
+/* 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)
+{
+ /* 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))
+ return;
+
+ /* create new node, that should be inserted */
+ t = DMNEW(struct LoopElement, 1);
+ t->block = to_insert;
+ t->node = -1;
+
+ /* first, find the node, that has to be replaced (= "to_insert") and */
+ /* replace it by the node "replace" */
+ le = lc->nodes;
+ while (le->block != to_insert)
+ le = le->next;
+ le->block = replace;
+
+ /* now find the node after and insert the newly create node before "after" */
+ le = lc->nodes;
+ if (le->block == after) {
+ t->next = lc->nodes;
+ lc->nodes = t;
+ }
+ else {
+ while (le->next->block != after)
+ le = le->next;
+
+ t->next = le->next;
+ le->next = t;
+ }
+
+ /* go up one hierarchie level */
+ header_into_parent_loops(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)
+{
+ struct LoopElement *le, *t;
+
+ /* if the top of the tree is reached, then return */
+ if ((lc == NULL) || (lc == root))
+ return;
+
+ /* create new node, that should be inserted */
+ t = DMNEW(struct LoopElement, 1);
+ t->block = to_insert;
+ t->node = -1;
+
+ le = lc->nodes;
+
+ /* append new node to node list of loop */
+ while (le->next != NULL)
+ le = le->next;
+
+ t->next = le->next;
+ le->next = t;
+
+ /* go up one hierarchie level */
+ node_into_parent_loops(NULL, to_insert);
+}
+
+
+/* void patch_handler(...) is very similar to parts of the function patch_jumps.
+ Its task is to redirect all jumps from the original head to the new head and
+ 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;
+ s4 *s4ptr;
+ void **tptr;
+ int high, low, count, i;
+
+ /* If node is not part of exception handler or has been visited, exit */
+ if (!(bptr->lflags & HANDLER_PART) || (bptr->lflags & HANDLER_VISITED))
+ return;
+
+ /* mark block as visited */
+ bptr->lflags |= HANDLER_VISITED;
+
+ /* for all instructions in the copied block, do */
+ for (i = 0, ip = bptr->copied_to->iinstr; i < bptr->copied_to->icount; ++i, ++ip) {
+ 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_IF_ICMPEQ:
+ case ICMD_IF_ICMPLT:
+ case ICMD_IF_ICMPLE:
+ case ICMD_IF_ICMPNE:
+ case ICMD_IF_ICMPGT:
+ case ICMD_IF_ICMPGE:
+
+ 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_ACMPEQ:
+ case ICMD_IF_ACMPNE:
+
+ case ICMD_IFEQ:
+ case ICMD_IFNE:
+ case ICMD_IFLT:
+ case ICMD_IFGE:
+ case ICMD_IFGT:
+ case ICMD_IFLE:
+
+ 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_JSR:
+ case ICMD_IFNULL:
+ case ICMD_IFNONNULL:
+
+ patch_handler(lc, bptr->next, original_head, new_head);
+
+ /* fall through */
+
+ case ICMD_GOTO:
+
+ patch_handler(lc, ip->target, original_head, new_head);
+
+ /* jumps to old header have to be redirected */
+ if (((basicblock *) ip->target) == original_head)
+ ip->target = (void *) new_head->copied_to;
+ /* jumps to handler internal nodes have to be redirected */
+ else if (((basicblock *) ip->target)->lflags & HANDLER_PART)
+ ip->target = (void *) ((basicblock *) ip->target)->copied_to;
+ /* jumps to loop internal nodes have to be redirected */
+ else if (((basicblock *) ip->target)->lflags & LOOP_PART)
+ ip->target = (void *) ((basicblock *) ip->target)->copied_to;
+
+
+ break;
+
+ case ICMD_TABLESWITCH:
+ {
+ s4 *s4ptr, l, i;
+ void **tptr;
+ void **copy_ptr, **base_ptr;
+
+ tptr = (void **) ip->target;
+ s4ptr = ip->val.a;
+ l = s4ptr[1]; /* low */
+ i = s4ptr[2]; /* high */
+ i = i - l + 1;
+
+ copy_ptr = (void**) DMNEW(void*, i+1);
+ base_ptr = (void*) copy_ptr;
+
+ for (tptr = ip->target; i >= 0; --i, ++tptr, ++copy_ptr) {
+ patch_handler(lc, ((basicblock *) *tptr), original_head, new_head);
+ /* jumps to old header have to be redirected */
+ if (((basicblock *) *tptr) == original_head)
+ copy_ptr[0] = (void *) new_head->copied_to;
+ /* jumps to handler internal nodes have to be redirected */
+ else if (((basicblock *) *tptr)->lflags & HANDLER_PART)
+ copy_ptr[0] = (void *) ((basicblock *) tptr[0])->copied_to;
+ /* jumps to loop internal nodes have to be redirected */
+ else if (((basicblock *) ip->target)->lflags & LOOP_PART)
+ copy_ptr[0] = (void *) ((basicblock *) tptr[0])->copied_to;
+ else
+ copy_ptr[0] = tptr[0];
+ }
+
+ ip->target = base_ptr;
+ }
+ break;
+
+ case ICMD_LOOKUPSWITCH:
+ {
+ s4 i, l, val, *s4ptr;
+
+ void **tptr;
+ void **copy_ptr, **base_ptr;
+
+ tptr = (void **) ip->target;
+ s4ptr = ip->val.a;
+ l = s4ptr[0]; /* default */
+ i = s4ptr[1]; /* count */
+
+ copy_ptr = (void**) DMNEW(void*, i+1);
+ base_ptr = (void*) copy_ptr;
+
+ for (tptr = ip->target; i >= 0; --i, ++tptr, ++copy_ptr) {
+
+ patch_handler(lc, ((basicblock *) *tptr), original_head, new_head);
+ /* jumps to old header have to be redirected */
+ if (((basicblock *) *tptr) == original_head)
+ copy_ptr[0] = (void *) new_head->copied_to;
+ /* jumps to handler internal nodes have to be redirected */
+ else if (((basicblock *) *tptr)->lflags & HANDLER_PART)
+ copy_ptr[0] = (void *) ((basicblock *) tptr[0])->copied_to;
+ /* jumps to loop internal nodes have to be redirected */
+ else if (((basicblock *) ip->target)->lflags & LOOP_PART)
+ copy_ptr[0] = (void *) ((basicblock *) tptr[0])->copied_to;
+ else
+ copy_ptr[0] = tptr[0];
+ }
+
+ ip->target = base_ptr;
+ }
+ break;
+
+ } /* switch */
+
+ } /* for */
+
+ /* if fall through exits loop, goto is needed */
+ if (!(bptr->next->lflags & HANDLER_PART)) {
+ bptr->copied_to->iinstr[bptr->copied_to->icount].opc = ICMD_GOTO;
+ bptr->copied_to->iinstr[bptr->copied_to->icount].dst = NULL;
+ bptr->copied_to->iinstr[bptr->copied_to->icount].target = bptr->next;
+ bptr->copied_to->icount++;
+ }
+}
+
+
+/* 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)
+{
+ instruction *ip;
+ s4 *s4ptr;
+ void **tptr;
+ int high, low, count, cnt;
+ struct LoopElement *le;
+ basicblock *new;
+
+ /* If this node has already been copied, return */
+ if (bptr->lflags & HANDLER_PART)
+ return;
+
+ /* The exception handler exists, when control flow enters loop again */
+
+ if (bptr->lflags & LOOP_PART)
+ return;
+ for (le = lc->nodes; le != NULL; le = le->next) {
+ if (le->block == bptr) {
+ printf("C_PANIC: should not happen\n");
+ exit(-1);
+ }
+ }
+
+ /* mark block as part of handler */
+ bptr->lflags |= HANDLER_PART;
+
+ /* copy node */
+ new = DMNEW(basicblock, 1);
+ memcpy(new, bptr, sizeof(basicblock));
+ new->debug_nr = c_debug_nr++;
+
+ c_last_block_copied = new;
+
+ /* 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));
+
+ /* update original block */
+ bptr->copied_to = new;
+
+ /* append block to global list of basic blocks */
+ last_block->next = new;
+ last_block = 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);
+ 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;
+
+ 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_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_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_GOTO:
+
+ /* 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);
+
+ break;
+
+ case ICMD_TABLESWITCH:
+ s4ptr = ip->val.a;
+ tptr = (void **) ip->target;
+
+ /* default branch */
+ if (((basicblock *) *tptr) == original_head)
+ tptr[0] = (void *) new_head;
+
+ copy_handler(lc, (basicblock *) *tptr, original_head, new_head);
+
+ s4ptr++;
+ low = *s4ptr;
+ s4ptr++;
+ high = *s4ptr;
+
+ count = (high-low+1);
+
+ 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;
+
+ /* default branch */
+ if (((basicblock *) *tptr) == original_head)
+ tptr[0] = (void *) new_head;
+
+ copy_handler(lc, (basicblock *) *tptr, original_head, new_head);
+
+ ++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(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_RET:
+ copy_handler(lc, c_last_target->next, original_head, new_head);
+ break;
+
+ default:
+ copy_handler(lc, bptr->next, original_head, new_head);
+ break;
+ }
+
+}
+
+
+/* If a loop is duplicated, all exceptions, that are contained in this loops' body
+ 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)
+{
+ xtable *ex, *new;
+ struct LoopContainer *l;
+
+ /* Bottom of tree reached -> return */
+ if (lc == NULL)
+ return;
+
+ /* Call update_internal for all nested (=child) loops */
+ l = lc->tree_down;
+ while (l != NULL) {
+ update_internal_exceptions(l, original_head, new_head);
+ l = l->tree_right;
+ }
+
+ /* For all exceptions of this loop, do */
+ ex = lc->exceptions;
+ while (ex != NULL) {
+
+ /* Copy the exception and patch the jumps */
+ copy_handler(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));
+
+ /* Increase number of exceptions */
+ ++exceptiontablelength;
+
+ ex->next = new;
+ ex->down = new;
+
+ /* Set new start and end point of this exception */
+ new->start = ex->start->copied_to;
+ new->end = ex->end->copied_to;
+
+ /* Set handler pointer to copied exception handler */
+ new->handler = ex->handler->copied_to;
+
+ ex = new->next;
+ }
+
+}
+
+/* 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)
+{
+ xtable *ex, *new;
+
+ /* Top of tree reached -> return */
+ if (lc == NULL)
+ return;
+
+ ex = lc->exceptions;
+
+ /* For all exceptions of this loop do */
+ while (ex != 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])) {
+
+ /* loop is really inside exception, so create new exception entry */
+ /* in global exception list */
+ new = DMNEW(xtable, 1);
+ memcpy(new, ex, sizeof(xtable));
+
+
+ /* Increase number of exceptions */
+ ++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;
+
+ ex = new->next;
+ }
+ /* exception does not contain the duplicated loop -> do nothing */
+ else
+ ex = ex->next;
+ }
+
+ /* Call update_external for parent node */
+ update_external_exceptions(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)
+{
+ int i, j, stackdepth, cnt;
+ struct Changes **c;
+ struct Constraint *tc1, *tc2;
+ struct LoopElement *le;
+
+ /* loop_head points to the newly inserted loop_head, original_start to */
+ /* the old loop header */
+ basicblock *bptr, *loop_head, *original_start, *temp;
+ instruction *inst, *tiptr;
+
+ /* tos and newstack are needed by the macros, that insert instructions into */
+ /* the new loop head */
+ stackptr newstack, tos, sptr;
+ xtable *ex;
+
+#ifdef STATISTICS
+ /* show_loop_statistics(); */
+#endif
+
+ loop_head = &block[c_current_head];
+ c_first_block_copied = c_last_block_copied = NULL;
+
+ /* the loop nodes are copied */
+ le = lc->nodes;
+ while (le != NULL)
+ {
+ bptr = DMNEW(basicblock, 1);
+ memcpy(bptr, le->block, sizeof(basicblock));
+ bptr->debug_nr = c_debug_nr++;
+
+ /* determine beginning of copied loop to extend exception handler, that */
+ /* protect this loop */
+ if (c_first_block_copied == NULL)
+ c_first_block_copied = bptr;
+
+ /* copy instructions and add one more slot for possible GOTO */
+ bptr->iinstr = DMNEW(instruction, bptr->icount + 1);
+
+ memcpy(bptr->iinstr, le->block->iinstr, (bptr->icount+1)*sizeof(instruction));
+
+ le->block->copied_to = bptr;
+
+ /* add block to global list of BBs */
+ last_block->next = bptr;
+ last_block = bptr;
+ bptr->next = NULL;
+
+ node_into_parent_loops(lc->parent, bptr);
+ le = le->next;
+ }
+
+ 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++;
+
+ /* insert the new basic block and move header before first loop node */
+ le = lc->nodes;
+ temp = le->block;
+
+ /* if header is first node of loop, insert original header after it */
+ if (temp == loop_head)
+ loop_head->next = bptr;
+ else {
+ /* else, we have to find the predecessor of loop header */
+ while (temp->next != loop_head)
+ temp = temp->next;
+
+ /* insert original header after newly created block */
+ temp->next = bptr;
+
+ /* if predecessor is not loop part, insert a goto */
+ if (!(temp->lflags & LOOP_PART)) {
+
+ /* copy instructions and add an additional slot */
+ tiptr = DMNEW(instruction, temp->icount + 1);
+ memcpy(tiptr, temp->iinstr, sizeof(instruction)*temp->icount);
+
+ temp->iinstr = tiptr;
+ tiptr = temp->iinstr + temp->icount;
+
+ /* add goto to loop header. If node is part of exception handler */
+ /* jmp is automagically redirected during patch_handler and works */
+ /* correct */
+ tiptr->opc = ICMD_GOTO;
+ tiptr->dst = NULL;
+ tiptr->target = (void*) loop_head;
+
+ ++temp->icount;
+ }
+
+
+ temp = block;
+ /* 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;
+ }
+ else {
+ loop_head->next = c_newstart;
+ c_newstart = loop_head;
+ }
+ }
+ else {
+
+ while (temp->next != le->block)
+ temp = temp->next;
+
+ loop_head->next = temp->next;
+ temp->next = loop_head;
+
+ /* to be on the safe side insert a jump from the previous instr */
+ /* over thr new inserted node */
+
+ /* special case - jump from node to loop_head: then remove */
+ /* goto / happens rather often due to loop layout */
+ tiptr = temp->iinstr + (temp->icount-1);
+
+ if ((tiptr->opc == ICMD_GOTO) && (tiptr->target == loop_head)) {
+ tiptr->opc = ICMD_NOP;
+ tiptr->dst = NULL;
+ }
+ else {
+
+ tiptr = DMNEW(instruction, temp->icount + 1);
+ memcpy(tiptr, temp->iinstr, sizeof(instruction)*temp->icount);
+
+ temp->iinstr = tiptr;
+ tiptr = temp->iinstr + temp->icount;
+
+ tiptr->opc = ICMD_GOTO;
+ tiptr->dst = NULL;
+ tiptr->target = (void*) loop_head->next;
+
+ ++temp->icount;
+ }
+ }
+ }
+
+ /* adjust exceptions */
+ ex = extable;
+ 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]))
+ ex->start = loop_head;
+ }
+
+ /* an exception that ended at the old loop header now must contains the */
+ /* new loop header as well */
+ if (ex->end == loop_head)
+ ex->end = original_start;
+
+ ex = ex->down;
+ }
+
+
+ /* insert new header node into nodelists of all enclosing loops */
+ header_into_parent_loops(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;
+
+ /* init instruction array */
+ for (cnt=0; cnt<c_needed_instr + 1; ++cnt) {
+ inst[0].opc = ICMD_NOP;
+ inst[0].dst = NULL;
+ }
+
+ loop_head->copied_to = NULL;
+
+ /* prepare stack */
+ loop_head->instack = copy_stack_from(bptr->instack);
+ loop_head->outstack = copy_stack_from(bptr->instack);
+
+ tos = loop_head->instack;
+ stackdepth = loop_head->indepth;
+
+ /* step through all inserted checks and create instructions for them */
+ for (i=0; i<maxlocals+1; ++i)
+ {
+ tc1 = c_constraints[i];
+ while (tc1 != NULL)
+ {
+ switch (tc1->type)
+ {
+
+ /* check a variable against a constant */
+ case TEST_ZERO:
+ case TEST_UNMOD_ZERO:
+
+#ifdef LOOP_DEBUG
+ printf("insert ZERO-test\n");
+ fflush(stdout);
+#endif
+
+ /* optimize if tc1->varRef >= tc1->constant */
+ LOAD_VAR(tc1->varRef);
+ LOAD_CONST(tc1->constant);
+ GOTO_NOOPT_IF_LT;
+ break;
+
+ /* check a variable against an array length */
+ case TEST_ALENGTH:
+ case TEST_UNMOD_ALENGTH:
+
+ /* optimize if */
+ /* tc1->varRef + tc1->constant < lengthOf(tc1->arrayRef) */
+#ifdef LOOP_DEBUG
+ printf("insert ALENGTH-test\n");
+ fflush(stdout);
+#endif
+
+ LOAD_VAR(tc1->varRef);
+ LOAD_CONST(tc1->constant);
+ ADD;
+ LOAD_ARRAYLENGTH(tc1->arrayRef);
+ GOTO_NOOPT_IF_GE;
+ break;
+
+ /* test right side of comparison against constant */
+ case TEST_RS_ZERO:
+
+#ifdef LOOP_DEBUG
+ printf("insert RS-ZERO-test\n");
+ fflush(stdout);
+#endif
+
+ /* optimize if right-side >= tc1->constant */
+ LOAD_RIGHT_SIDE;
+ LOAD_CONST(tc1->constant);
+ GOTO_NOOPT_IF_LT;
+ break;
+
+ /* test right side of comparison against array length */
+ case TEST_RS_ALENGTH:
+
+#ifdef LOOP_DEBUG
+ printf("insert RS-ALENGTH-test\n");
+ fflush(stdout);
+#endif
+ /* optimize if right-side < lengthOf(arrayRef) */
+ LOAD_RIGHT_SIDE;
+ LOAD_ARRAYLENGTH(tc1->arrayRef);
+ GOTO_NOOPT_IF_GT;
+ break;
+
+ /* test unmodified variable against arraylength */
+ case TEST_CONST_ALENGTH:
+
+#ifdef LOOP_DEBUG
+ printf("insert CONST ALENGTH-test\n");
+ fflush(stdout);
+#endif
+
+ /* optimize if tc1->constant < lengthOf(tc1->arrayRef) */
+ LOAD_CONST(tc1->constant);
+ LOAD_ARRAYLENGTH(tc1->arrayRef);
+ GOTO_NOOPT_IF_GE;
+ break;
+ }
+
+ tc1 = tc1->next;
+ }
+ c_constraints[i] = NULL;
+ }
+
+ /* if all tests succeed, jump to optimized loop header */
+ if (loop_head->next != original_start) {
+ inst->opc = ICMD_GOTO;
+ inst->dst = NULL;
+ inst->target = original_start;
+ }
+
+ /* redirect jumps from original loop head to newly inserted one */
+ patch_jumps(original_start, loop_head, lc);
+
+ /* 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);
+
+}
+
+
+/* This function performs an update between two arrays of struct Changes (that
+ reflect variable changes). The merge is performed unrstricted in the way, that
+ all variable changes in c1 took place in a nested loop and therefore are
+ considered to be without limit. Beside that, the merge is a simple union of the
+ changes recorded in both arrays. A variable, which limits are undefinied, is
+ 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)
+{
+ int i, changed;
+
+ if ((c1 == NULL) || (c2 == NULL))
+ printf("C_ERROR: debugging error 0x03\n");
+
+ changed = 0;
+ for (i=0; i<maxlocals; ++i) {
+ if (c1[i] == NULL) {
+ if (c2[i] != NULL) { /* a change in c2 is updated in c1 */
+ changed = 1;
+ c1[i] = c2[i];
+ c1[i]->lower_bound = c1[i]->upper_bound+1;
+ }
+ }
+ else {
+ if (c1[i]->lower_bound > c1[i]->upper_bound)
+ continue; /* variable's bounds already undefined */
+
+ if (c2[i] == NULL) { /* variable changed in c1 -> now undef. */
+ changed = 1;
+ c1[i]->lower_bound = c1[i]->upper_bound+1;
+ }
+ else {
+ if ((c1[i]->lower_bound == c2[i]->lower_bound) &&
+ (c1[i]->upper_bound == c2[i]->upper_bound))
+ continue; /* variable's bounds remain the same */
+ else {
+ changed = 1;
+ c1[i]->lower_bound = c1[i]->upper_bound+1;
+ } /* variable changed in c1 -> now undef. */
+ }
+ }
+ }
+
+ if (changed)
+ return c1;
+ else
+ return NULL;
+}
+
+/* This function performs an update between two arrays of struct Changes (that
+ reflect variable changes). The merge is a simple union of the bounds
+ changes recorded in both arrays. A variable, which limits are undefinied, is
+ 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)
+{
+ int i, changed;
+
+ if ((c1 == NULL) || (c2 == NULL))
+ printf("C_ERROR: debugging error 0x04\n");
+
+ changed = 0;
+
+ for (i=0; i<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)
+ c_mem_error();
+
+ c1[i]->lower_bound = c2[i]->lower_bound;
+ c1[i]->upper_bound = c2[i]->upper_bound;
+ changed = 1;
+ }
+ }
+ else {
+ if (c2[i] != NULL) {
+
+ if (c1[i]->lower_bound > c1[i]->upper_bound)
+ continue; /* var in c1 is unrestricted */
+
+ if (c1[i]->lower_bound > c2[i]->lower_bound) {
+ c1[i]->lower_bound = c2[i]->lower_bound;
+ changed = 1; /* write new lower bound */
+ }
+ if (c1[i]->upper_bound < c2[i]->upper_bound) {
+ c1[i]->upper_bound = c2[i]->upper_bound;
+ changed = 1; /* write new higher bound */
+ }
+ }
+ }
+ }
+
+ if (changed)
+ return c1;
+ else
+ return NULL;
+}
+
+
+/* This function simply copies an array of changes
+*/
+struct Changes** constraints_clone(struct Changes **c)
+{
+ int i;
+ struct Changes **t;
+
+ if ((t = (struct Changes **) malloc(maxlocals * sizeof(struct Changes *))) == NULL)
+ c_mem_error();
+
+ for (i=0; i<maxlocals; ++i) { /* for all array elements (vars) do */
+ if (c[i] == NULL)
+ t[i] = NULL;
+ else {
+ if ((t[i] = (struct Changes *) malloc(sizeof(struct Changes))) == NULL)
+ c_mem_error();
+ t[i]->lower_bound = c[i]->lower_bound;
+ t[i]->upper_bound = c[i]->upper_bound;
+ }
+ }
+
+ return t;
+}
+
+/* This function is used to reset the changes of a variable to the time, it was
+ pushed onto the stack. If a variable has been modified between an instruction
+ and a previous push onto the stack, its value in the changes array does not
+ 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 *tmp;
+ basicblock bp;
+ instruction *ip;
+ struct Trace *t;
+
+ if (changes == NULL) /* if there are no changes, immediately return */
+ return NULL;
+ else { /* init a Changes structure with current values */
+ if ((tmp = (struct Changes *) malloc(sizeof(struct Changes))) == NULL)
+ c_mem_error();
+
+ tmp->upper_bound = changes->upper_bound;
+ tmp->lower_bound = changes->lower_bound;
+ }
+
+ if (tmp->upper_bound < tmp->lower_bound)
+ return tmp; /* if it is unrestricted no backtracking can happen */
+
+ bp = block[node];
+ ip = bp.iinstr + to;
+
+ for (; from < to; --to, --ip) { /* scan instructions backwards */
+ switch (ip->opc) {
+ case ICMD_IINC: /* a var has been modified */
+ if (varRef != ip->op1) /* not the one, we are interested in */
+ break;
+ tmp->upper_bound -= ip->val.i; /* take back modifications */
+ tmp->lower_bound -= ip->val.i;
+ break;
+
+ case ICMD_ISTORE: /* a var has been modified */
+ if (varRef != ip->op1) /* not the one, we are interested in */
+ break;
+
+ /* it is our variable, so trace its origin */
+ t = tracing(&block[node],to, 0);
+
+ switch (t->type) {
+ case TRACE_IVAR:
+ if ((t->var = ip->op1) && (t->neg > 0)) {
+ /* it was the same var -> take back modifications */
+ tmp->upper_bound -= t->constant;
+ tmp->lower_bound -= t->constant;
+ }
+ else
+ tmp->lower_bound = tmp->upper_bound+1; /* unknown */
+ break;
+
+ /* cannot restore it -> invalidate t */
+ case TRACE_ICONST:
+ case TRACE_ALENGTH:
+ case TRACE_UNKNOWN:
+ case TRACE_AVAR:
+ tmp->lower_bound = tmp->upper_bound+1;
+ break;
+ }
+
+ break;
+ }
+ }
+ 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)
+{
+ basicblock bp;
+ instruction *ip;
+ int i, j, count, ignore, degrade_checks, opt_level;
+ struct depthElement *d;
+ struct Changes **t1, **t2, **tmp, *t;
+ struct Trace *t_array, *t_index;
+
+ /* 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 */
+
+ /* get variable changes, already recorded for this node */
+ t1 = 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])) {
+ /* we are looping in a nested loop, so made optimizations */
+ /* need to be reconsidered */
+ degrade_checks = 1;
+ if (constraints_unrestricted_merge(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)
+ 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);
+ }
+
+ /* tmp now holds a copy of the updated variable changes */
+ tmp = constraints_clone(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);
+ }
+ else
+ return;
+
+ bp = block[node]; /* scan all instructions */
+ count = bp.icount;
+ ip = bp.iinstr;
+ ignore = 0;
+
+ for (i=0; i<count; ++i, ++ip) {
+ switch (ip->opc) {
+ case ICMD_IASTORE: /* found an array store */
+ case ICMD_LASTORE:
+ case ICMD_FASTORE:
+ case ICMD_DASTORE:
+ case ICMD_AASTORE:
+ case ICMD_BASTORE:
+ case ICMD_CASTORE:
+ case ICMD_SASTORE:
+
+ t_index = tracing(&bp, i-1, 1); /* get index */
+ t_array = tracing(&bp, i-1, 2); /* get array refernce */
+ ignore = 1;
+ /* fall through */
+
+ case ICMD_IALOAD: /* found an array load */
+ case ICMD_LALOAD:
+ case ICMD_FALOAD:
+ case ICMD_DALOAD:
+ case ICMD_AALOAD:
+ case ICMD_BALOAD:
+ case ICMD_CALOAD:
+ case ICMD_SALOAD:
+ if (!ignore) {
+ t_index = tracing(&bp, i-1, 0); /* get index */
+ t_array = tracing(&bp, i-1, 1); /* get array refernce */
+ ignore = 0;
+ }
+
+ /* printf("Array access with params:\n");
+ printf("Array:\n");
+ show_trace(t_array);
+ printf("Index:\n");
+ show_trace(t_index);
+ */
+
+#ifdef STATISTICS
+ if (ip->op1 == OPT_UNCHECKED) { /* found new access */
+ c_stat_array_accesses++;
+ ip->op1 = OPT_NONE;
+ 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]))
+ 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
+ switch (ip->op1) { /* take back old optimzation */
+ case OPT_UNCHECKED:
+ break;
+ case OPT_NONE:
+ c_stat_no_opt--;
+ break;
+ case OPT_FULL:
+ c_stat_full_opt--;
+ break;
+ case OPT_UPPER:
+ c_stat_upper_opt--;
+ break;
+ case OPT_LOWER:
+ c_stat_lower_opt--;
+ break;
+ }
+#endif
+ if (degrade_checks) /* replace existing optimization */
+ ip->op1 = insert_static(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);
+ break;
+ case OPT_NONE:
+ ip->op1 = insert_static(t_array->var, t_index, NULL, special);
+ break;
+ case OPT_UPPER:
+ opt_level = insert_static(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);
+ if ((opt_level == OPT_FULL) || (opt_level == OPT_UPPER))
+ ip->op1 = OPT_FULL;
+ break;
+ case OPT_FULL:
+#ifdef STATISTICS
+ c_stat_full_opt++;
+#endif
+ break;
+ }
+ }
+ break;
+
+ case TRACE_IVAR: /* it's a variable */
+
+ /* if the variable is changed between its usage as an index */
+ /* 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
+ switch (ip->op1) { /* take back old optimzation */
+ case OPT_UNCHECKED:
+ break;
+ case OPT_NONE:
+ c_stat_no_opt--;
+ break;
+ case OPT_FULL:
+ c_stat_full_opt--;
+ break;
+ case OPT_UPPER:
+ c_stat_upper_opt--;
+ break;
+ case OPT_LOWER:
+ c_stat_lower_opt--;
+ break;
+ }
+#endif
+ if (degrade_checks)
+ ip->op1 = insert_static(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);
+ break;
+ case OPT_NONE:
+ ip->op1 = insert_static(t_array->var, t_index, t, special);
+ break;
+ case OPT_UPPER:
+ opt_level = insert_static(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);
+ if ((opt_level == OPT_FULL) || (opt_level == OPT_UPPER))
+ ip->op1 = OPT_FULL;
+ break;
+ case OPT_FULL:
+#ifdef STATISTICS
+ c_stat_full_opt++;
+#endif
+ break;
+ }
+ }
+ break;
+
+ case TRACE_UNKNOWN:
+ case TRACE_AVAR:
+ break;
+ }
+ break;
+
+ case ICMD_ISTORE: /* an integer value is stored */
+ t_index = tracing(&bp, i-1, 0); /* trace back its origin */
+
+ /* the struct Changes for this variable needs to be updated */
+ t = tmp[ip->op1];
+ if (t == NULL) { /* if it's the first one, create new entry */
+ if ((t = (struct Changes *) malloc(sizeof(struct Changes))) == NULL)
+ c_mem_error();
+ t->upper_bound = t->lower_bound = 0;
+ tmp[ip->op1] = t;
+ }
+
+ switch (t_index->type) { /* check origin of store */
+
+ case TRACE_ICONST: /* constant -> set bounds to const value */
+ t->upper_bound = t->lower_bound = t_index->constant;
+ break;
+
+ case TRACE_IVAR: /* if it's the same variable, update consts */
+ if ((t_index->var = ip->op1) && (t_index->neg > 0)) {
+ t->upper_bound += t_index->constant;
+ t->lower_bound += t_index->constant;
+ }
+ else
+ t->lower_bound = t->upper_bound+1;
+ break;
+
+ case TRACE_ALENGTH: /* else -> unknown */
+ case TRACE_UNKNOWN:
+ case TRACE_AVAR:
+ t->lower_bound = t->upper_bound+1;
+ break;
+ }
+
+ break;
+
+ case ICMD_IINC:
+
+ /* the struct Changes for this variable needs to be updated */
+ if ((t = tmp[ip->op1]) == NULL) { /* first one -> create new */
+ if ((t = (struct Changes *) malloc(sizeof(struct Changes))) == NULL)
+ c_mem_error();
+ t->upper_bound = t->lower_bound = ip->val.i;
+ tmp[ip->op1] = t;
+ }
+ else { /* update changes, made by iinc */
+ t->upper_bound += ip->val.i;
+ t->lower_bound += ip->val.i;
+ }
+ break;
+ } /* switch */
+ } /* for */
+
+ if (!special) { /* we are not interested in only the header */
+ d = c_dTable[node];
+ while (d != NULL) { /* check all sucessors of current node */
+ remove_boundchecks(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)
+{
+ remove_boundchecks(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;
+
+ while (le != NULL) {
+ le->block->lflags |= LOOP_PART;
+ le = le->next;
+ }
+}
+
+/* Clears mark for all basicblocks that are part of the loop
+*/
+void unmark_loop_nodes(struct LoopContainer *lc)
+{
+ struct LoopElement *le = lc->nodes;
+
+ while (le != NULL) {
+ le->block->lflags = 0;
+ le = le->next;
+ }
+}
+
+
+/* This function performs the analysis of code in detected loops and trys to
+ 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)
+{
+ struct LoopElement *le;
+ struct depthElement *d;
+ int i, head, node;
+ struct Changes **changes;
+
+ if ((changes = (struct Changes **) malloc(maxlocals * sizeof(struct Changes *))) == NULL)
+ c_mem_error();
+
+ head = c_current_head = lc->loop_head;
+ c_needed_instr = c_rs_needed_instr = 0;
+
+ /* init array for null ptr checks */
+ for (i=0; i<maxlocals; ++i)
+ c_null_check[i] = 0;
+
+
+ /* don't optimize root node (it is the main procedure, not a loop) */
+ if (head < 0)
+ 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)
+ d->changes = NULL;
+ }
+
+ for (i=0; i < maxlocals; ++i) {
+ c_var_modified[i] = 0;
+ if (changes[i] != NULL) {
+ changes[i] = NULL;
+ printf("C_PANIC 1\n");
+ }
+ }
+
+ for (i=0; i < (maxlocals+1); ++i) {
+ if (c_constraints[i] != NULL) {
+ c_constraints[i] = NULL;
+ printf("C_PANIC 2\n");
+ }
+ }
+
+ le = lc->nodes;
+ while (le != 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 */
+ else
+ c_current_loop[node] = 3; /* nodes, part of nested loop get 3 */
+
+ c_toVisit[node] = 1;
+ le = le->next;
+ }
+
+ /* After setup work has been performed, start to analyse */
+#ifdef LOOP_DEBUG
+ printf("****** Starting analysis (%d)******\n", head);
+ fflush(stdout);
+#endif
+
+ if (analyze_for_array_access(head) > 0) {/* loop contains array access */
+
+#ifdef LOOP_DEBUG
+ printf("analyze for array access finished and found\n");
+ fflush(stdout);
+#endif
+
+ /* 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();
+
+#ifdef LOOP_DEBUG
+ printf("global list scanned\n");
+ fflush(stdout);
+#endif
+
+ /* 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) {
+
+#ifdef LOOP_DEBUG
+ printf("Analyzed for or/exception - no problems \n");
+ fflsuh(stdout);
+#endif
+
+ init_constraints(head); /* analyze dynamic bounds in header */
+ /* show_right_side(); */
+
+ if (c_rightside == NULL)
+ return;
+
+ /* single pass bound check removal - for all successors, do */
+ remove_header_boundchecks(head, changes);
+
+ d = c_dTable[head];
+ while (d != NULL) {
+ remove_boundchecks(d->value, -1, changes, BOUNDCHECK_REGULAR);
+ d = d->next;
+ }
+
+#ifdef LOOP_DEBUG
+ printf("Array-bound checks finished\n");
+ fflsuh(stdout);
+#endif
+
+ mark_loop_nodes(lc);
+
+#ifdef LOOP_DEBUG
+ printf("START: create static checks\n");
+ fflush(stdout);
+#endif
+
+ create_static_checks(lc); /* create checks */
+
+#ifdef LOOP_DEBUG
+ printf("END: create static checks\n");
+ fflush(stdout);
+#endif
+ unmark_loop_nodes(lc);
+ }
+ }
+ /* 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;
+#endif
+
+}
+
+/* This function preforms necessary setup work, before the recursive function
+ optimize_single loop can be called.
+*/
+void optimize_loops()
+{
+ struct LoopContainer *lc = 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 */
+ /* same dynamic loop condition */
+
+#ifdef LOOP_DEBUG
+ printf("start analyze_double_headers\n");
+ fflush(stdout);
+#endif
+
+ analyze_double_headers();
+
+ /* create array with loop nesting levels - nested loops cause problems, */
+ /* especially, when they modify index variables used in surrounding loops */
+ /* store results in array c_nestedLoops and c_hierarchie */
+
+#ifdef LOOP_DEBUG
+ printf("double done\n");
+ fflush(stdout);
+#endif
+
+ analyze_nested();
+
+#ifdef LOOP_DEBUG
+ printf("analyze nested done\n");
+ fflush(stdout);
+#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);
+
+ if ((c_constraints = (struct Constraint **) malloc((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;
+#endif
+
+ /* init vars needed by all loops */
+ c_needs_redirection = false;
+ c_newstart = NULL;
+ c_old_xtablelength = exceptiontablelength;
+
+ /* loops have been topologically sorted */
+ lc = c_allLoops;
+ while (lc != NULL) {
+ optimize_single_loop(lc);
+
+#ifdef LOOP_DEBUG
+ printf(" *** Optimized loop *** \n");
+ fflush(stdout);
+#endif
+
+ lc = lc->next;
+ }
+#ifdef LOOP_DEBUG
+ printf("---*** All loops finished ***---\n");
+ fflush(stdout);
+#endif
+
+ /* if global BB list start is modified, set block to new start */
+ if (c_needs_redirection == true)
+ block = c_newstart;
+
+}
+/*
+ * These are local overrides for various environment variables in Emacs.
+ * Please do not remove this and leave it at the end of the file, where
+ * Emacs will automagically detect them.
+ * ---------------------------------------------------------------------
+ * Local variables:
+ * mode: c
+ * indent-tabs-mode: t
+ * c-basic-offset: 4
+ * tab-width: 4
+ * End:
+ */
+
+
+