--- /dev/null
+/* src/vm/jit/allocator/liveness.c - liveness analysis for lsra
+
+ Copyright (C) 1996-2005, 2006 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
+
+ Changes:
+
+ $Id: liveness.c $
+
+*/
+
+#include <limits.h>
+#include <stdlib.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->cd->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:
+ *exceptionptr =
+ new_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:
+ */
-/* src/vm/jit/allocator/lsra.inc - linear scan register allocator
+/* src/vm/jit/allocator/lsra.c - linear scan register allocator
Copyright (C) 1996-2005, 2006 R. Grafl, A. Krall, C. Kruegel,
C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
Changes: Christian Thalinger
Edwin Steiner
- $Id: lsra.c 4879 2006-05-05 17:34:49Z edwin $
+ $Id: lsra.c 5234 2006-08-14 17:50:12Z christian $
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
+#include <limits.h>
#include "arch.h"
#include "md-abi.h"
#include "vm/stringlocal.h"
#include "vm/jit/abi.h"
#include "vm/jit/reg.h"
+#include "vm/jit/allocator/liveness.h"
#include "vm/jit/allocator/lsra.h"
+#ifdef USAGE_COUNT
+extern char **prof_m_names;
+extern u4 **prof_bb_freq;
+extern int prof_size;
+#endif
/* function prototypes */
-bool lsra_test(methodinfo *, codegendata *);
-void lsra_init(methodinfo *, codegendata *, lsradata *);
-void lsra_setup(methodinfo *, codegendata *, registerdata *, lsradata *);
-void lsra_main(methodinfo *, lsradata *, registerdata *, codegendata *);
-void lsra_clean_Graph( methodinfo *, codegendata *, lsradata *);
+void lsra_init(jitdata *);
+void lsra_setup(jitdata *);
+void lsra_main(jitdata *);
+
+void lsra_reg_setup(jitdata *, struct lsra_register *, struct lsra_register * );
+void lsra_calc_lifetime_length(jitdata *);
+void _lsra_main( jitdata *, int *, int, struct lsra_register *, int *);
+void lsra_expire_old_intervalls(jitdata *, struct lifetime *,
+ struct lsra_register *);
+void spill_at_intervall(jitdata *, struct lifetime *);
+void lsra_add_active(struct lifetime *, struct lifetime **, int *);
+void _lsra_expire_old_intervalls(jitdata *, struct lifetime *,
+ struct lsra_register *, struct lifetime **,
+ int *);
+void _spill_at_intervall(struct lifetime *, struct lifetime **, int *);
+
+void lsra_alloc(jitdata *, int *, int, int *);
+int lsra_getmem(struct lifetime *, struct freemem *, int *);
+struct freemem *lsra_getnewmem(int *);
+void lsra_setflags(int *, int);
-#ifdef LSRA_DEBUG
+#ifdef LSRA_DEBUG_VERBOSE
void lsra_dump_stack(stackptr );
+void print_lifetimes(jitdata *, int *, int);
#endif
-#ifdef LSRA_PRINTLIFETIMES
-void print_lifetimes(registerdata *, lsradata *, int *, int);
-#endif
-#ifdef LSRA_TESTLT
-void test_lifetimes( methodinfo *, lsradata *, registerdata *);
-#endif
-
-void lsra_reg_setup(methodinfo *m ,registerdata *,struct lsra_register *,struct lsra_register * );
-
-void lsra_scan_registers_canditates(methodinfo *, lsradata *, int);
-
-void lsra_join_lifetimes( methodinfo *, lsradata *, int);
-void lsra_calc_lifetime_length(methodinfo *, lsradata *, codegendata *);
+#if !defined(LV)
+void lsra_scan_registers_canditates(jitdata *, int);
+void lsra_join_lifetimes(jitdata *, int);
void _lsra_new_stack( lsradata *, stackptr , int , int, int);
void _lsra_from_stack(lsradata *, stackptr , int , int, int);
void lsra_add_ss(struct lifetime *, stackptr );
void lsra_usage_local(lsradata *, s4 , int , int , int , int );
+#endif
-void _lsra_main( methodinfo *, lsradata *, int *, int, struct lsra_register *, int *);
-void lsra_expire_old_intervalls(methodinfo *, lsradata *, struct lifetime *, struct lsra_register *);
-void spill_at_intervall(methodinfo *, lsradata *, struct lifetime *);
-void lsra_add_active(struct lifetime *, struct lifetime **, int *);
-void _lsra_expire_old_intervalls(methodinfo *, struct lifetime *, struct lsra_register *, struct lifetime **, int *);
-void _spill_at_intervall(struct lifetime *, struct lifetime **, int *);
-
-void lsra_alloc(methodinfo *, registerdata *, struct lsradata *, int *, int, int *);
-int lsra_getmem(struct lifetime *, struct freemem *, int *);
-struct freemem *lsra_getnewmem(int *);
-void lsra_align_stackslots(struct lsradata *, stackptr, stackptr);
-void lsra_setflags(int *, int);
bool lsra(jitdata *jd)
{
- methodinfo *m;
- codegendata *cd;
- registerdata *rd;
- lsradata *ls;
#if defined(ENABLE_STATISTICS)
+ lsradata *ls;
int locals_start;
int i,j;
#endif
-#if defined(LSRA_DEBUG) || defined(LSRA_LEAF)
- char name[1256], name1[1256];
-#endif
-
-#if defined(LSRA_DEBUG)
- int b_index;
+#if defined(LSRA_DEBUG_CHECK)
+ methodinfo *m;
+ int b_index;
stackptr in,out;
int ind, outd;
+#endif
+#if defined(LSRA_DEBUG_CHECK)
+ m = jd->m;
b_index = 0;
while (b_index < m->basicblockcount ) {
ind=m->basicblocks[b_index].indepth;
for (;ind != 0;in=in->prev, ind--) {
/* ARGVAR or LOCALVAR in instack is ok*/
+#if 0
if (in->varkind == ARGVAR) printf("ARGVAR in instack: \n");
if (in->varkind == LOCALVAR) printf("LOCALVAR in instack\n");
+#endif
}
out=m->basicblocks[b_index].outstack;
outd=m->basicblocks[b_index].outdepth;
}
#endif
-#if defined(LSRA_DEBUG) || defined(LSRA_LEAF)
- printf("Max Lifetimes %i \n", m->maxlifetimes);
- utf_sprint_convert_to_latin1(name, m->class->name);
- utf_sprint_convert_to_latin1(name1, m->name);
- strcat(name, ".");
- strcat(name, name1);
- utf_sprint_convert_to_latin1(name1, m->descriptor);
- strcat(name, name1);
-
-#ifndef LSRA_LEAF
- printf("/******************************************************/\n");
-#endif
-#ifdef LSRA_LEAF
- if (m->isleafmethod)
-#endif
-/* printf("LSRA Start for %s opt_from: %i opt_to: %i\n", name, opt_from, opt_to); */
-#ifndef LSRA_LEAF
- if (strcmp(name,"java/util/Vector.<init>(II)V")==0) {
- printf("-------------------\n");
- }
- if (m->isleafmethod)
- printf("**Leafmethod**\n");
-#endif
-#endif
-
- /* get required compiler data */
-
- m = jd->m;
- cd = jd->cd;
- rd = jd->rd;
-
- ls=DNEW(lsradata);
- lsra_init(m, cd, ls);
-
-#if 0
-#if defined(LSRA_USES_REG_RES)
- for (i=opt_from; i<=opt_to; i++) {
- icmd_uses_reg_res[i][0]=S|D|YES;
- icmd_uses_reg_res[i][1]=S|D|YES;
- icmd_uses_reg_res[i][2]=S|D|YES;
- icmd_uses_reg_res[i][3]=REG_NULL;
- }
-#endif
-#endif
-
- lsra_setup(m, cd, rd, ls);
+ jd->ls = DNEW(lsradata);
+ lsra_init(jd);
+ lsra_setup(jd);
#if defined(ENABLE_STATISTICS)
/* find conflicts between locals for statistics */
if (opt_stat) {
+ ls = jd->ls;
/* local Variable Lifetimes are at the end of the lifetime array and */
/* have v_index >= 0 */
for (locals_start = ls->lifetimecount-1; (locals_start >=0) &&
}
#endif
/* Run LSRA */
- lsra_main(m, ls, rd, cd);
+ lsra_main(jd);
/* everything's ok */
/* sort Basic Blocks using Depth First Search in reverse post order in */
/* ls->sorted. */
-void lsra_DFS(methodinfo *m, lsradata *ls) {
+void lsra_DFS(jitdata *jd) {
int *stack;
int *visited;
int stack_top;
int i,p;
struct _list *succ;
+ methodinfo *m;
+ lsradata *ls;
+
+ m = jd->m;
+ ls = jd->ls;
+
stack = DMNEW( int, m->basicblockcount + 1);
- visited = DMNEW( bool, m->basicblockcount + 1);
+ visited = (int *)DMNEW( int, m->basicblockcount + 1);
for (i = 0; i <= m->basicblockcount; i++) {
visited[i] = 0;
ls->sorted[i]=-1;
}
}
-void lsra_get_nesting(methodinfo *m, lsradata *ls) {
+void lsra_get_nesting(jitdata *jd) {
+ methodinfo *m;
+ lsradata *ls;
int i,j, end;
struct _backedge *n;
+ m = jd->m;
+ ls = jd->ls;
+
for (i=0; i <= m->basicblockcount; i++)
if (ls->sorted[i] != -1)
ls->sorted_rev[ls->sorted[i]]=i;
}
}
-#ifdef LSRA_DEBUG
+#ifdef LSRA_DEBUG_VERBOSE
+ if (compileverbose) {
printf("sorted: \n");
for (i=0; i < ls->backedge_count; i++)
printf("Backedge: %i - %i, %i - %i\n", ls->sorted[ls->backedge[i]->start], ls->sorted[ls->backedge[i]->end], ls->backedge[i]->start, ls->backedge[i]->end);
printf("Nesting Level \n");
for (i=0; i<m->basicblockcount; i++) printf(" %3li", ls->nesting[i]);
printf("\n");
+ }
#endif
for (i=0; i <= m->basicblockcount; i++) {
ls->sorted_rev[i] = -1;
- ls->nesting[i] = 1+ls->nesting[i]*ls->nesting[i];
+ ls->nesting[i] = 1+ls->nesting[i]*ls->nesting[i]*10;
}
}
-void lsra_get_backedges( methodinfo *m, lsradata *ls) {
+void lsra_get_backedges(jitdata *jd) {
+ methodinfo *m;
+ lsradata *ls;
struct _list **next;
struct _backedge *n;
int i,j;
bool merged;
+ m = jd->m;
+ ls = jd->ls;
+
/* first remove artificial end basicblock from ls->sorted, succ and pred */
j=-1;
for (i=0; i < m->basicblockcount; i++) {
/* - sort backedge by increasing start */
for (i=0; i < ls->backedge_count; i++)
for (j=i+1; j < ls->backedge_count; j++)
- if (ls->backedge[i]->start > ls->backedge[j]->start) { /* -> swap */
- n=ls->backedge[i];
- ls->backedge[i]=ls->backedge[j];
- ls->backedge[j]=n;
+ if (ls->backedge[i]->start > ls->backedge[j]->start) {
+ /* -> swap */
+ n = ls->backedge[i];
+ ls->backedge[i] = ls->backedge[j];
+ ls->backedge[j] = n;
}
-#ifdef LSRA_DEBUG
- printf("sorted: \n");
- for (i=0; i < ls->backedge_count; i++)
- printf("Backedge: %i - %i, %i - %i\n", ls->sorted[ls->backedge[i]->start], ls->sorted[ls->backedge[i]->end], ls->backedge[i]->start, ls->backedge[i]->end);
- printf("Nesting Level \n");
- for (i=0; i<m->basicblockcount; i++) printf(" %3li", ls->nesting[i]);
- printf("\n");
+#ifdef LSRA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("sorted: \n");
+ for (i=0; i < ls->backedge_count; i++)
+ printf("Backedge: %i - %i, %i - %i\n",
+ ls->sorted[ls->backedge[i]->start],
+ ls->sorted[ls->backedge[i]->end], ls->backedge[i]->start,
+ ls->backedge[i]->end);
+ printf("Nesting Level \n");
+ for (i=0; i<m->basicblockcount; i++) printf(" %3li", ls->nesting[i]);
+ printf("\n");
+ }
#endif
merged = true;
}
}
}
-#ifdef LSRA_DEBUG
- printf("merged: \n");
- for (i = 0; i < ls->backedge_count; i++)
- if (ls->backedge[i] != NULL)
- printf("Backedge: %i - %i, %i - %i\n",ls->sorted[ls->backedge[i]->start],ls->sorted[ls->backedge[i]->end],ls->backedge[i]->start, ls->backedge[i]->end);
+#ifdef LSRA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("merged: \n");
+ for (i = 0; i < ls->backedge_count; i++)
+ if (ls->backedge[i] != NULL)
+ printf("Backedge: %i - %i, %i - %i\n",
+ ls->sorted[ls->backedge[i]->start],
+ ls->sorted[ls->backedge[i]->end],
+ ls->backedge[i]->start, ls->backedge[i]->end);
+ }
#endif
/* - remove backedge[] == NULL from array */
ls->backedge_count--;
} else i--;
}
-#ifdef LSRA_DEBUG
- printf("ready: \n");
- for (i=0; i < ls->backedge_count; i++)
- printf("Backedge: %i - %i, %i - %i\n",ls->sorted[ls->backedge[i]->start],ls->sorted[ls->backedge[i]->end],ls->backedge[i]->start, ls->backedge[i]->end);
+#ifdef LSRA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("ready: \n");
+ for (i=0; i < ls->backedge_count; i++)
+ printf("Backedge: %i - %i, %i - %i\n",
+ ls->sorted[ls->backedge[i]->start],
+ ls->sorted[ls->backedge[i]->end],ls->backedge[i]->start,
+ ls->backedge[i]->end);
+ }
#endif
}
-void lsra_add_cfg( methodinfo *m, lsradata *ls, int from, int to) {
+void lsra_add_cfg(jitdata *jd, int from, int to) {
struct _list *n;
+ methodinfo *m;
+ lsradata *ls;
+
+ m = jd->m;
+ ls = jd->ls;
/* ignore Empty, Deleted,... Basic Blocks as target */
/* TODO: Setup BasicBlock array before to avoid this */
}
/* add Edges from guarded Areas to Exception handlers in the CFG */
-void lsra_add_exceptions(methodinfo *m, codegendata *cd, lsradata *ls) {
+void lsra_add_exceptions(jitdata *jd) {
+ methodinfo *m;
+ lsradata *ls;
int i;
+ exceptiontable *ex;
+
+
+ m = jd->m;
+ ls = jd->ls;
+
+ ex = jd->cd->exceptiontable;
/* add cfg edges from all bb of a try block to the start of the according */
/* exception handler to ensure the right order after depthfirst search */
- exceptiontable *ex;
- ex=cd->exceptiontable;
-#ifdef LSRA_DEBUG
- printf("ExTable(%i): ", cd->exceptiontablelength);
+
+#ifdef LSRA_DEBUG_VERBOSE
+ if (compileverbose)
+ printf("ExTable(%i): ", jd->cd->exceptiontablelength);
#endif
for (; ex != NULL; ex = ex->down) {
-#ifdef LSRA_DEBUG
- printf("[%i-%i]->%i ",ex->start->debug_nr, ex->end->debug_nr,
- ex->handler->debug_nr);
- if (ex->handler->debug_nr >= m->basicblockcount)
- { log_text("Exceptionhandler Basicblocknummer invalid\n");
- assert(0); }
- if (m->basicblocks[ex->handler->debug_nr].flags < BBREACHED)
- { log_text("Exceptionhandler Basicblocknummer not reachable\n");
- assert(0); }
- if (ex->start->debug_nr > ex->end->debug_nr)
- { log_text("Guarded Area starts after its end\n"); assert(0); }
+#ifdef LSRA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("[%i-%i]->%i ",ex->start->nr, ex->end->nr,
+ ex->handler->nr);
+ if (ex->handler->nr >= m->basicblockcount) {
+ log_text("Exceptionhandler Basicblocknummer invalid\n");
+ abort();
+ }
+ if (m->basicblocks[ex->handler->nr].flags < BBREACHED) {
+ log_text("Exceptionhandler Basicblocknummer not reachable\n");
+ abort();
+ }
+ if (ex->start->nr > ex->end->nr) {
+ log_text("Guarded Area starts after its end\n");
+ abort();
+ }
+ }
#endif
/* loop all valid Basic Blocks of the guarded area and add CFG edges */
/* to the appropriate handler */
- for (i=ex->start->debug_nr; (i <= ex->end->debug_nr) &&
+ for (i=ex->start->nr; (i <= ex->end->nr) &&
(i < m->basicblockcount); i++)
if (m->basicblocks[i].flags >= BBREACHED)
- lsra_add_cfg(m, ls, i, ex->handler->debug_nr);
+ lsra_add_cfg(jd, i, ex->handler->nr);
+ }
+#ifdef LSRA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("\n");
}
-#ifdef LSRA_DEBUG
- printf("\n");
#endif
}
-void lsra_add_jsr( methodinfo *m, lsradata *ls, int from, int to) {
+void lsra_add_jsr(jitdata *jd, int from, int to) {
+ methodinfo *m;
+ lsradata *ls;
struct _sbr *sbr, *n;
struct _list *ret;
+ ls = jd->ls;
+ m = jd->m;
+
/* ignore Empty, Deleted,... Basic Blocks as target */
/* TODO: Setup BasicBlock array before to avoid this */
/* best together with using the basicblock list, so lsra works */
/* with opt_loops, too */
for (; (to < m->basicblockcount) && (m->basicblocks[to].flags < BBREACHED);
to++);
-#ifdef LSRA_DEBUG
- if (to == m->basicblockcount)
- { log_text("Invalid subroutine start index\n"); assert(0); }
+#ifdef LSRA_DEBUG_CHECK
+ if (to == m->basicblockcount)
+ { log_text("Invalid subroutine start index\n"); assert(0); }
#endif
- lsra_add_cfg(m, ls, from, to);
+ lsra_add_cfg(jd, from, to);
/* from + 1 ist the return Basic Block Index */
for (from++; (from < m->basicblockcount) &&
(m->basicblocks[from].flags < BBREACHED); from++);
-#ifdef LSRA_DEBUG
+#ifdef LSRA_DEBUG_CHECK
if (from == m->basicblockcount)
{ log_text("Invalid return basic block index for jsr\n"); assert(0); }
#endif
sbr->ret = ret;
}
-void lsra_add_sub( methodinfo *m, lsradata *ls, int b_index, struct _list *ret, bool *visited )
+void lsra_add_sub( jitdata *jd, int b_index, struct _list *ret,
+ bool *visited )
{
+ methodinfo *m;
+ lsradata *ls;
struct _list *l;
instruction *ip;
bool next_block;
+ m = jd->m;
+ ls = jd->ls;
+
/* break at virtual End Block */
if (b_index != m->basicblockcount) {
visited[b_index] = true;
next_block = true;
if (!next_block) {
- ip = m->basicblocks[b_index].iinstr + m->basicblocks[b_index].icount -1;
+ ip = m->basicblocks[b_index].iinstr
+ + m->basicblocks[b_index].icount -1;
if (ip->opc == ICMD_JSR) /* nested Subroutines */
next_block = true;
}
if (!next_block) {
- if (ip->opc == ICMD_RET) { /* subroutine return found -> add return adresses to CFG */
+ if (ip->opc == ICMD_RET) {
+ /* subroutine return found -> add return adresses to CFG */
for (l = ret; l != NULL; l = l->next)
- lsra_add_cfg( m, ls, b_index, l->value);
+ lsra_add_cfg(jd, b_index, l->value);
} else { /* follow CFG */
for ( l = ls->succ[b_index]; l != NULL; l = l->next)
if (!visited[l->value])
- lsra_add_sub( m, ls, l->value, ret, visited);
+ lsra_add_sub(jd, l->value, ret, visited);
}
} else { /* fall through to next block */
if (!visited[b_index + 1])
- lsra_add_sub(m, ls, b_index + 1, ret, visited);
+ lsra_add_sub(jd, b_index + 1, ret, visited);
}
}
}
/* Add subroutines from ls->sbr list to CFG */
-void lsra_add_subs(methodinfo *m, lsradata *ls) {
+void lsra_add_subs(jitdata *jd) {
+ methodinfo *m;
+ lsradata *ls;
struct _sbr *sbr;
bool *visited;
int i;
-#ifdef LSRA_DEBUG
+#ifdef LSRA_DEBUG_VERBOSE
struct _list *ret;
#endif
- visited = DMNEW(int, m->basicblockcount + 1);
- for (i=0; i <= m->basicblockcount; i++); visited[i] = false;
+ m = jd->m;
+ ls = jd->ls;
+
+ visited = (bool *)DMNEW(int, m->basicblockcount + 1);
+ for (i=0; i <= m->basicblockcount; i++) visited[i] = false;
for (sbr = ls->sbr.next; sbr != NULL; sbr=sbr->next) {
-#ifdef LSRA_DEBUG
- printf("Subroutine Header: %3i Return Adresses:",sbr->header);
- for (ret = sbr->ret; ret != NULL; ret = ret->next)
- printf(" %3i", ret->value);
- printf("\n");
-#endif
- lsra_add_sub( m, ls, sbr->header, sbr->ret, visited );
+#ifdef LSRA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("Subroutine Header: %3i Return Adresses:",sbr->header);
+ for (ret = sbr->ret; ret != NULL; ret = ret->next)
+ printf(" %3i", ret->value);
+ printf("\n");
+ }
+#endif
+ lsra_add_sub(jd, sbr->header, sbr->ret, visited );
}
}
-
-
/* Generate the Control Flow Graph */
/* ( pred,succ,num_pred of lsradata structure) */
-void lsra_make_cfg(methodinfo *m, lsradata *ls)
-{
+void lsra_make_cfg(jitdata *jd) {
+ methodinfo *m;
+ lsradata *ls;
instruction *ip;
s4 *s4ptr;
int high, low, count;
- int b_index;
+ int b_index, len;
+
+ m = jd->m;
+ ls = jd->ls;
b_index=0;
while (b_index < m->basicblockcount ) {
- if (m->basicblocks[b_index].flags >= BBREACHED) {
+ if ((m->basicblocks[b_index].flags >= BBREACHED) &&
+ (len = m->basicblocks[b_index].icount)) {
+ /* block is valid and contains instructions */
+
+ /* set ip to last instruction */
ip = m->basicblocks[b_index].iinstr +
m->basicblocks[b_index].icount -1;
- /* set ip to last instruction */
-
- if (m->basicblocks[b_index].icount) {
- /* block contains instructions */
- switch (ip->opc) { /* check type of last instruction */
- case ICMD_RETURN:
- case ICMD_IRETURN:
- case ICMD_LRETURN:
+ while ((len>0) && (ip->opc == ICMD_NOP)) {
+ len--;
+ ip--;
+ }
+ switch (ip->opc) { /* check type of last instruction */
+ case ICMD_RETURN:
+ case ICMD_IRETURN:
+ case ICMD_LRETURN:
case ICMD_FRETURN:
case ICMD_DRETURN:
case ICMD_ARETURN:
case ICMD_ATHROW:
- lsra_add_cfg(m, ls, b_index, m->basicblockcount);
+ lsra_add_cfg(jd, b_index, m->basicblockcount);
break; /* function returns -> end of graph */
case ICMD_IFNULL:
case ICMD_IF_LCMPLE:
case ICMD_IF_ACMPEQ:
case ICMD_IF_ACMPNE: /* branch -> add next block */
- lsra_add_cfg(m, ls, b_index, b_index+1);
+ lsra_add_cfg(jd, b_index, b_index+1);
/* fall throu -> add branch target */
case ICMD_GOTO:
- lsra_add_cfg(m, ls, b_index, m->basicblockindex[ip->op1]);
+ lsra_add_cfg(jd, b_index, m->basicblockindex[ip->op1]);
break; /* visit branch (goto) target */
case ICMD_TABLESWITCH: /* switch statement */
s4ptr = ip->val.a;
- lsra_add_cfg(m, ls, b_index, m->basicblockindex[*s4ptr]);
+ lsra_add_cfg(jd, b_index, m->basicblockindex[*s4ptr]);
s4ptr++;
low = *s4ptr;
while (--count >= 0) {
s4ptr++;
- lsra_add_cfg(m, ls, b_index,
+ lsra_add_cfg(jd, b_index,
m->basicblockindex[*s4ptr]);
}
break;
case ICMD_LOOKUPSWITCH: /* switch statement */
s4ptr = ip->val.a;
- lsra_add_cfg(m, ls, b_index, m->basicblockindex[*s4ptr]);
+ lsra_add_cfg(jd, b_index, m->basicblockindex[*s4ptr]);
++s4ptr;
count = *s4ptr++;
while (--count >= 0) {
- lsra_add_cfg(m, ls, b_index,
+ lsra_add_cfg(jd, b_index,
m->basicblockindex[s4ptr[1]]);
s4ptr += 2;
}
break;
case ICMD_JSR:
- lsra_add_jsr(m, ls, b_index, m->basicblockindex[ip->op1]);
+ lsra_add_jsr(jd, b_index, m->basicblockindex[ip->op1]);
break;
case ICMD_RET:
break;
default:
- lsra_add_cfg(m, ls, b_index, b_index + 1 );
+ lsra_add_cfg(jd, b_index, b_index + 1 );
break;
- } /* switch (ip->opc)*/
- } /* if (m->basicblocks[blockIndex].icount) */
- } /* if (m->basicblocks[b_index].flags >= BBREACHED) */
+ } /* switch (ip->opc)*/
+ } /* if ((m->basicblocks[blockIndex].icount)&& */
+ /* (m->basicblocks[b_index].flags >= BBREACHED)) */
b_index++;
} /* while (b_index < m->basicblockcount ) */
}
-
-
-
-void lsra_init(methodinfo *m, codegendata *cd, lsradata *ls)
-{
+void lsra_init(jitdata *jd) {
+ methodinfo *m;
+ lsradata *ls;
int i;
+ ls = jd->ls;
+ m = jd->m;
+
/* Init LSRA Data Structures */
/* allocate lifetimes for all Basicblocks */
/* + 1 for an artificial exit node */
ls->sorted = DMNEW(int , m->basicblockcount+1);
ls->sorted_rev = DMNEW(int , m->basicblockcount+1);
ls->num_pred = DMNEW(int , m->basicblockcount+1);
- ls->nesting = DMNEW(long , m->basicblockcount);
+ ls->nesting = DMNEW(long , m->basicblockcount+1);
for (i=0; i<m->basicblockcount; i++) {
ls->pred[i]=NULL;
ls->succ[i]=NULL;
ls->sorted_rev[m->basicblockcount]=-1;
ls->num_pred[m->basicblockcount]=0;
-#ifdef LSRA_DEBUG
- if (cd->maxlocals != id->cumlocals)
- { log_text("lsra: Welche locals nehmen?\n"); assert(0); }
-#endif
-
- ls->maxlifetimes = m->maxlifetimes;
- ls->lifetimecount = ls->maxlifetimes + cd->maxlocals * (TYPE_ADR+1);
- ls->lifetime = DMNEW(struct lifetime, ls->lifetimecount);
- ls->lt_used = DMNEW(int, ls->lifetimecount);
- ls->lt_int = DMNEW(int, ls->lifetimecount);
- ls->lt_int_count = 0;
- ls->lt_flt = DMNEW(int, ls->lifetimecount);
- ls->lt_flt_count = 0;
- ls->lt_mem = DMNEW(int, ls->lifetimecount);
- ls->lt_mem_count = 0;
- for (i=0; i < ls->lifetimecount; i++) ls->lifetime[i].type = -1;
-
ls->sbr.next = NULL;
ls->v_index = -1;
}
-void lsra_setup(methodinfo *m, codegendata *cd, registerdata *rd, lsradata *ls)
-{
-#ifdef LSRA_DEBUG
+void lsra_setup(jitdata *jd) {
+ methodinfo *m;
+ codegendata *cd;
+ lsradata *ls;
+
+#ifdef LSRA_DEBUG_VERBOSE
basicblock *bptr;
struct _list *nl;
#endif
- int i,p;
- s4 t;
- methoddesc *md = m->parseddesc;
+
+ int i;
+
+#if !defined(LV)
+ registerdata *rd;
+
+ rd = jd->rd;
+#endif
+
+ ls = jd->ls;
+ m = jd->m;
+ cd = jd->cd;
#if defined(ENABLE_LOOP)
/* Loop optimization "destroys" the basicblock array */
/* TODO: work with the basicblock list */
if (opt_loops) {
log_text("lsra not possible with loop optimization\n");
- assert(0);
+ abort();
}
#endif /* defined(ENABLE_LOOP) */
/* Setup LSRA Data structures */
/* Generate the Control Flow Graph */
- lsra_make_cfg(m, ls);
+ lsra_make_cfg(jd);
/* gather nesting before adding of Exceptions and Subroutines!!! */
+
#ifdef USAGE_COUNT
- lsra_DFS(m, ls);
- lsra_get_nesting( m, ls);
+ lsra_DFS(jd);
+ lsra_get_nesting(jd);
#endif
-#ifdef LSRA_DEBUG
+
+#ifdef LSRA_DEBUG_VERBOSE
+ if (compileverbose) {
printf("Successors:\n");
for (i=0; i < m->basicblockcount; i++) {
printf("%3i->: ",i);
printf("Sorted_rev: ");
for (i=0; i < m->basicblockcount; i++) printf("%3i ", ls->sorted_rev[i]);
printf("\n");
+ }
#endif
+
/* add subroutines before exceptions! They "destroy" the CFG */
- lsra_add_subs(m, ls);
- lsra_add_exceptions(m, cd, ls);
+ lsra_add_subs(jd);
+ lsra_add_exceptions(jd);
/* generate reverse post order sort */
- lsra_DFS(m, ls);
+ lsra_DFS(jd);
/* setup backedge and nested data structures*/
- lsra_get_backedges( m, ls);
-#ifdef LSRA_DEBUG
+ lsra_get_backedges(jd);
+
+ liveness_init(jd);
+
+ ls->lifetimecount = ls->maxlifetimes + cd->maxlocals * (TYPE_ADR+1);
+ ls->lifetime = DMNEW(struct lifetime, ls->lifetimecount);
+ ls->lt_used = DMNEW(int, ls->lifetimecount);
+ ls->lt_int = DMNEW(int, ls->lifetimecount);
+ ls->lt_int_count = 0;
+ ls->lt_flt = DMNEW(int, ls->lifetimecount);
+ ls->lt_flt_count = 0;
+ ls->lt_mem = DMNEW(int, ls->lifetimecount);
+ ls->lt_mem_count = 0;
+
+ for (i=0; i < ls->lifetimecount; i++) ls->lifetime[i].type = -1;
+
+#ifdef LSRA_DEBUG_VERBOSE
+ if (compileverbose) {
printf("Successors:\n");
for (i=0; i < m->basicblockcount; i++) {
printf("%3i->: ",i);
printf("Sorted_rev: ");
for (i=0; i < m->basicblockcount; i++) printf("%3i ", ls->sorted_rev[i]);
printf("\n");
+ }
#endif
-#ifdef LSRA_DEBUG
+#ifdef LSRA_DEBUG_CHECK
/* compare m->basicblocks[] with the list basicblocks->next */
- printf("LSRA BB check\n");
i=0;
bptr = m->basicblocks;
while (bptr != NULL) {
#endif
- /* Create Stack Slot lifetimes over all basic blocks */
- for (i=m->basicblockcount-1; i >= 0; i--) {
- if (ls->sorted[i] != -1) {
- lsra_scan_registers_canditates(m, ls, ls->sorted[i]);
- lsra_join_lifetimes(m, ls, ls->sorted[i]);
+ liveness_setup(jd);
+
+#if defined(LV)
+ liveness(jd);
+#else /* LV */
+ {
+ int p, t;
+ methoddesc *md = m->parseddesc;
+
+ /* Create Stack Slot lifetimes over all basic blocks */
+ for (i=m->basicblockcount-1; i >= 0; i--) {
+ if (ls->sorted[i] != -1) {
+ lsra_scan_registers_canditates(jd, ls->sorted[i]);
+ lsra_join_lifetimes(jd, ls->sorted[i]);
+ }
}
- }
- /* Parameter initialisiation for locals [0 .. paramcount[ */
- /* -> add local var write access at (bb=0,iindex=-1) */
- /* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */
- /* this needs a special treatment, wenn lifetimes get extended */
- /* over backedges, since this parameter initialisation happens */
- /* outside of Basic Block 0 !!!! */
- /* this could have been avoided by marking the read access with -1,0 */
+ /* Parameter initialisiation for locals [0 .. paramcount[ */
+ /* -> add local var write access at (bb=0,iindex=-1) */
+ /* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */
+ /* this needs a special treatment, wenn lifetimes get extended */
+ /* over backedges, since this parameter initialisation happens */
+ /* outside of Basic Block 0 !!!! */
+ /* this could have been avoided by marking the read access with -1,0 */
- for (p = 0, i = 0; p < md->paramcount; p++) {
- t = md->paramtypes[p].type;
+ 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 */
- lsra_usage_local(ls, i, t, 0, -1, LSRA_STORE);
- i++;
- if (IS_2_WORD_TYPE(t)) /* increment local counter a second time */
- i++; /* for 2 word types */
- } /* end for */
+ if (rd->locals[i][t].type >= 0)
+ /* Param to Local init happens before normal Code */
+ lsra_usage_local(ls, i, t, 0, -1, LSRA_STORE);
+ i++;
+ /* increment local counter a second time */
+ /* for 2 word types */
+ if (IS_2_WORD_TYPE(t))
+ i++;
+ } /* end for */
+ }
+#endif /* LV */
- lsra_calc_lifetime_length(m, ls, cd);
+ lsra_calc_lifetime_length(jd);
-#ifdef LSRA_PRINTLIFETIMES
- printf("Basicblockcount: %4i\n",m->basicblockcount);
-/* print_lifetimes(rd, ls, ls->lt_used, ls->lifetimecount); */
+#ifdef LSRA_DEBUG_VERBOSE
+ if (compileverbose)
+ printf("Basicblockcount: %4i\n",m->basicblockcount);
#endif
}
-bool lsra_join_ss( struct lsradata *ls, struct stackelement *in,
- struct stackelement *out, int join_flag) {
- struct lifetime *lt, *lto;
- struct stackslot *ss, *ss_last;
+void lsra_reg_setup(jitdata *jd, struct lsra_register *int_reg,
+ struct lsra_register *flt_reg ) {
+ int i, j, iarg, farg;
+ int int_sav_top;
+ int flt_sav_top;
+ bool *fltarg_used, *intarg_used;
+ methoddesc *md;
+ methodinfo *m;
+ registerdata *rd;
- if (in->varnum != out->varnum) {
- lt = &(ls->lifetime[-in->varnum - 1]);
-#if 0
- printf("Lifetime1 %3i:",-in->varnum-1);
- for (ss=lt->local_ss; ss!=NULL; ss=ss->next)
- printf(" %p",ss);
- printf("\n");
-#endif
-
-#ifdef LSRA_DEBUG
- if (join_flag == JOIN_BB)
- if (lt->type == -1) {
- log_text("lsra_join_ss: lifetime for instack not found\n");
- assert(0);
- }
-#endif
+ m = jd->m;
+ rd = jd->rd;
+ md = m->parseddesc;
- if (out->varnum >= 0) { /* no lifetime for this slot till now */
- lsra_add_ss(lt, out);
- } else {
- lto = &(ls->lifetime[-out->varnum - 1]);
- if ((join_flag == JOIN_DUP) || (join_flag == JOIN_OP))
- if ( (lt->flags & JOIN_BB) || (lto->flags & JOIN_BB)) {
-#ifdef LSRA_DEBUG
- printf("DUP or OP join rejected for JOIN_BB Lifetime: v_index1 %3i v_index2 %3i\n",in->varnum, out->varnum);
-#endif
- return false;
- }
- if (join_flag == JOIN_DUP)
- if ( (lt->flags & JOIN_OP) || (lto->flags & JOIN_OP)) {
-#ifdef LSRA_DEBUG
- printf("DUP join rejected for JOIN_OP Lifetime: v_index1 %3i v_index2 %3i\n",in->varnum, out->varnum);
-#endif
- return false;
- }
-#ifdef LSRA_DEBUG
- if (lto->type == -1) {
- log_text("lsra_join_ss: lifetime for outstack not found\n");
- assert(0);
- }
-#endif
-#ifdef LSRA_DEBUG
- if (lto->type != lt->type) {
- log_text("lsra_join_ss: in/out stack type mismatch\n");
- assert(0);
- }
-#endif
-#if 0
- printf("Lifetime2 %3i:",-out->varnum-1);
- for (ss=lto->local_ss; ss!=NULL; ss=ss->next)
- printf(" %p",ss);
- printf("\n");
-#endif
+ int_reg->nregdesc = nregdescint;
+ flt_reg->nregdesc = nregdescfloat;
+ if (jd->isleafmethod) {
+ /* Temp and Argumentregister can be used as saved registers */
-
- lt->flags |= JOINING;
+ int_reg->sav_top = INT_ARG_CNT + INT_TMP_CNT + INT_SAV_CNT;
+ int_reg->sav_reg = DMNEW(int, int_reg->sav_top);
+ int_reg->tmp_reg = NULL;
+ int_reg->tmp_top = -1;
+ flt_reg->sav_top = FLT_ARG_CNT + FLT_TMP_CNT + FLT_SAV_CNT;
+ flt_reg->sav_reg = DMNEW(int, flt_reg->sav_top);
+ flt_reg->tmp_reg = NULL;
+ flt_reg->tmp_top = -1;
- /* take Lifetime lto out of ls->lifetimes */
- lto->type = -1;
+ /* additionaly precolour registers for Local Variables acting as */
+ /* Parameters */
- /* merge lto into lt of in */
+ farg = FLT_ARG_CNT;
+ iarg = INT_ARG_CNT;
- ss_last = ss = lto->local_ss;
- while (ss != NULL) {
- ss_last = ss;
- ss->s->varnum = lt->v_index;
- ss = ss->next;
- }
- if (ss_last != NULL) {
- ss_last->next = lt->local_ss;
- lt->local_ss = lto->local_ss;
- }
-#if 0
- printf("Lifetime1+2 %3i:",-in->varnum-1);
- for (ss=lt->local_ss; ss!=NULL; ss=ss->next)
- printf(" %p",ss);
- printf("\n");
-#endif
- lt->savedvar |= lto->savedvar;
- lt->flags |= lto->flags | join_flag;
- lt->usagecount += lto->usagecount;
-
- /*join of bb_first_def, i_first_def und *_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;
- }
- }
- }
- return true;
-}
-
-/* join instack of Basic Block b_index with outstack of predecessors */
-void lsra_join_lifetimes(methodinfo *m, lsradata *ls, int b_index) {
- struct stackelement *in, *i, *out;
- struct _list *pred;
-
- /* 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) {
- lsra_join_ss(ls, i, out, JOIN_BB);
- }
- }
- }
-}
-
-void lsra_reg_setup(methodinfo *m , registerdata *rd,
- struct lsra_register *int_reg,
- struct lsra_register *flt_reg ) {
- int i, j, iarg, farg;
- int int_sav_top;
- int flt_sav_top;
- bool *fltarg_used, *intarg_used;
-
- int_reg->nregdesc = nregdescint;
- flt_reg->nregdesc = nregdescfloat;
- if (m->isleafmethod) {
- /* Temp and Argumentregister can be used as saved registers */
- methoddesc *md = m->parseddesc;
-
- int_reg->sav_top = INT_ARG_CNT + INT_TMP_CNT + INT_SAV_CNT;
- int_reg->sav_reg = DMNEW(int, int_reg->sav_top);
- int_reg->tmp_reg = NULL;
- int_reg->tmp_top = -1;
- flt_reg->sav_top = FLT_ARG_CNT + FLT_TMP_CNT + FLT_SAV_CNT;
- flt_reg->sav_reg = DMNEW(int, flt_reg->sav_top);
- flt_reg->tmp_reg = NULL;
- flt_reg->tmp_top = -1;
-
-
- /* additionaly precolour registers for Local Variables acting as */
- /* Parameters */
-
- farg = FLT_ARG_CNT;
- iarg = INT_ARG_CNT;
-
- intarg_used = DMNEW(bool, INT_ARG_CNT);
- for (i=0; i < INT_ARG_CNT; i++)
- intarg_used[i]=false;
+ intarg_used = DMNEW(bool, INT_ARG_CNT);
+ for (i=0; i < INT_ARG_CNT; i++)
+ intarg_used[i]=false;
fltarg_used = DMNEW(bool, FLT_ARG_CNT);
for (i=0; i < FLT_ARG_CNT; i++)
/* non leaf method -> use Argument Registers [arg[int|flt]reguse */
/* ... [INT|FLT]_ARG_CNT[ as temp reg */
/* divide temp and saved registers */
+ int argintreguse, argfltreguse;
+#ifdef LV
+ /* with Locals as non SAVEDVAR, the used arg[int|flt] as in params */
+ /* of the method itself have to be regarded, or mismatch before */
+ /* block 0 with parameter copy could happen! */
+ argintreguse = max(rd->argintreguse, md->argintreguse);
+ argfltreguse = max(rd->argfltreguse, md->argfltreguse);
+#else
+ argintreguse = rd->argintreguse;
+ argfltreguse = rd->argfltreguse;
+#endif
int_sav_top = int_reg->sav_top = INT_SAV_CNT;
int_reg->sav_reg = DMNEW(int, int_reg->sav_top);
int_reg->tmp_top = INT_TMP_CNT +
- max(0, (INT_ARG_CNT - rd->argintreguse));
+ max(0, (INT_ARG_CNT - argintreguse));
int_reg->tmp_reg = DMNEW(int, int_reg->tmp_top);
flt_sav_top =flt_reg->sav_top = FLT_SAV_CNT;
flt_reg->sav_reg = DMNEW(int, flt_reg->sav_top);
flt_reg->tmp_top = FLT_TMP_CNT +
- max(0 , (FLT_ARG_CNT - rd->argfltreguse));
+ max(0 , (FLT_ARG_CNT - argfltreguse));
flt_reg->tmp_reg = DMNEW(int, flt_reg->tmp_top);
/* copy temp and unused argument registers to flt_reg->tmp_reg and */
/* int_reg->tmp_reg */
for (i=0; i < INT_TMP_CNT; i++)
int_reg->tmp_reg[i]=rd->tmpintregs[i];
- for (j=rd->argintreguse; j < INT_ARG_CNT; j++, i++)
+ for (j=argintreguse; j < INT_ARG_CNT; j++, i++)
int_reg->tmp_reg[i]=rd->argintregs[j];
for (i=0; i < FLT_TMP_CNT; i++)
flt_reg->tmp_reg[i]=rd->tmpfltregs[i];
- for (j=rd->argfltreguse; j < FLT_ARG_CNT; j++, i++)
+ for (j=argfltreguse; j < FLT_ARG_CNT; j++, i++)
flt_reg->tmp_reg[i]=rd->argfltregs[j];
}
/* done */
}
-void lsra_insertion( struct lsradata *ls, int *a, int lo, int hi) {
+void lsra_insertion_sort( struct lsradata *ls, int *a, int lo, int hi) {
int i,j,t,tmp;
for (i=lo+1; i<=hi; i++) {
if (lo < j) lsra_qsort( ls, a, lo, j);
if (i < hi) lsra_qsort( ls, a, i, hi);
} else
- lsra_insertion(ls, a, lo, hi);
+ lsra_insertion_sort(ls, a, lo, hi);
}
}
}
}
-void lsra_main(methodinfo *m, lsradata *ls, registerdata *rd, codegendata *cd)
-{
-#ifdef LSRA_DEBUG
+void lsra_main(jitdata *jd) {
+#ifdef LSRA_DEBUG_VERBOSE
int i;
#endif
int lsra_mem_use;
int lsra_reg_use;
struct lsra_register flt_reg, int_reg;
+ lsradata *ls;
+ registerdata *rd;
+#if defined(__I386__)
+ methodinfo *m;
+
+ m = jd->m;
+#endif
+ ls = jd->ls;
+ rd = jd->rd;
/* sort lifetimes by increasing start */
lsra_qsort( ls, ls->lt_mem, 0, ls->lt_mem_count - 1);
/* sort local vars used as parameter */
lsra_param_sort( ls, ls->lt_int, ls->lt_int_count);
lsra_param_sort( ls, ls->lt_flt, ls->lt_flt_count);
- lsra_reg_setup(m, rd, &int_reg, &flt_reg);
-
-#ifdef LSRA_DEBUG
- printf("INTSAV REG: ");
- for (i=0; i<int_reg.sav_top; i++)
- printf("%2i ",int_reg.sav_reg[i]);
- printf("\nINTTMP REG: ");
- for (i=0; i<int_reg.tmp_top; i++)
- printf("%2i ",int_reg.tmp_reg[i]);
- printf("\nFLTSAV REG: ");
- for (i=0; i<flt_reg.sav_top; i++)
- printf("%2i ",flt_reg.sav_reg[i]);
- printf("\nFLTTMP REG: ");
- for (i=0; i<flt_reg.tmp_top; i++)
- printf("%2i ",flt_reg.tmp_reg[i]);
- printf("\n");
+ lsra_reg_setup(jd, &int_reg, &flt_reg);
+
+#ifdef LSRA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("INTSAV REG: ");
+ for (i=0; i<int_reg.sav_top; i++)
+ printf("%2i ",int_reg.sav_reg[i]);
+ printf("\nINTTMP REG: ");
+ for (i=0; i<int_reg.tmp_top; i++)
+ printf("%2i ",int_reg.tmp_reg[i]);
+ printf("\nFLTSAV REG: ");
+ for (i=0; i<flt_reg.sav_top; i++)
+ printf("%2i ",flt_reg.sav_reg[i]);
+ printf("\nFLTTMP REG: ");
+ for (i=0; i<flt_reg.tmp_top; i++)
+ printf("%2i ",flt_reg.tmp_reg[i]);
+ printf("\n");
+ }
#endif
ls->active_tmp = DMNEW( struct lifetime *, max(INT_REG_CNT, FLT_REG_CNT));
ls->active_sav = DMNEW( struct lifetime *, max(INT_REG_CNT, FLT_REG_CNT));
lsra_reg_use=INT_SAV_CNT; /* init to no saved reg used... */
- _lsra_main(m, ls, ls->lt_int, ls->lt_int_count, &int_reg,
- &lsra_reg_use);
- if (lsra_reg_use > INT_SAV_CNT) lsra_reg_use=INT_SAV_CNT;
+ _lsra_main(jd, ls->lt_int, ls->lt_int_count, &int_reg, &lsra_reg_use);
+ if (lsra_reg_use > INT_SAV_CNT)
+ lsra_reg_use=INT_SAV_CNT;
rd->savintreguse = lsra_reg_use;
lsra_reg_use = FLT_SAV_CNT; /* no saved reg used... */
-
- _lsra_main(m,ls, ls->lt_flt, ls->lt_flt_count, &flt_reg, &lsra_reg_use);
- if (lsra_reg_use > FLT_SAV_CNT) lsra_reg_use=FLT_SAV_CNT;
-
+ _lsra_main(jd, ls->lt_flt, ls->lt_flt_count, &flt_reg, &lsra_reg_use);
+ if (lsra_reg_use > FLT_SAV_CNT)
+ lsra_reg_use=FLT_SAV_CNT;
rd->savfltreguse=lsra_reg_use;
/* rd->memuse was already set in stack.c to allocate stack space for */
lsra_mem_use = rd->memuse; /* Init with memuse from stack.c */
- lsra_alloc(m, rd, ls, ls->lt_mem, ls->lt_mem_count, &lsra_mem_use);
- lsra_alloc(m, rd, ls, ls->lt_int, ls->lt_int_count, &lsra_mem_use);
- lsra_alloc(m, rd, ls, ls->lt_flt, ls->lt_flt_count, &lsra_mem_use);
+ lsra_alloc(jd, ls->lt_mem, ls->lt_mem_count, &lsra_mem_use);
+ lsra_alloc(jd, ls->lt_int, ls->lt_int_count, &lsra_mem_use);
+ lsra_alloc(jd, ls->lt_flt, ls->lt_flt_count, &lsra_mem_use);
-#ifdef LSRA_PRINTLIFETIMES
- printf("Int RA complete \n");
- printf("Lifetimes after splitting int: \n");
- print_lifetimes(rd, ls, ls->lt_int, ls->lt_int_count);
-
- printf("Flt RA complete \n");
- printf("Lifetimes after splitting flt:\n");
- print_lifetimes(rd, ls, ls->lt_flt, ls->lt_flt_count);
-
- printf("Rest RA complete \n");
- printf("Lifetimes after leftt:\n");
- print_lifetimes(rd, ls, ls->lt_mem, ls->lt_mem_count);
-#endif
rd->memuse=lsra_mem_use;
-#ifdef LSRA_TESTLT
- test_lifetimes(m, ls, rd );
-#endif
+#ifdef LSRA_DEBUG_VERBOSE
+ if (compileverbose) {
+ printf("Int RA complete \n");
+ printf("Lifetimes after splitting int: \n");
+ print_lifetimes(jd, ls->lt_int, ls->lt_int_count);
+
+ printf("Flt RA complete \n");
+ printf("Lifetimes after splitting flt:\n");
+ print_lifetimes(jd, ls->lt_flt, ls->lt_flt_count);
+
+ printf("Rest RA complete \n");
+ printf("Lifetimes after leftt:\n");
+ print_lifetimes(jd, ls->lt_mem, ls->lt_mem_count);
+ }
+#endif
}
-void lsra_alloc(methodinfo *m, registerdata *rd, struct lsradata *ls, int *lifet, int lifetimecount, int *mem_use)
+void lsra_alloc(jitdata *jd, int *lifet, int lifetimecount, int *mem_use)
{
int flags,regoff;
struct lifetime *lt;
#ifdef HAS_4BYTE_STACKSLOT
struct freemem *fmem_2;
#endif
+ registerdata *rd;
+ lsradata *ls;
+
+ rd = jd->rd;
+ ls = jd->ls;
- fmem=DNEW(struct freemem);
- fmem->off=-1;
- fmem->next=NULL;
+ fmem = DNEW(struct freemem);
+ fmem->off = -1;
+ fmem->next = NULL;
#ifdef HAS_4BYTE_STACKSLOT
fmem_2=DNEW(struct freemem);
- fmem_2->off=-1;
- fmem_2->next=NULL;
+ fmem_2->off = -1;
+ fmem_2->next = NULL;
#endif
for (lt_index = 0; lt_index < lifetimecount; lt_index ++) {
lt = &(ls->lifetime[lifet[lt_index]]);
#ifdef LSRA_MEMORY
- lt->reg=-1;
+ lt->reg = -1;
#endif
- if (lt->reg==-1) {
- flags=INMEMORY;
+ if (lt->reg == -1) {
+ flags = INMEMORY;
#ifdef HAS_4BYTE_STACKSLOT
if (IS_2_WORD_TYPE(lt->type))
- regoff=lsra_getmem(lt, fmem_2, mem_use);
+ regoff = lsra_getmem(lt, fmem_2, mem_use);
else
#endif
- regoff=lsra_getmem(lt, fmem, mem_use);
+ regoff = lsra_getmem(lt, fmem, mem_use);
} else {
- flags=lt->savedvar;
- regoff=lt->reg;
+ flags = lt->savedvar;
+ regoff = lt->reg;
}
if (lt->v_index < 0) {
- for (n=lt->local_ss; n!=NULL; n=n->next) {
- lsra_setflags( &(n->s->flags), flags);
- n->s->regoff=regoff;
+ for (n = lt->local_ss; n != NULL; n = n->next) {
+ lsra_setflags(&(n->s->flags), flags);
+ n->s->regoff = regoff;
}
} else { /* local var */
- if (rd->locals[lt->v_index][lt->type].type>=0) {
- rd->locals[lt->v_index][lt->type].flags= flags;
- rd->locals[lt->v_index][lt->type].regoff=regoff;
- } else { log_text("Type Data mismatch 1\n"); assert(0); }
+ if (rd->locals[lt->v_index][lt->type].type >= 0) {
+ rd->locals[lt->v_index][lt->type].flags = flags;
+ rd->locals[lt->v_index][lt->type].regoff = regoff;
+ } else {
+ log_text("Type Data mismatch\n");
+ abort();
+ }
}
lt->reg = regoff;
}
{
struct freemem *fm, *p;
- /* noch kein Speicher vergeben, oder alle Enden später */
+ /* no Memory Slot allocated till now or all are still live */
if ((fmem->next == NULL) || (fmem->next->end > lt->i_start)) {
#ifdef HAS_4BYTE_STACKSLOT
if (IS_2_WORD_TYPE(lt->type))
fm=lsra_getnewmem(mem_use);
#endif
} else {
- /* Speicherstelle frei */
- fm=fmem->next;
- fmem->next=fm->next;
- fm->next=NULL;
- }
- fm->end=lt->i_end;
- for (p=fmem; (p->next!=NULL) && (p->next->end < fm->end); p=p->next);
- fm->next=p->next;
- p->next=fm;
+ /* Memoryslot free */
+ fm = fmem->next;
+ fmem->next = fm->next;
+ fm->next = NULL;
+ }
+ fm->end = lt->i_end;
+ for (p = fmem; (p->next != NULL) && (p->next->end < fm->end); p = p->next);
+ fm->next = p->next;
+ p->next = fm;
return fm->off;
}
{
struct freemem *fm;
- fm=DNEW(struct freemem);
- fm->next=NULL;
- fm->off=*mem_use;
+ fm = DNEW(struct freemem);
+ fm->next = NULL;
+ fm->off = *mem_use;
(*mem_use)++;
return fm;
}
-void _lsra_main( methodinfo *m, lsradata *ls, int *lifet, int lifetimecount,
- struct lsra_register *reg, int *reg_use)
+void _lsra_main(jitdata *jd, int *lifet, int lifetimecount,
+ struct lsra_register *reg, int *reg_use)
{
struct lifetime *lt;
int lt_index;
int reg_index;
int regsneeded;
bool temp; /* reg from temp registers (true) or saved registers (false) */
+ methodinfo *m;
+ lsradata *ls;
+
+ m = jd->m;
+ ls = jd->ls;
#if !defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
regsneeded = 0;
regsneeded = (lt->type == TYPE_LNG)?1:0;
#endif
- lsra_expire_old_intervalls(m, ls, lt, reg);
+ lsra_expire_old_intervalls(jd, lt, reg);
reg_index = -1;
temp = false;
- if (lt->savedvar || m->isleafmethod) {
+ if (lt->savedvar || jd->isleafmethod) {
/* use Saved Reg (in case of leafmethod all regs are saved regs) */
if (reg->sav_top > regsneeded) {
#if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
}
}
if (reg_index == -1) /* no reg is available anymore... -> spill */
- spill_at_intervall(m, ls, lt);
+ spill_at_intervall(jd, lt);
else {
lt->reg = reg_index;
if (temp)
}
}
-void lsra_add_active(struct lifetime *lt, struct lifetime **active, int *active_top)
+void lsra_add_active(struct lifetime *lt, struct lifetime **active,
+ int *active_top)
{
int i, j;
for(i = 0; (i < *active_top) && (active[i]->i_end < lt->i_end); i++);
-
for(j = *active_top; j > i; j--) active[j] = active[j-1];
-
(*active_top)++;
-
active[i] = lt;
-
}
-void lsra_expire_old_intervalls(methodinfo *m, lsradata *ls,
- struct lifetime *lt, struct lsra_register *reg)
+void lsra_expire_old_intervalls(jitdata *jd, struct lifetime *lt,
+ struct lsra_register *reg)
{
- _lsra_expire_old_intervalls(m, lt, reg, ls->active_tmp, &(ls->active_tmp_top));
- _lsra_expire_old_intervalls(m, lt, reg, ls->active_sav, &(ls->active_sav_top));
+ _lsra_expire_old_intervalls(jd, lt, reg, jd->ls->active_tmp,
+ &(jd->ls->active_tmp_top));
+ _lsra_expire_old_intervalls(jd, lt, reg, jd->ls->active_sav,
+ &(jd->ls->active_sav_top));
}
-void _lsra_expire_old_intervalls(methodinfo *m, struct lifetime *lt,
+void _lsra_expire_old_intervalls(jitdata *jd, struct lifetime *lt,
struct lsra_register *reg,
struct lifetime **active, int *active_top)
{
if (active[i]->i_end > lt->i_start) break;
/* make active[i]->reg available again */
- if (m->isleafmethod) {
+ if (jd->isleafmethod) {
/* leafmethod -> don't care about type -> put all again into */
/* reg->sav_reg */
#if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
}
-void spill_at_intervall(methodinfo *m, lsradata *ls, struct lifetime *lt )
+void spill_at_intervall(jitdata *jd, struct lifetime *lt )
{
- if (lt->savedvar || m->isleafmethod) {
- _spill_at_intervall(lt, ls->active_sav, &(ls->active_sav_top));
+ if (lt->savedvar || jd->isleafmethod) {
+ _spill_at_intervall(lt, jd->ls->active_sav, &(jd->ls->active_sav_top));
} else {
- _spill_at_intervall(lt, ls->active_tmp, &(ls->active_tmp_top));
- if (lt->reg == -1) { /* kein tmp mehr frei gewesen */
- _spill_at_intervall(lt, ls->active_sav, &(ls->active_sav_top));
+ _spill_at_intervall(lt, jd->ls->active_tmp, &(jd->ls->active_tmp_top));
+ if (lt->reg == -1) { /* no tmp free anymore */
+ _spill_at_intervall(lt, jd->ls->active_sav,
+ &(jd->ls->active_sav_top));
}
}
}
-void _spill_at_intervall(struct lifetime *lt, struct lifetime **active, int *active_top)
+void _spill_at_intervall(struct lifetime *lt, struct lifetime **active,
+ int *active_top)
{
int i, j;
-#if 0
-#ifdef USAGE_COUNT
+#ifdef USAGE_COUNT_EXACT
int u_min, i_min;
-#endif
#endif
if (*active_top == 0) {
}
i = *active_top - 1;
-#ifdef USAGE_COUNT
-#if 0
- /* find intervall which ends later or equal than than lt and has the lowest usagecount lower than lt*/
+#if defined(USAGE_COUNT_EXACT)
+ /* find intervall which ends later or equal than than lt and has the lowest
+ usagecount lower than lt */
i_min = -1;
u_min = lt->usagecount;
for (; (i >= 0) && (active[i]->i_end >= lt->i_end); i--) {
if (i_min != -1) {
i = i_min;
-#endif
- if ((active[i]->i_end >= lt->i_end) && (active[i]->usagecount < lt->usagecount)) {
#else
+# if defined(USAGE_COUNT) && !defined(USAGE_COUNT_EXACT)
+ if ((active[i]->i_end >= lt->i_end)
+ && (active[i]->usagecount < lt->usagecount)) {
+# else /* "normal" LSRA heuristic */
/* get last intervall from active */
if (active[i]->i_end > lt->i_end) {
+# endif
#endif
#if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
/* Don't spill between one and two word int types */
if ((active[i]->type == TYPE_LNG) != (lt->type == TYPE_LNG))
return;
#endif
-
- lt->reg=active[i]->reg;
+ lt->reg = active[i]->reg;
active[i]->reg=-1;
-
+
(*active_top)--;
for (j = i; j < *active_top; j++)
active[j] = active[j + 1];
}
}
-void lsra_calc_lifetime_length(methodinfo *m, lsradata *ls, codegendata *cd)
-{
+void lsra_calc_lifetime_length(jitdata *jd) {
+ methodinfo *m;
+ lsradata *ls;
+ codegendata *cd;
struct lifetime *lt;
- int i, lt_index;
- int lifetimecount;
-#if 0
- struct stackslot *ss;
+#if defined(LSRA_DEBUG_VERBOSE) || !defined(LV)
+ int i;
#endif
- int *icount_block, icount;
+ int lt_index;
+ int lifetimecount;
int flags; /* 0 INMEMORY -> ls->lt_mem */
/* 1 INTREG -> ls->lt_int */
/* 2 FLTREG -> ls->lt_flt */
-#if 0
- int max_local_ss;
- int cum_local_ss,local_ss_count;
- int i_count;
-#endif
- icount_block = DMNEW(int, m->basicblockcount);
- icount_block[0] = icount = 0;
- for (i=1; i < m->basicblockcount; i++) {
- if (ls->sorted[i-1] != -1)
- icount += m->basicblocks[ ls->sorted[i-1] ].icount;
- if (ls->sorted[i] != -1)
- icount_block[i] = icount;
- }
+ m = jd->m;
+ ls = jd->ls;
+ cd = jd->cd;
-#ifdef LSRA_DEBUG
+#ifdef LSRA_DEBUG_VERBOSE
+ if (compileverbose) {
printf("icount_block: ");
for (i=0; i < m->basicblockcount; i++)
- printf("(%3i-%3i) ",i, icount_block[i]);
+ printf("(%3i-%3i) ",i, ls->icount_block[i]);
printf("\n");
+ }
#endif
- /* extend lifetime over backedges */
- /* now iterate through lifetimes and expand them */
+ /* extend lifetime over backedges (for the lsra version without exact
+ liveness analysis)
+ now iterate through lifetimes and expand them */
-#if 0
- max_local_ss = cum_local_ss = 0;
-#endif
lifetimecount = 0;
for(lt_index = 0 ;lt_index < ls->lifetimecount; lt_index++) {
if ( ls->lifetime[lt_index].type != -1) { /* used lifetime */
/* remember lt_index in lt_sorted */
- ls->lt_used[lifetimecount ++] = lt_index;
+ ls->lt_used[lifetimecount++] = lt_index;
lt = &(ls->lifetime[lt_index]);
#if defined(SUPPORT_COMBINE_INTEGER_REGISTERS)
- /* prevent conflicts between lifetimes of type long by increasing */
- /* the lifetime by one instruction */
- /* i.e.(ri/rj) ... */
- /* (rk/rl) ICMD_LNEG */
- /* with i==l and/or j==k */
- /* to resolve this during codegeneration a temporary register */
- /* would be needed */
+ /* prevent conflicts between lifetimes of type long by increasing
+ the lifetime by one instruction
+ i.e.(ri/rj) ...
+ (rk/rl) ICMD_LNEG
+ with i==l and/or j==k
+ to resolve this during codegeneration a temporary register
+ would be needed */
if (lt->type == TYPE_LNG)
lt->i_last_use++;
#endif
}
-#if 0
- local_ss_count = 0;
- for (ss=lt->local_ss; ss != 0; ss = ss->next, local_ss_count++);
- if (local_ss_count > max_local_ss) max_local_ss = local_ss_count;
- cum_local_ss+=local_ss_count;
+ if (lt->i_first_def == INT_MAX) {
+#ifdef LSRA_DEBUG_VERBOSE
+ printf("Warning: var not defined! vi: %i start: %i end: %i\n",
+ lt->v_index, lt->i_start, lt->i_end);
#endif
-
- if (lt->bb_first_def == -1) {
-/* printf("--------- Warning: variable not defined!------------------vi: %i start: %i end: %i\n", lt->v_index, lt->i_start, lt->i_end); */
lt->bb_first_def = 0;
lt->i_first_def = 0;
}
- lt->i_start = icount_block[lt->bb_first_def] + lt->i_first_def;
+ lt->i_start = lt->i_first_def;
- if (lt->bb_last_use == -1) {
-/* printf("--------- Warning: variable not used! --------------------vi: %i start: %i end: %i\n", lt->v_index, lt->i_start, lt->i_end); */
+ if (lt->i_last_use == -2) {
+#ifdef LSRA_DEBUG_VERBOSE
+ printf("Warning: Var not used! vi: %i start: %i end: %i\n",
+ lt->v_index, lt->i_start, lt->i_end);
+#endif
lt->bb_last_use = lt->bb_first_def;
lt->i_last_use = lt->i_first_def;
}
- lt->i_end = icount_block[lt->bb_last_use] + lt->i_last_use;
+ lt->i_end = lt->i_last_use;
+#ifdef LSRA_DEBUG_VERBOSE
if (lt->i_start > lt->i_end)
printf("Warning: last use before first def! vi: %i start: %i end: %i\n", lt->v_index, lt->i_start, lt->i_end);
+#endif
+#if !defined(LV)
if ((lt->bb_first_def != lt->bb_last_use) ||
(lt->i_first_def == -1)) {
/* Lifetime goes over more than one Basic Block -> */
/* see lsra_get_backedges */
/* Arguments are set "before" Block 0, so they have */
/* a lifespan of more then one block, too */
-
+
for (i=0; i < ls->backedge_count; i++) {
if (!( (lt->bb_first_def > ls->backedge[i]->start) ||
(lt->bb_last_use < ls->backedge[i]->end) )) {
/* Live intervall intersects with a backedge */
/* if (lt->bb_first_def <= ls->backedge[i]->start) */
if (lt->bb_last_use <= ls->backedge[i]->start)
- lt->i_end = icount_block[ls->backedge[i]->start] +
+ lt->i_end =
+ ls->icount_block[ls->backedge[i]->start] +
m->basicblocks[ls->sorted[ls->backedge[i]->start]].icount;
- }
+ }
}
}
+#endif /* !defined(LV) */
+
#ifdef USAGE_PER_INSTR
lt->usagecount = lt->usagecount / ( lt->i_end - lt->i_start + 1);
#endif
}
}
ls->lifetimecount = lifetimecount;
-#if 0
- i_count=0;
- for (i=0; i<m->basicblockcount; i++)
- if (m->basicblocks[i].flags >= BBREACHED)
- i_count+=m->basicblocks[i].icount;
- printf("Instr: %5i Lifetimes: %5i Local SS Max: %4i Cum: %4i m->maxlifetimes %4i\n",i_count, lifetimecount, max_local_ss, cum_local_ss, m->maxlifetimes);
-#endif
}
-#ifdef LSRA_PRINTLIFETIMES
-void print_lifetimes(registerdata *rd, lsradata *ls, int *lt, int lifetimecount)
+#ifdef LSRA_DEBUG_VERBOSE
+void print_lifetimes(jitdata *jd, int *lt, int lifetimecount)
{
struct lifetime *n;
int lt_index;
int type,flags,regoff,varkind;
+ lsradata *ls;
+ registerdata *rd;
+
+ ls = jd->ls;
+ rd = jd->rd;
+
for (lt_index = 0; lt_index < lifetimecount; lt_index++) {
n = &(ls->lifetime[lt[lt_index]]);
+ if (n->savedvar == SAVEDVAR)
+ printf("S");
+ else
+ printf(" ");
if (n->v_index < 0) { /* stackslot */
type = n->local_ss->s->type;
flags=n->local_ss->s->flags;
} else
{ log_text("Type Data mismatch 3\n"); assert(0); }
}
+#if !defined(LV)
printf("i_Start: %3i(%3i,%3i) i_stop: %3i(%3i,%3i) reg: %3i VI: %3i type: %3i flags: %3i varkind: %3i usage: %3li ltflags: %xi \n",n->i_start, ls->sorted[n->bb_first_def], n->i_first_def,n->i_end, ls->sorted[n->bb_last_use], n->i_last_use,regoff,n->v_index,type,flags, varkind, n->usagecount, n->flags);
+#else
+ printf("i_Start: %3i i_stop: %3i reg: %3i VI: %3i type: %3i flags: %3i varkind: %3i usage: %3li ltflags: %xi \n",n->i_start, n->i_end, regoff,n->v_index,type,flags, varkind, n->usagecount, n->flags);
+#endif
}
printf( "%3i Lifetimes printed \n",lt_index);
}
#endif
+
+
+/******************************************************************************
+Helpers for first LSRA Version without exact Liveness Analysis
+ *****************************************************************************/
+
+#if !defined(LV)
+bool lsra_join_ss( struct lsradata *ls, struct stackelement *in,
+ struct stackelement *out, int join_flag) {
+ struct lifetime *lt, *lto;
+ struct stackslot *ss, *ss_last;
+
+
+ if (in->varnum != out->varnum) {
+ lt = &(ls->lifetime[-in->varnum - 1]);
+
+#ifdef LSRA_DEBUG_CHECK
+ if (join_flag == JOIN_BB)
+ if (lt->type == -1) {
+ log_text("lsra_join_ss: lifetime for instack not found\n");
+ assert(0);
+ }
+#endif
+
+ if (out->varnum >= 0) { /* no lifetime for this slot till now */
+ lsra_add_ss(lt, out);
+ } else {
+ lto = &(ls->lifetime[-out->varnum - 1]);
+ if ((join_flag == JOIN_DUP) || (join_flag == JOIN_OP))
+ if ( (lt->flags & JOIN_BB) || (lto->flags & JOIN_BB)) {
+ return false;
+ }
+ if (join_flag == JOIN_DUP)
+ if ( (lt->flags & JOIN_OP) || (lto->flags & JOIN_OP)) {
+ return false;
+ }
+#ifdef LSRA_DEBUG_CHECK
+ if (lto->type == -1) {
+ log_text("lsra_join_ss: lifetime for outstack not found\n");
+ abort();
+ }
+#endif
+#ifdef LSRA_DEBUG_CHECK
+ if (lto->type != lt->type) {
+ log_text("lsra_join_ss: in/out stack type mismatch\n");
+ abort();
+ }
+#endif
+
+ lt->flags |= JOINING;
+
+ /* take Lifetime lto out of ls->lifetimes */
+ lto->type = -1;
+
+ /* merge lto into lt of in */
+
+ ss_last = ss = lto->local_ss;
+ while (ss != NULL) {
+ ss_last = ss;
+ ss->s->varnum = lt->v_index;
+ ss = ss->next;
+ }
+ if (ss_last != NULL) {
+ ss_last->next = lt->local_ss;
+ lt->local_ss = lto->local_ss;
+ }
+
+ lt->savedvar |= lto->savedvar;
+ lt->flags |= lto->flags | join_flag;
+ lt->usagecount += lto->usagecount;
+
+ /*join of i_first_def and i_last_use */
+ if (lto->i_first_def < lt->i_first_def) {
+ lt->i_first_def = lto->i_first_def;
+ }
+ if (lto->i_last_use > lt->i_last_use) {
+ lt->i_last_use = lto->i_last_use;
+ }
+ }
+ }
+ return true;
+}
+
+/* join instack of Basic Block b_index with outstack of predecessors */
+void lsra_join_lifetimes(jitdata *jd,int b_index) {
+ methodinfo *m;
+ lsradata *ls;
+ struct stackelement *in, *i, *out;
+ struct _list *pred;
+
+ m = jd->m;
+ ls = jd->ls;
+
+ /* 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) {
+ lsra_join_ss(ls, i, out, JOIN_BB);
+ }
+ }
+ }
+}
+
struct stackslot *lsra_make_ss(stackptr s, int bb_index)
{
struct stackslot *ss;
- ss=DNEW(struct stackslot);
- ss->bb=bb_index;
- ss->s=s;
+ ss = DNEW(struct stackslot);
+ ss->bb = bb_index;
+ ss->s = s;
return ss;
}
void lsra_add_ss(struct lifetime *lt, stackptr s) {
struct stackslot *ss;
- /* Stackslot noch nicht eingetragen? */
+ /* Stackslot not in list? */
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;
-#if 0
- printf("New ss vn %i s %p ss %p\n",ss->s->varnum, ss->s, ss);
-#endif
+ if (s != NULL)
+ lt->savedvar |= s->flags & SAVEDVAR;
+ if (s != NULL)
+ lt->type = s->type;
}
}
struct lifetime *n;
if (s->varnum >= 0) { /* new stackslot lifetime */
+#ifdef LSRA_DEBUG_CHECK_VERBOSE
if (-ls->v_index - 1 >= ls->maxlifetimes) {
printf("%i %i\n", -ls->v_index - 1, ls->maxlifetimes);
}
- assert(-ls->v_index - 1 < ls->maxlifetimes);
+#endif
+ _LSRA_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->bb_last_use = -1;
+ n->bb_last_use = -1;
n->bb_first_def = -1;
+ n->i_last_use = -2; /* At -1 param init happens, so -2 is below all
+ possible instruction indices */
+ n->i_first_def = INT_MAX;
n->local_ss = NULL;
n->savedvar = 0;
- n->flags = 0;
+ n->flags = 0;
} else
n = &(ls->lifetime[-s->varnum - 1]);
if (IS_TEMP_VAR(s1)) { \
join_ret = false; \
if (IS_TEMP_VAR(s2)) \
- join_ret = lsra_join_ss(ls, s1, s2, JOIN);/* undangerous join!*/ \
+ join_ret = lsra_join_ss(ls, s1, s2, JOIN); \
+ /* undangerous join!*/\
if (IS_TEMP_VAR(s3)) { \
if (join_ret) /* first join succesfull -> second of type */ \
/* JOIN_DUP */ \
lsra_join_ss(ls, s2, s3, JOIN_DUP); \
}
-#define lsra_new_stack(ls, s, block, instr) if ((s)->varkind != ARGVAR) _lsra_new_stack(ls, s, block, instr, LSRA_STORE)
+#define lsra_new_stack(ls, s, block, instr) \
+ if ((s)->varkind != ARGVAR) _lsra_new_stack(ls, s, block, instr, LSRA_STORE)
void _lsra_new_stack(lsradata *ls, stackptr s, int block, int instr, int store)
{
struct lifetime *n;
lsra_usage_local(ls, s->varnum, s->type, block, instr, LSRA_STORE);
} else /* if (s->varkind != ARGVAR) */ {
- n=get_ss_lifetime( ls, s );
+ n=get_ss_lifetime(ls, s);
if (store == LSRA_BB_IN)
n->flags |= JOIN_BB;
/* remember first def -> overwrite everytime */
n->bb_first_def = ls->sorted_rev[block];
- n->i_first_def = instr;
+ n->i_first_def = ls->icount_block[ls->sorted_rev[block]] + instr;
n->usagecount+=ls->nesting[ls->sorted_rev[block]];
}
}
-#define lsra_from_stack(ls, s, block, instr) if ((s)->varkind != ARGVAR) _lsra_from_stack(ls, s, block, instr, LSRA_LOAD)
-#define lsra_pop_from_stack(ls, s, block, instr) if ((s)->varkind != ARGVAR) _lsra_from_stack(ls, s, block, instr, LSRA_POP)
+#define lsra_from_stack(ls, s, block, instr) \
+ if ((s)->varkind != ARGVAR) _lsra_from_stack(ls, s, block, instr, LSRA_LOAD)
+#define lsra_pop_from_stack(ls, s, block, instr) \
+ if ((s)->varkind != ARGVAR) _lsra_from_stack(ls, s, block, instr, LSRA_POP)
void _lsra_from_stack(lsradata *ls, stackptr s, int block, int instr, int store)
{
struct lifetime *n;
/* No STACKVARS possible with lsra! */
s->varkind = TEMPVAR;
- n=get_ss_lifetime( ls, s );
+ n=get_ss_lifetime(ls, s);
if (store == LSRA_BB_OUT)
n->flags |= JOIN_BB;
/* remember last USE, so only write, if USE Field is undefined (==-1) */
if (n->bb_last_use == -1) {
n->bb_last_use = ls->sorted_rev[block];
- n->i_last_use = instr;
+ n->i_last_use = ls->icount_block[ls->sorted_rev[block]] + instr;
}
}
}
-void lsra_usage_local(lsradata *ls, s4 v_index, int type, int block, int instr, int store)
+void lsra_usage_local(lsradata *ls, s4 v_index, int type, int block, int instr,
+ int store)
{
struct lifetime *n;
n = &(ls->lifetime[ ls->maxlifetimes + v_index * (TYPE_ADR+1) + type]);
if (n->type == -1) { /* new local lifetime */
-#ifdef LSRA_DEBUG
-/* if (store != LSRA_STORE) printf("lsra_local_store: Read before write Local var: %i paramcount: ?\n", v_index); */
-#endif
n->local_ss=NULL;
n->v_index=v_index;
n->type=type;
n->bb_last_use = -1;
n->bb_first_def = -1;
+ n->i_last_use = -2;
+ n->i_first_def = INT_MAX;
}
n->usagecount+=ls->nesting[ls->sorted_rev[block]];
/* add access at (block, instr) to instruction list */
/* other vars */
if (n->bb_last_use == -1) {
n->bb_last_use = ls->sorted_rev[block];
- n->i_last_use = instr;
+ n->i_last_use = ls->icount_block[ls->sorted_rev[block]] + instr;
}
if (store == LSRA_STORE) {
/* store == LSRA_STORE, remember first def -> overwrite everytime */
n->bb_first_def = ls->sorted_rev[block];
- n->i_first_def = instr;
+ n->i_first_def = ls->icount_block[ls->sorted_rev[block]] + instr;
}
}
-#ifdef LSRA_DEBUG
+#ifdef LSRA_DEBUG_VERBOSE
void lsra_dump_stack(stackptr s)
{
while (s!=NULL) {
- printf("%p(R%3i N%3i K%3i T%3i F%3i) ",(void *)s,s->regoff, s->varnum, s->varkind, s->type, s->flags);
+ printf("%p(R%3i N%3i K%3i T%3i F%3i) ",(void *)s,s->regoff, s->varnum,
+ s->varkind, s->type, s->flags);
s=s->prev;
}
printf("\n");
#endif
-void lsra_scan_registers_canditates(methodinfo *m, lsradata *ls, int b_index)
+void lsra_scan_registers_canditates(jitdata *jd, int b_index)
{
- methodinfo *lm;
+/* methodinfo *lm; */
builtintable_entry *bte;
methoddesc *md;
int i;
stackptr dst;
instruction *iptr;
bool join_ret; /* for lsra_join* Macros */
-#if defined(LSRA_USES_REG_RES)
- int v_index_min_before_instruction;
- int v_index_min[REG_RES_CNT];
+ methodinfo *m;
+ lsradata *ls;
- for (i=0; i < REG_RES_CNT; i++) {
- ls->reg_res_free[i] = -1;
- v_index_min[i] = ls->v_index;
- }
-#endif
+ m = jd->m;
+ ls = jd->ls;
/* get instruction count for BB and remember the max instruction count */
/* of all BBs */
src = m->basicblocks[b_index].instack;
if (m->basicblocks[b_index].type != BBTYPE_STD) {
-#ifdef LSRA_DEBUG
- if (src == NULL) {
- log_text("No Incoming Stackslot for Exception/Subroutine BB\n");
- assert(0);
- }
-#endif
lsra_new_stack(ls, src, b_index, 0);
- 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! */
- { log_text("LOCALVAR at basicblock instack\n"); assert(0); }
- else {
- if (src->varkind == STACKVAR )
- /* no Interfaces at BB Boundaries with LSRA! */
- /* -> change to TEMPVAR */
- src->varkind = TEMPVAR;
/*******************************************************************************
Check this - ? For every incoming Stack Slot a lifetime has to be created ?
*******************************************************************************/
_lsra_new_stack(ls, src, b_index, 0, LSRA_BB_IN);
- }
}
src = m->basicblocks[b_index].outstack;
for (;src != NULL; src=src->prev) {
- if (src->varkind == ARGVAR )
- { log_text("ARGVAR at basicblock outstack\n"); assert(0); }
- else if (src->varkind == LOCALVAR )
- { log_text("LOCALVAR at basicblock outstack\n"); assert(0); }
- else {
- /* no Interfaces at BB Boundaries with LSRA! */
- /* -> change to TEMPVAR */
- if (src->varkind == STACKVAR )
- src->varkind = TEMPVAR;
_lsra_from_stack(ls, src, b_index, iindex, LSRA_BB_OUT);
- }
}
-
+
/* set iptr to last instruction of BB */
iptr = m->basicblocks[b_index].iinstr + iindex;
for (;iindex >= 0; iindex--, iptr--) {
+
/* get source and destination Stack for the current instruction */
/* destination stack is available as iptr->dst */
+
dst = 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;
+ opcode = iptr->opc;
-#if defined(LSRA_USES_REG_RES)
- /* remember last Stack Slot v_index, so not all lifetimes have to */
- /* be checked for reserved register allocation */
- v_index_min_before_instruction = ls->v_index;
-#endif
-#ifdef LSRA_DEBUG
- /* printf("bb: %3i bcount: %3i iindex: %3i ilen: %3i opcode: %3i %s\n",b_index,m->basicblockcount,iindex,len,opcode,icmd_names[opcode]); */
- /* lsra_dump_stack(src); */
- /* lsra_dump_stack(dst); */
-#endif
- opcode = iptr->opc;
switch (opcode) {
/* pop 0 push 0 */
LSRA_LOAD);
break;
case ICMD_NOP:
- case ICMD_ELSE_ICONST:
+/* case ICMD_ELSE_ICONST: */
case ICMD_CHECKNULL:
case ICMD_JSR:
case ICMD_RETURN:
case ICMD_PUTSTATICCONST:
case ICMD_INLINE_START:
case ICMD_INLINE_END:
+ case ICMD_INLINE_GOTO:
break;
case ICMD_IINC:
/* pop 2 push 3 dup */
case ICMD_DUP_X1:
- lsra_from_stack(ls, src, b_index, iindex);
- lsra_from_stack(ls, src->prev, b_index, iindex);
+ lsra_from_stack(ls, src, b_index, iindex+1);
+ lsra_from_stack(ls, src->prev, b_index, iindex+1);
lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
lsra_new_stack(ls, dst->prev, b_index, iindex);
lsra_new_stack(ls, dst, b_index, iindex);
/* pop 3 push 4 dup */
case ICMD_DUP_X2:
- lsra_from_stack(ls, src,b_index, iindex);
- lsra_from_stack(ls, src->prev, b_index, iindex);
- lsra_from_stack(ls, src->prev->prev, b_index, iindex);
+ lsra_from_stack(ls, src,b_index, iindex+1);
+ lsra_from_stack(ls, src->prev, b_index, iindex+1);
+ lsra_from_stack(ls, src->prev->prev, b_index, iindex+1);
lsra_new_stack(ls, dst->prev->prev->prev, b_index, iindex);
lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
lsra_new_stack(ls, dst->prev, b_index, iindex);
/* pop 3 push 5 dup */
case ICMD_DUP2_X1:
- lsra_from_stack(ls, src, b_index, iindex);
- lsra_from_stack(ls, src->prev, b_index, iindex);
- lsra_from_stack(ls, src->prev->prev, b_index, iindex);
+ lsra_from_stack(ls, src, b_index, iindex+1);
+ lsra_from_stack(ls, src->prev, b_index, iindex+1);
+ lsra_from_stack(ls, src->prev->prev, b_index, iindex+1);
lsra_new_stack(ls, dst->prev->prev->prev->prev, b_index, iindex);
lsra_new_stack(ls, dst->prev->prev->prev, b_index, iindex);
lsra_new_stack(ls, dst->prev->prev, b_index, iindex);
/* pop 4 push 6 dup */
case ICMD_DUP2_X2:
- lsra_from_stack(ls, src, b_index, iindex);
- lsra_from_stack(ls, src->prev, b_index, iindex);
- lsra_from_stack(ls, src->prev->prev, b_index, iindex);
- lsra_from_stack(ls, src->prev->prev->prev, b_index, iindex);
+ lsra_from_stack(ls, src, b_index, iindex+1);
+ lsra_from_stack(ls, src->prev, b_index, iindex+1);
+ lsra_from_stack(ls, src->prev->prev, b_index, iindex+1);
+ lsra_from_stack(ls, src->prev->prev->prev, b_index, iindex+1);
lsra_new_stack(ls, dst->prev->prev->prev->prev->prev, b_index,
iindex);
lsra_new_stack(ls, dst->prev->prev->prev->prev, b_index, iindex);
/* pop 2 push 2 swap */
case ICMD_SWAP:
- lsra_from_stack(ls, src, b_index, iindex);
- lsra_from_stack(ls, src->prev, b_index, iindex);
+ lsra_from_stack(ls, src, b_index, iindex+1);
+ lsra_from_stack(ls, src->prev, b_index, iindex+1);
lsra_new_stack(ls, dst->prev, b_index, iindex);
lsra_new_stack(ls, dst, b_index, iindex);
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_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:
iptr->opc);
return;
} /* switch */
-
-#if defined(LSRA_USES_REG_RES)
- {
- int /* length, */ maxlength, j;
- int index, reg_res,start_iindex, end_iindex;
- struct stackslot * ss;
- struct lifetime *n;
-
- end_iindex = -1;
-/* length = 0; */
-
- if ((reg_res = icmd_uses_reg_res[opcode][REG_RES_CNT])==REG_NULL)
- /* no preferred "output" register for this ICMD -> start with */
- /* EAX */
- reg_res = EAX;
- for (j=0; j < REG_RES_CNT; j++, reg_res=(reg_res+1)%REG_RES_CNT) {
- maxlength = -1;
- index = -1;
- if ((iindex == 0) || (icmd_uses_reg_res[opcode][reg_res])) {
- /* least iindex looked at, or reg_res does not */
- /* "fully" survivy this ICMD */
- if (ls->reg_res_free[reg_res] != -1) {
- /* reg_res is free from ls->reg_res_free[] til here */
- /* (iindex). Now search for the longest lifetime, */
- /* which fits in this intervall and if found assign */
- /* reg_res to it */
- if (icmd_uses_reg_res[opcode][reg_res] & D)
- /* ICMD destroys REG_RES as destination operand */
- start_iindex = iindex +1;
- else
- start_iindex = iindex;
- for (i = (-v_index_min[reg_res] - 1);
- i < (-ls->v_index -1); i++) {
- n = &(ls->lifetime[i]);
- if (!(n->flags & (JOINING || JOIN_BB))) {
- /* do not assign reserved Regs to lifetimes */
- /* not completely seen till now */
- if ((n->type == TYPE_INT)
- || (n->type == TYPE_ADR)) {
- if (n->savedvar == 0) {
- if ((n->bb_last_use == n->bb_first_def)
- && (n->bb_last_use
- == ls->sorted_rev[b_index])) {
- if ((n->i_last_use
- <= ls->reg_res_free[reg_res])
- && (n->i_first_def >=
- start_iindex)) {
-
-/* length = n->i_last_use - */
-/* n->i_first_def; */
-/* if (length > maxlength) { */
-/* maxlength = length; */
-/* index = i; */
-/* } */
-/* length++; */
- /* there is a lifetime, which a reserved register can */
- /* be assigned to */
-
- ls->lifetime[i].reg = lsra_reg_res[reg_res];
- for (ss = ls->lifetime[i].local_ss; ss != NULL;
- ss=ss->next) {
- ss->s->regoff = lsra_reg_res[reg_res];
- }
- /* drop lifetime, no further processing required */
- ls->lifetime[i].type = -1;
-
- ls->reg_res_free[reg_res] = n->i_first_def;
- }
- }
- }
- }
- }
- }
-/* if (length > 1) */
-/* printf("%i reg res Lifetimes assigned for this intervall \n",length); */
- }
- if (icmd_uses_reg_res[opcode][reg_res] & S)
- /* ICMD destroys REG_RES as source operand */
- ls->reg_res_free[reg_res] = -1;
- else
- ls->reg_res_free[reg_res] = iindex;
-
- v_index_min[reg_res] = v_index_min_before_instruction;
- } else
- if (ls->reg_res_free[reg_res] == -1)
- ls->reg_res_free[reg_res] = iindex;
- }
- }
-#endif /* defined(LSRA_USES_REG_RES) */
-#if 0
- {
- int i, j;
- stackptr t;
-
- i = 14; /* maxstack */
- t = dst;
-
- while (t) {
- i--;
- t = t->prev;
- }
- j = 14 - i;
- while (--i >= 0)
- printf(" ");
- t = dst;
- while (t) {
- printf(" %3i (%p)", t->varnum);
- t=t->prev;
- }
- printf(" %3i %s\n", iindex, icmd_names[opcode]);
- fflush(stdout);
- }
-#endif
-
}
}
+#endif /* defined(LV) */
-#ifdef LSRA_TESTLT
-
-int lsra_test_lt(registerdata *rd, struct lifetime *n, int store, int *values, bool inmemory) {
- int value_index;
-
- if (inmemory) {
- value_index = n->reg;
- } else {
- if (IS_FLT_DBL_TYPE(n->type)) {
- value_index = rd->memuse + INT_REG_CNT + n->reg;
- } else {
- value_index = rd->memuse + n->reg;
- }
- }
-
- if ((store == LSRA_LOAD) || (store == LSRA_POP)) {
- if (values[value_index] == VS) {
-#if 0
- /* this happens through not really returning right from subroutines while the test */
- /* so this (in this case) useless warning is inhibited till this case is handled */
- /* right */
- if (n->i_start != -1) { /* not a parameter */
- printf("lsra_test: Warning: v_index %3i type %3i reg %3i", n->v_index, n->type, n->reg);
- if (inmemory)
- printf (" MEM");
- printf(" not initialized\n");
- }
-#endif
- } else if (values[value_index] != n->v_index) {
- printf("lsra_test: Error: v_index %3i type %3i reg %3i", n->v_index, n->type, n->reg);
- if (inmemory)
- printf (" MEM ");
- printf("Conflict: %3i \n", values[value_index]);
- return (n->reg);
- }
-
- } else { /* LSRA_STORE */
- values[value_index] = n->v_index;
- }
- return -1;
-}
-
-int lsra_test_local( lsradata *ls, registerdata *rd, int v_index, int type, int store, int *values) {
- struct lifetime *n;
-
- n = &(ls->lifetime[ ls->maxlifetimes + v_index * (TYPE_ADR+1) + type]);
- if (n->type == -1)
- { log_text("lsra_test: Local Var Lifetime not initialized!\n"); assert(0); }
-
- return lsra_test_lt(rd, n, store, values, rd->locals[v_index][type].flags & INMEMORY);
-}
-
-#define lsra_test_new_stack( ls, rd, s, values) lsra_test_stack(ls, rd, s, values, LSRA_STORE)
-#define lsra_test_from_stack( ls, rd, s, values) lsra_test_stack(ls, rd, s, values,LSRA_LOAD)
-#define lsra_test_pop_from_stack( ls, rd, s, values) lsra_test_stack(ls, rd, s, values, LSRA_LOAD)
-int lsra_test_stack( lsradata *ls, registerdata *rd, stackptr s, int *values, int store)
-{
- struct lifetime *n;
- int value_index;
-
- if (s->varkind == LOCALVAR) {
- return lsra_test_local(ls, rd, s->varnum, s->type, store, values);
- }
- if (s->varkind != ARGVAR) {
- if (s->varnum >=0)
- { log_text("lsra_test: Stackslot not initialized!\n"); assert(0); }
- n = &(ls->lifetime[-s->varnum - 1]);
- if (n->type == -1)
- { log_text("lsra_test: Stackslot Lifetime not initialized!\n"); assert(0); }
-
- return lsra_test_lt(rd, n, store, values, s->flags & INMEMORY);
- }
- return -1;
-}
-
-int _test_lifetimes(methodinfo *m, lsradata *ls, registerdata *rd, int b_index, int *values, int rec_depth)
-{
- struct stackslot *ss;
- int *v, i, j;
-
-
- int opcode;
- int iindex;
- stackptr src;
- stackptr dst;
- instruction *iptr;
- methoddesc *md;
-
- struct _list *succ;
-
- bool end_of_method;
-
- int ret;
-
- if (rec_depth > 1000) {
- printf("%s.%s rec_depth > 1000\n", m->class->name->text, m->name->text);
- return -1;
- }
-
- ret = -1;
- end_of_method = false;
- iptr = m->basicblocks[b_index].iinstr;
-
- dst = m->basicblocks[b_index].instack;
-
- if (m->basicblocks[b_index].type != BBTYPE_STD) {
- /* init incoming stackslot (exception or return address) */
- ret = lsra_test_new_stack(ls, rd , dst , values);
-
- }
-
- for (iindex =0 ;(iindex < m->basicblocks[b_index].icount) && (ret == -1) ; iindex++, iptr++) {
- src = dst;
- dst = iptr->dst;
- opcode = iptr->opc;
-
- switch (opcode) {
-
- /* pop 0 push 0 */
- case ICMD_RET:
- ret = lsra_test_local(ls, rd, iptr->op1, TYPE_ADR, LSRA_LOAD, values); /* local read (return adress) */
- break;
- case ICMD_NOP:
- case ICMD_ELSE_ICONST:
- case ICMD_CHECKNULL:
- case ICMD_CHECKASIZE:
- case ICMD_CHECKEXCEPTION:
- case ICMD_JSR:
- case ICMD_GOTO:
- case ICMD_PUTSTATICCONST:
- case ICMD_INLINE_START:
- case ICMD_INLINE_END:
- break;
-
- case ICMD_RETURN:
- end_of_method = true;
- break;
-
- case ICMD_IINC:
- ret = lsra_test_local(ls, rd,iptr->op1,TYPE_INT, LSRA_LOAD, values); /* local */
- ret = lsra_test_local(ls, rd,iptr->op1,TYPE_INT, LSRA_STORE, values); /* local = local+<const> */
- 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 */
- ret = lsra_test_new_stack(ls, rd,dst, values); /* const->stack */
- 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) {
- ret = lsra_test_local(ls, rd,iptr->op1,opcode-ICMD_ILOAD, LSRA_LOAD, values); /* local->value */
- ret = lsra_test_new_stack(ls, rd,dst, values); /* value->stack */
- } else if (dst->varnum != iptr->op1) {
- ret = lsra_test_local(ls, rd,iptr->op1,opcode-ICMD_ILOAD, LSRA_LOAD, values); /* local->value */
- ret = lsra_test_local(ls, rd,dst->varnum,opcode-ICMD_ILOAD, LSRA_STORE, values); /* local->value */
- }
-
- 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:
- ret = lsra_test_from_stack(ls, rd, src, values); /* stack->index */
- ret = lsra_test_from_stack(ls, rd, src->prev, values); /* stack->arrayref */
- ret = lsra_test_new_stack(ls, rd, dst, values); /* arrayref[index]->stack */
- 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:
-
- ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
- ret = lsra_test_from_stack(ls, rd, src->prev, values); /* stack -> index */
- ret = lsra_test_from_stack(ls, rd, src->prev->prev, values); /* stack -> arrayref */
- break;
-
- case ICMD_POP: /* throw away a stackslot -> check if used anyway! */
- ret = lsra_test_pop_from_stack(ls, rd,src, values);
- 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) {
- ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
- ret = lsra_test_local(ls, rd,iptr->op1,opcode-ICMD_ISTORE, LSRA_STORE, values); /* local->value */
- } else if (src->varnum != iptr->op1) {
- ret = lsra_test_local(ls, rd,iptr->op1,opcode-ICMD_ISTORE, LSRA_STORE, values); /* local->value */
- ret = lsra_test_local(ls, rd,src->varnum,opcode-ICMD_ISTORE, LSRA_LOAD, values); /* local->value */
- }
- 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 */
- end_of_method = true;
- ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
- break;
- case ICMD_PUTSTATIC: /* stack(value) -> static_field */
- case ICMD_PUTFIELDCONST:
- /* pop 1 push 0 branch */
- case ICMD_MONITORENTER:
- case ICMD_MONITOREXIT:
- ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
- break;
-
- 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:
- ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
- break;
-
- /* pop 1 push 0 table branch */
-
- case ICMD_TABLESWITCH:
- ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
- break;
- case ICMD_LOOKUPSWITCH:
- ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value */
- break;
-
- /* pop 2 push 0 */
-
- case ICMD_POP2: /* throw away 2 stackslots -> check if used anyway! */
- ret = lsra_test_pop_from_stack(ls, rd,src, values);
- ret = lsra_test_pop_from_stack(ls, rd,src->prev, values);
- 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:
- ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value*/
- ret = lsra_test_from_stack(ls, rd, src->prev, values); /* stack -> objref*/
- break;
-
- /* pop 2 push 0 */
-
- case ICMD_PUTFIELD: /* stack(objref,value) -> objref->method=value */
-
- case ICMD_IASTORECONST:
- case ICMD_LASTORECONST:
- case ICMD_AASTORECONST:
- case ICMD_BASTORECONST:
- case ICMD_CASTORECONST:
- case ICMD_SASTORECONST:
- ret = lsra_test_from_stack(ls, rd, src, values); /* stack -> value*/
- ret = lsra_test_from_stack(ls, rd, src->prev, values); /* stack -> objref*/
- break;
-
- /* pop 0 push 1 dup */
- /* merge dupped vars??? */
- case ICMD_DUP: /* src == dst->prev, src -> dst */
- /* ret = lsra_test_from_stack(ls, rd, src,b_index,iindex);*/ /* just inc usage count? */
- ret = lsra_test_new_stack(ls, rd,dst, values);
- break;
-
- /* pop 0 push 2 dup */
-
- case ICMD_DUP2:
- /* ret = lsra_test_from_stack(ls, rd, src,b_index,iindex); */ /* just inc usage count? */
- /* ret = lsra_test_from_stack(ls, rd, src->prev,b_index,iindex); */ /* just inc usage count? */
- ret = lsra_test_new_stack(ls, rd,dst->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst, values);
- break;
-
- /* pop 2 push 3 dup */
-
- case ICMD_DUP_X1:
- ret = lsra_test_from_stack(ls, rd, src, values);
- ret = lsra_test_from_stack(ls, rd, src->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst->prev->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst, values);
- break;
-
- /* pop 3 push 4 dup */
-
- case ICMD_DUP_X2:
- ret = lsra_test_from_stack(ls, rd, src, values);
- ret = lsra_test_from_stack(ls, rd, src->prev, values);
- ret = lsra_test_from_stack(ls, rd, src->prev->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst->prev->prev->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst->prev->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst, values);
- break;
-
- /* pop 3 push 5 dup */
-
- case ICMD_DUP2_X1:
- ret = lsra_test_from_stack(ls, rd, src, values);
- ret = lsra_test_from_stack(ls, rd, src->prev, values);
- ret = lsra_test_from_stack(ls, rd, src->prev->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst->prev->prev->prev->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst->prev->prev->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst->prev->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst, values);
- break;
-
- /* pop 4 push 6 dup */
-
- case ICMD_DUP2_X2:
- ret = lsra_test_from_stack(ls, rd, src, values);
- ret = lsra_test_from_stack(ls, rd, src->prev, values);
- ret = lsra_test_from_stack(ls, rd, src->prev->prev, values);
- ret = lsra_test_from_stack(ls, rd, src->prev->prev->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst->prev->prev->prev->prev->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst->prev->prev->prev->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst->prev->prev->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst->prev->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst, values);
-
- break;
-
- /* pop 2 push 2 swap */
-
- case ICMD_SWAP:
- ret = lsra_test_from_stack(ls, rd, src, values);
- ret = lsra_test_from_stack(ls, rd, src->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst, values);
-
- break;
-
- /* pop 2 push 1 */
-
- case ICMD_IADD:
- case ICMD_ISUB:
- case ICMD_IMUL:
- case ICMD_IDIV:
- case ICMD_IREM:
-
- case ICMD_ISHL:
- case ICMD_ISHR:
- case ICMD_IUSHR:
- case ICMD_IAND:
- case ICMD_IOR:
- case ICMD_IXOR:
-
- case ICMD_LADD:
- case ICMD_LSUB:
- case ICMD_LMUL:
- case ICMD_LDIV:
- case ICMD_LREM:
-
- case ICMD_LOR:
- case ICMD_LAND:
- case ICMD_LXOR:
-
- case ICMD_LSHL:
- case ICMD_LSHR:
- case ICMD_LUSHR:
-
- case ICMD_FADD:
- case ICMD_FSUB:
- case ICMD_FMUL:
- case ICMD_FDIV:
- case ICMD_FREM:
-
- case ICMD_DADD:
- case ICMD_DSUB:
- case ICMD_DMUL:
- case ICMD_DDIV:
- case ICMD_DREM:
-
- case ICMD_LCMP:
- case ICMD_FCMPL:
- case ICMD_FCMPG:
- case ICMD_DCMPL:
- case ICMD_DCMPG:
- ret = lsra_test_from_stack(ls, rd, src, values);
- ret = lsra_test_from_stack(ls, rd, src->prev, values);
- ret = lsra_test_new_stack(ls, rd,dst, values);
- break;
-
- /* pop 1 push 1 */
- 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_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_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_ARRAYCHECKCAST:
-
- case ICMD_ARRAYLENGTH:
- case ICMD_INSTANCEOF:
-
- case ICMD_NEWARRAY:
- case ICMD_ANEWARRAY:
-
- case ICMD_GETFIELD:
- ret = lsra_test_from_stack(ls, rd, src, values);
- ret = lsra_test_new_stack(ls, rd,dst, values);
- break;
-
- /* pop 0 push 1 */
-
- case ICMD_GETSTATIC:
- case ICMD_NEW:
- ret = lsra_test_new_stack(ls, rd,dst, values);
- break;
-
- /* pop many push any */
- case ICMD_INVOKEVIRTUAL:
- case ICMD_INVOKESPECIAL:
- case ICMD_INVOKESTATIC:
- case ICMD_INVOKEINTERFACE:
- INSTRUCTION_GET_METHODDESC(iptr,md);
- i = md->paramcount;
- while (--i >= 0) {
- ret = lsra_test_from_stack(ls, rd, src, values);
- src = src->prev;
- }
- if (md->returntype.type != TYPE_VOID)
- ret = lsra_test_new_stack(ls, rd,dst, values);
- break;
-
- case ICMD_BUILTIN:
- i = iptr->op1;
- while (--i >= 0) {
- ret = lsra_test_from_stack(ls, rd, src, values);
- src = src->prev;
- }
- if (((builtintable_entry *) iptr->val.a)->md->returntype.type != TYPE_VOID)
- ret = lsra_test_new_stack(ls, rd,dst, values);
- break;
-
- case ICMD_MULTIANEWARRAY:
- i = iptr->op1;
- while (--i >= 0) {
- ret = lsra_test_from_stack(ls, rd, src, values);
- src = src->prev;
- }
- ret = lsra_test_new_stack(ls, rd, dst, values);
- break;
-
- default:
- printf("ICMD %d at %d\n", iptr->opc, (int)(iptr - m->instructions));
- { log_text("Missing ICMD code during register allocation"); assert(0); }
- } /* switch */
- }
-
- if (ret != -1) {
- printf("BB: %i IIndex %i \n", b_index, iindex);
- } else {
-
- i=0;
-
- for (succ = ls->succ[b_index]; succ != NULL; succ = succ->next)
- i++;
-
- if (end_of_method) {
- /* XRETURN or ATHROW encountered */
- /* take a 50% chance to end testing */
- /* otherwise follow successor (possible exception handler) */
- if (rand() % 2) i = 0;
- }
-
- if (i != 0) {
- j = rand() % i;
-
- for (i=0, succ = ls->succ[b_index]; i!=j; i++, succ=succ->next);
-
- if ( (ret=_test_lifetimes(m, ls, rd, succ->value, values, rec_depth + 1)) != -1) {
- printf("[BB %3i IIndex %3i]",b_index, iindex);
- }
- }
- }
- return ret;
-}
-
-void test_lifetimes( methodinfo *m, lsradata *ls, registerdata *rd)
-{
- int *values, i, j, p, t;
- int v_max,ret;
- methoddesc *md = m->parseddesc;
-
- v_max = rd->memuse + INT_REG_CNT + FLT_REG_CNT;
-
- if ( (values = MNEW(int, v_max)) == NULL )
- { log_text("test_lifetimes: out of memory\n"); assert(0); }
-
- ret = -1;
- for (j=0; (j < 100) && (ret == -1); j++ ) {
- for (i=0; i < v_max; i++) values[i]=VS;
-
- for (p = 0, i = 0; p < md->paramcount; p++) {
- t = md->paramtypes[p].type;
-
- if (rd->locals[i][t].type >= 0)
- lsra_test_local( ls, rd, i, t, LSRA_STORE, values);
-
- i++;
- if (IS_2_WORD_TYPE(t)) /* increment local counter for 2 word types */
- i++;
- } /* end for */
-
- if ((ret=_test_lifetimes(m, ls, rd, 0, values, 0)) != -1) {
- printf("\n");
- }
- }
-
-
- MFREE(values, int, v_max);
-}
-#endif
/*
* These are local overrides for various environment variables in Emacs.
Christian Ullrich
Edwin Steiner
- $Id: codegen.c 5228 2006-08-09 15:11:29Z twisti $
+ $Id: codegen.c 5234 2006-08-14 17:50:12Z christian $
*/
#include "vm/jit/reg.h"
#include "vm/jit/replace.h"
-#if defined(ENABLE_LSRA)
-# ifdef LSRA_USES_REG_RES
-# include "vm/jit/i386/icmd_uses_reg_res.inc"
-# endif
+#if defined(ENABLE_LSRA) && !defined(ENABLE_SSA)
# include "vm/jit/allocator/lsra.h"
#endif
+#if defined(ENABLE_SSA)
+# include "vm/jit/optimizing/lsra.h"
+# include "vm/jit/optimizing/ssa.h"
+#endif
/* codegen *********************************************************************
*******************************************************************************/
+#if defined(ENABLE_SSA)
+void cg_move(codegendata *cd, s4 type, s4 src_regoff, s4 src_flags,
+ s4 dst_regoff, s4 dst_flags);
+void codegen_insert_phi_moves(codegendata *cd, registerdata *rd, lsradata *ls,
+ basicblock *bptr);
+#endif
+
bool codegen(jitdata *jd)
{
methodinfo *m;
builtintable_entry *bte;
methoddesc *md;
rplpoint *replacementpoint;
+#if defined(ENABLE_SSA)
+ lsradata *ls;
+ bool last_cmd_was_goto;
+
+ last_cmd_was_goto = false;
+ ls = jd->ls;
+#endif
/* get required compiler data */
stack_off = 0;
for (p = 0, l = 0; p < md->paramcount; p++) {
t = md->paramtypes[p].type;
+#if defined(ENABLE_SSA)
+ if ( ls != NULL ) {
+ l = ls->local_0[p];
+ }
+#endif
var = &(rd->locals[l][t]);
l++;
if (IS_2_WORD_TYPE(t)) /* increment local counter for 2 word types */
if (var->type < 0)
continue;
s1 = md->params[p].regoff;
+
if (IS_INT_LNG_TYPE(t)) { /* integer args */
if (!md->params[p].inmemory) { /* register arguments */
log_text("integer register argument");
assert(0);
if (!(var->flags & INMEMORY)) { /* reg arg -> register */
/* rd->argintregs[md->params[p].regoff -> var->regoff */
- } else { /* reg arg -> spilled */
+ }
+ else { /* reg arg -> spilled */
/* rd->argintregs[md->params[p].regoff -> var->regoff * 4 */
}
- } else { /* stack arguments */
+ }
+ else { /* stack arguments */
if (!(var->flags & INMEMORY)) { /* stack arg -> register */
emit_mov_membase_reg( /* + 4 for return address */
cd, REG_SP, (stackframesize + s1) * 4 + 4, var->regoff);
/* + 4 for return address */
- } else { /* stack arg -> spilled */
+ }
+ else { /* stack arg -> spilled */
if (!IS_2_WORD_TYPE(t)) {
-#if 0
- emit_mov_membase_reg( /* + 4 for return address */
- cd, REG_SP, (stackframesize + s1) * 4 + 4,
- REG_ITMP1);
- emit_mov_reg_membase(
- cd, REG_ITMP1, REG_SP, var->regoff * 4);
-#else
+#if defined(ENABLE_SSA)
+ /* no copy avoiding by now possible with SSA */
+ if (ls != NULL) {
+ emit_mov_membase_reg( /* + 4 for return address */
+ cd, REG_SP, (stackframesize + s1) * 4 + 4,
+ REG_ITMP1);
+ emit_mov_reg_membase(
+ cd, REG_ITMP1, REG_SP, var->regoff * 4);
+ }
+ else
+#endif /*defined(ENABLE_SSA)*/
/* reuse Stackslotand avoid copying */
- var->regoff = stackframesize + s1 + 1;
-#endif
+ var->regoff = stackframesize + s1 + 1;
- } else {
-#if 0
- emit_mov_membase_reg( /* + 4 for return address */
- cd, REG_SP, (stackframesize + s1) * 4 + 4,
- REG_ITMP1);
- emit_mov_reg_membase(
- cd, REG_ITMP1, REG_SP, var->regoff * 4);
- emit_mov_membase_reg( /* + 4 for return address */
- cd, REG_SP, (stackframesize + s1) * 4 + 4 + 4,
- REG_ITMP1);
- emit_mov_reg_membase(
- cd, REG_ITMP1, REG_SP, var->regoff * 4 + 4);
-#else
+ }
+ else {
+#if defined(ENABLE_SSA)
+ /* no copy avoiding by now possible with SSA */
+ if (ls != NULL) {
+ emit_mov_membase_reg( /* + 4 for return address */
+ cd, REG_SP, (stackframesize + s1) * 4 + 4,
+ REG_ITMP1);
+ emit_mov_reg_membase(
+ cd, REG_ITMP1, REG_SP, var->regoff * 4);
+ emit_mov_membase_reg( /* + 4 for return address */
+ cd, REG_SP, (stackframesize + s1) * 4 + 4 + 4,
+ REG_ITMP1);
+ emit_mov_reg_membase(
+ cd, REG_ITMP1, REG_SP, var->regoff * 4 + 4);
+ }
+ else
+#endif /*defined(ENABLE_SSA)*/
/* reuse Stackslotand avoid copying */
- var->regoff = stackframesize + s1 + 1;
-#endif
+ var->regoff = stackframesize + s1 + 1;
}
}
}
-
- } else { /* floating args */
+ }
+ else { /* floating args */
if (!md->params[p].inmemory) { /* register arguments */
log_text("There are no float argument registers!");
assert(0);
/* rd->argfltregs[md->params[p].regoff -> var->regoff * 4 */
}
- } else { /* stack arguments */
+ }
+ else { /* stack arguments */
if (!(var->flags & INMEMORY)) { /* stack-arg -> register */
if (t == TYPE_FLT) {
emit_flds_membase(
assert(0);
/* emit_fstp_reg(cd, var->regoff + fpu_st_offset); */
- } else {
+ }
+ else {
emit_fldl_membase(
cd, REG_SP, (stackframesize + s1) * 4 + 4);
assert(0);
}
} else { /* stack-arg -> spilled */
-#if 0
- emit_mov_membase_reg(
- cd, REG_SP, (stackframesize + s1) * 4 + 4, REG_ITMP1);
- emit_mov_reg_membase(
- cd, REG_ITMP1, REG_SP, var->regoff * 4);
- if (t == TYPE_FLT) {
- emit_flds_membase(
- cd, REG_SP, (stackframesize + s1) * 4 + 4);
- emit_fstps_membase(cd, REG_SP, var->regoff * 4);
- } else {
- emit_fldl_membase(
- cd, REG_SP, (stackframesize + s1) * 4 + 4);
- emit_fstpl_membase(cd, REG_SP, var->regoff * 4);
+#if defined(ENABLE_SSA)
+ /* no copy avoiding by now possible with SSA */
+ if (ls != NULL) {
+ emit_mov_membase_reg(
+ cd, REG_SP, (stackframesize + s1) * 4 + 4, REG_ITMP1);
+ emit_mov_reg_membase(
+ cd, REG_ITMP1, REG_SP, var->regoff * 4);
+ if (t == TYPE_FLT) {
+ emit_flds_membase(
+ cd, REG_SP, (stackframesize + s1) * 4 + 4);
+ emit_fstps_membase(cd, REG_SP, var->regoff * 4);
+ }
+ else {
+ emit_fldl_membase(
+ cd, REG_SP, (stackframesize + s1) * 4 + 4);
+ emit_fstpl_membase(cd, REG_SP, var->regoff * 4);
+ }
}
-#else
+ else
+#endif /*defined(ENABLE_SSA)*/
/* reuse Stackslotand avoid copying */
var->regoff = stackframesize + s1 + 1;
-#endif
}
}
}
}
#endif /* !defined(NDEBUG) */
- }
+ }
+
+#if defined(ENABLE_SSA)
+ /* with SSA Header is Basic Block 0 - insert phi Moves if necessary */
+ if ( ls != NULL)
+ codegen_insert_phi_moves(cd, rd, ls, ls->basicblocks[0]);
+#endif
/* end of header generation */
}
#endif
-#if defined(ENABLE_LSRA)
+#if defined(ENABLE_LSRA) || defined(ENABLE_SSA)
+# if defined(ENABLE_LSRA) && !defined(ENABLE_SSA)
if (opt_lsra) {
- while (src != NULL) {
+# endif
+# if defined(ENABLE_SSA)
+ if (ls != NULL) {
+ last_cmd_was_goto = false;
+# endif
+ if (src != NULL) {
len--;
- if ((len == 0) && (bptr->type != BBTYPE_STD)) {
+ if (bptr->type != BBTYPE_STD) {
if (!IS_2_WORD_TYPE(src->type)) {
if (bptr->type == BBTYPE_SBR) {
- /* d = reg_of_var(m, src, REG_ITMP1); */
if (!(src->flags & INMEMORY))
d = src->regoff;
else
d = REG_ITMP1;
-
emit_pop_reg(cd, d);
emit_store(jd, NULL, src, d);
-
} else if (bptr->type == BBTYPE_EXH) {
- /* d = reg_of_var(m, src, REG_ITMP1); */
if (!(src->flags & INMEMORY))
d = src->regoff;
else
src = src->prev;
}
- } else {
-#endif
+ } else
+#endif /* defined(ENABLE_LSRA) || defined(ENABLE_SSA) */
+ {
while (src != NULL) {
len--;
if ((len == bptr->indepth-1) && (bptr->type != BBTYPE_STD)) {
d = codegen_reg_of_var(rd, 0, src, REG_ITMP1);
emit_pop_reg(cd, d);
emit_store(jd, NULL, src, d);
+
} else if (bptr->type == BBTYPE_EXH) {
d = codegen_reg_of_var(rd, 0, src, REG_ITMP1);
M_INTMOVE(REG_ITMP1, d);
emit_store(jd, NULL, src, d);
}
-
} else {
log_text("copy interface registers: longs have to be in memory (begin 1)");
assert(0);
}
src = src->prev;
}
-#if defined(ENABLE_LSRA)
}
-#endif
/* walk through all instructions */
M_COPY(src, iptr->dst);
M_COPY(src->prev, iptr->dst->prev);
- M_COPY(iptr->dst, iptr->dst->prev->prev);
+#if defined(ENABLE_SSA)
+ if ((ls==NULL) || (iptr->dst->varkind != TEMPVAR) ||
+ (ls->lifetime[-iptr->dst->varnum-1].type != -1)) {
+#endif
+ M_COPY(iptr->dst, iptr->dst->prev->prev);
+#if defined(ENABLE_SSA)
+ } else {
+ M_COPY(src, iptr->dst->prev->prev);
+ }
+#endif
break;
case ICMD_DUP_X2: /* ..., a, b, c ==> ..., c, a, b, c */
M_COPY(src, iptr->dst);
M_COPY(src->prev, iptr->dst->prev);
M_COPY(src->prev->prev, iptr->dst->prev->prev);
- M_COPY(iptr->dst, iptr->dst->prev->prev->prev);
+#if defined(ENABLE_SSA)
+ if ((ls==NULL) || (iptr->dst->varkind != TEMPVAR) ||
+ (ls->lifetime[-iptr->dst->varnum-1].type != -1)) {
+#endif
+ M_COPY(iptr->dst, iptr->dst->prev->prev->prev);
+#if defined(ENABLE_SSA)
+ } else {
+ M_COPY(src, iptr->dst->prev->prev->prev);
+ }
+#endif
break;
case ICMD_DUP2_X1: /* ..., a, b, c ==> ..., b, c, a, b, c */
case ICMD_IINC: /* ..., value ==> ..., value + constant */
/* op1 = variable, val.i = constant */
- var = &(rd->locals[iptr->op1][TYPE_INT]);
- if (var->flags & INMEMORY) {
- s1 = REG_ITMP1;
- M_ILD(s1, REG_SP, var->regoff * 4);
- }
- else
- s1 = var->regoff;
+#if defined(ENABLE_SSA)
+ if ( ls != NULL ) {
+ varinfo *var_t;
+ /* with SSA in op1 is the source Local Var, in val._i.op1_t */
+ /* the target Local Var, in val._i.i the constant */
+ /* val._i.op1_t <- op1 + val._i.i */
- /* `inc reg' is slower on p4's (regarding to ia32
- optimization reference manual and benchmarks) and as
- fast on athlon's. */
+
+ var = &(rd->locals[iptr->op1][TYPE_INT]);
+ var_t = &(rd->locals[iptr->val._i.op1_t][TYPE_INT]);
- M_IADD_IMM(iptr->val.i, s1);
+ if (var->flags & INMEMORY) {
+ if (!(var_t->flags & INMEMORY))
+ s1 = var_t->regoff;
+ else
+ s1 = REG_ITMP1;
+ M_ILD(s1, REG_SP, var->regoff * 4);
+ }
+ else
+ s1 = var->regoff;
- if (var->flags & INMEMORY)
- M_IST(s1, REG_SP, var->regoff * 4);
+ /* `inc reg' is slower on p4's (regarding to ia32
+ optimization reference manual and benchmarks) and as
+ fast on athlon's. */
+
+ M_IADD_IMM(iptr->val._i.i, s1);
+
+ if (var_t->flags && INMEMORY)
+ M_IST(s1, REG_SP, var_t->regoff * 4);
+ else if (!(var_t->flags && INMEMORY))
+ M_INTMOVE(s1, var_t->regoff);
+
+ } else
+#endif /* defined(ENABLE_SSA) */
+ {
+ var = &(rd->locals[iptr->op1][TYPE_INT]);
+ if (var->flags & INMEMORY) {
+ s1 = REG_ITMP1;
+ M_ILD(s1, REG_SP, var->regoff * 4);
+ }
+ else
+ s1 = var->regoff;
+
+ /* `inc reg' is slower on p4's (regarding to ia32
+ optimization reference manual and benchmarks) and as
+ fast on athlon's. */
+
+ M_IADD_IMM(iptr->val.i, s1);
+
+ if (var->flags & INMEMORY)
+ M_IST(s1, REG_SP, var->regoff * 4);
+ }
break;
case ICMD_GOTO: /* ... ==> ... */
/* op1 = target JavaVM pc */
+#if defined(ENABLE_SSA)
+ if ( ls != NULL ) {
+ last_cmd_was_goto = true;
+ /* In case of a Goto phimoves have to be inserted before the */
+ /* jump */
+ codegen_insert_phi_moves(cd, rd, ls, bptr);
+ }
+#endif
M_JMP_IMM(0);
codegen_addreference(cd, (basicblock *) iptr->target);
ALIGNCODENOP;
/* d contains return type */
if (d != TYPE_VOID) {
- if (IS_INT_LNG_TYPE(iptr->dst->type)) {
- if (IS_2_WORD_TYPE(iptr->dst->type)) {
- s1 = codegen_reg_of_var(rd, iptr->opc, iptr->dst, REG_RESULT_PACKED);
- M_LNGMOVE(REG_RESULT_PACKED, s1);
+#if defined(ENABLE_SSA)
+ if ((ls == NULL) || (iptr->dst->varkind != TEMPVAR) ||
+ (ls->lifetime[-iptr->dst->varnum-1].type != -1))
+ /* a "living" stackslot */
+#endif
+ {
+ if (IS_INT_LNG_TYPE(iptr->dst->type)) {
+ if (IS_2_WORD_TYPE(iptr->dst->type)) {
+ s1 = codegen_reg_of_var(rd, iptr->opc, iptr->dst, REG_RESULT_PACKED);
+ M_LNGMOVE(REG_RESULT_PACKED, s1);
+ }
+ else {
+ s1 = codegen_reg_of_var(rd, iptr->opc, iptr->dst, REG_RESULT);
+ M_INTMOVE(REG_RESULT, s1);
+ }
}
else {
- s1 = codegen_reg_of_var(rd, iptr->opc, iptr->dst, REG_RESULT);
- M_INTMOVE(REG_RESULT, s1);
+ s1 = codegen_reg_of_var(rd, iptr->opc, iptr->dst, REG_NULL);
}
+ emit_store(jd, iptr, iptr->dst, s1);
}
- else {
- s1 = codegen_reg_of_var(rd, iptr->opc, iptr->dst, REG_NULL);
- }
- emit_store(jd, iptr, iptr->dst, s1);
}
break;
src = bptr->outstack;
len = bptr->outdepth;
MCODECHECK(64+len);
-#if defined(ENABLE_LSRA)
+#if defined(ENABLE_LSRA) && !defined(ENABLE_SSA)
if (!opt_lsra)
+#endif
+#if defined(ENABLE_SSA)
+ if ( ls != NULL ) {
+ /* by edge splitting, in Blocks with phi moves there can only */
+ /* be a goto as last command, no other Jump/Branch Command */
+ if (!last_cmd_was_goto)
+ codegen_insert_phi_moves(cd, rd, ls, bptr);
+ } else
#endif
while (src) {
len--;
return true;
}
+#if defined(ENABLE_SSA)
+void codegen_insert_phi_moves(codegendata *cd, registerdata *rd, lsradata *ls, basicblock *bptr) {
+ /* look for phi moves */
+ int t_a,s_a,i, type;
+ int t_lt, s_lt; /* lifetime indices of phi_moves */
+ bool t_inmemory, s_inmemory;
+ s4 t_regoff, s_regoff, s_flags, t_flags;
+ MCODECHECK(512);
+
+ /* Moves from phi functions with highest indices have to be */
+ /* inserted first, since this is the order as is used for */
+ /* conflict resolution */
+ for(i = ls->num_phi_moves[bptr->nr] - 1; i >= 0 ; i--) {
+ t_a = ls->phi_moves[bptr->nr][i][0];
+ s_a = ls->phi_moves[bptr->nr][i][1];
+#if defined(SSA_DEBUG_VERBOSE)
+ if (compileverbose)
+ printf("BB %3i Move %3i <- %3i ",bptr->nr,t_a,s_a);
+#endif
+ if (t_a >= 0) {
+ /* local var lifetimes */
+ t_lt = ls->maxlifetimes + t_a;
+ type = ls->lifetime[t_lt].type;
+ } else {
+ t_lt = -t_a-1;
+ type = ls->lifetime[t_lt].local_ss->s->type;
+ /* stackslot lifetime */
+ }
+ if (type == -1) {
+#if defined(SSA_DEBUG_VERBOSE)
+ if (compileverbose)
+ printf("...returning - phi lifetimes where joined\n");
+#endif
+ return;
+ }
+ if (s_a >= 0) {
+ /* local var lifetimes */
+ s_lt = ls->maxlifetimes + s_a;
+ type = ls->lifetime[s_lt].type;
+ } else {
+ s_lt = -s_a-1;
+ type = ls->lifetime[s_lt].type;
+ /* stackslot lifetime */
+ }
+ if (type == -1) {
+#if defined(SSA_DEBUG_VERBOSE)
+ if (compileverbose)
+ printf("...returning - phi lifetimes where joined\n");
+#endif
+ return;
+ }
+ if (t_a >= 0) {
+
+ t_inmemory = rd->locals[t_a][type].flags & INMEMORY;
+ t_flags = rd->locals[t_a][type].flags;
+ t_regoff = rd->locals[t_a][type].regoff;
+
+ } else {
+ t_inmemory = ls->lifetime[t_lt].local_ss->s->flags & INMEMORY;
+ t_flags = ls->lifetime[t_lt].local_ss->s->flags;
+ t_regoff = ls->lifetime[t_lt].local_ss->s->regoff;
+ }
+
+ if (s_a >= 0) {
+ /* local var move */
+
+ s_inmemory = rd->locals[s_a][type].flags & INMEMORY;
+ s_flags = rd->locals[s_a][type].flags;
+ s_regoff = rd->locals[s_a][type].regoff;
+ } else {
+ /* stackslot lifetime */
+ s_inmemory = ls->lifetime[s_lt].local_ss->s->flags & INMEMORY;
+ s_flags = ls->lifetime[s_lt].local_ss->s->flags;
+ s_regoff = ls->lifetime[s_lt].local_ss->s->regoff;
+ }
+ if (type == -1) {
+#if defined(SSA_DEBUG_VERBOSE)
+ if (compileverbose)
+ printf("...returning - phi lifetimes where joined\n");
+#endif
+ return;
+ }
+
+ cg_move(cd, type, s_regoff, s_flags, t_regoff, t_flags);
+
+#if defined(SSA_DEBUG_VERBOSE)
+ if (compileverbose) {
+ if ((t_inmemory) && (s_inmemory)) {
+ /* mem -> mem */
+ printf("M%3i <- M%3i",t_regoff,s_regoff);
+ } else if (s_inmemory) {
+ /* mem -> reg */
+ printf("R%3i <- M%3i",t_regoff,s_regoff);
+ } else if (t_inmemory) {
+ /* reg -> mem */
+ printf("M%3i <- R%3i",t_regoff,s_regoff);
+ } else {
+ /* reg -> reg */
+ printf("R%3i <- R%3i",t_regoff,s_regoff);
+ }
+ printf("\n");
+ }
+#endif /* defined(SSA_DEBUG_VERBOSE) */
+ }
+}
+
+void cg_move(codegendata *cd, s4 type, s4 src_regoff, s4 src_flags,
+ s4 dst_regoff, s4 dst_flags) {
+ if ((dst_flags & INMEMORY) && (src_flags & INMEMORY)) {
+ /* mem -> mem */
+ if (dst_regoff != src_regoff) {
+ if (!IS_2_WORD_TYPE(type)) {
+ if (IS_FLT_DBL_TYPE(type)) {
+ emit_flds_membase(cd, REG_SP, src_regoff * 4);
+ emit_fstps_membase(cd, REG_SP, dst_regoff * 4);
+ } else{
+ emit_mov_membase_reg(cd, REG_SP, src_regoff * 4,
+ REG_ITMP1);
+ emit_mov_reg_membase(cd, REG_ITMP1, REG_SP, dst_regoff * 4);
+ }
+ } else { /* LONG OR DOUBLE */
+ if (IS_FLT_DBL_TYPE(type)) {
+ emit_fldl_membase( cd, REG_SP, src_regoff * 4);
+ emit_fstpl_membase(cd, REG_SP, dst_regoff * 4);
+ } else {
+ emit_mov_membase_reg(cd, REG_SP, src_regoff * 4,
+ REG_ITMP1);
+ emit_mov_reg_membase(cd, REG_ITMP1, REG_SP, dst_regoff * 4);
+ emit_mov_membase_reg(cd, REG_SP, src_regoff * 4 + 4,
+ REG_ITMP1);
+ emit_mov_reg_membase(cd, REG_ITMP1, REG_SP,
+ dst_regoff * 4 + 4);
+ }
+ }
+ }
+ } else {
+ if (IS_FLT_DBL_TYPE(type)) {
+ log_text("cg_move: flt/dbl type have to be in memory\n");
+/* assert(0); */
+ }
+ if (IS_2_WORD_TYPE(type)) {
+ log_text("cg_move: longs have to be in memory\n");
+/* assert(0); */
+ }
+ if (src_flags & INMEMORY) {
+ /* mem -> reg */
+ emit_mov_membase_reg(cd, REG_SP, src_regoff * 4, dst_regoff);
+ } else if (dst_flags & INMEMORY) {
+ /* reg -> mem */
+ emit_mov_reg_membase(cd, src_regoff, REG_SP, dst_regoff * 4);
+ } else {
+ /* reg -> reg */
+ /* only ints can be in regs on i386 */
+ M_INTMOVE(src_regoff,dst_regoff);
+ }
+ }
+}
+#endif /* defined(ENABLE_SSA) */
/* createcompilerstub **********************************************************
projects / cacao.git / commitdiff