lower_dw.c

/*
 * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

/*
 * Project:     libFIRM
 * File name:   ir/lower/lower_dw.c
 * Purpose:     Lower Double word operations, ie Mode L -> I.
 * Author:      Michael Beck
 * Created:     8.10.2004
 * CVS-ID:      $Id$
 * Copyright:   (c) 1998-2006 Universitt Karlsruhe
 */
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif

#ifdef HAVE_STRING_H
# include <string.h>
#endif
#ifdef HAVE_STDLIB_H
# include <stdlib.h>
#endif

#include <assert.h>

#include "irnode_t.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 "lower_dw.h"
#include "irflag.h"
#include "irtools.h"
#include "debug.h"
#include "set.h"
#include "pmap.h"
#include "pdeq.h"
#include "irdump.h"
#include "xmalloc.h"

/** A map from mode to a primitive type. */
static pmap *prim_types;

/** 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;

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

/** 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;

/**
 * Every double word node will be replaced,
 * we need some store to hold the replacement:
 */
typedef struct _node_entry_t {
	ir_node *low_word;    /**< the low word */
	ir_node *high_word;   /**< the high word */
} node_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_env_t {
	node_entry_t **entries;       /**< entries per node */
	struct obstack obst;          /**< an obstack holding the temporary data */
	tarval   *tv_mode_bytes;      /**< a tarval containing the number of bytes in the lowered modes */
	tarval   *tv_mode_bits;       /**< a tarval containing the number of bits in the lowered modes */
	pdeq     *waitq;              /**< a wait queue of all nodes that must be handled later */
	pmap     *proj_2_block;       /**< a map from ProjX to its destination blocks */
	const lwrdw_param_t *params;  /**< transformation parameter */
	unsigned flags;               /**< some flags */
	int      n_entries;           /**< number of entries */
} lower_env_t;

/**
 * Get a primitive mode for a mode.
 */
static ir_type *get_primitive_type(ir_mode *mode) {
	pmap_entry *entry = pmap_find(prim_types, mode);
	ir_type *tp;
	char buf[64];

	if (entry)
		return entry->value;

	snprintf(buf, sizeof(buf), "_prim_%s", get_mode_name(mode));
	tp = new_type_primitive(new_id_from_str(buf), mode);

	pmap_insert(prim_types, mode, tp);
	return tp;
}  /* get_primitive_type */

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

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

	entry = set_insert(conv_types, &key, sizeof(key), HASH_PTR(imode) ^ HASH_PTR(omode));
	if (! entry->mtd) {
		int n_param = 1, n_res = 1;
		char buf[64];

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

		/* create a new one */
		snprintf(buf, sizeof(buf), "LConv%s%s", get_mode_name(imode), get_mode_name(omode));
		mtd = new_type_method(new_id_from_str(buf), n_param, n_res);

		/* set param types and result types */
		n_param = 0;
		if (imode == env->params->high_signed) {
			set_method_param_type(mtd, n_param++, tp_s);
			set_method_param_type(mtd, n_param++, tp_s);
		} else if (imode == env->params->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_primitive_type(imode);
			set_method_param_type(mtd, n_param++, tp);
		}  /* if */

		n_res = 0;
		if (omode == env->params->high_signed) {
			set_method_res_type(mtd, n_res++, tp_s);
			set_method_res_type(mtd, n_res++, tp_s);
		} else if (omode == env->params->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_primitive_type(omode);
			set_method_res_type(mtd, n_res++, tp);
		}  /* if */
		entry->mtd = mtd;
	} else {
		mtd = entry->mtd;
	}  /* if */
	return mtd;
}  /* get_conv_type */

/**
 * 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_irn_arity(block);
	ir_node **in, *phi;

	assert(nr < arity);

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

	set_irn_in(block, i + 1, in);

	for (phi = get_irn_link(block); phi; phi = get_irn_link(phi)) {
		for (i = 0; i < arity; ++i)
			in[i] = get_irn_n(phi, i);
		in[i] = in[nr];
		set_irn_in(phi, i + 1, in);
	}  /* for */
}  /* add_block_cf_input_nr */

/**
 * 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_irn_arity(block);
	int nr = 0;

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

/**
 * 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_DivMod:
		return get_irn_mode(get_DivMod_left(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);
	}  /* switch */
}  /* get_irn_op_mode */

/**
 * Walker, prepare the node links.
 */
