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

   Copyright (C) 2005, 2006, 2007 R. Grafl, A. Krall, C. Kruegel,
   C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
   E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
   J. Wenninger, Institut f. Computersprachen - TU Wien

   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.

   Contact: cacao@cacaojvm.org

   Authors: Christian Ullrich

   $Id: liveness.c $

*/


#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, 
										stackptr src, lv_sets *sets);
void liveness_set_stack(lsradata *ls, int block, int g_iindex, stackptr 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, stackptr 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;
	stackptr 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;
	stackptr 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;
	stackptr    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
	stackptr 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, stackptr 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, stackptr 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,
										stackptr src, lv_sets *sets)
{
/* 	methodinfo         *lm; */
	builtintable_entry *bte;
	methoddesc         *md;
	int i, g_iindex;
	instruction *iptr;
	stackptr    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:
 */