beabi.c 46.9 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
Christian Würdig's avatar
Christian Würdig committed
2
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
6
7
8
 */

/**
 * @file
 * @brief       Backend ABI implementation.
9
 * @author      Sebastian Hack, Michael Beck
Sebastian Hack's avatar
Sebastian Hack committed
10
 */
Matthias Braun's avatar
Matthias Braun committed
11
#include <stdbool.h>
Sebastian Hack's avatar
Sebastian Hack committed
12

Matthias Braun's avatar
Matthias Braun committed
13
#include "obst.h"
14
#include "irgopt.h"
Sebastian Hack's avatar
Sebastian Hack committed
15
16
17
18
19
20
#include "irgraph_t.h"
#include "irnode_t.h"
#include "ircons_t.h"
#include "iredges_t.h"
#include "irgmod.h"
#include "irgwalk.h"
21
#include "irgopt.h"
22
#include "iropt_t.h"
23
#include "irtools.h"
24
#include "heights.h"
25
#include "util.h"
Matthias Braun's avatar
Matthias Braun committed
26
#include "raw_bitset.h"
Matthias Braun's avatar
Matthias Braun committed
27
#include "panic.h"
28
#include "pset_new.h"
29
#include "irmemory_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
30
31
32

#include "be.h"
#include "beabi.h"
33
#include "beabihelper.h"
34
#include "bearch.h"
35
#include "benode.h"
Matthias Braun's avatar
Matthias Braun committed
36
#include "belive.h"
37
38
#include "besched.h"
#include "beirg.h"
39
#include "bessaconstr.h"
40
#include "bemodule.h"
41
#include "betranshlp.h"
42
43

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

45
typedef struct be_abi_call_arg_t {
Matthias Braun's avatar
Matthias Braun committed
46
47
48
49
50
51
	bool is_res   : 1;  /**< true:  the call argument is a return value.
	                         false: it's a call parameter. */
	bool in_reg   : 1;  /**< true: this argument is transmitted in registers,
	                         false: on stack. */
	bool callee   : 1;  /**< true: someone called us.
	                         false: We call another function */
Sebastian Hack's avatar
Sebastian Hack committed
52

53
	int                    pos;
Sebastian Hack's avatar
Sebastian Hack committed
54
	const arch_register_t *reg;
55
56
57
58
59
	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
60
61
} be_abi_call_arg_t;

62
struct be_abi_call_t {
Matthias Braun's avatar
Matthias Braun committed
63
64
65
66
	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. */
67
68
	const be_abi_callbacks_t *cb;
	set                      *params;
Sebastian Hack's avatar
Sebastian Hack committed
69
70
};

Michael Beck's avatar
Michael Beck committed
71
/**
72
 * The ABI information for the current graph.
Michael Beck's avatar
Michael Beck committed
73
 */
74
struct be_abi_irg_t {
Matthias Braun's avatar
Matthias Braun committed
75
76
77
78
79
80
81
	be_abi_call_t *call;     /**< The ABI call information. */
	ir_node       *init_sp;  /**< The node representing the stack pointer
	                              at the start of the function. */
	pmap          *regs;     /**< A map of all callee-save and ignore regs to
	                              their Projs to the RegParams node. */
	pmap          *keep_map; /**< mapping blocks to keep nodes. */
	ir_node      **calls;    /**< flexible array containing all be_Call nodes */
Sebastian Hack's avatar
Sebastian Hack committed
82
};
Sebastian Hack's avatar
Sebastian Hack committed
83

84
static ir_heights_t *ir_heights;
85

Matthias Braun's avatar
Matthias Braun committed
86
87
static ir_node *be_abi_reg_map_get(pmap *map, const arch_register_t *reg)
{
88
	return pmap_get(ir_node, map, reg);
Matthias Braun's avatar
Matthias Braun committed
89
90
91
92
93
94
95
96
}

static void be_abi_reg_map_set(pmap *map, const arch_register_t* reg,
                               ir_node *node)
{
	pmap_insert(map, reg, node);
}

97
/**
yb9976's avatar
yb9976 committed
98
 * Check if the given register is callee save, i.e. will be saved by the callee.
99
 */
Matthias Braun's avatar
Matthias Braun committed
100
101
static bool arch_register_is_callee_save(const arch_env_t *arch_env,
                                         const arch_register_t *reg)
102
103
104
105
106
107
108
{
	if (arch_env->impl->register_saved_by)
		return arch_env->impl->register_saved_by(reg, /*callee=*/1);
	return false;
}

/**
yb9976's avatar
yb9976 committed
109
 * Check if the given register is caller save, i.e. must be saved by the caller.
110
 */
Matthias Braun's avatar
Matthias Braun committed
111
112
static bool arch_register_is_caller_save(const arch_env_t *arch_env,
                                         const arch_register_t *reg)
