lower_calls.c 23.3 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
14
#include "array.h"
#include "error.h"
15
#include "firm_types.h"
16
#include "heights.h"
17
18
19
#include "ircons.h"
#include "irgmod.h"
#include "irgwalk.h"
20
#include "irmemory.h"
21
#include "irmemory_t.h"
Matthias Braun's avatar
Matthias Braun committed
22
23
#include "irmode_t.h"
#include "irnode_t.h"
24
#include "iroptimize.h"
Matthias Braun's avatar
Matthias Braun committed
25
26
27
28
#include "irprog_t.h"
#include "irtools.h"
#include "lower_calls.h"
#include "lowering.h"
29
#include "pmap.h"
Matthias Braun's avatar
Matthias Braun committed
30
#include "type_t.h"
31
#include "util.h"
32

33
34
static pmap *pointer_types;
static pmap *lowered_mtps;
35
36
37

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

50
51
52
static void fix_parameter_entities(ir_graph *irg, size_t n_compound_ret)
{
	ir_type *frame_type = get_irg_frame_type(irg);
53
	size_t   n_members  = get_compound_n_members(frame_type);
54

yb9976's avatar
yb9976 committed
55
	for (size_t i = 0; i < n_members; ++i) {
56
57
58
59
60
		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
61
		size_t num = get_entity_parameter_number(member);
62
63
		if (num == IR_VA_START_PARAMETER_NUMBER)
			continue;
64
65
66
67
		set_entity_parameter_number(member, num + n_compound_ret);
	}
}

68
69
70
71
72
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
73
74
	for (size_t i = n_members; i-- > 0; ) {
		ir_entity *member = get_compound_member(frame_type, i);
75
76
77
		if (!is_parameter_entity(member))
			continue;

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

85
86
87
88
/**
 * Creates a new lowered type for a method type with compound
 * arguments. The new type is associated to the old one and returned.
 */
89
static ir_type *lower_mtp(compound_call_lowering_flags flags, ir_type *mtp)
90
{
91
92
93
	if (!is_Method_type(mtp))
		return mtp;

yb9976's avatar
yb9976 committed
94
	ir_type *lowered = pmap_get(ir_type, lowered_mtps, mtp);
95
	if (lowered != NULL)
96
97
		return lowered;

98
	/* check if the type has to be lowered at all */
yb9976's avatar
yb9976 committed
99
100
101
102
	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) {
103
		ir_type *res_tp = get_method_res_type(mtp, i);
104
		if (is_aggregate_type(res_tp)) {
105
106
			must_be_lowered = true;
			break;
107
		}
108
	}
109
	if (!must_be_lowered && !(flags & LF_DONT_LOWER_ARGUMENTS)) {
yb9976's avatar
yb9976 committed
110
		for (size_t i = 0; i < n_params; ++i) {
111
			ir_type *param_type = get_method_param_type(mtp, i);
112
			if (is_aggregate_type(param_type)) {
113
114
115
116
117
				must_be_lowered = true;
				break;
			}
		}
	}
118
119
120
	if (!must_be_lowered)
		return mtp;

yb9976's avatar
yb9976 committed
121
122
123
124
	ir_type **params    = ALLOCANZ(ir_type*, n_params + n_ress);
	ir_type **results   = ALLOCANZ(ir_type*, n_ress);
	size_t    nn_params = 0;
	size_t    nn_ress   = 0;
125
126

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

130
		if (is_aggregate_type(res_tp)) {
131
132
133
134
135
136
137
138
139
			/* 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;
		} else {
			/* scalar result */
			results[nn_ress++] = res_tp;
140
141
		}
	}
142
	/* copy over parameter types */
yb9976's avatar
yb9976 committed
143
	for (size_t i = 0; i < n_params; ++i) {
144
		ir_type *param_type = get_method_param_type(mtp, i);
145
146
		if (!(flags & LF_DONT_LOWER_ARGUMENTS)
		    && is_aggregate_type(param_type)) {
147
148
149
150
		    /* turn parameter into a pointer type */
		    param_type = new_type_pointer(param_type);
		}
		params[nn_params++] = param_type;
151
152
153
	}
	assert(nn_ress <= n_ress);
	assert(nn_params <= n_params + n_ress);
154
155

	/* create the new type */
