src/vm/jit/allocator/liveness.c

   1 /* src/vm/jit/allocator/liveness.c - liveness analysis for lsra
   2
   3    Copyright (C) 2005, 2006, 2007 R. Grafl, A. Krall, C. Kruegel,
   4    C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
   5    E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
   6    J. Wenninger, 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., 51 Franklin Street, Fifth Floor, Boston, MA
  23    02110-1301, USA.
  24
  25    Contact: cacao@cacaojvm.org
  26
  27    Authors: Christian Ullrich
  28
  29    $Id: liveness.c $
  30
  31 */
  32
  33
  34 #include "config.h"
  35
  36 #include <limits.h>
  37 #include <stdlib.h>
  38
  39 #include "vm/types.h"
  40
  41 #include "mm/memory.h"
  42
  43 #include "toolbox/logging.h"
  44 #include "toolbox/worklist.h"
  45
  46 #include "vm/builtin.h"
  47 #include "vm/exceptions.h"
  48 #include "vm/global.h"
  49 #include "vm/method.h"
  50 #include "vm/resolve.h"
  51 #include "vm/jit/codegen-common.h"
  52 #include "vm/jit/jit.h"
  53 #include "vm/jit/allocator/lsra.h"
  54 #include "vm/jit/allocator/liveness.h"
  55
  56
  57 /* function prototypes */
  58 void liveness_scan_registers_canditates(jitdata *jd, int b_index, int iindex,
  59                                                                                 stackptr src, lv_sets *sets);
  60 void liveness_set_stack(lsradata *ls, int block, int g_iindex, stackptr s,
  61                                                 lv_sets *sets, int op);
  62 void liveness_set_local(lsradata *ls, int block, int g_iindex, s4 v_index,
  63                                                 int type, lv_sets *sets, int op);
  64
  65 void liveness_add_ss(struct lifetime *lt, stackptr s) {
  66         struct stackslot *ss;
  67         /* Stackslot noch nicht eingetragen? */
  68
  69         if (s->varnum != lt->v_index) {
  70                 ss = DNEW(struct stackslot);
  71                 ss->s = s;
  72                 ss->s->varnum = lt->v_index;
  73                 ss->next = lt->local_ss;
  74                 lt->local_ss = ss;
  75                 if (s != NULL) lt->savedvar |= s->flags & SAVEDVAR;
  76                 if (s != NULL) lt->type = s->type;
  77         }
  78 }
  79
  80 void liveness_join_ss( struct lsradata *ls, struct stackelement *in,
  81                                    struct stackelement *out) {
  82         struct lifetime *lt, *lto;
  83         struct stackslot *ss, *ss_last;
  84
  85
  86         if (in->varnum != out->varnum) {
  87                 lt = &(ls->lifetime[-in->varnum - 1]);
  88
  89 #ifdef LV_DEBUG_CHECK
  90                 if (lt->type == -1) {
  91 #ifdef LV_DEBUG_VERBOSE
  92                         log_text("liveness_join_ss: lifetime for instack not found\n");
  93 #endif
  94                         assert(0);
  95                 }
  96 #endif
  97
  98                 if (out->varnum >= 0) { /* no lifetime for this slot till now */
  99                         liveness_add_ss(lt, out);
 100                 } else {
 101                         lto = &(ls->lifetime[-out->varnum - 1]);
 102
 103 #ifdef LV_DEBUG_CHECK
 104                         if (lto->type == -1) {
 105 #ifdef LV_DEBUG_VERBOSE
 106                                 log_text("liveness_join_ss: lifetime for outstack not found\n");
 107 #endif
 108                                 assert(0);
 109                         }
 110 #endif
 111 #ifdef LV_DEBUG_CHECK
 112                         if (lto->type != lt->type) {
 113 #ifdef LV_DEBUG_VERBOSE
 114                                 log_text("liveness_join_ss: in/out stack type mismatch\n");
 115 #endif
 116                                 assert(0);
 117                         }
 118 #endif
 119
 120                         /* take Lifetime lto out of ls->lifetimes */
 121                         lto->type = -1;
 122
 123                         /* merge lto into lt of in */
 124
 125                         /* change varnums of all lto->local_ss->s to lt->v_index */
 126                         ss_last = ss = lto->local_ss;
 127                         while (ss != NULL) {
 128                                 ss_last = ss;
 129                                 ss->s->varnum = lt->v_index;
 130                                 ss = ss->next;
 131                         }
 132                         /* link both lto->local_ss list to lt->local_ss */
 133                         if (ss_last != NULL) {
 134                                 ss_last->next = lt->local_ss;
 135                                 lt->local_ss = lto->local_ss;
 136                         }
 137
 138                         lt->savedvar |= lto->savedvar;
 139                         lt->flags |= lto->flags;
 140                         lt->usagecount += lto->usagecount;
 141
 142                         /*join of [bb|i]_first_def und [bb|i]_last_use */
 143                         if (lto->bb_first_def < lt->bb_first_def) {
 144                                 lt->bb_first_def = lto->bb_first_def;
 145                                 lt->i_first_def = lto->i_first_def;
 146                         } else if ((lto->bb_first_def == lt->bb_first_def) &&
 147                                            ( lto->i_first_def < lt->i_first_def)) {
 148                                 lt->i_first_def = lto->i_first_def;
 149                         }
 150                         if (lto->bb_last_use > lt->bb_last_use) {
 151                                 lt->bb_last_use = lto->bb_last_use;
 152                                 lt->i_last_use = lto->i_last_use;
 153                         } else if ((lto->bb_last_use == lt->bb_last_use) &&
 154                                            ( lto->i_last_use > lt->i_last_use)) {
 155                                 lt->i_last_use = lto->i_last_use;
 156                         }
 157                 }
 158         }
 159 }
 160
 161 /* join instack of Basic Block b_index with outstack of predecessors */
 162 void liveness_join_lifetimes(jitdata *jd, int b_index) {
 163         struct stackelement *in, *i, *out;
 164     struct _list *pred;
 165
 166         lsradata *ls;
 167         methodinfo *m;
 168
 169         ls = jd->ls;
 170         m  = jd->m;
 171
 172         /* do not join instack of Exception Handler */
 173         if (m->basicblocks[b_index].type == BBTYPE_EXH)
 174                 return;
 175         in=m->basicblocks[b_index].instack;
 176         /* do not join first instack element of a subroutine header */
 177         if (m->basicblocks[b_index].type == BBTYPE_SBR)
 178                 in=in->prev;
 179
 180         if (in != NULL) {
 181                 for (pred = ls->pred[b_index]; pred != NULL; pred = pred->next) {
 182                         out = m->basicblocks[pred->value].outstack;
 183                         for (i=in; (i != NULL); i = i->prev, out=out->prev) {
 184                                 liveness_join_ss(ls, i, out);
 185                         }
 186                 }
 187         }
 188 }
 189
 190 void liveness_setup(jitdata *jd) {
 191         int i, icount, b_index;
 192         stackptr src;
 193         methodinfo *m;
 194         lsradata *ls;
 195
 196         ls = jd->ls;
 197         m  = jd->m;
 198
 199         ls->icount_block = DMNEW(int, m->basicblockcount);
 200         ls->icount_block[0] = icount = 0;
 201         for(i = 0; i < m->basicblockcount; i++) {
 202                 if (i != 0) {
 203                         /* create a global instruction index in icount_block */
 204                         if (ls->sorted[i-1] != -1)
 205                                 icount += m->basicblocks[ ls->sorted[i-1] ].icount;
 206                                 ls->icount_block[i] = icount;
 207                 }
 208
 209                 if ((b_index = ls->sorted[i]) != -1) {
 210                         /* 'valid' Basic Block */
 211
 212                         /* adapt in- and outstacks for LSRA */
 213                         src = m->basicblocks[b_index].instack;
 214                         if (m->basicblocks[b_index].type != BBTYPE_STD) {
 215 #ifdef LV_DEBUG_CHECK
 216                                 if (src == NULL) {
 217 #ifdef LV_DEBUG_VERBOSE
 218                                 log_text("No Incoming Stackslot for Exception/Subroutine BB\n");
 219 #endif
 220                                         assert(0);
 221                                 }
 222 #endif
 223                                 if (src->varkind == STACKVAR)
 224                                         src->varkind = TEMPVAR;
 225                                 src = src->prev;
 226                         }
 227                         for (;src != NULL; src=src->prev) {
 228                                 /* no ARGVAR possible at BB Boundaries with LSRA! */
 229                                 /* -> change to TEMPVAR                           */
 230                                 if (src->varkind == ARGVAR ) {
 231                                         src->varkind = TEMPVAR;
 232                                         /* On Architectures with own return registers a return
 233                                            stackslot is marked as varkind=ARGVAR with varnum=-1
 234                                            but for lsra a varkind==TEMPVAR, varnum=-1 would mean,
 235                                            that already a lifetime was allocated! */
 236                                         if (src->varnum < 0) src->varnum = 0;
 237                                 }
 238                                 else if (src->varkind == LOCALVAR ) {
 239                                         /* only allowed for top most ss at sbr or exh entries! */
 240 #ifdef LV_DEBUG_VERBOSE
 241                                         log_text("LOCALVAR at basicblock instack\n");
 242 #endif
 243                                         abort();
 244                                 } else {
 245                                         if (src->varkind == STACKVAR )
 246                                                 /* no Interfaces at BB Boundaries with LSRA! */
 247                                                 /* -> change to TEMPVAR                      */
 248                                                 src->varkind = TEMPVAR;
 249                                 }
 250                         }
 251
 252                         src = m->basicblocks[b_index].outstack;
 253                         for (;src != NULL; src=src->prev) {
 254                                 if (src->varkind == ARGVAR ) {
 255 #ifdef LV_DEBUG_VERBOSE
 256                                         log_text("ARGVAR at basicblock outstack\n");
 257 #endif
 258                                         abort();
 259                                 } else if (src->varkind == LOCALVAR ) {
 260 #ifdef LV_DEBUG_VERBOSE
 261                                         log_text("LOCALVAR at basicblock outstack\n");
 262 #endif
 263                                         abort();
 264                                 } else {
 265                                         /* no Interfaces at BB Boundaries with LSRA! */
 266                                         /* -> change to TEMPVAR                      */
 267                                         if (src->varkind == STACKVAR )
 268                                                 src->varkind = TEMPVAR;
 269                                 }
 270                         }
 271                 }
 272         }
 273 }
 274
 275 void liveness_init(jitdata *jd) {
 276         int i, b_index, len;
 277         int lifetimes;
 278         stackptr src, dst;
 279         instruction *iptr;
 280         methodinfo *m;
 281         lsradata *ls;
 282
 283         ls = jd->ls;
 284         m  = jd->m;
 285
 286         lifetimes = 0;
 287
 288         for(i = 0; i < m->basicblockcount; i++) {
 289                 if ((b_index = ls->sorted[i]) != -1) {
 290                         /* 'valid' Basic Block */
 291
 292                         /* Scan Number of Stack Lifetimes */
 293                         lifetimes += m->basicblocks[b_index].indepth;
 294
 295                         dst = m->basicblocks[b_index].instack;
 296                         len = m->basicblocks[b_index].icount;
 297                         iptr = m->basicblocks[b_index].iinstr;
 298                         for (;len>0; len--, iptr++) {
 299                                 src = dst;
 300                                 dst = iptr->dst;
 301
 302                                 switch(iptr->opc) {
 303                                 case ICMD_SWAP:
 304                                 case ICMD_DUP2:
 305                                         lifetimes += 2;
 306                                         break;
 307                                 case ICMD_DUP_X1:
 308                                         lifetimes += 3;
 309                                         break;
 310                                 case ICMD_DUP2_X1:
 311                                         lifetimes += 5;
 312                                         break;
 313                                 case ICMD_DUP_X2:
 314                                         lifetimes += 4;
 315                                         break;
 316                                 case ICMD_DUP2_X2:
 317                                         lifetimes += 6;
 318                                         break;
 319
 320                                 default:
 321                                         if (( dst != NULL) && (src != dst))
 322                                                 lifetimes++;
 323                                 }
 324                         }
 325                 }
 326         }
 327         ls->maxlifetimes = lifetimes;
 328         ls->lifetimecount = lifetimes + jd->maxlocals * (TYPE_ADR+1);
 329 }
 330
 331 void liveness_scan_basicblock(jitdata *jd, int b_index,
 332                                                           lv_sets *sets, int lifetimes) {
 333         int iindex;
 334         stackptr    src;
 335         instruction *iptr;
 336         int i;
 337         methodinfo *m;
 338         lsradata *ls;
 339
 340         ls = jd->ls;
 341         m  = jd->m;
 342
 343         src = m->basicblocks[b_index].instack;
 344
 345         iindex = m->basicblocks[b_index].icount - 1;
 346         /* set iptr to last instruction of BB */
 347         iptr = m->basicblocks[b_index].iinstr + iindex;
 348
 349         bv_reset(sets->in, lifetimes);
 350
 351         for (;iindex >= 0; iindex--, iptr--)  {
 352                 /* get source Stack for the current instruction     */
 353                 /* destination stack is available as iptr->dst                      */
 354                 /* source stack is either the destination stack of the previos      */
 355                 /* instruction, or the basicblock instack for the first instruction */
 356                 if (iindex) /* != 0 is > 0 here, since iindex ist always >= 0 */
 357                         src=(iptr-1)->dst;
 358                 else
 359                         src=m->basicblocks[b_index].instack;
 360
 361                 /* Reset kill and gen bitvectors for use in */
 362                 /* liveness_scan_register_canditates */
 363
 364                 bv_reset(sets->kill, lifetimes);
 365                 bv_reset(sets->gen, lifetimes);
 366
 367                 /* get gen and kill set of instruction */
 368
 369                 liveness_scan_registers_canditates(jd, b_index, iindex, src, sets);
 370
 371                 /* tmp = out(instr) - kill(instr) */
 372
 373                 bv_minus(sets->tmp, sets->out, sets->kill, lifetimes);
 374
 375                 /* in  = gen(instr) union tmp = gen union (out - kill) */
 376
 377                 bv_union(sets->in, sets->gen, sets->tmp, lifetimes);
 378
 379                 /* Set SAVEDVAR flag for locals */
 380
 381                 if (op_needs_saved[iptr->opc])
 382                         for(i = ls->maxlifetimes; i < ls->lifetimecount; i++)
 383                                 if (!ls->lifetime[i].savedvar)
 384                                         if ( bv_get_bit(sets->in,i) && bv_get_bit(sets->out,i) )
 385                                                 ls->lifetime[i].savedvar = SAVEDVAR;
 386
 387         /* out(instr-1) = in(instr) (only one successor)*/
 388
 389                 bv_copy(sets->out, sets->in, lifetimes);
 390         }
 391         /* create gen sets for incoming stackslots */
 392
 393         /* global instruction index for bb b_index */
 394
 395         iindex = ls->icount_block[ls->sorted_rev[b_index]];
 396         bv_reset(sets->kill, lifetimes);
 397         bv_reset(sets->gen, lifetimes);
 398         src = m->basicblocks[b_index].instack;
 399         if (m->basicblocks[b_index].type != BBTYPE_STD) {
 400                 liveness_set_stack(ls, b_index, iindex, src, sets, LV_KILL);
 401                 src = src->prev;
 402         }
 403         for (;src != NULL; src=src->prev) {
 404                 /* only TEMP or LOCALVAR by now possible      */
 405                 /* liveness_set_stack redirects for LOCALVARS */
 406                 liveness_set_stack(ls, b_index, iindex, src,    sets, LV_GEN);
 407                 _LV_ASSERT( ((src->varkind == LOCALVAR) || (src->varkind == TEMPVAR)) );
 408         }
 409         /* in  = gen union (out - kill) */
 410         bv_minus(sets->tmp, sets->out, sets->kill, lifetimes);
 411         bv_union(sets->in, sets->gen, sets->tmp, lifetimes);
 412 }
 413
 414 void liveness(jitdata *jd) {
 415         bitvector *out;
 416         bitvector *in;
 417         bitvector params;
 418         char *buff;
 419         worklist *W;
 420         int b_index;
 421     struct _list *succ;
 422         struct _list *pred;
 423         bitvector visited;
 424         lv_sets   sets;
 425         int       i, p, t;
 426         methoddesc *md;
 427 #ifdef LV_DEBUG_CHECK
 428         stackptr s;
 429 #endif
 430         methodinfo *m;
 431         registerdata *rd;
 432         lsradata *ls;
 433         /***************************************************************************
 434  TODO:
 435  - Exact Lifeness Information for intra Basic Blocks Stackslots are trivial
 436  They should not be included in the gen, kill, in and out sets to improve
 437  performance.
 438  - Local Vars as represented in rd->locals "are quite sparse". An intermediate
 439  representation for really used index/type pairs should be implemented.
 440         ***************************************************************************/
 441
 442         ls = jd->ls;
 443         m  = jd->m;
 444         rd = jd->rd;
 445
 446         if (ls->lifetimecount == 0)
 447                 return;
 448         ls->lifetime = DMNEW(struct lifetime, ls->lifetimecount);
 449         for (i=0; i < ls->lifetimecount; i++) ls->lifetime[i].type = -1;
 450
 451         sets.gen = bv_new(ls->lifetimecount);
 452         sets.kill = bv_new(ls->lifetimecount);
 453         sets.tmp = bv_new(ls->lifetimecount);
 454         sets.out = bv_new(ls->lifetimecount);
 455         sets.in =  bv_new(ls->lifetimecount);
 456
 457         params =  bv_new(ls->lifetimecount);
 458
 459         visited = bv_new(m->basicblockcount);
 460         buff = DMNEW(char, ls->lifetimecount+1);
 461
 462         out = DMNEW(bitvector, m->basicblockcount);
 463         in  = DMNEW(bitvector, m->basicblockcount);
 464         for(i = 0; i < m->basicblockcount; i++) {
 465                 out[i] = bv_new(ls->lifetimecount);
 466                 in[i]  = bv_new(ls->lifetimecount);
 467         }
 468
 469         /* set in[0] to arguments */
 470         /* <-> kill at 0, -1 */
 471         md = m->parseddesc;
 472         for (p = 0, i = 0; p < md->paramcount; p++) {
 473                 t = md->paramtypes[p].type;
 474
 475                 if (rd->locals[i][t].type >= 0)
 476                         /* Param to Local init happens before normal Code */
 477                         liveness_set_local(ls, 0, -1, i, t, &sets, LV_KILL);
 478                 i++;
 479                 if (IS_2_WORD_TYPE(t))    /* increment local counter a second time  */
 480                         i++;                  /* for 2 word types */
 481         }  /* end for */
 482         bv_copy(params, sets.kill, ls->lifetimecount);
 483
 484         /* fill Worklist so that last node will be taken out first */
 485         W = wl_new(m->basicblockcount);
 486         for (i = 0; i < m->basicblockcount; i++)
 487                 if (ls->sorted[i] != -1)
 488                         wl_add(W, ls->sorted[i]);
 489
 490         /* Worklist algorithm*/
 491         while (!wl_is_empty(W)) {
 492                 b_index = wl_get(W);
 493
 494                 /* out[b_index] = for all s element of successors(b_index) union in[s]*/
 495                 for (succ = ls->succ[b_index]; succ != NULL; succ = succ->next)
 496                         bv_union(out[b_index], out[b_index], in[succ->value],
 497                                          ls->lifetimecount);
 498
 499                 bv_copy(sets.out, out[b_index], ls->lifetimecount);
 500
 501                 /* compute in[b_index] */
 502                 liveness_scan_basicblock(jd, b_index, &sets, ls->lifetimecount);
 503
 504                 if (!bv_get_bit(visited, b_index)) {
 505                         liveness_join_lifetimes(jd, b_index);
 506                         bv_set_bit(visited, b_index);
 507                 }
 508
 509                 if (!bv_equal(sets.in, in[b_index], ls->lifetimecount)) {
 510                         bv_copy(in[b_index], sets.in, ls->lifetimecount);
 511                         for(pred = ls->pred[b_index]; pred != NULL; pred = pred->next)
 512                                 wl_add(W, pred->value);
 513                 }
 514         }
 515
 516 #ifdef LV_DEBUG_CHECK
 517         s = m->basicblocks[b_index].instack;
 518         if ((s != NULL) && (m->basicblocks[b_index].flags != BBTYPE_STD))
 519                 s = s->prev;
 520         for( ; s != NULL; s = s->prev) {
 521 #ifdef LV_DEBUG_VERBOSE
 522                 if (!bv_get_bit(in[b_index], -s->varnum - 1)) {
 523                         log_text("liveness: Error In Stacklot not live!\n");
 524                 }
 525 #endif
 526                 _LV_ASSERT( (bv_get_bit(in[b_index], -s->varnum - 1)) );
 527         }
 528 #endif
 529
 530         for (i = 0; i < m->basicblockcount; i++)
 531                 if ((b_index=ls->sorted[i]) != -1) {
 532                         for(t = 0; t < ls->lifetimecount; t++) {
 533                                 if (ls->lifetime[t].type != -1) {
 534                                         if (bv_get_bit(in[b_index], t)) {
 535                                                 p = ls->icount_block[ls->sorted_rev[b_index]];
 536                                                 if (p < ls->lifetime[t].i_first_def)
 537                                                         ls->lifetime[t].i_first_def = p;
 538                                         }
 539                                         if (bv_get_bit(out[b_index], t)) {
 540                                                 p =
 541    ls->icount_block[ls->sorted_rev[b_index]]+m->basicblocks[b_index].icount - 1;
 542                                                 if (p > ls->lifetime[t].i_last_use)
 543                                                         ls->lifetime[t].i_last_use = p;
 544                                         }
 545                                 }
 546                         }
 547                 }
 548
 549 }
 550
 551 struct lifetime *liveness_get_ss_lifetime(lsradata *ls, stackptr s) {
 552         struct lifetime *n;
 553
 554         if (s->varnum >= 0) { /* new stackslot lifetime */
 555 #ifdef LV_DEBUG_VERBOSE
 556                 if (-ls->v_index - 1 >= ls->maxlifetimes) {
 557                         printf("%i %i\n", -ls->v_index - 1, ls->maxlifetimes);
 558                 }
 559 #endif
 560                 _LV_ASSERT(-ls->v_index - 1 < ls->maxlifetimes);
 561
 562                 n = &(ls->lifetime[-ls->v_index - 1]);
 563                 n->type = s->type;
 564                 n->v_index = ls->v_index--;
 565                 n->usagecount = 0;
 566
 567                 n->i_last_use = -2;
 568                 n->i_first_def = INT_MAX;
 569                 n->local_ss = NULL;
 570                 n->savedvar = 0;
 571                 n->flags = 0;
 572         } else
 573                 n = &(ls->lifetime[-s->varnum - 1]);
 574
 575         liveness_add_ss( n, s);
 576         return n;
 577 }
 578
 579 void liveness_set_stack(lsradata *ls, int block, int g_iindex, stackptr s,
 580                                                 lv_sets *sets,
 581                                                 int op) {
 582         struct lifetime *n;
 583
 584         if (s->varkind == LOCALVAR) {
 585                 liveness_set_local(ls, block, g_iindex, s->varnum, s->type, sets, op);
 586         } else if (s->varkind == TEMPVAR) {
 587                 n = liveness_get_ss_lifetime(ls, s);
 588                 if (op == LV_KILL) {
 589                         bv_set_bit(sets->kill, -s->varnum - 1);
 590                         if (n->i_first_def > g_iindex) {
 591                                 n->i_first_def = g_iindex;
 592                         }
 593                 } else {
 594                         /* LV_GEN */
 595                         bv_set_bit(sets->gen, -s->varnum - 1);
 596                         if (n->i_last_use < g_iindex) {
 597                                 n->i_last_use = g_iindex;
 598                         }
 599                 }
 600                 n->usagecount+=ls->nesting[ls->sorted_rev[block]];
 601         }
 602 }
 603
 604 void liveness_set_local(lsradata *ls, int block, int g_iindex, s4 v_index,
 605                                                 int type, lv_sets *sets, int op) {
 606         struct lifetime *n;
 607
 608         n = &(ls->lifetime[ ls->maxlifetimes + v_index * (TYPE_ADR+1) + type]);
 609
 610         if (n->type == -1) { /* new local lifetime */
 611                 n->local_ss=NULL;
 612                 n->v_index=v_index;
 613                 n->type=type;
 614                 /* TODO: Look if local really needs to be a savedvar */
 615                 n->savedvar = 0; /* SAVEDVAR; */
 616                 n->flags = 0;
 617                 n->usagecount = 0;
 618
 619                 n->i_last_use = -2;
 620                 n->i_first_def = INT_MAX;
 621         }
 622         n->usagecount+=ls->nesting[ls->sorted_rev[block]];
 623         if (op == LV_KILL) {
 624                 bv_set_bit(sets->kill, ls->maxlifetimes + v_index * (TYPE_ADR+1)+ type);
 625                 if (n->i_first_def > g_iindex) {
 626                         n->i_first_def = g_iindex;
 627                 }
 628         } else {
 629                 /* LV_GEN */
 630                 bv_set_bit(sets->gen, ls->maxlifetimes + v_index * (TYPE_ADR+1) + type);
 631                 if (n->i_last_use < g_iindex) {
 632                         n->i_last_use = g_iindex;
 633                 }
 634         }
 635 }
 636
 637 void liveness_scan_registers_canditates(jitdata *jd, int b_index, int iindex,
 638                                                                                 stackptr src, lv_sets *sets)
 639 {
 640 /*      methodinfo         *lm; */
 641         builtintable_entry *bte;
 642         methoddesc         *md;
 643         int i, g_iindex;
 644         instruction *iptr;
 645         stackptr    dst;
 646         methodinfo *m;
 647         lsradata   *ls;
 648
 649         m  = jd->m;
 650         ls = jd->ls;
 651
 652         iptr = m->basicblocks[b_index].iinstr + iindex;
 653         dst = iptr->dst;
 654         g_iindex = ls->icount_block[ls->sorted_rev[b_index]] + iindex;
 655         switch (iptr->opc) {
 656                 /* pop 0 push 0 */
 657         case ICMD_RET:
 658                 /* local read (return adress) */
 659                 liveness_set_local(ls, b_index, g_iindex, iptr->op1, TYPE_ADR, sets, LV_GEN);
 660
 661                 break;
 662         case ICMD_NOP:
 663 /*      case ICMD_ELSE_ICONST: */
 664         case ICMD_CHECKNULL:
 665         case ICMD_JSR:
 666         case ICMD_RETURN:
 667         case ICMD_GOTO:
 668         case ICMD_PUTSTATICCONST:
 669         case ICMD_INLINE_START:
 670         case ICMD_INLINE_END:
 671         case ICMD_INLINE_GOTO:
 672                 break;
 673
 674         case ICMD_IINC:
 675                 /* local = local+<const> */
 676                 liveness_set_local(ls, b_index, g_iindex, iptr->op1, TYPE_INT, sets,  LV_GEN);
 677                 liveness_set_local(ls, b_index, g_iindex, iptr->op1, TYPE_INT, sets,  LV_KILL);
 678                 break;
 679
 680                 /* pop 0 push 1 const: const->stack */
 681         case ICMD_ICONST:
 682         case ICMD_LCONST:
 683         case ICMD_FCONST:
 684         case ICMD_DCONST:
 685         case ICMD_ACONST:
 686                 /* new stack slot */
 687                 liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
 688                 break;
 689
 690                 /* pop 0 push 1 load: local->stack */
 691         case ICMD_ILOAD:
 692         case ICMD_LLOAD:
 693         case ICMD_FLOAD:
 694         case ICMD_DLOAD:
 695         case ICMD_ALOAD:
 696                 if (dst->varkind != LOCALVAR) {
 697                         /* local->value on stack */
 698                         liveness_set_local(ls, b_index, g_iindex, iptr->op1,
 699                                                            iptr->opc - ICMD_ILOAD, sets, LV_GEN);
 700                         /* value->stack */
 701                         liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
 702                 } else /* if (dst->varnum != iptr->op1) */ {
 703                         /* local -> local */
 704                         liveness_set_local(ls, b_index, g_iindex, iptr->op1,
 705                                                            iptr->opc - ICMD_ILOAD, sets, LV_GEN);
 706                         liveness_set_local(ls, b_index, g_iindex, dst->varnum,
 707                                                            iptr->opc - ICMD_ILOAD, sets, LV_KILL);
 708                 }
 709                 break;
 710
 711                 /* pop 2 push 1 */
 712                 /* Stack(arrayref,index)->stack */
 713         case ICMD_IALOAD:
 714         case ICMD_LALOAD:
 715         case ICMD_FALOAD:
 716         case ICMD_DALOAD:
 717         case ICMD_AALOAD:
 718
 719         case ICMD_BALOAD:
 720         case ICMD_CALOAD:
 721         case ICMD_SALOAD:
 722                 /* stack->index */
 723                 liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
 724                 /* stack->arrayref */
 725                 liveness_set_stack(ls, b_index, g_iindex, src->prev, sets, LV_GEN);
 726                 /* arrayref[index]->stack */
 727                 liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
 728                 break;
 729
 730                 /* pop 3 push 0 */
 731                 /* stack(arrayref,index,value)->arrayref[index]=value */
 732         case ICMD_IASTORE:
 733         case ICMD_LASTORE:
 734         case ICMD_FASTORE:
 735         case ICMD_DASTORE:
 736         case ICMD_AASTORE:
 737
 738         case ICMD_BASTORE:
 739         case ICMD_CASTORE:
 740         case ICMD_SASTORE:
 741                 /* stack -> value */
 742                 liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
 743                 /* stack -> index*/
 744                 liveness_set_stack(ls, b_index, g_iindex, src->prev, sets, LV_GEN);
 745                 /* stack -> arrayref */
 746                 liveness_set_stack(ls, b_index, g_iindex, src->prev->prev, sets, LV_GEN);
 747                 break;
 748
 749                 /* pop 1 push 0 store: stack -> local */
 750         case ICMD_ISTORE:
 751         case ICMD_LSTORE:
 752         case ICMD_FSTORE:
 753         case ICMD_DSTORE:
 754         case ICMD_ASTORE:
 755                 if (src->varkind != LOCALVAR) {
 756                         /* stack -> value */
 757                         liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
 758                         liveness_set_local(ls, b_index, g_iindex, iptr->op1, iptr->opc - ICMD_ISTORE,
 759                                                            sets, LV_KILL);
 760                 } else {
 761                         liveness_set_local(ls, b_index, g_iindex, src->varnum, iptr->opc-ICMD_ISTORE,
 762                                                            sets, LV_GEN);
 763                         liveness_set_local(ls, b_index, g_iindex, iptr->op1, iptr->opc - ICMD_ISTORE,
 764                                                            sets, LV_KILL);
 765                 }
 766                 break;
 767
 768                 /* pop 1 push 0 */
 769         case ICMD_POP: /* throw away a stackslot */
 770                 /* TODO: check if used anyway (DUP...) and change codegen to */
 771                 /*       ignore this stackslot */
 772                 liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
 773                 break;
 774
 775                 /* pop 1 push 0 */
 776         case ICMD_IRETURN:
 777         case ICMD_LRETURN:
 778         case ICMD_FRETURN:
 779         case ICMD_DRETURN:
 780         case ICMD_ARETURN: /* stack(value) -> [empty]    */
 781
 782         case ICMD_ATHROW:  /* stack(objref) -> undefined */
 783
 784         case ICMD_PUTSTATIC: /* stack(value) -> static_field */
 785         case ICMD_PUTFIELDCONST:
 786
 787                 /* pop 1 push 0 branch */
 788         case ICMD_IFNULL: /* stack(value) -> branch? */
 789         case ICMD_IFNONNULL:
 790
 791         case ICMD_IFEQ:
 792         case ICMD_IFNE:
 793         case ICMD_IFLT:
 794         case ICMD_IFGE:
 795         case ICMD_IFGT:
 796         case ICMD_IFLE:
 797
 798         case ICMD_IF_LEQ:
 799         case ICMD_IF_LNE:
 800         case ICMD_IF_LLT:
 801         case ICMD_IF_LGE:
 802         case ICMD_IF_LGT:
 803         case ICMD_IF_LLE:
 804
 805                 /* pop 1 push 0 table branch */
 806         case ICMD_TABLESWITCH:
 807         case ICMD_LOOKUPSWITCH:
 808
 809         case ICMD_MONITORENTER:
 810         case ICMD_MONITOREXIT:
 811                 /* stack -> value */
 812                 liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
 813                 break;
 814
 815                 /* pop 2 push 0 */
 816         case ICMD_POP2: /* throw away 2 stackslots */
 817                 /* TODO: check if used anyway (DUP...) and change codegen to */
 818                 /*       ignore this stackslot */
 819                 liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
 820                 liveness_set_stack(ls, b_index, g_iindex, src->prev, sets, LV_GEN);
 821                 break;
 822
 823                 /* pop 2 push 0 branch */
 824
 825         case ICMD_IF_ICMPEQ: /* stack (v1,v2) -> branch(v1,v2) */
 826         case ICMD_IF_ICMPNE:
 827         case ICMD_IF_ICMPLT:
 828         case ICMD_IF_ICMPGE:
 829         case ICMD_IF_ICMPGT:
 830         case ICMD_IF_ICMPLE:
 831
 832         case ICMD_IF_LCMPEQ:
 833         case ICMD_IF_LCMPNE:
 834         case ICMD_IF_LCMPLT:
 835         case ICMD_IF_LCMPGE:
 836         case ICMD_IF_LCMPGT:
 837         case ICMD_IF_LCMPLE:
 838
 839         case ICMD_IF_ACMPEQ:
 840         case ICMD_IF_ACMPNE:
 841
 842                 /* pop 2 push 0 */
 843         case ICMD_PUTFIELD: /* stack(objref,value) -> objref = value */
 844
 845         case ICMD_IASTORECONST:
 846         case ICMD_LASTORECONST:
 847         case ICMD_AASTORECONST:
 848         case ICMD_BASTORECONST:
 849         case ICMD_CASTORECONST:
 850         case ICMD_SASTORECONST:
 851                 /* stack -> value*/
 852                 liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
 853                 liveness_set_stack(ls, b_index, g_iindex, src->prev, sets, LV_GEN);
 854                 break;
 855
 856                 /* pop 0 push 1 dup */
 857         case ICMD_DUP:
 858                 /* src == dst->prev */
 859                 /* src -> dst */
 860
 861                 /* src and dst->prev are identical */
 862                 /*              liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_KILL);
 863                                 liveness_set_stack(ls, b_index, g_iindex, dst->prev, sets, LV_GEN);*/
 864
 865                 liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
 866
 867                 break;
 868
 869                 /* pop 0 push 2 dup */
 870         case ICMD_DUP2:
 871                 /* src       ==  dst->prev->prev */
 872                 /* src->prev == dst->prev->prev->prev */
 873                 /* src       ->  dst */
 874                 /* src->prev -> dst->prev-> */
 875
 876                 liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
 877                 liveness_set_stack(ls, b_index, g_iindex, dst->prev, sets, LV_KILL);
 878                 break;
 879
 880                 /* pop 2 push 3 dup */
 881         case ICMD_DUP_X1:
 882                 /* src       -> dst */
 883                 /* src->prev -> dst->prev */
 884                 /* src       -> dst->prev->prev */
 885
 886                 liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
 887                 liveness_set_stack(ls, b_index, g_iindex, dst->prev, sets, LV_KILL);
 888                 liveness_set_stack(ls, b_index, g_iindex, dst->prev->prev, sets,
 889                                                    LV_KILL);
 890                 liveness_set_stack(ls, b_index, g_iindex + 1, src, sets, LV_GEN);
 891                 liveness_set_stack(ls, b_index, g_iindex + 1, src->prev, sets, LV_GEN);
 892                 break;
 893
 894                 /* pop 3 push 4 dup */
 895         case ICMD_DUP_X2:
 896                 /* src             -> dst                   */
 897                 /* src->prev       -> dst->prev             */
 898                 /* src->prev->prev -> dst->prev->prev       */
 899                 /* dst (=src)      -> dst->prev->prev->prev */
 900
 901                 liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
 902                 liveness_set_stack(ls, b_index, g_iindex, dst->prev, sets, LV_KILL);
 903                 liveness_set_stack(ls, b_index, g_iindex, dst->prev->prev, sets,
 904                                                    LV_KILL);
 905                 liveness_set_stack(ls, b_index, g_iindex, dst->prev->prev->prev, sets,
 906                                                    LV_KILL);
 907                 liveness_set_stack(ls, b_index, g_iindex + 1, src, sets, LV_GEN);
 908                 liveness_set_stack(ls, b_index, g_iindex + 1, src->prev, sets, LV_GEN);
 909                 liveness_set_stack(ls, b_index, g_iindex + 1, src->prev->prev, sets,
 910                                                    LV_GEN);
 911                 break;
 912
 913                 /* pop 3 push 5 dup */
 914         case ICMD_DUP2_X1:
 915                 /* src                    -> dst                   */
 916                 /* src->prev              -> dst->prev             */
 917                 /* src->prev->prev        -> dst->prev->prev       */
 918                 /* dst (=src)             -> dst->prev->prev->prev */
 919                 /* dst->prev (=src->prev) -> dst->prev->prev->prev->prev */
 920                 liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
 921                 liveness_set_stack(ls, b_index, g_iindex, dst->prev, sets, LV_KILL);
 922                 liveness_set_stack(ls, b_index, g_iindex, dst->prev->prev, sets,
 923                                                    LV_KILL);
 924                 liveness_set_stack(ls, b_index, g_iindex, dst->prev->prev->prev, sets,
 925                                                    LV_KILL);
 926                 liveness_set_stack(ls, b_index, g_iindex, dst->prev->prev->prev->prev,
 927                                                    sets, LV_KILL);
 928                 liveness_set_stack(ls, b_index, g_iindex + 1, src, sets, LV_GEN);
 929                 liveness_set_stack(ls, b_index, g_iindex + 1, src->prev, sets, LV_GEN);
 930                 liveness_set_stack(ls, b_index, g_iindex + 1, src->prev->prev, sets,
 931                                                    LV_GEN);
 932                 break;
 933
 934                 /* pop 4 push 6 dup */
 935         case ICMD_DUP2_X2:
 936                 /* src                    -> dst                   */
 937                 /* src->prev              -> dst->prev             */
 938                 /* src->prev->prev        -> dst->prev->prev       */
 939                 /* src->prev->prev->prev  -> dst->prev->prev->prev       */
 940                 /* dst (=src)             -> dst->prev->prev->prev->prev */
 941                 /* dst->prev (=src->prev) -> dst->prev->prev->prev->prev->prev */
 942                 liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
 943                 liveness_set_stack(ls, b_index, g_iindex, dst->prev, sets, LV_KILL);
 944                 liveness_set_stack(ls, b_index, g_iindex, dst->prev->prev, sets,
 945                                                    LV_KILL);
 946                 liveness_set_stack(ls, b_index, g_iindex, dst->prev->prev->prev, sets,
 947                                                    LV_KILL);
 948                 liveness_set_stack(ls, b_index, g_iindex, dst->prev->prev->prev->prev,
 949                                                    sets, LV_KILL);
 950                 liveness_set_stack(ls, b_index, g_iindex,
 951                                                    dst->prev->prev->prev->prev->prev, sets, LV_KILL);
 952                 liveness_set_stack(ls, b_index, g_iindex + 1, src, sets, LV_GEN);
 953                 liveness_set_stack(ls, b_index, g_iindex + 1, src->prev, sets, LV_GEN);
 954                 liveness_set_stack(ls, b_index, g_iindex + 1, src->prev->prev, sets,
 955                                                    LV_GEN);
 956                 liveness_set_stack(ls, b_index, g_iindex + 1, src->prev->prev->prev,
 957                                                    sets, LV_GEN);
 958                 break;
 959
 960                 /* pop 2 push 2 swap */
 961         case ICMD_SWAP:
 962                 /* src       -> dst->prev */
 963                 /* src->prev -> dst       */
 964                 liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
 965                 liveness_set_stack(ls, b_index, g_iindex, dst->prev, sets, LV_KILL);
 966                 liveness_set_stack(ls, b_index, g_iindex + 1, src, sets, LV_GEN);
 967                 liveness_set_stack(ls, b_index, g_iindex + 1, src->prev, sets, LV_GEN);
 968                 break;
 969
 970                 /* pop 2 push 1 */
 971
 972         case ICMD_LADD:
 973         case ICMD_LSUB:
 974         case ICMD_LMUL:
 975
 976         case ICMD_LOR:
 977         case ICMD_LAND:
 978         case ICMD_LXOR:
 979
 980         case ICMD_LSHL:
 981         case ICMD_LSHR:
 982         case ICMD_LUSHR:
 983
 984         case ICMD_IADD:
 985         case ICMD_IMUL:
 986
 987         case ICMD_ISHL:
 988         case ICMD_ISHR:
 989         case ICMD_IUSHR:
 990         case ICMD_IAND:
 991         case ICMD_IOR:
 992         case ICMD_IXOR:
 993
 994
 995         case ICMD_FADD:
 996         case ICMD_FSUB:
 997         case ICMD_FMUL:
 998
 999         case ICMD_DADD:
1000         case ICMD_DSUB:
1001         case ICMD_DMUL:
1002         case ICMD_DDIV:
1003         case ICMD_DREM:
1004
1005         case ICMD_ISUB:
1006
1007         case ICMD_LDIV:
1008         case ICMD_LREM:
1009
1010         case ICMD_IDIV:
1011         case ICMD_IREM:
1012
1013         case ICMD_FDIV:
1014         case ICMD_FREM:
1015
1016         case ICMD_LCMP:
1017         case ICMD_FCMPL:
1018         case ICMD_FCMPG:
1019         case ICMD_DCMPL:
1020         case ICMD_DCMPG:
1021                 liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
1022                 liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
1023                 liveness_set_stack(ls, b_index, g_iindex, src->prev, sets, LV_GEN);
1024                 break;
1025
1026                 /* pop 1 push 1 */
1027         case ICMD_LADDCONST:
1028         case ICMD_LSUBCONST:
1029         case ICMD_LMULCONST:
1030         case ICMD_LMULPOW2:
1031         case ICMD_LDIVPOW2:
1032         case ICMD_LREMPOW2:
1033         case ICMD_LANDCONST:
1034         case ICMD_LORCONST:
1035         case ICMD_LXORCONST:
1036         case ICMD_LSHLCONST:
1037         case ICMD_LSHRCONST:
1038         case ICMD_LUSHRCONST:
1039
1040         case ICMD_IADDCONST:
1041         case ICMD_ISUBCONST:
1042         case ICMD_IMULCONST:
1043         case ICMD_IMULPOW2:
1044         case ICMD_IDIVPOW2:
1045         case ICMD_IREMPOW2:
1046         case ICMD_IANDCONST:
1047         case ICMD_IORCONST:
1048         case ICMD_IXORCONST:
1049         case ICMD_ISHLCONST:
1050         case ICMD_ISHRCONST:
1051         case ICMD_IUSHRCONST:
1052
1053 /*      case ICMD_IFEQ_ICONST: */
1054 /*      case ICMD_IFNE_ICONST: */
1055 /*      case ICMD_IFLT_ICONST: */
1056 /*      case ICMD_IFGE_ICONST: */
1057 /*      case ICMD_IFGT_ICONST: */
1058 /*      case ICMD_IFLE_ICONST: */
1059
1060         case ICMD_INEG:
1061         case ICMD_INT2BYTE:
1062         case ICMD_INT2CHAR:
1063         case ICMD_INT2SHORT:
1064         case ICMD_LNEG:
1065         case ICMD_FNEG:
1066         case ICMD_DNEG:
1067
1068         case ICMD_I2L:
1069         case ICMD_I2F:
1070         case ICMD_I2D:
1071         case ICMD_L2I:
1072         case ICMD_L2F:
1073         case ICMD_L2D:
1074         case ICMD_F2I:
1075         case ICMD_F2L:
1076         case ICMD_F2D:
1077         case ICMD_D2I:
1078         case ICMD_D2L:
1079         case ICMD_D2F:
1080
1081         case ICMD_CHECKCAST:
1082
1083         case ICMD_ARRAYLENGTH:
1084         case ICMD_INSTANCEOF:
1085
1086         case ICMD_NEWARRAY:
1087         case ICMD_ANEWARRAY:
1088
1089         case ICMD_GETFIELD:
1090                 liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
1091                 liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
1092                 break;
1093
1094                 /* pop 0 push 1 */
1095         case ICMD_GETSTATIC:
1096
1097         case ICMD_NEW:
1098                 liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
1099                 break;
1100
1101                 /* pop many push any */
1102
1103         case ICMD_INVOKESTATIC:
1104         case ICMD_INVOKESPECIAL:
1105         case ICMD_INVOKEVIRTUAL:
1106         case ICMD_INVOKEINTERFACE:
1107                         INSTRUCTION_GET_METHODDESC(iptr,md);
1108                         i = md->paramcount;
1109                         while (--i >= 0) {
1110                                 liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
1111                                 src = src->prev;
1112                         }
1113                         if (md->returntype.type != TYPE_VOID)
1114                                 liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
1115                         break;
1116
1117         case ICMD_BUILTIN:
1118                 bte = iptr->val.a;
1119                 md = bte->md;
1120                 i = md->paramcount;
1121                 while (--i >= 0) {
1122                         liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
1123                         src = src->prev;
1124                 }
1125                 if (md->returntype.type != TYPE_VOID)
1126                         liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
1127                 break;
1128
1129         case ICMD_MULTIANEWARRAY:
1130                 i = iptr->op1;
1131                 while (--i >= 0) {
1132                         liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
1133                         src = src->prev;
1134                 }
1135                 liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
1136                 break;
1137
1138         default:
1139                 exceptions_throw_internalerror("Unknown ICMD %d during register allocation",
1140                                                                            iptr->opc);
1141                 return;
1142         } /* switch */
1143 }
1144
1145 /*
1146  * These are local overrides for various environment variables in Emacs.
1147  * Please do not remove this and leave it at the end of the file, where
1148  * Emacs will automagically detect them.
1149  * ---------------------------------------------------------------------
1150  * Local variables:
1151  * mode: c
1152  * indent-tabs-mode: t
1153  * c-basic-offset: 4
1154  * tab-width: 4
1155  * End:
1156  * vim:noexpandtab:sw=4:ts=4:
1157  */