3 * @file tp_inheritance.c
5 * Project: libFIRM <br>
6 * File name: ir/tr/tp_inheritance.c <br>
7 * Purpose: Utility routines for inheritance representation <br>
8 * Author: Goetz Lindenmaier <br>
11 * Copyright: (c) 2001-2005 Universität Karlsruhe <br>
12 * Licence: This file protected by GPL - GNU GENERAL PUBLIC LICENSE. <br>
17 * @see type.h entity.h
31 /* ----------------------------------------------------------------------- */
32 /* Resolve implicit inheritance. */
33 /* ----------------------------------------------------------------------- */
35 ident *default_mangle_inherited_name(entity *super, type *clss) {
36 return mangle_u(get_type_ident(clss), get_entity_ident(super));
39 /** Replicates all entities in all super classes that are not overwritten
40 by an entity of this class. */
41 static void copy_entities_from_superclass(type *clss, void *env)
45 type *super, *inhenttype;
46 entity *inhent, *thisent;
47 mangle_inherited_name_func *mfunc = (mangle_inherited_name_func *)env;
49 for(i = 0; i < get_class_n_supertypes(clss); i++) {
50 super = get_class_supertype(clss, i);
51 assert(is_Class_type(super) && "not a class");
52 for(j = 0; j < get_class_n_members(super); j++) {
53 inhent = get_class_member(super, j);
54 inhenttype = get_entity_type(inhent);
55 /* check whether inhent is already overwritten */
57 for (k = 0; (k < get_class_n_members(clss)) && (overwritten == 0); k++) {
58 thisent = get_class_member(clss, k);
59 for(l = 0; l < get_entity_n_overwrites(thisent); l++) {
60 if(inhent == get_entity_overwrites(thisent, l)) {
61 /* overwritten - do not copy */
69 thisent = copy_entity_own(inhent, clss);
70 add_entity_overwrites(thisent, inhent);
71 set_entity_peculiarity(thisent, peculiarity_inherited);
72 set_entity_ld_ident(thisent, mfunc(inhent, clss));
73 if (get_entity_variability(inhent) == variability_constant) {
74 assert(is_atomic_entity(inhent) && /* @@@ */
75 "Inheritance of constant, compound entities not implemented");
76 set_entity_variability(thisent, variability_constant);
77 set_atomic_ent_value(thisent, get_atomic_ent_value(inhent));
84 /* Resolve implicit inheritance.
86 * Resolves the implicit inheritance supplied by firm.
88 void resolve_inheritance(mangle_inherited_name_func *mfunc) {
90 mfunc = default_mangle_inherited_name;
91 class_walk_super2sub(copy_entities_from_superclass, NULL, (void *)mfunc);
95 /* ----------------------------------------------------------------------- */
96 /* The transitive closure of the subclass/superclass and */
97 /* overwrites/overwrittenby relation. */
99 /* A walk over the ir (O(#types+#entities)) computes the transitive */
100 /* closure. Adding a new type/entity or changing the basic relations in */
101 /* some other way invalidates the transitive closure, i.e., it is not */
102 /* updated by the basic functions. */
104 /* All functions are named as their counterparts for the basic relations, */
105 /* adding the infix 'trans_'. */
106 /* ----------------------------------------------------------------------- */
108 void set_irp_inh_transitive_closure_state(inh_transitive_closure_state s) {
109 irp->inh_trans_closure_state = s;
111 void invalidate_irp_inh_transitive_closure_state(void) {
112 if (irp->inh_trans_closure_state == inh_transitive_closure_valid)
113 irp->inh_trans_closure_state = inh_transitive_closure_invalid;
115 inh_transitive_closure_state get_irp_inh_transitive_closure_state(void) {
116 return irp->inh_trans_closure_state;
119 static void assert_valid_state(void) {
120 assert(irp->inh_trans_closure_state == inh_transitive_closure_valid ||
121 irp->inh_trans_closure_state == inh_transitive_closure_invalid);
124 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
125 /* There is a set that extends each entity/type with two new */
126 /* fields: one for the upwards directed relation: 'up' (supertype, */
127 /* overwrites) and one for the downwards directed relation: 'down' (sub- */
128 /* type, overwrittenby. These fields contain psets (and maybe later */
129 /* arrays) listing all subtypes... */
130 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
133 firm_kind *kind; /* An entity or type. */
138 /* We use this set for all types and entities. */
139 static set *tr_inh_trans_set = NULL;
141 static int tr_inh_trans_cmp(const void *e1, const void *e2, size_t size) {
142 tr_inh_trans_tp *ef1 = (tr_inh_trans_tp *)e1;
143 tr_inh_trans_tp *ef2 = (tr_inh_trans_tp *)e2;
144 return (ef1->kind != ef2->kind);
147 static INLINE unsigned int tr_inh_trans_hash(void *e) {
148 void *v = (void *) ((tr_inh_trans_tp *)e)->kind;
157 /* This always completes successfully. */
158 static tr_inh_trans_tp* get_firm_kind_entry(firm_kind *k) {
159 tr_inh_trans_tp a, *found;
162 if (!tr_inh_trans_set) tr_inh_trans_set = new_set(tr_inh_trans_cmp, 128);
164 found = set_find(tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
166 a.up = pset_new_ptr(16);
167 a.down = pset_new_ptr(16);
168 found = set_insert(tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
173 static pset *get_entity_map(entity *ent, dir d) {
174 tr_inh_trans_tp *found;
176 assert(is_entity(ent));
177 found = get_firm_kind_entry((firm_kind *)ent);
178 return (d == d_up) ? found->up : found->down;
181 static void add_entity_map(entity *ent, dir d, entity *new) {
182 tr_inh_trans_tp *found;
184 assert(is_entity(ent) && is_entity(new));
185 tr_inh_trans_tp *found = get_firm_kind_entry((firm_kind *)ent);
187 pset_insert_ptr(found->up, new);
189 pset_insert_ptr(found->down, new);
192 static pset *get_type_map(type *tp, dir d) {
193 tr_inh_trans_tp *found;
196 found = get_firm_kind_entry((firm_kind *)tp);
197 return (d == d_up) ? found->up : found->down;
200 static void add_type_map(type *tp, dir d, type *new) {
201 tr_inh_trans_tp *found;
203 assert(is_type(tp) && is_type(new));
204 found = get_firm_kind_entry((firm_kind *)tp);
205 if (d == d_up) pset_insert_ptr(found->up, new);
206 else pset_insert_ptr(found->down, new);
212 * Walk over all types reachable from tp in the sub/supertype
213 * relation and compute the closure for the two downwards directed
216 * The walk in the dag formed by the relation is tricky: We must visit
217 * all subtypes before visiting the supertypes. So we first walk down.
218 * Then we can compute the closure for this type. Then we walk up.
219 * As we call ourselves recursive, and walk in both directions, there
220 * can be cycles. So we have to make sure, that if we visit a node
221 * a second time (in a walk up) we do nothing. For this we increment
222 * the master visited flag twice.
223 * If the type is marked with master_flag_visited-1 it is on the stack.
224 * If it is marked with master_flag_visited it is fully processed.
226 * Well, we still miss some candidates ... */
227 static void compute_down_closure(type *tp) {
228 pset *myset, *subset;
229 int i, n_subtypes, n_members, n_supertypes;
230 unsigned long master_visited = get_master_type_visited();
232 assert(is_Class_type(tp));
234 set_type_visited(tp, master_visited-1);
236 /* Recursive descend. */
237 n_subtypes = get_class_n_subtypes(tp);
238 for (i = 0; i < n_subtypes; ++i) {
239 type *stp = get_class_subtype(tp, i);
240 if (type_not_visited(stp)) {
241 assert(get_type_visited(tp) < master_visited-1);
242 compute_down_closure(stp);
247 myset = get_type_map(tp, d_down);
248 for (i = 0; i < n_subtypes; ++i) {
249 type *stp = get_class_subtype(tp, i);
250 subset = get_type_map(stp, d_down);
251 pset_insert_ptr(myset, stp);
252 pset_insert_pset_ptr(myset, subset);
256 n_members = get_class_n_members(tp);
257 for (i = 0; i < n_members; ++i) {
258 entity *mem = get_class_member(tp, i);
259 int j, n_overwrittenby = get_entity_n_overwrittenby(mem);
261 myset = get_entity_map(mem, d_down);
262 for (j = 0; j > n_overwrittenby; ++j) {
263 entity *ov = get_entity_overwrittenby(mem, j);
264 subset = get_entity_map(ov, d_down);
265 pset_insert_pset_ptr(myset, subset);
266 pset_insert_ptr(myset, ov);
270 mark_type_visited(tp);
273 n_supertypes = get_class_n_supertypes(tp);
274 for (i = 0; i < n_supertypes; ++i) {
275 type *stp = get_class_supertype(tp, i);
276 if (get_type_visited(tp) < master_visited-1) {
277 compute_down_closure(stp);
282 static void compute_up_closure(type *tp) {
283 pset *myset, *subset;
284 int i, n_subtypes, n_members, n_supertypes;
285 int master_visited = get_master_type_visited();
287 assert(is_Class_type(tp));
289 set_type_visited(tp, master_visited-1);
291 /* Recursive descend. */
292 n_supertypes = get_class_n_supertypes(tp);
293 for (i = 0; i < n_supertypes; ++i) {
294 type *stp = get_class_supertype(tp, i);
295 if (type_not_visited(stp)) {
296 assert(get_type_visited(tp) < get_master_type_visited()-1);
297 compute_up_closure(stp);
302 myset = get_type_map(tp, d_up);
303 for (i = 0; i < n_supertypes; ++i) {
304 type *stp = get_class_supertype(tp, i);
305 subset = get_type_map(stp, d_up);
306 pset_insert_ptr(myset, stp);
307 pset_insert_pset_ptr(myset, subset);
311 n_members = get_class_n_members(tp);
312 for (i = 0; i < n_members; ++i) {
313 entity *mem = get_class_member(tp, i);
314 int j, n_overwrites = get_entity_n_overwrites(mem);
316 myset = get_entity_map(mem, d_up);
317 for (j = 0; j > n_overwrites; ++j) {
318 entity *ov = get_entity_overwrites(mem, j);
319 subset = get_entity_map(ov, d_up);
320 pset_insert_pset_ptr(myset, subset);
321 pset_insert_ptr(myset, ov);
325 mark_type_visited(tp);
328 n_subtypes = get_class_n_subtypes(tp);
329 for (i = 0; i < n_subtypes; ++i) {
330 type *stp = get_class_subtype(tp, i);
331 if (get_type_visited(tp) < master_visited-1) {
332 compute_up_closure(stp);
337 /** Compute the transitive closure of the subclass/superclass and
338 * overwrites/overwrittenby relation.
340 * This function walks over the ir (O(#types+#entities)) to compute the
341 * transitive closure. */
342 void compute_inh_transitive_closure(void) {
343 int i, n_types = get_irp_n_types();
344 free_inh_transitive_closure();
346 /* The 'down' relation */
347 inc_master_type_visited(); /* Inc twice: one if on stack, second if values computed. */
348 inc_master_type_visited();
349 for (i = 0; i < n_types; ++i) {
350 type *tp = get_irp_type(i);
351 if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
352 int j, n_subtypes = get_class_n_subtypes(tp);
353 int has_unmarked_subtype = false;
355 assert(get_type_visited(tp) < get_master_type_visited()-1);
356 for (j = 0; j < n_subtypes && !has_unmarked_subtype; ++j) {
357 type *stp = get_class_subtype(tp, j);
358 if (type_not_visited(stp)) has_unmarked_subtype = true;
361 /* This is a good starting point. */
362 if (!has_unmarked_subtype)
363 compute_down_closure(tp);
367 /* The 'up' relation */
368 inc_master_type_visited();
369 inc_master_type_visited();
370 for (i = 0; i < n_types; ++i) {
371 type *tp = get_irp_type(i);
372 if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
373 int j, n_supertypes = get_class_n_supertypes(tp);
374 int has_unmarked_supertype = false;
376 assert(get_type_visited(tp) < get_master_type_visited()-1);
377 for (j = 0; j < n_supertypes && !has_unmarked_supertype; ++j) {
378 type *stp = get_class_supertype(tp, j);
379 if (type_not_visited(stp)) has_unmarked_supertype = true;
382 /* This is a good starting point. */
383 if (!has_unmarked_supertype)
384 compute_up_closure(tp);
388 irp->inh_trans_closure_state = inh_transitive_closure_valid;
391 /** Free memory occupied by the transitive closure information. */
392 void free_inh_transitive_closure(void) {
393 if (tr_inh_trans_set) {
394 tr_inh_trans_tp *elt;
395 for (elt = set_first(tr_inh_trans_set); elt; elt = set_next(tr_inh_trans_set)) {
399 del_set(tr_inh_trans_set);
400 tr_inh_trans_set = NULL;
402 irp->inh_trans_closure_state = inh_transitive_closure_none;
405 /* - subtype ------------------------------------------------------------- */
407 type *get_class_trans_subtype_first(type *tp) {
408 assert_valid_state();
409 return pset_first(get_type_map(tp, d_down));
412 type *get_class_trans_subtype_next (type *tp) {
413 assert_valid_state();
414 return pset_next(get_type_map(tp, d_down));
417 /* - supertype ----------------------------------------------------------- */
419 type *get_class_trans_supertype_first(type *tp) {
420 assert_valid_state();
421 return pset_first(get_type_map(tp, d_up));
424 type *get_class_trans_supertype_next (type *tp) {
425 assert_valid_state();
426 return pset_next(get_type_map(tp, d_up));
429 /* - overwrittenby ------------------------------------------------------- */
431 entity *get_entity_trans_overwrittenby_first(entity *ent) {
432 assert_valid_state();
433 return pset_first(get_entity_map(ent, d_down));
436 entity *get_entity_trans_overwrittenby_next (entity *ent) {
437 assert_valid_state();
438 return pset_next(get_entity_map(ent, d_down));
441 /* - overwrites ---------------------------------------------------------- */
444 /** Iterate over all transitive overwritten entities. */
445 entity *get_entity_trans_overwrites_first(entity *ent) {
446 assert_valid_state();
447 return pset_first(get_entity_map(ent, d_up));
450 entity *get_entity_trans_overwrites_next (entity *ent) {
451 assert_valid_state();
452 return pset_next(get_entity_map(ent, d_up));
459 /* ----------------------------------------------------------------------- */
460 /* Classify pairs of types/entities in the inheritance relations. */
461 /* ----------------------------------------------------------------------- */
463 /* Returns true if low is subclass of high. */
464 int is_subclass_of(type *low, type *high) {
466 assert(is_Class_type(low) && is_Class_type(high));
468 if (low == high) return 1;
470 if (get_irp_inh_transitive_closure_state() == inh_transitive_closure_valid) {
471 pset *m = get_type_map(high, d_down);
472 return pset_find_ptr(m, low) ? 1 : 0;
475 /* depth first search from high downwards. */
476 n_subtypes = get_class_n_subtypes(high);
477 for (i = 0; i < n_subtypes; i++) {
478 type *stp = get_class_subtype(high, i);
479 if (low == stp) return 1;
480 if (is_subclass_of(low, stp))
486 int is_overwritten_by(entity *high, entity *low) {
487 int i, n_overwrittenby;
488 assert(is_entity(low) && is_entity(high));
490 if (get_irp_inh_transitive_closure_state() == inh_transitive_closure_valid) {
491 pset *m = get_entity_map(high, d_down);
492 return pset_find_ptr(m, low) ? 1 : 0;
495 /* depth first search from high downwards. */
496 n_overwrittenby = get_entity_n_overwrittenby(high);
497 for (i = 0; i < n_overwrittenby; i++) {
498 entity *ov = get_entity_overwrittenby(high, i);
499 if (low == ov) return 1;
500 if (is_overwritten_by(low, ov))
507 /** Need two routines because I want to assert the result. */
508 static entity *resolve_ent_polymorphy2 (type *dynamic_class, entity *static_ent) {
509 int i, n_overwrittenby;
512 if (get_entity_owner(static_ent) == dynamic_class) return static_ent;
514 n_overwrittenby = get_entity_n_overwrittenby(static_ent);
515 for (i = 0; i < n_overwrittenby; ++i) {
516 res = resolve_ent_polymorphy2(dynamic_class, get_entity_overwrittenby(static_ent, i));
524 /* Resolve polymorphy in the inheritance relation.
526 * Returns the dynamically referenced entity if the static entity and the
527 * dynamic type are given.
528 * Search downwards in overwritten tree. */
529 entity *resolve_ent_polymorphy(type *dynamic_class, entity *static_ent) {
531 assert(static_ent && is_entity(static_ent));
533 res = resolve_ent_polymorphy2(dynamic_class, static_ent);