Re: [PATCH 3/3] spill-reload: Use radix_tree_lookup() in insert_mov_insns()
Ack here as well, this is obviously correct (provided radix_tree_lookup()
works).
On Tue, 18 Aug 2009 21:41:19 +0300
Pekka Enberg penb...@cs.helsinki.fi wrote:
Lets use radix_tree_lookup() and get rid of the nasty loop in
bb_last_insn(). For some reason, this seems to fix the infinite loop
triggered by empty basic blocks.
Cc: Arthur HUILLET arthur.huil...@free.fr
Cc: Tomek Grabiec tgrab...@gmail.com
Signed-off-by: Pekka Enberg penb...@cs.helsinki.fi
---
jit/basic-block.c | 16 +---
jit/spill-reload.c |2 +-
2 files changed, 2 insertions(+), 16 deletions(-)
diff --git a/jit/basic-block.c b/jit/basic-block.c
index 6de5c3f..dbf3675 100644
--- a/jit/basic-block.c
+++ b/jit/basic-block.c
@@ -176,21 +176,7 @@ struct insn *bb_first_insn(struct basic_block *bb)
struct insn *bb_last_insn(struct basic_block *bb)
{
- struct insn *this = list_entry(bb-insn_list.prev, struct insn,
insn_list_node);
-
- /*
- * We want to return the last real instruction of the basic block.
Taking the
- * last of the insn_list will not work in case a live interval has been
spilled
- * right after the final jump of the basic block.
- * This is a side effect of the linear scan algorithm.
- *
- * As a result, we browse instructions starting from the last, in order
to find the one
- * that has a LIR position matching the position for the end of the
block.
- */
- while (this-lir_pos != bb-end_insn - 1) {
- this = list_entry(this-insn_list_node.prev, struct insn,
insn_list_node);
- }
- return this;
+ return list_entry(bb-insn_list.prev, struct insn, insn_list_node);
}
static int __bb_add_neighbor(void *new, void **array, unsigned long *nb)
diff --git a/jit/spill-reload.c b/jit/spill-reload.c
index 5ced80e..515db8a 100644
--- a/jit/spill-reload.c
+++ b/jit/spill-reload.c
@@ -183,7 +183,7 @@ static void insert_mov_insns(struct compilation_unit *cu,
struct insn *spill_at_insn;
int i;
- spill_at_insn = bb_last_insn(from_bb);
+ spill_at_insn = radix_tree_lookup(cu-lir_insn_map, from_bb-end_insn
- 1);
/* Spill all intervals that have to be resolved */
for (i = 0; i nr_mapped; i++) {
--
1.5.6.3
--
Greetings,
A. Huillet
--
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
[PATCH 2/3] spill-reload: Remove redundant argument from insert_copy_slot_insn()
The 'pop_at_insn' argument is not used in insert_copy_slot_insn()
function so remove it to clean up code.
Cc: Arthur HUILLET arthur.huil...@free.fr
Cc: Tomek Grabiec tgrab...@gmail.com
Signed-off-by: Pekka Enberg penb...@cs.helsinki.fi
---
jit/spill-reload.c | 13 +
1 files changed, 5 insertions(+), 8 deletions(-)
diff --git a/jit/spill-reload.c b/jit/spill-reload.c
index bf31288..5ced80e 100644
--- a/jit/spill-reload.c
+++ b/jit/spill-reload.c
@@ -125,8 +125,7 @@ insert_copy_slot_insn(struct live_interval *interval,
struct compilation_unit *cu,
struct stack_slot *from,
struct stack_slot *to,
- struct insn *push_at_insn,
- struct insn *pop_at_insn)
+ struct insn *push_at_insn)
{
struct insn *push, *pop;
@@ -140,7 +139,7 @@ insert_copy_slot_insn(struct live_interval *interval,
free_insn(push);
return warn(out of memory), -ENOMEM;
}
- pop-bytecode_offset = pop_at_insn-bytecode_offset;
+ pop-bytecode_offset = push_at_insn-bytecode_offset;
list_add_tail(push-insn_list_node, push_at_insn-insn_list_node);
list_add(pop-insn_list_node, push-insn_list_node);
@@ -179,10 +178,10 @@ static void insert_mov_insns(struct compilation_unit *cu,
struct basic_block *from_bb,
struct basic_block *to_bb)
{
- int i;
- struct insn *spill_at_insn, *reload_at_insn;
struct live_interval *from_it, *to_it;
struct stack_slot *slots[nr_mapped];
+ struct insn *spill_at_insn;
+ int i;
spill_at_insn = bb_last_insn(from_bb);
@@ -201,12 +200,10 @@ static void insert_mov_insns(struct compilation_unit *cu,
for (i = 0; i nr_mapped; i++) {
to_it = mappings[i].to;
- reload_at_insn = bb_first_insn(to_bb);
-
if (to_it-need_reload to_it-range.start =
to_bb-start_insn) {
insert_copy_slot_insn(mappings[i].to, cu, slots[i],
to_it-spill_parent-spill_slot,
- spill_at_insn, reload_at_insn);
+ spill_at_insn);
continue;
}
--
1.5.6.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
[PATCH 3/3] spill-reload: Use radix_tree_lookup() in insert_mov_insns()
Lets use radix_tree_lookup() and get rid of the nasty loop in
bb_last_insn(). For some reason, this seems to fix the infinite loop
triggered by empty basic blocks.
Cc: Arthur HUILLET arthur.huil...@free.fr
Cc: Tomek Grabiec tgrab...@gmail.com
Signed-off-by: Pekka Enberg penb...@cs.helsinki.fi
---
jit/basic-block.c | 16 +---
jit/spill-reload.c |2 +-
2 files changed, 2 insertions(+), 16 deletions(-)
diff --git a/jit/basic-block.c b/jit/basic-block.c
index 6de5c3f..dbf3675 100644
--- a/jit/basic-block.c
+++ b/jit/basic-block.c
@@ -176,21 +176,7 @@ struct insn *bb_first_insn(struct basic_block *bb)
struct insn *bb_last_insn(struct basic_block *bb)
{
- struct insn *this = list_entry(bb-insn_list.prev, struct insn,
insn_list_node);
-
- /*
-* We want to return the last real instruction of the basic block.
Taking the
-* last of the insn_list will not work in case a live interval has been
spilled
-* right after the final jump of the basic block.
-* This is a side effect of the linear scan algorithm.
-*
-* As a result, we browse instructions starting from the last, in order
to find the one
-* that has a LIR position matching the position for the end of the
block.
-*/
- while (this-lir_pos != bb-end_insn - 1) {
- this = list_entry(this-insn_list_node.prev, struct insn,
insn_list_node);
- }
- return this;
+ return list_entry(bb-insn_list.prev, struct insn, insn_list_node);
}
static int __bb_add_neighbor(void *new, void **array, unsigned long *nb)
diff --git a/jit/spill-reload.c b/jit/spill-reload.c
index 5ced80e..515db8a 100644
--- a/jit/spill-reload.c
+++ b/jit/spill-reload.c
@@ -183,7 +183,7 @@ static void insert_mov_insns(struct compilation_unit *cu,
struct insn *spill_at_insn;
int i;
- spill_at_insn = bb_last_insn(from_bb);
+ spill_at_insn = radix_tree_lookup(cu-lir_insn_map, from_bb-end_insn
- 1);
/* Spill all intervals that have to be resolved */
for (i = 0; i nr_mapped; i++) {
--
1.5.6.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
[PATCH 1/3] spill-reload: Insert spill instructions before branches
Use insn_is_branch() to determine whether we must insert a spill
instruction before or after the last instruction in a basic block.
Cc: Arthur HUILLET arthur.huil...@free.fr
Cc: Tomek Grabiec tgrab...@gmail.com
Signed-off-by: Pekka Enberg penb...@cs.helsinki.fi
---
arch/mmix/include/arch/instruction.h |5 +
arch/x86/include/arch/instruction.h | 17 +
jit/spill-reload.c |8
3 files changed, 26 insertions(+), 4 deletions(-)
diff --git a/arch/mmix/include/arch/instruction.h
b/arch/mmix/include/arch/instruction.h
index 427131a..d12bf83 100644
--- a/arch/mmix/include/arch/instruction.h
+++ b/arch/mmix/include/arch/instruction.h
@@ -108,6 +108,11 @@ exception_spill_insn(struct stack_slot *slot)
return NULL;
}
+static inline bool insn_is_branch(struct insn *insn)
+{
+ return insn-type == INSN_JMP;
+}
+
struct insn *alloc_insn(enum insn_type);
void free_insn(struct insn *);
diff --git a/arch/x86/include/arch/instruction.h
b/arch/x86/include/arch/instruction.h
index f2f858c..8d875b1 100644
--- a/arch/x86/include/arch/instruction.h
+++ b/arch/x86/include/arch/instruction.h
@@ -308,6 +308,23 @@ static inline struct insn *jump_insn(struct basic_block
*bb)
return branch_insn(INSN_JMP_BRANCH, bb);
}
+
+static inline bool insn_is_branch(struct insn *insn)
+{
+ switch (insn-type) {
+ case INSN_JE_BRANCH:
+ case INSN_JGE_BRANCH:
+ case INSN_JG_BRANCH:
+ case INSN_JLE_BRANCH:
+ case INSN_JL_BRANCH:
+ case INSN_JMP_BRANCH:
+ case INSN_JNE_BRANCH:
+ return true;
+ default:
+ return false;
+ }
+}
+
struct insn *alloc_insn(enum insn_type);
void free_insn(struct insn *);
diff --git a/jit/spill-reload.c b/jit/spill-reload.c
index 17b5134..bf31288 100644
--- a/jit/spill-reload.c
+++ b/jit/spill-reload.c
@@ -68,7 +68,7 @@ static struct insn *last_insn(struct compilation_unit *cu,
struct live_interval
static struct stack_slot *
spill_interval(struct live_interval *interval,
struct compilation_unit *cu,
- struct insn *last, bool tail)
+ struct insn *last)
{
struct stack_slot *slot;
struct insn *spill;
@@ -83,7 +83,7 @@ spill_interval(struct live_interval *interval,
spill-bytecode_offset = last-bytecode_offset;
- if (tail)
+ if (insn_is_branch(last))
list_add_tail(spill-insn_list_node, last-insn_list_node);
else
list_add(spill-insn_list_node, last-insn_list_node);
@@ -94,7 +94,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(cu,
interval), false);
+ interval-spill_slot = spill_interval(interval, cu, last_insn(cu,
interval));
if (!interval-spill_slot)
return warn(out of memory), -ENOMEM;
@@ -193,7 +193,7 @@ static void insert_mov_insns(struct compilation_unit *cu,
if (from_it-need_spill from_it-range.end
from_bb-end_insn) {
slots[i] = from_it-spill_slot;
} else {
- slots[i] = spill_interval(from_it, cu, spill_at_insn,
true);
+ slots[i] = spill_interval(from_it, cu, spill_at_insn);
}
}
--
1.5.6.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
Re: [PATCH 3/3] spill-reload: Use radix_tree_lookup() in insert_mov_insns()
2009/8/18 Pekka Enberg penb...@cs.helsinki.fi:
Lets use radix_tree_lookup() and get rid of the nasty loop in
bb_last_insn(). For some reason, this seems to fix the infinite loop
triggered by empty basic blocks.
Cc: Arthur HUILLET arthur.huil...@free.fr
Cc: Tomek Grabiec tgrab...@gmail.com
Signed-off-by: Pekka Enberg penb...@cs.helsinki.fi
---
jit/basic-block.c | 16 +---
jit/spill-reload.c | 2 +-
2 files changed, 2 insertions(+), 16 deletions(-)
diff --git a/jit/basic-block.c b/jit/basic-block.c
index 6de5c3f..dbf3675 100644
--- a/jit/basic-block.c
+++ b/jit/basic-block.c
@@ -176,21 +176,7 @@ struct insn *bb_first_insn(struct basic_block *bb)
struct insn *bb_last_insn(struct basic_block *bb)
{
- struct insn *this = list_entry(bb-insn_list.prev, struct insn,
insn_list_node);
-
- /*
- * We want to return the last real instruction of the basic block.
Taking the
- * last of the insn_list will not work in case a live interval has
been spilled
- * right after the final jump of the basic block.
- * This is a side effect of the linear scan algorithm.
- *
- * As a result, we browse instructions starting from the last, in
order to find the one
- * that has a LIR position matching the position for the end of the
block.
- */
- while (this-lir_pos != bb-end_insn - 1) {
- this = list_entry(this-insn_list_node.prev, struct insn,
insn_list_node);
- }
- return this;
+ return list_entry(bb-insn_list.prev, struct insn, insn_list_node);
}
static int __bb_add_neighbor(void *new, void **array, unsigned long *nb)
diff --git a/jit/spill-reload.c b/jit/spill-reload.c
index 5ced80e..515db8a 100644
--- a/jit/spill-reload.c
+++ b/jit/spill-reload.c
@@ -183,7 +183,7 @@ static void insert_mov_insns(struct compilation_unit *cu,
struct insn *spill_at_insn;
int i;
- spill_at_insn = bb_last_insn(from_bb);
+ spill_at_insn = radix_tree_lookup(cu-lir_insn_map,
from_bb-end_insn - 1);
/* Spill all intervals that have to be resolved */
for (i = 0; i nr_mapped; i++) {
--
1.5.6.3
Like I said on IRC, this will not work for empty basic blocks, because
spill_at_insn will belong to the preceding
basic block. This causes that instructions will be added to different
(preceding) basic block and might not be executed on some
execution paths.
--
Tomek Grabiec
--
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
Re: [PATCH 3/3] spill-reload: Use radix_tree_lookup() in insert_mov_insns()
On Tue, 2009-08-18 at 21:21 +0200, Tomek Grabiec wrote:
Like I said on IRC, this will not work for empty basic blocks, because
spill_at_insn will belong to the preceding
basic block. This causes that instructions will be added to different
(preceding) basic block and might not be executed on some
execution paths.
I think the following patch _is_ correct but it breaks make regression
so I think we're silently spilling/reloading empty basic blocks.
Pekka
From 999622798d073ae892c316e6f69fde7697233e4d Mon Sep 17 00:00:00 2001
From: Pekka Enberg penb...@cs.helsinki.fi
Date: Tue, 18 Aug 2009 21:12:22 +0300
Subject: [PATCH] spill-reload: Use radix_tree_lookup() in bb_last_insn()
Lets use radix_tree_lookup() and get rid of the nasty loop in
bb_last_insn().
Cc: Arthur HUILLET arthur.huil...@free.fr
Cc: Tomek Grabiec tgrab...@gmail.com
Signed-off-by: Pekka Enberg penb...@cs.helsinki.fi
---
include/jit/basic-block.h |5 +
jit/basic-block.c | 23 ---
jit/spill-reload.c|3 ++-
3 files changed, 15 insertions(+), 16 deletions(-)
diff --git a/include/jit/basic-block.h b/include/jit/basic-block.h
index e50f6c6..e1d8c86 100644
--- a/include/jit/basic-block.h
+++ b/include/jit/basic-block.h
@@ -74,6 +74,11 @@ static inline struct basic_block *bb_entry(struct list_head
*head)
return list_entry(head, struct basic_block, bb_list_node);
}
+static inline bool bb_is_empty(struct basic_block *bb)
+{
+ return list_is_empty(bb-stmt_list);
+}
+
struct basic_block *alloc_basic_block(struct compilation_unit *, unsigned
long, unsigned long);
struct basic_block *get_basic_block(struct compilation_unit *, unsigned long,
unsigned long);
void free_basic_block(struct basic_block *);
diff --git a/jit/basic-block.c b/jit/basic-block.c
index 6de5c3f..0f40bcc 100644
--- a/jit/basic-block.c
+++ b/jit/basic-block.c
@@ -176,21 +176,14 @@ struct insn *bb_first_insn(struct basic_block *bb)
struct insn *bb_last_insn(struct basic_block *bb)
{
- struct insn *this = list_entry(bb-insn_list.prev, struct insn,
insn_list_node);
-
- /*
-* We want to return the last real instruction of the basic block.
Taking the
-* last of the insn_list will not work in case a live interval has been
spilled
-* right after the final jump of the basic block.
-* This is a side effect of the linear scan algorithm.
-*
-* As a result, we browse instructions starting from the last, in order
to find the one
-* that has a LIR position matching the position for the end of the
block.
-*/
- while (this-lir_pos != bb-end_insn - 1) {
- this = list_entry(this-insn_list_node.prev, struct insn,
insn_list_node);
- }
- return this;
+ unsigned long pos = bb-end_insn - 1;
+
+ if (bb_is_empty(bb))
+ return NULL;
+
+ assert(pos = bb-start_insn);
+
+ return radix_tree_lookup(bb-b_parent-lir_insn_map, pos);
}
static int __bb_add_neighbor(void *new, void **array, unsigned long *nb)
diff --git a/jit/spill-reload.c b/jit/spill-reload.c
index 5ced80e..a8806f1 100644
--- a/jit/spill-reload.c
+++ b/jit/spill-reload.c
@@ -183,7 +183,8 @@ static void insert_mov_insns(struct compilation_unit *cu,
struct insn *spill_at_insn;
int i;
- spill_at_insn = bb_last_insn(from_bb);
+ spill_at_insn = bb_last_insn(from_bb);
+ assert(spill_at_insn != NULL);
/* Spill all intervals that have to be resolved */
for (i = 0; i nr_mapped; i++) {
--
1.5.6.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
