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