static void prepare_links(ir_node *node, void *env)
{
	lower_env_t  *lenv = env;
	ir_mode      *mode = get_irn_op_mode(node);
	node_entry_t *link;
	int          i;

	if (mode == lenv->params->high_signed ||
		mode == lenv->params->high_unsigned) {
		/* ok, found a node that will be lowered */
		link = obstack_alloc(&lenv->obst, sizeof(*link));

		memset(link, 0, sizeof(*link));

		lenv->entries[get_irn_idx(node)] = link;
		lenv->flags |= MUST_BE_LOWERED;
	} else if (get_irn_op(node) == op_Conv) {
		/* Conv nodes have two modes */
		ir_node *pred = get_Conv_op(node);
		mode = get_irn_mode(pred);

		if (mode == lenv->params->high_signed ||
			mode == lenv->params->high_unsigned) {
			/* must lower this node either but don't need a link */
			lenv->flags |= MUST_BE_LOWERED;
		}  /* if */
		return;
	}  /* if */

	if (is_Proj(node)) {
		/* link all Proj nodes to its predecessor:
		   Note that Tuple Proj's and its Projs are linked either. */
		ir_node *pred = get_Proj_pred(node);

		set_irn_link(node, get_irn_link(pred));
		set_irn_link(pred, node);
	} else if (is_Phi(node)) {
		/* link all Phi nodes to its block */
		ir_node *block = get_nodes_block(node);

		set_irn_link(node, get_irn_link(block));
		set_irn_link(block, node);
	} else if (is_Block(node)) {
		/* fill the Proj -> Block map */
		for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
			ir_node *pred = get_Block_cfgpred(node, i);

			if (is_Proj(pred))
				pmap_insert(lenv->proj_2_block, pred, node);
		}  /* for */
	}  /* if */
}  /* prepare_links */

/**
 * Translate a Constant: create two.
 */
static void lower_Const(ir_node *node, ir_mode *mode, lower_env_t *env) {
	tarval   *tv, *tv_l, *tv_h;
	ir_node  *low, *high;
	dbg_info *dbg = get_irn_dbg_info(node);
	ir_node  *block = get_nodes_block(node);
	int      idx;
	ir_graph *irg = current_ir_graph;

	tv   = get_Const_tarval(node);

	tv_l = tarval_convert_to(tv, mode);
	low  = new_rd_Const(dbg, irg, block, mode, tv_l);

	tv_h = tarval_convert_to(tarval_shrs(tv, env->tv_mode_bits), mode);
	high = new_rd_Const(dbg, irg, block, mode, tv_h);

	idx = get_irn_idx(node);
	assert(idx < env->n_entries);
	env->entries[idx]->low_word  = low;
	env->entries[idx]->high_word = high;
}  /* lower_Const */

/**
 * Translate a Load: create two.
 */
static void lower_Load(ir_node *node, ir_mode *mode, lower_env_t *env) {
	ir_graph *irg = current_ir_graph;
	ir_node  *adr = get_Load_ptr(node);
	ir_node  *mem = get_Load_mem(node);
	ir_node  *low, *high, *proj;
	dbg_info *dbg;
	ir_node  *block = get_nodes_block(node);
	int      idx;

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

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

	set_Load_volatility(low,  get_Load_volatility(node));
	set_Load_volatility(high, get_Load_volatility(node));

	idx = get_irn_idx(node);
	assert(idx < env->n_entries);
	env->entries[idx]->low_word  = low;
	env->entries[idx]->high_word = high;

	for (proj = get_irn_link(node); proj; proj = get_irn_link(proj)) {
		idx = get_irn_idx(proj);

		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. */
			assert(idx < env->n_entries);
			env->entries[idx]->low_word  = new_r_Proj(irg, block, low, mode, pn_Load_res);
			env->entries[idx]->high_word = new_r_Proj(irg, block, high, mode, pn_Load_res);
			break;
		default:
			assert(0 && "unexpected Proj number");
		}  /* switch */
		/* mark this proj: we have handled it already, otherwise we might fall into
		 * out new nodes. */
		mark_irn_visited(proj);
	}  /* for */
}  /* lower_Load */

/**
 * Translate a Store: create two.
 */
static void lower_Store(ir_node *node, ir_mode *mode, lower_env_t *env) {
	ir_graph *irg;
	ir_node  *block, *adr, *mem;
	ir_node  *low, *high, *irn, *proj;
	dbg_info *dbg;
	int      idx;
	node_entry_t *entry;

	irn = get_Store_value(node);
	entry = env->entries[get_irn_idx(irn)];
	assert(entry);

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

	irg = current_ir_graph;
	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(irg, block, adr,
			new_r_Const(irg, block, get_tarval_mode(env->tv_mode_bytes), env->tv_mode_bytes),
			get_irn_mode(adr));
	} else {
		low  = new_r_Add(irg, block, adr,
			new_r_Const(irg, block, get_tarval_mode(env->tv_mode_bytes), env->tv_mode_bytes),
			get_irn_mode(adr));
		high = adr;
	}  /* if */

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

	set_Store_volatility(low,  get_Store_volatility(node));
	set_Store_volatility(high, get_Store_volatility(node));

	idx = get_irn_idx(node);
	assert(idx < env->n_entries);
	env->entries[idx]->low_word  = low;
	env->entries[idx]->high_word = high;

	for (proj = get_irn_link(node); proj; proj = get_irn_link(proj)) {
		idx = get_irn_idx(proj);

		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");
		}  /* switch */
		/* mark this proj: we have handled it already, otherwise we might fall into
		 * out new nodes. */
		mark_irn_visited(proj);
	}  /* for */
}  /* lower_Store */

