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