2 * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * File name: ir/opt/ifconv.c
23 * Purpose: If conversion
24 * Author: Sebastian Hack.
27 * Copyright: (c) 1998-2005 Universität Karlsruhe
56 DEBUG_ONLY(firm_dbg_module_t *dbg);
58 /** allow every Psi to be created. */
59 static int default_allow_ifconv(ir_node *sel, ir_node* phi_list, int i, int j)
67 static const opt_if_conv_info_t default_info = {
68 0, /* doesn't matter for Psi */
73 * Additional block info.
75 typedef struct block_info {
76 ir_node *phi; /**< head of the Phi list */
77 int has_pinned; /**< set if the block contains instructions that cannot be moved */
80 #define get_block_blockinfo(block) ((block_info *)get_irn_link(block))
83 * Returns non-zero if a Block can be emptied.
85 static int can_empty_block(ir_node *block)
87 return !get_block_blockinfo(block)->has_pinned;
91 static ir_node* walk_to_projx(ir_node* start, const ir_node* dependency)
96 /* No need to find the conditional block if this block cannot be emptied and
99 if (!can_empty_block(start)) return NULL;
101 arity = get_irn_arity(start);
102 for (i = 0; i < arity; ++i) {
103 ir_node* pred = get_irn_n(start, i);
104 ir_node* pred_block = get_nodes_block(pred);
106 if (pred_block == dependency) {
108 assert(get_irn_mode(pred) == mode_X);
115 assert(get_irn_mode(pred) == mode_X);
119 if (is_cdep_on(pred_block, dependency)) {
120 return walk_to_projx(pred_block, dependency);
128 * Copies the DAG starting at node to the ith predecessor block of src_block
129 * -if the node isn't in the src_block, this is a nop and the node is returned
130 * -if the node is a phi in the src_block, the ith predecessor of the phi is
132 * otherwise returns the copy of the passed node
134 static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
141 if (get_nodes_block(node) != src_block) return node;
142 if (get_irn_op(node) == op_Phi) return get_irn_n(node, i);
144 copy = exact_copy(node);
145 dst_block = get_nodes_block(get_irn_n(src_block, i));
146 set_nodes_block(copy, dst_block);
148 DB((dbg, LEVEL_1, "Copying node %+F to block %+F, copy is %+F\n",
149 node, dst_block, copy));
151 arity = get_irn_arity(node);
152 for (j = 0; j < arity; ++j) {
153 set_irn_n(copy, j, copy_to(get_irn_n(node, j), src_block, i));
154 DB((dbg, LEVEL_2, "-- pred %d is %+F\n", j, get_irn_n(copy, j)));
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);
170 NEW_ARR_A(ir_node *, ins, arity - 1);
173 for (k = 0; k < i; ++k) ins[l++] = get_irn_n(node, k);
174 for (++k; k < j; ++k) ins[l++] = get_irn_n(node, k);
175 for (++k; k < arity; ++k) ins[l++] = get_irn_n(node, k);
177 assert(l == arity - 1);
178 set_irn_in(node, l, ins);
183 * Remove the jth predecessors from the ith predecessor of block and add it to block
185 static void split_block(ir_node* block, int i, int j)
187 ir_node* pred_block = get_nodes_block(get_irn_n(block, i));
188 int arity = get_irn_arity(block);
195 DB((dbg, LEVEL_1, "Splitting predecessor %d of predecessor %d of %+F\n", j, i, block));
197 NEW_ARR_A(ir_node*, ins, arity + 1);
199 for (phi = get_block_blockinfo(block)->phi; phi != NULL; phi = get_irn_link(phi)) {
200 ir_node* copy = copy_to(get_irn_n(phi, i), pred_block, j);
202 for (k = 0; k < i; ++k) ins[k] = get_irn_n(phi, k);
204 for (; k < arity; ++k) ins[k] = get_irn_n(phi, k);
205 ins[k] = get_irn_n(phi, i);
207 set_irn_in(phi, arity + 1, ins);
210 for (k = 0; k < i; ++k) ins[k] = get_irn_n(block, k);
211 ins[k++] = get_irn_n(pred_block, j);
212 for (; k < arity; ++k) ins[k] = get_irn_n(block, k);
213 ins[k] = get_irn_n(block, i);
215 set_irn_in(block, arity + 1, ins);
217 new_pred_arity = get_irn_arity(pred_block) - 1;
218 NEW_ARR_A(ir_node*, pred_ins, new_pred_arity);
220 for (phi = get_block_blockinfo(pred_block)->phi; phi != NULL; phi = get_irn_link(phi)) {
221 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(phi, k);
222 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(phi, k + 1);
223 assert(k == new_pred_arity);
224 if (new_pred_arity > 1) {
225 set_irn_in(phi, new_pred_arity, pred_ins);
227 exchange(phi, pred_ins[0]);
231 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(pred_block, k);
232 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(pred_block, k + 1);
233 assert(k == new_pred_arity);
234 if (new_pred_arity > 1) {
235 set_irn_in(pred_block, new_pred_arity, pred_ins);
237 exchange(pred_block, get_nodes_block(pred_ins[0]));
242 static void prepare_path(ir_node* block, int i, const ir_node* dependency)
244 ir_node* pred = get_nodes_block(get_irn_n(block, i));
248 DB((dbg, LEVEL_1, "Preparing predecessor %d of %+F\n", i, block));
250 pred_arity = get_irn_arity(pred);
251 for (j = 0; j < pred_arity; ++j) {
252 ir_node* pred_pred = get_nodes_block(get_irn_n(pred, j));
254 if (is_cdep_on(pred_pred, dependency)) {
255 prepare_path(pred, j, dependency);
256 split_block(block, i, j);
263 static void if_conv_walker(ir_node* block, void* env)
267 opt_if_conv_info_t *opt_info = env;
269 /* Bail out, if there are no Phis at all */
270 if (get_block_blockinfo(block)->phi == NULL) return;
273 arity = get_irn_arity(block);
274 for (i = 0; i < arity; ++i) {
278 pred = get_nodes_block(get_irn_n(block, i));
279 for (cdep = find_cdep(pred); cdep != NULL; cdep = cdep->next) {
280 const ir_node* dependency = cdep->node;
281 ir_node* projx0 = walk_to_projx(pred, dependency);
285 if (projx0 == NULL) continue;
287 cond = get_Proj_pred(projx0);
288 if (get_irn_op(cond) != op_Cond) continue;
290 /* We only handle boolean decisions, no switches */
291 if (get_irn_mode(get_Cond_selector(cond)) != mode_b) continue;
293 for (j = i + 1; j < arity; ++j) {
301 pred = get_nodes_block(get_irn_n(block, j));
303 if (!is_cdep_on(pred, dependency)) continue;
305 projx1 = walk_to_projx(pred, dependency);
307 if (projx1 == NULL) continue;
309 phi = get_block_blockinfo(block)->phi;
310 if (!opt_info->allow_ifconv(get_Cond_selector(cond), phi, i, j)) continue;
312 DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n",
316 prepare_path(block, i, dependency);
317 prepare_path(block, j, dependency);
318 arity = get_irn_arity(block);
320 conds[0] = get_Cond_selector(cond);
322 psi_block = get_nodes_block(cond);
324 ir_node* val_i = get_irn_n(phi, i);
325 ir_node* val_j = get_irn_n(phi, j);
327 if (val_i == val_j) {
329 DB((dbg, LEVEL_2, "Generating no psi, because both values are equal\n"));
331 /* Something is very fishy if two predecessors of a PhiM point into
332 * one block, but not at the same memory node
334 assert(get_irn_mode(phi) != mode_M);
335 if (get_Proj_proj(projx0) == pn_Cond_true) {
344 current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
346 DB((dbg, LEVEL_2, "Generating %+F for %+F\n", psi, phi));
349 /* only exchange if we have a Psi */
353 rewire(phi, i, j, psi);
356 phi = get_irn_link(phi);
357 } while (phi != NULL);
359 exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
360 exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
364 DB((dbg, LEVEL_1, "Welding block %+F and %+F\n", block, psi_block));
365 /* copy the block-info from the Psi-block to the block before merging */
366 get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
367 set_irn_link(block, get_irn_link(psi_block));
369 set_irn_in(block, get_irn_arity(psi_block), get_irn_in(psi_block) + 1);
370 exchange_cdep(psi_block, block);
371 exchange(psi_block, block);
373 DB((dbg, LEVEL_1, "Welding block %+F to %+F\n", block, psi_block));
374 get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
375 exchange(block, psi_block);
379 rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block));
388 * Block walker: add additional data
390 static void init_block_link(ir_node *block, void *env)
392 struct obstack *obst = env;
393 block_info *bi = obstack_alloc(obst, sizeof(*bi));
397 set_irn_link(block, bi);
402 * Daisy-chain all phis in a block
403 * If a non-movable node is encountered set the has_pinned flag
405 static void collect_phis(ir_node *node, void *env)
408 ir_node *block = get_nodes_block(node);
409 block_info *bi = get_block_blockinfo(block);
411 set_irn_link(node, bi->phi);
415 if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
417 * Ignore control flow nodes, these will be removed.
418 * This ignores Raise. That is surely bad. FIXME.
420 if (! is_cfop(node)) {
421 ir_node *block = get_nodes_block(node);
422 block_info *bi = get_block_blockinfo(block);
424 DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
433 * Transform multiple cascaded Psis into one Psi
435 static ir_node* fold_psi(ir_node* psi)
437 int arity = get_Psi_n_conds(psi);
448 for (i = 0; i < arity; ++i) {
449 n = get_Psi_val(psi, i);
450 if (get_irn_op(n) == op_Psi) {
451 new_arity += get_Psi_n_conds(n) + 1;
456 n = get_Psi_default(psi);
457 if (get_irn_op(n) == op_Psi) {
458 new_arity += get_Psi_n_conds(n);
461 if (arity == new_arity) return psi; // no attached Psis found
462 DB((dbg, LEVEL_1, "Folding %+F from %d to %d conds\n", psi, arity, new_arity));
464 NEW_ARR_A(ir_node *, conds, new_arity);
465 NEW_ARR_A(ir_node *, vals, new_arity + 1);
467 for (i = 0; i < arity; ++i) {
468 ir_node* c = get_Psi_cond(psi, i);
470 n = get_Psi_val(psi, i);
471 if (get_irn_op(n) == op_Psi) {
472 a = get_Psi_n_conds(n);
473 for (k = 0; k < a; ++k) {
474 conds[j] = new_r_And(
475 current_ir_graph, get_nodes_block(psi),
476 c, get_Psi_cond(n, k), mode_b
478 vals[j] = get_Psi_val(n, k);
482 vals[j] = get_Psi_default(n);
489 n = get_Psi_default(psi);
490 if (get_irn_op(n) == op_Psi) {
491 a = get_Psi_n_conds(n);
492 for (k = 0; k < a; ++k) {
493 conds[j] = get_Psi_cond(n, k);
494 vals[j] = get_Psi_val(n, k);
497 vals[j] = get_Psi_default(n);
501 assert(j == new_arity);
503 current_ir_graph, get_nodes_block(psi),
504 new_arity, conds, vals, get_irn_mode(psi)
506 DB((dbg, LEVEL_1, "Folded %+F into new %+F\n", psi, new_psi));
507 exchange(psi, new_psi);
513 * Merge consecutive psi inputs if the data inputs are the same
515 static ir_node* meld_psi(ir_node* psi)
517 int arity = get_Psi_n_conds(psi);
528 val = get_Psi_val(psi, 0);
529 DB((dbg, LEVEL_1, "Pred 0 of %+F is %+F\n", psi, val));
530 for (i = 1; i < arity; ++i) {
531 ir_node* v = get_Psi_val(psi, i);
532 DB((dbg, LEVEL_1, "Pred %2d of %+F is %+F\n", i, psi, v));
538 DB((dbg, LEVEL_1, "Default of %+F is %+F\n", psi, get_Psi_default(psi)));
539 if (val == get_Psi_default(psi)) --new_arity;
541 DB((dbg, LEVEL_1, "Melding Psi %+F from %d conds to %d\n", psi, arity, new_arity));
543 if (new_arity == arity) return psi;
545 /* If all data inputs of the Psi are equal, exchange the Psi with that value */
546 if (new_arity == 0) {
551 NEW_ARR_A(ir_node *, conds, new_arity);
552 NEW_ARR_A(ir_node *, vals, new_arity + 1);
553 cond = get_Psi_cond(psi, 0);
554 val = get_Psi_val(psi, 0);
556 for (i = 1; i < arity; ++i) {
557 ir_node* v = get_Psi_val(psi, i);
561 current_ir_graph, get_nodes_block(psi),
562 cond, get_Psi_cond(psi, i), mode_b
571 if (val != get_Psi_default(psi)) {
576 vals[j] = get_Psi_default(psi);
577 assert(j == new_arity);
579 current_ir_graph, get_nodes_block(psi),
580 new_arity, conds, vals, get_irn_mode(psi)
582 DB((dbg, LEVEL_1, "Molded %+F into %+F\n", psi, new_psi));
583 exchange(psi, new_psi);
589 * Split a Psi with multiple conditions into multiple Psis with one condtition
592 static ir_node* split_psi(ir_node* psi)
594 int arity = get_Psi_n_conds(psi);
600 if (arity == 1) return psi;
602 mode = get_irn_mode(psi);
603 block = get_nodes_block(psi);
604 rval = get_Psi_default(psi);
605 for (i = arity - 1; i >= 0; --i) {
609 conds[0] = get_Psi_cond(psi, i);
610 vals[0] = get_Psi_val(psi, i);
613 current_ir_graph, block, 1, conds, vals, mode
621 static void optimise_psis(ir_node* node, void* env)
623 if (get_irn_op(node) != op_Psi) return;
625 node = fold_psi(node);
628 node = meld_psi(node);
631 node = split_psi(node);
636 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
639 opt_if_conv_info_t p;
641 if (! get_opt_if_conversion())
644 /* get the parameters */
646 memcpy(&p, params, sizeof(p));
648 memcpy(&p, &default_info, sizeof(p));
650 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
652 DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
654 normalize_one_return(irg);
655 remove_critical_cf_edges(irg);
661 irg_block_walk_graph(irg, init_block_link, NULL, &obst);
662 irg_walk_graph(irg, collect_phis, NULL, NULL);
663 irg_block_walk_graph(irg, NULL, if_conv_walker, &p);
665 local_optimize_graph(irg);
667 irg_walk_graph(irg, NULL, optimise_psis, NULL);
669 obstack_free(&obst, NULL);
680 * Make Mux nodes from Conds where it its possible.
681 * @author Sebastian Hack
698 #include "irgraph_t.h"
699 #include "irnode_t.h"
703 #include "irmode_t.h"
704 #include "ircons_t.h"
709 #include "irflag_t.h"
711 #include "irprintf.h"
716 #include "bitfiddle.h"
723 * check, if a node is const and return its tarval or
724 * return a default tarval.
725 * @param cnst The node whose tarval to get.
726 * @param or The alternative tarval, if the node is no Const.
727 * @return The tarval of @p cnst, if the node is Const, @p otherwise.
729 static tarval *get_value_or(ir_node *cnst, tarval *or)
731 return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
736 * Try to optimize nested muxes into a dis- or conjunction
738 * @param mux The parent mux, which has muxes as operands.
739 * @return The replacement node for this mux. If the optimization is
740 * successful, this might be an And or Or node, if not, its the mux
743 static ir_node *optimize_mux_chain(ir_node *mux)
748 ir_mode *mode = get_irn_mode(mux);
753 * If we have no mux, or its mode is not integer, we
756 if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
760 null = get_mode_null(mode);
761 minus_one = tarval_sub(null, get_tarval_one(mode));
763 ops[0] = get_Mux_false(mux);
764 ops[1] = get_Mux_true(mux);
766 for(i = 0; i < 2; ++i) {
768 tarval *tva, *tvb, *tvd;
772 * A mux operand at the first position can be factored
773 * out, if the operands fulfill several conditions:
775 * mux(c1, mux(c2, a, b), d)
777 * This can be made into:
778 * 1) mux(c1, 0, d) | mux(c2, a, b)
779 * if a | d == d and b | d == d
781 * 2) mux(c1, -1, d) & mux(c2, a, b)
782 * if a & d == d and a & b == b
784 if(get_irn_op(ops[i]) == op_Mux) {
787 a = get_Mux_false(child_mux);
788 b = get_Mux_true(child_mux);
791 /* Try the or stuff */
792 tva = get_value_or(a, minus_one);
793 tvb = get_value_or(b, minus_one);
794 tvd = get_value_or(d, null);
796 if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
797 && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
799 ops[i] = new_Const(mode, null);
800 res = new_r_Or(current_ir_graph, get_nodes_block(mux),
801 mux, child_mux, mode);
805 /* If the or didn't go, try the and stuff */
806 tva = get_value_or(a, null);
807 tvb = get_value_or(b, null);
808 tvd = get_value_or(d, minus_one);
810 if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
811 && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
813 ops[i] = new_Const(mode, minus_one);
814 res = new_r_And(current_ir_graph, get_nodes_block(mux),
815 mux, child_mux, mode);
821 /* recursively optimize nested muxes. */
822 set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
823 set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
829 /***********************************************************
830 * The If conversion itself.
831 ***********************************************************/
833 /** allow every Mux to be created. */
834 static int default_allow_mux(ir_node *sel, ir_node *false_res, ir_node *true_res) {
841 static const opt_if_conv_info_t default_info = {
846 /** The debugging module. */
847 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
850 * A simple check for side effects upto an opcode of a ir node.
851 * @param irn The ir node to check,
852 * @return 1 if the opcode itself may produce side effects, 0 if not.
854 static INLINE int has_side_effects(const ir_node *irn)
856 ir_op *op = get_irn_op(irn);
861 return !mode_is_datab(get_irn_mode(irn));
865 * Possible failure reasons
867 enum failure_reason_t {
868 SUCCESS = IF_RESULT_SUCCESS,
869 TO_DEEP = IF_RESULT_TOO_DEEP,
870 SIDE_EFFECTS = IF_RESULT_SIDE_EFFECT,
871 PHI_FOUND = IF_RESULT_SIDE_EFFECT_PHI,
872 DENIED = IF_RESULT_DENIED
876 * Decides, if a given expression and its subexpressions
877 * (to certain, also given extent) can be moved to a block.
879 * @param expr The expression to examine.
880 * @param block The block where the expression should go.
881 * @param depth The current depth, passed recursively. Use 0 for
882 * non-recursive calls.
883 * @param info The options for createing Mux nodes.
886 * @return a failure reason
888 static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, const opt_if_conv_info_t *info)
892 ir_node *expr_block = get_nodes_block(expr);
895 * If we are forced to look too deep into the expression,
896 * treat it like it could not be moved.
898 if(depth >= info->max_depth) {
904 * If the block of the expression dominates the specified
905 * destination block, it does not matter if the expression
906 * has side effects or anything else. It is executed on each
907 * path the destination block is reached.
909 if (block_dominates(expr_block, dest_block))
913 * We cannot move phis!
921 * This should be superfluous and could be converted into a assertion.
922 * The destination block _must_ dominate the block of the expression,
923 * else the expression could be used without its definition.
925 if (! block_dominates(dest_block, expr_block)) {
926 res = IF_RESULT_SIDE_EFFECT;
931 * Surely, if the expression does not have a data mode, it is not
932 * movable. Perhaps one should also test the floating property of
935 if (has_side_effects(expr)) {
936 res = IF_RESULT_SIDE_EFFECT;
941 * If the node looks alright so far, look at its operands and
942 * check them out. If one of them cannot be moved, this one
943 * cannot be moved either.
945 for (i = 0, n = get_irn_arity(expr); i < n; ++i) {
946 ir_node *op = get_irn_n(expr, i);
947 int new_depth = is_Proj(op) ? depth : depth + 1;
949 res = _can_move_to(op, dest_block, new_depth, info);
956 DBG((dbg, LEVEL_3, "\t\t\tcan move to %n: %d\n", expr, res));
962 * Convenience function for _can_move_to.
963 * Checks, if an expression can be moved to another block. The check can
964 * be limited to a expression depth meaning if we need to crawl in
965 * deeper into an expression than a given threshold to examine if
966 * it can be moved, the expression is rejected and the test returns
969 * @param expr The expression to check for.
970 * @param dest_block The destination block you want @p expr to be.
971 * @param info The options for createing Mux nodes.
973 * @return return a failure reason
975 static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, const opt_if_conv_info_t *info)
977 return _can_move_to(expr, dest_block, 0, info);
981 * move a DAG given by a root node expr into a new block
983 * @param expr the root of a dag
984 * @param dest_block the destination block
986 static void move_to(ir_node *expr, ir_node *dest_block)
989 ir_node *expr_block = get_nodes_block(expr);
992 * If we reached the dominator, we are done.
993 * We will never put code through the dominator
995 if (block_dominates(expr_block, dest_block))
998 for (i = 0, n = get_irn_arity(expr); i < n; ++i)
999 move_to(get_irn_n(expr, i), dest_block);
1001 set_nodes_block(expr, dest_block);
1005 * return the common dominator of two blocks
1007 static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2)
1009 if(block_dominates(b1, b2))
1011 else if(block_dominates(b2, b1))
1016 for (p = get_Block_idom(b1); !block_dominates(p, b2); p = get_Block_idom(p));
1022 * Information about a cond node.
1024 typedef struct _cond_t {
1025 ir_node *cond; /**< The cond node. */
1026 struct list_head list; /**< List head which is used for queuing this cond
1027 into the cond bunch it belongs to. */
1028 unsigned is_new : 1;
1029 unsigned totally_covers : 1;
1030 struct _cond_t *link;
1034 * Information about the both 'branches'
1035 * (true and false), the cond creates.
1038 int pos; /**< Number of the predecessor of the
1039 phi block by which this branch is
1040 reached. It is -1, if this branch is
1041 only reached through another cond. */
1043 struct _cond_t *masked_by; /**< If this cond's branch is only reached
1044 through another cond, we store this
1045 cond ir_node here. */
1050 * retrieve the conditional information from a Cond node
1052 static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
1057 return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
1061 typedef void (cond_walker_t)(cond_t *cond, void *env);
1063 static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
1064 long visited_nr, void *env)
1068 if(cond->visited_nr >= visited_nr)
1071 cond->visited_nr = visited_nr;
1076 for(i = 0; i < 2; ++i) {
1077 cond_t *c = cond->cases[i].masked_by;
1080 _walk_conds(c, pre, post, visited_nr, env);
1087 static long cond_visited_nr = 0;
1089 static void walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post, void *env)
1091 _walk_conds(cond, pre, post, ++cond_visited_nr, env);
1094 static void link_conds(cond_t *cond, void *env)
1096 cond_t **ptr = (cond_t **) env;
1103 * Compare two conds for use in a firm set.
1104 * Two cond_t's are equal, if they designate the same cond node.
1105 * @param a A cond_t.
1106 * @param b Another one.
1107 * @param size Not used.
1108 * @return 0 (!) if they are equal, != 0 otherwise.
1110 static int cond_cmp(const void *a, const void *b, size_t size)
1112 const cond_t *x = a;
1113 const cond_t *y = b;
1114 return x->cond != y->cond;
1118 * Information about conds which can be made to muxes.
1119 * Instances of this struct are attached to the link field of
1120 * blocks in which phis are located.
1122 typedef struct _cond_info_t {
1123 struct list_head list; /**< Used to list all of these structs per class. */
1125 struct list_head roots; /**< A list of non-depending Conds. Two Conds are
1126 independent, if it's not possible not reach one from the
1127 other (all Conds in this list have to dominate the
1128 block this struct is attached to). */
1130 ir_node *first_phi; /**< The first phi node this cond info was made for. */
1131 set *cond_set; /**< A set of all dominating reachable Conds. */
1137 static void _find_conds(ir_node *irn, unsigned long visited_nr,
1138 ir_node *dominator, cond_t *masked_by, int pos, int depth, cond_info_t *ci)
1141 int saw_select_cond = 0;
1143 block = get_nodes_block(irn);
1146 * Only check this block if it is dominated by the specified
1147 * dominator or it has not been visited yet.
1149 if (block_dominates(dominator, block) && get_Block_block_visited(block) < visited_nr) {
1150 cond_t *res = masked_by;
1153 /* check, if we're on a ProjX
1155 * Further, the ProjX/Cond block must dominate the base block
1156 * (the block with the phi in it), otherwise, the Cond
1157 * is not affecting the phi so that a mux can be inserted.
1159 if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
1161 int proj = get_Proj_proj(irn);
1162 ir_node *cond = get_Proj_pred(irn);
1164 /* true, if the mode is a mode_b cond _NO_ switch cond */
1165 int is_modeb_cond = get_irn_opcode(cond) == iro_Cond
1166 && get_irn_mode(get_Cond_selector(cond)) == mode_b;
1168 saw_select_cond = !is_modeb_cond;
1170 /* Check, if the pred of the proj is a Cond
1171 * with a Projb as selector.
1176 memset(&c, 0, sizeof(c));
1179 c.cases[0].pos = -1;
1180 c.cases[1].pos = -1;
1182 /* get or insert the cond info into the set. */
1183 res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
1186 * If this cond is already masked by the masked_by cond
1187 * return immediately, since we don't have anything to add.
1189 if(masked_by && res->cases[proj].masked_by == masked_by)
1194 list_add(&res->list, &ci->roots);
1198 * Set masked by (either NULL or another cond node.
1199 * If this cond is truly masked by another one, set
1200 * the position of the actually investigated branch
1201 * to -1. Since the cond is masked by another one,
1202 * there could be more ways from the start block
1203 * to this branch, so we choose -1.
1205 res->cases[proj].masked_by = masked_by;
1208 res->cases[proj].pos = pos;
1211 * Since the masked_by nodes masks a cond, remove it from the
1212 * root list of the conf trees.
1215 assert(res->cases[proj].pos < 0);
1216 list_del_init(&masked_by->list);
1219 DBG((dbg, LEVEL_2, "%n (%s branch) "
1220 "for pos %d in block %n reached by %n\n",
1221 cond, proj ? "true" : "false", pos,
1222 block, masked_by ? masked_by->cond : NULL));
1226 if(get_Block_block_visited(block) < visited_nr && !saw_select_cond) {
1228 set_Block_block_visited(block, visited_nr);
1230 /* Search recursively from this cond. */
1231 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1232 ir_node *pred = get_irn_n(block, i);
1235 * If the depth is 0 (the first recursion), we set the pos to
1236 * the current viewed predecessor, else we adopt the position
1237 * as given by the caller. We also increase the depth for the
1238 * recursively called functions.
1240 _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci);
1248 * A convenience function for _find_conds.
1249 * It sets some parameters needed for recursion to appropriate start
1250 * values. Always use this function.
1252 * @param irn The node to start looking for Conds from. This might
1253 * be the phi node we are investigating.
1254 * @param conds The set to record the found Conds in.
1256 static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
1259 unsigned long visited_nr;
1260 ir_node *block = get_nodes_block(irn);
1261 ir_node *dom = get_Block_idom(block);
1263 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1264 ir_node *pred = get_irn_n(block, i);
1266 inc_irg_block_visited(current_ir_graph);
1267 visited_nr = get_irg_block_visited(current_ir_graph);
1268 set_Block_block_visited(block, visited_nr);
1270 DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
1271 _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
1276 * Make the mux for a given cond.
1278 * @param phi The phi node which shall be replaced by a mux.
1279 * @param dom The block where the muxes shall be placed.
1280 * @param cond The cond information.
1281 * @param info The options for createing Mux nodes.
1282 * @return The mux node made for this cond.
1284 static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond,
1285 const opt_if_conv_info_t *info, ir_node **mux, bitset_t *positions,
1286 int *muxes_made, long visited_nr)
1289 ir_node *projb = get_Cond_selector(cond->cond);
1290 ir_node *bl = get_nodes_block(cond->cond);
1291 ir_node *operands[2];
1294 cond->visited_nr = visited_nr;
1295 DBG((dbg, LEVEL_2, "%n\n", cond->cond));
1296 for(i = 0; i < 2; ++i) {
1297 cond_t *masked_by = cond->cases[i].masked_by;
1298 int pos = cond->cases[i].pos;
1304 * If this Cond branch is masked by another cond, make the mux
1305 * for that Cond first, since the Mux for this cond takes
1310 DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
1311 if(masked_by->visited_nr < visited_nr)
1312 operands[i] = make_mux_on_demand(phi, dom, masked_by, info, mux, positions, muxes_made, visited_nr);
1316 * If this cond branch is not masked by another cond, take
1317 * the corresponding phi operand as an operand to the mux.
1320 operands[i] = get_irn_n(phi, pos);
1326 * Move the operands to the dominator block if the cond
1327 * made sense. Some Conds found are not suitable for making a mux
1328 * out of them, since one of their branches cannot be reached from
1329 * the phi block. In that case we do not make a mux and return NULL.
1331 if(operands[0] && operands[1]) {
1332 if (operands[0] == operands[1]) {
1333 /* there is no gain in using mux in this case, as
1334 it will be optimized away. We will NOT move the
1335 content of the blocks either
1337 for (i = 0; i < 2; ++i)
1339 bitset_set(positions, set[i]);
1345 can_move[0] = can_move_to(operands[0], bl, info);
1346 can_move[1] = can_move_to(operands[1], bl, info);
1348 if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) {
1349 if (info->allow_mux(projb, operands[0], operands[1])) {
1350 move_to(operands[0], bl);
1351 move_to(operands[1], bl);
1354 *mux = new_r_Mux(current_ir_graph, bl, projb,
1355 operands[0], operands[1], get_irn_mode(operands[0]));
1359 DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
1360 *mux, projb, operands[0], operands[1], set[0], set[1]));
1362 for(i = 0; i < 2; ++i)
1364 bitset_set(positions, set[i]);
1366 /* we have done one */
1367 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_SUCCESS);
1371 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_DENIED);
1375 if(can_move[0] != SUCCESS)
1376 hook_if_conversion(current_ir_graph, phi, set[0], NULL, can_move[0]);
1377 if(can_move[1] != SUCCESS)
1378 hook_if_conversion(current_ir_graph, phi, set[1], NULL, can_move[1]);
1383 hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF);
1385 hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF);
1391 typedef struct _phi_info_t {
1392 struct list_head list;
1393 cond_info_t *cond_info;
1399 * Examine a phi node if it can be replaced by some muxes.
1400 * @param irn A phi node.
1401 * @param info Parameters for the if conversion algorithm.
1403 static int check_out_phi(phi_info_t *phi_info, const opt_if_conv_info_t *info)
1405 ir_node *irn = phi_info->irn;
1406 ir_node *block, *nw;
1407 cond_info_t *cond_info = phi_info->cond_info;
1411 bitset_t *positions;
1413 block = get_nodes_block(irn);
1414 arity = get_irn_arity(irn);
1415 positions = bitset_alloca(arity);
1417 assert(is_Phi(irn));
1418 assert(get_irn_arity(irn) == get_irn_arity(block));
1421 DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
1423 list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
1424 ir_node *cidom = block;
1425 ir_node *mux = NULL;
1426 cond_t *p, *head = NULL;
1429 bitset_clear_all(positions);
1431 DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
1433 * Link all conds which are in the subtree of
1434 * the current cond in the list together.
1436 walk_conds(cond, link_conds, NULL, &head);
1439 for(p = head; p; p = p->link) {
1440 for(i = 0; i < 2; ++i) {
1441 int pos = p->cases[i].pos;
1443 cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
1447 DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
1448 make_mux_on_demand(irn, cidom, cond, info, &mux, positions, &muxes_made, ++cond_visited_nr);
1451 bitset_foreach(positions, pos)
1452 set_irn_n(irn, (int) pos, mux);
1457 * optimize the phi away. This can anable further runs of this
1458 * function. Look at _can_move. phis cannot be moved there.
1460 nw = optimize_in_place_2(irn);
1467 typedef struct _cond_walk_info_t {
1468 struct obstack *obst;
1469 struct list_head cond_info_head;
1470 struct list_head phi_head;
1474 static void annotate_cond_info_pre(ir_node *irn, void *data)
1476 set_irn_link(irn, NULL);
1479 static void annotate_cond_info_post(ir_node *irn, void *data)
1481 cond_walk_info_t *cwi = data;
1484 * Check, if the node is a phi
1485 * we then compute a set of conds which are reachable from this
1486 * phi's block up to its dominator.
1487 * The set is attached to the blocks link field.
1489 if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
1490 ir_node *block = get_nodes_block(irn);
1492 cond_info_t *ci = get_irn_link(block);
1494 /* If the set is not yet computed, do it now. */
1496 ci = obstack_alloc(cwi->obst, sizeof(*ci));
1497 ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
1498 ci->first_phi = irn;
1500 INIT_LIST_HEAD(&ci->roots);
1501 INIT_LIST_HEAD(&ci->list);
1504 * Add this cond info to the list of all cond infos
1505 * in this graph. This is just done to xfree the
1506 * set easier afterwards (we save an irg_walk_graph).
1508 list_add(&cwi->cond_info_head, &ci->list);
1510 DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
1513 * Fill the set with conds we find on the way from
1514 * the block to its dominator.
1516 find_conds(irn, ci);
1519 * If there where no suitable conds, delete the set
1520 * immediately and reset the set pointer to NULL
1522 if(set_count(ci->cond_set) == 0) {
1523 del_set(ci->cond_set);
1524 list_del(&ci->list);
1525 obstack_free(cwi->obst, ci);
1531 DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
1533 set_irn_link(block, ci);
1536 phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
1539 INIT_LIST_HEAD(&pi->list);
1540 list_add(&pi->list, &cwi->phi_head);
1546 static void dump_conds(cond_t *cond, void *env)
1551 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
1552 cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
1553 get_nodes_block(cond->cond));
1555 for(i = 0; i < 2; ++i)
1556 if(cond->cases[i].masked_by)
1557 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
1558 cond, cond->cases[i].masked_by, i);
1561 static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi)
1566 snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
1568 if((f = fopen(buf, "wt")) != NULL) {
1573 ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
1574 list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
1575 ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
1576 list_for_each_entry(cond_t, cond, &ci->roots, list) {
1577 walk_conds(cond, NULL, dump_conds, f);
1578 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
1582 list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
1583 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
1584 phi->irn, phi->irn, get_nodes_block(phi->irn));
1585 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
1591 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
1594 struct obstack obst;
1595 phi_info_t *phi_info;
1596 cond_info_t *cond_info;
1597 cond_walk_info_t cwi;
1599 opt_if_conv_info_t p;
1601 if(!get_opt_if_conversion())
1604 /* get the parameters */
1606 memcpy(&p, params, sizeof(p));
1608 memcpy(&p, &default_info, sizeof(p));
1611 p.allow_mux = default_info.allow_mux;
1613 obstack_init(&obst);
1616 INIT_LIST_HEAD(&cwi.cond_info_head);
1617 INIT_LIST_HEAD(&cwi.phi_head);
1619 /* Init the debug stuff. */
1620 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
1622 firm_dbg_set_mask(dbg, LEVEL_1|LEVEL_2|LEVEL_3);
1625 /* if-conversion works better with normalized returns */
1626 normalize_one_return(irg);
1628 /* Ensure, that the dominators are computed. */
1631 DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
1632 get_entity_name(get_irg_entity(irg)), irg));
1635 * Collect information about the conds pu the phis on an obstack.
1636 * It is important that phi nodes which are 'higher' (with a
1637 * lower dfs pre order) are in front of the obstack. Since they are
1638 * possibly turned in to muxes this can enable the optimization
1641 irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
1644 vcg_dump_conds(irg, &cwi);
1647 /* Process each suitable phi found. */
1648 list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
1649 DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
1650 muxes_made += check_out_phi(phi_info, &p);
1653 list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
1654 del_set(cond_info->cond_set);
1657 DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
1659 obstack_free(&obst, NULL);