src/vm/jit/loop/graph.c

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