/**
 * 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 block   where the new mode is created
 * @param env     the lower environment
 */
static ir_node *get_intrinsic_address(ir_type *method, ir_op *op,
                                      ir_mode *imode, ir_mode *omode,
                                      ir_node *block, lower_env_t *env) {
	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(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;
	}  /* if */
	sym.entity_p = ent;
	return new_r_SymConst(current_ir_graph, block, sym, symconst_addr_ent);
}  /* get_intrinsic_address */

/**
 * Translate a Div.
 *
 * Create an intrinsic Call.
 */
static void lower_Div(ir_node *node, ir_mode *mode, lower_env_t *env) {
	ir_node  *block, *irn, *call, *proj;
	ir_node  *in[4];
	ir_mode  *opmode;
	dbg_info *dbg;
	ir_type  *mtp;
	int      idx;
	ir_graph *irg;
	node_entry_t *entry;

	irn   = get_Div_left(node);
	entry = env->entries[get_irn_idx(irn)];
	assert(entry);

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

	in[0] = entry->low_word;
	in[1] = entry->high_word;

	irn   = get_Div_right(node);
	entry = env->entries[get_irn_idx(irn)];
	assert(entry);

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

	in[2] = entry->low_word;
	in[3] = entry->high_word;

	dbg   = get_irn_dbg_info(node);
	block = get_nodes_block(node);
	irg   = current_ir_graph;

	mtp = mode_is_signed(mode) ? binop_tp_s : binop_tp_u;
	opmode = get_irn_op_mode(node);
	irn = get_intrinsic_address(mtp, get_irn_op(node), opmode, opmode, block, env);
	call = new_rd_Call(dbg, irg, block, get_Div_mem(node),
		irn, 4, in, mtp);
	set_irn_pinned(call, get_irn_pinned(node));
	irn = new_r_Proj(irg, block, call, mode_T, pn_Call_T_result);

	for (proj = get_irn_link(node); proj; proj = get_irn_link(proj)) {
		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_except);
			break;
		case pn_Div_X_except:  /* Execution result if exception occurred. */
			/* reroute to the call */
			set_Proj_pred(proj, call);
			set_Proj_proj(proj, pn_Call_X_except);
			break;
		case pn_Div_res:       /* Result of computation. */
			idx = get_irn_idx(proj);
			assert(idx < env->n_entries);
			env->entries[idx]->low_word  = new_r_Proj(current_ir_graph, block, irn, mode, 0);
			env->entries[idx]->high_word = new_r_Proj(current_ir_graph, block, irn, mode, 1);
			break;
		default:
			assert(0 && "unexpected Proj number");
		}  /* switch */
		/* mark this proj: we have handled it already, otherwise we might fall into
		 * out new nodes. */
		mark_irn_visited(proj);
	}  /* for */
}  /* lower_Div */

/**
 * Translate a Mod.
 *
 * Create an intrinsic Call.
 */
static void lower_Mod(ir_node *node, ir_mode *mode, lower_env_t *env) {
	ir_node  *block, *proj, *irn, *call;
	ir_node  *in[4];
	ir_mode  *opmode;
	dbg_info *dbg;
	ir_type  *mtp;
	int      idx;
	ir_graph *irg;
	node_entry_t *entry;

	irn   = get_Mod_left(node);
	entry = env->entries[get_irn_idx(irn)];
	assert(entry);

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

	in[0] = entry->low_word;
	in[1] = entry->high_word;

	irn   = get_Mod_right(node);
	entry = env->entries[get_irn_idx(irn)];
	assert(entry);

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

	in[2] = entry->low_word;
	in[3] = entry->high_word;

	dbg   = get_irn_dbg_info(node);
	block = get_nodes_block(node);
	irg   = current_ir_graph;

	mtp = mode_is_signed(mode) ? binop_tp_s : binop_tp_u;
	opmode = get_irn_op_mode(node);
	irn = get_intrinsic_address(mtp, get_irn_op(node), opmode, opmode, block, env);
	call = new_rd_Call(dbg, irg, block, get_Mod_mem(node),
		irn, 4, in, mtp);
	set_irn_pinned(call, get_irn_pinned(node));
	irn = new_r_Proj(irg, block, call, mode_T, pn_Call_T_result);

	for (proj = get_irn_link(node); proj; proj = get_irn_link(proj)) {
		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_except);
			break;
		case pn_Mod_X_except:  /* Execution result if exception occurred. */
			/* reroute to the call */
			set_Proj_pred(proj, call);
			set_Proj_proj(proj, pn_Call_X_except);
			break;
		case pn_Mod_res:       /* Result of computation. */
			idx = get_irn_idx(proj);
			assert(idx < env->n_entries);
			env->entries[idx]->low_word  = new_r_Proj(irg, block, irn, mode, 0);
			env->entries[idx]->high_word = new_r_Proj(irg, block, irn, mode, 1);
			break;
		default:
			assert(0 && "unexpected Proj number");
		}  /* switch */
		/* mark this proj: we have handled it already, otherwise we might fall into
		 * out new nodes. */
		mark_irn_visited(proj);
	}  /* for */
}  /* lower_Mod */

