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

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

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

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

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

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

60
61
#include "irdump.h"

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

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

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


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

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

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

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

105
106
107
108
/**
 * 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.
109
 *
110
 * @param method  the method
111
 */
112
static ir_entity **get_impl_methods(ir_entity *method)
Matthias Braun's avatar
Matthias Braun committed
113
{
114
115
116
	ir_entity **arr;
	eset      *set = eset_create();
	size_t    size;
Michael Beck's avatar
Michael Beck committed
117
118

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

121
122
	if (size == 0) {
		/* no overwriting methods found */
Michael Beck's avatar
Michael Beck committed
123
124
125
126
		arr = NULL;
	} else {
		ir_entity * ent;
		arr = NEW_ARR_F(ir_entity *, size);
127
128
		for (ent = (ir_entity*) eset_first(set); size > 0; ent = (ir_entity*) eset_next(set))
			arr[--size] = ent;
Michael Beck's avatar
Michael Beck committed
129
130
131
	}
	eset_destroy(set);
	return arr;
132
133
}

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

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

168
	if (is_Sel(node) && is_Method_type(get_entity_type(get_Sel_entity(node)))) {
169
170
171
172
173
174
175
176
177
		ir_entity *ent = get_SymConst_entity(get_atomic_ent_value(get_Sel_entity(node)));

		if (!eset_contains(entities, ent)) {
			/* Entity not yet handled. Find all (internal or external)
			 * implemented methods that overwrites this entity.
			 * This set is stored in the entity link. */
			set_entity_link(ent, get_impl_methods(ent));
			eset_insert(entities, ent);
		}
Michael Beck's avatar
Michael Beck committed
178

179
180
		/* -- As an add on we get an optimization that removes polymorphic calls.
		This optimization is more powerful than that in transform_node_Sel().  -- */
181
		arr = (ir_entity**) get_entity_link(ent);
182
183
184
185
186
187
		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
188
			assert(get_entity_irg(ent) == NULL);
189
190
191
192
193
194
195
196
197
198
		}
		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
199
			assert(get_entity_irg(arr[0]) != NULL);
200
			new_node = copy_const_value(get_irn_dbg_info(node), get_atomic_ent_value(arr[0]), get_nodes_block(node));
201
202
203
			DBG_OPT_POLY(node, new_node);
			exchange(node, new_node);
		}
Michael Beck's avatar
Michael Beck committed
204
	}
205
206
}

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

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

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

244
245
246
/**
 * Returns an array of all methods that could be called at a Sel node.
 * This array contains every entry only once.
247
248
 *
 * @param sel  the Sel node
249
 */
Matthias Braun's avatar
Matthias Braun committed
250
251
static ir_entity ** get_Sel_arr(ir_node * sel)
{
Michael Beck's avatar
Michael Beck committed
252
253
254
255
256
257
258
259
	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? */
260
	arr = (ir_entity**) get_entity_link(ent);
Michael Beck's avatar
Michael Beck committed
261
262
263
264
	if (arr) {
		return arr;
	} else {
		/* "NULL" zeigt an, dass keine Implementierung existiert. Dies
yb9976's avatar
yb9976 committed
265
		 * kann f�r polymorphe (abstrakte) Methoden passieren. */
Michael Beck's avatar
Michael Beck committed
266
267
268
269
270
		if (!NULL_ARRAY) {
			NULL_ARRAY = NEW_ARR_F(ir_entity *, 0);
		}
		return NULL_ARRAY;
	}
271
272
}

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

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

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

Matthias Braun's avatar
Matthias Braun committed
296
297
static void free_mark_proj(ir_node * node, long n, eset * set)
{
Michael Beck's avatar
Michael Beck committed
298
299
300
301
302
303
304
305
306
307
308
309
	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);
310
		if (get_irn_link(pred) != MARK && is_Tuple(pred)) {
Michael Beck's avatar
Michael Beck committed
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
336
			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;
	}
337
	// set_irn_link(node, NULL);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
338
339
}

340
/**
Michael Beck's avatar
Michael Beck committed
341
342
343
344
345
346
347
 * 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
 *
348
349
350
 * @param node  the current visited node
 * @param set   the set of all free methods
 */
Matthias Braun's avatar
Matthias Braun committed
351
352
static void free_mark(ir_node *node, eset * set)
{
353
	size_t i, n;
Michael Beck's avatar
Michael Beck committed
354
355
356
357
358
359
360
361

	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
362
363
		ir_entity *ent = get_Sel_entity(node);
		if (is_method_entity(ent)) {
364
			for (i = 0, n = get_Sel_n_methods(node); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
365
366
367
368
				eset_insert(set, get_Sel_method(node, i));
			}
		}
		break;
Michael Beck's avatar
Michael Beck committed
369
	}
