src/vm/jit/loop/analyze.c

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