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 = exact_copy(node);
101 dst_block = get_nodes_block(get_irn_n(src_block, i));
102 set_nodes_block(copy, dst_block);
104 DB((dbg, LEVEL_1, "Copying node %+F to block %+F, copy is %+F\n",
105 node, dst_block, copy));
107 arity = get_irn_arity(node);
108 for (j = 0; j < arity; ++j) {
109 set_irn_n(copy, j, copy_to(get_irn_n(node, j), src_block, i));
110 DB((dbg, LEVEL_2, "-- pred %d is %+F\n", j, get_irn_n(copy, j)));
117 * Duplicate and move the contents of ith block predecessor into its
118 * predecessors if the block has multiple control dependencies and only one
120 * Also bail out if the block contains non-movable nodes, because later
121 * if-conversion would be pointless.
123 static int fission_block(ir_node* block, int i)
125 ir_node* pred = get_irn_n(block, i);
134 if (get_irn_op(pred) != op_Jmp) return 0;
135 pred_block = get_nodes_block(pred);
137 if (!has_multiple_cdep(pred_block)) return 0;
138 if (!can_empty_block(pred_block)) return 0;
140 DB((dbg, LEVEL_1, "Fissioning block %+F\n", pred_block));
142 pred_arity = get_irn_arity(pred_block);
143 arity = get_irn_arity(block);
144 info = get_block_blockinfo(block);
145 NEW_ARR_A(ir_node *, ins, arity + pred_arity - 1);
146 for (phi = info->phi; phi != NULL; phi = get_irn_link(phi)) {
147 for (j = 0; j < i; ++j) ins[j] = get_irn_n(phi, j);
148 for (j = 0; j < pred_arity; ++j) {
149 ins[i + j] = copy_to(get_irn_n(phi, i), pred_block, j);
151 for (j = i + 1; j < arity; ++j) {
152 ins[pred_arity - 1 + j] = get_irn_n(phi, j);
154 set_irn_in(phi, arity + pred_arity - 1, ins);
156 for (j = 0; j < i; ++j) ins[j] = get_irn_n(block, j);
157 for (j = 0; j < pred_arity; ++j) ins[i + j] = get_irn_n(pred_block, j);
158 for (j = i + 1; j < arity; ++j) ins[pred_arity - 1 + j] = get_irn_n(block, j);
159 set_irn_in(block, arity + pred_arity - 1, ins);
161 /* Kill all Phis in the fissioned block
162 * This is to make sure they're not kept alive
164 info = get_block_blockinfo(pred_block);
166 while (phi != NULL) {
167 ir_node* next = get_irn_link(phi);
168 exchange(phi, new_Bad());
176 * Remove predecessors i and j from node and add predecessor new_pred
178 static void rewire(ir_node* node, int i, int j, ir_node* new_pred)
180 int arity = get_irn_arity(node);
185 NEW_ARR_A(ir_node *, ins, arity - 1);
188 for (k = 0; k < i; ++k) ins[l++] = get_irn_n(node, k);
189 for (++k; k < j; ++k) ins[l++] = get_irn_n(node, k);
190 for (++k; k < arity; ++k) ins[l++] = get_irn_n(node, k);
192 assert(l == arity - 1);
193 set_irn_in(node, l, ins);
197 static void if_conv_walker(ir_node* block, void* env)
203 /* Bail out, if there are no Phis at all */
204 if (get_block_blockinfo(block)->phi == NULL) return;
207 arity = get_irn_arity(block);
208 for (i = 0; i < arity; ++i) {
209 if (fission_block(block, i)) goto restart;
213 arity = get_irn_arity(block);
214 for (i = 0; i < arity; ++i) {
220 projx0 = walk_to_projx(get_irn_n(block, i));
221 if (projx0 == NULL) return;
222 pred = get_Proj_pred(projx0);
223 if (get_irn_op(pred) != op_Cond || get_irn_mode(get_Cond_selector(pred)) != mode_b) continue;
226 if (!can_empty_block(get_nodes_block(get_irn_n(block, i)))) {
227 DB((dbg, LEVEL_1, "Cannot empty block %+F\n",
228 get_nodes_block(get_irn_n(block, i))
233 for (j = i + 1; j < arity; ++j) {
240 projx1 = walk_to_projx(get_irn_n(block, j));
241 if (projx1 == NULL) continue;
242 pred = get_Proj_pred(projx1);
243 if (get_irn_op(pred) != op_Cond || get_irn_mode(get_Cond_selector(pred)) != mode_b) continue;
244 if (pred != cond) continue;
245 DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n", cond, projx0, projx1));
247 if (!can_empty_block(get_nodes_block(get_irn_n(block, j)))) {
248 DB((dbg, LEVEL_1, "Cannot empty %+F\n", get_nodes_block(get_irn_n(block, j))));
252 conds[0] = get_Cond_selector(cond);
254 psi_block = get_nodes_block(cond);
255 phi = get_block_blockinfo(block)->phi;
257 ir_node* val_i = get_irn_n(phi, i);
258 ir_node* val_j = get_irn_n(phi, j);
260 if (val_i == val_j) {
262 DB((dbg, LEVEL_2, "Generating no psi, because both values are equal\n"));
264 /* Something is very fishy if two predecessors of a PhiM point into
265 * one block, but not at the same memory node
267 assert(get_irn_mode(phi) != mode_M);
268 if (get_Proj_proj(projx0) == pn_Cond_true) {
276 current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
278 DB((dbg, LEVEL_2, "Generating %+F for %+F\n", psi, phi));
284 rewire(phi, i, j, psi);
287 phi = get_irn_link(phi);
288 } while (phi != NULL);
290 exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
291 exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
294 DB((dbg, LEVEL_1, "Welding block %+F to %+F\n", block, psi_block));
295 get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
296 exchange(block, psi_block);
299 rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block));
307 * Block walker: add additional data
309 static void init_block_link(ir_node *block, void *env)
311 struct obstack *obst = env;
312 block_info *bi = obstack_alloc(obst, sizeof(*bi));
316 set_irn_link(block, bi);
321 * Daisy-chain all phis in a block
322 * If a non-movable node is encountered set the has_pinned flag
324 static void collect_phis(ir_node *node, void *env)
327 ir_node *block = get_nodes_block(node);
328 block_info *bi = get_block_blockinfo(block);
330 set_irn_link(node, bi->phi);
334 if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
336 * Ignore control flow nodes, these will be removed.
337 * This ignores Raise. That is surely bad. FIXME.
339 if (! is_cfop(node)) {
340 ir_node *block = get_nodes_block(node);
341 block_info *bi = get_block_blockinfo(block);
343 DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
352 * Transform multiple cascaded Psis into one Psi
354 static ir_node* fold_psi(ir_node* psi)
356 int arity = get_Psi_n_conds(psi);
367 for (i = 0; i < arity; ++i) {
368 n = get_Psi_val(psi, i);
369 if (get_irn_op(n) == op_Psi) {
370 new_arity += get_Psi_n_conds(n) + 1;
375 n = get_Psi_default(psi);
376 if (get_irn_op(n) == op_Psi) {
377 new_arity += get_Psi_n_conds(n);
380 if (arity == new_arity) return psi; // no attached Psis found
381 DB((dbg, LEVEL_1, "Folding %+F from %d to %d conds\n", psi, arity, new_arity));
383 NEW_ARR_A(ir_node *, conds, new_arity);
384 NEW_ARR_A(ir_node *, vals, new_arity + 1);
386 for (i = 0; i < arity; ++i) {
387 ir_node* c = get_Psi_cond(psi, i);
389 n = get_Psi_val(psi, i);
390 if (get_irn_op(n) == op_Psi) {
391 a = get_Psi_n_conds(n);
392 for (k = 0; k < a; ++k) {
393 conds[j] = new_r_And(
394 current_ir_graph, get_nodes_block(psi),
395 c, get_Psi_cond(n, k), mode_b
397 vals[j] = get_Psi_val(n, k);
401 vals[j] = get_Psi_default(n);
408 n = get_Psi_default(psi);
409 if (get_irn_op(n) == op_Psi) {
410 a = get_Psi_n_conds(n);
411 for (k = 0; k < a; ++k) {
412 conds[j] = get_Psi_cond(n, k);
413 vals[j] = get_Psi_val(n, k);
416 vals[j] = get_Psi_default(n);
420 assert(j == new_arity);
422 current_ir_graph, get_nodes_block(psi),
423 new_arity, conds, vals, get_irn_mode(psi)
425 DB((dbg, LEVEL_1, "Folded %+F into new %+F\n", psi, new_psi));
426 exchange(psi, new_psi);
432 * Merge consecutive psi inputs if the data inputs are the same
434 static ir_node* meld_psi(ir_node* psi)
436 int arity = get_Psi_n_conds(psi);
447 val = get_Psi_val(psi, 0);
448 DB((dbg, LEVEL_1, "Pred 0 of %+F is %+F\n", psi, val));
449 for (i = 1; i < arity; ++i) {
450 ir_node* v = get_Psi_val(psi, i);
451 DB((dbg, LEVEL_1, "Pred %2d of %+F is %+F\n", i, psi, v));
457 DB((dbg, LEVEL_1, "Default of %+F is %+F\n", psi, get_Psi_default(psi)));
458 if (val == get_Psi_default(psi)) --new_arity;
460 DB((dbg, LEVEL_1, "Melding Psi %+F from %d conds to %d\n", psi, arity, new_arity));
462 if (new_arity == arity) return psi;
464 /* If all data inputs of the Psi are equal, exchange the Psi with that value */
465 if (new_arity == 0) {
470 NEW_ARR_A(ir_node *, conds, new_arity);
471 NEW_ARR_A(ir_node *, vals, new_arity + 1);
472 cond = get_Psi_cond(psi, 0);
473 val = get_Psi_val(psi, 0);
475 for (i = 1; i < arity; ++i) {
476 ir_node* v = get_Psi_val(psi, i);
480 current_ir_graph, get_nodes_block(psi),
481 cond, get_Psi_cond(psi, i), mode_b
490 if (val != get_Psi_default(psi)) {
495 vals[j] = get_Psi_default(psi);
496 assert(j == new_arity);
498 current_ir_graph, get_nodes_block(psi),
499 new_arity, conds, vals, get_irn_mode(psi)
501 DB((dbg, LEVEL_1, "Molded %+F into %+F\n", psi, new_psi));
502 exchange(psi, new_psi);
508 * Split a Psi with multiple conditions into multiple Psis with one condtition
511 static ir_node* split_psi(ir_node* psi)
513 int arity = get_Psi_n_conds(psi);
519 if (arity == 1) return psi;
521 mode = get_irn_mode(psi);
522 block = get_nodes_block(psi);
523 rval = get_Psi_default(psi);
524 for (i = arity - 1; i >= 0; --i) {
528 conds[0] = get_Psi_cond(psi, i);
529 vals[0] = get_Psi_val(psi, i);
532 current_ir_graph, block, 1, conds, vals, mode
540 static void optimise_psis(ir_node* node, void* env)
542 if (get_irn_op(node) != op_Psi) return;
544 node = fold_psi(node);
547 node = meld_psi(node);
550 node = split_psi(node);
555 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
559 if (!get_opt_if_conversion())
562 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
564 DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
566 dump_ir_block_graph(irg, "_00_pre");
568 normalize_one_return(irg);
569 remove_critical_cf_edges(irg);
571 dump_ir_block_graph(irg, "_01_normal");
577 irg_block_walk_graph(irg, init_block_link, NULL, &obst);
578 irg_walk_graph(irg, collect_phis, NULL, NULL);
579 irg_block_walk_graph(irg, NULL, if_conv_walker, NULL);
581 local_optimize_graph(irg);
582 dump_ir_block_graph(irg, "_02_ifconv");
584 irg_walk_graph(irg, NULL, optimise_psis, NULL);
586 dump_ir_block_graph(irg, "_03_postifconv");
588 obstack_free(&obst, NULL);
599 * Make Mux nodes from Conds where it its possible.
600 * @author Sebastian Hack
617 #include "irgraph_t.h"
618 #include "irnode_t.h"
622 #include "irmode_t.h"
623 #include "ircons_t.h"
628 #include "irflag_t.h"
630 #include "irprintf.h"
635 #include "bitfiddle.h"
642 * check, if a node is const and return its tarval or
643 * return a default tarval.
644 * @param cnst The node whose tarval to get.
645 * @param or The alternative tarval, if the node is no Const.
646 * @return The tarval of @p cnst, if the node is Const, @p otherwise.
648 static tarval *get_value_or(ir_node *cnst, tarval *or)
650 return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
655 * Try to optimize nested muxes into a dis- or conjunction
657 * @param mux The parent mux, which has muxes as operands.
658 * @return The replacement node for this mux. If the optimization is
659 * successful, this might be an And or Or node, if not, its the mux
662 static ir_node *optimize_mux_chain(ir_node *mux)
667 ir_mode *mode = get_irn_mode(mux);
672 * If we have no mux, or its mode is not integer, we
675 if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
679 null = get_mode_null(mode);
680 minus_one = tarval_sub(null, get_tarval_one(mode));
682 ops[0] = get_Mux_false(mux);
683 ops[1] = get_Mux_true(mux);
685 for(i = 0; i < 2; ++i) {
687 tarval *tva, *tvb, *tvd;
691 * A mux operand at the first position can be factored
692 * out, if the operands fulfill several conditions:
694 * mux(c1, mux(c2, a, b), d)
696 * This can be made into:
697 * 1) mux(c1, 0, d) | mux(c2, a, b)
698 * if a | d == d and b | d == d
700 * 2) mux(c1, -1, d) & mux(c2, a, b)
701 * if a & d == d and a & b == b
703 if(get_irn_op(ops[i]) == op_Mux) {
706 a = get_Mux_false(child_mux);
707 b = get_Mux_true(child_mux);
710 /* Try the or stuff */
711 tva = get_value_or(a, minus_one);
712 tvb = get_value_or(b, minus_one);
713 tvd = get_value_or(d, null);
715 if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
716 && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
718 ops[i] = new_Const(mode, null);
719 res = new_r_Or(current_ir_graph, get_nodes_block(mux),
720 mux, child_mux, mode);
724 /* If the or didn't go, try the and stuff */
725 tva = get_value_or(a, null);
726 tvb = get_value_or(b, null);
727 tvd = get_value_or(d, minus_one);
729 if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
730 && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
732 ops[i] = new_Const(mode, minus_one);
733 res = new_r_And(current_ir_graph, get_nodes_block(mux),
734 mux, child_mux, mode);
740 /* recursively optimize nested muxes. */
741 set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
742 set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
748 /***********************************************************
749 * The If conversion itself.
750 ***********************************************************/
752 /** allow every Mux to be created. */
753 static int default_allow_mux(ir_node *sel, ir_node *false_res, ir_node *true_res) {
760 static const opt_if_conv_info_t default_info = {
765 /** The debugging module. */
766 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
769 * A simple check for side effects upto an opcode of a ir node.
770 * @param irn The ir node to check,
771 * @return 1 if the opcode itself may produce side effects, 0 if not.
773 static INLINE int has_side_effects(const ir_node *irn)
775 ir_op *op = get_irn_op(irn);
780 return !mode_is_datab(get_irn_mode(irn));
784 * Possible failure reasons
786 enum failure_reason_t {
787 SUCCESS = IF_RESULT_SUCCESS,
788 TO_DEEP = IF_RESULT_TOO_DEEP,
789 SIDE_EFFECTS = IF_RESULT_SIDE_EFFECT,
790 PHI_FOUND = IF_RESULT_SIDE_EFFECT_PHI,
791 DENIED = IF_RESULT_DENIED
795 * Decides, if a given expression and its subexpressions
796 * (to certain, also given extent) can be moved to a block.
798 * @param expr The expression to examine.
799 * @param block The block where the expression should go.
800 * @param depth The current depth, passed recursively. Use 0 for
801 * non-recursive calls.
802 * @param info The options for createing Mux nodes.
805 * @return a failure reason
807 static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, const opt_if_conv_info_t *info)
811 ir_node *expr_block = get_nodes_block(expr);
814 * If we are forced to look too deep into the expression,
815 * treat it like it could not be moved.
817 if(depth >= info->max_depth) {
823 * If the block of the expression dominates the specified
824 * destination block, it does not matter if the expression
825 * has side effects or anything else. It is executed on each
826 * path the destination block is reached.
828 if (block_dominates(expr_block, dest_block))
832 * We cannot move phis!
840 * This should be superfluous and could be converted into a assertion.
841 * The destination block _must_ dominate the block of the expression,
842 * else the expression could be used without its definition.
844 if (! block_dominates(dest_block, expr_block)) {
845 res = IF_RESULT_SIDE_EFFECT;
850 * Surely, if the expression does not have a data mode, it is not
851 * movable. Perhaps one should also test the floating property of
854 if (has_side_effects(expr)) {
855 res = IF_RESULT_SIDE_EFFECT;
860 * If the node looks alright so far, look at its operands and
861 * check them out. If one of them cannot be moved, this one
862 * cannot be moved either.
864 for (i = 0, n = get_irn_arity(expr); i < n; ++i) {
865 ir_node *op = get_irn_n(expr, i);
866 int new_depth = is_Proj(op) ? depth : depth + 1;
868 res = _can_move_to(op, dest_block, new_depth, info);
875 DBG((dbg, LEVEL_3, "\t\t\tcan move to %n: %d\n", expr, res));
881 * Convenience function for _can_move_to.
882 * Checks, if an expression can be moved to another block. The check can
883 * be limited to a expression depth meaning if we need to crawl in
884 * deeper into an expression than a given threshold to examine if
885 * it can be moved, the expression is rejected and the test returns
888 * @param expr The expression to check for.
889 * @param dest_block The destination block you want @p expr to be.
890 * @param info The options for createing Mux nodes.
892 * @return return a failure reason
894 static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, const opt_if_conv_info_t *info)
896 return _can_move_to(expr, dest_block, 0, info);
900 * move a DAG given by a root node expr into a new block
902 * @param expr the root of a dag
903 * @param dest_block the destination block
905 static void move_to(ir_node *expr, ir_node *dest_block)
908 ir_node *expr_block = get_nodes_block(expr);
911 * If we reached the dominator, we are done.
912 * We will never put code through the dominator
914 if (block_dominates(expr_block, dest_block))
917 for (i = 0, n = get_irn_arity(expr); i < n; ++i)
918 move_to(get_irn_n(expr, i), dest_block);
920 set_nodes_block(expr, dest_block);
924 * return the common dominator of two blocks
926 static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2)
928 if(block_dominates(b1, b2))
930 else if(block_dominates(b2, b1))
935 for (p = get_Block_idom(b1); !block_dominates(p, b2); p = get_Block_idom(p));
941 * Information about a cond node.
943 typedef struct _cond_t {
944 ir_node *cond; /**< The cond node. */
945 struct list_head list; /**< List head which is used for queuing this cond
946 into the cond bunch it belongs to. */
948 unsigned totally_covers : 1;
949 struct _cond_t *link;
953 * Information about the both 'branches'
954 * (true and false), the cond creates.
957 int pos; /**< Number of the predecessor of the
958 phi block by which this branch is
959 reached. It is -1, if this branch is
960 only reached through another cond. */
962 struct _cond_t *masked_by; /**< If this cond's branch is only reached
963 through another cond, we store this
964 cond ir_node here. */
969 * retrieve the conditional information from a Cond node
971 static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
976 return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
980 typedef void (cond_walker_t)(cond_t *cond, void *env);
982 static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
983 long visited_nr, void *env)
987 if(cond->visited_nr >= visited_nr)
990 cond->visited_nr = visited_nr;
995 for(i = 0; i < 2; ++i) {
996 cond_t *c = cond->cases[i].masked_by;
999 _walk_conds(c, pre, post, visited_nr, env);
1006 static long cond_visited_nr = 0;
1008 static void walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post, void *env)
1010 _walk_conds(cond, pre, post, ++cond_visited_nr, env);
1013 static void link_conds(cond_t *cond, void *env)
1015 cond_t **ptr = (cond_t **) env;
1022 * Compare two conds for use in a firm set.
1023 * Two cond_t's are equal, if they designate the same cond node.
1024 * @param a A cond_t.
1025 * @param b Another one.
1026 * @param size Not used.
1027 * @return 0 (!) if they are equal, != 0 otherwise.
1029 static int cond_cmp(const void *a, const void *b, size_t size)
1031 const cond_t *x = a;
1032 const cond_t *y = b;
1033 return x->cond != y->cond;
1037 * Information about conds which can be made to muxes.
1038 * Instances of this struct are attached to the link field of
1039 * blocks in which phis are located.
1041 typedef struct _cond_info_t {
1042 struct list_head list; /**< Used to list all of these structs per class. */
1044 struct list_head roots; /**< A list of non-depending Conds. Two Conds are
1045 independent, if it's not possible not reach one from the
1046 other (all Conds in this list have to dominate the
1047 block this struct is attached to). */
1049 ir_node *first_phi; /**< The first phi node this cond info was made for. */
1050 set *cond_set; /**< A set of all dominating reachable Conds. */
1056 static void _find_conds(ir_node *irn, unsigned long visited_nr,
1057 ir_node *dominator, cond_t *masked_by, int pos, int depth, cond_info_t *ci)
1060 int saw_select_cond = 0;
1062 block = get_nodes_block(irn);
1065 * Only check this block if it is dominated by the specified
1066 * dominator or it has not been visited yet.
1068 if (block_dominates(dominator, block) && get_Block_block_visited(block) < visited_nr) {
1069 cond_t *res = masked_by;
1072 /* check, if we're on a ProjX
1074 * Further, the ProjX/Cond block must dominate the base block
1075 * (the block with the phi in it), otherwise, the Cond
1076 * is not affecting the phi so that a mux can be inserted.
1078 if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
1080 int proj = get_Proj_proj(irn);
1081 ir_node *cond = get_Proj_pred(irn);
1083 /* true, if the mode is a mode_b cond _NO_ switch cond */
1084 int is_modeb_cond = get_irn_opcode(cond) == iro_Cond
1085 && get_irn_mode(get_Cond_selector(cond)) == mode_b;
1087 saw_select_cond = !is_modeb_cond;
1089 /* Check, if the pred of the proj is a Cond
1090 * with a Projb as selector.
1095 memset(&c, 0, sizeof(c));
1098 c.cases[0].pos = -1;
1099 c.cases[1].pos = -1;
1101 /* get or insert the cond info into the set. */
1102 res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
1105 * If this cond is already masked by the masked_by cond
1106 * return immediately, since we don't have anything to add.
1108 if(masked_by && res->cases[proj].masked_by == masked_by)
1113 list_add(&res->list, &ci->roots);
1117 * Set masked by (either NULL or another cond node.
1118 * If this cond is truly masked by another one, set
1119 * the position of the actually investigated branch
1120 * to -1. Since the cond is masked by another one,
1121 * there could be more ways from the start block
1122 * to this branch, so we choose -1.
1124 res->cases[proj].masked_by = masked_by;
1127 res->cases[proj].pos = pos;
1130 * Since the masked_by nodes masks a cond, remove it from the
1131 * root list of the conf trees.
1134 assert(res->cases[proj].pos < 0);
1135 list_del_init(&masked_by->list);
1138 DBG((dbg, LEVEL_2, "%n (%s branch) "
1139 "for pos %d in block %n reached by %n\n",
1140 cond, proj ? "true" : "false", pos,
1141 block, masked_by ? masked_by->cond : NULL));
1145 if(get_Block_block_visited(block) < visited_nr && !saw_select_cond) {
1147 set_Block_block_visited(block, visited_nr);
1149 /* Search recursively from this cond. */
1150 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1151 ir_node *pred = get_irn_n(block, i);
1154 * If the depth is 0 (the first recursion), we set the pos to
1155 * the current viewed predecessor, else we adopt the position
1156 * as given by the caller. We also increase the depth for the
1157 * recursively called functions.
1159 _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci);
1167 * A convenience function for _find_conds.
1168 * It sets some parameters needed for recursion to appropriate start
1169 * values. Always use this function.
1171 * @param irn The node to start looking for Conds from. This might
1172 * be the phi node we are investigating.
1173 * @param conds The set to record the found Conds in.
1175 static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
1178 unsigned long visited_nr;
1179 ir_node *block = get_nodes_block(irn);
1180 ir_node *dom = get_Block_idom(block);
1182 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1183 ir_node *pred = get_irn_n(block, i);
1185 inc_irg_block_visited(current_ir_graph);
1186 visited_nr = get_irg_block_visited(current_ir_graph);
1187 set_Block_block_visited(block, visited_nr);
1189 DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
1190 _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
1195 * Make the mux for a given cond.
1197 * @param phi The phi node which shall be replaced by a mux.
1198 * @param dom The block where the muxes shall be placed.
1199 * @param cond The cond information.
1200 * @param info The options for createing Mux nodes.
1201 * @return The mux node made for this cond.
1203 static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond,
1204 const opt_if_conv_info_t *info, ir_node **mux, bitset_t *positions,
1205 int *muxes_made, long visited_nr)
1208 ir_node *projb = get_Cond_selector(cond->cond);
1209 ir_node *bl = get_nodes_block(cond->cond);
1210 ir_node *operands[2];
1213 cond->visited_nr = visited_nr;
1214 DBG((dbg, LEVEL_2, "%n\n", cond->cond));
1215 for(i = 0; i < 2; ++i) {
1216 cond_t *masked_by = cond->cases[i].masked_by;
1217 int pos = cond->cases[i].pos;
1223 * If this Cond branch is masked by another cond, make the mux
1224 * for that Cond first, since the Mux for this cond takes
1229 DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
1230 if(masked_by->visited_nr < visited_nr)
1231 operands[i] = make_mux_on_demand(phi, dom, masked_by, info, mux, positions, muxes_made, visited_nr);
1235 * If this cond branch is not masked by another cond, take
1236 * the corresponding phi operand as an operand to the mux.
1239 operands[i] = get_irn_n(phi, pos);
1245 * Move the operands to the dominator block if the cond
1246 * made sense. Some Conds found are not suitable for making a mux
1247 * out of them, since one of their branches cannot be reached from
1248 * the phi block. In that case we do not make a mux and return NULL.
1250 if(operands[0] && operands[1]) {
1251 if (operands[0] == operands[1]) {
1252 /* there is no gain in using mux in this case, as
1253 it will be optimized away. We will NOT move the
1254 content of the blocks either
1256 for (i = 0; i < 2; ++i)
1258 bitset_set(positions, set[i]);
1264 can_move[0] = can_move_to(operands[0], bl, info);
1265 can_move[1] = can_move_to(operands[1], bl, info);
1267 if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) {
1268 if (info->allow_mux(projb, operands[0], operands[1])) {
1269 move_to(operands[0], bl);
1270 move_to(operands[1], bl);
1273 *mux = new_r_Mux(current_ir_graph, bl, projb,
1274 operands[0], operands[1], get_irn_mode(operands[0]));
1278 DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
1279 *mux, projb, operands[0], operands[1], set[0], set[1]));
1281 for(i = 0; i < 2; ++i)
1283 bitset_set(positions, set[i]);
1285 /* we have done one */
1286 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_SUCCESS);
1290 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_DENIED);
1294 if(can_move[0] != SUCCESS)
1295 hook_if_conversion(current_ir_graph, phi, set[0], NULL, can_move[0]);
1296 if(can_move[1] != SUCCESS)
1297 hook_if_conversion(current_ir_graph, phi, set[1], NULL, can_move[1]);
1302 hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF);
1304 hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF);
1310 typedef struct _phi_info_t {
1311 struct list_head list;
1312 cond_info_t *cond_info;
1318 * Examine a phi node if it can be replaced by some muxes.
1319 * @param irn A phi node.
1320 * @param info Parameters for the if conversion algorithm.
1322 static int check_out_phi(phi_info_t *phi_info, const opt_if_conv_info_t *info)
1324 ir_node *irn = phi_info->irn;
1325 ir_node *block, *nw;
1326 cond_info_t *cond_info = phi_info->cond_info;
1330 bitset_t *positions;
1332 block = get_nodes_block(irn);
1333 arity = get_irn_arity(irn);
1334 positions = bitset_alloca(arity);
1336 assert(is_Phi(irn));
1337 assert(get_irn_arity(irn) == get_irn_arity(block));
1340 DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
1342 list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
1343 ir_node *cidom = block;
1344 ir_node *mux = NULL;
1345 cond_t *p, *head = NULL;
1348 bitset_clear_all(positions);
1350 DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
1352 * Link all conds which are in the subtree of
1353 * the current cond in the list together.
1355 walk_conds(cond, link_conds, NULL, &head);
1358 for(p = head; p; p = p->link) {
1359 for(i = 0; i < 2; ++i) {
1360 int pos = p->cases[i].pos;
1362 cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
1366 DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
1367 make_mux_on_demand(irn, cidom, cond, info, &mux, positions, &muxes_made, ++cond_visited_nr);
1370 bitset_foreach(positions, pos)
1371 set_irn_n(irn, (int) pos, mux);
1376 * optimize the phi away. This can anable further runs of this
1377 * function. Look at _can_move. phis cannot be moved there.
1379 nw = optimize_in_place_2(irn);
1386 typedef struct _cond_walk_info_t {
1387 struct obstack *obst;
1388 struct list_head cond_info_head;
1389 struct list_head phi_head;
1393 static void annotate_cond_info_pre(ir_node *irn, void *data)
1395 set_irn_link(irn, NULL);
1398 static void annotate_cond_info_post(ir_node *irn, void *data)
1400 cond_walk_info_t *cwi = data;
1403 * Check, if the node is a phi
1404 * we then compute a set of conds which are reachable from this
1405 * phi's block up to its dominator.
1406 * The set is attached to the blocks link field.
1408 if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
1409 ir_node *block = get_nodes_block(irn);
1411 cond_info_t *ci = get_irn_link(block);
1413 /* If the set is not yet computed, do it now. */
1415 ci = obstack_alloc(cwi->obst, sizeof(*ci));
1416 ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
1417 ci->first_phi = irn;
1419 INIT_LIST_HEAD(&ci->roots);
1420 INIT_LIST_HEAD(&ci->list);
1423 * Add this cond info to the list of all cond infos
1424 * in this graph. This is just done to xfree the
1425 * set easier afterwards (we save an irg_walk_graph).
1427 list_add(&cwi->cond_info_head, &ci->list);
1429 DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
1432 * Fill the set with conds we find on the way from
1433 * the block to its dominator.
1435 find_conds(irn, ci);
1438 * If there where no suitable conds, delete the set
1439 * immediately and reset the set pointer to NULL
1441 if(set_count(ci->cond_set) == 0) {
1442 del_set(ci->cond_set);
1443 list_del(&ci->list);
1444 obstack_free(cwi->obst, ci);
1450 DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
1452 set_irn_link(block, ci);
1455 phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
1458 INIT_LIST_HEAD(&pi->list);
1459 list_add(&pi->list, &cwi->phi_head);
1465 static void dump_conds(cond_t *cond, void *env)
1470 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
1471 cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
1472 get_nodes_block(cond->cond));
1474 for(i = 0; i < 2; ++i)
1475 if(cond->cases[i].masked_by)
1476 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
1477 cond, cond->cases[i].masked_by, i);
1480 static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi)
1485 snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
1487 if((f = fopen(buf, "wt")) != NULL) {
1492 ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
1493 list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
1494 ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
1495 list_for_each_entry(cond_t, cond, &ci->roots, list) {
1496 walk_conds(cond, NULL, dump_conds, f);
1497 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
1501 list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
1502 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
1503 phi->irn, phi->irn, get_nodes_block(phi->irn));
1504 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
1510 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
1513 struct obstack obst;
1514 phi_info_t *phi_info;
1515 cond_info_t *cond_info;
1516 cond_walk_info_t cwi;
1518 opt_if_conv_info_t p;
1520 if(!get_opt_if_conversion())
1523 /* get the parameters */
1525 memcpy(&p, params, sizeof(p));
1527 memcpy(&p, &default_info, sizeof(p));
1530 p.allow_mux = default_info.allow_mux;
1532 obstack_init(&obst);
1535 INIT_LIST_HEAD(&cwi.cond_info_head);
1536 INIT_LIST_HEAD(&cwi.phi_head);
1538 /* Init the debug stuff. */
1539 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
1541 firm_dbg_set_mask(dbg, LEVEL_1|LEVEL_2|LEVEL_3);
1544 /* if-conversion works better with normalized returns */
1545 normalize_one_return(irg);
1547 /* Ensure, that the dominators are computed. */
1550 DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
1551 get_entity_name(get_irg_entity(irg)), irg));
1554 * Collect information about the conds pu the phis on an obstack.
1555 * It is important that phi nodes which are 'higher' (with a
1556 * lower dfs pre order) are in front of the obstack. Since they are
1557 * possibly turned in to muxes this can enable the optimization
1560 irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
1563 vcg_dump_conds(irg, &cwi);
1566 /* Process each suitable phi found. */
1567 list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
1568 DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
1569 muxes_made += check_out_phi(phi_info, &p);
1572 list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
1573 del_set(cond_info->cond_set);
1576 DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
1578 obstack_free(&obst, NULL);
1580 dump_ir_block_graph(irg, "_ifconv_hack");