Michael Beck's avatar
Michael Beck committed
370
371
	case iro_SymConst:
		if (get_SymConst_kind(node) == symconst_addr_ent) {
Michael Beck's avatar
Michael Beck committed
372
373
			ir_entity *ent = get_SymConst_entity(node);
			if (is_method_entity(ent)) {
Michael Beck's avatar
Michael Beck committed
374
375
376
377
378
379
				eset_insert(set, ent);
			}
		}
		break;

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

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

	if (get_irn_link(node) == MARK) {
		/* already visited */
		return;
	}
	switch (get_irn_opcode(node)) {
		/* special nodes */
	case iro_Sel:
	case iro_SymConst:
	case iro_Const:
	case iro_Phi:
	case iro_Id:
	case iro_Proj:
	case iro_Tuple:
		/* nothing */
		break;
	case iro_Call:
Michael Beck's avatar
Michael Beck committed
420
421
		/* we must handle Call nodes specially, because their call address input
		   do not expose a method address. */
Michael Beck's avatar
Michael Beck committed
422
423
424
425
426
427
428
429
		set_irn_link(node, MARK);
		for (i = get_Call_n_params(node) - 1; i >= 0; --i) {
			ir_node *pred = get_Call_param(node, i);
			if (mode_is_reference(get_irn_mode(pred))) {
				free_mark(pred, set);
			}
		}
		break;
Michael Beck's avatar
Michael Beck committed
430
	default:
yb9976's avatar
yb9976 committed
431
		/* other nodes: Alle anderen Knoten nehmen wir als Verr�ter an, bis
Michael Beck's avatar
Michael Beck committed
432
433
434
		 * 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
435
			ir_node *pred = get_irn_n(node, i);
Michael Beck's avatar
Michael Beck committed
436
437
438
439
440
441
			if (mode_is_reference(get_irn_mode(pred))) {
				free_mark(pred, set);
			}
		}
		break;
	}
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
442
443
}

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

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

		/* let's check if it's the address of a function */
466
467
		if (is_Global(n)) {
			ir_entity *ent = get_Global_entity(n);
468
469
470
471
472
473
474
475

			if (is_Method_type(get_entity_type(ent)))
				eset_insert(set, ent);
		}
		return;
	case IR_INITIALIZER_TARVAL:
	case IR_INITIALIZER_NULL:
		return;
476
	case IR_INITIALIZER_COMPOUND:
477
		for (i = 0; i < initializer->compound.n_initializers; ++i) {
478
479
			ir_initializer_t *sub_initializer
				= initializer->compound.initializers[i];
480
			add_method_address_inititializer(sub_initializer, set);
481
482
483
484
485
486
		}
		return;
	}
	panic("invalid initializer found");
}

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

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

Matthias Braun's avatar
Matthias Braun committed
509
	if (ent->initializer != NULL) {
510
		add_method_address_inititializer(get_entity_initializer(ent), set);
Matthias Braun's avatar
Matthias Braun committed
511
	} else if (entity_has_compound_ent_values(ent)) {
Michael Beck's avatar
Michael Beck committed
512
513
514
		size_t i, n;
		for (i = 0, n = get_compound_ent_n_values(ent); i < n; ++i) {
			ir_node *irn = get_compound_ent_value(ent, i);
Michael Beck's avatar
Michael Beck committed
515
516

			/* let's check if it's the address of a function */
Michael Beck's avatar
Michael Beck committed
517
518
			if (is_Global(irn)) {
				ir_entity *ent = get_Global_entity(irn);
Michael Beck's avatar
Michael Beck committed
519

Michael Beck's avatar
Michael Beck committed
520
521
				if (is_Method_type(get_entity_type(ent)))
					eset_insert(set, ent);
Michael Beck's avatar
Michael Beck committed
522
523
524
			}
		}
	}
525
526
}

Michael Beck's avatar
Michael Beck committed
527
528
529
530
/**
 * 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
531
 * Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
532
 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
Matthias Braun's avatar
Matthias Braun committed
533
 * SymConst(name)-Operationen müssen in passende SymConst(ent)-Operationen
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
534
 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
Michael Beck's avatar
Michael Beck committed
535
536
 * auf eine echt externe Methode.
 */
