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.h"
  34
  35 #include "vm/global.h"
  36
  37 #include "vm/jit/jit.h"
  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                 if ((bptr->icount == 0) || (bptr->flags == BBUNDEF))
 145                         continue;
 146
 147                 iptr = bptr->iinstr + bptr->icount - 1;
 148
 149                 /* skip NOPs at the end of the block */
 150
 151                 while (iptr->opc == ICMD_NOP) {
 152                         if (iptr == bptr->iinstr)
 153                                 break;
 154                         iptr--;
 155                 }
 156
 157                 if (iptr->opc == ICMD_GOTO) {
 158
 159                         /*
 160                          This is needed for the following special case caused by
 161                          stack_reach_next_block:
 162                          I.e. there might be instructions causing control flow before
 163                          a GOTO:
 164
 165                          ....
 166                          129: 192:  IFEQ            Ti102 0 (0x00000000) --> L052
 167                          131: 193:  NOP
 168                            0:   0:  GOTO            --> L060
 169                         */
 170
 171                         bptr->successorcount++;
 172
 173                         tbptr = iptr->dst.block;
 174                         tbptr->predecessorcount++;
 175
 176                         if (iptr == bptr->iinstr) {
 177                                 continue;
 178                         }
 179
 180                         iptr--;
 181
 182                         while (iptr->opc == ICMD_NOP) {
 183                                 if (iptr == bptr->iinstr) {
 184                                         break;
 185                                 }
 186                                 iptr--;
 187                         }
 188
 189                         has_fallthrough = false;
 190                 } else {
 191                         has_fallthrough = true;
 192                 }
 193
 194                 switch (icmd_table[iptr->opc].controlflow) {
 195
 196                 case CF_END:
 197                         break;
 198
 199                 case CF_IF:
 200
 201                         bptr->successorcount += 2;
 202
 203                         tbptr  = iptr->dst.block;
 204                         tbptr->predecessorcount++;
 205
 206                         if (has_fallthrough) {
 207                                 ntbptr = bptr->next;
 208                                 ntbptr->predecessorcount++;
 209                         }
 210                         break;
 211
 212                 case CF_JSR:
 213                         bptr->successorcount++;
 214
 215                         tbptr = iptr->sx.s23.s3.jsrtarget.block;
 216                         tbptr->predecessorcount++;
 217                         break;
 218
 219                 case CF_GOTO:
 220                 case CF_RET:
 221                         bptr->successorcount++;
 222
 223                         tbptr = iptr->dst.block;
 224                         tbptr->predecessorcount++;
 225                         break;
 226
 227                 case CF_TABLE:
 228                         table = iptr->dst.table;
 229
 230                         bptr->successorcount++;
 231
 232                         tbptr = table->block;
 233                         tbptr->predecessorcount++;
 234                         table++;
 235
 236                         i = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
 237
 238                         while (--i >= 0) {
 239                                 bptr->successorcount++;
 240
 241                                 tbptr = table->block;
 242                                 tbptr->predecessorcount++;
 243                                 table++;
 244                         }
 245                         break;
 246
 247                 case CF_LOOKUP:
 248                         lookup = iptr->dst.lookup;
 249
 250                         bptr->successorcount++;
 251
 252                         tbptr = iptr->sx.s23.s3.lookupdefault.block;
 253                         tbptr->predecessorcount++;
 254
 255                         i = iptr->sx.s23.s2.lookupcount;
 256
 257                         while (--i >= 0) {
 258                                 bptr->successorcount++;
 259
 260                                 tbptr = lookup->target.block;
 261                                 tbptr->predecessorcount++;
 262                                 lookup++;
 263                         }
 264                         break;
 265
 266                 default:
 267                         if (has_fallthrough) {
 268                                 bptr->successorcount++;
 269
 270                                 tbptr = bptr->next;
 271
 272                                 /* An exception handler has no predecessors. */
 273
 274                                 if (tbptr->type != BBTYPE_EXH)
 275                                         tbptr->predecessorcount++;
 276                         }
 277                         break;
 278                 }
 279         }
 280
 281         /* Second iteration to allocate the arrays and insert the basic
 282            block pointers. */
 283
 284         bptr = jd->basicblocks;
 285
 286         for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
 287                 if ((bptr->icount == 0) || (bptr->flags == BBUNDEF))
 288                         continue;
 289
 290                 iptr = bptr->iinstr + bptr->icount - 1;
 291
 292                 /* skip NOPs at the end of the block */
 293
 294                 while (iptr->opc == ICMD_NOP) {
 295                         if (iptr == bptr->iinstr)
 296                                 break;
 297                         iptr--;
 298                 }
 299
 300                 if (iptr->opc == ICMD_GOTO) {
 301                         tbptr = iptr->dst.block;
 302
 303                         cfg_allocate_successors(bptr);
 304
 305                         cfg_insert_successors(bptr, tbptr);
 306
 307                         cfg_allocate_predecessors(tbptr);
 308
 309                         cfg_insert_predecessors(tbptr, bptr);
 310
 311                         if (iptr == bptr->iinstr) {
 312                                 continue;
 313                         }
 314
 315                         iptr--;
 316
 317                         while (iptr->opc == ICMD_NOP) {
 318                                 if (iptr == bptr->iinstr) {
 319                                         break;
 320                                 }
 321                                 iptr--;
 322                         }
 323
 324                         has_fallthrough = false;
 325
 326                 } else {
 327                         has_fallthrough = true;
 328                 }
 329
 330                 switch (icmd_table[iptr->opc].controlflow) {
 331
 332                 case CF_END:
 333                         break;
 334
 335                 case CF_IF:
 336
 337                         tbptr  = iptr->dst.block;
 338                         ntbptr = bptr->next;
 339
 340                         cfg_allocate_successors(bptr);
 341
 342                         cfg_insert_successors(bptr, tbptr);
 343                         if (has_fallthrough) {
 344                                 cfg_insert_successors(bptr, ntbptr);
 345                         }
 346
 347                         cfg_allocate_predecessors(tbptr);
 348                         if (has_fallthrough) {
 349                                 cfg_allocate_predecessors(ntbptr);
 350                         }
 351
 352                         cfg_insert_predecessors(tbptr, bptr);
 353                         if (has_fallthrough) {
 354                                 cfg_insert_predecessors(ntbptr, bptr);
 355                         }
 356                         break;
 357
 358                 case CF_JSR:
 359                         tbptr = iptr->sx.s23.s3.jsrtarget.block;
 360                         goto goto_tail;
 361
 362                 case CF_GOTO:
 363                 case CF_RET:
 364
 365                         tbptr = iptr->dst.block;
 366 goto_tail:
 367                         cfg_allocate_successors(bptr);
 368
 369                         cfg_insert_successors(bptr, tbptr);
 370
 371                         cfg_allocate_predecessors(tbptr);
 372
 373                         cfg_insert_predecessors(tbptr, bptr);
 374                         break;
 375
 376                 case CF_TABLE:
 377                         table = iptr->dst.table;
 378
 379                         tbptr = table->block;
 380                         table++;
 381
 382                         cfg_allocate_successors(bptr);
 383
 384                         cfg_insert_successors(bptr, tbptr);
 385
 386                         cfg_allocate_predecessors(tbptr);
 387
 388                         cfg_insert_predecessors(tbptr, bptr);
 389
 390                         i = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
 391
 392                         while (--i >= 0) {
 393                                 tbptr = table->block;
 394                                 table++;
 395
 396                                 cfg_insert_successors(bptr, tbptr);
 397
 398                                 cfg_allocate_predecessors(tbptr);
 399                                 cfg_insert_predecessors(tbptr, bptr);
 400                         }
 401                         break;
 402
 403                 case CF_LOOKUP:
 404                         lookup = iptr->dst.lookup;
 405
 406                         tbptr = iptr->sx.s23.s3.lookupdefault.block;
 407
 408                         cfg_allocate_successors(bptr);
 409
 410                         cfg_insert_successors(bptr, tbptr);
 411
 412                         cfg_allocate_predecessors(tbptr);
 413
 414                         cfg_insert_predecessors(tbptr, bptr);
 415
 416                         i = iptr->sx.s23.s2.lookupcount;
 417
 418                         while (--i >= 0) {
 419                                 tbptr = lookup->target.block;
 420                                 lookup++;
 421
 422                                 cfg_insert_successors(bptr, tbptr);
 423
 424                                 cfg_allocate_predecessors(tbptr);
 425                                 cfg_insert_predecessors(tbptr, bptr);
 426                         }
 427                         break;
 428
 429                 default:
 430                         if (has_fallthrough) {
 431                                 tbptr = bptr->next;
 432
 433                                 cfg_allocate_successors(bptr);
 434
 435                                 bptr->successors[0] = tbptr;
 436                                 bptr->successorcount++;
 437
 438                                 /* An exception handler has no predecessors. */
 439
 440                                 if (tbptr->type != BBTYPE_EXH) {
 441                                         cfg_allocate_predecessors(tbptr);
 442
 443                                         tbptr->predecessors[tbptr->predecessorcount] = bptr;
 444                                         tbptr->predecessorcount++;
 445                                 }
 446                         }
 447                         break;
 448                 }
 449         }
 450
 451         /* everything's ok */
 452
 453         return true;
 454 }
 455
 456 /* cfg_add_root ****************************************************************
 457
 458    Adds an empty root basicblock.
 459    The numbers of all other basicblocks are set off by one.
 460    Needed for some analyses that require the root basicblock to have no
 461    predecessors and to perform special initializations.
 462
 463 *******************************************************************************/
 464
 465 void cfg_add_root(jitdata *jd) {
 466         basicblock *root, *zero, *it;
 467
 468         zero = jd->basicblocks;
 469
 470         root = DNEW(basicblock);
 471         MZERO(root, basicblock, 1);
 472
 473         root->successorcount = 1;
 474         root->successors = DMNEW(basicblock *, 1);
 475         root->successors[0] = zero;
 476         root->next = zero;
 477         root->nr = 0;
 478         root->type = BBTYPE_STD;
 479
 480         if (zero->predecessorcount == 0) {
 481                 zero->predecessors = DNEW(basicblock *);
 482         } else {
 483                 zero->predecessors = DMREALLOC(zero->predecessors, basicblock *, zero->predecessorcount, zero->predecessorcount + 1);
 484         }
 485         zero->predecessors[zero->predecessorcount] = root;
 486         zero->predecessorcount += 1;
 487
 488         jd->basicblocks = root;
 489         jd->basicblockcount += 1;
 490
 491         for (it = zero; it; it = it->next) {
 492                 it->nr += 1;
 493         }
 494 }
 495
 496 #if defined(ENABLE_SSA)
 497
 498 /* cfg_add_exceptional_edges ***************************************************
 499
 500    Edges from basicblocks to their exception handlers and from exception
 501    handlers to the blocks they handle exceptions for are added. Further
 502    the number of potentially throwing instructions in the basicblocks are
 503    counted.
 504
 505    We don't consider nor do we determine the types of exceptions thrown. Edges
 506    are added from every block to every potential handler.
 507
 508 *******************************************************************************/
 509
 510 void cfg_add_exceptional_edges(jitdata *jd) {
 511         basicblock *bptr;
 512         instruction *iptr;
 513         exception_entry *ee;
 514
 515         /* Count the number of exceptional exits for every block.
 516          * Every PEI is an exceptional out.
 517          */
 518
 519         FOR_EACH_BASICBLOCK(jd, bptr) {
 520
 521                 if (bptr->flags == BBUNDEF) {
 522                         continue;
 523                 }
 524
 525                 FOR_EACH_INSTRUCTION(bptr, iptr) {
 526                         if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI) {
 527                                 bptr->exouts += 1;
 528                         }
 529                 }
 530         }
 531
 532         /* Count the number of exception handlers for every block. */
 533
 534         for (ee = jd->exceptiontable; ee; ee = ee->down) {
 535                 for (bptr = ee->start; bptr != ee->end; bptr = bptr->next) {
 536                         /* Linking a block with a handler, even if there are no exceptional exits
 537                            breaks stuff in other passes. */
 538                         if (bptr->exouts > 0) {
 539                                 bptr->exhandlercount += 1;
 540                                 ee->handler->expredecessorcount += 1;
 541                         }
 542                 }
 543         }
 544
 545         /* Allocate and fill exception handler arrays. */
 546
 547         for (ee = jd->exceptiontable; ee; ee = ee->down) {
 548                 for (bptr = ee->start; bptr != ee->end; bptr = bptr->next) {
 549                         if (bptr->exouts > 0) {
 550
 551                                 if (bptr->exhandlers == NULL) {
 552                                         bptr->exhandlers = DMNEW(basicblock *, bptr->exhandlercount);
 553                                         /* Move pointer past the end of the array,
 554                                          * It will be filled in the reverse order.
 555                                          */
 556                                         bptr->exhandlers += bptr->exhandlercount;
 557                                 }
 558
 559                                 bptr->exhandlers -= 1;
 560                                 *(bptr->exhandlers) = ee->handler;
 561
 562                                 if (ee->handler->expredecessors == NULL) {
 563                                         ee->handler->expredecessors = DMNEW(basicblock *, ee->handler->expredecessorcount);
 564                                         ee->handler->expredecessors += ee->handler->expredecessorcount;
 565                                 }
 566
 567                                 ee->handler->expredecessors -= 1;
 568                                 *(ee->handler->expredecessors) = bptr;
 569                         }
 570                 }
 571         }
 572 }
 573
 574 #endif
 575
 576 /*
 577  * These are local overrides for various environment variables in Emacs.
 578  * Please do not remove this and leave it at the end of the file, where
 579  * Emacs will automagically detect them.
 580  * ---------------------------------------------------------------------
 581  * Local variables:
 582  * mode: c
 583  * indent-tabs-mode: t
 584  * c-basic-offset: 4
 585  * tab-width: 4
 586  * End:
 587  * vim:noexpandtab:sw=4:ts=4:
 588  */