lower_calls.c 23 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
2
 * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

Michael Beck's avatar
Michael Beck committed
20
21
22
23
24
/**
 * @file
 * @brief   Lowering of Calls with compound parameters and return types.
 * @author  Michael Beck
 * @version $Id$
25
26
27
28
 */

#include "config.h"

29
#include "lowering.h"
30
31
32
33
34
35
36
#include "irprog_t.h"
#include "irnode_t.h"
#include "type_t.h"
#include "irmode_t.h"
#include "ircons.h"
#include "irgmod.h"
#include "irgwalk.h"
37
#include "irmemory.h"
38
#include "irtools.h"
39
#include "iroptimize.h"
40
#include "array_t.h"
41
#include "pmap.h"
42
#include "error.h"
43
44
45
46
47
48
49
50

/** A type map for def_find_pointer_type. */
static pmap *type_map;

/**
 * Default implementation for finding a pointer type for a given element type.
 * Simple create a new one.
 */
51
52
static ir_type *def_find_pointer_type(ir_type *e_type, ir_mode *mode,
                                      int alignment)
53
{
54
55
	/* Mode and alignment are always identical in all calls to def_find_pointer_type(), so
	   we simply can use a map from the element type to the pointer type. */
56
57
	ir_type *res = (ir_type*)pmap_get(type_map, e_type);
	if (res == NULL || get_type_mode(res) != mode) {
58
		res = new_type_pointer(e_type);
59
		set_type_mode(res, mode);
60
61
62
63
		set_type_alignment_bytes(res, alignment);
		pmap_insert(type_map, e_type, res);
	}
	return res;
64
}
65
66
67
68

/**
 * Creates a new lowered type for a method type with compound
 * arguments. The new type is associated to the old one and returned.
69
70
71
72
73
 *
 * @param lp   parameter struct
 * @param mtp  the method type to lower
 *
 * The current implementation expects that a lowered type already
74
 * includes the necessary changes ...
75
76
77
 */
static ir_type *create_modified_mtd_type(const lower_params_t *lp, ir_type *mtp)
{
78
	ir_type *lowered, *ptr_tp;
79
	ir_type **params, **results, *res_tp;
Michael Beck's avatar
Michael Beck committed
80
	size_t  *param_map;
81
	ir_mode *modes[MAX_REGISTER_RET_VAL];
82
	size_t  n_ress, n_params, nn_ress, nn_params, i;
83
84
	add_hidden hidden_params;
	int        changed = 0;
85
	ir_variadicity var;
86

87
	lowered = get_associated_type(mtp);
88
	if (lowered != NULL)
89
90
91
92
93
94
95
96
		return lowered;

	n_ress   = get_method_n_ress(mtp);
	NEW_ARR_A(ir_type *, results, n_ress);

	n_params = get_method_n_params(mtp);
	NEW_ARR_A(ir_type *, params, n_params + n_ress);

Michael Beck's avatar
Michael Beck committed
97
	NEW_ARR_A(size_t, param_map, n_params + n_ress);
98

99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
	hidden_params = lp->hidden_params;
	if (hidden_params == ADD_HIDDEN_SMART &&
		get_method_variadicity(mtp) == variadicity_variadic)
		hidden_params = ADD_HIDDEN_ALWAYS_IN_FRONT;

	if (hidden_params == ADD_HIDDEN_ALWAYS_IN_FRONT) {
		/* add hidden in front */
		for (nn_ress = nn_params = i = 0; i < n_ress; ++i) {
			res_tp = get_method_res_type(mtp, i);

			if (is_compound_type(res_tp)) {
				int n_regs = 0;

				if (lp->flags & LF_SMALL_CMP_IN_REGS)
					n_regs = lp->ret_compound_in_regs(res_tp, modes);

				if (n_regs > 0) {
					/* this compound will be returned solely in registers */
117
					panic("Returning compounds in registers not yet implemented");
118
119
120
121
				}
				else {
					/* this compound will be allocated on callers stack and its
					   address will be transmitted as a hidden parameter. */
122
					ptr_tp = lp->find_pointer_type(res_tp, get_modeP_data(), lp->def_ptr_alignment);
123
					params[nn_params]    = ptr_tp;
Michael Beck's avatar
Michael Beck committed
124
					param_map[nn_params] = n_params + i;
125
					++nn_params;
126
127
128
129
					changed++;
					if (lp->flags & LF_RETURN_HIDDEN)
						results[nn_ress++] = ptr_tp;
				}
130
131
			} else {
				/* scalar result */
132
				results[nn_ress++] = res_tp;
133
			}
134
135
		}

136
137
138
139
140
		for (i = 0; i < n_params; ++i, ++nn_params) {
			params[nn_params]    = get_method_param_type(mtp, i);
			param_map[nn_params] = i;
		}
	} else {
141
142
143
144
		/* add hidden parameters last */
		assert(get_method_variadicity(mtp) == variadicity_non_variadic &&
			"Cannot add hidden parameters at end of variadic function");

145
146
147
148
		for (nn_params = 0; nn_params < n_params; ++nn_params) {
			params[nn_params]    = get_method_param_type(mtp, nn_params);
			param_map[nn_params] = nn_params;
		}
149
150
151
152

		for (nn_ress = i = 0; i < n_ress; ++i) {
			res_tp = get_method_res_type(mtp, i);

153
			if (is_compound_type(res_tp)) {
154
				params[nn_params] = lp->find_pointer_type(res_tp, get_modeP_data(), lp->def_ptr_alignment);
Michael Beck's avatar
Michael Beck committed
155
				param_map[nn_params] = n_params + i;
156
157
				++nn_params;
			} else {
158
				results[nn_ress++] = res_tp;
159
			}
160
161
162
163
		}
	}

	/* create the new type */
164
	lowered = new_d_type_method(nn_params, nn_ress, get_type_dbg_info(mtp));
165
166
167
168
169
170
171
172
173
174
175

	/* fill it */
	for (i = 0; i < nn_params; ++i)
		set_method_param_type(lowered, i, params[i]);
	for (i = 0; i < nn_ress; ++i)
		set_method_res_type(lowered, i, results[i]);

	var = get_method_variadicity(mtp);
	set_method_variadicity(lowered, var);

	/* associate the lowered type with the original one for easier access */
176
	if (changed) {
177
178
		set_method_calling_convention(lowered, get_method_calling_convention(mtp) | cc_compound_ret);
	}
179

180
181
182
	set_lowered_type(mtp, lowered);

	return lowered;
183
184
185
}

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

