src/vm/jit/cfg.c

   1 /* src/vm/cfg.c - build a control-flow graph
   2
   3    Copyright (C) 2006 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    Contact: cacao@cacaojvm.org
  26
  27    Authors: Christian Thalinger
  28
  29    Changes: Edwin Steiner
  30
  31    $Id: cacao.c 4357 2006-01-22 23:33:38Z twisti $
  32
  33 */
  34
  35
  36 #include "config.h"
  37
  38 #include <assert.h>
  39
  40 #include "vm/types.h"
  41
  42 #include "mm/memory.h"
  43 #include "vm/jit/jit.h"
  44 #include "vm/jit/stack.h"
  45
  46
  47 /* cfg_allocate_predecessors ***************************************************
  48
  49    Allocates the predecessor array, if there is none, and resets the
  50    predecessor count.
  51
  52 *******************************************************************************/
  53
  54 static void cfg_allocate_predecessors(basicblock *bptr)
  55 {
  56         if (bptr->predecessors == NULL) {
  57                 bptr->predecessors = DMNEW(basicblock*, bptr->predecessorcount);
  58
  59                 bptr->predecessorcount = 0;
  60         }
  61 }
  62
  63
  64 /* cfg_allocate_successors *****************************************************
  65
  66    Allocates the succecessor array, if there is none, and resets the
  67    predecessor count.
  68
  69 *******************************************************************************/
  70
  71 static void cfg_allocate_successors(basicblock *bptr)
  72 {
  73         if (bptr->successors == NULL) {
  74                 bptr->successors = DMNEW(basicblock*, bptr->successorcount);
  75
  76                 bptr->successorcount = 0;
  77         }
  78 }
  79
  80
  81 /* cfg_insert_predecessor ******************************************************
  82
  83    Inserts a predecessor into the array, but checks for duplicate
  84    entries.  This is used for TABLESWITCH and LOOKUPSWITCH.
  85
  86 *******************************************************************************/
  87
  88 static void cfg_insert_predecessors(basicblock *bptr, basicblock *pbptr)
  89 {
  90         basicblock **tbptr;
  91         s4           i;
  92
  93         tbptr = bptr->predecessors;
  94
  95         /* check if the predecessors is already stored in the array */
  96
  97         for (i = 0; i < bptr->predecessorcount; i++, tbptr++)
  98                 if (*tbptr == pbptr)
  99                         return;
 100
 101         /* not found, insert it */
 102
 103         bptr->predecessors[bptr->predecessorcount] = pbptr;
 104         bptr->predecessorcount++;
 105 }
 106
 107
 108 /* cfg_build *******************************************************************
 109
 110    Build a control-flow graph in finding all predecessors and
 111    successors for the basic blocks.
 112
 113 *******************************************************************************/
 114
 115 bool cfg_build(jitdata *jd)
 116 {
 117         basicblock      *bptr;
 118         basicblock      *tbptr;
 119         basicblock      *ntbptr;
 120         instruction     *iptr;
 121         branch_target_t *table;
 122         lookup_target_t *lookup;
 123         s4               i;
 124
 125         /* process all basic blocks to find the predecessor/successor counts */
 126
 127         bptr = jd->basicblocks;
 128
 129         for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
 130                 if ((bptr->icount == 0) || (bptr->flags == BBUNDEF))
 131                         continue;
 132
 133                 iptr = bptr->iinstr + bptr->icount - 1;
 134
 135                 /* skip NOPs at the end of the block */
 136
 137                 while (iptr->opc == ICMD_NOP) {
 138                         if (iptr == bptr->iinstr)
 139                                 break;
 140                         iptr--;
 141                 }
 142
 143                 switch (iptr->opc) {
 144                 case ICMD_RETURN:
 145                 case ICMD_IRETURN:
 146                 case ICMD_LRETURN:
 147                 case ICMD_FRETURN:
 148                 case ICMD_DRETURN:
 149                 case ICMD_ARETURN:
 150                 case ICMD_ATHROW:
 151                         break;
 152
 153                 case ICMD_IFEQ:
 154                 case ICMD_IFNE:
 155                 case ICMD_IFLT:
 156                 case ICMD_IFGE:
 157                 case ICMD_IFGT:
 158                 case ICMD_IFLE:
 159
 160                 case ICMD_IFNULL:
 161                 case ICMD_IFNONNULL:
 162
 163                 case ICMD_IF_ICMPEQ:
 164                 case ICMD_IF_ICMPNE:
 165                 case ICMD_IF_ICMPLT:
 166                 case ICMD_IF_ICMPGE:
 167                 case ICMD_IF_ICMPGT:
 168                 case ICMD_IF_ICMPLE:
 169
 170                 case ICMD_IF_ACMPEQ:
 171                 case ICMD_IF_ACMPNE:
 172                         bptr->successorcount += 2;
 173
 174                         tbptr  = iptr->dst.block;
 175                         ntbptr = bptr->next;
 176
 177                         tbptr->predecessorcount++;
 178                         ntbptr->predecessorcount++;
 179                         break;
 180
 181                 case ICMD_JSR:
 182                         bptr->successorcount++;
 183
 184                         tbptr = iptr->sx.s23.s3.jsrtarget.block;
 185                         tbptr->predecessorcount++;
 186                         break;
 187
 188                 case ICMD_GOTO:
 189                 case ICMD_RET:
 190                         bptr->successorcount++;
 191
 192                         tbptr = iptr->dst.block;
 193                         tbptr->predecessorcount++;
 194                         break;
 195
 196                 case ICMD_TABLESWITCH:
 197                         table = iptr->dst.table;
 198
 199                         bptr->successorcount++;
 200
 201                         tbptr = table->block;
 202                         tbptr->predecessorcount++;
 203                         table++;
 204
 205                         i = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
 206
 207                         while (--i >= 0) {
 208                                 bptr->successorcount++;
 209
 210                                 tbptr = table->block;
 211                                 tbptr->predecessorcount++;
 212                                 table++;
 213                         }
 214                         break;
 215
 216                 case ICMD_LOOKUPSWITCH:
 217                         lookup = iptr->dst.lookup;
 218
 219                         bptr->successorcount++;
 220
 221                         tbptr = iptr->sx.s23.s3.lookupdefault.block;
 222                         tbptr->predecessorcount++;
 223
 224                         i = iptr->sx.s23.s2.lookupcount;
 225
 226                         while (--i >= 0) {
 227                                 bptr->successorcount++;
 228
 229                                 tbptr = lookup->target.block;
 230                                 tbptr->predecessorcount++;
 231                                 lookup++;
 232                         }
 233                         break;
 234
 235                 default:
 236                         bptr->successorcount++;
 237
 238                         tbptr = bptr->next;
 239
 240                         /* An exception handler has no predecessors. */
 241
 242                         if (tbptr->type != BBTYPE_EXH)
 243                                 tbptr->predecessorcount++;
 244                         break;
 245                 }
 246         }
 247
 248         /* Second iteration to allocate the arrays and insert the basic
 249            block pointers. */
 250
 251         bptr = jd->basicblocks;
 252
 253         for (bptr = jd->basicblocks; bptr != NULL; bptr = bptr->next) {
 254                 if ((bptr->icount == 0) || (bptr->flags == BBUNDEF))
 255                         continue;
 256
 257                 iptr = bptr->iinstr + bptr->icount - 1;
 258
 259                 /* skip NOPs at the end of the block */
 260
 261                 while (iptr->opc == ICMD_NOP) {
 262                         if (iptr == bptr->iinstr)
 263                                 break;
 264                         iptr--;
 265                 }
 266
 267                 switch (iptr->opc) {
 268                 case ICMD_RETURN:
 269                 case ICMD_IRETURN:
 270                 case ICMD_LRETURN:
 271                 case ICMD_FRETURN:
 272                 case ICMD_DRETURN:
 273                 case ICMD_ARETURN:
 274                 case ICMD_ATHROW:
 275                         break;
 276
 277                 case ICMD_IFEQ:
 278                 case ICMD_IFNE:
 279                 case ICMD_IFLT:
 280                 case ICMD_IFGE:
 281                 case ICMD_IFGT:
 282                 case ICMD_IFLE:
 283
 284                 case ICMD_IFNULL:
 285                 case ICMD_IFNONNULL:
 286
 287                 case ICMD_IF_ICMPEQ:
 288                 case ICMD_IF_ICMPNE:
 289                 case ICMD_IF_ICMPLT:
 290                 case ICMD_IF_ICMPGE:
 291                 case ICMD_IF_ICMPGT:
 292                 case ICMD_IF_ICMPLE:
 293
 294                 case ICMD_IF_ACMPEQ:
 295                 case ICMD_IF_ACMPNE:
 296                         tbptr  = iptr->dst.block;
 297                         ntbptr = bptr->next;
 298
 299                         cfg_allocate_successors(bptr);
 300
 301                         bptr->successors[0] = tbptr;
 302                         bptr->successors[1] = ntbptr;
 303                         bptr->successorcount += 2;
 304
 305                         cfg_allocate_predecessors(tbptr);
 306                         cfg_allocate_predecessors(ntbptr);
 307
 308                         tbptr->predecessors[tbptr->predecessorcount] = bptr;
 309                         tbptr->predecessorcount++;
 310
 311                         ntbptr->predecessors[ntbptr->predecessorcount] = bptr;
 312                         ntbptr->predecessorcount++;
 313                         break;
 314
 315                 case ICMD_JSR:
 316                         tbptr = iptr->sx.s23.s3.jsrtarget.block;
 317                         goto goto_tail;
 318
 319                 case ICMD_GOTO:
 320                 case ICMD_RET:
 321                         tbptr = iptr->dst.block;
 322 goto_tail:
 323                         cfg_allocate_successors(bptr);
 324
 325                         bptr->successors[0] = tbptr;
 326                         bptr->successorcount++;
 327
 328                         cfg_allocate_predecessors(tbptr);
 329
 330                         tbptr->predecessors[tbptr->predecessorcount] = bptr;
 331                         tbptr->predecessorcount++;
 332                         break;
 333
 334                 case ICMD_TABLESWITCH:
 335                         table = iptr->dst.table;
 336
 337                         tbptr = table->block;
 338                         table++;
 339
 340                         cfg_allocate_successors(bptr);
 341
 342                         bptr->successors[0] = tbptr;
 343                         bptr->successorcount++;
 344
 345                         cfg_allocate_predecessors(tbptr);
 346
 347                         tbptr->predecessors[tbptr->predecessorcount] = bptr;
 348                         tbptr->predecessorcount++;
 349
 350                         i = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
 351
 352                         while (--i >= 0) {
 353                                 tbptr = table->block;
 354                                 table++;
 355
 356                                 bptr->successors[bptr->successorcount] = tbptr;
 357                                 bptr->successorcount++;
 358
 359                                 cfg_allocate_predecessors(tbptr);
 360                                 cfg_insert_predecessors(tbptr, bptr);
 361                         }
 362                         break;
 363
 364                 case ICMD_LOOKUPSWITCH:
 365                         lookup = iptr->dst.lookup;
 366
 367                         tbptr = iptr->sx.s23.s3.lookupdefault.block;
 368
 369                         cfg_allocate_successors(bptr);
 370
 371                         bptr->successors[0] = tbptr;
 372                         bptr->successorcount++;
 373
 374                         cfg_allocate_predecessors(tbptr);
 375
 376                         tbptr->predecessors[tbptr->predecessorcount] = bptr;
 377                         tbptr->predecessorcount++;
 378
 379                         i = iptr->sx.s23.s2.lookupcount;
 380
 381                         while (--i >= 0) {
 382                                 tbptr = lookup->target.block;
 383                                 lookup++;
 384
 385                                 bptr->successors[bptr->successorcount] = tbptr;
 386                                 bptr->successorcount++;
 387
 388                                 cfg_allocate_predecessors(tbptr);
 389                                 cfg_insert_predecessors(tbptr, bptr);
 390                         }
 391                         break;
 392
 393                 default:
 394                         tbptr = bptr->next;
 395
 396                         cfg_allocate_successors(bptr);
 397
 398                         bptr->successors[0] = tbptr;
 399                         bptr->successorcount++;
 400
 401                         /* An exception handler has no predecessors. */
 402
 403                         if (tbptr->type != BBTYPE_EXH) {
 404                                 cfg_allocate_predecessors(tbptr);
 405
 406                                 tbptr->predecessors[tbptr->predecessorcount] = bptr;
 407                                 tbptr->predecessorcount++;
 408                         }
 409                         break;
 410                 }
 411         }
 412
 413         /* everything's ok */
 414
 415         return true;
 416 }
 417
 418
 419 /*
 420  * These are local overrides for various environment variables in Emacs.
 421  * Please do not remove this and leave it at the end of the file, where
 422  * Emacs will automagically detect them.
 423  * ---------------------------------------------------------------------
 424  * Local variables:
 425  * mode: c
 426  * indent-tabs-mode: t
 427  * c-basic-offset: 4
 428  * tab-width: 4
 429  * End:
 430  * vim:noexpandtab:sw=4:ts=4:
 431  */