lower_calls.c 28.7 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
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
 */

Michael Beck's avatar
Michael Beck committed
6
7
8
/**
 * @file
 * @brief   Lowering of Calls with compound parameters and return types.
9
 * @author  Michael Beck, Matthias Braun
10
 */
11
12
#include <stdbool.h>

Matthias Braun's avatar
Matthias Braun committed
13
#include "array.h"
14
#include "be.h"
Matthias Braun's avatar
Matthias Braun committed
15
#include "panic.h"
16
#include "firm_types.h"
17
#include "heights.h"
18
19
20
#include "ircons.h"
#include "irgmod.h"
#include "irgwalk.h"
21
#include "irmemory.h"
22
#include "irmemory_t.h"
Matthias Braun's avatar
Matthias Braun committed
23
24
#include "irmode_t.h"
#include "irnode_t.h"
25
#include "iroptimize.h"
Matthias Braun's avatar
Matthias Braun committed
26
27
28
29
#include "irprog_t.h"
#include "irtools.h"
#include "lower_calls.h"
#include "lowering.h"
30
#include "pmap.h"
Matthias Braun's avatar
Matthias Braun committed
31
#include "type_t.h"
32
#include "util.h"
33

34
35
36
static pmap    *pointer_types;
static pmap    *lowered_mtps;
static ir_mode *int_return_mode;
37
38
39

/**
 * Default implementation for finding a pointer type for a given element type.
Manuel Mohr's avatar
Manuel Mohr committed
40
 * Simply create a new one.
41
 */
42
static ir_type *get_pointer_type(ir_type *dest_type)
43
{
44
	ir_type *res = pmap_get(ir_type, pointer_types, dest_type);
45
46
47
	if (res == NULL) {
		res = new_type_pointer(dest_type);
		pmap_insert(pointer_types, dest_type, res);
48
49
	}
	return res;
50
}
51

52
static void fix_parameter_entities(ir_graph *irg, unsigned arg_shift)
53
54
{
	ir_type *frame_type = get_irg_frame_type(irg);
55
	size_t   n_members  = get_compound_n_members(frame_type);
56

yb9976's avatar
yb9976 committed
57
	for (size_t i = 0; i < n_members; ++i) {
58
59
60
61
62
		ir_entity *member = get_compound_member(frame_type, i);
		if (!is_parameter_entity(member))
			continue;

		/* increase parameter number since we added a new parameter in front */
yb9976's avatar
yb9976 committed
63
		size_t num = get_entity_parameter_number(member);
64
65
		if (num == IR_VA_START_PARAMETER_NUMBER)
			continue;
66
		set_entity_parameter_number(member, num + arg_shift);
67
68
69
	}
}

70
71
72
73
74
static void remove_compound_param_entities(ir_graph *irg)
{
	ir_type *frame_type = get_irg_frame_type(irg);
	size_t   n_members  = get_compound_n_members(frame_type);

yb9976's avatar
yb9976 committed
75
76
	for (size_t i = n_members; i-- > 0; ) {
		ir_entity *member = get_compound_member(frame_type, i);
77
78
79
		if (!is_parameter_entity(member))
			continue;

yb9976's avatar
yb9976 committed
80
		ir_type *type = get_entity_type(member);
81
		if (is_aggregate_type(type)) {
82
83
84
85
86
			free_entity(member);
		}
	}
}

87
88
static unsigned return_in_ints(compound_call_lowering_flags flags, ir_type *tp)
{
89
90
91
92
93
	if (is_Array_type(tp)) {
		if (!(flags&LF_RETURN_SMALL_ARRAY_IN_INTS))
			return 0;
	} else if (!(flags & LF_RETURN_SMALL_STRUCT_IN_INTS)) {
		assert(is_aggregate_type(tp));
94
		return 0;
95
	}
96
97
98
99
100
101
102
	unsigned size   = get_type_size_bytes(tp);
	unsigned n_regs = size / get_mode_size_bytes(int_return_mode);
	if (n_regs > 2)
		return 0;
	return n_regs;
}

103
104
105
106
/**
 * Creates a new lowered type for a method type with compound
 * arguments. The new type is associated to the old one and returned.
 */
