sparc_transform.c

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

/**
 * @file
 * @brief   code selection (transform FIRM into SPARC FIRM)
 * @author  Hannes Rapp, Matthias Braun
 */
#include <stdint.h>
#include <stdbool.h>

#include "irnode_t.h"
#include "irgraph_t.h"
#include "irmode_t.h"
#include "irgmod.h"
#include "iredges.h"
#include "ircons.h"
#include "iroptimize.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 "beabihelper.h"
#include "bearch_sparc_t.h"

#include "sparc_nodes_attr.h"
#include "sparc_transform.h"
#include "sparc_new_nodes.h"
#include "gen_sparc_new_nodes.h"

#include "gen_sparc_regalloc_if.h"
#include "sparc_cconv.h"

#include <limits.h>

DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)

typedef struct reg_info_t {
	size_t   offset;
	ir_node *irn;
} reg_info_t;

static const arch_register_t *sp_reg = &sparc_registers[REG_SP];
static const arch_register_t *fp_reg = &sparc_registers[REG_FRAME_POINTER];
static calling_convention_t  *current_cconv = NULL;
static be_stackorder_t       *stackorder;
static ir_mode               *mode_gp;
static ir_mode               *mode_flags;
static ir_mode               *mode_fp;
static ir_mode               *mode_fp2;
//static ir_mode               *mode_fp4;
static pmap                  *node_to_stack;
static reg_info_t             start_mem;
static reg_info_t             start_g0;
static reg_info_t             start_g7;
static reg_info_t             start_sp;
static reg_info_t             start_fp;
static ir_node               *frame_base;
static size_t                 start_params_offset;
static size_t                 start_callee_saves_offset;

static const arch_register_t *const omit_fp_callee_saves[] = {
	&sparc_registers[REG_L0],
	&sparc_registers[REG_L1],
	&sparc_registers[REG_L2],
	&sparc_registers[REG_L3],
	&sparc_registers[REG_L4],
	&sparc_registers[REG_L5],
	&sparc_registers[REG_L6],
	&sparc_registers[REG_L7],
	&sparc_registers[REG_I0],
	&sparc_registers[REG_I1],
	&sparc_registers[REG_I2],
	&sparc_registers[REG_I3],
	&sparc_registers[REG_I4],
	&sparc_registers[REG_I5],
};

static inline bool mode_needs_gp_reg(ir_mode *mode)
{
	if (mode_is_int(mode) || mode_is_reference(mode)) {
		/* we should only see 32bit code */
		assert(get_mode_size_bits(mode) <= 32);
		return true;
	}
	return false;
}

/**
 * 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,
                                   int src_bits)
{
	if (src_bits == 8) {
		return new_bd_sparc_And_imm(dbgi, block, op, NULL, 0xFF);
	} else if (src_bits == 16) {
		ir_node *lshift = new_bd_sparc_Sll_imm(dbgi, block, op, NULL, 16);
		ir_node *rshift = new_bd_sparc_Srl_imm(dbgi, block, lshift, NULL, 16);
		return rshift;
	} else {
		panic("zero extension only supported for 8 and 16 bits");
	}
}

/**
 * Generate code for a sign extension.
 *
 * @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_sign_extension(dbg_info *dbgi, ir_node *block, ir_node *op,
                                   int src_bits)
{
	int shift_width = 32 - src_bits;
	ir_node *lshift_node = new_bd_sparc_Sll_imm(dbgi, block, op, NULL, shift_width);
	ir_node *rshift_node = new_bd_sparc_Sra_imm(dbgi, block, lshift_node, NULL, shift_width);
	return rshift_node;
}

/**
 * Extend a value to 32 bit signed/unsigned depending on its mode.
 *
 * @param dbgi      debug info
 * @param block     the basic block
 * @param op        the original node
 * @param orig_mode the original mode of op
 */