/**
 * Walker environment for fix_args_and_collect_calls().
197
 */
198
typedef struct wlk_env_t {
Michael Beck's avatar
Michael Beck committed
199
200
	size_t               arg_shift;        /**< The Argument index shift for parameters. */
	size_t               first_hidden;     /**< The index of the first hidden argument. */
201
202
203
204
205
	struct obstack       obst;             /**< An obstack to allocate the data on. */
	cl_entry             *cl_list;         /**< The call list. */
	pmap                 *dummy_map;       /**< A map for finding the dummy arguments. */
	unsigned             dnr;              /**< The dummy index number. */
	const lower_params_t *params;          /**< Lowering parameters. */
206
207
	ir_type              *lowered_mtp;     /**< The lowered method type of the current irg if any. */
	ir_type              *value_params;    /**< The value params type if any. */
208
209
	unsigned             only_local_mem:1; /**< Set if only local memory access was found. */
	unsigned             changed:1;        /**< Set if the current graph was changed. */
210
211
212
} wlk_env;

/**
213
214
215
216
217
218
219
 * 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.
 */
220
221
static cl_entry *get_Call_entry(ir_node *call, wlk_env *env)
{
222
	cl_entry *res = (cl_entry*)get_irn_link(call);
223
	if (res == NULL) {
224
		res = OALLOC(&env->obst, cl_entry);
225
226
227
228
229
230
231
		res->next  = env->cl_list;
		res->call  = call;
		res->copyb = NULL;
		set_irn_link(call, res);
		env->cl_list = res;
	}
	return res;
232
233
234
}

/**
235
236
237
238
239
240
 * 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
 */
