beabi.c 69.5 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
2
 * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 *
 * 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.
Christian Würdig's avatar
Christian Würdig committed
18
19
20
21
22
 */

/**
 * @file
 * @brief       Backend ABI implementation.
23
 * @author      Sebastian Hack, Michael Beck
Christian Würdig's avatar
Christian Würdig committed
24
 * @version     $Id$
Sebastian Hack's avatar
Sebastian Hack committed
25
 */
Matthias Braun's avatar
Matthias Braun committed
26
#include "config.h"
27

Sebastian Hack's avatar
Sebastian Hack committed
28
29
#include "obst.h"

30
#include "irgopt.h"
Sebastian Hack's avatar
Sebastian Hack committed
31
32
33
34
35
36
37

#include "irgraph_t.h"
#include "irnode_t.h"
#include "ircons_t.h"
#include "iredges_t.h"
#include "irgmod.h"
#include "irgwalk.h"
Sebastian Hack's avatar
Sebastian Hack committed
38
#include "irprintf_t.h"
39
#include "irgopt.h"
40
#include "irbitset.h"
41
#include "iropt_t.h"
42
#include "heights.h"
43
44
#include "pdeq.h"
#include "irtools.h"
Matthias Braun's avatar
Matthias Braun committed
45
#include "raw_bitset.h"
46
#include "error.h"
47
#include "pset_new.h"
Sebastian Hack's avatar
Sebastian Hack committed
48
49
50

#include "be.h"
#include "beabi.h"
51
#include "bearch.h"
52
#include "benode.h"
Sebastian Hack's avatar
Sebastian Hack committed
53
#include "belive_t.h"
54
55
#include "besched.h"
#include "beirg.h"
56
#include "bessaconstr.h"
57
58
59
#include "bemodule.h"

DEBUG_ONLY(static firm_dbg_module_t *dbg;)
Sebastian Hack's avatar
Sebastian Hack committed
60

61
typedef struct be_abi_call_arg_t {
62
63
	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. */
64
	unsigned on_stack : 1;  /**< 1: this argument is transmitted on the stack. */
65
	unsigned callee   : 1;  /**< 1: someone called us. 0: We call another function */
Sebastian Hack's avatar
Sebastian Hack committed
66

67
	int                    pos;
Sebastian Hack's avatar
Sebastian Hack committed
68
	const arch_register_t *reg;
69
70
71
72
73
	ir_entity             *stack_ent;
	ir_mode               *load_mode;
	unsigned               alignment;    /**< stack alignment */
	unsigned               space_before; /**< allocate space before */
	unsigned               space_after;  /**< allocate space after */
Sebastian Hack's avatar
Sebastian Hack committed
74
75
} be_abi_call_arg_t;

76
struct be_abi_call_t {
Michael Beck's avatar
Michael Beck committed
77
78
	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. */
79
80
81
	const be_abi_callbacks_t    *cb;
	ir_type                     *between_type;
	set                         *params;
Michael Beck's avatar
Michael Beck committed
82
	const arch_register_class_t *cls_addr; /**< register class of the call address */
Sebastian Hack's avatar
Sebastian Hack committed
83
84
};

Michael Beck's avatar
Michael Beck committed
85
/**
86
 * The ABI information for the current graph.
Michael Beck's avatar
Michael Beck committed
87
 */
88
struct be_abi_irg_t {
Sebastian Hack's avatar
Sebastian Hack committed
89
90
	survive_dce_t        *dce_survivor;

Sebastian Hack's avatar
Sebastian Hack committed
91
	be_abi_call_t        *call;         /**< The ABI call information. */
Sebastian Hack's avatar
Sebastian Hack committed
92

Sebastian Hack's avatar
Sebastian Hack committed
93
	ir_node              *init_sp;      /**< The node representing the stack pointer
94
	                                         at the start of the function. */
Sebastian Hack's avatar
Sebastian Hack committed
95

96
	ir_node              *start;        /**< The be_Start params node. */
Sebastian Hack's avatar
Sebastian Hack committed
97
	pmap                 *regs;         /**< A map of all callee-save and ignore regs to
98
	                                         their Projs to the RegParams node. */
Sebastian Hack's avatar
Sebastian Hack committed
99

100
	int                  start_block_bias; /**< The stack bias at the end of the start block. */
Sebastian Hack's avatar
Sebastian Hack committed
101

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

Sebastian Hack's avatar
Sebastian Hack committed
104
105
	pmap                 *keep_map;     /**< mapping blocks to keep nodes. */

106
	ir_node              **calls;       /**< flexible array containing all be_Call nodes */
Sebastian Hack's avatar
Sebastian Hack committed
107
};
Sebastian Hack's avatar
Sebastian Hack committed
108