107
static ir_type *lower_mtp(compound_call_lowering_flags flags, ir_type *mtp)
108
{
109
110
111
	if (!is_Method_type(mtp))
		return mtp;

yb9976's avatar
yb9976 committed
112
	ir_type *lowered = pmap_get(ir_type, lowered_mtps, mtp);
113
	if (lowered != NULL)
114
115
		return lowered;

116
	/* check if the type has to be lowered at all */
yb9976's avatar
yb9976 committed
117
118
119
120
	bool   must_be_lowered = false;
	size_t n_params        = get_method_n_params(mtp);
	size_t n_ress          = get_method_n_ress(mtp);
	for (size_t i = 0; i < n_ress; ++i) {
121
		ir_type *res_tp = get_method_res_type(mtp, i);
122
		if (is_aggregate_type(res_tp)) {
123
124
			must_be_lowered = true;
			break;
125
		}
126
	}
127
	if (!must_be_lowered && !(flags & LF_DONT_LOWER_ARGUMENTS)) {
yb9976's avatar
yb9976 committed
128
		for (size_t i = 0; i < n_params; ++i) {
129
			ir_type *param_type = get_method_param_type(mtp, i);
130
			if (is_aggregate_type(param_type)) {
131
132
133
134
135
				must_be_lowered = true;
				break;
			}
		}
	}
136
137
138
	if (!must_be_lowered)
		return mtp;

yb9976's avatar
yb9976 committed
139
	ir_type **params    = ALLOCANZ(ir_type*, n_params + n_ress);
140
	ir_type **results   = ALLOCANZ(ir_type*, n_ress * 2);
yb9976's avatar
yb9976 committed
141
142
	size_t    nn_params = 0;
	size_t    nn_ress   = 0;
143
144

	/* add a hidden parameter in front for every compound result */
yb9976's avatar
yb9976 committed
145
	for (size_t i = 0; i < n_ress; ++i) {
146
147
		ir_type *res_tp = get_method_res_type(mtp, i);

148
		if (is_aggregate_type(res_tp)) {
149
150
151
152
153
154
155
156
157
158
159
160
161
			unsigned n_int_res = return_in_ints(flags, res_tp);
			if (n_int_res > 0) {
				for (unsigned i = 0; i < n_int_res; ++i) {
					results[nn_ress++] = get_type_for_mode(int_return_mode);
				}
			} else {
				/* this compound will be allocated on callers stack and its
				   address will be transmitted as a hidden parameter. */
				ir_type *ptr_tp = get_pointer_type(res_tp);
				params[nn_params++] = ptr_tp;
				if (flags & LF_RETURN_HIDDEN)
					results[nn_ress++] = ptr_tp;
			}
162
163
164
		} else {
			/* scalar result */
			results[nn_ress++] = res_tp;
165
166
		}
	}
167
	/* copy over parameter types */
yb9976's avatar
yb9976 committed
168
	for (size_t i = 0; i < n_params; ++i) {
169
		ir_type *param_type = get_method_param_type(mtp, i);
170
171
		if (!(flags & LF_DONT_LOWER_ARGUMENTS)
		    && is_aggregate_type(param_type)) {
172
173
174
175
		    /* turn parameter into a pointer type */
		    param_type = new_type_pointer(param_type);
		}
		params[nn_params++] = param_type;
176
	}
177
	assert(nn_ress <= n_ress*2);
178
	assert(nn_params <= n_params + n_ress);
179
180

	/* create the new type */
181
182
	lowered = new_type_method(nn_params, nn_ress);
	set_type_dbg_info(lowered, get_type_dbg_info(mtp));
183
184

	/* fill it */
yb9976's avatar
yb9976 committed
185
	for (size_t i = 0; i < nn_params; ++i)
186
		set_method_param_type(lowered, i, params[i]);
yb9976's avatar
yb9976 committed
187
	for (size_t i = 0; i < nn_ress; ++i)
188
189
		set_method_res_type(lowered, i, results[i]);

190
	set_method_variadicity(lowered, get_method_variadicity(mtp));
191

yb9976's avatar
yb9976 committed
192
	unsigned cconv = get_method_calling_convention(mtp);
193
194
195
196
197
	if (nn_params > n_params) {
		cconv |= cc_compound_ret;
	}
	set_method_calling_convention(lowered, cconv);

yb9976's avatar
yb9976 committed
198
	mtp_additional_properties mtp_properties = get_method_additional_properties(mtp);
199
	/* after lowering the call is not const/pure anymore, since it writes to the
200
	 * memory for the return value passed to it */
201
	mtp_properties &= ~(mtp_property_no_write | mtp_property_pure);
202
	set_method_additional_properties(lowered, mtp_properties);
203

204
	/* associate the lowered type with the original one for easier access */
205
	set_higher_type(lowered, mtp);
206
	pmap_insert(lowered_mtps, mtp, lowered);
207
208

	return lowered;
209
210
211
}

/**
212
213
214
215
 * A call list entry.
 */
typedef struct cl_entry cl_entry;
struct cl_entry {
216
217
218
	cl_entry *next;   /**< Pointer to the next entry. */
	ir_node  *call;   /**< Pointer to the Call node. */
	ir_node  *copyb;  /**< List of all CopyB nodes. */
219
220
221
222
	ir_node  *proj_M;
	ir_node  *proj_res;
	unsigned  n_compound_ret;
	bool      has_compound_param;
223
224
225
226
};

/**
 * Walker environment for fix_args_and_collect_calls().
227
 */
228
typedef struct wlk_env {
229
	unsigned             arg_shift;        /**< The Argument index shift for parameters. */
230
231
	struct obstack       obst;             /**< An obstack to allocate the data on. */
	cl_entry             *cl_list;         /**< The call list. */
232
	compound_call_lowering_flags flags;
Matthias Braun's avatar
Matthias Braun committed
233
	ir_type              *mtp;             /**< original mtp before lowering */
234
	ir_type              *lowered_mtp;     /**< The lowered method type of the current irg if any. */
235
	ir_heights_t         *heights;         /**< Heights for reachability check. */
236
237
	bool                  only_local_mem:1;/**< Set if only local memory access was found. */
	bool                  changed:1;       /**< Set if the current graph was changed. */
238
	ir_node             **param_members;
239
240
241
} wlk_env;

