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 // Don't generate PsiMs
259 if (get_irn_mode(phi) == mode_M) {
260 /* Something is very fishy if to predecessors of a PhiM point into the
261 * block but not at the same memory node
263 assert(get_irn_n(phi, i) == get_irn_n(phi, j));
265 psi = get_irn_n(phi, i);
266 DB((dbg, LEVEL_2, "Handling memory Phi %+F\n", phi));
268 ir_node* val_i = get_irn_n(phi, i);
269 ir_node* val_j = get_irn_n(phi, j);
271 if (val_i == val_j) {
273 DB((dbg, LEVEL_2, "Generating no psi, because both values are equal\n"));
275 if (get_Proj_proj(projx0) == pn_Cond_true) {
283 current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
285 DB((dbg, LEVEL_2, "Generating %+F for %+F\n", psi, phi));
292 rewire(phi, i, j, psi);
295 phi = get_irn_link(phi);
296 } while (phi != NULL);
298 exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
299 exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
302 DB((dbg, LEVEL_1, "Welding block %+F to %+F\n", block, psi_block));
303 get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
304 exchange(block, psi_block);
307 rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block));
315 * Block walker: add additional data
317 static void init_block_link(ir_node *block, void *env)
319 struct obstack *obst = env;
320 block_info *bi = obstack_alloc(obst, sizeof(*bi));
324 set_irn_link(block, bi);
329 * Daisy-chain all phis in a block
330 * If a non-movable node is encountered set the has_pinned flag
332 static void collect_phis(ir_node *node, void *env)
335 ir_node *block = get_nodes_block(node);
336 block_info *bi = get_block_blockinfo(block);
338 set_irn_link(node, bi->phi);
342 if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
344 * Ignore control flow nodes, these will be removed.
345 * This ignores Raise. That is surely bad. FIXME.
347 if (! is_cfop(node)) {
348 ir_node *block = get_nodes_block(node);
349 block_info *bi = get_block_blockinfo(block);
351 DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
360 * Transform multiple cascaded Psis into one Psi
362 static ir_node* fold_psi(ir_node* psi)
364 int arity = get_Psi_n_conds(psi);
375 for (i = 0; i < arity; ++i) {
376 n = get_Psi_val(psi, i);
377 if (get_irn_op(n) == op_Psi) {
378 new_arity += get_Psi_n_conds(n) + 1;
383 n = get_Psi_default(psi);
384 if (get_irn_op(n) == op_Psi) {
385 new_arity += get_Psi_n_conds(n);
388 if (arity == new_arity) return psi; // no attached Psis found
389 DB((dbg, LEVEL_1, "Folding %+F from %d to %d conds\n", psi, arity, new_arity));
391 NEW_ARR_A(ir_node *, conds, new_arity);
392 NEW_ARR_A(ir_node *, vals, new_arity + 1);
394 for (i = 0; i < arity; ++i) {
395 ir_node* c = get_Psi_cond(psi, i);
397 n = get_Psi_val(psi, i);
398 if (get_irn_op(n) == op_Psi) {
399 a = get_Psi_n_conds(n);
400 for (k = 0; k < a; ++k) {
401 conds[j] = new_r_And(
402 current_ir_graph, get_nodes_block(psi),
403 c, get_Psi_cond(n, k), mode_b
405 vals[j] = get_Psi_val(n, k);
409 vals[j] = get_Psi_default(n);
416 n = get_Psi_default(psi);
417 if (get_irn_op(n) == op_Psi) {
418 a = get_Psi_n_conds(n);
419 for (k = 0; k < a; ++k) {
420 conds[j] = get_Psi_cond(n, k);
421 vals[j] = get_Psi_val(n, k);
424 vals[j] = get_Psi_default(n);
428 assert(j == new_arity);
430 current_ir_graph, get_nodes_block(psi),
431 new_arity, conds, vals, get_irn_mode(psi)
433 DB((dbg, LEVEL_1, "Folded %+F into new %+F\n", psi, new_psi));
434 exchange(psi, new_psi);
440 * Merge consecutive psi inputs if the data inputs are the same
442 static void meld_psi(ir_node* psi)
444 int arity = get_Psi_n_conds(psi);
455 val = get_Psi_val(psi, 0);
456 DB((dbg, LEVEL_1, "Pred 0 of %+F is %+F\n", psi, val));
457 for (i = 1; i < arity; ++i) {
458 ir_node* v = get_Psi_val(psi, i);
459 DB((dbg, LEVEL_1, "Pred %2d of %+F is %+F\n", i, psi, v));
465 DB((dbg, LEVEL_1, "Default of %+F is %+F\n", psi, get_Psi_default(psi)));
466 if (val == get_Psi_default(psi)) --new_arity;
468 DB((dbg, LEVEL_1, "Melding Psi %+F from %d conds to %d\n", psi, arity, new_arity));
470 if (new_arity == arity) return;
472 /* If all data inputs of the Psi are equal, exchange the Psi with that value */
473 if (new_arity == 0) {
478 NEW_ARR_A(ir_node *, conds, new_arity);
479 NEW_ARR_A(ir_node *, vals, new_arity + 1);
480 cond = get_Psi_cond(psi, 0);
481 val = get_Psi_val(psi, 0);
483 for (i = 1; i < arity; ++i) {
484 ir_node* v = get_Psi_val(psi, i);
488 current_ir_graph, get_nodes_block(psi),
489 cond, get_Psi_cond(psi, i), mode_b
498 if (val != get_Psi_default(psi)) {
503 vals[j] = get_Psi_default(psi);
504 assert(j == new_arity);
506 current_ir_graph, get_nodes_block(psi),
507 new_arity, conds, vals, get_irn_mode(psi)
509 DB((dbg, LEVEL_1, "Molded %+F into %+F\n", psi, new_psi));
510 exchange(psi, new_psi);
514 static void optimise_psis(ir_node* node, void* env)
516 if (get_irn_op(node) != op_Psi) return;
518 node = fold_psi(node);
526 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
530 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
532 DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
534 dump_ir_block_graph(irg, "_00_pre");
536 normalize_one_return(irg);
537 remove_critical_cf_edges(irg);
539 dump_ir_block_graph(irg, "_01_normal");
545 irg_block_walk_graph(irg, init_block_link, NULL, &obst);
546 irg_walk_graph(irg, collect_phis, NULL, NULL);
547 irg_block_walk_graph(irg, NULL, if_conv_walker, NULL);
549 local_optimize_graph(irg);
550 dump_ir_block_graph(irg, "_02_ifconv");
552 irg_walk_graph(irg, NULL, optimise_psis, NULL);
554 dump_ir_block_graph(irg, "_03_postifconv");
556 obstack_free(&obst, NULL);
567 * Make Mux nodes from Conds where it its possible.
568 * @author Sebastian Hack
585 #include "irgraph_t.h"
586 #include "irnode_t.h"
590 #include "irmode_t.h"
591 #include "ircons_t.h"
596 #include "irflag_t.h"
598 #include "irprintf.h"
603 #include "bitfiddle.h"
610 * check, if a node is const and return its tarval or
611 * return a default tarval.
612 * @param cnst The node whose tarval to get.
613 * @param or The alternative tarval, if the node is no Const.
614 * @return The tarval of @p cnst, if the node is Const, @p otherwise.
616 static tarval *get_value_or(ir_node *cnst, tarval *or)
618 return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
623 * Try to optimize nested muxes into a dis- or conjunction
625 * @param mux The parent mux, which has muxes as operands.
626 * @return The replacement node for this mux. If the optimization is
627 * successful, this might be an And or Or node, if not, its the mux
630 static ir_node *optimize_mux_chain(ir_node *mux)
635 ir_mode *mode = get_irn_mode(mux);
640 * If we have no mux, or its mode is not integer, we
643 if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
647 null = get_mode_null(mode);
648 minus_one = tarval_sub(null, get_tarval_one(mode));
650 ops[0] = get_Mux_false(mux);
651 ops[1] = get_Mux_true(mux);
653 for(i = 0; i < 2; ++i) {
655 tarval *tva, *tvb, *tvd;
659 * A mux operand at the first position can be factored
660 * out, if the operands fulfill several conditions:
662 * mux(c1, mux(c2, a, b), d)
664 * This can be made into:
665 * 1) mux(c1, 0, d) | mux(c2, a, b)
666 * if a | d == d and b | d == d
668 * 2) mux(c1, -1, d) & mux(c2, a, b)
669 * if a & d == d and a & b == b
671 if(get_irn_op(ops[i]) == op_Mux) {
674 a = get_Mux_false(child_mux);
675 b = get_Mux_true(child_mux);
678 /* Try the or stuff */
679 tva = get_value_or(a, minus_one);
680 tvb = get_value_or(b, minus_one);
681 tvd = get_value_or(d, null);
683 if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
684 && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
686 ops[i] = new_Const(mode, null);
687 res = new_r_Or(current_ir_graph, get_nodes_block(mux),
688 mux, child_mux, mode);
692 /* If the or didn't go, try the and stuff */
693 tva = get_value_or(a, null);
694 tvb = get_value_or(b, null);
695 tvd = get_value_or(d, minus_one);
697 if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
698 && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
700 ops[i] = new_Const(mode, minus_one);
701 res = new_r_And(current_ir_graph, get_nodes_block(mux),
702 mux, child_mux, mode);
708 /* recursively optimize nested muxes. */
709 set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
710 set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
716 /***********************************************************
717 * The If conversion itself.
718 ***********************************************************/
720 /** allow every Mux to be created. */
721 static int default_allow_mux(ir_node *sel, ir_node *false_res, ir_node *true_res) {
728 static const opt_if_conv_info_t default_info = {
733 /** The debugging module. */
734 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
737 * A simple check for side effects upto an opcode of a ir node.
738 * @param irn The ir node to check,
739 * @return 1 if the opcode itself may produce side effects, 0 if not.
741 static INLINE int has_side_effects(const ir_node *irn)
743 ir_op *op = get_irn_op(irn);
748 return !mode_is_datab(get_irn_mode(irn));
752 * Possible failure reasons
754 enum failure_reason_t {
755 SUCCESS = IF_RESULT_SUCCESS,
756 TO_DEEP = IF_RESULT_TOO_DEEP,
757 SIDE_EFFECTS = IF_RESULT_SIDE_EFFECT,
758 PHI_FOUND = IF_RESULT_SIDE_EFFECT_PHI,
759 DENIED = IF_RESULT_DENIED
763 * Decides, if a given expression and its subexpressions
764 * (to certain, also given extent) can be moved to a block.
766 * @param expr The expression to examine.
767 * @param block The block where the expression should go.
768 * @param depth The current depth, passed recursively. Use 0 for
769 * non-recursive calls.
770 * @param info The options for createing Mux nodes.
773 * @return a failure reason
775 static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, const opt_if_conv_info_t *info)
779 ir_node *expr_block = get_nodes_block(expr);
782 * If we are forced to look too deep into the expression,
783 * treat it like it could not be moved.
785 if(depth >= info->max_depth) {
791 * If the block of the expression dominates the specified
792 * destination block, it does not matter if the expression
793 * has side effects or anything else. It is executed on each
794 * path the destination block is reached.
796 if (block_dominates(expr_block, dest_block))
800 * We cannot move phis!
808 * This should be superfluous and could be converted into a assertion.
809 * The destination block _must_ dominate the block of the expression,
810 * else the expression could be used without its definition.
812 if (! block_dominates(dest_block, expr_block)) {
813 res = IF_RESULT_SIDE_EFFECT;
818 * Surely, if the expression does not have a data mode, it is not
819 * movable. Perhaps one should also test the floating property of
822 if (has_side_effects(expr)) {
823 res = IF_RESULT_SIDE_EFFECT;
828 * If the node looks alright so far, look at its operands and
829 * check them out. If one of them cannot be moved, this one
830 * cannot be moved either.
832 for (i = 0, n = get_irn_arity(expr); i < n; ++i) {
833 ir_node *op = get_irn_n(expr, i);
834 int new_depth = is_Proj(op) ? depth : depth + 1;
836 res = _can_move_to(op, dest_block, new_depth, info);
843 DBG((dbg, LEVEL_3, "\t\t\tcan move to %n: %d\n", expr, res));
849 * Convenience function for _can_move_to.
850 * Checks, if an expression can be moved to another block. The check can
851 * be limited to a expression depth meaning if we need to crawl in
852 * deeper into an expression than a given threshold to examine if
853 * it can be moved, the expression is rejected and the test returns
856 * @param expr The expression to check for.
857 * @param dest_block The destination block you want @p expr to be.
858 * @param info The options for createing Mux nodes.
860 * @return return a failure reason
862 static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, const opt_if_conv_info_t *info)
864 return _can_move_to(expr, dest_block, 0, info);
868 * move a DAG given by a root node expr into a new block
870 * @param expr the root of a dag
871 * @param dest_block the destination block
873 static void move_to(ir_node *expr, ir_node *dest_block)
876 ir_node *expr_block = get_nodes_block(expr);
879 * If we reached the dominator, we are done.
880 * We will never put code through the dominator
882 if (block_dominates(expr_block, dest_block))
885 for (i = 0, n = get_irn_arity(expr); i < n; ++i)
886 move_to(get_irn_n(expr, i), dest_block);
888 set_nodes_block(expr, dest_block);
892 * return the common dominator of two blocks
894 static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2)
896 if(block_dominates(b1, b2))
898 else if(block_dominates(b2, b1))
903 for (p = get_Block_idom(b1); !block_dominates(p, b2); p = get_Block_idom(p));
909 * Information about a cond node.
911 typedef struct _cond_t {
912 ir_node *cond; /**< The cond node. */
913 struct list_head list; /**< List head which is used for queuing this cond
914 into the cond bunch it belongs to. */
916 unsigned totally_covers : 1;
917 struct _cond_t *link;
921 * Information about the both 'branches'
922 * (true and false), the cond creates.
925 int pos; /**< Number of the predecessor of the
926 phi block by which this branch is
927 reached. It is -1, if this branch is
928 only reached through another cond. */
930 struct _cond_t *masked_by; /**< If this cond's branch is only reached
931 through another cond, we store this
932 cond ir_node here. */
937 * retrieve the conditional information from a Cond node
939 static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
944 return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
948 typedef void (cond_walker_t)(cond_t *cond, void *env);
950 static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
951 long visited_nr, void *env)
955 if(cond->visited_nr >= visited_nr)
958 cond->visited_nr = visited_nr;
963 for(i = 0; i < 2; ++i) {
964 cond_t *c = cond->cases[i].masked_by;
967 _walk_conds(c, pre, post, visited_nr, env);
974 static long cond_visited_nr = 0;
976 static void walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post, void *env)
978 _walk_conds(cond, pre, post, ++cond_visited_nr, env);
981 static void link_conds(cond_t *cond, void *env)
983 cond_t **ptr = (cond_t **) env;
990 * Compare two conds for use in a firm set.
991 * Two cond_t's are equal, if they designate the same cond node.
993 * @param b Another one.
994 * @param size Not used.
995 * @return 0 (!) if they are equal, != 0 otherwise.
997 static int cond_cmp(const void *a, const void *b, size_t size)
1000 const cond_t *y = b;
1001 return x->cond != y->cond;
1005 * Information about conds which can be made to muxes.
1006 * Instances of this struct are attached to the link field of
1007 * blocks in which phis are located.
1009 typedef struct _cond_info_t {
1010 struct list_head list; /**< Used to list all of these structs per class. */
1012 struct list_head roots; /**< A list of non-depending Conds. Two Conds are
1013 independent, if it's not possible not reach one from the
1014 other (all Conds in this list have to dominate the
1015 block this struct is attached to). */
1017 ir_node *first_phi; /**< The first phi node this cond info was made for. */
1018 set *cond_set; /**< A set of all dominating reachable Conds. */
1024 static void _find_conds(ir_node *irn, unsigned long visited_nr,
1025 ir_node *dominator, cond_t *masked_by, int pos, int depth, cond_info_t *ci)
1028 int saw_select_cond = 0;
1030 block = get_nodes_block(irn);
1033 * Only check this block if it is dominated by the specified
1034 * dominator or it has not been visited yet.
1036 if (block_dominates(dominator, block) && get_Block_block_visited(block) < visited_nr) {
1037 cond_t *res = masked_by;
1040 /* check, if we're on a ProjX
1042 * Further, the ProjX/Cond block must dominate the base block
1043 * (the block with the phi in it), otherwise, the Cond
1044 * is not affecting the phi so that a mux can be inserted.
1046 if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
1048 int proj = get_Proj_proj(irn);
1049 ir_node *cond = get_Proj_pred(irn);
1051 /* true, if the mode is a mode_b cond _NO_ switch cond */
1052 int is_modeb_cond = get_irn_opcode(cond) == iro_Cond
1053 && get_irn_mode(get_Cond_selector(cond)) == mode_b;
1055 saw_select_cond = !is_modeb_cond;
1057 /* Check, if the pred of the proj is a Cond
1058 * with a Projb as selector.
1063 memset(&c, 0, sizeof(c));
1066 c.cases[0].pos = -1;
1067 c.cases[1].pos = -1;
1069 /* get or insert the cond info into the set. */
1070 res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
1073 * If this cond is already masked by the masked_by cond
1074 * return immediately, since we don't have anything to add.
1076 if(masked_by && res->cases[proj].masked_by == masked_by)
1081 list_add(&res->list, &ci->roots);
1085 * Set masked by (either NULL or another cond node.
1086 * If this cond is truly masked by another one, set
1087 * the position of the actually investigated branch
1088 * to -1. Since the cond is masked by another one,
1089 * there could be more ways from the start block
1090 * to this branch, so we choose -1.
1092 res->cases[proj].masked_by = masked_by;
1095 res->cases[proj].pos = pos;
1098 * Since the masked_by nodes masks a cond, remove it from the
1099 * root list of the conf trees.
1102 assert(res->cases[proj].pos < 0);
1103 list_del_init(&masked_by->list);
1106 DBG((dbg, LEVEL_2, "%n (%s branch) "
1107 "for pos %d in block %n reached by %n\n",
1108 cond, proj ? "true" : "false", pos,
1109 block, masked_by ? masked_by->cond : NULL));
1113 if(get_Block_block_visited(block) < visited_nr && !saw_select_cond) {
1115 set_Block_block_visited(block, visited_nr);
1117 /* Search recursively from this cond. */
1118 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1119 ir_node *pred = get_irn_n(block, i);
1122 * If the depth is 0 (the first recursion), we set the pos to
1123 * the current viewed predecessor, else we adopt the position
1124 * as given by the caller. We also increase the depth for the
1125 * recursively called functions.
1127 _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci);
1135 * A convenience function for _find_conds.
1136 * It sets some parameters needed for recursion to appropriate start
1137 * values. Always use this function.
1139 * @param irn The node to start looking for Conds from. This might
1140 * be the phi node we are investigating.
1141 * @param conds The set to record the found Conds in.
1143 static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
1146 unsigned long visited_nr;
1147 ir_node *block = get_nodes_block(irn);
1148 ir_node *dom = get_Block_idom(block);
1150 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1151 ir_node *pred = get_irn_n(block, i);
1153 inc_irg_block_visited(current_ir_graph);
1154 visited_nr = get_irg_block_visited(current_ir_graph);
1155 set_Block_block_visited(block, visited_nr);
1157 DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
1158 _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
1163 * Make the mux for a given cond.
1165 * @param phi The phi node which shall be replaced by a mux.
1166 * @param dom The block where the muxes shall be placed.
1167 * @param cond The cond information.
1168 * @param info The options for createing Mux nodes.
1169 * @return The mux node made for this cond.
1171 static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond,
1172 const opt_if_conv_info_t *info, ir_node **mux, bitset_t *positions,
1173 int *muxes_made, long visited_nr)
1176 ir_node *projb = get_Cond_selector(cond->cond);
1177 ir_node *bl = get_nodes_block(cond->cond);
1178 ir_node *operands[2];
1181 cond->visited_nr = visited_nr;
1182 DBG((dbg, LEVEL_2, "%n\n", cond->cond));
1183 for(i = 0; i < 2; ++i) {
1184 cond_t *masked_by = cond->cases[i].masked_by;
1185 int pos = cond->cases[i].pos;
1191 * If this Cond branch is masked by another cond, make the mux
1192 * for that Cond first, since the Mux for this cond takes
1197 DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
1198 if(masked_by->visited_nr < visited_nr)
1199 operands[i] = make_mux_on_demand(phi, dom, masked_by, info, mux, positions, muxes_made, visited_nr);
1203 * If this cond branch is not masked by another cond, take
1204 * the corresponding phi operand as an operand to the mux.
1207 operands[i] = get_irn_n(phi, pos);
1213 * Move the operands to the dominator block if the cond
1214 * made sense. Some Conds found are not suitable for making a mux
1215 * out of them, since one of their branches cannot be reached from
1216 * the phi block. In that case we do not make a mux and return NULL.
1218 if(operands[0] && operands[1]) {
1219 if (operands[0] == operands[1]) {
1220 /* there is no gain in using mux in this case, as
1221 it will be optimized away. We will NOT move the
1222 content of the blocks either
1224 for (i = 0; i < 2; ++i)
1226 bitset_set(positions, set[i]);
1232 can_move[0] = can_move_to(operands[0], bl, info);
1233 can_move[1] = can_move_to(operands[1], bl, info);
1235 if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) {
1236 if (info->allow_mux(projb, operands[0], operands[1])) {
1237 move_to(operands[0], bl);
1238 move_to(operands[1], bl);
1241 *mux = new_r_Mux(current_ir_graph, bl, projb,
1242 operands[0], operands[1], get_irn_mode(operands[0]));
1246 DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
1247 *mux, projb, operands[0], operands[1], set[0], set[1]));
1249 for(i = 0; i < 2; ++i)
1251 bitset_set(positions, set[i]);
1253 /* we have done one */
1254 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_SUCCESS);
1258 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_DENIED);
1262 if(can_move[0] != SUCCESS)
1263 hook_if_conversion(current_ir_graph, phi, set[0], NULL, can_move[0]);
1264 if(can_move[1] != SUCCESS)
1265 hook_if_conversion(current_ir_graph, phi, set[1], NULL, can_move[1]);
1270 hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF);
1272 hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF);
1278 typedef struct _phi_info_t {
1279 struct list_head list;
1280 cond_info_t *cond_info;
1286 * Examine a phi node if it can be replaced by some muxes.
1287 * @param irn A phi node.
1288 * @param info Parameters for the if conversion algorithm.
1290 static int check_out_phi(phi_info_t *phi_info, const opt_if_conv_info_t *info)
1292 ir_node *irn = phi_info->irn;
1293 ir_node *block, *nw;
1294 cond_info_t *cond_info = phi_info->cond_info;
1298 bitset_t *positions;
1300 block = get_nodes_block(irn);
1301 arity = get_irn_arity(irn);
1302 positions = bitset_alloca(arity);
1304 assert(is_Phi(irn));
1305 assert(get_irn_arity(irn) == get_irn_arity(block));
1308 DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
1310 list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
1311 ir_node *cidom = block;
1312 ir_node *mux = NULL;
1313 cond_t *p, *head = NULL;
1316 bitset_clear_all(positions);
1318 DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
1320 * Link all conds which are in the subtree of
1321 * the current cond in the list together.
1323 walk_conds(cond, link_conds, NULL, &head);
1326 for(p = head; p; p = p->link) {
1327 for(i = 0; i < 2; ++i) {
1328 int pos = p->cases[i].pos;
1330 cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
1334 DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
1335 make_mux_on_demand(irn, cidom, cond, info, &mux, positions, &muxes_made, ++cond_visited_nr);
1338 bitset_foreach(positions, pos)
1339 set_irn_n(irn, (int) pos, mux);
1344 * optimize the phi away. This can anable further runs of this
1345 * function. Look at _can_move. phis cannot be moved there.
1347 nw = optimize_in_place_2(irn);
1354 typedef struct _cond_walk_info_t {
1355 struct obstack *obst;
1356 struct list_head cond_info_head;
1357 struct list_head phi_head;
1361 static void annotate_cond_info_pre(ir_node *irn, void *data)
1363 set_irn_link(irn, NULL);
1366 static void annotate_cond_info_post(ir_node *irn, void *data)
1368 cond_walk_info_t *cwi = data;
1371 * Check, if the node is a phi
1372 * we then compute a set of conds which are reachable from this
1373 * phi's block up to its dominator.
1374 * The set is attached to the blocks link field.
1376 if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
1377 ir_node *block = get_nodes_block(irn);
1379 cond_info_t *ci = get_irn_link(block);
1381 /* If the set is not yet computed, do it now. */
1383 ci = obstack_alloc(cwi->obst, sizeof(*ci));
1384 ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
1385 ci->first_phi = irn;
1387 INIT_LIST_HEAD(&ci->roots);
1388 INIT_LIST_HEAD(&ci->list);
1391 * Add this cond info to the list of all cond infos
1392 * in this graph. This is just done to xfree the
1393 * set easier afterwards (we save an irg_walk_graph).
1395 list_add(&cwi->cond_info_head, &ci->list);
1397 DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
1400 * Fill the set with conds we find on the way from
1401 * the block to its dominator.
1403 find_conds(irn, ci);
1406 * If there where no suitable conds, delete the set
1407 * immediately and reset the set pointer to NULL
1409 if(set_count(ci->cond_set) == 0) {
1410 del_set(ci->cond_set);
1411 list_del(&ci->list);
1412 obstack_free(cwi->obst, ci);
1418 DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
1420 set_irn_link(block, ci);
1423 phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
1426 INIT_LIST_HEAD(&pi->list);
1427 list_add(&pi->list, &cwi->phi_head);
1433 static void dump_conds(cond_t *cond, void *env)
1438 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
1439 cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
1440 get_nodes_block(cond->cond));
1442 for(i = 0; i < 2; ++i)
1443 if(cond->cases[i].masked_by)
1444 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
1445 cond, cond->cases[i].masked_by, i);
1448 static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi)
1453 snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
1455 if((f = fopen(buf, "wt")) != NULL) {
1460 ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
1461 list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
1462 ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
1463 list_for_each_entry(cond_t, cond, &ci->roots, list) {
1464 walk_conds(cond, NULL, dump_conds, f);
1465 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
1469 list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
1470 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
1471 phi->irn, phi->irn, get_nodes_block(phi->irn));
1472 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
1478 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
1481 struct obstack obst;
1482 phi_info_t *phi_info;
1483 cond_info_t *cond_info;
1484 cond_walk_info_t cwi;
1486 opt_if_conv_info_t p;
1488 if(!get_opt_if_conversion())
1491 /* get the parameters */
1493 memcpy(&p, params, sizeof(p));
1495 memcpy(&p, &default_info, sizeof(p));
1498 p.allow_mux = default_info.allow_mux;
1500 obstack_init(&obst);
1503 INIT_LIST_HEAD(&cwi.cond_info_head);
1504 INIT_LIST_HEAD(&cwi.phi_head);
1506 /* Init the debug stuff. */
1507 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
1509 firm_dbg_set_mask(dbg, LEVEL_1|LEVEL_2|LEVEL_3);
1512 /* if-conversion works better with normalized returns */
1513 normalize_one_return(irg);
1515 /* Ensure, that the dominators are computed. */
1518 DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
1519 get_entity_name(get_irg_entity(irg)), irg));
1522 * Collect information about the conds pu the phis on an obstack.
1523 * It is important that phi nodes which are 'higher' (with a
1524 * lower dfs pre order) are in front of the obstack. Since they are
1525 * possibly turned in to muxes this can enable the optimization
1528 irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
1531 vcg_dump_conds(irg, &cwi);
1534 /* Process each suitable phi found. */
1535 list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
1536 DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
1537 muxes_made += check_out_phi(phi_info, &p);
1540 list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
1541 del_set(cond_info->cond_set);
1544 DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
1546 obstack_free(&obst, NULL);
1548 dump_ir_block_graph(irg, "_ifconv_hack");