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.
32 static ir_node* walk_to_projx(ir_node* start)
36 pred = get_nodes_block(start);
38 /* if there are multiple control flow predecessors nothing sensible can be
40 if (get_irn_arity(pred) > 1) return NULL;
42 pred = get_irn_n(pred, 0);
43 if (get_irn_op(pred) == op_Proj) {
44 assert(get_irn_mode(pred) == mode_X);
52 typedef struct block_info {
57 #define get_block_blockinfo(block) ((block_info*)get_irn_link(block))
59 static int can_empty_block(ir_node* block)
61 return !get_block_blockinfo(block)->evil;
66 * Copies the DAG starting at node to the ith predecessor block of src_block
67 * -if the node isn't in the src_block, this is a nop and the node is returned
68 * -if the node is a phi in the src_block, the ith predecessor of the phi is
70 * otherwise returns the copy of the passed node
72 static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
79 if (get_nodes_block(node) != src_block) return node;
80 if (get_irn_op(node) == op_Phi) return get_irn_n(node, i);
82 copy_irn_to_irg(node, current_ir_graph);
83 copy = get_irn_link(node);
84 dst_block = get_nodes_block(get_irn_n(src_block, i));
85 set_nodes_block(copy, dst_block);
87 ir_fprintf(stderr, "Copying node %+F to block %+F, copy is %+F\n",
91 arity = get_irn_arity(node);
92 for (j = 0; j < arity; ++j) {
93 set_irn_n(copy, j, copy_to(get_irn_n(node, j), src_block, i));
94 ir_fprintf(stderr, "-- pred %d is %+F\n", j, get_irn_n(copy, j));
101 * Duplicate and move the contents of ith block predecessor into its
102 * predecessors if the block has multiple control dependencies and only one
104 * Also bail out if the block contains non-movable nodes, because later
105 * if-conversion would be pointless.
107 static int fission_block(ir_node* block, int i)
109 ir_node* pred = get_irn_n(block, i);
118 if (get_irn_op(pred) != op_Jmp) return 0;
119 pred_block = get_nodes_block(pred);
121 if (!has_multiple_cdep(pred_block)) return 0;
122 if (!can_empty_block(pred_block)) return 0;
124 ir_fprintf(stderr, "Fissioning block %+F\n", pred_block);
126 pred_arity = get_irn_arity(pred_block);
127 arity = get_irn_arity(block);
128 info = get_irn_link(block);
129 ins = xmalloc(sizeof(*ins) * (arity + pred_arity - 1));
130 for (phi = info->phi; phi != NULL; phi = get_irn_link(phi)) {
131 for (j = 0; j < i; ++j) ins[j] = get_irn_n(phi, j);
132 for (j = 0; j < pred_arity; ++j) {
133 ins[i + j] = copy_to(get_irn_n(phi, i), pred_block, j);
135 for (j = i + 1; j < arity; ++j) {
136 ins[pred_arity - 1 + j] = get_irn_n(phi, j);
138 set_irn_in(phi, arity + pred_arity - 1, ins);
140 for (j = 0; j < i; ++j) ins[j] = get_irn_n(block, j);
141 for (j = 0; j < pred_arity; ++j) ins[i + j] = get_irn_n(pred_block, j);
142 for (j = i + 1; j < arity; ++j) ins[pred_arity - 1 + j] = get_irn_n(block, j);
143 set_irn_in(block, arity + pred_arity - 1, ins);
146 /* Kill all Phis in the fissioned block
147 * This is to make sure they're not kept alive
149 info = get_irn_link(pred_block);
151 while (phi != NULL) {
152 ir_node* next = get_irn_link(phi);
153 exchange(phi, new_Bad());
161 * Remove predecessors i and j from node and add predecessor new_pred
163 static void rewire(ir_node* node, int i, int j, ir_node* new_pred)
165 int arity = get_irn_arity(node);
166 ir_node** ins = xmalloc(sizeof(*ins) * (arity - 1));
171 for (k = 0; k < i; ++k) ins[l++] = get_irn_n(node, k);
172 for (++k; k < j; ++k) ins[l++] = get_irn_n(node, k);
173 for (++k; k < arity; ++k) ins[l++] = get_irn_n(node, k);
175 assert(l == arity - 1);
176 set_irn_in(node, l, ins);
182 static void if_conv_walker(ir_node* block, void* env)
188 // Bail out, if there are no Phis at all
189 if (get_block_blockinfo(block)->phi == NULL) return;
192 arity = get_irn_arity(block);
193 for (i = 0; i < arity; ++i) {
194 if (fission_block(block, i)) goto restart;
198 arity = get_irn_arity(block);
199 for (i = 0; i < arity; ++i) {
205 projx0 = walk_to_projx(get_irn_n(block, i));
206 if (projx0 == NULL) return;
207 pred = get_Proj_pred(projx0);
208 if (get_irn_op(pred) != op_Cond || get_irn_mode(get_Cond_selector(pred)) != mode_b) continue;
211 if (!can_empty_block(get_nodes_block(get_irn_n(block, i)))) {
212 ir_fprintf(stderr, "Cannot empty block %+F\n",
213 get_nodes_block(get_irn_n(block, i))
218 for (j = i + 1; j < arity; ++j) {
225 projx1 = walk_to_projx(get_irn_n(block, j));
226 if (projx1 == NULL) continue;
227 pred = get_Proj_pred(projx1);
228 if (get_irn_op(pred) != op_Cond || get_irn_mode(get_Cond_selector(pred)) != mode_b) continue;
229 if (pred != cond) continue;
230 ir_fprintf(stderr, "Found Cond %+F with proj %+F and %+F\n", cond, projx0, projx1);
232 if (!can_empty_block(get_nodes_block(get_irn_n(block, j)))) {
233 ir_fprintf(stderr, "Cannot empty block %+F\n",
234 get_nodes_block(get_irn_n(block, j))
239 conds[0] = get_Cond_selector(cond);
241 psi_block = get_nodes_block(cond);
242 phi = get_block_blockinfo(block)->phi;
244 // Don't generate PsiMs
245 if (get_irn_mode(phi) == mode_M) {
246 /* Something is very fishy if to predecessors of a PhiM point into the
247 * block but not at the same memory node
249 assert(get_irn_n(phi, i) == get_irn_n(phi, j));
251 psi = get_irn_n(phi, i);
252 ir_fprintf(stderr, "Handling memory Phi %+F\n", phi);
254 ir_node* val_i = get_irn_n(phi, i);
255 ir_node* val_j = get_irn_n(phi, j);
257 if (val_i == val_j) {
259 ir_fprintf(stderr, "Generating no psi, because both values are equal\n");
261 if (get_Proj_proj(projx0) == pn_Cond_true) {
269 current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
271 ir_fprintf(stderr, "Generating %+F for %+F\n", psi, phi);
278 rewire(phi, i, j, psi);
281 phi = get_irn_link(phi);
282 } while (phi != NULL);
284 exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
285 exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
288 ir_fprintf(stderr, "Welding block %+F to %+F\n", block, psi_block);
289 get_block_blockinfo(psi_block)->evil |= get_block_blockinfo(block)->evil;
290 exchange(block, psi_block);
293 rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block));
301 static void init_block_link(ir_node* block, void* env)
303 block_info* bi = xmalloc(sizeof(*bi));
307 set_irn_link(block, bi);
311 /* Daisy-chain all phis in a block
312 * If a non-movable node is encountered set the evil flag
314 static void collect_phis(ir_node* node, void* env)
319 if (get_irn_op(node) == op_Block) return;
321 block = get_nodes_block(node);
322 bi = get_irn_link(block);
324 if (get_irn_op(node) == op_Phi) {
325 set_irn_link(node, bi->phi);
329 if (get_irn_op(node) == op_Call ||
330 get_irn_op(node) == op_Store ||
331 get_irn_op(node) == op_Load) {
332 ir_fprintf(stderr, "Node %+F in block %+F is unmovable\n", node, block);
336 if (get_irn_op(node) != op_Jmp &&
337 get_irn_op(node) != op_Proj &&
338 get_irn_op(node) != op_Cond &&
339 get_irn_op(node) != op_Cmp &&
340 !mode_is_datab(get_irn_mode(node))) {
341 ir_fprintf(stderr, "Node %+F in block %+F is unmovable\n", node, block);
350 * Transform multiple cascaded Psis into one Psi
352 static ir_node* fold_psi(ir_node* psi)
354 int arity = get_Psi_n_conds(psi);
365 for (i = 0; i < arity; ++i) {
366 n = get_Psi_val(psi, i);
367 if (get_irn_op(n) == op_Psi) {
368 new_arity += get_Psi_n_conds(n) + 1;
373 n = get_Psi_default(psi);
374 if (get_irn_op(n) == op_Psi) {
375 new_arity += get_Psi_n_conds(n);
378 if (arity == new_arity) return psi; // no attached Psis found
379 ir_fprintf(stderr, "Folding %+F from %d to %d conds\n", psi, arity, new_arity);
381 conds = xmalloc(new_arity * sizeof(*conds));
382 vals = xmalloc((new_arity + 1) * sizeof(*vals));
384 for (i = 0; i < arity; ++i) {
385 ir_node* c = get_Psi_cond(psi, i);
387 n = get_Psi_val(psi, i);
388 if (get_irn_op(n) == op_Psi) {
389 a = get_Psi_n_conds(n);
390 for (k = 0; k < a; ++k) {
391 conds[j] = new_r_And(
392 current_ir_graph, get_nodes_block(psi),
393 c, get_Psi_cond(n, k), mode_b
395 vals[j] = get_Psi_val(n, k);
399 vals[j] = get_Psi_default(n);
406 n = get_Psi_default(psi);
407 if (get_irn_op(n) == op_Psi) {
408 a = get_Psi_n_conds(n);
409 for (k = 0; k < a; ++k) {
410 conds[j] = get_Psi_cond(n, k);
411 vals[j] = get_Psi_val(n, k);
414 vals[j] = get_Psi_default(n);
418 assert(j == new_arity);
420 current_ir_graph, get_nodes_block(psi),
421 new_arity, conds, vals, get_irn_mode(psi)
423 ir_fprintf(stderr, "Folded %+F into new %+F\n", psi, new_psi);
424 exchange(psi, new_psi);
432 * Merge consecutive psi inputs if the data inputs are the same
434 static void meld_psi(ir_node* psi)
436 int arity = get_Psi_n_conds(psi);
447 val = get_Psi_val(psi, 0);
448 ir_fprintf(stderr, "Pred 0 of %+F is %+F\n", psi, val);
449 for (i = 1; i < arity; ++i) {
450 ir_node* v = get_Psi_val(psi, i);
451 ir_fprintf(stderr, "Pred %2d of %+F is %+F\n", i, psi, v);
457 ir_fprintf(stderr, "Default of %+F is %+F\n", psi, get_Psi_default(psi));
458 if (val == get_Psi_default(psi)) --new_arity;
460 ir_fprintf(stderr, "Melding Psi %+F from %d conds to %d\n",
461 psi, arity, new_arity
464 if (new_arity == arity) return;
466 // If all data inputs of the Psi are equal, exchange the Psi with that value
467 if (new_arity == 0) {
472 conds = xmalloc(sizeof(*conds) * new_arity);
473 vals = xmalloc(sizeof(*vals) * (new_arity + 1));
474 cond = get_Psi_cond(psi, 0);
475 val = get_Psi_val(psi, 0);
477 for (i = 1; i < arity; ++i) {
478 ir_node* v = get_Psi_val(psi, i);
482 current_ir_graph, get_nodes_block(psi),
483 cond, get_Psi_cond(psi, i), mode_b
492 if (val != get_Psi_default(psi)) {
497 vals[j] = get_Psi_default(psi);
498 assert(j == new_arity);
500 current_ir_graph, get_nodes_block(psi),
501 new_arity, conds, vals, get_irn_mode(psi)
503 ir_fprintf(stderr, "Molded %+F into %+F\n", psi, new_psi);
504 exchange(psi, new_psi);
508 static void optimise_psis(ir_node* node, void* env)
510 if (get_irn_op(node) != op_Psi) return;
512 node = fold_psi(node);
520 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
522 ir_fprintf(stderr, "Running if-conversion on %+F\n", irg);
524 dump_ir_block_graph(irg, "_00_pre");
526 normalize_one_return(irg);
527 remove_critical_cf_edges(irg);
529 dump_ir_block_graph(irg, "_01_normal");
534 irg_block_walk_graph(irg, init_block_link, NULL, NULL);
535 irg_walk_graph(irg, collect_phis, NULL, NULL);
536 irg_block_walk_graph(irg, NULL, if_conv_walker, NULL);
538 local_optimize_graph(irg);
539 dump_ir_block_graph(irg, "_02_ifconv");
541 irg_walk_graph(irg, NULL, optimise_psis, NULL);
543 dump_ir_block_graph(irg, "_03_postifconv");
554 * Make Mux nodes from Conds where it its possible.
555 * @author Sebastian Hack
571 #ifdef HAVE_xmalloc_H
575 #include "irgraph_t.h"
576 #include "irnode_t.h"
580 #include "irmode_t.h"
581 #include "ircons_t.h"
586 #include "irflag_t.h"
588 #include "irprintf.h"
593 #include "bitfiddle.h"
600 * check, if a node is const and return its tarval or
601 * return a default tarval.
602 * @param cnst The node whose tarval to get.
603 * @param or The alternative tarval, if the node is no Const.
604 * @return The tarval of @p cnst, if the node is Const, @p otherwise.
606 static tarval *get_value_or(ir_node *cnst, tarval *or)
608 return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
613 * Try to optimize nested muxes into a dis- or conjunction
615 * @param mux The parent mux, which has muxes as operands.
616 * @return The replacement node for this mux. If the optimization is
617 * successful, this might be an And or Or node, if not, its the mux
620 static ir_node *optimize_mux_chain(ir_node *mux)
625 ir_mode *mode = get_irn_mode(mux);
630 * If we have no mux, or its mode is not integer, we
633 if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
637 null = get_mode_null(mode);
638 minus_one = tarval_sub(null, get_tarval_one(mode));
640 ops[0] = get_Mux_false(mux);
641 ops[1] = get_Mux_true(mux);
643 for(i = 0; i < 2; ++i) {
645 tarval *tva, *tvb, *tvd;
649 * A mux operand at the first position can be factored
650 * out, if the operands fulfill several conditions:
652 * mux(c1, mux(c2, a, b), d)
654 * This can be made into:
655 * 1) mux(c1, 0, d) | mux(c2, a, b)
656 * if a | d == d and b | d == d
658 * 2) mux(c1, -1, d) & mux(c2, a, b)
659 * if a & d == d and a & b == b
661 if(get_irn_op(ops[i]) == op_Mux) {
664 a = get_Mux_false(child_mux);
665 b = get_Mux_true(child_mux);
668 /* Try the or stuff */
669 tva = get_value_or(a, minus_one);
670 tvb = get_value_or(b, minus_one);
671 tvd = get_value_or(d, null);
673 if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
674 && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
676 ops[i] = new_Const(mode, null);
677 res = new_r_Or(current_ir_graph, get_nodes_block(mux),
678 mux, child_mux, mode);
682 /* If the or didn't go, try the and stuff */
683 tva = get_value_or(a, null);
684 tvb = get_value_or(b, null);
685 tvd = get_value_or(d, minus_one);
687 if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
688 && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
690 ops[i] = new_Const(mode, minus_one);
691 res = new_r_And(current_ir_graph, get_nodes_block(mux),
692 mux, child_mux, mode);
698 /* recursively optimize nested muxes. */
699 set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
700 set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
706 /***********************************************************
707 * The If conversion itself.
708 ***********************************************************/
710 /** allow every Mux to be created. */
711 static int default_allow_mux(ir_node *sel, ir_node *false_res, ir_node *true_res) {
718 static const opt_if_conv_info_t default_info = {
723 /** The debugging module. */
724 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
727 * A simple check for side effects upto an opcode of a ir node.
728 * @param irn The ir node to check,
729 * @return 1 if the opcode itself may produce side effects, 0 if not.
731 static INLINE int has_side_effects(const ir_node *irn)
733 ir_op *op = get_irn_op(irn);
738 return !mode_is_datab(get_irn_mode(irn));
742 * Possible failure reasons
744 enum failure_reason_t {
745 SUCCESS = IF_RESULT_SUCCESS,
746 TO_DEEP = IF_RESULT_TOO_DEEP,
747 SIDE_EFFECTS = IF_RESULT_SIDE_EFFECT,
748 PHI_FOUND = IF_RESULT_SIDE_EFFECT_PHI,
749 DENIED = IF_RESULT_DENIED
753 * Decides, if a given expression and its subexpressions
754 * (to certain, also given extent) can be moved to a block.
756 * @param expr The expression to examine.
757 * @param block The block where the expression should go.
758 * @param depth The current depth, passed recursively. Use 0 for
759 * non-recursive calls.
760 * @param info The options for createing Mux nodes.
763 * @return a failure reason
765 static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, const opt_if_conv_info_t *info)
769 ir_node *expr_block = get_nodes_block(expr);
772 * If we are forced to look too deep into the expression,
773 * treat it like it could not be moved.
775 if(depth >= info->max_depth) {
781 * If the block of the expression dominates the specified
782 * destination block, it does not matter if the expression
783 * has side effects or anything else. It is executed on each
784 * path the destination block is reached.
786 if (block_dominates(expr_block, dest_block))
790 * We cannot move phis!
798 * This should be superfluous and could be converted into a assertion.
799 * The destination block _must_ dominate the block of the expression,
800 * else the expression could be used without its definition.
802 if (! block_dominates(dest_block, expr_block)) {
803 res = IF_RESULT_SIDE_EFFECT;
808 * Surely, if the expression does not have a data mode, it is not
809 * movable. Perhaps one should also test the floating property of
812 if (has_side_effects(expr)) {
813 res = IF_RESULT_SIDE_EFFECT;
818 * If the node looks alright so far, look at its operands and
819 * check them out. If one of them cannot be moved, this one
820 * cannot be moved either.
822 for (i = 0, n = get_irn_arity(expr); i < n; ++i) {
823 ir_node *op = get_irn_n(expr, i);
824 int new_depth = is_Proj(op) ? depth : depth + 1;
826 res = _can_move_to(op, dest_block, new_depth, info);
833 DBG((dbg, LEVEL_3, "\t\t\tcan move to %n: %d\n", expr, res));
839 * Convenience function for _can_move_to.
840 * Checks, if an expression can be moved to another block. The check can
841 * be limited to a expression depth meaning if we need to crawl in
842 * deeper into an expression than a given threshold to examine if
843 * it can be moved, the expression is rejected and the test returns
846 * @param expr The expression to check for.
847 * @param dest_block The destination block you want @p expr to be.
848 * @param info The options for createing Mux nodes.
850 * @return return a failure reason
852 static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, const opt_if_conv_info_t *info)
854 return _can_move_to(expr, dest_block, 0, info);
858 * move a DAG given by a root node expr into a new block
860 * @param expr the root of a dag
861 * @param dest_block the destination block
863 static void move_to(ir_node *expr, ir_node *dest_block)
866 ir_node *expr_block = get_nodes_block(expr);
869 * If we reached the dominator, we are done.
870 * We will never put code through the dominator
872 if (block_dominates(expr_block, dest_block))
875 for (i = 0, n = get_irn_arity(expr); i < n; ++i)
876 move_to(get_irn_n(expr, i), dest_block);
878 set_nodes_block(expr, dest_block);
882 * return the common dominator of two blocks
884 static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2)
886 if(block_dominates(b1, b2))
888 else if(block_dominates(b2, b1))
893 for (p = get_Block_idom(b1); !block_dominates(p, b2); p = get_Block_idom(p));
899 * Information about a cond node.
901 typedef struct _cond_t {
902 ir_node *cond; /**< The cond node. */
903 struct list_head list; /**< List head which is used for queuing this cond
904 into the cond bunch it belongs to. */
906 unsigned totally_covers : 1;
907 struct _cond_t *link;
911 * Information about the both 'branches'
912 * (true and false), the cond creates.
915 int pos; /**< Number of the predecessor of the
916 phi block by which this branch is
917 reached. It is -1, if this branch is
918 only reached through another cond. */
920 struct _cond_t *masked_by; /**< If this cond's branch is only reached
921 through another cond, we store this
922 cond ir_node here. */
927 * retrieve the conditional information from a Cond node
929 static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
934 return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
938 typedef void (cond_walker_t)(cond_t *cond, void *env);
940 static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
941 long visited_nr, void *env)
945 if(cond->visited_nr >= visited_nr)
948 cond->visited_nr = visited_nr;
953 for(i = 0; i < 2; ++i) {
954 cond_t *c = cond->cases[i].masked_by;
957 _walk_conds(c, pre, post, visited_nr, env);
964 static long cond_visited_nr = 0;
966 static void walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post, void *env)
968 _walk_conds(cond, pre, post, ++cond_visited_nr, env);
971 static void link_conds(cond_t *cond, void *env)
973 cond_t **ptr = (cond_t **) env;
980 * Compare two conds for use in a firm set.
981 * Two cond_t's are equal, if they designate the same cond node.
983 * @param b Another one.
984 * @param size Not used.
985 * @return 0 (!) if they are equal, != 0 otherwise.
987 static int cond_cmp(const void *a, const void *b, size_t size)
991 return x->cond != y->cond;
995 * Information about conds which can be made to muxes.
996 * Instances of this struct are attached to the link field of
997 * blocks in which phis are located.
999 typedef struct _cond_info_t {
1000 struct list_head list; /**< Used to list all of these structs per class. */
1002 struct list_head roots; /**< A list of non-depending Conds. Two Conds are
1003 independent, if it's not possible not reach one from the
1004 other (all Conds in this list have to dominate the
1005 block this struct is attached to). */
1007 ir_node *first_phi; /**< The first phi node this cond info was made for. */
1008 set *cond_set; /**< A set of all dominating reachable Conds. */
1014 static void _find_conds(ir_node *irn, unsigned long visited_nr,
1015 ir_node *dominator, cond_t *masked_by, int pos, int depth, cond_info_t *ci)
1018 int saw_select_cond = 0;
1020 block = get_nodes_block(irn);
1023 * Only check this block if it is dominated by the specified
1024 * dominator or it has not been visited yet.
1026 if (block_dominates(dominator, block) && get_Block_block_visited(block) < visited_nr) {
1027 cond_t *res = masked_by;
1030 /* check, if we're on a ProjX
1032 * Further, the ProjX/Cond block must dominate the base block
1033 * (the block with the phi in it), otherwise, the Cond
1034 * is not affecting the phi so that a mux can be inserted.
1036 if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
1038 int proj = get_Proj_proj(irn);
1039 ir_node *cond = get_Proj_pred(irn);
1041 /* true, if the mode is a mode_b cond _NO_ switch cond */
1042 int is_modeb_cond = get_irn_opcode(cond) == iro_Cond
1043 && get_irn_mode(get_Cond_selector(cond)) == mode_b;
1045 saw_select_cond = !is_modeb_cond;
1047 /* Check, if the pred of the proj is a Cond
1048 * with a Projb as selector.
1053 memset(&c, 0, sizeof(c));
1056 c.cases[0].pos = -1;
1057 c.cases[1].pos = -1;
1059 /* get or insert the cond info into the set. */
1060 res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
1063 * If this cond is already masked by the masked_by cond
1064 * return immediately, since we don't have anything to add.
1066 if(masked_by && res->cases[proj].masked_by == masked_by)
1071 list_add(&res->list, &ci->roots);
1075 * Set masked by (either NULL or another cond node.
1076 * If this cond is truly masked by another one, set
1077 * the position of the actually investigated branch
1078 * to -1. Since the cond is masked by another one,
1079 * there could be more ways from the start block
1080 * to this branch, so we choose -1.
1082 res->cases[proj].masked_by = masked_by;
1085 res->cases[proj].pos = pos;
1088 * Since the masked_by nodes masks a cond, remove it from the
1089 * root list of the conf trees.
1092 assert(res->cases[proj].pos < 0);
1093 list_del_init(&masked_by->list);
1096 DBG((dbg, LEVEL_2, "%n (%s branch) "
1097 "for pos %d in block %n reached by %n\n",
1098 cond, proj ? "true" : "false", pos,
1099 block, masked_by ? masked_by->cond : NULL));
1103 if(get_Block_block_visited(block) < visited_nr && !saw_select_cond) {
1105 set_Block_block_visited(block, visited_nr);
1107 /* Search recursively from this cond. */
1108 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1109 ir_node *pred = get_irn_n(block, i);
1112 * If the depth is 0 (the first recursion), we set the pos to
1113 * the current viewed predecessor, else we adopt the position
1114 * as given by the caller. We also increase the depth for the
1115 * recursively called functions.
1117 _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci);
1125 * A convenience function for _find_conds.
1126 * It sets some parameters needed for recursion to appropriate start
1127 * values. Always use this function.
1129 * @param irn The node to start looking for Conds from. This might
1130 * be the phi node we are investigating.
1131 * @param conds The set to record the found Conds in.
1133 static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
1136 unsigned long visited_nr;
1137 ir_node *block = get_nodes_block(irn);
1138 ir_node *dom = get_Block_idom(block);
1140 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1141 ir_node *pred = get_irn_n(block, i);
1143 inc_irg_block_visited(current_ir_graph);
1144 visited_nr = get_irg_block_visited(current_ir_graph);
1145 set_Block_block_visited(block, visited_nr);
1147 DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
1148 _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
1153 * Make the mux for a given cond.
1155 * @param phi The phi node which shall be replaced by a mux.
1156 * @param dom The block where the muxes shall be placed.
1157 * @param cond The cond information.
1158 * @param info The options for createing Mux nodes.
1159 * @return The mux node made for this cond.
1161 static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond,
1162 const opt_if_conv_info_t *info, ir_node **mux, bitset_t *positions,
1163 int *muxes_made, long visited_nr)
1166 ir_node *projb = get_Cond_selector(cond->cond);
1167 ir_node *bl = get_nodes_block(cond->cond);
1168 ir_node *operands[2];
1171 cond->visited_nr = visited_nr;
1172 DBG((dbg, LEVEL_2, "%n\n", cond->cond));
1173 for(i = 0; i < 2; ++i) {
1174 cond_t *masked_by = cond->cases[i].masked_by;
1175 int pos = cond->cases[i].pos;
1181 * If this Cond branch is masked by another cond, make the mux
1182 * for that Cond first, since the Mux for this cond takes
1187 DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
1188 if(masked_by->visited_nr < visited_nr)
1189 operands[i] = make_mux_on_demand(phi, dom, masked_by, info, mux, positions, muxes_made, visited_nr);
1193 * If this cond branch is not masked by another cond, take
1194 * the corresponding phi operand as an operand to the mux.
1197 operands[i] = get_irn_n(phi, pos);
1203 * Move the operands to the dominator block if the cond
1204 * made sense. Some Conds found are not suitable for making a mux
1205 * out of them, since one of their branches cannot be reached from
1206 * the phi block. In that case we do not make a mux and return NULL.
1208 if(operands[0] && operands[1]) {
1209 if (operands[0] == operands[1]) {
1210 /* there is no gain in using mux in this case, as
1211 it will be optimized away. We will NOT move the
1212 content of the blocks either
1214 for (i = 0; i < 2; ++i)
1216 bitset_set(positions, set[i]);
1222 can_move[0] = can_move_to(operands[0], bl, info);
1223 can_move[1] = can_move_to(operands[1], bl, info);
1225 if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) {
1226 if (info->allow_mux(projb, operands[0], operands[1])) {
1227 move_to(operands[0], bl);
1228 move_to(operands[1], bl);
1231 *mux = new_r_Mux(current_ir_graph, bl, projb,
1232 operands[0], operands[1], get_irn_mode(operands[0]));
1236 DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
1237 *mux, projb, operands[0], operands[1], set[0], set[1]));
1239 for(i = 0; i < 2; ++i)
1241 bitset_set(positions, set[i]);
1243 /* we have done one */
1244 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_SUCCESS);
1248 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_DENIED);
1252 if(can_move[0] != SUCCESS)
1253 hook_if_conversion(current_ir_graph, phi, set[0], NULL, can_move[0]);
1254 if(can_move[1] != SUCCESS)
1255 hook_if_conversion(current_ir_graph, phi, set[1], NULL, can_move[1]);
1260 hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF);
1262 hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF);
1268 typedef struct _phi_info_t {
1269 struct list_head list;
1270 cond_info_t *cond_info;
1276 * Examine a phi node if it can be replaced by some muxes.
1277 * @param irn A phi node.
1278 * @param info Parameters for the if conversion algorithm.
1280 static int check_out_phi(phi_info_t *phi_info, const opt_if_conv_info_t *info)
1282 ir_node *irn = phi_info->irn;
1283 ir_node *block, *nw;
1284 cond_info_t *cond_info = phi_info->cond_info;
1288 bitset_t *positions;
1290 block = get_nodes_block(irn);
1291 arity = get_irn_arity(irn);
1292 positions = bitset_alloca(arity);
1294 assert(is_Phi(irn));
1295 assert(get_irn_arity(irn) == get_irn_arity(block));
1298 DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
1300 list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
1301 ir_node *cidom = block;
1302 ir_node *mux = NULL;
1303 cond_t *p, *head = NULL;
1306 bitset_clear_all(positions);
1308 DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
1310 * Link all conds which are in the subtree of
1311 * the current cond in the list together.
1313 walk_conds(cond, link_conds, NULL, &head);
1316 for(p = head; p; p = p->link) {
1317 for(i = 0; i < 2; ++i) {
1318 int pos = p->cases[i].pos;
1320 cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
1324 DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
1325 make_mux_on_demand(irn, cidom, cond, info, &mux, positions, &muxes_made, ++cond_visited_nr);
1328 bitset_foreach(positions, pos)
1329 set_irn_n(irn, (int) pos, mux);
1334 * optimize the phi away. This can anable further runs of this
1335 * function. Look at _can_move. phis cannot be moved there.
1337 nw = optimize_in_place_2(irn);
1344 typedef struct _cond_walk_info_t {
1345 struct obstack *obst;
1346 struct list_head cond_info_head;
1347 struct list_head phi_head;
1351 static void annotate_cond_info_pre(ir_node *irn, void *data)
1353 set_irn_link(irn, NULL);
1356 static void annotate_cond_info_post(ir_node *irn, void *data)
1358 cond_walk_info_t *cwi = data;
1361 * Check, if the node is a phi
1362 * we then compute a set of conds which are reachable from this
1363 * phi's block up to its dominator.
1364 * The set is attached to the blocks link field.
1366 if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
1367 ir_node *block = get_nodes_block(irn);
1369 cond_info_t *ci = get_irn_link(block);
1371 /* If the set is not yet computed, do it now. */
1373 ci = obstack_alloc(cwi->obst, sizeof(*ci));
1374 ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
1375 ci->first_phi = irn;
1377 INIT_LIST_HEAD(&ci->roots);
1378 INIT_LIST_HEAD(&ci->list);
1381 * Add this cond info to the list of all cond infos
1382 * in this graph. This is just done to xfree the
1383 * set easier afterwards (we save an irg_walk_graph).
1385 list_add(&cwi->cond_info_head, &ci->list);
1387 DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
1390 * Fill the set with conds we find on the way from
1391 * the block to its dominator.
1393 find_conds(irn, ci);
1396 * If there where no suitable conds, delete the set
1397 * immediately and reset the set pointer to NULL
1399 if(set_count(ci->cond_set) == 0) {
1400 del_set(ci->cond_set);
1401 list_del(&ci->list);
1402 obstack_free(cwi->obst, ci);
1408 DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
1410 set_irn_link(block, ci);
1413 phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
1416 INIT_LIST_HEAD(&pi->list);
1417 list_add(&pi->list, &cwi->phi_head);
1423 static void dump_conds(cond_t *cond, void *env)
1428 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
1429 cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
1430 get_nodes_block(cond->cond));
1432 for(i = 0; i < 2; ++i)
1433 if(cond->cases[i].masked_by)
1434 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
1435 cond, cond->cases[i].masked_by, i);
1438 static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi)
1443 snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
1445 if((f = fopen(buf, "wt")) != NULL) {
1450 ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
1451 list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
1452 ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
1453 list_for_each_entry(cond_t, cond, &ci->roots, list) {
1454 walk_conds(cond, NULL, dump_conds, f);
1455 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
1459 list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
1460 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
1461 phi->irn, phi->irn, get_nodes_block(phi->irn));
1462 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
1468 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
1471 struct obstack obst;
1472 phi_info_t *phi_info;
1473 cond_info_t *cond_info;
1474 cond_walk_info_t cwi;
1476 opt_if_conv_info_t p;
1478 if(!get_opt_if_conversion())
1481 /* get the parameters */
1483 memcpy(&p, params, sizeof(p));
1485 memcpy(&p, &default_info, sizeof(p));
1488 p.allow_mux = default_info.allow_mux;
1490 obstack_init(&obst);
1493 INIT_LIST_HEAD(&cwi.cond_info_head);
1494 INIT_LIST_HEAD(&cwi.phi_head);
1496 /* Init the debug stuff. */
1497 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
1499 firm_dbg_set_mask(dbg, LEVEL_1|LEVEL_2|LEVEL_3);
1502 /* if-conversion works better with normalized returns */
1503 normalize_one_return(irg);
1505 /* Ensure, that the dominators are computed. */
1508 DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
1509 get_entity_name(get_irg_entity(irg)), irg));
1512 * Collect information about the conds pu the phis on an obstack.
1513 * It is important that phi nodes which are 'higher' (with a
1514 * lower dfs pre order) are in front of the obstack. Since they are
1515 * possibly turned in to muxes this can enable the optimization
1518 irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
1521 vcg_dump_conds(irg, &cwi);
1524 /* Process each suitable phi found. */
1525 list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
1526 DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
1527 muxes_made += check_out_phi(phi_info, &p);
1530 list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
1531 del_set(cond_info->cond_set);
1534 DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
1536 obstack_free(&obst, NULL);
1538 dump_ir_block_graph(irg, "_ifconv_hack");