/**
 * Translate a DivMod.
 *
 * Create two intrinsic Calls.
 */
static void lower_DivMod(ir_node *node, ir_mode *mode, lower_env_t *env) {
	ir_node  *block, *proj, *irn, *mem, *callDiv, *callMod;
	ir_node  *resDiv = NULL;
	ir_node  *resMod = NULL;
	ir_node  *in[4];
	ir_mode  *opmode;
	dbg_info *dbg;
	ir_type  *mtp;
	int      idx;
	node_entry_t *entry;
	unsigned flags = 0;
	ir_graph *irg;

	/* check if both results are needed */
	for (proj = get_irn_link(node); proj; proj = get_irn_link(proj)) {
		switch (get_Proj_proj(proj)) {
		case pn_DivMod_res_div: flags |= 1; break;
		case pn_DivMod_res_mod: flags |= 2; break;
		default: break;
		}  /* switch */
	}  /* for */

	irn   = get_DivMod_left(node);
	entry = env->entries[get_irn_idx(irn)];
	assert(entry);

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

	in[0] = entry->low_word;
	in[1] = entry->high_word;

	irn   = get_DivMod_right(node);
	entry = env->entries[get_irn_idx(irn)];
	assert(entry);

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

	in[2] = entry->low_word;
	in[3] = entry->high_word;

	dbg   = get_irn_dbg_info(node);
	block = get_nodes_block(node);
	irg   = current_ir_graph;

	mem = get_DivMod_mem(node);

	callDiv = callMod = NULL;
	mtp = mode_is_signed(mode) ? binop_tp_s : binop_tp_u;
	if (flags & 1) {
		opmode = get_irn_op_mode(node);
		irn = get_intrinsic_address(mtp, op_Div, opmode, opmode, block, env);
		callDiv = new_rd_Call(dbg, irg, block, mem,
			irn, 4, in, mtp);
		set_irn_pinned(callDiv, get_irn_pinned(node));
		resDiv = new_r_Proj(irg, block, callDiv, mode_T, pn_Call_T_result);
	}  /* if */
	if (flags & 2) {
		if (flags & 1)
			mem = new_r_Proj(irg, block, callDiv, mode_M, pn_Call_M);
		opmode = get_irn_op_mode(node);
		irn = get_intrinsic_address(mtp, op_Mod, opmode, opmode, block, env);
		callMod = new_rd_Call(dbg, irg, block, mem,
			irn, 4, in, mtp);
		set_irn_pinned(callMod, get_irn_pinned(node));
		resMod = new_r_Proj(irg, block, callMod, mode_T, pn_Call_T_result);
	}  /* if */

	for (proj = get_irn_link(node); proj; proj = get_irn_link(proj)) {
		switch (get_Proj_proj(proj)) {
		case pn_DivMod_M:         /* Memory result. */
			/* reroute to the first call */
			set_Proj_pred(proj, callDiv ? callDiv : (callMod ? callMod : mem));
			set_Proj_proj(proj, pn_Call_M_except);
			break;
		case pn_DivMod_X_except:  /* Execution result if exception occurred. */
			/* reroute to the first call */
			set_Proj_pred(proj, callDiv ? callDiv : (callMod ? callMod : mem));
			set_Proj_proj(proj, pn_Call_X_except);
			break;
		case pn_DivMod_res_div:   /* Result of Div. */
			idx = get_irn_idx(proj);
			assert(idx < env->n_entries);
			env->entries[idx]->low_word  = new_r_Proj(irg, block, resDiv, mode, 0);
			env->entries[idx]->high_word = new_r_Proj(irg, block, resDiv, mode, 1);
			break;
		case pn_DivMod_res_mod:   /* Result of Mod. */
			idx = get_irn_idx(proj);
			env->entries[idx]->low_word  = new_r_Proj(irg, block, resMod, mode, 0);
			env->entries[idx]->high_word = new_r_Proj(irg, block, resMod, mode, 1);
			break;
		default:
			assert(0 && "unexpected Proj number");
		}  /* switch */
		/* mark this proj: we have handled it already, otherwise we might fall into
		 * out new nodes. */
		mark_irn_visited(proj);
	}  /* for */
}  /* lower_DivMod */

