cgana.c 21.4 KB
Newer Older
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1
/*
2
 * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
Matthias Braun's avatar
Matthias Braun committed
3
4
 *
 * This file is part of libFirm.
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
5
 *
Matthias Braun's avatar
Matthias Braun committed
6
7
8
9
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
10
 *
Matthias Braun's avatar
Matthias Braun committed
11
12
13
14
15
16
17
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
18
 */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
19

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

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

#include "cgana.h"

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

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

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

57
58
#include "irdump.h"

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

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

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


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

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

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

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

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

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

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

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

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

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

Matthias Braun's avatar
Matthias Braun committed
168
		if (!pset_find_ptr(entities, ent)) {
169
170
171
172
			/* 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
173
			pset_insert_ptr(entities, ent);
174
		}
Michael Beck's avatar
Michael Beck committed
175

176
177
		/* -- As an add on we get an optimization that removes polymorphic calls.
		This optimization is more powerful than that in transform_node_Sel().  -- */
178
		arr = (ir_entity**) get_entity_link(ent);
179
180
181
182
183
184
		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
185
			assert(get_entity_irg(ent) == NULL);
186
		}
Michael Beck's avatar
Michael Beck committed
187
	}
188
189
}

Michael Beck's avatar
Michael Beck committed
190
191
/**
 * Initialize auxiliary data structures.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
192
 *
Michael Beck's avatar
Michael Beck committed
193
194
 * 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
195
 *
Michael Beck's avatar
Michael Beck committed
196
197
198
199
200
 * 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
201
202
static void sel_methods_init(void)
{
Michael Beck's avatar
Michael Beck committed
203
	size_t i, n;
Michael Beck's avatar
Michael Beck committed
204
205
	pmap *ldname_map = pmap_create();   /* Map entity names to entities: to replace
	                                       SymConst(name) by SymConst(ent). */
Michael Beck's avatar
Michael Beck committed
206
	assert(entities == NULL);
Matthias Braun's avatar
Matthias Braun committed
207
	entities = pset_new_ptr_default();
Michael Beck's avatar
Michael Beck committed
208
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
209
210
		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
211
		if (entity_is_externally_visible(ent)) {
Michael Beck's avatar
Michael Beck committed
212
			pmap_insert(ldname_map, (void *)get_entity_ld_ident(ent), ent);
Michael Beck's avatar
Michael Beck committed
213
214
215
		}
	}

216
	all_irg_walk(sel_methods_walker, NULL, NULL);
Michael Beck's avatar
Michael Beck committed
217
	pmap_destroy(ldname_map);
218
219
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
220
221
222
223
224
225
/*--------------------------------------------------------------------------*/
/* Find free methods.
 *
 * We expect that each entity has an array with all implementations in its
 * link field.                                                              */
/*--------------------------------------------------------------------------*/
226

227
228
229
/**
 * Returns an array of all methods that could be called at a Sel node.
 * This array contains every entry only once.
230
231
 *
 * @param sel  the Sel node
232
 */
Matthias Braun's avatar
Matthias Braun committed
233
234
static ir_entity ** get_Sel_arr(ir_node * sel)
{
Michael Beck's avatar
Michael Beck committed
235
236
	static ir_entity ** NULL_ARRAY = NULL;

237
	ir_entity *const ent = get_Sel_entity(sel);
Michael Beck's avatar
Michael Beck committed
238
	assert(is_Method_type(get_entity_type(ent))); /* what else? */
239
240

	ir_entity **const arr = (ir_entity**)get_entity_link(ent);
Michael Beck's avatar
Michael Beck committed
241
242
243
244
	if (arr) {
		return arr;
	} else {
		/* "NULL" zeigt an, dass keine Implementierung existiert. Dies
yb9976's avatar
yb9976 committed
245
		 * kann f�r polymorphe (abstrakte) Methoden passieren. */
Michael Beck's avatar
Michael Beck committed
246
247
248
249
250
		if (!NULL_ARRAY) {
			NULL_ARRAY = NEW_ARR_F(ir_entity *, 0);
		}
		return NULL_ARRAY;
	}
251
252
}

