beabi.c 47.9 KB
Newer Older
Sebastian Hack's avatar
Sebastian Hack committed
1
2
3
/**
 * ABI lowering.
 *
4
5
 * @author Sebastian Hack
 * @date 7.3.2005
Sebastian Hack's avatar
Sebastian Hack committed
6
7
 */

Michael Beck's avatar
Michael Beck committed
8
9
10
#ifdef HAVE_CONFIG_H
# include "config.h"
#endif
11

Sebastian Hack's avatar
Sebastian Hack committed
12
#include "obst.h"
13
#include "offset.h"
Sebastian Hack's avatar
Sebastian Hack committed
14
15

#include "type.h"
16
#include "irgopt.h"
Sebastian Hack's avatar
Sebastian Hack committed
17
18
19
20
21
22
23

#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
24
#include "irprintf_t.h"
25
#include "irgopt.h"
Sebastian Hack's avatar
Sebastian Hack committed
26
27
28
29
30

#include "be.h"
#include "beabi.h"
#include "bearch.h"
#include "benode_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
31
#include "belive_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
32
#include "besched_t.h"
Sebastian Hack's avatar
Sebastian Hack committed
33
34
35
36
37

#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(x, y) ((x) < (y) ? (x) : (y))

typedef struct _be_abi_call_arg_t {
38
39
40
	unsigned is_res   : 1;
	unsigned in_reg   : 1;
	unsigned on_stack : 1;
Sebastian Hack's avatar
Sebastian Hack committed
41
42
43

	int pos;
	const arch_register_t *reg;
44
	entity *stack_ent;
45
	unsigned alignment;
46
47
	unsigned space_before;
	unsigned space_after;
Sebastian Hack's avatar
Sebastian Hack committed
48
49
50
51
} be_abi_call_arg_t;

struct _be_abi_call_t {
	be_abi_call_flags_t flags;
52
	const be_abi_callbacks_t *cb;
53
	type *between_type;
Sebastian Hack's avatar
Sebastian Hack committed
54
55
56
	set *params;
};

Sebastian Hack's avatar
Sebastian Hack committed
57
58
#define N_FRAME_TYPES 3

59
60
61
62
63
typedef struct _be_stack_frame_t {
	type *arg_type;
	type *between_type;
	type *frame_type;

Sebastian Hack's avatar
Sebastian Hack committed
64
	type *order[N_FRAME_TYPES];        /**< arg, between and frame types ordered. */
65
66
67
68
69
70
71
72
73
74

	int initial_offset;
	int stack_dir;
} be_stack_frame_t;

struct _be_stack_slot_t {
	struct _be_stack_frame_t *frame;
	entity *ent;
};

Sebastian Hack's avatar
Sebastian Hack committed
75
struct _be_abi_irg_t {
Sebastian Hack's avatar
Sebastian Hack committed
76
	struct obstack       obst;
Sebastian Hack's avatar
Sebastian Hack committed
77
78
	be_stack_frame_t     *frame;        /**< The stack frame model. */
	const be_irg_t       *birg;         /**< The back end IRG. */
Sebastian Hack's avatar
Sebastian Hack committed
79
80
81
	const arch_isa_t     *isa;          /**< The isa. */
	survive_dce_t        *dce_survivor;

Sebastian Hack's avatar
Sebastian Hack committed
82
83
	be_abi_call_t        *call;         /**< The ABI call information. */
	type                 *method_type;  /**< The type of the method of the IRG. */
Sebastian Hack's avatar
Sebastian Hack committed
84

Sebastian Hack's avatar
Sebastian Hack committed
85
	ir_node              *init_sp;      /**< The node representing the stack pointer
Sebastian Hack's avatar
Sebastian Hack committed
86
87
									     at the start of the function. */

Sebastian Hack's avatar
Sebastian Hack committed
88
89
90
91
92
93
94
95
	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. */

	pset                 *stack_phis;   /**< The set of all Phi nodes inserted due to
											stack pointer modifying nodes. */

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

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

Sebastian Hack's avatar
Sebastian Hack committed
99
100
	arch_irn_handler_t irn_handler;
	arch_irn_ops_t     irn_ops;
101
	DEBUG_ONLY(firm_dbg_module_t    *dbg;)          /**< The debugging module. */
Sebastian Hack's avatar
Sebastian Hack committed
102
};
Sebastian Hack's avatar
Sebastian Hack committed
103

104
105
#define get_abi_from_handler(ptr) firm_container_of(ptr, be_abi_irg_t, irn_handler)
#define get_abi_from_ops(ptr)     firm_container_of(ptr, be_abi_irg_t, irn_ops)
Sebastian Hack's avatar
Sebastian Hack committed
106

Sebastian Hack's avatar
Sebastian Hack committed
107
108
109
/* Forward, since be need it in be_abi_introduce(). */
static const arch_irn_ops_if_t abi_irn_ops;
static const arch_irn_handler_t abi_irn_handler;
110

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

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

