opt_inline.c 54 KB
Newer Older
1
/*
2
 * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 *
 * 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.
 */

/**
 * @file
 * @brief    Dead node elimination and Procedure Inlining.
 * @author   Michael Beck, Goetz Lindenmaier
 * @version  $Id$
 */
Matthias Braun's avatar
Matthias Braun committed
26
#include "config.h"
27

28
#include <limits.h>
29
#include <stdbool.h>
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <assert.h>

#include "irnode_t.h"
#include "irgraph_t.h"
#include "irprog_t.h"

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

43
44
45
46
47
48
49
#include "array_t.h"
#include "list.h"
#include "pset.h"
#include "pmap.h"
#include "pdeq.h"
#include "xmalloc.h"
#include "pqueue.h"
50
51
52
53

#include "irouts.h"
#include "irloop_t.h"
#include "irbackedge_t.h"
54
#include "opt_init.h"
55
56
57
58
#include "cgana.h"
#include "trouts.h"
#include "error.h"

59
#include "analyze_irg_args.h"
60
61
62
63
#include "iredges_t.h"
#include "irflag_t.h"
#include "irhooks.h"
#include "irtools.h"
64
#include "iropt_dbg.h"
65
#include "irpass_t.h"
66
#include "irphase_t.h"
67

68
DEBUG_ONLY(static firm_dbg_module_t *dbg;)
69
70
71
72
73
74
75
76
77

/*------------------------------------------------------------------*/
/* Routines for dead node elimination / copying garbage collection  */
/* of the obstack.                                                  */
/*------------------------------------------------------------------*/

/**
 * Remember the new node in the old node by using a field all nodes have.
 */
78
79
80
81
static void set_new_node(ir_node *node, ir_node *new_node)
{
	set_irn_link(node, new_node);
}
82
83
84
85

/**
 * Get this new node, before the old node is forgotten.
 */
86
87
88
89
90
static inline ir_node *get_new_node(ir_node *old_node)
{
	assert(irn_visited(old_node));
	return (ir_node*) get_irn_link(old_node);
}
91
92
93
94
95
96
97
98
99
100
101
102
103
104

/*--------------------------------------------------------------------*/
/*  Functionality for inlining                                         */
/*--------------------------------------------------------------------*/

/**
 * Copy node for inlineing.  Updates attributes that change when
 * inlineing but not for dead node elimination.
 *
 * 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.
 */
105
static void copy_node_inline(ir_node *node, void *env)
106
{
107
108
109
110
	ir_graph *new_irg  = (ir_graph*) env;
	ir_node  *new_node = irn_copy_into_irg(node, new_irg);

	set_new_node(node, new_node);
111
112
113
114
115
	if (is_Sel(node)) {
		ir_graph  *old_irg        = get_irn_irg(node);
		ir_type   *old_frame_type = get_irg_frame_type(old_irg);
		ir_entity *old_entity     = get_Sel_entity(node);
		assert(is_Sel(new_node));
116
		/* use copied entities from the new frame */
117
		if (get_entity_owner(old_entity) == old_frame_type) {
118
			ir_entity *new_entity = (ir_entity*)get_entity_link(old_entity);
119
120
			assert(new_entity != NULL);
			set_Sel_entity(new_node, new_entity);
121
		}
122
123
	} else if (is_Block(new_node)) {
		new_node->attr.block.irg.irg = new_irg;
124
125
126
	}
}

127
static void set_preds_inline(ir_node *node, void *env)
128
{
129
130
	ir_node *new_node;

131
	irn_rewire_inputs(node);
132
133
134
135
136
137
138

	/* move constants into start block */
	new_node = get_new_node(node);
	if (is_irn_constlike(new_node)) {
		ir_graph *new_irg     = (ir_graph *) env;
		ir_node  *start_block = get_irg_start_block(new_irg);
		set_nodes_block(new_node, start_block);
139
140
141
	}
}

142
143
144
/**
 * Walker: checks if P_value_arg_base is used.
 */
145
146
static void find_addr(ir_node *node, void *env)
{
147
	bool *allow_inline = (bool*)env;
148

149
150
151
152
153
154
155
	if (is_Sel(node)) {
		ir_graph *irg = current_ir_graph;
		if (get_Sel_ptr(node) == get_irg_frame(irg)) {
			/* access to frame */
			ir_entity *ent = get_Sel_entity(node);
			if (get_entity_owner(ent) != get_irg_frame_type(irg)) {
				/* access to value_type */
156
				*allow_inline = false;
157
			}
158
159
160
			if (is_parameter_entity(ent)) {
				*allow_inline = false;
			}
161
		}
162
163
164
165
166
167
168
	} else if (is_Alloc(node) && get_Alloc_where(node) == stack_alloc) {
		/* 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
169
		 * Sorrily this is true with our implementation also.
170
171
172
		 * Moreover, we cannot differentiate between alloca() and VLA yet, so
		 * this disables inlining of functions using VLA (which are completely
		 * save).
173
174
175
		 *
		 * 2 Solutions:
		 * - add a flag to the Alloc node for "real" alloca() calls
176
177
		 * - add a new Stack-Restore node at the end of a function using
		 *   alloca()
178
		 */
179
		*allow_inline = false;
180
181
182
183
184
185
186
187
188
189
190
	}
}