537
static size_t get_free_methods(ir_entity ***free_methods)
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
538
{
Michael Beck's avatar
Michael Beck committed
539
	eset *free_set = eset_create();
Michael Beck's avatar
Michael Beck committed
540
541
	size_t i, n;
	int j;
Michael Beck's avatar
Michael Beck committed
542
	ir_entity **arr;
Michael Beck's avatar
Michael Beck committed
543
544
	ir_entity *ent;
	ir_graph *irg;
Michael Beck's avatar
Michael Beck committed
545
	ir_type *tp;
546
	size_t length;
Michael Beck's avatar
Michael Beck committed
547

Michael Beck's avatar
Michael Beck committed
548
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
Matthias Braun's avatar
Matthias Braun committed
549
		ir_linkage linkage;
Michael Beck's avatar
Michael Beck committed
550
551
		irg = get_irp_irg(i);
		ent = get_irg_entity(irg);
Matthias Braun's avatar
Matthias Braun committed
552
553
		linkage = get_entity_linkage(ent);

Michael Beck's avatar
Michael Beck committed
554
		if ((linkage & IR_LINKAGE_HIDDEN_USER) || entity_is_externally_visible(ent)) {
Michael Beck's avatar
Michael Beck committed
555
556
			eset_insert(free_set, ent);
		}
Michael Beck's avatar
Michael Beck committed
557

558
		ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
559
		/* Find all method entities that gets "visible" through this graphs,
Michael Beck's avatar
Michael Beck committed
560
		 * for instance because their address is stored. */
561
		irg_walk_graph(irg, firm_clear_link, free_ana_walker, free_set);
562
		ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
Michael Beck's avatar
Michael Beck committed
563
564
	}

Michael Beck's avatar
Michael Beck committed
565
	/* insert all methods that are used in global variables initializers */
Michael Beck's avatar
Michael Beck committed
566
	tp = get_glob_type();
Michael Beck's avatar
Michael Beck committed
567
568
	for (j = get_class_n_members(tp) - 1; j >= 0; --j) {
		ent = get_class_member(tp, j);
Michael Beck's avatar
Michael Beck committed
569
570
571
		add_method_address(ent, free_set);
	}
	tp = get_tls_type();
Michael Beck's avatar
Michael Beck committed
572
573
	for (j = get_class_n_members(tp) - 1; j >= 0; --j) {
		ent = get_class_member(tp, j);
Michael Beck's avatar
Michael Beck committed
574
575
576
577
578
		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
579
	if (irg != NULL)
Michael Beck's avatar
Michael Beck committed
580
581
582
		eset_insert(free_set, get_irg_entity(irg));

	/* Finally, transform the set into an array. */
583
584
	length = eset_count(free_set);
	arr = XMALLOCN(ir_entity*, length);
585
	for (i = 0, ent = (ir_entity*) eset_first(free_set); ent; ent = (ir_entity*) eset_next(free_set)) {
Michael Beck's avatar
Michael Beck committed
586
		arr[i++] = ent;
Michael Beck's avatar
Michael Beck committed
587
588
589
	}
	eset_destroy(free_set);

590
591
	*free_methods = arr;
	return length;
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
592
593
594
595
596
597
598
}

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

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

Matthias Braun's avatar
Matthias Braun committed
600
601
static void callee_ana_proj(ir_node *node, long n, eset *methods)
{
Michael Beck's avatar
Michael Beck committed
602
603
604
605
606
607
608
609
610
611
612
	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
613
		 * zur�ckgibt. */
Michael Beck's avatar
Michael Beck committed
614
		ir_node *pred = get_Proj_pred(node);
Michael Beck's avatar
Michael Beck committed
615
		if (get_irn_link(pred) != MARK) {
Michael Beck's avatar
Michael Beck committed
616
			if (is_Tuple(pred)) {
Michael Beck's avatar
Michael Beck committed
617
618
				callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
			} else {
Michael Beck's avatar
Michael Beck committed
619
				eset_insert(methods, unknown_entity); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
620
621
622
			}
		}
		break;
Michael Beck's avatar
Michael Beck committed
623
	}
Michael Beck's avatar
Michael Beck committed
624
625
626
627
628
629

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

	default:
Michael Beck's avatar
Michael Beck committed
630
		eset_insert(methods, unknown_entity); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
631
632
		break;
	}
633
634
}

Michael Beck's avatar
Michael Beck committed
635
/**
Michael Beck's avatar
Michael Beck committed
636
 * Analyse a Call address.
Michael Beck's avatar
Michael Beck committed
637
 *
Michael Beck's avatar
Michael Beck committed
638
639
 * @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
640
 */
