- * 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 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, const opt_if_conv_info_t *info)
-{
- 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\tcan move to %n: %d\n", expr, res));
-
- return res;
-}
-
-/**
- * Convenience function for _can_move_to.
- * Checks, if an expression can be moved to another block. The check can
- * be limited to a expression depth meaning if we need to crawl in
- * 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 dest_block The destination block you want @p expr to be.
- * @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, const opt_if_conv_info_t *info)
-{
- 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);
-
- /*
- * 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);
-
- 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. */
- 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;
-
- 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 b Another one.
- * @param size Not used.
- * @return 0 (!) if they are equal, != 0 otherwise.
- */
-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;
-}
-
-/**
- * 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, unsigned 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);
-
- /*
- * 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.
- */
-static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
-{
- 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);
-
- 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 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,
- const opt_if_conv_info_t *info, ir_node **mux, bitset_t *positions,
- int *muxes_made, long visited_nr)
-{
- 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;
-} 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.