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