Basic blocks can have now any number of successors. This is needed by BB ended with athrow, as well as BB ended with tableswitch/lookupswitch (not implemented yet).
Signed-off-by: Tomek Grabiec <[email protected]> --- include/jit/basic-block.h | 6 +-- jit/basic-block.c | 35 ++++++++++++------ jit/cfg-analyzer.c | 75 +++++++++++++++++++++++++++++++---------- test/jit/basic-block-assert.h | 12 ++++-- test/jit/basic-block-test.c | 10 ++---- test/jit/cfg-analyzer-test.c | 24 ++++++------ 6 files changed, 105 insertions(+), 57 deletions(-) diff --git a/include/jit/basic-block.h b/include/jit/basic-block.h index a358e79..0cb4784 100644 --- a/include/jit/basic-block.h +++ b/include/jit/basic-block.h @@ -8,8 +8,6 @@ struct compilation_unit; struct insn; struct statement; -#define MAX_BB_SUCCESSORS 2 - struct basic_block { struct compilation_unit *b_parent; unsigned long start; @@ -24,7 +22,7 @@ struct basic_block { bool has_branch; unsigned long br_target_off; /* Branch target offset in bytecode insns. */ unsigned long nr_successors; - struct basic_block *successors[MAX_BB_SUCCESSORS]; + struct basic_block **successors; /* The mimic stack is used to simulate JVM operand stack at compile-time. See Section 2.2 ("Lazy code selection") of the paper @@ -66,7 +64,7 @@ void free_basic_block(struct basic_block *); struct basic_block *bb_split(struct basic_block *, unsigned long); void bb_add_stmt(struct basic_block *, struct statement *); void bb_add_insn(struct basic_block *, struct insn *); -void bb_add_successor(struct basic_block *, struct basic_block *); +int bb_add_successor(struct basic_block *, struct basic_block *); #define for_each_basic_block(bb, bb_list) list_for_each_entry(bb, bb_list, bb_list_node) #define for_each_basic_block_reverse(bb, bb_list) list_for_each_entry_reverse(bb, bb_list, bb_list_node) diff --git a/jit/basic-block.c b/jit/basic-block.c index 4041cd1..08cd8ad 100644 --- a/jit/basic-block.c +++ b/jit/basic-block.c @@ -15,6 +15,7 @@ #include <stdlib.h> #include <string.h> +#include <errno.h> struct basic_block *alloc_basic_block(struct compilation_unit *b_parent, unsigned long start, unsigned long end) { @@ -92,24 +93,23 @@ void free_basic_block(struct basic_block *bb) struct basic_block *bb_split(struct basic_block *orig_bb, unsigned long offset) { struct basic_block *new_bb; - unsigned int i; if (offset < orig_bb->start || offset >= orig_bb->end) return NULL; new_bb = get_basic_block(orig_bb->b_parent, offset, orig_bb->end); - if (new_bb) - orig_bb->end = offset; + if (new_bb == NULL) + return NULL; - if (orig_bb->has_branch) { - for (i = 0; i < orig_bb->nr_successors; i++) { - new_bb->successors[i] = orig_bb->successors[i]; - orig_bb->successors[i] = NULL; - } + orig_bb->end = offset; - new_bb->nr_successors = orig_bb->nr_successors; - orig_bb->nr_successors = 0; + new_bb->successors = orig_bb->successors; + orig_bb->successors = NULL; + new_bb->nr_successors = orig_bb->nr_successors; + orig_bb->nr_successors = 0; + + if (orig_bb->has_branch) { orig_bb->has_branch = false; new_bb->has_branch = true; @@ -130,10 +130,21 @@ void bb_add_insn(struct basic_block *bb, struct insn *insn) list_add_tail(&insn->insn_list_node, &bb->insn_list); } -void bb_add_successor(struct basic_block *bb, struct basic_block *successor) +int bb_add_successor(struct basic_block *bb, struct basic_block *successor) { - assert(bb->nr_successors < MAX_BB_SUCCESSORS); + int new_size; + struct basic_block **new_successors; + + new_size = sizeof(struct basic_block *) * (bb->nr_successors + 1); + + new_successors = realloc(bb->successors, new_size); + if (new_successors == NULL) + return -ENOMEM; + + bb->successors = new_successors; bb->successors[bb->nr_successors] = successor; bb->nr_successors++; + + return 0; } diff --git a/jit/cfg-analyzer.c b/jit/cfg-analyzer.c index db77394..3230685 100644 --- a/jit/cfg-analyzer.c +++ b/jit/cfg-analyzer.c @@ -34,9 +34,10 @@ static void detect_exception_handlers(struct compilation_unit *cu) } } -static void update_branch_successors(struct compilation_unit *cu) +static int update_branch_successors(struct compilation_unit *cu) { struct basic_block *bb; + int err = 0; for_each_basic_block(bb, &cu->bb_list) { struct basic_block *target_bb; @@ -46,30 +47,42 @@ static void update_branch_successors(struct compilation_unit *cu) target_bb = find_bb(cu, bb->br_target_off); assert(target_bb != NULL); - bb_add_successor(bb, target_bb); + + err = bb_add_successor(bb, target_bb); + if (err) + break; } + + return err; } -static void split_at_branch_targets(struct compilation_unit *cu, +static int split_at_branch_targets(struct compilation_unit *cu, struct bitset *branch_targets) { unsigned long offset; + int err = 0; for (offset = 0; offset < cu->method->code_size; offset++) { struct basic_block *bb; if (!test_bit(branch_targets->bits, offset)) continue; - + bb = find_bb(cu, offset); if (bb->start != offset) { struct basic_block *new_bb; new_bb = bb_split(bb, offset); - bb_add_successor(bb, new_bb); + + err = bb_add_successor(bb, new_bb); + if (err) + break; + bb = new_bb; } } + + return err; } static inline bool bc_ends_basic_block(unsigned char code) @@ -77,11 +90,12 @@ static inline bool bc_ends_basic_block(unsigned char code) return bc_is_branch(code) || bc_is_athrow(code) || bc_is_return(code); } -static void split_after_branches(struct stream *stream, +static int split_after_branches(struct stream *stream, struct basic_block *entry_bb, struct bitset *branch_targets) { struct basic_block *bb; + int err = 0; bb = entry_bb; @@ -100,8 +114,11 @@ static void split_after_branches(struct stream *stream, next_insn_off = offset + bc_insn_size(code); new_bb = bb_split(bb, next_insn_off); - if (bc_is_branch(*code) && !bc_is_goto(*code)) - bb_add_successor(bb, new_bb); + if (bc_is_branch(*code) && !bc_is_goto(*code)) { + err = bb_add_successor(bb, new_bb); + if (err) + break; + } if (bc_is_branch(*code)) { br_target_off = bc_target_off(code) + offset; @@ -114,12 +131,15 @@ static void split_after_branches(struct stream *stream, bb = new_bb; } + + return err; } -static void update_athrow_successors(struct stream *stream, +static int update_athrow_successors(struct stream *stream, struct compilation_unit *cu) { struct methodblock *method; + int err = 0; method = cu->method; @@ -146,10 +166,15 @@ static void update_athrow_successors(struct stream *stream, eh_bb = find_bb(cu, eh->handler_pc); assert(eh_bb != NULL); - bb_add_successor(bb, eh_bb); + err = bb_add_successor(bb, eh_bb); + if (err) + goto out; } } } + + out: + return err; } static bool all_exception_handlers_have_bb(struct compilation_unit *cu) @@ -175,7 +200,7 @@ static bool all_exception_handlers_have_bb(struct compilation_unit *cu) 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; @@ -196,6 +221,7 @@ int analyze_control_flow(struct compilation_unit *cu) struct bitset *branch_targets; struct basic_block *entry_bb; struct stream stream; + int err = 0; branch_targets = alloc_bitset(cu->method->code_size); if (!branch_targets) @@ -204,15 +230,25 @@ int analyze_control_flow(struct compilation_unit *cu) bytecode_stream_init(&stream, cu->method); entry_bb = get_basic_block(cu, 0, cu->method->code_size); - split_after_branches(&stream, entry_bb, branch_targets); - split_at_branch_targets(cu, branch_targets); - update_branch_successors(cu); + + err = split_after_branches(&stream, entry_bb, branch_targets); + if (err) + goto out; + + err = split_at_branch_targets(cu, branch_targets); + if (err) + goto out; + + err = update_branch_successors(cu); + if (err) + goto out; + detect_exception_handlers(cu); bytecode_stream_init(&stream, cu->method); - update_athrow_successors(&stream, cu); - - free(branch_targets); + err = update_athrow_successors(&stream, cu); + if (err) + goto out; /* * This checks whether every exception handler has its own @@ -222,5 +258,8 @@ int analyze_control_flow(struct compilation_unit *cu) */ assert(all_exception_handlers_have_bb(cu)); - return 0; + out: + free(branch_targets); + + return err; } diff --git a/test/jit/basic-block-assert.h b/test/jit/basic-block-assert.h index b1c434d..8f00672 100644 --- a/test/jit/basic-block-assert.h +++ b/test/jit/basic-block-assert.h @@ -12,12 +12,16 @@ static void inline assert_basic_block(struct compilation_unit *parent, assert_int_equals(end, bb->end); } -static void inline assert_basic_block_successors(struct basic_block *succ0, - struct basic_block *succ1, +static void inline assert_basic_block_successors(struct basic_block **succ, + int nsucc, struct basic_block *bb) { - assert_ptr_equals(succ0, bb->successors[0]); - assert_ptr_equals(succ1, bb->successors[1]); + int i; + + assert_int_equals(bb->nr_successors, nsucc); + + for (i = 0; i < nsucc; i++) + assert_ptr_equals(succ[i], bb->successors[i]); } #endif diff --git a/test/jit/basic-block-test.c b/test/jit/basic-block-test.c index e036965..af7dee5 100644 --- a/test/jit/basic-block-test.c +++ b/test/jit/basic-block-test.c @@ -56,19 +56,15 @@ void test_split_basic_block_with_branch(void) target_bb = bb_split(bb, 3); bb->has_branch = true; - bb->nr_successors = 1; - bb->successors[0] = target_bb; + bb_add_successor(bb, target_bb); new_bb = bb_split(bb, 2); assert_true(new_bb->has_branch); assert_false(bb->has_branch); - assert_int_equals(bb->nr_successors, 0); - assert_int_equals(new_bb->nr_successors, 1); - - assert_basic_block_successors(NULL, NULL, bb); - assert_basic_block_successors(target_bb, NULL, new_bb); + assert_basic_block_successors((struct basic_block*[]){ }, 0, bb); + assert_basic_block_successors((struct basic_block*[]){target_bb}, 1, new_bb); free_compilation_unit(cu); } diff --git a/test/jit/cfg-analyzer-test.c b/test/jit/cfg-analyzer-test.c index aaea81f..a9aaec4 100644 --- a/test/jit/cfg-analyzer-test.c +++ b/test/jit/cfg-analyzer-test.c @@ -43,9 +43,9 @@ void test_branch_opcode_ends_basic_block(void) assert_basic_block(cu, 4, 7, bb2); assert_basic_block(cu, 7, 9, bb3); - assert_basic_block_successors(bb2, bb3, bb1); - assert_basic_block_successors(bb3, NULL, bb2); - assert_basic_block_successors(NULL, NULL, bb3); + assert_basic_block_successors((struct basic_block*[]){bb2, bb3}, 2, bb1); + assert_basic_block_successors((struct basic_block*[]){bb3 }, 1, bb2); + assert_basic_block_successors((struct basic_block*[]){ }, 0, bb3); free_compilation_unit(cu); } @@ -83,10 +83,10 @@ void test_multiple_branches(void) bb3 = bb_entry(bb2->bb_list_node.next); bb4 = bb_entry(bb3->bb_list_node.next); - assert_basic_block_successors(bb2, bb3, bb1); - assert_basic_block_successors(bb4, NULL, bb2); - assert_basic_block_successors(bb4, NULL, bb3); - assert_basic_block_successors(NULL, NULL, bb4); + assert_basic_block_successors((struct basic_block*[]){bb2, bb3}, 2, bb1); + assert_basic_block_successors((struct basic_block*[]){bb4 }, 1, bb2); + assert_basic_block_successors((struct basic_block*[]){bb4 }, 1, bb3); + assert_basic_block_successors((struct basic_block*[]){ }, 0, bb4); free_compilation_unit(cu); } @@ -152,11 +152,11 @@ void test_multiple_branch_with_target_instruction_splitting(void) assert_basic_block(cu, 12, 14, bb3); assert_basic_block(cu, 14, 15, bb5); - assert_basic_block_successors(bb2, bb4, bb1); - assert_basic_block_successors(bb4, NULL, bb2); - assert_basic_block_successors(bb3, bb5, bb4); - assert_basic_block_successors(bb5, NULL, bb3); - assert_basic_block_successors(NULL, NULL, bb5); + assert_basic_block_successors((struct basic_block*[]){bb2, bb4}, 2, bb1); + assert_basic_block_successors((struct basic_block*[]){bb4 }, 1, bb2); + assert_basic_block_successors((struct basic_block*[]){bb3, bb5}, 2, bb4); + assert_basic_block_successors((struct basic_block*[]){bb5 }, 1, bb3); + assert_basic_block_successors((struct basic_block*[]){ }, 0, bb5); free_compilation_unit(cu); } -- 1.6.0.6 ------------------------------------------------------------------------------ Register Now & Save for Velocity, the Web Performance & Operations Conference from O'Reilly Media. Velocity features a full day of expert-led, hands-on workshops and two days of sessions from industry leaders in dedicated Performance & Operations tracks. Use code vel09scf and Save an extra 15% before 5/3. http://p.sf.net/sfu/velocityconf _______________________________________________ Jatovm-devel mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/jatovm-devel
