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