src/vm/jit/loop/analyze.c

   1 /* jit/loop/analyze.c - bound check removal functions
   2
   3    Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003
   4    R. Grafl, A. Krall, C. Kruegel, C. Oates, R. Obermaisser,
   5    M. Probst, S. Ring, E. Steiner, C. Thalinger, D. Thuernbeck,
   6    P. Tomsich, J. Wenninger
   7
   8    This file is part of CACAO.
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2, or (at
  13    your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful, but
  16    WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  23    02111-1307, USA.
  24
  25    Contact: cacao@complang.tuwien.ac.at
  26
  27    Authors: Christopher Kruegel
  28
  29    Contains the functions which perform the bound check removals. With
  30    the loops identified, these functions scan the code for array
  31    accesses that take place in loops and try to guarantee that their
  32    bounds are never violated. The function to call is
  33    optimize_loops().
  34
  35    $Id: analyze.c 1203 2004-06-22 23:14:55Z twisti $
  36
  37 */
  38
  39
  40 #include <stdio.h>
  41 #include <stdlib.h>
  42 #include <string.h>
  43 #include "jit/loop/analyze.h"
  44 #include "jit/jit.h"
  45 #include "jit/loop/loop.h"
  46 #include "jit/loop/graph.h"
  47 #include "jit/loop/tracing.h"
  48 #include "toolbox/logging.h"
  49 #include "toolbox/memory.h"
  50
  51
  52 #ifdef LOOP_DEBUG
  53
  54 /*      Test functions -> will be removed in final release
  55 */
  56
  57 void show_trace(struct Trace *trace)
  58 {
  59         if (trace != NULL) {
  60                 switch (trace->type) {
  61                 case TRACE_IVAR:
  62                         printf("int-var");
  63                         printf("\nNr.:\t%d", trace->var);
  64                         printf("\nValue:\t%d", trace->constant);
  65                         break;
  66
  67                 case TRACE_AVAR:
  68                         printf("object-var");
  69                         printf("\nNr.:\t%d", trace->var);
  70                         break;
  71
  72                 case TRACE_ALENGTH:
  73                         printf("array-length");
  74                         printf("\nNr.:\t%d", trace->var);
  75                         printf("\nValue:\t%d", trace->constant);
  76                         break;
  77
  78                 case TRACE_ICONST:
  79                         printf("int-const");
  80                         printf("\nValue:\t%d", trace->constant);
  81                         break;
  82
  83                 case TRACE_UNKNOWN:
  84                         printf("unknown");
  85                         break;
  86                         }
  87                 }
  88         else
  89                 printf("Trace is null");
  90
  91         printf("\n");
  92 }
  93
  94
  95 void show_change(struct Changes *c)
  96 {
  97         printf("*** Changes ***\n");
  98         if (c != NULL)
  99                 printf("Lower/Upper Bound:\t%d/%d\n", c->lower_bound, c->upper_bound);
 100         else
 101                 printf("Unrestricted\n");
 102 }
 103
 104 show_varinfo(struct LoopVar *lv)
 105 {
 106         printf("   *** Loop Info ***\n");
 107         printf("Value:\t%d\n", lv->value);
 108         printf("Static:\t\t%d/%d\n", lv->static_l, lv->static_u);
 109         printf("D-Valid:\t%d/%d\n", lv->dynamic_l_v, lv->dynamic_u_v);
 110         printf("Dynamic\t\t%d/%d\n", lv->dynamic_l, lv->dynamic_u);
 111 }
 112
 113 void show_right_side()
 114 {
 115         int i;
 116         printf("\n   *** Head ***   \nType:\t");
 117         show_trace(c_rightside);
 118
 119         printf("\n   *** Nested Loops: ***\n");
 120         for (i=0; i<m->basicblockcount; ++i)
 121                 printf("%d\t", c_nestedLoops[i]);
 122         printf("\n");
 123
 124         printf("\n   *** Hierarchie: ***\n");
 125         for (i=0; i<m->basicblockcount; ++i)
 126                 printf("%d\t", c_hierarchie[i]);
 127         printf("\n");
 128
 129
 130         printf("\n   *** Current Loop ***\n");
 131         for (i=0; i<m->basicblockcount; ++i)
 132             printf("%d\t", c_current_loop[i]);
 133         printf("\n");
 134 }
 135
 136 void resultPass3()
 137 {
 138         int i;
 139         struct LoopContainer *lc = c_allLoops;
 140
 141         printf("\n\n****** PASS 3 ******\n\n");
 142
 143         while (lc != NULL) {
 144                 printf("Loop Analysis:\n");
 145                 printf("Optimize:\t%d\n", lc->toOpt);
 146                 printf("Modified Vars: ");
 147                 /*
 148                 for (i=0; i<lc->num_vars; ++i)
 149                   printf("%d ", lc->vars[i]);
 150                 printf("\n\n");
 151                 */
 152                 lc = lc->next;
 153                 }
 154
 155         printf("\nNested Loops:\n");
 156         for (i=0; i<m->basicblockcount; ++i)
 157             printf("%d ", c_nestedLoops[i]);
 158         printf("\n");
 159         for (i=0; i<m->basicblockcount; ++i)
 160                 printf("%d ", c_hierarchie[i]);
 161         printf("\n");
 162         fflush(stdout);
 163 }
 164
 165 void show_tree(struct LoopContainer *lc, int tabs)
 166 {
 167         int cnt;
 168
 169         while (lc != NULL) {
 170                 for (cnt = 0; cnt < tabs; ++cnt)
 171                         printf("  ");
 172                 printf("%d\n", lc->loop_head);
 173
 174                 show_tree(lc->tree_down, tabs+1);
 175
 176                 lc = lc->tree_right;
 177         }
 178 }
 179
 180 #endif
 181
 182 #ifdef STATISTICS
 183
 184 void show_loop_statistics()
 185 {
 186         printf("\n\n****** LOOP STATISTICS ****** \n\n");
 187         if (c_stat_or)
 188             printf("Optimization cancelled by or\n");
 189         else if (c_stat_exception)
 190             printf("Optimization cancelled by exception\n");
 191         else {
 192                 printf("Number of array accesses:\t%d\n", c_stat_array_accesses);
 193                 if (c_stat_array_accesses) {
 194                         printf("\nFully optimized:\t%d\n", c_stat_full_opt);
 195                         printf("Not optimized:\t\t%d\n", c_stat_no_opt);
 196                         printf("Upper optimized:\t%d\n", c_stat_upper_opt);
 197                         printf("Lower optimized:\t%d\n", c_stat_lower_opt);
 198                         }
 199                 }
 200 }
 201
 202 void show_procedure_statistics()
 203 {
 204         printf("\n\n****** PROCEDURE STATISTICS ****** \n\n");
 205         printf("Number of loops:\t\t%d\n", c_stat_num_loops);
 206         printf("Number of array accesses:\t%d\n", c_stat_sum_accesses);
 207         if (c_stat_sum_accesses) {
 208                 printf("\nFully optimized:\t%d\n", c_stat_sum_full);
 209                 printf("Not optimized:\t\t%d\n", c_stat_sum_no);
 210                 printf("Upper optimized:\t%d\n", c_stat_sum_upper);
 211                 printf("Lower optimized:\t%d\n", c_stat_sum_lower);
 212                 }
 213         printf("Opt. cancelled by or:\t\t%d\n", c_stat_sum_or);
 214         printf("Opt. cancelled by exception:\t%d\n", c_stat_sum_exception);
 215 }
 216
 217 #endif
 218
 219
 220 /*      This function is used to merge two loops with the same header together.
 221         A simple merge sort of the lists nodes of both loops is performed.
 222 */
 223 void analyze_merge(struct LoopContainer *l1, struct LoopContainer *l2)
 224 {
 225         struct LoopElement *start, *last, *le1, *le2;
 226         /* start and last are pointers to the newly built list, le1 and le2 step  */
 227         /* step through the lists, that have to be merged.                        */
 228
 229         le1 = l1->nodes;
 230         le2 = l2->nodes;
 231
 232         /* start a simple merge sort of the nodes of both loops. These lists are  */
 233         /* already sorted, so merging is easy.                                    */
 234         if (le1->node < le2->node) {
 235                 start = last = le1;
 236                 le1 = le1->next;
 237                 }
 238         else if (le1->node == le2->node) {
 239                 start = last = le1;
 240                 le1 = le1->next;
 241                 le2 = le2->next;
 242                 }
 243         else {
 244                 start = last = le2;
 245                 le2 = le2->next;
 246                 }
 247
 248         /* while the first loop != NULL, depending of the first element of second */
 249         /* loop, add new node to result list                                      */
 250         while (le1 != NULL) {
 251
 252                 if (le2 == NULL) {
 253                         last->next = le1;
 254                         break;
 255                         }
 256                 if (le1->node < le2->node) {
 257                         last->next = le1;
 258                         le1 = le1->next;
 259                         }
 260                 else if (le1->node == le2->node) {
 261                         last->next = le1;
 262                         le1 = le1->next;
 263                         le2 = le2->next;
 264                         last = last->next;
 265                         }
 266                 else {
 267                         last->next = le2;
 268                         le2 = le2->next;
 269                         last = last->next;
 270                         }
 271                 }
 272
 273         last->next = le2;
 274 }
 275
 276
 277 /*      This function is used to merge loops with the same header node to a single
 278         one. O(n^2) of number of loops. This merginig is necessary, because the loop
 279         finding algorith sometimes (eg. when loopbody ends with a if-else construct)
 280         reports a single loop as two loops with the same header node.
 281 */
 282 void analyze_double_headers()
 283 {
 284         int toCheck;
 285         struct LoopContainer *t1, *t2, *t3;
 286
 287         t1 = c_allLoops;
 288
 289         while (t1 != NULL)      {                       /* for all loops do                                                     */
 290                 toCheck = t1->loop_head;        /* get header node                                                      */
 291                 t2 = t1->next;
 292
 293                 while (t2 != NULL) {            /* compare it to headers of rest                        */
 294                         if (t2->loop_head == toCheck) {
 295
 296                                 /* found overlapping loops -> merge them together                               */
 297                                 /* printf("C_INFO: found overlapping loops - merging");         */
 298                                 analyze_merge(t1, t2);
 299
 300                                 /* remove second loop from the list     of all loops                            */
 301                                 t3 = t1;
 302                                 while (t3->next != t2)
 303                                         t3 = t3->next;
 304                                 t3->next = t2->next;
 305                                 }
 306                         t2 = t2->next;
 307                     }
 308
 309                 t1 = t1->next;
 310             }
 311 }
 312
 313
 314 /* After the hierarchie of loops has been built, we have to insert the exceptions
 315    into this tree. The exception ex is inserted into the subtree pointed to by
 316    LoopContainer lc.
 317 */
 318 void insert_exception(methodinfo *m, struct LoopContainer *lc, exceptiontable *ex)
 319 {
 320         struct LoopContainer *temp;
 321         struct LoopElement *le;
 322
 323 #ifdef LOOP_DEBUG
 324         /* printf("insert_exception called with %d-%d and loop %d\n", ex->start->debug_nr, ex->end->debug_nr, lc->loop_head); */
 325 #endif
 326
 327         /* if child node is reached immediately insert exception into the tree    */
 328         if (lc->tree_down == NULL) {
 329                 ex->next = lc->exceptions;
 330                 lc->exceptions = ex;
 331             }
 332         else {
 333         /* if we are inside the tree, there are two possibilities:                */
 334         /* 1. the exception is inside a nested loop or                            */
 335         /* 2. in the loop body of the current loop                                */
 336
 337                 /* check all children (= nested loops)                                */
 338                 temp = lc->tree_down;
 339
 340                 while (temp != NULL) {
 341
 342                         le = temp->nodes;
 343                         while (le != NULL) {
 344
 345 #ifdef LOOP_DEBUG
 346                                 printf("%d.%d\n", le->node, block_index[ex->startpc]);
 347 #endif
 348                                 /* if the start of the exception is part of the loop, the     */
 349                                 /* whole exception must be part of the loop                   */
 350                                 if (le->node == m->basicblockindex[ex->startpc])
 351                                         break;
 352                                 le = le->next;
 353                             }
 354
 355                         /* Exception is part of a nested loop (Case 1) -> insert it there */
 356                         if (le != NULL) {
 357                                 insert_exception(m, temp, ex);
 358                                 return;
 359                             }
 360                         else if ((temp->loop_head >= m->basicblockindex[ex->startpc]) && (temp->loop_head < m->basicblockindex[ex->endpc])) {
 361
 362                                 /* optimization: if nested loop is part of the exception, the */
 363                                 /* exception cannot be part of a differnet nested loop.       */
 364                                 ex->next = lc->exceptions;
 365                                 lc->exceptions = ex;
 366                                 return;
 367                             }
 368                         else
 369                                 temp = temp->tree_right;
 370                     }
 371
 372                 /* Exception is not contained in any nested loop (Case 2)             */
 373                 if (temp == NULL) {
 374                         ex->next = lc->exceptions;
 375                         lc->exceptions = ex;
 376                     }
 377             }
 378 }
 379
 380
 381 /*      This function builds a loop hierarchie. The header node of the innermost loop,
 382         each basic block belongs to, is stored in the array c_nestedLoops. The array
 383         c_hierarchie stores the relationship between differnt loops in as follows:
 384     Each loop, that is a nested loop, stores its direct surrounding loop as a
 385     parent. Top level loops have no parents.
 386 */
 387 void analyze_nested(methodinfo *m)
 388 {
 389         /* i/count/tmp are counters                                               */
 390         /* toOverwrite is used while loop hierarchie is built (see below)         */
 391         int i, header, toOverwrite, tmp, len;
 392
 393         /* first/last are used during topological sort to build ordered loop list */
 394         struct LoopContainer *first, *last, *start, *t, *temp;
 395
 396         /* Used to step through all nodes of a loop.                              */
 397         struct LoopElement *le;
 398
 399         /* init global structures                                                 */
 400         c_nestedLoops = DMNEW(int, m->basicblockcount);
 401         c_hierarchie = DMNEW(int, m->basicblockcount);
 402         for (i=0; i<m->basicblockcount; ++i) {
 403                 c_nestedLoops[i] = -1;
 404                 c_hierarchie[i] = -1;
 405             }
 406
 407         /* if there are no optimizable loops -> return                            */
 408         if (c_allLoops == NULL)
 409                 return;
 410
 411         temp = c_allLoops;
 412         while (temp != NULL) {              /* for all loops, do                  */
 413                 header = temp->loop_head;
 414
 415                 /* toOverwrite is number of current parent loop (-1 if none)          */
 416                 toOverwrite = c_nestedLoops[header];
 417
 418                 c_hierarchie[header] = toOverwrite;
 419
 420                 if (toOverwrite == header)      /* check for loops with same header   */
 421                         printf("C_ERROR: Loops have same header\n");
 422
 423                 le = temp->nodes;
 424                 while (le != NULL) {            /* for all loop nodes, do             */
 425                         tmp = c_nestedLoops[le->node];
 426
 427                     /* if node is part of parent loop -> overwrite it with nested     */
 428                         if (tmp == toOverwrite)
 429                                 c_nestedLoops[le->node] = header;
 430                         else {
 431                                 c_hierarchie[tmp] = header;
 432 #ifdef LOOP_DEBUG
 433                                 /* printf("set head of %d to %d", tmp, header);               */
 434 #endif
 435                             }
 436
 437                         le = le->next;
 438                         }
 439
 440                 temp = temp->next;
 441                 }
 442
 443         /* init root of hierarchie tree                                           */
 444         root = DMNEW(struct LoopContainer, 1);
 445         LoopContainerInit(m, root, -1);
 446
 447     /* obtain parent pointer and build hierarchie tree                        */
 448     start = c_allLoops;
 449     while (start != NULL) {
 450
 451                 /* look for parent of loop pointed at by start                        */
 452                 first = c_allLoops;
 453                 while (first != NULL) {
 454
 455                         /* the parent of the loop, pointed at by start has been found     */
 456                         if (first->loop_head == c_hierarchie[start->loop_head]) {
 457 #ifdef LOOP_DEBUG
 458                                 /* printf("set parent to pointer\n");                         */
 459 #endif
 460
 461                                 start->parent = first;
 462                                 start->tree_right = first->tree_down;
 463                                 first->tree_down = start;
 464
 465                                 break;
 466                             }
 467                         first = first->next;
 468                     }
 469
 470                 /* no parent loop found, set parent to root                           */
 471                 if (first == NULL) {
 472 #ifdef LOOP_DEBUG
 473                         /* printf("set parent to root\n");                                */
 474 #endif
 475
 476                         start->parent = root;
 477                         start->tree_right = root->tree_down;
 478                         root->tree_down = start;
 479                     }
 480                 /* if a parent exists, increase this nodes indegree                   */
 481                 else
 482                         start->parent->in_degree += 1;
 483
 484                 start = start->next;
 485             }
 486
 487         /* insert exceptions into tree                                            */
 488 #ifdef LOOP_DEBUG
 489         printf("--- Showing tree ---\n");
 490         show_tree(root, 0);
 491         printf(" --- End ---\n");
 492 #endif
 493         for (len = 0; len < m->exceptiontablelength; ++len)
 494                 insert_exception(m, root, m->exceptiontable + len);
 495
 496
 497         /* determine sequence of loops for optimization by topological sort       */
 498
 499         /* init queue                                                             */
 500         start = NULL;
 501         temp = c_allLoops;
 502         while (temp != NULL) {
 503
 504                 /* a loops with indegree == 0 are pushed onto the stack               */
 505                 if (temp->in_degree == 0) {
 506                         t = temp->next;
 507                         temp->next = start;
 508                         start = temp;
 509                         }
 510                 else
 511                         t = temp->next;
 512
 513                 temp = t;
 514                 }
 515
 516         /* sort loops                                                             */
 517         first = last = start;
 518         start = start->next;
 519
 520         if (last == NULL) {
 521                 printf("C_ERROR: loops are looped\n");
 522                 exit(-1);
 523             }
 524
 525         /* pop each node from the stack and decrease its parents indegree by one  */
 526         /* when the parents indegree reaches zero, push it onto the stack as well */
 527         if ((last->parent != root) && (--last->parent->in_degree == 0)) {
 528                 last->parent->next = start;
 529                 start = last->parent;
 530                 }
 531         while (start != NULL) {
 532
 533                 last->next = start;
 534
 535                 start = start->next;
 536                 last = last->next;
 537
 538                 if ((last->parent != root) && (--last->parent->in_degree == 0)) {
 539                         last->parent->next = start;
 540                         start = last->parent;
 541                         }
 542                 }
 543
 544         last->next = NULL;
 545         c_allLoops = first;
 546
 547 #ifdef LOOP_DEBUG
 548         printf("*** Hierarchie Results \n");
 549         while (first != NULL) {
 550                 printf("%d ", first->loop_head);
 551                 first = first->next;
 552             }
 553         printf("\n");
 554         fflush(stdout);
 555 #endif
 556 }
 557
 558 /*      This function is used to add variables that occur as index variables in
 559         array accesses (ARRAY_INDEX) or as variables, that change their value (VAR_MOD)
 560         to the list of interesting vars (c_loopvars) for the current loop.
 561 */
 562 void add_to_vars(int var, int type, int direction)
 563 {
 564         struct LoopVar *lv;
 565
 566         /* printf("Added to vars %d %d %d\n", var, type, direction);              */
 567         lv = c_loopvars;
 568         while (lv != NULL) {            /* check if var has been previously added */
 569                 if (lv->value == var) {
 570                         if (type == ARRAY_INDEX)
 571                                 lv->index = 1;              /* var is used as index           */
 572                         else if (type == VAR_MOD) {
 573                                 lv->modified = 1;           /* var is used in assignment      */
 574                                 switch (direction) {        /* how was var modified ?         */
 575                                 case D_UP:
 576                                         lv->static_u = 0;       /* incremented, no static upper   */
 577                                         break;                  /* bound can be guaranteeed       */
 578                                 case D_DOWN:
 579                                         lv->static_l = 0;       /* decremented, no static lower   */
 580                                         break;                  /* bound can be guaranteeed       */
 581                                 case D_UNKNOWN:
 582                                         lv->static_u = lv->static_l = 0;
 583                                         break;                  /* no info at all                 */
 584                                 default:
 585                                         printf("C_ERROR: unknown direction\n");
 586                                         break;
 587                                         }
 588                                 }
 589                         return;
 590                         }
 591                 lv = lv->next;
 592                 }
 593
 594         /* variable is not found in list -> add variable to list                                        */
 595         lv = DNEW(struct LoopVar);
 596
 597         lv->modified = lv->index = 0;
 598         lv->value = var;
 599
 600         if (type == ARRAY_INDEX) {
 601                 lv->index = 1;
 602                 lv->static_u = lv->static_l = 1;    /* arrayindex -> var not modified */
 603                 }
 604         else if (type == VAR_MOD) {
 605                 lv->modified = 1;
 606                 switch (direction) {                /* var used in assignment -> set  */
 607                 case D_UP:                          /* proper static bounds           */
 608                         lv->static_u = 0; lv->static_l = 1;
 609                         break;
 610                 case D_DOWN:
 611                         lv->static_u = 1; lv->static_l = 0;
 612                         break;
 613                 case D_UNKNOWN:
 614                         lv->static_u = lv->static_l = 0;
 615                         break;
 616                 default:
 617                         printf("C_ERROR: unknown direction\n");
 618                         break;
 619                         }
 620                 }
 621
 622         /* no dynamic bounds have been determined so far                          */
 623         lv->dynamic_l = lv->dynamic_l_v = lv->dynamic_u = lv->dynamic_u_v = 0;
 624
 625         lv->next = c_loopvars;                  /* add var to list                */
 626         c_loopvars = lv;
 627 }
 628
 629 /*      This function checks, whether a given loop with header node contains array
 630         accesses. If so, it returns 1, else it returns 0 and the loops needs no
 631         further consideration in the optimization process. When array accesses are
 632         found, a list of all variables, that are used as array index, is built and
 633         stored in c_loopvars. For all variables (integer), which values are changed,
 634         a flag in c_var_modified is set.
 635 */
 636 int analyze_for_array_access(methodinfo *m, int node)
 637 {
 638         basicblock bp;
 639         instruction *ip;
 640         int ic, i, access;
 641         struct depthElement *d;
 642         struct Trace *t;
 643
 644         if (c_toVisit[node] > 0) {          /* node has not been visited yet      */
 645                 c_toVisit[node] = 0;
 646
 647                 bp = m->basicblocks[node];               /* prepare an instruction scan        */
 648                 ip = bp.iinstr;
 649                 ic = bp.icount;
 650
 651                 access = 0;                     /* number of array accesses in loop   */
 652
 653                 for (i=0; i<ic; ++i, ++ip) {    /* for each instruction, check opcode */
 654                         switch (ip->opc) {
 655                         case ICMD_IASTORE:          /* array store                        */
 656                         case ICMD_LASTORE:
 657                         case ICMD_FASTORE:
 658                         case ICMD_DASTORE:
 659                         case ICMD_AASTORE:
 660                         case ICMD_BASTORE:
 661                         case ICMD_CASTORE:
 662                         case ICMD_SASTORE:
 663                                 t = tracing(&bp, i-1, 1);   /* try to identify index variable */
 664
 665                                 if (t->type == TRACE_IVAR) {
 666                                         /* if it is a variable, add it to list of index variables */
 667                                         add_to_vars(t->var, ARRAY_INDEX, D_UNKNOWN);
 668                                         access++;
 669                                 }
 670                                 else if (t->type == TRACE_ICONST)
 671                                         access++;
 672                                 break;
 673
 674                         case ICMD_IALOAD:                               /* array load                                           */
 675                     case ICMD_LALOAD:
 676                         case ICMD_FALOAD:
 677                         case ICMD_DALOAD:
 678                         case ICMD_AALOAD:
 679                         case ICMD_BALOAD:
 680                         case ICMD_CALOAD:
 681                         case ICMD_SALOAD:
 682                                 t = tracing(&bp, i-1, 0);   /* try to identify index variable */
 683
 684                                 if (t->type == TRACE_IVAR) {
 685                                         /* if it is a variable, add it to list of index variables */
 686                                         add_to_vars(t->var, ARRAY_INDEX, D_UNKNOWN);
 687                                         access++;
 688                                         }
 689                                 else if (t->type == TRACE_ICONST)
 690                                         access++;
 691                                 break;
 692
 693                         case ICMD_ISTORE:                               /* integer store                                        */
 694                                 c_var_modified[ip->op1] = 1;
 695
 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(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(t->var, VAR_MOD, D_DOWN);
 705                                         else
 706                                                 add_to_vars(t->var, VAR_MOD, D_UNKNOWN);
 707                                         }
 708                                 else
 709                                         add_to_vars(ip->op1, VAR_MOD, D_UNKNOWN);
 710                                 break;
 711
 712                         case ICMD_IINC:                                 /* simple add/sub of a constant         */
 713                                 c_var_modified[ip->op1] = 1;
 714
 715                                 if (ip->val.i > 0)
 716                                         add_to_vars(ip->op1, VAR_MOD, D_UP);
 717                                 else
 718                                         add_to_vars(ip->op1, VAR_MOD, D_DOWN);
 719                                 break;
 720
 721                         case ICMD_LSTORE:
 722                         case ICMD_FSTORE:
 723                         case ICMD_DSTORE:
 724                         case ICMD_ASTORE:
 725                                 c_var_modified[ip->op1] = 1;
 726                                 break;
 727                         }
 728                 }
 729
 730                 d = c_dTable[node];
 731                 while (d != NULL) {                                     /* check all successors of block        */
 732                         access += analyze_for_array_access(m, d->value);
 733                         d = d->next;
 734                         }
 735
 736                 return access;
 737                 }
 738         else
 739                 return 0;
 740 }
 741
 742 /*      This function scans the exception graph structure to find modifications of
 743         array index variables of the current loop. If any modifications are found,
 744         1 is returned, else 0.
 745 */
 746 int quick_scan(methodinfo *m, int node)
 747 {
 748         basicblock bp;
 749         instruction *ip;
 750         int count, i;
 751         struct LoopVar *lv;
 752         struct depthElement *d;
 753
 754         /*  printf("QS: %d - %d\n", node, c_exceptionVisit[node]);                                      */
 755
 756
 757         if (c_exceptionVisit[node] > 0) {       /* node is part of exception graph              */
 758                 c_exceptionVisit[node] = -1;
 759
 760                 bp = m->basicblocks[node];                              /* setup scan of all instructions               */
 761                 ip = bp.iinstr;
 762                 count = bp.icount;
 763
 764                 for (i=0; i<count; ++i, ++ip) { /* for each instruction do                              */
 765                         switch (ip->opc) {
 766                         case ICMD_ISTORE:
 767                         case ICMD_IINC:                         /* a variable is modified                               */
 768
 769                                 lv = c_loopvars;                /* is it an array index var ?                   */
 770                                 while (lv != NULL) {
 771                                         if ((lv->index) && (lv->value == ip->op1))
 772                                                 return 1;               /* yes, so return 1                                             */
 773                                         lv = lv->next;
 774                                         }
 775                                 break;
 776                                 }
 777                         }
 778
 779             d = c_exceptionGraph[node];         /* check all successor nodes                    */
 780                 while (d != NULL) {
 781                         if (quick_scan(m, d->value) > 0)
 782                                 return 1;                               /* if an access is found return 1               */
 783                         d = d->next;
 784                         }
 785
 786                 return 0;                                               /* nothing found, so return 0                   */
 787                 }
 788         else
 789                 return 0;
 790 }
 791
 792 /*      This function returns 1, when the condition of the loop contains
 793         or statements or when an array index variable is modified in any
 794         catch block within the loop.
 795 */
 796 int analyze_or_exceptions(methodinfo *m, int head, struct LoopContainer *lc)
 797 {
 798         struct depthElement *d;
 799         int i, k, value, flag, count;
 800         struct LoopElement *le;
 801
 802         d = c_dTable[head];
 803         count = flag = 0;
 804
 805         /* analyze for or-statements                                                                                            */
 806 #ifdef LOOP_DEBUG
 807         printf("*** Analyze for OR ... ");
 808         fflush(stdout);
 809 #endif
 810
 811         while (d != NULL) {                             /* for all successor nodes check if they        */
 812                 value = d->value;                       /* are part of the loop                                         */
 813
 814                 le = lc->nodes;
 815
 816                 while (le != NULL) {
 817                         if (le->node == value)
 818                                 break;
 819                         le = le->next;
 820                         }
 821
 822                 if (le == NULL)                         /* node is not part of the loop                         */
 823                         ++flag;
 824
 825                 d = d->next;
 826                 ++count;
 827                 }
 828
 829         if ((count > 1) && (flag == 0)){/* if all successors part of the loop, exit */
 830 #ifdef STATISTICS
 831                 c_stat_or++;
 832 #endif
 833                 return 0;
 834                 }
 835
 836         /* check for exceptions */
 837         /* printf("done\n*** Analyze for EXCEPTIONS(%d) . ", m->exceptiontablelength);  */
 838
 839         if (!m->exceptiontablelength)           /* when there are no exceptions, exit           */
 840                 return 1;
 841
 842         if ((c_exceptionGraph = (struct depthElement **) malloc(sizeof(struct depthElement *) * m->basicblockcount)) == NULL)
 843                 c_mem_error();
 844         if ((c_exceptionVisit = (int *) malloc(sizeof(int) * m->basicblockcount)) == NULL)
 845                 c_mem_error();
 846
 847         for (k=0; k<m->basicblockcount; ++k) {
 848                 c_exceptionVisit[k] = -1;
 849                 c_exceptionGraph[k] = NULL;
 850                 }
 851
 852
 853         /* for all nodes that start catch block check whether they are part of loop     */
 854         for (i = 0; i < c_old_xtablelength; i++) {
 855                 value = m->basicblockindex[m->exceptiontable[i].startpc];
 856
 857                 le = lc->nodes;
 858                 while (le != NULL) {
 859
 860                         if (le->node == value)  {                       /* exception is in loop                 */
 861 #ifdef LOOP_DEBUG
 862                                 printf("C_INFO: Loop contains exception\n");
 863                                 fflush(stdout);
 864 #endif
 865
 866                                 /* build a graph structure, that contains all nodes that are    */
 867                                 /* part of the catc block                                                                               */
 868                                 dF_Exception(m, -1, m->basicblockindex[m->exceptiontable[i].handlerpc]);
 869
 870                                 /* if array index variables are modified there, return 0                */
 871                                 if (quick_scan(m, m->basicblockindex[m->exceptiontable[i].handlerpc]) > 0) {
 872 #ifdef STATISTICS
 873                                         c_stat_exception++;
 874 #endif
 875                                         /* printf("C_INFO: loopVar modified in exception\n");           */
 876                                         return 0;
 877                                         }
 878                                 }
 879                         le = le->next;
 880                         }
 881                 }
 882
 883 #ifdef LOOP_DEBUG
 884         printf("none ... done\n");
 885         fflush(stdout);
 886 #endif
 887         return 1;
 888 }
 889
 890 /*      This function sets a flag in c_var_modified for all variables that have
 891         been found as part of an assigment in the loop.
 892 */
 893 void scan_global_list()
 894 {
 895         struct LoopVar *lv;
 896         lv = c_loopvars;
 897
 898         while (lv != NULL) {
 899                 if (lv->modified)
 900                         c_var_modified[lv->value] = 1;
 901                 lv = lv->next;
 902                 }
 903 }
 904
 905 /*      This function analyses the condition in the loop header and trys to find
 906         out, whether some dynamic guarantees can be set up.
 907 */
 908 void init_constraints(methodinfo *m, int head)
 909 {
 910         basicblock bp;
 911         instruction *ip;
 912         int ic, l_mod, r_mod, changed, operand;
 913         struct Trace *left, *right, *th;
 914         struct LoopVar *lv_left, *lv_right, *lh;
 915
 916         bp = m->basicblocks[head];
 917         ic = bp.icount;
 918         ip = bp.iinstr+(ic-1);  /* set ip to last instruction in header node            */
 919
 920         switch (ip->opc) {              /* check op-code                                                                        */
 921
 922         /* comparison against constant value                                                                            */
 923         case ICMD_IFEQ:                 /* ..., value ==> ...                                                           */
 924         case ICMD_IFLT:         /* ..., value ==> ...                                                           */
 925         case ICMD_IFLE:         /* ..., value ==> ...                                                           */
 926         case ICMD_IFGT:         /* ..., value ==> ...                                                           */
 927         case ICMD_IFGE:         /* ..., value ==> ...                                                           */
 928                                                         /* op1 = target JavaVM pc, val.i = constant                     */
 929
 930                 left = tracing(&bp, ic-2, 0);   /* analyse left arg., right is constant */
 931                 right = create_trace(TRACE_ICONST, -1, ip->val.i, 0);
 932                 break;
 933
 934         /* standard comparison                                                                                                          */
 935         case ICMD_IF_ICMPEQ:    /* ..., value, value ==> ...                                            */
 936         case ICMD_IF_ICMPLT:    /* ..., value, value ==> ...                                            */
 937         case ICMD_IF_ICMPGT:    /* ..., value, value ==> ...                                            */
 938         case ICMD_IF_ICMPLE:    /* ..., value, value ==> ...                                            */
 939         case ICMD_IF_ICMPGE:    /* ..., value, value ==> ...                                            */
 940
 941                 left = tracing(&bp, ic-2, 1);   /* get left and right argument                  */
 942                 right = tracing(&bp, ic-2, 0);
 943                 break;
 944
 945         /* other condition                                                                                                                      */
 946         default:
 947                 left = create_trace(TRACE_UNKNOWN, -1, 0, 0);
 948                 right = create_trace(TRACE_UNKNOWN, -1, 0, 0);
 949                 break;
 950                 }
 951
 952         /* analyse left and right side of comparison                                                            */
 953         l_mod = r_mod = 0;
 954
 955         if (left->type == TRACE_IVAR) { /* is a loop variable on left side ?            */
 956                 lv_left = c_loopvars;
 957                 while (lv_left != NULL) {
 958                         if (lv_left->value == left->var) {
 959                                 l_mod = lv_left->modified;      /* yes, but has it been modified ?      */
 960                                 break;
 961                                 }
 962                         lv_left = lv_left->next;
 963                         }
 964                 }
 965
 966         if (right->type == TRACE_IVAR){ /* is a loop variable on right side ?           */
 967                 lv_right = c_loopvars;
 968                 while (lv_right != NULL) {
 969                         if (lv_right->value == right->var) {
 970                                 r_mod = lv_right->modified;     /* yes, but has it been modified ?      */
 971                                 break;
 972                                 }
 973                         lv_right = lv_right->next;
 974                         }
 975                 }
 976
 977         if ((l_mod - r_mod) == 0) {             /* both 1 or both 0 -> no dynamic contraints*/
 978                 c_rightside = NULL;                     /* possible                                                                     */
 979                 return;
 980                 }
 981
 982         /* to simplify processing, make the left side the one, that contains the        */
 983         /* modified variable                                                                                                            */
 984         if (r_mod > l_mod) {
 985                 th = left;    left = right;        right = th;
 986                 lh = lv_left; lv_left = lv_right;  lv_right = lh;
 987                 changed = 1;                            /* set changed to true                                          */
 988                 }
 989         else
 990                 changed = 0;                            /* no change needed                                                     */
 991
 992         /* make sure that right side's value does not change during loop execution      */
 993         if (right->type == TRACE_UNKNOWN) {
 994                 c_rightside = NULL;
 995                 return;
 996                 }
 997
 998         /* determine operands:                                                                                                          */
 999         /* for further explaination a is modified, b nonmodified var                            */
1000         switch (ip->opc) {              /* check opcode again                                                           */
1001         case ICMD_IFEQ:         /* ..., value ==> ...                                                           */
1002         case ICMD_IF_ICMPEQ:    /* ..., value, value ==> ...                                            */
1003                 operand = OP_EQ;                                /* a == b                                                               */
1004                 break;
1005
1006         case ICMD_IFLE:         /* ..., value ==> ...                                                           */
1007         case ICMD_IF_ICMPLE:    /* ..., value, value ==> ...                                            */
1008                 if (changed)
1009                         operand = OP_GE;                        /* b<=a         -> a>=b                                         */
1010                 else {
1011                         operand = OP_LT;                        /* a<=b         -> a<(b+1)                                      */
1012                         if (left->constant != 0)
1013                                 left->constant -= 1;
1014                         else
1015                                 right->constant += 1;
1016                         }
1017                 break;
1018
1019         case ICMD_IFLT:         /* ..., value ==> ...                                                           */
1020         case ICMD_IF_ICMPLT:    /* ..., value, value ==> ...                                            */
1021                 if (changed) {
1022                         operand = OP_GE;                        /* b<a          -> a>=(b+1)                                     */
1023                         if (left->constant != 0)
1024                                 left->constant -= 1;
1025                         else
1026                                 right->constant += 1;
1027                         }
1028                 else
1029                         operand = OP_LT;                        /* a<b          -> a<b                                          */
1030                 break;
1031
1032         case ICMD_IFGT:         /* ..., value ==> ...                                                           */
1033         case ICMD_IF_ICMPGT:    /* ..., value, value ==> ...                                            */
1034                 if (changed)
1035                         operand = OP_LT;                        /* b>a          -> a<b                                          */
1036                 else {
1037                         operand = OP_GE;                        /* a>b          ->      a>=(b+1)                                */
1038                         if (left->constant != 0)
1039                                 left->constant -= 1;
1040                         else
1041                                 right->constant += 1;
1042                         }
1043                 break;
1044
1045         case ICMD_IFGE:         /* ..., value ==> ...                                                           */
1046         case ICMD_IF_ICMPGE:    /* ..., value, value ==> ...                                            */
1047                 if (changed) {
1048                         operand = OP_LT;                        /* b>=a         -> a<(b+1)                                      */
1049                         if (left->constant != 0)
1050                                 left->constant -= 1;
1051                         else
1052                                 right->constant += 1;
1053                         }
1054                 else
1055                         operand = OP_GE;                        /* a>=b         -> a>=b                                         */
1056                 break;
1057
1058         default:
1059                 printf("C_ERROR: debugging error 0x00\n");
1060                 }
1061
1062
1063         /* NOW: left/lv_left -> loopVar                                                                                         */
1064         /*              right/lv_right -> const, nonmod. var, arraylength                                       */
1065         switch (operand) {                                      /* check operand                                                */
1066         case OP_EQ:
1067                 lv_left->dynamic_u_v = 1;               /* upper + lower bound tested                   */
1068                 lv_left->dynamic_l_v = 1;
1069
1070                 lv_left->dynamic_l = lv_left->dynamic_u = left->constant;
1071                 break;
1072
1073         case OP_LT:
1074                 lv_left->dynamic_u_v = 1;               /* upper bound tested                                   */
1075
1076                 lv_left->dynamic_u = left->constant;
1077                 break;
1078
1079         case OP_GE:
1080                 lv_left->dynamic_l_v = 1;               /* lower bound tested                                   */
1081
1082                 lv_left->dynamic_l = left->constant;
1083                 break;
1084
1085         default:
1086                 printf("C_ERROR: debugging error 0x01\n");
1087                 }
1088
1089         c_rightside = right;
1090
1091         switch (c_rightside->type) {
1092         case TRACE_ICONST:
1093                 c_rs_needed_instr = 1;
1094                 break;
1095         case TRACE_ALENGTH:
1096                 c_rs_needed_instr = 2;
1097                 break;
1098         case TRACE_IVAR:
1099                 c_rs_needed_instr = 3;
1100                 break;
1101         default:
1102                 printf("C_ERROR: wrong right-side type\n");
1103                 }
1104 }
1105
1106 /*      This function is needed to add and record new static tests (before loop
1107         entry) of variables to make guaratees for index variables. type states
1108         the kind of the test. arrayRef is the array, which length is tested
1109         against, varRef is the variable, that is testes and constant is the
1110         constant value, that is tested.
1111 */
1112 void add_new_constraint(methodinfo *m, int type, int arrayRef, int varRef, int constant)
1113 {
1114         struct Constraint *tc;
1115
1116         switch (type) {
1117         case TEST_ZERO:                                 /* a variable is tested against a const         */
1118
1119                 tc = c_constraints[varRef];     /* does a test already exist for this var ?     */
1120                 while (tc != NULL) {
1121                         if (tc->type == TEST_ZERO) {
1122                                 if (constant < tc->constant)
1123                                         tc->constant = constant;
1124                                 return;                         /* yes. update constant and return                      */
1125                                 }
1126                                 tc = tc->next;
1127                         }
1128
1129                 /* insert a new test for this variable                                                                  */
1130                 if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
1131                         c_mem_error();
1132                 tc->type     = TEST_ZERO;
1133                 tc->varRef   = varRef;
1134                 tc->constant = constant;
1135                 tc->next     = c_constraints[varRef];
1136                 c_constraints[varRef] = tc;
1137                 c_needed_instr += 3;
1138
1139                 break;
1140
1141         case TEST_ALENGTH:                              /* variable is tested against array length      */
1142
1143                 tc = c_constraints[varRef];     /* does a test already exist for this var ?     */
1144                 while (tc != NULL) {
1145                         if ((tc->type == TEST_ALENGTH) && (tc->arrayRef == arrayRef)) {
1146                                 if (constant > tc->constant)
1147                                         tc->constant = constant;
1148                                 return;                         /* yes. update constant and return                      */
1149                                 }
1150                         tc = tc->next;
1151                         }
1152
1153                 /* insert a new test for this variable                                                                  */
1154                 if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
1155                         c_mem_error();
1156                 tc->type         = TEST_ALENGTH;
1157                 tc->arrayRef = arrayRef;
1158                 tc->varRef   = varRef;
1159                 tc->constant = constant;
1160                 tc->next     = c_constraints[varRef];
1161                 c_constraints[varRef] = tc;
1162                 c_needed_instr += 6;
1163
1164                 /* if arrayRef is not already tested against null, insert that test     */
1165                 if (!(c_null_check[arrayRef])) {
1166                         c_null_check[arrayRef] = 1;
1167                         c_needed_instr +=2;
1168                     }
1169
1170                 break;
1171
1172         case TEST_CONST_ZERO:
1173                 /* done earlier                                                                                                                 */
1174                 break;
1175
1176         case TEST_CONST_ALENGTH:                /* a const is tested against array length       */
1177
1178                 /* does a test already exist for this array                                                             */
1179                 tc = c_constraints[m->maxlocals];
1180                 while (tc != NULL) {
1181                         if ((tc->type == TEST_CONST_ALENGTH) && (tc->arrayRef == arrayRef)) {
1182                                 if (constant > tc->constant)
1183                                         tc->constant = constant;
1184                                 return;                         /* yes. update constant and return                      */
1185                                 }
1186                         tc = tc->next;
1187                         }
1188
1189                 /* insert a new test for this array                                                                             */
1190                 if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
1191                         c_mem_error();
1192                 tc->type         = TEST_CONST_ALENGTH;
1193                 tc->arrayRef = arrayRef;
1194                 tc->constant = constant;
1195                 tc->next     = c_constraints[m->maxlocals];
1196                 c_constraints[m->maxlocals] = tc;
1197                 c_needed_instr += 4;
1198
1199                 /* if arrayRef is not already tested against null, insert that test     */
1200                 if (!(c_null_check[arrayRef])) {
1201                         c_null_check[arrayRef] = 1;
1202                         c_needed_instr +=2;
1203                     }
1204
1205                 break;
1206
1207         case TEST_UNMOD_ZERO:                   /* test unmodified var against constant         */
1208
1209                 /* search if test already exists                                                                                */
1210                 tc = c_constraints[varRef];
1211                 while (tc != NULL) {
1212                         if (tc->type == TEST_UNMOD_ZERO) {
1213                                 if (constant < tc->constant)
1214                                         tc->constant = constant;
1215                                 return;                         /* yes, so update constant                                      */
1216                                 }
1217                         tc = tc->next;
1218                         }
1219
1220                 /* else, a new test is inserted                                                                                 */
1221                 if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
1222                         c_mem_error();
1223                 tc->type         = TEST_UNMOD_ZERO;
1224                 tc->varRef   = varRef;
1225                 tc->constant = constant;
1226                 tc->next     = c_constraints[varRef];
1227                 c_constraints[varRef] = tc;
1228                 c_needed_instr += 3;
1229
1230                 break;
1231
1232         case TEST_UNMOD_ALENGTH:                /* test unmodified var against array length     */
1233
1234                 /* search if test alreay exists                                                                                 */
1235                 tc = c_constraints[varRef];
1236                 while (tc != NULL) {
1237                         if ((tc->type == TEST_UNMOD_ALENGTH) && (tc->arrayRef == arrayRef)) {
1238                                 if (constant > tc->constant)
1239                                         tc->constant = constant;
1240                                 return;                         /* yes, so modify constants                                     */
1241                                 }
1242                         tc = tc->next;
1243                         }
1244
1245                 /* create new entry                                                                                                             */
1246                 if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
1247                         c_mem_error();
1248                 tc->type         = TEST_UNMOD_ALENGTH;
1249                 tc->varRef   = varRef;
1250                 tc->arrayRef = arrayRef;
1251                 tc->constant = constant;
1252                 tc->next     = c_constraints[varRef];
1253                 c_constraints[varRef] = tc;
1254                 c_needed_instr += 6;
1255
1256                 /* if arrayRef is not already tested against null, insert that test     */
1257                 if (!(c_null_check[arrayRef])) {
1258                         c_null_check[arrayRef] = 1;
1259                         c_needed_instr +=2;
1260                     }
1261
1262                 break;
1263
1264         case TEST_RS_ZERO:                              /* test right side of the loop condition        */
1265                                                                         /* against a constant - needed by dynamic       */
1266                                                                         /* checks                                                                       */
1267                 /*!! varRef -> maxlocals */
1268                 /* search if test already exists                                                                                */
1269                 tc = c_constraints[m->maxlocals];
1270                 while (tc != NULL) {
1271                         if (tc->type == TEST_RS_ZERO) {
1272                                 if (constant < tc->constant)
1273                                         tc->constant = constant;
1274                                 return;                         /* yes, so modify constants                                     */
1275                                 }
1276                         tc = tc->next;
1277                         }
1278
1279                 /* create new entry                                                                                                             */
1280                 if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
1281                         c_mem_error();
1282                 tc->type     = TEST_RS_ZERO;
1283                 tc->constant = constant;
1284                 tc->next     = c_constraints[m->maxlocals];
1285                 c_constraints[m->maxlocals] = tc;
1286                 c_needed_instr += (2 + c_rs_needed_instr);
1287
1288                 /* if arrayRef on right side is not already tested against null,        */
1289                 /* insert that test                                                     */
1290                 if ((c_rightside->type == TRACE_ALENGTH) && (!(c_null_check[c_rightside->var]))) {
1291                         c_null_check[c_rightside->var] = 1;
1292                         c_needed_instr +=2;
1293                     }
1294
1295                 break;
1296
1297         case TEST_RS_ALENGTH:                   /* test right side of the loop condition        */
1298                                                                         /* against array length - needed by dynamic     */
1299                                                                         /* checks                                                                       */
1300                 /*!! varRef -> maxlocals */
1301                 /* search if test already exists                                                                                */
1302                 tc = c_constraints[m->maxlocals];
1303                 while (tc != NULL)
1304                 {
1305                         if ((tc->type == TEST_RS_ALENGTH) && (tc->arrayRef == arrayRef))
1306                         {
1307                                 if (constant > tc->constant)
1308                                         tc->constant = constant;
1309                                 return;                         /* yes, so modify constants                                     */
1310                         }
1311                         tc = tc->next;
1312                 }
1313
1314                 /* create new entry                                                                                                             */
1315                 if ((tc = (struct Constraint *) malloc(sizeof(struct Constraint))) == NULL)
1316                         c_mem_error();
1317                 tc->type         = TEST_RS_ALENGTH;
1318                 tc->arrayRef = arrayRef;
1319                 tc->constant = constant;
1320                 tc->next     = c_constraints[m->maxlocals];
1321                 c_constraints[m->maxlocals] = tc;
1322                 c_needed_instr += (3 + c_rs_needed_instr);
1323
1324                 /* if arrayRef is not already tested against null, insert that test     */
1325                 if (!(c_null_check[arrayRef])) {
1326                         c_null_check[arrayRef] = 1;
1327                         c_needed_instr +=2;
1328                     }
1329
1330                 /* if arrayRef on right side is not already tested against null,        */
1331                 /* insert that test                                                     */
1332                 if ((c_rightside->type == TRACE_ALENGTH) && (!(c_null_check[c_rightside->var]))) {
1333                         c_null_check[c_rightside->var] = 1;
1334                         c_needed_instr +=2;
1335                     }
1336                 break;
1337
1338         }
1339 }
1340
1341 /*      This functions adds new static (before loop enry) tests of variables to the
1342         program to be able to guarantee certain values for index variables in array
1343         access (to safely remove bound checks).
1344 */
1345 int insert_static(methodinfo *m, int arrayRef, struct Trace *index, struct Changes *varChanges, int special)
1346 {
1347         struct LoopVar *lv;
1348         int varRef;
1349         int high, low;
1350
1351         /* printf("insert static check - %d\n", arrayRef);
1352            show_trace(index);
1353            show_change(varChanges);
1354         */
1355
1356         if (varChanges == NULL) {                       /* the variable hasn't changed / const  */
1357                 if ((varChanges = (struct Changes *) malloc(sizeof(struct Changes))) == NULL)
1358                         c_mem_error();
1359                 varChanges->lower_bound = varChanges->upper_bound = 0;
1360                 }
1361
1362         switch (index->type) {                          /* check index type                                             */
1363         case TRACE_IVAR:                                        /* it is a variable                                             */
1364                 if (index->neg < 0) {                   /* if it's a negated var, return                */
1365 #ifdef STATISTICS
1366                         c_stat_no_opt++;
1367 #endif
1368                         return OPT_NONE;
1369                         }
1370
1371                 varRef = index->var;
1372                 high = low = 0;
1373
1374                 if (c_var_modified[varRef])     {       /* volatile var                                                 */
1375
1376                         lv = c_loopvars;                        /* get reference to loop variable               */
1377
1378                         while ((lv != NULL) && (lv->value != varRef))
1379                                 lv = lv->next;
1380                         if (lv == NULL)
1381                           printf("C_ERROR: debugging error 0x02\n");
1382
1383                         /* show_varinfo(lv);                                                                                            */
1384
1385                         /* check existing static bounds and add new contraints on variable      */
1386                         /* to possibly remove bound checks                                                                      */
1387                         if (lv->static_l) {
1388                                 /* the var is never decremented, so we add a static test againt */
1389                                 /* constant                                                                                                             */
1390                                 if (varChanges->lower_bound > varChanges->upper_bound)
1391                                         add_new_constraint(m, TEST_ZERO, arrayRef, varRef, index->constant);
1392                                 else
1393                                         add_new_constraint(m, TEST_ZERO, arrayRef, varRef, varChanges->lower_bound+index->constant);
1394                                 low = 1;
1395                                 }
1396                         else if ((lv->dynamic_l_v) && (!special)) {
1397                                 /* the variable is decremented, but it is checked against a             */
1398                                 /* bound in the loop condition                                                                  */
1399                                 if (varChanges->lower_bound <= varChanges->upper_bound) {
1400                                         add_new_constraint(m, TEST_RS_ZERO, arrayRef, varRef, varChanges->lower_bound+index->constant+lv->dynamic_l);
1401                                         low = 1;
1402                                         }
1403                                 }
1404
1405                         if (lv->static_u) {
1406                                 /* the var is never incremented, so we add a static test againt */
1407                                 /* constant                                                                                                             */
1408                                 if (varChanges->lower_bound > varChanges->upper_bound)
1409                                         add_new_constraint(m, TEST_ALENGTH, arrayRef, varRef, index->constant);
1410                                 else
1411                                         add_new_constraint(m, TEST_ALENGTH, arrayRef, varRef, varChanges->upper_bound+index->constant);
1412                                 high = 1;
1413                                 }
1414                         else if ((lv->dynamic_u_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, TEST_RS_ALENGTH, arrayRef, varRef, varChanges->upper_bound+index->constant+lv->dynamic_u);
1419                                         high = 1;
1420                                         }
1421                                 }
1422                         }
1423                 else {                                                  /* the var is never modified at all             */
1424                         add_new_constraint(m, TEST_UNMOD_ZERO, arrayRef, index->var, index->constant);
1425                         add_new_constraint(m, TEST_UNMOD_ALENGTH, arrayRef, index->var, index->constant);
1426                         low = high = 1;
1427                         }
1428
1429                 /* if the addition of new variable tests made guarantees possible,              */
1430                 /* return the best possible optimization                                                                */
1431                 if ((high > 0) && (low > 0)) {
1432                         /* printf("fully optimzed\n");                                                                          */
1433 #ifdef STATISTICS
1434                         c_stat_full_opt++;
1435 #endif
1436                         return OPT_FULL;
1437                         }
1438                 else if (high > 0) {
1439                         /* printf("upper optimzed\n");                                                                          */
1440 #ifdef STATISTICS
1441                         c_stat_upper_opt++;
1442 #endif
1443                         return OPT_UPPER;
1444                         }
1445                 else if (low > 0) {
1446                         /* printf("lower optimzed\n");                                                                          */
1447 #ifdef STATISTICS
1448                         c_stat_lower_opt++;
1449 #endif
1450                         return OPT_LOWER;
1451                         }
1452                 else {
1453                         /* printf("not optimzed\n");                                                                            */
1454 #ifdef STATISTICS
1455                         c_stat_no_opt++;
1456 #endif
1457                         return OPT_NONE;
1458                         }
1459                 break;
1460
1461         case TRACE_ICONST:                      /* if it is a constant, optimization is easy    */
1462                 if (index->constant < 0) {
1463 #ifdef STATISTICS
1464                         c_stat_no_opt++;
1465 #endif
1466                         return OPT_NONE;        /* negative index -> bad                                                */
1467                         }
1468                 else {
1469                         add_new_constraint(m, TEST_CONST_ALENGTH, arrayRef, 0, index->constant);
1470 #ifdef STATISTICS
1471                         c_stat_full_opt++;
1472 #endif
1473                         return OPT_FULL;        /* else just test constant against array length */
1474                         }
1475                 break;
1476
1477         case TRACE_ALENGTH:                     /* else, no optimizations possible                              */
1478         case TRACE_UNKNOWN:
1479         case TRACE_AVAR:
1480 #ifdef STATISTICS
1481                 c_stat_no_opt++;
1482 #endif
1483                 return OPT_NONE;
1484         }
1485
1486         /* keep compiler happy */
1487         return 0;
1488 }
1489
1490
1491
1492 /*      copy a stack and return the start pointer of the newly created one
1493 */
1494 stackptr copy_stack_from(stackptr source) {
1495         stackptr current, top;
1496
1497         if (source == NULL)
1498                 return NULL;
1499
1500         /* copy first element                                                       */
1501         current = DMNEW(stackelement, 1);
1502         current->type = source->type;
1503         current->flags = source->flags;
1504         current->varkind = source->varkind;
1505         current->varnum = source->varnum;
1506         current->regoff = source->regoff;
1507
1508         top = current;
1509
1510         /* if there exist more, then copy the rest                                  */
1511         while (source->prev != NULL) {
1512                 source = source->prev;
1513                 current->prev = DMNEW(stackelement, 1);
1514                 current->type = source->type;
1515                 current->flags = source->flags;
1516                 current->varkind = source->varkind;
1517                 current->varnum = source->varnum;
1518                 current->regoff = source->regoff;
1519                 current = current->prev;
1520                 }
1521
1522         current->prev = NULL;
1523         return top;
1524 }
1525
1526
1527 /* The following defines are used in the procedure void create_static_checks(...)
1528    They add a new instruction with its corresponding stack manipulation and
1529    are used to build the new loop header of an optimized loop, where we have
1530    to check certain variables and constants against values to guarantee that
1531    index values in array accesses remain with array bounds.
1532
1533    inst: pointer to the new instruction
1534    tos: stackpointer before this operation is executed
1535    newstack: temporary stackptr
1536    stackdepth: counts the current stackdepth
1537    original start: blockpointer to the head of the new, optimized loop
1538 */
1539
1540 /* Load a local integer variable v                                              */
1541 #define LOAD_VAR(v) { \
1542         inst->opc = ICMD_ILOAD; \
1543         inst->op1 = v; \
1544         newstack = DMNEW(stackelement, 1); \
1545     inst->dst = newstack; \
1546         newstack->prev = tos; \
1547         newstack->type = TYPE_INT; \
1548         newstack->flags = 0; \
1549         newstack->varkind = LOCALVAR; \
1550         newstack->varnum = v; \
1551         tos = newstack; \
1552         inst++; \
1553         stackdepth++; \
1554         }
1555
1556 /* Load a constant with value c                                                 */
1557 #define LOAD_CONST(c) { \
1558         inst->opc = ICMD_ICONST; \
1559         inst->op1 = 0; \
1560         inst->val.i = (c); \
1561         newstack = DMNEW(stackelement, 1); \
1562         newstack->prev = tos; \
1563         newstack->type = TYPE_INT; \
1564         newstack->flags = 0; \
1565         newstack->varkind = UNDEFVAR; \
1566         newstack->varnum = stackdepth; \
1567         tos = newstack; \
1568         inst->dst = tos; \
1569         inst++; \
1570         stackdepth++; \
1571         }
1572
1573 /* Load a local reference (adress) variable a                                   */
1574 #define LOAD_ADDR(a) { \
1575         inst->opc = ICMD_ALOAD; \
1576         inst->op1 = a; \
1577         newstack = DMNEW(stackelement, 1); \
1578         newstack->prev = tos; \
1579         newstack->type = TYPE_ADR; \
1580         newstack->flags = 0; \
1581         newstack->varkind = LOCALVAR; \
1582         newstack->varnum = a; \
1583         tos = newstack; \
1584         inst->dst = tos; \
1585         inst++; \
1586         stackdepth++; \
1587         }
1588
1589 /* Insert a compare greater-or-equal and jump to the unoptimized loop, if the   */
1590 /* comparison is true                                                           */
1591 #define GOTO_NOOPT_IF_GE { \
1592         inst->opc = ICMD_IF_ICMPGE; \
1593     inst->target = original_start->copied_to; \
1594         if (tos->varkind == UNDEFVAR) \
1595                 tos->varkind = TEMPVAR;  \
1596     tos = tos->prev; \
1597     if (tos->varkind == UNDEFVAR) \
1598                 tos->varkind = TEMPVAR;  \
1599     tos = tos->prev; \
1600         inst->dst = tos; \
1601         inst++; \
1602         stackdepth -= 2; \
1603         }
1604
1605 /* Insert a compare greater than and jump to the unoptimized loop, if the       */
1606 /* comparison is true                                                           */
1607 #define GOTO_NOOPT_IF_GT { \
1608         inst->opc = ICMD_IF_ICMPGT; \
1609     inst->target = original_start->copied_to; \
1610         if (tos->varkind == UNDEFVAR) \
1611                 tos->varkind = TEMPVAR;  \
1612     tos = tos->prev; \
1613     if (tos->varkind == UNDEFVAR) \
1614                 tos->varkind = TEMPVAR;  \
1615     tos = tos->prev; \
1616         inst->dst = tos; \
1617         inst++; \
1618         stackdepth -= 2; \
1619         }
1620
1621
1622 /* Insert a compare less-than and jump to the unoptimized loop, if the          */
1623 /* comparison is true                                                           */
1624 #define GOTO_NOOPT_IF_LT { \
1625         inst->opc = ICMD_IF_ICMPLT; \
1626     inst->target = original_start->copied_to; \
1627         if(tos->varkind == UNDEFVAR) \
1628                 tos->varkind = TEMPVAR;  \
1629     tos = tos->prev; \
1630     if(tos->varkind == UNDEFVAR) \
1631                 tos->varkind = TEMPVAR;  \
1632     tos = tos->prev; \
1633         inst->dst = tos; \
1634         inst++; \
1635         stackdepth -= 2; \
1636         }
1637
1638 /* Insert a compare if-not-null and jump to the unoptimized loop, if the        */
1639 /* comparison is true                                                           */
1640 #define GOTO_NOOPT_IF_NULL { \
1641         inst->opc = ICMD_IFNULL; \
1642     inst->target = original_start->copied_to; \
1643     if(tos->varkind == UNDEFVAR) \
1644                 tos->varkind = TEMPVAR;  \
1645     tos = tos->prev; \
1646         inst->dst = tos; \
1647         inst++; \
1648         stackdepth -= 1; \
1649         }
1650
1651 /* Insert an add instruction, that adds two integer values on top of the stack  */
1652 /* together                                                                     */
1653 #define ADD { \
1654         inst->opc = ICMD_IADD; \
1655         if(tos->varkind == UNDEFVAR) \
1656                 tos->varkind = TEMPVAR;  \
1657     tos = tos->prev; \
1658     if(tos->varkind == UNDEFVAR) \
1659                 tos->varkind = TEMPVAR;  \
1660     tos = tos->prev; \
1661         newstack = DMNEW(stackelement, 1); \
1662         newstack->prev = tos; \
1663         newstack->type = TYPE_INT; \
1664         newstack->flags = 0; \
1665         newstack->varkind = UNDEFVAR; \
1666         newstack->varnum = stackdepth; \
1667         tos = newstack; \
1668         inst->dst = tos; \
1669         inst++; \
1670         stackdepth--; \
1671         }
1672
1673 /* Insert instructions to load the arraylength of an array with reference a     */
1674 /* fisrt, the reference must be loaded, then a null-pointer check is inserted   */
1675 /* if not already done earlier. Finally an arraylength instruction is added     */
1676 #define LOAD_ARRAYLENGTH(a) { \
1677     if (c_null_check[a]) { \
1678                 LOAD_ADDR(a); \
1679                 GOTO_NOOPT_IF_NULL; \
1680                 c_null_check[a] = 0; \
1681             }  \
1682         LOAD_ADDR(a); \
1683     inst->opc = ICMD_ARRAYLENGTH; \
1684         if(tos->varkind == UNDEFVAR) \
1685                 tos->varkind = TEMPVAR;  \
1686     tos = tos->prev; \
1687         newstack = DMNEW(stackelement, 1); \
1688         newstack->prev = tos; \
1689         newstack->type = TYPE_INT; \
1690         newstack->flags = 0; \
1691         newstack->varkind = UNDEFVAR; \
1692         newstack->varnum = stackdepth; \
1693         tos = newstack; \
1694         inst->dst = tos; \
1695         inst++; \
1696         }
1697
1698
1699 /* Inserts the instructions to load the value of the right side of comparison   */
1700 /* Depending of the type of the right side, the apropriate instructions are     */
1701 /* created.                                                                     */
1702 #define LOAD_RIGHT_SIDE { \
1703         switch (c_rightside->type) { \
1704         case TRACE_ICONST: \
1705                 LOAD_CONST(c_rightside->constant); \
1706                 break; \
1707         case TRACE_IVAR: \
1708                 LOAD_VAR(c_rightside->var); \
1709                 LOAD_CONST(c_rightside->constant); \
1710                 ADD; \
1711                 break; \
1712         case TRACE_ALENGTH: \
1713                 LOAD_ARRAYLENGTH(c_rightside->var); \
1714                 break; \
1715         default: \
1716                 panic("C_ERROR: illegal trace on rightside of loop-header"); \
1717         } \
1718 }
1719
1720 /*      Patch jumps in original loop and in copied loop, add gotos in copied loop.
1721         All jumps in the original loop to the loop head have to be redirected to
1722         the newly inserted one. For the copied loop, it is necessay to redirect all
1723         jumps inside that loop to the copied nodes. lc points to the current loop,
1724         loop_head is a pointer to the newly inserted head and original start was
1725         the old head and is now the head of the optimized variant of the loop.
1726 */
1727 void patch_jumps(basicblock *original_start, basicblock *loop_head, struct LoopContainer *lc)
1728 {
1729         /* step through all nodes of a loop                                         */
1730         struct LoopElement *le;
1731         basicblock *bptr;
1732         instruction *inst, *temp_instr;
1733         int i;
1734
1735         le = lc->nodes;
1736         while (le != NULL) {
1737
1738                 /* do nothing for new loop head                                         */
1739                 if (le->block == loop_head) {
1740                         le = le->next;
1741                         continue;
1742                     }
1743
1744                 /* for original version                                                 */
1745                 bptr = le->block;
1746                 inst = bptr->iinstr;
1747                 for (i = 0; i < bptr->icount; ++i, ++inst) {
1748                         switch (inst->opc) {
1749
1750                         case ICMD_IF_ICMPEQ:
1751                         case ICMD_IF_ICMPLT:
1752                         case ICMD_IF_ICMPLE:
1753                         case ICMD_IF_ICMPNE:
1754                         case ICMD_IF_ICMPGT:
1755                         case ICMD_IF_ICMPGE:
1756
1757                         case ICMD_IF_LCMPEQ:
1758                         case ICMD_IF_LCMPLT:
1759                         case ICMD_IF_LCMPLE:
1760                         case ICMD_IF_LCMPNE:
1761                         case ICMD_IF_LCMPGT:
1762                         case ICMD_IF_LCMPGE:
1763
1764                         case ICMD_IF_ACMPEQ:
1765                         case ICMD_IF_ACMPNE:
1766
1767                         case ICMD_IFEQ:
1768                         case ICMD_IFNE:
1769                         case ICMD_IFLT:
1770                         case ICMD_IFGE:
1771                         case ICMD_IFGT:
1772                         case ICMD_IFLE:
1773
1774                         case ICMD_IF_LEQ:
1775                         case ICMD_IF_LNE:
1776                         case ICMD_IF_LLT:
1777                         case ICMD_IF_LGE:
1778                         case ICMD_IF_LGT:
1779                         case ICMD_IF_LLE:
1780
1781                         case ICMD_GOTO:
1782                         case ICMD_JSR:
1783                         case ICMD_IFNULL:
1784                         case ICMD_IFNONNULL:
1785
1786                                 /* jump to newly inserted loopheader has to be redirected       */
1787                                 if (((basicblock *) inst->target) == loop_head)
1788                                         inst->target = (void *) original_start;
1789                                 break;
1790
1791                         case ICMD_TABLESWITCH:
1792                                 {
1793                                         s4 *s4ptr, l, i;
1794                                         void **tptr;
1795
1796                                         tptr = (void **) inst->target;
1797
1798                                         s4ptr = inst->val.a;
1799                                         l = s4ptr[1];                          /* low     */
1800                                         i = s4ptr[2];                          /* high    */
1801
1802                                         i = i - l + 1;
1803
1804                                         /* jump to newly inserted loopheader has to be redirected   */
1805                                         for (tptr = inst->target; i >= 0; --i, ++tptr) {
1806                                                 if (((basicblock *) *tptr) == loop_head)
1807                                                         tptr[0] = (void *) original_start;
1808                                                 }
1809                                 }
1810                                 break;
1811
1812                         case ICMD_LOOKUPSWITCH:
1813                                 {
1814                                         s4 i, l, *s4ptr;
1815                                         void **tptr;
1816
1817                                         tptr = (void **) inst->target;
1818
1819                                         s4ptr = inst->val.a;
1820                                         l = s4ptr[0];                          /* default  */
1821                                         i = s4ptr[1];                          /* count    */
1822
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;
1827                                                 }
1828                                 }
1829                                 break;
1830                         }
1831                 }
1832
1833                 /* if node is part of loop and has fall through to original start, that */
1834                 /* must be redirected. Unfortunately the instructions have to be copied */
1835
1836                 if (bptr->next == loop_head) {
1837                         temp_instr = DMNEW(instruction, bptr->icount + 1);
1838                         memcpy(temp_instr, bptr->iinstr, sizeof(instruction)*bptr->icount);
1839                         bptr->iinstr = temp_instr;
1840
1841                         bptr->iinstr[bptr->icount].opc = ICMD_GOTO;
1842                         bptr->iinstr[bptr->icount].target = original_start;
1843                         bptr->iinstr[bptr->icount].dst = NULL;
1844                         ++bptr->icount;
1845                         }
1846
1847                 /* for copied version - which gets the unoptimized variant              */
1848                 bptr = le->block->copied_to;
1849                 inst = bptr->iinstr;
1850                 for (i = 0; i < bptr->icount; ++i, ++inst) {
1851
1852                         switch (inst->opc) {
1853
1854                         case ICMD_IASTORE:                      /* array store                                                  */
1855                         case ICMD_LASTORE:
1856                         case ICMD_FASTORE:
1857                         case ICMD_DASTORE:
1858                         case ICMD_AASTORE:
1859                         case ICMD_BASTORE:
1860                         case ICMD_CASTORE:
1861                         case ICMD_SASTORE:
1862                         case ICMD_IALOAD:                       /* array load                                               */
1863                     case ICMD_LALOAD:
1864                         case ICMD_FALOAD:
1865                         case ICMD_DALOAD:
1866                         case ICMD_AALOAD:
1867                         case ICMD_BALOAD:
1868                         case ICMD_CALOAD:
1869                         case ICMD_SALOAD:
1870
1871                                 /* undo previous optimizations in new loop                      */
1872                                 inst->op1 = 0;
1873                                 break;
1874
1875                         case ICMD_IF_ICMPEQ:
1876                         case ICMD_IF_ICMPLT:
1877                         case ICMD_IF_ICMPLE:
1878                         case ICMD_IF_ICMPNE:
1879                         case ICMD_IF_ICMPGT:
1880                         case ICMD_IF_ICMPGE:
1881
1882                         case ICMD_IF_LCMPEQ:
1883                         case ICMD_IF_LCMPLT:
1884                         case ICMD_IF_LCMPLE:
1885                         case ICMD_IF_LCMPNE:
1886                         case ICMD_IF_LCMPGT:
1887                         case ICMD_IF_LCMPGE:
1888
1889                         case ICMD_IF_ACMPEQ:
1890                         case ICMD_IF_ACMPNE:
1891
1892                         case ICMD_IFEQ:
1893                         case ICMD_IFNE:
1894                         case ICMD_IFLT:
1895                         case ICMD_IFGE:
1896                         case ICMD_IFGT:
1897                         case ICMD_IFLE:
1898
1899                         case ICMD_IF_LEQ:
1900                         case ICMD_IF_LNE:
1901                         case ICMD_IF_LLT:
1902                         case ICMD_IF_LGE:
1903                         case ICMD_IF_LGT:
1904                         case ICMD_IF_LLE:
1905
1906                         case ICMD_GOTO:
1907                         case ICMD_JSR:
1908                         case ICMD_IFNULL:
1909                         case ICMD_IFNONNULL:
1910
1911                                 /* jump to newly inserted loopheader has to be redirected       */
1912                                 if (((basicblock *) inst->target) == loop_head)
1913                                         inst->target = (void *) original_start->copied_to;
1914                                 /* jump to loop internal nodes has to be redirected             */
1915                                 else if (((basicblock *) inst->target)->lflags & LOOP_PART)
1916                                         inst->target = (void *) ((basicblock *) inst->target)->copied_to;
1917                                 break;
1918
1919                         case ICMD_TABLESWITCH:
1920                                 {
1921                                         s4 *s4ptr, l, i;
1922
1923                                         void **copy_ptr, *base_ptr;
1924                                         void **tptr;
1925
1926                                         tptr = (void **) inst->target;
1927
1928                                         s4ptr = inst->val.a;
1929                                         l = s4ptr[1];                          /* low     */
1930                                         i = s4ptr[2];                          /* high    */
1931
1932                                         i = i - l + 1;
1933
1934                                         copy_ptr = (void**) DMNEW(void*, i+1);
1935                                         base_ptr = (void*) copy_ptr;
1936
1937                                         /* Targets for switch instructions are stored in an extra   */
1938                                         /* that must be copied for new inserted loop.               */
1939
1940                                         for (tptr = inst->target; i >= 0; --i, ++tptr, ++copy_ptr) {
1941                                                 /* jump to newly inserted loopheader must be redirected */
1942                                                 if (((basicblock *) *tptr) == loop_head)
1943                                                         copy_ptr[0] = (void *) original_start->copied_to;
1944                                                 /* jump to loop internal nodes has to be redirected     */
1945                                                 else if (((basicblock *) *tptr)->lflags & LOOP_PART)
1946                                                         copy_ptr[0] = (void *) ((basicblock *) tptr[0])->copied_to;
1947                                                 else
1948                                                         copy_ptr[0] = tptr[0];
1949                                                 }
1950
1951                                         inst->target = base_ptr;
1952                                 }
1953                                 break;
1954
1955                         case ICMD_LOOKUPSWITCH:
1956                                 {
1957                                         s4 i, l, *s4ptr;
1958
1959                                         void **copy_ptr, **base_ptr;
1960                                         void **tptr;
1961
1962                                         tptr = (void **) inst->target;
1963
1964                                         s4ptr = inst->val.a;
1965                                         l = s4ptr[0];                          /* default  */
1966                                         i = s4ptr[1];                          /* count    */
1967
1968                                         copy_ptr = (void**) DMNEW(void*, i+1);
1969                                         base_ptr = (void*) copy_ptr;
1970
1971                                         /* Targets for switch instructions are stored in an extra   */
1972                                         /* that must be copied for new inserted loop.               */
1973
1974                                         for (tptr = inst->target; i >= 0; --i, ++tptr, ++copy_ptr) {
1975                                                 /* jump to newly inserted loopheader must be redirected */
1976                                                 if (((basicblock *) *tptr) == loop_head)
1977                                                         copy_ptr[0] = (void *) original_start->copied_to;
1978                                                 /* jump to loop internal nodes has to be redirected     */
1979                                                 else if (((basicblock *) *tptr)->lflags & LOOP_PART)
1980                                                         copy_ptr[0] = (void *) ((basicblock *) tptr[0])->copied_to;
1981                                                 else
1982                                                         copy_ptr[0] = tptr[0];
1983                                                 }
1984
1985                                         inst->target = base_ptr;
1986                                 }
1987                                 break;
1988
1989                                 }
1990                         }
1991
1992                 /* if fall through exits loop, goto is needed                           */
1993                 if (!(le->block->next->lflags & LOOP_PART)) {
1994                         bptr->iinstr[bptr->icount].opc = ICMD_GOTO;
1995                         bptr->iinstr[bptr->icount].dst = NULL;
1996                         bptr->iinstr[bptr->icount].target = le->block->next;
1997                         bptr->icount++;
1998                         }
1999
2000                 le = le->next;
2001                 }
2002 }
2003
2004 /*      Add the new header node of a loop that has been duplicated to all parent
2005     loops in nesting hierarchie.
2006 */
2007 void header_into_parent_loops(struct LoopContainer *lc, basicblock *to_insert, basicblock *replace, basicblock *after)
2008 {
2009         /* we have to insert the node to_insert before the node after and replace   */
2010         /* the pointer of to_insert by the node replace                             */
2011
2012         struct LoopElement *le, *t;
2013
2014         /* if the top of the tree is reached, then return                           */
2015         if ((lc == NULL) || (lc == root))
2016                 return;
2017
2018         /* create new node, that should be inserted                                 */
2019         t = DMNEW(struct LoopElement, 1);
2020         t->block = to_insert;
2021         t->node = -1;
2022
2023         /* first, find the node, that has to be replaced (= "to_insert") and        */
2024         /* replace it by the node "replace"                                         */
2025         le = lc->nodes;
2026         while (le->block != to_insert)
2027                 le = le->next;
2028         le->block = replace;
2029
2030         /* BUGFIX                                                                   */
2031         if (after == to_insert)
2032                 after = replace;
2033
2034         /* now find the node after and insert the newly create node before "after"  */
2035         le = lc->nodes;
2036         if (le->block == after) {
2037                 t->next = lc->nodes;
2038                 lc->nodes = t;
2039             }
2040         else {
2041                 while (le->next->block != after)
2042                         le = le->next;
2043
2044                 t->next = le->next;
2045                 le->next = t;
2046             }
2047
2048         /* go up one hierarchie level                                               */
2049         header_into_parent_loops(lc->parent, to_insert, replace, after);
2050 }
2051
2052 /*      Add a new node (not header) of a duplicated loop to all parent loops in
2053     nesting hierarchie
2054 */
2055 void node_into_parent_loops(struct LoopContainer *lc, basicblock *to_insert)
2056 {
2057         struct LoopElement *le, *t;
2058
2059         /* if the top of the tree is reached, then return                           */
2060         if ((lc == NULL) || (lc == root))
2061                 return;
2062
2063         /* create new node, that should be inserted                                 */
2064         t = DMNEW(struct LoopElement, 1);
2065         t->block = to_insert;
2066         t->node = -1;
2067
2068         le = lc->nodes;
2069
2070         /* append new node to node list of loop                                     */
2071         while (le->next != NULL)
2072                 le = le->next;
2073
2074         t->next = le->next;
2075         le->next = t;
2076
2077         /* go up one hierarchie level                                               */
2078         node_into_parent_loops(NULL, to_insert);
2079 }
2080
2081
2082 /* void patch_handler(...) is very similar to parts of the function patch_jumps.
2083    Its task is to redirect all jumps from the original head to the new head and
2084    to redirect internal jumps inside the exception handler to the newly
2085    created (copied) nodes.
2086 */
2087 void patch_handler(struct LoopContainer *lc, basicblock *bptr, basicblock *original_head, basicblock *new_head)
2088 {
2089         instruction *ip;
2090         int i;
2091
2092         /* If node is not part of exception handler or has been visited, exit       */
2093         if (!(bptr->lflags & HANDLER_PART) || (bptr->lflags & HANDLER_VISITED))
2094                 return;
2095
2096         /* mark block as visited                                                    */
2097         bptr->lflags |= HANDLER_VISITED;
2098
2099         /* for all instructions in the copied block, do                             */
2100         for (i = 0, ip = bptr->copied_to->iinstr; i < bptr->copied_to->icount; ++i, ++ip) {
2101                 switch (ip->opc) {
2102                 case ICMD_RETURN:
2103                 case ICMD_IRETURN:
2104                 case ICMD_LRETURN:
2105                 case ICMD_FRETURN:
2106                 case ICMD_DRETURN:
2107                 case ICMD_ARETURN:
2108                 case ICMD_ATHROW:
2109                         break;
2110
2111                 case ICMD_IF_ICMPEQ:
2112                 case ICMD_IF_ICMPLT:
2113                 case ICMD_IF_ICMPLE:
2114                 case ICMD_IF_ICMPNE:
2115                 case ICMD_IF_ICMPGT:
2116                 case ICMD_IF_ICMPGE:
2117
2118                 case ICMD_IF_LCMPEQ:
2119                 case ICMD_IF_LCMPLT:
2120                 case ICMD_IF_LCMPLE:
2121                 case ICMD_IF_LCMPNE:
2122                 case ICMD_IF_LCMPGT:
2123                 case ICMD_IF_LCMPGE:
2124
2125                 case ICMD_IF_ACMPEQ:
2126                 case ICMD_IF_ACMPNE:
2127
2128                 case ICMD_IFEQ:
2129                 case ICMD_IFNE:
2130                 case ICMD_IFLT:
2131                 case ICMD_IFGE:
2132                 case ICMD_IFGT:
2133                 case ICMD_IFLE:
2134
2135                 case ICMD_IF_LEQ:
2136                 case ICMD_IF_LNE:
2137                 case ICMD_IF_LLT:
2138                 case ICMD_IF_LGE:
2139                 case ICMD_IF_LGT:
2140                 case ICMD_IF_LLE:
2141
2142                 case ICMD_JSR:
2143                 case ICMD_IFNULL:
2144                 case ICMD_IFNONNULL:
2145
2146                         patch_handler(lc, bptr->next, original_head, new_head);
2147
2148                         /* fall through */
2149
2150                 case ICMD_GOTO:
2151
2152                         patch_handler(lc, ip->target, original_head, new_head);
2153
2154                         /* jumps to old header have to be redirected                        */
2155                         if (((basicblock *) ip->target) == original_head)
2156                                 ip->target = (void *) new_head->copied_to;
2157                         /* jumps to handler internal nodes have to be redirected            */
2158                         else if (((basicblock *) ip->target)->lflags & HANDLER_PART)
2159                                 ip->target = (void *) ((basicblock *) ip->target)->copied_to;
2160                         /* jumps to loop internal nodes have to be redirected               */
2161                         else if (((basicblock *) ip->target)->lflags & LOOP_PART)
2162                                 ip->target = (void *) ((basicblock *) ip->target)->copied_to;
2163
2164
2165                         break;
2166
2167                 case ICMD_TABLESWITCH:
2168                         {
2169                                 s4 *s4ptr, l, i;
2170                                 void **tptr;
2171                                 void **copy_ptr, **base_ptr;
2172
2173                                 tptr = (void **) ip->target;
2174                                 s4ptr = ip->val.a;
2175                                 l = s4ptr[1];                          /* low                   */
2176                                 i = s4ptr[2];                          /* high                  */
2177                                 i = i - l + 1;
2178
2179                                 copy_ptr = (void**) DMNEW(void*, i+1);
2180                                 base_ptr = (void*) copy_ptr;
2181
2182                                 for (tptr = ip->target; i >= 0; --i, ++tptr, ++copy_ptr) {
2183                                         patch_handler(lc, ((basicblock *) *tptr), original_head, new_head);
2184                                         /* jumps to old header have to be redirected                */
2185                                         if (((basicblock *) *tptr) == original_head)
2186                                                 copy_ptr[0] = (void *) new_head->copied_to;
2187                                         /* jumps to handler internal nodes have to be redirected    */
2188                                         else if (((basicblock *) *tptr)->lflags & HANDLER_PART)
2189                                                 copy_ptr[0] = (void *) ((basicblock *) tptr[0])->copied_to;
2190                                         /* jumps to loop internal nodes have to be redirected       */
2191                                         else if (((basicblock *) ip->target)->lflags & LOOP_PART)
2192                                                 copy_ptr[0] = (void *) ((basicblock *) tptr[0])->copied_to;
2193                                         else
2194                                                 copy_ptr[0] = tptr[0];
2195                                     }
2196
2197                                 ip->target = base_ptr;
2198                         }
2199                         break;
2200
2201                 case ICMD_LOOKUPSWITCH:
2202                         {
2203                                 s4 i, l, *s4ptr;
2204
2205                                 void **tptr;
2206                                 void **copy_ptr, **base_ptr;
2207
2208                                 tptr = (void **) ip->target;
2209                                 s4ptr = ip->val.a;
2210                                 l = s4ptr[0];                          /* default               */
2211                                 i = s4ptr[1];                          /* count                 */
2212
2213                                 copy_ptr = (void**) DMNEW(void*, i+1);
2214                                 base_ptr = (void*) copy_ptr;
2215
2216                                 for (tptr = ip->target; i >= 0; --i, ++tptr, ++copy_ptr) {
2217
2218                                         patch_handler(lc, ((basicblock *) *tptr), original_head, new_head);
2219                                         /* jumps to old header have to be redirected                */
2220                                         if (((basicblock *) *tptr) == original_head)
2221                                                 copy_ptr[0] = (void *) new_head->copied_to;
2222                                         /* jumps to handler internal nodes have to be redirected    */
2223                                         else if (((basicblock *) *tptr)->lflags & HANDLER_PART)
2224                                                 copy_ptr[0] = (void *) ((basicblock *) tptr[0])->copied_to;
2225                                         /* jumps to loop internal nodes have to be redirected       */
2226                                         else if (((basicblock *) ip->target)->lflags & LOOP_PART)
2227                                                 copy_ptr[0] = (void *) ((basicblock *) tptr[0])->copied_to;
2228                                         else
2229                                                 copy_ptr[0] = tptr[0];
2230                                     }
2231
2232                                 ip->target = base_ptr;
2233                         }
2234                         break;
2235
2236                     }   /* switch */
2237
2238             }       /* for    */
2239
2240                 /* if fall through exits loop, goto is needed                           */
2241                 if (!(bptr->next->lflags & HANDLER_PART)) {
2242                         bptr->copied_to->iinstr[bptr->copied_to->icount].opc = ICMD_GOTO;
2243                         bptr->copied_to->iinstr[bptr->copied_to->icount].dst = NULL;
2244                         bptr->copied_to->iinstr[bptr->copied_to->icount].target = bptr->next;
2245                         bptr->copied_to->icount++;
2246                         }
2247 }
2248
2249
2250 /* This function copys the exception handler and redirects all jumps from the
2251    original head to the new head in the original exception handler. All
2252    redirection in the copied exception handler is done in patch_handler(...).
2253 */
2254 void copy_handler(methodinfo *m, struct LoopContainer *lc, basicblock *bptr, basicblock *original_head, basicblock *new_head)
2255 {
2256         instruction *ip;
2257         s4 *s4ptr;
2258         void **tptr;
2259         int high, low, count;
2260         struct LoopElement *le;
2261         basicblock *new, *temp;
2262
2263         /* If this node has already been copied, return                             */
2264         if (bptr->lflags & HANDLER_PART)
2265                 return;
2266
2267         /* The exception handler exists, when control flow enters loop again        */
2268
2269         if (bptr->lflags & LOOP_PART)
2270                 return;
2271         for (le = lc->nodes; le != NULL; le = le->next) {
2272                 if (le->block == bptr) {
2273                         printf("C_PANIC: should not happen\n");
2274                         exit(-1);
2275             }
2276             }
2277
2278         /* mark block as part of handler                                            */
2279         bptr->lflags |= HANDLER_PART;
2280
2281         /* copy node                                                                */
2282         new = DMNEW(basicblock, 1);
2283         memcpy(new, bptr, sizeof(basicblock));
2284         new->debug_nr = c_debug_nr++;
2285
2286         c_last_block_copied = new;
2287
2288         /* copy instructions and allow one more slot for possible GOTO              */
2289         new->iinstr = DMNEW(instruction, bptr->icount + 1);
2290         memcpy(new->iinstr, bptr->iinstr, bptr->icount*sizeof(instruction));
2291
2292         /* update original block                                                    */
2293         bptr->copied_to = new;
2294
2295         /* append block to global list of basic blocks                              */
2296         temp = m->basicblocks;
2297
2298         while (temp->next)
2299                 temp = temp->next;
2300
2301         temp->next = new;
2302         new->next = NULL;
2303
2304
2305         /* find next block to copy, depending on last instruction of BB             */
2306         if (bptr->icount == 0) {
2307                 copy_handler(m, lc, bptr->next, original_head, new_head);
2308                 return;
2309             }
2310
2311         ip = bptr->iinstr + (bptr->icount - 1);
2312
2313                 switch (ip->opc) {
2314                 case ICMD_RETURN:
2315                 case ICMD_IRETURN:
2316                 case ICMD_LRETURN:
2317                 case ICMD_FRETURN:
2318                 case ICMD_DRETURN:
2319                 case ICMD_ARETURN:
2320                 case ICMD_ATHROW:
2321                         break;
2322
2323                 case ICMD_IFEQ:
2324                 case ICMD_IFNE:
2325                 case ICMD_IFLT:
2326                 case ICMD_IFGE:
2327                 case ICMD_IFGT:
2328                 case ICMD_IFLE:
2329
2330                 case ICMD_IF_LCMPEQ:
2331                 case ICMD_IF_LCMPLT:
2332                 case ICMD_IF_LCMPLE:
2333                 case ICMD_IF_LCMPNE:
2334                 case ICMD_IF_LCMPGT:
2335                 case ICMD_IF_LCMPGE:
2336
2337                 case ICMD_IF_LEQ:
2338                 case ICMD_IF_LNE:
2339                 case ICMD_IF_LLT:
2340                 case ICMD_IF_LGE:
2341                 case ICMD_IF_LGT:
2342                 case ICMD_IF_LLE:
2343
2344                 case ICMD_IFNULL:
2345                 case ICMD_IFNONNULL:
2346
2347                 case ICMD_IF_ICMPEQ:
2348                 case ICMD_IF_ICMPNE:
2349                 case ICMD_IF_ICMPLT:
2350                 case ICMD_IF_ICMPGE:
2351                 case ICMD_IF_ICMPGT:
2352                 case ICMD_IF_ICMPLE:
2353                 case ICMD_IF_ACMPEQ:
2354                 case ICMD_IF_ACMPNE:
2355                         copy_handler(m, lc, bptr->next, original_head, new_head);
2356                         /* fall through */
2357
2358                 case ICMD_GOTO:
2359
2360                         /* redirect jump from original_head to new_head                    */
2361                         if ((basicblock *) ip->target == original_head)
2362                                 ip->target = (void *) new_head;
2363
2364                         copy_handler(m, lc, (basicblock *) (ip->target), original_head, new_head);
2365
2366                         break;
2367
2368                 case ICMD_TABLESWITCH:
2369                         s4ptr = ip->val.a;
2370                         tptr = (void **) ip->target;
2371
2372                         /* default branch */
2373                         if (((basicblock *) *tptr) == original_head)
2374                                 tptr[0] = (void *) new_head;
2375
2376                         copy_handler(m, lc, (basicblock *) *tptr, original_head, new_head);
2377
2378                         s4ptr++;
2379                         low = *s4ptr;
2380                         s4ptr++;
2381                         high = *s4ptr;
2382
2383                         count = (high-low+1);
2384
2385                         while (--count >= 0) {
2386                                 tptr++;
2387                                 /* redirect jump from original_head to new_head                 */
2388                                 if (((basicblock *) *tptr) == original_head)
2389                                         tptr[0] = (void *) new_head;
2390                                 copy_handler(m, lc, (basicblock *) *tptr, original_head, new_head);
2391                         }
2392                         break;
2393
2394                 case ICMD_LOOKUPSWITCH:
2395                         s4ptr = ip->val.a;
2396                         tptr = (void **) ip->target;
2397
2398                         /* default branch */
2399                         if (((basicblock *) *tptr) == original_head)
2400                                 tptr[0] = (void *) new_head;
2401
2402                         copy_handler(m, lc, (basicblock *) *tptr, original_head, new_head);
2403
2404                         ++s4ptr;
2405                         count = *s4ptr;
2406
2407                         while (--count >= 0) {
2408                                 ++tptr;
2409                                 /* redirect jump from original_head to new_head                 */
2410                                 if (((basicblock *) *tptr) == original_head)
2411                                         tptr[0] = (void *) new_head;
2412                                 copy_handler(m, lc, (basicblock *) *tptr, original_head, new_head);
2413                         }
2414                         break;
2415
2416                 case ICMD_JSR:
2417                         c_last_target = bptr;
2418                         copy_handler(m, lc, (basicblock *) (ip->target), original_head, new_head);
2419                         break;
2420
2421                 case ICMD_RET:
2422                         copy_handler(m, lc, c_last_target->next, original_head, new_head);
2423                         break;
2424
2425                 default:
2426                         copy_handler(m, lc, bptr->next, original_head, new_head);
2427                         break;
2428                     }
2429
2430 }
2431
2432
2433 /* If a loop is duplicated, all exceptions, that are contained in this loops' body
2434    have to be duplicated as well. The following function together with the
2435    two helper functions copy_handler and patch_handler perform this task.
2436 */
2437 void update_internal_exceptions(methodinfo *m, struct LoopContainer *lc, basicblock *original_head, basicblock *new_head)
2438 {
2439         exceptiontable *ex, *new;
2440         struct LoopContainer *l;
2441
2442         /* Bottom of tree reached -> return                                         */
2443         if (lc == NULL)
2444                 return;
2445
2446         /* Call update_internal for all nested (=child) loops                       */
2447         l = lc->tree_down;
2448         while (l != NULL) {
2449                 update_internal_exceptions(m, l, original_head, new_head);
2450                 l = l->tree_right;
2451             }
2452
2453         /* For all exceptions of this loop, do                                      */
2454         ex = lc->exceptions;
2455         while (ex != NULL) {
2456
2457                 /* Copy the exception and patch the jumps                               */
2458                 copy_handler(m, lc, ex->handler, original_head, new_head);
2459                 patch_handler(lc, ex->handler, original_head, new_head);
2460
2461                 /* Insert a new exception into the global exception table               */
2462                 new = DNEW(exceptiontable);
2463                 memcpy(new, ex, sizeof(exceptiontable));
2464
2465                 /* Increase number of exceptions                                        */
2466                 ++m->exceptiontablelength;
2467
2468                 ex->next = new;
2469                 ex->down = new;
2470
2471                 /* Set new start and end point of this exception                        */
2472                 new->start = ex->start->copied_to;
2473                 new->end = ex->end->copied_to;
2474
2475                 /* Set handler pointer to copied exception handler                      */
2476                 new->handler = ex->handler->copied_to;
2477
2478                 ex = new->next;
2479             }
2480
2481 }
2482
2483 /* If a loop is duplicated, all exceptions that contain this loop have to be
2484    extended to the copied nodes as well. The following function checks for
2485    all exceptions of all parent loops, whether they contain the loop pointed to
2486    by lc. If so, the exceptions are extended to contain all newly created nodes.
2487 */
2488 void update_external_exceptions(methodinfo *m, struct LoopContainer *lc, int loop_head)
2489 {
2490         exceptiontable *ex, *new;
2491
2492         /* Top of tree reached -> return                                            */
2493         if (lc == NULL)
2494                 return;
2495
2496         ex = lc->exceptions;
2497
2498         /* For all exceptions of this loop do                                       */
2499         while (ex != NULL) {
2500
2501                 /* It is possible that the loop contains exceptions that do not protect */
2502                 /* the loop just duplicated. It must be checked, if this is the case    */
2503                 if ((loop_head >= m->basicblockindex[ex->startpc]) && (loop_head < m->basicblockindex[ex->endpc])) {
2504
2505                         /* loop is really inside exception, so create new exception entry   */
2506                         /* in global exception list                                         */
2507                         new = DNEW(exceptiontable);
2508                         memcpy(new, ex, sizeof(exceptiontable));
2509
2510
2511                         /* Increase number of exceptions                                    */
2512                         ++m->exceptiontablelength;
2513
2514                         ex->next = new;
2515                         ex->down = new;
2516
2517                         /* Set new start and end point of this exception                    */
2518                         new->start = c_first_block_copied;
2519                         new->end = c_last_block_copied;
2520
2521                         ex = new->next;
2522                 }
2523                 /* exception does not contain the duplicated loop -> do nothing         */
2524                 else
2525                         ex = ex->next;
2526             }
2527
2528         /* Call update_external for parent node                                     */
2529         update_external_exceptions(m, lc->parent, loop_head);
2530 }
2531
2532
2533
2534 /*      This function is needed to insert the static checks, stored in c_constraints
2535         into the intermediate code.
2536 */
2537 void create_static_checks(methodinfo *m, struct LoopContainer *lc)
2538 {
2539         int i, stackdepth, cnt;
2540         struct Constraint *tc1;
2541         struct LoopElement *le;
2542
2543         /* loop_head points to the newly inserted loop_head, original_start to      */
2544         /* the old loop header                                                      */
2545         basicblock *bptr, *loop_head, *original_start, *temp;
2546         instruction *inst, *tiptr;
2547
2548         /* tos and newstack are needed by the macros, that insert instructions into */
2549         /* the new loop head                                                        */
2550         stackptr newstack, tos;
2551         exceptiontable *ex;
2552
2553 #ifdef STATISTICS
2554         /* show_loop_statistics(); */
2555 #endif
2556
2557         loop_head = &m->basicblocks[c_current_head];
2558         c_first_block_copied = c_last_block_copied = NULL;
2559
2560         /* the loop nodes are copied                                                */
2561         le = lc->nodes;
2562         while (le != NULL)
2563         {
2564                 bptr = DMNEW(basicblock, 1);
2565                 memcpy(bptr, le->block, sizeof(basicblock));
2566                 bptr->debug_nr = c_debug_nr++;
2567
2568                 /* determine beginning of copied loop to extend exception handler, that */
2569                 /* protect this loop                                                    */
2570                 if (c_first_block_copied == NULL)
2571                         c_first_block_copied = bptr;
2572
2573                 /* copy instructions and add one more slot for possible GOTO            */
2574                 bptr->iinstr = DMNEW(instruction, bptr->icount + 1);
2575
2576                 memcpy(bptr->iinstr, le->block->iinstr, (bptr->icount+1)*sizeof(instruction));
2577
2578                 le->block->copied_to = bptr;
2579
2580                 /* add block to global list of BBs                                      */
2581                 temp = m->basicblocks;
2582
2583                 while (temp->next)
2584                         temp = temp->next;
2585
2586                 temp->next = bptr;
2587                 bptr->next = NULL;
2588
2589                 node_into_parent_loops(lc->parent, bptr);
2590                 le = le->next;
2591         }
2592
2593         c_last_block_copied = bptr;
2594
2595         /* create an additional basicblock for dynamic checks                       */
2596         original_start = bptr = DMNEW(basicblock, 1);
2597
2598         /* copy current loop header to new basic block                              */
2599         memcpy(bptr, loop_head, sizeof(basicblock));
2600     bptr->debug_nr = c_debug_nr++;
2601
2602         /* insert the new basic block and move header before first loop node        */
2603         le = lc->nodes;
2604         temp = le->block;
2605
2606         /* if header is first node of loop, insert original header after it         */
2607         if (temp == loop_head)
2608                 loop_head->next = bptr;
2609         else {
2610         /* else, we have to find the predecessor of loop header                     */
2611                 while (temp->next != loop_head)
2612                         temp = temp->next;
2613
2614                 /* insert original header after newly created block                     */
2615                 temp->next = bptr;
2616
2617                 /* if predecessor is not loop part, insert a goto                       */
2618                 if (!(temp->lflags & LOOP_PART)) {
2619
2620                         /* copy instructions and add an additional slot                     */
2621                         tiptr = DMNEW(instruction, temp->icount + 1);
2622                         memcpy(tiptr, temp->iinstr, sizeof(instruction)*temp->icount);
2623
2624                         temp->iinstr = tiptr;
2625                         tiptr = temp->iinstr + temp->icount;
2626
2627                         /* add goto to loop header. If node is part of exception handler    */
2628                         /* jmp is automagically redirected during patch_handler and works   */
2629                         /* correct                                                          */
2630                         tiptr->opc = ICMD_GOTO;
2631                         tiptr->dst = NULL;
2632                         tiptr->target = (void*) loop_head;
2633
2634                         ++temp->icount;
2635                     }
2636
2637
2638                 temp = m->basicblocks;
2639                 /* if first loop block is first BB of global list, insert loop_head at  */
2640                 /* beginning of global BB list                                          */
2641                 if (temp == le->block) {
2642                         if (c_newstart == NULL) {
2643                                 c_needs_redirection = true;
2644                                 c_newstart = loop_head;
2645                                 loop_head->next = m->basicblocks;
2646                             }
2647                         else {
2648                                 loop_head->next = c_newstart;
2649                                 c_newstart = loop_head;
2650                             }
2651                     }
2652                 else {
2653
2654                         while (temp->next != le->block)
2655                                 temp = temp->next;
2656
2657                         loop_head->next = temp->next;
2658                         temp->next = loop_head;
2659
2660                         /* to be on the safe side insert a jump from the previous instr     */
2661                         /* over thr new inserted node                                       */
2662
2663                         /* special case - jump from node to loop_head: then remove          */
2664                         /* goto / happens rather often due to loop layout                   */
2665                         tiptr = temp->iinstr + (temp->icount-1);
2666
2667                         if ((tiptr->opc == ICMD_GOTO) && (tiptr->target == loop_head)) {
2668                                 tiptr->opc = ICMD_NOP;
2669                                 tiptr->dst = NULL;
2670                         }
2671                         else {
2672
2673                                 tiptr = DMNEW(instruction, temp->icount + 1);
2674                                 memcpy(tiptr, temp->iinstr, sizeof(instruction)*temp->icount);
2675
2676                                 temp->iinstr = tiptr;
2677                                 tiptr = temp->iinstr + temp->icount;
2678
2679                                 tiptr->opc = ICMD_GOTO;
2680                                 tiptr->dst = NULL;
2681                                 tiptr->target = (void*) loop_head->next;
2682
2683                                 ++temp->icount;
2684                     }
2685                     }
2686             }
2687
2688         /* adjust exceptions                                                        */
2689         ex = m->exceptiontable;
2690         while (ex != NULL) {
2691
2692                 /* if an exception covers whole loop and starts at first loop node, it  */
2693                 /* has to be extended to cover the new first node as well               */
2694                 if (ex->start == le->block) {
2695
2696                         if ((lc->loop_head >= m->basicblockindex[ex->startpc]) && (lc->loop_head < m->basicblockindex[ex->endpc]))
2697                                 ex->start = loop_head;
2698                     }
2699
2700                 /* an exception that ended at the old loop header now must contains the */
2701                 /* new loop header as well                                              */
2702                 if (ex->end == loop_head)
2703                         ex->end = original_start;
2704
2705                 ex = ex->down;
2706             }
2707
2708
2709         /* insert new header node into nodelists of all enclosing loops             */
2710         header_into_parent_loops(lc, loop_head, original_start, le->block);
2711
2712         /* prepare instruction array to insert checks                               */
2713         inst = loop_head->iinstr = DMNEW(instruction, c_needed_instr + 2);
2714         loop_head->icount = c_needed_instr + 1;
2715
2716         /* init instruction array                                                   */
2717         for (cnt=0; cnt<c_needed_instr + 1; ++cnt) {
2718                 inst[0].opc = ICMD_NOP;
2719                 inst[0].dst = NULL;
2720             }
2721
2722         loop_head->copied_to = NULL;
2723
2724         /* prepare stack                                                            */
2725         loop_head->instack = copy_stack_from(bptr->instack);
2726         loop_head->outstack = copy_stack_from(bptr->instack);
2727
2728         tos = loop_head->instack;
2729         stackdepth = loop_head->indepth;
2730
2731         /* step through all inserted checks and create instructions for them        */
2732         for (i=0; i<m->maxlocals+1; ++i)
2733         {
2734                 tc1 = c_constraints[i];
2735                 while (tc1 != NULL)
2736                 {
2737                         switch (tc1->type)
2738                         {
2739
2740                                 /* check a variable against a constant                          */
2741                         case TEST_ZERO:
2742                         case TEST_UNMOD_ZERO:
2743
2744 #ifdef LOOP_DEBUG
2745                                 printf("insert ZERO-test\n");
2746                                 fflush(stdout);
2747 #endif
2748
2749                                 /* optimize if tc1->varRef >= tc1->constant                     */
2750                                 LOAD_VAR(tc1->varRef);
2751                                 LOAD_CONST(tc1->constant);
2752                                 GOTO_NOOPT_IF_LT;
2753                                 break;
2754
2755                                 /* check a variable against an array length                     */
2756                         case TEST_ALENGTH:
2757                         case TEST_UNMOD_ALENGTH:
2758
2759                                 /* optimize if                                                  */
2760                                 /* tc1->varRef + tc1->constant < lengthOf(tc1->arrayRef)        */
2761 #ifdef LOOP_DEBUG
2762                                 printf("insert ALENGTH-test\n");
2763                                 fflush(stdout);
2764 #endif
2765
2766                                 LOAD_VAR(tc1->varRef);
2767                                 LOAD_CONST(tc1->constant);
2768                                 ADD;
2769                                 LOAD_ARRAYLENGTH(tc1->arrayRef);
2770                                 GOTO_NOOPT_IF_GE;
2771                                 break;
2772
2773                                 /* test right side of comparison against constant               */
2774                         case TEST_RS_ZERO:
2775
2776 #ifdef LOOP_DEBUG
2777                                 printf("insert RS-ZERO-test\n");
2778                                 fflush(stdout);
2779 #endif
2780
2781                                 /* optimize if right-side >= tc1->constant                      */
2782                                 LOAD_RIGHT_SIDE;
2783                                 LOAD_CONST(tc1->constant);
2784                                 GOTO_NOOPT_IF_LT;
2785                                 break;
2786
2787                                 /* test right side of comparison against array length           */
2788                         case TEST_RS_ALENGTH:
2789
2790 #ifdef LOOP_DEBUG
2791                                 printf("insert RS-ALENGTH-test\n");
2792                                 fflush(stdout);
2793 #endif
2794                                 /* optimize if right-side < lengthOf(arrayRef)                  */
2795                                 LOAD_RIGHT_SIDE;
2796                                 LOAD_ARRAYLENGTH(tc1->arrayRef);
2797                                 GOTO_NOOPT_IF_GT;
2798                                 break;
2799
2800                                 /* test unmodified variable against arraylength                 */
2801                         case TEST_CONST_ALENGTH:
2802
2803 #ifdef LOOP_DEBUG
2804                                 printf("insert CONST ALENGTH-test\n");
2805                                 fflush(stdout);
2806 #endif
2807
2808                                 /* optimize if tc1->constant < lengthOf(tc1->arrayRef)          */
2809                                 LOAD_CONST(tc1->constant);
2810                                 LOAD_ARRAYLENGTH(tc1->arrayRef);
2811                                 GOTO_NOOPT_IF_GE;
2812                                 break;
2813                         }
2814
2815                         tc1 = tc1->next;
2816                 }
2817                 c_constraints[i] = NULL;
2818         }
2819
2820         /* if all tests succeed, jump to optimized loop header                      */
2821         if (loop_head->next != original_start) {
2822                 inst->opc = ICMD_GOTO;
2823                 inst->dst = NULL;
2824                 inst->target = original_start;
2825             }
2826
2827         /* redirect jumps from original loop head to newly inserted one             */
2828         patch_jumps(original_start, loop_head, lc);
2829
2830         /* if exceptions have to be correct due to loop duplication these two       */
2831         /* functions perform this task.                                             */
2832         update_internal_exceptions(m, lc, loop_head, original_start);
2833         update_external_exceptions(m, lc->parent, lc->loop_head);
2834 }
2835
2836
2837 /*      This function performs an update between two arrays of struct Changes (that
2838         reflect variable changes). The merge is performed unrstricted in the way, that
2839         all variable changes in c1 took place in a nested loop and therefore are
2840         considered to be without limit. Beside that, the merge is a simple union of the
2841         changes recorded in both arrays. A variable, which limits are undefinied, is
2842         represented by its lower bound being higher than the upper bound. The result
2843         of the union is stored in c1.
2844 */
2845 struct Changes ** constraints_unrestricted_merge(methodinfo *m, struct Changes **c1, struct Changes **c2)
2846 {
2847         int i, changed;
2848
2849         if ((c1 == NULL) || (c2 == NULL))
2850                 printf("C_ERROR: debugging error 0x03\n");
2851
2852         changed = 0;
2853         for (i=0; i<m->maxlocals; ++i) {
2854                 if (c1[i] == NULL) {
2855                         if (c2[i] != NULL) {            /* a change in c2 is updated in c1              */
2856                                 changed = 1;
2857                                 c1[i] = c2[i];
2858                                 c1[i]->lower_bound = c1[i]->upper_bound+1;
2859                                 }
2860                         }
2861                 else {
2862                         if (c1[i]->lower_bound > c1[i]->upper_bound)
2863                                 continue;                               /* variable's bounds already undefined  */
2864
2865                         if (c2[i] == NULL) {            /* variable changed in c1 -> now undef. */
2866                                 changed = 1;
2867                                 c1[i]->lower_bound = c1[i]->upper_bound+1;
2868                                 }
2869                         else {
2870                                 if ((c1[i]->lower_bound == c2[i]->lower_bound) &&
2871                                         (c1[i]->upper_bound == c2[i]->upper_bound))
2872                                         continue;                       /* variable's bounds remain the same    */
2873                                 else {
2874                                         changed = 1;
2875                                         c1[i]->lower_bound = c1[i]->upper_bound+1;
2876                                         }                                       /* variable changed in c1 -> now undef. */
2877                                 }
2878                         }
2879                 }
2880
2881         if (changed)
2882                 return c1;
2883         else
2884                 return NULL;
2885 }
2886
2887 /*      This function performs an update between two arrays of struct Changes (that
2888         reflect variable changes). The merge is a simple union of the bounds
2889         changes recorded in both arrays. A variable, which limits are undefinied, is
2890         represented by its lower bound being higher than the upper bound. The result
2891         of the union is stored in c1.
2892 */
2893 struct Changes ** constraints_merge(methodinfo *m, struct Changes **c1, struct Changes **c2)
2894 {
2895         int i, changed;
2896
2897         if ((c1 == NULL) || (c2 == NULL))
2898                 printf("C_ERROR: debugging error 0x04\n");
2899
2900         changed = 0;
2901
2902         for (i=0; i<m->maxlocals; ++i) {
2903                 if (c1[i] == NULL) {
2904                         if (c2[i] != NULL) {            /* update changes in c2 in c1                   */
2905                                 if ((c1[i] = (struct Changes *) malloc (sizeof(struct Changes))) == NULL)
2906                                         c_mem_error();
2907
2908                                         c1[i]->lower_bound = c2[i]->lower_bound;
2909                                         c1[i]->upper_bound = c2[i]->upper_bound;
2910                                         changed = 1;
2911                                 }
2912                 }
2913                 else {
2914                         if (c2[i] != NULL) {
2915
2916                                 if (c1[i]->lower_bound > c1[i]->upper_bound)
2917                                         continue;                       /* var in c1 is unrestricted                    */
2918
2919                                 if (c1[i]->lower_bound > c2[i]->lower_bound) {
2920                                         c1[i]->lower_bound = c2[i]->lower_bound;
2921                                         changed = 1;            /* write new lower bound                                */
2922                                         }
2923                                 if (c1[i]->upper_bound < c2[i]->upper_bound) {
2924                                         c1[i]->upper_bound = c2[i]->upper_bound;
2925                                         changed = 1;            /* write new higher bound                               */
2926                                         }
2927                                 }
2928                         }
2929                 }
2930
2931         if (changed)
2932                 return c1;
2933         else
2934                 return NULL;
2935 }
2936
2937
2938 /*      This function simply copies an array of changes
2939 */
2940 struct Changes** constraints_clone(methodinfo *m, struct Changes **c)
2941 {
2942         int i;
2943         struct Changes **t;
2944
2945         if ((t = (struct Changes **) malloc(m->maxlocals * sizeof(struct Changes *))) == NULL)
2946                 c_mem_error();
2947
2948         for (i=0; i<m->maxlocals; ++i) {                /* for all array elements (vars) do             */
2949                 if (c[i] == NULL)
2950                         t[i] = NULL;
2951                 else {
2952                         if ((t[i] = (struct Changes *) malloc(sizeof(struct Changes))) == NULL)
2953                                 c_mem_error();
2954                         t[i]->lower_bound = c[i]->lower_bound;
2955                         t[i]->upper_bound = c[i]->upper_bound;
2956                         }
2957                 }
2958
2959         return t;
2960 }
2961
2962 /*      This function is used to reset the changes of a variable to the time, it was
2963         pushed onto the stack. If a variable has been modified between an instruction
2964         and a previous push onto the stack, its value in the changes array does not
2965         correctly reflect its bounds the time, it was pushed onto the stack. This
2966         function corrects the situation.
2967         */
2968 struct Changes* backtrack_var(methodinfo *m, int node, int from, int to, int varRef, struct Changes *changes)
2969 {
2970         struct Changes *tmp;
2971         basicblock bp;
2972         instruction *ip;
2973         struct Trace *t;
2974
2975         if (changes == NULL)    /* if there are no changes, immediately return          */
2976                 return NULL;
2977         else {                                  /* init a Changes structure with current values         */
2978                 if ((tmp = (struct Changes *) malloc(sizeof(struct Changes))) == NULL)
2979                         c_mem_error();
2980
2981                 tmp->upper_bound = changes->upper_bound;
2982                 tmp->lower_bound = changes->lower_bound;
2983                 }
2984
2985         if (tmp->upper_bound < tmp->lower_bound)
2986                 return tmp;                     /* if it is unrestricted no backtracking can happen     */
2987
2988         bp = m->basicblocks[node];
2989         ip = bp.iinstr + to;
2990
2991         for (; from < to; --to, --ip) {         /* scan instructions backwards                  */
2992                 switch (ip->opc) {
2993                 case ICMD_IINC:                                 /* a var has been modified                              */
2994                         if (varRef != ip->op1)          /* not the one, we are interested in    */
2995                                 break;
2996                         tmp->upper_bound -= ip->val.i;          /* take back modifications              */
2997                         tmp->lower_bound -= ip->val.i;
2998                         break;
2999
3000                 case ICMD_ISTORE:                               /* a var has been modified                              */
3001                         if (varRef != ip->op1)          /* not the one, we are interested in    */
3002                                 break;
3003
3004                         /* it is our variable, so trace its origin                                                      */
3005                         t = tracing(&m->basicblocks[node],to, 0);
3006
3007                         switch (t->type) {
3008                                 case TRACE_IVAR:
3009                                         if ((t->var = ip->op1) && (t->neg > 0)) {
3010                                                 /* it was the same var -> take back modifications               */
3011                                                 tmp->upper_bound -= t->constant;
3012                                                 tmp->lower_bound -= t->constant;
3013                                                 }
3014                                         else
3015                                                 tmp->lower_bound = tmp->upper_bound+1;  /* unknown              */
3016                                         break;
3017
3018                                 /* cannot restore it -> invalidate t                                                    */
3019                                 case TRACE_ICONST:
3020                                 case TRACE_ALENGTH:
3021                                 case TRACE_UNKNOWN:
3022                                 case TRACE_AVAR:
3023                                         tmp->lower_bound = tmp->upper_bound+1;
3024                                         break;
3025                                 }
3026
3027                         break;
3028                         }
3029                 }
3030         return tmp;
3031 }
3032
3033 /*      This function performs the main task of bound check removal. It removes
3034         all bound-checks in node. change is a pointer to an array of struct Changes
3035         that reflect for all local variables, how their values have changed from
3036         the start of the loop. The special flag is needed to deal with the header
3037         node.
3038 */
3039 void remove_boundchecks(methodinfo *m, int node, int from, struct Changes **change, int special)
3040 {
3041         basicblock bp;
3042         instruction *ip;
3043         int i, count, ignore, degrade_checks, opt_level;
3044         struct depthElement *d;
3045         struct Changes **t1, **tmp, *t;
3046         struct Trace *t_array, *t_index;
3047
3048         /* printf("remove_bc called: %d - %d - %d\n", node, from, special);                     */
3049
3050         /* a flag, that is set, when previous optimzations have to be taken back        */
3051         degrade_checks = 0;
3052
3053         if (c_current_loop[node] > 0) {         /* this node is part of the loop                */
3054                 if (c_current_loop[node] > 1) { /* it is not the header node                    */
3055
3056                         /* get variable changes, already recorded for this node                         */
3057                         t1 = c_dTable[node]->changes;
3058
3059                         if (t1 != NULL) {                       /* it is not the first visit                    */
3060                                 if ((c_nestedLoops[node] != c_current_head) && (c_nestedLoops[node] == c_nestedLoops[from])) {
3061                                 /* we are looping in a nested loop, so made optimizations               */
3062                                 /* need to be reconsidered                                                                              */
3063                                         degrade_checks = 1;
3064                                         if (constraints_unrestricted_merge(m, t1, change) == NULL)
3065                                                 return;                 /* no changes since previous visit              */
3066                                                 /* if there have been changes, they are updated by              */
3067                                                 /* constraints_unrestricted_merge in t1                                 */
3068                                         }
3069                                 else {
3070                                         if (constraints_merge(m, t1, change) == NULL)
3071                                                 return;                 /* no changes since previous visit              */
3072                                                 /* if there have been changes, they are updated by              */
3073                                                 /* constraints_merge in t1                                                              */
3074                                         }
3075                                 }
3076                         else {                                          /* first visit                                                  */
3077                                 /* printf("first visit - constraints cloned\n");                                */
3078                                 c_dTable[node]->changes = constraints_clone(m, change);
3079                                 }
3080
3081                         /* tmp now holds a copy of the updated variable changes                         */
3082                         tmp = constraints_clone(m, c_dTable[node]->changes);
3083                         }
3084                 else if (special) {                             /* header and need special traetment    */
3085                         /* printf("special treatment called\n");                                                        */
3086                         /* tmp now holds a copy of the current new variable changes                     */
3087                         tmp = constraints_clone(m, change);
3088                         }
3089                 else
3090                         return;
3091
3092                 bp = m->basicblocks[node];                              /* scan all instructions                                */
3093                 count = bp.icount;
3094                 ip = bp.iinstr;
3095                 ignore = 0;
3096
3097                 for (i=0; i<count; ++i, ++ip) {
3098                         switch (ip->opc) {
3099                         case ICMD_IASTORE:                      /* found an array store                                 */
3100                         case ICMD_LASTORE:
3101                         case ICMD_FASTORE:
3102                         case ICMD_DASTORE:
3103                         case ICMD_AASTORE:
3104                         case ICMD_BASTORE:
3105                         case ICMD_CASTORE:
3106                         case ICMD_SASTORE:
3107
3108                                 t_index = tracing(&bp, i-1, 1); /* get index                                    */
3109                                 t_array = tracing(&bp, i-1, 2); /* get array refernce                   */
3110                                 ignore = 1;
3111                                 /* fall through */
3112
3113                         case ICMD_IALOAD:                       /* found an array load                                  */
3114                         case ICMD_LALOAD:
3115                         case ICMD_FALOAD:
3116                         case ICMD_DALOAD:
3117                         case ICMD_AALOAD:
3118                         case ICMD_BALOAD:
3119                         case ICMD_CALOAD:
3120                         case ICMD_SALOAD:
3121                                 if (!ignore) {
3122                                         t_index = tracing(&bp, i-1, 0); /* get index                            */
3123                                         t_array = tracing(&bp, i-1, 1); /* get array refernce           */
3124                                         ignore = 0;
3125                                         }
3126
3127                                 /* printf("Array access with params:\n");
3128                                 printf("Array:\n");
3129                                 show_trace(t_array);
3130                                 printf("Index:\n");
3131                                 show_trace(t_index);
3132                                 */
3133
3134 #ifdef STATISTICS
3135                                 if (ip->op1 == OPT_UNCHECKED) {         /* found new access                     */
3136                                    c_stat_array_accesses++;
3137                                    ip->op1 = OPT_NONE;
3138                                    c_stat_no_opt++;
3139                                    }
3140 #endif
3141
3142                                 /* can only optimize known arrays that do not change                    */
3143                                 if ((t_array->type != TRACE_AVAR) || (c_var_modified[t_array->var]))
3144                                         break;
3145
3146                                 switch (t_index->type) {        /* now we look at the index                     */
3147                                 case TRACE_ICONST:                      /* it is a constant value or an         */
3148                                 case TRACE_ALENGTH:                     /* array length                                         */
3149 #ifdef STATISTICS
3150                                         switch (ip->op1) {              /* take back old optimzation            */
3151                                         case OPT_UNCHECKED:
3152                                                 break;
3153                                         case OPT_NONE:
3154                                                 c_stat_no_opt--;
3155                                                 break;
3156                                         case OPT_FULL:
3157                                                 c_stat_full_opt--;
3158                                                 break;
3159                                         case OPT_UPPER:
3160                                                 c_stat_upper_opt--;
3161                                                 break;
3162                                         case OPT_LOWER:
3163                                                 c_stat_lower_opt--;
3164                                                 break;
3165                                                 }
3166 #endif
3167                                         if (degrade_checks)             /* replace existing optimization        */
3168                                                 ip->op1 = insert_static(m, t_array->var, t_index, NULL, special);
3169                                         else {
3170                                                 /* Check current optimization and try to improve it     by      */
3171                                                 /* inserting new checks                                                                 */
3172                                                 switch (ip->op1) {
3173                                                 case OPT_UNCHECKED:
3174                                                         ip->op1 = insert_static(m, t_array->var, t_index, NULL, special);
3175                                                         break;
3176                                                 case OPT_NONE:
3177                                                         ip->op1 = insert_static(m, t_array->var, t_index, NULL, special);
3178                                                         break;
3179                                                 case OPT_UPPER:
3180                                                         opt_level = insert_static(m, t_array->var, t_index, NULL, special);
3181                                                         if ((opt_level == OPT_FULL) || (opt_level == OPT_LOWER))
3182                                                                 ip->op1 = OPT_FULL;
3183                                                         break;
3184                                                 case OPT_LOWER:
3185                                                         opt_level = insert_static(m, t_array->var, t_index, NULL, special);
3186                                                         if ((opt_level == OPT_FULL) || (opt_level == OPT_UPPER))
3187                                                                 ip->op1 = OPT_FULL;
3188                                                         break;
3189                                                 case OPT_FULL:
3190 #ifdef STATISTICS
3191                                                         c_stat_full_opt++;
3192 #endif
3193                                                         break;
3194                                                         }
3195                                                 }
3196                                         break;
3197
3198                                 case TRACE_IVAR:                        /* it's a variable                                      */
3199
3200                                         /* if the variable is changed between its usage as an index     */
3201                                         /* of the array access and its push onto the stack, we have     */
3202                                         /* to set the changes back to the time, it is pushed onto       */
3203                                         /* the stack as an index variable.                                                      */
3204                                         t = backtrack_var(m, node, t_index->nr, i-1, t_index->var, tmp[t_index->var]);
3205 #ifdef STATISTICS
3206                                         switch (ip->op1) {              /* take back old optimzation            */
3207                                         case OPT_UNCHECKED:
3208                                                 break;
3209                                         case OPT_NONE:
3210                                                 c_stat_no_opt--;
3211                                                 break;
3212                                         case OPT_FULL:
3213                                                 c_stat_full_opt--;
3214                                                 break;
3215                                         case OPT_UPPER:
3216                                                 c_stat_upper_opt--;
3217                                                 break;
3218                                         case OPT_LOWER:
3219                                                 c_stat_lower_opt--;
3220                                                 break;
3221                                                 }
3222 #endif
3223                                         if (degrade_checks)
3224                                                 ip->op1 = insert_static(m, t_array->var, t_index, t, special);
3225                                         else {
3226                                                 /* Check current optimization and try to improve it     by      */
3227                                                 /* insert new check. t reflects var changes for index   */
3228                                                 switch (ip->op1) {
3229                                                 case OPT_UNCHECKED:
3230                                                         ip->op1 = insert_static(m, t_array->var, t_index, t, special);
3231                                                         break;
3232                                                 case OPT_NONE:
3233                                                         ip->op1 = insert_static(m, t_array->var, t_index, t, special);
3234                                                         break;
3235                                                 case OPT_UPPER:
3236                                                         opt_level = insert_static(m, t_array->var, t_index, t, special);
3237                                                         if ((opt_level == OPT_FULL) || (opt_level == OPT_LOWER))
3238                                                                 ip->op1 = OPT_FULL;
3239                                                         break;
3240                                                 case OPT_LOWER:
3241                                                         opt_level = insert_static(m, t_array->var, t_index, t, special);
3242                                                         if ((opt_level == OPT_FULL) || (opt_level == OPT_UPPER))
3243                                                                 ip->op1 = OPT_FULL;
3244                                                         break;
3245                                                 case OPT_FULL:
3246 #ifdef STATISTICS
3247                                                         c_stat_full_opt++;
3248 #endif
3249                                                         break;
3250                                                         }
3251                                                 }
3252                                         break;
3253
3254                                 case TRACE_UNKNOWN:
3255                                 case TRACE_AVAR:
3256                                         break;
3257                                         }
3258                                 break;
3259
3260                         case ICMD_ISTORE:               /* an integer value is stored                           */
3261                                 t_index = tracing(&bp, i-1, 0); /* trace back its origin                */
3262
3263                                 /* the struct Changes for this variable needs to be updated             */
3264                                 t = tmp[ip->op1];
3265                                 if (t == NULL) {        /* if it's the first one, create new entry      */
3266                                         if ((t = (struct Changes *) malloc(sizeof(struct Changes))) == NULL)
3267                                                 c_mem_error();
3268                                         t->upper_bound = t->lower_bound = 0;
3269                                         tmp[ip->op1] = t;
3270                                         }
3271
3272                                 switch (t_index->type) {                /* check origin of store                */
3273
3274                                 case TRACE_ICONST:      /* constant -> set bounds to const value        */
3275                                         t->upper_bound = t->lower_bound = t_index->constant;
3276                                         break;
3277
3278                                 case TRACE_IVAR:        /* if it's the same variable, update consts     */
3279                                         if ((t_index->var = ip->op1) && (t_index->neg > 0)) {
3280                                                 t->upper_bound += t_index->constant;
3281                                                 t->lower_bound += t_index->constant;
3282                                                 }
3283                                         else
3284                                                 t->lower_bound = t->upper_bound+1;
3285                                         break;
3286
3287                                 case TRACE_ALENGTH:   /* else -> unknown                                                */
3288                                 case TRACE_UNKNOWN:
3289                                 case TRACE_AVAR:
3290                                         t->lower_bound = t->upper_bound+1;
3291                                         break;
3292                                         }
3293
3294                                 break;
3295
3296                         case ICMD_IINC:
3297
3298                                 /* the struct Changes for this variable needs to be updated             */
3299                                 if ((t = tmp[ip->op1]) == NULL) {       /* first one -> create new      */
3300                                         if ((t = (struct Changes *) malloc(sizeof(struct Changes))) == NULL)
3301                                                 c_mem_error();
3302                                         t->upper_bound = t->lower_bound = ip->val.i;
3303                                         tmp[ip->op1] = t;
3304                                         }
3305                                 else {                          /* update changes, made by iinc                         */
3306                                         t->upper_bound += ip->val.i;
3307                                         t->lower_bound += ip->val.i;
3308                                         }
3309                                 break;
3310                                 }       /* switch */
3311                         }               /* for    */
3312
3313                 if (!special) {                         /* we are not interested in only the header     */
3314                         d = c_dTable[node];
3315                         while (d != NULL) {             /* check all sucessors of current node          */
3316                                 remove_boundchecks(m, d->value, node, tmp, special);
3317                                 d = d->next;
3318                                 }
3319                         }
3320             }   /* if */
3321 }
3322
3323 /*      This function calls the bound-check removal function for the header node
3324         with a special flag. It is important to notice, that no dynamic
3325         constraint hold in the header node (because the comparison is done at
3326         block end).
3327 */
3328 void remove_header_boundchecks(methodinfo *m, int node, struct Changes **changes)
3329 {
3330         remove_boundchecks(m, node, -1, changes, BOUNDCHECK_SPECIAL);
3331 }
3332
3333 /*      Marks all basicblocks that are part of the loop
3334 */
3335 void mark_loop_nodes(struct LoopContainer *lc)
3336 {
3337         struct LoopElement *le = lc->nodes;
3338
3339         while (le != NULL) {
3340                 le->block->lflags |= LOOP_PART;
3341                 le = le->next;
3342                 }
3343 }
3344
3345 /*      Clears mark for all basicblocks that are part of the loop
3346 */
3347 void unmark_loop_nodes(struct LoopContainer *lc)
3348 {
3349         struct LoopElement *le = lc->nodes;
3350
3351         while (le != NULL) {
3352                 le->block->lflags = 0;
3353                 le = le->next;
3354                 }
3355 }
3356
3357
3358 /*      This function performs the analysis of code in detected loops and trys to
3359         identify array accesses suitable for optimization (bound check removal). The
3360         intermediate code is then modified to reflect these optimizations.
3361 */
3362 void optimize_single_loop(methodinfo *m, struct LoopContainer *lc)
3363 {
3364         struct LoopElement *le;
3365         struct depthElement *d;
3366         int i, head, node;
3367         struct Changes **changes;
3368
3369         if ((changes = (struct Changes **) malloc(m->maxlocals * sizeof(struct Changes *))) == NULL)
3370                 c_mem_error();
3371
3372     head = c_current_head = lc->loop_head;
3373         c_needed_instr = c_rs_needed_instr = 0;
3374
3375         /* init array for null ptr checks */
3376         for (i=0; i<m->maxlocals; ++i)
3377                 c_null_check[i] = 0;
3378
3379
3380         /* don't optimize root node (it is the main procedure, not a loop)                      */
3381         if (head < 0)
3382                 return;
3383
3384         /* setup variables with initial values                                                                          */
3385         c_loopvars = NULL;
3386         for (i=0; i < m->basicblockcount; ++i) {
3387                 c_toVisit[i] = 0;
3388                 c_current_loop[i] = -1;
3389                 if ((d = c_dTable[i]) != NULL)
3390                         d->changes = NULL;
3391                 }
3392
3393         for (i=0; i < m->maxlocals; ++i) {
3394                 c_var_modified[i] = 0;
3395                 if (changes[i] != NULL) {
3396                         changes[i] = NULL;
3397                         }
3398                 }
3399
3400         for (i=0; i < (m->maxlocals+1); ++i) {
3401                 if (c_constraints[i] != NULL) {
3402                     c_constraints[i] = NULL;
3403                         }
3404                 }
3405
3406         le = lc->nodes;
3407         while (le != NULL) {
3408                 node = le->node;
3409
3410                 if (node == head)
3411                         c_current_loop[node] = 1;   /* the header node gets 1               */
3412                 else if (c_nestedLoops[node] == head)
3413                         c_current_loop[node] = 2;       /* top level nodes get 2                                */
3414                 else
3415                         c_current_loop[node] = 3;       /* nodes, part of nested loop get 3             */
3416
3417                 c_toVisit[node] = 1;
3418                 le = le->next;
3419                 }
3420
3421         /* After setup work has been performed, start to analyse                                        */
3422 #ifdef LOOP_DEBUG
3423         printf("****** Starting analysis (%d)******\n", head);
3424         fflush(stdout);
3425 #endif
3426
3427         if (analyze_for_array_access(m, head) > 0) {/* loop contains array access               */
3428
3429 #ifdef LOOP_DEBUG
3430                 struct LoopVar *lv;
3431
3432                 printf("analyze for array access finished and found\n");
3433                 fflush(stdout);
3434                 lv = c_loopvars;
3435                 while (lv != NULL) {
3436                         if (lv->modified)
3437                                 printf("Var --> %d\n", lv->value);
3438                         lv = lv->next;
3439                 }
3440 #endif
3441
3442                 /* for performance reasons the list of all interesting loop vars is             */
3443                 /* scaned and for all modified vars a flag in c_var_modified is set             */
3444                 scan_global_list();
3445
3446 #ifdef LOOP_DEBUG
3447                 printf("global list scanned\n");
3448                 fflush(stdout);
3449 #endif
3450
3451                 /* if the loop header contains or-conditions or an index variable               */
3452                 /* is modified in the catch-block within the loop, a conservative               */
3453                 /* approach is taken and optimizations are cancelled                                    */
3454                 if (analyze_or_exceptions(m, head, lc) > 0) {
3455
3456 #ifdef LOOP_DEBUG
3457                         printf("Analyzed for or/exception - no problems \n");
3458                         fflush(stdout);
3459 #endif
3460
3461                         init_constraints(m, head);      /* analyze dynamic bounds in header                     */
3462
3463 #ifdef LOOP_DEBUG
3464                         show_right_side();
3465 #endif
3466
3467                         if (c_rightside == NULL)
3468                                 return;
3469
3470                         /* single pass bound check removal - for all successors, do                     */
3471                         remove_header_boundchecks(m, head, changes);
3472
3473                         d = c_dTable[head];
3474                         while (d != NULL) {
3475                                 remove_boundchecks(m, d->value, -1, changes, BOUNDCHECK_REGULAR);
3476                                 d = d->next;
3477                                 }
3478
3479 #ifdef LOOP_DEBUG
3480                         printf("Array-bound checks finished\n");
3481                         fflush(stdout);
3482 #endif
3483
3484                         mark_loop_nodes(lc);
3485
3486 #ifdef LOOP_DEBUG
3487                         printf("START: create static checks\n");
3488                         fflush(stdout);
3489 #endif
3490
3491                         create_static_checks(m, lc);    /* create checks                                                */
3492
3493 #ifdef LOOP_DEBUG
3494                         printf("END: create static checks\n");
3495                         fflush(stdout);
3496 #endif
3497                         unmark_loop_nodes(lc);
3498                         }
3499                 }
3500         /* else
3501                 printf("No array accesses found\n");                                                                    */
3502
3503 #ifdef STATISTICS
3504         c_stat_num_loops++;             /* increase number of loops                                                     */
3505
3506         c_stat_sum_accesses += c_stat_array_accesses;
3507         c_stat_sum_full += c_stat_full_opt;
3508         c_stat_sum_no += c_stat_no_opt;
3509         c_stat_sum_lower += c_stat_lower_opt;
3510         c_stat_sum_upper += c_stat_upper_opt;
3511         c_stat_sum_or += c_stat_or;
3512         c_stat_sum_exception += c_stat_exception;
3513
3514         c_stat_array_accesses = 0;
3515         c_stat_full_opt = 0;
3516         c_stat_no_opt = 0;
3517         c_stat_lower_opt = 0;
3518         c_stat_upper_opt = 0;
3519         c_stat_or = c_stat_exception = 0;
3520 #endif
3521
3522 }
3523
3524 /*      This function preforms necessary setup work, before the recursive function
3525         optimize_single loop can be called.
3526 */
3527 void optimize_loops(methodinfo *m)
3528 {
3529         struct LoopContainer *lc = c_allLoops;
3530
3531         /* first, merge loops with same header node - all loops with the same           */
3532         /* header node are optimizied in one pass, because they all depend on the       */
3533         /* same dynamic loop condition                                                                                          */
3534
3535 #ifdef LOOP_DEBUG
3536         printf("start analyze_double_headers\n");
3537         fflush(stdout);
3538 #endif
3539
3540         analyze_double_headers();
3541
3542         /* create array with loop nesting levels - nested loops cause problems,         */
3543         /* especially, when they modify index variables used in surrounding     loops   */
3544         /* store results in array c_nestedLoops and c_hierarchie                                        */
3545
3546 #ifdef LOOP_DEBUG
3547         printf("double done\n");
3548         fflush(stdout);
3549 #endif
3550
3551         analyze_nested(m);
3552
3553 #ifdef LOOP_DEBUG
3554         printf("analyze nested done\n");
3555         fflush(stdout);
3556 #endif
3557
3558         /* create array with entries for current loop                                                           */
3559         c_current_loop = DMNEW(int, m->basicblockcount);
3560         c_toVisit = DMNEW(int, m->basicblockcount);
3561         c_var_modified = DMNEW(int, m->maxlocals);
3562         c_null_check = DMNEW(int, m->maxlocals);
3563
3564         if ((c_constraints = (struct Constraint **) malloc((m->maxlocals+1) * sizeof(struct Constraint *))) == NULL)
3565                 c_mem_error();
3566
3567 #ifdef STATISTICS
3568         c_stat_num_loops = 0;           /* set statistic vars to zero                                   */
3569         c_stat_array_accesses = c_stat_sum_accesses = 0;
3570         c_stat_full_opt = c_stat_sum_full = 0;
3571         c_stat_no_opt = c_stat_sum_no = 0;
3572         c_stat_lower_opt = c_stat_sum_lower = 0;
3573         c_stat_upper_opt = c_stat_sum_upper = 0;
3574         c_stat_or = c_stat_sum_or = 0;
3575         c_stat_exception = c_stat_sum_exception = 0;
3576 #endif
3577
3578         /* init vars needed by all loops                                            */
3579         c_needs_redirection = false;
3580         c_newstart = NULL;
3581         c_old_xtablelength = m->exceptiontablelength;
3582
3583         /* loops have been topologically sorted                                     */
3584         lc = c_allLoops;
3585         while (lc != NULL) {
3586                 optimize_single_loop(m, lc);
3587
3588 #ifdef LOOP_DEBUG
3589                 printf(" *** Optimized loop *** \n");
3590                 fflush(stdout);
3591 #endif
3592
3593                 lc = lc->next;
3594                 }
3595 #ifdef LOOP_DEBUG
3596         printf("---*** All loops finished ***---\n");
3597         fflush(stdout);
3598 #endif
3599
3600         /* if global BB list start is modified, set block to new start              */
3601         if (c_needs_redirection == true)
3602                 m->basicblocks = c_newstart;
3603
3604 }
3605
3606
3607 /*
3608  * These are local overrides for various environment variables in Emacs.
3609  * Please do not remove this and leave it at the end of the file, where
3610  * Emacs will automagically detect them.
3611  * ---------------------------------------------------------------------
3612  * Local variables:
3613  * mode: c
3614  * indent-tabs-mode: t
3615  * c-basic-offset: 4
3616  * tab-width: 4
3617  * End:
3618  */