Michael Beck's avatar
Michael Beck committed
122
123
124
/**
 * Set compare function: compares two ABI call object arguments.
 */
Sebastian Hack's avatar
Sebastian Hack committed
125
126
127
128
129
130
static int cmp_call_arg(const void *a, const void *b, size_t n)
{
	const be_abi_call_arg_t *p = a, *q = b;
	return !(p->is_res == q->is_res && p->pos == q->pos);
}

Michael Beck's avatar
Michael Beck committed
131
132
133
134
135
136
137
138
/**
 * 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
 */
Sebastian Hack's avatar
Sebastian Hack committed
139
140
141
142
143
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;

144
	memset(&arg, 0, sizeof(arg));
Sebastian Hack's avatar
Sebastian Hack committed
145
146
147
	arg.is_res = is_res;
	arg.pos    = pos;

Michael Beck's avatar
Michael Beck committed
148
	hash = is_res * 128 + pos;
Sebastian Hack's avatar
Sebastian Hack committed
149
150
151
152
153
154

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

Michael Beck's avatar
Michael Beck committed
155
156
157
158
159
160
161
/**
 * 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
 */
Sebastian Hack's avatar
Sebastian Hack committed
162
163
164
165
166
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);
}

Michael Beck's avatar
Michael Beck committed
167
/* Set the flags for a call. */
168
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
169
{
170
171
	call->flags        = flags;
	call->cb           = cb;
Sebastian Hack's avatar
Sebastian Hack committed
172
173
}

174
void be_abi_call_param_stack(be_abi_call_t *call, int arg_pos, unsigned alignment, unsigned space_before, unsigned space_after)
Sebastian Hack's avatar
Sebastian Hack committed
175
176
{
	be_abi_call_arg_t *arg = get_or_set_call_arg(call, 0, arg_pos, 1);
177
178
179
180
	arg->on_stack     = 1;
	arg->alignment    = alignment;
	arg->space_before = space_before;
	arg->space_after  = space_after;
181
	assert(alignment > 0 && "Alignment must be greater than 0");
Sebastian Hack's avatar
Sebastian Hack committed
182
183
184
185
186
}

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);
187
	arg->in_reg = 1;
Sebastian Hack's avatar
Sebastian Hack committed
188
189
190
191
192
193
	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);
194
	arg->in_reg = 1;
Sebastian Hack's avatar
Sebastian Hack committed
195
196
197
	arg->reg = reg;
}

Michael Beck's avatar
Michael Beck committed
198
/* Get the flags of a ABI call object. */
199
200
201
202
203
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
204
205
206
207
208
209
/**
 * Constructor for a new ABI call object.
 *
 * @return the new ABI call object
 */
static be_abi_call_t *be_abi_call_new(void)
Sebastian Hack's avatar
Sebastian Hack committed
210
{
Michael Beck's avatar
Michael Beck committed
211
	be_abi_call_t *call = xmalloc(sizeof(call[0]));
Sebastian Hack's avatar
Sebastian Hack committed
212
213
214
	call->flags.val  = 0;
	call->params     = new_set(cmp_call_arg, 16);
	call->cb         = NULL;
Sebastian Hack's avatar
Sebastian Hack committed
215
216
217
	return call;
}

Michael Beck's avatar
Michael Beck committed
218
219
220
221
/**
 * Destructor for an ABI call object.
 */
static void be_abi_call_free(be_abi_call_t *call)
Sebastian Hack's avatar
Sebastian Hack committed
222
223
224
225
226
{
	del_set(call->params);
	free(call);
}

Sebastian Hack's avatar
Sebastian Hack committed
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
/*
  _____                           _   _                 _ _ _
 |  ___| __ __ _ _ __ ___   ___  | | | | __ _ _ __   __| | (_)_ __   __ _
 | |_ | '__/ _` | '_ ` _ \ / _ \ | |_| |/ _` | '_ \ / _` | | | '_ \ / _` |
 |  _|| | | (_| | | | | | |  __/ |  _  | (_| | | | | (_| | | | | | | (_| |
 |_|  |_|  \__,_|_| |_| |_|\___| |_| |_|\__,_|_| |_|\__,_|_|_|_| |_|\__, |
                                                                    |___/

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

244
245
static int get_stack_entity_offset(be_stack_frame_t *frame, entity *ent, int bias)
{
Sebastian Hack's avatar
Sebastian Hack committed
246
	type *t = get_entity_owner(ent);
247
248
249
250
251
	int ofs = get_entity_offset_bytes(ent);

	int i, index;

	/* Find the type the entity is contained in. */
Sebastian Hack's avatar
Sebastian Hack committed
252
	for(index = 0; index < N_FRAME_TYPES; ++index) {
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
		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;
}

Michael Beck's avatar
Michael Beck committed
270
271
272
/**
 * Retrieve the entity with given offset from a frame type.
 */
