1 /*
2 * Copyright (C) 1995-2011 University of Karlsruhe. All right reserved.
3 *
4 * This file is part of libFirm.
5 *
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.
10 *
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.
14 *
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
17 * PURPOSE.
18 */
19
20 /**
21 * @file tr_inheritance.c
22 * @brief Utility routines for inheritance representation
23 * @author Goetz Lindenmaier
24 */
25 #include "config.h"
26
27 #include "debug.h"
28 #include "typerep.h"
29 #include "irgraph_t.h"
30 #include "irprog_t.h"
31 #include "irprintf.h"
32 #include "pset.h"
33 #include "set.h"
34 #include "irgwalk.h"
35 #include "irflag.h"
36
37 /* ----------------------------------------------------------------------- */
38 /* Resolve implicit inheritance. */
39 /* ----------------------------------------------------------------------- */
40
default_mangle_inherited_name(const ir_entity * super,const ir_type * clss)41 ident *default_mangle_inherited_name(const ir_entity *super, const ir_type *clss)
42 {
43 return id_mangle_u(new_id_from_str("inh"), id_mangle_u(get_class_ident(clss), get_entity_ident(super)));
44 }
45
46 /** Replicates all entities in all super classes that are not overwritten
47 by an entity of this class. */
copy_entities_from_superclass(ir_type * clss,void * env)48 static void copy_entities_from_superclass(ir_type *clss, void *env)
49 {
50 size_t i;
51 size_t j;
52 size_t k;
53 size_t l;
54 int overwritten;
55 ir_type *super;
56 ir_entity *inhent, *thisent;
57 mangle_inherited_name_func *mfunc = *(mangle_inherited_name_func **)env;
58
59 for (i = 0; i < get_class_n_supertypes(clss); i++) {
60 super = get_class_supertype(clss, i);
61 assert(is_Class_type(super) && "not a class");
62 for (j = 0; j < get_class_n_members(super); j++) {
63 inhent = get_class_member(super, j);
64 /* check whether inhent is already overwritten */
65 overwritten = 0;
66 for (k = 0; (k < get_class_n_members(clss)) && (overwritten == 0); k++) {
67 thisent = get_class_member(clss, k);
68 for (l = 0; l < get_entity_n_overwrites(thisent); l++) {
69 if (inhent == get_entity_overwrites(thisent, l)) {
70 /* overwritten - do not copy */
71 overwritten = 1;
72 break;
73 }
74 }
75 }
76 /* Inherit entity */
77 if (!overwritten) {
78 thisent = copy_entity_own(inhent, clss);
79 add_entity_overwrites(thisent, inhent);
80 if (get_entity_peculiarity(inhent) == peculiarity_existent)
81 set_entity_peculiarity(thisent, peculiarity_inherited);
82 set_entity_ld_ident(thisent, mfunc(inhent, clss));
83 if (get_entity_linkage(inhent) & IR_LINKAGE_CONSTANT) {
84 assert(is_atomic_entity(inhent) && /* @@@ */
85 "Inheritance of constant, compound entities not implemented");
86 add_entity_linkage(thisent, IR_LINKAGE_CONSTANT);
87 set_atomic_ent_value(thisent, get_atomic_ent_value(inhent));
88 }
89 }
90 }
91 }
92 }
93
resolve_inheritance(mangle_inherited_name_func * mfunc)94 void resolve_inheritance(mangle_inherited_name_func *mfunc)
95 {
96 if (!mfunc)
97 mfunc = default_mangle_inherited_name;
98 class_walk_super2sub(copy_entities_from_superclass, NULL, (void *)&mfunc);
99 }
100
101
102 /* ----------------------------------------------------------------------- */
103 /* The transitive closure of the subclass/superclass and */
104 /* overwrites/overwrittenby relation. */
105 /* */
106 /* A walk over the ir (O(#types+#entities)) computes the transitive */
107 /* closure. Adding a new type/entity or changing the basic relations in */
108 /* some other way invalidates the transitive closure, i.e., it is not */
109 /* updated by the basic functions. */
110 /* */
111 /* All functions are named as their counterparts for the basic relations, */
112 /* adding the infix 'trans_'. */
113 /* ----------------------------------------------------------------------- */
114
set_irp_inh_transitive_closure_state(inh_transitive_closure_state s)115 void set_irp_inh_transitive_closure_state(inh_transitive_closure_state s)
116 {
117 irp->inh_trans_closure_state = s;
118 }
invalidate_irp_inh_transitive_closure_state(void)119 void invalidate_irp_inh_transitive_closure_state(void)
120 {
121 if (irp->inh_trans_closure_state == inh_transitive_closure_valid)
122 irp->inh_trans_closure_state = inh_transitive_closure_invalid;
123 }
get_irp_inh_transitive_closure_state(void)124 inh_transitive_closure_state get_irp_inh_transitive_closure_state(void)
125 {
126 return irp->inh_trans_closure_state;
127 }
128
assert_valid_state(void)129 static void assert_valid_state(void)
130 {
131 assert(irp->inh_trans_closure_state == inh_transitive_closure_valid ||
132 irp->inh_trans_closure_state == inh_transitive_closure_invalid);
133 }
134
135 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
136 /* There is a set that extends each entity/type with two new */
137 /* fields: one for the upwards directed relation: 'up' (supertype, */
138 /* overwrites) and one for the downwards directed relation: 'down' (sub- */
139 /* type, overwrittenby. These fields contain psets (and maybe later */
140 /* arrays) listing all subtypes... */
141 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
142
143 typedef enum {
144 d_up = 0,
145 d_down = 1,
146 } dir;
147
148 typedef struct {
149 const firm_kind *kind; /**< An entity or type. */
150 pset *directions[2];
151 } tr_inh_trans_tp;
152
153 /* We use this set for all types and entities. */
154 static set *tr_inh_trans_set = NULL;
155
156 /**
157 * Compare two tr_inh_trans_tp entries.
158 */
tr_inh_trans_cmp(const void * e1,const void * e2,size_t size)159 static int tr_inh_trans_cmp(const void *e1, const void *e2, size_t size)
160 {
161 const tr_inh_trans_tp *ef1 = (const tr_inh_trans_tp*)e1;
162 const tr_inh_trans_tp *ef2 = (const tr_inh_trans_tp*)e2;
163 (void) size;
164
165 return ef1->kind != ef2->kind;
166 }
167
168 /**
169 * calculate the hash value of an tr_inh_trans_tp
170 */
tr_inh_trans_hash(const tr_inh_trans_tp * v)171 static inline unsigned int tr_inh_trans_hash(const tr_inh_trans_tp *v)
172 {
173 return hash_ptr(v->kind);
174 }
175
176 /* This always completes successfully. */
get_firm_kind_entry(const firm_kind * k)177 static tr_inh_trans_tp *get_firm_kind_entry(const firm_kind *k)
178 {
179 tr_inh_trans_tp a, *found;
180 a.kind = k;
181
182 if (!tr_inh_trans_set) tr_inh_trans_set = new_set(tr_inh_trans_cmp, 128);
183
184 found = set_find(tr_inh_trans_tp, tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
185 if (!found) {
186 a.directions[d_up] = pset_new_ptr(16);
187 a.directions[d_down] = pset_new_ptr(16);
188 found = set_insert(tr_inh_trans_tp, tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
189 }
190 return found;
191 }
192
get_entity_map(const ir_entity * ent,dir d)193 static pset *get_entity_map(const ir_entity *ent, dir d)
194 {
195 tr_inh_trans_tp *found;
196
197 assert(is_entity(ent));
198 found = get_firm_kind_entry((const firm_kind *)ent);
199 return found->directions[d];
200 }
201
get_type_map(const ir_type * tp,dir d)202 static pset *get_type_map(const ir_type *tp, dir d)
203 {
204 tr_inh_trans_tp *found;
205
206 assert(is_type(tp));
207 found = get_firm_kind_entry((const firm_kind *)tp);
208 return found->directions[d];
209 }
210
211
212 /**
213 * Walk over all types reachable from tp in the sub/supertype
214 * relation and compute the closure for the two downwards directed
215 * relations.
216 *
217 * The walk in the dag formed by the relation is tricky: We must visit
218 * all subtypes before visiting the supertypes. So we first walk down.
219 * Then we can compute the closure for this type. Then we walk up.
220 * As we call ourselves recursive, and walk in both directions, there
221 * can be cycles. So we have to make sure, that if we visit a node
222 * a second time (in a walk up) we do nothing. For this we increment
223 * the master visited flag twice.
224 * If the type is marked with master_flag_visited-1 it is on the stack.
225 * If it is marked with master_flag_visited it is fully processed.
226 *
227 * Well, we still miss some candidates ... */
compute_down_closure(ir_type * tp)228 static void compute_down_closure(ir_type *tp)
229 {
230 pset *myset, *subset;
231 size_t i, n_subtypes, n_members, n_supertypes;
232 ir_visited_t master_visited = get_master_type_visited();
233
234 assert(is_Class_type(tp));
235
236 set_type_visited(tp, master_visited-1);
237
238 /* Recursive descend. */
239 n_subtypes = get_class_n_subtypes(tp);
240 for (i = 0; i < n_subtypes; ++i) {
241 ir_type *stp = get_class_subtype(tp, i);
242 if (get_type_visited(stp) < master_visited-1) {
243 compute_down_closure(stp);
244 }
245 }
246
247 /* types */
248 myset = get_type_map(tp, d_down);
249 for (i = 0; i < n_subtypes; ++i) {
250 ir_type *stp = get_class_subtype(tp, i);
251 subset = get_type_map(stp, d_down);
252 pset_insert_ptr(myset, stp);
253 pset_insert_pset_ptr(myset, subset);
254 }
255
256 /* entities */
257 n_members = get_class_n_members(tp);
258 for (i = 0; i < n_members; ++i) {
259 ir_entity *mem = get_class_member(tp, i);
260 size_t j, n_overwrittenby = get_entity_n_overwrittenby(mem);
261
262 myset = get_entity_map(mem, d_down);
263 for (j = 0; j < n_overwrittenby; ++j) {
264 ir_entity *ov = get_entity_overwrittenby(mem, j);
265 subset = get_entity_map(ov, d_down);
266 pset_insert_ptr(myset, ov);
267 pset_insert_pset_ptr(myset, subset);
268 }
269 }
270
271 mark_type_visited(tp);
272
273 /* Walk up. */
274 n_supertypes = get_class_n_supertypes(tp);
275 for (i = 0; i < n_supertypes; ++i) {
276 ir_type *stp = get_class_supertype(tp, i);
277 if (get_type_visited(stp) < master_visited-1) {
278 compute_down_closure(stp);
279 }
280 }
281 }
282
compute_up_closure(ir_type * tp)283 static void compute_up_closure(ir_type *tp)
284 {
285 pset *myset, *subset;
286 size_t i, n_subtypes, n_members, n_supertypes;
287 ir_visited_t master_visited = get_master_type_visited();
288
289 assert(is_Class_type(tp));
290
291 set_type_visited(tp, master_visited-1);
292
293 /* Recursive descend. */
294 n_supertypes = get_class_n_supertypes(tp);
295 for (i = 0; i < n_supertypes; ++i) {
296 ir_type *stp = get_class_supertype(tp, i);
297 if (get_type_visited(stp) < get_master_type_visited()-1) {
298 compute_up_closure(stp);
299 }
300 }
301
302 /* types */
303 myset = get_type_map(tp, d_up);
304 for (i = 0; i < n_supertypes; ++i) {
305 ir_type *stp = get_class_supertype(tp, i);
306 subset = get_type_map(stp, d_up);
307 pset_insert_ptr(myset, stp);
308 pset_insert_pset_ptr(myset, subset);
309 }
310
311 /* entities */
312 n_members = get_class_n_members(tp);
313 for (i = 0; i < n_members; ++i) {
314 ir_entity *mem = get_class_member(tp, i);
315 size_t j, n_overwrites = get_entity_n_overwrites(mem);
316
317 myset = get_entity_map(mem, d_up);
318 for (j = 0; j < n_overwrites; ++j) {
319 ir_entity *ov = get_entity_overwrites(mem, j);
320 subset = get_entity_map(ov, d_up);
321 pset_insert_pset_ptr(myset, subset);
322 pset_insert_ptr(myset, ov);
323 }
324 }
325
326 mark_type_visited(tp);
327
328 /* Walk down. */
329 n_subtypes = get_class_n_subtypes(tp);
330 for (i = 0; i < n_subtypes; ++i) {
331 ir_type *stp = get_class_subtype(tp, i);
332 if (get_type_visited(stp) < master_visited-1) {
333 compute_up_closure(stp);
334 }
335 }
336 }
337
compute_inh_transitive_closure(void)338 void compute_inh_transitive_closure(void)
339 {
340 size_t i, n_types = get_irp_n_types();
341 free_inh_transitive_closure();
342
343 /* The 'down' relation */
344 irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
345 inc_master_type_visited(); /* Inc twice: one if on stack, second if values computed. */
346 inc_master_type_visited();
347 for (i = 0; i < n_types; ++i) {
348 ir_type *tp = get_irp_type(i);
349 if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
350 size_t j, n_subtypes = get_class_n_subtypes(tp);
351 int has_unmarked_subtype = 0;
352
353 assert(get_type_visited(tp) < get_master_type_visited()-1);
354 for (j = 0; j < n_subtypes; ++j) {
355 ir_type *stp = get_class_subtype(tp, j);
356 if (type_not_visited(stp)) {
357 has_unmarked_subtype = 1;
358 break;
359 }
360 }
361
362 /* This is a good starting point. */
363 if (!has_unmarked_subtype)
364 compute_down_closure(tp);
365 }
366 }
367
368 /* The 'up' relation */
369 inc_master_type_visited();
370 inc_master_type_visited();
371 for (i = 0; i < n_types; ++i) {
372 ir_type *tp = get_irp_type(i);
373 if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
374 size_t j, n_supertypes = get_class_n_supertypes(tp);
375 int has_unmarked_supertype = 0;
376
377 assert(get_type_visited(tp) < get_master_type_visited()-1);
378 for (j = 0; j < n_supertypes; ++j) {
379 ir_type *stp = get_class_supertype(tp, j);
380 if (type_not_visited(stp)) {
381 has_unmarked_supertype = 1;
382 break;
383 }
384 }
385
386 /* This is a good starting point. */
387 if (!has_unmarked_supertype)
388 compute_up_closure(tp);
389 }
390 }
391
392 irp->inh_trans_closure_state = inh_transitive_closure_valid;
393 irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
394 }
395
free_inh_transitive_closure(void)396 void free_inh_transitive_closure(void)
397 {
398 if (tr_inh_trans_set) {
399 foreach_set(tr_inh_trans_set, tr_inh_trans_tp, elt) {
400 del_pset(elt->directions[d_up]);
401 del_pset(elt->directions[d_down]);
402 }
403 del_set(tr_inh_trans_set);
404 tr_inh_trans_set = NULL;
405 }
406 irp->inh_trans_closure_state = inh_transitive_closure_none;
407 }
408
409 /* - subtype ------------------------------------------------------------- */
410
get_class_trans_subtype_first(const ir_type * tp)411 ir_type *get_class_trans_subtype_first(const ir_type *tp)
412 {
413 assert_valid_state();
414 return pset_first(ir_type, get_type_map(tp, d_down));
415 }
416
get_class_trans_subtype_next(const ir_type * tp)417 ir_type *get_class_trans_subtype_next(const ir_type *tp)
418 {
419 assert_valid_state();
420 return pset_next(ir_type, get_type_map(tp, d_down));
421 }
422
is_class_trans_subtype(const ir_type * tp,const ir_type * subtp)423 int is_class_trans_subtype(const ir_type *tp, const ir_type *subtp)
424 {
425 assert_valid_state();
426 return (pset_find_ptr(get_type_map(tp, d_down), subtp) != NULL);
427 }
428
429 /* - supertype ----------------------------------------------------------- */
430
get_class_trans_supertype_first(const ir_type * tp)431 ir_type *get_class_trans_supertype_first(const ir_type *tp)
432 {
433 assert_valid_state();
434 return pset_first(ir_type, get_type_map(tp, d_up));
435 }
436
get_class_trans_supertype_next(const ir_type * tp)437 ir_type *get_class_trans_supertype_next(const ir_type *tp)
438 {
439 assert_valid_state();
440 return pset_next(ir_type, get_type_map(tp, d_up));
441 }
442
443 /* - overwrittenby ------------------------------------------------------- */
444
get_entity_trans_overwrittenby_first(const ir_entity * ent)445 ir_entity *get_entity_trans_overwrittenby_first(const ir_entity *ent)
446 {
447 assert_valid_state();
448 return pset_first(ir_entity, get_entity_map(ent, d_down));
449 }
450
get_entity_trans_overwrittenby_next(const ir_entity * ent)451 ir_entity *get_entity_trans_overwrittenby_next(const ir_entity *ent)
452 {
453 assert_valid_state();
454 return pset_next(ir_entity, get_entity_map(ent, d_down));
455 }
456
457 /* - overwrites ---------------------------------------------------------- */
458
459
get_entity_trans_overwrites_first(const ir_entity * ent)460 ir_entity *get_entity_trans_overwrites_first(const ir_entity *ent)
461 {
462 assert_valid_state();
463 return pset_first(ir_entity, get_entity_map(ent, d_up));
464 }
465
get_entity_trans_overwrites_next(const ir_entity * ent)466 ir_entity *get_entity_trans_overwrites_next(const ir_entity *ent)
467 {
468 assert_valid_state();
469 return pset_next(ir_entity, get_entity_map(ent, d_up));
470 }
471
472
473 /* ----------------------------------------------------------------------- */
474 /* Classify pairs of types/entities in the inheritance relations. */
475 /* ----------------------------------------------------------------------- */
476
477 /** Returns true if low is subclass of high. */
check_is_SubClass_of(ir_type * low,ir_type * high)478 static int check_is_SubClass_of(ir_type *low, ir_type *high)
479 {
480 size_t i, n_subtypes;
481
482 /* depth first search from high downwards. */
483 n_subtypes = get_class_n_subtypes(high);
484 for (i = 0; i < n_subtypes; i++) {
485 ir_type *stp = get_class_subtype(high, i);
486 if (low == stp) return 1;
487 if (is_SubClass_of(low, stp))
488 return 1;
489 }
490 return 0;
491 }
492
is_SubClass_of(ir_type * low,ir_type * high)493 int is_SubClass_of(ir_type *low, ir_type *high)
494 {
495 assert(is_Class_type(low) && is_Class_type(high));
496
497 if (low == high) return 1;
498
499 if (get_irp_inh_transitive_closure_state() == inh_transitive_closure_valid) {
500 pset *m = get_type_map(high, d_down);
501 return pset_find_ptr(m, low) ? 1 : 0;
502 }
503 return check_is_SubClass_of(low, high);
504 }
505
is_SubClass_ptr_of(ir_type * low,ir_type * high)506 int is_SubClass_ptr_of(ir_type *low, ir_type *high)
507 {
508 while (is_Pointer_type(low) && is_Pointer_type(high)) {
509 low = get_pointer_points_to_type(low);
510 high = get_pointer_points_to_type(high);
511 }
512
513 if (is_Class_type(low) && is_Class_type(high))
514 return is_SubClass_of(low, high);
515 return 0;
516 }
517
is_overwritten_by(ir_entity * high,ir_entity * low)518 int is_overwritten_by(ir_entity *high, ir_entity *low)
519 {
520 size_t i, n_overwrittenby;
521 assert(is_entity(low) && is_entity(high));
522
523 if (get_irp_inh_transitive_closure_state() == inh_transitive_closure_valid) {
524 pset *m = get_entity_map(high, d_down);
525 return pset_find_ptr(m, low) ? 1 : 0;
526 }
527
528 /* depth first search from high downwards. */
529 n_overwrittenby = get_entity_n_overwrittenby(high);
530 for (i = 0; i < n_overwrittenby; i++) {
531 ir_entity *ov = get_entity_overwrittenby(high, i);
532 if (low == ov) return 1;
533 if (is_overwritten_by(low, ov))
534 return 1;
535 }
536 return 0;
537 }
538
539 /** Resolve polymorphy in the inheritance relation.
540 *
541 * Returns the dynamically referenced entity if the static entity and the
542 * dynamic type are given.
543 * Search downwards in overwritten tree.
544 *
545 * Need two routines because I want to assert the result.
546 */
do_resolve_ent_polymorphy(ir_type * dynamic_class,ir_entity * static_ent)547 static ir_entity *do_resolve_ent_polymorphy(ir_type *dynamic_class, ir_entity *static_ent)
548 {
549 size_t i, n_overwrittenby;
550
551 ir_type *owner = get_entity_owner(static_ent);
552 if (owner == dynamic_class) return static_ent;
553
554 // if the owner of the static_ent already is more special than the dynamic
555 // type to check against - stop here.
556 if (! is_SubClass_of(dynamic_class, owner)) return NULL;
557
558 n_overwrittenby = get_entity_n_overwrittenby(static_ent);
559 for (i = 0; i < n_overwrittenby; ++i) {
560 ir_entity *ent = get_entity_overwrittenby(static_ent, i);
561 ent = do_resolve_ent_polymorphy(dynamic_class, ent);
562 if (ent) return ent;
563 }
564
565 // No further specialization of static_ent has been found
566 return static_ent;
567 }
568
resolve_ent_polymorphy(ir_type * dynamic_class,ir_entity * static_ent)569 ir_entity *resolve_ent_polymorphy(ir_type *dynamic_class, ir_entity *static_ent)
570 {
571 ir_entity *res;
572 assert(static_ent && is_entity(static_ent));
573
574 res = do_resolve_ent_polymorphy(dynamic_class, static_ent);
575 assert(res);
576
577 return res;
578 }
579
580
581
582 /* ----------------------------------------------------------------------- */
583 /* Class cast state handling. */
584 /* ----------------------------------------------------------------------- */
585
586 /* - State handling. ----------------------------------------- */
587
set_irg_class_cast_state(ir_graph * irg,ir_class_cast_state s)588 void set_irg_class_cast_state(ir_graph *irg, ir_class_cast_state s)
589 {
590 if (get_irp_class_cast_state() > s)
591 set_irp_class_cast_state(s);
592 irg->class_cast_state = s;
593 }
594
get_irg_class_cast_state(const ir_graph * irg)595 ir_class_cast_state get_irg_class_cast_state(const ir_graph *irg)
596 {
597 return irg->class_cast_state;
598 }
599
set_irp_class_cast_state(ir_class_cast_state s)600 void set_irp_class_cast_state(ir_class_cast_state s)
601 {
602 #ifndef NDEBUG
603 size_t i, n;
604 for (i = 0, n = get_irp_n_irgs(); i < n; ++i)
605 assert(get_irg_class_cast_state(get_irp_irg(i)) >= s);
606 #endif
607 irp->class_cast_state = s;
608 }
609
get_irp_class_cast_state(void)610 ir_class_cast_state get_irp_class_cast_state(void)
611 {
612 return irp->class_cast_state;
613 }
614