cgana.c 22.3 KB
Newer Older
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1
/*
2
 * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
Matthias Braun's avatar
Matthias Braun committed
3
4
 *
 * This file is part of libFirm.
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
5
 *
Matthias Braun's avatar
Matthias Braun committed
6
7
8
9
 * 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.
10
 *
Matthias Braun's avatar
Matthias Braun committed
11
12
13
14
15
16
17
 * 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.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
18
 */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
19

Matthias Braun's avatar
Matthias Braun committed
20
21
22
23
24
/**
 * @file
 * @brief      Intraprozedural analyses to estimate the call graph.
 * @author     Hubert Schmid
 * @date       09.06.2002
yb9976's avatar
yb9976 committed
25
 * @brief
Matthias Braun's avatar
Matthias Braun committed
26
27
28
29
30
31
32
 *  Interprocedural analysis to estimate the calling relation.
 *
 *  This analysis computes all entities representing methods that
 *  can be called at a Call node.  Further it computes a set of
 *  methods that are 'free', i.e., their adress is handled by
 *  the program directly, or they are visible external.
 */
Matthias Braun's avatar
Matthias Braun committed
33
#include "config.h"
Michael Beck's avatar
Michael Beck committed
34

Matthias Braun's avatar
Matthias Braun committed
35
#include <string.h>
36
37
38

#include "cgana.h"

Michael Beck's avatar
Michael Beck committed
39
#include "xmalloc.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
40
41
42
#include "irnode_t.h"
#include "irmode_t.h"
#include "irprog_t.h"
43
44
45
#include "irgwalk.h"
#include "ircons.h"
#include "irgmod.h"
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
46
#include "iropt.h"
47
#include "irtools.h"
48

Götz Lindenmaier's avatar
Götz Lindenmaier committed
49
#include "irflag_t.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
50
#include "dbginfo_t.h"
Michael Beck's avatar
Michael Beck committed
51
#include "iropt_dbg.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
52

Götz Lindenmaier's avatar
Götz Lindenmaier committed
53
54
#include "pmap.h"
#include "array.h"
55
#include "error.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
56

57
58
#include "irdump.h"

Michael Beck's avatar
Michael Beck committed
59
/* unambiguous address used as a mark. */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
60
static void *MARK = &MARK;
61

Matthias Braun's avatar
Matthias Braun committed
62
static pset *entities = NULL;
63

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
64
65
66
/*--------------------------------------------------------------------------*/
/* The analysis                                                             */
/*--------------------------------------------------------------------------*/
67
68


Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
69
70
71
72
/*--------------------------------------------------------------------------*/
/* Initialize datastructures, remove unwanted constructs, optimize          */
/* call target computations.                                                */
/*--------------------------------------------------------------------------*/
73

74
/** Collect the entity representing the implementation of this
75
 *  method (not the same if inherited) and all entities for overwriting
76
 *  implementations in parameter set.
77
78
79
 *  A recursive descend in the overwritten relation.
 *  Cycle-free, therefore must terminate.
 *
80
 * @param method   the overwritten method
81
 * @param set      A set of entities.
82
83
 *
 * @return Number of entities in set.
84
 */
Matthias Braun's avatar
Matthias Braun committed
85
static size_t collect_impls(ir_entity *method, pset *set)
Matthias Braun's avatar
Matthias Braun committed
86
{
87
88
	size_t i;
	size_t size = 0;
Michael Beck's avatar
Michael Beck committed
89

Matthias Braun's avatar
Matthias Braun committed
90
	if (get_entity_irg(method) != NULL) {
91
		/* has an implementation */
Matthias Braun's avatar
Matthias Braun committed
92
		pset_insert_ptr(set, method);
93
		++size;
Michael Beck's avatar
Michael Beck committed
94
95
96
	}

	/*- recursive descent -*/
97
98
99
	for (i = get_entity_n_overwrittenby(method); i > 0;)
		size += collect_impls(get_entity_overwrittenby(method, --i), set);
	return size;
100
101
}

102
103
104
105
/**
 * Determine all methods that overwrite the given method (and implement it).
 * The returned array must be freed by the caller (see DEL_ARR_F).
 * If the set of overwriting methods is empty, returns NULL.
106
 *
107
 * @param method  the method
108
 */
109
static ir_entity **get_impl_methods(ir_entity *method)
Matthias Braun's avatar
Matthias Braun committed
110
{
111
	ir_entity **arr;
Matthias Braun's avatar
Matthias Braun committed
112
	pset      *set = pset_new_ptr_default();
113
	size_t    size;
Michael Beck's avatar
Michael Beck committed
114
115

	/* Collect all method entities that can be called here */
116
	size = collect_impls(method, set);
Michael Beck's avatar
Michael Beck committed
117

118
119
	if (size == 0) {
		/* no overwriting methods found */
Michael Beck's avatar
Michael Beck committed
120
121
122
123
		arr = NULL;
	} else {
		ir_entity * ent;
		arr = NEW_ARR_F(ir_entity *, size);
Matthias Braun's avatar
Matthias Braun committed
124
		foreach_pset(set, ir_entity*, ent) {
125
			arr[--size] = ent;
Matthias Braun's avatar
Matthias Braun committed
126
		}
Michael Beck's avatar
Michael Beck committed
127
	}
Matthias Braun's avatar
Matthias Braun committed
128
	del_pset(set);
Michael Beck's avatar
Michael Beck committed
129
	return arr;
130
131
}

