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_ifconv(ir_node *sel, ir_node* phi_list, int i, int j)
54 static const opt_if_conv_info_t default_info = {
55 0, /* doesn't matter for Psi */
60 * Additional block info.
62 typedef struct block_info {
63 ir_node *phi; /**< head of the Phi list */
64 int has_pinned; /**< set if the block contains instructions that cannot be moved */
67 #define get_block_blockinfo(block) ((block_info *)get_irn_link(block))
70 * Returns non-zero if a Block can be emptied.
72 static int can_empty_block(ir_node *block)
74 return !get_block_blockinfo(block)->has_pinned;
78 static ir_node* walk_to_projx(ir_node* start, const ir_node* dependency)
83 /* No need to find the conditional block if this block cannot be emptied and
86 if (!can_empty_block(start)) return NULL;
88 arity = get_irn_arity(start);
89 for (i = 0; i < arity; ++i) {
90 ir_node* pred = get_irn_n(start, i);
91 ir_node* pred_block = get_nodes_block(pred);
93 if (pred_block == dependency) {
95 assert(get_irn_mode(pred) == mode_X);
102 assert(get_irn_mode(pred) == mode_X);
106 if (is_cdep_on(pred_block, dependency)) {
107 return walk_to_projx(pred_block, dependency);
115 * Copies the DAG starting at node to the ith predecessor block of src_block
116 * -if the node isn't in the src_block, this is a nop and the node is returned
117 * -if the node is a phi in the src_block, the ith predecessor of the phi is
119 * otherwise returns the copy of the passed node
121 static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
128 if (get_nodes_block(node) != src_block) return node;
129 if (get_irn_op(node) == op_Phi) return get_irn_n(node, i);
131 copy = exact_copy(node);
132 dst_block = get_nodes_block(get_irn_n(src_block, i));
133 set_nodes_block(copy, dst_block);
135 DB((dbg, LEVEL_1, "Copying node %+F to block %+F, copy is %+F\n",
136 node, dst_block, copy));
138 arity = get_irn_arity(node);
139 for (j = 0; j < arity; ++j) {
140 set_irn_n(copy, j, copy_to(get_irn_n(node, j), src_block, i));
141 DB((dbg, LEVEL_2, "-- pred %d is %+F\n", j, get_irn_n(copy, j)));
148 * Remove predecessors i and j from node and add predecessor new_pred
150 static void rewire(ir_node* node, int i, int j, ir_node* new_pred)
152 int arity = get_irn_arity(node);
157 NEW_ARR_A(ir_node *, ins, arity - 1);
160 for (k = 0; k < i; ++k) ins[l++] = get_irn_n(node, k);
161 for (++k; k < j; ++k) ins[l++] = get_irn_n(node, k);
162 for (++k; k < arity; ++k) ins[l++] = get_irn_n(node, k);
164 assert(l == arity - 1);
165 set_irn_in(node, l, ins);
170 * Remove the jth predecessors from the ith predecessor of block and add it to block
172 static void split_block(ir_node* block, int i, int j)
174 ir_node* pred_block = get_nodes_block(get_irn_n(block, i));
175 int arity = get_irn_arity(block);
182 DB((dbg, LEVEL_1, "Splitting predecessor %d of predecessor %d of %+F\n", j, i, block));
184 NEW_ARR_A(ir_node*, ins, arity + 1);
186 for (phi = get_block_blockinfo(block)->phi; phi != NULL; phi = get_irn_link(phi)) {
187 ir_node* copy = copy_to(get_irn_n(phi, i), pred_block, j);
189 for (k = 0; k < i; ++k) ins[k] = get_irn_n(phi, k);
191 for (; k < arity; ++k) ins[k] = get_irn_n(phi, k);
192 ins[k] = get_irn_n(phi, i);
194 set_irn_in(phi, arity + 1, ins);
197 for (k = 0; k < i; ++k) ins[k] = get_irn_n(block, k);
198 ins[k++] = get_irn_n(pred_block, j);
199 for (; k < arity; ++k) ins[k] = get_irn_n(block, k);
200 ins[k] = get_irn_n(block, i);
202 set_irn_in(block, arity + 1, ins);
204 new_pred_arity = get_irn_arity(pred_block) - 1;
205 NEW_ARR_A(ir_node*, pred_ins, new_pred_arity);
207 for (phi = get_block_blockinfo(pred_block)->phi; phi != NULL; phi = get_irn_link(phi)) {
208 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(phi, k);
209 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(phi, k + 1);
210 assert(k == new_pred_arity);
211 if (new_pred_arity > 1) {
212 set_irn_in(phi, new_pred_arity, pred_ins);
214 exchange(phi, pred_ins[0]);
218 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(pred_block, k);
219 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(pred_block, k + 1);
220 assert(k == new_pred_arity);
221 if (new_pred_arity > 1) {
222 set_irn_in(pred_block, new_pred_arity, pred_ins);
224 exchange(pred_block, get_nodes_block(pred_ins[0]));
229 static void prepare_path(ir_node* block, int i, const ir_node* dependency)
231 ir_node* pred = get_nodes_block(get_irn_n(block, i));
235 DB((dbg, LEVEL_1, "Preparing predecessor %d of %+F\n", i, block));
237 pred_arity = get_irn_arity(pred);
238 for (j = 0; j < pred_arity; ++j) {
239 ir_node* pred_pred = get_nodes_block(get_irn_n(pred, j));
241 if (is_cdep_on(pred_pred, dependency)) {
242 prepare_path(pred, j, dependency);
243 split_block(block, i, j);
250 static void if_conv_walker(ir_node* block, void* env)
254 opt_if_conv_info_t *opt_info = env;
256 /* Bail out, if there are no Phis at all */
257 if (get_block_blockinfo(block)->phi == NULL) return;
260 arity = get_irn_arity(block);
261 for (i = 0; i < arity; ++i) {
265 pred = get_nodes_block(get_irn_n(block, i));
266 for (cdep = find_cdep(pred); cdep != NULL; cdep = cdep->next) {
267 const ir_node* dependency = cdep->node;
268 ir_node* projx0 = walk_to_projx(pred, dependency);
272 if (projx0 == NULL) continue;
274 cond = get_Proj_pred(projx0);
275 if (get_irn_op(cond) != op_Cond) continue;
277 /* We only handle boolean decisions, no switches */
278 if (get_irn_mode(get_Cond_selector(cond)) != mode_b) 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 phi = get_block_blockinfo(block)->phi;
297 if (!opt_info->allow_ifconv(get_Cond_selector(cond), phi, i, j)) continue;
299 DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n",
303 prepare_path(block, i, dependency);
304 prepare_path(block, j, dependency);
305 arity = get_irn_arity(block);
307 conds[0] = get_Cond_selector(cond);
309 psi_block = get_nodes_block(cond);
311 ir_node* val_i = get_irn_n(phi, i);
312 ir_node* val_j = get_irn_n(phi, j);
314 if (val_i == val_j) {
316 DB((dbg, LEVEL_2, "Generating no psi, because both values are equal\n"));
318 /* Something is very fishy if two predecessors of a PhiM point into
319 * one block, but not at the same memory node
321 assert(get_irn_mode(phi) != mode_M);
322 if (get_Proj_proj(projx0) == pn_Cond_true) {
331 current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
333 DB((dbg, LEVEL_2, "Generating %+F for %+F\n", psi, phi));
336 /* only exchange if we have a Psi */
340 rewire(phi, i, j, psi);
343 phi = get_irn_link(phi);
344 } while (phi != NULL);
346 exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
347 exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
351 DB((dbg, LEVEL_1, "Welding block %+F and %+F\n", block, psi_block));
352 /* copy the block-info from the Psi-block to the block before merging */
353 get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
354 set_irn_link(block, get_irn_link(psi_block));
356 set_irn_in(block, get_irn_arity(psi_block), get_irn_in(psi_block) + 1);
357 exchange_cdep(psi_block, block);
358 exchange(psi_block, block);
360 DB((dbg, LEVEL_1, "Welding block %+F to %+F\n", block, psi_block));
361 get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
362 exchange(block, psi_block);
366 rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block));
375 * Block walker: add additional data
377 static void init_block_link(ir_node *block, void *env)
379 struct obstack *obst = env;
380 block_info *bi = obstack_alloc(obst, sizeof(*bi));
384 set_irn_link(block, bi);
389 * Daisy-chain all phis in a block
390 * If a non-movable node is encountered set the has_pinned flag
392 static void collect_phis(ir_node *node, void *env)
395 ir_node *block = get_nodes_block(node);
396 block_info *bi = get_block_blockinfo(block);
398 set_irn_link(node, bi->phi);
402 if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
404 * Ignore control flow nodes, these will be removed.
405 * This ignores Raise. That is surely bad. FIXME.
407 if (! is_cfop(node)) {
408 ir_node *block = get_nodes_block(node);
409 block_info *bi = get_block_blockinfo(block);
411 DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
420 * Transform multiple cascaded Psis into one Psi
422 static ir_node* fold_psi(ir_node* psi)
424 int arity = get_Psi_n_conds(psi);
435 for (i = 0; i < arity; ++i) {
436 n = get_Psi_val(psi, i);
437 if (get_irn_op(n) == op_Psi) {
438 new_arity += get_Psi_n_conds(n) + 1;
443 n = get_Psi_default(psi);
444 if (get_irn_op(n) == op_Psi) {
445 new_arity += get_Psi_n_conds(n);
448 if (arity == new_arity) return psi; // no attached Psis found
449 DB((dbg, LEVEL_1, "Folding %+F from %d to %d conds\n", psi, arity, new_arity));
451 NEW_ARR_A(ir_node *, conds, new_arity);
452 NEW_ARR_A(ir_node *, vals, new_arity + 1);
454 for (i = 0; i < arity; ++i) {
455 ir_node* c = get_Psi_cond(psi, i);
457 n = get_Psi_val(psi, i);
458 if (get_irn_op(n) == op_Psi) {
459 a = get_Psi_n_conds(n);
460 for (k = 0; k < a; ++k) {
461 conds[j] = new_r_And(
462 current_ir_graph, get_nodes_block(psi),
463 c, get_Psi_cond(n, k), mode_b
465 vals[j] = get_Psi_val(n, k);
469 vals[j] = get_Psi_default(n);
476 n = get_Psi_default(psi);
477 if (get_irn_op(n) == op_Psi) {
478 a = get_Psi_n_conds(n);
479 for (k = 0; k < a; ++k) {
480 conds[j] = get_Psi_cond(n, k);
481 vals[j] = get_Psi_val(n, k);
484 vals[j] = get_Psi_default(n);
488 assert(j == new_arity);
490 current_ir_graph, get_nodes_block(psi),
491 new_arity, conds, vals, get_irn_mode(psi)
493 DB((dbg, LEVEL_1, "Folded %+F into new %+F\n", psi, new_psi));
494 exchange(psi, new_psi);
500 * Merge consecutive psi inputs if the data inputs are the same
502 static ir_node* meld_psi(ir_node* psi)
504 int arity = get_Psi_n_conds(psi);
515 val = get_Psi_val(psi, 0);
516 DB((dbg, LEVEL_1, "Pred 0 of %+F is %+F\n", psi, val));
517 for (i = 1; i < arity; ++i) {
518 ir_node* v = get_Psi_val(psi, i);
519 DB((dbg, LEVEL_1, "Pred %2d of %+F is %+F\n", i, psi, v));
525 DB((dbg, LEVEL_1, "Default of %+F is %+F\n", psi, get_Psi_default(psi)));
526 if (val == get_Psi_default(psi)) --new_arity;
528 DB((dbg, LEVEL_1, "Melding Psi %+F from %d conds to %d\n", psi, arity, new_arity));
530 if (new_arity == arity) return psi;
532 /* If all data inputs of the Psi are equal, exchange the Psi with that value */
533 if (new_arity == 0) {
538 NEW_ARR_A(ir_node *, conds, new_arity);
539 NEW_ARR_A(ir_node *, vals, new_arity + 1);
540 cond = get_Psi_cond(psi, 0);
541 val = get_Psi_val(psi, 0);
543 for (i = 1; i < arity; ++i) {
544 ir_node* v = get_Psi_val(psi, i);
548 current_ir_graph, get_nodes_block(psi),
549 cond, get_Psi_cond(psi, i), mode_b
558 if (val != get_Psi_default(psi)) {
563 vals[j] = get_Psi_default(psi);
564 assert(j == new_arity);
566 current_ir_graph, get_nodes_block(psi),
567 new_arity, conds, vals, get_irn_mode(psi)
569 DB((dbg, LEVEL_1, "Molded %+F into %+F\n", psi, new_psi));
570 exchange(psi, new_psi);
576 * Split a Psi with multiple conditions into multiple Psis with one condtition
579 static ir_node* split_psi(ir_node* psi)
581 int arity = get_Psi_n_conds(psi);
587 if (arity == 1) return psi;
589 mode = get_irn_mode(psi);
590 block = get_nodes_block(psi);
591 rval = get_Psi_default(psi);
592 for (i = arity - 1; i >= 0; --i) {
596 conds[0] = get_Psi_cond(psi, i);
597 vals[0] = get_Psi_val(psi, i);
600 current_ir_graph, block, 1, conds, vals, mode
608 static void optimise_psis(ir_node* node, void* env)
610 if (get_irn_op(node) != op_Psi) return;
612 node = fold_psi(node);
615 node = meld_psi(node);
618 node = split_psi(node);
623 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
626 opt_if_conv_info_t p;
628 if (! get_opt_if_conversion())
631 /* get the parameters */
633 memcpy(&p, params, sizeof(p));
635 memcpy(&p, &default_info, sizeof(p));
637 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
639 DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
641 normalize_one_return(irg);
642 remove_critical_cf_edges(irg);
648 irg_block_walk_graph(irg, init_block_link, NULL, &obst);
649 irg_walk_graph(irg, collect_phis, NULL, NULL);
650 irg_block_walk_graph(irg, NULL, if_conv_walker, &p);
652 local_optimize_graph(irg);
654 irg_walk_graph(irg, NULL, optimise_psis, NULL);
656 obstack_free(&obst, NULL);
667 * Make Mux nodes from Conds where it its possible.
668 * @author Sebastian Hack
685 #include "irgraph_t.h"
686 #include "irnode_t.h"
690 #include "irmode_t.h"
691 #include "ircons_t.h"
696 #include "irflag_t.h"
698 #include "irprintf.h"
703 #include "bitfiddle.h"
710 * check, if a node is const and return its tarval or
711 * return a default tarval.
712 * @param cnst The node whose tarval to get.
713 * @param or The alternative tarval, if the node is no Const.
714 * @return The tarval of @p cnst, if the node is Const, @p otherwise.
716 static tarval *get_value_or(ir_node *cnst, tarval *or)
718 return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
723 * Try to optimize nested muxes into a dis- or conjunction
725 * @param mux The parent mux, which has muxes as operands.
726 * @return The replacement node for this mux. If the optimization is
727 * successful, this might be an And or Or node, if not, its the mux
730 static ir_node *optimize_mux_chain(ir_node *mux)
735 ir_mode *mode = get_irn_mode(mux);
740 * If we have no mux, or its mode is not integer, we
743 if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
747 null = get_mode_null(mode);
748 minus_one = tarval_sub(null, get_tarval_one(mode));
750 ops[0] = get_Mux_false(mux);
751 ops[1] = get_Mux_true(mux);
753 for(i = 0; i < 2; ++i) {
755 tarval *tva, *tvb, *tvd;
759 * A mux operand at the first position can be factored
760 * out, if the operands fulfill several conditions:
762 * mux(c1, mux(c2, a, b), d)
764 * This can be made into:
765 * 1) mux(c1, 0, d) | mux(c2, a, b)
766 * if a | d == d and b | d == d
768 * 2) mux(c1, -1, d) & mux(c2, a, b)
769 * if a & d == d and a & b == b
771 if(get_irn_op(ops[i]) == op_Mux) {
774 a = get_Mux_false(child_mux);
775 b = get_Mux_true(child_mux);
778 /* Try the or stuff */
779 tva = get_value_or(a, minus_one);
780 tvb = get_value_or(b, minus_one);
781 tvd = get_value_or(d, null);
783 if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
784 && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
786 ops[i] = new_Const(mode, null);
787 res = new_r_Or(current_ir_graph, get_nodes_block(mux),
788 mux, child_mux, mode);
792 /* If the or didn't go, try the and stuff */
793 tva = get_value_or(a, null);
794 tvb = get_value_or(b, null);
795 tvd = get_value_or(d, minus_one);
797 if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
798 && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
800 ops[i] = new_Const(mode, minus_one);
801 res = new_r_And(current_ir_graph, get_nodes_block(mux),
802 mux, child_mux, mode);
808 /* recursively optimize nested muxes. */
809 set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
810 set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
816 /***********************************************************
817 * The If conversion itself.
818 ***********************************************************/
820 /** allow every Mux to be created. */
821 static int default_allow_mux(ir_node *sel, ir_node *false_res, ir_node *true_res) {
828 static const opt_if_conv_info_t default_info = {
833 /** The debugging module. */
834 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
837 * A simple check for side effects upto an opcode of a ir node.
838 * @param irn The ir node to check,
839 * @return 1 if the opcode itself may produce side effects, 0 if not.
841 static INLINE int has_side_effects(const ir_node *irn)
843 ir_op *op = get_irn_op(irn);
848 return !mode_is_datab(get_irn_mode(irn));
852 * Possible failure reasons
854 enum failure_reason_t {
855 SUCCESS = IF_RESULT_SUCCESS,
856 TO_DEEP = IF_RESULT_TOO_DEEP,
857 SIDE_EFFECTS = IF_RESULT_SIDE_EFFECT,
858 PHI_FOUND = IF_RESULT_SIDE_EFFECT_PHI,
859 DENIED = IF_RESULT_DENIED
863 * Decides, if a given expression and its subexpressions
864 * (to certain, also given extent) can be moved to a block.
866 * @param expr The expression to examine.
867 * @param block The block where the expression should go.
868 * @param depth The current depth, passed recursively. Use 0 for
869 * non-recursive calls.
870 * @param info The options for createing Mux nodes.
873 * @return a failure reason
875 static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, const opt_if_conv_info_t *info)
879 ir_node *expr_block = get_nodes_block(expr);
882 * If we are forced to look too deep into the expression,
883 * treat it like it could not be moved.
885 if(depth >= info->max_depth) {
891 * If the block of the expression dominates the specified
892 * destination block, it does not matter if the expression
893 * has side effects or anything else. It is executed on each
894 * path the destination block is reached.
896 if (block_dominates(expr_block, dest_block))
900 * We cannot move phis!
908 * This should be superfluous and could be converted into a assertion.
909 * The destination block _must_ dominate the block of the expression,
910 * else the expression could be used without its definition.
912 if (! block_dominates(dest_block, expr_block)) {
913 res = IF_RESULT_SIDE_EFFECT;
918 * Surely, if the expression does not have a data mode, it is not
919 * movable. Perhaps one should also test the floating property of
922 if (has_side_effects(expr)) {
923 res = IF_RESULT_SIDE_EFFECT;
928 * If the node looks alright so far, look at its operands and
929 * check them out. If one of them cannot be moved, this one
930 * cannot be moved either.
932 for (i = 0, n = get_irn_arity(expr); i < n; ++i) {
933 ir_node *op = get_irn_n(expr, i);
934 int new_depth = is_Proj(op) ? depth : depth + 1;
936 res = _can_move_to(op, dest_block, new_depth, info);
943 DBG((dbg, LEVEL_3, "\t\t\tcan move to %n: %d\n", expr, res));
949 * Convenience function for _can_move_to.
950 * Checks, if an expression can be moved to another block. The check can
951 * be limited to a expression depth meaning if we need to crawl in
952 * deeper into an expression than a given threshold to examine if
953 * it can be moved, the expression is rejected and the test returns
956 * @param expr The expression to check for.
957 * @param dest_block The destination block you want @p expr to be.
958 * @param info The options for createing Mux nodes.
960 * @return return a failure reason
962 static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, const opt_if_conv_info_t *info)
964 return _can_move_to(expr, dest_block, 0, info);
968 * move a DAG given by a root node expr into a new block
970 * @param expr the root of a dag
971 * @param dest_block the destination block
973 static void move_to(ir_node *expr, ir_node *dest_block)
976 ir_node *expr_block = get_nodes_block(expr);
979 * If we reached the dominator, we are done.
980 * We will never put code through the dominator
982 if (block_dominates(expr_block, dest_block))
985 for (i = 0, n = get_irn_arity(expr); i < n; ++i)
986 move_to(get_irn_n(expr, i), dest_block);
988 set_nodes_block(expr, dest_block);
992 * return the common dominator of two blocks
994 static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2)
996 if(block_dominates(b1, b2))
998 else if(block_dominates(b2, b1))
1003 for (p = get_Block_idom(b1); !block_dominates(p, b2); p = get_Block_idom(p));
1009 * Information about a cond node.
1011 typedef struct _cond_t {
1012 ir_node *cond; /**< The cond node. */
1013 struct list_head list; /**< List head which is used for queuing this cond
1014 into the cond bunch it belongs to. */
1015 unsigned is_new : 1;
1016 unsigned totally_covers : 1;
1017 struct _cond_t *link;
1021 * Information about the both 'branches'
1022 * (true and false), the cond creates.
1025 int pos; /**< Number of the predecessor of the
1026 phi block by which this branch is
1027 reached. It is -1, if this branch is
1028 only reached through another cond. */
1030 struct _cond_t *masked_by; /**< If this cond's branch is only reached
1031 through another cond, we store this
1032 cond ir_node here. */
1037 * retrieve the conditional information from a Cond node
1039 static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
1044 return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
1048 typedef void (cond_walker_t)(cond_t *cond, void *env);
1050 static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
1051 long visited_nr, void *env)
1055 if(cond->visited_nr >= visited_nr)
1058 cond->visited_nr = visited_nr;
1063 for(i = 0; i < 2; ++i) {
1064 cond_t *c = cond->cases[i].masked_by;
1067 _walk_conds(c, pre, post, visited_nr, env);
1074 static long cond_visited_nr = 0;
1076 static void walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post, void *env)
1078 _walk_conds(cond, pre, post, ++cond_visited_nr, env);
1081 static void link_conds(cond_t *cond, void *env)
1083 cond_t **ptr = (cond_t **) env;
1090 * Compare two conds for use in a firm set.
1091 * Two cond_t's are equal, if they designate the same cond node.
1092 * @param a A cond_t.
1093 * @param b Another one.
1094 * @param size Not used.
1095 * @return 0 (!) if they are equal, != 0 otherwise.
1097 static int cond_cmp(const void *a, const void *b, size_t size)
1099 const cond_t *x = a;
1100 const cond_t *y = b;
1101 return x->cond != y->cond;
1105 * Information about conds which can be made to muxes.
1106 * Instances of this struct are attached to the link field of
1107 * blocks in which phis are located.
1109 typedef struct _cond_info_t {
1110 struct list_head list; /**< Used to list all of these structs per class. */
1112 struct list_head roots; /**< A list of non-depending Conds. Two Conds are
1113 independent, if it's not possible not reach one from the
1114 other (all Conds in this list have to dominate the
1115 block this struct is attached to). */
1117 ir_node *first_phi; /**< The first phi node this cond info was made for. */
1118 set *cond_set; /**< A set of all dominating reachable Conds. */
1124 static void _find_conds(ir_node *irn, unsigned long visited_nr,
1125 ir_node *dominator, cond_t *masked_by, int pos, int depth, cond_info_t *ci)
1128 int saw_select_cond = 0;
1130 block = get_nodes_block(irn);
1133 * Only check this block if it is dominated by the specified
1134 * dominator or it has not been visited yet.
1136 if (block_dominates(dominator, block) && get_Block_block_visited(block) < visited_nr) {
1137 cond_t *res = masked_by;
1140 /* check, if we're on a ProjX
1142 * Further, the ProjX/Cond block must dominate the base block
1143 * (the block with the phi in it), otherwise, the Cond
1144 * is not affecting the phi so that a mux can be inserted.
1146 if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
1148 int proj = get_Proj_proj(irn);
1149 ir_node *cond = get_Proj_pred(irn);
1151 /* true, if the mode is a mode_b cond _NO_ switch cond */
1152 int is_modeb_cond = get_irn_opcode(cond) == iro_Cond
1153 && get_irn_mode(get_Cond_selector(cond)) == mode_b;
1155 saw_select_cond = !is_modeb_cond;
1157 /* Check, if the pred of the proj is a Cond
1158 * with a Projb as selector.
1163 memset(&c, 0, sizeof(c));
1166 c.cases[0].pos = -1;
1167 c.cases[1].pos = -1;
1169 /* get or insert the cond info into the set. */
1170 res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
1173 * If this cond is already masked by the masked_by cond
1174 * return immediately, since we don't have anything to add.
1176 if(masked_by && res->cases[proj].masked_by == masked_by)
1181 list_add(&res->list, &ci->roots);
1185 * Set masked by (either NULL or another cond node.
1186 * If this cond is truly masked by another one, set
1187 * the position of the actually investigated branch
1188 * to -1. Since the cond is masked by another one,
1189 * there could be more ways from the start block
1190 * to this branch, so we choose -1.
1192 res->cases[proj].masked_by = masked_by;
1195 res->cases[proj].pos = pos;
1198 * Since the masked_by nodes masks a cond, remove it from the
1199 * root list of the conf trees.
1202 assert(res->cases[proj].pos < 0);
1203 list_del_init(&masked_by->list);
1206 DBG((dbg, LEVEL_2, "%n (%s branch) "
1207 "for pos %d in block %n reached by %n\n",
1208 cond, proj ? "true" : "false", pos,
1209 block, masked_by ? masked_by->cond : NULL));
1213 if(get_Block_block_visited(block) < visited_nr && !saw_select_cond) {
1215 set_Block_block_visited(block, visited_nr);
1217 /* Search recursively from this cond. */
1218 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1219 ir_node *pred = get_irn_n(block, i);
1222 * If the depth is 0 (the first recursion), we set the pos to
1223 * the current viewed predecessor, else we adopt the position
1224 * as given by the caller. We also increase the depth for the
1225 * recursively called functions.
1227 _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci);
1235 * A convenience function for _find_conds.
1236 * It sets some parameters needed for recursion to appropriate start
1237 * values. Always use this function.
1239 * @param irn The node to start looking for Conds from. This might
1240 * be the phi node we are investigating.
1241 * @param conds The set to record the found Conds in.
1243 static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
1246 unsigned long visited_nr;
1247 ir_node *block = get_nodes_block(irn);
1248 ir_node *dom = get_Block_idom(block);
1250 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1251 ir_node *pred = get_irn_n(block, i);
1253 inc_irg_block_visited(current_ir_graph);
1254 visited_nr = get_irg_block_visited(current_ir_graph);
1255 set_Block_block_visited(block, visited_nr);
1257 DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
1258 _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
1263 * Make the mux for a given cond.
1265 * @param phi The phi node which shall be replaced by a mux.
1266 * @param dom The block where the muxes shall be placed.
1267 * @param cond The cond information.
1268 * @param info The options for createing Mux nodes.
1269 * @return The mux node made for this cond.
1271 static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond,
1272 const opt_if_conv_info_t *info, ir_node **mux, bitset_t *positions,
1273 int *muxes_made, long visited_nr)
1276 ir_node *projb = get_Cond_selector(cond->cond);
1277 ir_node *bl = get_nodes_block(cond->cond);
1278 ir_node *operands[2];
1281 cond->visited_nr = visited_nr;
1282 DBG((dbg, LEVEL_2, "%n\n", cond->cond));
1283 for(i = 0; i < 2; ++i) {
1284 cond_t *masked_by = cond->cases[i].masked_by;
1285 int pos = cond->cases[i].pos;
1291 * If this Cond branch is masked by another cond, make the mux
1292 * for that Cond first, since the Mux for this cond takes
1297 DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
1298 if(masked_by->visited_nr < visited_nr)
1299 operands[i] = make_mux_on_demand(phi, dom, masked_by, info, mux, positions, muxes_made, visited_nr);
1303 * If this cond branch is not masked by another cond, take
1304 * the corresponding phi operand as an operand to the mux.
1307 operands[i] = get_irn_n(phi, pos);
1313 * Move the operands to the dominator block if the cond
1314 * made sense. Some Conds found are not suitable for making a mux
1315 * out of them, since one of their branches cannot be reached from
1316 * the phi block. In that case we do not make a mux and return NULL.
1318 if(operands[0] && operands[1]) {
1319 if (operands[0] == operands[1]) {
1320 /* there is no gain in using mux in this case, as
1321 it will be optimized away. We will NOT move the
1322 content of the blocks either
1324 for (i = 0; i < 2; ++i)
1326 bitset_set(positions, set[i]);
1332 can_move[0] = can_move_to(operands[0], bl, info);
1333 can_move[1] = can_move_to(operands[1], bl, info);
1335 if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) {
1336 if (info->allow_mux(projb, operands[0], operands[1])) {
1337 move_to(operands[0], bl);
1338 move_to(operands[1], bl);
1341 *mux = new_r_Mux(current_ir_graph, bl, projb,
1342 operands[0], operands[1], get_irn_mode(operands[0]));
1346 DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
1347 *mux, projb, operands[0], operands[1], set[0], set[1]));
1349 for(i = 0; i < 2; ++i)
1351 bitset_set(positions, set[i]);
1353 /* we have done one */
1354 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_SUCCESS);
1358 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_DENIED);
1362 if(can_move[0] != SUCCESS)
1363 hook_if_conversion(current_ir_graph, phi, set[0], NULL, can_move[0]);
1364 if(can_move[1] != SUCCESS)
1365 hook_if_conversion(current_ir_graph, phi, set[1], NULL, can_move[1]);
1370 hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF);
1372 hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF);
1378 typedef struct _phi_info_t {
1379 struct list_head list;
1380 cond_info_t *cond_info;
1386 * Examine a phi node if it can be replaced by some muxes.
1387 * @param irn A phi node.
1388 * @param info Parameters for the if conversion algorithm.
1390 static int check_out_phi(phi_info_t *phi_info, const opt_if_conv_info_t *info)
1392 ir_node *irn = phi_info->irn;
1393 ir_node *block, *nw;
1394 cond_info_t *cond_info = phi_info->cond_info;
1398 bitset_t *positions;
1400 block = get_nodes_block(irn);
1401 arity = get_irn_arity(irn);
1402 positions = bitset_alloca(arity);
1404 assert(is_Phi(irn));
1405 assert(get_irn_arity(irn) == get_irn_arity(block));
1408 DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
1410 list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
1411 ir_node *cidom = block;
1412 ir_node *mux = NULL;
1413 cond_t *p, *head = NULL;
1416 bitset_clear_all(positions);
1418 DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
1420 * Link all conds which are in the subtree of
1421 * the current cond in the list together.
1423 walk_conds(cond, link_conds, NULL, &head);
1426 for(p = head; p; p = p->link) {
1427 for(i = 0; i < 2; ++i) {
1428 int pos = p->cases[i].pos;
1430 cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
1434 DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
1435 make_mux_on_demand(irn, cidom, cond, info, &mux, positions, &muxes_made, ++cond_visited_nr);
1438 bitset_foreach(positions, pos)
1439 set_irn_n(irn, (int) pos, mux);
1444 * optimize the phi away. This can anable further runs of this
1445 * function. Look at _can_move. phis cannot be moved there.
1447 nw = optimize_in_place_2(irn);
1454 typedef struct _cond_walk_info_t {
1455 struct obstack *obst;
1456 struct list_head cond_info_head;
1457 struct list_head phi_head;
1461 static void annotate_cond_info_pre(ir_node *irn, void *data)
1463 set_irn_link(irn, NULL);
1466 static void annotate_cond_info_post(ir_node *irn, void *data)
1468 cond_walk_info_t *cwi = data;
1471 * Check, if the node is a phi
1472 * we then compute a set of conds which are reachable from this
1473 * phi's block up to its dominator.
1474 * The set is attached to the blocks link field.
1476 if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
1477 ir_node *block = get_nodes_block(irn);
1479 cond_info_t *ci = get_irn_link(block);
1481 /* If the set is not yet computed, do it now. */
1483 ci = obstack_alloc(cwi->obst, sizeof(*ci));
1484 ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
1485 ci->first_phi = irn;
1487 INIT_LIST_HEAD(&ci->roots);
1488 INIT_LIST_HEAD(&ci->list);
1491 * Add this cond info to the list of all cond infos
1492 * in this graph. This is just done to xfree the
1493 * set easier afterwards (we save an irg_walk_graph).
1495 list_add(&cwi->cond_info_head, &ci->list);
1497 DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
1500 * Fill the set with conds we find on the way from
1501 * the block to its dominator.
1503 find_conds(irn, ci);
1506 * If there where no suitable conds, delete the set
1507 * immediately and reset the set pointer to NULL
1509 if(set_count(ci->cond_set) == 0) {
1510 del_set(ci->cond_set);
1511 list_del(&ci->list);
1512 obstack_free(cwi->obst, ci);
1518 DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
1520 set_irn_link(block, ci);
1523 phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
1526 INIT_LIST_HEAD(&pi->list);
1527 list_add(&pi->list, &cwi->phi_head);
1533 static void dump_conds(cond_t *cond, void *env)
1538 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
1539 cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
1540 get_nodes_block(cond->cond));
1542 for(i = 0; i < 2; ++i)
1543 if(cond->cases[i].masked_by)
1544 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
1545 cond, cond->cases[i].masked_by, i);
1548 static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi)
1553 snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
1555 if((f = fopen(buf, "wt")) != NULL) {
1560 ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
1561 list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
1562 ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
1563 list_for_each_entry(cond_t, cond, &ci->roots, list) {
1564 walk_conds(cond, NULL, dump_conds, f);
1565 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
1569 list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
1570 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
1571 phi->irn, phi->irn, get_nodes_block(phi->irn));
1572 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
1578 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
1581 struct obstack obst;
1582 phi_info_t *phi_info;
1583 cond_info_t *cond_info;
1584 cond_walk_info_t cwi;
1586 opt_if_conv_info_t p;
1588 if(!get_opt_if_conversion())
1591 /* get the parameters */
1593 memcpy(&p, params, sizeof(p));
1595 memcpy(&p, &default_info, sizeof(p));
1598 p.allow_mux = default_info.allow_mux;
1600 obstack_init(&obst);
1603 INIT_LIST_HEAD(&cwi.cond_info_head);
1604 INIT_LIST_HEAD(&cwi.phi_head);
1606 /* Init the debug stuff. */
1607 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
1609 firm_dbg_set_mask(dbg, LEVEL_1|LEVEL_2|LEVEL_3);
1612 /* if-conversion works better with normalized returns */
1613 normalize_one_return(irg);
1615 /* Ensure, that the dominators are computed. */
1618 DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
1619 get_entity_name(get_irg_entity(irg)), irg));
1622 * Collect information about the conds pu the phis on an obstack.
1623 * It is important that phi nodes which are 'higher' (with a
1624 * lower dfs pre order) are in front of the obstack. Since they are
1625 * possibly turned in to muxes this can enable the optimization
1628 irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
1631 vcg_dump_conds(irg, &cwi);
1634 /* Process each suitable phi found. */
1635 list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
1636 DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
1637 muxes_made += check_out_phi(phi_info, &p);
1640 list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
1641 del_set(cond_info->cond_set);
1644 DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
1646 obstack_free(&obst, NULL);