lower_calls.c 28.9 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, size_t 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
229
typedef struct wlk_env {
	long                 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
305
	ir_entity *ent;
	ir_node *base_ptr = find_base_adr(ptr, &ent);
	ir_storage_class_class_t sc = get_base_sc(classify_pointer(base_ptr, ent));
306
307
	if (sc != ir_sc_localvar && sc != ir_sc_malloced) {
		/* non-local memory access */
308
		env->only_local_mem = false;
309
310
311
	}
}

312
313
314
315
316
317
/*
 * 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)
{
318
319
320
	const ir_entity *callee = get_Call_callee(call);
	if (callee != NULL) {
		const ir_graph *irg = get_entity_linktime_irg(callee);
321
		if (irg == get_irn_irg(call))
322
			return true;
323
	}
324
	return false;
325
326
}

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

	switch (get_irn_opcode(n)) {
	case iro_Load:
	case iro_Store:
		if (env->only_local_mem) {
yb9976's avatar
yb9976 committed
341
			ir_node *ptr = get_irn_n(n, 1);
342
343
344
			check_ptr(ptr, env);
		}
		break;
345
346
347
	case iro_Proj: {
		ir_node  *pred = get_Proj_pred(n);
		ir_graph *irg  = get_irn_irg(n);
348
		if (pred == get_irg_args(irg)) {
349
350
351
352
353
354
355
			long arg_shift = env->arg_shift;
			if (arg_shift > 0) {
				long pn = get_Proj_proj(n);
				set_Proj_proj(n, pn + arg_shift);
				env->changed = true;
			}
		} else if (is_Call(pred)) {
356
			long pn = get_Proj_proj(n);
357
358
359
360
361
362
363
			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;
			}
364
		}
365
		break;
366
	}
367
	case iro_Call: {
368
369
370
		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);
371
372
		if (! is_self_recursive_Call(n)) {
			/* any non self recursive call might access global memory */
373
			env->only_local_mem = false;
374
		}
375

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

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

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

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

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

Matthias Braun's avatar
Matthias Braun committed
481
482
483
		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);
484
485
486
487
				break;
			}
		}
	}
488
489
490
}

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

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

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

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

526
527
528
529
		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);
530

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

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

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

549
550
551
552
553
554
555
556
557
558
559
		/* 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);
560
		}
561
562
563
564
565

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

	/* now create dummy entities for function with ignored return value */
569
570
571
572
573
	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);
574
			if (is_aggregate_type(rtp)) {
575
				if (ins[j] == NULL)
576
					ins[j] = get_dummy_member(get_nodes_block(entry->call), rtp);
577
578
579
580
				++j;
			}
		}
	}
581
582
}

583
static ir_node *find_proj(ir_node *node, long search_pn)
584
{
585
586
587
588
589
590
591
592
593
594
595
	assert(get_irn_mode(node) == mode_T);
	foreach_out_edge(node, edge) {
		ir_node *src = get_edge_src_irn(edge);
		if (!is_Proj(src))
			continue;
		long pn = get_Proj_proj(src);
		if (pn == search_pn)
			return src;
	}
	return NULL;
}
yb9976's avatar
yb9976 committed
596

597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
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 */
	ir_node *res_user = find_proj(proj_res, orig_pn);
	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);
		ir_node *const store     = new_r_Store(block, proj_mem, addr, value,
		                                       cons_none);
		ir_node *const store_mem = new_r_Proj(store, mode_M, pn_Store_M);
		sync_in[i] = store_mem;
643
	}
644
	ir_node *sync = new_r_Sync(block, n_int_rets, sync_in);
645

646
647
648
	/* reroute edges */
	edges_reroute(dummy, sync);
}
yb9976's avatar
yb9976 committed
649

650
651
652
653
654
655
656
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);
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
693
694
695
696
697
698
699
700
701
702
703
704
	/* 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);
705
706
707
	}
}

Manuel Mohr's avatar
Manuel Mohr committed
708
static ir_entity *create_compound_arg_entity(ir_graph *irg, ir_type *type)
709
710
711
712
{
	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
713
714
	/* TODO: we could do some optimizations here and create a big union type
	 * for all different call types in a function */
