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

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