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);
81 assert(get_irn_mode(pred) == mode_X);
85 pred_block = get_nodes_block(pred);
86 if (is_cdep_on(pred_block, dependency)) {
87 return walk_to_projx(pred_block, dependency);
95 * Copies the DAG starting at node to the ith predecessor block of src_block
96 * -if the node isn't in the src_block, this is a nop and the node is returned
97 * -if the node is a phi in the src_block, the ith predecessor of the phi is
99 * otherwise returns the copy of the passed node
101 static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
108 if (get_nodes_block(node) != src_block) return node;
109 if (get_irn_op(node) == op_Phi) return get_irn_n(node, i);
111 copy = exact_copy(node);
112 dst_block = get_nodes_block(get_irn_n(src_block, i));
113 set_nodes_block(copy, dst_block);
115 DB((dbg, LEVEL_1, "Copying node %+F to block %+F, copy is %+F\n",
116 node, dst_block, copy));
118 arity = get_irn_arity(node);
119 for (j = 0; j < arity; ++j) {
120 set_irn_n(copy, j, copy_to(get_irn_n(node, j), src_block, i));
121 DB((dbg, LEVEL_2, "-- pred %d is %+F\n", j, get_irn_n(copy, j)));
128 * Remove predecessors i and j from node and add predecessor new_pred
130 static void rewire(ir_node* node, int i, int j, ir_node* new_pred)
132 int arity = get_irn_arity(node);
137 NEW_ARR_A(ir_node *, ins, arity - 1);
140 for (k = 0; k < i; ++k) ins[l++] = get_irn_n(node, k);
141 for (++k; k < j; ++k) ins[l++] = get_irn_n(node, k);
142 for (++k; k < arity; ++k) ins[l++] = get_irn_n(node, k);
144 assert(l == arity - 1);
145 set_irn_in(node, l, ins);
150 * Remove the jth predecessors from the ith predecessor of block and add it to block
152 static void split_block(ir_node* block, int i, int j)
154 ir_node* pred_block = get_nodes_block(get_irn_n(block, i));
155 int arity = get_irn_arity(block);
162 DB((dbg, LEVEL_1, "Splitting predecessor %d of predecessor %d of %+F\n", j, i, block));
164 NEW_ARR_A(ir_node*, ins, arity + 1);
166 for (phi = get_block_blockinfo(block)->phi; phi != NULL; phi = get_irn_link(phi)) {
167 ir_node* copy = copy_to(get_irn_n(phi, i), pred_block, j);
169 for (k = 0; k < i; ++k) ins[k] = get_irn_n(phi, k);
171 for (; k < arity; ++k) ins[k] = get_irn_n(phi, k);
172 ins[k] = get_irn_n(phi, i);
174 set_irn_in(phi, arity + 1, ins);
177 for (k = 0; k < i; ++k) ins[k] = get_irn_n(block, k);
178 ins[k++] = get_irn_n(pred_block, j);
179 for (; k < arity; ++k) ins[k] = get_irn_n(block, k);
180 ins[k] = get_irn_n(block, i);
182 set_irn_in(block, arity + 1, ins);
184 new_pred_arity = get_irn_arity(pred_block) - 1;
185 NEW_ARR_A(ir_node*, pred_ins, new_pred_arity);
187 for (phi = get_block_blockinfo(pred_block)->phi; phi != NULL; phi = get_irn_link(phi)) {
188 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(phi, k);
189 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(phi, k + 1);
190 assert(k == new_pred_arity);
191 if (new_pred_arity > 1) {
192 set_irn_in(phi, new_pred_arity, pred_ins);
194 exchange(phi, pred_ins[0]);
198 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(pred_block, k);
199 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(pred_block, k + 1);
200 assert(k == new_pred_arity);
201 if (new_pred_arity > 1) {
202 set_irn_in(pred_block, new_pred_arity, pred_ins);
204 exchange(pred_block, get_nodes_block(pred_ins[0]));
209 static void prepare_path(ir_node* block, int i, const ir_node* dependency)
211 ir_node* pred = get_nodes_block(get_irn_n(block, i));
215 DB((dbg, LEVEL_1, "Preparing predecessor %d of %+F\n", i, block));
217 pred_arity = get_irn_arity(pred);
218 for (j = 0; j < pred_arity; ++j) {
219 ir_node* pred_pred = get_nodes_block(get_irn_n(pred, j));
221 if (is_cdep_on(pred_pred, dependency)) {
222 prepare_path(pred, j, dependency);
223 split_block(block, i, j);
230 static void if_conv_walker(ir_node* block, void* env)
235 /* Bail out, if there are no Phis at all */
236 if (get_block_blockinfo(block)->phi == NULL) return;
239 arity = get_irn_arity(block);
240 for (i = 0; i < arity; ++i) {
244 pred = get_nodes_block(get_irn_n(block, i));
245 for (cdep = find_cdep(pred); cdep != NULL; cdep = cdep->next) {
246 const ir_node* dependency = cdep->node;
247 ir_node* projx0 = walk_to_projx(pred, dependency);
251 if (projx0 == NULL) continue;
253 cond = get_Proj_pred(projx0);
254 if (get_irn_op(cond) != op_Cond) continue;
255 /* We only handle boolean decisions, no switches */
256 if (get_irn_mode(get_Cond_selector(cond)) != mode_b) continue;
258 for (j = i + 1; j < arity; ++j) {
266 pred = get_nodes_block(get_irn_n(block, j));
268 if (!is_cdep_on(pred, dependency)) continue;
270 projx1 = walk_to_projx(pred, dependency);
272 if (projx1 == NULL) continue;
274 DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n",
278 prepare_path(block, i, dependency);
279 prepare_path(block, j, dependency);
280 arity = get_irn_arity(block);
282 conds[0] = get_Cond_selector(cond);
284 psi_block = get_nodes_block(cond);
285 phi = get_block_blockinfo(block)->phi;
287 ir_node* val_i = get_irn_n(phi, i);
288 ir_node* val_j = get_irn_n(phi, j);
290 if (val_i == val_j) {
292 DB((dbg, LEVEL_2, "Generating no psi, because both values are equal\n"));
294 /* Something is very fishy if two predecessors of a PhiM point into
295 * one block, but not at the same memory node
297 assert(get_irn_mode(phi) != mode_M);
298 if (get_Proj_proj(projx0) == pn_Cond_true) {
306 current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
308 DB((dbg, LEVEL_2, "Generating %+F for %+F\n", psi, phi));
314 rewire(phi, i, j, psi);
317 phi = get_irn_link(phi);
318 } while (phi != NULL);
320 exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
321 exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
324 DB((dbg, LEVEL_1, "Welding block %+F to %+F\n", block, psi_block));
325 get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
326 exchange(block, psi_block);
329 rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block));
338 * Block walker: add additional data
340 static void init_block_link(ir_node *block, void *env)
342 struct obstack *obst = env;
343 block_info *bi = obstack_alloc(obst, sizeof(*bi));
347 set_irn_link(block, bi);
352 * Daisy-chain all phis in a block
353 * If a non-movable node is encountered set the has_pinned flag
355 static void collect_phis(ir_node *node, void *env)
358 ir_node *block = get_nodes_block(node);
359 block_info *bi = get_block_blockinfo(block);
361 set_irn_link(node, bi->phi);
365 if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
367 * Ignore control flow nodes, these will be removed.
368 * This ignores Raise. That is surely bad. FIXME.
370 if (! is_cfop(node)) {
371 ir_node *block = get_nodes_block(node);
372 block_info *bi = get_block_blockinfo(block);
374 DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
383 * Transform multiple cascaded Psis into one Psi
385 static ir_node* fold_psi(ir_node* psi)
387 int arity = get_Psi_n_conds(psi);
398 for (i = 0; i < arity; ++i) {
399 n = get_Psi_val(psi, i);
400 if (get_irn_op(n) == op_Psi) {
401 new_arity += get_Psi_n_conds(n) + 1;
406 n = get_Psi_default(psi);
407 if (get_irn_op(n) == op_Psi) {
408 new_arity += get_Psi_n_conds(n);
411 if (arity == new_arity) return psi; // no attached Psis found
412 DB((dbg, LEVEL_1, "Folding %+F from %d to %d conds\n", psi, arity, new_arity));
414 NEW_ARR_A(ir_node *, conds, new_arity);
415 NEW_ARR_A(ir_node *, vals, new_arity + 1);
417 for (i = 0; i < arity; ++i) {
418 ir_node* c = get_Psi_cond(psi, i);
420 n = get_Psi_val(psi, i);
421 if (get_irn_op(n) == op_Psi) {
422 a = get_Psi_n_conds(n);
423 for (k = 0; k < a; ++k) {
424 conds[j] = new_r_And(
425 current_ir_graph, get_nodes_block(psi),
426 c, get_Psi_cond(n, k), mode_b
428 vals[j] = get_Psi_val(n, k);
432 vals[j] = get_Psi_default(n);
439 n = get_Psi_default(psi);
440 if (get_irn_op(n) == op_Psi) {
441 a = get_Psi_n_conds(n);
442 for (k = 0; k < a; ++k) {
443 conds[j] = get_Psi_cond(n, k);
444 vals[j] = get_Psi_val(n, k);
447 vals[j] = get_Psi_default(n);
451 assert(j == new_arity);
453 current_ir_graph, get_nodes_block(psi),
454 new_arity, conds, vals, get_irn_mode(psi)
456 DB((dbg, LEVEL_1, "Folded %+F into new %+F\n", psi, new_psi));
457 exchange(psi, new_psi);
463 * Merge consecutive psi inputs if the data inputs are the same
465 static ir_node* meld_psi(ir_node* psi)
467 int arity = get_Psi_n_conds(psi);
478 val = get_Psi_val(psi, 0);
479 DB((dbg, LEVEL_1, "Pred 0 of %+F is %+F\n", psi, val));
480 for (i = 1; i < arity; ++i) {
481 ir_node* v = get_Psi_val(psi, i);
482 DB((dbg, LEVEL_1, "Pred %2d of %+F is %+F\n", i, psi, v));
488 DB((dbg, LEVEL_1, "Default of %+F is %+F\n", psi, get_Psi_default(psi)));
489 if (val == get_Psi_default(psi)) --new_arity;
491 DB((dbg, LEVEL_1, "Melding Psi %+F from %d conds to %d\n", psi, arity, new_arity));
493 if (new_arity == arity) return psi;
495 /* If all data inputs of the Psi are equal, exchange the Psi with that value */
496 if (new_arity == 0) {
501 NEW_ARR_A(ir_node *, conds, new_arity);
502 NEW_ARR_A(ir_node *, vals, new_arity + 1);
503 cond = get_Psi_cond(psi, 0);
504 val = get_Psi_val(psi, 0);
506 for (i = 1; i < arity; ++i) {
507 ir_node* v = get_Psi_val(psi, i);
511 current_ir_graph, get_nodes_block(psi),
512 cond, get_Psi_cond(psi, i), mode_b
521 if (val != get_Psi_default(psi)) {
526 vals[j] = get_Psi_default(psi);
527 assert(j == new_arity);
529 current_ir_graph, get_nodes_block(psi),
530 new_arity, conds, vals, get_irn_mode(psi)
532 DB((dbg, LEVEL_1, "Molded %+F into %+F\n", psi, new_psi));
533 exchange(psi, new_psi);
539 * Split a Psi with multiple conditions into multiple Psis with one condtition
542 static ir_node* split_psi(ir_node* psi)
544 int arity = get_Psi_n_conds(psi);
550 if (arity == 1) return psi;
552 mode = get_irn_mode(psi);
553 block = get_nodes_block(psi);
554 rval = get_Psi_default(psi);
555 for (i = arity - 1; i >= 0; --i) {
559 conds[0] = get_Psi_cond(psi, i);
560 vals[0] = get_Psi_val(psi, i);
563 current_ir_graph, block, 1, conds, vals, mode
571 static void optimise_psis(ir_node* node, void* env)
573 if (get_irn_op(node) != op_Psi) return;
575 node = fold_psi(node);
578 node = meld_psi(node);
581 node = split_psi(node);
586 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
590 if (!get_opt_if_conversion())
593 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
595 DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
597 dump_ir_block_graph(irg, "_00_pre");
599 normalize_one_return(irg);
600 remove_critical_cf_edges(irg);
602 dump_ir_block_graph(irg, "_01_normal");
608 irg_block_walk_graph(irg, init_block_link, NULL, &obst);
609 irg_walk_graph(irg, collect_phis, NULL, NULL);
610 irg_block_walk_graph(irg, NULL, if_conv_walker, NULL);
612 dump_ir_block_graph(irg, "_02_ifconv");
613 local_optimize_graph(irg);
614 dump_ir_block_graph(irg, "_03_postopt");
616 irg_walk_graph(irg, NULL, optimise_psis, NULL);
618 dump_ir_block_graph(irg, "_04_postifconv");
620 obstack_free(&obst, NULL);
631 * Make Mux nodes from Conds where it its possible.
632 * @author Sebastian Hack
649 #include "irgraph_t.h"
650 #include "irnode_t.h"
654 #include "irmode_t.h"
655 #include "ircons_t.h"
660 #include "irflag_t.h"
662 #include "irprintf.h"
667 #include "bitfiddle.h"
674 * check, if a node is const and return its tarval or
675 * return a default tarval.
676 * @param cnst The node whose tarval to get.
677 * @param or The alternative tarval, if the node is no Const.
678 * @return The tarval of @p cnst, if the node is Const, @p otherwise.
680 static tarval *get_value_or(ir_node *cnst, tarval *or)
682 return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
687 * Try to optimize nested muxes into a dis- or conjunction
689 * @param mux The parent mux, which has muxes as operands.
690 * @return The replacement node for this mux. If the optimization is
691 * successful, this might be an And or Or node, if not, its the mux
694 static ir_node *optimize_mux_chain(ir_node *mux)
699 ir_mode *mode = get_irn_mode(mux);
704 * If we have no mux, or its mode is not integer, we
707 if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
711 null = get_mode_null(mode);
712 minus_one = tarval_sub(null, get_tarval_one(mode));
714 ops[0] = get_Mux_false(mux);
715 ops[1] = get_Mux_true(mux);
717 for(i = 0; i < 2; ++i) {
719 tarval *tva, *tvb, *tvd;
723 * A mux operand at the first position can be factored
724 * out, if the operands fulfill several conditions:
726 * mux(c1, mux(c2, a, b), d)
728 * This can be made into:
729 * 1) mux(c1, 0, d) | mux(c2, a, b)
730 * if a | d == d and b | d == d
732 * 2) mux(c1, -1, d) & mux(c2, a, b)
733 * if a & d == d and a & b == b
735 if(get_irn_op(ops[i]) == op_Mux) {
738 a = get_Mux_false(child_mux);
739 b = get_Mux_true(child_mux);
742 /* Try the or stuff */
743 tva = get_value_or(a, minus_one);
744 tvb = get_value_or(b, minus_one);
745 tvd = get_value_or(d, null);
747 if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
748 && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
750 ops[i] = new_Const(mode, null);
751 res = new_r_Or(current_ir_graph, get_nodes_block(mux),
752 mux, child_mux, mode);
756 /* If the or didn't go, try the and stuff */
757 tva = get_value_or(a, null);
758 tvb = get_value_or(b, null);
759 tvd = get_value_or(d, minus_one);
761 if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
762 && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
764 ops[i] = new_Const(mode, minus_one);
765 res = new_r_And(current_ir_graph, get_nodes_block(mux),
766 mux, child_mux, mode);
772 /* recursively optimize nested muxes. */
773 set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
774 set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
780 /***********************************************************
781 * The If conversion itself.
782 ***********************************************************/
784 /** allow every Mux to be created. */
785 static int default_allow_mux(ir_node *sel, ir_node *false_res, ir_node *true_res) {
792 static const opt_if_conv_info_t default_info = {
797 /** The debugging module. */
798 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
801 * A simple check for side effects upto an opcode of a ir node.
802 * @param irn The ir node to check,
803 * @return 1 if the opcode itself may produce side effects, 0 if not.
805 static INLINE int has_side_effects(const ir_node *irn)
807 ir_op *op = get_irn_op(irn);
812 return !mode_is_datab(get_irn_mode(irn));
816 * Possible failure reasons
818 enum failure_reason_t {
819 SUCCESS = IF_RESULT_SUCCESS,
820 TO_DEEP = IF_RESULT_TOO_DEEP,
821 SIDE_EFFECTS = IF_RESULT_SIDE_EFFECT,
822 PHI_FOUND = IF_RESULT_SIDE_EFFECT_PHI,
823 DENIED = IF_RESULT_DENIED
827 * Decides, if a given expression and its subexpressions
828 * (to certain, also given extent) can be moved to a block.
830 * @param expr The expression to examine.
831 * @param block The block where the expression should go.
832 * @param depth The current depth, passed recursively. Use 0 for
833 * non-recursive calls.
834 * @param info The options for createing Mux nodes.
837 * @return a failure reason
839 static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, const opt_if_conv_info_t *info)
843 ir_node *expr_block = get_nodes_block(expr);
846 * If we are forced to look too deep into the expression,
847 * treat it like it could not be moved.
849 if(depth >= info->max_depth) {
855 * If the block of the expression dominates the specified
856 * destination block, it does not matter if the expression
857 * has side effects or anything else. It is executed on each
858 * path the destination block is reached.
860 if (block_dominates(expr_block, dest_block))
864 * We cannot move phis!
872 * This should be superfluous and could be converted into a assertion.
873 * The destination block _must_ dominate the block of the expression,
874 * else the expression could be used without its definition.
876 if (! block_dominates(dest_block, expr_block)) {
877 res = IF_RESULT_SIDE_EFFECT;
882 * Surely, if the expression does not have a data mode, it is not
883 * movable. Perhaps one should also test the floating property of
886 if (has_side_effects(expr)) {
887 res = IF_RESULT_SIDE_EFFECT;
892 * If the node looks alright so far, look at its operands and
893 * check them out. If one of them cannot be moved, this one
894 * cannot be moved either.
896 for (i = 0, n = get_irn_arity(expr); i < n; ++i) {
897 ir_node *op = get_irn_n(expr, i);
898 int new_depth = is_Proj(op) ? depth : depth + 1;
900 res = _can_move_to(op, dest_block, new_depth, info);
907 DBG((dbg, LEVEL_3, "\t\t\tcan move to %n: %d\n", expr, res));
913 * Convenience function for _can_move_to.
914 * Checks, if an expression can be moved to another block. The check can
915 * be limited to a expression depth meaning if we need to crawl in
916 * deeper into an expression than a given threshold to examine if
917 * it can be moved, the expression is rejected and the test returns
920 * @param expr The expression to check for.
921 * @param dest_block The destination block you want @p expr to be.
922 * @param info The options for createing Mux nodes.
924 * @return return a failure reason
926 static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, const opt_if_conv_info_t *info)
928 return _can_move_to(expr, dest_block, 0, info);
932 * move a DAG given by a root node expr into a new block
934 * @param expr the root of a dag
935 * @param dest_block the destination block
937 static void move_to(ir_node *expr, ir_node *dest_block)
940 ir_node *expr_block = get_nodes_block(expr);
943 * If we reached the dominator, we are done.
944 * We will never put code through the dominator
946 if (block_dominates(expr_block, dest_block))
949 for (i = 0, n = get_irn_arity(expr); i < n; ++i)
950 move_to(get_irn_n(expr, i), dest_block);
952 set_nodes_block(expr, dest_block);
956 * return the common dominator of two blocks
958 static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2)
960 if(block_dominates(b1, b2))
962 else if(block_dominates(b2, b1))
967 for (p = get_Block_idom(b1); !block_dominates(p, b2); p = get_Block_idom(p));
973 * Information about a cond node.
975 typedef struct _cond_t {
976 ir_node *cond; /**< The cond node. */
977 struct list_head list; /**< List head which is used for queuing this cond
978 into the cond bunch it belongs to. */
980 unsigned totally_covers : 1;
981 struct _cond_t *link;
985 * Information about the both 'branches'
986 * (true and false), the cond creates.
989 int pos; /**< Number of the predecessor of the
990 phi block by which this branch is
991 reached. It is -1, if this branch is
992 only reached through another cond. */
994 struct _cond_t *masked_by; /**< If this cond's branch is only reached
995 through another cond, we store this
996 cond ir_node here. */
1001 * retrieve the conditional information from a Cond node
1003 static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
1008 return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
1012 typedef void (cond_walker_t)(cond_t *cond, void *env);
1014 static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
1015 long visited_nr, void *env)
1019 if(cond->visited_nr >= visited_nr)
1022 cond->visited_nr = visited_nr;
1027 for(i = 0; i < 2; ++i) {
1028 cond_t *c = cond->cases[i].masked_by;
1031 _walk_conds(c, pre, post, visited_nr, env);
1038 static long cond_visited_nr = 0;
1040 static void walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post, void *env)
1042 _walk_conds(cond, pre, post, ++cond_visited_nr, env);
1045 static void link_conds(cond_t *cond, void *env)
1047 cond_t **ptr = (cond_t **) env;
1054 * Compare two conds for use in a firm set.
1055 * Two cond_t's are equal, if they designate the same cond node.
1056 * @param a A cond_t.
1057 * @param b Another one.
1058 * @param size Not used.
1059 * @return 0 (!) if they are equal, != 0 otherwise.
1061 static int cond_cmp(const void *a, const void *b, size_t size)
1063 const cond_t *x = a;
1064 const cond_t *y = b;
1065 return x->cond != y->cond;
1069 * Information about conds which can be made to muxes.
1070 * Instances of this struct are attached to the link field of
1071 * blocks in which phis are located.
1073 typedef struct _cond_info_t {
1074 struct list_head list; /**< Used to list all of these structs per class. */
1076 struct list_head roots; /**< A list of non-depending Conds. Two Conds are
1077 independent, if it's not possible not reach one from the
1078 other (all Conds in this list have to dominate the
1079 block this struct is attached to). */
1081 ir_node *first_phi; /**< The first phi node this cond info was made for. */
1082 set *cond_set; /**< A set of all dominating reachable Conds. */
1088 static void _find_conds(ir_node *irn, unsigned long visited_nr,
1089 ir_node *dominator, cond_t *masked_by, int pos, int depth, cond_info_t *ci)
1092 int saw_select_cond = 0;
1094 block = get_nodes_block(irn);
1097 * Only check this block if it is dominated by the specified
1098 * dominator or it has not been visited yet.
1100 if (block_dominates(dominator, block) && get_Block_block_visited(block) < visited_nr) {
1101 cond_t *res = masked_by;
1104 /* check, if we're on a ProjX
1106 * Further, the ProjX/Cond block must dominate the base block
1107 * (the block with the phi in it), otherwise, the Cond
1108 * is not affecting the phi so that a mux can be inserted.
1110 if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
1112 int proj = get_Proj_proj(irn);
1113 ir_node *cond = get_Proj_pred(irn);
1115 /* true, if the mode is a mode_b cond _NO_ switch cond */
1116 int is_modeb_cond = get_irn_opcode(cond) == iro_Cond
1117 && get_irn_mode(get_Cond_selector(cond)) == mode_b;
1119 saw_select_cond = !is_modeb_cond;
1121 /* Check, if the pred of the proj is a Cond
1122 * with a Projb as selector.
1127 memset(&c, 0, sizeof(c));
1130 c.cases[0].pos = -1;
1131 c.cases[1].pos = -1;
1133 /* get or insert the cond info into the set. */
1134 res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
1137 * If this cond is already masked by the masked_by cond
1138 * return immediately, since we don't have anything to add.
1140 if(masked_by && res->cases[proj].masked_by == masked_by)
1145 list_add(&res->list, &ci->roots);
1149 * Set masked by (either NULL or another cond node.
1150 * If this cond is truly masked by another one, set
1151 * the position of the actually investigated branch
1152 * to -1. Since the cond is masked by another one,
1153 * there could be more ways from the start block
1154 * to this branch, so we choose -1.
1156 res->cases[proj].masked_by = masked_by;
1159 res->cases[proj].pos = pos;
1162 * Since the masked_by nodes masks a cond, remove it from the
1163 * root list of the conf trees.
1166 assert(res->cases[proj].pos < 0);
1167 list_del_init(&masked_by->list);
1170 DBG((dbg, LEVEL_2, "%n (%s branch) "
1171 "for pos %d in block %n reached by %n\n",
1172 cond, proj ? "true" : "false", pos,
1173 block, masked_by ? masked_by->cond : NULL));
1177 if(get_Block_block_visited(block) < visited_nr && !saw_select_cond) {
1179 set_Block_block_visited(block, visited_nr);
1181 /* Search recursively from this cond. */
1182 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1183 ir_node *pred = get_irn_n(block, i);
1186 * If the depth is 0 (the first recursion), we set the pos to
1187 * the current viewed predecessor, else we adopt the position
1188 * as given by the caller. We also increase the depth for the
1189 * recursively called functions.
1191 _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci);
1199 * A convenience function for _find_conds.
1200 * It sets some parameters needed for recursion to appropriate start
1201 * values. Always use this function.
1203 * @param irn The node to start looking for Conds from. This might
1204 * be the phi node we are investigating.
1205 * @param conds The set to record the found Conds in.
1207 static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
1210 unsigned long visited_nr;
1211 ir_node *block = get_nodes_block(irn);
1212 ir_node *dom = get_Block_idom(block);
1214 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1215 ir_node *pred = get_irn_n(block, i);
1217 inc_irg_block_visited(current_ir_graph);
1218 visited_nr = get_irg_block_visited(current_ir_graph);
1219 set_Block_block_visited(block, visited_nr);
1221 DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
1222 _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
1227 * Make the mux for a given cond.
1229 * @param phi The phi node which shall be replaced by a mux.
1230 * @param dom The block where the muxes shall be placed.
1231 * @param cond The cond information.
1232 * @param info The options for createing Mux nodes.
1233 * @return The mux node made for this cond.
1235 static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond,
1236 const opt_if_conv_info_t *info, ir_node **mux, bitset_t *positions,
1237 int *muxes_made, long visited_nr)
1240 ir_node *projb = get_Cond_selector(cond->cond);
1241 ir_node *bl = get_nodes_block(cond->cond);
1242 ir_node *operands[2];
1245 cond->visited_nr = visited_nr;
1246 DBG((dbg, LEVEL_2, "%n\n", cond->cond));
1247 for(i = 0; i < 2; ++i) {
1248 cond_t *masked_by = cond->cases[i].masked_by;
1249 int pos = cond->cases[i].pos;
1255 * If this Cond branch is masked by another cond, make the mux
1256 * for that Cond first, since the Mux for this cond takes
1261 DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
1262 if(masked_by->visited_nr < visited_nr)
1263 operands[i] = make_mux_on_demand(phi, dom, masked_by, info, mux, positions, muxes_made, visited_nr);
1267 * If this cond branch is not masked by another cond, take
1268 * the corresponding phi operand as an operand to the mux.
1271 operands[i] = get_irn_n(phi, pos);
1277 * Move the operands to the dominator block if the cond
1278 * made sense. Some Conds found are not suitable for making a mux
1279 * out of them, since one of their branches cannot be reached from
1280 * the phi block. In that case we do not make a mux and return NULL.
1282 if(operands[0] && operands[1]) {
1283 if (operands[0] == operands[1]) {
1284 /* there is no gain in using mux in this case, as
1285 it will be optimized away. We will NOT move the
1286 content of the blocks either
1288 for (i = 0; i < 2; ++i)
1290 bitset_set(positions, set[i]);
1296 can_move[0] = can_move_to(operands[0], bl, info);
1297 can_move[1] = can_move_to(operands[1], bl, info);
1299 if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) {
1300 if (info->allow_mux(projb, operands[0], operands[1])) {
1301 move_to(operands[0], bl);
1302 move_to(operands[1], bl);
1305 *mux = new_r_Mux(current_ir_graph, bl, projb,
1306 operands[0], operands[1], get_irn_mode(operands[0]));
1310 DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
1311 *mux, projb, operands[0], operands[1], set[0], set[1]));
1313 for(i = 0; i < 2; ++i)
1315 bitset_set(positions, set[i]);
1317 /* we have done one */
1318 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_SUCCESS);
1322 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_DENIED);
1326 if(can_move[0] != SUCCESS)
1327 hook_if_conversion(current_ir_graph, phi, set[0], NULL, can_move[0]);
1328 if(can_move[1] != SUCCESS)
1329 hook_if_conversion(current_ir_graph, phi, set[1], NULL, can_move[1]);
1334 hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF);
1336 hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF);
1342 typedef struct _phi_info_t {
1343 struct list_head list;
1344 cond_info_t *cond_info;
1350 * Examine a phi node if it can be replaced by some muxes.
1351 * @param irn A phi node.
1352 * @param info Parameters for the if conversion algorithm.
1354 static int check_out_phi(phi_info_t *phi_info, const opt_if_conv_info_t *info)
1356 ir_node *irn = phi_info->irn;
1357 ir_node *block, *nw;
1358 cond_info_t *cond_info = phi_info->cond_info;
1362 bitset_t *positions;
1364 block = get_nodes_block(irn);
1365 arity = get_irn_arity(irn);
1366 positions = bitset_alloca(arity);
1368 assert(is_Phi(irn));
1369 assert(get_irn_arity(irn) == get_irn_arity(block));
1372 DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
1374 list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
1375 ir_node *cidom = block;
1376 ir_node *mux = NULL;
1377 cond_t *p, *head = NULL;
1380 bitset_clear_all(positions);
1382 DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
1384 * Link all conds which are in the subtree of
1385 * the current cond in the list together.
1387 walk_conds(cond, link_conds, NULL, &head);
1390 for(p = head; p; p = p->link) {
1391 for(i = 0; i < 2; ++i) {
1392 int pos = p->cases[i].pos;
1394 cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
1398 DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
1399 make_mux_on_demand(irn, cidom, cond, info, &mux, positions, &muxes_made, ++cond_visited_nr);
1402 bitset_foreach(positions, pos)
1403 set_irn_n(irn, (int) pos, mux);
1408 * optimize the phi away. This can anable further runs of this
1409 * function. Look at _can_move. phis cannot be moved there.
1411 nw = optimize_in_place_2(irn);
1418 typedef struct _cond_walk_info_t {
1419 struct obstack *obst;
1420 struct list_head cond_info_head;
1421 struct list_head phi_head;
1425 static void annotate_cond_info_pre(ir_node *irn, void *data)
1427 set_irn_link(irn, NULL);
1430 static void annotate_cond_info_post(ir_node *irn, void *data)
1432 cond_walk_info_t *cwi = data;
1435 * Check, if the node is a phi
1436 * we then compute a set of conds which are reachable from this
1437 * phi's block up to its dominator.
1438 * The set is attached to the blocks link field.
1440 if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
1441 ir_node *block = get_nodes_block(irn);
1443 cond_info_t *ci = get_irn_link(block);
1445 /* If the set is not yet computed, do it now. */
1447 ci = obstack_alloc(cwi->obst, sizeof(*ci));
1448 ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
1449 ci->first_phi = irn;
1451 INIT_LIST_HEAD(&ci->roots);
1452 INIT_LIST_HEAD(&ci->list);
1455 * Add this cond info to the list of all cond infos
1456 * in this graph. This is just done to xfree the
1457 * set easier afterwards (we save an irg_walk_graph).
1459 list_add(&cwi->cond_info_head, &ci->list);
1461 DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
1464 * Fill the set with conds we find on the way from
1465 * the block to its dominator.
1467 find_conds(irn, ci);
1470 * If there where no suitable conds, delete the set
1471 * immediately and reset the set pointer to NULL
1473 if(set_count(ci->cond_set) == 0) {
1474 del_set(ci->cond_set);
1475 list_del(&ci->list);
1476 obstack_free(cwi->obst, ci);
1482 DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
1484 set_irn_link(block, ci);
1487 phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
1490 INIT_LIST_HEAD(&pi->list);
1491 list_add(&pi->list, &cwi->phi_head);
1497 static void dump_conds(cond_t *cond, void *env)
1502 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
1503 cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
1504 get_nodes_block(cond->cond));
1506 for(i = 0; i < 2; ++i)
1507 if(cond->cases[i].masked_by)
1508 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
1509 cond, cond->cases[i].masked_by, i);
1512 static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi)
1517 snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
1519 if((f = fopen(buf, "wt")) != NULL) {
1524 ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
1525 list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
1526 ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
1527 list_for_each_entry(cond_t, cond, &ci->roots, list) {
1528 walk_conds(cond, NULL, dump_conds, f);
1529 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
1533 list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
1534 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
1535 phi->irn, phi->irn, get_nodes_block(phi->irn));
1536 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
1542 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
1545 struct obstack obst;
1546 phi_info_t *phi_info;
1547 cond_info_t *cond_info;
1548 cond_walk_info_t cwi;
1550 opt_if_conv_info_t p;
1552 if(!get_opt_if_conversion())
1555 /* get the parameters */
1557 memcpy(&p, params, sizeof(p));
1559 memcpy(&p, &default_info, sizeof(p));
1562 p.allow_mux = default_info.allow_mux;
1564 obstack_init(&obst);
1567 INIT_LIST_HEAD(&cwi.cond_info_head);
1568 INIT_LIST_HEAD(&cwi.phi_head);
1570 /* Init the debug stuff. */
1571 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
1573 firm_dbg_set_mask(dbg, LEVEL_1|LEVEL_2|LEVEL_3);
1576 /* if-conversion works better with normalized returns */
1577 normalize_one_return(irg);
1579 /* Ensure, that the dominators are computed. */
1582 DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
1583 get_entity_name(get_irg_entity(irg)), irg));
1586 * Collect information about the conds pu the phis on an obstack.
1587 * It is important that phi nodes which are 'higher' (with a
1588 * lower dfs pre order) are in front of the obstack. Since they are
1589 * possibly turned in to muxes this can enable the optimization
1592 irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
1595 vcg_dump_conds(irg, &cwi);
1598 /* Process each suitable phi found. */
1599 list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
1600 DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
1601 muxes_made += check_out_phi(phi_info, &p);
1604 list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
1605 del_set(cond_info->cond_set);
1608 DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
1610 obstack_free(&obst, NULL);
1612 dump_ir_block_graph(irg, "_ifconv_hack");