src/vm/jit/cfg.c

   1 /* src/vm/jit/cfg.c - build a control-flow graph
   2
   3    Copyright (C) 2006, 2007 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    J. Wenninger, 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., 51 Franklin Street, Fifth Floor, Boston, MA
  23    02110-1301, USA.
  24
  25 */
  26
  27
  28 #include "config.h"
  29
  30 #include <assert.h>
  31 #include <stdint.h>
  32
  33 #include "mm/memory.hpp"
  34
  35 #include "vm/global.h"
  36
  37 #include "vm/jit/jit.hpp"
  38 #include "vm/jit/stack.h"
  39
  40
  41 /* cfg_allocate_predecessors ***************************************************
  42
  43    Allocates the predecessor array, if there is none, and resets the
  44    predecessor count.
  45
  46 *******************************************************************************/
  47
  48 static void cfg_allocate_predecessors(basicblock *bptr)
  49 {
  50         if (bptr->predecessors == NULL) {
  51                 bptr->predecessors = DMNEW(basicblock*, bptr->predecessorcount);
  52
  53                 bptr->predecessorcount = 0;
  54         }
  55 }
  56
  57
  58 /* cfg_allocate_successors *****************************************************
  59
  60    Allocates the succecessor array, if there is none, and resets the
  61    predecessor count.
  62
  63 *******************************************************************************/
  64
  65 static void cfg_allocate_successors(basicblock *bptr)
  66 {
  67         if (bptr->successors == NULL) {
  68                 bptr->successors = DMNEW(basicblock*, bptr->successorcount);
  69
  70                 bptr->successorcount = 0;
  71         }
  72 }
  73
  74
  75 /* cfg_insert_predecessor ******************************************************
  76
  77    Inserts a predecessor into the array, but checks for duplicate
  78    entries.  This is used for TABLESWITCH and LOOKUPSWITCH.
  79
  80 *******************************************************************************/
  81
  82 static void cfg_insert_predecessors(basicblock *bptr, basicblock *pbptr)
  83 {
  84         basicblock **tbptr;
  85         int          i;
  86
  87         tbptr = bptr->predecessors;
  88
  89         /* check if the predecessors is already stored in the array */
  90
  91         for (i = 0; i < bptr->predecessorcount; i++, tbptr++)
  92                 if (*tbptr == pbptr)
  93                         return;
  94
  95         /* not found, insert it */
  96
  97         bptr->predecessors[bptr->predecessorcount] = pbptr;
  98         bptr->predecessorcount++;
  99 }
 100
 101 static void cfg_insert_successors(basicblock *bptr, basicblock *pbptr)
 102 {
 103         basicblock **tbptr;
 104         int          i;
 105
 106         tbptr = bptr->successors;
 107
 108         /* check if the successor is already stored in the array */
 109
 110         for (i = 0; i < bptr->successorcount; i++, tbptr++)
 111                 if (*tbptr == pbptr)
 112                         return;
 113
 114         /* not found, insert it */
 115
 116         bptr->successors[bptr->successorcount] = pbptr;
 117         bptr->successorcount++;
 118 }
 119
 120
 121 /* cfg_build *******************************************************************
 122
 123    Build a control-flow graph in finding all predecessors and
 124    successors for the basic blocks.
 125
 126 *******************************************************************************/
 127
 128 bool cfg_build(jitdata *jd)
 129 {
 130         basicblock      *bptr;
 131         basicblock      *tbptr;
 132         basicblock      *ntbptr;
 133         instruction     *iptr;
 134         branch_target_t *table;
 135         lookup_target_t *lookup;
 136         int              i;
 137         bool             has_fallthrough;
 138
 139         /* process all basic blocks to find the predecessor/successor counts */
 140
 141         bptr = jd->basicblocks;
 142
 143         for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
 144
 145                 if (bptr->type == BBTYPE_EXH) {
 146                         /* predecessorcount for exception handlers is initialized to -1,
 147                            so we need to fix it to 0. */
 148                         bptr->predecessorcount += 1;
 149                 }
 150
 151                 if ((bptr->icount == 0) || (bptr->flags == BBUNDEF))
 152                         continue;
 153
 154                 iptr = bptr->iinstr + bptr->icount - 1;
 155
 156                 /* skip NOPs at the end of the block */
 157
 158                 while (iptr->opc == ICMD_NOP) {
 159                         if (iptr == bptr->iinstr)
 160                                 break;
 161                         iptr--;
 162                 }
 163
 164                 if (iptr->opc == ICMD_GOTO) {
 165
 166                         /*
 167                          This is needed for the following special case caused by
 168                          stack_reach_next_block:
 169                          I.e. there might be instructions causing control flow before
 170                          a GOTO:
 171
 172                          ....
 173                          129: 192:  IFEQ            Ti102 0 (0x00000000) --> L052
 174                          131: 193:  NOP
 175                            0:   0:  GOTO            --> L060
 176                         */
 177
 178                         bptr->successorcount++;
 179
 180                         tbptr = iptr->dst.block;
 181                         tbptr->predecessorcount++;
 182
 183                         if (iptr == bptr->iinstr) {
 184                                 continue;
 185                         }
 186
 187                         iptr--;
 188
 189                         while (iptr->opc == ICMD_NOP) {
 190                                 if (iptr == bptr->iinstr) {
 191                                         break;
 192                                 }
 193                                 iptr--;
 194                         }
 195
 196                         has_fallthrough = false;
 197                 } else {
 198                         has_fallthrough = true;
 199                 }
 200
 201                 switch (icmd_table[iptr->opc].controlflow) {
 202
 203                 case CF_END:
 204                         break;
 205
 206                 case CF_IF:
 207
 208                         bptr->successorcount += 2;
 209
 210                         tbptr  = iptr->dst.block;
 211                         tbptr->predecessorcount++;
 212
 213                         if (has_fallthrough) {
 214                                 ntbptr = bptr->next;
 215                                 ntbptr->predecessorcount++;
 216                         }
 217                         break;
 218
 219                 case CF_JSR:
 220                         bptr->successorcount++;
 221
 222                         tbptr = iptr->sx.s23.s3.jsrtarget.block;
 223                         tbptr->predecessorcount++;
 224                         break;
 225
 226                 case CF_GOTO:
 227                 case CF_RET:
 228                         bptr->successorcount++;
 229
 230                         tbptr = iptr->dst.block;
 231                         tbptr->predecessorcount++;
 232                         break;
 233
 234                 case CF_TABLE:
 235                         table = iptr->dst.table;
 236
 237                         bptr->successorcount++;
 238
 239                         tbptr = table->block;
 240                         tbptr->predecessorcount++;
 241                         table++;
 242
 243                         i = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
 244
 245                         while (--i >= 0) {
 246                                 bptr->successorcount++;
 247
 248                                 tbptr = table->block;
 249                                 tbptr->predecessorcount++;
 250                                 table++;
 251                         }
 252                         break;
 253
 254                 case CF_LOOKUP:
 255                         lookup = iptr->dst.lookup;
 256
 257                         bptr->successorcount++;
 258
 259                         tbptr = iptr->sx.s23.s3.lookupdefault.block;
 260                         tbptr->predecessorcount++;
 261
 262                         i = iptr->sx.s23.s2.lookupcount;
 263
 264                         while (--i >= 0) {
 265                                 bptr->successorcount++;
 266
 267                                 tbptr = lookup->target.block;
 268                                 tbptr->predecessorcount++;
 269                                 lookup++;
 270                         }
 271                         break;
 272
 273                 default:
 274                         if (has_fallthrough) {
 275                                 bptr->successorcount++;
 276
 277                                 tbptr = bptr->next;
 278
 279                                 /* An exception handler has no predecessors. */
 280
 281                                 if (tbptr->type != BBTYPE_EXH)
 282                                         tbptr->predecessorcount++;
 283                         }
 284                         break;
 285                 }
 286         }
 287
 288         /* Second iteration to allocate the arrays and insert the basic
 289            block pointers. */
 290
 291         bptr = jd->basicblocks;
 292
 293         for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
 294                 if ((bptr->icount == 0) || (bptr->flags == BBUNDEF))
 295                         continue;
 296
 297                 iptr = bptr->iinstr + bptr->icount - 1;
 298
 299                 /* skip NOPs at the end of the block */
 300
 301                 while (iptr->opc == ICMD_NOP) {
 302                         if (iptr == bptr->iinstr)
 303                                 break;
 304                         iptr--;
 305                 }
 306
 307                 if (iptr->opc == ICMD_GOTO) {
 308                         tbptr = iptr->dst.block;
 309
 310                         cfg_allocate_successors(bptr);
 311
 312                         cfg_insert_successors(bptr, tbptr);
 313
 314                         cfg_allocate_predecessors(tbptr);
 315
 316                         cfg_insert_predecessors(tbptr, bptr);
 317
 318                         if (iptr == bptr->iinstr) {
 319                                 continue;
 320                         }
 321
 322                         iptr--;
 323
 324                         while (iptr->opc == ICMD_NOP) {
 325                                 if (iptr == bptr->iinstr) {
 326                                         break;
 327                                 }
 328                                 iptr--;
 329                         }
 330
 331                         has_fallthrough = false;
 332
 333                 } else {
 334                         has_fallthrough = true;
 335                 }
 336
 337                 switch (icmd_table[iptr->opc].controlflow) {
 338
 339                 case CF_END:
 340                         break;
 341
 342                 case CF_IF:
 343
 344                         tbptr  = iptr->dst.block;
 345                         ntbptr = bptr->next;
 346
 347                         cfg_allocate_successors(bptr);
 348
 349                         cfg_insert_successors(bptr, tbptr);
 350                         if (has_fallthrough) {
 351                                 cfg_insert_successors(bptr, ntbptr);
 352                         }
 353
 354                         cfg_allocate_predecessors(tbptr);
 355                         if (has_fallthrough) {
 356                                 cfg_allocate_predecessors(ntbptr);
 357                         }
 358
 359                         cfg_insert_predecessors(tbptr, bptr);
 360                         if (has_fallthrough) {
 361                                 cfg_insert_predecessors(ntbptr, bptr);
 362                         }
 363                         break;
 364
 365                 case CF_JSR:
 366                         tbptr = iptr->sx.s23.s3.jsrtarget.block;
 367                         goto goto_tail;
 368
 369                 case CF_GOTO:
 370                 case CF_RET:
 371
 372                         tbptr = iptr->dst.block;
 373 goto_tail:
 374                         cfg_allocate_successors(bptr);
 375
 376                         cfg_insert_successors(bptr, tbptr);
 377
 378                         cfg_allocate_predecessors(tbptr);
 379
 380                         cfg_insert_predecessors(tbptr, bptr);
 381                         break;
 382
 383                 case CF_TABLE:
 384                         table = iptr->dst.table;
 385
 386                         tbptr = table->block;
 387                         table++;
 388
 389                         cfg_allocate_successors(bptr);
 390
 391                         cfg_insert_successors(bptr, tbptr);
 392
 393                         cfg_allocate_predecessors(tbptr);
 394
 395                         cfg_insert_predecessors(tbptr, bptr);
 396
 397                         i = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
 398
 399                         while (--i >= 0) {
 400                                 tbptr = table->block;
 401                                 table++;
 402
 403                                 cfg_insert_successors(bptr, tbptr);
 404
 405                                 cfg_allocate_predecessors(tbptr);
 406                                 cfg_insert_predecessors(tbptr, bptr);
 407                         }
 408                         break;
 409
 410                 case CF_LOOKUP:
 411                         lookup = iptr->dst.lookup;
 412
 413                         tbptr = iptr->sx.s23.s3.lookupdefault.block;
 414
 415                         cfg_allocate_successors(bptr);
 416
 417                         cfg_insert_successors(bptr, tbptr);
 418
 419                         cfg_allocate_predecessors(tbptr);
 420
 421                         cfg_insert_predecessors(tbptr, bptr);
 422
 423                         i = iptr->sx.s23.s2.lookupcount;
 424
 425                         while (--i >= 0) {
 426                                 tbptr = lookup->target.block;
 427                                 lookup++;
 428
 429                                 cfg_insert_successors(bptr, tbptr);
 430
 431                                 cfg_allocate_predecessors(tbptr);
 432                                 cfg_insert_predecessors(tbptr, bptr);
 433                         }
 434                         break;
 435
 436                 default:
 437                         if (has_fallthrough) {
 438                                 tbptr = bptr->next;
 439
 440                                 cfg_allocate_successors(bptr);
 441
 442                                 bptr->successors[0] = tbptr;
 443                                 bptr->successorcount++;
 444
 445                                 /* An exception handler has no predecessors. */
 446
 447                                 if (tbptr->type != BBTYPE_EXH) {
 448                                         cfg_allocate_predecessors(tbptr);
 449
 450                                         tbptr->predecessors[tbptr->predecessorcount] = bptr;
 451                                         tbptr->predecessorcount++;
 452                                 }
 453                         }
 454                         break;
 455                 }
 456         }
 457
 458         /* everything's ok */
 459
 460         return true;
 461 }
 462
 463 /* cfg_add_root ****************************************************************
 464
 465    Adds an empty root basicblock.
 466    The numbers of all other basicblocks are set off by one.
 467    Needed for some analyses that require the root basicblock to have no
 468    predecessors and to perform special initializations.
 469
 470 *******************************************************************************/
 471
 472 void cfg_add_root(jitdata *jd) {
 473         basicblock *root, *zero, *it;
 474
 475         zero = jd->basicblocks;
 476
 477         root = DNEW(basicblock);
 478         MZERO(root, basicblock, 1);
 479
 480         root->successorcount = 1;
 481         root->successors = DMNEW(basicblock *, 1);
 482         root->successors[0] = zero;
 483         root->next = zero;
 484         root->nr = 0;
 485         root->type = BBTYPE_STD;
 486         root->method = jd->m;
 487
 488         if (zero->predecessorcount == 0) {
 489                 zero->predecessors = DNEW(basicblock *);
 490         } else {
 491                 zero->predecessors = DMREALLOC(zero->predecessors, basicblock *, zero->predecessorcount, zero->predecessorcount + 1);
 492         }
 493         zero->predecessors[zero->predecessorcount] = root;
 494         zero->predecessorcount += 1;
 495
 496         jd->basicblocks = root;
 497         jd->basicblockcount += 1;
 498
 499         for (it = zero; it; it = it->next) {
 500                 it->nr += 1;
 501         }
 502 }
 503
 504 void cfg_remove_root(jitdata *jd) {
 505         basicblock *root, *zero, *it;
 506
 507         root = jd->basicblocks;
 508         zero = root->next;
 509
 510         zero->predecessorcount -= 1;
 511
 512         jd->basicblocks = zero;
 513
 514         for (it = zero; it; it = it->next) {
 515                 it->nr -= 1;
 516         }
 517 }
 518
 519 #if defined(ENABLE_SSA)
 520
 521 static void cfg_eliminate_edges_to_unreachable(jitdata *jd);
 522
 523 /* cfg_add_exceptional_edges ***************************************************
 524
 525    Edges from basicblocks to their exception handlers and from exception
 526    handlers to the blocks they handle exceptions for are added. Further
 527    the number of potentially throwing instructions in the basicblocks are
 528    counted.
 529
 530    We don't consider nor do we determine the types of exceptions thrown. Edges
 531    are added from every block to every potential handler.
 532
 533 *******************************************************************************/
 534
 535 void cfg_add_exceptional_edges(jitdata *jd) {
 536         basicblock *bptr;
 537         instruction *iptr;
 538         exception_entry *ee;
 539         bool unreachable_exh = false;
 540
 541         /* Count the number of exceptional exits for every block.
 542          * Every PEI is an exceptional out.
 543          */
 544
 545         FOR_EACH_BASICBLOCK(jd, bptr) {
 546
 547                 /* Prepare for reachability calculation. */
 548                 bptr->vp = NULL;
 549
 550                 if (bptr->flags == BBUNDEF) {
 551                         continue;
 552                 }
 553
 554                 FOR_EACH_INSTRUCTION(bptr, iptr) {
 555                         if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI) {
 556                                 bptr->exouts += 1;
 557                         }
 558                 }
 559         }
 560
 561         /* Count the number of exception handlers for every block. */
 562
 563         for (ee = jd->exceptiontable; ee; ee = ee->down) {
 564                 for (bptr = ee->start; bptr != ee->end; bptr = bptr->next) {
 565                         /* Linking a block with a handler, even if there are no exceptional exits
 566                            breaks stuff in other passes. */
 567                         if (bptr->exouts > 0) {
 568                                 bptr->exhandlercount += 1;
 569                                 ee->handler->expredecessorcount += 1;
 570                         }
 571                 }
 572         }
 573
 574         /* Allocate and fill exception handler arrays. */
 575
 576         for (ee = jd->exceptiontable; ee; ee = ee->down) {
 577
 578                 if (ee->handler->expredecessorcount == 0) {
 579                         /* An exception handler that is unreachable.
 580                            This is inconsistent with the semantics of the CFG,
 581                            we need to recalculate reachability. */
 582                         unreachable_exh = true;
 583                 }
 584
 585                 for (bptr = ee->start; bptr != ee->end; bptr = bptr->next) {
 586                         if (bptr->exouts > 0) {
 587
 588                                 if (bptr->exhandlers == NULL) {
 589                                         bptr->exhandlers = DMNEW(basicblock *, bptr->exhandlercount);
 590                                         /* Move pointer past the end of the array,
 591                                          * It will be filled in the reverse order.
 592                                          */
 593                                         bptr->exhandlers += bptr->exhandlercount;
 594                                 }
 595
 596                                 bptr->exhandlers -= 1;
 597                                 *(bptr->exhandlers) = ee->handler;
 598
 599                                 if (ee->handler->expredecessors == NULL) {
 600                                         ee->handler->expredecessors = DMNEW(basicblock *, ee->handler->expredecessorcount);
 601                                         ee->handler->expredecessors += ee->handler->expredecessorcount;
 602                                 }
 603
 604                                 ee->handler->expredecessors -= 1;
 605                                 *(ee->handler->expredecessors) = bptr;
 606                         }
 607                 }
 608         }
 609
 610         if (unreachable_exh) {
 611
 612                 /* This is rare in ``normal'' compiler generated code.
 613
 614                    The dead block [EXH] is a predecessor of [BB1],
 615                    but the edge [EXH] -> [BB1] will never be traversed.
 616
 617                    [BB1] --[next]--> [BB2, no peis] ==[exhandler]==> [EXH] --[next]--+
 618              ^                                                               |
 619                      +---------------------------------------------------------------+
 620                 */
 621
 622                 /*
 623                 fprintf(stderr, "Found unreachable exh, adjusting %s %s",
 624                         jd->m->klazz->name->text, jd->m->name->text);
 625                 fprintf(stderr, "<before>\n");
 626                 show_method(jd, 3);
 627                 fprintf(stderr, "</before>\n");
 628                 */
 629
 630                 cfg_eliminate_edges_to_unreachable(jd);
 631
 632                 /*
 633                 fprintf(stderr, "<after>\n");
 634                 show_method(jd, 3);
 635                 fprintf(stderr, "</after>\n");
 636                 */
 637         }
 638 }
 639
 640 static void cfg_calculate_reachability(basicblock *bptr) {
 641         basicblock **itsucc;
 642
 643         /* Block not marked. */
 644         assert(bptr->vp == NULL);
 645
 646         bptr->vp = bptr; /* Mark block */
 647
 648         FOR_EACH_SUCCESSOR(bptr, itsucc) {
 649                 if ((*itsucc)->vp == NULL) {
 650                         cfg_calculate_reachability(*itsucc);
 651                 }
 652         }
 653
 654         if (bptr->exouts > 0) {
 655                 FOR_EACH_EXHANDLER(bptr, itsucc) {
 656                         if ((*itsucc)->vp == NULL) {
 657                                 cfg_calculate_reachability(*itsucc);
 658                         }
 659                 }
 660         }
 661 }
 662
 663 static void cfg_remove_predecessors(basicblock *bptr, basicblock *pbptr) {
 664         s4 i;
 665
 666         for (i = 0; i < bptr->predecessorcount; ++i) {
 667                 /* Search item. */
 668                 if (bptr->predecessors[i] == pbptr) {
 669                         if (i != (bptr->predecessorcount - 1)) {
 670                                 /* If not last element, replace element with last element. */
 671                                 bptr->predecessors[i] = bptr->predecessors[bptr->predecessorcount - 1];
 672                         }
 673
 674                         /* Decrease element count. */
 675                         bptr->predecessorcount -= 1;
 676
 677                         return;
 678                 }
 679         }
 680 }
 681
 682 static void cfg_eliminate_edges_to_unreachable(jitdata *jd) {
 683         basicblock *it;
 684         basicblock **itsucc;
 685
 686         cfg_calculate_reachability(jd->basicblocks);
 687
 688         FOR_EACH_BASICBLOCK(jd, it) {
 689                 if (it->vp == NULL) {
 690
 691                         /* Mark as unreachable. */
 692
 693                         it->flags = BBUNDEF;
 694
 695                         /* As this block got unreachable, it is no more a predecessor
 696                            of its successors. */
 697
 698                         FOR_EACH_SUCCESSOR(it, itsucc) {
 699                                 cfg_remove_predecessors(*itsucc, it);
 700                         }
 701
 702                         /* Eliminiate all CFG edges of this block. */
 703
 704                         it->predecessorcount = 0;
 705                         it->successorcount = 0;
 706                         it->expredecessorcount = 0;
 707                 }
 708         }
 709 }
 710
 711
 712 #endif
 713
 714 /*
 715  * These are local overrides for various environment variables in Emacs.
 716  * Please do not remove this and leave it at the end of the file, where
 717  * Emacs will automagically detect them.
 718  * ---------------------------------------------------------------------
 719  * Local variables:
 720  * mode: c
 721  * indent-tabs-mode: t
 722  * c-basic-offset: 4
 723  * tab-width: 4
 724  * End:
 725  * vim:noexpandtab:sw=4:ts=4:
 726  */