/**
 * 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
 */
191
static bool can_inline(ir_node *call, ir_graph *called_graph)
192
{
193
194
195
	ir_entity          *called      = get_irg_entity(called_graph);
	ir_type            *called_type = get_entity_type(called);
	ir_type            *call_type   = get_Call_type(call);
196
197
198
	size_t              n_params    = get_method_n_params(called_type);
	size_t              n_arguments = get_method_n_params(call_type);
	size_t              n_res       = get_method_n_ress(called_type);
199
	irg_inline_property prop        = get_irg_inline_property(called_graph);
200
	size_t              i;
201
	bool                res;
202
203

	if (prop == irg_inline_forbidden)
204
		return false;
205

206
	if (n_arguments != n_params) {
Michael Beck's avatar
Michael Beck committed
207
208
209
		/* 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. */
210
		return false;
Michael Beck's avatar
Michael Beck committed
211
	}
212
213
	if (n_res != get_method_n_ress(call_type)) {
		return false;
214
	}
215

Michael Beck's avatar
Michael Beck committed
216
	/* Argh, compiling C has some bad consequences:
Michael Beck's avatar
Michael Beck committed
217
218
219
	 * 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. */
220
	for (i = 0; i < n_params; ++i) {
221
222
		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
223
224
225
226
227
228

		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)
229
				return false;
Michael Beck's avatar
Michael Beck committed
230
			if (get_mode_size_bits(pmode) != get_mode_size_bits(amode))
231
				return false;
Michael Beck's avatar
Michael Beck committed
232
			if (get_mode_arithmetic(pmode) != get_mode_arithmetic(amode))
233
				return false;
Michael Beck's avatar
Michael Beck committed
234
			/* otherwise we can simply "reinterpret" the bits */
235
		}
236
	}
237
	for (i = 0; i < n_res; ++i) {
238
239
		ir_type *decl_res_tp = get_method_res_type(called_type, i);
		ir_type *used_res_tp = get_method_res_type(call_type, i);
240
241
242
243
244

		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)
245
				return false;
246
			if (get_mode_size_bits(decl_mode) != get_mode_size_bits(used_mode))
247
				return false;
248
			if (get_mode_arithmetic(decl_mode) != get_mode_arithmetic(used_mode))
249
				return false;
250
251
252
			/* otherwise we can "reinterpret" the bits */
		}
	}
253

254
255
256
	/* check parameters for compound arguments */
	for (i = 0; i < n_params; ++i) {
		ir_type *p_type = get_method_param_type(call_type, i);
257

258
259
260
		if (is_compound_type(p_type))
			return false;
	}
261

262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
	/* check results for compound arguments */
	for (i = 0; i < n_res; ++i) {
		ir_type *r_type = get_method_res_type(call_type, i);

		if (is_compound_type(r_type))
			return false;
	}

	res = true;
	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. */
};