113
114
115
116
117
118
119
120
{
	if (arch_env->impl->register_saved_by)
		return arch_env->impl->register_saved_by(reg, /*callee=*/0);
	return false;
}



Sebastian Hack's avatar
Sebastian Hack committed
121
122
123
124
125
126
/*
     _    ____ ___    ____      _ _ _                _
    / \  | __ )_ _|  / ___|__ _| | | |__   __ _  ___| | _____
   / _ \ |  _ \| |  | |   / _` | | | '_ \ / _` |/ __| |/ / __|
  / ___ \| |_) | |  | |__| (_| | | | |_) | (_| | (__|   <\__ \
 /_/   \_\____/___|  \____\__,_|_|_|_.__/ \__,_|\___|_|\_\___/
127

Sebastian Hack's avatar
Sebastian Hack committed
128
129
130
  These callbacks are used by the backend to set the parameters
  for a specific call type.
*/
Sebastian Hack's avatar
Sebastian Hack committed
131

Michael Beck's avatar
Michael Beck committed
132
133
134
/**
 * Set compare function: compares two ABI call object arguments.
 */
Sebastian Hack's avatar
Sebastian Hack committed
135
136
static int cmp_call_arg(const void *a, const void *b, size_t n)
{
Matthias Braun's avatar
Matthias Braun committed
137
	(void) n;
138
139
	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;
140
	return !(p->is_res == q->is_res && p->pos == q->pos && p->callee == q->callee);
Sebastian Hack's avatar
Sebastian Hack committed
141
142
}

Michael Beck's avatar
Michael Beck committed
143
/**
Michael Beck's avatar
Michael Beck committed
144
 * Get  an ABI call object argument.
Michael Beck's avatar
Michael Beck committed
145
146
147
148
 *
 * @param call      the abi call
 * @param is_res    true for call results, false for call arguments
 * @param pos       position of the argument
149
 * @param callee    context type - if we are callee or caller
Michael Beck's avatar
Michael Beck committed
150
 */
Matthias Braun's avatar
Matthias Braun committed
151
152
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
153
154
{
	be_abi_call_arg_t arg;
155
	memset(&arg, 0, sizeof(arg));
Sebastian Hack's avatar
Sebastian Hack committed
156
157
	arg.is_res = is_res;
	arg.pos    = pos;
158
	arg.callee = callee;
Sebastian Hack's avatar
Sebastian Hack committed
159

Matthias Braun's avatar
Matthias Braun committed
160
	unsigned hash = is_res * 128 + pos;
161
	return set_find(be_abi_call_arg_t, call->params, &arg, sizeof(arg), hash);
Sebastian Hack's avatar
Sebastian Hack committed
162
163
}

Michael Beck's avatar
Michael Beck committed
164
/**
Michael Beck's avatar
Michael Beck committed
165
 * Set an ABI call object argument.
Michael Beck's avatar
Michael Beck committed
166
 */
Matthias Braun's avatar
Matthias Braun committed
167
168
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
169
{
170
171
172
	unsigned hash = arg->is_res * 128 + arg->pos;
	if (context & ABI_CONTEXT_CALLEE) {
		arg->callee = 1;
yb9976's avatar
yb9976 committed
173
		(void)set_insert(be_abi_call_arg_t, call->params, arg, sizeof(*arg), hash);
174
175
176
	}
	if (context & ABI_CONTEXT_CALLER) {
		arg->callee = 0;
yb9976's avatar
yb9976 committed
177
		(void)set_insert(be_abi_call_arg_t, call->params, arg, sizeof(*arg), hash);
178
	}
Sebastian Hack's avatar
Sebastian Hack committed
179
180
}

Michael Beck's avatar
Michael Beck committed
181
/* Set the flags for a call. */
Matthias Braun's avatar
Matthias Braun committed
182
183
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
184
{
185
186
	call->flags = flags;
	call->cb    = cb;
Sebastian Hack's avatar
Sebastian Hack committed
187
188
}

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

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

214
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
215
{
216
217
218
219
220
221
222
223
	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
224
225
}

226
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
227
{
228
229
230
231
232
233
234
235
	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
236
237
}

Michael Beck's avatar
Michael Beck committed
238
/* Get the flags of a ABI call object. */
239
240
241
242
243
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
244
245
246
247
248
/**
 * Constructor for a new ABI call object.
 *
 * @return the new ABI call object
 */
249
static be_abi_call_t *be_abi_call_new(void)
Sebastian Hack's avatar
Sebastian Hack committed
250
{
251
	be_abi_call_t *call = XMALLOCZ(be_abi_call_t);
252
253
	call->params            = new_set(cmp_call_arg, 16);
	call->cb                = NULL;
254
	call->flags.try_omit_fp = be_options.omit_fp;
255

Sebastian Hack's avatar
Sebastian Hack committed
256
257
258
	return call;
}

