/*
- * 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 <assert.h>
+#include <stdbool.h>
+
#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"
#include "irtools.h"
#include "array_t.h"
#include "irpass_t.h"
+#include "be.h"
-// debug
#include "irdump.h"
#include "debug.h"
* 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;
}
/**
- * 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;
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;
*/
static void if_conv_walker(ir_node *block, void *ctx)
{
- walker_env *env = ctx;
+ walker_env *env = (walker_env*)ctx;
int arity;
int i;
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;
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;
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;
* 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));
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));
* 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)) {
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.
*/
}
}
-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);
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);
}
projects / libfirm / blobdiff