253
254
/**
 * Returns the number of possible called methods at a Sel node.
255
256
 *
 * @param sel  the Sel node
257
 */
258
static size_t get_Sel_n_methods(ir_node * sel)
Matthias Braun's avatar
Matthias Braun committed
259
{
Michael Beck's avatar
Michael Beck committed
260
	return ARR_LEN(get_Sel_arr(sel));
261
262
}

263
264
265
/**
 * Returns the ith possible called method entity at a Sel node.
 */
266
static ir_entity * get_Sel_method(ir_node * sel, size_t pos)
Matthias Braun's avatar
Matthias Braun committed
267
{
Michael Beck's avatar
Michael Beck committed
268
	ir_entity ** arr = get_Sel_arr(sel);
269
	assert(pos < ARR_LEN(arr));
Michael Beck's avatar
Michael Beck committed
270
	return arr[pos];
271
272
}

Michael Beck's avatar
Michael Beck committed
273
/* forward */
Matthias Braun's avatar
Matthias Braun committed
274
static void free_mark(ir_node *node, pset *set);
275

Matthias Braun's avatar
Matthias Braun committed
276
static void free_mark_proj(ir_node *node, long n, pset *set)
Matthias Braun's avatar
Matthias Braun committed
277
{
Michael Beck's avatar
Michael Beck committed
278
279
280
281
282
283
284
285
286
287
288
289
	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);
290
		if (get_irn_link(pred) != MARK && is_Tuple(pred)) {
Michael Beck's avatar
Michael Beck committed
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
			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;
	}
317
	// set_irn_link(node, NULL);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
318
319
}

320
/**
Michael Beck's avatar
Michael Beck committed
321
322
323
324
325
326
327
 * 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
 *
328
329
330
 * @param node  the current visited node
 * @param set   the set of all free methods
 */
Matthias Braun's avatar
Matthias Braun committed
331
static void free_mark(ir_node *node, pset *set)
Matthias Braun's avatar
Matthias Braun committed
332
{
Michael Beck's avatar
Michael Beck committed
333
334
335
336
337
338
339
	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
340
341
		ir_entity *ent = get_Sel_entity(node);
		if (is_method_entity(ent)) {
342
			size_t i, n;
343
			for (i = 0, n = get_Sel_n_methods(node); i < n; ++i) {
Matthias Braun's avatar
Matthias Braun committed
344
				pset_insert_ptr(set, get_Sel_method(node, i));
Michael Beck's avatar
Michael Beck committed
345
346
347
			}
		}
		break;
Michael Beck's avatar
Michael Beck committed
348
	}
Michael Beck's avatar
Michael Beck committed
349
350
	case iro_SymConst:
		if (get_SymConst_kind(node) == symconst_addr_ent) {
Michael Beck's avatar
Michael Beck committed
351
352
			ir_entity *ent = get_SymConst_entity(node);
			if (is_method_entity(ent)) {
Matthias Braun's avatar
Matthias Braun committed
353
				pset_insert_ptr(set, ent);
Michael Beck's avatar
Michael Beck committed
354
355
356
357
358
			}
		}
		break;

	case iro_Phi:
359
360
361
	{
		int i, n;
		for (i = 0, n = get_Phi_n_preds(node); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
362
363
364
			free_mark(get_Phi_pred(node, i), set);
		}
		break;
365
	}
Michael Beck's avatar
Michael Beck committed
366
367
368
369
	case iro_Proj:
		free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
		break;
	default:
Michael Beck's avatar
Michael Beck committed
370
		/* nothing: */
Michael Beck's avatar
Michael Beck committed
371
372
		break;
	}
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
373
}
374

375
/**
Michael Beck's avatar
Michael Beck committed
376
 * post-walker. Find method addresses.
377
 */
