funccall.c 30.9 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
2
 * Copyright (C) 1995-2008 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   Optimization of function calls.
 * @author  Michael Beck
 * @version $Id$
25
 */
26
27
#include "config.h"

28
29
#include <adt/raw_bitset.h>

30
#include "funccall_t.h"
31

32
33
34
35
36
37
38
#include "irnode_t.h"
#include "irgraph_t.h"
#include "irgmod.h"
#include "irgwalk.h"
#include "irvrfy.h"
#include "dbginfo_t.h"
#include "irflag_t.h"
39
#include "irloop_t.h"
40
#include "ircons.h"
41
#include "iredges_t.h"
42
#include "irpass_t.h"
43
#include "analyze_irg_args.h"
44
#include "irhooks.h"
45
46
47
#include "debug.h"

DEBUG_ONLY(static firm_dbg_module_t *dbg;)
48
49

/**
50
 * The walker environment for updating function calls.
51
52
 */
typedef struct _env_t {
53
54
	unsigned n_calls_SymConst;
	unsigned n_calls_Sel;
55
56
57
58
59
	ir_node  *float_const_call_list;    /**< The list of all floating const function calls that will be changed. */
	ir_node  *nonfloat_const_call_list; /**< The list of all non-floating const function calls that will be changed. */
	ir_node  *pure_call_list;           /**< The list of all pure function calls that will be changed. */
	ir_node  *nothrow_call_list;        /**< The list of all nothrow function calls that will be changed. */
	ir_node  *proj_list;                /**< The list of all potential Proj nodes that must be fixed. */
60
61
} env_t;

62
63
64
/** If non-null, evaluates entities for being a heap alloc. */
static check_alloc_entity_func is_alloc_entity = NULL;

65
66
67
68
69
70
71
/** Ready IRG's are marked in the ready set. */
static unsigned *ready_set;

/** IRG's that are in progress are marked here. */
static unsigned *busy_set;

/**
72
73
74
 * We misuse the mtp_property_inherited flag as temporary here.
 * The is ok, as we cannot set or get it anyway using the
 * get_addtional_properties API.
75
76
77
 */
#define mtp_temporary  mtp_property_inherited

78
/**
79
 * Walker: Collect all calls to const and pure functions
80
 * to lists. Collect all Proj(Call) nodes into a Proj list.
81
 */
82
static void collect_const_and_pure_calls(ir_node *node, void *env) {
83
84
	env_t     *ctx = env;
	ir_node   *call, *ptr;
85
	ir_entity *ent;
86
	unsigned  and_prop, or_prop, prop;
87
88
89
90
91
92
93

	if (is_Call(node)) {
		call = node;

		/* set the link to NULL for all non-const/pure calls */
		set_irn_link(call, NULL);
		ptr = get_Call_ptr(call);
94
95
		if (is_Global(ptr)) {
			ent = get_Global_entity(ptr);
96

97
98
			prop = get_entity_additional_properties(ent);
			if ((prop & (mtp_property_const|mtp_property_pure)) == 0)
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
				return;
			++ctx->n_calls_SymConst;
		} else if (get_opt_closed_world() &&
		           is_Sel(ptr) &&
		           get_irg_callee_info_state(current_ir_graph) == irg_callee_info_consistent) {
			/* If all possible callees are const functions, we can remove the memory edge. */
			int i, n_callees = get_Call_n_callees(call);
			if (n_callees == 0) {
				/* This is kind of strange:  dying code or a Call that will raise an exception
				   when executed as there is no implementation to call.  So better not
				   optimize. */
				return;
			}

			/* note that const function are a subset of pure ones */
114
115
			and_prop = mtp_property_const | mtp_property_pure;
			or_prop  = 0;
116
117
118
119
120
121
			for (i = 0; i < n_callees; ++i) {
				ent = get_Call_callee(call, i);
				if (ent == unknown_entity) {
					/* we don't know which entity is called here */
					return;
				}
122
123
124
125
				prop      = get_entity_additional_properties(ent);
				and_prop &= prop;
				or_prop  &= prop;
				if (and_prop == mtp_no_property)
126
127
					return;
			}
128
			prop = and_prop | (or_prop & mtp_property_has_loop);
129
130
131
132
133
			++ctx->n_calls_Sel;
		} else
			return;

		/* ok, if we get here we found a call to a const or a pure function */
134
		if (prop & mtp_property_pure) {
135
136
137
			set_irn_link(call, ctx->pure_call_list);
			ctx->pure_call_list = call;
		} else {
138
139
140
141
142
143
144
			if (prop & mtp_property_has_loop) {
				set_irn_link(call, ctx->nonfloat_const_call_list);
				ctx->nonfloat_const_call_list = call;
			} else {
				set_irn_link(call, ctx->float_const_call_list);
				ctx->float_const_call_list = call;
			}
145
146
147
148
149
150
151
152
153
154
155
156
157
158
		}
	} else if (is_Proj(node)) {
		/*
		 * Collect all memory and exception Proj's from
		 * calls.
		 */
		call = get_Proj_pred(node);
		if (! is_Call(call))
			return;

		/* collect the Proj's in the Proj list */
		switch (get_Proj_proj(node)) {
		case pn_Call_M_regular:
		case pn_Call_X_except:
159
		case pn_Call_X_regular:
160
161
162
163
164
165
166
167
		case pn_Call_M_except:
			set_irn_link(node, ctx->proj_list);
			ctx->proj_list = node;
			break;
		default:
			break;
		}
	}
168
}  /* collect_const_and_pure_calls */
169
170
171