/**
242
243
244
245
246
247
248
 * Return the call list entry of a call node.
 * If no entry exists yet, allocate one and enter the node into
 * the call list of the environment.
 *
 * @param call   A Call node.
 * @param env    The environment.
 */
249
static cl_entry *get_call_entry(ir_node *call, wlk_env *env)
250
{
251
	cl_entry *res = (cl_entry*)get_irn_link(call);
252
	if (res == NULL) {
253
254
255
		res = OALLOCZ(&env->obst, cl_entry);
		res->next = env->cl_list;
		res->call = call;
256
257
258
259
		set_irn_link(call, res);
		env->cl_list = res;
	}
	return res;
260
261
262
}

/**
263
 * Finds the base address of an address by skipping Member's and address
264
265
266
267
268
 * calculation.
 *
 * @param adr   the address
 * @param pEnt  points to the base entity if any
 */
269
270
static ir_node *find_base_adr(ir_node *ptr, ir_entity **pEnt)
{
271
272
273
274
	ir_entity *ent = NULL;
	assert(mode_is_reference(get_irn_mode(ptr)));

	for (;;) {
275
276
277
278
		if (is_Member(ptr)) {
			ent = get_Member_entity(ptr);
			ptr = get_Member_ptr(ptr);
		} else if (is_Sel(ptr)) {
279
			ptr = get_Sel_ptr(ptr);
280
		} else if (is_Add(ptr)) {
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
			ir_node *left = get_Add_left(ptr);
			if (mode_is_reference(get_irn_mode(left)))
				ptr = left;
			else
				ptr = get_Add_right(ptr);
			ent = NULL;
		} else if (is_Sub(ptr)) {
			ptr = get_Sub_left(ptr);
			ent = NULL;
		} else {
			*pEnt = ent;
			return ptr;
		}
	}
}

/**
 * Check if a given pointer represents non-local memory.
 */
300
301
static void check_ptr(ir_node *ptr, wlk_env *env)
{
302
	/* still alias free */
Matthias Braun's avatar
Matthias Braun committed
303
304
	ir_entity *ent;
	ir_node *base_ptr = find_base_adr(ptr, &ent);
305
306
	ir_storage_class_class_t sc
		= get_base_sc(classify_pointer(ptr, base_ptr));
307
308
	if (sc != ir_sc_localvar && sc != ir_sc_malloced) {
		/* non-local memory access */
309
		env->only_local_mem = false;
310
311
312
	}
}

313
314
315
316
317
318
/*
 * Returns non-zero if a Call is surely a self-recursive Call.
 * Beware: if this functions returns 0, the call might be self-recursive!
 */
static bool is_self_recursive_Call(const ir_node *call)
{
319
320
321
	const ir_entity *callee = get_Call_callee(call);
	if (callee != NULL) {
		const ir_graph *irg = get_entity_linktime_irg(callee);
322
		if (irg == get_irn_irg(call))
323
			return true;
324
	}
325
	return false;
326
327
}

328
329
/**
 * Post walker: shift all parameter indexes
330
 * and collect Calls with compound returns in the call list.
331
332
 * If a non-alias free memory access is found, reset the alias free
 * flag.
333
 */
