ia32_transform.c

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

/**
 * @file
 * @brief       This file implements the IR transformation from firm into
 *              ia32-Firm.
 * @author      Christian Wuerdig, Matthias Braun
 */
#include <stdbool.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 "irouts.h"
#include "irgmod.h"
#include "ircons.h"
#include "irgwalk.h"
#include "irprintf.h"
#include "debug.h"
#include "irdom.h"
#include "iropt.h"
#include "panic.h"
#include "array.h"
#include "heights.h"
#include "tv_t.h"

#include "bediagnostic.h"
#include "benode.h"
#include "betranshlp.h"
#include "be_t.h"
#include "beutil.h"

#include "gen_ia32_regalloc_if.h"
#include "ia32_architecture.h"
#include "ia32_bearch_t.h"
#include "ia32_new_nodes.h"
#include "ia32_nodes_attr.h"
#include "ia32_transform.h"
#include "util.h"
#include "x86_address_mode.h"
#include "x86_cconv.h"
#include "x86_x87.h"

/* define this to construct SSE constants instead of load them */
#undef CONSTRUCT_SSE_CONST

DEBUG_ONLY(static firm_dbg_module_t *dbg;)

static x86_cconv_t          *current_cconv;
static be_stack_env_t        stack_env;
static ir_heights_t         *heights;
static x86_immediate_kind_t  lconst_imm_kind;
static x86_addr_variant_t    lconst_variant;
static ir_node              *initial_va_list;

/** we don't have a concept of aliasing registers, so enumerate them
 * manually for the asm nodes. */
const x86_clobber_name_t ia32_additional_clobber_names[] = {
	{ "al", REG_EAX }, { "ah", REG_EAX }, { "ax", REG_EAX },
	{ "bl", REG_EBX }, { "bh", REG_EBX }, { "bx", REG_EBX },
	{ "cl", REG_ECX }, { "ch", REG_ECX }, { "cx", REG_ECX },
	{ "dl", REG_EDX }, { "dh", REG_EDX }, { "dx", REG_EDX },
	{ "si", REG_ESI }, { "di", REG_EDI }, { "sp", REG_ESP },
	{ "bp", REG_EBP }, { NULL, ~0u }
};

#define GP &ia32_reg_classes[CLASS_ia32_gp]
#define FP &ia32_reg_classes[CLASS_ia32_fp]
const x86_asm_constraint_list_t ia32_asm_constraints = {
	['A'] = { MATCH_REG, GP, 1 << REG_GP_EAX | 1 << REG_GP_EDX },
	['D'] = { MATCH_REG, GP, 1 << REG_GP_EDI },
	['I'] = { MATCH_IMM, GP, 0 },
	['J'] = { MATCH_IMM, GP, 0 },
	['K'] = { MATCH_IMM, GP, 0 },
	['L'] = { MATCH_IMM, GP, 0 },
	['M'] = { MATCH_IMM, GP, 0 },
	['N'] = { MATCH_IMM, GP, 0 },
	['O'] = { MATCH_IMM, GP, 0 },
	['R'] = { MATCH_REG, GP, 0 },
	['S'] = { MATCH_REG, GP, 1 << REG_GP_ESI },
	['Q'] = { MATCH_REG, GP, 1 << REG_GP_EAX | 1 << REG_GP_EBX
		| 1 << REG_GP_ECX | 1 << REG_GP_EDX },
	['V'] = { MATCH_MEM, GP, 0 },
	['X'] = { MATCH_ANY, GP, 0 },
	['a'] = { MATCH_REG, GP, 1 << REG_GP_EAX },
	['b'] = { MATCH_REG, GP, 1 << REG_GP_EBX },
	['c'] = { MATCH_REG, GP, 1 << REG_GP_ECX },
	['d'] = { MATCH_REG, GP, 1 << REG_GP_EDX },
	['e'] = { MATCH_IMM, GP, 0 },
	['f'] = { MATCH_REG, FP, 0 },
	['g'] = { MATCH_ANY, GP, 0 },
	['i'] = { MATCH_IMM, GP, 0 },
	['l'] = { MATCH_REG, GP, 1 << REG_GP_EAX | 1 << REG_GP_EBX
		| 1 << REG_GP_ECX | 1 << REG_GP_EDX | 1 << REG_GP_ESI
		| 1 << REG_GP_EDI | 1 << REG_GP_EBP },
	['m'] = { MATCH_MEM, GP, 0 },
	['n'] = { MATCH_IMM, GP, 0 },
	['o'] = { MATCH_MEM, GP, 0 },
	['p'] = { MATCH_REG, GP, 0 },
	['q'] = { MATCH_REG, GP, 1 << REG_GP_EAX | 1 << REG_GP_EBX
		| 1 << REG_GP_ECX | 1 << REG_GP_EDX },
	['r'] = { MATCH_REG, GP, 0 },
	['t'] = { MATCH_REG, FP, 1 << REG_FP_ST0 },
	['u'] = { MATCH_REG, FP, 1 << REG_FP_ST1 },
	['x'] = { MATCH_REG, &ia32_reg_classes[CLASS_ia32_xmm], 0 },

	// There are more constraints and in general there is alot of internal gcc
	// logic at play not everything is documented in the manual. In the gcc
	// source you can look at reload.c, stmt.c and constraints.md. I am not sure
	// how much we want/need to understand and reimplement here.
};
#undef GP
#undef FP

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

