3 * File name: ir/opt/ifconv.c
4 * Purpose: If conversion
5 * Author: Sebastian Hack.
8 * Copyright: (c) 1998-2005 Universität Karlsruhe
9 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
43 DEBUG_ONLY(firm_dbg_module_t *dbg);
45 static ir_node* walk_to_projx(ir_node* start)
49 pred = get_nodes_block(start);
51 /* if there are multiple control flow predecessors nothing sensible can be
53 if (get_irn_arity(pred) > 1) return NULL;
55 pred = get_irn_n(pred, 0);
56 if (get_irn_op(pred) == op_Proj) {
57 assert(get_irn_mode(pred) == mode_X);
65 * Additional block info.
67 typedef struct block_info {
68 ir_node *phi; /**< head of the Phi list */
69 int has_pinned; /**< set if the block contains instructions that cannot be moved */
72 #define get_block_blockinfo(block) ((block_info *)get_irn_link(block))
75 * Returns non-zero if a Block can be emptied.
77 static int can_empty_block(ir_node *block)
79 return !get_block_blockinfo(block)->has_pinned;
84 * Copies the DAG starting at node to the ith predecessor block of src_block
85 * -if the node isn't in the src_block, this is a nop and the node is returned
86 * -if the node is a phi in the src_block, the ith predecessor of the phi is
88 * otherwise returns the copy of the passed node
90 static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
97 if (get_nodes_block(node) != src_block) return node;
98 if (get_irn_op(node) == op_Phi) return get_irn_n(node, i);
100 copy_irn_to_irg(node, current_ir_graph);
101 copy = get_irn_link(node);
102 dst_block = get_nodes_block(get_irn_n(src_block, i));
103 set_nodes_block(copy, dst_block);
105 DB((dbg, LEVEL_1, "Copying node %+F to block %+F, copy is %+F\n",
106 node, dst_block, copy));
108 arity = get_irn_arity(node);
109 for (j = 0; j < arity; ++j) {
110 set_irn_n(copy, j, copy_to(get_irn_n(node, j), src_block, i));
111 DB((dbg, LEVEL_2, "-- pred %d is %+F\n", j, get_irn_n(copy, j)));
118 * Duplicate and move the contents of ith block predecessor into its
119 * predecessors if the block has multiple control dependencies and only one
121 * Also bail out if the block contains non-movable nodes, because later
122 * if-conversion would be pointless.
124 static int fission_block(ir_node* block, int i)
126 ir_node* pred = get_irn_n(block, i);
135 if (get_irn_op(pred) != op_Jmp) return 0;
136 pred_block = get_nodes_block(pred);
138 if (!has_multiple_cdep(pred_block)) return 0;
139 if (!can_empty_block(pred_block)) return 0;
141 DB((dbg, LEVEL_1, "Fissioning block %+F\n", pred_block));
143 pred_arity = get_irn_arity(pred_block);
144 arity = get_irn_arity(block);
145 info = get_block_blockinfo(block);
146 NEW_ARR_A(ir_node *, ins, arity + pred_arity - 1);
147 for (phi = info->phi; phi != NULL; phi = get_irn_link(phi)) {
148 for (j = 0; j < i; ++j) ins[j] = get_irn_n(phi, j);
149 for (j = 0; j < pred_arity; ++j) {
150 ins[i + j] = copy_to(get_irn_n(phi, i), pred_block, j);
152 for (j = i + 1; j < arity; ++j) {
153 ins[pred_arity - 1 + j] = get_irn_n(phi, j);
155 set_irn_in(phi, arity + pred_arity - 1, ins);
157 for (j = 0; j < i; ++j) ins[j] = get_irn_n(block, j);
158 for (j = 0; j < pred_arity; ++j) ins[i + j] = get_irn_n(pred_block, j);
159 for (j = i + 1; j < arity; ++j) ins[pred_arity - 1 + j] = get_irn_n(block, j);
160 set_irn_in(block, arity + pred_arity - 1, ins);
162 /* Kill all Phis in the fissioned block
163 * This is to make sure they're not kept alive
165 info = get_block_blockinfo(pred_block);
167 while (phi != NULL) {
168 ir_node* next = get_irn_link(phi);
169 exchange(phi, new_Bad());
177 * Remove predecessors i and j from node and add predecessor new_pred
179 static void rewire(ir_node* node, int i, int j, ir_node* new_pred)
181 int arity = get_irn_arity(node);
186 NEW_ARR_A(ir_node *, ins, arity - 1);
189 for (k = 0; k < i; ++k) ins[l++] = get_irn_n(node, k);
190 for (++k; k < j; ++k) ins[l++] = get_irn_n(node, k);
191 for (++k; k < arity; ++k) ins[l++] = get_irn_n(node, k);
193 assert(l == arity - 1);
194 set_irn_in(node, l, ins);
198 static void if_conv_walker(ir_node* block, void* env)
204 /* Bail out, if there are no Phis at all */
205 if (get_block_blockinfo(block)->phi == NULL) return;
208 arity = get_irn_arity(block);
209 for (i = 0; i < arity; ++i) {
210 if (fission_block(block, i)) goto restart;
214 arity = get_irn_arity(block);
215 for (i = 0; i < arity; ++i) {
221 projx0 = walk_to_projx(get_irn_n(block, i));
222 if (projx0 == NULL) return;
223 pred = get_Proj_pred(projx0);
224 if (get_irn_op(pred) != op_Cond || get_irn_mode(get_Cond_selector(pred)) != mode_b) continue;
227 if (!can_empty_block(get_nodes_block(get_irn_n(block, i)))) {
228 DB((dbg, LEVEL_1, "Cannot empty block %+F\n",
229 get_nodes_block(get_irn_n(block, i))
234 for (j = i + 1; j < arity; ++j) {
241 projx1 = walk_to_projx(get_irn_n(block, j));
242 if (projx1 == NULL) continue;
243 pred = get_Proj_pred(projx1);
244 if (get_irn_op(pred) != op_Cond || get_irn_mode(get_Cond_selector(pred)) != mode_b) continue;
245 if (pred != cond) continue;
246 DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n", cond, projx0, projx1));
248 if (!can_empty_block(get_nodes_block(get_irn_n(block, j)))) {
249 DB((dbg, LEVEL_1, "Cannot empty %+F\n", get_nodes_block(get_irn_n(block, j))));
253 conds[0] = get_Cond_selector(cond);
255 psi_block = get_nodes_block(cond);
256 phi = get_block_blockinfo(block)->phi;
258 ir_node* val_i = get_irn_n(phi, i);
259 ir_node* val_j = get_irn_n(phi, j);
261 if (val_i == val_j) {
263 DB((dbg, LEVEL_2, "Generating no psi, because both values are equal\n"));
265 /* Something is very fishy if two predecessors of a PhiM point into
266 * one block, but not at the same memory node
268 assert(get_irn_mode(phi) != mode_M);
269 if (get_Proj_proj(projx0) == pn_Cond_true) {
277 current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
279 DB((dbg, LEVEL_2, "Generating %+F for %+F\n", psi, phi));
285 rewire(phi, i, j, psi);
288 phi = get_irn_link(phi);
289 } while (phi != NULL);
291 exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
292 exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
295 DB((dbg, LEVEL_1, "Welding block %+F to %+F\n", block, psi_block));
296 get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
297 exchange(block, psi_block);
300 rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block));
308 * Block walker: add additional data
310 static void init_block_link(ir_node *block, void *env)
312 struct obstack *obst = env;
313 block_info *bi = obstack_alloc(obst, sizeof(*bi));
317 set_irn_link(block, bi);
322 * Daisy-chain all phis in a block
323 * If a non-movable node is encountered set the has_pinned flag
325 static void collect_phis(ir_node *node, void *env)
328 ir_node *block = get_nodes_block(node);
329 block_info *bi = get_block_blockinfo(block);
331 set_irn_link(node, bi->phi);
335 if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
337 * Ignore control flow nodes, these will be removed.
338 * This ignores Raise. That is surely bad. FIXME.
340 if (! is_cfop(node)) {
341 ir_node *block = get_nodes_block(node);
342 block_info *bi = get_block_blockinfo(block);
344 DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
353 * Transform multiple cascaded Psis into one Psi
355 static ir_node* fold_psi(ir_node* psi)
357 int arity = get_Psi_n_conds(psi);
368 for (i = 0; i < arity; ++i) {
369 n = get_Psi_val(psi, i);
370 if (get_irn_op(n) == op_Psi) {
371 new_arity += get_Psi_n_conds(n) + 1;
376 n = get_Psi_default(psi);
377 if (get_irn_op(n) == op_Psi) {
378 new_arity += get_Psi_n_conds(n);
381 if (arity == new_arity) return psi; // no attached Psis found
382 DB((dbg, LEVEL_1, "Folding %+F from %d to %d conds\n", psi, arity, new_arity));
384 NEW_ARR_A(ir_node *, conds, new_arity);
385 NEW_ARR_A(ir_node *, vals, new_arity + 1);
387 for (i = 0; i < arity; ++i) {
388 ir_node* c = get_Psi_cond(psi, i);
390 n = get_Psi_val(psi, i);
391 if (get_irn_op(n) == op_Psi) {
392 a = get_Psi_n_conds(n);
393 for (k = 0; k < a; ++k) {
394 conds[j] = new_r_And(
395 current_ir_graph, get_nodes_block(psi),
396 c, get_Psi_cond(n, k), mode_b
398 vals[j] = get_Psi_val(n, k);
402 vals[j] = get_Psi_default(n);
409 n = get_Psi_default(psi);
410 if (get_irn_op(n) == op_Psi) {
411 a = get_Psi_n_conds(n);
412 for (k = 0; k < a; ++k) {
413 conds[j] = get_Psi_cond(n, k);
414 vals[j] = get_Psi_val(n, k);
417 vals[j] = get_Psi_default(n);
421 assert(j == new_arity);
423 current_ir_graph, get_nodes_block(psi),
424 new_arity, conds, vals, get_irn_mode(psi)
426 DB((dbg, LEVEL_1, "Folded %+F into new %+F\n", psi, new_psi));
427 exchange(psi, new_psi);
433 * Merge consecutive psi inputs if the data inputs are the same
435 static ir_node* meld_psi(ir_node* psi)
437 int arity = get_Psi_n_conds(psi);
448 val = get_Psi_val(psi, 0);
449 DB((dbg, LEVEL_1, "Pred 0 of %+F is %+F\n", psi, val));
450 for (i = 1; i < arity; ++i) {
451 ir_node* v = get_Psi_val(psi, i);
452 DB((dbg, LEVEL_1, "Pred %2d of %+F is %+F\n", i, psi, v));
458 DB((dbg, LEVEL_1, "Default of %+F is %+F\n", psi, get_Psi_default(psi)));
459 if (val == get_Psi_default(psi)) --new_arity;
461 DB((dbg, LEVEL_1, "Melding Psi %+F from %d conds to %d\n", psi, arity, new_arity));
463 if (new_arity == arity) return psi;
465 /* If all data inputs of the Psi are equal, exchange the Psi with that value */
466 if (new_arity == 0) {
471 NEW_ARR_A(ir_node *, conds, new_arity);
472 NEW_ARR_A(ir_node *, vals, new_arity + 1);
473 cond = get_Psi_cond(psi, 0);
474 val = get_Psi_val(psi, 0);
476 for (i = 1; i < arity; ++i) {
477 ir_node* v = get_Psi_val(psi, i);
481 current_ir_graph, get_nodes_block(psi),
482 cond, get_Psi_cond(psi, i), mode_b
491 if (val != get_Psi_default(psi)) {
496 vals[j] = get_Psi_default(psi);
497 assert(j == new_arity);
499 current_ir_graph, get_nodes_block(psi),
500 new_arity, conds, vals, get_irn_mode(psi)
502 DB((dbg, LEVEL_1, "Molded %+F into %+F\n", psi, new_psi));
503 exchange(psi, new_psi);
509 * Split a Psi with multiple conditions into multiple Psis with one condtition
512 static ir_node* split_psi(ir_node* psi)
514 int arity = get_Psi_n_conds(psi);
520 if (arity == 1) return psi;
522 mode = get_irn_mode(psi);
523 block = get_nodes_block(psi);
524 rval = get_Psi_default(psi);
525 for (i = arity - 1; i >= 0; --i) {
529 conds[0] = get_Psi_cond(psi, i);
530 vals[0] = get_Psi_val(psi, i);
533 current_ir_graph, block, 1, conds, vals, mode
541 static void optimise_psis(ir_node* node, void* env)
543 if (get_irn_op(node) != op_Psi) return;
545 node = fold_psi(node);
548 node = meld_psi(node);
551 node = split_psi(node);
556 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
560 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
562 DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
564 dump_ir_block_graph(irg, "_00_pre");
566 normalize_one_return(irg);
567 remove_critical_cf_edges(irg);
569 dump_ir_block_graph(irg, "_01_normal");
575 irg_block_walk_graph(irg, init_block_link, NULL, &obst);
576 irg_walk_graph(irg, collect_phis, NULL, NULL);
577 irg_block_walk_graph(irg, NULL, if_conv_walker, NULL);
579 local_optimize_graph(irg);
580 dump_ir_block_graph(irg, "_02_ifconv");
582 irg_walk_graph(irg, NULL, optimise_psis, NULL);
584 dump_ir_block_graph(irg, "_03_postifconv");
586 obstack_free(&obst, NULL);
597 * Make Mux nodes from Conds where it its possible.
598 * @author Sebastian Hack
615 #include "irgraph_t.h"
616 #include "irnode_t.h"
620 #include "irmode_t.h"
621 #include "ircons_t.h"
626 #include "irflag_t.h"
628 #include "irprintf.h"
633 #include "bitfiddle.h"
640 * check, if a node is const and return its tarval or
641 * return a default tarval.
642 * @param cnst The node whose tarval to get.
643 * @param or The alternative tarval, if the node is no Const.
644 * @return The tarval of @p cnst, if the node is Const, @p otherwise.
646 static tarval *get_value_or(ir_node *cnst, tarval *or)
648 return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
653 * Try to optimize nested muxes into a dis- or conjunction
655 * @param mux The parent mux, which has muxes as operands.
656 * @return The replacement node for this mux. If the optimization is
657 * successful, this might be an And or Or node, if not, its the mux
660 static ir_node *optimize_mux_chain(ir_node *mux)
665 ir_mode *mode = get_irn_mode(mux);
670 * If we have no mux, or its mode is not integer, we
673 if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
677 null = get_mode_null(mode);
678 minus_one = tarval_sub(null, get_tarval_one(mode));
680 ops[0] = get_Mux_false(mux);
681 ops[1] = get_Mux_true(mux);
683 for(i = 0; i < 2; ++i) {
685 tarval *tva, *tvb, *tvd;
689 * A mux operand at the first position can be factored
690 * out, if the operands fulfill several conditions:
692 * mux(c1, mux(c2, a, b), d)
694 * This can be made into:
695 * 1) mux(c1, 0, d) | mux(c2, a, b)
696 * if a | d == d and b | d == d
698 * 2) mux(c1, -1, d) & mux(c2, a, b)
699 * if a & d == d and a & b == b
701 if(get_irn_op(ops[i]) == op_Mux) {
704 a = get_Mux_false(child_mux);
705 b = get_Mux_true(child_mux);
708 /* Try the or stuff */
709 tva = get_value_or(a, minus_one);
710 tvb = get_value_or(b, minus_one);
711 tvd = get_value_or(d, null);
713 if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
714 && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
716 ops[i] = new_Const(mode, null);
717 res = new_r_Or(current_ir_graph, get_nodes_block(mux),
718 mux, child_mux, mode);
722 /* If the or didn't go, try the and stuff */
723 tva = get_value_or(a, null);
724 tvb = get_value_or(b, null);
725 tvd = get_value_or(d, minus_one);
727 if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
728 && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
730 ops[i] = new_Const(mode, minus_one);
731 res = new_r_And(current_ir_graph, get_nodes_block(mux),
732 mux, child_mux, mode);
738 /* recursively optimize nested muxes. */
739 set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
740 set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
746 /***********************************************************
747 * The If conversion itself.
748 ***********************************************************/
750 /** allow every Mux to be created. */
751 static int default_allow_mux(ir_node *sel, ir_node *false_res, ir_node *true_res) {
758 static const opt_if_conv_info_t default_info = {
763 /** The debugging module. */
764 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
767 * A simple check for side effects upto an opcode of a ir node.
768 * @param irn The ir node to check,
769 * @return 1 if the opcode itself may produce side effects, 0 if not.
771 static INLINE int has_side_effects(const ir_node *irn)
773 ir_op *op = get_irn_op(irn);
778 return !mode_is_datab(get_irn_mode(irn));
782 * Possible failure reasons
784 enum failure_reason_t {
785 SUCCESS = IF_RESULT_SUCCESS,
786 TO_DEEP = IF_RESULT_TOO_DEEP,
787 SIDE_EFFECTS = IF_RESULT_SIDE_EFFECT,
788 PHI_FOUND = IF_RESULT_SIDE_EFFECT_PHI,
789 DENIED = IF_RESULT_DENIED
793 * Decides, if a given expression and its subexpressions
794 * (to certain, also given extent) can be moved to a block.
796 * @param expr The expression to examine.
797 * @param block The block where the expression should go.
798 * @param depth The current depth, passed recursively. Use 0 for
799 * non-recursive calls.
800 * @param info The options for createing Mux nodes.
803 * @return a failure reason
805 static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, const opt_if_conv_info_t *info)
809 ir_node *expr_block = get_nodes_block(expr);
812 * If we are forced to look too deep into the expression,
813 * treat it like it could not be moved.
815 if(depth >= info->max_depth) {
821 * If the block of the expression dominates the specified
822 * destination block, it does not matter if the expression
823 * has side effects or anything else. It is executed on each
824 * path the destination block is reached.
826 if (block_dominates(expr_block, dest_block))
830 * We cannot move phis!
838 * This should be superfluous and could be converted into a assertion.
839 * The destination block _must_ dominate the block of the expression,
840 * else the expression could be used without its definition.
842 if (! block_dominates(dest_block, expr_block)) {
843 res = IF_RESULT_SIDE_EFFECT;
848 * Surely, if the expression does not have a data mode, it is not
849 * movable. Perhaps one should also test the floating property of
852 if (has_side_effects(expr)) {
853 res = IF_RESULT_SIDE_EFFECT;
858 * If the node looks alright so far, look at its operands and
859 * check them out. If one of them cannot be moved, this one
860 * cannot be moved either.
862 for (i = 0, n = get_irn_arity(expr); i < n; ++i) {
863 ir_node *op = get_irn_n(expr, i);
864 int new_depth = is_Proj(op) ? depth : depth + 1;
866 res = _can_move_to(op, dest_block, new_depth, info);
873 DBG((dbg, LEVEL_3, "\t\t\tcan move to %n: %d\n", expr, res));
879 * Convenience function for _can_move_to.
880 * Checks, if an expression can be moved to another block. The check can
881 * be limited to a expression depth meaning if we need to crawl in
882 * deeper into an expression than a given threshold to examine if
883 * it can be moved, the expression is rejected and the test returns
886 * @param expr The expression to check for.
887 * @param dest_block The destination block you want @p expr to be.
888 * @param info The options for createing Mux nodes.
890 * @return return a failure reason
892 static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, const opt_if_conv_info_t *info)
894 return _can_move_to(expr, dest_block, 0, info);
898 * move a DAG given by a root node expr into a new block
900 * @param expr the root of a dag
901 * @param dest_block the destination block
903 static void move_to(ir_node *expr, ir_node *dest_block)
906 ir_node *expr_block = get_nodes_block(expr);
909 * If we reached the dominator, we are done.
910 * We will never put code through the dominator
912 if (block_dominates(expr_block, dest_block))
915 for (i = 0, n = get_irn_arity(expr); i < n; ++i)
916 move_to(get_irn_n(expr, i), dest_block);
918 set_nodes_block(expr, dest_block);
922 * return the common dominator of two blocks
924 static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2)
926 if(block_dominates(b1, b2))
928 else if(block_dominates(b2, b1))
933 for (p = get_Block_idom(b1); !block_dominates(p, b2); p = get_Block_idom(p));
939 * Information about a cond node.
941 typedef struct _cond_t {
942 ir_node *cond; /**< The cond node. */
943 struct list_head list; /**< List head which is used for queuing this cond
944 into the cond bunch it belongs to. */
946 unsigned totally_covers : 1;
947 struct _cond_t *link;
951 * Information about the both 'branches'
952 * (true and false), the cond creates.
955 int pos; /**< Number of the predecessor of the
956 phi block by which this branch is
957 reached. It is -1, if this branch is
958 only reached through another cond. */
960 struct _cond_t *masked_by; /**< If this cond's branch is only reached
961 through another cond, we store this
962 cond ir_node here. */
967 * retrieve the conditional information from a Cond node
969 static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
974 return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
978 typedef void (cond_walker_t)(cond_t *cond, void *env);
980 static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
981 long visited_nr, void *env)
985 if(cond->visited_nr >= visited_nr)
988 cond->visited_nr = visited_nr;
993 for(i = 0; i < 2; ++i) {
994 cond_t *c = cond->cases[i].masked_by;
997 _walk_conds(c, pre, post, visited_nr, env);
1004 static long cond_visited_nr = 0;
1006 static void walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post, void *env)
1008 _walk_conds(cond, pre, post, ++cond_visited_nr, env);
1011 static void link_conds(cond_t *cond, void *env)
1013 cond_t **ptr = (cond_t **) env;
1020 * Compare two conds for use in a firm set.
1021 * Two cond_t's are equal, if they designate the same cond node.
1022 * @param a A cond_t.
1023 * @param b Another one.
1024 * @param size Not used.
1025 * @return 0 (!) if they are equal, != 0 otherwise.
1027 static int cond_cmp(const void *a, const void *b, size_t size)
1029 const cond_t *x = a;
1030 const cond_t *y = b;
1031 return x->cond != y->cond;
1035 * Information about conds which can be made to muxes.
1036 * Instances of this struct are attached to the link field of
1037 * blocks in which phis are located.
1039 typedef struct _cond_info_t {
1040 struct list_head list; /**< Used to list all of these structs per class. */
1042 struct list_head roots; /**< A list of non-depending Conds. Two Conds are
1043 independent, if it's not possible not reach one from the
1044 other (all Conds in this list have to dominate the
1045 block this struct is attached to). */
1047 ir_node *first_phi; /**< The first phi node this cond info was made for. */
1048 set *cond_set; /**< A set of all dominating reachable Conds. */
1054 static void _find_conds(ir_node *irn, unsigned long visited_nr,
1055 ir_node *dominator, cond_t *masked_by, int pos, int depth, cond_info_t *ci)
1058 int saw_select_cond = 0;
1060 block = get_nodes_block(irn);
1063 * Only check this block if it is dominated by the specified
1064 * dominator or it has not been visited yet.
1066 if (block_dominates(dominator, block) && get_Block_block_visited(block) < visited_nr) {
1067 cond_t *res = masked_by;
1070 /* check, if we're on a ProjX
1072 * Further, the ProjX/Cond block must dominate the base block
1073 * (the block with the phi in it), otherwise, the Cond
1074 * is not affecting the phi so that a mux can be inserted.
1076 if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
1078 int proj = get_Proj_proj(irn);
1079 ir_node *cond = get_Proj_pred(irn);
1081 /* true, if the mode is a mode_b cond _NO_ switch cond */
1082 int is_modeb_cond = get_irn_opcode(cond) == iro_Cond
1083 && get_irn_mode(get_Cond_selector(cond)) == mode_b;
1085 saw_select_cond = !is_modeb_cond;
1087 /* Check, if the pred of the proj is a Cond
1088 * with a Projb as selector.
1093 memset(&c, 0, sizeof(c));
1096 c.cases[0].pos = -1;
1097 c.cases[1].pos = -1;
1099 /* get or insert the cond info into the set. */
1100 res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
1103 * If this cond is already masked by the masked_by cond
1104 * return immediately, since we don't have anything to add.
1106 if(masked_by && res->cases[proj].masked_by == masked_by)
1111 list_add(&res->list, &ci->roots);
1115 * Set masked by (either NULL or another cond node.
1116 * If this cond is truly masked by another one, set
1117 * the position of the actually investigated branch
1118 * to -1. Since the cond is masked by another one,
1119 * there could be more ways from the start block
1120 * to this branch, so we choose -1.
1122 res->cases[proj].masked_by = masked_by;
1125 res->cases[proj].pos = pos;
1128 * Since the masked_by nodes masks a cond, remove it from the
1129 * root list of the conf trees.
1132 assert(res->cases[proj].pos < 0);
1133 list_del_init(&masked_by->list);
1136 DBG((dbg, LEVEL_2, "%n (%s branch) "
1137 "for pos %d in block %n reached by %n\n",
1138 cond, proj ? "true" : "false", pos,
1139 block, masked_by ? masked_by->cond : NULL));
1143 if(get_Block_block_visited(block) < visited_nr && !saw_select_cond) {
1145 set_Block_block_visited(block, visited_nr);
1147 /* Search recursively from this cond. */
1148 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1149 ir_node *pred = get_irn_n(block, i);
1152 * If the depth is 0 (the first recursion), we set the pos to
1153 * the current viewed predecessor, else we adopt the position
1154 * as given by the caller. We also increase the depth for the
1155 * recursively called functions.
1157 _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci);
1165 * A convenience function for _find_conds.
1166 * It sets some parameters needed for recursion to appropriate start
1167 * values. Always use this function.
1169 * @param irn The node to start looking for Conds from. This might
1170 * be the phi node we are investigating.
1171 * @param conds The set to record the found Conds in.
1173 static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
1176 unsigned long visited_nr;
1177 ir_node *block = get_nodes_block(irn);
1178 ir_node *dom = get_Block_idom(block);
1180 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1181 ir_node *pred = get_irn_n(block, i);
1183 inc_irg_block_visited(current_ir_graph);
1184 visited_nr = get_irg_block_visited(current_ir_graph);
1185 set_Block_block_visited(block, visited_nr);
1187 DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
1188 _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
1193 * Make the mux for a given cond.
1195 * @param phi The phi node which shall be replaced by a mux.
1196 * @param dom The block where the muxes shall be placed.
1197 * @param cond The cond information.
1198 * @param info The options for createing Mux nodes.
1199 * @return The mux node made for this cond.
1201 static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond,
1202 const opt_if_conv_info_t *info, ir_node **mux, bitset_t *positions,
1203 int *muxes_made, long visited_nr)
1206 ir_node *projb = get_Cond_selector(cond->cond);
1207 ir_node *bl = get_nodes_block(cond->cond);
1208 ir_node *operands[2];
1211 cond->visited_nr = visited_nr;
1212 DBG((dbg, LEVEL_2, "%n\n", cond->cond));
1213 for(i = 0; i < 2; ++i) {
1214 cond_t *masked_by = cond->cases[i].masked_by;
1215 int pos = cond->cases[i].pos;
1221 * If this Cond branch is masked by another cond, make the mux
1222 * for that Cond first, since the Mux for this cond takes
1227 DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
1228 if(masked_by->visited_nr < visited_nr)
1229 operands[i] = make_mux_on_demand(phi, dom, masked_by, info, mux, positions, muxes_made, visited_nr);
1233 * If this cond branch is not masked by another cond, take
1234 * the corresponding phi operand as an operand to the mux.
1237 operands[i] = get_irn_n(phi, pos);
1243 * Move the operands to the dominator block if the cond
1244 * made sense. Some Conds found are not suitable for making a mux
1245 * out of them, since one of their branches cannot be reached from
1246 * the phi block. In that case we do not make a mux and return NULL.
1248 if(operands[0] && operands[1]) {
1249 if (operands[0] == operands[1]) {
1250 /* there is no gain in using mux in this case, as
1251 it will be optimized away. We will NOT move the
1252 content of the blocks either
1254 for (i = 0; i < 2; ++i)
1256 bitset_set(positions, set[i]);
1262 can_move[0] = can_move_to(operands[0], bl, info);
1263 can_move[1] = can_move_to(operands[1], bl, info);
1265 if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) {
1266 if (info->allow_mux(projb, operands[0], operands[1])) {
1267 move_to(operands[0], bl);
1268 move_to(operands[1], bl);
1271 *mux = new_r_Mux(current_ir_graph, bl, projb,
1272 operands[0], operands[1], get_irn_mode(operands[0]));
1276 DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
1277 *mux, projb, operands[0], operands[1], set[0], set[1]));
1279 for(i = 0; i < 2; ++i)
1281 bitset_set(positions, set[i]);
1283 /* we have done one */
1284 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_SUCCESS);
1288 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_DENIED);
1292 if(can_move[0] != SUCCESS)
1293 hook_if_conversion(current_ir_graph, phi, set[0], NULL, can_move[0]);
1294 if(can_move[1] != SUCCESS)
1295 hook_if_conversion(current_ir_graph, phi, set[1], NULL, can_move[1]);
1300 hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF);
1302 hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF);
1308 typedef struct _phi_info_t {
1309 struct list_head list;
1310 cond_info_t *cond_info;
1316 * Examine a phi node if it can be replaced by some muxes.
1317 * @param irn A phi node.
1318 * @param info Parameters for the if conversion algorithm.
1320 static int check_out_phi(phi_info_t *phi_info, const opt_if_conv_info_t *info)
1322 ir_node *irn = phi_info->irn;
1323 ir_node *block, *nw;
1324 cond_info_t *cond_info = phi_info->cond_info;
1328 bitset_t *positions;
1330 block = get_nodes_block(irn);
1331 arity = get_irn_arity(irn);
1332 positions = bitset_alloca(arity);
1334 assert(is_Phi(irn));
1335 assert(get_irn_arity(irn) == get_irn_arity(block));
1338 DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
1340 list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
1341 ir_node *cidom = block;
1342 ir_node *mux = NULL;
1343 cond_t *p, *head = NULL;
1346 bitset_clear_all(positions);
1348 DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
1350 * Link all conds which are in the subtree of
1351 * the current cond in the list together.
1353 walk_conds(cond, link_conds, NULL, &head);
1356 for(p = head; p; p = p->link) {
1357 for(i = 0; i < 2; ++i) {
1358 int pos = p->cases[i].pos;
1360 cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
1364 DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
1365 make_mux_on_demand(irn, cidom, cond, info, &mux, positions, &muxes_made, ++cond_visited_nr);
1368 bitset_foreach(positions, pos)
1369 set_irn_n(irn, (int) pos, mux);
1374 * optimize the phi away. This can anable further runs of this
1375 * function. Look at _can_move. phis cannot be moved there.
1377 nw = optimize_in_place_2(irn);
1384 typedef struct _cond_walk_info_t {
1385 struct obstack *obst;
1386 struct list_head cond_info_head;
1387 struct list_head phi_head;
1391 static void annotate_cond_info_pre(ir_node *irn, void *data)
1393 set_irn_link(irn, NULL);
1396 static void annotate_cond_info_post(ir_node *irn, void *data)
1398 cond_walk_info_t *cwi = data;
1401 * Check, if the node is a phi
1402 * we then compute a set of conds which are reachable from this
1403 * phi's block up to its dominator.
1404 * The set is attached to the blocks link field.
1406 if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
1407 ir_node *block = get_nodes_block(irn);
1409 cond_info_t *ci = get_irn_link(block);
1411 /* If the set is not yet computed, do it now. */
1413 ci = obstack_alloc(cwi->obst, sizeof(*ci));
1414 ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
1415 ci->first_phi = irn;
1417 INIT_LIST_HEAD(&ci->roots);
1418 INIT_LIST_HEAD(&ci->list);
1421 * Add this cond info to the list of all cond infos
1422 * in this graph. This is just done to xfree the
1423 * set easier afterwards (we save an irg_walk_graph).
1425 list_add(&cwi->cond_info_head, &ci->list);
1427 DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
1430 * Fill the set with conds we find on the way from
1431 * the block to its dominator.
1433 find_conds(irn, ci);
1436 * If there where no suitable conds, delete the set
1437 * immediately and reset the set pointer to NULL
1439 if(set_count(ci->cond_set) == 0) {
1440 del_set(ci->cond_set);
1441 list_del(&ci->list);
1442 obstack_free(cwi->obst, ci);
1448 DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
1450 set_irn_link(block, ci);
1453 phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
1456 INIT_LIST_HEAD(&pi->list);
1457 list_add(&pi->list, &cwi->phi_head);
1463 static void dump_conds(cond_t *cond, void *env)
1468 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
1469 cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
1470 get_nodes_block(cond->cond));
1472 for(i = 0; i < 2; ++i)
1473 if(cond->cases[i].masked_by)
1474 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
1475 cond, cond->cases[i].masked_by, i);
1478 static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi)
1483 snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
1485 if((f = fopen(buf, "wt")) != NULL) {
1490 ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
1491 list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
1492 ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
1493 list_for_each_entry(cond_t, cond, &ci->roots, list) {
1494 walk_conds(cond, NULL, dump_conds, f);
1495 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
1499 list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
1500 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
1501 phi->irn, phi->irn, get_nodes_block(phi->irn));
1502 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
1508 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
1511 struct obstack obst;
1512 phi_info_t *phi_info;
1513 cond_info_t *cond_info;
1514 cond_walk_info_t cwi;
1516 opt_if_conv_info_t p;
1518 if(!get_opt_if_conversion())
1521 /* get the parameters */
1523 memcpy(&p, params, sizeof(p));
1525 memcpy(&p, &default_info, sizeof(p));
1528 p.allow_mux = default_info.allow_mux;
1530 obstack_init(&obst);
1533 INIT_LIST_HEAD(&cwi.cond_info_head);
1534 INIT_LIST_HEAD(&cwi.phi_head);
1536 /* Init the debug stuff. */
1537 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
1539 firm_dbg_set_mask(dbg, LEVEL_1|LEVEL_2|LEVEL_3);
1542 /* if-conversion works better with normalized returns */
1543 normalize_one_return(irg);
1545 /* Ensure, that the dominators are computed. */
1548 DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
1549 get_entity_name(get_irg_entity(irg)), irg));
1552 * Collect information about the conds pu the phis on an obstack.
1553 * It is important that phi nodes which are 'higher' (with a
1554 * lower dfs pre order) are in front of the obstack. Since they are
1555 * possibly turned in to muxes this can enable the optimization
1558 irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
1561 vcg_dump_conds(irg, &cwi);
1564 /* Process each suitable phi found. */
1565 list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
1566 DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
1567 muxes_made += check_out_phi(phi_info, &p);
1570 list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
1571 del_set(cond_info->cond_set);
1574 DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
1576 obstack_free(&obst, NULL);
1578 dump_ir_block_graph(irg, "_ifconv_hack");