2 * This file is part of libFirm.
3 * Copyright (C) 2012 University of Karlsruhe.
8 * @brief Utility routines for inheritance representation
9 * @author Goetz Lindenmaier
15 #include "irgraph_t.h"
23 /* ----------------------------------------------------------------------- */
24 /* Resolve implicit inheritance. */
25 /* ----------------------------------------------------------------------- */
27 ident *default_mangle_inherited_name(const ir_entity *super, const ir_type *clss)
29 return id_mangle_u(new_id_from_str("inh"), id_mangle_u(get_class_ident(clss), get_entity_ident(super)));
32 /** Replicates all entities in all super classes that are not overwritten
33 by an entity of this class. */
34 static void copy_entities_from_superclass(ir_type *clss, void *env)
42 ir_entity *inhent, *thisent;
43 mangle_inherited_name_func *mfunc = *(mangle_inherited_name_func **)env;
45 for (i = 0; i < get_class_n_supertypes(clss); i++) {
46 super = get_class_supertype(clss, i);
47 for (j = 0; j < get_class_n_members(super); j++) {
48 inhent = get_class_member(super, j);
49 /* check whether inhent is already overwritten */
51 for (k = 0; (k < get_class_n_members(clss)) && (overwritten == 0); k++) {
52 thisent = get_class_member(clss, k);
53 for (l = 0; l < get_entity_n_overwrites(thisent); l++) {
54 if (inhent == get_entity_overwrites(thisent, l)) {
55 /* overwritten - do not copy */
63 thisent = copy_entity_own(inhent, clss);
64 add_entity_overwrites(thisent, inhent);
65 if (get_entity_peculiarity(inhent) == peculiarity_existent)
66 set_entity_peculiarity(thisent, peculiarity_inherited);
67 set_entity_ld_ident(thisent, mfunc(inhent, clss));
68 if (get_entity_linkage(inhent) & IR_LINKAGE_CONSTANT) {
69 assert(is_atomic_entity(inhent) && /* @@@ */
70 "Inheritance of constant, compound entities not implemented");
71 add_entity_linkage(thisent, IR_LINKAGE_CONSTANT);
72 set_atomic_ent_value(thisent, get_atomic_ent_value(inhent));
79 void resolve_inheritance(mangle_inherited_name_func *mfunc)
82 mfunc = default_mangle_inherited_name;
83 class_walk_super2sub(copy_entities_from_superclass, NULL, (void *)&mfunc);
87 /* ----------------------------------------------------------------------- */
88 /* The transitive closure of the subclass/superclass and */
89 /* overwrites/overwrittenby relation. */
91 /* A walk over the ir (O(#types+#entities)) computes the transitive */
92 /* closure. Adding a new type/entity or changing the basic relations in */
93 /* some other way invalidates the transitive closure, i.e., it is not */
94 /* updated by the basic functions. */
96 /* All functions are named as their counterparts for the basic relations, */
97 /* adding the infix 'trans_'. */
98 /* ----------------------------------------------------------------------- */
100 void set_irp_inh_transitive_closure_state(inh_transitive_closure_state s)
102 irp->inh_trans_closure_state = s;
104 void invalidate_irp_inh_transitive_closure_state(void)
106 if (irp->inh_trans_closure_state == inh_transitive_closure_valid)
107 irp->inh_trans_closure_state = inh_transitive_closure_invalid;
109 inh_transitive_closure_state get_irp_inh_transitive_closure_state(void)
111 return irp->inh_trans_closure_state;
114 static void assert_valid_state(void)
116 assert(irp->inh_trans_closure_state == inh_transitive_closure_valid ||
117 irp->inh_trans_closure_state == inh_transitive_closure_invalid);
120 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
121 /* There is a set that extends each entity/type with two new */
122 /* fields: one for the upwards directed relation: 'up' (supertype, */
123 /* overwrites) and one for the downwards directed relation: 'down' (sub- */
124 /* type, overwrittenby. These fields contain psets (and maybe later */
125 /* arrays) listing all subtypes... */
126 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
134 const 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;
142 * Compare two tr_inh_trans_tp entries.
144 static int tr_inh_trans_cmp(const void *e1, const void *e2, size_t size)
146 const tr_inh_trans_tp *ef1 = (const tr_inh_trans_tp*)e1;
147 const tr_inh_trans_tp *ef2 = (const tr_inh_trans_tp*)e2;
150 return ef1->kind != ef2->kind;
154 * calculate the hash value of an tr_inh_trans_tp
156 static inline unsigned int tr_inh_trans_hash(const tr_inh_trans_tp *v)
158 return hash_ptr(v->kind);
161 /* This always completes successfully. */
162 static tr_inh_trans_tp *get_firm_kind_entry(const firm_kind *k)
164 tr_inh_trans_tp a, *found;
167 if (!tr_inh_trans_set) tr_inh_trans_set = new_set(tr_inh_trans_cmp, 128);
169 found = set_find(tr_inh_trans_tp, tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
171 a.directions[d_up] = pset_new_ptr(16);
172 a.directions[d_down] = pset_new_ptr(16);
173 found = set_insert(tr_inh_trans_tp, tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
178 static pset *get_entity_map(const ir_entity *ent, dir d)
180 tr_inh_trans_tp *found;
182 assert(is_entity(ent));
183 found = get_firm_kind_entry((const firm_kind *)ent);
184 return found->directions[d];
187 static pset *get_type_map(const ir_type *tp, dir d)
189 tr_inh_trans_tp *found;
192 found = get_firm_kind_entry((const firm_kind *)tp);
193 return found->directions[d];
198 * Walk over all types reachable from tp in the sub/supertype
199 * relation and compute the closure for the two downwards directed
202 * The walk in the dag formed by the relation is tricky: We must visit
203 * all subtypes before visiting the supertypes. So we first walk down.
204 * Then we can compute the closure for this type. Then we walk up.
205 * As we call ourselves recursive, and walk in both directions, there
206 * can be cycles. So we have to make sure, that if we visit a node
207 * a second time (in a walk up) we do nothing. For this we increment
208 * the master visited flag twice.
209 * If the type is marked with master_flag_visited-1 it is on the stack.
210 * If it is marked with master_flag_visited it is fully processed.
212 * Well, we still miss some candidates ... */
213 static void compute_down_closure(ir_type *tp)
215 pset *myset, *subset;
216 size_t i, n_subtypes, n_members, n_supertypes;
217 ir_visited_t master_visited = get_master_type_visited();
219 set_type_visited(tp, master_visited-1);
221 /* Recursive descend. */
222 n_subtypes = get_class_n_subtypes(tp);
223 for (i = 0; i < n_subtypes; ++i) {
224 ir_type *stp = get_class_subtype(tp, i);
225 if (get_type_visited(stp) < master_visited-1) {
226 compute_down_closure(stp);
231 myset = get_type_map(tp, d_down);
232 for (i = 0; i < n_subtypes; ++i) {
233 ir_type *stp = get_class_subtype(tp, i);
234 subset = get_type_map(stp, d_down);
235 pset_insert_ptr(myset, stp);
236 pset_insert_pset_ptr(myset, subset);
240 n_members = get_class_n_members(tp);
241 for (i = 0; i < n_members; ++i) {
242 ir_entity *mem = get_class_member(tp, i);
243 size_t j, n_overwrittenby = get_entity_n_overwrittenby(mem);
245 myset = get_entity_map(mem, d_down);
246 for (j = 0; j < n_overwrittenby; ++j) {
247 ir_entity *ov = get_entity_overwrittenby(mem, j);
248 subset = get_entity_map(ov, d_down);
249 pset_insert_ptr(myset, ov);
250 pset_insert_pset_ptr(myset, subset);
254 mark_type_visited(tp);
257 n_supertypes = get_class_n_supertypes(tp);
258 for (i = 0; i < n_supertypes; ++i) {
259 ir_type *stp = get_class_supertype(tp, i);
260 if (get_type_visited(stp) < master_visited-1) {
261 compute_down_closure(stp);
266 static void compute_up_closure(ir_type *tp)
268 pset *myset, *subset;
269 size_t i, n_subtypes, n_members, n_supertypes;
270 ir_visited_t master_visited = get_master_type_visited();
272 set_type_visited(tp, master_visited-1);
274 /* Recursive descend. */
275 n_supertypes = get_class_n_supertypes(tp);
276 for (i = 0; i < n_supertypes; ++i) {
277 ir_type *stp = get_class_supertype(tp, i);
278 if (get_type_visited(stp) < get_master_type_visited()-1) {
279 compute_up_closure(stp);
284 myset = get_type_map(tp, d_up);
285 for (i = 0; i < n_supertypes; ++i) {
286 ir_type *stp = get_class_supertype(tp, i);
287 subset = get_type_map(stp, d_up);
288 pset_insert_ptr(myset, stp);
289 pset_insert_pset_ptr(myset, subset);
293 n_members = get_class_n_members(tp);
294 for (i = 0; i < n_members; ++i) {
295 ir_entity *mem = get_class_member(tp, i);
296 size_t j, n_overwrites = get_entity_n_overwrites(mem);
298 myset = get_entity_map(mem, d_up);
299 for (j = 0; j < n_overwrites; ++j) {
300 ir_entity *ov = get_entity_overwrites(mem, j);
301 subset = get_entity_map(ov, d_up);
302 pset_insert_pset_ptr(myset, subset);
303 pset_insert_ptr(myset, ov);
307 mark_type_visited(tp);
310 n_subtypes = get_class_n_subtypes(tp);
311 for (i = 0; i < n_subtypes; ++i) {
312 ir_type *stp = get_class_subtype(tp, i);
313 if (get_type_visited(stp) < master_visited-1) {
314 compute_up_closure(stp);
319 void compute_inh_transitive_closure(void)
321 size_t i, n_types = get_irp_n_types();
322 free_inh_transitive_closure();
324 /* The 'down' relation */
325 irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
326 inc_master_type_visited(); /* Inc twice: one if on stack, second if values computed. */
327 inc_master_type_visited();
328 for (i = 0; i < n_types; ++i) {
329 ir_type *tp = get_irp_type(i);
330 if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
331 size_t j, n_subtypes = get_class_n_subtypes(tp);
332 int has_unmarked_subtype = 0;
334 assert(get_type_visited(tp) < get_master_type_visited()-1);
335 for (j = 0; j < n_subtypes; ++j) {
336 ir_type *stp = get_class_subtype(tp, j);
337 if (type_not_visited(stp)) {
338 has_unmarked_subtype = 1;
343 /* This is a good starting point. */
344 if (!has_unmarked_subtype)
345 compute_down_closure(tp);
349 /* The 'up' relation */
350 inc_master_type_visited();
351 inc_master_type_visited();
352 for (i = 0; i < n_types; ++i) {
353 ir_type *tp = get_irp_type(i);
354 if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
355 size_t j, n_supertypes = get_class_n_supertypes(tp);
356 int has_unmarked_supertype = 0;
358 assert(get_type_visited(tp) < get_master_type_visited()-1);
359 for (j = 0; j < n_supertypes; ++j) {
360 ir_type *stp = get_class_supertype(tp, j);
361 if (type_not_visited(stp)) {
362 has_unmarked_supertype = 1;
367 /* This is a good starting point. */
368 if (!has_unmarked_supertype)
369 compute_up_closure(tp);
373 irp->inh_trans_closure_state = inh_transitive_closure_valid;
374 irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
377 void free_inh_transitive_closure(void)
379 if (tr_inh_trans_set) {
380 foreach_set(tr_inh_trans_set, tr_inh_trans_tp, elt) {
381 del_pset(elt->directions[d_up]);
382 del_pset(elt->directions[d_down]);
384 del_set(tr_inh_trans_set);
385 tr_inh_trans_set = NULL;
387 irp->inh_trans_closure_state = inh_transitive_closure_none;
390 /* - subtype ------------------------------------------------------------- */
392 ir_type *get_class_trans_subtype_first(const ir_type *tp)
394 assert_valid_state();
395 return pset_first(ir_type, get_type_map(tp, d_down));
398 ir_type *get_class_trans_subtype_next(const ir_type *tp)
400 assert_valid_state();
401 return pset_next(ir_type, get_type_map(tp, d_down));
404 int is_class_trans_subtype(const ir_type *tp, const ir_type *subtp)
406 assert_valid_state();
407 return (pset_find_ptr(get_type_map(tp, d_down), subtp) != NULL);
410 /* - supertype ----------------------------------------------------------- */
412 ir_type *get_class_trans_supertype_first(const ir_type *tp)
414 assert_valid_state();
415 return pset_first(ir_type, get_type_map(tp, d_up));
418 ir_type *get_class_trans_supertype_next(const ir_type *tp)
420 assert_valid_state();
421 return pset_next(ir_type, get_type_map(tp, d_up));
424 /* - overwrittenby ------------------------------------------------------- */
426 ir_entity *get_entity_trans_overwrittenby_first(const ir_entity *ent)
428 assert_valid_state();
429 return pset_first(ir_entity, get_entity_map(ent, d_down));
432 ir_entity *get_entity_trans_overwrittenby_next(const ir_entity *ent)
434 assert_valid_state();
435 return pset_next(ir_entity, get_entity_map(ent, d_down));
438 /* - overwrites ---------------------------------------------------------- */
441 ir_entity *get_entity_trans_overwrites_first(const ir_entity *ent)
443 assert_valid_state();
444 return pset_first(ir_entity, get_entity_map(ent, d_up));
447 ir_entity *get_entity_trans_overwrites_next(const ir_entity *ent)
449 assert_valid_state();
450 return pset_next(ir_entity, get_entity_map(ent, d_up));
454 /* ----------------------------------------------------------------------- */
455 /* Classify pairs of types/entities in the inheritance relations. */
456 /* ----------------------------------------------------------------------- */
458 /** Returns true if low is subclass of high. */
459 static int check_is_SubClass_of(ir_type *low, ir_type *high)
461 size_t i, n_subtypes;
463 /* depth first search from high downwards. */
464 n_subtypes = get_class_n_subtypes(high);
465 for (i = 0; i < n_subtypes; i++) {
466 ir_type *stp = get_class_subtype(high, i);
467 if (low == stp) return 1;
468 if (is_SubClass_of(low, stp))
474 int is_SubClass_of(ir_type *low, ir_type *high)
476 assert(is_Class_type(low) && is_Class_type(high));
478 if (low == high) return 1;
480 if (get_irp_inh_transitive_closure_state() == inh_transitive_closure_valid) {
481 pset *m = get_type_map(high, d_down);
482 return pset_find_ptr(m, low) ? 1 : 0;
484 return check_is_SubClass_of(low, high);
487 int is_SubClass_ptr_of(ir_type *low, ir_type *high)
489 while (is_Pointer_type(low) && is_Pointer_type(high)) {
490 low = get_pointer_points_to_type(low);
491 high = get_pointer_points_to_type(high);
494 if (is_Class_type(low) && is_Class_type(high))
495 return is_SubClass_of(low, high);
499 int is_overwritten_by(ir_entity *high, ir_entity *low)
501 size_t i, n_overwrittenby;
502 assert(is_entity(low) && is_entity(high));
504 if (get_irp_inh_transitive_closure_state() == inh_transitive_closure_valid) {
505 pset *m = get_entity_map(high, d_down);
506 return pset_find_ptr(m, low) ? 1 : 0;
509 /* depth first search from high downwards. */
510 n_overwrittenby = get_entity_n_overwrittenby(high);
511 for (i = 0; i < n_overwrittenby; i++) {
512 ir_entity *ov = get_entity_overwrittenby(high, i);
513 if (low == ov) return 1;
514 if (is_overwritten_by(low, ov))
520 /** Resolve polymorphy in the inheritance relation.
522 * Returns the dynamically referenced entity if the static entity and the
523 * dynamic type are given.
524 * Search downwards in overwritten tree.
526 * Need two routines because I want to assert the result.
528 static ir_entity *do_resolve_ent_polymorphy(ir_type *dynamic_class, ir_entity *static_ent)
530 size_t i, n_overwrittenby;
532 ir_type *owner = get_entity_owner(static_ent);
533 if (owner == dynamic_class) return static_ent;
535 // if the owner of the static_ent already is more special than the dynamic
536 // type to check against - stop here.
537 if (! is_SubClass_of(dynamic_class, owner)) return NULL;
539 n_overwrittenby = get_entity_n_overwrittenby(static_ent);
540 for (i = 0; i < n_overwrittenby; ++i) {
541 ir_entity *ent = get_entity_overwrittenby(static_ent, i);
542 ent = do_resolve_ent_polymorphy(dynamic_class, ent);
546 // No further specialization of static_ent has been found
550 ir_entity *resolve_ent_polymorphy(ir_type *dynamic_class, ir_entity *static_ent)
553 assert(static_ent && is_entity(static_ent));
555 res = do_resolve_ent_polymorphy(dynamic_class, static_ent);