narray/analyze.c

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