narray/analyze.c

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