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