Michael Beck's avatar
Michael Beck committed
132
/** Analyze address computations.
133
 *
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
134
 *  Compute for all Sel nodes the set of methods that can be selected.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
135
 *  For each entity we store the set of subentities in the link field.
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
136
137
138
139
 *
 *  Further do some optimizations:
 *  - Call standard optimizations for Sel nodes: this removes polymorphic
 *    calls.
140
 *  - If the node is a SymConst(name) replace it by SymConst(ent) if possible.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
141
142
 *    For this we precomputed a map name->entity.  Nowadays, we no more support
 *    this and assert.
143
 *  - If the node is a Sel:
Götz Lindenmaier's avatar
Götz Lindenmaier committed
144
145
146
147
 *    If we found only a single method that can be called, replace the Sel
 *    by a SymConst.  This is more powerful than the analysis in opt_polymorphy,
 *    as here we walk the type graph.  In opt_polymorphy we only apply a local
 *    pattern.
148
 *
Michael Beck's avatar
Michael Beck committed
149
150
 *  @param node  The node to analyze
 *  @param env   A map that maps names of entities to the entities.
151
 */
Matthias Braun's avatar
Matthias Braun committed
152
153
static void sel_methods_walker(ir_node *node, void *env)
{
Michael Beck's avatar
Michael Beck committed
154
	ir_entity **arr;
155
	(void)env;
Michael Beck's avatar
Michael Beck committed
156
157
158
159

	/* Call standard optimizations */
	if (is_Sel(node)) {
		ir_node *new_node = optimize_in_place(node);
160
		if (node != new_node) {
Michael Beck's avatar
Michael Beck committed
161
			exchange(node, new_node);
162
163
			node = new_node;
		}
Michael Beck's avatar
Michael Beck committed
164
165
	}

166
	if (is_Sel(node) && is_Method_type(get_entity_type(get_Sel_entity(node)))) {
167
168
		ir_entity *ent = get_SymConst_entity(get_atomic_ent_value(get_Sel_entity(node)));

Matthias Braun's avatar
Matthias Braun committed
169
		if (!pset_find_ptr(entities, ent)) {
170
171
172
173
			/* Entity not yet handled. Find all (internal or external)
			 * implemented methods that overwrites this entity.
			 * This set is stored in the entity link. */
			set_entity_link(ent, get_impl_methods(ent));
Matthias Braun's avatar
Matthias Braun committed
174
			pset_insert_ptr(entities, ent);
175
		}
Michael Beck's avatar
Michael Beck committed
176

177
178
		/* -- As an add on we get an optimization that removes polymorphic calls.
		This optimization is more powerful than that in transform_node_Sel().  -- */
179
		arr = (ir_entity**) get_entity_link(ent);
180
181
182
183
184
185
		if (arr == NULL) {
			/*
			 * The Sel node never returns a pointer to a usable method.
			 * We could not call it, but it may be description:
			 * We call a method in a dead part of the program.
			 */
Matthias Braun's avatar
Matthias Braun committed
186
			assert(get_entity_irg(ent) == NULL);
187
		}
Matthias Braun's avatar
Matthias Braun committed
188
#if 0
189
190
191
192
193
194
195
196
197
		else if (get_opt_closed_world() && get_opt_dyn_meth_dispatch() &&
			(ARR_LEN(arr) == 1 && arr[0] != NULL)) {
			ir_node *new_node;

			/*
			 * The Sel node returns only one possible method.
			 * So we could replace the Sel node by a SymConst.
			 * This method must exists.
			 */
Matthias Braun's avatar
Matthias Braun committed
198
			assert(get_entity_irg(arr[0]) != NULL);
199
			new_node = copy_const_value(get_irn_dbg_info(node), get_atomic_ent_value(arr[0]), get_nodes_block(node));
200
201
202
			DBG_OPT_POLY(node, new_node);
			exchange(node, new_node);
		}
Matthias Braun's avatar
Matthias Braun committed
203
#endif
Michael Beck's avatar
Michael Beck committed
204
	}
205
206
}

Michael Beck's avatar
Michael Beck committed
207
208
/**
 * Initialize auxiliary data structures.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
209
 *
Michael Beck's avatar
Michael Beck committed
210
211
 * Computes a set of entities that overwrite an entity and contain
 * an implementation. The set is stored in the entity's link field.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
212
 *
Michael Beck's avatar
Michael Beck committed
213
214
215
216
217
 * Further replaces Sel nodes where this set contains exactly one
 * method by SymConst nodes.
 * Finally asserts if there is a SymConst(name) if there could be a
 * SymConst(ent).
 */
