cgana.c 20.8 KB
Newer Older
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1
/*
Matthias Braun's avatar
Matthias Braun committed
2
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
4
 */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
5

Matthias Braun's avatar
Matthias Braun committed
6
7
8
9
10
/**
 * @file
 * @brief      Intraprozedural analyses to estimate the call graph.
 * @author     Hubert Schmid
 * @date       09.06.2002
yb9976's avatar
yb9976 committed
11
 * @brief
Matthias Braun's avatar
Matthias Braun committed
12
13
14
15
16
17
18
 *  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
19
#include "config.h"
Michael Beck's avatar
Michael Beck committed
20

21
#include "cgana.h"
Michael Beck's avatar
Michael Beck committed
22
#include "xmalloc.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
23
24
25
#include "irnode_t.h"
#include "irmode_t.h"
#include "irprog_t.h"
26
27
28
#include "irgwalk.h"
#include "ircons.h"
#include "irgmod.h"
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
29
#include "iropt.h"
30
#include "irtools.h"
31

Götz Lindenmaier's avatar
Götz Lindenmaier committed
32
#include "irflag_t.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
33
#include "dbginfo_t.h"
Michael Beck's avatar
Michael Beck committed
34
#include "iropt_dbg.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
35

Götz Lindenmaier's avatar
Götz Lindenmaier committed
36
37
#include "pmap.h"
#include "array.h"
38
#include "error.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
39

40
41
#include "irdump.h"

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

Matthias Braun's avatar
Matthias Braun committed
45
static pset *entities = NULL;
46

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
47
48
49
/*--------------------------------------------------------------------------*/
/* The analysis                                                             */
/*--------------------------------------------------------------------------*/
50
51


Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
52
53
54
55
/*--------------------------------------------------------------------------*/
/* Initialize datastructures, remove unwanted constructs, optimize          */
/* call target computations.                                                */
/*--------------------------------------------------------------------------*/
56

57
/** Collect the entity representing the implementation of this
58
 *  method (not the same if inherited) and all entities for overwriting
59
 *  implementations in parameter set.
60
61
62
 *  A recursive descend in the overwritten relation.
 *  Cycle-free, therefore must terminate.
 *
63
 * @param method   the overwritten method
64
 * @param set      A set of entities.
65
66
 *
 * @return Number of entities in set.
67
 */
Matthias Braun's avatar
Matthias Braun committed
68
static size_t collect_impls(ir_entity *method, pset *set)
Matthias Braun's avatar
Matthias Braun committed
69
{
70
71
	size_t i;
	size_t size = 0;
Michael Beck's avatar
Michael Beck committed
72

Matthias Braun's avatar
Matthias Braun committed
73
	if (get_entity_irg(method) != NULL) {
74
		/* has an implementation */
Matthias Braun's avatar
Matthias Braun committed
75
		pset_insert_ptr(set, method);
76
		++size;
Michael Beck's avatar
Michael Beck committed
77
78
79
	}

	/*- recursive descent -*/
80
81
82
	for (i = get_entity_n_overwrittenby(method); i > 0;)
		size += collect_impls(get_entity_overwrittenby(method, --i), set);
	return size;
83
84
}

85
86
87
88
/**
 * 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.
89
 *
90
 * @param method  the method
91
 */
92
static ir_entity **get_impl_methods(ir_entity *method)
Matthias Braun's avatar
Matthias Braun committed
93
{
94
	ir_entity **arr;
Matthias Braun's avatar
Matthias Braun committed
95
	pset      *set = pset_new_ptr_default();
96
	size_t    size;
Michael Beck's avatar
Michael Beck committed
97
98

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

101
102
	if (size == 0) {
		/* no overwriting methods found */
Michael Beck's avatar
Michael Beck committed
103
104
105
		arr = NULL;
	} else {
		arr = NEW_ARR_F(ir_entity *, size);
106
		foreach_pset(set, ir_entity, ent) {
107
			arr[--size] = ent;
Matthias Braun's avatar
Matthias Braun committed
108
		}
Michael Beck's avatar
Michael Beck committed
109
	}
Matthias Braun's avatar
Matthias Braun committed
110
	del_pset(set);
Michael Beck's avatar
Michael Beck committed
111
	return arr;
112
113
}