Michael Beck's avatar
Michael Beck committed
259
260
261
262
/**
 * Destructor for an ABI call object.
 */
static void be_abi_call_free(be_abi_call_t *call)
Sebastian Hack's avatar
Sebastian Hack committed
263
264
265
266
267
{
	del_set(call->params);
	free(call);
}

268
269
270
271
272
273
274
275
276
277
278
/**
 * 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
 *
 * @return the initialized stack layout
 */
static be_stack_layout_t *stack_frame_init(be_stack_layout_t *frame, ir_type *args,
279
                                           ir_type *between, ir_type *locals)
280
281
282
283
284
{
	frame->arg_type       = args;
	frame->between_type   = between;
	frame->frame_type     = locals;
	frame->initial_offset = 0;
Matthias Braun's avatar
Matthias Braun committed
285
	frame->initial_bias   = 0;
286
287
	frame->order[1]       = between;

288
289
290
291
	/* typical decreasing stack: locals have the
	 * lowest addresses, arguments the highest */
	frame->order[0] = locals;
	frame->order[2] = args;
292
293
294
	return frame;
}

295
296
297
298
299
300
301
302
303
304
305
/*
   ____      _ _
  / ___|__ _| | |___
 | |   / _` | | / __|
 | |__| (_| | | \__ \
  \____\__,_|_|_|___/

  Adjustment of the calls inside a graph.

*/

Sebastian Hack's avatar
Sebastian Hack committed
306
/**
307
308
 * Transform a call node into a be_Call node.
 *
Sebastian Hack's avatar
Sebastian Hack committed
309
 * @param env The ABI environment for the current irg.
310
311
312
 * @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
313
 */
Matthias Braun's avatar
Matthias Braun committed
314
static ir_node *adjust_call(be_abi_irg_t *env, ir_node *irn, ir_node *curr_sp)
Sebastian Hack's avatar
Sebastian Hack committed
315
{
Matthias Braun's avatar
Matthias Braun committed
316
317
318
319
320
321
322
323
324
325
326
	ir_graph         *const irg       = get_irn_irg(irn);
	const arch_env_t *const arch_env  = be_get_irg_arch_env(irg);
	ir_type                *call_tp   = get_Call_type(irn);
	ir_node                *call_ptr  = get_Call_ptr(irn);
	size_t            const n_params  = get_method_n_params(call_tp);
	ir_node          *      curr_mem  = get_Call_mem(irn);
	ir_node          *const bl        = get_nodes_block(irn);
	const arch_register_t  *sp        = arch_env->sp;
	be_abi_call_t    *const call      = be_abi_call_new();
	ir_mode          *const mach_mode = sp->reg_class->mode;
	size_t            const n_res     = get_method_n_ress(call_tp);
Sebastian Hack's avatar
Sebastian Hack committed
327
328

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

	/* Insert code to put the stack arguments on the stack. */
332
	assert((size_t)get_Call_n_params(irn) == n_params);
Matthias Braun's avatar
Matthias Braun committed
333
334
335
336
	int *const stack_param_idx = ALLOCAN(int, n_params);
	int        stack_size      = 0;
	int        n_stack_params  = 0;
	for (size_t p = 0; p < n_params; ++p) {
337
		be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
338
		assert(arg);
339
		if (!arg->in_reg) {
340
			int arg_size = get_type_size_bytes(get_method_param_type(call_tp, p));
Michael Beck's avatar
Michael Beck committed
341
342
343
344

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

346
			stack_param_idx[n_stack_params++] = p;
Sebastian Hack's avatar
Sebastian Hack committed
347
348
349
350
		}
	}

	/* Collect all arguments which are passed in registers. */
Matthias Braun's avatar
Matthias Braun committed
351
352
353
	int *const reg_param_idxs = ALLOCAN(int, n_params);
	int        n_reg_params   = 0;
	for (size_t p = 0; p < n_params; ++p) {
354
		be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
355
		if (arg && arg->in_reg) {
356
			reg_param_idxs[n_reg_params++] = p;
Sebastian Hack's avatar
Sebastian Hack committed
357
358
359
		}
	}

360
361
362
363
364
365
366
367
368
	/*
	 * 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.
	 */
369
	curr_sp = be_new_IncSP(sp, bl, curr_sp, stack_size, 1);
370

Matthias Braun's avatar
Matthias Braun committed
371
	dbg_info *dbgi = get_irn_dbg_info(irn);
Sebastian Hack's avatar
Sebastian Hack committed
372
	/* If there are some parameters which shall be passed on the stack. */
373
	if (n_stack_params > 0) {
374
375
376
		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
377

378
		curr_mem = get_Call_mem(irn);
379
		in[n_in++] = curr_mem;
380

Matthias Braun's avatar
Matthias Braun committed
381
		for (int i = 0; i < n_stack_params; ++i) {
382
			int p                  = stack_param_idx[i];
383
			be_abi_call_arg_t *arg = get_call_arg(call, 0, p, 0);
384
385
386
			ir_node *param         = get_Call_param(irn, p);
			ir_node *addr          = curr_sp;
			ir_node *mem           = NULL;
387
			ir_type *param_type    = get_method_param_type(call_tp, p);
388
389
			int param_size         = get_type_size_bytes(param_type) + arg->space_after;

390
391
392
393
394
			/*
			 * If we wanted to build the arguments sequentially,
			 * the stack pointer for the next must be incremented,
			 * and the memory value propagated.
			 */
395
396
397
398
399
400
401
402
			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;
403
				}
404
405
				addr = new_r_Const_long(irg, constmode, curr_ofs);
				addr = new_r_Add(bl, curr_sp, addr, mach_mode);
Sebastian Hack's avatar
Sebastian Hack committed
406
407
408
			}

			/* Insert a store for primitive arguments. */
409
			if (is_atomic_type(param_type)) {
410
				ir_node *nomem     = get_irg_no_mem(irg);
411
				ir_node *mem_input = nomem;
412
				ir_node *store     = new_rd_Store(dbgi, bl, mem_input, addr, param, cons_none);
413
				mem   = new_r_Proj(store, mode_M, pn_Store_M);
414
415
			} else {
				/* Make a mem copy for compound arguments. */
Sebastian Hack's avatar
Sebastian Hack committed
416
				assert(mode_is_reference(get_irn_mode(param)));
417
418
419
420
421

				bool is_volatile = is_partly_volatile(addr) ||
					is_partly_volatile(param);

				mem = new_rd_CopyB(dbgi, bl, curr_mem, addr, param, param_type, is_volatile ? cons_volatile : cons_none);
Sebastian Hack's avatar
Sebastian Hack committed
422
423
424
425
			}

			curr_ofs += param_size;

426
			in[n_in++] = mem;
Sebastian Hack's avatar
Sebastian Hack committed
427
428
429
		}

		/* We need the sync only, if we didn't build the stores sequentially. */