334
335
static void fix_args_and_collect_calls(ir_node *n, void *ctx)
{
336
	wlk_env *env = (wlk_env*)ctx;
337
338
339
340
341

	switch (get_irn_opcode(n)) {
	case iro_Load:
	case iro_Store:
		if (env->only_local_mem) {
yb9976's avatar
yb9976 committed
342
			ir_node *ptr = get_irn_n(n, 1);
343
344
345
			check_ptr(ptr, env);
		}
		break;
346
347
348
	case iro_Proj: {
		ir_node  *pred = get_Proj_pred(n);
		ir_graph *irg  = get_irn_irg(n);
349
		if (pred == get_irg_args(irg)) {
350
			unsigned arg_shift = env->arg_shift;
351
			if (arg_shift > 0) {
352
353
				unsigned pn = get_Proj_num(n);
				set_Proj_num(n, pn + arg_shift);
354
355
356
				env->changed = true;
			}
		} else if (is_Call(pred)) {
357
			unsigned pn = get_Proj_num(n);
358
359
360
361
362
363
364
			if (pn == pn_Call_M) {
				cl_entry *entry = get_call_entry(pred, env);
				entry->proj_M = n;
			} else if (pn == pn_Call_T_result) {
				cl_entry *entry = get_call_entry(pred, env);
				entry->proj_res = n;
			}
365
		}
366
		break;
367
	}
368
	case iro_Call: {
369
370
371
		ir_type *ctp      = get_Call_type(n);
		size_t   n_ress   = get_method_n_ress(ctp);
		size_t   n_params = get_method_n_params(ctp);
372
373
		if (! is_self_recursive_Call(n)) {
			/* any non self recursive call might access global memory */
374
			env->only_local_mem = false;
375
		}
376

377
		/* check for compound returns */
yb9976's avatar
yb9976 committed
378
		for (size_t i = 0; i < n_ress; ++i) {
379
			ir_type *type = get_method_res_type(ctp, i);
380
			if (is_aggregate_type(type)) {
381
382
383
384
				/*
				 * This is a call with a compound return. As the result
				 * might be ignored, we must put it in the list.
				 */
385
				cl_entry *entry = get_call_entry(n, env);
386
				++entry->n_compound_ret;
387
388
			}
		}
yb9976's avatar
yb9976 committed
389
		for (size_t i = 0; i < n_params; ++i) {
390
			ir_type *type = get_method_param_type(ctp, i);
391
			if (is_aggregate_type(type)) {
392
393
				cl_entry *entry = get_call_entry(n, env);
				entry->has_compound_param = true;
394
				break;
395
396
			}
		}
397
		break;
398
399
400
	}
	case iro_CopyB: {
		ir_node *src = get_CopyB_src(n);
401
402
403
404
405
		if (env->only_local_mem) {
			check_ptr(get_CopyB_src(n), env);
			if (env->only_local_mem)
				check_ptr(get_CopyB_dst(n), env);
		}
406
407
408
		/* check for compound returns */
		if (is_Proj(src)) {
			ir_node *proj = get_Proj_pred(src);
409
			if (is_Proj(proj) && get_Proj_num(proj) == pn_Call_T_result) {
410
411
				ir_node *call = get_Proj_pred(proj);
				if (is_Call(call)) {
412
					ir_type *ctp = get_Call_type(call);
413
					if (is_aggregate_type(get_method_res_type(ctp, get_Proj_num(src)))) {
414
						/* found a CopyB from compound Call result */
415
						cl_entry *e = get_call_entry(call, env);
416
417
						set_irn_link(n, e->copyb);
						e->copyb = n;
418
419
420
					}
				}
			}
421
		}
422
		break;
423
	}
424
425
	case iro_Member: {
		ir_entity *entity = get_Member_entity(n);
426
427
428
429
430
		if (!is_parameter_entity(entity))
			break;
		ir_type *type = get_entity_type(entity);
		if (is_aggregate_type(type)) {
			if (! (env->flags & LF_DONT_LOWER_ARGUMENTS))
431
				ARR_APP1(ir_node*, env->param_members, n);
432
433
			/* we need to copy compound parameters */
			env->only_local_mem = false;
434
435
436
		}
		break;
	}
437
438
439
	default:
		/* do nothing */
		break;
440
	}
441
442
443
}

/**
Matthias Braun's avatar
Matthias Braun committed
444
 * Returns non-zero if a node is a compound address of a frame-type entity.
445
446
447
448
 *
 * @param ft   the frame type
 * @param adr  the node
 */
449
static bool is_compound_address(ir_type *ft, ir_node *adr)
450
{
451
	if (!is_Member(adr))
452
		return false;
453
	ir_entity *ent = get_Member_entity(adr);
454
	return get_entity_owner(ent) == ft;
455
456
}

457
/** A pair for the copy-return-optimization. */
458
typedef struct cr_pair {
459
460
	ir_entity *ent; /**< the entity than can be removed from the frame */
	ir_node *arg;   /**< the argument that replaces the entities address */
461
462
} cr_pair;

Matthias Braun's avatar
Matthias Braun committed
463
464
465
466
467
typedef struct copy_return_opt_env {
	cr_pair *arr;
	size_t   n_pairs;
} copy_return_opt_env;

468
469
470
471
/**
 * Post walker: fixes all entities addresses for the copy-return
 * optimization.
 *
yb9976's avatar
yb9976 committed
472
 * Note: We expect the length of the cr_pair array (i.e. number of compound
473
474
 * return values) to be 1 (C, C++) in almost all cases, so ignore the
 * linear search complexity here.
475
 */
476
477
static void do_copy_return_opt(ir_node *n, void *ctx)
{
478
	if (is_Member(n)) {
Matthias Braun's avatar
Matthias Braun committed
479
		copy_return_opt_env *env = (copy_return_opt_env*)ctx;
480
		ir_entity *ent = get_Member_entity(n);
481

Matthias Braun's avatar
Matthias Braun committed
482
483
484
		for (size_t i = 0, n_pairs = env->n_pairs; i < n_pairs; ++i) {
			if (ent == env->arr[i].ent) {
				exchange(n, env->arr[i].arg);
485
486
487
488
				break;
			}
		}
	}
489
490
491
}

/**
492
 * Return a Member node that selects a dummy argument of type tp.
493
 *
494
 * @param block  the block where a newly create Member should be placed
495
496
 * @param tp     the type of the dummy entity that should be create
 */
497
static ir_node *get_dummy_member(ir_node *block, ir_type *tp)
498
{
499
	ir_graph *irg = get_irn_irg(block);
500
	ir_type  *ft  = get_irg_frame_type(irg);
501
502
	if (get_type_state(ft) == layout_fixed) {
		/* Fix the layout again */
503
		panic("fixed layout not implemented");
504
	}
505

506
	ident     *dummy_id = id_unique("call_result.%u");
yb9976's avatar
yb9976 committed
507
	ir_entity *ent      = new_entity(ft, dummy_id, tp);
508
	return new_r_Member(block, get_irg_frame(irg), ent);
509
510
511
512
513
}

/**
 * Add the hidden parameter from the CopyB node to the Call node.
 */
514
515
static void get_dest_addrs(const cl_entry *entry, ir_node **ins,
                           const ir_type *orig_ctp, wlk_env *env)
