lower_dw.c

/*
 * This file is part of libFirm.
 * Copyright (C) 2012 University of Karlsruhe.
 */

/**
 * @file
 * @brief   Lower double word operations, i.e. 64bit -> 32bit, 32bit -> 16bit etc.
 * @date    8.10.2004
 * @author  Michael Beck
 */
#include "config.h"

#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

#include "be.h"
#include "error.h"
#include "lowering.h"
#include "irnode_t.h"
#include "irnodeset.h"
#include "irgraph_t.h"
#include "irmode_t.h"
#include "iropt_t.h"
#include "irgmod.h"
#include "tv_t.h"
#include "dbginfo_t.h"
#include "iropt_dbg.h"
#include "irflag_t.h"
#include "firmstat.h"
#include "irgwalk.h"
#include "ircons.h"
#include "irflag.h"
#include "iroptimize.h"
#include "debug.h"
#include "set.h"
#include "pmap.h"
#include "pdeq.h"
#include "irdump.h"
#include "array_t.h"
#include "irpass_t.h"
#include "lower_dw.h"

/** A map from (op, imode, omode) to Intrinsic functions entities. */
static set *intrinsic_fkt;

/** A map from (imode, omode) to conv function types. */
static set *conv_types;

/** A map from a method type to its lowered type. */
static pmap *lowered_type;

/** A map from a builtin type to its lower and higher type. */
static pmap *lowered_builtin_type_high;
static pmap *lowered_builtin_type_low;

/** The types for the binop and unop intrinsics. */
static ir_type *binop_tp_u, *binop_tp_s, *unop_tp_u, *unop_tp_s, *tp_s, *tp_u;

static ir_nodeset_t created_mux_nodes;

/** the debug handle */
DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)

/**
 * An entry in the (op, imode, omode) -> entity map.
 */
typedef struct op_mode_entry {
	const ir_op   *op;    /**< the op */
	const ir_mode *imode; /**< the input mode */
	const ir_mode *omode; /**< the output mode */
	ir_entity     *ent;   /**< the associated entity of this (op, imode, omode) triple */
} op_mode_entry_t;

/**
 * An entry in the (imode, omode) -> tp map.
 */
typedef struct conv_tp_entry {
	const ir_mode *imode; /**< the input mode */
	const ir_mode *omode; /**< the output mode */
	ir_type       *mtd;   /**< the associated method type of this (imode, omode) pair */
} conv_tp_entry_t;

enum lower_flags {
	MUST_BE_LOWERED = 1,  /**< graph must be lowered */
	CF_CHANGED      = 2,  /**< control flow was changed */
};

/**
 * The lower environment.
 */
typedef struct lower_dw_env_t {
	lower64_entry_t **entries;     /**< entries per node */
	ir_graph      *irg;
	struct obstack obst;           /**< an obstack holding the temporary data */
	ir_tarval *tv_mode_bytes;      /**< a tarval containing the number of bytes in the lowered modes */
	pdeq      *waitq;              /**< a wait queue of all nodes that must be handled later */
	ir_node  **lowered_phis;       /**< list of lowered phis */
	ir_mode   *high_signed;        /**< doubleword signed type */
	ir_mode   *high_unsigned;      /**< doubleword unsigned type */
	ir_mode   *low_signed;         /**< word signed type */
	ir_mode   *low_unsigned;       /**< word unsigned type */
	ident     *first_id;           /**< .l for little and .h for big endian */
	ident     *next_id;            /**< .h for little and .l for big endian */
	const lwrdw_param_t *params;   /**< transformation parameter */
	unsigned flags;                /**< some flags */
	unsigned n_entries;            /**< number of entries */
} lower_dw_env_t;

static lower_dw_env_t *env;

static void lower_node(ir_node *node);

/**
 * Create a method type for a Conv emulation from imode to omode.
 */
