opt_inline.c 40.2 KB
Newer Older
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
4
5
6
7
8
9
10
 */

/**
 * @file
 * @brief    Dead node elimination and Procedure Inlining.
 * @author   Michael Beck, Goetz Lindenmaier
 */
11
#include <limits.h>
12
#include <stdbool.h>
13
14
15
16
17
#include <assert.h>

#include "irnode_t.h"
#include "irgraph_t.h"
#include "irprog_t.h"
18
#include "entity_t.h"
19
20
21
22
23
24
25
26

#include "iroptimize.h"
#include "ircons_t.h"
#include "iropt_t.h"
#include "irgopt.h"
#include "irgmod.h"
#include "irgwalk.h"

27
#include "array.h"
28
29
30
31
#include "list.h"
#include "pmap.h"
#include "xmalloc.h"
#include "pqueue.h"
32

33
#include "irouts_t.h"
34
35
#include "irloop_t.h"
#include "irbackedge_t.h"
36
#include "opt_init.h"
37
#include "cgana.h"
38
#include "irmemory_t.h"
39

40
#include "analyze_irg_args.h"
41
42
43
44
#include "iredges_t.h"
#include "irflag_t.h"
#include "irhooks.h"
#include "irtools.h"
45
#include "iropt_dbg.h"
46
#include "irnodemap.h"
47

48
DEBUG_ONLY(static firm_dbg_module_t *dbg;)
49
50
51
52

/**
 * Remember the new node in the old node by using a field all nodes have.
 */
53
54
55
56
static void set_new_node(ir_node *node, ir_node *new_node)
{
	set_irn_link(node, new_node);
}
57
58
59
60

/**
 * Get this new node, before the old node is forgotten.
 */
61
62
63
64
65
static inline ir_node *get_new_node(ir_node *old_node)
{
	assert(irn_visited(old_node));
	return (ir_node*) get_irn_link(old_node);
}
66
67

/**
68
 * Copy node for inlining.  Updates attributes that change when
yb9976's avatar
yb9976 committed
69
 * inlining but not for dead node elimination.
70
71
72
73
74
75
 *
 * Copies the node by calling copy_node() and then updates the entity if
 * it's a local one.  env must be a pointer of the frame type of the
 * inlined procedure. The new entities must be in the link field of
 * the entities.
 */
76
static void copy_node_inline(ir_node *node, void *env)
77
{
78
79
80
81
	ir_graph *new_irg  = (ir_graph*) env;
	ir_node  *new_node = irn_copy_into_irg(node, new_irg);

	set_new_node(node, new_node);
82
	if (is_Member(node)) {
83
84
		ir_graph  *old_irg        = get_irn_irg(node);
		ir_type   *old_frame_type = get_irg_frame_type(old_irg);
85
86
		ir_entity *old_entity     = get_Member_entity(node);
		assert(is_Member(new_node));
87
		/* use copied entities from the new frame */
88
		if (get_entity_owner(old_entity) == old_frame_type) {
89
			ir_entity *new_entity = (ir_entity*)get_entity_link(old_entity);
90
			assert(new_entity != NULL);
91
			set_Member_entity(new_node, new_entity);
92
93
94
95
		}
	}
}

96
static void set_preds_inline(ir_node *node, void *env)
97
{
98
	irn_rewire_inputs(node);
99
100

	/* move constants into start block */
101
	ir_node *new_node = get_new_node(node);
102
	if (is_irn_start_block_placed(new_node)) {
103
104
105
		ir_graph *new_irg     = (ir_graph *) env;
		ir_node  *start_block = get_irg_start_block(new_irg);
		set_nodes_block(new_node, start_block);
106
107
108
	}
}

109
110
111
/**
 * Walker: checks if P_value_arg_base is used.
 */
112
113
static void find_addr(ir_node *node, void *env)
{
114
	bool *allow_inline = (bool*)env;
115

116
117
118
119
120
121
	if (is_Block(node) && get_Block_entity(node)) {
		/**
		 * Currently we can't handle blocks whose address was taken correctly
		 * when inlining
		 */
		*allow_inline = false;
122
	} else if (is_Member(node)) {
123
		ir_graph *irg = current_ir_graph;
124
		if (get_Member_ptr(node) == get_irg_frame(irg)) {
125
			/* access to frame */
126
			ir_entity *ent = get_Member_entity(node);
127
128
			if (get_entity_owner(ent) != get_irg_frame_type(irg)) {
				/* access to value_type */
129
				*allow_inline = false;
130
131
			}
		}
132
	} else if (is_Alloc(node)) {
133
134
135
136
137
138
		/* From GCC:
		 * Refuse to inline alloca call unless user explicitly forced so as this
		 * may change program's memory overhead drastically when the function
		 * using alloca is called in loop.  In GCC present in SPEC2000 inlining
		 * into schedule_block cause it to require 2GB of ram instead of 256MB.
		 *
Michael Beck's avatar
Michael Beck committed
139
		 * Sorrily this is true with our implementation also.
140
141
142
		 * Moreover, we cannot differentiate between alloca() and VLA yet, so
		 * this disables inlining of functions using VLA (which are completely
		 * save).
143
144
145
		 *
		 * 2 Solutions:
		 * - add a flag to the Alloc node for "real" alloca() calls
146
147
		 * - add a new Stack-Restore node at the end of a function using
		 *   alloca()
148
		 */
149
		*allow_inline = false;
150
151
152
153
154
155
156
157
158
159
160
	}
}