241
242
static ir_node *find_base_adr(ir_node *ptr, ir_entity **pEnt)
{
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
	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.
 */
271
272
static void check_ptr(ir_node *ptr, wlk_env *env)
{
273
274
275
276
277
	ir_storage_class_class_t sc;
	ir_entity                *ent;

	/* still alias free */
	ptr = find_base_adr(ptr, &ent);
278
	sc  = get_base_sc(classify_pointer(ptr, ent));
279
280
281
282
283
284
285
286
	if (sc != ir_sc_localvar && sc != ir_sc_malloced) {
		/* non-local memory access */
		env->only_local_mem = 0;
	}
}

/**
 * Post walker: shift all parameter indexes
287
 * and collect Calls with compound returns in the call list.
288
289
 * If a non-alias free memory access is found, reset the alias free
 * flag.
290
 */
291
292
static void fix_args_and_collect_calls(ir_node *n, void *ctx)
{
293
	wlk_env *env = (wlk_env*)ctx;
294
	ir_type *ctp;
295
296
297
	ir_node *ptr;

	switch (get_irn_opcode(n)) {
298
299
300
301
302
	case iro_Sel:
		if (env->lowered_mtp != NULL && env->value_params != NULL) {
			ir_entity *ent = get_Sel_entity(n);

			if (get_entity_owner(ent) == env->value_params) {
Michael Beck's avatar
Michael Beck committed
303
				size_t pos = get_struct_member_index(env->value_params, ent) + env->arg_shift;
304
305
306
307
				ir_entity *new_ent;

				new_ent = get_method_value_param_ent(env->lowered_mtp, pos);
				set_entity_ident(new_ent, get_entity_ident(ent));
Michael Beck's avatar
Michael Beck committed
308
				set_Sel_entity(n, new_ent);
309
310
311
			}
		}
		break;
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
	case iro_Load:
	case iro_Store:
		if (env->only_local_mem) {
			ptr = get_irn_n(n, 1);
			check_ptr(ptr, env);
		}
		break;
	case iro_Proj:
		if (env->arg_shift > 0) {
			ir_node *pred = get_Proj_pred(n);

			/* Fix the argument numbers */
			if (pred == get_irg_args(current_ir_graph)) {
				long pnr = get_Proj_proj(n);
				set_Proj_proj(n, pnr + env->arg_shift);
				env->changed = 1;
			}
		}
		break;
	case iro_Call:
		if (! is_self_recursive_Call(n)) {
			/* any non self recursive call might access global memory */
			env->only_local_mem = 0;
335
		}
336

337
338
339
		ctp = get_Call_type(n);
		if (env->params->flags & LF_COMPOUND_RETURN) {
			/* check for compound returns */
Michael Beck's avatar
Michael Beck committed
340
341
			size_t i, n_res;
			for (i = 0, n_res = get_method_n_ress(ctp); i < n_res; ++i) {
342
343
344
345
346
347
348
349
350
351
				if (is_compound_type(get_method_res_type(ctp, i))) {
					/*
					 * This is a call with a compound return. As the result
					 * might be ignored, we must put it in the list.
					 */
					(void)get_Call_entry(n, env);
					break;
				}
			}
		}
352
353
354
355
356
357
358
359
360
361
		break;
	case iro_CopyB:
		if (env->only_local_mem) {
			check_ptr(get_CopyB_src(n), env);
			if (env->only_local_mem)
				check_ptr(get_CopyB_dst(n), env);
		}
		if (env->params->flags & LF_COMPOUND_RETURN) {
			/* check for compound returns */
			ir_node *src = get_CopyB_src(n);
362
363
364
			if (is_Proj(src)) {
				ir_node *proj = get_Proj_pred(src);
				if (is_Proj(proj) && get_Proj_proj(proj) == pn_Call_T_result) {
365
366
					ir_node *call = get_Proj_pred(proj);
					if (is_Call(call)) {
367
368
369
370
371
372
						ctp = get_Call_type(call);
						if (is_compound_type(get_method_res_type(ctp, get_Proj_proj(src)))) {
							/* found a CopyB from compound Call result */
							cl_entry *e = get_Call_entry(call, env);
							set_irn_link(n, e->copyb);
							e->copyb = n;
373
374
375
376
						}
					}
				}
			}
377
		}
378
379
380
381
		break;
	default:
		/* do nothing */
		break;
382
	}
383
384
385
}

/**
386
387
 * Returns non-zero if a node is a compound address
 * of a frame-type entity.
388
389
390
391
392
393
 *
 * @param ft   the frame type
 * @param adr  the node
 */
static int is_compound_address(ir_type *ft, ir_node *adr)
{
394
395
396
397
398
399
400
401
	ir_entity *ent;

	if (! is_Sel(adr))
		return 0;
	if (get_Sel_n_indexs(adr) != 0)
		return 0;
	ent = get_Sel_entity(adr);
	return get_entity_owner(ent) == ft;
402
403
}

404
/** A pair for the copy-return-optimization. */
405
typedef struct cr_pair {
406
407
	ir_entity *ent; /**< the entity than can be removed from the frame */
	ir_node *arg;   /**< the argument that replaces the entities address */
408
409
410
411
412
413
} cr_pair;

/**
 * Post walker: fixes all entities addresses for the copy-return
 * optimization.
 *
yb9976's avatar
yb9976 committed
414
 * Note: We expect the length of the cr_pair array (i.e. number of compound
415
416
 * return values) to be 1 (C, C++) in almost all cases, so ignore the
 * linear search complexity here.
417
 */
418
419
static void do_copy_return_opt(ir_node *n, void *ctx)
{
420
421
	if (is_Sel(n)) {
		ir_entity *ent = get_Sel_entity(n);
422
423
		cr_pair   *arr = (cr_pair*)ctx;
		size_t    i, l;
424

425
		for (i = 0, l = ARR_LEN(arr); i < l; ++i) {
426
427
428
429
430
431
			if (ent == arr[i].ent) {
				exchange(n, arr[i].arg);
				break;
			}
		}
	}
432
433
434
}

/**
435
436
437
438
439
440
441
442
443
444
445
446
447
 * Return a Sel node that selects a dummy argument of type tp.
 * Dummy arguments are only needed once and we use a map
 * to store them.
 * We could even assign all dummy arguments the same offset
 * in the frame type ...
 *
 * @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
 * @param env    the environment
 */
static ir_node *get_dummy_sel(ir_graph *irg, ir_node *block, ir_type *tp, wlk_env *env)
{
448
449
450
451
452
453
	ir_entity *ent;
	pmap_entry *e;

	/* use a map the check if we already create such an entity */
	e = pmap_find(env->dummy_map, tp);
	if (e)
454
		ent = (ir_entity*)e->value;
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
	else {
		ir_type *ft = get_irg_frame_type(irg);
		char buf[16];

		snprintf(buf, sizeof(buf), "dummy.%u", env->dnr++);
		ent = new_entity(ft, new_id_from_str(buf), tp);
		pmap_insert(env->dummy_map, tp, ent);

		if (get_type_state(ft) == layout_fixed) {
			/* Fix the layout again */
			assert(0 && "Fixed layout not implemented");
		}
	}
	return new_r_simpleSel(
		block,
		get_irg_no_mem(irg),
		get_irg_frame(irg),
		ent);
473
474
475
476
477
478
479
480
481
482
483
}

/**
 * Add the hidden parameter from the CopyB node to the Call node.
 *
 * @param irg    the graph
 * @param n_com  number of compound results (will be number of hidden parameters)
 * @param ins    in array to store the hidden parameters into
 * @param entry  the call list
 * @param env    the environment
 */
Michael Beck's avatar
Michael Beck committed
484
static void add_hidden_param(ir_graph *irg, size_t n_com, ir_node **ins, cl_entry *entry, wlk_env *env)
485
{
486
	ir_node *p, *n, *mem, *blk;
Michael Beck's avatar
Michael Beck committed
487
	size_t n_args;
488
489
490

	n_args = 0;
	for (p = entry->copyb; p; p = n) {
491
492
493
		ir_node *src = get_CopyB_src(p);
		size_t   idx = get_Proj_proj(src);
		n = (ir_node*)get_irn_link(p);
494
495
496
497
498
499

		ins[idx] = get_CopyB_dst(p);
		mem      = get_CopyB_mem(p);
		blk      = get_nodes_block(p);

		/* get rid of the CopyB */
500
		turn_into_tuple(p, pn_CopyB_max+1);
501
		set_Tuple_pred(p, pn_CopyB_M,         mem);
502
		set_Tuple_pred(p, pn_CopyB_X_regular, new_r_Jmp(blk));
Matthias Braun's avatar
Matthias Braun committed
503
		set_Tuple_pred(p, pn_CopyB_X_except,  new_r_Bad(irg, mode_X));
504
505
506
507
508
509
		++n_args;
	}

	/* now create dummy entities for function with ignored return value */
	if (n_args < n_com) {
		ir_type *ctp = get_Call_type(entry->call);
510
511
		size_t   i;
		size_t   j;
512

513
514
		if (is_lowered_type(ctp))
			ctp = get_associated_type(ctp);
515
516
517
518
519
520
521
522
523
524

		for (j = i = 0; i < get_method_n_ress(ctp); ++i) {
			ir_type *rtp = get_method_res_type(ctp, i);
			if (is_compound_type(rtp)) {
				if (ins[j] == NULL)
					ins[j] = get_dummy_sel(irg, get_nodes_block(entry->call), rtp, env);
				++j;
			}
		}
	}
525
526
527
528
}

/**
 * Fix all calls on a call list by adding hidden parameters.
529
 *
530
531
532
 * @param irg  the graph
 * @param env  the environment
 */
533
534
static void fix_call_list(ir_graph *irg, wlk_env *env)
{
535
536
537
538
539
	const lower_params_t *lp = env->params;
	cl_entry *p;
	ir_node *call, **new_in;
	ir_type *ctp, *lowered_mtp;
	add_hidden hidden_params;
Michael Beck's avatar
Michael Beck committed
540
	size_t i, n_res, n_params, n_com, pos;
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556

	new_in = NEW_ARR_F(ir_node *, 0);
	for (p = env->cl_list; p; p = p->next) {
		call = p->call;
		ctp = get_Call_type(call);
		lowered_mtp = create_modified_mtd_type(lp, ctp);
		set_Call_type(call, lowered_mtp);

		hidden_params = lp->hidden_params;
		if (hidden_params == ADD_HIDDEN_SMART &&
			get_method_variadicity(ctp) == variadicity_variadic)
			hidden_params = ADD_HIDDEN_ALWAYS_IN_FRONT;

		n_params = get_Call_n_params(call);

		n_com = 0;
Michael Beck's avatar
Michael Beck committed
557
		for (i = 0, n_res = get_method_n_ress(ctp); i < n_res; ++i) {
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
			if (is_compound_type(get_method_res_type(ctp, i)))
				++n_com;
		}
		pos = 2;
		ARR_RESIZE(ir_node *, new_in, n_params + n_com + pos);
		memset(new_in, 0, sizeof(*new_in) * (n_params + n_com + pos));
		if (hidden_params == ADD_HIDDEN_ALWAYS_IN_FRONT) {
			add_hidden_param(irg, n_com, &new_in[pos], p, env);
			pos += n_com;
		}
		/* copy all other parameters */
		for (i = 0; i < n_params; ++i)
			new_in[pos++] = get_Call_param(call, i);
		if (hidden_params == ADD_HIDDEN_ALWAYS_LAST) {
			add_hidden_param(irg, n_com, &new_in[pos], p, env);
			pos += n_com;
		}
		new_in[0] = get_Call_mem(call);
		new_in[1] = get_Call_ptr(call);

		set_irn_in(call, n_params + n_com + 2, new_in);
	}
580
581
582
583
584
585
586
587
588
}

/**
 * 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.
 *
 * @param lp   parameter struct
589
590
591
592
 * @param irg  the graph to transform
 */
static void transform_irg(const lower_params_t *lp, ir_graph *irg)
{
593
	ir_graph   *rem = current_ir_graph;
594
595
	ir_entity  *ent = get_irg_entity(irg);
	ir_type    *mtp, *lowered_mtp, *tp, *ft;
Michael Beck's avatar
Michael Beck committed
596
	size_t     i, j, k, n_ress = 0, n_ret_com = 0;
597
	size_t     n_cr_opt;
598
599
600
	ir_node    **new_in, *ret, *endbl, *bl, *mem, *copy;
	cr_pair    *cr_opt;
	wlk_env    env;
601
602
	add_hidden hidden_params;

603
604
	current_ir_graph = irg;

605
	assert(ent && "Cannot transform graph without an entity");
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
	assert(get_irg_phase_state(irg) == phase_high && "call lowering must be done in phase high");

	mtp = get_entity_type(ent);

	if (lp->flags & LF_COMPOUND_RETURN) {
		/* calculate the number of compound returns */
		n_ress = get_method_n_ress(mtp);
		for (n_ret_com = i = 0; i < n_ress; ++i) {
			tp = get_method_res_type(mtp, i);

			if (is_compound_type(tp))
				++n_ret_com;
		}
	}

	if (n_ret_com) {
		/* much easier if we have only one return */
		normalize_one_return(irg);

		/* This graph has a compound argument. Create a new type */
		lowered_mtp = create_modified_mtd_type(lp, mtp);
		set_entity_type(ent, lowered_mtp);

		hidden_params = lp->hidden_params;
		if (hidden_params == ADD_HIDDEN_SMART &&
			get_method_variadicity(mtp) == variadicity_variadic)
			hidden_params = ADD_HIDDEN_ALWAYS_IN_FRONT;

		if (hidden_params == ADD_HIDDEN_ALWAYS_IN_FRONT) {
			/* hidden arguments are added first */
			env.arg_shift    = n_ret_com;
			env.first_hidden = 0;
638
		} else {
639
640
641
642
643
644
645
			/* hidden arguments are added last */
			env.arg_shift    = 0;
			env.first_hidden = get_method_n_params(mtp);
		}
	} else {
		/* we must only search for calls */
		env.arg_shift = 0;
646
		lowered_mtp   = NULL;
647
648
	}
	obstack_init(&env.obst);
649
650
651
652
	env.cl_list        = NULL;
	env.dummy_map      = pmap_create_ex(8);
	env.dnr            = 0;
	env.params         = lp;
653
654
	env.lowered_mtp    = lowered_mtp;
	env.value_params   = get_method_value_param_type(mtp);
655
656
	env.only_local_mem = 1;
	env.changed        = 0;
657
658
659
660
661
662
663
664
665
666
667

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

	/* fix all calls */
	if (env.cl_list) {
		fix_call_list(irg, &env);
		env.changed = 1;
	}

	if (n_ret_com) {
Michael Beck's avatar
Michael Beck committed
668
669
		int idx;

670
671
672
		/* STEP 1: find the return. This is simple, we have normalized the graph. */
		endbl = get_irg_end_block(irg);
		ret = NULL;
Michael Beck's avatar
Michael Beck committed
673
674
		for (idx = get_Block_n_cfgpreds(endbl) - 1; idx >= 0; --idx) {
			ir_node *pred = get_Block_cfgpred(endbl, idx);
675
676
677
678
679
680

			if (is_Return(pred)) {
				ret = pred;
				break;
			}
		}
Andreas Zwinkau's avatar
Andreas Zwinkau committed
681
682

		/* in case of infinite loops, there might be no return */
Andreas Zwinkau's avatar
Andreas Zwinkau committed
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
		if (ret != NULL) {
			/*
			 * Now fix the Return node of the current graph.
			 */
			env.changed = 1;

			/*
			 * STEP 2: fix it. For all compound return values add a CopyB,
			 * all others are copied.
			 */
			NEW_ARR_A(ir_node *, new_in, n_ress + 1);

			bl  = get_nodes_block(ret);
			mem = get_Return_mem(ret);

			ft = get_irg_frame_type(irg);
			NEW_ARR_A(cr_pair, cr_opt, n_ret_com);
			n_cr_opt = 0;
			for (j = 1, i = k = 0; i < n_ress; ++i) {
				ir_node *pred = get_Return_res(ret, i);
				tp = get_method_res_type(mtp, i);

				if (is_compound_type(tp)) {
					ir_node *arg = get_irg_args(irg);
					arg = new_r_Proj(arg, mode_P_data, env.first_hidden + k);
					++k;

					if (is_Unknown(pred)) {
						/* The Return(Unknown) is the Firm construct for a missing return.
							Do nothing. */
					} else {
						/**
						 * 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(ft, 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. */
							copy = new_r_CopyB(
									bl,
									mem,
									arg,
									pred,
									tp
									);
							mem = new_r_Proj(copy, mode_M, pn_CopyB_M);
						}
736
					}
Andreas Zwinkau's avatar
Andreas Zwinkau committed
737
738
739
740
741
742
					if (lp->flags & LF_RETURN_HIDDEN) {
						new_in[j] = arg;
						++j;
					}
				} else { /* scalar return value */
					new_in[j] = pred;
743
744
745
					++j;
				}
			}
Andreas Zwinkau's avatar
Andreas Zwinkau committed
746
747
748
			/* replace the in of the Return */
			new_in[0] = mem;
			set_irn_in(ret, j, new_in);
749

Andreas Zwinkau's avatar
Andreas Zwinkau committed
750
			if (n_cr_opt > 0) {
751
752
				size_t c;
				size_t n;
753

Andreas Zwinkau's avatar
Andreas Zwinkau committed
754
				irg_walk_graph(irg, NULL, do_copy_return_opt, cr_opt);
755

756
757
				for (c = 0, n = ARR_LEN(cr_opt); c < n; ++c) {
					free_entity(cr_opt[c].ent);
Andreas Zwinkau's avatar
Andreas Zwinkau committed
758
				}
759
760
761
762
763
764
765
			}
		}
	} /* if (n_ret_com) */

	pmap_destroy(env.dummy_map);
	obstack_free(&env.obst, NULL);

766
	current_ir_graph = rem;
767
768
769
770
771
772
}

