lower_calls.c 28.8 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 "error.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
200
201
202
	/* after lowering the call is not const anymore, since it writes to the
	 * memory for the return value passed to it */
	mtp_properties &= ~mtp_property_const;
	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_sels;
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
264
265
266
267
268
 * Finds the base address of an address by skipping Sel's and address
 * 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
275
276
277
	ir_entity *ent = NULL;
	assert(mode_is_reference(get_irn_mode(ptr)));

	for (;;) {
		if (is_Sel(ptr)) {
			ent = get_Sel_entity(ptr);
			ptr = get_Sel_ptr(ptr);
278
		} else if (is_Add(ptr)) {
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
			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.
 */
298
299
static void check_ptr(ir_node *ptr, wlk_env *env)
{
300
	/* still alias free */
Matthias Braun's avatar
Matthias Braun committed
301
302
303
	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));
304
305
	if (sc != ir_sc_localvar && sc != ir_sc_malloced) {
		/* non-local memory access */
306
		env->only_local_mem = false;
307
308
309
	}
}

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

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

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

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

/**
Matthias Braun's avatar
Matthias Braun committed
441
 * Returns non-zero if a node is a compound address of a frame-type entity.
442
443
444
445
 *
 * @param ft   the frame type
 * @param adr  the node
 */
446
static bool is_compound_address(ir_type *ft, ir_node *adr)
447
{
Matthias Braun's avatar
Matthias Braun committed
448
	if (!is_Sel(adr))
449
		return false;
450
	if (get_Sel_n_indexs(adr) != 0)
451
		return false;
yb9976's avatar
yb9976 committed
452
	ir_entity *ent = get_Sel_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_Sel(n)) {
Matthias Braun's avatar
Matthias Braun committed
478
		copy_return_opt_env *env = (copy_return_opt_env*)ctx;
479
480
		ir_entity *ent = get_Sel_entity(n);

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
492
493
494
495
 * Return a Sel node that selects a dummy argument of type tp.
 *
 * @param block  the block where a newly create Sel should be placed
 * @param tp     the type of the dummy entity that should be create
 */
496
static ir_node *get_dummy_sel(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_simpleSel(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_sel(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_simpleSel(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;
		}

Matthias Braun's avatar
Matthias Braun committed
815
816
817
818
819
820
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
		ir_node *arg = new_r_Proj(args, mode_P_data, k++);
		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 */
			cr_opt[n_cr_opt].ent = get_Sel_entity(pred);
			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_sels     = 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
920
921
922
923
924
925
	/* fix parameter sels */
	ir_node *args = get_irg_args(irg);
	for (size_t i = 0, n = ARR_LEN(env.param_sels); i < n; ++i) {
		ir_node   *sel    = env.param_sels[i];
		ir_entity *entity = get_Sel_entity(sel);
		size_t     num    = get_entity_parameter_number(entity);
		ir_node   *ptr    = new_r_Proj(args, mode_P, num);
		exchange(sel, ptr);
926
	}
927
	DEL_ARR_F(env.param_sels);
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
987
988
989
990
	/* 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 {
			panic("Can't determine machine register mode");
		}
	}

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
}