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
 102 /* cfg_build *******************************************************************
 103
 104    Build a control-flow graph in finding all predecessors and
 105    successors for the basic blocks.
 106
 107 *******************************************************************************/
 108
 109 bool cfg_build(jitdata *jd)
 110 {
 111         basicblock      *bptr;
 112         basicblock      *tbptr;
 113         basicblock      *ntbptr;
 114         instruction     *iptr;
 115         branch_target_t *table;
 116         lookup_target_t *lookup;
 117         int              i;
 118
 119         /* process all basic blocks to find the predecessor/successor counts */
 120
 121         bptr = jd->basicblocks;
 122
 123         for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
 124                 if ((bptr->icount == 0) || (bptr->flags == BBUNDEF))
 125                         continue;
 126
 127                 iptr = bptr->iinstr + bptr->icount - 1;
 128
 129                 /* skip NOPs at the end of the block */
 130
 131                 while (iptr->opc == ICMD_NOP) {
 132                         if (iptr == bptr->iinstr)
 133                                 break;
 134                         iptr--;
 135                 }
 136
 137                 switch (iptr->opc) {
 138                 case ICMD_RETURN:
 139                 case ICMD_IRETURN:
 140                 case ICMD_LRETURN:
 141                 case ICMD_FRETURN:
 142                 case ICMD_DRETURN:
 143                 case ICMD_ARETURN:
 144                 case ICMD_ATHROW:
 145                         break;
 146
 147                 case ICMD_IFEQ:
 148                 case ICMD_IFNE:
 149                 case ICMD_IFLT:
 150                 case ICMD_IFGE:
 151                 case ICMD_IFGT:
 152                 case ICMD_IFLE:
 153
 154                 case ICMD_IFNULL:
 155                 case ICMD_IFNONNULL:
 156
 157                 case ICMD_IF_ICMPEQ:
 158                 case ICMD_IF_ICMPNE:
 159                 case ICMD_IF_ICMPLT:
 160                 case ICMD_IF_ICMPGE:
 161                 case ICMD_IF_ICMPGT:
 162                 case ICMD_IF_ICMPLE:
 163
 164                 case ICMD_IF_ACMPEQ:
 165                 case ICMD_IF_ACMPNE:
 166                         bptr->successorcount += 2;
 167
 168                         tbptr  = iptr->dst.block;
 169                         ntbptr = bptr->next;
 170
 171                         tbptr->predecessorcount++;
 172                         ntbptr->predecessorcount++;
 173                         break;
 174
 175                 case ICMD_JSR:
 176                         bptr->successorcount++;
 177
 178                         tbptr = iptr->sx.s23.s3.jsrtarget.block;
 179                         tbptr->predecessorcount++;
 180                         break;
 181
 182                 case ICMD_GOTO:
 183                 case ICMD_RET:
 184                         bptr->successorcount++;
 185
 186                         tbptr = iptr->dst.block;
 187                         tbptr->predecessorcount++;
 188                         break;
 189
 190                 case ICMD_TABLESWITCH:
 191                         table = iptr->dst.table;
 192
 193                         bptr->successorcount++;
 194
 195                         tbptr = table->block;
 196                         tbptr->predecessorcount++;
 197                         table++;
 198
 199                         i = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
 200
 201                         while (--i >= 0) {
 202                                 bptr->successorcount++;
 203
 204                                 tbptr = table->block;
 205                                 tbptr->predecessorcount++;
 206                                 table++;
 207                         }
 208                         break;
 209
 210                 case ICMD_LOOKUPSWITCH:
 211                         lookup = iptr->dst.lookup;
 212
 213                         bptr->successorcount++;
 214
 215                         tbptr = iptr->sx.s23.s3.lookupdefault.block;
 216                         tbptr->predecessorcount++;
 217
 218                         i = iptr->sx.s23.s2.lookupcount;
 219
 220                         while (--i >= 0) {
 221                                 bptr->successorcount++;
 222
 223                                 tbptr = lookup->target.block;
 224                                 tbptr->predecessorcount++;
 225                                 lookup++;
 226                         }
 227                         break;
 228
 229                 default:
 230                         bptr->successorcount++;
 231
 232                         tbptr = bptr->next;
 233
 234                         /* An exception handler has no predecessors. */
 235
 236                         if (tbptr->type != BBTYPE_EXH)
 237                                 tbptr->predecessorcount++;
 238                         break;
 239                 }
 240         }
 241
 242         /* Second iteration to allocate the arrays and insert the basic
 243            block pointers. */
 244
 245         bptr = jd->basicblocks;
 246
 247         for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
 248                 if ((bptr->icount == 0) || (bptr->flags == BBUNDEF))
 249                         continue;
 250
 251                 iptr = bptr->iinstr + bptr->icount - 1;
 252
 253                 /* skip NOPs at the end of the block */
 254
 255                 while (iptr->opc == ICMD_NOP) {
 256                         if (iptr == bptr->iinstr)
 257                                 break;
 258                         iptr--;
 259                 }
 260
 261                 switch (iptr->opc) {
 262                 case ICMD_RETURN:
 263                 case ICMD_IRETURN:
 264                 case ICMD_LRETURN:
 265                 case ICMD_FRETURN:
 266                 case ICMD_DRETURN:
 267                 case ICMD_ARETURN:
 268                 case ICMD_ATHROW:
 269                         break;
 270
 271                 case ICMD_IFEQ:
 272                 case ICMD_IFNE:
 273                 case ICMD_IFLT:
 274                 case ICMD_IFGE:
 275                 case ICMD_IFGT:
 276                 case ICMD_IFLE:
 277
 278                 case ICMD_IFNULL:
 279                 case ICMD_IFNONNULL:
 280
 281                 case ICMD_IF_ICMPEQ:
 282                 case ICMD_IF_ICMPNE:
 283                 case ICMD_IF_ICMPLT:
 284                 case ICMD_IF_ICMPGE:
 285                 case ICMD_IF_ICMPGT:
 286                 case ICMD_IF_ICMPLE:
 287
 288                 case ICMD_IF_ACMPEQ:
 289                 case ICMD_IF_ACMPNE:
 290                         tbptr  = iptr->dst.block;
 291                         ntbptr = bptr->next;
 292
 293                         cfg_allocate_successors(bptr);
 294
 295                         bptr->successors[0] = tbptr;
 296                         bptr->successors[1] = ntbptr;
 297                         bptr->successorcount += 2;
 298
 299                         cfg_allocate_predecessors(tbptr);
 300                         cfg_allocate_predecessors(ntbptr);
 301
 302                         tbptr->predecessors[tbptr->predecessorcount] = bptr;
 303                         tbptr->predecessorcount++;
 304
 305                         ntbptr->predecessors[ntbptr->predecessorcount] = bptr;
 306                         ntbptr->predecessorcount++;
 307                         break;
 308
 309                 case ICMD_JSR:
 310                         tbptr = iptr->sx.s23.s3.jsrtarget.block;
 311                         goto goto_tail;
 312
 313                 case ICMD_GOTO:
 314                 case ICMD_RET:
 315                         tbptr = iptr->dst.block;
 316 goto_tail:
 317                         cfg_allocate_successors(bptr);
 318
 319                         bptr->successors[0] = tbptr;
 320                         bptr->successorcount++;
 321
 322                         cfg_allocate_predecessors(tbptr);
 323
 324                         tbptr->predecessors[tbptr->predecessorcount] = bptr;
 325                         tbptr->predecessorcount++;
 326                         break;
 327
 328                 case ICMD_TABLESWITCH:
 329                         table = iptr->dst.table;
 330
 331                         tbptr = table->block;
 332                         table++;
 333
 334                         cfg_allocate_successors(bptr);
 335
 336                         bptr->successors[0] = tbptr;
 337                         bptr->successorcount++;
 338
 339                         cfg_allocate_predecessors(tbptr);
 340
 341                         tbptr->predecessors[tbptr->predecessorcount] = bptr;
 342                         tbptr->predecessorcount++;
 343
 344                         i = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
 345
 346                         while (--i >= 0) {
 347                                 tbptr = table->block;
 348                                 table++;
 349
 350                                 bptr->successors[bptr->successorcount] = tbptr;
 351                                 bptr->successorcount++;
 352
 353                                 cfg_allocate_predecessors(tbptr);
 354                                 cfg_insert_predecessors(tbptr, bptr);
 355                         }
 356                         break;
 357
 358                 case ICMD_LOOKUPSWITCH:
 359                         lookup = iptr->dst.lookup;
 360
 361                         tbptr = iptr->sx.s23.s3.lookupdefault.block;
 362
 363                         cfg_allocate_successors(bptr);
 364
 365                         bptr->successors[0] = tbptr;
 366                         bptr->successorcount++;
 367
 368                         cfg_allocate_predecessors(tbptr);
 369
 370                         tbptr->predecessors[tbptr->predecessorcount] = bptr;
 371                         tbptr->predecessorcount++;
 372
 373                         i = iptr->sx.s23.s2.lookupcount;
 374
 375                         while (--i >= 0) {
 376                                 tbptr = lookup->target.block;
 377                                 lookup++;
 378
 379                                 bptr->successors[bptr->successorcount] = tbptr;
 380                                 bptr->successorcount++;
 381
 382                                 cfg_allocate_predecessors(tbptr);
 383                                 cfg_insert_predecessors(tbptr, bptr);
 384                         }
 385                         break;
 386
 387                 default:
 388                         tbptr = bptr->next;
 389
 390                         cfg_allocate_successors(bptr);
 391
 392                         bptr->successors[0] = tbptr;
 393                         bptr->successorcount++;
 394
 395                         /* An exception handler has no predecessors. */
 396
 397                         if (tbptr->type != BBTYPE_EXH) {
 398                                 cfg_allocate_predecessors(tbptr);
 399
 400                                 tbptr->predecessors[tbptr->predecessorcount] = bptr;
 401                                 tbptr->predecessorcount++;
 402                         }
 403                         break;
 404                 }
 405         }
 406
 407         /* everything's ok */
 408
 409         return true;
 410 }
 411
 412
 413 /*
 414  * These are local overrides for various environment variables in Emacs.
 415  * Please do not remove this and leave it at the end of the file, where
 416  * Emacs will automagically detect them.
 417  * ---------------------------------------------------------------------
 418  * Local variables:
 419  * mode: c
 420  * indent-tabs-mode: t
 421  * c-basic-offset: 4
 422  * tab-width: 4
 423  * End:
 424  * vim:noexpandtab:sw=4:ts=4:
 425  */