/**
 * Returns non-zero if the given type is a method
 * type that must be lowered.
 *
773
 * @param lp  lowering parameters
774
775
 * @param tp  The type.
 */
776
777
static int must_be_lowered(const lower_params_t *lp, ir_type *tp)
{
Michael Beck's avatar
Michael Beck committed
778
  size_t i, n_ress;
779
780
781
  ir_type *res_tp;

  if (is_Method_type(tp)) {
782
783
784
785
786
787
788
789
790
    if (lp->flags & LF_COMPOUND_RETURN) {
      /* check for compound returns */
      n_ress = get_method_n_ress(tp);
      for (i = 0; i < n_ress; ++i) {
        res_tp = get_method_res_type(tp, i);

        if (is_compound_type(res_tp))
          return 1;
      }
791
792
    }
  }
793
794
  return 0;
}
795

796
797
798
799
/**
 * type-walker: lower all method types of entities
 * and points-to types.
 */
800
static void lower_method_types(type_or_ent tore, void *env)
801
{
802
	const lower_params_t *lp = (const lower_params_t*)env;
803
804
805
	ir_type *tp;

	/* fix method entities */
806
807
	if (is_entity(tore.ent)) {
		ir_entity *ent = tore.ent;
808
809
810
811
812
813
814
		tp = get_entity_type(ent);

		if (must_be_lowered(lp, tp)) {
			tp = create_modified_mtd_type(lp, tp);
			set_entity_type(ent, tp);
		}
	} else {
815
		tp = tore.typ;
816
817
818
819
820
821
822
823
824
825

		/* fix pointer to methods */
		if (is_Pointer_type(tp)) {
			ir_type *etp = get_pointer_points_to_type(tp);
			if (must_be_lowered(lp, etp)) {
				etp = create_modified_mtd_type(lp, etp);
				set_pointer_points_to_type(tp, etp);
			}
		}
	}
826
827
828
}