typedef ir_node *construct_binop_flags_func(dbg_info *db, ir_node *block,
        ir_node *base, ir_node *index, ir_node *mem, ir_node *op1, ir_node *op2,
        ir_node *flags, x86_insn_size_t size);

typedef ir_node *construct_shift_func(dbg_info *db, ir_node *block,
        ir_node *op1, ir_node *op2, x86_insn_size_t size);

typedef ir_node *construct_binop_dest_func(dbg_info *db, ir_node *block,
        ir_node *base, ir_node *index, ir_node *mem, ir_node *op,
        x86_insn_size_t size);

typedef ir_node *construct_unop_dest_func(dbg_info *db, ir_node *block,
        ir_node *base, ir_node *index, ir_node *mem, x86_insn_size_t size);

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

typedef ir_node *construct_unop_func(dbg_info *db, ir_node *block, ir_node *op,
                                     x86_insn_size_t size);

static ir_node *create_immediate_or_transform(ir_node *node,
                                              const char immediate_mode);

static ir_node *create_I2I_Conv(ir_mode *src_mode, dbg_info *dbgi, ir_node *block, ir_node *op);

/* its enough to have those once */
static ir_node *nomem;
static ir_node *noreg_GP;

static bool mode_needs_gp_reg(ir_mode *mode)
{
	return get_mode_arithmetic(mode) == irma_twos_complement;
}

/** Return non-zero is a node represents the 0 constant. */
static bool is_Const_0(ir_node *node)
{
	return is_Const(node) && is_Const_null(node);
}

/** Return non-zero is a node represents the 1 constant. */
static bool is_Const_1(ir_node *node)
{
	return is_Const(node) && is_Const_one(node);
}

/** Return non-zero is a node represents the -1 constant. */
static bool is_Const_Minus_1(ir_node *node)
{
	return is_Const(node) && is_Const_all_one(node);
}

/**
 * returns true if constant can be created with a simple float command
 */
static bool is_simple_x87_Const(ir_node *node)
{
	ir_tarval *tv = get_Const_tarval(node);
	if (tarval_is_null(tv) || tarval_is_one(tv))
		return true;

	/* TODO: match all the other float constants */
	return false;
}

/**
 * returns true if constant can be created with a simple float command
 */
