cgana.c 22 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
		}
Matthias Braun's avatar
Matthias Braun committed
187
#if 0
188
189
190
191
192
193
194
195
196
		else if (get_opt_closed_world() && get_opt_dyn_meth_dispatch() &&
			(ARR_LEN(arr) == 1 && arr[0] != NULL)) {
			ir_node *new_node;

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

Michael Beck's avatar
Michael Beck committed
206
207
/**
 * Initialize auxiliary data structures.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
208
 *
Michael Beck's avatar
Michael Beck committed
209
210
 * 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
211
 *
Michael Beck's avatar
Michael Beck committed
212
213
214
215
216
 * 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
217
218
static void sel_methods_init(void)
{
Michael Beck's avatar
Michael Beck committed
219
	size_t i, n;
Michael Beck's avatar
Michael Beck committed
220
221
	pmap *ldname_map = pmap_create();   /* Map entity names to entities: to replace
	                                       SymConst(name) by SymConst(ent). */
Michael Beck's avatar
Michael Beck committed
222
	assert(entities == NULL);
Matthias Braun's avatar
Matthias Braun committed
223
	entities = pset_new_ptr_default();
Michael Beck's avatar
Michael Beck committed
224
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
225
226
		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
227
		if (entity_is_externally_visible(ent)) {
Michael Beck's avatar
Michael Beck committed
228
			pmap_insert(ldname_map, (void *)get_entity_ld_ident(ent), ent);
Michael Beck's avatar
Michael Beck committed
229
230
231
		}
	}

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

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

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

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

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

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

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

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

Matthias Braun's avatar
Matthias Braun committed
295
static void free_mark_proj(ir_node *node, long n, pset *set)
Matthias Braun's avatar
Matthias Braun committed
296
{
Michael Beck's avatar
Michael Beck committed
297
298
299
300
301
302
303
304
305
306
307
308
	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);
309
		if (get_irn_link(pred) != MARK && is_Tuple(pred)) {
Michael Beck's avatar
Michael Beck committed
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
			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;
	}
336
	// set_irn_link(node, NULL);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
337
338
}

339
/**
Michael Beck's avatar
Michael Beck committed
340
341
342
343
344
345
346
 * 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
 *
347
348
349
 * @param node  the current visited node
 * @param set   the set of all free methods
 */
Matthias Braun's avatar
Matthias Braun committed
350
static void free_mark(ir_node *node, pset *set)
Matthias Braun's avatar
Matthias Braun committed
351
{
Michael Beck's avatar
Michael Beck committed
352
353
354
355
356
357
358
	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
359
360
		ir_entity *ent = get_Sel_entity(node);
		if (is_method_entity(ent)) {
361
			size_t i, n;
362
			for (i = 0, n = get_Sel_n_methods(node); i < n; ++i) {
Matthias Braun's avatar
Matthias Braun committed
363
				pset_insert_ptr(set, get_Sel_method(node, i));
Michael Beck's avatar
Michael Beck committed
364
365
366
			}
		}
		break;
Michael Beck's avatar
Michael Beck committed
367
	}
Michael Beck's avatar
Michael Beck committed
368
369
	case iro_SymConst:
		if (get_SymConst_kind(node) == symconst_addr_ent) {
Michael Beck's avatar
Michael Beck committed
370
371
			ir_entity *ent = get_SymConst_entity(node);
			if (is_method_entity(ent)) {
Matthias Braun's avatar
Matthias Braun committed
372
				pset_insert_ptr(set, ent);
Michael Beck's avatar
Michael Beck committed
373
374
375
376
377
			}
		}
		break;

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

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

	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
