3 * Make Mux nodes from Conds where it its possible.
4 * @author Sebastian Hack
25 #include "irgraph_t.h"
41 #include "bitfiddle.h"
48 * check, if a node is const and return its tarval or
49 * return a default tarval.
50 * @param cnst The node whose tarval to get.
51 * @param or The alternative tarval, if the node is no Const.
52 * @return The tarval of @p cnst, if the node is Const, @p otherwise.
54 static tarval *get_value_or(ir_node *cnst, tarval *or)
56 return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
61 * Try to optimize nested muxes into a dis- or conjunction
63 * @param mux The parent mux, which has muxes as operands.
64 * @return The replacement node for this mux. If the optimization is
65 * successful, this might be an And or Or node, if not, its the mux
68 static ir_node *optimize_mux_chain(ir_node *mux)
73 ir_mode *mode = get_irn_mode(mux);
78 * If we have no mux, or its mode is not integer, we
81 if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
85 null = get_tarval_null(mode);
86 minus_one = tarval_sub(null, get_tarval_one(mode));
88 ops[0] = get_Mux_false(mux);
89 ops[1] = get_Mux_true(mux);
91 for(i = 0; i < 2; ++i) {
93 tarval *tva, *tvb, *tvd;
97 * A mux operand at the first position can be factored
98 * out, if the operands fulfill several conditions:
100 * mux(c1, mux(c2, a, b), d)
102 * This can be made into:
103 * 1) mux(c1, 0, d) | mux(c2, a, b)
104 * if a | d == d and b | d == d
106 * 2) mux(c1, -1, d) & mux(c2, a, b)
107 * if a & d == d and a & b == b
109 if(get_irn_op(ops[i]) == op_Mux) {
112 a = get_Mux_false(child_mux);
113 b = get_Mux_true(child_mux);
116 /* Try the or stuff */
117 tva = get_value_or(a, minus_one);
118 tvb = get_value_or(b, minus_one);
119 tvd = get_value_or(d, null);
121 if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
122 && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
124 ops[i] = new_Const(mode, null);
125 res = new_r_Or(current_ir_graph, get_nodes_block(mux),
126 mux, child_mux, mode);
130 /* If the or didn't go, try the and stuff */
131 tva = get_value_or(a, null);
132 tvb = get_value_or(b, null);
133 tvd = get_value_or(d, minus_one);
135 if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
136 && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
138 ops[i] = new_Const(mode, minus_one);
139 res = new_r_And(current_ir_graph, get_nodes_block(mux),
140 mux, child_mux, mode);
146 /* recursively optimize nested muxes. */
147 set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
148 set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
154 /***********************************************************
155 * The If conversion itself.
156 ***********************************************************/
161 static opt_if_conv_info_t default_info = {
165 /** The debugging module. */
166 static firm_dbg_module_t *dbg;
169 * A simple check for side effects upto an opcode of a ir node.
170 * @param irn The ir node to check,
171 * @return 1 if the opcode itself may produce side effects, 0 if not.
173 static INLINE int has_side_effects(const ir_node *irn)
175 ir_op *op = get_irn_op(irn);
180 return !mode_is_datab(get_irn_mode(irn));
183 enum failure_reason_t {
184 SUCCESS = IF_RESULT_SUCCESS,
185 TO_DEEP = IF_RESULT_TOO_DEEP,
186 SIDE_EFFECTS = IF_RESULT_SIDE_EFFECT,
187 PHI_FOUND = IF_RESULT_SIDE_EFFECT_PHI
191 * Decides, if a given expression and its subexpressions
192 * (to certain, also given extent) can be moved to a block.
194 * @param expr The expression to examine.
195 * @param block The block where the expression should go.
196 * @param depth The current depth, passed recursively. Use 0 for
197 * non-recursive calls.
198 * @param max_depth The maximum depth to which the expression should be
201 * @return a failure reason
203 static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, int max_depth)
207 ir_node *expr_block = get_nodes_block(expr);
210 * If we are forced to look too deep into the expression,
211 * treat it like it could not be moved.
213 if(depth >= max_depth) {
219 * If the block of the expression dominates the specified
220 * destination block, it does not matter if the expression
221 * has side effects or anything else. It is executed on each
222 * path the destination block is reached.
224 if (block_dominates(expr_block, dest_block))
228 * We cannot move phis!
236 * This should be superfluous and could be converted into a assertion.
237 * The destination block _must_ dominate the block of the expression,
238 * else the expression could be used without its definition.
240 if (! block_dominates(dest_block, expr_block)) {
241 res = IF_RESULT_SIDE_EFFECT;
246 * Surely, if the expression does not have a data mode, it is not
247 * movable. Perhaps one should also test the floating property of
250 if (has_side_effects(expr)) {
251 res = IF_RESULT_SIDE_EFFECT;
256 * If the node looks alright so far, look at its operands and
257 * check them out. If one of them cannot be moved, this one
258 * cannot be moved either.
260 for (i = 0, n = get_irn_arity(expr); i < n; ++i) {
261 ir_node *op = get_irn_n(expr, i);
262 int new_depth = is_Proj(op) ? depth : depth + 1;
264 res = _can_move_to(op, dest_block, new_depth, max_depth);
271 DBG((dbg, LEVEL_3, "\t\t\t%Dcan move to %n: %d\n", depth, expr, res));
277 * Convenience function for _can_move_to.
278 * Checks, if an expression can be moved to another block. The check can
279 * be limited to a expression depth meaning if we need to crawl in
280 * deeper into an expression than a given threshold to examine if
281 * it can be moved, the expression is rejected and the test returns
284 * @param expr The expression to check for.
285 * @param dest_block The destination block you want @p expr to be.
286 * @param max_depth The maximum depth @p expr should be investigated.
288 * @return return a failure reason
290 static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, int max_depth)
292 return _can_move_to(expr, dest_block, 0, max_depth);
296 * move a DAG given by a root node expr into a new block
298 * @param expr the root of a dag
299 * @param dest_block the destination block
301 static void move_to(ir_node *expr, ir_node *dest_block)
304 ir_node *expr_block = get_nodes_block(expr);
307 * If we reached the dominator, we are done.
308 * We will never put code through the dominator
310 if (block_dominates(expr_block, dest_block))
313 for (i = 0, n = get_irn_arity(expr); i < n; ++i)
314 move_to(get_irn_n(expr, i), dest_block);
316 set_nodes_block(expr, dest_block);
320 * return the common dominator of two blocks
322 static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2)
324 if(block_dominates(b1, b2))
326 else if(block_dominates(b2, b1))
331 for (p = get_Block_idom(b1); !block_dominates(p, b2); p = get_Block_idom(p));
337 * Information about a cond node.
339 typedef struct _cond_t {
340 ir_node *cond; /**< The cond node. */
341 struct list_head list; /**< List head which is used for queuing this cond
342 into the cond bunch it belongs to. */
344 unsigned totally_covers : 1;
345 struct _cond_t *link;
349 * Information about the both 'branches'
350 * (true and false), the cond creates.
353 int pos; /**< Number of the predecessor of the
354 phi block by which this branch is
355 reached. It is -1, if this branch is
356 only reached through another cond. */
358 struct _cond_t *masked_by; /**< If this cond's branch is only reached
359 through another cond, we store this
360 cond ir_node here. */
365 * retrieve the conditional information from a Cond node
367 static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
372 return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
376 typedef void (cond_walker_t)(cond_t *cond, void *env);
378 static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
379 long visited_nr, void *env)
383 if(cond->visited_nr >= visited_nr)
386 cond->visited_nr = visited_nr;
391 for(i = 0; i < 2; ++i) {
392 cond_t *c = cond->cases[i].masked_by;
395 _walk_conds(c, pre, post, visited_nr, env);
402 static long cond_visited_nr = 0;
404 static void walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post, void *env)
406 _walk_conds(cond, pre, post, ++cond_visited_nr, env);
409 static void link_conds(cond_t *cond, void *env)
411 cond_t **ptr = (cond_t **) env;
418 * Compare two conds for use in a firm set.
419 * Two cond_t's are equal, if they designate the same cond node.
421 * @param b Another one.
422 * @param size Not used.
423 * @return 0 (!) if they are equal, != 0 otherwise.
425 static int cond_cmp(const void *a, const void *b, size_t size)
429 return x->cond != y->cond;
433 * Information about conds which can be made to muxes.
434 * Instances of this struct are attached to the link field of
435 * blocks in which phis are located.
437 typedef struct _cond_info_t {
438 struct list_head list; /**< Used to list all of these structs per class. */
440 struct list_head roots; /**< A list of non-depending Conds. Two Conds are
441 independent, if it's not possible not reach one from the
442 other (all Conds in this list have to dominate the
443 block this struct is attached to). */
445 ir_node *first_phi; /**< The first phi node this cond info was made for. */
446 set *cond_set; /**< A set of all dominating reachable Conds. */
452 static void _find_conds(ir_node *irn, unsigned long visited_nr,
453 ir_node *dominator, cond_t *masked_by, int pos, int depth, cond_info_t *ci)
456 int saw_select_cond = 0;
458 block = get_nodes_block(irn);
461 * Only check this block if it is dominated by the specified
462 * dominator or it has not been visited yet.
464 if (block_dominates(dominator, block) && get_Block_block_visited(block) < visited_nr) {
465 cond_t *res = masked_by;
468 /* check, if we're on a ProjX
470 * Further, the ProjX/Cond block must dominate the base block
471 * (the block with the phi in it), otherwise, the Cond
472 * is not affecting the phi so that a mux can be inserted.
474 if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
476 int proj = get_Proj_proj(irn);
477 ir_node *cond = get_Proj_pred(irn);
479 /* true, if the mode is a mode_b cond _NO_ switch cond */
480 int is_modeb_cond = get_irn_opcode(cond) == iro_Cond
481 && get_irn_mode(get_Cond_selector(cond)) == mode_b;
483 saw_select_cond = !is_modeb_cond;
485 /* Check, if the pred of the proj is a Cond
486 * with a Projb as selector.
491 memset(&c, 0, sizeof(c));
497 /* get or insert the cond info into the set. */
498 res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
501 * If this cond is already masked by the masked_by cond
502 * return immediately, since we don't have anything to add.
504 if(masked_by && res->cases[proj].masked_by == masked_by)
509 list_add(&res->list, &ci->roots);
513 * Set masked by (either NULL or another cond node.
514 * If this cond is truly masked by another one, set
515 * the position of the actually investigated branch
516 * to -1. Since the cond is masked by another one,
517 * there could be more ways from the start block
518 * to this branch, so we choose -1.
520 res->cases[proj].masked_by = masked_by;
523 res->cases[proj].pos = pos;
526 * Since the masked_by nodes masks a cond, remove it from the
527 * root list of the conf trees.
530 assert(res->cases[proj].pos < 0);
531 list_del_init(&masked_by->list);
534 DBG((dbg, LEVEL_2, "%D%n (%s branch) "
535 "for pos %d in block %n reached by %n\n",
536 depth, cond, proj ? "true" : "false", pos,
537 block, masked_by ? masked_by->cond : NULL));
541 if(get_Block_block_visited(block) < visited_nr && !saw_select_cond) {
543 set_Block_block_visited(block, visited_nr);
545 /* Search recursively from this cond. */
546 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
547 ir_node *pred = get_irn_n(block, i);
550 * If the depth is 0 (the first recursion), we set the pos to
551 * the current viewed predecessor, else we adopt the position
552 * as given by the caller. We also increase the depth for the
553 * recursively called functions.
555 _find_conds(pred, visited_nr, dominator, res, pos, depth + (res != masked_by), ci);
563 * A convenience function for _find_conds.
564 * It sets some parameters needed for recursion to appropriate start
565 * values. Always use this function.
567 * @param irn The node to start looking for Conds from. This might
568 * be the phi node we are investigating.
569 * @param conds The set to record the found Conds in.
571 static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
574 unsigned long visited_nr;
575 ir_node *block = get_nodes_block(irn);
576 ir_node *dom = get_Block_idom(block);
578 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
579 ir_node *pred = get_irn_n(block, i);
581 inc_irg_block_visited(current_ir_graph);
582 visited_nr = get_irg_block_visited(current_ir_graph);
583 set_Block_block_visited(block, visited_nr);
585 DBG((dbg, LEVEL_2, "find conds at pred %d (%n) and idom %n\n", i, pred, dom));
586 _find_conds(pred, visited_nr, dom, NULL, i, 0, ci);
591 * Make the mux for a given cond.
592 * @param phi The phi node which shall be replaced by a mux.
593 * @param dom The block where the muxes shall be placed.
594 * @param cond The cond information.
595 * @return The mux node made for this cond.
597 static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond,
598 int max_depth, ir_node **mux, bitset_t *positions, int *muxes_made, long visited_nr)
601 ir_node *projb = get_Cond_selector(cond->cond);
602 ir_node *bl = get_nodes_block(cond->cond);
603 ir_node *operands[2];
606 cond->visited_nr = visited_nr;
607 DBG((dbg, LEVEL_2, "%n\n", cond->cond));
608 for(i = 0; i < 2; ++i) {
609 cond_t *masked_by = cond->cases[i].masked_by;
610 int pos = cond->cases[i].pos;
616 * If this Cond branch is masked by another cond, make the mux
617 * for that Cond first, since the Mux for this cond takes
622 DBG((dbg, LEVEL_2, "\tmasked by: %n\n", masked_by->cond));
623 if(masked_by->visited_nr < visited_nr)
624 operands[i] = make_mux_on_demand(phi, dom, masked_by, max_depth, mux, positions, muxes_made, visited_nr);
628 * If this cond branch is not masked by another cond, take
629 * the corresponding phi operand as an operand to the mux.
632 operands[i] = get_irn_n(phi, pos);
638 * Move the operands to the dominator block if the cond
639 * made sense. Some Conds found are not suitable for making a mux
640 * out of them, since one of their branches cannot be reached from
641 * the phi block. In that case we do not make a mux and return NULL.
643 if(operands[0] && operands[1]) {
644 if (operands[0] == operands[1]) {
645 /* there is no gain in using mux in this case, as
646 it will be optimized away. We will NOT move the
647 content of the blocks either
649 for (i = 0; i < 2; ++i)
651 bitset_set(positions, set[i]);
657 can_move[0] = can_move_to(operands[0], bl, max_depth);
658 can_move[1] = can_move_to(operands[1], bl, max_depth);
660 if (can_move[0] == SUCCESS && can_move[1] == SUCCESS) {
661 move_to(operands[0], bl);
662 move_to(operands[1], bl);
665 *mux = new_r_Mux(current_ir_graph, bl, projb,
666 operands[0], operands[1], get_irn_mode(operands[0]));
670 DBG((dbg, LEVEL_2, "\t%n(%n, %n, %n)[%d, %d]\n",
671 *mux, projb, operands[0], operands[1], set[0], set[1]));
673 for(i = 0; i < 2; ++i)
675 bitset_set(positions, set[i]);
677 /* we have done one */
678 hook_if_conversion(current_ir_graph, phi, set[i], *mux, IF_RESULT_SUCCESS);
682 if(can_move[0] != SUCCESS)
683 hook_if_conversion(current_ir_graph, phi, set[0], NULL, can_move[0]);
684 if(can_move[1] != SUCCESS)
685 hook_if_conversion(current_ir_graph, phi, set[1], NULL, can_move[1]);
690 hook_if_conversion(current_ir_graph, phi, set[0], NULL, IF_RESULT_BAD_CF);
692 hook_if_conversion(current_ir_graph, phi, set[1], NULL, IF_RESULT_BAD_CF);
698 typedef struct _phi_info_t {
699 struct list_head list;
700 cond_info_t *cond_info;
706 * Examine a phi node if it can be replaced by some muxes.
707 * @param irn A phi node.
708 * @param info Parameters for the if conversion algorithm.
710 static int check_out_phi(phi_info_t *phi_info, opt_if_conv_info_t *info)
712 int max_depth = info->max_depth;
713 ir_node *irn = phi_info->irn;
715 cond_info_t *cond_info = phi_info->cond_info;
721 block = get_nodes_block(irn);
722 arity = get_irn_arity(irn);
723 positions = bitset_alloca(arity);
726 assert(get_irn_arity(irn) == get_irn_arity(block));
729 DBG((dbg, LEVEL_2, "phi candidate: %n\n", irn));
731 list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
732 ir_node *cidom = block;
734 cond_t *p, *head = NULL;
737 bitset_clear_all(positions);
739 DBG((dbg, LEVEL_2, "\tcond root: %n\n", cond->cond));
741 * Link all conds which are in the subtree of
742 * the current cond in the list together.
744 walk_conds(cond, link_conds, NULL, &head);
747 for(p = head; p; p = p->link) {
748 for(i = 0; i < 2; ++i) {
749 int pos = p->cases[i].pos;
751 cidom = common_idom(cidom, get_nodes_block(get_irn_n(block, pos)));
755 DBG((dbg, LEVEL_2, "\tcommon idom: %n\n", cidom));
756 make_mux_on_demand(irn, cidom, cond, max_depth, &mux, positions, &muxes_made, ++cond_visited_nr);
759 bitset_foreach(positions, pos)
760 set_irn_n(irn, (int) pos, mux);
765 * optimize the phi away. This can anable further runs of this
766 * function. Look at _can_move. phis cannot be moved there.
768 nw = optimize_in_place_2(irn);
775 typedef struct _cond_walk_info_t {
776 struct obstack *obst;
777 struct list_head cond_info_head;
778 struct list_head phi_head;
782 static void annotate_cond_info_pre(ir_node *irn, void *data)
784 set_irn_link(irn, NULL);
787 static void annotate_cond_info_post(ir_node *irn, void *data)
789 cond_walk_info_t *cwi = data;
792 * Check, if the node is a phi
793 * we then compute a set of conds which are reachable from this
794 * phi's block up to its dominator.
795 * The set is attached to the blocks link field.
797 if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
798 ir_node *block = get_nodes_block(irn);
800 cond_info_t *ci = get_irn_link(block);
802 /* If the set is not yet computed, do it now. */
804 ci = obstack_alloc(cwi->obst, sizeof(*ci));
805 ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
808 INIT_LIST_HEAD(&ci->roots);
809 INIT_LIST_HEAD(&ci->list);
812 * Add this cond info to the list of all cond infos
813 * in this graph. This is just done to free the
814 * set easier afterwards (we save an irg_walk_graph).
816 list_add(&cwi->cond_info_head, &ci->list);
818 DBG((dbg, LEVEL_2, "searching conds at %n\n", irn));
821 * Fill the set with conds we find on the way from
822 * the block to its dominator.
827 * If there where no suitable conds, delete the set
828 * immediately and reset the set pointer to NULL
830 if(set_count(ci->cond_set) == 0) {
831 del_set(ci->cond_set);
833 obstack_free(cwi->obst, ci);
839 DBG((dbg, LEVEL_2, "conds already computed for %n (look at %n)\n", irn, ci->first_phi));
841 set_irn_link(block, ci);
844 phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
847 INIT_LIST_HEAD(&pi->list);
848 list_add(&pi->list, &cwi->phi_head);
854 static void dump_conds(cond_t *cond, void *env)
859 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n(%d, %d)\n%n\"}\n",
860 cond, cond->cond, cond->cases[0].pos, cond->cases[1].pos,
861 get_nodes_block(cond->cond));
863 for(i = 0; i < 2; ++i)
864 if(cond->cases[i].masked_by)
865 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\" label:\"%d\"}\n",
866 cond, cond->cases[i].masked_by, i);
869 static void vcg_dump_conds(ir_graph *irg, cond_walk_info_t *cwi)
874 snprintf(buf, sizeof(buf), "%s-conds.vcg", get_entity_name(get_irg_entity(irg)));
876 if((f = fopen(buf, "wt")) != NULL) {
881 ir_fprintf(f, "graph:{\ndisplay_edge_labels:yes\n");
882 list_for_each_entry(cond_info_t, ci, &cwi->cond_info_head, list) {
883 ir_fprintf(f, "node:{title:\"n%p\" label:\"cond info\"}\n", ci);
884 list_for_each_entry(cond_t, cond, &ci->roots, list) {
885 walk_conds(cond, NULL, dump_conds, f);
886 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", ci, cond);
890 list_for_each_entry(phi_info_t, phi, &cwi->phi_head, list) {
891 ir_fprintf(f, "node:{title:\"n%p\" label:\"%n\n%n\"}\n",
892 phi->irn, phi->irn, get_nodes_block(phi->irn));
893 ir_fprintf(f, "edge:{sourcename:\"n%p\" targetname:\"n%p\"}\n", phi->irn, phi->cond_info);
899 void opt_if_conv(ir_graph *irg, opt_if_conv_info_t *params)
903 phi_info_t *phi_info;
904 cond_info_t *cond_info;
905 cond_walk_info_t cwi;
907 opt_if_conv_info_t *p = params ? params : &default_info;
909 if(!get_opt_if_conversion())
915 INIT_LIST_HEAD(&cwi.cond_info_head);
916 INIT_LIST_HEAD(&cwi.phi_head);
918 /* Init the debug stuff. */
919 dbg = firm_dbg_register("firm.opt.ifconv");
921 firm_dbg_set_mask(dbg, LEVEL_1);
924 /* if-conversion works better with normalized returns */
925 normalize_one_return(irg);
927 /* Ensure, that the dominators are computed. */
930 DBG((dbg, LEVEL_1, "if conversion for irg %s(%p)\n",
931 get_entity_name(get_irg_entity(irg)), irg));
934 * Collect information about the conds pu the phis on an obstack.
935 * It is important that phi nodes which are 'higher' (with a
936 * lower dfs pre order) are in front of the obstack. Since they are
937 * possibly turned in to muxes this can enable the optimization
940 irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &cwi);
943 vcg_dump_conds(irg, &cwi);
946 /* Process each suitable phi found. */
947 list_for_each_entry(phi_info_t, phi_info, &cwi.phi_head, list) {
948 DBG((dbg, LEVEL_2, "phi node %n\n", phi_info->irn));
949 muxes_made += check_out_phi(phi_info, p);
952 list_for_each_entry(cond_info_t, cond_info, &cwi.cond_info_head, list) {
953 del_set(cond_info->cond_set);
956 DBG((dbg, LEVEL_1, "muxes made: %d\n", muxes_made));
958 obstack_free(&obst, NULL);