Logo Search packages:      
Sourcecode: cacao-source version File versions  Download package

liveness.c

/* src/vm/jit/allocator/liveness.c - liveness analysis for lsra

   Copyright (C) 2005, 2006, 2007, 2008
   CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO

   This file is part of CACAO.

   This program is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2, or (at
   your option) any later version.

   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
   02110-1301, USA.

*/


#include "config.h"

#include <limits.h>
#include <stdlib.h>

#include "vm/types.h"

#include "mm/memory.h"

#include "toolbox/logging.h"
#include "toolbox/worklist.h"

#include "vm/builtin.h"
#include "vm/exceptions.h"
#include "vm/global.h"
#include "vm/method.h"
#include "vm/resolve.h"
#include "vm/jit/codegen-common.h"
#include "vm/jit/jit.h"
#include "vm/jit/allocator/lsra.h"
#include "vm/jit/allocator/liveness.h"


/* function prototypes */
void liveness_scan_registers_canditates(jitdata *jd, int b_index, int iindex, 
                                                            stackelement_t* src, lv_sets *sets);
void liveness_set_stack(lsradata *ls, int block, int g_iindex, stackelement_t* s,
                                    lv_sets *sets, int op);
void liveness_set_local(lsradata *ls, int block, int g_iindex, s4 v_index,
                                    int type, lv_sets *sets, int op);

void liveness_add_ss(struct lifetime *lt, stackelement_t* s) {
      struct stackslot *ss;
      /* Stackslot noch nicht eingetragen? */

      if (s->varnum != lt->v_index) {
            ss = DNEW(struct stackslot);
            ss->s = s;
            ss->s->varnum = lt->v_index;
            ss->next = lt->local_ss;
            lt->local_ss = ss;
            if (s != NULL) lt->savedvar |= s->flags & SAVEDVAR;
            if (s != NULL) lt->type = s->type;
      }
}

void liveness_join_ss( struct lsradata *ls, struct stackelement *in,
                           struct stackelement *out) {
      struct lifetime *lt, *lto;
      struct stackslot *ss, *ss_last;


      if (in->varnum != out->varnum) {
            lt = &(ls->lifetime[-in->varnum - 1]);

#ifdef LV_DEBUG_CHECK
            if (lt->type == -1) { 
#ifdef LV_DEBUG_VERBOSE
                  log_text("liveness_join_ss: lifetime for instack not found\n");
#endif
                  assert(0);
            }
#endif

            if (out->varnum >= 0) { /* no lifetime for this slot till now */
                  liveness_add_ss(lt, out);
            } else {
                  lto = &(ls->lifetime[-out->varnum - 1]);

#ifdef LV_DEBUG_CHECK
                  if (lto->type == -1) {
#ifdef LV_DEBUG_VERBOSE
                        log_text("liveness_join_ss: lifetime for outstack not found\n");
#endif
                        assert(0);
                  }
#endif
#ifdef LV_DEBUG_CHECK
                  if (lto->type != lt->type) {
#ifdef LV_DEBUG_VERBOSE
                        log_text("liveness_join_ss: in/out stack type mismatch\n");
#endif
                        assert(0);
                  }
#endif
      
                  /* take Lifetime lto out of ls->lifetimes */
                  lto->type = -1;

                  /* merge lto into lt of in */

                  /* change varnums of all lto->local_ss->s to lt->v_index */
                  ss_last = ss = lto->local_ss;
                  while (ss != NULL) {
                        ss_last = ss;
                        ss->s->varnum = lt->v_index;
                        ss = ss->next;
                  }
                  /* link both lto->local_ss list to lt->local_ss */
                  if (ss_last != NULL) {
                        ss_last->next = lt->local_ss;
                        lt->local_ss = lto->local_ss;
                  }

                  lt->savedvar |= lto->savedvar;
                  lt->flags |= lto->flags;
                  lt->usagecount += lto->usagecount;

                  /*join of [bb|i]_first_def und [bb|i]_last_use */
                  if (lto->bb_first_def < lt->bb_first_def) {
                        lt->bb_first_def = lto->bb_first_def;
                        lt->i_first_def = lto->i_first_def;
                  } else if ((lto->bb_first_def == lt->bb_first_def) &&
                                 ( lto->i_first_def < lt->i_first_def)) {
                        lt->i_first_def = lto->i_first_def;
                  }     
                  if (lto->bb_last_use > lt->bb_last_use) {
                        lt->bb_last_use = lto->bb_last_use;
                        lt->i_last_use = lto->i_last_use;
                  } else if ((lto->bb_last_use == lt->bb_last_use) &&
                                 ( lto->i_last_use > lt->i_last_use)) {
                        lt->i_last_use = lto->i_last_use;
                  }     
            }
      }
}

