-/**
- * If conversion.
- * Make Mux nodes from Conds where it its possible.
- * @author Sebastian Hack
- * @date 4.2.2005
- * $Id$
+/*
+ * Project: libFIRM
+ * File name: ir/opt/ifconv.c
+ * Purpose: If conversion
+ * Author: Sebastian Hack.
+ * Created:
+ * CVS-ID: $Id$
+ * Copyright: (c) 1998-2005 Universität Karlsruhe
+ * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
*/
-#include <stdlib.h>
-#include <string.h>
+#if 1
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+#ifdef HAVE_MALLOC_H
+#include <malloc.h>
+#endif
+#ifdef HAVE_ALLOCA_H
#include <alloca.h>
+#endif
-#include "irgraph_t.h"
+#include <assert.h>
+
+#include "obst.h"
#include "irnode_t.h"
-#include "iropt_t.h"
+#include "cdep.h"
+#include "ircons.h"
+#include "ifconv.h"
+#include "irdom.h"
#include "irgmod.h"
-#include "irmode_t.h"
-#include "ircons_t.h"
-#include "irdom_t.h"
+#include "irgopt.h"
+#include "irgwalk.h"
+#include "irtools.h"
+#include "return.h"
+#include "array.h"
+
+// debug
+#include "irdump.h"
+#include "debug.h"
-#include "ifconv.h"
-#include "irflag_t.h"
+DEBUG_ONLY(firm_dbg_module_t *dbg);
-#include "irprintf.h"
-#include "debug.h"
-#include "obst.h"
-#include "set.h"
-#include "bitset.h"
-#include "bitfiddle.h"
-#define MAX_DEPTH 20
+/**
+ * Additional block info.
+ */
+typedef struct block_info {
+ ir_node *phi; /**< head of the Phi list */
+ int has_pinned; /**< set if the block contains instructions that cannot be moved */
+} block_info;
-/*
- * Mux optimization routines.
+#define get_block_blockinfo(block) ((block_info *)get_irn_link(block))
+
+/**
+ * Returns non-zero if a Block can be emptied.
*/
+static int can_empty_block(ir_node *block)
+{
+ return !get_block_blockinfo(block)->has_pinned;
+}
-#if 0
-static ir_node *local_optimize_mux(ir_node *mux)
-{
- int i, n;
- ir_node *res = mux;
- ir_node *sel = get_Mux_sel(mux);
- ir_node *cmp = skip_Proj(sel);
-
- /* Optimize the children */
- for(i = 1, n = get_irn_arity(mux); i < n; ++i) {
- ir_node *operand = get_irn_n(mux, i);
- if(get_irn_op(operand) == op_Mux)
- optimize_mux(operand);
+
+static ir_node* walk_to_projx(ir_node* start, const ir_node* dependency)
+{
+ int arity;
+ int i;
+
+ /* No need to find the conditional block if this block cannot be emptied and
+ * therefore not moved
+ */
+ if (!can_empty_block(start)) return NULL;
+
+ arity = get_irn_arity(start);
+ for (i = 0; i < arity; ++i) {
+ ir_node* pred = get_irn_n(start, i);
+ ir_node* pred_block = get_nodes_block(pred);
+
+ if (pred_block == dependency) {
+ assert(is_Proj(pred));
+ assert(get_irn_mode(pred) == mode_X);
+ return pred;
+ }
+
+ if (is_Proj(pred)) {
+ assert(get_irn_mode(pred) == mode_X);
+ return NULL;
+ }
+
+ if (is_cdep_on(pred_block, dependency)) {
+ return walk_to_projx(pred_block, dependency);
+ }
}
+ return NULL;
+}
- /* If we have no cmp above the mux, get out. */
- if(is_Proj(sel) && get_irn_mode(sel) == mode_b && get_irn_opcode(cmp) == iro_Cmp) {
- pn_Cmp cc = get_Proj_proj(sel);
- ir_mode *mode = get_irn_mode(mux);
- ir_node *block = get_nodes_block(n);
- ir_node *cmp_left = get_Cmp_left(cmp);
- ir_node *cmp_right = get_Cmp_right(cmp);
- ir_node *mux_true = get_Mux_true(mux);
- ir_node *mux_false = get_Mux_false(mux);
+/**
+ * Copies the DAG starting at node to the ith predecessor block of src_block
+ * -if the node isn't in the src_block, this is a nop and the node is returned
+ * -if the node is a phi in the src_block, the ith predecessor of the phi is
+ * returned
+ * otherwise returns the copy of the passed node
+ */
+static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
+{
+ ir_node* dst_block;
+ ir_node* copy;
+ int arity;
+ int j;
- /*
- * Check for comparisons with signed integers.
- */
- if(mode_is_int(mode) /* We need an integral mode */
- && mode_is_signed(mode) /* which is signed */
- && cc == Lt) { /* and have to compare for < */
+ if (get_nodes_block(node) != src_block) return node;
+ if (get_irn_op(node) == op_Phi) return get_irn_n(node, i);
+
+ copy = exact_copy(node);
+ dst_block = get_nodes_block(get_irn_n(src_block, i));
+ set_nodes_block(copy, dst_block);
+
+ DB((dbg, LEVEL_1, "Copying node %+F to block %+F, copy is %+F\n",
+ node, dst_block, copy));
+
+ arity = get_irn_arity(node);
+ for (j = 0; j < arity; ++j) {
+ set_irn_n(copy, j, copy_to(get_irn_n(node, j), src_block, i));
+ DB((dbg, LEVEL_2, "-- pred %d is %+F\n", j, get_irn_n(copy, j)));
+ }
+ return copy;
+}
+
+
+/**
+ * Remove predecessors i and j from node and add predecessor new_pred
+ */
+static void rewire(ir_node* node, int i, int j, ir_node* new_pred)
+{
+ int arity = get_irn_arity(node);
+ ir_node **ins;
+ int k;
+ int l;
+
+ NEW_ARR_A(ir_node *, ins, arity - 1);
+
+ l = 0;
+ for (k = 0; k < i; ++k) ins[l++] = get_irn_n(node, k);
+ for (++k; k < j; ++k) ins[l++] = get_irn_n(node, k);
+ for (++k; k < arity; ++k) ins[l++] = get_irn_n(node, k);
+ ins[l++] = new_pred;
+ assert(l == arity - 1);
+ set_irn_in(node, l, ins);
+}
- /*
- * Mux(x:T < 0, -1, 0) -> Shrs(x, sizeof_bits(T) - 1)
- * Conditions:
- * T must be signed.
- */
- if(classify_Const(cmp_right) == CNST_NULL
- && classify_Const(mux_true) == CNST_ALL_ONE
- && classify_Const(mux_false) == CNST_NULL) {
- ir_mode *u_mode = find_unsigned_mode(mode);
+/**
+ * Remove the jth predecessors from the ith 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;
+ ir_node **ins;
+ ir_node **pred_ins;
+ 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_blockinfo(block)->phi; phi != NULL; phi = get_irn_link(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);
+ }
+
+ for (k = 0; k < i; ++k) ins[k] = get_irn_n(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);
+
+ new_pred_arity = get_irn_arity(pred_block) - 1;
+ NEW_ARR_A(ir_node*, pred_ins, new_pred_arity);
+
+ for (phi = get_block_blockinfo(pred_block)->phi; phi != NULL; phi = get_irn_link(phi)) {
+ 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);
+ if (new_pred_arity > 1) {
+ set_irn_in(phi, new_pred_arity, pred_ins);
+ } else {
+ exchange(phi, pred_ins[0]);
+ }
+ }
+
+ 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 {
+ exchange(pred_block, get_nodes_block(pred_ins[0]));
+ }
+}
+
- res = new_r_Shrs(current_ir_graph, block, cmp_left,
- new_r_Const_long(current_ir_graph, block, u_mode,
- get_mode_size_bits(mode) - 1),
- mode);
+static void prepare_path(ir_node* block, int i, const ir_node* dependency)
+{
+ ir_node* pred = get_nodes_block(get_irn_n(block, i));
+ int pred_arity;
+ int j;
+
+ DB((dbg, LEVEL_1, "Preparing predecessor %d of %+F\n", i, block));
+
+ pred_arity = get_irn_arity(pred);
+ 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)) {
+ prepare_path(pred, j, dependency);
+ split_block(block, i, j);
+ break;
+ }
+ }
+}
+
+
+static void if_conv_walker(ir_node* block, void* env)
+{
+ int arity;
+ int i;
+
+ /* Bail out, if there are no Phis at all */
+ if (get_block_blockinfo(block)->phi == NULL) return;
+
+restart:
+ arity = get_irn_arity(block);
+ for (i = 0; i < arity; ++i) {
+ ir_node* pred;
+ cdep* cdep;
+
+ pred = get_nodes_block(get_irn_n(block, i));
+ for (cdep = find_cdep(pred); cdep != NULL; cdep = cdep->next) {
+ const ir_node* dependency = cdep->node;
+ ir_node* projx0 = walk_to_projx(pred, dependency);
+ ir_node* cond;
+ int j;
+
+ if (projx0 == NULL) continue;
+
+ cond = get_Proj_pred(projx0);
+ if (get_irn_op(cond) != op_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* conds[1];
+ ir_node* vals[2];
+ ir_node* psi;
+ ir_node* psi_block;
+ ir_node* phi;
+
+ pred = get_nodes_block(get_irn_n(block, j));
+
+ if (!is_cdep_on(pred, dependency)) continue;
+
+ projx1 = walk_to_projx(pred, dependency);
+
+ if (projx1 == NULL) continue;
+
+ DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n",
+ cond, projx0, projx1
+ ));
+
+ prepare_path(block, i, dependency);
+ prepare_path(block, j, dependency);
+ arity = get_irn_arity(block);
+
+ conds[0] = get_Cond_selector(cond);
+
+ psi_block = get_nodes_block(cond);
+ phi = get_block_blockinfo(block)->phi;
+ do {
+ ir_node* val_i = get_irn_n(phi, i);
+ ir_node* val_j = get_irn_n(phi, j);
+
+ if (val_i == val_j) {
+ psi = val_i;
+ DB((dbg, LEVEL_2, "Generating no psi, because both values are equal\n"));
+ } else {
+ /* Something is very fishy if two predecessors of a PhiM point into
+ * one block, but not at the same memory node
+ */
+ assert(get_irn_mode(phi) != mode_M);
+ if (get_Proj_proj(projx0) == pn_Cond_true) {
+ vals[0] = val_i;
+ vals[1] = val_j;
+ } else {
+ vals[0] = val_j;
+ vals[1] = val_i;
+ }
+ psi = new_r_Psi(
+ current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
+ );
+ DB((dbg, LEVEL_2, "Generating %+F for %+F\n", psi, phi));
+ }
+
+ if (arity == 2) {
+ exchange(phi, psi);
+ } else {
+ rewire(phi, i, j, psi);
+ }
+
+ phi = get_irn_link(phi);
+ } while (phi != NULL);
+
+ exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
+ exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
+
+ if (arity == 2) {
+#if 1
+ DB((dbg, LEVEL_1, "Welding block %+F and %+F\n", block, psi_block));
+ get_block_blockinfo(block)->has_pinned |= get_block_blockinfo(psi_block)->has_pinned;
+ set_irn_in(block, get_irn_arity(psi_block), get_irn_in(psi_block) + 1);
+ exchange_cdep(psi_block, block);
+ exchange(psi_block, block);
+#else
+ DB((dbg, LEVEL_1, "Welding block %+F to %+F\n", block, psi_block));
+ get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
+ exchange(block, psi_block);
+#endif
+ return;
+ } else {
+ rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block));
+ goto restart;
+ }
}
+ }
+ }
+}
+
+/**
+ * Block walker: add additional data
+ */
+static void init_block_link(ir_node *block, void *env)
+{
+ struct obstack *obst = env;
+ block_info *bi = obstack_alloc(obst, sizeof(*bi));
+ bi->phi = NULL;
+ bi->has_pinned = 0;
+ set_irn_link(block, bi);
+}
+
+
+/**
+ * Daisy-chain all phis in a block
+ * If a non-movable node is encountered set the has_pinned flag
+ */
+static void collect_phis(ir_node *node, void *env)
+{
+ if (is_Phi(node)) {
+ ir_node *block = get_nodes_block(node);
+ block_info *bi = get_block_blockinfo(block);
+
+ set_irn_link(node, bi->phi);
+ bi->phi = node;
+ }
+ else {
+ if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
/*
- * Mux(0 < x:T, 1, 0) -> Shr(-x, sizeof_bits(T) - 1)
- * Conditions:
- * T must be signed.
+ * Ignore control flow nodes, these will be removed.
+ * This ignores Raise. That is surely bad. FIXME.
*/
- else if(classify_Const(cmp_left) == CNST_NULL
- && classify_Const(mux_true) == CNST_ONE
- && classify_Const(mux_false) == CNST_NULL) {
+ if (! is_cfop(node)) {
+ ir_node *block = get_nodes_block(node);
+ block_info *bi = get_block_blockinfo(block);
- ir_mode *u_mode = find_unsigned_mode(mode);
+ DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
+ bi->has_pinned = 1;
+ }
+ }
+ }
+}
- res = new_r_Shr(current_ir_graph, block,
- /* -x goes to 0 - x in Firm (cmp_left is 0, see the if) */
- new_r_Sub(current_ir_graph, block, cmp_left, cmp_right, mode),
+/*
+ * Transform multiple cascaded Psis into one Psi
+ */
+static ir_node* fold_psi(ir_node* psi)
+{
+ int arity = get_Psi_n_conds(psi);
+ int new_arity = 0;
+ int i;
+ ir_node* n;
+ ir_node** conds;
+ ir_node** vals;
+ int j;
+ int k;
+ int a;
+ ir_node* new_psi;
+
+ for (i = 0; i < arity; ++i) {
+ n = get_Psi_val(psi, i);
+ if (get_irn_op(n) == op_Psi) {
+ new_arity += get_Psi_n_conds(n) + 1;
+ } else {
+ ++new_arity;
+ }
+ }
+ n = get_Psi_default(psi);
+ if (get_irn_op(n) == op_Psi) {
+ new_arity += get_Psi_n_conds(n);
+ }
- /* This is sizeof_bits(T) - 1 */
- new_r_Const_long(current_ir_graph, block, u_mode,
- get_mode_size_bits(mode) - 1),
- mode);
+ if (arity == new_arity) return psi; // no attached Psis found
+ DB((dbg, LEVEL_1, "Folding %+F from %d to %d conds\n", psi, arity, new_arity));
+
+ NEW_ARR_A(ir_node *, conds, new_arity);
+ NEW_ARR_A(ir_node *, vals, new_arity + 1);
+ j = 0;
+ for (i = 0; i < arity; ++i) {
+ ir_node* c = get_Psi_cond(psi, i);
+
+ n = get_Psi_val(psi, i);
+ if (get_irn_op(n) == op_Psi) {
+ a = get_Psi_n_conds(n);
+ for (k = 0; k < a; ++k) {
+ conds[j] = new_r_And(
+ current_ir_graph, get_nodes_block(psi),
+ c, get_Psi_cond(n, k), mode_b
+ );
+ vals[j] = get_Psi_val(n, k);
+ ++j;
}
+ conds[j] = c;
+ vals[j] = get_Psi_default(n);
+ } else {
+ conds[j] = c;
+ vals[j] = n;
+ }
+ ++j;
+ }
+ n = get_Psi_default(psi);
+ if (get_irn_op(n) == op_Psi) {
+ a = get_Psi_n_conds(n);
+ for (k = 0; k < a; ++k) {
+ conds[j] = get_Psi_cond(n, k);
+ vals[j] = get_Psi_val(n, k);
+ ++j;
}
+ vals[j] = get_Psi_default(n);
+ } else {
+ vals[j] = n;
}
+ assert(j == new_arity);
+ new_psi = new_r_Psi(
+ current_ir_graph, get_nodes_block(psi),
+ new_arity, conds, vals, get_irn_mode(psi)
+ );
+ DB((dbg, LEVEL_1, "Folded %+F into new %+F\n", psi, new_psi));
+ exchange(psi, new_psi);
+ return new_psi;
+}
+
+
+/*
+ * Merge consecutive psi inputs if the data inputs are the same
+ */
+static ir_node* meld_psi(ir_node* psi)
+{
+ int arity = get_Psi_n_conds(psi);
+ int new_arity;
+ ir_node** conds;
+ ir_node** vals;
+ ir_node* cond;
+ ir_node* val;
+ int i;
+ int j;
+ ir_node* new_psi;
+
+ new_arity = 1;
+ val = get_Psi_val(psi, 0);
+ DB((dbg, LEVEL_1, "Pred 0 of %+F is %+F\n", psi, val));
+ for (i = 1; i < arity; ++i) {
+ ir_node* v = get_Psi_val(psi, i);
+ DB((dbg, LEVEL_1, "Pred %2d of %+F is %+F\n", i, psi, v));
+ if (val != v) {
+ val = v;
+ ++new_arity;
+ }
+ }
+ DB((dbg, LEVEL_1, "Default of %+F is %+F\n", psi, get_Psi_default(psi)));
+ if (val == get_Psi_default(psi)) --new_arity;
+
+ DB((dbg, LEVEL_1, "Melding Psi %+F from %d conds to %d\n", psi, arity, new_arity));
+
+ if (new_arity == arity) return psi;
- return res;
+ /* If all data inputs of the Psi are equal, exchange the Psi with that value */
+ if (new_arity == 0) {
+ exchange(psi, val);
+ return val;
+ }
+
+ NEW_ARR_A(ir_node *, conds, new_arity);
+ NEW_ARR_A(ir_node *, vals, new_arity + 1);
+ cond = get_Psi_cond(psi, 0);
+ val = get_Psi_val(psi, 0);
+ j = 0;
+ for (i = 1; i < arity; ++i) {
+ ir_node* v = get_Psi_val(psi, i);
+
+ if (v == val) {
+ cond = new_r_Or(
+ current_ir_graph, get_nodes_block(psi),
+ cond, get_Psi_cond(psi, i), mode_b
+ );
+ } else {
+ conds[j] = cond;
+ vals[j] = val;
+ ++j;
+ val = v;
+ }
+ }
+ if (val != get_Psi_default(psi)) {
+ conds[j] = cond;
+ vals[j] = val;
+ ++j;
+ }
+ vals[j] = get_Psi_default(psi);
+ assert(j == new_arity);
+ new_psi = new_r_Psi(
+ current_ir_graph, get_nodes_block(psi),
+ new_arity, conds, vals, get_irn_mode(psi)
+ );
+ DB((dbg, LEVEL_1, "Molded %+F into %+F\n", psi, new_psi));
+ exchange(psi, new_psi);
+ return new_psi;
+}
+
+
+/**
+ * Split a Psi with multiple conditions into multiple Psis with one condtition
+ * each
+ */
+static ir_node* split_psi(ir_node* psi)
+{
+ int arity = get_Psi_n_conds(psi);
+ ir_mode* mode;
+ ir_node* block;
+ ir_node* rval;
+ int i;
+
+ if (arity == 1) return psi;
+
+ mode = get_irn_mode(psi);
+ block = get_nodes_block(psi);
+ rval = get_Psi_default(psi);
+ for (i = arity - 1; i >= 0; --i) {
+ ir_node* conds[1];
+ ir_node* vals[2];
+
+ conds[0] = get_Psi_cond(psi, i);
+ vals[0] = get_Psi_val(psi, i);
+ vals[1] = rval;
+ rval = new_r_Psi(
+ current_ir_graph, block, 1, conds, vals, mode
+ );
+ }
+ exchange(psi, rval);
+ return rval;
}
+
+
+static void optimise_psis(ir_node* node, void* env)
+{
+ if (get_irn_op(node) != op_Psi) return;
+#if 1
+ node = fold_psi(node);
+#endif
+#if 1
+ node = meld_psi(node);
+#endif
+#if 1
+ node = split_psi(node);
+#endif
+}
+
+
+void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
+{
+ struct obstack obst;
+
+ if (!get_opt_if_conversion())
+ return;
+
+ FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
+
+ DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
+
+ dump_ir_block_graph(irg, "_00_pre");
+
+ normalize_one_return(irg);
+ remove_critical_cf_edges(irg);
+
+ dump_ir_block_graph(irg, "_01_normal");
+
+ compute_cdep(irg);
+ assure_doms(irg);
+
+ obstack_init(&obst);
+ irg_block_walk_graph(irg, init_block_link, NULL, &obst);
+ irg_walk_graph(irg, collect_phis, NULL, NULL);
+ irg_block_walk_graph(irg, NULL, if_conv_walker, NULL);
+
+ dump_ir_block_graph(irg, "_02_ifconv");
+ local_optimize_graph(irg);
+ dump_ir_block_graph(irg, "_03_postopt");
+
+ irg_walk_graph(irg, NULL, optimise_psis, NULL);
+
+ dump_ir_block_graph(irg, "_04_postifconv");
+
+ obstack_free(&obst, NULL);
+
+ free_dom(irg);
+ free_cdep(irg);
+}
+
+#else
+
+/**
+ * @file ifconv.c
+ * If conversion.
+ * Make Mux nodes from Conds where it its possible.
+ * @author Sebastian Hack
+ * @date 4.2.2005
+ */
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#ifdef HAVE_STDLIB_H
+#include <stdlib.h>
+#endif
+#ifdef HAVE_STRING_H
+#include <string.h>
+#endif
+#ifdef HAVE_ALLOCA_H
+#include <alloca.h>
#endif
+#include "irgraph_t.h"
+#include "irnode_t.h"
+#include "irgwalk.h"
+#include "iropt_t.h"
+#include "irgmod.h"
+#include "irmode_t.h"
+#include "ircons_t.h"
+#include "irdom_t.h"
+#include "irgwalk.h"
+
+#include "ifconv.h"
+#include "irflag_t.h"
+
+#include "irprintf.h"
+#include "debug.h"
+#include "obst.h"
+#include "set.h"
+#include "bitset.h"
+#include "bitfiddle.h"
+#include "irhooks.h"
+#include "return.h"
+
+#define MAX_DEPTH 4
+
/**
* check, if a node is const and return its tarval or
* return a default tarval.
*/
static tarval *get_value_or(ir_node *cnst, tarval *or)
{
- return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
+ return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
}
*/
static ir_node *optimize_mux_chain(ir_node *mux)
{
- int i;
- ir_node *res;
- ir_node *ops[2];
- ir_mode *mode = get_irn_mode(mux);
- tarval *null;
- tarval *minus_one;
-
- /*
- * If we have no mux, or its mode is not integer, we
- * can return.
- */
- if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
- return mux;
-
- res = mux;
- null = get_tarval_null(mode);
- minus_one = tarval_sub(null, get_tarval_one(mode));
-
- ops[0] = get_Mux_false(mux);
- ops[1] = get_Mux_true(mux);
-
- for(i = 0; i < 2; ++i) {
- ir_node *a, *b, *d;
- tarval *tva, *tvb, *tvd;
- ir_node *child_mux;
-
- /*
- * A mux operand at the first position can be factored
- * out, if the operands fulfill several conditions:
- *
- * mux(c1, mux(c2, a, b), d)
- *
- * This can be made into:
- * 1) mux(c1, 0, d) | mux(c2, a, b)
- * if a | d == d and b | d == d
- *
- * 2) mux(c1, -1, d) & mux(c2, a, b)
- * if a & d == d and a & b == b
- */
- if(get_irn_op(ops[i]) == op_Mux) {
-
- child_mux = ops[i];
- a = get_Mux_false(child_mux);
- b = get_Mux_true(child_mux);
- d = ops[1 - i];
-
- /* Try the or stuff */
- tva = get_value_or(a, minus_one);
- tvb = get_value_or(b, minus_one);
- tvd = get_value_or(d, null);
-
- if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
- && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
-
- ops[i] = new_Const(mode, null);
- res = new_r_Or(current_ir_graph, get_nodes_block(mux),
- mux, child_mux, mode);
- break;
- }
-
- /* If the or didn't go, try the and stuff */
- tva = get_value_or(a, null);
- tvb = get_value_or(b, null);
- tvd = get_value_or(d, minus_one);
-
- if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
- && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
-
- ops[i] = new_Const(mode, minus_one);
- res = new_r_And(current_ir_graph, get_nodes_block(mux),
- mux, child_mux, mode);
- break;
- }
- }
- }
-
- /* recursively optimize nested muxes. */
- set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
- set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
-
- return res;
+ int i;
+ ir_node *res;
+ ir_node *ops[2];
+ ir_mode *mode = get_irn_mode(mux);
+ tarval *null;
+ tarval *minus_one;
+
+ /*
+ * If we have no mux, or its mode is not integer, we
+ * can return.
+ */
+ if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
+ return mux;
+
+ res = mux;
+ null = get_mode_null(mode);
+ minus_one = tarval_sub(null, get_tarval_one(mode));
+
+ ops[0] = get_Mux_false(mux);
+ ops[1] = get_Mux_true(mux);
+
+ for(i = 0; i < 2; ++i) {
+ ir_node *a, *b, *d;
+ tarval *tva, *tvb, *tvd;
+ ir_node *child_mux;
+
+ /*
+ * A mux operand at the first position can be factored
+ * out, if the operands fulfill several conditions:
+ *
+ * mux(c1, mux(c2, a, b), d)
+ *
+ * This can be made into:
+ * 1) mux(c1, 0, d) | mux(c2, a, b)
+ * if a | d == d and b | d == d
+ *
+ * 2) mux(c1, -1, d) & mux(c2, a, b)
+ * if a & d == d and a & b == b
+ */
+ if(get_irn_op(ops[i]) == op_Mux) {
+
+ child_mux = ops[i];
+ a = get_Mux_false(child_mux);
+ b = get_Mux_true(child_mux);
+ d = ops[1 - i];
+
+ /* Try the or stuff */
+ tva = get_value_or(a, minus_one);
+ tvb = get_value_or(b, minus_one);
+ tvd = get_value_or(d, null);
+
+ if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
+ && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
+
+ ops[i] = new_Const(mode, null);
+ res = new_r_Or(current_ir_graph, get_nodes_block(mux),
+ mux, child_mux, mode);
+ break;
+ }
+
+ /* If the or didn't go, try the and stuff */
+ tva = get_value_or(a, null);
+ tvb = get_value_or(b, null);
+ tvd = get_value_or(d, minus_one);
+
+ if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
+ && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
+
+ ops[i] = new_Const(mode, minus_one);
+ res = new_r_And(current_ir_graph, get_nodes_block(mux),
+ mux, child_mux, mode);
+ break;
+ }
+ }
+ }
+
+ /* recursively optimize nested muxes. */
+ set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
+ set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
+
+ return res;
}
* The If conversion itself.
***********************************************************/
+/** allow every Mux to be created. */
+static int default_allow_mux(ir_node *sel, ir_node *false_res, ir_node *true_res) {
+ return 1;
+}
+
/**
* Default options.
*/
-static opt_if_conv_info_t default_info = {
- MAX_DEPTH
+static const opt_if_conv_info_t default_info = {
+ MAX_DEPTH,
+ default_allow_mux
};
/** The debugging module. */
-static firm_dbg_module_t *dbg;
+DEBUG_ONLY(static firm_dbg_module_t *dbg;)
/**
- * A simple check for sde effects upton an opcode of a ir node.
+ * A simple check for side effects upto an opcode of a ir node.
* @param irn The ir node to check,
* @return 1 if the opcode itself may produce side effects, 0 if not.
*/
static INLINE int has_side_effects(const ir_node *irn)
{
- opcode opc = get_irn_opcode(irn);
+ ir_op *op = get_irn_op(irn);
- if(opc == iro_Cmp)
- return 0;
+ if (op == op_Cmp)
+ return 0;
- return !mode_is_datab(get_irn_mode(irn));
+ return !mode_is_datab(get_irn_mode(irn));
}
/**
- * Decdies, if a given expression and its subexpressions
+ * Possible failure reasons
+ */
+enum failure_reason_t {
+ SUCCESS = IF_RESULT_SUCCESS,
+ TO_DEEP = IF_RESULT_TOO_DEEP,
+ SIDE_EFFECTS = IF_RESULT_SIDE_EFFECT,
+ PHI_FOUND = IF_RESULT_SIDE_EFFECT_PHI,
+ DENIED = IF_RESULT_DENIED
+};
+
+/**
+ * Decides, if a given expression and its subexpressions
* (to certain, also given extent) can be moved to a block.
- * @param expr The expression to examine.
- * @param block The block where the expression should go.
- * @param depth The current depth, passed recursively. Use 0 for
- * non-recursive calls.
- * @param max_depth The maximum depth to which the expression should be
+ *
+ * @param expr The expression to examine.
+ * @param block The block where the expression should go.
+ * @param depth The current depth, passed recursively. Use 0 for
+ * non-recursive calls.
+ * @param info The options for createing Mux nodes.
* examined.
+ *
+ * @return a failure reason
*/
-static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, int max_depth)
+static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, const opt_if_conv_info_t *info)
{
- int i, n;
- int res = 1;
- ir_node *expr_block = get_nodes_block(expr);
-
-
- /*
- * If we are forced to look too deep into the expression,
- * treat it like it could not be moved.
- */
- if(depth >= max_depth) {
- res = 0;
- goto end;
- }
-
- /*
- * If the block of the expression dominates the specified
- * destination block, it does not matter if the expression
- * has side effects or anything else. It is executed on each
- * path the destination block is reached.
- */
- if(block_dominates(expr_block, dest_block))
- goto end;
-
- /*
- * We cannot move phis!
- */
- if(is_Phi(expr)) {
- res = 0;
- goto end;
- }
-
- /*
- * This should be superflous and could be converted into a assertion.
- * The destination block _must_ dominate the block of the expression,
- * else the expression could be used without its definition.
- */
- if(!block_dominates(dest_block, expr_block)) {
- res = 0;
- goto end;
- }
-
- /*
- * Surely, if the expression does not have a data mode, it is not
- * movable. Perhaps onw should also test the floating property of
- * the opcode/node.
- */
- if(has_side_effects(expr)) {
- res = 0;
- goto end;
- }
-
- /*
- * If the node looks alright so far, look at its operands and
- * check them out. If one of them cannot be moved, this one
- * cannot be moved either.
- */
- for(i = 0, n = get_irn_arity(expr); i < n; ++i) {
- ir_node *op = get_irn_n(expr, i);
- int new_depth = is_Proj(op) ? depth : depth + 1;
- if(!_can_move_to(op, dest_block, new_depth, max_depth)) {
- res = 0;
- goto end;
- }
- }
+ int i, n;
+ int res = SUCCESS;
+ ir_node *expr_block = get_nodes_block(expr);
+
+ /*
+ * If we are forced to look too deep into the expression,
+ * treat it like it could not be moved.
+ */
+ if(depth >= info->max_depth) {
+ res = TO_DEEP;
+ goto end;
+ }
+
+ /*
+ * If the block of the expression dominates the specified
+ * destination block, it does not matter if the expression
+ * has side effects or anything else. It is executed on each
+ * path the destination block is reached.
+ */
+ if (block_dominates(expr_block, dest_block))
+ goto end;
+
+ /*
+ * We cannot move phis!
+ */
+ if (is_Phi(expr)) {
+ res = PHI_FOUND;
+ goto end;
+ }
+
+ /*
+ * This should be superfluous and could be converted into a assertion.
+ * The destination block _must_ dominate the block of the expression,
+ * else the expression could be used without its definition.
+ */
+ if (! block_dominates(dest_block, expr_block)) {
+ res = IF_RESULT_SIDE_EFFECT;
+ goto end;
+ }
+
+ /*
+ * Surely, if the expression does not have a data mode, it is not
+ * movable. Perhaps one should also test the floating property of
+ * the opcode/node.
+ */
+ if (has_side_effects(expr)) {
+ res = IF_RESULT_SIDE_EFFECT;
+ goto end;
+ }
+
+ /*
+ * If the node looks alright so far, look at its operands and
+ * check them out. If one of them cannot be moved, this one
+ * cannot be moved either.
+ */
+ for (i = 0, n = get_irn_arity(expr); i < n; ++i) {
+ ir_node *op = get_irn_n(expr, i);
+ int new_depth = is_Proj(op) ? depth : depth + 1;
+
+ res = _can_move_to(op, dest_block, new_depth, info);
+
+ if (res != SUCCESS)
+ goto end;
+ }
end:
- DBG((dbg, LEVEL_3, "\t\t\t%Dcan move to %n: %d\n", depth, expr, res));
+ DBG((dbg, LEVEL_3, "\t\t\tcan move to %n: %d\n", expr, res));
- return res;
+ return res;
}
/**
* deeper into an expression than a given threshold to examine if
* it can be moved, the expression is rejected and the test returns
* false.
- * @param expr The expression to check for.
+ *
+ * @param expr The expression to check for.
* @param dest_block The destination block you want @p expr to be.
- * @param max_depth The maximum depth @p expr should be investigated.
- * @return 1, if the expression can be moved to the destination block,
- * 0 if not.
+ * @param info The options for createing Mux nodes.
+ *
+ * @return return a failure reason
*/
-static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, int max_depth)
+static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, const opt_if_conv_info_t *info)
{
- return _can_move_to(expr, dest_block, 0, max_depth);
+ return _can_move_to(expr, dest_block, 0, info);
}
+/**
+ * move a DAG given by a root node expr into a new block
+ *
+ * @param expr the root of a dag
+ * @param dest_block the destination block
+ */
static void move_to(ir_node *expr, ir_node *dest_block)
{
- int i, n;
- ir_node *expr_block = get_nodes_block(expr);
+ int i, n;
+ ir_node *expr_block = get_nodes_block(expr);
- /*
- * If we reached the dominator, we are done.
- * We will never put code through the dominator
- */
- if(block_dominates(expr_block, dest_block))
- return;
+ /*
+ * If we reached the dominator, we are done.
+ * We will never put code through the dominator
+ */
+ if (block_dominates(expr_block, dest_block))
+ return;
- for(i = 0, n = get_irn_arity(expr); i < n; ++i)
- move_to(get_irn_n(expr, i), dest_block);
+ for (i = 0, n = get_irn_arity(expr); i < n; ++i)
+ move_to(get_irn_n(expr, i), dest_block);
- set_nodes_block(expr, dest_block);
+ set_nodes_block(expr, dest_block);
}
+/**
+ * return the common dominator of two blocks
+ */
static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2)
{
- if(block_dominates(b1, b2))
- return b1;
- else if(block_dominates(b2, b1))
- return b2;
- else {
- ir_node *p;
-
- for(p = b1; !block_dominates(p, b2); p = get_Block_idom(p));
- return p;
- }
+ if(block_dominates(b1, b2))
+ return b1;
+ else if(block_dominates(b2, b1))
+ return b2;
+ else {
+ ir_node *p;
+
+ for (p = get_Block_idom(b1); !block_dominates(p, b2); p = get_Block_idom(p));
+ return p;
+ }
}
-
/**
* Information about a cond node.
*/
typedef struct _cond_t {
- ir_node *cond; /**< The cond node. */
- struct list_head list; /**< List head which is used for queueing this cond
- into the cond bunch it belongs to. */
- unsigned is_new : 1;
- unsigned totally_covers : 1;
- struct _cond_t *link;
- long visited_nr;
-
- /**
- * Information about the both 'branches'
- * (true and false), the cond creates.
- */
- struct {
- int pos; /**< Number of the predecessor of the
- phi block by which this branch is
- reached. It is -1, if this branch is
- only reached through another cond. */
-
- struct _cond_t *masked_by; /**< If this cond's branch is only reached
- through another cond, we store this
- cond ir_node here. */
- } cases[2];
+ ir_node *cond; /**< The cond node. */
+ struct list_head list; /**< List head which is used for queuing this cond
+ into the cond bunch it belongs to. */
+ unsigned is_new : 1;
+ unsigned totally_covers : 1;
+ struct _cond_t *link;
+ long visited_nr;
+
+ /**
+ * Information about the both 'branches'
+ * (true and false), the cond creates.
+ */
+ struct {
+ int pos; /**< Number of the predecessor of the
+ phi block by which this branch is
+ reached. It is -1, if this branch is
+ only reached through another cond. */
+
+ struct _cond_t *masked_by; /**< If this cond's branch is only reached
+ through another cond, we store this
+ cond ir_node here. */
+ } cases[2];
} cond_t;
+/**
+ * retrieve the conditional information from a Cond node
+ */
static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
{
- cond_t templ;
+ cond_t templ;
- templ.cond = irn;
- return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
+ templ.cond = irn;
+ return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
}
typedef void (cond_walker_t)(cond_t *cond, void *env);
static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
- long visited_nr, void *env)
+ long visited_nr, void *env)
{
- int i;
+ int i;
- if(cond->visited_nr >= visited_nr)
- return;
+ if(cond->visited_nr >= visited_nr)
+ return;
- cond->visited_nr = visited_nr;
+ cond->visited_nr = visited_nr;
- if(pre)
- pre(cond, env);
+ if(pre)
+ pre(cond, env);
- for(i = 0; i < 2; ++i) {
- cond_t *c = cond->cases[i].masked_by;
+ for(i = 0; i < 2; ++i) {
+ cond_t *c = cond->cases[i].masked_by;
- if(c)
- _walk_conds(c, pre, post, visited_nr, env);
- }
+ if(c)
+ _walk_conds(c, pre, post, visited_nr, env);
+ }
- if(post)
- post(cond, env);
+ if(post)
+ post(cond, env);
}
static long cond_visited_nr = 0;
static void walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post, void *env)
{
- _walk_conds(cond, pre, post, ++cond_visited_nr, env);
+ _walk_conds(cond, pre, post, ++cond_visited_nr, env);
}
static void link_conds(cond_t *cond, void *env)
{
- cond_t **ptr = (cond_t **) env;
+ cond_t **ptr = (cond_t **) env;
- cond->link = *ptr;
- *ptr = cond;
+ cond->link = *ptr;
+ *ptr = cond;
}
/**
*/
static int cond_cmp(const void *a, const void *b, size_t size)
{
- const cond_t *x = a;
- const cond_t *y = b;
- return x->cond != y->cond;
+ const cond_t *x = a;
+ const cond_t *y = b;
+ return x->cond != y->cond;
}
/**
* blocks in which phis are located.
*/
typedef struct _cond_info_t {
- struct list_head list; /**< Used to list all of these structs per class. */
+ struct list_head list; /**< Used to list all of these structs per class. */
- struct list_head roots; /**< A list of non-depending conds. Two conds are
- independent, if yot can not reach the one from the
- other (all conds in this list have to dominate the
- block this struct is attached to. */
+ struct list_head roots; /**< A list of non-depending Conds. Two Conds are
+ independent, if it's not possible not reach one from the
+ other (all Conds in this list have to dominate the
+ block this struct is attached to). */
- ir_node *first_phi; /**< The first phi node this cond info was made for. */
- set *cond_set; /**< A set of all dominating reachable conds. */
+ ir_node *first_phi; /**< The first phi node this cond info was made for. */
+ set *cond_set; /**< A set of all dominating reachable Conds. */
} cond_info_t;
/**
* @see find_conds.
*/
-static void _find_conds(ir_node *irn, long visited_nr,
- ir_node *dominator, cond_t *masked_by, int pos, int depth, cond_info_t *ci)
+static void _find_conds(ir_node *irn, unsigned long visited_nr,
+ ir_node *dominator, cond_t *masked_by, int pos, int depth, cond_info_t *ci)
{
- ir_node *block;
- int is_modeb_cond = 0;
-
- block = get_nodes_block(irn);
-
- /*
- * Only check this block if it is dominated by the specified
- * dominator or it has not been visited yet.
- */
- if(block_dominates(dominator, block) && get_Block_block_visited(block) < visited_nr) {
- cond_t *res = masked_by;
- int i, n;
-
- /* check, if we're on a ProjX
- *
- * Further, the ProjX/Cond block must dominate the base block
- * (the block with the phi in it), otherwise, the Cond
- * is not affecting the phi so that a mux can be inserted.
- */
- if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
-
- int proj = get_Proj_proj(irn);
- ir_node *cond = get_Proj_pred(irn);
-
- /* true, if the mode is a mode_b cond _NO_ switch cond */
- is_modeb_cond = get_irn_opcode(cond) == iro_Cond
- && get_irn_mode(get_Cond_selector(cond)) == mode_b;
-
- /* Check, if the pred of the proj is a Cond
- * with a Projb as selector.
- */
- if(is_modeb_cond) {
- cond_t c;
-
- memset(&c, 0, sizeof(c));
- c.cond = cond;
- c.is_new = 1;
- c.cases[0].pos = -1;
- c.cases[1].pos = -1;
-
- /* get or insert the cond info into the set. */
- res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
-
- /*
- * If this cond is already masked by the masked_by cond
- * return immediately, since we don't have anything to add.
- */
- if(masked_by && res->cases[proj].masked_by == masked_by)
- return;
-
- if(res->is_new) {
- res->is_new = 0;
- list_add(&res->list, &ci->roots);
- }
-
- /*
- * Set masked by (either NULL or another cond node.
- * If this cond is truly masked by another one, set
- * the position of the actually investigated branch
- * to -1. Since the cond is masked by another one,
- * there could be more ways from the start block
- * to this branch, so we choose -1.
- */
- res->cases[proj].masked_by = masked_by;
-
- if(!masked_by)
- res->cases[proj].pos = pos;
-
- /*
- * Since the masked_by nodes masks a cond, remove it from the
- * root list of the conf trees.
- */
- else {
- assert(res->cases[proj].pos < 0);
- list_del_init(&masked_by->list);
- }
-
- DBG((dbg, LEVEL_2, "%D%n (%s branch) "
- "for pos %d in block %n reached by %n\n",
- depth, cond, proj ? "true" : "false", pos,
- block, masked_by ? masked_by->cond : NULL));
- }
- }
-
- if(get_Block_block_visited(block) < visited_nr) {
-
- set_Block_block_visited(block, visited_nr);
-
- /* Search recursively from this cond. */
- for(i = 0, n = get_irn_arity(block); i < n; ++i) {
- ir_node *pred = get_irn_n(block, i);
-
- /*
- * If the depth is 0 (the first recursion), we set the pos to
- * the current viewed predecessor, else we adopt the position
- * as given by the caller. We also increase the depth for the
- * recursively called functions.
- */
- _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci);
- }
- }
- }
+ ir_node *block;
+ int saw_select_cond = 0;
+
+ block = get_nodes_block(irn);
+
+ /*
+ * Only check this block if it is dominated by the specified
+ * dominator or it has not been visited yet.
+ */
+ if (block_dominates(dominator, block) && get_Block_block_visited(block) < visited_nr) {
+ cond_t *res = masked_by;
+ int i, n;
+
+ /* check, if we're on a ProjX
+ *
+ * Further, the ProjX/Cond block must dominate the base block
+ * (the block with the phi in it), otherwise, the Cond
+ * is not affecting the phi so that a mux can be inserted.
+ */
+ if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
+
+ int proj = get_Proj_proj(irn);
+ ir_node *cond = get_Proj_pred(irn);
+
+ /* true, if the mode is a mode_b cond _NO_ switch cond */
+ int is_modeb_cond = get_irn_opcode(cond) == iro_Cond
+ && get_irn_mode(get_Cond_selector(cond)) == mode_b;
+
+ saw_select_cond = !is_modeb_cond;
+
+ /* Check, if the pred of the proj is a Cond
+ * with a Projb as selector.
+ */
+ if(is_modeb_cond) {
+ cond_t c;
+
+ memset(&c, 0, sizeof(c));
+ c.cond = cond;
+ c.is_new = 1;
+ c.cases[0].pos = -1;
+ c.cases[1].pos = -1;
+
+ /* get or insert the cond info into the set. */
+ res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
+
+ /*
+ * If this cond is already masked by the masked_by cond
+ * return immediately, since we don't have anything to add.
+ */
+ if(masked_by && res->cases[proj].masked_by == masked_by)
+ return;
+
+ if(res->is_new) {
+ res->is_new = 0;
+ list_add(&res->list, &ci->roots);
+ }
+
+ /*
+ * Set masked by (either NULL or another cond node.
+ * If this cond is truly masked by another one, set
+ * the position of the actually investigated branch
+ * to -1. Since the cond is masked by another one,
+ * there could be more ways from the start block
+ * to this branch, so we choose -1.
+ */
+ res->cases[proj].masked_by = masked_by;
+
+ if(!masked_by)
+ res->cases[proj].pos = pos;
+
+ /*
+ * Since the masked_by nodes masks a cond, remove it from the
+ * root list of the conf trees.
+ */
+ else {
+ assert(res->cases[proj].pos < 0);
+ list_del_init(&masked_by->list);
+ }
+
+ DBG((dbg, LEVEL_2, "%n (%s branch) "
+ "for pos %d in block %n reached by %n\n",
+ cond, proj ? "true" : "false", pos,
+ block, masked_by ? masked_by->cond : NULL));
+ }
+ }
+
+ if(get_Block_block_visited(block) < visited_nr && !saw_select_cond) {
+
+ set_Block_block_visited(block, visited_nr);
+
+ /* Search recursively from this cond. */
+ for(i = 0, n = get_irn_arity(block); i < n; ++i) {
+ ir_node *pred = get_irn_n(block, i);
+
+ /*
+ * If the depth is 0 (the first recursion), we set the pos to
+ * the current viewed predecessor, else we adopt the position
+ * as given by the caller. We also increase the depth for the
+ * recursively called functions.
+ */
+ _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci);
+ }
+ }
+ }
}
* A convenience function for _find_conds.
* It sets some parameters needed for recursion to appropriate start
* values. Always use this function.
- * @param irn The node to start looking for conds from. This might
- * be the phi node we are investigating.
- * @param conds The set to record the found conds in.
+ *
+ * @param irn The node to start looking for Conds from. This might
+ * be the phi node we are investigating.
+ * @param conds The set to record the found Conds in.
*/
static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
{
- int i, n;
- long visited_nr;
- ir_node *block = get_nodes_block(irn);
- ir_node *dom = get_Block_idom(block);
-
+ int i, n;
+ unsigned long visited_nr;
+ ir_node *block = get_nodes_block(irn);
+ ir_node *dom = get_Block_idom(block);
- for(i = 0, n = get_irn_arity(block); i < n; ++i) {
- ir_node *pred = get_irn_n(block, i);
+ for(i = 0, n = get_irn_arity(block); i < n; ++i) {
+ ir_node *pred = get_irn_n(block, i);
- inc_irg_block_visited(current_ir_graph);
- visited_nr = get_irg_block_visited(current_ir_graph);
- set_Block_block_visited(block, visited_nr);
+ inc_irg_block_visited(current_ir_graph);
+ visited_nr = get_irg_block_visited(current_ir_graph);
+ set_Block_block_visited(block, visited_nr);
- DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
- _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
- }
+ DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
+ _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
+ }
}
/**
* Make the mux for a given cond.
- * @param phi The phi node which shall be replaced by a mux.
- * @param dom The block where the muxes shall be placed.
- * @param cond The cond information.
+ *
+ * @param phi The phi node which shall be replaced by a mux.
+ * @param dom The block where the muxes shall be placed.
+ * @param cond The cond information.
+ * @param info The options for createing Mux nodes.
* @return The mux node made for this cond.
*/
static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond,
- int max_depth, ir_node **mux, bitset_t *positions, int *muxes_made, long visited_nr)
+ const opt_if_conv_info_t *info, ir_node **mux, bitset_t *positions,
+ int *muxes_made, long visited_nr)
{
- int i;
- ir_node *projb = get_Cond_selector(cond->cond);
- ir_node *bl = get_nodes_block(cond->cond);
- ir_node *operands[2];
- int set[2];
-
- cond->visited_nr = visited_nr;
- DBG((dbg, LEVEL_2, "%n\n", cond->cond));
- for(i = 0; i < 2; ++i) {
- cond_t *masked_by = cond->cases[i].masked_by;
- int pos = cond->cases[i].pos;
-
- operands[i] = NULL;
- set[i] = -1;
-
- /*
- * If this cond branch is masked by another cond, make the mux
- * for that cond first, since the mux for this cond takes
- * it as an operand.
- */
- if(masked_by) {
- assert(pos < 0);
- DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
- if(masked_by->visited_nr < visited_nr)
- operands[i] = make_mux_on_demand(phi, dom, masked_by, max_depth, mux, positions, muxes_made, visited_nr);
- }
-
- /*
- * If this cond branch is not masked by another cond, take
- * the corresponding phi operand as an operand to the mux.
- */
- else if(pos >= 0) {
- operands[i] = get_irn_n(phi, pos);
- set[i] = pos;
- }
- }
-
- /*
- * Move the operands to the dominator block if the cond
- * made sense. Some conds found are not suitable for making a mux
- * out of them, since one of their branches cannot be reached from
- * the phi block. In that case we do not make a mux and return NULL.
- */
- if(operands[0] && operands[1]
- && can_move_to(operands[0], bl, max_depth)
- && can_move_to(operands[1], bl, max_depth)) {
-
- move_to(operands[0], bl);
- move_to(operands[1], bl);
-
- /* Make the mux. */
- *mux = new_r_Mux(current_ir_graph, bl, projb,
- operands[0], operands[1], get_irn_mode(operands[0]));
-
- *muxes_made += 1;
-
- DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
- *mux, projb, operands[0], operands[1], set[0], set[1]));
-
- for(i = 0; i < 2; ++i)
- if(set[i] >= 0)
- bitset_set(positions, set[i]);
- }
-
- return *mux;
+ int i, can_move[2];
+ ir_node *projb = get_Cond_selector(cond->cond);
+ ir_node *bl = get_nodes_block(cond->cond);
+ ir_node *operands[2];
+ int set[2];
+
+ cond->visited_nr = visited_nr;
+ DBG((dbg, LEVEL_2, "%n\n", cond->cond));
+ for(i = 0; i < 2; ++i) {
+ cond_t *masked_by = cond->cases[i].masked_by;
+ int pos = cond->cases[i].pos;
+
+ operands[i] = NULL;
+ set[i] = -1;
+
+ /*
+ * If this Cond branch is masked by another cond, make the mux
+ * for that Cond first, since the Mux for this cond takes
+ * it as an operand.
+ */
+ if(masked_by) {
+ assert(pos < 0);
+ DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
+ if(masked_by->visited_nr < visited_nr)
+ operands[i] = make_mux_on_demand(phi, dom, masked_by, info, mux, positions, muxes_made, visited_nr);
+ }
+
+ /*
+ * If this cond branch is not masked by another cond, take
+ * the corresponding phi operand as an operand to the mux.
+ */
+ else if(pos >= 0) {
+ operands[i] = get_irn_n(phi, pos);
+ set[i] = pos;
+ }
+ }
+
+ /*
+ * Move the operands to the dominator block if the cond
+ * made sense. Some Conds found are not suitable for making a mux
+ * out of them, since one of their branches cannot be reached from
+ * the phi block. In that case we do not make a mux and return NULL.
+ */
+ if(operands[0] && operands[1]) {
+ if (operands[0] == operands[1]) {
+ /* there is no gain in using mux in this case, as
+ it will be optimized away. We will NOT move the
+ content of the blocks either
+ */
+ for (i = 0; i < 2; ++i)
+ if(set[i] >= 0)
+ bitset_set(positions, set[i]);
+
+ *mux = operands[0];
+ return *mux;
+ }
+
+ can_move[0] = can_move_to(operands[0], bl, info);
+ can_move[1] = can_move_to(operands[1], bl, info);
+
+ if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) {
+ if (info->allow_mux(projb, operands[0], operands[1])) {
+ move_to(operands[0], bl);
+ move_to(operands[1], bl);
+
+ /* Make the mux. */
+ *mux = new_r_Mux(current_ir_graph, bl, projb,
+ operands[0], operands[1], get_irn_mode(operands[0]));
+
+ *muxes_made += 1;
+
+ DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
+ *mux, projb, operands[0], operands[1], set[0], set[1]));
+
+ for(i = 0; i < 2; ++i)
+ if(set[i] >= 0) {
+ bitset_set(positions, set[i]);
+
+ /* we have done one */
+ hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_SUCCESS);
+ }
+ }
+ else {
+ hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_DENIED);
+ }
+ }
+ else {
+ if(can_move[0] != SUCCESS)
+ hook_if_conversion(current_ir_graph, phi, set[0], NULL, can_move[0]);
+ if(can_move[1] != SUCCESS)
+ hook_if_conversion(current_ir_graph, phi, set[1], NULL, can_move[1]);
+ }
+ }
+ else {
+ if(operands[0])
+ hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF);
+ if(operands[1])
+ hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF);
+ }
+
+ return *mux;
}
typedef struct _phi_info_t {
- struct list_head list;
- cond_info_t *cond_info;
- ir_node *irn;
+ struct list_head list;
+ cond_info_t *cond_info;
+ ir_node *irn;
} phi_info_t;
* @param irn A phi node.
* @param info Parameters for the if conversion algorithm.
*/
-static int check_out_phi(phi_info_t *phi_info, opt_if_conv_info_t *info)
-{
- int max_depth = info->max_depth;
- ir_node *irn = phi_info->irn;
- ir_node *block, *nw;
- cond_info_t *cond_info = phi_info->cond_info;
- cond_t *cond;
- int i, arity;
- int muxes_made = 0;
- bitset_t *positions;
-
- block = get_nodes_block(irn);
- arity = get_irn_arity(irn);
- positions = bitset_alloca(arity);
-
- assert(is_Phi(irn));
- assert(get_irn_arity(irn) == get_irn_arity(block));
- assert(arity > 0);
-
- DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
-
- list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
- ir_node *cidom = block;
- ir_node *mux = NULL;
- cond_t *p, *head = NULL;
- long pos;
-
- bitset_clear_all(positions);
-
- DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
- /*
- * Link all conds which are in the subtree of
- * the current cond in the list together.
- */
- walk_conds(cond, link_conds, NULL, &head);
-
- cidom = block;
- for(p = head; p; p = p->link) {
- for(i = 0; i < 2; ++i) {
- int pos = p->cases[i].pos;
- if(pos != -1)
- cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
- }
- }
-
- DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
- make_mux_on_demand(irn, cidom, cond, max_depth, &mux, positions, &muxes_made, ++cond_visited_nr);
-
- if(mux) {
- bitset_foreach(positions, pos)
- set_irn_n(irn, (int) pos, mux);
- }
- }
-
- /*
- * optimize the phi away. This can anable further runs of this
- * function. Look at _can_move. phis cannot be moved there.
- */
- nw = optimize_in_place_2(irn);
- if(nw != irn)
- exchange(irn, nw);
-
- return muxes_made;
+static int check_out_phi(phi_info_t *phi_info, const opt_if_conv_info_t *info)
+{
+ ir_node *irn = phi_info->irn;
+ ir_node *block, *nw;
+ cond_info_t *cond_info = phi_info->cond_info;
+ cond_t *cond;
+ int i, arity;
+ int muxes_made = 0;
+ bitset_t *positions;
+
+ block = get_nodes_block(irn);
+ arity = get_irn_arity(irn);
+ positions = bitset_alloca(arity);
+
+ assert(is_Phi(irn));
+ assert(get_irn_arity(irn) == get_irn_arity(block));
+ assert(arity > 0);
+
+ DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
+
+ list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
+ ir_node *cidom = block;
+ ir_node *mux = NULL;
+ cond_t *p, *head = NULL;
+ long pos;
+
+ bitset_clear_all(positions);
+
+ DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
+ /*
+ * Link all conds which are in the subtree of
+ * the current cond in the list together.
+ */
+ walk_conds(cond, link_conds, NULL, &head);
+
+ cidom = block;
+ for(p = head; p; p = p->link) {
+ for(i = 0; i < 2; ++i) {
+ int pos = p->cases[i].pos;
+ if(pos != -1)
+ cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
+ }
+ }
+
+ DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
+ make_mux_on_demand(irn, cidom, cond, info, &mux, positions, &muxes_made, ++cond_visited_nr);
+
+ if(mux) {
+ bitset_foreach(positions, pos)
+ set_irn_n(irn, (int) pos, mux);
+ }
+ }
+
+ /*
+ * optimize the phi away. This can anable further runs of this
+ * function. Look at _can_move. phis cannot be moved there.
+ */
+ nw = optimize_in_place_2(irn);
+ if(nw != irn)
+ exchange(irn, nw);
+
+ return muxes_made;
}
typedef struct _cond_walk_info_t {
- struct obstack *obst;
- struct list_head cond_info_head;
- struct list_head phi_head;
+ struct obstack *obst;
+ struct list_head cond_info_head;
+ struct list_head phi_head;
} cond_walk_info_t;
static void annotate_cond_info_pre(ir_node *irn, void *data)
{
- set_irn_link(irn, NULL);
+ set_irn_link(irn, NULL);
}
static void annotate_cond_info_post(ir_node *irn, void *data)
{
- cond_walk_info_t *cwi = data;
-
- /*
- * Check, if the node is a phi
- * we then compute a set of conds which are reachable from this
- * phi's block up to its dominator.
- * The set is attached to the blocks link field.
- */
- if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
- ir_node *block = get_nodes_block(irn);
-
- cond_info_t *ci = get_irn_link(block);
-
- /* If the set is not yet computed, do it now. */
- if(!ci) {
- ci = obstack_alloc(cwi->obst, sizeof(*ci));
- ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
- ci->first_phi = irn;
-
- INIT_LIST_HEAD(&ci->roots);
- INIT_LIST_HEAD(&ci->list);
-
- /*
- * Add this cond info to the list of all cond infos
- * in this graph. This is just done to free the
- * set easier afterwards (we save an irg_walk_graph).
- */
- list_add(&cwi->cond_info_head, &ci->list);
-
- DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
-
- /*
- * Fill the set with conds we find on the way from
- * the block to its dominator.
- */
- find_conds(irn, ci);
-
- /*
- * If there where no suitable conds, delete the set
- * immediately and reset the set pointer to NULL
- */
- if(set_count(ci->cond_set) == 0) {
- del_set(ci->cond_set);
- list_del(&ci->list);
- obstack_free(cwi->obst, ci);
- ci = NULL;
- }
- }
-
- else
- DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
-
- set_irn_link(block, ci);
-
- if(ci) {
- phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
- pi->irn = irn;
- pi->cond_info = ci;
- INIT_LIST_HEAD(&pi->list);
- list_add(&pi->list, &cwi->phi_head);
- }
-
- }
+ cond_walk_info_t *cwi = data;
+
+ /*
+ * Check, if the node is a phi
+ * we then compute a set of conds which are reachable from this
+ * phi's block up to its dominator.
+ * The set is attached to the blocks link field.
+ */
+ if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
+ ir_node *block = get_nodes_block(irn);
+
+ cond_info_t *ci = get_irn_link(block);
+
+ /* If the set is not yet computed, do it now. */
+ if(!ci) {
+ ci = obstack_alloc(cwi->obst, sizeof(*ci));
+ ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
+ ci->first_phi = irn;
+
+ INIT_LIST_HEAD(&ci->roots);
+ INIT_LIST_HEAD(&ci->list);
+
+ /*
+ * Add this cond info to the list of all cond infos
+ * in this graph. This is just done to xfree the
+ * set easier afterwards (we save an irg_walk_graph).
+ */
+ list_add(&cwi->cond_info_head, &ci->list);
+
+ DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
+
+ /*
+ * Fill the set with conds we find on the way from
+ * the block to its dominator.
+ */
+ find_conds(irn, ci);
+
+ /*
+ * If there where no suitable conds, delete the set
+ * immediately and reset the set pointer to NULL
+ */
+ if(set_count(ci->cond_set) == 0) {
+ del_set(ci->cond_set);
+ list_del(&ci->list);
+ obstack_free(cwi->obst, ci);
+ ci = NULL;
+ }
+ }
+
+ else
+ DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
+
+ set_irn_link(block, ci);
+
+ if(ci) {
+ phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
+ pi->irn = irn;
+ pi->cond_info = ci;
+ INIT_LIST_HEAD(&pi->list);
+ list_add(&pi->list, &cwi->phi_head);
+ }
+
+ }
}
static void dump_conds(cond_t *cond, void *env)
{
- int i;
- FILE *f = env;
+ int i;
+ FILE *f = env;
- ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
- cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
- get_nodes_block(cond->cond));
+ ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
+ cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
+ get_nodes_block(cond->cond));
- for(i = 0; i < 2; ++i)
- if(cond->cases[i].masked_by)
- ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
- cond, cond->cases[i].masked_by, i);
+ for(i = 0; i < 2; ++i)
+ if(cond->cases[i].masked_by)
+ ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
+ cond, cond->cases[i].masked_by, i);
}
static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi)
{
- char buf[512];
- FILE *f;
-
- snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
-
- if((f = fopen(buf, "wt")) != NULL) {
- cond_info_t *ci;
- phi_info_t *phi;
- cond_t *cond;
-
- ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
- list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
- ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
- list_for_each_entry(cond_t, cond, &ci->roots, list) {
- walk_conds(cond, NULL, dump_conds, f);
- ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
- }
- }
-
- list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
- ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
- phi->irn, phi->irn, get_nodes_block(phi->irn));
- ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
- }
- fprintf(f, "}\n");
- }
+ char buf[512];
+ FILE *f;
+
+ snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
+
+ if((f = fopen(buf, "wt")) != NULL) {
+ cond_info_t *ci;
+ phi_info_t *phi;
+ cond_t *cond;
+
+ ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
+ list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
+ ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
+ list_for_each_entry(cond_t, cond, &ci->roots, list) {
+ walk_conds(cond, NULL, dump_conds, f);
+ ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
+ }
+ }
+
+ list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
+ ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
+ phi->irn, phi->irn, get_nodes_block(phi->irn));
+ ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
+ }
+ fprintf(f, "}\n");
+ }
}
-void opt_if_conv(ir_graph *irg, opt_if_conv_info_t *params)
+void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
{
- int muxes_made = 0;
- struct obstack obst;
- phi_info_t *phi_info;
- cond_info_t *cond_info;
- cond_walk_info_t cwi;
+ int muxes_made = 0;
+ struct obstack obst;
+ phi_info_t *phi_info;
+ cond_info_t *cond_info;
+ cond_walk_info_t cwi;
- opt_if_conv_info_t *p = params ? params : &default_info;
+ opt_if_conv_info_t p;
- if(!get_opt_if_conversion())
- return;
+ if(!get_opt_if_conversion())
+ return;
- obstack_init(&obst);
+ /* get the parameters */
+ if (params)
+ memcpy(&p, params, sizeof(p));
+ else
+ memcpy(&p, &default_info, sizeof(p));
- cwi.obst = &obst;
- INIT_LIST_HEAD(&cwi.cond_info_head);
- INIT_LIST_HEAD(&cwi.phi_head);
+ if (! p.allow_mux)
+ p.allow_mux = default_info.allow_mux;
- /* Init the debug stuff. */
- dbg = firm_dbg_register("firm.opt.ifconv");
+ obstack_init(&obst);
+
+ cwi.obst = &obst;
+ INIT_LIST_HEAD(&cwi.cond_info_head);
+ INIT_LIST_HEAD(&cwi.phi_head);
+
+ /* Init the debug stuff. */
+ FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
#if 0
- firm_dbg_set_mask(dbg, LEVEL_1);
+ firm_dbg_set_mask(dbg, LEVEL_1|LEVEL_2|LEVEL_3);
#endif
- /* Ensure, that the dominators are computed. */
- compute_doms(irg);
+ /* if-conversion works better with normalized returns */
+ normalize_one_return(irg);
- DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
- get_entity_name(get_irg_entity(irg)), irg));
+ /* Ensure, that the dominators are computed. */
+ assure_doms(irg);
- /*
- * Collect information about the conds pu the phis on an obstack.
- * It is important that phi nodes which are 'higher' (with a
- * lower dfs pre order) are in front of the obstack. Since they are
- * possibly turned in to muxes this can enable the optimization
- * of 'lower' ones.
- */
- irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
+ DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
+ get_entity_name(get_irg_entity(irg)), irg));
+
+ /*
+ * Collect information about the conds pu the phis on an obstack.
+ * It is important that phi nodes which are 'higher' (with a
+ * lower dfs pre order) are in front of the obstack. Since they are
+ * possibly turned in to muxes this can enable the optimization
+ * of 'lower' ones.
+ */
+ irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
#if 0
- vcg_dump_conds(irg, &cwi);
+ vcg_dump_conds(irg, &cwi);
#endif
- /* Process each suitable phi found. */
- list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
- DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
- muxes_made += check_out_phi(phi_info, p);
- }
+ /* Process each suitable phi found. */
+ list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
+ DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
+ muxes_made += check_out_phi(phi_info, &p);
+ }
- list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
- del_set(cond_info->cond_set);
- }
+ list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
+ del_set(cond_info->cond_set);
+ }
- DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
+ DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
- obstack_free(&obst, NULL);
+ obstack_free(&obst, NULL);
+
+ dump_ir_block_graph(irg, "_ifconv_hack");
}
+
+#endif
projects / libfirm / blobdiff