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

   1 /**
   2  *
   3  * @file tp_inheritance.c
   4  *
   5  * Project:     libFIRM                                                   <br>
   6  * File name:   ir/tr/tp_inheritance.c                                    <br>
   7  * Purpose:     Utility routines for inheritance representation           <br>
   8  * Author:      Goetz Lindenmaier                                         <br>
   9  * Modified by:                                                           <br>
  10  * Created:                                                               <br>
  11  * Copyright:   (c) 2001-2005 Universität Karlsruhe                       <br>
  12  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE. <br>
  13  * CVS-ID:      $Id$
  14  *
  15  *
  16  *
  17  *  @see  type.h entity.h
  18  */
  19
  20 #include "type.h"
  21 #include "entity.h"
  22 #include "typewalk.h"
  23 #include "irprog_t.h"
  24 #include "pset.h"
  25 #include "set.h"
  26 #include "mangle.h"
  27 //#include ".h"
  28
  29
  30
  31 /* ----------------------------------------------------------------------- */
  32 /* Resolve implicit inheritance.                                           */
  33 /* ----------------------------------------------------------------------- */
  34
  35 ident *default_mangle_inherited_name(entity *super, type *clss) {
  36   return mangle_u(get_type_ident(clss), get_entity_ident(super));
  37 }
  38
  39 /* Replicates all entities in all super classes that are not overwritten
  40    by an entity of this class. */
  41 static void copy_entities_from_superclass(type *clss, void *env)
  42 {
  43   int i, j, k, l;
  44   int overwritten;
  45   type *super, *inhenttype;
  46   entity *inhent, *thisent;
  47   mangle_inherited_name_func *mfunc = (mangle_inherited_name_func *)env;
  48
  49   for(i = 0; i < get_class_n_supertypes(clss); i++) {
  50     super = get_class_supertype(clss, i);
  51     assert(is_Class_type(super) && "not a class");
  52     for(j = 0; j < get_class_n_members(super); j++) {
  53       inhent = get_class_member(super, j);
  54       inhenttype = get_entity_type(inhent);
  55       /* check whether inhent is already overwritten */
  56       overwritten = 0;
  57       for (k = 0; (k < get_class_n_members(clss)) && (overwritten == 0); k++) {
  58         thisent = get_class_member(clss, k);
  59         for(l = 0; l < get_entity_n_overwrites(thisent); l++) {
  60           if(inhent == get_entity_overwrites(thisent, l)) {
  61             /* overwritten - do not copy */
  62             overwritten = 1;
  63             break;
  64           }
  65         }
  66       }
  67       /* Inherit entity */
  68       if (!overwritten) {
  69         thisent = copy_entity_own(inhent, clss);
  70         add_entity_overwrites(thisent, inhent);
  71         set_entity_peculiarity(thisent, peculiarity_inherited);
  72         set_entity_ld_ident(thisent, mfunc(inhent, clss));
  73         if (get_entity_variability(inhent) == variability_constant) {
  74           assert(is_atomic_entity(inhent) &&  /* @@@ */
  75                  "Inheritance of constant, compound entities not implemented");
  76           set_entity_variability(thisent, variability_constant);
  77           set_atomic_ent_value(thisent, get_atomic_ent_value(inhent));
  78         }
  79       }
  80     }
  81   }
  82 }
  83
  84 /* Resolve implicit inheritance.
  85  *
  86  *  Resolves the implicit inheritance supplied by firm.
  87  */
  88 void resolve_inheritance(mangle_inherited_name_func *mfunc) {
  89   if (!mfunc)
  90     mfunc = default_mangle_inherited_name;
  91   class_walk_super2sub(copy_entities_from_superclass, NULL, (void *)mfunc);
  92 }
  93
  94
  95 /* ----------------------------------------------------------------------- */
  96 /* The transitive closure of the subclass/superclass and                   */
  97 /* overwrites/overwrittenby relation.                                      */
  98 /*                                                                         */
  99 /* A walk over the ir (O(#types+#entities)) computes the transitive        */
 100 /* closure.  Adding a new type/entity or changing the basic relations in   */
 101 /* some other way invalidates the transitive closure, i.e., it is not      */
 102 /* updated by the basic functions.                                         */
 103 /*                                                                         */
 104 /* All functions are named as their counterparts for the basic relations,  */
 105 /* adding the infix 'trans_'.                                              */
 106 /* ----------------------------------------------------------------------- */
 107
 108 void                        set_irp_inh_transitive_closure_state(inh_transitive_closure_state s) {
 109   irp->inh_trans_closure_state = s;
 110 }
 111 void                        invalidate_irp_inh_transitive_closure_state(void) {
 112   if (irp->inh_trans_closure_state == inh_transitive_closure_valid)
 113     irp->inh_trans_closure_state = inh_transitive_closure_invalid;
 114 }
 115 inh_transitive_closure_state get_irp_inh_transitive_closure_state(void) {
 116   return irp->inh_trans_closure_state;
 117 }
 118
 119 static void assert_valid_state(void) {
 120   assert(irp->inh_trans_closure_state == inh_transitive_closure_valid ||
 121          irp->inh_trans_closure_state == inh_transitive_closure_invalid);
 122 }
 123
 124 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
 125 /* There is a set that extends each entity/type with two new               */
 126 /* fields:  one for the upwards directed relation: 'up' (supertype,        */
 127 /* overwrites) and one for the downwards directed relation: 'down' (sub-   */
 128 /* type, overwrittenby.  These fields contain psets (and maybe later       */
 129 /* arrays) listing all subtypes...                                         */
 130 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
 131
 132 typedef struct {
 133   firm_kind *kind;   /* An entity or type. */
 134   pset *up;
 135   pset *down;
 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 static int tr_inh_trans_cmp(const void *e1, const void *e2, size_t size) {
 142   tr_inh_trans_tp *ef1 = (tr_inh_trans_tp *)e1;
 143   tr_inh_trans_tp *ef2 = (tr_inh_trans_tp *)e2;
 144   return (ef1->kind != ef2->kind);
 145 }
 146
 147 static INLINE unsigned int tr_inh_trans_hash(void *e) {
 148   void *v = (void *) ((tr_inh_trans_tp *)e)->kind;
 149   return HASH_PTR(v);
 150 }
 151
 152 typedef enum {
 153   d_up,
 154   d_down,
 155 } dir;
 156
 157 /* This always completes successfully. */
 158 static tr_inh_trans_tp* get_firm_kind_entry(firm_kind *k) {
 159   tr_inh_trans_tp a, *found;
 160   a.kind = k;
 161
 162   if (!tr_inh_trans_set) tr_inh_trans_set = new_set(tr_inh_trans_cmp, 128);
 163
 164   found = set_find(tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
 165   if (!found) {
 166     a.up   = pset_new_ptr(16);
 167     a.down = pset_new_ptr(16);
 168     found = set_insert(tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
 169   }
 170   return found;
 171 }
 172
 173 static pset *get_entity_map(entity *ent, dir d) {
 174   assert(is_entity(ent));
 175   tr_inh_trans_tp *found = get_firm_kind_entry((firm_kind *)ent);
 176   if (d == d_up) return found->up;
 177   else           return found->down;
 178 }
 179 /*
 180 static void  add_entity_map(entity *ent, dir d, entity *new) {
 181   assert(is_entity(ent) && is_entity(new));
 182   tr_inh_trans_tp *found = get_firm_kind_entry((firm_kind *)ent);
 183   if (d == d_up) pset_insert_ptr(found->up,   new);
 184   else           pset_insert_ptr(found->down, new);
 185 }
 186 */
 187 static pset *get_type_map(type *tp, dir d) {
 188   assert(is_type(tp));
 189   tr_inh_trans_tp *found = get_firm_kind_entry((firm_kind *)tp);
 190   if (d == d_up) return found->up;
 191   else           return found->down;
 192 }
 193 /*
 194 static void  add_type_map(type *tp, dir d, type *new) {
 195   assert(is_type(tp) && is_type(new));
 196   tr_inh_trans_tp *found = get_firm_kind_entry((firm_kind *)tp);
 197   if (d == d_up) pset_insert_ptr(found->up,   new);
 198   else           pset_insert_ptr(found->down, new);
 199 }
 200 */
 201
 202
 203 /* Walk over all types reachable from tp in the sub/supertype
 204  * retlation and compute the closure for the two downwards directed
 205  * relations.
 206  *
 207  * The walk in the dag formed by the relation is tricky:  We must visit
 208  * all subtypes before visiting the supertypes.  So we first walk down.
 209  * Then we can compute the closure for this type.  Then we walk up.
 210  * As we call ourselves recursive, and walk in both directions, there
 211  * can be cycles.  So we have to make sure, that if we visit a node
 212  * a second time (in a walk up) we do nothing.  For this we increment
 213  * the master visited flag twice.
 214  * If the type is marked with master_flag_visited-1 it is on the stack.
 215  * If it is marked with master_flag_visited it is fully processed.
 216  *
 217  * Well, we still miss some candidates ... */
 218 static void compute_down_closure(type *tp) {
 219   pset *myset, *subset;
 220   int i, n_subtypes, n_members, n_supertypes;
 221   int master_visited = get_master_type_visited();
 222
 223   assert(is_Class_type(tp));
 224
 225   set_type_visited(tp, master_visited-1);
 226
 227   /* Recursive descend. */
 228   n_subtypes = get_class_n_subtypes(tp);
 229   for (i = 0; i < n_subtypes; ++i) {
 230     type *stp = get_class_subtype(tp, i);
 231     if (type_not_visited(stp)) {
 232       assert(get_type_visited(tp) < master_visited-1);
 233       compute_down_closure(stp);
 234     }
 235   }
 236
 237   /* types */
 238   myset = get_type_map(tp, d_down);
 239   for (i = 0; i < n_subtypes; ++i) {
 240     type *stp = get_class_subtype(tp, i);
 241     subset = get_type_map(stp, d_down);
 242     pset_insert_ptr(myset, stp);
 243     pset_insert_pset_ptr(myset, subset);
 244   }
 245
 246   /* entities */
 247   n_members = get_class_n_members(tp);
 248   for (i = 0; i < n_members; ++i) {
 249     entity *mem = get_class_member(tp, i);
 250     int j, n_overwrittenby = get_entity_n_overwrittenby(mem);
 251
 252     myset = get_entity_map(mem, d_down);
 253     for (j = 0; j > n_overwrittenby; ++j) {
 254       entity *ov = get_entity_overwrittenby(mem, j);
 255       subset = get_entity_map(ov, d_down);
 256       pset_insert_pset_ptr(myset, subset);
 257       pset_insert_ptr(myset, ov);
 258     }
 259   }
 260
 261   mark_type_visited(tp);
 262
 263   /* Walk up. */
 264   n_supertypes = get_class_n_supertypes(tp);
 265   for (i = 0; i < n_supertypes; ++i) {
 266     type *stp = get_class_supertype(tp, i);
 267     if (get_type_visited(tp) < master_visited-1) {
 268       compute_down_closure(stp);
 269     }
 270   }
 271 }
 272
 273 static void compute_up_closure(type *tp) {
 274   pset *myset, *subset;
 275   int i, n_subtypes, n_members, n_supertypes;
 276   int master_visited = get_master_type_visited();
 277
 278   assert(is_Class_type(tp));
 279
 280   set_type_visited(tp, master_visited-1);
 281
 282   /* Recursive descend. */
 283   n_supertypes = get_class_n_supertypes(tp);
 284   for (i = 0; i < n_supertypes; ++i) {
 285     type *stp = get_class_supertype(tp, i);
 286     if (type_not_visited(stp)) {
 287       assert(get_type_visited(tp) < get_master_type_visited()-1);
 288       compute_up_closure(stp);
 289     }
 290   }
 291
 292   /* types */
 293   myset = get_type_map(tp, d_up);
 294   for (i = 0; i < n_supertypes; ++i) {
 295     type *stp = get_class_supertype(tp, i);
 296     subset = get_type_map(stp, d_up);
 297     pset_insert_ptr(myset, stp);
 298     pset_insert_pset_ptr(myset, subset);
 299   }
 300
 301   /* entities */
 302   n_members = get_class_n_members(tp);
 303   for (i = 0; i < n_members; ++i) {
 304     entity *mem = get_class_member(tp, i);
 305     int j, n_overwrites = get_entity_n_overwrites(mem);
 306
 307     myset = get_entity_map(mem, d_up);
 308     for (j = 0; j > n_overwrites; ++j) {
 309       entity *ov = get_entity_overwrites(mem, j);
 310       subset = get_entity_map(ov, d_up);
 311       pset_insert_pset_ptr(myset, subset);
 312       pset_insert_ptr(myset, ov);
 313     }
 314   }
 315
 316   mark_type_visited(tp);
 317
 318   /* Walk down. */
 319   n_subtypes = get_class_n_subtypes(tp);
 320   for (i = 0; i < n_subtypes; ++i) {
 321     type *stp = get_class_subtype(tp, i);
 322     if (get_type_visited(tp) < master_visited-1) {
 323       compute_up_closure(stp);
 324     }
 325   }
 326 }
 327
 328 /** Compute the transitive closure of the subclass/superclass and
 329  *  overwrites/overwrittenby relation.
 330  *
 331  *  This function walks over the ir (O(#types+#entities)) to compute the
 332  *  transitive closure.    */
 333 void compute_inh_transitive_closure(void) {
 334   int i, n_types = get_irp_n_types();
 335   free_inh_transitive_closure();
 336
 337   /* The 'down' relation */
 338   inc_master_type_visited();  /* Inc twice: one if on stack, second if values computed. */
 339   inc_master_type_visited();
 340   for (i = 0; i < n_types; ++i) {
 341     type *tp = get_irp_type(i);
 342     if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
 343       assert(get_type_visited(tp) < get_master_type_visited()-1);
 344       int j, n_subtypes = get_class_n_subtypes(tp);
 345       int has_unmarked_subtype = false;
 346       for (j = 0; j < n_subtypes && !has_unmarked_subtype; ++j) {
 347         type *stp = get_class_subtype(tp, j);
 348         if (type_not_visited(stp)) has_unmarked_subtype = true;
 349       }
 350
 351       /* This is a good starting point. */
 352       if (!has_unmarked_subtype)
 353         compute_down_closure(tp);
 354     }
 355   }
 356
 357   /* The 'up' relation */
 358   inc_master_type_visited();
 359   inc_master_type_visited();
 360   for (i = 0; i < n_types; ++i) {
 361     type *tp = get_irp_type(i);
 362     if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
 363       assert(get_type_visited(tp) < get_master_type_visited()-1);
 364       int j, n_supertypes = get_class_n_supertypes(tp);
 365       int has_unmarked_supertype = false;
 366       for (j = 0; j < n_supertypes && !has_unmarked_supertype; ++j) {
 367         type *stp = get_class_supertype(tp, j);
 368         if (type_not_visited(stp)) has_unmarked_supertype = true;
 369       }
 370
 371       /* This is a good starting point. */
 372       if (!has_unmarked_supertype)
 373         compute_up_closure(tp);
 374     }
 375   }
 376
 377   irp->inh_trans_closure_state = inh_transitive_closure_valid;
 378 }
 379
 380 /** Free memory occupied by the transitive closure information. */
 381 void free_inh_transitive_closure(void) {
 382   if (tr_inh_trans_set) {
 383     tr_inh_trans_tp *elt;
 384     for (elt = set_first(tr_inh_trans_set); elt; elt = set_next(tr_inh_trans_set)) {
 385       del_pset(elt->up);
 386       del_pset(elt->down);
 387     }
 388     del_set(tr_inh_trans_set);
 389     tr_inh_trans_set = NULL;
 390   }
 391   irp->inh_trans_closure_state = inh_transitive_closure_none;
 392 }
 393
 394 /* - subtype ------------------------------------------------------------- */
 395
 396 type *get_class_trans_subtype_first(type *tp) {
 397   assert_valid_state();
 398   return pset_first(get_type_map(tp, d_down));
 399 }
 400
 401 type *get_class_trans_subtype_next (type *tp) {
 402   assert_valid_state();
 403   return pset_next(get_type_map(tp, d_down));
 404 }
 405
 406 /* - supertype ----------------------------------------------------------- */
 407
 408 type *get_class_trans_supertype_first(type *tp) {
 409   assert_valid_state();
 410   return pset_first(get_type_map(tp, d_up));
 411 }
 412
 413 type *get_class_trans_supertype_next (type *tp) {
 414   assert_valid_state();
 415   return pset_next(get_type_map(tp, d_up));
 416 }
 417
 418 /* - overwrittenby ------------------------------------------------------- */
 419
 420 entity *get_entity_trans_overwrittenby_first(entity *ent) {
 421   assert_valid_state();
 422   return pset_first(get_entity_map(ent, d_down));
 423 }
 424
 425 entity *get_entity_trans_overwrittenby_next (entity *ent) {
 426   assert_valid_state();
 427   return pset_next(get_entity_map(ent, d_down));
 428 }
 429
 430 /* - overwrites ---------------------------------------------------------- */
 431
 432
 433 /** Iterate over all transitive overwritten entities. */
 434 entity *get_entity_trans_overwrites_first(entity *ent) {
 435   assert_valid_state();
 436   return pset_first(get_entity_map(ent, d_up));
 437 }
 438
 439 entity *get_entity_trans_overwrites_next (entity *ent) {
 440   assert_valid_state();
 441   return pset_next(get_entity_map(ent, d_up));
 442 }
 443
 444
 445
 446
 447
 448 /* ----------------------------------------------------------------------- */
 449 /* Classify pairs of types/entities in the inheritance relations.          */
 450 /* ----------------------------------------------------------------------- */
 451
 452 /* Returns true if low is subclass of high. */
 453 int is_subclass_of(type *low, type *high) {
 454   int i, n_subtypes;
 455   assert(is_Class_type(low) && is_Class_type(high));
 456
 457   if (low == high) return 1;
 458
 459   if (get_irp_inh_transitive_closure_state() == inh_transitive_closure_valid) {
 460     pset *m = get_type_map(high, d_down);
 461     if (pset_find_ptr(m, low)) return 1;
 462     else                        return 0;
 463   }
 464
 465   /* depth first search from high downwards. */
 466   n_subtypes = get_class_n_subtypes(high);
 467   for (i = 0; i < n_subtypes; i++) {
 468     type *stp = get_class_subtype(high, i);
 469     if (low == stp) return 1;
 470     if (is_subclass_of(low, stp))
 471       return 1;
 472   }
 473   return 0;
 474 }
 475
 476 int is_overwritten_by(entity *high, entity *low) {
 477   int i, n_overwrittenby;
 478   assert(is_entity(low) && is_entity(high));
 479
 480   if (get_irp_inh_transitive_closure_state() == inh_transitive_closure_valid) {
 481     pset *m = get_entity_map(high, d_down);
 482     if (pset_find_ptr(m, low)) return 1;
 483     else                       return 0;
 484   }
 485
 486   /* depth first search from high downwards. */
 487   n_overwrittenby = get_entity_n_overwrittenby(high);
 488   for (i = 0; i < n_overwrittenby; i++) {
 489     entity *ov = get_entity_overwrittenby(high, i);
 490     if (low == ov) return 1;
 491     if (is_overwritten_by(low, ov))
 492       return 1;
 493   }
 494   return 0;
 495 }
 496
 497
 498 /* Need two routines because I want to assert the result. */
 499 static entity *resolve_ent_polymorphy2 (type *dynamic_class, entity *static_ent) {
 500   int i, n_overwrittenby;
 501   entity *res = NULL;
 502
 503   if (get_entity_owner(static_ent) == dynamic_class) return static_ent;
 504
 505   n_overwrittenby = get_entity_n_overwrittenby(static_ent);
 506   for (i = 0; i < n_overwrittenby; ++i) {
 507     res = resolve_ent_polymorphy2(dynamic_class, get_entity_overwrittenby(static_ent, i));
 508     if (res)
 509       break;
 510   }
 511
 512   return res;
 513 }
 514
 515 /* Resolve polymorphy in the inheritance relation.
 516  *
 517  * Returns the dynamically referenced entity if the static entity and the
 518  * dynamic type are given.
 519  * Search downwards in overwritten tree. */
 520 entity *resolve_ent_polymorphy(type *dynamic_class, entity *static_ent) {
 521   entity *res;
 522   assert(static_ent && is_entity(static_ent));
 523
 524   res = resolve_ent_polymorphy2(dynamic_class, static_ent);
 525   assert(res);
 526
 527   return res;
 528 }