/* join instack of Basic Block b_index with outstack of predecessors */
void liveness_join_lifetimes(jitdata *jd, int b_index) {
      struct stackelement *in, *i, *out;
    struct _list *pred;

      lsradata *ls;
      methodinfo *m;

      ls = jd->ls;
      m  = jd->m;

      /* do not join instack of Exception Handler */ 
      if (m->basicblocks[b_index].type == BBTYPE_EXH)
            return;
      in=m->basicblocks[b_index].instack;
      /* do not join first instack element of a subroutine header */
      if (m->basicblocks[b_index].type == BBTYPE_SBR)
            in=in->prev; 
      
      if (in != NULL) {
            for (pred = ls->pred[b_index]; pred != NULL; pred = pred->next) {
                  out = m->basicblocks[pred->value].outstack;
                  for (i=in; (i != NULL); i = i->prev, out=out->prev) {
                        liveness_join_ss(ls, i, out);
                  }
            }
      }
}

void liveness_setup(jitdata *jd) {
      int i, icount, b_index;
      stackelement_t* src;
      methodinfo *m;
      lsradata *ls;

      ls = jd->ls;
      m  = jd->m;

      ls->icount_block = DMNEW(int, m->basicblockcount);
      ls->icount_block[0] = icount = 0;
      for(i = 0; i < m->basicblockcount; i++) {
            if (i != 0) {
                  /* create a global instruction index in icount_block */
                  if (ls->sorted[i-1] != -1)
                        icount += m->basicblocks[ ls->sorted[i-1] ].icount;
                        ls->icount_block[i] = icount;
            }

            if ((b_index = ls->sorted[i]) != -1) {
                  /* 'valid' Basic Block */

                  /* adapt in- and outstacks for LSRA */
                  src = m->basicblocks[b_index].instack;
                  if (m->basicblocks[b_index].type != BBTYPE_STD) {
#ifdef LV_DEBUG_CHECK
                        if (src == NULL) {
#ifdef LV_DEBUG_VERBOSE
                        log_text("No Incoming Stackslot for Exception/Subroutine BB\n");
#endif
                              assert(0);
                        }
#endif
                        if (src->varkind == STACKVAR)
                              src->varkind = TEMPVAR;
                        src = src->prev;
                  }
                  for (;src != NULL; src=src->prev) {
                        /* no ARGVAR possible at BB Boundaries with LSRA! */
                        /* -> change to TEMPVAR                           */
                        if (src->varkind == ARGVAR ) {
                              src->varkind = TEMPVAR;
                              /* On Architectures with own return registers a return
                                 stackslot is marked as varkind=ARGVAR with varnum=-1
                                 but for lsra a varkind==TEMPVAR, varnum=-1 would mean,
                                 that already a lifetime was allocated! */
                              if (src->varnum < 0) src->varnum = 0;
                        }
                        else if (src->varkind == LOCALVAR ) {
                              /* only allowed for top most ss at sbr or exh entries! */
#ifdef LV_DEBUG_VERBOSE
                              log_text("LOCALVAR at basicblock instack\n");
#endif
                              abort();
                        } else {
                              if (src->varkind == STACKVAR )
                                    /* no Interfaces at BB Boundaries with LSRA! */
                                    /* -> change to TEMPVAR                      */
                                    src->varkind = TEMPVAR;
                        }
                  }

                  src = m->basicblocks[b_index].outstack;
                  for (;src != NULL; src=src->prev) {
                        if (src->varkind == ARGVAR ) {
#ifdef LV_DEBUG_VERBOSE
                              log_text("ARGVAR at basicblock outstack\n");
#endif
                              abort();
                        } else if (src->varkind == LOCALVAR ) {
#ifdef LV_DEBUG_VERBOSE
                              log_text("LOCALVAR at basicblock outstack\n");
#endif
                              abort();
                        } else {
                              /* no Interfaces at BB Boundaries with LSRA! */
                              /* -> change to TEMPVAR                      */
                              if (src->varkind == STACKVAR )
                                    src->varkind = TEMPVAR;
                        }
                  }
            }
      }
}

void liveness_init(jitdata *jd) {
      int i, b_index, len;
      int lifetimes;
      stackelement_t* src, dst;
      instruction *iptr;
      methodinfo *m;
      lsradata *ls;

      ls = jd->ls;
      m  = jd->m;

      lifetimes = 0;

      for(i = 0; i < m->basicblockcount; i++) {
            if ((b_index = ls->sorted[i]) != -1) {
                  /* 'valid' Basic Block */

                  /* Scan Number of Stack Lifetimes */
                  lifetimes += m->basicblocks[b_index].indepth;

                  dst = m->basicblocks[b_index].instack;
                  len = m->basicblocks[b_index].icount;
                  iptr = m->basicblocks[b_index].iinstr;
                  for (;len>0; len--, iptr++) {
                        src = dst;
                        dst = iptr->dst;
                        
                        switch(iptr->opc) {
                        case ICMD_SWAP:
                        case ICMD_DUP2:
                              lifetimes += 2;
                              break;
                        case ICMD_DUP_X1:
                              lifetimes += 3;
                              break;
                        case ICMD_DUP2_X1:
                              lifetimes += 5;
                              break;
                        case ICMD_DUP_X2:
                              lifetimes += 4;
                              break;
                        case ICMD_DUP2_X2:
                              lifetimes += 6;
                              break;

                        default:
                              if (( dst != NULL) && (src != dst))
                                    lifetimes++;
                        }
                  }
            }
      }
      ls->maxlifetimes = lifetimes;
      ls->lifetimecount = lifetimes + jd->maxlocals * (TYPE_ADR+1);
}