static bool is_simple_sse_Const(ir_node *node)
{
	ir_tarval *tv   = get_Const_tarval(node);
	ir_mode   *mode = get_tarval_mode(tv);

	if (get_mode_size_bits(mode) == 32)
		return true;

	if (tarval_is_null(tv)
#ifdef CONSTRUCT_SSE_CONST
	    || tarval_is_one(tv)
#endif
	   )
		return true;
#ifdef CONSTRUCT_SSE_CONST
	if (mode == ia32_mode_float64) {
		unsigned const val = be_get_tv_bits32(tv, 0);
		if (val == 0)
			/* lower 32bit are zero, really a 32bit constant */
			return true;
	}
#endif /* CONSTRUCT_SSE_CONST */
	/* TODO: match all the other float constants */
	return false;
}

ir_node *ia32_get_pic_base(ir_graph *irg)
{
	ir_node **const get_eip = &ia32_get_irg_data(irg)->get_eip;
	if (!*get_eip) {
		ir_node *const block = get_irg_start_block(irg);
		*get_eip = new_bd_ia32_GetEIP(NULL, block);
	}
	return *get_eip;
}

/**
 * return NoREG or pic_base in case of PIC.
 * This is necessary as base address for newly created symbols
 */
static ir_node *get_global_base(ir_graph *const irg)
{
	if (be_options.pic_style != BE_PIC_NONE)
		return ia32_get_pic_base(irg);
	return noreg_GP;
}

static ir_node *get_initial_sp(ir_graph *irg)
{
	return be_get_Start_proj(irg, &ia32_registers[REG_ESP]);
}

static ir_node *get_initial_fp(ir_graph *irg)
{
	return be_get_Start_proj(irg, &ia32_registers[REG_EBP]);
}

static ir_node *get_initial_fpcw(ir_graph *irg)
{
	return be_get_Start_proj(irg, &ia32_registers[REG_FPCW]);
}

ir_node *ia32_create_Immediate_full(ir_graph *const irg,
                                    x86_imm32_t const *const imm)
{
	ir_node *const start_block = get_irg_start_block(irg);
	ir_node *const immediate
		= new_bd_ia32_Immediate(NULL, start_block, imm);
	arch_set_irn_register(immediate, &ia32_registers[REG_GP_NOREG]);
	return immediate;
}

static void adjust_relocation(x86_imm32_t *imm)
{
	if (imm->kind != X86_IMM_ADDR)
		return;
	ir_entity *entity = imm->entity;
	if (is_tls_entity(entity)) {
		imm->kind = entity_has_definition(entity) ? X86_IMM_TLS_LE
		                                          : X86_IMM_TLS_IE;
		return;
	}
}

static ir_node *try_create_Immediate(const ir_node *node, char const constraint)
{
	x86_imm32_t immediate;
	if (!x86_match_immediate(&immediate, node, constraint))
		return NULL;
	adjust_relocation(&immediate);

	ir_graph *const irg = get_irn_irg(node);
	return ia32_create_Immediate_full(irg, &immediate);
}

static ir_entity *create_float_const_entity(ir_tarval *tv, ident *name)
{
	ir_mode *mode = get_tarval_mode(tv);
	if (!ia32_cg_config.use_sse2) {
		/* try to reduce the mode to produce smaller sized entities */
		ir_mode *const modes[] = { mode_F, mode_D, NULL };
		for (ir_mode *const *i = modes;; ++i) {
			ir_mode *const to = *i;
			if (!to || to == mode)
				break;
			if (tarval_ieee754_can_conv_lossless(tv, to)) {
				tv   = tarval_convert_to(tv, to);
				mode = to;
				break;
			}
		}
	}

	ir_entity *res = pmap_get(ir_entity, ia32_tv_ent, tv);
	if (!res) {
		if (!name)
			name = id_unique("C");

		ir_type *const tp = get_type_for_mode(mode);
		res = new_global_entity(get_glob_type(), name, tp,
		                        ir_visibility_private,
		                        IR_LINKAGE_CONSTANT | IR_LINKAGE_NO_IDENTITY);

		ir_initializer_t *const initializer = create_initializer_tarval(tv);
		set_entity_initializer(res, initializer);

		pmap_insert(ia32_tv_ent, tv, res);
	}
	return res;
}

