This fixes bug encountered when compiling Substring().
---
include/jit/vars.h | 5 ++-
jit/interval.c | 33 +++++++++++++++
jit/linear-scan.c | 1 +
jit/spill-reload.c | 113 +++++++++++++++++++++++++++++++++++++++++++++++-----
4 files changed, 141 insertions(+), 11 deletions(-)
diff --git a/include/jit/vars.h b/include/jit/vars.h
index 482f10a..1821bb3 100644
--- a/include/jit/vars.h
+++ b/include/jit/vars.h
@@ -4,6 +4,8 @@
#include "lib/list.h"
#include "arch/registers.h"
#include "vm/types.h"
+#include "compilation-unit.h"
+
#include <stdbool.h>
#include <assert.h>
@@ -111,5 +113,6 @@ struct live_interval *alloc_interval(struct var_info *);
void free_interval(struct live_interval *);
struct live_interval *split_interval_at(struct live_interval *, unsigned long
pos);
unsigned long next_use_pos(struct live_interval *, unsigned long);
-
+struct live_interval *vreg_start_interval(struct compilation_unit *, unsigned
long);
+struct live_interval *interval_child_at(struct live_interval *, unsigned long);
#endif /* __JIT_VARS_H */
diff --git a/jit/interval.c b/jit/interval.c
index e450b94..03da977 100644
--- a/jit/interval.c
+++ b/jit/interval.c
@@ -121,3 +121,36 @@ unsigned long next_use_pos(struct live_interval *it,
unsigned long pos)
return min;
}
+
+struct live_interval *vreg_start_interval(struct compilation_unit *cu,
unsigned long vreg)
+{
+ struct var_info *var;
+
+ var = cu->var_infos;
+
+ while (var) {
+ if (var->vreg == vreg)
+ break;
+
+ var = var->next;
+ }
+
+ if (var == NULL)
+ return NULL;
+
+ return var->interval;
+}
+
+struct live_interval *interval_child_at(struct live_interval *parent, unsigned
long pos)
+{
+ struct live_interval *it = parent;
+
+ while (it) {
+ if (in_range(&it->range, pos))
+ return it;
+
+ it = it->next_child;
+ }
+
+ return NULL;
+}
diff --git a/jit/linear-scan.c b/jit/linear-scan.c
index ca3053b..cceb145 100644
--- a/jit/linear-scan.c
+++ b/jit/linear-scan.c
@@ -381,6 +381,7 @@ int allocate_registers(struct compilation_unit *cu)
if (current->reg != REG_UNASSIGNED)
list_add(¤t->interval_node, &active);
}
+
free(registers);
return 0;
diff --git a/jit/spill-reload.c b/jit/spill-reload.c
index 94d2af7..4d1c409 100644
--- a/jit/spill-reload.c
+++ b/jit/spill-reload.c
@@ -30,8 +30,17 @@
#include "arch/instruction.h"
+#include "lib/bitset.h"
+
#include <errno.h>
+#include <stdio.h>
+#include <string.h>
+
+struct live_interval_mapping {
+ struct live_interval *from, *to;
+};
+
static struct insn *last_insn(struct live_interval *interval)
{
unsigned long end;
@@ -44,13 +53,12 @@ static struct insn *last_insn(struct live_interval
*interval)
return ret;
}
-static int insert_spill_insn(struct live_interval *interval, struct
compilation_unit *cu)
+static struct stack_slot *spill_interval(struct live_interval *interval,
struct compilation_unit *cu)
{
- struct insn *last = last_insn(interval);
struct stack_slot *slot;
struct var_info *reg;
struct insn *spill;
-
+ struct insn *last = last_insn(interval);
/*
* We've already done register allocation, so use fixed registers for
* spilling and reloading.
@@ -59,18 +67,26 @@ static int insert_spill_insn(struct live_interval
*interval, struct compilation_
slot = get_spill_slot_32(cu->stack_frame);
if (!slot)
- return -ENOMEM;
+ return NULL;
spill = spill_insn(reg, slot);
if (!spill)
- return -ENOMEM;
-
- interval->spill_slot = slot;
+ return NULL;
spill->bytecode_offset = last->bytecode_offset;
list_add(&spill->insn_list_node, &last->insn_list_node);
+ return slot;
+}
+
+static int insert_spill_insn(struct live_interval *interval, struct
compilation_unit *cu)
+{
+ interval->spill_slot = spill_interval(interval, cu);
+
+ if (!interval->spill_slot)
+ return -ENOMEM;
+
return 0;
}
@@ -84,14 +100,14 @@ static struct insn *first_insn(struct live_interval
*interval)
return ret;
}
-static int insert_reload_insn(struct live_interval *interval, struct
compilation_unit *cu)
+static int insert_reload_insn(struct live_interval *interval, struct
compilation_unit *cu, struct stack_slot *from)
{
struct insn *first = first_insn(interval);
struct insn *reload;
struct var_info *reg;
reg = get_fixed_var(cu, interval->reg);
- reload = reload_insn(interval->spill_parent->spill_slot, reg);
+ reload = reload_insn(from, reg);
if (!reload)
return -ENOMEM;
@@ -110,7 +126,7 @@ static int __insert_spill_reload_insn(struct live_interval
*interval, struct com
goto out;
if (interval->need_reload) {
- err = insert_reload_insn(interval, cu);
+ err = insert_reload_insn(interval, cu,
interval->spill_parent->spill_slot);
if (err)
goto out;
}
@@ -124,6 +140,79 @@ out:
return err;
}
+static void maybe_add_mov_for_vreg(struct compilation_unit *cu, struct
basic_block *from, struct basic_block *to, unsigned long vreg, struct
live_interval_mapping *mappings, int *nrmapped)
+{
+ struct live_interval *parent_it;
+ struct live_interval *from_it, *to_it;
+
+ parent_it = vreg_start_interval(cu, vreg);
+ from_it = interval_child_at(parent_it, from->end);
+ to_it = interval_child_at(parent_it, to->start);
+
+ /* We seem to have some vregs that are alive at the beginning of a bb,
+ * but have no interval covering them. In that case, no mov is to be
inserted.
+ */
+ if (!from_it || !to_it)
+ return;
+
+ if (from_it != to_it) {
+ printf("vreg %lu at position %lu is not in the same
interval...\n", vreg, from->end);
+ mappings[*nrmapped].from = from_it;
+ mappings[*nrmapped].to = to_it;
+ (*nrmapped)++;
+ }
+}
+
+static void insert_mov_insns(struct compilation_unit *cu, struct
live_interval_mapping *mappings, int nrmapped)
+{
+ int i;
+ struct stack_slot *slots[nrmapped];
+
+ /* Spill all intervals that have to be resolved */
+ for (i = 0; i < nrmapped; i++) {
+ printf("mapping it %#x to it %#x\n", (unsigned
int)mappings[i].from, (unsigned int)mappings[i].to);
+ if (mappings[i].from->need_spill)
+ slots[i] = mappings[i].from->spill_slot;
+ else
+ slots[i] = spill_interval(mappings[i].from, cu);
+
+ /* Reload those intervals into their new location */
+ if (mappings[i].to->need_reload) {
+ NOT_IMPLEMENTED;
+ } else {
+ insert_reload_insn(mappings[i].from, cu, slots[i]);
+ }
+ }
+}
+
+static void resolve_data_flow(struct compilation_unit *cu)
+{
+ struct basic_block *this, *succ;
+ unsigned int isucc;
+ unsigned long vreg;
+
+ /* This implements the algorithm ResolveDataFlow described by
+ * Christian Wimmer in 2004 */
+ for_each_basic_block(this, &cu->bb_list) {
+ for (isucc = 0; isucc < this->nr_successors; isucc++) {
+ struct live_interval_mapping
mappings[this->nr_predecessors];
+ int nrmapped = 0;
+
+ memset(mappings, 0, this->nr_predecessors *
sizeof(struct live_interval_mapping));
+
+ succ = this->successors[isucc];
+
+ for (vreg = 0; vreg < cu->nr_vregs; vreg++) {
+ if (test_bit(succ->live_in_set->bits, vreg)) {
+ maybe_add_mov_for_vreg(cu, this, succ,
vreg, mappings, &nrmapped);
+ }
+ }
+
+ insert_mov_insns(cu, mappings, nrmapped);
+ }
+ }
+}
+
int insert_spill_reload_insns(struct compilation_unit *cu)
{
struct var_info *var;
@@ -138,5 +227,9 @@ int insert_spill_reload_insns(struct compilation_unit *cu)
break;
}
}
+
+ /* Make sure intervals spilled across basic block boundaries will
+ * be reloaded correctly */
+ resolve_data_flow(cu);
return err;
}
--
1.5.6.3
------------------------------------------------------------------------------
Enter the BlackBerry Developer Challenge
This is your chance to win up to $100,000 in prizes! For a limited time,
vendors submitting new applications to BlackBerry App World(TM) will have
the opportunity to enter the BlackBerry Developer Challenge. See full prize
details at: http://p.sf.net/sfu/Challenge
_______________________________________________
Jatovm-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/jatovm-devel
