beabi.c

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

/**
 * @file
 * @brief       Backend ABI implementation.
 * @author      Sebastian Hack, Michael Beck
 * @version     $Id$
 */
#include "config.h"

#include "obst.h"

#include "irgopt.h"

#include "irgraph_t.h"
#include "irnode_t.h"
#include "ircons_t.h"
#include "iredges_t.h"
#include "irgmod.h"
#include "irgwalk.h"
#include "irprintf_t.h"
#include "irgopt.h"
#include "irbitset.h"
#include "iropt_t.h"
#include "height.h"
#include "pdeq.h"
#include "irtools.h"
#include "raw_bitset.h"
#include "error.h"
#include "pset_new.h"

#include "be.h"
#include "beabi.h"
#include "bearch.h"
#include "benode.h"
#include "belive_t.h"
#include "besched.h"
#include "beirg.h"
#include "bessaconstr.h"
#include "bemodule.h"

DEBUG_ONLY(static firm_dbg_module_t *dbg;)

typedef struct _be_abi_call_arg_t {
	unsigned is_res   : 1;  /**< 1: the call argument is a return value. 0: it's a call parameter. */
	unsigned in_reg   : 1;  /**< 1: this argument is transmitted in registers. */
	unsigned on_stack : 1;	/**< 1: this argument is transmitted on the stack. */
	unsigned callee   : 1;  /**< 1: someone called us. 0: We call another function */

	int                    pos;
	const arch_register_t *reg;
	ir_entity             *stack_ent;
	ir_mode               *load_mode;
	unsigned               alignment;    /**< stack alignment */
	unsigned               space_before; /**< allocate space before */
	unsigned               space_after;  /**< allocate space after */
} be_abi_call_arg_t;

struct _be_abi_call_t {
	be_abi_call_flags_t          flags;  /**< Flags describing the ABI behavior on calls */
	int                          pop;    /**< number of bytes the stack frame is shrinked by the callee on return. */
	const be_abi_callbacks_t    *cb;
	ir_type                     *between_type;
	set                         *params;
	const arch_register_class_t *cls_addr; /**< register class of the call address */
};

/**
 * The ABI information for the current graph.
 */
struct _be_abi_irg_t {
	survive_dce_t        *dce_survivor;

	be_abi_call_t        *call;         /**< The ABI call information. */

	ir_node              *init_sp;      /**< The node representing the stack pointer
	                                         at the start of the function. */

	ir_node              *start;        /**< The be_Start params node. */
	pmap                 *regs;         /**< A map of all callee-save and ignore regs to
	                                         their Projs to the RegParams node. */

	int                  start_block_bias; /**< The stack bias at the end of the start block. */

	void                 *cb;           /**< ABI Callback self pointer. */

	pmap                 *keep_map;     /**< mapping blocks to keep nodes. */
	pset                 *ignore_regs;  /**< Additional registers which shall be ignored. */

	ir_node              **calls;       /**< flexible array containing all be_Call nodes */

	arch_register_req_t  *sp_req;
};

static heights_t *ir_heights;

/** Flag: if set, try to omit the frame pointer in all routines. */
static int be_omit_fp = 1;

/** Flag: if set, try to omit the frame pointer in leaf routines only. */
static int be_omit_leaf_fp = 1;

/*
     _    ____ ___    ____      _ _ _                _
    / \  | __ )_ _|  / ___|__ _| | | |__   __ _  ___| | _____
   / _ \ |  _ \| |  | |   / _` | | | '_ \ / _` |/ __| |/ / __|
  / ___ \| |_) | |  | |__| (_| | | | |_) | (_| | (__|   <\__ \
 /_/   \_\____/___|  \____\__,_|_|_|_.__/ \__,_|\___|_|\_\___/

  These callbacks are used by the backend to set the parameters
  for a specific call type.
*/

/**
 * Set compare function: compares two ABI call object arguments.
 */
static int cmp_call_arg(const void *a, const void *b, size_t n)
{
	const be_abi_call_arg_t *p = a, *q = b;
	(void) n;
	return !(p->is_res == q->is_res && p->pos == q->pos && p->callee == q->callee);
}

/**
 * Get  an ABI call object argument.
 *
 * @param call      the abi call
 * @param is_res    true for call results, false for call arguments
 * @param pos       position of the argument
 * @param callee	context type - if we are callee or caller
 */