static void set_am_const_entity(ir_node *node, ir_entity *entity)
{
	ia32_attr_t *const attr = get_ia32_attr(node);
	attr->addr.immediate = (x86_imm32_t) {
		.kind   = lconst_imm_kind,
		.entity = entity,
	};
	attr->addr.variant = lconst_variant;
}

/**
 * Transforms a Const.
 */
static ir_node *gen_Const(ir_node *node)
{
	ir_node        *const block = be_transform_nodes_block(node);
	dbg_info       *const dbgi  = get_irn_dbg_info(node);
	ir_mode        *const mode  = get_irn_mode(node);
	ir_tarval      *const tv    = get_Const_tarval(node);
	x86_insn_size_t const size  = x86_size_from_mode(mode);

	if (mode_is_float(mode)) {
		ir_graph *const irg = get_irn_irg(node);
		ir_node        *res;
		if (ia32_cg_config.use_sse2) {
			if (tarval_is_null(tv)) {
				res = new_bd_ia32_xZero(dbgi, block, size);
#ifdef CONSTRUCT_SSE_CONST
			} else if (tarval_is_one(tv)) {
				int      cnst    = mode == ia32_mode_float32 ? 26 : 55;
				ir_node *imm1    = ia32_create_Immediate(irg, cnst);
				ir_node *imm2    = ia32_create_Immediate(irg, 2);
				ir_node *allones = new_bd_ia32_xAllOnes(dbgi, block, size);
				ir_node *pslld   = new_bd_ia32_xPslld(dbgi, block, allones,
				                                      imm1, size);
				res = new_bd_ia32_xPsrld(dbgi, block, pslld, imm2, size);
#endif /* CONSTRUCT_SSE_CONST */
			} else if (mode == ia32_mode_float32) {
				/* we can place any 32bit constant by using a movd gp, sse */
				x86_imm32_t imm = {
					.offset = be_get_tv_bits32(tv, 0),
				};
				ir_node *cnst = new_bd_ia32_Const(dbgi, block, &imm);
				res = new_bd_ia32_xMovd(dbgi, block, cnst);
			} else {
#ifdef CONSTRUCT_SSE_CONST
				if (mode == ia32_mode_float64 && be_get_tv_bits32(tv, 0) == 0) {
					ir_node *imm32 = ia32_create_Immediate(irg, 32);

					/* fine, lower 32bit are zero, produce 32bit value */
					x86_imm32_t const imm = {
						.offset = be_get_tv_bits32(tv, 4),
					};
					ir_node *const cnst = new_bd_ia32_Const(dbgi, block, &imm);
					ir_node *const movd = new_bd_ia32_xMovd(dbgi, block, cnst);
					res = new_bd_ia32_xPsllq(dbgi, block, movd, imm32, size);
					goto end;
				}
#endif /* CONSTRUCT_SSE_CONST */
				ir_entity *const floatent = create_float_const_entity(tv, NULL);

				ir_node *base = get_global_base(irg);
				ir_node *load = new_bd_ia32_xLoad(dbgi, block, base, noreg_GP,
				                                  nomem, size);
				set_irn_pinned(load, false);
				set_ia32_op_type(load, ia32_AddrModeS);
				set_am_const_entity(load, floatent);
				arch_add_irn_flags(load, arch_irn_flag_rematerializable);
				res = be_new_Proj(load, pn_ia32_xLoad_res);
			}
		} else {
			if (tarval_is_null(tv)) {
				res = new_bd_ia32_fldz(dbgi, block);
			} else if (tarval_is_one(tv)) {
				res = new_bd_ia32_fld1(dbgi, block);
			} else if (tarval_is_minus_null(tv)) {
				res = new_bd_ia32_fldz(dbgi, block);
				goto negate;
			} else if (tarval_is_minus_one(tv)) {
				res = new_bd_ia32_fld1(dbgi, block);
negate:
				res = new_bd_ia32_fchs(dbgi, block, res);
			} else {
				ir_entity *const floatent = create_float_const_entity(tv, NULL);
				/* create_float_const_ent is smart and sometimes creates
				   smaller entities */
				ir_mode *ent_mode = get_type_mode(get_entity_type(floatent));
				x86_insn_size_t const size = x86_size_from_mode(ent_mode);
				ir_node *base = get_global_base(irg);
				ir_node *load = new_bd_ia32_fld(dbgi, block, base, noreg_GP,
				                                nomem, size);
				set_irn_pinned(load, false);
				ia32_attr_t *const attr = get_ia32_attr(load);
				attr->addr = (x86_addr_t) {
					.immediate = {
						.kind   = lconst_imm_kind,
						.entity = floatent,
					},
					.variant = lconst_variant,
				};
				set_ia32_op_type(load, ia32_AddrModeS);
				arch_add_irn_flags(load, arch_irn_flag_rematerializable);
				res = be_new_Proj(load, pn_ia32_fld_res);
			}
		}
#ifdef CONSTRUCT_SSE_CONST
end:
#endif
		return res;
	} else { /* non-float mode */
		ir_tarval *conv_tv = tarval_convert_to(tv, ia32_mode_gp);
		if (conv_tv == get_tarval_bad())
			panic("couldn't convert constant tarval (%+F)", node);

		x86_imm32_t imm = { .offset = get_tarval_long(conv_tv) };
		return new_bd_ia32_Const(dbgi, block, &imm);
	}
}