109
static ir_heights_t *ir_heights;
110

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

Sebastian Hack's avatar
Sebastian Hack committed
114
115
116
117
118
119
/*
     _    ____ ___    ____      _ _ _                _
    / \  | __ )_ _|  / ___|__ _| | | |__   __ _  ___| | _____
   / _ \ |  _ \| |  | |   / _` | | | '_ \ / _` |/ __| |/ / __|
  / ___ \| |_) | |  | |__| (_| | | | |_) | (_| | (__|   <\__ \
 /_/   \_\____/___|  \____\__,_|_|_|_.__/ \__,_|\___|_|\_\___/
120

Sebastian Hack's avatar
Sebastian Hack committed
121
122
123
  These callbacks are used by the backend to set the parameters
  for a specific call type.
*/
Sebastian Hack's avatar
Sebastian Hack committed
124

Michael Beck's avatar
Michael Beck committed
125
126
127
/**
 * Set compare function: compares two ABI call object arguments.
 */
Sebastian Hack's avatar
Sebastian Hack committed
128
129
static int cmp_call_arg(const void *a, const void *b, size_t n)
{
130
131
	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;
132
	(void) n;
133
	return !(p->is_res == q->is_res && p->pos == q->pos && p->callee == q->callee);
Sebastian Hack's avatar
Sebastian Hack committed
134
135
}

Michael Beck's avatar
Michael Beck committed
136
/**
Michael Beck's avatar
Michael Beck committed
137
 * Get  an ABI call object argument.
Michael Beck's avatar
Michael Beck committed
138
139
140
141
 *
 * @param call      the abi call
 * @param is_res    true for call results, false for call arguments
 * @param pos       position of the argument
142
 * @param callee    context type - if we are callee or caller
Michael Beck's avatar
Michael Beck committed
143
 */
144
static be_abi_call_arg_t *get_call_arg(be_abi_call_t *call, int is_res, int pos, int callee)
Sebastian Hack's avatar
Sebastian Hack committed
145
146
147
148
{
	be_abi_call_arg_t arg;
	unsigned hash;

149
	memset(&arg, 0, sizeof(arg));
Sebastian Hack's avatar
Sebastian Hack committed
150
151
	arg.is_res = is_res;
	arg.pos    = pos;
152
	arg.callee = callee;
Sebastian Hack's avatar
Sebastian Hack committed
153

Michael Beck's avatar
Michael Beck committed
154
	hash = is_res * 128 + pos;
Sebastian Hack's avatar
Sebastian Hack committed
155

156
	return (be_abi_call_arg_t*)set_find(call->params, &arg, sizeof(arg), hash);
Sebastian Hack's avatar
Sebastian Hack committed
157
158
}

Michael Beck's avatar
Michael Beck committed
159
/**
Michael Beck's avatar
Michael Beck committed
160
 * Set an ABI call object argument.
Michael Beck's avatar
Michael Beck committed
161
 */
162
static void remember_call_arg(be_abi_call_arg_t *arg, be_abi_call_t *call, be_abi_context_t context)
Sebastian Hack's avatar
Sebastian Hack committed
163
{
164
165
166
167
168
169
170
171
172
	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);
	}
Sebastian Hack's avatar
Sebastian Hack committed
173
174
}

Michael Beck's avatar
Michael Beck committed
175
/* Set the flags for a call. */
176
void be_abi_call_set_flags(be_abi_call_t *call, be_abi_call_flags_t flags, const be_abi_callbacks_t *cb)
Sebastian Hack's avatar
Sebastian Hack committed
177
{
178
179
	call->flags = flags;
	call->cb    = cb;
Sebastian Hack's avatar
Sebastian Hack committed
180
181
}