/**
 * Fix the list of collected Calls.
172
 *
173
174
 * @param irg  the graph that contained calls to pure functions
 * @param ctx  context
175
 */
176
static void fix_const_call_lists(ir_graph *irg, env_t *ctx) {
177
178
179
180
181
182
	ir_node *call, *next, *mem, *proj;
	int exc_changed = 0;
	ir_graph *rem = current_ir_graph;

	current_ir_graph = irg;

183
184
	/* First step: fix all calls by removing their memory input and let
	 * them floating.
Christoph Mallon's avatar
Christoph Mallon committed
185
	 * The original memory input is preserved in their link fields. */
186
	for (call = ctx->float_const_call_list; call != NULL; call = next) {
187
188
189
190
191
192
193
		next = get_irn_link(call);
		mem  = get_Call_mem(call);

		set_irn_link(call, mem);
		set_Call_mem(call, get_irg_no_mem(irg));

		/*
Christoph Mallon's avatar
Christoph Mallon committed
194
		 * Unfortunately we cannot simply set the node to 'float'.
195
196
197
198
199
200
201
202
203
204
205
206
207
		 * There is a reason for that:
		 *
		 * - The call might be inside a loop/if that is NOT entered
		 *   and calls a endless function. Setting the call to float
		 *   would allow to move it out from the loop/if causing this
		 *   function be called even if the loop/if is not entered ...
		 *
		 * This could be fixed using post-dominators for calls and Pin nodes
		 * but need some more analyzes to ensure that a call that potential
		 * never returns is not executed before some code that generates
		 * observable states...
		 */

208
209
		/* finally, this call can float */
		set_irn_pinned(call, op_pin_state_floats);
210
211
212
		hook_func_call(irg, call);
	}

213
214
	/* Last step: fix all Proj's */
	for (proj = ctx->proj_list; proj != NULL; proj = next) {
215
216
217
218
219
		next = get_irn_link(proj);
		call = get_Proj_pred(proj);
		mem  = get_irn_link(call);

		/* beware of calls in the pure call list */
220
		if (!mem || is_Call(mem))
221
222
223
224
225
226
227
228
			continue;
		assert(get_irn_mode(mem) == mode_M);

		switch (get_Proj_proj(proj)) {
		case pn_Call_M_regular: {
			/* in dead code there might be cycles where proj == mem */
			if (proj != mem)
				exchange(proj, mem);
229
230
			 break;
		}
231
232
233
234
235
		case pn_Call_X_except:
		case pn_Call_M_except:
			exc_changed = 1;
			exchange(proj, get_irg_bad(irg));
			break;
236
237
238
		case pn_Call_X_regular: {
			ir_node *block = get_nodes_block(call);
			exc_changed = 1;
239
			exchange(proj, new_r_Jmp(block));
240
241
			break;
		}
242
243
244
245
246
247
248
249
250
251
252
253
254
255
		default:
			;
		}
	}

	/* changes were done ... */
	set_irg_outs_inconsistent(irg);
	set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);

	if (exc_changed) {
		/* ... including exception edges */
		set_irg_doms_inconsistent(irg);
	}
	current_ir_graph = rem;
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
}  /* fix_const_call_list */

/**
 * Walker: Collect all calls to nothrow functions
 * to lists. Collect all Proj(Call) nodes into a Proj list.
 */