static be_abi_call_arg_t *get_call_arg(be_abi_call_t *call, int is_res, int pos, int callee)
{
	be_abi_call_arg_t arg;
	unsigned hash;

	memset(&arg, 0, sizeof(arg));
	arg.is_res = is_res;
	arg.pos    = pos;
	arg.callee = callee;

	hash = is_res * 128 + pos;

	return set_find(call->params, &arg, sizeof(arg), hash);
}

/**
 * Set an ABI call object argument.
 */
static void remember_call_arg(be_abi_call_arg_t *arg, be_abi_call_t *call, be_abi_context_t context)
{
	unsigned hash = arg->is_res * 128 + arg->pos;
	if (context & ABI_CONTEXT_CALLEE) {
		arg->callee = 1;
		set_insert(call->params, arg, sizeof(*arg), hash);
	}
	if (context & ABI_CONTEXT_CALLER) {
		arg->callee = 0;
		set_insert(call->params, arg, sizeof(*arg), hash);
	}
}

/* Set the flags for a call. */
void be_abi_call_set_flags(be_abi_call_t *call, be_abi_call_flags_t flags, const be_abi_callbacks_t *cb)
{
	call->flags = flags;
	call->cb    = cb;
}

/* Sets the number of bytes the stackframe is shrinked by the callee on return */
void be_abi_call_set_pop(be_abi_call_t *call, int pop)
{
	assert(pop >= 0);
	call->pop = pop;
}

/* Set register class for call address */
void be_abi_call_set_call_address_reg_class(be_abi_call_t *call, const arch_register_class_t *cls)
{
	call->cls_addr = cls;
}


void be_abi_call_param_stack(be_abi_call_t *call, int arg_pos,
                             ir_mode *load_mode, unsigned alignment,
                             unsigned space_before, unsigned space_after,
                             be_abi_context_t context)
{
	be_abi_call_arg_t arg;
	memset(&arg, 0, sizeof(arg));
	assert(alignment > 0 && "Alignment must be greater than 0");
	arg.on_stack     = 1;
	arg.load_mode    = load_mode;
	arg.alignment    = alignment;
	arg.space_before = space_before;
	arg.space_after  = space_after;
	arg.is_res       = 0;
	arg.pos          = arg_pos;

	remember_call_arg(&arg, call, context);
}

void be_abi_call_param_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg, be_abi_context_t context)
{
	be_abi_call_arg_t arg;
	memset(&arg, 0, sizeof(arg));

	arg.in_reg = 1;
	arg.reg    = reg;
	arg.is_res = 0;
	arg.pos    = arg_pos;

	remember_call_arg(&arg, call, context);
}

void be_abi_call_res_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg, be_abi_context_t context)
{
	be_abi_call_arg_t arg;
	memset(&arg, 0, sizeof(arg));

	arg.in_reg = 1;
	arg.reg    = reg;
	arg.is_res = 1;
	arg.pos    = arg_pos;

	remember_call_arg(&arg, call, context);
}

/* Get the flags of a ABI call object. */
be_abi_call_flags_t be_abi_call_get_flags(const be_abi_call_t *call)
{
	return call->flags;
}

/**
 * Constructor for a new ABI call object.
 *
 * @param cls_addr  register class of the call address
 *
 * @return the new ABI call object
 */
static be_abi_call_t *be_abi_call_new(const arch_register_class_t *cls_addr)
{
	be_abi_call_t *call = XMALLOCZ(be_abi_call_t);

	call->flags.val  = 0;
	call->params     = new_set(cmp_call_arg, 16);
	call->cb         = NULL;
	call->cls_addr   = cls_addr;

	call->flags.bits.try_omit_fp = be_omit_fp | be_omit_leaf_fp;

	return call;
}

/**
 * Destructor for an ABI call object.
 */
static void be_abi_call_free(be_abi_call_t *call)
{
	del_set(call->params);
	free(call);
}

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

  Handling of the stack frame. It is composed of three types:
  1) The type of the arguments which are pushed on the stack.
  2) The "between type" which consists of stuff the call of the
     function pushes on the stack (like the return address and
	 the old base pointer for ia32).
  3) The Firm frame type which consists of all local variables
     and the spills.
*/

