arm_transform.c

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

/**
 * @file
 * @brief   The codegenerator (transform FIRM into arm FIRM)
 * @author  Matthias Braun, Oliver Richter, Tobias Gneist, Michael Beck
 */
#include "bearch_arm_t.h"
#include "irnode_t.h"
#include "irgraph_t.h"
#include "irmode_t.h"
#include "irgmod.h"
#include "iredges.h"
#include "ircons.h"
#include "dbginfo.h"
#include "iropt_t.h"
#include "debug.h"
#include "panic.h"
#include "util.h"

#include "benode.h"
#include "beirg.h"
#include "beutil.h"
#include "betranshlp.h"

#include "arm_nodes_attr.h"
#include "arm_transform.h"
#include "arm_optimize.h"
#include "arm_new_nodes.h"
#include "arm_cconv.h"

#include "gen_arm_regalloc_if.h"
#include "gen_arm_new_nodes.h"

#define ARM_PO2_STACK_ALIGNMENT 3

DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)

static const arch_register_t *sp_reg = &arm_registers[REG_SP];
static be_stackorder_t       *stackorder;
static calling_convention_t  *cconv = NULL;
static pmap                  *node_to_stack;

static const arch_register_t *const callee_saves[] = {
	&arm_registers[REG_R4],
	&arm_registers[REG_R5],
	&arm_registers[REG_R6],
	&arm_registers[REG_R7],
	&arm_registers[REG_R8],
	&arm_registers[REG_R9],
	&arm_registers[REG_R10],
	&arm_registers[REG_R11],
	&arm_registers[REG_LR],
};

static const arch_register_t *const caller_saves[] = {
	&arm_registers[REG_R0],
	&arm_registers[REG_R1],
	&arm_registers[REG_R2],
	&arm_registers[REG_R3],
	&arm_registers[REG_LR],

	&arm_registers[REG_F0],
	&arm_registers[REG_F1],
	&arm_registers[REG_F2],
	&arm_registers[REG_F3],
	&arm_registers[REG_F4],
	&arm_registers[REG_F5],
	&arm_registers[REG_F6],
	&arm_registers[REG_F7],
};

void arm_gen_vals_from_word(uint32_t value, arm_vals *result)
{
	/* TODO: not optimal yet, as we only "shift" the value and don't take
	 * advantage of rotations */

	/* special case: we prefer shift amount 0 */
	if (value <= 0xFF) {
		result->values[0] = value;
		result->rors[0]   = 0;
		result->ops       = 1;
		return;
	}

	int initial = 0;
	result->ops = 0;
	do {
		while ((value & 0x3) == 0) {
			value  >>= 2;
			initial += 2;
		}

		result->values[result->ops] = value & 0xFF;
		result->rors[result->ops]   = (32-initial) % 32;
		++result->ops;

		value  >>= 8;
		initial += 8;
	} while (value != 0);
}

/**
 * create firm graph for a constant
 */
static ir_node *create_const_graph_value(dbg_info *dbgi, ir_node *block,
                                         uint32_t value)
{
	/* We only have 8 bit immediates. So we possibly have to combine several
	 * operations to construct the desired value.
	 *
	 * we can either create the value by adding bits to 0 or by removing bits
	 * from an register with all bits set. Try which alternative needs fewer
	 * operations */
	arm_vals v;
	arm_gen_vals_from_word(value, &v);
	arm_vals vn;
	arm_gen_vals_from_word(~value, &vn);

	ir_node *result;
	if (vn.ops < v.ops) {
		/* remove bits */
		result = new_bd_arm_Mvn_imm(dbgi, block, vn.values[0], vn.rors[0]);

		for (unsigned cnt = 1; cnt < vn.ops; ++cnt) {
			result = new_bd_arm_Bic_imm(dbgi, block, result,
			                            vn.values[cnt], vn.rors[cnt]);
		}
	} else {
		/* add bits */
		result = new_bd_arm_Mov_imm(dbgi, block, v.values[0], v.rors[0]);

		for (unsigned cnt = 1; cnt < v.ops; ++cnt) {
			result = new_bd_arm_Or_imm(dbgi, block, result,
			                           v.values[cnt], v.rors[cnt]);
		}
	}
	return result;
}

/**
 * Create a DAG constructing a given Const.
 *
 * @param irn  a Firm const
 */
static ir_node *create_const_graph(ir_node *irn, ir_node *block)
{
	ir_tarval *tv   = get_Const_tarval(irn);
	ir_mode   *mode = get_tarval_mode(tv);
	if (mode_is_reference(mode)) {
		/* ARM is 32bit, so we can safely convert a reference tarval into Iu */
		assert(get_mode_size_bits(mode) == get_mode_size_bits(arm_mode_gp));
		tv = tarval_convert_to(tv, arm_mode_gp);
	}
	long value = get_tarval_long(tv);
	return create_const_graph_value(get_irn_dbg_info(irn), block, value);
}

/**
 * Create an And that will zero out upper bits.
 *
 * @param dbgi     debug info
 * @param block    the basic block
 * @param op       the original node
 * param src_bits  number of lower bits that will remain
 */
static ir_node *gen_zero_extension(dbg_info *dbgi, ir_node *block, ir_node *op,
                                   unsigned src_bits)
{
	if (src_bits == 8) {
		return new_bd_arm_And_imm(dbgi, block, op, 0xFF, 0);
	} else if (src_bits == 16) {
		ir_node *lshift = new_bd_arm_Mov_reg_shift_imm(dbgi, block, op, ARM_SHF_LSL_IMM, 16);
		ir_node *rshift = new_bd_arm_Mov_reg_shift_imm(dbgi, block, lshift, ARM_SHF_LSR_IMM, 16);
		return rshift;
	} else {
		panic("zero extension only supported for 8 and 16 bits");
	}
}

