cgana.c 25.2 KB
Newer Older
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 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
25
/**
 * @file
 * @brief      Intraprozedural analyses to estimate the call graph.
 * @author     Hubert Schmid
 * @date       09.06.2002
 * @version    $Id$
yb9976's avatar
yb9976 committed
26
 * @brief
Matthias Braun's avatar
Matthias Braun committed
27
28
29
30
31
32
33
 *  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
34
#include "config.h"
Michael Beck's avatar
Michael Beck committed
35
36

# include <string.h>
37
38

#include "cgana.h"
Florian Liekweg's avatar
Florian Liekweg committed
39
#include "rta.h"
40

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

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

Götz Lindenmaier's avatar
Götz Lindenmaier committed
55
56
57
#include "eset.h"
#include "pmap.h"
#include "array.h"
58
#include "error.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
59

60
61
#include "irdump.h"

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

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
65
static eset *entities = NULL;
66

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
67
68
69
/*--------------------------------------------------------------------------*/
/* The analysis                                                             */
/*--------------------------------------------------------------------------*/
70
71


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

77
/** Returns the entity that contains the implementation of the inherited
Götz Lindenmaier's avatar
Götz Lindenmaier committed
78
 *  entity if available, else returns the entity passed. */
79
static ir_entity *get_inherited_methods_implementation(ir_entity *inh_meth) {
80
81
82
	ir_node *value = get_atomic_ent_value(inh_meth);
	assert(value && "constant entity without value");
	assert(is_SymConst_addr_ent(value) &&
Michael Beck's avatar
Michael Beck committed
83
	       "Complex constant values not supported -- address of method should be straight constant!");
84

85
	return get_SymConst_entity(value);
86
87
}

88
/** Collect the entity representing the implementation of this
89
 *  method (not the same if inherited) and all entities for overwriting
90
91
92
93
94
95
96
97
98
99
100
 *  implementations in "set".
 *  If the implementation of the method is not included in the
 *  compilation unit "open" is set to true.
 *  A recursive descend in the overwritten relation.
 *  Cycle-free, therefore must terminate.
 *
 * @param method
 * @param set      A set of entities.
 * @param size     Number of entities in set.
 * @param open
 */
101
static void collect_impls(ir_entity *method, eset *set, int *size, int *open) {
Michael Beck's avatar
Michael Beck committed
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
	int i;
	ir_entity *impl;

	/* Add the implementation to the set if it contains an irg, else
	   remember that there are more methods called. */
	impl = method;
	if (get_entity_peculiarity(method) == peculiarity_inherited)
		impl = get_inherited_methods_implementation(method);

	if (get_entity_peculiarity(method) != peculiarity_description) {
		eset_insert(set, impl);
		++(*size);
	}

	/*- recursive descent -*/
	for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i)
		collect_impls(get_entity_overwrittenby(method, i), set, size, open);
119
120
}

yb9976's avatar
yb9976 committed
121
122
123
124
125
126
127
/** Alle Methoden bestimmen, die die �bergebene Methode �berschreiben
 *  (und implementieren). In der zur�ckgegebenen Reihung kommt jede
 *  Methode nur einmal vor. Der Wert 'NULL' steht f�r unbekannte
 *  (externe) Methoden. Die zur�ckgegebene Reihung mu� vom Aufrufer
 *  wieder freigegeben werden (siehe "DEL_ARR_F"). Gibt es �berhaupt
 *  keine Methoden, die "method" �berschreiben, so gibt die Methode
 *  "NULL" zur�ck.
128
129
130
 *
 *  @param method
 */
