ia32_transform.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.
 */

/**
 * @file
 * @brief       This file implements the IR transformation from firm into
 *              ia32-Firm.
 * @author      Christian Wuerdig, Matthias Braun
 * @version     $Id$
 */
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <limits.h>

#include "irargs_t.h"
#include "irnode_t.h"
#include "irgraph_t.h"
#include "irmode_t.h"
#include "iropt_t.h"
#include "irop_t.h"
#include "irprog_t.h"
#include "iredges_t.h"
#include "irgmod.h"
#include "irvrfy.h"
#include "ircons.h"
#include "irgwalk.h"
#include "irprintf.h"
#include "debug.h"
#include "irdom.h"
#include "archop.h"
#include "error.h"
#include "height.h"

#include "../benode_t.h"
#include "../besched.h"
#include "../beabi.h"
#include "../beutil.h"
#include "../beirg_t.h"
#include "../betranshlp.h"

#include "bearch_ia32_t.h"
#include "ia32_nodes_attr.h"
#include "ia32_transform.h"
#include "ia32_new_nodes.h"
#include "ia32_map_regs.h"
#include "ia32_dbg_stat.h"
#include "ia32_optimize.h"
#include "ia32_util.h"
#include "ia32_address_mode.h"

#include "gen_ia32_regalloc_if.h"

#define SFP_SIGN "0x80000000"
#define DFP_SIGN "0x8000000000000000"
#define SFP_ABS  "0x7FFFFFFF"
#define DFP_ABS  "0x7FFFFFFFFFFFFFFF"

#define TP_SFP_SIGN "ia32_sfp_sign"
#define TP_DFP_SIGN "ia32_dfp_sign"
#define TP_SFP_ABS  "ia32_sfp_abs"
#define TP_DFP_ABS  "ia32_dfp_abs"

#define ENT_SFP_SIGN "IA32_SFP_SIGN"
#define ENT_DFP_SIGN "IA32_DFP_SIGN"
#define ENT_SFP_ABS  "IA32_SFP_ABS"
#define ENT_DFP_ABS  "IA32_DFP_ABS"

#define mode_vfp	(ia32_reg_classes[CLASS_ia32_vfp].mode)
#define mode_xmm    (ia32_reg_classes[CLASS_ia32_xmm].mode)

DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)

/** hold the current code generator during transformation */
static ia32_code_gen_t *env_cg       = NULL;
static ir_node         *initial_fpcw = NULL;
static heights_t       *heights      = NULL;

extern ir_op *get_op_Mulh(void);

typedef ir_node *construct_binop_func(dbg_info *db, ir_graph *irg,
        ir_node *block, ir_node *base, ir_node *index, ir_node *op1,
        ir_node *op2, ir_node *mem);

typedef ir_node *construct_shift_func(dbg_info *db, ir_graph *irg,
        ir_node *block, ir_node *op1, ir_node *op2);

typedef ir_node *construct_binop_dest_func(dbg_info *db, ir_graph *irg,
        ir_node *block, ir_node *base, ir_node *index, ir_node *op,
        ir_node *mem);

typedef ir_node *construct_unop_dest_func(dbg_info *db, ir_graph *irg,
        ir_node *block, ir_node *base, ir_node *index, ir_node *mem);

typedef ir_node *construct_binop_float_func(dbg_info *db, ir_graph *irg,
        ir_node *block, ir_node *base, ir_node *index, ir_node *op1,
        ir_node *op2, ir_node *mem, ir_node *fpcw);

typedef ir_node *construct_unop_func(dbg_info *db, ir_graph *irg,
        ir_node *block, ir_node *op);

/****************************************************************************************************
 *                  _        _                        __                           _   _
 *                 | |      | |                      / _|                         | | (_)
 *  _ __   ___   __| | ___  | |_ _ __ __ _ _ __  ___| |_ ___  _ __ _ __ ___   __ _| |_ _  ___  _ __
 * | '_ \ / _ \ / _` |/ _ \ | __| '__/ _` | '_ \/ __|  _/ _ \| '__| '_ ` _ \ / _` | __| |/ _ \| '_ \
 * | | | | (_) | (_| |  __/ | |_| | | (_| | | | \__ \ || (_) | |  | | | | | | (_| | |_| | (_) | | | |
 * |_| |_|\___/ \__,_|\___|  \__|_|  \__,_|_| |_|___/_| \___/|_|  |_| |_| |_|\__,_|\__|_|\___/|_| |_|
 *
 ****************************************************************************************************/