/**
 * Transforms an Address.
 */
static ir_node *gen_Address(ir_node *node)
{
	ir_node  *block = be_transform_nodes_block(node);
	dbg_info *dbgi  = get_irn_dbg_info(node);
	ir_mode  *mode  = get_irn_mode(node);

	if (!mode_needs_gp_reg(mode))
		panic("unexpected mode for Address");

	ir_entity *entity = get_Address_entity(node);
	x86_imm32_t imm = {
		.kind   = X86_IMM_ADDR,
		.entity = entity,
	};
	adjust_relocation(&imm);

	if (is_tls_entity(entity)) {
		ir_node     *const tls_base = new_bd_ia32_LdTls(NULL, block);
		ir_node     *const lea      = new_bd_ia32_Lea(dbgi, block, tls_base, noreg_GP);
		ia32_attr_t *const attr     = get_ia32_attr(lea);
		attr->addr.variant   = X86_ADDR_BASE;
		attr->addr.immediate = imm;
		return lea;
	} else {
		return new_bd_ia32_Const(dbgi, block, &imm);
	}
}

static ir_node *gen_be_Relocation(ir_node *node)
{
	ir_node  *block = be_transform_nodes_block(node);
	dbg_info *dbgi  = get_irn_dbg_info(node);
	x86_imm32_t imm = {
		.kind   = (x86_immediate_kind_t)be_get_Relocation_kind(node),
		.entity = be_get_Relocation_entity(node),
	};
	return new_bd_ia32_Const(dbgi, block, &imm);
}

/**
 * Create a float[2] array type for the given atomic type.
 *
 * @param tp  the atomic type
 */
static ir_type *ia32_create_float_array(ir_type *tp)
{
	static ir_type *float_F;
	static ir_type *float_D;
	static ir_type *float_E;
	ir_mode  *const mode = get_type_mode(tp);
	ir_type **const arr  =
		mode == ia32_mode_float32 ? &float_F :
		mode == ia32_mode_float64 ? &float_D :
		/*                       */ &float_E;
	if (!*arr)
		*arr = new_type_array(tp, 2);
	return *arr;
}