/**
 * Translate a Binop.
 *
 * Create an intrinsic Call.
 */
static void lower_Binop(ir_node *node, ir_mode *mode, lower_env_t *env) {
	ir_node  *block, *irn;
	ir_node  *in[4];
	dbg_info *dbg;
	ir_type  *mtp;
	int      idx;
	ir_graph *irg;
	node_entry_t *entry;

	irn   = get_binop_left(node);
	entry = env->entries[get_irn_idx(irn)];
	assert(entry);

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

	in[0] = entry->low_word;
	in[1] = entry->high_word;

	irn   = get_binop_right(node);
	entry = env->entries[get_irn_idx(irn)];
	assert(entry);

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

	in[2] = entry->low_word;
	in[3] = entry->high_word;

	dbg   = get_irn_dbg_info(node);
	block = get_nodes_block(node);
	irg   = current_ir_graph;

	mtp = mode_is_signed(mode) ? binop_tp_s : binop_tp_u;
	irn = get_intrinsic_address(mtp, get_irn_op(node), mode, mode, block, env);
	irn = new_rd_Call(dbg, irg, block, get_irg_no_mem(current_ir_graph),
		irn, 4, in, mtp);
	set_irn_pinned(irn, get_irn_pinned(node));
	irn = new_r_Proj(irg, block, irn, mode_T, pn_Call_T_result);

	idx = get_irn_idx(node);
	assert(idx < env->n_entries);
	env->entries[idx]->low_word  = new_r_Proj(irg, block, irn, mode, 0);
	env->entries[idx]->high_word = new_r_Proj(irg, block, irn, mode, 1);
}  /* lower_Binop */

/**
 * Translate a Shiftop.
 *
 * Create an intrinsic Call.
 */
static void lower_Shiftop(ir_node *node, ir_mode *mode, lower_env_t *env) {
	ir_node  *block, *irn;
	ir_node  *in[3];
	dbg_info *dbg;
	ir_type  *mtp;
	int      idx;
	ir_graph *irg;
	node_entry_t *entry;

	irn   = get_binop_left(node);
	entry = env->entries[get_irn_idx(irn)];
	assert(entry);

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

	in[0] = entry->low_word;
	in[1] = entry->high_word;

	/* The shift count is always mode_Iu in firm, so there is no need for lowering */
	in[2] = get_binop_right(node);

	dbg   = get_irn_dbg_info(node);
	block = get_nodes_block(node);
	irg  = current_ir_graph;

	mtp = mode_is_signed(mode) ? shiftop_tp_s : shiftop_tp_u;
	irn = get_intrinsic_address(mtp, get_irn_op(node), mode, mode, block, env);
	irn = new_rd_Call(dbg, irg, block, get_irg_no_mem(current_ir_graph),
		irn, 3, in, mtp);
	set_irn_pinned(irn, get_irn_pinned(node));
	irn = new_r_Proj(irg, block, irn, mode_T, pn_Call_T_result);

	idx = get_irn_idx(node);
	assert(idx < env->n_entries);
	env->entries[idx]->low_word  = new_r_Proj(irg, block, irn, mode, 0);
	env->entries[idx]->high_word = new_r_Proj(irg, block, irn, mode, 1);
}  /* lower_Shiftop */

/**
 * Translate a Shr and handle special cases.
 */
static void lower_Shr(ir_node *node, ir_mode *mode, lower_env_t *env) {
	ir_node  *right = get_Shr_right(node);
	ir_graph *irg = current_ir_graph;

	if (get_mode_arithmetic(mode) == irma_twos_complement && is_Const(right)) {
		tarval *tv = get_Const_tarval(right);

		if (tarval_is_long(tv) &&
			get_tarval_long(tv) >= get_mode_size_bits(mode)) {
			ir_node *block = get_nodes_block(node);
			ir_node *left = get_Shr_left(node);
			ir_node *c;
			long shf_cnt = get_tarval_long(tv) - get_mode_size_bits(mode);
			int idx = get_irn_idx(left);

			left = env->entries[idx]->high_word;
			idx = get_irn_idx(node);

			if (shf_cnt > 0) {
				c = new_r_Const_long(irg, block, mode_Iu, shf_cnt);
				env->entries[idx]->low_word = new_r_Shr(irg, block, left, c, mode);
			} else {
				env->entries[idx]->low_word = left;
			}  /* if */
			env->entries[idx]->high_word = new_r_Const(irg, block, mode, get_mode_null(mode));

			return;
		}  /* if */
	}  /* if */
	lower_Shiftop(node, mode, env);
}  /* lower_Shr */