static ir_type *get_conv_type(ir_mode *imode, ir_mode *omode)
{
	conv_tp_entry_t key, *entry;
	ir_type *mtd;

	key.imode = imode;
	key.omode = omode;
	key.mtd   = NULL;

	entry = set_insert(conv_tp_entry_t, conv_types, &key, sizeof(key), hash_ptr(imode) ^ hash_ptr(omode));
	if (! entry->mtd) {
		int n_param = 1, n_res = 1;

		if (imode == env->high_signed || imode == env->high_unsigned)
			n_param = 2;
		if (omode == env->high_signed || omode == env->high_unsigned)
			n_res = 2;

		/* create a new one */
		mtd = new_type_method(n_param, n_res);

		/* set param types and result types */
		n_param = 0;
		if (imode == env->high_signed) {
			if (env->params->little_endian) {
				set_method_param_type(mtd, n_param++, tp_u);
				set_method_param_type(mtd, n_param++, tp_s);
			} else {
				set_method_param_type(mtd, n_param++, tp_s);
				set_method_param_type(mtd, n_param++, tp_u);
			}
		} else if (imode == env->high_unsigned) {
			set_method_param_type(mtd, n_param++, tp_u);
			set_method_param_type(mtd, n_param++, tp_u);
		} else {
			ir_type *tp = get_type_for_mode(imode);
			set_method_param_type(mtd, n_param++, tp);
		}

		n_res = 0;
		if (omode == env->high_signed) {
			if (env->params->little_endian) {
				set_method_res_type(mtd, n_res++, tp_u);
				set_method_res_type(mtd, n_res++, tp_s);
			} else {
				set_method_res_type(mtd, n_res++, tp_s);
				set_method_res_type(mtd, n_res++, tp_u);
			}
		} else if (omode == env->high_unsigned) {
			set_method_res_type(mtd, n_res++, tp_u);
			set_method_res_type(mtd, n_res++, tp_u);
		} else {
			ir_type *tp = get_type_for_mode(omode);
			set_method_res_type(mtd, n_res++, tp);
		}
		entry->mtd = mtd;
	} else {
		mtd = entry->mtd;
	}
	return mtd;
}

/**
 * Add an additional control flow input to a block.
 * Patch all Phi nodes. The new Phi inputs are copied from
 * old input number nr.
 */
static void add_block_cf_input_nr(ir_node *block, int nr, ir_node *cf)
{
	int i, arity = get_Block_n_cfgpreds(block);
	ir_node **in;

	assert(nr < arity);

	NEW_ARR_A(ir_node *, in, arity + 1);
	for (i = 0; i < arity; ++i)
		in[i] = get_Block_cfgpred(block, i);
	in[i] = cf;

	set_irn_in(block, i + 1, in);

	foreach_out_edge(block, edge) {
		ir_node *phi = get_edge_src_irn(edge);
		if (!is_Phi(phi))
			continue;

		for (i = 0; i < arity; ++i)
			in[i] = get_irn_n(phi, i);
		in[i] = in[nr];
		set_irn_in(phi, i + 1, in);
	}
}

/**
 * Add an additional control flow input to a block.
 * Patch all Phi nodes. The new Phi inputs are copied from
 * old input from cf tmpl.
 */
static void add_block_cf_input(ir_node *block, ir_node *tmpl, ir_node *cf)
{
	int i, arity = get_Block_n_cfgpreds(block);
	int nr = 0;

	for (i = 0; i < arity; ++i) {
		if (get_Block_cfgpred(block, i) == tmpl) {
			nr = i;
			break;
		}
	}
	assert(i < arity);
	add_block_cf_input_nr(block, nr, cf);
}

/**
 * Return the "operational" mode of a Firm node.
 */
static ir_mode *get_irn_op_mode(ir_node *node)
{
	switch (get_irn_opcode(node)) {
	case iro_Load:
		return get_Load_mode(node);
	case iro_Store:
		return get_irn_mode(get_Store_value(node));
	case iro_Div:
		return get_irn_mode(get_Div_left(node));
	case iro_Mod:
		return get_irn_mode(get_Mod_left(node));
	case iro_Cmp:
		return get_irn_mode(get_Cmp_left(node));
	default:
		return get_irn_mode(node);
	}
}

/**
 * Walker, prepare the node links and determine which nodes need to be lowered
 * at all.
 */
static void prepare_links(ir_node *node)
{
	ir_mode         *mode = get_irn_op_mode(node);
	lower64_entry_t *link;

	if (mode == env->high_signed || mode == env->high_unsigned) {
		unsigned idx = get_irn_idx(node);
		/* ok, found a node that will be lowered */
		link = OALLOCZ(&env->obst, lower64_entry_t);

		if (idx >= env->n_entries) {
			/* enlarge: this happens only for Rotl nodes which is RARELY */
			unsigned old   = env->n_entries;
			unsigned n_idx = idx + (idx >> 3);

			ARR_RESIZE(lower64_entry_t *, env->entries, n_idx);
			memset(&env->entries[old], 0, (n_idx - old) * sizeof(env->entries[0]));
			env->n_entries = n_idx;
		}
		env->entries[idx] = link;
		env->flags |= MUST_BE_LOWERED;
	} else if (is_Conv(node)) {
		/* Conv nodes have two modes */
		ir_node *pred = get_Conv_op(node);
		mode = get_irn_mode(pred);

		if (mode == env->high_signed || mode == env->high_unsigned) {
			/* must lower this node either but don't need a link */
			env->flags |= MUST_BE_LOWERED;
		}
		return;
	} else if (is_Call(node)) {
		/* Special case:  If the result of the Call is never used, we won't
		 * find a Proj with a mode that potentially triggers MUST_BE_LOWERED
		 * to be set.  Thus, if we see a call, we check its result types and
		 * decide whether MUST_BE_LOWERED has to be set.
		 */
		ir_type *tp = get_Call_type(node);
		size_t   n_res, i;

		n_res = get_method_n_ress(tp);
		for (i = 0; i < n_res; ++i) {
			ir_type *rtp = get_method_res_type(tp, i);

			if (is_Primitive_type(rtp)) {
				ir_mode *rmode = get_type_mode(rtp);

				if (rmode == env->high_signed || rmode == env->high_unsigned) {
					env->flags |= MUST_BE_LOWERED;
				}
			}
		}
	}
}