static void collect_nothrow_calls(ir_node *node, void *env) {
	env_t *ctx = env;
	ir_node *call, *ptr;
	ir_entity *ent;
	unsigned prop;

	if (is_Call(node)) {
		call = node;

		/* set the link to NULL for all non-const/pure calls */
		set_irn_link(call, NULL);
		ptr = get_Call_ptr(call);
274
275
		if (is_Global(ptr)) {
			ent = get_Global_entity(ptr);
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377

			prop = get_entity_additional_properties(ent);
			if ((prop & mtp_property_nothrow) == 0)
				return;
			++ctx->n_calls_SymConst;
		} else if (get_opt_closed_world() &&
		           is_Sel(ptr) &&
		           get_irg_callee_info_state(current_ir_graph) == irg_callee_info_consistent) {
			/* If all possible callees are nothrow functions, we can remove the exception edge. */
			int i, n_callees = get_Call_n_callees(call);
			if (n_callees == 0) {
				/* This is kind of strange:  dying code or a Call that will raise an exception
				   when executed as there is no implementation to call.  So better not
				   optimize. */
				return;
			}

			/* note that const function are a subset of pure ones */
			prop = mtp_property_nothrow;
			for (i = 0; i < n_callees; ++i) {
				ent = get_Call_callee(call, i);
				if (ent == unknown_entity) {
					/* we don't know which entity is called here */
					return;
				}
				prop &= get_entity_additional_properties(ent);
				if (prop == mtp_no_property)
					return;
			}
			++ctx->n_calls_Sel;
		} else
			return;

		/* ok, if we get here we found a call to a nothrow function */
		set_irn_link(call, ctx->nothrow_call_list);
		ctx->nothrow_call_list = call;
	} else if (is_Proj(node)) {
		/*
		 * Collect all memory and exception Proj's from
		 * calls.
		 */
		call = get_Proj_pred(node);
		if (! is_Call(call))
			return;

		/* collect the Proj's in the Proj list */
		switch (get_Proj_proj(node)) {
		case pn_Call_M_regular:
		case pn_Call_X_except:
		case pn_Call_X_regular:
		case pn_Call_M_except:
			set_irn_link(node, ctx->proj_list);
			ctx->proj_list = node;
			break;
		default:
			break;
		}
	}
}  /* collect_nothrow_calls */

/**
 * Fix the list of collected nothrow Calls.
 *
 * @param irg        the graph that contained calls to pure functions
 * @param call_list  the list of all call sites of const functions
 * @param proj_list  the list of all memory/exception Proj's of this call sites
 */
static void fix_nothrow_call_list(ir_graph *irg, ir_node *call_list, ir_node *proj_list) {
	ir_node *call, *next, *proj;
	int exc_changed = 0;
	ir_graph *rem = current_ir_graph;

	current_ir_graph = irg;

	/* First step: go through the list of calls and mark them. */
	for (call = call_list; call; call = next) {
		next = get_irn_link(call);

		/* current_ir_graph is in memory anyway, so it's a good marker */
		set_irn_link(call, &current_ir_graph);
		hook_func_call(irg, call);
	}

	/* Second step: Remove all exception Proj's */
	for (proj = proj_list; proj; proj = next) {
		next = get_irn_link(proj);
		call = get_Proj_pred(proj);

		/* handle only marked calls */
		if (get_irn_link(call) != &current_ir_graph)
			continue;

		/* kill any exception flow */
		switch (get_Proj_proj(proj)) {
		case pn_Call_X_except:
		case pn_Call_M_except:
			exc_changed = 1;
			exchange(proj, get_irg_bad(irg));
			break;
		case pn_Call_X_regular: {
			ir_node *block = get_nodes_block(call);
			exc_changed = 1;
378
			exchange(proj, new_r_Jmp(block));
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
			break;
		}
		default:
			;
		}
	}

	/* changes were done ... */
	set_irg_outs_inconsistent(irg);
	set_irg_loopinfo_state(irg, loopinfo_cf_inconsistent);

	if (exc_changed) {
		/* ... including exception edges */
		set_irg_doms_inconsistent(irg);
	}
	current_ir_graph = rem;
}  /* fix_nothrow_call_list */
396

397
398
399
400
401
402
/* marking */
#define SET_IRG_READY(irg)	rbitset_set(ready_set, get_irg_idx(irg))
#define IS_IRG_READY(irg)   rbitset_is_set(ready_set, get_irg_idx(irg))
#define SET_IRG_BUSY(irg)   rbitset_set(busy_set, get_irg_idx(irg))
#define CLEAR_IRG_BUSY(irg) rbitset_clear(busy_set, get_irg_idx(irg))
#define IS_IRG_BUSY(irg)    rbitset_is_set(busy_set, get_irg_idx(irg))
403
404

/* forward */
405
static unsigned check_const_or_pure_function(ir_graph *irg, int top);
406
static unsigned check_nothrow_or_malloc(ir_graph *irg, int top);
407
408

/**
409
 * Calculate the bigger property of two. Handle the temporary flag right.
410
 */
411
static unsigned max_property(unsigned a, unsigned b) {
412
413
414
	unsigned r, t = (a | b) & mtp_temporary;
	a &= ~mtp_temporary;
	b &= ~mtp_temporary;
415

416
417
418
419
	if (a == mtp_no_property || b == mtp_no_property)
		return mtp_no_property;
	r = a > b ? a : b;
	return r | t;
420
}  /* max_property */
421
422
423
424
425
426

/**
 * Follow the memory chain starting at node and determine
 * the mtp_property.
 *
 * @return mtp_property_const if only calls of const functions are detected
Michael Beck's avatar
Michael Beck committed
427
428
 *         mtp_property_pure  if only Loads and const/pure calls detected
 *         mtp_no_property    else
429
430
 */