/* Generates an entity for a known FP const (used for FP Neg + Abs) */
ir_entity *ia32_gen_fp_known_const(ia32_known_const_t const kct)
{
	static const struct {
		const char *name;
		const char *cnst_str;
		char        mode;
	} names [ia32_known_const_max] = {
		{ "C_sfp_sign", "0x80000000",          0 },
		{ "C_dfp_sign", "0x8000000000000000",  1 },
		{ "C_sfp_abs",  "0x7FFFFFFF",          0 },
		{ "C_dfp_abs",  "0x7FFFFFFFFFFFFFFF",  1 },
		{ "C_ull_bias", "0x10000000000000000", 2 }
	};
	static ir_entity *ent_cache[ia32_known_const_max];

	ir_entity *ent = ent_cache[kct];

	if (ent == NULL) {
		char const *const cnst_str = names[kct].cnst_str;
		ident      *const name     = new_id_from_str(names[kct].name);
		ir_mode          *mode;
		switch (names[kct].mode) {
		case 0:  mode = ia32_mode_gp; break;
		case 1:  mode = mode_Lu; break;
		case 2:  mode = ia32_mode_float32;  break;
		default: panic("internal compiler error");
		}
		ir_tarval *tv = new_tarval_from_str(cnst_str, strlen(cnst_str), mode);

		if (kct == ia32_ULLBIAS) {
			ir_type *type  = get_type_for_mode(ia32_mode_float32);
			ir_type *atype = ia32_create_float_array(type);

			ent = new_global_entity(get_glob_type(), name, atype,
			                        ir_visibility_private,
			                        IR_LINKAGE_CONSTANT|IR_LINKAGE_NO_IDENTITY);

			ir_initializer_t *initializer = create_initializer_compound(2);
			set_initializer_compound_value(initializer, 0,
				create_initializer_tarval(get_mode_null(mode)));
			set_initializer_compound_value(initializer, 1,
				create_initializer_tarval(tv));
			set_entity_initializer(ent, initializer);
		} else {
			ent = create_float_const_entity(tv, name);
		}
		/* cache the entry */
		ent_cache[kct] = ent;
	}

	return ent_cache[kct];
}

static ir_node *gen_Unknown(ir_node *node)
{
	ir_mode  *mode  = get_irn_mode(node);
	dbg_info *dbgi  = get_irn_dbg_info(node);
	ir_graph *irg   = get_irn_irg(node);
	ir_node  *block = get_irg_start_block(irg);
	ir_node  *res   = NULL;

	if (mode_is_float(mode)) {
		if (ia32_cg_config.use_sse2) {
			res = new_bd_ia32_xUnknown(dbgi, block, X86_SIZE_128);
		} else {
			res = new_bd_ia32_fldz(dbgi, block);
		}
	} else if (mode_needs_gp_reg(mode)) {
		res = new_bd_ia32_Unknown(dbgi, block);
	} else {
		panic("unsupported Unknown-Mode");
	}

	return res;
}

/**
 * Checks whether other node inputs depend on the am_candidate (via mem-proj).
 */
static bool prevents_AM(ir_node *const block, ir_node *const am_candidate,
                        ir_node *const other)
{
	if (get_nodes_block(other) != block)
		return false;

	if (is_Sync(other)) {
		int i;

		for (i = get_Sync_n_preds(other) - 1; i >= 0; --i) {
			ir_node *const pred = get_Sync_pred(other, i);

			if (get_nodes_block(pred) != block)
				continue;

			/* Do not block ourselves from getting eaten */
			if (is_Proj(pred) && get_Proj_pred(pred) == am_candidate)
				continue;

			if (!heights_reachable_in_block(heights, pred, am_candidate))
				continue;

			return true;
		}

		return false;
	} else {
		/* Do not block ourselves from getting eaten */
		if (is_Proj(other) && get_Proj_pred(other) == am_candidate)
			return false;

		if (!heights_reachable_in_block(heights, other, am_candidate))
			return false;

		return true;
	}
}

static bool cmp_can_use_sub_flags(ir_node *cmp, ir_node *sub, bool *swap)
{
	ir_node *cmp_block = get_nodes_block(cmp);
	ir_node *sub_block = get_nodes_block(sub);

	if (!(block_dominates(cmp_block, sub_block) ||
	      block_dominates(sub_block, cmp_block))) {
		return false;
	}

	ir_node *cmp_left  = get_Cmp_left(cmp);
	ir_node *cmp_right = get_Cmp_right(cmp);
	ir_node *sub_left  = get_Sub_left(sub);
	ir_node *sub_right = get_Sub_right(sub);

	if (cmp_left == sub_left && cmp_right == sub_right) {
		*swap = false;
	} else if (cmp_left == sub_right && cmp_right == sub_left) {
		*swap = true;
	} else {
		return false;
	}

	ir_mode *sub_mode = get_irn_mode(sub_left);
	if (get_mode_size_bits(sub_mode) != 32 &&
	    (!be_upper_bits_clean(sub_left,  sub_mode) ||
	     !be_upper_bits_clean(sub_right, sub_mode))) {
		return false;
	}

	return true;
}

