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 557 2003-11-02 22:51:59Z 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_globalCount = 0;
 106         c_allLoops = NULL;
 107
 108         dF(-1, 0);      /* call helper function dF that traverses basic block structure */
 109 }
 110
 111
 112 /*
 113    dF starts from the first block of the given procedure and traverses the
 114    control flow graph in a depth-first order, thereby building up the adeacency
 115    list c_dTable
 116 */
 117 void dF(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                 if ((hp = (struct depthElement *) malloc(sizeof(struct depthElement))) == NULL)
 129                         c_mem_error();                  /* cretae new depth element                                     */
 130
 131                 hp->next = c_dTable[from];      /* insert values                                                        */
 132                 hp->value = blockIndex;
 133                 hp->changes = NULL;
 134
 135                 c_dTable[from] = hp;    /* insert into table                                                    */
 136             }
 137
 138         if (from == blockIndex) {       /* insert one node loops into loop container    */
 139                 if ((tmp = (struct LoopContainer *) malloc(sizeof(struct LoopContainer))) == NULL)
 140                         c_mem_error();
 141                 LoopContainerInit(tmp, blockIndex);
 142                 tmp->next = c_allLoops;
 143                 c_allLoops = tmp;
 144             }
 145
 146 #ifdef C_DEBUG
 147         if (blockIndex > block_count) {
 148                 fprintf(stderr, "DepthFirst: BlockIndex exceeded\n");
 149                 exit(1);
 150                 }
 151 #endif
 152
 153         ip = block[blockIndex].iinstr + block[blockIndex].icount -1;
 154                                                                                 /* set ip to last instruction                   */
 155
 156         if (c_defnum[blockIndex] == -1) {       /* current block has not been visited   */
 157             c_defnum[blockIndex] = c_globalCount;       /* update global count                  */
 158             c_parent[blockIndex] = from;        /* write parent block of current one    */
 159                 c_reverse[c_globalCount] = blockIndex;
 160                 ++c_globalCount;
 161
 162                 if (!block[blockIndex].icount) {
 163                                                                                 /* block does not contain instructions  */
 164                         dF(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_ACMPEQ:
 192                         case ICMD_IF_ACMPNE:                            /* branch -> check next block   */
 193                            dF(blockIndex, blockIndex + 1);
 194                            /* fall throu */
 195
 196                         case ICMD_GOTO:
 197                                 dF(blockIndex, block_index[ip->op1]);
 198                                 break;                                                  /* visit branch (goto) target   */
 199
 200                         case ICMD_TABLESWITCH:                          /* switch statement                             */
 201                                 s4ptr = ip->val.a;
 202
 203                                 dF(blockIndex, block_index[*s4ptr]);    /* default branch               */
 204
 205                                 s4ptr++;
 206                                 low = *s4ptr;
 207                                 s4ptr++;
 208                                 high = *s4ptr;
 209
 210                                 count = (high-low+1);
 211
 212                                 while (--count >= 0) {
 213                                         s4ptr++;
 214                                         dF(blockIndex, block_index[*s4ptr]);
 215                                     }
 216                                 break;
 217
 218                         case ICMD_LOOKUPSWITCH:                         /* switch statement                             */
 219                                 s4ptr = ip->val.a;
 220
 221                                 dF(blockIndex, block_index[*s4ptr]);    /* default branch               */
 222
 223                                 ++s4ptr;
 224                                 count = *s4ptr++;
 225
 226                                 while (--count >= 0) {
 227                                         dF(blockIndex, block_index[s4ptr[1]]);
 228                                         s4ptr += 2;
 229                                     }
 230                                 break;
 231
 232                         case ICMD_JSR:
 233                                 c_last_jump = blockIndex;
 234                                 dF(blockIndex, block_index[ip->op1]);
 235                                 break;
 236
 237                         case ICMD_RET:
 238                                 dF(blockIndex, c_last_jump+1);
 239                                 break;
 240
 241                         default:
 242                                 dF(blockIndex, blockIndex + 1);
 243                                 break;
 244                             }
 245                     }
 246             }
 247
 248         for (ptr = c_pre[blockIndex], cnt = 0; cnt < c_numPre[blockIndex]; ++cnt, ++ptr)
 249         {
 250                 if (*ptr == from)
 251                         break;
 252         }
 253
 254         if (cnt >= c_numPre[blockIndex]) {
 255                 c_pre[blockIndex][c_numPre[blockIndex]] = from;
 256                                                     /* add predeccessors to list c_pre          */
 257                 c_numPre[blockIndex]++;                         /* increase number of predecessors      */
 258             }
 259
 260 }
 261
 262 /*
 263    a slightly modified version of dF(int, int) that is used to traverse the part
 264    of the control graph that is not reached by normal program flow but by the
 265    raising of exceptions (code of catch blocks)
 266 */
 267 void dF_Exception(int from, int blockIndex)
 268 {
 269         instruction *ip;
 270         s4 *s4ptr;
 271         int high, low, count;
 272         struct depthElement *hp;
 273
 274         if (c_exceptionVisit[blockIndex] < 0)   /* has block been visited, return       */
 275                 c_exceptionVisit[blockIndex] = 1;
 276         else
 277                 return;
 278
 279         if (c_dTable[blockIndex] != NULL)               /* back to regular code section         */
 280                 return;
 281
 282         if (from >= 0) {                /* build exception graph (in c_exceptionGraph)          */
 283             if ((hp = (struct depthElement *) malloc(sizeof(struct depthElement))) == NULL)
 284                         c_mem_error();
 285
 286                 hp->next = c_exceptionGraph[from];
 287                 hp->value = blockIndex;
 288                 hp->changes = NULL;
 289
 290                 c_exceptionGraph[from] = hp;
 291             }
 292
 293 #ifdef C_DEBUG
 294         if (blockIndex > block_count) {
 295                 fprintf(stderr, "DepthFirst: BlockIndex exceeded\n");
 296                 exit(1);
 297         }
 298 #endif
 299
 300         ip = block[blockIndex].iinstr + block[blockIndex].icount -1;
 301
 302         if (!block[blockIndex].icount)
 303                 dF_Exception(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_ACMPEQ:
 330                 case ICMD_IF_ACMPNE:
 331                         dF_Exception(blockIndex, blockIndex + 1);
 332                         /* fall throu */
 333
 334                 case ICMD_GOTO:
 335                         dF_Exception(blockIndex, block_index[ip->op1]);
 336                         break;
 337
 338                 case ICMD_TABLESWITCH:
 339                         s4ptr = ip->val.a;
 340
 341                         /* default branch */
 342                         dF_Exception(blockIndex, block_index[*s4ptr]);
 343
 344                         s4ptr++;
 345                         low = *s4ptr;
 346                         s4ptr++;
 347                         high = *s4ptr;
 348
 349                         count = (high-low+1);
 350
 351                         while (--count >= 0) {
 352                                 s4ptr++;
 353                                 dF_Exception(blockIndex, block_index[*s4ptr]);
 354                             }
 355                         break;
 356
 357                 case ICMD_LOOKUPSWITCH:
 358                         s4ptr = ip->val.a;
 359
 360                         /* default branch */
 361                         dF_Exception(blockIndex, block_index[*s4ptr]);
 362
 363                         ++s4ptr;
 364                         count = *s4ptr++;
 365
 366                         while (--count >= 0) {
 367                                 dF_Exception(blockIndex, block_index[s4ptr[1]]);
 368                                 s4ptr += 2;
 369                             }
 370                         break;
 371
 372                 case ICMD_JSR:
 373                         c_last_jump = blockIndex;
 374                         dF_Exception(blockIndex, block_index[ip->op1]);
 375                         break;
 376
 377                 case ICMD_RET:
 378                         dF_Exception(blockIndex, c_last_jump+1);
 379                         break;
 380
 381                 default:
 382                         dF_Exception(blockIndex, blockIndex + 1);
 383                         break;
 384                     }
 385         }
 386 }
 387
 388
 389 /*
 390   Test function -> will be removed in final release
 391 */
 392 void resultPass1()
 393 {
 394         int i, j;
 395         struct depthElement *hp;
 396
 397         printf("\n\n****** PASS 1 ******\n\n");
 398         printf("Number of Nodes: %d\n\n", c_globalCount);
 399
 400         printf("Predecessors:\n");
 401         for (i=0; i<block_count; ++i) {
 402                 printf("Block %d:\t", i);
 403                 for (j=0; j<c_numPre[i]; ++j)
 404                         printf("%d ", c_pre[i][j]);
 405                 printf("\n");
 406         }
 407         printf("\n");
 408
 409         printf("Graph:\n");
 410         for (i=0; i<block_count; ++i) {
 411                 printf("Block %d:\t", i);
 412                 hp = c_dTable[i];
 413
 414                 while (hp != NULL) {
 415                         printf("%d ", hp->value);
 416                         hp = hp->next;
 417                     }
 418                 printf("\n");
 419             }
 420         printf("\n");
 421 }
 422
 423 /*
 424  * These are local overrides for various environment variables in Emacs.
 425  * Please do not remove this and leave it at the end of the file, where
 426  * Emacs will automagically detect them.
 427  * ---------------------------------------------------------------------
 428  * Local variables:
 429  * mode: c
 430  * indent-tabs-mode: t
 431  * c-basic-offset: 4
 432  * tab-width: 4
 433  * End:
 434  */