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