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

Matthias Braun's avatar
Matthias Braun committed
21
#include <string.h>
22
23
24

#include "cgana.h"

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

Götz Lindenmaier's avatar
Götz Lindenmaier committed
35
#include "irflag_t.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
36
#include "dbginfo_t.h"
Michael Beck's avatar
Michael Beck committed
37
#include "iropt_dbg.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
38

Götz Lindenmaier's avatar
Götz Lindenmaier committed
39
40
#include "pmap.h"
#include "array.h"
41
#include "error.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
42

43
44
#include "irdump.h"

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

Matthias Braun's avatar
Matthias Braun committed
48
static pset *entities = NULL;
49

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
50
51
52
/*--------------------------------------------------------------------------*/
/* The analysis                                                             */
/*--------------------------------------------------------------------------*/
53
54


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

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

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

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

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

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

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

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

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

151
	if (is_Sel(node) && is_Method_type(get_entity_type(get_Sel_entity(node)))) {
152
153
		ir_entity *ent = get_SymConst_entity(get_atomic_ent_value(get_Sel_entity(node)));

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

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

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

202
	all_irg_walk(sel_methods_walker, NULL, NULL);
Michael Beck's avatar
Michael Beck committed
203
	pmap_destroy(ldname_map);
204
205
}

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

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

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

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

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

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

Michael Beck's avatar
Michael Beck committed
259
/* forward */
Matthias Braun's avatar
Matthias Braun committed
260
static void free_mark(ir_node *node, pset *set);
261

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

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

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

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

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

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

430
	switch (initializer->kind) {
431
432
	case IR_INITIALIZER_CONST:
		n = initializer->consti.value;
433
434

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

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

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

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

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

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

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

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

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

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

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

545
546
	*free_methods = arr;
	return length;
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
547
548
549
550
551
552
}

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

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

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

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

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

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

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

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

	case iro_Bad:
		/* nothing */
		break;

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

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

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

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

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

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

Michael Beck's avatar
Michael Beck committed
711
712
	nn = skip_Tuple(proj);
	if (nn != proj) exchange(proj, nn);
713
714
715
}


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

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
733
734
735
/*--------------------------------------------------------------------------*/
/* Cleanup after analyses.                                                  */
/*--------------------------------------------------------------------------*/
736

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

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

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

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

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

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