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

   1 /**
   2  * @file tr_inheritance.h
   3  *
   4  * Project:     libFIRM                                                   <br>
   5  * File name:   ir/tr/tp_inheritance.h                                    <br>
   6  * Purpose:     Utility routines for inheritance representation           <br>
   7  * Author:      Goetz Lindenmaier                                         <br>
   8  * Modified by:                                                           <br>
   9  * Created:                                                               <br>
  10  * Copyright:   (c) 2001-2005 Universität Karlsruhe                       <br>
  11  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE. <br>
  12  * CVS-ID:      $Id$
  13  *
  14  * This file supplies a set of utility routines for the inheritance
  15  * representation.
  16  *
  17  * Inheritance is represented in Firm by two relations: sub/supertype
  18  * between class types, overwrites/ovwerwrittenby between entities.
  19  *
  20  * - Classify pairs of types/entities in the inheritance relations.
  21  * - Resolve implicit inheritance.
  22  * - Compute the transitive closure of the subclass/superclass and
  23  *   overwrites/overwrittenby relation.
  24  *
  25  *  @see  type.h entity.h
  26  */
  27 #ifndef _FIRM_TR_INHERITANCE_H_
  28 #define _FIRM_TR_INHERITANCE_H_
  29
  30 #include "firm_types.h"
  31 #include "type.h"
  32 #include "ident.h"
  33
  34 /* ----------------------------------------------------------------------- */
  35 /* Classify pairs of types/entities in the inheritance relations.          */
  36 /* ----------------------------------------------------------------------- */
  37
  38 /** Returns true if low is subclass of high.
  39  *
  40  *  Low is a subclass of high if low == high or if low is a subclass of
  41  *  a subclass of high.  I.e, we search in all subtypes of high for low.
  42  *  @@@ this can be implemented more efficient if we know the set of all
  43  *  subclasses of high.  */
  44 int is_SubClass_of(ir_type *low, ir_type *high);
  45
  46 /** Subclass check for pointers to classes.
  47  *
  48  *  Dereferences at both types the same amount of pointer types (as
  49  *  many as possible).  If the remaining types are both class types
  50  *  and subclasses, returns true, else false.  Can also be called with
  51  *  two class types.  */
  52 int is_SubClass_ptr_of(ir_type *low, ir_type *high);
  53
  54 /** Returns true if high is superclass of low.
  55  *
  56  *  Low is a subclass of high if low == high or if low is a subclass of
  57  *  a subclass of high.  I.e, we search in all subtypes of high for low.
  58  *  @@@ this can be implemented more efficient if we know the set of all
  59  *  subclasses of high.  */
  60 #define is_SuperClass_of(high, low) is_SubClass_of(low, high)
  61
  62 /** Superclass check for pointers to classes.
  63  *
  64  *  Dereferences at both types the same amount of pointer types (as
  65  *  many as possible).  If the remaining types are both class types
  66  *  and superclasses, returns true, else false.  Can also be called with
  67  *  two class types.  */
  68 #define is_SuperClass_ptr_of(low, high) is_SubClass_ptr_of(high, low)
  69
  70 /** Returns true if high is (transitive) overwritten by low.
  71  *
  72  *  Returns false if high == low. */
  73 int is_overwritten_by(entity *high, entity *low);
  74
  75 /** Resolve polymorphism in the inheritance relation.
  76  *
  77  *  Returns the dynamically referenced entity if the static entity and the
  78  *  dynamic type are given.
  79  *  Searches downwards in overwritten tree. */
  80 entity *resolve_ent_polymorphy(ir_type *dynamic_class, entity* static_ent);
  81
  82 /* ----------------------------------------------------------------------- */
  83 /* Resolve implicit inheritance.                                           */
  84 /* ----------------------------------------------------------------------- */
  85
  86 /** Default name mangling for inherited entities.
  87  *
  88  *  Returns an ident that consists of the name of type followed by an
  89  *  underscore and the name (not ld_name) of the entity. */
  90 ident *default_mangle_inherited_name(entity *ent, ir_type *clss);
  91
  92 /** Type of argument functions for inheritance resolver.
  93  *
  94  * @param ent     The entity in the super type that will be overwritten
  95  *                by the newly generated entity, for which this name is
  96  *                used.
  97  * @param clss    The class type in which the new entity will be placed.
  98  */
  99 typedef ident *mangle_inherited_name_func(entity *ent, ir_type *clss);
 100
 101 /** Resolve implicit inheritance.
 102  *
 103  *  Resolves the implicit inheritance supplied by firm.  Firm defines,
 104  *  that each entity that is not overwritten in a subclass is
 105  *  inherited to this subclass without change implicitly.  This
 106  *  function generates entities that explicitly represent this
 107  *  inheritance.  It generates for each entity overwriting entities in
 108  *  all subclasses of the owner of the entity, if the entity is not
 109  *  overwritten in that subclass.
 110  *
 111  *  The name of the new entity is generated with the function passed.
 112  *  If the function is NULL, the default_mangle_inherited_name() is
 113  *  used.
 114  *
 115  *  This function was moved here from firmlower 3/2005.
 116  */
 117 void resolve_inheritance(mangle_inherited_name_func *mfunc);
 118
 119
 120 /* ----------------------------------------------------------------------- */
 121 /* The transitive closure of the subclass/superclass and                   */
 122 /* overwrites/overwrittenby relation.                                      */
 123 /*                                                                         */
 124 /* A walk over the ir (O(#types+#entities)) computes the transitive        */
 125 /* closure.  Adding a new type/entity or changing the basic relations in   */
 126 /* some other way invalidates the transitive closure, i.e., it is not      */
 127 /* updated by the basic functions.                                         */
 128 /*                                                                         */
 129 /* The transitive edges are held in a set, not in an array as the          */
 130 /* underlying relation.                                                    */
 131 /*                                                                         */
 132 /* Do the sets contain the node itself?  I assume NOT!                     */
 133 /* ----------------------------------------------------------------------- */
 134
 135 /** The state of the transitive closure.
 136  *
 137  *  @todo: we could manage the state for each relation separately.  Invalidating
 138  *  the entity relations does not mean invalidating the class relation. */
 139 typedef enum {
 140   inh_transitive_closure_none,       /**<  Closure is not computed, can not be accessed. */
 141   inh_transitive_closure_valid,      /**<  Closure computed and valid. */
 142   inh_transitive_closure_invalid,    /**<  Closure invalid, but can be accessed. */
 143   inh_transitive_closure_max         /**<  Invalid value. */
 144 } inh_transitive_closure_state;
 145
 146 void                         set_irp_inh_transitive_closure_state(inh_transitive_closure_state s);
 147 void                         invalidate_irp_inh_transitive_closure_state(void);
 148 inh_transitive_closure_state get_irp_inh_transitive_closure_state(void);
 149
 150
 151 /** Compute transitive closure of the subclass/superclass and
 152 * overwrites/overwrittenby relation.
 153 *
 154 * This function walks over the ir (O(#types+#entities)) to compute the
 155 * transitive closure.    */
 156 void compute_inh_transitive_closure(void);
 157
 158 /** Free memory occupied by the transitive closure information. */
 159 void free_inh_transitive_closure(void);
 160
 161
 162 /* - subtype ------------------------------------------------------------- */
 163
 164 /** Iterate over all transitive subtypes. */
 165 ir_type *get_class_trans_subtype_first(ir_type *tp);
 166 ir_type *get_class_trans_subtype_next (ir_type *tp);
 167 int   is_class_trans_subtype (ir_type *tp, ir_type *subtp);
 168
 169 /* - supertype ----------------------------------------------------------- */
 170
 171 /** Iterate over all transitive supertypes. */
 172 ir_type *get_class_trans_supertype_first(ir_type *tp);
 173 ir_type *get_class_trans_supertype_next (ir_type *tp);
 174
 175 /* - overwrittenby ------------------------------------------------------- */
 176
 177 /** Iterate over all entities that transitive overwrite this entities. */
 178 entity *get_entity_trans_overwrittenby_first(entity *ent);
 179 entity *get_entity_trans_overwrittenby_next (entity *ent);
 180
 181 /* - overwrites ---------------------------------------------------------- */
 182
 183 /** Iterate over all transitive overwritten entities. */
 184 entity *get_entity_trans_overwrites_first(entity *ent);
 185 entity *get_entity_trans_overwrites_next (entity *ent);
 186
 187
 188 /* ----------------------------------------------------------------------- */
 189 /** The state of Cast operations that cast class types or pointers to class
 190  *  types.
 191  *
 192  * The state expresses, how far Cast operations conform with the class
 193  * hierarchy.
 194  *
 195  *   class A {}
 196  *   class B1 extends A {}
 197  *   class B2 extends A {}
 198  *   class C  extends B1 {}
 199  * normalized:  Cast operations conform with the inheritance relation.
 200  *   I.e., the type of the operand of a Cast is either a super= or a sub-
 201  *   type of the type casted to. Example: (A)((B2) (new C())).
 202  * transitive:  Cast operations conform with the transitive inheritance
 203  *   relation. Example: (A)(new C()).
 204  * any:  Cast operations do not conform with the transitive inheritance
 205  *   relation.  Example: (B2)(new B1())
 206  *
 207  *  @see: tropt.h
 208  */
 209 /* ----------------------------------------------------------------------- */
 210
 211 /** Flags for class cast state.
 212  *
 213  * The state in irp is always smaller or equal to the state of any
 214  * irg.
 215  *
 216  * We rely on the ordering of the enum. */
 217 typedef enum {
 218   ir_class_casts_any        = 0, /**< There are class casts that do not cast in conformance with
 219                                       the class hierarchy.  @@@ So far this does not happen in Firm. */
 220   ir_class_casts_transitive = 1, /**< Class casts conform to transitive inheritance edges. Default. */
 221   ir_class_casts_normalized = 2, /**< Class casts conform to inheritance edges. */
 222   ir_class_casts_state_max
 223 } ir_class_cast_state;
 224 char *get_class_cast_state_string(ir_class_cast_state s);
 225
 226 void                set_irg_class_cast_state(ir_graph *irg, ir_class_cast_state s);
 227 ir_class_cast_state get_irg_class_cast_state(ir_graph *irg);
 228 void                set_irp_class_cast_state(ir_class_cast_state s);
 229 ir_class_cast_state get_irp_class_cast_state(void);
 230
 231 /** Verify the class cast state of an irg.
 232  *
 233  *  Asserts if state is to high, outputs warning if state is to low
 234  *  and firm verbosity is set.
 235  */
 236 void verify_irg_class_cast_state(ir_graph *irg);
 237 #endif  /* _FIRM_TR_INHERITANCE_H_ */