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.
38 DEBUG_ONLY(firm_dbg_module_t *dbg);
40 /** allow every Psi to be created. */
41 static int default_allow_ifconv(ir_node *sel, ir_node* phi_list, int i, int j)
49 static const opt_if_conv_info_t default_info = {
50 0, /* doesn't matter for Psi */
55 * Additional block info.
57 typedef struct block_info {
58 ir_node *phi; /**< head of the Phi list */
59 int has_pinned; /**< set if the block contains instructions that cannot be moved */
62 #define get_block_blockinfo(block) ((block_info *)get_irn_link(block))
65 * Returns non-zero if a Block can be emptied.
67 static int can_empty_block(ir_node *block)
69 return !get_block_blockinfo(block)->has_pinned;
73 static ir_node* walk_to_projx(ir_node* start, const ir_node* dependency)
78 /* No need to find the conditional block if this block cannot be emptied and
81 if (!can_empty_block(start)) return NULL;
83 arity = get_irn_arity(start);
84 for (i = 0; i < arity; ++i) {
85 ir_node* pred = get_irn_n(start, i);
86 ir_node* pred_block = get_nodes_block(pred);
88 if (pred_block == dependency) {
90 assert(get_irn_mode(pred) == mode_X);
97 assert(get_irn_mode(pred) == mode_X);
101 if (is_cdep_on(pred_block, dependency)) {
102 return walk_to_projx(pred_block, dependency);
110 * Copies the DAG starting at node to the ith predecessor block of src_block
111 * -if the node isn't in the src_block, this is a nop and the node is returned
112 * -if the node is a phi in the src_block, the ith predecessor of the phi is
114 * otherwise returns the copy of the passed node
116 static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
123 if (get_nodes_block(node) != src_block) return node;
124 if (get_irn_op(node) == op_Phi) return get_irn_n(node, i);
126 copy = exact_copy(node);
127 dst_block = get_nodes_block(get_irn_n(src_block, i));
128 set_nodes_block(copy, dst_block);
130 DB((dbg, LEVEL_1, "Copying node %+F to block %+F, copy is %+F\n",
131 node, dst_block, copy));
133 arity = get_irn_arity(node);
134 for (j = 0; j < arity; ++j) {
135 set_irn_n(copy, j, copy_to(get_irn_n(node, j), src_block, i));
136 DB((dbg, LEVEL_2, "-- pred %d is %+F\n", j, get_irn_n(copy, j)));
143 * Remove predecessors i and j from node and add predecessor new_pred
145 static void rewire(ir_node* node, int i, int j, ir_node* new_pred)
147 int arity = get_irn_arity(node);
152 NEW_ARR_A(ir_node *, ins, arity - 1);
155 for (k = 0; k < i; ++k) ins[l++] = get_irn_n(node, k);
156 for (++k; k < j; ++k) ins[l++] = get_irn_n(node, k);
157 for (++k; k < arity; ++k) ins[l++] = get_irn_n(node, k);
159 assert(l == arity - 1);
160 set_irn_in(node, l, ins);
165 * Remove the jth predecessors from the ith predecessor of block and add it to block
167 static void split_block(ir_node* block, int i, int j)
169 ir_node* pred_block = get_nodes_block(get_irn_n(block, i));
170 int arity = get_irn_arity(block);
177 DB((dbg, LEVEL_1, "Splitting predecessor %d of predecessor %d of %+F\n", j, i, block));
179 NEW_ARR_A(ir_node*, ins, arity + 1);
181 for (phi = get_block_blockinfo(block)->phi; phi != NULL; phi = get_irn_link(phi)) {
182 ir_node* copy = copy_to(get_irn_n(phi, i), pred_block, j);
184 for (k = 0; k < i; ++k) ins[k] = get_irn_n(phi, k);
186 for (; k < arity; ++k) ins[k] = get_irn_n(phi, k);
187 ins[k] = get_irn_n(phi, i);
189 set_irn_in(phi, arity + 1, ins);
192 for (k = 0; k < i; ++k) ins[k] = get_irn_n(block, k);
193 ins[k++] = get_irn_n(pred_block, j);
194 for (; k < arity; ++k) ins[k] = get_irn_n(block, k);
195 ins[k] = get_irn_n(block, i);
197 set_irn_in(block, arity + 1, ins);
199 new_pred_arity = get_irn_arity(pred_block) - 1;
200 NEW_ARR_A(ir_node*, pred_ins, new_pred_arity);
202 for (phi = get_block_blockinfo(pred_block)->phi; phi != NULL; phi = get_irn_link(phi)) {
203 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(phi, k);
204 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(phi, k + 1);
205 assert(k == new_pred_arity);
206 if (new_pred_arity > 1) {
207 set_irn_in(phi, new_pred_arity, pred_ins);
209 exchange(phi, pred_ins[0]);
213 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(pred_block, k);
214 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(pred_block, k + 1);
215 assert(k == new_pred_arity);
216 if (new_pred_arity > 1) {
217 set_irn_in(pred_block, new_pred_arity, pred_ins);
219 exchange(pred_block, get_nodes_block(pred_ins[0]));
224 static void prepare_path(ir_node* block, int i, const ir_node* dependency)
226 ir_node* pred = get_nodes_block(get_irn_n(block, i));
230 DB((dbg, LEVEL_1, "Preparing predecessor %d of %+F\n", i, block));
232 pred_arity = get_irn_arity(pred);
233 for (j = 0; j < pred_arity; ++j) {
234 ir_node* pred_pred = get_nodes_block(get_irn_n(pred, j));
236 if (is_cdep_on(pred_pred, dependency)) {
237 prepare_path(pred, j, dependency);
238 split_block(block, i, j);
245 static void if_conv_walker(ir_node* block, void* env)
249 opt_if_conv_info_t *opt_info = env;
251 /* Bail out, if there are no Phis at all */
252 if (get_block_blockinfo(block)->phi == NULL) return;
255 arity = get_irn_arity(block);
256 for (i = 0; i < arity; ++i) {
260 pred = get_nodes_block(get_irn_n(block, i));
261 for (cdep = find_cdep(pred); cdep != NULL; cdep = cdep->next) {
262 const ir_node* dependency = cdep->node;
263 ir_node* projx0 = walk_to_projx(pred, dependency);
267 if (projx0 == NULL) continue;
269 cond = get_Proj_pred(projx0);
270 if (get_irn_op(cond) != op_Cond) continue;
272 /* We only handle boolean decisions, no switches */
273 if (get_irn_mode(get_Cond_selector(cond)) != mode_b) continue;
275 for (j = i + 1; j < arity; ++j) {
283 pred = get_nodes_block(get_irn_n(block, j));
285 if (!is_cdep_on(pred, dependency)) continue;
287 projx1 = walk_to_projx(pred, dependency);
289 if (projx1 == NULL) continue;
291 phi = get_block_blockinfo(block)->phi;
292 if (!opt_info->allow_ifconv(get_Cond_selector(cond), phi, i, j)) continue;
294 DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n",
298 prepare_path(block, i, dependency);
299 prepare_path(block, j, dependency);
300 arity = get_irn_arity(block);
302 conds[0] = get_Cond_selector(cond);
304 psi_block = get_nodes_block(cond);
306 ir_node* val_i = get_irn_n(phi, i);
307 ir_node* val_j = get_irn_n(phi, j);
309 if (val_i == val_j) {
311 DB((dbg, LEVEL_2, "Generating no psi, because both values are equal\n"));
313 /* Something is very fishy if two predecessors of a PhiM point into
314 * one block, but not at the same memory node
316 assert(get_irn_mode(phi) != mode_M);
317 if (get_Proj_proj(projx0) == pn_Cond_true) {
326 current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
328 DB((dbg, LEVEL_2, "Generating %+F for %+F\n", psi, phi));
331 /* only exchange if we have a Psi */
335 rewire(phi, i, j, psi);
338 phi = get_irn_link(phi);
339 } while (phi != NULL);
341 exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
342 exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
346 DB((dbg, LEVEL_1, "Welding block %+F and %+F\n", block, psi_block));
347 /* copy the block-info from the Psi-block to the block before merging */
348 get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
349 set_irn_link(block, get_irn_link(psi_block));
351 set_irn_in(block, get_irn_arity(psi_block), get_irn_in(psi_block) + 1);
352 exchange_cdep(psi_block, block);
353 exchange(psi_block, block);
355 DB((dbg, LEVEL_1, "Welding block %+F to %+F\n", block, psi_block));
356 get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
357 exchange(block, psi_block);
361 rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block));
370 * Block walker: add additional data
372 static void init_block_link(ir_node *block, void *env)
374 struct obstack *obst = env;
375 block_info *bi = obstack_alloc(obst, sizeof(*bi));
379 set_irn_link(block, bi);
384 * Daisy-chain all phis in a block
385 * If a non-movable node is encountered set the has_pinned flag
387 static void collect_phis(ir_node *node, void *env)
390 ir_node *block = get_nodes_block(node);
391 block_info *bi = get_block_blockinfo(block);
393 set_irn_link(node, bi->phi);
397 if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
399 * Ignore control flow nodes, these will be removed.
400 * This ignores Raise. That is surely bad. FIXME.
402 if (! is_cfop(node)) {
403 ir_node *block = get_nodes_block(node);
404 block_info *bi = get_block_blockinfo(block);
406 DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
415 * Transform multiple cascaded Psis into one Psi
417 static ir_node* fold_psi(ir_node* psi)
419 int arity = get_Psi_n_conds(psi);
430 for (i = 0; i < arity; ++i) {
431 n = get_Psi_val(psi, i);
432 if (get_irn_op(n) == op_Psi) {
433 new_arity += get_Psi_n_conds(n) + 1;
438 n = get_Psi_default(psi);
439 if (get_irn_op(n) == op_Psi) {
440 new_arity += get_Psi_n_conds(n);
443 if (arity == new_arity) return psi; // no attached Psis found
444 DB((dbg, LEVEL_1, "Folding %+F from %d to %d conds\n", psi, arity, new_arity));
446 NEW_ARR_A(ir_node *, conds, new_arity);
447 NEW_ARR_A(ir_node *, vals, new_arity + 1);
449 for (i = 0; i < arity; ++i) {
450 ir_node* c = get_Psi_cond(psi, i);
452 n = get_Psi_val(psi, i);
453 if (get_irn_op(n) == op_Psi) {
454 a = get_Psi_n_conds(n);
455 for (k = 0; k < a; ++k) {
456 conds[j] = new_r_And(
457 current_ir_graph, get_nodes_block(psi),
458 c, get_Psi_cond(n, k), mode_b
460 vals[j] = get_Psi_val(n, k);
464 vals[j] = get_Psi_default(n);
471 n = get_Psi_default(psi);
472 if (get_irn_op(n) == op_Psi) {
473 a = get_Psi_n_conds(n);
474 for (k = 0; k < a; ++k) {
475 conds[j] = get_Psi_cond(n, k);
476 vals[j] = get_Psi_val(n, k);
479 vals[j] = get_Psi_default(n);
483 assert(j == new_arity);
485 current_ir_graph, get_nodes_block(psi),
486 new_arity, conds, vals, get_irn_mode(psi)
488 DB((dbg, LEVEL_1, "Folded %+F into new %+F\n", psi, new_psi));
489 exchange(psi, new_psi);
495 * Merge consecutive psi inputs if the data inputs are the same
497 static ir_node* meld_psi(ir_node* psi)
499 int arity = get_Psi_n_conds(psi);
510 val = get_Psi_val(psi, 0);
511 DB((dbg, LEVEL_1, "Pred 0 of %+F is %+F\n", psi, val));
512 for (i = 1; i < arity; ++i) {
513 ir_node* v = get_Psi_val(psi, i);
514 DB((dbg, LEVEL_1, "Pred %2d of %+F is %+F\n", i, psi, v));
520 DB((dbg, LEVEL_1, "Default of %+F is %+F\n", psi, get_Psi_default(psi)));
521 if (val == get_Psi_default(psi)) --new_arity;
523 DB((dbg, LEVEL_1, "Melding Psi %+F from %d conds to %d\n", psi, arity, new_arity));
525 if (new_arity == arity) return psi;
527 /* If all data inputs of the Psi are equal, exchange the Psi with that value */
528 if (new_arity == 0) {
533 NEW_ARR_A(ir_node *, conds, new_arity);
534 NEW_ARR_A(ir_node *, vals, new_arity + 1);
535 cond = get_Psi_cond(psi, 0);
536 val = get_Psi_val(psi, 0);
538 for (i = 1; i < arity; ++i) {
539 ir_node* v = get_Psi_val(psi, i);
543 current_ir_graph, get_nodes_block(psi),
544 cond, get_Psi_cond(psi, i), mode_b
553 if (val != get_Psi_default(psi)) {
558 vals[j] = get_Psi_default(psi);
559 assert(j == new_arity);
561 current_ir_graph, get_nodes_block(psi),
562 new_arity, conds, vals, get_irn_mode(psi)
564 DB((dbg, LEVEL_1, "Molded %+F into %+F\n", psi, new_psi));
565 exchange(psi, new_psi);
571 * Split a Psi with multiple conditions into multiple Psis with one condtition
574 static ir_node* split_psi(ir_node* psi)
576 int arity = get_Psi_n_conds(psi);
582 if (arity == 1) return psi;
584 mode = get_irn_mode(psi);
585 block = get_nodes_block(psi);
586 rval = get_Psi_default(psi);
587 for (i = arity - 1; i >= 0; --i) {
591 conds[0] = get_Psi_cond(psi, i);
592 vals[0] = get_Psi_val(psi, i);
595 current_ir_graph, block, 1, conds, vals, mode
603 static void optimise_psis(ir_node* node, void* env)
605 if (get_irn_op(node) != op_Psi) return;
607 node = fold_psi(node);
610 node = meld_psi(node);
613 node = split_psi(node);
618 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
621 opt_if_conv_info_t p;
623 if (! get_opt_if_conversion())
626 /* get the parameters */
628 memcpy(&p, params, sizeof(p));
630 memcpy(&p, &default_info, sizeof(p));
632 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
634 DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
636 normalize_one_return(irg);
637 remove_critical_cf_edges(irg);
643 irg_block_walk_graph(irg, init_block_link, NULL, &obst);
644 irg_walk_graph(irg, collect_phis, NULL, NULL);
645 irg_block_walk_graph(irg, NULL, if_conv_walker, &p);
647 local_optimize_graph(irg);
649 irg_walk_graph(irg, NULL, optimise_psis, NULL);
651 obstack_free(&obst, NULL);
662 * Make Mux nodes from Conds where it its possible.
663 * @author Sebastian Hack
680 #include "irgraph_t.h"
681 #include "irnode_t.h"
685 #include "irmode_t.h"
686 #include "ircons_t.h"
691 #include "irflag_t.h"
693 #include "irprintf.h"
698 #include "bitfiddle.h"
705 * check, if a node is const and return its tarval or
706 * return a default tarval.
707 * @param cnst The node whose tarval to get.
708 * @param or The alternative tarval, if the node is no Const.
709 * @return The tarval of @p cnst, if the node is Const, @p otherwise.
711 static tarval *get_value_or(ir_node *cnst, tarval *or)
713 return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
718 * Try to optimize nested muxes into a dis- or conjunction
720 * @param mux The parent mux, which has muxes as operands.
721 * @return The replacement node for this mux. If the optimization is
722 * successful, this might be an And or Or node, if not, its the mux
725 static ir_node *optimize_mux_chain(ir_node *mux)
730 ir_mode *mode = get_irn_mode(mux);
735 * If we have no mux, or its mode is not integer, we
738 if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
742 null = get_mode_null(mode);
743 minus_one = tarval_sub(null, get_tarval_one(mode));
745 ops[0] = get_Mux_false(mux);
746 ops[1] = get_Mux_true(mux);
748 for(i = 0; i < 2; ++i) {
750 tarval *tva, *tvb, *tvd;
754 * A mux operand at the first position can be factored
755 * out, if the operands fulfill several conditions:
757 * mux(c1, mux(c2, a, b), d)
759 * This can be made into:
760 * 1) mux(c1, 0, d) | mux(c2, a, b)
761 * if a | d == d and b | d == d
763 * 2) mux(c1, -1, d) & mux(c2, a, b)
764 * if a & d == d and a & b == b
766 if(get_irn_op(ops[i]) == op_Mux) {
769 a = get_Mux_false(child_mux);
770 b = get_Mux_true(child_mux);
773 /* Try the or stuff */
774 tva = get_value_or(a, minus_one);
775 tvb = get_value_or(b, minus_one);
776 tvd = get_value_or(d, null);
778 if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
779 && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
781 ops[i] = new_Const(mode, null);
782 res = new_r_Or(current_ir_graph, get_nodes_block(mux),
783 mux, child_mux, mode);
787 /* If the or didn't go, try the and stuff */
788 tva = get_value_or(a, null);
789 tvb = get_value_or(b, null);
790 tvd = get_value_or(d, minus_one);
792 if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
793 && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
795 ops[i] = new_Const(mode, minus_one);
796 res = new_r_And(current_ir_graph, get_nodes_block(mux),
797 mux, child_mux, mode);
803 /* recursively optimize nested muxes. */
804 set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
805 set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
811 /***********************************************************
812 * The If conversion itself.
813 ***********************************************************/
815 /** allow every Mux to be created. */
816 static int default_allow_mux(ir_node *sel, ir_node *false_res, ir_node *true_res) {
823 static const opt_if_conv_info_t default_info = {
828 /** The debugging module. */
829 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
832 * A simple check for side effects upto an opcode of a ir node.
833 * @param irn The ir node to check,
834 * @return 1 if the opcode itself may produce side effects, 0 if not.
836 static INLINE int has_side_effects(const ir_node *irn)
838 ir_op *op = get_irn_op(irn);
843 return !mode_is_datab(get_irn_mode(irn));
847 * Possible failure reasons
849 enum failure_reason_t {
850 SUCCESS = IF_RESULT_SUCCESS,
851 TO_DEEP = IF_RESULT_TOO_DEEP,
852 SIDE_EFFECTS = IF_RESULT_SIDE_EFFECT,
853 PHI_FOUND = IF_RESULT_SIDE_EFFECT_PHI,
854 DENIED = IF_RESULT_DENIED
858 * Decides, if a given expression and its subexpressions
859 * (to certain, also given extent) can be moved to a block.
861 * @param expr The expression to examine.
862 * @param block The block where the expression should go.
863 * @param depth The current depth, passed recursively. Use 0 for
864 * non-recursive calls.
865 * @param info The options for createing Mux nodes.
868 * @return a failure reason
870 static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, const opt_if_conv_info_t *info)
874 ir_node *expr_block = get_nodes_block(expr);
877 * If we are forced to look too deep into the expression,
878 * treat it like it could not be moved.
880 if(depth >= info->max_depth) {
886 * If the block of the expression dominates the specified
887 * destination block, it does not matter if the expression
888 * has side effects or anything else. It is executed on each
889 * path the destination block is reached.
891 if (block_dominates(expr_block, dest_block))
895 * We cannot move phis!
903 * This should be superfluous and could be converted into a assertion.
904 * The destination block _must_ dominate the block of the expression,
905 * else the expression could be used without its definition.
907 if (! block_dominates(dest_block, expr_block)) {
908 res = IF_RESULT_SIDE_EFFECT;
913 * Surely, if the expression does not have a data mode, it is not
914 * movable. Perhaps one should also test the floating property of
917 if (has_side_effects(expr)) {
918 res = IF_RESULT_SIDE_EFFECT;
923 * If the node looks alright so far, look at its operands and
924 * check them out. If one of them cannot be moved, this one
925 * cannot be moved either.
927 for (i = 0, n = get_irn_arity(expr); i < n; ++i) {
928 ir_node *op = get_irn_n(expr, i);
929 int new_depth = is_Proj(op) ? depth : depth + 1;
931 res = _can_move_to(op, dest_block, new_depth, info);
938 DBG((dbg, LEVEL_3, "\t\t\tcan move to %n: %d\n", expr, res));
944 * Convenience function for _can_move_to.
945 * Checks, if an expression can be moved to another block. The check can
946 * be limited to a expression depth meaning if we need to crawl in
947 * deeper into an expression than a given threshold to examine if
948 * it can be moved, the expression is rejected and the test returns
951 * @param expr The expression to check for.
952 * @param dest_block The destination block you want @p expr to be.
953 * @param info The options for createing Mux nodes.
955 * @return return a failure reason
957 static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, const opt_if_conv_info_t *info)
959 return _can_move_to(expr, dest_block, 0, info);
963 * move a DAG given by a root node expr into a new block
965 * @param expr the root of a dag
966 * @param dest_block the destination block
968 static void move_to(ir_node *expr, ir_node *dest_block)
971 ir_node *expr_block = get_nodes_block(expr);
974 * If we reached the dominator, we are done.
975 * We will never put code through the dominator
977 if (block_dominates(expr_block, dest_block))
980 for (i = 0, n = get_irn_arity(expr); i < n; ++i)
981 move_to(get_irn_n(expr, i), dest_block);
983 set_nodes_block(expr, dest_block);
987 * return the common dominator of two blocks
989 static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2)
991 if(block_dominates(b1, b2))
993 else if(block_dominates(b2, b1))
998 for (p = get_Block_idom(b1); !block_dominates(p, b2); p = get_Block_idom(p));
1004 * Information about a cond node.
1006 typedef struct _cond_t {
1007 ir_node *cond; /**< The cond node. */
1008 struct list_head list; /**< List head which is used for queuing this cond
1009 into the cond bunch it belongs to. */
1010 unsigned is_new : 1;
1011 unsigned totally_covers : 1;
1012 struct _cond_t *link;
1016 * Information about the both 'branches'
1017 * (true and false), the cond creates.
1020 int pos; /**< Number of the predecessor of the
1021 phi block by which this branch is
1022 reached. It is -1, if this branch is
1023 only reached through another cond. */
1025 struct _cond_t *masked_by; /**< If this cond's branch is only reached
1026 through another cond, we store this
1027 cond ir_node here. */
1032 * retrieve the conditional information from a Cond node
1034 static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
1039 return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
1043 typedef void (cond_walker_t)(cond_t *cond, void *env);
1045 static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
1046 long visited_nr, void *env)
1050 if(cond->visited_nr >= visited_nr)
1053 cond->visited_nr = visited_nr;
1058 for(i = 0; i < 2; ++i) {
1059 cond_t *c = cond->cases[i].masked_by;
1062 _walk_conds(c, pre, post, visited_nr, env);
1069 static long cond_visited_nr = 0;
1071 static void walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post, void *env)
1073 _walk_conds(cond, pre, post, ++cond_visited_nr, env);
1076 static void link_conds(cond_t *cond, void *env)
1078 cond_t **ptr = (cond_t **) env;
1085 * Compare two conds for use in a firm set.
1086 * Two cond_t's are equal, if they designate the same cond node.
1087 * @param a A cond_t.
1088 * @param b Another one.
1089 * @param size Not used.
1090 * @return 0 (!) if they are equal, != 0 otherwise.
1092 static int cond_cmp(const void *a, const void *b, size_t size)
1094 const cond_t *x = a;
1095 const cond_t *y = b;
1096 return x->cond != y->cond;
1100 * Information about conds which can be made to muxes.
1101 * Instances of this struct are attached to the link field of
1102 * blocks in which phis are located.
1104 typedef struct _cond_info_t {
1105 struct list_head list; /**< Used to list all of these structs per class. */
1107 struct list_head roots; /**< A list of non-depending Conds. Two Conds are
1108 independent, if it's not possible not reach one from the
1109 other (all Conds in this list have to dominate the
1110 block this struct is attached to). */
1112 ir_node *first_phi; /**< The first phi node this cond info was made for. */
1113 set *cond_set; /**< A set of all dominating reachable Conds. */
1119 static void _find_conds(ir_node *irn, unsigned long visited_nr,
1120 ir_node *dominator, cond_t *masked_by, int pos, int depth, cond_info_t *ci)
1123 int saw_select_cond = 0;
1125 block = get_nodes_block(irn);
1128 * Only check this block if it is dominated by the specified
1129 * dominator or it has not been visited yet.
1131 if (block_dominates(dominator, block) && get_Block_block_visited(block) < visited_nr) {
1132 cond_t *res = masked_by;
1135 /* check, if we're on a ProjX
1137 * Further, the ProjX/Cond block must dominate the base block
1138 * (the block with the phi in it), otherwise, the Cond
1139 * is not affecting the phi so that a mux can be inserted.
1141 if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
1143 int proj = get_Proj_proj(irn);
1144 ir_node *cond = get_Proj_pred(irn);
1146 /* true, if the mode is a mode_b cond _NO_ switch cond */
1147 int is_modeb_cond = get_irn_opcode(cond) == iro_Cond
1148 && get_irn_mode(get_Cond_selector(cond)) == mode_b;
1150 saw_select_cond = !is_modeb_cond;
1152 /* Check, if the pred of the proj is a Cond
1153 * with a Projb as selector.
1158 memset(&c, 0, sizeof(c));
1161 c.cases[0].pos = -1;
1162 c.cases[1].pos = -1;
1164 /* get or insert the cond info into the set. */
1165 res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
1168 * If this cond is already masked by the masked_by cond
1169 * return immediately, since we don't have anything to add.
1171 if(masked_by && res->cases[proj].masked_by == masked_by)
1176 list_add(&res->list, &ci->roots);
1180 * Set masked by (either NULL or another cond node.
1181 * If this cond is truly masked by another one, set
1182 * the position of the actually investigated branch
1183 * to -1. Since the cond is masked by another one,
1184 * there could be more ways from the start block
1185 * to this branch, so we choose -1.
1187 res->cases[proj].masked_by = masked_by;
1190 res->cases[proj].pos = pos;
1193 * Since the masked_by nodes masks a cond, remove it from the
1194 * root list of the conf trees.
1197 assert(res->cases[proj].pos < 0);
1198 list_del_init(&masked_by->list);
1201 DBG((dbg, LEVEL_2, "%n (%s branch) "
1202 "for pos %d in block %n reached by %n\n",
1203 cond, proj ? "true" : "false", pos,
1204 block, masked_by ? masked_by->cond : NULL));
1208 if(get_Block_block_visited(block) < visited_nr && !saw_select_cond) {
1210 set_Block_block_visited(block, visited_nr);
1212 /* Search recursively from this cond. */
1213 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1214 ir_node *pred = get_irn_n(block, i);
1217 * If the depth is 0 (the first recursion), we set the pos to
1218 * the current viewed predecessor, else we adopt the position
1219 * as given by the caller. We also increase the depth for the
1220 * recursively called functions.
1222 _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci);
1230 * A convenience function for _find_conds.
1231 * It sets some parameters needed for recursion to appropriate start
1232 * values. Always use this function.
1234 * @param irn The node to start looking for Conds from. This might
1235 * be the phi node we are investigating.
1236 * @param conds The set to record the found Conds in.
1238 static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
1241 unsigned long visited_nr;
1242 ir_node *block = get_nodes_block(irn);
1243 ir_node *dom = get_Block_idom(block);
1245 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1246 ir_node *pred = get_irn_n(block, i);
1248 inc_irg_block_visited(current_ir_graph);
1249 visited_nr = get_irg_block_visited(current_ir_graph);
1250 set_Block_block_visited(block, visited_nr);
1252 DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
1253 _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
1258 * Make the mux for a given cond.
1260 * @param phi The phi node which shall be replaced by a mux.
1261 * @param dom The block where the muxes shall be placed.
1262 * @param cond The cond information.
1263 * @param info The options for createing Mux nodes.
1264 * @return The mux node made for this cond.
1266 static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond,
1267 const opt_if_conv_info_t *info, ir_node **mux, bitset_t *positions,
1268 int *muxes_made, long visited_nr)
1271 ir_node *projb = get_Cond_selector(cond->cond);
1272 ir_node *bl = get_nodes_block(cond->cond);
1273 ir_node *operands[2];
1276 cond->visited_nr = visited_nr;
1277 DBG((dbg, LEVEL_2, "%n\n", cond->cond));
1278 for(i = 0; i < 2; ++i) {
1279 cond_t *masked_by = cond->cases[i].masked_by;
1280 int pos = cond->cases[i].pos;
1286 * If this Cond branch is masked by another cond, make the mux
1287 * for that Cond first, since the Mux for this cond takes
1292 DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
1293 if(masked_by->visited_nr < visited_nr)
1294 operands[i] = make_mux_on_demand(phi, dom, masked_by, info, mux, positions, muxes_made, visited_nr);
1298 * If this cond branch is not masked by another cond, take
1299 * the corresponding phi operand as an operand to the mux.
1302 operands[i] = get_irn_n(phi, pos);
1308 * Move the operands to the dominator block if the cond
1309 * made sense. Some Conds found are not suitable for making a mux
1310 * out of them, since one of their branches cannot be reached from
1311 * the phi block. In that case we do not make a mux and return NULL.
1313 if(operands[0] && operands[1]) {
1314 if (operands[0] == operands[1]) {
1315 /* there is no gain in using mux in this case, as
1316 it will be optimized away. We will NOT move the
1317 content of the blocks either
1319 for (i = 0; i < 2; ++i)
1321 bitset_set(positions, set[i]);
1327 can_move[0] = can_move_to(operands[0], bl, info);
1328 can_move[1] = can_move_to(operands[1], bl, info);
1330 if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) {
1331 if (info->allow_mux(projb, operands[0], operands[1])) {
1332 move_to(operands[0], bl);
1333 move_to(operands[1], bl);
1336 *mux = new_r_Mux(current_ir_graph, bl, projb,
1337 operands[0], operands[1], get_irn_mode(operands[0]));
1341 DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
1342 *mux, projb, operands[0], operands[1], set[0], set[1]));
1344 for(i = 0; i < 2; ++i)
1346 bitset_set(positions, set[i]);
1348 /* we have done one */
1349 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_SUCCESS);
1353 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_DENIED);
1357 if(can_move[0] != SUCCESS)
1358 hook_if_conversion(current_ir_graph, phi, set[0], NULL, can_move[0]);
1359 if(can_move[1] != SUCCESS)
1360 hook_if_conversion(current_ir_graph, phi, set[1], NULL, can_move[1]);
1365 hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF);
1367 hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF);
1373 typedef struct _phi_info_t {
1374 struct list_head list;
1375 cond_info_t *cond_info;
1381 * Examine a phi node if it can be replaced by some muxes.
1382 * @param irn A phi node.
1383 * @param info Parameters for the if conversion algorithm.
1385 static int check_out_phi(phi_info_t *phi_info, const opt_if_conv_info_t *info)
1387 ir_node *irn = phi_info->irn;
1388 ir_node *block, *nw;
1389 cond_info_t *cond_info = phi_info->cond_info;
1393 bitset_t *positions;
1395 block = get_nodes_block(irn);
1396 arity = get_irn_arity(irn);
1397 positions = bitset_alloca(arity);
1399 assert(is_Phi(irn));
1400 assert(get_irn_arity(irn) == get_irn_arity(block));
1403 DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
1405 list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
1406 ir_node *cidom = block;
1407 ir_node *mux = NULL;
1408 cond_t *p, *head = NULL;
1411 bitset_clear_all(positions);
1413 DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
1415 * Link all conds which are in the subtree of
1416 * the current cond in the list together.
1418 walk_conds(cond, link_conds, NULL, &head);
1421 for(p = head; p; p = p->link) {
1422 for(i = 0; i < 2; ++i) {
1423 int pos = p->cases[i].pos;
1425 cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
1429 DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
1430 make_mux_on_demand(irn, cidom, cond, info, &mux, positions, &muxes_made, ++cond_visited_nr);
1433 bitset_foreach(positions, pos)
1434 set_irn_n(irn, (int) pos, mux);
1439 * optimize the phi away. This can anable further runs of this
1440 * function. Look at _can_move. phis cannot be moved there.
1442 nw = optimize_in_place_2(irn);
1449 typedef struct _cond_walk_info_t {
1450 struct obstack *obst;
1451 struct list_head cond_info_head;
1452 struct list_head phi_head;
1456 static void annotate_cond_info_pre(ir_node *irn, void *data)
1458 set_irn_link(irn, NULL);
1461 static void annotate_cond_info_post(ir_node *irn, void *data)
1463 cond_walk_info_t *cwi = data;
1466 * Check, if the node is a phi
1467 * we then compute a set of conds which are reachable from this
1468 * phi's block up to its dominator.
1469 * The set is attached to the blocks link field.
1471 if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
1472 ir_node *block = get_nodes_block(irn);
1474 cond_info_t *ci = get_irn_link(block);
1476 /* If the set is not yet computed, do it now. */
1478 ci = obstack_alloc(cwi->obst, sizeof(*ci));
1479 ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
1480 ci->first_phi = irn;
1482 INIT_LIST_HEAD(&ci->roots);
1483 INIT_LIST_HEAD(&ci->list);
1486 * Add this cond info to the list of all cond infos
1487 * in this graph. This is just done to xfree the
1488 * set easier afterwards (we save an irg_walk_graph).
1490 list_add(&cwi->cond_info_head, &ci->list);
1492 DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
1495 * Fill the set with conds we find on the way from
1496 * the block to its dominator.
1498 find_conds(irn, ci);
1501 * If there where no suitable conds, delete the set
1502 * immediately and reset the set pointer to NULL
1504 if(set_count(ci->cond_set) == 0) {
1505 del_set(ci->cond_set);
1506 list_del(&ci->list);
1507 obstack_free(cwi->obst, ci);
1513 DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
1515 set_irn_link(block, ci);
1518 phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
1521 INIT_LIST_HEAD(&pi->list);
1522 list_add(&pi->list, &cwi->phi_head);
1528 static void dump_conds(cond_t *cond, void *env)
1533 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
1534 cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
1535 get_nodes_block(cond->cond));
1537 for(i = 0; i < 2; ++i)
1538 if(cond->cases[i].masked_by)
1539 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
1540 cond, cond->cases[i].masked_by, i);
1543 static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi)
1548 snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
1550 if((f = fopen(buf, "wt")) != NULL) {
1555 ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
1556 list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
1557 ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
1558 list_for_each_entry(cond_t, cond, &ci->roots, list) {
1559 walk_conds(cond, NULL, dump_conds, f);
1560 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
1564 list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
1565 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
1566 phi->irn, phi->irn, get_nodes_block(phi->irn));
1567 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
1573 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
1576 struct obstack obst;
1577 phi_info_t *phi_info;
1578 cond_info_t *cond_info;
1579 cond_walk_info_t cwi;
1581 opt_if_conv_info_t p;
1583 if(!get_opt_if_conversion())
1586 /* get the parameters */
1588 memcpy(&p, params, sizeof(p));
1590 memcpy(&p, &default_info, sizeof(p));
1593 p.allow_mux = default_info.allow_mux;
1595 obstack_init(&obst);
1598 INIT_LIST_HEAD(&cwi.cond_info_head);
1599 INIT_LIST_HEAD(&cwi.phi_head);
1601 /* Init the debug stuff. */
1602 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
1604 firm_dbg_set_mask(dbg, LEVEL_1|LEVEL_2|LEVEL_3);
1607 /* if-conversion works better with normalized returns */
1608 normalize_one_return(irg);
1610 /* Ensure, that the dominators are computed. */
1613 DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
1614 get_entity_name(get_irg_entity(irg)), irg));
1617 * Collect information about the conds pu the phis on an obstack.
1618 * It is important that phi nodes which are 'higher' (with a
1619 * lower dfs pre order) are in front of the obstack. Since they are
1620 * possibly turned in to muxes this can enable the optimization
1623 irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
1626 vcg_dump_conds(irg, &cwi);
1629 /* Process each suitable phi found. */
1630 list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
1631 DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
1632 muxes_made += check_out_phi(phi_info, &p);
1635 list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
1636 del_set(cond_info->cond_set);
1639 DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
1641 obstack_free(&obst, NULL);