516
{
517
	unsigned n_args = 0;
518
519
	for (ir_node *next, *copyb = entry->copyb; copyb != NULL; copyb = next) {
		ir_node *src = get_CopyB_src(copyb);
520
		size_t   idx = get_Proj_num(src);
521
		next = (ir_node*)get_irn_link(copyb);
522

523
		/* consider only the first CopyB */
524
525
		if (ins[idx] != NULL)
			continue;
526

527
528
529
530
		ir_node *call       = entry->call;
		ir_node *call_block = get_nodes_block(call);
		ir_node *dst        = get_CopyB_dst(copyb);
		ir_node *dst_block  = get_nodes_block(dst);
531

532
533
534
		/* Check whether we can use the destination of the CopyB for the call. */
		if (!block_dominates(dst_block, call_block))
			continue;
535

536
537
538
		if (dst_block == call_block) {
			ir_heights_t *heights = env->heights;
			if (heights == NULL) {
539
				ir_graph *irg = get_irn_irg(call_block);
540
541
				heights = heights_new(irg);
				env->heights = heights;
542
543
			}

544
545
546
547
548
			/* Do not optimize the CopyB if the destination depends on the
			 * call. */
			if (heights_reachable_in_block(heights, dst, call))
				continue;
		}
549

550
551
552
553
554
555
556
557
558
559
560
		/* Special case for calls with NoMem memory input. This can happen
		 * for mtp_property_const functions. The call needs a memory input
		 * after lowering, so patch it here to be the input of the CopyB.
		 * Note that in case of multiple CopyB return values this code
		 * may break the order: fix it if you find a language that actually
		 * uses this. */
		ir_node *copyb_mem = get_CopyB_mem(copyb);
		ir_node *call_mem  = get_Call_mem(call);
		if (is_NoMem(call_mem)) {
			set_Call_mem(call, copyb_mem);
			copyb_mem = new_r_Proj(call, mode_M, pn_Call_M);
561
		}
562
563
564
565
566

		ins[idx] = dst;
		/* get rid of the CopyB */
		exchange(copyb, copyb_mem);
		++n_args;
567
568
569
	}

	/* now create dummy entities for function with ignored return value */
570
571
572
573
574
	unsigned n_compound_ret = entry->n_compound_ret;
	if (n_args < n_compound_ret) {
		for (size_t i = 0, j = 0, n_ress = get_method_n_ress(orig_ctp);
		     i < n_ress; ++i) {
			ir_type *rtp = get_method_res_type(orig_ctp, i);
575
			if (is_aggregate_type(rtp)) {
576
				if (ins[j] == NULL)
577
					ins[j] = get_dummy_member(get_nodes_block(entry->call), rtp);
578
579
580
581
				++j;
			}
		}
	}
582
583
}

584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
static void fix_int_return(const cl_entry *entry, ir_node *base_addr,
                           unsigned n_int_rets, long orig_pn, long pn)
{
	ir_node  *const call  = entry->call;
	ir_node  *const block = get_nodes_block(call);
	ir_graph *const irg   = get_irn_irg(base_addr);

	/* we need edges activated here */
	assure_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES);

	/* if the Call throws an exception, then we cannot add instruction
	 * immediately behind it as the call ends the basic block */
	assert(!ir_throws_exception(call));
	ir_mode *const mode_ref = get_irn_mode(base_addr);

	ir_node *proj_mem = entry->proj_M;
	if (proj_mem == NULL)
		proj_mem = new_r_Proj(call, mode_M, pn_Call_M);
	ir_node *proj_res = entry->proj_res;
	if (proj_res == NULL)
		proj_res = new_r_Proj(call, mode_T, pn_Call_T_result);
	/* reroute old users */
Christoph Mallon's avatar
Christoph Mallon committed
606
	ir_node *const res_user = get_Proj_for_pn(proj_res, orig_pn);
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
	if (res_user != NULL)
		edges_reroute(res_user, base_addr);

	/* very hacky: reroute all memory users to a dummy node, which we will
	 * later reroute to the new memory */
	ir_node *dummy = new_r_Dummy(irg, mode_M);
	edges_reroute(proj_mem, dummy);

	ir_node **sync_in = ALLOCAN(ir_node*, n_int_rets);
	for (unsigned i = 0; i < n_int_rets; ++i) {
		ir_node *addr = base_addr;
		if (i > 0) {
			ir_mode *mode_int
				= get_reference_mode_unsigned_eq(mode_ref);
			int      offset      = i * get_mode_size_bytes(int_return_mode);
			ir_node *offset_cnst = new_r_Const_long(irg, mode_int, offset);
			addr = new_r_Add(block, addr, offset_cnst, mode_ref);
		}
		ir_node *const value     = new_r_Proj(proj_res, int_return_mode, pn+i);
626
		ir_type *const type      = get_method_res_type(get_Call_type(call), 0);
627
		ir_node *const store     = new_r_Store(block, proj_mem, addr, value,
628
		                                       type, cons_none);
629
630
		ir_node *const store_mem = new_r_Proj(store, mode_M, pn_Store_M);
		sync_in[i] = store_mem;
631
	}
632
	ir_node *sync = new_r_Sync(block, n_int_rets, sync_in);