/**
 * return true if the users of the given value will be merged by later
 * optimization. This applies to multiple Cmp nodes (and maybe a Sub
 * node) with the same inputs.
 */
static bool users_will_merge(ir_node *proj)
{
	ir_node *sub = NULL;

	/* Check that there is one Sub and some Cmps. */
	foreach_out_edge(proj, edge) {
		ir_node *user = get_edge_src_irn(edge);

		if (is_Sub(user)) {
			if (sub == NULL) {
				sub = user;
			} else {
				/* Two Subs will not merge */
				return false;
			}
		} else if (!is_Cmp(user)) {
			return false;
		}
	}

	if (sub == NULL) {
		/* Cmps only will not merge.
		 * (probably need to be rematerialized later anyway) */
		return false;
	}

	foreach_out_edge(proj, edge) {
		ir_node *user = get_edge_src_irn(edge);

		if (is_Cmp(user)) {
			bool dump;
			if (!cmp_can_use_sub_flags(user, sub, &dump)) {
				return false;
			}
		}
	}
	return true;
}

/**
 * return true if the node is a Proj(Load) and could be used in source address
 * mode for another node. Will return only true if the @p other node is not
 * dependent on the memory of the Load (for binary operations use the other
 * input here, for unary operations use NULL).
 */
static bool ia32_use_source_address_mode(ir_node *block, ir_node *node,
                                         ir_node *other, ir_node *other2,
                                         match_flags_t flags)
{
	/* float constants are always available */
	if (is_Const(node)) {
		ir_mode *mode = get_irn_mode(node);
		if (mode_is_float(mode)) {
			ir_tarval *tv = get_Const_tarval(node);
			if (!tarval_ieee754_can_conv_lossless(tv, ia32_mode_float64))
				return false;
			if (ia32_cg_config.use_sse2) {
				if (is_simple_sse_Const(node))
					return false;
			} else {
				if (is_simple_x87_Const(node))
					return false;
			}
			if (get_irn_n_edges(node) > 1)
				return false;
			return true;
		}
		return false;
	}

	if (!is_Proj(node))
		return false;
	ir_node *load = get_Proj_pred(node);
	if (!is_Load(load))
		return false;
	assert(get_Proj_num(node) == pn_Load_res);
	if (get_nodes_block(load) != block)
		return false;
	ir_mode *mode = get_irn_mode(node);
	/* we can't fold mode_E AM */
	if (mode == x86_mode_E)
		return false;
	/* we only use address mode if we're the only user of the load
	 * or the users will be merged later anyway */
	if (get_irn_n_edges(node) != (flags & match_two_users ? 2 : 1) &&
	    !users_will_merge(node))
		return false;
	/* in some edge cases with address mode we might reach the load normally
	 * and through some AM sequence, if it is already materialized then we
	 * can't create an AM node from it */
	if (be_is_transformed(node))
		return false;

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

	if (other2 != NULL && prevents_AM(block, load, other2))
		return false;

	return true;
}

typedef struct ia32_address_mode_t ia32_address_mode_t;
struct ia32_address_mode_t {
	x86_address_t   addr;
	ir_node        *mem_proj;
	x86_insn_size_t size;
	ia32_op_type_t  op_type;
	ir_node        *new_op1;
	ir_node        *new_op2;
	bool            pinned       : 1;
	unsigned        commutative  : 1;
	unsigned        ins_permuted : 1;
};