int be_get_stack_entity_offset(be_stack_layout_t *frame, ir_entity *ent,
                               int bias)
{
	ir_type *t = get_entity_owner(ent);
	int ofs    = get_entity_offset(ent);

	int index;

	/* Find the type the entity is contained in. */
	for (index = 0; index < N_FRAME_TYPES; ++index) {
		if (frame->order[index] == t)
			break;
		/* Add the size of all the types below the one of the entity to the entity's offset */
		ofs += get_type_size_bytes(frame->order[index]);
	}

	/* correct the offset by the initial position of the frame pointer */
	ofs -= frame->initial_offset;

	/* correct the offset with the current bias. */
	ofs += bias;

	return ofs;
}

/**
 * Retrieve the entity with given offset from a frame type.
 */
static ir_entity *search_ent_with_offset(ir_type *t, int offset)
{
	int i, n;

	for (i = 0, n = get_compound_n_members(t); i < n; ++i) {
		ir_entity *ent = get_compound_member(t, i);
		if (get_entity_offset(ent) == offset)
			return ent;
	}

	return NULL;
}

static int stack_frame_compute_initial_offset(be_stack_layout_t *frame)
{
	ir_type  *base = frame->stack_dir < 0 ? frame->between_type : frame->frame_type;
	ir_entity *ent = search_ent_with_offset(base, 0);

	if (ent == NULL) {
		frame->initial_offset
			= frame->stack_dir < 0 ? get_type_size_bytes(frame->frame_type) : get_type_size_bytes(frame->between_type);
	} else {
		frame->initial_offset = be_get_stack_entity_offset(frame, ent, 0);
	}

	return frame->initial_offset;
}

/**
 * Initializes the frame layout from parts
 *
 * @param frame     the stack layout that will be initialized
 * @param args      the stack argument layout type
 * @param between   the between layout type
 * @param locals    the method frame type
 * @param stack_dir the stack direction: < 0 decreasing, > 0 increasing addresses
 * @param param_map an array mapping method argument positions to the stack argument type
 *
 * @return the initialized stack layout
 */
static be_stack_layout_t *stack_frame_init(be_stack_layout_t *frame, ir_type *args,
                                           ir_type *between, ir_type *locals, int stack_dir,
                                           ir_entity *param_map[])
{
	frame->arg_type       = args;
	frame->between_type   = between;
	frame->frame_type     = locals;
	frame->initial_offset = 0;
	frame->initial_bias   = 0;
	frame->stack_dir      = stack_dir;
	frame->order[1]       = between;
	frame->param_map      = param_map;

	if (stack_dir > 0) {
		frame->order[0] = args;
		frame->order[2] = locals;
	} else {
		/* typical decreasing stack: locals have the
		 * lowest addresses, arguments the highest */
		frame->order[0] = locals;
		frame->order[2] = args;
	}
	return frame;
}

/*
   ____      _ _
  / ___|__ _| | |___
 | |   / _` | | / __|
 | |__| (_| | | \__ \
  \____\__,_|_|_|___/

  Adjustment of the calls inside a graph.

*/

/**
 * Transform a call node into a be_Call node.
 *
 * @param env The ABI environment for the current irg.
 * @param irn The call node.
 * @param curr_sp The stack pointer node to use.
 * @return The stack pointer after the call.
 */
