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
 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
 487         if (zero->predecessorcount == 0) {
 488                 zero->predecessors = DNEW(basicblock *);
 489         } else {
 490                 zero->predecessors = DMREALLOC(zero->predecessors, basicblock *, zero->predecessorcount, zero->predecessorcount + 1);
 491         }
 492         zero->predecessors[zero->predecessorcount] = root;
 493         zero->predecessorcount += 1;
 494
 495         jd->basicblocks = root;
 496         jd->basicblockcount += 1;
 497
 498         for (it = zero; it; it = it->next) {
 499                 it->nr += 1;
 500         }
 501 }
 502
 503 #if defined(ENABLE_SSA)
 504
 505 /* cfg_add_exceptional_edges ***************************************************
 506
 507    Edges from basicblocks to their exception handlers and from exception
 508    handlers to the blocks they handle exceptions for are added. Further
 509    the number of potentially throwing instructions in the basicblocks are
 510    counted.
 511
 512    We don't consider nor do we determine the types of exceptions thrown. Edges
 513    are added from every block to every potential handler.
 514
 515 *******************************************************************************/
 516
 517 void cfg_add_exceptional_edges(jitdata *jd) {
 518         basicblock *bptr;
 519         instruction *iptr;
 520         exception_entry *ee;
 521
 522         /* Count the number of exceptional exits for every block.
 523          * Every PEI is an exceptional out.
 524          */
 525
 526         FOR_EACH_BASICBLOCK(jd, bptr) {
 527
 528                 if (bptr->flags == BBUNDEF) {
 529                         continue;
 530                 }
 531
 532                 FOR_EACH_INSTRUCTION(bptr, iptr) {
 533                         if (icmd_table[iptr->opc].flags & ICMDTABLE_PEI) {
 534                                 bptr->exouts += 1;
 535                         }
 536                 }
 537         }
 538
 539         /* Count the number of exception handlers for every block. */
 540
 541         for (ee = jd->exceptiontable; ee; ee = ee->down) {
 542                 for (bptr = ee->start; bptr != ee->end; bptr = bptr->next) {
 543                         /* Linking a block with a handler, even if there are no exceptional exits
 544                            breaks stuff in other passes. */
 545                         if (bptr->exouts > 0) {
 546                                 bptr->exhandlercount += 1;
 547                                 ee->handler->expredecessorcount += 1;
 548                         }
 549                 }
 550         }
 551
 552         /* Allocate and fill exception handler arrays. */
 553
 554         for (ee = jd->exceptiontable; ee; ee = ee->down) {
 555                 for (bptr = ee->start; bptr != ee->end; bptr = bptr->next) {
 556                         if (bptr->exouts > 0) {
 557
 558                                 if (bptr->exhandlers == NULL) {
 559                                         bptr->exhandlers = DMNEW(basicblock *, bptr->exhandlercount);
 560                                         /* Move pointer past the end of the array,
 561                                          * It will be filled in the reverse order.
 562                                          */
 563                                         bptr->exhandlers += bptr->exhandlercount;
 564                                 }
 565
 566                                 bptr->exhandlers -= 1;
 567                                 *(bptr->exhandlers) = ee->handler;
 568
 569                                 if (ee->handler->expredecessors == NULL) {
 570                                         ee->handler->expredecessors = DMNEW(basicblock *, ee->handler->expredecessorcount);
 571                                         ee->handler->expredecessors += ee->handler->expredecessorcount;
 572                                 }
 573
 574                                 ee->handler->expredecessors -= 1;
 575                                 *(ee->handler->expredecessors) = bptr;
 576                         }
 577                 }
 578         }
 579 }
 580
 581 #endif
 582
 583 /*
 584  * These are local overrides for various environment variables in Emacs.
 585  * Please do not remove this and leave it at the end of the file, where
 586  * Emacs will automagically detect them.
 587  * ---------------------------------------------------------------------
 588  * Local variables:
 589  * mode: c
 590  * indent-tabs-mode: t
 591  * c-basic-offset: 4
 592  * tab-width: 4
 593  * End:
 594  * vim:noexpandtab:sw=4:ts=4:
 595  */