static ir_node *try_create_Immediate(ir_node *node,
                                     char immediate_constraint_type);

static ir_node *create_immediate_or_transform(ir_node *node,
                                              char immediate_constraint_type);

static ir_node *create_I2I_Conv(ir_mode *src_mode, ir_mode *tgt_mode,
                                dbg_info *dbgi, ir_node *new_block,
                                ir_node *new_op);

/**
 * Return true if a mode can be stored in the GP register set
 */
static INLINE int mode_needs_gp_reg(ir_mode *mode) {
	if(mode == mode_fpcw)
		return 0;
	return mode_is_int(mode) || mode_is_reference(mode) || mode == mode_b;
}

/**
 * creates a unique ident by adding a number to a tag
 *
 * @param tag   the tag string, must contain a %d if a number
 *              should be added
 */
static ident *unique_id(const char *tag)
{
	static unsigned id = 0;
	char str[256];

	snprintf(str, sizeof(str), tag, ++id);
	return new_id_from_str(str);
}

/**
 * Get a primitive type for a mode.
 */
static ir_type *get_prim_type(pmap *types, ir_mode *mode)
{
	pmap_entry *e = pmap_find(types, mode);
	ir_type *res;

	if (! e) {
		char buf[64];
		snprintf(buf, sizeof(buf), "prim_type_%s", get_mode_name(mode));
		res = new_type_primitive(new_id_from_str(buf), mode);
		set_type_alignment_bytes(res, 16);
		pmap_insert(types, mode, res);
	}
	else
		res = e->value;
	return res;
}

/**
 * Get an atomic entity that is initialized with a tarval
 */
static ir_entity *ia32_get_entity_for_tv(ia32_isa_t *isa, ir_node *cnst)
{
	tarval *tv    = get_Const_tarval(cnst);
	pmap_entry *e = pmap_find(isa->tv_ent, tv);
	ir_entity *res;
	ir_graph *rem;

	if (! e) {
		ir_mode *mode = get_irn_mode(cnst);
		ir_type *tp = get_Const_type(cnst);
		if (tp == firm_unknown_type)
			tp = get_prim_type(isa->types, mode);

		res = new_entity(get_glob_type(), unique_id(".LC%u"), tp);

		set_entity_ld_ident(res, get_entity_ident(res));
		set_entity_visibility(res, visibility_local);
		set_entity_variability(res, variability_constant);
		set_entity_allocation(res, allocation_static);

		 /* we create a new entity here: It's initialization must resist on the
		    const code irg */
		rem = current_ir_graph;
		current_ir_graph = get_const_code_irg();
		set_atomic_ent_value(res, new_Const_type(tv, tp));
		current_ir_graph = rem;

		pmap_insert(isa->tv_ent, tv, res);
	} else {
		res = e->value;
	}

	return res;
}

static int is_Const_0(ir_node *node) {
	if(!is_Const(node))
		return 0;

	return classify_Const(node) == CNST_NULL;
}

static int is_Const_1(ir_node *node) {
	if(!is_Const(node))
		return 0;

	return classify_Const(node) == CNST_ONE;
}

static int is_Const_Minus_1(ir_node *node) {
	tarval  *tv;
	ir_mode *mode;
	if(!is_Const(node))
		return 0;

	mode = get_irn_mode(node);
	if(!mode_is_signed(mode))
		return 0;

	tv = get_Const_tarval(node);
	tv = tarval_neg(tv);

	return classify_tarval(tv) == CNST_ONE;
}

/**
 * Transforms a Const.
 */
