This is needed for precise modeling of live ranges.

Signed-off-by: Tomek Grabiec <tgrab...@gmail.com>
---
 include/jit/vars.h          |   83 +++++++++++++---
 jit/interval.c              |  228 +++++++++++++++++++++++++++++++++++++++++-
 jit/linear-scan.c           |   51 ++++++----
 jit/liveness.c              |   24 +++--
 jit/spill-reload.c          |   12 +-
 jit/trace-jit.c             |   26 +++--
 test/jit/linear-scan-test.c |   18 +---
 test/jit/live-range-test.c  |   50 ++++++++++
 test/jit/liveness-test.c    |    8 +-
 9 files changed, 421 insertions(+), 79 deletions(-)

diff --git a/include/jit/vars.h b/include/jit/vars.h
index 6afb16b..f00c5f9 100644
--- a/include/jit/vars.h
+++ b/include/jit/vars.h
@@ -10,18 +10,9 @@
 
 struct live_range {
        unsigned long start, end;       /* end is exclusive */
+       struct list_head range_list_node;
 };
 
-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);
@@ -69,8 +60,21 @@ struct live_interval {
        /* Parent variable of this interval.  */
        struct var_info *var_info;
 
-       /* Live range of this interval.  */
-       struct live_range range;
+       /* Live ranges of this interval. List of not overlaping and
+          not adjacent ranges sorted in ascending order. */
+       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.
+        */
+       struct live_range *current_range;
 
        /* Linked list of child intervals.  */
        struct live_interval *next_child, *prev_child;
@@ -118,11 +122,66 @@ mark_need_reload(struct live_interval *it, struct 
live_interval *parent)
        it->spill_parent = parent;
 }
 
+static inline struct live_range *node_to_range(struct list_head *node)
+{
+       return list_entry(node, struct live_range, range_list_node);
+}
+
+static inline struct live_range *
+next_range(struct list_head *list, struct live_range *range)
+{
+       if (range->range_list_node.next == list)
+               return NULL;
+
+       return list_entry(range->range_list_node.next, struct live_range,
+                         range_list_node);
+}
+
+static inline unsigned long interval_start(struct live_interval *it)
+{
+       assert(!list_is_empty(&it->range_list));
+       return node_to_range(it->range_list.next)->start;
+}
+
+static inline unsigned long interval_end(struct live_interval *it)
+{
+       assert(!list_is_empty(&it->range_list));
+       return node_to_range(it->range_list.prev)->end;
+}
+
+static inline unsigned long interval_last_insn_pos(struct live_interval *it)
+{
+       return (interval_end(it) - 1) & ~1ul;
+}
+
+static inline unsigned long interval_first_insn_pos(struct live_interval *it)
+{
+       return interval_start(it) & ~1ul;
+}
+
+static inline bool interval_is_empty(struct live_interval *it)
+{
+       return list_is_empty(&it->range_list);
+}
+
+static inline struct live_range *interval_first_range(struct live_interval *it)
+{
+       assert(!interval_is_empty(it));
+       return list_first_entry(&it->range_list, struct live_range,
+                               range_list_node);
+}
+
 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);
+bool intervals_intersect(struct live_interval *, struct live_interval *);
+unsigned long interval_intersection_start(struct live_interval *, struct 
live_interval *);
+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);
 
 #endif /* __JIT_VARS_H */
diff --git a/jit/interval.c b/jit/interval.c
index 9ad9d97..9e22c0c 100644
--- a/jit/interval.c
+++ b/jit/interval.c
@@ -35,6 +35,65 @@
 #include <string.h>
 #include <errno.h>
 