Michael Beck's avatar
Michael Beck committed
182
/* Sets the number of bytes the stackframe is shrinked by the callee on return */
183
184
185
186
187
void be_abi_call_set_pop(be_abi_call_t *call, int pop)
{
	assert(pop >= 0);
	call->pop = pop;
}
188
189
190
191
192
193
194
195

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


196
197
198
199
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)
Sebastian Hack's avatar
Sebastian Hack committed
200
{
201
202
	be_abi_call_arg_t arg;
	memset(&arg, 0, sizeof(arg));
203
	assert(alignment > 0 && "Alignment must be greater than 0");
204
205
206
207
208
209
210
211
212
	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);
Sebastian Hack's avatar
Sebastian Hack committed
213
214
}

215
void be_abi_call_param_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg, be_abi_context_t context)
Sebastian Hack's avatar
Sebastian Hack committed
216
{
217
218
219
220
221
222
223
224
225
	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);
Sebastian Hack's avatar
Sebastian Hack committed
226
227
}

228
void be_abi_call_res_reg(be_abi_call_t *call, int arg_pos, const arch_register_t *reg, be_abi_context_t context)
Sebastian Hack's avatar
Sebastian Hack committed
229
{
230
231
232
233
234
235
236
237
238
	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);
Sebastian Hack's avatar
Sebastian Hack committed
239
240
}

Michael Beck's avatar
Michael Beck committed
241
/* Get the flags of a ABI call object. */
242
243
244
245
246
be_abi_call_flags_t be_abi_call_get_flags(const be_abi_call_t *call)
{
	return call->flags;
}

Michael Beck's avatar
Michael Beck committed
247
248
249
/**
 * Constructor for a new ABI call object.
 *
Michael Beck's avatar
Michael Beck committed
250
251
 * @param cls_addr  register class of the call address
 *
Michael Beck's avatar
Michael Beck committed
252
253
 * @return the new ABI call object
 */
254
static be_abi_call_t *be_abi_call_new(const arch_register_class_t *cls_addr)
Sebastian Hack's avatar
Sebastian Hack committed
255
{
256
	be_abi_call_t *call = XMALLOCZ(be_abi_call_t);
257

Sebastian Hack's avatar
Sebastian Hack committed
258
259
260
	call->flags.val  = 0;
	call->params     = new_set(cmp_call_arg, 16);
	call->cb         = NULL;
261
	call->cls_addr   = cls_addr;
262

263
	call->flags.bits.try_omit_fp = be_omit_fp;
264

Sebastian Hack's avatar
Sebastian Hack committed
265
266
267
	return call;
}

Michael Beck's avatar
Michael Beck committed
268
269
270
271
/**
 * Destructor for an ABI call object.
 */
static void be_abi_call_free(be_abi_call_t *call)
Sebastian Hack's avatar
Sebastian Hack committed
272
273
274
275
276
{
	del_set(call->params);
	free(call);
}

277
278
279
280
281
282
283
/**
 * 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
284
 * @param stack_dir the stack direction: < 0 decreasing, > 0 increasing addresses
285
 * @param param_map an array mapping method argument positions to the stack argument type
286
287
288
289
 *
 * @return the initialized stack layout
 */
static be_stack_layout_t *stack_frame_init(be_stack_layout_t *frame, ir_type *args,
290
                                           ir_type *between, ir_type *locals, int stack_dir,
291
                                           ir_entity *param_map[])
292
293
294
295
296
{
	frame->arg_type       = args;
	frame->between_type   = between;
	frame->frame_type     = locals;
	frame->initial_offset = 0;
Matthias Braun's avatar
Matthias Braun committed
297
	frame->initial_bias   = 0;
298
299
	frame->stack_dir      = stack_dir;
	frame->order[1]       = between;
300
	frame->param_map      = param_map;
301

302
	if (stack_dir > 0) {
303
304
		frame->order[0] = args;
		frame->order[2] = locals;
305
	} else {
306
307
		/* typical decreasing stack: locals have the
		 * lowest addresses, arguments the highest */
308
309
310
311
312
313
		frame->order[0] = locals;
		frame->order[2] = args;
	}
	return frame;
}

314
315
316
317
318
319
320
321
322
323
324
/*
   ____      _ _
  / ___|__ _| | |___
 | |   / _` | | / __|
 | |__| (_| | | \__ \
  \____\__,_|_|_|___/

  Adjustment of the calls inside a graph.

*/

