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.
43 DEBUG_ONLY(firm_dbg_module_t *dbg);
47 * Additional block info.
49 typedef struct block_info {
50 ir_node *phi; /**< head of the Phi list */
51 int has_pinned; /**< set if the block contains instructions that cannot be moved */
54 #define get_block_blockinfo(block) ((block_info *)get_irn_link(block))
57 * Returns non-zero if a Block can be emptied.
59 static int can_empty_block(ir_node *block)
61 return !get_block_blockinfo(block)->has_pinned;
65 static ir_node* walk_to_projx(ir_node* start, const ir_node* dependency)
70 /* No need to find the conditional block if this block cannot be emptied and
73 if (!can_empty_block(start)) return NULL;
75 arity = get_irn_arity(start);
76 for (i = 0; i < arity; ++i) {
77 ir_node* pred = get_irn_n(start, i);
78 ir_node* pred_block = get_nodes_block(pred);
80 if (pred_block == dependency) {
82 assert(get_irn_mode(pred) == mode_X);
89 assert(get_irn_mode(pred) == mode_X);
93 if (is_cdep_on(pred_block, dependency)) {
94 return walk_to_projx(pred_block, dependency);
102 * Copies the DAG starting at node to the ith predecessor block of src_block
103 * -if the node isn't in the src_block, this is a nop and the node is returned
104 * -if the node is a phi in the src_block, the ith predecessor of the phi is
106 * otherwise returns the copy of the passed node
108 static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
115 if (get_nodes_block(node) != src_block) return node;
116 if (get_irn_op(node) == op_Phi) return get_irn_n(node, i);
118 copy = exact_copy(node);
119 dst_block = get_nodes_block(get_irn_n(src_block, i));
120 set_nodes_block(copy, dst_block);
122 DB((dbg, LEVEL_1, "Copying node %+F to block %+F, copy is %+F\n",
123 node, dst_block, copy));
125 arity = get_irn_arity(node);
126 for (j = 0; j < arity; ++j) {
127 set_irn_n(copy, j, copy_to(get_irn_n(node, j), src_block, i));
128 DB((dbg, LEVEL_2, "-- pred %d is %+F\n", j, get_irn_n(copy, j)));
135 * Remove predecessors i and j from node and add predecessor new_pred
137 static void rewire(ir_node* node, int i, int j, ir_node* new_pred)
139 int arity = get_irn_arity(node);
144 NEW_ARR_A(ir_node *, ins, arity - 1);
147 for (k = 0; k < i; ++k) ins[l++] = get_irn_n(node, k);
148 for (++k; k < j; ++k) ins[l++] = get_irn_n(node, k);
149 for (++k; k < arity; ++k) ins[l++] = get_irn_n(node, k);
151 assert(l == arity - 1);
152 set_irn_in(node, l, ins);
157 * Remove the jth predecessors from the ith predecessor of block and add it to block
159 static void split_block(ir_node* block, int i, int j)
161 ir_node* pred_block = get_nodes_block(get_irn_n(block, i));
162 int arity = get_irn_arity(block);
169 DB((dbg, LEVEL_1, "Splitting predecessor %d of predecessor %d of %+F\n", j, i, block));
171 NEW_ARR_A(ir_node*, ins, arity + 1);
173 for (phi = get_block_blockinfo(block)->phi; phi != NULL; phi = get_irn_link(phi)) {
174 ir_node* copy = copy_to(get_irn_n(phi, i), pred_block, j);
176 for (k = 0; k < i; ++k) ins[k] = get_irn_n(phi, k);
178 for (; k < arity; ++k) ins[k] = get_irn_n(phi, k);
179 ins[k] = get_irn_n(phi, i);
181 set_irn_in(phi, arity + 1, ins);
184 for (k = 0; k < i; ++k) ins[k] = get_irn_n(block, k);
185 ins[k++] = get_irn_n(pred_block, j);
186 for (; k < arity; ++k) ins[k] = get_irn_n(block, k);
187 ins[k] = get_irn_n(block, i);
189 set_irn_in(block, arity + 1, ins);
191 new_pred_arity = get_irn_arity(pred_block) - 1;
192 NEW_ARR_A(ir_node*, pred_ins, new_pred_arity);
194 for (phi = get_block_blockinfo(pred_block)->phi; phi != NULL; phi = get_irn_link(phi)) {
195 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(phi, k);
196 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(phi, k + 1);
197 assert(k == new_pred_arity);
198 if (new_pred_arity > 1) {
199 set_irn_in(phi, new_pred_arity, pred_ins);
201 exchange(phi, pred_ins[0]);
205 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(pred_block, k);
206 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(pred_block, k + 1);
207 assert(k == new_pred_arity);
208 if (new_pred_arity > 1) {
209 set_irn_in(pred_block, new_pred_arity, pred_ins);
211 exchange(pred_block, get_nodes_block(pred_ins[0]));
216 static void prepare_path(ir_node* block, int i, const ir_node* dependency)
218 ir_node* pred = get_nodes_block(get_irn_n(block, i));
222 DB((dbg, LEVEL_1, "Preparing predecessor %d of %+F\n", i, block));
224 pred_arity = get_irn_arity(pred);
225 for (j = 0; j < pred_arity; ++j) {
226 ir_node* pred_pred = get_nodes_block(get_irn_n(pred, j));
228 if (is_cdep_on(pred_pred, dependency)) {
229 prepare_path(pred, j, dependency);
230 split_block(block, i, j);
237 static void if_conv_walker(ir_node* block, void* env)
242 /* Bail out, if there are no Phis at all */
243 if (get_block_blockinfo(block)->phi == NULL) return;
246 arity = get_irn_arity(block);
247 for (i = 0; i < arity; ++i) {
251 pred = get_nodes_block(get_irn_n(block, i));
252 for (cdep = find_cdep(pred); cdep != NULL; cdep = cdep->next) {
253 const ir_node* dependency = cdep->node;
254 ir_node* projx0 = walk_to_projx(pred, dependency);
258 if (projx0 == NULL) continue;
260 cond = get_Proj_pred(projx0);
261 if (get_irn_op(cond) != op_Cond) continue;
262 /* We only handle boolean decisions, no switches */
263 if (get_irn_mode(get_Cond_selector(cond)) != mode_b) continue;
265 for (j = i + 1; j < arity; ++j) {
273 pred = get_nodes_block(get_irn_n(block, j));
275 if (!is_cdep_on(pred, dependency)) continue;
277 projx1 = walk_to_projx(pred, dependency);
279 if (projx1 == NULL) continue;
281 DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n",
285 prepare_path(block, i, dependency);
286 prepare_path(block, j, dependency);
287 arity = get_irn_arity(block);
289 conds[0] = get_Cond_selector(cond);
291 psi_block = get_nodes_block(cond);
292 phi = get_block_blockinfo(block)->phi;
294 ir_node* val_i = get_irn_n(phi, i);
295 ir_node* val_j = get_irn_n(phi, j);
297 if (val_i == val_j) {
299 DB((dbg, LEVEL_2, "Generating no psi, because both values are equal\n"));
301 /* Something is very fishy if two predecessors of a PhiM point into
302 * one block, but not at the same memory node
304 assert(get_irn_mode(phi) != mode_M);
305 if (get_Proj_proj(projx0) == pn_Cond_true) {
313 current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
315 DB((dbg, LEVEL_2, "Generating %+F for %+F\n", psi, phi));
321 rewire(phi, i, j, psi);
324 phi = get_irn_link(phi);
325 } while (phi != NULL);
327 exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
328 exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
332 DB((dbg, LEVEL_1, "Welding block %+F and %+F\n", block, psi_block));
333 get_block_blockinfo(block)->has_pinned |= get_block_blockinfo(psi_block)->has_pinned;
334 set_irn_in(block, get_irn_arity(psi_block), get_irn_in(psi_block) + 1);
335 exchange_cdep(psi_block, block);
336 exchange(psi_block, block);
338 DB((dbg, LEVEL_1, "Welding block %+F to %+F\n", block, psi_block));
339 get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
340 exchange(block, psi_block);
344 rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block));
353 * Block walker: add additional data
355 static void init_block_link(ir_node *block, void *env)
357 struct obstack *obst = env;
358 block_info *bi = obstack_alloc(obst, sizeof(*bi));
362 set_irn_link(block, bi);
367 * Daisy-chain all phis in a block
368 * If a non-movable node is encountered set the has_pinned flag
370 static void collect_phis(ir_node *node, void *env)
373 ir_node *block = get_nodes_block(node);
374 block_info *bi = get_block_blockinfo(block);
376 set_irn_link(node, bi->phi);
380 if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
382 * Ignore control flow nodes, these will be removed.
383 * This ignores Raise. That is surely bad. FIXME.
385 if (! is_cfop(node)) {
386 ir_node *block = get_nodes_block(node);
387 block_info *bi = get_block_blockinfo(block);
389 DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
398 * Transform multiple cascaded Psis into one Psi
400 static ir_node* fold_psi(ir_node* psi)
402 int arity = get_Psi_n_conds(psi);
413 for (i = 0; i < arity; ++i) {
414 n = get_Psi_val(psi, i);
415 if (get_irn_op(n) == op_Psi) {
416 new_arity += get_Psi_n_conds(n) + 1;
421 n = get_Psi_default(psi);
422 if (get_irn_op(n) == op_Psi) {
423 new_arity += get_Psi_n_conds(n);
426 if (arity == new_arity) return psi; // no attached Psis found
427 DB((dbg, LEVEL_1, "Folding %+F from %d to %d conds\n", psi, arity, new_arity));
429 NEW_ARR_A(ir_node *, conds, new_arity);
430 NEW_ARR_A(ir_node *, vals, new_arity + 1);
432 for (i = 0; i < arity; ++i) {
433 ir_node* c = get_Psi_cond(psi, i);
435 n = get_Psi_val(psi, i);
436 if (get_irn_op(n) == op_Psi) {
437 a = get_Psi_n_conds(n);
438 for (k = 0; k < a; ++k) {
439 conds[j] = new_r_And(
440 current_ir_graph, get_nodes_block(psi),
441 c, get_Psi_cond(n, k), mode_b
443 vals[j] = get_Psi_val(n, k);
447 vals[j] = get_Psi_default(n);
454 n = get_Psi_default(psi);
455 if (get_irn_op(n) == op_Psi) {
456 a = get_Psi_n_conds(n);
457 for (k = 0; k < a; ++k) {
458 conds[j] = get_Psi_cond(n, k);
459 vals[j] = get_Psi_val(n, k);
462 vals[j] = get_Psi_default(n);
466 assert(j == new_arity);
468 current_ir_graph, get_nodes_block(psi),
469 new_arity, conds, vals, get_irn_mode(psi)
471 DB((dbg, LEVEL_1, "Folded %+F into new %+F\n", psi, new_psi));
472 exchange(psi, new_psi);
478 * Merge consecutive psi inputs if the data inputs are the same
480 static ir_node* meld_psi(ir_node* psi)
482 int arity = get_Psi_n_conds(psi);
493 val = get_Psi_val(psi, 0);
494 DB((dbg, LEVEL_1, "Pred 0 of %+F is %+F\n", psi, val));
495 for (i = 1; i < arity; ++i) {
496 ir_node* v = get_Psi_val(psi, i);
497 DB((dbg, LEVEL_1, "Pred %2d of %+F is %+F\n", i, psi, v));
503 DB((dbg, LEVEL_1, "Default of %+F is %+F\n", psi, get_Psi_default(psi)));
504 if (val == get_Psi_default(psi)) --new_arity;
506 DB((dbg, LEVEL_1, "Melding Psi %+F from %d conds to %d\n", psi, arity, new_arity));
508 if (new_arity == arity) return psi;
510 /* If all data inputs of the Psi are equal, exchange the Psi with that value */
511 if (new_arity == 0) {
516 NEW_ARR_A(ir_node *, conds, new_arity);
517 NEW_ARR_A(ir_node *, vals, new_arity + 1);
518 cond = get_Psi_cond(psi, 0);
519 val = get_Psi_val(psi, 0);
521 for (i = 1; i < arity; ++i) {
522 ir_node* v = get_Psi_val(psi, i);
526 current_ir_graph, get_nodes_block(psi),
527 cond, get_Psi_cond(psi, i), mode_b
536 if (val != get_Psi_default(psi)) {
541 vals[j] = get_Psi_default(psi);
542 assert(j == new_arity);
544 current_ir_graph, get_nodes_block(psi),
545 new_arity, conds, vals, get_irn_mode(psi)
547 DB((dbg, LEVEL_1, "Molded %+F into %+F\n", psi, new_psi));
548 exchange(psi, new_psi);
554 * Split a Psi with multiple conditions into multiple Psis with one condtition
557 static ir_node* split_psi(ir_node* psi)
559 int arity = get_Psi_n_conds(psi);
565 if (arity == 1) return psi;
567 mode = get_irn_mode(psi);
568 block = get_nodes_block(psi);
569 rval = get_Psi_default(psi);
570 for (i = arity - 1; i >= 0; --i) {
574 conds[0] = get_Psi_cond(psi, i);
575 vals[0] = get_Psi_val(psi, i);
578 current_ir_graph, block, 1, conds, vals, mode
586 static void optimise_psis(ir_node* node, void* env)
588 if (get_irn_op(node) != op_Psi) return;
590 node = fold_psi(node);
593 node = meld_psi(node);
596 node = split_psi(node);
601 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
605 if (!get_opt_if_conversion())
608 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
610 DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
612 dump_ir_block_graph(irg, "_00_pre");
614 normalize_one_return(irg);
615 remove_critical_cf_edges(irg);
617 dump_ir_block_graph(irg, "_01_normal");
623 irg_block_walk_graph(irg, init_block_link, NULL, &obst);
624 irg_walk_graph(irg, collect_phis, NULL, NULL);
625 irg_block_walk_graph(irg, NULL, if_conv_walker, NULL);
627 dump_ir_block_graph(irg, "_02_ifconv");
628 local_optimize_graph(irg);
629 dump_ir_block_graph(irg, "_03_postopt");
631 irg_walk_graph(irg, NULL, optimise_psis, NULL);
633 dump_ir_block_graph(irg, "_04_postifconv");
635 obstack_free(&obst, NULL);
646 * Make Mux nodes from Conds where it its possible.
647 * @author Sebastian Hack
664 #include "irgraph_t.h"
665 #include "irnode_t.h"
669 #include "irmode_t.h"
670 #include "ircons_t.h"
675 #include "irflag_t.h"
677 #include "irprintf.h"
682 #include "bitfiddle.h"
689 * check, if a node is const and return its tarval or
690 * return a default tarval.
691 * @param cnst The node whose tarval to get.
692 * @param or The alternative tarval, if the node is no Const.
693 * @return The tarval of @p cnst, if the node is Const, @p otherwise.
695 static tarval *get_value_or(ir_node *cnst, tarval *or)
697 return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
702 * Try to optimize nested muxes into a dis- or conjunction
704 * @param mux The parent mux, which has muxes as operands.
705 * @return The replacement node for this mux. If the optimization is
706 * successful, this might be an And or Or node, if not, its the mux
709 static ir_node *optimize_mux_chain(ir_node *mux)
714 ir_mode *mode = get_irn_mode(mux);
719 * If we have no mux, or its mode is not integer, we
722 if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
726 null = get_mode_null(mode);
727 minus_one = tarval_sub(null, get_tarval_one(mode));
729 ops[0] = get_Mux_false(mux);
730 ops[1] = get_Mux_true(mux);
732 for(i = 0; i < 2; ++i) {
734 tarval *tva, *tvb, *tvd;
738 * A mux operand at the first position can be factored
739 * out, if the operands fulfill several conditions:
741 * mux(c1, mux(c2, a, b), d)
743 * This can be made into:
744 * 1) mux(c1, 0, d) | mux(c2, a, b)
745 * if a | d == d and b | d == d
747 * 2) mux(c1, -1, d) & mux(c2, a, b)
748 * if a & d == d and a & b == b
750 if(get_irn_op(ops[i]) == op_Mux) {
753 a = get_Mux_false(child_mux);
754 b = get_Mux_true(child_mux);
757 /* Try the or stuff */
758 tva = get_value_or(a, minus_one);
759 tvb = get_value_or(b, minus_one);
760 tvd = get_value_or(d, null);
762 if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
763 && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
765 ops[i] = new_Const(mode, null);
766 res = new_r_Or(current_ir_graph, get_nodes_block(mux),
767 mux, child_mux, mode);
771 /* If the or didn't go, try the and stuff */
772 tva = get_value_or(a, null);
773 tvb = get_value_or(b, null);
774 tvd = get_value_or(d, minus_one);
776 if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
777 && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
779 ops[i] = new_Const(mode, minus_one);
780 res = new_r_And(current_ir_graph, get_nodes_block(mux),
781 mux, child_mux, mode);
787 /* recursively optimize nested muxes. */
788 set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
789 set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
795 /***********************************************************
796 * The If conversion itself.
797 ***********************************************************/
799 /** allow every Mux to be created. */
800 static int default_allow_mux(ir_node *sel, ir_node *false_res, ir_node *true_res) {
807 static const opt_if_conv_info_t default_info = {
812 /** The debugging module. */
813 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
816 * A simple check for side effects upto an opcode of a ir node.
817 * @param irn The ir node to check,
818 * @return 1 if the opcode itself may produce side effects, 0 if not.
820 static INLINE int has_side_effects(const ir_node *irn)
822 ir_op *op = get_irn_op(irn);
827 return !mode_is_datab(get_irn_mode(irn));
831 * Possible failure reasons
833 enum failure_reason_t {
834 SUCCESS = IF_RESULT_SUCCESS,
835 TO_DEEP = IF_RESULT_TOO_DEEP,
836 SIDE_EFFECTS = IF_RESULT_SIDE_EFFECT,
837 PHI_FOUND = IF_RESULT_SIDE_EFFECT_PHI,
838 DENIED = IF_RESULT_DENIED
842 * Decides, if a given expression and its subexpressions
843 * (to certain, also given extent) can be moved to a block.
845 * @param expr The expression to examine.
846 * @param block The block where the expression should go.
847 * @param depth The current depth, passed recursively. Use 0 for
848 * non-recursive calls.
849 * @param info The options for createing Mux nodes.
852 * @return a failure reason
854 static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, const opt_if_conv_info_t *info)
858 ir_node *expr_block = get_nodes_block(expr);
861 * If we are forced to look too deep into the expression,
862 * treat it like it could not be moved.
864 if(depth >= info->max_depth) {
870 * If the block of the expression dominates the specified
871 * destination block, it does not matter if the expression
872 * has side effects or anything else. It is executed on each
873 * path the destination block is reached.
875 if (block_dominates(expr_block, dest_block))
879 * We cannot move phis!
887 * This should be superfluous and could be converted into a assertion.
888 * The destination block _must_ dominate the block of the expression,
889 * else the expression could be used without its definition.
891 if (! block_dominates(dest_block, expr_block)) {
892 res = IF_RESULT_SIDE_EFFECT;
897 * Surely, if the expression does not have a data mode, it is not
898 * movable. Perhaps one should also test the floating property of
901 if (has_side_effects(expr)) {
902 res = IF_RESULT_SIDE_EFFECT;
907 * If the node looks alright so far, look at its operands and
908 * check them out. If one of them cannot be moved, this one
909 * cannot be moved either.
911 for (i = 0, n = get_irn_arity(expr); i < n; ++i) {
912 ir_node *op = get_irn_n(expr, i);
913 int new_depth = is_Proj(op) ? depth : depth + 1;
915 res = _can_move_to(op, dest_block, new_depth, info);
922 DBG((dbg, LEVEL_3, "\t\t\tcan move to %n: %d\n", expr, res));
928 * Convenience function for _can_move_to.
929 * Checks, if an expression can be moved to another block. The check can
930 * be limited to a expression depth meaning if we need to crawl in
931 * deeper into an expression than a given threshold to examine if
932 * it can be moved, the expression is rejected and the test returns
935 * @param expr The expression to check for.
936 * @param dest_block The destination block you want @p expr to be.
937 * @param info The options for createing Mux nodes.
939 * @return return a failure reason
941 static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, const opt_if_conv_info_t *info)
943 return _can_move_to(expr, dest_block, 0, info);
947 * move a DAG given by a root node expr into a new block
949 * @param expr the root of a dag
950 * @param dest_block the destination block
952 static void move_to(ir_node *expr, ir_node *dest_block)
955 ir_node *expr_block = get_nodes_block(expr);
958 * If we reached the dominator, we are done.
959 * We will never put code through the dominator
961 if (block_dominates(expr_block, dest_block))
964 for (i = 0, n = get_irn_arity(expr); i < n; ++i)
965 move_to(get_irn_n(expr, i), dest_block);
967 set_nodes_block(expr, dest_block);
971 * return the common dominator of two blocks
973 static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2)
975 if(block_dominates(b1, b2))
977 else if(block_dominates(b2, b1))
982 for (p = get_Block_idom(b1); !block_dominates(p, b2); p = get_Block_idom(p));
988 * Information about a cond node.
990 typedef struct _cond_t {
991 ir_node *cond; /**< The cond node. */
992 struct list_head list; /**< List head which is used for queuing this cond
993 into the cond bunch it belongs to. */
995 unsigned totally_covers : 1;
996 struct _cond_t *link;
1000 * Information about the both 'branches'
1001 * (true and false), the cond creates.
1004 int pos; /**< Number of the predecessor of the
1005 phi block by which this branch is
1006 reached. It is -1, if this branch is
1007 only reached through another cond. */
1009 struct _cond_t *masked_by; /**< If this cond's branch is only reached
1010 through another cond, we store this
1011 cond ir_node here. */
1016 * retrieve the conditional information from a Cond node
1018 static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
1023 return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
1027 typedef void (cond_walker_t)(cond_t *cond, void *env);
1029 static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
1030 long visited_nr, void *env)
1034 if(cond->visited_nr >= visited_nr)
1037 cond->visited_nr = visited_nr;
1042 for(i = 0; i < 2; ++i) {
1043 cond_t *c = cond->cases[i].masked_by;
1046 _walk_conds(c, pre, post, visited_nr, env);
1053 static long cond_visited_nr = 0;
1055 static void walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post, void *env)
1057 _walk_conds(cond, pre, post, ++cond_visited_nr, env);
1060 static void link_conds(cond_t *cond, void *env)
1062 cond_t **ptr = (cond_t **) env;
1069 * Compare two conds for use in a firm set.
1070 * Two cond_t's are equal, if they designate the same cond node.
1071 * @param a A cond_t.
1072 * @param b Another one.
1073 * @param size Not used.
1074 * @return 0 (!) if they are equal, != 0 otherwise.
1076 static int cond_cmp(const void *a, const void *b, size_t size)
1078 const cond_t *x = a;
1079 const cond_t *y = b;
1080 return x->cond != y->cond;
1084 * Information about conds which can be made to muxes.
1085 * Instances of this struct are attached to the link field of
1086 * blocks in which phis are located.
1088 typedef struct _cond_info_t {
1089 struct list_head list; /**< Used to list all of these structs per class. */
1091 struct list_head roots; /**< A list of non-depending Conds. Two Conds are
1092 independent, if it's not possible not reach one from the
1093 other (all Conds in this list have to dominate the
1094 block this struct is attached to). */
1096 ir_node *first_phi; /**< The first phi node this cond info was made for. */
1097 set *cond_set; /**< A set of all dominating reachable Conds. */
1103 static void _find_conds(ir_node *irn, unsigned long visited_nr,
1104 ir_node *dominator, cond_t *masked_by, int pos, int depth, cond_info_t *ci)
1107 int saw_select_cond = 0;
1109 block = get_nodes_block(irn);
1112 * Only check this block if it is dominated by the specified
1113 * dominator or it has not been visited yet.
1115 if (block_dominates(dominator, block) && get_Block_block_visited(block) < visited_nr) {
1116 cond_t *res = masked_by;
1119 /* check, if we're on a ProjX
1121 * Further, the ProjX/Cond block must dominate the base block
1122 * (the block with the phi in it), otherwise, the Cond
1123 * is not affecting the phi so that a mux can be inserted.
1125 if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
1127 int proj = get_Proj_proj(irn);
1128 ir_node *cond = get_Proj_pred(irn);
1130 /* true, if the mode is a mode_b cond _NO_ switch cond */
1131 int is_modeb_cond = get_irn_opcode(cond) == iro_Cond
1132 && get_irn_mode(get_Cond_selector(cond)) == mode_b;
1134 saw_select_cond = !is_modeb_cond;
1136 /* Check, if the pred of the proj is a Cond
1137 * with a Projb as selector.
1142 memset(&c, 0, sizeof(c));
1145 c.cases[0].pos = -1;
1146 c.cases[1].pos = -1;
1148 /* get or insert the cond info into the set. */
1149 res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
1152 * If this cond is already masked by the masked_by cond
1153 * return immediately, since we don't have anything to add.
1155 if(masked_by && res->cases[proj].masked_by == masked_by)
1160 list_add(&res->list, &ci->roots);
1164 * Set masked by (either NULL or another cond node.
1165 * If this cond is truly masked by another one, set
1166 * the position of the actually investigated branch
1167 * to -1. Since the cond is masked by another one,
1168 * there could be more ways from the start block
1169 * to this branch, so we choose -1.
1171 res->cases[proj].masked_by = masked_by;
1174 res->cases[proj].pos = pos;
1177 * Since the masked_by nodes masks a cond, remove it from the
1178 * root list of the conf trees.
1181 assert(res->cases[proj].pos < 0);
1182 list_del_init(&masked_by->list);
1185 DBG((dbg, LEVEL_2, "%n (%s branch) "
1186 "for pos %d in block %n reached by %n\n",
1187 cond, proj ? "true" : "false", pos,
1188 block, masked_by ? masked_by->cond : NULL));
1192 if(get_Block_block_visited(block) < visited_nr && !saw_select_cond) {
1194 set_Block_block_visited(block, visited_nr);
1196 /* Search recursively from this cond. */
1197 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1198 ir_node *pred = get_irn_n(block, i);
1201 * If the depth is 0 (the first recursion), we set the pos to
1202 * the current viewed predecessor, else we adopt the position
1203 * as given by the caller. We also increase the depth for the
1204 * recursively called functions.
1206 _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci);
1214 * A convenience function for _find_conds.
1215 * It sets some parameters needed for recursion to appropriate start
1216 * values. Always use this function.
1218 * @param irn The node to start looking for Conds from. This might
1219 * be the phi node we are investigating.
1220 * @param conds The set to record the found Conds in.
1222 static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
1225 unsigned long visited_nr;
1226 ir_node *block = get_nodes_block(irn);
1227 ir_node *dom = get_Block_idom(block);
1229 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
1230 ir_node *pred = get_irn_n(block, i);
1232 inc_irg_block_visited(current_ir_graph);
1233 visited_nr = get_irg_block_visited(current_ir_graph);
1234 set_Block_block_visited(block, visited_nr);
1236 DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
1237 _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
1242 * Make the mux for a given cond.
1244 * @param phi The phi node which shall be replaced by a mux.
1245 * @param dom The block where the muxes shall be placed.
1246 * @param cond The cond information.
1247 * @param info The options for createing Mux nodes.
1248 * @return The mux node made for this cond.
1250 static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond,
1251 const opt_if_conv_info_t *info, ir_node **mux, bitset_t *positions,
1252 int *muxes_made, long visited_nr)
1255 ir_node *projb = get_Cond_selector(cond->cond);
1256 ir_node *bl = get_nodes_block(cond->cond);
1257 ir_node *operands[2];
1260 cond->visited_nr = visited_nr;
1261 DBG((dbg, LEVEL_2, "%n\n", cond->cond));
1262 for(i = 0; i < 2; ++i) {
1263 cond_t *masked_by = cond->cases[i].masked_by;
1264 int pos = cond->cases[i].pos;
1270 * If this Cond branch is masked by another cond, make the mux
1271 * for that Cond first, since the Mux for this cond takes
1276 DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
1277 if(masked_by->visited_nr < visited_nr)
1278 operands[i] = make_mux_on_demand(phi, dom, masked_by, info, mux, positions, muxes_made, visited_nr);
1282 * If this cond branch is not masked by another cond, take
1283 * the corresponding phi operand as an operand to the mux.
1286 operands[i] = get_irn_n(phi, pos);
1292 * Move the operands to the dominator block if the cond
1293 * made sense. Some Conds found are not suitable for making a mux
1294 * out of them, since one of their branches cannot be reached from
1295 * the phi block. In that case we do not make a mux and return NULL.
1297 if(operands[0] && operands[1]) {
1298 if (operands[0] == operands[1]) {
1299 /* there is no gain in using mux in this case, as
1300 it will be optimized away. We will NOT move the
1301 content of the blocks either
1303 for (i = 0; i < 2; ++i)
1305 bitset_set(positions, set[i]);
1311 can_move[0] = can_move_to(operands[0], bl, info);
1312 can_move[1] = can_move_to(operands[1], bl, info);
1314 if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) {
1315 if (info->allow_mux(projb, operands[0], operands[1])) {
1316 move_to(operands[0], bl);
1317 move_to(operands[1], bl);
1320 *mux = new_r_Mux(current_ir_graph, bl, projb,
1321 operands[0], operands[1], get_irn_mode(operands[0]));
1325 DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
1326 *mux, projb, operands[0], operands[1], set[0], set[1]));
1328 for(i = 0; i < 2; ++i)
1330 bitset_set(positions, set[i]);
1332 /* we have done one */
1333 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_SUCCESS);
1337 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_DENIED);
1341 if(can_move[0] != SUCCESS)
1342 hook_if_conversion(current_ir_graph, phi, set[0], NULL, can_move[0]);
1343 if(can_move[1] != SUCCESS)
1344 hook_if_conversion(current_ir_graph, phi, set[1], NULL, can_move[1]);
1349 hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF);
1351 hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF);
1357 typedef struct _phi_info_t {
1358 struct list_head list;
1359 cond_info_t *cond_info;
1365 * Examine a phi node if it can be replaced by some muxes.
1366 * @param irn A phi node.
1367 * @param info Parameters for the if conversion algorithm.
1369 static int check_out_phi(phi_info_t *phi_info, const opt_if_conv_info_t *info)
1371 ir_node *irn = phi_info->irn;
1372 ir_node *block, *nw;
1373 cond_info_t *cond_info = phi_info->cond_info;
1377 bitset_t *positions;
1379 block = get_nodes_block(irn);
1380 arity = get_irn_arity(irn);
1381 positions = bitset_alloca(arity);
1383 assert(is_Phi(irn));
1384 assert(get_irn_arity(irn) == get_irn_arity(block));
1387 DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
1389 list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
1390 ir_node *cidom = block;
1391 ir_node *mux = NULL;
1392 cond_t *p, *head = NULL;
1395 bitset_clear_all(positions);
1397 DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
1399 * Link all conds which are in the subtree of
1400 * the current cond in the list together.
1402 walk_conds(cond, link_conds, NULL, &head);
1405 for(p = head; p; p = p->link) {
1406 for(i = 0; i < 2; ++i) {
1407 int pos = p->cases[i].pos;
1409 cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
1413 DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
1414 make_mux_on_demand(irn, cidom, cond, info, &mux, positions, &muxes_made, ++cond_visited_nr);
1417 bitset_foreach(positions, pos)
1418 set_irn_n(irn, (int) pos, mux);
1423 * optimize the phi away. This can anable further runs of this
1424 * function. Look at _can_move. phis cannot be moved there.
1426 nw = optimize_in_place_2(irn);
1433 typedef struct _cond_walk_info_t {
1434 struct obstack *obst;
1435 struct list_head cond_info_head;
1436 struct list_head phi_head;
1440 static void annotate_cond_info_pre(ir_node *irn, void *data)
1442 set_irn_link(irn, NULL);
1445 static void annotate_cond_info_post(ir_node *irn, void *data)
1447 cond_walk_info_t *cwi = data;
1450 * Check, if the node is a phi
1451 * we then compute a set of conds which are reachable from this
1452 * phi's block up to its dominator.
1453 * The set is attached to the blocks link field.
1455 if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
1456 ir_node *block = get_nodes_block(irn);
1458 cond_info_t *ci = get_irn_link(block);
1460 /* If the set is not yet computed, do it now. */
1462 ci = obstack_alloc(cwi->obst, sizeof(*ci));
1463 ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
1464 ci->first_phi = irn;
1466 INIT_LIST_HEAD(&ci->roots);
1467 INIT_LIST_HEAD(&ci->list);
1470 * Add this cond info to the list of all cond infos
1471 * in this graph. This is just done to xfree the
1472 * set easier afterwards (we save an irg_walk_graph).
1474 list_add(&cwi->cond_info_head, &ci->list);
1476 DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
1479 * Fill the set with conds we find on the way from
1480 * the block to its dominator.
1482 find_conds(irn, ci);
1485 * If there where no suitable conds, delete the set
1486 * immediately and reset the set pointer to NULL
1488 if(set_count(ci->cond_set) == 0) {
1489 del_set(ci->cond_set);
1490 list_del(&ci->list);
1491 obstack_free(cwi->obst, ci);
1497 DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
1499 set_irn_link(block, ci);
1502 phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
1505 INIT_LIST_HEAD(&pi->list);
1506 list_add(&pi->list, &cwi->phi_head);
1512 static void dump_conds(cond_t *cond, void *env)
1517 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
1518 cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
1519 get_nodes_block(cond->cond));
1521 for(i = 0; i < 2; ++i)
1522 if(cond->cases[i].masked_by)
1523 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
1524 cond, cond->cases[i].masked_by, i);
1527 static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi)
1532 snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
1534 if((f = fopen(buf, "wt")) != NULL) {
1539 ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
1540 list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
1541 ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
1542 list_for_each_entry(cond_t, cond, &ci->roots, list) {
1543 walk_conds(cond, NULL, dump_conds, f);
1544 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
1548 list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
1549 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
1550 phi->irn, phi->irn, get_nodes_block(phi->irn));
1551 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
1557 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
1560 struct obstack obst;
1561 phi_info_t *phi_info;
1562 cond_info_t *cond_info;
1563 cond_walk_info_t cwi;
1565 opt_if_conv_info_t p;
1567 if(!get_opt_if_conversion())
1570 /* get the parameters */
1572 memcpy(&p, params, sizeof(p));
1574 memcpy(&p, &default_info, sizeof(p));
1577 p.allow_mux = default_info.allow_mux;
1579 obstack_init(&obst);
1582 INIT_LIST_HEAD(&cwi.cond_info_head);
1583 INIT_LIST_HEAD(&cwi.phi_head);
1585 /* Init the debug stuff. */
1586 FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
1588 firm_dbg_set_mask(dbg, LEVEL_1|LEVEL_2|LEVEL_3);
1591 /* if-conversion works better with normalized returns */
1592 normalize_one_return(irg);
1594 /* Ensure, that the dominators are computed. */
1597 DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
1598 get_entity_name(get_irg_entity(irg)), irg));
1601 * Collect information about the conds pu the phis on an obstack.
1602 * It is important that phi nodes which are 'higher' (with a
1603 * lower dfs pre order) are in front of the obstack. Since they are
1604 * possibly turned in to muxes this can enable the optimization
1607 irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
1610 vcg_dump_conds(irg, &cwi);
1613 /* Process each suitable phi found. */
1614 list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
1615 DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
1616 muxes_made += check_out_phi(phi_info, &p);
1619 list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
1620 del_set(cond_info->cond_set);
1623 DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
1625 obstack_free(&obst, NULL);
1627 dump_ir_block_graph(irg, "_ifconv_hack");