/**
 * Check if we can inline a given call.
 * Currently, we cannot inline two cases:
 * - call with compound arguments
 * - graphs that take the address of a parameter
 *
 * check these conditions here
 */
161
static bool can_inline(ir_node *call, ir_graph *called_graph)
162
{
yb9976's avatar
yb9976 committed
163
164
	ir_entity                 *called = get_irg_entity(called_graph);
	mtp_additional_properties  props  = get_entity_additional_properties(called);
Matthias Braun's avatar
Matthias Braun committed
165
	if (props & mtp_property_noinline)
166
		return false;
167

168
169
170
171
	ir_type *called_type = get_entity_type(called);
	size_t   n_params    = get_method_n_params(called_type);
	ir_type *call_type   = get_Call_type(call);
	size_t   n_arguments = get_method_n_params(call_type);
172
	if (n_arguments != n_params) {
Michael Beck's avatar
Michael Beck committed
173
174
175
		/* this is a bad feature of C: without a prototype, we can
		 * call a function with less parameters than needed. Currently
		 * we don't support this, although we could use Unknown than. */
176
		return false;
Michael Beck's avatar
Michael Beck committed
177
	}
178
	size_t n_res = get_method_n_ress(called_type);
179
180
	if (n_res != get_method_n_ress(call_type)) {
		return false;
181
	}
182

Michael Beck's avatar
Michael Beck committed
183
	/* Argh, compiling C has some bad consequences:
Michael Beck's avatar
Michael Beck committed
184
185
186
	 * It is implementation dependent what happens in that case.
	 * We support inlining, if the bitsize of the types matches AND
	 * the same arithmetic is used. */
187
	for (size_t i = 0; i < n_params; ++i) {
188
189
		ir_type *param_tp = get_method_param_type(called_type, i);
		ir_type *arg_tp   = get_method_param_type(call_type, i);
Michael Beck's avatar
Michael Beck committed
190
191
192
193
194
195

		if (param_tp != arg_tp) {
			ir_mode *pmode = get_type_mode(param_tp);
			ir_mode *amode = get_type_mode(arg_tp);

			if (pmode == NULL || amode == NULL)
196
				return false;
Michael Beck's avatar
Michael Beck committed
197
			if (get_mode_size_bits(pmode) != get_mode_size_bits(amode))
198
				return false;
Michael Beck's avatar
Michael Beck committed
199
			if (get_mode_arithmetic(pmode) != get_mode_arithmetic(amode))
200
				return false;
Michael Beck's avatar
Michael Beck committed
201
			/* otherwise we can simply "reinterpret" the bits */
202
		}
203
	}
204
	for (size_t i = 0; i < n_res; ++i) {
205
206
		ir_type *decl_res_tp = get_method_res_type(called_type, i);
		ir_type *used_res_tp = get_method_res_type(call_type, i);
207
208
209
210
211

		if (decl_res_tp != used_res_tp) {
			ir_mode *decl_mode = get_type_mode(decl_res_tp);
			ir_mode *used_mode = get_type_mode(used_res_tp);
			if (decl_mode == NULL || used_mode == NULL)
212
				return false;
213
			if (get_mode_size_bits(decl_mode) != get_mode_size_bits(used_mode))
214
				return false;
215
			if (get_mode_arithmetic(decl_mode) != get_mode_arithmetic(used_mode))
216
				return false;
217
218
219
			/* otherwise we can "reinterpret" the bits */
		}
	}
220

221
	/* check for variable number of parameters */
222
223
224
	ir_type *frame_type = get_irg_frame_type(called_graph);
	for (size_t i = 0, n_entities = get_class_n_members(frame_type);
	     i < n_entities; ++i) {
225
		ir_entity *ent = get_class_member(frame_type, i);
226
227
		if (is_parameter_entity(ent) && (get_entity_parameter_number(ent) == IR_VA_START_PARAMETER_NUMBER))
			return false;
228
229
	}

230
	bool res = true;
231
232
233
234
235
236
237
238
239
240
241
	irg_walk_graph(called_graph, find_addr, NULL, &res);

	return res;
}

enum exc_mode {
	exc_handler,    /**< There is a handler. */
	exc_no_handler  /**< Exception handling not represented. */
};

/**
yb9976's avatar
yb9976 committed
242
 * copy all entities on the stack frame on 1 irg to the stack frame of another.
243
244
245
246
247
248
249
 * Sets entity links of the old entities to the copies
 */
static void copy_frame_entities(ir_graph *from, ir_graph *to)
{
	ir_type *from_frame = get_irg_frame_type(from);
	ir_type *to_frame   = get_irg_frame_type(to);
	assert(from_frame != to_frame);
250
251
	for (size_t i = 0, n_members = get_class_n_members(from_frame);
	     i < n_members; ++i) {
252
		ir_entity *old_ent = get_class_member(from_frame, i);
253
254
255
256
257
258

		// parameter entities are already copied and the link has been set
		if (!is_parameter_entity(old_ent)) {
			ir_entity *new_ent = copy_entity_own(old_ent, to_frame);
			set_entity_link(old_ent, new_ent);
		}
259
260
261
	}
}

