src/vm/jit/loop/analyze.c

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