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