Sebastian Hack's avatar
Sebastian Hack committed
325
/**
326
327
 * Transform a call node into a be_Call node.
 *
Sebastian Hack's avatar
Sebastian Hack committed
328
 * @param env The ABI environment for the current irg.
329
330
331
 * @param irn The call node.
 * @param curr_sp The stack pointer node to use.
 * @return The stack pointer after the call.
Sebastian Hack's avatar
Sebastian Hack committed
332
 */
Matthias Braun's avatar
Matthias Braun committed
333
static ir_node *adjust_call(be_abi_irg_t *env, ir_node *irn, ir_node *curr_sp)
Sebastian Hack's avatar
Sebastian Hack committed
334
{
335
336
	ir_graph *irg              = get_irn_irg(irn);
	const arch_env_t *arch_env = be_get_irg_arch_env(irg);
337
	ir_type *call_tp           = get_Call_type(irn);
338
	ir_node *call_ptr          = get_Call_ptr(irn);
339
	int n_params               = get_method_n_params(call_tp);
340
341
342
	ir_node *curr_mem          = get_Call_mem(irn);
	ir_node *bl                = get_nodes_block(irn);
	int stack_size             = 0;
343
344
	int stack_dir              = arch_env->stack_dir;
	const arch_register_t *sp  = arch_env->sp;
345
346
347
	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;
348
	int n_res                  = get_method_n_ress(call_tp);
349
	int do_seq                 = call->flags.bits.store_args_sequential && !no_alloc;
350
351
352
353
354

	ir_node *res_proj  = NULL;
	int n_reg_params   = 0;
	int n_stack_params = 0;
	int n_ins;
Sebastian Hack's avatar
Sebastian Hack committed
355

356
357
	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);
358
359
360
361
362
363
364
	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;
365
	int                     i, n, destroy_all_regs;
366
	dbg_info               *dbgi;
Sebastian Hack's avatar
Sebastian Hack committed
367
368

	/* Let the isa fill out the abi description for that call node. */
369
	arch_env_get_call_abi(arch_env, call_tp, call);
Sebastian Hack's avatar
Sebastian Hack committed
370
371

	/* Insert code to put the stack arguments on the stack. */
372
	assert(get_Call_n_params(irn) == n_params);
373
	stack_param_idx = ALLOCAN(int, n_params);
374
	for (i = 0; i < n_params; ++i) {
375
		be_abi_call_arg_t *arg = get_call_arg(call, 0, i, 0);
376
		assert(arg);
Michael Beck's avatar
Michael Beck committed
377
		if (arg->on_stack) {
378
			int arg_size = get_type_size_bytes(get_method_param_type(call_tp, i));
Michael Beck's avatar
Michael Beck committed
379
380
381
382

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

			stack_param_idx[n_stack_params++] = i;
Sebastian Hack's avatar
Sebastian Hack committed
385
386
387
388
		}
	}

	/* Collect all arguments which are passed in registers. */
389
	reg_param_idxs = ALLOCAN(int, n_params);
390
	for (i = 0; i < n_params; ++i) {
391
		be_abi_call_arg_t *arg = get_call_arg(call, 0, i, 0);
392
		if (arg && arg->in_reg) {
393
			reg_param_idxs[n_reg_params++] = i;
Sebastian Hack's avatar
Sebastian Hack committed
394
395
396
		}
	}

397
398
399
400
401
402
403
404
405
406
	/*
	 * 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) {
407
		curr_sp = be_new_IncSP(sp, bl, curr_sp, stack_size, 1);
408
409
	}

Christoph Mallon's avatar
Christoph Mallon committed
410
	dbgi = get_irn_dbg_info(irn);
Sebastian Hack's avatar
Sebastian Hack committed
411
	/* If there are some parameters which shall be passed on the stack. */
412
	if (n_stack_params > 0) {
413
414
415
		int       curr_ofs = 0;
		ir_node **in       = ALLOCAN(ir_node*, n_stack_params+1);
		unsigned  n_in     = 0;
Sebastian Hack's avatar
Sebastian Hack committed
416

417
418
		/*
		 * Reverse list of stack parameters if call arguments are from left to right.
419
		 * We must them reverse again if they are pushed (not stored) and the stack
420
421
422
		 * direction is downwards.
		 */
		if (call->flags.bits.left_to_right ^ (do_seq && stack_dir < 0)) {
423
424
425
426
427
			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;
Sebastian Hack's avatar
Sebastian Hack committed
428
429
430
			}
		}

