3 * File name: ir/opt/ifconv.c
4 * Purpose: If conversion
5 * Author: Sebastian Hack.
8 * Copyright: (c) 1998-2005 Universität Karlsruhe
9 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
43 DEBUG_ONLY(firm_dbg_module_t *dbg);
45 static ir_node* walk_to_projx(ir_node* start)
49 pred = get_nodes_block(start);
51 /* if there are multiple control flow predecessors nothing sensible can be
53 if (get_irn_arity(pred) > 1) return NULL;
55 pred = get_irn_n(pred, 0);
56 if (get_irn_op(pred) == op_Proj) {
57 assert(get_irn_mode(pred) == mode_X);
65 * Additional block info.
67 typedef struct block_info {
68 ir_node *phi; /**< head of the Phi list */
69 int has_pinned; /**< set if the block contains instructions that cannot be moved */
72 #define get_block_blockinfo(block) ((block_info *)get_irn_link(block))
75 * Returns non-zero if a Block can be emptied.
77 static int can_empty_block(ir_node *block)
79 return !get_block_blockinfo(block)->has_pinned;
84 * Copies the DAG starting at node to the ith predecessor block of src_block
85 * -if the node isn't in the src_block, this is a nop and the node is returned
86 * -if the node is a phi in the src_block, the ith predecessor of the phi is
88 * otherwise returns the copy of the passed node
90 static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
97 if (get_nodes_block(node) != src_block) return node;
98 if (get_irn_op(node) == op_Phi) return get_irn_n(node, i);
100 copy_irn_to_irg(node, current_ir_graph);
101 copy = get_irn_link(node);
102 dst_block = get_nodes_block(get_irn_n(src_block, i));
103 set_nodes_block(copy, dst_block);
105 DB((dbg, LEVEL_1, "Copying node %+F to block %+F, copy is %+F\n",
106 node, dst_block, copy));
108 arity = get_irn_arity(node);
109 for (j = 0; j < arity; ++j) {
110 set_irn_n(copy, j, copy_to(get_irn_n(node, j), src_block, i));
111 DB((dbg, LEVEL_2, "-- pred %d is %+F\n", j, get_irn_n(copy, j)));
118 * Duplicate and move the contents of ith block predecessor into its
119 * predecessors if the block has multiple control dependencies and only one
121 * Also bail out if the block contains non-movable nodes, because later
122 * if-conversion would be pointless.
124 static int fission_block(ir_node* block, int i)
126 ir_node* pred = get_irn_n(block, i);
135 if (get_irn_op(pred) != op_Jmp) return 0;
136 pred_block = get_nodes_block(pred);
138 if (!has_multiple_cdep(pred_block)) return 0;
139 if (!can_empty_block(pred_block)) return 0;
141 DB((dbg, LEVEL_1, "Fissioning block %+F\n", pred_block));
143 pred_arity = get_irn_arity(pred_block);
144 arity = get_irn_arity(block);
145 info = get_block_blockinfo(block);
146 NEW_ARR_A(ir_node *, ins, arity + pred_arity - 1);
147 for (phi = info->phi; phi != NULL; phi = get_irn_link(phi)) {
148 for (j = 0; j < i; ++j) ins[j] = get_irn_n(phi, j);
149 for (j = 0; j < pred_arity; ++j) {
150 ins[i + j] = copy_to(get_irn_n(phi, i), pred_block, j);
152 for (j = i + 1; j < arity; ++j) {
153 ins[pred_arity - 1 + j] = get_irn_n(phi, j);
155 set_irn_in(phi, arity + pred_arity - 1, ins);
157 for (j = 0; j < i; ++j) ins[j] = get_irn_n(block, j);
158 for (j = 0; j < pred_arity; ++j) ins[i + j] = get_irn_n(pred_block, j);
159 for (j = i + 1; j < arity; ++j) ins[pred_arity - 1 + j] = get_irn_n(block, j);
160 set_irn_in(block, arity + pred_arity - 1, ins);
162 /* Kill all Phis in the fissioned block
163 * This is to make sure they're not kept alive
165 info = get_block_blockinfo(pred_block);
167 while (phi != NULL) {
168 ir_node* next = get_irn_link(phi);
169 exchange(phi, new_Bad());
177 * Remove predecessors i and j from node and add predecessor new_pred
179 static void rewire(ir_node* node, int i, int j, ir_node* new_pred)
181 int arity = get_irn_arity(node);
186 NEW_ARR_A(ir_node *, ins, arity - 1);
189 for (k = 0; k < i; ++k) ins[l++] = get_irn_n(node, k);
190 for (++k; k < j; ++k) ins[l++] = get_irn_n(node, k);
191 for (++k; k < arity; ++k) ins[l++] = get_irn_n(node, k);
193 assert(l == arity - 1);
194 set_irn_in(node, l, ins);
198 static void if_conv_walker(ir_node* block, void* env)
204 /* Bail out, if there are no Phis at all */
205 if (get_block_blockinfo(block)->phi == NULL) return;
208 arity = get_irn_arity(block);
209 for (i = 0; i < arity; ++i) {
210 if (fission_block(block, i)) goto restart;
214 arity = get_irn_arity(block);
215 for (i = 0; i < arity; ++i) {
221 projx0 = walk_to_projx(get_irn_n(block, i));
222 if (projx0 == NULL) return;
223 pred = get_Proj_pred(projx0);
224 if (get_irn_op(pred) != op_Cond || get_irn_mode(get_Cond_selector(pred)) != mode_b) continue;
227 if (!can_empty_block(get_nodes_block(get_irn_n(block, i)))) {
228 DB((dbg, LEVEL_1, "Cannot empty block %+F\n",
229 get_nodes_block(get_irn_n(block, i))
234 for (j = i + 1; j < arity; ++j) {
241 projx1 = walk_to_projx(get_irn_n(block, j));
242 if (projx1 == NULL) continue;
243 pred = get_Proj_pred(projx1);
244 if (get_irn_op(pred) != op_Cond || get_irn_mode(get_Cond_selector(pred)) != mode_b) continue;
245 if (pred != cond) continue;
246 DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n", cond, projx0, projx1));
248 if (!can_empty_block(get_nodes_block(get_irn_n(block, j)))) {
249 DB((dbg, LEVEL_1, "Cannot empty %+F\n", get_nodes_block(get_irn_n(block, j))));
253 conds[0] = get_Cond_selector(cond);
255 psi_block = get_nodes_block(cond);
256 phi = get_block_blockinfo(block)->phi;
258 ir_node* val_i = get_irn_n(phi, i);
259 ir_node* val_j = get_irn_n(phi, j);
261 if (val_i == val_j) {
263 DB((dbg, LEVEL_2, "Generating no psi, because both values are equal\n"));
265 /* Something is very fishy if two predecessors of a PhiM point into
266 * one block, but not at the same memory node
268 assert(get_irn_mode(phi) != mode_M);
269 if (get_Proj_proj(projx0) == pn_Cond_true) {
277 current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
279 DB((dbg, LEVEL_2, "Generating %+F for %+F\n", psi, phi));
285 rewire(phi, i, j, psi);
288 phi = get_irn_link(phi);
289 } while (phi != NULL);
291 exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
292 exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
295 DB((dbg, LEVEL_1, "Welding block %+F to %+F\n", block, psi_block));
296 get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
297 exchange(block, psi_block);
300 rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block));
308 * Block walker: add additional data
310 static void init_block_link(ir_node *block, void *env)
312 struct obstack *obst = env;
313 block_info *bi = obstack_alloc(obst, sizeof(*bi));
317 set_irn_link(block, bi);
322 * Daisy-chain all phis in a block
323 * If a non-movable node is encountered set the has_pinned flag
325 static void collect_phis(ir_node *node, void *env)
328 ir_node *block = get_nodes_block(node);
329 block_info *bi = get_block_blockinfo(block);
331 set_irn_link(node, bi->phi);
335 if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
337 * Ignore control flow nodes, these will be removed.
338 * This ignores Raise. That is surely bad. FIXME.
340 if (! is_cfop(node)) {
341 ir_node *block = get_nodes_block(node);
342 block_info *bi = get_block_blockinfo(block);
344 DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
353 * Transform multiple cascaded Psis into one Psi
355 static ir_node* fold_psi(ir_node* psi)
357 int arity = get_Psi_n_conds(psi);
368 for (i = 0; i < arity; ++i) {
369 n = get_Psi_val(psi, i);
370 if (get_irn_op(n) == op_Psi) {
371 new_arity += get_Psi_n_conds(n) + 1;
376 n = get_Psi_default(psi);
377 if (get_irn_op(n) == op_Psi) {
378 new_arity += get_Psi_n_conds(n);
381 if (arity == new_arity) return psi; // no attached Psis found
382 DB((dbg, LEVEL_1, "Folding %+F from %d to %d conds\n", psi, arity, new_arity));
384 NEW_ARR_A(ir_node *, conds, new_arity);
385 NEW_ARR_A(ir_node *, vals, new_arity + 1);
387 for (i = 0; i < arity; ++i) {
388 ir_node* c = get_Psi_cond(psi, i);
390 n = get_Psi_val(psi, i);
391 if (get_irn_op(n) == op_Psi) {
392 a = get_Psi_n_conds(n);
393 for (k = 0; k < a; ++k) {
394 conds[j] = new_r_And(
395 current_ir_graph, get_nodes_block(psi),
396 c, get_Psi_cond(n, k), mode_b
398 vals[j] = get_Psi_val(n, k);
402 vals[j] = get_Psi_default(n);
409 n = get_Psi_default(psi);
410 if (get_irn_op(n) == op_Psi) {
411 a = get_Psi_n_conds(n);
412 for (k = 0; k < a; ++k) {
413 conds[j] = get_Psi_cond(n, k);
414 vals[j] = get_Psi_val(n, k);
417 vals[j] = get_Psi_default(n);
421 assert(j == new_arity);
423 current_ir_graph, get_nodes_block(psi),
424 new_arity, conds, vals, get_irn_mode(psi)
426 DB((dbg, LEVEL_1, "Folded %+F into new %+F\n", psi, new_psi));
427 exchange(psi, new_psi);
433 * Merge consecutive psi inputs if the data inputs are the same
435 static ir_node* meld_psi(ir_node* psi)
437 int arity = get_Psi_n_conds(psi);
448 val = get_Psi_val(psi, 0);
449 DB((dbg, LEVEL_1, "Pred 0 of %+F is %+F\n", psi, val));
450 for (i = 1; i < arity; ++i) {
451 ir_node* v = get_Psi_val(psi, i);
452 DB((dbg, LEVEL_1, "Pred %2d of %+F is %+F\n", i, psi, v));
458 DB((dbg, LEVEL_1, "Default of %+F is %+F\n", psi, get_Psi_default(psi)));
459 if (val == get_Psi_default(psi)) --new_arity;
461 DB((dbg, LEVEL_1, "Melding Psi %+F from %d conds to %d\n", psi, arity, new_arity));
463 if (new_arity == arity) return psi;
465 /* If all data inputs of the Psi are equal, exchange the Psi with that value */
466 if (new_arity == 0) {
471 NEW_ARR_A(ir_node *, conds, new_arity);
472 NEW_ARR_A(ir_node *, vals, new_arity + 1);
473 cond = get_Psi_cond(psi, 0);
474 val = get_Psi_val(psi, 0);
476 for (i = 1; i < arity; ++i) {
477 ir_node* v = get_Psi_val(psi, i);
481 current_ir_graph, get_nodes_block(psi),
482 cond, get_Psi_cond(psi, i), mode_b
491 if (val != get_Psi_default(psi)) {
496 vals[j] = get_Psi_default(psi);
497 assert(j == new_arity);
499 current_ir_graph, get_nodes_block(psi),
500 new_arity, conds, vals, get_irn_mode(psi)
502 DB((dbg, LEVEL_1, "Molded %+F into %+F\n", psi, new_psi));
503 exchange(psi, new_psi);
509 * Split a Psi with multiple conditions into multiple Psis with one condtition
512 static ir_node* split_psi(ir_node* psi)
514 int arity = get_Psi_n_conds(psi);
520 if (arity == 1) return psi;
522 mode = get_irn_mode(psi);
523 block = get_nodes_block(psi);
524 rval = get_Psi_default(psi);
525 for (i = arity - 1; i >= 0; --i) {
529 conds[0] = get_Psi_cond(psi, i);
530 vals[0] = get_Psi_val(psi, i);
533 current_ir_graph, block, 1, conds, vals, mode
541 static void optimise_psis(ir_node* node, void* env)
543 if (get_irn_op(node) != op_Psi) return;
545 node = fold_psi(node);
548 node = meld_psi(node);
551 node = split_psi(node);
556 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
560 if (!get_opt_if_conversion())
563 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
565 DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
567 dump_ir_block_graph(irg, "_00_pre");
569 normalize_one_return(irg);
570 remove_critical_cf_edges(irg);
572 dump_ir_block_graph(irg, "_01_normal");
578 irg_block_walk_graph(irg, init_block_link, NULL, &obst);
579 irg_walk_graph(irg, collect_phis, NULL, NULL);
580 irg_block_walk_graph(irg, NULL, if_conv_walker, NULL);
582 local_optimize_graph(irg);
583 dump_ir_block_graph(irg, "_02_ifconv");
585 irg_walk_graph(irg, NULL, optimise_psis, NULL);
587 dump_ir_block_graph(irg, "_03_postifconv");
589 obstack_free(&obst, NULL);
600 * Make Mux nodes from Conds where it its possible.
601 * @author Sebastian Hack
618 #include "irgraph_t.h"
619 #include "irnode_t.h"
623 #include "irmode_t.h"
624 #include "ircons_t.h"
629 #include "irflag_t.h"
631 #include "irprintf.h"
636 #include "bitfiddle.h"
643 * check, if a node is const and return its tarval or
644 * return a default tarval.
645 * @param cnst The node whose tarval to get.
646 * @param or The alternative tarval, if the node is no Const.
647 * @return The tarval of @p cnst, if the node is Const, @p otherwise.
649 static tarval *get_value_or(ir_node *cnst, tarval *or)
651 return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
656 * Try to optimize nested muxes into a dis- or conjunction
658 * @param mux The parent mux, which has muxes as operands.
659 * @return The replacement node for this mux. If the optimization is
660 * successful, this might be an And or Or node, if not, its the mux
663 static ir_node *optimize_mux_chain(ir_node *mux)
668 ir_mode *mode = get_irn_mode(mux);
673 * If we have no mux, or its mode is not integer, we
676 if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
680 null = get_mode_null(mode);
681 minus_one = tarval_sub(null, get_tarval_one(mode));
683 ops[0] = get_Mux_false(mux);
684 ops[1] = get_Mux_true(mux);
686 for(i = 0; i < 2; ++i) {
688 tarval *tva, *tvb, *tvd;
692 * A mux operand at the first position can be factored
693 * out, if the operands fulfill several conditions:
695 * mux(c1, mux(c2, a, b), d)
697 * This can be made into:
698 * 1) mux(c1, 0, d) | mux(c2, a, b)
699 * if a | d == d and b | d == d
701 * 2) mux(c1, -1, d) & mux(c2, a, b)
702 * if a & d == d and a & b == b
704 if(get_irn_op(ops[i]) == op_Mux) {
707 a = get_Mux_false(child_mux);
708 b = get_Mux_true(child_mux);
711 /* Try the or stuff */
712 tva = get_value_or(a, minus_one);
713 tvb = get_value_or(b, minus_one);
714 tvd = get_value_or(d, null);
716 if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
717 && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
719 ops[i] = new_Const(mode, null);
720 res = new_r_Or(current_ir_graph, get_nodes_block(mux),
721 mux, child_mux, mode);
725 /* If the or didn't go, try the and stuff */
726 tva = get_value_or(a, null);
727 tvb = get_value_or(b, null);
728 tvd = get_value_or(d, minus_one);
730 if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
731 && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
733 ops[i] = new_Const(mode, minus_one);
734 res = new_r_And(current_ir_graph, get_nodes_block(mux),
735 mux, child_mux, mode);
741 /* recursively optimize nested muxes. */
742 set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
743 set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
749 /***********************************************************
750 * The If conversion itself.
751 ***********************************************************/
753 /** allow every Mux to be created. */
754 static int default_allow_mux(ir_node *sel, ir_node *false_res, ir_node *true_res) {
761 static const opt_if_conv_info_t default_info = {
766 /** The debugging module. */
767 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
770 * A simple check for side effects upto an opcode of a ir node.
771 * @param irn The ir node to check,
772 * @return 1 if the opcode itself may produce side effects, 0 if not.
774 static INLINE int has_side_effects(const ir_node *irn)
776 ir_op *op = get_irn_op(irn);
781 return !mode_is_datab(get_irn_mode(irn));
785 * Possible failure reasons
787 enum failure_reason_t {
788 SUCCESS = IF_RESULT_SUCCESS,
789 TO_DEEP = IF_RESULT_TOO_DEEP,
790 SIDE_EFFECTS = IF_RESULT_SIDE_EFFECT,
791 PHI_FOUND = IF_RESULT_SIDE_EFFECT_PHI,
792 DENIED = IF_RESULT_DENIED
796 * Decides, if a given expression and its subexpressions
797 * (to certain, also given extent) can be moved to a block.
799 * @param expr The expression to examine.
800 * @param block The block where the expression should go.
801 * @param depth The current depth, passed recursively. Use 0 for
802 * non-recursive calls.
803 * @param info The options for createing Mux nodes.
806 * @return a failure reason
808 static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, const opt_if_conv_info_t *info)
812 ir_node *expr_block = get_nodes_block(expr);
815 * If we are forced to look too deep into the expression,
816 * treat it like it could not be moved.
818 if(depth >= info->max_depth) {
824 * If the block of the expression dominates the specified
825 * destination block, it does not matter if the expression
826 * has side effects or anything else. It is executed on each
827 * path the destination block is reached.
829 if (block_dominates(expr_block, dest_block))
833 * We cannot move phis!
841 * This should be superfluous and could be converted into a assertion.
842 * The destination block _must_ dominate the block of the expression,
843 * else the expression could be used without its definition.
845 if (! block_dominates(dest_block, expr_block)) {
846 res = IF_RESULT_SIDE_EFFECT;
851 * Surely, if the expression does not have a data mode, it is not
852 * movable. Perhaps one should also test the floating property of
855 if (has_side_effects(expr)) {
856 res = IF_RESULT_SIDE_EFFECT;
861 * If the node looks alright so far, look at its operands and
862 * check them out. If one of them cannot be moved, this one
863 * cannot be moved either.
865 for (i = 0, n = get_irn_arity(expr); i < n; ++i) {
866 ir_node *op = get_irn_n(expr, i);
867 int new_depth = is_Proj(op) ? depth : depth + 1;
869 res = _can_move_to(op, dest_block, new_depth, info);
876 DBG((dbg, LEVEL_3, "\t\t\tcan move to %n: %d\n", expr, res));
882 * Convenience function for _can_move_to.
883 * Checks, if an expression can be moved to another block. The check can
884 * be limited to a expression depth meaning if we need to crawl in
885 * deeper into an expression than a given threshold to examine if
886 * it can be moved, the expression is rejected and the test returns
889 * @param expr The expression to check for.
890 * @param dest_block The destination block you want @p expr to be.
891 * @param info The options for createing Mux nodes.
893 * @return return a failure reason
895 static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, const opt_if_conv_info_t *info)
897 return _can_move_to(expr, dest_block, 0, info);
901 * move a DAG given by a root node expr into a new block
903 * @param expr the root of a dag
904 * @param dest_block the destination block
906 static void move_to(ir_node *expr, ir_node *dest_block)
909 ir_node *expr_block = get_nodes_block(expr);
912 * If we reached the dominator, we are done.
913 * We will never put code through the dominator
915 if (block_dominates(expr_block, dest_block))
918 for (i = 0, n = get_irn_arity(expr); i < n; ++i)
919 move_to(get_irn_n(expr, i), dest_block);
921 set_nodes_block(expr, dest_block);
925 * return the common dominator of two blocks
927 static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2)
929 if(block_dominates(b1, b2))
931 else if(block_dominates(b2, b1))
936 for (p = get_Block_idom(b1); !block_dominates(p, b2); p = get_Block_idom(p));
942 * Information about a cond node.
944 typedef struct _cond_t {
945 ir_node *cond; /**< The cond node. */
946 struct list_head list; /**< List head which is used for queuing this cond
947 into the cond bunch it belongs to. */
949 unsigned totally_covers : 1;
950 struct _cond_t *link;
954 * Information about the both 'branches'
955 * (true and false), the cond creates.
958 int pos; /**< Number of the predecessor of the
959 phi block by which this branch is
960 reached. It is -1, if this branch is
961 only reached through another cond. */
963 struct _cond_t *masked_by; /**< If this cond's branch is only reached
964 through another cond, we store this
965 cond ir_node here. */
970 * retrieve the conditional information from a Cond node
972 static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
977 return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
981 typedef void (cond_walker_t)(cond_t *cond, void *env);
983 static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
984 long visited_nr, void *env)
988 if(cond->visited_nr >= visited_nr)
991 cond->visited_nr = visited_nr;
996 for(i = 0; i < 2; ++i) {
997 cond_t *c = cond->cases[i].masked_by;
1000 _walk_conds(c, pre, post, visited_nr, env);
1007 static long cond_visited_nr = 0;
1009 static void walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post, void *env)
1011 _walk_conds(cond, pre, post, ++cond_visited_nr, env);
1014 static void link_conds(cond_t *cond, void *env)
1016 cond_t **ptr = (cond_t **) env;
1023 * Compare two conds for use in a firm set.
1024 * Two cond_t's are equal, if they designate the same cond node.
1025 * @param a A cond_t.
1026 * @param b Another one.
1027 * @param size Not used.
1028 * @return 0 (!) if they are equal, != 0 otherwise.
1030 static int cond_cmp(const void *a, const void *b, size_t size)
1032 const cond_t *x = a;
1033 const cond_t *y = b;
1034 return x->cond != y->cond;
1038 * Information about conds which can be made to muxes.
1039 * Instances of this struct are attached to the link field of
1040 * blocks in which phis are located.
1042 typedef struct _cond_info_t {
1043 struct list_head list; /**< Used to list all of these structs per class. */
1045 struct list_head roots; /**< A list of non-depending Conds. Two Conds are
1046 independent, if it's not possible not reach one from the
1047 other (all Conds in this list have to dominate the
1048 block this struct is attached to). */
1050 ir_node *first_phi; /**< The first phi node this cond info was made for. */
1051 set *cond_set; /**< A set of all dominating reachable Conds. */
1057 static void _find_conds(ir_node *irn, unsigned long visited_nr,
1058 ir_node *dominator, cond_t *masked_by, int pos, int depth, cond_info_t *ci)
1061 int saw_select_cond = 0;
1063 block = get_nodes_block(irn);
1066 * Only check this block if it is dominated by the specified
1067 * dominator or it has not been visited yet.
1069 if (block_dominates(dominator, block) && get_Block_block_visited(block) < visited_nr) {
1070 cond_t *res = masked_by;
1073 /* check, if we're on a ProjX
1075 * Further, the ProjX/Cond block must dominate the base block
1076 * (the block with the phi in it), otherwise, the Cond
1077 * is not affecting the phi so that a mux can be inserted.
1079 if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
1081 int proj = get_Proj_proj(irn);
1082 ir_node *cond = get_Proj_pred(irn);
1084 /* true, if the mode is a mode_b cond _NO_ switch cond */
1085 int is_modeb_cond = get_irn_opcode(cond) == iro_Cond
1086 && get_irn_mode(get_Cond_selector(cond)) == mode_b;
1088 saw_select_cond = !is_modeb_cond;
1090 /* Check, if the pred of the proj is a Cond
1091 * with a Projb as selector.
1096 memset(&c, 0, sizeof(c));
1099 c.cases[0].pos = -1;
1100 c.cases[1].pos = -1;
1102 /* get or insert the cond info into the set. */
1103 res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
1106 * If this cond is already masked by the masked_by cond
1107 * return immediately, since we don't have anything to add.
1109 if(masked_by && res->cases[proj].masked_by == masked_by)
1114 list_add(&res->list, &ci->roots);
1118 * Set masked by (either NULL or another cond node.
1119 * If this cond is truly masked by another one, set
1120 * the position of the actually investigated branch
1121 * to -1. Since the cond is masked by another one,
1122 * there could be more ways from the start block
1123 * to this branch, so we choose -1.
1125 res->cases[proj].masked_by = masked_by;
1128 res->cases[proj].pos = pos;
1131 * Since the masked_by nodes masks a cond, remove it from the
1132 * root list of the conf trees.
1135 assert(res->cases[proj].pos < 0);
1136 list_del_init(&masked_by->list);
1139 DBG((dbg, LEVEL_2, "%n (%s branch) "
1140 "for pos %d in block %n reached by %n\n",
1141 cond, proj ? "true" : "false", pos,
1142 block, masked_by ? masked_by->cond : NULL));
1146 if(get_Block_block_visited(block) < visited_nr && !saw_select_cond) {
1148 set_Block_block_visited(block, visited_nr);
1150 /* Search recursively from this cond. */
1151 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1152 ir_node *pred = get_irn_n(block, i);
1155 * If the depth is 0 (the first recursion), we set the pos to
1156 * the current viewed predecessor, else we adopt the position
1157 * as given by the caller. We also increase the depth for the
1158 * recursively called functions.
1160 _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci);
1168 * A convenience function for _find_conds.
1169 * It sets some parameters needed for recursion to appropriate start
1170 * values. Always use this function.
1172 * @param irn The node to start looking for Conds from. This might
1173 * be the phi node we are investigating.
1174 * @param conds The set to record the found Conds in.
1176 static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
1179 unsigned long visited_nr;
1180 ir_node *block = get_nodes_block(irn);
1181 ir_node *dom = get_Block_idom(block);
1183 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1184 ir_node *pred = get_irn_n(block, i);
1186 inc_irg_block_visited(current_ir_graph);
1187 visited_nr = get_irg_block_visited(current_ir_graph);
1188 set_Block_block_visited(block, visited_nr);
1190 DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
1191 _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
1196 * Make the mux for a given cond.
1198 * @param phi The phi node which shall be replaced by a mux.
1199 * @param dom The block where the muxes shall be placed.
1200 * @param cond The cond information.
1201 * @param info The options for createing Mux nodes.
1202 * @return The mux node made for this cond.
1204 static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond,
1205 const opt_if_conv_info_t *info, ir_node **mux, bitset_t *positions,
1206 int *muxes_made, long visited_nr)
1209 ir_node *projb = get_Cond_selector(cond->cond);
1210 ir_node *bl = get_nodes_block(cond->cond);
1211 ir_node *operands[2];
1214 cond->visited_nr = visited_nr;
1215 DBG((dbg, LEVEL_2, "%n\n", cond->cond));
1216 for(i = 0; i < 2; ++i) {
1217 cond_t *masked_by = cond->cases[i].masked_by;
1218 int pos = cond->cases[i].pos;
1224 * If this Cond branch is masked by another cond, make the mux
1225 * for that Cond first, since the Mux for this cond takes
1230 DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
1231 if(masked_by->visited_nr < visited_nr)
1232 operands[i] = make_mux_on_demand(phi, dom, masked_by, info, mux, positions, muxes_made, visited_nr);
1236 * If this cond branch is not masked by another cond, take
1237 * the corresponding phi operand as an operand to the mux.
1240 operands[i] = get_irn_n(phi, pos);
1246 * Move the operands to the dominator block if the cond
1247 * made sense. Some Conds found are not suitable for making a mux
1248 * out of them, since one of their branches cannot be reached from
1249 * the phi block. In that case we do not make a mux and return NULL.
1251 if(operands[0] && operands[1]) {
1252 if (operands[0] == operands[1]) {
1253 /* there is no gain in using mux in this case, as
1254 it will be optimized away. We will NOT move the
1255 content of the blocks either
1257 for (i = 0; i < 2; ++i)
1259 bitset_set(positions, set[i]);
1265 can_move[0] = can_move_to(operands[0], bl, info);
1266 can_move[1] = can_move_to(operands[1], bl, info);
1268 if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) {
1269 if (info->allow_mux(projb, operands[0], operands[1])) {
1270 move_to(operands[0], bl);
1271 move_to(operands[1], bl);
1274 *mux = new_r_Mux(current_ir_graph, bl, projb,
1275 operands[0], operands[1], get_irn_mode(operands[0]));
1279 DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
1280 *mux, projb, operands[0], operands[1], set[0], set[1]));
1282 for(i = 0; i < 2; ++i)
1284 bitset_set(positions, set[i]);
1286 /* we have done one */
1287 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_SUCCESS);
1291 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_DENIED);
1295 if(can_move[0] != SUCCESS)
1296 hook_if_conversion(current_ir_graph, phi, set[0], NULL, can_move[0]);
1297 if(can_move[1] != SUCCESS)
1298 hook_if_conversion(current_ir_graph, phi, set[1], NULL, can_move[1]);
1303 hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF);
1305 hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF);
1311 typedef struct _phi_info_t {
1312 struct list_head list;
1313 cond_info_t *cond_info;
1319 * Examine a phi node if it can be replaced by some muxes.
1320 * @param irn A phi node.
1321 * @param info Parameters for the if conversion algorithm.
1323 static int check_out_phi(phi_info_t *phi_info, const opt_if_conv_info_t *info)
1325 ir_node *irn = phi_info->irn;
1326 ir_node *block, *nw;
1327 cond_info_t *cond_info = phi_info->cond_info;
1331 bitset_t *positions;
1333 block = get_nodes_block(irn);
1334 arity = get_irn_arity(irn);
1335 positions = bitset_alloca(arity);
1337 assert(is_Phi(irn));
1338 assert(get_irn_arity(irn) == get_irn_arity(block));
1341 DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
1343 list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
1344 ir_node *cidom = block;
1345 ir_node *mux = NULL;
1346 cond_t *p, *head = NULL;
1349 bitset_clear_all(positions);
1351 DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
1353 * Link all conds which are in the subtree of
1354 * the current cond in the list together.
1356 walk_conds(cond, link_conds, NULL, &head);
1359 for(p = head; p; p = p->link) {
1360 for(i = 0; i < 2; ++i) {
1361 int pos = p->cases[i].pos;
1363 cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
1367 DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
1368 make_mux_on_demand(irn, cidom, cond, info, &mux, positions, &muxes_made, ++cond_visited_nr);
1371 bitset_foreach(positions, pos)
1372 set_irn_n(irn, (int) pos, mux);
1377 * optimize the phi away. This can anable further runs of this
1378 * function. Look at _can_move. phis cannot be moved there.
1380 nw = optimize_in_place_2(irn);
1387 typedef struct _cond_walk_info_t {
1388 struct obstack *obst;
1389 struct list_head cond_info_head;
1390 struct list_head phi_head;
1394 static void annotate_cond_info_pre(ir_node *irn, void *data)
1396 set_irn_link(irn, NULL);
1399 static void annotate_cond_info_post(ir_node *irn, void *data)
1401 cond_walk_info_t *cwi = data;
1404 * Check, if the node is a phi
1405 * we then compute a set of conds which are reachable from this
1406 * phi's block up to its dominator.
1407 * The set is attached to the blocks link field.
1409 if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
1410 ir_node *block = get_nodes_block(irn);
1412 cond_info_t *ci = get_irn_link(block);
1414 /* If the set is not yet computed, do it now. */
1416 ci = obstack_alloc(cwi->obst, sizeof(*ci));
1417 ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
1418 ci->first_phi = irn;
1420 INIT_LIST_HEAD(&ci->roots);
1421 INIT_LIST_HEAD(&ci->list);
1424 * Add this cond info to the list of all cond infos
1425 * in this graph. This is just done to xfree the
1426 * set easier afterwards (we save an irg_walk_graph).
1428 list_add(&cwi->cond_info_head, &ci->list);
1430 DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
1433 * Fill the set with conds we find on the way from
1434 * the block to its dominator.
1436 find_conds(irn, ci);
1439 * If there where no suitable conds, delete the set
1440 * immediately and reset the set pointer to NULL
1442 if(set_count(ci->cond_set) == 0) {
1443 del_set(ci->cond_set);
1444 list_del(&ci->list);
1445 obstack_free(cwi->obst, ci);
1451 DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
1453 set_irn_link(block, ci);
1456 phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
1459 INIT_LIST_HEAD(&pi->list);
1460 list_add(&pi->list, &cwi->phi_head);
1466 static void dump_conds(cond_t *cond, void *env)
1471 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
1472 cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
1473 get_nodes_block(cond->cond));
1475 for(i = 0; i < 2; ++i)
1476 if(cond->cases[i].masked_by)
1477 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
1478 cond, cond->cases[i].masked_by, i);
1481 static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi)
1486 snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
1488 if((f = fopen(buf, "wt")) != NULL) {
1493 ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
1494 list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
1495 ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
1496 list_for_each_entry(cond_t, cond, &ci->roots, list) {
1497 walk_conds(cond, NULL, dump_conds, f);
1498 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
1502 list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
1503 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
1504 phi->irn, phi->irn, get_nodes_block(phi->irn));
1505 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
1511 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
1514 struct obstack obst;
1515 phi_info_t *phi_info;
1516 cond_info_t *cond_info;
1517 cond_walk_info_t cwi;
1519 opt_if_conv_info_t p;
1521 if(!get_opt_if_conversion())
1524 /* get the parameters */
1526 memcpy(&p, params, sizeof(p));
1528 memcpy(&p, &default_info, sizeof(p));
1531 p.allow_mux = default_info.allow_mux;
1533 obstack_init(&obst);
1536 INIT_LIST_HEAD(&cwi.cond_info_head);
1537 INIT_LIST_HEAD(&cwi.phi_head);
1539 /* Init the debug stuff. */
1540 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
1542 firm_dbg_set_mask(dbg, LEVEL_1|LEVEL_2|LEVEL_3);
1545 /* if-conversion works better with normalized returns */
1546 normalize_one_return(irg);
1548 /* Ensure, that the dominators are computed. */
1551 DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
1552 get_entity_name(get_irg_entity(irg)), irg));
1555 * Collect information about the conds pu the phis on an obstack.
1556 * It is important that phi nodes which are 'higher' (with a
1557 * lower dfs pre order) are in front of the obstack. Since they are
1558 * possibly turned in to muxes this can enable the optimization
1561 irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
1564 vcg_dump_conds(irg, &cwi);
1567 /* Process each suitable phi found. */
1568 list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
1569 DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
1570 muxes_made += check_out_phi(phi_info, &p);
1573 list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
1574 del_set(cond_info->cond_set);
1577 DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
1579 obstack_free(&obst, NULL);
1581 dump_ir_block_graph(irg, "_ifconv_hack");