tr_inheritance.c 21.1 KB
Newer Older
Christian Würdig's avatar
Christian Würdig committed
1
/*
Michael Beck's avatar
Michael Beck committed
2
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
Christian Würdig's avatar
Christian Würdig committed
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 *
 * This file is part of libFirm.
 *
 * 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.
 *
 * 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.
 */

20
/**
Michael Beck's avatar
Michael Beck committed
21
22
23
24
 * @file    tr_inheritance.c
 * @brief   Utility routines for inheritance representation
 * @author  Goetz Lindenmaier
 * @version $Id$
25
 */
Matthias Braun's avatar
Matthias Braun committed
26
#include "config.h"
27

28
#include "debug.h"
29
#include "typerep.h"
30
#include "irgraph_t.h"
31
#include "irprog_t.h"
32
#include "irprintf.h"
33
34
#include "pset.h"
#include "set.h"
35
36
#include "irgwalk.h"
#include "irflag.h"
37

38
DEBUG_ONLY(static firm_dbg_module_t *dbg);
39
40
41
42
43

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

44
ident *default_mangle_inherited_name(ir_entity *super, ir_type *clss) {
45
	return id_mangle_u(new_id_from_str("inh"), id_mangle_u(get_type_ident(clss), get_entity_ident(super)));
46
47
}

Michael Beck's avatar
Michael Beck committed
48
/** Replicates all entities in all super classes that are not overwritten
Michael Beck's avatar
Michael Beck committed
49
    by an entity of this class. */
50
static void copy_entities_from_superclass(ir_type *clss, void *env)
51
{
Michael Beck's avatar
Michael Beck committed
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
	int i, j, k, l;
	int overwritten;
	ir_type *super, *inhenttype;
	ir_entity *inhent, *thisent;
	mangle_inherited_name_func *mfunc = *(mangle_inherited_name_func **)env;

	for(i = 0; i < get_class_n_supertypes(clss); i++) {
		super = get_class_supertype(clss, i);
		assert(is_Class_type(super) && "not a class");
		for(j = 0; j < get_class_n_members(super); j++) {
			inhent = get_class_member(super, j);
			inhenttype = get_entity_type(inhent);
			/* check whether inhent is already overwritten */
			overwritten = 0;
			for (k = 0; (k < get_class_n_members(clss)) && (overwritten == 0); k++) {
				thisent = get_class_member(clss, k);
				for(l = 0; l < get_entity_n_overwrites(thisent); l++) {
					if(inhent == get_entity_overwrites(thisent, l)) {
						/* overwritten - do not copy */
						overwritten = 1;
						break;
					}
				}
			}
			/* Inherit entity */
			if (!overwritten) {
				thisent = copy_entity_own(inhent, clss);
				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));
				if (get_entity_variability(inhent) == variability_constant) {
					assert(is_atomic_entity(inhent) &&  /* @@@ */
						"Inheritance of constant, compound entities not implemented");
					set_entity_variability(thisent, variability_constant);
					set_atomic_ent_value(thisent, get_atomic_ent_value(inhent));
				}
			}
		}
	}
92
93
94
95
96
97
98
}

/* Resolve implicit inheritance.
 *
 *  Resolves the implicit inheritance supplied by firm.
 */
void resolve_inheritance(mangle_inherited_name_func *mfunc) {
Michael Beck's avatar
Michael Beck committed
99
100
101
	if (!mfunc)
		mfunc = default_mangle_inherited_name;
	class_walk_super2sub(copy_entities_from_superclass, NULL, (void *)&mfunc);
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
}


/* ----------------------------------------------------------------------- */
/* 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_'.                                              */
/* ----------------------------------------------------------------------- */

void                        set_irp_inh_transitive_closure_state(inh_transitive_closure_state s) {
Michael Beck's avatar
Michael Beck committed
119
	irp->inh_trans_closure_state = s;
120
121
}
void                        invalidate_irp_inh_transitive_closure_state(void) {
Michael Beck's avatar
Michael Beck committed
122
123
	if (irp->inh_trans_closure_state == inh_transitive_closure_valid)
		irp->inh_trans_closure_state = inh_transitive_closure_invalid;
124
125
}
inh_transitive_closure_state get_irp_inh_transitive_closure_state(void) {
Michael Beck's avatar
Michael Beck committed
126
	return irp->inh_trans_closure_state;
127
128
129
}