633

634
635
636
	/* reroute edges */
	edges_reroute(dummy, sync);
}
yb9976's avatar
yb9976 committed
637

638
639
640
641
642
643
644
static void fix_call_compound_ret(const cl_entry *entry,
                                  const ir_type *orig_ctp, wlk_env *env)
{
	/* produce destination addresses */
	unsigned  n_compound_ret = entry->n_compound_ret;
	ir_node **dest_addrs     = ALLOCANZ(ir_node*, n_compound_ret);
	get_dest_addrs(entry, dest_addrs, orig_ctp, env);
645

646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
	/* now add parameters for destinations or produce stores if compound is
	 * returned as values */
	ir_node  *call     = entry->call;
	size_t    n_params = get_Call_n_params(call);
	size_t    max_ins  = n_params + (n_Call_max+1) + n_compound_ret;
	ir_node **new_in   = NULL;
	size_t    pos      = (size_t)-1;
	long      pn       = 0;
	for (size_t i = 0, c = 0, n_ress = get_method_n_ress(orig_ctp);
	     i < n_ress; ++i) {
		ir_type *type = get_method_res_type(orig_ctp, i);
		if (!is_aggregate_type(type)) {
			++pn;
			continue;
		}

		ir_node *dest_addr = dest_addrs[c++];
		unsigned n_int_res = return_in_ints(env->flags, type);
		if (n_int_res > 0) {
			fix_int_return(entry, dest_addr, n_int_res, i, pn);
			pn += n_int_res;
		} else {
			/* add parameter with destination */
			/* lazily construct new_input list */
			if (new_in == NULL) {
				new_in = ALLOCAN(ir_node*, max_ins);
				new_in[n_Call_mem] = get_Call_mem(call);
				new_in[n_Call_ptr] = get_Call_ptr(call);
				pos = 2;
				assert(pos == n_Call_max+1);
			}
			new_in[pos++] = dest_addr;

			if (env->flags & LF_RETURN_HIDDEN)
				++pn;
		}
	}

	/* do we have new inputs? */
	if (new_in != NULL) {
		/* copy all other parameters */
		for (size_t i = 0; i < n_params; ++i) {
			ir_node *param = get_Call_param(call, i);
			new_in[pos++] = param;
		}
		assert(pos <= max_ins);
		set_irn_in(call, pos, new_in);
693
694
695
	}
}

Manuel Mohr's avatar
Manuel Mohr committed
696
static ir_entity *create_compound_arg_entity(ir_graph *irg, ir_type *type)
697
698
699
700
{
	ir_type   *frame  = get_irg_frame_type(irg);
	ident     *id     = id_unique("$compound_param.%u");
	ir_entity *entity = new_entity(frame, id, type);
Matthias Braun's avatar
Matthias Braun committed
701
702
	/* TODO: we could do some optimizations here and create a big union type
	 * for all different call types in a function */
703
704
705
	return entity;
}

706
static void fix_call_compound_params(const cl_entry *entry, const ir_type *ctp)
707
708
709
710
711
712
713
{
	ir_node  *call     = entry->call;
	dbg_info *dbgi     = get_irn_dbg_info(call);
	ir_node  *mem      = get_Call_mem(call);
	ir_graph *irg      = get_irn_irg(call);
	ir_node  *frame    = get_irg_frame(irg);
	size_t    n_params = get_method_n_params(ctp);
yb9976's avatar
yb9976 committed
714
715
716

	for (size_t i = 0; i < n_params; ++i) {
		ir_type *type = get_method_param_type(ctp, i);
717
		if (!is_aggregate_type(type))
718
719
			continue;

yb9976's avatar
yb9976 committed
720
721
722
		ir_node   *arg         = get_Call_param(call, i);
		ir_entity *arg_entity  = create_compound_arg_entity(irg, type);
		ir_node   *block       = get_nodes_block(call);
723
		ir_node   *sel         = new_rd_Member(dbgi, block, frame, arg_entity);
yb9976's avatar
yb9976 committed
724
725
		bool       is_volatile = is_partly_volatile(arg);
		mem = new_rd_CopyB(dbgi, block, mem, sel, arg, type, is_volatile ? cons_volatile : cons_none);
726
727
728
729
730
731
732
		set_Call_param(call, i, sel);
	}
	set_Call_mem(call, mem);
}

static void fix_calls(wlk_env *env)
{
733
734
735
	for (const cl_entry *entry = env->cl_list; entry; entry = entry->next) {
		if (!entry->has_compound_param && entry->n_compound_ret == 0)
			continue;
736
737
738
739
		ir_node *call        = entry->call;
		ir_type *ctp         = get_Call_type(call);
		ir_type *lowered_mtp = lower_mtp(env->flags, ctp);
		set_Call_type(call, lowered_mtp);
740

741
		if (entry->has_compound_param) {
742
			fix_call_compound_params(entry, ctp);
743
		}
744
745
		if (entry->n_compound_ret > 0) {
			fix_call_compound_ret(entry, ctp, env);
746
		}
747
		env->changed = true;
748
	}
749
750
}

