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
 138         /* process all basic blocks to find the predecessor/successor counts */
 139
 140         bptr = jd->basicblocks;
 141
 142         for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
 143                 if ((bptr->icount == 0) || (bptr->flags == BBUNDEF))
 144                         continue;
 145
 146                 iptr = bptr->iinstr + bptr->icount - 1;
 147
 148                 /* skip NOPs at the end of the block */
 149
 150                 while (iptr->opc == ICMD_NOP) {
 151                         if (iptr == bptr->iinstr)
 152                                 break;
 153                         iptr--;
 154                 }
 155
 156                 switch (icmd_table[iptr->opc].controlflow) {
 157
 158                 case CF_END:
 159                         break;
 160
 161                 case CF_IF:
 162
 163                         bptr->successorcount += 2;
 164
 165                         tbptr  = iptr->dst.block;
 166                         ntbptr = bptr->next;
 167
 168                         tbptr->predecessorcount++;
 169                         ntbptr->predecessorcount++;
 170                         break;
 171
 172                 case CF_JSR:
 173                         bptr->successorcount++;
 174
 175                         tbptr = iptr->sx.s23.s3.jsrtarget.block;
 176                         tbptr->predecessorcount++;
 177                         break;
 178
 179                 case CF_GOTO:
 180                 case CF_RET:
 181                         bptr->successorcount++;
 182
 183                         tbptr = iptr->dst.block;
 184                         tbptr->predecessorcount++;
 185                         break;
 186
 187                 case CF_TABLE:
 188                         table = iptr->dst.table;
 189
 190                         bptr->successorcount++;
 191
 192                         tbptr = table->block;
 193                         tbptr->predecessorcount++;
 194                         table++;
 195
 196                         i = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
 197
 198                         while (--i >= 0) {
 199                                 bptr->successorcount++;
 200
 201                                 tbptr = table->block;
 202                                 tbptr->predecessorcount++;
 203                                 table++;
 204                         }
 205                         break;
 206
 207                 case CF_LOOKUP:
 208                         lookup = iptr->dst.lookup;
 209
 210                         bptr->successorcount++;
 211
 212                         tbptr = iptr->sx.s23.s3.lookupdefault.block;
 213                         tbptr->predecessorcount++;
 214
 215                         i = iptr->sx.s23.s2.lookupcount;
 216
 217                         while (--i >= 0) {
 218                                 bptr->successorcount++;
 219
 220                                 tbptr = lookup->target.block;
 221                                 tbptr->predecessorcount++;
 222                                 lookup++;
 223                         }
 224                         break;
 225
 226                 default:
 227                         bptr->successorcount++;
 228
 229                         tbptr = bptr->next;
 230
 231                         /* An exception handler has no predecessors. */
 232
 233                         if (tbptr->type != BBTYPE_EXH)
 234                                 tbptr->predecessorcount++;
 235                         break;
 236                 }
 237         }
 238
 239         /* Second iteration to allocate the arrays and insert the basic
 240            block pointers. */
 241
 242         bptr = jd->basicblocks;
 243
 244         for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
 245                 if ((bptr->icount == 0) || (bptr->flags == BBUNDEF))
 246                         continue;
 247
 248                 iptr = bptr->iinstr + bptr->icount - 1;
 249
 250                 /* skip NOPs at the end of the block */
 251
 252                 while (iptr->opc == ICMD_NOP) {
 253                         if (iptr == bptr->iinstr)
 254                                 break;
 255                         iptr--;
 256                 }
 257
 258                 switch (icmd_table[iptr->opc].controlflow) {
 259
 260                 case CF_END:
 261                         break;
 262
 263                 case CF_IF:
 264
 265                         tbptr  = iptr->dst.block;
 266                         ntbptr = bptr->next;
 267
 268                         cfg_allocate_successors(bptr);
 269
 270                         cfg_insert_successors(bptr, tbptr);
 271                         cfg_insert_successors(bptr, ntbptr);
 272
 273                         cfg_allocate_predecessors(tbptr);
 274                         cfg_allocate_predecessors(ntbptr);
 275
 276                         cfg_insert_predecessors(tbptr, bptr);
 277                         cfg_insert_predecessors(ntbptr, bptr);
 278                         break;
 279
 280                 case CF_JSR:
 281                         tbptr = iptr->sx.s23.s3.jsrtarget.block;
 282                         goto goto_tail;
 283
 284                 case CF_GOTO:
 285                 case CF_RET:
 286
 287                         tbptr = iptr->dst.block;
 288 goto_tail:
 289                         cfg_allocate_successors(bptr);
 290
 291                         cfg_insert_successors(bptr, tbptr);
 292
 293                         cfg_allocate_predecessors(tbptr);
 294
 295                         cfg_insert_predecessors(tbptr, bptr);
 296                         break;
 297
 298                 case CF_TABLE:
 299                         table = iptr->dst.table;
 300
 301                         tbptr = table->block;
 302                         table++;
 303
 304                         cfg_allocate_successors(bptr);
 305
 306                         cfg_insert_successors(bptr, tbptr);
 307
 308                         cfg_allocate_predecessors(tbptr);
 309
 310                         cfg_insert_predecessors(tbptr, bptr);
 311
 312                         i = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
 313
 314                         while (--i >= 0) {
 315                                 tbptr = table->block;
 316                                 table++;
 317
 318                                 cfg_insert_successors(bptr, tbptr);
 319
 320                                 cfg_allocate_predecessors(tbptr);
 321                                 cfg_insert_predecessors(tbptr, bptr);
 322                         }
 323                         break;
 324
 325                 case CF_LOOKUP:
 326                         lookup = iptr->dst.lookup;
 327
 328                         tbptr = iptr->sx.s23.s3.lookupdefault.block;
 329
 330                         cfg_allocate_successors(bptr);
 331
 332                         cfg_insert_successors(bptr, tbptr);
 333
 334                         cfg_allocate_predecessors(tbptr);
 335
 336                         cfg_insert_predecessors(tbptr, bptr);
 337
 338                         i = iptr->sx.s23.s2.lookupcount;
 339
 340                         while (--i >= 0) {
 341                                 tbptr = lookup->target.block;
 342                                 lookup++;
 343
 344                                 cfg_insert_successors(bptr, tbptr);
 345
 346                                 cfg_allocate_predecessors(tbptr);
 347                                 cfg_insert_predecessors(tbptr, bptr);
 348                         }
 349                         break;
 350
 351                 default:
 352                         tbptr = bptr->next;
 353
 354                         cfg_allocate_successors(bptr);
 355
 356                         bptr->successors[0] = tbptr;
 357                         bptr->successorcount++;
 358
 359                         /* An exception handler has no predecessors. */
 360
 361                         if (tbptr->type != BBTYPE_EXH) {
 362                                 cfg_allocate_predecessors(tbptr);
 363
 364                                 tbptr->predecessors[tbptr->predecessorcount] = bptr;
 365                                 tbptr->predecessorcount++;
 366                         }
 367                         break;
 368                 }
 369         }
 370
 371         /* everything's ok */
 372
 373         return true;
 374 }
 375
 376 /* cfg_add_root ****************************************************************
 377
 378    Adds an empty root basicblock.
 379    The numbers of all other basicblocks are set off by one.
 380    Needed for some analyses that require the root basicblock to have no
 381    predecessors and to perform special initializations.
 382
 383 *******************************************************************************/
 384
 385 void cfg_add_root(jitdata *jd) {
 386         basicblock *root, *zero, *it;
 387
 388         zero = jd->basicblocks;
 389
 390         root = DNEW(basicblock);
 391         MZERO(root, basicblock, 1);
 392
 393         root->successorcount = 1;
 394         root->successors = DMNEW(basicblock *, 1);
 395         root->successors[0] = zero;
 396         root->next = zero;
 397         root->nr = 0;
 398         root->type = BBTYPE_STD;
 399
 400         if (zero->predecessorcount == 0) {
 401                 zero->predecessors = DNEW(basicblock *);
 402         } else {
 403                 zero->predecessors = DMREALLOC(zero->predecessors, basicblock *, zero->predecessorcount, zero->predecessorcount + 1);
 404         }
 405         zero->predecessors[zero->predecessorcount] = root;
 406         zero->predecessorcount += 1;
 407
 408         jd->basicblocks = root;
 409         jd->basicblockcount += 1;
 410
 411         for (it = zero; it; it = it->next) {
 412                 it->nr += 1;
 413         }
 414 }
 415
 416 /*
 417  * These are local overrides for various environment variables in Emacs.
 418  * Please do not remove this and leave it at the end of the file, where
 419  * Emacs will automagically detect them.
 420  * ---------------------------------------------------------------------
 421  * Local variables:
 422  * mode: c
 423  * indent-tabs-mode: t
 424  * c-basic-offset: 4
 425  * tab-width: 4
 426  * End:
 427  * vim:noexpandtab:sw=4:ts=4:
 428  */