src/vm/jit/optimizing/graph.c

   1 /* src/vm/jit/optimizing/graph.c - CFG
   2
   3    Copyright (C) 2005, 2006 R. Grafl, A. Krall, C. Kruegel, C. Oates,
   4    R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
   5    C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
   6    Institut f. Computersprachen - TU Wien
   7
   8    This file is part of CACAO.
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2, or (at
  13    your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful, but
  16    WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  23    02111-1307, USA.
  24
  25    Contact: cacao@complang.tuwien.ac.at
  26
  27    Authors: Christian Ullrich
  28
  29
  30 */
  31
  32 #include <stdlib.h>
  33
  34 #include "config.h"
  35
  36 #include "mm/memory.h"
  37
  38 #include "toolbox/bitvector.h"
  39
  40 #include "vm/jit/jit.h"
  41
  42 #include "vm/jit/optimizing/lsra.h"
  43 #include "vm/jit/optimizing/ssa.h"
  44 #include "vm/jit/optimizing/graph.h"
  45
  46 #ifdef GRAPH_DEBUG_VERBOSE
  47 #include "vmcore/options.h"
  48 #endif
  49
  50 /* Helpers for graph_make_cfg */
  51 void graph_add_cfg( jitdata *jd, graphdata *gd, basicblock *, basicblock *);
  52 void graph_add_exceptions(jitdata *jd, graphdata *gd);
  53 void graph_add_edge( graphdata *gd, int from, int to );
  54
  55 /* Helper for graph_get_first_* */
  56 int graph_get_first_(graph_element *ge, graphiterator *i);
  57 void transform_CFG(jitdata *, graphdata *);
  58
  59 #ifdef GRAPH_DEBUG_VERBOSE
  60 void graph_print(lsradata *ls, graphdata *gd);
  61 #endif
  62
  63
  64 graphdata *graph_init(int basicblockcount) {
  65         graphdata *gd;
  66         int i;
  67
  68         gd = NEW(graphdata);
  69 #ifdef GRAPH_DEBUG_CHECK
  70         /* Remember basicblockcount, so Array Bound checks can be made */
  71         gd->basicblockcount = basicblockcount;
  72 #endif
  73
  74         gd->num_succ = DMNEW(int, basicblockcount);
  75         gd->successor = DMNEW(graph_element *, basicblockcount);
  76
  77         gd->num_pred = DMNEW(int, basicblockcount);
  78         gd->predecessor = DMNEW(graph_element *, basicblockcount);
  79
  80         for(i = 0; i < basicblockcount; i++) {
  81                 gd->num_succ[i] = gd->num_pred[i] = 0;
  82                 gd->successor[i] = NULL;
  83                 gd->predecessor[i] = NULL;
  84         }
  85         return gd;
  86 }
  87
  88 int graph_get_num_predecessor(graphdata *gd, int b_index) {
  89         _GRAPH_CHECK_BOUNDS(b_index, 0, gd->basicblockcount);
  90         return gd->num_pred[b_index];
  91 }
  92
  93 int graph_get_num_successor(graphdata *gd, int b_index) {
  94         _GRAPH_CHECK_BOUNDS(b_index, 0, gd->basicblockcount);
  95         return gd->num_succ[b_index];
  96 }
  97
  98 int graph_get_first_successor(graphdata *gd, int b_index, graphiterator *i) {
  99         _GRAPH_CHECK_BOUNDS(b_index, 0, gd->basicblockcount);
 100         return graph_get_first_(gd->successor[b_index], i);
 101 }
 102
 103 int graph_get_first_predecessor(graphdata *gd, int b_index, graphiterator *i) {
 104         _GRAPH_CHECK_BOUNDS(b_index, 0, gd->basicblockcount);
 105         return graph_get_first_(gd->predecessor[b_index], i);
 106 }
 107
 108 int graph_get_next(graphiterator *i) {
 109         if ((*i) == NULL)
 110                 return -1;
 111         (*i) = (*i)->next;
 112         if ( (*i) == NULL )
 113                 return -1;
 114         else
 115                 return (*i)->value;
 116 }
 117
 118 int graph_get_first_(graph_element *ge, graphiterator *i) {
 119         if ( ((*i) = ge) == NULL)
 120                 return -1;
 121         else
 122                 return (*i)->value;
 123 }
 124
 125 bool graph_has_multiple_predecessors( graphdata *gd, int b_index) {
 126         _GRAPH_CHECK_BOUNDS(b_index, 0, gd->basicblockcount);
 127         return (gd->num_pred[b_index] > 1);
 128 }
 129
 130 bool graph_has_multiple_successors( graphdata *gd, int b_index) {
 131         _GRAPH_CHECK_BOUNDS(b_index, 0, gd->basicblockcount);
 132         return (gd->num_succ[b_index] > 1);
 133 }
 134
 135 void graph_add_edge( graphdata *gd, int from, int to ) {
 136         graphiterator i;
 137         graph_element *n;
 138         int b;
 139
 140         /* prevent multiple similar edges from TABLESWITCH and */
 141         /* LOOKUPSWITCH */
 142         b = graph_get_first_successor(gd, from, &i);
 143         for( ; (b != -1) && ( b != to); b = graph_get_next(&i));
 144         if (b != -1) /* edge from->to already existing */
 145                 return;
 146
 147         /* We need two new graph_elements. One for successors and one for */
 148         /* predecessors */
 149         n = DMNEW(graph_element, 2);
 150
 151         n->value=to;
 152         n->next=gd->successor[from];
 153         gd->successor[from]=n;
 154         gd->num_succ[from]++;
 155
 156         n++; /* take next allocated graph_element */
 157         n->value=from;
 158         n->next=gd->predecessor[to];
 159         gd->predecessor[to]=n;
 160         gd->num_pred[to]++;
 161 }
 162
 163 /* split the edge from BB from shown by iterator i with new_block */
 164 void graph_split_edge(graphdata *gd, int from, graphiterator *i, int new_block) {
 165         graphiterator i_pred;
 166         graph_element *n;
 167         int l, succ;
 168
 169         /* i->value is the BB index of the "old" successor */
 170
 171         succ = (*i)->value;
 172
 173         /* search for iterator showing predecessor edge from BB succ back to */
 174         /* from */
 175
 176         l = graph_get_first_predecessor(gd, succ, &i_pred);
 177         for(; (l != -1) && (l != from); l = graph_get_next(&i_pred));
 178         _GRAPH_ASSERT(l == from);
 179
 180         /* change CFG entries */
 181
 182         (*i)->value = new_block;
 183         i_pred->value = new_block;
 184
 185         /* and insert the CFG successor and predecesser entries for new_block */
 186         /* 2 entries needed */
 187
 188         n = DMNEW(graph_element, 2);
 189
 190         /* make the successor entry for new_block */
 191
 192         n->value = succ;
 193         n->next = gd->successor[new_block];
 194         gd->successor[new_block] = n;
 195         gd->num_succ[new_block]++;
 196
 197         /* make the predecessor entry for new_block */
 198
 199         n++;
 200         n->value = from;
 201         n->next = gd->predecessor[new_block];
 202         gd->predecessor[new_block] = n;
 203         gd->num_pred[new_block]++;
 204 }
 205
 206 /***********************************************
 207 Generate the Control Flow Graph
 208 ( pred,succ,num_pred of lsradata structure)
 209 ************************************************/
 210 void graph_make_cfg(jitdata *jd,graphdata *gd) {
 211         instruction *iptr;
 212         lookup_target_t *lookup;
 213         branch_target_t *table;
 214         int len, i, l;
 215         methodinfo *m;
 216         codegendata *cd;
 217         registerdata *rd;
 218         lsradata *ls;
 219         basicblock *bptr;
 220
 221         m = jd->m;
 222         cd = jd->cd;
 223         rd = jd->rd;
 224         ls = jd->ls;
 225
 226         /* Add edge from new Basic Block 0 (parameter initialization) */
 227         graph_add_edge(gd, 0, 1);
 228
 229         for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
 230                 if (bptr->flags >= BBREACHED) {
 231                         if ((len = bptr->icount)) {
 232                                 /* set iptr to last non NOP instruction */
 233                                 iptr = bptr->iinstr + bptr->icount -1;
 234                                 while ((len>0) && (iptr->opc == ICMD_NOP)) {
 235                                         len--;
 236                                         iptr--;
 237                                 }
 238                                 /* block contains instructions  */
 239                                 switch (iptr->opc) {            /* check type of last instruction */
 240                                 case ICMD_RETURN:
 241                                 case ICMD_IRETURN:
 242                                 case ICMD_LRETURN:
 243                                 case ICMD_FRETURN:
 244                                 case ICMD_DRETURN:
 245                                 case ICMD_ARETURN:
 246                                 case ICMD_ATHROW:
 247                                         break;                            /* function returns -> end of graph */
 248
 249                                 case ICMD_IFNULL:
 250                                 case ICMD_IFNONNULL:
 251                                 case ICMD_IFEQ:
 252                                 case ICMD_IFNE:
 253                                 case ICMD_IFLT:
 254                                 case ICMD_IFGE:
 255                                 case ICMD_IFGT:
 256                                 case ICMD_IFLE:
 257                                 case ICMD_IF_LEQ:
 258                                 case ICMD_IF_LNE:
 259                                 case ICMD_IF_LLT:
 260                                 case ICMD_IF_LGE:
 261                                 case ICMD_IF_LGT:
 262                                 case ICMD_IF_LLE:
 263                                 case ICMD_IF_ICMPEQ:
 264                                 case ICMD_IF_ICMPNE:
 265                                 case ICMD_IF_ICMPLT:
 266                                 case ICMD_IF_ICMPGE:
 267                                 case ICMD_IF_ICMPGT:
 268                                 case ICMD_IF_ICMPLE:
 269                                 case ICMD_IF_LCMPEQ:
 270                                 case ICMD_IF_LCMPNE:
 271                                 case ICMD_IF_LCMPLT:
 272                                 case ICMD_IF_LCMPGE:
 273                                 case ICMD_IF_LCMPGT:
 274                                 case ICMD_IF_LCMPLE:
 275                                 case ICMD_IF_ACMPEQ:
 276                                 case ICMD_IF_ACMPNE:                /* branch -> add next block */
 277                                         /* Add branch target */
 278                                         graph_add_cfg(jd, gd, bptr, iptr->dst.block);
 279                                         /* Add fall through path */
 280                                         graph_add_cfg(jd, gd, bptr, bptr->next);
 281                                         break;
 282
 283
 284                                 case ICMD_GOTO:
 285                                         graph_add_cfg(jd, gd, bptr,  iptr->dst.block);
 286                                         break;                                  /* visit branch (goto) target   */
 287
 288                                 case ICMD_TABLESWITCH:          /* switch statement                             */
 289                                         table = iptr->dst.table;
 290                                         l = iptr->sx.s23.s2.tablelow;
 291                                         i = iptr->sx.s23.s3.tablehigh;
 292                                         i = i - l + 1;
 293
 294                                         /* Add default target */
 295
 296                                         graph_add_cfg(jd, gd, bptr,  table[0].block);
 297                                         table += i;
 298
 299                                         while (--i >= 0) {
 300                                                 graph_add_cfg(jd, gd, bptr,  table->block);
 301                                                 --table;
 302                                         }
 303                                         break;
 304
 305                                 case ICMD_LOOKUPSWITCH:         /* switch statement                             */
 306                                         lookup = iptr->dst.lookup;
 307                                         i = iptr->sx.s23.s2.lookupcount;
 308
 309                                         while (--i >= 0) {
 310                                                 graph_add_cfg(jd, gd, bptr, lookup->target.block);
 311                                                 lookup++;
 312                                         }
 313
 314                                         graph_add_cfg(jd, gd, bptr, iptr->sx.s23.s3.lookupdefault.block);
 315                                         break;
 316
 317                                 case ICMD_RET:
 318                                 case ICMD_JSR:
 319                                         assert(0);
 320                                         break;
 321
 322                                 case ICMD_NOP:
 323                                         assert(0);
 324
 325                                 default:
 326                                         graph_add_cfg(jd, gd, bptr, bptr + 1 );
 327                                         break;
 328                             } /* switch (iptr->opc)*/
 329                     }     /* if (bptr->icount) */
 330             }         /* if (bptr->flags >= BBREACHED) */
 331         }             /* for (bptr = ...; bptr != NULL; bptr = bptr->next) */
 332
 333         graph_add_exceptions(jd, gd);
 334         transform_CFG(jd, gd);
 335
 336 #ifdef GRAPH_DEBUG_VERBOSE
 337         if (compileverbose)
 338                 graph_print(ls, gd);
 339 #endif
 340 }
 341
 342 /*****************************************************************
 343 add Edges from guarded Areas to Exception handlers in the CFG
 344 *****************************************************************/
 345 void graph_add_exceptions(jitdata *jd, graphdata *gd) {
 346 #if 0
 347         basicblock *bptr;
 348         raw_exception_entry *ex;
 349         codegendata *cd;
 350
 351         cd = jd->cd;
 352
 353         /* add cfg edges from all bb of a try block to the start of the according */
 354         /* exception handler to ensure the right order after depthfirst search    */
 355
 356         ex=jd->exceptiontable;
 357
 358 #ifdef GRAPH_DEBUG_VERBOSE
 359         if (compileverbose)
 360                 printf("ExTable(%i): ", jd->exceptiontablelength);
 361 #endif
 362
 363         for (; ex != NULL; ex = ex->down) {
 364
 365 #ifdef GRAPH_DEBUG_VERBOSE
 366                 if (compileverbose)
 367                         printf("[%i-%i]->%i ",ex->start->nr, ex->end->nr,
 368                                    ex->handler->nr);
 369 #endif
 370
 371                 _GRAPH_ASSERT(ex->handler->nr < jd->new_basicblockcount);
 372                 _GRAPH_ASSERT(ex->handler->flags >= BBREACHED);
 373                 _GRAPH_ASSERT(ex->start->nr <= ex->end->nr);
 374
 375                 /* loop all valid Basic Blocks of the guarded area and add CFG edges  */
 376                 /* to the appropriate handler */
 377                 for (bptr = ex->start; (bptr != NULL) && (bptr != ex->end); bptr = bptr->next)
 378                         if (bptr->flags >= BBREACHED)
 379                                 graph_add_cfg(jd, gd, bptr, ex->handler);
 380
 381                 _GRAPH_ASSERT((bptr != NULL)
 382                                           && ((bptr->flags >=BBREACHED) || (bptr == ex->end)));
 383         }
 384 #ifdef GRAPH_DEBUG_VERBOSE
 385         if (compileverbose)
 386                 printf("\n");
 387 #endif
 388 #endif
 389 }
 390
 391
 392 /******************************************************************
 393 Add the CFG Edge into next und succ
 394 ******************************************************************/
 395 void graph_add_cfg( jitdata *jd, graphdata *gd, basicblock *from,
 396                                         basicblock *to) {
 397
 398         /* ignore Empty, Deleted,... Basic Blocks as target */
 399         /* TODO: Setup BasicBlock array before to avoid this */
 400         /*       best together with using the basicblock list, so lsra works */
 401         /*       with opt_loops, too */
 402
 403         for (; (to != NULL) && (to->flags < BBREACHED); to = to->next);
 404
 405         _GRAPH_ASSERT(to != NULL);
 406
 407
 408         /* add one to from and to, so the to be inserted Basic Block 0 is */
 409         /* already regarded */
 410         graph_add_edge( gd, from->nr + 1, to->nr + 1);
 411 }
 412
 413
 414 /*****************************************************************
 415 Sort Basic Blocks using Depth First search in reverse post order
 416 In: ls->basicblockcount, ls->basicblocks[], gd->
 417 Out: ls->sorted, ls->sorted_rev
 418 *****************************************************************/
 419
 420 void graph_DFS(lsradata *ls, graphdata *gd) {
 421         int *stack;
 422         int *visited;
 423         int stack_top;
 424         bool not_finished;
 425         int i,p,s, num_pred;
 426         graphiterator iter;
 427
 428         ls->sorted = DMNEW(int, ls->basicblockcount);
 429         ls->sorted_rev = DMNEW(int, ls->basicblockcount);
 430
 431         stack = DMNEW( int, ls->basicblockcount);
 432         visited = (int *)DMNEW( bool, ls->basicblockcount);
 433         for (i = 0; i < ls->basicblockcount; i++) {
 434                 visited[i] = 0;
 435                 ls->sorted[i]=-1;
 436                 ls->sorted_rev[i]=-1;
 437         }
 438
 439     stack[0] = 0; /* start with Block 0 */
 440         stack_top = 1;
 441         /* Start Block is handled right and can be put in sorted */
 442         visited[0] = graph_get_num_predecessor(gd , 0);
 443         p = 0;
 444         not_finished = true;
 445         while (not_finished) {
 446                 while (stack_top != 0) {
 447                         stack_top--;
 448                         i = stack[stack_top];
 449                         ls->sorted[p]=i;
 450                         p++;
 451                         s = graph_get_first_successor(gd, i, &iter);
 452                         for (; s != -1; s = graph_get_next(&iter)) {
 453                                 visited[s]++;
 454                                 if (visited[s] ==  graph_get_num_predecessor(gd, s)) {
 455                                         /* push the node on the stack, only if all ancestors have */
 456                                         /* been visited */
 457                                         stack[stack_top] = s;
 458                                         stack_top++;
 459                                 }
 460                         }
 461                 }
 462                 not_finished = false;
 463                 for (i=1; i < ls->basicblockcount; i++) {
 464                         /* search for visited blocks, which have not reached the num_pre */
 465                         /* and put them on the stack -> happens with backedges */
 466                         num_pred = graph_get_num_predecessor(gd, i);
 467                         if ((visited[i] != 0) && (visited[i] < num_pred)) {
 468                                 stack[stack_top] = i;
 469                                 stack_top++;
 470                                 visited[i] = num_pred;
 471                                 not_finished=true;
 472                                 break;
 473                         }
 474                 }
 475         }
 476
 477         for(i = 0; i < ls->basicblockcount; i++)
 478                 if (ls->sorted[i] != -1)
 479                          ls->sorted_rev[ls->sorted[i]] = i;
 480 }
 481
 482
 483 void graph_init_basicblock(jitdata *jd, basicblock *bptr, int b_index) {
 484                 bptr->nr = b_index;
 485                 bptr->icount = 0;
 486                 bptr->iinstr = NULL;
 487                 bptr->type = BBTYPE_STD;
 488                 bptr->flags = BBFINISHED;
 489                 bptr->invars = NULL;
 490                 bptr->outvars = NULL;
 491                 bptr->indepth = 0;
 492                 bptr->outdepth = 0;
 493                 bptr->branchrefs = NULL;
 494                 bptr->mpc = -1;
 495                 bptr->next = NULL;
 496                 bptr->method = jd->m;
 497 }
 498
 499 /*********************************************************************+
 500 After the "original" CFG has been created, it has to be adopted for
 501 SSA. (inluding insertion of new Basic Blocks)
 502
 503 TODO: Do not insert blocks right now - just adopt the call graph!
 504       After the phi moves are determined create only the needed Blocks
 505 **********************************************************************/
 506 void transform_CFG(jitdata *jd, graphdata *gd) {
 507         int i, j, k, n, num_new_blocks;
 508         int **var_def;
 509         basicblock *tmp, *bptr;
 510         s4 *in, *out, *new_in_stack, *new_out_stack;
 511         graphiterator iter;
 512         int *num_succ;
 513         struct graph_element **successor;
 514         int *num_pred;
 515         struct graph_element **predecessor;
 516         methodinfo *m;
 517         codegendata *cd;
 518         registerdata *rd;
 519         lsradata *ls;
 520
 521         m = jd->m;
 522         cd = jd->cd;
 523         rd = jd->rd;
 524         ls = jd->ls;
 525
 526         /* with SSA a new Basic Block 0 is inserted for parameter initialisation  */
 527         /* & look for nodes with multiple successors leading to nodes with        */
 528         /* multiple predecessor -> if found insert a new block between to split   */
 529         /* this edge. As first step count how many blocks have to be inserted.    */
 530
 531         num_new_blocks = 1;
 532         for(i = 0; i< jd->basicblockcount + 1; i++) {
 533                 if (graph_has_multiple_successors(gd, i)) {
 534                         k = graph_get_first_successor(gd, i, &iter);
 535                         for(; k != -1; k = graph_get_next(&iter)) {
 536                                 /* check for successor blocks with more than one       */
 537                                 /* predecessor. For each found incremet num_new_blocks */
 538                                 if (graph_has_multiple_predecessors(gd, k))
 539                                         num_new_blocks++;
 540                         }
 541                 }
 542         }
 543
 544         /* increase now basicblockcount accordingly. */
 545         ls->basicblockcount = jd->basicblockcount + num_new_blocks;
 546
 547         ls->basicblocks = DMNEW(basicblock *, ls->basicblockcount);
 548         for(i = 0; i< ls->basicblockcount; i++)
 549                 ls->basicblocks[i] = NULL;
 550
 551         /* copy Basic Block References to ls->basicblocks */
 552
 553         for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
 554 /*              if (bptr->flags >= BBREACHED) { */
 555                         _GRAPH_ASSERT(bptr->nr < jd->basicblockcount);
 556                         ls->basicblocks[bptr->nr + 1] = bptr;
 557                         bptr->nr = bptr->nr+1;
 558 /*              } */
 559         }
 560
 561         /* Create new Basic Blocks:
 562            0, [jd->new_basicblockcount..ls->basicblockcount[ */
 563         /* num_new_blocks have to be inserted*/
 564
 565         tmp = DMNEW( basicblock, num_new_blocks);
 566         ls->basicblocks[0] = tmp;
 567         graph_init_basicblock( jd, tmp, 0);
 568         tmp++;
 569         ls->basicblocks[0]->next = ls->basicblocks[1];
 570
 571         if (ls->basicblockcount > jd->basicblockcount + 1) {
 572                 /* new Blocks have to be inserted                   */
 573                 num_succ = DMNEW(int, ls->basicblockcount);
 574                 successor = DMNEW(graph_element *, ls->basicblockcount);
 575
 576                 num_pred = DMNEW(int, ls->basicblockcount);
 577                 predecessor = DMNEW(graph_element *, ls->basicblockcount);
 578
 579                 /* regard the + 1 for the already inserted new BB 0 */
 580                 /* So recreate ls->var_def                          */
 581                 var_def = DMNEW(int *, ls->basicblockcount);
 582                 for(i = 0; i < jd->basicblockcount + 1; i++) {
 583                         var_def[i] = ls->var_def[i];
 584                         num_succ[i] = gd->num_succ[i];
 585                         num_pred[i] = gd->num_pred[i];
 586                         successor[i] = gd->successor[i];
 587                         predecessor[i] = gd->predecessor[i];
 588                 }
 589                 for(i = jd->basicblockcount + 1; i < ls->basicblockcount; i++) {
 590                         var_def[i] = bv_new(jd->varcount);
 591                         graph_init_basicblock( jd, tmp, i);
 592                         ls->basicblocks[i] = tmp;
 593                         tmp++;
 594
 595                         num_succ[i] = 0;
 596                         num_pred[i] = 0;
 597                         successor[i] = NULL;
 598                         predecessor[i] = NULL;
 599                 }
 600                 ls->var_def = var_def;
 601                 gd->num_succ = num_succ;
 602                 gd->num_pred = num_pred;
 603                 gd->successor = successor;
 604                 gd->predecessor = predecessor;
 605 #ifdef GRAPH_DEBUG_CHECK
 606                 /* Remember basicblockcount, so Array Bound checks can be made */
 607                 gd->basicblockcount = ls->basicblockcount;
 608 #endif
 609         }
 610
 611         /* Now Split the edges */
 612         num_new_blocks = jd->basicblockcount + 1; /* first free new block index */
 613         for(i = 0; i < jd->basicblockcount + 1; i++) {
 614                 if (graph_has_multiple_successors(gd, i)) {/* more than one successor */
 615                         j = graph_get_first_successor( gd, i, &iter);
 616                         for(; j != -1; j = graph_get_next(&iter)) {
 617                                 if (graph_has_multiple_predecessors(gd, j)) {
 618                                         /* and more than one predecessor -> split edge */
 619                                         _GRAPH_ASSERT(num_new_blocks < ls->basicblockcount);
 620
 621                                         /* insert new Block num_new_blocks */
 622
 623                                         /* splite the edge from BB i to j with the new BB */
 624                                         /* num_new_blocks ( i->j --> i->nnb->j)*/
 625                                         /* iter_succ shows the edge from i to j */
 626                                         graph_split_edge(gd, i, &iter, num_new_blocks);
 627
 628                                         ls->basicblocks[num_new_blocks]->indepth =
 629                                                 ls->basicblocks[i]->outdepth;
 630                                         out = ls->basicblocks[i]->outvars;
 631                                         ls->basicblocks[num_new_blocks]->invars = in = NULL;
 632
 633                                         if (ls->basicblocks[num_new_blocks]->indepth > 0)
 634                                                 new_in_stack = DMNEW( s4,
 635                                                                           ls->basicblocks[num_new_blocks]->indepth);
 636                                                 new_out_stack = DMNEW( s4,
 637                                                                           ls->basicblocks[num_new_blocks]->indepth);
 638
 639                                         for(n=0; n<ls->basicblocks[num_new_blocks]->indepth; n++) {
 640                                                 new_in_stack[n] = out[n];
 641                                                 new_out_stack[n] = out[n];
 642                                         }
 643                                         ls->basicblocks[num_new_blocks]->invars = new_in_stack;
 644
 645                                         /* Create Outstack */
 646                                         ls->basicblocks[num_new_blocks]->outvars =
 647                                                 new_out_stack;
 648                                         ls->basicblocks[num_new_blocks]->outdepth =
 649                                                 ls->basicblocks[num_new_blocks]->indepth;
 650
 651                                         _GRAPH_ASSERT(ls->basicblocks[num_new_blocks]->outdepth ==
 652                                                                   ls->basicblocks[j]->indepth );
 653
 654 #if 0
 655                                         /* !!!! There can't be inoutvar definitions in one of these */
 656                                         /* newly inserted basicblocks !!!! */
 657
 658                                         /* Add Definition */
 659                                         /* decrease nr temporarly, because ssa_set_interface*/
 660                                         /* adds 1 since it is called from stack.c, where there is */
 661                                         /* no new BB 0 inserted like now */
 662
 663                                         ls->basicblocks[num_new_blocks]->nr--;
 664                                         ssa_set_interface(jd, ls->basicblocks[num_new_blocks]);
 665                                         ls->basicblocks[num_new_blocks]->nr++;
 666 #endif
 667                                         num_new_blocks++;
 668                                 }
 669                         }
 670                 }
 671         }
 672 }
 673
 674 void transform_BB(jitdata *jd, graphdata *gd) {
 675         int n, len;
 676         int pred, succ;
 677         basicblock *last_block;
 678         instruction *iptr;
 679         graphiterator iter;
 680         methodinfo *m;
 681         lsradata *ls;
 682
 683         m = jd->m;
 684         ls = jd->ls;
 685
 686         /* the "real" last Block is always an empty block        */
 687         /* so take the one before, to insert new blocks after it */
 688         last_block = &(jd->basicblocks[jd->basicblockcount - 1]);
 689         _GRAPH_ASSERT(last_block->next->next == NULL);
 690         _GRAPH_ASSERT(last_block->next->flags <= BBREACHED);
 691         last_block->next->nr = ls->basicblockcount;
 692
 693         /* look through new blocks */
 694         for(n = jd->basicblockcount + 1; n < ls->basicblockcount ; n++) {
 695                 /* if a phi move happens at this block, we need this block */
 696                 /* if not, remove him from the CFG */
 697                 if (ls->num_phi_moves[n] > 0) {
 698                         /* i can only have one predecessor and one successor! */
 699                         _GRAPH_ASSERT( graph_has_multiple_predecessors(gd, n) == false);
 700                         _GRAPH_ASSERT( graph_has_multiple_successors(gd, n) == false);
 701
 702                         succ = graph_get_first_successor(gd, n, &iter);
 703                         pred = graph_get_first_predecessor(gd, n, &iter);
 704
 705                         /* set iptr to last instruction                       */
 706                         len = ls->basicblocks[pred]->icount;
 707                         iptr = ls->basicblocks[pred]->iinstr + len - 1;
 708                         while ((len>0) && (iptr->opc == ICMD_NOP)) {
 709                                 len--;
 710                                 iptr--;
 711                         }
 712
 713
 714                         /* with JSR there can not be multiple successors  */
 715                         _GRAPH_ASSERT(iptr->opc != ICMD_JSR);
 716                         /* If the return Statment has more successors and  */
 717                         /* one of these has more predecessor, we are in    */
 718                         /* troubles - one would have to insert a new Block */
 719                         /* after the one which executes the ICMD_JSR       */
 720                         /* !!TODO!! if subroutines will not be inlined     */
 721                         _GRAPH_ASSERT(iptr->opc != ICMD_RET);
 722
 723                         /* link new block into basicblocks list */
 724                         /* if edge to split is the "fallthrough" path of the */
 725                         /* conditional, then link the new block inbetween    */
 726                         /* and generate no ICMD */
 727                         /* else if edge to split is the branch, generate a   */
 728                         /* ICMD_GOTO and add new BB at the end of the BB List*/
 729                         if ((ls->basicblocks[pred]->next == ls->basicblocks[succ])
 730                                 && (iptr->opc != ICMD_LOOKUPSWITCH)
 731                                 && (iptr->opc != ICMD_TABLESWITCH)
 732                                 && (iptr->opc != ICMD_GOTO)) {
 733                                 /* GOTO, *SWITCH have no fallthrough path */
 734
 735                                 /* link into fallthrough path */
 736
 737
 738                                 ls->basicblocks[n]->next =
 739                                         ls->basicblocks[pred]->next;
 740                                 ls->basicblocks[pred]->next =
 741                                         ls->basicblocks[n];
 742                                 /* generate no instructions */
 743                                 ls->basicblocks[n]->icount = 1;
 744                                 ls->basicblocks[n]->iinstr = NEW(instruction);
 745                                 ls->basicblocks[n]->iinstr[0].opc =     ICMD_NOP;
 746                         } else {
 747                                 /* Block n is in the Branch path */
 748                                 /* link Block at the end */
 749                                 ls->basicblocks[n]->next =last_block->next;
 750                                 last_block->next = ls->basicblocks[n];
 751                                 last_block = ls->basicblocks[n];
 752
 753                                 /* change the Branch Target to BB i */
 754
 755
 756
 757                                 switch(iptr->opc) {
 758                                 case ICMD_LOOKUPSWITCH:
 759                                         {
 760                                                 s4 i;
 761                                                 lookup_target_t *lookup;
 762
 763                                                 lookup = iptr->dst.lookup;
 764
 765                                                 i = iptr->sx.s23.s2.lookupcount;
 766
 767                                                 while (--i >= 0) {
 768                                                         if (lookup->target.block == ls->basicblocks[succ])
 769                                                                 /* target found -> change */
 770                                                                 lookup->target.block = ls->basicblocks[n];
 771                                                         lookup++;
 772                                                 }
 773
 774                                                 if (iptr->sx.s23.s3.lookupdefault.block == ls->basicblocks[succ])
 775                                                         /* target found -> change */
 776                                                         iptr->sx.s23.s3.lookupdefault.block = ls->basicblocks[n];
 777                                         }
 778                                         break;
 779                                 case ICMD_TABLESWITCH:
 780                                         {
 781                                                 s4 i, l;
 782                                                 branch_target_t *table;
 783
 784                                                 table = iptr->dst.table;
 785
 786                                                 l = iptr->sx.s23.s2.tablelow;
 787                                                 i = iptr->sx.s23.s3.tablehigh;
 788
 789                                                 i = i - l + 1;
 790
 791                                                 if (table[0].block ==  ls->basicblocks[succ]) /* default target */
 792                                                         /* target found -> change*/
 793                                                         table[0].block = ls->basicblocks[n];
 794
 795                                                 table += i;
 796
 797                                                 while (--i >= 0) {
 798                                                         if (table->block == ls->basicblocks[succ])
 799                                                                 /* target found -> change */
 800                                                                 table->block = ls->basicblocks[n];
 801                                                         --table;
 802                                                 }
 803                                         }
 804                                         break;
 805                                 case ICMD_IFNULL:
 806                                 case ICMD_IFNONNULL:
 807                                 case ICMD_IFEQ:
 808                                 case ICMD_IFNE:
 809                                 case ICMD_IFLT:
 810                                 case ICMD_IFGE:
 811                                 case ICMD_IFGT:
 812                                 case ICMD_IFLE:
 813                                 case ICMD_IF_LEQ:
 814                                 case ICMD_IF_LNE:
 815                                 case ICMD_IF_LLT:
 816                                 case ICMD_IF_LGE:
 817                                 case ICMD_IF_LGT:
 818                                 case ICMD_IF_LLE:
 819                                 case ICMD_IF_ICMPEQ:
 820                                 case ICMD_IF_ICMPNE:
 821                                 case ICMD_IF_ICMPLT:
 822                                 case ICMD_IF_ICMPGE:
 823                                 case ICMD_IF_ICMPGT:
 824                                 case ICMD_IF_ICMPLE:
 825                                 case ICMD_IF_LCMPEQ:
 826                                 case ICMD_IF_LCMPNE:
 827                                 case ICMD_IF_LCMPLT:
 828                                 case ICMD_IF_LCMPGE:
 829                                 case ICMD_IF_LCMPGT:
 830                                 case ICMD_IF_LCMPLE:
 831                                 case ICMD_IF_ACMPEQ:
 832                                 case ICMD_IF_ACMPNE:
 833                                 case ICMD_GOTO:
 834                                         _GRAPH_ASSERT(iptr->dst.block == ls->basicblocks[succ]);
 835                                         iptr->dst.block = ls->basicblocks[n];
 836                                         break;
 837                                 default:
 838                                         /* Exception Edge to split */
 839                                         /* not handled by now -> fallback to regalloc */
 840                                         exit(1);
 841                                 }
 842
 843                                 /* Generate the ICMD_GOTO */
 844                                 ls->basicblocks[n]->icount = 1;
 845                                 ls->basicblocks[n]->iinstr =
 846                                         DNEW(instruction);
 847                                 ls->basicblocks[n]->iinstr->opc =
 848                                         ICMD_GOTO;
 849                                 ls->basicblocks[n]->iinstr->dst.block =
 850                                         ls->basicblocks[succ];
 851                         }
 852                 }
 853         }
 854 }
 855
 856 #ifdef GRAPH_DEBUG_VERBOSE
 857 void graph_print(lsradata *ls, graphdata *gd) {
 858         int i,j;
 859         graphiterator iter;
 860         printf("graph_print: basicblockcount %3i\n", ls->basicblockcount);
 861
 862         printf("CFG: \n");
 863         for(i = 0; i < ls->basicblockcount; i++) {
 864                 printf("%3i: ",i);
 865                 j = graph_get_first_successor(gd, i, &iter);
 866                 for(; j != -1; j = graph_get_next(&iter)) {
 867                         printf("%3i ",j);
 868                 }
 869                 printf("\n");
 870         }
 871         printf("Pred: \n");
 872         for(i = 0; i < ls->basicblockcount; i++) {
 873                 printf("%3i: ",i);
 874                 j = graph_get_first_predecessor(gd, i, &iter);
 875                 for(; j != -1; j = graph_get_next(&iter)) {
 876                         printf("%3i ", j);
 877                 }
 878                 printf("\n");
 879         }
 880 }
 881 #endif
 882
 883
 884
 885 /*
 886  * These are local overrides for various environment variables in Emacs.
 887  * Please do not remove this and leave it at the end of the file, where
 888  * Emacs will automagically detect them.
 889  * ---------------------------------------------------------------------
 890  * Local variables:
 891  * mode: c
 892  * indent-tabs-mode: t
 893  * c-basic-offset: 4
 894  * tab-width: 4
 895  * End:
 896  */