417
418
	{
		size_t i, n;
Michael Beck's avatar
Michael Beck committed
419
420
		/* we must handle Call nodes specially, because their call address input
		   do not expose a method address. */
Michael Beck's avatar
Michael Beck committed
421
		set_irn_link(node, MARK);
Michael Beck's avatar
Michael Beck committed
422
		for (i = 0, n = get_Call_n_params(node); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
423
424
425
426
427
428
			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
429
	}
430
431
	default: {
		int i;
yb9976's avatar
yb9976 committed
432
		/* other nodes: Alle anderen Knoten nehmen wir als Verr�ter an, bis
Michael Beck's avatar
Michael Beck committed
433
434
435
		 * 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
436
			ir_node *pred = get_irn_n(node, i);
Michael Beck's avatar
Michael Beck committed
437
438
439
440
441
442
			if (mode_is_reference(get_irn_mode(pred))) {
				free_mark(pred, set);
			}
		}
		break;
	}
443
	}
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
444
445
}

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

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

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

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

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

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

Matthias Braun's avatar
Matthias Braun committed
511
	if (ent->initializer != NULL) {
512
		add_method_address_inititializer(get_entity_initializer(ent), set);
Michael Beck's avatar
Michael Beck committed
513
	}
514
515
}

Michael Beck's avatar
Michael Beck committed
516
517
518
519
/**
 * 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
520
 * Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
521
 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
Matthias Braun's avatar
Matthias Braun committed
522
 * SymConst(name)-Operationen müssen in passende SymConst(ent)-Operationen
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
523
 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
Michael Beck's avatar
Michael Beck committed
524
525
 * auf eine echt externe Methode.
 */
526
static size_t get_free_methods(ir_entity ***free_methods)
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
527
{
Matthias Braun's avatar
Matthias Braun committed
528
	pset *free_set = pset_new_ptr_default();
Michael Beck's avatar
Michael Beck committed
529
	size_t i, n, j, m;
Michael Beck's avatar
Michael Beck committed
530
	ir_entity **arr;
Michael Beck's avatar
Michael Beck committed
531
	ir_graph *irg;
Michael Beck's avatar
Michael Beck committed
532
	ir_type *tp;
533
	size_t length;
Michael Beck's avatar
Michael Beck committed
534

Michael Beck's avatar
Michael Beck committed
535
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
Matthias Braun's avatar
Matthias Braun committed
536
		ir_linkage linkage;
Michael Beck's avatar
Michael Beck committed
537
		irg = get_irp_irg(i);
538
		ir_entity *const ent = get_irg_entity(irg);
Matthias Braun's avatar
Matthias Braun committed
539
540
		linkage = get_entity_linkage(ent);

Michael Beck's avatar
Michael Beck committed
541
		if ((linkage & IR_LINKAGE_HIDDEN_USER) || entity_is_externally_visible(ent)) {
Matthias Braun's avatar
Matthias Braun committed
542
			pset_insert_ptr(free_set, ent);
Michael Beck's avatar
Michael Beck committed
543
		}
Michael Beck's avatar
Michael Beck committed
544

545
		ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
546
		/* Find all method entities that gets "visible" through this graphs,
Michael Beck's avatar
Michael Beck committed
547
		 * for instance because their address is stored. */
548
		irg_walk_graph(irg, firm_clear_link, free_ana_walker, free_set);
549
		ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
Michael Beck's avatar
Michael Beck committed
550
551
	}

Michael Beck's avatar
Michael Beck committed
552
	/* insert all methods that are used in global variables initializers */
Michael Beck's avatar
Michael Beck committed
553
	tp = get_glob_type();
Michael Beck's avatar
Michael Beck committed
554
	for (j = 0, m = get_class_n_members(tp); j < m; ++j) {
555
		ir_entity *const ent = get_class_member(tp, j);
Michael Beck's avatar
Michael Beck committed
556
557
558
		add_method_address(ent, free_set);
	}
	tp = get_tls_type();
559
	for (j = 0, m = get_compound_n_members(tp); j < m; ++j) {
560
		ir_entity *const ent = get_compound_member(tp, j);
Michael Beck's avatar
Michael Beck committed
561
562
563
564
565
		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
566
	if (irg != NULL)
Matthias Braun's avatar
Matthias Braun committed
567
		pset_insert_ptr(free_set, get_irg_entity(irg));
Michael Beck's avatar
Michael Beck committed
568
569

	/* Finally, transform the set into an array. */
Matthias Braun's avatar
Matthias Braun committed
570
	length = pset_count(free_set);
571
	arr = XMALLOCN(ir_entity*, length);
Matthias Braun's avatar
Matthias Braun committed
572
	i = 0;
573
	foreach_pset(free_set, ir_entity, ent) {
Michael Beck's avatar
Michael Beck committed
574
		arr[i++] = ent;
Michael Beck's avatar
Michael Beck committed
575
	}
Matthias Braun's avatar
Matthias Braun committed
576
	del_pset(free_set);
Michael Beck's avatar
Michael Beck committed
577

578
579
	*free_methods = arr;
	return length;
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
580
581
582
583
584
585
}

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

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

Matthias Braun's avatar
Matthias Braun committed
588
static void callee_ana_proj(ir_node *node, long n, pset *methods)
Matthias Braun's avatar
Matthias Braun committed
589
{
Michael Beck's avatar
Michael Beck committed
590
591
592
593
594
595
596
597
598
599
600
	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
601
		 * zur�ckgibt. */
Michael Beck's avatar
Michael Beck committed
602
		ir_node *pred = get_Proj_pred(node);
Michael Beck's avatar
Michael Beck committed
603
		if (get_irn_link(pred) != MARK) {
Michael Beck's avatar
Michael Beck committed
604
			if (is_Tuple(pred)) {
Michael Beck's avatar
Michael Beck committed
605
606
				callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
			} else {
607
				pset_insert_ptr(methods, get_unknown_entity()); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
608
609
610
			}
		}
		break;
Michael Beck's avatar
Michael Beck committed
611
	}
Michael Beck's avatar
Michael Beck committed
612
613
614
615
616
617

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

	default:
618
		pset_insert_ptr(methods, get_unknown_entity()); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
619
620
		break;
	}
621
622
}

