src/vm/jit/allocator/liveness.c

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