X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fcondeval.c;h=4b0facf00361f4b1e1bc5d8fcd5e88c8e4be597d;hb=b4a3d8471ab4a2ad12041f4ef1cb2473d9b5fe4c;hp=94824800fa1d72bd67f058bbe6860dd157124edd;hpb=77b6e60bf9eec251585b02d29a5b689697aed67e;p=libfirm diff --git a/ir/opt/condeval.c b/ir/opt/condeval.c index 94824800f..4b0facf00 100644 --- a/ir/opt/condeval.c +++ b/ir/opt/condeval.c @@ -1,5 +1,5 @@ /* - * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved. * * This file is part of libFirm. * @@ -44,6 +44,9 @@ #include "irtools.h" #include "irgraph.h" #include "tv.h" +#include "opt_confirms.h" + +#undef AVOID_PHIB DEBUG_ONLY(static firm_dbg_module_t *dbg); @@ -74,38 +77,40 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) ir_node *phi; ir_node **in; - // This is needed because we create bads sometimes + /* This is needed because we create bads sometimes */ if(is_Bad(block)) return new_Bad(); - // already processed this block? + /* already processed this block? */ if(irn_visited(block)) { ir_node *value = (ir_node*) get_irn_link(block); return value; } - // blocks with only 1 pred need no phi + irg = get_irn_irg(block); + assert(block != get_irg_start_block(irg)); + + /* a Blocks with only 1 predecessor need no Phi */ n_cfgpreds = get_Block_n_cfgpreds(block); if(n_cfgpreds == 1) { ir_node *pred_block = get_Block_cfgpred_block(block, 0); - ir_node *value = search_def_and_create_phis(pred_block, mode); + ir_node *value = search_def_and_create_phis(pred_block, mode); set_irn_link(block, value); mark_irn_visited(block); return value; } - // create a new phi + /* create a new Phi */ NEW_ARR_A(ir_node*, in, n_cfgpreds); for(i = 0; i < n_cfgpreds; ++i) in[i] = new_Unknown(mode); - irg = get_irn_irg(block); phi = new_r_Phi(irg, block, n_cfgpreds, in, mode); set_irn_link(block, phi); mark_irn_visited(block); - // set phi preds + /* set Phi predecessors */ for(i = 0; i < n_cfgpreds; ++i) { ir_node *pred_block = get_Block_cfgpred_block(block, i); ir_node *pred_val = search_def_and_create_phis(pred_block, mode); @@ -130,7 +135,7 @@ static void construct_ssa(ir_node * const *blocks, ir_node * const *vals, int n_ const ir_edge_t *next; ir_node *value; - assert(n_vals > 0); + assert(n_vals == 2); irg = get_irn_irg(vals[0]); inc_irg_visited(irg); @@ -140,26 +145,26 @@ static void construct_ssa(ir_node * const *blocks, ir_node * const *vals, int n_ ir_node *value = vals[i]; ir_node *value_block = blocks[i]; - assert(get_irn_mode(value) == mode); + assert(get_irn_mode(value) == mode || is_Bad(value)); set_irn_link(value_block, value); mark_irn_visited(value_block); } - // Only fix the users of the first, i.e. the original node + /* Only fix the users of the first, i.e. the original node */ value = vals[0]; - // this can happen when fixing phi preds, we mustn't fix the users - if(get_nodes_block(value) != blocks[0]) return; - foreach_out_edge_safe(value, edge, next) { ir_node *user = get_edge_src_irn(edge); int j = get_edge_src_pos(edge); ir_node *user_block = get_nodes_block(user); ir_node *newval; - // ignore keeps - if(get_irn_op(user) == op_End) + /* ignore keeps */ + if (is_End(user)) + continue; + + if (user_block == blocks[1]) continue; DB((dbg, LEVEL_3, ">>> Fixing user %+F (pred %d == %+F)\n", user, j, get_irn_n(user, j))); @@ -171,7 +176,7 @@ static void construct_ssa(ir_node * const *blocks, ir_node * const *vals, int n_ newval = search_def_and_create_phis(user_block, mode); } - // don't fix newly created phis from the SSA construction + /* don't fix newly created Phis from the SSA construction */ if (newval != user) { DB((dbg, LEVEL_4, ">>>> Setting input %d of %+F to %+F\n", j, user, newval)); set_irn_n(user, j, newval); @@ -193,16 +198,58 @@ static void split_critical_edge(ir_node *block, int pos) { typedef struct condeval_env_t { ir_node *true_block; - pn_Cmp pnc; + ir_node *cmp; /**< The Compare node that might be partial evaluated */ + pn_Cmp pnc; /**< The Compare mode of the Compare node. */ ir_node *cnst; tarval *tv; - unsigned long visited_nr; + ir_visited_t visited_nr; ir_node *cnst_pred; /**< the block before the constant */ int cnst_pos; /**< the pos to the constant block (needed to kill that edge later) */ } condeval_env_t; +static ir_node *copy_and_fix_node(const condeval_env_t *env, ir_node *block, + ir_node *copy_block, int j, ir_node *node) { + int i, arity; + ir_node *copy; + + /* we can evaluate Phis right now, all other nodes get copied */ + if (is_Phi(node)) { + copy = get_Phi_pred(node, j); + /* we might have to evaluate a Phi-cascade */ + if(get_irn_visited(copy) >= env->visited_nr) { + copy = get_irn_link(copy); + } + } else { + copy = exact_copy(node); + set_nodes_block(copy, copy_block); + + assert(get_irn_mode(copy) != mode_X); + + arity = get_irn_arity(copy); + for(i = 0; i < arity; ++i) { + ir_node *pred = get_irn_n(copy, i); + ir_node *new_pred; + + if(get_nodes_block(pred) != block) + continue; + + if(get_irn_visited(pred) >= env->visited_nr) { + new_pred = get_irn_link(pred); + } else { + new_pred = copy_and_fix_node(env, block, copy_block, j, pred); + } + set_irn_n(copy, i, new_pred); + } + } + + set_irn_link(node, copy); + set_irn_visited(node, env->visited_nr); + + return copy; +} + static void copy_and_fix(const condeval_env_t *env, ir_node *block, ir_node *copy_block, int j) { const ir_edge_t *edge; @@ -211,15 +258,22 @@ static void copy_and_fix(const condeval_env_t *env, ir_node *block, foreach_out_edge(block, edge) { ir_node *node = get_edge_src_irn(edge); ir_node *copy; - ir_mode *mode = get_irn_mode(node); + ir_mode *mode; + + if (is_Block(node)) { + /* Block->Block edge, should be the MacroBlock edge */ + assert(get_Block_MacroBlock(node) == block && "Block->Block edge found"); + continue; + } /* ignore control flow */ + mode = get_irn_mode(node); if (mode == mode_X || is_Cond(node)) continue; -#if 1 - /* we may not copy mode_b nodes, because this could produce phi with +#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 it's users */ + * the node and move it to its users */ if (mode == mode_b) { const ir_edge_t *edge, *next; ir_node *pred; @@ -248,19 +302,10 @@ static void copy_and_fix(const condeval_env_t *env, ir_node *block, } #endif - /* we can evaluate Phis right now, all other nodes get copied */ - if (is_Phi(node)) { - copy = get_Phi_pred(node, j); - } else { - copy = exact_copy(node); - set_nodes_block(copy, copy_block); - } - - set_irn_link(node, copy); - set_irn_visited(node, env->visited_nr); + copy = copy_and_fix_node(env, block, copy_block, j, node); /* we might hit values in blocks that have already been processed by a - * recursive find_phi_with_const call */ + * recursive find_phi_with_const() call */ assert(get_irn_visited(copy) <= env->visited_nr); if(get_irn_visited(copy) >= env->visited_nr) { ir_node *prev_copy = get_irn_link(copy); @@ -274,12 +319,21 @@ static void copy_and_fix(const condeval_env_t *env, ir_node *block, ir_node *vals[2]; ir_node *blocks[2]; ir_node *node = get_edge_src_irn(edge); - ir_mode *mode = get_irn_mode(node); + ir_mode *mode; + + if (is_Block(node)) { + /* Block->Block edge, should be the MacroBlock edge */ + assert(get_Block_MacroBlock(node) == block && "Block->Block edge found"); + continue; + } + mode = get_irn_mode(node); if (mode == mode_X || is_Cond(node)) continue; +#ifdef AVOID_PHIB if (mode == mode_b) continue; +#endif DB((dbg, LEVEL_2, ">> Fixing users of %+F\n", node)); @@ -291,31 +345,78 @@ static void copy_and_fix(const condeval_env_t *env, ir_node *block, } } -static int eval_cmp(pn_Cmp pnc, tarval *tv1, tarval *tv2) { - pn_Cmp cmp_result = tarval_cmp(tv1, tv2); +/** + * returns whether the cmp evaluates to true or false, or can't be evaluated! + * 1: true, 0: false, -1: can't evaluate + * + * @param pnc the compare mode of the Compare + * @param tv_left the left tarval + * @param tv_right the right tarval + */ +static int eval_cmp_tv(pn_Cmp pnc, tarval *tv_left, tarval *tv_right) { + pn_Cmp cmp_result = tarval_cmp(tv_left, tv_right); - // does the compare evaluate to true? - if(cmp_result == pn_Cmp_False) - return 0; - if((cmp_result & pnc) != cmp_result) + /* does the compare evaluate to true? */ + if (cmp_result == pn_Cmp_False) + return -1; + if ((cmp_result & pnc) != cmp_result) return 0; return 1; } -static ir_node *find_const(condeval_env_t *env, ir_node *jump, ir_node *value) +/** + * returns whether the cmp evaluates to true or false, or can't be evaluated! + * 1: true, 0: false, -1: can't evaluate + * + * @param env the environment + * @param cand the candidate node, either a Const or a Confirm + */ +static int eval_cmp(condeval_env_t *env, ir_node *cand) { + if (is_Const(cand)) { + tarval *tv_cand = get_Const_tarval(cand); + tarval *tv_cmp = get_Const_tarval(env->cnst); + + return eval_cmp_tv(env->pnc, tv_cand, tv_cmp); + } else { /* a Confirm */ + tarval *res = computed_value_Cmp_Confirm(env->cmp, cand, env->cnst, env->pnc); + + if (res == tarval_bad) + return -1; + return res == tarval_b_true; + } +} + +/** + * Check for Const or Confirm with Const. + */ +static int is_Const_or_Confirm(const ir_node *node) { + if (is_Confirm(node)) + node = get_Confirm_bound(node); + return is_Const(node); +} + +/** + * get the tarval of a Const or Confirm with + */ +static tarval *get_Const_or_Confirm_tarval(const ir_node *node) { + if (is_Confirm(node)) { + if (get_Confirm_bound(node)) + node = get_Confirm_bound(node); + } + return get_Const_tarval(node); +} + +static ir_node *find_const_or_confirm(condeval_env_t *env, ir_node *jump, ir_node *value) { ir_node *block = get_nodes_block(jump); - if(irn_visited(value)) + if (irn_visited(value)) return NULL; mark_irn_visited(value); - if(is_Const(value)) { - tarval *tv_const = get_Const_tarval(env->cnst); - tarval *tv = get_Const_tarval(value); - - if(!eval_cmp(env->pnc, tv, tv_const)) { + if (is_Const_or_Confirm(value)) { + if (eval_cmp(env, value) <= 0) { return NULL; } @@ -325,12 +426,12 @@ static ir_node *find_const(condeval_env_t *env, ir_node *jump, ir_node *value) env->true_block, block )); - // adjust true_block to point directly towards our jump + /* adjust true_block to point directly towards our jump */ add_pred(env->true_block, jump); split_critical_edge(env->true_block, 0); - // we need a bigger visited nr when going back + /* we need a bigger visited nr when going back */ env->visited_nr++; return block; @@ -339,7 +440,7 @@ static ir_node *find_const(condeval_env_t *env, ir_node *jump, ir_node *value) if(is_Phi(value)) { int i, arity; - // the phi has to be in the same block as the jump + /* the Phi has to be in the same Block as the Jmp */ if(get_nodes_block(value) != block) { return NULL; } @@ -350,7 +451,7 @@ static ir_node *find_const(condeval_env_t *env, ir_node *jump, ir_node *value) ir_node *phi_pred = get_Phi_pred(value, i); ir_node *cfgpred = get_Block_cfgpred(block, i); - copy_block = find_const(env, cfgpred, phi_pred); + copy_block = find_const_or_confirm(env, cfgpred, phi_pred); if(copy_block == NULL) continue; @@ -362,7 +463,7 @@ static ir_node *find_const(condeval_env_t *env, ir_node *jump, ir_node *value) env->cnst_pos = i; } - // return now as we can't process more possibilities in 1 run + /* return now as we can't process more possibilities in 1 run */ return copy_block; } } @@ -380,10 +481,10 @@ static ir_node *find_candidate(condeval_env_t *env, ir_node *jump, } mark_irn_visited(value); - if(is_Const(value)) { - tarval *tv = get_Const_tarval(value); + if (is_Const_or_Confirm(value)) { + tarval *tv = get_Const_or_Confirm_tarval(value); - if(tv != env->tv) + if (tv != env->tv) return NULL; DB(( @@ -392,12 +493,12 @@ static ir_node *find_candidate(condeval_env_t *env, ir_node *jump, env->true_block, block )); - // adjust true_block to point directly towards our jump + /* adjust true_block to point directly towards our jump */ add_pred(env->true_block, jump); split_critical_edge(env->true_block, 0); - // we need a bigger visited nr when going back + /* we need a bigger visited nr when going back */ env->visited_nr++; return block; @@ -405,7 +506,7 @@ static ir_node *find_candidate(condeval_env_t *env, ir_node *jump, if(is_Phi(value)) { int i, arity; - // the phi has to be in the same block as the jump + /* the Phi has to be in the same Block as the Jmp */ if(get_nodes_block(value) != block) return NULL; @@ -427,7 +528,7 @@ static ir_node *find_candidate(condeval_env_t *env, ir_node *jump, env->cnst_pos = i; } - // return now as we can't process more possibilities in 1 run + /* return now as we can't process more possibilities in 1 run */ return copy_block; } } @@ -461,15 +562,16 @@ static ir_node *find_candidate(condeval_env_t *env, ir_node *jump, } /* negate condition when we're looking for the false block */ - if(env->tv == get_tarval_b_false()) { + if(env->tv == tarval_b_false) { pnc = get_negated_pnc(pnc, get_irn_mode(right)); } - // (recursively) look if a pred of a phi is a constant + /* (recursively) look if a pred of a Phi is a constant or a Confirm */ + env->cmp = cmp; env->pnc = pnc; env->cnst = right; - return find_const(env, jump, left); + return find_const_or_confirm(env, jump, left); } return NULL; @@ -496,6 +598,7 @@ static void cond_eval(ir_node* block, void* data) ir_node *projx; ir_node *cond; ir_node *copy_block; + int selector_evaluated; const ir_edge_t *edge, *next; ir_node* bad; size_t cnst_pos; @@ -513,17 +616,60 @@ static void cond_eval(ir_node* block, void* data) return; selector = get_Cond_selector(cond); - // TODO handle switch Conds + /* TODO handle switch Conds */ if (get_irn_mode(selector) != mode_b) return; + /* handle cases that can be immediately evaluated */ + selector_evaluated = -1; + if(is_Proj(selector)) { + ir_node *cmp = get_Proj_pred(selector); + if(is_Cmp(cmp)) { + ir_node *left = get_Cmp_left(cmp); + ir_node *right = get_Cmp_right(cmp); + if(is_Const(left) && is_Const(right)) { + int pnc = get_Proj_proj(selector); + tarval *tv_left = get_Const_tarval(left); + tarval *tv_right = get_Const_tarval(right); + + selector_evaluated = eval_cmp_tv(pnc, tv_left, tv_right); + if(selector_evaluated < 0) + return; + } + } + } else if (is_Const_or_Confirm(selector)) { + tarval *tv = get_Const_or_Confirm_tarval(selector); + if(tv == tarval_b_true) { + selector_evaluated = 1; + } else { + assert(tv == tarval_b_false); + selector_evaluated = 0; + } + } + + env.cnst_pred = NULL; if (get_Proj_proj(projx) == pn_Cond_false) { - env.tv = get_tarval_b_false(); + env.tv = tarval_b_false; + if(selector_evaluated >= 0) + selector_evaluated = !selector_evaluated; } else { - env.tv = get_tarval_b_true(); + env.tv = tarval_b_true; + } + + if(selector_evaluated == 0) { + bad = new_Bad(); + exchange(projx, bad); + *changed = 1; + return; + } else if(selector_evaluated == 1) { + dbg_info *dbgi = get_irn_dbg_info(selector); + ir_node *jmp = new_rd_Jmp(dbgi, current_ir_graph, get_nodes_block(projx)); + exchange(projx, jmp); + *changed = 1; + return; } - // (recursively) look if a pred of a phi is a constant + /* (recursively) look if a pred of a Phi is a constant or a Confirm */ env.true_block = block; inc_irg_visited(current_ir_graph); env.visited_nr = get_irg_visited(current_ir_graph); @@ -533,12 +679,12 @@ static void cond_eval(ir_node* block, void* data) return; /* we have to remove the edge towards the pred as the pred now - * jumps into the true_block. We also have to shorten phis + * jumps into the true_block. We also have to shorten Phis * in our block because of this */ bad = new_Bad(); cnst_pos = env.cnst_pos; - /* shorten phis */ + /* shorten Phis */ foreach_out_edge_safe(env.cnst_pred, edge, next) { ir_node *node = get_edge_src_irn(edge); @@ -564,8 +710,7 @@ void opt_cond_eval(ir_graph* irg) normalize_proj_nodes(irg); edges_assure(irg); - set_using_irn_link(irg); - set_using_visited(irg); + ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK | IR_RESOURCE_IRN_VISITED); changed = 0; do { @@ -574,14 +719,18 @@ void opt_cond_eval(ir_graph* irg) 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); + + /* Dead code might be created. Optimize it away as it is dangerous + * to call optimize_df() an dead code. */ + optimize_cf(irg); } - clear_using_visited(irg); - clear_using_irn_link(irg); }