src/vm/jit/loop/graph.c

   1 /* src/vm/jit/loop/graph.c - control flow graph
   2
   3    Copyright (C) 1996-2005 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    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., 59 Temple Place - Suite 330, Boston, MA
  23    02111-1307, USA.
  24
  25    Contact: cacao@complang.tuwien.ac.at
  26
  27    Authors: Christopher Kruegel
  28
  29    Changes: Christian Thalinger
  30
  31    Contains the functions which build a list, that represents the
  32    control flow graph of the procedure, that is being analyzed.
  33
  34    $Id: graph.c 2495 2005-05-22 19:49:53Z twisti $
  35
  36 */
  37
  38
  39 #include <assert.h>
  40
  41 #include "mm/memory.h"
  42 #include "toolbox/logging.h"
  43 #include "vm/jit/jit.h"
  44 #include "vm/jit/loop/graph.h"
  45 #include "vm/jit/loop/loop.h"
  46
  47
  48 void LoopContainerInit(methodinfo *m, struct LoopContainer *lc, int i)
  49 {
  50         struct LoopElement *le = DMNEW(struct LoopElement, 1);
  51
  52         le->next = NULL;
  53
  54         lc->parent = NULL;
  55
  56         lc->tree_right = NULL;
  57         lc->tree_down = NULL;
  58
  59         lc->exceptions = NULL;
  60
  61         lc->in_degree = 0;
  62         le->node = lc->loop_head = i;
  63         le->block = &m->basicblocks[i];
  64
  65         /* lc->nodes = (int *) malloc(sizeof(int)*m->basicblockcount);
  66         lc->nodes[0] = i; */
  67
  68         lc->nodes = le;
  69 }
  70
  71
  72 /*
  73    depthFirst() builds the control flow graph out of the intermediate code of
  74    the procedure, that is to be optimized and stores the list in the global
  75    variable c_dTable
  76 */
  77
  78 void depthFirst(methodinfo *m, loopdata *ld)
  79 {
  80         int i;
  81
  82 /*      allocate memory and init gobal variables needed by function dF(m, int, int)     */
  83
  84         ld->c_defnum = DMNEW(int, m->basicblockcount);
  85         ld->c_numPre = DMNEW(int, m->basicblockcount);
  86         ld->c_parent = DMNEW(int, m->basicblockcount);
  87         ld->c_reverse = DMNEW(int, m->basicblockcount);
  88         ld->c_pre = DMNEW(int *, m->basicblockcount);
  89         ld->c_dTable = DMNEW(struct depthElement *, m->basicblockcount);
  90
  91         for (i = 0; i < m->basicblockcount; ++i) {
  92                 ld->c_defnum[i] = ld->c_parent[i] = -1;
  93                 ld->c_numPre[i] = ld->c_reverse[i] = 0;
  94
  95                 ld->c_pre[i] = DMNEW(int, m->basicblockcount);
  96                 ld->c_dTable[i] = NULL;
  97         }
  98
  99         ld->c_globalCount = 0;
 100         ld->c_allLoops = NULL;
 101
 102         dF(m, ld, -1, 0);       /* call helper function dF that traverses basic block structure */
 103 }
 104
 105
 106 /*
 107    dF starts from the first block of the given procedure and traverses the
 108    control flow graph in a depth-first order, thereby building up the adeacency
 109    list c_dTable
 110 */
 111
 112 void dF(methodinfo *m, loopdata *ld, int from, int blockIndex)
 113 {
 114         instruction *ip;
 115         s4 *s4ptr;
 116         int high, low, count;
 117         struct depthElement *hp;
 118         struct LoopContainer *tmp;
 119         int cnt, *ptr;
 120
 121         if (from >= 0) {
 122 /*      the current basic block has a predecessor (ie. is not the first one)            */
 123                 hp = DNEW(struct depthElement);/* create new depth element                                      */
 124
 125                 hp->next = ld->c_dTable[from];  /* insert values                                                        */
 126                 hp->value = blockIndex;
 127                 hp->changes = NULL;
 128
 129                 ld->c_dTable[from] = hp;        /* insert into table                                                    */
 130         }
 131
 132         if (from == blockIndex) {       /* insert one node loops into loop container    */
 133                 tmp = DNEW(struct LoopContainer);
 134                 LoopContainerInit(m, tmp, blockIndex);
 135                 tmp->next = ld->c_allLoops;
 136                 ld->c_allLoops = tmp;
 137         }
 138
 139 #ifdef C_DEBUG
 140         if (blockIndex > m->basicblockcount) {
 141                 log_text("DepthFirst: BlockIndex exceeded\n");
 142                 assert(0);
 143         }
 144 #endif
 145
 146         ip = m->basicblocks[blockIndex].iinstr + m->basicblocks[blockIndex].icount -1;
 147                                                                                 /* set ip to last instruction                   */
 148
 149         if (ld->c_defnum[blockIndex] == -1) {   /* current block has not been visited   */
 150             ld->c_defnum[blockIndex] = ld->c_globalCount;       /* update global count                  */
 151             ld->c_parent[blockIndex] = from;    /* write parent block of current one    */
 152                 ld->c_reverse[ld->c_globalCount] = blockIndex;
 153                 ++ld->c_globalCount;
 154
 155                 if (!m->basicblocks[blockIndex].icount) {
 156                                                                                 /* block does not contain instructions  */
 157                         dF(m, ld, blockIndex, blockIndex+1);
 158                     }
 159                 else {                                                  /* for all successors, do                               */
 160                         switch (ip->opc) {                      /* check type of last instruction               */
 161                         case ICMD_RETURN:
 162                         case ICMD_IRETURN:
 163                         case ICMD_LRETURN:
 164                         case ICMD_FRETURN:
 165                         case ICMD_DRETURN:
 166                         case ICMD_ARETURN:
 167                         case ICMD_ATHROW:
 168                                 break;                                  /* function returns -> end of graph             */
 169
 170                         case ICMD_IFEQ:
 171                         case ICMD_IFNE:
 172                         case ICMD_IFLT:
 173                         case ICMD_IFGE:
 174                         case ICMD_IFGT:
 175                         case ICMD_IFLE:
 176                         case ICMD_IFNULL:
 177                         case ICMD_IFNONNULL:
 178                         case ICMD_IF_ICMPEQ:
 179                         case ICMD_IF_ICMPNE:
 180                         case ICMD_IF_ICMPLT:
 181                         case ICMD_IF_ICMPGE:
 182                         case ICMD_IF_ICMPGT:
 183                         case ICMD_IF_ICMPLE:
 184                         case ICMD_IF_LEQ:
 185                         case ICMD_IF_LNE:
 186                         case ICMD_IF_LLT:
 187                         case ICMD_IF_LGE:
 188                         case ICMD_IF_LGT:
 189                         case ICMD_IF_LLE:
 190                         case ICMD_IF_LCMPEQ:
 191                         case ICMD_IF_LCMPNE:
 192                         case ICMD_IF_LCMPLT:
 193                         case ICMD_IF_LCMPGE:
 194                         case ICMD_IF_LCMPGT:
 195                         case ICMD_IF_LCMPLE:
 196                         case ICMD_IF_ACMPEQ:
 197                         case ICMD_IF_ACMPNE:                            /* branch -> check next block   */
 198                            dF(m, ld, blockIndex, blockIndex + 1);
 199                            /* fall throu */
 200
 201                         case ICMD_GOTO:
 202                                 dF(m, ld, blockIndex, m->basicblockindex[ip->op1]);
 203                                 break;                                                  /* visit branch (goto) target   */
 204
 205                         case ICMD_TABLESWITCH:                          /* switch statement                             */
 206                                 s4ptr = ip->val.a;
 207
 208                                 dF(m, ld, blockIndex, m->basicblockindex[*s4ptr]);      /* default branch               */
 209
 210                                 s4ptr++;
 211                                 low = *s4ptr;
 212                                 s4ptr++;
 213                                 high = *s4ptr;
 214
 215                                 count = (high-low+1);
 216
 217                                 while (--count >= 0) {
 218                                         s4ptr++;
 219                                         dF(m, ld, blockIndex, m->basicblockindex[*s4ptr]);
 220                                     }
 221                                 break;
 222
 223                         case ICMD_LOOKUPSWITCH:                         /* switch statement                             */
 224                                 s4ptr = ip->val.a;
 225
 226                                 dF(m, ld, blockIndex, m->basicblockindex[*s4ptr]);      /* default branch               */
 227
 228                                 ++s4ptr;
 229                                 count = *s4ptr++;
 230
 231                                 while (--count >= 0) {
 232                                         dF(m, ld, blockIndex, m->basicblockindex[s4ptr[1]]);
 233                                         s4ptr += 2;
 234                                     }
 235                                 break;
 236
 237                         case ICMD_JSR:
 238                                 ld->c_last_jump = blockIndex;
 239                                 dF(m, ld, blockIndex, m->basicblockindex[ip->op1]);
 240                                 break;
 241
 242                         case ICMD_RET:
 243                                 dF(m, ld, blockIndex, ld->c_last_jump+1);
 244                                 break;
 245
 246                         default:
 247                                 dF(m, ld, blockIndex, blockIndex + 1);
 248                                 break;
 249                             }
 250                     }
 251             }
 252
 253         for (ptr = ld->c_pre[blockIndex], cnt = 0; cnt < ld->c_numPre[blockIndex]; ++cnt, ++ptr)
 254         {
 255                 if (*ptr == from)
 256                         break;
 257         }
 258
 259         if (cnt >= ld->c_numPre[blockIndex]) {
 260                 ld->c_pre[blockIndex][ld->c_numPre[blockIndex]] = from;
 261                                                     /* add predeccessors to list c_pre          */
 262                 ld->c_numPre[blockIndex]++;                             /* increase number of predecessors      */
 263         }
 264
 265 }
 266
 267
 268 /*
 269    a slightly modified version of dF(m, ld, int, int) that is used to traverse the part
 270    of the control graph that is not reached by normal program flow but by the
 271    raising of exceptions (code of catch blocks)
 272 */
 273
 274 void dF_Exception(methodinfo *m, loopdata *ld, int from, int blockIndex)
 275 {
 276         instruction *ip;
 277         s4 *s4ptr;
 278         int high, low, count;
 279         struct depthElement *hp;
 280
 281         if (ld->c_exceptionVisit[blockIndex] < 0)       /* has block been visited, return       */
 282                 ld->c_exceptionVisit[blockIndex] = 1;
 283         else
 284                 return;
 285
 286         if (ld->c_dTable[blockIndex] != NULL)           /* back to regular code section         */
 287                 return;
 288
 289         if (from >= 0) {                /* build exception graph (in c_exceptionGraph)          */
 290             hp = DNEW(struct depthElement);
 291                 hp->next = ld->c_exceptionGraph[from];
 292                 hp->value = blockIndex;
 293                 hp->changes = NULL;
 294
 295                 ld->c_exceptionGraph[from] = hp;
 296         }
 297
 298 #ifdef C_DEBUG
 299         if (blockIndex > m->basicblockcount) {
 300                 log_text("DepthFirst: BlockIndex exceeded");
 301                 assert(0);
 302         }
 303 #endif
 304
 305         ip = m->basicblocks[blockIndex].iinstr + m->basicblocks[blockIndex].icount -1;
 306
 307         if (!m->basicblocks[blockIndex].icount)
 308                 dF_Exception(m, ld, blockIndex, blockIndex+1);
 309         else {
 310                 switch (ip->opc) {
 311                 case ICMD_RETURN:
 312                 case ICMD_IRETURN:
 313                 case ICMD_LRETURN:
 314                 case ICMD_FRETURN:
 315                 case ICMD_DRETURN:
 316                 case ICMD_ARETURN:
 317                 case ICMD_ATHROW:
 318                         break;
 319
 320                 case ICMD_IFEQ:
 321                 case ICMD_IFNE:
 322                 case ICMD_IFLT:
 323                 case ICMD_IFGE:
 324                 case ICMD_IFGT:
 325                 case ICMD_IFLE:
 326                 case ICMD_IFNULL:
 327                 case ICMD_IFNONNULL:
 328                 case ICMD_IF_ICMPEQ:
 329                 case ICMD_IF_ICMPNE:
 330                 case ICMD_IF_ICMPLT:
 331                 case ICMD_IF_ICMPGE:
 332                 case ICMD_IF_ICMPGT:
 333                 case ICMD_IF_ICMPLE:
 334                 case ICMD_IF_LEQ:
 335                 case ICMD_IF_LNE:
 336                 case ICMD_IF_LLT:
 337                 case ICMD_IF_LGE:
 338                 case ICMD_IF_LGT:
 339                 case ICMD_IF_LLE:
 340                 case ICMD_IF_LCMPEQ:
 341                 case ICMD_IF_LCMPNE:
 342                 case ICMD_IF_LCMPLT:
 343                 case ICMD_IF_LCMPGE:
 344                 case ICMD_IF_LCMPGT:
 345                 case ICMD_IF_LCMPLE:
 346                 case ICMD_IF_ACMPEQ:
 347                 case ICMD_IF_ACMPNE:                    /* branch -> check next block   */
 348                         dF_Exception(m, ld, blockIndex, blockIndex + 1);
 349                         /* fall throu */
 350
 351                 case ICMD_GOTO:
 352                         dF_Exception(m, ld, blockIndex, m->basicblockindex[ip->op1]);
 353                         break;
 354
 355                 case ICMD_TABLESWITCH:
 356                         s4ptr = ip->val.a;
 357
 358                         /* default branch */
 359                         dF_Exception(m, ld, blockIndex, m->basicblockindex[*s4ptr]);
 360
 361                         s4ptr++;
 362                         low = *s4ptr;
 363                         s4ptr++;
 364                         high = *s4ptr;
 365
 366                         count = (high-low+1);
 367
 368                         while (--count >= 0) {
 369                                 s4ptr++;
 370                                 dF_Exception(m, ld, blockIndex, m->basicblockindex[*s4ptr]);
 371                             }
 372                         break;
 373
 374                 case ICMD_LOOKUPSWITCH:
 375                         s4ptr = ip->val.a;
 376
 377                         /* default branch */
 378                         dF_Exception(m, ld, blockIndex, m->basicblockindex[*s4ptr]);
 379
 380                         ++s4ptr;
 381                         count = *s4ptr++;
 382
 383                         while (--count >= 0) {
 384                                 dF_Exception(m, ld, blockIndex, m->basicblockindex[s4ptr[1]]);
 385                                 s4ptr += 2;
 386                             }
 387                         break;
 388
 389                 case ICMD_JSR:
 390                         ld->c_last_jump = blockIndex;
 391                         dF_Exception(m, ld, blockIndex, m->basicblockindex[ip->op1]);
 392                         break;
 393
 394                 case ICMD_RET:
 395                         dF_Exception(m, ld, blockIndex, ld->c_last_jump+1);
 396                         break;
 397
 398                 default:
 399                         dF_Exception(m, ld, blockIndex, blockIndex + 1);
 400                         break;
 401                     }
 402         }
 403 }
 404
 405
 406 #if 0
 407 /*
 408   Test function -> will be removed in final release
 409 */
 410 void resultPass1(methodinfo *m)
 411 {
 412         int i, j;
 413         struct depthElement *hp;
 414
 415         printf("\n\n****** PASS 1 ******\n\n");
 416         printf("Number of Nodes: %d\n\n", ld->c_globalCount);
 417
 418         printf("Predecessors:\n");
 419         for (i=0; i<m->basicblockcount; ++i) {
 420                 printf("Block %d:\t", i);
 421                 for (j=0; j<ld->c_numPre[i]; ++j)
 422                         printf("%d ", ld->c_pre[i][j]);
 423                 printf("\n");
 424         }
 425         printf("\n");
 426
 427         printf("Graph:\n");
 428         for (i=0; i<m->basicblockcount; ++i) {
 429                 printf("Block %d:\t", i);
 430                 hp = ld->c_dTable[i];
 431
 432                 while (hp != NULL) {
 433                         printf("%d ", hp->value);
 434                         hp = hp->next;
 435                     }
 436                 printf("\n");
 437             }
 438         printf("\n");
 439 }
 440 #endif
 441
 442 /*
 443  * These are local overrides for various environment variables in Emacs.
 444  * Please do not remove this and leave it at the end of the file, where
 445  * Emacs will automagically detect them.
 446  * ---------------------------------------------------------------------
 447  * Local variables:
 448  * mode: c
 449  * indent-tabs-mode: t
 450  * c-basic-offset: 4
 451  * tab-width: 4
 452  * End:
 453  */