static ir_node *adjust_call(be_abi_irg_t *env, ir_node *irn, ir_node *curr_sp)
{
	ir_graph *irg              = get_irn_irg(irn);
	const arch_env_t *arch_env = be_get_irg_arch_env(irg);
	ir_type *call_tp           = get_Call_type(irn);
	ir_node *call_ptr          = get_Call_ptr(irn);
	int n_params               = get_method_n_params(call_tp);
	ir_node *curr_mem          = get_Call_mem(irn);
	ir_node *bl                = get_nodes_block(irn);
	int stack_size             = 0;
	int stack_dir              = arch_env->stack_dir;
	const arch_register_t *sp  = arch_env->sp;
	be_abi_call_t *call        = be_abi_call_new(sp->reg_class);
	ir_mode *mach_mode         = sp->reg_class->mode;
	int no_alloc               = call->flags.bits.frame_is_setup_on_call;
	int n_res                  = get_method_n_ress(call_tp);
	int do_seq                 = call->flags.bits.store_args_sequential && !no_alloc;

	ir_node *res_proj  = NULL;
	int n_reg_params   = 0;
	int n_stack_params = 0;
	int n_ins;

	const arch_register_t **states = NEW_ARR_F(const arch_register_t*, 0);
	const arch_register_t **destroyed_regs = NEW_ARR_F(const arch_register_t*, 0);
	ir_node                *low_call;
	ir_node               **in;
	ir_node               **res_projs;
	int                     n_reg_results = 0;
	const ir_edge_t        *edge;
	int                    *reg_param_idxs;
	int                    *stack_param_idx;
	int                     i, n, destroy_all_regs;
	dbg_info               *dbgi;

	/* Let the isa fill out the abi description for that call node. */
	arch_env_get_call_abi(arch_env, call_tp, call);

	/* Insert code to put the stack arguments on the stack. */
	assert(get_Call_n_params(irn) == n_params);
	stack_param_idx = ALLOCAN(int, n_params);
	for (i = 0; i < n_params; ++i) {
		be_abi_call_arg_t *arg = get_call_arg(call, 0, i, 0);
		assert(arg);
		if (arg->on_stack) {
			int arg_size = get_type_size_bytes(get_method_param_type(call_tp, i));

			stack_size += round_up2(arg->space_before, arg->alignment);
			stack_size += round_up2(arg_size, arg->alignment);
			stack_size += round_up2(arg->space_after, arg->alignment);

			stack_param_idx[n_stack_params++] = i;
		}
	}

	/* Collect all arguments which are passed in registers. */
	reg_param_idxs = ALLOCAN(int, n_params);
	for (i = 0; i < n_params; ++i) {
		be_abi_call_arg_t *arg = get_call_arg(call, 0, i, 0);
		if (arg && arg->in_reg) {
			reg_param_idxs[n_reg_params++] = i;
		}
	}

	/*
	 * If the stack is decreasing and we do not want to store sequentially,
	 * or someone else allocated the call frame
	 * we allocate as much space on the stack all parameters need, by
	 * moving the stack pointer along the stack's direction.
	 *
	 * Note: we also have to do this for stack_size == 0, because we may have
	 * to adjust stack alignment for the call.
	 */
	if (stack_dir < 0 && !do_seq && !no_alloc) {
		curr_sp = be_new_IncSP(sp, bl, curr_sp, stack_size, 1);
	}

	dbgi = get_irn_dbg_info(irn);
	/* If there are some parameters which shall be passed on the stack. */
	if (n_stack_params > 0) {
		int       curr_ofs = 0;
		ir_node **in       = ALLOCAN(ir_node*, n_stack_params+1);
		unsigned  n_in     = 0;

		/*
		 * Reverse list of stack parameters if call arguments are from left to right.
		 * We must them reverse again if they are pushed (not stored) and the stack
		 * direction is downwards.
		 */
		if (call->flags.bits.left_to_right ^ (do_seq && stack_dir < 0)) {
			for (i = 0; i < n_stack_params >> 1; ++i) {
				int other  = n_stack_params - i - 1;
				int tmp    = stack_param_idx[i];
				stack_param_idx[i]     = stack_param_idx[other];
				stack_param_idx[other] = tmp;
			}
		}

		curr_mem = get_Call_mem(irn);
		if (! do_seq) {
			in[n_in++] = curr_mem;
		}

		for (i = 0; i < n_stack_params; ++i) {
			int p                  = stack_param_idx[i];
			be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
			ir_node *param         = get_Call_param(irn, p);
			ir_node *addr          = curr_sp;
			ir_node *mem           = NULL;
			ir_type *param_type    = get_method_param_type(call_tp, p);
			int param_size         = get_type_size_bytes(param_type) + arg->space_after;

			/*
			 * If we wanted to build the arguments sequentially,
			 * the stack pointer for the next must be incremented,
			 * and the memory value propagated.
			 */
			if (do_seq) {
				curr_ofs = 0;
				addr = curr_sp = be_new_IncSP(sp, bl, curr_sp,
				                              param_size + arg->space_before, 0);
				add_irn_dep(curr_sp, curr_mem);
			} else {
				curr_ofs += arg->space_before;
				curr_ofs =  round_up2(curr_ofs, arg->alignment);

				/* Make the expression to compute the argument's offset. */
				if (curr_ofs > 0) {
					ir_mode *constmode = mach_mode;
					if (mode_is_reference(mach_mode)) {
						constmode = mode_Is;
					}
					addr = new_r_Const_long(irg, constmode, curr_ofs);
					addr = new_r_Add(bl, curr_sp, addr, mach_mode);
				}
			}

			/* Insert a store for primitive arguments. */
			if (is_atomic_type(param_type)) {
				ir_node *store;
				ir_node *mem_input = do_seq ? curr_mem : new_NoMem();
				store = new_rd_Store(dbgi, bl, mem_input, addr, param, 0);
				mem   = new_r_Proj(store, mode_M, pn_Store_M);
			} else {
				/* Make a mem copy for compound arguments. */
				ir_node *copy;

				assert(mode_is_reference(get_irn_mode(param)));
				copy = new_rd_CopyB(dbgi, bl, curr_mem, addr, param, param_type);
				mem = new_r_Proj(copy, mode_M, pn_CopyB_M);
			}

			curr_ofs += param_size;

			if (do_seq)
				curr_mem = mem;
			else
				in[n_in++] = mem;
		}

		/* We need the sync only, if we didn't build the stores sequentially. */
		if (! do_seq) {
			if (n_stack_params >= 1) {
				curr_mem = new_r_Sync(bl, n_in, in);
			} else {
				curr_mem = get_Call_mem(irn);
			}
		}
	}

	/* check for the return_twice property */
	destroy_all_regs = 0;
	if (is_SymConst_addr_ent(call_ptr)) {
		ir_entity *ent = get_SymConst_entity(call_ptr);

		if (get_entity_additional_properties(ent) & mtp_property_returns_twice)
			destroy_all_regs = 1;
	} else {
		ir_type *call_tp = get_Call_type(irn);

		if (get_method_additional_properties(call_tp) & mtp_property_returns_twice)
			destroy_all_regs = 1;
	}

	/* Put caller save into the destroyed set and state registers in the states
	 * set */
	for (i = 0, n = arch_env_get_n_reg_class(arch_env); i < n; ++i) {
		unsigned j;
		const arch_register_class_t *cls = arch_env_get_reg_class(arch_env, i);
		for (j = 0; j < cls->n_regs; ++j) {
			const arch_register_t *reg = arch_register_for_index(cls, j);

			/* even if destroyed all is specified, neither SP nor FP are
			 * destroyed (else bad things will happen) */
			if (reg == arch_env->sp || reg == arch_env->bp)
				continue;

			if (arch_register_type_is(reg, state)) {
				ARR_APP1(const arch_register_t*, destroyed_regs, reg);
				ARR_APP1(const arch_register_t*, states, reg);
				/* we're already in the destroyed set so no need for further
				 * checking */
				continue;
			}
			if (destroy_all_regs || arch_register_type_is(reg, caller_save)) {
				if (! arch_register_type_is(reg, ignore)) {
					ARR_APP1(const arch_register_t*, destroyed_regs, reg);
				}
			}
		}
	}

	/* search the largest result proj number */
	res_projs = ALLOCANZ(ir_node*, n_res);

	foreach_out_edge(irn, edge) {
		const ir_edge_t *res_edge;
		ir_node         *irn = get_edge_src_irn(edge);

		if (!is_Proj(irn) || get_Proj_proj(irn) != pn_Call_T_result)
			continue;

		foreach_out_edge(irn, res_edge) {
			int proj;
			ir_node *res = get_edge_src_irn(res_edge);

			assert(is_Proj(res));

			proj = get_Proj_proj(res);
			assert(proj < n_res);
			assert(res_projs[proj] == NULL);
			res_projs[proj] = res;
		}
		res_proj = irn;
		break;
	}

	/** TODO: this is not correct for cases where return values are passed
	 * on the stack, but no known ABI does this currently...
	 */
	n_reg_results = n_res;

	n_ins = 0;
	in    = ALLOCAN(ir_node*, n_reg_params + ARR_LEN(states));

	/* make the back end call node and set its register requirements. */
	for (i = 0; i < n_reg_params; ++i) {
		in[n_ins++] = get_Call_param(irn, reg_param_idxs[i]);
	}

	/* add state registers ins */
	for (i = 0; i < ARR_LEN(states); ++i) {
		const arch_register_t       *reg = states[i];
		const arch_register_class_t *cls = arch_register_get_class(reg);
#if 0
		ir_node *regnode = be_abi_reg_map_get(env->regs, reg);
		ir_fprintf(stderr, "Adding %+F\n", regnode);
#endif
		ir_node *regnode = new_r_Unknown(irg, arch_register_class_mode(cls));
		in[n_ins++]      = regnode;
	}
	assert(n_ins == (int) (n_reg_params + ARR_LEN(states)));

	/* ins collected, build the call */
	if (env->call->flags.bits.call_has_imm && is_SymConst(call_ptr)) {
		/* direct call */
		low_call = be_new_Call(dbgi, irg, bl, curr_mem, curr_sp, curr_sp,
		                       n_reg_results + pn_be_Call_first_res + ARR_LEN(destroyed_regs),
		                       n_ins, in, get_Call_type(irn));
		be_Call_set_entity(low_call, get_SymConst_entity(call_ptr));
	} else {
		/* indirect call */
		low_call = be_new_Call(dbgi, irg, bl, curr_mem, curr_sp, call_ptr,
		                       n_reg_results + pn_be_Call_first_res + ARR_LEN(destroyed_regs),
		                       n_ins, in, get_Call_type(irn));
	}
	be_Call_set_pop(low_call, call->pop);

	/* put the call into the list of all calls for later processing */
	ARR_APP1(ir_node *, env->calls, low_call);

	/* create new stack pointer */
	curr_sp = new_r_Proj(low_call, get_irn_mode(curr_sp), pn_be_Call_sp);
	be_set_constr_single_reg_out(low_call, pn_be_Call_sp, sp,
			arch_register_req_type_ignore | arch_register_req_type_produces_sp);
	arch_set_irn_register(curr_sp, sp);

	/* now handle results */
	for (i = 0; i < n_res; ++i) {
		int pn;
		ir_node           *proj = res_projs[i];
		be_abi_call_arg_t *arg  = get_call_arg(call, 1, i, 0);

		/* returns values on stack not supported yet */
		assert(arg->in_reg);

		/*
			shift the proj number to the right, since we will drop the
			unspeakable Proj_T from the Call. Therefore, all real argument
			Proj numbers must be increased by pn_be_Call_first_res
		*/
		pn = i + pn_be_Call_first_res;

		if (proj == NULL) {
			ir_type *res_type = get_method_res_type(call_tp, i);
			ir_mode *mode     = get_type_mode(res_type);
			proj              = new_r_Proj(low_call, mode, pn);
			res_projs[i]      = proj;
		} else {
			set_Proj_pred(proj, low_call);
			set_Proj_proj(proj, pn);
		}

		if (arg->in_reg) {
			/* remove register from destroyed regs */
			int j;
			int n = ARR_LEN(destroyed_regs);
			for (j = 0; j < n; ++j) {
				if (destroyed_regs[j] == arg->reg) {
					destroyed_regs[j] = destroyed_regs[n-1];
					ARR_SHRINKLEN(destroyed_regs,n-1);
					break;
				}
			}
		}
	}

	/*
		Set the register class of the call address to
		the backend provided class (default: stack pointer class)
	*/
	be_node_set_reg_class_in(low_call, be_pos_Call_ptr, call->cls_addr);

	DBG((dbg, LEVEL_3, "\tcreated backend call %+F\n", low_call));

	/* Set the register classes and constraints of the Call parameters. */
	for (i = 0; i < n_reg_params; ++i) {
		int index = reg_param_idxs[i];
		be_abi_call_arg_t *arg = get_call_arg(call, 0, index, 0);
		assert(arg->reg != NULL);

		be_set_constr_single_reg_in(low_call, be_pos_Call_first_arg + i,
		                            arg->reg, 0);
	}

	/* Set the register constraints of the results. */
	for (i = 0; i < n_res; ++i) {
		ir_node                 *proj = res_projs[i];
		const be_abi_call_arg_t *arg  = get_call_arg(call, 1, i, 0);
		int                      pn   = get_Proj_proj(proj);

		assert(arg->in_reg);
		be_set_constr_single_reg_out(low_call, pn, arg->reg, 0);
		arch_set_irn_register(proj, arg->reg);
	}
	exchange(irn, low_call);

	/* kill the ProjT node */
	if (res_proj != NULL) {
		kill_node(res_proj);
	}

	/* Make additional projs for the caller save registers
	   and the Keep node which keeps them alive. */
	{
		ir_node               **in, *keep;
		int                   i;
		int                   n = 0;
		int                   curr_res_proj = pn_be_Call_first_res + n_reg_results;
		int                   n_ins;

		n_ins = ARR_LEN(destroyed_regs) + n_reg_results + 1;
		in    = ALLOCAN(ir_node *, n_ins);

		/* also keep the stack pointer */
		set_irn_link(curr_sp, (void*) sp);
		in[n++] = curr_sp;

		for (i = 0; i < ARR_LEN(destroyed_regs); ++i) {
			const arch_register_t *reg = destroyed_regs[i];
			ir_node *proj = new_r_Proj(low_call, reg->reg_class->mode, curr_res_proj);

			/* memorize the register in the link field. we need afterwards to set the register class of the keep correctly. */
			be_set_constr_single_reg_out(low_call, curr_res_proj, reg, 0);
			arch_set_irn_register(proj, reg);

			set_irn_link(proj, (void*) reg);
			in[n++] = proj;
			++curr_res_proj;
		}

		for (i = 0; i < n_reg_results; ++i) {
			ir_node *proj = res_projs[i];
			const arch_register_t *reg = arch_get_irn_register(proj);
			set_irn_link(proj, (void*) reg);
			in[n++] = proj;
		}
		assert(n <= n_ins);

		/* create the Keep for the caller save registers */
		keep = be_new_Keep(bl, n, in);
		for (i = 0; i < n; ++i) {
			const arch_register_t *reg = get_irn_link(in[i]);
			be_node_set_reg_class_in(keep, i, reg->reg_class);
		}
	}

	/* Clean up the stack. */
	assert(stack_size >= call->pop);
	stack_size -= call->pop;

	if (stack_size > 0) {
		ir_node *mem_proj = NULL;

		foreach_out_edge(low_call, edge) {
			ir_node *irn = get_edge_src_irn(edge);
			if (is_Proj(irn) && get_Proj_proj(irn) == pn_Call_M) {
				mem_proj = irn;
				break;
			}
		}

		if (! mem_proj) {
			mem_proj = new_r_Proj(low_call, mode_M, pn_be_Call_M_regular);
			keep_alive(mem_proj);
		}
	}
	/* Clean up the stack frame or revert alignment fixes if we allocated it */
	if (! no_alloc) {
		curr_sp = be_new_IncSP(sp, bl, curr_sp, -stack_size, 0);
	}

	be_abi_call_free(call);

	DEL_ARR_F(states);
	DEL_ARR_F(destroyed_regs);

	return curr_sp;
}

