The mimic stack propagation procedure was pushing elements onto
successors' stacks on every CFG edge. This caused that the successor's
stack was larger then it should be. Suppose we have basic block X,
which has N predecessors. For each X's predecessor, Q elements were
pushed onto X's mimic stack, so finally it had N*Q elements instead of
Q. The X's mimic stack was then also propagated, along with extra
elements. This led to generation of many unnecessary register moves.
In some CFG configurations this may lead to degenerative mimic stack
resolution, where STMT_STORE is inserted with src temporary that is
assigned only on some paths. This leads to incorrect liveness analysis
of the temporary register, because it is seen to be used before it is
defined. The register appears to be always live before it's use
position, which is wrong, and could cause problems with GC.
Signed-off-by: Tomek Grabiec <tgrab...@gmail.com>
---
include/jit/basic-block.h | 9 ++++++++
include/lib/stack.h | 11 +++++++++-
jit/basic-block.c | 1 +
jit/bytecode-to-ir.c | 50 ++++++++++++++++++++++++++++++++------------
lib/stack.c | 17 +++++++++++++++
5 files changed, 73 insertions(+), 15 deletions(-)
diff --git a/include/jit/basic-block.h b/include/jit/basic-block.h
index b3e3cc1..e175eba 100644
--- a/include/jit/basic-block.h
+++ b/include/jit/basic-block.h
@@ -46,6 +46,10 @@ struct basic_block {
Adl-Tabatabai et al (1998) for more in-depth explanation. */
struct stack *mimic_stack;
+ /* Holds the size of mimic stack at basic block entry. If
+ mimic stack has not yet been resolved it's set to -1. */
+ long entry_mimic_stack_size;
+
/* Is this basic block an exception handler? */
bool is_eh;
@@ -74,6 +78,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_entry_mimic_stack_set(struct basic_block *bb)
+{
+ return bb->entry_mimic_stack_size != -1;
+}
+
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/include/lib/stack.h b/include/lib/stack.h
index e4e79d9..2a5f6bc 100644
--- a/include/lib/stack.h
+++ b/include/lib/stack.h
@@ -1,9 +1,11 @@
#ifndef LIB_STACK_H
#define LIB_STACK_H
+#include <assert.h>
+#include <errno.h>
+#include <memory.h>
#include <stdbool.h>
#include <stdlib.h>
-#include <assert.h>
struct stack {
unsigned long nr_elements;
@@ -37,4 +39,11 @@ static inline bool stack_is_empty(struct stack *stack)
return !stack->nr_elements;
}
+static inline unsigned long stack_size(struct stack *stack)
+{
+ return stack->nr_elements;
+}
+
+void stack_copy(struct stack *src, struct stack *dst);
+
#endif
diff --git a/jit/basic-block.c b/jit/basic-block.c
index d478315..ff8c11c 100644
--- a/jit/basic-block.c
+++ b/jit/basic-block.c
@@ -41,6 +41,7 @@ struct basic_block *alloc_basic_block(struct compilation_unit
*b_parent, unsigne
bb->b_parent = b_parent;
bb->start = start;
bb->end = end;
+ bb->entry_mimic_stack_size = -1;
return bb;
}
diff --git a/jit/bytecode-to-ir.c b/jit/bytecode-to-ir.c
index 2923890..b9d08a4 100644
--- a/jit/bytecode-to-ir.c
+++ b/jit/bytecode-to-ir.c
@@ -181,8 +181,14 @@ static int do_convert_bb_to_ir(struct basic_block *bb)
buffer.buffer = cu->method->code_attribute.code;
buffer.pos = bb->start;
- if (bb->is_eh)
+ if (bb->is_eh) {
+ assert(!bb_entry_mimic_stack_set(bb));
stack_push(bb->mimic_stack, exception_ref_expr());
+ bb->entry_mimic_stack_size = 1;
+ }
+
+ if (!bb_entry_mimic_stack_set(bb))
+ bb->entry_mimic_stack_size = 0;
while (buffer.pos < bb->end) {
ctx.offset = ctx.buffer->pos; /* this is fragile */
@@ -194,6 +200,32 @@ static int do_convert_bb_to_ir(struct basic_block *bb)
return err;
}
+static int reload_mimic_stack(struct basic_block *bb, struct stack *reload)
+{
+ unsigned int i;
+
+ for (i = 0; i < reload->nr_elements; i++)
+ bb_add_mimic_stack_expr(bb, reload->elements[i]);
+
+ if (bb_entry_mimic_stack_set(bb)) {
+ if (stack_size(reload) == (unsigned long)
bb->entry_mimic_stack_size)
+ return 0;
+
+ return warn("stack size differs on different paths"), -EINVAL;
+ }
+
+ for (i = 0; i < reload->nr_elements; i++) {
+ struct expression *elem;
+
+ elem = reload->elements[reload->nr_elements - i - 1];
+ expr_get(elem);
+ stack_push(bb->mimic_stack, elem);
+ }
+
+ bb->entry_mimic_stack_size = stack_size(bb->mimic_stack);
+ return 0;
+}
+
static int convert_bb_to_ir(struct basic_block *bb)
{
struct stack *reload_stack;
@@ -227,20 +259,10 @@ static int convert_bb_to_ir(struct basic_block *bb)
if (!reload_stack)
return warn("out of memory"), -ENOMEM;
- while (!stack_is_empty(reload_stack)) {
- struct expression *expr = stack_pop(reload_stack);
+ for (i = 0; i < bb->nr_successors; i++)
+ reload_mimic_stack(bb->successors[i], reload_stack);
- for (i = 0; i < bb->nr_successors; i++) {
- struct basic_block *s = bb->successors[i];
-
- expr_get(expr);
-
- bb_add_mimic_stack_expr(s, expr);
-
- stack_push(s->mimic_stack, expr);
- }
- expr_put(expr);
- }
+ clear_mimic_stack(reload_stack);
free_stack(reload_stack);
for (i = 0; i < bb->nr_successors; i++) {
diff --git a/lib/stack.c b/lib/stack.c
index ac0aec4..9b1e54f 100644
--- a/lib/stack.c
+++ b/lib/stack.c
@@ -26,6 +26,8 @@
#include "lib/stack.h"
+#include "vm/die.h"
+
#include <stdlib.h>
#include <string.h>
@@ -42,3 +44,18 @@ void free_stack(struct stack *stack)
free(stack->elements);
free(stack);
}
+
+void stack_copy(struct stack *src, struct stack *dst)
+{
+ void **new_elements;
+ unsigned long size;
+
+ size = src->nr_elements * sizeof(void*);
+ new_elements = realloc(dst->elements, size);
+ if (!new_elements)
+ error("out of memory");
+
+ dst->elements = new_elements;
+ dst->nr_elements = src->nr_elements;
+ memcpy(new_elements, src->elements, size);
+}
--
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