+static struct live_range *alloc_live_range(unsigned long start, unsigned long 
end)
+{
+       struct live_range *range;
+
+       range = malloc(sizeof *range);
+       if (!range)
+               return NULL;
+
+       range->start = start;
+       range->end = end;
+       INIT_LIST_HEAD(&range->range_list_node);
+       return range;
+}
+
+static int split_ranges(struct live_interval *new, struct live_interval *it,
+                       unsigned long pos)
+{
+       struct live_range *this;
+
+       list_for_each_entry(this, &it->range_list, range_list_node) {
+               struct live_range *next;
+
+               if (!in_range(this, pos))
+                       continue;
+
+               next = next_range(&it->range_list, this);
+
+               if (this->start == pos) {
+                       list_move(&this->range_list_node, &new->range_list);
+               } else {
+                       struct live_range *range;
+
+                       range = alloc_live_range(pos, this->end);
+                       if (!range)
+                               return -ENOMEM;
+
+                       this->end = pos;
+                       list_add(&range->range_list_node, &new->range_list);
+               }
+
+               this = next;
+               if (!this)
+                       return 0;
+
+               while (&this->range_list_node != &it->range_list) {
+                       struct list_head *next;
+
+                       next = this->range_list_node.next;
+
+                       list_move(&this->range_list_node, new->range_list.prev);
+                       this = node_to_range(next);
+               }
+
+               return 0;
+       }
+
+       error("pos is not within an interval live ranges");
+}
+
 struct live_interval *alloc_interval(struct var_info *var)
 {
        struct live_interval *interval = zalloc(sizeof *interval);
@@ -42,11 +101,10 @@ struct live_interval *alloc_interval(struct var_info *var)
                interval->var_info = var;
                interval->reg = MACH_REG_UNASSIGNED;
                interval->fixed_reg = false;
-               interval->range.start = ~0UL;
-               interval->range.end = 0UL;
                interval->spill_reload_reg.interval = interval;
                INIT_LIST_HEAD(&interval->interval_node);
                INIT_LIST_HEAD(&interval->use_positions);
+               INIT_LIST_HEAD(&interval->range_list);
        }
        return interval;
 }
@@ -56,6 +114,11 @@ void free_interval(struct live_interval *interval)
        if (interval->next_child)
                free_interval(interval->next_child);
 
+       struct live_range *this, *next;
+       list_for_each_entry_safe(this, next, &interval->range_list, 
range_list_node) {
+               free(this);
+       }
+
        free(interval);
 }
 
@@ -65,14 +128,21 @@ struct live_interval *split_interval_at(struct 
live_interval *interval,
        struct use_position *this, *next;
        struct live_interval *new;
 
+       assert(pos > interval_start(interval));
+       assert(pos < interval_end(interval));
+
        new = alloc_interval(interval->var_info);
        if (!new)
                return NULL;
 
        new->reg = MACH_REG_UNASSIGNED;
-       new->range.start = pos;
-       new->range.end = interval->range.end;
-       interval->range.end = pos;
+
+       if (split_ranges(new, interval, pos)) {
+               free(new);
+               return NULL;
+       }
+
+       new->current_range = interval_first_range(new);
 
        new->fixed_reg = interval->fixed_reg;
        if (new->fixed_reg)
@@ -128,12 +198,58 @@ 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)
+{
+       if (pos < interval_start(it) || pos >= interval_end(it))
+               return;
+
+       assert (pos >= it->current_range->start);
+
+       while (!in_range(it->current_range, pos)) {
+               struct live_range *next;
+
+               next = next_range(&it->range_list, it->current_range);
+               if (pos < next->start)
+                       break;
+
+               it->current_range = next;
+       }
+}
+
+struct live_range *interval_range_at(struct live_interval *it, unsigned long 
pos)
+{
+       struct live_range *range;
+
+       if (pos < interval_start(it) || pos >= interval_end(it))
+               return NULL;
+
+       range = it->current_range;
+       if (pos < range->start)
+               range = interval_first_range(it);
+
+       while (range && pos >= range->start) {
+               if (in_range(range, pos))
+                       return range;
+
+               range = next_range(&it->range_list, range);
+       }
+
+       return NULL;
+}
+
 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))
+               struct live_range *range;
+
+               range = interval_range_at(it, pos);
+               if (range)
                        return it;
 
                it = it->next_child;
@@ -141,3 +257,103 @@ struct live_interval *interval_child_at(struct 
live_interval *parent, unsigned l
 
        return NULL;
 }
