src/vm/jit/loop/analyze.c

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