lower64_entry_t *get_node_entry(ir_node *node)
{
	unsigned idx = get_irn_idx(node);
	assert(idx < env->n_entries);
	return env->entries[idx];
}

void ir_set_dw_lowered(ir_node *old, ir_node *new_low, ir_node *new_high)
{
	lower64_entry_t *entry = get_node_entry(old);
	entry->low_word  = new_low;
	entry->high_word = new_high;
}

ir_mode *ir_get_low_unsigned_mode(void)
{
	return env->low_unsigned;
}

/**
 * Translate a Constant: create two.
 */
static void lower_Const(ir_node *node, ir_mode *mode)
{
	ir_graph  *irg      = get_irn_irg(node);
	dbg_info  *dbg      = get_irn_dbg_info(node);
	ir_mode   *low_mode = env->low_unsigned;
	ir_tarval *tv       = get_Const_tarval(node);
	ir_tarval *tv_l     = tarval_convert_to(tv, low_mode);
	ir_node   *res_low  = new_rd_Const(dbg, irg, tv_l);
	ir_tarval *tv_shrs  = tarval_shrs_unsigned(tv, get_mode_size_bits(low_mode));
	ir_tarval *tv_h     = tarval_convert_to(tv_shrs, mode);
	ir_node   *res_high = new_rd_Const(dbg, irg, tv_h);

	ir_set_dw_lowered(node, res_low, res_high);
}

/**
 * Translate a Load: create two.
 */
static void lower_Load(ir_node *node, ir_mode *mode)
{
	ir_mode    *low_mode = env->low_unsigned;
	ir_graph   *irg = get_irn_irg(node);
	ir_node    *adr = get_Load_ptr(node);
	ir_node    *mem = get_Load_mem(node);
	ir_node    *low;
	ir_node    *high;
	ir_node    *proj_m;
	dbg_info   *dbg;
	ir_node    *block = get_nodes_block(node);
	ir_cons_flags volatility = get_Load_volatility(node) == volatility_is_volatile
	                         ? cons_volatile : cons_none;

	if (env->params->little_endian) {
		low  = adr;
		high = new_r_Add(block, adr, new_r_Const(irg, env->tv_mode_bytes), get_irn_mode(adr));
	} else {
		low  = new_r_Add(block, adr, new_r_Const(irg, env->tv_mode_bytes), get_irn_mode(adr));
		high = adr;
	}

	/* create two loads */
	dbg    = get_irn_dbg_info(node);
	low    = new_rd_Load(dbg, block, mem,  low,  low_mode, volatility);
	proj_m = new_r_Proj(low, mode_M, pn_Load_M);
	high   = new_rd_Load(dbg, block, proj_m, high, mode, volatility);

	foreach_out_edge_safe(node, edge) {
		ir_node *proj = get_edge_src_irn(edge);
		if (!is_Proj(proj))
			continue;

		switch (get_Proj_proj(proj)) {
		case pn_Load_M:         /* Memory result. */
			/* put it to the second one */
			set_Proj_pred(proj, high);
			break;
		case pn_Load_X_except:  /* Execution result if exception occurred. */
			/* put it to the first one */
			set_Proj_pred(proj, low);
			break;
		case pn_Load_res: {       /* Result of load operation. */
			ir_node *res_low  = new_r_Proj(low,  low_mode, pn_Load_res);
			ir_node *res_high = new_r_Proj(high, mode,     pn_Load_res);
			ir_set_dw_lowered(proj, res_low, res_high);
			break;
		}
		default:
			assert(0 && "unexpected Proj number");
		}
		/* mark this proj: we have handled it already, otherwise we might fall
		 * into out new nodes. */
		mark_irn_visited(proj);
	}
}

/**
 * Translate a Store: create two.
 */