Sebastian Hack's avatar
Sebastian Hack committed
273
274
275
276
277
278
279
280
281
282
283
284
285
286
static entity *search_ent_with_offset(type *t, int offset)
{
	int i, n;

	for(i = 0, n = get_class_n_members(t); i < n; ++i) {
		entity *ent = get_class_member(t, i);
		if(get_entity_offset_bytes(ent) == offset)
			return ent;
	}

	return NULL;
}

static int stack_frame_compute_initial_offset(be_stack_frame_t *frame)
287
{
Sebastian Hack's avatar
Sebastian Hack committed
288
289
	type   *base = frame->stack_dir < 0 ? frame->between_type : frame->frame_type;
	entity *ent  = search_ent_with_offset(base, 0);
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
	frame->initial_offset = 0;
	frame->initial_offset = get_stack_entity_offset(frame, ent, 0);
	return frame->initial_offset;
}

static be_stack_frame_t *stack_frame_init(be_stack_frame_t *frame, type *args, type *between, type *locals, int stack_dir)
{
	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;

	if(stack_dir > 0) {
		frame->order[0] = args;
		frame->order[2] = locals;
	}

	else {
		frame->order[0] = locals;
		frame->order[2] = args;
	}

	return frame;
}

Sebastian Hack's avatar
Sebastian Hack committed
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
static void stack_frame_dump(FILE *file, be_stack_frame_t *frame)
{
	int i, j, n;

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

		ir_fprintf(file, "type %d: %Fm size: %d\n", j, t, get_type_size_bytes(t));
		for(i = 0, n = get_class_n_members(t); i < n; ++i) {
			entity *ent = get_class_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));
		}
	}
}

Michael Beck's avatar
Michael Beck committed
333
/**
Michael Beck's avatar
Michael Beck committed
334
 * If irn is a Sel node computes the address of an entity
Michael Beck's avatar
Michael Beck committed
335
336
 * on the frame type return the entity, else NULL.
 */
337
338
static INLINE entity *get_sel_ent(ir_node *irn)
{
Michael Beck's avatar
Michael Beck committed
339
	if(is_Sel(irn) && get_Sel_ptr(irn) == get_irg_frame(get_irn_irg(irn))) {
340
341
342
343
344
345
		return get_Sel_entity(irn);
	}

	return NULL;
}

Michael Beck's avatar
Michael Beck committed
346
347
348
349
/**
 * Walker: Replaces Loads, Stores and Sels of frame type entities
 * by FrameLoad, FrameStore and FrameAdress.
 */
350
351
352
static void lower_frame_sels_walker(ir_node *irn, void *data)
{
	ir_node *nw  = NULL;
353
	entity *ent = get_sel_ent(irn);
354

355
356
357
358
359
	if(ent != NULL) {
		be_abi_irg_t *env = data;
		ir_node *bl       = get_nodes_block(irn);
		ir_graph *irg     = get_irn_irg(bl);
		ir_node *frame    = get_irg_frame(irg);
360

361
		nw = be_new_FrameAddr(env->isa->sp->reg_class, irg, bl, frame, ent);
362
		exchange(irn, nw);
Michael Beck's avatar
Michael Beck committed
363
	}
364
365
}

Michael Beck's avatar
Michael Beck committed
366
367
368
369
/**
 * Returns non-zero if the call argument at given position
 * is transfered on the stack.
 */
Sebastian Hack's avatar
Sebastian Hack committed
370
371
372
373
374
375
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;
}

376
377
378
379
380
381
382
383
384
385
386
/*
   ____      _ _
  / ___|__ _| | |___
 | |   / _` | | / __|
 | |__| (_| | | \__ \
  \____\__,_|_|_|___/

  Adjustment of the calls inside a graph.

*/

Sebastian Hack's avatar
Sebastian Hack committed
387
388
389
/**
 * Transform a call node.
 * @param env The ABI environment for the current irg.
390
391
392
 * @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
393
 */
394
static ir_node *adjust_call(be_abi_irg_t *env, ir_node *irn, ir_node *curr_sp)
Sebastian Hack's avatar
Sebastian Hack committed
395
396
397
398
399
{
	ir_graph *irg             = env->birg->irg;
	const arch_isa_t *isa     = env->birg->main_env->arch_env->isa;
	be_abi_call_t *call       = be_abi_call_new();
	ir_type *mt               = get_Call_type(irn);
Sebastian Hack's avatar
Sebastian Hack committed
400
	ir_node *call_ptr         = get_Call_ptr(irn);
Sebastian Hack's avatar
Sebastian Hack committed
401
402
403
404
405
406
407
408
409
410
	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);
	int stack_size            = 0;
	int stack_dir             = arch_isa_stack_dir(isa);
	const arch_register_t *sp = arch_isa_sp(isa);
	ir_mode *mach_mode        = sp->reg_class->mode;
	struct obstack *obst      = &env->obst;
Sebastian Hack's avatar
Sebastian Hack committed
411
	ir_node *no_mem           = get_irg_no_mem(irg);
412
	int no_alloc              = call->flags.bits.frame_is_setup_on_call;