Matthias Braun's avatar
Matthias Braun committed
218
219
static void sel_methods_init(void)
{
Michael Beck's avatar
Michael Beck committed
220
	size_t i, n;
Michael Beck's avatar
Michael Beck committed
221
222
	pmap *ldname_map = pmap_create();   /* Map entity names to entities: to replace
	                                       SymConst(name) by SymConst(ent). */
Michael Beck's avatar
Michael Beck committed
223
	assert(entities == NULL);
Matthias Braun's avatar
Matthias Braun committed
224
	entities = pset_new_ptr_default();
Michael Beck's avatar
Michael Beck committed
225
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
226
227
		ir_entity * ent = get_irg_entity(get_irp_irg(i));
		/* only external visible methods are allowed to call by a SymConst_ptr_name */
Matthias Braun's avatar
Matthias Braun committed
228
		if (entity_is_externally_visible(ent)) {
Michael Beck's avatar
Michael Beck committed
229
			pmap_insert(ldname_map, (void *)get_entity_ld_ident(ent), ent);
Michael Beck's avatar
Michael Beck committed
230
231
232
		}
	}

233
	all_irg_walk(sel_methods_walker, NULL, NULL);
Michael Beck's avatar
Michael Beck committed
234
	pmap_destroy(ldname_map);
235
236
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
237
238
239
240
241
242
/*--------------------------------------------------------------------------*/
/* Find free methods.
 *
 * We expect that each entity has an array with all implementations in its
 * link field.                                                              */
/*--------------------------------------------------------------------------*/
243

244
245
246
/**
 * Returns an array of all methods that could be called at a Sel node.
 * This array contains every entry only once.
247
248
 *
 * @param sel  the Sel node
249
 */
Matthias Braun's avatar
Matthias Braun committed
250
251
static ir_entity ** get_Sel_arr(ir_node * sel)
{
Michael Beck's avatar
Michael Beck committed
252
253
254
255
256
257
258
259
	static ir_entity ** NULL_ARRAY = NULL;
	ir_entity * ent;
	ir_entity ** arr;

	assert(is_Sel(sel));
	ent = get_Sel_entity(sel);

	assert(is_Method_type(get_entity_type(ent))); /* what else? */
260
	arr = (ir_entity**) get_entity_link(ent);
Michael Beck's avatar
Michael Beck committed
261
262
263
264
	if (arr) {
		return arr;
	} else {
		/* "NULL" zeigt an, dass keine Implementierung existiert. Dies
yb9976's avatar
yb9976 committed
265
		 * kann f�r polymorphe (abstrakte) Methoden passieren. */
Michael Beck's avatar
Michael Beck committed
266
267
268
269
270
		if (!NULL_ARRAY) {
			NULL_ARRAY = NEW_ARR_F(ir_entity *, 0);
		}
		return NULL_ARRAY;
	}
271
272
}

273
274
/**
 * Returns the number of possible called methods at a Sel node.
275
276
 *
 * @param sel  the Sel node
277
 */
278
static size_t get_Sel_n_methods(ir_node * sel)
Matthias Braun's avatar
Matthias Braun committed
279
{
Michael Beck's avatar
Michael Beck committed
280
	return ARR_LEN(get_Sel_arr(sel));
281
282
}

283
284
285
/**
 * Returns the ith possible called method entity at a Sel node.
 */
286
static ir_entity * get_Sel_method(ir_node * sel, size_t pos)
Matthias Braun's avatar
Matthias Braun committed
287
{
Michael Beck's avatar
Michael Beck committed
288
	ir_entity ** arr = get_Sel_arr(sel);
289
	assert(pos < ARR_LEN(arr));
Michael Beck's avatar
Michael Beck committed
290
	return arr[pos];
291
292
}

Michael Beck's avatar
Michael Beck committed
293
/* forward */
Matthias Braun's avatar
Matthias Braun committed
294
static void free_mark(ir_node *node, pset *set);
295

Matthias Braun's avatar
Matthias Braun committed
296
static void free_mark_proj(ir_node *node, long n, pset *set)
Matthias Braun's avatar
Matthias Braun committed
297
{
Michael Beck's avatar
Michael Beck committed
298
299
300
301
302
303
304
305
306
307
308
309
	assert(get_irn_mode(node) == mode_T);
	if (get_irn_link(node) == MARK) {
		/* already visited */
		return;
	}
	set_irn_link(node, MARK);
	switch (get_irn_opcode(node)) {
	case iro_Proj: {
		/* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
		 * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
		 * wird. */
		ir_node * pred = get_Proj_pred(node);
310
		if (get_irn_link(pred) != MARK && is_Tuple(pred)) {
Michael Beck's avatar
Michael Beck committed
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
			free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
		} else {
			/* nothing: da in "free_ana_walker" behandelt. */
		}
		break;
	}

	case iro_Tuple:
		free_mark(get_Tuple_pred(node, n), set);
		break;

	case iro_Id:
		free_mark_proj(get_Id_pred(node), n, set);
		break;

	case iro_Start:
	case iro_Alloc:
	case iro_Load:
		/* nothing: Die Operationen werden in free_ana_walker() selbst
		 * behandelt. */
		break;

	default:
		assert(0 && "unexpected opcode or opcode not implemented");
		break;
	}
337
	// set_irn_link(node, NULL);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
338
339
}