/**
 * Generate code for a sign extension.
 */
static ir_node *gen_sign_extension(dbg_info *dbgi, ir_node *block, ir_node *op,
                                   unsigned src_bits)
{
	unsigned shift_width = 32 - src_bits;
	ir_node *lshift_node = new_bd_arm_Mov_reg_shift_imm(dbgi, block, op, ARM_SHF_LSL_IMM, shift_width);
	ir_node *rshift_node = new_bd_arm_Mov_reg_shift_imm(dbgi, block, lshift_node, ARM_SHF_ASR_IMM, shift_width);
	return rshift_node;
}

static ir_node *gen_extension(dbg_info *dbgi, ir_node *block, ir_node *op,
                              ir_mode *orig_mode)
{
	unsigned bits = get_mode_size_bits(orig_mode);
	if (bits == 32)
		return op;

	if (mode_is_signed(orig_mode)) {
		return gen_sign_extension(dbgi, block, op, bits);
	} else {
		return gen_zero_extension(dbgi, block, op, bits);
	}
}

/**
 * returns true if it is assured, that the upper bits of a node are "clean"
 * which means for a 16 or 8 bit value, that the upper bits in the register
 * are 0 for unsigned and a copy of the last significant bit for signed
 * numbers.
 */
static bool upper_bits_clean(ir_node *transformed_node, ir_mode *mode)
{
	(void)transformed_node;
	(void)mode;
	/* TODO */
	return false;
}

/**
 * Transforms a Conv node.
 *
 * @return The created ia32 Conv node
 */
static ir_node *gen_Conv(ir_node *node)
{
	ir_node  *block    = be_transform_nodes_block(node);
	ir_node  *op       = get_Conv_op(node);
	ir_node  *new_op   = be_transform_node(op);
	ir_mode  *src_mode = get_irn_mode(op);
	ir_mode  *dst_mode = get_irn_mode(node);
	dbg_info *dbg      = get_irn_dbg_info(node);

	if (src_mode == dst_mode)
		return new_op;

	if (mode_is_float(src_mode) || mode_is_float(dst_mode)) {
		if (arm_cg_config.fpu == ARM_FPU_FPA) {
			if (mode_is_float(src_mode)) {
				if (mode_is_float(dst_mode)) {
					/* from float to float */
					return new_bd_arm_Mvf(dbg, block, new_op, dst_mode);
				} else {
					/* from float to int */
					panic("TODO");
				}
			} else {
				/* from int to float */
				if (!mode_is_signed(src_mode)) {
					panic("TODO");
				} else {
					return new_bd_arm_FltX(dbg, block, new_op, dst_mode);
				}
			}
		} else {
			panic("softfloat not lowered");
		}
	} else { /* complete in gp registers */
		unsigned src_bits = get_mode_size_bits(src_mode);
		unsigned dst_bits = get_mode_size_bits(dst_mode);
		if (src_bits == dst_bits) {
			/* kill unnecessary conv */
			return new_op;
		}

		unsigned min_bits;
		ir_mode *min_mode;
		if (src_bits < dst_bits) {
			min_bits = src_bits;
			min_mode = src_mode;
		} else {
			min_bits = dst_bits;
			min_mode = dst_mode;
		}

		if (upper_bits_clean(new_op, min_mode)) {
			return new_op;
		}

		if (mode_is_signed(min_mode)) {
			return gen_sign_extension(dbg, block, new_op, min_bits);
		} else {
			return gen_zero_extension(dbg, block, new_op, min_bits);
		}
	}
}

typedef struct {
	uint8_t imm_8;
	uint8_t rot;
} arm_immediate_t;

static bool try_encode_val_as_immediate(uint32_t val, arm_immediate_t *const res)
{
	if (val <= 0xff) {
		res->imm_8 = val;
		res->rot   = 0;
		return true;
	}
	/* arm allows to use to rotate an 8bit immediate value by a multiple of 2
	   (= 0, 2, 4, 6, ...).
	   So we determine the smallest even position with a bit set
	   and the highest even position with no bit set anymore.
	   If the difference between these 2 is <= 8, then we can encode the value
	   as immediate.
	 */
	unsigned low_pos  = ntz(val) & ~1u;
	unsigned high_pos = (32-nlz(val)+1) & ~1u;

	if (high_pos - low_pos <= 8) {
		res->imm_8 = val >> low_pos;
		res->rot   = 32 - low_pos;
		return true;
	}

	if (high_pos > 24) {
		res->rot = 34 - high_pos;
		val      = val >> (32-res->rot) | val << (res->rot);
		if (val <= 0xff) {
			res->imm_8 = val;
			return true;
		}
	}

	return false;
}

typedef enum imm_match_t {
	IMM_NONE = 0,
	IMM_POS  = 1 << 0,
	IMM_NOT  = 1 << 1,
	IMM_NEG  = 1 << 2,
} imm_match_t;

static imm_match_t try_encode_as_immediate(ir_node const *const node, arm_immediate_t *const res, imm_match_t const match)
{
	if (!is_Const(node))
		return IMM_NONE;
	uint32_t const val = get_Const_long(node);
	return
		match & IMM_POS && try_encode_val_as_immediate( val, res) ? IMM_POS :
		match & IMM_NOT && try_encode_val_as_immediate(~val, res) ? IMM_NOT :
		match & IMM_NEG && try_encode_val_as_immediate(-val, res) ? IMM_NEG :
		IMM_NONE;
}

