<commit_before>/*
 * Copyright (C) 1995-2007 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      <NAME>, <NAME>
 * @version     $Id$
 */
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif

#include "obst.h"
#include "offset.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 "height.h"
#include "pdeq.h"
#include "irtools.h"
#include "raw_bitset.h"
#include "error.h"

#include "be.h"
#include "beabi.h"
#include "bearch_t.h"
#include "benode_t.h"
#include "belive_t.h"
#include "besched_t.h"
#include "beirg_t.h"
#include "bessaconstr.h"

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. */

	int pos;
	const arch_register_t *reg;
	ir_entity *stack_ent;
	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;
	const be_abi_callbacks_t    *cb;
	ir_type                     *between_type;
	set                         *params;
	const arch_register_class_t *cls_addr;
};

struct _be_abi_irg_t {
	struct obstack       obst;
	be_stack_layout_t    *frame;        /**< The stack frame model. */
	be_irg_t             *birg;         /**< The back end IRG. */
	const arch_isa_t     *isa;          /**< The isa. */
	survive_dce_t        *dce_survivor;

	be_abi_call_t        *call;         /**< The ABI call information. */
	ir_type              *method_type;  /**< The type of the method of the IRG. */

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

	ir_node              *reg_params;   /**< The reg 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;
	arch_register_req_t sp_cls_req;

	DEBUG_ONLY(firm_dbg_module_t    *dbg;)          /**< The debugging module. */
};

static heights_t *ir_heights;

/* Flag: if set, try to omit the frame pointer if called by the backend */
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 = a, *q = b;
	(void) n;
	return !(p->is_res == q->is_res && p->pos == q->pos);
}

/**
 * Get or set 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 do_insert true if the argument is set, false if it's retrieved
 */
static be_abi_call_arg_t *get_or_set_call_arg(be_abi_call_t *call, int is_res, int pos, int do_insert)
{
	be_abi_call_arg_t arg;
	unsigned hash;

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

	hash = is_res * 128 + pos;

	return do_insert
		? set_insert(call->params, &arg, sizeof(arg), hash)
		: set_find(call->params, &arg, sizeof(arg), hash);
}

/**
 * Retrieve an ABI call object argument.
 *
 * @param call      the ABI call object
 * @param is_res    true for call results, false for call arguments
 * @param pos       position of the argument
 */
static INLINE be_abi_call_arg_t *get_call_arg(be_abi_call_t *call, int is_res, int pos)
{
	return get_or_set_call_arg(call, is_res, pos, 0);
}

/* 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;
}


/* 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, unsigned alignment, unsigned space_before, unsigned space_after)
{
	be_abi_call_arg_t *arg = get_or_set_call_arg(call, 0, arg_pos, 1);
	arg->on_stack     = 1;
	arg->alignment    = alignment;
	arg->space_before = space_before;
	arg->space_after  = space_after;
	assert(alignment > 0 && "Alignment must be greater than 0");
}

void be_abi_call_param_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
{
	be_abi_call_arg_t *arg = get_or_set_call_arg(call, 0, arg_pos, 1);
	arg->in_reg = 1;
	arg->reg = reg;
}

void be_abi_call_res_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
{
	be_abi_call_arg_t *arg = get_or_set_call_arg(call, 1, arg_pos, 1);
	arg->in_reg = 1;
	arg->reg = reg;
}

/* 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.
 *
 * @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 = xmalloc(sizeof(call[0]));

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

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

  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.
*/

static int 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 i, 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 */
	for(i = 0; i < index; ++i)
		ofs += get_type_size_bytes(frame->order[i]);

	/* 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);

	frame->initial_offset = ent ? get_stack_entity_offset(frame, ent, 0) : 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
 * @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->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 {
		frame->order[0] = locals;
		frame->order[2] = args;
	}
	return frame;
}

#if 0
/** Dumps the stack layout to file. */
static void stack_layout_dump(FILE *file, be_stack_layout_t *frame)
{
	int i, j, n;

	ir_fprintf(file, "initial offset: %d\n", frame->initial_offset);
	for (j = 0; j < N_FRAME_TYPES; ++j) {
		ir_type *t = frame->order[j];

		ir_fprintf(file, "type %d: %F size: %d\n", j, t, get_type_size_bytes(t));
		for (i = 0, n = get_compound_n_members(t); i < n; ++i) {
			ir_entity *ent = get_compound_member(t, i);
			ir_fprintf(file, "\t%F int ofs: %d glob ofs: %d\n", ent, get_entity_offset_bytes(ent), get_stack_entity_offset(frame, ent, 0));
		}
	}
}
#endif

/**
 * Returns non-zero if the call argument at given position
 * is transfered on the stack.
 */