void liveness_scan_basicblock(jitdata *jd, int b_index,
                                            lv_sets *sets, int lifetimes) {
      int iindex;
      stackelement_t*    src;
      instruction *iptr;
      int i;
      methodinfo *m;
      lsradata *ls;

      ls = jd->ls;
      m  = jd->m;

      src = m->basicblocks[b_index].instack;

      iindex = m->basicblocks[b_index].icount - 1;
      /* set iptr to last instruction of BB */
      iptr = m->basicblocks[b_index].iinstr + iindex;

      bv_reset(sets->in, lifetimes);

      for (;iindex >= 0; iindex--, iptr--)  {
            /* get source Stack for the current instruction     */
            /* destination stack is available as iptr->dst                      */
            /* source stack is either the destination stack of the previos      */
            /* instruction, or the basicblock instack for the first instruction */
            if (iindex) /* != 0 is > 0 here, since iindex ist always >= 0 */
                  src=(iptr-1)->dst;
            else
                  src=m->basicblocks[b_index].instack;

            /* Reset kill and gen bitvectors for use in */
            /* liveness_scan_register_canditates */

            bv_reset(sets->kill, lifetimes);
            bv_reset(sets->gen, lifetimes);

            /* get gen and kill set of instruction */

            liveness_scan_registers_canditates(jd, b_index, iindex, src, sets);

            /* tmp = out(instr) - kill(instr) */

            bv_minus(sets->tmp, sets->out, sets->kill, lifetimes);

            /* in  = gen(instr) union tmp = gen union (out - kill) */

            bv_union(sets->in, sets->gen, sets->tmp, lifetimes);    

            /* Set SAVEDVAR flag for locals */

            if (op_needs_saved[iptr->opc])
                  for(i = ls->maxlifetimes; i < ls->lifetimecount; i++)
                        if (!ls->lifetime[i].savedvar)
                              if ( bv_get_bit(sets->in,i) && bv_get_bit(sets->out,i) )
                                    ls->lifetime[i].savedvar = SAVEDVAR;

        /* out(instr-1) = in(instr) (only one successor)*/

            bv_copy(sets->out, sets->in, lifetimes);
      }
      /* create gen sets for incoming stackslots */

      /* global instruction index for bb b_index */

      iindex = ls->icount_block[ls->sorted_rev[b_index]];
      bv_reset(sets->kill, lifetimes);
      bv_reset(sets->gen, lifetimes);
      src = m->basicblocks[b_index].instack;
      if (m->basicblocks[b_index].type != BBTYPE_STD) {
            liveness_set_stack(ls, b_index, iindex, src, sets, LV_KILL);
            src = src->prev;
      }
      for (;src != NULL; src=src->prev) {
            /* only TEMP or LOCALVAR by now possible      */
            /* liveness_set_stack redirects for LOCALVARS */
            liveness_set_stack(ls, b_index, iindex, src,    sets, LV_GEN);
            _LV_ASSERT( ((src->varkind == LOCALVAR) || (src->varkind == TEMPVAR)) );
      }     
      /* in  = gen union (out - kill) */
      bv_minus(sets->tmp, sets->out, sets->kill, lifetimes);
      bv_union(sets->in, sets->gen, sets->tmp, lifetimes);    
}
            
