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