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