src/vm/jit/loop/graph.c

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