430
431
432
433
		if (n_stack_params >= 1) {
			curr_mem = new_r_Sync(bl, n_in, in);
		} else {
			curr_mem = get_Call_mem(irn);
434
		}
Sebastian Hack's avatar
Sebastian Hack committed
435
436
	}

437
438
	/* Put caller save into the destroyed set and state registers in the states
	 * set */
Matthias Braun's avatar
Matthias Braun committed
439
440
441
	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);
	for (int i = 0, n = arch_env->n_register_classes; i < n; ++i) {
442
		const arch_register_class_t *cls = &arch_env->register_classes[i];
Matthias Braun's avatar
Matthias Braun committed
443
		for (unsigned j = 0; j < cls->n_regs; ++j) {
Sebastian Hack's avatar
Sebastian Hack committed
444
			const arch_register_t *reg = arch_register_for_index(cls, j);
445

446
447
448
449
450
			/* 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;

451
			if (reg->type & arch_register_type_state) {
452
453
454
455
456
457
				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;
			}
458
459
			if (arch_register_is_caller_save(arch_env, reg))
				ARR_APP1(const arch_register_t*, destroyed_regs, reg);
Sebastian Hack's avatar
Sebastian Hack committed
460
461
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
462

Christoph Mallon's avatar
Christoph Mallon committed
463
	/* search the largest result proj number */
Matthias Braun's avatar
Matthias Braun committed
464
465
	ir_node **const res_projs = ALLOCANZ(ir_node*, n_res);
	ir_node  *      res_proj  = NULL;
Sebastian Hack's avatar
Sebastian Hack committed
466
	foreach_out_edge(irn, edge) {
467
		ir_node *irn = get_edge_src_irn(edge);
Sebastian Hack's avatar
Sebastian Hack committed
468

469
		if (!is_Proj(irn) || get_Proj_proj(irn) != pn_Call_T_result)
Matthias Braun's avatar
Matthias Braun committed
470
471
472
			continue;

		foreach_out_edge(irn, res_edge) {
473
474
			ir_node *const res  = get_edge_src_irn(res_edge);
			long     const proj = get_Proj_proj(res);
Matthias Braun's avatar
Matthias Braun committed
475
			assert(proj < (long)n_res);
Matthias Braun's avatar
Matthias Braun committed
476
			assert(res_projs[proj] == NULL);
Matthias Braun's avatar
Matthias Braun committed
477
			res_projs[proj] = res;
Sebastian Hack's avatar
Sebastian Hack committed
478
		}
Matthias Braun's avatar
Matthias Braun committed
479
480
		res_proj = irn;
		break;
Sebastian Hack's avatar
Sebastian Hack committed
481
	}
482

Matthias Braun's avatar
Matthias Braun committed
483
	/** TODO: this is not correct for cases where return values are passed
Christoph Mallon's avatar
Christoph Mallon committed
484
	 * on the stack, but no known ABI does this currently...
Matthias Braun's avatar
Matthias Braun committed
485
	 */
Matthias Braun's avatar
Matthias Braun committed
486
	int n_reg_results = n_res;
Sebastian Hack's avatar
Sebastian Hack committed
487

Matthias Braun's avatar
Matthias Braun committed
488
489
	int       n_ins = 0;
	ir_node **in    = ALLOCAN(ir_node*, n_reg_params + ARR_LEN(states));
490

491
	/* make the back end call node and set its register requirements. */
Matthias Braun's avatar
Matthias Braun committed
492
	for (int i = 0; i < n_reg_params; ++i) {
493
		in[n_ins++] = get_Call_param(irn, reg_param_idxs[i]);
494
	}
495
496

	/* add state registers ins */
Matthias Braun's avatar
Matthias Braun committed
497
	for (size_t s = 0; s < ARR_LEN(states); ++s) {
Matthias Braun's avatar
Matthias Braun committed
498
		const arch_register_t       *reg = states[s];
499
500
		const arch_register_class_t *cls = reg->reg_class;
		ir_node *regnode = new_r_Unknown(irg, cls->mode);
501
		in[n_ins++]      = regnode;
502
	}
503
	assert(n_ins == (int) (n_reg_params + ARR_LEN(states)));
504

505
	/* ins collected, build the call */
Matthias Braun's avatar
Matthias Braun committed
506
	ir_node *low_call;
507
	if (env->call->flags.call_has_imm && is_Address(call_ptr)) {
508
		/* direct call */
509
		low_call = be_new_Call(dbgi, bl, curr_mem, sp->single_req, curr_sp,
510
		                       sp->single_req, curr_sp,
511
		                       n_reg_results + pn_be_Call_first_res + ARR_LEN(destroyed_regs),
Matthias Braun's avatar
Matthias Braun committed
512
		                       n_ins, in, get_Call_type(irn));
513
		be_Call_set_entity(low_call, get_Address_entity(call_ptr));
514
	} else {
515
		/* indirect call */
516
		low_call = be_new_Call(dbgi, bl, curr_mem, sp->single_req, curr_sp,
517
		                       sp->reg_class->class_req, call_ptr,
518
		                       n_reg_results + pn_be_Call_first_res + ARR_LEN(destroyed_regs),
519
		                       n_ins, in, get_Call_type(irn));
Sebastian Hack's avatar
Sebastian Hack committed
520
	}
Matthias Braun's avatar
Matthias Braun committed
521
	int throws_exception = ir_throws_exception(irn);
522
	ir_set_throws_exception(low_call, throws_exception);
523
	be_Call_set_pop(low_call, call->pop);
524
525

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

Matthias Braun's avatar
Matthias Braun committed
528
	/* create new stack pointer */
529
	curr_sp = new_r_Proj(low_call, get_irn_mode(curr_sp), pn_be_Call_sp);
530
531
	be_set_constr_single_reg_out(low_call, pn_be_Call_sp, sp,
			arch_register_req_type_ignore | arch_register_req_type_produces_sp);
532
	arch_set_irn_register(curr_sp, sp);
Matthias Braun's avatar
Matthias Braun committed
533

534
	/* now handle results */
Matthias Braun's avatar
Matthias Braun committed
535
	for (size_t i = 0; i < n_res; ++i) {
Matthias Braun's avatar
Matthias Braun committed
536
		ir_node           *proj = res_projs[i];
537
		be_abi_call_arg_t *arg  = get_call_arg(call, 1, i, 0);
Matthias Braun's avatar
Matthias Braun committed
538

Matthias Braun's avatar
Matthias Braun committed
539
540
541
		/* returns values on stack not supported yet */
		assert(arg->in_reg);

Matthias Braun's avatar
Matthias Braun committed
542
543
544
545
546
		/*
			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
		*/
547
		long pn = i + pn_be_Call_first_res;
Matthias Braun's avatar
Matthias Braun committed
548

549
		if (proj == NULL) {
550
			ir_type *res_type = get_method_res_type(call_tp, i);
Matthias Braun's avatar
Matthias Braun committed
551
			ir_mode *mode     = get_type_mode(res_type);
552
			proj              = new_r_Proj(low_call, mode, pn);
Matthias Braun's avatar
Matthias Braun committed
553
554
555
556
557
558
559
			res_projs[i]      = proj;
		} else {
			set_Proj_pred(proj, low_call);
			set_Proj_proj(proj, pn);
		}

		if (arg->in_reg) {
560
			/* remove register from destroyed regs */
Matthias Braun's avatar
Matthias Braun committed
561
			for (size_t j = 0, n = ARR_LEN(destroyed_regs); j < n; ++j) {
562
563
564
565
566
567
				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
568
569
570
		}
	}

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

Sebastian Hack's avatar
Sebastian Hack committed
573
	/* Set the register classes and constraints of the Call parameters. */
Matthias Braun's avatar
Matthias Braun committed
574
	for (int i = 0; i < n_reg_params; ++i) {
575
		int index = reg_param_idxs[i];
576
		be_abi_call_arg_t *arg = get_call_arg(call, 0, index, 0);
Sebastian Hack's avatar
Sebastian Hack committed
577
		assert(arg->reg != NULL);
578

579
		be_set_constr_single_reg_in(low_call, n_be_Call_first_arg + i,
580
		                            arg->reg, arch_register_req_type_none);
Sebastian Hack's avatar
Sebastian Hack committed
581
582
583
	}

	/* Set the register constraints of the results. */
Matthias Braun's avatar
Matthias Braun committed
584
	for (size_t i = 0; i < n_res; ++i) {
Matthias Braun's avatar
Matthias Braun committed
585
		ir_node                 *proj = res_projs[i];
586
		const be_abi_call_arg_t *arg  = get_call_arg(call, 1, i, 0);
Matthias Braun's avatar
Matthias Braun committed
587
		int                      pn   = get_Proj_proj(proj);
588

Sebastian Hack's avatar
Sebastian Hack committed
589
		assert(arg->in_reg);
590
591
		be_set_constr_single_reg_out(low_call, pn, arg->reg,
		                             arch_register_req_type_none);
592
		arch_set_irn_register(proj, arg->reg);
Sebastian Hack's avatar
Sebastian Hack committed
593
	}
594
595
	exchange(irn, low_call);

Matthias Braun's avatar
Matthias Braun committed
596
	/* kill the ProjT node */
597
	if (res_proj != NULL) {
598
		kill_node(res_proj);
599
600
	}

Sebastian Hack's avatar
Sebastian Hack committed
601
602
	/* Make additional projs for the caller save registers
	   and the Keep node which keeps them alive. */
Matthias Braun's avatar
Matthias Braun committed
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
	int       max_keep_ins = ARR_LEN(destroyed_regs) + n_reg_results + 1;
	ir_node **keep_in      = ALLOCAN(ir_node *, max_keep_ins);
	int       n            = 0;

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

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

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

Matthias Braun's avatar
Matthias Braun committed
621
622
623
624
		set_irn_link(proj, (void*) reg);
		keep_in[n++] = proj;
		++curr_res_proj;
	}
Matthias Braun's avatar
Matthias Braun committed
625

Matthias Braun's avatar
Matthias Braun committed
626
627
628
629
630
631
632
633
634
635
636
637
638
	for (int i = 0; i < n_reg_results; ++i) {
		ir_node *proj = res_projs[i];
		const arch_register_t *reg = arch_get_irn_register(proj);
		set_irn_link(proj, (void*) reg);
		keep_in[n++] = proj;
	}
	assert(n <= max_keep_ins);

	/* create the Keep for the caller save registers */
	ir_node *keep = be_new_Keep(bl, n, keep_in);
	for (int i = 0; i < n; ++i) {
		const arch_register_t *reg = (const arch_register_t*)get_irn_link(keep_in[i]);
		be_node_set_reg_class_in(keep, i, reg->reg_class);
Sebastian Hack's avatar
Sebastian Hack committed
639
640
641
	}

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

645
	if (stack_size > 0) {
646
647
648
649
		ir_node *mem_proj = NULL;

		foreach_out_edge(low_call, edge) {
			ir_node *irn = get_edge_src_irn(edge);
650
			if (is_Proj(irn) && get_Proj_proj(irn) == pn_Call_M) {
651
652
653
654
				mem_proj = irn;
				break;
			}
		}
Sebastian Hack's avatar
Sebastian Hack committed
655

Matthias Braun's avatar
Matthias Braun committed
656
		if (mem_proj == NULL) {
657
			mem_proj = new_r_Proj(low_call, mode_M, pn_be_Call_M);
Sebastian Hack's avatar
Sebastian Hack committed
658
659
			keep_alive(mem_proj);
		}
660
661
	}
	/* Clean up the stack frame or revert alignment fixes if we allocated it */
662
	curr_sp = be_new_IncSP(sp, bl, curr_sp, -stack_size, 0);
Sebastian Hack's avatar
Sebastian Hack committed
663
664

	be_abi_call_free(call);
665

666
667
	DEL_ARR_F(states);
	DEL_ARR_F(destroyed_regs);
668
669
670
671

	return curr_sp;
}

672
673
674
675
676
/**
 * 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
677
 * @param block      the block where new nodes are allocated on
678
679
680
681
 * @param dbg        debug info for new nodes
 *
 * @return a node representing the aligned size
 */
682
static ir_node *adjust_alloc_size(unsigned stack_alignment, ir_node *size,
683
                                  ir_node *block, dbg_info *dbg)
684
{
Matthias Braun's avatar
Matthias Braun committed
685
686
687
688
	assert(is_po2(stack_alignment));
	if (stack_alignment <= 1)
		return size;

689
	ir_mode  *mode = get_irn_mode(size);
690
	ir_graph *irg  = get_irn_irg(block);
691
	ir_node  *mask = new_r_Const_long(irg, mode, stack_alignment - 1);
Matthias Braun's avatar
Matthias Braun committed
692
	size = new_rd_Add(dbg, block, size, mask, mode);
693
	mask = new_r_Const_long(irg, mode, -(long)stack_alignment);
Matthias Braun's avatar
Matthias Braun committed
694
	size = new_rd_And(dbg, block, size, mask, mode);
695
696
	return size;
}
697
698
/**
 * Adjust an alloca.
699
700
 * The alloca is transformed into a back end alloca node and connected to the
 * stack nodes.
701
 */
Matthias Braun's avatar
Matthias Braun committed
702
static ir_node *adjust_alloc(be_abi_irg_t *env, ir_node *alloc, ir_node *curr_sp)
703
{
704
	ir_node          *block     = get_nodes_block(alloc);
705
	ir_graph         *irg       = get_irn_irg(alloc);
706
	const arch_env_t *arch_env  = be_get_irg_arch_env(irg);
707

Matthias Braun's avatar
Matthias Braun committed
708
709
	ir_node *alloc_mem = NULL;
	ir_node *alloc_res = NULL;
710
711
	foreach_out_edge(alloc, edge) {
		ir_node *irn = get_edge_src_irn(edge);
712

713
		switch (get_Proj_proj(irn)) {
714
715
716
717
718
719
720
721
		case pn_Alloc_M:
			alloc_mem = irn;
			break;
		case pn_Alloc_res:
			alloc_res = irn;
			break;
		default:
			break;
722
		}
723
	}
724

725
726
727
728
729
730
731
732
	/* 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;
	}

733
734
	dbg_info *dbg  = get_irn_dbg_info(alloc);
	ir_node  *size = get_Alloc_size(alloc);
735

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

Matthias Braun's avatar
Matthias Braun committed
740
741
742
	unsigned stack_alignment = 1 << arch_env->stack_alignment;
	size = adjust_alloc_size(stack_alignment, size, block, dbg);
	ir_node *new_alloc = be_new_AddSP(arch_env->sp, block, curr_sp, size);
743
	set_irn_dbg_info(new_alloc, dbg);
744

745
	if (alloc_mem != NULL) {
Matthias Braun's avatar
Matthias Braun committed
746
		ir_node *addsp_mem = new_r_Proj(new_alloc, mode_M, pn_be_AddSP_M);
747

748
749
		/* We need to sync the output mem of the AddSP with the input mem
		   edge into the alloc node. */
Matthias Braun's avatar
Matthias Braun committed
750
751
		ir_node *ins[] = { get_Alloc_mem(alloc), addsp_mem };
		ir_node *sync  = new_r_Sync(block, ARRAY_SIZE(ins), ins);
752

753
754
		exchange(alloc_mem, sync);
	}
755

756
	exchange(alloc, new_alloc);
757

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

761
	curr_sp = new_r_Proj(new_alloc,  get_irn_mode(curr_sp), pn_be_AddSP_sp);
762

763
	return curr_sp;
764
}
765
766
767
768
769
770
771

