X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fifconv.c;h=daafa17bc3fa8f58d332c4dce1672885ef700ea3;hb=8eb0a1256d88d68e762c1f087bffadca68dc5c12;hp=49be52a6b092a2103c5bb67ec6f2977684399a84;hpb=89eed07bb73e771f357eb2fa9a98dcba85d8e32f;p=libfirm diff --git a/ir/opt/ifconv.c b/ir/opt/ifconv.c index 49be52a6b..daafa17bc 100644 --- a/ir/opt/ifconv.c +++ b/ir/opt/ifconv.c @@ -3,13 +3,29 @@ * Make Mux nodes from Conds where it its possible. * @author Sebastian Hack * @date 4.2.2005 + * $Id$ */ +#ifdef HAVE_CONFIG_H +#include "config.h" +#endif +#ifdef HAVE_STDLIB_H #include +#endif +#ifdef HAVE_STRING_H +#include +#endif +#ifdef HAVE_ALLOCA_H #include +#endif +#ifdef HAVE_MALLOC_H +#include +#endif #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" @@ -17,10 +33,15 @@ #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" -#define MAX_DEPTH 4 +#define MAX_DEPTH 20 /* * Mux optimization routines. @@ -44,7 +65,7 @@ static ir_node *local_optimize_mux(ir_node *mux) /* 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); @@ -104,26 +125,44 @@ static ir_node *local_optimize_mux(ir_node *mux) } #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)); @@ -136,8 +175,8 @@ static ir_node *optimize_mux_chain(ir_node *mux) 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) * @@ -160,8 +199,8 @@ static ir_node *optimize_mux_chain(ir_node *mux) 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), @@ -174,8 +213,8 @@ static ir_node *optimize_mux_chain(ir_node *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), @@ -185,6 +224,7 @@ static ir_node *optimize_mux_chain(ir_node *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])); @@ -200,50 +240,59 @@ static ir_node *optimize_mux_chain(ir_node *mux) * 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; /** - * 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) + if (op == op_Cmp) return 0; return !mode_is_datab(get_irn_mode(irn)); } +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 +}; + /** - * Decdies, if a given expression and its subexpressions + * 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 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 * examined. + * + * @return a failure reason */ static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, int max_depth) { int i, n; - int res = 1; + 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 >= max_depth) { - res = 0; + res = TO_DEEP; goto end; } @@ -253,26 +302,34 @@ static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, int max_d * has side effects or anything else. It is executed on each * path the destination block is reached. */ - if(block_dominates(expr_block, dest_block)) + 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 superflous and could be converted into a assertion. + * 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 = 0; + 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 onw should also test the floating property of + * movable. Perhaps one should also test the floating property of * the opcode/node. */ - if(has_side_effects(expr)) { - res = 0; + if (has_side_effects(expr)) { + res = IF_RESULT_SIDE_EFFECT; goto end; } @@ -281,17 +338,18 @@ static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, int max_d * 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) { + 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; + + res = _can_move_to(op, dest_block, new_depth, max_depth); + + if (res != SUCCESS) goto end; - } } 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; } @@ -303,17 +361,24 @@ end: * 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 max_depth The maximum depth @p expr should be investigated. + * + * @return return a failure reason */ static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, int max_depth) { return _can_move_to(expr, dest_block, 0, max_depth); } +/** + * 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; @@ -323,21 +388,43 @@ static void move_to(ir_node *expr, ir_node *dest_block) * If we reached the dominator, we are done. * We will never put code through the dominator */ - if(block_dominates(expr_block, dest_block)) + if (block_dominates(expr_block, dest_block)) return; - for(i = 0, n = get_irn_arity(expr); i < n; ++i) + 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); } +/** + * 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 = 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. */ - 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 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' @@ -349,16 +436,69 @@ typedef struct _cond_t { 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; +/** + * retrieve the conditional information from a Cond node + */ +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. @@ -370,51 +510,85 @@ static int cond_cmp(const void *a, const void *b, size_t size) 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 class. */ + + 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. */ +} cond_info_t; + /** * @see find_conds. */ -static void _find_conds(ir_node *irn, ir_node *start_block, - 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_select_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; - /* We ran into a loop, since we saw the start block twice. */ - if(block == start_block && depth > 0) - return; - - /* 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; - cond_t *res, c; + 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.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. @@ -425,43 +599,74 @@ static void _find_conds(ir_node *irn, ir_node *start_block, * 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 { + 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)); } } - /* 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(get_Block_block_visited(block) < visited_nr && !saw_select_cond) { - /* - * 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, start_block, dominator, cond, depth == 0 ? i : pos, depth + 1, conds); + 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 dominator The dominator up to which we want to look for conds. - * @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, ir_node *dominator, set *conds) +static INLINE void find_conds(ir_node *irn, cond_info_t *ci) { - _find_conds(irn, get_nodes_block(irn), 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. @@ -470,162 +675,190 @@ static INLINE void find_conds(ir_node *irn, ir_node *dominator, set *conds) * @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; + 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 + * 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]) { + 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, max_depth); + can_move[1] = can_move_to(operands[1], bl, max_depth); + + if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) { + 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 { + 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] != SUCCESS) + hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF); + if(operands[1] != SUCCESS) + hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF); + } + + return *mux; +} - /* Make the mux. */ - cond->mux = new_r_Mux(current_ir_graph, dom, projb, - operands[0], operands[1], get_irn_mode(operands[0])); +typedef struct _phi_info_t { + struct list_head list; + cond_info_t *cond_info; + ir_node *irn; +} phi_info_t; - return cond->mux; -} /** * 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_5, "phi candidate: %n\n", irn)); + DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn)); - /* - * 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; - } - } + 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; - 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]; - } - } + nw = optimize_in_place_2(irn); + if(nw != irn) + exchange(irn, nw); -#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 + return muxes_made; +} - /* - * 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); +typedef struct _cond_walk_info_t { + struct obstack *obst; + struct list_head cond_info_head; + struct list_head phi_head; +} cond_walk_info_t; - mux = optimize_mux_chain(mux); - /* - * 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) { @@ -634,87 +867,171 @@ 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 * phi's block up to its dominator. * The set is attached to the blocks link field. */ - if(is_Phi(irn)) { + 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", irn)); /* * 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); +#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); + +#if 0 + vcg_dump_conds(irg, &cwi); +#endif - /* traverse the list of linked phis */ - while(list_head) { - check_out_phi(list_head, p); - list_head = get_irn_link(list_head); + /* 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); } - irg_walk_graph(irg, free_sets, NULL, NULL); + 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)); + + obstack_free(&obst, NULL); }