We will need this to optimize register allocation. Every LIR
instruction has two positions assigned - consecutive even and
odd. Even interval use positions correspond to instruction input and
odd positions correspond to instruction output. Distinction between
those allow to allocate the same physical register to adjacent
intervals where first ends at instruction input and the second starts
at instruction output. There are some more advantages of this
described in "Linear Scan Register Allocation for the Java HotSpot
Client Compiler", C. Wimmer.
This is a preliminary patch. All use positions are even yet.
Signed-off-by: Tomek Grabiec <tgrab...@gmail.com>
---
include/jit/compilation-unit.h | 2 +
include/jit/vars.h | 10 +++++
jit/compilation-unit.c | 4 ++-
jit/liveness.c | 4 +-
jit/spill-reload.c | 16 +++++++--
jit/trace-jit.c | 68 +++++++++++++++++++------------------
test/jit/compilation-unit-test.c | 2 +-
test/jit/liveness-test.c | 22 ++++++------
8 files changed, 77 insertions(+), 51 deletions(-)
diff --git a/include/jit/compilation-unit.h b/include/jit/compilation-unit.h
index f6fb0e9..4114bce 100644
--- a/include/jit/compilation-unit.h
+++ b/include/jit/compilation-unit.h
@@ -85,6 +85,8 @@ struct compilation_unit {
*/
struct radix_tree *lir_insn_map;
+ unsigned long last_insn;
+
/*
* This maps machine-code offset (of gc safepoint) to gc map
*/
diff --git a/include/jit/vars.h b/include/jit/vars.h
index 177c283..6afb16b 100644
--- a/include/jit/vars.h
+++ b/include/jit/vars.h
@@ -12,6 +12,16 @@ struct live_range {
unsigned long start, end; /* end is exclusive */
};
+static inline unsigned long range_last_insn_pos(struct live_range *range)
+{
+ return (range->end - 1) & ~1;
+}
+
+static inline unsigned long range_first_insn_pos(struct live_range *range)
+{
+ return range->start & ~1;
+}
+
static inline bool in_range(struct live_range *range, unsigned long offset)
{
return (offset >= range->start) && (offset < range->end);
diff --git a/jit/compilation-unit.c b/jit/compilation-unit.c
index cf349b8..956d8b8 100644
--- a/jit/compilation-unit.c
+++ b/jit/compilation-unit.c
@@ -259,9 +259,11 @@ void compute_insn_positions(struct compilation_unit *cu)
radix_tree_insert(cu->lir_insn_map, pos, insn);
- ++pos;
+ pos += 2;
}
bb->end_insn = pos;
}
+
+ cu->last_insn = pos;
}
diff --git a/jit/liveness.c b/jit/liveness.c
index cc82933..3e0f586 100644
--- a/jit/liveness.c
+++ b/jit/liveness.c
@@ -142,8 +142,8 @@ static void __analyze_use_def(struct basic_block *bb,
struct insn *insn)
*/
if (!test_bit(bb->def_set->bits, var->vreg))
set_bit(bb->use_set->bits, var->vreg);
- }
-
+ }
+
nr_defs = insn_defs(bb->b_parent, insn, defs);
for (i = 0; i < nr_defs; i++) {
struct var_info *var = defs[i];
diff --git a/jit/spill-reload.c b/jit/spill-reload.c
index af50046..5964682 100644
--- a/jit/spill-reload.c
+++ b/jit/spill-reload.c
@@ -50,7 +50,7 @@ static struct insn *first_insn(struct compilation_unit *cu,
struct live_interval
{
struct insn *ret;
- ret = radix_tree_lookup(cu->lir_insn_map, interval->range.start);
+ ret = radix_tree_lookup(cu->lir_insn_map,
range_first_insn_pos(&interval->range));
assert(ret != NULL);
return ret;
@@ -60,7 +60,7 @@ static struct insn *last_insn(struct compilation_unit *cu,
struct live_interval
{
struct insn *ret;
- ret = radix_tree_lookup(cu->lir_insn_map, interval->range.end - 1);
+ ret = radix_tree_lookup(cu->lir_insn_map,
range_last_insn_pos(&interval->range));
assert(ret != NULL);
return ret;
@@ -86,7 +86,7 @@ static struct list_head *bb_last_spill_node(struct
basic_block *bb)
if (bb->end_insn == bb->start_insn)
return &bb->insn_list;
- last = radix_tree_lookup(bb->b_parent->lir_insn_map, bb->end_insn - 1);
+ last = radix_tree_lookup(bb->b_parent->lir_insn_map, bb->end_insn - 2);
assert(last);
if (insn_is_branch(last))
@@ -190,6 +190,16 @@ static int __insert_spill_reload_insn(struct live_interval
*interval, struct com
goto out;
if (interval->need_reload) {
+ /*
+ * Intervals which start with a DEF position (odd
+ * numbers) should not be reloaded. One reason for
+ * this is that they do not have to because register
+ * content is overriden. Another reason is that we
+ * can't insert a reload instruction in the middle of
+ * instruction.
+ */
+ assert((interval->range.start & 1) == 0);
+
err = insert_reload_insn(interval, cu,
interval->spill_parent->spill_slot,
first_insn(cu, interval));
diff --git a/jit/trace-jit.c b/jit/trace-jit.c
index 1bde5e1..3b2823e 100644
--- a/jit/trace-jit.c
+++ b/jit/trace-jit.c
@@ -189,7 +189,6 @@ void trace_tree_ir(struct compilation_unit *cu)
void trace_lir(struct compilation_unit *cu)
{
- unsigned long offset = 0;
struct basic_block *bb;
struct string *str;
struct insn *insn;
@@ -221,7 +220,7 @@ void trace_lir(struct compilation_unit *cu)
free_str(bc_str);
}
- trace_printf(" %5lu: %s\n", offset++, str->value);
+ trace_printf(" %5lu: %s\n", insn->lir_pos,
str->value);
free_str(str);
}
}
@@ -232,35 +231,42 @@ void trace_lir(struct compilation_unit *cu)
static void
print_var_liveness(struct compilation_unit *cu, struct var_info *var)
{
- struct live_range *range = &var->interval->range;
- struct basic_block *bb;
+ struct live_interval *interval;
unsigned long offset;
- struct insn *insn;
trace_printf(" %2lu: ", var->vreg);
-
+ interval = var->interval;
offset = 0;
- for_each_basic_block(bb, &cu->bb_list) {
- for_each_insn(insn, &bb->insn_list) {
- if (in_range(range, offset)) {
- if (next_use_pos(var->interval, offset) ==
offset) {
- /* In use */
- trace_printf("UUU");
- } else {
- if (var->interval->reg ==
MACH_REG_UNASSIGNED)
- trace_printf("***");
- else
- trace_printf("---");
- }
- }
- else
- trace_printf(" ");
- offset++;
- }
+ if (range_is_empty(&interval->range))
+ goto skip;
+
+ for (; offset < interval->range.start; offset++)
+ trace_printf(" ");
+
+ for (; offset < interval->range.end; offset++) {
+ if (in_range(&interval->range, offset)) {
+ if (next_use_pos(var->interval, offset) == offset) {
+ /* In use */
+ trace_printf("UUU");
+ } else {
+ if (var->interval->reg == MACH_REG_UNASSIGNED)
+ trace_printf("***");
+ else
+ trace_printf("---");
+ }
+ } else
+ trace_printf(" ");
}
- if (!range_is_empty(range))
- trace_printf(" (start: %2lu, end: %2lu)\n", range->start,
range->end);
+
+ skip:
+ for (; offset < cu->last_insn; offset++)
+ trace_printf(" ");
+
+ if (!range_is_empty(&interval->range))
+ trace_printf(" (start: %2lu, end: %2lu)\n",
+ interval->range.start,
+ interval->range.end);
else
trace_printf(" (empty)\n");
}
@@ -306,7 +312,6 @@ void trace_liveness(struct compilation_unit *cu)
struct basic_block *bb;
struct var_info *var;
unsigned long offset;
- struct insn *insn;
if (!cu_matches_regex(cu))
return;
@@ -314,14 +319,11 @@ void trace_liveness(struct compilation_unit *cu)
trace_printf("Liveness:\n\n");
trace_printf("Legend: (U) In use, (-) Fixed register, (*) Non-fixed
register\n\n");
-
trace_printf(" ");
- offset = 0;
- for_each_basic_block(bb, &cu->bb_list) {
- for_each_insn(insn, &bb->insn_list) {
- trace_printf("%-2lu ", offset++);
- }
- }
+
+ for (offset = 0; offset < cu->last_insn; offset++)
+ trace_printf("%-2lu ", offset);
+
trace_printf("\n");
for_each_variable(var, cu->var_infos)
diff --git a/test/jit/compilation-unit-test.c b/test/jit/compilation-unit-test.c
index 6ae6105..f2a5a19 100644
--- a/test/jit/compilation-unit-test.c
+++ b/test/jit/compilation-unit-test.c
@@ -65,7 +65,7 @@ void
test_instruction_positions_are_computed_in_basic_block_order(void)
compute_insn_positions(cu);
for (i = 0; i < ARRAY_SIZE(insns); i++)
- assert_int_equals(i, insns[i]->lir_pos);
+ assert_int_equals(i * 2, insns[i]->lir_pos);
free_compilation_unit(cu);
}
diff --git a/test/jit/liveness-test.c b/test/jit/liveness-test.c
index 10bfb72..19f01d0 100644
--- a/test/jit/liveness-test.c
+++ b/test/jit/liveness-test.c
@@ -69,15 +69,15 @@ void test_variable_range_limited_to_basic_block(void)
assert_defines(bb, r1);
assert_defines(bb, r2);
- assert_live_range(r1->interval, 0, 3);
- assert_live_range(r2->interval, 1, 3);
+ assert_live_range(r1->interval, 0, 5);
+ assert_live_range(r2->interval, 2, 5);
assert_insn_at_equals(insn[0], cu, r1->interval, 0);
- assert_insn_at_equals(insn[1], cu, r1->interval, 1);
- assert_insn_at_equals(insn[2], cu, r1->interval, 2);
+ assert_insn_at_equals(insn[1], cu, r1->interval, 2);
+ assert_insn_at_equals(insn[2], cu, r1->interval, 4);
assert_insn_at_equals(insn[1], cu, r2->interval, 0);
- assert_insn_at_equals(insn[2], cu, r2->interval, 1);
+ assert_insn_at_equals(insn[2], cu, r2->interval, 2);
free_compilation_unit(cu);
}
@@ -116,16 +116,16 @@ void test_variable_range_spans_two_basic_blocks(void)
assert_defines(bb2, r2);
assert_uses(bb2, r1);
- assert_live_range(r1->interval, 0, 4);
- assert_live_range(r2->interval, 2, 4);
+ assert_live_range(r1->interval, 0, 7);
+ assert_live_range(r2->interval, 4, 7);
assert_insn_at_equals(insn[0], cu, r1->interval, 0);
- assert_insn_at_equals(insn[1], cu, r1->interval, 1);
- assert_insn_at_equals(insn[2], cu, r1->interval, 2);
- assert_insn_at_equals(insn[3], cu, r1->interval, 3);
+ assert_insn_at_equals(insn[1], cu, r1->interval, 2);
+ assert_insn_at_equals(insn[2], cu, r1->interval, 4);
+ assert_insn_at_equals(insn[3], cu, r1->interval, 6);
assert_insn_at_equals(insn[2], cu, r2->interval, 0);
- assert_insn_at_equals(insn[3], cu, r2->interval, 1);
+ assert_insn_at_equals(insn[3], cu, r2->interval, 2);
free_compilation_unit(cu);
}
--
1.6.3.3
------------------------------------------------------------------------------
Let Crystal Reports handle the reporting - Free Crystal Reports 2008 30-Day
trial. Simplify your report design, integration and deployment - and focus on
what you do best, core application coding. Discover what's new with
Crystal Reports now. http://p.sf.net/sfu/bobj-july
_______________________________________________
Jatovm-devel mailing list
Jatovm-devel@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/jatovm-devel
