X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fifconv.c;h=327465a4a7e2eae927fcbd58b35426b4ae65248b;hb=4cbdab238c1bd78c11cda18f18f8a4ab676e5c56;hp=a957cbbdb5f11b521459d13bcc90b169533dea71;hpb=f8b8a445d2c65da173ad640978a5687761a3a620;p=libfirm diff --git a/ir/opt/ifconv.c b/ir/opt/ifconv.c index a957cbbdb..327465a4a 100644 --- a/ir/opt/ifconv.c +++ b/ir/opt/ifconv.c @@ -1,36 +1,22 @@ /* - * Copyright (C) 1995-2008 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. + * Copyright (C) 2012 University of Karlsruhe. */ -/* - * @file ir/opt/ifconv.c +/** + * @file * @brief If conversion * @author Christoph Mallon - * @version $Id$ */ - #include "config.h" #include +#include + #include "iroptimize.h" #include "obst.h" #include "irnode_t.h" -#include "cdep.h" +#include "cdep_t.h" #include "ircons.h" #include "irgmod.h" #include "irgopt.h" @@ -38,8 +24,8 @@ #include "irtools.h" #include "array_t.h" #include "irpass_t.h" +#include "be.h" -// debug #include "irdump.h" #include "debug.h" @@ -47,38 +33,19 @@ * Environment for if-conversion. */ typedef struct walker_env { - const ir_settings_if_conv_t *params; /**< Conversion parameter. */ - int changed; /**< Set if the graph was changed. */ + arch_allow_ifconv_func allow_ifconv; + bool changed; /**< Set if the graph was changed. */ } walker_env; -DEBUG_ONLY(static firm_dbg_module_t *dbg); - -/** - * Default callback for Mux creation: allows every Mux to be created. - */ -static int default_allow_ifconv(ir_node *sel, ir_node* phi_list, int i, int j) -{ - (void) sel; - (void) phi_list; - (void) i; - (void) j; - return 1; -} - -/** - * Default options. - */ -static const ir_settings_if_conv_t default_info = { - 0, /* doesn't matter for Mux */ - default_allow_ifconv -}; +DEBUG_ONLY(static firm_dbg_module_t *dbg;) /** * Returns non-zero if a Block can be emptied. * * @param block the block */ -static int can_empty_block(ir_node *block) { +static bool can_empty_block(ir_node *block) +{ return get_Block_mark(block) == 0; } @@ -207,69 +174,64 @@ static void rewire(ir_node* node, int i, int j, ir_node* new_pred) /** - * Remove the j-th predecessors from the i-th predecessor of block and add it to block + * Remove the j-th predecessor from the i-th predecessor of block and add it to block */ static void split_block(ir_node* block, int i, int j) { - ir_node* pred_block = get_nodes_block(get_irn_n(block, i)); - int arity = get_irn_arity(block); - int new_pred_arity; - ir_node *phi, *next; - ir_node **ins; + ir_node *pred_block = get_nodes_block(get_Block_cfgpred(block, i)); + int arity = get_Block_n_cfgpreds(block); + ir_node **ins = ALLOCAN(ir_node*, arity + 1); + int new_pred_arity; + ir_node *phi; + ir_node *next; ir_node **pred_ins; - int k; + int k; DB((dbg, LEVEL_1, "Splitting predecessor %d of predecessor %d of %+F\n", j, i, block)); - NEW_ARR_A(ir_node*, ins, arity + 1); - for (phi = get_Block_phis(block); phi != NULL; phi = get_Phi_next(phi)) { ir_node* copy = copy_to(get_irn_n(phi, i), pred_block, j); for (k = 0; k < i; ++k) ins[k] = get_irn_n(phi, k); ins[k++] = copy; for (; k < arity; ++k) ins[k] = get_irn_n(phi, k); - ins[k] = get_irn_n(phi, i); - assert(k == arity); - set_irn_in(phi, arity + 1, ins); + ins[k++] = get_irn_n(phi, i); + set_irn_in(phi, k, ins); } - for (k = 0; k < i; ++k) ins[k] = get_irn_n(block, k); + for (k = 0; k < i; ++k) ins[k] = get_Block_cfgpred(block, k); ins[k++] = get_irn_n(pred_block, j); - for (; k < arity; ++k) ins[k] = get_irn_n(block, k); - ins[k] = get_irn_n(block, i); - assert(k == arity); - set_irn_in(block, arity + 1, ins); + for (; k < arity; ++k) ins[k] = get_Block_cfgpred(block, k); + ins[k++] = get_Block_cfgpred(block, i); + set_irn_in(block, k, ins); new_pred_arity = get_irn_arity(pred_block) - 1; - NEW_ARR_A(ir_node*, pred_ins, new_pred_arity); + pred_ins = ALLOCAN(ir_node*, new_pred_arity); for (phi = get_Block_phis(pred_block); phi != NULL; phi = next) { - for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(phi, k); - for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(phi, k + 1); - assert(k == new_pred_arity); next = get_Phi_next(phi); - if (new_pred_arity > 1) { - set_irn_in(phi, new_pred_arity, pred_ins); - } else { + for (k = 0; k != j; ++k) pred_ins[k] = get_irn_n(phi, k); + for (; k != new_pred_arity; ++k) pred_ins[k] = get_irn_n(phi, k + 1); + if (k == 1) { exchange(phi, pred_ins[0]); + } else { + set_irn_in(phi, k, pred_ins); } } - for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(pred_block, k); - for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(pred_block, k + 1); - assert(k == new_pred_arity); - if (new_pred_arity > 1) { - set_irn_in(pred_block, new_pred_arity, pred_ins); - } else { + for (k = 0; k != j; ++k) pred_ins[k] = get_irn_n(pred_block, k); + for (; k != new_pred_arity; ++k) pred_ins[k] = get_irn_n(pred_block, k + 1); + if (k == 1) { exchange(pred_block, get_nodes_block(pred_ins[0])); + } else { + set_irn_in(pred_block, k, pred_ins); } } static void prepare_path(ir_node* block, int i, const ir_node* dependency) { - ir_node* pred = get_nodes_block(get_irn_n(block, i)); + ir_node* pred = get_nodes_block(get_Block_cfgpred(block, i)); int pred_arity; int j; @@ -279,7 +241,7 @@ static void prepare_path(ir_node* block, int i, const ir_node* dependency) for (j = 0; j < pred_arity; ++j) { ir_node* pred_pred = get_nodes_block(get_irn_n(pred, j)); - if (is_cdep_on(pred_pred, dependency)) { + if (pred_pred != dependency && is_cdep_on(pred_pred, dependency)) { prepare_path(pred, j, dependency); split_block(block, i, j); break; @@ -292,7 +254,7 @@ static void prepare_path(ir_node* block, int i, const ir_node* dependency) */ static void if_conv_walker(ir_node *block, void *ctx) { - walker_env *env = ctx; + walker_env *env = (walker_env*)ctx; int arity; int i; @@ -306,8 +268,10 @@ restart: ir_cdep* cdep; pred0 = get_Block_cfgpred_block(block, i); - for (cdep = find_cdep(pred0); cdep != NULL; cdep = cdep->next) { - const ir_node* dependency = cdep->node; + if (pred0 == block) continue; + + for (cdep = find_cdep(pred0); cdep != NULL; cdep = get_cdep_next(cdep)) { + const ir_node* dependency = get_cdep_node(cdep); ir_node* projx0 = walk_to_projx(pred0, dependency); ir_node* cond; int j; @@ -318,18 +282,19 @@ restart: if (! is_Cond(cond)) continue; - /* We only handle boolean decisions, no switches */ - if (get_irn_mode(get_Cond_selector(cond)) != mode_b) continue; - for (j = i + 1; j < arity; ++j) { ir_node* projx1; ir_node* sel; ir_node* mux_block; ir_node* phi; + ir_node* p; ir_node* pred1; + bool supported; + bool negated; dbg_info* cond_dbg; pred1 = get_Block_cfgpred_block(block, j); + if (pred1 == block) continue; if (!is_cdep_on(pred1, dependency)) continue; @@ -337,24 +302,45 @@ restart: if (projx1 == NULL) continue; + sel = get_Cond_selector(cond); phi = get_Block_phis(block); - if (!env->params->allow_ifconv(get_Cond_selector(cond), phi, i, j)) + supported = true; + negated = get_Proj_proj(projx0) == pn_Cond_false; + for (p = phi; p != NULL; p = get_Phi_next(p)) { + ir_node *mux_false; + ir_node *mux_true; + if (negated) { + mux_true = get_Phi_pred(p, j); + mux_false = get_Phi_pred(p, i); + } else { + mux_true = get_Phi_pred(p, i); + mux_false = get_Phi_pred(p, j); + } + if (mux_true == mux_false) + continue; + ir_mode *mode = get_irn_mode(mux_true); + if (mode == mode_M + || !env->allow_ifconv(sel, mux_false, mux_true)) { + supported = false; + break; + } + } + if (!supported) continue; DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n", cond, projx0, projx1 )); - env->changed = 1; + /* remove critical edges */ + env->changed = true; prepare_path(block, i, dependency); prepare_path(block, j, dependency); arity = get_irn_arity(block); - sel = get_Cond_selector(cond); - mux_block = get_nodes_block(cond); cond_dbg = get_irn_dbg_info(cond); - do { + do { /* generate Mux nodes in mux_block for Phis in block */ ir_node* val_i = get_irn_n(phi, i); ir_node* val_j = get_irn_n(phi, j); ir_node* mux; @@ -370,12 +356,12 @@ restart: * one block, but not at the same memory node */ assert(get_irn_mode(phi) != mode_M); - if (get_Proj_proj(projx0) == pn_Cond_true) { - t = val_i; - f = val_j; - } else { + if (negated) { t = val_j; f = val_i; + } else { + t = val_i; + f = val_j; } mux = new_rd_Mux(cond_dbg, mux_block, sel, f, t, get_irn_mode(phi)); @@ -392,29 +378,17 @@ restart: phi = next_phi; } while (phi != NULL); - exchange(get_nodes_block(get_irn_n(block, i)), mux_block); - exchange(get_nodes_block(get_irn_n(block, j)), mux_block); + /* move mux operands into mux_block */ + exchange(get_nodes_block(get_Block_cfgpred(block, i)), mux_block); + exchange(get_nodes_block(get_Block_cfgpred(block, j)), mux_block); if (arity == 2) { unsigned mark; -#if 1 - DB((dbg, LEVEL_1, "Welding block %+F and %+F\n", block, mux_block)); - /* copy the block-info from the Mux-block to the block before merging */ - - mark = get_Block_mark(mux_block) | get_Block_mark(block); - set_Block_mark(block, mark); - set_Block_phis(block, get_Block_phis(mux_block)); - - set_irn_in(block, get_irn_arity(mux_block), get_irn_in(mux_block) + 1); - exchange_cdep(mux_block, block); - exchange(mux_block, block); -#else DB((dbg, LEVEL_1, "Welding block %+F to %+F\n", block, mux_block)); mark = get_Block_mark(mux_block) | get_Block_mark(block); /* mark both block just to be sure, should be enough to mark mux_block */ set_Block_mark(mux_block, mark); exchange(block, mux_block); -#endif return; } else { rewire(block, i, j, new_r_Jmp(mux_block)); @@ -440,7 +414,8 @@ static void init_block_link(ir_node *block, void *env) * Daisy-chain all Phis in a block. * If a non-movable node is encountered set the has_pinned flag in its block. */ -static void collect_phis(ir_node *node, void *env) { +static void collect_phis(ir_node *node, void *env) +{ (void) env; if (is_Phi(node)) { @@ -448,7 +423,7 @@ static void collect_phis(ir_node *node, void *env) { add_Block_phi(block, node); } else { - if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) { + if (!is_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) { /* * Ignore control flow nodes (except Raise), these will be removed. */ @@ -462,21 +437,25 @@ static void collect_phis(ir_node *node, void *env) { } } -void opt_if_conv(ir_graph *irg, const ir_settings_if_conv_t *params) +void opt_if_conv(ir_graph *irg) { - walker_env env; + walker_env env; + const backend_params *be_params = be_get_backend_param(); + + assure_irg_properties(irg, + IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES + | IR_GRAPH_PROPERTY_NO_UNREACHABLE_CODE + | IR_GRAPH_PROPERTY_NO_BADS + | IR_GRAPH_PROPERTY_ONE_RETURN); /* get the parameters */ - env.params = (params != NULL ? params : &default_info); - env.changed = 0; + env.allow_ifconv = be_params->allow_ifconv; + env.changed = false; FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv"); DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg)); - normalize_one_return(irg); - remove_critical_cf_edges(irg); - compute_cdep(irg); ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_PHI_LIST); @@ -489,46 +468,16 @@ void opt_if_conv(ir_graph *irg, const ir_settings_if_conv_t *params) if (env.changed) { local_optimize_graph(irg); - - /* graph has changed, invalidate analysis info */ - set_irg_outs_inconsistent(irg); - set_irg_extblk_inconsistent(irg); - set_irg_loopinfo_inconsistent(irg); - set_irg_doms_inconsistent(irg); } free_cdep(irg); -} -struct pass_t { - ir_graph_pass_t pass; - const ir_settings_if_conv_t *params; -}; + confirm_irg_properties(irg, + IR_GRAPH_PROPERTY_NO_CRITICAL_EDGES + | IR_GRAPH_PROPERTY_ONE_RETURN); +} -/** - * Wrapper for running opt_if_conv() as an ir_graph pass. - */ -static int pass_wrapper(ir_graph *irg, void *context) { - struct pass_t *pass = context; - opt_if_conv(irg, pass->params); - return 0; -} /* pass_wrapper */ - -ir_graph_pass_t *opt_if_conv_pass( - const char *name, int verify, int dump, const ir_settings_if_conv_t *params) +ir_graph_pass_t *opt_if_conv_pass(const char *name) { - struct pass_t *pass = xmalloc(sizeof(*pass)); - - pass->pass.kind = k_ir_prog_pass; - pass->pass.run_on_irg = pass_wrapper; - pass->pass.context = pass; - pass->pass.name = name; - pass->pass.verify = verify != 0; - pass->pass.dump = dump != 0; - - pass->params = params; - - INIT_LIST_HEAD(&pass->pass.list); - - return &pass->pass; + return def_graph_pass(name ? name : "ifconv", opt_if_conv); }