156
157
	lowered = new_type_method(nn_params, nn_ress);
	set_type_dbg_info(lowered, get_type_dbg_info(mtp));
158
159

	/* fill it */
yb9976's avatar
yb9976 committed
160
	for (size_t i = 0; i < nn_params; ++i)
161
		set_method_param_type(lowered, i, params[i]);
yb9976's avatar
yb9976 committed
162
	for (size_t i = 0; i < nn_ress; ++i)
163
164
		set_method_res_type(lowered, i, results[i]);

165
	set_method_variadicity(lowered, get_method_variadicity(mtp));
166

yb9976's avatar
yb9976 committed
167
	unsigned cconv = get_method_calling_convention(mtp);
168
169
170
171
172
	if (nn_params > n_params) {
		cconv |= cc_compound_ret;
	}
	set_method_calling_convention(lowered, cconv);

yb9976's avatar
yb9976 committed
173
	mtp_additional_properties mtp_properties = get_method_additional_properties(mtp);
174
175
176
177
	/* 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);
178

179
	/* associate the lowered type with the original one for easier access */
180
	set_higher_type(lowered, mtp);
181
	pmap_insert(lowered_mtps, mtp, lowered);
182
183

	return lowered;
184
185
186
}

/**
187
188
189
190
 * A call list entry.
 */
typedef struct cl_entry cl_entry;
struct cl_entry {
191
192
193
	cl_entry *next;   /**< Pointer to the next entry. */
	ir_node  *call;   /**< Pointer to the Call node. */
	ir_node  *copyb;  /**< List of all CopyB nodes. */
194
195
	bool      has_compound_ret   : 1;
	bool      has_compound_param : 1;
196
197
198
199
};

/**
 * Walker environment for fix_args_and_collect_calls().
200
 */
201
202
typedef struct wlk_env {
	long                 arg_shift;        /**< The Argument index shift for parameters. */
203
204
	struct obstack       obst;             /**< An obstack to allocate the data on. */
	cl_entry             *cl_list;         /**< The call list. */
205
	compound_call_lowering_flags flags;
Matthias Braun's avatar
Matthias Braun committed
206
	ir_type              *mtp;             /**< original mtp before lowering */
207
	ir_type              *lowered_mtp;     /**< The lowered method type of the current irg if any. */
208
	ir_heights_t         *heights;         /**< Heights for reachability check. */
209
210
	bool                  only_local_mem:1;/**< Set if only local memory access was found. */
	bool                  changed:1;       /**< Set if the current graph was changed. */
211
	ir_node             **param_sels;
212
213
214
} wlk_env;

/**
215
216
217
218
219
220
221
 * 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.
 */
222
static cl_entry *get_call_entry(ir_node *call, wlk_env *env)
223
{
224
	cl_entry *res = (cl_entry*)get_irn_link(call);
225
	if (res == NULL) {
226
		res = OALLOC(&env->obst, cl_entry);
227
228
229
		res->next  = env->cl_list;
		res->call  = call;
		res->copyb = NULL;
Andreas Zwinkau's avatar
Andreas Zwinkau committed
230
231
		res->has_compound_ret   = false;
		res->has_compound_param = false;
232
233
234
235
		set_irn_link(call, res);
		env->cl_list = res;
	}
	return res;
236
237
238
}

/**
239
240
241
242
243
244
 * 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
 */
245
246
static ir_node *find_base_adr(ir_node *ptr, ir_entity **pEnt)
{
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
	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);
		}
		else if (is_Add(ptr)) {
			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.
 */
275
276
static void check_ptr(ir_node *ptr, wlk_env *env)
{
277
	/* still alias free */
Matthias Braun's avatar
Matthias Braun committed
278
279
280
	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));
281
282
	if (sc != ir_sc_localvar && sc != ir_sc_malloced) {
		/* non-local memory access */
283
		env->only_local_mem = false;
284
285
286
	}
}

287
288
289
290
291
292
/*
 * 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)
{
293
294
295
	const ir_entity *callee = get_Call_callee(call);
	if (callee != NULL) {
		const ir_graph *irg = get_entity_linktime_irg(callee);
296
		if (irg == get_irn_irg(call))
297
			return true;
298
	}
299
	return false;
300
301
}

302
303
/**
 * Post walker: shift all parameter indexes
304
 * and collect Calls with compound returns in the call list.
305
306
 * If a non-alias free memory access is found, reset the alias free
 * flag.
307
 */
