src/vm/jit/optimizing/lifetimes.c

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