340
/**
Michael Beck's avatar
Michael Beck committed
341
342
343
344
345
346
347
 * Called for predecessors nodes of "interesting" ones.
 * Interesting ones include all nodes that can somehow make
 * a method visible.
 *
 * If a method (or a set of methods in case of polymorph calls) gets visible,
 * add it to the set of 'free' methods
 *
348
349
350
 * @param node  the current visited node
 * @param set   the set of all free methods
 */
Matthias Braun's avatar
Matthias Braun committed
351
static void free_mark(ir_node *node, pset *set)
Matthias Braun's avatar
Matthias Braun committed
352
{
Michael Beck's avatar
Michael Beck committed
353
354
355
356
357
358
359
	if (get_irn_link(node) == MARK)
		return; /* already visited */

	set_irn_link(node, MARK);

	switch (get_irn_opcode(node)) {
	case iro_Sel: {
Michael Beck's avatar
Michael Beck committed
360
361
		ir_entity *ent = get_Sel_entity(node);
		if (is_method_entity(ent)) {
362
			size_t i, n;
363
			for (i = 0, n = get_Sel_n_methods(node); i < n; ++i) {
Matthias Braun's avatar
Matthias Braun committed
364
				pset_insert_ptr(set, get_Sel_method(node, i));
Michael Beck's avatar
Michael Beck committed
365
366
367
			}
		}
		break;
Michael Beck's avatar
Michael Beck committed
368
	}
Michael Beck's avatar
Michael Beck committed
369
370
	case iro_SymConst:
		if (get_SymConst_kind(node) == symconst_addr_ent) {
Michael Beck's avatar
Michael Beck committed
371
372
			ir_entity *ent = get_SymConst_entity(node);
			if (is_method_entity(ent)) {
Matthias Braun's avatar
Matthias Braun committed
373
				pset_insert_ptr(set, ent);
Michael Beck's avatar
Michael Beck committed
374
375
376
377
378
			}
		}
		break;

	case iro_Phi:
379
380
381
	{
		int i, n;
		for (i = 0, n = get_Phi_n_preds(node); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
382
383
384
			free_mark(get_Phi_pred(node, i), set);
		}
		break;
385
	}
Michael Beck's avatar
Michael Beck committed
386
387
388
389
	case iro_Proj:
		free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
		break;
	default:
Michael Beck's avatar
Michael Beck committed
390
		/* nothing: */
Michael Beck's avatar
Michael Beck committed
391
392
		break;
	}
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
393
}
394

395
/**
Michael Beck's avatar
Michael Beck committed
396
 * post-walker. Find method addresses.
397
 */
Matthias Braun's avatar
Matthias Braun committed
398
399
static void free_ana_walker(ir_node *node, void *env)
{
Matthias Braun's avatar
Matthias Braun committed
400
	pset *set = (pset*) env;
Michael Beck's avatar
Michael Beck committed
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417

	if (get_irn_link(node) == MARK) {
		/* already visited */
		return;
	}
	switch (get_irn_opcode(node)) {
		/* special nodes */
	case iro_Sel:
	case iro_SymConst:
	case iro_Const:
	case iro_Phi:
	case iro_Id:
	case iro_Proj:
	case iro_Tuple:
		/* nothing */
		break;
	case iro_Call:
Michael Beck's avatar
Michael Beck committed
418
419
	{
		size_t i, n;
Michael Beck's avatar
Michael Beck committed
420
421
		/* we must handle Call nodes specially, because their call address input
		   do not expose a method address. */
Michael Beck's avatar
Michael Beck committed
422
		set_irn_link(node, MARK);
Michael Beck's avatar
Michael Beck committed
423
		for (i = 0, n = get_Call_n_params(node); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
424
425
426
427
428
429
			ir_node *pred = get_Call_param(node, i);
			if (mode_is_reference(get_irn_mode(pred))) {
				free_mark(pred, set);
			}
		}
		break;
Michael Beck's avatar
Michael Beck committed
430
	}
431
432
	default: {
		int i;
yb9976's avatar
yb9976 committed
433
		/* other nodes: Alle anderen Knoten nehmen wir als Verr�ter an, bis
Michael Beck's avatar
Michael Beck committed
434
435
436
		 * jemand das Gegenteil implementiert. */
		set_irn_link(node, MARK);
		for (i = get_irn_arity(node) - 1; i >= 0; --i) {
Michael Beck's avatar
Michael Beck committed
437
			ir_node *pred = get_irn_n(node, i);
Michael Beck's avatar
Michael Beck committed
438
439
440
441
442
443
			if (mode_is_reference(get_irn_mode(pred))) {
				free_mark(pred, set);
			}
		}
		break;
	}
444
	}
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
445
446
}