308
309
static void fix_args_and_collect_calls(ir_node *n, void *ctx)
{
310
	wlk_env *env = (wlk_env*)ctx;
311
312
313
314
315

	switch (get_irn_opcode(n)) {
	case iro_Load:
	case iro_Store:
		if (env->only_local_mem) {
yb9976's avatar
yb9976 committed
316
			ir_node *ptr = get_irn_n(n, 1);
317
318
319
			check_ptr(ptr, env);
		}
		break;
320
321
322
	case iro_Proj: {
		ir_node  *pred = get_Proj_pred(n);
		ir_graph *irg  = get_irn_irg(n);
323
324
325
326
327
		if (pred == get_irg_args(irg)) {
			long pn = get_Proj_proj(n);
			set_Proj_proj(n, pn + env->arg_shift);
			env->changed = true;
		}
328
		break;
329
	}
330
	case iro_Call: {
331
332
333
		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);
334
335
		if (! is_self_recursive_Call(n)) {
			/* any non self recursive call might access global memory */
336
			env->only_local_mem = false;
337
		}
338

339
		/* check for compound returns */
yb9976's avatar
yb9976 committed
340
		for (size_t i = 0; i < n_ress; ++i) {
341
			ir_type *type = get_method_res_type(ctp, i);
342
			if (is_aggregate_type(type)) {
343
344
345
346
				/*
				 * This is a call with a compound return. As the result
				 * might be ignored, we must put it in the list.
				 */
347
348
349
350
351
				cl_entry *entry = get_call_entry(n, env);
				entry->has_compound_ret = true;
				break;
			}
		}
yb9976's avatar
yb9976 committed
352
		for (size_t i = 0; i < n_params; ++i) {
353
			ir_type *type = get_method_param_type(ctp, i);
354
			if (is_aggregate_type(type)) {
355
356
				cl_entry *entry = get_call_entry(n, env);
				entry->has_compound_param = true;
357
				break;
358
359
			}
		}
360
		break;
361
362
363
	}
	case iro_CopyB: {
		ir_node *src = get_CopyB_src(n);
364
365
366
367
368
		if (env->only_local_mem) {
			check_ptr(get_CopyB_src(n), env);
			if (env->only_local_mem)
				check_ptr(get_CopyB_dst(n), env);
		}
369
370
371
372
373
374
		/* 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)) {
375
					ir_type *ctp = get_Call_type(call);
376
					if (is_aggregate_type(get_method_res_type(ctp, get_Proj_proj(src)))) {
377
						/* found a CopyB from compound Call result */
378
						cl_entry *e = get_call_entry(call, env);
379
380
						set_irn_link(n, e->copyb);
						e->copyb = n;
381
382
383
					}
				}
			}
384
		}
385
		break;
386
	}
387
	case iro_Sel: {
388
		ir_entity *entity = get_Sel_entity(n);
389
390
391
392
393
394
		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);
395
396
			/* we need to copy compound parameters */
			env->only_local_mem = false;
397
398
399
		}
		break;
	}
400
401
402
	default:
		/* do nothing */
		break;
403
	}
404
405
406
}

/**
Matthias Braun's avatar
Matthias Braun committed
407
 * Returns non-zero if a node is a compound address of a frame-type entity.
408
409
410
411
 *
 * @param ft   the frame type
 * @param adr  the node
 */
412
static bool is_compound_address(ir_type *ft, ir_node *adr)
413
{
Matthias Braun's avatar
Matthias Braun committed
414
	if (!is_Sel(adr))
415
		return false;
416
	if (get_Sel_n_indexs(adr) != 0)
417
		return false;
yb9976's avatar
yb9976 committed
418
	ir_entity *ent = get_Sel_entity(adr);
419
	return get_entity_owner(ent) == ft;
420
421
}

422
/** A pair for the copy-return-optimization. */
423
typedef struct cr_pair {
424
425
	ir_entity *ent; /**< the entity than can be removed from the frame */
	ir_node *arg;   /**< the argument that replaces the entities address */
426
427
} cr_pair;