431
		curr_mem = get_Call_mem(irn);
432
		if (! do_seq) {
433
			in[n_in++] = curr_mem;
434
435
		}

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

445
446
447
448
449
450
451
			/*
			 * 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;
452
453
				addr = curr_sp = be_new_IncSP(sp, bl, curr_sp,
				                              param_size + arg->space_before, 0);
Sebastian Hack's avatar
Sebastian Hack committed
454
				add_irn_dep(curr_sp, curr_mem);
455
			} else {
456
457
458
459
				curr_ofs += arg->space_before;
				curr_ofs =  round_up2(curr_ofs, arg->alignment);

				/* Make the expression to compute the argument's offset. */
460
				if (curr_ofs > 0) {
461
					ir_mode *constmode = mach_mode;
462
					if (mode_is_reference(mach_mode)) {
463
464
						constmode = mode_Is;
					}
465
					addr = new_r_Const_long(irg, constmode, curr_ofs);
466
					addr = new_r_Add(bl, curr_sp, addr, mach_mode);
467
				}
Sebastian Hack's avatar
Sebastian Hack committed
468
469
470
			}

			/* Insert a store for primitive arguments. */
471
			if (is_atomic_type(param_type)) {
472
				ir_node *mem_input = do_seq ? curr_mem : new_r_NoMem(irg);
473
				ir_node *store     = new_rd_Store(dbgi, bl, mem_input, addr, param, cons_none);
474
				mem   = new_r_Proj(store, mode_M, pn_Store_M);
475
476
			} else {
				/* Make a mem copy for compound arguments. */
477
478
				ir_node *copy;

Sebastian Hack's avatar
Sebastian Hack committed
479
				assert(mode_is_reference(get_irn_mode(param)));
480
				copy = new_rd_CopyB(dbgi, bl, curr_mem, addr, param, param_type);
481
				mem = new_r_Proj(copy, mode_M, pn_CopyB_M);
Sebastian Hack's avatar
Sebastian Hack committed
482
483
484
485
			}

			curr_ofs += param_size;

486
			if (do_seq)
Sebastian Hack's avatar
Sebastian Hack committed
487
				curr_mem = mem;
488
			else
489
				in[n_in++] = mem;
Sebastian Hack's avatar
Sebastian Hack committed
490
491
492
		}

		/* We need the sync only, if we didn't build the stores sequentially. */
493
494
		if (! do_seq) {
			if (n_stack_params >= 1) {
495
				curr_mem = new_r_Sync(bl, n_in, in);
496
497
498
499
			} else {
				curr_mem = get_Call_mem(irn);
			}
		}
Sebastian Hack's avatar
Sebastian Hack committed
500
501
	}

502
503
504
505
506
507
508
509
510
511
512
513
514
515
	/* 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;
	}

516
517
	/* Put caller save into the destroyed set and state registers in the states
	 * set */
518
	for (i = 0, n = arch_env->n_register_classes; i < n; ++i) {
519
		unsigned j;
520
		const arch_register_class_t *cls = &arch_env->register_classes[i];
521
		for (j = 0; j < cls->n_regs; ++j) {
Sebastian Hack's avatar
Sebastian Hack committed
522
			const arch_register_t *reg = arch_register_for_index(cls, j);
523

524
525
526
527
528
			/* 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;

529
			if (reg->type & arch_register_type_state) {
530
531
532
533
534
535
				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;
			}
536
537
			if (destroy_all_regs || (reg->type & arch_register_type_caller_save)) {
				if (!(reg->type & arch_register_type_ignore)) {
538
539
					ARR_APP1(const arch_register_t*, destroyed_regs, reg);
				}
540
			}
Sebastian Hack's avatar
Sebastian Hack committed
541
542
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
543

Christoph Mallon's avatar
Christoph Mallon committed
544
	/* search the largest result proj number */
545
	res_projs = ALLOCANZ(ir_node*, n_res);
Matthias Braun's avatar
Matthias Braun committed
546

Sebastian Hack's avatar
Sebastian Hack committed
547
548
	foreach_out_edge(irn, edge) {
		const ir_edge_t *res_edge;
Matthias Braun's avatar
Matthias Braun committed
549
		ir_node         *irn = get_edge_src_irn(edge);
Sebastian Hack's avatar
Sebastian Hack committed
550

551
		if (!is_Proj(irn) || get_Proj_proj(irn) != pn_Call_T_result)
Matthias Braun's avatar
Matthias Braun committed
552
553
554
555
556
557
558
559
560
561
			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);
Matthias Braun's avatar
Matthias Braun committed
562
			assert(res_projs[proj] == NULL);
Matthias Braun's avatar
Matthias Braun committed
563
			res_projs[proj] = res;
Sebastian Hack's avatar
Sebastian Hack committed
564
		}
Matthias Braun's avatar
Matthias Braun committed
565
566
		res_proj = irn;
		break;
Sebastian Hack's avatar
Sebastian Hack committed
567
	}
