nsz Git - libfirm/blob - ir/tr/tr_inheritance.c

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief   Utility routines for inheritance representation
   9  * @author  Goetz Lindenmaier
  10  */
  11 #include "config.h"
  12
  13 #include "debug.h"
  14 #include "typerep.h"
  15 #include "irgraph_t.h"
  16 #include "irprog_t.h"
  17 #include "irprintf.h"
  18 #include "pset.h"
  19 #include "set.h"
  20 #include "irgwalk.h"
  21 #include "irflag.h"
  22
  23 /* ----------------------------------------------------------------------- */
  24 /* Resolve implicit inheritance.                                           */
  25 /* ----------------------------------------------------------------------- */
  26
  27 ident *default_mangle_inherited_name(const ir_entity *super, const ir_type *clss)
  28 {
  29         return id_mangle_u(new_id_from_str("inh"), id_mangle_u(get_class_ident(clss), get_entity_ident(super)));
  30 }
  31
  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)
  35 {
  36         size_t i;
  37         size_t j;
  38         size_t k;
  39         size_t l;
  40         int overwritten;
  41         ir_type *super;
  42         ir_entity *inhent, *thisent;
  43         mangle_inherited_name_func *mfunc = *(mangle_inherited_name_func **)env;
  44
  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 */
  50                         overwritten = 0;
  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 */
  56                                                 overwritten = 1;
  57                                                 break;
  58                                         }
  59                                 }
  60                         }
  61                         /* Inherit entity */
  62                         if (!overwritten) {
  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));
  73                                 }
  74                         }
  75                 }
  76         }
  77 }
  78
  79 void resolve_inheritance(mangle_inherited_name_func *mfunc)
  80 {
  81         if (!mfunc)
  82                 mfunc = default_mangle_inherited_name;
  83         class_walk_super2sub(copy_entities_from_superclass, NULL, (void *)&mfunc);
  84 }
  85
  86
  87 /* ----------------------------------------------------------------------- */
  88 /* The transitive closure of the subclass/superclass and                   */
  89 /* overwrites/overwrittenby relation.                                      */
  90 /*                                                                         */
  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.                                         */
  95 /*                                                                         */
  96 /* All functions are named as their counterparts for the basic relations,  */
  97 /* adding the infix 'trans_'.                                              */
  98 /* ----------------------------------------------------------------------- */
  99
 100 void                        set_irp_inh_transitive_closure_state(inh_transitive_closure_state s)
 101 {
 102         irp->inh_trans_closure_state = s;
 103 }
 104 void                        invalidate_irp_inh_transitive_closure_state(void)
 105 {
 106         if (irp->inh_trans_closure_state == inh_transitive_closure_valid)
 107                 irp->inh_trans_closure_state = inh_transitive_closure_invalid;
 108 }
 109 inh_transitive_closure_state get_irp_inh_transitive_closure_state(void)
 110 {
 111         return irp->inh_trans_closure_state;
 112 }
 113
 114 static void assert_valid_state(void)
 115 {
 116         assert(irp->inh_trans_closure_state == inh_transitive_closure_valid ||
 117                irp->inh_trans_closure_state == inh_transitive_closure_invalid);
 118 }
 119
 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 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
 127
 128 typedef enum {
 129         d_up   = 0,
 130         d_down = 1,
 131 } dir;
 132
 133 typedef struct {
 134         const firm_kind *kind;   /**< An entity or type. */
 135         pset *directions[2];
 136 } tr_inh_trans_tp;
 137
 138 /* We use this set for all types and entities.  */
 139 static set *tr_inh_trans_set = NULL;
 140
 141 /**
 142  * Compare two tr_inh_trans_tp entries.
 143  */
 144 static int tr_inh_trans_cmp(const void *e1, const void *e2, size_t size)
 145 {
 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;
 148         (void) size;
 149
 150         return ef1->kind != ef2->kind;
 151 }
 152
 153 /**
 154  * calculate the hash value of an tr_inh_trans_tp
 155  */
 156 static inline unsigned int tr_inh_trans_hash(const tr_inh_trans_tp *v)
 157 {
 158         return hash_ptr(v->kind);
 159 }
 160
 161 /* This always completes successfully. */
 162 static tr_inh_trans_tp *get_firm_kind_entry(const firm_kind *k)
 163 {
 164         tr_inh_trans_tp a, *found;
 165         a.kind = k;
 166
 167         if (!tr_inh_trans_set) tr_inh_trans_set = new_set(tr_inh_trans_cmp, 128);
 168
 169         found = set_find(tr_inh_trans_tp, tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
 170         if (!found) {
 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));
 174         }
 175         return found;
 176 }
 177
 178 static pset *get_entity_map(const ir_entity *ent, dir d)
 179 {
 180         tr_inh_trans_tp *found;
 181
 182         assert(is_entity(ent));
 183         found = get_firm_kind_entry((const firm_kind *)ent);
 184         return found->directions[d];
 185 }
 186
 187 static pset *get_type_map(const ir_type *tp, dir d)
 188 {
 189         tr_inh_trans_tp *found;
 190
 191         assert(is_type(tp));
 192         found = get_firm_kind_entry((const firm_kind *)tp);
 193         return found->directions[d];
 194 }
 195
 196
 197 /**
 198  * Walk over all types reachable from tp in the sub/supertype
 199  * relation and compute the closure for the two downwards directed
 200  * relations.
 201  *
 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.
 211  *
 212  * Well, we still miss some candidates ... */
 213 static void compute_down_closure(ir_type *tp)
 214 {
 215         pset *myset, *subset;
 216         size_t i, n_subtypes, n_members, n_supertypes;
 217         ir_visited_t master_visited = get_master_type_visited();
 218
 219         set_type_visited(tp, master_visited-1);
 220
 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);
 227                 }
 228         }
 229
 230         /* types */
 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);
 237         }
 238
 239         /* entities */
 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);
 244
 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);
 251                 }
 252         }
 253
 254         mark_type_visited(tp);
 255
 256         /* Walk up. */
 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);
 262                 }
 263         }
 264 }
 265
 266 static void compute_up_closure(ir_type *tp)
 267 {
 268         pset *myset, *subset;
 269         size_t i, n_subtypes, n_members, n_supertypes;
 270         ir_visited_t master_visited = get_master_type_visited();
 271
 272         set_type_visited(tp, master_visited-1);
 273
 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);
 280                 }
 281         }
 282
 283         /* types */
 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);
 290         }
 291
 292         /* entities */
 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);
 297
 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);
 304                 }
 305         }
 306
 307         mark_type_visited(tp);
 308
 309         /* Walk down. */
 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);
 315                 }
 316         }
 317 }
 318
 319 void compute_inh_transitive_closure(void)
 320 {
 321         size_t i, n_types = get_irp_n_types();
 322         free_inh_transitive_closure();
 323
 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;
 333
 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;
 339                                         break;
 340                                 }
 341                         }
 342
 343                         /* This is a good starting point. */
 344                         if (!has_unmarked_subtype)
 345                                 compute_down_closure(tp);
 346                 }
 347         }
 348
 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;
 357
 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;
 363                                         break;
 364                                 }
 365                         }
 366
 367                         /* This is a good starting point. */
 368                         if (!has_unmarked_supertype)
 369                                 compute_up_closure(tp);
 370                 }
 371         }
 372
 373         irp->inh_trans_closure_state = inh_transitive_closure_valid;
 374         irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
 375 }
 376
 377 void free_inh_transitive_closure(void)
 378 {
 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]);
 383                 }
 384                 del_set(tr_inh_trans_set);
 385                 tr_inh_trans_set = NULL;
 386         }
 387         irp->inh_trans_closure_state = inh_transitive_closure_none;
 388 }
 389
 390 /* - subtype ------------------------------------------------------------- */
 391
 392 ir_type *get_class_trans_subtype_first(const ir_type *tp)
 393 {
 394         assert_valid_state();
 395         return pset_first(ir_type, get_type_map(tp, d_down));
 396 }
 397
 398 ir_type *get_class_trans_subtype_next(const ir_type *tp)
 399 {
 400         assert_valid_state();
 401         return pset_next(ir_type, get_type_map(tp, d_down));
 402 }
 403
 404 int is_class_trans_subtype(const ir_type *tp, const ir_type *subtp)
 405 {
 406         assert_valid_state();
 407         return (pset_find_ptr(get_type_map(tp, d_down), subtp) != NULL);
 408 }
 409
 410 /* - supertype ----------------------------------------------------------- */
 411
 412 ir_type *get_class_trans_supertype_first(const ir_type *tp)
 413 {
 414         assert_valid_state();
 415         return pset_first(ir_type, get_type_map(tp, d_up));
 416 }
 417
 418 ir_type *get_class_trans_supertype_next(const ir_type *tp)
 419 {
 420         assert_valid_state();
 421         return pset_next(ir_type, get_type_map(tp, d_up));
 422 }
 423
 424 /* - overwrittenby ------------------------------------------------------- */
 425
 426 ir_entity *get_entity_trans_overwrittenby_first(const ir_entity *ent)
 427 {
 428         assert_valid_state();
 429         return pset_first(ir_entity, get_entity_map(ent, d_down));
 430 }
 431
 432 ir_entity *get_entity_trans_overwrittenby_next(const ir_entity *ent)
 433 {
 434         assert_valid_state();
 435         return pset_next(ir_entity, get_entity_map(ent, d_down));
 436 }
 437
 438 /* - overwrites ---------------------------------------------------------- */
 439
 440
 441 ir_entity *get_entity_trans_overwrites_first(const ir_entity *ent)
 442 {
 443         assert_valid_state();
 444         return pset_first(ir_entity, get_entity_map(ent, d_up));
 445 }
 446
 447 ir_entity *get_entity_trans_overwrites_next(const ir_entity *ent)
 448 {
 449         assert_valid_state();
 450         return pset_next(ir_entity, get_entity_map(ent, d_up));
 451 }
 452
 453
 454 /* ----------------------------------------------------------------------- */
 455 /* Classify pairs of types/entities in the inheritance relations.          */
 456 /* ----------------------------------------------------------------------- */
 457
 458 /** Returns true if low is subclass of high. */
 459 static int check_is_SubClass_of(ir_type *low, ir_type *high)
 460 {
 461         size_t i, n_subtypes;
 462
 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))
 469                         return 1;
 470         }
 471         return 0;
 472 }
 473
 474 int is_SubClass_of(ir_type *low, ir_type *high)
 475 {
 476         assert(is_Class_type(low) && is_Class_type(high));
 477
 478         if (low == high) return 1;
 479
 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;
 483         }
 484         return check_is_SubClass_of(low, high);
 485 }
 486
 487 int is_SubClass_ptr_of(ir_type *low, ir_type *high)
 488 {
 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);
 492         }
 493
 494         if (is_Class_type(low) && is_Class_type(high))
 495                 return is_SubClass_of(low, high);
 496         return 0;
 497 }
 498
 499 int is_overwritten_by(ir_entity *high, ir_entity *low)
 500 {
 501         size_t i, n_overwrittenby;
 502         assert(is_entity(low) && is_entity(high));
 503
 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;
 507         }
 508
 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))
 515                         return 1;
 516         }
 517         return 0;
 518 }
 519
 520 /** Resolve polymorphy in the inheritance relation.
 521  *
 522  * Returns the dynamically referenced entity if the static entity and the
 523  * dynamic type are given.
 524  * Search downwards in overwritten tree.
 525  *
 526  * Need two routines because I want to assert the result.
 527  */
 528 static ir_entity *do_resolve_ent_polymorphy(ir_type *dynamic_class, ir_entity *static_ent)
 529 {
 530         size_t i, n_overwrittenby;
 531
 532         ir_type *owner = get_entity_owner(static_ent);
 533         if (owner == dynamic_class) return static_ent;
 534
 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;
 538
 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);
 543                 if (ent) return ent;
 544         }
 545
 546         // No further specialization of static_ent has been found
 547         return static_ent;
 548 }
 549
 550 ir_entity *resolve_ent_polymorphy(ir_type *dynamic_class, ir_entity *static_ent)
 551 {
 552         ir_entity *res;
 553         assert(static_ent && is_entity(static_ent));
 554
 555         res = do_resolve_ent_polymorphy(dynamic_class, static_ent);
 556         assert(res);
 557
 558         return res;
 559 }