131
static ir_entity ** get_impl_methods(ir_entity * method) {
Michael Beck's avatar
Michael Beck committed
132
133
134
135
136
137
138
139
140
141
	eset * set = eset_create();
	int size = 0;
	ir_entity ** arr;
	int open = 0;

	/* Collect all method entities that can be called here */
	collect_impls(method, set, &size, &open);

	/* Vorgaenger einfuegen. */
	if (size == 0 && !open) {
yb9976's avatar
yb9976 committed
142
		/* keine implementierte �berschriebene Methode */
Michael Beck's avatar
Michael Beck committed
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
		arr = NULL;
	} else if (open) {
		ir_entity * ent;
		arr = NEW_ARR_F(ir_entity *, size + 1);
		arr[0] = NULL;  /* Represents open method */
		for (ent = eset_first(set); size > 0; ent = eset_next(set), --size)
			arr[size] = ent;
	} else {
		ir_entity * ent;
		arr = NEW_ARR_F(ir_entity *, size);
		for (size -= 1, ent = eset_first(set); size >= 0; ent = eset_next(set), --size)
			arr[size] = ent;
	}
	eset_destroy(set);
	return arr;
158
159
}

Michael Beck's avatar
Michael Beck committed
160
/** Analyze address computations.
161
 *
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
162
 *  Compute for all Sel nodes the set of methods that can be selected.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
163
 *  For each entity we store the set of subentities in the link field.
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
164
165
166
167
 *
 *  Further do some optimizations:
 *  - Call standard optimizations for Sel nodes: this removes polymorphic
 *    calls.
168
 *  - If the node is a SymConst(name) replace it by SymConst(ent) if possible.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
169
170
 *    For this we precomputed a map name->entity.  Nowadays, we no more support
 *    this and assert.
171
 *  - If the node is a Sel:
Götz Lindenmaier's avatar
Götz Lindenmaier committed
172
173
174
175
 *    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.
176
 *
Michael Beck's avatar
Michael Beck committed
177
178
 *  @param node  The node to analyze
 *  @param env   A map that maps names of entities to the entities.
179
 */
Michael Beck's avatar
Michael Beck committed
180
static void sel_methods_walker(ir_node *node, void *env) {
Michael Beck's avatar
Michael Beck committed
181
182
183
184
185
186
	pmap *ldname_map = env;
	ir_entity **arr;

	/* Call standard optimizations */
	if (is_Sel(node)) {
		ir_node *new_node = optimize_in_place(node);
187
		if (node != new_node) {
Michael Beck's avatar
Michael Beck committed
188
			exchange(node, new_node);
189
190
			node = new_node;
		}
Michael Beck's avatar
Michael Beck committed
191
192
193
	}

	/* replace SymConst(name)-operations by SymConst(ent) */
Michael Beck's avatar
Michael Beck committed
194
	if (is_SymConst(node)) {
Michael Beck's avatar
Michael Beck committed
195
		if (get_SymConst_kind(node) == symconst_addr_name) {
Michael Beck's avatar
Michael Beck committed
196
			pmap_entry *entry = pmap_find(ldname_map, get_SymConst_name(node));
Michael Beck's avatar
Michael Beck committed
197
			if (entry != NULL) { /* Method is declared in the compiled code */
Michael Beck's avatar
Michael Beck committed
198
				assert(!"There should not be a SymConst[addr_name] addressing a method with an implementation"
Michael Beck's avatar
Michael Beck committed
199
200
201
					"in this compilation unit.  Use a SymConst[addr_ent].");
			}
		}
Michael Beck's avatar
Michael Beck committed
202
	} else if (is_Sel(node) && is_Method_type(get_entity_type(get_Sel_entity(node)))) {
203
204
205
206
207
208
209
210
211
212
		ir_entity *ent = get_SymConst_entity(get_atomic_ent_value(get_Sel_entity(node)));
		assert(get_entity_peculiarity(ent) != peculiarity_inherited);

		if (!eset_contains(entities, ent)) {
			/* 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));
			eset_insert(entities, ent);
		}
Michael Beck's avatar
Michael Beck committed
213

214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
		/* -- As an add on we get an optimization that removes polymorphic calls.
		This optimization is more powerful than that in transform_node_Sel().  -- */
		arr = get_entity_link(ent);
		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.
			 */
			assert(get_entity_peculiarity(ent) == peculiarity_description);
		}
		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.
			 */
			set_irg_current_block(current_ir_graph, get_nodes_block(node));
			assert(get_entity_peculiarity(get_SymConst_entity(get_atomic_ent_value(arr[0]))) ==
				peculiarity_existent);
			new_node = copy_const_value(get_irn_dbg_info(node), get_atomic_ent_value(arr[0]));
			DBG_OPT_POLY(node, new_node);
			exchange(node, new_node);
		}
Michael Beck's avatar
Michael Beck committed
241
	}
