src/vm/jit/optimizing/lifetimes.c

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