static void assert_valid_state(void) {
Michael Beck's avatar
Michael Beck committed
130
131
	assert(irp->inh_trans_closure_state == inh_transitive_closure_valid ||
	       irp->inh_trans_closure_state == inh_transitive_closure_invalid);
132
133
134
135
136
137
138
139
140
141
}

/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
/* 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...                                         */
/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */

142
typedef enum {
Michael Beck's avatar
Michael Beck committed
143
144
	d_up   = 0,
	d_down = 1,
145
146
} dir;

147
typedef struct {
Michael Beck's avatar
Michael Beck committed
148
	const firm_kind *kind;   /**< An entity or type. */
Michael Beck's avatar
Michael Beck committed
149
	pset *directions[2];
150
151
152
153
154
} 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
155
156
157
/**
 * Compare two tr_inh_trans_tp entries.
 */
158
static int tr_inh_trans_cmp(const void *e1, const void *e2, size_t size) {
Michael Beck's avatar
Michael Beck committed
159
160
	const tr_inh_trans_tp *ef1 = e1;
	const tr_inh_trans_tp *ef2 = e2;
Matthias Braun's avatar
Matthias Braun committed
161
162
	(void) size;

Michael Beck's avatar
Michael Beck committed
163
	return ef1->kind != ef2->kind;
164
165
}

Michael Beck's avatar
Michael Beck committed
166
167
168
/**
 * calculate the hash value of an tr_inh_trans_tp
 */
169
static inline unsigned int tr_inh_trans_hash(const tr_inh_trans_tp *v) {
Michael Beck's avatar
Michael Beck committed
170
	return HASH_PTR(v->kind);
171
172
173
}

