1 /* src/vm/jit/loop/analyze.c - bound check removal functions
3 Copyright (C) 1996-2005, 2006, 2008
4 CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
6 This file is part of CACAO.
8 This program is free software; you can redistribute it and/or
9 modify it under the terms of the GNU General Public License as
10 published by the Free Software Foundation; either version 2, or (at
11 your option) any later version.
13 This program is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program; if not, write to the Free Software
20 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
35 #include "mm/memory.hpp"
36 #include "toolbox/logging.hpp"
38 #include "vm/jit/jit.hpp"
39 #include "vm/jit/stack.h"
41 #include "vm/jit/loop/analyze.h"
42 #include "vm/jit/loop/graph.h"
43 #include "vm/jit/loop/loop.h"
44 #include "vm/jit/loop/tracing.h"
49 /* Test functions -> will be removed in final release
52 void show_trace(struct Trace *trace)
55 switch (trace->type) {
58 printf("\nNr.:\t%d", trace->var);
59 printf("\nValue:\t%d", trace->constant);
64 printf("\nNr.:\t%d", trace->var);
68 printf("array-length");
69 printf("\nNr.:\t%d", trace->var);
70 printf("\nValue:\t%d", trace->constant);
75 printf("\nValue:\t%d", trace->constant);
84 printf("Trace is null");
90 void show_change(struct Changes *c)
92 printf("*** Changes ***\n");
94 printf("Lower/Upper Bound:\t%d/%d\n", c->lower_bound, c->upper_bound);
96 printf("Unrestricted\n");
99 show_varinfo(struct LoopVar *lv)
101 printf(" *** Loop Info ***\n");
102 printf("Value:\t%d\n", lv->value);
103 printf("Static:\t\t%d/%d\n", lv->static_l, lv->static_u);
104 printf("D-Valid:\t%d/%d\n", lv->dynamic_l_v, lv->dynamic_u_v);
105 printf("Dynamic\t\t%d/%d\n", lv->dynamic_l, lv->dynamic_u);
108 void show_right_side(methodinfo *m)
111 printf("\n *** Head *** \nType:\t");
112 show_trace(m->loopdata->c_rightside);
114 printf("\n *** Nested Loops: ***\n");
115 for (i=0; i<m->basicblockcount; ++i)
116 printf("%d\t", m->loopdata->c_nestedLoops[i]);
119 printf("\n *** Hierarchie: ***\n");
120 for (i=0; i<m->basicblockcount; ++i)
121 printf("%d\t", m->loopdata->c_hierarchie[i]);
125 printf("\n *** Current Loop ***\n");
126 for (i=0; i<m->basicblockcount; ++i)
127 printf("%d\t", m->loopdata->c_current_loop[i]);
131 void resultPass3(methodinfo *m)
134 struct LoopContainer *lc = m->loopdata->c_allLoops;
136 printf("\n\n****** PASS 3 ******\n\n");
139 printf("Loop Analysis:\n");
140 printf("Optimize:\t%d\n", lc->toOpt);
141 printf("Modified Vars: ");
143 for (i=0; i<lc->num_vars; ++i)
144 printf("%d ", lc->vars[i]);
150 printf("\nNested Loops:\n");
151 for (i=0; i<m->basicblockcount; ++i)
152 printf("%d ", m->loopdata->c_nestedLoops[i]);
154 for (i=0; i<m->basicblockcount; ++i)
155 printf("%d ", m->loopdata->c_hierarchie[i]);
160 void show_tree(struct LoopContainer *lc, int tabs)
165 for (cnt = 0; cnt < tabs; ++cnt)
167 printf("%d\n", lc->loop_head);
169 show_tree(lc->tree_down, tabs+1);
177 #ifdef ENABLE_STATISTICS
179 void show_loop_statistics(loopdata *ld)
181 printf("\n\n****** LOOP STATISTICS ****** \n\n");
183 printf("Optimization cancelled by or\n");
184 else if (ld->c_stat_exception)
185 printf("Optimization cancelled by exception\n");
187 printf("Number of array accesses:\t%d\n", ld->c_stat_array_accesses);
188 if (ld->c_stat_array_accesses) {
189 printf("\nFully optimized:\t%d\n", ld->c_stat_full_opt);
190 printf("Not optimized:\t\t%d\n", ld->c_stat_no_opt);
191 printf("Upper optimized:\t%d\n", ld->c_stat_upper_opt);
192 printf("Lower optimized:\t%d\n", ld->c_stat_lower_opt);
197 void show_procedure_statistics(loopdata *ld)
199 printf("\n\n****** PROCEDURE STATISTICS ****** \n\n");
200 printf("Number of loops:\t\t%d\n", ld->c_stat_num_loops);
201 printf("Number of array accesses:\t%d\n", ld->c_stat_sum_accesses);
202 if (ld->c_stat_sum_accesses) {
203 printf("\nFully optimized:\t%d\n", ld->c_stat_sum_full);
204 printf("Not optimized:\t\t%d\n", ld->c_stat_sum_no);
205 printf("Upper optimized:\t%d\n", ld->c_stat_sum_upper);
206 printf("Lower optimized:\t%d\n", ld->c_stat_sum_lower);
208 printf("Opt. cancelled by or:\t\t%d\n", ld->c_stat_sum_or);
209 printf("Opt. cancelled by exception:\t%d\n", ld->c_stat_sum_exception);
215 /* This function is used to merge two loops with the same header together.
216 A simple merge sort of the lists nodes of both loops is performed.
218 void analyze_merge(struct LoopContainer *l1, struct LoopContainer *l2)
220 struct LoopElement *start, *last, *le1, *le2;
221 /* start and last are pointers to the newly built list, le1 and le2 step */
222 /* step through the lists, that have to be merged. */
227 /* start a simple merge sort of the nodes of both loops. These lists are */
228 /* already sorted, so merging is easy. */
229 if (le1->node < le2->node) {
233 else if (le1->node == le2->node) {
243 /* while the first loop != NULL, depending of the first element of second */
244 /* loop, add new node to result list */
245 while (le1 != NULL) {
251 if (le1->node < le2->node) {
255 else if (le1->node == le2->node) {
272 /* This function is used to merge loops with the same header node to a single
273 one. O(n^2) of number of loops. This merginig is necessary, because the loop
274 finding algorith sometimes (eg. when loopbody ends with a if-else construct)
275 reports a single loop as two loops with the same header node.
277 void analyze_double_headers(loopdata *ld)
280 LoopContainer *t1, *t2, *t3;
284 while (t1 != NULL) { /* for all loops do */
285 toCheck = t1->loop_head; /* get header node */
288 while (t2 != NULL) { /* compare it to headers of rest */
289 if (t2->loop_head == toCheck) {
291 /* found overlapping loops -> merge them together */
292 /* printf("C_INFO: found overlapping loops - merging"); */
293 analyze_merge(t1, t2);
295 /* remove second loop from the list of all loops */
297 while (t3->next != t2)
309 /* After the hierarchie of loops has been built, we have to insert the exceptions
310 into this tree. The exception ex is inserted into the subtree pointed to by
313 void insert_exception(methodinfo *m, struct LoopContainer *lc, exceptiontable *ex)
315 struct LoopContainer *temp;
316 struct LoopElement *le;
319 /* printf("insert_exception called with %d-%d and loop %d\n", ex->start->nr, ex->end->nr, lc->loop_head); */
322 /* if child node is reached immediately insert exception into the tree */
323 if (lc->tree_down == NULL) {
324 ex->next = lc->exceptions;
328 /* if we are inside the tree, there are two possibilities: */
329 /* 1. the exception is inside a nested loop or */
330 /* 2. in the loop body of the current loop */
332 /* check all children (= nested loops) */
333 temp = lc->tree_down;
335 while (temp != NULL) {
341 printf("%d.%d\n", le->node, block_index[ex->startpc]);
343 /* if the start of the exception is part of the loop, the */
344 /* whole exception must be part of the loop */
345 if (le->node == m->basicblockindex[ex->startpc])
350 /* Exception is part of a nested loop (Case 1) -> insert it there */
352 insert_exception(m, temp, ex);
355 else if ((temp->loop_head >= m->basicblockindex[ex->startpc]) && (temp->loop_head < m->basicblockindex[ex->endpc])) {
357 /* optimization: if nested loop is part of the exception, the */
358 /* exception cannot be part of a differnet nested loop. */
359 ex->next = lc->exceptions;
364 temp = temp->tree_right;
367 /* Exception is not contained in any nested loop (Case 2) */
369 ex->next = lc->exceptions;
376 /* This function builds a loop hierarchie. The header node of the innermost loop,
377 each basic block belongs to, is stored in the array c_nestedLoops. The array
378 c_hierarchie stores the relationship between differnt loops in as follows:
379 Each loop, that is a nested loop, stores its direct surrounding loop as a
380 parent. Top level loops have no parents.
383 void analyze_nested(methodinfo *m, codegendata *cd, loopdata *ld)
385 /* i/count/tmp are counters */
386 /* toOverwrite is used while loop hierarchie is built (see below) */
387 int i, header, toOverwrite, tmp, len;
389 /* first/last are used during topological sort to build ordered loop list */
390 struct LoopContainer *first, *last, *start, *t, *temp;
392 /* Used to step through all nodes of a loop. */
393 struct LoopElement *le;
395 /* init global structures */
396 ld->c_nestedLoops = DMNEW(int, m->basicblockcount);
397 ld->c_hierarchie = DMNEW(int, m->basicblockcount);
398 for (i=0; i<m->basicblockcount; ++i) {
399 ld->c_nestedLoops[i] = -1;
400 ld->c_hierarchie[i] = -1;
403 /* if there are no optimizable loops -> return */
404 if (ld->c_allLoops == NULL)
407 temp = ld->c_allLoops;
408 while (temp != NULL) { /* for all loops, do */
409 header = temp->loop_head;
411 /* toOverwrite is number of current parent loop (-1 if none) */
412 toOverwrite = ld->c_nestedLoops[header];
414 ld->c_hierarchie[header] = toOverwrite;
416 if (toOverwrite == header) /* check for loops with same header */
417 printf("C_ERROR: Loops have same header\n");
420 while (le != NULL) { /* for all loop nodes, do */
421 tmp = ld->c_nestedLoops[le->node];
423 /* if node is part of parent loop -> overwrite it with nested */
424 if (tmp == toOverwrite)
425 ld->c_nestedLoops[le->node] = header;
427 ld->c_hierarchie[tmp] = header;
429 /* printf("set head of %d to %d", tmp, header); */
439 /* init root of hierarchie tree */
440 ld->root = DMNEW(struct LoopContainer, 1);
441 LoopContainerInit(m, ld->root, -1);
443 /* obtain parent pointer and build hierarchie tree */
444 start = ld->c_allLoops;
445 while (start != NULL) {
447 /* look for parent of loop pointed at by start */
448 first = ld->c_allLoops;
449 while (first != NULL) {
451 /* the parent of the loop, pointed at by start has been found */
452 if (first->loop_head == ld->c_hierarchie[start->loop_head]) {
454 /* printf("set parent to pointer\n"); */
457 start->parent = first;
458 start->tree_right = first->tree_down;
459 first->tree_down = start;
466 /* no parent loop found, set parent to root */
469 /* printf("set parent to root\n"); */
472 start->parent = ld->root;
473 start->tree_right = ld->root->tree_down;
474 ld->root->tree_down = start;
476 /* if a parent exists, increase this nodes indegree */
478 start->parent->in_degree += 1;
483 /* insert exceptions into tree */
485 printf("--- Showing tree ---\n");
486 show_tree(ld->root, 0);
487 printf(" --- End ---\n");
489 for (len = 0; len < jd->exceptiontablelength; ++len)
490 insert_exception(m, ld->root, jd->exceptiontable + len);
493 /* determine sequence of loops for optimization by topological sort */
497 temp = ld->c_allLoops;
498 while (temp != NULL) {
500 /* a loops with indegree == 0 are pushed onto the stack */
501 if (temp->in_degree == 0) {
513 first = last = start;
517 printf("C_ERROR: loops are looped\n");
521 /* pop each node from the stack and decrease its parents indegree by one */
522 /* when the parents indegree reaches zero, push it onto the stack as well */
523 if ((last->parent != ld->root) && (--last->parent->in_degree == 0)) {
524 last->parent->next = start;
525 start = last->parent;
527 while (start != NULL) {
534 if ((last->parent != ld->root) && (--last->parent->in_degree == 0)) {
535 last->parent->next = start;
536 start = last->parent;
541 ld->c_allLoops = first;
544 printf("*** Hierarchie Results \n");
545 while (first != NULL) {
546 printf("%d ", first->loop_head);
555 /* This function is used to add variables that occur as index variables in
556 array accesses (ARRAY_INDEX) or as variables, that change their value (VAR_MOD)
557 to the list of interesting vars (c_loopvars) for the current loop.
560 void add_to_vars(loopdata *ld, int var, int type, int direction)
564 /* printf("Added to vars %d %d %d\n", var, type, direction); */
566 while (lv != NULL) { /* check if var has been previously added */
567 if (lv->value == var) {
568 if (type == ARRAY_INDEX)
569 lv->index = 1; /* var is used as index */
570 else if (type == VAR_MOD) {
571 lv->modified = 1; /* var is used in assignment */
572 switch (direction) { /* how was var modified ? */
574 lv->static_u = 0; /* incremented, no static upper */
575 break; /* bound can be guaranteeed */
577 lv->static_l = 0; /* decremented, no static lower */
578 break; /* bound can be guaranteeed */
580 lv->static_u = lv->static_l = 0;
581 break; /* no info at all */
583 printf("C_ERROR: unknown direction\n");
592 /* variable is not found in list -> add variable to list */
593 lv = DNEW(struct LoopVar);
595 lv->modified = lv->index = 0;
598 if (type == ARRAY_INDEX) {
600 lv->static_u = lv->static_l = 1; /* arrayindex -> var not modified */
602 else if (type == VAR_MOD) {
604 switch (direction) { /* var used in assignment -> set */
605 case D_UP: /* proper static bounds */
606 lv->static_u = 0; lv->static_l = 1;
609 lv->static_u = 1; lv->static_l = 0;
612 lv->static_u = lv->static_l = 0;
615 printf("C_ERROR: unknown direction\n");
620 /* no dynamic bounds have been determined so far */
621 lv->dynamic_l = lv->dynamic_l_v = lv->dynamic_u = lv->dynamic_u_v = 0;
623 lv->next = ld->c_loopvars; /* add var to list */
628 /* This function checks, whether a given loop with header node contains array
629 accesses. If so, it returns 1, else it returns 0 and the loops needs no
630 further consideration in the optimization process. When array accesses are
631 found, a list of all variables, that are used as array index, is built and
632 stored in c_loopvars. For all variables (integer), which values are changed,
633 a flag in c_var_modified is set.
636 int analyze_for_array_access(methodinfo *m, loopdata *ld, int node)
641 struct depthElement *d;
644 if (ld->c_toVisit[node] > 0) { /* node has not been visited yet */
645 ld->c_toVisit[node] = 0;
647 bp = m->basicblocks[node]; /* prepare an instruction scan */
651 access = 0; /* number of array accesses in loop */
653 for (i=0; i<ic; ++i, ++ip) { /* for each instruction, check opcode */
655 case ICMD_IASTORE: /* array store */
663 t = tracing(&bp, i-1, 1); /* try to identify index variable */
665 if (t->type == TRACE_IVAR) {
666 /* if it is a variable, add it to list of index variables */
667 add_to_vars(ld, t->var, ARRAY_INDEX, D_UNKNOWN);
670 else if (t->type == TRACE_ICONST)
674 case ICMD_IALOAD: /* array load */
682 t = tracing(&bp, i-1, 0); /* try to identify index variable */
684 if (t->type == TRACE_IVAR) {
685 /* if it is a variable, add it to list of index variables */
686 add_to_vars(ld, t->var, ARRAY_INDEX, D_UNKNOWN);
689 else if (t->type == TRACE_ICONST)
693 case ICMD_ISTORE: /* integer store */
694 ld->c_var_modified[ip->op1] = 1;
696 /* try to find out, how it was modified */
697 t = tracing(&bp, i-1, 0);
698 if (t->type == TRACE_IVAR) {
699 if ((t->constant > 0) && (t->var == ip->op1))
700 /* a constant was added to the same var */
701 add_to_vars(ld, t->var, VAR_MOD, D_UP);
702 else if (t->var == ip->op1)
703 /* a constant was subtracted from the same var */
704 add_to_vars(ld, t->var, VAR_MOD, D_DOWN);
706 add_to_vars(ld, t->var, VAR_MOD, D_UNKNOWN);
709 add_to_vars(ld, ip->op1, VAR_MOD, D_UNKNOWN);
712 case ICMD_IINC: /* simple add/sub of a constant */
713 ld->c_var_modified[ip->op1] = 1;
716 add_to_vars(ld, ip->op1, VAR_MOD, D_UP);
718 add_to_vars(ld, ip->op1, VAR_MOD, D_DOWN);
725 ld->c_var_modified[ip->op1] = 1;
730 d = ld->c_dTable[node];
731 while (d != NULL) { /* check all successors of block */
732 access += analyze_for_array_access(m, ld, d->value);
743 /* This function scans the exception graph structure to find modifications of
744 array index variables of the current loop. If any modifications are found,
745 1 is returned, else 0.
748 int quick_scan(methodinfo *m, loopdata *ld, int node)
754 struct depthElement *d;
756 /* printf("QS: %d - %d\n", node, ld->c_exceptionVisit[node]); */
759 if (ld->c_exceptionVisit[node] > 0) { /* node is part of exception graph */
760 ld->c_exceptionVisit[node] = -1;
762 bp = m->basicblocks[node]; /* setup scan of all instructions */
766 for (i=0; i<count; ++i, ++ip) { /* for each instruction do */
769 case ICMD_IINC: /* a variable is modified */
771 lv = ld->c_loopvars; /* is it an array index var ? */
773 if ((lv->index) && (lv->value == ip->op1))
774 return 1; /* yes, so return 1 */
781 d = ld->c_exceptionGraph[node]; /* check all successor nodes */
783 if (quick_scan(m, ld, d->value) > 0)
784 return 1; /* if an access is found return 1 */
788 return 0; /* nothing found, so return 0 */
795 /* This function returns 1, when the condition of the loop contains
796 or statements or when an array index variable is modified in any
797 catch block within the loop.
800 int analyze_or_exceptions(methodinfo *m, codegendata *cd, loopdata *ld, int head, struct LoopContainer *lc)
802 struct depthElement *d;
803 int i, k, value, flag, count;
804 struct LoopElement *le;
806 d = ld->c_dTable[head];
809 /* analyze for or-statements */
811 printf("*** Analyze for OR ... ");
815 while (d != NULL) { /* for all successor nodes check if they */
816 value = d->value; /* are part of the loop */
821 if (le->node == value)
826 if (le == NULL) /* node is not part of the loop */
833 if ((count > 1) && (flag == 0)){/* if all successors part of the loop, exit */
834 #ifdef ENABLE_STATISTICS
840 /* check for exceptions */
841 /* printf("done\n*** Analyze for EXCEPTIONS(%d) . ", jd->exceptiontablelength); */
843 if (!jd->exceptiontablelength) /* when there are no exceptions, exit */
846 if ((ld->c_exceptionGraph = (struct depthElement **) malloc(sizeof(struct depthElement *) * m->basicblockcount)) == NULL)
848 if ((ld->c_exceptionVisit = (int *) malloc(sizeof(int) * m->basicblockcount)) == NULL)
851 for (k=0; k<m->basicblockcount; ++k) {
852 ld->c_exceptionVisit[k] = -1;
853 ld->c_exceptionGraph[k] = NULL;
857 /* for all nodes that start catch block check whether they are part of loop */
858 for (i = 0; i < ld->c_old_xtablelength; i++) {
859 value = m->basicblockindex[jd->exceptiontable[i].startpc];
864 if (le->node == value) { /* exception is in loop */
866 printf("C_INFO: Loop contains exception\n");
870 /* build a graph structure, that contains all nodes that are */
871 /* part of the catc block */
872 dF_Exception(m, ld, -1, m->basicblockindex[jd->exceptiontable[i].handlerpc]);
874 /* if array index variables are modified there, return 0 */
875 if (quick_scan(m, ld, m->basicblockindex[jd->exceptiontable[i].handlerpc]) > 0) {
876 #ifdef ENABLE_STATISTICS
877 ld->c_stat_exception++;
879 /* printf("C_INFO: loopVar modified in exception\n"); */
888 printf("none ... done\n");
895 /* This function sets a flag in c_var_modified for all variables that have
896 been found as part of an assigment in the loop.
899 void scan_global_list(loopdata *ld)
906 ld->c_var_modified[lv->value] = 1;
912 /* This function analyses the condition in the loop header and trys to find
913 out, whether some dynamic guarantees can be set up.
916 void init_constraints(methodinfo *m, loopdata *ld, int head)
920 int ic, l_mod, r_mod, changed, operand;
921 struct Trace *left, *right, *th;
922 struct LoopVar *lv_left, *lv_right, *lh;
924 /* prevent some compiler warnings */
930 bp = m->basicblocks[head];
932 ip = bp.iinstr+(ic-1); /* set ip to last instruction in header node */
934 switch (ip->opc) { /* check op-code */
936 /* comparison against constant value */
937 case ICMD_IFEQ: /* ..., value ==> ... */
938 case ICMD_IFLT: /* ..., value ==> ... */
939 case ICMD_IFLE: /* ..., value ==> ... */
940 case ICMD_IFGT: /* ..., value ==> ... */
941 case ICMD_IFGE: /* ..., value ==> ... */
942 /* op1 = target JavaVM pc, val.i = constant */
944 left = tracing(&bp, ic-2, 0); /* analyse left arg., right is constant */
945 right = create_trace(TRACE_ICONST, -1, ip->val.i, 0);
948 /* standard comparison */
949 case ICMD_IF_ICMPEQ: /* ..., value, value ==> ... */
950 case ICMD_IF_ICMPLT: /* ..., value, value ==> ... */
951 case ICMD_IF_ICMPGT: /* ..., value, value ==> ... */
952 case ICMD_IF_ICMPLE: /* ..., value, value ==> ... */
953 case ICMD_IF_ICMPGE: /* ..., value, value ==> ... */
955 left = tracing(&bp, ic-2, 1); /* get left and right argument */
956 right = tracing(&bp, ic-2, 0);
959 /* other condition */
961 left = create_trace(TRACE_UNKNOWN, -1, 0, 0);
962 right = create_trace(TRACE_UNKNOWN, -1, 0, 0);
966 /* analyse left and right side of comparison */
969 if (left->type == TRACE_IVAR) { /* is a loop variable on left side ? */
970 lv_left = ld->c_loopvars;
971 while (lv_left != NULL) {
972 if (lv_left->value == left->var) {
973 l_mod = lv_left->modified; /* yes, but has it been modified ? */
976 lv_left = lv_left->next;
980 if (right->type == TRACE_IVAR){ /* is a loop variable on right side ? */
981 lv_right = ld->c_loopvars;
982 while (lv_right != NULL) {
983 if (lv_right->value == right->var) {
984 r_mod = lv_right->modified; /* yes, but has it been modified ? */
987 lv_right = lv_right->next;
991 if ((l_mod - r_mod) == 0) { /* both 1 or both 0 -> no dynamic contraints*/
992 ld->c_rightside = NULL; /* possible */
996 /* to simplify processing, make the left side the one, that contains the */
997 /* modified variable */
999 th = left; left = right; right = th;
1000 lh = lv_left; lv_left = lv_right; lv_right = lh;
1001 changed = 1; /* set changed to true */
1004 changed = 0; /* no change needed */
1006 /* make sure that right side's value does not change during loop execution */
1007 if (right->type == TRACE_UNKNOWN) {
1008 ld->c_rightside = NULL;
1012 /* determine operands: */
1013 /* for further explaination a is modified, b nonmodified var */
1014 switch (ip->opc) { /* check opcode again */
1015 case ICMD_IFEQ: /* ..., value ==> ... */
1016 case ICMD_IF_ICMPEQ: /* ..., value, value ==> ... */
1017 operand = OP_EQ; /* a == b */
1020 case ICMD_IFLE: /* ..., value ==> ... */
1021 case ICMD_IF_ICMPLE: /* ..., value, value ==> ... */
1023 operand = OP_GE; /* b<=a -> a>=b */
1025 operand = OP_LT; /* a<=b -> a<(b+1) */
1026 if (left->constant != 0)
1027 left->constant -= 1;
1029 right->constant += 1;
1033 case ICMD_IFLT: /* ..., value ==> ... */
1034 case ICMD_IF_ICMPLT: /* ..., value, value ==> ... */
1036 operand = OP_GE; /* b<a -> a>=(b+1) */
1037 if (left->constant != 0)
1038 left->constant -= 1;
1040 right->constant += 1;
1043 operand = OP_LT; /* a<b -> a<b */
1046 case ICMD_IFGT: /* ..., value ==> ... */
1047 case ICMD_IF_ICMPGT: /* ..., value, value ==> ... */
1049 operand = OP_LT; /* b>a -> a<b */
1051 operand = OP_GE; /* a>b -> a>=(b+1) */
1052 if (left->constant != 0)
1053 left->constant -= 1;
1055 right->constant += 1;
1059 case ICMD_IFGE: /* ..., value ==> ... */
1060 case ICMD_IF_ICMPGE: /* ..., value, value ==> ... */
1062 operand = OP_LT; /* b>=a -> a<(b+1) */
1063 if (left->constant != 0)
1064 left->constant -= 1;
1066 right->constant += 1;
1069 operand = OP_GE; /* a>=b -> a>=b */
1073 printf("C_ERROR: debugging error 0x00\n");
1077 /* NOW: left/lv_left -> loopVar */
1078 /* right/lv_right -> const, nonmod. var, arraylength */
1079 switch (operand) { /* check operand */
1081 lv_left->dynamic_u_v = 1; /* upper + lower bound tested */
1082 lv_left->dynamic_l_v = 1;
1084 lv_left->dynamic_l = lv_left->dynamic_u = left->constant;
1088 lv_left->dynamic_u_v = 1; /* upper bound tested */
1090 lv_left->dynamic_u = left->constant;
1094 lv_left->dynamic_l_v = 1; /* lower bound tested */
1096 lv_left->dynamic_l = left->constant;
1100 printf("C_ERROR: debugging error 0x01\n");
1103 ld->c_rightside = right;
1105 switch (ld->c_rightside->type) {
1107 ld->c_rs_needed_instr = 1;
1110 ld->c_rs_needed_instr = 2;
1113 ld->c_rs_needed_instr = 3;
1116 printf("C_ERROR: wrong right-side type\n");
1121 /* This function is needed to add and record new static tests (before loop
1122 entry) of variables to make guaratees for index variables. type states
1123 the kind of the test. arrayRef is the array, which length is tested
1124 against, varRef is the variable, that is testes and constant is the
1125 constant value, that is tested.
1128 void add_new_constraint(methodinfo *m, codegendata *cd, loopdata *ld, int type, int arrayRef, int varRef, int constant)
1130 struct Constraint *tc;
1133 case TEST_ZERO: /* a variable is tested against a const */
1135 tc = ld->c_constraints[varRef]; /* does a test already exist for this var ? */
1136 while (tc != NULL) {
1137 if (tc->type == TEST_ZERO) {
1138 if (constant < tc->constant)
1139 tc->constant = constant;
1140 return; /* yes. update constant and return */
1145 /* insert a new test for this variable */
1146 if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
1148 tc->type = TEST_ZERO;
1149 tc->varRef = varRef;
1150 tc->constant = constant;
1151 tc->next = ld->c_constraints[varRef];
1152 ld->c_constraints[varRef] = tc;
1153 ld->c_needed_instr += 3;
1157 case TEST_ALENGTH: /* variable is tested against array length */
1159 tc = ld->c_constraints[varRef]; /* does a test already exist for this var ? */
1160 while (tc != NULL) {
1161 if ((tc->type == TEST_ALENGTH) && (tc->arrayRef == arrayRef)) {
1162 if (constant > tc->constant)
1163 tc->constant = constant;
1164 return; /* yes. update constant and return */
1169 /* insert a new test for this variable */
1170 if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
1172 tc->type = TEST_ALENGTH;
1173 tc->arrayRef = arrayRef;
1174 tc->varRef = varRef;
1175 tc->constant = constant;
1176 tc->next = ld->c_constraints[varRef];
1177 ld->c_constraints[varRef] = tc;
1178 ld->c_needed_instr += 6;
1180 /* if arrayRef is not already tested against null, insert that test */
1181 if (!(ld->c_null_check[arrayRef])) {
1182 ld->c_null_check[arrayRef] = 1;
1183 ld->c_needed_instr +=2;
1188 case TEST_CONST_ZERO:
1192 case TEST_CONST_ALENGTH: /* a const is tested against array length */
1194 /* does a test already exist for this array */
1195 tc = ld->c_constraints[jd->maxlocals];
1196 while (tc != NULL) {
1197 if ((tc->type == TEST_CONST_ALENGTH) && (tc->arrayRef == arrayRef)) {
1198 if (constant > tc->constant)
1199 tc->constant = constant;
1200 return; /* yes. update constant and return */
1205 /* insert a new test for this array */
1206 if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
1208 tc->type = TEST_CONST_ALENGTH;
1209 tc->arrayRef = arrayRef;
1210 tc->constant = constant;
1211 tc->next = ld->c_constraints[jd->maxlocals];
1212 ld->c_constraints[jd->maxlocals] = tc;
1213 ld->c_needed_instr += 4;
1215 /* if arrayRef is not already tested against null, insert that test */
1216 if (!(ld->c_null_check[arrayRef])) {
1217 ld->c_null_check[arrayRef] = 1;
1218 ld->c_needed_instr +=2;
1223 case TEST_UNMOD_ZERO: /* test unmodified var against constant */
1225 /* search if test already exists */
1226 tc = ld->c_constraints[varRef];
1227 while (tc != NULL) {
1228 if (tc->type == TEST_UNMOD_ZERO) {
1229 if (constant < tc->constant)
1230 tc->constant = constant;
1231 return; /* yes, so update constant */
1236 /* else, a new test is inserted */
1237 if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
1239 tc->type = TEST_UNMOD_ZERO;
1240 tc->varRef = varRef;
1241 tc->constant = constant;
1242 tc->next = ld->c_constraints[varRef];
1243 ld->c_constraints[varRef] = tc;
1244 ld->c_needed_instr += 3;
1248 case TEST_UNMOD_ALENGTH: /* test unmodified var against array length */
1250 /* search if test alreay exists */
1251 tc = ld->c_constraints[varRef];
1252 while (tc != NULL) {
1253 if ((tc->type == TEST_UNMOD_ALENGTH) && (tc->arrayRef == arrayRef)) {
1254 if (constant > tc->constant)
1255 tc->constant = constant;
1256 return; /* yes, so modify constants */
1261 /* create new entry */
1262 if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
1264 tc->type = TEST_UNMOD_ALENGTH;
1265 tc->varRef = varRef;
1266 tc->arrayRef = arrayRef;
1267 tc->constant = constant;
1268 tc->next = ld->c_constraints[varRef];
1269 ld->c_constraints[varRef] = tc;
1270 ld->c_needed_instr += 6;
1272 /* if arrayRef is not already tested against null, insert that test */
1273 if (!(ld->c_null_check[arrayRef])) {
1274 ld->c_null_check[arrayRef] = 1;
1275 ld->c_needed_instr +=2;
1280 case TEST_RS_ZERO: /* test right side of the loop condition */
1281 /* against a constant - needed by dynamic */
1283 /*!! varRef -> maxlocals */
1284 /* search if test already exists */
1285 tc = ld->c_constraints[jd->maxlocals];
1286 while (tc != NULL) {
1287 if (tc->type == TEST_RS_ZERO) {
1288 if (constant < tc->constant)
1289 tc->constant = constant;
1290 return; /* yes, so modify constants */
1295 /* create new entry */
1296 if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
1298 tc->type = TEST_RS_ZERO;
1299 tc->constant = constant;
1300 tc->next = ld->c_constraints[jd->maxlocals];
1301 ld->c_constraints[jd->maxlocals] = tc;
1302 ld->c_needed_instr += (2 + ld->c_rs_needed_instr);
1304 /* if arrayRef on right side is not already tested against null, */
1305 /* insert that test */
1306 if ((ld->c_rightside->type == TRACE_ALENGTH) && (!(ld->c_null_check[ld->c_rightside->var]))) {
1307 ld->c_null_check[ld->c_rightside->var] = 1;
1308 ld->c_needed_instr +=2;
1313 case TEST_RS_ALENGTH: /* test right side of the loop condition */
1314 /* against array length - needed by dynamic */
1316 /*!! varRef -> maxlocals */
1317 /* search if test already exists */
1318 tc = ld->c_constraints[jd->maxlocals];
1321 if ((tc->type == TEST_RS_ALENGTH) && (tc->arrayRef == arrayRef))
1323 if (constant > tc->constant)
1324 tc->constant = constant;
1325 return; /* yes, so modify constants */
1330 /* create new entry */
1331 if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
1333 tc->type = TEST_RS_ALENGTH;
1334 tc->arrayRef = arrayRef;
1335 tc->constant = constant;
1336 tc->next = ld->c_constraints[jd->maxlocals];
1337 ld->c_constraints[jd->maxlocals] = tc;
1338 ld->c_needed_instr += (3 + ld->c_rs_needed_instr);
1340 /* if arrayRef is not already tested against null, insert that test */
1341 if (!(ld->c_null_check[arrayRef])) {
1342 ld->c_null_check[arrayRef] = 1;
1343 ld->c_needed_instr +=2;
1346 /* if arrayRef on right side is not already tested against null, */
1347 /* insert that test */
1348 if ((ld->c_rightside->type == TRACE_ALENGTH) && (!(ld->c_null_check[ld->c_rightside->var]))) {
1349 ld->c_null_check[ld->c_rightside->var] = 1;
1350 ld->c_needed_instr +=2;
1358 /* This functions adds new static (before loop enry) tests of variables to the
1359 program to be able to guarantee certain values for index variables in array
1360 access (to safely remove bound checks).
1363 int insert_static(methodinfo *m, codegendata *cd, loopdata *ld, int arrayRef, struct Trace *index, struct Changes *varChanges, int special)
1369 /* printf("insert static check - %d\n", arrayRef);
1371 show_change(varChanges);
1374 if (varChanges == NULL) { /* the variable hasn't changed / const */
1375 if ((varChanges = (struct Changes *) malloc(sizeof(struct Changes))) == NULL)
1377 varChanges->lower_bound = varChanges->upper_bound = 0;
1380 switch (index->type) { /* check index type */
1381 case TRACE_IVAR: /* it is a variable */
1382 if (index->neg < 0) { /* if it's a negated var, return */
1383 #ifdef ENABLE_STATISTICS
1384 ld->c_stat_no_opt++;
1389 varRef = index->var;
1392 if (ld->c_var_modified[varRef]) { /* volatile var */
1394 lv = ld->c_loopvars; /* get reference to loop variable */
1396 while ((lv != NULL) && (lv->value != varRef))
1399 printf("C_ERROR: debugging error 0x02\n");
1401 /* show_varinfo(lv); */
1403 /* check existing static bounds and add new contraints on variable */
1404 /* to possibly remove bound checks */
1406 /* the var is never decremented, so we add a static test againt */
1408 if (varChanges->lower_bound > varChanges->upper_bound)
1409 add_new_constraint(m, cd, ld, TEST_ZERO, arrayRef, varRef, index->constant);
1411 add_new_constraint(m, cd, ld, TEST_ZERO, arrayRef, varRef, varChanges->lower_bound+index->constant);
1414 else if ((lv->dynamic_l_v) && (!special)) {
1415 /* the variable is decremented, but it is checked against a */
1416 /* bound in the loop condition */
1417 if (varChanges->lower_bound <= varChanges->upper_bound) {
1418 add_new_constraint(m, cd, ld, TEST_RS_ZERO, arrayRef, varRef, varChanges->lower_bound+index->constant+lv->dynamic_l);
1424 /* the var is never incremented, so we add a static test againt */
1426 if (varChanges->lower_bound > varChanges->upper_bound)
1427 add_new_constraint(m, cd, ld, TEST_ALENGTH, arrayRef, varRef, index->constant);
1429 add_new_constraint(m, cd, ld, TEST_ALENGTH, arrayRef, varRef, varChanges->upper_bound+index->constant);
1432 else if ((lv->dynamic_u_v) && (!special)) {
1433 /* the variable is decremented, but it is checked against a */
1434 /* bound in the loop condition */
1435 if (varChanges->lower_bound <= varChanges->upper_bound) {
1436 add_new_constraint(m, cd, ld, TEST_RS_ALENGTH, arrayRef, varRef, varChanges->upper_bound+index->constant+lv->dynamic_u);
1441 else { /* the var is never modified at all */
1442 add_new_constraint(m, cd, ld, TEST_UNMOD_ZERO, arrayRef, index->var, index->constant);
1443 add_new_constraint(m, cd, ld, TEST_UNMOD_ALENGTH, arrayRef, index->var, index->constant);
1447 /* if the addition of new variable tests made guarantees possible, */
1448 /* return the best possible optimization */
1449 if ((high > 0) && (low > 0)) {
1450 /* printf("fully optimzed\n"); */
1451 #ifdef ENABLE_STATISTICS
1452 ld->c_stat_full_opt++;
1456 else if (high > 0) {
1457 /* printf("upper optimzed\n"); */
1458 #ifdef ENABLE_STATISTICS
1459 ld->c_stat_upper_opt++;
1464 /* printf("lower optimzed\n"); */
1465 #ifdef ENABLE_STATISTICS
1466 ld->c_stat_lower_opt++;
1471 /* printf("not optimzed\n"); */
1472 #ifdef ENABLE_STATISTICS
1473 ld->c_stat_no_opt++;
1479 case TRACE_ICONST: /* if it is a constant, optimization is easy */
1480 if (index->constant < 0) {
1481 #ifdef ENABLE_STATISTICS
1482 ld->c_stat_no_opt++;
1484 return OPT_NONE; /* negative index -> bad */
1487 add_new_constraint(m, cd, ld, TEST_CONST_ALENGTH, arrayRef, 0, index->constant);
1488 #ifdef ENABLE_STATISTICS
1489 ld->c_stat_full_opt++;
1491 return OPT_FULL; /* else just test constant against array length */
1495 case TRACE_ALENGTH: /* else, no optimizations possible */
1498 #ifdef ENABLE_STATISTICS
1499 ld->c_stat_no_opt++;
1504 /* keep compiler happy */
1510 /* copy a stack and return the start pointer of the newly created one
1512 stackelement_t* copy_stack_from(stackelement_t* source) {
1513 stackelement_t* current, top;
1518 /* copy first element */
1519 current = DMNEW(stackelement, 1);
1520 current->type = source->type;
1521 current->flags = source->flags;
1522 current->varkind = source->varkind;
1523 current->varnum = source->varnum;
1524 current->regoff = source->regoff;
1528 /* if there exist more, then copy the rest */
1529 while (source->prev != NULL) {
1530 source = source->prev;
1531 current->prev = DMNEW(stackelement, 1);
1532 current->type = source->type;
1533 current->flags = source->flags;
1534 current->varkind = source->varkind;
1535 current->varnum = source->varnum;
1536 current->regoff = source->regoff;
1537 current = current->prev;
1540 current->prev = NULL;
1545 /* The following defines are used in the procedure void create_static_checks(...)
1546 They add a new instruction with its corresponding stack manipulation and
1547 are used to build the new loop header of an optimized loop, where we have
1548 to check certain variables and constants against values to guarantee that
1549 index values in array accesses remain with array bounds.
1551 inst: pointer to the new instruction
1552 tos: stackpointer before this operation is executed
1553 newstack: temporary stackelement_t*
1554 stackdepth: counts the current stackdepth
1555 original start: blockpointer to the head of the new, optimized loop
1558 /* Load a local integer variable v */
1559 #define LOAD_VAR(v) { \
1560 inst->opc = ICMD_ILOAD; \
1562 newstack = DMNEW(stackelement, 1); \
1563 inst->dst = newstack; \
1564 newstack->prev = tos; \
1565 newstack->type = TYPE_INT; \
1566 newstack->flags = 0; \
1567 newstack->varkind = LOCALVAR; \
1568 newstack->varnum = v; \
1574 /* Load a constant with value c */
1575 #define LOAD_CONST(c) { \
1576 inst->opc = ICMD_ICONST; \
1578 inst->val.i = (c); \
1579 newstack = DMNEW(stackelement, 1); \
1580 newstack->prev = tos; \
1581 newstack->type = TYPE_INT; \
1582 newstack->flags = 0; \
1583 newstack->varkind = UNDEFVAR; \
1584 newstack->varnum = stackdepth; \
1591 /* Load a local reference (adress) variable a */
1592 #define LOAD_ADDR(a) { \
1593 inst->opc = ICMD_ALOAD; \
1595 newstack = DMNEW(stackelement, 1); \
1596 newstack->prev = tos; \
1597 newstack->type = TYPE_ADR; \
1598 newstack->flags = 0; \
1599 newstack->varkind = LOCALVAR; \
1600 newstack->varnum = a; \
1607 /* Insert a compare greater-or-equal and jump to the unoptimized loop, if the */
1608 /* comparison is true */
1609 #define GOTO_NOOPT_IF_GE { \
1610 inst->opc = ICMD_IF_ICMPGE; \
1611 inst->target = original_start->copied_to; \
1612 if (tos->varkind == UNDEFVAR) \
1613 tos->varkind = TEMPVAR; \
1615 if (tos->varkind == UNDEFVAR) \
1616 tos->varkind = TEMPVAR; \
1623 /* Insert a compare greater than and jump to the unoptimized loop, if the */
1624 /* comparison is true */
1625 #define GOTO_NOOPT_IF_GT { \
1626 inst->opc = ICMD_IF_ICMPGT; \
1627 inst->target = original_start->copied_to; \
1628 if (tos->varkind == UNDEFVAR) \
1629 tos->varkind = TEMPVAR; \
1631 if (tos->varkind == UNDEFVAR) \
1632 tos->varkind = TEMPVAR; \
1640 /* Insert a compare less-than and jump to the unoptimized loop, if the */
1641 /* comparison is true */
1642 #define GOTO_NOOPT_IF_LT { \
1643 inst->opc = ICMD_IF_ICMPLT; \
1644 inst->target = original_start->copied_to; \
1645 if(tos->varkind == UNDEFVAR) \
1646 tos->varkind = TEMPVAR; \
1648 if(tos->varkind == UNDEFVAR) \
1649 tos->varkind = TEMPVAR; \
1656 /* Insert a compare if-not-null and jump to the unoptimized loop, if the */
1657 /* comparison is true */
1658 #define GOTO_NOOPT_IF_NULL { \
1659 inst->opc = ICMD_IFNULL; \
1660 inst->target = original_start->copied_to; \
1661 if(tos->varkind == UNDEFVAR) \
1662 tos->varkind = TEMPVAR; \
1669 /* Insert an add instruction, that adds two integer values on top of the stack */
1672 inst->opc = ICMD_IADD; \
1673 if(tos->varkind == UNDEFVAR) \
1674 tos->varkind = TEMPVAR; \
1676 if(tos->varkind == UNDEFVAR) \
1677 tos->varkind = TEMPVAR; \
1679 newstack = DMNEW(stackelement, 1); \
1680 newstack->prev = tos; \
1681 newstack->type = TYPE_INT; \
1682 newstack->flags = 0; \
1683 newstack->varkind = UNDEFVAR; \
1684 newstack->varnum = stackdepth; \
1691 /* Insert instructions to load the arraylength of an array with reference a */
1692 /* fisrt, the reference must be loaded, then a null-pointer check is inserted */
1693 /* if not already done earlier. Finally an arraylength instruction is added */
1694 #define LOAD_ARRAYLENGTH(a) { \
1695 if (ld->c_null_check[a]) { \
1697 GOTO_NOOPT_IF_NULL; \
1698 ld->c_null_check[a] = 0; \
1701 inst->opc = ICMD_ARRAYLENGTH; \
1702 if(tos->varkind == UNDEFVAR) \
1703 tos->varkind = TEMPVAR; \
1705 newstack = DMNEW(stackelement, 1); \
1706 newstack->prev = tos; \
1707 newstack->type = TYPE_INT; \
1708 newstack->flags = 0; \
1709 newstack->varkind = UNDEFVAR; \
1710 newstack->varnum = stackdepth; \
1717 /* Inserts the instructions to load the value of the right side of comparison */
1718 /* Depending of the type of the right side, the apropriate instructions are */
1720 #define LOAD_RIGHT_SIDE { \
1721 switch (ld->c_rightside->type) { \
1722 case TRACE_ICONST: \
1723 LOAD_CONST(ld->c_rightside->constant); \
1726 LOAD_VAR(ld->c_rightside->var); \
1727 LOAD_CONST(ld->c_rightside->constant); \
1730 case TRACE_ALENGTH: \
1731 LOAD_ARRAYLENGTH(ld->c_rightside->var); \
1734 log_text("C_ERROR: illegal trace on rightside of loop-header"); \
1739 /* Patch jumps in original loop and in copied loop, add gotos in copied loop.
1740 All jumps in the original loop to the loop head have to be redirected to
1741 the newly inserted one. For the copied loop, it is necessay to redirect all
1742 jumps inside that loop to the copied nodes. lc points to the current loop,
1743 loop_head is a pointer to the newly inserted head and original start was
1744 the old head and is now the head of the optimized variant of the loop.
1746 void patch_jumps(basicblock *original_start, basicblock *loop_head, struct LoopContainer *lc)
1748 /* step through all nodes of a loop */
1749 struct LoopElement *le;
1751 instruction *inst, *temp_instr;
1755 while (le != NULL) {
1757 /* do nothing for new loop head */
1758 if (le->block == loop_head) {
1763 /* for original version */
1765 inst = bptr->iinstr;
1766 for (i = 0; i < bptr->icount; ++i, ++inst) {
1767 switch (inst->opc) {
1769 case ICMD_IF_ICMPEQ:
1770 case ICMD_IF_ICMPLT:
1771 case ICMD_IF_ICMPLE:
1772 case ICMD_IF_ICMPNE:
1773 case ICMD_IF_ICMPGT:
1774 case ICMD_IF_ICMPGE:
1776 case ICMD_IF_LCMPEQ:
1777 case ICMD_IF_LCMPLT:
1778 case ICMD_IF_LCMPLE:
1779 case ICMD_IF_LCMPNE:
1780 case ICMD_IF_LCMPGT:
1781 case ICMD_IF_LCMPGE:
1783 case ICMD_IF_ACMPEQ:
1784 case ICMD_IF_ACMPNE:
1803 case ICMD_IFNONNULL:
1805 /* jump to newly inserted loopheader has to be redirected */
1806 if (((basicblock *) inst->target) == loop_head)
1807 inst->target = (void *) original_start;
1810 case ICMD_TABLESWITCH:
1815 tptr = (void **) inst->target;
1817 s4ptr = inst->val.a;
1818 l = s4ptr[1]; /* low */
1819 i = s4ptr[2]; /* high */
1823 /* jump to newly inserted loopheader has to be redirected */
1824 for (tptr = inst->target; i >= 0; --i, ++tptr) {
1825 if (((basicblock *) *tptr) == loop_head)
1826 tptr[0] = (void *) original_start;
1831 case ICMD_LOOKUPSWITCH:
1836 tptr = (void **) inst->target;
1838 s4ptr = inst->val.a;
1839 l = s4ptr[0]; /* default */
1840 i = s4ptr[1]; /* count */
1842 /* jump to newly inserted loopheader has to be redirected */
1843 for (tptr = inst->target; i >= 0; --i, ++tptr) {
1844 if (((basicblock *) *tptr) == loop_head)
1845 tptr[0] = (void *) original_start;
1852 /* if node is part of loop and has fall through to original start, that */
1853 /* must be redirected. Unfortunately the instructions have to be copied */
1855 if (bptr->next == loop_head) {
1856 temp_instr = DMNEW(instruction, bptr->icount + 1);
1857 memcpy(temp_instr, bptr->iinstr, sizeof(instruction)*bptr->icount);
1858 bptr->iinstr = temp_instr;
1860 bptr->iinstr[bptr->icount].opc = ICMD_GOTO;
1861 bptr->iinstr[bptr->icount].target = original_start;
1862 bptr->iinstr[bptr->icount].dst = NULL;
1866 /* for copied version - which gets the unoptimized variant */
1867 bptr = le->block->copied_to;
1868 inst = bptr->iinstr;
1869 for (i = 0; i < bptr->icount; ++i, ++inst) {
1871 switch (inst->opc) {
1873 case ICMD_IASTORE: /* array store */
1881 case ICMD_IALOAD: /* array load */
1890 /* undo previous optimizations in new loop */
1894 case ICMD_IF_ICMPEQ:
1895 case ICMD_IF_ICMPLT:
1896 case ICMD_IF_ICMPLE:
1897 case ICMD_IF_ICMPNE:
1898 case ICMD_IF_ICMPGT:
1899 case ICMD_IF_ICMPGE:
1901 case ICMD_IF_LCMPEQ:
1902 case ICMD_IF_LCMPLT:
1903 case ICMD_IF_LCMPLE:
1904 case ICMD_IF_LCMPNE:
1905 case ICMD_IF_LCMPGT:
1906 case ICMD_IF_LCMPGE:
1908 case ICMD_IF_ACMPEQ:
1909 case ICMD_IF_ACMPNE:
1928 case ICMD_IFNONNULL:
1930 /* jump to newly inserted loopheader has to be redirected */
1931 if (((basicblock *) inst->target) == loop_head)
1932 inst->target = (void *) original_start->copied_to;
1933 /* jump to loop internal nodes has to be redirected */
1934 else if (((basicblock *) inst->target)->lflags & LOOP_PART)
1935 inst->target = (void *) ((basicblock *) inst->target)->copied_to;
1938 case ICMD_TABLESWITCH:
1942 void **copy_ptr, *base_ptr;
1945 tptr = (void **) inst->target;
1947 s4ptr = inst->val.a;
1948 l = s4ptr[1]; /* low */
1949 i = s4ptr[2]; /* high */
1953 copy_ptr = (void**) DMNEW(void*, i+1);
1954 base_ptr = (void*) copy_ptr;
1956 /* Targets for switch instructions are stored in an extra */
1957 /* that must be copied for new inserted loop. */
1959 for (tptr = inst->target; i >= 0; --i, ++tptr, ++copy_ptr) {
1960 /* jump to newly inserted loopheader must be redirected */
1961 if (((basicblock *) *tptr) == loop_head)
1962 copy_ptr[0] = (void *) original_start->copied_to;
1963 /* jump to loop internal nodes has to be redirected */
1964 else if (((basicblock *) *tptr)->lflags & LOOP_PART)
1965 copy_ptr[0] = (void *) ((basicblock *) tptr[0])->copied_to;
1967 copy_ptr[0] = tptr[0];
1970 inst->target = base_ptr;
1974 case ICMD_LOOKUPSWITCH:
1978 void **copy_ptr, **base_ptr;
1981 tptr = (void **) inst->target;
1983 s4ptr = inst->val.a;
1984 l = s4ptr[0]; /* default */
1985 i = s4ptr[1]; /* count */
1987 copy_ptr = (void**) DMNEW(void*, i+1);
1988 base_ptr = (void*) copy_ptr;
1990 /* Targets for switch instructions are stored in an extra */
1991 /* that must be copied for new inserted loop. */
1993 for (tptr = inst->target; i >= 0; --i, ++tptr, ++copy_ptr) {
1994 /* jump to newly inserted loopheader must be redirected */
1995 if (((basicblock *) *tptr) == loop_head)
1996 copy_ptr[0] = (void *) original_start->copied_to;
1997 /* jump to loop internal nodes has to be redirected */
1998 else if (((basicblock *) *tptr)->lflags & LOOP_PART)
1999 copy_ptr[0] = (void *) ((basicblock *) tptr[0])->copied_to;
2001 copy_ptr[0] = tptr[0];
2004 inst->target = base_ptr;
2011 /* if fall through exits loop, goto is needed */
2012 if (!(le->block->next->lflags & LOOP_PART)) {
2013 bptr->iinstr[bptr->icount].opc = ICMD_GOTO;
2014 bptr->iinstr[bptr->icount].dst = NULL;
2015 bptr->iinstr[bptr->icount].target = le->block->next;
2024 /* Add the new header node of a loop that has been duplicated to all parent
2025 loops in nesting hierarchie.
2028 void header_into_parent_loops(loopdata *ld, struct LoopContainer *lc, basicblock *to_insert, basicblock *replace, basicblock *after)
2030 /* we have to insert the node to_insert before the node after and replace */
2031 /* the pointer of to_insert by the node replace */
2033 struct LoopElement *le, *t;
2035 /* if the top of the tree is reached, then return */
2036 if ((lc == NULL) || (lc == ld->root))
2039 /* create new node, that should be inserted */
2040 t = DMNEW(struct LoopElement, 1);
2041 t->block = to_insert;
2044 /* first, find the node, that has to be replaced (= "to_insert") and */
2045 /* replace it by the node "replace" */
2047 while (le->block != to_insert)
2049 le->block = replace;
2052 if (after == to_insert)
2055 /* now find the node after and insert the newly create node before "after" */
2057 if (le->block == after) {
2058 t->next = lc->nodes;
2062 while (le->next->block != after)
2069 /* go up one hierarchie level */
2070 header_into_parent_loops(ld, lc->parent, to_insert, replace, after);
2074 /* Add a new node (not header) of a duplicated loop to all parent loops in
2078 void node_into_parent_loops(loopdata *ld, struct LoopContainer *lc, basicblock *to_insert)
2080 struct LoopElement *le, *t;
2082 /* if the top of the tree is reached, then return */
2083 if ((lc == NULL) || (lc == ld->root))
2086 /* create new node, that should be inserted */
2087 t = DNEW(LoopElement);
2088 t->block = to_insert;
2093 /* append new node to node list of loop */
2094 while (le->next != NULL)
2100 /* go up one hierarchie level */
2101 node_into_parent_loops(ld, NULL, to_insert);
2105 /* void patch_handler(...) is very similar to parts of the function patch_jumps.
2106 Its task is to redirect all jumps from the original head to the new head and
2107 to redirect internal jumps inside the exception handler to the newly
2108 created (copied) nodes.
2111 void patch_handler(struct LoopContainer *lc, basicblock *bptr, basicblock *original_head, basicblock *new_head)
2116 /* If node is not part of exception handler or has been visited, exit */
2117 if (!(bptr->lflags & HANDLER_PART) || (bptr->lflags & HANDLER_VISITED))
2120 /* mark block as visited */
2121 bptr->lflags |= HANDLER_VISITED;
2123 /* for all instructions in the copied block, do */
2124 for (i = 0, ip = bptr->copied_to->iinstr; i < bptr->copied_to->icount; ++i, ++ip) {
2135 case ICMD_IF_ICMPEQ:
2136 case ICMD_IF_ICMPLT:
2137 case ICMD_IF_ICMPLE:
2138 case ICMD_IF_ICMPNE:
2139 case ICMD_IF_ICMPGT:
2140 case ICMD_IF_ICMPGE:
2142 case ICMD_IF_LCMPEQ:
2143 case ICMD_IF_LCMPLT:
2144 case ICMD_IF_LCMPLE:
2145 case ICMD_IF_LCMPNE:
2146 case ICMD_IF_LCMPGT:
2147 case ICMD_IF_LCMPGE:
2149 case ICMD_IF_ACMPEQ:
2150 case ICMD_IF_ACMPNE:
2168 case ICMD_IFNONNULL:
2170 patch_handler(lc, bptr->next, original_head, new_head);
2176 patch_handler(lc, ip->target, original_head, new_head);
2178 /* jumps to old header have to be redirected */
2179 if (((basicblock *) ip->target) == original_head)
2180 ip->target = (void *) new_head->copied_to;
2181 /* jumps to handler internal nodes have to be redirected */
2182 else if (((basicblock *) ip->target)->lflags & HANDLER_PART)
2183 ip->target = (void *) ((basicblock *) ip->target)->copied_to;
2184 /* jumps to loop internal nodes have to be redirected */
2185 else if (((basicblock *) ip->target)->lflags & LOOP_PART)
2186 ip->target = (void *) ((basicblock *) ip->target)->copied_to;
2191 case ICMD_TABLESWITCH:
2195 void **copy_ptr, **base_ptr;
2197 tptr = (void **) ip->target;
2199 l = s4ptr[1]; /* low */
2200 i = s4ptr[2]; /* high */
2203 copy_ptr = (void**) DMNEW(void*, i+1);
2204 base_ptr = (void*) copy_ptr;
2206 for (tptr = ip->target; i >= 0; --i, ++tptr, ++copy_ptr) {
2207 patch_handler(lc, ((basicblock *) *tptr), original_head, new_head);
2208 /* jumps to old header have to be redirected */
2209 if (((basicblock *) *tptr) == original_head)
2210 copy_ptr[0] = (void *) new_head->copied_to;
2211 /* jumps to handler internal nodes have to be redirected */
2212 else if (((basicblock *) *tptr)->lflags & HANDLER_PART)
2213 copy_ptr[0] = (void *) ((basicblock *) tptr[0])->copied_to;
2214 /* jumps to loop internal nodes have to be redirected */
2215 else if (((basicblock *) ip->target)->lflags & LOOP_PART)
2216 copy_ptr[0] = (void *) ((basicblock *) tptr[0])->copied_to;
2218 copy_ptr[0] = tptr[0];
2221 ip->target = base_ptr;
2225 case ICMD_LOOKUPSWITCH:
2230 void **copy_ptr, **base_ptr;
2232 tptr = (void **) ip->target;
2234 l = s4ptr[0]; /* default */
2235 i = s4ptr[1]; /* count */
2237 copy_ptr = (void**) DMNEW(void*, i+1);
2238 base_ptr = (void*) copy_ptr;
2240 for (tptr = ip->target; i >= 0; --i, ++tptr, ++copy_ptr) {
2242 patch_handler(lc, ((basicblock *) *tptr), original_head, new_head);
2243 /* jumps to old header have to be redirected */
2244 if (((basicblock *) *tptr) == original_head)
2245 copy_ptr[0] = (void *) new_head->copied_to;
2246 /* jumps to handler internal nodes have to be redirected */
2247 else if (((basicblock *) *tptr)->lflags & HANDLER_PART)
2248 copy_ptr[0] = (void *) ((basicblock *) tptr[0])->copied_to;
2249 /* jumps to loop internal nodes have to be redirected */
2250 else if (((basicblock *) ip->target)->lflags & LOOP_PART)
2251 copy_ptr[0] = (void *) ((basicblock *) tptr[0])->copied_to;
2253 copy_ptr[0] = tptr[0];
2256 ip->target = base_ptr;
2264 /* if fall through exits loop, goto is needed */
2265 if (!(bptr->next->lflags & HANDLER_PART)) {
2266 bptr->copied_to->iinstr[bptr->copied_to->icount].opc = ICMD_GOTO;
2267 bptr->copied_to->iinstr[bptr->copied_to->icount].dst = NULL;
2268 bptr->copied_to->iinstr[bptr->copied_to->icount].target = bptr->next;
2269 bptr->copied_to->icount++;
2274 /* copy_handler ****************************************************************
2276 This function copys the exception handler and redirects all jumps from the
2277 original head to the new head in the original exception handler. All
2278 redirection in the copied exception handler is done in patch_handler(...).
2280 *******************************************************************************/
2282 void copy_handler(methodinfo *m, loopdata *ld, struct LoopContainer *lc, basicblock *bptr, basicblock *original_head, basicblock *new_head)
2287 int high, low, count;
2288 struct LoopElement *le;
2289 basicblock *new, *temp;
2291 /* If this node has already been copied, return */
2292 if (bptr->lflags & HANDLER_PART)
2295 /* The exception handler exists, when control flow enters loop again */
2297 if (bptr->lflags & LOOP_PART)
2299 for (le = lc->nodes; le != NULL; le = le->next) {
2300 if (le->block == bptr) {
2301 printf("C_PANIC: should not happen\n");
2306 /* mark block as part of handler */
2307 bptr->lflags |= HANDLER_PART;
2310 new = DMNEW(basicblock, 1);
2311 memcpy(new, bptr, sizeof(basicblock));
2314 ld->c_last_block_copied = new;
2316 /* copy instructions and allow one more slot for possible GOTO */
2317 new->iinstr = DMNEW(instruction, bptr->icount + 1);
2318 memcpy(new->iinstr, bptr->iinstr, bptr->icount * sizeof(instruction));
2320 /* update original block */
2321 bptr->copied_to = new;
2323 /* append block to global list of basic blocks */
2324 temp = m->basicblocks;
2333 /* find next block to copy, depending on last instruction of BB */
2334 if (bptr->icount == 0) {
2335 copy_handler(m, ld, lc, bptr->next, original_head, new_head);
2339 ip = bptr->iinstr + (bptr->icount - 1);
2358 case ICMD_IF_LCMPEQ:
2359 case ICMD_IF_LCMPLT:
2360 case ICMD_IF_LCMPLE:
2361 case ICMD_IF_LCMPNE:
2362 case ICMD_IF_LCMPGT:
2363 case ICMD_IF_LCMPGE:
2373 case ICMD_IFNONNULL:
2375 case ICMD_IF_ICMPEQ:
2376 case ICMD_IF_ICMPNE:
2377 case ICMD_IF_ICMPLT:
2378 case ICMD_IF_ICMPGE:
2379 case ICMD_IF_ICMPGT:
2380 case ICMD_IF_ICMPLE:
2381 case ICMD_IF_ACMPEQ:
2382 case ICMD_IF_ACMPNE:
2383 copy_handler(m, ld, lc, bptr->next, original_head, new_head);
2388 /* redirect jump from original_head to new_head */
2389 if ((basicblock *) ip->target == original_head)
2390 ip->target = (void *) new_head;
2392 copy_handler(m, ld, lc, (basicblock *) (ip->target), original_head, new_head);
2396 case ICMD_TABLESWITCH:
2398 tptr = (void **) ip->target;
2400 /* default branch */
2401 if (((basicblock *) *tptr) == original_head)
2402 tptr[0] = (void *) new_head;
2404 copy_handler(m, ld, lc, (basicblock *) *tptr, original_head, new_head);
2411 count = (high-low+1);
2413 while (--count >= 0) {
2415 /* redirect jump from original_head to new_head */
2416 if (((basicblock *) *tptr) == original_head)
2417 tptr[0] = (void *) new_head;
2418 copy_handler(m, ld, lc, (basicblock *) *tptr, original_head, new_head);
2422 case ICMD_LOOKUPSWITCH:
2424 tptr = (void **) ip->target;
2426 /* default branch */
2427 if (((basicblock *) *tptr) == original_head)
2428 tptr[0] = (void *) new_head;
2430 copy_handler(m, ld, lc, (basicblock *) *tptr, original_head, new_head);
2435 while (--count >= 0) {
2437 /* redirect jump from original_head to new_head */
2438 if (((basicblock *) *tptr) == original_head)
2439 tptr[0] = (void *) new_head;
2440 copy_handler(m, ld, lc, (basicblock *) *tptr, original_head, new_head);
2445 ld->c_last_target = bptr;
2446 copy_handler(m, ld, lc, (basicblock *) (ip->target), original_head, new_head);
2450 copy_handler(m, ld, lc, ld->c_last_target->next, original_head, new_head);
2454 copy_handler(m, ld, lc, bptr->next, original_head, new_head);
2460 /* If a loop is duplicated, all exceptions, that are contained in this loops' body
2461 have to be duplicated as well. The following function together with the
2462 two helper functions copy_handler and patch_handler perform this task.
2465 void update_internal_exceptions(methodinfo *m, codegendata *cd, loopdata *ld, struct LoopContainer *lc, basicblock *original_head, basicblock *new_head)
2467 exceptiontable *ex, *new;
2468 struct LoopContainer *l;
2470 /* Bottom of tree reached -> return */
2474 /* Call update_internal for all nested (=child) loops */
2477 update_internal_exceptions(m, cd, ld, l, original_head, new_head);
2481 /* For all exceptions of this loop, do */
2482 ex = lc->exceptions;
2483 while (ex != NULL) {
2485 /* Copy the exception and patch the jumps */
2486 copy_handler(m, ld, lc, ex->handler, original_head, new_head);
2487 patch_handler(lc, ex->handler, original_head, new_head);
2489 /* Insert a new exception into the global exception table */
2490 new = DNEW(exceptiontable);
2491 memcpy(new, ex, sizeof(exceptiontable));
2493 /* Increase number of exceptions */
2494 ++jd->exceptiontablelength;
2499 /* Set new start and end point of this exception */
2500 new->start = ex->start->copied_to;
2501 new->end = ex->end->copied_to;
2503 /* Set handler pointer to copied exception handler */
2504 new->handler = ex->handler->copied_to;
2512 /* If a loop is duplicated, all exceptions that contain this loop have to be
2513 extended to the copied nodes as well. The following function checks for
2514 all exceptions of all parent loops, whether they contain the loop pointed to
2515 by lc. If so, the exceptions are extended to contain all newly created nodes.
2518 void update_external_exceptions(methodinfo *m, codegendata *cd, loopdata *ld, struct LoopContainer *lc, int loop_head)
2520 exceptiontable *ex, *new;
2522 /* Top of tree reached -> return */
2526 ex = lc->exceptions;
2528 /* For all exceptions of this loop do */
2529 while (ex != NULL) {
2531 /* It is possible that the loop contains exceptions that do not protect */
2532 /* the loop just duplicated. It must be checked, if this is the case */
2533 if ((loop_head >= m->basicblockindex[ex->startpc]) && (loop_head < m->basicblockindex[ex->endpc])) {
2535 /* loop is really inside exception, so create new exception entry */
2536 /* in global exception list */
2537 new = DNEW(exceptiontable);
2538 memcpy(new, ex, sizeof(exceptiontable));
2541 /* Increase number of exceptions */
2542 ++jd->exceptiontablelength;
2547 /* Set new start and end point of this exception */
2548 new->start = ld->c_first_block_copied;
2549 new->end = ld->c_last_block_copied;
2553 /* exception does not contain the duplicated loop -> do nothing */
2558 /* Call update_external for parent node */
2559 update_external_exceptions(m, cd, ld, lc->parent, loop_head);
2563 /* This function is needed to insert the static checks, stored in c_constraints
2564 into the intermediate code.
2567 void create_static_checks(methodinfo *m, codegendata *cd, loopdata *ld, struct LoopContainer *lc)
2569 int i, stackdepth, cnt;
2570 struct Constraint *tc1;
2571 struct LoopElement *le;
2573 /* loop_head points to the newly inserted loop_head, original_start to */
2574 /* the old loop header */
2575 basicblock *bptr, *loop_head, *original_start, *temp;
2576 instruction *inst, *tiptr;
2578 /* tos and newstack are needed by the macros, that insert instructions into */
2579 /* the new loop head */
2580 stackelement_t* newstack, tos;
2583 /* prevent some compiler warnings */
2587 #ifdef ENABLE_STATISTICS
2588 /* show_loop_statistics(l); */
2591 loop_head = &m->basicblocks[ld->c_current_head];
2592 ld->c_first_block_copied = ld->c_last_block_copied = NULL;
2594 /* the loop nodes are copied */
2598 bptr = DMNEW(basicblock, 1);
2599 memcpy(bptr, le->block, sizeof(basicblock));
2602 /* determine beginning of copied loop to extend exception handler, that */
2603 /* protect this loop */
2604 if (ld->c_first_block_copied == NULL)
2605 ld->c_first_block_copied = bptr;
2607 /* copy instructions and add one more slot for possible GOTO */
2608 bptr->iinstr = DMNEW(instruction, bptr->icount + 1);
2610 memcpy(bptr->iinstr, le->block->iinstr, (bptr->icount+1)*sizeof(instruction));
2612 le->block->copied_to = bptr;
2614 /* add block to global list of BBs */
2615 temp = m->basicblocks;
2623 node_into_parent_loops(ld, lc->parent, bptr);
2627 ld->c_last_block_copied = bptr;
2629 /* create an additional basicblock for dynamic checks */
2630 original_start = bptr = DMNEW(basicblock, 1);
2632 /* copy current loop header to new basic block */
2633 memcpy(bptr, loop_head, sizeof(basicblock));
2636 /* insert the new basic block and move header before first loop node */
2640 /* if header is first node of loop, insert original header after it */
2641 if (temp == loop_head)
2642 loop_head->next = bptr;
2644 /* else, we have to find the predecessor of loop header */
2645 while (temp->next != loop_head)
2648 /* insert original header after newly created block */
2651 /* if predecessor is not loop part, insert a goto */
2652 if (!(temp->lflags & LOOP_PART)) {
2654 /* copy instructions and add an additional slot */
2655 tiptr = DMNEW(instruction, temp->icount + 1);
2656 memcpy(tiptr, temp->iinstr, sizeof(instruction)*temp->icount);
2658 temp->iinstr = tiptr;
2659 tiptr = temp->iinstr + temp->icount;
2661 /* add goto to loop header. If node is part of exception handler */
2662 /* jmp is automagically redirected during patch_handler and works */
2664 tiptr->opc = ICMD_GOTO;
2666 tiptr->target = (void*) loop_head;
2672 temp = m->basicblocks;
2673 /* if first loop block is first BB of global list, insert loop_head at */
2674 /* beginning of global BB list */
2675 if (temp == le->block) {
2676 if (ld->c_newstart == NULL) {
2677 ld->c_needs_redirection = true;
2678 ld->c_newstart = loop_head;
2679 loop_head->next = m->basicblocks;
2682 loop_head->next = ld->c_newstart;
2683 ld->c_newstart = loop_head;
2688 while (temp->next != le->block)
2691 loop_head->next = temp->next;
2692 temp->next = loop_head;
2694 /* to be on the safe side insert a jump from the previous instr */
2695 /* over thr new inserted node */
2697 /* special case - jump from node to loop_head: then remove */
2698 /* goto / happens rather often due to loop layout */
2699 tiptr = temp->iinstr + (temp->icount-1);
2701 if ((tiptr->opc == ICMD_GOTO) && (tiptr->target == loop_head)) {
2702 tiptr->opc = ICMD_NOP;
2707 tiptr = DMNEW(instruction, temp->icount + 1);
2708 memcpy(tiptr, temp->iinstr, sizeof(instruction)*temp->icount);
2710 temp->iinstr = tiptr;
2711 tiptr = temp->iinstr + temp->icount;
2713 tiptr->opc = ICMD_GOTO;
2715 tiptr->target = (void*) loop_head->next;
2722 /* adjust exceptions */
2723 ex = jd->exceptiontable;
2724 while (ex != NULL) {
2726 /* if an exception covers whole loop and starts at first loop node, it */
2727 /* has to be extended to cover the new first node as well */
2728 if (ex->start == le->block) {
2730 if ((lc->loop_head >= m->basicblockindex[ex->startpc]) && (lc->loop_head < m->basicblockindex[ex->endpc]))
2731 ex->start = loop_head;
2734 /* an exception that ended at the old loop header now must contains the */
2735 /* new loop header as well */
2736 if (ex->end == loop_head)
2737 ex->end = original_start;
2743 /* insert new header node into nodelists of all enclosing loops */
2744 header_into_parent_loops(ld, lc, loop_head, original_start, le->block);
2746 /* prepare instruction array to insert checks */
2747 inst = loop_head->iinstr = DMNEW(instruction, ld->c_needed_instr + 2);
2748 loop_head->icount = ld->c_needed_instr + 1;
2750 /* init instruction array */
2751 for (cnt=0; cnt<ld->c_needed_instr + 1; ++cnt) {
2752 inst[0].opc = ICMD_NOP;
2756 loop_head->copied_to = NULL;
2759 loop_head->instack = copy_stack_from(bptr->instack);
2760 loop_head->outstack = copy_stack_from(bptr->instack);
2762 tos = loop_head->instack;
2763 stackdepth = loop_head->indepth;
2765 /* step through all inserted checks and create instructions for them */
2766 for (i=0; i<jd->maxlocals+1; ++i)
2768 tc1 = ld->c_constraints[i];
2774 /* check a variable against a constant */
2776 case TEST_UNMOD_ZERO:
2779 printf("insert ZERO-test\n");
2783 /* optimize if tc1->varRef >= tc1->constant */
2784 LOAD_VAR(tc1->varRef);
2785 LOAD_CONST(tc1->constant);
2789 /* check a variable against an array length */
2791 case TEST_UNMOD_ALENGTH:
2794 /* tc1->varRef + tc1->constant < lengthOf(tc1->arrayRef) */
2796 printf("insert ALENGTH-test\n");
2800 LOAD_VAR(tc1->varRef);
2801 LOAD_CONST(tc1->constant);
2803 LOAD_ARRAYLENGTH(tc1->arrayRef);
2807 /* test right side of comparison against constant */
2811 printf("insert RS-ZERO-test\n");
2815 /* optimize if right-side >= tc1->constant */
2817 LOAD_CONST(tc1->constant);
2821 /* test right side of comparison against array length */
2822 case TEST_RS_ALENGTH:
2825 printf("insert RS-ALENGTH-test\n");
2828 /* optimize if right-side < lengthOf(arrayRef) */
2830 LOAD_ARRAYLENGTH(tc1->arrayRef);
2834 /* test unmodified variable against arraylength */
2835 case TEST_CONST_ALENGTH:
2838 printf("insert CONST ALENGTH-test\n");
2842 /* optimize if tc1->constant < lengthOf(tc1->arrayRef) */
2843 LOAD_CONST(tc1->constant);
2844 LOAD_ARRAYLENGTH(tc1->arrayRef);
2851 ld->c_constraints[i] = NULL;
2854 /* if all tests succeed, jump to optimized loop header */
2855 if (loop_head->next != original_start) {
2856 inst->opc = ICMD_GOTO;
2858 inst->target = original_start;
2861 /* redirect jumps from original loop head to newly inserted one */
2862 patch_jumps(original_start, loop_head, lc);
2864 /* if exceptions have to be correct due to loop duplication these two */
2865 /* functions perform this task. */
2866 update_internal_exceptions(m, cd, ld, lc, loop_head, original_start);
2867 update_external_exceptions(m, cd, ld, lc->parent, lc->loop_head);
2871 /* This function performs an update between two arrays of struct Changes (that
2872 reflect variable changes). The merge is performed unrstricted in the way, that
2873 all variable changes in c1 took place in a nested loop and therefore are
2874 considered to be without limit. Beside that, the merge is a simple union of the
2875 changes recorded in both arrays. A variable, which limits are undefinied, is
2876 represented by its lower bound being higher than the upper bound. The result
2877 of the union is stored in c1.
2879 struct Changes ** constraints_unrestricted_merge(codegendata *cd, struct Changes **c1, struct Changes **c2)
2883 if ((c1 == NULL) || (c2 == NULL))
2884 printf("C_ERROR: debugging error 0x03\n");
2887 for (i=0; i<jd->maxlocals; ++i) {
2888 if (c1[i] == NULL) {
2889 if (c2[i] != NULL) { /* a change in c2 is updated in c1 */
2892 c1[i]->lower_bound = c1[i]->upper_bound+1;
2896 if (c1[i]->lower_bound > c1[i]->upper_bound)
2897 continue; /* variable's bounds already undefined */
2899 if (c2[i] == NULL) { /* variable changed in c1 -> now undef. */
2901 c1[i]->lower_bound = c1[i]->upper_bound+1;
2904 if ((c1[i]->lower_bound == c2[i]->lower_bound) &&
2905 (c1[i]->upper_bound == c2[i]->upper_bound))
2906 continue; /* variable's bounds remain the same */
2909 c1[i]->lower_bound = c1[i]->upper_bound+1;
2910 } /* variable changed in c1 -> now undef. */
2921 /* This function performs an update between two arrays of struct Changes (that
2922 reflect variable changes). The merge is a simple union of the bounds
2923 changes recorded in both arrays. A variable, which limits are undefinied, is
2924 represented by its lower bound being higher than the upper bound. The result
2925 of the union is stored in c1.
2927 struct Changes ** constraints_merge(codegendata *cd, struct Changes **c1, struct Changes **c2)
2931 if ((c1 == NULL) || (c2 == NULL))
2932 printf("C_ERROR: debugging error 0x04\n");
2936 for (i=0; i<jd->maxlocals; ++i) {
2937 if (c1[i] == NULL) {
2938 if (c2[i] != NULL) { /* update changes in c2 in c1 */
2939 if ((c1[i] = (struct Changes *) malloc (sizeof(struct Changes))) == NULL)
2942 c1[i]->lower_bound = c2[i]->lower_bound;
2943 c1[i]->upper_bound = c2[i]->upper_bound;
2948 if (c2[i] != NULL) {
2950 if (c1[i]->lower_bound > c1[i]->upper_bound)
2951 continue; /* var in c1 is unrestricted */
2953 if (c1[i]->lower_bound > c2[i]->lower_bound) {
2954 c1[i]->lower_bound = c2[i]->lower_bound;
2955 changed = 1; /* write new lower bound */
2957 if (c1[i]->upper_bound < c2[i]->upper_bound) {
2958 c1[i]->upper_bound = c2[i]->upper_bound;
2959 changed = 1; /* write new higher bound */
2972 /* This function simply copies an array of changes
2974 struct Changes** constraints_clone(codegendata *cd, struct Changes **c)
2979 if ((t = (struct Changes **) malloc(jd->maxlocals * sizeof(struct Changes *))) == NULL)
2982 for (i=0; i<jd->maxlocals; ++i) { /* for all array elements (vars) do */
2986 if ((t[i] = (struct Changes *) malloc(sizeof(struct Changes))) == NULL)
2988 t[i]->lower_bound = c[i]->lower_bound;
2989 t[i]->upper_bound = c[i]->upper_bound;
2996 /* This function is used to reset the changes of a variable to the time, it was
2997 pushed onto the stack. If a variable has been modified between an instruction
2998 and a previous push onto the stack, its value in the changes array does not
2999 correctly reflect its bounds the time, it was pushed onto the stack. This
3000 function corrects the situation.
3002 struct Changes* backtrack_var(methodinfo *m, int node, int from, int to, int varRef, struct Changes *changes)
3004 struct Changes *tmp;
3009 if (changes == NULL) /* if there are no changes, immediately return */
3011 else { /* init a Changes structure with current values */
3012 if ((tmp = (struct Changes *) malloc(sizeof(struct Changes))) == NULL)
3015 tmp->upper_bound = changes->upper_bound;
3016 tmp->lower_bound = changes->lower_bound;
3019 if (tmp->upper_bound < tmp->lower_bound)
3020 return tmp; /* if it is unrestricted no backtracking can happen */
3022 bp = m->basicblocks[node];
3023 ip = bp.iinstr + to;
3025 for (; from < to; --to, --ip) { /* scan instructions backwards */
3027 case ICMD_IINC: /* a var has been modified */
3028 if (varRef != ip->op1) /* not the one, we are interested in */
3030 tmp->upper_bound -= ip->val.i; /* take back modifications */
3031 tmp->lower_bound -= ip->val.i;
3034 case ICMD_ISTORE: /* a var has been modified */
3035 if (varRef != ip->op1) /* not the one, we are interested in */
3038 /* it is our variable, so trace its origin */
3039 t = tracing(&m->basicblocks[node],to, 0);
3043 if ((t->var = ip->op1) && (t->neg > 0)) {
3044 /* it was the same var -> take back modifications */
3045 tmp->upper_bound -= t->constant;
3046 tmp->lower_bound -= t->constant;
3049 tmp->lower_bound = tmp->upper_bound+1; /* unknown */
3052 /* cannot restore it -> invalidate t */
3057 tmp->lower_bound = tmp->upper_bound+1;
3068 /* This function performs the main task of bound check removal. It removes
3069 all bound-checks in node. change is a pointer to an array of struct Changes
3070 that reflect for all local variables, how their values have changed from
3071 the start of the loop. The special flag is needed to deal with the header
3075 void remove_boundchecks(methodinfo *m, codegendata *cd, loopdata *ld, int node, int from, struct Changes **change, int special)
3079 int i, count, ignore, degrade_checks, opt_level;
3080 struct depthElement *d;
3081 struct Changes **t1, **tmp, *t;
3082 struct Trace *t_array, *t_index;
3084 /* prevent some compiler warnings */
3089 /* printf("remove_bc called: %d - %d - %d\n", node, from, special); */
3091 /* a flag, that is set, when previous optimzations have to be taken back */
3094 if (ld->c_current_loop[node] > 0) { /* this node is part of the loop */
3095 if (ld->c_current_loop[node] > 1) { /* it is not the header node */
3097 /* get variable changes, already recorded for this node */
3098 t1 = ld->c_dTable[node]->changes;
3100 if (t1 != NULL) { /* it is not the first visit */
3101 if ((ld->c_nestedLoops[node] != ld->c_current_head) && (ld->c_nestedLoops[node] == ld->c_nestedLoops[from])) {
3102 /* we are looping in a nested loop, so made optimizations */
3103 /* need to be reconsidered */
3105 if (constraints_unrestricted_merge(cd, t1, change) == NULL)
3106 return; /* no changes since previous visit */
3107 /* if there have been changes, they are updated by */
3108 /* constraints_unrestricted_merge in t1 */
3111 if (constraints_merge(cd, t1, change) == NULL)
3112 return; /* no changes since previous visit */
3113 /* if there have been changes, they are updated by */
3114 /* constraints_merge in t1 */
3117 else { /* first visit */
3118 /* printf("first visit - constraints cloned\n"); */
3119 ld->c_dTable[node]->changes = constraints_clone(cd, change);
3122 /* tmp now holds a copy of the updated variable changes */
3123 tmp = constraints_clone(cd, ld->c_dTable[node]->changes);
3125 else if (special) { /* header and need special traetment */
3126 /* printf("special treatment called\n"); */
3127 /* tmp now holds a copy of the current new variable changes */
3128 tmp = constraints_clone(cd, change);
3133 bp = m->basicblocks[node]; /* scan all instructions */
3138 for (i=0; i<count; ++i, ++ip) {
3140 case ICMD_IASTORE: /* found an array store */
3149 t_index = tracing(&bp, i-1, 1); /* get index */
3150 t_array = tracing(&bp, i-1, 2); /* get array refernce */
3154 case ICMD_IALOAD: /* found an array load */
3163 t_index = tracing(&bp, i-1, 0); /* get index */
3164 t_array = tracing(&bp, i-1, 1); /* get array refernce */
3168 /* printf("Array access with params:\n");
3170 show_trace(t_array);
3172 show_trace(t_index);
3175 #ifdef ENABLE_STATISTICS
3176 if (ip->op1 == OPT_UNCHECKED) { /* found new access */
3177 ld->c_stat_array_accesses++;
3179 ld->c_stat_no_opt++;
3183 /* can only optimize known arrays that do not change */
3184 if ((t_array->type != TRACE_AVAR) || (ld->c_var_modified[t_array->var]))
3187 switch (t_index->type) { /* now we look at the index */
3188 case TRACE_ICONST: /* it is a constant value or an */
3189 case TRACE_ALENGTH: /* array length */
3190 #ifdef ENABLE_STATISTICS
3191 switch (ip->op1) { /* take back old optimzation */
3195 ld->c_stat_no_opt--;
3198 ld->c_stat_full_opt--;
3201 ld->c_stat_upper_opt--;
3204 ld->c_stat_lower_opt--;
3208 if (degrade_checks) /* replace existing optimization */
3209 ip->op1 = insert_static(m, cd, ld, t_array->var, t_index, NULL, special);
3211 /* Check current optimization and try to improve it by */
3212 /* inserting new checks */
3215 ip->op1 = insert_static(m, cd, ld, t_array->var, t_index, NULL, special);
3218 ip->op1 = insert_static(m, cd, ld, t_array->var, t_index, NULL, special);
3221 opt_level = insert_static(m, cd, ld, t_array->var, t_index, NULL, special);
3222 if ((opt_level == OPT_FULL) || (opt_level == OPT_LOWER))
3226 opt_level = insert_static(m, cd, ld, t_array->var, t_index, NULL, special);
3227 if ((opt_level == OPT_FULL) || (opt_level == OPT_UPPER))
3231 #ifdef ENABLE_STATISTICS
3232 ld->c_stat_full_opt++;
3239 case TRACE_IVAR: /* it's a variable */
3241 /* if the variable is changed between its usage as an index */
3242 /* of the array access and its push onto the stack, we have */
3243 /* to set the changes back to the time, it is pushed onto */
3244 /* the stack as an index variable. */
3245 t = backtrack_var(m, node, t_index->nr, i-1, t_index->var, tmp[t_index->var]);
3246 #ifdef ENABLE_STATISTICS
3247 switch (ip->op1) { /* take back old optimzation */
3251 ld->c_stat_no_opt--;
3254 ld->c_stat_full_opt--;
3257 ld->c_stat_upper_opt--;
3260 ld->c_stat_lower_opt--;
3265 ip->op1 = insert_static(m, cd, ld, t_array->var, t_index, t, special);
3267 /* Check current optimization and try to improve it by */
3268 /* insert new check. t reflects var changes for index */
3271 ip->op1 = insert_static(m, cd, ld, t_array->var, t_index, t, special);
3274 ip->op1 = insert_static(m, cd, ld, t_array->var, t_index, t, special);
3277 opt_level = insert_static(m, cd, ld, t_array->var, t_index, t, special);
3278 if ((opt_level == OPT_FULL) || (opt_level == OPT_LOWER))
3282 opt_level = insert_static(m, cd, ld, t_array->var, t_index, t, special);
3283 if ((opt_level == OPT_FULL) || (opt_level == OPT_UPPER))
3287 #ifdef ENABLE_STATISTICS
3288 ld->c_stat_full_opt++;
3301 case ICMD_ISTORE: /* an integer value is stored */
3302 t_index = tracing(&bp, i-1, 0); /* trace back its origin */
3304 /* the struct Changes for this variable needs to be updated */
3306 if (t == NULL) { /* if it's the first one, create new entry */
3307 if ((t = (struct Changes *) malloc(sizeof(struct Changes))) == NULL)
3309 t->upper_bound = t->lower_bound = 0;
3313 switch (t_index->type) { /* check origin of store */
3315 case TRACE_ICONST: /* constant -> set bounds to const value */
3316 t->upper_bound = t->lower_bound = t_index->constant;
3319 case TRACE_IVAR: /* if it's the same variable, update consts */
3320 if ((t_index->var = ip->op1) && (t_index->neg > 0)) {
3321 t->upper_bound += t_index->constant;
3322 t->lower_bound += t_index->constant;
3325 t->lower_bound = t->upper_bound+1;
3328 case TRACE_ALENGTH: /* else -> unknown */
3331 t->lower_bound = t->upper_bound+1;
3339 /* the struct Changes for this variable needs to be updated */
3340 if ((t = tmp[ip->op1]) == NULL) { /* first one -> create new */
3341 if ((t = (struct Changes *) malloc(sizeof(struct Changes))) == NULL)
3343 t->upper_bound = t->lower_bound = ip->val.i;
3346 else { /* update changes, made by iinc */
3347 t->upper_bound += ip->val.i;
3348 t->lower_bound += ip->val.i;
3354 if (!special) { /* we are not interested in only the header */
3355 d = ld->c_dTable[node];
3356 while (d != NULL) { /* check all sucessors of current node */
3357 remove_boundchecks(m, cd, ld, d->value, node, tmp, special);
3365 /* This function calls the bound-check removal function for the header node
3366 with a special flag. It is important to notice, that no dynamic
3367 constraint hold in the header node (because the comparison is done at
3371 void remove_header_boundchecks(methodinfo *m, codegendata *cd, loopdata *ld, int node, struct Changes **changes)
3373 remove_boundchecks(m, cd, ld, node, -1, changes, BOUNDCHECK_SPECIAL);
3377 /* Marks all basicblocks that are part of the loop
3380 void mark_loop_nodes(struct LoopContainer *lc)
3382 struct LoopElement *le = lc->nodes;
3384 while (le != NULL) {
3385 le->block->lflags |= LOOP_PART;
3391 /* Clears mark for all basicblocks that are part of the loop
3393 void unmark_loop_nodes(LoopContainer *lc)
3395 LoopElement *le = lc->nodes;
3397 while (le != NULL) {
3398 le->block->lflags = 0;
3404 /* This function performs the analysis of code in detected loops and trys to
3405 identify array accesses suitable for optimization (bound check removal). The
3406 intermediate code is then modified to reflect these optimizations.
3408 void optimize_single_loop(methodinfo *m, codegendata *cd, loopdata *ld, LoopContainer *lc)
3410 struct LoopElement *le;
3411 struct depthElement *d;
3413 struct Changes **changes;
3415 if ((changes = (struct Changes **) malloc(jd->maxlocals * sizeof(struct Changes *))) == NULL)
3418 head = ld->c_current_head = lc->loop_head;
3419 ld->c_needed_instr = ld->c_rs_needed_instr = 0;
3421 /* init array for null ptr checks */
3422 for (i=0; i<jd->maxlocals; ++i)
3423 ld->c_null_check[i] = 0;
3426 /* don't optimize root node (it is the main procedure, not a loop) */
3430 /* setup variables with initial values */
3431 ld->c_loopvars = NULL;
3432 for (i=0; i < m->basicblockcount; ++i) {
3433 ld->c_toVisit[i] = 0;
3434 ld->c_current_loop[i] = -1;
3435 if ((d = ld->c_dTable[i]) != NULL)
3439 for (i=0; i < jd->maxlocals; ++i) {
3440 ld->c_var_modified[i] = 0;
3441 if (changes[i] != NULL) {
3446 for (i=0; i < (jd->maxlocals+1); ++i) {
3447 if (ld->c_constraints[i] != NULL) {
3448 ld->c_constraints[i] = NULL;
3453 while (le != NULL) {
3457 ld->c_current_loop[node] = 1; /* the header node gets 1 */
3458 else if (ld->c_nestedLoops[node] == head)
3459 ld->c_current_loop[node] = 2; /* top level nodes get 2 */
3461 ld->c_current_loop[node] = 3; /* nodes, part of nested loop get 3 */
3463 ld->c_toVisit[node] = 1;
3467 /* After setup work has been performed, start to analyse */
3469 printf("****** Starting analysis (%d)******\n", head);
3473 if (analyze_for_array_access(m, ld, head) > 0) {/* loop contains array access */
3478 printf("analyze for array access finished and found\n");
3480 lv = ld->c_loopvars;
3481 while (lv != NULL) {
3483 printf("Var --> %d\n", lv->value);
3488 /* for performance reasons the list of all interesting loop vars is */
3489 /* scaned and for all modified vars a flag in c_var_modified is set */
3490 scan_global_list(ld);
3493 printf("global list scanned\n");
3497 /* if the loop header contains or-conditions or an index variable */
3498 /* is modified in the catch-block within the loop, a conservative */
3499 /* approach is taken and optimizations are cancelled */
3500 if (analyze_or_exceptions(m, cd, ld, head, lc) > 0) {
3503 printf("Analyzed for or/exception - no problems \n");
3507 init_constraints(m, ld, head); /* analyze dynamic bounds in header */
3513 if (ld->c_rightside == NULL)
3516 /* single pass bound check removal - for all successors, do */
3517 remove_header_boundchecks(m, cd, ld, head, changes);
3519 d = ld->c_dTable[head];
3521 remove_boundchecks(m, cd, ld, d->value, -1, changes, BOUNDCHECK_REGULAR);
3526 printf("Array-bound checks finished\n");
3530 mark_loop_nodes(lc);
3533 printf("START: create static checks\n");
3537 create_static_checks(m, cd, ld, lc); /* create checks */
3540 printf("END: create static checks\n");
3543 unmark_loop_nodes(lc);
3547 printf("No array accesses found\n"); */
3549 #ifdef ENABLE_STATISTICS
3550 ld->c_stat_num_loops++; /* increase number of loops */
3552 ld->c_stat_sum_accesses += ld->c_stat_array_accesses;
3553 ld->c_stat_sum_full += ld->c_stat_full_opt;
3554 ld->c_stat_sum_no += ld->c_stat_no_opt;
3555 ld->c_stat_sum_lower += ld->c_stat_lower_opt;
3556 ld->c_stat_sum_upper += ld->c_stat_upper_opt;
3557 ld->c_stat_sum_or += ld->c_stat_or;
3558 ld->c_stat_sum_exception += ld->c_stat_exception;
3560 ld->c_stat_array_accesses = 0;
3561 ld->c_stat_full_opt = 0;
3562 ld->c_stat_no_opt = 0;
3563 ld->c_stat_lower_opt = 0;
3564 ld->c_stat_upper_opt = 0;
3565 ld->c_stat_or = ld->c_stat_exception = 0;
3571 /* optimize_loops **************************************************************
3573 This function preforms necessary setup work, before the recursive
3574 function optimize_single loop can be called.
3576 *******************************************************************************/
3578 void optimize_loops(jitdata *jd)
3585 /* get required compiler data */
3591 lc = ld->c_allLoops;
3593 /* first, merge loops with same header node - all loops with the same */
3594 /* header node are optimizied in one pass, because they all depend on the */
3595 /* same dynamic loop condition */
3598 printf("start analyze_double_headers\n");
3602 analyze_double_headers(ld);
3604 /* create array with loop nesting levels - nested loops cause problems, */
3605 /* especially, when they modify index variables used in surrounding loops */
3606 /* store results in array c_nestedLoops and c_hierarchie */
3609 printf("double done\n");
3613 analyze_nested(m,cd, ld);
3616 printf("analyze nested done\n");
3620 /* create array with entries for current loop */
3621 ld->c_current_loop = DMNEW(int, m->basicblockcount);
3622 ld->c_toVisit = DMNEW(int, m->basicblockcount);
3623 ld->c_var_modified = DMNEW(int, jd->maxlocals);
3624 ld->c_null_check = DMNEW(int, jd->maxlocals);
3626 if ((ld->c_constraints = (struct Constraint **) malloc((jd->maxlocals+1) * sizeof(struct Constraint *))) == NULL)
3629 #ifdef ENABLE_STATISTICS
3630 ld->c_stat_num_loops = 0; /* set statistic vars to zero */
3631 ld->c_stat_array_accesses = ld->c_stat_sum_accesses = 0;
3632 ld->c_stat_full_opt = ld->c_stat_sum_full = 0;
3633 ld->c_stat_no_opt = ld->c_stat_sum_no = 0;
3634 ld->c_stat_lower_opt = ld->c_stat_sum_lower = 0;
3635 ld->c_stat_upper_opt = ld->c_stat_sum_upper = 0;
3636 ld->c_stat_or = ld->c_stat_sum_or = 0;
3637 ld->c_stat_exception = ld->c_stat_sum_exception = 0;
3640 /* init vars needed by all loops */
3641 ld->c_needs_redirection = false;
3642 ld->c_newstart = NULL;
3643 ld->c_old_xtablelength = jd->exceptiontablelength;
3645 /* loops have been topologically sorted */
3646 lc = ld->c_allLoops;
3647 while (lc != NULL) {
3648 optimize_single_loop(m, cd, ld, lc);
3651 printf(" *** Optimized loop *** \n");
3658 printf("---*** All loops finished ***---\n");
3662 /* if global BB list start is modified, set block to new start */
3663 if (ld->c_needs_redirection == true)
3664 m->basicblocks = ld->c_newstart;
3670 * These are local overrides for various environment variables in Emacs.
3671 * Please do not remove this and leave it at the end of the file, where
3672 * Emacs will automagically detect them.
3673 * ---------------------------------------------------------------------
3676 * indent-tabs-mode: t