262
/* Copies parameter entities from the given called graph */
263
static void copy_parameter_entities(ir_node *call, ir_graph *called_graph)
264
{
265
266
267
268
269
270
271
272
273
274
275
	dbg_info *dbgi         = get_irn_dbg_info(call);
	ir_graph *irg          = get_irn_irg(call);
	ir_node  *frame        = get_irg_frame(irg);
	ir_node  *block        = get_nodes_block(call);
	ir_type  *called_frame = get_irg_frame_type(called_graph);
	ir_type  *frame_type   = get_irg_frame_type(irg);
	ir_node  *call_mem     = get_Call_mem(call);
	ir_node **sync_mem     = NULL;

	for (size_t i = 0, n_entities = get_class_n_members(called_frame);
	     i < n_entities; ++i) {
276
		ir_entity *old_entity = get_class_member(called_frame, i);
277
278
		if (!is_parameter_entity(old_entity))
			continue;
279

280
281
		ir_type   *old_type    = get_entity_type(old_entity);
		dbg_info  *entity_dbgi = get_entity_dbg_info(old_entity);
yb9976's avatar
yb9976 committed
282
		ident     *old_name    = get_entity_ident(old_entity);
283
		ident     *name        = new_id_fmt("%s$inlined", old_name);
284
285
286
		ir_entity *new_ent     = new_entity(frame_type, name, old_type);
		set_entity_dbg_info(new_ent, entity_dbgi);
		set_entity_link(old_entity, new_ent);
287
288
289

		size_t   n_param_pos = get_entity_parameter_number(old_entity);
		ir_node *param       = get_Call_param(call, n_param_pos);
290
		ir_node *sel         = new_rd_Member(dbgi, block, frame, new_ent);
291
		ir_node *new_mem;
292
		if (is_aggregate_type(old_type)) {
293
			/* Copy the compound parameter */
294
295
296
297

			bool is_volatile = is_partly_volatile(param) || is_partly_volatile(sel);

			new_mem = new_rd_CopyB(dbgi, block, call_mem, sel, param, old_type, is_volatile ? cons_volatile : cons_none);
298
			set_Call_param(call, n_param_pos, sel);
299
300
		} else {
			/* Store the parameter onto the frame */
301
			ir_node *store = new_rd_Store(dbgi, block, call_mem, sel, param, old_type, cons_none);
302
			new_mem = new_r_Proj(store, mode_M, pn_Store_M);
303
304
305
		}

		if (sync_mem) {
306
			ARR_APP1(ir_node*, sync_mem, new_mem);
307
308
309
		} else {
			sync_mem = NEW_ARR_F(ir_node*, 1);
			sync_mem[0] = new_mem;
310
		}
311
312
313
	}

	if (sync_mem != NULL) {
314
315
316
317
318
319
320
		int sync_arity = (int)ARR_LEN(sync_mem);
		if (sync_arity > 1) {
			ir_node *sync = new_r_Sync(block, sync_arity, sync_mem);
			set_Call_mem(call, sync);
		} else {
			set_Call_mem(call, sync_mem[0]);
		}
321
		DEL_ARR_F(sync_mem);
322
323
324
325
	}
}

/* Inlines a method at the given call site. */
326
static bool inline_method(ir_node *const call, ir_graph *called_graph)
327
328
{
	/* we cannot inline some types of calls */
329
330
	if (!can_inline(call, called_graph))
		return false;
331

332
333
	/* We cannot inline a recursive call. The graph must be copied before
	 * the call the inline_method() using create_irg_copy(). */
334
	ir_graph *irg = get_irn_irg(call);
335
	if (called_graph == irg)
336
		return false;
337

338
	ir_graph *rem = current_ir_graph;
339
340
	current_ir_graph = irg;

341
	DB((dbg, LEVEL_1, "Inlining %+F(%+F) into %+F\n", call, called_graph, irg));
342

343
	/* optimizations can cause problems when allocating new nodes */
Matthias Braun's avatar
Matthias Braun committed
344
	int rem_opt = get_optimize();
345
346
347
	set_optimize(0);

	/* Handle graph state */
348
	assert(get_irg_pinned(irg) == op_pin_state_pinned);
349
	assert(get_irg_pinned(called_graph) == op_pin_state_pinned);
350
351
	clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE
	                   | IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE);
352
	set_irg_callee_info_state(irg, irg_callee_info_inconsistent);
353
	clear_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_ENTITY_USAGE);
354
	edges_deactivate(irg);
355
356
357
358
359
360
361
362
363

	/* here we know we WILL inline, so inform the statistics */
	hook_inline(call, called_graph);

	/* -- Decide how to handle exception control flow: Is there a handler
	   for the Call node, or do we branch directly to End on an exception?
	   exc_handling:
	   0 There is a handler.
	   2 Exception handling not represented in Firm. -- */
364
365
366
	ir_node *Xproj = NULL;
	for (ir_node *proj = (ir_node*)get_irn_link(call); proj != NULL;
		 proj = (ir_node*)get_irn_link(proj)) {
367
		unsigned proj_nr = get_Proj_num(proj);
368
		if (proj_nr == pn_Call_X_except) Xproj = proj;
369
	}