/* This always completes successfully. */
Michael Beck's avatar
Michael Beck committed
174
static tr_inh_trans_tp *get_firm_kind_entry(const firm_kind *k) {
Michael Beck's avatar
Michael Beck committed
175
176
	tr_inh_trans_tp a, *found;
	a.kind = k;
177

Michael Beck's avatar
Michael Beck committed
178
	if (!tr_inh_trans_set) tr_inh_trans_set = new_set(tr_inh_trans_cmp, 128);
179

Michael Beck's avatar
Michael Beck committed
180
181
182
183
184
185
186
	found = set_find(tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
	if (!found) {
		a.directions[d_up]   = pset_new_ptr(16);
		a.directions[d_down] = pset_new_ptr(16);
		found = set_insert(tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
	}
	return found;
187
188
}

Michael Beck's avatar
Michael Beck committed
189
static pset *get_entity_map(const ir_entity *ent, dir d) {
Michael Beck's avatar
Michael Beck committed
190
	tr_inh_trans_tp *found;
Michael Beck's avatar
Michael Beck committed
191

Michael Beck's avatar
Michael Beck committed
192
	assert(is_entity(ent));
Michael Beck's avatar
Michael Beck committed
193
	found = get_firm_kind_entry((const firm_kind *)ent);
Michael Beck's avatar
Michael Beck committed
194
	return found->directions[d];
195
}
Michael Beck's avatar
Michael Beck committed
196

Michael Beck's avatar
Michael Beck committed
197
static pset *get_type_map(const ir_type *tp, dir d) {
Michael Beck's avatar
Michael Beck committed
198
	tr_inh_trans_tp *found;
Michael Beck's avatar
Michael Beck committed
199

Michael Beck's avatar
Michael Beck committed
200
	assert(is_type(tp));
Michael Beck's avatar
Michael Beck committed
201
	found = get_firm_kind_entry((const firm_kind *)tp);
Michael Beck's avatar
Michael Beck committed
202
	return found->directions[d];
203
204
205
}


Michael Beck's avatar
Michael Beck committed
206
207
208
/**
 * Walk over all types reachable from tp in the sub/supertype
 * relation and compute the closure for the two downwards directed
209
210
211
212
213
214
215
216
217
218
219
220
221
 * 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 ... */
222
static void compute_down_closure(ir_type *tp) {
Michael Beck's avatar
Michael Beck committed
223
224
	pset *myset, *subset;
	int i, n_subtypes, n_members, n_supertypes;
225
	ir_visited_t master_visited = get_master_type_visited();
Michael Beck's avatar
Michael Beck committed
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273

	assert(is_Class_type(tp));

	set_type_visited(tp, master_visited-1);

	/* Recursive descend. */
	n_subtypes = get_class_n_subtypes(tp);
	for (i = 0; i < n_subtypes; ++i) {
		ir_type *stp = get_class_subtype(tp, i);
		if (get_type_visited(stp) < master_visited-1) {
			compute_down_closure(stp);
		}
	}

	/* types */
	myset = get_type_map(tp, d_down);
	for (i = 0; i < n_subtypes; ++i) {
		ir_type *stp = get_class_subtype(tp, i);
		subset = get_type_map(stp, d_down);
		pset_insert_ptr(myset, stp);
		pset_insert_pset_ptr(myset, subset);
	}

	/* entities */
	n_members = get_class_n_members(tp);
	for (i = 0; i < n_members; ++i) {
		ir_entity *mem = get_class_member(tp, i);
		int j, n_overwrittenby = get_entity_n_overwrittenby(mem);

		myset = get_entity_map(mem, d_down);
		for (j = 0; j < n_overwrittenby; ++j) {
			ir_entity *ov = get_entity_overwrittenby(mem, j);
			subset = get_entity_map(ov, d_down);
			pset_insert_ptr(myset, ov);
			pset_insert_pset_ptr(myset, subset);
		}
	}

	mark_type_visited(tp);

	/* Walk up. */
	n_supertypes = get_class_n_supertypes(tp);
	for (i = 0; i < n_supertypes; ++i) {
		ir_type *stp = get_class_supertype(tp, i);
		if (get_type_visited(stp) < master_visited-1) {
			compute_down_closure(stp);
		}
	}
274
275
}

276
static void compute_up_closure(ir_type *tp) {
Michael Beck's avatar
Michael Beck committed
277
278
	pset *myset, *subset;
	int i, n_subtypes, n_members, n_supertypes;
279
	ir_visited_t master_visited = get_master_type_visited();
Michael Beck's avatar
Michael Beck committed
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327

	assert(is_Class_type(tp));

	set_type_visited(tp, master_visited-1);

	/* Recursive descend. */
	n_supertypes = get_class_n_supertypes(tp);
	for (i = 0; i < n_supertypes; ++i) {
		ir_type *stp = get_class_supertype(tp, i);
		if (get_type_visited(stp) < get_master_type_visited()-1) {
			compute_up_closure(stp);
		}
	}

	/* types */
	myset = get_type_map(tp, d_up);
	for (i = 0; i < n_supertypes; ++i) {
		ir_type *stp = get_class_supertype(tp, i);
		subset = get_type_map(stp, d_up);
		pset_insert_ptr(myset, stp);
		pset_insert_pset_ptr(myset, subset);
	}

	/* entities */
	n_members = get_class_n_members(tp);
	for (i = 0; i < n_members; ++i) {
		ir_entity *mem = get_class_member(tp, i);
		int j, n_overwrites = get_entity_n_overwrites(mem);

		myset = get_entity_map(mem, d_up);
		for (j = 0; j < n_overwrites; ++j) {
			ir_entity *ov = get_entity_overwrites(mem, j);
			subset = get_entity_map(ov, d_up);
			pset_insert_pset_ptr(myset, subset);
			pset_insert_ptr(myset, ov);
		}
	}

	mark_type_visited(tp);

	/* Walk down. */
	n_subtypes = get_class_n_subtypes(tp);
	for (i = 0; i < n_subtypes; ++i) {
		ir_type *stp = get_class_subtype(tp, i);
		if (get_type_visited(stp) < master_visited-1) {
			compute_up_closure(stp);
		}
	}
328
329
330
331
332
333
334
335
}

/** Compute the transitive closure of the subclass/superclass and
 *  overwrites/overwrittenby relation.
 *
 *  This function walks over the ir (O(#types+#entities)) to compute the
 *  transitive closure.    */
void compute_inh_transitive_closure(void) {
Michael Beck's avatar
Michael Beck committed
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
	int i, n_types = get_irp_n_types();
	free_inh_transitive_closure();

	/* The 'down' relation */
	inc_master_type_visited();  /* Inc twice: one if on stack, second if values computed. */
	inc_master_type_visited();
	for (i = 0; i < n_types; ++i) {
		ir_type *tp = get_irp_type(i);
		if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
			int j, n_subtypes = get_class_n_subtypes(tp);
			int has_unmarked_subtype = 0;

			assert(get_type_visited(tp) < get_master_type_visited()-1);
			for (j = 0; j < n_subtypes; ++j) {
				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();
	for (i = 0; i < n_types; ++i) {
		ir_type *tp = get_irp_type(i);
		if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
			int j, n_supertypes = get_class_n_supertypes(tp);
			int has_unmarked_supertype = 0;

			assert(get_type_visited(tp) < get_master_type_visited()-1);
			for (j = 0; j < n_supertypes; ++j) {
				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;
388
389
390
391
}

/** Free memory occupied by the transitive closure information. */
void free_inh_transitive_closure(void) {
Michael Beck's avatar
Michael Beck committed
392
393
394
395
396
397
398
399
400
401
	if (tr_inh_trans_set) {
		tr_inh_trans_tp *elt;
		for (elt = set_first(tr_inh_trans_set); elt; elt = set_next(tr_inh_trans_set)) {
			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;
402
403
404
405
}

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

Michael Beck's avatar
Michael Beck committed
406
ir_type *get_class_trans_subtype_first(const ir_type *tp) {
Michael Beck's avatar
Michael Beck committed
407
408
	assert_valid_state();
	return pset_first(get_type_map(tp, d_down));
409
410
}

Michael Beck's avatar
Michael Beck committed
411
ir_type *get_class_trans_subtype_next(const ir_type *tp) {
Michael Beck's avatar
Michael Beck committed
412
413
	assert_valid_state();
	return pset_next(get_type_map(tp, d_down));
414
415
}

Michael Beck's avatar
Michael Beck committed
416
int is_class_trans_subtype(const ir_type *tp, const ir_type *subtp) {
Michael Beck's avatar
Michael Beck committed
417
418
	assert_valid_state();
	return (pset_find_ptr(get_type_map(tp, d_down), subtp) != NULL);
419
420
}

421
422
/* - supertype ----------------------------------------------------------- */

Michael Beck's avatar
Michael Beck committed
423
ir_type *get_class_trans_supertype_first(const ir_type *tp) {
Michael Beck's avatar
Michael Beck committed
424
425
	assert_valid_state();
	return pset_first(get_type_map(tp, d_up));
426
427
}

Michael Beck's avatar
Michael Beck committed
428
ir_type *get_class_trans_supertype_next(const ir_type *tp) {
Michael Beck's avatar
Michael Beck committed
429
430
	assert_valid_state();
	return pset_next(get_type_map(tp, d_up));
431
432
433
434
}

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

Michael Beck's avatar
Michael Beck committed
435
ir_entity *get_entity_trans_overwrittenby_first(const ir_entity *ent) {
Michael Beck's avatar
Michael Beck committed
436
437
	assert_valid_state();
	return pset_first(get_entity_map(ent, d_down));
438
439
}

Michael Beck's avatar
Michael Beck committed
440
ir_entity *get_entity_trans_overwrittenby_next(const ir_entity *ent) {
Michael Beck's avatar
Michael Beck committed
441
442
	assert_valid_state();
	return pset_next(get_entity_map(ent, d_down));
443
444
445
446
447
448
}

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


/** Iterate over all transitive overwritten entities. */
Michael Beck's avatar
Michael Beck committed
449
ir_entity *get_entity_trans_overwrites_first(const ir_entity *ent) {
Michael Beck's avatar
Michael Beck committed
450
451
	assert_valid_state();
	return pset_first(get_entity_map(ent, d_up));
452
453
}

Michael Beck's avatar
Michael Beck committed
454
ir_entity *get_entity_trans_overwrites_next(const ir_entity *ent) {
Michael Beck's avatar
Michael Beck committed
455
456
	assert_valid_state();
	return pset_next(get_entity_map(ent, d_up));
457
458
459
460
461
462
463
}


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

464
465
/** Returns true if low is subclass of high. */
static int check_is_SubClass_of(ir_type *low, ir_type *high) {
Michael Beck's avatar
Michael Beck committed
466
	int i, n_subtypes;
467

Michael Beck's avatar
Michael Beck committed
468
469
470
471
472
473
474
475
476
	/* depth first search from high downwards. */
	n_subtypes = get_class_n_subtypes(high);
	for (i = 0; i < n_subtypes; i++) {
		ir_type *stp = get_class_subtype(high, i);
		if (low == stp) return 1;
		if (is_SubClass_of(low, stp))
			return 1;
	}
	return 0;
477
478
}

479
480
/* Returns true if low is subclass of high. */
int is_SubClass_of(ir_type *low, ir_type *high) {
Michael Beck's avatar
Michael Beck committed
481
	assert(is_Class_type(low) && is_Class_type(high));
482

Michael Beck's avatar
Michael Beck committed
483
	if (low == high) return 1;
484

Michael Beck's avatar
Michael Beck committed
485
486
487
488
489
	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);
490
491
}

Götz Lindenmaier's avatar
Götz Lindenmaier committed
492
493
494
495
496
497
498

/* Subclass check for pointers to classes.
 *
 *  Dereferences at both types the same amount of pointer types (as
 *  many as possible).  If the remaining types are both class types
 *  and subclasses, returns true, else false.  Can also be called with
 *  two class types.  */
499
int is_SubClass_ptr_of(ir_type *low, ir_type *high) {
Michael Beck's avatar
Michael Beck committed
500
501
502
503
	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
504

Michael Beck's avatar
Michael Beck committed
505
506
507
	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
508
509
}

510
int is_overwritten_by(ir_entity *high, ir_entity *low) {
Michael Beck's avatar
Michael Beck committed
511
512
	int i, n_overwrittenby;
	assert(is_entity(low) && is_entity(high));
513

Michael Beck's avatar
Michael Beck committed
514
515
516
517
	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;
	}
518

Michael Beck's avatar
Michael Beck committed
519
520
521
522
523
524
525
526
527
	/* depth first search from high downwards. */
	n_overwrittenby = get_entity_n_overwrittenby(high);
	for (i = 0; i < n_overwrittenby; i++) {
		ir_entity *ov = get_entity_overwrittenby(high, i);
		if (low == ov) return 1;
		if (is_overwritten_by(low, ov))
			return 1;
	}
	return 0;
528
529
}

530
531
532
533
534
535
536
537
/** 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.
 */
538
static ir_entity *do_resolve_ent_polymorphy(ir_type *dynamic_class, ir_entity *static_ent) {
Michael Beck's avatar
Michael Beck committed
539
	int i, n_overwrittenby;
540

Michael Beck's avatar
Michael Beck committed
541
	if (get_entity_owner(static_ent) == dynamic_class) return static_ent;
542

Michael Beck's avatar
Michael Beck committed
543
544
545
546
547
548
549
	n_overwrittenby = get_entity_n_overwrittenby(static_ent);
	for (i = 0; i < n_overwrittenby; ++i) {
		ir_entity *ent = get_entity_overwrittenby(static_ent, i);
		ent = do_resolve_ent_polymorphy(dynamic_class, ent);
		if (ent) return ent;
	}
	return NULL;
550
551
552
553
554
555
556
}

/* 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. */
557
ir_entity *resolve_ent_polymorphy(ir_type *dynamic_class, ir_entity *static_ent) {
Michael Beck's avatar
Michael Beck committed
558
559
	ir_entity *res;
	assert(static_ent && is_entity(static_ent));
560

Michael Beck's avatar
Michael Beck committed
561
562
	res = do_resolve_ent_polymorphy(dynamic_class, static_ent);
	assert(res);
563

Michael Beck's avatar
Michael Beck committed
564
	return res;
565
}
566
567
568
569
570
571
572
573
574
575



/* ----------------------------------------------------------------------- */
/* Class cast state handling.                                              */
/* ----------------------------------------------------------------------- */

/* - State handling. ----------------------------------------- */

void set_irg_class_cast_state(ir_graph *irg, ir_class_cast_state s) {
Michael Beck's avatar
Michael Beck committed
576
577
	if (get_irp_class_cast_state() > s) set_irp_class_cast_state(s);
	irg->class_cast_state = s;
578
579
580
}

ir_class_cast_state get_irg_class_cast_state(ir_graph *irg) {
Michael Beck's avatar
Michael Beck committed
581
	return irg->class_cast_state;
582
583
584
}

void set_irp_class_cast_state(ir_class_cast_state s) {
Michael Beck's avatar
Michael Beck committed
585
#ifndef NDEBUG
Michael Beck's avatar
Michael Beck committed
586
	int i;
Michael Beck's avatar
Michael Beck committed
587
	for (i = get_irp_n_irgs() - 1; i >= 0; --i)
Michael Beck's avatar
Michael Beck committed
588
		assert(get_irg_class_cast_state(get_irp_irg(i)) >= s);
Michael Beck's avatar
Michael Beck committed
589
#endif
Michael Beck's avatar
Michael Beck committed
590
	irp->class_cast_state = s;
591
592
593
}

ir_class_cast_state get_irp_class_cast_state(void) {
Michael Beck's avatar
Michael Beck committed
594
	return irp->class_cast_state;
595
596
597
598
}

char *get_class_cast_state_string(ir_class_cast_state s) {
#define X(a)    case a: return #a
Michael Beck's avatar
Michael Beck committed
599
600
601
602
603
604
605
	switch(s) {
	X(ir_class_casts_any);
	X(ir_class_casts_transitive);
	X(ir_class_casts_normalized);
	X(ir_class_casts_state_max);
	default: return "invalid class cast state";
	}
606
607
608
609
610
611
#undef X
}

/* - State verification. ------------------------------------- */

typedef struct ccs_env {
Michael Beck's avatar
Michael Beck committed
612
613
	ir_class_cast_state expected_state;
	ir_class_cast_state worst_situation;
614
615
616
} ccs_env;

void verify_irn_class_cast_state(ir_node *n, void *env) {
Michael Beck's avatar
Michael Beck committed
617
618
619
620
621
	ccs_env             *ccs = (ccs_env *)env;
	ir_class_cast_state this_state = ir_class_casts_any;
	ir_type             *fromtype, *totype;
	int                 ref_depth = 0;

622
	if (!is_Cast(n)) return;
Michael Beck's avatar
Michael Beck committed
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648

	fromtype = get_irn_typeinfo_type(get_Cast_op(n));
	totype   = get_Cast_type(n);

	while (is_Pointer_type(totype) && is_Pointer_type(fromtype)) {
		totype   = get_pointer_points_to_type(totype);
		fromtype = get_pointer_points_to_type(fromtype);
		ref_depth++;
	}

	if (!is_Class_type(totype)) return;

	if (is_SubClass_of(totype, fromtype) ||
		is_SubClass_of(fromtype, totype)   ) {
		this_state = ir_class_casts_transitive;
		if ((get_class_supertype_index(totype, fromtype) != -1) ||
		    (get_class_supertype_index(fromtype, totype) != -1) ||
		    fromtype == totype) {
			/*   Das ist doch alt?  Aus dem cvs aufgetaucht ...
			if ((get_class_supertype_index(totype, fromtype) == -1) &&
			    (get_class_supertype_index(fromtype, totype) == -1) ) {  */
			this_state = ir_class_casts_normalized;
		}
	}

	if (!(this_state >= ccs->expected_state)) {
649
650
651
652
		ir_printf("  Node is %+F\n", n);
		ir_printf("    totype   %+F\n", totype);
		ir_printf("    fromtype %+F\n", fromtype);
		ir_printf("    this_state: %s, exp. state: %s\n",
Michael Beck's avatar
Michael Beck committed
653
654
655
656
657
658
659
660
			get_class_cast_state_string(this_state),
			get_class_cast_state_string(ccs->expected_state));
		assert(this_state >= ccs->expected_state &&
			"invalid state class cast state setting in graph");
	}

	if (this_state < ccs->worst_situation)
		ccs->worst_situation = this_state;
661
662
}

Michael Beck's avatar
Michael Beck committed
663
/** Verify that the graph meets requirements of state set. */
664
void verify_irg_class_cast_state(ir_graph *irg) {
Michael Beck's avatar
Michael Beck committed
665
	ccs_env env;
666

667
668
	FIRM_DBG_REGISTER(dbg, "firm.tr.inheritance");

Michael Beck's avatar
Michael Beck committed
669
670
	env.expected_state  = get_irg_class_cast_state(irg);
	env.worst_situation = ir_class_casts_normalized;
671

Michael Beck's avatar
Michael Beck committed
672
	irg_walk_graph(irg, NULL, verify_irn_class_cast_state, &env);
673

674
675
676
677
	if ((env.worst_situation > env.expected_state)) {
		DB((dbg, LEVEL_1, "Note:  class cast state is set lower than reqired "
		    "in graph \n\t%+F\n", irg));
		DB((dbg, LEVEL_1, "       state is %s, reqired is %s\n",
Michael Beck's avatar
Michael Beck committed
678
			get_class_cast_state_string(env.expected_state),
679
			get_class_cast_state_string(env.worst_situation)));
Michael Beck's avatar
Michael Beck committed
680
	}
681
}