+
+bool intervals_intersect(struct live_interval *it1, struct live_interval *it2)
+{
+       struct live_range *r1, *r2;
+
+       if (interval_start(it1) >= interval_end(it2) ||
+           interval_start(it2) >= interval_end(it1))
+               return false;
+
+       if (interval_is_empty(it1) || interval_is_empty(it2))
+               return false;
+
+       r1 = it1->current_range;
+       r2 = it2->current_range;
+
+       while (r1 && r1->end <= r2->start)
+               r1 = next_range(&it1->range_list, r1);
+
+       while (r2 && r2->end <= r1->start)
+               r2 = next_range(&it2->range_list, r2);
+
+       while (r1 && r2) {
+               if (ranges_intersect(r1, r2))
+                       return true;
+
+               if (r1->start < r2->start)
+                       r1 = next_range(&it1->range_list, r1);
+               else
+                       r2 = next_range(&it2->range_list, r2);
+       }
+
+       return false;
+}
+
+unsigned long
+interval_intersection_start(struct live_interval *it1, struct live_interval 
*it2)
+{
+       struct live_range *r1, *r2;
+
+       assert(!interval_is_empty(it1) && !interval_is_empty(it2));
+
+       r1 = it1->current_range;
+       r2 = it2->current_range;
+
+       while (r1 && r1->end <= r2->start)
+               r1 = next_range(&it1->range_list, r1);
+
+       while (r2 && r2->end <= r1->start)
+               r2 = next_range(&it2->range_list, r2);
+
+       while (r1 && r2) {
+               if (ranges_intersect(r1, r2))
+                       return range_intersection_start(r1, r2);
+
+               if (r1->start < r2->start)
+                       r1 = next_range(&it1->range_list, r1);
+               else
+                       r2 = next_range(&it2->range_list, r2);
+       }
+
+       error("intervals do not overlap");
+}
+
+bool interval_covers(struct live_interval *it, unsigned long pos)
+{
+       return interval_range_at(it, pos) != NULL;
+}
+
+int interval_add_range(struct live_interval *it, unsigned long start,
+                      unsigned long end)
+{
+       struct live_range *range, *next, *new;
+
+       new = alloc_live_range(start, end);
+       if (!new)
+               return -ENOMEM;
+
+       list_for_each_entry_safe(range, next, &it->range_list, range_list_node) 
{
+               if (range->start > end)
+                       break;
+
+               if (range->start <= new->end && new->start <= range->end) {
+                       new->start = min(new->start, range->start);
+                       new->end = max(new->end, range->end);
+                       list_del(&range->range_list_node);
+                       free(range);
+               }
+       }
+
+       list_for_each_entry_safe(range, next, &it->range_list, range_list_node) 
{
+               if (new->start > range->start)
+                       continue;
+
+               list_add_tail(&new->range_list_node, &range->range_list_node);
+               return 0;
+       }
+
+       list_add_tail(&new->range_list_node, &it->range_list);
+       return 0;
+}
diff --git a/jit/linear-scan.c b/jit/linear-scan.c
index 8baa914..765cea9 100644
--- a/jit/linear-scan.c
+++ b/jit/linear-scan.c
@@ -120,7 +120,7 @@ static void spill_interval(struct live_interval *it, 
unsigned long pos,
                unsigned long next_pos = next_use_pos(new, 0);
 
                /* Trim interval if it does not start with a use position. */
-               if (next_pos > new->range.start)
+               if (next_pos > interval_start(new))
                        new = split_interval_at(new, next_pos);
 
                it->need_spill = true;
@@ -137,13 +137,13 @@ static void __spill_interval_intersecting(struct 
live_interval *current,
        if (it->reg != reg)
                return;
 
-       if (!ranges_intersect(&it->range, &current->range))
+       if (!intervals_intersect(it, current))
                return;
 
-       if (current->range.start == it->range.start)
+       if (interval_start(current) == interval_start(it))
                return;
 
-       spill_interval(it, current->range.start, unhandled);
+       spill_interval(it, interval_start(current), unhandled);
 }
 
 static void spill_all_intervals_intersecting(struct live_interval *current,
@@ -185,7 +185,7 @@ static void allocate_blocked_reg(struct live_interval 
*current,
                if (it->fixed_reg)
                        continue;
 
-               pos = next_use_pos(it, current->range.start);
+               pos = next_use_pos(it, interval_start(current));
                set_use_pos(use_pos, it->reg, pos);
        }
 
@@ -195,8 +195,8 @@ static void allocate_blocked_reg(struct live_interval 
*current,
                if (it->fixed_reg)
                        continue;
 
-               if (ranges_intersect(&it->range, &current->range)) {
-                       pos = next_use_pos(it, current->range.start);
+               if (intervals_intersect(it, current)) {
+                       pos = next_use_pos(it, interval_start(current));
                        set_use_pos(use_pos, it->reg, pos);
                }
        }
@@ -212,10 +212,10 @@ static void allocate_blocked_reg(struct live_interval 
*current,
                if (!it->fixed_reg)
                        continue;
 
-               if (ranges_intersect(&it->range, &current->range)) {
+               if (intervals_intersect(it, current)) {
                        unsigned long pos;
 
-                       pos = range_intersection_start(&it->range, 
&current->range);
+                       pos = interval_intersection_start(it, current);
                        set_block_pos(block_pos, use_pos, it->reg, pos);
                }
        }
@@ -228,7 +228,7 @@ static void allocate_blocked_reg(struct live_interval 
*current,
                 * All active and inactive intervals are used before current,
                 * so it is best to spill current itself
                 */
-               pos = next_use_pos(current, current->range.start);
+               pos = next_use_pos(current, interval_start(current));
                spill_interval(current, pos, unhandled);
        } else {
                /*
@@ -236,7 +236,7 @@ static void allocate_blocked_reg(struct live_interval 
*current,
                 */
                current->reg = reg;
 
-               if (block_pos[reg] < current->range.end)
+               if (block_pos[reg] < interval_start(current))
                        spill_interval(current, block_pos[reg], unhandled);
 
                spill_all_intervals_intersecting(current, reg, active,
@@ -262,10 +262,10 @@ static void try_to_allocate_free_reg(struct live_interval 
*current,
        }
 
        list_for_each_entry(it, inactive, interval_node) {
-               if (ranges_intersect(&it->range, &current->range)) {
+               if (intervals_intersect(it, current)) {
                        unsigned long pos;
 
-                       pos = range_intersection_start(&it->range, 
&current->range);
+                       pos = interval_intersection_start(it, current);
                        set_free_pos(free_until_pos, it->reg, pos);
                }
        }
@@ -278,7 +278,7 @@ static void try_to_allocate_free_reg(struct live_interval 
*current,
                return;
        }
 
-       if (current->range.end <= free_until_pos[reg]) {
+       if (interval_end(current) <= free_until_pos[reg]) {
                /*
                 * Register available for the full interval.
                 */
@@ -297,7 +297,7 @@ static int interval_compare(void *a, void *b)
        struct live_interval *x = a;
        struct live_interval *y = b;
 
-       return (int)(y->range.start - x->range.start);
+       return (int)(interval_start(y) - interval_start(x));
 }
 
 int allocate_registers(struct compilation_unit *cu)
@@ -327,6 +327,11 @@ int allocate_registers(struct compilation_unit *cu)
         * non-fixed interval.
         */
        for_each_variable(var, cu->var_infos) {
+               if (interval_is_empty(var->interval))
+                       continue;
+
+               var->interval->current_range = 
interval_first_range(var->interval);
+
                if (var->interval->fixed_reg)
                        list_add(&var->interval->interval_node, &inactive);
                else
@@ -338,29 +343,35 @@ int allocate_registers(struct compilation_unit *cu)
                unsigned long position;
 
                current = pqueue_remove_top(unhandled);
-               position = current->range.start;
+               position = interval_start(current);
 
                list_for_each_entry_safe(it, prev, &active, interval_node) {
-                       if (it->range.end <= position) {
+                       if (interval_end(it) <= position) {
                                /*
                                 * Remove handled interval from active list.
                                 */
                                list_del(&it->interval_node);
                                continue;
                        }
-                       if (!in_range(&it->range, position))
+
+                       interval_update_current_range(it, position);
+
+                       if (!interval_covers(it, position))
                                list_move(&it->interval_node, &inactive);
                }
 
                list_for_each_entry_safe(it, prev, &inactive, interval_node) {
-                       if (it->range.end <= position) {
+                       if (interval_end(it) <= position) {
                                /*
                                 * Remove handled interval from inactive list.
                                 */
                                list_del(&it->interval_node);
                                continue;
                        }
-                       if (in_range(&it->range, position))
+
+                       interval_update_current_range(it, position);
+
+                       if (interval_covers(it, position))
                                list_move(&it->interval_node, &active);
                }
 
diff --git a/jit/liveness.c b/jit/liveness.c
index 3e0f586..ee01989 100644
--- a/jit/liveness.c
+++ b/jit/liveness.c
@@ -36,13 +36,19 @@
 #include <errno.h>
 #include <stdlib.h>
 
-static void __update_live_range(struct live_range *range, unsigned long pos)
+static void __update_live_range(struct live_interval *it, unsigned long pos)
 {
-       if (range->start > pos)
-               range->start = pos;
+       if (interval_is_empty(it))
+               interval_add_range(it, pos, pos + 1);
+       else {
+               struct live_range *r = interval_first_range(it);
 
-       if (range->end < (pos + 1))
-               range->end = pos + 1;
+               if (r->start > pos)
+                       r->start = pos;
+
+               if (r->end < (pos + 1))
+                       r->end = pos + 1;
+       }
 }
 
 static void update_live_ranges(struct compilation_unit *cu)
@@ -54,10 +60,10 @@ static void update_live_ranges(struct compilation_unit *cu)
 
                for_each_variable(var, cu->var_infos) {
                        if (test_bit(this->live_in_set->bits, var->vreg))
-                               __update_live_range(&var->interval->range, 
this->start_insn);
+                               __update_live_range(var->interval, 
this->start_insn);
 
                        if (test_bit(this->live_out_set->bits, var->vreg))
-                               __update_live_range(&var->interval->range, 
this->end_insn);
+                               __update_live_range(var->interval, 
this->end_insn);
                }
        }
 }
@@ -134,7 +140,7 @@ static void __analyze_use_def(struct basic_block *bb, 
struct insn *insn)
        for (i = 0; i < nr_uses; i++) {
                struct var_info *var = uses[i];
 
-               __update_live_range(&var->interval->range, insn->lir_pos);
+               __update_live_range(var->interval, insn->lir_pos);
 
                /*
                 * It's in the use set if and only if it has not
@@ -148,7 +154,7 @@ static void __analyze_use_def(struct basic_block *bb, 
struct insn *insn)
        for (i = 0; i < nr_defs; i++) {
                struct var_info *var = defs[i];
 
-               __update_live_range(&var->interval->range, insn->lir_pos);
+               __update_live_range(var->interval, insn->lir_pos);
                set_bit(bb->def_set->bits, var->vreg);
        }
 }
diff --git a/jit/spill-reload.c b/jit/spill-reload.c
index 5964682..f434547 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, 
range_first_insn_pos(&interval->range));
+       ret = radix_tree_lookup(cu->lir_insn_map, 
interval_first_insn_pos(interval));
        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, 
range_last_insn_pos(&interval->range));
+       ret = radix_tree_lookup(cu->lir_insn_map, 
interval_last_insn_pos(interval));
        assert(ret != NULL);
 
        return ret;
@@ -186,7 +186,7 @@ static int __insert_spill_reload_insn(struct live_interval 
*interval, struct com
 {
        int err = 0;
 
-       if (range_is_empty(&interval->range))
+       if (interval_is_empty(interval))
                goto out;
 
        if (interval->need_reload) {
@@ -198,7 +198,7 @@ static int __insert_spill_reload_insn(struct live_interval 
*interval, struct com
                 * can't insert a reload instruction in the middle of
                 * instruction.
                 */
-               assert((interval->range.start & 1) == 0);
+               assert((interval_start(interval) & 1) == 0);
 
                err = insert_reload_insn(interval, cu,
                                interval->spill_parent->spill_slot,
@@ -235,7 +235,7 @@ static void insert_mov_insns(struct compilation_unit *cu,
        for (i = 0; i < nr_mapped; i++) {
                from_it         = mappings[i].from;
 
-               if (from_it->need_spill && from_it->range.end < 
from_bb->end_insn) {
+               if (from_it->need_spill && interval_end(from_it) < 
from_bb->end_insn) {
                        slots[i] = from_it->spill_slot;
                } else {
                        slots[i] = spill_interval(from_it, cu, spill_before, 
bc_offset);
@@ -246,7 +246,7 @@ static void insert_mov_insns(struct compilation_unit *cu,
        for (i = 0; i < nr_mapped; i++) {
                to_it           = mappings[i].to;
 
-               if (to_it->need_reload && to_it->range.start >= 
to_bb->start_insn) {
+               if (to_it->need_reload && interval_start(to_it) >= 
to_bb->start_insn) {
                        insert_copy_slot_insn(mappings[i].to, cu, slots[i],
                                              to_it->spill_parent->spill_slot,
                                              spill_before, bc_offset);
diff --git a/jit/trace-jit.c b/jit/trace-jit.c
index 3b2823e..c648a40 100644
--- a/jit/trace-jit.c
+++ b/jit/trace-jit.c
@@ -238,14 +238,14 @@ print_var_liveness(struct compilation_unit *cu, struct 
var_info *var)
        interval = var->interval;
        offset = 0;
 
-       if (range_is_empty(&interval->range))
+       if (interval_is_empty(interval))
                goto skip;
 
-       for (; offset < interval->range.start; offset++)
+       for (; offset < interval_start(interval); offset++)
                trace_printf("   ");
 
-       for (; offset < interval->range.end; offset++) {
-               if (in_range(&interval->range, offset)) {
+       for (; offset < interval_end(interval); offset++) {
+               if (interval_covers(interval, offset)) {
                        if (next_use_pos(var->interval, offset) == offset) {
                                /* In use */
                                trace_printf("UUU");
@@ -263,10 +263,10 @@ print_var_liveness(struct compilation_unit *cu, struct 
var_info *var)
        for (; offset < cu->last_insn; offset++)
                trace_printf("   ");
 
-       if (!range_is_empty(&interval->range))
+       if (!interval_is_empty(interval))
                trace_printf(" (start: %2lu, end: %2lu)\n",
-                            interval->range.start,
-                            interval->range.end);
+                            interval_start(interval),
+                            interval_end(interval));
        else
                trace_printf(" (empty)\n");
 }
@@ -349,7 +349,15 @@ void trace_regalloc(struct compilation_unit *cu)
                struct live_interval *interval;
 
                for (interval = var->interval; interval != NULL; interval = 
interval->next_child) {
-                       trace_printf("  %2lu (pos: %2ld-%2lu):", var->vreg, 
(signed long)interval->range.start, interval->range.end);
+                       trace_printf("  %2lu ", var->vreg);
+
+                       if (interval_is_empty(interval))
+                               trace_printf("(empty)       :");
+                       else
+                               trace_printf("(pos: %3lu-%3lu):",
+                                            interval_start(interval),
+                                            interval_end(interval));
+
                        trace_printf("\t%s", reg_name(interval->reg));
                        trace_printf("\t%s", interval->fixed_reg ? "fixed\t" : 
"non-fixed");
                        if (interval->need_spill) {
@@ -409,7 +417,7 @@ static void print_gc_map(struct compilation_unit *cu, 
struct insn *insn)
                if (!test_bit(live_vars->bits, i++))
                        continue;
 
-               if (in_range(&var->interval->range, insn->lir_pos)) {
+               if (interval_covers(var->interval, insn->lir_pos)) {
                        trace_printf("%d (%s), ",
                                var->vreg, reg_name(var->interval->reg));
                } else if (var->interval->need_spill) {
diff --git a/test/jit/linear-scan-test.c b/test/jit/linear-scan-test.c
index b742084..433c503 100644
--- a/test/jit/linear-scan-test.c
+++ b/test/jit/linear-scan-test.c
@@ -19,12 +19,10 @@ void 
test_allocates_different_registers_for_overlapping_intervals(void)
        cu = compilation_unit_alloc(&method);
 
        v1 = get_var(cu, J_INT);
-       v1->interval->range.start = 0;
-       v1->interval->range.end   = 2;
+       interval_add_range(v1->interval, 0, 2);
 
        v2 = get_var(cu, J_INT);
-       v2->interval->range.start = 1;
-       v2->interval->range.end   = 2;
+       interval_add_range(v2->interval, 1, 2);
 
        allocate_registers(cu);
 
@@ -41,12 +39,10 @@ void 
test_reuses_registers_for_non_overlapping_intervals(void)
        cu = compilation_unit_alloc(&method);
 
        v1 = get_var(cu, J_INT);
-       v1->interval->range.start = 0;
-       v1->interval->range.end   = 2;
+       interval_add_range(v1->interval, 0, 2);
 
        v2 = get_var(cu, J_INT);
-       v2->interval->range.start = 2;
-       v2->interval->range.end   = 4;
+       interval_add_range(v2->interval, 2, 4);
 
        allocate_registers(cu);
 
@@ -63,12 +59,10 @@ void 
test_honors_fixed_interval_register_constraint_for_overlapping_intervals(vo
        cu = compilation_unit_alloc(&method);
 
        v1 = get_fixed_var(cu, R0);
-       v1->interval->range.start = 0;
-       v1->interval->range.end   = 2;
+       interval_add_range(v1->interval, 0, 2);
 
        v2 = get_var(cu, J_INT);
-       v2->interval->range.start = 0;
-       v2->interval->range.end   = 2;
+       interval_add_range(v2->interval, 0, 2);
 
        allocate_registers(cu);
 
diff --git a/test/jit/live-range-test.c b/test/jit/live-range-test.c
index 0f0f626..a078218 100644
--- a/test/jit/live-range-test.c
+++ b/test/jit/live-range-test.c
@@ -84,3 +84,53 @@ void test_ranges_that_do_not_intersect(void)
        assert_false(ranges_intersect(&range1, &range2));
        assert_false(ranges_intersect(&range2, &range1));
 }
+
+void test_interval_add_range(void)
+{
+       struct live_interval it;
+       struct live_range *r;
+
+       INIT_LIST_HEAD(&it.range_list);
+
+       interval_add_range(&it, 1, 3);
+       r = interval_first_range(&it);
+       assert_int_equals(1, r->start);
+       assert_int_equals(3, r->end);
+       assert_ptr_equals(NULL, next_range(&it.range_list, r));
+
+       interval_add_range(&it, 5, 7);
+       r = interval_first_range(&it);
+       assert_int_equals(1, r->start);
+       assert_int_equals(3, r->end);
+       r = next_range(&it.range_list, r);
+       assert_int_equals(5, r->start);
+       assert_int_equals(7, r->end);
+       assert_ptr_equals(NULL, next_range(&it.range_list, r));
+
+       interval_add_range(&it, 3, 5);
+       r = interval_first_range(&it);
+       assert_int_equals(1, r->start);
+       assert_int_equals(7, r->end);
+       assert_ptr_equals(NULL, next_range(&it.range_list, r));
+
+       interval_add_range(&it, 7, 8);
+       r = interval_first_range(&it);
+       assert_int_equals(1, r->start);
+       assert_int_equals(8, r->end);
+       assert_ptr_equals(NULL, next_range(&it.range_list, r));
+
+       interval_add_range(&it, 10, 13);
+       r = interval_first_range(&it);
+       assert_int_equals(1, r->start);
+       assert_int_equals(8, r->end);
+       r = next_range(&it.range_list, r);
+       assert_int_equals(10, r->start);
+       assert_int_equals(13, r->end);
+       assert_ptr_equals(NULL, next_range(&it.range_list, r));
+
+       interval_add_range(&it, 0, 14);
+       r = interval_first_range(&it);
+       assert_int_equals(0, r->start);
+       assert_int_equals(14, r->end);
+       assert_ptr_equals(NULL, next_range(&it.range_list, r));
+}
diff --git a/test/jit/liveness-test.c b/test/jit/liveness-test.c
index 19f01d0..cb85e42 100644
--- a/test/jit/liveness-test.c
+++ b/test/jit/liveness-test.c
@@ -15,8 +15,8 @@ struct vm_method method;
 
 static void assert_live_range(struct live_interval *interval, unsigned long 
expected_start, unsigned long expected_end)
 {
-       assert_int_equals(expected_start, interval->range.start);
-       assert_int_equals(expected_end, interval->range.end);
+       assert_int_equals(expected_start, interval_start(interval));
+       assert_int_equals(expected_end, interval_end(interval));
 }
 
 static void assert_uses(struct basic_block *bb, struct var_info *var)
@@ -35,9 +35,7 @@ static void assert_insn_at_equals(struct insn *insn, struct 
compilation_unit *cu
 {
        struct insn *insn2;
 
-       insn2 = radix_tree_lookup(cu->lir_insn_map,
-               interval->range.start + offset);
-
+       insn2 = radix_tree_lookup(cu->lir_insn_map, interval_start(interval) + 
offset);
        assert_ptr_equals(insn, insn2);
 }
 
-- 
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

Reply via email to