370
	enum exc_mode exc_handling = Xproj != NULL ? exc_handler : exc_no_handler;
371

yb9976's avatar
yb9976 committed
372
373
	/* entity link is used to link entities on old stack frame to the
	 * new stack frame */
374
375
	irp_reserve_resources(irp, IRP_RESOURCE_ENTITY_LINK);

376
	/* If the call has parameters, copy all parameter entities */
377
378
379
	ir_entity *ent      = get_irg_entity(called_graph);
	ir_type   *mtp      = get_entity_type(ent);
	int        n_params = get_method_n_params(mtp);
380
	if (n_params != 0) {
381
		copy_parameter_entities(call, called_graph);
382
	}
383

Michael Beck's avatar
Michael Beck committed
384
	/* create the argument tuple */
385
	ir_node **args_in = ALLOCAN(ir_node*, n_params);
Michael Beck's avatar
Michael Beck committed
386

387
388
	ir_node *block = get_nodes_block(call);
	for (int i = n_params - 1; i >= 0; --i) {
Michael Beck's avatar
Michael Beck committed
389
390
391
392
		ir_node *arg      = get_Call_param(call, i);
		ir_type *param_tp = get_method_param_type(mtp, i);
		ir_mode *mode     = get_type_mode(param_tp);

393
		if (!is_aggregate_type(param_tp) && mode != get_irn_mode(arg)) {
394
			arg = new_r_Conv(block, arg, mode);
Michael Beck's avatar
Michael Beck committed
395
396
397
398
		}
		args_in[i] = arg;
	}

399
400
401
	/* the procedure and later replaces the Start node of the called graph.
	 * Post_call is the old Call node and collects the results of the called
	 * graph. Both will end up being a tuple. */
402
	ir_node *post_bl = get_nodes_block(call);
403
	/* XxMxPxPxPxT of Start + parameter of Call */
404
	ir_node *in[pn_Start_max+1];
405
406
407
	in[pn_Start_M]              = get_Call_mem(call);
	in[pn_Start_P_frame_base]   = get_irg_frame(irg);
	in[pn_Start_T_args]         = new_r_Tuple(post_bl, n_params, args_in);
408
	ir_node *pre_call = new_r_Tuple(post_bl, pn_Start_max+1, in);
409
410
411
412
413
414

	/* --
	   The new block gets the ins of the old block, pre_call and all its
	   predecessors and all Phi nodes. -- */
	part_block(pre_call);

415
416
417
418
419
420
421
422
423
	/* increment visited flag for later walk */
	inc_irg_visited(called_graph);

	/* link some nodes to nodes in the current graph so instead of copying
	 * the linked nodes will get used.
	 * So the copier will use the created Tuple instead of copying the start
	 * node, similar for singleton nodes like NoMem and Bad.
	 * Note: this will prohibit predecessors to be copied - only do it for
	 *       nodes without predecessors */
424
425
426
427
428
429
430
431
432
433
434
	ir_node *start_block = get_irg_start_block(called_graph);
	set_new_node(start_block, get_nodes_block(pre_call));
	mark_irn_visited(start_block);

	ir_node *start = get_irg_start(called_graph);
	set_new_node(start, pre_call);
	mark_irn_visited(start);

	ir_node *nomem = get_irg_no_mem(called_graph);
	set_new_node(nomem, get_irg_no_mem(irg));
	mark_irn_visited(nomem);
435

436
437
438
439
440
	/* copy entities and nodes */
	assert(!irn_visited(get_irg_end(called_graph)));
	copy_frame_entities(called_graph, irg);
	irg_walk_core(get_irg_end(called_graph), copy_node_inline, set_preds_inline,
	              irg);
441

442
	irp_free_resources(irp, IRP_RESOURCE_ENTITY_LINK);
Michael Beck's avatar
Michael Beck committed
443

444
445
446
447
448
449
450
451
452
453
454
455
456
457
	/* -- Merge the end of the inlined procedure with the call site -- */
	/* We will turn the old Call node into a Tuple with the following
	   predecessors:
	   -1:  Block of Tuple.
	   0: Phi of all Memories of Return statements.
	   1: Jmp from new Block that merges the control flow from all exception
	   predecessors of the old end block.
	   2: Tuple of all arguments.
	   3: Phi of Exception memories.
	   In case the old Call directly branches to End on an exception we don't
	   need the block merging all exceptions nor the Phi of the exception
	   memories.
	*/

458
	/* Precompute some values */
459
460
461
462
	ir_node *end_bl = get_new_node(get_irg_end_block(called_graph));
	ir_node *end    = get_new_node(get_irg_end(called_graph));
	int      arity  = get_Block_n_cfgpreds(end_bl); /* arity = n_exc + n_ret  */
	int      n_res  = get_method_n_ress(get_Call_type(call));
463

464
465
	ir_node **res_pred = XMALLOCN(ir_node*, n_res);
	ir_node **cf_pred  = XMALLOCN(ir_node*, arity);
466

467
	/* archive keepalives */