Matthias Braun's avatar
Matthias Braun committed
751
752
753
static void transform_return(ir_node *ret, size_t n_ret_com, wlk_env *env)
{
	ir_node   *block      = get_nodes_block(ret);
754
	ir_graph  *irg        = get_irn_irg(ret);
Matthias Braun's avatar
Matthias Braun committed
755
756
757
758
759
760
761
	ir_type   *mtp        = env->mtp;
	size_t     n_ress     = get_method_n_ress(mtp);
	ir_node   *mem        = get_Return_mem(ret);
	ir_node   *args       = get_irg_args(irg);
	ir_type   *frame_type = get_irg_frame_type(irg);
	size_t     n_cr_opt   = 0;
	size_t     n_in       = 1;
762
	ir_node  **new_in     = ALLOCAN(ir_node*, n_ress*2 + 1);
Matthias Braun's avatar
Matthias Braun committed
763
764
765
766
767
768
769
770
771
772
	cr_pair   *cr_opt     = ALLOCAN(cr_pair, n_ret_com);

	for (size_t i = 0, k = 0; i < n_ress; ++i) {
		ir_node *pred = get_Return_res(ret, i);
		ir_type *type = get_method_res_type(mtp, i);
		if (!is_aggregate_type(type)) {
			new_in[n_in++] = pred;
			continue;
		}

773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
		unsigned int_rets = return_in_ints(env->flags, type);
		if (int_rets > 0) {
			if (is_Unknown(pred)) {
				for (unsigned i = 0; i < int_rets; ++i) {
					new_in[n_in++] = new_r_Unknown(irg, int_return_mode);
				}
			} else {
				ir_node **sync_in = ALLOCAN(ir_node*,int_rets);
				for (unsigned i = 0; i < int_rets; ++i) {
					ir_node *addr = pred;
					ir_mode *mode_ref = get_irn_mode(addr);
					if (i > 0) {
						ir_mode *mode_int
							= get_reference_mode_unsigned_eq(mode_ref);
						int offset = i * get_mode_size_bytes(int_return_mode);
						ir_node *offset_cnst
							= new_r_Const_long(irg, mode_int, offset);
						addr = new_r_Add(block, addr, offset_cnst, mode_ref);
					}
					ir_node *load = new_r_Load(block, mem, addr,
793
					                           int_return_mode, type, cons_none);
794
795
796
797
798
799
800
801
802
					sync_in[i] = new_r_Proj(load, mode_M, pn_Load_M);
					new_in[n_in++] = new_r_Proj(load, int_return_mode,
					                            pn_Load_res);
				}
				mem = new_r_Sync(block, int_rets, sync_in);
			}
			continue;
		}

803
		ir_node *arg = new_r_Proj(args, mode_P, k++);
Matthias Braun's avatar
Matthias Braun committed
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
		if (env->flags & LF_RETURN_HIDDEN)
			new_in[n_in++] = arg;

		/* nothing to do when returning an unknown value */
		if (is_Unknown(pred))
			continue;

		/**
		 * Sorrily detecting that copy-return is possible isn't
		 * that simple. We must check, that the hidden address
		 * is alias free during the whole function.
		 * A simple heuristic: all Loads/Stores inside
		 * the function access only local frame.
		 */
		if (env->only_local_mem && is_compound_address(frame_type, pred)) {
			/* we can do the copy-return optimization here */
820
			cr_opt[n_cr_opt].ent = get_Member_entity(pred);
Matthias Braun's avatar
Matthias Braun committed
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
			cr_opt[n_cr_opt].arg = arg;
			++n_cr_opt;
		} else {
			/* copy-return optimization is impossible, do the copy. */
			bool is_volatile = is_partly_volatile(pred);
			mem = new_r_CopyB(block, mem, arg, pred, type,
							  is_volatile ? cons_volatile : cons_none);
		}
	}
	/* replace the in of the Return */
	new_in[0] = mem;
	set_irn_in(ret, n_in, new_in);

	if (n_cr_opt > 0) {
		copy_return_opt_env env;
		env.arr     = cr_opt;
		env.n_pairs = n_cr_opt;
		irg_walk_graph(irg, NULL, do_copy_return_opt, &env);

		for (size_t c = 0; c < n_cr_opt; ++c)
			free_entity(cr_opt[c].ent);
	}

	env->changed = true;
}

847
848
849
850
851
852
/**
 * Transform a graph. If it has compound parameter returns,
 * remove them and use the hidden parameter instead.
 * If it calls methods with compound parameter returns, add hidden
 * parameters.
 *
853
854
 * @param irg  the graph to transform
 */
