[PATCH 4/4] jit: fix mimic stack content propagation
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;
+}
+
[PATCH 4/4] jit: fix mimic stack content propagation
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. The successor's stack was then
also propagated, along with extra elements. This leads to geneartion
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 |3 ++
include/lib/stack.h | 24 +-
jit/bytecode-to-ir.c | 49
3 files changed, 61 insertions(+), 15 deletions(-)
diff --git a/include/jit/basic-block.h b/include/jit/basic-block.h
index b3e3cc1..c4b74ec 100644
--- a/include/jit/basic-block.h
+++ b/include/jit/basic-block.h
@@ -46,6 +46,9 @@ struct basic_block {
Adl-Tabatabai et al (1998) for more in-depth explanation. */
struct stack *mimic_stack;
+ unsigned long entry_mimic_stack_size;
+ bool entry_mimic_stack_set;
+
/* Is this basic block an exception handler? */
bool is_eh;
diff --git a/include/lib/stack.h b/include/lib/stack.h
index e4e79d9..7ec599d 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,24 @@ 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;
+}
+
+static inline 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);
+}
+
#endif
diff --git a/jit/bytecode-to-ir.c b/jit/bytecode-to-ir.c
index 2923890..4c059e0 100644
--- a/jit/bytecode-to-ir.c
+++ b/jit/bytecode-to-ir.c
@@ -181,8 +181,17 @@ 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);
stack_push(bb-mimic_stack, exception_ref_expr());
+ bb-entry_mimic_stack_size = 1;
+ bb-entry_mimic_stack_set = true;
+ }
+
+ if (!bb-entry_mimic_stack_set) {
+ bb-entry_mimic_stack_size = 0;
+ bb-entry_mimic_stack_set = true;
+ }
while (buffer.pos bb-end) {
ctx.offset = ctx.buffer-pos; /* this is fragile */
@@ -194,6 +203,28 @@ 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)
+{
+ for (unsigned int i = 0; i reload-nr_elements; i++)
+ bb_add_mimic_stack_expr(bb, reload-elements[i]);
+
+ if (!bb-entry_mimic_stack_set) {
+ for (unsigned int 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);
+ bb-entry_mimic_stack_set = true;
+ } else if (stack_size(reload) != bb-entry_mimic_stack_size)
+ return error(stack size differs on different paths), -EINVAL;
+
+ return 0;
+}
+
static int convert_bb_to_ir(struct basic_block *bb)
{
struct stack *reload_stack;
@@ -227,20 +258,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++) {
- struct basic_block *s = bb-successors[i];
+ for (i = 0; i bb-nr_successors; i++)
+ reload_mimic_stack(bb-successors[i], reload_stack);
- expr_get(expr);
-
- bb_add_mimic_stack_expr(s, expr);
-
-