/*
829
 * Lower calls with compound parameters and return types.
830
831
832
833
834
835
836
837
838
839
840
841
842
 * This function does the following transformations:
 *
 * - Adds a new (hidden) pointer parameter for
 *   any return compound type.
 *
 * - Use of the hidden parameters in the function code.
 *
 * - Change all calls to functions with compound return
 *   by providing space for the hidden parameter on the callers
 *   stack.
 *
 * - Replace a possible block copy after the function call.
 */
843
void lower_calls_with_compounds(const lower_params_t *params)
844
{
Michael Beck's avatar
Michael Beck committed
845
	size_t i, n;
846
847
	ir_graph *irg;
	lower_params_t param = *params;
848

849
850
851
	if (param.find_pointer_type == NULL) {
		param.find_pointer_type = def_find_pointer_type;
		type_map = pmap_create_ex(8);
852
	} else
853
		type_map = NULL;
854

855
	/* first step: Transform all graphs */
Michael Beck's avatar
Michael Beck committed
856
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
857
		irg = get_irp_irg(i);
858

859
860
		transform_irg(&param, irg);
	}
861

862
863
	/* second step: Lower all method types of visible entities */
	type_walk(NULL, lower_method_types, &param);
864

865
866
	if (type_map)
		pmap_destroy(type_map);
867
}
868