447
448
449
450
/**
 * Add all method addresses in global new style initializers to the set.
 *
 * @note
451
 * We do NOT check the type here, just if it's an entity address.
452
453
454
455
456
457
 * The reason for this is code like:
 *
 * void *p = function;
 *
 * which is sometimes used to anchor functions.
 */
458
static void add_method_address_inititializer(ir_initializer_t *initializer,
Matthias Braun's avatar
Matthias Braun committed
459
                                             pset *set)
460
{
461
462
463
	ir_node *n;
	size_t  i;

464
	switch (initializer->kind) {
465
466
	case IR_INITIALIZER_CONST:
		n = initializer->consti.value;
467
468

		/* let's check if it's the address of a function */
469
470
		if (is_SymConst_addr_ent(n)) {
			ir_entity *ent = get_SymConst_entity(n);
471
472

			if (is_Method_type(get_entity_type(ent)))
Matthias Braun's avatar
Matthias Braun committed
473
				pset_insert_ptr(set, ent);
474
475
476
477
478
		}
		return;
	case IR_INITIALIZER_TARVAL:
	case IR_INITIALIZER_NULL:
		return;
479
	case IR_INITIALIZER_COMPOUND:
480
		for (i = 0; i < initializer->compound.n_initializers; ++i) {
481
482
			ir_initializer_t *sub_initializer
				= initializer->compound.initializers[i];
483
			add_method_address_inititializer(sub_initializer, set);
484
485
486
487
488
489
		}
		return;
	}
	panic("invalid initializer found");
}

490
491
/**
 * Add all method addresses in global initializers to the set.
492
493
 *
 * @note
494
 * We do NOT check the type here, just if it's an entity address.
495
496
497
498
499
 * The reason for this is code like:
 *
 * void *p = function;
 *
 * which is sometimes used to anchor functions.
500
 */
Matthias Braun's avatar
Matthias Braun committed
501
static void add_method_address(ir_entity *ent, pset *set)
502
{
Michael Beck's avatar
Michael Beck committed
503
504
	ir_type *tp;

505
	/* ignore methods: these of course reference their addresses
Michael Beck's avatar
Michael Beck committed
506
	 * TODO: remove this later once this incorrect self-initialisation is gone
Matthias Braun's avatar
Matthias Braun committed
507
508
509
	 */
	tp = get_entity_type(ent);
	if (is_Method_type(tp))
Michael Beck's avatar
Michael Beck committed
510
511
		return;

Matthias Braun's avatar
Matthias Braun committed
512
	if (ent->initializer != NULL) {
513
		add_method_address_inititializer(get_entity_initializer(ent), set);
Matthias Braun's avatar
Matthias Braun committed
514
	} else if (entity_has_compound_ent_values(ent)) {
Michael Beck's avatar
Michael Beck committed
515
516
517
		size_t i, n;
		for (i = 0, n = get_compound_ent_n_values(ent); i < n; ++i) {
			ir_node *irn = get_compound_ent_value(ent, i);
Michael Beck's avatar
Michael Beck committed
518
519

			/* let's check if it's the address of a function */
520
521
			if (is_SymConst_addr_ent(irn)) {
				ir_entity *ent2 = get_SymConst_entity(irn);
Michael Beck's avatar
Michael Beck committed
522

523
				if (is_Method_type(get_entity_type(ent2)))
Matthias Braun's avatar
Matthias Braun committed
524
					pset_insert_ptr(set, ent2);
Michael Beck's avatar
Michael Beck committed
525
526
527
			}
		}
	}
528
529
}

Michael Beck's avatar
Michael Beck committed
530
531
532
533
/**
 * returns a list of 'free' methods, i.e., the methods that can be called
 * from external or via function pointers.
 *
Matthias Braun's avatar
Matthias Braun committed
534
 * Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
535
 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
Matthias Braun's avatar
Matthias Braun committed
536
 * SymConst(name)-Operationen müssen in passende SymConst(ent)-Operationen
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
537
 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
Michael Beck's avatar
Michael Beck committed
538
539
 * auf eine echt externe Methode.
 */
