2 * Copyright (C) 1995-2011 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
29 #include "irgraph_t.h"
37 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
39 /* ----------------------------------------------------------------------- */
40 /* Resolve implicit inheritance. */
41 /* ----------------------------------------------------------------------- */
43 ident *default_mangle_inherited_name(const ir_entity *super, const ir_type *clss)
45 return id_mangle_u(new_id_from_str("inh"), id_mangle_u(get_class_ident(clss), get_entity_ident(super)));
48 /** Replicates all entities in all super classes that are not overwritten
49 by an entity of this class. */
50 static void copy_entities_from_superclass(ir_type *clss, void *env)
58 ir_entity *inhent, *thisent;
59 mangle_inherited_name_func *mfunc = *(mangle_inherited_name_func **)env;
61 for (i = 0; i < get_class_n_supertypes(clss); i++) {
62 super = get_class_supertype(clss, i);
63 assert(is_Class_type(super) && "not a class");
64 for (j = 0; j < get_class_n_members(super); j++) {
65 inhent = get_class_member(super, j);
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_linkage(inhent) & IR_LINKAGE_CONSTANT) {
86 assert(is_atomic_entity(inhent) && /* @@@ */
87 "Inheritance of constant, compound entities not implemented");
88 add_entity_linkage(thisent, IR_LINKAGE_CONSTANT);
89 set_atomic_ent_value(thisent, get_atomic_ent_value(inhent));
96 void resolve_inheritance(mangle_inherited_name_func *mfunc)
99 mfunc = default_mangle_inherited_name;
100 class_walk_super2sub(copy_entities_from_superclass, NULL, (void *)&mfunc);
104 /* ----------------------------------------------------------------------- */
105 /* The transitive closure of the subclass/superclass and */
106 /* overwrites/overwrittenby relation. */
108 /* A walk over the ir (O(#types+#entities)) computes the transitive */
109 /* closure. Adding a new type/entity or changing the basic relations in */
110 /* some other way invalidates the transitive closure, i.e., it is not */
111 /* updated by the basic functions. */
113 /* All functions are named as their counterparts for the basic relations, */
114 /* adding the infix 'trans_'. */
115 /* ----------------------------------------------------------------------- */
117 void set_irp_inh_transitive_closure_state(inh_transitive_closure_state s)
119 irp->inh_trans_closure_state = s;
121 void invalidate_irp_inh_transitive_closure_state(void)
123 if (irp->inh_trans_closure_state == inh_transitive_closure_valid)
124 irp->inh_trans_closure_state = inh_transitive_closure_invalid;
126 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)
133 assert(irp->inh_trans_closure_state == inh_transitive_closure_valid ||
134 irp->inh_trans_closure_state == inh_transitive_closure_invalid);
137 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
138 /* There is a set that extends each entity/type with two new */
139 /* fields: one for the upwards directed relation: 'up' (supertype, */
140 /* overwrites) and one for the downwards directed relation: 'down' (sub- */
141 /* type, overwrittenby. These fields contain psets (and maybe later */
142 /* arrays) listing all subtypes... */
143 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
151 const firm_kind *kind; /**< An entity or type. */
155 /* We use this set for all types and entities. */
156 static set *tr_inh_trans_set = NULL;
159 * Compare two tr_inh_trans_tp entries.
161 static int tr_inh_trans_cmp(const void *e1, const void *e2, size_t size)
163 const tr_inh_trans_tp *ef1 = (const tr_inh_trans_tp*)e1;
164 const tr_inh_trans_tp *ef2 = (const tr_inh_trans_tp*)e2;
167 return ef1->kind != ef2->kind;
171 * calculate the hash value of an tr_inh_trans_tp
173 static inline unsigned int tr_inh_trans_hash(const tr_inh_trans_tp *v)
175 return hash_ptr(v->kind);
178 /* This always completes successfully. */
179 static tr_inh_trans_tp *get_firm_kind_entry(const firm_kind *k)
181 tr_inh_trans_tp a, *found;
184 if (!tr_inh_trans_set) tr_inh_trans_set = new_set(tr_inh_trans_cmp, 128);
186 found = (tr_inh_trans_tp*)set_find(tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
188 a.directions[d_up] = pset_new_ptr(16);
189 a.directions[d_down] = pset_new_ptr(16);
190 found = (tr_inh_trans_tp*)set_insert(tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
195 static pset *get_entity_map(const ir_entity *ent, dir d)
197 tr_inh_trans_tp *found;
199 assert(is_entity(ent));
200 found = get_firm_kind_entry((const firm_kind *)ent);
201 return found->directions[d];
204 static pset *get_type_map(const ir_type *tp, dir d)
206 tr_inh_trans_tp *found;
209 found = get_firm_kind_entry((const firm_kind *)tp);
210 return found->directions[d];
215 * Walk over all types reachable from tp in the sub/supertype
216 * relation and compute the closure for the two downwards directed
219 * The walk in the dag formed by the relation is tricky: We must visit
220 * all subtypes before visiting the supertypes. So we first walk down.
221 * Then we can compute the closure for this type. Then we walk up.
222 * As we call ourselves recursive, and walk in both directions, there
223 * can be cycles. So we have to make sure, that if we visit a node
224 * a second time (in a walk up) we do nothing. For this we increment
225 * the master visited flag twice.
226 * If the type is marked with master_flag_visited-1 it is on the stack.
227 * If it is marked with master_flag_visited it is fully processed.
229 * Well, we still miss some candidates ... */
230 static void compute_down_closure(ir_type *tp)
232 pset *myset, *subset;
233 size_t i, n_subtypes, n_members, n_supertypes;
234 ir_visited_t master_visited = get_master_type_visited();
236 assert(is_Class_type(tp));
238 set_type_visited(tp, master_visited-1);
240 /* Recursive descend. */
241 n_subtypes = get_class_n_subtypes(tp);
242 for (i = 0; i < n_subtypes; ++i) {
243 ir_type *stp = get_class_subtype(tp, i);
244 if (get_type_visited(stp) < master_visited-1) {
245 compute_down_closure(stp);
250 myset = get_type_map(tp, d_down);
251 for (i = 0; i < n_subtypes; ++i) {
252 ir_type *stp = get_class_subtype(tp, i);
253 subset = get_type_map(stp, d_down);
254 pset_insert_ptr(myset, stp);
255 pset_insert_pset_ptr(myset, subset);
259 n_members = get_class_n_members(tp);
260 for (i = 0; i < n_members; ++i) {
261 ir_entity *mem = get_class_member(tp, i);
262 size_t j, n_overwrittenby = get_entity_n_overwrittenby(mem);
264 myset = get_entity_map(mem, d_down);
265 for (j = 0; j < n_overwrittenby; ++j) {
266 ir_entity *ov = get_entity_overwrittenby(mem, j);
267 subset = get_entity_map(ov, d_down);
268 pset_insert_ptr(myset, ov);
269 pset_insert_pset_ptr(myset, subset);
273 mark_type_visited(tp);
276 n_supertypes = get_class_n_supertypes(tp);
277 for (i = 0; i < n_supertypes; ++i) {
278 ir_type *stp = get_class_supertype(tp, i);
279 if (get_type_visited(stp) < master_visited-1) {
280 compute_down_closure(stp);
285 static void compute_up_closure(ir_type *tp)
287 pset *myset, *subset;
288 size_t i, n_subtypes, n_members, n_supertypes;
289 ir_visited_t master_visited = get_master_type_visited();
291 assert(is_Class_type(tp));
293 set_type_visited(tp, master_visited-1);
295 /* Recursive descend. */
296 n_supertypes = get_class_n_supertypes(tp);
297 for (i = 0; i < n_supertypes; ++i) {
298 ir_type *stp = get_class_supertype(tp, i);
299 if (get_type_visited(stp) < get_master_type_visited()-1) {
300 compute_up_closure(stp);
305 myset = get_type_map(tp, d_up);
306 for (i = 0; i < n_supertypes; ++i) {
307 ir_type *stp = get_class_supertype(tp, i);
308 subset = get_type_map(stp, d_up);
309 pset_insert_ptr(myset, stp);
310 pset_insert_pset_ptr(myset, subset);
314 n_members = get_class_n_members(tp);
315 for (i = 0; i < n_members; ++i) {
316 ir_entity *mem = get_class_member(tp, i);
317 size_t j, n_overwrites = get_entity_n_overwrites(mem);
319 myset = get_entity_map(mem, d_up);
320 for (j = 0; j < n_overwrites; ++j) {
321 ir_entity *ov = get_entity_overwrites(mem, j);
322 subset = get_entity_map(ov, d_up);
323 pset_insert_pset_ptr(myset, subset);
324 pset_insert_ptr(myset, ov);
328 mark_type_visited(tp);
331 n_subtypes = get_class_n_subtypes(tp);
332 for (i = 0; i < n_subtypes; ++i) {
333 ir_type *stp = get_class_subtype(tp, i);
334 if (get_type_visited(stp) < master_visited-1) {
335 compute_up_closure(stp);
340 void compute_inh_transitive_closure(void)
342 size_t i, n_types = get_irp_n_types();
343 free_inh_transitive_closure();
345 /* The 'down' relation */
346 irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
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 ir_type *tp = get_irp_type(i);
351 if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
352 size_t j, n_subtypes = get_class_n_subtypes(tp);
353 int has_unmarked_subtype = 0;
355 assert(get_type_visited(tp) < get_master_type_visited()-1);
356 for (j = 0; j < n_subtypes; ++j) {
357 ir_type *stp = get_class_subtype(tp, j);
358 if (type_not_visited(stp)) {
359 has_unmarked_subtype = 1;
364 /* This is a good starting point. */
365 if (!has_unmarked_subtype)
366 compute_down_closure(tp);
370 /* The 'up' relation */
371 inc_master_type_visited();
372 inc_master_type_visited();
373 for (i = 0; i < n_types; ++i) {
374 ir_type *tp = get_irp_type(i);
375 if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
376 size_t j, n_supertypes = get_class_n_supertypes(tp);
377 int has_unmarked_supertype = 0;
379 assert(get_type_visited(tp) < get_master_type_visited()-1);
380 for (j = 0; j < n_supertypes; ++j) {
381 ir_type *stp = get_class_supertype(tp, j);
382 if (type_not_visited(stp)) {
383 has_unmarked_supertype = 1;
388 /* This is a good starting point. */
389 if (!has_unmarked_supertype)
390 compute_up_closure(tp);
394 irp->inh_trans_closure_state = inh_transitive_closure_valid;
395 irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
398 void free_inh_transitive_closure(void)
400 if (tr_inh_trans_set) {
401 tr_inh_trans_tp *elt;
402 for (elt = (tr_inh_trans_tp*)set_first(tr_inh_trans_set); elt != NULL;
403 elt = (tr_inh_trans_tp*)set_next(tr_inh_trans_set)) {
404 del_pset(elt->directions[d_up]);
405 del_pset(elt->directions[d_down]);
407 del_set(tr_inh_trans_set);
408 tr_inh_trans_set = NULL;
410 irp->inh_trans_closure_state = inh_transitive_closure_none;
413 /* - subtype ------------------------------------------------------------- */
415 ir_type *get_class_trans_subtype_first(const ir_type *tp)
417 assert_valid_state();
418 return (ir_type*)pset_first(get_type_map(tp, d_down));
421 ir_type *get_class_trans_subtype_next(const ir_type *tp)
423 assert_valid_state();
424 return (ir_type*)pset_next(get_type_map(tp, d_down));
427 int is_class_trans_subtype(const ir_type *tp, const ir_type *subtp)
429 assert_valid_state();
430 return (pset_find_ptr(get_type_map(tp, d_down), subtp) != NULL);
433 /* - supertype ----------------------------------------------------------- */
435 ir_type *get_class_trans_supertype_first(const ir_type *tp)
437 assert_valid_state();
438 return (ir_type*)pset_first(get_type_map(tp, d_up));
441 ir_type *get_class_trans_supertype_next(const ir_type *tp)
443 assert_valid_state();
444 return (ir_type*)pset_next(get_type_map(tp, d_up));
447 /* - overwrittenby ------------------------------------------------------- */
449 ir_entity *get_entity_trans_overwrittenby_first(const ir_entity *ent)
451 assert_valid_state();
452 return (ir_entity*)pset_first(get_entity_map(ent, d_down));
455 ir_entity *get_entity_trans_overwrittenby_next(const ir_entity *ent)
457 assert_valid_state();
458 return (ir_entity*)pset_next(get_entity_map(ent, d_down));
461 /* - overwrites ---------------------------------------------------------- */
464 ir_entity *get_entity_trans_overwrites_first(const ir_entity *ent)
466 assert_valid_state();
467 return (ir_entity*)pset_first(get_entity_map(ent, d_up));
470 ir_entity *get_entity_trans_overwrites_next(const ir_entity *ent)
472 assert_valid_state();
473 return (ir_entity*)pset_next(get_entity_map(ent, d_up));
477 /* ----------------------------------------------------------------------- */
478 /* Classify pairs of types/entities in the inheritance relations. */
479 /* ----------------------------------------------------------------------- */
481 /** Returns true if low is subclass of high. */
482 static int check_is_SubClass_of(ir_type *low, ir_type *high)
484 size_t i, n_subtypes;
486 /* depth first search from high downwards. */
487 n_subtypes = get_class_n_subtypes(high);
488 for (i = 0; i < n_subtypes; i++) {
489 ir_type *stp = get_class_subtype(high, i);
490 if (low == stp) return 1;
491 if (is_SubClass_of(low, stp))
497 int is_SubClass_of(ir_type *low, ir_type *high)
499 assert(is_Class_type(low) && is_Class_type(high));
501 if (low == high) return 1;
503 if (get_irp_inh_transitive_closure_state() == inh_transitive_closure_valid) {
504 pset *m = get_type_map(high, d_down);
505 return pset_find_ptr(m, low) ? 1 : 0;
507 return check_is_SubClass_of(low, high);
510 int is_SubClass_ptr_of(ir_type *low, ir_type *high)
512 while (is_Pointer_type(low) && is_Pointer_type(high)) {
513 low = get_pointer_points_to_type(low);
514 high = get_pointer_points_to_type(high);
517 if (is_Class_type(low) && is_Class_type(high))
518 return is_SubClass_of(low, high);
522 int is_overwritten_by(ir_entity *high, ir_entity *low)
524 size_t i, n_overwrittenby;
525 assert(is_entity(low) && is_entity(high));
527 if (get_irp_inh_transitive_closure_state() == inh_transitive_closure_valid) {
528 pset *m = get_entity_map(high, d_down);
529 return pset_find_ptr(m, low) ? 1 : 0;
532 /* depth first search from high downwards. */
533 n_overwrittenby = get_entity_n_overwrittenby(high);
534 for (i = 0; i < n_overwrittenby; i++) {
535 ir_entity *ov = get_entity_overwrittenby(high, i);
536 if (low == ov) return 1;
537 if (is_overwritten_by(low, ov))
543 /** Resolve polymorphy in the inheritance relation.
545 * Returns the dynamically referenced entity if the static entity and the
546 * dynamic type are given.
547 * Search downwards in overwritten tree.
549 * Need two routines because I want to assert the result.
551 static ir_entity *do_resolve_ent_polymorphy(ir_type *dynamic_class, ir_entity *static_ent)
553 size_t i, n_overwrittenby;
555 ir_type *owner = get_entity_owner(static_ent);
556 if (owner == dynamic_class) return static_ent;
558 // if the owner of the static_ent already is more special than the dynamic
559 // type to check against - stop here.
560 if (! is_SubClass_of(dynamic_class, owner)) return NULL;
562 n_overwrittenby = get_entity_n_overwrittenby(static_ent);
563 for (i = 0; i < n_overwrittenby; ++i) {
564 ir_entity *ent = get_entity_overwrittenby(static_ent, i);
565 ent = do_resolve_ent_polymorphy(dynamic_class, ent);
569 // No further specialization of static_ent has been found
573 ir_entity *resolve_ent_polymorphy(ir_type *dynamic_class, ir_entity *static_ent)
576 assert(static_ent && is_entity(static_ent));
578 res = do_resolve_ent_polymorphy(dynamic_class, static_ent);
586 /* ----------------------------------------------------------------------- */
587 /* Class cast state handling. */
588 /* ----------------------------------------------------------------------- */
590 /* - State handling. ----------------------------------------- */
592 void set_irg_class_cast_state(ir_graph *irg, ir_class_cast_state s)
594 if (get_irp_class_cast_state() > s)
595 set_irp_class_cast_state(s);
596 irg->class_cast_state = s;
599 ir_class_cast_state get_irg_class_cast_state(const ir_graph *irg)
601 return irg->class_cast_state;
604 void set_irp_class_cast_state(ir_class_cast_state s)
608 for (i = 0, n = get_irp_n_irgs(); i < n; ++i)
609 assert(get_irg_class_cast_state(get_irp_irg(i)) >= s);
611 irp->class_cast_state = s;
614 ir_class_cast_state get_irp_class_cast_state(void)
616 return irp->class_cast_state;
619 const char *get_class_cast_state_string(ir_class_cast_state s)
621 #define X(a) case a: return #a
623 X(ir_class_casts_any);
624 X(ir_class_casts_transitive);
625 X(ir_class_casts_normalized);
626 X(ir_class_casts_state_max);
627 default: return "invalid class cast state";
632 /* - State verification. ------------------------------------- */
634 typedef struct ccs_env {
635 ir_class_cast_state expected_state;
636 ir_class_cast_state worst_situation;
640 * Walker: check Casts.
642 static void verify_irn_class_cast_state(ir_node *n, void *env)
644 ccs_env *ccs = (ccs_env *)env;
645 ir_class_cast_state this_state = ir_class_casts_any;
646 ir_type *fromtype, *totype;
648 if (!is_Cast(n)) return;
650 fromtype = get_irn_typeinfo_type(get_Cast_op(n));
651 totype = get_Cast_type(n);
653 while (is_Pointer_type(totype) && is_Pointer_type(fromtype)) {
654 totype = get_pointer_points_to_type(totype);
655 fromtype = get_pointer_points_to_type(fromtype);
658 if (!is_Class_type(totype)) return;
660 if (is_SubClass_of(totype, fromtype) ||
661 is_SubClass_of(fromtype, totype)) {
662 this_state = ir_class_casts_transitive;
663 if ((get_class_supertype_index(totype, fromtype) != (size_t)-1) ||
664 (get_class_supertype_index(fromtype, totype) != (size_t)-1) ||
665 fromtype == totype) {
666 this_state = ir_class_casts_normalized;
670 if (!(this_state >= ccs->expected_state)) {
671 ir_printf(" Node is %+F\n", n);
672 ir_printf(" totype %+F\n", totype);
673 ir_printf(" fromtype %+F\n", fromtype);
674 ir_printf(" this_state: %s, exp. state: %s\n",
675 get_class_cast_state_string(this_state),
676 get_class_cast_state_string(ccs->expected_state));
677 assert(this_state >= ccs->expected_state &&
678 "invalid state class cast state setting in graph");
681 if (this_state < ccs->worst_situation)
682 ccs->worst_situation = this_state;
685 void verify_irg_class_cast_state(ir_graph *irg)
689 FIRM_DBG_REGISTER(dbg, "firm.tr.inheritance");
691 env.expected_state = get_irg_class_cast_state(irg);
692 env.worst_situation = ir_class_casts_normalized;
694 irg_walk_graph(irg, NULL, verify_irn_class_cast_state, &env);
696 if ((env.worst_situation > env.expected_state)) {
697 DB((dbg, LEVEL_1, "Note: class cast state is set lower than reqired "
698 "in graph \n\t%+F\n", irg));
699 DB((dbg, LEVEL_1, " state is %s, reqired is %s\n",
700 get_class_cast_state_string(env.expected_state),
701 get_class_cast_state_string(env.worst_situation)));