/**
 * 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)
{
772
#if 0
773
	/* we might need to multiply the size with the element size */
Matthias Braun's avatar
Matthias Braun committed
774
775
776
777
778
	ir_type  *type  = get_Free_type(free);
	ir_node  *block = get_nodes_block(free);
	ir_graph *irg   = get_irn_irg(free);
	dbg_info *dbg   = get_irn_dbg_info(free);
	ir_node  *size;
779
	if (!is_unknown_type(type) && get_type_size_bytes(type) != 1) {
780
781
		ir_node *const cnst = new_rd_Const(dbg, irg, mode_Iu, get_type_size_bytes(type));
		ir_node *const mul  = new_rd_Mul(dbg, block, get_Free_count(free), cnst, mode_Iu);
782
783
		size = mul;
	} else {
784
		size = get_Free_count(free);
785
	}
786

Matthias Braun's avatar
Matthias Braun committed
787
788
789
	const arch_env_t *arch_env        = be_get_irg_arch_env(irg);
	unsigned          stack_alignment = 1 << arch_env->stack_alignment;
	size = adjust_alloc_size(stack_alignment, size, block, dbg);
790

791
792
	/* The stack pointer will be modified in an unknown manner.
	   We cannot omit it. */
793
	env->call->flags.try_omit_fp = 0;