typedef enum {
	MATCH_NONE         = 0,
	MATCH_COMMUTATIVE  = 1 << 0,  /**< commutative node */
	MATCH_REVERSE      = 1 << 1,  /**< support reverse opcode */
	MATCH_SIZE_NEUTRAL = 1 << 2,
} match_flags_t;
ENUM_BITSET(match_flags_t)

/**
 * possible binop constructors.
 */
typedef struct arm_binop_factory_t {
	/** normal reg op reg operation. */
	ir_node *(*new_binop_reg)(dbg_info *dbgi, ir_node *block, ir_node *op1, ir_node *op2);
	/** normal reg op imm operation. */
	ir_node *(*new_binop_imm)(dbg_info *dbgi, ir_node *block, ir_node *op1, unsigned char imm8, unsigned char imm_rot);
	/** barrel shifter reg op (reg shift reg operation. */
	ir_node *(*new_binop_reg_shift_reg)(dbg_info *dbgi, ir_node *block, ir_node *left, ir_node *right, ir_node *shift, arm_shift_modifier_t shift_modifier);
	/** barrel shifter reg op (reg shift imm operation. */
	ir_node *(*new_binop_reg_shift_imm)(dbg_info *dbgi, ir_node *block, ir_node *left, ir_node *right, arm_shift_modifier_t shift_modifier, unsigned shift_immediate);
} arm_binop_factory_t;

static ir_node *gen_int_binop_ops(ir_node *node, ir_node *op1, ir_node *op2,
                                  match_flags_t flags,
                                  const arm_binop_factory_t *factory)
{
	ir_node  *block = be_transform_nodes_block(node);
	dbg_info *dbgi  = get_irn_dbg_info(node);

	if (flags & MATCH_SIZE_NEUTRAL) {
		op1 = be_skip_downconv(op1, true);
		op2 = be_skip_downconv(op2, true);
	} else {
		assert(get_mode_size_bits(get_irn_mode(node)) == 32);
		op1 = be_skip_sameconv(op1);
		op2 = be_skip_sameconv(op2);
	}

	arm_immediate_t imm;
	if (try_encode_as_immediate(op2, &imm, IMM_POS) != IMM_NONE) {
		ir_node *new_op1 = be_transform_node(op1);
		return factory->new_binop_imm(dbgi, block, new_op1, imm.imm_8, imm.rot);
	}
	ir_node *new_op2 = be_transform_node(op2);
    if ((flags & (MATCH_COMMUTATIVE|MATCH_REVERSE)) && try_encode_as_immediate(op1, &imm, IMM_POS) != IMM_NONE) {
		if (flags & MATCH_REVERSE)
			return factory[1].new_binop_imm(dbgi, block, new_op2, imm.imm_8, imm.rot);
		else
			return factory[0].new_binop_imm(dbgi, block, new_op2, imm.imm_8, imm.rot);
	}
	ir_node *new_op1 = be_transform_node(op1);

	/* check if we can fold in a Mov */
	if (is_arm_Mov(new_op2)) {
		const arm_shifter_operand_t *attr = get_arm_shifter_operand_attr_const(new_op2);

		switch (attr->shift_modifier) {
		case ARM_SHF_IMM:
		case ARM_SHF_ASR_IMM:
		case ARM_SHF_LSL_IMM:
		case ARM_SHF_LSR_IMM:
		case ARM_SHF_ROR_IMM:
			if (factory->new_binop_reg_shift_imm) {
				ir_node *mov_op = get_irn_n(new_op2, n_arm_Mov_Rm);
				return factory->new_binop_reg_shift_imm(dbgi, block, new_op1, mov_op,
					attr->shift_modifier, attr->shift_immediate);
			}
			break;

		case ARM_SHF_ASR_REG:
		case ARM_SHF_LSL_REG:
		case ARM_SHF_LSR_REG:
		case ARM_SHF_ROR_REG:
			if (factory->new_binop_reg_shift_reg) {
				ir_node *mov_op  = get_irn_n(new_op2, n_arm_Mov_Rm);
				ir_node *mov_sft = get_irn_n(new_op2, n_arm_Mov_Rs);
				return factory->new_binop_reg_shift_reg(dbgi, block, new_op1, mov_op, mov_sft,
					attr->shift_modifier);
			}
			break;
		case ARM_SHF_REG:
		case ARM_SHF_RRX:
			break;
		case ARM_SHF_INVALID:
			panic("invalid shift");
		}
	}
	if ((flags & (MATCH_COMMUTATIVE|MATCH_REVERSE)) && is_arm_Mov(new_op1)) {
		const arm_shifter_operand_t *attr = get_arm_shifter_operand_attr_const(new_op1);
		int idx = flags & MATCH_REVERSE ? 1 : 0;

		switch (attr->shift_modifier) {
		case ARM_SHF_IMM:
		case ARM_SHF_ASR_IMM:
		case ARM_SHF_LSL_IMM:
		case ARM_SHF_LSR_IMM:
		case ARM_SHF_ROR_IMM:
			if (factory[idx].new_binop_reg_shift_imm) {
				ir_node *mov_op = get_irn_n(new_op1, n_arm_Mov_Rm);
				return factory[idx].new_binop_reg_shift_imm(dbgi, block, new_op2, mov_op,
					attr->shift_modifier, attr->shift_immediate);
			}
			break;

		case ARM_SHF_ASR_REG:
		case ARM_SHF_LSL_REG:
		case ARM_SHF_LSR_REG:
		case ARM_SHF_ROR_REG:
			if (factory[idx].new_binop_reg_shift_reg) {
				ir_node *mov_op  = get_irn_n(new_op1, n_arm_Mov_Rm);
				ir_node *mov_sft = get_irn_n(new_op1, n_arm_Mov_Rs);
				return factory[idx].new_binop_reg_shift_reg(dbgi, block, new_op2, mov_op, mov_sft,
					attr->shift_modifier);
			}
			break;

		case ARM_SHF_REG:
		case ARM_SHF_RRX:
			break;
		case ARM_SHF_INVALID:
			panic("invalid shift");
		}
	}
	return factory->new_binop_reg(dbgi, block, new_op1, new_op2);
}