Michael Beck's avatar
Michael Beck committed
623
/**
Michael Beck's avatar
Michael Beck committed
624
 * Analyse a Call address.
Michael Beck's avatar
Michael Beck committed
625
 *
Michael Beck's avatar
Michael Beck committed
626
627
 * @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
628
 */
Matthias Braun's avatar
Matthias Braun committed
629
static void callee_ana_node(ir_node *node, pset *methods)
Matthias Braun's avatar
Matthias Braun committed
630
{
Michael Beck's avatar
Michael Beck committed
631
632
633
634
635
636
637
638
639
640
641
	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
642
		   call and ignore it completely. */
643
		pset_insert_ptr(methods, get_unknown_entity()); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
644
		break;
645
646
647
648

	case iro_SymConst: {
		ir_entity *ent = get_SymConst_entity(node);
		assert(ent && is_method_entity(ent));
Matthias Braun's avatar
Matthias Braun committed
649
		pset_insert_ptr(methods, ent);
Michael Beck's avatar
Michael Beck committed
650
		break;
651
652
	}

653
	case iro_Sel: {
Michael Beck's avatar
Michael Beck committed
654
		/* polymorphic method */
655
656
		size_t i, n;
		for (i = 0, n = get_Sel_n_methods(node); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
657
658
			ir_entity *ent = get_Sel_method(node, i);
			if (ent != NULL) {
Matthias Braun's avatar
Matthias Braun committed
659
				pset_insert_ptr(methods, ent);
Michael Beck's avatar
Michael Beck committed
660
			} else {
661
				pset_insert_ptr(methods, get_unknown_entity());
Michael Beck's avatar
Michael Beck committed
662
663
664
			}
		}
		break;
665
	}
Michael Beck's avatar
Michael Beck committed
666
667
668
669
670

	case iro_Bad:
		/* nothing */
		break;

671
672
	case iro_Phi: {
		int i;
Michael Beck's avatar
Michael Beck committed
673
674
675
676
		for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
			callee_ana_node(get_Phi_pred(node, i), methods);
		}
		break;
677
	}
Michael Beck's avatar
Michael Beck committed
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695

	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 */
696
		pset_insert_ptr(methods, get_unknown_entity()); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
697
698
699
700
701
702
		break;

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

Michael Beck's avatar
Michael Beck committed
705
/**
Michael Beck's avatar
Michael Beck committed
706
 * Walker: Analyses every Call node and calculates an array of possible
Michael Beck's avatar
Michael Beck committed
707
708
 * callees for that call.
 */