static ir_node *gen_Const(ir_node *node) {
	ir_graph        *irg   = current_ir_graph;
	ir_node         *old_block = get_nodes_block(node);
	ir_node         *block = be_transform_node(old_block);
	dbg_info        *dbgi  = get_irn_dbg_info(node);
	ir_mode         *mode  = get_irn_mode(node);

	if (mode_is_float(mode)) {
		ir_node   *res   = NULL;
		ir_node   *noreg = ia32_new_NoReg_gp(env_cg);
		ir_node   *nomem = new_NoMem();
		ir_node   *load;
		ir_entity *floatent;
		cnst_classify_t clss = classify_Const(node);

		if (USE_SSE2(env_cg)) {
			if (clss == CNST_NULL) {
				load = new_rd_ia32_xZero(dbgi, irg, block);
				set_ia32_ls_mode(load, mode);
				res  = load;
			} else {
				floatent = ia32_get_entity_for_tv(env_cg->isa, node);

				load     = new_rd_ia32_xLoad(dbgi, irg, block, noreg, noreg, nomem,
											 mode);
				set_ia32_op_type(load, ia32_AddrModeS);
				set_ia32_am_sc(load, floatent);
				set_ia32_flags(load, get_ia32_flags(load) | arch_irn_flags_rematerializable);
				res = new_r_Proj(irg, block, load, mode_xmm, pn_ia32_xLoad_res);
			}
		} else {
			if (clss == CNST_NULL) {
				load = new_rd_ia32_vfldz(dbgi, irg, block);
				res  = load;
			} else if (clss == CNST_ONE) {
				load = new_rd_ia32_vfld1(dbgi, irg, block);
				res  = load;
			} else {
				floatent = ia32_get_entity_for_tv(env_cg->isa, node);

				load     = new_rd_ia32_vfld(dbgi, irg, block, noreg, noreg, nomem, mode);
				set_ia32_op_type(load, ia32_AddrModeS);
				set_ia32_am_sc(load, floatent);
				set_ia32_flags(load, get_ia32_flags(load) | arch_irn_flags_rematerializable);
				res = new_r_Proj(irg, block, load, mode_vfp, pn_ia32_vfld_res);
			}
			set_ia32_ls_mode(load, mode);
		}

		SET_IA32_ORIG_NODE(load, ia32_get_old_node_name(env_cg, node));

		/* Const Nodes before the initial IncSP are a bad idea, because
		 * they could be spilled and we have no SP ready at that point yet.
		 * So add a dependency to the initial frame pointer calculation to
		 * avoid that situation.
		 */
		if (get_irg_start_block(irg) == block) {
			add_irn_dep(load, get_irg_frame(irg));
		}

		SET_IA32_ORIG_NODE(load, ia32_get_old_node_name(env_cg, node));
		return res;
	} else {
		ir_node *cnst;
		tarval  *tv = get_Const_tarval(node);
		long     val;

		tv = tarval_convert_to(tv, mode_Iu);

		if(tv == get_tarval_bad() || tv == get_tarval_undefined()
				|| tv == NULL) {
			panic("couldn't convert constant tarval (%+F)", node);
		}
		val = get_tarval_long(tv);

		cnst = new_rd_ia32_Const(dbgi, irg, block, NULL, 0, val);
		SET_IA32_ORIG_NODE(cnst, ia32_get_old_node_name(env_cg, node));

		/* see above */
		if (get_irg_start_block(irg) == block) {
			add_irn_dep(cnst, get_irg_frame(irg));
		}

		return cnst;
	}
}

/**
 * Transforms a SymConst.
 */
static ir_node *gen_SymConst(ir_node *node) {
	ir_graph *irg   = current_ir_graph;
	ir_node  *old_block = get_nodes_block(node);
	ir_node  *block = be_transform_node(old_block);
	dbg_info *dbgi  = get_irn_dbg_info(node);
	ir_mode  *mode  = get_irn_mode(node);
	ir_node  *cnst;

	if (mode_is_float(mode)) {
		ir_node *noreg = ia32_new_NoReg_gp(env_cg);
		ir_node *nomem = new_NoMem();

		if (USE_SSE2(env_cg))
			cnst = new_rd_ia32_xLoad(dbgi, irg, block, noreg, noreg, nomem, mode_E);
		else
			cnst = new_rd_ia32_vfld(dbgi, irg, block, noreg, noreg, nomem, mode_E);
		set_ia32_am_sc(cnst, get_SymConst_entity(node));
	} else {
		ir_entity *entity;

		if(get_SymConst_kind(node) != symconst_addr_ent) {
			panic("backend only support symconst_addr_ent (at %+F)", node);
		}
		entity = get_SymConst_entity(node);
		cnst = new_rd_ia32_Const(dbgi, irg, block, entity, 0, 0);
	}

	/* Const Nodes before the initial IncSP are a bad idea, because
	 * they could be spilled and we have no SP ready at that point yet
	 */
	if (get_irg_start_block(irg) == block) {
		add_irn_dep(cnst, get_irg_frame(irg));
	}

	SET_IA32_ORIG_NODE(cnst, ia32_get_old_node_name(env_cg, node));

	return cnst;
}