Michael Beck's avatar
Michael Beck committed
114
/** Analyze address computations.
115
 *
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
116
 *  Compute for all Sel nodes the set of methods that can be selected.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
117
 *  For each entity we store the set of subentities in the link field.
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
118
119
120
121
 *
 *  Further do some optimizations:
 *  - Call standard optimizations for Sel nodes: this removes polymorphic
 *    calls.
122
 *  - If the node is a SymConst(name) replace it by SymConst(ent) if possible.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
123
124
 *    For this we precomputed a map name->entity.  Nowadays, we no more support
 *    this and assert.
125
 *  - If the node is a Sel:
Götz Lindenmaier's avatar
Götz Lindenmaier committed
126
127
128
129
 *    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.
130
 *
Michael Beck's avatar
Michael Beck committed
131
132
 *  @param node  The node to analyze
 *  @param env   A map that maps names of entities to the entities.
133
 */
Matthias Braun's avatar
Matthias Braun committed
134
135
static void sel_methods_walker(ir_node *node, void *env)
{
Michael Beck's avatar
Michael Beck committed
136
	ir_entity **arr;
137
	(void)env;
Michael Beck's avatar
Michael Beck committed
138
139
140
141

	/* Call standard optimizations */
	if (is_Sel(node)) {
		ir_node *new_node = optimize_in_place(node);
142
		if (node != new_node) {
Michael Beck's avatar
Michael Beck committed
143
			exchange(node, new_node);
144
145
			node = new_node;
		}
Michael Beck's avatar
Michael Beck committed
146
147
	}

148
	if (is_Sel(node) && is_Method_type(get_entity_type(get_Sel_entity(node)))) {
149
150
		ir_entity *ent = get_SymConst_entity(get_atomic_ent_value(get_Sel_entity(node)));

Matthias Braun's avatar
Matthias Braun committed
151
		if (!pset_find_ptr(entities, ent)) {
152
153
154
155
			/* 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
156
			pset_insert_ptr(entities, ent);
157
		}
Michael Beck's avatar
Michael Beck committed
158

159
160
		/* -- As an add on we get an optimization that removes polymorphic calls.
		This optimization is more powerful than that in transform_node_Sel().  -- */
161
		arr = (ir_entity**) get_entity_link(ent);
162
163
164
165
166
167
		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
168
			assert(get_entity_irg(ent) == NULL);
169
		}
Michael Beck's avatar
Michael Beck committed
170
	}
171
172
}

Michael Beck's avatar
Michael Beck committed
173
174
/**
 * Initialize auxiliary data structures.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
175
 *
Michael Beck's avatar
Michael Beck committed
176
177
 * 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
178
 *
Michael Beck's avatar
Michael Beck committed
179
180
181
182
183
 * 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
184
185
static void sel_methods_init(void)
{
Michael Beck's avatar
Michael Beck committed
186
	size_t i, n;
Michael Beck's avatar
Michael Beck committed
187
188
	pmap *ldname_map = pmap_create();   /* Map entity names to entities: to replace
	                                       SymConst(name) by SymConst(ent). */
Michael Beck's avatar
Michael Beck committed
189
	assert(entities == NULL);
Matthias Braun's avatar
Matthias Braun committed
190
	entities = pset_new_ptr_default();
Michael Beck's avatar
Michael Beck committed
191
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
192
193
		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
194
		if (entity_is_externally_visible(ent)) {
Michael Beck's avatar
Michael Beck committed
195
			pmap_insert(ldname_map, (void *)get_entity_ld_ident(ent), ent);
Michael Beck's avatar
Michael Beck committed
196
197
198
		}
	}

199
	all_irg_walk(sel_methods_walker, NULL, NULL);
Michael Beck's avatar
Michael Beck committed
200
	pmap_destroy(ldname_map);
201
202
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
203
204
205
206
207
208
/*--------------------------------------------------------------------------*/
/* Find free methods.
 *
 * We expect that each entity has an array with all implementations in its
 * link field.                                                              */
/*--------------------------------------------------------------------------*/
209

210
211
212
/**
 * Returns an array of all methods that could be called at a Sel node.
 * This array contains every entry only once.
213
214
 *
 * @param sel  the Sel node
215
 */