static unsigned _follow_mem(ir_node *node) {
431
432
433
434
435
	unsigned m, mode = mtp_property_const;
	ir_node  *ptr;
	int i;

	for (;;) {
436
437
438
		if (mode == mtp_no_property)
			return mtp_no_property;

439
		if (irn_visited_else_mark(node))
440
441
442
443
444
445
446
447
448
449
450
451
452
			return mode;

		switch (get_irn_opcode(node)) {
		case iro_Proj:
			node = get_Proj_pred(node);
			break;

		case iro_NoMem:
			/* finish here */
			return mode;

		case iro_Phi:
		case iro_Sync:
453
			/* do a dfs search */
454
			for (i = get_irn_arity(node) - 1; i >= 0; --i) {
455
				m    = _follow_mem(get_irn_n(node, i));
456
				mode = max_property(mode, m);
457
458
				if (mode == mtp_no_property)
					return mtp_no_property;
459
			}
460
			return mode;
461
462

		case iro_Load:
463
			/* Beware volatile Loads are NOT allowed in pure functions. */
464
			if (get_Load_volatility(node) == volatility_is_volatile)
465
				return mtp_no_property;
466
			mode = max_property(mode, mtp_property_pure);
467
468
469
470
			node = get_Load_mem(node);
			break;

		case iro_Call:
471
			/* A call is only tolerable if its either constant or pure. */
472
			ptr = get_Call_ptr(node);
Michael Beck's avatar
Michael Beck committed
473
			if (is_SymConst_addr_ent(ptr)) {
474
475
476
477
				ir_entity *ent = get_SymConst_entity(ptr);
				ir_graph  *irg = get_entity_irg(ent);

				if (irg == current_ir_graph) {
478
					/* A self-recursive call. The property did not depend on this call. */
479
480
				} else if (irg == NULL) {
					m = get_entity_additional_properties(ent) & (mtp_property_const|mtp_property_pure);
481
					mode = max_property(mode, m);
482
				} else if (irg != NULL) {
483
484
					/* we have a graph, analyze it. */
					m = check_const_or_pure_function(irg, /*top=*/0);
485
					mode = max_property(mode, m);
486
487
				}
			} else
488
				return mtp_no_property;
489
490
491
492
			node = get_Call_mem(node);
			break;

		default:
493
			return mtp_no_property;
494
495
		}
	}
496
}  /* _follow_mem */
497

498
499
500
501
502
/**
 * Follow the memory chain starting at node and determine
 * the mtp_property.
 *
 * @return mtp_property_const if only calls of const functions are detected
Michael Beck's avatar
Michael Beck committed
503
504
 *         mtp_property_pure  if only Loads and const/pure calls detected
 *         mtp_no_property else
505
 */
Michael Beck's avatar
Michael Beck committed
506
static unsigned follow_mem(ir_node *node, unsigned mode) {
507
508
509
	unsigned m;

	m = _follow_mem(node);
510
	return max_property(mode, m);
511
}  /* follow_mem */
512

513
514
/**
 * Check if a graph represents a const or a pure function.
515
 *
516
517
 * @param irg  the graph to check
 * @param top  if set, this is the top call
518
 */
519
static unsigned check_const_or_pure_function(ir_graph *irg, int top) {
520
521
	ir_node *end, *endbl;
	int j;
522
	unsigned prop = get_irg_additional_properties(irg);
523
524
	ir_graph *rem = current_ir_graph;

525
	if (prop & mtp_property_const) {
526
527
528
		/* already marked as a const function */
		return mtp_property_const;
	}
529
	if (prop & mtp_property_pure) {
530
531
532
533
		/* already marked as a pure function */
		return mtp_property_pure;
	}

534
535
536
537
538
539
540
541
542
543
	if (IS_IRG_READY(irg)) {
		/* already checked */
		return mtp_no_property;
	}
	if (IS_IRG_BUSY(irg)) {
		/* we are still evaluate this method. Be optimistic,
		   return the best possible so far but mark the result as temporary. */
		return mtp_temporary | mtp_property_const;
	}
	SET_IRG_BUSY(irg);
544
545
546

	end   = get_irg_end(irg);
	endbl = get_nodes_block(end);
547
	prop  = mtp_property_const;
548
549
550

	current_ir_graph = irg;

Michael Beck's avatar
Michael Beck committed
551
	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
552
	inc_irg_visited(irg);
Michael Beck's avatar
Michael Beck committed
553
	/* mark the initial mem: recursion of follow_mem() stops here */
554
555
	mark_irn_visited(get_irg_initial_mem(irg));

556
557
	/* visit every Return */
	for (j = get_Block_n_cfgpreds(endbl) - 1; j >= 0; --j) {
558
559
560
		ir_node   *node = get_Block_cfgpred(endbl, j);
		ir_opcode code  = get_irn_opcode(node);
		ir_node   *mem;
561
562

		/* Bad nodes usually do NOT produce anything, so it's ok */
563
		if (code == iro_Bad)
564
565
			continue;

566
		if (code == iro_Return) {
567
568
569
570
571
572
573
			mem = get_Return_mem(node);

			/* Bad nodes usually do NOT produce anything, so it's ok */
			if (is_Bad(mem))
				continue;

			if (mem != get_irg_initial_mem(irg))
574
				prop = max_property(prop, follow_mem(mem, prop));
575
		} else {
576
			/* Exception found. Cannot be const or pure. */
577
			prop = mtp_no_property;
578
579
			break;
		}
580
		if (prop == mtp_no_property)
581
582
583
			break;
	}

584
	if (prop != mtp_no_property) {
585
586
		/* check, if a keep-alive exists */
		for (j = get_End_n_keepalives(end) - 1; j >= 0; --j) {
587
			ir_node *kept = get_End_keepalive(end, j);
588

589
590
591
592
593
594
			if (is_Block(kept)) {
				prop = mtp_no_property;
				break;
			}

			if (mode_M != get_irn_mode(kept))
595
596
				continue;

597
			prop = max_property(prop, follow_mem(kept, prop));
598
			if (prop == mtp_no_property)
599
600
601
602
				break;
		}
	}

603
604
	if (prop != mtp_no_property) {
		if (top || (prop & mtp_temporary) == 0) {
605
606
607
			/* We use the temporary flag here to mark optimistic result.
			   Set the property only if we are sure that it does NOT base on
			   temporary results OR if we are at top-level. */
608
			set_irg_additional_property(irg, prop & ~mtp_temporary);
609
610
611
612
613
614
			SET_IRG_READY(irg);
		}
	}
	if (top)
		SET_IRG_READY(irg);
	CLEAR_IRG_BUSY(irg);
Michael Beck's avatar
Michael Beck committed
615
	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
616
	current_ir_graph = rem;
617
	return prop;
618
}  /* check_const_or_pure_function */
619
620
621

