3 * Make Mux nodes from Conds where it its possible.
4 * @author Sebastian Hack
12 #include "irgraph_t.h"
27 #include "bitfiddle.h"
32 * Mux optimization routines.
36 static ir_node *local_optimize_mux(ir_node *mux)
40 ir_node *sel = get_Mux_sel(mux);
41 ir_node *cmp = skip_Proj(sel);
43 /* Optimize the children */
44 for(i = 1, n = get_irn_arity(mux); i < n; ++i) {
45 ir_node *operand = get_irn_n(mux, i);
46 if(get_irn_op(operand) == op_Mux)
47 optimize_mux(operand);
50 /* If we have no cmp above the mux, get out. */
51 if(is_Proj(sel) && get_irn_mode(sel) == mode_b && get_irn_opcode(cmp) == iro_Cmp) {
53 pn_Cmp cc = get_Proj_proj(sel);
54 ir_mode *mode = get_irn_mode(mux);
55 ir_node *block = get_nodes_block(n);
56 ir_node *cmp_left = get_Cmp_left(cmp);
57 ir_node *cmp_right = get_Cmp_right(cmp);
58 ir_node *mux_true = get_Mux_true(mux);
59 ir_node *mux_false = get_Mux_false(mux);
62 * Check for comparisons with signed integers.
64 if(mode_is_int(mode) /* We need an integral mode */
65 && mode_is_signed(mode) /* which is signed */
66 && cc == Lt) { /* and have to compare for < */
69 * Mux(x:T < 0, -1, 0) -> Shrs(x, sizeof_bits(T) - 1)
73 if(classify_Const(cmp_right) == CNST_NULL
74 && classify_Const(mux_true) == CNST_ALL_ONE
75 && classify_Const(mux_false) == CNST_NULL) {
77 ir_mode *u_mode = find_unsigned_mode(mode);
79 res = new_r_Shrs(current_ir_graph, block, cmp_left,
80 new_r_Const_long(current_ir_graph, block, u_mode,
81 get_mode_size_bits(mode) - 1),
86 * Mux(0 < x:T, 1, 0) -> Shr(-x, sizeof_bits(T) - 1)
90 else if(classify_Const(cmp_left) == CNST_NULL
91 && classify_Const(mux_true) == CNST_ONE
92 && classify_Const(mux_false) == CNST_NULL) {
94 ir_mode *u_mode = find_unsigned_mode(mode);
96 res = new_r_Shr(current_ir_graph, block,
98 /* -x goes to 0 - x in Firm (cmp_left is 0, see the if) */
99 new_r_Sub(current_ir_graph, block, cmp_left, cmp_right, mode),
101 /* This is sizeof_bits(T) - 1 */
102 new_r_Const_long(current_ir_graph, block, u_mode,
103 get_mode_size_bits(mode) - 1),
114 * check, if a node is const and return its tarval or
115 * return a default tarval.
116 * @param cnst The node whose tarval to get.
117 * @param or The alternative tarval, if the node is no Const.
118 * @return The tarval of @p cnst, if the node is Const, @p otherwise.
120 static tarval *get_value_or(ir_node *cnst, tarval *or)
122 return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
127 * Try to optimize nested muxes into a dis- or conjunction
129 * @param mux The parent mux, which has muxes as operands.
130 * @return The replacement node for this mux. If the optimization is
131 * successful, this might be an And or Or node, if not, its the mux
134 static ir_node *optimize_mux_chain(ir_node *mux)
139 ir_mode *mode = get_irn_mode(mux);
144 * If we have no mux, or its mode is not integer, we
147 if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
151 null = get_tarval_null(mode);
152 minus_one = tarval_sub(null, get_tarval_one(mode));
154 ops[0] = get_Mux_false(mux);
155 ops[1] = get_Mux_true(mux);
157 for(i = 0; i < 2; ++i) {
159 tarval *tva, *tvb, *tvd;
163 * A mux operand at the first position can be factored
164 * out, if the operands fulfill several conditions:
166 * mux(c1, mux(c2, a, b), d)
168 * This can be made into:
169 * 1) mux(c1, 0, d) | mux(c2, a, b)
170 * if a | d == d and b | d == d
172 * 2) mux(c1, -1, d) & mux(c2, a, b)
173 * if a & d == d and a & b == b
175 if(get_irn_op(ops[i]) == op_Mux) {
178 a = get_Mux_false(child_mux);
179 b = get_Mux_true(child_mux);
182 /* Try the or stuff */
183 tva = get_value_or(a, minus_one);
184 tvb = get_value_or(b, minus_one);
185 tvd = get_value_or(d, null);
187 if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
188 && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
190 ops[i] = new_Const(mode, null);
191 res = new_r_Or(current_ir_graph, get_nodes_block(mux),
192 mux, child_mux, mode);
196 /* If the or didn't go, try the and stuff */
197 tva = get_value_or(a, null);
198 tvb = get_value_or(b, null);
199 tvd = get_value_or(d, minus_one);
201 if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
202 && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
204 ops[i] = new_Const(mode, minus_one);
205 res = new_r_And(current_ir_graph, get_nodes_block(mux),
206 mux, child_mux, mode);
212 /* recursively optimize nested muxes. */
213 set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
214 set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
220 /***********************************************************
221 * The If conversion itself.
222 ***********************************************************/
227 static opt_if_conv_info_t default_info = {
231 /** The debugging module. */
232 static firm_dbg_module_t *dbg;
235 * A simple check for sde effects upton an opcode of a ir node.
236 * @param irn The ir node to check,
237 * @return 1 if the opcode itself may produce side effects, 0 if not.
239 static INLINE int has_side_effects(const ir_node *irn)
241 opcode opc = get_irn_opcode(irn);
246 return !mode_is_datab(get_irn_mode(irn));
250 * Decdies, if a given expression and its subexpressions
251 * (to certain, also given extent) can be moved to a block.
252 * @param expr The expression to examine.
253 * @param block The block where the expression should go.
254 * @param depth The current depth, passed recursively. Use 0 for
255 * non-recursive calls.
256 * @param max_depth The maximum depth to which the expression should be
259 static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, int max_depth)
263 ir_node *expr_block = get_nodes_block(expr);
267 * If we are forced to look too deep into the expression,
268 * treat it like it could not be moved.
270 if(depth >= max_depth) {
276 * If the block of the expression dominates the specified
277 * destination block, it does not matter if the expression
278 * has side effects or anything else. It is executed on each
279 * path the destination block is reached.
281 if(block_dominates(expr_block, dest_block))
285 * We cannot move phis!
293 * This should be superflous and could be converted into a assertion.
294 * The destination block _must_ dominate the block of the expression,
295 * else the expression could be used without its definition.
297 if(!block_dominates(dest_block, expr_block)) {
303 * Surely, if the expression does not have a data mode, it is not
304 * movable. Perhaps onw should also test the floating property of
307 if(has_side_effects(expr)) {
313 * If the node looks alright so far, look at its operands and
314 * check them out. If one of them cannot be moved, this one
315 * cannot be moved either.
317 for(i = 0, n = get_irn_arity(expr); i < n; ++i) {
318 ir_node *op = get_irn_n(expr, i);
319 int new_depth = is_Proj(op) ? depth : depth + 1;
320 if(!_can_move_to(op, dest_block, new_depth, max_depth)) {
327 DBG((dbg, LEVEL_5, "\t\t\t%Dcan move to %n: %d\n", depth, expr, res));
333 * Convenience function for _can_move_to.
334 * Checks, if an expression can be moved to another block. The check can
335 * be limited to a expression depth meaning if we need to crawl in
336 * deeper into an expression than a given threshold to examine if
337 * it can be moved, the expression is rejected and the test returns
339 * @param expr The expression to check for.
340 * @param dest_block The destination block you want @p expr to be.
341 * @param max_depth The maximum depth @p expr should be investigated.
342 * @return 1, if the expression can be moved to the destination block,
345 static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, int max_depth)
347 return _can_move_to(expr, dest_block, 0, max_depth);
350 static void move_to(ir_node *expr, ir_node *dest_block)
353 ir_node *expr_block = get_nodes_block(expr);
356 * If we reached the dominator, we are done.
357 * We will never put code through the dominator
359 if(block_dominates(expr_block, dest_block))
362 for(i = 0, n = get_irn_arity(expr); i < n; ++i)
363 move_to(get_irn_n(expr, i), dest_block);
365 set_nodes_block(expr, dest_block);
368 static ir_node *common_idom(ir_node *b1, ir_node *b2)
370 if(block_dominates(b1, b2))
372 else if(block_dominates(b2, b1))
377 for(p = b1; !block_dominates(p, b2); p = get_Block_idom(p));
383 * Information about a cond node.
385 typedef struct _cond_t {
386 ir_node *cond; /**< The cond node. */
387 ir_node *mux; /**< The mux node, that will be generated for this cond. */
388 struct list_head list; /**< List head which is used for queueing this cond
389 into the cond bunch it belongs to. */
390 unsigned in_list : 1;
391 struct _cond_t *link;
395 * Information about the both 'branches'
396 * (true and false), the cond creates.
399 int pos; /**< Number of the predecessor of the
400 phi block by which this branch is
401 reached. It is -1, if this branch is
402 only reached through another cond. */
404 ir_node *masked_by; /**< If this cond's branch is only reached
405 through another cond, we store this
406 cond ir_node here. */
410 static INLINE cond_t *get_cond(ir_node *irn, set *cond_set)
415 return set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
419 typedef void (cond_walker_t)(cond_t *cond, void *env);
421 static void _walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
422 long visited_nr, set *cond_set, void *env)
426 if(cond->visited_nr >= visited_nr)
429 cond->visited_nr = visited_nr;
434 for(i = 0; i < 2; ++i) {
435 cond_t *c = get_cond(cond->cases[i].masked_by, cond_set);
438 _walk_conds(c, pre, post, visited_nr, cond_set, env);
445 static void walk_conds(cond_t *cond, cond_walker_t *pre, cond_walker_t *post,
446 set *cond_set, void *env)
448 static long visited_nr = 0;
450 _walk_conds(cond, pre, post, ++visited_nr, cond_set, env);
453 static void link_conds(cond_t *cond, void *env)
455 cond_t **ptr = (cond_t **) env;
462 * Compare two conds for use in a firm set.
463 * Two cond_t's are equal, if they designate the same cond node.
465 * @param b Another one.
466 * @param size Not used.
467 * @return 0 (!) if they are equal, != 0 otherwise.
469 static int cond_cmp(const void *a, const void *b, size_t size)
473 return x->cond != y->cond;
477 * Information about conds which can be made to muxes.
478 * Instances of this struct are attached to the link field of
479 * blocks in which phis are located.
481 typedef struct _cond_info_t {
482 struct list_head list; /**< Used to list all of these structs per class. */
484 struct list_head roots; /**< A list of non-depending conds. Two conds are
485 independent, if yot can not reach the one from the
486 other (all conds in this list have to dominate the
487 block this struct is attached to. */
489 set *cond_set; /**< A set of all dominating reachable conds. */
495 static void _find_conds(ir_node *irn, ir_node *base_block, long visited_nr,
496 ir_node *dominator, ir_node *masked_by, int pos, int depth, cond_info_t *ci)
500 block = get_nodes_block(irn);
502 if(block_dominates(dominator, block)) {
503 ir_node *cond = NULL;
506 /* check, if we're on a ProjX
508 * Further, the ProjX/Cond block must dominate the base block
509 * (the block with the phi in it), otherwise, the Cond
510 * is not affecting the phi so that a mux can be inserted.
512 if(is_Proj(irn) && get_irn_mode(irn) == mode_X) {
514 int proj = get_Proj_proj(irn);
515 cond = get_Proj_pred(irn);
517 /* Check, if the pred of the proj is a Cond
518 * with a Projb as selector.
520 if(get_irn_opcode(cond) == iro_Cond
521 && get_irn_mode(get_Cond_selector(cond)) == mode_b) {
525 memset(&c, 0, sizeof(c));
527 INIT_LIST_HEAD(&c.list);
531 /* get or insert the cond info into the set. */
532 res = set_insert(ci->cond_set, &c, sizeof(c), HASH_PTR(cond));
536 list_add(&res->list, &ci->roots);
540 * Link it to the cond ir_node. We need that later, since
541 * one cond masks the other we want to retreive the cond_t
542 * data from the masking cond ir_node.
544 set_irn_link(cond, res);
547 * Set masked by (either NULL or another cond node.
548 * If this cond is truly masked by another one, set
549 * the position of the actually investigated branch
550 * to -1. Since the cond is masked by another one,
551 * there could be more ways from the start block
552 * to this branch, so we choose -1.
554 res->cases[proj].masked_by = masked_by;
556 res->cases[proj].pos = pos;
559 * Since the masked_by nodes masks a cond, remove it from the
560 * root list of the conf trees.
563 cond_t *m = get_cond(masked_by, ci->cond_set);
564 struct list_head *list = &m->list;
567 * If this cond was not removed before,
568 * remove it now from the list.
570 if(!list_empty(list))
574 DBG((dbg, LEVEL_5, "%{firm:indent}found cond %n (%s branch) "
575 "for pos %d in block %n reached by %n\n",
576 depth, cond, get_Proj_proj(irn) ? "true" : "false", pos, block, masked_by));
580 * We set cond to NULL if the cond was an switch cond, since it is
581 * passed (as the masked_by argument) to recursive calls to this
582 * function. We do not consider switch conds as masking conds for
589 if(get_Block_block_visited(block) < visited_nr) {
591 set_Block_block_visited(block, visited_nr);
593 /* Search recursively from this cond. */
594 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
595 ir_node *pred = get_irn_n(block, i);
598 * If the depth is 0 (the first recursion), we set the pos to
599 * the current viewed predecessor, else we adopt the position
600 * as given by the caller. We also increase the depth for the
601 * recursively called functions.
603 _find_conds(pred, base_block, visited_nr, dominator, cond, pos, depth + 1, ci);
611 * A convenience function for _find_conds.
612 * It sets some parameters needed for recursion to appropriate start
613 * values. Always use this function.
614 * @param irn The node to start looking for conds from. This might
615 * be the phi node we are investigating.
616 * @param conds The set to record the found conds in.
618 static INLINE void find_conds(ir_node *irn, cond_info_t *ci)
622 ir_node *block = get_nodes_block(irn);
624 inc_irg_block_visited(current_ir_graph);
625 visited_nr = get_irg_block_visited(current_ir_graph);
627 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
628 ir_node *pred = get_irn_n(block, i);
629 ir_node *pred_block = get_nodes_block(pred);
630 ir_node *dom = get_Block_idom(pred_block);
633 * If the pred_block is the start block, its idom is NULL
634 * so we treat the block itself as its immediate dominator.
639 _find_conds(pred, pred_block, visited_nr, dom, NULL, i, 0, ci);
645 * Make the mux for a given cond.
646 * @param phi The phi node which shall be replaced by a mux.
647 * @param dom The block where the muxes shall be placed.
648 * @param cond The cond information.
649 * @return The mux node made for this cond.
651 static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond, set *cond_set)
654 ir_node *projb = get_Cond_selector(cond->cond);
655 ir_node *operands[2];
661 for(i = 0; i < 2; ++i) {
664 * If this cond branch is masked by another cond, make the mux
665 * for that cond first, since the mux for this cond takes
668 if(cond->cases[i].masked_by) {
670 cond_t *masking_cond;
672 templ.cond = cond->cases[i].masked_by;
673 masking_cond = set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
675 operands[i] = make_mux_on_demand(phi, dom, masking_cond, cond_set);
679 * If this cond branch is not masked by another cond, take
680 * the corresponding phi operand as an operand to the mux.
683 if(cond->cases[i].pos >= 0)
684 operands[i] = get_irn_n(phi, cond->cases[i].pos);
689 * Move the operands to the dominator block if the cond
690 * made sense. Some conds found are not suitable for making a mux
691 * out of them, since one of their branches cannot be reached from
692 * the phi block. In that case we do not make a mux and return NULL.
694 if(operands[0] && operands[1]) {
695 move_to(operands[0], dom);
696 move_to(operands[1], dom);
700 cond->mux = new_r_Mux(current_ir_graph, dom, projb,
701 operands[0], operands[1], get_irn_mode(operands[0]));
707 typedef struct _phi_info_t {
708 struct list_head list;
709 cond_info_t *cond_info;
715 * Examine a phi node if it can be replaced by some muxes.
716 * @param irn A phi node.
717 * @param info Parameters for the if conversion algorithm.
719 static void check_out_phi(phi_info_t *phi_info, opt_if_conv_info_t *info)
721 int max_depth = info->max_depth;
723 ir_node *irn = phi_info->irn;
725 cond_info_t *cond_info = phi_info->cond_info;
729 set *cond_set = cond_info->cond_set;
732 block = get_nodes_block(irn);
733 arity = get_irn_arity(irn);
736 assert(get_irn_arity(irn) == get_irn_arity(block));
739 positions = bitset_alloca(arity);
741 DBG((dbg, LEVEL_5, "phi candidate: %n\n", irn));
743 list_for_each_entry(cond_t, cond, &cond_info->roots, list) {
745 ir_node *cidom = get_nodes_block(cond->cond);
747 cond_t *p, *head = NULL;
749 DBG((dbg, LEVEL_5, "\tcond root: %n\n", cond->cond));
751 /* clear the position array. */
752 bitset_clear_all(positions);
755 * Link all conds which are in the subtree of
756 * the current cond in the list together.
758 walk_conds(cond, link_conds, NULL, cond_set, &head);
760 for(p = head, n = 0; p; p = p->link)
761 cidom = common_idom(cidom, get_nodes_block(p->cond));
763 DBG((dbg, LEVEL_5, "\tcommon idom: %n\n", cidom));
765 for(p = head, n = 0; p && !cannot_move; p = p->link) {
767 if(!can_move_to(get_Cond_selector(p->cond), cidom, max_depth)) {
768 DBG((dbg, LEVEL_5, "\tcannot move selector of %n\n", p->cond));
773 for(i = 0; i < 2; ++i) {
774 int pos = p->cases[i].pos;
777 bitset_set(positions, pos);
779 if(!can_move_to(get_irn_n(irn, pos), cidom, max_depth)) {
781 DBG((dbg, LEVEL_5, "\tcannot move phi operand %d\n", pos));
785 DBG((dbg, LEVEL_5, "\tcan move phi operand %d\n", pos));
791 * If all operands and the cond condition can be moved to
792 * the common immediate dominator, move them there, make a
793 * mux and associate the corresponding phi operands with
797 ir_node *mux = make_mux_on_demand(irn, cidom, cond, cond_info->cond_set);
799 /* If a mux could be made, associate the phi operands with it. */
800 DBG((dbg, LEVEL_5, "\tassociating:\n"));
803 bitset_foreach(positions, elm) {
804 DBG((dbg, LEVEL_5, "\t\t%d\n", positions[i]));
805 set_irn_n(irn, (int) elm, mux);
812 * optimize the phi away. This can anable further runs of this
813 * function. Look at _can_move. phis cannot be moved there.
815 nw = optimize_in_place_2(irn);
820 typedef struct _cond_walk_info_t {
821 struct obstack *obst;
822 struct list_head cond_info_head;
823 struct list_head phi_head;
827 static void annotate_cond_info_pre(ir_node *irn, void *data)
829 set_irn_link(irn, NULL);
832 static void annotate_cond_info_post(ir_node *irn, void *data)
834 cond_walk_info_t *cwi = data;
837 * Check, if the node is a phi
838 * we then compute a set of conds which are reachable from this
839 * phi's block up to its dominator.
840 * The set is attached to the blocks link field.
842 if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
843 ir_node *block = get_nodes_block(irn);
845 cond_info_t *ci = get_irn_link(block);
847 /* If the set is not yet computed, do it now. */
849 ci = obstack_alloc(cwi->obst, sizeof(*ci));
850 ci->cond_set = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
851 INIT_LIST_HEAD(&ci->roots);
852 INIT_LIST_HEAD(&ci->list);
855 * Add this cond info to the list of all cond infos
856 * in this graph. This is just done to free the
857 * set easier afterwards (we save an irg_walk_graph).
859 list_add(&cwi->cond_info_head, &ci->list);
861 DBG((dbg, LEVEL_5, "searching conds at %n\n", irn));
864 * Fill the set with conds we find on the way from
865 * the block to its dominator.
870 * If there where no suitable conds, delete the set
871 * immediately and reset the set pointer to NULL
873 if(set_count(ci->cond_set) == 0) {
874 del_set(ci->cond_set);
876 obstack_free(cwi->obst, ci);
881 DBG((dbg, LEVEL_5, "conds already computed for %n\n", irn));
883 set_irn_link(block, ci);
886 phi_info_t *pi = obstack_alloc(cwi->obst, sizeof(*pi));
889 INIT_LIST_HEAD(&pi->list);
890 list_add(&pi->list, &cwi->phi_head);
898 * Free the sets which are put at some blocks.
900 static void free_sets(ir_node *irn, void *data)
902 if(is_Block(irn) && get_irn_link(irn)) {
903 set *conds = get_irn_link(irn);
909 void opt_if_conv(ir_graph *irg, opt_if_conv_info_t *params)
912 phi_info_t *phi_info;
913 cond_info_t *cond_info;
914 cond_walk_info_t cwi;
916 opt_if_conv_info_t *p = params ? params : &default_info;
918 if(!get_opt_if_conversion())
924 INIT_LIST_HEAD(&cwi.cond_info_head);
925 INIT_LIST_HEAD(&cwi.phi_head);
927 /* Init the debug stuff. */
928 dbg = firm_dbg_register("firm.opt.ifconv");
929 firm_dbg_set_mask(dbg, 0);
931 /* Ensure, that the dominators are computed. */
934 DBG((dbg, LEVEL_4, "if conversion for irg %s(%p)\n",
935 get_entity_name(get_irg_entity(irg)), irg));
938 * Collect information about the conds pu the phis on an obstack.
939 * It is important that phi nodes which are 'higher' (with a
940 * lower dfs pre order) are in front of the obstack. Since they are
941 * possibly turned in to muxes this can enable the optimization
944 irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &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_4, "phi node %n\n", phi_info->irn));
949 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 obstack_free(&obst, NULL);