715
716
717
	return entity;
}

718
static void fix_call_compound_params(const cl_entry *entry, const ir_type *ctp)
719
720
721
722
723
724
725
{
	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
726
727
728

	for (size_t i = 0; i < n_params; ++i) {
		ir_type *type = get_method_param_type(ctp, i);
729
		if (!is_aggregate_type(type))
730
731
			continue;

yb9976's avatar
yb9976 committed
732
733
734
		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);
735
		ir_node   *sel         = new_rd_Member(dbgi, block, frame, arg_entity);
yb9976's avatar
yb9976 committed
736
737
		bool       is_volatile = is_partly_volatile(arg);
		mem = new_rd_CopyB(dbgi, block, mem, sel, arg, type, is_volatile ? cons_volatile : cons_none);
738
739
740
741
742
743
744
		set_Call_param(call, i, sel);
	}
	set_Call_mem(call, mem);
}

static void fix_calls(wlk_env *env)
{
745
746
747
	for (const cl_entry *entry = env->cl_list; entry; entry = entry->next) {
		if (!entry->has_compound_param && entry->n_compound_ret == 0)
			continue;
748
749
750
751
		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);
752

753
		if (entry->has_compound_param) {
754
			fix_call_compound_params(entry, ctp);
755
		}
756
757
		if (entry->n_compound_ret > 0) {
			fix_call_compound_ret(entry, ctp, env);
758
		}
759
		env->changed = true;
760
	}
761
762
}

Matthias Braun's avatar
Matthias Braun committed
763
764
765
766
767
768
769
770
771
772
773
static void transform_return(ir_node *ret, size_t n_ret_com, wlk_env *env)
{
	ir_node   *block      = get_nodes_block(ret);
	ir_graph  *irg        = get_Block_irg(block);
	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;
774
	ir_node  **new_in     = ALLOCAN(ir_node*, n_ress*2 + 1);
Matthias Braun's avatar
Matthias Braun committed
775
776
777
778
779
780
781
782
783
784
	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;
		}

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
		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,
					                           int_return_mode, cons_none);
					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;
		}

815
		ir_node *arg = new_r_Proj(args, mode_P, k++);
Matthias Braun's avatar
Matthias Braun committed
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
		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 */
832
			cr_opt[n_cr_opt].ent = get_Member_entity(pred);
Matthias Braun's avatar
Matthias Braun committed
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
			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;
}

859
860
861
862
863
864
/**
 * 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.
 *
865
866
 * @param irg  the graph to transform
 */
867
static void transform_irg(compound_call_lowering_flags flags, ir_graph *irg)
868
{
869
870
871
872
873
	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;
874

875
	/* calculate the number of compound returns */
876
	size_t n_ret_com = 0;
877
	long   arg_shift = 0;
yb9976's avatar
yb9976 committed
878
	for (size_t i = 0; i < n_ress; ++i) {
879
		ir_type *type = get_method_res_type(mtp, i);
880
		if (is_aggregate_type(type)) {
881
			++n_ret_com;
882
883
884
885
886
			/* 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;
		}
887
	}
yb9976's avatar
yb9976 committed
888
	for (size_t i = 0; i < n_params; ++i) {
889
		ir_type *type = get_method_param_type(mtp, i);
890
		if (is_aggregate_type(type))
891
892
			++n_param_com;
	}
893

894
	if (arg_shift > 0) {
895
		fix_parameter_entities(irg, n_ret_com);
896

897
		/* much easier if we have only one return */
Matthias Braun's avatar
Matthias Braun committed
898
		assure_irg_properties(irg, IR_GRAPH_PROPERTY_ONE_RETURN);
899
	}
900

yb9976's avatar
yb9976 committed
901
	ir_type *lowered_mtp = lower_mtp(flags, mtp);
902
903
	set_entity_type(ent, lowered_mtp);

904
905
	wlk_env env;
	memset(&env, 0, sizeof(env));
906
	obstack_init(&env.obst);
907
	env.arg_shift      = arg_shift;
908
	env.flags          = flags;
Matthias Braun's avatar
Matthias Braun committed
909
	env.mtp            = mtp;
910
	env.lowered_mtp    = lowered_mtp;
911
	env.param_members  = NEW_ARR_F(ir_node*, 0);
912
	env.only_local_mem = true;
913
914

	/* scan the code, fix argument numbers and collect calls. */
915
916
	irg_walk_graph(irg, firm_clear_link, NULL, &env);
	irg_walk_graph(irg, fix_args_and_collect_calls, NULL, &env);
917

918
919
	/* fix parameter sels */
	ir_node *args = get_irg_args(irg);
920
921
922
	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);
923
924
		size_t     num    = get_entity_parameter_number(entity);
		ir_node   *ptr    = new_r_Proj(args, mode_P, num);
925
		exchange(member, ptr);
926
	}