static ir_node *gen_int_binop(ir_node *node, match_flags_t flags,
                              const arm_binop_factory_t *factory)
{
	ir_node *op1 = get_binop_left(node);
	ir_node *op2 = get_binop_right(node);
	return gen_int_binop_ops(node, op1, op2, flags, factory);
}

static ir_node *gen_Ror(ir_node *node, ir_node *op1, ir_node *op2,
                        bool negate_op)
{
	dbg_info *dbgi    = get_irn_dbg_info(node);
	ir_node  *block   = be_transform_nodes_block(node);
	ir_node  *new_op1 = be_transform_node(op1);
	if (is_Const(op2)) {
		ir_tarval *tv   = get_Const_tarval(op2);
		ir_mode   *mode = get_irn_mode(node);
		long       bits = get_mode_size_bits(mode);
		if (tarval_is_long(tv) && bits == 32) {
			long val = get_tarval_long(tv);
			val = (negate_op ? bits - val : val) & 31;
			return new_bd_arm_Mov_reg_shift_imm(dbgi, block, new_op1, ARM_SHF_ROR_IMM, val);
		}
	}

	ir_node *new_op2 = be_transform_node(op2);
	if (negate_op) {
		new_op2 = new_bd_arm_Rsb_imm(dbgi, block, new_op2, 32, 0);
	}
	return new_bd_arm_Mov_reg_shift_reg(dbgi, block, new_op1, new_op2,
											ARM_SHF_ROR_REG);
}

static bool is_low_mask(ir_tarval *tv)
{
	return get_tarval_popcount(tv) == 16 && get_tarval_highest_bit(tv) == 15;
}

static bool is_high_mask(ir_tarval *tv)
{
	return get_tarval_popcount(tv) == 16 && get_tarval_lowest_bit(tv) == 16;
}

static ir_node *match_pkh(ir_node *node)
{
	assert(is_Or(node) || is_Add(node));
	ir_node *left  = get_binop_left(node);
	ir_node *right = get_binop_right(node);
	if (!is_And(left) || !is_And(right))
		return NULL;
	ir_node *left_right  = get_And_right(left);
	ir_node *right_right = get_And_right(right);
	if (!is_Const(left_right) || !is_Const(right_right))
		return NULL;
	/* we want the low-mask on the right side */
	if (is_high_mask(get_Const_tarval(left_right))) {
		ir_node *tmp = left;
		left       = right;
		right      = tmp;
		left_right = right_right;
	} else if (!is_high_mask(get_Const_tarval(right_right))) {
		return NULL;
	}
	if (!is_low_mask(get_Const_tarval(left_right)))
		return NULL;
	ir_node *left_left  = get_And_left(left);
	ir_node *right_left = get_And_left(right);
	static const arm_binop_factory_t pkhbt_pkhtb_factory[2] = {
		{
			new_bd_arm_Pkhbt_reg,
			new_bd_arm_Pkhbt_imm,
			new_bd_arm_Pkhbt_reg_shift_reg,
			new_bd_arm_Pkhbt_reg_shift_imm
		},
		{
			new_bd_arm_Pkhtb_reg,
			new_bd_arm_Pkhtb_imm,
			new_bd_arm_Pkhtb_reg_shift_reg,
			new_bd_arm_Pkhtb_reg_shift_imm
		}
	};
	return gen_int_binop_ops(node, left_left, right_left, MATCH_REVERSE,
	                         pkhbt_pkhtb_factory);
}

/**
 * Creates an ARM Add.
 *
 * @return the created arm Add node
 */
