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) {
82 assert(get_irn_mode(pred) == mode_X);
89 assert(get_irn_mode(pred) == mode_X);
93 if (is_cdep_on(pred_block, dependency)) {
94 return walk_to_projx(pred_block, dependency);
102 * Copies the DAG starting at node to the ith predecessor block of src_block
103 * -if the node isn't in the src_block, this is a nop and the node is returned
104 * -if the node is a phi in the src_block, the ith predecessor of the phi is
106 * otherwise returns the copy of the passed node
108 static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
115 if (get_nodes_block(node) != src_block) return node;
116 if (get_irn_op(node) == op_Phi) return get_irn_n(node, i);
118 copy = exact_copy(node);
119 dst_block = get_nodes_block(get_irn_n(src_block, i));
120 set_nodes_block(copy, dst_block);
122 DB((dbg, LEVEL_1, "Copying node %+F to block %+F, copy is %+F\n",
123 node, dst_block, copy));
125 arity = get_irn_arity(node);
126 for (j = 0; j < arity; ++j) {
127 set_irn_n(copy, j, copy_to(get_irn_n(node, j), src_block, i));
128 DB((dbg, LEVEL_2, "-- pred %d is %+F\n", j, get_irn_n(copy, j)));
135 * Remove predecessors i and j from node and add predecessor new_pred
137 static void rewire(ir_node* node, int i, int j, ir_node* new_pred)
139 int arity = get_irn_arity(node);
144 NEW_ARR_A(ir_node *, ins, arity - 1);
147 for (k = 0; k < i; ++k) ins[l++] = get_irn_n(node, k);
148 for (++k; k < j; ++k) ins[l++] = get_irn_n(node, k);
149 for (++k; k < arity; ++k) ins[l++] = get_irn_n(node, k);
151 assert(l == arity - 1);
152 set_irn_in(node, l, ins);
157 * Remove the jth predecessors from the ith predecessor of block and add it to block
159 static void split_block(ir_node* block, int i, int j)
161 ir_node* pred_block = get_nodes_block(get_irn_n(block, i));
162 int arity = get_irn_arity(block);
169 DB((dbg, LEVEL_1, "Splitting predecessor %d of predecessor %d of %+F\n", j, i, block));
171 NEW_ARR_A(ir_node*, ins, arity + 1);
173 for (phi = get_block_blockinfo(block)->phi; phi != NULL; phi = get_irn_link(phi)) {
174 ir_node* copy = copy_to(get_irn_n(phi, i), pred_block, j);
176 for (k = 0; k < i; ++k) ins[k] = get_irn_n(phi, k);
178 for (; k < arity; ++k) ins[k] = get_irn_n(phi, k);
179 ins[k] = get_irn_n(phi, i);
181 set_irn_in(phi, arity + 1, ins);
184 for (k = 0; k < i; ++k) ins[k] = get_irn_n(block, k);
185 ins[k++] = get_irn_n(pred_block, j);
186 for (; k < arity; ++k) ins[k] = get_irn_n(block, k);
187 ins[k] = get_irn_n(block, i);
189 set_irn_in(block, arity + 1, ins);
191 new_pred_arity = get_irn_arity(pred_block) - 1;
192 NEW_ARR_A(ir_node*, pred_ins, new_pred_arity);
194 for (phi = get_block_blockinfo(pred_block)->phi; phi != NULL; phi = get_irn_link(phi)) {
195 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(phi, k);
196 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(phi, k + 1);
197 assert(k == new_pred_arity);
198 if (new_pred_arity > 1) {
199 set_irn_in(phi, new_pred_arity, pred_ins);
201 exchange(phi, pred_ins[0]);
205 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(pred_block, k);
206 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(pred_block, k + 1);
207 assert(k == new_pred_arity);
208 if (new_pred_arity > 1) {
209 set_irn_in(pred_block, new_pred_arity, pred_ins);
211 exchange(pred_block, get_nodes_block(pred_ins[0]));
216 static void prepare_path(ir_node* block, int i, const ir_node* dependency)
218 ir_node* pred = get_nodes_block(get_irn_n(block, i));
222 DB((dbg, LEVEL_1, "Preparing predecessor %d of %+F\n", i, block));
224 pred_arity = get_irn_arity(pred);
225 for (j = 0; j < pred_arity; ++j) {
226 ir_node* pred_pred = get_nodes_block(get_irn_n(pred, j));
228 if (is_cdep_on(pred_pred, dependency)) {
229 prepare_path(pred, j, dependency);
230 split_block(block, i, j);
237 static void if_conv_walker(ir_node* block, void* env)
242 /* Bail out, if there are no Phis at all */
243 if (get_block_blockinfo(block)->phi == NULL) return;
246 arity = get_irn_arity(block);
247 for (i = 0; i < arity; ++i) {
251 pred = get_nodes_block(get_irn_n(block, i));
252 for (cdep = find_cdep(pred); cdep != NULL; cdep = cdep->next) {
253 const ir_node* dependency = cdep->node;
254 ir_node* projx0 = walk_to_projx(pred, dependency);
258 if (projx0 == NULL) continue;
260 cond = get_Proj_pred(projx0);
261 if (get_irn_op(cond) != op_Cond) continue;
262 /* We only handle boolean decisions, no switches */
263 if (get_irn_mode(get_Cond_selector(cond)) != mode_b) continue;
265 for (j = i + 1; j < arity; ++j) {
273 pred = get_nodes_block(get_irn_n(block, j));
275 if (!is_cdep_on(pred, dependency)) continue;
277 projx1 = walk_to_projx(pred, dependency);
279 if (projx1 == NULL) continue;
281 DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n",
285 prepare_path(block, i, dependency);
286 prepare_path(block, j, dependency);
287 arity = get_irn_arity(block);
289 conds[0] = get_Cond_selector(cond);
291 psi_block = get_nodes_block(cond);
292 phi = get_block_blockinfo(block)->phi;
294 ir_node* val_i = get_irn_n(phi, i);
295 ir_node* val_j = get_irn_n(phi, j);
297 if (val_i == val_j) {
299 DB((dbg, LEVEL_2, "Generating no psi, because both values are equal\n"));
301 /* Something is very fishy if two predecessors of a PhiM point into
302 * one block, but not at the same memory node
304 assert(get_irn_mode(phi) != mode_M);
305 if (get_Proj_proj(projx0) == pn_Cond_true) {
313 current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
315 DB((dbg, LEVEL_2, "Generating %+F for %+F\n", psi, phi));
321 rewire(phi, i, j, psi);
324 phi = get_irn_link(phi);
325 } while (phi != NULL);
327 exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
328 exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
332 DB((dbg, LEVEL_1, "Welding block %+F and %+F\n", block, psi_block));
333 /* copy the block-info from the Psi-block to the block before merging */
334 get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
335 set_irn_link(block, get_irn_link(psi_block));
337 set_irn_in(block, get_irn_arity(psi_block), get_irn_in(psi_block) + 1);
338 exchange_cdep(psi_block, block);
339 exchange(psi_block, block);
341 DB((dbg, LEVEL_1, "Welding block %+F to %+F\n", block, psi_block));
342 get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
343 exchange(block, psi_block);
347 rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block));
356 * Block walker: add additional data
358 static void init_block_link(ir_node *block, void *env)
360 struct obstack *obst = env;
361 block_info *bi = obstack_alloc(obst, sizeof(*bi));
365 set_irn_link(block, bi);
370 * Daisy-chain all phis in a block
371 * If a non-movable node is encountered set the has_pinned flag
373 static void collect_phis(ir_node *node, void *env)
376 ir_node *block = get_nodes_block(node);
377 block_info *bi = get_block_blockinfo(block);
379 set_irn_link(node, bi->phi);
383 if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
385 * Ignore control flow nodes, these will be removed.
386 * This ignores Raise. That is surely bad. FIXME.
388 if (! is_cfop(node)) {
389 ir_node *block = get_nodes_block(node);
390 block_info *bi = get_block_blockinfo(block);
392 DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
401 * Transform multiple cascaded Psis into one Psi
403 static ir_node* fold_psi(ir_node* psi)
405 int arity = get_Psi_n_conds(psi);
416 for (i = 0; i < arity; ++i) {
417 n = get_Psi_val(psi, i);
418 if (get_irn_op(n) == op_Psi) {
419 new_arity += get_Psi_n_conds(n) + 1;
424 n = get_Psi_default(psi);
425 if (get_irn_op(n) == op_Psi) {
426 new_arity += get_Psi_n_conds(n);
429 if (arity == new_arity) return psi; // no attached Psis found
430 DB((dbg, LEVEL_1, "Folding %+F from %d to %d conds\n", psi, arity, new_arity));
432 NEW_ARR_A(ir_node *, conds, new_arity);
433 NEW_ARR_A(ir_node *, vals, new_arity + 1);
435 for (i = 0; i < arity; ++i) {
436 ir_node* c = get_Psi_cond(psi, i);
438 n = get_Psi_val(psi, i);
439 if (get_irn_op(n) == op_Psi) {
440 a = get_Psi_n_conds(n);
441 for (k = 0; k < a; ++k) {
442 conds[j] = new_r_And(
443 current_ir_graph, get_nodes_block(psi),
444 c, get_Psi_cond(n, k), mode_b
446 vals[j] = get_Psi_val(n, k);
450 vals[j] = get_Psi_default(n);
457 n = get_Psi_default(psi);
458 if (get_irn_op(n) == op_Psi) {
459 a = get_Psi_n_conds(n);
460 for (k = 0; k < a; ++k) {
461 conds[j] = get_Psi_cond(n, k);
462 vals[j] = get_Psi_val(n, k);
465 vals[j] = get_Psi_default(n);
469 assert(j == new_arity);
471 current_ir_graph, get_nodes_block(psi),
472 new_arity, conds, vals, get_irn_mode(psi)
474 DB((dbg, LEVEL_1, "Folded %+F into new %+F\n", psi, new_psi));
475 exchange(psi, new_psi);
481 * Merge consecutive psi inputs if the data inputs are the same
483 static ir_node* meld_psi(ir_node* psi)
485 int arity = get_Psi_n_conds(psi);
496 val = get_Psi_val(psi, 0);
497 DB((dbg, LEVEL_1, "Pred 0 of %+F is %+F\n", psi, val));
498 for (i = 1; i < arity; ++i) {
499 ir_node* v = get_Psi_val(psi, i);
500 DB((dbg, LEVEL_1, "Pred %2d of %+F is %+F\n", i, psi, v));
506 DB((dbg, LEVEL_1, "Default of %+F is %+F\n", psi, get_Psi_default(psi)));
507 if (val == get_Psi_default(psi)) --new_arity;
509 DB((dbg, LEVEL_1, "Melding Psi %+F from %d conds to %d\n", psi, arity, new_arity));
511 if (new_arity == arity) return psi;
513 /* If all data inputs of the Psi are equal, exchange the Psi with that value */
514 if (new_arity == 0) {
519 NEW_ARR_A(ir_node *, conds, new_arity);
520 NEW_ARR_A(ir_node *, vals, new_arity + 1);
521 cond = get_Psi_cond(psi, 0);
522 val = get_Psi_val(psi, 0);
524 for (i = 1; i < arity; ++i) {
525 ir_node* v = get_Psi_val(psi, i);
529 current_ir_graph, get_nodes_block(psi),
530 cond, get_Psi_cond(psi, i), mode_b
539 if (val != get_Psi_default(psi)) {
544 vals[j] = get_Psi_default(psi);
545 assert(j == new_arity);
547 current_ir_graph, get_nodes_block(psi),
548 new_arity, conds, vals, get_irn_mode(psi)
550 DB((dbg, LEVEL_1, "Molded %+F into %+F\n", psi, new_psi));
551 exchange(psi, new_psi);
557 * Split a Psi with multiple conditions into multiple Psis with one condtition
560 static ir_node* split_psi(ir_node* psi)
562 int arity = get_Psi_n_conds(psi);
568 if (arity == 1) return psi;
570 mode = get_irn_mode(psi);
571 block = get_nodes_block(psi);
572 rval = get_Psi_default(psi);
573 for (i = arity - 1; i >= 0; --i) {
577 conds[0] = get_Psi_cond(psi, i);
578 vals[0] = get_Psi_val(psi, i);
581 current_ir_graph, block, 1, conds, vals, mode
589 static void optimise_psis(ir_node* node, void* env)
591 if (get_irn_op(node) != op_Psi) return;
593 node = fold_psi(node);
596 node = meld_psi(node);
599 node = split_psi(node);
604 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
608 if (!get_opt_if_conversion())
611 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
613 DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
615 normalize_one_return(irg);
616 remove_critical_cf_edges(irg);
622 irg_block_walk_graph(irg, init_block_link, NULL, &obst);
623 irg_walk_graph(irg, collect_phis, NULL, NULL);
624 irg_block_walk_graph(irg, NULL, if_conv_walker, NULL);
626 local_optimize_graph(irg);
628 irg_walk_graph(irg, NULL, optimise_psis, NULL);
630 obstack_free(&obst, NULL);
641 * Make Mux nodes from Conds where it its possible.
642 * @author Sebastian Hack
659 #include "irgraph_t.h"
660 #include "irnode_t.h"
664 #include "irmode_t.h"
665 #include "ircons_t.h"
670 #include "irflag_t.h"
672 #include "irprintf.h"
677 #include "bitfiddle.h"
684 * check, if a node is const and return its tarval or
685 * return a default tarval.
686 * @param cnst The node whose tarval to get.
687 * @param or The alternative tarval, if the node is no Const.
688 * @return The tarval of @p cnst, if the node is Const, @p otherwise.
690 static tarval *get_value_or(ir_node *cnst, tarval *or)
692 return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
697 * Try to optimize nested muxes into a dis- or conjunction
699 * @param mux The parent mux, which has muxes as operands.
700 * @return The replacement node for this mux. If the optimization is
701 * successful, this might be an And or Or node, if not, its the mux
704 static ir_node *optimize_mux_chain(ir_node *mux)
709 ir_mode *mode = get_irn_mode(mux);
714 * If we have no mux, or its mode is not integer, we
717 if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
721 null = get_mode_null(mode);
722 minus_one = tarval_sub(null, get_tarval_one(mode));
724 ops[0] = get_Mux_false(mux);
725 ops[1] = get_Mux_true(mux);
727 for(i = 0; i < 2; ++i) {
729 tarval *tva, *tvb, *tvd;
733 * A mux operand at the first position can be factored
734 * out, if the operands fulfill several conditions:
736 * mux(c1, mux(c2, a, b), d)
738 * This can be made into:
739 * 1) mux(c1, 0, d) | mux(c2, a, b)
740 * if a | d == d and b | d == d
742 * 2) mux(c1, -1, d) & mux(c2, a, b)
743 * if a & d == d and a & b == b
745 if(get_irn_op(ops[i]) == op_Mux) {
748 a = get_Mux_false(child_mux);
749 b = get_Mux_true(child_mux);
752 /* Try the or stuff */
753 tva = get_value_or(a, minus_one);
754 tvb = get_value_or(b, minus_one);
755 tvd = get_value_or(d, null);
757 if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
758 && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
760 ops[i] = new_Const(mode, null);
761 res = new_r_Or(current_ir_graph, get_nodes_block(mux),
762 mux, child_mux, mode);
766 /* If the or didn't go, try the and stuff */
767 tva = get_value_or(a, null);
768 tvb = get_value_or(b, null);
769 tvd = get_value_or(d, minus_one);
771 if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
772 && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
774 ops[i] = new_Const(mode, minus_one);
775 res = new_r_And(current_ir_graph, get_nodes_block(mux),
776 mux, child_mux, mode);
782 /* recursively optimize nested muxes. */
783 set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
784 set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
790 /***********************************************************
791 * The If conversion itself.
792 ***********************************************************/
794 /** allow every Mux to be created. */
795 static int default_allow_mux(ir_node *sel, ir_node *false_res, ir_node *true_res) {
802 static const opt_if_conv_info_t default_info = {
807 /** The debugging module. */
808 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
811 * A simple check for side effects upto an opcode of a ir node.
812 * @param irn The ir node to check,
813 * @return 1 if the opcode itself may produce side effects, 0 if not.
815 static INLINE int has_side_effects(const ir_node *irn)
817 ir_op *op = get_irn_op(irn);
822 return !mode_is_datab(get_irn_mode(irn));
826 * Possible failure reasons
828 enum failure_reason_t {
829 SUCCESS = IF_RESULT_SUCCESS,
830 TO_DEEP = IF_RESULT_TOO_DEEP,
831 SIDE_EFFECTS = IF_RESULT_SIDE_EFFECT,
832 PHI_FOUND = IF_RESULT_SIDE_EFFECT_PHI,
833 DENIED = IF_RESULT_DENIED
837 * Decides, if a given expression and its subexpressions
838 * (to certain, also given extent) can be moved to a block.
840 * @param expr The expression to examine.
841 * @param block The block where the expression should go.
842 * @param depth The current depth, passed recursively. Use 0 for
843 * non-recursive calls.
844 * @param info The options for createing Mux nodes.
847 * @return a failure reason
849 static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, const opt_if_conv_info_t *info)
853 ir_node *expr_block = get_nodes_block(expr);
856 * If we are forced to look too deep into the expression,
857 * treat it like it could not be moved.
859 if(depth >= info->max_depth) {
865 * If the block of the expression dominates the specified
866 * destination block, it does not matter if the expression
867 * has side effects or anything else. It is executed on each
868 * path the destination block is reached.
870 if (block_dominates(expr_block, dest_block))
874 * We cannot move phis!
882 * This should be superfluous and could be converted into a assertion.
883 * The destination block _must_ dominate the block of the expression,
884 * else the expression could be used without its definition.
886 if (! block_dominates(dest_block, expr_block)) {
887 res = IF_RESULT_SIDE_EFFECT;
892 * Surely, if the expression does not have a data mode, it is not
893 * movable. Perhaps one should also test the floating property of
896 if (has_side_effects(expr)) {
897 res = IF_RESULT_SIDE_EFFECT;
902 * If the node looks alright so far, look at its operands and
903 * check them out. If one of them cannot be moved, this one
904 * cannot be moved either.
906 for (i = 0, n = get_irn_arity(expr); i < n; ++i) {
907 ir_node *op = get_irn_n(expr, i);
908 int new_depth = is_Proj(op) ? depth : depth + 1;
910 res = _can_move_to(op, dest_block, new_depth, info);
917 DBG((dbg, LEVEL_3, "\t\t\tcan move to %n: %d\n", expr, res));
923 * Convenience function for _can_move_to.
924 * Checks, if an expression can be moved to another block. The check can
925 * be limited to a expression depth meaning if we need to crawl in
926 * deeper into an expression than a given threshold to examine if
927 * it can be moved, the expression is rejected and the test returns
930 * @param expr The expression to check for.
931 * @param dest_block The destination block you want @p expr to be.
932 * @param info The options for createing Mux nodes.
934 * @return return a failure reason
936 static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, const opt_if_conv_info_t *info)
938 return _can_move_to(expr, dest_block, 0, info);
942 * move a DAG given by a root node expr into a new block
944 * @param expr the root of a dag
945 * @param dest_block the destination block
947 static void move_to(ir_node *expr, ir_node *dest_block)
950 ir_node *expr_block = get_nodes_block(expr);
953 * If we reached the dominator, we are done.
954 * We will never put code through the dominator
956 if (block_dominates(expr_block, dest_block))
959 for (i = 0, n = get_irn_arity(expr); i < n; ++i)
960 move_to(get_irn_n(expr, i), dest_block);
962 set_nodes_block(expr, dest_block);
966 * return the common dominator of two blocks
968 static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2)
970 if(block_dominates(b1, b2))
972 else if(block_dominates(b2, b1))
977 for (p = get_Block_idom(b1); !block_dominates(p, b2); p = get_Block_idom(p));
983 * Information about a cond node.
985 typedef struct _cond_t {
986 ir_node *cond; /**< The cond node. */
987 struct list_head list; /**< List head which is used for queuing this cond
988 into the cond bunch it belongs to. */
990 unsigned totally_covers : 1;
991 struct _cond_t *link;
995 * Information about the both 'branches'
996 * (true and false), the cond creates.
999 int pos; /**< Number of the predecessor of the
1000 phi block by which this branch is
1001 reached. It is -1, if this branch is
1002 only reached through another cond. */
1004 struct _cond_t *masked_by; /**< If this cond's branch is only reached
1005 through another cond, we store this
1006 cond ir_node here. */
1011 * retrieve the conditional information from a Cond node
1013 static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
1018 return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
1022 typedef void (cond_walker_t)(cond_t *cond, void *env);
1024 static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
1025 long visited_nr, void *env)
1029 if(cond->visited_nr >= visited_nr)
1032 cond->visited_nr = visited_nr;
1037 for(i = 0; i < 2; ++i) {
1038 cond_t *c = cond->cases[i].masked_by;
1041 _walk_conds(c, pre, post, visited_nr, env);
1048 static long cond_visited_nr = 0;
1050 static void walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post, void *env)
1052 _walk_conds(cond, pre, post, ++cond_visited_nr, env);
1055 static void link_conds(cond_t *cond, void *env)
1057 cond_t **ptr = (cond_t **) env;
1064 * Compare two conds for use in a firm set.
1065 * Two cond_t's are equal, if they designate the same cond node.
1066 * @param a A cond_t.
1067 * @param b Another one.
1068 * @param size Not used.
1069 * @return 0 (!) if they are equal, != 0 otherwise.
1071 static int cond_cmp(const void *a, const void *b, size_t size)
1073 const cond_t *x = a;
1074 const cond_t *y = b;
1075 return x->cond != y->cond;
1079 * Information about conds which can be made to muxes.
1080 * Instances of this struct are attached to the link field of
1081 * blocks in which phis are located.
1083 typedef struct _cond_info_t {
1084 struct list_head list; /**< Used to list all of these structs per class. */
1086 struct list_head roots; /**< A list of non-depending Conds. Two Conds are
1087 independent, if it's not possible not reach one from the
1088 other (all Conds in this list have to dominate the
1089 block this struct is attached to). */
1091 ir_node *first_phi; /**< The first phi node this cond info was made for. */
1092 set *cond_set; /**< A set of all dominating reachable Conds. */
1098 static void _find_conds(ir_node *irn, unsigned long visited_nr,
1099 ir_node *dominator, cond_t *masked_by, int pos, int depth, cond_info_t *ci)
1102 int saw_select_cond = 0;
1104 block = get_nodes_block(irn);
1107 * Only check this block if it is dominated by the specified
1108 * dominator or it has not been visited yet.
1110 if (block_dominates(dominator, block) && get_Block_block_visited(block) < visited_nr) {
1111 cond_t *res = masked_by;
1114 /* check, if we're on a ProjX
1116 * Further, the ProjX/Cond block must dominate the base block
1117 * (the block with the phi in it), otherwise, the Cond
1118 * is not affecting the phi so that a mux can be inserted.
1120 if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
1122 int proj = get_Proj_proj(irn);
1123 ir_node *cond = get_Proj_pred(irn);
1125 /* true, if the mode is a mode_b cond _NO_ switch cond */
1126 int is_modeb_cond = get_irn_opcode(cond) == iro_Cond
1127 && get_irn_mode(get_Cond_selector(cond)) == mode_b;
1129 saw_select_cond = !is_modeb_cond;
1131 /* Check, if the pred of the proj is a Cond
1132 * with a Projb as selector.
1137 memset(&c, 0, sizeof(c));
1140 c.cases[0].pos = -1;
1141 c.cases[1].pos = -1;
1143 /* get or insert the cond info into the set. */
1144 res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
1147 * If this cond is already masked by the masked_by cond
1148 * return immediately, since we don't have anything to add.
1150 if(masked_by && res->cases[proj].masked_by == masked_by)
1155 list_add(&res->list, &ci->roots);
1159 * Set masked by (either NULL or another cond node.
1160 * If this cond is truly masked by another one, set
1161 * the position of the actually investigated branch
1162 * to -1. Since the cond is masked by another one,
1163 * there could be more ways from the start block
1164 * to this branch, so we choose -1.
1166 res->cases[proj].masked_by = masked_by;
1169 res->cases[proj].pos = pos;
1172 * Since the masked_by nodes masks a cond, remove it from the
1173 * root list of the conf trees.
1176 assert(res->cases[proj].pos < 0);
1177 list_del_init(&masked_by->list);
1180 DBG((dbg, LEVEL_2, "%n (%s branch) "
1181 "for pos %d in block %n reached by %n\n",
1182 cond, proj ? "true" : "false", pos,
1183 block, masked_by ? masked_by->cond : NULL));
1187 if(get_Block_block_visited(block) < visited_nr && !saw_select_cond) {
1189 set_Block_block_visited(block, visited_nr);
1191 /* Search recursively from this cond. */
1192 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1193 ir_node *pred = get_irn_n(block, i);
1196 * If the depth is 0 (the first recursion), we set the pos to
1197 * the current viewed predecessor, else we adopt the position
1198 * as given by the caller. We also increase the depth for the
1199 * recursively called functions.
1201 _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci);
1209 * A convenience function for _find_conds.
1210 * It sets some parameters needed for recursion to appropriate start
1211 * values. Always use this function.
1213 * @param irn The node to start looking for Conds from. This might
1214 * be the phi node we are investigating.
1215 * @param conds The set to record the found Conds in.
1217 static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
1220 unsigned long visited_nr;
1221 ir_node *block = get_nodes_block(irn);
1222 ir_node *dom = get_Block_idom(block);
1224 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1225 ir_node *pred = get_irn_n(block, i);
1227 inc_irg_block_visited(current_ir_graph);
1228 visited_nr = get_irg_block_visited(current_ir_graph);
1229 set_Block_block_visited(block, visited_nr);
1231 DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
1232 _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
1237 * Make the mux for a given cond.
1239 * @param phi The phi node which shall be replaced by a mux.
1240 * @param dom The block where the muxes shall be placed.
1241 * @param cond The cond information.
1242 * @param info The options for createing Mux nodes.
1243 * @return The mux node made for this cond.
1245 static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond,
1246 const opt_if_conv_info_t *info, ir_node **mux, bitset_t *positions,
1247 int *muxes_made, long visited_nr)
1250 ir_node *projb = get_Cond_selector(cond->cond);
1251 ir_node *bl = get_nodes_block(cond->cond);
1252 ir_node *operands[2];
1255 cond->visited_nr = visited_nr;
1256 DBG((dbg, LEVEL_2, "%n\n", cond->cond));
1257 for(i = 0; i < 2; ++i) {
1258 cond_t *masked_by = cond->cases[i].masked_by;
1259 int pos = cond->cases[i].pos;
1265 * If this Cond branch is masked by another cond, make the mux
1266 * for that Cond first, since the Mux for this cond takes
1271 DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
1272 if(masked_by->visited_nr < visited_nr)
1273 operands[i] = make_mux_on_demand(phi, dom, masked_by, info, mux, positions, muxes_made, visited_nr);
1277 * If this cond branch is not masked by another cond, take
1278 * the corresponding phi operand as an operand to the mux.
1281 operands[i] = get_irn_n(phi, pos);
1287 * Move the operands to the dominator block if the cond
1288 * made sense. Some Conds found are not suitable for making a mux
1289 * out of them, since one of their branches cannot be reached from
1290 * the phi block. In that case we do not make a mux and return NULL.
1292 if(operands[0] && operands[1]) {
1293 if (operands[0] == operands[1]) {
1294 /* there is no gain in using mux in this case, as
1295 it will be optimized away. We will NOT move the
1296 content of the blocks either
1298 for (i = 0; i < 2; ++i)
1300 bitset_set(positions, set[i]);
1306 can_move[0] = can_move_to(operands[0], bl, info);
1307 can_move[1] = can_move_to(operands[1], bl, info);
1309 if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) {
1310 if (info->allow_mux(projb, operands[0], operands[1])) {
1311 move_to(operands[0], bl);
1312 move_to(operands[1], bl);
1315 *mux = new_r_Mux(current_ir_graph, bl, projb,
1316 operands[0], operands[1], get_irn_mode(operands[0]));
1320 DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
1321 *mux, projb, operands[0], operands[1], set[0], set[1]));
1323 for(i = 0; i < 2; ++i)
1325 bitset_set(positions, set[i]);
1327 /* we have done one */
1328 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_SUCCESS);
1332 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_DENIED);
1336 if(can_move[0] != SUCCESS)
1337 hook_if_conversion(current_ir_graph, phi, set[0], NULL, can_move[0]);
1338 if(can_move[1] != SUCCESS)
1339 hook_if_conversion(current_ir_graph, phi, set[1], NULL, can_move[1]);
1344 hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF);
1346 hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF);
1352 typedef struct _phi_info_t {
1353 struct list_head list;
1354 cond_info_t *cond_info;
1360 * Examine a phi node if it can be replaced by some muxes.
1361 * @param irn A phi node.
1362 * @param info Parameters for the if conversion algorithm.
1364 static int check_out_phi(phi_info_t *phi_info, const opt_if_conv_info_t *info)
1366 ir_node *irn = phi_info->irn;
1367 ir_node *block, *nw;
1368 cond_info_t *cond_info = phi_info->cond_info;
1372 bitset_t *positions;
1374 block = get_nodes_block(irn);
1375 arity = get_irn_arity(irn);
1376 positions = bitset_alloca(arity);
1378 assert(is_Phi(irn));
1379 assert(get_irn_arity(irn) == get_irn_arity(block));
1382 DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
1384 list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
1385 ir_node *cidom = block;
1386 ir_node *mux = NULL;
1387 cond_t *p, *head = NULL;
1390 bitset_clear_all(positions);
1392 DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
1394 * Link all conds which are in the subtree of
1395 * the current cond in the list together.
1397 walk_conds(cond, link_conds, NULL, &head);
1400 for(p = head; p; p = p->link) {
1401 for(i = 0; i < 2; ++i) {
1402 int pos = p->cases[i].pos;
1404 cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
1408 DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
1409 make_mux_on_demand(irn, cidom, cond, info, &mux, positions, &muxes_made, ++cond_visited_nr);
1412 bitset_foreach(positions, pos)
1413 set_irn_n(irn, (int) pos, mux);
1418 * optimize the phi away. This can anable further runs of this
1419 * function. Look at _can_move. phis cannot be moved there.
1421 nw = optimize_in_place_2(irn);
1428 typedef struct _cond_walk_info_t {
1429 struct obstack *obst;
1430 struct list_head cond_info_head;
1431 struct list_head phi_head;
1435 static void annotate_cond_info_pre(ir_node *irn, void *data)
1437 set_irn_link(irn, NULL);
1440 static void annotate_cond_info_post(ir_node *irn, void *data)
1442 cond_walk_info_t *cwi = data;
1445 * Check, if the node is a phi
1446 * we then compute a set of conds which are reachable from this
1447 * phi's block up to its dominator.
1448 * The set is attached to the blocks link field.
1450 if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
1451 ir_node *block = get_nodes_block(irn);
1453 cond_info_t *ci = get_irn_link(block);
1455 /* If the set is not yet computed, do it now. */
1457 ci = obstack_alloc(cwi->obst, sizeof(*ci));
1458 ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
1459 ci->first_phi = irn;
1461 INIT_LIST_HEAD(&ci->roots);
1462 INIT_LIST_HEAD(&ci->list);
1465 * Add this cond info to the list of all cond infos
1466 * in this graph. This is just done to xfree the
1467 * set easier afterwards (we save an irg_walk_graph).
1469 list_add(&cwi->cond_info_head, &ci->list);
1471 DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
1474 * Fill the set with conds we find on the way from
1475 * the block to its dominator.
1477 find_conds(irn, ci);
1480 * If there where no suitable conds, delete the set
1481 * immediately and reset the set pointer to NULL
1483 if(set_count(ci->cond_set) == 0) {
1484 del_set(ci->cond_set);
1485 list_del(&ci->list);
1486 obstack_free(cwi->obst, ci);
1492 DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
1494 set_irn_link(block, ci);
1497 phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
1500 INIT_LIST_HEAD(&pi->list);
1501 list_add(&pi->list, &cwi->phi_head);
1507 static void dump_conds(cond_t *cond, void *env)
1512 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
1513 cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
1514 get_nodes_block(cond->cond));
1516 for(i = 0; i < 2; ++i)
1517 if(cond->cases[i].masked_by)
1518 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
1519 cond, cond->cases[i].masked_by, i);
1522 static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi)
1527 snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
1529 if((f = fopen(buf, "wt")) != NULL) {
1534 ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
1535 list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
1536 ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
1537 list_for_each_entry(cond_t, cond, &ci->roots, list) {
1538 walk_conds(cond, NULL, dump_conds, f);
1539 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
1543 list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
1544 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
1545 phi->irn, phi->irn, get_nodes_block(phi->irn));
1546 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
1552 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
1555 struct obstack obst;
1556 phi_info_t *phi_info;
1557 cond_info_t *cond_info;
1558 cond_walk_info_t cwi;
1560 opt_if_conv_info_t p;
1562 if(!get_opt_if_conversion())
1565 /* get the parameters */
1567 memcpy(&p, params, sizeof(p));
1569 memcpy(&p, &default_info, sizeof(p));
1572 p.allow_mux = default_info.allow_mux;
1574 obstack_init(&obst);
1577 INIT_LIST_HEAD(&cwi.cond_info_head);
1578 INIT_LIST_HEAD(&cwi.phi_head);
1580 /* Init the debug stuff. */
1581 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
1583 firm_dbg_set_mask(dbg, LEVEL_1|LEVEL_2|LEVEL_3);
1586 /* if-conversion works better with normalized returns */
1587 normalize_one_return(irg);
1589 /* Ensure, that the dominators are computed. */
1592 DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
1593 get_entity_name(get_irg_entity(irg)), irg));
1596 * Collect information about the conds pu the phis on an obstack.
1597 * It is important that phi nodes which are 'higher' (with a
1598 * lower dfs pre order) are in front of the obstack. Since they are
1599 * possibly turned in to muxes this can enable the optimization
1602 irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
1605 vcg_dump_conds(irg, &cwi);
1608 /* Process each suitable phi found. */
1609 list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
1610 DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
1611 muxes_made += check_out_phi(phi_info, &p);
1614 list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
1615 del_set(cond_info->cond_set);
1618 DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
1620 obstack_free(&obst, NULL);