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.
31 static ir_node* walk_to_projx(ir_node* start)
36 pred = get_nodes_block(start);
37 cdep = get_unique_cdep(pred);
38 if (cdep == NULL) return NULL;
40 assert(get_irn_arity(pred) == 1);
41 pred = get_irn_n(pred, 0);
42 if (get_irn_op(pred) == op_Proj) {
43 assert(get_irn_mode(pred) == mode_X);
51 typedef struct block_info {
57 static int can_empty_block(ir_node* block)
59 return !((block_info*)get_irn_link(block))->evil;
64 * Copies the DAG starting at node to the ith predecessor block of src_block
65 * -if the node isn't in the src_block, this is a nop and the node is returned
66 * -if the node is a phi in the src_block, the ith predecessor of the phi is
68 * otherwise returns the copy of the passed node
70 static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
77 if (get_nodes_block(node) != src_block) return node;
78 if (get_irn_op(node) == op_Phi) return get_irn_n(node, i);
80 copy_irn_to_irg(node, current_ir_graph);
81 copy = get_irn_link(node);
82 dst_block = get_nodes_block(get_irn_n(src_block, i));
83 set_nodes_block(copy, dst_block);
85 ir_fprintf(stderr, "Copying node %+F to block %+F, copy is %+F\n",
89 arity = get_irn_arity(node);
90 for (j = 0; j < arity; ++j) {
91 set_irn_n(copy, j, copy_to(get_irn_n(node, j), src_block, i));
92 ir_fprintf(stderr, "-- pred %d is %+F\n", j, get_irn_n(copy, j));
99 * Duplicate and move the contents of ith block predecessor into its
100 * predecessors if the block has multiple control dependencies and only one
102 * Also bail out if the block contains non-movable nodes, because later
103 * if-conversion would be pointless.
105 static int fission_block(ir_node* block, int i)
107 ir_node* pred = get_irn_n(block, i);
116 if (get_irn_op(pred) != op_Jmp) return 0;
117 pred_block = get_nodes_block(pred);
119 if (!has_multiple_cdep(pred_block)) return 0;
120 if (!can_empty_block(pred_block)) return 0;
122 ir_fprintf(stderr, "Fissioning block %+F\n", pred_block);
124 pred_arity = get_irn_arity(pred_block);
125 arity = get_irn_arity(block);
126 info = get_irn_link(block);
127 ins = malloc(sizeof(*ins) * (arity + pred_arity - 1));
128 for (phi = info->phi; phi != NULL; phi = get_irn_link(phi)) {
129 for (j = 0; j < i; ++j) ins[j] = get_irn_n(phi, j);
130 for (j = 0; j < pred_arity; ++j) {
131 ins[i + j] = copy_to(get_irn_n(phi, i), pred_block, j);
133 for (j = i + 1; j < arity; ++j) {
134 ins[pred_arity - 1 + j] = get_irn_n(phi, j);
136 set_irn_in(phi, arity + pred_arity - 1, ins);
138 for (j = 0; j < i; ++j) ins[j] = get_irn_n(block, j);
139 for (j = 0; j < pred_arity; ++j) ins[i + j] = get_irn_n(pred_block, j);
140 for (j = i + 1; j < arity; ++j) ins[pred_arity - 1 + j] = get_irn_n(block, j);
141 set_irn_in(block, arity + pred_arity - 1, ins);
144 /* Kill all Phis in the fissioned block
145 * This is to make sure they're not kept alive
147 info = get_irn_link(pred_block);
149 while (phi != NULL) {
150 ir_node* next = get_irn_link(phi);
151 exchange(phi, new_Bad());
158 static void if_conv_walker(ir_node* block, void* env)
164 // Bail out, if there are no Phis at all
165 if (((block_info*)get_irn_link(block))->phi == NULL) return;
168 arity = get_irn_arity(block);
169 for (i = 0; i < arity; ++i) {
170 if (fission_block(block, i)) goto restart;
174 arity = get_irn_arity(block);
175 for (i = 0; i < arity; ++i) {
181 projx0 = walk_to_projx(get_irn_n(block, i));
182 if (projx0 == NULL) return;
183 pred = get_Proj_pred(projx0);
184 if (get_irn_op(pred) != op_Cond || get_irn_mode(get_Cond_selector(pred)) != mode_b) continue;
187 if (!can_empty_block(get_nodes_block(get_irn_n(block, i)))) {
188 ir_fprintf(stderr, "Cannot empty block %+F\n",
189 get_nodes_block(get_irn_n(block, i))
194 for (j = i + 1; j < arity; ++j) {
201 projx1 = walk_to_projx(get_irn_n(block, j));
202 if (projx1 == NULL) continue;
203 pred = get_Proj_pred(projx1);
204 if (get_irn_op(pred) != op_Cond || get_irn_mode(get_Cond_selector(pred)) != mode_b) continue;
205 if (pred != cond) continue;
206 ir_fprintf(stderr, "Found Cond %+F with proj %+F and %+F\n", cond, projx0, projx1);
208 if (!can_empty_block(get_nodes_block(get_irn_n(block, j)))) {
209 ir_fprintf(stderr, "Cannot empty block %+F\n",
210 get_nodes_block(get_irn_n(block, j))
215 conds[0] = get_Cond_selector(cond);
217 psi_block = get_nodes_block(cond);
218 phi = ((block_info*)get_irn_link(block))->phi;
220 // Don't generate PsiMs
221 if (get_irn_mode(phi) == mode_M) {
222 /* Something is very fishy if to predecessors of a PhiM point into the
223 * block but not at the same memory node
225 assert(get_irn_n(phi, i) == get_irn_n(phi, j));
227 psi = get_irn_n(phi, i);
228 ir_fprintf(stderr, "Handling memory Phi %+F\n", phi);
230 if (get_Proj_proj(projx0) == pn_Cond_true) {
231 vals[0] = get_irn_n(phi, i);
232 vals[1] = get_irn_n(phi, j);
234 vals[0] = get_irn_n(phi, j);
235 vals[1] = get_irn_n(phi, i);
238 current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
240 ir_fprintf(stderr, "Generating %+F for %+F\n", psi, phi);
246 ir_node** ins = malloc(sizeof(*ins) * (arity - 1));
251 for (k = 0; k < i; ++k) ins[l++] = get_irn_n(phi, k);
252 for (++k; k < j; ++k) ins[l++] = get_irn_n(phi, k);
253 for (++k; k < arity; ++k) ins[l++] = get_irn_n(phi, k);
255 assert(l == arity - 1);
256 set_irn_in(phi, l, ins);
261 phi = get_irn_link(phi);
262 } while (phi != NULL && get_irn_op(phi) == op_Phi);
264 exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
265 exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
268 ir_fprintf(stderr, "Welding block %+F to %+F\n", block, psi_block);
269 ((block_info*)get_irn_link(psi_block))->evil |=
270 ((block_info*)get_irn_link(block))->evil;
271 exchange(block, psi_block);
274 ir_node** ins = malloc(sizeof(*ins) * (arity - 1));
279 for (k = 0; k < i; ++k) ins[l++] = get_irn_n(block, k);
280 for (++k; k < j; ++k) ins[l++] = get_irn_n(block, k);
281 for (++k; k < arity; ++k) ins[l++] = get_irn_n(block, k);
282 ins[l++] = new_r_Jmp(current_ir_graph, psi_block);
283 assert(l == arity - 1);
284 set_irn_in(block, l, ins);
294 static void init_block_link(ir_node* block, void* env)
296 block_info* bi = malloc(sizeof(*bi));
300 set_irn_link(block, bi);
304 /* Daisy-chain all phis in a block
305 * If a non-movable node is encountered set the evil flag
307 static void collect_phis(ir_node* node, void* env)
312 if (get_irn_op(node) == op_Block) return;
314 block = get_nodes_block(node);
315 bi = get_irn_link(block);
317 if (get_irn_op(node) == op_Phi) {
318 set_irn_link(node, bi->phi);
322 if (get_irn_op(node) == op_Call ||
323 get_irn_op(node) == op_Store ||
324 get_irn_op(node) == op_Load) {
325 ir_fprintf(stderr, "Node %+F in block %+F is unmovable\n", node, block);
329 if (get_irn_op(node) != op_Jmp &&
330 get_irn_op(node) != op_Proj &&
331 get_irn_op(node) != op_Cond &&
332 get_irn_op(node) != op_Cmp &&
333 !mode_is_datab(get_irn_mode(node))) {
334 ir_fprintf(stderr, "Node %+F in block %+F is unmovable\n", node, block);
343 * Transform multiple cascaded Psis into one Psi
345 static ir_node* fold_psi(ir_node* psi)
347 int arity = get_Psi_n_conds(psi);
358 for (i = 0; i < arity; ++i) {
359 n = get_Psi_val(psi, i);
360 if (get_irn_op(n) == op_Psi) {
361 new_arity += get_Psi_n_conds(n) + 1;
366 n = get_Psi_default(psi);
367 if (get_irn_op(n) == op_Psi) {
368 new_arity += get_Psi_n_conds(n);
371 if (arity == new_arity) return psi; // no attached Psis found
372 ir_fprintf(stderr, "Folding %+F from %d to %d conds\n", psi, arity, new_arity);
374 conds = malloc(new_arity * sizeof(*conds));
375 vals = malloc((new_arity + 1) * sizeof(*vals));
377 for (i = 0; i < arity; ++i) {
378 ir_node* c = get_Psi_cond(psi, i);
380 n = get_Psi_val(psi, i);
381 if (get_irn_op(n) == op_Psi) {
382 a = get_Psi_n_conds(n);
383 for (k = 0; k < a; ++k) {
384 conds[j] = new_r_And(
385 current_ir_graph, get_nodes_block(psi),
386 c, get_Psi_cond(n, k), mode_b
388 vals[j] = get_Psi_val(n, k);
392 vals[j] = get_Psi_default(n);
399 n = get_Psi_default(psi);
400 if (get_irn_op(n) == op_Psi) {
401 a = get_Psi_n_conds(n);
402 for (k = 0; k < a; ++k) {
403 conds[j] = get_Psi_cond(n, k);
404 vals[j] = get_Psi_val(n, k);
407 vals[j] = get_Psi_default(n);
411 assert(j == new_arity);
413 current_ir_graph, get_nodes_block(psi),
414 new_arity, conds, vals, get_irn_mode(psi)
416 ir_fprintf(stderr, "Folded %+F into new %+F\n", psi, new_psi);
417 exchange(psi, new_psi);
425 * Merge consecutive psi inputs if the data inputs are the same
427 static void meld_psi(ir_node* psi)
429 int arity = get_Psi_n_conds(psi);
440 val = get_Psi_val(psi, 0);
441 ir_fprintf(stderr, "Pred 0 of %+F is %+F\n", psi, val);
442 for (i = 1; i < arity; ++i) {
443 ir_node* v = get_Psi_val(psi, i);
444 ir_fprintf(stderr, "Pred %2d of %+F is %+F\n", i, psi, v);
450 ir_fprintf(stderr, "Default of %+F is %+F\n", psi, get_Psi_default(psi));
451 if (val == get_Psi_default(psi)) --new_arity;
453 ir_fprintf(stderr, "Melding Psi %+F from %d conds to %d\n",
454 psi, arity, new_arity
457 if (new_arity == arity) return;
459 // If all data inputs of the Psi are equal, exchange the Psi with that value
460 if (new_arity == 0) {
465 conds = malloc(sizeof(*conds) * new_arity);
466 vals = malloc(sizeof(*vals) * (new_arity + 1));
467 cond = get_Psi_cond(psi, 0);
468 val = get_Psi_val(psi, 0);
470 for (i = 1; i < arity; ++i) {
471 ir_node* v = get_Psi_val(psi, i);
475 current_ir_graph, get_nodes_block(psi),
476 cond, get_Psi_cond(psi, i), mode_b
485 if (val != get_Psi_default(psi)) {
490 vals[j] = get_Psi_default(psi);
491 assert(j == new_arity);
493 current_ir_graph, get_nodes_block(psi),
494 new_arity, conds, vals, get_irn_mode(psi)
496 ir_fprintf(stderr, "Molded %+F into %+F\n", psi, new_psi);
497 exchange(psi, new_psi);
501 static void optimise_psis(ir_node* node, void* env)
503 if (get_irn_op(node) != op_Psi) return;
505 node = fold_psi(node);
513 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
515 ir_fprintf(stderr, "Running if-conversion on %+F\n", irg);
517 dump_ir_block_graph(irg, "_00_pre");
519 normalize_one_return(irg);
520 remove_critical_cf_edges(irg);
522 dump_ir_block_graph(irg, "_01_normal");
527 irg_block_walk_graph(irg, init_block_link, NULL, NULL);
528 irg_walk_graph(irg, collect_phis, NULL, NULL);
529 irg_block_walk_graph(irg, NULL, if_conv_walker, NULL);
531 dump_ir_block_graph(irg, "_02_ifconv");
533 local_optimize_graph(irg);
534 irg_walk_graph(irg, NULL, optimise_psis, NULL);
536 dump_ir_block_graph(irg, "_03_postifconv");
547 * Make Mux nodes from Conds where it its possible.
548 * @author Sebastian Hack
568 #include "irgraph_t.h"
569 #include "irnode_t.h"
573 #include "irmode_t.h"
574 #include "ircons_t.h"
579 #include "irflag_t.h"
581 #include "irprintf.h"
586 #include "bitfiddle.h"
593 * check, if a node is const and return its tarval or
594 * return a default tarval.
595 * @param cnst The node whose tarval to get.
596 * @param or The alternative tarval, if the node is no Const.
597 * @return The tarval of @p cnst, if the node is Const, @p otherwise.
599 static tarval *get_value_or(ir_node *cnst, tarval *or)
601 return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
606 * Try to optimize nested muxes into a dis- or conjunction
608 * @param mux The parent mux, which has muxes as operands.
609 * @return The replacement node for this mux. If the optimization is
610 * successful, this might be an And or Or node, if not, its the mux
613 static ir_node *optimize_mux_chain(ir_node *mux)
618 ir_mode *mode = get_irn_mode(mux);
623 * If we have no mux, or its mode is not integer, we
626 if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
630 null = get_mode_null(mode);
631 minus_one = tarval_sub(null, get_tarval_one(mode));
633 ops[0] = get_Mux_false(mux);
634 ops[1] = get_Mux_true(mux);
636 for(i = 0; i < 2; ++i) {
638 tarval *tva, *tvb, *tvd;
642 * A mux operand at the first position can be factored
643 * out, if the operands fulfill several conditions:
645 * mux(c1, mux(c2, a, b), d)
647 * This can be made into:
648 * 1) mux(c1, 0, d) | mux(c2, a, b)
649 * if a | d == d and b | d == d
651 * 2) mux(c1, -1, d) & mux(c2, a, b)
652 * if a & d == d and a & b == b
654 if(get_irn_op(ops[i]) == op_Mux) {
657 a = get_Mux_false(child_mux);
658 b = get_Mux_true(child_mux);
661 /* Try the or stuff */
662 tva = get_value_or(a, minus_one);
663 tvb = get_value_or(b, minus_one);
664 tvd = get_value_or(d, null);
666 if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
667 && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
669 ops[i] = new_Const(mode, null);
670 res = new_r_Or(current_ir_graph, get_nodes_block(mux),
671 mux, child_mux, mode);
675 /* If the or didn't go, try the and stuff */
676 tva = get_value_or(a, null);
677 tvb = get_value_or(b, null);
678 tvd = get_value_or(d, minus_one);
680 if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
681 && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
683 ops[i] = new_Const(mode, minus_one);
684 res = new_r_And(current_ir_graph, get_nodes_block(mux),
685 mux, child_mux, mode);
691 /* recursively optimize nested muxes. */
692 set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
693 set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
699 /***********************************************************
700 * The If conversion itself.
701 ***********************************************************/
703 /** allow every Mux to be created. */
704 static int default_allow_mux(ir_node *sel, ir_node *false_res, ir_node *true_res) {
711 static const opt_if_conv_info_t default_info = {
716 /** The debugging module. */
717 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
720 * A simple check for side effects upto an opcode of a ir node.
721 * @param irn The ir node to check,
722 * @return 1 if the opcode itself may produce side effects, 0 if not.
724 static INLINE int has_side_effects(const ir_node *irn)
726 ir_op *op = get_irn_op(irn);
731 return !mode_is_datab(get_irn_mode(irn));
735 * Possible failure reasons
737 enum failure_reason_t {
738 SUCCESS = IF_RESULT_SUCCESS,
739 TO_DEEP = IF_RESULT_TOO_DEEP,
740 SIDE_EFFECTS = IF_RESULT_SIDE_EFFECT,
741 PHI_FOUND = IF_RESULT_SIDE_EFFECT_PHI,
742 DENIED = IF_RESULT_DENIED
746 * Decides, if a given expression and its subexpressions
747 * (to certain, also given extent) can be moved to a block.
749 * @param expr The expression to examine.
750 * @param block The block where the expression should go.
751 * @param depth The current depth, passed recursively. Use 0 for
752 * non-recursive calls.
753 * @param info The options for createing Mux nodes.
756 * @return a failure reason
758 static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, const opt_if_conv_info_t *info)
762 ir_node *expr_block = get_nodes_block(expr);
765 * If we are forced to look too deep into the expression,
766 * treat it like it could not be moved.
768 if(depth >= info->max_depth) {
774 * If the block of the expression dominates the specified
775 * destination block, it does not matter if the expression
776 * has side effects or anything else. It is executed on each
777 * path the destination block is reached.
779 if (block_dominates(expr_block, dest_block))
783 * We cannot move phis!
791 * This should be superfluous and could be converted into a assertion.
792 * The destination block _must_ dominate the block of the expression,
793 * else the expression could be used without its definition.
795 if (! block_dominates(dest_block, expr_block)) {
796 res = IF_RESULT_SIDE_EFFECT;
801 * Surely, if the expression does not have a data mode, it is not
802 * movable. Perhaps one should also test the floating property of
805 if (has_side_effects(expr)) {
806 res = IF_RESULT_SIDE_EFFECT;
811 * If the node looks alright so far, look at its operands and
812 * check them out. If one of them cannot be moved, this one
813 * cannot be moved either.
815 for (i = 0, n = get_irn_arity(expr); i < n; ++i) {
816 ir_node *op = get_irn_n(expr, i);
817 int new_depth = is_Proj(op) ? depth : depth + 1;
819 res = _can_move_to(op, dest_block, new_depth, info);
826 DBG((dbg, LEVEL_3, "\t\t\tcan move to %n: %d\n", expr, res));
832 * Convenience function for _can_move_to.
833 * Checks, if an expression can be moved to another block. The check can
834 * be limited to a expression depth meaning if we need to crawl in
835 * deeper into an expression than a given threshold to examine if
836 * it can be moved, the expression is rejected and the test returns
839 * @param expr The expression to check for.
840 * @param dest_block The destination block you want @p expr to be.
841 * @param info The options for createing Mux nodes.
843 * @return return a failure reason
845 static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, const opt_if_conv_info_t *info)
847 return _can_move_to(expr, dest_block, 0, info);
851 * move a DAG given by a root node expr into a new block
853 * @param expr the root of a dag
854 * @param dest_block the destination block
856 static void move_to(ir_node *expr, ir_node *dest_block)
859 ir_node *expr_block = get_nodes_block(expr);
862 * If we reached the dominator, we are done.
863 * We will never put code through the dominator
865 if (block_dominates(expr_block, dest_block))
868 for (i = 0, n = get_irn_arity(expr); i < n; ++i)
869 move_to(get_irn_n(expr, i), dest_block);
871 set_nodes_block(expr, dest_block);
875 * return the common dominator of two blocks
877 static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2)
879 if(block_dominates(b1, b2))
881 else if(block_dominates(b2, b1))
886 for (p = get_Block_idom(b1); !block_dominates(p, b2); p = get_Block_idom(p));
892 * Information about a cond node.
894 typedef struct _cond_t {
895 ir_node *cond; /**< The cond node. */
896 struct list_head list; /**< List head which is used for queuing this cond
897 into the cond bunch it belongs to. */
899 unsigned totally_covers : 1;
900 struct _cond_t *link;
904 * Information about the both 'branches'
905 * (true and false), the cond creates.
908 int pos; /**< Number of the predecessor of the
909 phi block by which this branch is
910 reached. It is -1, if this branch is
911 only reached through another cond. */
913 struct _cond_t *masked_by; /**< If this cond's branch is only reached
914 through another cond, we store this
915 cond ir_node here. */
920 * retrieve the conditional information from a Cond node
922 static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
927 return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
931 typedef void (cond_walker_t)(cond_t *cond, void *env);
933 static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
934 long visited_nr, void *env)
938 if(cond->visited_nr >= visited_nr)
941 cond->visited_nr = visited_nr;
946 for(i = 0; i < 2; ++i) {
947 cond_t *c = cond->cases[i].masked_by;
950 _walk_conds(c, pre, post, visited_nr, env);
957 static long cond_visited_nr = 0;
959 static void walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post, void *env)
961 _walk_conds(cond, pre, post, ++cond_visited_nr, env);
964 static void link_conds(cond_t *cond, void *env)
966 cond_t **ptr = (cond_t **) env;
973 * Compare two conds for use in a firm set.
974 * Two cond_t's are equal, if they designate the same cond node.
976 * @param b Another one.
977 * @param size Not used.
978 * @return 0 (!) if they are equal, != 0 otherwise.
980 static int cond_cmp(const void *a, const void *b, size_t size)
984 return x->cond != y->cond;
988 * Information about conds which can be made to muxes.
989 * Instances of this struct are attached to the link field of
990 * blocks in which phis are located.
992 typedef struct _cond_info_t {
993 struct list_head list; /**< Used to list all of these structs per class. */
995 struct list_head roots; /**< A list of non-depending Conds. Two Conds are
996 independent, if it's not possible not reach one from the
997 other (all Conds in this list have to dominate the
998 block this struct is attached to). */
1000 ir_node *first_phi; /**< The first phi node this cond info was made for. */
1001 set *cond_set; /**< A set of all dominating reachable Conds. */
1007 static void _find_conds(ir_node *irn, unsigned long visited_nr,
1008 ir_node *dominator, cond_t *masked_by, int pos, int depth, cond_info_t *ci)
1011 int saw_select_cond = 0;
1013 block = get_nodes_block(irn);
1016 * Only check this block if it is dominated by the specified
1017 * dominator or it has not been visited yet.
1019 if (block_dominates(dominator, block) && get_Block_block_visited(block) < visited_nr) {
1020 cond_t *res = masked_by;
1023 /* check, if we're on a ProjX
1025 * Further, the ProjX/Cond block must dominate the base block
1026 * (the block with the phi in it), otherwise, the Cond
1027 * is not affecting the phi so that a mux can be inserted.
1029 if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
1031 int proj = get_Proj_proj(irn);
1032 ir_node *cond = get_Proj_pred(irn);
1034 /* true, if the mode is a mode_b cond _NO_ switch cond */
1035 int is_modeb_cond = get_irn_opcode(cond) == iro_Cond
1036 && get_irn_mode(get_Cond_selector(cond)) == mode_b;
1038 saw_select_cond = !is_modeb_cond;
1040 /* Check, if the pred of the proj is a Cond
1041 * with a Projb as selector.
1046 memset(&c, 0, sizeof(c));
1049 c.cases[0].pos = -1;
1050 c.cases[1].pos = -1;
1052 /* get or insert the cond info into the set. */
1053 res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
1056 * If this cond is already masked by the masked_by cond
1057 * return immediately, since we don't have anything to add.
1059 if(masked_by && res->cases[proj].masked_by == masked_by)
1064 list_add(&res->list, &ci->roots);
1068 * Set masked by (either NULL or another cond node.
1069 * If this cond is truly masked by another one, set
1070 * the position of the actually investigated branch
1071 * to -1. Since the cond is masked by another one,
1072 * there could be more ways from the start block
1073 * to this branch, so we choose -1.
1075 res->cases[proj].masked_by = masked_by;
1078 res->cases[proj].pos = pos;
1081 * Since the masked_by nodes masks a cond, remove it from the
1082 * root list of the conf trees.
1085 assert(res->cases[proj].pos < 0);
1086 list_del_init(&masked_by->list);
1089 DBG((dbg, LEVEL_2, "%n (%s branch) "
1090 "for pos %d in block %n reached by %n\n",
1091 cond, proj ? "true" : "false", pos,
1092 block, masked_by ? masked_by->cond : NULL));
1096 if(get_Block_block_visited(block) < visited_nr && !saw_select_cond) {
1098 set_Block_block_visited(block, visited_nr);
1100 /* Search recursively from this cond. */
1101 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1102 ir_node *pred = get_irn_n(block, i);
1105 * If the depth is 0 (the first recursion), we set the pos to
1106 * the current viewed predecessor, else we adopt the position
1107 * as given by the caller. We also increase the depth for the
1108 * recursively called functions.
1110 _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci);
1118 * A convenience function for _find_conds.
1119 * It sets some parameters needed for recursion to appropriate start
1120 * values. Always use this function.
1122 * @param irn The node to start looking for Conds from. This might
1123 * be the phi node we are investigating.
1124 * @param conds The set to record the found Conds in.
1126 static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
1129 unsigned long visited_nr;
1130 ir_node *block = get_nodes_block(irn);
1131 ir_node *dom = get_Block_idom(block);
1133 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1134 ir_node *pred = get_irn_n(block, i);
1136 inc_irg_block_visited(current_ir_graph);
1137 visited_nr = get_irg_block_visited(current_ir_graph);
1138 set_Block_block_visited(block, visited_nr);
1140 DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
1141 _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
1146 * Make the mux for a given cond.
1148 * @param phi The phi node which shall be replaced by a mux.
1149 * @param dom The block where the muxes shall be placed.
1150 * @param cond The cond information.
1151 * @param info The options for createing Mux nodes.
1152 * @return The mux node made for this cond.
1154 static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond,
1155 const opt_if_conv_info_t *info, ir_node **mux, bitset_t *positions,
1156 int *muxes_made, long visited_nr)
1159 ir_node *projb = get_Cond_selector(cond->cond);
1160 ir_node *bl = get_nodes_block(cond->cond);
1161 ir_node *operands[2];
1164 cond->visited_nr = visited_nr;
1165 DBG((dbg, LEVEL_2, "%n\n", cond->cond));
1166 for(i = 0; i < 2; ++i) {
1167 cond_t *masked_by = cond->cases[i].masked_by;
1168 int pos = cond->cases[i].pos;
1174 * If this Cond branch is masked by another cond, make the mux
1175 * for that Cond first, since the Mux for this cond takes
1180 DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
1181 if(masked_by->visited_nr < visited_nr)
1182 operands[i] = make_mux_on_demand(phi, dom, masked_by, info, mux, positions, muxes_made, visited_nr);
1186 * If this cond branch is not masked by another cond, take
1187 * the corresponding phi operand as an operand to the mux.
1190 operands[i] = get_irn_n(phi, pos);
1196 * Move the operands to the dominator block if the cond
1197 * made sense. Some Conds found are not suitable for making a mux
1198 * out of them, since one of their branches cannot be reached from
1199 * the phi block. In that case we do not make a mux and return NULL.
1201 if(operands[0] && operands[1]) {
1202 if (operands[0] == operands[1]) {
1203 /* there is no gain in using mux in this case, as
1204 it will be optimized away. We will NOT move the
1205 content of the blocks either
1207 for (i = 0; i < 2; ++i)
1209 bitset_set(positions, set[i]);
1215 can_move[0] = can_move_to(operands[0], bl, info);
1216 can_move[1] = can_move_to(operands[1], bl, info);
1218 if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) {
1219 if (info->allow_mux(projb, operands[0], operands[1])) {
1220 move_to(operands[0], bl);
1221 move_to(operands[1], bl);
1224 *mux = new_r_Mux(current_ir_graph, bl, projb,
1225 operands[0], operands[1], get_irn_mode(operands[0]));
1229 DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
1230 *mux, projb, operands[0], operands[1], set[0], set[1]));
1232 for(i = 0; i < 2; ++i)
1234 bitset_set(positions, set[i]);
1236 /* we have done one */
1237 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_SUCCESS);
1241 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_DENIED);
1245 if(can_move[0] != SUCCESS)
1246 hook_if_conversion(current_ir_graph, phi, set[0], NULL, can_move[0]);
1247 if(can_move[1] != SUCCESS)
1248 hook_if_conversion(current_ir_graph, phi, set[1], NULL, can_move[1]);
1253 hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF);
1255 hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF);
1261 typedef struct _phi_info_t {
1262 struct list_head list;
1263 cond_info_t *cond_info;
1269 * Examine a phi node if it can be replaced by some muxes.
1270 * @param irn A phi node.
1271 * @param info Parameters for the if conversion algorithm.
1273 static int check_out_phi(phi_info_t *phi_info, const opt_if_conv_info_t *info)
1275 ir_node *irn = phi_info->irn;
1276 ir_node *block, *nw;
1277 cond_info_t *cond_info = phi_info->cond_info;
1281 bitset_t *positions;
1283 block = get_nodes_block(irn);
1284 arity = get_irn_arity(irn);
1285 positions = bitset_alloca(arity);
1287 assert(is_Phi(irn));
1288 assert(get_irn_arity(irn) == get_irn_arity(block));
1291 DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
1293 list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
1294 ir_node *cidom = block;
1295 ir_node *mux = NULL;
1296 cond_t *p, *head = NULL;
1299 bitset_clear_all(positions);
1301 DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
1303 * Link all conds which are in the subtree of
1304 * the current cond in the list together.
1306 walk_conds(cond, link_conds, NULL, &head);
1309 for(p = head; p; p = p->link) {
1310 for(i = 0; i < 2; ++i) {
1311 int pos = p->cases[i].pos;
1313 cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
1317 DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
1318 make_mux_on_demand(irn, cidom, cond, info, &mux, positions, &muxes_made, ++cond_visited_nr);
1321 bitset_foreach(positions, pos)
1322 set_irn_n(irn, (int) pos, mux);
1327 * optimize the phi away. This can anable further runs of this
1328 * function. Look at _can_move. phis cannot be moved there.
1330 nw = optimize_in_place_2(irn);
1337 typedef struct _cond_walk_info_t {
1338 struct obstack *obst;
1339 struct list_head cond_info_head;
1340 struct list_head phi_head;
1344 static void annotate_cond_info_pre(ir_node *irn, void *data)
1346 set_irn_link(irn, NULL);
1349 static void annotate_cond_info_post(ir_node *irn, void *data)
1351 cond_walk_info_t *cwi = data;
1354 * Check, if the node is a phi
1355 * we then compute a set of conds which are reachable from this
1356 * phi's block up to its dominator.
1357 * The set is attached to the blocks link field.
1359 if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
1360 ir_node *block = get_nodes_block(irn);
1362 cond_info_t *ci = get_irn_link(block);
1364 /* If the set is not yet computed, do it now. */
1366 ci = obstack_alloc(cwi->obst, sizeof(*ci));
1367 ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
1368 ci->first_phi = irn;
1370 INIT_LIST_HEAD(&ci->roots);
1371 INIT_LIST_HEAD(&ci->list);
1374 * Add this cond info to the list of all cond infos
1375 * in this graph. This is just done to free the
1376 * set easier afterwards (we save an irg_walk_graph).
1378 list_add(&cwi->cond_info_head, &ci->list);
1380 DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
1383 * Fill the set with conds we find on the way from
1384 * the block to its dominator.
1386 find_conds(irn, ci);
1389 * If there where no suitable conds, delete the set
1390 * immediately and reset the set pointer to NULL
1392 if(set_count(ci->cond_set) == 0) {
1393 del_set(ci->cond_set);
1394 list_del(&ci->list);
1395 obstack_free(cwi->obst, ci);
1401 DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
1403 set_irn_link(block, ci);
1406 phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
1409 INIT_LIST_HEAD(&pi->list);
1410 list_add(&pi->list, &cwi->phi_head);
1416 static void dump_conds(cond_t *cond, void *env)
1421 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
1422 cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
1423 get_nodes_block(cond->cond));
1425 for(i = 0; i < 2; ++i)
1426 if(cond->cases[i].masked_by)
1427 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
1428 cond, cond->cases[i].masked_by, i);
1431 static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi)
1436 snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
1438 if((f = fopen(buf, "wt")) != NULL) {
1443 ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
1444 list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
1445 ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
1446 list_for_each_entry(cond_t, cond, &ci->roots, list) {
1447 walk_conds(cond, NULL, dump_conds, f);
1448 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
1452 list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
1453 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
1454 phi->irn, phi->irn, get_nodes_block(phi->irn));
1455 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
1461 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
1464 struct obstack obst;
1465 phi_info_t *phi_info;
1466 cond_info_t *cond_info;
1467 cond_walk_info_t cwi;
1469 opt_if_conv_info_t p;
1471 if(!get_opt_if_conversion())
1474 /* get the parameters */
1476 memcpy(&p, params, sizeof(p));
1478 memcpy(&p, &default_info, sizeof(p));
1481 p.allow_mux = default_info.allow_mux;
1483 obstack_init(&obst);
1486 INIT_LIST_HEAD(&cwi.cond_info_head);
1487 INIT_LIST_HEAD(&cwi.phi_head);
1489 /* Init the debug stuff. */
1490 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
1492 firm_dbg_set_mask(dbg, LEVEL_1|LEVEL_2|LEVEL_3);
1495 /* if-conversion works better with normalized returns */
1496 normalize_one_return(irg);
1498 /* Ensure, that the dominators are computed. */
1501 DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
1502 get_entity_name(get_irg_entity(irg)), irg));
1505 * Collect information about the conds pu the phis on an obstack.
1506 * It is important that phi nodes which are 'higher' (with a
1507 * lower dfs pre order) are in front of the obstack. Since they are
1508 * possibly turned in to muxes this can enable the optimization
1511 irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
1514 vcg_dump_conds(irg, &cwi);
1517 /* Process each suitable phi found. */
1518 list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
1519 DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
1520 muxes_made += check_out_phi(phi_info, &p);
1523 list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
1524 del_set(cond_info->cond_set);
1527 DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
1529 obstack_free(&obst, NULL);
1531 dump_ir_block_graph(irg, "_ifconv_hack");