242
243
}

Michael Beck's avatar
Michael Beck committed
244
245
/**
 * Initialize auxiliary data structures.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
246
 *
Michael Beck's avatar
Michael Beck committed
247
248
 * 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
249
 *
Michael Beck's avatar
Michael Beck committed
250
251
252
253
254
 * 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).
 */
255
static void sel_methods_init(void) {
Michael Beck's avatar
Michael Beck committed
256
	int i;
Michael Beck's avatar
Michael Beck committed
257
258
	pmap *ldname_map = pmap_create();   /* Map entity names to entities: to replace
	                                       SymConst(name) by SymConst(ent). */
Michael Beck's avatar
Michael Beck committed
259
260
261
262
263
264
	assert(entities == NULL);
	entities = eset_create();
	for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
		ir_entity * ent = get_irg_entity(get_irp_irg(i));
		/* only external visible methods are allowed to call by a SymConst_ptr_name */
		if (get_entity_visibility(ent) != visibility_local) {
Michael Beck's avatar
Michael Beck committed
265
			pmap_insert(ldname_map, (void *)get_entity_ld_ident(ent), ent);
Michael Beck's avatar
Michael Beck committed
266
267
268
269
270
		}
	}

	all_irg_walk(sel_methods_walker, NULL, ldname_map);
	pmap_destroy(ldname_map);
271
272
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
273
274
275
276
277
278
/*--------------------------------------------------------------------------*/
/* Find free methods.
 *
 * We expect that each entity has an array with all implementations in its
 * link field.                                                              */
/*--------------------------------------------------------------------------*/
279

280
281
282
/**
 * Returns an array of all methods that could be called at a Sel node.
 * This array contains every entry only once.
283
284
 *
 * @param sel  the Sel node
285
 */
286
static ir_entity ** get_Sel_arr(ir_node * sel) {
Michael Beck's avatar
Michael Beck committed
287
288
289
290
291
292
293
294
295
296
297
298
299
300
	static ir_entity ** NULL_ARRAY = NULL;
	ir_entity * ent;
	ir_entity ** arr;

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

	assert(is_Method_type(get_entity_type(ent))); /* what else? */
	arr = get_entity_link(ent);
	if (arr) {
		return arr;
	} else {
		/* "NULL" zeigt an, dass keine Implementierung existiert. Dies
yb9976's avatar
yb9976 committed
301
		 * kann f�r polymorphe (abstrakte) Methoden passieren. */
Michael Beck's avatar
Michael Beck committed
302
303
304
305
306
		if (!NULL_ARRAY) {
			NULL_ARRAY = NEW_ARR_F(ir_entity *, 0);
		}
		return NULL_ARRAY;
	}
307
308
}

309
310
/**
 * Returns the number of possible called methods at a Sel node.
311
312
 *
 * @param sel  the Sel node
313
 */
314
static int get_Sel_n_methods(ir_node * sel) {
Michael Beck's avatar
Michael Beck committed
315
	return ARR_LEN(get_Sel_arr(sel));
316
317
}

318
319
320
/**
 * Returns the ith possible called method entity at a Sel node.
 */