540
static size_t get_free_methods(ir_entity ***free_methods)
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
541
{
Matthias Braun's avatar
Matthias Braun committed
542
	pset *free_set = pset_new_ptr_default();
Michael Beck's avatar
Michael Beck committed
543
	size_t i, n, j, m;
Michael Beck's avatar
Michael Beck committed
544
	ir_entity **arr;
Michael Beck's avatar
Michael Beck committed
545
546
	ir_entity *ent;
	ir_graph *irg;
Michael Beck's avatar
Michael Beck committed
547
	ir_type *tp;
548
	size_t length;
Michael Beck's avatar
Michael Beck committed
549

Michael Beck's avatar
Michael Beck committed
550
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
Matthias Braun's avatar
Matthias Braun committed
551
		ir_linkage linkage;
Michael Beck's avatar
Michael Beck committed
552
553
		irg = get_irp_irg(i);
		ent = get_irg_entity(irg);
Matthias Braun's avatar
Matthias Braun committed
554
555
		linkage = get_entity_linkage(ent);

Michael Beck's avatar
Michael Beck committed
556
		if ((linkage & IR_LINKAGE_HIDDEN_USER) || entity_is_externally_visible(ent)) {
Matthias Braun's avatar
Matthias Braun committed
557
			pset_insert_ptr(free_set, ent);
Michael Beck's avatar
Michael Beck committed
558
		}
Michael Beck's avatar
Michael Beck committed
559

560
		ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
561
		/* Find all method entities that gets "visible" through this graphs,
Michael Beck's avatar
Michael Beck committed
562
		 * for instance because their address is stored. */
563
		irg_walk_graph(irg, firm_clear_link, free_ana_walker, free_set);
564
		ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
Michael Beck's avatar
Michael Beck committed
565
566
	}

Michael Beck's avatar
Michael Beck committed
567
	/* insert all methods that are used in global variables initializers */
Michael Beck's avatar
Michael Beck committed
568
	tp = get_glob_type();
Michael Beck's avatar
Michael Beck committed
569
	for (j = 0, m = get_class_n_members(tp); j < m; ++j) {
Michael Beck's avatar
Michael Beck committed
570
		ent = get_class_member(tp, j);
Michael Beck's avatar
Michael Beck committed
571
572
573
		add_method_address(ent, free_set);
	}
	tp = get_tls_type();
574
575
	for (j = 0, m = get_compound_n_members(tp); j < m; ++j) {
		ent = get_compound_member(tp, j);
Michael Beck's avatar
Michael Beck committed
576
577
578
579
580
		add_method_address(ent, free_set);
	}

	/* the main program is even then "free", if it's not external visible. */
	irg = get_irp_main_irg();
Michael Beck's avatar
Michael Beck committed
581
	if (irg != NULL)
Matthias Braun's avatar
Matthias Braun committed
582
		pset_insert_ptr(free_set, get_irg_entity(irg));
Michael Beck's avatar
Michael Beck committed
583
584

	/* Finally, transform the set into an array. */
Matthias Braun's avatar
Matthias Braun committed
585
	length = pset_count(free_set);
586
	arr = XMALLOCN(ir_entity*, length);
Matthias Braun's avatar
Matthias Braun committed
587
588
	i = 0;
	foreach_pset(free_set, ir_entity*, ent) {
Michael Beck's avatar
Michael Beck committed
589
		arr[i++] = ent;
Michael Beck's avatar
Michael Beck committed
590
	}
Matthias Braun's avatar
Matthias Braun committed
591
	del_pset(free_set);
Michael Beck's avatar
Michael Beck committed
592

593
594
	*free_methods = arr;
	return length;
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
595
596
597
598
599
600
}

/*--------------------------------------------------------------------------*/
/* Callee analysis.                                                         */
/*--------------------------------------------------------------------------*/

Matthias Braun's avatar
Matthias Braun committed
601
static void callee_ana_node(ir_node *node, pset *methods);
602

Matthias Braun's avatar
Matthias Braun committed
603
static void callee_ana_proj(ir_node *node, long n, pset *methods)
Matthias Braun's avatar
Matthias Braun committed
604
{
Michael Beck's avatar
Michael Beck committed
605
606
607
608
609
610
611
612
613
614
615
	assert(get_irn_mode(node) == mode_T);
	if (get_irn_link(node) == MARK) {
		/* already visited */
		return;
	}
	set_irn_link(node, MARK);

	switch (get_irn_opcode(node)) {
	case iro_Proj: {
		/* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
		 * op_Tuple oder ein Knoten, der eine "freie Methode"
yb9976's avatar
yb9976 committed
616
		 * zur�ckgibt. */
Michael Beck's avatar
Michael Beck committed
617
		ir_node *pred = get_Proj_pred(node);
Michael Beck's avatar
Michael Beck committed
618
		if (get_irn_link(pred) != MARK) {
Michael Beck's avatar
Michael Beck committed
619
			if (is_Tuple(pred)) {
Michael Beck's avatar
Michael Beck committed
620
621
				callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
			} else {
Matthias Braun's avatar
Matthias Braun committed
622
				pset_insert_ptr(methods, unknown_entity); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
623
624
625
			}
		}
		break;
Michael Beck's avatar
Michael Beck committed
626
	}
Michael Beck's avatar
Michael Beck committed
627
628
629
630
631
632

	case iro_Tuple:
		callee_ana_node(get_Tuple_pred(node, n), methods);
		break;

	default:
Matthias Braun's avatar
Matthias Braun committed
633
		pset_insert_ptr(methods, unknown_entity); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
634
635
		break;
	}
636
637
}

