src/vm/jit/optimizing/lifetimes.c

   1 /* src/vm/jit/lsra.inc - lifetime anaylsis
   2
   3    Copyright (C) 1996-2005 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 "vm/options.h"
  55 #endif
  56
  57 #include <time.h>
  58 #include <errno.h>
  59
  60 /* function prototypes */
  61 void _scan_lifetimes(registerdata *rd, lsradata *ls, graphdata *gd,
  62                                         basicblock *bptr);
  63 void _lsra_new_stack( lsradata *, stackptr , int , int, int);
  64 void _lsra_from_stack(lsradata *, stackptr , int , int, int);
  65 void lsra_usage_local(lsradata *, s4 , int , int , int , int );
  66
  67
  68 void LifeOutAtBlock(lsradata *ls, graphdata *gd, int *M, int n,
  69                                         struct lifetime *lt);
  70 void LifeInAtStatement(lsradata *ls, graphdata *gd, int *M, int b_index,
  71                                            int iindex, struct lifetime *lt);
  72 void LifeOutAtStatement(lsradata *ls, graphdata *gd, int *M, int b_index,
  73                                                 int iindex, struct lifetime *lt);
  74 #ifdef USAGE_COUNT
  75 void lt_get_nesting(lsradata *ls, graphdata *gd, dominatordata *dd);
  76 #endif
  77
  78 void set_use_site(struct lifetime *lt, struct site *use_site) {
  79 }
  80
  81 struct site *get_first_use_site(struct lifetime *lt, lt_iterator *iter) {
  82         return ((*iter) = lt->use);
  83 }
  84
  85 struct site *get_next_site(lt_iterator *iter) {
  86         if ((*iter) == NULL)
  87                 return NULL;
  88         else
  89                 return ((*iter) = (*iter)->next);
  90 }
  91
  92 struct site *get_first_def_site(struct lifetime *lt, lt_iterator *iter) {
  93         return ((*iter) = lt->def);
  94 }
  95
  96 bool v_is_defined_at_s(lsradata *ls, int b_index, int iindex,
  97                                            struct lifetime * lt) {
  98         struct site *def_site;
  99         bool is_defined_at_s;
 100
 101         def_site = lt->def;
 102         is_defined_at_s = ((def_site->b_index == b_index)
 103                                            && (def_site->iindex == iindex));
 104         return is_defined_at_s;
 105 }
 106
 107 /****************************************************************************
 108 Get Def & Use Sites
 109 ****************************************************************************/
 110 void scan_lifetimes(methodinfo *m, codegendata *cd, registerdata *rd,
 111                                         lsradata *ls, graphdata *gd, dominatordata *dd) {
 112         int i, p;
 113         s4 t;
 114         methoddesc *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++) printf("%3i ", ls->sorted[i]);
 126                 printf("\n");
 127                 printf("Sorted_rev: ");
 128                 for (i=0; i < ls->basicblockcount; i++)
 129                         printf("%3i ", ls->sorted_rev[i]);
 130                 printf("\n");
 131         }
 132 #endif
 133         if (ls->max_interfaces != -1) {
 134                 /* init Interface Stackslot lifetimes -1.. */
 135                 for (i = -1; i > -ls->interface_0[-ls->max_interfaces-1]-1; i--) {
 136                         ls->lifetime[-i-1].v_index = i;
 137                         ls->lifetime[-i-1].usagecount = 0;
 138                         ls->lifetime[-i-1].bb_last_use = -1;
 139                         ls->lifetime[-i-1].bb_first_def = -1;
 140                         ls->lifetime[-i-1].local_ss = NULL;
 141                         ls->lifetime[-i-1].savedvar = 0;
 142                         ls->lifetime[-i-1].flags = 0;
 143                         /* .type already set while ssa_Rename_, so we could save a */
 144                         /* lookup table for the type information */
 145                 }
 146                 ls->v_index = -ls->interface_0[-ls->max_interfaces-1]-1;
 147         }
 148
 149         for(i = ls->basicblockcount - 1; i>= 0; i--)
 150                 if (ls->sorted[i] != -1)
 151                         _scan_lifetimes(rd, ls, gd, ls->basicblocks[ls->sorted[i]]);
 152
 153         /* Parameter initialisiation for locals [0 .. paramcount[            */
 154         /* -> add local var write access at (bb=0,iindex=0)                 */
 155
 156         for (p = 0; p < md->paramcount; p++) {
 157                 t = md->paramtypes[p].type;
 158                 i = ls->local_0[p];
 159                 _LT_ASSERT( i < cd->maxlocals);
 160 #ifdef LT_DEBUG_VERBOSE
 161                 if (compileverbose)
 162                         printf("param %3i -> L %3i/%3i",p,i,t);
 163 #endif
 164                 if (rd->locals[i][t].type >= 0) {
 165                         /* Param to Local init happens before normal Code */
 166 #ifdef LT_DEBUG_VERBOSE
 167                         if (compileverbose)
 168                                 printf(" ok\n");
 169 #endif
 170                         lsra_usage_local(ls, i, t, 0, 0, LSRA_STORE);
 171                 }
 172 #ifdef LT_DEBUG_VERBOSE
 173                 else
 174                         if (compileverbose)
 175                                 printf(" .....\n");
 176 #endif
 177         }  /* end for */
 178 }
 179
 180
 181 bool is_simple_lt(struct lifetime *lt) {
 182         lt_iterator i_def, i_use;
 183         struct site *def, *use;
 184         bool all_in_same_block;
 185
 186
 187         def = get_first_def_site(lt, &i_def);
 188         use = get_first_use_site(lt, &i_use);
 189         all_in_same_block = true;
 190         for (; (all_in_same_block && (use != NULL)); use = get_next_site(&i_use)) {
 191                 all_in_same_block =
 192                         (use->iindex >= 0) && (use->b_index == def->b_index);
 193         }
 194         return all_in_same_block;
 195 }
 196
 197 void lt_is_live(lsradata *ls, struct lifetime *lt, int b_index, int iindex) {
 198         int bb_sorted;
 199
 200         bb_sorted = ls->sorted_rev[b_index];
 201
 202         if ((lt->bb_last_use < bb_sorted) ||
 203                 ((lt->bb_last_use == bb_sorted) && (lt->i_last_use < iindex))) {
 204                 lt->bb_last_use = bb_sorted;
 205                 lt->i_last_use  = iindex;
 206         }
 207         if ((lt->bb_first_def > bb_sorted) ||
 208                 ((lt->bb_first_def == bb_sorted) && (lt->i_first_def > iindex))) {
 209                 lt->bb_first_def = bb_sorted;
 210                 lt->i_first_def  = iindex;
 211         }
 212 }
 213
 214 void lt_set_simple_use(lsradata *ls, struct lifetime *lt) {
 215         lt_iterator i_use;
 216         struct site *use;
 217
 218         /* SAVEDVAR is nowhere set!!!! */
 219
 220         /* Def is first use */
 221 /*      lt->bb_first_def = ls->sorted_rev[lt->def->b_index]; */
 222 /*      lt->i_first_def = lt->def->iindex; */
 223
 224         lt_is_live(ls, lt, lt->def->b_index, lt->def->iindex);
 225
 226         /* get last use */
 227         use = get_first_use_site(lt, &i_use);
 228 /*      lt->bb_last_use = ls->sorted_rev[use->b_index]; */
 229 /*      lt->i_last_use = use->iindex; */
 230         for (;  (use != NULL); use = get_next_site(&i_use))
 231                 lt_is_live(ls, lt, use->b_index, use->iindex);
 232 /*              if (use->iindex > lt->i_last_use) */
 233 /*                      lt->i_last_use = use->iindex; */
 234 }
 235
 236 #if defined(JOIN_PHI_LT)
 237 /******************************************************************************
 238 Set up data structures for a interference graphs of variables used in each phi
 239 function
 240 ******************************************************************************/
 241 void lt_setup_phi_interference(lsradata *ls, graphdata *gd) {
 242         int a, b, i, j, t;
 243         int *stack, stack_top;
 244         struct igraph_lookup **lookup;
 245         struct igraph_lookup *tmp;
 246         int lookup_top, igraph_top;
 247         struct igraph_vars *new_var;
 248
 249         lookup_top = igraph_top = 0;
 250         lookup = DMNEW(struct igraph_lookup *, ls->max_vars_with_indices*2);
 251         stack  = DMNEW(int, ls->max_vars_with_indices);
 252         for(b = 0; b < ls->basicblockcount; b++) {
 253                 for(a = 0; a < ls->max_vars; a++) {
 254                         if (ls->phi[b][a] != NULL) {
 255
 256 #if defined(LT_DEBUG_VERBOSE)
 257                                 if (compileverbose) {
 258                                         printf("Phi(%3i, %3i): ", a, gd->num_pred[b]);
 259                                 }
 260 #endif
 261                                 stack_top = 0;
 262                                 /* loop for all vars in this phi function -> setup a interf graph */
 263                                 /* structure for it */
 264                                 for(j = 0; j < gd->num_pred[b] + 1; j++) {
 265                                         if (ls->phi[b][a][j] != ls->max_vars_with_indices) {
 266                                                 /* used entry */
 267                                                 stack[stack_top++] = ls->phi[b][a][j];
 268 #if defined(LT_DEBUG_VERBOSE)
 269                                                 if (compileverbose) {
 270                                                         printf("%3i ",ls->phi[b][a][j]);
 271                                                 }
 272 #endif
 273                                         }
 274                                 }
 275                                 _LT_ASSERT(stack_top <= ls->max_vars_with_indices);
 276 #if defined(LT_DEBUG_VERBOSE)
 277                                 if (compileverbose) {
 278                                         printf("\n ");
 279                                 }
 280 #endif
 281                                 /* sort (insertion)*/
 282                                 /* TODO: make unique sort proc (see lsra_insertion...) */
 283                                 for (i = 1; i <= stack_top - 1; i++) {
 284                                         j = i;
 285                                         t = stack[j];
 286                                         while ((j > 0) && (stack[j-1] > t)) {
 287                                                 stack[j] = stack[j-1];
 288                                                 j--;
 289                                         }
 290                                         stack[j] = t;
 291                                 }
 292 #if defined(LT_DEBUG_VERBOSE)
 293                                 if (compileverbose) {
 294                                         printf("Sorted: ");
 295                                         for(i=0; i < stack_top; i++)
 296                                                 printf("%3i ",stack[i]);
 297                                         printf("\n");
 298                                 }
 299 #endif
 300                                 /* now remove duplicates */
 301                                 /* t ... new stack_top */
 302                                 /* i ... first of duplicate sequence */
 303                                 /* j ... next duplicate sequence */
 304                                 i = t = 0;
 305                                 while (i < stack_top) {
 306                                         stack[t] = stack[i];
 307                                         t++;
 308                                         for(j = i + 1; (j < stack_top)&&(stack[i]==stack[j]); j++);
 309                                         if (j == stack_top) {
 310                                                 /* last duplicate entries */
 311                                                 stack_top = t;
 312                                                 break;
 313                                         }
 314                                         i = j;
 315                                 }
 316                                 _LT_ASSERT(stack_top <= ls->max_vars_with_indices);
 317 #if defined(LSRA_DEBUG_VERBOSE)
 318                                 if (compileverbose) {
 319                                         printf("wo duplicates: ");
 320                                         for(i=0; i < stack_top; i++)
 321                                                 printf("%3i ",stack[i]);
 322                                         printf("\n");
 323                                 }
 324 #endif
 325                                 /* setup lookuptable for vars stack[0..stack_top[ to        */
 326                                 /* interference graph number & interference graph structure */
 327                                 for(i = 0; i < stack_top; i++) {
 328                                         _LT_ASSERT(lookup_top < ls->max_vars_with_indices*2);
 329                                         lookup[lookup_top] = DNEW(struct igraph_lookup);
 330                                         lookup[lookup_top]->var = stack[i]; /* var index */
 331                                         lookup[lookup_top]->igraph = igraph_top; /* igraph index */
 332                                         lookup_top++;
 333                                 }
 334                                 igraph_top++;
 335                         }
 336                 }
 337         }
 338         ls->igraph = DMNEW(struct igraph , igraph_top);
 339         ls->igraph_top = igraph_top;
 340         for(i = 0; i < igraph_top; i++) {
 341                 ls->igraph[i].inter = NULL;
 342                 ls->igraph[i].vars = NULL;
 343         }
 344
 345         /* sort lookup */
 346
 347         for (i = 1; i < lookup_top; i++) {
 348                 j = i;
 349                 t = lookup[j]->var;
 350                 tmp = lookup[j];
 351                 while ((j > 0) && (lookup[j-1]->var > t)) {
 352                         lookup[j]=lookup[j-1];
 353                         j--;
 354                 }
 355                 lookup[j] = tmp;
 356         }
 357
 358         /* join igraphs for multiple vars  */
 359         /* TODO: make this more efficient! */
 360         for (i = 1; i < lookup_top; i++) {
 361                 if (lookup[i-1]->var == lookup[i]->var) {
 362                         for(j = 0; j < lookup_top; j++)
 363                                 if (j != i)
 364                                         if (lookup[j]->igraph == lookup[i]->igraph)
 365                                                 lookup[j]->igraph = lookup[i-1]->igraph;
 366                         lookup[i]->igraph = lookup[i-1]->igraph;
 367                 }
 368         }
 369
 370         ls->igraph_lookup_top = lookup_top;
 371         ls->igraph_lookup = DMNEW(struct igraph_lookup *, lookup_top);
 372         for(i = 0; i < lookup_top; i++) {
 373                 ls->igraph_lookup[i] = lookup[i];
 374                 new_var = DNEW(struct igraph_vars);
 375                 new_var->v = lookup[i]->var;
 376                 new_var->next = ls->igraph[lookup[i]->igraph].vars;
 377                 ls->igraph[lookup[i]->igraph].vars = new_var;
 378         }
 379 #if defined(LT_DEBUG_VERBOSE)
 380                                 if (compileverbose) {
 381                                         printf("IGraph(%3i): ",igraph_top);
 382                                         for(i = 0; i < igraph_top; i++) {
 383                                                 printf("%3i(",i);
 384                                                 for(new_var = ls->igraph[i].vars; new_var != NULL; new_var = new_var->next)
 385                                                         printf("%3i,",new_var->v);
 386                                                 printf(") ");
 387                                         }
 388                                         printf("\n");
 389                                         for(i=0; i < lookup_top; i++)
 390                                                 printf("(%3i->%3i) ",ls->igraph_lookup[i]->var, ls->igraph_lookup[i]->igraph);
 391                                         printf("\n");
 392                                 }
 393 #endif
 394 }
 395
 396 int get_igraph_index(lsradata *ls, int var) {
 397         int i, i_max, i_min;
 398
 399         if (ls->igraph_lookup == NULL)
 400                 return -1;
 401
 402         i_min = 0;
 403         i_max = ls->igraph_lookup_top;
 404
 405         while (true) {
 406                 i = (i_min + i_max)/2;
 407                 if (ls->igraph_lookup[i]->var == var)
 408                         return ls->igraph_lookup[i]->igraph;
 409                 if ((i_max - i_min <= 1))
 410                         return -1;
 411                 if (var < ls->igraph_lookup[i]->var) {
 412                         i_max = i;
 413                 } else {
 414                         i_min = i;
 415                 }
 416         }
 417         /* prevent compiler warning */
 418         return -1;
 419 }
 420
 421 void build_interference(lsradata *ls, int b_index, int iindex,
 422                                          struct lifetime *lt) {
 423         int igraph_index;
 424         struct igraph_vars *v;
 425         struct igraph_interference *i;
 426         struct lifetime *lt_i;
 427
 428         if ((igraph_index = get_igraph_index(ls, lt->v_index)) == -1)
 429                 return;
 430
 431         _LT_ASSERT(ls->igraph[igraph_index].vars != NULL);
 432
 433         for(v = ls->igraph[igraph_index].vars; v != NULL; v = v->next) {
 434                 /* ignore interference with var itself */
 435                 if (v->v != lt->v_index) {
 436                         /* get lifetime of v->v */
 437                         if (v->v >= 0) {
 438                                 lt_i = &(ls->lifetime[ls->maxlifetimes + v->v]);
 439                         } else {
 440                                 lt_i = &(ls->lifetime[-v->v - 1]);
 441                         }
 442                         _LT_ASSERT(lt_i->v_index == v->v);
 443
 444                         if (v_is_defined_at_s(ls, b_index, iindex, lt_i)) {
 445                                 /* search if entry already exists */
 446                                 for(i = ls->igraph[igraph_index].inter; i != NULL; i = i->next)
 447                                 {
 448                                         if ((i->v1 == min(v->v, lt->v_index)) &&
 449                                                 (i->v2 == max(v->v, lt->v_index)))
 450                                                 break;
 451                                 }
 452                                 if (i == NULL) {
 453                                         i = DNEW(struct igraph_interference);
 454                                         i->v1 = min(v->v, lt->v_index);
 455                                         i->v2 = max(v->v, lt->v_index);
 456                                         i->next = ls->igraph[igraph_index].inter;
 457                                         ls->igraph[igraph_index].inter = i;
 458                                 }
 459                         }
 460                 }
 461         }
 462
 463 }
 464 #endif
 465
 466 void LifenessAnalysis(methodinfo *m, lsradata *ls, graphdata *gd) {
 467         int *M; /* bit_vecor of visited blocks */
 468         int *use; /* bit_vecor of blocks with use sites visited */
 469
 470         struct site *use_site, *u_site;
 471         lt_iterator iter, iter1;
 472         graphiterator pred_iter;
 473
 474         int lt_index, i, pred, iindex, iindex1;
 475         struct lifetime *lt;
 476         int *phi;
 477         struct timespec time_start,time_end;
 478 #if 0
 479         bool measure = false;
 480 #endif
 481
 482 /* #define MEASURE_RT */
 483
 484 #ifdef MEASURE_RT
 485         if (clock_gettime(CLOCK_THREAD_CPUTIME_ID,&(time_start)) != 0) {
 486                 fprintf(stderr,"could not get time: %s\n",strerror(errno));
 487                 abort();
 488         }
 489 #endif
 490 #if 0
 491         if ((strcmp(m->class->name->text, "java/lang/Object")==0) &&
 492                 (strcmp(m->name->text,"equals")==0)) {
 493                 printf("----------------\n");
 494 /*              measure = false; */
 495         }
 496 #endif
 497 #if defined(JOIN_PHI_LT)
 498         lt_setup_phi_interference(ls, gd);
 499 #endif
 500
 501         M = bv_new(ls->basicblockcount);
 502         use = bv_new(ls->basicblockcount);
 503
 504 #ifdef LT_DEBUG_VERBOSE
 505         if (compileverbose)
 506         printf("LT_ANALYSE: \n");
 507 #endif
 508         for(lt_index = 0; lt_index < ls->lifetimecount; lt_index++) {
 509                 lt = &(ls->lifetime[lt_index]);
 510                 if (lt->type == -1)
 511                         continue;
 512 #ifdef LT_DEBUG_VERBOSE
 513         if (compileverbose)
 514                 printf("LT: %3i:", lt_index);
 515 #endif
 516
 517 #if 0
 518                 if (measure)
 519                         if (clock_gettime(CLOCK_THREAD_CPUTIME_ID,&(time_start)) != 0) {
 520                                 fprintf(stderr,"could not get time: %s\n",strerror(errno));
 521                                 abort();
 522                         }
 523 #endif
 524
 525                 lt->savedvar = 0;
 526
 527                 _LT_ASSERT(lt->def != NULL);
 528                 _LT_ASSERT(lt->def->next == NULL); /* SSA! */
 529                 _LT_ASSERT(lt->use != NULL);
 530
 531                 lt->bb_last_use = -1;
 532                 lt->bb_first_def = ls->basicblockcount;
 533
 534                 bv_reset(M, ls->basicblockcount);
 535                 bv_reset(use, ls->basicblockcount);
 536
 537                 use_site = get_first_use_site(lt, &iter);
 538                 for (;use_site != NULL; use_site = get_next_site(&iter)) {
 539                         iindex  = use_site->iindex;
 540                         if ((lt->def->b_index == use_site->b_index) &&
 541                                 (iindex < 0) &&
 542                                 (iindex <= lt->def->iindex)) {
 543                                 if (iindex == lt->def->iindex) /* check this */
 544                                         continue;
 545                                 /* do normal analysis */
 546                                 /* there is a use in a phi function before def site */
 547                         } else if (bv_get_bit(use, use_site->b_index)) {
 548                                 continue;
 549                         } else {
 550                                 bv_set_bit(use, use_site->b_index);
 551                                 /* use sites of this basic block not visited till now */
 552                                 /* get use site of this bb with highest iindex (lower than def site)*/
 553                                 iindex1 = -1;
 554                                 u_site = use_site;
 555                                 for(iter1= iter; u_site != NULL; u_site = get_next_site(&iter1)) {
 556                                         if ((u_site->b_index == use_site->b_index) &&
 557                                                 (lt->def->b_index == use_site->b_index) &&
 558                                                 (u_site->iindex >= 0) &&
 559                                                 (u_site->iindex < lt->def->iindex) &&
 560                                                 (u_site->iindex > iindex1)) {
 561                                                 iindex1 = u_site->iindex;
 562                                         } else {
 563                                                 if ((u_site->b_index == use_site->b_index) &&
 564                                                         (u_site->iindex > iindex))
 565                                                         iindex = u_site->iindex;
 566                                         }
 567                                 }
 568                                 if (iindex1 != -1)
 569                                         iindex = iindex1;
 570                         }
 571 #ifdef LT_DEBUG_VERBOSE
 572         if (compileverbose)
 573                         printf("(%3i,%3i)", use_site->b_index, iindex);
 574 #endif
 575
 576                         if (iindex < 0) {
 577                                 /* use in phi function */
 578                                 /* ls->phi[use_site->b_index][-use_site->iindex-1]*/
 579
 580                                 lt_is_live(ls, lt, use_site->b_index, iindex);
 581
 582                                 phi = ls->phi[use_site->b_index][-iindex-1];
 583                                 _LT_ASSERT(phi != NULL);
 584
 585                                 if (lt->v_index != phi[0]) { /* check this */
 586                                         /* ignore "Self use/def" in phi function */
 587
 588
 589                                         pred = graph_get_first_predecessor(gd, use_site->b_index,
 590                                                                                                            &pred_iter);
 591                                         for(i = 1; (pred != -1); i++,pred =
 592                                                         graph_get_next(&pred_iter))
 593                                                 if (lt->v_index == phi[i])
 594                                                         LifeOutAtBlock(ls, gd, M, pred, lt);
 595                                 }
 596                         } else
 597                                 LifeInAtStatement(ls, gd, M, use_site->b_index,
 598                                                                   iindex, lt);
 599                 }
 600 #ifdef LT_DEBUG_VERBOSE
 601         if (compileverbose)
 602                         printf("\n");
 603 #endif
 604
 605 #if 0
 606                 if (measure) {
 607                         if (clock_gettime(CLOCK_THREAD_CPUTIME_ID,&(time_end)) != 0) {
 608                                 fprintf(stderr,"could not get time: %s\n",strerror(errno));
 609                                 abort();
 610                         }
 611
 612                         {
 613                                 long diff;
 614                                 time_t atime;
 615
 616                                 diff = (time_end.tv_nsec - time_start.tv_nsec) / 1000;
 617                                 atime = time_start.tv_sec;
 618                                 while (atime < time_end.tv_sec) {
 619                                         atime++;
 620                                         diff += 1000000;
 621                                 }
 622                                 printf("%8li %3i %s.%s.%s\n",diff, lt_index, m->class->name->text, m->name->text,
 623                                            m->descriptor->text);
 624                         }
 625                 }
 626 #endif
 627         }
 628 #ifdef MEASURE_RT
 629         if (clock_gettime(CLOCK_THREAD_CPUTIME_ID,&(time_end)) != 0) {
 630                 fprintf(stderr,"could not get time: %s\n",strerror(errno));
 631                 abort();
 632         }
 633
 634         {
 635                 long diff;
 636                 time_t atime;
 637
 638                 diff = (time_end.tv_nsec - time_start.tv_nsec) / 1000;
 639                 atime = time_start.tv_sec;
 640                 while (atime < time_end.tv_sec) {
 641                         atime++;
 642                         diff += 1000000;
 643                 }
 644                 printf("%8li %s.%s.%s\n",diff, m->class->name->text, m->name->text,
 645                            m->descriptor->text);
 646         }
 647 #endif
 648
 649 #if defined(JOIN_PHI_LT)
 650 #if defined(LT_DEBUG_VERBOSE)
 651         if (compileverbose) {
 652                 struct igraph_interference *inter;
 653                 printf("Interferences: ");
 654                 for(i = 0; i < ls->igraph_top; i++) {
 655                         if (ls->igraph[i].inter != NULL) {
 656                                 for(inter = ls->igraph[i].inter; inter != NULL; inter = inter->next)
 657                                         printf("%3i(%3i,%3i) ",i,inter->v1,inter->v2);
 658                         }
 659                 }
 660                 printf("\n");
 661         }
 662 #endif
 663
 664         {
 665         struct igraph_vars *var, *var1;
 666         struct igraph_interference *inter;
 667         struct lifetime *lt1, *lt2;
 668         struct stackslot *ss;
 669         struct site *s;
 670         int j, k, l;
 671         instruction *iptr;
 672         int pred;
 673         graphiterator iter;
 674
 675         /* join phi arguments that do not interfere */
 676         printf("this should not be seen \n");
 677         for(i = 0; i < ls->igraph_top; i++) {
 678                 if (ls->igraph[i].inter == NULL) {
 679                         lt1 = lt2 = NULL;
 680                         for(var = ls->igraph[i].vars; var != NULL; var = var->next) {
 681                                 if (lt1 == NULL) {
 682                                         if (var->v >= 0) {
 683                                                 lt1 = &(ls->lifetime[ls->maxlifetimes + var->v]);
 684                                         } else {
 685                                                 lt1 = &(ls->lifetime[-var->v - 1]);
 686                                         }
 687                                         _LT_ASSERT(lt1->v_index == var->v);
 688                                         continue;
 689                                 } else {
 690                                         if (var->v >= 0) {
 691                                                 lt2 = &(ls->lifetime[ls->maxlifetimes + var->v]);
 692                                         } else {
 693                                                 lt2 = &(ls->lifetime[-var->v - 1]);
 694                                         }
 695                                         _LT_ASSERT(lt2->v_index == var->v);
 696                                 }
 697
 698                                 if ((lt1->v_index < 0) && (lt2->v_index >=0)) {
 699                                         /* swap lt1 and lt2 - cannot join Stackslotlifetime */
 700                                         /* into Localvar lifetimes */
 701
 702                                         lt = lt1;
 703                                         lt1 = lt2;
 704                                         lt2 = lt;
 705                                 }
 706
 707                                 if ((lt1->v_index >=0) && (lt2->v_index >=0)) {
 708                                         for(s = lt2->def; s != NULL; s = s->next) {
 709                                                 if ((s->b_index == 0) && (s->iindex ==0)) {
 710                                                         /* swap lt1 and lt2 - lt2 is initialized by a param*/
 711
 712                                                         _LT_ASSERT((lt1->def->b_index != 0)
 713                                                                            || (lt1->def->iindex !=0));
 714                                                         lt = lt1;
 715                                                         lt1 = lt2;
 716                                                         lt2 = lt;
 717                                                         break;
 718                                                 }
 719                                         }
 720                                 }
 721
 722                                 /* already joined */
 723                                 if ((lt2->type == -1) || (lt1 == lt2))
 724                                         continue;
 725 #if defined(LT_DEBUG_VERBOSE)
 726                                 if (compileverbose) {
 727                                         printf("Joining %3i into %3i\n",lt2->v_index, lt1->v_index);
 728                                 }
 729 #endif
 730
 731                                 /* copy local_ss from lt2 to lt1 & rename local_ss->s->varnum */
 732                                 while (lt2->local_ss != NULL) {
 733                                         if (lt1->v_index >= 0) {
 734                                                 lt2->local_ss->s->varkind = LOCALVAR;
 735                                         }
 736                                         /* other direction not possible! (LOCALVAR->TEMPVAR) */
 737                                         /* see 'if' above */
 738                                         lt2->local_ss->s->varnum  = lt1->v_index;
 739
 740                                         ss = lt1->local_ss;
 741                                         lt1->local_ss = lt2->local_ss;
 742                                         lt2->local_ss = lt2->local_ss->next;
 743                                         lt1->local_ss->next = ss;
 744                                 }
 745
 746                                 /* look at the use sites */
 747                                 for(s = lt2->use; s != NULL; s = s->next) {
 748                                         if (s->iindex < 0) {
 749                                                 /* use in phi function -> change */
 750                                                 pred=graph_get_first_predecessor(gd, s->b_index, &iter);
 751                                                 for (j = 1; pred != -1; j++,
 752                                                                  pred = graph_get_next(&iter)) {
 753                                                         if (ls->phi[s->b_index][-s->iindex-1][j] ==
 754                                                                 lt2->v_index) {
 755                                                                 ls->phi[s->b_index][-s->iindex-1][j]
 756                                                                         = lt1->v_index;
 757                                                                 /* change in appropriate phi_move, too */
 758                                                                 for(k=0; k<ls->num_phi_moves[pred]; k++) {
 759                                                                         if (ls->phi_moves[pred][k][1] ==
 760                                                                                 lt2->v_index) {
 761                                                                                 ls->phi_moves[pred][k][1]=lt1->v_index;
 762                                                                         }
 763 /*                                                                      if (ls->phi_moves[pred][k][0] == */
 764 /*                                                                              lt2->v_index) { */
 765 /*                                                                              ls->phi_moves[pred][k][0]=lt1->v_index; */
 766 /*                                                                      } */
 767                                                                 }
 768                                                         }
 769                                                 }
 770                                                 /* change in appropriate phi_move, too */
 771                                         } else {
 772                                                 if (lt2->v_index >= 0) {
 773                                                         /* lt1&&lt2 are LOCALVAR, XSTORE,IINC and XLOAD */
 774                                                         /* have to be changed */
 775                                                         iptr = ls->basicblocks[s->b_index]->iinstr +
 776                                                                 s->iindex;
 777                                                         if (iptr != NULL) {
 778                                                                 /* no edge splitting block from SSA */
 779                                                                 switch(iptr->opc) {
 780                                                                 case ICMD_ILOAD:
 781                                                                 case ICMD_LLOAD:
 782                                                                 case ICMD_FLOAD:
 783                                                                 case ICMD_DLOAD:
 784                                                                 case ICMD_ALOAD:/* iptr->op1 == USE */
 785                                                                 case ICMD_ISTORE:
 786                                                                 case ICMD_LSTORE:
 787                                                                 case ICMD_FSTORE:
 788                                                                 case ICMD_DSTORE:
 789                                                                 case ICMD_ASTORE:
 790                                                                 case ICMD_IINC: /* iptr->op1 == USE */
 791                                                                         if (iptr->op1 == lt2->v_index)
 792                                                                                 iptr->op1 = lt1->v_index;
 793                                                                         break;
 794                                                                         /*                                                      default: */
 795                                                                         /* could be in another than the top stackslot */
 796                                                                         /* too! */
 797                                                                         /*                                                              _LT_ASSERT((iptr-1)->dst->varnum == */
 798                                                                         /*                                                                                 lt1->v_index); */
 799                                                                 }
 800                                                         }
 801                                                 }
 802                                                 /* uses in stackslots are already changed above by */
 803                                                 /* renameing and copying of local_ss */
 804                                         }
 805                                 } /* for(s = lt2->use; s != NULL; s = s->next) */
 806                                 if (lt2->v_index >= 0) {
 807                                         /* change def site */
 808                                         _LT_ASSERT(lt2->def != NULL);
 809                                         /* no SSA Anymore -> cyle through all def sites */
 810                                         /*                                              _LT_ASSERT(lt2->def->next == NULL); */
 811
 812                                         for(s = lt2->def; s != NULL; s = s->next) {
 813                                                 if (s->iindex < 0) {
 814                                                         /* change phi */
 815                                                         if (ls->phi[s->b_index][-s->iindex-1][0] == lt2->v_index)
 816                                                                 ls->phi[s->b_index][-s->iindex-1][0] = lt1->v_index;
 817                                                         pred=graph_get_first_predecessor(gd, s->b_index, &iter);
 818                                                         for (; pred != -1; pred = graph_get_next(&iter)) {
 819                                                                 /* change in appropriate phi_move, too */
 820                                                                 for(k=0; k<ls->num_phi_moves[pred]; k++) {
 821                                                                         if (ls->phi_moves[pred][k][0] ==
 822                                                                                 lt2->v_index) {
 823                                                                                 ls->phi_moves[pred][k][0]=lt1->v_index;
 824                                                                         }
 825                                                                 }
 826                                                         }
 827                                                 } else {
 828                                                         /* change ICMD */
 829
 830                                                         iptr = ls->basicblocks[s->b_index]->iinstr
 831                                                                 + s->iindex;
 832                                                         switch(iptr->opc) {
 833                                                         case ICMD_ILOAD:
 834                                                         case ICMD_LLOAD:
 835                                                         case ICMD_FLOAD:
 836                                                         case ICMD_DLOAD:
 837                                                         case ICMD_ALOAD:
 838                                                         case ICMD_ISTORE:
 839                                                         case ICMD_LSTORE:
 840                                                         case ICMD_FSTORE:
 841                                                         case ICMD_DSTORE:
 842                                                         case ICMD_ASTORE: /* iptr->op1 == DEF */
 843                                                                 if(iptr->op1 == lt2->v_index)
 844                                                                         iptr->op1 = lt1->v_index;
 845                                                                 break;
 846                                                         case ICMD_IINC: /* iptr->val._i.op1_t == DEF */
 847                                                                 if (iptr->val._i.op1_t == lt2->v_index)
 848                                                                         iptr->val._i.op1_t = lt1->v_index;
 849                                                                 break;
 850                                                                 /*                                                      default: */
 851                                                                 /* could be in another than the top stackslot */
 852                                                                 /* too! */
 853                                                                 /*                                                              _LT_ASSERT((iptr->dst->varnum == lt1->v_index)); */
 854                                                         }
 855                                                 }
 856                                         }
 857                                 }
 858
 859                                 /* combine def sites (SSA is dead now)*/
 860                                 _LT_ASSERT(lt2->def != NULL);
 861                                 for(s = lt2->def; s->next != NULL; s = s->next);
 862                                 s->next = lt1->def;
 863                                 lt1->def = lt2->def;
 864
 865                                 /* combine use sites */
 866                                 _LT_ASSERT(lt2->use != NULL);
 867                                 for(s = lt2->use; s->next != NULL; s = s->next);
 868                                 s->next = lt1->use;
 869                                 lt1->use = lt2->use;
 870
 871                                 /* combine first_def and last_use */
 872                                 if (lt1->bb_first_def == lt2->bb_first_def) {
 873                                         lt1->i_first_def = min(lt1->i_first_def, lt2->i_first_def);
 874                                 } else if (lt1->bb_first_def > lt2->bb_first_def) {
 875                                         lt1->bb_first_def = lt2->bb_first_def;
 876                                         lt1->i_first_def  = lt2->i_first_def;
 877                                 }
 878                                 if (lt1->bb_last_use == lt2->bb_last_use) {
 879                                         lt1->i_last_use = max(lt1->i_last_use, lt2->i_last_use);
 880                                 } else if (lt1->bb_last_use < lt2->bb_last_use) {
 881                                         lt1->bb_last_use = lt2->bb_last_use;
 882                                         lt1->i_last_use  = lt2->i_last_use;
 883                                 }
 884
 885                                 /* combine savedvar flags */
 886                                 lt1->savedvar |= lt2->savedvar;
 887                                 _LT_ASSERT(lt1->type == lt2->type);
 888                                 lt2->type = -1;
 889                                 /* change the var in all future references of ls->igraph */
 890                                 /* TODO: do something against this!! */
 891 /*                              for(j = i + 1; j < ls->igraph_top; j++) { */
 892 /*                                      if (ls->igraph[j].inter == NULL) { */
 893 /*                                              for(var1 = ls->igraph[j].vars; var1 != NULL;  */
 894 /*                                                      var1 = var1->next) { */
 895 /*                                                      if (var1->v == lt2->v_index) */
 896 /*                                                              var1->v = lt1->v_index; */
 897 /*                                              } */
 898 /*                                      } */
 899 #if 0
 900                                         /* not needed by now, since only for phi functions */
 901                                         /* with absolutely no interference is checked */
 902                                         else {
 903                                                 inter = ls->igraph[j].inter;
 904                                                 for(;inter != NULL; inter = inter->next) {
 905                                                         if (inter->v1 == lt2->v_index)
 906                                                                 inter->v1 = lt1->v_index;
 907                                                         if (inter->v2 == lt2->v_index)
 908                                                                 inter->v2 = lt1->v_index;
 909                                                 }
 910                                         }
 911 #endif
 912 /*                              } */
 913
 914                                 /* look through all phi functions */
 915                                 for(j = 0; j < ls->basicblockcount; j++) {
 916                                         for(k = 0; k < ls->max_vars; k++) {
 917                                                 if (ls->phi[j][k] != NULL) {
 918                                                         if (ls->phi[j][k][0] == lt2->v_index)
 919                                                                 ls->phi[j][k][0] = lt1->v_index;
 920                                                         for (l = 1; l < graph_get_num_predecessor(gd, j); l++) {
 921                                                                 if (ls->phi[j][k][l] == lt2->v_index)
 922                                                                         ls->phi[j][k][l] = lt1->v_index;
 923                                                         }
 924                                                 }
 925                                         }
 926                                         /* change in phi move, too */
 927                                         for(k = 0; k < ls->num_phi_moves[j]; k++) {
 928                                                 if (ls->phi_moves[j][k][1] == lt2->v_index)
 929                                                         ls->phi_moves[j][k][1] = lt1->v_index;
 930                                                 if (ls->phi_moves[j][k][0] == lt2->v_index)
 931                                                         ls->phi_moves[j][k][0] = lt1->v_index;
 932                                         }
 933                                 }
 934                         } /* for(var = ls->igraph[i].vars; var != NULL; var = var->next) */
 935                 } /* if (ls->igraph[i].inter == NULL) */
 936         } /* for(i = 0; i < ls->igraph_top; i++) */
 937         }
 938 #endif
 939 }
 940
 941 void LifeOutAtBlock(lsradata *ls, graphdata *gd, int *M, int n,
 942                                         struct lifetime *lt) {
 943         /* lt->v_index is life at Block n */
 944         if (!bv_get_bit(M,n)) { /* n no Element of M */
 945                 bv_set_bit(M,n);
 946
 947                 /* lt->v_index is life at last Statement of n */
 948                 if (n != 0) {
 949                         int i;
 950                         i = ls->basicblocks[n]->icount - 1;
 951                         for (;((i>0) && (ls->basicblocks[n]->iinstr+i == ICMD_NOP)); i--);
 952                         LifeOutAtStatement(ls, gd, M, n, i,lt);
 953                 }
 954                 else
 955                         LifeOutAtStatement(ls, gd, M, n, 0, lt);
 956         }
 957 }
 958
 959 void LifeInAtStatement(lsradata *ls, graphdata *gd, int *M, int b_index,
 960                                            int iindex, struct lifetime *lt) {
 961         /* lt->v_index is live-in at s */
 962         int prev_iindex; /* Statement before iindex */
 963         int pred;
 964         graphiterator pred_iter;
 965
 966         lt_is_live(ls, lt, b_index, iindex);
 967
 968         prev_iindex = iindex - 1;
 969         if (prev_iindex < 0)
 970                 /* look through phi functions */
 971                 for(; prev_iindex > -ls->max_vars-1;
 972                         prev_iindex--)
 973                         if (ls->phi[b_index][-prev_iindex-1] != NULL)
 974                                 break;
 975
 976         if (iindex == -ls->max_vars-1) {
 977                 /* iindex is the first statement of b_index */
 978                 /* Statements -ls->max_vars-1 .. -1 are possible phi functions */
 979                 /* lt->v_index is live-in at b_index */
 980
 981                 pred = graph_get_first_predecessor(gd, b_index, &pred_iter);
 982                 for(; pred != -1; pred = graph_get_next(&pred_iter))
 983                         LifeOutAtBlock(ls, gd, M, pred, lt);
 984         } else
 985                 LifeOutAtStatement(ls, gd, M, b_index, prev_iindex, lt);
 986 }
 987
 988 void LifeOutAtStatement(lsradata *ls, graphdata *gd, int *M, int b_index,
 989                                                 int iindex, struct lifetime *lt) {
 990         instruction *iptr;
 991         int igraph_index;
 992         int var;
 993         /* lt->v_index is life-out at s */
 994
 995         /* for each variable w defined at s except v=lt->v_index, add a edge */
 996         /* (v,w) to the interference graph, once one is needed */
 997
 998 #if defined(JOIN_PHI_LT)
 999         /* Build interference Graph for variables involved in phi functions */
1000         /* it is essential, that these variables get merged, if possible!   */
1001         build_interference(ls, b_index, iindex, lt);
1002 #endif
1003         if (!v_is_defined_at_s(ls, b_index, iindex, lt)) {
1004                 /* v is life in at out of statement -> check if the SAVEDVAR */
1005                 /* flag is needed to be set */
1006                 if ((iindex >= 0) && (b_index != 0)) {
1007                         /* real ICMD */
1008                         _LT_ASSERT(ls->basicblocks[b_index]->iinstr != NULL);
1009                         iptr = ls->basicblocks[b_index]->iinstr + iindex;
1010                         if (op_data[iptr->opc][NEEDS_SAVED])
1011                                 lt->savedvar = SAVEDVAR;
1012                 }
1013                 LifeInAtStatement(ls, gd, M, b_index, iindex, lt);
1014         } else
1015                 lt_is_live(ls, lt, b_index, iindex);
1016 }
1017
1018 struct stackslot *lsra_make_ss(stackptr s, int bb_index)
1019 {
1020         struct stackslot *ss;
1021
1022         ss=DNEW(struct stackslot);
1023         ss->bb=bb_index;
1024         ss->s=s;
1025         return ss;
1026 }
1027
1028 void lsra_add_ss(struct lifetime *lt, stackptr s) {
1029         struct stackslot *ss;
1030         bool  insert_s;
1031         /* Stackslot noch nicht eingetragen? */
1032
1033         insert_s = true;
1034
1035         for (ss = lt->local_ss; (!insert_s) && (ss != NULL); ss = ss->next)
1036                 insert_s = (ss->s == s);
1037
1038
1039         /* local_ss == NULL -> stack lt was set in ssa -> create Stack entry */
1040         if ((lt->local_ss == NULL) || (insert_s)) {
1041                 ss = DNEW(struct stackslot);
1042                 ss->s = s;
1043                 ss->s->varnum = lt->v_index;
1044                 ss->next = lt->local_ss;
1045                 lt->local_ss = ss;
1046                 if (s != NULL) lt->savedvar |= s->flags & SAVEDVAR;
1047                 if (s != NULL) lt->type = s->type;
1048         }
1049 }
1050
1051 void move_stackslots(struct lifetime *from, struct lifetime *to) {
1052         struct stackslot *ss;
1053
1054         if (from->local_ss == NULL)
1055                 /* nothing to move */
1056                 return;
1057
1058         for(ss = from->local_ss; ss->next != NULL; ss = ss->next);
1059
1060         ss->next = to->local_ss;
1061         to->local_ss = from->local_ss;
1062         from->local_ss = NULL;
1063 }
1064 void move_use_sites(struct lifetime *from, struct lifetime *to) {
1065         struct site *s;
1066
1067         _LT_ASSERT(from->use != NULL);
1068         if (from->use == NULL)
1069                 return;
1070         for(s = from->use; s->next != NULL; s = s->next);
1071
1072         s->next = to->use;
1073         to->use = from->use;
1074         from->use = NULL;
1075 }
1076
1077 void add_use_site(struct lifetime *lt, int block, int iindex) {
1078         struct site *n;
1079
1080         n = DNEW(struct site);
1081         n->b_index = block;
1082         n->iindex = iindex;
1083         n->next = lt->use;
1084         lt->use = n;
1085
1086         /* CFG is analysed from the end to the start -> so first found use site */
1087         /* is the last use of the Local Var */
1088         if (lt->last_use == NULL)
1089                 lt->last_use = n;
1090 }
1091
1092 void remove_use_site(struct lifetime *lt, int block, int iindex) {
1093         struct site *n;
1094
1095         /* check lt->use itself */
1096         if ((lt->use->b_index == block) && (lt->use->iindex == iindex)) {
1097                 /* found */
1098                 lt->use = lt->use->next;
1099         } else {
1100                 /* look through list */
1101                 for (n = lt->use; (n->next != NULL) && ((n->next->b_index != block) ||
1102                                                                         (n->next->iindex != iindex)); n = n->next);
1103                 /* assert, that lt was found */
1104                 _LT_ASSERT(n->next != NULL);
1105                 _LT_ASSERT(n->next->b_index == block);
1106                 _LT_ASSERT(n->next->iindex == iindex);
1107
1108                 n->next = n->next->next;
1109         }
1110 }
1111
1112 void add_def_site(struct lifetime *lt, int block, int iindex) {
1113         struct site *n;
1114
1115         /* SSA <-> only one definition per lifetime! */
1116         _LT_ASSERT(lt->def == NULL);
1117         n = DNEW(struct site);
1118         n->b_index = block;
1119         n->iindex = iindex;
1120         n->next = NULL;
1121         lt->def = n;
1122 }
1123
1124 struct lifetime *get_ss_lifetime(lsradata *ls, stackptr s) {
1125         struct lifetime *n;
1126
1127         if (s->varnum >= 0) { /* new stackslot lifetime */
1128                 if (-ls->v_index - 1 >= ls->maxlifetimes) {
1129                         printf("%i %i\n", -ls->v_index - 1, ls->maxlifetimes);
1130                 }
1131                 _LT_ASSERT(-ls->v_index - 1 < ls->maxlifetimes);
1132
1133                 n = &(ls->lifetime[-ls->v_index - 1]);
1134                 n->type = s->type;
1135                 n->v_index = ls->v_index--;
1136                 n->usagecount = 0;
1137
1138                 n->bb_last_use = -1;
1139                 n->bb_first_def = -1;
1140                 n->local_ss = NULL;
1141                 n->savedvar = 0;
1142                 n->flags = 0;
1143
1144                 n->use = NULL;
1145                 n->def = NULL;
1146                 n->last_use = NULL;
1147         } else {
1148                 _LT_ASSERT(-s->varnum - 1 < ls->maxlifetimes);
1149                 n = &(ls->lifetime[-s->varnum - 1]);
1150         }
1151
1152         lsra_add_ss( n, s);
1153         return n;
1154 }
1155
1156 #define lsra_new_stack(ls, s, block, instr) \
1157         if ((s)->varkind != ARGVAR) _lsra_new_stack(ls, s, block, instr, LSRA_STORE)
1158 void _lsra_new_stack(lsradata *ls, stackptr s, int block, int instr, int store)
1159 {
1160         struct lifetime *n;
1161
1162         if (s->varkind == LOCALVAR) {
1163 /*              _LT_ASSERT(0); */
1164                 lsra_usage_local(ls, s->varnum, s->type, block, instr, LSRA_LOAD);
1165         } else {
1166
1167
1168                 n=get_ss_lifetime( ls, s );
1169                 if (store == LSRA_STORE) {
1170                         /* for LSRA_BB_[IN|OUT] do not add a def site, just add s to */
1171                         /* local_ss */
1172                         add_def_site(n, block, instr);
1173                 }
1174         }
1175 }
1176
1177 #define lsra_from_stack(ls, s, block, instr) \
1178         if ((s)->varkind != ARGVAR) _lsra_from_stack(ls, s, block, instr, LSRA_LOAD)
1179 #define lsra_pop_from_stack(ls, s, block, instr) \
1180         if ((s)->varkind != ARGVAR) _lsra_from_stack(ls, s, block, instr, LSRA_POP)
1181 void _lsra_from_stack(lsradata *ls, stackptr s, int block, int instr, int store)
1182 {
1183         struct lifetime *n;
1184
1185         if (s->varkind == LOCALVAR) {
1186 /*              _LT_ASSERT(0); */
1187                 lsra_usage_local(ls, s->varnum, s->type, block, instr, LSRA_LOAD);
1188         } else /* if (s->varkind != ARGVAR) */ {
1189                 if (s->varkind == STACKVAR ) {
1190 /*                      _LT_ASSERT(0); */
1191                         printf("---------STACKVAR left over! \n");
1192                         /* No STACKVARS possible with lsra! */
1193                         s->varkind = TEMPVAR;
1194                 }
1195         }
1196
1197                 n=get_ss_lifetime( ls, s );
1198
1199                 /* LSRA_POP -> invalidate Stackslot ?! */
1200 #ifdef USAGE_COUNT
1201                 n->usagecount += ls->nesting[block];
1202 #endif
1203
1204                 add_use_site(n, block, instr);
1205
1206 }
1207
1208 void lsra_usage_local(lsradata *ls, s4 v_index, int type, int block, int instr,
1209                                           int store)
1210 {
1211         struct lifetime *n;
1212
1213         n = &(ls->lifetime[ls->maxlifetimes + v_index]);
1214
1215         if (n->type == -1) { /* new local lifetime */
1216                 n->local_ss=NULL;
1217                 n->v_index=v_index;
1218                 n->type=type;
1219                 n->savedvar = SAVEDVAR;
1220                 n->flags = 0;
1221                 n->usagecount = 0;
1222
1223                 n->bb_last_use = -1;
1224                 n->bb_first_def = -1;
1225
1226                 n->use = NULL;
1227                 n->def = NULL;
1228                 n->last_use = NULL;
1229         }
1230         _LT_ASSERT(type == n->type);
1231
1232         /* add access at (block, instr) to instruction list */
1233         /* remember last USE, so only write, if USE Field is undefined (==-1)   */
1234         /* count store as use, too -> defined and not used vars would overwrite */
1235         /* other vars */
1236         if (store == LSRA_LOAD) {
1237 #ifdef USAGE_COUNT
1238                 n->usagecount += ls->nesting[block];
1239 #endif
1240                 add_use_site(n, block, instr);
1241         }
1242         if (store == LSRA_STORE) {
1243                 add_def_site(n, block, instr);
1244         }
1245 }
1246
1247 /***************************************************************************
1248 use sites: dead code elemination, LifenessAnalysis
1249 def sites: dead code elemination
1250 ***************************************************************************/
1251 void _scan_lifetimes(registerdata *rd, lsradata *ls, graphdata *gd,
1252                                         basicblock *bptr)
1253 {
1254 /*      methodinfo         *lm; */
1255         builtintable_entry *bte;
1256         methoddesc         *md;
1257         int i, j, t, v;
1258         int opcode;
1259         int iindex, b_index;
1260         stackptr    src;
1261         stackptr    dst;
1262         instruction *iptr;
1263
1264         struct lifetime *lt;
1265
1266
1267         if (bptr->flags >= BBREACHED) {
1268
1269                 b_index = bptr->nr;
1270
1271                 /* get instruction count for BB */
1272                 iindex = bptr->icount - 1;
1273                 /* regard not setup new BB with maybee just in and outstack */
1274                 if (iindex < 0) iindex = 0;
1275
1276                 /* Regard phi_functions (Definition of target, Use of source) */
1277                 for(i = 0; i < ls->max_vars; i++) {
1278                         if (ls->phi[b_index][i] != NULL) {
1279                                 /* Phi Function for var i at b_index exists */
1280                                 v = ls->phi[b_index][i][0];
1281                                 _LT_ASSERT( v != ls->max_vars_with_indices);
1282                                 if (v >= 0) {
1283                                         /* Local Var */
1284                                         for(t = 0;(t < 5) && (rd->locals[v][t].type==-1); t++);
1285                                         _LT_ASSERT(t != 5);
1286                                         /* Add definition of target add - phi index -1*/
1287                                         lsra_usage_local(ls, v, t, b_index, -i-1,
1288                                                                          LSRA_STORE);
1289                                         /* Add Use of sources */
1290                                         for (j = 1; j <= graph_get_num_predecessor(gd, b_index);
1291                                                  j++) {
1292                                                 if (ls->phi[b_index][i][j] != ls->max_vars_with_indices)
1293                                                         lsra_usage_local(ls, ls->phi[b_index][i][j], t,
1294                                                                                          b_index, -i-1, LSRA_LOAD);
1295                                         }
1296                                 } else {
1297                                         /* Interface Stackslot */
1298                                         /* Add definition of target */
1299                                         lt = &(ls->lifetime[-v-1]);
1300                                         add_def_site(lt, b_index, -i-1);
1301                                         /* add use of sources */
1302                                         for (j = 1; j <= graph_get_num_predecessor(gd, b_index);
1303                                                  j++) {
1304                                                 if (ls->phi[b_index][i][j] != ls->max_vars_with_indices)
1305                                                 {
1306                                                         lt = &(ls->lifetime[-ls->phi[b_index][i][j]-1]);
1307                                                         add_use_site(lt, b_index, -i-1);
1308                                                 }
1309                                         }
1310                                 }
1311                         }
1312                 }
1313
1314                 src = bptr->instack;
1315                 if (bptr->type != BBTYPE_STD) {
1316 #ifdef LT_DEBUG_CHECK
1317                         if (src == NULL) {
1318                            log_text("No Incoming Stackslot for Exception/Subroutine BB\n");
1319                                 _LT_ASSERT(0);
1320                         }
1321 #endif
1322                         _LT_ASSERT(src != NULL);
1323                         lsra_new_stack(ls, src, b_index, 0);
1324                         if (src->varkind == STACKVAR)
1325                                 src->varkind = TEMPVAR;
1326                         src = src->prev;
1327                 }
1328                 for (;src != NULL; src=src->prev) {
1329                         /* no ARGVAR possible at BB Boundaries with LSRA! */
1330                         /* -> change to TEMPVAR                           */
1331
1332                         if (src->varkind == ARGVAR ) {
1333                                 src->varkind = TEMPVAR;
1334                                 /* On Architectures with own return registers a return    */
1335                                 /* stackslot is marked as varkind=ARGVAR with varnum=-1   */
1336                                 /* but for lsra a varkind==TEMPVAR, varnum=-1 would mean, */
1337                                 /* that already a lifetime was allocated! */
1338                                 if (src->varnum < 0) src->varnum = 0;
1339                         }
1340                         else if (src->varkind == LOCALVAR )
1341                                 /* only allowed for topmost ss at sbr or exh entries! */
1342                                 { log_text("LOCALVAR at basicblock instack\n"); exit(1); }
1343                         else {
1344                                 /* no Interfaces (STACKVAR) at BB Boundaries with LSRA! */
1345                                 /* -> change to TEMPVAR                      */
1346                                 if (src->varkind == STACKVAR )
1347                                         src->varkind = TEMPVAR;
1348 /*                              _lsra_new_stack(ls, src, b_index, 0, LSRA_BB_IN); */
1349                                 _lsra_from_stack(ls, src, b_index, 0, LSRA_BB_OUT);
1350                         }
1351                 }
1352                 /* Should not be necessary to check out stackslots, too */
1353                 /* either they are identical to the instacks or handled */
1354                 /* by their phi functions */
1355                 src = bptr->outstack;
1356                 for (;src != NULL; src=src->prev) {
1357                         if (src->varkind == ARGVAR )
1358                                 { log_text("ARGVAR at basicblock outstack\n"); exit(1); }
1359                         else if (src->varkind == LOCALVAR )
1360                                 { log_text("LOCALVAR at basicblock outstack\n"); exit(1); }
1361                         else {
1362                                 /* no Interfaces at BB Boundaries with LSRA! */
1363                                 /* -> change to TEMPVAR                      */
1364                                 if (src->varkind == STACKVAR )
1365                                         src->varkind = TEMPVAR;
1366 /*                              _lsra_from_stack(ls, src, b_index, iindex, LSRA_BB_OUT); */
1367                         }
1368                 }
1369
1370                 if (bptr->iinstr != NULL) {
1371                         /* set iptr to last instruction of BB */
1372                         iptr = bptr->iinstr + iindex;
1373                 } else
1374                         iindex = -1;
1375
1376                 for (;iindex >= 0; iindex--, iptr--)  {
1377                         /* Get source and destination Stack for the current           */
1378                         /* instruction. Destination stack is available as iptr->dst   */
1379                         dst = iptr->dst;
1380                         /* source stack is either the destination stack of the previos*/
1381                         /* instruction, or the basicblock instack for the             */
1382                         /* first instruction */
1383                         if (iindex) /* != 0 is > 0 here, since iindex ist always >= 0 */
1384                                 src=(iptr-1)->dst;
1385                         else
1386                                 src=bptr->instack;
1387
1388                         opcode = iptr->opc;
1389                         switch (opcode) {
1390
1391                                 /* pop 0 push 0 */
1392                         case ICMD_RET:
1393                                 /* local read (return adress) */
1394                                 lsra_usage_local(ls, iptr->op1, TYPE_ADR, b_index, iindex,
1395                                                                  LSRA_LOAD);
1396                                 break;
1397                         case ICMD_NOP:
1398 /*                      case ICMD_ELSE_ICONST: */
1399                         case ICMD_CHECKNULL:
1400                         case ICMD_JSR:
1401                         case ICMD_RETURN:
1402                         case ICMD_GOTO:
1403                         case ICMD_PUTSTATICCONST:
1404                         case ICMD_INLINE_START:
1405                         case ICMD_INLINE_END:
1406                         case ICMD_INLINE_GOTO:
1407                                 break;
1408
1409                         case ICMD_IINC:
1410                                 /* local = local+<const> */
1411                                 lsra_usage_local(ls, iptr->op1, TYPE_INT, b_index, iindex,
1412                                                                  LSRA_LOAD);
1413                                 lsra_usage_local(ls, iptr->val._i.op1_t, TYPE_INT, b_index,
1414                                                                  iindex, LSRA_STORE);
1415                                 break;
1416
1417                                 /* pop 0 push 1 const: const->stack */
1418                         case ICMD_ICONST:
1419                         case ICMD_LCONST:
1420                         case ICMD_FCONST:
1421                         case ICMD_DCONST:
1422                         case ICMD_ACONST:
1423                                 /* new stack slot */
1424                                 lsra_new_stack(ls, dst, b_index, iindex);
1425                                 break;
1426
1427                                 /* pop 0 push 1 load: local->stack */
1428                         case ICMD_ILOAD:
1429                         case ICMD_LLOAD:
1430                         case ICMD_FLOAD:
1431                         case ICMD_DLOAD:
1432                         case ICMD_ALOAD:
1433                                 if (dst->varkind != LOCALVAR) {
1434                                         /* local->value on stack */
1435                                         lsra_usage_local(ls, iptr->op1, opcode - ICMD_ILOAD,
1436                                                                          b_index,  iindex, LSRA_LOAD);
1437                                         lsra_new_stack(ls, dst, b_index, iindex);
1438                                 } else /* if (dst->varnum != iptr->op1) */ {
1439                                         /* local -> local */
1440                                         lsra_usage_local(ls, iptr->op1, opcode - ICMD_ILOAD,
1441                                                                          b_index,  iindex,LSRA_LOAD);
1442                                         lsra_usage_local(ls, dst->varnum, opcode - ICMD_ILOAD,
1443                                                                          b_index, iindex, LSRA_STORE);
1444                                 }
1445
1446                                 break;
1447
1448                                 /* pop 2 push 1 */
1449                                 /* Stack(arrayref,index)->stack */
1450                         case ICMD_IALOAD:
1451                         case ICMD_LALOAD:
1452                         case ICMD_FALOAD:
1453                         case ICMD_DALOAD:
1454                         case ICMD_AALOAD:
1455
1456                         case ICMD_BALOAD:
1457                         case ICMD_CALOAD:
1458                         case ICMD_SALOAD:
1459                                 /* stack->index */
1460                                 lsra_from_stack(ls, src, b_index, iindex);
1461                                 /* stack->arrayref */
1462                                 lsra_from_stack(ls, src->prev, b_index, iindex);
1463                                 /* arrayref[index]->stack */
1464                                 lsra_new_stack(ls, dst, b_index, iindex);
1465                                 break;
1466
1467                                 /* pop 3 push 0 */
1468                                 /* stack(arrayref,index,value)->arrayref[index]=value */
1469                         case ICMD_IASTORE:
1470                         case ICMD_LASTORE:
1471                         case ICMD_FASTORE:
1472                         case ICMD_DASTORE:
1473                         case ICMD_AASTORE:
1474
1475                         case ICMD_BASTORE:
1476                         case ICMD_CASTORE:
1477                         case ICMD_SASTORE:
1478
1479                                 lsra_from_stack(ls, src,b_index, iindex);
1480                                 lsra_from_stack(ls, src->prev, b_index, iindex);
1481                                 lsra_from_stack(ls, src->prev->prev, b_index, iindex);
1482                                 break;
1483
1484                                 /* pop 1 push 0 store: stack -> local */
1485                         case ICMD_ISTORE:
1486                         case ICMD_LSTORE:
1487                         case ICMD_FSTORE:
1488                         case ICMD_DSTORE:
1489                         case ICMD_ASTORE:
1490                                 if (src->varkind != LOCALVAR) {
1491                                         lsra_from_stack(ls, src, b_index, iindex);
1492                                         lsra_usage_local(ls, iptr->op1, opcode-ICMD_ISTORE,
1493                                                                          b_index, iindex, LSRA_STORE);
1494                                 } else /* if (src->varnum != iptr->op1) */ {
1495                                         lsra_usage_local(ls, iptr->op1, opcode-ICMD_ISTORE,
1496                                                                          b_index, iindex, LSRA_STORE);
1497                                         lsra_usage_local(ls, src->varnum, opcode-ICMD_ISTORE,
1498                                                                          b_index,  iindex, LSRA_LOAD);
1499                                 }
1500                                 break;
1501
1502                                 /* pop 1 push 0 */
1503                         case ICMD_POP: /* throw away a stackslot */
1504                                 /* TODO: check if used anyway (DUP...) and change codegen */
1505                                 /* to ignore this stackslot */
1506 #if 0
1507                                 lsra_pop_from_stack(ls, src, b_index, iindex);
1508 #endif
1509                         break;
1510
1511                                 /* pop 1 push 0 */
1512                         case ICMD_IRETURN:
1513                         case ICMD_LRETURN:
1514                         case ICMD_FRETURN:
1515                         case ICMD_DRETURN:
1516                         case ICMD_ARETURN: /* stack(value) -> [empty]    */
1517
1518                         case ICMD_ATHROW:  /* stack(objref) -> undefined */
1519
1520                         case ICMD_PUTSTATIC: /* stack(value) -> static_field */
1521                         case ICMD_PUTFIELDCONST:
1522
1523                                 /* pop 1 push 0 branch */
1524                         case ICMD_IFNULL: /* stack(value) -> branch? */
1525                         case ICMD_IFNONNULL:
1526
1527                         case ICMD_IFEQ:
1528                         case ICMD_IFNE:
1529                         case ICMD_IFLT:
1530                         case ICMD_IFGE:
1531                         case ICMD_IFGT:
1532                         case ICMD_IFLE:
1533
1534                         case ICMD_IF_LEQ:
1535                         case ICMD_IF_LNE:
1536                         case ICMD_IF_LLT:
1537                         case ICMD_IF_LGE:
1538                         case ICMD_IF_LGT:
1539                         case ICMD_IF_LLE:
1540
1541                                 /* pop 1 push 0 table branch */
1542                         case ICMD_TABLESWITCH:
1543                         case ICMD_LOOKUPSWITCH:
1544
1545                         case ICMD_MONITORENTER:
1546                         case ICMD_MONITOREXIT:
1547                                 lsra_from_stack(ls, src, b_index, iindex);
1548                                 break;
1549
1550                                 /* pop 2 push 0 */
1551                         case ICMD_POP2: /* throw away 2 stackslots */
1552 #if 0
1553                                 /* TODO: check if used anyway (DUP...) and change codegen */
1554                                 /* to ignore this stackslot */
1555                                 lsra_pop_from_stack(ls, src, b_index, iindex);
1556                                 lsra_pop_from_stack(ls, src->prev, b_index, iindex);
1557 #endif
1558                                 break;
1559
1560                                 /* pop 2 push 0 branch */
1561
1562                         case ICMD_IF_ICMPEQ: /* stack (v1,v2) -> branch(v1,v2) */
1563                         case ICMD_IF_ICMPNE:
1564                         case ICMD_IF_ICMPLT:
1565                         case ICMD_IF_ICMPGE:
1566                         case ICMD_IF_ICMPGT:
1567                         case ICMD_IF_ICMPLE:
1568
1569                         case ICMD_IF_LCMPEQ:
1570                         case ICMD_IF_LCMPNE:
1571                         case ICMD_IF_LCMPLT:
1572                         case ICMD_IF_LCMPGE:
1573                         case ICMD_IF_LCMPGT:
1574                         case ICMD_IF_LCMPLE:
1575
1576                         case ICMD_IF_ACMPEQ:
1577                         case ICMD_IF_ACMPNE:
1578
1579                                 /* pop 2 push 0 */
1580                         case ICMD_PUTFIELD: /* stack(objref,value) -> objref = value */
1581
1582                         case ICMD_IASTORECONST:
1583                         case ICMD_LASTORECONST:
1584                         case ICMD_AASTORECONST:
1585                         case ICMD_BASTORECONST:
1586                         case ICMD_CASTORECONST:
1587                         case ICMD_SASTORECONST:
1588                                 lsra_from_stack(ls, src, b_index, iindex);
1589                                 lsra_from_stack(ls, src->prev, b_index, iindex);
1590                                 break;
1591
1592                                 /* pop 0 push 1 dup */
1593                         case ICMD_DUP:
1594                                 /* src == dst->prev */
1595                                 /* ---------------- */
1596                                 /* src -> dst       */
1597
1598                                 /* Add the use site for src==dst */
1599                                 lsra_from_stack(ls, src, b_index, iindex);
1600
1601                                 lsra_new_stack(ls, dst, b_index, iindex);
1602
1603                                 break;
1604
1605                                 /* pop 0 push 2 dup */
1606                         case ICMD_DUP2:
1607                                 /* src       == dst->prev->prev       */
1608                                 /* src->prev == dst->prev->prev->prev */
1609                                 /* ---------------- */
1610                                 /* src       -> dst                   */
1611                                 /* src->prev -> dst->prev             */
1612                                 /* src & src->prev "continue" living -> so no conflicts */
1613                                 /* with dst and dst->prec possible                      */
1614
1615                                 /* add the use site for src == dst->prev->prev */
1616                                 lsra_from_stack(ls, src, b_index, iindex);
1617                                 /* add the use site for src->prev == dst->prev->prev->prev */
1618                                 lsra_from_stack(ls, src->prev, b_index, iindex);
1619
1620
1621                                 lsra_new_stack(ls, dst->prev, b_index, iindex);
1622                                 lsra_new_stack(ls, dst, b_index, iindex);
1623
1624                                 break;
1625
1626                                 /* pop 2 push 3 dup */
1627                         case ICMD_DUP_X1:
1628                                 /* src       -> dst             */
1629                                 /* src->prev -> dst->prev       */
1630                                 /* src       -> dst->prev->prev */
1631                                 /* !!!!!!!!!!!!!!!!!!!!!!!!!!!! */
1632                                 /* Copy Conflicts possible!     */
1633                                 /* -> instack [    t1 t0 ]      */
1634                                 /* -> outstack[ t0 t1 t3 ]      */
1635                                 /* -> t1->t0, t0->t1, t1->t3 !! */
1636                                 /* -> Remove src->prev on iindex+1 instead of iindex! */
1637                                 lsra_from_stack(ls, src, b_index, iindex);
1638                                 lsra_from_stack(ls, src->prev, b_index, iindex);
1639                                 lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
1640                                 lsra_new_stack(ls, dst->prev, b_index, iindex);
1641                                 lsra_new_stack(ls, dst, b_index, iindex);
1642
1643                                 break;
1644
1645                                 /* pop 3 push 4 dup */
1646                         case ICMD_DUP_X2:
1647                                 /* src             -> dst  */
1648                                 /* src             -> dst->prev->prev->prev */
1649                                 /* src->prev       -> dst->prev */
1650                                 /* src->prev->prev -> dst->prev->prev */
1651                                 /* Conflicts possible! -> remove srces at iindex + 1 */
1652                                 lsra_from_stack(ls, src,b_index, iindex);
1653                                 lsra_from_stack(ls, src->prev, b_index, iindex);
1654                                 lsra_from_stack(ls, src->prev->prev, b_index, iindex);
1655                                 lsra_new_stack(ls, dst->prev->prev->prev, b_index, iindex);
1656                                 lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
1657                                 lsra_new_stack(ls, dst->prev, b_index, iindex);
1658                                 lsra_new_stack(ls, dst, b_index, iindex);
1659
1660                                 break;
1661
1662                                 /* pop 3 push 5 dup */
1663                         case ICMD_DUP2_X1:
1664                                 /* src             -> dst  */
1665                                 /* src             -> dst->prev->prev->prev */
1666                                 /* src->prev       -> dst->prev->prev->prev->prev */
1667                                 /* src->prev       -> dst->prev */
1668                                 /* src->prev->prev -> dst->prev->prev */
1669                                 /* Conflicts possible! -> remove srces at iindex + 1 */
1670                                 lsra_from_stack(ls, src, b_index, iindex);
1671                                 lsra_from_stack(ls, src->prev, b_index, iindex);
1672                                 lsra_from_stack(ls, src->prev->prev, b_index, iindex);
1673                                 lsra_new_stack(ls, dst->prev->prev->prev->prev, b_index,
1674                                                            iindex);
1675                                 lsra_new_stack(ls, dst->prev->prev->prev, b_index, iindex);
1676                                 lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
1677                                 lsra_new_stack(ls, dst->prev, b_index, iindex);
1678                                 lsra_new_stack(ls, dst, b_index, iindex);
1679
1680
1681                                 break;
1682
1683                                 /* pop 4 push 6 dup */
1684                         case ICMD_DUP2_X2:
1685                                 /* src                   -> dst  */
1686                                 /* src                   -> dst->prev->prev->prev->prev */
1687                                 /* src->prev         -> dst->prev->prev->prev->prev->prev */
1688                                 /* src->prev             -> dst->prev */
1689                                 /* src->prev->prev       -> dst->prev->prev */
1690                                 /* src->prev->prev->prev -> dst->prev->prev->prev */
1691                                 /* Conflicts possible! -> remove srcs at iindex + 1 */
1692                                 lsra_from_stack(ls, src, b_index, iindex);
1693                                 lsra_from_stack(ls, src->prev, b_index, iindex);
1694                                 lsra_from_stack(ls, src->prev->prev, b_index, iindex);
1695                                 lsra_from_stack(ls, src->prev->prev->prev, b_index, iindex);
1696                                 lsra_new_stack(ls, dst->prev->prev->prev->prev->prev,
1697                                                            b_index, iindex);
1698                                 lsra_new_stack(ls, dst->prev->prev->prev->prev, b_index,
1699                                                            iindex);
1700                                 lsra_new_stack(ls, dst->prev->prev->prev, b_index, iindex);
1701                                 lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
1702                                 lsra_new_stack(ls, dst->prev, b_index, iindex);
1703                                 lsra_new_stack(ls, dst, b_index, iindex);
1704
1705                                 break;
1706
1707                                 /* pop 2 push 2 swap */
1708                         case ICMD_SWAP:
1709                                 /* src                   -> dst->prev  */
1710                                 /* src->prev             -> dst */
1711                                 /* Conflicts possible -> remove src at iindex + 1 */
1712                                 lsra_from_stack(ls, src, b_index, iindex);
1713                                 lsra_from_stack(ls, src->prev, b_index, iindex);
1714                                 lsra_new_stack(ls, dst->prev, b_index, iindex);
1715                                 lsra_new_stack(ls, dst, b_index, iindex);
1716                                 break;
1717
1718                                 /* pop 2 push 1 */
1719
1720                         case ICMD_LADD:
1721                         case ICMD_LSUB:
1722                         case ICMD_LMUL:
1723
1724                         case ICMD_LOR:
1725                         case ICMD_LAND:
1726                         case ICMD_LXOR:
1727
1728                         case ICMD_LSHL:
1729                         case ICMD_LSHR:
1730                         case ICMD_LUSHR:
1731
1732                         case ICMD_IADD:
1733                         case ICMD_IMUL:
1734
1735                         case ICMD_ISHL:
1736                         case ICMD_ISHR:
1737                         case ICMD_IUSHR:
1738                         case ICMD_IAND:
1739                         case ICMD_IOR:
1740                         case ICMD_IXOR:
1741
1742
1743                         case ICMD_FADD:
1744                         case ICMD_FSUB:
1745                         case ICMD_FMUL:
1746
1747                         case ICMD_DADD:
1748                         case ICMD_DSUB:
1749                         case ICMD_DMUL:
1750                         case ICMD_DDIV:
1751                         case ICMD_DREM:
1752                                 lsra_from_stack(ls, src, b_index, iindex);
1753                                 lsra_from_stack(ls, src->prev, b_index, iindex);
1754                                 lsra_new_stack(ls, dst, b_index, iindex);
1755                                 break;
1756
1757                         case ICMD_ISUB:
1758                                 lsra_from_stack(ls, src, b_index, iindex);
1759                                 lsra_from_stack(ls, src->prev,b_index,iindex);
1760                                 lsra_new_stack(ls, dst, b_index, iindex);
1761                                 break;
1762
1763                         case ICMD_LDIV:
1764                         case ICMD_LREM:
1765
1766                         case ICMD_IDIV:
1767                         case ICMD_IREM:
1768
1769                         case ICMD_FDIV:
1770                         case ICMD_FREM:
1771
1772                         case ICMD_LCMP:
1773                         case ICMD_FCMPL:
1774                         case ICMD_FCMPG:
1775                         case ICMD_DCMPL:
1776                         case ICMD_DCMPG:
1777                                 lsra_from_stack(ls, src, b_index, iindex);
1778                                 lsra_from_stack(ls, src->prev, b_index, iindex);
1779                                 lsra_new_stack(ls, dst, b_index, iindex);
1780                                 break;
1781
1782                                 /* pop 1 push 1 */
1783                         case ICMD_LADDCONST:
1784                         case ICMD_LSUBCONST:
1785                         case ICMD_LMULCONST:
1786                         case ICMD_LMULPOW2:
1787                         case ICMD_LDIVPOW2:
1788                         case ICMD_LREMPOW2:
1789                         case ICMD_LANDCONST:
1790                         case ICMD_LORCONST:
1791                         case ICMD_LXORCONST:
1792                         case ICMD_LSHLCONST:
1793                         case ICMD_LSHRCONST:
1794                         case ICMD_LUSHRCONST:
1795
1796                         case ICMD_IADDCONST:
1797                         case ICMD_ISUBCONST:
1798                         case ICMD_IMULCONST:
1799                         case ICMD_IMULPOW2:
1800                         case ICMD_IDIVPOW2:
1801                         case ICMD_IREMPOW2:
1802                         case ICMD_IANDCONST:
1803                         case ICMD_IORCONST:
1804                         case ICMD_IXORCONST:
1805                         case ICMD_ISHLCONST:
1806                         case ICMD_ISHRCONST:
1807                         case ICMD_IUSHRCONST:
1808
1809 /*                      case ICMD_IFEQ_ICONST: */
1810 /*                      case ICMD_IFNE_ICONST: */
1811 /*                      case ICMD_IFLT_ICONST: */
1812 /*                      case ICMD_IFGE_ICONST: */
1813 /*                      case ICMD_IFGT_ICONST: */
1814 /*                      case ICMD_IFLE_ICONST: */
1815
1816                         case ICMD_INEG:
1817                         case ICMD_INT2BYTE:
1818                         case ICMD_INT2CHAR:
1819                         case ICMD_INT2SHORT:
1820                         case ICMD_LNEG:
1821                         case ICMD_FNEG:
1822                         case ICMD_DNEG:
1823
1824                         case ICMD_I2L:
1825                         case ICMD_I2F:
1826                         case ICMD_I2D:
1827                         case ICMD_L2I:
1828                         case ICMD_L2F:
1829                         case ICMD_L2D:
1830                         case ICMD_F2I:
1831                         case ICMD_F2L:
1832                         case ICMD_F2D:
1833                         case ICMD_D2I:
1834                         case ICMD_D2L:
1835                         case ICMD_D2F:
1836
1837                         case ICMD_CHECKCAST:
1838                                 lsra_from_stack(ls, src, b_index, iindex);
1839                                 lsra_new_stack(ls, dst, b_index, iindex);
1840                                 break;
1841
1842                         case ICMD_ARRAYLENGTH:
1843                         case ICMD_INSTANCEOF:
1844
1845                         case ICMD_NEWARRAY:
1846                         case ICMD_ANEWARRAY:
1847
1848                         case ICMD_GETFIELD:
1849                                 lsra_from_stack(ls, src, b_index, iindex);
1850                                 lsra_new_stack(ls, dst, b_index, iindex);
1851                                 break;
1852
1853                                 /* pop 0 push 1 */
1854                         case ICMD_GETSTATIC:
1855
1856                         case ICMD_NEW:
1857                                 lsra_new_stack(ls, dst, b_index, iindex);
1858                                 break;
1859
1860                                 /* pop many push any */
1861
1862                         case ICMD_INVOKESTATIC:
1863                         case ICMD_INVOKESPECIAL:
1864                         case ICMD_INVOKEVIRTUAL:
1865                         case ICMD_INVOKEINTERFACE:
1866                                 INSTRUCTION_GET_METHODDESC(iptr,md);
1867                                 i = md->paramcount;
1868                                 while (--i >= 0) {
1869                                         lsra_from_stack(ls, src, b_index, iindex);
1870                                         src = src->prev;
1871                                 }
1872                                 if (md->returntype.type != TYPE_VOID)
1873                                         lsra_new_stack(ls, dst, b_index, iindex);
1874                                 break;
1875
1876                         case ICMD_BUILTIN:
1877                                 bte = iptr->val.a;
1878                                 md = bte->md;
1879                                 i = md->paramcount;
1880                                 while (--i >= 0) {
1881                                         lsra_from_stack(ls, src, b_index, iindex);
1882                                         src = src->prev;
1883                                 }
1884                                 if (md->returntype.type != TYPE_VOID)
1885                                         lsra_new_stack(ls, dst, b_index, iindex);
1886                                 break;
1887
1888                         case ICMD_MULTIANEWARRAY:
1889                                 i = iptr->op1;
1890                                 while (--i >= 0) {
1891                                         lsra_from_stack(ls, src, b_index, iindex);
1892                                         src = src->prev;
1893                                 }
1894                                 lsra_new_stack(ls, dst, b_index, iindex);
1895                                 break;
1896
1897                         default:
1898 /*                              assert(0); */
1899                                 throw_cacao_exception_exit(string_java_lang_InternalError,
1900                                                                                    "Unknown ICMD %d during register allocation", iptr->opc);
1901                         } /* switch */
1902                 } /* for (;iindex >= 0; iindex--, iptr--) */
1903         } /* if (bptr->flags >= BBREACHED) */
1904 } /* scan_lifetimes */
1905
1906
1907 #ifdef USAGE_COUNT
1908 /*******************************************************************************
1909 true, if i dominates j
1910 *******************************************************************************/
1911 bool dominates(dominatordata *dd, int i, int j) {
1912         bool dominates = false;
1913
1914         while(!dominates && (dd->idom[j] != -1)) {
1915                 dominates = (i == dd->idom[j]);
1916                 j = dd->idom[j];
1917         }
1918         return dominates;
1919 }
1920
1921 /*******************************************************************************
1922 lt_get_nesting
1923
1924 Look for loops in the CFG and set the nesting depth of all Basicblocks in
1925 gd->nesting:
1926
1927 The Loop Header BB h is an element of DF[n] for all Basicblocks n of this loop
1928 So Look through all x element of DF[n] for a backedge n->x. If this
1929 exists, increment nesting for all n with x in DF[n]
1930 *******************************************************************************/
1931 void lt_get_nesting(lsradata *ls, graphdata *gd, dominatordata *dd) {
1932         int i, j, lh;
1933         bitvector loop_header;
1934         worklist *loop, *loop1;
1935
1936         int succ;
1937         graphiterator iter;
1938
1939         int num_loops;
1940
1941         int *loop_parent;
1942         int lh_p;
1943
1944         /* init nesting to 1 and get loop_headers */
1945         ls->nesting = DMNEW(long, ls->basicblockcount);
1946         loop_header = bv_new(ls->basicblockcount);
1947         loop = wl_new(ls->basicblockcount);
1948         num_loops = 0;
1949         for(i = 0; i < ls->basicblockcount; i++) {
1950                 ls->nesting[i] = 1;
1951
1952                 for(succ = graph_get_first_successor(gd, i, &iter); succ != -1;
1953                         succ = graph_get_next(&iter)) {
1954                         for (j = 0; j < dd->num_DF[i]; j++) {
1955                                 if (succ == dd->DF[i][j]) {
1956                                         /* There is an edge from i to DF[i][j] */
1957
1958                                         /* look if DF[i][j] dominates i -> backedge */
1959                                         if (dominates(dd, dd->DF[i][j], i)) {
1960                                                 /* this edge is a backedge */
1961                                                 /* -> DF[i][j] is a loop header */
1962                                                 _LT_CHECK_BOUNDS(dd->DF[i][j], 0, ls->basicblockcount);
1963                                                 if (!bv_get_bit(loop_header, dd->DF[i][j])) {
1964                                                         /* new loop_header found */
1965                                                         num_loops++;
1966                                                         bv_set_bit(loop_header, dd->DF[i][j]);
1967                                                         ls->nesting[dd->DF[i][j]] = 10;
1968                                                 }
1969                                                 wl_add(loop, dd->DF[i][j]);
1970                                         }
1971                                 }
1972                         }
1973                 }
1974         }
1975
1976         loop_parent = DMNEW(int , ls->basicblockcount);
1977         loop1 = wl_new(ls->basicblockcount);
1978
1979         /* look for direct parents of nested loopheaders */
1980         /* (DF[loop_header[i]] has the element loop_header[j] with i != j */
1981         /* TODO: BULLSHIT:unfortunately not such an easy condition ;( */
1982         while(!wl_is_empty(loop)) {
1983                 lh = wl_get(loop);
1984                 wl_add(loop1, lh);
1985
1986                 loop_parent[lh] = -1;
1987
1988                 for (j = 0; j < dd->num_DF[lh]; j++) {
1989                         _LT_CHECK_BOUNDS(dd->DF[lh][j], 0, ls->basicblockcount);
1990                         if (lh != dd->DF[lh][j]) {
1991                                 if (bv_get_bit(loop_header, dd->DF[lh][j])) {
1992 #ifdef LT_DEBUG_VERBOSE
1993                                         if (compileverbose)
1994                                                 if (loop_parent[lh] != -1)
1995                                                         printf("Warning: LoopHeader has more than one parent\n");
1996 #endif
1997 /*                                      _LT_ASSERT( loop_parent[lh] == -1); */
1998                                         loop_parent[lh] = dd->DF[lh][j];
1999                                 }
2000                         }
2001                 }
2002         }
2003
2004         /* create nesting for loopheaders */
2005         while(!wl_is_empty(loop1)) {
2006                 lh = wl_get(loop1);
2007                 for (lh_p = lh; lh_p != -1; lh_p = loop_parent[lh_p]) {
2008                         ls->nesting[lh] *= 10;
2009                 }
2010         }
2011
2012
2013         /* copy loopheader nesting to loop body */
2014         for(i = 0; i < ls->basicblockcount; i++) {
2015                 if (!bv_get_bit(loop_header, i)) {
2016                         /* Do not touch the nesting of a loopheader itself */
2017                         for(j = 0; j < dd->num_DF[i]; j++) {
2018                                 _LT_CHECK_BOUNDS(dd->DF[i][j], 0, ls->basicblockcount);
2019                                 if (bv_get_bit(loop_header, dd->DF[i][j])) {
2020                                         /* DF[i][j] is a loop header -> copy nesting for i */
2021 #ifdef LT_DEBUG_VERBOSE
2022                                         if (compileverbose)
2023                                                 if (ls->nesting[i] != 1)
2024                                                         printf("Warning: More than one loopheader for one BB\n");
2025 /*                                      _LT_ASSERT(ls->nesting[i] == 1); */
2026 #endif
2027                                         ls->nesting[i] = ls->nesting[dd->DF[i][j]];
2028                                 }
2029                         }
2030                 }
2031         }
2032
2033 #ifdef LT_DEBUG_VERBOSE
2034         if (compileverbose) {
2035                 printf("Num Loops: %3i\n",num_loops);
2036                 for(i = 0; i < ls->basicblockcount; i++)
2037                         printf("(BB%3i->N%3li) ",i, ls->nesting[i]);
2038                 printf("\n");
2039         }
2040 #endif
2041 }
2042 #endif
2043
2044
2045 /*
2046  * These are local overrides for various environment variables in Emacs.
2047  * Please do not remove this and leave it at the end of the file, where
2048  * Emacs will automagically detect them.
2049  * ---------------------------------------------------------------------
2050  * Local variables:
2051  * mode: c
2052  * indent-tabs-mode: t
2053  * c-basic-offset: 4
2054  * tab-width: 4
2055  * End:
2056  */