/**
 * copy all entities on the stack frame on 1 irg to the stackframe of another.
 * 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);
Michael Beck's avatar
Michael Beck committed
289
290
	size_t   n_members  = get_class_n_members(from_frame);
	size_t   i;
291
292
293
294
295
296
	assert(from_frame != to_frame);

	for (i = 0; i < n_members; ++i) {
		ir_entity *old_ent = get_class_member(from_frame, i);
		ir_entity *new_ent = copy_entity_own(old_ent, to_frame);
		set_entity_link(old_ent, new_ent);
297
		assert (!is_parameter_entity(old_ent));
298
299
300
301
302
303
304
305
	}
}

/* Inlines a method at the given call site. */
int inline_method(ir_node *call, ir_graph *called_graph)
{
	ir_node       *pre_call;
	ir_node       *post_call, *post_bl;
306
	ir_node       *in[pn_Start_max+1];
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
	ir_node       *end, *end_bl, *block;
	ir_node       **res_pred;
	ir_node       **cf_pred;
	ir_node       **args_in;
	ir_node       *ret, *phi;
	int           arity, n_ret, n_exc, n_res, i, j, rem_opt;
	int           irn_arity, n_params;
	int           n_mem_phi;
	enum exc_mode exc_handling;
	ir_type       *mtp;
	ir_type       *ctp;
	ir_entity     *ent;
	ir_graph      *rem;
	ir_graph      *irg = get_irn_irg(call);

	/* we cannot inline some types of calls */
323
324
325
	if (! can_inline(call, called_graph))
		return 0;

326
327
328
329
330
331
332
333
334
335
336
	/* We cannot inline a recursive call. The graph must be copied before
	 * the call the inline_method() using create_irg_copy(). */
	if (called_graph == irg)
		return 0;

	ent      = get_irg_entity(called_graph);
	mtp      = get_entity_type(ent);
	ctp      = get_Call_type(call);
	n_params = get_method_n_params(mtp);
	n_res    = get_method_n_ress(mtp);

337
338
339
	rem = current_ir_graph;
	current_ir_graph = irg;

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

342
	/* optimizations can cause problems when allocating new nodes */
343
344
345
346
	rem_opt = get_opt_optimize();
	set_optimize(0);

	/* Handle graph state */
347
348
	assert(get_irg_phase_state(irg) != phase_building);
	assert(get_irg_pinned(irg) == op_pin_state_pinned);
349
	assert(get_irg_pinned(called_graph) == op_pin_state_pinned);
350
351
352
	set_irg_extblk_inconsistent(irg);
	set_irg_doms_inconsistent(irg);
	set_irg_callee_info_state(irg, irg_callee_info_inconsistent);
353
	set_irg_entity_usage_state(irg, ir_entity_usage_not_computed);
354
	edges_deactivate(irg);
355
356
357
358
359
360
361
362
363
364

	/* 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. -- */
	{
365
366
		ir_node *Xproj = NULL;
		ir_node *proj;
367
368
		for (proj = (ir_node*)get_irn_link(call); proj != NULL;
		     proj = (ir_node*)get_irn_link(proj)) {
369
370
371
			long proj_nr = get_Proj_proj(proj);
			if (proj_nr == pn_Call_X_except) Xproj = proj;
		}
372
		exc_handling = Xproj != NULL ? exc_handler : exc_no_handler;
373
374
	}

Michael Beck's avatar
Michael Beck committed
375
	/* create the argument tuple */
376
	args_in = ALLOCAN(ir_node*, n_params);
Michael Beck's avatar
Michael Beck committed
377
378
379
380
381
382
383
384

	block = get_nodes_block(call);
	for (i = n_params - 1; i >= 0; --i) {
		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);

		if (mode != get_irn_mode(arg)) {
385
			arg = new_r_Conv(block, arg, mode);
Michael Beck's avatar
Michael Beck committed
386
387
388
389
		}
		args_in[i] = arg;
	}

390
391
392
	/* 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. */
393
394
	post_bl = get_nodes_block(call);
	/* XxMxPxPxPxT of Start + parameter of Call */
395
396
397
398
	in[pn_Start_M]              = get_Call_mem(call);
	in[pn_Start_X_initial_exec] = new_r_Jmp(post_bl);
	in[pn_Start_P_frame_base]   = get_irg_frame(irg);
	in[pn_Start_T_args]         = new_r_Tuple(post_bl, n_params, args_in);
399
	pre_call = new_r_Tuple(post_bl, pn_Start_max+1, in);
400
401
402
403
404
405
406
	post_call = call;

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

407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
	/* 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 */
	{
		ir_node *start_block;
		ir_node *start;
		ir_node *nomem;

		start_block = get_irg_start_block(called_graph);
		set_new_node(start_block, get_nodes_block(pre_call));
		mark_irn_visited(start_block);

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

		nomem = get_irg_no_mem(called_graph);
		set_new_node(nomem, get_irg_no_mem(irg));
		mark_irn_visited(nomem);
432
433
	}

434
435
	/* entitiy link is used to link entities on old stackframe to the
	 * new stackframe */
436
	irp_reserve_resources(irp, IRP_RESOURCE_ENTITY_LINK);
437

438
439
440
441
442
	/* 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);
443

444
	irp_free_resources(irp, IRP_RESOURCE_ENTITY_LINK);
Michael Beck's avatar
Michael Beck committed
445

446
447
448
449
450
451
452
453
454
455
456
457
458
459
	/* -- 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.
	*/

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

466
467
	res_pred = XMALLOCN(ir_node*, n_res);
	cf_pred  = XMALLOCN(ir_node*, arity);
468

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

477
	/* replace Return nodes by Jump nodes */
478
479
480
	n_ret = 0;
	for (i = 0; i < arity; i++) {
		ir_node *ret;
481
		ret = get_Block_cfgpred(end_bl, i);
482
		if (is_Return(ret)) {
483
484
			ir_node *block = get_nodes_block(ret);
			cf_pred[n_ret] = new_r_Jmp(block);
485
486
487
488
489
			n_ret++;
		}
	}
	set_irn_in(post_bl, n_ret, cf_pred);

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

	/* Finally the exception control flow.
557
558
559
	   We have two possible situations:
	   First if the Call branches to an exception handler:
	   We need to add a Phi node to
560
561
562
563
	   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.
564
565
566
	   Second: There is no exception edge. Just add all inlined exception
	   branches to the End node.
	 */