Sebastian Hack's avatar
Sebastian Hack committed
413
414

	ir_node *res_proj = NULL;
415
	int curr_res_proj = pn_Call_max;
Sebastian Hack's avatar
Sebastian Hack committed
416
417
418
419
420
	int n_low_args    = 0;
	int n_pos         = 0;

	ir_node *low_call;
	ir_node **in;
421
	ir_node **res_projs;
Sebastian Hack's avatar
Sebastian Hack committed
422
423
424
425
426
427
428
429
430
	const ir_edge_t *edge;
	int *low_args;
	int *pos;
	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. */
431
432
	assert(get_Call_n_params(irn) == n_params);
	for(i = 0; i < n_params; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
433
		be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
434
		assert(arg);
435
		if(arg->on_stack) {
436
437
			stack_size += arg->space_before;
			stack_size =  round_up2(stack_size, arg->alignment);
Sebastian Hack's avatar
Sebastian Hack committed
438
			stack_size += get_type_size_bytes(get_method_param_type(mt, i));
439
			stack_size += arg->space_after;
Sebastian Hack's avatar
Sebastian Hack committed
440
441
442
443
444
445
446
			obstack_int_grow(obst, i);
			n_pos++;
		}
	}
	pos = obstack_finish(obst);

	/* Collect all arguments which are passed in registers. */
Sebastian Hack's avatar
Sebastian Hack committed
447
	for(i = 0, n = get_Call_n_params(irn); i < n; ++i) {
Sebastian Hack's avatar
Sebastian Hack committed
448
449
450
451
452
453
454
455
		be_abi_call_arg_t *arg = get_call_arg(call, 0, i);
		if(arg && arg->in_reg) {
			obstack_int_grow(obst, i);
			n_low_args++;
		}
	}
	low_args = obstack_finish(obst);

Sebastian Hack's avatar
Sebastian Hack committed
456
	/* If there are some parameters which shall be passed on the stack. */
Sebastian Hack's avatar
Sebastian Hack committed
457
458
	if(n_pos > 0) {
		int curr_ofs      = 0;
459
		int do_seq        = call->flags.bits.store_args_sequential && !no_alloc;
Sebastian Hack's avatar
Sebastian Hack committed
460
461

		/* Reverse list of stack parameters if call arguments are from left to right */
Sebastian Hack's avatar
Sebastian Hack committed
462
		if(call->flags.bits.left_to_right) {
Sebastian Hack's avatar
Sebastian Hack committed
463
464
465
466
467
468
469
470
471
472
			for(i = 0; i < n_pos / 2; ++i) {
				int other  = n_pos - i - 1;
				int tmp    = pos[i];
				pos[i]     = pos[other];
				pos[other] = tmp;
			}
		}

		/*
		 * If the stack is decreasing and we do not want to store sequentially,
473
		 * or someone else allocated the call frame
Sebastian Hack's avatar
Sebastian Hack committed
474
475
476
		 * we allocate as much space on the stack all parameters need, by
		 * moving the stack pointer along the stack's direction.
		 */
477
		if(stack_dir < 0 && !do_seq && !no_alloc) {
478
			curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, no_mem, stack_size, be_stack_dir_expand);
Sebastian Hack's avatar
Sebastian Hack committed
479
480
		}

Sebastian Hack's avatar
Sebastian Hack committed
481
		assert(mode_is_reference(mach_mode) && "machine mode must be pointer");
Sebastian Hack's avatar
Sebastian Hack committed
482
		for(i = 0; i < n_pos; ++i) {
483
484
485
486
487
488
489
490
491
492
			int p                  = pos[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;
			type *param_type       = get_method_param_type(mt, p);
			int param_size         = get_type_size_bytes(param_type) + arg->space_after;

			curr_ofs += arg->space_before;
			curr_ofs =  round_up2(curr_ofs, arg->alignment);
Sebastian Hack's avatar
Sebastian Hack committed
493
494
495

			/* Make the expression to compute the argument's offset. */
			if(curr_ofs > 0) {
Sebastian Hack's avatar
Sebastian Hack committed
496
				addr = new_r_Const_long(irg, bl, mode_Is, curr_ofs);
Sebastian Hack's avatar
Sebastian Hack committed
497
498
499
500
				addr = new_r_Add(irg, bl, curr_sp, addr, mach_mode);
			}

			/* Insert a store for primitive arguments. */
Sebastian Hack's avatar
Sebastian Hack committed
501
			if(is_atomic_type(param_type)) {
Sebastian Hack's avatar
Sebastian Hack committed
502
503
504
505
				mem = new_r_Store(irg, bl, curr_mem, addr, param);
				mem = new_r_Proj(irg, bl, mem, mode_M, pn_Store_M);
			}

506
			/* Make a mem copy for compound arguments. */
Sebastian Hack's avatar
Sebastian Hack committed
507
508
509
510
511
512
513
514
515
516
517
			else {
				assert(mode_is_reference(get_irn_mode(param)));
				mem = new_r_CopyB(irg, bl, curr_mem, addr, param, param_type);
				mem = new_r_Proj(irg, bl, mem, mode_M, pn_CopyB_M_regular);
			}

			obstack_ptr_grow(obst, mem);

			curr_ofs += param_size;

			/*
Michael Beck's avatar
Michael Beck committed
518
519
520
521
			 * If we wanted to build the arguments sequentially,
			 * the stack pointer for the next must be incremented,
			 * and the memory value propagated.
			 */
Sebastian Hack's avatar
Sebastian Hack committed
522
523
			if(do_seq) {
				curr_ofs = 0;
524
				curr_sp  = be_new_IncSP(sp, irg, bl, curr_sp, no_mem, param_size, be_stack_dir_expand);
Sebastian Hack's avatar
Sebastian Hack committed
525
526
527
528
529
530
531
532
533
534
535
536
537
				curr_mem = mem;
			}
		}

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

		/* We need the sync only, if we didn't build the stores sequentially. */
		if(!do_seq)
			curr_mem = new_r_Sync(irg, bl, n_pos, in);
		obstack_free(obst, in);
	}

	/* Collect caller save registers */