static ir_node *gen_Add(ir_node *node)
{
	ir_node *rotl_left;
	ir_node *rotl_right;
	if (be_pattern_is_rotl(node, &rotl_left, &rotl_right)) {
		if (is_Minus(rotl_right))
			return gen_Ror(node, rotl_left, get_Minus_op(rotl_right), false);
		return gen_Ror(node, rotl_left, rotl_right, true);
	}
	ir_node *pkh = match_pkh(node);
	if (pkh != NULL)
		return pkh;

	ir_mode *mode = get_irn_mode(node);
	if (mode_is_float(mode)) {
		ir_node  *block   = be_transform_nodes_block(node);
		ir_node  *op1     = get_Add_left(node);
		ir_node  *op2     = get_Add_right(node);
		dbg_info *dbgi    = get_irn_dbg_info(node);
		ir_node  *new_op1 = be_transform_node(op1);
		ir_node  *new_op2 = be_transform_node(op2);
		if (arm_cg_config.fpu == ARM_FPU_FPA) {
			return new_bd_arm_Adf(dbgi, block, new_op1, new_op2, mode);
		} else {
			panic("softfloat not lowered");
		}
	} else {
		ir_node *left  = get_Add_left(node);
		ir_node *right = get_Add_right(node);
		ir_node *mul_left;
		ir_node *mul_right;
		ir_node *other;
		if (is_Mul(left)) {
			mul_left  = get_Mul_left(left);
			mul_right = get_Mul_right(left);
			other     = right;
			goto create_mla;
		} else if (is_Mul(right)) {
			mul_left  = get_Mul_left(right);
			mul_right = get_Mul_right(right);
			other     = left;
create_mla:;
			dbg_info *dbgi      = get_irn_dbg_info(node);
			ir_node  *block     = be_transform_nodes_block(node);
			ir_node  *new_left  = be_transform_node(mul_left);
			ir_node  *new_right = be_transform_node(mul_right);
			ir_node  *new_add   = be_transform_node(other);
			if (arm_cg_config.variant < ARM_VARIANT_6)
				return new_bd_arm_Mla_v5(dbgi, block, new_left, new_right, new_add);
			else
				return new_bd_arm_Mla(dbgi, block, new_left, new_right,
				                      new_add);
		}

		arm_immediate_t imm;
		if (try_encode_as_immediate(right, &imm, IMM_NEG) != IMM_NONE) {
			dbg_info *const dbgi     = get_irn_dbg_info(node);
			ir_node  *const block    = be_transform_nodes_block(node);
			ir_node  *const new_left = be_transform_node(left);
			return new_bd_arm_Sub_imm(dbgi, block, new_left, imm.imm_8, imm.rot);
		}

		static const arm_binop_factory_t add_factory = {
			new_bd_arm_Add_reg,
			new_bd_arm_Add_imm,
			new_bd_arm_Add_reg_shift_reg,
			new_bd_arm_Add_reg_shift_imm
		};
		return gen_int_binop_ops(node, left, right,
		                         MATCH_COMMUTATIVE | MATCH_SIZE_NEUTRAL,
		                         &add_factory);
	}
}

static ir_node *gen_arm_AddS_t(ir_node *node)
{
	static const arm_binop_factory_t adds_factory = {
		new_bd_arm_AddS_reg,
		new_bd_arm_AddS_imm,
		new_bd_arm_AddS_reg_shift_reg,
		new_bd_arm_AddS_reg_shift_imm,
	};
	ir_node *left  = get_irn_n(node, n_arm_AddS_t_left);
	ir_node *right = get_irn_n(node, n_arm_AddS_t_right);
	ir_node *res   = gen_int_binop_ops(node, left, right,
	                                   MATCH_COMMUTATIVE | MATCH_SIZE_NEUTRAL,
	                                   &adds_factory);
	arch_set_irn_register_out(res, pn_arm_AddS_flags, &arm_registers[REG_FL]);
	return res;
}

static ir_node *gen_Proj_arm_AddS_t(ir_node *node)
{
	unsigned pn       = get_Proj_num(node);
	ir_node *pred     = get_Proj_pred(node);
	ir_node *new_pred = be_transform_node(pred);
	switch ((pn_arm_AddS_t)pn) {
	case pn_arm_AddS_t_res:
		return be_new_Proj(new_pred, pn_arm_AddS_res);
	case pn_arm_AddS_t_flags:
		return be_new_Proj(new_pred, pn_arm_AddS_flags);
	}
	panic("%+F: Invalid proj number", node);
}

static ir_node *gen_arm_AdC_t(ir_node *node)
{
	ir_node *left  = get_irn_n(node, n_arm_AdC_t_left);
	ir_node *right = get_irn_n(node, n_arm_AdC_t_right);
	ir_node *flags = get_irn_n(node, n_arm_AdC_t_flags);
	/* TODO: handle complete set of shifter operands */
	ir_node *new_left  = be_transform_node(left);
	ir_node *new_right = be_transform_node(right);
	ir_node *new_flags = be_transform_node(flags);

	dbg_info *dbgi      = get_irn_dbg_info(node);
	ir_node  *new_block = be_transform_nodes_block(node);
	ir_node  *res       = new_bd_arm_AdC_reg(dbgi, new_block, new_left,
	                                         new_right, new_flags);
	return res;
}

/**
 * Creates an ARM Mul.
 *
 * @return the created arm Mul node
 */
static ir_node *gen_Mul(ir_node *node)
{
	ir_node  *block   = be_transform_nodes_block(node);
	ir_node  *op1     = get_Mul_left(node);
	ir_node  *new_op1 = be_transform_node(op1);
	ir_node  *op2     = get_Mul_right(node);
	ir_node  *new_op2 = be_transform_node(op2);
	ir_mode  *mode    = get_irn_mode(node);
	dbg_info *dbg     = get_irn_dbg_info(node);

	if (mode_is_float(mode)) {
		if (arm_cg_config.fpu == ARM_FPU_FPA) {
			return new_bd_arm_Muf(dbg, block, new_op1, new_op2, mode);
		} else {
			panic("softfloat not lowered");
		}
	}
	assert(mode_is_data(mode));
	if (arm_cg_config.variant < ARM_VARIANT_6) {
		return new_bd_arm_Mul_v5(dbg, block, new_op1, new_op2);
	} else {
		return new_bd_arm_Mul(dbg, block, new_op1, new_op2);
	}
}