Matthias Braun's avatar
Matthias Braun committed
794
	ir_node *subsp = be_new_SubSP(arch_env->sp, block, curr_sp, size);
795
	set_irn_dbg_info(subsp, dbg);
796

Matthias Braun's avatar
Matthias Braun committed
797
798
799
	ir_node *mem     = new_r_Proj(subsp, mode_M, pn_be_SubSP_M);
	ir_mode *sp_mode = arch_env->sp->reg_class->mode;
	ir_node *res     = new_r_Proj(subsp, sp_mode, pn_be_SubSP_sp);
800

801
	/* we need to sync the memory */
Matthias Braun's avatar
Matthias Braun committed
802
803
	ir_node *in[] = { get_Free_mem(free), mem };
	ir_node *sync = new_r_Sync(block, ARRAY_SIZE(in), in);
804
805
806
807
808
809

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

	/* kill the free */
	exchange(free, sync);
810
	curr_sp = res;
811
	return curr_sp;
812
813
814
815
816
#endif
	(void)env;
	(void)free;
	(void)curr_sp;
	panic("beabi: Free nodes do not work properly yet");
Sebastian Hack's avatar
Sebastian Hack committed
817
818
}

819
820
821
822
823
824
825
/**
 * 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.
 */
Matthias Braun's avatar
Matthias Braun committed
826
static bool dependent_on(ir_node *n1, ir_node *n2)
827
{
828
	assert(get_nodes_block(n1) == get_nodes_block(n2));
829
	return heights_reachable_in_block(ir_heights, n1, n2);
830
831
}

