tr_inheritance.c 16.2 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
2
/*
 * This file is part of libFirm.
3
 * Copyright (C) 2012 University of Karlsruhe.
Christian Würdig's avatar
Christian Würdig committed
4
5
 */

6
/**
7
 * @file
Michael Beck's avatar
Michael Beck committed
8
9
 * @brief   Utility routines for inheritance representation
 * @author  Goetz Lindenmaier
10
 */
Matthias Braun's avatar
Matthias Braun committed
11
#include "config.h"
12

13
#include "debug.h"
14
#include "typerep.h"
15
#include "irgraph_t.h"
16
17
18
#include "irprog_t.h"
#include "pset.h"
#include "set.h"
19
20
#include "irgwalk.h"
#include "irflag.h"
21
22
23
24
25

/* ----------------------------------------------------------------------- */
/* Resolve implicit inheritance.                                           */
/* ----------------------------------------------------------------------- */

26
27
ident *default_mangle_inherited_name(const ir_entity *super, const ir_type *clss)
{
28
	return id_mangle_u(new_id_from_str("inh"), id_mangle_u(get_class_ident(clss), get_entity_ident(super)));
29
30
}

Michael Beck's avatar
Michael Beck committed
31
/** Replicates all entities in all super classes that are not overwritten
Michael Beck's avatar
Michael Beck committed
32
    by an entity of this class. */
33
static void copy_entities_from_superclass(ir_type *clss, void *env)
34
{
Michael Beck's avatar
Michael Beck committed
35
36
	mangle_inherited_name_func *mfunc = *(mangle_inherited_name_func **)env;

Matthias Braun's avatar
Matthias Braun committed
37
38
39
40
	for (size_t i = 0; i < get_class_n_supertypes(clss); i++) {
		ir_type *super = get_class_supertype(clss, i);
		for (size_t j = 0; j < get_class_n_members(super); j++) {
			ir_entity *inhent = get_class_member(super, j);
Michael Beck's avatar
Michael Beck committed
41
			/* check whether inhent is already overwritten */
Matthias Braun's avatar
Matthias Braun committed
42
43
44
45
			bool overwritten = false;
			for (size_t k = 0; (k < get_class_n_members(clss)) && (overwritten == 0); k++) {
				ir_entity *thisent = get_class_member(clss, k);
				for (size_t l = 0; l < get_entity_n_overwrites(thisent); l++) {
46
					if (inhent == get_entity_overwrites(thisent, l)) {
Michael Beck's avatar
Michael Beck committed
47
						/* overwritten - do not copy */
Matthias Braun's avatar
Matthias Braun committed
48
						overwritten = true;
Michael Beck's avatar
Michael Beck committed
49
50
51
52
53
54
						break;
					}
				}
			}
			/* Inherit entity */
			if (!overwritten) {
Matthias Braun's avatar
Matthias Braun committed
55
				ir_entity *thisent = copy_entity_own(inhent, clss);
Michael Beck's avatar
Michael Beck committed
56
57
58
59
				add_entity_overwrites(thisent, inhent);
				if (get_entity_peculiarity(inhent) == peculiarity_existent)
					set_entity_peculiarity(thisent, peculiarity_inherited);
				set_entity_ld_ident(thisent, mfunc(inhent, clss));
Matthias Braun's avatar
Matthias Braun committed
60
				if (get_entity_linkage(inhent) & IR_LINKAGE_CONSTANT) {
Michael Beck's avatar
Michael Beck committed
61
62
					assert(is_atomic_entity(inhent) &&  /* @@@ */
						"Inheritance of constant, compound entities not implemented");
Matthias Braun's avatar
Matthias Braun committed
63
					add_entity_linkage(thisent, IR_LINKAGE_CONSTANT);
Michael Beck's avatar
Michael Beck committed
64
65
66
67
68
					set_atomic_ent_value(thisent, get_atomic_ent_value(inhent));
				}
			}
		}
	}
69
70
}

71
72
void resolve_inheritance(mangle_inherited_name_func *mfunc)
{
Michael Beck's avatar
Michael Beck committed
73
74
75
	if (!mfunc)
		mfunc = default_mangle_inherited_name;
	class_walk_super2sub(copy_entities_from_superclass, NULL, (void *)&mfunc);
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
}