static void lower_Store(ir_node *node, ir_mode *mode)
{
	ir_graph              *irg;
	ir_node               *block, *adr, *mem;
	ir_node               *low, *high, *proj_m;
	dbg_info              *dbg;
	ir_node               *value = get_Store_value(node);
	const lower64_entry_t *entry = get_node_entry(value);
	ir_cons_flags volatility = get_Store_volatility(node) == volatility_is_volatile
	                           ? cons_volatile : cons_none;
	(void) mode;

	assert(entry);

	if (! entry->low_word) {
		/* not ready yet, wait */
		pdeq_putr(env->waitq, node);
		return;
	}

	irg = get_irn_irg(node);
	adr = get_Store_ptr(node);
	mem = get_Store_mem(node);
	block = get_nodes_block(node);

	if (env->params->little_endian) {
		low  = adr;
		high = new_r_Add(block, adr, new_r_Const(irg, env->tv_mode_bytes), get_irn_mode(adr));
	} else {
		low  = new_r_Add(block, adr, new_r_Const(irg, env->tv_mode_bytes), get_irn_mode(adr));
		high = adr;
	}

	/* create two Stores */
	dbg    = get_irn_dbg_info(node);
	low    = new_rd_Store(dbg, block, mem, low,  entry->low_word, volatility);
	proj_m = new_r_Proj(low, mode_M, pn_Store_M);
	high   = new_rd_Store(dbg, block, proj_m, high, entry->high_word, volatility);

	foreach_out_edge_safe(node, edge) {
		ir_node *proj = get_edge_src_irn(edge);
		if (!is_Proj(proj))
			continue;

		switch (get_Proj_proj(proj)) {
		case pn_Store_M:         /* Memory result. */
			/* put it to the second one */
			set_Proj_pred(proj, high);
			break;
		case pn_Store_X_except:  /* Execution result if exception occurred. */
			/* put it to the first one */
			set_Proj_pred(proj, low);
			break;
		default:
			assert(0 && "unexpected Proj number");
		}
		/* mark this proj: we have handled it already, otherwise we might fall into
		 * out new nodes. */
		mark_irn_visited(proj);
	}
}

/**
 * Return a node containing the address of the intrinsic emulation function.
 *
 * @param method  the method type of the emulation function
 * @param op      the emulated ir_op
 * @param imode   the input mode of the emulated opcode
 * @param omode   the output mode of the emulated opcode
 * @param env     the lower environment
 */
static ir_node *get_intrinsic_address(ir_type *method, ir_op *op,
                                      ir_mode *imode, ir_mode *omode)
{
	symconst_symbol sym;
	ir_entity *ent;
	op_mode_entry_t key, *entry;

	key.op    = op;
	key.imode = imode;
	key.omode = omode;
	key.ent   = NULL;

	entry = set_insert(op_mode_entry_t, intrinsic_fkt, &key, sizeof(key),
				hash_ptr(op) ^ hash_ptr(imode) ^ (hash_ptr(omode) << 8));
	if (! entry->ent) {
		/* create a new one */
		ent = env->params->create_intrinsic(method, op, imode, omode, env->params->ctx);

		assert(ent && "Intrinsic creator must return an entity");
		entry->ent = ent;
	} else {
		ent = entry->ent;
	}
	sym.entity_p = ent;
	return new_r_SymConst(env->irg, mode_P_code, sym, symconst_addr_ent);
}

/**
 * Translate a Div.
 *
 * Create an intrinsic Call.
 */
static void lower_Div(ir_node *node, ir_mode *mode)
{
	ir_node  *left   = get_Div_left(node);
	ir_node  *right  = get_Div_right(node);
	ir_node  *block  = get_nodes_block(node);
	dbg_info *dbgi   = get_irn_dbg_info(node);
	ir_type  *mtp    = mode_is_signed(mode) ? binop_tp_s : binop_tp_u;
	ir_mode  *opmode = get_irn_op_mode(node);
	ir_node  *addr   = get_intrinsic_address(mtp, get_irn_op(node), opmode, opmode);
	ir_node  *in[4];
	ir_node  *call;
	ir_node  *resproj;

	if (env->params->little_endian) {
		in[0] = get_lowered_low(left);
		in[1] = get_lowered_high(left);
		in[2] = get_lowered_low(right);
		in[3] = get_lowered_high(right);
	} else {
		in[0] = get_lowered_high(left);
		in[1] = get_lowered_low(left);
		in[2] = get_lowered_high(right);
		in[3] = get_lowered_low(right);
	}
	call    = new_rd_Call(dbgi, block, get_Div_mem(node), addr, 4, in, mtp);
	resproj = new_r_Proj(call, mode_T, pn_Call_T_result);
	set_irn_pinned(call, get_irn_pinned(node));

	foreach_out_edge_safe(node, edge) {
		ir_node *proj = get_edge_src_irn(edge);
		if (!is_Proj(proj))
			continue;

		switch (get_Proj_proj(proj)) {
		case pn_Div_M:         /* Memory result. */
			/* reroute to the call */
			set_Proj_pred(proj, call);
			set_Proj_proj(proj, pn_Call_M);
			break;
		case pn_Div_X_regular:
			set_Proj_pred(proj, call);
			set_Proj_proj(proj, pn_Call_X_regular);
			break;
		case pn_Div_X_except:
			set_Proj_pred(proj, call);
			set_Proj_proj(proj, pn_Call_X_except);
			break;
		case pn_Div_res:
			if (env->params->little_endian) {
				ir_node *res_low  = new_r_Proj(resproj, env->low_unsigned, 0);
				ir_node *res_high = new_r_Proj(resproj, mode,              1);
				ir_set_dw_lowered(proj, res_low, res_high);
			} else {
				ir_node *res_low  = new_r_Proj(resproj, env->low_unsigned, 1);
				ir_node *res_high = new_r_Proj(resproj, mode,              0);
				ir_set_dw_lowered(proj, res_low, res_high);
			}
			break;
		default:
			assert(0 && "unexpected Proj number");
		}
		/* mark this proj: we have handled it already, otherwise we might fall into
		 * out new nodes. */
		mark_irn_visited(proj);
	}
}