/* Generates an entity for a known FP const (used for FP Neg + Abs) */
ir_entity *ia32_gen_fp_known_const(ia32_known_const_t kct) {
	static const struct {
		const char *tp_name;
		const char *ent_name;
		const char *cnst_str;
	} names [ia32_known_const_max] = {
		{ TP_SFP_SIGN, ENT_SFP_SIGN, SFP_SIGN },	/* ia32_SSIGN */
		{ TP_DFP_SIGN, ENT_DFP_SIGN, DFP_SIGN },	/* ia32_DSIGN */
		{ TP_SFP_ABS,  ENT_SFP_ABS,  SFP_ABS },		/* ia32_SABS */
		{ TP_DFP_ABS,  ENT_DFP_ABS,  DFP_ABS }		/* ia32_DABS */
	};
	static ir_entity *ent_cache[ia32_known_const_max];

	const char    *tp_name, *ent_name, *cnst_str;
	ir_type       *tp;
	ir_node       *cnst;
	ir_graph      *rem;
	ir_entity     *ent;
	tarval        *tv;
	ir_mode       *mode;

	ent_name = names[kct].ent_name;
	if (! ent_cache[kct]) {
		tp_name  = names[kct].tp_name;
		cnst_str = names[kct].cnst_str;

		mode = kct == ia32_SSIGN || kct == ia32_SABS ? mode_Iu : mode_Lu;
		//mode = mode_xmm;
		tv  = new_tarval_from_str(cnst_str, strlen(cnst_str), mode);
		tp  = new_type_primitive(new_id_from_str(tp_name), mode);
		/* these constants are loaded as part of an instruction, so they must be aligned
		   to 128 bit. */
		set_type_alignment_bytes(tp, 16);
		ent = new_entity(get_glob_type(), new_id_from_str(ent_name), tp);

		set_entity_ld_ident(ent, get_entity_ident(ent));
		set_entity_visibility(ent, visibility_local);
		set_entity_variability(ent, variability_constant);
		set_entity_allocation(ent, allocation_static);

		/* we create a new entity here: It's initialization must resist on the
		    const code irg */
		rem = current_ir_graph;
		current_ir_graph = get_const_code_irg();
		cnst = new_Const(mode, tv);
		current_ir_graph = rem;

		set_atomic_ent_value(ent, cnst);

		/* cache the entry */
		ent_cache[kct] = ent;
	}

	return ent_cache[kct];
}

#ifndef NDEBUG
/**
 * Prints the old node name on cg obst and returns a pointer to it.
 */
const char *ia32_get_old_node_name(ia32_code_gen_t *cg, ir_node *irn) {
	ia32_isa_t *isa = (ia32_isa_t *)cg->arch_env->isa;

	lc_eoprintf(firm_get_arg_env(), isa->name_obst, "%+F", irn);
	obstack_1grow(isa->name_obst, 0);
 	return obstack_finish(isa->name_obst);
}
#endif /* NDEBUG */

static int use_source_address_mode(ir_node *block, ir_node *node,
                                   ir_node *other)
{
	ir_mode *mode;
	ir_node *load;
	long     pn;

	if(!is_Proj(node))
		return 0;
	load = get_Proj_pred(node);
	pn   = get_Proj_proj(node);
	if(!is_Load(load) || pn != pn_Load_res)
		return 0;
	if(get_nodes_block(load) != block)
		return 0;
	/* we only use address mode if we're the only user of the load */
	if(get_irn_n_edges(node) > 1)
		return 0;

	mode = get_irn_mode(node);
	if(!mode_needs_gp_reg(mode))
		return 0;
	if(get_mode_size_bits(mode) != 32)
		return 0;

	/* don't do AM if other node inputs depend on the load (via mem-proj) */
	if(other != NULL && get_nodes_block(other) == block
			&& heights_reachable_in_block(heights, other, load))
		return 0;

	return 1;
}

typedef struct ia32_address_mode_t ia32_address_mode_t;
struct ia32_address_mode_t {
	ia32_address_t  addr;
	ir_mode        *ls_mode;
	ir_node        *mem_proj;
	ia32_op_type_t  op_type;
	ir_node        *new_op1;
	ir_node        *new_op2;
	int             commutative;
	int             flipped;
};