/**
 * Handle calls to const functions.
622
623
 *
 * @param ctx  context
624
 */
625
626
static void handle_const_Calls(env_t *ctx) {
	int i;
627

628
629
	ctx->n_calls_SymConst = 0;
	ctx->n_calls_Sel      = 0;
630

631
632
633
	/* all calls of const functions can be transformed */
	for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
		ir_graph *irg  = get_irp_irg(i);
634

635
636
637
638
		ctx->float_const_call_list    = NULL;
		ctx->nonfloat_const_call_list = NULL;
		ctx->pure_call_list           = NULL;
		ctx->proj_list                = NULL;
Michael Beck's avatar
Michael Beck committed
639
640

		ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
641
		irg_walk_graph(irg, NULL, collect_const_and_pure_calls, ctx);
642

Michael Beck's avatar
Michael Beck committed
643
		if (ctx->float_const_call_list != NULL)
644
			fix_const_call_lists(irg, ctx);
Michael Beck's avatar
Michael Beck committed
645
		ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
646
	}
647
648
}  /* handle_const_Calls */

649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
/**
 * Handle calls to nothrow functions.
 *
 * @param ctx  context
 */
static void handle_nothrow_Calls(env_t *ctx) {
	int i;

	ctx->n_calls_SymConst = 0;
	ctx->n_calls_Sel      = 0;

	/* all calls of const functions can be transformed */
	for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
		ir_graph *irg  = get_irp_irg(i);

		ctx->nothrow_call_list = NULL;
		ctx->proj_list         = NULL;
Michael Beck's avatar
Michael Beck committed
666
667

		ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
668
669
		irg_walk_graph(irg, NULL, collect_nothrow_calls, ctx);

Michael Beck's avatar
Michael Beck committed
670
		if (ctx->nothrow_call_list)
671
			fix_nothrow_call_list(irg, ctx->nothrow_call_list, ctx->proj_list);
Michael Beck's avatar
Michael Beck committed
672
		ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
	}
}

/**
 * Check, whether a given node represents a return value of
 * a malloc like function (ie, new heap allocated memory).
 *
 * @param node  the node to check
 */
static int is_malloc_call_result(const ir_node *node) {
	if (is_Alloc(node) && get_Alloc_where(node) == heap_alloc) {
		/* Firm style high-level allocation */
		return 1;
	}
	if (is_alloc_entity != NULL && is_Call(node)) {
		ir_node *ptr = get_Call_ptr(node);

690
691
		if (is_Global(ptr)) {
			ir_entity *ent = get_Global_entity(ptr);
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
			return is_alloc_entity(ent);
		}
	}
	return 0;
}  /* is_malloc_call_result */

/**
 * Update a property depending on a call property.
 */
static unsigned update_property(unsigned orig_prop, unsigned call_prop) {
	unsigned t = (orig_prop | call_prop) & mtp_temporary;
	unsigned r = orig_prop & call_prop;
	return r | t;
}  /** update_property */

707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
/**
 * Check if a node is stored.
 */