Matthias Braun's avatar
Matthias Braun committed
709
710
static void callee_walker(ir_node *call, void *env)
{
Michael Beck's avatar
Michael Beck committed
711
712
	(void) env;
	if (is_Call(call)) {
Matthias Braun's avatar
Matthias Braun committed
713
		pset *methods = pset_new_ptr_default();
Michael Beck's avatar
Michael Beck committed
714
		ir_entity **arr;
715
		size_t i;
Michael Beck's avatar
Michael Beck committed
716

Michael Beck's avatar
Michael Beck committed
717
		callee_ana_node(get_Call_ptr(call), methods);
Matthias Braun's avatar
Matthias Braun committed
718
719
		arr = NEW_ARR_F(ir_entity*, pset_count(methods));
		i = 0;
720
		foreach_pset(methods, ir_entity, ent) {
Michael Beck's avatar
Michael Beck committed
721
722
			arr[i] = ent;
			/* we want the unknown_entity on the zero position for easy tests later */
723
			if (is_unknown_entity(ent)) {
Michael Beck's avatar
Michael Beck committed
724
				arr[i] = arr[0];
725
				arr[0] = get_unknown_entity();
Michael Beck's avatar
Michael Beck committed
726
			}
Michael Beck's avatar
Michael Beck committed
727
			++i;
Michael Beck's avatar
Michael Beck committed
728
		}
Michael Beck's avatar
Michael Beck committed
729
		set_Call_callee_arr(call, ARR_LEN(arr), arr);
Michael Beck's avatar
Michael Beck committed
730
		DEL_ARR_F(arr);
Matthias Braun's avatar
Matthias Braun committed
731
		del_pset(methods);
Michael Beck's avatar
Michael Beck committed
732
	}
733
734
}

Michael Beck's avatar
Michael Beck committed
735
736
737
/**
 * Walker: Removes all tuple.
 */
Matthias Braun's avatar
Matthias Braun committed
738
739
static void remove_Tuples(ir_node *proj, void *env)
{
Michael Beck's avatar
Michael Beck committed
740
741
742
	ir_node *nn;
	(void) env;
	if (! is_Proj(proj)) return;
743

Michael Beck's avatar
Michael Beck committed
744
745
	nn = skip_Tuple(proj);
	if (nn != proj) exchange(proj, nn);
746
747
748
}


Michael Beck's avatar
Michael Beck committed
749
750
751
752
753
/**
 * 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
754
755
static void callee_ana(void)
{
Michael Beck's avatar
Michael Beck committed
756
	size_t i, n;
Michael Beck's avatar
Michael Beck committed
757
	/* analyse all graphs */
Michael Beck's avatar
Michael Beck committed
758
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
759
760
761
762
763
		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);
764
765
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
766
767
768
/*--------------------------------------------------------------------------*/
/* Cleanup after analyses.                                                  */
/*--------------------------------------------------------------------------*/
769

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
770
/** Frees intermediate data structures. */
Matthias Braun's avatar
Matthias Braun committed
771
772
static void sel_methods_dispose(void)
{
Michael Beck's avatar
Michael Beck committed
773
	assert(entities);
774
	foreach_pset(entities, ir_entity, ent) {
Matthias Braun's avatar
Matthias Braun committed
775
776
		ir_entity **arr = (ir_entity**) get_entity_link(ent);
		if (arr != NULL) {
Michael Beck's avatar
Michael Beck committed
777
778
779
780
			DEL_ARR_F(arr);
		}
		set_entity_link(ent, NULL);
	}
Matthias Braun's avatar
Matthias Braun committed
781
	del_pset(entities);
Michael Beck's avatar
Michael Beck committed
782
	entities = NULL;
783
784
}

Matthias Braun's avatar
Matthias Braun committed
785
786
static void destruct_walker(ir_node * node, void * env)
{
Michael Beck's avatar
Michael Beck committed
787
788
789
790
	(void) env;
	if (is_Call(node)) {
		remove_Call_callee_arr(node);
	}
791
792
}

793
size_t cgana(ir_entity ***free_methods)
Matthias Braun's avatar
Matthias Braun committed
794
{
795
	size_t length;
Michael Beck's avatar
Michael Beck committed
796
797
	/* Optimize Sel/SymConst nodes and compute all methods that implement an entity. */
	sel_methods_init();
798
	length = get_free_methods(free_methods);
Michael Beck's avatar
Michael Beck committed
799
800
	callee_ana();
	sel_methods_dispose();
801
	return length;
802
}
803

Matthias Braun's avatar
Matthias Braun committed
804
805
void free_callee_info(ir_graph *irg)
{
Michael Beck's avatar
Michael Beck committed
806
807
	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
808
809
}

Matthias Braun's avatar
Matthias Braun committed
810
811
void free_irp_callee_info(void)
{
Michael Beck's avatar
Michael Beck committed
812
813
	size_t i, n;
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
814
815
		free_callee_info(get_irp_irg(i));
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
816
817
}

Matthias Braun's avatar
Matthias Braun committed
818
819
void opt_call_addrs(void)
{
820
821
822
823
824
825
826
827
828
829
830
831
832
833
	/* 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
834
835
	sel_methods_init();
	sel_methods_dispose();
836
}