src/vm/jit/loop/analyze.c

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