Sebastian Hack's avatar
Sebastian Hack committed
538
539
540
541
542
543
544
545
546
	for(i = 0, n = arch_isa_get_n_reg_class(isa); i < n; ++i) {
		int 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);
		}
	}
Sebastian Hack's avatar
Sebastian Hack committed
547
548

	/* search the greatest result proj number */
Michael Beck's avatar
Michael Beck committed
549
550
551
552
553
554
555
556
557

	/* TODO: what if the result is NOT used? Currently there is
	 * no way to detect this later, especially there is no way to
	 * see this in the proj numbers.
	 * While this is ok for the register allocator, it is bad for
	 * backends which need to change the be_Call further (x87 simulator
	 * for instance. However for this particular case the call_type is
	 * sufficient.).
	 */
Sebastian Hack's avatar
Sebastian Hack committed
558
559
560
561
	foreach_out_edge(irn, edge) {
		const ir_edge_t *res_edge;
		ir_node *irn = get_edge_src_irn(edge);

Michael Beck's avatar
Michael Beck committed
562
		if(is_Proj(irn) && get_Proj_proj(irn) == pn_Call_T_result) {
Sebastian Hack's avatar
Sebastian Hack committed
563
564
565
566
567
568
569
			res_proj = irn;
			foreach_out_edge(irn, res_edge) {
				int proj;
				be_abi_call_arg_t *arg;
				ir_node *res = get_edge_src_irn(res_edge);

				assert(is_Proj(res));
570

Sebastian Hack's avatar
Sebastian Hack committed
571
572
				proj = get_Proj_proj(res);
				arg = get_call_arg(call, 1, proj);
573
574
575
576

				/*
					shift the proj number to the right, since we will drop the
					unspeakable Proj_T from the Call. Therefore, all real argument
Michael Beck's avatar
Michael Beck committed
577
					Proj numbers must be increased by pn_be_Call_first_res
578
				*/
Michael Beck's avatar
Michael Beck committed
579
				proj += pn_be_Call_first_res;
580
581
582
				set_Proj_proj(res, proj);
				obstack_ptr_grow(obst, res);

Sebastian Hack's avatar
Sebastian Hack committed
583
584
				if(proj > curr_res_proj)
					curr_res_proj = proj;
585
				if(arg->in_reg) {
Sebastian Hack's avatar
Sebastian Hack committed
586
					pset_remove_ptr(caller_save, arg->reg);
587
588
					//pmap_insert(arg_regs, arg->reg, INT_TO_PTR(proj + 1))
				}
Sebastian Hack's avatar
Sebastian Hack committed
589
590
591
			}
		}
	}
592

Sebastian Hack's avatar
Sebastian Hack committed
593
	curr_res_proj++;
594
595
	obstack_ptr_grow(obst, NULL);
	res_projs = obstack_finish(obst);
Sebastian Hack's avatar
Sebastian Hack committed
596

597
598
599
600
601
	/* make the back end call node and set its register requirements. */
	for(i = 0; i < n_low_args; ++i)
		obstack_ptr_grow(obst, get_Call_param(irn, low_args[i]));

	in = obstack_finish(obst);
602

Sebastian Hack's avatar
Sebastian Hack committed
603
	if(env->call->flags.bits.call_has_imm && get_irn_opcode(call_ptr) == iro_SymConst) {
Michael Beck's avatar
Michael Beck committed
604
605
606
		low_call = be_new_Call(get_irn_dbg_info(irn), irg, bl, curr_mem, curr_sp, curr_sp,
		                       curr_res_proj + pset_count(caller_save), n_low_args, in,
		                       get_Call_type(irn));
Sebastian Hack's avatar
Sebastian Hack committed
607
608
609
		be_Call_set_entity(low_call, get_SymConst_entity(call_ptr));
	}