void liveness(jitdata *jd) {
      bitvector *out;
      bitvector *in;
      bitvector params;
      char *buff;
      worklist *W;
      int b_index;
    struct _list *succ;
      struct _list *pred;
      bitvector visited;
      lv_sets   sets;
      int       i, p, t;
      methoddesc *md;
#ifdef LV_DEBUG_CHECK
      stackelement_t* s;
#endif
      methodinfo *m;
      registerdata *rd;
      lsradata *ls;
      /***************************************************************************
 TODO: 
 - Exact Lifeness Information for intra Basic Blocks Stackslots are trivial
 They should not be included in the gen, kill, in and out sets to improve
 performance.
 - Local Vars as represented in rd->locals "are quite sparse". An intermediate
 representation for really used index/type pairs should be implemented. 
      ***************************************************************************/

      ls = jd->ls;
      m  = jd->m;
      rd = jd->rd;

      if (ls->lifetimecount == 0)
            return;
      ls->lifetime = DMNEW(struct lifetime, ls->lifetimecount);
      for (i=0; i < ls->lifetimecount; i++) ls->lifetime[i].type = -1;

      sets.gen = bv_new(ls->lifetimecount);
      sets.kill = bv_new(ls->lifetimecount);
      sets.tmp = bv_new(ls->lifetimecount);
      sets.out = bv_new(ls->lifetimecount);
      sets.in =  bv_new(ls->lifetimecount);

      params =  bv_new(ls->lifetimecount);

      visited = bv_new(m->basicblockcount);
      buff = DMNEW(char, ls->lifetimecount+1);

      out = DMNEW(bitvector, m->basicblockcount);
      in  = DMNEW(bitvector, m->basicblockcount);
      for(i = 0; i < m->basicblockcount; i++) {
            out[i] = bv_new(ls->lifetimecount);
            in[i]  = bv_new(ls->lifetimecount);
      }

      /* set in[0] to arguments */
      /* <-> kill at 0, -1 */
      md = m->parseddesc;
      for (p = 0, i = 0; p < md->paramcount; p++) {
            t = md->paramtypes[p].type;

            if (rd->locals[i][t].type >= 0)     
                  /* Param to Local init happens before normal Code */
                  liveness_set_local(ls, 0, -1, i, t, &sets, LV_KILL); 
            i++;
            if (IS_2_WORD_TYPE(t))    /* increment local counter a second time  */
                  i++;                  /* for 2 word types */
      }  /* end for */
      bv_copy(params, sets.kill, ls->lifetimecount);

      /* fill Worklist so that last node will be taken out first */
      W = wl_new(m->basicblockcount);
      for (i = 0; i < m->basicblockcount; i++)
            if (ls->sorted[i] != -1)
                  wl_add(W, ls->sorted[i]);

      /* Worklist algorithm*/
      while (!wl_is_empty(W)) {
            b_index = wl_get(W);

            /* out[b_index] = for all s element of successors(b_index) union in[s]*/
            for (succ = ls->succ[b_index]; succ != NULL; succ = succ->next)
                  bv_union(out[b_index], out[b_index], in[succ->value],
                               ls->lifetimecount);

            bv_copy(sets.out, out[b_index], ls->lifetimecount);

            /* compute in[b_index] */
            liveness_scan_basicblock(jd, b_index, &sets, ls->lifetimecount);

            if (!bv_get_bit(visited, b_index)) {
                  liveness_join_lifetimes(jd, b_index);
                  bv_set_bit(visited, b_index);
            }

            if (!bv_equal(sets.in, in[b_index], ls->lifetimecount)) {
                  bv_copy(in[b_index], sets.in, ls->lifetimecount);
                  for(pred = ls->pred[b_index]; pred != NULL; pred = pred->next)
                        wl_add(W, pred->value);
            }
      }

#ifdef LV_DEBUG_CHECK
      s = m->basicblocks[b_index].instack;
      if ((s != NULL) && (m->basicblocks[b_index].flags != BBTYPE_STD))
            s = s->prev;
      for( ; s != NULL; s = s->prev) {
#ifdef LV_DEBUG_VERBOSE
            if (!bv_get_bit(in[b_index], -s->varnum - 1)) {
                  log_text("liveness: Error In Stacklot not live!\n");
            }
#endif
            _LV_ASSERT( (bv_get_bit(in[b_index], -s->varnum - 1)) );
      }
#endif

      for (i = 0; i < m->basicblockcount; i++)
            if ((b_index=ls->sorted[i]) != -1) {
                  for(t = 0; t < ls->lifetimecount; t++) {
                        if (ls->lifetime[t].type != -1) {
                              if (bv_get_bit(in[b_index], t)) {
                                    p = ls->icount_block[ls->sorted_rev[b_index]];
                                    if (p < ls->lifetime[t].i_first_def)
                                          ls->lifetime[t].i_first_def = p;
                              }
                              if (bv_get_bit(out[b_index], t)) {
                                    p = 
   ls->icount_block[ls->sorted_rev[b_index]]+m->basicblocks[b_index].icount - 1;
                                    if (p > ls->lifetime[t].i_last_use)
                                          ls->lifetime[t].i_last_use = p;
                              }
                        }
                  }
            }
               
}

struct lifetime *liveness_get_ss_lifetime(lsradata *ls, stackelement_t* s) {
      struct lifetime *n;
      
      if (s->varnum >= 0) { /* new stackslot lifetime */
#ifdef LV_DEBUG_VERBOSE       
            if (-ls->v_index - 1 >= ls->maxlifetimes) {
                  printf("%i %i\n", -ls->v_index - 1, ls->maxlifetimes);
            }
#endif
            _LV_ASSERT(-ls->v_index - 1 < ls->maxlifetimes);

            n = &(ls->lifetime[-ls->v_index - 1]);
            n->type = s->type;
            n->v_index = ls->v_index--;
            n->usagecount = 0;
            
            n->i_last_use = -2;
            n->i_first_def = INT_MAX;
            n->local_ss = NULL;
            n->savedvar = 0;
            n->flags = 0;
      } else
            n = &(ls->lifetime[-s->varnum - 1]);

