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