Matthias Braun's avatar
Matthias Braun committed
428
429
430
431
432
typedef struct copy_return_opt_env {
	cr_pair *arr;
	size_t   n_pairs;
} copy_return_opt_env;

433
434
435
436
/**
 * Post walker: fixes all entities addresses for the copy-return
 * optimization.
 *
yb9976's avatar
yb9976 committed
437
 * Note: We expect the length of the cr_pair array (i.e. number of compound
438
439
 * return values) to be 1 (C, C++) in almost all cases, so ignore the
 * linear search complexity here.
440
 */
441
442
static void do_copy_return_opt(ir_node *n, void *ctx)
{
443
	if (is_Sel(n)) {
Matthias Braun's avatar
Matthias Braun committed
444
		copy_return_opt_env *env = (copy_return_opt_env*)ctx;
445
446
		ir_entity *ent = get_Sel_entity(n);

Matthias Braun's avatar
Matthias Braun committed
447
448
449
		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);
450
451
452
453
				break;
			}
		}
	}
454
455
456
}

/**
457
458
459
460
461
462
 * Return a Sel node that selects a dummy argument of type tp.
 *
 * @param irg    the graph
 * @param block  the block where a newly create Sel should be placed
 * @param tp     the type of the dummy entity that should be create
 */
463
static ir_node *get_dummy_sel(ir_graph *irg, ir_node *block, ir_type *tp)
464
{
yb9976's avatar
yb9976 committed
465
	ir_type *ft = get_irg_frame_type(irg);
466
467
468
	if (get_type_state(ft) == layout_fixed) {
		/* Fix the layout again */
		panic("Fixed layout not implemented");
469
	}
470

yb9976's avatar
yb9976 committed
471
472
	ident     *dummy_id = id_unique("dummy.%u");
	ir_entity *ent      = new_entity(ft, dummy_id, tp);
473
	return new_r_simpleSel(block, get_irg_frame(irg), ent);
474
475
476
477
478
}

/**
 * Add the hidden parameter from the CopyB node to the Call node.
 */
479
static void add_hidden_param(ir_graph *irg, size_t n_com, ir_node **ins,
480
                             cl_entry *entry, ir_type *ctp, wlk_env *env)
481
{
yb9976's avatar
yb9976 committed
482
	size_t n_args = 0;
483

484
485
	for (ir_node *next, *copyb = entry->copyb; copyb != NULL; copyb = next) {
		ir_node *src = get_CopyB_src(copyb);
486
		size_t   idx = get_Proj_proj(src);
487
		next = (ir_node*)get_irn_link(copyb);
488

489
		/* consider only the first CopyB */
490
491
		if (ins[idx] != NULL)
			continue;
492

493
494
495
496
		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);
497

498
499
500
		/* Check whether we can use the destination of the CopyB for the call. */
		if (!block_dominates(dst_block, call_block))
			continue;
501

502
503
504
505
506
		if (dst_block == call_block) {
			ir_heights_t *heights = env->heights;
			if (heights == NULL) {
				heights = heights_new(irg);
				env->heights = heights;
507
508
			}

509
510
511
512
513
			/* Do not optimize the CopyB if the destination depends on the
			 * call. */
			if (heights_reachable_in_block(heights, dst, call))
				continue;
		}
514

515
516
517
518
519
520
521
522
523
524
525
		/* 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);
526
		}
527
528
529
530
531

		ins[idx] = dst;
		/* get rid of the CopyB */
		exchange(copyb, copyb_mem);
		++n_args;
532
533
534
535
	}

	/* now create dummy entities for function with ignored return value */
	if (n_args < n_com) {
yb9976's avatar
yb9976 committed
536
		for (size_t i = 0, j = 0; i < get_method_n_ress(ctp); ++i) {
537
			ir_type *rtp = get_method_res_type(ctp, i);
538
			if (is_aggregate_type(rtp)) {
539
				if (ins[j] == NULL)
540
					ins[j] = get_dummy_sel(irg, get_nodes_block(entry->call), rtp);
541
542
543
544
				++j;
			}
		}
	}
545
546
}