/* ----------------------------------------------------------------------- */
/* The transitive closure of the subclass/superclass and                   */
/* overwrites/overwrittenby relation.                                      */
/*                                                                         */
/* A walk over the ir (O(#types+#entities)) computes the transitive        */
/* closure.  Adding a new type/entity or changing the basic relations in   */
/* some other way invalidates the transitive closure, i.e., it is not      */
/* updated by the basic functions.                                         */
/*                                                                         */
/* All functions are named as their counterparts for the basic relations,  */
/* adding the infix 'trans_'.                                              */
/* ----------------------------------------------------------------------- */

Matthias Braun's avatar
Matthias Braun committed
92
void set_irp_inh_transitive_closure_state(inh_transitive_closure_state s)
93
{
Michael Beck's avatar
Michael Beck committed
94
	irp->inh_trans_closure_state = s;
95
}
Matthias Braun's avatar
Matthias Braun committed
96
void invalidate_irp_inh_transitive_closure_state(void)
97
{
Michael Beck's avatar
Michael Beck committed
98
99
	if (irp->inh_trans_closure_state == inh_transitive_closure_valid)
		irp->inh_trans_closure_state = inh_transitive_closure_invalid;
100
}
101
102
inh_transitive_closure_state get_irp_inh_transitive_closure_state(void)
{
Michael Beck's avatar
Michael Beck committed
103
	return irp->inh_trans_closure_state;
104
105
}