Matthias Braun's avatar
Matthias Braun committed
216
217
static ir_entity ** get_Sel_arr(ir_node * sel)
{
Michael Beck's avatar
Michael Beck committed
218
219
	static ir_entity ** NULL_ARRAY = NULL;

220
	ir_entity *const ent = get_Sel_entity(sel);
Michael Beck's avatar
Michael Beck committed
221
	assert(is_Method_type(get_entity_type(ent))); /* what else? */
222
223

	ir_entity **const arr = (ir_entity**)get_entity_link(ent);
Michael Beck's avatar
Michael Beck committed
224
225
226
227
	if (arr) {
		return arr;
	} else {
		/* "NULL" zeigt an, dass keine Implementierung existiert. Dies
yb9976's avatar
yb9976 committed
228
		 * kann f�r polymorphe (abstrakte) Methoden passieren. */
Michael Beck's avatar
Michael Beck committed
229
230
231
232
233
		if (!NULL_ARRAY) {
			NULL_ARRAY = NEW_ARR_F(ir_entity *, 0);
		}
		return NULL_ARRAY;
	}
234
235
}

236
237
/**
 * Returns the number of possible called methods at a Sel node.
238
239
 *
 * @param sel  the Sel node
240
 */
241
static size_t get_Sel_n_methods(ir_node * sel)
Matthias Braun's avatar
Matthias Braun committed
242
{
Michael Beck's avatar
Michael Beck committed
243
	return ARR_LEN(get_Sel_arr(sel));
244
245
}

246
247
248
/**
 * Returns the ith possible called method entity at a Sel node.
 */
249
static ir_entity * get_Sel_method(ir_node * sel, size_t pos)
Matthias Braun's avatar
Matthias Braun committed
250
{
Michael Beck's avatar
Michael Beck committed
251
	ir_entity ** arr = get_Sel_arr(sel);
252
	assert(pos < ARR_LEN(arr));
Michael Beck's avatar
Michael Beck committed
253
	return arr[pos];
254
255
}

Michael Beck's avatar
Michael Beck committed
256
/* forward */
Matthias Braun's avatar
Matthias Braun committed
257
static void free_mark(ir_node *node, pset *set);
258

Matthias Braun's avatar
Matthias Braun committed
259
static void free_mark_proj(ir_node *node, long n, pset *set)
Matthias Braun's avatar
Matthias Braun committed
260
{
Michael Beck's avatar
Michael Beck committed
261
262
263
264
265
266
267
268
269
270
271
272
	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);
273
		if (get_irn_link(pred) != MARK && is_Tuple(pred)) {
Michael Beck's avatar
Michael Beck committed
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
			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;
	}
300
	// set_irn_link(node, NULL);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
301
302
}

303
/**
Michael Beck's avatar
Michael Beck committed
304
305
306
307
308
309
310
 * 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
 *
311
312
313
 * @param node  the current visited node
 * @param set   the set of all free methods
 */
Matthias Braun's avatar
Matthias Braun committed
314
static void free_mark(ir_node *node, pset *set)
Matthias Braun's avatar
Matthias Braun committed
315
{
Michael Beck's avatar
Michael Beck committed
316
317
318
319
320
321
322
	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
323
324
		ir_entity *ent = get_Sel_entity(node);
		if (is_method_entity(ent)) {
325
			size_t i, n;
326
			for (i = 0, n = get_Sel_n_methods(node); i < n; ++i) {
Matthias Braun's avatar
Matthias Braun committed
327
				pset_insert_ptr(set, get_Sel_method(node, i));
Michael Beck's avatar
Michael Beck committed
328
329
330
			}
		}
		break;
Michael Beck's avatar
Michael Beck committed
331
	}
Michael Beck's avatar
Michael Beck committed
332
333
	case iro_SymConst:
		if (get_SymConst_kind(node) == symconst_addr_ent) {
Michael Beck's avatar
Michael Beck committed
334
335
			ir_entity *ent = get_SymConst_entity(node);
			if (is_method_entity(ent)) {
Matthias Braun's avatar
Matthias Braun committed
336
				pset_insert_ptr(set, ent);
Michael Beck's avatar
Michael Beck committed
337
338
339
340
341
			}
		}
		break;

	case iro_Phi:
342
343
344
	{
		int i, n;
		for (i = 0, n = get_Phi_n_preds(node); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
345
346
347
			free_mark(get_Phi_pred(node, i), set);
		}
		break;
348
	}