568

Matthias Braun's avatar
Matthias Braun committed
569
	/** TODO: this is not correct for cases where return values are passed
Christoph Mallon's avatar
Christoph Mallon committed
570
	 * on the stack, but no known ABI does this currently...
Matthias Braun's avatar
Matthias Braun committed
571
572
	 */
	n_reg_results = n_res;
Sebastian Hack's avatar
Sebastian Hack committed
573

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

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

	/* add state registers ins */
583
584
	for (i = 0; i < ARR_LEN(states); ++i) {
		const arch_register_t       *reg = states[i];
585
586
587
588
589
		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
590
		ir_node *regnode = new_r_Unknown(irg, arch_register_class_mode(cls));
591
		in[n_ins++]      = regnode;
592
	}
593
	assert(n_ins == (int) (n_reg_params + ARR_LEN(states)));
594

595
	/* ins collected, build the call */
596
597
	if (env->call->flags.bits.call_has_imm && is_SymConst(call_ptr)) {
		/* direct call */
598
		low_call = be_new_Call(dbgi, irg, bl, curr_mem, curr_sp, curr_sp,
599
		                       n_reg_results + pn_be_Call_first_res + ARR_LEN(destroyed_regs),
Matthias Braun's avatar
Matthias Braun committed
600
		                       n_ins, in, get_Call_type(irn));
Sebastian Hack's avatar
Sebastian Hack committed
601
		be_Call_set_entity(low_call, get_SymConst_entity(call_ptr));
602
	} else {
603
		/* indirect call */
604
		low_call = be_new_Call(dbgi, irg, bl, curr_mem, curr_sp, call_ptr,
605
		                       n_reg_results + pn_be_Call_first_res + ARR_LEN(destroyed_regs),
606
		                       n_ins, in, get_Call_type(irn));
Sebastian Hack's avatar
Sebastian Hack committed
607
	}
608
	be_Call_set_pop(low_call, call->pop);
609
610

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

Matthias Braun's avatar
Matthias Braun committed
613
	/* create new stack pointer */
614
	curr_sp = new_r_Proj(low_call, get_irn_mode(curr_sp), pn_be_Call_sp);
615
616
	be_set_constr_single_reg_out(low_call, pn_be_Call_sp, sp,
			arch_register_req_type_ignore | arch_register_req_type_produces_sp);
617
	arch_set_irn_register(curr_sp, sp);
Matthias Braun's avatar
Matthias Braun committed
618

619
	/* now handle results */
620
	for (i = 0; i < n_res; ++i) {
Matthias Braun's avatar
Matthias Braun committed
621
622
		int pn;
		ir_node           *proj = res_projs[i];
623
		be_abi_call_arg_t *arg  = get_call_arg(call, 1, i, 0);
Matthias Braun's avatar
Matthias Braun committed
624

Matthias Braun's avatar
Matthias Braun committed
625
626
627
		/* returns values on stack not supported yet */
		assert(arg->in_reg);

Matthias Braun's avatar
Matthias Braun committed
628
629
630
631
632
633
634
		/*
			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;

635
		if (proj == NULL) {
636
			ir_type *res_type = get_method_res_type(call_tp, i);
Matthias Braun's avatar
Matthias Braun committed
637
			ir_mode *mode     = get_type_mode(res_type);
638
			proj              = new_r_Proj(low_call, mode, pn);
Matthias Braun's avatar
Matthias Braun committed
639
640
641
642
643
644
645
			res_projs[i]      = proj;
		} else {
			set_Proj_pred(proj, low_call);
			set_Proj_proj(proj, pn);
		}

		if (arg->in_reg) {
646
			/* remove register from destroyed regs */
647
648
			size_t j;
			size_t n = ARR_LEN(destroyed_regs);
649
650
651
652
653
654
655
			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;
				}
			}
