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 /*                      printf("param %3i -> L %3i/%3i\n",p,i,t); */
 165                 _LT_ASSERT(t == VAR(i)->type);
 166
 167                 /* Param to Local init happens before normal Code */
 168
 169 #ifdef LT_DEBUG_VERBOSE
 170                 if (compileverbose)
 171                         printf(" ok\n");
 172 #endif
 173                 lt_usage(jd, i, 0, 0, LT_DEF);
 174         }  /* end for */
 175 }
 176
 177
 178 bool lt_is_simple_lt(struct lifetime *lt) {
 179         lt_iterator i_def, i_use;
 180         struct site *def, *use;
 181         bool all_in_same_block;
 182
 183
 184         def = lt_get_first_def_site(lt, &i_def);
 185         use = lt_get_first_use_site(lt, &i_use);
 186         all_in_same_block = true;
 187         for (; (all_in_same_block && (use != NULL));
 188                  use = lt_get_next_site(&i_use)) {
 189                 all_in_same_block =
 190                         (use->iindex >= 0) && (use->b_index == def->b_index);
 191         }
 192         return all_in_same_block;
 193 }
 194
 195 void lt_is_live(lsradata *ls, struct lifetime *lt, int b_index, int iindex) {
 196         int bb_sorted;
 197
 198         bb_sorted = ls->sorted_rev[b_index];
 199
 200         if ((lt->bb_last_use < bb_sorted) ||
 201                 ((lt->bb_last_use == bb_sorted) && (lt->i_last_use < iindex))) {
 202                 lt->bb_last_use = bb_sorted;
 203                 lt->i_last_use  = iindex;
 204         }
 205         if ((lt->bb_first_def > bb_sorted) ||
 206                 ((lt->bb_first_def == bb_sorted) && (lt->i_first_def > iindex))) {
 207                 lt->bb_first_def = bb_sorted;
 208                 lt->i_first_def  = iindex;
 209         }
 210 }
 211
 212 void lt_set_simple_use(lsradata *ls, struct lifetime *lt) {
 213         lt_iterator i_use;
 214         struct site *use;
 215
 216         /* SAVEDVAR is nowhere set!!!! */
 217
 218         /* Def is first use */
 219 /*      lt->bb_first_def = ls->sorted_rev[lt->def->b_index]; */
 220 /*      lt->i_first_def = lt->def->iindex; */
 221
 222         lt_is_live(ls, lt, lt->def->b_index, lt->def->iindex);
 223
 224         /* get last use */
 225         use = lt_get_first_use_site(lt, &i_use);
 226 /*      lt->bb_last_use = ls->sorted_rev[use->b_index]; */
 227 /*      lt->i_last_use = use->iindex; */
 228         for (;  (use != NULL); use = lt_get_next_site(&i_use))
 229                 lt_is_live(ls, lt, use->b_index, use->iindex);
 230 /*              if (use->iindex > lt->i_last_use) */
 231 /*                      lt->i_last_use = use->iindex; */
 232 }
 233
 234 void lt_lifeness_analysis(jitdata *jd, graphdata *gd) {
 235         int *M;      /* bit_vecor of visited blocks */
 236         int *use;    /* bit_vecor of blocks with use sites visited */
 237         worklist *W; /* Worklist of Basic Blocks, where lt is life-out */
 238
 239         struct site *use_site, *u_site;
 240         lt_iterator iter, iter1;
 241         graphiterator pred_iter;
 242
 243         int lt_index, i, pred, iindex, iindex1, b_index;
 244         struct lifetime *lt;
 245         int *phi;
 246 /* #define MEASURE_RT */
 247 #ifdef MEASURE_RT
 248         struct timespec time_start,time_end;
 249 #endif
 250
 251         lsradata *ls;
 252         methodinfo *m;
 253
 254         ls = jd->ls;
 255         m  = jd->m;
 256
 257
 258 #ifdef MEASURE_RT
 259         if (clock_gettime(CLOCK_THREAD_CPUTIME_ID,&(time_start)) != 0) {
 260                 fprintf(stderr,"could not get time: %s\n",strerror(errno));
 261                 abort();
 262         }
 263 #endif
 264
 265         M   = bv_new(ls->basicblockcount);
 266         use = bv_new(ls->basicblockcount);
 267         W   = wl_new(ls->basicblockcount);
 268
 269 #ifdef LT_DEBUG_VERBOSE
 270         if (compileverbose)
 271         printf("LT_ANALYSE: \n");
 272 #endif
 273         for(lt_index = 0; lt_index < ls->lifetimecount; lt_index++) {
 274                 lt = &(ls->lifetime[lt_index]);
 275                 if (lt->type == -1)
 276                         continue;
 277 #ifdef LT_DEBUG_VERBOSE
 278         if (compileverbose)
 279                 printf("LT: %3i:", lt_index);
 280 #endif
 281
 282                 lt->savedvar = 0;
 283
 284                 _LT_ASSERT(lt->def != NULL);
 285                 _LT_ASSERT(lt->def->next == NULL); /* SSA! */
 286 /*              _LT_ASSERT(lt->use != NULL); */
 287
 288                 lt->bb_last_use = -1;
 289                 lt->bb_first_def = ls->basicblockcount;
 290
 291                 bv_reset(M, ls->basicblockcount);
 292                 bv_reset(use, ls->basicblockcount);
 293                 wl_reset(W, ls->basicblockcount);
 294
 295                 use_site = lt_get_first_use_site(lt, &iter);
 296
 297                 /* Make unused Vars life at their Def Site */
 298
 299                 if (use_site == NULL) {
 300                         lt_is_live(ls, lt, lt->def->b_index, lt->def->iindex);
 301                         if (lt->def->iindex < 0) {
 302
 303                                 /* def only in phi function */
 304
 305                                 lt_is_live(ls, lt, lt->def->b_index, 0);
 306                         }
 307                 }
 308                 for (;use_site != NULL; use_site = lt_get_next_site(&iter)) {
 309                         iindex  = use_site->iindex;
 310                         if ((lt->def->b_index == use_site->b_index) &&
 311                                 (iindex < 0) &&
 312                                 (iindex <= lt->def->iindex)) {
 313
 314 /*                              bv_set_bit(use, use_site->b_index); */
 315                                 /* do normal analysis */
 316                                 /* there is a use in a phi function before def site */
 317
 318                         }
 319                         else if (bv_get_bit(use, use_site->b_index)) {
 320                                 continue;
 321                         }
 322                         else {
 323                                 bv_set_bit(use, use_site->b_index);
 324
 325                                 /* use sites of this basic block not visited till now */
 326                                 /* get use site of this bb with highest iindex lower than */
 327                                 /* def site */
 328
 329                                 iindex1 = -1;
 330                                 u_site = use_site;
 331                                 for(iter1= iter; u_site != NULL;
 332                                         u_site = lt_get_next_site(&iter1)) {
 333                                         if ((u_site->b_index == use_site->b_index) &&
 334                                                 (lt->def->b_index == use_site->b_index) &&
 335                                                 (u_site->iindex >= 0) &&
 336                                                 (u_site->iindex < lt->def->iindex) &&
 337                                                 (u_site->iindex > iindex1)) {
 338                                                 iindex1 = u_site->iindex;
 339                                         } else {
 340                                                 if ((u_site->b_index == use_site->b_index) &&
 341                                                         (u_site->iindex > iindex))
 342                                                         iindex = u_site->iindex;
 343                                         }
 344                                 }
 345                                 if (iindex1 != -1)
 346                                         iindex = iindex1;
 347                         }
 348
 349 #ifdef LT_DEBUG_VERBOSE
 350         if (compileverbose)
 351                         printf("(%3i,%3i)", use_site->b_index, iindex);
 352 #endif
 353
 354                         if (iindex < 0) {
 355
 356                                 /* use in phi function */
 357                                 /* ls->phi[use_site->b_index][-use_site->iindex-1]*/
 358
 359                                 lt_is_live(ls, lt, use_site->b_index, iindex);
 360
 361                                 phi = ls->phi[use_site->b_index][-iindex-1];
 362                                 _LT_ASSERT(phi != NULL);
 363
 364                                         pred = graph_get_first_predecessor(gd, use_site->b_index,
 365                                                                                                            &pred_iter);
 366                                         for(i = 1; (pred != -1); i++,pred =
 367                                                         graph_get_next(&pred_iter))
 368                                                 if (lt->v_index == phi[i]) {
 369
 370                                                         /* Add "Life out Basic Blocks to Worklist */
 371
 372                                                         wl_add(W, pred);
 373                                                 }
 374                         }
 375                         else /* lt is live-in at this statement */
 376                                 lt_lifeatstatement(ls, gd, use_site->b_index,
 377                                                                    iindex, lt, true, W);
 378                 } /* for (;use_site != NULL; use_site = lt_get_next_site(&iter)) */
 379
 380                 /* process Worklist */
 381
 382                 while (!wl_is_empty(W)) {
 383                         b_index = wl_get(W);
 384                         lt_lifeoutatblock(ls, gd, M, b_index, lt, W);
 385                 }
 386
 387
 388 #ifdef LT_DEBUG_VERBOSE
 389                 if (compileverbose)
 390                         printf("\n");
 391 #endif
 392
 393         } /* for(lt_index = 0; lt_index < ls->lifetimecount; lt_index++) */
 394
 395 #ifdef MEASURE_RT
 396         if (clock_gettime(CLOCK_THREAD_CPUTIME_ID,&(time_end)) != 0) {
 397                 fprintf(stderr,"could not get time: %s\n",strerror(errno));
 398                 abort();
 399         }
 400
 401         {
 402                 long diff;
 403                 time_t atime;
 404
 405                 diff = (time_end.tv_nsec - time_start.tv_nsec) / 1000;
 406                 atime = time_start.tv_sec;
 407                 while (atime < time_end.tv_sec) {
 408                         atime++;
 409                         diff += 1000000;
 410                 }
 411                 printf("%8li %s.%s.%s\n",diff, m->class->name->text, m->name->text,
 412                            m->descriptor->text);
 413         }
 414 #endif
 415 }
 416
 417 /*******************************************************************************
 418 lt_lifeatstatement
 419
 420
 421 IN:     lsradata *ls    pointer to worklist created with wl_new
 422         graphdata *gd
 423         int b_index     Basic block index of instruction
 424         int iindex      index of instruction in Basic Block
 425         struct lifetime *lt  Pointer to lifetime structure
 426         bool life_in    TRUE  lifetime lt is life 'into' that instruction
 427                         FALSE lifetime lt is life 'out' of that instruction
 428
 429 IN/OUT: worklist *W     Worklist of Basic Blocks, where lt is life-out
 430 *******************************************************************************/
 431 void lt_lifeatstatement(lsradata *ls, graphdata *gd, int b_index,
 432                                                 int iindex, struct lifetime *lt, bool life_in,
 433                                                 worklist *W) {
 434
 435         int prev_iindex; /* Statement before iindex */
 436         int pred;
 437         graphiterator pred_iter;
 438         instruction *iptr;
 439
 440         while (true) {
 441                 if (!life_in) {
 442 #ifdef LT_DEBUG_VERBOSE
 443                         if ((compileverbose) && (iindex >= 0))
 444                                 printf("LO@ST: vi %3i bi %3i ii %3i\n",
 445                                            lt->v_index, b_index, iindex);
 446 #endif
 447
 448                         /* lt->v_index is life-out at statement at (b_index,iindex) */
 449
 450                         /* Once a interference graph is needed, add here an edge (v,w) */
 451                         /* to the ig, for each variable w defined at this instruction  */
 452                         /* except v=lt->v_index */
 453
 454                         if (!lt_v_is_defined_at_s(ls, b_index, iindex, lt)) {
 455
 456                                 /* v is life in at out of statement -> check if the SAVEDVAR */
 457                                 /* flag is needed to be set */
 458
 459                                 if ((iindex >= 0) && (b_index != 0)) {
 460
 461                                         /* real ICMD, no phi-function, no param initialisation */
 462
 463                                         _LT_ASSERT(ls->basicblocks[b_index]->iinstr != NULL);
 464
 465                                         iptr = ls->basicblocks[b_index]->iinstr + iindex;
 466                                         if (icmd_table[iptr->opc].flags & ICMDTABLE_CALLS)
 467                                                 lt->savedvar = SAVEDVAR;
 468                                 }
 469
 470                                 /* lt stays life-in at statement */
 471
 472                                 life_in = true;
 473                         } else {
 474
 475                                 /* print LO verbose message only for phi functions, which */
 476                                 /* define this var */
 477
 478 #ifdef LT_DEBUG_VERBOSE
 479                                 if ((compileverbose) && (iindex < 0))
 480                                         printf("LO@ST: vi %3i bi %3i ii %3i\n",
 481                                                    lt->v_index, b_index, iindex);
 482                                 if ((compileverbose))
 483                                         printf("--> definition\n");
 484 #endif
 485
 486                                 lt_is_live(ls, lt, b_index, iindex);
 487
 488                                 /* Stop - lt is defined and not life before this instruction */
 489
 490                                 break;
 491                         }
 492                 }
 493
 494                 if (life_in) {
 495
 496                         /* lt->v_index is live-in at statement (b_index,iindex) */
 497
 498 #ifdef LT_DEBUG_VERBOSE
 499                         if ((compileverbose) && (iindex >= 0))
 500                                 printf("LI@ST: vi %3i bi %3i ii %3i\n",
 501                                            lt->v_index, b_index, iindex);
 502 #endif
 503
 504                         lt_is_live(ls, lt, b_index, iindex);
 505
 506
 507                         if (iindex == -ls->ssavarcount-1) {
 508
 509 #ifdef LT_DEBUG_VERBOSE
 510                                 if ((compileverbose))
 511                                         printf("LI@ST: vi %3i bi %3i ii %3i\n",
 512                                                    lt->v_index, b_index, iindex);
 513 #endif
 514                                 /* iindex is the first statement of b_index */
 515                                 /* Statements -ls->ssavarcounts-1 .. -1 are possible phi functions*/
 516                                 /* lt->v_index is live-in at b_index */
 517
 518                                 pred = graph_get_first_predecessor(gd, b_index, &pred_iter);
 519
 520                                 /* Add "Life out Basic Blocks to Worklist */
 521
 522                                 for(; pred != -1; pred = graph_get_next(&pred_iter))
 523                                         wl_add(W, pred);
 524
 525                                 /* Stop here - beginning of Basic Block reached */
 526
 527                                 break;
 528                         } else {
 529
 530                                 prev_iindex = iindex - 1;
 531                                 if (prev_iindex < 0)
 532
 533                                         /* look through phi functions */
 534
 535                                         for(; prev_iindex > -ls->ssavarcount-1; prev_iindex--)
 536                                                 if (ls->phi[b_index][-prev_iindex-1] != NULL)
 537                                                         break;
 538
 539                                 /* lt is live out at instruction prev_iindex */
 540
 541                                 iindex = prev_iindex;
 542                                 life_in = false;
 543                         }
 544                 }
 545         }
 546 }
 547
 548
 549 void lt_lifeoutatblock(lsradata *ls, graphdata *gd, int *M, int b_index,
 550                                            struct lifetime *lt, worklist *W) {
 551
 552 #if defined(LT_DEBUG_VERBOSE)
 553         if (compileverbose) {
 554                 printf("V %3i LO at BB %3i\n",lt->v_index, b_index);
 555         }
 556 #endif
 557
 558         /* lt->v_index is life out of Block b_index */
 559         if (!bv_get_bit(M, b_index)) { /* BB b_index not visited till now */
 560                 bv_set_bit(M, b_index);
 561
 562                 /* lt->v_index is life out of last Statement of b_index */
 563
 564                 if (b_index != 0) {
 565                         int i;
 566                         i = ls->basicblocks[b_index]->icount - 1;
 567                         for (;((i>0) && (ls->basicblocks[b_index]->iinstr+i == ICMD_NOP));
 568                                  i--);
 569                         lt_lifeatstatement(ls, gd, b_index, i, lt, false, W);
 570                 }
 571                 else
 572                         lt_lifeatstatement(ls, gd, b_index, 0, lt, false, W);
 573         }
 574 }
 575
 576 void lt_move_use_sites(struct lifetime *from, struct lifetime *to) {
 577         struct site *s;
 578
 579 #if 0
 580         /* not anymore true for copy propagated lifetimes */
 581         _LT_ASSERT(from->use != NULL);
 582 #endif
 583         if (from->use == NULL)
 584                 return;
 585         for(s = from->use; s->next != NULL; s = s->next);
 586
 587         s->next = to->use;
 588         to->use = from->use;
 589         from->use = NULL;
 590 }
 591
 592 void lt_add_use_site(struct lifetime *lt, int block, int iindex) {
 593         struct site *n;
 594
 595         n = DNEW(struct site);
 596         n->b_index = block;
 597         n->iindex = iindex;
 598         n->next = lt->use;
 599         lt->use = n;
 600
 601         /* CFG is analysed from the end to the start -> so first found use site */
 602         /* is the last use of the Local Var */
 603
 604         if (lt->last_use == NULL)
 605                 lt->last_use = n;
 606 }
 607
 608 void lt_remove_use_site(struct lifetime *lt, int block, int iindex) {
 609         struct site *n;
 610
 611         /* check lt->use itself */
 612
 613         if ((lt->use->b_index == block) && (lt->use->iindex == iindex)) {
 614                 /* found */
 615                 lt->use = lt->use->next;
 616         } else {
 617
 618                 /* look through list */
 619
 620                 for (n = lt->use; (n->next != NULL) && ((n->next->b_index != block) ||
 621                                                                         (n->next->iindex != iindex)); n = n->next);
 622
 623                 /* assert, that lt was found */
 624
 625                 _LT_ASSERT(n->next != NULL);
 626                 _LT_ASSERT(n->next->b_index == block);
 627                 _LT_ASSERT(n->next->iindex == iindex);
 628
 629                 n->next = n->next->next;
 630         }
 631 }
 632
 633 void lt_add_def_site(struct lifetime *lt, int block, int iindex) {
 634         struct site *n;
 635
 636         /* SSA <-> only one definition per lifetime! */
 637
 638         _LT_ASSERT(lt->def == NULL);
 639         n = DNEW(struct site);
 640         n->b_index = block;
 641         n->iindex = iindex;
 642         n->next = NULL;
 643         lt->def = n;
 644 }
 645
 646 void lt_usage(jitdata *jd,s4 v_index, int block, int instr,
 647                                           int store)
 648 {
 649         struct lifetime *n;
 650         lsradata *ls;
 651
 652         ls = jd->ls;
 653
 654         n = ls->lifetime + v_index;
 655
 656         if (n->type == -1) { /* new local lifetime */
 657                 _LT_ASSERT(0);
 658                 n->v_index=v_index;
 659                 n->type=VAR(v_index)->type;
 660                 /* TODO: check!!!!  */
 661                 /* All var are SAVEDVARS or this gets reset afterwards???? */
 662                 n->savedvar = SAVEDVAR;
 663                 n->flags = 0;
 664                 n->usagecount = 0;
 665
 666                 n->bb_last_use = -1;
 667                 n->bb_first_def = -1;
 668
 669                 n->use = NULL;
 670                 n->def = NULL;
 671                 n->last_use = NULL;
 672         }
 673         _LT_ASSERT(VAR(v_index)->type == n->type);
 674
 675         /* add access at (block, instr) to instruction list */
 676         /* remember last USE, so only write, if USE Field is undefined (==-1)   */
 677         /* count store as use, too -> defined and not used vars would overwrite */
 678         /* other vars */
 679
 680         if (store == LT_USE) {
 681 #ifdef USAGE_COUNT
 682                 n->usagecount += ls->nesting[block];
 683 #endif
 684                 lt_add_use_site(n, block, instr);
 685         }
 686         if (store == LT_DEF) {
 687                 lt_add_def_site(n, block, instr);
 688         }
 689 }
 690
 691 /***************************************************************************
 692 use sites: dead code elemination, LifenessAnalysis
 693 def sites: dead code elemination
 694 ***************************************************************************/
 695 void _lt_scanlifetimes(jitdata *jd, graphdata *gd, basicblock *bptr,
 696                                            int b_index)
 697 {
 698 /*      methodinfo         *lm; */
 699         builtintable_entry *bte;
 700         methoddesc         *md;
 701         int i, j, t, v;
 702         int iindex/*, b_index*/;
 703         instruction *iptr;
 704         s4 *argp;
 705
 706         lsradata *ls;
 707
 708         ls = jd->ls;
 709
 710 #ifdef LT_DEBUG_VERBOSE
 711         if (compileverbose)
 712                 printf("_lt_scanlifetimes: BB %3i flags %3i\n", b_index, bptr->flags);
 713 #endif
 714
 715         if (bptr->flags >= BBREACHED) {
 716
 717 /*              b_index = bptr->nr; */
 718
 719                 /* get instruction count for BB */
 720
 721                 iindex = bptr->icount - 1;
 722
 723                 /* regard not setup new BB with maybe just in and outstack */
 724
 725                 if (iindex < 0)
 726                         iindex = 0;
 727
 728                 /* Regard phi_functions (Definition of target, Use of source) */
 729
 730                 for(i = 0; i < ls->ssavarcount; i++) {
 731                         if (ls->phi[b_index][i] != NULL) {
 732                                 /* Phi Function for var i at b_index exists */
 733                                 v = ls->phi[b_index][i][0];
 734                                 _LT_ASSERT( v != ls->varcount_with_indices);
 735                                 t = VAR(i)->type;
 736
 737                                 /* Add definition of target add - phi index -1*/
 738 #ifdef LT_DEBUG_VERBOSE
 739                                 if (compileverbose)
 740                                         printf("_lt_scanlifetimes: phi_def: v: %3i\n i: %3i\n",
 741                                                    v, -i-1);
 742 #endif
 743                                 lt_usage(jd, v, b_index, -i-1, LT_DEF);
 744
 745                                 /* Add Use of sources */
 746
 747                                 for (j = 1; j <= graph_get_num_predecessor(gd, b_index); j++) {
 748                                         if (ls->phi[b_index][i][j] != ls->varcount_with_indices)
 749                                                 if (ls->phi[b_index][i][j] != UNUSED)
 750                                                         lt_usage(jd, ls->phi[b_index][i][j], b_index,
 751                                                                          -i-1, LT_USE);
 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  */