610
  else
Michael Beck's avatar
Michael Beck committed
611
612
613
		low_call = be_new_Call(get_irn_dbg_info(irn), irg, bl, curr_mem, curr_sp, call_ptr,
		                       curr_res_proj + pset_count(caller_save), n_low_args, in,
		                       get_Call_type(irn));
614

615
616
617
618
619
620
621
	/*
		TODO:
		Set the register class of the call address to the same as the stack pointer's.
		That' probably buggy for some architectures.
	*/
	be_node_set_reg_class(low_call, be_pos_Call_ptr, sp->reg_class);

Sebastian Hack's avatar
Sebastian Hack committed
622
623
624
	/* Set the register classes and constraints of the Call parameters. */
	for(i = 0; i < n_low_args; ++i) {
		int index = low_args[i];
Sebastian Hack's avatar
Sebastian Hack committed
625
626
		be_abi_call_arg_t *arg = get_call_arg(call, 0, index);
		assert(arg->reg != NULL);
627

628
		be_set_constr_single_reg(low_call, be_pos_Call_first_arg + index, arg->reg);
Sebastian Hack's avatar
Sebastian Hack committed
629
630
631
632
633
634
635
636
637
638
639
640
641
	}

	/* Set the register constraints of the results. */
	for(i = 0; res_projs[i]; ++i) {
		ir_node *irn                 = res_projs[i];
		int proj                     = get_Proj_proj(irn);

		/* Correct Proj number since it has been adjusted! (see above) */
		const be_abi_call_arg_t *arg = get_call_arg(call, 1, proj - pn_Call_max);

		assert(arg->in_reg);
		be_set_constr_single_reg(low_call, BE_OUT_POS(proj), arg->reg);
	}
642
643
644
	obstack_free(obst, in);
	exchange(irn, low_call);

645
646
647
648
	/* redirect the result projs to the lowered call instead of the Proj_T */
	for(i = 0; res_projs[i]; ++i)
		set_Proj_pred(res_projs[i], low_call);

Sebastian Hack's avatar
Sebastian Hack committed
649
650
651
652
	/* Make additional projs for the caller save registers
	   and the Keep node which keeps them alive. */
	if(pset_count(caller_save) > 0) {
		const arch_register_t *reg;
Sebastian Hack's avatar
Sebastian Hack committed
653
654
		ir_node **in, *keep;
		int i, n;
Sebastian Hack's avatar
Sebastian Hack committed
655

Sebastian Hack's avatar
Sebastian Hack committed
656
		for(reg = pset_first(caller_save), n = 0; reg; reg = pset_next(caller_save), ++n) {
657
			ir_node *proj = new_r_Proj(irg, bl, low_call, reg->reg_class->mode, curr_res_proj);
Sebastian Hack's avatar
Sebastian Hack committed
658

Sebastian Hack's avatar
Sebastian Hack committed
659
			/* memorize the register in the link field. we need afterwards to set the register class of the keep correctly. */
660
			be_set_constr_single_reg(low_call, BE_OUT_POS(curr_res_proj), reg);
Sebastian Hack's avatar
Sebastian Hack committed
661
662
			set_irn_link(proj, (void *) reg);
			obstack_ptr_grow(obst, proj);
663
			curr_res_proj++;
Sebastian Hack's avatar
Sebastian Hack committed
664
665
666
667
668
669
670
671
		}

		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);
		}
Sebastian Hack's avatar
Sebastian Hack committed
672
673
674
675
676
		obstack_free(obst, in);
	}

	/* Clean up the stack. */
	if(stack_size > 0) {
677
678
679
680
681
682
683
684
685
		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;
			}
		}
Sebastian Hack's avatar
Sebastian Hack committed
686

687
688
		if(!mem_proj)
			mem_proj = new_r_Proj(irg, bl, low_call, mode_M, pn_Call_M);
Sebastian Hack's avatar
Sebastian Hack committed
689

690
691
		 /* Clean up the stack frame if we allocated it */
		if(!no_alloc)
692
			curr_sp = be_new_IncSP(sp, irg, bl, curr_sp, mem_proj, stack_size, be_stack_dir_shrink);
Sebastian Hack's avatar
Sebastian Hack committed
693
694
695
696
697
698
	}

	be_abi_call_free(call);
	obstack_free(obst, pos);
	del_pset(results);
	del_pset(caller_save);
699
700
701
702
703
704
705
706
707
708

	return curr_sp;
}

/**
 * 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)
{
709
	if (get_Alloc_where(alloc) == stack_alloc) {
710
711
712
713
714
715
		ir_node *bl        = get_nodes_block(alloc);
		ir_graph *irg      = get_irn_irg(bl);
		ir_node *alloc_mem = NULL;
		ir_node *alloc_res = NULL;

		const ir_edge_t *edge;
716
717
		ir_node *new_alloc;

718
719
720
		env->call->flags.bits.try_omit_fp = 0;

		new_alloc = be_new_AddSP(env->isa->sp, irg, bl, curr_sp, get_Alloc_size(alloc));
721

722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
		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;
			}
		}

738
739
740
    /* TODO: Beware: currently Alloc nodes without a result might happen,
       only escape analysis kills them and this phase runs only for object
       oriented source. So this must be fixed. */
