src/vm/jit/allocator/liveness.c

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