Matthias Braun's avatar
Matthias Braun committed
641
642
static void callee_ana_node(ir_node *node, eset *methods)
{
Michael Beck's avatar
Michael Beck committed
643
644
645
646
647
648
649
650
651
652
653
	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
654
655
		   call and ignore it completely. */
		eset_insert(methods, unknown_entity); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
656
		break;
657
658
659
660
661

	case iro_SymConst: {
		ir_entity *ent = get_SymConst_entity(node);
		assert(ent && is_method_entity(ent));
		eset_insert(methods, ent);
Michael Beck's avatar
Michael Beck committed
662
		break;
663
664
	}

665
	case iro_Sel: {
Michael Beck's avatar
Michael Beck committed
666
		/* polymorphic method */
667
668
		size_t i, n;
		for (i = 0, n = get_Sel_n_methods(node); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
669
670
			ir_entity *ent = get_Sel_method(node, i);
			if (ent != NULL) {
Michael Beck's avatar
Michael Beck committed
671
672
				eset_insert(methods, ent);
			} else {
Michael Beck's avatar
Michael Beck committed
673
				eset_insert(methods, unknown_entity);
Michael Beck's avatar
Michael Beck committed
674
675
676
			}
		}
		break;
677
	}
Michael Beck's avatar
Michael Beck committed
678
679
680
681
682

	case iro_Bad:
		/* nothing */
		break;

683
684
	case iro_Phi: {
		int i;
Michael Beck's avatar
Michael Beck committed
685
686
687
688
		for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
			callee_ana_node(get_Phi_pred(node, i), methods);
		}
		break;
689
	}
Michael Beck's avatar
Michael Beck committed
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707

	case iro_Mux:
		callee_ana_node(get_Mux_false(node), methods);
		callee_ana_node(get_Mux_true(node), methods);
		break;

	case iro_Id:
		callee_ana_node(get_Id_pred(node), methods);
		break;

	case iro_Proj:
		callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
		break;

	case iro_Add:
	case iro_Sub:
	case iro_Conv:
		/* extern */
Michael Beck's avatar
Michael Beck committed
708
		eset_insert(methods, unknown_entity); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
709
710
711
712
713
714
		break;

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

Michael Beck's avatar
Michael Beck committed
717
/**
Michael Beck's avatar
Michael Beck committed
718
 * Walker: Analyses every Call node and calculates an array of possible
Michael Beck's avatar
Michael Beck committed
719
720
 * callees for that call.
 */
Matthias Braun's avatar
Matthias Braun committed
721
722
static void callee_walker(ir_node *call, void *env)
{
Michael Beck's avatar
Michael Beck committed
723
724
	(void) env;
	if (is_Call(call)) {
Michael Beck's avatar
Michael Beck committed
725
726
727
		eset *methods = eset_create();
		ir_entity *ent;
		ir_entity **arr;
728
		size_t i;
Michael Beck's avatar
Michael Beck committed
729

Michael Beck's avatar
Michael Beck committed
730
		callee_ana_node(get_Call_ptr(call), methods);
Michael Beck's avatar
Michael Beck committed
731
		arr = NEW_ARR_F(ir_entity *, eset_count(methods));
732
		for (i = 0, ent = (ir_entity*) eset_first(methods); ent; ent = (ir_entity*) eset_next(methods)) {
Michael Beck's avatar
Michael Beck committed
733
734
735
736
737
			arr[i] = ent;
			/* we want the unknown_entity on the zero position for easy tests later */
			if (ent == unknown_entity) {
				arr[i] = arr[0];
				arr[0] = unknown_entity;
Michael Beck's avatar
Michael Beck committed
738
			}
Michael Beck's avatar
Michael Beck committed
739
			++i;
Michael Beck's avatar
Michael Beck committed
740
		}
Michael Beck's avatar
Michael Beck committed
741
		set_Call_callee_arr(call, ARR_LEN(arr), arr);
Michael Beck's avatar
Michael Beck committed
742
743
744
		DEL_ARR_F(arr);
		eset_destroy(methods);
	}
745
746
}

Michael Beck's avatar
Michael Beck committed
747
748
749
/**
 * Walker: Removes all tuple.
 */
