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
39

#include "cgana.h"

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

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

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

59
60
#include "irdump.h"

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

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

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


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

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

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

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

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

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

120
121
	if (size == 0) {
		/* no overwriting methods found */
Michael Beck's avatar
Michael Beck committed
122
123
124
125
		arr = NULL;
	} else {
		ir_entity * ent;
		arr = NEW_ARR_F(ir_entity *, size);
126
127
		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
128
129
130
	}
	eset_destroy(set);
	return arr;
131
132
}

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

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

167
	if (is_Sel(node) && is_Method_type(get_entity_type(get_Sel_entity(node)))) {
168
169
170
171
172
173
174
175
176
		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
177

178
179
		/* -- As an add on we get an optimization that removes polymorphic calls.
		This optimization is more powerful than that in transform_node_Sel().  -- */
180
		arr = (ir_entity**) get_entity_link(ent);
181
182
183
184
185
186
		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
187
			assert(get_entity_irg(ent) == NULL);
188
189
190
191
192
193
194
195
196
197
		}
		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
198
			assert(get_entity_irg(arr[0]) != NULL);
199
			new_node = copy_const_value(get_irn_dbg_info(node), get_atomic_ent_value(arr[0]), get_nodes_block(node));
200
201
202
			DBG_OPT_POLY(node, new_node);
			exchange(node, new_node);
		}
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
223
	assert(entities == NULL);
	entities = eset_create();
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 */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
293
static void free_mark(ir_node * node, eset * set);
294

Matthias Braun's avatar
Matthias Braun committed
295
296
static void free_mark_proj(ir_node * node, long n, eset * set)
{
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
351
static void free_mark(ir_node *node, eset * set)
{
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) {
Michael Beck's avatar
Michael Beck committed
363
364
365
366
				eset_insert(set, get_Sel_method(node, i));
			}
		}
		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)) {
Michael Beck's avatar
Michael Beck committed
372
373
374
375
376
377
				eset_insert(set, ent);
			}
		}
		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)
{
399
	eset *set = (eset*) 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
458
static void add_method_address_inititializer(ir_initializer_t *initializer,
                                             eset *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_Global(n)) {
			ir_entity *ent = get_Global_entity(n);
470
471
472
473
474
475
476
477

			if (is_Method_type(get_entity_type(ent)))
				eset_insert(set, ent);
		}
		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
 */
500
static void add_method_address(ir_entity *ent, eset *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);
Matthias Braun's avatar
Matthias Braun committed
513
	} else if (entity_has_compound_ent_values(ent)) {
Michael Beck's avatar
Michael Beck committed
514
515
516
		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
517
518

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

522
523
				if (is_Method_type(get_entity_type(ent2)))
					eset_insert(set, ent2);
Michael Beck's avatar
Michael Beck committed
524
525
526
			}
		}
	}
527
528
}

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

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

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

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

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

	/* Finally, transform the set into an array. */
584
585
	length = eset_count(free_set);
	arr = XMALLOCN(ir_entity*, length);
586
	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
587
		arr[i++] = ent;
Michael Beck's avatar
Michael Beck committed
588
589
590
	}
	eset_destroy(free_set);

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

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

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

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

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

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

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

	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
663
		break;
664
665
	}

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

	case iro_Bad:
		/* nothing */
		break;

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

	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
709
		eset_insert(methods, unknown_entity); /* free method -> unknown */
Michael Beck's avatar
Michael Beck committed
710
711
712
713
714
715
		break;

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

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

Michael Beck's avatar
Michael Beck committed
731
		callee_ana_node(get_Call_ptr(call), methods);
Michael Beck's avatar
Michael Beck committed
732
		arr = NEW_ARR_F(ir_entity *, eset_count(methods));
733
		for (i = 0, ent = (ir_entity*) eset_first(methods); ent; ent = (ir_entity*) eset_next(methods)) {
Michael Beck's avatar
Michael Beck committed
734
735
736
737
738
			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
739
			}
Michael Beck's avatar
Michael Beck committed
740
			++i;
Michael Beck's avatar
Michael Beck committed
741
		}
Michael Beck's avatar
Michael Beck committed
742
		set_Call_callee_arr(call, ARR_LEN(arr), arr);
Michael Beck's avatar
Michael Beck committed
743
744
745
		DEL_ARR_F(arr);
		eset_destroy(methods);
	}
746
747
}

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

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


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

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

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
783
/** Frees intermediate data structures. */
Matthias Braun's avatar
Matthias Braun committed
784
785
static void sel_methods_dispose(void)
{
Michael Beck's avatar
Michael Beck committed
786
787
	ir_entity * ent;
	assert(entities);
788
789
	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
790
791
792
793
794
795
796
		if (arr) {
			DEL_ARR_F(arr);
		}
		set_entity_link(ent, NULL);
	}
	eset_destroy(entities);
	entities = NULL;
797
798
}

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

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

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

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

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

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

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