468
469
	int irn_arity = get_irn_arity(end);
	for (int i = 0; i < irn_arity; i++) {
470
		ir_node *ka = get_End_keepalive(end, i);
471
		if (!is_Bad(ka))
472
			add_End_keepalive(get_irg_end(irg), ka);
473
474
	}

475
	/* replace Return nodes by Jump nodes */
476
477
478
	int n_ret = 0;
	for (int i = 0; i < arity; i++) {
		ir_node *ret = get_Block_cfgpred(end_bl, i);
479
		if (is_Return(ret)) {
480
481
			ir_node *block = get_nodes_block(ret);
			cf_pred[n_ret] = new_r_Jmp(block);
482
483
484
			n_ret++;
		}
	}
485
486
487
488
489
490
491
	/* avoid blocks without any inputs */
	if (n_ret == 0) {
		ir_node *in[] = { new_r_Bad(irg, mode_X) };
		set_irn_in(post_bl, ARRAY_SIZE(in), in);
	} else {
		set_irn_in(post_bl, n_ret, cf_pred);
	}
492

493
494
	/* build a Tuple for all results of the method.
	 * add Phi node if there was more than one Return. */
495
	/* First the Memory-Phi */
496
497
498
	int n_mem_phi = 0;
	for (int i = 0; i < arity; i++) {
		ir_node *ret = get_Block_cfgpred(end_bl, i);
499
		if (is_Return(ret)) {
500
501
502
503
			cf_pred[n_mem_phi++] = get_Return_mem(ret);
		}
		/* memory output for some exceptions is directly connected to End */
		if (is_Call(ret)) {
504
			cf_pred[n_mem_phi++] = new_r_Proj(ret, mode_M, 3);
505
		} else if (is_fragile_op(ret)) {
506
507
			/* We rely that all cfops have the memory output at the same
			 * position. */
508
			cf_pred[n_mem_phi++] = new_r_Proj(ret, mode_M, 0);
509
		} else if (is_Raise(ret)) {
510
			cf_pred[n_mem_phi++] = new_r_Proj(ret, mode_M, 1);
511
512
		}
	}
513
	ir_node *const call_mem =
514
515
		n_mem_phi > 0 ? new_r_Phi(post_bl, n_mem_phi, cf_pred, mode_M)
		              : new_r_Bad(irg, mode_M);
yb9976's avatar
yb9976 committed
516
	/* Conserve Phi-list for further inlining -- but might be optimized */
517
518
519
	if (get_nodes_block(call_mem) == post_bl) {
		set_irn_link(call_mem, get_irn_link(post_bl));
		set_irn_link(post_bl, call_mem);
520
521
	}
	/* Now the real results */
yb9976's avatar
yb9976 committed
522
	ir_type *ctp      = get_Call_type(call);
523
	ir_node *call_res;
524
	if (n_res > 0) {
525
		for (int j = 0; j < n_res; j++) {
526
527
			ir_type *res_type     = get_method_res_type(ctp, j);
			bool     is_aggregate = is_aggregate_type(res_type);
528
			ir_mode *res_mode     = is_aggregate ? mode_P
529
			                                     : get_type_mode(res_type);
530
531
532
			int n_ret = 0;
			for (int i = 0; i < arity; i++) {
				ir_node *ret = get_Block_cfgpred(end_bl, i);
533
				if (is_Return(ret)) {
534
					ir_node *res = get_Return_res(ret, j);
535
					if (get_irn_mode(res) != res_mode) {
536
						ir_node *block = get_nodes_block(res);
537
						res = new_r_Conv(block, res, res_mode);
538
539
					}
					cf_pred[n_ret] = res;
540
541
542
					n_ret++;
				}
			}
543
544
545
			ir_node *const phi = n_ret > 0
				? new_r_Phi(post_bl, n_ret, cf_pred, res_mode)
				: new_r_Bad(irg, res_mode);
546
			res_pred[j] = phi;
yb9976's avatar
yb9976 committed
547
			/* Conserve Phi-list for further inlining -- but might be
548
			 * optimized */
549
550
551
552
553
			if (get_nodes_block(phi) == post_bl) {
				set_Phi_next(phi, get_Block_phis(post_bl));
				set_Block_phis(post_bl, phi);
			}
		}
554
		call_res = new_r_Tuple(post_bl, n_res, res_pred);
555
	} else {
556
		call_res = new_r_Bad(irg, mode_T);
557
558
559
	}

	/* Finally the exception control flow.
560
561
	   We have two possible situations:
	   First if the Call branches to an exception handler:
562
563
564
565
	   We need to add a Phi node to collect the memory containing the exception
	   objects.  Further we need to add another block to get a correct
	   representation of this Phi.  To this block we add a Jmp that resolves
	   into the X output of the Call when the Call is turned into a tuple.
566
567
568
	   Second: There is no exception edge. Just add all inlined exception
	   branches to the End node.
	 */
569
	ir_node *call_x_exc;