static int is_stored(const ir_node *n) {
	const ir_edge_t *edge;
	const ir_node   *ptr;

	foreach_out_edge(n, edge) {
		const ir_node *succ = get_edge_src_irn(edge);

		switch (get_irn_opcode(succ)) {
		case iro_Return:
		case iro_Load:
		case iro_Cmp:
			/* ok */
			break;
		case iro_Store:
724
			if (get_Store_value(succ) == n)
725
				return 1;
726
727
728
729
730
731
			/* ok if its only the address input */
			break;
		case iro_Sel:
		case iro_Cast:
		case iro_Confirm:
			if (is_stored(succ))
732
				return 1;
733
734
735
			break;
		case iro_Call:
			ptr = get_Call_ptr(succ);
736
737
			if (is_Global(ptr)) {
				ir_entity *ent = get_Global_entity(ptr);
738
739
740
741
742
743
744
745
				int       i;

				/* we know the called entity */
				for (i = get_Call_n_params(succ) - 1; i >= 0; --i) {
					if (get_Call_param(succ, i) == n) {
						/* n is the i'th param of the call */
						if (get_method_param_access(ent, i) & ptr_access_store) {
							/* n is store in ent */
746
							return 1;
747
748
749
750
						}
					}
				}
			} else {
751
752
				/* unknown call address */
				return 1;
753
754
755
756
			}
			break;
		default:
			/* bad, potential alias */
757
			return 1;
758
759
		}
	}
760
	return 0;
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
}  /* is_stored */

/**
 * Check that the return value of an irg is not stored anywhere.
 *
 * return ~mtp_property_malloc if return values are stored, ~0 else
 */
static unsigned check_stored_result(ir_graph *irg) {
	ir_node  *end_blk = get_irg_end_block(irg);
	int      i, j;
	unsigned res = ~0;
	int      old_edges = edges_assure_kind(irg, EDGE_KIND_NORMAL);

	for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
		ir_node *pred = get_Block_cfgpred(end_blk, i);

		if (! is_Return(pred))
			continue;
		for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
780
			const ir_node *irn = get_Return_res(pred, j);
781

782
			if (is_stored(irn)) {
783
784
785
786
787
788
789
790
791
792
793
794
				/* bad, might create an alias */
				res = ~mtp_property_malloc;
				goto finish;
			}
		}
	}
finish:
	if (! old_edges)
		edges_deactivate_kind(irg, EDGE_KIND_NORMAL);
	return res;
}  /* check_stored_result */

795
796
797
798
799
800
801
/**
 * Check if a graph represents a nothrow or a malloc function.
 *
 * @param irg  the graph to check
 * @param top  if set, this is the top call
 */