321
static ir_entity * get_Sel_method(ir_node * sel, int pos) {
Michael Beck's avatar
Michael Beck committed
322
323
324
	ir_entity ** arr = get_Sel_arr(sel);
	assert(pos >= 0 && pos < ARR_LEN(arr));
	return arr[pos];
325
326
}

Michael Beck's avatar
Michael Beck committed
327
/* forward */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
328
static void free_mark(ir_node * node, eset * set);
329

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
330
static void free_mark_proj(ir_node * node, long n, eset * set) {
Michael Beck's avatar
Michael Beck committed
331
332
333
334
335
336
337
338
339
340
341
342
	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);
343
		if (get_irn_link(pred) != MARK && is_Tuple(pred)) {
Michael Beck's avatar
Michael Beck committed
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
			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;
	}
370
	// set_irn_link(node, NULL);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
371
372
}

373
/**
Michael Beck's avatar
Michael Beck committed
374
375
376
377
378
379
380
 * 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
 *
381
382
383
384
 * @param node  the current visited node
 * @param set   the set of all free methods
 */
static void free_mark(ir_node *node, eset * set) {
Michael Beck's avatar
Michael Beck committed
385
386
387
388
389
390
391
392
393
	int i;

	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
394
395
		ir_entity *ent = get_Sel_entity(node);
		if (is_method_entity(ent)) {
Michael Beck's avatar
Michael Beck committed
396
397
398
399
400
			for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
				eset_insert(set, get_Sel_method(node, i));
			}
		}
		break;
Michael Beck's avatar
Michael Beck committed
401
	}
Michael Beck's avatar
Michael Beck committed
402
403
	case iro_SymConst:
		if (get_SymConst_kind(node) == symconst_addr_ent) {
Michael Beck's avatar
Michael Beck committed
404
405
			ir_entity *ent = get_SymConst_entity(node);
			if (is_method_entity(ent)) {
Michael Beck's avatar
Michael Beck committed
406
407
408
409
410
411
412
413
414
415
416
417
418
419
				eset_insert(set, ent);
			}
		}
		break;

	case iro_Phi:
		for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
			free_mark(get_Phi_pred(node, i), set);
		}
		break;
	case iro_Proj:
		free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
		break;
	default:
Michael Beck's avatar
Michael Beck committed
420
		/* nothing: */
Michael Beck's avatar
Michael Beck committed
421
422
		break;
	}
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
423
}
424

425
/**
Michael Beck's avatar
Michael Beck committed
426
 * post-walker. Find method addresses.
427
428
 */
