During CFG construction basic blocks are split at tableswitch argets
but they are not connected to the basic block containing the
tableswitch bytecode. During conversion of tableswitch bytecode 2 new
basic blocks are created by splitting the current basic block at the
end. After that basic blocks are connected to appropriate
successors. The resulting basic blocks look like this:
// [temporary int 0x853d578 (low)] - index
// [bb 0x853ea50] - tableswitch default target
IF:
if_conditional:
BINOP:
vm_type: [int]
binary_operator: [lt]
binary_left: [temporary int 0x853d578 (low)]
binary_right: [value int 0x1]
if_true: [bb 0x853ea50]
[bb 0x853f400]:
IF:
if_conditional:
BINOP:
vm_type: [int]
binary_operator: [gt]
binary_left: [temporary int 0x853d578 (low)]
binary_right: [value int 0x2]
if_true: [bb 0x853ea50]
[bb 0x853fc80]:
TABLESWITCH:
index: [temporary int 0x853d578 (low)]
case 1: [bb 0x853e1d0]
case 2: [bb 0x853ea50]
[bb 0x853ea50]
...
During conversion struct tableswitch is created which contains
an array of basic block pointers for each case target. After
emission these targets are resolved to native pointers.
The tableswitch statement selects the following code:
// $0x853d940 - lookup table
// r0 - tableswitch index reg
// r7 - temporary reg
sub_imm_reg $0x1, r0
mov_imm_reg $0x853d940, r7
jmp_memindex (r7, r0, 2)
Signed-off-by: Tomek Grabiec <tgrab...@gmail.com>
---
Makefile | 1 +
arch/x86/insn-selector.brg | 33 ++++++++-
include/jit/compilation-unit.h | 1 +
include/jit/compiler.h | 2 +
include/jit/statement.h | 28 +++++++-
include/vm/bytecodes.h | 18 ++++-
jit/branch-bc.c | 31 ++++++---
jit/bytecode-to-ir.c | 5 +-
jit/cfg-analyzer.c | 97 ++++++++++++++------------
jit/compilation-unit.c | 13 ++++
jit/emit.c | 19 +++++
jit/expression.c | 4 +-
jit/statement.c | 40 +++++++++++
jit/subroutine.c | 29 +++++++-
jit/switch-bc.c | 149 ++++++++++++++++++++++++++++++++++++++++
jit/tree-printer.c | 25 +++++++
test/arch-x86/Makefile | 2 +
test/jit/Makefile | 1 +
test/vm/bytecodes-test.c | 4 +-
vm/bytecodes.c | 40 +++++++++--
20 files changed, 461 insertions(+), 81 deletions(-)
create mode 100644 jit/switch-bc.c
diff --git a/Makefile b/Makefile
index ceb6955..8345916 100644
--- a/Makefile
+++ b/Makefile
@@ -82,6 +82,7 @@ JIT_OBJS = \
jit/spill-reload.o \
jit/stack-slot.o \
jit/statement.o \
+ jit/switch-bc.o \
jit/text.o \
jit/trace-jit.o \
jit/trampoline.o \
diff --git a/arch/x86/insn-selector.brg b/arch/x86/insn-selector.brg
index 0ddb543..31f8602 100644
--- a/arch/x86/insn-selector.brg
+++ b/arch/x86/insn-selector.brg
@@ -53,10 +53,9 @@ static void select_insn(struct basic_block *bb, struct
tree_node *tree,
static void select_exception_test(struct basic_block *bb,
struct tree_node *tree);
-static unsigned char type_to_scale(enum vm_type vm_type)
+static unsigned char size_to_scale(int size)
{
- /* Currently we can store not less than machine word at once */
- switch (get_vmtype_size(vm_type)) {
+ switch (size) {
case 1:
return 0;
case 2:
@@ -66,10 +65,16 @@ static unsigned char type_to_scale(enum vm_type vm_type)
case 8:
return 3;
default:
- error("Invalid type size");
+ error("Invalid size");
}
}
+static unsigned char type_to_scale(enum vm_type vm_type)
+{
+ /* Currently we can store not less than machine word at once */
+ return size_to_scale(get_vmtype_size(vm_type));
+}
+
static void method_args_cleanup(struct basic_block *bb, struct tree_node *tree,
unsigned long args_count)
{
@@ -1819,6 +1824,26 @@ stmt: STMT_GOTO
select_insn(s, tree, branch_insn(INSN_JMP_BRANCH, stmt->goto_target));
}
+stmt: STMT_TABLESWITCH(reg)
+{
+ struct statement *stmt;
+ struct var_info *base;
+ int scale;
+
+ stmt = to_stmt(tree);
+
+ select_insn(s, tree, imm_reg_insn(INSN_SUB_IMM_REG,
+ (unsigned long) stmt->table->low, state->left->reg1));
+
+ base = get_var(s->b_parent, J_REFERENCE);
+ select_insn(s, tree, imm_reg_insn(INSN_MOV_IMM_REG,
+ (unsigned long) stmt->table->lookup_table, base));
+
+ scale = size_to_scale(sizeof(void *));
+ select_insn(s, tree, memindex_insn(INSN_JMP_MEMINDEX,
+ base, state->left->reg1, scale));
+}
+
stmt: STMT_MONITOR_ENTER(reg)
{
struct var_info *ref;
diff --git a/include/jit/compilation-unit.h b/include/jit/compilation-unit.h
index d3fff81..cd52a07 100644
--- a/include/jit/compilation-unit.h
+++ b/include/jit/compilation-unit.h
@@ -54,6 +54,7 @@ struct compilation_unit {
unsigned char *unwind_past_unlock_ptr;
struct list_head static_fixup_site_list;
+ struct list_head tableswitch_list;
/*
* This holds a pointer to the method's code. It's value is
diff --git a/include/jit/compiler.h b/include/jit/compiler.h
index 18e32a8..de91e81 100644
--- a/include/jit/compiler.h
+++ b/include/jit/compiler.h
@@ -47,6 +47,8 @@ struct parse_context {
void convert_expression(struct parse_context *ctx, struct expression *expr);
void convert_statement(struct parse_context *ctx, struct statement *stmt);
+void do_convert_statement(struct basic_block *bb, struct statement *stmt,
+ unsigned long bc_offset);
int compile(struct compilation_unit *);
int analyze_control_flow(struct compilation_unit *);
diff --git a/include/jit/statement.h b/include/jit/statement.h
index 9527378..ae4d1fb 100644
--- a/include/jit/statement.h
+++ b/include/jit/statement.h
@@ -6,6 +6,8 @@
#include <stddef.h>
#include "vm/vm.h"
+struct tableswitch_info;
+
enum statement_type {
STMT_STORE = OP_LAST,
STMT_IF,
@@ -19,9 +21,24 @@ enum statement_type {
STMT_MONITOR_EXIT,
STMT_CHECKCAST,
STMT_ARRAY_STORE_CHECK,
+ STMT_TABLESWITCH,
STMT_LAST, /* Not a real type. Keep this last. */
};
+struct tableswitch {
+ uint32_t low;
+ uint32_t high;
+
+ union {
+ struct basic_block **bb_lookup_table;
+
+ /* Contains native pointers after instruction selection. */
+ void **lookup_table;
+ };
+
+ struct list_head list_node;
+};
+
struct statement {
union {
struct tree_node node;
@@ -53,6 +70,11 @@ struct statement {
struct tree_node *store_check_src;
struct tree_node *store_check_array;
};
+ struct /* STMT_TABLESWITCH */ {
+ struct tree_node *index;
+ struct tableswitch *table;
+ };
+
/* STMT_EXPRESSION, STMT_ARRAY_CHECK */
struct tree_node *expression;
};
@@ -74,6 +96,10 @@ struct statement *alloc_statement(enum statement_type);
void free_statement(struct statement *);
int stmt_nr_kids(struct statement *);
+struct tableswitch *alloc_tableswitch(struct tableswitch_info *, struct
compilation_unit *, unsigned long);
+void free_tableswitch(struct tableswitch *);
+struct statement *if_stmt(struct basic_block *, enum vm_type, enum
binary_operator, struct expression *, struct expression *);
+
#define for_each_stmt(stmt, stmt_list) list_for_each_entry(stmt, stmt_list,
stmt_list_node)
-
+
#endif
diff --git a/include/vm/bytecodes.h b/include/vm/bytecodes.h
index e4c2482..26da079 100644
--- a/include/vm/bytecodes.h
+++ b/include/vm/bytecodes.h
@@ -1,9 +1,10 @@
#ifndef __JIT_BYTECODES_H
#define __JIT_BYTECODES_H
+#include <stdint.h>
#include <stdbool.h>
-unsigned long bc_insn_size(const unsigned char *);
+unsigned long bc_insn_size(const unsigned char *, unsigned long);
bool bc_is_branch(unsigned char);
bool bc_is_goto(unsigned char);
bool bc_is_wide(unsigned char);
@@ -25,7 +26,20 @@ static inline bool bc_branches_to_follower(unsigned char
code)
}
#define bytecode_for_each_insn(code, code_length, pc) \
- for (pc = 0; pc < (code_length); pc += bc_insn_size(&(code)[(pc)]))
+ for (pc = 0; pc < (code_length); pc += bc_insn_size(code, pc))
+
+struct tableswitch_info {
+ uint32_t low;
+ uint32_t high;
+ int32_t default_target;
+ const unsigned char *targets;
+
+ uint32_t count;
+ unsigned long insn_size;
+};
+
+void get_tableswitch_info(const unsigned char *code, unsigned long pc,
+ struct tableswitch_info *info);
static inline unsigned long bytecode_insn_count(const unsigned char *code,
unsigned long code_length)
diff --git a/jit/branch-bc.c b/jit/branch-bc.c
index b60ed30..f6ec96b 100644
--- a/jit/branch-bc.c
+++ b/jit/branch-bc.c
@@ -19,20 +19,14 @@
#include <errno.h>
-static struct statement *__convert_if(struct parse_context *ctx,
- enum vm_type vm_type,
- enum binary_operator binop,
- struct expression *binary_left,
- struct expression *binary_right)
+struct statement *if_stmt(struct basic_block *true_bb,
+ enum vm_type vm_type,
+ enum binary_operator binop,
+ struct expression *binary_left,
+ struct expression *binary_right)
{
- struct basic_block *true_bb;
struct expression *if_conditional;
struct statement *if_stmt;
- int32_t if_target;
-
- if_target = bytecode_read_branch_target(ctx->opc, ctx->buffer);
-
- true_bb = find_bb(ctx->cu, ctx->offset + if_target);
if_conditional = binop_expr(vm_type, binop, binary_left, binary_right);
if (!if_conditional)
@@ -52,6 +46,21 @@ static struct statement *__convert_if(struct parse_context
*ctx,
return NULL;
}
+static struct statement *__convert_if(struct parse_context *ctx,
+ enum vm_type vm_type,
+ enum binary_operator binop,
+ struct expression *binary_left,
+ struct expression *binary_right)
+{
+ struct basic_block *true_bb;
+ int32_t if_target;
+
+ if_target = bytecode_read_branch_target(ctx->opc, ctx->buffer);
+ true_bb = find_bb(ctx->cu, ctx->offset + if_target);
+
+ return if_stmt(true_bb, vm_type, binop, binary_left, binary_right);
+}
+
static int convert_if(struct parse_context *ctx, enum binary_operator binop)
{
struct statement *stmt;
diff --git a/jit/bytecode-to-ir.c b/jit/bytecode-to-ir.c
index 658344a..69107e5 100644
--- a/jit/bytecode-to-ir.c
+++ b/jit/bytecode-to-ir.c
@@ -53,7 +53,6 @@ static int convert_not_implemented(struct parse_context *ctx)
return warn("bytecode %d is not supported", ctx->opc), -EINVAL;
}
-#define convert_tableswitch convert_not_implemented
#define convert_lookupswitch convert_not_implemented
#define convert_goto_w convert_goto
@@ -74,8 +73,8 @@ void convert_expression(struct parse_context *ctx, struct
expression *expr)
stack_push(ctx->bb->mimic_stack, expr);
}
-static void
-do_convert_statement(struct basic_block *bb, struct statement *stmt, unsigned
long bc_offset)
+void do_convert_statement(struct basic_block *bb, struct statement *stmt,
+ unsigned long bc_offset)
{
tree_patch_bc_offset(&stmt->node, bc_offset);
bb_add_stmt(bb, stmt);
diff --git a/jit/cfg-analyzer.c b/jit/cfg-analyzer.c
index fcb15a5..fe753ed 100644
--- a/jit/cfg-analyzer.c
+++ b/jit/cfg-analyzer.c
@@ -10,6 +10,7 @@
#include "jit/compiler.h"
#include "lib/bitset.h"
+#include "vm/bytecode.h"
#include "vm/bytecodes.h"
#include "vm/method.h"
#include "vm/stream.h"
@@ -92,38 +93,62 @@ static inline bool bc_ends_basic_block(unsigned char code)
return bc_is_branch(code) || bc_is_athrow(code) || bc_is_return(code);
}
-static int split_after_branches(struct stream *stream,
- struct basic_block *entry_bb,
- struct bitset *branch_targets)
+static int split_after_branches(const unsigned char *code,
+ unsigned long code_length,
+ struct basic_block *entry_bb,
+ struct bitset *branch_targets)
{
struct basic_block *bb;
int err = 0;
bb = entry_bb;
- for (; stream_has_more(stream); stream_advance(stream)) {
- unsigned long offset, next_insn_off;
+ unsigned long offset;
+ bytecode_for_each_insn(code, code_length, offset) {
+ unsigned long next_insn_off;
long br_target_off;
struct basic_block *new_bb;
- unsigned char *code;
+ unsigned char opcode;
- code = stream->current;
+ opcode = code[offset];
- if (!bc_ends_basic_block(*code))
+ if (!bc_ends_basic_block(opcode))
continue;
- offset = stream_offset(stream);
- next_insn_off = offset + bc_insn_size(code);
+ next_insn_off = offset + bc_insn_size(code, offset);
- new_bb = bb_split(bb, next_insn_off);
- if (bc_is_branch(*code) && !bc_is_goto(*code)) {
- err = bb_add_successor(bb, new_bb);
- if (err)
- break;
+ if (next_insn_off != bb->end) {
+ new_bb = bb_split(bb, next_insn_off);
+
+ if (bc_is_branch(opcode) && !bc_is_goto(opcode)) {
+ err = bb_add_successor(bb, new_bb);
+ if (err)
+ break;
+ }
}
- if (bc_is_branch(*code)) {
- br_target_off = bc_target_off(code) + offset;
+ if (opcode == OPC_TABLESWITCH) {
+ struct tableswitch_info info;
+
+ get_tableswitch_info(code, offset, &info);
+
+ /*
+ * We mark tableswitch targets to be split but
+ * we do not connect them to this basic block
+ * because it will be later split in
+ * convert_tableswitch().
+ */
+ set_bit(branch_targets->bits,
+ offset + info.default_target);
+
+ for (unsigned int i = 0; i < info.count; i++) {
+ int32_t target;
+
+ target = read_s32(info.targets + i * 4);
+ set_bit(branch_targets->bits, offset + target);
+ }
+ } else if (bc_is_branch(opcode)) {
+ br_target_off = bc_target_off(&code[offset]) + offset;
bb->br_target_off = br_target_off;
bb->has_branch = true;
@@ -157,42 +182,24 @@ static bool all_exception_handlers_have_bb(struct
compilation_unit *cu)
return true;
}
-static unsigned char *bytecode_next_insn(struct stream *stream)
-{
- unsigned long opc_size;
-
- opc_size = bc_insn_size(stream->current);
- assert(opc_size != 0);
- return stream->current + opc_size;
-}
-
-static struct stream_operations bytecode_stream_ops = {
- .new_position = bytecode_next_insn,
-};
-
-static void bytecode_stream_init(struct stream *stream, struct vm_method
*method)
-{
- stream_init(stream,
- method->code_attribute.code,
- method->code_attribute.code_length,
- &bytecode_stream_ops);
-}
-
int analyze_control_flow(struct compilation_unit *cu)
{
struct bitset *branch_targets;
- struct stream stream;
+ const unsigned char *code;
+ int code_length;
int err = 0;
- branch_targets = alloc_bitset(cu->method->code_attribute.code_length);
+ code = cu->method->code_attribute.code;
+ code_length = cu->method->code_attribute.code_length;
+
+ branch_targets = alloc_bitset(code_length);
if (!branch_targets)
return warn("out of memory"), -ENOMEM;
- bytecode_stream_init(&stream, cu->method);
+ cu->entry_bb = get_basic_block(cu, 0, code_length);
- cu->entry_bb = get_basic_block(cu, 0,
cu->method->code_attribute.code_length);
-
- err = split_after_branches(&stream, cu->entry_bb, branch_targets);
+ err = split_after_branches(code, code_length, cu->entry_bb,
+ branch_targets);
if (err)
goto out;
@@ -206,8 +213,6 @@ int analyze_control_flow(struct compilation_unit *cu)
detect_exception_handlers(cu);
- bytecode_stream_init(&stream, cu->method);
-
/*
* This checks whether every exception handler has its own
* basic block which starts at handler_pc. There always should
diff --git a/jit/compilation-unit.c b/jit/compilation-unit.c
index d67e216..fe5ae50 100644
--- a/jit/compilation-unit.c
+++ b/jit/compilation-unit.c
@@ -29,6 +29,7 @@
#include "jit/basic-block.h"
#include "jit/compilation-unit.h"
#include "jit/stack-slot.h"
+#include "jit/statement.h"
#include "jit/vars.h"
#include "lib/buffer.h"
#include "vm/method.h"
@@ -70,6 +71,7 @@ struct compilation_unit *compilation_unit_alloc(struct
vm_method *method)
goto out_of_memory;
INIT_LIST_HEAD(&cu->static_fixup_site_list);
+ INIT_LIST_HEAD(&cu->tableswitch_list);
}
return cu;
@@ -95,6 +97,16 @@ static void free_var_infos(struct var_info *var_infos)
}
}
+static void free_tableswitch_list(struct compilation_unit *cu)
+{
+ struct tableswitch *this, *next;
+
+ list_for_each_entry_safe(this, next, &cu->tableswitch_list, list_node) {
+ list_del(&this->list_node);
+ free_tableswitch(this);
+ }
+}
+
void free_compilation_unit(struct compilation_unit *cu)
{
struct basic_block *bb, *tmp_bb;
@@ -108,6 +120,7 @@ void free_compilation_unit(struct compilation_unit *cu)
free_buffer(cu->objcode);
free_var_infos(cu->var_infos);
free_stack_frame(cu->stack_frame);
+ free_tableswitch_list(cu);
free(cu);
}
diff --git a/jit/emit.c b/jit/emit.c
index 24f2d94..1a537a9 100644
--- a/jit/emit.c
+++ b/jit/emit.c
@@ -18,6 +18,7 @@
#include "jit/basic-block.h"
#include "jit/emit-code.h"
#include "jit/compiler.h"
+#include "jit/statement.h"
#include "jit/text.h"
#include "arch/instruction.h"
@@ -54,6 +55,22 @@ static void backpatch_branches(struct buffer *buf,
}
}
+static void backpatch_tableswitch_targets(struct compilation_unit *cu)
+{
+ struct tableswitch *this;
+
+ list_for_each_entry(this, &cu->tableswitch_list, list_node)
+ {
+ int count;
+
+ count = this->high - this->low + 1;
+
+ for (int i = 0; i < count; i++)
+ this->lookup_table[i] =
+ bb_native_ptr(this->bb_lookup_table[i]);
+ }
+}
+
void emit_body(struct basic_block *bb, struct buffer *buf)
{
struct insn *insn;
@@ -104,6 +121,8 @@ int emit_machine_code(struct compilation_unit *cu)
for_each_basic_block(bb, &cu->bb_list)
emit_body(bb, cu->objcode);
+ backpatch_tableswitch_targets(cu);
+
emit_body(cu->exit_bb, cu->objcode);
if (method_is_synchronized(cu->method))
emit_monitorexit(cu);
diff --git a/jit/expression.c b/jit/expression.c
index dde3c72..6863f2c 100644
--- a/jit/expression.c
+++ b/jit/expression.c
@@ -183,9 +183,11 @@ struct expression *expr_get(struct expression *expr)
return expr;
}
-
+extern void print_trace(void);
void expr_put(struct expression *expr)
{
+ if (!(expr->refcount > 0))
+ print_trace();
assert(expr->refcount > 0);
expr->refcount--;
diff --git a/jit/statement.c b/jit/statement.c
index f108eab..7547b5f 100644
--- a/jit/statement.c
+++ b/jit/statement.c
@@ -5,6 +5,8 @@
* LICENSE for details.
*/
+#include "vm/bytecode.h"
+#include "vm/bytecodes.h"
#include "vm/vm.h"
#include <assert.h>
#include "jit/expression.h"
@@ -28,6 +30,7 @@ int stmt_nr_kids(struct statement *stmt)
case STMT_MONITOR_ENTER:
case STMT_MONITOR_EXIT:
case STMT_CHECKCAST:
+ case STMT_TABLESWITCH:
return 1;
case STMT_GOTO:
case STMT_VOID_RETURN:
@@ -63,3 +66,40 @@ void free_statement(struct statement *stmt)
free(stmt);
}
+
+struct tableswitch *alloc_tableswitch(struct tableswitch_info *info,
+ struct compilation_unit *cu,
+ unsigned long offset)
+{
+ struct tableswitch *table;
+
+ table = malloc(sizeof(*table));
+ if (!table)
+ return NULL;
+
+ table->low = info->low;
+ table->high = info->high;
+
+ table->bb_lookup_table = malloc(sizeof(void *) * info->count);
+ if (!table->bb_lookup_table) {
+ free(table);
+ return NULL;
+ }
+
+ for (unsigned int i = 0; i < info->count; i++) {
+ int32_t target;
+
+ target = read_s32(info->targets + i * 4);
+ table->bb_lookup_table[i] = find_bb(cu, offset + target);
+ }
+
+ list_add(&table->list_node, &cu->tableswitch_list);
+
+ return table;
+}
+
+void free_tableswitch(struct tableswitch *table)
+{
+ free(table->lookup_table);
+ free(table);
+}
diff --git a/jit/subroutine.c b/jit/subroutine.c
index 9492a53..ad6f931 100644
--- a/jit/subroutine.c
+++ b/jit/subroutine.c
@@ -37,6 +37,7 @@
#include "jit/exception.h"
#include "vm/method.h"
+#include "vm/bytecode.h"
#include "vm/bytecodes.h"
#include "vm/stream.h"
#include "vm/stdlib.h"
@@ -98,7 +99,7 @@ static unsigned long next_pc(const unsigned char *code,
unsigned long current)
{
unsigned long opc_size;
- opc_size = bc_insn_size(&code[current]);
+ opc_size = bc_insn_size(code, current);
assert(opc_size != 0);
return current + opc_size;
@@ -289,7 +290,7 @@ static int subroutine_add_call_site(struct subroutine *sub,
sub->call_sites = new_tab;
sub->call_sites[sub->nr_call_sites++] = call_site;
- sub->call_sites_total_size += bc_insn_size(&code[call_site]);
+ sub->call_sites_total_size += bc_insn_size(code, call_site);
return 0;
}
@@ -354,7 +355,27 @@ static int do_subroutine_scan(struct
subroutine_scan_context *ctx,
continue;
}
- if (c[pc] == OPC_TABLESWITCH || c[pc] == OPC_LOOKUPSWITCH)
+ if (c[pc] == OPC_TABLESWITCH) {
+ struct tableswitch_info info;
+
+ get_tableswitch_info(c, pc, &info);
+ err = do_subroutine_scan(ctx, pc + info.default_target);
+ if (err)
+ return err;
+
+ for (unsigned int i = 0; i < info.count; i++) {
+ int32_t target;
+
+ target = read_s32(info.targets + i * 4);
+ err = do_subroutine_scan(ctx, pc + target);
+ if (err)
+ return err;
+ }
+
+ break;
+ }
+
+ if (c[pc] == OPC_LOOKUPSWITCH)
error("not implemented");
if (bc_is_jsr(c[pc])) {
@@ -443,7 +464,7 @@ static int subroutine_scan(struct inlining_context *ctx,
struct subroutine *sub)
return warn("subroutine end not found"), -EINVAL;
out:
- sub->epilog_size = bc_insn_size(&ctx->code.code[sub->end_pc]);
+ sub->epilog_size = bc_insn_size(ctx->code.code, sub->end_pc);
return 0;
}
diff --git a/jit/switch-bc.c b/jit/switch-bc.c
new file mode 100644
index 0000000..a2a9b84
--- /dev/null
+++ b/jit/switch-bc.c
@@ -0,0 +1,149 @@
+/*
+ * Copyright (c) 2009 Tomasz Grabiec
+ *
+ * This file is released under the GPL version 2 with the following
+ * clarification and special exception:
+ *
+ * Linking this library statically or dynamically with other modules is
+ * making a combined work based on this library. Thus, the terms and
+ * conditions of the GNU General Public License cover the whole
+ * combination.
+ *
+ * As a special exception, the copyright holders of this library give you
+ * permission to link this library with independent modules to produce an
+ * executable, regardless of the license terms of these independent
+ * modules, and to copy and distribute the resulting executable under terms
+ * of your choice, provided that you also meet, for each linked independent
+ * module, the terms and conditions of the license of that module. An
+ * independent module is a module which is not derived from or based on
+ * this library. If you modify this library, you may extend this exception
+ * to your version of the library, but you are not obligated to do so. If
+ * you do not wish to do so, delete this exception statement from your
+ * version.
+ *
+ * Please refer to the file LICENSE for details.
+ */
+
+#include <errno.h>
+
+#include "jit/bytecode-to-ir.h"
+#include "jit/compiler.h"
+#include "jit/compilation-unit.h"
+#include "jit/basic-block.h"
+#include "jit/statement.h"
+
+#include "vm/bytecode.h"
+#include "vm/bytecodes.h"
+#include "vm/stack.h"
+#include "vm/die.h"
+
+static struct statement *branch_if_lesser_stmt(struct basic_block *target,
+ struct expression *left,
+ int32_t right)
+{
+ struct expression *right_expr;
+
+ right_expr = value_expr(J_INT, right);
+ if (!right_expr)
+ return NULL;
+
+ return if_stmt(target, J_INT, OP_LT, left, right_expr);
+}
+
+static struct statement *branch_if_greater_stmt(struct basic_block *target,
+ struct expression *left,
+ int32_t right)
+{
+ struct expression *right_expr;
+
+ right_expr = value_expr(J_INT, right);
+ if (!right_expr)
+ return NULL;
+
+ return if_stmt(target, J_INT, OP_GT, left, right_expr);
+}
+
+int convert_tableswitch(struct parse_context *ctx)
+{
+ struct tableswitch_info info;
+ struct tableswitch *table;
+ struct basic_block *master_bb;
+ struct basic_block *default_bb;
+ struct basic_block *b1;
+ struct basic_block *b2;
+
+ get_tableswitch_info(ctx->code, ctx->offset, &info);
+ ctx->buffer->pos += info.insn_size;
+
+ table = alloc_tableswitch(&info, ctx->cu, ctx->offset);
+ if (!table)
+ return -ENOMEM;
+
+ default_bb = find_bb(ctx->cu, ctx->offset + info.default_target);
+ if (!default_bb)
+ goto fail_default_bb;
+
+ master_bb = ctx->bb;
+
+ b1 = bb_split(master_bb, ctx->offset);
+ b2 = bb_split(b1, ctx->offset);
+
+ b1->is_converted = true;
+ b2->is_converted = true;
+
+ assert(b1 && b2);
+
+ bb_add_successor(master_bb, default_bb );
+ bb_add_successor(master_bb, b1);
+
+ bb_add_successor(b1, default_bb );
+ bb_add_successor(b1, b2);
+
+ for (unsigned int i = 0; i < info.count; i++) {
+ struct basic_block *target_bb;
+ int32_t target;
+
+ target = read_s32(info.targets + i * 4);
+ target_bb = find_bb(ctx->cu, ctx->offset + target);
+
+ bb_add_successor(b2, target_bb);
+ }
+
+ struct statement *if_lesser_stmt;
+ struct statement *if_greater_stmt;
+ struct statement *stmt;
+ struct expression *pure_index;
+
+ pure_index = get_pure_expr(ctx, stack_pop(ctx->bb->mimic_stack));
+
+ if_lesser_stmt =
+ branch_if_lesser_stmt(default_bb, pure_index, info.low);
+ if (!if_lesser_stmt)
+ goto fail_lesser_stmt;
+
+ if_greater_stmt =
+ branch_if_greater_stmt(default_bb, pure_index, info.high);
+ if (!if_greater_stmt)
+ goto fail_greater_stmt;
+
+ stmt = alloc_statement(STMT_TABLESWITCH);
+ if (!stmt)
+ goto fail_stmt;
+
+ stmt->index = &pure_index->node;
+ stmt->table = table;
+
+ do_convert_statement(master_bb, if_lesser_stmt, ctx->offset);
+ do_convert_statement(b1, if_greater_stmt, ctx->offset);
+ do_convert_statement(b2, stmt, ctx->offset);
+ return 0;
+
+ fail_stmt:
+ free_statement(if_greater_stmt);
+ fail_greater_stmt:
+ free_statement(if_lesser_stmt);
+ fail_lesser_stmt:
+ fail_default_bb:
+ free_tableswitch(table);
+ return -1;
+}
diff --git a/jit/tree-printer.c b/jit/tree-printer.c
index 1afe60c..2473470 100644
--- a/jit/tree-printer.c
+++ b/jit/tree-printer.c
@@ -296,6 +296,30 @@ out:
return err;
}
+static int print_tableswitch_stmt(int lvl, struct string *str,
+ struct statement *stmt)
+{
+ int err;
+
+ err = append_formatted(lvl, str, "TABLESWITCH:\n");
+ if (err)
+ goto out;
+
+ err = append_tree_attr(lvl + 1, str, "index", stmt->expression);
+
+ unsigned int count = stmt->table->high - stmt->table->low + 1;
+ for (unsigned int i = 0; i < count; i++) {
+ char case_name[16];
+
+ sprintf(case_name, "case %d", stmt->table->low + i);
+ err = append_simple_attr(lvl + 1, str, case_name, "bb %p",
+ stmt->table->bb_lookup_table[i]);
+ }
+
+out:
+ return err;
+}
+
typedef int (*print_stmt_fn) (int, struct string * str, struct statement *);
static print_stmt_fn stmt_printers[] = {
@@ -311,6 +335,7 @@ static print_stmt_fn stmt_printers[] = {
[STMT_CHECKCAST] = print_checkcast_stmt,
[STMT_ATHROW] = print_athrow_stmt,
[STMT_ARRAY_STORE_CHECK] = print_array_store_check_stmt,
+ [STMT_TABLESWITCH] = print_tableswitch_stmt,
};
static int print_stmt(int lvl, struct tree_node *root, struct string *str)
diff --git a/test/arch-x86/Makefile b/test/arch-x86/Makefile
index de408a5..7b0d8ed 100644
--- a/test/arch-x86/Makefile
+++ b/test/arch-x86/Makefile
@@ -54,6 +54,8 @@ TOPLEVEL_OBJS := \
lib/list.o \
lib/radix-tree.o \
lib/string.o \
+ vm/bytecode.o \
+ vm/bytecodes.o \
vm/call.o \
vm/class.o \
vm/die.o \
diff --git a/test/jit/Makefile b/test/jit/Makefile
index dcf8e20..5c26268 100644
--- a/test/jit/Makefile
+++ b/test/jit/Makefile
@@ -36,6 +36,7 @@ TOPLEVEL_OBJS := \
jit/spill-reload.o \
jit/stack-slot.o \
jit/statement.o \
+ jit/switch-bc.o \
jit/text.o \
jit/tree-node.o \
jit/tree-printer.o \
diff --git a/test/vm/bytecodes-test.c b/test/vm/bytecodes-test.c
index 24fc579..06cd321 100644
--- a/test/vm/bytecodes-test.c
+++ b/test/vm/bytecodes-test.c
@@ -13,7 +13,7 @@
static void assert_bc_insn_size(unsigned long expected_len, unsigned char opc)
{
unsigned char code[] = { opc, 0x00, 0x00 };
- assert_int_equals(expected_len, bc_insn_size(code));
+ assert_int_equals(expected_len, bc_insn_size(code, 0));
}
void test_size_of_bytecode(void)
@@ -25,7 +25,7 @@ void test_size_of_bytecode(void)
static void assert_wide_bc_insn_size(unsigned long expected_len, unsigned char
opc)
{
unsigned char code[] = { OPC_WIDE, opc, 0x00, 0x00, 0x00, 0x00 };
- assert_int_equals(expected_len, bc_insn_size(code));
+ assert_int_equals(expected_len, bc_insn_size(code, 0));
}
void test_size_of_wide_bytecode(void)
diff --git a/vm/bytecodes.c b/vm/bytecodes.c
index 163a423..c374e82 100644
--- a/vm/bytecodes.c
+++ b/vm/bytecodes.c
@@ -46,21 +46,47 @@ static struct bytecode_info bytecode_infos[] = {
#undef BYTECODE
-unsigned long bc_insn_size(const unsigned char *bc_start)
+void get_tableswitch_info(const unsigned char *code, unsigned long pc,
+ struct tableswitch_info *info)
+{
+ unsigned long pad;
+
+ assert(code[pc] == OPC_TABLESWITCH);
+
+ pad = 3 - (pc % 4);
+ pc += pad + 1;
+
+ info->default_target = read_u32(&code[pc]);
+ info->low = read_u32(&code[pc + 4]);
+ info->high = read_u32(&code[pc + 8]);
+ info->targets = &code[pc + 12];
+
+ info->count = info->high - info->low + 1;
+ info->insn_size = 1 + pad + (3 + info->count) * 4;
+}
+
+unsigned long bc_insn_size(const unsigned char *code, unsigned long pc)
{
unsigned long size;
- if (*bc_start == OPC_WIDE) {
- if (*(bc_start + 1) == OPC_IINC)
+ if (code[pc] == OPC_WIDE) {
+ if (code[pc + 1] == OPC_IINC)
return 6;
return 4;
}
- size = bytecode_infos[*bc_start].size;
+ if (code[pc] == OPC_TABLESWITCH) {
+ struct tableswitch_info info;
+
+ get_tableswitch_info(code, pc, &info);
+ return info.insn_size;
+ }
+
+ size = bytecode_infos[code[pc]].size;
if (size == 0)
- error("unknown bytecode opcode: 0x%x\n", *bc_start);
+ error("unknown bytecode opcode: 0x%x\n", code[pc]);
return size;
}
@@ -212,7 +238,7 @@ void bytecode_disassemble(const unsigned char *code,
unsigned long size)
int size;
int _pc;
- size = bc_insn_size(&code[pc]);
+ size = bc_insn_size(code, pc);
trace_printf(" [ %-3ld ] 0x%02x ", pc, code[pc]);
@@ -236,7 +262,7 @@ void bytecode_disassemble(const unsigned char *code,
unsigned long size)
free(opc_name);
- if (bc_is_branch(code[_pc])) {
+ if (bc_is_branch(code[_pc]) && code[_pc] != OPC_TABLESWITCH) {
trace_printf(" %ld\n", bc_target_off(&code[_pc]) + _pc);
continue;
}
--
1.6.0.6
------------------------------------------------------------------------------
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
