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