beabi.c

/*
 * Copyright (C) 1995-2011 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 "heights.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. */

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

static ir_heights_t *ir_heights;

/** Flag: if set, try to omit the frame pointer in all routines. */
static int be_omit_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 = (const be_abi_call_arg_t*)a;
	const be_abi_call_arg_t *q = (const be_abi_call_arg_t*)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 (be_abi_call_arg_t*)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;

	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);
}

/**
 * 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 *mem_input = do_seq ? curr_mem : new_r_NoMem(irg);
				ir_node *store     = new_rd_Store(dbgi, bl, mem_input, addr, param, cons_none);
				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->n_register_classes; i < n; ++i) {
		unsigned j;
		const arch_register_class_t *cls = &arch_env->register_classes[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 (reg->type & arch_register_type_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 || (reg->type & arch_register_type_caller_save)) {
				if (!(reg->type & arch_register_type_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 */
			size_t j;
			size_t 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, arch_register_req_type_none);
	}

	/* 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,
		                             arch_register_req_type_none);
		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,
			                             arch_register_req_type_none);
			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 = (const arch_register_t*)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;
		ir_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);
	const arch_env_t *arch_env  = be_get_irg_arch_env(irg);
	ir_node          *alloc_mem = NULL;
	ir_node          *alloc_res = NULL;
	ir_type          *type      = get_Alloc_type(alloc);
	dbg_info         *dbg;

	const ir_edge_t *edge;
	ir_node *new_alloc;
	ir_node *count;
	ir_node *size;
	ir_node *ins[2];
	unsigned stack_alignment;

	/* all non-stack Alloc nodes should already be lowered before the backend */
	assert(get_Alloc_where(alloc) == stack_alloc);

	foreach_out_edge(alloc, edge) {
		ir_node *irn = get_edge_src_irn(edge);

		assert(is_Proj(irn));
		switch (get_Proj_proj(irn)) {
		case pn_Alloc_M:
			alloc_mem = irn;
			break;
		case pn_Alloc_res:
			alloc_res = irn;
			break;
		default:
			break;
		}
	}

	/* Beware: currently Alloc nodes without a result might happen,
	   only escape analysis kills them and this phase runs only for object
	   oriented source. We kill the Alloc here. */
	if (alloc_res == NULL && alloc_mem) {
		exchange(alloc_mem, get_Alloc_mem(alloc));
		return curr_sp;
	}

	dbg   = get_irn_dbg_info(alloc);
	count = get_Alloc_count(alloc);

	/* we might need to multiply the count with the element size */
	if (type != firm_unknown_type && get_type_size_bytes(type) != 1) {
		ir_mode   *mode  = get_irn_mode(count);
		ir_tarval *tv    = new_tarval_from_long(get_type_size_bytes(type),
		                                        mode);
		ir_node   *cnst = new_rd_Const(dbg, irg, tv);
		size            = new_rd_Mul(dbg, block, count, cnst, mode);
	} else {
		size = count;
	}