927
	DEL_ARR_F(env.param_members);
928

929
930
931
	if (n_param_com > 0 && !(flags & LF_DONT_LOWER_ARGUMENTS))
		remove_compound_param_entities(irg);

932
	fix_calls(&env);
933

Matthias Braun's avatar
Matthias Braun committed
934
935
	/* transform return nodes */
	if (n_ret_com > 0) {
yb9976's avatar
yb9976 committed
936
		ir_node *endbl = get_irg_end_block(irg);
Matthias Braun's avatar
Matthias Braun committed
937
		foreach_irn_in(endbl, i, pred) {
938
			if (is_Return(pred)) {
Matthias Braun's avatar
Matthias Braun committed
939
				transform_return(pred, n_ret_com, &env);
940
941
942
				break;
			}
		}
943
	}
944

945
946
	if (env.heights != NULL)
		heights_free(env.heights);
947
	obstack_free(&env.obst, NULL);
Matthias Braun's avatar
Matthias Braun committed
948
949
	confirm_irg_properties(irg, env.changed ? IR_GRAPH_PROPERTIES_CONTROL_FLOW
	                                        : IR_GRAPH_PROPERTIES_ALL);
950
}
951

Matthias Braun's avatar
Matthias Braun committed
952
953
static void lower_method_types(ir_type *const type, ir_entity *const entity,
                               void *const env)
954
{
955
956
	const compound_call_lowering_flags *flags
		= (const compound_call_lowering_flags*)env;
957
958

	/* fix method entities */
Matthias Braun's avatar
Matthias Braun committed
959
	if (entity != NULL) {
Christoph Mallon's avatar
Christoph Mallon committed
960
961
962
		ir_type *tp      = get_entity_type(entity);
		ir_type *lowered = lower_mtp(*flags, tp);
		set_entity_type(entity, lowered);
963
964
	} else {
		/* fix pointer to methods */
Christoph Mallon's avatar
Christoph Mallon committed
965
966
		if (is_Pointer_type(type)) {
			ir_type *points_to         = get_pointer_points_to_type(type);
967
			ir_type *lowered_points_to = lower_mtp(*flags, points_to);
Christoph Mallon's avatar
Christoph Mallon committed
968
			set_pointer_points_to_type(type, lowered_points_to);
969
970
		}
	}
971
972
}

973
void lower_calls_with_compounds(compound_call_lowering_flags flags)
974
{
975
976
	pointer_types = pmap_create();
	lowered_mtps = pmap_create();
977

978
979
980
981
982
983
984
985
986
	/* 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 {
yb9976's avatar
yb9976 committed
987
			panic("Cannot determine machine register mode");
988
989
990
		}
	}

991
	/* first step: Transform all graphs */
992
	foreach_irp_irg(i, irg) {
993
		transform_irg(flags, irg);
994
	}
995

996
	/* second step: Lower all method types of visible entities */
997
	type_walk(NULL, lower_method_types, &flags);
998

999
1000
	pmap_destroy(lowered_mtps);
	pmap_destroy(pointer_types);
1001
}