static ir_node *gen_extension(dbg_info *dbgi, ir_node *block, ir_node *op,
                              ir_mode *orig_mode)
{
	int bits = get_mode_size_bits(orig_mode);
	assert(bits < 32);

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

typedef enum {
	MATCH_NONE          = 0,
	MATCH_COMMUTATIVE   = 1U << 0, /**< commutative operation. */
	MATCH_MODE_NEUTRAL  = 1U << 1, /**< the higher bits of the inputs don't
	                                    influence the significant lower bit at
	                                    all (for cases where mode < 32bit) */
	MATCH_SIGN_EXT_LEFT = 1U << 2, /**< we need to sign-extend the left operand
	                                    (for cases when mode < 32bit) */
	MATCH_ZERO_EXT_LEFT = 1U << 3, /**< we need to zero-extend the left operand
                                            (for cases when mode < 32bit) */
} match_flags_t;
ENUM_BITSET(match_flags_t)

typedef ir_node* (*new_binop_reg_func) (dbg_info *dbgi, ir_node *block, ir_node *op1, ir_node *op2);
typedef ir_node* (*new_binop_fp_func) (dbg_info *dbgi, ir_node *block, ir_node *op1, ir_node *op2, ir_mode *mode);
typedef ir_node* (*new_binop_imm_func) (dbg_info *dbgi, ir_node *block, ir_node *op1, ir_entity *entity, int32_t immediate);
typedef ir_node* (*new_unop_fp_func) (dbg_info *dbgi, ir_node *block, ir_node *op1, ir_mode *mode);

/**
 * checks if a node's value can be encoded as a immediate
 */
static bool is_imm_encodeable(const ir_node *node)
{
	if (!is_Const(node))
		return false;

	long value = get_tarval_long(get_Const_tarval(node));
	return sparc_is_value_imm_encodeable(value);
}

static bool needs_extension(ir_node *op)
{
	ir_mode *mode = get_irn_mode(op);
	unsigned gp_bits = get_mode_size_bits(mode_gp);
	if (get_mode_size_bits(mode) >= gp_bits)
		return false;
	return !be_upper_bits_clean(op, mode);
}

/**
 * Check, if a given node is a Down-Conv, i.e. a integer Conv
 * from a mode with a mode with more bits to a mode with fewer bits.
 * Moreover, we return only true if the node has not more than 1 user.
 *
 * @param node   the node
 * @return non-zero if node is a Down-Conv
 */
static bool is_downconv(const ir_node *node)
{
	if (!is_Conv(node))
		return false;

	ir_mode *src_mode  = get_irn_mode(get_Conv_op(node));
	ir_mode *dest_mode = get_irn_mode(node);
	return
		mode_needs_gp_reg(src_mode)  &&
		mode_needs_gp_reg(dest_mode) &&
		get_mode_size_bits(dest_mode) <= get_mode_size_bits(src_mode);
}

static ir_node *skip_downconv(ir_node *node)
{
	while (is_downconv(node)) {
		node = get_Conv_op(node);
	}
	return node;
}

/**
 * An assembler constraint.
 */
typedef struct constraint_t {
	const arch_register_class_t *cls;
	char                         all_registers_allowed;
	char                         immediate_type;
	int                          same_as;
} constraint_t;

static void parse_asm_constraints(constraint_t *const constraint,
                                  ident *const constraint_text,
                                  bool const is_output)
{
	memset(constraint, 0, sizeof(constraint[0]));
	constraint->same_as = -1;

	char const *c = get_id_str(constraint_text);
	if (*c == '\0') {
		/* a memory constraint: no need to do anything in backend about it
		 * (the dependencies are already respected by the memory edge of
		 * the node) */
		return;
	}

	char                         immediate_type        = '\0';
	arch_register_class_t const *cls                   = NULL;
	bool                         all_registers_allowed = false;
	int                          same_as               = -1;
	while (*c != 0) {
		arch_register_class_t const *new_cls = NULL;
		char                         new_imm = '\0';
		switch (*c) {
		/* Skip spaces, out/in-out marker */
		case ' ':
		case '\t':
		case '\n':
		case '=':
		case '+':
		case '&': break;
		case '*':
			++c;
			break;
		case '#':
			while (*c != 0 && *c != ',')
				++c;
			break;
		case 'r':
			new_cls               = &sparc_reg_classes[CLASS_sparc_gp];
			all_registers_allowed = true;
			break;
		case 'e':
		case 'f':
			new_cls               = &sparc_reg_classes[CLASS_sparc_fp];
			all_registers_allowed = true;
			break;
		case 'A':
		case 'I':
			new_cls = &sparc_reg_classes[CLASS_sparc_gp];
			new_imm = *c;
			break;

		case '0':
		case '1':
		case '2':
		case '3':
		case '4':
		case '5':
		case '6':
		case '7':
		case '8':
		case '9': {
			if (is_output)
				panic("can only specify same constraint on input");

			int p;
			sscanf(c, "%d%n", &same_as, &p);
			if (same_as >= 0) {
				c += p;
				continue;
			}
			break;
		}

		default:
			panic("unknown asm constraint '%c'", *c);
		}

		if (new_cls) {
			if (!cls) {
				cls = new_cls;
			} else if (cls != new_cls) {
				panic("multiple register classes not supported");
			}
		}

		if (new_imm != '\0') {
			if (immediate_type == '\0') {
				immediate_type = new_imm;
			} else if (immediate_type != new_imm) {
				panic("multiple immediate types not supported");
			}
		}

		++c;
	}

	if (same_as >= 0) {
		if (cls != NULL)
			panic("same as and register constraint not supported");
		if (immediate_type != '\0')
			panic("same as and immediate constraint not supported");
	}

	if (!cls && same_as < 0)
		panic("no constraint specified for assembler input");

	constraint->same_as               = same_as;
	constraint->cls                   = cls;
	constraint->all_registers_allowed = all_registers_allowed;
	constraint->immediate_type        = immediate_type;
}

static const arch_register_t *find_register(const char *name)
{
	for (size_t i = 0; i < N_SPARC_REGISTERS; ++i) {
		const arch_register_t *const reg = &sparc_registers[i];
		if (strcmp(reg->name, name) == 0)
			return reg;
	}
	return NULL;
}

static arch_register_req_t const *make_register_req(ir_graph *const irg,
	constraint_t const *const c, int const n_outs,
	arch_register_req_t const **const out_reqs, int const pos)
{
	int const same_as = c->same_as;
	if (same_as >= 0) {
		if (same_as >= n_outs)
			panic("invalid output number in same_as constraint");

		struct obstack            *const obst  = get_irg_obstack(irg);
		arch_register_req_t       *const req   = OALLOC(obst, arch_register_req_t);
		arch_register_req_t const *const other = out_reqs[same_as];
		*req            = *other;
		req->type      |= arch_register_req_type_should_be_same;
		req->other_same = 1U << pos;

		/* Switch constraints. This is because in firm we have same_as
		 * constraints on the output constraints while in the gcc asm syntax
		 * they are specified on the input constraints. */
		out_reqs[same_as] = req;
		return other;
	}

	return c->cls->class_req;
}

void sparc_init_asm_constraints(void)
{
	static unsigned char const register_flags[] = {
		'r', 'e', 'f', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'
	};
	for (size_t i = 0; i < ARRAY_SIZE(register_flags); ++i) {
		unsigned char const c = register_flags[i];
		asm_constraint_flags[c] = ASM_CONSTRAINT_FLAG_SUPPORTS_REGISTER;
	}

	asm_constraint_flags['A'] = ASM_CONSTRAINT_FLAG_SUPPORTS_IMMEDIATE;
	asm_constraint_flags['I'] = ASM_CONSTRAINT_FLAG_SUPPORTS_IMMEDIATE;

	/* Note there are many more flags in gcc which we can't properly support
	 * at the moment. see gcc/config/sparc/constraints.md */
}

int sparc_is_valid_clobber(const char *clobber)
{
	return strcmp(clobber, "memory") == 0 || strcmp(clobber, "cc") == 0;
}

static ir_node *gen_ASM(ir_node *node)
{
	int       n_inputs     = get_ASM_n_inputs(node);
	size_t    n_clobbers   = 0;
	ident   **clobbers     = get_ASM_clobbers(node);
	ir_graph *irg          = get_irn_irg(node);
	//unsigned  clobber_bits[BITSET_SIZE_ELEMS(N_SPARC_REGISTERS)];

	for (size_t c = 0; c < get_ASM_n_clobbers(node); ++c) {
		const char *const clobber = get_id_str(clobbers[c]);
		if (strcmp(clobber, "memory") == 0)
			continue;
		if (strcmp(clobber, "cc") == 0) {
			n_clobbers += 2;
			continue;
		}

		const arch_register_t *reg = find_register(clobber);
		if (reg == NULL)
			panic("invalid clobber in sparc asm");

#if 0
		rbitset_set(clobber_bits, reg->global_index);
		++n_clobbers;
#else
		panic("clobbers not correctly supported yet");
#endif
	}
	size_t n_out_constraints = get_ASM_n_output_constraints(node);
	size_t n_outs            = n_out_constraints + n_clobbers;

	const ir_asm_constraint *in_constraints  = get_ASM_input_constraints(node);
	const ir_asm_constraint *out_constraints = get_ASM_output_constraints(node);

	/* determine number of operands */
	unsigned n_operands = 0;
	for (size_t out_idx = 0; out_idx < n_out_constraints; ++out_idx) {
		const ir_asm_constraint *constraint = &out_constraints[out_idx];
		if (constraint->pos+1 > n_operands)
			n_operands = constraint->pos+1;
	}
	for (int i = 0; i < n_inputs; ++i) {
		const ir_asm_constraint *constraint = &in_constraints[i];
		if (constraint->pos+1 > n_operands)
			n_operands = constraint->pos+1;
	}

	struct obstack      *const obst = get_irg_obstack(irg);
	sparc_asm_operand_t *const operands
		= NEW_ARR_DZ(sparc_asm_operand_t, obst, n_operands);

	/* construct output constraints */
	size_t                      out_size = n_outs + 1;
	const arch_register_req_t **out_reg_reqs
		= OALLOCN(obst, const arch_register_req_t*, out_size);

	size_t out_idx;
	for (out_idx = 0; out_idx < n_out_constraints; ++out_idx) {
		const ir_asm_constraint *constraint = &out_constraints[out_idx];
		unsigned                 pos        = constraint->pos;
		constraint_t             parsed_constraint;
		parse_asm_constraints(&parsed_constraint, constraint->constraint, true);

		assert(parsed_constraint.immediate_type == 0);
		arch_register_req_t const *const req
			= make_register_req(irg, &parsed_constraint, n_out_constraints,
			                    out_reg_reqs, out_idx);
		out_reg_reqs[out_idx] = req;

		/* TODO: adjust register_req for clobbers */

		sparc_asm_operand_t *const operand = &operands[pos];
		operand->kind = ASM_OPERAND_OUTPUT_VALUE;
		operand->pos  = out_idx;
	}

	/* inputs + input constraints */
	int       max_ins      = n_inputs+1;
	ir_node **in = ALLOCANZ(ir_node*, max_ins);
	const arch_register_req_t **in_reg_reqs
		= OALLOCN(obst, const arch_register_req_t*, max_ins);
	int n_ins = 0;
	for (int i = 0; i < n_inputs; ++i) {
		ir_node                 *pred         = get_ASM_input(node, i);
		const ir_asm_constraint *constraint   = &in_constraints[i];
		unsigned                 pos          = constraint->pos;

		constraint_t parsed_constraint;
		parse_asm_constraints(&parsed_constraint, constraint->constraint, false);

		sparc_asm_operand_t *const operand = &operands[pos];

		/* try to use an immediate value */
		char imm_type = parsed_constraint.immediate_type;
		if (imm_type == 'I') {
			if (is_imm_encodeable(pred)) {
				operand->kind = ASM_OPERAND_IMMEDIATE;
				operand->immediate_value = get_tarval_long(get_Const_tarval(pred));
				continue;
			}
		} else if (imm_type == 'A') {
			/* TODO: match Add(Address,Const), ... */
			if (is_Address(pred)) {
				operand->kind = ASM_OPERAND_IMMEDIATE;
				operand->immediate_value_entity = get_Address_entity(pred);
				continue;
			} else if (is_Const(pred)) {
				operand->kind = ASM_OPERAND_IMMEDIATE;
				operand->immediate_value = get_tarval_long(get_Const_tarval(pred));
				continue;
			}
		}

		arch_register_req_t const *const req = make_register_req(irg, &parsed_constraint, n_out_constraints, out_reg_reqs, i);
		in_reg_reqs[i] = req;

		int      op_pos      = n_ins++;
		ir_node *new_pred = be_transform_node(pred);
		in[op_pos]    = new_pred;
		operand->kind = ASM_OPERAND_INPUT_VALUE;
		operand->pos  = op_pos;
	}

	int      mem_pos     = n_ins++;
	ir_node *mem         = get_ASM_mem(node);
	in[mem_pos]          = be_transform_node(mem);
	in_reg_reqs[mem_pos] = arch_no_register_req;

	/* parse clobbers */
	for (size_t c = 0; c < get_ASM_n_clobbers(node); ++c) {
		const char *const clobber = get_id_str(clobbers[c]);
		if (strcmp(clobber, "memory") == 0)
			continue;
		if (strcmp(clobber, "cc") == 0) {
			const arch_register_t *flags_reg
				= &sparc_registers[REG_FLAGS];
			out_reg_reqs[out_idx++] = flags_reg->single_req;
			const arch_register_t *fpflags_reg
				= &sparc_registers[REG_FPFLAGS];
			out_reg_reqs[out_idx++] = fpflags_reg->single_req;
			continue;
		}

		const arch_register_t *reg = find_register(clobber);
		assert(reg != NULL); /* otherwise we had a panic earlier */
		out_reg_reqs[out_idx++] = reg->single_req;
	}

	/* append none register requirement for the memory output */
	if (n_outs+1 >= out_size) {
		out_size = n_outs + 1;
		const arch_register_req_t **new_out_reg_reqs
			= OALLOCN(obst, const arch_register_req_t*, out_size);
		memcpy(new_out_reg_reqs, out_reg_reqs,
			   n_outs * sizeof(new_out_reg_reqs[0]));
		out_reg_reqs = new_out_reg_reqs;
	}

	/* add a new (dummy) output which occupies the register */
	out_reg_reqs[n_outs] = arch_no_register_req;
	++n_outs;

	dbg_info *const dbgi      = get_irn_dbg_info(node);
	ir_node  *const block     = get_nodes_block(node);
	ir_node  *const new_block = be_transform_node(block);
	ident    *const text      = get_ASM_text(node);
	ir_node  *const new_node
		= new_bd_sparc_ASM(dbgi, new_block, n_ins, in, n_outs, text, operands);

	backend_info_t *const info = be_get_info(new_node);
	for (size_t o = 0; o < n_outs; ++o) {
		info->out_infos[o].req = out_reg_reqs[o];
	}
	arch_set_irn_register_reqs_in(new_node, in_reg_reqs);

	return new_node;
}

/* Transforms the left operand of a binary operation.
 *
 * Performs sign/zero extension if necessary.
 */
static ir_node *gen_helper_binop_left(ir_node *left, dbg_info *dbgi,
                                      ir_node *block, match_flags_t flags)
{
	ir_mode *mode     = get_irn_mode(left);
	ir_node *new_left = be_transform_node(left);

	if (flags & MATCH_MODE_NEUTRAL)
		return new_left;

	int bits    = get_mode_size_bits(mode);
	int gp_bits = get_mode_size_bits(mode_gp);

	if (bits >= gp_bits)
		return new_left;

	if (flags & MATCH_SIGN_EXT_LEFT) {
		if (!mode_is_signed(mode) || needs_extension(left)) {
			return gen_sign_extension(dbgi, block, new_left, bits);
		}
	} else if (flags & MATCH_ZERO_EXT_LEFT) {
		if (mode_is_signed(mode) || needs_extension(left)) {
			return gen_zero_extension(dbgi, block, new_left, bits);
		}
	} else if (needs_extension(left)) {
		return gen_extension(dbgi, block, new_left, mode);
	}

	return new_left;
}

/**
 * helper function for binop operations
 *
 * @param new_reg  register generation function ptr
 * @param new_imm  immediate generation function ptr
 */
static ir_node *gen_helper_binop_args(ir_node *node,
                                      ir_node *op1, ir_node *op2,
                                      match_flags_t flags,
                                      new_binop_reg_func new_reg,
                                      new_binop_imm_func new_imm)
{
	dbg_info *dbgi  = get_irn_dbg_info(node);
	ir_node  *block = be_transform_node(get_nodes_block(node));

	if (flags & MATCH_MODE_NEUTRAL) {
		op1 = skip_downconv(op1);
		op2 = skip_downconv(op2);
	}
	ir_mode *mode2 = get_irn_mode(op2);
	/* we should not see 64bit code */
	assert(get_mode_size_bits(get_irn_mode(op1)) <= 32);
	assert(get_mode_size_bits(mode2) <= 32);

	if (is_imm_encodeable(op2)) {
		int32_t  immediate = get_tarval_long(get_Const_tarval(op2));
		ir_node *new_op1   = gen_helper_binop_left(op1, dbgi, block, flags);
		return new_imm(dbgi, block, new_op1, NULL, immediate);
	}
	ir_node *new_op2 = be_transform_node(op2);
	if (! (flags & MATCH_MODE_NEUTRAL) && needs_extension(op2)) {
		new_op2 = gen_extension(dbgi, block, new_op2, mode2);
	}

	if ((flags & MATCH_COMMUTATIVE) && is_imm_encodeable(op1)) {
		int32_t immediate = get_tarval_long(get_Const_tarval(op1));
		return new_imm(dbgi, block, new_op2, NULL, immediate);
	}

	ir_node *new_op1 = gen_helper_binop_left(op1, dbgi, block, flags);
	return new_reg(dbgi, block, new_op1, new_op2);
}

static ir_node *gen_helper_binop(ir_node *node, match_flags_t flags,
                                 new_binop_reg_func new_reg,
                                 new_binop_imm_func new_imm)
{
	ir_node *op1 = get_binop_left(node);
	ir_node *op2 = get_binop_right(node);
	return gen_helper_binop_args(node, op1, op2, flags, new_reg, new_imm);
}

/**
 * helper function for FP binop operations
 */
static ir_node *gen_helper_binfpop(ir_node *node, ir_mode *mode,
                                   new_binop_fp_func new_func_single,
                                   new_binop_fp_func new_func_double,
                                   new_binop_fp_func new_func_quad)
{
	ir_node  *block   = be_transform_node(get_nodes_block(node));
	ir_node  *op1     = get_binop_left(node);
	ir_node  *new_op1 = be_transform_node(op1);
	ir_node  *op2     = get_binop_right(node);
	ir_node  *new_op2 = be_transform_node(op2);
	dbg_info *dbgi    = get_irn_dbg_info(node);
	unsigned  bits    = get_mode_size_bits(mode);

	switch (bits) {
	case 32:
		return new_func_single(dbgi, block, new_op1, new_op2, mode);
	case 64:
		return new_func_double(dbgi, block, new_op1, new_op2, mode);
	case 128:
		return new_func_quad(dbgi, block, new_op1, new_op2, mode);
	default:
		break;
	}
	panic("unsupported mode %+F for float op", mode);
}

typedef ir_node* (*new_binopx_imm_func)(dbg_info *dbgi, ir_node *block,
                                        ir_node *op1, ir_node *flags,
                                        ir_entity *imm_entity, int32_t imm);

typedef ir_node* (*new_binopx_reg_func)(dbg_info *dbgi, ir_node *block,
                                        ir_node *op1, ir_node *op2,
                                        ir_node *flags);

static ir_node *gen_helper_binopx(ir_node *node, match_flags_t match_flags,
                                  new_binopx_reg_func new_binopx_reg,
                                  new_binopx_imm_func new_binopx_imm)
{
	dbg_info *dbgi      = get_irn_dbg_info(node);
	ir_node  *block     = be_transform_node(get_nodes_block(node));
	ir_node  *op1       = get_irn_n(node, 0);
	ir_node  *op2       = get_irn_n(node, 1);
	ir_node  *flags     = get_irn_n(node, 2);
	ir_node  *new_flags = be_transform_node(flags);

	/* only support for mode-neutral implemented so far */
	assert(match_flags & MATCH_MODE_NEUTRAL);

	if (is_imm_encodeable(op2)) {
		int32_t  immediate = get_tarval_long(get_Const_tarval(op2));
		ir_node *new_op1   = be_transform_node(op1);
		return new_binopx_imm(dbgi, block, new_op1, new_flags, NULL, immediate);
	}
	ir_node *new_op2 = be_transform_node(op2);
	if ((match_flags & MATCH_COMMUTATIVE) && is_imm_encodeable(op1)) {
		int32_t immediate = get_tarval_long(get_Const_tarval(op1));
		return new_binopx_imm(dbgi, block, new_op2, new_flags, NULL, immediate);
	}
	ir_node *new_op1 = be_transform_node(op1);
	return new_binopx_reg(dbgi, block, new_op1, new_op2, new_flags);

}

static ir_node *get_reg(ir_graph *const irg, reg_info_t *const reg)
{
	if (!reg->irn) {
		/* this is already the transformed start node */
		ir_node *const start = get_irg_start(irg);
		assert(is_sparc_Start(start));
		arch_register_class_t const *const cls = arch_get_irn_register_req_out(start, reg->offset)->cls;
		reg->irn = new_r_Proj(start, cls ? cls->mode : mode_M, reg->offset);
	}
	return reg->irn;
}

static ir_node *get_g0(ir_graph *irg)
{
	return get_reg(irg, &start_g0);
}

static ir_node *get_g7(ir_graph *irg)
{
	return get_reg(irg, &start_g7);
}

static ir_node *make_tls_offset(dbg_info *dbgi, ir_node *block,
                                ir_entity *entity, int32_t offset)
{
	ir_node  *hi  = new_bd_sparc_SetHi(dbgi, block, entity, offset);
	ir_node  *low = new_bd_sparc_Xor_imm(dbgi, block, hi, entity, offset);
	return low;
}

static ir_node *make_address(dbg_info *dbgi, ir_node *block, ir_entity *entity,
                             int32_t offset)
{
	if (is_tls_entity(entity)) {
		ir_graph *irg     = get_irn_irg(block);
		ir_node  *g7      = get_g7(irg);
		ir_node  *offsetn = make_tls_offset(dbgi, block, entity, offset);
		ir_node  *add     = new_bd_sparc_Add_reg(dbgi, block, g7, offsetn);
		return add;
	} else {
		ir_node *hi  = new_bd_sparc_SetHi(dbgi, block, entity, offset);
		ir_node *low = new_bd_sparc_Or_imm(dbgi, block, hi, entity, offset);
		return low;
	}
}

typedef struct address_t {
	ir_node   *ptr;
	ir_node   *ptr2;
	ir_entity *entity;
	int32_t    offset;
} address_t;

/**
 * Match a load/store address
 */
static void match_address(ir_node *ptr, address_t *address, bool use_ptr2)
{
	ir_node   *base   = ptr;
	int32_t    offset = 0;

	if (is_Add(base)) {
		ir_node *add_right = get_Add_right(base);
		if (is_Const(add_right)) {
			base    = get_Add_left(base);
			offset += get_tarval_long(get_Const_tarval(add_right));
		}
	}
	/* Note that we don't match sub(x, Const) or chains of adds/subs
	 * because this should all be normalized by now */

	/* we only use the entity if we're the only user otherwise we probably
	 * won't save anything but produce multiple sethi+or combinations with
	 * just different offsets */
	ir_node   *ptr2   = NULL;
	ir_entity *entity = NULL;
	if (is_Address(base) && get_irn_n_edges(base) == 1) {
		ir_entity *sc_entity = get_Address_entity(base);
		dbg_info  *dbgi      = get_irn_dbg_info(ptr);
		ir_node   *block     = get_nodes_block(ptr);
		ir_node   *new_block = be_transform_node(block);

		if (is_tls_entity(sc_entity)) {
			if (!use_ptr2) {
				goto only_offset;
			} else {
				ptr2   = make_tls_offset(dbgi, new_block, sc_entity, offset);
				offset = 0;
				base   = get_g7(get_irn_irg(base));
			}
		} else {
			entity = sc_entity;
			base   = new_bd_sparc_SetHi(dbgi, new_block, entity, offset);
		}
	} else if (use_ptr2 && is_Add(base) && offset == 0) {
		ptr2 = be_transform_node(get_Add_right(base));
		base = be_transform_node(get_Add_left(base));
	} else {
only_offset:
		if (sparc_is_value_imm_encodeable(offset)) {
			base = be_transform_node(base);
		} else {
			base   = be_transform_node(ptr);
			offset = 0;
		}
	}

	address->ptr    = base;
	address->ptr2   = ptr2;
	address->entity = entity;
	address->offset = offset;
}

static ir_node *gen_Proj_ASM(ir_node *node)
{
	ir_mode *mode     = get_irn_mode(node);
	ir_node *pred     = get_Proj_pred(node);
	ir_node *new_pred = be_transform_node(pred);
	unsigned pn       = get_Proj_num(node);

	if (mode == mode_M) {
		pn = arch_get_irn_n_outs(new_pred)-1;
	} else if (mode_needs_gp_reg(mode)) {
		mode = mode_gp;
	} else {
		panic("unexpected proj mode at ASM");
	}

	return new_r_Proj(new_pred, mode, pn);
}

/**
 * Creates an sparc Add.
 *
 * @param node   FIRM node
 * @return the created sparc Add node
 */
static ir_node *gen_Add(ir_node *node)
{
	ir_mode *mode = get_irn_mode(node);
	if (mode_is_float(mode)) {
		return gen_helper_binfpop(node, mode, new_bd_sparc_fadd_s,
		                          new_bd_sparc_fadd_d, new_bd_sparc_fadd_q);
	}

	/* special case: + 0x1000 can be represented as - 0x1000 */
	ir_node *right = get_Add_right(node);
	if (is_Const(right)) {
		ir_node   *left = get_Add_left(node);
		/* is this simple address arithmetic? then we can let the linker do
		 * the calculation. */
		if (is_Address(left) && get_irn_n_edges(left) == 1) {
			dbg_info *dbgi  = get_irn_dbg_info(node);
			ir_node  *block = be_transform_node(get_nodes_block(node));

			/* the value of use_ptr2 shouldn't matter here */
			address_t address;
			match_address(node, &address, false);
			assert(is_sparc_SetHi(address.ptr));
			return new_bd_sparc_Or_imm(dbgi, block, address.ptr,
			                           address.entity, address.offset);
		}

		ir_tarval *tv  = get_Const_tarval(right);
		uint32_t   val = get_tarval_long(tv);
		if (val == 0x1000) {
			dbg_info *dbgi   = get_irn_dbg_info(node);
			ir_node  *block  = be_transform_node(get_nodes_block(node));
			ir_node  *op     = get_Add_left(node);
			ir_node  *new_op = be_transform_node(op);
			return new_bd_sparc_Sub_imm(dbgi, block, new_op, NULL, -0x1000);
		}
	}

	return gen_helper_binop(node, MATCH_COMMUTATIVE | MATCH_MODE_NEUTRAL,
	                        new_bd_sparc_Add_reg, new_bd_sparc_Add_imm);
}

static ir_node *gen_AddCC_t(ir_node *node)
{
	ir_node *left     = get_irn_n(node, n_sparc_AddCC_t_left);
	ir_node *right    = get_irn_n(node, n_sparc_AddCC_t_right);
	ir_node *new_node = gen_helper_binop_args(node, left, right,
	                             MATCH_COMMUTATIVE | MATCH_MODE_NEUTRAL,
	                             new_bd_sparc_AddCC_reg, new_bd_sparc_AddCC_imm);
	arch_set_irn_register_out(new_node, pn_sparc_AddCC_flags, &sparc_registers[REG_FLAGS]);

	return new_node;
}

static ir_node *gen_Proj_AddCC_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) {
	case pn_sparc_AddCC_t_res:
		return new_r_Proj(new_pred, mode_gp, pn_sparc_AddCC_res);
	case pn_sparc_AddCC_t_flags:
		return new_r_Proj(new_pred, mode_flags, pn_sparc_AddCC_flags);
	default:
		panic("Invalid proj found");
	}
}