static ir_node *gen_arm_UMulL_t(ir_node *node)
{
	ir_node  *block     = be_transform_nodes_block(node);
	ir_node  *left      = get_irn_n(node, n_arm_UMulL_t_left);
	ir_node  *new_left  = be_transform_node(left);
	ir_node  *right     = get_irn_n(node, n_arm_UMulL_t_right);
	ir_node  *new_right = be_transform_node(right);
	dbg_info *dbgi      = get_irn_dbg_info(node);
	return new_bd_arm_UMulL(dbgi, block, new_left, new_right);
}

static ir_node *gen_Proj_arm_UMulL_t(ir_node *node)
{
	unsigned pn       = get_Proj_num(node);
	ir_node *pred     = get_Proj_pred(node);
	ir_node *new_pred = be_transform_node(pred);
	switch ((pn_arm_UMulL_t)pn) {
	case pn_arm_UMulL_t_low:
		return be_new_Proj(new_pred, pn_arm_UMulL_low);
	case pn_arm_UMulL_t_high:
		return be_new_Proj(new_pred, pn_arm_UMulL_high);
	}
	panic("%+F: Invalid proj number", node);
}

static ir_node *gen_Div(ir_node *node)
{
	ir_node  *block   = be_transform_nodes_block(node);
	ir_node  *op1     = get_Div_left(node);
	ir_node  *new_op1 = be_transform_node(op1);
	ir_node  *op2     = get_Div_right(node);
	ir_node  *new_op2 = be_transform_node(op2);
	ir_mode  *mode    = get_Div_resmode(node);
	dbg_info *dbg     = get_irn_dbg_info(node);

	/* integer division should be replaced by builtin call */
	assert(mode_is_float(mode));

	if (arm_cg_config.fpu == ARM_FPU_FPA) {
		return new_bd_arm_Dvf(dbg, block, new_op1, new_op2, mode);
	} else {
		panic("softfloat not lowered");
	}
}

static ir_node *gen_And(ir_node *node)
{
	static const arm_binop_factory_t and_factory = {
		new_bd_arm_And_reg,
		new_bd_arm_And_imm,
		new_bd_arm_And_reg_shift_reg,
		new_bd_arm_And_reg_shift_imm
	};
	static const arm_binop_factory_t bic_factory = {
		new_bd_arm_Bic_reg,
		new_bd_arm_Bic_imm,
		new_bd_arm_Bic_reg_shift_reg,
		new_bd_arm_Bic_reg_shift_imm
	};

	/* check for and not */
	arm_immediate_t imm;
	ir_node *left  = get_And_left(node);
	ir_node *right = get_And_right(node);
	if (is_Not(right)) {
		ir_node *right_not = get_Not_op(right);
		return gen_int_binop_ops(node, left, right_not, MATCH_SIZE_NEUTRAL,
		                         &bic_factory);
	} else if (is_Not(left)) {
		ir_node *left_not = get_Not_op(left);
		return gen_int_binop_ops(node, right, left_not, MATCH_SIZE_NEUTRAL,
		                         &bic_factory);
	} else if (try_encode_as_immediate(right, &imm, IMM_NOT) != IMM_NONE) {
		dbg_info *const dbgi  = get_irn_dbg_info(node);
		ir_node  *const block = be_transform_nodes_block(node);
		ir_node  *const new_l = be_transform_node(left);
		return new_bd_arm_Bic_imm(dbgi, block, new_l, imm.imm_8, imm.rot);
	} else {
		return gen_int_binop(node, MATCH_COMMUTATIVE|MATCH_SIZE_NEUTRAL,
		                     &and_factory);
	}
}

static ir_node *gen_Or(ir_node *node)
{
	ir_node *rotl_left;
	ir_node *rotl_right;
	if (be_pattern_is_rotl(node, &rotl_left, &rotl_right)) {
		if (is_Minus(rotl_right))
			return gen_Ror(node, rotl_left, get_Minus_op(rotl_right), false);
		return gen_Ror(node, rotl_left, rotl_right, true);
	}
	ir_node *pkh = match_pkh(node);
	if (pkh != NULL)
		return pkh;

	static const arm_binop_factory_t or_factory = {
		new_bd_arm_Or_reg,
		new_bd_arm_Or_imm,
		new_bd_arm_Or_reg_shift_reg,
		new_bd_arm_Or_reg_shift_imm
	};
	return gen_int_binop(node, MATCH_COMMUTATIVE | MATCH_SIZE_NEUTRAL, &or_factory);
}

static ir_node *gen_arm_OrPl_t(ir_node *node)
{
	ir_node *left     = get_irn_n(node, n_arm_OrPl_t_left);
	ir_node *right    = get_irn_n(node, n_arm_OrPl_t_right);
	ir_node *falseval = get_irn_n(node, n_arm_OrPl_t_falseval);
	ir_node *flags    = get_irn_n(node, n_arm_OrPl_t_flags);
	/* TODO: handle complete set of shifter operands */
	ir_node *new_left     = be_transform_node(left);
	ir_node *new_right    = be_transform_node(right);
	ir_node *new_falseval = be_transform_node(falseval);
	ir_node *new_flags    = be_transform_node(flags);

	dbg_info *dbgi      = get_irn_dbg_info(node);
	ir_node  *new_block = be_transform_nodes_block(node);
	ir_node  *res       = new_bd_arm_OrPl(dbgi, new_block, new_left, new_right,
	                                      new_falseval, new_flags);
	return res;
}