static void ia32_create_address_mode(x86_address_t *addr, ir_node *ptr,
                                     x86_create_am_flags_t flags)
{
	x86_create_address_mode(addr, ptr, flags);
	adjust_relocation(&addr->imm);
}

static void build_address_ptr(x86_address_t *addr, ir_node *ptr, ir_node *mem)
{
	/* construct load address */
	memset(addr, 0, sizeof(addr[0]));
	ia32_create_address_mode(addr, ptr, x86_create_am_normal);

	addr->variant = addr->base ? (addr->index ? X86_ADDR_BASE_INDEX
	                                          : X86_ADDR_BASE)
	                           : (addr->index ? X86_ADDR_INDEX
	                                          : X86_ADDR_JUST_IMM);
	addr->base    = addr->base  ? be_transform_node(addr->base)  : noreg_GP;
	addr->index   = addr->index ? be_transform_node(addr->index) : noreg_GP;
	addr->mem     = be_transform_node(mem);
}

static void build_address(ia32_address_mode_t *am, ir_node *node,
                          x86_create_am_flags_t flags)
{
	x86_address_t *addr = &am->addr;

	/* floating point immediates */
	if (is_Const(node)) {
		ir_graph  *const irg    = get_irn_irg(node);
		ir_tarval *const tv     = get_Const_tarval(node);
		ir_entity *const entity = create_float_const_entity(tv, NULL);
		addr->base        = get_global_base(irg);
		addr->index       = noreg_GP;
		addr->mem         = nomem;
		addr->imm         = (x86_imm32_t) {
			.kind   = lconst_imm_kind,
			.entity = entity,
		};
		addr->variant     = lconst_variant,
		adjust_relocation(&addr->imm);
		addr->tls_segment = false;
		am->size          = x86_size_from_mode(get_type_mode(get_entity_type(entity)));
		am->pinned        = false;
		return;
	}

	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);
	am->pinned       = get_irn_pinned(load);
	am->size         = x86_size_from_mode(get_Load_mode(load));
	am->mem_proj     = get_Proj_for_pn(load, pn_Load_M);

	/* construct load address */
	ia32_create_address_mode(addr, ptr, flags);

	addr->variant = addr->base ? (addr->index ? X86_ADDR_BASE_INDEX
	                                          : X86_ADDR_BASE)
	                           : (addr->index ? X86_ADDR_INDEX
	                                          : X86_ADDR_JUST_IMM);
	addr->base    = addr->base  ? be_transform_node(addr->base)  : noreg_GP;
	addr->index   = addr->index ? be_transform_node(addr->index) : noreg_GP;
	addr->mem     = new_mem;
}

static void set_address(ir_node *node, const x86_address_t *addr)
{
	ia32_attr_t *const attr = get_ia32_attr(node);
	attr->addr.immediate = addr->imm;
	attr->addr.log_scale = addr->scale;
	attr->addr.variant   = addr->variant;
	if (addr->tls_segment)
		attr->addr.segment = X86_SEGMENT_GS;
	if (addr->imm.kind == X86_IMM_FRAMEENT)
		set_ia32_frame_use(node, IA32_FRAME_USE_AUTO);
}

/**
 * Apply attributes of a given address mode to a node.
 */
static void set_am_attributes(ir_node *node, const ia32_address_mode_t *am)
{
	set_address(node, &am->addr);

	set_ia32_op_type(node, am->op_type);
	if (am->pinned && !get_irn_pinned(node))
		set_irn_pinned(node, true);
	if (am->commutative)
		set_ia32_commutative(node);
}

static bool is_float_downconv(const ir_node *node)
{
	if (!is_Conv(node))
		return false;
	ir_node *pred      = get_Conv_op(node);
	ir_mode *pred_mode = get_irn_mode(pred);
	ir_mode *mode      = get_irn_mode(node);
	return mode_is_float(pred_mode)
	    && get_mode_size_bits(mode) <= get_mode_size_bits(pred_mode);
}

static ir_node *ia32_skip_float_downconv(ir_node *node)
{
	while (is_float_downconv(node)) {
		node = get_Conv_op(node);