static ir_node *gen_AddX_t(ir_node *node)
{
	return gen_helper_binopx(node, MATCH_COMMUTATIVE | MATCH_MODE_NEUTRAL,
	                         new_bd_sparc_AddX_reg, new_bd_sparc_AddX_imm);
}

/**
 * Creates an sparc Sub.
 *
 * @param node       FIRM node
 * @return the created sparc Sub node
 */
static ir_node *gen_Sub(ir_node *node)
{
	ir_mode *mode = get_irn_mode(node);
	if (mode_is_float(mode)) {
		return gen_helper_binfpop(node, mode, new_bd_sparc_fsub_s,
		                          new_bd_sparc_fsub_d, new_bd_sparc_fsub_q);
	}

	return gen_helper_binop(node, MATCH_MODE_NEUTRAL,
	                        new_bd_sparc_Sub_reg, new_bd_sparc_Sub_imm);
}

static ir_node *gen_SubCC_t(ir_node *node)
{
	ir_node *left     = get_irn_n(node, n_sparc_SubCC_t_left);
	ir_node *right    = get_irn_n(node, n_sparc_SubCC_t_right);
	ir_node *new_node = gen_helper_binop_args(node, left, right, MATCH_MODE_NEUTRAL,
	                             new_bd_sparc_SubCC_reg, new_bd_sparc_SubCC_imm);
	arch_set_irn_register_out(new_node, pn_sparc_SubCC_flags, &sparc_registers[REG_FLAGS]);

	return new_node;
}