Matthias Braun's avatar
Matthias Braun committed
832
static int cmp_call_dependency(const void *c1, const void *c2)
833
{
Matthias Braun's avatar
Matthias Braun committed
834
835
836
837
838
	/* 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
	 */
839
840
	ir_node *n1 = *(ir_node **) c1;
	ir_node *n2 = *(ir_node **) c2;
841
842
843
844
845
846
	if (dependent_on(n1, n2))
		return -1;

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

847
	/* The nodes have no depth order, but we need a total order because qsort()
Andreas Zwinkau's avatar
Andreas Zwinkau committed
848
849
850
851
852
	 * is not stable.
	 *
	 * Additionally, we need to respect transitive dependencies. Consider a
	 * Call a depending on Call b and an independent Call c.
	 * We MUST NOT order c > a and b > c. */
Matthias Braun's avatar
Matthias Braun committed
853
854
	unsigned h1 = get_irn_height(ir_heights, n1);
	unsigned h2 = get_irn_height(ir_heights, n2);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
855
856
857
	if (h1 < h2) return -1;
	if (h1 > h2) return  1;
	/* Same height, so use a random (but stable) order */
858
	return get_irn_idx(n1) - get_irn_idx(n2);
859
860
}

861
/**
862
 * Walker: links all Call/Alloc/Free nodes to the Block they are contained.
863
 */