static void build_address(ia32_address_mode_t *am, ir_node *node)
{
	ia32_address_t *addr    = &am->addr;
	ir_node        *load    = get_Proj_pred(node);
	ir_node        *ptr     = get_Load_ptr(load);
	ir_node        *mem     = get_Load_mem(load);
	ir_node        *new_mem = be_transform_node(mem);
	ir_node        *base;
	ir_node        *index;

	am->ls_mode  = get_Load_mode(load);
	am->mem_proj = be_get_Proj_for_pn(load, pn_Load_M);

	/* construct load address */
	ia32_create_address_mode(addr, ptr, 0);
	base  = addr->base;
	index = addr->index;

	if(base == NULL) {
		base = ia32_new_NoReg_gp(env_cg);
	} else {
		base = be_transform_node(base);
	}

	if(index == NULL) {
		index = ia32_new_NoReg_gp(env_cg);
	} else {
		index = be_transform_node(index);
	}

	addr->base  = base;
	addr->index = index;
	addr->mem   = new_mem;
}

static void set_address(ir_node *node, ia32_address_t *addr)
{
	set_ia32_am_scale(node, addr->scale);
	set_ia32_am_sc(node, addr->symconst_ent);
	set_ia32_am_offs_int(node, addr->offset);
	if(addr->symconst_sign)
		set_ia32_am_sc_sign(node);
	if(addr->use_frame)
		set_ia32_use_frame(node);
	set_ia32_frame_ent(node, addr->frame_entity);
}

static void set_am_attributes(ir_node *node, ia32_address_mode_t *am)
{
	set_address(node, &am->addr);

	set_ia32_op_type(node, am->op_type);
	set_ia32_ls_mode(node, am->ls_mode);
	if(am->commutative)
		set_ia32_commutative(node);
}

static void match_arguments(ia32_address_mode_t *am, ir_node *block,
                            ir_node *op1, ir_node *op2, int commutative,
                            int use_am_and_immediates)
{
	ia32_address_t *addr     = &am->addr;
	ir_node        *noreg_gp = ia32_new_NoReg_gp(env_cg);
	ir_node        *new_op1;
	ir_node        *new_op2;

	memset(am, 0, sizeof(am[0]));

	new_op2 = try_create_Immediate(op2, 0);
	if(new_op2 == NULL && use_source_address_mode(block, op2, op1)) {
		build_address(am, op2);
		new_op1     = be_transform_node(op1);
		new_op2     = noreg_gp;
		am->op_type = ia32_AddrModeS;
	} else if(commutative && (new_op2 == NULL || use_am_and_immediates) &&
		      use_source_address_mode(block, op1, op2)) {
		build_address(am, op1);
		if(new_op2 != NULL) {
			new_op1 = noreg_gp;
		} else {
			new_op1 = be_transform_node(op2);
			new_op2 = noreg_gp;
			am->flipped = 1;
		}
		am->op_type = ia32_AddrModeS;
	} else {
		new_op1 = be_transform_node(op1);
		if(new_op2 == NULL)
			new_op2 = be_transform_node(op2);
		am->op_type = ia32_Normal;
	}
	if(addr->base == NULL)
		addr->base = noreg_gp;
	if(addr->index == NULL)
		addr->index = noreg_gp;
	if(addr->mem == NULL)
		addr->mem = new_NoMem();

	am->new_op1     = new_op1;
	am->new_op2     = new_op2;
	am->commutative = commutative;
}

static ir_node *fix_mem_proj(ir_node *node, ia32_address_mode_t *am)
{
	ir_graph *irg = current_ir_graph;
	ir_mode  *mode;
	ir_node  *load;

	if(am->mem_proj == NULL)
		return node;

	/* we have to create a mode_T so the old MemProj can attach to us */
	mode = get_irn_mode(node);
	load = get_Proj_pred(am->mem_proj);

	mark_irn_visited(load);
	be_set_transformed_node(load, node);

	if(mode != mode_T) {
		set_irn_mode(node, mode_T);
		return new_rd_Proj(NULL, irg, get_nodes_block(node), node, mode, 0);
	} else {
		return node;
	}
}

/**
 * Construct a standard binary operation, set AM and immediate if required.
 *
 * @param op1   The first operand
 * @param op2   The second operand
 * @param func  The node constructor function
 * @return The constructed ia32 node.
 */