static ir_node *gen_Proj_SubCC_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) {
	case pn_sparc_SubCC_t_res:
		return new_r_Proj(new_pred, mode_gp, pn_sparc_SubCC_res);
	case pn_sparc_SubCC_t_flags:
		return new_r_Proj(new_pred, mode_flags, pn_sparc_SubCC_flags);
	default:
		panic("Invalid proj found");
	}
}

static ir_node *gen_SubX_t(ir_node *node)
{
	return gen_helper_binopx(node, MATCH_MODE_NEUTRAL,
	                         new_bd_sparc_SubX_reg, new_bd_sparc_SubX_imm);
}

ir_node *create_ldf(dbg_info *dbgi, ir_node *block, ir_node *ptr,
                    ir_node *mem, ir_mode *mode, ir_entity *entity,
                    long offset, bool is_frame_entity)
{
	unsigned bits = get_mode_size_bits(mode);
	assert(mode_is_float(mode));
	if (bits == 32) {
		return new_bd_sparc_Ldf_s(dbgi, block, ptr, mem, mode, entity,
		                          offset, is_frame_entity);
	} else if (bits == 64) {
		return new_bd_sparc_Ldf_d(dbgi, block, ptr, mem, mode, entity,
		                          offset, is_frame_entity);
	} else {
		assert(bits == 128);
		return new_bd_sparc_Ldf_q(dbgi, block, ptr, mem, mode, entity,
		                          offset, is_frame_entity);
	}
}