567
568
569
570
	if (exc_handling == exc_handler) {
		n_exc = 0;
		for (i = 0; i < arity; i++) {
			ir_node *ret, *irn;
571
			ret = get_Block_cfgpred(end_bl, i);
572
573
574
575
576
577
578
			irn = skip_Proj(ret);
			if (is_fragile_op(irn) || is_Raise(irn)) {
				cf_pred[n_exc] = ret;
				++n_exc;
			}
		}
		if (n_exc > 0) {
579
580
581
582
			if (n_exc == 1) {
				/* simple fix */
				set_Tuple_pred(call, pn_Call_X_except, cf_pred[0]);
			} else {
583
584
				ir_node *block = new_r_Block(irg, n_exc, cf_pred);
				set_Tuple_pred(call, pn_Call_X_except, new_r_Jmp(block));
585
			}
586
		} else {
Matthias Braun's avatar
Matthias Braun committed
587
			set_Tuple_pred(call, pn_Call_X_except, new_r_Bad(irg, mode_X));
588
589
590
591
592
593
594
595
596
		}
	} else {
		ir_node *main_end_bl;
		int main_end_bl_arity;
		ir_node **end_preds;

		/* assert(exc_handling == 1 || no exceptions. ) */
		n_exc = 0;
		for (i = 0; i < arity; i++) {
597
			ir_node *ret = get_Block_cfgpred(end_bl, i);
598
599
600
601
602
603
604
			ir_node *irn = skip_Proj(ret);

			if (is_fragile_op(irn) || is_Raise(irn)) {
				cf_pred[n_exc] = ret;
				n_exc++;
			}
		}
605
		main_end_bl       = get_irg_end_block(irg);
606
		main_end_bl_arity = get_irn_arity(main_end_bl);
607
		end_preds         = XMALLOCN(ir_node*, n_exc + main_end_bl_arity);
608
609
610
611
612
613

		for (i = 0; i < main_end_bl_arity; ++i)
			end_preds[i] = get_irn_n(main_end_bl, i);
		for (i = 0; i < n_exc; ++i)
			end_preds[main_end_bl_arity + i] = cf_pred[i];
		set_irn_in(main_end_bl, n_exc + main_end_bl_arity, end_preds);
Matthias Braun's avatar
Matthias Braun committed
614
		set_Tuple_pred(call, pn_Call_X_except, new_r_Bad(irg, mode_X));
615
616
617
618
619
620
621
		free(end_preds);
	}
	free(res_pred);
	free(cf_pred);

	/* --  Turn CSE back on. -- */
	set_optimize(rem_opt);
622
	current_ir_graph = rem;
623
624
625
626
627

	return 1;
}

/********************************************************************/
Michael Beck's avatar
Michael Beck committed
628
/* Apply inlining to small methods.                                 */
629
630
/********************************************************************/

631
632
static struct obstack  temp_obst;

633
/** Represents a possible inlinable call in a graph. */
634
typedef struct call_entry {
Michael Beck's avatar
Michael Beck committed
635
636
637
638
639
640
641
	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. */
	unsigned   local_adr:1; /**< Set if this call gets an address of a local variable. */
	unsigned   all_const:1; /**< Set if this call has only constant parameters. */
Michael Beck's avatar
Michael Beck committed
642
} call_entry;
643
644
645
646

/**
 * environment for inlining small irgs
 */
647
typedef struct inline_env_t {
Michael Beck's avatar
Michael Beck committed
648
649
	struct obstack obst;  /**< An obstack where call_entries are allocated on. */
	list_head      calls; /**< The call entry list. */
650
651
652
653
654
655
656
657
} inline_env_t;

/**
 * Returns the irg called from a Call node. If the irg is not
 * known, NULL is returned.
 *
 * @param call  the call node
 */
658
659
static ir_graph *get_call_called_irg(ir_node *call)
{
660
661
662
663
664
	ir_node *addr;

	addr = get_Call_ptr(call);
	if (is_Global(addr)) {
		ir_entity *ent = get_Global_entity(addr);
665
666
667
668
		/* we don't know which function gets finally bound to a weak symbol */
		if (get_entity_linkage(ent) & IR_LINKAGE_WEAK)
			return NULL;

669
670
671
672
673
674
675
676
677
		return get_entity_irg(ent);
	}

	return NULL;
}

/**
 * Walker: Collect all calls to known graphs inside a graph.
 */
