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 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  38
  39 /* ----------------------------------------------------------------------- */
  40 /* Resolve implicit inheritance.                                           */
  41 /* ----------------------------------------------------------------------- */
  42
  43 ident *default_mangle_inherited_name(const ir_entity *super, const ir_type *clss)
  44 {
  45         return id_mangle_u(new_id_from_str("inh"), id_mangle_u(get_class_ident(clss), get_entity_ident(super)));
  46 }
  47
  48 /** Replicates all entities in all super classes that are not overwritten
  49     by an entity of this class. */
  50 static void copy_entities_from_superclass(ir_type *clss, void *env)
  51 {
  52         size_t i;
  53         size_t j;
  54         size_t k;
  55         size_t l;
  56         int overwritten;
  57         ir_type *super;
  58         ir_entity *inhent, *thisent;
  59         mangle_inherited_name_func *mfunc = *(mangle_inherited_name_func **)env;
  60
  61         for (i = 0; i < get_class_n_supertypes(clss); i++) {
  62                 super = get_class_supertype(clss, i);
  63                 assert(is_Class_type(super) && "not a class");
  64                 for (j = 0; j < get_class_n_members(super); j++) {
  65                         inhent = get_class_member(super, j);
  66                         /* check whether inhent is already overwritten */
  67                         overwritten = 0;
  68                         for (k = 0; (k < get_class_n_members(clss)) && (overwritten == 0); k++) {
  69                                 thisent = get_class_member(clss, k);
  70                                 for (l = 0; l < get_entity_n_overwrites(thisent); l++) {
  71                                         if (inhent == get_entity_overwrites(thisent, l)) {
  72                                                 /* overwritten - do not copy */
  73                                                 overwritten = 1;
  74                                                 break;
  75                                         }
  76                                 }
  77                         }
  78                         /* Inherit entity */
  79                         if (!overwritten) {
  80                                 thisent = copy_entity_own(inhent, clss);
  81                                 add_entity_overwrites(thisent, inhent);
  82                                 if (get_entity_peculiarity(inhent) == peculiarity_existent)
  83                                         set_entity_peculiarity(thisent, peculiarity_inherited);
  84                                 set_entity_ld_ident(thisent, mfunc(inhent, clss));
  85                                 if (get_entity_linkage(inhent) & IR_LINKAGE_CONSTANT) {
  86                                         assert(is_atomic_entity(inhent) &&  /* @@@ */
  87                                                 "Inheritance of constant, compound entities not implemented");
  88                                         add_entity_linkage(thisent, IR_LINKAGE_CONSTANT);
  89                                         set_atomic_ent_value(thisent, get_atomic_ent_value(inhent));
  90                                 }
  91                         }
  92                 }
  93         }
  94 }
  95
  96 /* Resolve implicit inheritance.
  97  *
  98  *  Resolves the implicit inheritance supplied by firm.
  99  */
 100 void resolve_inheritance(mangle_inherited_name_func *mfunc)
 101 {
 102         if (!mfunc)
 103                 mfunc = default_mangle_inherited_name;
 104         class_walk_super2sub(copy_entities_from_superclass, NULL, (void *)&mfunc);
 105 }
 106
 107
 108 /* ----------------------------------------------------------------------- */
 109 /* The transitive closure of the subclass/superclass and                   */
 110 /* overwrites/overwrittenby relation.                                      */
 111 /*                                                                         */
 112 /* A walk over the ir (O(#types+#entities)) computes the transitive        */
 113 /* closure.  Adding a new type/entity or changing the basic relations in   */
 114 /* some other way invalidates the transitive closure, i.e., it is not      */
 115 /* updated by the basic functions.                                         */
 116 /*                                                                         */
 117 /* All functions are named as their counterparts for the basic relations,  */
 118 /* adding the infix 'trans_'.                                              */
 119 /* ----------------------------------------------------------------------- */
 120
 121 void                        set_irp_inh_transitive_closure_state(inh_transitive_closure_state s)
 122 {
 123         irp->inh_trans_closure_state = s;
 124 }
 125 void                        invalidate_irp_inh_transitive_closure_state(void)
 126 {
 127         if (irp->inh_trans_closure_state == inh_transitive_closure_valid)
 128                 irp->inh_trans_closure_state = inh_transitive_closure_invalid;
 129 }
 130 inh_transitive_closure_state get_irp_inh_transitive_closure_state(void)
 131 {
 132         return irp->inh_trans_closure_state;
 133 }
 134
 135 static void assert_valid_state(void)
 136 {
 137         assert(irp->inh_trans_closure_state == inh_transitive_closure_valid ||
 138                irp->inh_trans_closure_state == inh_transitive_closure_invalid);
 139 }
 140
 141 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
 142 /* There is a set that extends each entity/type with two new               */
 143 /* fields:  one for the upwards directed relation: 'up' (supertype,        */
 144 /* overwrites) and one for the downwards directed relation: 'down' (sub-   */
 145 /* type, overwrittenby.  These fields contain psets (and maybe later       */
 146 /* arrays) listing all subtypes...                                         */
 147 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
 148
 149 typedef enum {
 150         d_up   = 0,
 151         d_down = 1,
 152 } dir;
 153
 154 typedef struct {
 155         const firm_kind *kind;   /**< An entity or type. */
 156         pset *directions[2];
 157 } tr_inh_trans_tp;
 158
 159 /* We use this set for all types and entities.  */
 160 static set *tr_inh_trans_set = NULL;
 161
 162 /**
 163  * Compare two tr_inh_trans_tp entries.
 164  */
 165 static int tr_inh_trans_cmp(const void *e1, const void *e2, size_t size)
 166 {
 167         const tr_inh_trans_tp *ef1 = (const tr_inh_trans_tp*)e1;
 168         const tr_inh_trans_tp *ef2 = (const tr_inh_trans_tp*)e2;
 169         (void) size;
 170
 171         return ef1->kind != ef2->kind;
 172 }
 173
 174 /**
 175  * calculate the hash value of an tr_inh_trans_tp
 176  */
 177 static inline unsigned int tr_inh_trans_hash(const tr_inh_trans_tp *v)
 178 {
 179         return HASH_PTR(v->kind);
 180 }
 181
 182 /* This always completes successfully. */
 183 static tr_inh_trans_tp *get_firm_kind_entry(const firm_kind *k)
 184 {
 185         tr_inh_trans_tp a, *found;
 186         a.kind = k;
 187
 188         if (!tr_inh_trans_set) tr_inh_trans_set = new_set(tr_inh_trans_cmp, 128);
 189
 190         found = (tr_inh_trans_tp*)set_find(tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
 191         if (!found) {
 192                 a.directions[d_up]   = pset_new_ptr(16);
 193                 a.directions[d_down] = pset_new_ptr(16);
 194                 found = (tr_inh_trans_tp*)set_insert(tr_inh_trans_set, &a, sizeof(a), tr_inh_trans_hash(&a));
 195         }
 196         return found;
 197 }
 198
 199 static pset *get_entity_map(const ir_entity *ent, dir d)
 200 {
 201         tr_inh_trans_tp *found;
 202
 203         assert(is_entity(ent));
 204         found = get_firm_kind_entry((const firm_kind *)ent);
 205         return found->directions[d];
 206 }
 207
 208 static pset *get_type_map(const ir_type *tp, dir d)
 209 {
 210         tr_inh_trans_tp *found;
 211
 212         assert(is_type(tp));
 213         found = get_firm_kind_entry((const firm_kind *)tp);
 214         return found->directions[d];
 215 }
 216
 217
 218 /**
 219  * Walk over all types reachable from tp in the sub/supertype
 220  * relation and compute the closure for the two downwards directed
 221  * relations.
 222  *
 223  * The walk in the dag formed by the relation is tricky:  We must visit
 224  * all subtypes before visiting the supertypes.  So we first walk down.
 225  * Then we can compute the closure for this type.  Then we walk up.
 226  * As we call ourselves recursive, and walk in both directions, there
 227  * can be cycles.  So we have to make sure, that if we visit a node
 228  * a second time (in a walk up) we do nothing.  For this we increment
 229  * the master visited flag twice.
 230  * If the type is marked with master_flag_visited-1 it is on the stack.
 231  * If it is marked with master_flag_visited it is fully processed.
 232  *
 233  * Well, we still miss some candidates ... */
 234 static void compute_down_closure(ir_type *tp)
 235 {
 236         pset *myset, *subset;
 237         size_t i, n_subtypes, n_members, n_supertypes;
 238         ir_visited_t master_visited = get_master_type_visited();
 239
 240         assert(is_Class_type(tp));
 241
 242         set_type_visited(tp, master_visited-1);
 243
 244         /* Recursive descend. */
 245         n_subtypes = get_class_n_subtypes(tp);
 246         for (i = 0; i < n_subtypes; ++i) {
 247                 ir_type *stp = get_class_subtype(tp, i);
 248                 if (get_type_visited(stp) < master_visited-1) {
 249                         compute_down_closure(stp);
 250                 }
 251         }
 252
 253         /* types */
 254         myset = get_type_map(tp, d_down);
 255         for (i = 0; i < n_subtypes; ++i) {
 256                 ir_type *stp = get_class_subtype(tp, i);
 257                 subset = get_type_map(stp, d_down);
 258                 pset_insert_ptr(myset, stp);
 259                 pset_insert_pset_ptr(myset, subset);
 260         }
 261
 262         /* entities */
 263         n_members = get_class_n_members(tp);
 264         for (i = 0; i < n_members; ++i) {
 265                 ir_entity *mem = get_class_member(tp, i);
 266                 size_t j, n_overwrittenby = get_entity_n_overwrittenby(mem);
 267
 268                 myset = get_entity_map(mem, d_down);
 269                 for (j = 0; j < n_overwrittenby; ++j) {
 270                         ir_entity *ov = get_entity_overwrittenby(mem, j);
 271                         subset = get_entity_map(ov, d_down);
 272                         pset_insert_ptr(myset, ov);
 273                         pset_insert_pset_ptr(myset, subset);
 274                 }
 275         }
 276
 277         mark_type_visited(tp);
 278
 279         /* Walk up. */
 280         n_supertypes = get_class_n_supertypes(tp);
 281         for (i = 0; i < n_supertypes; ++i) {
 282                 ir_type *stp = get_class_supertype(tp, i);
 283                 if (get_type_visited(stp) < master_visited-1) {
 284                         compute_down_closure(stp);
 285                 }
 286         }
 287 }
 288
 289 static void compute_up_closure(ir_type *tp)
 290 {
 291         pset *myset, *subset;
 292         size_t i, n_subtypes, n_members, n_supertypes;
 293         ir_visited_t master_visited = get_master_type_visited();
 294
 295         assert(is_Class_type(tp));
 296
 297         set_type_visited(tp, master_visited-1);
 298
 299         /* Recursive descend. */
 300         n_supertypes = get_class_n_supertypes(tp);
 301         for (i = 0; i < n_supertypes; ++i) {
 302                 ir_type *stp = get_class_supertype(tp, i);
 303                 if (get_type_visited(stp) < get_master_type_visited()-1) {
 304                         compute_up_closure(stp);
 305                 }
 306         }
 307
 308         /* types */
 309         myset = get_type_map(tp, d_up);
 310         for (i = 0; i < n_supertypes; ++i) {
 311                 ir_type *stp = get_class_supertype(tp, i);
 312                 subset = get_type_map(stp, d_up);
 313                 pset_insert_ptr(myset, stp);
 314                 pset_insert_pset_ptr(myset, subset);
 315         }
 316
 317         /* entities */
 318         n_members = get_class_n_members(tp);
 319         for (i = 0; i < n_members; ++i) {
 320                 ir_entity *mem = get_class_member(tp, i);
 321                 size_t j, n_overwrites = get_entity_n_overwrites(mem);
 322
 323                 myset = get_entity_map(mem, d_up);
 324                 for (j = 0; j < n_overwrites; ++j) {
 325                         ir_entity *ov = get_entity_overwrites(mem, j);
 326                         subset = get_entity_map(ov, d_up);
 327                         pset_insert_pset_ptr(myset, subset);
 328                         pset_insert_ptr(myset, ov);
 329                 }
 330         }
 331
 332         mark_type_visited(tp);
 333
 334         /* Walk down. */
 335         n_subtypes = get_class_n_subtypes(tp);
 336         for (i = 0; i < n_subtypes; ++i) {
 337                 ir_type *stp = get_class_subtype(tp, i);
 338                 if (get_type_visited(stp) < master_visited-1) {
 339                         compute_up_closure(stp);
 340                 }
 341         }
 342 }
 343
 344 /** Compute the transitive closure of the subclass/superclass and
 345  *  overwrites/overwrittenby relation.
 346  *
 347  *  This function walks over the ir (O(#types+#entities)) to compute the
 348  *  transitive closure.    */
 349 void compute_inh_transitive_closure(void)
 350 {
 351         size_t i, n_types = get_irp_n_types();
 352         free_inh_transitive_closure();
 353
 354         /* The 'down' relation */
 355         irp_reserve_resources(irp, IRP_RESOURCE_TYPE_VISITED);
 356         inc_master_type_visited();  /* Inc twice: one if on stack, second if values computed. */
 357         inc_master_type_visited();
 358         for (i = 0; i < n_types; ++i) {
 359                 ir_type *tp = get_irp_type(i);
 360                 if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
 361                         size_t j, n_subtypes = get_class_n_subtypes(tp);
 362                         int has_unmarked_subtype = 0;
 363
 364                         assert(get_type_visited(tp) < get_master_type_visited()-1);
 365                         for (j = 0; j < n_subtypes; ++j) {
 366                                 ir_type *stp = get_class_subtype(tp, j);
 367                                 if (type_not_visited(stp)) {
 368                                         has_unmarked_subtype = 1;
 369                                         break;
 370                                 }
 371                         }
 372
 373                         /* This is a good starting point. */
 374                         if (!has_unmarked_subtype)
 375                                 compute_down_closure(tp);
 376                 }
 377         }
 378
 379         /* The 'up' relation */
 380         inc_master_type_visited();
 381         inc_master_type_visited();
 382         for (i = 0; i < n_types; ++i) {
 383                 ir_type *tp = get_irp_type(i);
 384                 if (is_Class_type(tp) && type_not_visited(tp)) { /* For others there is nothing to accumulate. */
 385                         size_t j, n_supertypes = get_class_n_supertypes(tp);
 386                         int has_unmarked_supertype = 0;
 387
 388                         assert(get_type_visited(tp) < get_master_type_visited()-1);
 389                         for (j = 0; j < n_supertypes; ++j) {
 390                                 ir_type *stp = get_class_supertype(tp, j);
 391                                 if (type_not_visited(stp)) {
 392                                         has_unmarked_supertype = 1;
 393                                         break;
 394                                 }
 395                         }
 396
 397                         /* This is a good starting point. */
 398                         if (!has_unmarked_supertype)
 399                                 compute_up_closure(tp);
 400                 }
 401         }
 402
 403         irp->inh_trans_closure_state = inh_transitive_closure_valid;
 404         irp_free_resources(irp, IRP_RESOURCE_TYPE_VISITED);
 405 }
 406
 407 /** Free memory occupied by the transitive closure information. */
 408 void free_inh_transitive_closure(void)
 409 {
 410         if (tr_inh_trans_set) {
 411                 tr_inh_trans_tp *elt;
 412                 for (elt = (tr_inh_trans_tp*)set_first(tr_inh_trans_set); elt != NULL;
 413                      elt = (tr_inh_trans_tp*)set_next(tr_inh_trans_set)) {
 414                         del_pset(elt->directions[d_up]);
 415                         del_pset(elt->directions[d_down]);
 416                 }
 417                 del_set(tr_inh_trans_set);
 418                 tr_inh_trans_set = NULL;
 419         }
 420         irp->inh_trans_closure_state = inh_transitive_closure_none;
 421 }
 422
 423 /* - subtype ------------------------------------------------------------- */
 424
 425 ir_type *get_class_trans_subtype_first(const ir_type *tp)
 426 {
 427         assert_valid_state();
 428         return (ir_type*)pset_first(get_type_map(tp, d_down));
 429 }
 430
 431 ir_type *get_class_trans_subtype_next(const ir_type *tp)
 432 {
 433         assert_valid_state();
 434         return (ir_type*)pset_next(get_type_map(tp, d_down));
 435 }
 436
 437 int is_class_trans_subtype(const ir_type *tp, const ir_type *subtp)
 438 {
 439         assert_valid_state();
 440         return (pset_find_ptr(get_type_map(tp, d_down), subtp) != NULL);
 441 }
 442
 443 /* - supertype ----------------------------------------------------------- */
 444
 445 ir_type *get_class_trans_supertype_first(const ir_type *tp)
 446 {
 447         assert_valid_state();
 448         return (ir_type*)pset_first(get_type_map(tp, d_up));
 449 }
 450
 451 ir_type *get_class_trans_supertype_next(const ir_type *tp)
 452 {
 453         assert_valid_state();
 454         return (ir_type*)pset_next(get_type_map(tp, d_up));
 455 }
 456
 457 /* - overwrittenby ------------------------------------------------------- */
 458
 459 ir_entity *get_entity_trans_overwrittenby_first(const ir_entity *ent)
 460 {
 461         assert_valid_state();
 462         return (ir_entity*)pset_first(get_entity_map(ent, d_down));
 463 }
 464
 465 ir_entity *get_entity_trans_overwrittenby_next(const ir_entity *ent)
 466 {
 467         assert_valid_state();
 468         return (ir_entity*)pset_next(get_entity_map(ent, d_down));
 469 }
 470
 471 /* - overwrites ---------------------------------------------------------- */
 472
 473
 474 /** Iterate over all transitive overwritten entities. */
 475 ir_entity *get_entity_trans_overwrites_first(const ir_entity *ent)
 476 {
 477         assert_valid_state();
 478         return (ir_entity*)pset_first(get_entity_map(ent, d_up));
 479 }
 480
 481 ir_entity *get_entity_trans_overwrites_next(const ir_entity *ent)
 482 {
 483         assert_valid_state();
 484         return (ir_entity*)pset_next(get_entity_map(ent, d_up));
 485 }
 486
 487
 488 /* ----------------------------------------------------------------------- */
 489 /* Classify pairs of types/entities in the inheritance relations.          */
 490 /* ----------------------------------------------------------------------- */
 491
 492 /** Returns true if low is subclass of high. */
 493 static int check_is_SubClass_of(ir_type *low, ir_type *high)
 494 {
 495         size_t i, n_subtypes;
 496
 497         /* depth first search from high downwards. */
 498         n_subtypes = get_class_n_subtypes(high);
 499         for (i = 0; i < n_subtypes; i++) {
 500                 ir_type *stp = get_class_subtype(high, i);
 501                 if (low == stp) return 1;
 502                 if (is_SubClass_of(low, stp))
 503                         return 1;
 504         }
 505         return 0;
 506 }
 507
 508 /* Returns true if low is subclass of high. */
 509 int is_SubClass_of(ir_type *low, ir_type *high)
 510 {
 511         assert(is_Class_type(low) && is_Class_type(high));
 512
 513         if (low == high) return 1;
 514
 515         if (get_irp_inh_transitive_closure_state() == inh_transitive_closure_valid) {
 516                 pset *m = get_type_map(high, d_down);
 517                 return pset_find_ptr(m, low) ? 1 : 0;
 518         }
 519         return check_is_SubClass_of(low, high);
 520 }
 521
 522
 523 /* Subclass check for pointers to classes.
 524  *
 525  *  Dereferences at both types the same amount of pointer types (as
 526  *  many as possible).  If the remaining types are both class types
 527  *  and subclasses, returns true, else false.  Can also be called with
 528  *  two class types.  */
 529 int is_SubClass_ptr_of(ir_type *low, ir_type *high)
 530 {
 531         while (is_Pointer_type(low) && is_Pointer_type(high)) {
 532                 low  = get_pointer_points_to_type(low);
 533                 high = get_pointer_points_to_type(high);
 534         }
 535
 536         if (is_Class_type(low) && is_Class_type(high))
 537                 return is_SubClass_of(low, high);
 538         return 0;
 539 }
 540
 541 int is_overwritten_by(ir_entity *high, ir_entity *low)
 542 {
 543         size_t i, n_overwrittenby;
 544         assert(is_entity(low) && is_entity(high));
 545
 546         if (get_irp_inh_transitive_closure_state() == inh_transitive_closure_valid) {
 547                 pset *m = get_entity_map(high, d_down);
 548                 return pset_find_ptr(m, low) ? 1 : 0;
 549         }
 550
 551         /* depth first search from high downwards. */
 552         n_overwrittenby = get_entity_n_overwrittenby(high);
 553         for (i = 0; i < n_overwrittenby; i++) {
 554                 ir_entity *ov = get_entity_overwrittenby(high, i);
 555                 if (low == ov) return 1;
 556                 if (is_overwritten_by(low, ov))
 557                         return 1;
 558         }
 559         return 0;
 560 }
 561
 562 /** Resolve polymorphy in the inheritance relation.
 563  *
 564  * Returns the dynamically referenced entity if the static entity and the
 565  * dynamic type are given.
 566  * Search downwards in overwritten tree.
 567  *
 568  * Need two routines because I want to assert the result.
 569  */
 570 static ir_entity *do_resolve_ent_polymorphy(ir_type *dynamic_class, ir_entity *static_ent)
 571 {
 572         size_t i, n_overwrittenby;
 573
 574         ir_type *owner = get_entity_owner(static_ent);
 575         if (owner == dynamic_class) return static_ent;
 576
 577         // if the owner of the static_ent already is more special than the dynamic
 578         // type to check against - stop here.
 579         if (! is_SubClass_of(dynamic_class, owner)) return NULL;
 580
 581         n_overwrittenby = get_entity_n_overwrittenby(static_ent);
 582         for (i = 0; i < n_overwrittenby; ++i) {
 583                 ir_entity *ent = get_entity_overwrittenby(static_ent, i);
 584                 ent = do_resolve_ent_polymorphy(dynamic_class, ent);
 585                 if (ent) return ent;
 586         }
 587
 588         // No further specialization of static_ent has been found
 589         return static_ent;
 590 }
 591
 592 /* Resolve polymorphy in the inheritance relation.
 593  *
 594  * Returns the dynamically referenced entity if the static entity and the
 595  * dynamic type are given.
 596  * Search downwards in overwritten tree.
 597  */
 598 ir_entity *resolve_ent_polymorphy(ir_type *dynamic_class, ir_entity *static_ent)
 599 {
 600         ir_entity *res;
 601         assert(static_ent && is_entity(static_ent));
 602
 603         res = do_resolve_ent_polymorphy(dynamic_class, static_ent);
 604         assert(res);
 605
 606         return res;
 607 }
 608
 609
 610
 611 /* ----------------------------------------------------------------------- */
 612 /* Class cast state handling.                                              */
 613 /* ----------------------------------------------------------------------- */
 614
 615 /* - State handling. ----------------------------------------- */
 616
 617 void set_irg_class_cast_state(ir_graph *irg, ir_class_cast_state s)
 618 {
 619         if (get_irp_class_cast_state() > s)
 620                 set_irp_class_cast_state(s);
 621         irg->class_cast_state = s;
 622 }
 623
 624 ir_class_cast_state get_irg_class_cast_state(const ir_graph *irg)
 625 {
 626         return irg->class_cast_state;
 627 }
 628
 629 void set_irp_class_cast_state(ir_class_cast_state s)
 630 {
 631 #ifndef NDEBUG
 632         size_t i, n;
 633         for (i = 0, n = get_irp_n_irgs(); i < n; ++i)
 634                 assert(get_irg_class_cast_state(get_irp_irg(i)) >= s);
 635 #endif
 636         irp->class_cast_state = s;
 637 }
 638
 639 ir_class_cast_state get_irp_class_cast_state(void)
 640 {
 641         return irp->class_cast_state;
 642 }
 643
 644 const char *get_class_cast_state_string(ir_class_cast_state s)
 645 {
 646 #define X(a)    case a: return #a
 647         switch (s) {
 648         X(ir_class_casts_any);
 649         X(ir_class_casts_transitive);
 650         X(ir_class_casts_normalized);
 651         X(ir_class_casts_state_max);
 652         default: return "invalid class cast state";
 653         }
 654 #undef X
 655 }
 656
 657 /* - State verification. ------------------------------------- */
 658
 659 typedef struct ccs_env {
 660         ir_class_cast_state expected_state;
 661         ir_class_cast_state worst_situation;
 662 } ccs_env;
 663
 664 /**
 665  * Walker: check Casts.
 666  */
 667 static void verify_irn_class_cast_state(ir_node *n, void *env)
 668 {
 669         ccs_env             *ccs = (ccs_env *)env;
 670         ir_class_cast_state this_state = ir_class_casts_any;
 671         ir_type             *fromtype, *totype;
 672
 673         if (!is_Cast(n)) return;
 674
 675         fromtype = get_irn_typeinfo_type(get_Cast_op(n));
 676         totype   = get_Cast_type(n);
 677
 678         while (is_Pointer_type(totype) && is_Pointer_type(fromtype)) {
 679                 totype   = get_pointer_points_to_type(totype);
 680                 fromtype = get_pointer_points_to_type(fromtype);
 681         }
 682
 683         if (!is_Class_type(totype)) return;
 684
 685         if (is_SubClass_of(totype, fromtype) ||
 686                 is_SubClass_of(fromtype, totype)) {
 687                 this_state = ir_class_casts_transitive;
 688                 if ((get_class_supertype_index(totype, fromtype) != (size_t)-1) ||
 689                     (get_class_supertype_index(fromtype, totype) != (size_t)-1) ||
 690                     fromtype == totype) {
 691                         this_state = ir_class_casts_normalized;
 692                 }
 693         }
 694
 695         if (!(this_state >= ccs->expected_state)) {
 696                 ir_printf("  Node is %+F\n", n);
 697                 ir_printf("    totype   %+F\n", totype);
 698                 ir_printf("    fromtype %+F\n", fromtype);
 699                 ir_printf("    this_state: %s, exp. state: %s\n",
 700                         get_class_cast_state_string(this_state),
 701                         get_class_cast_state_string(ccs->expected_state));
 702                 assert(this_state >= ccs->expected_state &&
 703                         "invalid state class cast state setting in graph");
 704         }
 705
 706         if (this_state < ccs->worst_situation)
 707                 ccs->worst_situation = this_state;
 708 }
 709
 710 /** Verify that the graph meets requirements of state set. */
 711 void verify_irg_class_cast_state(ir_graph *irg)
 712 {
 713         ccs_env env;
 714
 715         FIRM_DBG_REGISTER(dbg, "firm.tr.inheritance");
 716
 717         env.expected_state  = get_irg_class_cast_state(irg);
 718         env.worst_situation = ir_class_casts_normalized;
 719
 720         irg_walk_graph(irg, NULL, verify_irn_class_cast_state, &env);
 721
 722         if ((env.worst_situation > env.expected_state)) {
 723                 DB((dbg, LEVEL_1, "Note:  class cast state is set lower than reqired "
 724                     "in graph \n\t%+F\n", irg));
 725                 DB((dbg, LEVEL_1, "       state is %s, reqired is %s\n",
 726                         get_class_cast_state_string(env.expected_state),
 727                         get_class_cast_state_string(env.worst_situation)));
 728         }
 729 }