Michael Beck's avatar
Michael Beck committed
638
/**
Michael Beck's avatar
Michael Beck committed
639
 * Analyse a Call address.
Michael Beck's avatar
Michael Beck committed
640
 *
Michael Beck's avatar
Michael Beck committed
641
642
 * @param node     the node representing the call address
 * @param methods  after call contains the set of all possibly called entities
Michael Beck's avatar
Michael Beck committed
643
 */
Matthias Braun's avatar
Matthias Braun committed
644
static void callee_ana_node(ir_node *node, pset *methods)
Matthias Braun's avatar
Matthias Braun committed
645
{
Michael Beck's avatar
Michael Beck committed
646
647
648
649
650
651
652
653
654
655
656
	assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
	/* Beware of recursion */
	if (get_irn_link(node) == MARK) {
		/* already visited */
		return;
	}
	set_irn_link(node, MARK);

	switch (get_irn_opcode(node)) {
	case iro_Const:
		/* A direct address call. We tread this as an external
Michael Beck's avatar
Michael Beck committed
657
		   call and ignore it completely. */
Matthias Braun's avatar
Matthias Braun committed
658
		pset_insert_ptr(methods, unknown_entity); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
659
		break;
660
661
662
663

	case iro_SymConst: {
		ir_entity *ent = get_SymConst_entity(node);
		assert(ent && is_method_entity(ent));
Matthias Braun's avatar
Matthias Braun committed
664
		pset_insert_ptr(methods, ent);
Michael Beck's avatar
Michael Beck committed
665
		break;
666
667
	}

668
	case iro_Sel: {
Michael Beck's avatar
Michael Beck committed
669
		/* polymorphic method */
670
671
		size_t i, n;
		for (i = 0, n = get_Sel_n_methods(node); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
672
673
			ir_entity *ent = get_Sel_method(node, i);
			if (ent != NULL) {
Matthias Braun's avatar
Matthias Braun committed
674
				pset_insert_ptr(methods, ent);
Michael Beck's avatar
Michael Beck committed
675
			} else {
Matthias Braun's avatar
Matthias Braun committed
676
				pset_insert_ptr(methods, unknown_entity);
Michael Beck's avatar
Michael Beck committed
677
678
679
			}
		}
		break;
680
	}
Michael Beck's avatar
Michael Beck committed
681
682
683
684
685

	case iro_Bad:
		/* nothing */
		break;

686
687
	case iro_Phi: {
		int i;
Michael Beck's avatar
Michael Beck committed
688
689
690
691
		for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
			callee_ana_node(get_Phi_pred(node, i), methods);
		}
		break;
692
	}
Michael Beck's avatar
Michael Beck committed
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710

	case iro_Mux:
		callee_ana_node(get_Mux_false(node), methods);
		callee_ana_node(get_Mux_true(node), methods);
		break;

	case iro_Id:
		callee_ana_node(get_Id_pred(node), methods);
		break;

	case iro_Proj:
		callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
		break;

	case iro_Add:
	case iro_Sub:
	case iro_Conv:
		/* extern */
Matthias Braun's avatar
Matthias Braun committed
711
		pset_insert_ptr(methods, unknown_entity); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
712
713
714
715
716
717
		break;

	default:
		assert(0 && "invalid opcode or opcode not implemented");
		break;
	}
718
719
}

Michael Beck's avatar
Michael Beck committed
720
/**
Michael Beck's avatar
Michael Beck committed
721
 * Walker: Analyses every Call node and calculates an array of possible
Michael Beck's avatar
Michael Beck committed
722
723
 * callees for that call.
 */
Matthias Braun's avatar
Matthias Braun committed
724
725
static void callee_walker(ir_node *call, void *env)
{
Michael Beck's avatar
Michael Beck committed
726
727
	(void) env;
	if (is_Call(call)) {
Matthias Braun's avatar
Matthias Braun committed
728
		pset *methods = pset_new_ptr_default();
Michael Beck's avatar
Michael Beck committed
729
730
		ir_entity *ent;
		ir_entity **arr;
731
		size_t i;
Michael Beck's avatar
Michael Beck committed
732

Michael Beck's avatar
Michael Beck committed
733
		callee_ana_node(get_Call_ptr(call), methods);
Matthias Braun's avatar
Matthias Braun committed
734
735
736
		arr = NEW_ARR_F(ir_entity*, pset_count(methods));
		i = 0;
		foreach_pset(methods, ir_entity*, ent) {
Michael Beck's avatar
Michael Beck committed
737
738
739
740
741
			arr[i] = ent;
			/* we want the unknown_entity on the zero position for easy tests later */
			if (ent == unknown_entity) {
				arr[i] = arr[0];
				arr[0] = unknown_entity;
Michael Beck's avatar
Michael Beck committed
742
			}
Michael Beck's avatar
Michael Beck committed
743
			++i;
Michael Beck's avatar
Michael Beck committed
744
		}
Michael Beck's avatar
Michael Beck committed
745
		set_Call_callee_arr(call, ARR_LEN(arr), arr);
Michael Beck's avatar
Michael Beck committed
746
		DEL_ARR_F(arr);
Matthias Braun's avatar
Matthias Braun committed
747
		del_pset(methods);
Michael Beck's avatar
Michael Beck committed
748
	}
749
750
}

