This fixes the performance issue in liveness analysis.
Signed-off-by: Vegard Nossum <vegard.nos...@gmail.com>
---
include/jit/compilation-unit.h | 7 +++++-
include/jit/vars.h | 3 --
jit/compilation-unit.c | 21 +++++++++++++++--
jit/interval.c | 25 +--------------------
jit/liveness.c | 40 ----------------------------------
jit/spill-reload.c | 30 ++++++++++++--------------
test/jit/Makefile | 1 -
test/jit/interval-test.c | 46 ----------------------------------------
test/jit/liveness-test.c | 32 ++++++++++++++++++---------
9 files changed, 60 insertions(+), 145 deletions(-)
delete mode 100644 test/jit/interval-test.c
diff --git a/include/jit/compilation-unit.h b/include/jit/compilation-unit.h
index 61ea66b..37178c1 100644
--- a/include/jit/compilation-unit.h
+++ b/include/jit/compilation-unit.h
@@ -3,8 +3,8 @@
#include "arch/registers.h"
#include "jit/basic-block.h"
-
#include "lib/list.h"
+#include "lib/radix-tree.h"
#include "vm/stack.h"
#include "vm/static.h"
#include "vm/types.h"
@@ -72,6 +72,11 @@ struct compilation_unit {
* inside JIT code.
*/
unsigned long *bc_offset_map;
+
+ /*
+ * This maps LIR offset to instruction.
+ */
+ struct radix_tree *lir_insn_map;
};
struct compilation_unit *compilation_unit_alloc(struct vm_method *);
diff --git a/include/jit/vars.h b/include/jit/vars.h
index e0e7bed..07aa6be 100644
--- a/include/jit/vars.h
+++ b/include/jit/vars.h
@@ -81,9 +81,6 @@ struct live_interval {
linear scan. */
struct list_head interval_node;
- /* Array of instructions within this interval. */
- struct insn **insn_array;
-
/* Do we need to spill the register of this interval? */
bool need_spill;
diff --git a/jit/compilation-unit.c b/jit/compilation-unit.c
index 9a207ac..e8a044b 100644
--- a/jit/compilation-unit.c
+++ b/jit/compilation-unit.c
@@ -109,6 +109,8 @@ struct compilation_unit *compilation_unit_alloc(struct
vm_method *method)
cu->fixed_var_infos[i] = ret;
}
+
+ cu->lir_insn_map = NULL;
}
return cu;
@@ -136,8 +138,7 @@ static void free_var_infos(struct var_info *var_infos)
static void free_bc_offset_map(unsigned long *map)
{
- if (map)
- free(map);
+ free(map);
}
static void free_tableswitch_list(struct compilation_unit *cu)
@@ -150,6 +151,11 @@ static void free_tableswitch_list(struct compilation_unit
*cu)
}
}
+static void free_lir_insn_map(struct compilation_unit *cu)
+{
+ free_radix_tree(cu->lir_insn_map);
+}
+
void free_compilation_unit(struct compilation_unit *cu)
{
struct basic_block *bb, *tmp_bb;
@@ -165,6 +171,7 @@ void free_compilation_unit(struct compilation_unit *cu)
free_stack_frame(cu->stack_frame);
free_bc_offset_map(cu->bc_offset_map);
free_tableswitch_list(cu);
+ free_lir_insn_map(cu);
free(cu);
}
@@ -219,11 +226,19 @@ void compute_insn_positions(struct compilation_unit *cu)
struct basic_block *bb;
unsigned long pos = 0;
+ cu->lir_insn_map = alloc_radix_tree(8, 8 * sizeof(pos));
+ if (!cu->lir_insn_map)
+ die("oom");
+
for_each_basic_block(bb, &cu->bb_list) {
struct insn *insn;
for_each_insn(insn, &bb->insn_list) {
- insn->lir_pos = pos++;
+ insn->lir_pos = pos;
+
+ radix_tree_insert(cu->lir_insn_map, pos, insn);
+
+ ++pos;
}
}
}
diff --git a/jit/interval.c b/jit/interval.c
index ccdc84e..8a7620f 100644
--- a/jit/interval.c
+++ b/jit/interval.c
@@ -56,33 +56,14 @@ void free_interval(struct live_interval *interval)
if (interval->next_child)
free_interval(interval->next_child);
- free(interval->insn_array);
free(interval);
}
-static int split_insn_array(struct live_interval *src, struct live_interval
*dst)
-{
- unsigned long src_len, dst_len, size;
-
- src_len = range_len(&src->range);
- dst_len = range_len(&dst->range);
-
- size = dst_len * sizeof(struct insn *);
- dst->insn_array = zalloc(size);
- if (!dst->insn_array)
- return warn("out of memory"), -ENOMEM;
-
- memcpy(dst->insn_array, src->insn_array + src_len, size);
-
- return 0;
-}
-
struct live_interval *split_interval_at(struct live_interval *interval,
unsigned long pos)
{
struct use_position *this, *next;
struct live_interval *new;
- int err;
new = alloc_interval(interval->var_info);
if (!new)
@@ -100,11 +81,7 @@ struct live_interval *split_interval_at(struct
live_interval *interval,
list_move(&this->use_pos_list, &new->use_positions);
this->interval = new;
}
- err = split_insn_array(interval, new);
- if (err) {
- free_interval(new);
- return NULL;
- }
+
new->next_child = interval->next_child;
new->prev_child = interval;
interval->next_child = new;
diff --git a/jit/liveness.c b/jit/liveness.c
index 8ffb1cb..619a988 100644
--- a/jit/liveness.c
+++ b/jit/liveness.c
@@ -36,45 +36,6 @@
#include <errno.h>
#include <stdlib.h>
-static void __update_interval_insn(struct live_interval *interval,
- struct basic_block *bb)
-{
- struct insn *insn;
-
- for_each_insn(insn, &bb->insn_list) {
- unsigned long offset;
-
- if (!in_range(&interval->range, insn->lir_pos))
- continue;
-
- offset = insn->lir_pos - interval->range.start;
- interval->insn_array[offset] = insn;
- }
-}
-
-static int update_interval_insns(struct compilation_unit *cu)
-{
- struct var_info *var;
- int err = 0;
-
- for_each_variable(var, cu->var_infos) {
- struct live_interval *interval = var->interval;
- struct basic_block *bb;
- unsigned long nr;
-
- nr = range_len(&interval->range);
- interval->insn_array = calloc(nr, sizeof(struct insn *));
- if (!interval->insn_array) {
- err = -ENOMEM;
- break;
- }
- for_each_basic_block(bb, &cu->bb_list) {
- __update_interval_insn(var->interval, bb);
- }
- }
- return err;
-}
-
static void __update_live_range(struct live_range *range, unsigned long pos)
{
if (range->start > pos)
@@ -272,7 +233,6 @@ int analyze_liveness(struct compilation_unit *cu)
update_live_ranges(cu);
- err = update_interval_insns(cu);
out:
return err;
}
diff --git a/jit/spill-reload.c b/jit/spill-reload.c
index 1d6e774..9ce571f 100644
--- a/jit/spill-reload.c
+++ b/jit/spill-reload.c
@@ -43,13 +43,21 @@ struct live_interval_mapping {
struct live_interval *from, *to;
};
-static struct insn *last_insn(struct live_interval *interval)
+static struct insn *first_insn(struct compilation_unit *cu, struct
live_interval *interval)
{
- unsigned long end;
struct insn *ret;
- end = range_len(&interval->range) - 1;
- ret = interval->insn_array[end];
+ ret = radix_tree_lookup(cu->lir_insn_map, interval->range.start);
+ assert(ret != NULL);
+
+ return ret;
+}
+
+static struct insn *last_insn(struct compilation_unit *cu, struct
live_interval *interval)
+{
+ struct insn *ret;
+
+ ret = radix_tree_lookup(cu->lir_insn_map, interval->range.end - 1);
assert(ret != NULL);
return ret;
@@ -84,7 +92,7 @@ spill_interval(struct live_interval *interval,
static int
insert_spill_insn(struct live_interval *interval, struct compilation_unit *cu)
{
- interval->spill_slot = spill_interval(interval, cu,
last_insn(interval), false);
+ interval->spill_slot = spill_interval(interval, cu, last_insn(cu,
interval), false);
if (!interval->spill_slot)
return warn("out of memory"), -ENOMEM;
@@ -92,16 +100,6 @@ insert_spill_insn(struct live_interval *interval, struct
compilation_unit *cu)
return 0;
}
-static struct insn *first_insn(struct live_interval *interval)
-{
- struct insn *ret;
-
- ret = interval->insn_array[0];
- assert(ret != NULL);
-
- return ret;
-}
-
static int insert_reload_insn(struct live_interval *interval,
struct compilation_unit *cu,
struct stack_slot *from,
@@ -159,7 +157,7 @@ static int __insert_spill_reload_insn(struct live_interval
*interval, struct com
if (interval->need_reload) {
err = insert_reload_insn(interval, cu,
interval->spill_parent->spill_slot,
- first_insn(interval));
+ first_insn(cu, interval));
if (err)
goto out;
}
diff --git a/test/jit/Makefile b/test/jit/Makefile
index 5c26268..f669c08 100644
--- a/test/jit/Makefile
+++ b/test/jit/Makefile
@@ -82,7 +82,6 @@ TEST_OBJS := \
cfg-analyzer-test.o \
compilation-unit-test.o \
expression-test.o \
- interval-test.o \
invoke-bc-test.o \
linear-scan-test.o \
live-range-test.o \
diff --git a/test/jit/interval-test.c b/test/jit/interval-test.c
deleted file mode 100644
index 23db794..0000000
--- a/test/jit/interval-test.c
+++ /dev/null
@@ -1,46 +0,0 @@
-/*
- * Copyright (c) 2008 Pekka Enberg
- */
-#include "arch/instruction.h"
-#include "jit/vars.h"
-#include <libharness.h>
-#include <stdlib.h>
-
-void test_split_interval_at(void)
-{
- struct live_interval *new_interval;
- struct insn insns[2];
- struct var_info var;
- unsigned int i;
-
- var.interval = alloc_interval(&var);
- var.interval->insn_array = calloc(ARRAY_SIZE(insns), sizeof(struct insn
*));
-
- for (i = 0; i < ARRAY_SIZE(insns); i++) {
- struct insn *insn = &insns[i];
-
- insn->lir_pos = i;
- register_set_insn(&insn->x.reg, insn);
- insert_register_to_interval(var.interval, &insn->x.reg);
- var.interval->insn_array[i] = insn;
- }
- var.interval->range.start = 0;
- var.interval->range.end = ARRAY_SIZE(insns);
-
- assert_ptr_equals(var.interval, insns[0].x.reg.interval);
- assert_ptr_equals(var.interval, insns[1].x.reg.interval);
-
- new_interval = split_interval_at(var.interval, 1);
-
- assert_ptr_equals(var.interval, insns[0].x.reg.interval);
- assert_int_equals(0, var.interval->range.start);
- assert_int_equals(1, var.interval->range.end);
- assert_ptr_equals(&insns[0], var.interval->insn_array[0]);
-
- assert_ptr_equals(new_interval, insns[1].x.reg.interval);
- assert_int_equals(1, new_interval->range.start);
- assert_int_equals(2, new_interval->range.end);
- assert_ptr_equals(&insns[1], new_interval->insn_array[0]);
-
- free_interval(var.interval);
-}
diff --git a/test/jit/liveness-test.c b/test/jit/liveness-test.c
index f154206..10bfb72 100644
--- a/test/jit/liveness-test.c
+++ b/test/jit/liveness-test.c
@@ -31,6 +31,16 @@ static void assert_defines(struct basic_block *bb, struct
var_info *var)
assert_false(test_bit(bb->use_set->bits, var->vreg));
}
+static void assert_insn_at_equals(struct insn *insn, struct compilation_unit
*cu, struct live_interval *interval, unsigned int offset)
+{
+ struct insn *insn2;
+
+ insn2 = radix_tree_lookup(cu->lir_insn_map,
+ interval->range.start + offset);
+
+ assert_ptr_equals(insn, insn2);
+}
+
void test_variable_range_limited_to_basic_block(void)
{
struct compilation_unit *cu;
@@ -62,12 +72,12 @@ void test_variable_range_limited_to_basic_block(void)
assert_live_range(r1->interval, 0, 3);
assert_live_range(r2->interval, 1, 3);
- assert_ptr_equals(insn[0], r1->interval->insn_array[0]);
- assert_ptr_equals(insn[1], r1->interval->insn_array[1]);
- assert_ptr_equals(insn[2], r1->interval->insn_array[2]);
+ 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_ptr_equals(insn[1], r2->interval->insn_array[0]);
- assert_ptr_equals(insn[2], r2->interval->insn_array[1]);
+ assert_insn_at_equals(insn[1], cu, r2->interval, 0);
+ assert_insn_at_equals(insn[2], cu, r2->interval, 1);
free_compilation_unit(cu);
}
@@ -109,13 +119,13 @@ void test_variable_range_spans_two_basic_blocks(void)
assert_live_range(r1->interval, 0, 4);
assert_live_range(r2->interval, 2, 4);
- assert_ptr_equals(insn[0], r1->interval->insn_array[0]);
- assert_ptr_equals(insn[1], r1->interval->insn_array[1]);
- assert_ptr_equals(insn[2], r1->interval->insn_array[2]);
- assert_ptr_equals(insn[3], r1->interval->insn_array[3]);
+ 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_ptr_equals(insn[2], r2->interval->insn_array[0]);
- assert_ptr_equals(insn[3], r2->interval->insn_array[1]);
+ assert_insn_at_equals(insn[2], cu, r2->interval, 0);
+ assert_insn_at_equals(insn[3], cu, r2->interval, 1);
free_compilation_unit(cu);
}
--
1.6.0.4
------------------------------------------------------------------------------
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