static void free_ana_walker(ir_node *node, void *env) {
Michael Beck's avatar
Michael Beck committed
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
	eset *set = env;
	int i;

	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
448
449
		/* we must handle Call nodes specially, because their call address input
		   do not expose a method address. */
Michael Beck's avatar
Michael Beck committed
450
451
452
453
454
455
456
457
		set_irn_link(node, MARK);
		for (i = get_Call_n_params(node) - 1; i >= 0; --i) {
			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
458
	default:
yb9976's avatar
yb9976 committed
459
		/* other nodes: Alle anderen Knoten nehmen wir als Verr�ter an, bis
Michael Beck's avatar
Michael Beck committed
460
461
462
		 * 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
463
			ir_node *pred = get_irn_n(node, i);
Michael Beck's avatar
Michael Beck committed
464
465
466
467
468
469
			if (mode_is_reference(get_irn_mode(pred))) {
				free_mark(pred, set);
			}
		}
		break;
	}
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
470
471
}

472
473
474
475
476
477
478
479
480
481
482
/**
 * Add all method addresses in global new style initializers to the set.
 *
 * @note
 * We do NOT check the type here, just it it's an entity address.
 * The reason for this is code like:
 *
 * void *p = function;
 *
 * which is sometimes used to anchor functions.
 */
483
484
static void add_method_address_inititializer(ir_initializer_t *initializer,
                                             eset *set)
485
{
486
487
488
	ir_node *n;
	size_t  i;

489
	switch (initializer->kind) {
490
491
	case IR_INITIALIZER_CONST:
		n = initializer->consti.value;
492
493

		/* let's check if it's the address of a function */
494
495
		if (is_Global(n)) {
			ir_entity *ent = get_Global_entity(n);
496
497
498
499
500
501
502
503

			if (is_Method_type(get_entity_type(ent)))
				eset_insert(set, ent);
		}
		return;
	case IR_INITIALIZER_TARVAL:
	case IR_INITIALIZER_NULL:
		return;
504
	case IR_INITIALIZER_COMPOUND:
505
		for (i = 0; i < initializer->compound.n_initializers; ++i) {
506
507
			ir_initializer_t *sub_initializer
				= initializer->compound.initializers[i];
508
			add_method_address_inititializer(sub_initializer, set);
509
510
511
512
513
514
		}
		return;
	}
	panic("invalid initializer found");
}

515
516
/**
 * Add all method addresses in global initializers to the set.
517
518
519
520
521
522
523
524
 *
 * @note
 * We do NOT check the type here, just it it's an entity address.
 * The reason for this is code like:
 *
 * void *p = function;
 *
 * which is sometimes used to anchor functions.
525
 */
526
static void add_method_address(ir_entity *ent, eset *set)
527
{
Michael Beck's avatar
Michael Beck committed
528
529
530
531
532
533
534
535
	ir_node *n;
	ir_type *tp;
	int i;

	/* do not check uninitialized values */
	if (get_entity_variability(ent) == variability_uninitialized)
		return;

536
	if (ent->has_initializer) {
537
		add_method_address_inititializer(get_entity_initializer(ent), set);
538
	} else if (is_atomic_entity(ent)) {
Michael Beck's avatar
Michael Beck committed
539
540
541
542
543
544
545
546
		tp = get_entity_type(ent);

		/* ignore methods: these of course reference it's address */
		if (is_Method_type(tp))
			return;

		/* let's check if it's the address of a function */
		n = get_atomic_ent_value(ent);
547
548
		if (is_Global(n)) {
			ent = get_Global_entity(n);
Michael Beck's avatar
Michael Beck committed
549

Michael Beck's avatar
Michael Beck committed
550
551
			if (is_Method_type(get_entity_type(ent)))
				eset_insert(set, ent);
Michael Beck's avatar
Michael Beck committed
552
553
554
555
556
557
		}
	} else {
		for (i = get_compound_ent_n_values(ent) - 1; i >= 0; --i) {
			n = get_compound_ent_value(ent, i);

			/* let's check if it's the address of a function */
558
559
			if (is_Global(n)) {
				ir_entity *ent = get_Global_entity(n);
Michael Beck's avatar
Michael Beck committed
560

Michael Beck's avatar
Michael Beck committed
561
562
				if (is_Method_type(get_entity_type(ent)))
					eset_insert(set, ent);
Michael Beck's avatar
Michael Beck committed
563
564
565
			}
		}
	}
566
567
}

Michael Beck's avatar
Michael Beck committed
568
569
570
571
/**
 * returns a list of 'free' methods, i.e., the methods that can be called
 * from external or via function pointers.
 *
yb9976's avatar
yb9976 committed
572
 * Die Datenstrukturen f�r sel-Methoden (sel_methods) mu� vor dem
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
573
 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
yb9976's avatar
yb9976 committed
574
 * SymConst(name)-Operationen m�ssen in passende SymConst(ent)-Operationen
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
575
 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
Michael Beck's avatar
Michael Beck committed
576
577
 * auf eine echt externe Methode.
 */
Michael Beck's avatar
Michael Beck committed
578
static ir_entity **get_free_methods(int *length)
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
579
{
Michael Beck's avatar
Michael Beck committed
580
581
	eset *free_set = eset_create();
	int i;
Michael Beck's avatar
Michael Beck committed
582
	ir_entity **arr;
Michael Beck's avatar
Michael Beck committed
583
584
	ir_entity *ent;
	ir_graph *irg;
Michael Beck's avatar
Michael Beck committed
585
	ir_type *tp;
Michael Beck's avatar
Michael Beck committed
586
587
588
589
590

	for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
		irg = get_irp_irg(i);
		ent = get_irg_entity(irg);
		if (get_entity_visibility(ent) != visibility_local) {
591
			/* insert non-local (external) methods. */
Michael Beck's avatar
Michael Beck committed
592
			eset_insert(free_set, ent);
593
594
		} else if (get_entity_stickyness(ent) == stickyness_sticky) {
			/* insert "sticky" methods. */
Michael Beck's avatar
Michael Beck committed
595
596
			eset_insert(free_set, ent);
		}
Michael Beck's avatar
Michael Beck committed
597

598
		ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
599
		/* Find all method entities that gets "visible" through this graphs,
Michael Beck's avatar
Michael Beck committed
600
		 * for instance because their address is stored. */
601
		irg_walk_graph(irg, firm_clear_link, free_ana_walker, free_set);
602
		ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
Michael Beck's avatar
Michael Beck committed
603
604
	}

Michael Beck's avatar
Michael Beck committed
605
	/* insert all methods that are used in global variables initializers */
Michael Beck's avatar
Michael Beck committed
606
607
608
609
610
611
612
613
	tp = get_glob_type();
	for (i = get_class_n_members(tp) - 1; i >= 0; --i) {
		ent = get_class_member(tp, i);
		add_method_address(ent, free_set);
	}
	tp = get_tls_type();
	for (i = get_struct_n_members(tp) - 1; i >= 0; --i) {
		ent = get_struct_member(tp, i);
Michael Beck's avatar
Michael Beck committed
614
615
616
617
618
		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
619
	if (irg != NULL)
Michael Beck's avatar
Michael Beck committed
620
621
622
		eset_insert(free_set, get_irg_entity(irg));

	/* Finally, transform the set into an array. */
Michael Beck's avatar
Michael Beck committed
623
	*length = eset_count(free_set);
624
	arr = XMALLOCN(ir_entity*, *length);
Michael Beck's avatar
Michael Beck committed
625
626
	for (i = 0, ent = eset_first(free_set); ent; ent = eset_next(free_set)) {
		arr[i++] = ent;
Michael Beck's avatar
Michael Beck committed
627
628
629
630
	}
	eset_destroy(free_set);

	return arr;
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
631
632
633
634
635
636
637
}

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

static void callee_ana_node(ir_node * node, eset * methods);
638

Michael Beck's avatar
Michael Beck committed
639
static void callee_ana_proj(ir_node *node, long n, eset *methods) {
Michael Beck's avatar
Michael Beck committed
640
641
642
643
644
645
646
647
648
649
650
	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
651
		 * zur�ckgibt. */
Michael Beck's avatar
Michael Beck committed
652
		ir_node *pred = get_Proj_pred(node);
Michael Beck's avatar
Michael Beck committed
653
		if (get_irn_link(pred) != MARK) {
Michael Beck's avatar
Michael Beck committed
654
			if (is_Tuple(pred)) {
Michael Beck's avatar
Michael Beck committed
655
656
				callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
			} else {
Michael Beck's avatar
Michael Beck committed
657
				eset_insert(methods, unknown_entity); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
658
659
660
			}
		}
		break;
Michael Beck's avatar
Michael Beck committed
661
	}
Michael Beck's avatar
Michael Beck committed
662
663
664
665
666
667

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

	default:
Michael Beck's avatar
Michael Beck committed
668
		eset_insert(methods, unknown_entity); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
669
670
		break;
	}
671
672
}

