3 * @file tr_inheritance.c
5 * Project: libFIRM <br>
6 * File name: ir/tr/tr_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
23 #include "irgraph_t.h"
33 /* ----------------------------------------------------------------------- */
34 /* Resolve implicit inheritance. */
35 /* ----------------------------------------------------------------------- */
37 ident *default_mangle_inherited_name(entity *super, type *clss) {
38 return mangle_u(new_id_from_str("inh"), mangle_u(get_type_ident(clss), get_entity_ident(super)));
41 /** Replicates all entities in all super classes that are not overwritten
42 by an entity of this class. */
43 static void copy_entities_from_superclass(type *clss, void *env)
47 type *super, *inhenttype;
48 entity *inhent, *thisent;
49 mangle_inherited_name_func *mfunc = *(mangle_inherited_name_func **)env;
51 for(i = 0; i < get_class_n_supertypes(clss); i++) {
52 super = get_class_supertype(clss, i);
53 assert(is_Class_type(super) && "not a class");
54 for(j = 0; j < get_class_n_members(super); j++) {
55 inhent = get_class_member(super, j);
56 inhenttype = get_entity_type(inhent);
57 /* check whether inhent is already overwritten */
59 for (k = 0; (k < get_class_n_members(clss)) && (overwritten == 0); k++) {
60 thisent = get_class_member(clss, k);
61 for(l = 0; l < get_entity_n_overwrites(thisent); l++) {
62 if(inhent == get_entity_overwrites(thisent, l)) {
63 /* overwritten - do not copy */
71 thisent = copy_entity_own(inhent, clss);
72 add_entity_overwrites(thisent, inhent);
73 if (get_entity_peculiarity(inhent) == peculiarity_existent)
74 set_entity_peculiarity(thisent, peculiarity_inherited);
75 set_entity_ld_ident(thisent, mfunc(inhent, clss));
76 if (get_entity_variability(inhent) == variability_constant) {
77 assert(is_atomic_entity(inhent) && /* @@@ */
78 "Inheritance of constant, compound entities not implemented");
79 set_entity_variability(thisent, variability_constant);
80 set_atomic_ent_value(thisent, get_atomic_ent_value(inhent));
87 /* Resolve implicit inheritance.
89 * Resolves the implicit inheritance supplied by firm.
91 void resolve_inheritance(mangle_inherited_name_func *mfunc) {
93 mfunc = default_mangle_inherited_name;
94 class_walk_super2sub(copy_entities_from_superclass, NULL, (void *)&mfunc);
98 /* ----------------------------------------------------------------------- */
99 /* The transitive closure of the subclass/superclass and */
100 /* overwrites/overwrittenby relation. */
102 /* A walk over the ir (O(#types+#entities)) computes the transitive */
103 /* closure. Adding a new type/entity or changing the basic relations in */
104 /* some other way invalidates the transitive closure, i.e., it is not */
105 /* updated by the basic functions. */
107 /* All functions are named as their counterparts for the basic relations, */
108 /* adding the infix 'trans_'. */
109 /* ----------------------------------------------------------------------- */
111 void set_irp_inh_transitive_closure_state(inh_transitive_closure_state s) {
112 irp->inh_trans_closure_state = s;
114 void invalidate_irp_inh_transitive_closure_state(void) {
115 if (irp->inh_trans_closure_state == inh_transitive_closure_valid)
116 irp->inh_trans_closure_state = inh_transitive_closure_invalid;
118 inh_transitive_closure_state get_irp_inh_transitive_closure_state(void) {
119 return irp->inh_trans_closure_state;
122 static void assert_valid_state(void) {
123 assert(irp->inh_trans_closure_state == inh_transitive_closure_valid ||
124 irp->inh_trans_closure_state == inh_transitive_closure_invalid);
127 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
128 /* There is a set that extends each entity/type with two new */
129 /* fields: one for the upwards directed relation: 'up' (supertype, */
130 /* overwrites) and one for the downwards directed relation: 'down' (sub- */
131 /* type, overwrittenby. These fields contain psets (and maybe later */
132 /* arrays) listing all subtypes... */
133 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
141 firm_kind *kind; /* An entity or type. */
145 /* We use this set for all types and entities. */
146 static set *tr_inh_trans_set = NULL;
148 static int tr_inh_trans_cmp(const void *e1, const void *e2, size_t size) {
149 tr_inh_trans_tp *ef1 = (tr_inh_trans_tp *)e1;
150 tr_inh_trans_tp *ef2 = (tr_inh_trans_tp *)e2;
151 return (ef1->kind != ef2->kind);
154 static INLINE unsigned int tr_inh_trans_hash(void *e) {
155 tr_inh_trans_tp *v = e;
156 return HASH_PTR(v->kind);
159 /* This always completes successfully. */
160 static tr_inh_trans_tp* get_firm_kind_entry(firm_kind *k) {
161 tr_inh_trans_tp a, *found;
164 if (!tr_inh_trans_set) tr_inh_trans_set = new_set(tr_inh_trans_cmp, 128);
166 found = set_find(tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
168 a.directions[d_up] = pset_new_ptr(16);
169 a.directions[d_down] = pset_new_ptr(16);
170 found = set_insert(tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
175 static pset *get_entity_map(entity *ent, dir d) {
176 tr_inh_trans_tp *found;
178 assert(is_entity(ent));
179 found = get_firm_kind_entry((firm_kind *)ent);
180 return found->directions[d];
183 static void add_entity_map(entity *ent, dir d, entity *new) {
184 tr_inh_trans_tp *found;
186 assert(is_entity(ent) && is_entity(new));
187 tr_inh_trans_tp *found = get_firm_kind_entry((firm_kind *)ent);
188 pset_insert_ptr(found->directions[d], new);
191 static pset *get_type_map(type *tp, dir d) {
192 tr_inh_trans_tp *found;
195 found = get_firm_kind_entry((firm_kind *)tp);
196 return found->directions[d];
199 static void add_type_map(type *tp, dir d, type *new) {
200 tr_inh_trans_tp *found;
202 assert(is_type(tp) && is_type(new));
203 found = get_firm_kind_entry((firm_kind *)tp);
204 pset_insert_ptr(found->directions[d], new);
210 * Walk over all types reachable from tp in the sub/supertype
211 * relation and compute the closure for the two downwards directed
214 * The walk in the dag formed by the relation is tricky: We must visit
215 * all subtypes before visiting the supertypes. So we first walk down.
216 * Then we can compute the closure for this type. Then we walk up.
217 * As we call ourselves recursive, and walk in both directions, there
218 * can be cycles. So we have to make sure, that if we visit a node
219 * a second time (in a walk up) we do nothing. For this we increment
220 * the master visited flag twice.
221 * If the type is marked with master_flag_visited-1 it is on the stack.
222 * If it is marked with master_flag_visited it is fully processed.
224 * Well, we still miss some candidates ... */
225 static void compute_down_closure(type *tp) {
226 pset *myset, *subset;
227 int i, n_subtypes, n_members, n_supertypes;
228 unsigned long master_visited = get_master_type_visited();
230 assert(is_Class_type(tp));
232 set_type_visited(tp, master_visited-1);
234 /* Recursive descend. */
235 n_subtypes = get_class_n_subtypes(tp);
236 for (i = 0; i < n_subtypes; ++i) {
237 type *stp = get_class_subtype(tp, i);
238 if (get_type_visited(stp) < master_visited-1) {
239 compute_down_closure(stp);
244 myset = get_type_map(tp, d_down);
245 for (i = 0; i < n_subtypes; ++i) {
246 type *stp = get_class_subtype(tp, i);
247 subset = get_type_map(stp, d_down);
248 pset_insert_ptr(myset, stp);
249 pset_insert_pset_ptr(myset, subset);
253 n_members = get_class_n_members(tp);
254 for (i = 0; i < n_members; ++i) {
255 entity *mem = get_class_member(tp, i);
256 int j, n_overwrittenby = get_entity_n_overwrittenby(mem);
258 myset = get_entity_map(mem, d_down);
259 for (j = 0; j < n_overwrittenby; ++j) {
260 entity *ov = get_entity_overwrittenby(mem, j);
261 subset = get_entity_map(ov, d_down);
262 pset_insert_ptr(myset, ov);
263 pset_insert_pset_ptr(myset, subset);
267 mark_type_visited(tp);
270 n_supertypes = get_class_n_supertypes(tp);
271 for (i = 0; i < n_supertypes; ++i) {
272 type *stp = get_class_supertype(tp, i);
273 if (get_type_visited(stp) < master_visited-1) {
274 compute_down_closure(stp);
279 static void compute_up_closure(type *tp) {
280 pset *myset, *subset;
281 int i, n_subtypes, n_members, n_supertypes;
282 unsigned long master_visited = get_master_type_visited();
284 assert(is_Class_type(tp));
286 set_type_visited(tp, master_visited-1);
288 /* Recursive descend. */
289 n_supertypes = get_class_n_supertypes(tp);
290 for (i = 0; i < n_supertypes; ++i) {
291 type *stp = get_class_supertype(tp, i);
292 if (get_type_visited(stp) < get_master_type_visited()-1) {
293 compute_up_closure(stp);
298 myset = get_type_map(tp, d_up);
299 for (i = 0; i < n_supertypes; ++i) {
300 type *stp = get_class_supertype(tp, i);
301 subset = get_type_map(stp, d_up);
302 pset_insert_ptr(myset, stp);
303 pset_insert_pset_ptr(myset, subset);
307 n_members = get_class_n_members(tp);
308 for (i = 0; i < n_members; ++i) {
309 entity *mem = get_class_member(tp, i);
310 int j, n_overwrites = get_entity_n_overwrites(mem);
312 myset = get_entity_map(mem, d_up);
313 for (j = 0; j < n_overwrites; ++j) {
314 entity *ov = get_entity_overwrites(mem, j);
315 subset = get_entity_map(ov, d_up);
316 pset_insert_pset_ptr(myset, subset);
317 pset_insert_ptr(myset, ov);
321 mark_type_visited(tp);
324 n_subtypes = get_class_n_subtypes(tp);
325 for (i = 0; i < n_subtypes; ++i) {
326 type *stp = get_class_subtype(tp, i);
327 if (get_type_visited(stp) < master_visited-1) {
328 compute_up_closure(stp);
333 /** Compute the transitive closure of the subclass/superclass and
334 * overwrites/overwrittenby relation.
336 * This function walks over the ir (O(#types+#entities)) to compute the
337 * transitive closure. */
338 void compute_inh_transitive_closure(void) {
339 int i, n_types = get_irp_n_types();
340 free_inh_transitive_closure();
342 /* The 'down' relation */
343 inc_master_type_visited(); /* Inc twice: one if on stack, second if values computed. */
344 inc_master_type_visited();
345 for (i = 0; i < n_types; ++i) {
346 type *tp = get_irp_type(i);
347 if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
348 int j, n_subtypes = get_class_n_subtypes(tp);
349 int has_unmarked_subtype = 0;
351 assert(get_type_visited(tp) < get_master_type_visited()-1);
352 for (j = 0; j < n_subtypes; ++j) {
353 type *stp = get_class_subtype(tp, j);
354 if (type_not_visited(stp)) {
355 has_unmarked_subtype = 1;
360 /* This is a good starting point. */
361 if (!has_unmarked_subtype)
362 compute_down_closure(tp);
366 /* The 'up' relation */
367 inc_master_type_visited();
368 inc_master_type_visited();
369 for (i = 0; i < n_types; ++i) {
370 type *tp = get_irp_type(i);
371 if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
372 int j, n_supertypes = get_class_n_supertypes(tp);
373 int has_unmarked_supertype = 0;
375 assert(get_type_visited(tp) < get_master_type_visited()-1);
376 for (j = 0; j < n_supertypes; ++j) {
377 type *stp = get_class_supertype(tp, j);
378 if (type_not_visited(stp)) {
379 has_unmarked_supertype = 1;
384 /* This is a good starting point. */
385 if (!has_unmarked_supertype)
386 compute_up_closure(tp);
390 irp->inh_trans_closure_state = inh_transitive_closure_valid;
393 /** Free memory occupied by the transitive closure information. */
394 void free_inh_transitive_closure(void) {
395 if (tr_inh_trans_set) {
396 tr_inh_trans_tp *elt;
397 for (elt = set_first(tr_inh_trans_set); elt; elt = set_next(tr_inh_trans_set)) {
398 del_pset(elt->directions[d_up]);
399 del_pset(elt->directions[d_down]);
401 del_set(tr_inh_trans_set);
402 tr_inh_trans_set = NULL;
404 irp->inh_trans_closure_state = inh_transitive_closure_none;
407 /* - subtype ------------------------------------------------------------- */
409 type *get_class_trans_subtype_first(type *tp) {
410 assert_valid_state();
411 return pset_first(get_type_map(tp, d_down));
414 type *get_class_trans_subtype_next (type *tp) {
415 assert_valid_state();
416 return pset_next(get_type_map(tp, d_down));
419 int is_class_trans_subtype (type *tp, type *subtp) {
420 assert_valid_state();
421 return (pset_find_ptr(get_type_map(tp, d_down), subtp) != NULL);
424 /* - supertype ----------------------------------------------------------- */
426 type *get_class_trans_supertype_first(type *tp) {
427 assert_valid_state();
428 return pset_first(get_type_map(tp, d_up));
431 type *get_class_trans_supertype_next (type *tp) {
432 assert_valid_state();
433 return pset_next(get_type_map(tp, d_up));
436 /* - overwrittenby ------------------------------------------------------- */
438 entity *get_entity_trans_overwrittenby_first(entity *ent) {
439 assert_valid_state();
440 return pset_first(get_entity_map(ent, d_down));
443 entity *get_entity_trans_overwrittenby_next (entity *ent) {
444 assert_valid_state();
445 return pset_next(get_entity_map(ent, d_down));
448 /* - overwrites ---------------------------------------------------------- */
451 /** Iterate over all transitive overwritten entities. */
452 entity *get_entity_trans_overwrites_first(entity *ent) {
453 assert_valid_state();
454 return pset_first(get_entity_map(ent, d_up));
457 entity *get_entity_trans_overwrites_next (entity *ent) {
458 assert_valid_state();
459 return pset_next(get_entity_map(ent, d_up));
466 /* ----------------------------------------------------------------------- */
467 /* Classify pairs of types/entities in the inheritance relations. */
468 /* ----------------------------------------------------------------------- */
470 /* Returns true if low is subclass of high. */
471 int is_SubClass_of(type *low, type *high) {
473 assert(is_Class_type(low) && is_Class_type(high));
475 if (low == high) return 1;
477 if (get_irp_inh_transitive_closure_state() == inh_transitive_closure_valid) {
478 pset *m = get_type_map(high, d_down);
479 return pset_find_ptr(m, low) ? 1 : 0;
482 /* depth first search from high downwards. */
483 n_subtypes = get_class_n_subtypes(high);
484 for (i = 0; i < n_subtypes; i++) {
485 type *stp = get_class_subtype(high, i);
486 if (low == stp) return 1;
487 if (is_SubClass_of(low, stp))
494 /* Subclass check for pointers to classes.
496 * Dereferences at both types the same amount of pointer types (as
497 * many as possible). If the remaining types are both class types
498 * and subclasses, returns true, else false. Can also be called with
499 * two class types. */
500 int is_SubClass_ptr_of(type *low, type *high) {
501 while (is_Pointer_type(low) && is_Pointer_type(high)) {
502 low = get_pointer_points_to_type(low);
503 high = get_pointer_points_to_type(high);
506 if (is_Class_type(low) && is_Class_type(high))
507 return is_SubClass_of(low, high);
511 int is_overwritten_by(entity *high, entity *low) {
512 int i, n_overwrittenby;
513 assert(is_entity(low) && is_entity(high));
515 if (get_irp_inh_transitive_closure_state() == inh_transitive_closure_valid) {
516 pset *m = get_entity_map(high, d_down);
517 return pset_find_ptr(m, low) ? 1 : 0;
520 /* depth first search from high downwards. */
521 n_overwrittenby = get_entity_n_overwrittenby(high);
522 for (i = 0; i < n_overwrittenby; i++) {
523 entity *ov = get_entity_overwrittenby(high, i);
524 if (low == ov) return 1;
525 if (is_overwritten_by(low, ov))
532 /** Need two routines because I want to assert the result. */
533 static entity *resolve_ent_polymorphy2 (type *dynamic_class, entity *static_ent) {
534 int i, n_overwrittenby;
537 if (get_entity_owner(static_ent) == dynamic_class) return static_ent;
539 n_overwrittenby = get_entity_n_overwrittenby(static_ent);
540 for (i = 0; i < n_overwrittenby; ++i) {
541 res = resolve_ent_polymorphy2(dynamic_class, get_entity_overwrittenby(static_ent, i));
549 /* Resolve polymorphy in the inheritance relation.
551 * Returns the dynamically referenced entity if the static entity and the
552 * dynamic type are given.
553 * Search downwards in overwritten tree. */
554 entity *resolve_ent_polymorphy(type *dynamic_class, entity *static_ent) {
556 assert(static_ent && is_entity(static_ent));
558 res = resolve_ent_polymorphy2(dynamic_class, static_ent);
566 /* ----------------------------------------------------------------------- */
567 /* Class cast state handling. */
568 /* ----------------------------------------------------------------------- */
570 /* - State handling. ----------------------------------------- */
572 void set_irg_class_cast_state(ir_graph *irg, ir_class_cast_state s) {
573 if (get_irp_class_cast_state() > s) set_irp_class_cast_state(s);
574 irg->class_cast_state = s;
577 ir_class_cast_state get_irg_class_cast_state(ir_graph *irg) {
578 return irg->class_cast_state;
581 void set_irp_class_cast_state(ir_class_cast_state s) {
583 for (i = 0; i < get_irp_n_irgs(); ++i)
584 assert(get_irg_class_cast_state(get_irp_irg(i)) >= s);
585 irp->class_cast_state = s;
588 ir_class_cast_state get_irp_class_cast_state(void) {
589 return irp->class_cast_state;
592 char *get_class_cast_state_string(ir_class_cast_state s) {
593 #define X(a) case a: return #a
595 X(ir_class_casts_any);
596 X(ir_class_casts_transitive);
597 X(ir_class_casts_normalized);
598 X(ir_class_casts_state_max);
599 default: return "invalid class cast state";
604 /* - State verification. ------------------------------------- */
606 typedef struct ccs_env {
607 ir_class_cast_state expected_state;
608 ir_class_cast_state worst_situation;
611 void verify_irn_class_cast_state(ir_node *n, void *env) {
612 ccs_env *ccs = (ccs_env *)env;
613 ir_class_cast_state this_state = ir_class_casts_any;
614 type *fromtype, *totype;
617 if (get_irn_op(n) != op_Cast) return;
619 fromtype = get_irn_typeinfo_type(get_Cast_op(n));
620 totype = get_Cast_type(n);
622 while (is_Pointer_type(totype) && is_Pointer_type(fromtype)) {
623 totype = get_pointer_points_to_type(totype);
624 fromtype = get_pointer_points_to_type(fromtype);
628 if (!is_Class_type(totype)) return;
630 if (is_SubClass_of(totype, fromtype) ||
631 is_SubClass_of(fromtype, totype) ) {
632 this_state = ir_class_casts_transitive;
633 if ((get_class_supertype_index(totype, fromtype) != -1) ||
634 (get_class_supertype_index(fromtype, totype) != -1) ||
635 fromtype == totype) {
636 /* Das ist doch alt? Aus dem cvs aufgetaucht ...
637 if ((get_class_supertype_index(totype, fromtype) == -1) &&
638 (get_class_supertype_index(fromtype, totype) == -1) ) { */
639 this_state = ir_class_casts_normalized;
643 if (!(this_state >= ccs->expected_state)) {
644 printf(" Node is "); DDMN(n);
645 printf(" totype "); DDMT(totype);
646 printf(" fromtype "); DDMT(fromtype);
647 printf(" this_state: %s, exp. state: %s\n",
648 get_class_cast_state_string(this_state),
649 get_class_cast_state_string(ccs->expected_state));
650 assert(this_state >= ccs->expected_state &&
651 "invalid state class cast state setting in graph");
654 if (this_state < ccs->worst_situation)
655 ccs->worst_situation = this_state;
659 /** Verify that the graph meets requirements of state set. */
660 void verify_irg_class_cast_state(ir_graph *irg) {
663 env.expected_state = get_irg_class_cast_state(irg);
664 env.worst_situation = ir_class_casts_normalized;
666 irg_walk_graph(irg, NULL, verify_irn_class_cast_state, &env);
668 if ((env.worst_situation > env.expected_state) && get_firm_verbosity()) {
669 printf("Note: class cast state is set lower than reqired in graph\n ");
671 printf(" state is %s, reqired is %s\n",
672 get_class_cast_state_string(env.expected_state),
673 get_class_cast_state_string(env.worst_situation));