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