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);
47 * Additional block info.
49 typedef struct block_info {
50 ir_node *phi; /**< head of the Phi list */
51 int has_pinned; /**< set if the block contains instructions that cannot be moved */
54 #define get_block_blockinfo(block) ((block_info *)get_irn_link(block))
57 * Returns non-zero if a Block can be emptied.
59 static int can_empty_block(ir_node *block)
61 return !get_block_blockinfo(block)->has_pinned;
65 static ir_node* walk_to_projx(ir_node* start, const ir_node* dependency)
70 /* No need to find the conditional block if this block cannot be emptied and
73 if (!can_empty_block(start)) return NULL;
75 arity = get_irn_arity(start);
76 for (i = 0; i < arity; ++i) {
77 ir_node* pred = get_irn_n(start, i);
78 ir_node* pred_block = get_nodes_block(pred);
80 if (pred_block == dependency) {
81 assert(is_Proj(pred));
82 assert(get_irn_mode(pred) == mode_X);
86 if (is_cdep_on(pred_block, dependency)) {
87 return walk_to_projx(pred_block, dependency);
95 * Copies the DAG starting at node to the ith predecessor block of src_block
96 * -if the node isn't in the src_block, this is a nop and the node is returned
97 * -if the node is a phi in the src_block, the ith predecessor of the phi is
99 * otherwise returns the copy of the passed node
101 static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
108 if (get_nodes_block(node) != src_block) return node;
109 if (get_irn_op(node) == op_Phi) return get_irn_n(node, i);
111 copy = exact_copy(node);
112 dst_block = get_nodes_block(get_irn_n(src_block, i));
113 set_nodes_block(copy, dst_block);
115 DB((dbg, LEVEL_1, "Copying node %+F to block %+F, copy is %+F\n",
116 node, dst_block, copy));
118 arity = get_irn_arity(node);
119 for (j = 0; j < arity; ++j) {
120 set_irn_n(copy, j, copy_to(get_irn_n(node, j), src_block, i));
121 DB((dbg, LEVEL_2, "-- pred %d is %+F\n", j, get_irn_n(copy, j)));
128 * Remove predecessors i and j from node and add predecessor new_pred
130 static void rewire(ir_node* node, int i, int j, ir_node* new_pred)
132 int arity = get_irn_arity(node);
137 NEW_ARR_A(ir_node *, ins, arity - 1);
140 for (k = 0; k < i; ++k) ins[l++] = get_irn_n(node, k);
141 for (++k; k < j; ++k) ins[l++] = get_irn_n(node, k);
142 for (++k; k < arity; ++k) ins[l++] = get_irn_n(node, k);
144 assert(l == arity - 1);
145 set_irn_in(node, l, ins);
150 * Remove the jth predecessors from the ith predecessor of block and add it to block
152 static void split_block(ir_node* block, int i, int j)
154 ir_node* pred_block = get_nodes_block(get_irn_n(block, i));
155 int arity = get_irn_arity(block);
162 DB((dbg, LEVEL_1, "Splitting predecessor %d of predecessor %d of %+F\n", j, i, block));
164 NEW_ARR_A(ir_node*, ins, arity + 1);
166 for (phi = get_block_blockinfo(block)->phi; phi != NULL; phi = get_irn_link(phi)) {
167 ir_node* copy = copy_to(get_irn_n(phi, i), pred_block, j);
169 for (k = 0; k < i; ++k) ins[k] = get_irn_n(phi, k);
171 for (; k < arity; ++k) ins[k] = get_irn_n(phi, k);
172 ins[k] = get_irn_n(phi, i);
174 set_irn_in(phi, arity + 1, ins);
177 for (k = 0; k < i; ++k) ins[k] = get_irn_n(block, k);
178 ins[k++] = get_irn_n(pred_block, j);
179 for (; k < arity; ++k) ins[k] = get_irn_n(block, k);
180 ins[k] = get_irn_n(block, i);
182 set_irn_in(block, arity + 1, ins);
184 new_pred_arity = get_irn_arity(pred_block) - 1;
185 NEW_ARR_A(ir_node*, pred_ins, new_pred_arity);
187 for (phi = get_block_blockinfo(pred_block)->phi; phi != NULL; phi = get_irn_link(phi)) {
188 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(phi, k);
189 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(phi, k + 1);
190 assert(k == new_pred_arity);
191 if (new_pred_arity > 1) {
192 set_irn_in(phi, new_pred_arity, pred_ins);
194 exchange(phi, pred_ins[0]);
198 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(pred_block, k);
199 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(pred_block, k + 1);
200 assert(k == new_pred_arity);
201 if (new_pred_arity > 1) {
202 set_irn_in(pred_block, new_pred_arity, pred_ins);
204 exchange(pred_block, get_nodes_block(pred_ins[0]));
209 static void prepare_path(ir_node* block, int i, const ir_node* dependency)
211 ir_node* pred = get_nodes_block(get_irn_n(block, i));
215 DB((dbg, LEVEL_1, "Preparing predecessor %d of %+F\n", i, block));
217 pred_arity = get_irn_arity(pred);
218 for (j = 0; j < pred_arity; ++j) {
219 ir_node* pred_pred = get_nodes_block(get_irn_n(pred, j));
221 if (is_cdep_on(pred_pred, dependency)) {
222 prepare_path(pred, j, dependency);
223 split_block(block, i, j);
230 static void if_conv_walker(ir_node* block, void* env)
235 /* Bail out, if there are no Phis at all */
236 if (get_block_blockinfo(block)->phi == NULL) return;
239 arity = get_irn_arity(block);
240 for (i = 0; i < arity; ++i) {
244 pred = get_nodes_block(get_irn_n(block, i));
245 for (cdep = find_cdep(pred); cdep != NULL; cdep = cdep->next) {
246 const ir_node* dependency = cdep->node;
247 ir_node* projx0 = walk_to_projx(pred, dependency);
251 if (projx0 == NULL) continue;
253 cond = get_Proj_pred(projx0);
254 if (get_irn_op(cond) != op_Cond) continue;
255 /* We only handle boolean decisions, no switches */
256 if (get_irn_mode(get_Cond_selector(cond)) != mode_b) continue;
258 for (j = i + 1; j < arity; ++j) {
266 pred = get_nodes_block(get_irn_n(block, j));
268 if (!is_cdep_on(pred, dependency)) continue;
270 projx1 = walk_to_projx(pred, dependency);
272 if (projx1 == NULL) continue;
274 DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n",
278 prepare_path(block, i, dependency);
279 prepare_path(block, j, dependency);
280 arity = get_irn_arity(block);
282 conds[0] = get_Cond_selector(cond);
284 psi_block = get_nodes_block(cond);
285 phi = get_block_blockinfo(block)->phi;
287 ir_node* val_i = get_irn_n(phi, i);
288 ir_node* val_j = get_irn_n(phi, j);
290 if (val_i == val_j) {
292 DB((dbg, LEVEL_2, "Generating no psi, because both values are equal\n"));
294 /* Something is very fishy if two predecessors of a PhiM point into
295 * one block, but not at the same memory node
297 assert(get_irn_mode(phi) != mode_M);
298 if (get_Proj_proj(projx0) == pn_Cond_true) {
306 current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
308 DB((dbg, LEVEL_2, "Generating %+F for %+F\n", psi, phi));
314 rewire(phi, i, j, psi);
317 phi = get_irn_link(phi);
318 } while (phi != NULL);
320 exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
321 exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
325 DB((dbg, LEVEL_1, "Welding block %+F and %+F\n", block, psi_block));
326 get_block_blockinfo(block)->has_pinned |= get_block_blockinfo(psi_block)->has_pinned;
327 set_irn_in(block, get_irn_arity(psi_block), get_irn_in(psi_block) + 1);
328 exchange_cdep(psi_block, block);
329 exchange(psi_block, block);
331 DB((dbg, LEVEL_1, "Welding block %+F to %+F\n", block, psi_block));
332 get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
333 exchange(block, psi_block);
337 rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block));
346 * Block walker: add additional data
348 static void init_block_link(ir_node *block, void *env)
350 struct obstack *obst = env;
351 block_info *bi = obstack_alloc(obst, sizeof(*bi));
355 set_irn_link(block, bi);
360 * Daisy-chain all phis in a block
361 * If a non-movable node is encountered set the has_pinned flag
363 static void collect_phis(ir_node *node, void *env)
366 ir_node *block = get_nodes_block(node);
367 block_info *bi = get_block_blockinfo(block);
369 set_irn_link(node, bi->phi);
373 if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
375 * Ignore control flow nodes, these will be removed.
376 * This ignores Raise. That is surely bad. FIXME.
378 if (! is_cfop(node)) {
379 ir_node *block = get_nodes_block(node);
380 block_info *bi = get_block_blockinfo(block);
382 DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
391 * Transform multiple cascaded Psis into one Psi
393 static ir_node* fold_psi(ir_node* psi)
395 int arity = get_Psi_n_conds(psi);
406 for (i = 0; i < arity; ++i) {
407 n = get_Psi_val(psi, i);
408 if (get_irn_op(n) == op_Psi) {
409 new_arity += get_Psi_n_conds(n) + 1;
414 n = get_Psi_default(psi);
415 if (get_irn_op(n) == op_Psi) {
416 new_arity += get_Psi_n_conds(n);
419 if (arity == new_arity) return psi; // no attached Psis found
420 DB((dbg, LEVEL_1, "Folding %+F from %d to %d conds\n", psi, arity, new_arity));
422 NEW_ARR_A(ir_node *, conds, new_arity);
423 NEW_ARR_A(ir_node *, vals, new_arity + 1);
425 for (i = 0; i < arity; ++i) {
426 ir_node* c = get_Psi_cond(psi, i);
428 n = get_Psi_val(psi, i);
429 if (get_irn_op(n) == op_Psi) {
430 a = get_Psi_n_conds(n);
431 for (k = 0; k < a; ++k) {
432 conds[j] = new_r_And(
433 current_ir_graph, get_nodes_block(psi),
434 c, get_Psi_cond(n, k), mode_b
436 vals[j] = get_Psi_val(n, k);
440 vals[j] = get_Psi_default(n);
447 n = get_Psi_default(psi);
448 if (get_irn_op(n) == op_Psi) {
449 a = get_Psi_n_conds(n);
450 for (k = 0; k < a; ++k) {
451 conds[j] = get_Psi_cond(n, k);
452 vals[j] = get_Psi_val(n, k);
455 vals[j] = get_Psi_default(n);
459 assert(j == new_arity);
461 current_ir_graph, get_nodes_block(psi),
462 new_arity, conds, vals, get_irn_mode(psi)
464 DB((dbg, LEVEL_1, "Folded %+F into new %+F\n", psi, new_psi));
465 exchange(psi, new_psi);
471 * Merge consecutive psi inputs if the data inputs are the same
473 static ir_node* meld_psi(ir_node* psi)
475 int arity = get_Psi_n_conds(psi);
486 val = get_Psi_val(psi, 0);
487 DB((dbg, LEVEL_1, "Pred 0 of %+F is %+F\n", psi, val));
488 for (i = 1; i < arity; ++i) {
489 ir_node* v = get_Psi_val(psi, i);
490 DB((dbg, LEVEL_1, "Pred %2d of %+F is %+F\n", i, psi, v));
496 DB((dbg, LEVEL_1, "Default of %+F is %+F\n", psi, get_Psi_default(psi)));
497 if (val == get_Psi_default(psi)) --new_arity;
499 DB((dbg, LEVEL_1, "Melding Psi %+F from %d conds to %d\n", psi, arity, new_arity));
501 if (new_arity == arity) return psi;
503 /* If all data inputs of the Psi are equal, exchange the Psi with that value */
504 if (new_arity == 0) {
509 NEW_ARR_A(ir_node *, conds, new_arity);
510 NEW_ARR_A(ir_node *, vals, new_arity + 1);
511 cond = get_Psi_cond(psi, 0);
512 val = get_Psi_val(psi, 0);
514 for (i = 1; i < arity; ++i) {
515 ir_node* v = get_Psi_val(psi, i);
519 current_ir_graph, get_nodes_block(psi),
520 cond, get_Psi_cond(psi, i), mode_b
529 if (val != get_Psi_default(psi)) {
534 vals[j] = get_Psi_default(psi);
535 assert(j == new_arity);
537 current_ir_graph, get_nodes_block(psi),
538 new_arity, conds, vals, get_irn_mode(psi)
540 DB((dbg, LEVEL_1, "Molded %+F into %+F\n", psi, new_psi));
541 exchange(psi, new_psi);
547 * Split a Psi with multiple conditions into multiple Psis with one condtition
550 static ir_node* split_psi(ir_node* psi)
552 int arity = get_Psi_n_conds(psi);
558 if (arity == 1) return psi;
560 mode = get_irn_mode(psi);
561 block = get_nodes_block(psi);
562 rval = get_Psi_default(psi);
563 for (i = arity - 1; i >= 0; --i) {
567 conds[0] = get_Psi_cond(psi, i);
568 vals[0] = get_Psi_val(psi, i);
571 current_ir_graph, block, 1, conds, vals, mode
579 static void optimise_psis(ir_node* node, void* env)
581 if (get_irn_op(node) != op_Psi) return;
583 node = fold_psi(node);
586 node = meld_psi(node);
589 node = split_psi(node);
594 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
598 if (!get_opt_if_conversion())
601 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
603 DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
605 dump_ir_block_graph(irg, "_00_pre");
607 normalize_one_return(irg);
608 remove_critical_cf_edges(irg);
610 dump_ir_block_graph(irg, "_01_normal");
616 irg_block_walk_graph(irg, init_block_link, NULL, &obst);
617 irg_walk_graph(irg, collect_phis, NULL, NULL);
618 irg_block_walk_graph(irg, NULL, if_conv_walker, NULL);
620 dump_ir_block_graph(irg, "_02_ifconv");
621 local_optimize_graph(irg);
622 dump_ir_block_graph(irg, "_03_postopt");
624 irg_walk_graph(irg, NULL, optimise_psis, NULL);
626 dump_ir_block_graph(irg, "_04_postifconv");
628 obstack_free(&obst, NULL);
639 * Make Mux nodes from Conds where it its possible.
640 * @author Sebastian Hack
657 #include "irgraph_t.h"
658 #include "irnode_t.h"
662 #include "irmode_t.h"
663 #include "ircons_t.h"
668 #include "irflag_t.h"
670 #include "irprintf.h"
675 #include "bitfiddle.h"
682 * check, if a node is const and return its tarval or
683 * return a default tarval.
684 * @param cnst The node whose tarval to get.
685 * @param or The alternative tarval, if the node is no Const.
686 * @return The tarval of @p cnst, if the node is Const, @p otherwise.
688 static tarval *get_value_or(ir_node *cnst, tarval *or)
690 return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
695 * Try to optimize nested muxes into a dis- or conjunction
697 * @param mux The parent mux, which has muxes as operands.
698 * @return The replacement node for this mux. If the optimization is
699 * successful, this might be an And or Or node, if not, its the mux
702 static ir_node *optimize_mux_chain(ir_node *mux)
707 ir_mode *mode = get_irn_mode(mux);
712 * If we have no mux, or its mode is not integer, we
715 if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
719 null = get_mode_null(mode);
720 minus_one = tarval_sub(null, get_tarval_one(mode));
722 ops[0] = get_Mux_false(mux);
723 ops[1] = get_Mux_true(mux);
725 for(i = 0; i < 2; ++i) {
727 tarval *tva, *tvb, *tvd;
731 * A mux operand at the first position can be factored
732 * out, if the operands fulfill several conditions:
734 * mux(c1, mux(c2, a, b), d)
736 * This can be made into:
737 * 1) mux(c1, 0, d) | mux(c2, a, b)
738 * if a | d == d and b | d == d
740 * 2) mux(c1, -1, d) & mux(c2, a, b)
741 * if a & d == d and a & b == b
743 if(get_irn_op(ops[i]) == op_Mux) {
746 a = get_Mux_false(child_mux);
747 b = get_Mux_true(child_mux);
750 /* Try the or stuff */
751 tva = get_value_or(a, minus_one);
752 tvb = get_value_or(b, minus_one);
753 tvd = get_value_or(d, null);
755 if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
756 && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
758 ops[i] = new_Const(mode, null);
759 res = new_r_Or(current_ir_graph, get_nodes_block(mux),
760 mux, child_mux, mode);
764 /* If the or didn't go, try the and stuff */
765 tva = get_value_or(a, null);
766 tvb = get_value_or(b, null);
767 tvd = get_value_or(d, minus_one);
769 if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
770 && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
772 ops[i] = new_Const(mode, minus_one);
773 res = new_r_And(current_ir_graph, get_nodes_block(mux),
774 mux, child_mux, mode);
780 /* recursively optimize nested muxes. */
781 set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
782 set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
788 /***********************************************************
789 * The If conversion itself.
790 ***********************************************************/
792 /** allow every Mux to be created. */
793 static int default_allow_mux(ir_node *sel, ir_node *false_res, ir_node *true_res) {
800 static const opt_if_conv_info_t default_info = {
805 /** The debugging module. */
806 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
809 * A simple check for side effects upto an opcode of a ir node.
810 * @param irn The ir node to check,
811 * @return 1 if the opcode itself may produce side effects, 0 if not.
813 static INLINE int has_side_effects(const ir_node *irn)
815 ir_op *op = get_irn_op(irn);
820 return !mode_is_datab(get_irn_mode(irn));
824 * Possible failure reasons
826 enum failure_reason_t {
827 SUCCESS = IF_RESULT_SUCCESS,
828 TO_DEEP = IF_RESULT_TOO_DEEP,
829 SIDE_EFFECTS = IF_RESULT_SIDE_EFFECT,
830 PHI_FOUND = IF_RESULT_SIDE_EFFECT_PHI,
831 DENIED = IF_RESULT_DENIED
835 * Decides, if a given expression and its subexpressions
836 * (to certain, also given extent) can be moved to a block.
838 * @param expr The expression to examine.
839 * @param block The block where the expression should go.
840 * @param depth The current depth, passed recursively. Use 0 for
841 * non-recursive calls.
842 * @param info The options for createing Mux nodes.
845 * @return a failure reason
847 static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, const opt_if_conv_info_t *info)
851 ir_node *expr_block = get_nodes_block(expr);
854 * If we are forced to look too deep into the expression,
855 * treat it like it could not be moved.
857 if(depth >= info->max_depth) {
863 * If the block of the expression dominates the specified
864 * destination block, it does not matter if the expression
865 * has side effects or anything else. It is executed on each
866 * path the destination block is reached.
868 if (block_dominates(expr_block, dest_block))
872 * We cannot move phis!
880 * This should be superfluous and could be converted into a assertion.
881 * The destination block _must_ dominate the block of the expression,
882 * else the expression could be used without its definition.
884 if (! block_dominates(dest_block, expr_block)) {
885 res = IF_RESULT_SIDE_EFFECT;
890 * Surely, if the expression does not have a data mode, it is not
891 * movable. Perhaps one should also test the floating property of
894 if (has_side_effects(expr)) {
895 res = IF_RESULT_SIDE_EFFECT;
900 * If the node looks alright so far, look at its operands and
901 * check them out. If one of them cannot be moved, this one
902 * cannot be moved either.
904 for (i = 0, n = get_irn_arity(expr); i < n; ++i) {
905 ir_node *op = get_irn_n(expr, i);
906 int new_depth = is_Proj(op) ? depth : depth + 1;
908 res = _can_move_to(op, dest_block, new_depth, info);
915 DBG((dbg, LEVEL_3, "\t\t\tcan move to %n: %d\n", expr, res));
921 * Convenience function for _can_move_to.
922 * Checks, if an expression can be moved to another block. The check can
923 * be limited to a expression depth meaning if we need to crawl in
924 * deeper into an expression than a given threshold to examine if
925 * it can be moved, the expression is rejected and the test returns
928 * @param expr The expression to check for.
929 * @param dest_block The destination block you want @p expr to be.
930 * @param info The options for createing Mux nodes.
932 * @return return a failure reason
934 static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, const opt_if_conv_info_t *info)
936 return _can_move_to(expr, dest_block, 0, info);
940 * move a DAG given by a root node expr into a new block
942 * @param expr the root of a dag
943 * @param dest_block the destination block
945 static void move_to(ir_node *expr, ir_node *dest_block)
948 ir_node *expr_block = get_nodes_block(expr);
951 * If we reached the dominator, we are done.
952 * We will never put code through the dominator
954 if (block_dominates(expr_block, dest_block))
957 for (i = 0, n = get_irn_arity(expr); i < n; ++i)
958 move_to(get_irn_n(expr, i), dest_block);
960 set_nodes_block(expr, dest_block);
964 * return the common dominator of two blocks
966 static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2)
968 if(block_dominates(b1, b2))
970 else if(block_dominates(b2, b1))
975 for (p = get_Block_idom(b1); !block_dominates(p, b2); p = get_Block_idom(p));
981 * Information about a cond node.
983 typedef struct _cond_t {
984 ir_node *cond; /**< The cond node. */
985 struct list_head list; /**< List head which is used for queuing this cond
986 into the cond bunch it belongs to. */
988 unsigned totally_covers : 1;
989 struct _cond_t *link;
993 * Information about the both 'branches'
994 * (true and false), the cond creates.
997 int pos; /**< Number of the predecessor of the
998 phi block by which this branch is
999 reached. It is -1, if this branch is
1000 only reached through another cond. */
1002 struct _cond_t *masked_by; /**< If this cond's branch is only reached
1003 through another cond, we store this
1004 cond ir_node here. */
1009 * retrieve the conditional information from a Cond node
1011 static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
1016 return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
1020 typedef void (cond_walker_t)(cond_t *cond, void *env);
1022 static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
1023 long visited_nr, void *env)
1027 if(cond->visited_nr >= visited_nr)
1030 cond->visited_nr = visited_nr;
1035 for(i = 0; i < 2; ++i) {
1036 cond_t *c = cond->cases[i].masked_by;
1039 _walk_conds(c, pre, post, visited_nr, env);
1046 static long cond_visited_nr = 0;
1048 static void walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post, void *env)
1050 _walk_conds(cond, pre, post, ++cond_visited_nr, env);
1053 static void link_conds(cond_t *cond, void *env)
1055 cond_t **ptr = (cond_t **) env;
1062 * Compare two conds for use in a firm set.
1063 * Two cond_t's are equal, if they designate the same cond node.
1064 * @param a A cond_t.
1065 * @param b Another one.
1066 * @param size Not used.
1067 * @return 0 (!) if they are equal, != 0 otherwise.
1069 static int cond_cmp(const void *a, const void *b, size_t size)
1071 const cond_t *x = a;
1072 const cond_t *y = b;
1073 return x->cond != y->cond;
1077 * Information about conds which can be made to muxes.
1078 * Instances of this struct are attached to the link field of
1079 * blocks in which phis are located.
1081 typedef struct _cond_info_t {
1082 struct list_head list; /**< Used to list all of these structs per class. */
1084 struct list_head roots; /**< A list of non-depending Conds. Two Conds are
1085 independent, if it's not possible not reach one from the
1086 other (all Conds in this list have to dominate the
1087 block this struct is attached to). */
1089 ir_node *first_phi; /**< The first phi node this cond info was made for. */
1090 set *cond_set; /**< A set of all dominating reachable Conds. */
1096 static void _find_conds(ir_node *irn, unsigned long visited_nr,
1097 ir_node *dominator, cond_t *masked_by, int pos, int depth, cond_info_t *ci)
1100 int saw_select_cond = 0;
1102 block = get_nodes_block(irn);
1105 * Only check this block if it is dominated by the specified
1106 * dominator or it has not been visited yet.
1108 if (block_dominates(dominator, block) && get_Block_block_visited(block) < visited_nr) {
1109 cond_t *res = masked_by;
1112 /* check, if we're on a ProjX
1114 * Further, the ProjX/Cond block must dominate the base block
1115 * (the block with the phi in it), otherwise, the Cond
1116 * is not affecting the phi so that a mux can be inserted.
1118 if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
1120 int proj = get_Proj_proj(irn);
1121 ir_node *cond = get_Proj_pred(irn);
1123 /* true, if the mode is a mode_b cond _NO_ switch cond */
1124 int is_modeb_cond = get_irn_opcode(cond) == iro_Cond
1125 && get_irn_mode(get_Cond_selector(cond)) == mode_b;
1127 saw_select_cond = !is_modeb_cond;
1129 /* Check, if the pred of the proj is a Cond
1130 * with a Projb as selector.
1135 memset(&c, 0, sizeof(c));
1138 c.cases[0].pos = -1;
1139 c.cases[1].pos = -1;
1141 /* get or insert the cond info into the set. */
1142 res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
1145 * If this cond is already masked by the masked_by cond
1146 * return immediately, since we don't have anything to add.
1148 if(masked_by && res->cases[proj].masked_by == masked_by)
1153 list_add(&res->list, &ci->roots);
1157 * Set masked by (either NULL or another cond node.
1158 * If this cond is truly masked by another one, set
1159 * the position of the actually investigated branch
1160 * to -1. Since the cond is masked by another one,
1161 * there could be more ways from the start block
1162 * to this branch, so we choose -1.
1164 res->cases[proj].masked_by = masked_by;
1167 res->cases[proj].pos = pos;
1170 * Since the masked_by nodes masks a cond, remove it from the
1171 * root list of the conf trees.
1174 assert(res->cases[proj].pos < 0);
1175 list_del_init(&masked_by->list);
1178 DBG((dbg, LEVEL_2, "%n (%s branch) "
1179 "for pos %d in block %n reached by %n\n",
1180 cond, proj ? "true" : "false", pos,
1181 block, masked_by ? masked_by->cond : NULL));
1185 if(get_Block_block_visited(block) < visited_nr && !saw_select_cond) {
1187 set_Block_block_visited(block, visited_nr);
1189 /* Search recursively from this cond. */
1190 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1191 ir_node *pred = get_irn_n(block, i);
1194 * If the depth is 0 (the first recursion), we set the pos to
1195 * the current viewed predecessor, else we adopt the position
1196 * as given by the caller. We also increase the depth for the
1197 * recursively called functions.
1199 _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci);
1207 * A convenience function for _find_conds.
1208 * It sets some parameters needed for recursion to appropriate start
1209 * values. Always use this function.
1211 * @param irn The node to start looking for Conds from. This might
1212 * be the phi node we are investigating.
1213 * @param conds The set to record the found Conds in.
1215 static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
1218 unsigned long visited_nr;
1219 ir_node *block = get_nodes_block(irn);
1220 ir_node *dom = get_Block_idom(block);
1222 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1223 ir_node *pred = get_irn_n(block, i);
1225 inc_irg_block_visited(current_ir_graph);
1226 visited_nr = get_irg_block_visited(current_ir_graph);
1227 set_Block_block_visited(block, visited_nr);
1229 DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
1230 _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
1235 * Make the mux for a given cond.
1237 * @param phi The phi node which shall be replaced by a mux.
1238 * @param dom The block where the muxes shall be placed.
1239 * @param cond The cond information.
1240 * @param info The options for createing Mux nodes.
1241 * @return The mux node made for this cond.
1243 static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond,
1244 const opt_if_conv_info_t *info, ir_node **mux, bitset_t *positions,
1245 int *muxes_made, long visited_nr)
1248 ir_node *projb = get_Cond_selector(cond->cond);
1249 ir_node *bl = get_nodes_block(cond->cond);
1250 ir_node *operands[2];
1253 cond->visited_nr = visited_nr;
1254 DBG((dbg, LEVEL_2, "%n\n", cond->cond));
1255 for(i = 0; i < 2; ++i) {
1256 cond_t *masked_by = cond->cases[i].masked_by;
1257 int pos = cond->cases[i].pos;
1263 * If this Cond branch is masked by another cond, make the mux
1264 * for that Cond first, since the Mux for this cond takes
1269 DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
1270 if(masked_by->visited_nr < visited_nr)
1271 operands[i] = make_mux_on_demand(phi, dom, masked_by, info, mux, positions, muxes_made, visited_nr);
1275 * If this cond branch is not masked by another cond, take
1276 * the corresponding phi operand as an operand to the mux.
1279 operands[i] = get_irn_n(phi, pos);
1285 * Move the operands to the dominator block if the cond
1286 * made sense. Some Conds found are not suitable for making a mux
1287 * out of them, since one of their branches cannot be reached from
1288 * the phi block. In that case we do not make a mux and return NULL.
1290 if(operands[0] && operands[1]) {
1291 if (operands[0] == operands[1]) {
1292 /* there is no gain in using mux in this case, as
1293 it will be optimized away. We will NOT move the
1294 content of the blocks either
1296 for (i = 0; i < 2; ++i)
1298 bitset_set(positions, set[i]);
1304 can_move[0] = can_move_to(operands[0], bl, info);
1305 can_move[1] = can_move_to(operands[1], bl, info);
1307 if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) {
1308 if (info->allow_mux(projb, operands[0], operands[1])) {
1309 move_to(operands[0], bl);
1310 move_to(operands[1], bl);
1313 *mux = new_r_Mux(current_ir_graph, bl, projb,
1314 operands[0], operands[1], get_irn_mode(operands[0]));
1318 DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
1319 *mux, projb, operands[0], operands[1], set[0], set[1]));
1321 for(i = 0; i < 2; ++i)
1323 bitset_set(positions, set[i]);
1325 /* we have done one */
1326 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_SUCCESS);
1330 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_DENIED);
1334 if(can_move[0] != SUCCESS)
1335 hook_if_conversion(current_ir_graph, phi, set[0], NULL, can_move[0]);
1336 if(can_move[1] != SUCCESS)
1337 hook_if_conversion(current_ir_graph, phi, set[1], NULL, can_move[1]);
1342 hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF);
1344 hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF);
1350 typedef struct _phi_info_t {
1351 struct list_head list;
1352 cond_info_t *cond_info;
1358 * Examine a phi node if it can be replaced by some muxes.
1359 * @param irn A phi node.
1360 * @param info Parameters for the if conversion algorithm.
1362 static int check_out_phi(phi_info_t *phi_info, const opt_if_conv_info_t *info)
1364 ir_node *irn = phi_info->irn;
1365 ir_node *block, *nw;
1366 cond_info_t *cond_info = phi_info->cond_info;
1370 bitset_t *positions;
1372 block = get_nodes_block(irn);
1373 arity = get_irn_arity(irn);
1374 positions = bitset_alloca(arity);
1376 assert(is_Phi(irn));
1377 assert(get_irn_arity(irn) == get_irn_arity(block));
1380 DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
1382 list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
1383 ir_node *cidom = block;
1384 ir_node *mux = NULL;
1385 cond_t *p, *head = NULL;
1388 bitset_clear_all(positions);
1390 DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
1392 * Link all conds which are in the subtree of
1393 * the current cond in the list together.
1395 walk_conds(cond, link_conds, NULL, &head);
1398 for(p = head; p; p = p->link) {
1399 for(i = 0; i < 2; ++i) {
1400 int pos = p->cases[i].pos;
1402 cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
1406 DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
1407 make_mux_on_demand(irn, cidom, cond, info, &mux, positions, &muxes_made, ++cond_visited_nr);
1410 bitset_foreach(positions, pos)
1411 set_irn_n(irn, (int) pos, mux);
1416 * optimize the phi away. This can anable further runs of this
1417 * function. Look at _can_move. phis cannot be moved there.
1419 nw = optimize_in_place_2(irn);
1426 typedef struct _cond_walk_info_t {
1427 struct obstack *obst;
1428 struct list_head cond_info_head;
1429 struct list_head phi_head;
1433 static void annotate_cond_info_pre(ir_node *irn, void *data)
1435 set_irn_link(irn, NULL);
1438 static void annotate_cond_info_post(ir_node *irn, void *data)
1440 cond_walk_info_t *cwi = data;
1443 * Check, if the node is a phi
1444 * we then compute a set of conds which are reachable from this
1445 * phi's block up to its dominator.
1446 * The set is attached to the blocks link field.
1448 if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
1449 ir_node *block = get_nodes_block(irn);
1451 cond_info_t *ci = get_irn_link(block);
1453 /* If the set is not yet computed, do it now. */
1455 ci = obstack_alloc(cwi->obst, sizeof(*ci));
1456 ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
1457 ci->first_phi = irn;
1459 INIT_LIST_HEAD(&ci->roots);
1460 INIT_LIST_HEAD(&ci->list);
1463 * Add this cond info to the list of all cond infos
1464 * in this graph. This is just done to xfree the
1465 * set easier afterwards (we save an irg_walk_graph).
1467 list_add(&cwi->cond_info_head, &ci->list);
1469 DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
1472 * Fill the set with conds we find on the way from
1473 * the block to its dominator.
1475 find_conds(irn, ci);
1478 * If there where no suitable conds, delete the set
1479 * immediately and reset the set pointer to NULL
1481 if(set_count(ci->cond_set) == 0) {
1482 del_set(ci->cond_set);
1483 list_del(&ci->list);
1484 obstack_free(cwi->obst, ci);
1490 DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
1492 set_irn_link(block, ci);
1495 phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
1498 INIT_LIST_HEAD(&pi->list);
1499 list_add(&pi->list, &cwi->phi_head);
1505 static void dump_conds(cond_t *cond, void *env)
1510 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
1511 cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
1512 get_nodes_block(cond->cond));
1514 for(i = 0; i < 2; ++i)
1515 if(cond->cases[i].masked_by)
1516 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
1517 cond, cond->cases[i].masked_by, i);
1520 static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi)
1525 snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
1527 if((f = fopen(buf, "wt")) != NULL) {
1532 ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
1533 list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
1534 ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
1535 list_for_each_entry(cond_t, cond, &ci->roots, list) {
1536 walk_conds(cond, NULL, dump_conds, f);
1537 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
1541 list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
1542 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
1543 phi->irn, phi->irn, get_nodes_block(phi->irn));
1544 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
1550 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
1553 struct obstack obst;
1554 phi_info_t *phi_info;
1555 cond_info_t *cond_info;
1556 cond_walk_info_t cwi;
1558 opt_if_conv_info_t p;
1560 if(!get_opt_if_conversion())
1563 /* get the parameters */
1565 memcpy(&p, params, sizeof(p));
1567 memcpy(&p, &default_info, sizeof(p));
1570 p.allow_mux = default_info.allow_mux;
1572 obstack_init(&obst);
1575 INIT_LIST_HEAD(&cwi.cond_info_head);
1576 INIT_LIST_HEAD(&cwi.phi_head);
1578 /* Init the debug stuff. */
1579 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
1581 firm_dbg_set_mask(dbg, LEVEL_1|LEVEL_2|LEVEL_3);
1584 /* if-conversion works better with normalized returns */
1585 normalize_one_return(irg);
1587 /* Ensure, that the dominators are computed. */
1590 DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
1591 get_entity_name(get_irg_entity(irg)), irg));
1594 * Collect information about the conds pu the phis on an obstack.
1595 * It is important that phi nodes which are 'higher' (with a
1596 * lower dfs pre order) are in front of the obstack. Since they are
1597 * possibly turned in to muxes this can enable the optimization
1600 irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
1603 vcg_dump_conds(irg, &cwi);
1606 /* Process each suitable phi found. */
1607 list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
1608 DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
1609 muxes_made += check_out_phi(phi_info, &p);
1612 list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
1613 del_set(cond_info->cond_set);
1616 DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
1618 obstack_free(&obst, NULL);
1620 dump_ir_block_graph(irg, "_ifconv_hack");