2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
21 * @file tr_inheritance.c
22 * @brief Utility routines for inheritance representation
23 * @author Goetz Lindenmaier
32 #include "irgraph_t.h"
40 DEBUG_ONLY(static firm_dbg_module_t *dbg);
42 /* ----------------------------------------------------------------------- */
43 /* Resolve implicit inheritance. */
44 /* ----------------------------------------------------------------------- */
46 ident *default_mangle_inherited_name(ir_entity *super, ir_type *clss) {
47 return mangle_u(new_id_from_str("inh"), mangle_u(get_type_ident(clss), get_entity_ident(super)));
50 /** Replicates all entities in all super classes that are not overwritten
51 by an entity of this class. */
52 static void copy_entities_from_superclass(ir_type *clss, void *env)
56 ir_type *super, *inhenttype;
57 ir_entity *inhent, *thisent;
58 mangle_inherited_name_func *mfunc = *(mangle_inherited_name_func **)env;
60 for(i = 0; i < get_class_n_supertypes(clss); i++) {
61 super = get_class_supertype(clss, i);
62 assert(is_Class_type(super) && "not a class");
63 for(j = 0; j < get_class_n_members(super); j++) {
64 inhent = get_class_member(super, j);
65 inhenttype = get_entity_type(inhent);
66 /* check whether inhent is already overwritten */
68 for (k = 0; (k < get_class_n_members(clss)) && (overwritten == 0); k++) {
69 thisent = get_class_member(clss, k);
70 for(l = 0; l < get_entity_n_overwrites(thisent); l++) {
71 if(inhent == get_entity_overwrites(thisent, l)) {
72 /* overwritten - do not copy */
80 thisent = copy_entity_own(inhent, clss);
81 add_entity_overwrites(thisent, inhent);
82 if (get_entity_peculiarity(inhent) == peculiarity_existent)
83 set_entity_peculiarity(thisent, peculiarity_inherited);
84 set_entity_ld_ident(thisent, mfunc(inhent, clss));
85 if (get_entity_variability(inhent) == variability_constant) {
86 assert(is_atomic_entity(inhent) && /* @@@ */
87 "Inheritance of constant, compound entities not implemented");
88 set_entity_variability(thisent, variability_constant);
89 set_atomic_ent_value(thisent, get_atomic_ent_value(inhent));
96 /* Resolve implicit inheritance.
98 * Resolves the implicit inheritance supplied by firm.
100 void resolve_inheritance(mangle_inherited_name_func *mfunc) {
102 mfunc = default_mangle_inherited_name;
103 class_walk_super2sub(copy_entities_from_superclass, NULL, (void *)&mfunc);
107 /* ----------------------------------------------------------------------- */
108 /* The transitive closure of the subclass/superclass and */
109 /* overwrites/overwrittenby relation. */
111 /* A walk over the ir (O(#types+#entities)) computes the transitive */
112 /* closure. Adding a new type/entity or changing the basic relations in */
113 /* some other way invalidates the transitive closure, i.e., it is not */
114 /* updated by the basic functions. */
116 /* All functions are named as their counterparts for the basic relations, */
117 /* adding the infix 'trans_'. */
118 /* ----------------------------------------------------------------------- */
120 void set_irp_inh_transitive_closure_state(inh_transitive_closure_state s) {
121 irp->inh_trans_closure_state = s;
123 void invalidate_irp_inh_transitive_closure_state(void) {
124 if (irp->inh_trans_closure_state == inh_transitive_closure_valid)
125 irp->inh_trans_closure_state = inh_transitive_closure_invalid;
127 inh_transitive_closure_state get_irp_inh_transitive_closure_state(void) {
128 return irp->inh_trans_closure_state;
131 static void assert_valid_state(void) {
132 assert(irp->inh_trans_closure_state == inh_transitive_closure_valid ||
133 irp->inh_trans_closure_state == inh_transitive_closure_invalid);
136 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
137 /* There is a set that extends each entity/type with two new */
138 /* fields: one for the upwards directed relation: 'up' (supertype, */
139 /* overwrites) and one for the downwards directed relation: 'down' (sub- */
140 /* type, overwrittenby. These fields contain psets (and maybe later */
141 /* arrays) listing all subtypes... */
142 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
150 const firm_kind *kind; /**< An entity or type. */
154 /* We use this set for all types and entities. */
155 static set *tr_inh_trans_set = NULL;
158 * Compare two tr_inh_trans_tp entries.
160 static int tr_inh_trans_cmp(const void *e1, const void *e2, size_t size) {
161 const tr_inh_trans_tp *ef1 = e1;
162 const tr_inh_trans_tp *ef2 = e2;
165 return ef1->kind != ef2->kind;
169 * calculate the hash value of an tr_inh_trans_tp
171 static INLINE unsigned int tr_inh_trans_hash(const tr_inh_trans_tp *v) {
172 return HASH_PTR(v->kind);
175 /* This always completes successfully. */
176 static tr_inh_trans_tp *get_firm_kind_entry(const firm_kind *k) {
177 tr_inh_trans_tp a, *found;
180 if (!tr_inh_trans_set) tr_inh_trans_set = new_set(tr_inh_trans_cmp, 128);
182 found = set_find(tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
184 a.directions[d_up] = pset_new_ptr(16);
185 a.directions[d_down] = pset_new_ptr(16);
186 found = set_insert(tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
191 static pset *get_entity_map(const ir_entity *ent, dir d) {
192 tr_inh_trans_tp *found;
194 assert(is_entity(ent));
195 found = get_firm_kind_entry((const firm_kind *)ent);
196 return found->directions[d];
199 static pset *get_type_map(const ir_type *tp, dir d) {
200 tr_inh_trans_tp *found;
203 found = get_firm_kind_entry((const firm_kind *)tp);
204 return found->directions[d];
209 * Walk over all types reachable from tp in the sub/supertype
210 * relation and compute the closure for the two downwards directed
213 * The walk in the dag formed by the relation is tricky: We must visit
214 * all subtypes before visiting the supertypes. So we first walk down.
215 * Then we can compute the closure for this type. Then we walk up.
216 * As we call ourselves recursive, and walk in both directions, there
217 * can be cycles. So we have to make sure, that if we visit a node
218 * a second time (in a walk up) we do nothing. For this we increment
219 * the master visited flag twice.
220 * If the type is marked with master_flag_visited-1 it is on the stack.
221 * If it is marked with master_flag_visited it is fully processed.
223 * Well, we still miss some candidates ... */
224 static void compute_down_closure(ir_type *tp) {
225 pset *myset, *subset;
226 int i, n_subtypes, n_members, n_supertypes;
227 unsigned long master_visited = get_master_type_visited();
229 assert(is_Class_type(tp));
231 set_type_visited(tp, master_visited-1);
233 /* Recursive descend. */
234 n_subtypes = get_class_n_subtypes(tp);
235 for (i = 0; i < n_subtypes; ++i) {
236 ir_type *stp = get_class_subtype(tp, i);
237 if (get_type_visited(stp) < master_visited-1) {
238 compute_down_closure(stp);
243 myset = get_type_map(tp, d_down);
244 for (i = 0; i < n_subtypes; ++i) {
245 ir_type *stp = get_class_subtype(tp, i);
246 subset = get_type_map(stp, d_down);
247 pset_insert_ptr(myset, stp);
248 pset_insert_pset_ptr(myset, subset);
252 n_members = get_class_n_members(tp);
253 for (i = 0; i < n_members; ++i) {
254 ir_entity *mem = get_class_member(tp, i);
255 int j, n_overwrittenby = get_entity_n_overwrittenby(mem);
257 myset = get_entity_map(mem, d_down);
258 for (j = 0; j < n_overwrittenby; ++j) {
259 ir_entity *ov = get_entity_overwrittenby(mem, j);
260 subset = get_entity_map(ov, d_down);
261 pset_insert_ptr(myset, ov);
262 pset_insert_pset_ptr(myset, subset);
266 mark_type_visited(tp);
269 n_supertypes = get_class_n_supertypes(tp);
270 for (i = 0; i < n_supertypes; ++i) {
271 ir_type *stp = get_class_supertype(tp, i);
272 if (get_type_visited(stp) < master_visited-1) {
273 compute_down_closure(stp);
278 static void compute_up_closure(ir_type *tp) {
279 pset *myset, *subset;
280 int i, n_subtypes, n_members, n_supertypes;
281 unsigned long master_visited = get_master_type_visited();
283 assert(is_Class_type(tp));
285 set_type_visited(tp, master_visited-1);
287 /* Recursive descend. */
288 n_supertypes = get_class_n_supertypes(tp);
289 for (i = 0; i < n_supertypes; ++i) {
290 ir_type *stp = get_class_supertype(tp, i);
291 if (get_type_visited(stp) < get_master_type_visited()-1) {
292 compute_up_closure(stp);
297 myset = get_type_map(tp, d_up);
298 for (i = 0; i < n_supertypes; ++i) {
299 ir_type *stp = get_class_supertype(tp, i);
300 subset = get_type_map(stp, d_up);
301 pset_insert_ptr(myset, stp);
302 pset_insert_pset_ptr(myset, subset);
306 n_members = get_class_n_members(tp);
307 for (i = 0; i < n_members; ++i) {
308 ir_entity *mem = get_class_member(tp, i);
309 int j, n_overwrites = get_entity_n_overwrites(mem);
311 myset = get_entity_map(mem, d_up);
312 for (j = 0; j < n_overwrites; ++j) {
313 ir_entity *ov = get_entity_overwrites(mem, j);
314 subset = get_entity_map(ov, d_up);
315 pset_insert_pset_ptr(myset, subset);
316 pset_insert_ptr(myset, ov);
320 mark_type_visited(tp);
323 n_subtypes = get_class_n_subtypes(tp);
324 for (i = 0; i < n_subtypes; ++i) {
325 ir_type *stp = get_class_subtype(tp, i);
326 if (get_type_visited(stp) < master_visited-1) {
327 compute_up_closure(stp);
332 /** Compute the transitive closure of the subclass/superclass and
333 * overwrites/overwrittenby relation.
335 * This function walks over the ir (O(#types+#entities)) to compute the
336 * transitive closure. */
337 void compute_inh_transitive_closure(void) {
338 int i, n_types = get_irp_n_types();
339 free_inh_transitive_closure();
341 /* The 'down' relation */
342 inc_master_type_visited(); /* Inc twice: one if on stack, second if values computed. */
343 inc_master_type_visited();
344 for (i = 0; i < n_types; ++i) {
345 ir_type *tp = get_irp_type(i);
346 if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
347 int j, n_subtypes = get_class_n_subtypes(tp);
348 int has_unmarked_subtype = 0;
350 assert(get_type_visited(tp) < get_master_type_visited()-1);
351 for (j = 0; j < n_subtypes; ++j) {
352 ir_type *stp = get_class_subtype(tp, j);
353 if (type_not_visited(stp)) {
354 has_unmarked_subtype = 1;
359 /* This is a good starting point. */
360 if (!has_unmarked_subtype)
361 compute_down_closure(tp);
365 /* The 'up' relation */
366 inc_master_type_visited();
367 inc_master_type_visited();
368 for (i = 0; i < n_types; ++i) {
369 ir_type *tp = get_irp_type(i);
370 if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
371 int j, n_supertypes = get_class_n_supertypes(tp);
372 int has_unmarked_supertype = 0;
374 assert(get_type_visited(tp) < get_master_type_visited()-1);
375 for (j = 0; j < n_supertypes; ++j) {
376 ir_type *stp = get_class_supertype(tp, j);
377 if (type_not_visited(stp)) {
378 has_unmarked_supertype = 1;
383 /* This is a good starting point. */
384 if (!has_unmarked_supertype)
385 compute_up_closure(tp);
389 irp->inh_trans_closure_state = inh_transitive_closure_valid;
392 /** Free memory occupied by the transitive closure information. */
393 void free_inh_transitive_closure(void) {
394 if (tr_inh_trans_set) {
395 tr_inh_trans_tp *elt;
396 for (elt = set_first(tr_inh_trans_set); elt; elt = set_next(tr_inh_trans_set)) {
397 del_pset(elt->directions[d_up]);
398 del_pset(elt->directions[d_down]);
400 del_set(tr_inh_trans_set);
401 tr_inh_trans_set = NULL;
403 irp->inh_trans_closure_state = inh_transitive_closure_none;
406 /* - subtype ------------------------------------------------------------- */
408 ir_type *get_class_trans_subtype_first(const ir_type *tp) {
409 assert_valid_state();
410 return pset_first(get_type_map(tp, d_down));
413 ir_type *get_class_trans_subtype_next(const ir_type *tp) {
414 assert_valid_state();
415 return pset_next(get_type_map(tp, d_down));
418 int is_class_trans_subtype(const ir_type *tp, const ir_type *subtp) {
419 assert_valid_state();
420 return (pset_find_ptr(get_type_map(tp, d_down), subtp) != NULL);
423 /* - supertype ----------------------------------------------------------- */
425 ir_type *get_class_trans_supertype_first(const ir_type *tp) {
426 assert_valid_state();
427 return pset_first(get_type_map(tp, d_up));
430 ir_type *get_class_trans_supertype_next(const ir_type *tp) {
431 assert_valid_state();
432 return pset_next(get_type_map(tp, d_up));
435 /* - overwrittenby ------------------------------------------------------- */
437 ir_entity *get_entity_trans_overwrittenby_first(const ir_entity *ent) {
438 assert_valid_state();
439 return pset_first(get_entity_map(ent, d_down));
442 ir_entity *get_entity_trans_overwrittenby_next(const ir_entity *ent) {
443 assert_valid_state();
444 return pset_next(get_entity_map(ent, d_down));
447 /* - overwrites ---------------------------------------------------------- */
450 /** Iterate over all transitive overwritten entities. */
451 ir_entity *get_entity_trans_overwrites_first(const ir_entity *ent) {
452 assert_valid_state();
453 return pset_first(get_entity_map(ent, d_up));
456 ir_entity *get_entity_trans_overwrites_next(const ir_entity *ent) {
457 assert_valid_state();
458 return pset_next(get_entity_map(ent, d_up));
462 /* ----------------------------------------------------------------------- */
463 /* Classify pairs of types/entities in the inheritance relations. */
464 /* ----------------------------------------------------------------------- */
466 /** Returns true if low is subclass of high. */
467 static int check_is_SubClass_of(ir_type *low, ir_type *high) {
470 /* depth first search from high downwards. */
471 n_subtypes = get_class_n_subtypes(high);
472 for (i = 0; i < n_subtypes; i++) {
473 ir_type *stp = get_class_subtype(high, i);
474 if (low == stp) return 1;
475 if (is_SubClass_of(low, stp))
481 /* Returns true if low is subclass of high. */
482 int is_SubClass_of(ir_type *low, ir_type *high) {
483 assert(is_Class_type(low) && is_Class_type(high));
485 if (low == high) return 1;
487 if (get_irp_inh_transitive_closure_state() == inh_transitive_closure_valid) {
488 pset *m = get_type_map(high, d_down);
489 return pset_find_ptr(m, low) ? 1 : 0;
491 return check_is_SubClass_of(low, high);
495 /* Subclass check for pointers to classes.
497 * Dereferences at both types the same amount of pointer types (as
498 * many as possible). If the remaining types are both class types
499 * and subclasses, returns true, else false. Can also be called with
500 * two class types. */
501 int is_SubClass_ptr_of(ir_type *low, ir_type *high) {
502 while (is_Pointer_type(low) && is_Pointer_type(high)) {
503 low = get_pointer_points_to_type(low);
504 high = get_pointer_points_to_type(high);
507 if (is_Class_type(low) && is_Class_type(high))
508 return is_SubClass_of(low, high);
512 int is_overwritten_by(ir_entity *high, ir_entity *low) {
513 int i, n_overwrittenby;
514 assert(is_entity(low) && is_entity(high));
516 if (get_irp_inh_transitive_closure_state() == inh_transitive_closure_valid) {
517 pset *m = get_entity_map(high, d_down);
518 return pset_find_ptr(m, low) ? 1 : 0;
521 /* depth first search from high downwards. */
522 n_overwrittenby = get_entity_n_overwrittenby(high);
523 for (i = 0; i < n_overwrittenby; i++) {
524 ir_entity *ov = get_entity_overwrittenby(high, i);
525 if (low == ov) return 1;
526 if (is_overwritten_by(low, ov))
532 /** Resolve polymorphy in the inheritance relation.
534 * Returns the dynamically referenced entity if the static entity and the
535 * dynamic type are given.
536 * Search downwards in overwritten tree.
538 * Need two routines because I want to assert the result.
540 static ir_entity *do_resolve_ent_polymorphy(ir_type *dynamic_class, ir_entity *static_ent) {
541 int i, n_overwrittenby;
543 if (get_entity_owner(static_ent) == dynamic_class) return static_ent;
545 n_overwrittenby = get_entity_n_overwrittenby(static_ent);
546 for (i = 0; i < n_overwrittenby; ++i) {
547 ir_entity *ent = get_entity_overwrittenby(static_ent, i);
548 ent = do_resolve_ent_polymorphy(dynamic_class, ent);
554 /* Resolve polymorphy in the inheritance relation.
556 * Returns the dynamically referenced entity if the static entity and the
557 * dynamic type are given.
558 * Search downwards in overwritten tree. */
559 ir_entity *resolve_ent_polymorphy(ir_type *dynamic_class, ir_entity *static_ent) {
561 assert(static_ent && is_entity(static_ent));
563 res = do_resolve_ent_polymorphy(dynamic_class, static_ent);
571 /* ----------------------------------------------------------------------- */
572 /* Class cast state handling. */
573 /* ----------------------------------------------------------------------- */
575 /* - State handling. ----------------------------------------- */
577 void set_irg_class_cast_state(ir_graph *irg, ir_class_cast_state s) {
578 if (get_irp_class_cast_state() > s) set_irp_class_cast_state(s);
579 irg->class_cast_state = s;
582 ir_class_cast_state get_irg_class_cast_state(ir_graph *irg) {
583 return irg->class_cast_state;
586 void set_irp_class_cast_state(ir_class_cast_state s) {
589 for (i = get_irp_n_irgs() - 1; i >= 0; --i)
590 assert(get_irg_class_cast_state(get_irp_irg(i)) >= s);
592 irp->class_cast_state = s;
595 ir_class_cast_state get_irp_class_cast_state(void) {
596 return irp->class_cast_state;
599 char *get_class_cast_state_string(ir_class_cast_state s) {
600 #define X(a) case a: return #a
602 X(ir_class_casts_any);
603 X(ir_class_casts_transitive);
604 X(ir_class_casts_normalized);
605 X(ir_class_casts_state_max);
606 default: return "invalid class cast state";
611 /* - State verification. ------------------------------------- */
613 typedef struct ccs_env {
614 ir_class_cast_state expected_state;
615 ir_class_cast_state worst_situation;
618 void verify_irn_class_cast_state(ir_node *n, void *env) {
619 ccs_env *ccs = (ccs_env *)env;
620 ir_class_cast_state this_state = ir_class_casts_any;
621 ir_type *fromtype, *totype;
624 if (get_irn_op(n) != op_Cast) return;
626 fromtype = get_irn_typeinfo_type(get_Cast_op(n));
627 totype = get_Cast_type(n);
629 while (is_Pointer_type(totype) && is_Pointer_type(fromtype)) {
630 totype = get_pointer_points_to_type(totype);
631 fromtype = get_pointer_points_to_type(fromtype);
635 if (!is_Class_type(totype)) return;
637 if (is_SubClass_of(totype, fromtype) ||
638 is_SubClass_of(fromtype, totype) ) {
639 this_state = ir_class_casts_transitive;
640 if ((get_class_supertype_index(totype, fromtype) != -1) ||
641 (get_class_supertype_index(fromtype, totype) != -1) ||
642 fromtype == totype) {
643 /* Das ist doch alt? Aus dem cvs aufgetaucht ...
644 if ((get_class_supertype_index(totype, fromtype) == -1) &&
645 (get_class_supertype_index(fromtype, totype) == -1) ) { */
646 this_state = ir_class_casts_normalized;
650 if (!(this_state >= ccs->expected_state)) {
651 ir_printf(" Node is %+F\n", n);
652 ir_printf(" totype %+F\n", totype);
653 ir_printf(" fromtype %+F\n", fromtype);
654 ir_printf(" this_state: %s, exp. state: %s\n",
655 get_class_cast_state_string(this_state),
656 get_class_cast_state_string(ccs->expected_state));
657 assert(this_state >= ccs->expected_state &&
658 "invalid state class cast state setting in graph");
661 if (this_state < ccs->worst_situation)
662 ccs->worst_situation = this_state;
665 /** Verify that the graph meets requirements of state set. */
666 void verify_irg_class_cast_state(ir_graph *irg) {
669 FIRM_DBG_REGISTER(dbg, "firm.tr.inheritance");
671 env.expected_state = get_irg_class_cast_state(irg);
672 env.worst_situation = ir_class_casts_normalized;
674 irg_walk_graph(irg, NULL, verify_irn_class_cast_state, &env);
676 if ((env.worst_situation > env.expected_state)) {
677 DB((dbg, LEVEL_1, "Note: class cast state is set lower than reqired "
678 "in graph \n\t%+F\n", irg));
679 DB((dbg, LEVEL_1, " state is %s, reqired is %s\n",
680 get_class_cast_state_string(env.expected_state),
681 get_class_cast_state_string(env.worst_situation)));