* Make Mux nodes from Conds where it its possible.
* @author Sebastian Hack
* @date 4.2.2005
+ * $Id$
*/
#include <stdlib.h>
+#include <string.h>
#include <alloca.h>
#include "irgraph_t.h"
#include "irnode_t.h"
+#include "iropt_t.h"
+#include "irgmod.h"
#include "irmode_t.h"
#include "ircons_t.h"
#include "irdom_t.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"
-#define MAX_DEPTH 4
+#define MAX_DEPTH 20
/*
* Mux optimization routines.
/* 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) {
- pnc_number cc = get_Proj_proj(sel);
+ 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);
}
#endif
+/**
+ * check, if a node is const and return its tarval or
+ * return a default tarval.
+ * @param cnst The node whose tarval to get.
+ * @param or The alternative tarval, if the node is no Const.
+ * @return The tarval of @p cnst, if the node is Const, @p otherwise.
+ */
static tarval *get_value_or(ir_node *cnst, tarval *or)
{
return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
}
+/**
+ * Try to optimize nested muxes into a dis- or conjunction
+ * of two muxes.
+ * @param mux The parent mux, which has muxes as operands.
+ * @return The replacement node for this mux. If the optimization is
+ * successful, this might be an And or Or node, if not, its the mux
+ * himself.
+ */
static ir_node *optimize_mux_chain(ir_node *mux)
{
int i;
ir_node *res;
ir_node *ops[2];
- ir_mode *mode;
+ ir_mode *mode = get_irn_mode(mux);
tarval *null;
tarval *minus_one;
- if(get_irn_op(mux) != op_Mux)
+ /*
+ * 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;
- mode = get_irn_mode(mux);
null = get_tarval_null(mode);
minus_one = tarval_sub(null, get_tarval_one(mode));
ir_node *child_mux;
/*
- * This is the or case, the child mux is the false operand
- * of the parent 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)
*
tvb = get_value_or(b, minus_one);
tvd = get_value_or(d, null);
- if(tarval_cmp(tarval_or(tva, tvd), tvd) == Eq
- && tarval_cmp(tarval_or(tvb, tvd), tvd) == Eq) {
+ 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),
tvb = get_value_or(b, null);
tvd = get_value_or(d, minus_one);
- if(tarval_cmp(tarval_and(tva, tvd), tvd) == Eq
- && tarval_cmp(tarval_and(tvb, tvd), tvd) == Eq) {
+ 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),
}
}
+ /* recursively optimize nested muxes. */
set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
* Default options.
*/
static opt_if_conv_info_t default_info = {
- 4
+ MAX_DEPTH
};
-/** THe debugging module. */
+/** The debugging module. */
static firm_dbg_module_t *dbg;
/**
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,
}
end:
- DBG((dbg, LEVEL_5, "\t\t\tcan move to(%d) %n: %d\n", depth, expr, res));
+ DBG((dbg, LEVEL_3, "\t\t\t%Dcan move to %n: %d\n", depth, expr, res));
return res;
}
set_nodes_block(expr, dest_block);
}
+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;
+ }
+}
+
+
/**
* Information about a cond node.
*/
typedef struct _cond_t {
- ir_node *cond; /**< The cond node. */
- ir_node *mux; /**< The mux node, that will be generated for this cond. */
+ 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'
reached. It is -1, if this branch is
only reached through another cond. */
- ir_node *masked_by; /**< If this cond's branch is only reached
- through another cond, we store this
- cond ir_node here. */
+ 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;
+static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
+{
+ cond_t templ;
+
+ 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)
+{
+ int i;
+
+ if(cond->visited_nr >= visited_nr)
+ return;
+
+ cond->visited_nr = visited_nr;
+
+ if(pre)
+ pre(cond, env);
+
+ 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(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);
+}
+
+static void link_conds(cond_t *cond, void *env)
+{
+ cond_t **ptr = (cond_t **) env;
+
+ cond->link = *ptr;
+ *ptr = cond;
+}
+
/**
* Compare two conds for use in a firm set.
* Two cond_t's are equal, if they designate the same cond node.
- * @param a A cond_t
+ * @param a A cond_t.
* @param b Another one.
* @param size Not used.
* @return 0 (!) if they are equal, != 0 otherwise.
return x->cond != y->cond;
}
+/**
+ * Information about conds which can be made to muxes.
+ * Instances of this struct are attached to the link field of
+ * blocks in which phis are located.
+ */
+typedef struct _cond_info_t {
+ struct list_head list; /**< Used to list all of these structs per method. */
+
+ 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. */
+
+ 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, unsigned long visited_nr,
- ir_node *dominator, ir_node *masked_by, int pos, int depth, set *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)
{
ir_node *block;
+ int saw_switch_cond = 0;
block = get_nodes_block(irn);
- if(block_dominates(dominator, block)) {
- ir_node *cond = NULL;
+ /*
+ * 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 */
+ /* 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);
- cond = get_Proj_pred(irn);
+ ir_node *cond = get_Proj_pred(irn);
- /* Check, if the pred of the proj is a Cond
- * with a Projb as selector. */
- if(get_irn_opcode(cond) == iro_Cond
- && get_irn_mode(get_Cond_selector(cond)) == mode_b) {
+ /* 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_switch_cond = !is_modeb_cond;
- cond_t *res, c;
+ /* 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.mux = NULL;
+ 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(conds, &c, sizeof(c), HASH_PTR(cond));
+ res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
/*
- * Link it to the cond ir_node. We need that later, since
- * one cond masks the other we want to retreive the cond_t
- * data from the masking cond ir_node.
+ * If this cond is already masked by the masked_by cond
+ * return immediately, since we don't have anything to add.
*/
- set_irn_link(cond, res);
+ 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.
* to this branch, so we choose -1.
*/
res->cases[proj].masked_by = masked_by;
+
if(!masked_by)
res->cases[proj].pos = pos;
- DBG((dbg, LEVEL_5, "found cond %n (%s branch) for pos %d in block %n reached by %n\n",
- cond, get_Proj_proj(irn) ? "true" : "false", pos, block, masked_by));
+ /*
+ * Since the masked_by nodes masks a cond, remove it from the
+ * root list of the conf trees.
+ */
+ else {
+ DBG((dbg, LEVEL_2, "%Ddeleting from list: %n, res: %n\n", depth, masked_by->cond, res->cond));
+ 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 this block has already been visited, don't recurse to its
- * children.
- */
- if(get_Block_block_visited(block) < visited_nr) {
+ if(get_Block_block_visited(block) < visited_nr && !saw_switch_cond) {
- /* Mark the block visited. */
set_Block_block_visited(block, visited_nr);
/* Search recursively from this cond. */
* as given by the caller. We also increase the depth for the
* recursively called functions.
*/
- _find_conds(pred, visited_nr, dominator, cond, depth == 0 ? i : pos, depth + 1, conds);
+ _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 dominator The dominator up to which we want to look for conds.
* @param conds The set to record the found conds in.
*/
-static INLINE void find_conds(ir_node *irn, ir_node *dominator, set *conds)
+static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
{
- inc_irg_block_visited(current_ir_graph);
- _find_conds(irn, get_irg_block_visited(current_ir_graph), dominator, NULL, 0, 0, conds);
-}
+ int i, n;
+ 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);
+
+ 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);
+ }
+}
+
/**
* Make the mux for a given cond.
* @param phi The phi node which shall be replaced by a mux.
* @param cond The cond information.
* @return The mux node made for this cond.
*/
-static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *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)
{
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(cond->cases[i].masked_by) {
- cond_t *masking_cond = get_irn_link(cond->cases[i].masked_by);
- operands[i] = make_mux_on_demand(phi, dom, masking_cond);
+ 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 {
- assert(cond->cases[i].pos >= 0);
- operands[i] = get_irn_n(phi, cond->cases[i].pos);
+ else if(pos >= 0) {
+ operands[i] = get_irn_n(phi, pos);
+ set[i] = pos;
}
-
- /* Move the selected operand to the dominator block. */
- move_to(operands[i], dom);
}
- /* Move the comparison expression of the cond to the dominator. */
- move_to(projb, dom);
+ /*
+ * 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)) {
- /* Make the mux. */
- cond->mux = new_r_Mux(current_ir_graph, dom, projb,
- operands[0], operands[1], get_irn_mode(operands[0]));
+ move_to(operands[0], bl);
+ move_to(operands[1], bl);
- return cond->mux;
+ /* 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;
}
+typedef struct _phi_info_t {
+ struct list_head list;
+ cond_info_t *cond_info;
+ ir_node *irn;
+} phi_info_t;
+
+
/**
* Examine a phi node if it can be replaced by some muxes.
* @param irn A phi node.
* @param info Parameters for the if conversion algorithm.
*/
-static void check_out_phi(ir_node *irn, opt_if_conv_info_t *info)
+static int check_out_phi(phi_info_t *phi_info, opt_if_conv_info_t *info)
{
int max_depth = info->max_depth;
- int i;
- ir_node *block;
- int arity;
- ir_node *idom;
- ir_node *mux = NULL;
-
- cond_t **conds;
+ ir_node *irn = phi_info->irn;
+ ir_node *block, *nw;
+ cond_info_t *cond_info = phi_info->cond_info;
cond_t *cond;
- cond_t *largest_cond;
- set *cond_set;
- int n_conds = 0;
-
- if(!is_Phi(irn))
- return;
+ int i, arity;
+ int muxes_made = 0;
+ bitset_t *positions;
block = get_nodes_block(irn);
arity = get_irn_arity(irn);
- idom = get_Block_idom(block);
+ positions = bitset_alloca(arity);
assert(is_Phi(irn));
assert(get_irn_arity(irn) == get_irn_arity(block));
assert(arity > 0);
- cond_set = get_irn_link(block);
- assert(conds && "no cond set for this phi");
+ DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
- DBG((dbg, LEVEL_5, "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;
- /*
- * Check, if we can move all operands of the
- * phi node to the dominator. Else exit.
- */
- for(i = 0; i < arity; ++i) {
- if(!can_move_to(get_irn_n(irn, i), idom, max_depth)) {
- DBG((dbg, LEVEL_5, "cannot move operand %d of %n to %n\n", i, irn, idom));
- return;
- }
- }
-
- n_conds = set_count(cond_set);
+ bitset_clear_all(positions);
- /* This should never happen and can be turned into an assertion */
- if(n_conds == 0) {
- DBG((dbg, LEVEL_5, "no conds found. how can this be?"));
- return;
- }
+ 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)));
+ }
+ }
- /*
- * Put all cond information structures into an array.
- * This is just done for convenience. It's not neccessary.
- */
- conds = alloca(n_conds * sizeof(conds[0]));
- for(i = 0, cond = set_first(cond_set); cond; cond = set_next(cond_set))
- conds[i++] = cond;
+ 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);
- /*
- * Check, if we can move the compare nodes of the conds to
- * the dominator.
- */
- for(i = 0; i < n_conds; ++i) {
- ir_node *projb = get_Cond_selector(conds[i]->cond);
- if(!can_move_to(projb, idom, max_depth)) {
- DBG((dbg, LEVEL_5, "cannot move Projb %d of %n to %n\n", i, projb, idom));
- return;
+ if(mux) {
+ bitset_foreach(positions, pos)
+ set_irn_n(irn, (int) pos, mux);
}
}
/*
- * Find the largest cond (the one that dominates all others)
- * and start the mux generation from there.
+ * optimize the phi away. This can anable further runs of this
+ * function. Look at _can_move. phis cannot be moved there.
*/
- largest_cond = conds[0];
- DBG((dbg, LEVEL_5, "\tlargest cond %n\n", largest_cond->cond));
- for(i = 1; i < n_conds; ++i) {
- ir_node *curr_largest_block = get_nodes_block(largest_cond->cond);
- ir_node *bl = get_nodes_block(conds[i]->cond);
-
- if(block_dominates(bl, curr_largest_block)) {
- DBG((dbg, LEVEL_5, "\tnew largest cond %n\n", largest_cond->cond));
- largest_cond = conds[i];
- }
- }
-
-#if 0
- for(i = 0; i < n_conds; ++i) {
- cond_t *c = conds[i];
- DBG((dbg, LEVEL_5, "\tcond %n (t: (%d,%n), f: (%d,%n))\n", c->cond,
- c->cases[1].pos, c->cases[1].masked_by,
- c->cases[0].pos, c->cases[0].masked_by));
- }
-#endif
+ nw = optimize_in_place_2(irn);
+ if(nw != irn)
+ exchange(irn, nw);
- /*
- * Make the mux for the 'largest' cond. This will also
- * produce all other muxes.
- * @see make_mux_on_demand.
- */
- mux = make_mux_on_demand(irn, idom, largest_cond);
+ return muxes_made;
+}
- /*
- * Try to optimize mux chains.
- */
- mux = optimize_mux_chain(mux);
+typedef struct _cond_walk_info_t {
+ struct obstack *obst;
+ struct list_head cond_info_head;
+ struct list_head phi_head;
+} cond_walk_info_t;
- /*
- * Set all preds of the phi node to the mux
- * for the 'largest' cond.
- */
- for(i = 0; i < arity; ++i)
- set_irn_n(irn, i, mux);
-}
static void annotate_cond_info_pre(ir_node *irn, void *data)
{
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
*/
if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
ir_node *block = get_nodes_block(irn);
- ir_node **phi_list_head = (ir_node **) data;
- set *conds = get_irn_link(block);
+ cond_info_t *ci = get_irn_link(block);
/* If the set is not yet computed, do it now. */
- if(!conds) {
- ir_node *idom = get_Block_idom(block);
- conds = new_set(cond_cmp, 8);
+ 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)\n", irn, block));
/*
* Fill the set with conds we find on the way from
* the block to its dominator.
*/
- find_conds(irn, idom, conds);
+ find_conds(irn, ci);
/*
* If there where no suitable conds, delete the set
* immediately and reset the set pointer to NULL
*/
- if(set_count(conds) == 0) {
- del_set(conds);
- conds = NULL;
+ if(set_count(ci->cond_set) == 0) {
+ del_set(ci->cond_set);
+ list_del(&ci->list);
+ obstack_free(cwi->obst, ci);
+ ci = NULL;
}
}
- set_irn_link(block, conds);
+ else
+ DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
- /*
- * If this phi node has a set of conds reachable, enqueue
- * the phi node in a list with its link field.
- * Then, we do not have to walk the graph again. We can
- * use the list to reach all phi nodes for which if conversion
- * can be tested.
- */
- if(conds) {
- ir_node *old = *phi_list_head;
- set_irn_link(irn, old);
- *phi_list_head = irn;
+ 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 free_sets(ir_node *irn, void *data)
+static void dump_conds(cond_t *cond, void *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));
+
+ 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)
{
- if(is_Block(irn) && get_irn_link(irn)) {
- set *conds = get_irn_link(irn);
- del_set(conds);
+ 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)
{
+ 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;
- ir_node *list_head = NULL;
if(!get_opt_if_conversion())
return;
+ obstack_init(&obst);
+
+ cwi.obst = &obst;
+ INIT_LIST_HEAD(&cwi.cond_info_head);
+ INIT_LIST_HEAD(&cwi.phi_head);
+
+ /* Init the debug stuff. */
dbg = firm_dbg_register("firm.opt.ifconv");
- firm_dbg_set_mask(dbg, -1);
+#if 0
+ firm_dbg_set_mask(dbg, LEVEL_1 | LEVEL_2 | LEVEL_3);
+#endif
+ /* Ensure, that the dominators are computed. */
compute_doms(irg);
- DBG((dbg, LEVEL_4, "if conversion for irg %s(%p)\n",
+
+ DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
get_entity_name(get_irg_entity(irg)), irg));
- irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &list_head);
+ /*
+ * 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);
- /* traverse the list of linked phis */
- while(list_head) {
- check_out_phi(list_head, p);
- list_head = get_irn_link(list_head);
+#if 0
+ 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);
+ }
+
+ list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
+ del_set(cond_info->cond_set);
}
- irg_walk_graph(irg, free_sets, NULL, NULL);
+ DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
+
+ obstack_free(&obst, NULL);
}
projects / libfirm / blobdiff