From 2addb3e18bee68a40a1500d152e1abbb3e3cc4f6 Mon Sep 17 00:00:00 2001 From: Rhys Weatherley Date: Thu, 20 May 2004 02:15:52 +0000 Subject: [PATCH] Perform peephole optimization of branches to branches before live variable analysis, so that the back ends don't need to worry about jump threading. --- ChangeLog | 5 ++ jit/jit-block.c | 104 +++++++++++++++++++++++++++++++++++++++ jit/jit-internal.h | 7 +++ jit/jit-live.c | 1 + jit/jit-rules-interp.c | 107 ++++++++--------------------------------- 5 files changed, 138 insertions(+), 86 deletions(-) diff --git a/ChangeLog b/ChangeLog index 9d3e55d..871c03b 100644 --- a/ChangeLog +++ b/ChangeLog @@ -5,6 +5,11 @@ convert constant conditional branches such as "if true goto L" into unconditional branches. + * jit/jit-block.c, jit/jit-internal.h, jit/jit-live.c, + jit/jit-rules-interp.c: perform peephole optimization of + branches to branches before live variable analysis, so that + the back ends don't need to worry about jump threading. + 2004-05-15 Rhys Weatherley * tools/gen-apply.c: fix a macro generation bug for Win32 systems. diff --git a/jit/jit-block.c b/jit/jit-block.c index 8878ecb..8ef0a89 100644 --- a/jit/jit-block.c +++ b/jit/jit-block.c @@ -382,3 +382,107 @@ int jit_block_ends_in_dead(jit_block_t block) { return block->ends_in_dead; } + +/* + * Determine if the next block after "block" has "label". + */ +static int block_branches_to_next(jit_block_t block, jit_label_t label) +{ + jit_insn_t insn; + block = block->next; + while(block != 0) + { + if(block->label == label) + { + return 1; + } + if(block->first_insn < block->last_insn) + { + /* This block contains more than one instruction, so the + first cannot be an unconditional branch */ + break; + } + else if(block->first_insn == block->last_insn) + { + insn = block->func->builder->insns[block->first_insn]; + if(insn->opcode == JIT_OP_BR) + { + /* If the instruction branches to its next block, + then it is equivalent to an empty block. If it + does not, then we have to stop scanning here */ + if(!block_branches_to_next(block, (jit_label_t)(insn->dest))) + { + return 0; + } + } + else + { + /* The block does not contain an unconditional branch */ + break; + } + } + block = block->next; + } + return 0; +} + +void _jit_block_peephole_branch(jit_block_t block) +{ + jit_insn_t insn; + jit_insn_t new_insn; + jit_label_t label; + jit_block_t new_block; + int count; + + /* Bail out if the last instruction is not actually a branch */ + insn = _jit_block_get_last(block); + if(!insn || insn->opcode < JIT_OP_BR || insn->opcode > JIT_OP_BR_NFGE_INV) + { + return; + } + + /* Thread unconditional branches. We stop if we jump back to the + starting block, or follow more than 32 links. This is to prevent + infinite loops in situations like "while true do nothing" */ + label = (jit_label_t)(insn->dest); + count = 32; + while(label != block->label && count > 0) + { + new_block = jit_block_from_label(block->func, label); + while(new_block != 0 && new_block->first_insn > new_block->last_insn) + { + /* Skip past empty blocks */ + new_block = new_block->next; + } + if(!new_block) + { + break; + } + if(new_block->first_insn < new_block->last_insn) + { + /* There is more than one instruction in this block, + so the first instruction cannot be a branch */ + break; + } + new_insn = new_block->func->builder->insns[new_block->first_insn]; + if(new_insn->opcode != JIT_OP_BR) + { + /* The target block does not contain an unconditional branch */ + break; + } + label = (jit_label_t)(new_insn->dest); + --count; + } + insn->dest = (jit_value_t)label; + + /* Determine if we are branching to the immediately following block */ + if(block_branches_to_next(block, label)) + { + /* Remove the branch instruction, because it has no effect. + It doesn't matter if the branch is unconditional or + conditional. Any side-effects in a conditional expression + would have already been computed by now. Expressions without + side-effects will be optimized away by liveness analysis */ + --(block->last_insn); + } +} diff --git a/jit/jit-internal.h b/jit/jit-internal.h index 249f810..d2f9acd 100644 --- a/jit/jit-internal.h +++ b/jit/jit-internal.h @@ -524,6 +524,13 @@ jit_insn_t _jit_block_add_insn(jit_block_t block); */ jit_insn_t _jit_block_get_last(jit_block_t block); +/* + * Perform peephole optimization on the branch instruction at the + * end of a block (if there is a branch). This will resolve branches + * to branches, and remove branches to the following block. + */ +void _jit_block_peephole_branch(jit_block_t block); + /* * Free one element in a metadata list. */ diff --git a/jit/jit-live.c b/jit/jit-live.c index 882a54b..5193313 100644 --- a/jit/jit-live.c +++ b/jit/jit-live.c @@ -199,6 +199,7 @@ void _jit_function_compute_liveness(jit_function_t func) jit_block_t block = func->builder->first_block; while(block != 0) { + _jit_block_peephole_branch(block); compute_liveness_for_block(block); block = block->next; } diff --git a/jit/jit-rules-interp.c b/jit/jit-rules-interp.c index fc5f051..b092ade 100644 --- a/jit/jit-rules-interp.c +++ b/jit/jit-rules-interp.c @@ -839,54 +839,6 @@ void _jit_gen_fix_value(jit_value_t value) } } -/* - * Get the destination of a branch instruction, and thread through - * unconditional branches that this one points to. Returns - * "jit_label_undefined" if we are branching to the next block - * (i.e. the branch instruction can be quietly eliminated). - */ -static jit_label_t get_branch_dest(jit_block_t block, jit_insn_t insn) -{ - jit_label_t label; - jit_block_t new_block; - int max_thread; - jit_insn_iter_t iter; - - /* Get the starting label */ - label = (jit_label_t)(insn->dest); - - /* Bail out now if we are within an exception block, because we - don't want to thread to jumps outside the "finally" context */ - if(block->block_eh && insn->opcode == JIT_OP_BR) - { - return label; - } - - /* Thread unconditional jumps at the destination */ - max_thread = 20; - while(max_thread > 0 && - (new_block = jit_block_from_label(block->func, label)) != 0) - { - jit_insn_iter_init(&iter, new_block); - insn = jit_insn_iter_next(&iter); - if(!insn || insn->opcode != JIT_OP_BR) - { - break; - } - label = (jit_label_t)(insn->dest); - --max_thread; - } - - /* Determine if we are branching to the next block */ - if(block->next && block->next->label == label) - { - return jit_label_undefined; - } - - /* Return the destination label to the caller */ - return label; -} - /* * Record that a destination is now in a particular register. */ @@ -937,29 +889,26 @@ void _jit_gen_insn(jit_gencode_t gen, jit_function_t func, { /* Unconditional branch */ _jit_regs_spill_all(gen); - label = get_branch_dest(block, insn); - if(label != jit_label_undefined) + label = (jit_label_t)(insn->dest); + branch: + pc = (void **)(gen->posn.ptr); + jit_cache_opcode(&(gen->posn), insn->opcode); + block = jit_block_from_label(func, label); + if(!block) { - branch: - pc = (void **)(gen->posn.ptr); - jit_cache_opcode(&(gen->posn), insn->opcode); - block = jit_block_from_label(func, label); - if(!block) - { - break; - } - if(block->address) - { - /* We already know the address of the block */ - jit_cache_native - (&(gen->posn), ((void **)(block->address)) - pc); - } - else - { - /* Record this position on the block's fixup list */ - jit_cache_native(&(gen->posn), block->fixup_list); - block->fixup_list = (void *)pc; - } + break; + } + if(block->address) + { + /* We already know the address of the block */ + jit_cache_native + (&(gen->posn), ((void **)(block->address)) - pc); + } + else + { + /* Record this position on the block's fixup list */ + jit_cache_native(&(gen->posn), block->fixup_list); + block->fixup_list = (void *)pc; } } break; @@ -971,14 +920,7 @@ void _jit_gen_insn(jit_gencode_t gen, jit_function_t func, case JIT_OP_CALL_FILTER: { /* Unary branch */ - label = get_branch_dest(block, insn); - if(label == jit_label_undefined) - { - /* We are falling through, no matter what the test - says, so optimize the entire instruction away */ - _jit_regs_spill_all(gen); - break; - } + label = (jit_label_t)(insn->dest); if(!_jit_regs_is_top(gen, insn->value1) || _jit_regs_num_used(gen, 0) != 1) { @@ -1049,14 +991,7 @@ void _jit_gen_insn(jit_gencode_t gen, jit_function_t func, case JIT_OP_BR_NFGE_INV: { /* Binary branch */ - label = get_branch_dest(block, insn); - if(label == jit_label_undefined) - { - /* We are falling through, no matter what the test - says, so optimize the entire instruction away */ - _jit_regs_spill_all(gen); - break; - } + label = (jit_label_t)(insn->dest); if(!_jit_regs_is_top_two(gen, insn->value1, insn->value2) || _jit_regs_num_used(gen, 0) != 2) { -- 2.47.3