864
static void link_ops_in_block_walker(ir_node *irn, void *data)
865
{
866
867
	be_abi_irg_t *env  = (be_abi_irg_t*)data;
	unsigned      code = get_irn_opcode(irn);
868

869
	if (code == iro_Call || code == iro_Alloc || code == iro_Free) {
Sebastian Hack's avatar
Sebastian Hack committed
870
871
872
		ir_node *bl       = get_nodes_block(irn);
		void *save        = get_irn_link(bl);

873
874
875
		set_irn_link(irn, save);
		set_irn_link(bl, irn);
	}
876
877
878

	if (code == iro_Builtin && get_Builtin_kind(irn) == ir_bk_return_address) {
		ir_node       *param = get_Builtin_param(irn, 0);
Matthias Braun's avatar
Matthias Braun committed
879
		ir_tarval     *tv    = get_Const_tarval(param);
880
881
882
		unsigned long  value = get_tarval_long(tv);
		/* use ebp, so the climbframe algo works... */
		if (value > 0) {
883
			env->call->flags.try_omit_fp = 0;
884
885
		}
	}
886
887
888
}

/**
889
 * Block-walker:
890
 * Process all Call/Alloc/Free nodes inside a basic block.
891
 * Note that the link field of the block must contain a linked list of all
Michael Beck's avatar
Michael Beck committed
892
893
 * nodes inside the Block. We first order this list according to data dependency
 * and that connect the nodes together.
894
 */
895
static void process_ops_in_block(ir_node *bl, void *data)
896
{
Matthias Braun's avatar
Matthias Braun committed
897
898
	int n_nodes = 0;
	for (ir_node *irn = (ir_node*)get_irn_link(bl); irn != NULL;
899
	     irn = (ir_node*)get_irn_link(irn)) {
900
901
902