ir_node *create_stf(dbg_info *dbgi, ir_node *block, ir_node *value,
                    ir_node *ptr, ir_node *mem, ir_mode *mode,
                    ir_entity *entity, long offset,
                    bool is_frame_entity)
{
	unsigned bits = get_mode_size_bits(mode);
	assert(mode_is_float(mode));
	if (bits == 32) {
		return new_bd_sparc_Stf_s(dbgi, block, value, ptr, mem, mode, entity,
		                          offset, is_frame_entity);
	} else if (bits == 64) {
		return new_bd_sparc_Stf_d(dbgi, block, value, ptr, mem, mode, entity,
		                          offset, is_frame_entity);
	} else {
		assert(bits == 128);
		return new_bd_sparc_Stf_q(dbgi, block, value, ptr, mem, mode, entity,
		                          offset, is_frame_entity);
	}
}

/**
 * Transforms a Load.
 *
 * @param node    the ir Load node
 * @return the created sparc Load node
 */
static ir_node *gen_Load(ir_node *node)
{
	dbg_info *dbgi     = get_irn_dbg_info(node);
	ir_mode  *mode     = get_Load_mode(node);
	ir_node  *block    = be_transform_node(get_nodes_block(node));
	ir_node  *ptr      = get_Load_ptr(node);
	ir_node  *mem      = get_Load_mem(node);
	ir_node  *new_mem  = be_transform_node(mem);

	if (get_Load_unaligned(node) == align_non_aligned) {
		panic("transformation of unaligned Loads not implemented yet");
	}

	ir_node  *new_load;
	if (mode_is_float(mode)) {
		address_t address;
		match_address(ptr, &address, false);
		new_load = create_ldf(dbgi, block, address.ptr, new_mem, mode,
		                      address.entity, address.offset, false);
	} else {
		address_t address;
		match_address(ptr, &address, true);
		if (address.ptr2 != NULL) {
			assert(address.entity == NULL && address.offset == 0);
			new_load = new_bd_sparc_Ld_reg(dbgi, block, address.ptr,
			                               address.ptr2, new_mem, mode);
		} else {
			new_load = new_bd_sparc_Ld_imm(dbgi, block, address.ptr, new_mem,
			                               mode, address.entity, address.offset,
			                               false);
		}
	}
	set_irn_pinned(new_load, get_irn_pinned(node));

	return new_load;
}