/**
 * Translate a Shl and handle special cases.
 */
static void lower_Shl(ir_node *node, ir_mode *mode, lower_env_t *env) {
	ir_node  *right = get_Shl_right(node);
	ir_graph *irg = current_ir_graph;

	if (get_mode_arithmetic(mode) == irma_twos_complement && is_Const(right)) {
		tarval *tv = get_Const_tarval(right);

		if (tarval_is_long(tv) &&
			get_tarval_long(tv) >= get_mode_size_bits(mode)) {
			ir_node *block = get_nodes_block(node);
			ir_node *left = get_Shl_left(node);
			ir_node *c;
			long shf_cnt = get_tarval_long(tv) - get_mode_size_bits(mode);
			int idx = get_irn_idx(left);

			left = env->entries[idx]->low_word;
			idx = get_irn_idx(node);

			if (shf_cnt > 0) {
				c = new_r_Const_long(irg, block, mode_Iu, shf_cnt);
				env->entries[idx]->high_word = new_r_Shl(irg, block, left, c, mode);
			} else {
				env->entries[idx]->high_word = left;
			}  /* if */
			env->entries[idx]->low_word  = new_r_Const(irg, block, mode, get_mode_null(mode));

			return;
		}  /* if */
	}  /* if */
	lower_Shiftop(node, mode, env);
}  /* lower_Shl */

/**
 * Translate a Shrs and handle special cases.
 */
static void lower_Shrs(ir_node *node, ir_mode *mode, lower_env_t *env) {
	ir_node  *right = get_Shrs_right(node);
	ir_graph *irg = current_ir_graph;

	if (get_mode_arithmetic(mode) == irma_twos_complement && is_Const(right)) {
		tarval *tv = get_Const_tarval(right);

		if (tarval_is_long(tv) &&
			get_tarval_long(tv) >= get_mode_size_bits(mode)) {
			ir_node *block = get_nodes_block(node);
			ir_node *left = get_Shrs_left(node);
			long shf_cnt = get_tarval_long(tv) - get_mode_size_bits(mode);
			ir_node *c;
			int idx = get_irn_idx(left);

			left = env->entries[idx]->high_word;
			idx = get_irn_idx(node);

			if (shf_cnt > 0) {
				c = new_r_Const_long(irg, block, mode_Iu, shf_cnt);
				env->entries[idx]->low_word = new_r_Shrs(irg, block, left, c, mode);
			} else {
				env->entries[idx]->low_word = left;
			}  /* if */
			c = new_r_Const_long(irg, block, mode_Iu, get_mode_size_bits(mode) - 1);
			env->entries[idx]->high_word = new_r_Shrs(irg, block, left, c, mode);

			return;
		}  /* if */
	}  /* if */
	lower_Shiftop(node, mode, env);
}  /* lower_Shrs */

/**
 * Translate a Rot and handle special cases.
 */
static void lower_Rot(ir_node *node, ir_mode *mode, lower_env_t *env) {
	ir_node  *right = get_Rot_right(node);

	if (get_mode_arithmetic(mode) == irma_twos_complement && is_Const(right)) {
		tarval *tv = get_Const_tarval(right);

		if (tarval_is_long(tv) &&
			get_tarval_long(tv) == get_mode_size_bits(mode)) {
			ir_node *left = get_Rot_left(node);
			ir_node *h, *l;
			int idx = get_irn_idx(left);

			l = env->entries[idx]->low_word;
			h = env->entries[idx]->high_word;
			idx = get_irn_idx(node);

			env->entries[idx]->low_word  = h;
			env->entries[idx]->high_word = l;

			return;
		}  /* if */
	}  /* if */
	lower_Shiftop(node, mode, env);
}  /* lower_Rot */

/**
 * Translate an Unop.
 *
 * Create an intrinsic Call.
 */