/**
 * Translate a Mod.
 *
 * Create an intrinsic Call.
 */
static void lower_Mod(ir_node *node, ir_mode *mode)
{
	ir_node  *left   = get_Mod_left(node);
	ir_node  *right  = get_Mod_right(node);
	dbg_info *dbgi   = get_irn_dbg_info(node);
	ir_node  *block  = get_nodes_block(node);
	ir_type  *mtp    = mode_is_signed(mode) ? binop_tp_s : binop_tp_u;
	ir_mode  *opmode = get_irn_op_mode(node);
	ir_node  *addr   = get_intrinsic_address(mtp, get_irn_op(node), opmode, opmode);
	ir_node  *in[4];
	ir_node  *call;
	ir_node  *resproj;

	if (env->params->little_endian) {
		in[0] = get_lowered_low(left);
		in[1] = get_lowered_high(left);
		in[2] = get_lowered_low(right);
		in[3] = get_lowered_high(right);
	} else {
		in[0] = get_lowered_high(left);
		in[1] = get_lowered_low(left);
		in[2] = get_lowered_high(right);
		in[3] = get_lowered_low(right);
	}
	call    = new_rd_Call(dbgi, block, get_Mod_mem(node), addr, 4, in, mtp);
	resproj = new_r_Proj(call, mode_T, pn_Call_T_result);
	set_irn_pinned(call, get_irn_pinned(node));

	foreach_out_edge_safe(node, edge) {
		ir_node *proj = get_edge_src_irn(edge);
		if (!is_Proj(proj))
			continue;

		switch (get_Proj_proj(proj)) {
		case pn_Mod_M:         /* Memory result. */
			/* reroute to the call */
			set_Proj_pred(proj, call);
			set_Proj_proj(proj, pn_Call_M);
			break;
		case pn_Div_X_regular:
			set_Proj_pred(proj, call);
			set_Proj_proj(proj, pn_Call_X_regular);
			break;
		case pn_Mod_X_except:
			set_Proj_pred(proj, call);
			set_Proj_proj(proj, pn_Call_X_except);
			break;
		case pn_Mod_res:
			if (env->params->little_endian) {
				ir_node *res_low  = new_r_Proj(resproj, env->low_unsigned, 0);
				ir_node *res_high = new_r_Proj(resproj, mode,              1);
				ir_set_dw_lowered(proj, res_low, res_high);
			} else {
				ir_node *res_low  = new_r_Proj(resproj, env->low_unsigned, 1);
				ir_node *res_high = new_r_Proj(resproj, mode,              0);
				ir_set_dw_lowered(proj, res_low, res_high);
			}
			break;
		default:
			assert(0 && "unexpected Proj number");
		}
		/* mark this proj: we have handled it already, otherwise we might fall
		 * into out new nodes. */
		mark_irn_visited(proj);
	}
}

/**
 * Translate a binop.
 *
 * Create an intrinsic Call.
 */