static INLINE int is_on_stack(be_abi_call_t *call, int pos)
{
	be_abi_call_arg_t *arg = get_call_arg(call, 0, pos);
	return arg && !arg->in_reg;
}

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

  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              = env->birg->irg;
	const arch_env_t *arch_env = env->birg->main_env->arch_env;
	const arch_isa_t *isa      = arch_env->isa;
	ir_type *mt                = get_Call_type(irn);
	ir_node *call_ptr          = get_Call_ptr(irn);
	int n_params               = get_method_n_params(mt);
	ir_node *curr_mem          = get_Call_mem(irn);
	ir_node *bl                = get_nodes_block(irn);
	pset *results              = pset_new_ptr(8);
	pset *caller_save          = pset_new_ptr(8);
	pset *states               = pset_new_ptr(2);
	int stack_size             = 0;
	int stack_dir              = arch_isa_stack_dir(isa);
	const arch_register_t *sp  = arch_isa_sp(isa);
	be_abi_call_t *call        = be_abi_call_new(sp->reg_class);
	ir_mode *mach_mode         = sp->reg_class->mode;
	struct obstack *obst       = &env->obst;
	int no_alloc               = call->flags.bits.frame_is_setup_on_call;
	int n_res                  = get_method_n_ress(mt);

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

	ir_node *low_call;
	ir_node **in;
	ir_node **res_projs;
	int      n_reg_results = 0;
	const arch_register_t *reg;
	const ir_edge_t *edge;
	int *reg_param_idxs;
	int *stack_param_idx;
	int i, n;

	/* Let the isa fill out the abi description for that call node. */
	arch_isa_get_call_abi(isa, mt, call);

	/* Insert code to put the stack arguments on the stack. */
	assert(get_Call_n_params(irn) == n_params);
	for (i = 0; i < n_params; ++i) {
		be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
		assert(arg);
		if (arg->on_stack) {
			int arg_size = get_type_size_bytes(get_method_param_type(mt, 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);
			obstack_int_grow(obst, i);
			++n_stack_params;
		}
	}
	stack_param_idx = obstack_finish(obst);

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

	/* If there are some parameters which shall be passed on the stack. */
	if (n_stack_params > 0) {
		int curr_ofs      = 0;
		int do_seq        = call->flags.bits.store_args_sequential && !no_alloc;

		/*
		 * 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;
			}
		}

		/*
		 * 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.
		 */
		if (stack_dir < 0 && !do_seq && !no_alloc) {
			curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, stack_size);
		}

		curr_mem = get_Call_mem(irn);
		if (! do_seq) {
			obstack_ptr_grow(obst, 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);
			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(mt, 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, irg, bl, curr_sp, param_size + arg->space_before);
				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, bl, constmode, curr_ofs);
					addr = new_r_Add(irg, 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_r_Store(irg, bl, mem_input, addr, param);
				mem = new_r_Proj(irg, bl, store, mode_M, pn_Store_M);
			}

			/* Make a mem copy for compound arguments. */
			else {
				ir_node *copy;

				assert(mode_is_reference(get_irn_mode(param)));
				copy = new_r_CopyB(irg, bl, curr_mem, addr, param, param_type);
				mem = new_r_Proj(irg, bl, copy, mode_M, pn_CopyB_M_regular);
			}

			curr_ofs += param_size;

			if (do_seq)
				curr_mem = mem;
			else
				obstack_ptr_grow(obst, mem);
		}

		in = (ir_node **) obstack_finish(obst);

		/* 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(irg, bl, n_stack_params + 1, in);
			} else {
				curr_mem = get_Call_mem(irn);
			}
		}
		obstack_free(obst, in);
	}

	/* Collect caller save registers */
	for (i = 0, n = arch_isa_get_n_reg_class(isa); i < n; ++i) {
		unsigned j;
		const arch_register_class_t *cls = arch_isa_get_reg_class(isa, i);
		for (j = 0; j < cls->n_regs; ++j) {
			const arch_register_t *reg = arch_register_for_index(cls, j);
			if (arch_register_type_is(reg, caller_save)) {
				pset_insert_ptr(caller_save, (void *) reg);
			}
			if (arch_register_type_is(reg, state)) {
				pset_insert_ptr(caller_save, (void*) reg);
				pset_insert_ptr(states, (void*) reg);
			}
		}
	}

	/* search the greatest result proj number */

	res_projs = alloca(n_res * sizeof(res_projs[0]));
	memset(res_projs, 0, n_res * sizeof(res_projs[0]));

	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 currentl...
	 */
	n_reg_results = n_res;

	/* make the back end call node and set its register requirements. */
	for (i = 0; i < n_reg_params; ++i) {
		obstack_ptr_grow(obst, get_Call_param(irn, reg_param_idxs[i]));
	}
	foreach_pset(states, reg) {
		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_rd_Unknown(irg, arch_register_class_mode(cls));
		obstack_ptr_grow(obst, regnode);
	}
	n_ins = n_reg_params + pset_count(states);

	in = obstack_finish(obst);

	if (env->call->flags.bits.call_has_imm && is_SymConst(call_ptr)) {
		/* direct call */
		low_call = be_new_Call(get_irn_dbg_info(irn), irg, bl, curr_mem,
		                       curr_sp, curr_sp,
		                       n_reg_results + pn_be_Call_first_res + pset_count(caller_save),
		                       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(get_irn_dbg_info(irn), irg, bl, curr_mem,
		                       curr_sp, call_ptr,
		                       n_reg_results + pn_be_Call_first_res + pset_count(caller_save),
		                       n_ins, in, get_Call_type(irn));
	}
	ARR_APP1(ir_node *, env->calls, low_call);

	/* create new stack pointer */
	curr_sp = new_r_Proj(irg, bl, low_call, get_irn_mode(curr_sp),
	                     pn_be_Call_sp);
	be_set_constr_single_reg(low_call, BE_OUT_POS(pn_be_Call_sp), sp);
	arch_set_irn_register(arch_env, curr_sp, sp);
	be_node_set_flags(low_call, BE_OUT_POS(pn_be_Call_sp),
			arch_irn_flags_ignore | arch_irn_flags_modify_sp);

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

		/* 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(mt, i);
			ir_mode *mode     = get_type_mode(res_type);
			proj              = new_r_Proj(irg, bl, low_call, mode, pn);
			res_projs[i]      = proj;
		} else {
			set_Proj_pred(proj, low_call);
			set_Proj_proj(proj, pn);
		}

		if (arg->in_reg) {
			pset_remove_ptr(caller_save, arg->reg);
		}
	}

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

	DBG((env->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);
		assert(arg->reg != NULL);

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

	/* 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);
		int                      pn   = get_Proj_proj(proj);

		assert(arg->in_reg);
		be_set_constr_single_reg(low_call, BE_OUT_POS(pn), arg->reg);
		arch_set_irn_register(arch_env, proj, arg->reg);
	}
	obstack_free(obst, in);
	exchange(irn, low_call);

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

	/* Make additional projs for the caller save registers
	   and the Keep node which keeps them alive. */
	if (pset_count(caller_save) + n_reg_results > 0) {
		const arch_register_t *reg;
		ir_node               **in, *keep;
		int                   i, n;
		int                   curr_res_proj
			= pn_be_Call_first_res + n_reg_results;

		for (reg = pset_first(caller_save), n = 0; reg; reg = pset_next(caller_save), ++n) {
			ir_node *proj = new_r_Proj(irg, bl, 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(low_call, BE_OUT_POS(curr_res_proj), reg);
			arch_set_irn_register(arch_env, proj, reg);

			/* a call can produce ignore registers, in this case set the flag and register for the Proj */
			if (arch_register_type_is(reg, ignore)) {
				be_node_set_flags(low_call, BE_OUT_POS(curr_res_proj),
				                  arch_irn_flags_ignore);
			}

			set_irn_link(proj, (void*) reg);
			obstack_ptr_grow(obst, 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(arch_env, proj);
			set_irn_link(proj, (void*) reg);
			obstack_ptr_grow(obst, proj);
		}
		n += n_reg_results;

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

	/* Clean up the stack. */
	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(irg, bl, low_call, mode_M, pn_Call_M);
			keep_alive(mem_proj);
		}

		 /* Clean up the stack frame if we allocated it */
		if (! no_alloc) {
			/* the callee pops the shadow parameter */
			if(get_method_calling_convention(mt) & cc_compound_ret) {
				unsigned size = get_mode_size_bytes(mode_P_data);
				stack_size -= size;
				be_Call_set_pop(low_call, size);
			}

			curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, -stack_size);
			//add_irn_dep(curr_sp, mem_proj);
		}
	}

	be_abi_call_free(call);
	obstack_free(obst, stack_param_idx);
	del_pset(results);
	del_pset(states);
	del_pset(caller_save);

	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 irg        the irg where new nodes are allocated on
 * @param irg        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_graph *irg, ir_node *block, dbg_info *dbg)
{
	if (stack_alignment > 1) {
		ir_mode *mode = get_irn_mode(size);
		tarval  *tv   = new_tarval_from_long(stack_alignment-1, mode);
		ir_node *mask = new_r_Const(irg, block, mode, tv);

		size = new_rd_Add(dbg, irg, block, size, mask, mode);

		tv   = new_tarval_from_long(-(long)stack_alignment, mode);
		mask = new_r_Const(irg, block, mode, tv);
		size = new_rd_And(dbg, irg, 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;
	ir_graph *irg;
	ir_node *alloc_mem;
	ir_node *alloc_res;
	ir_type *type;
	dbg_info *dbg;

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

	if (get_Alloc_where(alloc) != stack_alloc) {
		assert(0);
		return alloc;
	}

	block = get_nodes_block(alloc);
	irg = get_irn_irg(block);
	alloc_mem = NULL;
	alloc_res = NULL;
	type = get_Alloc_type(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);

	/* we might need to multiply the size with the element size */
	if(type != get_unknown_type() && get_type_size_bytes(type) != 1) {
		tarval *tv    = new_tarval_from_long(get_type_size_bytes(type),
		                                     mode_Iu);
		ir_node *cnst = new_rd_Const(dbg, irg, block, mode_Iu, tv);
		ir_node *mul  = new_rd_Mul(dbg, irg, block, get_Alloc_size(alloc),
		                           cnst, mode_Iu);
		size = mul;
	} else {
		size = get_Alloc_size(alloc);
	}

	/* The stack pointer will be modified in an unknown manner.
	   We cannot omit it. */
	env->call->flags.bits.try_omit_fp = 0;

	/* FIXME: size must be here round up for the stack alignment, but
	   this must be transmitted from the backend. */
	stack_alignment = 4;
	size            = adjust_alloc_size(stack_alignment, size, irg, block, dbg);
	new_alloc       = be_new_AddSP(env->isa->sp, irg, block, curr_sp, size);
	set_irn_dbg_info(new_alloc, dbg);

	if(alloc_mem != NULL) {
		ir_node *addsp_mem;
		ir_node *sync;

		addsp_mem = new_r_Proj(irg, block, new_alloc, mode_M, pn_be_AddSP_M);

		/* We need to sync the output mem of the AddSP with the input mem
		   edge into the alloc node. */
		ins[0] = get_Alloc_mem(alloc);
		ins[1] = addsp_mem;
		sync = new_r_Sync(irg, block, 2, ins);

		exchange(alloc_mem, sync);
	}

	exchange(alloc, new_alloc);

	/* fix projnum of alloca res */
	set_Proj_proj(alloc_res, pn_be_AddSP_res);

	addr    = alloc_res;
	curr_sp = new_r_Proj(irg, block, new_alloc,  get_irn_mode(curr_sp),
	                     pn_be_AddSP_sp);

	return curr_sp;
}  /* adjust_alloc */

/**
 * Adjust a Free.
 * The Free is transformed into a back end free node and connected to the stack nodes.
 */
static ir_node *adjust_free(be_abi_irg_t *env, ir_node *free, ir_node *curr_sp)
{
	ir_node *block;
	ir_graph *irg;
	ir_node *subsp, *mem, *res, *size, *sync;
	ir_type *type;
	ir_node *in[2];
	ir_mode *sp_mode;
	unsigned stack_alignment;
	dbg_info *dbg;

	if (get_Free_where(free) != stack_alloc) {
		assert(0);
		return free;
	}

	block = get_nodes_block(free);
	irg = get_irn_irg(block);
	type = get_Free_type(free);
	sp_mode = env->isa->sp->reg_class->mode;
	dbg = get_irn_dbg_info(free);

	/* we might need to multiply the size with the element size */
	if(type != get_unknown_type() && get_type_size_bytes(type) != 1) {
		tarval *tv = new_tarval_from_long(get_type_size_bytes(type), mode_Iu);
		ir_node *cnst = new_rd_Const(dbg, irg, block, mode_Iu, tv);
		ir_node *mul = new_rd_Mul(dbg, irg, block, get_Free_size(free),
		                          cnst, mode_Iu);
		size = mul;
	} else {
		size = get_Free_size(free);
	}

	/* FIXME: size must be here round up for the stack alignment, but
	   this must be transmitted from the backend. */
	stack_alignment = 4;
	size = adjust_alloc_size(stack_alignment, size, irg, block, dbg);

	/* The stack pointer will be modified in an unknown manner.
	   We cannot omit it. */
	env->call->flags.bits.try_omit_fp = 0;
	subsp = be_new_SubSP(env->isa->sp, irg, block, curr_sp, size);
	set_irn_dbg_info(subsp, dbg);

	mem = new_r_Proj(irg, block, subsp, mode_M, pn_be_SubSP_M);
	res = new_r_Proj(irg, block, subsp, sp_mode, pn_be_SubSP_sp);

	/* we need to sync the memory */
	in[0] = get_Free_mem(free);
	in[1] = mem;
	sync = new_r_Sync(irg, block, 2, in);

	/* and make the AddSP dependent on the former memory */
	add_irn_dep(subsp, get_Free_mem(free));

	/* kill the free */
	exchange(free, sync);
	curr_sp = res;

	return curr_sp;
}  /* adjust_free */

/* the following function is replaced by the usage of the heights module */
#if 0
/**
 * Walker for dependent_on().
 * This function searches a node tgt recursively from a given node
 * but is restricted to the given block.
 * @return 1 if tgt was reachable from curr, 0 if not.
 */
static int check_dependence(ir_node *curr, ir_node *tgt, ir_node *bl)
{
	int n, i;

	if (get_nodes_block(curr) != bl)
		return 0;

	if (curr == tgt)
		return 1;

	/* Phi functions stop the recursion inside a basic block */
	if (! is_Phi(curr)) {
		for(i = 0, n = get_irn_arity(curr); i < n; ++i) {
			if (check_dependence(get_irn_n(curr, i), tgt, bl))
				return 1;
		}
	}

	return 0;
}
#endif /* if 0 */

/**
 * Check if a node is somehow data dependent on another one.
 * both nodes must be in the same basic block.
 * @param n1 The first node.
 * @param n2 The second node.
 * @return 1, if n1 is data dependent (transitively) on n2, 0 if not.
 */
static int dependent_on(ir_node *n1, ir_node *n2)
{
	assert(get_nodes_block(n1) == get_nodes_block(n2));

	return heights_reachable_in_block(ir_heights, n1, n2);
}

static int cmp_call_dependency(const void *c1, const void *c2)
{
	ir_node *n1 = *(ir_node **) c1;
	ir_node *n2 = *(ir_node **) c2;

	/*
		Classical qsort() comparison function behavior:
		0  if both elements are equal
		1  if second is "smaller" that first
		-1 if first is "smaller" that second
	*/
	if (dependent_on(n1, n2))
		return -1;

	if (dependent_on(n2, n1))
		return 1;

	return 0;
}

/**
 * Walker: links all Call/alloc/Free nodes to the Block they are contained.
 */
static void link_calls_in_block_walker(ir_node *irn, void *data)
{
	ir_opcode code = get_irn_opcode(irn);

	if (code == iro_Call ||
		(code == iro_Alloc && get_Alloc_where(irn) == stack_alloc) ||
		(code == iro_Free && get_Free_where(irn) == stack_alloc)) {
		be_abi_irg_t *env = data;
		ir_node *bl       = get_nodes_block(irn);
		void *save        = get_irn_link(bl);

		if (code == iro_Call)
			env->call->flags.bits.irg_is_leaf = 0;

		set_irn_link(irn, save);
		set_irn_link(bl, irn);
	}
}

/**
 * Block-walker:
 * Process all Call nodes inside a basic block.
 * Note that the link field of the block must contain a linked list of all
 * Call nodes inside the Block. We first order this list according to data dependency
 * and that connect the calls together.
 */
static void process_calls_in_block(ir_node *bl, void *data)
{
	be_abi_irg_t *env = data;
	ir_node *curr_sp  = env->init_sp;
	ir_node *irn;
	int n;

	for(irn = get_irn_link(bl), n = 0; irn; irn = get_irn_link(irn), ++n)
		obstack_ptr_grow(&env->obst, irn);

	/* If there were call nodes in the block. */
	if(n > 0) {
		ir_node *keep;
		ir_node **nodes;
		int i;

		nodes = obstack_finish(&env->obst);

		/* order the call nodes according to data dependency */
		qsort(nodes, n, sizeof(nodes[0]), cmp_call_dependency);

		for(i = n - 1; i >= 0; --i) {
			ir_node *irn = nodes[i];

			DBG((env->dbg, LEVEL_3, "\tprocessing call %+F\n", irn));
			switch(get_irn_opcode(irn)) {
			case iro_Call:
				curr_sp = adjust_call(env, irn, curr_sp);
				break;
			case iro_Alloc:
				curr_sp = adjust_alloc(env, irn, curr_sp);
				break;
			case iro_Free:
				curr_sp = adjust_free(env, irn, curr_sp);
				break;
			default:
				panic("invalid call");
				break;
			}
		}

		obstack_free(&env->obst, nodes);

		/* Keep the last stack state in the block by tying it to Keep node */
		if(curr_sp != env->init_sp) {
			nodes[0] = curr_sp;
			keep     = be_new_Keep(env->isa->sp->reg_class, get_irn_irg(bl),
			                       bl, 1, nodes);
			pmap_insert(env->keep_map, bl, keep);
		}
	}

	set_irn_link(bl, curr_sp);<commit_msg>avoid an extra keep for the Call esp projs<commit_after>/*
 * Copyright (C) 1995-2007 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      <NAME>, <NAME>
 * @version     $Id$
 */
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif

#include "obst.h"
#include "offset.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 "height.h"
#include "pdeq.h"
#include "irtools.h"
#include "raw_bitset.h"
#include "error.h"

#include "be.h"
#include "beabi.h"
#include "bearch_t.h"
#include "benode_t.h"
#include "belive_t.h"
#include "besched_t.h"
#include "beirg_t.h"
#include "bessaconstr.h"

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. */

	int pos;
	const arch_register_t *reg;
	ir_entity *stack_ent;
	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;
	const be_abi_callbacks_t    *cb;
	ir_type                     *between_type;
	set                         *params;
	const arch_register_class_t *cls_addr;
};

struct _be_abi_irg_t {
	struct obstack       obst;
	be_stack_layout_t    *frame;        /**< The stack frame model. */
	be_irg_t             *birg;         /**< The back end IRG. */
	const arch_isa_t     *isa;          /**< The isa. */
	survive_dce_t        *dce_survivor;

	be_abi_call_t        *call;         /**< The ABI call information. */
	ir_type              *method_type;  /**< The type of the method of the IRG. */

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

	ir_node              *reg_params;   /**< The reg 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;
	arch_register_req_t sp_cls_req;

	DEBUG_ONLY(firm_dbg_module_t    *dbg;)          /**< The debugging module. */
};

static heights_t *ir_heights;

/* Flag: if set, try to omit the frame pointer if called by the backend */
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 = a, *q = b;
	(void) n;
	return !(p->is_res == q->is_res && p->pos == q->pos);
}

/**
 * Get or set 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 do_insert true if the argument is set, false if it's retrieved
 */
static be_abi_call_arg_t *get_or_set_call_arg(be_abi_call_t *call, int is_res, int pos, int do_insert)
{
	be_abi_call_arg_t arg;
	unsigned hash;

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

	hash = is_res * 128 + pos;

	return do_insert
		? set_insert(call->params, &arg, sizeof(arg), hash)
		: set_find(call->params, &arg, sizeof(arg), hash);
}

/**
 * Retrieve an ABI call object argument.
 *
 * @param call      the ABI call object
 * @param is_res    true for call results, false for call arguments
 * @param pos       position of the argument
 */
static INLINE be_abi_call_arg_t *get_call_arg(be_abi_call_t *call, int is_res, int pos)
{
	return get_or_set_call_arg(call, is_res, pos, 0);
}

/* 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;
}


/* 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, unsigned alignment, unsigned space_before, unsigned space_after)
{
	be_abi_call_arg_t *arg = get_or_set_call_arg(call, 0, arg_pos, 1);
	arg->on_stack     = 1;
	arg->alignment    = alignment;
	arg->space_before = space_before;
	arg->space_after  = space_after;
	assert(alignment > 0 && "Alignment must be greater than 0");
}

void be_abi_call_param_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
{
	be_abi_call_arg_t *arg = get_or_set_call_arg(call, 0, arg_pos, 1);
	arg->in_reg = 1;
	arg->reg = reg;
}

void be_abi_call_res_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg)
{
	be_abi_call_arg_t *arg = get_or_set_call_arg(call, 1, arg_pos, 1);
	arg->in_reg = 1;
	arg->reg = reg;
}

/* 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.
 *
 * @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 = xmalloc(sizeof(call[0]));

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

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

  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.
*/

static int 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 i, 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 */
	for(i = 0; i < index; ++i)
		ofs += get_type_size_bytes(frame->order[i]);

	/* 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);

	frame->initial_offset = ent ? get_stack_entity_offset(frame, ent, 0) : 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
 * @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->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 {
		frame->order[0] = locals;
		frame->order[2] = args;
	}
	return frame;
}

#if 0
/** Dumps the stack layout to file. */
static void stack_layout_dump(FILE *file, be_stack_layout_t *frame)
{
	int i, j, n;

	ir_fprintf(file, "initial offset: %d\n", frame->initial_offset);
	for (j = 0; j < N_FRAME_TYPES; ++j) {
		ir_type *t = frame->order[j];

		ir_fprintf(file, "type %d: %F size: %d\n", j, t, get_type_size_bytes(t));
		for (i = 0, n = get_compound_n_members(t); i < n; ++i) {
			ir_entity *ent = get_compound_member(t, i);
			ir_fprintf(file, "\t%F int ofs: %d glob ofs: %d\n", ent, get_entity_offset_bytes(ent), get_stack_entity_offset(frame, ent, 0));
		}
	}
}
#endif

/**
 * Returns non-zero if the call argument at given position
 * is transfered on the stack.
 */
static INLINE int is_on_stack(be_abi_call_t *call, int pos)
{
	be_abi_call_arg_t *arg = get_call_arg(call, 0, pos);
	return arg && !arg->in_reg;
}

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

  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              = env->birg->irg;
	const arch_env_t *arch_env = env->birg->main_env->arch_env;
	const arch_isa_t *isa      = arch_env->isa;
	ir_type *mt                = get_Call_type(irn);
	ir_node *call_ptr          = get_Call_ptr(irn);
	int n_params               = get_method_n_params(mt);
	ir_node *curr_mem          = get_Call_mem(irn);
	ir_node *bl                = get_nodes_block(irn);
	pset *results              = pset_new_ptr(8);
	pset *caller_save          = pset_new_ptr(8);
	pset *states               = pset_new_ptr(2);
	int stack_size             = 0;
	int stack_dir              = arch_isa_stack_dir(isa);
	const arch_register_t *sp  = arch_isa_sp(isa);
	be_abi_call_t *call        = be_abi_call_new(sp->reg_class);
	ir_mode *mach_mode         = sp->reg_class->mode;
	struct obstack *obst       = &env->obst;
	int no_alloc               = call->flags.bits.frame_is_setup_on_call;
	int n_res                  = get_method_n_ress(mt);

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

	ir_node *low_call;
	ir_node **in;
	ir_node **res_projs;
	int      n_reg_results = 0;
	const arch_register_t *reg;
	const ir_edge_t *edge;
	int *reg_param_idxs;
	int *stack_param_idx;
	int i, n;

	/* Let the isa fill out the abi description for that call node. */
	arch_isa_get_call_abi(isa, mt, call);

	/* Insert code to put the stack arguments on the stack. */
	assert(get_Call_n_params(irn) == n_params);
	for (i = 0; i < n_params; ++i) {
		be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
		assert(arg);
		if (arg->on_stack) {
			int arg_size = get_type_size_bytes(get_method_param_type(mt, 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);
			obstack_int_grow(obst, i);
			++n_stack_params;
		}
	}
	stack_param_idx = obstack_finish(obst);

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

	/* If there are some parameters which shall be passed on the stack. */
	if (n_stack_params > 0) {
		int curr_ofs      = 0;
		int do_seq        = call->flags.bits.store_args_sequential && !no_alloc;

		/*
		 * 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;
			}
		}

		/*
		 * 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.
		 */
		if (stack_dir < 0 && !do_seq && !no_alloc) {
			curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, stack_size);
		}

		curr_mem = get_Call_mem(irn);
		if (! do_seq) {
			obstack_ptr_grow(obst, 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);
			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(mt, 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, irg, bl, curr_sp, param_size + arg->space_before);
				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, bl, constmode, curr_ofs);
					addr = new_r_Add(irg, 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_r_Store(irg, bl, mem_input, addr, param);
				mem = new_r_Proj(irg, bl, store, mode_M, pn_Store_M);
			}

			/* Make a mem copy for compound arguments. */
			else {
				ir_node *copy;

				assert(mode_is_reference(get_irn_mode(param)));
				copy = new_r_CopyB(irg, bl, curr_mem, addr, param, param_type);
				mem = new_r_Proj(irg, bl, copy, mode_M, pn_CopyB_M_regular);
			}

			curr_ofs += param_size;

			if (do_seq)
				curr_mem = mem;
			else
				obstack_ptr_grow(obst, mem);
		}

		in = (ir_node **) obstack_finish(obst);

		/* 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(irg, bl, n_stack_params + 1, in);
			} else {
				curr_mem = get_Call_mem(irn);
			}
		}
		obstack_free(obst, in);
	}

	/* Collect caller save registers */
	for (i = 0, n = arch_isa_get_n_reg_class(isa); i < n; ++i) {
		unsigned j;
		const arch_register_class_t *cls = arch_isa_get_reg_class(isa, i);
		for (j = 0; j < cls->n_regs; ++j) {
			const arch_register_t *reg = arch_register_for_index(cls, j);
			if (arch_register_type_is(reg, caller_save)) {
				pset_insert_ptr(caller_save, (void *) reg);
			}
			if (arch_register_type_is(reg, state)) {
				pset_insert_ptr(caller_save, (void*) reg);
				pset_insert_ptr(states, (void*) reg);
			}
		}
	}

	/* search the greatest result proj number */

	res_projs = alloca(n_res * sizeof(res_projs[0]));
	memset(res_projs, 0, n_res * sizeof(res_projs[0]));

	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 currentl...
	 */
	n_reg_results = n_res;

	/* make the back end call node and set its register requirements. */
	for (i = 0; i < n_reg_params; ++i) {
		obstack_ptr_grow(obst, get_Call_param(irn, reg_param_idxs[i]));
	}
	foreach_pset(states, reg) {
		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_rd_Unknown(irg, arch_register_class_mode(cls));
		obstack_ptr_grow(obst, regnode);
	}
	n_ins = n_reg_params + pset_count(states);

	in = obstack_finish(obst);

	if (env->call->flags.bits.call_has_imm && is_SymConst(call_ptr)) {
		/* direct call */
		low_call = be_new_Call(get_irn_dbg_info(irn), irg, bl, curr_mem,
		                       curr_sp, curr_sp,
		                       n_reg_results + pn_be_Call_first_res + pset_count(caller_save),
		                       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(get_irn_dbg_info(irn), irg, bl, curr_mem,
		                       curr_sp, call_ptr,
		                       n_reg_results + pn_be_Call_first_res + pset_count(caller_save),
		                       n_ins, in, get_Call_type(irn));
	}
	ARR_APP1(ir_node *, env->calls, low_call);

	/* create new stack pointer */
	curr_sp = new_r_Proj(irg, bl, low_call, get_irn_mode(curr_sp),
	                     pn_be_Call_sp);
	be_set_constr_single_reg(low_call, BE_OUT_POS(pn_be_Call_sp), sp);
	arch_set_irn_register(arch_env, curr_sp, sp);
	be_node_set_flags(low_call, BE_OUT_POS(pn_be_Call_sp),
			arch_irn_flags_ignore | arch_irn_flags_modify_sp);

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

		/* 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(mt, i);
			ir_mode *mode     = get_type_mode(res_type);
			proj              = new_r_Proj(irg, bl, low_call, mode, pn);
			res_projs[i]      = proj;
		} else {
			set_Proj_pred(proj, low_call);
			set_Proj_proj(proj, pn);
		}

		if (arg->in_reg) {
			pset_remove_ptr(caller_save, arg->reg);
		}
	}

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

	DBG((env->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);
		assert(arg->reg != NULL);

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

	/* 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);
		int                      pn   = get_Proj_proj(proj);

		assert(arg->in_reg);
		be_set_constr_single_reg(low_call, BE_OUT_POS(pn), arg->reg);
		arch_set_irn_register(arch_env, proj, arg->reg);
	}
	obstack_free(obst, in);
	exchange(irn, low_call);

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

	/* Make additional projs for the caller save registers
	   and the Keep node which keeps them alive. */
	if (1 || pset_count(caller_save) + n_reg_results > 0) {
		const arch_register_t *reg;
		ir_node               **in, *keep;
		int                   i;
		int                   n = 0;
		int                   curr_res_proj
			= pn_be_Call_first_res + n_reg_results;

		/* also keep the stack pointer */
		++n;
		set_irn_link(curr_sp, (void*) sp);
		obstack_ptr_grow(obst, curr_sp);

		for (reg = pset_first(caller_save); reg; reg = pset_next(caller_save), ++n) {
			ir_node *proj = new_r_Proj(irg, bl, 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(low_call, BE_OUT_POS(curr_res_proj), reg);
			arch_set_irn_register(arch_env, proj, reg);

			/* a call can produce ignore registers, in this case set the flag and register for the Proj */
			if (arch_register_type_is(reg, ignore)) {
				be_node_set_flags(low_call, BE_OUT_POS(curr_res_proj),
				                  arch_irn_flags_ignore);
			}

			set_irn_link(proj, (void*) reg);
			obstack_ptr_grow(obst, 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(arch_env, proj);
			set_irn_link(proj, (void*) reg);
			obstack_ptr_grow(obst, proj);
		}
		n += n_reg_results;

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

	/* Clean up the stack. */
	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(irg, bl, low_call, mode_M, pn_be_Call_M_regular);
			keep_alive(mem_proj);
		}

		 /* Clean up the stack frame if we allocated it */
		if (! no_alloc) {
			/* the callee pops the shadow parameter */
			if(get_method_calling_convention(mt) & cc_compound_ret) {
				unsigned size = get_mode_size_bytes(mode_P_data);
				stack_size -= size;
				be_Call_set_pop(low_call, size);
			}

			curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, -stack_size);
			//add_irn_dep(curr_sp, mem_proj);
		}
	}

	be_abi_call_free(call);
	obstack_free(obst, stack_param_idx);
	del_pset(results);
	del_pset(states);
	del_pset(caller_save);

	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 irg        the irg where new nodes are allocated on
 * @param irg        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_graph *irg, ir_node *block, dbg_info *dbg)
{
	if (stack_alignment > 1) {
		ir_mode *mode = get_irn_mode(size);
		tarval  *tv   = new_tarval_from_long(stack_alignment-1, mode);
		ir_node *mask = new_r_Const(irg, block, mode, tv);

		size = new_rd_Add(dbg, irg, block, size, mask, mode);

		tv   = new_tarval_from_long(-(long)stack_alignment, mode);
		mask = new_r_Const(irg, block, mode, tv);
		size = new_rd_And(dbg, irg, 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;
	ir_graph *irg;
	ir_node *alloc_mem;
	ir_node *alloc_res;
	ir_type *type;
	dbg_info *dbg;

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

	if (get_Alloc_where(alloc) != stack_alloc) {
		assert(0);
		return alloc;
	}

	block = get_nodes_block(alloc);
	irg = get_irn_irg(block);
	alloc_mem = NULL;
	alloc_res = NULL;
	type = get_Alloc_type(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);

	/* we might need to multiply the size with the element size */
	if(type != get_unknown_type() && get_type_size_bytes(type) != 1) {
		tarval *tv    = new_tarval_from_long(get_type_size_bytes(type),
		                                     mode_Iu);
		ir_node *cnst = new_rd_Const(dbg, irg, block, mode_Iu, tv);
		ir_node *mul  = new_rd_Mul(dbg, irg, block, get_Alloc_size(alloc),
		                           cnst, mode_Iu);
		size = mul;
	} else {
		size = get_Alloc_size(alloc);
	}

	/* The stack pointer will be modified in an unknown manner.
	   We cannot omit it. */
	env->call->flags.bits.try_omit_fp = 0;

	/* FIXME: size must be here round up for the stack alignment, but
	   this must be transmitted from the backend. */
	stack_alignment = 4;
	size            = adjust_alloc_size(stack_alignment, size, irg, block, dbg);
	new_alloc       = be_new_AddSP(env->isa->sp, irg, block, curr_sp, size);
	set_irn_dbg_info(new_alloc, dbg);

	if(alloc_mem != NULL) {
		ir_node *addsp_mem;
		ir_node *sync;

		addsp_mem = new_r_Proj(irg, block, new_alloc, mode_M, pn_be_AddSP_M);

		/* We need to sync the output mem of the AddSP with the input mem
		   edge into the alloc node. */
		ins[0] = get_Alloc_mem(alloc);
		ins[1] = addsp_mem;
		sync = new_r_Sync(irg, block, 2, ins);

		exchange(alloc_mem, sync);
	}

	exchange(alloc, new_alloc);

	/* fix projnum of alloca res */
	set_Proj_proj(alloc_res, pn_be_AddSP_res);

	addr    = alloc_res;
	curr_sp = new_r_Proj(irg, block, new_alloc,  get_irn_mode(curr_sp),
	                     pn_be_AddSP_sp);

	return curr_sp;
}  /* adjust_alloc */

/**
 * Adjust a Free.
 * The Free is transformed into a back end free node and connected to the stack nodes.
 */
static ir_node *adjust_free(be_abi_irg_t *env, ir_node *free, ir_node *curr_sp)
{
	ir_node *block;
	ir_graph *irg;
	ir_node *subsp, *mem, *res, *size, *sync;
	ir_type *type;
	ir_node *in[2];
	ir_mode *sp_mode;
	unsigned stack_alignment;
	dbg_info *dbg;

	if (get_Free_where(free) != stack_alloc) {
		assert(0);
		return free;
	}

	block = get_nodes_block(free);
	irg = get_irn_irg(block);
	type = get_Free_type(free);
	sp_mode = env->isa->sp->reg_class->mode;
	dbg = get_irn_dbg_info(free);

	/* we might need to multiply the size with the element size */
	if(type != get_unknown_type() && get_type_size_bytes(type) != 1) {
		tarval *tv = new_tarval_from_long(get_type_size_bytes(type), mode_Iu);
		ir_node *cnst = new_rd_Const(dbg, irg, block, mode_Iu, tv);
		ir_node *mul = new_rd_Mul(dbg, irg, block, get_Free_size(free),
		                          cnst, mode_Iu);
		size = mul;
	} else {
		size = get_Free_size(free);
	}

	/* FIXME: size must be here round up for the stack alignment, but
	   this must be transmitted from the backend. */
	stack_alignment = 4;
	size = adjust_alloc_size(stack_alignment, size, irg, block, dbg);

	/* The stack pointer will be modified in an unknown manner.
	   We cannot omit it. */
	env->call->flags.bits.try_omit_fp = 0;
	subsp = be_new_SubSP(env->isa->sp, irg, block, curr_sp, size);
	set_irn_dbg_info(subsp, dbg);

	mem = new_r_Proj(irg, block, subsp, mode_M, pn_be_SubSP_M);
	res = new_r_Proj(irg, block, subsp, sp_mode, pn_be_SubSP_sp);

	/* we need to sync the memory */
	in[0] = get_Free_mem(free);
	in[1] = mem;
	sync = new_r_Sync(irg, block, 2, in);

	/* and make the AddSP dependent on the former memory */
	add_irn_dep(subsp, get_Free_mem(free));

	/* kill the free */
	exchange(free, sync);
	curr_sp = res;

	return curr_sp;
}  /* adjust_free */

/* the following function is replaced by the usage of the heights module */
#if 0
/**
 * Walker for dependent_on().
 * This function searches a node tgt recursively from a given node
 * but is restricted to the given block.
 * @return 1 if tgt was reachable from curr, 0 if not.
 */
static int check_dependence(ir_node *curr, ir_node *tgt, ir_node *bl)
{
	int n, i;

	if (get_nodes_block(curr) != bl)
		return 0;

	if (curr == tgt)
		return 1;

	/* Phi functions stop the recursion inside a basic block */
	if (! is_Phi(curr)) {
		for(i = 0, n = get_irn_arity(curr); i < n; ++i) {
			if (check_dependence(get_irn_n(curr, i), tgt, bl))
				return 1;
		}
	}

	return 0;
}
#endif /* if 0 */

/**
 * Check if a node is somehow data dependent on another one.
 * both nodes must be in the same basic block.
 * @param n1 The first node.
 * @param n2 The second node.
 * @return 1, if n1 is data dependent (transitively) on n2, 0 if not.
 */
static int dependent_on(ir_node *n1, ir_node *n2)
{
	assert(get_nodes_block(n1) == get_nodes_block(n2));

	return heights_reachable_in_block(ir_heights, n1, n2);
}

static int cmp_call_dependency(const void *c1, const void *c2)
{
	ir_node *n1 = *(ir_node **) c1;
	ir_node *n2 = *(ir_node **) c2;

	/*
		Classical qsort() comparison function behavior:
		0  if both elements are equal
		1  if second is "smaller" that first
		-1 if first is "smaller" that second
	*/
	if (dependent_on(n1, n2))
		return -1;

	if (dependent_on(n2, n1))
		return 1;

	return 0;
}

/**
 * Walker: links all Call/alloc/Free nodes to the Block they are contained.
 */
static void link_calls_in_block_walker(ir_node *irn, void *data)
{
	ir_opcode code = get_irn_opcode(irn);

	if (code == iro_Call ||
		(code == iro_Alloc && get_Alloc_where(irn) == stack_alloc) ||
		(code == iro_Free && get_Free_where(irn) == stack_alloc)) {
		be_abi_irg_t *env = data;
		ir_node *bl       = get_nodes_block(irn);
		void *save        = get_irn_link(bl);

		if (code == iro_Call)
			env->call->flags.bits.irg_is_leaf = 0;

		set_irn_link(irn, save);
		set_irn_link(bl, irn);
	}
}

/**
 * Block-walker:
 * Process all Call nodes inside a basic block.
 * Note that the link field of the block must contain a linked list of all
 * Call nodes inside the Block. We first order this list according to data dependency
 * and that connect the calls together.
 */
static void process_calls_in_block(ir_node *bl, void *data)
{
	be_abi_irg_t *env = data;
	ir_node *curr_sp  = env->init_sp;
	ir_node *irn;
	int n;

	for(irn = get_irn_link(bl), n = 0; irn; irn = get_irn_link(irn), ++n)
		obstack_ptr_grow(&env->obst, irn);

	/* If there were call nodes in the block. */
	if(n > 0) {
		ir_node *keep;
		ir_node **nodes;
		int i;

		nodes = obstack_finish(&env->obst);

		/* order the call nodes according to data dependency */
		qsort(nodes, n, sizeof(nodes[0]), cmp_call_dependency);

		for(i = n - 1; i >= 0; --i) {
			ir_node *irn = nodes[i];

			DBG((env->dbg, LEVEL_3, "\tprocessing call %+F\n", irn));
			switch(get_irn_opcode(irn)) {
			case iro_Call:
				curr_sp = adjust_call(env, irn, curr_sp);
				break;
			case iro_Alloc:
				curr_sp = adjust_alloc(env, irn, curr_sp);
				break;
			case iro_Free:
				curr_sp = adjust_free(env, irn, curr_sp);
				break;
			default:
				panic("invalid call");
				break;
			}
		}

		obstack_free(&env->obst, nodes);

		/* Keep the last stack state in the block by tying it to Keep node,
		 * the proj from calls is already kept */
		if(curr_sp != env->init_sp && !is_Proj(curr_sp)) {
			nodes[0] = curr_sp;
			keep     = be_new_Keep(env->isa->sp->reg_class, get_irn_irg(bl),
			                       bl, 1, nodes);
			pmap_insert(env->keep_map, bl, keep);
		}
	}

	set_irn_link(bl, curr_sp);
{'fraction_non_alphanumeric': 0.11985764707605337, 'fraction_numerical': 0.00508194080344459, 'mean_word_length': 3.1307924984875983, 'pattern_counts': {'":': 0, '<': 93, '<?xml version=': 0, '>': 255, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 28, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6762078', 'n_tokens_mistral': 27569, 'n_tokens_neox': 25549, 'n_words': 6669}