-#ifdef HAVE_STRING_H
-#include <string.h>
-#endif
-#ifdef HAVE_ALLOCA_H
-#include <alloca.h>
-#endif
-
-#include "irgraph_t.h"
-#include "irnode_t.h"
-#include "irgwalk.h"
-#include "iropt_t.h"
-#include "irgmod.h"
-#include "irmode_t.h"
-#include "ircons_t.h"
-#include "irdom_t.h"
-#include "irgwalk.h"
-
-#include "ifconv.h"
-#include "irflag_t.h"
-
-#include "irprintf.h"
-#include "debug.h"
-#include "obst.h"
-#include "set.h"
-#include "bitset.h"
-#include "bitfiddle.h"
-#include "irhooks.h"
-#include "return.h"
-
-#define MAX_DEPTH 4
-
-/**
- * check, if a node is const and return its tarval or
- * return a default tarval.
- * @param cnst The node whose tarval to get.
- * @param or The alternative tarval, if the node is no Const.
- * @return The tarval of @p cnst, if the node is Const, @p otherwise.
- */
-static tarval *get_value_or(ir_node *cnst, tarval *or)
-{
- return get_irn_op(cnst) == op_Const ? get_Const_tarval(cnst) : or;
-}
-
-
-/**
- * Try to optimize nested muxes into a dis- or conjunction
- * of two muxes.
- * @param mux The parent mux, which has muxes as operands.
- * @return The replacement node for this mux. If the optimization is
- * successful, this might be an And or Or node, if not, its the mux
- * himself.
- */
-static ir_node *optimize_mux_chain(ir_node *mux)
-{
- int i;
- ir_node *res;
- ir_node *ops[2];
- ir_mode *mode = get_irn_mode(mux);
- tarval *null;
- tarval *minus_one;
-
- /*
- * If we have no mux, or its mode is not integer, we
- * can return.
- */
- if(get_irn_op(mux) != op_Mux || !mode_is_int(mode))
- return mux;
-
- res = mux;
- null = get_mode_null(mode);
- minus_one = tarval_sub(null, get_tarval_one(mode));
-
- ops[0] = get_Mux_false(mux);
- ops[1] = get_Mux_true(mux);
-
- for(i = 0; i < 2; ++i) {
- ir_node *a, *b, *d;
- tarval *tva, *tvb, *tvd;
- ir_node *child_mux;
-
- /*
- * A mux operand at the first position can be factored
- * out, if the operands fulfill several conditions:
- *
- * mux(c1, mux(c2, a, b), d)
- *
- * This can be made into:
- * 1) mux(c1, 0, d) | mux(c2, a, b)
- * if a | d == d and b | d == d
- *
- * 2) mux(c1, -1, d) & mux(c2, a, b)
- * if a & d == d and a & b == b
- */
- if(get_irn_op(ops[i]) == op_Mux) {
-
- child_mux = ops[i];
- a = get_Mux_false(child_mux);
- b = get_Mux_true(child_mux);
- d = ops[1 - i];
-
- /* Try the or stuff */
- tva = get_value_or(a, minus_one);
- tvb = get_value_or(b, minus_one);
- tvd = get_value_or(d, null);
-
- if(tarval_cmp(tarval_or(tva, tvd), tvd) == pn_Cmp_Eq
- && tarval_cmp(tarval_or(tvb, tvd), tvd) == pn_Cmp_Eq) {
-
- ops[i] = new_Const(mode, null);
- res = new_r_Or(current_ir_graph, get_nodes_block(mux),
- mux, child_mux, mode);
- break;
- }
-
- /* If the or didn't go, try the and stuff */
- tva = get_value_or(a, null);
- tvb = get_value_or(b, null);
- tvd = get_value_or(d, minus_one);
-
- if(tarval_cmp(tarval_and(tva, tvd), tvd) == pn_Cmp_Eq
- && tarval_cmp(tarval_and(tvb, tvd), tvd) == pn_Cmp_Eq) {
-
- ops[i] = new_Const(mode, minus_one);
- res = new_r_And(current_ir_graph, get_nodes_block(mux),
- mux, child_mux, mode);
- break;
- }
- }
- }
-
- /* recursively optimize nested muxes. */
- set_irn_n(mux, 1, optimize_mux_chain(ops[0]));
- set_irn_n(mux, 2, optimize_mux_chain(ops[1]));
-
- return res;
-}
-
-
-/***********************************************************
- * The If conversion itself.
- ***********************************************************/
-
-/** allow every Mux to be created. */
-static int default_allow_mux(ir_node *sel, ir_node *false_res, ir_node *true_res) {
- return 1;
-}
-
-/**
- * Default options.
- */
-static const opt_if_conv_info_t default_info = {
- MAX_DEPTH,
- default_allow_mux
-};
-
-/** The debugging module. */
-DEBUG_ONLY(static firm_dbg_module_t *dbg;)
-
-/**
- * A simple check for side effects upto an opcode of a ir node.
- * @param irn The ir node to check,
- * @return 1 if the opcode itself may produce side effects, 0 if not.
- */
-static INLINE int has_side_effects(const ir_node *irn)
-{
- ir_op *op = get_irn_op(irn);
-
- if (op == op_Cmp)
- return 0;
-
- return !mode_is_datab(get_irn_mode(irn));
-}
-
-/**
- * Possible failure reasons
- */
-enum failure_reason_t {
- SUCCESS = IF_RESULT_SUCCESS,
- TO_DEEP = IF_RESULT_TOO_DEEP,
- SIDE_EFFECTS = IF_RESULT_SIDE_EFFECT,
- PHI_FOUND = IF_RESULT_SIDE_EFFECT_PHI,
- DENIED = IF_RESULT_DENIED
-};
-
-/**
- * Decides, if a given expression and its subexpressions
- * (to certain, also given extent) can be moved to a block.
- *
- * @param expr The expression to examine.
- * @param block The block where the expression should go.
- * @param depth The current depth, passed recursively. Use 0 for
- * non-recursive calls.
- * @param info The options for createing Mux nodes.
- * examined.
- *
- * @return a failure reason
- */
-static int _can_move_to(ir_node *expr, ir_node *dest_block, int depth, const opt_if_conv_info_t *info)
-{
- int i, n;
- int res = SUCCESS;
- ir_node *expr_block = get_nodes_block(expr);
-
- /*
- * If we are forced to look too deep into the expression,
- * treat it like it could not be moved.
- */
- if(depth >= info->max_depth) {
- res = TO_DEEP;
- goto end;
- }
-
- /*
- * If the block of the expression dominates the specified
- * destination block, it does not matter if the expression
- * has side effects or anything else. It is executed on each
- * path the destination block is reached.
- */
- if (block_dominates(expr_block, dest_block))
- goto end;
-
- /*
- * We cannot move phis!
- */
- if (is_Phi(expr)) {
- res = PHI_FOUND;
- goto end;
- }
-
- /*
- * This should be superfluous and could be converted into a assertion.
- * The destination block _must_ dominate the block of the expression,
- * else the expression could be used without its definition.
- */
- if (! block_dominates(dest_block, expr_block)) {
- res = IF_RESULT_SIDE_EFFECT;
- goto end;
- }
-
- /*
- * Surely, if the expression does not have a data mode, it is not
- * movable. Perhaps one should also test the floating property of
- * the opcode/node.
- */
- if (has_side_effects(expr)) {
- res = IF_RESULT_SIDE_EFFECT;
- goto end;
- }
-
- /*
- * If the node looks alright so far, look at its operands and
- * check them out. If one of them cannot be moved, this one
- * cannot be moved either.
- */
- for (i = 0, n = get_irn_arity(expr); i < n; ++i) {
- ir_node *op = get_irn_n(expr, i);
- int new_depth = is_Proj(op) ? depth : depth + 1;
-
- res = _can_move_to(op, dest_block, new_depth, info);
-
- if (res != SUCCESS)
- goto end;
- }
-
-end:
- DBG((dbg, LEVEL_3, "\t\t\tcan move to %n: %d\n", expr, res));
-
- return res;
-}
-
-/**
- * Convenience function for _can_move_to.
- * Checks, if an expression can be moved to another block. The check can
- * be limited to a expression depth meaning if we need to crawl in
- * deeper into an expression than a given threshold to examine if
- * it can be moved, the expression is rejected and the test returns
- * false.
- *
- * @param expr The expression to check for.
- * @param dest_block The destination block you want @p expr to be.
- * @param info The options for createing Mux nodes.
- *
- * @return return a failure reason
- */
-static INLINE int can_move_to(ir_node *expr, ir_node *dest_block, const opt_if_conv_info_t *info)
-{
- return _can_move_to(expr, dest_block, 0, info);
-}
-
-/**
- * move a DAG given by a root node expr into a new block
- *
- * @param expr the root of a dag
- * @param dest_block the destination block
- */
-static void move_to(ir_node *expr, ir_node *dest_block)
-{
- int i, n;
- ir_node *expr_block = get_nodes_block(expr);
-
- /*
- * If we reached the dominator, we are done.
- * We will never put code through the dominator
- */
- if (block_dominates(expr_block, dest_block))
- return;
-
- for (i = 0, n = get_irn_arity(expr); i < n; ++i)
- move_to(get_irn_n(expr, i), dest_block);
-
- set_nodes_block(expr, dest_block);
-}
-
-/**
- * return the common dominator of two blocks
- */
-static INLINE ir_node *common_idom(ir_node *b1, ir_node *b2)
-{
- if(block_dominates(b1, b2))
- return b1;
- else if(block_dominates(b2, b1))
- return b2;
- else {
- ir_node *p;
-
- for (p = get_Block_idom(b1); !block_dominates(p, b2); p = get_Block_idom(p));
- return p;
- }