Having ->current_range in struct interval is very error prone.
Instead of that, we maintain a list of expired ranges, which are moved
from range_list and are no longer considered as interval's
ranges. After linear scan expired ranges are restored.
This fixes a crash in trace_var_liveness().
Signed-off-by: Tomek Grabiec <tgrab...@gmail.com>
---
include/jit/vars.h | 18 ++++++++----------
jit/interval.c | 41 +++++++++++++++++++++++------------------
jit/linear-scan.c | 15 +++++++++++----
3 files changed, 42 insertions(+), 32 deletions(-)
diff --git a/include/jit/vars.h b/include/jit/vars.h
index 2471b17..ae48752 100644
--- a/include/jit/vars.h
+++ b/include/jit/vars.h
@@ -65,16 +65,13 @@ struct live_interval {
struct list_head range_list;
/*
- * Points to a range from range_list which should be
- * considered as interval's starting range in operations:
- * intervals_intersect(), interval_intersection_start(),
- * interval_range_at(). It's used to speedup register
- * allocation. Intervals can have a lot of live ranges. Linear
- * scan algorithm goes through intervals in ascending order by
- * interval start. We can take advantage of this and don't
- * browse ranges past current position in some operations.
+ * Contains ranges which were moved from range_list to speedup
+ * some interval oprations. Intervals can have a lot of live
+ * ranges. Linear scan algorithm goes through intervals in
+ * ascending order by interval start. We can take advantage of
+ * this and don't check ranges before current position.
*/
- struct live_range *current_range;
+ struct list_head expired_range_list;
/* Linked list of child intervals. */
struct live_interval *next_child, *prev_child;
@@ -172,7 +169,8 @@ unsigned long interval_intersection_start(struct
live_interval *, struct live_in
bool interval_covers(struct live_interval *, unsigned long);
int interval_add_range(struct live_interval *, unsigned long, unsigned long);
struct live_range *interval_range_at(struct live_interval *, unsigned long);
-void interval_update_current_range(struct live_interval *, unsigned long);
+void interval_expire_ranges_before(struct live_interval *, unsigned long);
+void interval_restore_expired_ranges(struct live_interval *);
static inline unsigned long first_use_pos(struct live_interval *it)
{
diff --git a/jit/interval.c b/jit/interval.c
index 8eb7d32..c84de36 100644
--- a/jit/interval.c
+++ b/jit/interval.c
@@ -106,6 +106,7 @@ struct live_interval *alloc_interval(struct var_info *var)
INIT_LIST_HEAD(&interval->interval_node);
INIT_LIST_HEAD(&interval->use_positions);
INIT_LIST_HEAD(&interval->range_list);
+ INIT_LIST_HEAD(&interval->expired_range_list);
}
return interval;
}
@@ -143,8 +144,6 @@ struct live_interval *split_interval_at(struct
live_interval *interval,
return NULL;
}
- new->current_range = interval_first_range(new);
-
new->fixed_reg = interval->fixed_reg;
if (new->fixed_reg)
new->reg = interval->reg;
@@ -210,25 +209,33 @@ struct live_interval *vreg_start_interval(struct
compilation_unit *cu, unsigned
return var->interval;
}
-/**
- * Advances @it->current_range to the last range which covers @pos or
- * is before @pos.
- */
-void interval_update_current_range(struct live_interval *it, unsigned long pos)
+void interval_expire_ranges_before(struct live_interval *it, unsigned long pos)
{
+ struct live_range *range;
+
if (pos < interval_start(it) || pos >= interval_end(it))
return;
- assert (pos >= it->current_range->start);
+ range = interval_first_range(it);
- while (!in_range(it->current_range, pos)) {
+ while (!in_range(range, pos)) {
struct live_range *next;
- next = next_range(&it->range_list, it->current_range);
+ next = next_range(&it->range_list, range);
if (pos < next->start)
break;
- it->current_range = next;
+ list_move(&range->range_list_node, &it->expired_range_list);
+ range = next;
+ }
+}
+
+void interval_restore_expired_ranges(struct live_interval *it)
+{
+ struct live_range *this, *next;
+
+ list_for_each_entry_safe(this, next, &it->expired_range_list,
range_list_node) {
+ list_move(&this->range_list_node, &it->range_list);
}
}
@@ -239,9 +246,7 @@ struct live_range *interval_range_at(struct live_interval
*it, unsigned long pos
if (pos < interval_start(it) || pos >= interval_end(it))
return NULL;
- range = it->current_range;
- if (pos < range->start)
- range = interval_first_range(it);
+ range = interval_first_range(it);
while (range && pos >= range->start) {
if (in_range(range, pos))
@@ -281,8 +286,8 @@ bool intervals_intersect(struct live_interval *it1, struct
live_interval *it2)
if (interval_is_empty(it1) || interval_is_empty(it2))
return false;
- r1 = it1->current_range;
- r2 = it2->current_range;
+ r1 = interval_first_range(it1);
+ r2 = interval_first_range(it2);
while (r1 && r1->end <= r2->start)
r1 = next_range(&it1->range_list, r1);
@@ -310,8 +315,8 @@ interval_intersection_start(struct live_interval *it1,
struct live_interval *it2
assert(!interval_is_empty(it1) && !interval_is_empty(it2));
- r1 = it1->current_range;
- r2 = it2->current_range;
+ r1 = interval_first_range(it1);
+ r2 = interval_first_range(it2);
while (r1 && r1->end <= r2->start)
r1 = next_range(&it1->range_list, r1);
diff --git a/jit/linear-scan.c b/jit/linear-scan.c
index c824104..05ff33d 100644
--- a/jit/linear-scan.c
+++ b/jit/linear-scan.c
@@ -354,8 +354,6 @@ int allocate_registers(struct compilation_unit *cu)
if (interval_is_empty(var->interval))
continue;
- var->interval->current_range =
interval_first_range(var->interval);
-
if (var->interval->fixed_reg) {
if (var->interval->reg < NR_REGISTERS)
list_add(&var->interval->interval_node,
&inactive);
@@ -379,7 +377,7 @@ int allocate_registers(struct compilation_unit *cu)
continue;
}
- interval_update_current_range(it, position);
+ interval_expire_ranges_before(it, position);
if (!interval_covers(it, position))
list_move(&it->interval_node, &inactive);
@@ -394,7 +392,7 @@ int allocate_registers(struct compilation_unit *cu)
continue;
}
- interval_update_current_range(it, position);
+ interval_expire_ranges_before(it, position);
if (interval_covers(it, position))
list_move(&it->interval_node, &active);
@@ -415,6 +413,15 @@ int allocate_registers(struct compilation_unit *cu)
}
free(registers);
+ for_each_variable(var, cu->var_infos) {
+ struct live_interval *it = var->interval;
+
+ while (it) {
+ interval_restore_expired_ranges(it);
+ it = it->next_child;
+ }
+ }
+
cu->is_reg_alloc_done = true;
return 0;
--
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