741
742
743
744
745
746
747
		assert(alloc_res != NULL);
		exchange(alloc_res, env->isa->stack_dir < 0 ? new_alloc : curr_sp);

		if(alloc_mem != NULL)
			exchange(alloc_mem, new_r_NoMem(irg));

		curr_sp = new_alloc;
748
749
750
	}

	return curr_sp;
Sebastian Hack's avatar
Sebastian Hack committed
751
752
}

753
754
755
756
757
758
759
/**
 * 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, unsigned long visited_nr)
Sebastian Hack's avatar
Sebastian Hack committed
760
{
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
	int n, i;

	if(get_irn_visited(curr) >= visited_nr)
		return 0;

	set_irn_visited(curr, visited_nr);
	if(get_nodes_block(curr) != bl)
		return 0;

	if(curr == tgt)
		return 1;

	for(i = 0, n = get_irn_arity(curr); i < n; ++i) {
		if(check_dependence(get_irn_n(curr, i), tgt, bl, visited_nr))
			return 1;
	}

	return 0;
Sebastian Hack's avatar
Sebastian Hack committed
779
780
}

781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
/**
 * 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)
{
	ir_node *bl   = get_nodes_block(n1);
	ir_graph *irg = get_irn_irg(bl);
	long vis_nr   = get_irg_visited(irg) + 1;

	assert(bl == get_nodes_block(n2));
	set_irg_visited(irg, vis_nr);
	return check_dependence(n1, n2, bl, vis_nr);
}

static int cmp_call_dependecy(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
	*/
	return n1 == n2 ? 0 : (dependent_on(n1, n2) ? -1 : 1);
}