static void lower_binop(ir_node *node, ir_mode *mode)
{
	ir_node  *left  = get_binop_left(node);
	ir_node  *right = get_binop_right(node);
	dbg_info *dbgi  = get_irn_dbg_info(node);
	ir_node  *block = get_nodes_block(node);
	ir_graph *irg   = get_irn_irg(block);
	ir_type  *mtp   = mode_is_signed(mode) ? binop_tp_s : binop_tp_u;
	ir_node  *addr  = get_intrinsic_address(mtp, get_irn_op(node), mode, mode);
	ir_node  *in[4];
	ir_node  *call;
	ir_node  *resproj;

	if (env->params->little_endian) {
		in[0] = get_lowered_low(left);
		in[1] = get_lowered_high(left);
		in[2] = get_lowered_low(right);
		in[3] = get_lowered_high(right);
	} else {
		in[0] = get_lowered_high(left);
		in[1] = get_lowered_low(left);
		in[2] = get_lowered_high(right);
		in[3] = get_lowered_low(right);
	}
	call    = new_rd_Call(dbgi, block, get_irg_no_mem(irg), addr, 4, in, mtp);
	resproj = new_r_Proj(call, mode_T, pn_Call_T_result);
	set_irn_pinned(call, get_irn_pinned(node));

	if (env->params->little_endian) {
		ir_node *res_low  = new_r_Proj(resproj, env->low_unsigned, 0);
		ir_node *res_high = new_r_Proj(resproj, mode,              1);
		ir_set_dw_lowered(node, res_low, res_high);
	} else {
		ir_node *res_low  = new_r_Proj(resproj, env->low_unsigned, 1);
		ir_node *res_high = new_r_Proj(resproj, mode,              0);
		ir_set_dw_lowered(node, res_low, res_high);
	}
}

static ir_node *create_conv(ir_node *block, ir_node *node, ir_mode *dest_mode)
{
	if (get_irn_mode(node) == dest_mode)
		return node;
	return new_r_Conv(block, node, dest_mode);
}

/**
 * Moves node and all predecessors of node from from_bl to to_bl.
 * Does not move predecessors of Phi nodes (or block nodes).
 */
static void move(ir_node *node, ir_node *from_bl, ir_node *to_bl)
{
	int i, arity;

	/* move this node */
	set_nodes_block(node, to_bl);

	/* move its Projs */
	if (get_irn_mode(node) == mode_T) {
		foreach_out_edge(node, edge) {
			ir_node *proj = get_edge_src_irn(edge);
			if (!is_Proj(proj))
				continue;
			move(proj, from_bl, to_bl);
		}
	}

	/* We must not move predecessors of Phi nodes, even if they are in
	 * from_bl. (because these are values from an earlier loop iteration
	 * which are not predecessors of node here)
	 */
	if (is_Phi(node))
		return;

	/* recursion ... */
	arity = get_irn_arity(node);
	for (i = 0; i < arity; i++) {
		ir_node *pred      = get_irn_n(node, i);
		ir_mode *pred_mode = get_irn_mode(pred);
		if (get_nodes_block(pred) == from_bl)
			move(pred, from_bl, to_bl);
		if (pred_mode == env->high_signed || pred_mode == env->high_unsigned) {
			ir_node *pred_low  = get_lowered_low(pred);
			ir_node *pred_high = get_lowered_high(pred);
			if (get_nodes_block(pred_low) == from_bl)
				move(pred_low, from_bl, to_bl);
			if (pred_high != NULL && get_nodes_block(pred_high) == from_bl)
				move(pred_high, from_bl, to_bl);
		}
	}
}

/**
 * We need a custom version of part_block_edges because during transformation
 * not all data-dependencies are explicit yet if a lowered nodes users are not
 * lowered yet.
 * We can fix this by modifying move to look for such implicit dependencies.
 * Additionally we have to keep the proj_2_block map updated
 */
static ir_node *part_block_dw(ir_node *node)
{
	ir_graph *irg        = get_irn_irg(node);
	ir_node  *old_block  = get_nodes_block(node);
	int       n_cfgpreds = get_Block_n_cfgpreds(old_block);
	ir_node **cfgpreds   = get_Block_cfgpred_arr(old_block);
	ir_node  *new_block  = new_r_Block(irg, n_cfgpreds, cfgpreds);

	/* old_block has no predecessors anymore for now */
	set_irn_in(old_block, 0, NULL);

	/* move node and its predecessors to new_block */
	move(node, old_block, new_block);

	/* move Phi nodes to new_block */
	foreach_out_edge_safe(old_block, edge) {
		ir_node *phi = get_edge_src_irn(edge);
		if (!is_Phi(phi))
			continue;
		set_nodes_block(phi, new_block);
	}
	return old_block;
}

typedef ir_node* (*new_rd_shr_func)(dbg_info *dbgi, ir_node *block,
                                    ir_node *left, ir_node *right,
                                    ir_mode *mode);