      liveness_add_ss( n, s);
      return n;
}

void liveness_set_stack(lsradata *ls, int block, int g_iindex, stackelement_t* s,
                                    lv_sets *sets,
                                    int op) {
      struct lifetime *n;

      if (s->varkind == LOCALVAR) {
            liveness_set_local(ls, block, g_iindex, s->varnum, s->type, sets, op);
      } else if (s->varkind == TEMPVAR) {
            n = liveness_get_ss_lifetime(ls, s);
            if (op == LV_KILL) {
                  bv_set_bit(sets->kill, -s->varnum - 1);
                  if (n->i_first_def > g_iindex) {
                        n->i_first_def = g_iindex;
                  }
            } else {
                  /* LV_GEN */
                  bv_set_bit(sets->gen, -s->varnum - 1);
                  if (n->i_last_use < g_iindex) {
                        n->i_last_use = g_iindex;
                  }
            }
            n->usagecount+=ls->nesting[ls->sorted_rev[block]];
      }
}

void liveness_set_local(lsradata *ls, int block, int g_iindex, s4 v_index,
                                    int type, lv_sets *sets, int op) {
      struct lifetime *n;

      n = &(ls->lifetime[ ls->maxlifetimes + v_index * (TYPE_ADR+1) + type]);

      if (n->type == -1) { /* new local lifetime */
            n->local_ss=NULL;
            n->v_index=v_index;
            n->type=type;
            /* TODO: Look if local really needs to be a savedvar */
            n->savedvar = 0; /* SAVEDVAR; */
            n->flags = 0;
            n->usagecount = 0;

            n->i_last_use = -2;
            n->i_first_def = INT_MAX;
      }
      n->usagecount+=ls->nesting[ls->sorted_rev[block]];
      if (op == LV_KILL) {
            bv_set_bit(sets->kill, ls->maxlifetimes + v_index * (TYPE_ADR+1)+ type);
            if (n->i_first_def > g_iindex) {
                  n->i_first_def = g_iindex;
            }
      } else {
            /* LV_GEN */
            bv_set_bit(sets->gen, ls->maxlifetimes + v_index * (TYPE_ADR+1) + type);
            if (n->i_last_use < g_iindex) {
                  n->i_last_use = g_iindex;
            }
      }
}

