X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fcondeval.c;h=1b1b65403a83b4e4015f8deab76202f6bd98cc76;hb=f8133875ddf70372c10a52b7266f3d04e8129486;hp=88f0f659d6e25ebddd065529da516ca57a8ec48d;hpb=0cd91c8055e5965f29bb6c89ecf32cdbb8937486;p=libfirm diff --git a/ir/opt/condeval.c b/ir/opt/condeval.c index 88f0f659d..1b1b65403 100644 --- a/ir/opt/condeval.c +++ b/ir/opt/condeval.c @@ -1,20 +1,37 @@ /* - * Project: libFIRM - * File name: ir/opt/cfopt.c - * Purpose: Partial condition evaluation - * Author: Christoph Mallon, Matthias Braun - * Created: 10. Sep. 2006 - * CVS-ID: $Id$ - * Copyright: (c) 1998-2006 Universität Karlsruhe - * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. + * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved. + * + * This file is part of libFirm. + * + * This file may be distributed and/or modified under the terms of the + * GNU General Public License version 2 as published by the Free Software + * Foundation and appearing in the file LICENSE.GPL included in the + * packaging of this file. + * + * Licensees holding valid libFirm Professional Edition licenses may use + * this file in accordance with the libFirm Commercial License. + * Agreement provided with the Software. + * + * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE + * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR + * PURPOSE. + */ + +/** + * @file + * @brief Partial condition evaluation + * @date 10. Sep. 2006 + * @author Christoph Mallon, Matthias Braun + * @version $Id$ */ #ifdef HAVE_CONFIG_H #include "config.h" #endif +#include "iroptimize.h" + #include #include "array.h" -#include "condeval.h" #include "debug.h" #include "ircons.h" #include "irgmod.h" @@ -25,6 +42,7 @@ #include "iredges.h" #include "iredges_t.h" #include "irtools.h" +#include "irgraph.h" #include "tv.h" DEBUG_ONLY(static firm_dbg_module_t *dbg); @@ -48,42 +66,6 @@ static void add_pred(ir_node* node, ir_node* x) set_irn_in(node, n + 1, ins); } -/** - * Remove predecessor j from node, which is either a Block or a Phi - * returns true if only one predecessor is left - */ -static int remove_pred(ir_node* node, int j) -{ - int n; - - assert(is_Block(node) || is_Phi(node)); - - n = get_irn_arity(node); - if (n == 2) { - ir_node* pred = get_irn_n(node, 1 - j); - - if (is_Block(node)) { - pred = get_nodes_block(pred); - edges_reroute(node, pred, current_ir_graph); - } else { - exchange(node, pred); - } - return 1; - } else { - ir_node** ins; - int i; - - NEW_ARR_A(ir_node*, ins, n - 1); - for (i = 0; i < j; i++) - ins[i] = get_irn_n(node, i); - for (i++; i < n; i++) - ins[i - 1] = get_irn_n(node, i); - - set_irn_in(node, n - 1, ins); - return 0; - } -} - static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) { int i; @@ -135,15 +117,18 @@ static ir_node *search_def_and_create_phis(ir_node *block, ir_mode *mode) } /** - * Given a set of values this function constructs SSA-form for all users of the - * values (the user are determined through the out-edges of the values). Uses - * the irn_visited flags. Works without using the dominance tree. + * Given a set of values this function constructs SSA-form for the users of the + * first value (the users are determined through the out-edges of the value). + * Uses the irn_visited flags. Works without using the dominance tree. */ static void construct_ssa(ir_node * const *blocks, ir_node * const *vals, int n_vals) { int i; ir_graph *irg; ir_mode *mode; + const ir_edge_t *edge; + const ir_edge_t *next; + ir_node *value; assert(n_vals > 0); @@ -161,35 +146,35 @@ static void construct_ssa(ir_node * const *blocks, ir_node * const *vals, int n_ mark_irn_visited(value_block); } - for(i = 0; i < n_vals; ++i) { - const ir_edge_t *edge, *next; - ir_node *value = vals[i]; + // 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[i]) { - continue; - } + // 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; + 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) - continue; + // ignore keeps + if(get_irn_op(user) == op_End) + continue; - if(is_Phi(user)) { - ir_node *pred_block = get_Block_cfgpred_block(user_block, j); - newval = search_def_and_create_phis(pred_block, mode); - } else { - newval = search_def_and_create_phis(user_block, mode); - } + DB((dbg, LEVEL_3, ">>> Fixing user %+F (pred %d == %+F)\n", user, j, get_irn_n(user, j))); - // don't fix newly created phis from the SSA construction - if(newval != user) - set_irn_n(user, j, newval); + if(is_Phi(user)) { + ir_node *pred_block = get_Block_cfgpred_block(user_block, j); + newval = search_def_and_create_phis(pred_block, mode); + } else { + newval = search_def_and_create_phis(user_block, mode); + } + + // 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); } } } @@ -223,10 +208,39 @@ static void copy_and_fix(ir_node *block, ir_node *copy_block, int j, const conde foreach_out_edge(block, edge) { ir_node *node = get_edge_src_irn(edge); ir_node *copy; + ir_mode *mode = get_irn_mode(node); /* ignore control flow */ - if (get_irn_mode(node) == mode_X) + if (mode == mode_X || is_Cond(node)) continue; + /* 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 */ + if (mode == mode_b) { + const ir_edge_t *edge, *next; + ir_node *pred; + int pn; + + assert(is_Proj(node)); + + pred = get_Proj_pred(node); + pn = get_Proj_proj(node); + + foreach_out_edge_safe(node, edge, next) { + ir_node *cmp_copy; + ir_node *user = get_edge_src_irn(edge); + int pos = get_edge_src_pos(edge); + ir_node *user_block = get_nodes_block(user); + + if(user_block == block) + continue; + + cmp_copy = exact_copy(pred); + set_nodes_block(cmp_copy, user_block); + copy = new_r_Proj(current_ir_graph, user_block, cmp_copy, mode_b, pn); + set_irn_n(user, pos, copy); + } + continue; + } /* we can evaluate Phis right now, all other nodes get copied */ if (is_Phi(node)) { @@ -253,11 +267,15 @@ static void copy_and_fix(ir_node *block, ir_node *copy_block, int j, const conde foreach_out_edge(block, edge) { ir_node *vals[2]; ir_node *blocks[2]; - ir_node *node = get_edge_src_irn(edge); + ir_mode *mode = get_irn_mode(node); - if (get_irn_mode(node) == mode_X) + if (mode == mode_X || is_Cond(node)) continue; + if (mode == mode_b) + continue; + + DB((dbg, LEVEL_2, ">> Fixing users of %+F\n", node)); blocks[0] = block; vals[0] = node; @@ -345,7 +363,7 @@ static ir_node *find_phi_with_const(ir_node *jump, ir_node *value, condeval_env_ /** - * Block-walker: searchs for the following construct + * Block-walker: searches for the following construct * * Const or Phi with constants * | @@ -452,42 +470,54 @@ static void cond_eval(ir_node* block, void* data) * jumps into the true_block. We also have to shorten phis * in our block because of this */ const ir_edge_t *edge, *next; + ir_node* bad = new_Bad(); + size_t 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)) - remove_pred(node, env.cnst_pos); + set_Phi_pred(node, cnst_pos, bad); } - remove_pred(env.cnst_pred, env.cnst_pos); + set_Block_cfgpred(env.cnst_pred, cnst_pos, bad); - // the graph is changed now + /* the graph is changed now */ *changed = 1; - set_irg_doms_inconsistent(irg); - set_irg_extblk_inconsistent(irg); - set_irg_loopinfo_inconsistent(irg); } } } void opt_cond_eval(ir_graph* irg) { - int changed; + int changed, rerun; FIRM_DBG_REGISTER(dbg, "firm.opt.condeval"); - //firm_dbg_set_mask(dbg, SET_LEVEL_5); DB((dbg, LEVEL_1, "===> Performing condition evaluation on %+F\n", irg)); - edges_assure(irg); remove_critical_cf_edges(irg); - normalize_proj_nodes(irg); + edges_assure(irg); + set_using_irn_link(irg); + set_using_visited(irg); + + changed = 0; do { - changed = 0; - irg_block_walk_graph(irg, cond_eval, NULL, &changed); - } while(changed); + rerun = 0; + irg_block_walk_graph(irg, cond_eval, NULL, &rerun); + changed |= rerun; + } while (rerun); + + if (changed) { + /* control flow changed, some blocks may become dead */ + set_irg_doms_inconsistent(irg); + set_irg_extblk_inconsistent(irg); + set_irg_loopinfo_inconsistent(irg); + } + + clear_using_visited(irg); + clear_using_irn_link(irg); }