Matthias Braun's avatar
Matthias Braun committed
656
657
658
		}
	}

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

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

Sebastian Hack's avatar
Sebastian Hack committed
667
	/* Set the register classes and constraints of the Call parameters. */
668
669
	for (i = 0; i < n_reg_params; ++i) {
		int index = reg_param_idxs[i];
670
		be_abi_call_arg_t *arg = get_call_arg(call, 0, index, 0);
Sebastian Hack's avatar
Sebastian Hack committed
671
		assert(arg->reg != NULL);
672

673
		be_set_constr_single_reg_in(low_call, be_pos_Call_first_arg + i,
674
		                            arg->reg, arch_register_req_type_none);
Sebastian Hack's avatar
Sebastian Hack committed
675
676
677
	}

	/* Set the register constraints of the results. */
Matthias Braun's avatar
Matthias Braun committed
678
679
	for (i = 0; i < n_res; ++i) {
		ir_node                 *proj = res_projs[i];
680
		const be_abi_call_arg_t *arg  = get_call_arg(call, 1, i, 0);
Matthias Braun's avatar
Matthias Braun committed
681
		int                      pn   = get_Proj_proj(proj);
682

Sebastian Hack's avatar
Sebastian Hack committed
683
		assert(arg->in_reg);
684
685
		be_set_constr_single_reg_out(low_call, pn, arg->reg,
		                             arch_register_req_type_none);
686
		arch_set_irn_register(proj, arg->reg);
Sebastian Hack's avatar
Sebastian Hack committed
687
	}
688
689
	exchange(irn, low_call);

Matthias Braun's avatar
Matthias Braun committed
690
	/* kill the ProjT node */
691
	if (res_proj != NULL) {
692
		kill_node(res_proj);
693
694
	}

Sebastian Hack's avatar
Sebastian Hack committed
695
696
	/* Make additional projs for the caller save registers
	   and the Keep node which keeps them alive. */
697
	{
698
		ir_node               **in, *keep;
699
700
		int                   i;
		int                   n = 0;
701
		int                   curr_res_proj = pn_be_Call_first_res + n_reg_results;
702
		int                   n_ins;
Sebastian Hack's avatar
Sebastian Hack committed
703

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

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

711
712
		for (i = 0; i < ARR_LEN(destroyed_regs); ++i) {
			const arch_register_t *reg = destroyed_regs[i];
713
			ir_node *proj = new_r_Proj(low_call, reg->reg_class->mode, curr_res_proj);
Sebastian Hack's avatar
Sebastian Hack committed
714

Sebastian Hack's avatar
Sebastian Hack committed
715
			/* memorize the register in the link field. we need afterwards to set the register class of the keep correctly. */
716
717
			be_set_constr_single_reg_out(low_call, curr_res_proj, reg,
			                             arch_register_req_type_none);
718
			arch_set_irn_register(proj, reg);
719

Matthias Braun's avatar
Matthias Braun committed
720
			set_irn_link(proj, (void*) reg);
721
			in[n++] = proj;
722
			++curr_res_proj;
Sebastian Hack's avatar
Sebastian Hack committed
723
724
		}

725
		for (i = 0; i < n_reg_results; ++i) {
Matthias Braun's avatar
Matthias Braun committed
726
			ir_node *proj = res_projs[i];
727
			const arch_register_t *reg = arch_get_irn_register(proj);
Matthias Braun's avatar
Matthias Braun committed
728
			set_irn_link(proj, (void*) reg);
729
			in[n++] = proj;
Matthias Braun's avatar
Matthias Braun committed
730
		}
731
		assert(n <= n_ins);
Matthias Braun's avatar
Matthias Braun committed
732

733
		/* create the Keep for the caller save registers */
734
		keep = be_new_Keep(bl, n, in);
735
		for (i = 0; i < n; ++i) {
736
			const arch_register_t *reg = (const arch_register_t*)get_irn_link(in[i]);
737
			be_node_set_reg_class_in(keep, i, reg->reg_class);
Sebastian Hack's avatar
Sebastian Hack committed
738
		}
Sebastian Hack's avatar
Sebastian Hack committed
739
740
741
	}

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

