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 /** allow every Psi to be created. */
46 static int default_allow_mux(ir_node *sel, ir_node *false_res, ir_node *true_res) {
53 static const opt_if_conv_info_t default_info = {
54 0, /* doesn't matter for Psi */
59 * Additional block info.
61 typedef struct block_info {
62 ir_node *phi; /**< head of the Phi list */
63 int has_pinned; /**< set if the block contains instructions that cannot be moved */
66 #define get_block_blockinfo(block) ((block_info *)get_irn_link(block))
69 * Returns non-zero if a Block can be emptied.
71 static int can_empty_block(ir_node *block)
73 return !get_block_blockinfo(block)->has_pinned;
77 static ir_node* walk_to_projx(ir_node* start, const ir_node* dependency)
82 /* No need to find the conditional block if this block cannot be emptied and
85 if (!can_empty_block(start)) return NULL;
87 arity = get_irn_arity(start);
88 for (i = 0; i < arity; ++i) {
89 ir_node* pred = get_irn_n(start, i);
90 ir_node* pred_block = get_nodes_block(pred);
92 if (pred_block == dependency) {
94 assert(get_irn_mode(pred) == mode_X);
101 assert(get_irn_mode(pred) == mode_X);
105 if (is_cdep_on(pred_block, dependency)) {
106 return walk_to_projx(pred_block, dependency);
114 * Copies the DAG starting at node to the ith predecessor block of src_block
115 * -if the node isn't in the src_block, this is a nop and the node is returned
116 * -if the node is a phi in the src_block, the ith predecessor of the phi is
118 * otherwise returns the copy of the passed node
120 static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
127 if (get_nodes_block(node) != src_block) return node;
128 if (get_irn_op(node) == op_Phi) return get_irn_n(node, i);
130 copy = exact_copy(node);
131 dst_block = get_nodes_block(get_irn_n(src_block, i));
132 set_nodes_block(copy, dst_block);
134 DB((dbg, LEVEL_1, "Copying node %+F to block %+F, copy is %+F\n",
135 node, dst_block, copy));
137 arity = get_irn_arity(node);
138 for (j = 0; j < arity; ++j) {
139 set_irn_n(copy, j, copy_to(get_irn_n(node, j), src_block, i));
140 DB((dbg, LEVEL_2, "-- pred %d is %+F\n", j, get_irn_n(copy, j)));
147 * Remove predecessors i and j from node and add predecessor new_pred
149 static void rewire(ir_node* node, int i, int j, ir_node* new_pred)
151 int arity = get_irn_arity(node);
156 NEW_ARR_A(ir_node *, ins, arity - 1);
159 for (k = 0; k < i; ++k) ins[l++] = get_irn_n(node, k);
160 for (++k; k < j; ++k) ins[l++] = get_irn_n(node, k);
161 for (++k; k < arity; ++k) ins[l++] = get_irn_n(node, k);
163 assert(l == arity - 1);
164 set_irn_in(node, l, ins);
169 * Remove the jth predecessors from the ith predecessor of block and add it to block
171 static void split_block(ir_node* block, int i, int j)
173 ir_node* pred_block = get_nodes_block(get_irn_n(block, i));
174 int arity = get_irn_arity(block);
181 DB((dbg, LEVEL_1, "Splitting predecessor %d of predecessor %d of %+F\n", j, i, block));
183 NEW_ARR_A(ir_node*, ins, arity + 1);
185 for (phi = get_block_blockinfo(block)->phi; phi != NULL; phi = get_irn_link(phi)) {
186 ir_node* copy = copy_to(get_irn_n(phi, i), pred_block, j);
188 for (k = 0; k < i; ++k) ins[k] = get_irn_n(phi, k);
190 for (; k < arity; ++k) ins[k] = get_irn_n(phi, k);
191 ins[k] = get_irn_n(phi, i);
193 set_irn_in(phi, arity + 1, ins);
196 for (k = 0; k < i; ++k) ins[k] = get_irn_n(block, k);
197 ins[k++] = get_irn_n(pred_block, j);
198 for (; k < arity; ++k) ins[k] = get_irn_n(block, k);
199 ins[k] = get_irn_n(block, i);
201 set_irn_in(block, arity + 1, ins);
203 new_pred_arity = get_irn_arity(pred_block) - 1;
204 NEW_ARR_A(ir_node*, pred_ins, new_pred_arity);
206 for (phi = get_block_blockinfo(pred_block)->phi; phi != NULL; phi = get_irn_link(phi)) {
207 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(phi, k);
208 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(phi, k + 1);
209 assert(k == new_pred_arity);
210 if (new_pred_arity > 1) {
211 set_irn_in(phi, new_pred_arity, pred_ins);
213 exchange(phi, pred_ins[0]);
217 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(pred_block, k);
218 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(pred_block, k + 1);
219 assert(k == new_pred_arity);
220 if (new_pred_arity > 1) {
221 set_irn_in(pred_block, new_pred_arity, pred_ins);
223 exchange(pred_block, get_nodes_block(pred_ins[0]));
228 static void prepare_path(ir_node* block, int i, const ir_node* dependency)
230 ir_node* pred = get_nodes_block(get_irn_n(block, i));
234 DB((dbg, LEVEL_1, "Preparing predecessor %d of %+F\n", i, block));
236 pred_arity = get_irn_arity(pred);
237 for (j = 0; j < pred_arity; ++j) {
238 ir_node* pred_pred = get_nodes_block(get_irn_n(pred, j));
240 if (is_cdep_on(pred_pred, dependency)) {
241 prepare_path(pred, j, dependency);
242 split_block(block, i, j);
249 static void if_conv_walker(ir_node* block, void* env)
253 opt_if_conv_info_t *opt_info = env;
255 /* Bail out, if there are no Phis at all */
256 if (get_block_blockinfo(block)->phi == NULL) return;
259 arity = get_irn_arity(block);
260 for (i = 0; i < arity; ++i) {
264 pred = get_nodes_block(get_irn_n(block, i));
265 for (cdep = find_cdep(pred); cdep != NULL; cdep = cdep->next) {
266 const ir_node* dependency = cdep->node;
267 ir_node* projx0 = walk_to_projx(pred, dependency);
271 if (projx0 == NULL) continue;
273 cond = get_Proj_pred(projx0);
274 if (get_irn_op(cond) != op_Cond) continue;
276 /* We only handle boolean decisions, no switches */
277 if (get_irn_mode(get_Cond_selector(cond)) != mode_b) continue;
278 if (! opt_info->allow_mux(get_Cond_selector(cond), NULL, NULL)) continue;
280 for (j = i + 1; j < arity; ++j) {
288 pred = get_nodes_block(get_irn_n(block, j));
290 if (!is_cdep_on(pred, dependency)) continue;
292 projx1 = walk_to_projx(pred, dependency);
294 if (projx1 == NULL) continue;
296 DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n",
300 prepare_path(block, i, dependency);
301 prepare_path(block, j, dependency);
302 arity = get_irn_arity(block);
304 conds[0] = get_Cond_selector(cond);
306 psi_block = get_nodes_block(cond);
307 phi = get_block_blockinfo(block)->phi;
309 ir_node* val_i = get_irn_n(phi, i);
310 ir_node* val_j = get_irn_n(phi, j);
312 if (val_i == val_j) {
314 DB((dbg, LEVEL_2, "Generating no psi, because both values are equal\n"));
316 /* Something is very fishy if two predecessors of a PhiM point into
317 * one block, but not at the same memory node
319 assert(get_irn_mode(phi) != mode_M);
320 if (get_Proj_proj(projx0) == pn_Cond_true) {
329 current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
331 DB((dbg, LEVEL_2, "Generating %+F for %+F\n", psi, phi));
334 /* only exchange if we have a Psi */
338 rewire(phi, i, j, psi);
341 phi = get_irn_link(phi);
342 } while (phi != NULL);
344 exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
345 exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
349 DB((dbg, LEVEL_1, "Welding block %+F and %+F\n", block, psi_block));
350 /* copy the block-info from the Psi-block to the block before merging */
351 get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
352 set_irn_link(block, get_irn_link(psi_block));
354 set_irn_in(block, get_irn_arity(psi_block), get_irn_in(psi_block) + 1);
355 exchange_cdep(psi_block, block);
356 exchange(psi_block, block);
358 DB((dbg, LEVEL_1, "Welding block %+F to %+F\n", block, psi_block));
359 get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
360 exchange(block, psi_block);
364 rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block));
373 * Block walker: add additional data
375 static void init_block_link(ir_node *block, void *env)
377 struct obstack *obst = env;
378 block_info *bi = obstack_alloc(obst, sizeof(*bi));
382 set_irn_link(block, bi);
387 * Daisy-chain all phis in a block
388 * If a non-movable node is encountered set the has_pinned flag
390 static void collect_phis(ir_node *node, void *env)
393 ir_node *block = get_nodes_block(node);
394 block_info *bi = get_block_blockinfo(block);
396 set_irn_link(node, bi->phi);
400 if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
402 * Ignore control flow nodes, these will be removed.
403 * This ignores Raise. That is surely bad. FIXME.
405 if (! is_cfop(node)) {
406 ir_node *block = get_nodes_block(node);
407 block_info *bi = get_block_blockinfo(block);
409 DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
418 * Transform multiple cascaded Psis into one Psi
420 static ir_node* fold_psi(ir_node* psi)
422 int arity = get_Psi_n_conds(psi);
433 for (i = 0; i < arity; ++i) {
434 n = get_Psi_val(psi, i);
435 if (get_irn_op(n) == op_Psi) {
436 new_arity += get_Psi_n_conds(n) + 1;
441 n = get_Psi_default(psi);
442 if (get_irn_op(n) == op_Psi) {
443 new_arity += get_Psi_n_conds(n);
446 if (arity == new_arity) return psi; // no attached Psis found
447 DB((dbg, LEVEL_1, "Folding %+F from %d to %d conds\n", psi, arity, new_arity));
449 NEW_ARR_A(ir_node *, conds, new_arity);
450 NEW_ARR_A(ir_node *, vals, new_arity + 1);
452 for (i = 0; i < arity; ++i) {
453 ir_node* c = get_Psi_cond(psi, i);
455 n = get_Psi_val(psi, i);
456 if (get_irn_op(n) == op_Psi) {
457 a = get_Psi_n_conds(n);
458 for (k = 0; k < a; ++k) {
459 conds[j] = new_r_And(
460 current_ir_graph, get_nodes_block(psi),
461 c, get_Psi_cond(n, k), mode_b
463 vals[j] = get_Psi_val(n, k);
467 vals[j] = get_Psi_default(n);
474 n = get_Psi_default(psi);
475 if (get_irn_op(n) == op_Psi) {
476 a = get_Psi_n_conds(n);
477 for (k = 0; k < a; ++k) {
478 conds[j] = get_Psi_cond(n, k);
479 vals[j] = get_Psi_val(n, k);
482 vals[j] = get_Psi_default(n);
486 assert(j == new_arity);
488 current_ir_graph, get_nodes_block(psi),
489 new_arity, conds, vals, get_irn_mode(psi)
491 DB((dbg, LEVEL_1, "Folded %+F into new %+F\n", psi, new_psi));
492 exchange(psi, new_psi);
498 * Merge consecutive psi inputs if the data inputs are the same
500 static ir_node* meld_psi(ir_node* psi)
502 int arity = get_Psi_n_conds(psi);
513 val = get_Psi_val(psi, 0);
514 DB((dbg, LEVEL_1, "Pred 0 of %+F is %+F\n", psi, val));
515 for (i = 1; i < arity; ++i) {
516 ir_node* v = get_Psi_val(psi, i);
517 DB((dbg, LEVEL_1, "Pred %2d of %+F is %+F\n", i, psi, v));
523 DB((dbg, LEVEL_1, "Default of %+F is %+F\n", psi, get_Psi_default(psi)));
524 if (val == get_Psi_default(psi)) --new_arity;
526 DB((dbg, LEVEL_1, "Melding Psi %+F from %d conds to %d\n", psi, arity, new_arity));
528 if (new_arity == arity) return psi;
530 /* If all data inputs of the Psi are equal, exchange the Psi with that value */
531 if (new_arity == 0) {
536 NEW_ARR_A(ir_node *, conds, new_arity);
537 NEW_ARR_A(ir_node *, vals, new_arity + 1);
538 cond = get_Psi_cond(psi, 0);
539 val = get_Psi_val(psi, 0);
541 for (i = 1; i < arity; ++i) {
542 ir_node* v = get_Psi_val(psi, i);
546 current_ir_graph, get_nodes_block(psi),
547 cond, get_Psi_cond(psi, i), mode_b
556 if (val != get_Psi_default(psi)) {
561 vals[j] = get_Psi_default(psi);
562 assert(j == new_arity);
564 current_ir_graph, get_nodes_block(psi),
565 new_arity, conds, vals, get_irn_mode(psi)
567 DB((dbg, LEVEL_1, "Molded %+F into %+F\n", psi, new_psi));
568 exchange(psi, new_psi);
574 * Split a Psi with multiple conditions into multiple Psis with one condtition
577 static ir_node* split_psi(ir_node* psi)
579 int arity = get_Psi_n_conds(psi);
585 if (arity == 1) return psi;
587 mode = get_irn_mode(psi);
588 block = get_nodes_block(psi);
589 rval = get_Psi_default(psi);
590 for (i = arity - 1; i >= 0; --i) {
594 conds[0] = get_Psi_cond(psi, i);
595 vals[0] = get_Psi_val(psi, i);
598 current_ir_graph, block, 1, conds, vals, mode
606 static void optimise_psis(ir_node* node, void* env)
608 if (get_irn_op(node) != op_Psi) return;
610 node = fold_psi(node);
613 node = meld_psi(node);
616 node = split_psi(node);
621 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
624 opt_if_conv_info_t p;
626 if (! get_opt_if_conversion())
629 /* get the parameters */
631 memcpy(&p, params, sizeof(p));
633 memcpy(&p, &default_info, sizeof(p));
635 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
637 DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
639 normalize_one_return(irg);
640 remove_critical_cf_edges(irg);
646 irg_block_walk_graph(irg, init_block_link, NULL, &obst);
647 irg_walk_graph(irg, collect_phis, NULL, NULL);
648 irg_block_walk_graph(irg, NULL, if_conv_walker, &p);
650 local_optimize_graph(irg);
652 irg_walk_graph(irg, NULL, optimise_psis, NULL);
654 obstack_free(&obst, NULL);
665 * Make Mux nodes from Conds where it its possible.
666 * @author Sebastian Hack
683 #include "irgraph_t.h"
684 #include "irnode_t.h"
688 #include "irmode_t.h"
689 #include "ircons_t.h"
694 #include "irflag_t.h"
696 #include "irprintf.h"
701 #include "bitfiddle.h"
708 * check, if a node is const and return its tarval or
709 * return a default tarval.
710 * @param cnst The node whose tarval to get.
711 * @param or The alternative tarval, if the node is no Const.
712 * @return The tarval of @p cnst, if the node is Const, @p otherwise.
714 static tarval *get_value_or(ir_node *cnst, tarval *or)
716 return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
721 * Try to optimize nested muxes into a dis- or conjunction
723 * @param mux The parent mux, which has muxes as operands.
724 * @return The replacement node for this mux. If the optimization is
725 * successful, this might be an And or Or node, if not, its the mux
728 static ir_node *optimize_mux_chain(ir_node *mux)
733 ir_mode *mode = get_irn_mode(mux);
738 * If we have no mux, or its mode is not integer, we
741 if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
745 null = get_mode_null(mode);
746 minus_one = tarval_sub(null, get_tarval_one(mode));
748 ops[0] = get_Mux_false(mux);
749 ops[1] = get_Mux_true(mux);
751 for(i = 0; i < 2; ++i) {
753 tarval *tva, *tvb, *tvd;
757 * A mux operand at the first position can be factored
758 * out, if the operands fulfill several conditions:
760 * mux(c1, mux(c2, a, b), d)
762 * This can be made into:
763 * 1) mux(c1, 0, d) | mux(c2, a, b)
764 * if a | d == d and b | d == d
766 * 2) mux(c1, -1, d) & mux(c2, a, b)
767 * if a & d == d and a & b == b
769 if(get_irn_op(ops[i]) == op_Mux) {
772 a = get_Mux_false(child_mux);
773 b = get_Mux_true(child_mux);
776 /* Try the or stuff */
777 tva = get_value_or(a, minus_one);
778 tvb = get_value_or(b, minus_one);
779 tvd = get_value_or(d, null);
781 if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
782 && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
784 ops[i] = new_Const(mode, null);
785 res = new_r_Or(current_ir_graph, get_nodes_block(mux),
786 mux, child_mux, mode);
790 /* If the or didn't go, try the and stuff */
791 tva = get_value_or(a, null);
792 tvb = get_value_or(b, null);
793 tvd = get_value_or(d, minus_one);
795 if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
796 && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
798 ops[i] = new_Const(mode, minus_one);
799 res = new_r_And(current_ir_graph, get_nodes_block(mux),
800 mux, child_mux, mode);
806 /* recursively optimize nested muxes. */
807 set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
808 set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
814 /***********************************************************
815 * The If conversion itself.
816 ***********************************************************/
818 /** allow every Mux to be created. */
819 static int default_allow_mux(ir_node *sel, ir_node *false_res, ir_node *true_res) {
826 static const opt_if_conv_info_t default_info = {
831 /** The debugging module. */
832 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
835 * A simple check for side effects upto an opcode of a ir node.
836 * @param irn The ir node to check,
837 * @return 1 if the opcode itself may produce side effects, 0 if not.
839 static INLINE int has_side_effects(const ir_node *irn)
841 ir_op *op = get_irn_op(irn);
846 return !mode_is_datab(get_irn_mode(irn));
850 * Possible failure reasons
852 enum failure_reason_t {
853 SUCCESS = IF_RESULT_SUCCESS,
854 TO_DEEP = IF_RESULT_TOO_DEEP,
855 SIDE_EFFECTS = IF_RESULT_SIDE_EFFECT,
856 PHI_FOUND = IF_RESULT_SIDE_EFFECT_PHI,
857 DENIED = IF_RESULT_DENIED
861 * Decides, if a given expression and its subexpressions
862 * (to certain, also given extent) can be moved to a block.
864 * @param expr The expression to examine.
865 * @param block The block where the expression should go.
866 * @param depth The current depth, passed recursively. Use 0 for
867 * non-recursive calls.
868 * @param info The options for createing Mux nodes.
871 * @return a failure reason
873 static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, const opt_if_conv_info_t *info)
877 ir_node *expr_block = get_nodes_block(expr);
880 * If we are forced to look too deep into the expression,
881 * treat it like it could not be moved.
883 if(depth >= info->max_depth) {
889 * If the block of the expression dominates the specified
890 * destination block, it does not matter if the expression
891 * has side effects or anything else. It is executed on each
892 * path the destination block is reached.
894 if (block_dominates(expr_block, dest_block))
898 * We cannot move phis!
906 * This should be superfluous and could be converted into a assertion.
907 * The destination block _must_ dominate the block of the expression,
908 * else the expression could be used without its definition.
910 if (! block_dominates(dest_block, expr_block)) {
911 res = IF_RESULT_SIDE_EFFECT;
916 * Surely, if the expression does not have a data mode, it is not
917 * movable. Perhaps one should also test the floating property of
920 if (has_side_effects(expr)) {
921 res = IF_RESULT_SIDE_EFFECT;
926 * If the node looks alright so far, look at its operands and
927 * check them out. If one of them cannot be moved, this one
928 * cannot be moved either.
930 for (i = 0, n = get_irn_arity(expr); i < n; ++i) {
931 ir_node *op = get_irn_n(expr, i);
932 int new_depth = is_Proj(op) ? depth : depth + 1;
934 res = _can_move_to(op, dest_block, new_depth, info);
941 DBG((dbg, LEVEL_3, "\t\t\tcan move to %n: %d\n", expr, res));
947 * Convenience function for _can_move_to.
948 * Checks, if an expression can be moved to another block. The check can
949 * be limited to a expression depth meaning if we need to crawl in
950 * deeper into an expression than a given threshold to examine if
951 * it can be moved, the expression is rejected and the test returns
954 * @param expr The expression to check for.
955 * @param dest_block The destination block you want @p expr to be.
956 * @param info The options for createing Mux nodes.
958 * @return return a failure reason
960 static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, const opt_if_conv_info_t *info)
962 return _can_move_to(expr, dest_block, 0, info);
966 * move a DAG given by a root node expr into a new block
968 * @param expr the root of a dag
969 * @param dest_block the destination block
971 static void move_to(ir_node *expr, ir_node *dest_block)
974 ir_node *expr_block = get_nodes_block(expr);
977 * If we reached the dominator, we are done.
978 * We will never put code through the dominator
980 if (block_dominates(expr_block, dest_block))
983 for (i = 0, n = get_irn_arity(expr); i < n; ++i)
984 move_to(get_irn_n(expr, i), dest_block);
986 set_nodes_block(expr, dest_block);
990 * return the common dominator of two blocks
992 static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2)
994 if(block_dominates(b1, b2))
996 else if(block_dominates(b2, b1))
1001 for (p = get_Block_idom(b1); !block_dominates(p, b2); p = get_Block_idom(p));
1007 * Information about a cond node.
1009 typedef struct _cond_t {
1010 ir_node *cond; /**< The cond node. */
1011 struct list_head list; /**< List head which is used for queuing this cond
1012 into the cond bunch it belongs to. */
1013 unsigned is_new : 1;
1014 unsigned totally_covers : 1;
1015 struct _cond_t *link;
1019 * Information about the both 'branches'
1020 * (true and false), the cond creates.
1023 int pos; /**< Number of the predecessor of the
1024 phi block by which this branch is
1025 reached. It is -1, if this branch is
1026 only reached through another cond. */
1028 struct _cond_t *masked_by; /**< If this cond's branch is only reached
1029 through another cond, we store this
1030 cond ir_node here. */
1035 * retrieve the conditional information from a Cond node
1037 static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
1042 return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
1046 typedef void (cond_walker_t)(cond_t *cond, void *env);
1048 static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
1049 long visited_nr, void *env)
1053 if(cond->visited_nr >= visited_nr)
1056 cond->visited_nr = visited_nr;
1061 for(i = 0; i < 2; ++i) {
1062 cond_t *c = cond->cases[i].masked_by;
1065 _walk_conds(c, pre, post, visited_nr, env);
1072 static long cond_visited_nr = 0;
1074 static void walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post, void *env)
1076 _walk_conds(cond, pre, post, ++cond_visited_nr, env);
1079 static void link_conds(cond_t *cond, void *env)
1081 cond_t **ptr = (cond_t **) env;
1088 * Compare two conds for use in a firm set.
1089 * Two cond_t's are equal, if they designate the same cond node.
1090 * @param a A cond_t.
1091 * @param b Another one.
1092 * @param size Not used.
1093 * @return 0 (!) if they are equal, != 0 otherwise.
1095 static int cond_cmp(const void *a, const void *b, size_t size)
1097 const cond_t *x = a;
1098 const cond_t *y = b;
1099 return x->cond != y->cond;
1103 * Information about conds which can be made to muxes.
1104 * Instances of this struct are attached to the link field of
1105 * blocks in which phis are located.
1107 typedef struct _cond_info_t {
1108 struct list_head list; /**< Used to list all of these structs per class. */
1110 struct list_head roots; /**< A list of non-depending Conds. Two Conds are
1111 independent, if it's not possible not reach one from the
1112 other (all Conds in this list have to dominate the
1113 block this struct is attached to). */
1115 ir_node *first_phi; /**< The first phi node this cond info was made for. */
1116 set *cond_set; /**< A set of all dominating reachable Conds. */
1122 static void _find_conds(ir_node *irn, unsigned long visited_nr,
1123 ir_node *dominator, cond_t *masked_by, int pos, int depth, cond_info_t *ci)
1126 int saw_select_cond = 0;
1128 block = get_nodes_block(irn);
1131 * Only check this block if it is dominated by the specified
1132 * dominator or it has not been visited yet.
1134 if (block_dominates(dominator, block) && get_Block_block_visited(block) < visited_nr) {
1135 cond_t *res = masked_by;
1138 /* check, if we're on a ProjX
1140 * Further, the ProjX/Cond block must dominate the base block
1141 * (the block with the phi in it), otherwise, the Cond
1142 * is not affecting the phi so that a mux can be inserted.
1144 if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
1146 int proj = get_Proj_proj(irn);
1147 ir_node *cond = get_Proj_pred(irn);
1149 /* true, if the mode is a mode_b cond _NO_ switch cond */
1150 int is_modeb_cond = get_irn_opcode(cond) == iro_Cond
1151 && get_irn_mode(get_Cond_selector(cond)) == mode_b;
1153 saw_select_cond = !is_modeb_cond;
1155 /* Check, if the pred of the proj is a Cond
1156 * with a Projb as selector.
1161 memset(&c, 0, sizeof(c));
1164 c.cases[0].pos = -1;
1165 c.cases[1].pos = -1;
1167 /* get or insert the cond info into the set. */
1168 res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
1171 * If this cond is already masked by the masked_by cond
1172 * return immediately, since we don't have anything to add.
1174 if(masked_by && res->cases[proj].masked_by == masked_by)
1179 list_add(&res->list, &ci->roots);
1183 * Set masked by (either NULL or another cond node.
1184 * If this cond is truly masked by another one, set
1185 * the position of the actually investigated branch
1186 * to -1. Since the cond is masked by another one,
1187 * there could be more ways from the start block
1188 * to this branch, so we choose -1.
1190 res->cases[proj].masked_by = masked_by;
1193 res->cases[proj].pos = pos;
1196 * Since the masked_by nodes masks a cond, remove it from the
1197 * root list of the conf trees.
1200 assert(res->cases[proj].pos < 0);
1201 list_del_init(&masked_by->list);
1204 DBG((dbg, LEVEL_2, "%n (%s branch) "
1205 "for pos %d in block %n reached by %n\n",
1206 cond, proj ? "true" : "false", pos,
1207 block, masked_by ? masked_by->cond : NULL));
1211 if(get_Block_block_visited(block) < visited_nr && !saw_select_cond) {
1213 set_Block_block_visited(block, visited_nr);
1215 /* Search recursively from this cond. */
1216 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1217 ir_node *pred = get_irn_n(block, i);
1220 * If the depth is 0 (the first recursion), we set the pos to
1221 * the current viewed predecessor, else we adopt the position
1222 * as given by the caller. We also increase the depth for the
1223 * recursively called functions.
1225 _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci);
1233 * A convenience function for _find_conds.
1234 * It sets some parameters needed for recursion to appropriate start
1235 * values. Always use this function.
1237 * @param irn The node to start looking for Conds from. This might
1238 * be the phi node we are investigating.
1239 * @param conds The set to record the found Conds in.
1241 static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
1244 unsigned long visited_nr;
1245 ir_node *block = get_nodes_block(irn);
1246 ir_node *dom = get_Block_idom(block);
1248 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1249 ir_node *pred = get_irn_n(block, i);
1251 inc_irg_block_visited(current_ir_graph);
1252 visited_nr = get_irg_block_visited(current_ir_graph);
1253 set_Block_block_visited(block, visited_nr);
1255 DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
1256 _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
1261 * Make the mux for a given cond.
1263 * @param phi The phi node which shall be replaced by a mux.
1264 * @param dom The block where the muxes shall be placed.
1265 * @param cond The cond information.
1266 * @param info The options for createing Mux nodes.
1267 * @return The mux node made for this cond.
1269 static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond,
1270 const opt_if_conv_info_t *info, ir_node **mux, bitset_t *positions,
1271 int *muxes_made, long visited_nr)
1274 ir_node *projb = get_Cond_selector(cond->cond);
1275 ir_node *bl = get_nodes_block(cond->cond);
1276 ir_node *operands[2];
1279 cond->visited_nr = visited_nr;
1280 DBG((dbg, LEVEL_2, "%n\n", cond->cond));
1281 for(i = 0; i < 2; ++i) {
1282 cond_t *masked_by = cond->cases[i].masked_by;
1283 int pos = cond->cases[i].pos;
1289 * If this Cond branch is masked by another cond, make the mux
1290 * for that Cond first, since the Mux for this cond takes
1295 DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
1296 if(masked_by->visited_nr < visited_nr)
1297 operands[i] = make_mux_on_demand(phi, dom, masked_by, info, mux, positions, muxes_made, visited_nr);
1301 * If this cond branch is not masked by another cond, take
1302 * the corresponding phi operand as an operand to the mux.
1305 operands[i] = get_irn_n(phi, pos);
1311 * Move the operands to the dominator block if the cond
1312 * made sense. Some Conds found are not suitable for making a mux
1313 * out of them, since one of their branches cannot be reached from
1314 * the phi block. In that case we do not make a mux and return NULL.
1316 if(operands[0] && operands[1]) {
1317 if (operands[0] == operands[1]) {
1318 /* there is no gain in using mux in this case, as
1319 it will be optimized away. We will NOT move the
1320 content of the blocks either
1322 for (i = 0; i < 2; ++i)
1324 bitset_set(positions, set[i]);
1330 can_move[0] = can_move_to(operands[0], bl, info);
1331 can_move[1] = can_move_to(operands[1], bl, info);
1333 if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) {
1334 if (info->allow_mux(projb, operands[0], operands[1])) {
1335 move_to(operands[0], bl);
1336 move_to(operands[1], bl);
1339 *mux = new_r_Mux(current_ir_graph, bl, projb,
1340 operands[0], operands[1], get_irn_mode(operands[0]));
1344 DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
1345 *mux, projb, operands[0], operands[1], set[0], set[1]));
1347 for(i = 0; i < 2; ++i)
1349 bitset_set(positions, set[i]);
1351 /* we have done one */
1352 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_SUCCESS);
1356 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_DENIED);
1360 if(can_move[0] != SUCCESS)
1361 hook_if_conversion(current_ir_graph, phi, set[0], NULL, can_move[0]);
1362 if(can_move[1] != SUCCESS)
1363 hook_if_conversion(current_ir_graph, phi, set[1], NULL, can_move[1]);
1368 hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF);
1370 hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF);
1376 typedef struct _phi_info_t {
1377 struct list_head list;
1378 cond_info_t *cond_info;
1384 * Examine a phi node if it can be replaced by some muxes.
1385 * @param irn A phi node.
1386 * @param info Parameters for the if conversion algorithm.
1388 static int check_out_phi(phi_info_t *phi_info, const opt_if_conv_info_t *info)
1390 ir_node *irn = phi_info->irn;
1391 ir_node *block, *nw;
1392 cond_info_t *cond_info = phi_info->cond_info;
1396 bitset_t *positions;
1398 block = get_nodes_block(irn);
1399 arity = get_irn_arity(irn);
1400 positions = bitset_alloca(arity);
1402 assert(is_Phi(irn));
1403 assert(get_irn_arity(irn) == get_irn_arity(block));
1406 DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
1408 list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
1409 ir_node *cidom = block;
1410 ir_node *mux = NULL;
1411 cond_t *p, *head = NULL;
1414 bitset_clear_all(positions);
1416 DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
1418 * Link all conds which are in the subtree of
1419 * the current cond in the list together.
1421 walk_conds(cond, link_conds, NULL, &head);
1424 for(p = head; p; p = p->link) {
1425 for(i = 0; i < 2; ++i) {
1426 int pos = p->cases[i].pos;
1428 cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
1432 DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
1433 make_mux_on_demand(irn, cidom, cond, info, &mux, positions, &muxes_made, ++cond_visited_nr);
1436 bitset_foreach(positions, pos)
1437 set_irn_n(irn, (int) pos, mux);
1442 * optimize the phi away. This can anable further runs of this
1443 * function. Look at _can_move. phis cannot be moved there.
1445 nw = optimize_in_place_2(irn);
1452 typedef struct _cond_walk_info_t {
1453 struct obstack *obst;
1454 struct list_head cond_info_head;
1455 struct list_head phi_head;
1459 static void annotate_cond_info_pre(ir_node *irn, void *data)
1461 set_irn_link(irn, NULL);
1464 static void annotate_cond_info_post(ir_node *irn, void *data)
1466 cond_walk_info_t *cwi = data;
1469 * Check, if the node is a phi
1470 * we then compute a set of conds which are reachable from this
1471 * phi's block up to its dominator.
1472 * The set is attached to the blocks link field.
1474 if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
1475 ir_node *block = get_nodes_block(irn);
1477 cond_info_t *ci = get_irn_link(block);
1479 /* If the set is not yet computed, do it now. */
1481 ci = obstack_alloc(cwi->obst, sizeof(*ci));
1482 ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
1483 ci->first_phi = irn;
1485 INIT_LIST_HEAD(&ci->roots);
1486 INIT_LIST_HEAD(&ci->list);
1489 * Add this cond info to the list of all cond infos
1490 * in this graph. This is just done to xfree the
1491 * set easier afterwards (we save an irg_walk_graph).
1493 list_add(&cwi->cond_info_head, &ci->list);
1495 DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
1498 * Fill the set with conds we find on the way from
1499 * the block to its dominator.
1501 find_conds(irn, ci);
1504 * If there where no suitable conds, delete the set
1505 * immediately and reset the set pointer to NULL
1507 if(set_count(ci->cond_set) == 0) {
1508 del_set(ci->cond_set);
1509 list_del(&ci->list);
1510 obstack_free(cwi->obst, ci);
1516 DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
1518 set_irn_link(block, ci);
1521 phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
1524 INIT_LIST_HEAD(&pi->list);
1525 list_add(&pi->list, &cwi->phi_head);
1531 static void dump_conds(cond_t *cond, void *env)
1536 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
1537 cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
1538 get_nodes_block(cond->cond));
1540 for(i = 0; i < 2; ++i)
1541 if(cond->cases[i].masked_by)
1542 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
1543 cond, cond->cases[i].masked_by, i);
1546 static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi)
1551 snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
1553 if((f = fopen(buf, "wt")) != NULL) {
1558 ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
1559 list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
1560 ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
1561 list_for_each_entry(cond_t, cond, &ci->roots, list) {
1562 walk_conds(cond, NULL, dump_conds, f);
1563 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
1567 list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
1568 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
1569 phi->irn, phi->irn, get_nodes_block(phi->irn));
1570 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
1576 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
1579 struct obstack obst;
1580 phi_info_t *phi_info;
1581 cond_info_t *cond_info;
1582 cond_walk_info_t cwi;
1584 opt_if_conv_info_t p;
1586 if(!get_opt_if_conversion())
1589 /* get the parameters */
1591 memcpy(&p, params, sizeof(p));
1593 memcpy(&p, &default_info, sizeof(p));
1596 p.allow_mux = default_info.allow_mux;
1598 obstack_init(&obst);
1601 INIT_LIST_HEAD(&cwi.cond_info_head);
1602 INIT_LIST_HEAD(&cwi.phi_head);
1604 /* Init the debug stuff. */
1605 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
1607 firm_dbg_set_mask(dbg, LEVEL_1|LEVEL_2|LEVEL_3);
1610 /* if-conversion works better with normalized returns */
1611 normalize_one_return(irg);
1613 /* Ensure, that the dominators are computed. */
1616 DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
1617 get_entity_name(get_irg_entity(irg)), irg));
1620 * Collect information about the conds pu the phis on an obstack.
1621 * It is important that phi nodes which are 'higher' (with a
1622 * lower dfs pre order) are in front of the obstack. Since they are
1623 * possibly turned in to muxes this can enable the optimization
1626 irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
1629 vcg_dump_conds(irg, &cwi);
1632 /* Process each suitable phi found. */
1633 list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
1634 DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
1635 muxes_made += check_out_phi(phi_info, &p);
1638 list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
1639 del_set(cond_info->cond_set);
1642 DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
1644 obstack_free(&obst, NULL);