static ir_node *gen_binop(ir_node *node, ir_node *op1, ir_node *op2,
                          construct_binop_func *func, int commutative)
{
	ir_node  *src_block = get_nodes_block(node);
	ir_node  *block     = be_transform_node(src_block);
	ir_graph *irg       = current_ir_graph;
	dbg_info *dbgi      = get_irn_dbg_info(node);
	ir_node  *new_node;
	ia32_address_mode_t  am;
	ia32_address_t      *addr = &am.addr;

	match_arguments(&am, src_block, op1, op2, commutative, 0);

	new_node = func(dbgi, irg, block, addr->base, addr->index, am.new_op1,
	                am.new_op2, addr->mem);
	set_am_attributes(new_node, &am);
	/* we can't use source address mode anymore when using immediates */
	if(is_ia32_Immediate(am.new_op1) || is_ia32_Immediate(am.new_op2))
		set_ia32_am_support(new_node, ia32_am_None, ia32_am_arity_none);
	SET_IA32_ORIG_NODE(new_node, ia32_get_old_node_name(env_cg, node));

	new_node = fix_mem_proj(new_node, &am);

	return new_node;
}

/**
 * Construct a standard binary operation, set AM and immediate if required.
 *
 * @param op1   The first operand
 * @param op2   The second operand
 * @param func  The node constructor function
 * @return The constructed ia32 node.
 */
static ir_node *gen_binop_sse_float(ir_node *node, ir_node *op1, ir_node *op2,
                                    construct_binop_func *func)
{
	ir_node  *block    = be_transform_node(get_nodes_block(node));
	ir_node  *new_op1  = be_transform_node(op1);
	ir_node  *new_op2  = be_transform_node(op2);
	ir_node  *new_node = NULL;
	dbg_info *dbgi     = get_irn_dbg_info(node);
	ir_graph *irg      = current_ir_graph;
	ir_mode  *mode     = get_irn_mode(node);
	ir_node  *noreg_gp = ia32_new_NoReg_gp(env_cg);
	ir_node  *nomem    = new_NoMem();

	new_node = func(dbgi, irg, block, noreg_gp, noreg_gp, new_op1, new_op2,
	                nomem);
	if (is_op_commutative(get_irn_op(node))) {
		set_ia32_commutative(new_node);
	}
	set_ia32_ls_mode(new_node, mode);

	SET_IA32_ORIG_NODE(new_node, ia32_get_old_node_name(env_cg, node));

	return new_node;
}

static ir_node *get_fpcw(void)
{
	ir_node *fpcw;
	if(initial_fpcw != NULL)
		return initial_fpcw;

	fpcw         = be_abi_get_ignore_irn(env_cg->birg->abi,
	                                     &ia32_fp_cw_regs[REG_FPCW]);
	initial_fpcw = be_transform_node(fpcw);

	return initial_fpcw;
}

/**
 * Construct a standard binary operation, set AM and immediate if required.
 *
 * @param op1   The first operand
 * @param op2   The second operand
 * @param func  The node constructor function
 * @return The constructed ia32 node.
 */
static ir_node *gen_binop_x87_float(ir_node *node, ir_node *op1, ir_node *op2,
                                    construct_binop_float_func *func)
{
	ir_node  *block    = be_transform_node(get_nodes_block(node));
	ir_node  *new_op1  = be_transform_node(op1);
	ir_node  *new_op2  = be_transform_node(op2);
	ir_node  *new_node = NULL;
	dbg_info *dbgi     = get_irn_dbg_info(node);
	ir_graph *irg      = current_ir_graph;
	ir_node  *noreg_gp = ia32_new_NoReg_gp(env_cg);
	ir_node  *nomem    = new_NoMem();

	new_node = func(dbgi, irg, block, noreg_gp, noreg_gp, new_op1, new_op2,
	                nomem, get_fpcw());
	if (is_op_commutative(get_irn_op(node))) {
		set_ia32_commutative(new_node);
	}

	SET_IA32_ORIG_NODE(new_node, ia32_get_old_node_name(env_cg, node));

	return new_node;
}

/**
 * Construct a shift/rotate binary operation, sets AM and immediate if required.
 *
 * @param op1   The first operand
 * @param op2   The second operand
 * @param func  The node constructor function
 * @return The constructed ia32 node.
 */
static ir_node *gen_shift_binop(ir_node *node, ir_node *op1, ir_node *op2,
                                construct_shift_func *func)
{
	dbg_info *dbgi      = get_irn_dbg_info(node);
	ir_graph *irg       = current_ir_graph;
	ir_node  *block     = get_nodes_block(node);
	ir_node  *new_block = be_transform_node(block);
	ir_node  *new_op1   = be_transform_node(op1);
	ir_node  *new_op2   = create_immediate_or_transform(op2, 0);
	ir_node  *res;

	assert(! mode_is_float(get_irn_mode(node))
	         && "Shift/Rotate with float not supported");

	res = func(dbgi, irg, new_block, new_op1, new_op2);
	SET_IA32_ORIG_NODE(res, ia32_get_old_node_name(env_cg, node));

	/* lowered shift instruction may have a dependency operand, handle it here */
	if (get_irn_arity(node) == 3) {
		/* we have a dependency */
		ir_node *new_dep = be_transform_node(get_irn_n(node, 2));
		add_irn_dep(res, new_dep);
	}

	return res;
}