547
static void fix_compound_ret(cl_entry *entry, ir_type *ctp, wlk_env *env)
548
{
yb9976's avatar
yb9976 committed
549
550
551
552
553
	ir_node *call  = entry->call;
	size_t   n_com = 0;
	size_t   n_res = get_method_n_ress(ctp);

	for (size_t i = 0; i < n_res; ++i) {
554
		ir_type *type = get_method_res_type(ctp, i);
555
		if (is_aggregate_type(type))
556
557
558
			++n_com;
	}

yb9976's avatar
yb9976 committed
559
560
561
562
563
	ir_graph  *irg      = get_irn_irg(call);
	size_t     n_params = get_Call_n_params(call);
	size_t     pos      = 0;
	ir_node  **new_in   = ALLOCANZ(ir_node*, n_params + n_com + (n_Call_max+1));

564
565
566
	new_in[pos++] = get_Call_mem(call);
	new_in[pos++] = get_Call_ptr(call);
	assert(pos == n_Call_max+1);
567
	add_hidden_param(irg, n_com, &new_in[pos], entry, ctp, env);
568
569
570
	pos += n_com;

	/* copy all other parameters */
yb9976's avatar
yb9976 committed
571
	for (size_t i = 0; i < n_params; ++i) {
572
573
574
575
576
577
578
		ir_node *param = get_Call_param(call, i);
		new_in[pos++] = param;
	}
	assert(pos == n_params+n_com+(n_Call_max+1));
	set_irn_in(call, pos, new_in);
}

Manuel Mohr's avatar
Manuel Mohr committed
579
static ir_entity *create_compound_arg_entity(ir_graph *irg, ir_type *type)
580
581
582
583
{
	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
584
585
	/* TODO: we could do some optimizations here and create a big union type
	 * for all different call types in a function */
586
587
588
589
590
591
592
593
594
595
596
	return entity;
}

static void fix_compound_params(cl_entry *entry, ir_type *ctp)
{
	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
597
598
599

	for (size_t i = 0; i < n_params; ++i) {
		ir_type *type = get_method_param_type(ctp, i);
600
		if (!is_aggregate_type(type))
601
602
			continue;

yb9976's avatar
yb9976 committed
603
604
605
		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);
606
		ir_node   *sel         = new_rd_simpleSel(dbgi, block, frame, arg_entity);
yb9976's avatar
yb9976 committed
607
608
		bool       is_volatile = is_partly_volatile(arg);
		mem = new_rd_CopyB(dbgi, block, mem, sel, arg, type, is_volatile ? cons_volatile : cons_none);
609
610
611
612
613
614
615
		set_Call_param(call, i, sel);
	}
	set_Call_mem(call, mem);
}

static void fix_calls(wlk_env *env)
{
yb9976's avatar
yb9976 committed
616
	for (cl_entry *entry = env->cl_list; entry; entry = entry->next) {
617
618
619
620
		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);
621

622
623
624
625
		if (entry->has_compound_param) {
			fix_compound_params(entry, ctp);
		}
		if (entry->has_compound_ret) {
626
			fix_compound_ret(entry, ctp, env);
627
628
		}
	}
629
630
}

Matthias Braun's avatar
Matthias Braun committed
631
632
633
634
635
636
637
638
639
640
641
642
643
644
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
693
694
695
696
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;
	ir_node  **new_in     = ALLOCAN(ir_node*, n_ress+1);
	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;
		}

		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;
}

697
698
699
700
701
702
/**
 * 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.
 *
703
704
 * @param irg  the graph to transform
 */