570
	if (exc_handling == exc_handler) {
571
572
573
574
		int n_exc = 0;
		for (int i = 0; i < arity; i++) {
			ir_node *ret = get_Block_cfgpred(end_bl, i);
			ir_node *irn = skip_Proj(ret);
575
576
577
578
579
580
			if (is_fragile_op(irn) || is_Raise(irn)) {
				cf_pred[n_exc] = ret;
				++n_exc;
			}
		}
		if (n_exc > 0) {
581
582
			if (n_exc == 1) {
				/* simple fix */
583
				call_x_exc = cf_pred[0];
584
			} else {
585
				ir_node *block = new_r_Block(irg, n_exc, cf_pred);
586
				call_x_exc = new_r_Jmp(block);
587
			}
588
		} else {
589
			call_x_exc = new_r_Bad(irg, mode_X);
590
591
592
		}
	} else {
		/* assert(exc_handling == 1 || no exceptions. ) */
593
594
		int n_exc = 0;
		for (int i = 0; i < arity; i++) {
595
			ir_node *ret = get_Block_cfgpred(end_bl, i);
596
597
598
599
600
601
602
			ir_node *irn = skip_Proj(ret);

			if (is_fragile_op(irn) || is_Raise(irn)) {
				cf_pred[n_exc] = ret;
				n_exc++;
			}
		}
603
604
605
		ir_node  *main_end_bl       = get_irg_end_block(irg);
		int       main_end_bl_arity = get_irn_arity(main_end_bl);
		ir_node **end_preds         = XMALLOCN(ir_node*, n_exc+main_end_bl_arity);
606

607
608
		foreach_irn_in(main_end_bl, i, pred)
			end_preds[i] = pred;
609
		for (int i = 0; i < n_exc; ++i)
610
611
			end_preds[main_end_bl_arity + i] = cf_pred[i];
		set_irn_in(main_end_bl, n_exc + main_end_bl_arity, end_preds);
612
		call_x_exc = new_r_Bad(irg, mode_X);
613
614
615
616
617
		free(end_preds);
	}
	free(res_pred);
	free(cf_pred);

618
	ir_node *call_in[pn_Call_max+1] = {
619
620
621
		[pn_Call_M]         = call_mem,
		[pn_Call_T_result]  = call_res,
	};
622
623
624
625
626
627
628
629
	int n_in = 2;
	assert(pn_Call_M == 0 && pn_Call_T_result == 1);
	if (ir_throws_exception(call)) {
		call_in[pn_Call_X_regular] = new_r_Jmp(post_bl);
		call_in[pn_Call_X_except]  = call_x_exc;
		n_in = 4;
	}
	turn_into_tuple(call, n_in, call_in);
630

631
632
	/* --  Turn CSE back on. -- */
	set_optimize(rem_opt);
633
	current_ir_graph = rem;
634

635
636
	confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);

637
	return true;
638
639
}

640
641
static struct obstack  temp_obst;

642
/** Represents a possible inlinable call in a graph. */
643
typedef struct call_entry {
Michael Beck's avatar
Michael Beck committed
644
645
646
647
648
	ir_node    *call;       /**< The Call node. */
	ir_graph   *callee;     /**< The callee IR-graph. */
	list_head  list;        /**< List head for linking the next one. */
	int        loop_depth;  /**< The loop depth of this call. */
	int        benefice;    /**< The calculated benefice of this call. */
649
	bool       all_const:1; /**< Set if this call has only constant parameters. */
Michael Beck's avatar
Michael Beck committed
650
} call_entry;
651
652
653
654
655

/**
 * Environment for inlining irgs.
 */
typedef struct {
Michael Beck's avatar
Michael Beck committed
656
657
658
659
660
661
662
663
664
665
666
	list_head calls;             /**< List of of all call nodes in this graph. */
	unsigned  *local_weights;    /**< Once allocated, the beneficial weight for transmitting local addresses. */
	unsigned  n_nodes;           /**< Number of nodes in graph except Id, Tuple, Proj, Start, End. */
	unsigned  n_blocks;          /**< Number of Blocks in graph without Start and End block. */
	unsigned  n_nodes_orig;      /**< for statistics */
	unsigned  n_call_nodes;      /**< Number of Call nodes in the graph. */
	unsigned  n_call_nodes_orig; /**< for statistics */
	unsigned  n_callers;         /**< Number of known graphs that call this graphs. */
	unsigned  n_callers_orig;    /**< for statistics */
	unsigned  got_inline:1;      /**< Set, if at least one call inside this graph was inlined. */
	unsigned  recursive:1;       /**< Set, if this function is self recursive. */
667
668
669
670
671
} inline_irg_env;

/**
 * Allocate a new environment for inlining.
 */
672
673
static inline_irg_env *alloc_inline_irg_env(void)
{
674
	inline_irg_env *env = OALLOC(&temp_obst, inline_irg_env);
Michael Beck's avatar
Michael Beck committed
675
676
	INIT_LIST_HEAD(&env->calls);
	env->local_weights     = NULL;
677
	env->n_nodes           = 0;
678
	env->n_blocks          = -1; /* do not count count End Block */
679
	env->n_nodes_orig      = 0;
680
681
682
683
684
	env->n_call_nodes      = 0;
	env->n_call_nodes_orig = 0;
	env->n_callers         = 0;
	env->n_callers_orig    = 0;
	env->got_inline        = 0;
Michael Beck's avatar
Michael Beck committed
685
	env->recursive         = 0;
686
687
688
689
	return env;
}