static void lower_Unop(ir_node *node, ir_mode *mode, lower_env_t *env) {
	ir_node  *block, *irn;
	ir_node  *in[2];
	dbg_info *dbg;
	ir_type  *mtp;
	int      idx;
	ir_graph *irg;
	node_entry_t *entry;

	irn   = get_unop_op(node);
	entry = env->entries[get_irn_idx(irn)];
	assert(entry);

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

	in[0] = entry->low_word;
	in[1] = entry->high_word;

	dbg   = get_irn_dbg_info(node);
	block = get_nodes_block(node);
	irg   = current_ir_graph;

	mtp = mode_is_signed(mode) ? unop_tp_s : unop_tp_u;
	irn = get_intrinsic_address(mtp, get_irn_op(node), mode, mode, block, env);
	irn = new_rd_Call(dbg, irg, block, get_irg_no_mem(current_ir_graph),
		irn, 2, in, mtp);
	set_irn_pinned(irn, get_irn_pinned(node));
	irn = new_r_Proj(irg, block, irn, mode_T, pn_Call_T_result);

	idx = get_irn_idx(node);
	assert(idx < env->n_entries);
	env->entries[idx]->low_word  = new_r_Proj(irg, block, irn, mode, 0);
	env->entries[idx]->high_word = new_r_Proj(irg, block, irn, mode, 1);
}  /* lower_Unop */

/**
 * Translate a logical Binop.
 *
 * Create two logical Binops.
 */
static void lower_Binop_logical(ir_node *node, ir_mode *mode, lower_env_t *env,
								ir_node *(*constr_rd)(dbg_info *db, ir_graph *irg, ir_node *block, ir_node *op1, ir_node *op2, ir_mode *mode) ) {
	ir_node  *block, *irn;
	ir_node  *lop_l, *lop_h, *rop_l, *rop_h;
	dbg_info *dbg;
	int      idx;
	ir_graph *irg;
	node_entry_t *entry;

	irn   = get_binop_left(node);
	entry = env->entries[get_irn_idx(irn)];
	assert(entry);

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

	lop_l = entry->low_word;
	lop_h = entry->high_word;

	irn   = get_binop_right(node);
	entry = env->entries[get_irn_idx(irn)];
	assert(entry);

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

	rop_l = entry->low_word;
	rop_h = entry->high_word;

	dbg = get_irn_dbg_info(node);
	block = get_nodes_block(node);

	idx = get_irn_idx(node);
	assert(idx < env->n_entries);
	irg = current_ir_graph;
	env->entries[idx]->low_word  = constr_rd(dbg, irg, block, lop_l, rop_l, mode);
	env->entries[idx]->high_word = constr_rd(dbg, irg, block, lop_h, rop_h, mode);
}  /* lower_Binop_logical */

/** create a logical operation tranformation */
#define lower_logical(op)                                                \
static void lower_##op(ir_node *node, ir_mode *mode, lower_env_t *env) { \
	lower_Binop_logical(node, mode, env, new_rd_##op);                   \
}

lower_logical(And)
lower_logical(Or)
lower_logical(Eor)

/**
 * Translate a Not.
 *
 * Create two logical Nots.
 */
static void lower_Not(ir_node *node, ir_mode *mode, lower_env_t *env) {
	ir_node  *block, *irn;
	ir_node  *op_l, *op_h;
	dbg_info *dbg;
	int      idx;
	ir_graph *irg;
	node_entry_t *entry;

	irn   = get_Not_op(node);
	entry = env->entries[get_irn_idx(irn)];
	assert(entry);

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

	op_l = entry->low_word;
	op_h = entry->high_word;

	dbg   = get_irn_dbg_info(node);
	block = get_nodes_block(node);
	irg   = current_ir_graph;

	idx = get_irn_idx(node);
	assert(idx < env->n_entries);
	env->entries[idx]->low_word  = new_rd_Not(dbg, current_ir_graph, block, op_l, mode);
	env->entries[idx]->high_word = new_rd_Not(dbg, current_ir_graph, block, op_h, mode);
}  /* lower_Not */

/**
 * Translate a Minus.
 *
 * Create two Minus'.
 */
static void lower_Minus(ir_node *node, ir_mode *mode, lower_env_t *env) {
	ir_node  *block, *irn;
	ir_node  *op_l, *op_h;
	dbg_info *dbg;
	int      idx;
	ir_graph *irg;
	node_entry_t *entry;

	irn   = get_Minus_op(node);
	entry = env->entries[get_irn_idx(irn)];
	assert(entry);

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

	op_l = entry->low_word;
	op_h = entry->high_word;

	dbg   = get_irn_dbg_info(node);
	block = get_nodes_block(node);
	irg   = current_ir_graph;

	idx = get_irn_idx(node);
	assert(idx < env->n_entries);
	env->entries[idx]->low_word  = new_rd_Minus(dbg, current_ir_graph, block, op_l, mode);
	env->entries[idx]->high_word = new_rd_Minus(dbg, current_ir_graph, block, op_h, mode);
}  /* lower_Minus */

/**
 * Translate a Cond.
 */