static unsigned check_nothrow_or_malloc(ir_graph *irg, int top) {
802
803
804
805
806
	ir_node   *end_blk = get_irg_end_block(irg);
	ir_entity *ent;
	ir_type   *mtp;
	int       i, j;
	unsigned  curr_prop = mtp_property_malloc | mtp_property_nothrow;
807
808
809
810
811
812
813
814
815
816
817
818

	if (IS_IRG_READY(irg)) {
		/* already checked */
		return get_irg_additional_properties(irg);
	}
	if (IS_IRG_BUSY(irg)) {
		/* we are still evaluate this method. Be optimistic,
		return the best possible so far but mark the result as temporary. */
		return mtp_temporary | mtp_property_malloc | mtp_property_nothrow;
	}
	SET_IRG_BUSY(irg);

819
820
821
822
823
824
	ent = get_irg_entity(irg);
	mtp = get_entity_type(ent);

	if (get_method_n_ress(mtp) <= 0)
		curr_prop &= ~mtp_property_malloc;

825
826
827
828
829
830
831
	for (i = get_Block_n_cfgpreds(end_blk) - 1; i >= 0; --i) {
		ir_node *pred = get_Block_cfgpred(end_blk, i);

		if (is_Return(pred)) {
			if (curr_prop & mtp_property_malloc) {
				/* check, if malloc is called here */
				for (j = get_Return_n_ress(pred) - 1; j >= 0; --j) {
832
833
834
835
836
837
838
					ir_node *res = get_Return_res(pred, j);

					/* skip Confirms and Casts */
					res = skip_HighLevel_ops(res);
					/* skip Proj's */
					while (is_Proj(res))
						res = get_Proj_pred(res);
839
840
841
842
843
					if (is_malloc_call_result(res)) {
						/* ok, this is a malloc */
					} else if (is_Call(res)) {
						ir_node *ptr = get_Call_ptr(res);

844
						if (is_Global(ptr)) {
845
							/* a direct call */
846
							ir_entity *ent    = get_Global_entity(ptr);
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
							ir_graph  *callee = get_entity_irg(ent);

							if (callee == irg) {
								/* A self-recursive call. The property did not depend on this call. */
							} else if (callee != NULL) {
								unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0);
								curr_prop = update_property(curr_prop, prop);
							} else {
								curr_prop = update_property(curr_prop, get_entity_additional_properties(ent));
							}
						} else if (get_opt_closed_world() &&
						           is_Sel(ptr) &&
						           get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
							/* check if all possible callees are malloc functions. */
							int i, n_callees = get_Call_n_callees(res);
							if (n_callees == 0) {
								/* This is kind of strange:  dying code or a Call that will raise an exception
								   when executed as there is no implementation to call.  So better not
								   optimize. */
								curr_prop &= ~mtp_property_malloc;
								continue;
							}

							for (i = 0; i < n_callees; ++i) {
								ir_entity *ent = get_Call_callee(res, i);
								if (ent == unknown_entity) {
									/* we don't know which entity is called here */
									curr_prop &= ~mtp_property_malloc;
									break;
								}
								if ((get_entity_additional_properties(ent) & mtp_property_malloc) == 0) {
									curr_prop &= ~mtp_property_malloc;
									break;
								}
							}
							/* if we pass the for cycle, malloc is still ok */
						} else {
							/* unknown call */
							curr_prop &= ~mtp_property_malloc;
						}
887
888
889
					} else {
						/* unknown return value */
						curr_prop &= ~mtp_property_malloc;
890
891
892
893
894
895
896
897
898
899
					}
				}
			}
		} else if (curr_prop & mtp_property_nothrow) {
			/* exception flow detected */
			pred = skip_Proj(pred);

			if (is_Call(pred)) {
				ir_node *ptr = get_Call_ptr(pred);

900
				if (is_Global(ptr)) {
901
					/* a direct call */
902
					ir_entity *ent    = get_Global_entity(ptr);
903
904
905
906
907
					ir_graph  *callee = get_entity_irg(ent);

					if (callee == irg) {
						/* A self-recursive call. The property did not depend on this call. */
					} else if (callee != NULL) {
908
909
						/* Note: we check here for nothrow only, so do NOT reset the malloc property */
						unsigned prop = check_nothrow_or_malloc(callee, /*top=*/0) | mtp_property_malloc;
910
911
						curr_prop = update_property(curr_prop, prop);
					} else {
912
913
						if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0)
							curr_prop &= ~mtp_property_nothrow;
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
					}
				} else if (get_opt_closed_world() &&
				           is_Sel(ptr) &&
				           get_irg_callee_info_state(irg) == irg_callee_info_consistent) {
					/* check if all possible callees are nothrow functions. */
					int i, n_callees = get_Call_n_callees(pred);
					if (n_callees == 0) {
						/* This is kind of strange:  dying code or a Call that will raise an exception
						   when executed as there is no implementation to call.  So better not
						   optimize. */
						curr_prop &= ~mtp_property_nothrow;
						continue;
					}

					for (i = 0; i < n_callees; ++i) {
						ir_entity *ent = get_Call_callee(pred, i);
						if (ent == unknown_entity) {
							/* we don't know which entity is called here */
							curr_prop &= ~mtp_property_nothrow;
							break;
						}
						if ((get_entity_additional_properties(ent) & mtp_property_nothrow) == 0) {
							curr_prop &= ~mtp_property_nothrow;
							break;
						}
					}
					/* if we pass the for cycle, nothrow is still ok */
				} else {
					/* unknown call */
					curr_prop &= ~mtp_property_nothrow;
				}
			} else {
				/* real exception flow possible. */
				curr_prop &= ~mtp_property_nothrow;
			}
		}
		if ((curr_prop & ~mtp_temporary) == mtp_no_property) {
			/* no need to search further */
			break;
		}
	}
955
956
957
958
959
960
961
962
963
964
965

	if (curr_prop & mtp_property_malloc) {
		/*
		 * Note that the malloc property means not only return newly allocated
		 * memory, but also that this memory is ALIAS FREE.
		 * To ensure that, we do NOT allow that the returned memory is somewhere
		 * stored.
	     */
		curr_prop &= check_stored_result(irg);
	}

966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
	if (curr_prop != mtp_no_property) {
		if (top || (curr_prop & mtp_temporary) == 0) {
			/* We use the temporary flag here to mark an optimistic result.
			   Set the property only if we are sure that it does NOT base on
			   temporary results OR if we are at top-level. */
			set_irg_additional_property(irg, curr_prop & ~mtp_temporary);
			SET_IRG_READY(irg);
		}
	}
	if (top)
		SET_IRG_READY(irg);
	CLEAR_IRG_BUSY(irg);
	return curr_prop;
}  /* check_nothrow_or_malloc */

981
982
/**
 * When a function was detected as "const", it might be moved out of loops.
Michael Beck's avatar
Michael Beck committed
983
 * This might be dangerous if the graph can contain endless loops.
984
985
986
987
988
989
990
991
992
993
 */
static void check_for_possible_endless_loops(ir_graph *irg) {
	ir_loop *root_loop;
	assure_cf_loop(irg);

	root_loop = get_irg_loop(irg);
	if (root_loop->flags & loop_outer_loop)
		set_irg_additional_property(irg, mtp_property_has_loop);
}