Michael Beck's avatar
Michael Beck committed
751
752
753
/**
 * Walker: Removes all tuple.
 */
Matthias Braun's avatar
Matthias Braun committed
754
755
static void remove_Tuples(ir_node *proj, void *env)
{
Michael Beck's avatar
Michael Beck committed
756
757
758
	ir_node *nn;
	(void) env;
	if (! is_Proj(proj)) return;
759

Michael Beck's avatar
Michael Beck committed
760
761
	nn = skip_Tuple(proj);
	if (nn != proj) exchange(proj, nn);
762
763
764
}


Michael Beck's avatar
Michael Beck committed
765
766
767
768
769
/**
 * Determine for every Call the set of possibly called methods and stores it
 * inside the Call (@see set_Call_callee()).
 * Uses the sel_methods set with much be already calculated.
 */
Matthias Braun's avatar
Matthias Braun committed
770
771
static void callee_ana(void)
{
Michael Beck's avatar
Michael Beck committed
772
	size_t i, n;
Michael Beck's avatar
Michael Beck committed
773
	/* analyse all graphs */
Michael Beck's avatar
Michael Beck committed
774
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
775
776
777
778
779
		ir_graph *irg = get_irp_irg(i);
		irg_walk_graph(irg, callee_walker, remove_Tuples, NULL);
		set_irg_callee_info_state(irg, irg_callee_info_consistent);
	}
	set_irp_callee_info_state(irg_callee_info_consistent);
780
781
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
782
783
784
/*--------------------------------------------------------------------------*/
/* Cleanup after analyses.                                                  */
/*--------------------------------------------------------------------------*/
785

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
786
/** Frees intermediate data structures. */
Matthias Braun's avatar
Matthias Braun committed
787
788
static void sel_methods_dispose(void)
{
Michael Beck's avatar
Michael Beck committed
789
790
	ir_entity * ent;
	assert(entities);
Matthias Braun's avatar
Matthias Braun committed
791
792
793
	foreach_pset(entities, ir_entity*, ent) {
		ir_entity **arr = (ir_entity**) get_entity_link(ent);
		if (arr != NULL) {
Michael Beck's avatar
Michael Beck committed
794
795
796
797
			DEL_ARR_F(arr);
		}
		set_entity_link(ent, NULL);
	}
Matthias Braun's avatar
Matthias Braun committed
798
	del_pset(entities);
Michael Beck's avatar
Michael Beck committed
799
	entities = NULL;
800
801
}

Matthias Braun's avatar
Matthias Braun committed
802
803
static void destruct_walker(ir_node * node, void * env)
{
Michael Beck's avatar
Michael Beck committed
804
805
806
807
	(void) env;
	if (is_Call(node)) {
		remove_Call_callee_arr(node);
	}
808
809
}

810
size_t cgana(ir_entity ***free_methods)
Matthias Braun's avatar
Matthias Braun committed
811
{
812
	size_t length;
Michael Beck's avatar
Michael Beck committed
813
814
	/* Optimize Sel/SymConst nodes and compute all methods that implement an entity. */
	sel_methods_init();
815
	length = get_free_methods(free_methods);
Michael Beck's avatar
Michael Beck committed
816
817
	callee_ana();
	sel_methods_dispose();
818
	return length;
819
}
820

Matthias Braun's avatar
Matthias Braun committed
821
822
void free_callee_info(ir_graph *irg)
{
Michael Beck's avatar
Michael Beck committed
823
824
	irg_walk_graph(irg, destruct_walker, NULL, NULL);
	set_irg_callee_info_state(irg, irg_callee_info_none);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
825
826
}

Matthias Braun's avatar
Matthias Braun committed
827
828
void free_irp_callee_info(void)
{
Michael Beck's avatar
Michael Beck committed
829
830
	size_t i, n;
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
831
832
		free_callee_info(get_irp_irg(i));
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
833
834
}

Matthias Braun's avatar
Matthias Braun committed
835
836
void opt_call_addrs(void)
{
837
838
839
840
841
842
843
844
845
846
847
848
849
850
	/* Optimize the address expressions passed to call nodes.
	 *
	 * This optimization performs the following transformations for
	 * all ir graphs:
	 * - All SymConst operations that refer to intern methods are replaced
	 *   by Const operations referring to the corresponding entity.
	 * - Sel nodes, that select entities that are not overwritten are
	 *   replaced by Const nodes referring to the selected entity.
	 * - Sel nodes, for which no method exists at all are replaced by Bad
	 *   nodes.
	 * - Sel nodes with a pointer input that is an Alloc node are replaced
	 *   by Const nodes referring to the entity that implements the method in
	 *   the type given by the Alloc node.
	 */
Michael Beck's avatar
Michael Beck committed
851
852
	sel_methods_init();
	sel_methods_dispose();
853
}