X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fjumpthreading.c;h=3a18401acd34b8a46606916126cff470a3ac16e1;hb=8c9921a1fc166552f6e416434fd8394a4fc210a3;hp=135ede9dd9827db039165cf9da85231fcf48edde;hpb=4f8e80463195b1fee6ebbeefb59722faf76134cc;p=libfirm diff --git a/ir/opt/jumpthreading.c b/ir/opt/jumpthreading.c index 135ede9dd..3a18401ac 100644 --- a/ir/opt/jumpthreading.c +++ b/ir/opt/jumpthreading.c @@ -22,7 +22,6 @@ * @brief Path-Sensitive Jump Threading * @date 10. Sep. 2006 * @author Christoph Mallon, Matthias Braun - * @version $Id$ */ #include "config.h" @@ -46,10 +45,11 @@ #include "iropt_dbg.h" #include "irpass.h" #include "vrp.h" +#include "opt_manage.h" #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); @@ -83,10 +83,10 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode, ir_node **in; ir_node *dummy; - /* This is needed because we create bads sometimes */ - if (is_Bad(block) || is_Block_dead(block)) { + /* In case of a bad input to a block we need to return the bad value */ + if (is_Bad(block)) { ir_graph *irg = get_irn_irg(block); - return new_r_Bad(irg); + return new_r_Bad(irg, mode); } /* the other defs can't be marked for cases where a user of the original @@ -194,6 +194,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); @@ -275,9 +285,16 @@ static void copy_and_fix(const jumpthreading_env_t *env, ir_node *block, ir_node *copy; 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. + */ + 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 @@ -330,7 +347,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) @@ -624,9 +641,10 @@ static void thread_jumps(ir_node* block, void* data) int selector_evaluated; const ir_edge_t *edge, *next; ir_graph *irg; - ir_node *bad; + 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; @@ -636,15 +654,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); @@ -686,7 +701,7 @@ static void thread_jumps(ir_node* block, void* data) if (selector_evaluated == 0) { ir_graph *irg = get_irn_irg(block); - bad = new_r_Bad(irg); + ir_node *bad = new_r_Bad(irg, mode_X); exchange(projx, bad); *changed = 1; return; @@ -709,37 +724,41 @@ 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 */ - bad = new_r_Bad(irg); + badX = new_r_Bad(irg, mode_X); cnst_pos = env.cnst_pos; /* shorten Phis */ foreach_out_edge_safe(env.cnst_pred, edge, next) { ir_node *node = get_edge_src_irn(edge); - if (is_Phi(node)) + if (is_Phi(node)) { + ir_node *bad = new_r_Bad(irg, get_irn_mode(node)); set_Phi_pred(node, cnst_pos, bad); + } } - set_Block_cfgpred(env.cnst_pred, cnst_pos, bad); + set_Block_cfgpred(env.cnst_pred, cnst_pos, badX); /* the graph is changed now */ *changed = 1; } -void opt_jumpthreading(ir_graph* irg) +static ir_graph_state_t do_jumpthread(ir_graph* irg) { int changed, rerun; + ir_graph_state_t res = 0; FIRM_DBG_REGISTER(dbg, "firm.opt.jumpthreading"); DB((dbg, LEVEL_1, "===> Performing jumpthreading on %+F\n", irg)); - remove_critical_cf_edges(irg); - - edges_assure(irg); ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_IRN_VISITED); changed = 0; @@ -751,18 +770,22 @@ void opt_jumpthreading(ir_graph* irg) 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); - - /* Dead code might be created. Optimize it away as it is dangerous - * to call optimize_df() an dead code. */ - optimize_cf(irg); + if (!changed) { + res |= IR_GRAPH_STATE_CONSISTENT_DOMINANCE | IR_GRAPH_STATE_CONSISTENT_ENTITY_USAGE; } + + return res; +} + +static optdesc_t opt_jumpthread = { + "jumpthreading", + IR_GRAPH_STATE_NO_UNREACHABLE_CODE | IR_GRAPH_STATE_CONSISTENT_OUT_EDGES | IR_GRAPH_STATE_NO_CRITICAL_EDGES, + do_jumpthread, +}; + +void opt_jumpthreading(ir_graph* irg) +{ + perform_irg_optimization(irg, &opt_jumpthread); } /* Creates an ir_graph pass for opt_jumpthreading. */