/**
 * Adjust the size of a node representing a stack alloc or free for the minimum stack alignment.
 *
 * @param alignment  the minimum stack alignment
 * @param size       the node containing the non-aligned size
 * @param block      the block where new nodes are allocated on
 * @param dbg        debug info for new nodes
 *
 * @return a node representing the aligned size
 */
static ir_node *adjust_alloc_size(unsigned stack_alignment, ir_node *size,
                                  ir_node *block, dbg_info *dbg)
{
	if (stack_alignment > 1) {
		ir_mode  *mode;
		tarval   *tv;
		ir_node  *mask;
		ir_graph *irg;

		assert(is_po2(stack_alignment));

		mode = get_irn_mode(size);
		tv   = new_tarval_from_long(stack_alignment-1, mode);
		irg  = get_Block_irg(block);
		mask = new_r_Const(irg, tv);
		size = new_rd_Add(dbg, block, size, mask, mode);

		tv   = new_tarval_from_long(-(long)stack_alignment, mode);
		mask = new_r_Const(irg, tv);
		size = new_rd_And(dbg, block, size, mask, mode);
	}
	return size;
}
/**
 * Adjust an alloca.
 * The alloca is transformed into a back end alloca node and connected to the stack nodes.
 */
static ir_node *adjust_alloc(be_abi_irg_t *env, ir_node *alloc, ir_node *curr_sp)
{
	ir_node          *block     = get_nodes_block(alloc);
	ir_graph         *irg       = get_Block_irg(block);