X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fjumpthreading.c;h=754c3f313f95064b48e144acf67f104077e6326c;hb=5d0dc80583152b7e75989b205755bdb0cd1ce0aa;hp=095f6a001618f7f854a6cbf04b32ed0e9d397ad6;hpb=6f068af98daa4725d60e5d23a8f98ec2841cfa44;p=libfirm diff --git a/ir/opt/jumpthreading.c b/ir/opt/jumpthreading.c index 095f6a001..754c3f313 100644 --- a/ir/opt/jumpthreading.c +++ b/ir/opt/jumpthreading.c @@ -22,13 +22,13 @@ * @brief Path-Sensitive Jump Threading * @date 10. Sep. 2006 * @author Christoph Mallon, Matthias Braun - * @version $Id$ */ #include "config.h" #include "iroptimize.h" #include +#include #include "array_t.h" #include "debug.h" #include "ircons.h" @@ -49,7 +49,7 @@ #undef AVOID_PHIB -DEBUG_ONLY(static firm_dbg_module_t *dbg); +DEBUG_ONLY(static firm_dbg_module_t *dbg;) /** * Add the new predecessor x to node node, which is either a Block or a Phi @@ -60,7 +60,7 @@ static void add_pred(ir_node* node, ir_node* x) int n; int i; - assert(is_Block(node) || is_Phi(node)); + assert(is_Block(node)); n = get_irn_arity(node); NEW_ARR_A(ir_node*, ins, n + 1); @@ -149,8 +149,6 @@ static void construct_ssa(ir_node *orig_block, ir_node *orig_val, { ir_graph *irg; ir_mode *mode; - const ir_edge_t *edge; - const ir_edge_t *next; /* no need to do anything */ if (orig_val == second_val) @@ -167,7 +165,7 @@ static void construct_ssa(ir_node *orig_block, ir_node *orig_val, ssa_second_def = second_val; /* Only fix the users of the first, i.e. the original node */ - foreach_out_edge_safe(orig_val, edge, next) { + foreach_out_edge_safe(orig_val, edge) { ir_node *user = get_edge_src_irn(edge); int j = get_edge_src_pos(edge); ir_node *user_block = get_nodes_block(user); @@ -194,6 +192,16 @@ static void construct_ssa(ir_node *orig_block, ir_node *orig_val, } } +/** + * jumpthreading produces critical edges, e.g. B-C: + * A A + * \ / \ | + * B => B | + * / \ / \| + * C C + * + * By splitting this critical edge more threadings might be possible. + */ static void split_critical_edge(ir_node *block, int pos) { ir_graph *irg = get_irn_irg(block); @@ -267,8 +275,6 @@ static ir_node *copy_and_fix_node(const jumpthreading_env_t *env, static void copy_and_fix(const jumpthreading_env_t *env, ir_node *block, ir_node *copy_block, int j) { - const ir_edge_t *edge; - /* Look at all nodes in the cond_block and copy them into pred */ foreach_out_edge(block, edge) { ir_node *node = get_edge_src_irn(edge); @@ -276,22 +282,21 @@ static void copy_and_fix(const jumpthreading_env_t *env, ir_node *block, ir_mode *mode; if (is_End(node)) { - /* edge is a Keep edge. If the end block is unreachable via normal control flow, - * we must maintain end's reachability with Keeps. + /* edge is a Keep edge. If the end block is unreachable via normal + * control flow, we must maintain end's reachability with Keeps. */ keep_alive(copy_block); continue; } /* ignore control flow */ mode = get_irn_mode(node); - if (mode == mode_X || is_Cond(node)) + if (mode == mode_X || is_Cond(node) || is_Switch(node)) continue; #ifdef AVOID_PHIB /* we may not copy mode_b nodes, because this could produce Phi with * mode_bs which can't be handled in all backends. Instead we duplicate * the node and move it to its users */ if (mode == mode_b) { - const ir_edge_t *edge, *next; ir_node *pred; int pn; @@ -300,7 +305,7 @@ static void copy_and_fix(const jumpthreading_env_t *env, ir_node *block, pred = get_Proj_pred(node); pn = get_Proj_proj(node); - foreach_out_edge_safe(node, edge, next) { + foreach_out_edge_safe(node, edge) { ir_node *cmp_copy; ir_node *user = get_edge_src_irn(edge); int pos = get_edge_src_pos(edge); @@ -337,7 +342,7 @@ static void copy_and_fix(const jumpthreading_env_t *env, ir_node *block, ir_mode *mode; mode = get_irn_mode(node); - if (mode == mode_X || is_Cond(node)) + if (mode == mode_X || is_Cond(node) || is_Switch(node)) continue; #ifdef AVOID_PHIB if (mode == mode_b) @@ -349,6 +354,17 @@ static void copy_and_fix(const jumpthreading_env_t *env, ir_node *block, copy_node = (ir_node*)get_irn_link(node); construct_ssa(block, node, copy_block, copy_node); } + + /* make sure new nodes are kept alive if old nodes were */ + ir_graph *irg = get_irn_irg(block); + ir_node *end = get_irg_end(irg); + for (int i = 0, arity = get_End_n_keepalives(end); i < arity; ++i) { + ir_node *keep = get_End_keepalive(end, i); + if (get_irn_visited(keep) < env->visited_nr || is_Block(keep)) + continue; + ir_node *copy = get_irn_link(keep); + add_End_keepalive(end, copy); + } } /** @@ -462,7 +478,7 @@ static ir_node *find_const_or_confirm(jumpthreading_env_t *env, ir_node *jump, DB(( dbg, LEVEL_1, "> Found jump threading candidate %+F->%+F\n", - env->true_block, block + block, env->true_block )); /* adjust true_block to point directly towards our jump */ @@ -527,7 +543,7 @@ static ir_node *find_candidate(jumpthreading_env_t *env, ir_node *jump, DB(( dbg, LEVEL_1, "> Found jump threading candidate %+F->%+F\n", - env->true_block, block + block, env->true_block )); /* adjust true_block to point directly towards our jump */ @@ -623,17 +639,17 @@ static ir_node *find_candidate(jumpthreading_env_t *env, ir_node *jump, static void thread_jumps(ir_node* block, void* data) { jumpthreading_env_t env; - int *changed = (int*)data; + bool *changed = (bool*)data; ir_node *selector; ir_node *projx; ir_node *cond; ir_node *copy_block; int selector_evaluated; - const ir_edge_t *edge, *next; ir_graph *irg; ir_node *badX; int cnst_pos; + /* we do not deal with Phis, so restrict this to exactly one cfgpred */ if (get_Block_n_cfgpreds(block) != 1) return; @@ -643,15 +659,12 @@ static void thread_jumps(ir_node* block, void* data) assert(get_irn_mode(projx) == mode_X); cond = get_Proj_pred(projx); - if (!is_Cond(cond)) - return; - - selector = get_Cond_selector(cond); /* TODO handle switch Conds */ - if (get_irn_mode(selector) != mode_b) + if (!is_Cond(cond)) return; /* handle cases that can be immediately evaluated */ + selector = get_Cond_selector(cond); selector_evaluated = -1; if (is_Cmp(selector)) { ir_node *left = get_Cmp_left(selector); @@ -695,14 +708,14 @@ static void thread_jumps(ir_node* block, void* data) ir_graph *irg = get_irn_irg(block); ir_node *bad = new_r_Bad(irg, mode_X); exchange(projx, bad); - *changed = 1; + *changed = true; return; } else if (selector_evaluated == 1) { dbg_info *dbgi = get_irn_dbg_info(selector); ir_node *jmp = new_rd_Jmp(dbgi, get_nodes_block(projx)); DBG_OPT_JUMPTHREADING(projx, jmp); exchange(projx, jmp); - *changed = 1; + *changed = true; return; } @@ -716,6 +729,10 @@ static void thread_jumps(ir_node* block, void* data) if (copy_block == NULL) return; + /* We might thread the condition block of an infinite loop, + * such that there is no path to End anymore. */ + keep_alive(block); + /* we have to remove the edge towards the pred as the pred now * jumps into the true_block. We also have to shorten Phis * in our block because of this */ @@ -723,7 +740,7 @@ static void thread_jumps(ir_node* block, void* data) cnst_pos = env.cnst_pos; /* shorten Phis */ - foreach_out_edge_safe(env.cnst_pred, edge, next) { + foreach_out_edge_safe(env.cnst_pred, edge) { ir_node *node = get_edge_src_irn(edge); if (is_Phi(node)) { @@ -735,43 +752,36 @@ static void thread_jumps(ir_node* block, void* data) set_Block_cfgpred(env.cnst_pred, cnst_pos, badX); /* the graph is changed now */ - *changed = 1; + *changed = true; } void opt_jumpthreading(ir_graph* irg) { - int changed, rerun; + bool changed; + bool rerun; + + assure_irg_properties(irg, + IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE + | IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES + | IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES); FIRM_DBG_REGISTER(dbg, "firm.opt.jumpthreading"); DB((dbg, LEVEL_1, "===> Performing jumpthreading on %+F\n", irg)); - remove_critical_cf_edges(irg); - - /* ugly: jump threading might get confused by garbage nodes - * of mode_X in copy_and_fix_node(), so remove all garbage edges. */ - edges_deactivate(irg); - - edges_assure(irg); ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_IRN_VISITED); - changed = 0; + changed = false; do { - rerun = 0; + rerun = false; irg_block_walk_graph(irg, thread_jumps, NULL, &rerun); changed |= rerun; } while (rerun); ir_free_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_IRN_VISITED); - if (changed) { - /* control flow changed, some blocks may become dead */ - set_irg_outs_inconsistent(irg); - set_irg_doms_inconsistent(irg); - set_irg_extblk_inconsistent(irg); - set_irg_loopinfo_inconsistent(irg); - set_irg_entity_usage_state(irg, ir_entity_usage_not_computed); - } + confirm_irg_properties(irg, + changed ? IR_GRAPH_PROPERTIES_NONE : IR_GRAPH_PROPERTIES_ALL); } /* Creates an ir_graph pass for opt_jumpthreading. */