/**
 * Transforms a Store.
 *
 * @param node    the ir Store node
 * @return the created sparc Store node
 */
static ir_node *gen_Store(ir_node *node)
{
	ir_node  *block    = be_transform_node(get_nodes_block(node));
	ir_node  *ptr      = get_Store_ptr(node);
	ir_node  *mem      = get_Store_mem(node);
	ir_node  *new_mem  = be_transform_node(mem);
	ir_node  *val      = get_Store_value(node);
	ir_mode  *mode     = get_irn_mode(val);
	dbg_info *dbgi     = get_irn_dbg_info(node);

	if (get_Store_unaligned(node) == align_non_aligned) {
		panic("transformation of unaligned Stores not implemented yet");
	}

	ir_node  *new_store;
	if (mode_is_float(mode)) {
		ir_node *new_val = be_transform_node(val);
		/* TODO: variants with reg+reg address mode */
		address_t address;
		match_address(ptr, &address, false);
		new_store = create_stf(dbgi, block, new_val, address.ptr, new_mem,
		                       mode, address.entity, address.offset, false);
	} else {
		unsigned dest_bits = get_mode_size_bits(mode);
		while (is_downconv(node)
		       && get_mode_size_bits(get_irn_mode(node)) >= dest_bits) {
		    val = get_Conv_op(val);
		}
		ir_node *new_val = be_transform_node(val);

		assert(dest_bits <= 32);
		address_t address;
		match_address(ptr, &address, true);
		if (address.ptr2 != NULL) {
			assert(address.entity == NULL && address.offset == 0);
			new_store = new_bd_sparc_St_reg(dbgi, block, new_val, address.ptr,
			                                address.ptr2, new_mem, mode);
		} else {
			new_store = new_bd_sparc_St_imm(dbgi, block, new_val, address.ptr,
			                                new_mem, mode, address.entity,
			                                address.offset, false);
		}
	}
	set_irn_pinned(new_store, get_irn_pinned(node));

	return new_store;
}

