narray/graph.c

   1 /* graph.c *********************************************************************
   2
   3         Copyright (c) 1997 A. Krall, R. Grafl, M. Gschwind, M. Probst
   4
   5         See file COPYRIGHT for information on usage and disclaimer of warranties.
   6
   7         Contains the functions which build a list, that represents the control
   8                 flow graph of the procedure, that is being analyzed.
   9
  10         Authors: Christopher Kruegel      EMAIL: cacao@complang.tuwien.ac.at
  11
  12         Last Change: 1998/17/02
  13
  14 *******************************************************************************/
  15
  16 void dF(int from, int blockIndex);
  17
  18 void LoopContainerInit(struct LoopContainer *lc, int i)
  19 {
  20         struct LoopElement *le = DMNEW(struct LoopElement, 1);
  21
  22         le->next = NULL;
  23
  24         lc->parent = NULL;
  25
  26         lc->tree_right = NULL;
  27         lc->tree_down = NULL;
  28
  29         lc->exceptions = NULL;
  30
  31         lc->in_degree = 0;
  32         le->node = lc->loop_head = i;
  33         le->block = &block[i];
  34
  35         /* lc->nodes = (int *) malloc(sizeof(int)*block_count);
  36         lc->nodes[0] = i; */
  37
  38         lc->nodes = le;
  39 }
  40
  41 /*      depthFirst() builds the control flow graph out of the intermediate code of
  42         the procedure, that is to be optimized and stores the list in the global
  43         variable c_dTable
  44 */
  45 void depthFirst()
  46 {
  47         int i, j;
  48         struct depthElement *hp;
  49
  50 /*      allocate memory and init gobal variables needed by function dF(int, int)        */
  51
  52         if ((c_defnum = (int *) malloc(block_count * sizeof(int))) == NULL)
  53                 c_mem_error();
  54         if ((c_numPre = (int *) malloc(block_count * sizeof(int))) == NULL)
  55                 c_mem_error();
  56         if ((c_parent = (int *) malloc(block_count * sizeof(int))) == NULL)
  57                 c_mem_error();
  58         if ((c_reverse = (int *) malloc(block_count * sizeof(int))) == NULL)
  59                 c_mem_error();
  60
  61         if ((c_pre = (int **) malloc(block_count * sizeof(int *))) == NULL)
  62                 c_mem_error();
  63
  64         if ((c_dTable = (struct depthElement **) malloc(block_count * sizeof(struct depthElement *))) == NULL)
  65                 c_mem_error();
  66
  67         for (i = 0; i < block_count; ++i) {
  68                 c_defnum[i] = c_parent[i] = -1;
  69                 c_numPre[i] = c_reverse[i] = 0;
  70
  71                 if ((c_pre[i] = (int *) malloc(block_count * sizeof(int))) == NULL)
  72                         c_mem_error();
  73                 c_dTable[i] = NULL;
  74             }
  75
  76         c_globalCount = 0;
  77         c_allLoops = NULL;
  78
  79         dF(-1, 0);      /* call helper function dF that traverses basic block structure */
  80 }
  81
  82 /*      dF starts from the first block of the given procedure and traverses the
  83         control flow graph in a depth-first order, thereby building up the adeacency
  84         list c_dTable
  85 */
  86 void dF(int from, int blockIndex)
  87 {
  88         instruction *ip;
  89         s4 *s4ptr;
  90         int high, low, count;
  91         struct depthElement *hp;
  92         struct LoopContainer *tmp;
  93         int cnt, *ptr;
  94
  95         if (from >= 0) {
  96 /*      the current basic block has a predecessor (ie. is not the first one)            */
  97                 if ((hp = (struct depthElement *) malloc(sizeof(struct depthElement))) == NULL)
  98                         c_mem_error();                  /* cretae new depth element                                     */
  99
 100                 hp->next = c_dTable[from];      /* insert values                                                        */
 101                 hp->value = blockIndex;
 102                 hp->changes = NULL;
 103
 104                 c_dTable[from] = hp;    /* insert into table                                                    */
 105             }
 106
 107         if (from == blockIndex) {       /* insert one node loops into loop container    */
 108                 if ((tmp = (struct LoopContainer *) malloc(sizeof(struct LoopContainer))) == NULL)
 109                         c_mem_error();
 110                 LoopContainerInit(tmp, blockIndex);
 111                 tmp->next = c_allLoops;
 112                 c_allLoops = tmp;
 113             }
 114
 115 #ifdef C_DEBUG
 116         if (blockIndex > block_count) {
 117                 fprintf(stderr, "DepthFirst: BlockIndex exceeded\n");
 118                 exit(1);
 119                 }
 120 #endif
 121
 122         ip = block[blockIndex].iinstr + block[blockIndex].icount -1;
 123                                                                                 /* set ip to last instruction                   */
 124
 125         if (c_defnum[blockIndex] == -1) {       /* current block has not been visited   */
 126             c_defnum[blockIndex] = c_globalCount;       /* update global count                  */
 127             c_parent[blockIndex] = from;        /* write parent block of current one    */
 128                 c_reverse[c_globalCount] = blockIndex;
 129                 ++c_globalCount;
 130
 131                 if (!block[blockIndex].icount) {
 132                                                                                 /* block does not contain instructions  */
 133                         dF(blockIndex, blockIndex+1);
 134                     }
 135                 else {                                                  /* for all successors, do                               */
 136                         switch (ip->opc) {                      /* check type of last instruction               */
 137                         case ICMD_RETURN:
 138                         case ICMD_IRETURN:
 139                         case ICMD_LRETURN:
 140                         case ICMD_FRETURN:
 141                         case ICMD_DRETURN:
 142                         case ICMD_ARETURN:
 143                         case ICMD_ATHROW:
 144                                 break;                                  /* function returns -> end of graph             */
 145
 146                         case ICMD_IFEQ:
 147                         case ICMD_IFNE:
 148                         case ICMD_IFLT:
 149                         case ICMD_IFGE:
 150                         case ICMD_IFGT:
 151                         case ICMD_IFLE:
 152                         case ICMD_IFNULL:
 153                         case ICMD_IFNONNULL:
 154                         case ICMD_IF_ICMPEQ:
 155                         case ICMD_IF_ICMPNE:
 156                         case ICMD_IF_ICMPLT:
 157                         case ICMD_IF_ICMPGE:
 158                         case ICMD_IF_ICMPGT:
 159                         case ICMD_IF_ICMPLE:
 160                         case ICMD_IF_ACMPEQ:
 161                         case ICMD_IF_ACMPNE:                            /* branch -> check next block   */
 162                            dF(blockIndex, blockIndex + 1);
 163                            /* fall throu */
 164
 165                         case ICMD_GOTO:
 166                                 dF(blockIndex, block_index[ip->op1]);
 167                                 break;                                                  /* visit branch (goto) target   */
 168
 169                         case ICMD_TABLESWITCH:                          /* switch statement                             */
 170                                 s4ptr = ip->val.a;
 171
 172                                 dF(blockIndex, block_index[*s4ptr]);    /* default branch               */
 173
 174                                 s4ptr++;
 175                                 low = *s4ptr;
 176                                 s4ptr++;
 177                                 high = *s4ptr;
 178
 179                                 count = (high-low+1);
 180
 181                                 while (--count >= 0) {
 182                                         s4ptr++;
 183                                         dF(blockIndex, block_index[*s4ptr]);
 184                                     }
 185                                 break;
 186
 187                         case ICMD_LOOKUPSWITCH:                         /* switch statement                             */
 188                                 s4ptr = ip->val.a;
 189
 190                                 dF(blockIndex, block_index[*s4ptr]);    /* default branch               */
 191
 192                                 ++s4ptr;
 193                                 count = *s4ptr++;
 194
 195                                 while (--count >= 0) {
 196                                         dF(blockIndex, block_index[s4ptr[1]]);
 197                                         s4ptr += 2;
 198                                     }
 199                                 break;
 200
 201                         case ICMD_JSR:
 202                                 c_last_jump = blockIndex;
 203                                 dF(blockIndex, block_index[ip->op1]);
 204                                 break;
 205
 206                         case ICMD_RET:
 207                                 dF(blockIndex, c_last_jump+1);
 208                                 break;
 209
 210                         default:
 211                                 dF(blockIndex, blockIndex + 1);
 212                                 break;
 213                             }
 214                     }
 215             }
 216
 217         for (ptr = c_pre[blockIndex], cnt = 0; cnt < c_numPre[blockIndex]; ++cnt, ++ptr)
 218         {
 219                 if (*ptr == from)
 220                         break;
 221         }
 222
 223         if (cnt >= c_numPre[blockIndex]) {
 224                 c_pre[blockIndex][c_numPre[blockIndex]] = from;
 225                                                     /* add predeccessors to list c_pre          */
 226                 c_numPre[blockIndex]++;                         /* increase number of predecessors      */
 227             }
 228
 229 }
 230
 231 /* a slightly modified version of dF(int, int) that is used to traverse the part
 232    of the control graph that is not reached by normal program flow but by the
 233    raising of exceptions (code of catch blocks)
 234 */
 235 void dF_Exception(int from, int blockIndex)
 236 {
 237         instruction *ip;
 238         s4 *s4ptr;
 239         int high, low, count;
 240         struct depthElement *hp;
 241         struct LoopContainer *tmp;
 242
 243         if (c_exceptionVisit[blockIndex] < 0)   /* has block been visited, return       */
 244                 c_exceptionVisit[blockIndex] = 1;
 245         else
 246                 return;
 247
 248         if (c_dTable[blockIndex] != NULL)               /* back to regular code section         */
 249                 return;
 250
 251         if (from >= 0) {                /* build exception graph (in c_exceptionGraph)          */
 252             if ((hp = (struct depthElement *) malloc(sizeof(struct depthElement))) == NULL)
 253                         c_mem_error();
 254
 255                 hp->next = c_exceptionGraph[from];
 256                 hp->value = blockIndex;
 257                 hp->changes = NULL;
 258
 259                 c_exceptionGraph[from] = hp;
 260             }
 261
 262 #ifdef C_DEBUG
 263         if (blockIndex > block_count) {
 264                 fprintf(stderr, "DepthFirst: BlockIndex exceeded\n");
 265                 exit(1);
 266         }
 267 #endif
 268
 269         ip = block[blockIndex].iinstr + block[blockIndex].icount -1;
 270
 271         if (!block[blockIndex].icount)
 272                 dF_Exception(blockIndex, blockIndex+1);
 273         else {
 274                 switch (ip->opc) {
 275                 case ICMD_RETURN:
 276                 case ICMD_IRETURN:
 277                 case ICMD_LRETURN:
 278                 case ICMD_FRETURN:
 279                 case ICMD_DRETURN:
 280                 case ICMD_ARETURN:
 281                 case ICMD_ATHROW:
 282                         break;
 283
 284                 case ICMD_IFEQ:
 285                 case ICMD_IFNE:
 286                 case ICMD_IFLT:
 287                 case ICMD_IFGE:
 288                 case ICMD_IFGT:
 289                 case ICMD_IFLE:
 290                 case ICMD_IFNULL:
 291                 case ICMD_IFNONNULL:
 292                 case ICMD_IF_ICMPEQ:
 293                 case ICMD_IF_ICMPNE:
 294                 case ICMD_IF_ICMPLT:
 295                 case ICMD_IF_ICMPGE:
 296                 case ICMD_IF_ICMPGT:
 297                 case ICMD_IF_ICMPLE:
 298                 case ICMD_IF_ACMPEQ:
 299                 case ICMD_IF_ACMPNE:
 300                         dF_Exception(blockIndex, blockIndex + 1);
 301                         /* fall throu */
 302
 303                 case ICMD_GOTO:
 304                         dF_Exception(blockIndex, block_index[ip->op1]);
 305                         break;
 306
 307                 case ICMD_TABLESWITCH:
 308                         s4ptr = ip->val.a;
 309
 310                         /* default branch */
 311                         dF_Exception(blockIndex, block_index[*s4ptr]);
 312
 313                         s4ptr++;
 314                         low = *s4ptr;
 315                         s4ptr++;
 316                         high = *s4ptr;
 317
 318                         count = (high-low+1);
 319
 320                         while (--count >= 0) {
 321                                 s4ptr++;
 322                                 dF_Exception(blockIndex, block_index[*s4ptr]);
 323                             }
 324                         break;
 325
 326                 case ICMD_LOOKUPSWITCH:
 327                         s4ptr = ip->val.a;
 328
 329                         /* default branch */
 330                         dF_Exception(blockIndex, block_index[*s4ptr]);
 331
 332                         ++s4ptr;
 333                         count = *s4ptr++;
 334
 335                         while (--count >= 0) {
 336                                 dF_Exception(blockIndex, block_index[s4ptr[1]]);
 337                                 s4ptr += 2;
 338                             }
 339                         break;
 340
 341                 case ICMD_JSR:
 342                         c_last_jump = blockIndex;
 343                         dF_Exception(blockIndex, block_index[ip->op1]);
 344                         break;
 345
 346                 case ICMD_RET:
 347                         dF_Exception(blockIndex, c_last_jump+1);
 348                         break;
 349
 350                 default:
 351                         dF_Exception(blockIndex, blockIndex + 1);
 352                         break;
 353                     }
 354         }
 355 }
 356
 357 /*      Test function -> will be removed in final release
 358 */
 359 void resultPass1()
 360 {
 361         int i, j;
 362         struct depthElement *hp;
 363
 364         printf("\n\n****** PASS 1 ******\n\n");
 365         printf("Number of Nodes: %d\n\n", c_globalCount);
 366
 367         printf("Predecessors:\n");
 368         for (i=0; i<block_count; ++i) {
 369                 printf("Block %d:\t", i);
 370                 for (j=0; j<c_numPre[i]; ++j)
 371                         printf("%d ", c_pre[i][j]);
 372                 printf("\n");
 373         }
 374         printf("\n");
 375
 376         printf("Graph:\n");
 377         for (i=0; i<block_count; ++i) {
 378                 printf("Block %d:\t", i);
 379                 hp = c_dTable[i];
 380
 381                 while (hp != NULL) {
 382                         printf("%d ", hp->value);
 383                         hp = hp->next;
 384                     }
 385                 printf("\n");
 386             }
 387         printf("\n");
 388 }
 389
 390 /*
 391  * These are local overrides for various environment variables in Emacs.
 392  * Please do not remove this and leave it at the end of the file, where
 393  * Emacs will automagically detect them.
 394  * ---------------------------------------------------------------------
 395  * Local variables:
 396  * mode: c
 397  * indent-tabs-mode: t
 398  * c-basic-offset: 4
 399  * tab-width: 4
 400  * End:
 401  */