static void link_calls_in_block_walker(ir_node *irn, void *data)
{
	if(is_Call(irn)) {
Sebastian Hack's avatar
Sebastian Hack committed
816
817
818
819
820
		be_abi_irg_t *env = data;
		ir_node *bl       = get_nodes_block(irn);
		void *save        = get_irn_link(bl);

		env->call->flags.bits.irg_is_leaf = 0;
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884

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

/**
 * 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 **nodes;
		int i;

		nodes = obstack_finish(&env->obst);

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

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

			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;
			default:
				break;
			}
		}

		obstack_free(&env->obst, nodes);

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

	set_irn_link(bl, curr_sp);
}

/**
 * Adjust all call nodes in the graph to the ABI conventions.
 */
static void process_calls(be_abi_irg_t *env)
{
	ir_graph *irg = env->birg->irg;

Sebastian Hack's avatar
Sebastian Hack committed
885
886
	env->call->flags.bits.irg_is_leaf = 1;
	irg_walk_graph(irg, firm_clear_link, link_calls_in_block_walker, env);
887
888
889
	irg_block_walk_graph(irg, NULL, process_calls_in_block, env);
}

Sebastian Hack's avatar
Sebastian Hack committed
890
891
892
893
894
895
896
897
static void collect_return_walker(ir_node *irn, void *data)
{
	if(get_irn_opcode(irn) == iro_Return) {
		struct obstack *obst = data;
		obstack_ptr_grow(obst, irn);
	}
}

Sebastian Hack's avatar
Sebastian Hack committed
898
899
900
901
902
static ir_node *setup_frame(be_abi_irg_t *env)
{
	const arch_isa_t *isa = env->birg->main_env->arch_env->isa;
	const arch_register_t *sp = isa->sp;
	const arch_register_t *bp = isa->bp;
Sebastian Hack's avatar
Sebastian Hack committed
903
	be_abi_call_flags_bits_t flags = env->call->flags.bits;
Sebastian Hack's avatar
Sebastian Hack committed
904
905
906
907
	ir_graph *irg      = env->birg->irg;
	ir_node *bl        = get_irg_start_block(irg);
	ir_node *no_mem    = get_irg_no_mem(irg);
	ir_node *old_frame = get_irg_frame(irg);
Sebastian Hack's avatar
Sebastian Hack committed
908
909
	ir_node *stack     = pmap_get(env->regs, (void *) sp);
	ir_node *frame     = pmap_get(env->regs, (void *) bp);
Sebastian Hack's avatar
Sebastian Hack committed
910
911
912

	int stack_nr       = get_Proj_proj(stack);

Sebastian Hack's avatar
Sebastian Hack committed
913
	if(flags.try_omit_fp) {
914
		stack = be_new_IncSP(sp, irg, bl, stack, no_mem, BE_STACK_FRAME_SIZE, be_stack_dir_expand);
Sebastian Hack's avatar
Sebastian Hack committed
915
916
917
918
919
920
		frame = stack;
	}

	else {
		frame = be_new_Copy(bp->reg_class, irg, bl, stack);

Sebastian Hack's avatar
Sebastian Hack committed
921
		be_node_set_flags(frame, -1, arch_irn_flags_dont_spill);
Sebastian Hack's avatar
Sebastian Hack committed
922
		if(!flags.fp_free) {
Sebastian Hack's avatar
Sebastian Hack committed
923
924
			be_set_constr_single_reg(frame, -1, bp);
			be_node_set_flags(frame, -1, arch_irn_flags_ignore);
Sebastian Hack's avatar
Sebastian Hack committed
925
			arch_set_irn_register(env->birg->main_env->arch_env, frame, bp);
Sebastian Hack's avatar
Sebastian Hack committed
926
927
		}

928
		stack = be_new_IncSP(sp, irg, bl, stack, frame, BE_STACK_FRAME_SIZE, be_stack_dir_expand);
Sebastian Hack's avatar
Sebastian Hack committed
929
930
931
932
933
934
935
936
937
938
	}

	be_node_set_flags(env->reg_params, -(stack_nr + 1), arch_irn_flags_ignore);
	env->init_sp = stack;
	set_irg_frame(irg, frame);
	edges_reroute(old_frame, frame, irg);

	return frame;
}

939
static void clearup_frame(be_abi_irg_t *env, ir_node *ret, pmap *reg_map, struct obstack *obst)
Sebastian Hack's avatar
Sebastian Hack committed
940
{
Sebastian Hack's avatar
Sebastian Hack committed
941
942
943
944
	const arch_isa_t *isa = env->birg->main_env->arch_env->isa;
	const arch_register_t *sp = isa->sp;
	const arch_register_t *bp = isa->bp;
	ir_graph *irg      = env->birg->irg;
945
	ir_node *ret_mem   = get_Return_mem(ret);
Sebastian Hack's avatar
Sebastian Hack committed
946
	ir_node *frame     = get_irg_frame(irg);
Sebastian Hack's avatar
Sebastian Hack committed
947
	ir_node *bl        = get_nodes_block(ret);
948
	ir_node *stack     = get_irn_link(bl);
Sebastian Hack's avatar
Sebastian Hack committed
949
950
951

	pmap_entry *ent;

Sebastian Hack's avatar
Sebastian Hack committed
952
	if(env->call->flags.bits.try_omit_fp) {
953
		stack = be_new_IncSP(sp, irg, bl, stack, ret_mem, BE_STACK_FRAME_SIZE, be_stack_dir_shrink);
Sebastian Hack's avatar
Sebastian Hack committed
954
955
956
	}

	else {
957
		stack = be_new_SetSP(sp, irg, bl, stack, frame, ret_mem);
958
959
		be_set_constr_single_reg(stack, -1, sp);
		be_node_set_flags(stack, -1, arch_irn_flags_ignore);
Sebastian Hack's avatar
Sebastian Hack committed
960
961
962
963
964
965
966
	}

	pmap_foreach(env->regs, ent) {
		const arch_register_t *reg = ent->key;
		ir_node *irn               = ent->value;

		if(reg == sp)
967
			obstack_ptr_grow(&env->obst, stack);
Sebastian Hack's avatar
Sebastian Hack committed
968
		else if(reg == bp)
969
970
971
			obstack_ptr_grow(&env->obst, frame);
		else if(arch_register_type_is(reg, callee_save) || arch_register_type_is(reg, ignore))
			obstack_ptr_grow(obst, irn);
Sebastian Hack's avatar
Sebastian Hack committed
972
	}
Sebastian Hack's avatar
Sebastian Hack committed
973
974
}

975
976
static ir_type *compute_arg_type(be_abi_irg_t *env, be_abi_call_t *call, ir_type *method_type)
{
Sebastian Hack's avatar
Sebastian Hack committed
977
978
	int dir  = env->call->flags.bits.left_to_right ? 1 : -1;
	int inc  = env->birg->main_env->arch_env->isa->stack_dir * dir;
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
	int n    = get_method_n_params(method_type);
	int curr = inc > 0 ? 0 : n - 1;
	int ofs  = 0;

	char buf[128];
	ir_type *res;
	int i;

	snprintf(buf, sizeof(buf), "%s_arg_type", get_entity_name(get_irg_entity(env->birg->irg)));
	res = new_type_class(new_id_from_str(buf));

	for(i = 0; i < n; ++i, curr += inc) {
		type *param_type       = get_method_param_type(method_type, curr);
		be_abi_call_arg_t *arg = get_call_arg(call, 0, curr);

994
		if(arg->on_stack) {
995
996
			snprintf(buf, sizeof(buf), "param_%d", i);
			arg->stack_ent = new_entity(res, new_id_from_str(buf), param_type);
997
			ofs += arg->space_before;
998
			ofs = round_up2(ofs, arg->alignment);
999
			set_entity_offset_bytes(arg->stack_ent, ofs);
1000
			ofs += arg->space_after;
For faster browsing, not all history is shown. View entire blame