678
679
static void collect_calls(ir_node *call, void *env)
{
Michael Beck's avatar
Michael Beck committed
680
	(void) env;
681
682
683
684
685
	if (is_Call(call)) {
		ir_graph *called_irg = get_call_called_irg(call);

		if (called_irg != NULL) {
			/* The Call node calls a locally defined method.  Remember to inline. */
686
			inline_env_t *ienv  = (inline_env_t*)env;
687
			call_entry   *entry = OALLOC(&ienv->obst, call_entry);
688
689
690
			entry->call       = call;
			entry->callee     = called_irg;
			entry->loop_depth = 0;
Michael Beck's avatar
Michael Beck committed
691
692
693
			entry->benefice   = 0;
			entry->local_adr  = 0;
			entry->all_const  = 0;
694

Michael Beck's avatar
Michael Beck committed
695
			list_add_tail(&entry->list, &ienv->calls);
696
697
698
699
700
701
702
703
704
705
706
707
		}
	}
}

/**
 * Inlines all small methods at call sites where the called address comes
 * from a Const node that references the entity representing the called
 * method.
 * The size argument is a rough measure for the code size of the method:
 * Methods where the obstack containing the firm graph is smaller than
 * size are inlined.
 */
708
709
void inline_small_irgs(ir_graph *irg, int size)
{
710
	ir_graph *rem = current_ir_graph;
711
712
713
714
715
716
717
718
719
	inline_env_t env;
	call_entry *entry;

	current_ir_graph = irg;
	/* Handle graph state */
	assert(get_irg_phase_state(irg) != phase_building);
	free_callee_info(irg);

	/* Find Call nodes to inline.
Michael Beck's avatar
Michael Beck committed
720
	   (We can not inline during a walk of the graph, as inlining the same
721
	   method several times changes the visited flag of the walked graph:
Michael Beck's avatar
Michael Beck committed
722
723
	   after the first inlining visited of the callee equals visited of
	   the caller.  With the next inlining both are increased.) */
724
	obstack_init(&env.obst);
Michael Beck's avatar
Michael Beck committed
725
	INIT_LIST_HEAD(&env.calls);
726
727
	irg_walk_graph(irg, NULL, collect_calls, &env);

Michael Beck's avatar
Michael Beck committed
728
	if (! list_empty(&env.calls)) {
729
		/* There are calls to inline */
730
		ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
731
		collect_phiprojs(irg);
Michael Beck's avatar
Michael Beck committed
732

Michael Beck's avatar
Michael Beck committed
733
		list_for_each_entry(call_entry, entry, &env.calls, list) {
Michael Beck's avatar
Michael Beck committed
734
735
736
			ir_graph            *callee = entry->callee;
			irg_inline_property prop    = get_irg_inline_property(callee);

737
			if (prop == irg_inline_forbidden) {
Michael Beck's avatar
Michael Beck committed
738
739
740
741
742
				continue;
			}

			if (prop >= irg_inline_forced ||
			    _obstack_memory_used(callee->obst) - (int)obstack_room(callee->obst) < size) {
743
				inline_method(entry->call, callee);
744
745
			}
		}
746
		ir_free_resources(irg, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
747
748
749
750
751
	}
	obstack_free(&env.obst, NULL);
	current_ir_graph = rem;
}

752
typedef struct inline_small_irgs_pass_t {
753
754
	ir_graph_pass_t pass;
	int            size;
755
} inline_small_irgs_pass_t;
756
757
758
759

/**
 * Wrapper to run inline_small_irgs() as a pass.
 */
760
761
static int inline_small_irgs_wrapper(ir_graph *irg, void *context)
{
762
	inline_small_irgs_pass_t *pass = (inline_small_irgs_pass_t*)context;
763
764
765
766
767
768

	inline_small_irgs(irg, pass->size);
	return 0;
}

/* create a pass for inline_small_irgs() */
769
770
ir_graph_pass_t *inline_small_irgs_pass(const char *name, int size)
{
771
	inline_small_irgs_pass_t *pass = XMALLOCZ(inline_small_irgs_pass_t);
772
773
774
775
776
777

	pass->size = size;
	return def_graph_pass_constructor(
		&pass->pass, name ? name : "inline_small_irgs", inline_small_irgs_wrapper);
}

778
779
780
781
/**
 * Environment for inlining irgs.
 */
typedef struct {
Michael Beck's avatar
Michael Beck committed
782
783
784
785
786
787
788
789
790
791
792
	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. */
793
794
795
796
797
} inline_irg_env;

/**
 * Allocate a new environment for inlining.
 */
798
799
static inline_irg_env *alloc_inline_irg_env(void)
{
800
	inline_irg_env *env    = OALLOC(&temp_obst, inline_irg_env);
Michael Beck's avatar
Michael Beck committed
801
802
	INIT_LIST_HEAD(&env->calls);
	env->local_weights     = NULL;
803
	env->n_nodes           = -2; /* do not count count Start, End */
804
	env->n_blocks          = -2; /* do not count count Start, End Block */
805
806
807
808
809
810
	env->n_nodes_orig      = -2; /* do not count Start, End */
	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
811
	env->recursive         = 0;
812
813
814
815
	return env;
}

typedef struct walker_env {
816
817
818
	inline_irg_env *x;     /**< the inline environment */
	char ignore_runtime;   /**< the ignore runtime flag */
	char ignore_callers;   /**< if set, do change callers data */
819
820
821
822
823
824
} wenv_t;

/**
 * post-walker: collect all calls in the inline-environment
 * of a graph and sum some statistics.
 */
825
826
static void collect_calls2(ir_node *call, void *ctx)
{
827
	wenv_t         *env = (wenv_t*)ctx;
828
	inline_irg_env *x = env->x;
829
	unsigned        code = get_irn_opcode(call);
830
831
832
833
834
	ir_graph       *callee;
	call_entry     *entry;

	/* count meaningful nodes in irg */
	if (code != iro_Proj && code != iro_Tuple && code != iro_Sync) {
835
836
837
838
839
840
		if (code != iro_Block) {
			++x->n_nodes;
			++x->n_nodes_orig;
		} else {
			++x->n_blocks;
		}
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
	}

	if (code != iro_Call) return;

	/* check, if it's a runtime call */
	if (env->ignore_runtime) {
		ir_node *symc = get_Call_ptr(call);

		if (is_Global(symc)) {
			ir_entity *ent = get_Global_entity(symc);

			if (get_entity_additional_properties(ent) & mtp_property_runtime)
				return;
		}
	}

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

	callee = get_call_called_irg(call);
	if (callee != NULL) {
		if (! env->ignore_callers) {
864
			inline_irg_env *callee_env = (inline_irg_env*)get_irg_link(callee);
865
866
867
868
			/* count all static callers */
			++callee_env->n_callers;
			++callee_env->n_callers_orig;
		}
Michael Beck's avatar
Michael Beck committed
869
870
		if (callee == current_ir_graph)
			x->recursive = 1;
871
872

		/* link it in the list of possible inlinable entries */
873
		entry = OALLOC(&temp_obst, call_entry);
874
875
876
		entry->call       = call;
		entry->callee     = callee;
		entry->loop_depth = get_irn_loop(get_nodes_block(call))->depth;
Michael Beck's avatar
Michael Beck committed
877
878
879
		entry->benefice   = 0;
		entry->local_adr  = 0;
		entry->all_const  = 0;
880

Michael Beck's avatar
Michael Beck committed
881
		list_add_tail(&entry->list, &x->calls);
882
883
884
885
886
887
888
	}
}

/**
 * Returns TRUE if the number of callers is 0 in the irg's environment,
 * hence this irg is a leave.
 */
889
890
inline static int is_leave(ir_graph *irg)
{
891
	inline_irg_env *env = (inline_irg_env*)get_irg_link(irg);
892
893
894
895
896
897
898
	return env->n_call_nodes == 0;
}

/**
 * Returns TRUE if the number of nodes in the callee is
 * smaller then size in the irg's environment.
 */
899
900
inline static int is_smaller(ir_graph *callee, unsigned size)
{
901
	inline_irg_env *env = (inline_irg_env*)get_irg_link(callee);
902
903
904
905
	return env->n_nodes < size;
}

/**
Michael Beck's avatar
Michael Beck committed
906
907
908
909
910
911
 * 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
912
 */
913
static call_entry *duplicate_call_entry(const call_entry *entry,
914
915
                                        ir_node *new_call, int loop_depth_delta)
{
916
	call_entry *nentry = OALLOC(&temp_obst, call_entry);
917
918
	nentry->call       = new_call;
	nentry->callee     = entry->callee;
Michael Beck's avatar
Michael Beck committed
919
	nentry->benefice   = entry->benefice;
920
	nentry->loop_depth = entry->loop_depth + loop_depth_delta;
Michael Beck's avatar
Michael Beck committed
921
922
	nentry->local_adr  = entry->local_adr;
	nentry->all_const  = entry->all_const;
923

924
	return nentry;
925
926
}

Michael Beck's avatar
Michael Beck committed
927
928
929
930
931
932
933
934
/**
 * Append all call nodes of the source environment to the nodes of in the destination
 * environment.
 *
 * @param dst         destination environment
 * @param src         source environment
 * @param loop_depth  the loop depth of the call that is replaced by the src list
 */
935
936
static void append_call_list(inline_irg_env *dst, inline_irg_env *src, int loop_depth)
{
Michael Beck's avatar
Michael Beck committed
937
938
939
940
941
942
	call_entry *entry, *nentry;

	/* Note that the src list points to Call nodes in the inlined graph, but
	   we need Call nodes in our graph. Luckily the inliner leaves this information
	   in the link field. */
	list_for_each_entry(call_entry, entry, &src->calls, list) {
943
		nentry = duplicate_call_entry(entry, (ir_node*)get_irn_link(entry->call), loop_depth);
Michael Beck's avatar
Michael Beck committed
944
945
946
947
948
949
		list_add_tail(&nentry->list, &dst->calls);
	}
	dst->n_call_nodes += src->n_call_nodes;
	dst->n_nodes      += src->n_nodes;
}

950
951
952
953
954
955
956
957
/*
 * Inlines small leave methods at call sites where the called address comes
 * from a Const node that references the entity representing the called
 * method.
 * The size argument is a rough measure for the code size of the method:
 * Methods where the obstack containing the firm graph is smaller than
 * size are inlined.
 */
958
void inline_leave_functions(unsigned maxsize, unsigned leavesize,
Michael Beck's avatar
Michael Beck committed
959
                            unsigned size, int ignore_runtime)
960
{
961
962
	inline_irg_env   *env;
	ir_graph         *irg;
Michael Beck's avatar
Michael Beck committed
963
	size_t           i, n_irgs;
964
965
966
	ir_graph         *rem;
	int              did_inline;
	wenv_t           wenv;
Michael Beck's avatar
Michael Beck committed
967
	call_entry       *entry, *next;
968
969
970
971
972
	const call_entry *centry;
	pmap             *copied_graphs;
	pmap_entry       *pm_entry;

	rem = current_ir_graph;
973
	obstack_init(&temp_obst);
974
975
976
977
978
979
980

	/* a map for the copied graphs, used to inline recursive calls */
	copied_graphs = pmap_create();

	/* extend all irgs by a temporary data structure for inlining. */
	n_irgs = get_irp_n_irgs();
	for (i = 0; i < n_irgs; ++i)
981
		set_irg_link(get_irp_irg(i), alloc_inline_irg_env());
982

Michael Beck's avatar
Michael Beck committed
983
	/* Pre-compute information in temporary data structure. */
984
985
986
987
988
989
990
991
	wenv.ignore_runtime = ignore_runtime;
	wenv.ignore_callers = 0;
	for (i = 0; i < n_irgs; ++i) {
		ir_graph *irg = get_irp_irg(i);

		assert(get_irg_phase_state(irg) != phase_building);
		free_callee_info(irg);

992
		assure_cf_loop(irg);
993
		wenv.x = (inline_irg_env*)get_irg_link(irg);
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
		irg_walk_graph(irg, NULL, collect_calls2, &wenv);
	}

	/* -- and now inline. -- */

	/* Inline leaves recursively -- we might construct new leaves. */
	do {
		did_inline = 0;

		for (i = 0; i < n_irgs; ++i) {
			ir_node *call;
			int phiproj_computed = 0;

			current_ir_graph = get_irp_irg(i);
1008
			env              = (inline_irg_env*)get_irg_link(current_ir_graph);
1009

1010
			ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
Michael Beck's avatar
Michael Beck committed
1011
			list_for_each_entry_safe(call_entry, entry, next, &env->calls, list) {
Michael Beck's avatar
Michael Beck committed
1012
				ir_graph            *callee;
1013
				irg_inline_property  prop;
1014

Michael Beck's avatar
Michael Beck committed
1015
1016
				if (env->n_nodes > maxsize)
					break;
1017
1018
1019
1020

				call   = entry->call;
				callee = entry->callee;

Michael Beck's avatar
Michael Beck committed
1021
				prop = get_irg_inline_property(callee);
1022
				if (prop == irg_inline_forbidden) {
Michael Beck's avatar
Michael Beck committed
1023
1024
1025
					continue;
				}

1026
				if (is_leave(callee) && (
Michael Beck's avatar
Michael Beck committed
1027
				    is_smaller(callee, leavesize) || prop >= irg_inline_forced)) {
1028
1029
1030
1031
1032
1033
1034
					if (!phiproj_computed) {
						phiproj_computed = 1;
						collect_phiprojs(current_ir_graph);
					}
					did_inline = inline_method(call, callee);

					if (did_inline) {
1035
						inline_irg_env *callee_env = (inline_irg_env*)get_irg_link(callee);
1036

Michael Beck's avatar
Michael Beck committed
1037
						/* call was inlined, Phi/Projs for current graph must be recomputed */
1038
1039
1040
1041
1042
1043
1044
1045
1046
						phiproj_computed = 0;

						/* Do some statistics */
						env->got_inline = 1;
						--env->n_call_nodes;
						env->n_nodes += callee_env->n_nodes;
						--callee_env->n_callers;

						/* remove this call from the list */
Michael Beck's avatar
Michael Beck committed
1047
						list_del(&entry->list);
1048
1049
1050
1051
						continue;
					}
				}
			}
1052
			ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1053
1054
1055
1056
1057
1058
1059
1060
1061
		}
	} while (did_inline);

	/* inline other small functions. */
	for (i = 0; i < n_irgs; ++i) {
		ir_node *call;
		int phiproj_computed = 0;

		current_ir_graph = get_irp_irg(i);
1062
		env              = (inline_irg_env*)get_irg_link(current_ir_graph);
1063

1064
1065
		ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);

1066
		/* note that the list of possible calls is updated during the process */
Michael Beck's avatar
Michael Beck committed
1067
		list_for_each_entry_safe(call_entry, entry, next, &env->calls, list) {
Michael Beck's avatar
Michael Beck committed
1068
1069
1070
			irg_inline_property prop;
			ir_graph            *callee;
			pmap_entry          *e;
1071
1072
1073
1074

			call   = entry->call;
			callee = entry->callee;

Michael Beck's avatar
Michael Beck committed
1075
			prop = get_irg_inline_property(callee);
1076
			if (prop == irg_inline_forbidden) {
Michael Beck's avatar
Michael Beck committed
1077
1078
1079
				continue;
			}

1080
1081
1082
1083
1084
1085
			e = pmap_find(copied_graphs, callee);
			if (e != NULL) {
				/*
				 * Remap callee if we have a copy.
				 * FIXME: Should we do this only for recursive Calls ?
				 */
1086
				callee = (ir_graph*)e->value;
1087
1088
			}

Michael Beck's avatar
Michael Beck committed
1089
1090
			if (prop >= irg_inline_forced ||
			    (is_smaller(callee, size) && env->n_nodes < maxsize) /* small function */) {
1091
1092
1093
1094
1095
1096
1097
1098
1099
				if (current_ir_graph == callee) {
					/*
					 * Recursive call: we cannot directly inline because we cannot walk
					 * the graph and change it. So we have to make a copy of the graph
					 * first.
					 */

					inline_irg_env *callee_env;
					ir_graph       *copy;
1100

1101
1102
					ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);

1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
					/*
					 * No copy yet, create one.
					 * Note that recursive methods are never leaves, so it is sufficient
					 * to test this condition here.
					 */
					copy = create_irg_copy(callee);

					/* create_irg_copy() destroys the Proj links, recompute them */
					phiproj_computed = 0;

1113
1114
					ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);

1115
					/* allocate new environment */
1116
					callee_env = alloc_inline_irg_env();
1117
1118
					set_irg_link(copy, callee_env);

1119
					assure_cf_loop(copy);
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
					wenv.x              = callee_env;
					wenv.ignore_callers = 1;
					irg_walk_graph(copy, NULL, collect_calls2, &wenv);

					/*
					 * Enter the entity of the original graph. This is needed
					 * for inline_method(). However, note that ent->irg still points
					 * to callee, NOT to copy.
					 */
					set_irg_entity(copy, get_irg_entity(callee));

					pmap_insert(copied_graphs, callee, copy);
					callee = copy;

					/* we have only one caller: the original graph */
					callee_env->n_callers      = 1;
					callee_env->n_callers_orig = 1;
				}
				if (! phiproj_computed) {
					phiproj_computed = 1;
					collect_phiprojs(current_ir_graph);
				}
				did_inline = inline_method(call, callee);
				if (did_inline) {
					inline_irg_env *callee_env = (inline_irg_env *)get_irg_link(callee);

Michael Beck's avatar
Michael Beck committed
1146
					/* call was inlined, Phi/Projs for current graph must be recomputed */
1147
1148
					phiproj_computed = 0;

1149
					/* callee was inline. Append its call list. */
1150
1151
					env->got_inline = 1;
					--env->n_call_nodes;
Michael Beck's avatar
Michael Beck committed
1152
					append_call_list(env, callee_env, entry->loop_depth);
1153
1154
1155
1156
					--callee_env->n_callers;

					/* after we have inlined callee, all called methods inside callee
					   are now called once more */
Michael Beck's avatar
Michael Beck committed
1157
					list_for_each_entry(call_entry, centry, &callee_env->calls, list) {
1158
						inline_irg_env *penv = (inline_irg_env*)get_irg_link(centry->callee);
1159
1160
1161
1162
						++penv->n_callers;
					}

					/* remove this call from the list */
Michael Beck's avatar
Michael Beck committed
1163
					list_del(&entry->list);
1164
1165
1166
1167
					continue;
				}
			}
		}
1168
		ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_LINK|IR_RESOURCE_PHI_LIST);
1169
1170
1171
1172
	}

	for (i = 0; i < n_irgs; ++i) {
		irg = get_irp_irg(i);