Matthias Braun's avatar
Matthias Braun committed
378
379
static void free_ana_walker(ir_node *node, void *env)
{
Matthias Braun's avatar
Matthias Braun committed
380
	pset *set = (pset*) env;
Michael Beck's avatar
Michael Beck committed
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397

	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
398
399
	{
		size_t i, n;
Michael Beck's avatar
Michael Beck committed
400
401
		/* we must handle Call nodes specially, because their call address input
		   do not expose a method address. */
Michael Beck's avatar
Michael Beck committed
402
		set_irn_link(node, MARK);
Michael Beck's avatar
Michael Beck committed
403
		for (i = 0, n = get_Call_n_params(node); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
404
405
406
407
408
409
			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
410
	}
411
412
	default: {
		int i;
yb9976's avatar
yb9976 committed
413
		/* other nodes: Alle anderen Knoten nehmen wir als Verr�ter an, bis
Michael Beck's avatar
Michael Beck committed
414
415
416
		 * 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
417
			ir_node *pred = get_irn_n(node, i);
Michael Beck's avatar
Michael Beck committed
418
419
420
421
422
423
			if (mode_is_reference(get_irn_mode(pred))) {
				free_mark(pred, set);
			}
		}
		break;
	}
424
	}
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
425
426
}

427
428
429
430
/**
 * Add all method addresses in global new style initializers to the set.
 *
 * @note
431
 * We do NOT check the type here, just if it's an entity address.
432
433
434
435
436
437
 * The reason for this is code like:
 *
 * void *p = function;
 *
 * which is sometimes used to anchor functions.
 */
438
static void add_method_address_inititializer(ir_initializer_t *initializer,
Matthias Braun's avatar
Matthias Braun committed
439
                                             pset *set)
440
{
441
442
443
	ir_node *n;
	size_t  i;

444
	switch (initializer->kind) {
445
446
	case IR_INITIALIZER_CONST:
		n = initializer->consti.value;
447
448

		/* let's check if it's the address of a function */
449
450
		if (is_SymConst_addr_ent(n)) {
			ir_entity *ent = get_SymConst_entity(n);
451
452

			if (is_Method_type(get_entity_type(ent)))
Matthias Braun's avatar
Matthias Braun committed
453
				pset_insert_ptr(set, ent);
454
455
456
457
458
		}
		return;
	case IR_INITIALIZER_TARVAL:
	case IR_INITIALIZER_NULL:
		return;
459
	case IR_INITIALIZER_COMPOUND:
460
		for (i = 0; i < initializer->compound.n_initializers; ++i) {
461
462
			ir_initializer_t *sub_initializer
				= initializer->compound.initializers[i];
463
			add_method_address_inititializer(sub_initializer, set);
464
465
466
467
468
469
		}
		return;
	}
	panic("invalid initializer found");
}

470
471
/**
 * Add all method addresses in global initializers to the set.
472
473
 *
 * @note
474
 * We do NOT check the type here, just if it's an entity address.
475
476
477
478
479
 * The reason for this is code like:
 *
 * void *p = function;
 *
 * which is sometimes used to anchor functions.
480
 */
Matthias Braun's avatar
Matthias Braun committed
481
static void add_method_address(ir_entity *ent, pset *set)
482
{
Michael Beck's avatar
Michael Beck committed
483
484
	ir_type *tp;

485
	/* ignore methods: these of course reference their addresses
Michael Beck's avatar
Michael Beck committed
486
	 * TODO: remove this later once this incorrect self-initialisation is gone
Matthias Braun's avatar
Matthias Braun committed
487
488
489
	 */
	tp = get_entity_type(ent);
	if (is_Method_type(tp))
Michael Beck's avatar
Michael Beck committed
490
491
		return;

Matthias Braun's avatar
Matthias Braun committed
492
	if (ent->initializer != NULL) {
493
		add_method_address_inititializer(get_entity_initializer(ent), set);
Michael Beck's avatar
Michael Beck committed
494
	}
495
496
}

Michael Beck's avatar
Michael Beck committed
497
498
499
500
/**
 * 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
501
 * Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
502
 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
Matthias Braun's avatar
Matthias Braun committed
503
 * SymConst(name)-Operationen müssen in passende SymConst(ent)-Operationen
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
504
 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
Michael Beck's avatar
Michael Beck committed
505
506
 * auf eine echt externe Methode.
 */
507
static size_t get_free_methods(ir_entity ***free_methods)
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
508
{
Matthias Braun's avatar
Matthias Braun committed
509
	pset *free_set = pset_new_ptr_default();
Michael Beck's avatar
Michael Beck committed
510
	size_t i, n, j, m;
Michael Beck's avatar
Michael Beck committed
511
	ir_entity **arr;
Michael Beck's avatar
Michael Beck committed
512
	ir_graph *irg;
Michael Beck's avatar
Michael Beck committed
513
	ir_type *tp;
514
	size_t length;
Michael Beck's avatar
Michael Beck committed
515

Michael Beck's avatar
Michael Beck committed
516
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
Matthias Braun's avatar
Matthias Braun committed
517
		ir_linkage linkage;
Michael Beck's avatar
Michael Beck committed
518
		irg = get_irp_irg(i);
519
		ir_entity *const ent = get_irg_entity(irg);
Matthias Braun's avatar
Matthias Braun committed
520
521
		linkage = get_entity_linkage(ent);

Michael Beck's avatar
Michael Beck committed
522
		if ((linkage & IR_LINKAGE_HIDDEN_USER) || entity_is_externally_visible(ent)) {
Matthias Braun's avatar
Matthias Braun committed
523
			pset_insert_ptr(free_set, ent);
Michael Beck's avatar
Michael Beck committed
524
		}
Michael Beck's avatar
Michael Beck committed
525

526
		ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
527
		/* Find all method entities that gets "visible" through this graphs,
Michael Beck's avatar
Michael Beck committed
528
		 * for instance because their address is stored. */
529
		irg_walk_graph(irg, firm_clear_link, free_ana_walker, free_set);
530
		ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
Michael Beck's avatar
Michael Beck committed
531
532
	}

Michael Beck's avatar
Michael Beck committed
533
	/* insert all methods that are used in global variables initializers */
Michael Beck's avatar
Michael Beck committed
534
	tp = get_glob_type();
Michael Beck's avatar
Michael Beck committed
535
	for (j = 0, m = get_class_n_members(tp); j < m; ++j) {
536
		ir_entity *const ent = get_class_member(tp, j);
Michael Beck's avatar
Michael Beck committed
537
538
539
		add_method_address(ent, free_set);
	}
	tp = get_tls_type();
540
	for (j = 0, m = get_compound_n_members(tp); j < m; ++j) {
541
		ir_entity *const ent = get_compound_member(tp, j);
Michael Beck's avatar
Michael Beck committed
542
543
544
545
546
		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
547
	if (irg != NULL)
Matthias Braun's avatar
Matthias Braun committed
548
		pset_insert_ptr(free_set, get_irg_entity(irg));
Michael Beck's avatar
Michael Beck committed
549
550

	/* Finally, transform the set into an array. */
Matthias Braun's avatar
Matthias Braun committed
551
	length = pset_count(free_set);
552
	arr = XMALLOCN(ir_entity*, length);
Matthias Braun's avatar
Matthias Braun committed
553
	i = 0;
554
	foreach_pset(free_set, ir_entity, ent) {
Michael Beck's avatar
Michael Beck committed
555
		arr[i++] = ent;
Michael Beck's avatar
Michael Beck committed
556
	}
Matthias Braun's avatar
Matthias Braun committed
557
	del_pset(free_set);
Michael Beck's avatar
Michael Beck committed
558

559
560
	*free_methods = arr;
	return length;
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
561
562
563
564
565
566
}

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

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

Matthias Braun's avatar
Matthias Braun committed
569
static void callee_ana_proj(ir_node *node, long n, pset *methods)
Matthias Braun's avatar
Matthias Braun committed
570
{
Michael Beck's avatar
Michael Beck committed
571
572
573
574
575
576
577
578
579
580
581
	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
582
		 * zur�ckgibt. */
Michael Beck's avatar
Michael Beck committed
583
		ir_node *pred = get_Proj_pred(node);
Michael Beck's avatar
Michael Beck committed
584
		if (get_irn_link(pred) != MARK) {
Michael Beck's avatar
Michael Beck committed
585
			if (is_Tuple(pred)) {
Michael Beck's avatar
Michael Beck committed
586
587
				callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
			} else {
588
				pset_insert_ptr(methods, get_unknown_entity()); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
589
590
591
			}
		}
		break;
Michael Beck's avatar
Michael Beck committed
592
	}
Michael Beck's avatar
Michael Beck committed
593
594
595
596
597
598

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

	default:
599
		pset_insert_ptr(methods, get_unknown_entity()); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
600
601
		break;
	}
602
603
}

Michael Beck's avatar
Michael Beck committed
604
/**
Michael Beck's avatar
Michael Beck committed
605
 * Analyse a Call address.
Michael Beck's avatar
Michael Beck committed
606
 *
Michael Beck's avatar
Michael Beck committed
607
608
 * @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
609
 */
Matthias Braun's avatar
Matthias Braun committed
610
static void callee_ana_node(ir_node *node, pset *methods)
Matthias Braun's avatar
Matthias Braun committed
611
{
Michael Beck's avatar
Michael Beck committed
612
613
614
615
616
617
618
619
620
621
622
	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
623
		   call and ignore it completely. */
624
		pset_insert_ptr(methods, get_unknown_entity()); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
625
		break;
626
627
628
629

	case iro_SymConst: {
		ir_entity *ent = get_SymConst_entity(node);
		assert(ent && is_method_entity(ent));
Matthias Braun's avatar
Matthias Braun committed
630
		pset_insert_ptr(methods, ent);
Michael Beck's avatar
Michael Beck committed
631
		break;
632
633
	}

634
	case iro_Sel: {
Michael Beck's avatar
Michael Beck committed
635
		/* polymorphic method */
636
637
		size_t i, n;
		for (i = 0, n = get_Sel_n_methods(node); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
638
639
			ir_entity *ent = get_Sel_method(node, i);
			if (ent != NULL) {
Matthias Braun's avatar
Matthias Braun committed
640
				pset_insert_ptr(methods, ent);
Michael Beck's avatar
Michael Beck committed
641
			} else {
642
				pset_insert_ptr(methods, get_unknown_entity());
Michael Beck's avatar
Michael Beck committed
643
644
645
			}
		}
		break;
646
	}
Michael Beck's avatar
Michael Beck committed
647
648
649
650
651

	case iro_Bad:
		/* nothing */
		break;

652
653
	case iro_Phi: {
		int i;
Michael Beck's avatar
Michael Beck committed
654
655
656
657
		for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
			callee_ana_node(get_Phi_pred(node, i), methods);
		}
		break;
658
	}
Michael Beck's avatar
Michael Beck committed
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676

	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 */
677
		pset_insert_ptr(methods, get_unknown_entity()); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
678
679
680
681
682
683
		break;

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

Michael Beck's avatar
Michael Beck committed
686
/**
Michael Beck's avatar
Michael Beck committed
687
 * Walker: Analyses every Call node and calculates an array of possible
Michael Beck's avatar
Michael Beck committed
688
689
 * callees for that call.
 */
Matthias Braun's avatar
Matthias Braun committed
690
691
static void callee_walker(ir_node *call, void *env)
{
Michael Beck's avatar
Michael Beck committed
692
693
	(void) env;
	if (is_Call(call)) {
Matthias Braun's avatar
Matthias Braun committed
694
		pset *methods = pset_new_ptr_default();
Michael Beck's avatar
Michael Beck committed
695
		ir_entity **arr;
696
		size_t i;
Michael Beck's avatar
Michael Beck committed
697

Michael Beck's avatar
Michael Beck committed
698
		callee_ana_node(get_Call_ptr(call), methods);
Matthias Braun's avatar
Matthias Braun committed
699
700
		arr = NEW_ARR_F(ir_entity*, pset_count(methods));
		i = 0;
701
		foreach_pset(methods, ir_entity, ent) {
Michael Beck's avatar
Michael Beck committed
702
703
			arr[i] = ent;
			/* we want the unknown_entity on the zero position for easy tests later */
704
			if (is_unknown_entity(ent)) {
Michael Beck's avatar
Michael Beck committed
705
				arr[i] = arr[0];
706
				arr[0] = get_unknown_entity();
Michael Beck's avatar
Michael Beck committed
707
			}
Michael Beck's avatar
Michael Beck committed
708
			++i;
Michael Beck's avatar
Michael Beck committed
709
		}
Michael Beck's avatar
Michael Beck committed
710
		set_Call_callee_arr(call, ARR_LEN(arr), arr);
Michael Beck's avatar
Michael Beck committed
711
		DEL_ARR_F(arr);
Matthias Braun's avatar
Matthias Braun committed
712
		del_pset(methods);
Michael Beck's avatar
Michael Beck committed
713
	}
714
715
}

Michael Beck's avatar
Michael Beck committed
716
717
718
/**
 * Walker: Removes all tuple.
 */
Matthias Braun's avatar
Matthias Braun committed
719
720
static void remove_Tuples(ir_node *proj, void *env)
{
Michael Beck's avatar
Michael Beck committed
721
722
723
	ir_node *nn;
	(void) env;
	if (! is_Proj(proj)) return;
724

Michael Beck's avatar
Michael Beck committed
725
726
	nn = skip_Tuple(proj);
	if (nn != proj) exchange(proj, nn);
727
728
729
}


Michael Beck's avatar
Michael Beck committed
730
731
732
733
734
/**
 * 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
735
736
static void callee_ana(void)
{
Michael Beck's avatar
Michael Beck committed
737
	size_t i, n;
Michael Beck's avatar
Michael Beck committed
738
	/* analyse all graphs */
Michael Beck's avatar
Michael Beck committed
739
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
740
741
742
743
744
		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);
