-/* src/vm/jit/allocator/lsra.inc - linear scan register allocator
+/* src/vm/jit/allocator/lsra.c - linear scan register allocator
- Copyright (C) 1996-2005 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
+ Copyright (C) 2005, 2006, 2007 R. Grafl, A. Krall, C. Kruegel,
+ C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
+ E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
+ J. Wenninger, Institut f. Computersprachen - TU Wien
This file is part of CACAO.
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., 59 Temple Place - Suite 330, Boston, MA
- 02111-1307, USA.
+ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA.
- Contact: cacao@complang.tuwien.ac.at
+ Contact: cacao@cacaojvm.org
Authors: Christian Ullrich
-
- Changes: Christian Thalinger
-
- $Id: lsra.c 4055 2006-01-02 12:59:54Z christian $
+ Christian Thalinger
+ Edwin Steiner
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
+#include <limits.h>
#include "arch.h"
#include "md-abi.h"
#include "vm/options.h"
#include "vm/statistics.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"
-#include "md-abi.inc"
+#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 *, t_inlining_globals *, 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 );
-#endif
-#ifdef LSRA_PRINTLIFETIMES
-void print_lifetimes(registerdata *, lsradata *, int *, int);
-#endif
-#ifdef LSRA_TESTLT
-void test_lifetimes( methodinfo *, lsradata *, registerdata *);
+void print_lifetimes(jitdata *, int *, int);
#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);
-void lsra(methodinfo *m, codegendata *cd, registerdata *rd,
- t_inlining_globals *id)
+bool lsra(jitdata *jd)
{
-
- 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(name, m->class->name);
- utf_sprint(name1, m->name);
- strcat(name, ".");
- strcat(name, name1);
- utf_sprint(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
-
- ls=DNEW(lsradata);
- lsra_init(m, cd, id, 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 */
+
+ return true;
}
/* 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->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->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, t_inlining_globals *id,
- 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 + jd->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]);
- }
- }
-
- /* 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;
-
- 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 */
-
- lsra_calc_lifetime_length(m, ls, cd);
-
-#ifdef LSRA_PRINTLIFETIMES
- printf("Basicblockcount: %4i\n",m->basicblockcount);
-/* print_lifetimes(rd, ls, ls->lt_used, ls->lifetimecount); */
-#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;
+ liveness_setup(jd);
+#if defined(LV)
+ liveness(jd);
+#else /* LV */
+ {
+ int p, t;
+ methoddesc *md = m->parseddesc;
- 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);
+ /* 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]);
}
-#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)) {
-#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
+ /* 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 */
-
- lt->flags |= JOINING;
+ for (p = 0, i = 0; p < md->paramcount; p++) {
+ t = md->paramtypes[p].type;
- /* take Lifetime lto out of ls->lifetimes */
- lto->type = -1;
+ 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 */
- /* merge lto into lt of in */
+ lsra_calc_lifetime_length(jd);
- 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");
+#ifdef LSRA_DEBUG_VERBOSE
+ if (compileverbose)
+ printf("Basicblockcount: %4i\n",m->basicblockcount);
#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,
+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;
+
+ m = jd->m;
+ rd = jd->rd;
+ md = m->parseddesc;
int_reg->nregdesc = nregdescint;
flt_reg->nregdesc = nregdescfloat;
- if (m->isleafmethod) {
+ if (jd->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);
flt_reg->tmp_reg = NULL;
flt_reg->tmp_top = -1;
-
/* additionaly precolour registers for Local Variables acting as */
/* Parameters */
/* 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");
-#endif
+ 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);
-
-#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);
+ 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);
- 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:
case ICMD_INVOKESPECIAL:
case ICMD_INVOKEVIRTUAL:
case ICMD_INVOKEINTERFACE:
- lm = iptr->val.a;
-
- if (lm)
- md = lm->parseddesc;
- else {
- unresolved_method *um = iptr->target;
- md = um->methodref->parseddesc.md;
- }
+ INSTRUCTION_GET_METHODDESC(iptr,md);
i = md->paramcount;
while (--i >= 0) {
lsra_from_stack(ls, src, b_index, iindex);
break;
default:
- throw_cacao_exception_exit(string_java_lang_InternalError,
- "Unknown ICMD %d during register allocation", iptr->opc);
+ exceptions_throw_internalerror("Unknown ICMD %d during register allocation",
+ 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
-
- }
-}
-
-#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;
}
+#endif /* defined(LV) */
-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;
-
- 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:
-#error XXX FIXME TWISTI: use md->paramcount (2005/10/4)
- i = iptr->op1;
- while (--i >= 0) {
- ret = lsra_test_from_stack(ls, rd, src, values);
- src = src->prev;
- }
- if (((unresolved_method *) iptr->target)->methodref->parseddesc.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.
* c-basic-offset: 4
* tab-width: 4
* End:
+ * vim:noexpandtab:sw=4:ts=4:
*/
projects / cacao.git / blobdiff