/**
 * Creates an sparc Mul.
 * returns the lower 32bits of the 64bit multiply result
 *
 * @return the created sparc Mul node
 */
static ir_node *gen_Mul(ir_node *node)
{
	ir_mode *mode = get_irn_mode(node);
	if (mode_is_float(mode)) {
		return gen_helper_binfpop(node, mode, new_bd_sparc_fmul_s,
		                          new_bd_sparc_fmul_d, new_bd_sparc_fmul_q);
	}

	return gen_helper_binop(node, MATCH_COMMUTATIVE | MATCH_MODE_NEUTRAL,
	                        new_bd_sparc_Mul_reg, new_bd_sparc_Mul_imm);
}

/**
 * Creates an sparc Mulh.
 * Mulh returns the upper 32bits of a mul instruction
 *
 * @return the created sparc Mulh node
 */
static ir_node *gen_Mulh(ir_node *node)
{
	ir_mode *mode = get_irn_mode(node);
	if (mode_is_float(mode))
		panic("FP not supported yet");

	if (mode_is_signed(mode)) {
		ir_node *mul = gen_helper_binop(node, MATCH_COMMUTATIVE, new_bd_sparc_SMulh_reg, new_bd_sparc_SMulh_imm);
		return new_r_Proj(mul, mode_gp, pn_sparc_SMulh_low);
	} else {
		ir_node *mul = gen_helper_binop(node, MATCH_COMMUTATIVE, new_bd_sparc_UMulh_reg, new_bd_sparc_UMulh_imm);
		return new_r_Proj(mul, mode_gp, pn_sparc_UMulh_low);
	}
}