Michael Beck's avatar
Michael Beck committed
673
/**
Michael Beck's avatar
Michael Beck committed
674
 * Analyse a Call address.
Michael Beck's avatar
Michael Beck committed
675
 *
Michael Beck's avatar
Michael Beck committed
676
677
 * @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
678
 */
Michael Beck's avatar
Michael Beck committed
679
static void callee_ana_node(ir_node *node, eset *methods) {
Michael Beck's avatar
Michael Beck committed
680
681
682
683
684
685
686
687
688
689
690
691
692
	int i;

	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
693
694
		   call and ignore it completely. */
		eset_insert(methods, unknown_entity); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
695
696
697
698
		break;
	case iro_SymConst:
		if (get_SymConst_kind(node) == symconst_addr_ent) {
			ir_entity *ent = get_SymConst_entity(node);
Michael Beck's avatar
Michael Beck committed
699
			assert(ent && is_method_entity(ent));
Michael Beck's avatar
Michael Beck committed
700
701
702
			eset_insert(methods, ent);
		} else {
			assert(get_SymConst_kind(node) == symconst_addr_name);
Michael Beck's avatar
Michael Beck committed
703
704
			/* external method (because fix_symconst()!) */
			eset_insert(methods, unknown_entity); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
705
706
707
		}
		break;
	case iro_Sel:
Michael Beck's avatar
Michael Beck committed
708
		/* polymorphic method */
Michael Beck's avatar
Michael Beck committed
709
		for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
Michael Beck's avatar
Michael Beck committed
710
711
			ir_entity *ent = get_Sel_method(node, i);
			if (ent != NULL) {
Michael Beck's avatar
Michael Beck committed
712
713
				eset_insert(methods, ent);
			} else {
Michael Beck's avatar
Michael Beck committed
714
				eset_insert(methods, unknown_entity);
Michael Beck's avatar
Michael Beck committed
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
			}
		}
		break;

	case iro_Bad:
		/* nothing */
		break;

	case iro_Phi:
		for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
			callee_ana_node(get_Phi_pred(node, i), methods);
		}
		break;

	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 */
