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)
37 pred = get_nodes_block(start);
38 cdep = get_unique_cdep(pred);
39 if (cdep == NULL) return NULL;
41 assert(get_irn_arity(pred) == 1);
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());
160 static void if_conv_walker(ir_node* block, void* env)
166 // Bail out, if there are no Phis at all
167 if (get_block_blockinfo(block)->phi == NULL) return;
170 arity = get_irn_arity(block);
171 for (i = 0; i < arity; ++i) {
172 if (fission_block(block, i)) goto restart;
176 arity = get_irn_arity(block);
177 for (i = 0; i < arity; ++i) {
183 projx0 = walk_to_projx(get_irn_n(block, i));
184 if (projx0 == NULL) return;
185 pred = get_Proj_pred(projx0);
186 if (get_irn_op(pred) != op_Cond || get_irn_mode(get_Cond_selector(pred)) != mode_b) continue;
189 if (!can_empty_block(get_nodes_block(get_irn_n(block, i)))) {
190 ir_fprintf(stderr, "Cannot empty block %+F\n",
191 get_nodes_block(get_irn_n(block, i))
196 for (j = i + 1; j < arity; ++j) {
203 projx1 = walk_to_projx(get_irn_n(block, j));
204 if (projx1 == NULL) continue;
205 pred = get_Proj_pred(projx1);
206 if (get_irn_op(pred) != op_Cond || get_irn_mode(get_Cond_selector(pred)) != mode_b) continue;
207 if (pred != cond) continue;
208 ir_fprintf(stderr, "Found Cond %+F with proj %+F and %+F\n", cond, projx0, projx1);
210 if (!can_empty_block(get_nodes_block(get_irn_n(block, j)))) {
211 ir_fprintf(stderr, "Cannot empty block %+F\n",
212 get_nodes_block(get_irn_n(block, j))
217 conds[0] = get_Cond_selector(cond);
219 psi_block = get_nodes_block(cond);
220 phi = get_block_blockinfo(block)->phi;
222 // Don't generate PsiMs
223 if (get_irn_mode(phi) == mode_M) {
224 /* Something is very fishy if to predecessors of a PhiM point into the
225 * block but not at the same memory node
227 assert(get_irn_n(phi, i) == get_irn_n(phi, j));
229 psi = get_irn_n(phi, i);
230 ir_fprintf(stderr, "Handling memory Phi %+F\n", phi);
232 if (get_Proj_proj(projx0) == pn_Cond_true) {
233 vals[0] = get_irn_n(phi, i);
234 vals[1] = get_irn_n(phi, j);
236 vals[0] = get_irn_n(phi, j);
237 vals[1] = get_irn_n(phi, i);
240 current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
242 ir_fprintf(stderr, "Generating %+F for %+F\n", psi, phi);
248 ir_node** ins = xmalloc(sizeof(*ins) * (arity - 1));
253 for (k = 0; k < i; ++k) ins[l++] = get_irn_n(phi, k);
254 for (++k; k < j; ++k) ins[l++] = get_irn_n(phi, k);
255 for (++k; k < arity; ++k) ins[l++] = get_irn_n(phi, k);
257 assert(l == arity - 1);
258 set_irn_in(phi, l, ins);
263 phi = get_irn_link(phi);
264 } while (phi != NULL && get_irn_op(phi) == op_Phi);
266 exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
267 exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
270 ir_fprintf(stderr, "Welding block %+F to %+F\n", block, psi_block);
271 get_block_blockinfo(psi_block)->evil |= get_block_blockinfo(block)->evil;
272 exchange(block, psi_block);
275 ir_node** ins = xmalloc(sizeof(*ins) * (arity - 1));
280 for (k = 0; k < i; ++k) ins[l++] = get_irn_n(block, k);
281 for (++k; k < j; ++k) ins[l++] = get_irn_n(block, k);
282 for (++k; k < arity; ++k) ins[l++] = get_irn_n(block, k);
283 ins[l++] = new_r_Jmp(current_ir_graph, psi_block);
284 assert(l == arity - 1);
285 set_irn_in(block, l, ins);
295 static void init_block_link(ir_node* block, void* env)
297 block_info* bi = xmalloc(sizeof(*bi));
301 set_irn_link(block, bi);
305 /* Daisy-chain all phis in a block
306 * If a non-movable node is encountered set the evil flag
308 static void collect_phis(ir_node* node, void* env)
313 if (get_irn_op(node) == op_Block) return;
315 block = get_nodes_block(node);
316 bi = get_irn_link(block);
318 if (get_irn_op(node) == op_Phi) {
319 set_irn_link(node, bi->phi);
323 if (get_irn_op(node) == op_Call ||
324 get_irn_op(node) == op_Store ||
325 get_irn_op(node) == op_Load) {
326 ir_fprintf(stderr, "Node %+F in block %+F is unmovable\n", node, block);
330 if (get_irn_op(node) != op_Jmp &&
331 get_irn_op(node) != op_Proj &&
332 get_irn_op(node) != op_Cond &&
333 get_irn_op(node) != op_Cmp &&
334 !mode_is_datab(get_irn_mode(node))) {
335 ir_fprintf(stderr, "Node %+F in block %+F is unmovable\n", node, block);
344 * Transform multiple cascaded Psis into one Psi
346 static ir_node* fold_psi(ir_node* psi)
348 int arity = get_Psi_n_conds(psi);
359 for (i = 0; i < arity; ++i) {
360 n = get_Psi_val(psi, i);
361 if (get_irn_op(n) == op_Psi) {
362 new_arity += get_Psi_n_conds(n) + 1;
367 n = get_Psi_default(psi);
368 if (get_irn_op(n) == op_Psi) {
369 new_arity += get_Psi_n_conds(n);
372 if (arity == new_arity) return psi; // no attached Psis found
373 ir_fprintf(stderr, "Folding %+F from %d to %d conds\n", psi, arity, new_arity);
375 conds = xmalloc(new_arity * sizeof(*conds));
376 vals = xmalloc((new_arity + 1) * sizeof(*vals));
378 for (i = 0; i < arity; ++i) {
379 ir_node* c = get_Psi_cond(psi, i);
381 n = get_Psi_val(psi, i);
382 if (get_irn_op(n) == op_Psi) {
383 a = get_Psi_n_conds(n);
384 for (k = 0; k < a; ++k) {
385 conds[j] = new_r_And(
386 current_ir_graph, get_nodes_block(psi),
387 c, get_Psi_cond(n, k), mode_b
389 vals[j] = get_Psi_val(n, k);
393 vals[j] = get_Psi_default(n);
400 n = get_Psi_default(psi);
401 if (get_irn_op(n) == op_Psi) {
402 a = get_Psi_n_conds(n);
403 for (k = 0; k < a; ++k) {
404 conds[j] = get_Psi_cond(n, k);
405 vals[j] = get_Psi_val(n, k);
408 vals[j] = get_Psi_default(n);
412 assert(j == new_arity);
414 current_ir_graph, get_nodes_block(psi),
415 new_arity, conds, vals, get_irn_mode(psi)
417 ir_fprintf(stderr, "Folded %+F into new %+F\n", psi, new_psi);
418 exchange(psi, new_psi);
426 * Merge consecutive psi inputs if the data inputs are the same
428 static void meld_psi(ir_node* psi)
430 int arity = get_Psi_n_conds(psi);
441 val = get_Psi_val(psi, 0);
442 ir_fprintf(stderr, "Pred 0 of %+F is %+F\n", psi, val);
443 for (i = 1; i < arity; ++i) {
444 ir_node* v = get_Psi_val(psi, i);
445 ir_fprintf(stderr, "Pred %2d of %+F is %+F\n", i, psi, v);
451 ir_fprintf(stderr, "Default of %+F is %+F\n", psi, get_Psi_default(psi));
452 if (val == get_Psi_default(psi)) --new_arity;
454 ir_fprintf(stderr, "Melding Psi %+F from %d conds to %d\n",
455 psi, arity, new_arity
458 if (new_arity == arity) return;
460 // If all data inputs of the Psi are equal, exchange the Psi with that value
461 if (new_arity == 0) {
466 conds = xmalloc(sizeof(*conds) * new_arity);
467 vals = xmalloc(sizeof(*vals) * (new_arity + 1));
468 cond = get_Psi_cond(psi, 0);
469 val = get_Psi_val(psi, 0);
471 for (i = 1; i < arity; ++i) {
472 ir_node* v = get_Psi_val(psi, i);
476 current_ir_graph, get_nodes_block(psi),
477 cond, get_Psi_cond(psi, i), mode_b
486 if (val != get_Psi_default(psi)) {
491 vals[j] = get_Psi_default(psi);
492 assert(j == new_arity);
494 current_ir_graph, get_nodes_block(psi),
495 new_arity, conds, vals, get_irn_mode(psi)
497 ir_fprintf(stderr, "Molded %+F into %+F\n", psi, new_psi);
498 exchange(psi, new_psi);
502 static void optimise_psis(ir_node* node, void* env)
504 if (get_irn_op(node) != op_Psi) return;
506 node = fold_psi(node);
514 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
516 ir_fprintf(stderr, "Running if-conversion on %+F\n", irg);
518 dump_ir_block_graph(irg, "_00_pre");
520 normalize_one_return(irg);
521 remove_critical_cf_edges(irg);
523 dump_ir_block_graph(irg, "_01_normal");
528 irg_block_walk_graph(irg, init_block_link, NULL, NULL);
529 irg_walk_graph(irg, collect_phis, NULL, NULL);
530 irg_block_walk_graph(irg, NULL, if_conv_walker, NULL);
532 dump_ir_block_graph(irg, "_02_ifconv");
534 local_optimize_graph(irg);
535 irg_walk_graph(irg, NULL, optimise_psis, NULL);
537 dump_ir_block_graph(irg, "_03_postifconv");
548 * Make Mux nodes from Conds where it its possible.
549 * @author Sebastian Hack
565 #ifdef HAVE_xmalloc_H
569 #include "irgraph_t.h"
570 #include "irnode_t.h"
574 #include "irmode_t.h"
575 #include "ircons_t.h"
580 #include "irflag_t.h"
582 #include "irprintf.h"
587 #include "bitfiddle.h"
594 * check, if a node is const and return its tarval or
595 * return a default tarval.
596 * @param cnst The node whose tarval to get.
597 * @param or The alternative tarval, if the node is no Const.
598 * @return The tarval of @p cnst, if the node is Const, @p otherwise.
600 static tarval *get_value_or(ir_node *cnst, tarval *or)
602 return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
607 * Try to optimize nested muxes into a dis- or conjunction
609 * @param mux The parent mux, which has muxes as operands.
610 * @return The replacement node for this mux. If the optimization is
611 * successful, this might be an And or Or node, if not, its the mux
614 static ir_node *optimize_mux_chain(ir_node *mux)
619 ir_mode *mode = get_irn_mode(mux);
624 * If we have no mux, or its mode is not integer, we
627 if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
631 null = get_mode_null(mode);
632 minus_one = tarval_sub(null, get_tarval_one(mode));
634 ops[0] = get_Mux_false(mux);
635 ops[1] = get_Mux_true(mux);
637 for(i = 0; i < 2; ++i) {
639 tarval *tva, *tvb, *tvd;
643 * A mux operand at the first position can be factored
644 * out, if the operands fulfill several conditions:
646 * mux(c1, mux(c2, a, b), d)
648 * This can be made into:
649 * 1) mux(c1, 0, d) | mux(c2, a, b)
650 * if a | d == d and b | d == d
652 * 2) mux(c1, -1, d) & mux(c2, a, b)
653 * if a & d == d and a & b == b
655 if(get_irn_op(ops[i]) == op_Mux) {
658 a = get_Mux_false(child_mux);
659 b = get_Mux_true(child_mux);
662 /* Try the or stuff */
663 tva = get_value_or(a, minus_one);
664 tvb = get_value_or(b, minus_one);
665 tvd = get_value_or(d, null);
667 if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
668 && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
670 ops[i] = new_Const(mode, null);
671 res = new_r_Or(current_ir_graph, get_nodes_block(mux),
672 mux, child_mux, mode);
676 /* If the or didn't go, try the and stuff */
677 tva = get_value_or(a, null);
678 tvb = get_value_or(b, null);
679 tvd = get_value_or(d, minus_one);
681 if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
682 && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
684 ops[i] = new_Const(mode, minus_one);
685 res = new_r_And(current_ir_graph, get_nodes_block(mux),
686 mux, child_mux, mode);
692 /* recursively optimize nested muxes. */
693 set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
694 set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
700 /***********************************************************
701 * The If conversion itself.
702 ***********************************************************/
704 /** allow every Mux to be created. */
705 static int default_allow_mux(ir_node *sel, ir_node *false_res, ir_node *true_res) {
712 static const opt_if_conv_info_t default_info = {
717 /** The debugging module. */
718 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
721 * A simple check for side effects upto an opcode of a ir node.
722 * @param irn The ir node to check,
723 * @return 1 if the opcode itself may produce side effects, 0 if not.
725 static INLINE int has_side_effects(const ir_node *irn)
727 ir_op *op = get_irn_op(irn);
732 return !mode_is_datab(get_irn_mode(irn));
736 * Possible failure reasons
738 enum failure_reason_t {
739 SUCCESS = IF_RESULT_SUCCESS,
740 TO_DEEP = IF_RESULT_TOO_DEEP,
741 SIDE_EFFECTS = IF_RESULT_SIDE_EFFECT,
742 PHI_FOUND = IF_RESULT_SIDE_EFFECT_PHI,
743 DENIED = IF_RESULT_DENIED
747 * Decides, if a given expression and its subexpressions
748 * (to certain, also given extent) can be moved to a block.
750 * @param expr The expression to examine.
751 * @param block The block where the expression should go.
752 * @param depth The current depth, passed recursively. Use 0 for
753 * non-recursive calls.
754 * @param info The options for createing Mux nodes.
757 * @return a failure reason
759 static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, const opt_if_conv_info_t *info)
763 ir_node *expr_block = get_nodes_block(expr);
766 * If we are forced to look too deep into the expression,
767 * treat it like it could not be moved.
769 if(depth >= info->max_depth) {
775 * If the block of the expression dominates the specified
776 * destination block, it does not matter if the expression
777 * has side effects or anything else. It is executed on each
778 * path the destination block is reached.
780 if (block_dominates(expr_block, dest_block))
784 * We cannot move phis!
792 * This should be superfluous and could be converted into a assertion.
793 * The destination block _must_ dominate the block of the expression,
794 * else the expression could be used without its definition.
796 if (! block_dominates(dest_block, expr_block)) {
797 res = IF_RESULT_SIDE_EFFECT;
802 * Surely, if the expression does not have a data mode, it is not
803 * movable. Perhaps one should also test the floating property of
806 if (has_side_effects(expr)) {
807 res = IF_RESULT_SIDE_EFFECT;
812 * If the node looks alright so far, look at its operands and
813 * check them out. If one of them cannot be moved, this one
814 * cannot be moved either.
816 for (i = 0, n = get_irn_arity(expr); i < n; ++i) {
817 ir_node *op = get_irn_n(expr, i);
818 int new_depth = is_Proj(op) ? depth : depth + 1;
820 res = _can_move_to(op, dest_block, new_depth, info);
827 DBG((dbg, LEVEL_3, "\t\t\tcan move to %n: %d\n", expr, res));
833 * Convenience function for _can_move_to.
834 * Checks, if an expression can be moved to another block. The check can
835 * be limited to a expression depth meaning if we need to crawl in
836 * deeper into an expression than a given threshold to examine if
837 * it can be moved, the expression is rejected and the test returns
840 * @param expr The expression to check for.
841 * @param dest_block The destination block you want @p expr to be.
842 * @param info The options for createing Mux nodes.
844 * @return return a failure reason
846 static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, const opt_if_conv_info_t *info)
848 return _can_move_to(expr, dest_block, 0, info);
852 * move a DAG given by a root node expr into a new block
854 * @param expr the root of a dag
855 * @param dest_block the destination block
857 static void move_to(ir_node *expr, ir_node *dest_block)
860 ir_node *expr_block = get_nodes_block(expr);
863 * If we reached the dominator, we are done.
864 * We will never put code through the dominator
866 if (block_dominates(expr_block, dest_block))
869 for (i = 0, n = get_irn_arity(expr); i < n; ++i)
870 move_to(get_irn_n(expr, i), dest_block);
872 set_nodes_block(expr, dest_block);
876 * return the common dominator of two blocks
878 static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2)
880 if(block_dominates(b1, b2))
882 else if(block_dominates(b2, b1))
887 for (p = get_Block_idom(b1); !block_dominates(p, b2); p = get_Block_idom(p));
893 * Information about a cond node.
895 typedef struct _cond_t {
896 ir_node *cond; /**< The cond node. */
897 struct list_head list; /**< List head which is used for queuing this cond
898 into the cond bunch it belongs to. */
900 unsigned totally_covers : 1;
901 struct _cond_t *link;
905 * Information about the both 'branches'
906 * (true and false), the cond creates.
909 int pos; /**< Number of the predecessor of the
910 phi block by which this branch is
911 reached. It is -1, if this branch is
912 only reached through another cond. */
914 struct _cond_t *masked_by; /**< If this cond's branch is only reached
915 through another cond, we store this
916 cond ir_node here. */
921 * retrieve the conditional information from a Cond node
923 static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
928 return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
932 typedef void (cond_walker_t)(cond_t *cond, void *env);
934 static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
935 long visited_nr, void *env)
939 if(cond->visited_nr >= visited_nr)
942 cond->visited_nr = visited_nr;
947 for(i = 0; i < 2; ++i) {
948 cond_t *c = cond->cases[i].masked_by;
951 _walk_conds(c, pre, post, visited_nr, env);
958 static long cond_visited_nr = 0;
960 static void walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post, void *env)
962 _walk_conds(cond, pre, post, ++cond_visited_nr, env);
965 static void link_conds(cond_t *cond, void *env)
967 cond_t **ptr = (cond_t **) env;
974 * Compare two conds for use in a firm set.
975 * Two cond_t's are equal, if they designate the same cond node.
977 * @param b Another one.
978 * @param size Not used.
979 * @return 0 (!) if they are equal, != 0 otherwise.
981 static int cond_cmp(const void *a, const void *b, size_t size)
985 return x->cond != y->cond;
989 * Information about conds which can be made to muxes.
990 * Instances of this struct are attached to the link field of
991 * blocks in which phis are located.
993 typedef struct _cond_info_t {
994 struct list_head list; /**< Used to list all of these structs per class. */
996 struct list_head roots; /**< A list of non-depending Conds. Two Conds are
997 independent, if it's not possible not reach one from the
998 other (all Conds in this list have to dominate the
999 block this struct is attached to). */
1001 ir_node *first_phi; /**< The first phi node this cond info was made for. */
1002 set *cond_set; /**< A set of all dominating reachable Conds. */
1008 static void _find_conds(ir_node *irn, unsigned long visited_nr,
1009 ir_node *dominator, cond_t *masked_by, int pos, int depth, cond_info_t *ci)
1012 int saw_select_cond = 0;
1014 block = get_nodes_block(irn);
1017 * Only check this block if it is dominated by the specified
1018 * dominator or it has not been visited yet.
1020 if (block_dominates(dominator, block) && get_Block_block_visited(block) < visited_nr) {
1021 cond_t *res = masked_by;
1024 /* check, if we're on a ProjX
1026 * Further, the ProjX/Cond block must dominate the base block
1027 * (the block with the phi in it), otherwise, the Cond
1028 * is not affecting the phi so that a mux can be inserted.
1030 if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
1032 int proj = get_Proj_proj(irn);
1033 ir_node *cond = get_Proj_pred(irn);
1035 /* true, if the mode is a mode_b cond _NO_ switch cond */
1036 int is_modeb_cond = get_irn_opcode(cond) == iro_Cond
1037 && get_irn_mode(get_Cond_selector(cond)) == mode_b;
1039 saw_select_cond = !is_modeb_cond;
1041 /* Check, if the pred of the proj is a Cond
1042 * with a Projb as selector.
1047 memset(&c, 0, sizeof(c));
1050 c.cases[0].pos = -1;
1051 c.cases[1].pos = -1;
1053 /* get or insert the cond info into the set. */
1054 res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
1057 * If this cond is already masked by the masked_by cond
1058 * return immediately, since we don't have anything to add.
1060 if(masked_by && res->cases[proj].masked_by == masked_by)
1065 list_add(&res->list, &ci->roots);
1069 * Set masked by (either NULL or another cond node.
1070 * If this cond is truly masked by another one, set
1071 * the position of the actually investigated branch
1072 * to -1. Since the cond is masked by another one,
1073 * there could be more ways from the start block
1074 * to this branch, so we choose -1.
1076 res->cases[proj].masked_by = masked_by;
1079 res->cases[proj].pos = pos;
1082 * Since the masked_by nodes masks a cond, remove it from the
1083 * root list of the conf trees.
1086 assert(res->cases[proj].pos < 0);
1087 list_del_init(&masked_by->list);
1090 DBG((dbg, LEVEL_2, "%n (%s branch) "
1091 "for pos %d in block %n reached by %n\n",
1092 cond, proj ? "true" : "false", pos,
1093 block, masked_by ? masked_by->cond : NULL));
1097 if(get_Block_block_visited(block) < visited_nr && !saw_select_cond) {
1099 set_Block_block_visited(block, visited_nr);
1101 /* Search recursively from this cond. */
1102 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1103 ir_node *pred = get_irn_n(block, i);
1106 * If the depth is 0 (the first recursion), we set the pos to
1107 * the current viewed predecessor, else we adopt the position
1108 * as given by the caller. We also increase the depth for the
1109 * recursively called functions.
1111 _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci);
1119 * A convenience function for _find_conds.
1120 * It sets some parameters needed for recursion to appropriate start
1121 * values. Always use this function.
1123 * @param irn The node to start looking for Conds from. This might
1124 * be the phi node we are investigating.
1125 * @param conds The set to record the found Conds in.
1127 static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
1130 unsigned long visited_nr;
1131 ir_node *block = get_nodes_block(irn);
1132 ir_node *dom = get_Block_idom(block);
1134 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1135 ir_node *pred = get_irn_n(block, i);
1137 inc_irg_block_visited(current_ir_graph);
1138 visited_nr = get_irg_block_visited(current_ir_graph);
1139 set_Block_block_visited(block, visited_nr);
1141 DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
1142 _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
1147 * Make the mux for a given cond.
1149 * @param phi The phi node which shall be replaced by a mux.
1150 * @param dom The block where the muxes shall be placed.
1151 * @param cond The cond information.
1152 * @param info The options for createing Mux nodes.
1153 * @return The mux node made for this cond.
1155 static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond,
1156 const opt_if_conv_info_t *info, ir_node **mux, bitset_t *positions,
1157 int *muxes_made, long visited_nr)
1160 ir_node *projb = get_Cond_selector(cond->cond);
1161 ir_node *bl = get_nodes_block(cond->cond);
1162 ir_node *operands[2];
1165 cond->visited_nr = visited_nr;
1166 DBG((dbg, LEVEL_2, "%n\n", cond->cond));
1167 for(i = 0; i < 2; ++i) {
1168 cond_t *masked_by = cond->cases[i].masked_by;
1169 int pos = cond->cases[i].pos;
1175 * If this Cond branch is masked by another cond, make the mux
1176 * for that Cond first, since the Mux for this cond takes
1181 DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
1182 if(masked_by->visited_nr < visited_nr)
1183 operands[i] = make_mux_on_demand(phi, dom, masked_by, info, mux, positions, muxes_made, visited_nr);
1187 * If this cond branch is not masked by another cond, take
1188 * the corresponding phi operand as an operand to the mux.
1191 operands[i] = get_irn_n(phi, pos);
1197 * Move the operands to the dominator block if the cond
1198 * made sense. Some Conds found are not suitable for making a mux
1199 * out of them, since one of their branches cannot be reached from
1200 * the phi block. In that case we do not make a mux and return NULL.
1202 if(operands[0] && operands[1]) {
1203 if (operands[0] == operands[1]) {
1204 /* there is no gain in using mux in this case, as
1205 it will be optimized away. We will NOT move the
1206 content of the blocks either
1208 for (i = 0; i < 2; ++i)
1210 bitset_set(positions, set[i]);
1216 can_move[0] = can_move_to(operands[0], bl, info);
1217 can_move[1] = can_move_to(operands[1], bl, info);
1219 if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) {
1220 if (info->allow_mux(projb, operands[0], operands[1])) {
1221 move_to(operands[0], bl);
1222 move_to(operands[1], bl);
1225 *mux = new_r_Mux(current_ir_graph, bl, projb,
1226 operands[0], operands[1], get_irn_mode(operands[0]));
1230 DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
1231 *mux, projb, operands[0], operands[1], set[0], set[1]));
1233 for(i = 0; i < 2; ++i)
1235 bitset_set(positions, set[i]);
1237 /* we have done one */
1238 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_SUCCESS);
1242 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_DENIED);
1246 if(can_move[0] != SUCCESS)
1247 hook_if_conversion(current_ir_graph, phi, set[0], NULL, can_move[0]);
1248 if(can_move[1] != SUCCESS)
1249 hook_if_conversion(current_ir_graph, phi, set[1], NULL, can_move[1]);
1254 hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF);
1256 hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF);
1262 typedef struct _phi_info_t {
1263 struct list_head list;
1264 cond_info_t *cond_info;
1270 * Examine a phi node if it can be replaced by some muxes.
1271 * @param irn A phi node.
1272 * @param info Parameters for the if conversion algorithm.
1274 static int check_out_phi(phi_info_t *phi_info, const opt_if_conv_info_t *info)
1276 ir_node *irn = phi_info->irn;
1277 ir_node *block, *nw;
1278 cond_info_t *cond_info = phi_info->cond_info;
1282 bitset_t *positions;
1284 block = get_nodes_block(irn);
1285 arity = get_irn_arity(irn);
1286 positions = bitset_alloca(arity);
1288 assert(is_Phi(irn));
1289 assert(get_irn_arity(irn) == get_irn_arity(block));
1292 DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
1294 list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
1295 ir_node *cidom = block;
1296 ir_node *mux = NULL;
1297 cond_t *p, *head = NULL;
1300 bitset_clear_all(positions);
1302 DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
1304 * Link all conds which are in the subtree of
1305 * the current cond in the list together.
1307 walk_conds(cond, link_conds, NULL, &head);
1310 for(p = head; p; p = p->link) {
1311 for(i = 0; i < 2; ++i) {
1312 int pos = p->cases[i].pos;
1314 cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
1318 DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
1319 make_mux_on_demand(irn, cidom, cond, info, &mux, positions, &muxes_made, ++cond_visited_nr);
1322 bitset_foreach(positions, pos)
1323 set_irn_n(irn, (int) pos, mux);
1328 * optimize the phi away. This can anable further runs of this
1329 * function. Look at _can_move. phis cannot be moved there.
1331 nw = optimize_in_place_2(irn);
1338 typedef struct _cond_walk_info_t {
1339 struct obstack *obst;
1340 struct list_head cond_info_head;
1341 struct list_head phi_head;
1345 static void annotate_cond_info_pre(ir_node *irn, void *data)
1347 set_irn_link(irn, NULL);
1350 static void annotate_cond_info_post(ir_node *irn, void *data)
1352 cond_walk_info_t *cwi = data;
1355 * Check, if the node is a phi
1356 * we then compute a set of conds which are reachable from this
1357 * phi's block up to its dominator.
1358 * The set is attached to the blocks link field.
1360 if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
1361 ir_node *block = get_nodes_block(irn);
1363 cond_info_t *ci = get_irn_link(block);
1365 /* If the set is not yet computed, do it now. */
1367 ci = obstack_alloc(cwi->obst, sizeof(*ci));
1368 ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
1369 ci->first_phi = irn;
1371 INIT_LIST_HEAD(&ci->roots);
1372 INIT_LIST_HEAD(&ci->list);
1375 * Add this cond info to the list of all cond infos
1376 * in this graph. This is just done to xfree the
1377 * set easier afterwards (we save an irg_walk_graph).
1379 list_add(&cwi->cond_info_head, &ci->list);
1381 DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
1384 * Fill the set with conds we find on the way from
1385 * the block to its dominator.
1387 find_conds(irn, ci);
1390 * If there where no suitable conds, delete the set
1391 * immediately and reset the set pointer to NULL
1393 if(set_count(ci->cond_set) == 0) {
1394 del_set(ci->cond_set);
1395 list_del(&ci->list);
1396 obstack_free(cwi->obst, ci);
1402 DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
1404 set_irn_link(block, ci);
1407 phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
1410 INIT_LIST_HEAD(&pi->list);
1411 list_add(&pi->list, &cwi->phi_head);
1417 static void dump_conds(cond_t *cond, void *env)
1422 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
1423 cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
1424 get_nodes_block(cond->cond));
1426 for(i = 0; i < 2; ++i)
1427 if(cond->cases[i].masked_by)
1428 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
1429 cond, cond->cases[i].masked_by, i);
1432 static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi)
1437 snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
1439 if((f = fopen(buf, "wt")) != NULL) {
1444 ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
1445 list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
1446 ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
1447 list_for_each_entry(cond_t, cond, &ci->roots, list) {
1448 walk_conds(cond, NULL, dump_conds, f);
1449 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
1453 list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
1454 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
1455 phi->irn, phi->irn, get_nodes_block(phi->irn));
1456 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
1462 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
1465 struct obstack obst;
1466 phi_info_t *phi_info;
1467 cond_info_t *cond_info;
1468 cond_walk_info_t cwi;
1470 opt_if_conv_info_t p;
1472 if(!get_opt_if_conversion())
1475 /* get the parameters */
1477 memcpy(&p, params, sizeof(p));
1479 memcpy(&p, &default_info, sizeof(p));
1482 p.allow_mux = default_info.allow_mux;
1484 obstack_init(&obst);
1487 INIT_LIST_HEAD(&cwi.cond_info_head);
1488 INIT_LIST_HEAD(&cwi.phi_head);
1490 /* Init the debug stuff. */
1491 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
1493 firm_dbg_set_mask(dbg, LEVEL_1|LEVEL_2|LEVEL_3);
1496 /* if-conversion works better with normalized returns */
1497 normalize_one_return(irg);
1499 /* Ensure, that the dominators are computed. */
1502 DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
1503 get_entity_name(get_irg_entity(irg)), irg));
1506 * Collect information about the conds pu the phis on an obstack.
1507 * It is important that phi nodes which are 'higher' (with a
1508 * lower dfs pre order) are in front of the obstack. Since they are
1509 * possibly turned in to muxes this can enable the optimization
1512 irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
1515 vcg_dump_conds(irg, &cwi);
1518 /* Process each suitable phi found. */
1519 list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
1520 DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
1521 muxes_made += check_out_phi(phi_info, &p);
1524 list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
1525 del_set(cond_info->cond_set);
1528 DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
1530 obstack_free(&obst, NULL);
1532 dump_ir_block_graph(irg, "_ifconv_hack");