994
995
996
/*
 * optimize function calls by handling const functions
 */
997
void optimize_funccalls(int force_run, check_alloc_entity_func callback)
998
{
999
1000
1001
1002
1003
	int i, last_idx;
	unsigned num_const   = 0;
	unsigned num_pure    = 0;
	unsigned num_nothrow = 0;
	unsigned num_malloc  = 0;
1004

1005
1006
	is_alloc_entity = callback;

1007
	/* prepare: mark all graphs as not analyzed */
Michael Beck's avatar
Michael Beck committed
1008
	last_idx  = get_irp_last_idx();
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
	ready_set = rbitset_malloc(last_idx);
	busy_set  = rbitset_malloc(last_idx);

	/* first step: detect, which functions are nothrow or malloc */
	DB((dbg, LEVEL_2, "Detecting nothrow and malloc properties ...\n"));
	for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
		ir_graph *irg = get_irp_irg(i);
		unsigned prop = check_nothrow_or_malloc(irg, /*top=*/1);

		if (prop & mtp_property_nothrow) {
			++num_nothrow;
			DB((dbg, LEVEL_2, "%+F has the nothrow property\n", irg));
		} else if (prop & mtp_property_malloc) {
			++num_malloc;
			DB((dbg, LEVEL_2, "%+F has the malloc property\n", irg));
		}
	}

	/* second step: remove exception edges: this must be done before the
	   detection of const and pure functions take place. */
	if (force_run || num_nothrow > 0) {
		env_t ctx;
1031

1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
		handle_nothrow_Calls(&ctx);
		DB((dbg, LEVEL_1, "Detected %u nothrow graphs, %u malloc graphs.\n", num_nothrow, num_malloc));
		DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to nothrow functions.\n",
			ctx.n_calls_SymConst, ctx.n_calls_Sel));
	} else {
		DB((dbg, LEVEL_1, "No graphs without side effects detected\n"));
	}

	rbitset_clear_all(ready_set, last_idx);
	rbitset_clear_all(busy_set, last_idx);

	/* third step: detect, which functions are const or pure */
	DB((dbg, LEVEL_2, "Detecting const and pure properties ...\n"));
1045
	for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
1046
		ir_graph *irg = get_irp_irg(i);
1047
		unsigned prop = check_const_or_pure_function(irg, /*top=*/1);
1048

1049
		if (prop & mtp_property_const) {
1050
			++num_const;
1051
			DB((dbg, LEVEL_2, "%+F has the const property\n", irg));
1052
			check_for_possible_endless_loops(irg);
1053
		} else if (prop & mtp_property_pure) {
1054
			++num_pure;
1055
			DB((dbg, LEVEL_2, "%+F has the pure property\n", irg));
1056
1057
1058
1059
1060
1061
1062
		}
	}

	if (force_run || num_const > 0) {
		env_t ctx;

		handle_const_Calls(&ctx);
1063
1064
1065
		DB((dbg, LEVEL_1, "Detected %u const graphs, %u pure graphs.\n", num_const, num_pure));
		DB((dbg, LEVEL_1, "Optimizes %u(SymConst) + %u(Sel) calls to const functions.\n",
		       ctx.n_calls_SymConst, ctx.n_calls_Sel));
1066
	} else {
1067
		DB((dbg, LEVEL_1, "No graphs without side effects detected\n"));
1068
	}
1069
1070
	xfree(busy_set);
	xfree(ready_set);
1071
}  /* optimize_funccalls */
1072
1073

/* initialize the funccall optimization */
1074
void firm_init_funccalls(void) {
1075
1076
	FIRM_DBG_REGISTER(dbg, "firm.opt.funccalls");
}  /* firm_init_funccalls */
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086

struct pass_t {
	ir_prog_pass_t          pass;
	int                     force_run;
	check_alloc_entity_func callback;
};

/**
 * Wrapper for running optimize_funccalls() as an ir_prog pass.
 */
1087
static int pass_wrapper(ir_prog *irp, void *context) {
1088
	struct pass_t *pass = context;
1089
1090

	(void)irp;
1091
1092
1093
1094
1095
1096
	optimize_funccalls(pass->force_run, pass->callback);
	return 0;
}  /* pass_wrapper */

/* Creates an ir_prog pass for optimize_funccalls. */
ir_prog_pass_t *optimize_funccalls_pass(
1097
	const char *name,
1098
1099
	int force_run, check_alloc_entity_func callback)
{
Michael Beck's avatar
Michael Beck committed
1100
	struct pass_t *pass = XMALLOCZ(struct pass_t);
1101
1102
1103
1104

	pass->force_run = force_run;
	pass->callback  = callback;

Michael Beck's avatar
Michael Beck committed
1105
1106
	return def_prog_pass_constructor(
		&pass->pass, name ? name : "funccall", pass_wrapper);
1107
}  /* optimize_funccalls_pass */