void liveness_scan_registers_canditates(jitdata *jd, int b_index, int iindex,
                                                            stackelement_t* src, lv_sets *sets)
{
/*    methodinfo         *lm; */
      builtintable_entry *bte;
      methoddesc         *md;
      int i, g_iindex;
      instruction *iptr;
      stackelement_t*    dst;
      methodinfo *m;
      lsradata   *ls;

      m  = jd->m;
      ls = jd->ls;

      iptr = m->basicblocks[b_index].iinstr + iindex;
      dst = iptr->dst;
      g_iindex = ls->icount_block[ls->sorted_rev[b_index]] + iindex;
      switch (iptr->opc) {
            /* pop 0 push 0 */
      case ICMD_RET:
            /* local read (return adress) */
            liveness_set_local(ls, b_index, g_iindex, iptr->op1, TYPE_ADR, sets, LV_GEN);

            break;
      case ICMD_NOP:
/*    case ICMD_ELSE_ICONST: */
      case ICMD_CHECKNULL:
      case ICMD_JSR:
      case ICMD_RETURN:
      case ICMD_GOTO:
      case ICMD_PUTSTATICCONST:
      case ICMD_INLINE_START:
      case ICMD_INLINE_END:
      case ICMD_INLINE_GOTO:
            break;
                             
      case ICMD_IINC:
            /* local = local+<const> */
            liveness_set_local(ls, b_index, g_iindex, iptr->op1, TYPE_INT, sets,  LV_GEN);
            liveness_set_local(ls, b_index, g_iindex, iptr->op1, TYPE_INT, sets,  LV_KILL);
            break;

            /* pop 0 push 1 const: const->stack */
      case ICMD_ICONST:
      case ICMD_LCONST:
      case ICMD_FCONST:
      case ICMD_DCONST:
      case ICMD_ACONST:
            /* new stack slot */
            liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
            break;

            /* pop 0 push 1 load: local->stack */
      case ICMD_ILOAD:
      case ICMD_LLOAD:
      case ICMD_FLOAD:
      case ICMD_DLOAD:
      case ICMD_ALOAD:
            if (dst->varkind != LOCALVAR) {
                  /* local->value on stack */
                  liveness_set_local(ls, b_index, g_iindex, iptr->op1,
                                             iptr->opc - ICMD_ILOAD, sets, LV_GEN);
                  /* value->stack */
                  liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL); 
            } else /* if (dst->varnum != iptr->op1) */ {
                  /* local -> local */
                  liveness_set_local(ls, b_index, g_iindex, iptr->op1,
                                             iptr->opc - ICMD_ILOAD, sets, LV_GEN);
                  liveness_set_local(ls, b_index, g_iindex, dst->varnum,
                                             iptr->opc - ICMD_ILOAD, sets, LV_KILL);
            }
            break;

            /* pop 2 push 1 */
            /* Stack(arrayref,index)->stack */
      case ICMD_IALOAD:
      case ICMD_LALOAD:
      case ICMD_FALOAD:
      case ICMD_DALOAD:
      case ICMD_AALOAD:

      case ICMD_BALOAD:
      case ICMD_CALOAD:
      case ICMD_SALOAD:
            /* stack->index */
            liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
            /* stack->arrayref */
            liveness_set_stack(ls, b_index, g_iindex, src->prev, sets, LV_GEN);
            /* arrayref[index]->stack */
            liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
            break;

            /* pop 3 push 0 */
            /* stack(arrayref,index,value)->arrayref[index]=value */
      case ICMD_IASTORE:
      case ICMD_LASTORE:
      case ICMD_FASTORE:
      case ICMD_DASTORE:
      case ICMD_AASTORE:

      case ICMD_BASTORE:
      case ICMD_CASTORE:
      case ICMD_SASTORE:
            /* stack -> value */
            liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN); 
            /* stack -> index*/
            liveness_set_stack(ls, b_index, g_iindex, src->prev, sets, LV_GEN);
            /* stack -> arrayref */
            liveness_set_stack(ls, b_index, g_iindex, src->prev->prev, sets, LV_GEN); 
            break;

            /* pop 1 push 0 store: stack -> local */
      case ICMD_ISTORE:
      case ICMD_LSTORE:
      case ICMD_FSTORE:
      case ICMD_DSTORE:
      case ICMD_ASTORE:
            if (src->varkind != LOCALVAR) {
                  /* stack -> value */
                  liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN); 
                  liveness_set_local(ls, b_index, g_iindex, iptr->op1, iptr->opc - ICMD_ISTORE,
                                             sets, LV_KILL);
            } else {
                  liveness_set_local(ls, b_index, g_iindex, src->varnum, iptr->opc-ICMD_ISTORE,
                                             sets, LV_GEN);
                  liveness_set_local(ls, b_index, g_iindex, iptr->op1, iptr->opc - ICMD_ISTORE,
                                             sets, LV_KILL);
            }
            break;

            /* pop 1 push 0 */
      case ICMD_POP: /* throw away a stackslot */
            /* TODO: check if used anyway (DUP...) and change codegen to */
            /*       ignore this stackslot */
            liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
            break;

            /* pop 1 push 0 */
      case ICMD_IRETURN:
      case ICMD_LRETURN:
      case ICMD_FRETURN:
      case ICMD_DRETURN:
      case ICMD_ARETURN: /* stack(value) -> [empty]    */

      case ICMD_ATHROW:  /* stack(objref) -> undefined */

      case ICMD_PUTSTATIC: /* stack(value) -> static_field */
      case ICMD_PUTFIELDCONST:

            /* pop 1 push 0 branch */
      case ICMD_IFNULL: /* stack(value) -> branch? */
      case ICMD_IFNONNULL:

      case ICMD_IFEQ:
      case ICMD_IFNE:
      case ICMD_IFLT:
      case ICMD_IFGE:
      case ICMD_IFGT:
      case ICMD_IFLE:

      case ICMD_IF_LEQ:
      case ICMD_IF_LNE:
      case ICMD_IF_LLT:
      case ICMD_IF_LGE:
      case ICMD_IF_LGT:
      case ICMD_IF_LLE:

            /* pop 1 push 0 table branch */
      case ICMD_TABLESWITCH:
      case ICMD_LOOKUPSWITCH:

      case ICMD_MONITORENTER:
      case ICMD_MONITOREXIT:
            /* stack -> value */
            liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN); 
            break;

            /* pop 2 push 0 */
      case ICMD_POP2: /* throw away 2 stackslots */
            /* TODO: check if used anyway (DUP...) and change codegen to */
            /*       ignore this stackslot */
            liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
            liveness_set_stack(ls, b_index, g_iindex, src->prev, sets, LV_GEN);
            break;

            /* pop 2 push 0 branch */

      case ICMD_IF_ICMPEQ: /* stack (v1,v2) -> branch(v1,v2) */
      case ICMD_IF_ICMPNE:
      case ICMD_IF_ICMPLT:
      case ICMD_IF_ICMPGE:
      case ICMD_IF_ICMPGT:
      case ICMD_IF_ICMPLE:

      case ICMD_IF_LCMPEQ:
      case ICMD_IF_LCMPNE:
      case ICMD_IF_LCMPLT:
      case ICMD_IF_LCMPGE:
      case ICMD_IF_LCMPGT:
      case ICMD_IF_LCMPLE:

      case ICMD_IF_ACMPEQ:
      case ICMD_IF_ACMPNE:

            /* pop 2 push 0 */
      case ICMD_PUTFIELD: /* stack(objref,value) -> objref = value */

      case ICMD_IASTORECONST:
      case ICMD_LASTORECONST:
      case ICMD_AASTORECONST:
      case ICMD_BASTORECONST:
      case ICMD_CASTORECONST:
      case ICMD_SASTORECONST:
            /* stack -> value*/
            liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);  
            liveness_set_stack(ls, b_index, g_iindex, src->prev, sets, LV_GEN);
            break;

            /* pop 0 push 1 dup */
      case ICMD_DUP: 
            /* src == dst->prev */
            /* src -> dst */

            /* src and dst->prev are identical */
            /*          liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_KILL);
                        liveness_set_stack(ls, b_index, g_iindex, dst->prev, sets, LV_GEN);*/

            liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);

            break;

            /* pop 0 push 2 dup */
      case ICMD_DUP2: 
            /* src       ==  dst->prev->prev */
            /* src->prev == dst->prev->prev->prev */
            /* src       ->  dst */
            /* src->prev -> dst->prev-> */

            liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex, dst->prev, sets, LV_KILL);
            break;

            /* pop 2 push 3 dup */
      case ICMD_DUP_X1:
            /* src       -> dst */
            /* src->prev -> dst->prev */
            /* src       -> dst->prev->prev */

            liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex, dst->prev, sets, LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex, dst->prev->prev, sets,
                                       LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex + 1, src, sets, LV_GEN);
            liveness_set_stack(ls, b_index, g_iindex + 1, src->prev, sets, LV_GEN);
            break;

            /* pop 3 push 4 dup */
      case ICMD_DUP_X2:
            /* src             -> dst                   */
            /* src->prev       -> dst->prev             */
            /* src->prev->prev -> dst->prev->prev       */
            /* dst (=src)      -> dst->prev->prev->prev */

            liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex, dst->prev, sets, LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex, dst->prev->prev, sets,
                                       LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex, dst->prev->prev->prev, sets,
                                       LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex + 1, src, sets, LV_GEN);
            liveness_set_stack(ls, b_index, g_iindex + 1, src->prev, sets, LV_GEN);
            liveness_set_stack(ls, b_index, g_iindex + 1, src->prev->prev, sets,
                                       LV_GEN);
            break;

            /* pop 3 push 5 dup */
      case ICMD_DUP2_X1:
            /* src                    -> dst                   */
            /* src->prev              -> dst->prev             */
            /* src->prev->prev        -> dst->prev->prev       */
            /* dst (=src)             -> dst->prev->prev->prev */
            /* dst->prev (=src->prev) -> dst->prev->prev->prev->prev */
            liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex, dst->prev, sets, LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex, dst->prev->prev, sets,
                                       LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex, dst->prev->prev->prev, sets,
                                       LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex, dst->prev->prev->prev->prev,
                                       sets, LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex + 1, src, sets, LV_GEN);
            liveness_set_stack(ls, b_index, g_iindex + 1, src->prev, sets, LV_GEN);
            liveness_set_stack(ls, b_index, g_iindex + 1, src->prev->prev, sets,
                                       LV_GEN);
            break;

            /* pop 4 push 6 dup */
      case ICMD_DUP2_X2:
            /* src                    -> dst                   */
            /* src->prev              -> dst->prev             */
            /* src->prev->prev        -> dst->prev->prev       */
            /* src->prev->prev->prev  -> dst->prev->prev->prev       */
            /* dst (=src)             -> dst->prev->prev->prev->prev */
            /* dst->prev (=src->prev) -> dst->prev->prev->prev->prev->prev */
            liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex, dst->prev, sets, LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex, dst->prev->prev, sets,
                                       LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex, dst->prev->prev->prev, sets,
                                       LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex, dst->prev->prev->prev->prev,
                                       sets, LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex,
                                       dst->prev->prev->prev->prev->prev, sets, LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex + 1, src, sets, LV_GEN);
            liveness_set_stack(ls, b_index, g_iindex + 1, src->prev, sets, LV_GEN);
            liveness_set_stack(ls, b_index, g_iindex + 1, src->prev->prev, sets,
                                       LV_GEN);
            liveness_set_stack(ls, b_index, g_iindex + 1, src->prev->prev->prev,
                                       sets, LV_GEN);
            break;

            /* pop 2 push 2 swap */
      case ICMD_SWAP:
            /* src       -> dst->prev */
            /* src->prev -> dst       */
            liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex, dst->prev, sets, LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex + 1, src, sets, LV_GEN);
            liveness_set_stack(ls, b_index, g_iindex + 1, src->prev, sets, LV_GEN);
            break;

            /* pop 2 push 1 */
                              
      case ICMD_LADD:
      case ICMD_LSUB:
      case ICMD_LMUL:

      case ICMD_LOR:
      case ICMD_LAND:
      case ICMD_LXOR:

      case ICMD_LSHL:
      case ICMD_LSHR:
      case ICMD_LUSHR:

      case ICMD_IADD:
      case ICMD_IMUL:

      case ICMD_ISHL:
      case ICMD_ISHR:
      case ICMD_IUSHR:
      case ICMD_IAND:
      case ICMD_IOR:
      case ICMD_IXOR:


      case ICMD_FADD:
      case ICMD_FSUB:
      case ICMD_FMUL:

      case ICMD_DADD:
      case ICMD_DSUB:
      case ICMD_DMUL:
      case ICMD_DDIV:
      case ICMD_DREM:

      case ICMD_ISUB:

      case ICMD_LDIV:
      case ICMD_LREM:

      case ICMD_IDIV:
      case ICMD_IREM:

      case ICMD_FDIV:
      case ICMD_FREM:

      case ICMD_LCMP:
      case ICMD_FCMPL:
      case ICMD_FCMPG:
      case ICMD_DCMPL:
      case ICMD_DCMPG:
            liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
            liveness_set_stack(ls, b_index, g_iindex, src->prev, sets, LV_GEN);
            break;

            /* pop 1 push 1 */
      case ICMD_LADDCONST:
      case ICMD_LSUBCONST:
      case ICMD_LMULCONST:
      case ICMD_LMULPOW2:
      case ICMD_LDIVPOW2:
      case ICMD_LREMPOW2:
      case ICMD_LANDCONST:
      case ICMD_LORCONST:
      case ICMD_LXORCONST:
      case ICMD_LSHLCONST:
      case ICMD_LSHRCONST:
      case ICMD_LUSHRCONST:

      case ICMD_IADDCONST:
      case ICMD_ISUBCONST:
      case ICMD_IMULCONST:
      case ICMD_IMULPOW2:
      case ICMD_IDIVPOW2:
      case ICMD_IREMPOW2:
      case ICMD_IANDCONST:
      case ICMD_IORCONST:
      case ICMD_IXORCONST:
      case ICMD_ISHLCONST:
      case ICMD_ISHRCONST:
      case ICMD_IUSHRCONST:

/*    case ICMD_IFEQ_ICONST: */
/*    case ICMD_IFNE_ICONST: */
/*    case ICMD_IFLT_ICONST: */
/*    case ICMD_IFGE_ICONST: */
/*    case ICMD_IFGT_ICONST: */
/*    case ICMD_IFLE_ICONST: */

      case ICMD_INEG:
      case ICMD_INT2BYTE:
      case ICMD_INT2CHAR:
      case ICMD_INT2SHORT:
      case ICMD_LNEG:
      case ICMD_FNEG:
      case ICMD_DNEG:

      case ICMD_I2L:
      case ICMD_I2F:
      case ICMD_I2D:
      case ICMD_L2I:
      case ICMD_L2F:
      case ICMD_L2D:
      case ICMD_F2I:
      case ICMD_F2L:
      case ICMD_F2D:
      case ICMD_D2I:
      case ICMD_D2L:
      case ICMD_D2F:

      case ICMD_CHECKCAST:

      case ICMD_ARRAYLENGTH:
      case ICMD_INSTANCEOF:

      case ICMD_NEWARRAY:
      case ICMD_ANEWARRAY:

      case ICMD_GETFIELD:
            liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
            liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
            break;

            /* pop 0 push 1 */
      case ICMD_GETSTATIC:

      case ICMD_NEW:
            liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
            break;

            /* pop many push any */

      case ICMD_INVOKESTATIC:
      case ICMD_INVOKESPECIAL:
      case ICMD_INVOKEVIRTUAL:
      case ICMD_INVOKEINTERFACE:
                  INSTRUCTION_GET_METHODDESC(iptr,md);
                  i = md->paramcount;
                  while (--i >= 0) {
                        liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
                        src = src->prev;
                  }
                  if (md->returntype.type != TYPE_VOID)
                        liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
                  break;

      case ICMD_BUILTIN:
            bte = iptr->val.a;
            md = bte->md;
            i = md->paramcount;
            while (--i >= 0) {
                  liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
                  src = src->prev;
            }
            if (md->returntype.type != TYPE_VOID)
                  liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
            break;

      case ICMD_MULTIANEWARRAY:
            i = iptr->op1;
            while (--i >= 0) {
                  liveness_set_stack(ls, b_index, g_iindex, src, sets, LV_GEN);
                  src = src->prev;
            }
            liveness_set_stack(ls, b_index, g_iindex, dst, sets, LV_KILL);
            break;

      default:
            exceptions_throw_internalerror("Unknown ICMD %d during register allocation",
                                                         iptr->opc);
            return;
      } /* switch */
}

/*
 * These are local overrides for various environment variables in Emacs.
 * Please do not remove this and leave it at the end of the file, where
 * Emacs will automagically detect them.
 * ---------------------------------------------------------------------
 * Local variables:
 * mode: c
 * indent-tabs-mode: t
 * c-basic-offset: 4
 * tab-width: 4
 * End:
 * vim:noexpandtab:sw=4:ts=4:
 */

Generated by  Doxygen 1.6.0   Back to index