/**
 * Construct a standard unary operation, set AM and immediate if required.
 *
 * @param op    The operand
 * @param func  The node constructor function
 * @return The constructed ia32 node.
 */
static ir_node *gen_unop(ir_node *node, ir_node *op, construct_unop_func *func)
{
	ir_node  *block    = be_transform_node(get_nodes_block(node));
	ir_node  *new_op   = be_transform_node(op);
	ir_node  *new_node = NULL;
	ir_graph *irg      = current_ir_graph;
	dbg_info *dbgi     = get_irn_dbg_info(node);

	new_node = func(dbgi, irg, block, new_op);

	SET_IA32_ORIG_NODE(new_node, ia32_get_old_node_name(env_cg, node));

	return new_node;
}

static ir_node *create_lea_from_address(dbg_info *dbgi,	ir_node *block,
                                        ia32_address_t *addr)
{
	ir_graph *irg   = current_ir_graph;
	ir_node  *base  = addr->base;
	ir_node  *index = addr->index;
	ir_node  *res;

	if(base == NULL) {
		base = ia32_new_NoReg_gp(env_cg);
	} else {
		base = be_transform_node(base);
	}

	if(index == NULL) {
		index = ia32_new_NoReg_gp(env_cg);
	} else {
		index = be_transform_node(index);
	}

	res = new_rd_ia32_Lea(dbgi, irg, block, base, index);
	set_address(res, addr);

	return res;
}

static int am_has_immediates(const ia32_address_t *addr)
{
	return addr->offset != 0 || addr->symconst_ent != NULL
		|| addr->frame_entity || addr->use_frame;
}

/**
 * Creates an ia32 Add.
 *
 * @return the created ia32 Add node
 */
static ir_node *gen_Add(ir_node *node) {
	ir_node  *block   = be_transform_node(get_nodes_block(node));
	ir_node  *op1     = get_Add_left(node);
	ir_node  *op2     = get_Add_right(node);
	ir_node  *new_op;
	ir_node  *new_op1;
	ir_graph *irg     = current_ir_graph;
	dbg_info *dbgi    = get_irn_dbg_info(node);
	ir_mode  *mode    = get_irn_mode(node);
	ir_node  *noreg   = ia32_new_NoReg_gp(env_cg);
	ir_node  *src_block = get_nodes_block(node);
	ir_node  *add_immediate_op;
	ia32_address_t       addr;
	ia32_address_mode_t  am;

	if (mode_is_float(mode)) {
		if (USE_SSE2(env_cg))
			return gen_binop_sse_float(node, op1, op2, new_rd_ia32_xAdd);
		else
			return gen_binop_x87_float(node, op1, op2, new_rd_ia32_vfadd);
	}

	/**
	 * Rules for an Add:
	 *   0. Immediate Trees (example Add(Symconst, Const) -> Const)
	 *   1. Add with immediate -> Lea
	 *   2. Add with possible source address mode -> Add
	 *   3. Otherwise -> Lea
	 */
	memset(&addr, 0, sizeof(addr));
	ia32_create_address_mode(&addr, node, 1);
	add_immediate_op = NULL;
	/* a constant? */
	if(addr.base == NULL && addr.index == NULL) {
		new_op = new_rd_ia32_Const(dbgi, irg, block, addr.symconst_ent,
								   addr.symconst_sign, addr.offset);
		add_irn_dep(new_op, get_irg_frame(irg));
		SET_IA32_ORIG_NODE(new_op, ia32_get_old_node_name(env_cg, node));
		return new_op;
	}
	/* add with immediate? */
	if(addr.index == NULL) {
		add_immediate_op = addr.base;
	} else if(addr.base == NULL && addr.scale == 0) {
		add_immediate_op = addr.index;
	}

	if(add_immediate_op != NULL) {
		if(!am_has_immediates(&addr)) {
#ifdef DEBUG_libfirm
			ir_fprintf(stderr, "Optimisation warning Add x,0 (%+F) found\n",
					   node);
#endif
			return be_transform_node(add_immediate_op);
		}

		new_op = create_lea_from_address(dbgi, block, &addr);
		SET_IA32_ORIG_NODE(new_op, ia32_get_old_node_name(env_cg, node));
		return new_op;
	}

	/* test if we can use source address mode */
	memset(&am, 0, sizeof(am));
	new_op1 = NULL;
	if(use_source_address_mode(src_block, op2, op1)) {
		build_address(&am, op2);
		new_op1 = be_transform_node(op1);
	} else if(use_source_address_mode(src_block, op1, op2)) {
		build_address(&am, op1);
		new_op1 = be_transform_node(op2);
	}
	/* construct an Add with source address mode */
	if(new_op1 != NULL) {
		ia32_address_t *am_addr = &am.addr;
		new_op = new_rd_ia32_Add(dbgi, irg, block, am_addr->base,
		                         am_addr->index, new_op1, noreg, am_addr->mem);
		set_address(new_op, am_addr);
		set_ia32_op_type(new_op, ia32_AddrModeS);
		set_ia32_ls_mode(new_op, am.ls_mode);
		set_ia32_commutative(new_op);
		SET_IA32_ORIG_NODE(new_op, ia32_get_old_node_name(env_cg, node));

		new_op = fix_mem_proj(new_op, &am);

		return new_op;
	}

	/* otherwise construct a lea */
	new_op = create_lea_from_address(dbgi, block, &addr);
	SET_IA32_ORIG_NODE(new_op, ia32_get_old_node_name(env_cg, node));
	return new_op;
}