705
static void transform_irg(compound_call_lowering_flags flags, ir_graph *irg)
706
{
707
708
709
710
711
	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;
712

713
	/* calculate the number of compound returns */
714
	size_t n_ret_com = 0;
yb9976's avatar
yb9976 committed
715
	for (size_t i = 0; i < n_ress; ++i) {
716
		ir_type *type = get_method_res_type(mtp, i);
717
		if (is_aggregate_type(type))
718
			++n_ret_com;
719
	}
yb9976's avatar
yb9976 committed
720
	for (size_t i = 0; i < n_params; ++i) {
721
		ir_type *type = get_method_param_type(mtp, i);
722
		if (is_aggregate_type(type))
723
724
			++n_param_com;
	}
725

726
727
	if (n_ret_com > 0)
		fix_parameter_entities(irg, n_ret_com);
728

729
	long arg_shift;
Matthias Braun's avatar
Matthias Braun committed
730
	if (n_ret_com > 0) {
731
		/* much easier if we have only one return */
Matthias Braun's avatar
Matthias Braun committed
732
		assure_irg_properties(irg, IR_GRAPH_PROPERTY_ONE_RETURN);
733

734
		/* hidden arguments are added first */
735
		arg_shift = n_ret_com;
736
737
	} else {
		/* we must only search for calls */
738
		arg_shift = 0;
739
	}
740

yb9976's avatar
yb9976 committed
741
	ir_type *lowered_mtp = lower_mtp(flags, mtp);
742
743
	set_entity_type(ent, lowered_mtp);

744
745
	wlk_env env;
	memset(&env, 0, sizeof(env));
746
	obstack_init(&env.obst);
747
	env.arg_shift      = arg_shift;
748
	env.flags          = flags;
Matthias Braun's avatar
Matthias Braun committed
749
	env.mtp            = mtp;
750
	env.lowered_mtp    = lowered_mtp;
751
	env.param_sels     = NEW_ARR_F(ir_node*, 0);
752
	env.only_local_mem = true;
753
754

	/* scan the code, fix argument numbers and collect calls. */
755
756
	irg_walk_graph(irg, firm_clear_link, NULL, &env);
	irg_walk_graph(irg, fix_args_and_collect_calls, NULL, &env);
757

758
759
760
761
762
763
764
765
	/* 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);
766
	}
767
	DEL_ARR_F(env.param_sels);
768

769
770
771
	if (n_param_com > 0 && !(flags & LF_DONT_LOWER_ARGUMENTS))
		remove_compound_param_entities(irg);

772
	/* fix all calls */
773
774
775
	if (env.cl_list != NULL) {
		fix_calls(&env);
		env.changed = true;
776
777
	}

Matthias Braun's avatar
Matthias Braun committed
778
779
	/* transform return nodes */
	if (n_ret_com > 0) {
yb9976's avatar
yb9976 committed
780
		ir_node *endbl = get_irg_end_block(irg);
Matthias Braun's avatar
Matthias Braun committed
781
		foreach_irn_in(endbl, i, pred) {
782
			if (is_Return(pred)) {
Matthias Braun's avatar
Matthias Braun committed
783
				transform_return(pred, n_ret_com, &env);
784
785
786
				break;
			}
		}
787
	}
788

789
790
	if (env.heights != NULL)
		heights_free(env.heights);
791
	obstack_free(&env.obst, NULL);
Matthias Braun's avatar
Matthias Braun committed
792
793
	confirm_irg_properties(irg, env.changed ? IR_GRAPH_PROPERTIES_CONTROL_FLOW
	                                        : IR_GRAPH_PROPERTIES_ALL);
794
}
795

Matthias Braun's avatar
Matthias Braun committed
796
797
static void lower_method_types(ir_type *const type, ir_entity *const entity,
                               void *const env)
798
{
799
800
	const compound_call_lowering_flags *flags
		= (const compound_call_lowering_flags*)env;
801
802

	/* fix method entities */
Matthias Braun's avatar
Matthias Braun committed
803
	if (entity != NULL) {
Christoph Mallon's avatar
Christoph Mallon committed
804
805
806
		ir_type *tp      = get_entity_type(entity);
		ir_type *lowered = lower_mtp(*flags, tp);
		set_entity_type(entity, lowered);
807
808
	} else {
		/* fix pointer to methods */
Christoph Mallon's avatar
Christoph Mallon committed
809
810
		if (is_Pointer_type(type)) {
			ir_type *points_to         = get_pointer_points_to_type(type);
811
			ir_type *lowered_points_to = lower_mtp(*flags, points_to);
Christoph Mallon's avatar
Christoph Mallon committed
812
			set_pointer_points_to_type(type, lowered_points_to);
813
814
		}
	}
815
816
}

817
void lower_calls_with_compounds(compound_call_lowering_flags flags)
818
{
819
820
	pointer_types = pmap_create();
	lowered_mtps = pmap_create();
821

822
	/* first step: Transform all graphs */
823
	foreach_irp_irg(i, irg) {
824
		transform_irg(flags, irg);
825
	}
826

827
	/* second step: Lower all method types of visible entities */
828
	type_walk(NULL, lower_method_types, &flags);
829

830
831
	pmap_destroy(lowered_mtps);
	pmap_destroy(pointer_types);
832
}