Michael Beck's avatar
Michael Beck committed
746
		eset_insert(methods, unknown_entity); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
747
748
749
750
751
752
		break;

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

Michael Beck's avatar
Michael Beck committed
755
/**
Michael Beck's avatar
Michael Beck committed
756
 * Walker: Analyses every Call node and calculates an array of possible
Michael Beck's avatar
Michael Beck committed
757
758
 * callees for that call.
 */
Michael Beck's avatar
Michael Beck committed
759
static void callee_walker(ir_node *call, void *env) {
Michael Beck's avatar
Michael Beck committed
760
761
	(void) env;
	if (is_Call(call)) {
Michael Beck's avatar
Michael Beck committed
762
763
764
765
766
		eset *methods = eset_create();
		ir_entity *ent;
		ir_entity **arr;
		int i;

Michael Beck's avatar
Michael Beck committed
767
		callee_ana_node(get_Call_ptr(call), methods);
Michael Beck's avatar
Michael Beck committed
768
769
770
771
772
773
774
		arr = NEW_ARR_F(ir_entity *, eset_count(methods));
		for (i = 0, ent = eset_first(methods); ent; ent = eset_next(methods)) {
			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
775
			}
Michael Beck's avatar
Michael Beck committed
776
			++i;
Michael Beck's avatar
Michael Beck committed
777
		}
Michael Beck's avatar
Michael Beck committed
778
		set_Call_callee_arr(call, ARR_LEN(arr), arr);
Michael Beck's avatar
Michael Beck committed
779
780
781
		DEL_ARR_F(arr);
		eset_destroy(methods);
	}
782
783
}

Michael Beck's avatar
Michael Beck committed
784
785
786
787
/**
 * Walker: Removes all tuple.
 */