/**
 * Creates an ia32 Mul.
 *
 * @return the created ia32 Mul node
 */
static ir_node *gen_Mul(ir_node *node) {
	ir_node *op1  = get_Mul_left(node);
	ir_node *op2  = get_Mul_right(node);
	ir_mode *mode = get_irn_mode(node);

	if (mode_is_float(mode)) {
		if (USE_SSE2(env_cg))
			return gen_binop_sse_float(node, op1, op2, new_rd_ia32_xMul);
		else
			return gen_binop_x87_float(node, op1, op2, new_rd_ia32_vfmul);
	}

	/*
		for the lower 32bit of the result it doesn't matter whether we use
		signed or unsigned multiplication so we use IMul as it has fewer
		constraints
	*/
	return gen_binop(node, op1, op2, new_rd_ia32_IMul, 1);
}

/**
 * Creates an ia32 Mulh.
 * Note: Mul produces a 64Bit result and Mulh returns the upper 32 bit of
 * this result while Mul returns the lower 32 bit.
 *
 * @return the created ia32 Mulh node
 */
static ir_node *gen_Mulh(ir_node *node) {
	ir_node  *block   = be_transform_node(get_nodes_block(node));
	ir_node  *op1     = get_irn_n(node, 0);
	ir_node  *new_op1 = be_transform_node(op1);
	ir_node  *op2     = get_irn_n(node, 1);
	ir_node  *new_op2 = be_transform_node(op2);
	ir_graph *irg     = current_ir_graph;
	dbg_info *dbgi    = get_irn_dbg_info(node);
	ir_node  *noreg   = ia32_new_NoReg_gp(env_cg);
	ir_mode  *mode    = get_irn_mode(node);
	ir_node  *proj_EDX, *res;

	assert(!mode_is_float(mode) && "Mulh with float not supported");
	if (mode_is_signed(mode)) {
		res = new_rd_ia32_IMul1OP(dbgi, irg, block, noreg, noreg, new_op1,
		                          new_op2, new_NoMem());
	} else {
		res = new_rd_ia32_Mul(dbgi, irg, block, noreg, noreg, new_op1, new_op2,
		                      new_NoMem());
	}

	set_ia32_commutative(res);

	proj_EDX = new_rd_Proj(dbgi, irg, block, res, mode_Iu, pn_EDX);

	return proj_EDX;
}



/**
 * Creates an ia32 And.
 *
 * @return The created ia32 And node
 */
static ir_node *gen_And(ir_node *node) {
	ir_node *op1 = get_And_left(node);
	ir_node *op2 = get_And_right(node);
	assert(! mode_is_float(get_irn_mode(node)));

	/* is it a zero extension? */
	if (is_Const(op2)) {
		tarval   *tv    = get_Const_tarval(op2);
		long      v     = get_tarval_long(tv);