Michael Beck's avatar
Michael Beck committed
349
350
351
352
	case iro_Proj:
		free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
		break;
	default:
Michael Beck's avatar
Michael Beck committed
353
		/* nothing: */
Michael Beck's avatar
Michael Beck committed
354
355
		break;
	}
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
356
}
357

358
/**
Michael Beck's avatar
Michael Beck committed
359
 * post-walker. Find method addresses.
360
 */
Matthias Braun's avatar
Matthias Braun committed
361
362
static void free_ana_walker(ir_node *node, void *env)
{
Matthias Braun's avatar
Matthias Braun committed
363
	pset *set = (pset*) env;
Michael Beck's avatar
Michael Beck committed
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380

	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
381
382
	{
		size_t i, n;
Michael Beck's avatar
Michael Beck committed
383
384
		/* we must handle Call nodes specially, because their call address input
		   do not expose a method address. */
Michael Beck's avatar
Michael Beck committed
385
		set_irn_link(node, MARK);
Michael Beck's avatar
Michael Beck committed
386
		for (i = 0, n = get_Call_n_params(node); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
387
388
389
390
391
392
			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
393
	}
394
395
	default: {
		int i;
yb9976's avatar
yb9976 committed
396
		/* other nodes: Alle anderen Knoten nehmen wir als Verr�ter an, bis
Michael Beck's avatar
Michael Beck committed
397
398
399
		 * 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
400
			ir_node *pred = get_irn_n(node, i);
Michael Beck's avatar
Michael Beck committed
401
402
403
404
405
406
			if (mode_is_reference(get_irn_mode(pred))) {
				free_mark(pred, set);
			}
		}
		break;
	}
407
	}
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
408
409
}

410
411
412
413
/**
 * Add all method addresses in global new style initializers to the set.
 *
 * @note
414
 * We do NOT check the type here, just if it's an entity address.
415
416
417
418
419
420
 * The reason for this is code like:
 *
 * void *p = function;
 *
 * which is sometimes used to anchor functions.
 */
421
static void add_method_address_inititializer(ir_initializer_t *initializer,
Matthias Braun's avatar
Matthias Braun committed
422
                                             pset *set)
423
{
424
425
426
	ir_node *n;
	size_t  i;

427
	switch (initializer->kind) {
428
429
	case IR_INITIALIZER_CONST:
		n = initializer->consti.value;
430
431

		/* let's check if it's the address of a function */
432
433
		if (is_SymConst_addr_ent(n)) {
			ir_entity *ent = get_SymConst_entity(n);
434
435

			if (is_Method_type(get_entity_type(ent)))
Matthias Braun's avatar
Matthias Braun committed
436
				pset_insert_ptr(set, ent);
437
438
439
440
441
		}
		return;
	case IR_INITIALIZER_TARVAL:
	case IR_INITIALIZER_NULL:
		return;
442
	case IR_INITIALIZER_COMPOUND:
443
		for (i = 0; i < initializer->compound.n_initializers; ++i) {
444
445
			ir_initializer_t *sub_initializer
				= initializer->compound.initializers[i];
446
			add_method_address_inititializer(sub_initializer, set);
447
448
449
450
451
452
		}
		return;
	}
	panic("invalid initializer found");
}

453
454
/**
 * Add all method addresses in global initializers to the set.
455
456
 *
 * @note
457
 * We do NOT check the type here, just if it's an entity address.
458
459
460
461
462
 * The reason for this is code like:
 *
 * void *p = function;
 *
 * which is sometimes used to anchor functions.
463
 */
Matthias Braun's avatar
Matthias Braun committed
464
static void add_method_address(ir_entity *ent, pset *set)
465
{
Michael Beck's avatar
Michael Beck committed
466
467
	ir_type *tp;

468
	/* ignore methods: these of course reference their addresses
Michael Beck's avatar
Michael Beck committed
469
	 * TODO: remove this later once this incorrect self-initialisation is gone
Matthias Braun's avatar
Matthias Braun committed
470
471
472
	 */
	tp = get_entity_type(ent);
	if (is_Method_type(tp))
Michael Beck's avatar
Michael Beck committed
473
474
		return;

Matthias Braun's avatar
Matthias Braun committed
475
	if (ent->initializer != NULL) {
476
		add_method_address_inititializer(get_entity_initializer(ent), set);
Michael Beck's avatar
Michael Beck committed
477
	}
478
479
}

Michael Beck's avatar
Michael Beck committed
480
481
482
483
/**
 * 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
484
 * Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
485
 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
Matthias Braun's avatar
Matthias Braun committed
486
 * SymConst(name)-Operationen müssen in passende SymConst(ent)-Operationen
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
487
 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
Michael Beck's avatar
Michael Beck committed
488
489
 * auf eine echt externe Methode.
 */
490
static size_t get_free_methods(ir_entity ***free_methods)
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
491
{
Matthias Braun's avatar
Matthias Braun committed
492
	pset *free_set = pset_new_ptr_default();
Michael Beck's avatar
Michael Beck committed
493
	size_t i, n, j, m;
Michael Beck's avatar
Michael Beck committed
494
	ir_entity **arr;
Michael Beck's avatar
Michael Beck committed
495
	ir_graph *irg;
Michael Beck's avatar
Michael Beck committed
496
	ir_type *tp;
497
	size_t length;
Michael Beck's avatar
Michael Beck committed
498

Michael Beck's avatar
Michael Beck committed
499
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
Matthias Braun's avatar
Matthias Braun committed
500
		ir_linkage linkage;
Michael Beck's avatar
Michael Beck committed
501
		irg = get_irp_irg(i);
502
		ir_entity *const ent = get_irg_entity(irg);
Matthias Braun's avatar
Matthias Braun committed
503
504
		linkage = get_entity_linkage(ent);

Michael Beck's avatar
Michael Beck committed
505
		if ((linkage & IR_LINKAGE_HIDDEN_USER) || entity_is_externally_visible(ent)) {
Matthias Braun's avatar
Matthias Braun committed
506
			pset_insert_ptr(free_set, ent);
Michael Beck's avatar
Michael Beck committed
507
		}
Michael Beck's avatar
Michael Beck committed
508

509
		ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
510
		/* Find all method entities that gets "visible" through this graphs,
Michael Beck's avatar
Michael Beck committed
511
		 * for instance because their address is stored. */
512
		irg_walk_graph(irg, firm_clear_link, free_ana_walker, free_set);
513
		ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
Michael Beck's avatar
Michael Beck committed
514
515
	}

Michael Beck's avatar
Michael Beck committed
516
	/* insert all methods that are used in global variables initializers */
Michael Beck's avatar
Michael Beck committed
517
	tp = get_glob_type();
Michael Beck's avatar
Michael Beck committed
518
	for (j = 0, m = get_class_n_members(tp); j < m; ++j) {
519
		ir_entity *const ent = get_class_member(tp, j);
Michael Beck's avatar
Michael Beck committed
520
521
522
		add_method_address(ent, free_set);
	}
	tp = get_tls_type();
523
	for (j = 0, m = get_compound_n_members(tp); j < m; ++j) {
524
		ir_entity *const ent = get_compound_member(tp, j);
Michael Beck's avatar
Michael Beck committed
525
526
527
528
529
		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
530
	if (irg != NULL)
Matthias Braun's avatar
Matthias Braun committed
531
		pset_insert_ptr(free_set, get_irg_entity(irg));
Michael Beck's avatar
Michael Beck committed
532
533

	/* Finally, transform the set into an array. */
Matthias Braun's avatar
Matthias Braun committed
534
	length = pset_count(free_set);
535
	arr = XMALLOCN(ir_entity*, length);
Matthias Braun's avatar
Matthias Braun committed
536
	i = 0;
537
	foreach_pset(free_set, ir_entity, ent) {
Michael Beck's avatar
Michael Beck committed
538
		arr[i++] = ent;
Michael Beck's avatar
Michael Beck committed
539
	}
Matthias Braun's avatar
Matthias Braun committed
540
	del_pset(free_set);
Michael Beck's avatar
Michael Beck committed
541

542
543
	*free_methods = arr;
	return length;
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
544
545
546
547
548
549
}

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

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

Matthias Braun's avatar
Matthias Braun committed
552
static void callee_ana_proj(ir_node *node, long n, pset *methods)
Matthias Braun's avatar
Matthias Braun committed
553
{
Michael Beck's avatar
Michael Beck committed
554
555
556
557
558
559
560
561
562
563
564
	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
565
		 * zur�ckgibt. */
Michael Beck's avatar
Michael Beck committed
566
		ir_node *pred = get_Proj_pred(node);
Michael Beck's avatar
Michael Beck committed
567
		if (get_irn_link(pred) != MARK) {
Michael Beck's avatar
Michael Beck committed
568
			if (is_Tuple(pred)) {
Michael Beck's avatar
Michael Beck committed
569
570
				callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
			} else {
571
				pset_insert_ptr(methods, get_unknown_entity()); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
572
573
574
			}
		}
		break;
Michael Beck's avatar
Michael Beck committed
575
	}
Michael Beck's avatar
Michael Beck committed
576
577
578
579
580
581

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

	default:
582
		pset_insert_ptr(methods, get_unknown_entity()); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
583
584
		break;
	}
585
586
}

Michael Beck's avatar
Michael Beck committed
587
/**
Michael Beck's avatar
Michael Beck committed
588
 * Analyse a Call address.
Michael Beck's avatar
Michael Beck committed
589
 *
Michael Beck's avatar
Michael Beck committed
590
591
 * @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
592
 */
Matthias Braun's avatar
Matthias Braun committed
593
static void callee_ana_node(ir_node *node, pset *methods)
Matthias Braun's avatar
Matthias Braun committed
594
{
Michael Beck's avatar
Michael Beck committed
595
596
597
598
599
600
601
602
603
604
	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:
605
		/* A direct address call. We treat this as an external
Michael Beck's avatar
Michael Beck committed
606
		   call and ignore it completely. */
607
		pset_insert_ptr(methods, get_unknown_entity()); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
608
		break;
609
610
611
612

	case iro_SymConst: {
		ir_entity *ent = get_SymConst_entity(node);
		assert(ent && is_method_entity(ent));
Matthias Braun's avatar
Matthias Braun committed
613
		pset_insert_ptr(methods, ent);
Michael Beck's avatar
Michael Beck committed
614
		break;
615
616
	}

617
	case iro_Sel: {
Michael Beck's avatar
Michael Beck committed
618
		/* polymorphic method */
619
620
		size_t i, n;
		for (i = 0, n = get_Sel_n_methods(node); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
621
622
			ir_entity *ent = get_Sel_method(node, i);
			if (ent != NULL) {
Matthias Braun's avatar
Matthias Braun committed
623
				pset_insert_ptr(methods, ent);
Michael Beck's avatar
Michael Beck committed
624
			} else {
625
				pset_insert_ptr(methods, get_unknown_entity());
Michael Beck's avatar
Michael Beck committed
626
627
628
			}
		}
		break;
629
	}
Michael Beck's avatar
Michael Beck committed
630
631
632
633
634

	case iro_Bad:
		/* nothing */
		break;

635
636
	case iro_Phi: {
		int i;
Michael Beck's avatar
Michael Beck committed
637
638
639
640
		for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
			callee_ana_node(get_Phi_pred(node, i), methods);
		}
		break;
641
	}
Michael Beck's avatar
Michael Beck committed
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659

	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 */
660
		pset_insert_ptr(methods, get_unknown_entity()); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
661
662
663
664
665
666
		break;

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

Michael Beck's avatar
Michael Beck committed
669
/**
Michael Beck's avatar
Michael Beck committed
670
 * Walker: Analyses every Call node and calculates an array of possible
Michael Beck's avatar
Michael Beck committed
671
672
 * callees for that call.
 */
Matthias Braun's avatar
Matthias Braun committed
673
674
static void callee_walker(ir_node *call, void *env)
{
Michael Beck's avatar
Michael Beck committed
675
676
	(void) env;
	if (is_Call(call)) {
Matthias Braun's avatar
Matthias Braun committed
677
		pset *methods = pset_new_ptr_default();
Michael Beck's avatar
Michael Beck committed
678
		ir_entity **arr;
679
		size_t i;
Michael Beck's avatar
Michael Beck committed
680

Michael Beck's avatar
Michael Beck committed
681
		callee_ana_node(get_Call_ptr(call), methods);
Matthias Braun's avatar
Matthias Braun committed
682
683
		arr = NEW_ARR_F(ir_entity*, pset_count(methods));
		i = 0;
684
		foreach_pset(methods, ir_entity, ent) {
Michael Beck's avatar
Michael Beck committed
685
686
			arr[i] = ent;
			/* we want the unknown_entity on the zero position for easy tests later */
687
			if (is_unknown_entity(ent)) {
Michael Beck's avatar
Michael Beck committed
688
				arr[i] = arr[0];
689
				arr[0] = get_unknown_entity();
Michael Beck's avatar
Michael Beck committed
690
			}
Michael Beck's avatar
Michael Beck committed
691
			++i;
Michael Beck's avatar
Michael Beck committed
692
		}
Michael Beck's avatar
Michael Beck committed
693
		set_Call_callee_arr(call, ARR_LEN(arr), arr);
Michael Beck's avatar
Michael Beck committed
694
		DEL_ARR_F(arr);
Matthias Braun's avatar
Matthias Braun committed
695
		del_pset(methods);
Michael Beck's avatar
Michael Beck committed
696
	}
697
698
}

Michael Beck's avatar
Michael Beck committed
699
700
701
/**
 * Walker: Removes all tuple.
 */
Matthias Braun's avatar
Matthias Braun committed
702
703
static void remove_Tuples(ir_node *proj, void *env)
{
Michael Beck's avatar
Michael Beck committed
704
705
706
	ir_node *nn;
	(void) env;
	if (! is_Proj(proj)) return;
707

Michael Beck's avatar
Michael Beck committed
708
709
	nn = skip_Tuple(proj);
	if (nn != proj) exchange(proj, nn);
710
711
712
}


Michael Beck's avatar
Michael Beck committed
713
714
715
716
717
/**
 * 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
718
719
static void callee_ana(void)
{
Michael Beck's avatar
Michael Beck committed
720
	size_t i, n;
Michael Beck's avatar
Michael Beck committed
721
	/* analyse all graphs */
Michael Beck's avatar
Michael Beck committed
722
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
723
724
725
726
727
		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);