855
static void transform_irg(compound_call_lowering_flags flags, ir_graph *irg)
856
{
857
858
859
860
861
	ir_entity *ent         = get_irg_entity(irg);
	ir_type   *mtp         = get_entity_type(ent);
	size_t     n_ress      = get_method_n_ress(mtp);
	size_t     n_params    = get_method_n_params(mtp);
	size_t     n_param_com = 0;
862

863
	/* calculate the number of compound returns */
864
865
	size_t   n_ret_com = 0;
	unsigned arg_shift = 0;
yb9976's avatar
yb9976 committed
866
	for (size_t i = 0; i < n_ress; ++i) {
867
		ir_type *type = get_method_res_type(mtp, i);
868
		if (is_aggregate_type(type)) {
869
			++n_ret_com;
870
871
872
873
874
			/* if we don't return it as values, then we will add a new parameter
			 * with the address of the destination memory */
			if (return_in_ints(flags, type) == 0)
				++arg_shift;
		}
875
	}
yb9976's avatar
yb9976 committed
876
	for (size_t i = 0; i < n_params; ++i) {
877
		ir_type *type = get_method_param_type(mtp, i);
878
		if (is_aggregate_type(type))
879
880
			++n_param_com;
	}
881

882
	if (arg_shift > 0) {
883
		fix_parameter_entities(irg, n_ret_com);
884

885
		/* much easier if we have only one return */
Matthias Braun's avatar
Matthias Braun committed
886
		assure_irg_properties(irg, IR_GRAPH_PROPERTY_ONE_RETURN);
887
	}
888

yb9976's avatar
yb9976 committed
889
	ir_type *lowered_mtp = lower_mtp(flags, mtp);
890
891
	set_entity_type(ent, lowered_mtp);

892
893
	wlk_env env;
	memset(&env, 0, sizeof(env));
894
	obstack_init(&env.obst);
895
	env.arg_shift      = arg_shift;
896
	env.flags          = flags;
Matthias Braun's avatar
Matthias Braun committed
897
	env.mtp            = mtp;
898
	env.lowered_mtp    = lowered_mtp;
899
	env.param_members  = NEW_ARR_F(ir_node*, 0);
900
	env.only_local_mem = true;
901
902

	/* scan the code, fix argument numbers and collect calls. */
903
904
	irg_walk_graph(irg, firm_clear_link, NULL, &env);
	irg_walk_graph(irg, fix_args_and_collect_calls, NULL, &env);
905

906
907
	/* fix parameter sels */
	ir_node *args = get_irg_args(irg);
908
909
910
	for (size_t i = 0, n = ARR_LEN(env.param_members); i < n; ++i) {
		ir_node   *member = env.param_members[i];
		ir_entity *entity = get_Member_entity(member);
911
912
		size_t     num    = get_entity_parameter_number(entity);
		ir_node   *ptr    = new_r_Proj(args, mode_P, num);
913
		exchange(member, ptr);
914
	}
915
	DEL_ARR_F(env.param_members);
916

917
918
919
	if (n_param_com > 0 && !(flags & LF_DONT_LOWER_ARGUMENTS))
		remove_compound_param_entities(irg);

920
	fix_calls(&env);
921

Matthias Braun's avatar
Matthias Braun committed
922
923
	/* transform return nodes */
	if (n_ret_com > 0) {
yb9976's avatar
yb9976 committed
924
		ir_node *endbl = get_irg_end_block(irg);
Matthias Braun's avatar
Matthias Braun committed
925
		foreach_irn_in(endbl, i, pred) {
926
			if (is_Return(pred)) {
Matthias Braun's avatar
Matthias Braun committed
927
				transform_return(pred, n_ret_com, &env);
928
929
930
				break;
			}
		}
931
	}
932

933
934
	if (env.heights != NULL)
		heights_free(env.heights);
935
	obstack_free(&env.obst, NULL);
Matthias Braun's avatar
Matthias Braun committed
936
937
	confirm_irg_properties(irg, env.changed ? IR_GRAPH_PROPERTIES_CONTROL_FLOW
	                                        : IR_GRAPH_PROPERTIES_ALL);
938
}
939

Matthias Braun's avatar
Matthias Braun committed
940
941
static void lower_method_types(ir_type *const type, ir_entity *const entity,
                               void *const env)
942
{
943
944
	const compound_call_lowering_flags *flags
		= (const compound_call_lowering_flags*)env;
945
946

	/* fix method entities */
Matthias Braun's avatar
Matthias Braun committed
947
	if (entity != NULL) {
Christoph Mallon's avatar
Christoph Mallon committed
948
949
950
		ir_type *tp      = get_entity_type(entity);
		ir_type *lowered = lower_mtp(*flags, tp);
		set_entity_type(entity, lowered);
951
952
	} else {
		/* fix pointer to methods */
Christoph Mallon's avatar
Christoph Mallon committed
953
954
		if (is_Pointer_type(type)) {
			ir_type *points_to         = get_pointer_points_to_type(type);
955
			ir_type *lowered_points_to = lower_mtp(*flags, points_to);
Christoph Mallon's avatar
Christoph Mallon committed
956
			set_pointer_points_to_type(type, lowered_points_to);
957
958
		}
	}
959
960
}

961
void lower_calls_with_compounds(compound_call_lowering_flags flags)
962
{
963
964
	pointer_types = pmap_create();
	lowered_mtps = pmap_create();
965

966
967
968
969
970
971
972
973
974
	/* stupid heuristic to guess the mode of an integer register on the target
	 * machine */
	if (flags & LF_RETURN_SMALL_ARRAY_IN_INTS) {
		unsigned machine_size = be_get_machine_size();
		if (machine_size == 32) {
			int_return_mode = mode_Iu;
		} else if (machine_size == 64) {
			int_return_mode = mode_Lu;
		} else {
975
			panic("cannot determine machine register mode");
976
977
978
		}
	}

979
	/* first step: Transform all graphs */
980
	foreach_irp_irg(i, irg) {
981