static ir_node *gen_Eor(ir_node *node)
{
	static const arm_binop_factory_t eor_factory = {
		new_bd_arm_Eor_reg,
		new_bd_arm_Eor_imm,
		new_bd_arm_Eor_reg_shift_reg,
		new_bd_arm_Eor_reg_shift_imm
	};
	return gen_int_binop(node, MATCH_COMMUTATIVE | MATCH_SIZE_NEUTRAL,
	                     &eor_factory);
}

static ir_node *gen_Sub(ir_node *node)
{
	ir_mode *mode  = get_irn_mode(node);
	ir_node *left  = get_Sub_left(node);
	ir_node *right = get_Sub_right(node);
	if (mode_is_float(mode)) {
		ir_node  *block     = be_transform_nodes_block(node);
		ir_node  *new_left  = be_transform_node(left);
		ir_node  *new_right = be_transform_node(right);
		dbg_info *dbgi      = get_irn_dbg_info(node);

		if (arm_cg_config.fpu == ARM_FPU_FPA) {
			return new_bd_arm_Suf(dbgi, block, new_left, new_right, mode);
		} else {
			panic("softfloat not lowered");
		}
	} else {
		if (is_Mul(right) && arm_cg_config.variant >= ARM_VARIANT_6T2) {
			dbg_info *dbgi      = get_irn_dbg_info(node);
			ir_node  *block     = be_transform_nodes_block(node);
			ir_node  *mul_left  = get_Mul_left(right);
			ir_node  *mul_right = get_Mul_right(right);
			ir_node  *new_left  = be_transform_node(mul_left);
			ir_node  *new_right = be_transform_node(mul_right);
			ir_node  *new_sub   = be_transform_node(left);
			return new_bd_arm_Mls(dbgi, block, new_left, new_right, new_sub);
		}

		static const arm_binop_factory_t sub_rsb_factory[2] = {
			{
				new_bd_arm_Sub_reg,
				new_bd_arm_Sub_imm,
				new_bd_arm_Sub_reg_shift_reg,
				new_bd_arm_Sub_reg_shift_imm
			},
			{
				new_bd_arm_Rsb_reg,
				new_bd_arm_Rsb_imm,
				new_bd_arm_Rsb_reg_shift_reg,
				new_bd_arm_Rsb_reg_shift_imm
			}
		};
		return gen_int_binop(node, MATCH_SIZE_NEUTRAL | MATCH_REVERSE, sub_rsb_factory);
	}
}

static ir_node *gen_arm_SubS_t(ir_node *node)
{
	static const arm_binop_factory_t subs_factory[2] = {
		{
			new_bd_arm_SubS_reg,
			new_bd_arm_SubS_imm,
			new_bd_arm_SubS_reg_shift_reg,
			new_bd_arm_SubS_reg_shift_imm,
		},
		{
			new_bd_arm_RsbS_reg,
			new_bd_arm_RsbS_imm,
			new_bd_arm_RsbS_reg_shift_reg,
			new_bd_arm_RsbS_reg_shift_imm,
		},
	};
	ir_node *left  = get_irn_n(node, n_arm_SubS_t_left);
	ir_node *right = get_irn_n(node, n_arm_SubS_t_right);
	ir_node *res   = gen_int_binop_ops(node, left, right,
	                                   MATCH_SIZE_NEUTRAL | MATCH_REVERSE,
	                                   subs_factory);
	assert((int)pn_arm_SubS_flags == (int)pn_arm_RsbS_flags);
	arch_set_irn_register_out(res, pn_arm_SubS_flags, &arm_registers[REG_FL]);
	return res;
}

static ir_node *gen_Proj_arm_SubS_t(ir_node *node)
{
	unsigned pn       = get_Proj_num(node);
	ir_node *pred     = get_Proj_pred(node);
	ir_node *new_pred = be_transform_node(pred);
	assert((int)pn_arm_SubS_flags == (int)pn_arm_RsbS_flags);
	assert((int)pn_arm_SubS_res == (int)pn_arm_RsbS_res);
	switch ((pn_arm_SubS_t)pn) {
	case pn_arm_SubS_t_res:
		return be_new_Proj(new_pred, pn_arm_SubS_res);
	case pn_arm_SubS_t_flags:
		return be_new_Proj(new_pred, pn_arm_SubS_flags);
	}
	panic("%+F: Invalid proj number", node);
}

static ir_node *gen_arm_SbC_t(ir_node *node)
{
	ir_node *left  = get_irn_n(node, n_arm_SbC_t_left);
	ir_node *right = get_irn_n(node, n_arm_SbC_t_right);
	ir_node *flags = get_irn_n(node, n_arm_SbC_t_flags);
	/* TODO: handle complete set of shifter operands */
	ir_node *new_left  = be_transform_node(left);
	ir_node *new_right = be_transform_node(right);
	ir_node *new_flags = be_transform_node(flags);

	dbg_info *dbgi      = get_irn_dbg_info(node);
	ir_node  *new_block = be_transform_nodes_block(node);
	ir_node  *res       = new_bd_arm_SbC_reg(dbgi, new_block, new_left,
	                                         new_right, new_flags);
	return res;
}

/**
 * Checks if a given value can be used as an immediate for the given
 * ARM shift mode.
 */
static bool can_use_shift_constant(unsigned int val,
                                   arm_shift_modifier_t modifier)
{
	if (val <= 31)
		return true;
	if (val == 32 && modifier != ARM_SHF_LSL_REG && modifier != ARM_SHF_ROR_REG)
		return true;
	return false;
}

/**
 * generate an ARM shift instruction.
 *
 * @param node            the node
 * @param flags           matching flags
 * @param shift_modifier  initial encoding of the desired shift operation
 */
