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:
  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         methodinfo      *m;
 118         basicblock      *bptr;
 119         basicblock      *tbptr;
 120         basicblock      *ntbptr;
 121         instruction     *iptr;
 122         branch_target_t *table;
 123         lookup_target_t *lookup;
 124         s4               i, j;
 125
 126         /* get required compiler data */
 127
 128         m = jd->m;
 129
 130         /* process all basic blocks to find the predecessor/successor counts */
 131
 132         bptr = jd->new_basicblocks;
 133
 134         for (i = 0; i < jd->new_basicblockcount; i++, bptr++) {
 135                 if (bptr->icount == 0)
 136                         continue;
 137
 138                 iptr = bptr->iinstr + bptr->icount - 1;
 139
 140                 switch (iptr->opc) {
 141                 case ICMD_RET:
 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  = BLOCK_OF(iptr->dst.insindex);
 173                         ntbptr = bptr->next;
 174
 175                         tbptr->predecessorcount++;
 176                         ntbptr->predecessorcount++;
 177                         break;
 178
 179                 case ICMD_GOTO:
 180                         bptr->successorcount++;
 181
 182                         tbptr = BLOCK_OF(iptr->dst.insindex);
 183                         tbptr->predecessorcount++;
 184                         break;
 185
 186                 case ICMD_TABLESWITCH:
 187                         table = iptr->dst.table;
 188
 189                         bptr->successorcount++;
 190
 191                         tbptr = BLOCK_OF((table++)->insindex);
 192                         tbptr->predecessorcount++;
 193
 194                         j = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
 195
 196                         while (--j >= 0) {
 197                                 bptr->successorcount++;
 198
 199                                 tbptr = BLOCK_OF((table++)->insindex);
 200                                 tbptr->predecessorcount++;
 201                         }
 202                         break;
 203
 204                 case ICMD_LOOKUPSWITCH:
 205                         lookup = iptr->dst.lookup;
 206
 207                         bptr->successorcount++;
 208
 209                         tbptr = BLOCK_OF(iptr->sx.s23.s3.lookupdefault.insindex);
 210                         tbptr->predecessorcount++;
 211
 212                         j = iptr->sx.s23.s2.lookupcount;
 213
 214                         while (--j >= 0) {
 215                                 bptr->successorcount++;
 216
 217                                 tbptr = BLOCK_OF((lookup++)->target.insindex);
 218                                 tbptr->predecessorcount++;
 219                         }
 220                         break;
 221
 222                 default:
 223                         bptr->successorcount++;
 224
 225                         tbptr = bptr + 1;
 226                         tbptr->predecessorcount++;
 227                         break;
 228                 }
 229         }
 230
 231         /* Second iteration to allocate the arrays and insert the basic
 232            block pointers. */
 233
 234         bptr = jd->new_basicblocks;
 235
 236         for (i = 0; i < jd->new_basicblockcount; i++, bptr++) {
 237                 if (bptr->icount == 0)
 238                         continue;
 239
 240                 iptr = bptr->iinstr + bptr->icount - 1;
 241
 242                 switch (iptr->opc) {
 243                 case ICMD_RET:
 244                 case ICMD_RETURN:
 245                 case ICMD_IRETURN:
 246                 case ICMD_LRETURN:
 247                 case ICMD_FRETURN:
 248                 case ICMD_DRETURN:
 249                 case ICMD_ARETURN:
 250                 case ICMD_ATHROW:
 251                         break;
 252
 253                 case ICMD_IFEQ:
 254                 case ICMD_IFNE:
 255                 case ICMD_IFLT:
 256                 case ICMD_IFGE:
 257                 case ICMD_IFGT:
 258                 case ICMD_IFLE:
 259
 260                 case ICMD_IFNULL:
 261                 case ICMD_IFNONNULL:
 262
 263                 case ICMD_IF_ICMPEQ:
 264                 case ICMD_IF_ICMPNE:
 265                 case ICMD_IF_ICMPLT:
 266                 case ICMD_IF_ICMPGE:
 267                 case ICMD_IF_ICMPGT:
 268                 case ICMD_IF_ICMPLE:
 269
 270                 case ICMD_IF_ACMPEQ:
 271                 case ICMD_IF_ACMPNE:
 272                         tbptr  = BLOCK_OF(iptr->dst.insindex);
 273                         ntbptr = bptr->next;
 274
 275                         cfg_allocate_successors(bptr);
 276
 277                         bptr->successors[0] = tbptr;
 278                         bptr->successors[1] = ntbptr;
 279                         bptr->successorcount += 2;
 280
 281                         cfg_allocate_predecessors(tbptr);
 282                         cfg_allocate_predecessors(ntbptr);
 283
 284                         tbptr->predecessors[tbptr->predecessorcount] = bptr;
 285                         tbptr->predecessorcount++;
 286
 287                         ntbptr->predecessors[ntbptr->predecessorcount] = bptr;
 288                         ntbptr->predecessorcount++;
 289                         break;
 290
 291                 case ICMD_GOTO:
 292                         tbptr = BLOCK_OF(iptr->dst.insindex);
 293
 294                         cfg_allocate_successors(bptr);
 295
 296                         bptr->successors[0] = tbptr;
 297                         bptr->successorcount++;
 298
 299                         cfg_allocate_predecessors(tbptr);
 300
 301                         tbptr->predecessors[tbptr->predecessorcount] = bptr;
 302                         tbptr->predecessorcount++;
 303                         break;
 304
 305                 case ICMD_TABLESWITCH:
 306                         table = iptr->dst.table;
 307
 308                         tbptr = BLOCK_OF((table++)->insindex);
 309
 310                         cfg_allocate_successors(bptr);
 311
 312                         bptr->successors[0] = tbptr;
 313                         bptr->successorcount++;
 314
 315                         cfg_allocate_predecessors(tbptr);
 316
 317                         tbptr->predecessors[tbptr->predecessorcount] = bptr;
 318                         tbptr->predecessorcount++;
 319
 320                         j = iptr->sx.s23.s3.tablehigh - iptr->sx.s23.s2.tablelow + 1;
 321
 322                         while (--j >= 0) {
 323                                 tbptr = BLOCK_OF((table++)->insindex);
 324
 325                                 bptr->successors[bptr->successorcount] = tbptr;
 326                                 bptr->successorcount++;
 327
 328                                 cfg_allocate_predecessors(tbptr);
 329                                 cfg_insert_predecessors(tbptr, bptr);
 330                         }
 331                         break;
 332
 333                 case ICMD_LOOKUPSWITCH:
 334                         lookup = iptr->dst.lookup;
 335
 336                         tbptr = BLOCK_OF(iptr->sx.s23.s3.lookupdefault.insindex);
 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                         j = iptr->sx.s23.s2.lookupcount;
 349
 350                         while (--j >= 0) {
 351                                 tbptr = BLOCK_OF((lookup++)->target.insindex);
 352
 353                                 bptr->successors[bptr->successorcount] = tbptr;
 354                                 bptr->successorcount++;
 355
 356                                 cfg_allocate_predecessors(tbptr);
 357                                 cfg_insert_predecessors(tbptr, bptr);
 358                         }
 359                         break;
 360
 361                 default:
 362                         tbptr = bptr + 1;
 363
 364                         cfg_allocate_successors(bptr);
 365
 366                         bptr->successors[0] = tbptr;
 367                         bptr->successorcount++;
 368
 369                         cfg_allocate_predecessors(tbptr);
 370
 371                         tbptr->predecessors[tbptr->predecessorcount] = bptr;
 372                         tbptr->predecessorcount++;
 373                         break;
 374                 }
 375         }
 376
 377         /* everything's ok */
 378
 379         return true;
 380 }
 381
 382
 383 /*
 384  * These are local overrides for various environment variables in Emacs.
 385  * Please do not remove this and leave it at the end of the file, where
 386  * Emacs will automagically detect them.
 387  * ---------------------------------------------------------------------
 388  * Local variables:
 389  * mode: c
 390  * indent-tabs-mode: t
 391  * c-basic-offset: 4
 392  * tab-width: 4
 393  * End:
 394  * vim:noexpandtab:sw=4:ts=4:
 395  */