typedef struct walker_env {
690
691
	inline_irg_env *x;              /**< the inline environment */
	bool            ignore_callers; /**< if set, do change callers data */
692
693
} wenv_t;

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
static bool is_nop(const ir_node *node)
{
	unsigned code = get_irn_opcode(node);
	switch (code) {
	case iro_Anchor:
	case iro_Bad:
	case iro_Confirm:
	case iro_Deleted:
	case iro_Dummy:
	case iro_End:
	case iro_Id:
	case iro_NoMem:
	case iro_Pin:
	case iro_Proj:
	case iro_Start:
	case iro_Sync:
	case iro_Tuple:
	case iro_Unknown:
		return true;
	case iro_Phi:
		return get_irn_mode(node) == mode_M;
	default:
		return false;
	}
}

720
721
722
723
/**
 * post-walker: collect all calls in the inline-environment
 * of a graph and sum some statistics.
 */
724
static void collect_calls2(ir_node *node, void *ctx)
725
{
726
	wenv_t         *env = (wenv_t*)ctx;
727
	inline_irg_env *x   = env->x;
728

729
730
731
732
733
734
735
736
	if (is_nop(node))
		return;

	if (is_Block(node)) {
		++x->n_blocks;
	} else {
		++x->n_nodes;
		++x->n_nodes_orig;
737
738
	}

739
	if (!is_Call(node))
740
		return;
741
742
743
744
745

	/* collect all call nodes */
	++x->n_call_nodes;
	++x->n_call_nodes_orig;

746
	ir_entity *callee_ent = get_Call_callee(node);
747
748
749
	if (callee_ent == NULL)
		return;
	ir_graph *callee = get_entity_linktime_irg(callee_ent);
750
	if (callee != NULL) {
751
		if (!env->ignore_callers) {
752
			inline_irg_env *callee_env = (inline_irg_env*)get_irg_link(callee);
753
754
755
756
			/* count all static callers */
			++callee_env->n_callers;
			++callee_env->n_callers_orig;
		}
Michael Beck's avatar
Michael Beck committed
757
758
		if (callee == current_ir_graph)
			x->recursive = 1;
759
760

		/* link it in the list of possible inlinable entries */
761
		call_entry *entry = OALLOC(&temp_obst, call_entry);
762
		entry->call       = node;
763
		entry->callee     = callee;
764
		entry->loop_depth = get_irn_loop(get_nodes_block(node))->depth;
Michael Beck's avatar
Michael Beck committed
765
		entry->benefice   = 0;
766
		entry->all_const  = false;
767

Michael Beck's avatar
Michael Beck committed
768
		list_add_tail(&entry->list, &x->calls);
769
770
771
772
	}
}

/**
Michael Beck's avatar
Michael Beck committed
773
774
775
776
777
778
 * Duplicate a call entry.
 *
 * @param entry     the original entry to duplicate
 * @param new_call  the new call node
 * @param loop_depth_delta
 *                  delta value for the loop depth
779
 */
780
static call_entry *duplicate_call_entry(const call_entry *entry,
781
782
                                        ir_node *new_call, int loop_depth_delta)
{
783
	call_entry *nentry = OALLOC(&temp_obst, call_entry);
784
785
	nentry->call       = new_call;
	nentry->callee     = entry->callee;
Michael Beck's avatar
Michael Beck committed
786
	nentry->benefice   = entry->benefice;
787
	nentry->loop_depth = entry->loop_depth + loop_depth_delta;
Michael Beck's avatar
Michael Beck committed
788
	nentry->all_const  = entry->all_const;
789

790
	return nentry;
791
792
}

793
/**
794
795
 * Calculate the parameter weights for transmitting the address of a local
 * variable.
796
 */
797
798
static unsigned calc_method_local_weight(ir_node *arg)
{
799
	unsigned weight = 0;
800
	foreach_irn_out_r(arg, i, succ) {
801
802
803
804
805
806
807
		switch (get_irn_opcode(succ)) {
		case iro_Load:
		case iro_Store:
			/* Loads and Store can be removed */
			weight += 3;
			break;
		case iro_Sel:
808
809
810
811
			if (!is_Const(get_Sel_index(succ)))
				return 0;
			/* FALLTHROUGH */
		case iro_Member: {
812
813
			/* Check users on this Sel. Note: if a 0 is returned here, there was
			   some unsupported node. */
814
			unsigned v = calc_method_local_weight(succ);
815
816
817
818
819
			if (v == 0)
				return 0;
			/* we can kill one Sel with constant indexes, this is cheap */
			weight += v + 1;
			break;
820
		}
821
822
823
824
825
826
		case iro_Id:
			/* when looking backward we might find Id nodes */
			weight += calc_method_local_weight(succ);
			break;
		case iro_Tuple:
			/* unoptimized tuple */
827
			for (unsigned j = get_Tuple_n_preds(succ); j-- > 0; ) {
828
829
830
				ir_node *pred = get_Tuple_pred(succ, j);
				if (pred == arg) {
					/* look for Proj(j) */
831
					foreach_irn_out_r(succ, k, succ_succ) {
832
						if (is_Proj(succ_succ)) {
833
							if (get_Proj_num(succ_succ) == j) {
834
835
836
837
838
839
840
841
842
843
								/* found */
								weight += calc_method_local_weight(succ_succ);
							}
						} else {
							/* this should NOT happen */
							return 0;
						}
					}
				}
			}
844
			break;
845
846
847
848
849
850
851
852
853
		default:
			/* any other node: unsupported yet or bad. */
			return 0;
		}
	}
	return weight;
}