static void lower_Cond(ir_node *node, ir_mode *mode, lower_env_t *env) {
	ir_node *cmp, *left, *right, *block;
	ir_node *sel = get_Cond_selector(node);
	ir_mode *m = get_irn_mode(sel);
	int     idx;

	if (m == mode_b) {
		node_entry_t *lentry, *rentry;
		ir_node  *proj, *projT = NULL, *projF = NULL;
		ir_node  *new_bl, *cmpH, *cmpL, *irn;
		ir_node  *projHF, *projHT;
		ir_node  *dst_blk;
		ir_graph *irg;
		pn_Cmp   pnc;
		dbg_info *dbg;

		cmp   = get_Proj_pred(sel);
		left  = get_Cmp_left(cmp);
		idx   = get_irn_idx(left);
		lentry = env->entries[idx];

		if (! lentry) {
			/* a normal Cmp */
			return;
		}  /* if */

		right = get_Cmp_right(cmp);
		idx   = get_irn_idx(right);
		rentry = env->entries[idx];
		assert(rentry);

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

		/* all right, build the code */
		for (proj = get_irn_link(node); proj; proj = get_irn_link(proj)) {
			long proj_nr = get_Proj_proj(proj);

			if (proj_nr == pn_Cond_true) {
				assert(projT == NULL && "more than one Proj(true)");
				projT = proj;
			} else {
				assert(proj_nr == pn_Cond_false);
				assert(projF == NULL && "more than one Proj(false)");
				projF = proj;
			}  /* if */
			mark_irn_visited(proj);
		}  /* for */
		assert(projT && projF);

		/* create a new high compare */
		block = get_nodes_block(cmp);
		dbg   = get_irn_dbg_info(cmp);
		irg   = current_ir_graph;

		cmpH = new_rd_Cmp(dbg, irg, block, lentry->high_word, rentry->high_word);

		pnc = get_Proj_proj(sel);
		if (pnc == pn_Cmp_Eq) {
			/* simple case:a == b <==> a_h == b_h && a_l == b_l */
			pmap_entry *entry = pmap_find(env->proj_2_block, projF);

			assert(entry);
			dst_blk = entry->value;

			irn = new_r_Proj(irg, block, cmpH, mode_b, pn_Cmp_Eq);
			dbg = get_irn_dbg_info(node);
			irn = new_rd_Cond(dbg, irg, block, irn);

			projHF = new_r_Proj(irg, block, irn, mode_X, pn_Cond_false);
			mark_irn_visited(projHF);
			exchange(projF, projHF);

			projHT = new_r_Proj(irg, block, irn, mode_X, pn_Cond_true);
			mark_irn_visited(projHT);

			new_bl = new_r_Block(irg, 1, &projHT);

			dbg   = get_irn_dbg_info(cmp);
			cmpL = new_rd_Cmp(dbg, irg, new_bl, lentry->low_word, rentry->low_word);
			irn = new_r_Proj(irg, new_bl, cmpL, mode_b, pn_Cmp_Eq);
			dbg = get_irn_dbg_info(node);
			irn = new_rd_Cond(dbg, irg, new_bl, irn);

			proj = new_r_Proj(irg, new_bl, irn, mode_X, pn_Cond_false);
			mark_irn_visited(proj);
			add_block_cf_input(dst_blk, projHF, proj);

			proj = new_r_Proj(irg, new_bl, irn, mode_X, pn_Cond_true);
			mark_irn_visited(proj);
			exchange(projT, proj);
		} else if (pnc == pn_Cmp_Lg) {
			/* simple case:a != b <==> a_h != b_h || a_l != b_l */
			pmap_entry *entry = pmap_find(env->proj_2_block, projT);

			assert(entry);
			dst_blk = entry->value;

			irn = new_r_Proj(irg, block, cmpH, mode_b, pn_Cmp_Lg);
			dbg = get_irn_dbg_info(node);
			irn = new_rd_Cond(dbg, irg, block, irn);

			projHT = new_r_Proj(irg, block, irn, mode_X, pn_Cond_true);
			mark_irn_visited(projHT);
			exchange(projT, projHT);

			projHF = new_r_Proj(irg, block, irn, mode_X, pn_Cond_false);
			mark_irn_visited(projHF);

			new_bl = new_r_Block(irg, 1, &projHF);

			dbg   = get_irn_dbg_info(cmp);
			cmpL = new_rd_Cmp(dbg, irg, new_bl, lentry->low_word, rentry->low_word);
			irn = new_r_Proj(irg, new_bl, cmpL, mode_b, pn_Cmp_Lg);
			dbg = get_irn_dbg_info(node);
			irn = new_rd_Cond(dbg, irg, new_bl, irn);

			proj = new_r_Proj(irg, new_bl, irn, mode_X, pn_Cond_true);
			mark_irn_visited(proj);
			add_block_cf_input(dst_blk, projHT, proj);

			proj = new_r_Proj(irg, new_bl, irn, mode_X, pn_Cond_false);
			mark_irn_visited(proj);
			exchange(projF, proj);
		} else {