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

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