src/vm/jit/optimizing/graph.c

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