Authors: Andreas Krall
Reinhard Grafl
- $Id: codegen.c 1507 2004-11-14 17:02:15Z jowenn $
+ $Id: codegen.c 1590 2004-11-25 13:24:49Z christian $
*/
#include "jit/jit.h"
#include "jit/parse.h"
#include "jit/reg.h"
+#include "jit/lsra.h"
#include "builtin.h"
#include "asmpart.h"
#include "jni.h"
#include "jit/codegen.inc"
#include "jit/reg.inc"
+#include "jit/lsra.inc"
/* NullPointerException handlers and exception handling initialisation */
src = bptr->instack;
len = bptr->indepth;
MCODECHECK(64+len);
+ if (opt_lsra) {
while (src != NULL) {
len--;
if ((len == 0) && (bptr->type != BBTYPE_STD)) {
+ /* d = reg_of_var(m, src, REG_ITMP1); */
+ if (!(src->flags & INMEMORY))
+ d= src->regoff;
+ else
+ d=REG_ITMP1;
+ M_INTMOVE(REG_ITMP1, d);
+ store_reg_to_var_int(src, d);
+ }
+ src = src->prev;
+ }
+ } else {
+ while (src != NULL) {
+ len--;
+ if ((len == 0) && (bptr->type != BBTYPE_STD)) {
d = reg_of_var(rd, src, REG_ITMP1);
M_INTMOVE(REG_ITMP1, d);
store_reg_to_var_int(src, d);
}
src = src->prev;
}
+ }
/* walk through all instructions */
src = bptr->outstack;
len = bptr->outdepth;
MCODECHECK(64+len);
+ if (!opt_lsra)
while (src) {
len--;
if ((src->varkind != STACKVAR)) {
Authors: Andreas Krall
Christian Thalinger
- $Id: codegen.c 1577 2004-11-24 13:06:56Z twisti $
+ $Id: codegen.c 1590 2004-11-25 13:24:49Z christian $
*/
#include "jit/i386/codegen.h"
#include "jit/i386/emitfuncs.h"
-
/* register descripton - array ************************************************/
/* #define REG_RES 0 reserved register for OS or code generator */
#include "jit/codegen.inc"
#include "jit/reg.inc"
-
+#include "jit/lsra.inc"
void codegen_stubcalled() {
log_text("Stub has been called");
parentargs_base = rd->maxmemuse + savedregs_num;
+
#if defined(USE_THREADS) /* space to save argument of monitor_enter */
if (checksync && (m->flags & ACC_SYNCHRONIZED))
src = bptr->instack;
len = bptr->indepth;
MCODECHECK(64+len);
+
+ if (opt_lsra) {
while (src != NULL) {
len--;
if ((len == 0) && (bptr->type != BBTYPE_STD)) {
if (!IS_2_WORD_TYPE(src->type)) {
if (bptr->type == BBTYPE_SBR) {
- d = reg_of_var(rd, src, REG_ITMP1);
+ /* d = reg_of_var(m, src, REG_ITMP1); */
+ if (!(src->flags & INMEMORY))
+ d= src->regoff;
+ else
+ d=REG_ITMP1;
i386_pop_reg(cd, d);
store_reg_to_var_int(src, d);
+ } else if (bptr->type == BBTYPE_EXH) {
+ /* d = reg_of_var(m, src, REG_ITMP1); */
+ if (!(src->flags & INMEMORY))
+ d= src->regoff;
+ else
+ d=REG_ITMP1;
+ M_INTMOVE(REG_ITMP1, d);
+ store_reg_to_var_int(src, d);
+ }
+ } else {
+ panic("copy interface registers(EXH, SBR): longs have to me in memory (begin 1)");
+ }
+ }
+ src = src->prev;
+ }
+ } else {
+ while (src != NULL) {
+ len--;
+ if ((len == 0) && (bptr->type != BBTYPE_STD)) {
+ if (!IS_2_WORD_TYPE(src->type)) {
+ if (bptr->type == BBTYPE_SBR) {
+ d = reg_of_var(rd, src, REG_ITMP1);
+ i386_pop_reg(cd, d);
+ store_reg_to_var_int(src, d);
} else if (bptr->type == BBTYPE_EXH) {
d = reg_of_var(rd, src, REG_ITMP1);
M_INTMOVE(REG_ITMP1, d);
}
src = src->prev;
}
+ }
/* walk through all instructions */
src = bptr->outstack;
len = bptr->outdepth;
MCODECHECK(64+len);
+ if (!opt_lsra)
while (src) {
len--;
if ((src->varkind != STACKVAR)) {
Changes: Edwin Steiner
- $Id: jit.c 1530 2004-11-17 20:43:28Z christian $
+ $Id: jit.c 1590 2004-11-25 13:24:49Z christian $
*/
#include "toolbox/memory.h"
#include "types.h"
#include <stdio.h>
+#include "jit/lsra.h"
/* global switches ************************************************************/
log_message_method("Allocating registers: ", m);
/* allocate registers */
- regalloc(m, cd, rd);
+ if (opt_lsra)
+ lsra(m, cd, rd, ld, id);
+ else
+ regalloc(m, cd, rd);
if (compileverbose) {
log_message_method("Allocating registers done: ", m);
--- /dev/null
+/* jit/lsra.inc - linear scan register allocator header
+
+ Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
+ Institut f. Computersprachen, TU Wien
+ R. Grafl, A. Krall, C. Kruegel, C. Oates, R. Obermaisser, M. Probst,
+ S. Ring, E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich,
+ J. Wenninger, C. Ullrich
+
+ 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., 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA.
+
+ Contact: cacao@complang.tuwien.ac.at
+
+ Authors: Christian Ullrich
+
+ $Id: lsra.h 1590 2004-11-25 13:24:49Z christian $
+
+*/
+
+
+#ifndef _LSRA_H
+#define _LSRA_H
+
+#include "loop/loop.h"
+
+#define LSRA_STORE 1
+#define LSRA_LOAD 0
+#define LSRA_POP -1
+
+struct lifetime {
+ int index; /* unique index, LOCALVAR varnum or negative*/
+ int b_start; /* bb of first use */
+ int b_end; /* bb of last use */
+ int i_start; /* instruction number of first use */
+ int i_end; /* instruction number of last use */
+ int length; /* lifetime in instructions */
+ stackptr s; /* stackslot or NULL */
+ int v_index; /* local variable index or -1 */
+ int type;
+ int usagecount; /* number of refernces*/
+ int reg; /* regoffset durch lsra zugewiesen */
+ int savedvar;
+ struct stackslot *passthrough; /* List of Stackslots in Lifetime, which are passed through a Basic Block */
+ struct stackslot *local_ss;
+ struct _i_list *i_list; /* list of instructions with references to var */
+ struct lifetime *next;
+};
+
+/* struct int_list { */
+/* int value; */
+/* int_list *next; */
+/* }; */
+
+struct active_lt {
+ struct lifetime *lt;
+ struct active_lt *next;
+};
+
+struct l_loop {
+ int b_first;
+ int b_last;
+ int nesting;
+};
+
+struct b_loop {
+ int loop;
+ int instr;
+};
+
+struct _i_list {
+ int b_index;
+ int instr;
+ int store;
+ struct _i_list *next;
+};
+
+struct stackslot {
+ stackptr s;
+ int bb;
+ struct stackslot *next;
+};
+
+struct lsra_reg {
+ int reg_index;
+ int use;
+};
+
+struct lsradata {
+ struct lifetime **ss_lifetimes;
+ struct lifetime **locals_lifetimes;
+ struct lifetime *lifetimes;
+ struct stackslot *stackslots;
+ struct active_lt *active_tmp, *active_sav;
+ int active_sav_count, active_tmp_count;
+ int var_index;
+ bool back_edge_panic;
+};
+
+struct freemem {
+ int off;
+ int end;
+ struct freemem *next;
+};
+
+struct sss {
+ int bb;
+ bool out;
+ struct sss *next;
+};
+
+typedef struct lsradata lsradata;
+
+/* function prototypes */
+void lsra(methodinfo *, codegendata *, registerdata *, loopdata *, t_inlining_globals *);
+void lsra_init(methodinfo *, codegendata *, t_inlining_globals *, lsradata *);
+void lsra_setup(methodinfo *, codegendata *, registerdata *, lsradata *, loopdata *);
+void lsra_clean_Graph( methodinfo *, codegendata *, lsradata *, loopdata *);
+
+#ifdef LSRA_DEBUG
+void lsra_dump_Graph(methodinfo *, struct depthElement **);
+void lsra_dump_stack(stackptr );
+void print_lifetimes(registerdata *, struct lifetime *);
+#endif
+
+int lsra_get_sbr_end(methodinfo *, loopdata *, int , int *);
+void lsra_scan_registers_canditates(methodinfo *, lsradata *);
+void lsra_join_lifetimes( methodinfo *, codegendata *, lsradata *, loopdata *);
+int lsra_getmaxblock(methodinfo *, loopdata *, int );
+void lsra_calc_lifetime_length(methodinfo *, lsradata *, codegendata *, loopdata *);
+
+void lsra_merge_i_lists(struct lifetime *, struct lifetime *);
+
+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 );
+void lsra_new_local(lsradata *, s4 , int );
+struct _i_list *lsra_add_i_list(struct _i_list *, int, int ,int );
+
+void lsra_sort_lt(struct lifetime **);
+void lsra_main(methodinfo *, lsradata *, registerdata *);
+void _lsra_main( methodinfo *, lsradata *, struct lifetime *, struct lsra_reg *, int , int , int *, int *);
+void lsra_expire_old_intervalls(lsradata *, struct lifetime *, struct lsra_reg *);
+void _lsra_expire_old_intervalls(struct lifetime *, struct lsra_reg *, struct active_lt **, int *);
+void spill_at_intervall(lsradata *, struct lifetime *);
+void _spill_at_intervall(struct lifetime *, struct active_lt **, int *);
+void lsra_add_active(struct lifetime *, struct active_lt **, int *);
+void lsra_alloc(methodinfo *, registerdata *, struct lifetime *, 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);
+#endif /* _LSRA_H */
+
+
+/*
+ * 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:
+ */
--- /dev/null
+/* jit/lsra.inc - linear scan register allocator
+
+ Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
+ Institut f. Computersprachen, TU Wien
+ R. Grafl, A. Krall, C. Kruegel, C. Oates, R. Obermaisser, M. Probst,
+ S. Ring, E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich,
+ J. Wenninger, C. Ullrich
+
+ 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., 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA.
+
+ Contact: cacao@complang.tuwien.ac.at
+
+ Authors: Christian Ullrich
+
+ $Id: lsra.inc 1590 2004-11-25 13:24:49Z christian $
+
+*/
+
+/* #define LSRA_DEBUG */
+/* #define LSRA_SAVEDVAR */
+/* #define LSRA_MEMORY */
+
+#include "lsra.h"
+#include "loop/graph.h"
+#include "loop/loop.h"
+#include "toolbox/memory.h"
+#include "reg.h"
+#include "options.h"
+#include "string.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+
+void lsra(methodinfo *m, codegendata *cd, registerdata *rd, loopdata *ld, t_inlining_globals *id)
+{
+
+ lsradata *ls;
+
+#ifdef LSRA_DEBUG
+ char name[1256], name1[1256];
+
+ utf_sprint(name, m->class->name);
+ utf_sprint(name1, m->name);
+ strcat(name, name1);
+ utf_sprint(name1, m->descriptor);
+ strcat(name, name1);
+
+
+ printf("LSRA Start for %s\n", name);
+
+ if (strcmp(name,"at/dms/kjc/CSourceClassgenCode(Lat/dms/kjc/BytecodeOptimizer;Ljava/lang/String;Lat/dms/kjc/TypeFactory;)V")==0) {
+ printf("-------------------\n");
+ }
+#endif
+
+ ls=DNEW(lsradata);
+ lsra_init(m, cd, id, ls);
+ lsra_setup(m, cd, rd, ls, ld);
+
+
+ /* Run LSRA */
+ lsra_main(m, ls, rd);
+
+ return;
+}
+
+void lsra_init(methodinfo *m, codegendata *cd, t_inlining_globals *id, lsradata *ls)
+{
+ int i;
+
+ /* Init LSRA Data Structures */
+ ls->back_edge_panic=false;
+ /* lifetimes für alle Basicblocks allokieren */
+ ls->ss_lifetimes=DMNEW(struct lifetime *, m->basicblockcount);
+ for (i=0; i<m->basicblockcount; i++) ls->ss_lifetimes[i]=NULL;
+#ifdef LSRA_DEBUG
+ if (cd->maxlocals != id->cumlocals) panic("lsra: Welche locals nehmen?\n");
+#endif
+ ls->locals_lifetimes=DMNEW(struct lifetime *, cd->maxlocals);
+ for (i=0; i < cd->maxlocals; i++) ls->locals_lifetimes[i]=NULL;
+ ls->lifetimes=NULL;
+ ls->stackslots=NULL;
+ ls->var_index=-1;
+}
+
+void lsra_setup(methodinfo *m, codegendata *cd, registerdata *rd, lsradata *ls, loopdata *ld)
+{
+#ifdef LSRA_DEBUG
+ basicblock *bptr;
+#endif
+ int i,p;
+ s4 t;
+ struct lifetime *lt, *n;
+ int v_index;
+ struct stackslot *ss;
+
+ /* Setup LSRA Data structures */
+ if (opt_loops) panic("lsra with -oloop not possible!\n");
+ if (!opt_loops) {
+ depthFirst(m, ld);
+ analyseGraph(m, ld);
+ }
+
+ /* BBDELETED Blöcke aus loopdata->c_dTable rausschmeissen! */
+ /* Exceptionhandler in loopdata->c_dTable hinzufügen */
+#ifdef LSRA_DEBUG
+ printf("LSRA lsra_clean_Graph\n");
+#endif
+ lsra_clean_Graph(m, cd, ls, ld);
+
+#ifdef LSRA_DEBUG
+ /* sicherheitshalber Konsistenz von m->basicblocks[..] mit basicblocks->next (Liste) überprüfen */
+ printf("LSRA bb prüfen\n");
+ i=0;
+ bptr = m->basicblocks;
+ while (bptr != NULL) {
+ if (i > m->basicblockcount){
+ panic("linked bb list does not correspond with bb array(1)\n");
+ }
+ if (bptr != &(m->basicblocks[i])){
+ panic("linked bb list does not correspond with bb array(2)\n");
+ }
+
+ i++;
+ bptr=bptr->next;
+ }
+ if (i<m->basicblockcount){
+ panic("linked bb list does not correspond with bb array(3)\n");
+ }
+
+ printf("LSRA lsra_dump_Graph\n");
+ lsra_dump_Graph(m, ld->c_dTable);
+#endif
+
+
+ /* Parameter initialisieren = local Vars schreibzugriff bei 0,0*/
+
+ for (p = 0, i = 0; p < m->paramcount; p++) {
+ t = m->paramtypes[p];
+
+ if (rd->locals[i][t].type >= 0)
+ lsra_usage_local(ls, i, t, 0, 0, LSRA_STORE);
+ i++;
+ if (IS_2_WORD_TYPE(t)) /* increment local counter for 2 word types */
+ i++;
+ } /* end for */
+
+#ifdef LSRA_DEBUG
+ printf("LSRA lsra_scan_register_canditates\n");
+#endif
+ lsra_scan_registers_canditates(m, ls);
+ lsra_join_lifetimes(m, cd, ls, ld);
+
+ v_index=-1;
+
+ for (lt=ls->lifetimes; lt != NULL; lt=lt->next) {
+ lt->index=v_index;
+#ifdef LSRA_SAVEDVAR
+ lt->savedvar=SAVEDVAR;
+#endif
+ for (ss=lt->local_ss; ss != NULL; ss=ss->next) {
+ ss->s->varnum=v_index;
+ ss->s->varkind=TEMPVAR; /* just another time */
+ }
+ }
+
+ for (i=0; i < cd->maxlocals; i++) {
+ for (lt=ls->locals_lifetimes[i]; lt != NULL; lt=lt->next) {
+/* lt->local_ss=NULL; */
+#ifdef LSRA_SAVEDVAR
+ lt->savedvar=SAVEDVAR;
+#endif
+ }
+ }
+
+ for (i=0; i < m->basicblockcount; i++) {
+ if (m->basicblocks[i].flags >= BBREACHED) {
+ for (; ls->ss_lifetimes[i] != NULL;) {
+ lt=ls->ss_lifetimes[i];
+#ifdef LSRA_SAVEDVAR
+ lt->savedvar=SAVEDVAR;
+#endif
+ if (lt->s->varkind == LOCALVAR) {
+ /* join with LOCALVAR */
+ /* local Lifetime vom richtigen Type suchen */
+ for (n=ls->locals_lifetimes[lt->s->varnum]; (n!=NULL) && (n->type!=lt->s->type);n=n->next);
+#ifdef LSRA_DEBUG
+ if (n == NULL) panic("lsra_setup: Local Var not found\n");
+#endif
+ lsra_merge_i_lists(n, lt);
+ ss=DNEW(struct stackslot);
+ ss->s=lt->s;
+ ss->next=n->local_ss;
+ n->local_ss=ss;
+
+ ls->ss_lifetimes[i]=lt->next;
+ } else {
+#ifdef LSRA_DEBUG
+ if (lt->s == NULL) panic("lsra_setup: Wrong assumption about Stackslot Lifetimes -> s\n");
+
+#endif
+ if ((lt->s != NULL) && (lt->s->varkind != ARGVAR)) {
+ if (lt->s->varkind != ARGVAR) {
+ lt->s->varkind=TEMPVAR;
+ lt->s->varnum=v_index;
+ }
+ lt->index=lt->v_index=v_index;
+ for (ss=lt->local_ss; ss!=NULL; ss=ss->next) {
+ ss->s->varnum=v_index;
+ lt->s->varkind=TEMPVAR;
+ }
+
+ ls->ss_lifetimes[i]=lt->next;
+ lt->next=ls->lifetimes;
+ ls->lifetimes=lt;
+ } else {
+ ls->ss_lifetimes[i]=lt->next;
+ }
+ --v_index;
+ }
+ } /* for */
+ } /* if */
+ }
+
+ for (i=0; i < cd->maxlocals; i++) {
+ if (ls->locals_lifetimes[i] != NULL) {
+ for (lt=ls->locals_lifetimes[i]; lt->next != NULL; lt=lt->next);
+ lt->next=ls->lifetimes;
+ ls->lifetimes=ls->locals_lifetimes[i];
+ }
+ }
+
+ /* calc lifetime length */
+#ifdef LSRA_DEBUG
+ printf("Lifetimes before calc_lifetime_length: \n");
+ print_lifetimes(rd, ls->lifetimes);
+ printf("LSRA lsra_calc_lifetime_lengthe\n");
+#endif
+ lsra_calc_lifetime_length(m, ls, cd, ld);
+}
+
+int lsra_get_sbr_end(methodinfo *m, loopdata *ld, int bb, int *bb_visited)
+{
+ int j, bb_end;
+ struct depthElement *de;
+ instruction *ip;
+
+ bb_visited[bb]=true;
+ ip = m->basicblocks[bb].iinstr + m->basicblocks[bb].icount -1;/* set ip to last instruction */
+ if (ip->opc == ICMD_RET)
+ return bb;
+ /* This Block is not the end -> search all following Blocks */
+ j=bb_end=-1;
+ for (de=ld->c_dTable[bb]; de != NULL; de=de->next) {
+ if (!bb_visited[de->value]) {
+ j=lsra_get_sbr_end(m, ld, de->value, bb_visited);
+ if (j!=-1) { /* No new return path found */
+ if ((bb_end != -1) && (j!=bb_end)) panic("SBR has more than one exit Blocks\n");
+ bb_end=j;
+ }
+ }
+ }
+ return bb_end;
+}
+
+void lsra_clean_Graph( methodinfo *m, codegendata *cd, lsradata *ls, loopdata *ld)
+{
+ int i,j;
+ struct depthElement *de, *n;
+ int *bb_succ, *bb_visited, *ptr, index;
+ exceptiontable *ex;
+ struct depthElement **table;
+ bool back_edge;
+#ifdef LSRA_DEBUG
+ struct LoopContainer *lc;
+ struct LoopElement *le;
+#endif
+
+ table=ld->c_dTable;
+
+ if (table == NULL) {
+ return;
+ }
+
+ /* Exceptionhandler noch in c_dTable aufnehmen */
+ ex=cd->exceptiontable;
+#ifdef LSRA_DEBUG
+ printf("ExTable(%i): ", cd->exceptiontablelength);
+#endif
+
+ for (; ex != NULL; ex = ex->down) {
+#ifdef LSRA_DEBUG
+ if (ex->handler == NULL) {
+ panic("lsra_init_blocks EXCEPTIONTABLE without handler!\n");
+ }
+#endif
+#ifdef LSRA_DEBUG
+ if ((ex->handler->debug_nr < 0) || (ex->handler->debug_nr >= m->basicblockcount)) {
+ panic("lsra_init_blocks EXCEPTIONTABLE Handler Blocknummer invalid! \n");
+ }
+
+ printf("%i ",ex->handler->debug_nr);
+#endif
+ dF(m, ld, -1, ex->handler->debug_nr);
+ }
+
+
+ /* Setting up successors of deleted Basic Blocks, in case c_dTable has an edge */
+ /* to a deleted block, so it can be replaced with the next "normal" Block */
+ bb_succ= DMNEW(int, m->basicblockcount);
+ for (i=0; i < m->basicblockcount; i++) {
+ if (m->basicblocks[i].flags >= BBREACHED)
+ bb_succ[i]=i;
+ else {
+ for(j=i; ((j < m->basicblockcount) && (m->basicblocks[j].flags < BBREACHED)); j++);
+ if (j < m->basicblockcount)
+ bb_succ[i]=j;
+ else
+ bb_succ[i]=-1;
+ }
+ }
+
+ back_edge=false;
+#ifdef LSRA_DEBUG
+ printf("\n Cleaning c_dTable ");
+#endif
+ for(i=0; i < m->basicblockcount; i++) {
+#ifdef LSRA_DEBUG
+ printf("\n %i-",i);
+#endif
+ if (m->basicblocks[i].flags < BBREACHED) {
+#ifdef LSRA_DEBUG
+ printf("deleted\n");
+#endif
+ table[i]=NULL;
+ } else {
+ for (de=table[i]; de != NULL; de=de->next) {
+ if (de->value < i) back_edge=true;
+#ifdef LSRA_DEBUG
+ printf("%i-%i ",de->value, bb_succ[de->value]);
+#endif
+ if (bb_succ[de->value] != de->value)
+ de->value = bb_succ[de->value];
+ if (de->value == -1) panic("lsra_clean_Graph: Sprung ins nichts....");
+ }
+ }
+ }
+
+ if (back_edge) {
+ if ( ld->c_allLoops == NULL ) {
+ /* Keine Loops in Datenstruktur aber backedge! */
+ /* sollte nach BasicBlock umsortieren (revererse Depth First sort) */
+ /* und überprüfen von jit/loop/loop.c nicht mehr nötig sein */
+ /* TODO bis dahin eine loop über die backedge eintragen */
+ /* anstatt back_edge_panic zu setzen und alle Lifetimes über die */
+ /* gesamt Methode auszudehnen */
+ ls->back_edge_panic = true;
+ }
+ }
+#ifdef LSRA_DEBUG
+ if (back_edge) {
+ if ( ld->c_allLoops == NULL ) {
+ printf("-------------Warnung Back Edge + no LOOP..\n");
+ }
+ else
+ printf("Back-edges + Loops:\n");
+ lc = ld->c_allLoops;
+ i = 0;
+ while (lc != NULL) {
+ printf("Loop [%d]: ", ++i);
+ le = lc->nodes;
+ while (le != NULL) {
+ printf("%d ", le->node);
+ printf("\n");
+ le = le->next;
+ }
+ lc = lc->next;
+ }
+ printf("\n");
+ }
+#endif
+
+ bb_visited=DMNEW(int, m->basicblockcount);
+ for (i=0; i<m->basicblockcount; i++) {
+ bb_visited[i]=false;
+ }
+
+#ifdef LSRA_DEBUG
+ printf("LSRA Subroutine patching\n");
+#endif
+ for (i=0; i < m->basicblockcount; i++ ) {
+ /* Search all Subroutine Headers */
+ if (m->basicblocks[i].type == BBTYPE_SBR) {
+#ifdef LSRA_DEBUG
+ printf("Subroutine at BB %3i num pred: %3i Pred: ",i, ld->c_numPre[i]);
+ for (ptr=ld->c_pre[i], index=0; index < ld->c_numPre[i]; ++index, ++ptr)
+ printf("%3i ", *ptr);
+ printf("\n");
+#endif
+ if (ld->c_numPre[i] > 1) { /* only if more than one call */
+#ifdef LSRA_DEBUG
+ printf("Searching End of Subroutine: ");
+#endif
+ j=lsra_get_sbr_end(m, ld, i, bb_visited); /* get Ending Block of Subroutine */
+#ifdef LSRA_DEBUG
+ printf("%3i \n",j);
+#endif
+ /* ensure, that all Predecessors+1 of the Subroutine Header are in the list */
+ /* in the List is only one Predecessor */
+#ifdef LSRA_DEBUG
+ if (ld->c_dTable[j] == NULL) panic("No SBR Return in c_dTable\n");
+ if (ld->c_dTable[j]->next != NULL) panic("More than one SBR Return in c_dTable\n");
+#endif
+ de=ld->c_dTable[j];
+ for (ptr=ld->c_pre[i], index=0; index < ld->c_numPre[i]; ++index, ++ptr) {
+ if (*ptr+1!=de->value) { /* Make new Entry */
+ n=DNEW(struct depthElement);
+ n->value=*ptr+1;
+ n->next=de->next;
+ de->next=n;
+ }
+ }
+ }
+#ifdef LSRA_DEBUG
+ printf( "(%3i)table[%3i %3i]: ",m->basicblocks[j].flags,j,m->basicblocks[j].debug_nr);
+ for (de=ld->c_dTable[j]; de != NULL; de=de->next) {
+ printf( "%3i ", de->value);
+ }
+ printf("\n");
+#endif
+ }
+ }
+}
+
+#ifdef LSRA_DEBUG
+void lsra_dump_Graph(methodinfo *m, struct depthElement **table)
+{
+ int i;
+ struct depthElement *de;
+
+ if (table == NULL) {
+ printf ("table == NULL\n");
+ return;
+ }
+
+ for(i=0; i < m->basicblockcount; i++) {
+
+ switch (m->basicblocks[i].type) {
+
+ case BBTYPE_STD:
+ printf("STD ");
+ break;
+ case BBTYPE_EXH:
+ printf("EXH ");
+ break;
+ case BBTYPE_SBR:
+ printf("SBR ");
+ break;
+
+ default:
+ printf("%3i ", m->basicblocks[i].flags);
+ break;
+ }
+
+ printf( "(F%3i)table[%3i %3i]: ",m->basicblocks[i].flags,i,m->basicblocks[i].debug_nr);
+ for (de=table[i]; de != NULL; de=de->next) {
+ printf( "%3i ", de->value);
+ }
+ printf("\n");
+ }
+ printf( "table dump end\n");
+}
+#endif
+
+void lsra_main(methodinfo *m, lsradata *ls, registerdata *rd)
+{
+ struct lifetime *lt, *lt_prev, *lt_temp, *int_lt, *int_lt_last, *flt_lt, *flt_lt_last;
+ int lt_count,lt_int_count,lt_flt_count,lt_left_count;
+ int i;
+ int lsra_mem_use;
+ int sav_reg_count, tmp_reg_count;
+ struct lsra_reg *reg;
+ int reg_count;
+/* varinfo *v; */
+ int type;
+ int flags; /* 0 INMEMORY->lifetimes, 1 INTREG->int_lt, 2 FLTREG->flt_lt */
+ int lsra_reg_use;
+
+ int_lt_last=int_lt=NULL;
+ flt_lt_last=flt_lt=NULL;
+
+ for (lt_count=0,lt=ls->lifetimes; lt!=NULL;lt=lt->next,lt_count++);
+
+
+ for (lt_prev=lt=ls->lifetimes;lt!=NULL;) {
+ lt->reg = -1;
+
+ if (lt->v_index < 0) { /* stackslot */
+ if (lt->s != NULL)
+ type = lt->s->type;
+ else {
+#ifdef LSRA_DEBUG
+ if (lt->local_ss == NULL) panic("lsra_main Lifetime for Stackslot invalid\n");
+#endif
+ type = lt->local_ss->s->type;
+ }
+ } else { /* local var */
+ if (rd->locals[lt->v_index][lt->type].type>=0) {
+ type = rd->locals[lt->v_index][lt->type].type;
+ } else panic("Type Data Mismatch 2\n");
+ }
+
+ switch (type) {
+ case TYPE_LNG:
+#if defined(__I386__)
+ /*
+ * for i386 put all longs in memory
+ */
+ flags=0;
+ break;
+#endif
+ case TYPE_INT:
+ case TYPE_ADR:
+ flags=1;
+ break;
+ case TYPE_DBL:
+ case TYPE_FLT:
+ flags=2;
+ break;
+ default:
+ panic("Unknown Type\n");
+ }
+
+ if (flags!=0) {
+ switch (flags) {
+ case 1: /* l->lifetimes -> int_lt */
+ if (int_lt == NULL) {
+ int_lt_last=int_lt=lt;
+ } else {
+ int_lt_last->next=lt;
+ int_lt_last=lt;
+ }
+ break;
+ case 2: /* l->lifetimes -> flt_lt */
+ if (flt_lt==NULL) {
+ flt_lt_last=flt_lt=lt;
+ } else {
+ flt_lt_last->next=lt;
+ flt_lt_last=lt;
+ }
+ break;
+ }
+ lt_temp=lt;
+ if (lt == ls->lifetimes) {
+ lt=lt_prev=ls->lifetimes=ls->lifetimes->next;
+ } else {
+ lt_prev->next=lt->next;
+ lt=lt->next;
+ }
+ lt_temp->next=0;
+ } else {
+ lt_prev=lt;
+ lt=lt->next;
+ }
+ }
+ lsra_sort_lt(&int_lt);
+ lsra_sort_lt(&(ls->lifetimes));
+ lsra_sort_lt(&flt_lt);
+
+ for (lt_int_count=0,lt=int_lt; lt!=NULL;lt=lt->next,lt_int_count++);
+ for (lt_flt_count=0,lt=flt_lt; lt!=NULL;lt=lt->next,lt_flt_count++);
+ for (lt_left_count=0,lt=ls->lifetimes; lt!=NULL;lt=lt->next,lt_left_count++);
+
+#ifdef LSRA_DEBUG
+ printf("\nLifetimes: %3i left: %3i Intlt: %3i Fltlt: %3i \n",lt_count,lt_left_count,lt_int_count,lt_flt_count);
+#endif
+ if (lt_count != lt_int_count + lt_flt_count + lt_left_count) {
+ panic ("lifetimes missing\n");
+ }
+ lsra_reg_use=rd->savintregcnt;
+ if (int_lt!=NULL) {
+ for (reg_count = 0; nregdescint[reg_count] != REG_END; reg_count++);
+
+ reg=DMNEW(struct lsra_reg,reg_count);
+ sav_reg_count=0;
+ for (i=0; i<reg_count ; i++)
+ if (nregdescint[i]==REG_SAV) {
+ reg[sav_reg_count].reg_index=i;
+ reg[sav_reg_count].use=0;
+ sav_reg_count++;
+ }
+ tmp_reg_count=sav_reg_count;
+ for (i=0; i<reg_count ; i++) {
+#if defined(__I386__)
+ if ((method_uses_ecx) && (i==ECX)) continue;
+ if ((method_uses_edx) && (i==EDX)) continue;
+#endif
+ if (nregdescint[i]==REG_TMP) {
+ reg[tmp_reg_count].reg_index=i;
+ reg[tmp_reg_count].use=0;
+ tmp_reg_count++;
+ }
+ }
+ _lsra_main(m, ls, int_lt, reg, tmp_reg_count, sav_reg_count, &lsra_mem_use, &lsra_reg_use);
+ if (lsra_reg_use > rd->savintregcnt) lsra_reg_use=rd->savintregcnt;
+/* r->maxsavintreguse=lsra_reg_use; */
+ }
+ rd->maxsavintreguse= lsra_reg_use;
+ lsra_reg_use=rd->savfltregcnt;
+
+ if (flt_lt!=NULL){
+ for (reg_count = 0; nregdescfloat[reg_count] != REG_END; reg_count++);
+
+ reg=DMNEW(struct lsra_reg,reg_count);
+ sav_reg_count=0;
+ for (i=0; i<reg_count ; i++)
+ if (nregdescfloat[i]==REG_SAV) {
+ reg[sav_reg_count].reg_index=i;
+ reg[sav_reg_count].use=0;
+ sav_reg_count++;
+ }
+
+ tmp_reg_count=sav_reg_count;
+ for (i=0; i<reg_count ; i++)
+ if (nregdescfloat[i]==REG_TMP) {
+ reg[tmp_reg_count].reg_index=i;
+ reg[tmp_reg_count].use=0;
+ tmp_reg_count++;
+ }
+ _lsra_main(m,ls, flt_lt, reg, tmp_reg_count, sav_reg_count, &lsra_mem_use, &lsra_reg_use);
+ if (lsra_reg_use > rd->savfltregcnt) lsra_reg_use=rd->savfltregcnt;
+/* r->maxsavfltreguse=0; */
+ }
+
+ rd->maxsavfltreguse=lsra_reg_use;
+
+#ifndef SPECIALMEMUSE
+#if defined(__X86_64__)
+ /*
+ * XXX: we have a problem here, but allocating a little more stack space
+ * is better than having a bug
+ */
+ /* if (arguments_num > (intreg_argnum + fltreg_argnum)) */
+ /* ifmemuse = arguments_num - (intreg_argnum + fltreg_argnum); */
+ if (rd->arguments_num > rd->fltreg_argnum)
+ lsra_mem_use = rd->arguments_num - rd->fltreg_argnum;
+#else
+ if (rd->arguments_num > rd->intreg_argnum)
+ lsra_mem_use = rd->arguments_num - rd->intreg_argnum;
+#endif
+ else
+ lsra_mem_use = 0;
+#endif
+
+#ifdef LSRA_DEBUG
+ printf("Alloc Rest\n");
+#endif
+ lsra_alloc(m, rd, ls->lifetimes,&lsra_mem_use);
+#ifdef LSRA_DEBUG
+ printf("Alloc Int\n");
+#endif
+ lsra_alloc(m, rd, int_lt,&lsra_mem_use);
+#ifdef LSRA_DEBUG
+ printf("Alloc Flt\n");
+#endif
+ lsra_alloc(m, rd, flt_lt,&lsra_mem_use);
+
+#ifdef LSRA_DEBUG
+ printf("Int RA complete \n");
+ printf("Lifetimes after splitting int: \n");
+ print_lifetimes(rd, int_lt);
+
+ printf("Flt RA complete \n");
+ printf("Lifetimes after splitting flt:\n");
+ print_lifetimes(rd, flt_lt);
+
+ printf("Rest RA complete \n");
+ printf("Lifetimes after leftt:\n");
+ print_lifetimes(rd, ls->lifetimes);
+#endif
+
+ rd->maxmemuse=lsra_mem_use;
+}
+
+void lsra_alloc(methodinfo *m, registerdata *rd, struct lifetime *lifet, int *mem_use)
+{
+ int flags,regoff;
+ struct lifetime *lt;
+ struct freemem *fmem;
+ struct stackslot *n;
+
+ fmem=DNEW(struct freemem);
+ fmem->off=-1;
+ fmem->next=NULL;
+
+ for (lt=lifet;lt!=NULL;lt=lt->next) {
+#ifdef LSRA_MEMORY
+ lt->reg=-1;
+#endif
+ if (lt->reg==-1) {
+ flags=INMEMORY;
+
+ regoff=lsra_getmem(lt, fmem, mem_use);
+ } else {
+ flags=lt->savedvar;
+ regoff=lt->reg;
+ }
+
+ if (lt->v_index < 0) {
+ if (lt->s!=NULL) {
+ lsra_setflags( &(lt->s->flags), flags);
+ lt->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) {
+/* lsra_setflags( &(rd->locals[lt->v_index][lt->type].flags), flags); */
+ rd->locals[lt->v_index][lt->type].flags= flags;
+ rd->locals[lt->v_index][lt->type].regoff=regoff;
+ } else panic("Type Data mismatch 1\n");
+ }
+ }
+}
+
+void lsra_setflags(int *flags, int newflags)
+{
+ if ( newflags & INMEMORY)
+ *flags |= INMEMORY;
+ else
+ *flags &= ~INMEMORY;
+
+ if (newflags & SAVEDVAR)
+ *flags |= SAVEDVAR;
+}
+
+int lsra_getmem(struct lifetime *lt, struct freemem *fmem, int *mem_use)
+{
+ struct freemem *fm, *p;
+
+ /* noch kein Speicher vergeben, oder alle Enden später */
+ if ((fmem->next == NULL) || (fmem->next->end >= lt->i_start)) /* wirklich >= oder reicht > */
+ fm=lsra_getnewmem(mem_use);
+ 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;
+ return fm->off;
+}
+
+struct freemem *lsra_getnewmem(int *mem_use)
+{
+ struct freemem *fm;
+
+ fm=DNEW(struct freemem);
+ fm->next=NULL;
+ fm->off=*mem_use;
+ (*mem_use)++;
+ return fm;
+}
+
+void _lsra_main( methodinfo *m, lsradata *ls, struct lifetime *lifet, struct lsra_reg *reg, int tmp_reg_count, int sav_reg_count, int *mem_use, int *reg_use)
+{
+ struct lifetime *lt;
+/* struct active_lt *a; */
+ int i;
+ int _reg_use;
+ int reg_count, active_count;
+
+ if ((tmp_reg_count+sav_reg_count) == 0) {
+ for (lt=lifet; lt != NULL; lt=lt->next)
+ lt->reg=-1;
+ return;
+ }
+
+ ls->active_tmp = NULL;
+ ls->active_sav = NULL;
+ ls->active_tmp_count=0;
+ ls->active_sav_count=0;
+ for (lt=lifet; lt != NULL; lt=lt->next) {
+ lsra_expire_old_intervalls(ls, lt,reg);
+ if (lt->savedvar && (!m->isleafmethod)) {
+ reg_count=sav_reg_count;
+ active_count=ls->active_sav_count;
+ }
+ else {
+ reg_count=tmp_reg_count;
+ active_count=ls->active_sav_count+ls->active_tmp_count;
+ }
+ if (active_count == reg_count)
+ spill_at_intervall(ls, lt);
+ else {
+ for (i=reg_count-1;i>=0;i--) {
+ if (reg[i].use==0) {
+ reg[i].use=1;
+ lt->reg=reg[i].reg_index;
+ _reg_use=i;
+ if (_reg_use<*reg_use) *reg_use=_reg_use;
+ break;
+ }
+ }
+ if (i < sav_reg_count)
+ lsra_add_active(lt, &(ls->active_sav), &(ls->active_sav_count));
+ else
+ lsra_add_active(lt, &(ls->active_tmp), &(ls->active_tmp_count));
+ }
+ }
+}
+
+void lsra_add_active(struct lifetime *lt, struct active_lt **active, int *active_count)
+{
+ struct active_lt *alt,*alt1,*alt2;
+ alt=DNEW(struct active_lt);
+ alt->lt=lt;
+
+ for(alt1=alt2=*active; alt1 != NULL; alt2=alt1, alt1=alt1->next)
+ if (alt1->lt->i_end > lt->i_end) break;
+
+ if (alt1 == *active) {
+ alt->next = *active;
+ *active = alt;
+ } else {
+ alt->next = alt2->next;
+ alt2->next = alt;
+ }
+ (*active_count)++;
+}
+
+
+void lsra_expire_old_intervalls(lsradata *ls, struct lifetime *lt, struct lsra_reg *reg)
+{
+ _lsra_expire_old_intervalls(lt, reg, &(ls->active_tmp), &(ls->active_tmp_count));
+ _lsra_expire_old_intervalls(lt, reg, &(ls->active_sav), &(ls->active_sav_count));
+}
+
+void _lsra_expire_old_intervalls(struct lifetime *lt, struct lsra_reg *reg, struct active_lt **active, int *active_count)
+{
+ struct active_lt *alt,*alt1;
+ int i;
+
+ for (alt1=alt=*active; alt != NULL; alt1=alt, alt=alt->next) {
+ if (alt->lt->i_end >= lt->i_start) return;
+ if (alt == *active)
+ *active = (*active)->next;
+ else
+ alt1->next=alt->next;
+
+ for (i=0;reg[i].reg_index != alt->lt->reg;i++);
+ reg[i].use=0;
+/* FREE(alt,struct active_lt); */
+ (*active_count)--;
+ }
+}
+
+void spill_at_intervall(lsradata *ls, struct lifetime *lt )
+{
+ if (lt->savedvar)
+ _spill_at_intervall(lt, &(ls->active_sav), &(ls->active_sav_count));
+ else {
+ _spill_at_intervall(lt, &(ls->active_tmp), &(ls->active_tmp_count));
+ if (lt->reg == -1) /* kein tmp mehr frei gewesen */
+ _spill_at_intervall(lt, &(ls->active_sav), &(ls->active_sav_count));
+ }
+ if (lt->reg == -2) panic("spill_at_intervall: Keine Register mehr frei gewesen!\n");
+}
+
+void _spill_at_intervall(struct lifetime *lt, struct active_lt **active, int *active_count)
+{
+ struct active_lt *alt,*alt1;
+ if (*active == NULL) {
+ lt->reg=-2;
+ return;
+ panic("No Lifetime in Active List -> no free registers at all!\n");
+ }
+ /* get last intervall from active */
+ for (alt1=alt=*active; alt->next != NULL; alt1=alt, alt=alt->next);
+
+ if (alt->lt->i_end > lt->i_end) {
+ lt->reg=alt->lt->reg;
+ alt->lt->reg=-1;
+
+ if (alt == *active)
+ *active=(*active)->next;
+ else
+ alt1->next=alt->next;
+ /* FREE(alt,struct active_lt); */
+ (*active_count)--;
+ lsra_add_active(lt, active, active_count);
+ } else {
+ lt->reg=-1;
+ }
+}
+
+int lsra_getmaxblock(methodinfo *m, loopdata *ld, int bb_start)
+{
+ int i, *blocks;
+ int finished;
+ struct depthElement *hp;
+ int bb_max;
+
+ blocks=DMNEW(int, m->basicblockcount);
+ /* ExTable Ablauf kann in die STD Code BB wieder "hineinspringen" */
+ /* -> deshalb */
+ /* TODO vorher alle "normalen" BB mit 2=bereits besucht initialisieren */
+ bb_max=0;
+
+ for (i=0; i<m->basicblockcount; i++) blocks[i]=-1;
+
+ blocks[bb_start]=1;
+
+ finished=0;
+ while (!finished) {
+ finished=1;
+ for (i=0; i<m->basicblockcount; i++) {
+
+ if (blocks[i] == 1) {
+ if (i > bb_max) bb_max = i;
+ blocks[i]=2; /* visited */
+ for (hp=ld->c_dTable[i]; hp!=NULL; hp=hp->next) {
+ if (blocks[hp->value] != 2) {
+ blocks[hp->value]=1; /* to visit */
+ finished=0;
+ }
+ }
+ }
+ }
+ }
+#ifdef LSRA_DEBUG
+ printf("ExTable searching: BB_MAX %3i ",bb_max);
+ for (i=0; i<m->basicblockcount; i++)
+ if (blocks[i] != -1) printf("%3i ",i);
+ printf("\n");
+#endif
+ return bb_max;
+}
+
+
+void lsra_calc_lifetime_length(methodinfo *m, lsradata *ls, codegendata *cd, loopdata *ld)
+{
+ struct lifetime *lt;
+ struct _i_list *il;
+ struct l_loop *loops;
+ struct b_loop *block_loop;
+ exceptiontable *ex;
+ int *exh_max; /* Exception Handler End BB */
+ int *exh_min; /* Exception Handler Start BB */
+ int *ex_max; /* Exception guarded Area End BB */
+ int *ex_min; /* Exception guarded Area Start BB */
+
+ int blast,bfirst,ilast,ifirst,usage;
+
+ int i, j, num_loops;
+ struct LoopContainer *lc;
+ struct LoopElement *le;
+
+ /**********/
+ /* Todo: */
+ /* Für Exceptionhandler Blocks wurde keine Loop Analyse durchgeführt! */
+ /* -> deshalb vorerst die einzelnen Handler als eine Loop eintragen */
+ /* oder loop analyse extra für jeden Handler aufrufen */
+ /**/
+ /* lifetime der Vars des ExHandlers über guarded Bereich ausdehnen! */
+ /**/
+ /* Falls die einzelnen Blöcke einer Loop nicht durchgehend nummeriert sind */
+ /* auch nicht alle in block_loop eintragen! */
+
+ exh_max = DMNEW(int, cd->exceptiontablelength);
+ exh_min = DMNEW(int, cd->exceptiontablelength);
+ ex_max = DMNEW(int, cd->exceptiontablelength);
+ ex_min = DMNEW(int, cd->exceptiontablelength);
+
+ /* BB der Exhandler bestimmen + BB der guarded Area hinzu */
+ ex = cd->exceptiontable;
+ for (i=0; ex != NULL; i++,ex = ex->down) {
+ if (ex->handler == NULL) {
+#ifdef LSRA_DEBUG
+ printf("lsra_init_blocks EXCEPTIONTABLE without handler!\n");
+#endif
+ } else {
+ if ((ex->handler->debug_nr < 0) || (ex->handler->debug_nr >= m->basicblockcount)) {
+#ifdef LSRA_DEBUG
+ printf("lsra_init_blocks EXCEPTIONTABLE Handler Blocknummer invalid! %i\n", ex->handler->debug_nr);
+#endif
+ } else {
+ exh_min[i]=ex->handler->debug_nr;
+ exh_max[i]=lsra_getmaxblock(m, ld, ex->handler->debug_nr);
+
+ ex_min[i]=ex->start->debug_nr;
+ ex_max[i]=ex->end->debug_nr;
+#ifdef LSRA_DEBUG
+ printf("EX %3i exmin %3i exmax %3i exhmin %3i exhmax %3i\n",i,ex_min[i],ex_max[i],exh_min[i],exh_max[i]);
+#endif
+ }
+ }
+ }
+
+ /* extend lifetime within loops */
+
+
+ for (num_loops=0,lc =ld->c_allLoops;lc!=NULL;num_loops++,lc=lc->next);
+
+ loops=DMNEW(struct l_loop,num_loops);
+
+ for (i=0,lc=ld->c_allLoops;i<num_loops;i++,lc=lc->next) {
+
+ le = lc->nodes;
+ bfirst=m->basicblockcount;
+ blast=0;
+ while (le != NULL) {
+ if (le->node<bfirst) bfirst=le->node;
+ if (le->node>blast) blast=le->node;
+ le = le->next;
+ }
+ loops[i].b_first=bfirst;
+ loops[i].b_last=blast;
+ loops[i].nesting=0;
+ }
+
+/* for (i=0;i<num_loops;i++) printf("loops[%2i] bfirst: %3i blast %3i nesting %3i\n",i,loops[i].b_first,loops[i].b_last,loops[i].nesting); */
+
+ /* sort loops by b_first desc*/
+ for (i=0; i<num_loops-1;i++) {
+ for (j=i+1; j<num_loops;j++) {
+ if (loops[i].b_first < loops[j].b_first) {
+ bfirst=loops[j].b_first;
+ blast=loops[j].b_last;
+ loops[j].b_first=loops[i].b_first;
+ loops[j].b_last=loops[i].b_last;
+ loops[i].b_first=bfirst;
+ loops[i].b_last=blast;
+ }
+ }
+ }
+/* for (i=0;i<num_loops;i++) printf("loops[%2i] bfirst: %3i blast %3i nesting %3i\n",i,loops[i].b_first,loops[i].b_last,loops[i].nesting); */
+ /* check for nesting_level, overlapping */
+ for (i=0; i<num_loops-1;i++) {
+ /*! loops[i].b_first >= loops[i+1].b_first !*/
+ if (loops[i+1].b_last>=loops[i].b_first) {
+ if (loops[i+1].b_last<loops[i].b_last) {
+ /* overlapping -> make one loop of both */
+ loops[i+1].b_last=loops[i].b_last;
+ loops[i].b_first=-1;
+ loops[i].b_last=-1;
+ } else {
+ /* nested loops */
+ loops[i].nesting++; /* only boolean if nested... */
+ }
+ }
+ }
+/* for (i=0;i<num_loops;i++) printf("loops[%2i] bfirst: %3i blast %3i nesting %3i\n",i,loops[i].b_first,loops[i].b_last,loops[i].nesting); */
+
+ block_loop=DMNEW(struct b_loop, m->basicblockcount);
+ for (i=0;i<m->basicblockcount; i++) {
+ block_loop[i].loop=-1;
+ if (i!=0)
+ block_loop[i].instr=block_loop[i-1].instr+m->basicblocks[i-1].icount;
+ else
+ block_loop[i].instr=0;
+ }
+
+ for (i=0; i<num_loops;i++) {
+ if (loops[i].b_first!=-1) {
+ /* valid loop */
+ for (j=loops[i].b_first;j<=loops[i].b_last;j++) block_loop[j].loop=i;
+ }
+ }
+
+ lt=ls->lifetimes;
+ while(lt!=NULL) {
+
+ if (ls->back_edge_panic) {
+ lt->b_start=0;
+ lt->i_start=0;
+ lt->b_end=m->basicblockcount-1;
+ lt->i_end=block_loop[m->basicblockcount-1].instr+m->basicblocks[m->basicblockcount-1].icount;
+ } else {
+ usage = 0;
+ il=lt->i_list;
+ blast=il->b_index;
+ ilast=il->instr;
+ while (il->next!=NULL) {
+ il=il->next;
+ usage++;
+ }
+ bfirst=il->b_index;
+ ifirst=il->instr;
+ /* expand lifetimes in a exceptionhandler to at least the whole handler */
+ /* TODO do a loop analyze for the exceptionhandler, too*/
+ for (i=0; i < cd->exceptiontablelength; i++) {
+
+ if ( !((bfirst > exh_max[i]) || ( blast < exh_min[i])) ) {
+ /* Ãœberschneidung mit exh_???[i]-> lt liegt in Exceptionhandler */
+ /* -> Start auf mindestens die erste Instruktion des geschützten Bereiches legen */
+ if (bfirst >= exh_min[i]) {
+ bfirst=exh_min[i];
+ ifirst=0;
+ }
+ /* -> Ende auf mindestens die letzte Instruktion des geschützten Bereiches legen */
+ if (blast <= exh_max[i]) {
+ blast=exh_max[i];
+ ilast= m->basicblocks[exh_max[i]].icount-1;
+ }
+ }
+ }
+
+ ilast+=block_loop[blast].instr;
+ ifirst+=block_loop[bfirst].instr;
+
+ if ((j=block_loop[bfirst].loop)==-1)
+ j=block_loop[blast].loop;
+
+ if (j!=-1) {
+ if (loops[j].b_first<=bfirst) {
+ bfirst=loops[j].b_first;
+ ifirst=block_loop[bfirst].instr;
+ usage+=loops[j].nesting*100;
+ }
+ if (blast <= loops[j].b_last) {
+ blast=loops[j].b_last;
+ ilast=block_loop[blast].instr+m->basicblocks[blast].icount;
+ usage+=loops[j].nesting*100;
+ }
+ }
+
+ lt->length=ilast-ifirst;
+
+ lt->b_start=bfirst;
+ lt->b_end=blast;
+ lt->i_start=ifirst;
+ lt->i_end=ilast;
+ lt->usagecount=usage;
+ }
+ lt=lt->next;
+ }
+
+#ifdef LSRA_DEBUG
+ for (i=0; i<num_loops;i++) {
+ printf("LoopNR: %3i Start: %3i End: %3i Nesting: %3i Block_loop[%3i]:",i,loops[i].b_first,loops[i].b_last,loops[i].nesting,i);
+ for (j=0;j<m->basicblockcount;j++)
+ if (block_loop[j].loop==i) printf(" %3i",j);
+ printf("\n");
+ }
+#endif
+}
+
+void lsra_sort_lt(struct lifetime **lifet)
+{
+ /* sort lifetimes by increasing start point */
+/* struct lifetime **plt,**plt1; */
+ struct lifetime *lt, lt_new, *temp, *tmp;
+/* int swapped; */
+
+ /* lifetimes are sorted by decreasing start point -> just turn around */
+ /* not really correct through exception and loop lifetime expansion! -> turn around and sort in*/
+ lt_new.next=NULL;
+
+ for (lt=*lifet; lt!= NULL;) {
+ temp=lt->next;
+
+ for(tmp=<_new; (tmp->next!= NULL) && (tmp->next->i_start < lt->i_start); tmp=tmp->next);
+ lt->next=tmp->next;
+ tmp->next=lt;
+ lt=temp;
+ }
+ *lifet=lt_new.next;
+}
+
+
+void print_lifetimes(registerdata *rd, struct lifetime *lt)
+{
+ struct lifetime *n;
+ struct _i_list *ni;
+ int type,flags,regoff,j,varkind;
+/* int i; */
+
+ for (n=lt,j=0; n!=NULL; n=n->next,j++) {
+ if (n->v_index < 0) { /* stackslot */
+ if (n->s != 0) { /* stackslot */
+ type = n->s->type;
+ flags=n->s->flags;
+ regoff=n->s->regoff;
+ varkind=n->s->varkind;
+ } else {
+ if (n->local_ss != 0) {
+ type = n->local_ss->s->type;
+ flags=n->local_ss->s->flags;
+ regoff=n->local_ss->s->regoff;
+ varkind=n->local_ss->s->varkind;
+ }
+ }
+ } else { /* local var */
+/* for (i=TYPE_INT; i<=TYPE_ADR; i++) { */
+ if (rd->locals[n->v_index][n->type].type>=0) {
+ type = rd->locals[n->v_index][n->type].type;
+ flags=rd->locals[n->v_index][n->type].flags;
+ regoff=rd->locals[n->v_index][n->type].regoff;
+ varkind=-1;
+ } else panic("Type Data mismatch 3\n");
+/* } */
+ }
+ printf("i_Start: %3i i_stop: %3i reg: %3i Index: %3i VI: %3i Usage: %3i length: %3i type: %3i flags: %3i varkind: %3i ILst: ",n->i_start,n->i_end,regoff,n->index,n->v_index,n->usagecount, n->length,type,flags, varkind);
+ for (ni=n->i_list; ni!=NULL; ni=ni->next) {
+ if (ni==ni->next) panic("loop in instruction list!\n");
+ printf( "(%3i,%3i) ",ni->b_index,ni->instr);
+ }
+ printf("\n");
+/* if (n->s!=NULL) */
+/* printf(" type: %1i flags: %1i varkind: %1i varnum: %3i regoff: %4i\n",n->s->type,n->s->flags,n->s->varkind,n->s->varnum,n->s->regoff); */
+ }
+ printf( "%3i Lifetimes printed \n",j);
+}
+
+struct stackslot *lsra_make_ss(stackptr s, int bb_index)
+{
+ struct stackslot *ss;
+
+ ss=DNEW(struct stackslot);
+ ss->bb=bb_index;
+ ss->s=s;
+ return ss;
+}
+
+/* merge i_list from lt1 to lt in order */
+void lsra_merge_i_lists(struct lifetime *lt, struct lifetime *lt1)
+{
+ struct _i_list *iptr, *iptr1, *iptr2;
+
+ /* merge i_lists in order */
+ iptr=lt->i_list;
+ iptr2=lt->i_list=NULL;
+ iptr1=lt1->i_list;
+ while ((iptr != NULL) && (iptr1 != NULL)) {
+ if ((iptr->b_index > iptr1->b_index)|| ((iptr->b_index == iptr1->b_index) && (iptr->instr > iptr1->instr))) {
+ if (lt->i_list==NULL) {
+ lt->i_list=iptr;
+/* iptr2=lt->i_list; */
+ } else {
+ iptr2->next=iptr;
+ }
+ iptr2=iptr;
+ iptr=iptr->next;
+ } else {
+ if (lt->i_list==NULL) {
+ lt->i_list=iptr1;
+/* iptr2=lt->i_list; */
+ } else {
+ iptr2->next=iptr1;
+ }
+ iptr2=iptr1;
+ iptr1=iptr1->next;
+ }
+ }
+#ifdef LSRA_DEBUG
+ if (iptr2 == NULL) panic("lsra_merge_i_lists: Empty Instruction List in Lifetime\n");
+#endif
+ if (iptr==NULL)
+ iptr2->next=iptr1;
+ if (iptr1==NULL)
+ iptr2->next=iptr;
+}
+
+#ifdef LSRA_DEBUG
+void dump_join( struct lifetime *lt_passing)
+{
+ struct lifetime *lt;
+ struct stackslot *ss;
+ int i;
+
+ for (lt=lt_passing,i=0; lt != NULL; lt=lt->next, ++i) {
+ printf("Lifetime(%2i)\n PT: ",i);
+ for ( ss=lt->passthrough; ss!=NULL; ss=ss->next)
+ printf("(%2i, %2i, %6p) ",ss->bb, ss->s->varnum, ss->s);
+ printf("\n SS: ");
+ for (ss = lt->local_ss; ss!=NULL; ss=ss->next)
+ printf("(%2i, %2i, %6p) ", ss->bb, ss->s->varnum, ss->s);
+ printf("\n");
+ }
+}
+#endif
+
+void lsra_join_lifetimes(methodinfo *m, codegendata *cd, lsradata *ls, loopdata *ld)
+{
+ int i, j, index, stacks_top;
+ int in1, out1, in2, out2, temp;
+ struct depthElement *de;
+
+ int *in_stacks, *out_stacks;
+ stackptr out, s;
+ struct stackslot **stacks, *ss, *ss_new;
+ struct lifetime *lt, *lt_prev, *lt_new, *lt_passing;
+ struct stackslot *p, *q, *r;
+ bool drop;
+
+#ifdef LSRA_DEBUG
+ stackptr in;
+
+ in=m->basicblocks[0].instack; /* ?falls Instack des Startblocks != leer ?*/
+ if (in != NULL) printf("------------ Instack von BB0 nicht leer! -------\n");
+#endif
+
+ /* join copies of dup/swap? or let just codegen copy the contents? */
+ /* -> ?TODO? save at ICMD_DUP* and ICMD_SWAP Copy Info */
+
+ /* out_stacks hold an index to stacks, which holds the joined stacks */
+ /* in_stacks hold an index to out_stacks, with which they are joined */
+ /* an initial index of -1 mark, that they where not visited yet */
+ in_stacks = DMNEW(int, m->basicblockcount);
+ out_stacks = DMNEW(int, m->basicblockcount);
+ stacks = DMNEW(struct stackslot *, m->basicblockcount);
+/* for (i=0; i< m->basicblockcount; i++) stacks[i]=NULL; */
+ for (i=0; i < m->basicblockcount; i++ ) in_stacks[i]=out_stacks[i]=-1;
+ stacks_top=0;
+
+ for (i=0; i < m->basicblockcount; i++)
+ if (m->basicblocks[i].flags >= BBREACHED) {
+ if ((out=m->basicblocks[i].outstack) != NULL) {
+ ss=lsra_make_ss(out, i);
+ ss->next=NULL;
+ stacks[stacks_top]=ss;
+ out_stacks[i]=stacks_top++;
+ for (de=ld->c_dTable[i]; de != NULL; de=de->next) {
+ if (in_stacks[de->value] == -1) { /* not visited==joined yet */
+ in_stacks[de->value] = i;
+ ss=lsra_make_ss(m->basicblocks[de->value].instack, de->value);
+ ss->next=stacks[out_stacks[i]];
+ stacks[out_stacks[i]]=ss;
+ } else { /* in stacks already joined -> join with others */
+ /* join this outstack to index in_stack[de->value] points to */
+ for (ss=stacks[out_stacks[i]]; ss->next != NULL; ss=ss->next); /* get last element */
+ ss->next=stacks[out_stacks[in_stacks[de->value]]];
+ stacks[out_stacks[in_stacks[de->value]]]=stacks[out_stacks[i]];
+ stacks[out_stacks[i]]=NULL;
+ /* update all prior out_stacks indexes to this new join */
+ for (j=0; j <= i; j++) {
+ if (out_stacks[j] == out_stacks[i]) {
+ out_stacks[j]=out_stacks[in_stacks[de->value]];
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /* leere einträge aus stacks entfernen */
+ for (i=index=0; i< stacks_top;) {
+ if (stacks[index]!=NULL) { /* nächsten freien Platz suchen */
+ ++index;
+ ++i;
+ } else {
+ if (stacks[i]==NULL) { /* nächsten bestetzten Platz zum verschieben suchen*/
+ ++i;
+ } else { /* von i nach index umhängen */
+ stacks[index]=stacks[i];
+ stacks[i]=NULL;
+ ++index;
+ }
+ }
+ }
+
+ lt_passing=NULL;
+ /* 0 <= i < index | join all corresponding stackslots of in- and outstacks of stacks[i] to lt_new */
+ /* and put lt_new in lt_passing (if passthrough ss exist in them) or ls->lifetimes */
+ for (i=0; i < index; i++) {
+ while (stacks[i]->s != NULL) {
+ lt_new=NULL;
+ for (ss=stacks[i]; ss!=NULL; ss=ss->next) {
+ /* search stackslot ss->s lifetimelist of basicblock(ss->bb) (ss_lifetimes) */
+ /* remember the link before found lifetime, to remove it afterwards */
+ for (lt_prev=lt=ls->ss_lifetimes[ss->bb]; (lt!=NULL) && (lt->s != ss->s); lt_prev=lt, lt=lt->next);
+#ifdef LSRA_DEBUG
+ if (lt==NULL) panic("lsra_join_lifetimes error in lifetimelist\n");
+#endif
+ /* Remove found lifetime from Block Stackslot Lifetimelist */
+ if (lt==ls->ss_lifetimes[ss->bb]) {
+ ls->ss_lifetimes[ss->bb]=lt->next;
+ } else {
+ lt_prev->next=lt->next;
+ }
+ lt->next=NULL;
+
+ drop = false;
+ if (lt->i_list->instr==-1) {
+ if (out_stacks[in_stacks[ss->bb]] == out_stacks[ss->bb]) {
+ /* Throughpassing Basicblock is already in one "join Group" */
+ /* If this stackslot (lt->s == ss->s) is already in lt_new->local_ss */
+ /* do not add it a second time! */
+ if (lt_new != NULL) {
+ for (ss_new=lt_new->local_ss; (ss_new != NULL) && (ss_new->s != lt->s); ss_new = ss_new->next);
+ if (ss_new != NULL) drop = true;
+ }
+ }
+ }
+ if (!drop) {
+ lt->s->varkind=TEMPVAR; /* no LOCALVAR, ARGVAR or STACKVAR with joined lifetimes */
+ lt->v_index=-1; /* not a local var */
+
+ /* join Lifetime lt to lt_new */
+ if (lt_new == NULL) {
+ lt_new = lt;
+ lt_new->passthrough = NULL;
+ lt_new->s = NULL; /* Stackslots are all in local_ss for joined lifetimes */
+ } else
+ lsra_merge_i_lists( lt_new, lt);
+
+ /* add stackslot to local_ss of lt_new */
+ ss_new = DNEW(struct stackslot);
+ ss_new->s = ss->s;
+ ss_new->bb = ss->bb; /* for debugging only, has no further use */
+ ss_new->next = lt_new->local_ss;
+ lt_new->local_ss = ss_new;
+
+ lt_new->savedvar |= (lt->savedvar & SAVEDVAR);
+
+
+ if (lt->i_list->instr==-1) {
+ /* BB passes this stackslot through -> join later with other side!*/
+ if (out_stacks[in_stacks[ss->bb]] != out_stacks[ss->bb]) {
+ /* Stackslot ist not passed through to same (this) "join group" */
+
+ p = DNEW(struct stackslot);
+ p->bb = ss->bb; /* Basic Block index of joined Lifetime */
+ p->s = ss->s;
+ /* sort p in lt_new->passthrough list by increasing stackslot adress */
+ /* there are no two stackslots allowed, which "join" the same "join groups" */
+ /* in case one has to be dropped, keep the one with the "greater" address */
+ r = NULL;
+ drop = false;
+ in2=out_stacks[in_stacks[p->bb]];
+ out2=out_stacks[p->bb];
+ if (in2 > out2) { temp=in2; in2=out2; out2=temp; }
+ for (q=lt_new->passthrough; (q != NULL);) {
+ in1=out_stacks[in_stacks[q->bb]];
+ out1=out_stacks[q->bb];
+ if (in1 > out1) { temp=in1; in1=out1; out1=temp; }
+
+ if ((in1 == in2) && (out1 == out2)) { /* p->s would join to same group -> drop the one with the lower address */
+ if (p->s < q->s) /* drop p->s, it has the lower address */
+ drop = true;
+ else { /* drop q from the list, since it has the lower address */
+ if (q == lt_new->passthrough ) {
+ lt_new->passthrough=q->next;
+ q=q->next;
+ } else { /* r points to the previous element */
+ r->next=q->next;
+ }
+ }
+ }
+ if (q != NULL) {
+ if (q->s < p->s)
+ r=q; /* remember position for sorting p in */
+ q=q->next;
+ }
+ }
+ if (!drop) {
+ if (r == NULL) {
+ /* List Empty or all elements greater than p->s */
+ p->next=lt_new->passthrough;
+ lt_new->passthrough=p;
+ } else {
+ p->next=r->next;
+ r->next=p;
+ }
+ }
+ }
+ }
+ }
+ ss->s=ss->s->prev; /* Next Stackslot for next Iteration */
+ } /*for */
+ if (lt_new->passthrough != NULL) {
+ lt_new->next=lt_passing;
+ lt_passing=lt_new;
+ } else {
+ lt_new->next=ls->lifetimes;
+ ls->lifetimes=lt_new;
+ }
+ }/* while */
+ } /* for */
+
+ /* join lifetimes with same stackslots in ->passthrough in lt_passing */
+ for (lt=lt_passing; lt != NULL; lt=lt->next) {
+ while (lt->passthrough != NULL) {
+#ifdef LSRA_DEBUG
+ printf("before \n");
+ dump_join(lt_passing);
+#endif
+ s=lt->passthrough->s;
+ lt->passthrough=lt->passthrough->next; /* drop this stackslot from lt_passthrough list */
+ /* search for next lifetime, which has the same stackslot in passthrough */
+ /* lt_new->next will point to it */
+ /* there has to be another lifetime after lt with same s in passthrough */
+ for (lt_new=lt; (lt_new->next != NULL); lt_new=lt_new->next) {
+ /* passthrough is sorted by increasing address of s */
+ /* remember in q the list element before p with p->s == s */
+ for (p=lt_new->next->passthrough; (p!=NULL) && (p->s < s); q=p,p=p->next);
+ if ((p != NULL) && (p->s == s)) {
+ /* found -> now drop this stackslot from lt_new's passtrough list */
+ if (p == lt_new->next->passthrough) { /* first element in list */
+ lt_new->next->passthrough = lt_new->next->passthrough->next;
+ } else
+ q->next=p->next;
+ break;
+ }
+ }
+#ifdef LSRA_DEBUG
+ if (lt_new->next==NULL)
+ panic("lsra_join_lifetimes error in lt_passing lifetimelist\n");
+#endif
+ /* join lt and lt_new->next to lt */
+ lt->savedvar |= (lt_new->next->savedvar & SAVEDVAR);
+
+ /* join local_ss lists */
+#ifdef LSRA_DEBUG
+ if (lt_new->next->local_ss == NULL)
+ panic("lsra_join_lifetimes Lifetime without stackslot\n");
+#endif
+ for (ss=lt_new->next->local_ss; (ss->next != NULL); ss=ss->next);
+ ss->next=lt->local_ss;
+ lt->local_ss=lt_new->next->local_ss;
+
+ /* merge i_lists in order */
+ lsra_merge_i_lists(lt, lt_new->next);
+
+ /* join passthrough lists in ascending order */
+ /* if there are duplicates, it happened that a join was done through the */
+ /* other joins till now, so just drop both of them */
+ p=lt->passthrough;
+ q=lt_new->next->passthrough;
+ lt->passthrough=NULL;
+ ss=NULL; /* pointer to the end of lt->passthrough */
+ while ( (p!=NULL) && (q!=NULL) ) {
+ if (p->s > q->s) {
+ if (ss==NULL) {
+ lt->passthrough=q;
+ } else {
+ ss->next=q;
+ }
+ ss=q;
+ q=q->next;
+ } else {
+ if (q->s == p->s) {
+ /* Drop both stackslots -> they where just joined through some other joins */
+ q=q->next;
+ p=p->next;
+ } else {
+ /* p->s < q->s */
+ if (ss==NULL) {
+ lt->passthrough=p;
+ } else {
+ ss->next=p;
+ }
+ ss=p;
+ p=p->next;
+ }
+ }
+ }
+ if (q == NULL) {
+ if (lt->passthrough == NULL)
+ lt->passthrough=p;
+ else
+ ss->next = p;
+ }
+ if (p == NULL) {
+ if (lt->passthrough == NULL)
+ lt->passthrough=q;
+ else
+ ss->next = q;
+ }
+ lt_new->next=lt_new->next->next; /* throw away joined lifetime lt_new->next */
+#ifdef LSRA_DEBUG
+ printf("after\n");
+ dump_join(lt_passing);
+#endif
+ } /* while */
+ } /* for */
+
+ if (lt_passing!=NULL) {
+ for (lt=lt_passing; (lt->next!=NULL); lt=lt->next);
+ lt->next=ls->lifetimes;
+ ls->lifetimes=lt_passing;
+ }
+}
+
+
+struct _i_list *lsra_add_i_list(struct _i_list *i_list, int instr, int b_index, int store)
+{
+ struct _i_list *n;
+
+ n=DNEW(struct _i_list);
+ n->instr=instr;
+ n->b_index=b_index;
+ n->store=store;
+ n->next=i_list;
+ return n;
+}
+
+void lsra_add_ss(struct lifetime *lt, stackptr s) {
+ struct stackslot *ss;
+ /* Stackslot noch nicht eingetragen? */
+ if ((lt->local_ss==NULL) || (lt->local_ss->s != s)) {
+ ss = DNEW(struct stackslot);
+ ss->s = s;
+ ss->next = lt->local_ss;
+ lt->local_ss = ss;
+ if (s != NULL) lt->savedvar |= s->flags & SAVEDVAR;
+ }
+}
+
+#define lsra_new_stack(ls, s, block, instr) _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;
+
+ n=DNEW(struct lifetime);
+
+ n->index=s->varnum;
+ n->savedvar = (s->flags & SAVEDVAR);
+ n->s=s;
+ n->usagecount=1;
+ if (n->s->varkind == LOCALVAR)
+ n->v_index=n->s->varnum;
+ else
+ n->v_index=-1;
+ n->i_list=NULL;
+ n->local_ss=NULL;
+
+ n->next=ls->ss_lifetimes[block];
+ ls->ss_lifetimes[block]=n;
+
+ n->i_list=lsra_add_i_list(n->i_list, instr, block, store);
+}
+
+#define lsra_from_stack(ls, s, block, instr) _lsra_from_stack(ls, s, block, instr, LSRA_LOAD)
+#define lsra_pop_from_stack(ls, s, block, instr) _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;
+
+ for (n=ls->ss_lifetimes[block]; (n!=NULL) && (n->s!=s);n=n->next);
+ if (n==NULL) {
+ _lsra_new_stack(ls, s, block, instr, store);
+ /* ist mit dem neuen joinen hinterher immer so, wenn ein Stackslot in einen BB "reinkommt" */
+/* printf("type %i flags %i varkind %i varnum %i regoff %i \n",s->type,s->flags ,s->varkind ,s->varnum ,s->regoff); */
+/* panic("lsra_from_stack: Var on Stack not found"); */
+ } else {
+ n->usagecount++;
+ n->i_list=lsra_add_i_list(n->i_list, instr, block, store);
+ }
+}
+
+void lsra_usage_local(lsradata *ls, s4 v_index, int type, int block, int instr, int store)
+{
+ struct lifetime *n;
+
+ /* Lifetime vom richtigen Type suchen */
+ for (n=ls->locals_lifetimes[v_index]; (n!=NULL) && (n->type!=type);n=n->next);
+
+ if (n==NULL) {
+#ifdef LSRA_DEBUG
+ if (store != LSRA_STORE) printf("lsra_local_store: Read before write Local var: %i paramcount: ?\n", v_index);
+#endif
+ lsra_new_local(ls, v_index, type);
+ /* neue Lifetimes werden immer am Anfang der Liste eingehängt */
+ n=ls->locals_lifetimes[v_index];
+ }
+ /* add access at (block, instr) to intruction list */
+ n->i_list=lsra_add_i_list(n->i_list, instr, block, store);
+ n->usagecount++;
+}
+
+void lsra_new_local(lsradata *ls, s4 v_index, int type)
+{
+ struct lifetime *n;
+
+ n=DNEW(struct lifetime);
+ n->local_ss=NULL;
+ n->i_list=NULL;
+ n->index=v_index;
+ n->v_index=v_index;
+ n->s=NULL;
+ n->type=type;
+ n->usagecount=0;
+ n->savedvar = SAVEDVAR;
+
+ n->next=ls->locals_lifetimes[v_index];
+ ls->locals_lifetimes[v_index]=n;
+}
+
+#ifdef LSRA_DEBUG
+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);
+ s=s->prev;
+ }
+ printf("\n");
+}
+#endif
+
+void lsra_scan_registers_canditates(methodinfo *m, lsradata *ls)
+{
+ int i;
+ int opcode;
+ int iindex;
+ int len;
+ stackptr src;
+ stackptr dst;
+ instruction *iptr;
+ stackptr in,out;
+ int id, od;
+
+ int b_index;
+
+ b_index=0;
+ while (b_index < m->basicblockcount ) {
+
+ if (m->basicblocks[b_index].flags >= BBREACHED) {
+ dst = m->basicblocks[b_index].instack;
+ if (dst != NULL) { /* create Lifetimes for pass-through Stackslots */
+ in=m->basicblocks[b_index].instack;
+ id=m->basicblocks[b_index].indepth;
+ if (m->basicblocks[b_index].type != BBTYPE_STD) {
+ /* Pay attention to the top Stackslot in BBTYPE_EXH and BBTYPE_SBR Basicblocks */
+ /* this is not a passthrough, but set from the "system" to the exception object or */
+ /* the return adress -> just create a lifetime with a write at instr==0 */
+ lsra_new_stack(ls, in, b_index, 0);
+ in=in->prev;
+ --id;
+ }
+
+ out=m->basicblocks[b_index].outstack;
+ od=m->basicblocks[b_index].outdepth;
+
+ /* ignore all in-stackslots not in outstack */
+ for (;id>od; in=in->prev, --id);
+ /* ignore all out-stackslots not in instack */
+ for (;od>id; out=out->prev, --od);
+ /* ignore all non equal stackslots from in and outstack */
+ for (;in != out; in=in->prev, out=out->prev, --id);
+ /* set up a lifetime for the rest: */
+ /* stackslot adress equal, stackslot"number" equal */
+ for (;in!=NULL; in=in->prev) {
+ /* Make 2 entries -> one for the instack, one for the out stack */
+ lsra_new_stack(ls, in, b_index, -1);
+ lsra_new_stack(ls, in, b_index, -1);
+ /* } */
+ }
+ }
+ iptr = m->basicblocks[b_index].iinstr;
+ len = m->basicblocks[b_index].icount;
+ iindex=0;
+
+ while (iindex<len) {
+ src = dst;
+ dst = iptr->dst;
+ opcode = iptr->opc;
+#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
+ switch (opcode) {
+
+ case ICMD_RET:
+ lsra_usage_local(ls,iptr->op1,TYPE_ADR, b_index,iindex,LSRA_LOAD); /* local read (return adress) */
+
+ /* pop 0 push 0 */
+
+ case ICMD_NOP:
+ case ICMD_ELSE_ICONST:
+ case ICMD_CHECKEXCEPTION:
+ case ICMD_CHECKASIZE:
+ case ICMD_IINC:
+ case ICMD_JSR:
+ case ICMD_RETURN:
+ case ICMD_GOTO:
+ case ICMD_INLINE_START:
+ case ICMD_INLINE_END:
+ 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 */
+ lsra_new_stack(ls,dst,b_index,iindex); /* 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:
+ lsra_usage_local(ls,iptr->op1,opcode-ICMD_ILOAD, b_index,iindex,LSRA_LOAD); /* local->value */
+ lsra_new_stack(ls,dst,b_index,iindex); /* value->stack */
+ /* ?Reference to local var?-> attention if local var is changed */
+ 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:
+
+ lsra_new_stack(ls,dst,b_index,iindex); /* arrayref[index]->stack */
+ lsra_from_stack(ls, src,b_index,iindex); /* stack->index */
+ lsra_from_stack(ls, src->prev,b_index,iindex); /* stack->arrayref */
+ 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:
+
+ lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
+ lsra_from_stack(ls, src->prev,b_index,iindex); /* stack -> index */
+ lsra_from_stack(ls, src->prev->prev,b_index,iindex); /* stack -> arrayref */
+ break;
+
+ case ICMD_POP: /* throw away a stackslot -> check if used anyway! */
+ lsra_pop_from_stack(ls,src,b_index,iindex);
+ break;
+
+ /* pop 1 push 0 store */
+ /* stack -> local */
+
+ case ICMD_ISTORE:
+ case ICMD_LSTORE:
+ case ICMD_FSTORE:
+ case ICMD_DSTORE:
+ case ICMD_ASTORE:
+ lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
+ lsra_usage_local(ls,iptr->op1,opcode-ICMD_ISTORE, b_index,iindex,LSRA_STORE); /* 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 */
+
+ case ICMD_PUTSTATIC: /* stack(value) -> static_field */
+ /* 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_NULLCHECKPOP: /****** ????? -1 -> stack *********/
+ case ICMD_MONITORENTER:
+ case ICMD_MONITOREXIT:
+ lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
+ break;
+
+ /* pop 2 push 0 */
+
+ case ICMD_POP2: /* throw away 2 stackslots -> check if used anyway! */
+ lsra_pop_from_stack(ls,src,b_index,iindex);
+ lsra_pop_from_stack(ls,src->prev,b_index,iindex);
+ 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->method=value */
+
+ case ICMD_IASTORECONST:
+ case ICMD_LASTORECONST:
+ case ICMD_AASTORECONST:
+ case ICMD_BASTORECONST:
+ case ICMD_CASTORECONST:
+ case ICMD_SASTORECONST:
+ lsra_from_stack(ls, src,b_index,iindex); /* stack -> value*/
+ lsra_from_stack(ls, src->prev,b_index,iindex); /* stack -> objref*/
+ break;
+
+ /* pop 0 push 1 dup */
+ /* merge dupped vars??? */
+ case ICMD_DUP:
+ /* lsra_from_stack(ls, src,b_index,iindex);*/ /* inc usage_count! */
+/* dup_alignstackslots(src, dst); */
+ lsra_new_stack(ls,dst,b_index,iindex);
+ break;
+
+ /* pop 0 push 2 dup */
+
+ case ICMD_DUP2:
+ lsra_new_stack(ls,dst->prev,b_index,iindex);
+ lsra_new_stack(ls,dst,b_index,iindex);
+/* dup_alignstackslots(src, dst); */
+/* dup_alignstackslots(src->prev, dst->prev); */
+ lsra_from_stack(ls, src,b_index,iindex); /* or inc usage_count! */
+ lsra_from_stack(ls, src->prev,b_index,iindex); /* inc usage_count! */
+ break;
+
+ /* pop 2 push 3 dup */
+
+ case ICMD_DUP_X1:
+ lsra_from_stack(ls, src,b_index,iindex); /* from for to, or it will not work! inc usage_count! */
+ lsra_from_stack(ls, src->prev,b_index,iindex); /*from for to, or it will not work! inc usage_count! */
+/* dup_alignstackslots(src, dst); */
+/* dup_alignstackslots(src->prev, dst->prev); */
+/* dup_alignstackslots(src, dst->prev->prev); */
+ 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);
+ break;
+
+ /* pop 3 push 4 dup */
+
+ case ICMD_DUP_X2:
+ lsra_from_stack(ls, src,b_index,iindex); /* from for to, or it will not work! inc usage_count! */
+ lsra_from_stack(ls, src->prev,b_index,iindex); /*from for to, or it will not work! inc usage_count! */
+ lsra_from_stack(ls, src->prev->prev,b_index,iindex); /*from for to, or it will not work! inc usage_count! */
+/* dup_alignstackslots(src, dst); */
+/* dup_alignstackslots(src->prev, dst->prev); */
+/* dup_alignstackslots(src->prev->prev, dst->prev->prev); */
+/* dup_alignstackslots(src, dst->prev->prev->prev); */
+ 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);
+ lsra_new_stack(ls,dst,b_index,iindex);
+ break;
+
+ /* pop 3 push 5 dup */
+
+ case ICMD_DUP2_X1:
+ lsra_from_stack(ls, src,b_index,iindex); /* from for to, or it will not work! inc usage_count! */
+ lsra_from_stack(ls, src->prev,b_index,iindex); /*from for to, or it will not work! inc usage_count! */
+ lsra_from_stack(ls, src->prev->prev,b_index,iindex); /*from for to, or it will not work! inc usage_count! */
+/* dup_alignstackslots(src, dst); */
+/* dup_alignstackslots(src->prev, dst->prev); */
+/* dup_alignstackslots(src->prev->prev, dst->prev->prev); */
+/* dup_alignstackslots(src, dst->prev->prev->prev); */
+/* dup_alignstackslots(src->prev, dst->prev->prev->prev->prev); */
+ 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);
+ lsra_new_stack(ls,dst->prev,b_index,iindex);
+ lsra_new_stack(ls,dst,b_index,iindex);
+ break;
+
+ /* pop 4 push 6 dup */
+
+ case ICMD_DUP2_X2:
+ lsra_from_stack(ls, src,b_index,iindex); /* from for to, or it will not work! inc usage_count! */
+ lsra_from_stack(ls, src->prev,b_index,iindex); /*from for to, or it will not work! inc usage_count! */
+ lsra_from_stack(ls, src->prev->prev,b_index,iindex); /*from for to, or it will not work! inc usage_count! */
+ lsra_from_stack(ls, src->prev->prev->prev,b_index,iindex); /*from for to, or it will not work! inc usage_count! */
+/* dup_alignstackslots(src, dst); */
+/* dup_alignstackslots(src->prev, dst->prev); */
+/* dup_alignstackslots(src->prev->prev, dst->prev->prev); */
+/* dup_alignstackslots(src->prev->prev->prev, dst->prev->prev->prev); */
+/* dup_alignstackslots(src, dst->prev->prev->prev->prev); */
+/* dup_alignstackslots(src->prev, dst->prev->prev->prev->prev->prev); */
+ 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);
+ 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);
+ lsra_new_stack(ls,dst,b_index,iindex);
+ break;
+
+ /* pop 2 push 2 swap */
+
+ case ICMD_SWAP:
+ lsra_from_stack(ls, src,b_index,iindex); /* from for to, or it will not work! inc usage_count! */
+ lsra_from_stack(ls, src->prev,b_index,iindex); /*from for to, or it will not work! inc usage_count! */
+/* dst->varnum = src->varnum; */
+/* dst->varkind = src->varkind; */
+ lsra_new_stack(ls,dst->prev,b_index,iindex);
+ lsra_new_stack(ls,dst,b_index,iindex);
+ 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:
+ lsra_from_stack(ls, src,b_index,iindex);
+ lsra_from_stack(ls, src->prev,b_index,iindex);
+ lsra_new_stack(ls,dst,b_index,iindex);
+ break;
+
+ /* pop 1 push 1 */
+
+ case ICMD_IADDCONST:
+ case ICMD_ISUBCONST:
+ case ICMD_IMULCONST:
+ 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_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_ARRAYLENGTH:
+ case ICMD_INSTANCEOF:
+
+ case ICMD_NEWARRAY:
+ case ICMD_ANEWARRAY:
+
+ case ICMD_GETFIELD:
+ lsra_from_stack(ls, src,b_index,iindex);
+ lsra_new_stack(ls,dst,b_index,iindex);
+ break;
+
+ /* pop 0 push 1 */
+
+ case ICMD_GETSTATIC:
+
+ case ICMD_NEW:
+
+ lsra_new_stack(ls,dst,b_index,iindex);
+ break;
+
+ /* pop many push any */
+ case ICMD_INVOKEVIRTUAL:
+ case ICMD_INVOKESPECIAL:
+ case ICMD_INVOKESTATIC:
+ case ICMD_INVOKEINTERFACE:
+ {
+ i = iptr->op1;
+ while (--i >= 0) {
+ lsra_from_stack(ls, src,b_index,iindex);
+ src = src->prev;
+ }
+ if (((methodinfo*)iptr->val.a)->returntype != TYPE_VOID) {
+ lsra_new_stack(ls,dst,b_index,iindex);
+ }
+ break;
+ }
+
+ case ICMD_BUILTIN3:
+ lsra_from_stack(ls, src,b_index,iindex);
+ src = src->prev;
+ case ICMD_BUILTIN2:
+ lsra_from_stack(ls, src,b_index,iindex);
+ src = src->prev;
+ case ICMD_BUILTIN1:
+ lsra_from_stack(ls, src,b_index,iindex);
+ src = src->prev; /* ??????????? */
+ if (iptr->op1 != TYPE_VOID)
+ lsra_new_stack(ls,dst,b_index,iindex);
+ break;
+
+ case ICMD_MULTIANEWARRAY:
+ i = iptr->op1;
+ while (--i >= 0) {
+ lsra_from_stack(ls, src,b_index,iindex);
+ src = src->prev;
+ }
+ lsra_new_stack(ls,dst,b_index,iindex);
+ break;
+
+ default:
+ printf("ICMD %d at %d\n", iptr->opc, (int)(iptr - m->instructions));
+ panic("Missing ICMD code during register allocation");
+ } /* switch */
+ iptr++;
+ iindex++;
+ } /* while instructions */
+ } /* if */
+
+
+
+ b_index++;
+ } /* while blocks */
+}
+
+/*
+ * 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:
+ */
Changes: Edwin Steiner
- $Id: stack.c 1585 2004-11-24 14:20:21Z twisti $
+ $Id: stack.c 1590 2004-11-25 13:24:49Z christian $
*/
printf("\n");
}
printf("\n");
-
+ if (!opt_lsra) {
printf("Interface Table:\n");
for (i = 0; i < cd->maxstack; i++) {
if ((rd->interfaces[i][0].type >= 0) ||
}
}
printf("\n");
-
+ }
if (showdisassemble) {
#if defined(__I386__) || defined(__X86_64__)
u1 *u1ptr;
- Calling the class loader
- Running the main method
- $Id: main.c 1549 2004-11-19 13:17:33Z twisti $
+ $Id: main.c 1590 2004-11-25 13:24:49Z christian $
*/
void **stackbottom = 0;
#endif
-
/* define command line options ************************************************/
#define OPT_CLASSPATH 2
#define OPT_LIBERALUTF 31
#define OPT_VERBOSEEXCEPTION 32
#define OPT_EAGER 33
+#define OPT_LSRA 34
opt_struct opts[] = {
{"rt", false, OPT_RT},
{"xta", false, OPT_XTA},
{"vta", false, OPT_VTA},
+ {"lsra", false, OPT_LSRA},
{NULL, false, 0}
};
printf(" -rt .................. use rapid type analysis\n");
printf(" -xta ................. use x type analysis\n");
printf(" -vta ................. use variable type analysis\n");
+ printf(" -lsra ................ use linear scan register allocation\n");
/* exit with error code */
/***opt_vta = true; not yet **/
break;
+ case OPT_LSRA:
+#if defined(__I386__) || defined(__ALPHA__)
+ opt_lsra = true;
+#else
+ printf("LSRA not available for this architecture\n");
+ opt_lsra = false;
+#endif
+ break;
+
default:
usage();
}
Authors: Christian Thalinger
- $Id: options.c 1546 2004-11-18 12:25:04Z twisti $
+ $Id: options.c 1590 2004-11-25 13:24:49Z christian $
*/
bool opt_verify = true; /* true if classfiles should be verified */
bool opt_eager = false;
+bool opt_lsra = false;
int opt_ind = 1; /* index of processed arguments */
char *opt_arg; /* this one exports the option argument */
Authors: Christian Thalinger
- $Id: options.h 1553 2004-11-19 15:47:13Z carolyn $
+ $Id: options.h 1590 2004-11-25 13:24:49Z christian $
*/
extern bool opt_verify;
extern bool opt_eager;
+extern bool opt_lsra;
+
+
extern int opt_ind;
extern char *opt_arg;
int get_opt(int argc, char **argv, opt_struct *opts);
+
#endif /* _OPTIONS_H */
- Calling the class loader
- Running the main method
- $Id: cacao.c 1549 2004-11-19 13:17:33Z twisti $
+ $Id: cacao.c 1590 2004-11-25 13:24:49Z christian $
*/
void **stackbottom = 0;
#endif
-
/* define command line options ************************************************/
#define OPT_CLASSPATH 2
#define OPT_LIBERALUTF 31
#define OPT_VERBOSEEXCEPTION 32
#define OPT_EAGER 33
+#define OPT_LSRA 34
opt_struct opts[] = {
{"rt", false, OPT_RT},
{"xta", false, OPT_XTA},
{"vta", false, OPT_VTA},
+ {"lsra", false, OPT_LSRA},
{NULL, false, 0}
};
printf(" -rt .................. use rapid type analysis\n");
printf(" -xta ................. use x type analysis\n");
printf(" -vta ................. use variable type analysis\n");
+ printf(" -lsra ................ use linear scan register allocation\n");
/* exit with error code */
/***opt_vta = true; not yet **/
break;
+ case OPT_LSRA:
+#if defined(__I386__) || defined(__ALPHA__)
+ opt_lsra = true;
+#else
+ printf("LSRA not available for this architecture\n");
+ opt_lsra = false;
+#endif
+ break;
+
default:
usage();
}
Authors: Andreas Krall
Reinhard Grafl
- $Id: codegen.c 1507 2004-11-14 17:02:15Z jowenn $
+ $Id: codegen.c 1590 2004-11-25 13:24:49Z christian $
*/
#include "jit/jit.h"
#include "jit/parse.h"
#include "jit/reg.h"
+#include "jit/lsra.h"
#include "builtin.h"
#include "asmpart.h"
#include "jni.h"
#include "jit/codegen.inc"
#include "jit/reg.inc"
+#include "jit/lsra.inc"
/* NullPointerException handlers and exception handling initialisation */
src = bptr->instack;
len = bptr->indepth;
MCODECHECK(64+len);
+ if (opt_lsra) {
while (src != NULL) {
len--;
if ((len == 0) && (bptr->type != BBTYPE_STD)) {
+ /* d = reg_of_var(m, src, REG_ITMP1); */
+ if (!(src->flags & INMEMORY))
+ d= src->regoff;
+ else
+ d=REG_ITMP1;
+ M_INTMOVE(REG_ITMP1, d);
+ store_reg_to_var_int(src, d);
+ }
+ src = src->prev;
+ }
+ } else {
+ while (src != NULL) {
+ len--;
+ if ((len == 0) && (bptr->type != BBTYPE_STD)) {
d = reg_of_var(rd, src, REG_ITMP1);
M_INTMOVE(REG_ITMP1, d);
store_reg_to_var_int(src, d);
}
src = src->prev;
}
+ }
/* walk through all instructions */
src = bptr->outstack;
len = bptr->outdepth;
MCODECHECK(64+len);
+ if (!opt_lsra)
while (src) {
len--;
if ((src->varkind != STACKVAR)) {
Authors: Andreas Krall
Christian Thalinger
- $Id: codegen.c 1577 2004-11-24 13:06:56Z twisti $
+ $Id: codegen.c 1590 2004-11-25 13:24:49Z christian $
*/
#include "jit/i386/codegen.h"
#include "jit/i386/emitfuncs.h"
-
/* register descripton - array ************************************************/
/* #define REG_RES 0 reserved register for OS or code generator */
#include "jit/codegen.inc"
#include "jit/reg.inc"
-
+#include "jit/lsra.inc"
void codegen_stubcalled() {
log_text("Stub has been called");
parentargs_base = rd->maxmemuse + savedregs_num;
+
#if defined(USE_THREADS) /* space to save argument of monitor_enter */
if (checksync && (m->flags & ACC_SYNCHRONIZED))
src = bptr->instack;
len = bptr->indepth;
MCODECHECK(64+len);
+
+ if (opt_lsra) {
while (src != NULL) {
len--;
if ((len == 0) && (bptr->type != BBTYPE_STD)) {
if (!IS_2_WORD_TYPE(src->type)) {
if (bptr->type == BBTYPE_SBR) {
- d = reg_of_var(rd, src, REG_ITMP1);
+ /* d = reg_of_var(m, src, REG_ITMP1); */
+ if (!(src->flags & INMEMORY))
+ d= src->regoff;
+ else
+ d=REG_ITMP1;
i386_pop_reg(cd, d);
store_reg_to_var_int(src, d);
+ } else if (bptr->type == BBTYPE_EXH) {
+ /* d = reg_of_var(m, src, REG_ITMP1); */
+ if (!(src->flags & INMEMORY))
+ d= src->regoff;
+ else
+ d=REG_ITMP1;
+ M_INTMOVE(REG_ITMP1, d);
+ store_reg_to_var_int(src, d);
+ }
+ } else {
+ panic("copy interface registers(EXH, SBR): longs have to me in memory (begin 1)");
+ }
+ }
+ src = src->prev;
+ }
+ } else {
+ while (src != NULL) {
+ len--;
+ if ((len == 0) && (bptr->type != BBTYPE_STD)) {
+ if (!IS_2_WORD_TYPE(src->type)) {
+ if (bptr->type == BBTYPE_SBR) {
+ d = reg_of_var(rd, src, REG_ITMP1);
+ i386_pop_reg(cd, d);
+ store_reg_to_var_int(src, d);
} else if (bptr->type == BBTYPE_EXH) {
d = reg_of_var(rd, src, REG_ITMP1);
M_INTMOVE(REG_ITMP1, d);
}
src = src->prev;
}
+ }
/* walk through all instructions */
src = bptr->outstack;
len = bptr->outdepth;
MCODECHECK(64+len);
+ if (!opt_lsra)
while (src) {
len--;
if ((src->varkind != STACKVAR)) {
Changes: Edwin Steiner
- $Id: jit.c 1530 2004-11-17 20:43:28Z christian $
+ $Id: jit.c 1590 2004-11-25 13:24:49Z christian $
*/
#include "toolbox/memory.h"
#include "types.h"
#include <stdio.h>
+#include "jit/lsra.h"
/* global switches ************************************************************/
log_message_method("Allocating registers: ", m);
/* allocate registers */
- regalloc(m, cd, rd);
+ if (opt_lsra)
+ lsra(m, cd, rd, ld, id);
+ else
+ regalloc(m, cd, rd);
if (compileverbose) {
log_message_method("Allocating registers done: ", m);
--- /dev/null
+/* jit/lsra.inc - linear scan register allocator header
+
+ Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
+ Institut f. Computersprachen, TU Wien
+ R. Grafl, A. Krall, C. Kruegel, C. Oates, R. Obermaisser, M. Probst,
+ S. Ring, E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich,
+ J. Wenninger, C. Ullrich
+
+ 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., 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA.
+
+ Contact: cacao@complang.tuwien.ac.at
+
+ Authors: Christian Ullrich
+
+ $Id: lsra.h 1590 2004-11-25 13:24:49Z christian $
+
+*/
+
+
+#ifndef _LSRA_H
+#define _LSRA_H
+
+#include "loop/loop.h"
+
+#define LSRA_STORE 1
+#define LSRA_LOAD 0
+#define LSRA_POP -1
+
+struct lifetime {
+ int index; /* unique index, LOCALVAR varnum or negative*/
+ int b_start; /* bb of first use */
+ int b_end; /* bb of last use */
+ int i_start; /* instruction number of first use */
+ int i_end; /* instruction number of last use */
+ int length; /* lifetime in instructions */
+ stackptr s; /* stackslot or NULL */
+ int v_index; /* local variable index or -1 */
+ int type;
+ int usagecount; /* number of refernces*/
+ int reg; /* regoffset durch lsra zugewiesen */
+ int savedvar;
+ struct stackslot *passthrough; /* List of Stackslots in Lifetime, which are passed through a Basic Block */
+ struct stackslot *local_ss;
+ struct _i_list *i_list; /* list of instructions with references to var */
+ struct lifetime *next;
+};
+
+/* struct int_list { */
+/* int value; */
+/* int_list *next; */
+/* }; */
+
+struct active_lt {
+ struct lifetime *lt;
+ struct active_lt *next;
+};
+
+struct l_loop {
+ int b_first;
+ int b_last;
+ int nesting;
+};
+
+struct b_loop {
+ int loop;
+ int instr;
+};
+
+struct _i_list {
+ int b_index;
+ int instr;
+ int store;
+ struct _i_list *next;
+};
+
+struct stackslot {
+ stackptr s;
+ int bb;
+ struct stackslot *next;
+};
+
+struct lsra_reg {
+ int reg_index;
+ int use;
+};
+
+struct lsradata {
+ struct lifetime **ss_lifetimes;
+ struct lifetime **locals_lifetimes;
+ struct lifetime *lifetimes;
+ struct stackslot *stackslots;
+ struct active_lt *active_tmp, *active_sav;
+ int active_sav_count, active_tmp_count;
+ int var_index;
+ bool back_edge_panic;
+};
+
+struct freemem {
+ int off;
+ int end;
+ struct freemem *next;
+};
+
+struct sss {
+ int bb;
+ bool out;
+ struct sss *next;
+};
+
+typedef struct lsradata lsradata;
+
+/* function prototypes */
+void lsra(methodinfo *, codegendata *, registerdata *, loopdata *, t_inlining_globals *);
+void lsra_init(methodinfo *, codegendata *, t_inlining_globals *, lsradata *);
+void lsra_setup(methodinfo *, codegendata *, registerdata *, lsradata *, loopdata *);
+void lsra_clean_Graph( methodinfo *, codegendata *, lsradata *, loopdata *);
+
+#ifdef LSRA_DEBUG
+void lsra_dump_Graph(methodinfo *, struct depthElement **);
+void lsra_dump_stack(stackptr );
+void print_lifetimes(registerdata *, struct lifetime *);
+#endif
+
+int lsra_get_sbr_end(methodinfo *, loopdata *, int , int *);
+void lsra_scan_registers_canditates(methodinfo *, lsradata *);
+void lsra_join_lifetimes( methodinfo *, codegendata *, lsradata *, loopdata *);
+int lsra_getmaxblock(methodinfo *, loopdata *, int );
+void lsra_calc_lifetime_length(methodinfo *, lsradata *, codegendata *, loopdata *);
+
+void lsra_merge_i_lists(struct lifetime *, struct lifetime *);
+
+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 );
+void lsra_new_local(lsradata *, s4 , int );
+struct _i_list *lsra_add_i_list(struct _i_list *, int, int ,int );
+
+void lsra_sort_lt(struct lifetime **);
+void lsra_main(methodinfo *, lsradata *, registerdata *);
+void _lsra_main( methodinfo *, lsradata *, struct lifetime *, struct lsra_reg *, int , int , int *, int *);
+void lsra_expire_old_intervalls(lsradata *, struct lifetime *, struct lsra_reg *);
+void _lsra_expire_old_intervalls(struct lifetime *, struct lsra_reg *, struct active_lt **, int *);
+void spill_at_intervall(lsradata *, struct lifetime *);
+void _spill_at_intervall(struct lifetime *, struct active_lt **, int *);
+void lsra_add_active(struct lifetime *, struct active_lt **, int *);
+void lsra_alloc(methodinfo *, registerdata *, struct lifetime *, 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);
+#endif /* _LSRA_H */
+
+
+/*
+ * 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:
+ */
--- /dev/null
+/* jit/lsra.inc - linear scan register allocator
+
+ Copyright (C) 1996, 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
+ Institut f. Computersprachen, TU Wien
+ R. Grafl, A. Krall, C. Kruegel, C. Oates, R. Obermaisser, M. Probst,
+ S. Ring, E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich,
+ J. Wenninger, C. Ullrich
+
+ 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., 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA.
+
+ Contact: cacao@complang.tuwien.ac.at
+
+ Authors: Christian Ullrich
+
+ $Id: lsra.inc 1590 2004-11-25 13:24:49Z christian $
+
+*/
+
+/* #define LSRA_DEBUG */
+/* #define LSRA_SAVEDVAR */
+/* #define LSRA_MEMORY */
+
+#include "lsra.h"
+#include "loop/graph.h"
+#include "loop/loop.h"
+#include "toolbox/memory.h"
+#include "reg.h"
+#include "options.h"
+#include "string.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+
+void lsra(methodinfo *m, codegendata *cd, registerdata *rd, loopdata *ld, t_inlining_globals *id)
+{
+
+ lsradata *ls;
+
+#ifdef LSRA_DEBUG
+ char name[1256], name1[1256];
+
+ utf_sprint(name, m->class->name);
+ utf_sprint(name1, m->name);
+ strcat(name, name1);
+ utf_sprint(name1, m->descriptor);
+ strcat(name, name1);
+
+
+ printf("LSRA Start for %s\n", name);
+
+ if (strcmp(name,"at/dms/kjc/CSourceClassgenCode(Lat/dms/kjc/BytecodeOptimizer;Ljava/lang/String;Lat/dms/kjc/TypeFactory;)V")==0) {
+ printf("-------------------\n");
+ }
+#endif
+
+ ls=DNEW(lsradata);
+ lsra_init(m, cd, id, ls);
+ lsra_setup(m, cd, rd, ls, ld);
+
+
+ /* Run LSRA */
+ lsra_main(m, ls, rd);
+
+ return;
+}
+
+void lsra_init(methodinfo *m, codegendata *cd, t_inlining_globals *id, lsradata *ls)
+{
+ int i;
+
+ /* Init LSRA Data Structures */
+ ls->back_edge_panic=false;
+ /* lifetimes für alle Basicblocks allokieren */
+ ls->ss_lifetimes=DMNEW(struct lifetime *, m->basicblockcount);
+ for (i=0; i<m->basicblockcount; i++) ls->ss_lifetimes[i]=NULL;
+#ifdef LSRA_DEBUG
+ if (cd->maxlocals != id->cumlocals) panic("lsra: Welche locals nehmen?\n");
+#endif
+ ls->locals_lifetimes=DMNEW(struct lifetime *, cd->maxlocals);
+ for (i=0; i < cd->maxlocals; i++) ls->locals_lifetimes[i]=NULL;
+ ls->lifetimes=NULL;
+ ls->stackslots=NULL;
+ ls->var_index=-1;
+}
+
+void lsra_setup(methodinfo *m, codegendata *cd, registerdata *rd, lsradata *ls, loopdata *ld)
+{
+#ifdef LSRA_DEBUG
+ basicblock *bptr;
+#endif
+ int i,p;
+ s4 t;
+ struct lifetime *lt, *n;
+ int v_index;
+ struct stackslot *ss;
+
+ /* Setup LSRA Data structures */
+ if (opt_loops) panic("lsra with -oloop not possible!\n");
+ if (!opt_loops) {
+ depthFirst(m, ld);
+ analyseGraph(m, ld);
+ }
+
+ /* BBDELETED Blöcke aus loopdata->c_dTable rausschmeissen! */
+ /* Exceptionhandler in loopdata->c_dTable hinzufügen */
+#ifdef LSRA_DEBUG
+ printf("LSRA lsra_clean_Graph\n");
+#endif
+ lsra_clean_Graph(m, cd, ls, ld);
+
+#ifdef LSRA_DEBUG
+ /* sicherheitshalber Konsistenz von m->basicblocks[..] mit basicblocks->next (Liste) überprüfen */
+ printf("LSRA bb prüfen\n");
+ i=0;
+ bptr = m->basicblocks;
+ while (bptr != NULL) {
+ if (i > m->basicblockcount){
+ panic("linked bb list does not correspond with bb array(1)\n");
+ }
+ if (bptr != &(m->basicblocks[i])){
+ panic("linked bb list does not correspond with bb array(2)\n");
+ }
+
+ i++;
+ bptr=bptr->next;
+ }
+ if (i<m->basicblockcount){
+ panic("linked bb list does not correspond with bb array(3)\n");
+ }
+
+ printf("LSRA lsra_dump_Graph\n");
+ lsra_dump_Graph(m, ld->c_dTable);
+#endif
+
+
+ /* Parameter initialisieren = local Vars schreibzugriff bei 0,0*/
+
+ for (p = 0, i = 0; p < m->paramcount; p++) {
+ t = m->paramtypes[p];
+
+ if (rd->locals[i][t].type >= 0)
+ lsra_usage_local(ls, i, t, 0, 0, LSRA_STORE);
+ i++;
+ if (IS_2_WORD_TYPE(t)) /* increment local counter for 2 word types */
+ i++;
+ } /* end for */
+
+#ifdef LSRA_DEBUG
+ printf("LSRA lsra_scan_register_canditates\n");
+#endif
+ lsra_scan_registers_canditates(m, ls);
+ lsra_join_lifetimes(m, cd, ls, ld);
+
+ v_index=-1;
+
+ for (lt=ls->lifetimes; lt != NULL; lt=lt->next) {
+ lt->index=v_index;
+#ifdef LSRA_SAVEDVAR
+ lt->savedvar=SAVEDVAR;
+#endif
+ for (ss=lt->local_ss; ss != NULL; ss=ss->next) {
+ ss->s->varnum=v_index;
+ ss->s->varkind=TEMPVAR; /* just another time */
+ }
+ }
+
+ for (i=0; i < cd->maxlocals; i++) {
+ for (lt=ls->locals_lifetimes[i]; lt != NULL; lt=lt->next) {
+/* lt->local_ss=NULL; */
+#ifdef LSRA_SAVEDVAR
+ lt->savedvar=SAVEDVAR;
+#endif
+ }
+ }
+
+ for (i=0; i < m->basicblockcount; i++) {
+ if (m->basicblocks[i].flags >= BBREACHED) {
+ for (; ls->ss_lifetimes[i] != NULL;) {
+ lt=ls->ss_lifetimes[i];
+#ifdef LSRA_SAVEDVAR
+ lt->savedvar=SAVEDVAR;
+#endif
+ if (lt->s->varkind == LOCALVAR) {
+ /* join with LOCALVAR */
+ /* local Lifetime vom richtigen Type suchen */
+ for (n=ls->locals_lifetimes[lt->s->varnum]; (n!=NULL) && (n->type!=lt->s->type);n=n->next);
+#ifdef LSRA_DEBUG
+ if (n == NULL) panic("lsra_setup: Local Var not found\n");
+#endif
+ lsra_merge_i_lists(n, lt);
+ ss=DNEW(struct stackslot);
+ ss->s=lt->s;
+ ss->next=n->local_ss;
+ n->local_ss=ss;
+
+ ls->ss_lifetimes[i]=lt->next;
+ } else {
+#ifdef LSRA_DEBUG
+ if (lt->s == NULL) panic("lsra_setup: Wrong assumption about Stackslot Lifetimes -> s\n");
+
+#endif
+ if ((lt->s != NULL) && (lt->s->varkind != ARGVAR)) {
+ if (lt->s->varkind != ARGVAR) {
+ lt->s->varkind=TEMPVAR;
+ lt->s->varnum=v_index;
+ }
+ lt->index=lt->v_index=v_index;
+ for (ss=lt->local_ss; ss!=NULL; ss=ss->next) {
+ ss->s->varnum=v_index;
+ lt->s->varkind=TEMPVAR;
+ }
+
+ ls->ss_lifetimes[i]=lt->next;
+ lt->next=ls->lifetimes;
+ ls->lifetimes=lt;
+ } else {
+ ls->ss_lifetimes[i]=lt->next;
+ }
+ --v_index;
+ }
+ } /* for */
+ } /* if */
+ }
+
+ for (i=0; i < cd->maxlocals; i++) {
+ if (ls->locals_lifetimes[i] != NULL) {
+ for (lt=ls->locals_lifetimes[i]; lt->next != NULL; lt=lt->next);
+ lt->next=ls->lifetimes;
+ ls->lifetimes=ls->locals_lifetimes[i];
+ }
+ }
+
+ /* calc lifetime length */
+#ifdef LSRA_DEBUG
+ printf("Lifetimes before calc_lifetime_length: \n");
+ print_lifetimes(rd, ls->lifetimes);
+ printf("LSRA lsra_calc_lifetime_lengthe\n");
+#endif
+ lsra_calc_lifetime_length(m, ls, cd, ld);
+}
+
+int lsra_get_sbr_end(methodinfo *m, loopdata *ld, int bb, int *bb_visited)
+{
+ int j, bb_end;
+ struct depthElement *de;
+ instruction *ip;
+
+ bb_visited[bb]=true;
+ ip = m->basicblocks[bb].iinstr + m->basicblocks[bb].icount -1;/* set ip to last instruction */
+ if (ip->opc == ICMD_RET)
+ return bb;
+ /* This Block is not the end -> search all following Blocks */
+ j=bb_end=-1;
+ for (de=ld->c_dTable[bb]; de != NULL; de=de->next) {
+ if (!bb_visited[de->value]) {
+ j=lsra_get_sbr_end(m, ld, de->value, bb_visited);
+ if (j!=-1) { /* No new return path found */
+ if ((bb_end != -1) && (j!=bb_end)) panic("SBR has more than one exit Blocks\n");
+ bb_end=j;
+ }
+ }
+ }
+ return bb_end;
+}
+
+void lsra_clean_Graph( methodinfo *m, codegendata *cd, lsradata *ls, loopdata *ld)
+{
+ int i,j;
+ struct depthElement *de, *n;
+ int *bb_succ, *bb_visited, *ptr, index;
+ exceptiontable *ex;
+ struct depthElement **table;
+ bool back_edge;
+#ifdef LSRA_DEBUG
+ struct LoopContainer *lc;
+ struct LoopElement *le;
+#endif
+
+ table=ld->c_dTable;
+
+ if (table == NULL) {
+ return;
+ }
+
+ /* Exceptionhandler noch in c_dTable aufnehmen */
+ ex=cd->exceptiontable;
+#ifdef LSRA_DEBUG
+ printf("ExTable(%i): ", cd->exceptiontablelength);
+#endif
+
+ for (; ex != NULL; ex = ex->down) {
+#ifdef LSRA_DEBUG
+ if (ex->handler == NULL) {
+ panic("lsra_init_blocks EXCEPTIONTABLE without handler!\n");
+ }
+#endif
+#ifdef LSRA_DEBUG
+ if ((ex->handler->debug_nr < 0) || (ex->handler->debug_nr >= m->basicblockcount)) {
+ panic("lsra_init_blocks EXCEPTIONTABLE Handler Blocknummer invalid! \n");
+ }
+
+ printf("%i ",ex->handler->debug_nr);
+#endif
+ dF(m, ld, -1, ex->handler->debug_nr);
+ }
+
+
+ /* Setting up successors of deleted Basic Blocks, in case c_dTable has an edge */
+ /* to a deleted block, so it can be replaced with the next "normal" Block */
+ bb_succ= DMNEW(int, m->basicblockcount);
+ for (i=0; i < m->basicblockcount; i++) {
+ if (m->basicblocks[i].flags >= BBREACHED)
+ bb_succ[i]=i;
+ else {
+ for(j=i; ((j < m->basicblockcount) && (m->basicblocks[j].flags < BBREACHED)); j++);
+ if (j < m->basicblockcount)
+ bb_succ[i]=j;
+ else
+ bb_succ[i]=-1;
+ }
+ }
+
+ back_edge=false;
+#ifdef LSRA_DEBUG
+ printf("\n Cleaning c_dTable ");
+#endif
+ for(i=0; i < m->basicblockcount; i++) {
+#ifdef LSRA_DEBUG
+ printf("\n %i-",i);
+#endif
+ if (m->basicblocks[i].flags < BBREACHED) {
+#ifdef LSRA_DEBUG
+ printf("deleted\n");
+#endif
+ table[i]=NULL;
+ } else {
+ for (de=table[i]; de != NULL; de=de->next) {
+ if (de->value < i) back_edge=true;
+#ifdef LSRA_DEBUG
+ printf("%i-%i ",de->value, bb_succ[de->value]);
+#endif
+ if (bb_succ[de->value] != de->value)
+ de->value = bb_succ[de->value];
+ if (de->value == -1) panic("lsra_clean_Graph: Sprung ins nichts....");
+ }
+ }
+ }
+
+ if (back_edge) {
+ if ( ld->c_allLoops == NULL ) {
+ /* Keine Loops in Datenstruktur aber backedge! */
+ /* sollte nach BasicBlock umsortieren (revererse Depth First sort) */
+ /* und überprüfen von jit/loop/loop.c nicht mehr nötig sein */
+ /* TODO bis dahin eine loop über die backedge eintragen */
+ /* anstatt back_edge_panic zu setzen und alle Lifetimes über die */
+ /* gesamt Methode auszudehnen */
+ ls->back_edge_panic = true;
+ }
+ }
+#ifdef LSRA_DEBUG
+ if (back_edge) {
+ if ( ld->c_allLoops == NULL ) {
+ printf("-------------Warnung Back Edge + no LOOP..\n");
+ }
+ else
+ printf("Back-edges + Loops:\n");
+ lc = ld->c_allLoops;
+ i = 0;
+ while (lc != NULL) {
+ printf("Loop [%d]: ", ++i);
+ le = lc->nodes;
+ while (le != NULL) {
+ printf("%d ", le->node);
+ printf("\n");
+ le = le->next;
+ }
+ lc = lc->next;
+ }
+ printf("\n");
+ }
+#endif
+
+ bb_visited=DMNEW(int, m->basicblockcount);
+ for (i=0; i<m->basicblockcount; i++) {
+ bb_visited[i]=false;
+ }
+
+#ifdef LSRA_DEBUG
+ printf("LSRA Subroutine patching\n");
+#endif
+ for (i=0; i < m->basicblockcount; i++ ) {
+ /* Search all Subroutine Headers */
+ if (m->basicblocks[i].type == BBTYPE_SBR) {
+#ifdef LSRA_DEBUG
+ printf("Subroutine at BB %3i num pred: %3i Pred: ",i, ld->c_numPre[i]);
+ for (ptr=ld->c_pre[i], index=0; index < ld->c_numPre[i]; ++index, ++ptr)
+ printf("%3i ", *ptr);
+ printf("\n");
+#endif
+ if (ld->c_numPre[i] > 1) { /* only if more than one call */
+#ifdef LSRA_DEBUG
+ printf("Searching End of Subroutine: ");
+#endif
+ j=lsra_get_sbr_end(m, ld, i, bb_visited); /* get Ending Block of Subroutine */
+#ifdef LSRA_DEBUG
+ printf("%3i \n",j);
+#endif
+ /* ensure, that all Predecessors+1 of the Subroutine Header are in the list */
+ /* in the List is only one Predecessor */
+#ifdef LSRA_DEBUG
+ if (ld->c_dTable[j] == NULL) panic("No SBR Return in c_dTable\n");
+ if (ld->c_dTable[j]->next != NULL) panic("More than one SBR Return in c_dTable\n");
+#endif
+ de=ld->c_dTable[j];
+ for (ptr=ld->c_pre[i], index=0; index < ld->c_numPre[i]; ++index, ++ptr) {
+ if (*ptr+1!=de->value) { /* Make new Entry */
+ n=DNEW(struct depthElement);
+ n->value=*ptr+1;
+ n->next=de->next;
+ de->next=n;
+ }
+ }
+ }
+#ifdef LSRA_DEBUG
+ printf( "(%3i)table[%3i %3i]: ",m->basicblocks[j].flags,j,m->basicblocks[j].debug_nr);
+ for (de=ld->c_dTable[j]; de != NULL; de=de->next) {
+ printf( "%3i ", de->value);
+ }
+ printf("\n");
+#endif
+ }
+ }
+}
+
+#ifdef LSRA_DEBUG
+void lsra_dump_Graph(methodinfo *m, struct depthElement **table)
+{
+ int i;
+ struct depthElement *de;
+
+ if (table == NULL) {
+ printf ("table == NULL\n");
+ return;
+ }
+
+ for(i=0; i < m->basicblockcount; i++) {
+
+ switch (m->basicblocks[i].type) {
+
+ case BBTYPE_STD:
+ printf("STD ");
+ break;
+ case BBTYPE_EXH:
+ printf("EXH ");
+ break;
+ case BBTYPE_SBR:
+ printf("SBR ");
+ break;
+
+ default:
+ printf("%3i ", m->basicblocks[i].flags);
+ break;
+ }
+
+ printf( "(F%3i)table[%3i %3i]: ",m->basicblocks[i].flags,i,m->basicblocks[i].debug_nr);
+ for (de=table[i]; de != NULL; de=de->next) {
+ printf( "%3i ", de->value);
+ }
+ printf("\n");
+ }
+ printf( "table dump end\n");
+}
+#endif
+
+void lsra_main(methodinfo *m, lsradata *ls, registerdata *rd)
+{
+ struct lifetime *lt, *lt_prev, *lt_temp, *int_lt, *int_lt_last, *flt_lt, *flt_lt_last;
+ int lt_count,lt_int_count,lt_flt_count,lt_left_count;
+ int i;
+ int lsra_mem_use;
+ int sav_reg_count, tmp_reg_count;
+ struct lsra_reg *reg;
+ int reg_count;
+/* varinfo *v; */
+ int type;
+ int flags; /* 0 INMEMORY->lifetimes, 1 INTREG->int_lt, 2 FLTREG->flt_lt */
+ int lsra_reg_use;
+
+ int_lt_last=int_lt=NULL;
+ flt_lt_last=flt_lt=NULL;
+
+ for (lt_count=0,lt=ls->lifetimes; lt!=NULL;lt=lt->next,lt_count++);
+
+
+ for (lt_prev=lt=ls->lifetimes;lt!=NULL;) {
+ lt->reg = -1;
+
+ if (lt->v_index < 0) { /* stackslot */
+ if (lt->s != NULL)
+ type = lt->s->type;
+ else {
+#ifdef LSRA_DEBUG
+ if (lt->local_ss == NULL) panic("lsra_main Lifetime for Stackslot invalid\n");
+#endif
+ type = lt->local_ss->s->type;
+ }
+ } else { /* local var */
+ if (rd->locals[lt->v_index][lt->type].type>=0) {
+ type = rd->locals[lt->v_index][lt->type].type;
+ } else panic("Type Data Mismatch 2\n");
+ }
+
+ switch (type) {
+ case TYPE_LNG:
+#if defined(__I386__)
+ /*
+ * for i386 put all longs in memory
+ */
+ flags=0;
+ break;
+#endif
+ case TYPE_INT:
+ case TYPE_ADR:
+ flags=1;
+ break;
+ case TYPE_DBL:
+ case TYPE_FLT:
+ flags=2;
+ break;
+ default:
+ panic("Unknown Type\n");
+ }
+
+ if (flags!=0) {
+ switch (flags) {
+ case 1: /* l->lifetimes -> int_lt */
+ if (int_lt == NULL) {
+ int_lt_last=int_lt=lt;
+ } else {
+ int_lt_last->next=lt;
+ int_lt_last=lt;
+ }
+ break;
+ case 2: /* l->lifetimes -> flt_lt */
+ if (flt_lt==NULL) {
+ flt_lt_last=flt_lt=lt;
+ } else {
+ flt_lt_last->next=lt;
+ flt_lt_last=lt;
+ }
+ break;
+ }
+ lt_temp=lt;
+ if (lt == ls->lifetimes) {
+ lt=lt_prev=ls->lifetimes=ls->lifetimes->next;
+ } else {
+ lt_prev->next=lt->next;
+ lt=lt->next;
+ }
+ lt_temp->next=0;
+ } else {
+ lt_prev=lt;
+ lt=lt->next;
+ }
+ }
+ lsra_sort_lt(&int_lt);
+ lsra_sort_lt(&(ls->lifetimes));
+ lsra_sort_lt(&flt_lt);
+
+ for (lt_int_count=0,lt=int_lt; lt!=NULL;lt=lt->next,lt_int_count++);
+ for (lt_flt_count=0,lt=flt_lt; lt!=NULL;lt=lt->next,lt_flt_count++);
+ for (lt_left_count=0,lt=ls->lifetimes; lt!=NULL;lt=lt->next,lt_left_count++);
+
+#ifdef LSRA_DEBUG
+ printf("\nLifetimes: %3i left: %3i Intlt: %3i Fltlt: %3i \n",lt_count,lt_left_count,lt_int_count,lt_flt_count);
+#endif
+ if (lt_count != lt_int_count + lt_flt_count + lt_left_count) {
+ panic ("lifetimes missing\n");
+ }
+ lsra_reg_use=rd->savintregcnt;
+ if (int_lt!=NULL) {
+ for (reg_count = 0; nregdescint[reg_count] != REG_END; reg_count++);
+
+ reg=DMNEW(struct lsra_reg,reg_count);
+ sav_reg_count=0;
+ for (i=0; i<reg_count ; i++)
+ if (nregdescint[i]==REG_SAV) {
+ reg[sav_reg_count].reg_index=i;
+ reg[sav_reg_count].use=0;
+ sav_reg_count++;
+ }
+ tmp_reg_count=sav_reg_count;
+ for (i=0; i<reg_count ; i++) {
+#if defined(__I386__)
+ if ((method_uses_ecx) && (i==ECX)) continue;
+ if ((method_uses_edx) && (i==EDX)) continue;
+#endif
+ if (nregdescint[i]==REG_TMP) {
+ reg[tmp_reg_count].reg_index=i;
+ reg[tmp_reg_count].use=0;
+ tmp_reg_count++;
+ }
+ }
+ _lsra_main(m, ls, int_lt, reg, tmp_reg_count, sav_reg_count, &lsra_mem_use, &lsra_reg_use);
+ if (lsra_reg_use > rd->savintregcnt) lsra_reg_use=rd->savintregcnt;
+/* r->maxsavintreguse=lsra_reg_use; */
+ }
+ rd->maxsavintreguse= lsra_reg_use;
+ lsra_reg_use=rd->savfltregcnt;
+
+ if (flt_lt!=NULL){
+ for (reg_count = 0; nregdescfloat[reg_count] != REG_END; reg_count++);
+
+ reg=DMNEW(struct lsra_reg,reg_count);
+ sav_reg_count=0;
+ for (i=0; i<reg_count ; i++)
+ if (nregdescfloat[i]==REG_SAV) {
+ reg[sav_reg_count].reg_index=i;
+ reg[sav_reg_count].use=0;
+ sav_reg_count++;
+ }
+
+ tmp_reg_count=sav_reg_count;
+ for (i=0; i<reg_count ; i++)
+ if (nregdescfloat[i]==REG_TMP) {
+ reg[tmp_reg_count].reg_index=i;
+ reg[tmp_reg_count].use=0;
+ tmp_reg_count++;
+ }
+ _lsra_main(m,ls, flt_lt, reg, tmp_reg_count, sav_reg_count, &lsra_mem_use, &lsra_reg_use);
+ if (lsra_reg_use > rd->savfltregcnt) lsra_reg_use=rd->savfltregcnt;
+/* r->maxsavfltreguse=0; */
+ }
+
+ rd->maxsavfltreguse=lsra_reg_use;
+
+#ifndef SPECIALMEMUSE
+#if defined(__X86_64__)
+ /*
+ * XXX: we have a problem here, but allocating a little more stack space
+ * is better than having a bug
+ */
+ /* if (arguments_num > (intreg_argnum + fltreg_argnum)) */
+ /* ifmemuse = arguments_num - (intreg_argnum + fltreg_argnum); */
+ if (rd->arguments_num > rd->fltreg_argnum)
+ lsra_mem_use = rd->arguments_num - rd->fltreg_argnum;
+#else
+ if (rd->arguments_num > rd->intreg_argnum)
+ lsra_mem_use = rd->arguments_num - rd->intreg_argnum;
+#endif
+ else
+ lsra_mem_use = 0;
+#endif
+
+#ifdef LSRA_DEBUG
+ printf("Alloc Rest\n");
+#endif
+ lsra_alloc(m, rd, ls->lifetimes,&lsra_mem_use);
+#ifdef LSRA_DEBUG
+ printf("Alloc Int\n");
+#endif
+ lsra_alloc(m, rd, int_lt,&lsra_mem_use);
+#ifdef LSRA_DEBUG
+ printf("Alloc Flt\n");
+#endif
+ lsra_alloc(m, rd, flt_lt,&lsra_mem_use);
+
+#ifdef LSRA_DEBUG
+ printf("Int RA complete \n");
+ printf("Lifetimes after splitting int: \n");
+ print_lifetimes(rd, int_lt);
+
+ printf("Flt RA complete \n");
+ printf("Lifetimes after splitting flt:\n");
+ print_lifetimes(rd, flt_lt);
+
+ printf("Rest RA complete \n");
+ printf("Lifetimes after leftt:\n");
+ print_lifetimes(rd, ls->lifetimes);
+#endif
+
+ rd->maxmemuse=lsra_mem_use;
+}
+
+void lsra_alloc(methodinfo *m, registerdata *rd, struct lifetime *lifet, int *mem_use)
+{
+ int flags,regoff;
+ struct lifetime *lt;
+ struct freemem *fmem;
+ struct stackslot *n;
+
+ fmem=DNEW(struct freemem);
+ fmem->off=-1;
+ fmem->next=NULL;
+
+ for (lt=lifet;lt!=NULL;lt=lt->next) {
+#ifdef LSRA_MEMORY
+ lt->reg=-1;
+#endif
+ if (lt->reg==-1) {
+ flags=INMEMORY;
+
+ regoff=lsra_getmem(lt, fmem, mem_use);
+ } else {
+ flags=lt->savedvar;
+ regoff=lt->reg;
+ }
+
+ if (lt->v_index < 0) {
+ if (lt->s!=NULL) {
+ lsra_setflags( &(lt->s->flags), flags);
+ lt->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) {
+/* lsra_setflags( &(rd->locals[lt->v_index][lt->type].flags), flags); */
+ rd->locals[lt->v_index][lt->type].flags= flags;
+ rd->locals[lt->v_index][lt->type].regoff=regoff;
+ } else panic("Type Data mismatch 1\n");
+ }
+ }
+}
+
+void lsra_setflags(int *flags, int newflags)
+{
+ if ( newflags & INMEMORY)
+ *flags |= INMEMORY;
+ else
+ *flags &= ~INMEMORY;
+
+ if (newflags & SAVEDVAR)
+ *flags |= SAVEDVAR;
+}
+
+int lsra_getmem(struct lifetime *lt, struct freemem *fmem, int *mem_use)
+{
+ struct freemem *fm, *p;
+
+ /* noch kein Speicher vergeben, oder alle Enden später */
+ if ((fmem->next == NULL) || (fmem->next->end >= lt->i_start)) /* wirklich >= oder reicht > */
+ fm=lsra_getnewmem(mem_use);
+ 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;
+ return fm->off;
+}
+
+struct freemem *lsra_getnewmem(int *mem_use)
+{
+ struct freemem *fm;
+
+ fm=DNEW(struct freemem);
+ fm->next=NULL;
+ fm->off=*mem_use;
+ (*mem_use)++;
+ return fm;
+}
+
+void _lsra_main( methodinfo *m, lsradata *ls, struct lifetime *lifet, struct lsra_reg *reg, int tmp_reg_count, int sav_reg_count, int *mem_use, int *reg_use)
+{
+ struct lifetime *lt;
+/* struct active_lt *a; */
+ int i;
+ int _reg_use;
+ int reg_count, active_count;
+
+ if ((tmp_reg_count+sav_reg_count) == 0) {
+ for (lt=lifet; lt != NULL; lt=lt->next)
+ lt->reg=-1;
+ return;
+ }
+
+ ls->active_tmp = NULL;
+ ls->active_sav = NULL;
+ ls->active_tmp_count=0;
+ ls->active_sav_count=0;
+ for (lt=lifet; lt != NULL; lt=lt->next) {
+ lsra_expire_old_intervalls(ls, lt,reg);
+ if (lt->savedvar && (!m->isleafmethod)) {
+ reg_count=sav_reg_count;
+ active_count=ls->active_sav_count;
+ }
+ else {
+ reg_count=tmp_reg_count;
+ active_count=ls->active_sav_count+ls->active_tmp_count;
+ }
+ if (active_count == reg_count)
+ spill_at_intervall(ls, lt);
+ else {
+ for (i=reg_count-1;i>=0;i--) {
+ if (reg[i].use==0) {
+ reg[i].use=1;
+ lt->reg=reg[i].reg_index;
+ _reg_use=i;
+ if (_reg_use<*reg_use) *reg_use=_reg_use;
+ break;
+ }
+ }
+ if (i < sav_reg_count)
+ lsra_add_active(lt, &(ls->active_sav), &(ls->active_sav_count));
+ else
+ lsra_add_active(lt, &(ls->active_tmp), &(ls->active_tmp_count));
+ }
+ }
+}
+
+void lsra_add_active(struct lifetime *lt, struct active_lt **active, int *active_count)
+{
+ struct active_lt *alt,*alt1,*alt2;
+ alt=DNEW(struct active_lt);
+ alt->lt=lt;
+
+ for(alt1=alt2=*active; alt1 != NULL; alt2=alt1, alt1=alt1->next)
+ if (alt1->lt->i_end > lt->i_end) break;
+
+ if (alt1 == *active) {
+ alt->next = *active;
+ *active = alt;
+ } else {
+ alt->next = alt2->next;
+ alt2->next = alt;
+ }
+ (*active_count)++;
+}
+
+
+void lsra_expire_old_intervalls(lsradata *ls, struct lifetime *lt, struct lsra_reg *reg)
+{
+ _lsra_expire_old_intervalls(lt, reg, &(ls->active_tmp), &(ls->active_tmp_count));
+ _lsra_expire_old_intervalls(lt, reg, &(ls->active_sav), &(ls->active_sav_count));
+}
+
+void _lsra_expire_old_intervalls(struct lifetime *lt, struct lsra_reg *reg, struct active_lt **active, int *active_count)
+{
+ struct active_lt *alt,*alt1;
+ int i;
+
+ for (alt1=alt=*active; alt != NULL; alt1=alt, alt=alt->next) {
+ if (alt->lt->i_end >= lt->i_start) return;
+ if (alt == *active)
+ *active = (*active)->next;
+ else
+ alt1->next=alt->next;
+
+ for (i=0;reg[i].reg_index != alt->lt->reg;i++);
+ reg[i].use=0;
+/* FREE(alt,struct active_lt); */
+ (*active_count)--;
+ }
+}
+
+void spill_at_intervall(lsradata *ls, struct lifetime *lt )
+{
+ if (lt->savedvar)
+ _spill_at_intervall(lt, &(ls->active_sav), &(ls->active_sav_count));
+ else {
+ _spill_at_intervall(lt, &(ls->active_tmp), &(ls->active_tmp_count));
+ if (lt->reg == -1) /* kein tmp mehr frei gewesen */
+ _spill_at_intervall(lt, &(ls->active_sav), &(ls->active_sav_count));
+ }
+ if (lt->reg == -2) panic("spill_at_intervall: Keine Register mehr frei gewesen!\n");
+}
+
+void _spill_at_intervall(struct lifetime *lt, struct active_lt **active, int *active_count)
+{
+ struct active_lt *alt,*alt1;
+ if (*active == NULL) {
+ lt->reg=-2;
+ return;
+ panic("No Lifetime in Active List -> no free registers at all!\n");
+ }
+ /* get last intervall from active */
+ for (alt1=alt=*active; alt->next != NULL; alt1=alt, alt=alt->next);
+
+ if (alt->lt->i_end > lt->i_end) {
+ lt->reg=alt->lt->reg;
+ alt->lt->reg=-1;
+
+ if (alt == *active)
+ *active=(*active)->next;
+ else
+ alt1->next=alt->next;
+ /* FREE(alt,struct active_lt); */
+ (*active_count)--;
+ lsra_add_active(lt, active, active_count);
+ } else {
+ lt->reg=-1;
+ }
+}
+
+int lsra_getmaxblock(methodinfo *m, loopdata *ld, int bb_start)
+{
+ int i, *blocks;
+ int finished;
+ struct depthElement *hp;
+ int bb_max;
+
+ blocks=DMNEW(int, m->basicblockcount);
+ /* ExTable Ablauf kann in die STD Code BB wieder "hineinspringen" */
+ /* -> deshalb */
+ /* TODO vorher alle "normalen" BB mit 2=bereits besucht initialisieren */
+ bb_max=0;
+
+ for (i=0; i<m->basicblockcount; i++) blocks[i]=-1;
+
+ blocks[bb_start]=1;
+
+ finished=0;
+ while (!finished) {
+ finished=1;
+ for (i=0; i<m->basicblockcount; i++) {
+
+ if (blocks[i] == 1) {
+ if (i > bb_max) bb_max = i;
+ blocks[i]=2; /* visited */
+ for (hp=ld->c_dTable[i]; hp!=NULL; hp=hp->next) {
+ if (blocks[hp->value] != 2) {
+ blocks[hp->value]=1; /* to visit */
+ finished=0;
+ }
+ }
+ }
+ }
+ }
+#ifdef LSRA_DEBUG
+ printf("ExTable searching: BB_MAX %3i ",bb_max);
+ for (i=0; i<m->basicblockcount; i++)
+ if (blocks[i] != -1) printf("%3i ",i);
+ printf("\n");
+#endif
+ return bb_max;
+}
+
+
+void lsra_calc_lifetime_length(methodinfo *m, lsradata *ls, codegendata *cd, loopdata *ld)
+{
+ struct lifetime *lt;
+ struct _i_list *il;
+ struct l_loop *loops;
+ struct b_loop *block_loop;
+ exceptiontable *ex;
+ int *exh_max; /* Exception Handler End BB */
+ int *exh_min; /* Exception Handler Start BB */
+ int *ex_max; /* Exception guarded Area End BB */
+ int *ex_min; /* Exception guarded Area Start BB */
+
+ int blast,bfirst,ilast,ifirst,usage;
+
+ int i, j, num_loops;
+ struct LoopContainer *lc;
+ struct LoopElement *le;
+
+ /**********/
+ /* Todo: */
+ /* Für Exceptionhandler Blocks wurde keine Loop Analyse durchgeführt! */
+ /* -> deshalb vorerst die einzelnen Handler als eine Loop eintragen */
+ /* oder loop analyse extra für jeden Handler aufrufen */
+ /**/
+ /* lifetime der Vars des ExHandlers über guarded Bereich ausdehnen! */
+ /**/
+ /* Falls die einzelnen Blöcke einer Loop nicht durchgehend nummeriert sind */
+ /* auch nicht alle in block_loop eintragen! */
+
+ exh_max = DMNEW(int, cd->exceptiontablelength);
+ exh_min = DMNEW(int, cd->exceptiontablelength);
+ ex_max = DMNEW(int, cd->exceptiontablelength);
+ ex_min = DMNEW(int, cd->exceptiontablelength);
+
+ /* BB der Exhandler bestimmen + BB der guarded Area hinzu */
+ ex = cd->exceptiontable;
+ for (i=0; ex != NULL; i++,ex = ex->down) {
+ if (ex->handler == NULL) {
+#ifdef LSRA_DEBUG
+ printf("lsra_init_blocks EXCEPTIONTABLE without handler!\n");
+#endif
+ } else {
+ if ((ex->handler->debug_nr < 0) || (ex->handler->debug_nr >= m->basicblockcount)) {
+#ifdef LSRA_DEBUG
+ printf("lsra_init_blocks EXCEPTIONTABLE Handler Blocknummer invalid! %i\n", ex->handler->debug_nr);
+#endif
+ } else {
+ exh_min[i]=ex->handler->debug_nr;
+ exh_max[i]=lsra_getmaxblock(m, ld, ex->handler->debug_nr);
+
+ ex_min[i]=ex->start->debug_nr;
+ ex_max[i]=ex->end->debug_nr;
+#ifdef LSRA_DEBUG
+ printf("EX %3i exmin %3i exmax %3i exhmin %3i exhmax %3i\n",i,ex_min[i],ex_max[i],exh_min[i],exh_max[i]);
+#endif
+ }
+ }
+ }
+
+ /* extend lifetime within loops */
+
+
+ for (num_loops=0,lc =ld->c_allLoops;lc!=NULL;num_loops++,lc=lc->next);
+
+ loops=DMNEW(struct l_loop,num_loops);
+
+ for (i=0,lc=ld->c_allLoops;i<num_loops;i++,lc=lc->next) {
+
+ le = lc->nodes;
+ bfirst=m->basicblockcount;
+ blast=0;
+ while (le != NULL) {
+ if (le->node<bfirst) bfirst=le->node;
+ if (le->node>blast) blast=le->node;
+ le = le->next;
+ }
+ loops[i].b_first=bfirst;
+ loops[i].b_last=blast;
+ loops[i].nesting=0;
+ }
+
+/* for (i=0;i<num_loops;i++) printf("loops[%2i] bfirst: %3i blast %3i nesting %3i\n",i,loops[i].b_first,loops[i].b_last,loops[i].nesting); */
+
+ /* sort loops by b_first desc*/
+ for (i=0; i<num_loops-1;i++) {
+ for (j=i+1; j<num_loops;j++) {
+ if (loops[i].b_first < loops[j].b_first) {
+ bfirst=loops[j].b_first;
+ blast=loops[j].b_last;
+ loops[j].b_first=loops[i].b_first;
+ loops[j].b_last=loops[i].b_last;
+ loops[i].b_first=bfirst;
+ loops[i].b_last=blast;
+ }
+ }
+ }
+/* for (i=0;i<num_loops;i++) printf("loops[%2i] bfirst: %3i blast %3i nesting %3i\n",i,loops[i].b_first,loops[i].b_last,loops[i].nesting); */
+ /* check for nesting_level, overlapping */
+ for (i=0; i<num_loops-1;i++) {
+ /*! loops[i].b_first >= loops[i+1].b_first !*/
+ if (loops[i+1].b_last>=loops[i].b_first) {
+ if (loops[i+1].b_last<loops[i].b_last) {
+ /* overlapping -> make one loop of both */
+ loops[i+1].b_last=loops[i].b_last;
+ loops[i].b_first=-1;
+ loops[i].b_last=-1;
+ } else {
+ /* nested loops */
+ loops[i].nesting++; /* only boolean if nested... */
+ }
+ }
+ }
+/* for (i=0;i<num_loops;i++) printf("loops[%2i] bfirst: %3i blast %3i nesting %3i\n",i,loops[i].b_first,loops[i].b_last,loops[i].nesting); */
+
+ block_loop=DMNEW(struct b_loop, m->basicblockcount);
+ for (i=0;i<m->basicblockcount; i++) {
+ block_loop[i].loop=-1;
+ if (i!=0)
+ block_loop[i].instr=block_loop[i-1].instr+m->basicblocks[i-1].icount;
+ else
+ block_loop[i].instr=0;
+ }
+
+ for (i=0; i<num_loops;i++) {
+ if (loops[i].b_first!=-1) {
+ /* valid loop */
+ for (j=loops[i].b_first;j<=loops[i].b_last;j++) block_loop[j].loop=i;
+ }
+ }
+
+ lt=ls->lifetimes;
+ while(lt!=NULL) {
+
+ if (ls->back_edge_panic) {
+ lt->b_start=0;
+ lt->i_start=0;
+ lt->b_end=m->basicblockcount-1;
+ lt->i_end=block_loop[m->basicblockcount-1].instr+m->basicblocks[m->basicblockcount-1].icount;
+ } else {
+ usage = 0;
+ il=lt->i_list;
+ blast=il->b_index;
+ ilast=il->instr;
+ while (il->next!=NULL) {
+ il=il->next;
+ usage++;
+ }
+ bfirst=il->b_index;
+ ifirst=il->instr;
+ /* expand lifetimes in a exceptionhandler to at least the whole handler */
+ /* TODO do a loop analyze for the exceptionhandler, too*/
+ for (i=0; i < cd->exceptiontablelength; i++) {
+
+ if ( !((bfirst > exh_max[i]) || ( blast < exh_min[i])) ) {
+ /* Ãœberschneidung mit exh_???[i]-> lt liegt in Exceptionhandler */
+ /* -> Start auf mindestens die erste Instruktion des geschützten Bereiches legen */
+ if (bfirst >= exh_min[i]) {
+ bfirst=exh_min[i];
+ ifirst=0;
+ }
+ /* -> Ende auf mindestens die letzte Instruktion des geschützten Bereiches legen */
+ if (blast <= exh_max[i]) {
+ blast=exh_max[i];
+ ilast= m->basicblocks[exh_max[i]].icount-1;
+ }
+ }
+ }
+
+ ilast+=block_loop[blast].instr;
+ ifirst+=block_loop[bfirst].instr;
+
+ if ((j=block_loop[bfirst].loop)==-1)
+ j=block_loop[blast].loop;
+
+ if (j!=-1) {
+ if (loops[j].b_first<=bfirst) {
+ bfirst=loops[j].b_first;
+ ifirst=block_loop[bfirst].instr;
+ usage+=loops[j].nesting*100;
+ }
+ if (blast <= loops[j].b_last) {
+ blast=loops[j].b_last;
+ ilast=block_loop[blast].instr+m->basicblocks[blast].icount;
+ usage+=loops[j].nesting*100;
+ }
+ }
+
+ lt->length=ilast-ifirst;
+
+ lt->b_start=bfirst;
+ lt->b_end=blast;
+ lt->i_start=ifirst;
+ lt->i_end=ilast;
+ lt->usagecount=usage;
+ }
+ lt=lt->next;
+ }
+
+#ifdef LSRA_DEBUG
+ for (i=0; i<num_loops;i++) {
+ printf("LoopNR: %3i Start: %3i End: %3i Nesting: %3i Block_loop[%3i]:",i,loops[i].b_first,loops[i].b_last,loops[i].nesting,i);
+ for (j=0;j<m->basicblockcount;j++)
+ if (block_loop[j].loop==i) printf(" %3i",j);
+ printf("\n");
+ }
+#endif
+}
+
+void lsra_sort_lt(struct lifetime **lifet)
+{
+ /* sort lifetimes by increasing start point */
+/* struct lifetime **plt,**plt1; */
+ struct lifetime *lt, lt_new, *temp, *tmp;
+/* int swapped; */
+
+ /* lifetimes are sorted by decreasing start point -> just turn around */
+ /* not really correct through exception and loop lifetime expansion! -> turn around and sort in*/
+ lt_new.next=NULL;
+
+ for (lt=*lifet; lt!= NULL;) {
+ temp=lt->next;
+
+ for(tmp=<_new; (tmp->next!= NULL) && (tmp->next->i_start < lt->i_start); tmp=tmp->next);
+ lt->next=tmp->next;
+ tmp->next=lt;
+ lt=temp;
+ }
+ *lifet=lt_new.next;
+}
+
+
+void print_lifetimes(registerdata *rd, struct lifetime *lt)
+{
+ struct lifetime *n;
+ struct _i_list *ni;
+ int type,flags,regoff,j,varkind;
+/* int i; */
+
+ for (n=lt,j=0; n!=NULL; n=n->next,j++) {
+ if (n->v_index < 0) { /* stackslot */
+ if (n->s != 0) { /* stackslot */
+ type = n->s->type;
+ flags=n->s->flags;
+ regoff=n->s->regoff;
+ varkind=n->s->varkind;
+ } else {
+ if (n->local_ss != 0) {
+ type = n->local_ss->s->type;
+ flags=n->local_ss->s->flags;
+ regoff=n->local_ss->s->regoff;
+ varkind=n->local_ss->s->varkind;
+ }
+ }
+ } else { /* local var */
+/* for (i=TYPE_INT; i<=TYPE_ADR; i++) { */
+ if (rd->locals[n->v_index][n->type].type>=0) {
+ type = rd->locals[n->v_index][n->type].type;
+ flags=rd->locals[n->v_index][n->type].flags;
+ regoff=rd->locals[n->v_index][n->type].regoff;
+ varkind=-1;
+ } else panic("Type Data mismatch 3\n");
+/* } */
+ }
+ printf("i_Start: %3i i_stop: %3i reg: %3i Index: %3i VI: %3i Usage: %3i length: %3i type: %3i flags: %3i varkind: %3i ILst: ",n->i_start,n->i_end,regoff,n->index,n->v_index,n->usagecount, n->length,type,flags, varkind);
+ for (ni=n->i_list; ni!=NULL; ni=ni->next) {
+ if (ni==ni->next) panic("loop in instruction list!\n");
+ printf( "(%3i,%3i) ",ni->b_index,ni->instr);
+ }
+ printf("\n");
+/* if (n->s!=NULL) */
+/* printf(" type: %1i flags: %1i varkind: %1i varnum: %3i regoff: %4i\n",n->s->type,n->s->flags,n->s->varkind,n->s->varnum,n->s->regoff); */
+ }
+ printf( "%3i Lifetimes printed \n",j);
+}
+
+struct stackslot *lsra_make_ss(stackptr s, int bb_index)
+{
+ struct stackslot *ss;
+
+ ss=DNEW(struct stackslot);
+ ss->bb=bb_index;
+ ss->s=s;
+ return ss;
+}
+
+/* merge i_list from lt1 to lt in order */
+void lsra_merge_i_lists(struct lifetime *lt, struct lifetime *lt1)
+{
+ struct _i_list *iptr, *iptr1, *iptr2;
+
+ /* merge i_lists in order */
+ iptr=lt->i_list;
+ iptr2=lt->i_list=NULL;
+ iptr1=lt1->i_list;
+ while ((iptr != NULL) && (iptr1 != NULL)) {
+ if ((iptr->b_index > iptr1->b_index)|| ((iptr->b_index == iptr1->b_index) && (iptr->instr > iptr1->instr))) {
+ if (lt->i_list==NULL) {
+ lt->i_list=iptr;
+/* iptr2=lt->i_list; */
+ } else {
+ iptr2->next=iptr;
+ }
+ iptr2=iptr;
+ iptr=iptr->next;
+ } else {
+ if (lt->i_list==NULL) {
+ lt->i_list=iptr1;
+/* iptr2=lt->i_list; */
+ } else {
+ iptr2->next=iptr1;
+ }
+ iptr2=iptr1;
+ iptr1=iptr1->next;
+ }
+ }
+#ifdef LSRA_DEBUG
+ if (iptr2 == NULL) panic("lsra_merge_i_lists: Empty Instruction List in Lifetime\n");
+#endif
+ if (iptr==NULL)
+ iptr2->next=iptr1;
+ if (iptr1==NULL)
+ iptr2->next=iptr;
+}
+
+#ifdef LSRA_DEBUG
+void dump_join( struct lifetime *lt_passing)
+{
+ struct lifetime *lt;
+ struct stackslot *ss;
+ int i;
+
+ for (lt=lt_passing,i=0; lt != NULL; lt=lt->next, ++i) {
+ printf("Lifetime(%2i)\n PT: ",i);
+ for ( ss=lt->passthrough; ss!=NULL; ss=ss->next)
+ printf("(%2i, %2i, %6p) ",ss->bb, ss->s->varnum, ss->s);
+ printf("\n SS: ");
+ for (ss = lt->local_ss; ss!=NULL; ss=ss->next)
+ printf("(%2i, %2i, %6p) ", ss->bb, ss->s->varnum, ss->s);
+ printf("\n");
+ }
+}
+#endif
+
+void lsra_join_lifetimes(methodinfo *m, codegendata *cd, lsradata *ls, loopdata *ld)
+{
+ int i, j, index, stacks_top;
+ int in1, out1, in2, out2, temp;
+ struct depthElement *de;
+
+ int *in_stacks, *out_stacks;
+ stackptr out, s;
+ struct stackslot **stacks, *ss, *ss_new;
+ struct lifetime *lt, *lt_prev, *lt_new, *lt_passing;
+ struct stackslot *p, *q, *r;
+ bool drop;
+
+#ifdef LSRA_DEBUG
+ stackptr in;
+
+ in=m->basicblocks[0].instack; /* ?falls Instack des Startblocks != leer ?*/
+ if (in != NULL) printf("------------ Instack von BB0 nicht leer! -------\n");
+#endif
+
+ /* join copies of dup/swap? or let just codegen copy the contents? */
+ /* -> ?TODO? save at ICMD_DUP* and ICMD_SWAP Copy Info */
+
+ /* out_stacks hold an index to stacks, which holds the joined stacks */
+ /* in_stacks hold an index to out_stacks, with which they are joined */
+ /* an initial index of -1 mark, that they where not visited yet */
+ in_stacks = DMNEW(int, m->basicblockcount);
+ out_stacks = DMNEW(int, m->basicblockcount);
+ stacks = DMNEW(struct stackslot *, m->basicblockcount);
+/* for (i=0; i< m->basicblockcount; i++) stacks[i]=NULL; */
+ for (i=0; i < m->basicblockcount; i++ ) in_stacks[i]=out_stacks[i]=-1;
+ stacks_top=0;
+
+ for (i=0; i < m->basicblockcount; i++)
+ if (m->basicblocks[i].flags >= BBREACHED) {
+ if ((out=m->basicblocks[i].outstack) != NULL) {
+ ss=lsra_make_ss(out, i);
+ ss->next=NULL;
+ stacks[stacks_top]=ss;
+ out_stacks[i]=stacks_top++;
+ for (de=ld->c_dTable[i]; de != NULL; de=de->next) {
+ if (in_stacks[de->value] == -1) { /* not visited==joined yet */
+ in_stacks[de->value] = i;
+ ss=lsra_make_ss(m->basicblocks[de->value].instack, de->value);
+ ss->next=stacks[out_stacks[i]];
+ stacks[out_stacks[i]]=ss;
+ } else { /* in stacks already joined -> join with others */
+ /* join this outstack to index in_stack[de->value] points to */
+ for (ss=stacks[out_stacks[i]]; ss->next != NULL; ss=ss->next); /* get last element */
+ ss->next=stacks[out_stacks[in_stacks[de->value]]];
+ stacks[out_stacks[in_stacks[de->value]]]=stacks[out_stacks[i]];
+ stacks[out_stacks[i]]=NULL;
+ /* update all prior out_stacks indexes to this new join */
+ for (j=0; j <= i; j++) {
+ if (out_stacks[j] == out_stacks[i]) {
+ out_stacks[j]=out_stacks[in_stacks[de->value]];
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /* leere einträge aus stacks entfernen */
+ for (i=index=0; i< stacks_top;) {
+ if (stacks[index]!=NULL) { /* nächsten freien Platz suchen */
+ ++index;
+ ++i;
+ } else {
+ if (stacks[i]==NULL) { /* nächsten bestetzten Platz zum verschieben suchen*/
+ ++i;
+ } else { /* von i nach index umhängen */
+ stacks[index]=stacks[i];
+ stacks[i]=NULL;
+ ++index;
+ }
+ }
+ }
+
+ lt_passing=NULL;
+ /* 0 <= i < index | join all corresponding stackslots of in- and outstacks of stacks[i] to lt_new */
+ /* and put lt_new in lt_passing (if passthrough ss exist in them) or ls->lifetimes */
+ for (i=0; i < index; i++) {
+ while (stacks[i]->s != NULL) {
+ lt_new=NULL;
+ for (ss=stacks[i]; ss!=NULL; ss=ss->next) {
+ /* search stackslot ss->s lifetimelist of basicblock(ss->bb) (ss_lifetimes) */
+ /* remember the link before found lifetime, to remove it afterwards */
+ for (lt_prev=lt=ls->ss_lifetimes[ss->bb]; (lt!=NULL) && (lt->s != ss->s); lt_prev=lt, lt=lt->next);
+#ifdef LSRA_DEBUG
+ if (lt==NULL) panic("lsra_join_lifetimes error in lifetimelist\n");
+#endif
+ /* Remove found lifetime from Block Stackslot Lifetimelist */
+ if (lt==ls->ss_lifetimes[ss->bb]) {
+ ls->ss_lifetimes[ss->bb]=lt->next;
+ } else {
+ lt_prev->next=lt->next;
+ }
+ lt->next=NULL;
+
+ drop = false;
+ if (lt->i_list->instr==-1) {
+ if (out_stacks[in_stacks[ss->bb]] == out_stacks[ss->bb]) {
+ /* Throughpassing Basicblock is already in one "join Group" */
+ /* If this stackslot (lt->s == ss->s) is already in lt_new->local_ss */
+ /* do not add it a second time! */
+ if (lt_new != NULL) {
+ for (ss_new=lt_new->local_ss; (ss_new != NULL) && (ss_new->s != lt->s); ss_new = ss_new->next);
+ if (ss_new != NULL) drop = true;
+ }
+ }
+ }
+ if (!drop) {
+ lt->s->varkind=TEMPVAR; /* no LOCALVAR, ARGVAR or STACKVAR with joined lifetimes */
+ lt->v_index=-1; /* not a local var */
+
+ /* join Lifetime lt to lt_new */
+ if (lt_new == NULL) {
+ lt_new = lt;
+ lt_new->passthrough = NULL;
+ lt_new->s = NULL; /* Stackslots are all in local_ss for joined lifetimes */
+ } else
+ lsra_merge_i_lists( lt_new, lt);
+
+ /* add stackslot to local_ss of lt_new */
+ ss_new = DNEW(struct stackslot);
+ ss_new->s = ss->s;
+ ss_new->bb = ss->bb; /* for debugging only, has no further use */
+ ss_new->next = lt_new->local_ss;
+ lt_new->local_ss = ss_new;
+
+ lt_new->savedvar |= (lt->savedvar & SAVEDVAR);
+
+
+ if (lt->i_list->instr==-1) {
+ /* BB passes this stackslot through -> join later with other side!*/
+ if (out_stacks[in_stacks[ss->bb]] != out_stacks[ss->bb]) {
+ /* Stackslot ist not passed through to same (this) "join group" */
+
+ p = DNEW(struct stackslot);
+ p->bb = ss->bb; /* Basic Block index of joined Lifetime */
+ p->s = ss->s;
+ /* sort p in lt_new->passthrough list by increasing stackslot adress */
+ /* there are no two stackslots allowed, which "join" the same "join groups" */
+ /* in case one has to be dropped, keep the one with the "greater" address */
+ r = NULL;
+ drop = false;
+ in2=out_stacks[in_stacks[p->bb]];
+ out2=out_stacks[p->bb];
+ if (in2 > out2) { temp=in2; in2=out2; out2=temp; }
+ for (q=lt_new->passthrough; (q != NULL);) {
+ in1=out_stacks[in_stacks[q->bb]];
+ out1=out_stacks[q->bb];
+ if (in1 > out1) { temp=in1; in1=out1; out1=temp; }
+
+ if ((in1 == in2) && (out1 == out2)) { /* p->s would join to same group -> drop the one with the lower address */
+ if (p->s < q->s) /* drop p->s, it has the lower address */
+ drop = true;
+ else { /* drop q from the list, since it has the lower address */
+ if (q == lt_new->passthrough ) {
+ lt_new->passthrough=q->next;
+ q=q->next;
+ } else { /* r points to the previous element */
+ r->next=q->next;
+ }
+ }
+ }
+ if (q != NULL) {
+ if (q->s < p->s)
+ r=q; /* remember position for sorting p in */
+ q=q->next;
+ }
+ }
+ if (!drop) {
+ if (r == NULL) {
+ /* List Empty or all elements greater than p->s */
+ p->next=lt_new->passthrough;
+ lt_new->passthrough=p;
+ } else {
+ p->next=r->next;
+ r->next=p;
+ }
+ }
+ }
+ }
+ }
+ ss->s=ss->s->prev; /* Next Stackslot for next Iteration */
+ } /*for */
+ if (lt_new->passthrough != NULL) {
+ lt_new->next=lt_passing;
+ lt_passing=lt_new;
+ } else {
+ lt_new->next=ls->lifetimes;
+ ls->lifetimes=lt_new;
+ }
+ }/* while */
+ } /* for */
+
+ /* join lifetimes with same stackslots in ->passthrough in lt_passing */
+ for (lt=lt_passing; lt != NULL; lt=lt->next) {
+ while (lt->passthrough != NULL) {
+#ifdef LSRA_DEBUG
+ printf("before \n");
+ dump_join(lt_passing);
+#endif
+ s=lt->passthrough->s;
+ lt->passthrough=lt->passthrough->next; /* drop this stackslot from lt_passthrough list */
+ /* search for next lifetime, which has the same stackslot in passthrough */
+ /* lt_new->next will point to it */
+ /* there has to be another lifetime after lt with same s in passthrough */
+ for (lt_new=lt; (lt_new->next != NULL); lt_new=lt_new->next) {
+ /* passthrough is sorted by increasing address of s */
+ /* remember in q the list element before p with p->s == s */
+ for (p=lt_new->next->passthrough; (p!=NULL) && (p->s < s); q=p,p=p->next);
+ if ((p != NULL) && (p->s == s)) {
+ /* found -> now drop this stackslot from lt_new's passtrough list */
+ if (p == lt_new->next->passthrough) { /* first element in list */
+ lt_new->next->passthrough = lt_new->next->passthrough->next;
+ } else
+ q->next=p->next;
+ break;
+ }
+ }
+#ifdef LSRA_DEBUG
+ if (lt_new->next==NULL)
+ panic("lsra_join_lifetimes error in lt_passing lifetimelist\n");
+#endif
+ /* join lt and lt_new->next to lt */
+ lt->savedvar |= (lt_new->next->savedvar & SAVEDVAR);
+
+ /* join local_ss lists */
+#ifdef LSRA_DEBUG
+ if (lt_new->next->local_ss == NULL)
+ panic("lsra_join_lifetimes Lifetime without stackslot\n");
+#endif
+ for (ss=lt_new->next->local_ss; (ss->next != NULL); ss=ss->next);
+ ss->next=lt->local_ss;
+ lt->local_ss=lt_new->next->local_ss;
+
+ /* merge i_lists in order */
+ lsra_merge_i_lists(lt, lt_new->next);
+
+ /* join passthrough lists in ascending order */
+ /* if there are duplicates, it happened that a join was done through the */
+ /* other joins till now, so just drop both of them */
+ p=lt->passthrough;
+ q=lt_new->next->passthrough;
+ lt->passthrough=NULL;
+ ss=NULL; /* pointer to the end of lt->passthrough */
+ while ( (p!=NULL) && (q!=NULL) ) {
+ if (p->s > q->s) {
+ if (ss==NULL) {
+ lt->passthrough=q;
+ } else {
+ ss->next=q;
+ }
+ ss=q;
+ q=q->next;
+ } else {
+ if (q->s == p->s) {
+ /* Drop both stackslots -> they where just joined through some other joins */
+ q=q->next;
+ p=p->next;
+ } else {
+ /* p->s < q->s */
+ if (ss==NULL) {
+ lt->passthrough=p;
+ } else {
+ ss->next=p;
+ }
+ ss=p;
+ p=p->next;
+ }
+ }
+ }
+ if (q == NULL) {
+ if (lt->passthrough == NULL)
+ lt->passthrough=p;
+ else
+ ss->next = p;
+ }
+ if (p == NULL) {
+ if (lt->passthrough == NULL)
+ lt->passthrough=q;
+ else
+ ss->next = q;
+ }
+ lt_new->next=lt_new->next->next; /* throw away joined lifetime lt_new->next */
+#ifdef LSRA_DEBUG
+ printf("after\n");
+ dump_join(lt_passing);
+#endif
+ } /* while */
+ } /* for */
+
+ if (lt_passing!=NULL) {
+ for (lt=lt_passing; (lt->next!=NULL); lt=lt->next);
+ lt->next=ls->lifetimes;
+ ls->lifetimes=lt_passing;
+ }
+}
+
+
+struct _i_list *lsra_add_i_list(struct _i_list *i_list, int instr, int b_index, int store)
+{
+ struct _i_list *n;
+
+ n=DNEW(struct _i_list);
+ n->instr=instr;
+ n->b_index=b_index;
+ n->store=store;
+ n->next=i_list;
+ return n;
+}
+
+void lsra_add_ss(struct lifetime *lt, stackptr s) {
+ struct stackslot *ss;
+ /* Stackslot noch nicht eingetragen? */
+ if ((lt->local_ss==NULL) || (lt->local_ss->s != s)) {
+ ss = DNEW(struct stackslot);
+ ss->s = s;
+ ss->next = lt->local_ss;
+ lt->local_ss = ss;
+ if (s != NULL) lt->savedvar |= s->flags & SAVEDVAR;
+ }
+}
+
+#define lsra_new_stack(ls, s, block, instr) _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;
+
+ n=DNEW(struct lifetime);
+
+ n->index=s->varnum;
+ n->savedvar = (s->flags & SAVEDVAR);
+ n->s=s;
+ n->usagecount=1;
+ if (n->s->varkind == LOCALVAR)
+ n->v_index=n->s->varnum;
+ else
+ n->v_index=-1;
+ n->i_list=NULL;
+ n->local_ss=NULL;
+
+ n->next=ls->ss_lifetimes[block];
+ ls->ss_lifetimes[block]=n;
+
+ n->i_list=lsra_add_i_list(n->i_list, instr, block, store);
+}
+
+#define lsra_from_stack(ls, s, block, instr) _lsra_from_stack(ls, s, block, instr, LSRA_LOAD)
+#define lsra_pop_from_stack(ls, s, block, instr) _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;
+
+ for (n=ls->ss_lifetimes[block]; (n!=NULL) && (n->s!=s);n=n->next);
+ if (n==NULL) {
+ _lsra_new_stack(ls, s, block, instr, store);
+ /* ist mit dem neuen joinen hinterher immer so, wenn ein Stackslot in einen BB "reinkommt" */
+/* printf("type %i flags %i varkind %i varnum %i regoff %i \n",s->type,s->flags ,s->varkind ,s->varnum ,s->regoff); */
+/* panic("lsra_from_stack: Var on Stack not found"); */
+ } else {
+ n->usagecount++;
+ n->i_list=lsra_add_i_list(n->i_list, instr, block, store);
+ }
+}
+
+void lsra_usage_local(lsradata *ls, s4 v_index, int type, int block, int instr, int store)
+{
+ struct lifetime *n;
+
+ /* Lifetime vom richtigen Type suchen */
+ for (n=ls->locals_lifetimes[v_index]; (n!=NULL) && (n->type!=type);n=n->next);
+
+ if (n==NULL) {
+#ifdef LSRA_DEBUG
+ if (store != LSRA_STORE) printf("lsra_local_store: Read before write Local var: %i paramcount: ?\n", v_index);
+#endif
+ lsra_new_local(ls, v_index, type);
+ /* neue Lifetimes werden immer am Anfang der Liste eingehängt */
+ n=ls->locals_lifetimes[v_index];
+ }
+ /* add access at (block, instr) to intruction list */
+ n->i_list=lsra_add_i_list(n->i_list, instr, block, store);
+ n->usagecount++;
+}
+
+void lsra_new_local(lsradata *ls, s4 v_index, int type)
+{
+ struct lifetime *n;
+
+ n=DNEW(struct lifetime);
+ n->local_ss=NULL;
+ n->i_list=NULL;
+ n->index=v_index;
+ n->v_index=v_index;
+ n->s=NULL;
+ n->type=type;
+ n->usagecount=0;
+ n->savedvar = SAVEDVAR;
+
+ n->next=ls->locals_lifetimes[v_index];
+ ls->locals_lifetimes[v_index]=n;
+}
+
+#ifdef LSRA_DEBUG
+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);
+ s=s->prev;
+ }
+ printf("\n");
+}
+#endif
+
+void lsra_scan_registers_canditates(methodinfo *m, lsradata *ls)
+{
+ int i;
+ int opcode;
+ int iindex;
+ int len;
+ stackptr src;
+ stackptr dst;
+ instruction *iptr;
+ stackptr in,out;
+ int id, od;
+
+ int b_index;
+
+ b_index=0;
+ while (b_index < m->basicblockcount ) {
+
+ if (m->basicblocks[b_index].flags >= BBREACHED) {
+ dst = m->basicblocks[b_index].instack;
+ if (dst != NULL) { /* create Lifetimes for pass-through Stackslots */
+ in=m->basicblocks[b_index].instack;
+ id=m->basicblocks[b_index].indepth;
+ if (m->basicblocks[b_index].type != BBTYPE_STD) {
+ /* Pay attention to the top Stackslot in BBTYPE_EXH and BBTYPE_SBR Basicblocks */
+ /* this is not a passthrough, but set from the "system" to the exception object or */
+ /* the return adress -> just create a lifetime with a write at instr==0 */
+ lsra_new_stack(ls, in, b_index, 0);
+ in=in->prev;
+ --id;
+ }
+
+ out=m->basicblocks[b_index].outstack;
+ od=m->basicblocks[b_index].outdepth;
+
+ /* ignore all in-stackslots not in outstack */
+ for (;id>od; in=in->prev, --id);
+ /* ignore all out-stackslots not in instack */
+ for (;od>id; out=out->prev, --od);
+ /* ignore all non equal stackslots from in and outstack */
+ for (;in != out; in=in->prev, out=out->prev, --id);
+ /* set up a lifetime for the rest: */
+ /* stackslot adress equal, stackslot"number" equal */
+ for (;in!=NULL; in=in->prev) {
+ /* Make 2 entries -> one for the instack, one for the out stack */
+ lsra_new_stack(ls, in, b_index, -1);
+ lsra_new_stack(ls, in, b_index, -1);
+ /* } */
+ }
+ }
+ iptr = m->basicblocks[b_index].iinstr;
+ len = m->basicblocks[b_index].icount;
+ iindex=0;
+
+ while (iindex<len) {
+ src = dst;
+ dst = iptr->dst;
+ opcode = iptr->opc;
+#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
+ switch (opcode) {
+
+ case ICMD_RET:
+ lsra_usage_local(ls,iptr->op1,TYPE_ADR, b_index,iindex,LSRA_LOAD); /* local read (return adress) */
+
+ /* pop 0 push 0 */
+
+ case ICMD_NOP:
+ case ICMD_ELSE_ICONST:
+ case ICMD_CHECKEXCEPTION:
+ case ICMD_CHECKASIZE:
+ case ICMD_IINC:
+ case ICMD_JSR:
+ case ICMD_RETURN:
+ case ICMD_GOTO:
+ case ICMD_INLINE_START:
+ case ICMD_INLINE_END:
+ 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 */
+ lsra_new_stack(ls,dst,b_index,iindex); /* 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:
+ lsra_usage_local(ls,iptr->op1,opcode-ICMD_ILOAD, b_index,iindex,LSRA_LOAD); /* local->value */
+ lsra_new_stack(ls,dst,b_index,iindex); /* value->stack */
+ /* ?Reference to local var?-> attention if local var is changed */
+ 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:
+
+ lsra_new_stack(ls,dst,b_index,iindex); /* arrayref[index]->stack */
+ lsra_from_stack(ls, src,b_index,iindex); /* stack->index */
+ lsra_from_stack(ls, src->prev,b_index,iindex); /* stack->arrayref */
+ 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:
+
+ lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
+ lsra_from_stack(ls, src->prev,b_index,iindex); /* stack -> index */
+ lsra_from_stack(ls, src->prev->prev,b_index,iindex); /* stack -> arrayref */
+ break;
+
+ case ICMD_POP: /* throw away a stackslot -> check if used anyway! */
+ lsra_pop_from_stack(ls,src,b_index,iindex);
+ break;
+
+ /* pop 1 push 0 store */
+ /* stack -> local */
+
+ case ICMD_ISTORE:
+ case ICMD_LSTORE:
+ case ICMD_FSTORE:
+ case ICMD_DSTORE:
+ case ICMD_ASTORE:
+ lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
+ lsra_usage_local(ls,iptr->op1,opcode-ICMD_ISTORE, b_index,iindex,LSRA_STORE); /* 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 */
+
+ case ICMD_PUTSTATIC: /* stack(value) -> static_field */
+ /* 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_NULLCHECKPOP: /****** ????? -1 -> stack *********/
+ case ICMD_MONITORENTER:
+ case ICMD_MONITOREXIT:
+ lsra_from_stack(ls, src,b_index,iindex); /* stack -> value */
+ break;
+
+ /* pop 2 push 0 */
+
+ case ICMD_POP2: /* throw away 2 stackslots -> check if used anyway! */
+ lsra_pop_from_stack(ls,src,b_index,iindex);
+ lsra_pop_from_stack(ls,src->prev,b_index,iindex);
+ 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->method=value */
+
+ case ICMD_IASTORECONST:
+ case ICMD_LASTORECONST:
+ case ICMD_AASTORECONST:
+ case ICMD_BASTORECONST:
+ case ICMD_CASTORECONST:
+ case ICMD_SASTORECONST:
+ lsra_from_stack(ls, src,b_index,iindex); /* stack -> value*/
+ lsra_from_stack(ls, src->prev,b_index,iindex); /* stack -> objref*/
+ break;
+
+ /* pop 0 push 1 dup */
+ /* merge dupped vars??? */
+ case ICMD_DUP:
+ /* lsra_from_stack(ls, src,b_index,iindex);*/ /* inc usage_count! */
+/* dup_alignstackslots(src, dst); */
+ lsra_new_stack(ls,dst,b_index,iindex);
+ break;
+
+ /* pop 0 push 2 dup */
+
+ case ICMD_DUP2:
+ lsra_new_stack(ls,dst->prev,b_index,iindex);
+ lsra_new_stack(ls,dst,b_index,iindex);
+/* dup_alignstackslots(src, dst); */
+/* dup_alignstackslots(src->prev, dst->prev); */
+ lsra_from_stack(ls, src,b_index,iindex); /* or inc usage_count! */
+ lsra_from_stack(ls, src->prev,b_index,iindex); /* inc usage_count! */
+ break;
+
+ /* pop 2 push 3 dup */
+
+ case ICMD_DUP_X1:
+ lsra_from_stack(ls, src,b_index,iindex); /* from for to, or it will not work! inc usage_count! */
+ lsra_from_stack(ls, src->prev,b_index,iindex); /*from for to, or it will not work! inc usage_count! */
+/* dup_alignstackslots(src, dst); */
+/* dup_alignstackslots(src->prev, dst->prev); */
+/* dup_alignstackslots(src, dst->prev->prev); */
+ 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);
+ break;
+
+ /* pop 3 push 4 dup */
+
+ case ICMD_DUP_X2:
+ lsra_from_stack(ls, src,b_index,iindex); /* from for to, or it will not work! inc usage_count! */
+ lsra_from_stack(ls, src->prev,b_index,iindex); /*from for to, or it will not work! inc usage_count! */
+ lsra_from_stack(ls, src->prev->prev,b_index,iindex); /*from for to, or it will not work! inc usage_count! */
+/* dup_alignstackslots(src, dst); */
+/* dup_alignstackslots(src->prev, dst->prev); */
+/* dup_alignstackslots(src->prev->prev, dst->prev->prev); */
+/* dup_alignstackslots(src, dst->prev->prev->prev); */
+ 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);
+ lsra_new_stack(ls,dst,b_index,iindex);
+ break;
+
+ /* pop 3 push 5 dup */
+
+ case ICMD_DUP2_X1:
+ lsra_from_stack(ls, src,b_index,iindex); /* from for to, or it will not work! inc usage_count! */
+ lsra_from_stack(ls, src->prev,b_index,iindex); /*from for to, or it will not work! inc usage_count! */
+ lsra_from_stack(ls, src->prev->prev,b_index,iindex); /*from for to, or it will not work! inc usage_count! */
+/* dup_alignstackslots(src, dst); */
+/* dup_alignstackslots(src->prev, dst->prev); */
+/* dup_alignstackslots(src->prev->prev, dst->prev->prev); */
+/* dup_alignstackslots(src, dst->prev->prev->prev); */
+/* dup_alignstackslots(src->prev, dst->prev->prev->prev->prev); */
+ 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);
+ lsra_new_stack(ls,dst->prev,b_index,iindex);
+ lsra_new_stack(ls,dst,b_index,iindex);
+ break;
+
+ /* pop 4 push 6 dup */
+
+ case ICMD_DUP2_X2:
+ lsra_from_stack(ls, src,b_index,iindex); /* from for to, or it will not work! inc usage_count! */
+ lsra_from_stack(ls, src->prev,b_index,iindex); /*from for to, or it will not work! inc usage_count! */
+ lsra_from_stack(ls, src->prev->prev,b_index,iindex); /*from for to, or it will not work! inc usage_count! */
+ lsra_from_stack(ls, src->prev->prev->prev,b_index,iindex); /*from for to, or it will not work! inc usage_count! */
+/* dup_alignstackslots(src, dst); */
+/* dup_alignstackslots(src->prev, dst->prev); */
+/* dup_alignstackslots(src->prev->prev, dst->prev->prev); */
+/* dup_alignstackslots(src->prev->prev->prev, dst->prev->prev->prev); */
+/* dup_alignstackslots(src, dst->prev->prev->prev->prev); */
+/* dup_alignstackslots(src->prev, dst->prev->prev->prev->prev->prev); */
+ 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);
+ 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);
+ lsra_new_stack(ls,dst,b_index,iindex);
+ break;
+
+ /* pop 2 push 2 swap */
+
+ case ICMD_SWAP:
+ lsra_from_stack(ls, src,b_index,iindex); /* from for to, or it will not work! inc usage_count! */
+ lsra_from_stack(ls, src->prev,b_index,iindex); /*from for to, or it will not work! inc usage_count! */
+/* dst->varnum = src->varnum; */
+/* dst->varkind = src->varkind; */
+ lsra_new_stack(ls,dst->prev,b_index,iindex);
+ lsra_new_stack(ls,dst,b_index,iindex);
+ 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:
+ lsra_from_stack(ls, src,b_index,iindex);
+ lsra_from_stack(ls, src->prev,b_index,iindex);
+ lsra_new_stack(ls,dst,b_index,iindex);
+ break;
+
+ /* pop 1 push 1 */
+
+ case ICMD_IADDCONST:
+ case ICMD_ISUBCONST:
+ case ICMD_IMULCONST:
+ 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_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_ARRAYLENGTH:
+ case ICMD_INSTANCEOF:
+
+ case ICMD_NEWARRAY:
+ case ICMD_ANEWARRAY:
+
+ case ICMD_GETFIELD:
+ lsra_from_stack(ls, src,b_index,iindex);
+ lsra_new_stack(ls,dst,b_index,iindex);
+ break;
+
+ /* pop 0 push 1 */
+
+ case ICMD_GETSTATIC:
+
+ case ICMD_NEW:
+
+ lsra_new_stack(ls,dst,b_index,iindex);
+ break;
+
+ /* pop many push any */
+ case ICMD_INVOKEVIRTUAL:
+ case ICMD_INVOKESPECIAL:
+ case ICMD_INVOKESTATIC:
+ case ICMD_INVOKEINTERFACE:
+ {
+ i = iptr->op1;
+ while (--i >= 0) {
+ lsra_from_stack(ls, src,b_index,iindex);
+ src = src->prev;
+ }
+ if (((methodinfo*)iptr->val.a)->returntype != TYPE_VOID) {
+ lsra_new_stack(ls,dst,b_index,iindex);
+ }
+ break;
+ }
+
+ case ICMD_BUILTIN3:
+ lsra_from_stack(ls, src,b_index,iindex);
+ src = src->prev;
+ case ICMD_BUILTIN2:
+ lsra_from_stack(ls, src,b_index,iindex);
+ src = src->prev;
+ case ICMD_BUILTIN1:
+ lsra_from_stack(ls, src,b_index,iindex);
+ src = src->prev; /* ??????????? */
+ if (iptr->op1 != TYPE_VOID)
+ lsra_new_stack(ls,dst,b_index,iindex);
+ break;
+
+ case ICMD_MULTIANEWARRAY:
+ i = iptr->op1;
+ while (--i >= 0) {
+ lsra_from_stack(ls, src,b_index,iindex);
+ src = src->prev;
+ }
+ lsra_new_stack(ls,dst,b_index,iindex);
+ break;
+
+ default:
+ printf("ICMD %d at %d\n", iptr->opc, (int)(iptr - m->instructions));
+ panic("Missing ICMD code during register allocation");
+ } /* switch */
+ iptr++;
+ iindex++;
+ } /* while instructions */
+ } /* if */
+
+
+
+ b_index++;
+ } /* while blocks */
+}
+
+/*
+ * 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:
+ */
Changes: Edwin Steiner
- $Id: stack.c 1585 2004-11-24 14:20:21Z twisti $
+ $Id: stack.c 1590 2004-11-25 13:24:49Z christian $
*/
printf("\n");
}
printf("\n");
-
+ if (!opt_lsra) {
printf("Interface Table:\n");
for (i = 0; i < cd->maxstack; i++) {
if ((rd->interfaces[i][0].type >= 0) ||
}
}
printf("\n");
-
+ }
if (showdisassemble) {
#if defined(__I386__) || defined(__X86_64__)
u1 *u1ptr;
Authors: Christian Thalinger
- $Id: options.c 1546 2004-11-18 12:25:04Z twisti $
+ $Id: options.c 1590 2004-11-25 13:24:49Z christian $
*/
bool opt_verify = true; /* true if classfiles should be verified */
bool opt_eager = false;
+bool opt_lsra = false;
int opt_ind = 1; /* index of processed arguments */
char *opt_arg; /* this one exports the option argument */
Authors: Christian Thalinger
- $Id: options.h 1553 2004-11-19 15:47:13Z carolyn $
+ $Id: options.h 1590 2004-11-25 13:24:49Z christian $
*/
extern bool opt_verify;
extern bool opt_eager;
+extern bool opt_lsra;
+
+
extern int opt_ind;
extern char *opt_arg;
int get_opt(int argc, char **argv, opt_struct *opts);
+
#endif /* _OPTIONS_H */