src/vm/jit/optimizing/lifetimes.c

   1 /* src/vm/jit/lsra.inc - lifetime anaylsis
   2
   3    Copyright (C) 2005, 2006 R. Grafl, A. Krall, C. Kruegel, C. Oates,
   4    R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
   5    C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
   6    Institut f. Computersprachen - TU Wien
   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: Christian Ullrich
  28
  29    $Id: lifetimes.c $
  30
  31 */
  32
  33 #include <stdio.h>
  34 #include <stdlib.h>
  35
  36 #include "mm/memory.h"
  37
  38 #include "toolbox/bitvector.h"
  39 #include "toolbox/worklist.h"
  40
  41 #include "vm/builtin.h"
  42 #include "vm/resolve.h"
  43 #include "vm/exceptions.h"
  44 #include "vm/stringlocal.h"
  45
  46 #include "vm/jit/jit.h"
  47
  48 #include "vm/jit/optimizing/graph.h"
  49 #include "vm/jit/optimizing/lsra.h"
  50 #include "vm/jit/optimizing/ssa.h"
  51 #include "vm/jit/optimizing/lifetimes.h"
  52
  53 #ifdef LT_DEBUG_VERBOSE
  54 #include "vmcore/options.h"
  55 #endif
  56
  57 #include <time.h>
  58 #include <errno.h>
  59
  60 /* function prototypes */
  61 void _lt_scanlifetimes(jitdata *jd, graphdata *gd, basicblock *bptr, int);
  62 void lt_usage(jitdata *, s4 , int , int , int );
  63
  64
  65 void lt_lifeoutatblock(lsradata *ls, graphdata *gd, int *M, int b_index,
  66                                            struct lifetime *lt, worklist *W);
  67 void lt_lifeatstatement(lsradata *ls, graphdata *gd, int b_index,
  68                                                 int iindex, struct lifetime *lt, bool life_in,
  69                                                 worklist *W);
  70 #if 0
  71 void lt_lifeinatstatement(lsradata *ls, graphdata *gd, int *M, int b_index,
  72                                            int iindex, struct lifetime *lt);
  73 void lt_lifeoutatstatement(lsradata *ls, graphdata *gd, int *M, int b_index,
  74                                                 int iindex, struct lifetime *lt);
  75 #endif
  76 #ifdef USAGE_COUNT
  77 void lt_get_nesting(lsradata *ls, graphdata *gd, dominatordata *dd);
  78 #endif
  79
  80 void lt_set_use_site(struct lifetime *lt, struct site *use_site) {
  81 }
  82
  83 struct site *lt_get_first_use_site(struct lifetime *lt, lt_iterator *iter) {
  84         return ((*iter) = lt->use);
  85 }
  86
  87 struct site *lt_get_next_site(lt_iterator *iter) {
  88         if ((*iter) == NULL)
  89                 return NULL;
  90         else
  91                 return ((*iter) = (*iter)->next);
  92 }
  93
  94 struct site *lt_get_first_def_site(struct lifetime *lt, lt_iterator *iter) {
  95         return ((*iter) = lt->def);
  96 }
  97
  98 bool lt_v_is_defined_at_s(lsradata *ls, int b_index, int iindex,
  99                                            struct lifetime * lt) {
 100         struct site *def_site;
 101         bool is_defined_at_s;
 102
 103         def_site = lt->def;
 104         is_defined_at_s = ((def_site->b_index == b_index)
 105                                            && (def_site->iindex == iindex));
 106         return is_defined_at_s;
 107 }
 108
 109 /****************************************************************************
 110 Get Def & Use Sites
 111 ****************************************************************************/
 112 void lt_scanlifetimes(jitdata *jd, graphdata *gd, dominatordata *dd) {
 113         int i, l, p;
 114         s4 t;
 115         methodinfo *m;
 116         lsradata *ls;
 117         methoddesc *md;
 118
 119         ls = jd->ls;
 120         m  = jd->m;
 121         md = m->parseddesc;
 122
 123         graph_DFS(ls, gd);
 124
 125 #ifdef USAGE_COUNT
 126         lt_get_nesting(ls, gd, dd);
 127 #endif
 128
 129 #if defined(LT_DEBUG_VERBOSE)
 130         if (compileverbose) {
 131                 printf("Sorted: ");
 132                 for (i=0; i < ls->basicblockcount; i++) {
 133                         l = ls->sorted[i];
 134                         if (l != -1)
 135                                 l = ls->basicblocks[l]->nr;
 136                         printf("%3i(%3i) ", ls->sorted[i], l);
 137                 }
 138                 printf("\n");
 139                 printf("Sorted_rev: ");
 140                 for (i=0; i < ls->basicblockcount; i++)
 141                         printf("%3i ", ls->sorted_rev[i]);
 142                 printf("\n");
 143         }
 144 #endif
 145
 146         for(i = ls->basicblockcount - 1; i>= 0; i--)
 147                 if (ls->sorted[i] != -1)
 148                         _lt_scanlifetimes(jd, gd, ls->basicblocks[ls->sorted[i]],
 149                                                           ls->sorted[i]);
 150
 151         /* Parameter initialisiation for locals [0 .. paramcount[            */
 152         /* -> add local var write access at (bb=0,iindex=0)                 */
 153
 154         for (p = 0, l = 0; p < md->paramcount; p++) {
 155                 t = md->paramtypes[p].type;
 156                 i = jd->local_map[l * 5 + t];
 157                 l++;
 158                 if (IS_2_WORD_TYPE(t))    /* increment local counter for 2 word types */
 159                         l++;
 160                 if (i == UNUSED)
 161                         continue;
 162                 i = ls->var_0[i];
 163 /*              _LT_ASSERT( i < jd->cd->maxlocals); */
 164 #ifdef LT_DEBUG_VERBOSE
 165                 if (compileverbose)
 166                         printf("param %3i -> L %3i/%3i",p,i,t);
 167 #endif
 168                 _LT_ASSERT(t == VAR(i)->type);
 169
 170                 /* Param to Local init happens before normal Code */
 171
 172 #ifdef LT_DEBUG_VERBOSE
 173                 if (compileverbose)
 174                         printf(" ok\n");
 175 #endif
 176                 lt_usage(jd, i, 0, 0, LT_DEF);
 177         }  /* end for */
 178 }
 179
 180
 181 bool lt_is_simple_lt(struct lifetime *lt) {
 182         lt_iterator i_def, i_use;
 183         struct site *def, *use;
 184         bool all_in_same_block;
 185
 186
 187         def = lt_get_first_def_site(lt, &i_def);
 188         use = lt_get_first_use_site(lt, &i_use);
 189         all_in_same_block = true;
 190         for (; (all_in_same_block && (use != NULL));
 191                  use = lt_get_next_site(&i_use)) {
 192                 all_in_same_block =
 193                         (use->iindex >= 0) && (use->b_index == def->b_index);
 194         }
 195         return all_in_same_block;
 196 }
 197
 198 void lt_is_live(lsradata *ls, struct lifetime *lt, int b_index, int iindex) {
 199         int bb_sorted;
 200
 201         bb_sorted = ls->sorted_rev[b_index];
 202
 203         if ((lt->bb_last_use < bb_sorted) ||
 204                 ((lt->bb_last_use == bb_sorted) && (lt->i_last_use < iindex))) {
 205                 lt->bb_last_use = bb_sorted;
 206                 lt->i_last_use  = iindex;
 207         }
 208         if ((lt->bb_first_def > bb_sorted) ||
 209                 ((lt->bb_first_def == bb_sorted) && (lt->i_first_def > iindex))) {
 210                 lt->bb_first_def = bb_sorted;
 211                 lt->i_first_def  = iindex;
 212         }
 213 }
 214
 215 void lt_set_simple_use(lsradata *ls, struct lifetime *lt) {
 216         lt_iterator i_use;
 217         struct site *use;
 218
 219         /* SAVEDVAR is nowhere set!!!! */
 220
 221         /* Def is first use */
 222 /*      lt->bb_first_def = ls->sorted_rev[lt->def->b_index]; */
 223 /*      lt->i_first_def = lt->def->iindex; */
 224
 225         lt_is_live(ls, lt, lt->def->b_index, lt->def->iindex);
 226
 227         /* get last use */
 228         use = lt_get_first_use_site(lt, &i_use);
 229 /*      lt->bb_last_use = ls->sorted_rev[use->b_index]; */
 230 /*      lt->i_last_use = use->iindex; */
 231         for (;  (use != NULL); use = lt_get_next_site(&i_use))
 232                 lt_is_live(ls, lt, use->b_index, use->iindex);
 233 /*              if (use->iindex > lt->i_last_use) */
 234 /*                      lt->i_last_use = use->iindex; */
 235 }
 236
 237 void lt_lifeness_analysis(jitdata *jd, graphdata *gd) {
 238         int *M;      /* bit_vecor of visited blocks */
 239         int *use;    /* bit_vecor of blocks with use sites visited */
 240         worklist *W; /* Worklist of Basic Blocks, where lt is life-out */
 241
 242         struct site *use_site, *u_site;
 243         lt_iterator iter, iter1;
 244         graphiterator pred_iter;
 245
 246         int lt_index, i, pred, iindex, iindex1, b_index;
 247         struct lifetime *lt;
 248         int *phi;
 249 /* #define MEASURE_RT */
 250 #ifdef MEASURE_RT
 251         struct timespec time_start,time_end;
 252 #endif
 253
 254         lsradata *ls;
 255         methodinfo *m;
 256
 257         ls = jd->ls;
 258         m  = jd->m;
 259
 260
 261 #ifdef MEASURE_RT
 262         if (clock_gettime(CLOCK_THREAD_CPUTIME_ID,&(time_start)) != 0) {
 263                 fprintf(stderr,"could not get time: %s\n",strerror(errno));
 264                 abort();
 265         }
 266 #endif
 267
 268         M   = bv_new(ls->basicblockcount);
 269         use = bv_new(ls->basicblockcount);
 270         W   = wl_new(ls->basicblockcount);
 271
 272 #ifdef LT_DEBUG_VERBOSE
 273         if (compileverbose)
 274         printf("LT_ANALYSE: \n");
 275 #endif
 276         for(lt_index = 0; lt_index < ls->lifetimecount; lt_index++) {
 277                 lt = &(ls->lifetime[lt_index]);
 278                 if (lt->type == -1)
 279                         continue;
 280 #ifdef LT_DEBUG_VERBOSE
 281         if (compileverbose)
 282                 printf("LT: %3i:", lt_index);
 283 #endif
 284
 285                 lt->savedvar = 0;
 286
 287                 _LT_ASSERT(lt->def != NULL);
 288                 _LT_ASSERT(lt->def->next == NULL); /* SSA! */
 289 /*              _LT_ASSERT(lt->use != NULL); */
 290
 291                 lt->bb_last_use = -1;
 292                 lt->bb_first_def = ls->basicblockcount;
 293
 294                 bv_reset(M, ls->basicblockcount);
 295                 bv_reset(use, ls->basicblockcount);
 296                 wl_reset(W, ls->basicblockcount);
 297
 298                 use_site = lt_get_first_use_site(lt, &iter);
 299
 300                 /* Make unused Vars life at their Def Site */
 301
 302                 if (use_site == NULL) {
 303                         lt_is_live(ls, lt, lt->def->b_index, lt->def->iindex);
 304                         if (lt->def->iindex < 0) {
 305
 306                                 /* def only in phi function */
 307
 308                                 lt_is_live(ls, lt, lt->def->b_index, 0);
 309                         }
 310                 }
 311                 for (;use_site != NULL; use_site = lt_get_next_site(&iter)) {
 312                         iindex  = use_site->iindex;
 313                         if ((lt->def->b_index == use_site->b_index) &&
 314                                 (iindex < 0) &&
 315                                 (iindex <= lt->def->iindex)) {
 316
 317 /*                              bv_set_bit(use, use_site->b_index); */
 318                                 /* do normal analysis */
 319                                 /* there is a use in a phi function before def site */
 320
 321                         }
 322                         else if (bv_get_bit(use, use_site->b_index)) {
 323                                 continue;
 324                         }
 325                         else {
 326                                 bv_set_bit(use, use_site->b_index);
 327
 328                                 /* use sites of this basic block not visited till now */
 329                                 /* get use site of this bb with highest iindex lower than */
 330                                 /* def site */
 331
 332                                 iindex1 = -1;
 333                                 u_site = use_site;
 334                                 for(iter1= iter; u_site != NULL;
 335                                         u_site = lt_get_next_site(&iter1)) {
 336                                         if ((u_site->b_index == use_site->b_index) &&
 337                                                 (lt->def->b_index == use_site->b_index) &&
 338                                                 (u_site->iindex >= 0) &&
 339                                                 (u_site->iindex < lt->def->iindex) &&
 340                                                 (u_site->iindex > iindex1)) {
 341                                                 iindex1 = u_site->iindex;
 342                                         } else {
 343                                                 if ((u_site->b_index == use_site->b_index) &&
 344                                                         (u_site->iindex > iindex))
 345                                                         iindex = u_site->iindex;
 346                                         }
 347                                 }
 348                                 if (iindex1 != -1)
 349                                         iindex = iindex1;
 350                         }
 351
 352 #ifdef LT_DEBUG_VERBOSE
 353         if (compileverbose)
 354                         printf("(%3i,%3i)", use_site->b_index, iindex);
 355 #endif
 356
 357                         if (iindex < 0) {
 358
 359                                 /* use in phi function */
 360                                 /* ls->phi[use_site->b_index][-use_site->iindex-1]*/
 361
 362                                 lt_is_live(ls, lt, use_site->b_index, iindex);
 363
 364                                 phi = ls->phi[use_site->b_index][-iindex-1];
 365                                 _LT_ASSERT(phi != NULL);
 366
 367                                         pred = graph_get_first_predecessor(gd, use_site->b_index,
 368                                                                                                            &pred_iter);
 369                                         for(i = 1; (pred != -1); i++,pred =
 370                                                         graph_get_next(&pred_iter))
 371                                                 if (lt->v_index == phi[i]) {
 372
 373                                                         /* Add "Life out Basic Blocks to Worklist */
 374
 375                                                         wl_add(W, pred);
 376                                                 }
 377                         }
 378                         else /* lt is live-in at this statement */
 379                                 lt_lifeatstatement(ls, gd, use_site->b_index,
 380                                                                    iindex, lt, true, W);
 381                 } /* for (;use_site != NULL; use_site = lt_get_next_site(&iter)) */
 382
 383                 /* process Worklist */
 384
 385                 while (!wl_is_empty(W)) {
 386                         b_index = wl_get(W);
 387                         lt_lifeoutatblock(ls, gd, M, b_index, lt, W);
 388                 }
 389
 390
 391 #ifdef LT_DEBUG_VERBOSE
 392                 if (compileverbose)
 393                         printf("\n");
 394 #endif
 395
 396         } /* for(lt_index = 0; lt_index < ls->lifetimecount; lt_index++) */
 397
 398 #ifdef MEASURE_RT
 399         if (clock_gettime(CLOCK_THREAD_CPUTIME_ID,&(time_end)) != 0) {
 400                 fprintf(stderr,"could not get time: %s\n",strerror(errno));
 401                 abort();
 402         }
 403
 404         {
 405                 long diff;
 406                 time_t atime;
 407
 408                 diff = (time_end.tv_nsec - time_start.tv_nsec) / 1000;
 409                 atime = time_start.tv_sec;
 410                 while (atime < time_end.tv_sec) {
 411                         atime++;
 412                         diff += 1000000;
 413                 }
 414                 printf("%8li %s.%s.%s\n",diff, m->class->name->text, m->name->text,
 415                            m->descriptor->text);
 416         }
 417 #endif
 418 }
 419
 420 /*******************************************************************************
 421 lt_lifeatstatement
 422
 423
 424 IN:     lsradata *ls    pointer to worklist created with wl_new
 425         graphdata *gd
 426         int b_index     Basic block index of instruction
 427         int iindex      index of instruction in Basic Block
 428         struct lifetime *lt  Pointer to lifetime structure
 429         bool life_in    TRUE  lifetime lt is life 'into' that instruction
 430                         FALSE lifetime lt is life 'out' of that instruction
 431
 432 IN/OUT: worklist *W     Worklist of Basic Blocks, where lt is life-out
 433 *******************************************************************************/
 434 void lt_lifeatstatement(lsradata *ls, graphdata *gd, int b_index,
 435                                                 int iindex, struct lifetime *lt, bool life_in,
 436                                                 worklist *W) {
 437
 438         int prev_iindex; /* Statement before iindex */
 439         int pred;
 440         graphiterator pred_iter;
 441         instruction *iptr;
 442
 443         while (true) {
 444                 if (!life_in) {
 445 #ifdef LT_DEBUG_VERBOSE
 446                         if ((compileverbose) && (iindex >= 0))
 447                                 printf("LO@ST: vi %3i bi %3i ii %3i\n",
 448                                            lt->v_index, b_index, iindex);
 449 #endif
 450
 451                         /* lt->v_index is life-out at statement at (b_index,iindex) */
 452
 453                         /* Once a interference graph is needed, add here an edge (v,w) */
 454                         /* to the ig, for each variable w defined at this instruction  */
 455                         /* except v=lt->v_index */
 456
 457                         if (!lt_v_is_defined_at_s(ls, b_index, iindex, lt)) {
 458
 459                                 /* v is life in at out of statement -> check if the SAVEDVAR */
 460                                 /* flag is needed to be set */
 461
 462                                 if ((iindex >= 0) && (b_index != 0)) {
 463
 464                                         /* real ICMD, no phi-function, no param initialisation */
 465
 466                                         _LT_ASSERT(ls->basicblocks[b_index]->iinstr != NULL);
 467                                         iptr = ls->basicblocks[b_index]->iinstr + iindex;
 468                                         if (icmd_table[iptr->opc].flags & ICMDTABLE_CALLS)
 469                                                 lt->savedvar = SAVEDVAR;
 470                                 }
 471
 472                                 /* lt stays life-in at statement */
 473
 474                                 life_in = true;
 475                         } else {
 476
 477                                 /* print LO verbose message only for phi functions, which */
 478                                 /* define this var */
 479
 480 #ifdef LT_DEBUG_VERBOSE
 481                                 if ((compileverbose) && (iindex < 0))
 482                                         printf("LO@ST: vi %3i bi %3i ii %3i\n",
 483                                                    lt->v_index, b_index, iindex);
 484                                 if ((compileverbose))
 485                                         printf("--> definition\n");
 486 #endif
 487
 488                                 lt_is_live(ls, lt, b_index, iindex);
 489
 490                                 /* Stop - lt is defined and not life before this instruction */
 491
 492                                 break;
 493                         }
 494                 }
 495
 496                 if (life_in) {
 497
 498                         /* lt->v_index is live-in at statement (b_index,iindex) */
 499
 500 #ifdef LT_DEBUG_VERBOSE
 501                         if ((compileverbose) && (iindex >= 0))
 502                                 printf("LI@ST: vi %3i bi %3i ii %3i\n",
 503                                            lt->v_index, b_index, iindex);
 504 #endif
 505
 506                         lt_is_live(ls, lt, b_index, iindex);
 507
 508
 509                         if (iindex == -ls->varcount-1) {
 510
 511 #ifdef LT_DEBUG_VERBOSE
 512                                 if ((compileverbose))
 513                                         printf("LI@ST: vi %3i bi %3i ii %3i\n",
 514                                                    lt->v_index, b_index, iindex);
 515 #endif
 516                                 /* iindex is the first statement of b_index */
 517                                 /* Statements -ls->max_vars-1 .. -1 are possible phi functions*/
 518                                 /* lt->v_index is live-in at b_index */
 519
 520                                 pred = graph_get_first_predecessor(gd, b_index, &pred_iter);
 521
 522                                 /* Add "Life out Basic Blocks to Worklist */
 523
 524                                 for(; pred != -1; pred = graph_get_next(&pred_iter))
 525                                         wl_add(W, pred);
 526
 527                                 /* Stop here - beginning of Basic Block reached */
 528
 529                                 break;
 530                         } else {
 531
 532                                 prev_iindex = iindex - 1;
 533                                 if (prev_iindex < 0)
 534
 535                                         /* look through phi functions */
 536
 537                                         for(; prev_iindex > -ls->varcount-1; prev_iindex--)
 538                                                 if (ls->phi[b_index][-prev_iindex-1] != NULL)
 539                                                         break;
 540
 541                                 /* lt is live out at instruction prev_iindex */
 542
 543                                 iindex = prev_iindex;
 544                                 life_in = false;
 545                         }
 546                 }
 547         }
 548 }
 549
 550
 551 void lt_lifeoutatblock(lsradata *ls, graphdata *gd, int *M, int b_index,
 552                                            struct lifetime *lt, worklist *W) {
 553
 554 #if defined(LT_DEBUG_VERBOSE)
 555         if (compileverbose) {
 556                 printf("V %3i LO at BB %3i\n",lt->v_index, b_index);
 557         }
 558 #endif
 559
 560         /* lt->v_index is life out of Block b_index */
 561         if (!bv_get_bit(M, b_index)) { /* BB b_index not visited till now */
 562                 bv_set_bit(M, b_index);
 563
 564                 /* lt->v_index is life out of last Statement of b_index */
 565
 566                 if (b_index != 0) {
 567                         int i;
 568                         i = ls->basicblocks[b_index]->icount - 1;
 569                         for (;((i>0) && (ls->basicblocks[b_index]->iinstr+i == ICMD_NOP));
 570                                  i--);
 571                         lt_lifeatstatement(ls, gd, b_index, i, lt, false, W);
 572                 }
 573                 else
 574                         lt_lifeatstatement(ls, gd, b_index, 0, lt, false, W);
 575         }
 576 }
 577
 578 void lt_move_use_sites(struct lifetime *from, struct lifetime *to) {
 579         struct site *s;
 580
 581         _LT_ASSERT(from->use != NULL);
 582         if (from->use == NULL)
 583                 return;
 584         for(s = from->use; s->next != NULL; s = s->next);
 585
 586         s->next = to->use;
 587         to->use = from->use;
 588         from->use = NULL;
 589 }
 590
 591 void lt_add_use_site(struct lifetime *lt, int block, int iindex) {
 592         struct site *n;
 593
 594         n = DNEW(struct site);
 595         n->b_index = block;
 596         n->iindex = iindex;
 597         n->next = lt->use;
 598         lt->use = n;
 599
 600         /* CFG is analysed from the end to the start -> so first found use site */
 601         /* is the last use of the Local Var */
 602
 603         if (lt->last_use == NULL)
 604                 lt->last_use = n;
 605 }
 606
 607 void lt_remove_use_site(struct lifetime *lt, int block, int iindex) {
 608         struct site *n;
 609
 610         /* check lt->use itself */
 611
 612         if ((lt->use->b_index == block) && (lt->use->iindex == iindex)) {
 613                 /* found */
 614                 lt->use = lt->use->next;
 615         } else {
 616
 617                 /* look through list */
 618
 619                 for (n = lt->use; (n->next != NULL) && ((n->next->b_index != block) ||
 620                                                                         (n->next->iindex != iindex)); n = n->next);
 621
 622                 /* assert, that lt was found */
 623
 624                 _LT_ASSERT(n->next != NULL);
 625                 _LT_ASSERT(n->next->b_index == block);
 626                 _LT_ASSERT(n->next->iindex == iindex);
 627
 628                 n->next = n->next->next;
 629         }
 630 }
 631
 632 void lt_add_def_site(struct lifetime *lt, int block, int iindex) {
 633         struct site *n;
 634
 635         /* SSA <-> only one definition per lifetime! */
 636
 637         _LT_ASSERT(lt->def == NULL);
 638         n = DNEW(struct site);
 639         n->b_index = block;
 640         n->iindex = iindex;
 641         n->next = NULL;
 642         lt->def = n;
 643 }
 644
 645 void lt_usage(jitdata *jd,s4 v_index, int block, int instr,
 646                                           int store)
 647 {
 648         struct lifetime *n;
 649         lsradata *ls;
 650
 651         ls = jd->ls;
 652
 653         n = ls->lifetime + v_index;
 654
 655         if (n->type == -1) { /* new local lifetime */
 656                 _LT_ASSERT(0);
 657                 n->v_index=v_index;
 658                 n->type=VAR(v_index)->type;
 659                 /* TODO: check!!!!  */
 660                 /* All var are SAVEDVARS or this gets reset afterwards???? */
 661                 n->savedvar = SAVEDVAR;
 662                 n->flags = 0;
 663                 n->usagecount = 0;
 664
 665                 n->bb_last_use = -1;
 666                 n->bb_first_def = -1;
 667
 668                 n->use = NULL;
 669                 n->def = NULL;
 670                 n->last_use = NULL;
 671         }
 672         _LT_ASSERT(VAR(v_index)->type == n->type);
 673
 674         /* add access at (block, instr) to instruction list */
 675         /* remember last USE, so only write, if USE Field is undefined (==-1)   */
 676         /* count store as use, too -> defined and not used vars would overwrite */
 677         /* other vars */
 678
 679         if (store == LT_USE) {
 680 #ifdef USAGE_COUNT
 681                 n->usagecount += ls->nesting[block];
 682 #endif
 683                 lt_add_use_site(n, block, instr);
 684         }
 685         if (store == LT_DEF) {
 686                 lt_add_def_site(n, block, instr);
 687         }
 688 }
 689
 690 /***************************************************************************
 691 use sites: dead code elemination, LifenessAnalysis
 692 def sites: dead code elemination
 693 ***************************************************************************/
 694 void _lt_scanlifetimes(jitdata *jd, graphdata *gd, basicblock *bptr,
 695                                            int b_index)
 696 {
 697 /*      methodinfo         *lm; */
 698         builtintable_entry *bte;
 699         methoddesc         *md;
 700         int i, j, t, v;
 701         int iindex/*, b_index*/;
 702         instruction *iptr;
 703         s4 *argp;
 704
 705         lsradata *ls;
 706
 707         ls = jd->ls;
 708
 709 #ifdef LT_DEBUG_VERBOSE
 710         if (compileverbose)
 711                 printf("_lt_scanlifetimes: BB %3i flags %3i\n", b_index, bptr->flags);
 712 #endif
 713
 714         if (bptr->flags >= BBREACHED) {
 715
 716 /*              b_index = bptr->nr; */
 717
 718                 /* get instruction count for BB */
 719
 720                 iindex = bptr->icount - 1;
 721
 722                 /* regard not setup new BB with maybe just in and outstack */
 723
 724                 if (iindex < 0)
 725                         iindex = 0;
 726
 727                 /* Regard phi_functions (Definition of target, Use of source) */
 728
 729                 for(i = 0; i < ls->ssavarcount; i++) {
 730                         if (ls->phi[b_index][i] != NULL) {
 731                                 /* Phi Function for var i at b_index exists */
 732                                 v = ls->phi[b_index][i][0];
 733                                 _LT_ASSERT( v != ls->varcount_with_indices);
 734                                 t = VAR(i)->type;
 735
 736                                 /* Add definition of target add - phi index -1*/
 737 #ifdef LT_DEBUG_VERBOSE
 738                                 if (compileverbose)
 739                                         printf("_lt_scanlifetimes: phi_def: v: %3i\n i: %3i\n",
 740                                                    v, -i-1);
 741 #endif
 742                                 lt_usage(jd, v, b_index, -i-1, LT_DEF);
 743
 744                                 /* Add Use of sources */
 745
 746                                 for (j = 1; j <= graph_get_num_predecessor(gd, b_index); j++) {
 747                                         if (ls->phi[b_index][i][j] != ls->varcount_with_indices)
 748                                                 if (ls->phi[b_index][i][j] != UNUSED)
 749                                                         lt_usage(jd, ls->phi[b_index][i][j], b_index,
 750                                                                          -i-1, LT_USE);
 751                                 }
 752                         }
 753                 }
 754
 755
 756                 if (bptr->iinstr != NULL) {
 757                         /* set iptr to last instruction of BB */
 758                         iptr = bptr->iinstr + iindex;
 759                 } else
 760                         iindex = -1;
 761
 762                 for (;iindex >= 0; iindex--, iptr--)  {
 763                         i = UNUSED;
 764                         v = UNUSED;
 765
 766                         if (icmd_table[iptr->opc].dataflow >= DF_DST_BASE)
 767                                 v = iptr->dst.varindex;
 768
 769                         /* check for use (s1, s2, s3 or special (argp) ) */
 770                         /* and definitions (dst) */
 771                         switch(icmd_table[iptr->opc].dataflow) {
 772                         case DF_3_TO_0:
 773                         case DF_3_TO_1: /* icmd has s1, s2 and s3 */
 774                                 lt_usage(jd, iptr->sx.s23.s3.varindex, b_index, iindex, LT_USE);
 775
 776                                 /* now "fall through" for handling of s2 and s1 */
 777
 778                         case DF_2_TO_0:
 779                         case DF_2_TO_1: /* icmd has s1 and s2 */
 780                                 lt_usage(jd, iptr->sx.s23.s2.varindex, b_index, iindex, LT_USE);
 781
 782                                 /* now "fall through" for handling of s1 */
 783
 784                         case DF_1_TO_0:
 785                         case DF_1_TO_1:
 786                         case DF_MOVE:
 787                         case DF_COPY: /* icmd has s1 */
 788                                 lt_usage(jd, iptr->s1.varindex, b_index, iindex, LT_USE);
 789                                 break;
 790
 791                         case DF_INVOKE:
 792                                 INSTRUCTION_GET_METHODDESC(iptr,md);
 793                                 i = md->paramcount;
 794                                 if (md->returntype.type == TYPE_VOID)
 795                                         v = UNUSED;
 796                                 break;
 797
 798                         case DF_BUILTIN:
 799                                 bte = iptr->sx.s23.s3.bte;
 800                                 md = bte->md;
 801                                 i = md->paramcount;
 802                                 if (md->returntype.type == TYPE_VOID)
 803                                         v = UNUSED;
 804                                 break;
 805
 806                         case DF_N_TO_1:
 807                                 i = iptr->s1.argcount;
 808                                 break;
 809
 810                         }
 811
 812                         if (i != UNUSED) {
 813                                 argp = iptr->sx.s23.s2.args;
 814                                 while (--i >= 0) {
 815                                         lt_usage(jd, *argp, b_index, iindex, LT_USE);
 816                                         argp++;
 817                                 }
 818                         }
 819
 820                         if (v != UNUSED) {
 821                                 lt_usage(jd, v, b_index, iindex, LT_DEF);
 822                         }
 823                 } /* for (;iindex >= 0; iindex--, iptr--) */
 824         } /* if (bptr->flags >= BBREACHED) */
 825 } /* scan_lifetimes */
 826
 827
 828 #ifdef USAGE_COUNT
 829 /*******************************************************************************
 830 true, if i dominates j
 831 *******************************************************************************/
 832 bool dominates(dominatordata *dd, int i, int j) {
 833         bool dominates = false;
 834
 835         while(!dominates && (dd->idom[j] != -1)) {
 836                 dominates = (i == dd->idom[j]);
 837                 j = dd->idom[j];
 838         }
 839         return dominates;
 840 }
 841
 842 /*******************************************************************************
 843 lt_get_nesting
 844
 845 Look for loops in the CFG and set the nesting depth of all Basicblocks in
 846 gd->nesting:
 847
 848 The Loop Header BB h is an element of DF[n] for all Basicblocks n of this loop
 849 So Look through all x element of DF[n] for a backedge n->x. If this
 850 exists, increment nesting for all n with x in DF[n]
 851 *******************************************************************************/
 852 void lt_get_nesting(lsradata *ls, graphdata *gd, dominatordata *dd) {
 853         int i, j, lh;
 854         bitvector loop_header;
 855         worklist *loop, *loop1;
 856
 857         int succ;
 858         graphiterator iter;
 859
 860         int num_loops;
 861
 862         int *loop_parent;
 863         int lh_p;
 864
 865         /* init nesting to 1 and get loop_headers */
 866         ls->nesting = DMNEW(long, ls->basicblockcount);
 867         loop_header = bv_new(ls->basicblockcount);
 868         loop = wl_new(ls->basicblockcount);
 869         num_loops = 0;
 870         for(i = 0; i < ls->basicblockcount; i++) {
 871                 ls->nesting[i] = 1;
 872
 873                 for(succ = graph_get_first_successor(gd, i, &iter); succ != -1;
 874                         succ = graph_get_next(&iter)) {
 875                         for (j = 0; j < dd->num_DF[i]; j++) {
 876                                 if (succ == dd->DF[i][j]) {
 877                                         /* There is an edge from i to DF[i][j] */
 878
 879                                         /* look if DF[i][j] dominates i -> backedge */
 880                                         if (dominates(dd, dd->DF[i][j], i)) {
 881                                                 /* this edge is a backedge */
 882                                                 /* -> DF[i][j] is a loop header */
 883                                                 _LT_CHECK_BOUNDS(dd->DF[i][j], 0, ls->basicblockcount);
 884                                                 if (!bv_get_bit(loop_header, dd->DF[i][j])) {
 885                                                         /* new loop_header found */
 886                                                         num_loops++;
 887                                                         bv_set_bit(loop_header, dd->DF[i][j]);
 888                                                         ls->nesting[dd->DF[i][j]] = 10;
 889                                                 }
 890                                                 wl_add(loop, dd->DF[i][j]);
 891                                         }
 892                                 }
 893                         }
 894                 }
 895         }
 896
 897         loop_parent = DMNEW(int , ls->basicblockcount);
 898         loop1 = wl_new(ls->basicblockcount);
 899
 900         /* look for direct parents of nested loopheaders */
 901         /* (DF[loop_header[i]] has the element loop_header[j] with i != j */
 902         /* TODO: BULLSHIT:unfortunately not such an easy condition ;( */
 903         while(!wl_is_empty(loop)) {
 904                 lh = wl_get(loop);
 905                 wl_add(loop1, lh);
 906
 907                 loop_parent[lh] = -1;
 908
 909                 for (j = 0; j < dd->num_DF[lh]; j++) {
 910                         _LT_CHECK_BOUNDS(dd->DF[lh][j], 0, ls->basicblockcount);
 911                         if (lh != dd->DF[lh][j]) {
 912                                 if (bv_get_bit(loop_header, dd->DF[lh][j])) {
 913 #ifdef LT_DEBUG_VERBOSE
 914                                         if (compileverbose)
 915                                                 if (loop_parent[lh] != -1)
 916                                                         printf("Warning: LoopHeader has more than one parent\n");
 917 #endif
 918 /*                                      _LT_ASSERT( loop_parent[lh] == -1); */
 919                                         loop_parent[lh] = dd->DF[lh][j];
 920                                 }
 921                         }
 922                 }
 923         }
 924
 925         /* create nesting for loopheaders */
 926         while(!wl_is_empty(loop1)) {
 927                 lh = wl_get(loop1);
 928                 for (lh_p = lh; lh_p != -1; lh_p = loop_parent[lh_p]) {
 929                         ls->nesting[lh] *= 10;
 930                 }
 931         }
 932
 933
 934         /* copy loopheader nesting to loop body */
 935         for(i = 0; i < ls->basicblockcount; i++) {
 936                 if (!bv_get_bit(loop_header, i)) {
 937                         /* Do not touch the nesting of a loopheader itself */
 938                         for(j = 0; j < dd->num_DF[i]; j++) {
 939                                 _LT_CHECK_BOUNDS(dd->DF[i][j], 0, ls->basicblockcount);
 940                                 if (bv_get_bit(loop_header, dd->DF[i][j])) {
 941                                         /* DF[i][j] is a loop header -> copy nesting for i */
 942 #ifdef LT_DEBUG_VERBOSE
 943                                         if (compileverbose)
 944                                                 if (ls->nesting[i] != 1)
 945                                                         printf("Warning: More than one loopheader for one BB\n");
 946 /*                                      _LT_ASSERT(ls->nesting[i] == 1); */
 947 #endif
 948                                         ls->nesting[i] = ls->nesting[dd->DF[i][j]];
 949                                 }
 950                         }
 951                 }
 952         }
 953
 954 #ifdef LT_DEBUG_VERBOSE
 955         if (compileverbose) {
 956                 printf("Num Loops: %3i\n",num_loops);
 957                 for(i = 0; i < ls->basicblockcount; i++)
 958                         printf("(BB%3i->N%3li) ",i, ls->nesting[i]);
 959                 printf("\n");
 960         }
 961 #endif
 962 }
 963 #endif
 964
 965
 966 /*
 967  * These are local overrides for various environment variables in Emacs.
 968  * Please do not remove this and leave it at the end of the file, where
 969  * Emacs will automagically detect them.
 970  * ---------------------------------------------------------------------
 971  * Local variables:
 972  * mode: c
 973  * indent-tabs-mode: t
 974  * c-basic-offset: 4
 975  * tab-width: 4
 976  * End:
 977  */