static void lower_shr_helper(ir_node *node, ir_mode *mode,
                             new_rd_shr_func new_rd_shrs)
{
	ir_node  *right         = get_binop_right(node);
	ir_node  *left          = get_binop_left(node);
	ir_mode  *shr_mode      = get_irn_mode(node);
	unsigned  modulo_shift  = get_mode_modulo_shift(shr_mode);
	ir_mode  *low_unsigned  = env->low_unsigned;
	unsigned  modulo_shift2 = get_mode_modulo_shift(mode);
	ir_graph *irg           = get_irn_irg(node);
	ir_node  *left_low      = get_lowered_low(left);
	ir_node  *left_high     = get_lowered_high(left);
	dbg_info *dbgi          = get_irn_dbg_info(node);
	ir_node  *lower_block;
	ir_node  *block;
	ir_node  *cnst;
	ir_node  *andn;
	ir_node  *cmp;
	ir_node  *cond;
	ir_node  *proj_true;
	ir_node  *proj_false;
	ir_node  *phi_low;
	ir_node  *phi_high;
	ir_node  *lower_in[2];
	ir_node  *phi_low_in[2];
	ir_node  *phi_high_in[2];

	/* this version is optimized for modulo shift architectures
	 * (and can't handle anything else) */
	if (modulo_shift != get_mode_size_bits(shr_mode)
			|| modulo_shift2<<1 != modulo_shift) {
		panic("Shr lowering only implemented for modulo shift shr operations");
	}
	if (!is_po2(modulo_shift) || !is_po2(modulo_shift2)) {
		panic("Shr lowering only implemented for power-of-2 modes");
	}
	/* without 2-complement the -x instead of (bit_width-x) trick won't work */
	if (get_mode_arithmetic(shr_mode) != irma_twos_complement) {
		panic("Shr lowering only implemented for two-complement modes");
	}

	block = get_nodes_block(node);

	/* if the right operand is a 64bit value, we're only interested in the
	 * lower word */
	if (get_irn_mode(right) == env->high_unsigned) {
		right = get_lowered_low(right);
	} else {
		/* shift should never have signed mode on the right */
		assert(get_irn_mode(right) != env->high_signed);
		right = create_conv(block, right, low_unsigned);
	}

	lower_block = part_block_dw(node);
	env->flags |= CF_CHANGED;
	block = get_nodes_block(node);

	/* add a Cmp to test if highest bit is set <=> whether we shift more
	 * than half the word width */
	cnst       = new_r_Const_long(irg, low_unsigned, modulo_shift2);
	andn       = new_r_And(block, right, cnst, low_unsigned);
	cnst       = new_r_Const(irg, get_mode_null(low_unsigned));
	cmp        = new_rd_Cmp(dbgi, block, andn, cnst, ir_relation_equal);
	cond       = new_rd_Cond(dbgi, block, cmp);
	proj_true  = new_r_Proj(cond, mode_X, pn_Cond_true);
	proj_false = new_r_Proj(cond, mode_X, pn_Cond_false);

	/* the true block => shift_width < 1word */
	{
		/* In theory the low value (for 64bit shifts) is:
		 *    Or(High << (32-x)), Low >> x)
		 * In practice High << 32-x will fail when x is zero (since we have
		 * modulo shift and 32 will be 0). So instead we use:
		 *    Or(High<<1<<~x, Low >> x)
		 */
		ir_node *in[1]        = { proj_true };
		ir_node *block_true   = new_r_Block(irg, ARRAY_SIZE(in), in);
		ir_node *res_high     = new_rd_shrs(dbgi, block_true, left_high,
		                                    right, mode);
		ir_node *shift_low    = new_rd_Shr(dbgi, block_true, left_low, right,
		                                   low_unsigned);
		ir_node *not_shiftval = new_rd_Not(dbgi, block_true, right,
		                                   low_unsigned);
		ir_node *conv         = create_conv(block_true, left_high,
		                                    low_unsigned);
		ir_node *one          = new_r_Const(irg, get_mode_one(low_unsigned));
		ir_node *carry0       = new_rd_Shl(dbgi, block_true, conv, one,
		                                   low_unsigned);
		ir_node *carry1       = new_rd_Shl(dbgi, block_true, carry0,
		                                   not_shiftval, low_unsigned);
		ir_node *res_low      = new_rd_Or(dbgi, block_true, shift_low, carry1,
		                                  low_unsigned);
		lower_in[0]           = new_r_Jmp(block_true);
		phi_low_in[0]         = res_low;
		phi_high_in[0]        = res_high;
	}

	/* false block => shift_width > 1word */
	{
		ir_node *in[1]       = { proj_false };
		ir_node *block_false = new_r_Block(irg, ARRAY_SIZE(in), in);
		ir_node *conv        = create_conv(block_false, left_high, low_unsigned);
		ir_node *res_low     = new_rd_shrs(dbgi, block_false, conv, right,
		                                   low_unsigned);
		int      cnsti       = modulo_shift2-1;
		ir_node *cnst2       = new_r_Const_long(irg, low_unsigned, cnsti);
		ir_node *res_high;
		if (new_rd_shrs == new_rd_Shrs) {
			res_high = new_rd_shrs(dbgi, block_false, left_high, cnst2, mode);
		} else {
			res_high = new_r_Const(irg, get_mode_null(mode));
		}
		lower_in[1]          = new_r_Jmp(block_false);
		phi_low_in[1]        = res_low;
		phi_high_in[1]       = res_high;
	}

	/* patch lower block */
	set_irn_in(lower_block, ARRAY_SIZE(lower_in), lower_in);
	phi_low  = new_r_Phi(lower_block, ARRAY_SIZE(phi_low_in), phi_low_in,
	                     low_unsigned);
	phi_high = new_r_Phi(lower_block, ARRAY_SIZE(phi_high_in), phi_high_in,
	                     mode);
	ir_set_dw_lowered(node, phi_low, phi_high);
}

