3 * Make Mux nodes from Conds where it its possible.
4 * @author Sebastian Hack
11 #include "irgraph_t.h"
25 #include "bitfiddle.h"
30 * Mux optimization routines.
34 static ir_node *local_optimize_mux(ir_node *mux)
38 ir_node *sel = get_Mux_sel(mux);
39 ir_node *cmp = skip_Proj(sel);
41 /* Optimize the children */
42 for(i = 1, n = get_irn_arity(mux); i < n; ++i) {
43 ir_node *operand = get_irn_n(mux, i);
44 if(get_irn_op(operand) == op_Mux)
45 optimize_mux(operand);
48 /* If we have no cmp above the mux, get out. */
49 if(is_Proj(sel) && get_irn_mode(sel) == mode_b && get_irn_opcode(cmp) == iro_Cmp) {
51 pnc_number cc = get_Proj_proj(sel);
52 ir_mode *mode = get_irn_mode(mux);
53 ir_node *block = get_nodes_block(n);
54 ir_node *cmp_left = get_Cmp_left(cmp);
55 ir_node *cmp_right = get_Cmp_right(cmp);
56 ir_node *mux_true = get_Mux_true(mux);
57 ir_node *mux_false = get_Mux_false(mux);
60 * Check for comparisons with signed integers.
62 if(mode_is_int(mode) /* We need an integral mode */
63 && mode_is_signed(mode) /* which is signed */
64 && cc == Lt) { /* and have to compare for < */
67 * Mux(x:T < 0, -1, 0) -> Shrs(x, sizeof_bits(T) - 1)
71 if(classify_Const(cmp_right) == CNST_NULL
72 && classify_Const(mux_true) == CNST_ALL_ONE
73 && classify_Const(mux_false) == CNST_NULL) {
75 ir_mode *u_mode = find_unsigned_mode(mode);
77 res = new_r_Shrs(current_ir_graph, block, cmp_left,
78 new_r_Const_long(current_ir_graph, block, u_mode,
79 get_mode_size_bits(mode) - 1),
84 * Mux(0 < x:T, 1, 0) -> Shr(-x, sizeof_bits(T) - 1)
88 else if(classify_Const(cmp_left) == CNST_NULL
89 && classify_Const(mux_true) == CNST_ONE
90 && classify_Const(mux_false) == CNST_NULL) {
92 ir_mode *u_mode = find_unsigned_mode(mode);
94 res = new_r_Shr(current_ir_graph, block,
96 /* -x goes to 0 - x in Firm (cmp_left is 0, see the if) */
97 new_r_Sub(current_ir_graph, block, cmp_left, cmp_right, mode),
99 /* This is sizeof_bits(T) - 1 */
100 new_r_Const_long(current_ir_graph, block, u_mode,
101 get_mode_size_bits(mode) - 1),
112 * check, if a node is const and return its tarval or
113 * return a default tarval.
114 * @param cnst The node whose tarval to get.
115 * @param or The alternative tarval, if the node is no Const.
116 * @return The tarval of @p cnst, if the node is Const, @p otherwise.
118 static tarval *get_value_or(ir_node *cnst, tarval *or)
120 return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
125 * Try to optimize nested muxes into a dis- or conjunction
127 * @param mux The parent mux, which has muxes as operands.
128 * @return The replacement node for this mux. If the optimization is
129 * successful, this might be an And or Or node, if not, its the mux
132 static ir_node *optimize_mux_chain(ir_node *mux)
137 ir_mode *mode = get_irn_mode(mux);
142 * If we have no mux, or its mode is not integer, we
145 if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
149 null = get_tarval_null(mode);
150 minus_one = tarval_sub(null, get_tarval_one(mode));
152 ops[0] = get_Mux_false(mux);
153 ops[1] = get_Mux_true(mux);
155 for(i = 0; i < 2; ++i) {
157 tarval *tva, *tvb, *tvd;
161 * A mux operand at the first position can be factored
162 * out, if the operands fulfill several conditions:
164 * mux(c1, mux(c2, a, b), d)
166 * This can be made into:
167 * 1) mux(c1, 0, d) | mux(c2, a, b)
168 * if a | d == d and b | d == d
170 * 2) mux(c1, -1, d) & mux(c2, a, b)
171 * if a & d == d and a & b == b
173 if(get_irn_op(ops[i]) == op_Mux) {
176 a = get_Mux_false(child_mux);
177 b = get_Mux_true(child_mux);
180 /* Try the or stuff */
181 tva = get_value_or(a, minus_one);
182 tvb = get_value_or(b, minus_one);
183 tvd = get_value_or(d, null);
185 if(tarval_cmp(tarval_or(tva, tvd), tvd) == Eq
186 && tarval_cmp(tarval_or(tvb, tvd), tvd) == Eq) {
188 ops[i] = new_Const(mode, null);
189 res = new_r_Or(current_ir_graph, get_nodes_block(mux),
190 mux, child_mux, mode);
194 /* If the or didn't go, try the and stuff */
195 tva = get_value_or(a, null);
196 tvb = get_value_or(b, null);
197 tvd = get_value_or(d, minus_one);
199 if(tarval_cmp(tarval_and(tva, tvd), tvd) == Eq
200 && tarval_cmp(tarval_and(tvb, tvd), tvd) == Eq) {
202 ops[i] = new_Const(mode, minus_one);
203 res = new_r_And(current_ir_graph, get_nodes_block(mux),
204 mux, child_mux, mode);
210 /* recursively optimize nested muxes. */
211 set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
212 set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
218 /***********************************************************
219 * The If conversion itself.
220 ***********************************************************/
225 static opt_if_conv_info_t default_info = {
229 /** The debugging module. */
230 static firm_dbg_module_t *dbg;
233 * A small helper to indent strings.
235 static INLINE char *str_indent(char *buf, size_t len, int depth)
238 for(i = 0; i < depth && i < len - 1; ++i)
246 * A simple check for sde effects upton an opcode of a ir node.
247 * @param irn The ir node to check,
248 * @return 1 if the opcode itself may produce side effects, 0 if not.
250 static INLINE int has_side_effects(const ir_node *irn)
252 opcode opc = get_irn_opcode(irn);
257 return !mode_is_datab(get_irn_mode(irn));
261 * Decdies, if a given expression and its subexpressions
262 * (to certain, also given extent) can be moved to a block.
263 * @param expr The expression to examine.
264 * @param block The block where the expression should go.
265 * @param depth The current depth, passed recursively. Use 0 for
266 * non-recursive calls.
267 * @param max_depth The maximum depth to which the expression should be
270 static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, int max_depth)
274 ir_node *expr_block = get_nodes_block(expr);
278 * If we are forced to look too deep into the expression,
279 * treat it like it could not be moved.
281 if(depth >= max_depth) {
287 * We cannot move phis!
295 * If the block of the expression dominates the specified
296 * destination block, it does not matter if the expression
297 * has side effects or anything else. It is executed on each
298 * path the destination block is reached.
300 if(block_dominates(expr_block, dest_block))
304 * This should be superflous and could be converted into a assertion.
305 * The destination block _must_ dominate the block of the expression,
306 * else the expression could be used without its definition.
308 if(!block_dominates(dest_block, expr_block)) {
314 * Surely, if the expression does not have a data mode, it is not
315 * movable. Perhaps onw should also test the floating property of
318 if(has_side_effects(expr)) {
324 * If the node looks alright so far, look at its operands and
325 * check them out. If one of them cannot be moved, this one
326 * cannot be moved either.
328 for(i = 0, n = get_irn_arity(expr); i < n; ++i) {
329 ir_node *op = get_irn_n(expr, i);
330 int new_depth = is_Proj(op) ? depth : depth + 1;
331 if(!_can_move_to(op, dest_block, new_depth, max_depth)) {
338 DBG((dbg, LEVEL_5, "\t\t\tcan move to(%d) %n: %d\n", depth, expr, res));
344 * Convenience function for _can_move_to.
345 * Checks, if an expression can be moved to another block. The check can
346 * be limited to a expression depth meaning if we need to crawl in
347 * deeper into an expression than a given threshold to examine if
348 * it can be moved, the expression is rejected and the test returns
350 * @param expr The expression to check for.
351 * @param dest_block The destination block you want @p expr to be.
352 * @param max_depth The maximum depth @p expr should be investigated.
353 * @return 1, if the expression can be moved to the destination block,
356 static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, int max_depth)
358 return _can_move_to(expr, dest_block, 0, max_depth);
361 static void move_to(ir_node *expr, ir_node *dest_block)
364 ir_node *expr_block = get_nodes_block(expr);
367 * If we reached the dominator, we are done.
368 * We will never put code through the dominator
370 if(block_dominates(expr_block, dest_block))
373 for(i = 0, n = get_irn_arity(expr); i < n; ++i)
374 move_to(get_irn_n(expr, i), dest_block);
376 set_nodes_block(expr, dest_block);
380 * Information about a cond node.
382 typedef struct _cond_t {
383 ir_node *cond; /**< The cond node. */
384 ir_node *mux; /**< The mux node, that will be generated for this cond. */
387 * Information about the both 'branches'
388 * (true and false), the cond creates.
391 int pos; /**< Number of the predecessor of the
392 phi block by which this branch is
393 reached. It is -1, if this branch is
394 only reached through another cond. */
396 ir_node *masked_by; /**< If this cond's branch is only reached
397 through another cond, we store this
398 cond ir_node here. */
403 * Compare two conds for use in a firm set.
404 * Two cond_t's are equal, if they designate the same cond node.
406 * @param b Another one.
407 * @param size Not used.
408 * @return 0 (!) if they are equal, != 0 otherwise.
410 static int cond_cmp(const void *a, const void *b, size_t size)
414 return x->cond != y->cond;
420 static void _find_conds(ir_node *irn, ir_node *base_block, unsigned long visited_nr,
421 ir_node *dominator, ir_node *masked_by, int pos, int depth, set *conds)
426 block = get_nodes_block(irn);
428 if(block_dominates(dominator, block)) {
429 ir_node *cond = NULL;
432 /* check, if we're on a ProjX
434 * Further, the ProjX/Cond block must dominate the base block
435 * (the block with the phi in it), otherwise, the Cond
436 * is not affecting the phi so that a mux can be inserted.
438 if(is_Proj(irn) && get_irn_mode(irn) == mode_X
439 && block_dominates(block, base_block)) {
441 int proj = get_Proj_proj(irn);
442 cond = get_Proj_pred(irn);
444 /* Check, if the pred of the proj is a Cond
445 * with a Projb as selector.
447 if(get_irn_opcode(cond) == iro_Cond
448 && get_irn_mode(get_Cond_selector(cond)) == mode_b) {
457 /* get or insert the cond info into the set. */
458 res = set_insert(conds, &c, sizeof(c), HASH_PTR(cond));
461 * Link it to the cond ir_node. We need that later, since
462 * one cond masks the other we want to retreive the cond_t
463 * data from the masking cond ir_node.
465 set_irn_link(cond, res);
468 * Set masked by (either NULL or another cond node.
469 * If this cond is truly masked by another one, set
470 * the position of the actually investigated branch
471 * to -1. Since the cond is masked by another one,
472 * there could be more ways from the start block
473 * to this branch, so we choose -1.
475 res->cases[proj].masked_by = masked_by;
477 res->cases[proj].pos = pos;
479 DBG((dbg, LEVEL_5, "%>found cond %n (%s branch) for pos %d in block %n reached by %n\n",
480 depth, cond, get_Proj_proj(irn) ? "true" : "false", pos, block, masked_by));
485 * If this block has already been visited, don't recurse to its
488 if(get_Block_block_visited(block) < visited_nr) {
490 /* Mark the block visited. */
491 set_Block_block_visited(block, visited_nr);
493 /* Search recursively from this cond. */
494 for(i = 0, n = get_irn_arity(block); i < n; ++i) {
495 ir_node *pred = get_irn_n(block, i);
498 * If the depth is 0 (the first recursion), we set the pos to
499 * the current viewed predecessor, else we adopt the position
500 * as given by the caller. We also increase the depth for the
501 * recursively called functions.
503 _find_conds(pred, base_block, visited_nr, dominator, cond,
504 depth == 0 ? i : pos, depth + 1, conds);
511 * A convenience function for _find_conds.
512 * It sets some parameters needed for recursion to appropriate start
513 * values. Always use this function.
514 * @param irn The node to start looking for conds from. This might
515 * be the phi node we are investigating.
516 * @param dominator The dominator up to which we want to look for conds.
517 * @param conds The set to record the found conds in.
519 static INLINE void find_conds(ir_node *irn, ir_node *dominator, set *conds)
521 inc_irg_block_visited(current_ir_graph);
522 _find_conds(irn, get_nodes_block(irn), get_irg_block_visited(current_ir_graph),
523 dominator, NULL, 0, 0, conds);
528 * Make the mux for a given cond.
529 * @param phi The phi node which shall be replaced by a mux.
530 * @param dom The block where the muxes shall be placed.
531 * @param cond The cond information.
532 * @return The mux node made for this cond.
534 static ir_node *make_mux_on_demand(ir_node *phi, ir_node *dom, cond_t *cond, set *cond_set)
537 ir_node *projb = get_Cond_selector(cond->cond);
538 ir_node *operands[2];
540 for(i = 0; i < 2; ++i) {
543 * If this cond branch is masked by another cond, make the mux
544 * for that cond first, since the mux for this cond takes
547 if(cond->cases[i].masked_by) {
549 cond_t *masking_cond;
551 templ.cond = cond->cases[i].masked_by;
552 masking_cond = set_find(cond_set, &templ, sizeof(templ), HASH_PTR(templ.cond));
554 operands[i] = make_mux_on_demand(phi, dom, masking_cond, cond_set);
558 * If this cond branch is not masked by another cond, take
559 * the corresponding phi operand as an operand to the mux.
562 assert(cond->cases[i].pos >= 0);
563 operands[i] = get_irn_n(phi, cond->cases[i].pos);
566 /* Move the selected operand to the dominator block. */
567 move_to(operands[i], dom);
570 /* Move the comparison expression of the cond to the dominator. */
574 cond->mux = new_r_Mux(current_ir_graph, dom, projb,
575 operands[0], operands[1], get_irn_mode(operands[0]));
581 * Examine a phi node if it can be replaced by some muxes.
582 * @param irn A phi node.
583 * @param info Parameters for the if conversion algorithm.
585 static void check_out_phi(ir_node *irn, opt_if_conv_info_t *info)
587 int max_depth = info->max_depth;
596 cond_t *largest_cond;
603 block = get_nodes_block(irn);
604 arity = get_irn_arity(irn);
605 idom = get_Block_idom(block);
608 assert(get_irn_arity(irn) == get_irn_arity(block));
611 cond_set = get_irn_link(block);
612 assert(conds && "no cond set for this phi");
614 DBG((dbg, LEVEL_5, "phi candidate: %n\n", irn));
617 * Check, if we can move all operands of the
618 * phi node to the dominator. Else exit.
620 for(i = 0; i < arity; ++i) {
621 if(!can_move_to(get_irn_n(irn, i), idom, max_depth)) {
622 DBG((dbg, LEVEL_5, "cannot move operand %d of %n to %n\n", i, irn, idom));
627 n_conds = set_count(cond_set);
629 /* This should never happen and can be turned into an assertion */
631 DBG((dbg, LEVEL_5, "no conds found. how can this be?"));
636 * Put all cond information structures into an array.
637 * This is just done for convenience. It's not neccessary.
639 conds = alloca(n_conds * sizeof(conds[0]));
640 for(i = 0, cond = set_first(cond_set); cond; cond = set_next(cond_set))
644 * Check, if we can move the compare nodes of the conds to
647 for(i = 0; i < n_conds; ++i) {
648 ir_node *projb = get_Cond_selector(conds[i]->cond);
649 if(!can_move_to(projb, idom, max_depth)) {
650 DBG((dbg, LEVEL_5, "cannot move Projb %d of %n to %n\n", i, projb, idom));
656 * Find the largest cond (the one that dominates all others)
657 * and start the mux generation from there.
659 largest_cond = conds[0];
660 DBG((dbg, LEVEL_5, "\tlargest cond %n\n", largest_cond->cond));
661 for(i = 1; i < n_conds; ++i) {
662 ir_node *curr_largest_block = get_nodes_block(largest_cond->cond);
663 ir_node *bl = get_nodes_block(conds[i]->cond);
665 if(block_dominates(bl, curr_largest_block)) {
666 DBG((dbg, LEVEL_5, "\tnew largest cond %n\n", largest_cond->cond));
667 largest_cond = conds[i];
672 for(i = 0; i < n_conds; ++i) {
673 cond_t *c = conds[i];
674 DBG((dbg, LEVEL_5, "\tcond %n (t: (%d,%n), f: (%d,%n))\n", c->cond,
675 c->cases[1].pos, c->cases[1].masked_by,
676 c->cases[0].pos, c->cases[0].masked_by));
681 * Make the mux for the 'largest' cond. This will also
682 * produce all other muxes.
683 * @see make_mux_on_demand.
685 mux = make_mux_on_demand(irn, idom, largest_cond, cond_set);
688 * Try to optimize mux chains.
690 mux = optimize_mux_chain(mux);
693 * Set all preds of the phi node to the mux
694 * for the 'largest' cond.
696 for(i = 0; i < arity; ++i)
697 set_irn_n(irn, i, mux);
700 * optimize the phi away. This can anable further runs of this
701 * function. Look at _can_move. phis cannot be moved there.
703 nw = optimize_in_place_2(irn);
708 static void annotate_cond_info_pre(ir_node *irn, void *data)
710 set_irn_link(irn, NULL);
713 static void annotate_cond_info_post(ir_node *irn, void *data)
716 * Check, if the node is a phi
717 * we then compute a set of conds which are reachable from this
718 * phi's block up to its dominator.
719 * The set is attached to the blocks link field.
721 if(is_Phi(irn) && mode_is_datab(get_irn_mode(irn))) {
722 ir_node *block = get_nodes_block(irn);
724 set *conds = get_irn_link(block);
726 /* If the set is not yet computed, do it now. */
728 ir_node *idom = get_Block_idom(block);
729 conds = new_set(cond_cmp, log2_ceil(get_irn_arity(block)));
731 DBG((dbg, LEVEL_5, "searching conds at: %n up to: %n\n", irn, idom));
734 * Fill the set with conds we find on the way from
735 * the block to its dominator.
737 find_conds(irn, idom, conds);
740 * If there where no suitable conds, delete the set
741 * immediately and reset the set pointer to NULL
743 if(set_count(conds) == 0) {
749 set_irn_link(block, conds);
752 * If this phi node has a set of conds reachable, enqueue
753 * the phi node in a list with its link field.
754 * Then, we do not have to walk the graph again. We can
755 * use the list to reach all phi nodes for which if conversion
759 struct obstack *obst = data;
760 obstack_ptr_grow(obst, irn);
767 * Free the sets which are put at some blocks.
769 static void free_sets(ir_node *irn, void *data)
771 if(is_Block(irn) && get_irn_link(irn)) {
772 set *conds = get_irn_link(irn);
777 void opt_if_conv(ir_graph *irg, opt_if_conv_info_t *params)
783 opt_if_conv_info_t *p = params ? params : &default_info;
785 if(!get_opt_if_conversion())
790 /* Init the debug stuff. */
791 dbg = firm_dbg_register("firm.opt.ifconv");
792 firm_dbg_set_mask(dbg, 0);
794 /* Ensure, that the dominators are computed. */
797 DBG((dbg, LEVEL_4, "if conversion for irg %s(%p)\n",
798 get_entity_name(get_irg_entity(irg)), irg));
801 * Collect information about the conds pu the phis on an obstack.
802 * It is important that phi nodes which are 'higher' (with a
803 * lower dfs pre order) are in front of the obstack. Since they are
804 * possibly turned in to muxes this can enable the optimization
807 irg_walk_graph(irg, annotate_cond_info_pre, annotate_cond_info_post, &obst);
808 n_phis = obstack_object_size(&obst) / sizeof(phis[0]);
809 phis = obstack_finish(&obst);
811 /* Process each suitable phi found. */
812 for(i = 0; i < n_phis; ++i)
813 check_out_phi(phis[i], p);
816 irg_block_walk_graph(irg, free_sets, NULL, NULL);
818 obstack_free(&obst, NULL);