static ir_node *make_shift(ir_node *node, match_flags_t flags,
		arm_shift_modifier_t shift_modifier)
{
	ir_node  *block = be_transform_nodes_block(node);
	ir_node  *op1   = get_binop_left(node);
	ir_node  *op2   = get_binop_right(node);
	dbg_info *dbgi  = get_irn_dbg_info(node);
	ir_mode  *mode  = get_irn_mode(node);
	if (get_mode_modulo_shift(mode) != 256)
		panic("modulo shift!=256 not supported");

	if (flags & MATCH_SIZE_NEUTRAL) {
		op1 = be_skip_downconv(op1, true);
		op2 = be_skip_downconv(op2, true);
	}

	ir_node *new_op1 = be_transform_node(op1);
	if (is_Const(op2)) {
		unsigned int const val = get_Const_long(op2);
		if (can_use_shift_constant(val, shift_modifier)) {
			switch (shift_modifier) {
			case ARM_SHF_LSL_REG: shift_modifier = ARM_SHF_LSL_IMM; break;
			case ARM_SHF_LSR_REG: shift_modifier = ARM_SHF_LSR_IMM; break;
			case ARM_SHF_ASR_REG: shift_modifier = ARM_SHF_ASR_IMM; break;
			case ARM_SHF_ROR_REG: shift_modifier = ARM_SHF_ROR_IMM; break;
			default: panic("unexpected shift modifier");
			}
			return new_bd_arm_Mov_reg_shift_imm(dbgi, block, new_op1,
			                                    shift_modifier, val);
		}
	}

	ir_node *new_op2 = be_transform_node(op2);
	return new_bd_arm_Mov_reg_shift_reg(dbgi, block, new_op1, new_op2,
	                                    shift_modifier);
}

static ir_node *gen_Shl(ir_node *node)
{
	return make_shift(node, MATCH_SIZE_NEUTRAL, ARM_SHF_LSL_REG);
}

static ir_node *gen_Shr(ir_node *node)
{
	return make_shift(node, MATCH_NONE, ARM_SHF_LSR_REG);
}

static ir_node *gen_Shrs(ir_node *node)
{
	return make_shift(node, MATCH_NONE, ARM_SHF_ASR_REG);
}

static ir_node *gen_Not(ir_node *node)
{
	ir_node  *block  = be_transform_nodes_block(node);
	ir_node  *op     = get_Not_op(node);
	ir_node  *new_op = be_transform_node(op);
	dbg_info *dbgi   = get_irn_dbg_info(node);

	/* check if we can fold in a Mov */
	if (is_arm_Mov(new_op)) {
		const arm_shifter_operand_t *attr = get_arm_shifter_operand_attr_const(new_op);

		switch (attr->shift_modifier) {
		case ARM_SHF_IMM:
		case ARM_SHF_ASR_IMM:
		case ARM_SHF_LSL_IMM:
		case ARM_SHF_LSR_IMM:
		case ARM_SHF_ROR_IMM: {
			ir_node *mov_op = get_irn_n(new_op, n_arm_Mov_Rm);
			return new_bd_arm_Mvn_reg_shift_imm(dbgi, block, mov_op,
				attr->shift_modifier, attr->shift_immediate);
		}

		case ARM_SHF_ASR_REG:
		case ARM_SHF_LSL_REG:
		case ARM_SHF_LSR_REG:
		case ARM_SHF_ROR_REG: {
			ir_node *mov_op  = get_irn_n(new_op, n_arm_Mov_Rm);
			ir_node *mov_sft = get_irn_n(new_op, n_arm_Mov_Rs);
			return new_bd_arm_Mvn_reg_shift_reg(dbgi, block, mov_op, mov_sft,
				attr->shift_modifier);
		}

		case ARM_SHF_REG:
		case ARM_SHF_RRX:
			break;
		case ARM_SHF_INVALID:
			panic("invalid shift");
		}
	}

	return new_bd_arm_Mvn_reg(dbgi, block, new_op);
}

static ir_node *gen_Minus(ir_node *node)
{
	ir_node  *block  = be_transform_nodes_block(node);
	ir_node  *op     = get_Minus_op(node);
	ir_node  *new_op = be_transform_node(op);
	dbg_info *dbgi   = get_irn_dbg_info(node);
	ir_mode  *mode   = get_irn_mode(node);

	if (mode_is_float(mode)) {
		if (arm_cg_config.fpu == ARM_FPU_FPA) {
			return new_bd_arm_Mvf(dbgi, block, op, mode);
		} else {
			panic("softfloat not lowered");
		}
	}
	assert(mode_is_data(mode));
	return new_bd_arm_Rsb_imm(dbgi, block, new_op, 0, 0);
}

static ir_node *gen_Load(ir_node *node)
{
	ir_node  *block   = be_transform_nodes_block(node);
	ir_node  *ptr     = get_Load_ptr(node);
	ir_node  *new_ptr = be_transform_node(ptr);
	ir_node  *mem     = get_Load_mem(node);
	ir_node  *new_mem = be_transform_node(mem);
	ir_mode  *mode    = get_Load_mode(node);
	dbg_info *dbgi    = get_irn_dbg_info(node);
	if (get_Load_unaligned(node) == align_non_aligned)
		panic("unaligned Loads not supported yet");

	ir_node *new_load;
	if (mode_is_float(mode)) {
		if (arm_cg_config.fpu == ARM_FPU_FPA) {
			new_load = new_bd_arm_Ldf(dbgi, block, new_ptr, new_mem,