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