From ea505ea6095459d2e128857ed9ef836815c2a99c Mon Sep 17 00:00:00 2001 From: Aleksey Demakov Date: Fri, 8 May 2009 23:33:41 +0000 Subject: [PATCH] basic block changes --- ChangeLog | 16 ++++ jit/jit-block.c | 163 +++++++++++++++++++++++------------------ jit/jit-function.c | 3 - jit/jit-insn.c | 36 +++++---- jit/jit-internal.h | 22 +++--- jit/jit-rules-alpha.c | 10 +-- jit/jit-rules-arm.c | 9 +-- jit/jit-rules-x86-64.c | 7 +- jit/jit-rules-x86.c | 15 ++-- 9 files changed, 152 insertions(+), 129 deletions(-) diff --git a/ChangeLog b/ChangeLog index 4002537..ceaad70 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,19 @@ +2009-05-09 Aleksey Demakov + + * jit/jit-internal.h, jit/jit-block.c, jit/jit-insn.c, + * jit/jit-function.c: allocate insns as individual array for each + basic block instead of using common per-function pool. + + * jit/jit-internal.h, jit/jit-block.c: keep useless basic blocks + in the deleted_blocks list instead of freeing them immediately as + these blocks still may be referenced from elsewhere, for instance, + from jit_value_t structs. + + * jit/jit-internal.h, jit/jit-block.c (_jit_block_is_final): add + function to check if the given block is the last one. + * jit/jit-rules-alpha.c, jit/jit-rules-arm.c, jit/jit-rules-x86.c, + * jit/jit-rules-x86-64.c (jump_to_epilog): use _jit_block_is_final. + 2009-04-29 Aleksey Demakov * jit/jit-block.c (_jit_block_build_cfg, _jit_block_clean_cfg): add diff --git a/jit/jit-block.c b/jit/jit-block.c index 7499f0a..0f35f56 100644 --- a/jit/jit-block.c +++ b/jit/jit-block.c @@ -51,8 +51,6 @@ create_block(jit_function_t func) /* Initialize the block */ block->func = func; block->label = jit_label_undefined; - block->first_insn = func->builder->num_insns; - block->last_insn = block->first_insn - 1; return block; } @@ -63,9 +61,27 @@ free_block(jit_block_t block) jit_meta_destroy(&block->meta); jit_free(block->succs); jit_free(block->preds); + jit_free(block->insns); jit_free(block); } +/* Block may not be deleted right when it was found useless from + the control flow perspective as it might be referenced from + elsewhere, for instance, from some jit_value_t */ +static void +delete_block(jit_block_t block) +{ + jit_free(block->succs); + block->succs = 0; + jit_free(block->preds); + block->preds = 0; + jit_free(block->insns); + block->insns = 0; + + block->next = block->func->builder->deleted_blocks; + block->func->builder->deleted_blocks = block->next; +} + static int create_edge(jit_function_t func, jit_block_t src, jit_block_t dst, int flags, int create) { @@ -320,13 +336,11 @@ attach_edge_dst(_jit_edge_t edge, jit_block_t block) static int is_empty_block(jit_block_t block) { - jit_insn_t *insns; int index, opcode; - insns = block->func->builder->insns; - for(index = block->first_insn; index <= block->last_insn; index++) + for(index = 0; index < block->num_insns; index++) { - opcode = insns[index]->opcode; + opcode = block->insns[index].opcode; if(opcode != JIT_OP_NOP && opcode != JIT_OP_MARK_OFFSET && opcode != JIT_OP_BR) @@ -415,7 +429,7 @@ merge_empty(jit_function_t func, jit_block_t block, int *changed) detach_edge_dst(succ_edge); jit_memory_pool_dealloc(&func->builder->edge_pool, succ_edge); _jit_block_detach(block, block); - free_block(block); + delete_block(block); } return 1; @@ -432,7 +446,7 @@ delete_edge(jit_function_t func, _jit_edge_t edge) /* Delete block along with references to it */ static void -delete_block(jit_block_t block) +eliminate_block(jit_block_t block) { _jit_edge_t edge; int index; @@ -454,8 +468,8 @@ delete_block(jit_block_t block) jit_memory_pool_dealloc(&block->func->builder->edge_pool, edge); } - /* Free memory */ - free_block(block); + /* Finally delete the block */ + delete_block(block); } #if 0 @@ -494,7 +508,7 @@ eliminate_unreachable(jit_function_t func) } else { - delete_block(block); + eliminate_block(block); } block = next_block; } @@ -571,6 +585,14 @@ _jit_block_free(jit_function_t func) block = next; } + block = func->builder->deleted_blocks; + while(block) + { + next = block->next; + free_block(block); + block = next; + } + func->builder->entry_block = 0; func->builder->exit_block = 0; } @@ -712,13 +734,13 @@ _jit_block_compute_postorder(jit_function_t func) num_blocks = count_blocks(func); - blocks = jit_malloc(num_blocks * sizeof(jit_block_t)); + blocks = (jit_block_t *) jit_malloc(num_blocks * sizeof(jit_block_t)); if(!blocks) { return 0; } - stack = jit_malloc(num_blocks * sizeof(_jit_block_stack_entry_t)); + stack = (_jit_block_stack_entry_t *) jit_malloc(num_blocks * sizeof(_jit_block_stack_entry_t)); if(!stack) { jit_free(blocks); @@ -847,14 +869,14 @@ _jit_block_record_label(jit_block_t block) { num *= 2; } - blocks = (jit_block_t *)jit_realloc - (builder->label_blocks, num * sizeof(jit_block_t)); + blocks = (jit_block_t *)jit_realloc(builder->label_blocks, + num * sizeof(jit_block_t)); if(!blocks) { return 0; } jit_memzero(blocks + builder->max_label_blocks, - sizeof(jit_block_t) * (num - builder->max_label_blocks)); + sizeof(jit_block_t) * (num - builder->max_label_blocks)); builder->label_blocks = blocks; builder->max_label_blocks = num; } @@ -862,6 +884,60 @@ _jit_block_record_label(jit_block_t block) return 1; } +jit_insn_t +_jit_block_add_insn(jit_block_t block) +{ + int max_insns; + jit_insn_t insns; + + /* Make space for the instruction in the block's instruction list */ + if(block->num_insns == block->max_insns) + { + max_insns = block->max_insns ? block->max_insns * 2 : 4; + insns = (jit_insn_t) jit_realloc(block->insns, + max_insns * sizeof(struct _jit_insn)); + if(!insns) + { + return 0; + } + + block->insns = insns; + block->max_insns = max_insns; + } + + /* Zero-init the instruction */ + jit_memzero(&block->insns[block->num_insns], sizeof(struct _jit_insn)); + + /* Return the instruction, which is now ready to fill in */ + return &block->insns[block->num_insns++]; +} + +jit_insn_t +_jit_block_get_last(jit_block_t block) +{ + if(block->num_insns > 0) + { + return &block->insns[block->num_insns - 1]; + } + else + { + return 0; + } +} + +int +_jit_block_is_final(jit_block_t block) +{ + for(block = block->next; block; block = block->next) + { + if(block->num_insns) + { + return 0; + } + } + return 1; +} + /*@ * @deftypefun jit_function_t jit_block_get_function (jit_block_t @var{block}) * Get the function that a particular @var{block} belongs to. @@ -983,61 +1059,6 @@ jit_block_from_label(jit_function_t func, jit_label_t label) } } -jit_insn_t -_jit_block_add_insn(jit_block_t block) -{ - jit_builder_t builder = block->func->builder; - jit_insn_t insn; - int num; - jit_insn_t *insns; - - /* Allocate the instruction from the builder's memory pool */ - insn = jit_memory_pool_alloc(&(builder->insn_pool), struct _jit_insn); - if(!insn) - { - return 0; - } - - /* Make space for the instruction in the function's instruction list */ - if(builder->num_insns >= builder->max_insns) - { - num = builder->max_insns * 2; - if(num < 64) - { - num = 64; - } - insns = (jit_insn_t *)jit_realloc(builder->insns, num * sizeof(jit_insn_t)); - if(!insns) - { - return 0; - } - builder->insns = insns; - builder->max_insns = num; - } - else - { - insns = builder->insns; - } - insns[builder->num_insns] = insn; - block->last_insn = (builder->num_insns)++; - - /* Return the instruction, which is now ready to fill in */ - return insn; -} - -jit_insn_t -_jit_block_get_last(jit_block_t block) -{ - if(block->first_insn <= block->last_insn) - { - return block->func->builder->insns[block->last_insn]; - } - else - { - return 0; - } -} - /*@ * @deftypefun int jit_block_set_meta (jit_block_t @var{block}, int @var{type}, void *@var{data}, jit_meta_free_func @var{free_data}) * Tag a block with some metadata. Returns zero if out of memory. diff --git a/jit/jit-function.c b/jit/jit-function.c index b5183ee..fe423f5 100644 --- a/jit/jit-function.c +++ b/jit/jit-function.c @@ -189,7 +189,6 @@ int _jit_function_ensure_builder(jit_function_t func) /* Initialize the function builder */ jit_memory_pool_init(&(func->builder->value_pool), struct _jit_value); - jit_memory_pool_init(&(func->builder->insn_pool), struct _jit_insn); jit_memory_pool_init(&(func->builder->edge_pool), struct _jit_edge); jit_memory_pool_init(&(func->builder->meta_pool), struct _jit_meta); @@ -230,11 +229,9 @@ void _jit_function_free_builder(jit_function_t func) { _jit_block_free(func); jit_memory_pool_free(&(func->builder->edge_pool), 0); - jit_memory_pool_free(&(func->builder->insn_pool), 0); jit_memory_pool_free(&(func->builder->value_pool), _jit_value_free); jit_memory_pool_free(&(func->builder->meta_pool), _jit_meta_free_one); jit_free(func->builder->param_values); - jit_free(func->builder->insns); jit_free(func->builder->label_blocks); jit_free(func->builder); func->builder = 0; diff --git a/jit/jit-insn.c b/jit/jit-insn.c index 9e53c9e..cca465a 100644 --- a/jit/jit-insn.c +++ b/jit/jit-insn.c @@ -25,16 +25,16 @@ #include "jit-setjmp.h" #include #if HAVE_STDLIB_H - #include +# include #endif #if HAVE_ALLOCA_H - #include +# include #endif #ifdef JIT_WIN32_PLATFORM - #include - #ifndef alloca - #define alloca _alloca - #endif +# include +# ifndef alloca +# define alloca _alloca +# endif #endif /*@ @@ -7940,10 +7940,11 @@ int jit_insn_mark_breakpoint * Initialize an iterator to point to the first instruction in @var{block}. * @end deftypefun @*/ -void jit_insn_iter_init(jit_insn_iter_t *iter, jit_block_t block) +void +jit_insn_iter_init(jit_insn_iter_t *iter, jit_block_t block) { iter->block = block; - iter->posn = block->first_insn; + iter->posn = 0; } /*@ @@ -7951,10 +7952,11 @@ void jit_insn_iter_init(jit_insn_iter_t *iter, jit_block_t block) * Initialize an iterator to point to the last instruction in @var{block}. * @end deftypefun @*/ -void jit_insn_iter_init_last(jit_insn_iter_t *iter, jit_block_t block) +void +jit_insn_iter_init_last(jit_insn_iter_t *iter, jit_block_t block) { iter->block = block; - iter->posn = block->last_insn + 1; + iter->posn = block->num_insns; } /*@ @@ -7963,11 +7965,12 @@ void jit_insn_iter_init_last(jit_insn_iter_t *iter, jit_block_t block) * when there are no further instructions in the block. * @end deftypefun @*/ -jit_insn_t jit_insn_iter_next(jit_insn_iter_t *iter) +jit_insn_t +jit_insn_iter_next(jit_insn_iter_t *iter) { - if(iter->posn <= iter->block->last_insn) + if(iter->posn < iter->block->num_insns) { - return iter->block->func->builder->insns[(iter->posn)++]; + return &iter->block->insns[(iter->posn)++]; } else { @@ -7981,11 +7984,12 @@ jit_insn_t jit_insn_iter_next(jit_insn_iter_t *iter) * when there are no further instructions in the block. * @end deftypefun @*/ -jit_insn_t jit_insn_iter_previous(jit_insn_iter_t *iter) +jit_insn_t +jit_insn_iter_previous(jit_insn_iter_t *iter) { - if(iter->posn > iter->block->first_insn) + if(iter->posn > 0) { - return iter->block->func->builder->insns[--(iter->posn)]; + return &iter->block->insns[--(iter->posn)]; } else { diff --git a/jit/jit-internal.h b/jit/jit-internal.h index cf2abdd..7e7f951 100644 --- a/jit/jit-internal.h +++ b/jit/jit-internal.h @@ -204,9 +204,10 @@ struct _jit_block jit_function_t func; jit_label_t label; - /* Block's first and last instruction */ - int first_insn; - int last_insn; + /* List of all instructions in this block */ + jit_insn_t insns; + int num_insns; + int max_insns; /* Next and previous blocks in the function's linear block list */ jit_block_t next; @@ -332,6 +333,9 @@ struct _jit_builder /* The current block that is being constructed */ jit_block_t current_block; + /* The list of deleted blocks */ + jit_block_t deleted_blocks; + /* Blocks sorted in order required by an optimization pass */ jit_block_t *block_order; int num_block_order; @@ -365,14 +369,8 @@ struct _jit_builder /* Generate position-independent code */ unsigned position_independent : 1; - /* List of all instructions in this function */ - jit_insn_t *insns; - int num_insns; - int max_insns; - /* Memory pools that contain values, instructions, and metadata blocks */ jit_memory_pool value_pool; - jit_memory_pool insn_pool; jit_memory_pool edge_pool; jit_memory_pool meta_pool; @@ -634,6 +632,12 @@ jit_insn_t _jit_block_add_insn(jit_block_t block); */ jit_insn_t _jit_block_get_last(jit_block_t block); +/* + * The block goes just before the function end possibly excluding + * some empty blocks. + */ +int _jit_block_is_final(jit_block_t block); + /* * Free one element in a metadata list. */ diff --git a/jit/jit-rules-alpha.c b/jit/jit-rules-alpha.c index df8821d..bdd51fb 100644 --- a/jit/jit-rules-alpha.c +++ b/jit/jit-rules-alpha.c @@ -609,14 +609,10 @@ void jump_to_epilog(jit_gencode_t gen, alpha_inst inst, jit_block_t block) { * If the epilog is the next thing that we will output, * then fall through to the epilog directly. */ - - block = block->next; - - while (!block && block->first_insn > block->last_insn) - block = block->next; - - if (!block) + if(_jit_block_is_final(block)) + { return; + } /* * fixups are slightly strange for the alpha port. On alpha you diff --git a/jit/jit-rules-arm.c b/jit/jit-rules-arm.c index 748a50a..cfe3930 100644 --- a/jit/jit-rules-arm.c +++ b/jit/jit-rules-arm.c @@ -629,13 +629,8 @@ static void jump_to_epilog int offset; /* If the epilog is the next thing that we will output, - then fall through to the epilog directly */ - block = block->next; - while(block != 0 && block->first_insn > block->last_insn) - { - block = block->next; - } - if(!block) + then fall through to the epilog directly */ + if(_jit_block_is_final(block)) { return; } diff --git a/jit/jit-rules-x86-64.c b/jit/jit-rules-x86-64.c index 4eab821..9c5f3fc 100644 --- a/jit/jit-rules-x86-64.c +++ b/jit/jit-rules-x86-64.c @@ -1316,12 +1316,7 @@ jump_to_epilog(jit_gencode_t gen, unsigned char *inst, jit_block_t block) /* If the epilog is the next thing that we will output, then fall through to the epilog directly */ - block = block->next; - while(block != 0 && block->first_insn > block->last_insn) - { - block = block->next; - } - if(!block) + if(_jit_block_is_final(block)) { return inst; } diff --git a/jit/jit-rules-x86.c b/jit/jit-rules-x86.c index abac940..1669856 100644 --- a/jit/jit-rules-x86.c +++ b/jit/jit-rules-x86.c @@ -1311,17 +1311,12 @@ static unsigned char *output_branch /* * Jump to the current function's epilog. */ -static unsigned char *jump_to_epilog - (jit_gencode_t gen, unsigned char *inst, jit_block_t block) +static unsigned char * +jump_to_epilog(jit_gencode_t gen, unsigned char *inst, jit_block_t block) { /* If the epilog is the next thing that we will output, then fall through to the epilog directly */ - block = block->next; - while(block != 0 && block->first_insn > block->last_insn) - { - block = block->next; - } - if(!block) + if(_jit_block_is_final(block)) { return inst; } @@ -1336,8 +1331,8 @@ static unsigned char *jump_to_epilog /* * Throw a builtin exception. */ -static unsigned char *throw_builtin - (unsigned char *inst, jit_function_t func, int type) +static unsigned char * +throw_builtin(unsigned char *inst, jit_function_t func, int type) { /* We need to update "catch_pc" if we have a "try" block */ if(func->builder->setjmp_value != 0) -- 2.47.3