106
107
static void assert_valid_state(void)
{
Michael Beck's avatar
Michael Beck committed
108
109
	assert(irp->inh_trans_closure_state == inh_transitive_closure_valid ||
	       irp->inh_trans_closure_state == inh_transitive_closure_invalid);
110
111
112
113
114
115
116
117
118
119
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/* There is a set that extends each entity/type with two new               */
/* fields:  one for the upwards directed relation: 'up' (supertype,        */
/* overwrites) and one for the downwards directed relation: 'down' (sub-   */
/* type, overwrittenby.  These fields contain psets (and maybe later       */
/* arrays) listing all subtypes...                                         */
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

120
typedef enum {
Michael Beck's avatar
Michael Beck committed
121
122
	d_up   = 0,
	d_down = 1,
123
124
} dir;

125
typedef struct {
Michael Beck's avatar
Michael Beck committed
126
	const firm_kind *kind;   /**< An entity or type. */
Matthias Braun's avatar
Matthias Braun committed
127
	pset            *directions[2];
128
129
130
131
132
} tr_inh_trans_tp;

/* We use this set for all types and entities.  */
static set *tr_inh_trans_set = NULL;

Michael Beck's avatar
Michael Beck committed
133
134
135
/**
 * Compare two tr_inh_trans_tp entries.
 */
136
137
static int tr_inh_trans_cmp(const void *e1, const void *e2, size_t size)
{
Matthias Braun's avatar
Matthias Braun committed
138
	(void) size;
139
140
	const tr_inh_trans_tp *ef1 = (const tr_inh_trans_tp*)e1;
	const tr_inh_trans_tp *ef2 = (const tr_inh_trans_tp*)e2;
Michael Beck's avatar
Michael Beck committed
141
	return ef1->kind != ef2->kind;
142
143
}

Michael Beck's avatar
Michael Beck committed
144
145
146
/**
 * calculate the hash value of an tr_inh_trans_tp
 */
147
148
static inline unsigned int tr_inh_trans_hash(const tr_inh_trans_tp *v)
{
149
	return hash_ptr(v->kind);
150
151
152
}

/* This always completes successfully. */
153
154
static tr_inh_trans_tp *get_firm_kind_entry(const firm_kind *k)
{
Matthias Braun's avatar
Matthias Braun committed
155
156
	if (tr_inh_trans_set == NULL)
		tr_inh_trans_set = new_set(tr_inh_trans_cmp, 128);
157

Matthias Braun's avatar
Matthias Braun committed
158
159
160
	tr_inh_trans_tp a;
	a.kind = k;
	tr_inh_trans_tp *found = set_find(tr_inh_trans_tp, tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
Michael Beck's avatar
Michael Beck committed
161
162
163
	if (!found) {
		a.directions[d_up]   = pset_new_ptr(16);
		a.directions[d_down] = pset_new_ptr(16);
164
		found = set_insert(tr_inh_trans_tp, tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
Michael Beck's avatar
Michael Beck committed
165
166
	}
	return found;
167
168
}

169
170
static pset *get_entity_map(const ir_entity *ent, dir d)
{
Michael Beck's avatar
Michael Beck committed
171
	assert(is_entity(ent));
Matthias Braun's avatar
Matthias Braun committed
172
	tr_inh_trans_tp *found = get_firm_kind_entry((const firm_kind *)ent);
Michael Beck's avatar
Michael Beck committed
173
	return found->directions[d];
174
}
Michael Beck's avatar
Michael Beck committed
175

176
177
static pset *get_type_map(const ir_type *tp, dir d)
{
Michael Beck's avatar
Michael Beck committed
178
	assert(is_type(tp));
Matthias Braun's avatar
Matthias Braun committed
179
	tr_inh_trans_tp *found = get_firm_kind_entry((const firm_kind *)tp);
Michael Beck's avatar
Michael Beck committed
180
	return found->directions[d];
181
182
183
}


Michael Beck's avatar
Michael Beck committed
184
185
186
/**
 * Walk over all types reachable from tp in the sub/supertype
 * relation and compute the closure for the two downwards directed
187
188
189
190
191
192
193
194
195
196
197
198
199
 * relations.
 *
 * The walk in the dag formed by the relation is tricky:  We must visit
 * all subtypes before visiting the supertypes.  So we first walk down.
 * Then we can compute the closure for this type.  Then we walk up.
 * As we call ourselves recursive, and walk in both directions, there
 * can be cycles.  So we have to make sure, that if we visit a node
 * a second time (in a walk up) we do nothing.  For this we increment
 * the master visited flag twice.
 * If the type is marked with master_flag_visited-1 it is on the stack.
 * If it is marked with master_flag_visited it is fully processed.
 *
 * Well, we still miss some candidates ... */
200
201
static void compute_down_closure(ir_type *tp)
{
202
	ir_visited_t master_visited = get_master_type_visited();
Michael Beck's avatar
Michael Beck committed
203
204
205
	set_type_visited(tp, master_visited-1);

	/* Recursive descend. */
Matthias Braun's avatar
Matthias Braun committed
206
207
	size_t n_subtypes = get_class_n_subtypes(tp);
	for (size_t i = 0; i < n_subtypes; ++i) {
Michael Beck's avatar
Michael Beck committed
208
209
210
211
212
213
214
		ir_type *stp = get_class_subtype(tp, i);
		if (get_type_visited(stp) < master_visited-1) {
			compute_down_closure(stp);
		}
	}

	/* types */
Matthias Braun's avatar
Matthias Braun committed
215
216
217
218
	pset *myset = get_type_map(tp, d_down);
	for (size_t i = 0; i < n_subtypes; ++i) {
		ir_type *stp    = get_class_subtype(tp, i);
		pset    *subset = get_type_map(stp, d_down);
Michael Beck's avatar
Michael Beck committed
219
220
221
222
223
		pset_insert_ptr(myset, stp);
		pset_insert_pset_ptr(myset, subset);
	}

	/* entities */
Matthias Braun's avatar
Matthias Braun committed
224
	for (size_t i = 0, n_members = get_class_n_members(tp); i < n_members; ++i) {
Michael Beck's avatar
Michael Beck committed
225
		ir_entity *mem = get_class_member(tp, i);
Michael Beck's avatar
Michael Beck committed
226
		size_t j, n_overwrittenby = get_entity_n_overwrittenby(mem);
Michael Beck's avatar
Michael Beck committed
227
228
229

		myset = get_entity_map(mem, d_down);
		for (j = 0; j < n_overwrittenby; ++j) {
Matthias Braun's avatar
Matthias Braun committed
230
231
			ir_entity *ov     = get_entity_overwrittenby(mem, j);
			pset      *subset = get_entity_map(ov, d_down);
Michael Beck's avatar
Michael Beck committed
232
233
234
235
236
237
238
239
			pset_insert_ptr(myset, ov);
			pset_insert_pset_ptr(myset, subset);
		}
	}

	mark_type_visited(tp);

	/* Walk up. */
Matthias Braun's avatar
Matthias Braun committed
240
241
	for (size_t i = 0, n_supertypes = get_class_n_supertypes(tp);
	     i < n_supertypes; ++i) {
Michael Beck's avatar
Michael Beck committed
242
243
244
245
246
		ir_type *stp = get_class_supertype(tp, i);
		if (get_type_visited(stp) < master_visited-1) {
			compute_down_closure(stp);
		}
	}
247
248
}

249
250
static void compute_up_closure(ir_type *tp)
{
251
	ir_visited_t master_visited = get_master_type_visited();
Michael Beck's avatar
Michael Beck committed
252
253
254
	set_type_visited(tp, master_visited-1);

	/* Recursive descend. */
Matthias Braun's avatar
Matthias Braun committed
255
256
	size_t n_supertypes = get_class_n_supertypes(tp);
	for (size_t i = 0; i < n_supertypes; ++i) {
Michael Beck's avatar
Michael Beck committed
257
258
259
260
261
262
263
		ir_type *stp = get_class_supertype(tp, i);
		if (get_type_visited(stp) < get_master_type_visited()-1) {
			compute_up_closure(stp);
		}
	}

	/* types */
Matthias Braun's avatar
Matthias Braun committed
264
265
266
267
	pset *myset = get_type_map(tp, d_up);
	for (size_t i = 0; i < n_supertypes; ++i) {
		ir_type *stp    = get_class_supertype(tp, i);
		pset    *subset = get_type_map(stp, d_up);
Michael Beck's avatar
Michael Beck committed
268
269
270
271
272
		pset_insert_ptr(myset, stp);
		pset_insert_pset_ptr(myset, subset);
	}

	/* entities */
Matthias Braun's avatar
Matthias Braun committed
273
274
275
276
277
278
279
	for (size_t i = 0, n_members = get_class_n_members(tp); i < n_members; ++i) {
		ir_entity *mem   = get_class_member(tp, i);
		pset      *myset = get_entity_map(mem, d_up);
		for (size_t j = 0, n_overwrites = get_entity_n_overwrites(mem);
		     j < n_overwrites; ++j) {
			ir_entity *ov     = get_entity_overwrites(mem, j);
			pset      *subset = get_entity_map(ov, d_up);
Michael Beck's avatar
Michael Beck committed
280
281
282
283
284
285
286
287
			pset_insert_pset_ptr(myset, subset);
			pset_insert_ptr(myset, ov);
		}
	}

	mark_type_visited(tp);

	/* Walk down. */
Matthias Braun's avatar
Matthias Braun committed
288
289
	for (size_t i = 0, n_subtypes = get_class_n_subtypes(tp);
	     i < n_subtypes; ++i) {
Michael Beck's avatar
Michael Beck committed
290
291
292
293
294
		ir_type *stp = get_class_subtype(tp, i);
		if (get_type_visited(stp) < master_visited-1) {
			compute_up_closure(stp);
		}
	}
295
296
}

297
298
void compute_inh_transitive_closure(void)
{
Michael Beck's avatar
Michael Beck committed
299
300
301
	free_inh_transitive_closure();

	/* The 'down' relation */
302
	irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
Michael Beck's avatar
Michael Beck committed
303
304
	inc_master_type_visited();  /* Inc twice: one if on stack, second if values computed. */
	inc_master_type_visited();
Matthias Braun's avatar
Matthias Braun committed
305
306
	size_t n_types = get_irp_n_types();
	for (size_t i = 0; i < n_types; ++i) {
Michael Beck's avatar
Michael Beck committed
307
308
		ir_type *tp = get_irp_type(i);
		if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
Matthias Braun's avatar
Matthias Braun committed
309
			size_t n_subtypes = get_class_n_subtypes(tp);
Michael Beck's avatar
Michael Beck committed
310
311
312
			int has_unmarked_subtype = 0;

			assert(get_type_visited(tp) < get_master_type_visited()-1);
Matthias Braun's avatar
Matthias Braun committed
313
			for (size_t j = 0; j < n_subtypes; ++j) {
Michael Beck's avatar
Michael Beck committed
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
				ir_type *stp = get_class_subtype(tp, j);
				if (type_not_visited(stp)) {
					has_unmarked_subtype = 1;
					break;
				}
			}

			/* This is a good starting point. */
			if (!has_unmarked_subtype)
				compute_down_closure(tp);
		}
	}

	/* The 'up' relation */
	inc_master_type_visited();
	inc_master_type_visited();
Matthias Braun's avatar
Matthias Braun committed
330
	for (size_t i = 0; i < n_types; ++i) {
Michael Beck's avatar
Michael Beck committed
331
332
		ir_type *tp = get_irp_type(i);
		if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
Matthias Braun's avatar
Matthias Braun committed
333
			size_t n_supertypes = get_class_n_supertypes(tp);
Michael Beck's avatar
Michael Beck committed
334
335
336
			int has_unmarked_supertype = 0;

			assert(get_type_visited(tp) < get_master_type_visited()-1);
Matthias Braun's avatar
Matthias Braun committed
337
			for (size_t j = 0; j < n_supertypes; ++j) {
Michael Beck's avatar
Michael Beck committed
338
339
340
341
342
343
344
345
346
347
348
349
350
351
				ir_type *stp = get_class_supertype(tp, j);
				if (type_not_visited(stp)) {
					has_unmarked_supertype = 1;
					break;
				}
			}

			/* This is a good starting point. */
			if (!has_unmarked_supertype)
				compute_up_closure(tp);
		}
	}

	irp->inh_trans_closure_state = inh_transitive_closure_valid;
352
	irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
353
354
}

355
356
void free_inh_transitive_closure(void)
{
Michael Beck's avatar
Michael Beck committed
357
	if (tr_inh_trans_set) {
358
		foreach_set(tr_inh_trans_set, tr_inh_trans_tp, elt) {
Michael Beck's avatar
Michael Beck committed
359
360
361
362
363
364
365
			del_pset(elt->directions[d_up]);
			del_pset(elt->directions[d_down]);
		}
		del_set(tr_inh_trans_set);
		tr_inh_trans_set = NULL;
	}
	irp->inh_trans_closure_state = inh_transitive_closure_none;
366
367
368
369
}

/* - subtype ------------------------------------------------------------- */

370
371
ir_type *get_class_trans_subtype_first(const ir_type *tp)
{
Michael Beck's avatar
Michael Beck committed
372
	assert_valid_state();
373
	return pset_first(ir_type, get_type_map(tp, d_down));
374
375
}

376
377
ir_type *get_class_trans_subtype_next(const ir_type *tp)
{
Michael Beck's avatar
Michael Beck committed
378
	assert_valid_state();
379
	return pset_next(ir_type, get_type_map(tp, d_down));
380
381
}

382
383
int is_class_trans_subtype(const ir_type *tp, const ir_type *subtp)
{
Michael Beck's avatar
Michael Beck committed
384
385
	assert_valid_state();
	return (pset_find_ptr(get_type_map(tp, d_down), subtp) != NULL);
386
387
}

388
389
/* - supertype ----------------------------------------------------------- */

390
391
ir_type *get_class_trans_supertype_first(const ir_type *tp)
{
Michael Beck's avatar
Michael Beck committed
392
	assert_valid_state();
393
	return pset_first(ir_type, get_type_map(tp, d_up));
394
395
}

396
397
ir_type *get_class_trans_supertype_next(const ir_type *tp)
{
Michael Beck's avatar
Michael Beck committed
398
	assert_valid_state();
399
	return pset_next(ir_type, get_type_map(tp, d_up));
400
401
402
403
}

/* - overwrittenby ------------------------------------------------------- */

404
405
ir_entity *get_entity_trans_overwrittenby_first(const ir_entity *ent)
{
Michael Beck's avatar
Michael Beck committed
406
	assert_valid_state();
407
	return pset_first(ir_entity, get_entity_map(ent, d_down));
408
409
}

410
411
ir_entity *get_entity_trans_overwrittenby_next(const ir_entity *ent)
{
Michael Beck's avatar
Michael Beck committed
412
	assert_valid_state();
413
	return pset_next(ir_entity, get_entity_map(ent, d_down));
414
415
416
417
418
}

/* - overwrites ---------------------------------------------------------- */


419
420
ir_entity *get_entity_trans_overwrites_first(const ir_entity *ent)
{
Michael Beck's avatar
Michael Beck committed
421
	assert_valid_state();
422
	return pset_first(ir_entity, get_entity_map(ent, d_up));
423
424
}

425
426
ir_entity *get_entity_trans_overwrites_next(const ir_entity *ent)
{
Michael Beck's avatar
Michael Beck committed
427
	assert_valid_state();
428
	return pset_next(ir_entity, get_entity_map(ent, d_up));
429
430
431
432
433
434
435
}


/* ----------------------------------------------------------------------- */
/* Classify pairs of types/entities in the inheritance relations.          */
/* ----------------------------------------------------------------------- */

436
/** Returns true if low is subclass of high. */
437
438
static int check_is_SubClass_of(ir_type *low, ir_type *high)
{
Michael Beck's avatar
Michael Beck committed
439
	/* depth first search from high downwards. */
Matthias Braun's avatar
Matthias Braun committed
440
441
	for (size_t i = 0, n_subtypes = get_class_n_subtypes(high);
	     i < n_subtypes; i++) {
Michael Beck's avatar
Michael Beck committed
442
443
444
445
446
447
		ir_type *stp = get_class_subtype(high, i);
		if (low == stp) return 1;
		if (is_SubClass_of(low, stp))
			return 1;
	}
	return 0;
448
449
}

450
451
int is_SubClass_of(ir_type *low, ir_type *high)
{
Michael Beck's avatar
Michael Beck committed
452
	assert(is_Class_type(low) && is_Class_type(high));
Matthias Braun's avatar
Matthias Braun committed
453
454
	if (low == high)
		return 1;
455

Michael Beck's avatar
Michael Beck committed
456
457
458
459
460
	if (get_irp_inh_transitive_closure_state() == inh_transitive_closure_valid) {
		pset *m = get_type_map(high, d_down);
		return pset_find_ptr(m, low) ? 1 : 0;
	}
	return check_is_SubClass_of(low, high);
461
462
}

463
464
int is_SubClass_ptr_of(ir_type *low, ir_type *high)
{
Michael Beck's avatar
Michael Beck committed
465
466
467
468
	while (is_Pointer_type(low) && is_Pointer_type(high)) {
		low  = get_pointer_points_to_type(low);
		high = get_pointer_points_to_type(high);
	}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
469

Michael Beck's avatar
Michael Beck committed
470
471
472
	if (is_Class_type(low) && is_Class_type(high))
		return is_SubClass_of(low, high);
	return 0;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
473
474
}

475
476
int is_overwritten_by(ir_entity *high, ir_entity *low)
{
Michael Beck's avatar
Michael Beck committed
477
478
479
480
481
	assert(is_entity(low) && is_entity(high));
	if (get_irp_inh_transitive_closure_state() == inh_transitive_closure_valid) {
		pset *m = get_entity_map(high, d_down);
		return pset_find_ptr(m, low) ? 1 : 0;
	}
482

Michael Beck's avatar
Michael Beck committed
483
	/* depth first search from high downwards. */
Matthias Braun's avatar
Matthias Braun committed
484
485
	for (size_t i = 0, n_overwrittenby = get_entity_n_overwrittenby(high);
	     i < n_overwrittenby; i++) {
Michael Beck's avatar
Michael Beck committed
486
487
488
489
490
491
		ir_entity *ov = get_entity_overwrittenby(high, i);
		if (low == ov) return 1;
		if (is_overwritten_by(low, ov))
			return 1;
	}
	return 0;
492
493
}

494
495
496
497
498
499
500
501
/** Resolve polymorphy in the inheritance relation.
 *
 * Returns the dynamically referenced entity if the static entity and the
 * dynamic type are given.
 * Search downwards in overwritten tree.
 *
 * Need two routines because I want to assert the result.
 */
502
503
static ir_entity *do_resolve_ent_polymorphy(ir_type *dynamic_class, ir_entity *static_ent)
{
504
	ir_type *owner = get_entity_owner(static_ent);
Matthias Braun's avatar
Matthias Braun committed
505
506
	if (owner == dynamic_class)
		return static_ent;
507
508
509

	// if the owner of the static_ent already is more special than the dynamic
	// type to check against - stop here.
Matthias Braun's avatar
Matthias Braun committed
510
511
	if (!is_SubClass_of(dynamic_class, owner))
		return NULL;
512

Matthias Braun's avatar
Matthias Braun committed
513
514
	for (size_t i = 0, n_overwrittenby = get_entity_n_overwrittenby(static_ent);
	     i < n_overwrittenby; ++i) {
Michael Beck's avatar
Michael Beck committed
515
516
517
518
		ir_entity *ent = get_entity_overwrittenby(static_ent, i);
		ent = do_resolve_ent_polymorphy(dynamic_class, ent);
		if (ent) return ent;
	}
519
520
521

	// No further specialization of static_ent has been found
	return static_ent;
522
523
}

524
525
ir_entity *resolve_ent_polymorphy(ir_type *dynamic_class, ir_entity *static_ent)
{
Matthias Braun's avatar
Matthias Braun committed
526
527
528
	assert(is_entity(static_ent));
	ir_entity *res = do_resolve_ent_polymorphy(dynamic_class, static_ent);
	assert(res != NULL);
Michael Beck's avatar
Michael Beck committed
529
	return res;
530
}