static void remove_Tuples(ir_node *proj, void *env) {
Michael Beck's avatar
Michael Beck committed
788
789
790
	ir_node *nn;
	(void) env;
	if (! is_Proj(proj)) return;
791

Michael Beck's avatar
Michael Beck committed
792
793
	nn = skip_Tuple(proj);
	if (nn != proj) exchange(proj, nn);
794
795
796
}


Michael Beck's avatar
Michael Beck committed
797
798
799
800
801
/**
 * 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.
 */
802
static void callee_ana(void) {
Michael Beck's avatar
Michael Beck committed
803
	int i;
Michael Beck's avatar
Michael Beck committed
804
	/* analyse all graphs */
Michael Beck's avatar
Michael Beck committed
805
806
807
808
809
810
	for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
		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);
811
812
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
813
814
815
/*--------------------------------------------------------------------------*/
/* Cleanup after analyses.                                                  */
/*--------------------------------------------------------------------------*/
816

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
817
818
/** Frees intermediate data structures. */
static void sel_methods_dispose(void) {
Michael Beck's avatar
Michael Beck committed
819
820
821
822
823
824
825
826
827
828
829
	ir_entity * ent;
	assert(entities);
	for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
		ir_entity ** arr = get_entity_link(ent);
		if (arr) {
			DEL_ARR_F(arr);
		}
		set_entity_link(ent, NULL);
	}
	eset_destroy(entities);
	entities = NULL;
830
831
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
832
833
834
/*--------------------------------------------------------------------------*/
/* Freeing the callee arrays.                                               */
/*--------------------------------------------------------------------------*/
835

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
836
static void destruct_walker(ir_node * node, void * env) {
Michael Beck's avatar
Michael Beck committed
837
838
839
840
	(void) env;
	if (is_Call(node)) {
		remove_Call_callee_arr(node);
	}
841
842
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
843
844
845
/*--------------------------------------------------------------------------*/
/* Main drivers.                                                            */
/*--------------------------------------------------------------------------*/
846

847
void cgana(int *length, ir_entity ***free_methods) {
Michael Beck's avatar
Michael Beck committed
848
849
	/* Optimize Sel/SymConst nodes and compute all methods that implement an entity. */
	sel_methods_init();
Michael Beck's avatar
Michael Beck committed
850
	*free_methods = get_free_methods(length);
Michael Beck's avatar
Michael Beck committed
851
852
	callee_ana();
	sel_methods_dispose();
853
}
854

Götz Lindenmaier's avatar
Götz Lindenmaier committed
855
void free_callee_info(ir_graph *irg) {
Michael Beck's avatar
Michael Beck committed
856
857
	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
858
859
}

Götz Lindenmaier's avatar
Götz Lindenmaier committed
860
void free_irp_callee_info(void) {
Michael Beck's avatar
Michael Beck committed
861
862
863
864
	int i;
	for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
		free_callee_info(get_irp_irg(i));
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
865
866
}

867
/* Optimize the address expressions passed to call nodes.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
868
869
870
871
 *
 * This optimization performs the following transformations for
 * all ir graphs:
 * - All SymConst operations that refer to intern methods are replaced
Michael Beck's avatar
Michael Beck committed
872
 *   by Const operations referring to the corresponding entity.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
873
 * - Sel nodes, that select entities that are not overwritten are
Michael Beck's avatar
Michael Beck committed
874
 *   replaced by Const nodes referring to the selected entity.
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
875
 * - Sel nodes, for which no method exists at all are replaced by Bad
Götz Lindenmaier's avatar
Götz Lindenmaier committed
876
877
 *   nodes.
 * - Sel nodes with a pointer input that is an Alloc node are replaced
Michael Beck's avatar
Michael Beck committed
878
 *   by Const nodes referring to the entity that implements the method in
Götz Lindenmaier's avatar
Götz Lindenmaier committed
879
880
 *   the type given by the Alloc node.
 */
881
void opt_call_addrs(void) {
Michael Beck's avatar
Michael Beck committed
882
883
	sel_methods_init();
	sel_methods_dispose();
884
}