src/vm/jit/loop/analyze.c

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