static void lower_Shr(ir_node *node, ir_mode *mode)
{
	lower_shr_helper(node, mode, new_rd_Shr);
}

static void lower_Shrs(ir_node *node, ir_mode *mode)
{
	lower_shr_helper(node, mode, new_rd_Shrs);
}

static void lower_Shl(ir_node *node, ir_mode *mode)
{
	ir_node  *right         = get_binop_right(node);
	ir_node  *left          = get_binop_left(node);
	ir_mode  *shr_mode      = get_irn_mode(node);
	unsigned  modulo_shift  = get_mode_modulo_shift(shr_mode);
	ir_mode  *low_unsigned  = env->low_unsigned;
	unsigned  modulo_shift2 = get_mode_modulo_shift(mode);
	ir_graph *irg           = get_irn_irg(node);
	ir_node  *left_low      = get_lowered_low(left);
	ir_node  *left_high     = get_lowered_high(left);
	dbg_info *dbgi          = get_irn_dbg_info(node);
	ir_node  *lower_block   = get_nodes_block(node);
	ir_node  *block;
	ir_node  *cnst;
	ir_node  *andn;
	ir_node  *cmp;
	ir_node  *cond;
	ir_node  *proj_true;
	ir_node  *proj_false;
	ir_node  *phi_low;
	ir_node  *phi_high;
	ir_node  *lower_in[2];
	ir_node  *phi_low_in[2];
	ir_node  *phi_high_in[2];

	/* this version is optimized for modulo shift architectures
	 * (and can't handle anything else) */
	if (modulo_shift != get_mode_size_bits(shr_mode)
			|| modulo_shift2<<1 != modulo_shift) {
		panic("Shl lowering only implemented for modulo shift shl operations");
	}
	if (!is_po2(modulo_shift) || !is_po2(modulo_shift2)) {
		panic("Shl lowering only implemented for power-of-2 modes");
	}
	/* without 2-complement the -x instead of (bit_width-x) trick won't work */
	if (get_mode_arithmetic(shr_mode) != irma_twos_complement) {
		panic("Shl lowering only implemented for two-complement modes");
	}

	/* if the right operand is a 64bit value, we're only interested in the
	 * lower word */
	if (get_irn_mode(right) == env->high_unsigned) {
		right = get_lowered_low(right);
	} else {
		/* shift should never have signed mode on the right */
		assert(get_irn_mode(right) != env->high_signed);
		right = create_conv(lower_block, right, low_unsigned);
	}

	part_block_dw(node);
	env->flags |= CF_CHANGED;
	block = get_nodes_block(node);

	/* add a Cmp to test if highest bit is set <=> whether we shift more
	 * than half the word width */
	cnst       = new_r_Const_long(irg, low_unsigned, modulo_shift2);
	andn       = new_r_And(block, right, cnst, low_unsigned);
	cnst       = new_r_Const(irg, get_mode_null(low_unsigned));
	cmp        = new_rd_Cmp(dbgi, block, andn, cnst, ir_relation_equal);
	cond       = new_rd_Cond(dbgi, block, cmp);
	proj_true  = new_r_Proj(cond, mode_X, pn_Cond_true);
	proj_false = new_r_Proj(cond, mode_X, pn_Cond_false);

	/* the true block => shift_width < 1word */
	{
		ir_node *in[1]        = { proj_true };
		ir_node *block_true   = new_r_Block(irg, ARRAY_SIZE(in), in);

		ir_node *res_low      = new_rd_Shl(dbgi, block_true, left_low,
		                                   right, low_unsigned);
		ir_node *shift_high   = new_rd_Shl(dbgi, block_true, left_high, right,
		                                   mode);
		ir_node *not_shiftval = new_rd_Not(dbgi, block_true, right,
		                                   low_unsigned);
		ir_node *conv         = create_conv(block_true, left_low, mode);
		ir_node *one          = new_r_Const(irg, get_mode_one(low_unsigned));
		ir_node *carry0       = new_rd_Shr(dbgi, block_true, conv, one, mode);
		ir_node *carry1       = new_rd_Shr(dbgi, block_true, carry0,