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

   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
  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. */
  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
  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
 115 void                        set_irp_inh_transitive_closure_state(inh_transitive_closure_state s)
 116 {
 117         irp->inh_trans_closure_state = s;
 118 }
 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 }
 124 inh_transitive_closure_state get_irp_inh_transitive_closure_state(void)
 125 {
 126         return irp->inh_trans_closure_state;
 127 }
 128
 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  */
 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  */
 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. */
 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
 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
 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 ... */
 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
 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
 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
 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
 411 ir_type *get_class_trans_subtype_first(const ir_type *tp)
 412 {
 413         assert_valid_state();
 414         return (ir_type*)pset_first(get_type_map(tp, d_down));
 415 }
 416
 417 ir_type *get_class_trans_subtype_next(const ir_type *tp)
 418 {
 419         assert_valid_state();
 420         return (ir_type*)pset_next(get_type_map(tp, d_down));
 421 }
 422
 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
 431 ir_type *get_class_trans_supertype_first(const ir_type *tp)
 432 {
 433         assert_valid_state();
 434         return (ir_type*)pset_first(get_type_map(tp, d_up));
 435 }
 436
 437 ir_type *get_class_trans_supertype_next(const ir_type *tp)
 438 {
 439         assert_valid_state();
 440         return (ir_type*)pset_next(get_type_map(tp, d_up));
 441 }
 442
 443 /* - overwrittenby ------------------------------------------------------- */
 444
 445 ir_entity *get_entity_trans_overwrittenby_first(const ir_entity *ent)
 446 {
 447         assert_valid_state();
 448         return (ir_entity*)pset_first(get_entity_map(ent, d_down));
 449 }
 450
 451 ir_entity *get_entity_trans_overwrittenby_next(const ir_entity *ent)
 452 {
 453         assert_valid_state();
 454         return (ir_entity*)pset_next(get_entity_map(ent, d_down));
 455 }
 456
 457 /* - overwrites ---------------------------------------------------------- */
 458
 459
 460 ir_entity *get_entity_trans_overwrites_first(const ir_entity *ent)
 461 {
 462         assert_valid_state();
 463         return (ir_entity*)pset_first(get_entity_map(ent, d_up));
 464 }
 465
 466 ir_entity *get_entity_trans_overwrites_next(const ir_entity *ent)
 467 {
 468         assert_valid_state();
 469         return (ir_entity*)pset_next(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. */
 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
 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
 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
 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  */
 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
 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
 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
 595 ir_class_cast_state get_irg_class_cast_state(const ir_graph *irg)
 596 {
 597         return irg->class_cast_state;
 598 }
 599
 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
 610 ir_class_cast_state get_irp_class_cast_state(void)
 611 {
 612         return irp->class_cast_state;
 613 }