728
729
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
730
731
732
/*--------------------------------------------------------------------------*/
/* Cleanup after analyses.                                                  */
/*--------------------------------------------------------------------------*/
733

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
734
/** Frees intermediate data structures. */
Matthias Braun's avatar
Matthias Braun committed
735
736
static void sel_methods_dispose(void)
{
Michael Beck's avatar
Michael Beck committed
737
	assert(entities);
738
	foreach_pset(entities, ir_entity, ent) {
Matthias Braun's avatar
Matthias Braun committed
739
740
		ir_entity **arr = (ir_entity**) get_entity_link(ent);
		if (arr != NULL) {
Michael Beck's avatar
Michael Beck committed
741
742
743
744
			DEL_ARR_F(arr);
		}
		set_entity_link(ent, NULL);
	}
Matthias Braun's avatar
Matthias Braun committed
745
	del_pset(entities);
Michael Beck's avatar
Michael Beck committed
746
	entities = NULL;
747
748
}

Matthias Braun's avatar
Matthias Braun committed
749
750
static void destruct_walker(ir_node * node, void * env)
{
Michael Beck's avatar
Michael Beck committed
751
752
753
754
	(void) env;
	if (is_Call(node)) {
		remove_Call_callee_arr(node);
	}
755
756
}

757
size_t cgana(ir_entity ***free_methods)
Matthias Braun's avatar
Matthias Braun committed
758
{
759
	size_t length;
Michael Beck's avatar
Michael Beck committed
760
761
	/* Optimize Sel/SymConst nodes and compute all methods that implement an entity. */
	sel_methods_init();
762
	length = get_free_methods(free_methods);
Michael Beck's avatar
Michael Beck committed
763
764
	callee_ana();
	sel_methods_dispose();
765
	return length;
766
}
767

Matthias Braun's avatar
Matthias Braun committed
768
769
void free_callee_info(ir_graph *irg)
{
Michael Beck's avatar
Michael Beck committed
770
771
	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
772
773
}

Matthias Braun's avatar
Matthias Braun committed
774
775
void free_irp_callee_info(void)
{
Michael Beck's avatar
Michael Beck committed
776
777
	size_t i, n;
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
778
779
		free_callee_info(get_irp_irg(i));
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
780
781
}

Matthias Braun's avatar
Matthias Braun committed
782
783
void opt_call_addrs(void)
{
784
785
786
787
788
789
790
791
792
793
794
795
796
797
	/* 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
798
799
	sel_methods_init();
	sel_methods_dispose();
800
}