745
	if (stack_size > 0) {
746
747
748
749
		ir_node *mem_proj = NULL;

		foreach_out_edge(low_call, edge) {
			ir_node *irn = get_edge_src_irn(edge);
750
			if (is_Proj(irn) && get_Proj_proj(irn) == pn_Call_M) {
751
752
753
754
				mem_proj = irn;
				break;
			}
		}
Sebastian Hack's avatar
Sebastian Hack committed
755

756
		if (! mem_proj) {
757
			mem_proj = new_r_Proj(low_call, mode_M, pn_be_Call_M_regular);
Sebastian Hack's avatar
Sebastian Hack committed
758
759
			keep_alive(mem_proj);
		}
760
761
762
	}
	/* Clean up the stack frame or revert alignment fixes if we allocated it */
	if (! no_alloc) {
763
		curr_sp = be_new_IncSP(sp, bl, curr_sp, -stack_size, 0);
Sebastian Hack's avatar
Sebastian Hack committed
764
765
766
	}

	be_abi_call_free(call);
767

768
769
	DEL_ARR_F(states);
	DEL_ARR_F(destroyed_regs);
770
771
772
773

	return curr_sp;
}

774
775
776
777
778
/**
 * 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
779
 * @param block      the block where new nodes are allocated on
780
781
782
783
 * @param dbg        debug info for new nodes
 *
 * @return a node representing the aligned size
 */
784
static ir_node *adjust_alloc_size(unsigned stack_alignment, ir_node *size,
785
                                  ir_node *block, dbg_info *dbg)
786
{
787
	if (stack_alignment > 1) {
Matthias Braun's avatar
Matthias Braun committed
788
789
790
791
		ir_mode   *mode;
		ir_tarval *tv;
		ir_node   *mask;
		ir_graph  *irg;
Michael Beck's avatar
Michael Beck committed
792

793
		assert(is_po2(stack_alignment));
794

Michael Beck's avatar
Michael Beck committed
795
796
		mode = get_irn_mode(size);
		tv   = new_tarval_from_long(stack_alignment-1, mode);
797
		irg  = get_Block_irg(block);
798
		mask = new_r_Const(irg, tv);
799
		size = new_rd_Add(dbg, block, size, mask, mode);
800
801

		tv   = new_tarval_from_long(-(long)stack_alignment, mode);
802
		mask = new_r_Const(irg, tv);
803
		size = new_rd_And(dbg, block, size, mask, mode);
804
805
806
	}
	return size;
}
807
808
809
810
/**
 * Adjust an alloca.
 * The alloca is transformed into a back end alloca node and connected to the stack nodes.
 */
Matthias Braun's avatar
Matthias Braun committed
811
static ir_node *adjust_alloc(be_abi_irg_t *env, ir_node *alloc, ir_node *curr_sp)
812
{
813
814
815
816
817
818
819
	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;
820

821
	const ir_edge_t *edge;
822
823
824
825
	ir_node *new_alloc;
	ir_node *count;
	ir_node *size;
	ir_node *ins[2];
826
	unsigned stack_alignment;
827

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

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

834
		assert(is_Proj(irn));
835
		switch (get_Proj_proj(irn)) {
836
837
838
839
840
841
842
843
		case pn_Alloc_M:
			alloc_mem = irn;
			break;
		case pn_Alloc_res:
			alloc_res = irn;
			break;
		default:
			break;
844
		}
845
	}
846

847
848
849
850
851
852
853
854
	/* 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;
	}

855
856
	dbg   = get_irn_dbg_info(alloc);
	count = get_Alloc_count(alloc);
857

858
	/* we might need to multiply the count with the element size */
859
	if (type != firm_unknown_type && get_type_size_bytes(type) != 1) {
Matthias Braun's avatar
Matthias Braun committed
860
861
862
863
864
		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);
865
866
	} else {
		size = count;
867
	}
868

869
870
871