3 * File name: ir/opt/ifconv.c
4 * Purpose: If conversion
5 * Author: Sebastian Hack.
8 * Copyright: (c) 1998-2005 Universität Karlsruhe
9 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE.
43 DEBUG_ONLY(firm_dbg_module_t *dbg);
47 * Additional block info.
49 typedef struct block_info {
50 ir_node *phi; /**< head of the Phi list */
51 int has_pinned; /**< set if the block contains instructions that cannot be moved */
54 #define get_block_blockinfo(block) ((block_info *)get_irn_link(block))
57 * Returns non-zero if a Block can be emptied.
59 static int can_empty_block(ir_node *block)
61 return !get_block_blockinfo(block)->has_pinned;
65 static ir_node* walk_to_projx(ir_node* start, const ir_node* dependency)
70 /* No need to find the conditional block if this block cannot be emptied and
73 if (!can_empty_block(start)) return NULL;
75 arity = get_irn_arity(start);
76 for (i = 0; i < arity; ++i) {
77 ir_node* pred = get_irn_n(start, i);
78 ir_node* pred_block = get_nodes_block(pred);
80 if (pred_block == dependency) {
81 assert(is_Proj(pred));
82 assert(get_irn_mode(pred) == mode_X);
87 assert(get_irn_mode(pred) == mode_X);
91 if (is_cdep_on(pred_block, dependency)) {
92 return walk_to_projx(pred_block, dependency);
100 * Copies the DAG starting at node to the ith predecessor block of src_block
101 * -if the node isn't in the src_block, this is a nop and the node is returned
102 * -if the node is a phi in the src_block, the ith predecessor of the phi is
104 * otherwise returns the copy of the passed node
106 static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
113 if (get_nodes_block(node) != src_block) return node;
114 if (get_irn_op(node) == op_Phi) return get_irn_n(node, i);
116 copy = exact_copy(node);
117 dst_block = get_nodes_block(get_irn_n(src_block, i));
118 set_nodes_block(copy, dst_block);
120 DB((dbg, LEVEL_1, "Copying node %+F to block %+F, copy is %+F\n",
121 node, dst_block, copy));
123 arity = get_irn_arity(node);
124 for (j = 0; j < arity; ++j) {
125 set_irn_n(copy, j, copy_to(get_irn_n(node, j), src_block, i));
126 DB((dbg, LEVEL_2, "-- pred %d is %+F\n", j, get_irn_n(copy, j)));
133 * Remove predecessors i and j from node and add predecessor new_pred
135 static void rewire(ir_node* node, int i, int j, ir_node* new_pred)
137 int arity = get_irn_arity(node);
142 NEW_ARR_A(ir_node *, ins, arity - 1);
145 for (k = 0; k < i; ++k) ins[l++] = get_irn_n(node, k);
146 for (++k; k < j; ++k) ins[l++] = get_irn_n(node, k);
147 for (++k; k < arity; ++k) ins[l++] = get_irn_n(node, k);
149 assert(l == arity - 1);
150 set_irn_in(node, l, ins);
155 * Remove the jth predecessors from the ith predecessor of block and add it to block
157 static void split_block(ir_node* block, int i, int j)
159 ir_node* pred_block = get_nodes_block(get_irn_n(block, i));
160 int arity = get_irn_arity(block);
167 DB((dbg, LEVEL_1, "Splitting predecessor %d of predecessor %d of %+F\n", j, i, block));
169 NEW_ARR_A(ir_node*, ins, arity + 1);
171 for (phi = get_block_blockinfo(block)->phi; phi != NULL; phi = get_irn_link(phi)) {
172 ir_node* copy = copy_to(get_irn_n(phi, i), pred_block, j);
174 for (k = 0; k < i; ++k) ins[k] = get_irn_n(phi, k);
176 for (; k < arity; ++k) ins[k] = get_irn_n(phi, k);
177 ins[k] = get_irn_n(phi, i);
179 set_irn_in(phi, arity + 1, ins);
182 for (k = 0; k < i; ++k) ins[k] = get_irn_n(block, k);
183 ins[k++] = get_irn_n(pred_block, j);
184 for (; k < arity; ++k) ins[k] = get_irn_n(block, k);
185 ins[k] = get_irn_n(block, i);
187 set_irn_in(block, arity + 1, ins);
189 new_pred_arity = get_irn_arity(pred_block) - 1;
190 NEW_ARR_A(ir_node*, pred_ins, new_pred_arity);
192 for (phi = get_block_blockinfo(pred_block)->phi; phi != NULL; phi = get_irn_link(phi)) {
193 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(phi, k);
194 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(phi, k + 1);
195 assert(k == new_pred_arity);
196 if (new_pred_arity > 1) {
197 set_irn_in(phi, new_pred_arity, pred_ins);
199 exchange(phi, pred_ins[0]);
203 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(pred_block, k);
204 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(pred_block, k + 1);
205 assert(k == new_pred_arity);
206 if (new_pred_arity > 1) {
207 set_irn_in(pred_block, new_pred_arity, pred_ins);
209 exchange(pred_block, get_nodes_block(pred_ins[0]));
214 static void prepare_path(ir_node* block, int i, const ir_node* dependency)
216 ir_node* pred = get_nodes_block(get_irn_n(block, i));
220 DB((dbg, LEVEL_1, "Preparing predecessor %d of %+F\n", i, block));
222 pred_arity = get_irn_arity(pred);
223 for (j = 0; j < pred_arity; ++j) {
224 ir_node* pred_pred = get_nodes_block(get_irn_n(pred, j));
226 if (is_cdep_on(pred_pred, dependency)) {
227 prepare_path(pred, j, dependency);
228 split_block(block, i, j);
235 static void if_conv_walker(ir_node* block, void* env)
240 /* Bail out, if there are no Phis at all */
241 if (get_block_blockinfo(block)->phi == NULL) return;
244 arity = get_irn_arity(block);
245 for (i = 0; i < arity; ++i) {
249 pred = get_nodes_block(get_irn_n(block, i));
250 for (cdep = find_cdep(pred); cdep != NULL; cdep = cdep->next) {
251 const ir_node* dependency = cdep->node;
252 ir_node* projx0 = walk_to_projx(pred, dependency);
256 if (projx0 == NULL) continue;
258 cond = get_Proj_pred(projx0);
259 if (get_irn_op(cond) != op_Cond) continue;
260 /* We only handle boolean decisions, no switches */
261 if (get_irn_mode(get_Cond_selector(cond)) != mode_b) continue;
263 for (j = i + 1; j < arity; ++j) {
271 pred = get_nodes_block(get_irn_n(block, j));
273 if (!is_cdep_on(pred, dependency)) continue;
275 projx1 = walk_to_projx(pred, dependency);
277 if (projx1 == NULL) continue;
279 DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n",
283 prepare_path(block, i, dependency);
284 prepare_path(block, j, dependency);
285 arity = get_irn_arity(block);
287 conds[0] = get_Cond_selector(cond);
289 psi_block = get_nodes_block(cond);
290 phi = get_block_blockinfo(block)->phi;
292 ir_node* val_i = get_irn_n(phi, i);
293 ir_node* val_j = get_irn_n(phi, j);
295 if (val_i == val_j) {
297 DB((dbg, LEVEL_2, "Generating no psi, because both values are equal\n"));
299 /* Something is very fishy if two predecessors of a PhiM point into
300 * one block, but not at the same memory node
302 assert(get_irn_mode(phi) != mode_M);
303 if (get_Proj_proj(projx0) == pn_Cond_true) {
311 current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
313 DB((dbg, LEVEL_2, "Generating %+F for %+F\n", psi, phi));
319 rewire(phi, i, j, psi);
322 phi = get_irn_link(phi);
323 } while (phi != NULL);
325 exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
326 exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
330 DB((dbg, LEVEL_1, "Welding block %+F and %+F\n", block, psi_block));
331 get_block_blockinfo(block)->has_pinned |= get_block_blockinfo(psi_block)->has_pinned;
332 set_irn_in(block, get_irn_arity(psi_block), get_irn_in(psi_block) + 1);
333 exchange_cdep(psi_block, block);
334 exchange(psi_block, block);
336 DB((dbg, LEVEL_1, "Welding block %+F to %+F\n", block, psi_block));
337 get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
338 exchange(block, psi_block);
342 rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block));
351 * Block walker: add additional data
353 static void init_block_link(ir_node *block, void *env)
355 struct obstack *obst = env;
356 block_info *bi = obstack_alloc(obst, sizeof(*bi));
360 set_irn_link(block, bi);
365 * Daisy-chain all phis in a block
366 * If a non-movable node is encountered set the has_pinned flag
368 static void collect_phis(ir_node *node, void *env)
371 ir_node *block = get_nodes_block(node);
372 block_info *bi = get_block_blockinfo(block);
374 set_irn_link(node, bi->phi);
378 if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
380 * Ignore control flow nodes, these will be removed.
381 * This ignores Raise. That is surely bad. FIXME.
383 if (! is_cfop(node)) {
384 ir_node *block = get_nodes_block(node);
385 block_info *bi = get_block_blockinfo(block);
387 DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
396 * Transform multiple cascaded Psis into one Psi
398 static ir_node* fold_psi(ir_node* psi)
400 int arity = get_Psi_n_conds(psi);
411 for (i = 0; i < arity; ++i) {
412 n = get_Psi_val(psi, i);
413 if (get_irn_op(n) == op_Psi) {
414 new_arity += get_Psi_n_conds(n) + 1;
419 n = get_Psi_default(psi);
420 if (get_irn_op(n) == op_Psi) {
421 new_arity += get_Psi_n_conds(n);
424 if (arity == new_arity) return psi; // no attached Psis found
425 DB((dbg, LEVEL_1, "Folding %+F from %d to %d conds\n", psi, arity, new_arity));
427 NEW_ARR_A(ir_node *, conds, new_arity);
428 NEW_ARR_A(ir_node *, vals, new_arity + 1);
430 for (i = 0; i < arity; ++i) {
431 ir_node* c = get_Psi_cond(psi, i);
433 n = get_Psi_val(psi, i);
434 if (get_irn_op(n) == op_Psi) {
435 a = get_Psi_n_conds(n);
436 for (k = 0; k < a; ++k) {
437 conds[j] = new_r_And(
438 current_ir_graph, get_nodes_block(psi),
439 c, get_Psi_cond(n, k), mode_b
441 vals[j] = get_Psi_val(n, k);
445 vals[j] = get_Psi_default(n);
452 n = get_Psi_default(psi);
453 if (get_irn_op(n) == op_Psi) {
454 a = get_Psi_n_conds(n);
455 for (k = 0; k < a; ++k) {
456 conds[j] = get_Psi_cond(n, k);
457 vals[j] = get_Psi_val(n, k);
460 vals[j] = get_Psi_default(n);
464 assert(j == new_arity);
466 current_ir_graph, get_nodes_block(psi),
467 new_arity, conds, vals, get_irn_mode(psi)
469 DB((dbg, LEVEL_1, "Folded %+F into new %+F\n", psi, new_psi));
470 exchange(psi, new_psi);
476 * Merge consecutive psi inputs if the data inputs are the same
478 static ir_node* meld_psi(ir_node* psi)
480 int arity = get_Psi_n_conds(psi);
491 val = get_Psi_val(psi, 0);
492 DB((dbg, LEVEL_1, "Pred 0 of %+F is %+F\n", psi, val));
493 for (i = 1; i < arity; ++i) {
494 ir_node* v = get_Psi_val(psi, i);
495 DB((dbg, LEVEL_1, "Pred %2d of %+F is %+F\n", i, psi, v));
501 DB((dbg, LEVEL_1, "Default of %+F is %+F\n", psi, get_Psi_default(psi)));
502 if (val == get_Psi_default(psi)) --new_arity;
504 DB((dbg, LEVEL_1, "Melding Psi %+F from %d conds to %d\n", psi, arity, new_arity));
506 if (new_arity == arity) return psi;
508 /* If all data inputs of the Psi are equal, exchange the Psi with that value */
509 if (new_arity == 0) {
514 NEW_ARR_A(ir_node *, conds, new_arity);
515 NEW_ARR_A(ir_node *, vals, new_arity + 1);
516 cond = get_Psi_cond(psi, 0);
517 val = get_Psi_val(psi, 0);
519 for (i = 1; i < arity; ++i) {
520 ir_node* v = get_Psi_val(psi, i);
524 current_ir_graph, get_nodes_block(psi),
525 cond, get_Psi_cond(psi, i), mode_b
534 if (val != get_Psi_default(psi)) {
539 vals[j] = get_Psi_default(psi);
540 assert(j == new_arity);
542 current_ir_graph, get_nodes_block(psi),
543 new_arity, conds, vals, get_irn_mode(psi)
545 DB((dbg, LEVEL_1, "Molded %+F into %+F\n", psi, new_psi));
546 exchange(psi, new_psi);
552 * Split a Psi with multiple conditions into multiple Psis with one condtition
555 static ir_node* split_psi(ir_node* psi)
557 int arity = get_Psi_n_conds(psi);
563 if (arity == 1) return psi;
565 mode = get_irn_mode(psi);
566 block = get_nodes_block(psi);
567 rval = get_Psi_default(psi);
568 for (i = arity - 1; i >= 0; --i) {
572 conds[0] = get_Psi_cond(psi, i);
573 vals[0] = get_Psi_val(psi, i);
576 current_ir_graph, block, 1, conds, vals, mode
584 static void optimise_psis(ir_node* node, void* env)
586 if (get_irn_op(node) != op_Psi) return;
588 node = fold_psi(node);
591 node = meld_psi(node);
594 node = split_psi(node);
599 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
603 if (!get_opt_if_conversion())
606 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
608 DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
610 dump_ir_block_graph(irg, "_00_pre");
612 normalize_one_return(irg);
613 remove_critical_cf_edges(irg);
615 dump_ir_block_graph(irg, "_01_normal");
621 irg_block_walk_graph(irg, init_block_link, NULL, &obst);
622 irg_walk_graph(irg, collect_phis, NULL, NULL);
623 irg_block_walk_graph(irg, NULL, if_conv_walker, NULL);
625 dump_ir_block_graph(irg, "_02_ifconv");
626 local_optimize_graph(irg);
627 dump_ir_block_graph(irg, "_03_postopt");
629 irg_walk_graph(irg, NULL, optimise_psis, NULL);
631 dump_ir_block_graph(irg, "_04_postifconv");
633 obstack_free(&obst, NULL);
644 * Make Mux nodes from Conds where it its possible.
645 * @author Sebastian Hack
662 #include "irgraph_t.h"
663 #include "irnode_t.h"
667 #include "irmode_t.h"
668 #include "ircons_t.h"
673 #include "irflag_t.h"
675 #include "irprintf.h"
680 #include "bitfiddle.h"
687 * check, if a node is const and return its tarval or
688 * return a default tarval.
689 * @param cnst The node whose tarval to get.
690 * @param or The alternative tarval, if the node is no Const.
691 * @return The tarval of @p cnst, if the node is Const, @p otherwise.
693 static tarval *get_value_or(ir_node *cnst, tarval *or)
695 return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
700 * Try to optimize nested muxes into a dis- or conjunction
702 * @param mux The parent mux, which has muxes as operands.
703 * @return The replacement node for this mux. If the optimization is
704 * successful, this might be an And or Or node, if not, its the mux
707 static ir_node *optimize_mux_chain(ir_node *mux)
712 ir_mode *mode = get_irn_mode(mux);
717 * If we have no mux, or its mode is not integer, we
720 if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
724 null = get_mode_null(mode);
725 minus_one = tarval_sub(null, get_tarval_one(mode));
727 ops[0] = get_Mux_false(mux);
728 ops[1] = get_Mux_true(mux);
730 for(i = 0; i < 2; ++i) {
732 tarval *tva, *tvb, *tvd;
736 * A mux operand at the first position can be factored
737 * out, if the operands fulfill several conditions:
739 * mux(c1, mux(c2, a, b), d)
741 * This can be made into:
742 * 1) mux(c1, 0, d) | mux(c2, a, b)
743 * if a | d == d and b | d == d
745 * 2) mux(c1, -1, d) & mux(c2, a, b)
746 * if a & d == d and a & b == b
748 if(get_irn_op(ops[i]) == op_Mux) {
751 a = get_Mux_false(child_mux);
752 b = get_Mux_true(child_mux);
755 /* Try the or stuff */
756 tva = get_value_or(a, minus_one);
757 tvb = get_value_or(b, minus_one);
758 tvd = get_value_or(d, null);
760 if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
761 && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
763 ops[i] = new_Const(mode, null);
764 res = new_r_Or(current_ir_graph, get_nodes_block(mux),
765 mux, child_mux, mode);
769 /* If the or didn't go, try the and stuff */
770 tva = get_value_or(a, null);
771 tvb = get_value_or(b, null);
772 tvd = get_value_or(d, minus_one);
774 if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
775 && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
777 ops[i] = new_Const(mode, minus_one);
778 res = new_r_And(current_ir_graph, get_nodes_block(mux),
779 mux, child_mux, mode);
785 /* recursively optimize nested muxes. */
786 set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
787 set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
793 /***********************************************************
794 * The If conversion itself.
795 ***********************************************************/
797 /** allow every Mux to be created. */
798 static int default_allow_mux(ir_node *sel, ir_node *false_res, ir_node *true_res) {
805 static const opt_if_conv_info_t default_info = {
810 /** The debugging module. */
811 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
814 * A simple check for side effects upto an opcode of a ir node.
815 * @param irn The ir node to check,
816 * @return 1 if the opcode itself may produce side effects, 0 if not.
818 static INLINE int has_side_effects(const ir_node *irn)
820 ir_op *op = get_irn_op(irn);
825 return !mode_is_datab(get_irn_mode(irn));
829 * Possible failure reasons
831 enum failure_reason_t {
832 SUCCESS = IF_RESULT_SUCCESS,
833 TO_DEEP = IF_RESULT_TOO_DEEP,
834 SIDE_EFFECTS = IF_RESULT_SIDE_EFFECT,
835 PHI_FOUND = IF_RESULT_SIDE_EFFECT_PHI,
836 DENIED = IF_RESULT_DENIED
840 * Decides, if a given expression and its subexpressions
841 * (to certain, also given extent) can be moved to a block.
843 * @param expr The expression to examine.
844 * @param block The block where the expression should go.
845 * @param depth The current depth, passed recursively. Use 0 for
846 * non-recursive calls.
847 * @param info The options for createing Mux nodes.
850 * @return a failure reason
852 static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, const opt_if_conv_info_t *info)
856 ir_node *expr_block = get_nodes_block(expr);
859 * If we are forced to look too deep into the expression,
860 * treat it like it could not be moved.
862 if(depth >= info->max_depth) {
868 * If the block of the expression dominates the specified
869 * destination block, it does not matter if the expression
870 * has side effects or anything else. It is executed on each
871 * path the destination block is reached.
873 if (block_dominates(expr_block, dest_block))
877 * We cannot move phis!
885 * This should be superfluous and could be converted into a assertion.
886 * The destination block _must_ dominate the block of the expression,
887 * else the expression could be used without its definition.
889 if (! block_dominates(dest_block, expr_block)) {
890 res = IF_RESULT_SIDE_EFFECT;
895 * Surely, if the expression does not have a data mode, it is not
896 * movable. Perhaps one should also test the floating property of
899 if (has_side_effects(expr)) {
900 res = IF_RESULT_SIDE_EFFECT;
905 * If the node looks alright so far, look at its operands and
906 * check them out. If one of them cannot be moved, this one
907 * cannot be moved either.
909 for (i = 0, n = get_irn_arity(expr); i < n; ++i) {
910 ir_node *op = get_irn_n(expr, i);
911 int new_depth = is_Proj(op) ? depth : depth + 1;
913 res = _can_move_to(op, dest_block, new_depth, info);
920 DBG((dbg, LEVEL_3, "\t\t\tcan move to %n: %d\n", expr, res));
926 * Convenience function for _can_move_to.
927 * Checks, if an expression can be moved to another block. The check can
928 * be limited to a expression depth meaning if we need to crawl in
929 * deeper into an expression than a given threshold to examine if
930 * it can be moved, the expression is rejected and the test returns
933 * @param expr The expression to check for.
934 * @param dest_block The destination block you want @p expr to be.
935 * @param info The options for createing Mux nodes.
937 * @return return a failure reason
939 static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, const opt_if_conv_info_t *info)
941 return _can_move_to(expr, dest_block, 0, info);
945 * move a DAG given by a root node expr into a new block
947 * @param expr the root of a dag
948 * @param dest_block the destination block
950 static void move_to(ir_node *expr, ir_node *dest_block)
953 ir_node *expr_block = get_nodes_block(expr);
956 * If we reached the dominator, we are done.
957 * We will never put code through the dominator
959 if (block_dominates(expr_block, dest_block))
962 for (i = 0, n = get_irn_arity(expr); i < n; ++i)
963 move_to(get_irn_n(expr, i), dest_block);
965 set_nodes_block(expr, dest_block);
969 * return the common dominator of two blocks
971 static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2)
973 if(block_dominates(b1, b2))
975 else if(block_dominates(b2, b1))
980 for (p = get_Block_idom(b1); !block_dominates(p, b2); p = get_Block_idom(p));
986 * Information about a cond node.
988 typedef struct _cond_t {
989 ir_node *cond; /**< The cond node. */
990 struct list_head list; /**< List head which is used for queuing this cond
991 into the cond bunch it belongs to. */
993 unsigned totally_covers : 1;
994 struct _cond_t *link;
998 * Information about the both 'branches'
999 * (true and false), the cond creates.
1002 int pos; /**< Number of the predecessor of the
1003 phi block by which this branch is
1004 reached. It is -1, if this branch is
1005 only reached through another cond. */
1007 struct _cond_t *masked_by; /**< If this cond's branch is only reached
1008 through another cond, we store this
1009 cond ir_node here. */
1014 * retrieve the conditional information from a Cond node
1016 static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
1021 return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
1025 typedef void (cond_walker_t)(cond_t *cond, void *env);
1027 static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
1028 long visited_nr, void *env)
1032 if(cond->visited_nr >= visited_nr)
1035 cond->visited_nr = visited_nr;
1040 for(i = 0; i < 2; ++i) {
1041 cond_t *c = cond->cases[i].masked_by;
1044 _walk_conds(c, pre, post, visited_nr, env);
1051 static long cond_visited_nr = 0;
1053 static void walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post, void *env)
1055 _walk_conds(cond, pre, post, ++cond_visited_nr, env);
1058 static void link_conds(cond_t *cond, void *env)
1060 cond_t **ptr = (cond_t **) env;
1067 * Compare two conds for use in a firm set.
1068 * Two cond_t's are equal, if they designate the same cond node.
1069 * @param a A cond_t.
1070 * @param b Another one.
1071 * @param size Not used.
1072 * @return 0 (!) if they are equal, != 0 otherwise.
1074 static int cond_cmp(const void *a, const void *b, size_t size)
1076 const cond_t *x = a;
1077 const cond_t *y = b;
1078 return x->cond != y->cond;
1082 * Information about conds which can be made to muxes.
1083 * Instances of this struct are attached to the link field of
1084 * blocks in which phis are located.
1086 typedef struct _cond_info_t {
1087 struct list_head list; /**< Used to list all of these structs per class. */
1089 struct list_head roots; /**< A list of non-depending Conds. Two Conds are
1090 independent, if it's not possible not reach one from the
1091 other (all Conds in this list have to dominate the
1092 block this struct is attached to). */
1094 ir_node *first_phi; /**< The first phi node this cond info was made for. */
1095 set *cond_set; /**< A set of all dominating reachable Conds. */
1101 static void _find_conds(ir_node *irn, unsigned long visited_nr,
1102 ir_node *dominator, cond_t *masked_by, int pos, int depth, cond_info_t *ci)
1105 int saw_select_cond = 0;
1107 block = get_nodes_block(irn);
1110 * Only check this block if it is dominated by the specified
1111 * dominator or it has not been visited yet.
1113 if (block_dominates(dominator, block) && get_Block_block_visited(block) < visited_nr) {
1114 cond_t *res = masked_by;
1117 /* check, if we're on a ProjX
1119 * Further, the ProjX/Cond block must dominate the base block
1120 * (the block with the phi in it), otherwise, the Cond
1121 * is not affecting the phi so that a mux can be inserted.
1123 if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
1125 int proj = get_Proj_proj(irn);
1126 ir_node *cond = get_Proj_pred(irn);
1128 /* true, if the mode is a mode_b cond _NO_ switch cond */
1129 int is_modeb_cond = get_irn_opcode(cond) == iro_Cond
1130 && get_irn_mode(get_Cond_selector(cond)) == mode_b;
1132 saw_select_cond = !is_modeb_cond;
1134 /* Check, if the pred of the proj is a Cond
1135 * with a Projb as selector.
1140 memset(&c, 0, sizeof(c));
1143 c.cases[0].pos = -1;
1144 c.cases[1].pos = -1;
1146 /* get or insert the cond info into the set. */
1147 res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
1150 * If this cond is already masked by the masked_by cond
1151 * return immediately, since we don't have anything to add.
1153 if(masked_by && res->cases[proj].masked_by == masked_by)
1158 list_add(&res->list, &ci->roots);
1162 * Set masked by (either NULL or another cond node.
1163 * If this cond is truly masked by another one, set
1164 * the position of the actually investigated branch
1165 * to -1. Since the cond is masked by another one,
1166 * there could be more ways from the start block
1167 * to this branch, so we choose -1.
1169 res->cases[proj].masked_by = masked_by;
1172 res->cases[proj].pos = pos;
1175 * Since the masked_by nodes masks a cond, remove it from the
1176 * root list of the conf trees.
1179 assert(res->cases[proj].pos < 0);
1180 list_del_init(&masked_by->list);
1183 DBG((dbg, LEVEL_2, "%n (%s branch) "
1184 "for pos %d in block %n reached by %n\n",
1185 cond, proj ? "true" : "false", pos,
1186 block, masked_by ? masked_by->cond : NULL));
1190 if(get_Block_block_visited(block) < visited_nr && !saw_select_cond) {
1192 set_Block_block_visited(block, visited_nr);
1194 /* Search recursively from this cond. */
1195 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1196 ir_node *pred = get_irn_n(block, i);
1199 * If the depth is 0 (the first recursion), we set the pos to
1200 * the current viewed predecessor, else we adopt the position
1201 * as given by the caller. We also increase the depth for the
1202 * recursively called functions.
1204 _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci);
1212 * A convenience function for _find_conds.
1213 * It sets some parameters needed for recursion to appropriate start
1214 * values. Always use this function.
1216 * @param irn The node to start looking for Conds from. This might
1217 * be the phi node we are investigating.
1218 * @param conds The set to record the found Conds in.
1220 static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
1223 unsigned long visited_nr;
1224 ir_node *block = get_nodes_block(irn);
1225 ir_node *dom = get_Block_idom(block);
1227 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1228 ir_node *pred = get_irn_n(block, i);
1230 inc_irg_block_visited(current_ir_graph);
1231 visited_nr = get_irg_block_visited(current_ir_graph);
1232 set_Block_block_visited(block, visited_nr);
1234 DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
1235 _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
1240 * Make the mux for a given cond.
1242 * @param phi The phi node which shall be replaced by a mux.
1243 * @param dom The block where the muxes shall be placed.
1244 * @param cond The cond information.
1245 * @param info The options for createing Mux nodes.
1246 * @return The mux node made for this cond.
1248 static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond,
1249 const opt_if_conv_info_t *info, ir_node **mux, bitset_t *positions,
1250 int *muxes_made, long visited_nr)
1253 ir_node *projb = get_Cond_selector(cond->cond);
1254 ir_node *bl = get_nodes_block(cond->cond);
1255 ir_node *operands[2];
1258 cond->visited_nr = visited_nr;
1259 DBG((dbg, LEVEL_2, "%n\n", cond->cond));
1260 for(i = 0; i < 2; ++i) {
1261 cond_t *masked_by = cond->cases[i].masked_by;
1262 int pos = cond->cases[i].pos;
1268 * If this Cond branch is masked by another cond, make the mux
1269 * for that Cond first, since the Mux for this cond takes
1274 DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
1275 if(masked_by->visited_nr < visited_nr)
1276 operands[i] = make_mux_on_demand(phi, dom, masked_by, info, mux, positions, muxes_made, visited_nr);
1280 * If this cond branch is not masked by another cond, take
1281 * the corresponding phi operand as an operand to the mux.
1284 operands[i] = get_irn_n(phi, pos);
1290 * Move the operands to the dominator block if the cond
1291 * made sense. Some Conds found are not suitable for making a mux
1292 * out of them, since one of their branches cannot be reached from
1293 * the phi block. In that case we do not make a mux and return NULL.
1295 if(operands[0] && operands[1]) {
1296 if (operands[0] == operands[1]) {
1297 /* there is no gain in using mux in this case, as
1298 it will be optimized away. We will NOT move the
1299 content of the blocks either
1301 for (i = 0; i < 2; ++i)
1303 bitset_set(positions, set[i]);
1309 can_move[0] = can_move_to(operands[0], bl, info);
1310 can_move[1] = can_move_to(operands[1], bl, info);
1312 if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) {
1313 if (info->allow_mux(projb, operands[0], operands[1])) {
1314 move_to(operands[0], bl);
1315 move_to(operands[1], bl);
1318 *mux = new_r_Mux(current_ir_graph, bl, projb,
1319 operands[0], operands[1], get_irn_mode(operands[0]));
1323 DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
1324 *mux, projb, operands[0], operands[1], set[0], set[1]));
1326 for(i = 0; i < 2; ++i)
1328 bitset_set(positions, set[i]);
1330 /* we have done one */
1331 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_SUCCESS);
1335 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_DENIED);
1339 if(can_move[0] != SUCCESS)
1340 hook_if_conversion(current_ir_graph, phi, set[0], NULL, can_move[0]);
1341 if(can_move[1] != SUCCESS)
1342 hook_if_conversion(current_ir_graph, phi, set[1], NULL, can_move[1]);
1347 hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF);
1349 hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF);
1355 typedef struct _phi_info_t {
1356 struct list_head list;
1357 cond_info_t *cond_info;
1363 * Examine a phi node if it can be replaced by some muxes.
1364 * @param irn A phi node.
1365 * @param info Parameters for the if conversion algorithm.
1367 static int check_out_phi(phi_info_t *phi_info, const opt_if_conv_info_t *info)
1369 ir_node *irn = phi_info->irn;
1370 ir_node *block, *nw;
1371 cond_info_t *cond_info = phi_info->cond_info;
1375 bitset_t *positions;
1377 block = get_nodes_block(irn);
1378 arity = get_irn_arity(irn);
1379 positions = bitset_alloca(arity);
1381 assert(is_Phi(irn));
1382 assert(get_irn_arity(irn) == get_irn_arity(block));
1385 DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
1387 list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
1388 ir_node *cidom = block;
1389 ir_node *mux = NULL;
1390 cond_t *p, *head = NULL;
1393 bitset_clear_all(positions);
1395 DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
1397 * Link all conds which are in the subtree of
1398 * the current cond in the list together.
1400 walk_conds(cond, link_conds, NULL, &head);
1403 for(p = head; p; p = p->link) {
1404 for(i = 0; i < 2; ++i) {
1405 int pos = p->cases[i].pos;
1407 cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
1411 DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
1412 make_mux_on_demand(irn, cidom, cond, info, &mux, positions, &muxes_made, ++cond_visited_nr);
1415 bitset_foreach(positions, pos)
1416 set_irn_n(irn, (int) pos, mux);
1421 * optimize the phi away. This can anable further runs of this
1422 * function. Look at _can_move. phis cannot be moved there.
1424 nw = optimize_in_place_2(irn);
1431 typedef struct _cond_walk_info_t {
1432 struct obstack *obst;
1433 struct list_head cond_info_head;
1434 struct list_head phi_head;
1438 static void annotate_cond_info_pre(ir_node *irn, void *data)
1440 set_irn_link(irn, NULL);
1443 static void annotate_cond_info_post(ir_node *irn, void *data)
1445 cond_walk_info_t *cwi = data;
1448 * Check, if the node is a phi
1449 * we then compute a set of conds which are reachable from this
1450 * phi's block up to its dominator.
1451 * The set is attached to the blocks link field.
1453 if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
1454 ir_node *block = get_nodes_block(irn);
1456 cond_info_t *ci = get_irn_link(block);
1458 /* If the set is not yet computed, do it now. */
1460 ci = obstack_alloc(cwi->obst, sizeof(*ci));
1461 ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
1462 ci->first_phi = irn;
1464 INIT_LIST_HEAD(&ci->roots);
1465 INIT_LIST_HEAD(&ci->list);
1468 * Add this cond info to the list of all cond infos
1469 * in this graph. This is just done to xfree the
1470 * set easier afterwards (we save an irg_walk_graph).
1472 list_add(&cwi->cond_info_head, &ci->list);
1474 DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
1477 * Fill the set with conds we find on the way from
1478 * the block to its dominator.
1480 find_conds(irn, ci);
1483 * If there where no suitable conds, delete the set
1484 * immediately and reset the set pointer to NULL
1486 if(set_count(ci->cond_set) == 0) {
1487 del_set(ci->cond_set);
1488 list_del(&ci->list);
1489 obstack_free(cwi->obst, ci);
1495 DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
1497 set_irn_link(block, ci);
1500 phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
1503 INIT_LIST_HEAD(&pi->list);
1504 list_add(&pi->list, &cwi->phi_head);
1510 static void dump_conds(cond_t *cond, void *env)
1515 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
1516 cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
1517 get_nodes_block(cond->cond));
1519 for(i = 0; i < 2; ++i)
1520 if(cond->cases[i].masked_by)
1521 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
1522 cond, cond->cases[i].masked_by, i);
1525 static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi)
1530 snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
1532 if((f = fopen(buf, "wt")) != NULL) {
1537 ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
1538 list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
1539 ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
1540 list_for_each_entry(cond_t, cond, &ci->roots, list) {
1541 walk_conds(cond, NULL, dump_conds, f);
1542 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
1546 list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
1547 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
1548 phi->irn, phi->irn, get_nodes_block(phi->irn));
1549 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
1555 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
1558 struct obstack obst;
1559 phi_info_t *phi_info;
1560 cond_info_t *cond_info;
1561 cond_walk_info_t cwi;
1563 opt_if_conv_info_t p;
1565 if(!get_opt_if_conversion())
1568 /* get the parameters */
1570 memcpy(&p, params, sizeof(p));
1572 memcpy(&p, &default_info, sizeof(p));
1575 p.allow_mux = default_info.allow_mux;
1577 obstack_init(&obst);
1580 INIT_LIST_HEAD(&cwi.cond_info_head);
1581 INIT_LIST_HEAD(&cwi.phi_head);
1583 /* Init the debug stuff. */
1584 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
1586 firm_dbg_set_mask(dbg, LEVEL_1|LEVEL_2|LEVEL_3);
1589 /* if-conversion works better with normalized returns */
1590 normalize_one_return(irg);
1592 /* Ensure, that the dominators are computed. */
1595 DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
1596 get_entity_name(get_irg_entity(irg)), irg));
1599 * Collect information about the conds pu the phis on an obstack.
1600 * It is important that phi nodes which are 'higher' (with a
1601 * lower dfs pre order) are in front of the obstack. Since they are
1602 * possibly turned in to muxes this can enable the optimization
1605 irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
1608 vcg_dump_conds(irg, &cwi);
1611 /* Process each suitable phi found. */
1612 list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
1613 DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
1614 muxes_made += check_out_phi(phi_info, &p);
1617 list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
1618 del_set(cond_info->cond_set);
1621 DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
1623 obstack_free(&obst, NULL);
1625 dump_ir_block_graph(irg, "_ifconv_hack");