X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fopt%2Fifconv.c;h=daafa17bc3fa8f58d332c4dce1672885ef700ea3;hb=9bea3d74018e82f653deadff88f8626fd1a6557d;hp=e989a3052525f926ee802232219bace1cf81b834;hpb=2620c51c7c0939dc2ba6d8fbc56e824781371f4e;p=libfirm diff --git a/ir/opt/ifconv.c b/ir/opt/ifconv.c index e989a3052..daafa17bc 100644 --- a/ir/opt/ifconv.c +++ b/ir/opt/ifconv.c @@ -5,10 +5,22 @@ * @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" @@ -27,6 +39,7 @@ #include "set.h" #include "bitset.h" #include "bitfiddle.h" +#include "irhooks.h" #define MAX_DEPTH 20 @@ -234,43 +247,52 @@ static opt_if_conv_info_t default_info = { 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; } @@ -280,34 +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 = 0; + 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; } @@ -316,13 +338,14 @@ 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: @@ -338,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; @@ -358,15 +388,18 @@ 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)) @@ -376,21 +409,20 @@ static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2) else { ir_node *p; - for(p = b1; !block_dominates(p, b2); p = get_Block_idom(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 + struct list_head list; /**< List head which is used for queuing this cond into the cond bunch it belongs to. */ - unsigned in_list : 1; unsigned is_new : 1; + unsigned totally_covers : 1; struct _cond_t *link; long visited_nr; @@ -410,6 +442,9 @@ typedef struct _cond_t { } 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; @@ -445,10 +480,11 @@ static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *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) { - static long visited_nr = 0; - _walk_conds(cond, pre, post, ++visited_nr, env); + _walk_conds(cond, pre, post, ++cond_visited_nr, env); } static void link_conds(cond_t *cond, void *env) @@ -482,12 +518,13 @@ static int cond_cmp(const void *a, const void *b, size_t size) 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 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). */ - 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; /** @@ -497,7 +534,7 @@ 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 is_modeb_cond = 0; + int saw_select_cond = 0; block = get_nodes_block(irn); @@ -505,8 +542,8 @@ static void _find_conds(ir_node *irn, long visited_nr, * 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 = NULL; + 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 @@ -521,9 +558,11 @@ static void _find_conds(ir_node *irn, long visited_nr, 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 + 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. */ @@ -539,13 +578,15 @@ static void _find_conds(ir_node *irn, long visited_nr, /* 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; - INIT_LIST_HEAD(&res->list); - } - - if(!res->in_list) { - res->in_list = 1; list_add(&res->list, &ci->roots); } @@ -566,18 +607,19 @@ static void _find_conds(ir_node *irn, long visited_nr, * Since the masked_by nodes masks a cond, remove it from the * root list of the conf trees. */ - else if(!list_empty(&masked_by->list)) { + else { + assert(res->cases[proj].pos < 0); list_del_init(&masked_by->list); } - DBG((dbg, LEVEL_2, "%{firm:indent}found cond %n (%s branch) " + DBG((dbg, LEVEL_2, "%D%n (%s branch) " "for pos %d in block %n reached by %n\n", - depth, cond, get_Proj_proj(irn) ? "true" : "false", pos, + depth, cond, proj ? "true" : "false", pos, block, masked_by ? masked_by->cond : NULL)); } } - if(get_Block_block_visited(block) < visited_nr) { + if(get_Block_block_visited(block) < visited_nr && !saw_select_cond) { set_Block_block_visited(block, visited_nr); @@ -591,7 +633,7 @@ static void _find_conds(ir_node *irn, long visited_nr, * as given by the caller. We also increase the depth for the * recursively called functions. */ - _find_conds(pred, visited_nr, dominator, res, pos, depth + 1, ci); + _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci); } } } @@ -602,9 +644,10 @@ static void _find_conds(ir_node *irn, long visited_nr, * 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) { @@ -613,19 +656,18 @@ static INLINE void find_conds(ir_node *irn, cond_info_t *ci) 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. @@ -634,14 +676,15 @@ static INLINE void find_conds(ir_node *irn, cond_info_t *ci) * @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 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; @@ -651,13 +694,15 @@ static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond, 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(masked_by) { assert(pos < 0); - operands[i] = make_mux_on_demand(phi, dom, masked_by, max_depth, mux, positions); + 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); } /* @@ -672,28 +717,61 @@ static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond, /* * Move the operands to the dominator block if the cond - * made sense. Some conds found are not suitable for making a mux + * 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])); - - 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]); + 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; } @@ -710,7 +788,7 @@ typedef struct _phi_info_t { * @param irn A phi node. * @param info Parameters for the if conversion algorithm. */ -static void check_out_phi(phi_info_t *phi_info, 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; ir_node *irn = phi_info->irn; @@ -718,6 +796,7 @@ static void check_out_phi(phi_info_t *phi_info, opt_if_conv_info_t *info) 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); @@ -755,12 +834,11 @@ static void check_out_phi(phi_info_t *phi_info, opt_if_conv_info_t *info) } DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom)); - make_mux_on_demand(irn, cidom, cond, max_depth, &mux, positions); + make_mux_on_demand(irn, cidom, cond, max_depth, &mux, positions, &muxes_made, ++cond_visited_nr); if(mux) { - bitset_foreach(positions, pos) { + bitset_foreach(positions, pos) set_irn_n(irn, (int) pos, mux); - } } } @@ -771,6 +849,8 @@ static void check_out_phi(phi_info_t *phi_info, opt_if_conv_info_t *info) nw = optimize_in_place_2(irn); if(nw != irn) exchange(irn, nw); + + return muxes_made; } typedef struct _cond_walk_info_t { @@ -804,6 +884,8 @@ static void annotate_cond_info_post(ir_node *irn, void *data) 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); @@ -835,7 +917,7 @@ static void annotate_cond_info_post(ir_node *irn, void *data) } else - DBG((dbg, LEVEL_2, "conds already computed for %n\n", irn)); + DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi)); set_irn_link(block, ci); @@ -895,21 +977,9 @@ static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi) } } -#if 0 -/** - * Free the sets which are put at some blocks. - */ -static void free_sets(ir_node *irn, void *data) -{ - if(is_Block(irn) && get_irn_link(irn)) { - set *conds = get_irn_link(irn); - del_set(conds); - } -} -#endif - 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; @@ -929,13 +999,13 @@ void opt_if_conv(ir_graph *irg, opt_if_conv_info_t *params) /* Init the debug stuff. */ dbg = firm_dbg_register("firm.opt.ifconv"); #if 0 - firm_dbg_set_mask(dbg, LEVEL_1 | LEVEL_2 | LEVEL_3); + firm_dbg_set_mask(dbg, LEVEL_1); #endif /* Ensure, that the dominators are computed. */ compute_doms(irg); - DBG((dbg, LEVEL_2, "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)); /* @@ -953,13 +1023,15 @@ void opt_if_conv(ir_graph *irg, opt_if_conv_info_t *params) /* Process each suitable phi found. */ list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) { - DBG((dbg, LEVEL_4, "phi node %n\n", phi_info->irn)); - check_out_phi(phi_info, p); + 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); } + DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made)); + obstack_free(&obst, NULL); }