src/vm/jit/loop/graph.c

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