745
746
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
747
748
749
/*--------------------------------------------------------------------------*/
/* Cleanup after analyses.                                                  */
/*--------------------------------------------------------------------------*/
750

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
751
/** Frees intermediate data structures. */
Matthias Braun's avatar
Matthias Braun committed
752
753
static void sel_methods_dispose(void)
{
Michael Beck's avatar
Michael Beck committed
754
	assert(entities);
755
	foreach_pset(entities, ir_entity, ent) {
Matthias Braun's avatar
Matthias Braun committed
756
757
		ir_entity **arr = (ir_entity**) get_entity_link(ent);
		if (arr != NULL) {
Michael Beck's avatar
Michael Beck committed
758
759
760
761
			DEL_ARR_F(arr);
		}
		set_entity_link(ent, NULL);
	}
Matthias Braun's avatar
Matthias Braun committed
762
	del_pset(entities);
Michael Beck's avatar
Michael Beck committed
763
	entities = NULL;
764
765
}

Matthias Braun's avatar
Matthias Braun committed
766
767
static void destruct_walker(ir_node * node, void * env)
{
Michael Beck's avatar
Michael Beck committed
768
769
770
771
	(void) env;
	if (is_Call(node)) {
		remove_Call_callee_arr(node);
	}
772
773
}

774
size_t cgana(ir_entity ***free_methods)
Matthias Braun's avatar
Matthias Braun committed
775
{
776
	size_t length;
Michael Beck's avatar
Michael Beck committed
777
778
	/* Optimize Sel/SymConst nodes and compute all methods that implement an entity. */
	sel_methods_init();
779
	length = get_free_methods(free_methods);
Michael Beck's avatar
Michael Beck committed
780
781
	callee_ana();
	sel_methods_dispose();
782
	return length;
783
}
784

Matthias Braun's avatar
Matthias Braun committed
785
786
void free_callee_info(ir_graph *irg)
{
Michael Beck's avatar
Michael Beck committed
787
788
	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
789
790
}

Matthias Braun's avatar
Matthias Braun committed
791
792
void free_irp_callee_info(void)
{
Michael Beck's avatar
Michael Beck committed
793
794
	size_t i, n;
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
795
796
		free_callee_info(get_irp_irg(i));
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
797
798
}

Matthias Braun's avatar
Matthias Braun committed
799
800
void opt_call_addrs(void)
{
801
802
803
804
805
806
807
808
809
810
811
812
813
814
	/* 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
815
816
	sel_methods_init();
	sel_methods_dispose();
817
}