Matthias Braun's avatar
Matthias Braun committed
750
751
static void remove_Tuples(ir_node *proj, void *env)
{
Michael Beck's avatar
Michael Beck committed
752
753
754
	ir_node *nn;
	(void) env;
	if (! is_Proj(proj)) return;
755

Michael Beck's avatar
Michael Beck committed
756
757
	nn = skip_Tuple(proj);
	if (nn != proj) exchange(proj, nn);
758
759
760
}


Michael Beck's avatar
Michael Beck committed
761
762
763
764
765
/**
 * 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
766
767
static void callee_ana(void)
{
Michael Beck's avatar
Michael Beck committed
768
	size_t i, n;
Michael Beck's avatar
Michael Beck committed
769
	/* analyse all graphs */
Michael Beck's avatar
Michael Beck committed
770
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
771
772
773
774
775
		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);
776
777
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
778
779
780
/*--------------------------------------------------------------------------*/
/* Cleanup after analyses.                                                  */
/*--------------------------------------------------------------------------*/
781

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
782
/** Frees intermediate data structures. */
Matthias Braun's avatar
Matthias Braun committed
783
784
static void sel_methods_dispose(void)
{
Michael Beck's avatar
Michael Beck committed
785
786
	ir_entity * ent;
	assert(entities);
787
788
	for (ent = (ir_entity*) eset_first(entities); ent; ent = (ir_entity*) eset_next(entities)) {
		ir_entity ** arr = (ir_entity**) get_entity_link(ent);
Michael Beck's avatar
Michael Beck committed
789
790
791
792
793
794
795
		if (arr) {
			DEL_ARR_F(arr);
		}
		set_entity_link(ent, NULL);
	}
	eset_destroy(entities);
	entities = NULL;
796
797
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
798
799
800
/*--------------------------------------------------------------------------*/
/* Freeing the callee arrays.                                               */
/*--------------------------------------------------------------------------*/
801

Matthias Braun's avatar
Matthias Braun committed
802
803
static void destruct_walker(ir_node * node, void * env)
{
Michael Beck's avatar
Michael Beck committed
804
805
806
807
	(void) env;
	if (is_Call(node)) {
		remove_Call_callee_arr(node);
	}
808
809
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
810
811
812
/*--------------------------------------------------------------------------*/
/* Main drivers.                                                            */
/*--------------------------------------------------------------------------*/
813

814
size_t cgana(ir_entity ***free_methods)
Matthias Braun's avatar
Matthias Braun committed
815
{
816
	size_t length;
Michael Beck's avatar
Michael Beck committed
817
818
	/* Optimize Sel/SymConst nodes and compute all methods that implement an entity. */
	sel_methods_init();
819
	length = get_free_methods(free_methods);
Michael Beck's avatar
Michael Beck committed
820
821
	callee_ana();
	sel_methods_dispose();
822
	return length;
823
}
824

Matthias Braun's avatar
Matthias Braun committed
825
826
void free_callee_info(ir_graph *irg)
{
Michael Beck's avatar
Michael Beck committed
827
828
	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
829
830
}

Matthias Braun's avatar
Matthias Braun committed
831
832
void free_irp_callee_info(void)
{
Michael Beck's avatar
Michael Beck committed
833
834
	size_t i, n;
	for (i = 0, n = get_irp_n_irgs(); i < n; ++i) {
Michael Beck's avatar
Michael Beck committed
835
836
		free_callee_info(get_irp_irg(i));
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
837
838
}

839
/* Optimize the address expressions passed to call nodes.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
840
841
842
843
 *
 * This optimization performs the following transformations for
 * all ir graphs:
 * - All SymConst operations that refer to intern methods are replaced
Michael Beck's avatar
Michael Beck committed
844
 *   by Const operations referring to the corresponding entity.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
845
 * - Sel nodes, that select entities that are not overwritten are
Michael Beck's avatar
Michael Beck committed
846
 *   replaced by Const nodes referring to the selected entity.
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
847
 * - Sel nodes, for which no method exists at all are replaced by Bad
Götz Lindenmaier's avatar
Götz Lindenmaier committed
848
849
 *   nodes.
 * - Sel nodes with a pointer input that is an Alloc node are replaced
Michael Beck's avatar
Michael Beck committed
850
 *   by Const nodes referring to the entity that implements the method in
Götz Lindenmaier's avatar
Götz Lindenmaier committed
851
852
 *   the type given by the Alloc node.
 */
Matthias Braun's avatar
Matthias Braun committed
853
854
void opt_call_addrs(void)
{
Michael Beck's avatar
Michael Beck committed
855
856
	sel_methods_init();
	sel_methods_dispose();
857
}