/**
854
855
 * Calculate the parameter weights for transmitting the address of a local
 * variable.
856
 */
857
858
static void analyze_irg_local_weights(inline_irg_env *env, ir_graph *irg)
{
859
860
861
862
	ir_entity *ent     = get_irg_entity(irg);
	ir_type   *mtp     = get_entity_type(ent);
	size_t     nparams = get_method_n_params(mtp);
	env->local_weights = OALLOCNZ(&temp_obst, unsigned, nparams);
863
864

	assure_irg_outs(irg);
865
	ir_node *irg_args = get_irg_args(irg);
866
	foreach_irn_out_r(irg_args, i, arg) {
867
		unsigned const pn = get_Proj_num(arg);
868
		env->local_weights[pn] = calc_method_local_weight(arg);
869
870
871
872
873
874
875
876
	}
}

/**
 * Calculate the benefice for transmitting an local variable address.
 * After inlining, the local variable might be transformed into a
 * SSA variable by scalar_replacement().
 */
877
static unsigned get_method_local_adress_weight(ir_graph *callee, size_t pos)
878
{
879
	inline_irg_env *env = (inline_irg_env*)get_irg_link(callee);
880

881
882
	if (env->local_weights == NULL)
		analyze_irg_local_weights(env, callee);
883

884
885
	assert(pos < get_method_n_params(get_entity_type(get_irg_entity(callee))));
	return env->local_weights[pos];
886
887
}

888
/**
889
890
891
892
 * Calculate a benefice value for inlining the given call.
 *
 * @param call       the call node we have to inspect
 * @param callee     the called graph
893
 */
Michael Beck's avatar
Michael Beck committed
894
static int calc_inline_benefice(call_entry *entry, ir_graph *callee)
895
{
yb9976's avatar
yb9976 committed
896
897
898
	ir_node                   *call  = entry->call;
	ir_entity                 *ent   = get_irg_entity(callee);
	mtp_additional_properties  props = get_entity_additional_properties(ent);
Matthias Braun's avatar
Matthias Braun committed
899
	if (props & mtp_property_noinline) {
900
901
		DB((dbg, LEVEL_2, "In %+F Call to %+F: inlining forbidden\n",
		    call, callee));
Michael Beck's avatar
Michael Beck committed
902
		return entry->benefice = INT_MIN;
903
	}
904

Matthias Braun's avatar
Matthias Braun committed
905
	if (props & mtp_property_noreturn) {
906
907
		DB((dbg, LEVEL_2, "In %+F Call to %+F: not inlining noreturn or weak\n",
		    call, callee));
Michael Beck's avatar
Michael Beck committed
908
		return entry->benefice = INT_MIN;
909
910
911
	}

	/* costs for every passed parameter */
yb9976's avatar
yb9976 committed
912
913
914
915
	size_t    n_params = get_Call_n_params(call);
	ir_type  *mtp      = get_entity_type(ent);
	unsigned  cc       = get_method_calling_convention(mtp);
	int64_t   weight   = 0;
916
917
	if (cc & cc_reg_param) {
		/* register parameter, smaller costs for register parameters */
Andreas Zwinkau's avatar
Andreas Zwinkau committed
918
		size_t max_regs = cc & ~cc_bits;
919
920
921
922
923
924
925
926
927
928

		if (max_regs < n_params)
			weight += max_regs * 2 + (n_params - max_regs) * 5;
		else
			weight += n_params * 2;
	} else {
		/* parameters are passed an stack */
		weight += 5 * n_params;
	}

Michael Beck's avatar
Michael Beck committed
929
	/* constant parameters improve the benefice */
930
931
932
	ir_node *frame_ptr = get_irg_frame(current_ir_graph);
	bool     all_const = true;
	for (size_t i = 0; i < n_params; ++i) {
933
934
		ir_node *param = get_Call_param(call, i);

935
		if (is_Const(param)) {
936
			weight += get_method_param_weight(ent, i);
937
		} else {
938
			all_const = false;
939
			if (is_Address(param) || is_Align(param) || is_Offset(param) || is_Size(param))
Michael Beck's avatar
Michael Beck committed
940
				weight += get_method_param_weight(ent, i);
941
942
			else if (is_Sel(param) && get_Sel_ptr(param) == frame_ptr
			         && i < get_method_n_params(mtp)) {
Michael Beck's avatar
Michael Beck committed
943
				/*
944
945
946
				 * An address of a local variable is transmitted. After
				 * inlining, scalar_replacement might be able to remove the
				 * local variable, so honor this.
Michael Beck's avatar
Michael Beck committed
947
				 */
948
				weight += get_method_local_adress_weight(callee, i);
Michael Beck's avatar
Michael Beck committed
949
			}
950
		}
951
	}
Michael Beck's avatar
Michael Beck committed
952
	entry->all_const = all_const;