static ir_node *gen_sign_extension_value(ir_node *node)
{
	ir_node *block     = get_nodes_block(node);
	ir_node *new_block = be_transform_node(block);
	ir_node *new_node  = be_transform_node(node);
	/* TODO: we could do some shortcuts for some value types probably.
	 * (For constants or other cases where we know the sign bit in
	 *  advance) */
	return new_bd_sparc_Sra_imm(NULL, new_block, new_node, NULL, 31);
}

/**
 * Creates an sparc Div.
 *
 * @return the created sparc Div node
 */
static ir_node *gen_Div(ir_node *node)
{
	dbg_info *dbgi      = get_irn_dbg_info(node);
	ir_node  *block     = get_nodes_block(node);
	ir_node  *new_block = be_transform_node(block);
	ir_mode  *mode      = get_Div_resmode(node);
	ir_node  *left      = get_Div_left(node);
	ir_node  *left_low  = be_transform_node(left);
	ir_node  *right     = get_Div_right(node);

	if (mode_is_float(mode)) {
		return gen_helper_binfpop(node, mode, new_bd_sparc_fdiv_s,
		                          new_bd_sparc_fdiv_d, new_bd_sparc_fdiv_q);
	}

	ir_node *mem     = get_Div_mem(node);
	ir_node *new_mem = be_transform_node(mem);
	ir_node *res;
	if (mode_is_signed(mode)) {
		ir_node *left_high = gen_sign_extension_value(left);

		if (is_imm_encodeable(right)) {
			int32_t immediate = get_tarval_long(get_Const_tarval(right));
			res = new_bd_sparc_SDiv_imm(dbgi, new_block, new_mem, left_high, left_low,
			                            NULL, immediate);
		} else {
			ir_node *new_right = be_transform_node(right);
			res = new_bd_sparc_SDiv_reg(dbgi, new_block, new_mem, left_high, left_low,
			                            new_right);
		}
	} else {
		ir_graph *irg       = get_irn_irg(node);
		ir_node  *left_high = get_g0(irg);
		if (is_imm_encodeable(right)) {
			int32_t immediate = get_tarval_long(get_Const_tarval(right));
			res = new_bd_sparc_UDiv_imm(dbgi, new_block, new_mem, left_high, left_low,
			                            NULL, immediate);
		} else {
			ir_node *new_right = be_transform_node(right);
			res = new_bd_sparc_UDiv_reg(dbgi, new_block, new_mem, left_high, left_low,
			                            new_right);
		}
	}

	return res;
}

/**
 * Transforms a Not node.
 *
 * @return the created sparc Not node
 */
static ir_node *gen_Not(ir_node *node)
{
	ir_node  *op     = get_Not_op(node);
	ir_graph *irg    = get_irn_irg(node);
	ir_node  *zero   = get_g0(irg);
	dbg_info *dbgi   = get_irn_dbg_info(node);
	ir_node  *block  = be_transform_node(get_nodes_block(node));
	ir_node  *new_op = be_transform_node(op);

	/* Note: Not(Eor()) is normalize in firm localopts already so
	 * we don't match it for xnor here */

	/* Not can be represented with xnor 0, n */
	return new_bd_sparc_XNor_reg(dbgi, block, zero, new_op);
}

static ir_node *gen_helper_bitop(ir_node *node,
                                 new_binop_reg_func new_reg,
                                 new_binop_imm_func new_imm,
                                 new_binop_reg_func new_not_reg,
                                 new_binop_imm_func new_not_imm,
                                 match_flags_t flags)
{
	ir_node *op1 = get_binop_left(node);
	ir_node *op2 = get_binop_right(node);
	if (is_Not(op1)) {
		return gen_helper_binop_args(node, op2, get_Not_op(op1),
		                             flags,
		                             new_not_reg, new_not_imm);
	}
	if (is_Not(op2)) {
		return gen_helper_binop_args(node, op1, get_Not_op(op2),
		                             flags,
		                             new_not_reg, new_not_imm);
	}
	if (is_Const(op2) && get_irn_n_edges(op2) == 1) {
		ir_tarval *tv    = get_Const_tarval(op2);
		long       value = get_tarval_long(tv);
		if (!sparc_is_value_imm_encodeable(value)) {
			long notvalue = ~value;
			if ((notvalue & 0x3ff) == 0) {
				ir_node  *block     = get_nodes_block(node);
				ir_node  *new_block = be_transform_node(block);
				dbg_info *dbgi      = get_irn_dbg_info(node);
				ir_node  *new_op2
					= new_bd_sparc_SetHi(