include/llvm/SymbolTable.h

   1 //===-- llvm/SymbolTable.h - Implement a type plane'd symtab ----*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and re-written by Reid
   6 // Spencer. It is distributed under the University of Illinois Open Source
   7 // License. See LICENSE.TXT for details.
   8 //
   9 //===----------------------------------------------------------------------===//
  10 //
  11 // This file implements the main symbol table for LLVM.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_SYMBOL_TABLE_H
  16 #define LLVM_SYMBOL_TABLE_H
  17
  18 #include "llvm/Value.h"
  19 #include <map>
  20
  21 namespace llvm {
  22
  23 /// This class provides a symbol table of name/value pairs that is broken
  24 /// up by type. For each Type* there is a "plane" of name/value pairs in
  25 /// the symbol table.  Identical types may have overlapping symbol names as
  26 /// long as they are distinct. The SymbolTable also tracks,  separately, a
  27 /// map of name/type pairs. This allows types to be named. Types are treated
  28 /// distinctly from Values.
  29 ///
  30 /// The SymbolTable provides several utility functions for answering common
  31 /// questions about its contents as well as an iterator interface for
  32 /// directly iterating over the contents. To reduce confusion, the terms
  33 /// "type", "value", and "plane" are used consistently. For example,
  34 /// There is a TypeMap typedef that is the mapping of names to Types.
  35 /// Similarly there is a ValueMap typedef that is the mapping of
  36 /// names to Values. Finally, there is a PlaneMap typedef that is the
  37 /// mapping of types to planes of ValueMap. THis is the basic structure
  38 /// of the symbol table. When you call type_begin() you're asking
  39 /// for an iterator at the start of the TypeMap. When you call
  40 /// plane_begin(), you're asking for an iterator at the start of
  41 /// the PlaneMap. Finally, when you call value_begin(), you're asking
  42 /// for an iterator at the start of a ValueMap for a specific type
  43 /// plane.
  44 class SymbolTable : public AbstractTypeUser {
  45
  46 /// @name Types
  47 /// @{
  48 public:
  49
  50   /// @brief A mapping of names to types.
  51   typedef std::map<const std::string, Type*> TypeMap;
  52
  53   /// @brief An iterator over the TypeMap.
  54   typedef TypeMap::iterator type_iterator;
  55
  56   /// @brief A const_iterator over the TypeMap.
  57   typedef TypeMap::const_iterator type_const_iterator;
  58
  59   /// @brief A mapping of names to values.
  60   typedef std::map<const std::string, Value *> ValueMap;
  61
  62   /// @brief An iterator over a ValueMap.
  63   typedef ValueMap::iterator value_iterator;
  64
  65   /// @brief A const_iterator over a ValueMap.
  66   typedef ValueMap::const_iterator value_const_iterator;
  67
  68   /// @brief A mapping of types to names to values (type planes).
  69   typedef std::map<const Type *, ValueMap> PlaneMap;
  70
  71   /// @brief An iterator over the type planes.
  72   typedef PlaneMap::iterator plane_iterator;
  73
  74   /// @brief A const_iterator over the type planes
  75   typedef PlaneMap::const_iterator plane_const_iterator;
  76
  77 /// @}
  78 /// @name Constructors
  79 /// @{
  80 public:
  81
  82   inline SymbolTable()
  83     : pmap(), tmap(), InternallyInconsistent(false), LastUnique(0) {}
  84   ~SymbolTable();
  85
  86 /// @}
  87 /// @name Accessors
  88 /// @{
  89 public:
  90
  91   /// This method finds the value with the given \p name in the
  92   /// type plane \p Ty and returns it. This method will not find any
  93   /// Types, only Values. Use lookupType to find Types by name.
  94   /// @returns null on failure, otherwise the Value associated with
  95   /// the \p name in type plane \p Ty.
  96   /// @brief Lookup a named, typed value.
  97   Value *lookup(const Type *Ty, const std::string &name) const;
  98
  99   /// This method finds the type with the given \p name in the
 100   /// type  map and returns it.
 101   /// @returns null if the name is not found, otherwise the Type
 102   /// associated with the \p name.
 103   /// @brief Lookup a type by name.
 104   Type* lookupType( const std::string& name ) const;
 105
 106   /// @returns true iff the type map is not empty.
 107   /// @brief Determine if there are types in the symbol table
 108   inline bool hasTypes() const { return ! tmap.empty(); }
 109
 110   /// @returns true iff the type map and the type plane are both not
 111   /// empty.
 112   /// @brief Determine if the symbol table is empty
 113   inline bool isEmpty() const { return pmap.empty() && tmap.empty(); }
 114
 115   /// The plane associated with the \p TypeID parameter is found
 116   /// and the number of entries in the plane is returned.
 117   /// @returns Number of entries in the specified type plane or 0.
 118   /// @brief Get the size of a type plane.
 119   unsigned type_size(const Type *TypeID) const;
 120
 121   /// @brief The number of name/type pairs is returned.
 122   inline unsigned num_types() const { return tmap.size(); }
 123
 124   /// Finds the value \p val in the symbol table and returns its
 125   /// name. Only the type plane associated with the type of \p val
 126   /// is searched.
 127   /// @brief Return the name of a value
 128   std::string get_name( const Value* Val ) const;
 129
 130   /// Finds the type \p Ty in the symbol table and returns its name.
 131   /// @brief Return the name of a type
 132   std::string get_name( const Type* Ty ) const;
 133
 134   /// Given a base name, return a string that is either equal to it or
 135   /// derived from it that does not already occur in the symbol table
 136   /// for the specified type.
 137   /// @brief Get a name unique to this symbol table
 138   std::string getUniqueName(const Type *Ty,
 139     const std::string &BaseName) const;
 140
 141   /// This function can be used from the debugger to display the
 142   /// content of the symbol table while debugging.
 143   /// @brief Print out symbol table on stderr
 144   void dump() const;
 145
 146 /// @}
 147 /// @name Mutators
 148 /// @{
 149 public:
 150
 151   /// This method adds the provided value \p N to the symbol table.
 152   /// The Value must have both a name and a type which are extracted
 153   /// and used to place the value in the correct type plane under
 154   /// the value's name.
 155   /// @brief Add a named value to the symbol table
 156   inline void insert(Value *Val) {
 157     assert(Val && "Can't insert null type into symbol table!");
 158     assert(Val->hasName() && "Value must be named to go into symbol table!");
 159     insertEntry(Val->getName(), Val->getType(), Val);
 160   }
 161
 162   /// Inserts a constant or type into the symbol table with the specified
 163   /// name. There can be a many to one mapping between names and constants
 164   /// or types.
 165   /// @brief Insert a constant or type.
 166   inline void insert(const std::string &Name, Value *Val) {
 167     assert(Val && "Can't insert null type into symbol table!");
 168     assert(!isa<Type>(Val) && "Cannot insert types with this interface!");
 169     assert(isa<Constant>(Val) &&
 170            "Can only insert constants into a symbol table!");
 171     insertEntry(Name, Val->getType(), Val);
 172   }
 173
 174   /// Inserts a type into the symbol table with the specified name. There
 175   /// can be a many-to-one mapping between names and types. This method
 176   /// allows a type with an existing entry in the symbol table to get
 177   /// a new name.
 178   /// @brief Insert a type under a new name.
 179   inline void insert(const std::string &Name, Type *Typ) {
 180     assert(Typ && "Can't insert null type into symbol table!");
 181     insertEntry(Name, Typ );
 182   }
 183
 184   /// This method removes a named value from the symbol table. The
 185   /// type and name of the Value are extracted from \p N and used to
 186   /// lookup the Value in the correct type plane. If the Value is
 187   /// not in the symbol table, this method silently ignores the
 188   /// request.
 189   /// @brief Remove a named value from the symbol table.
 190   void remove(Value* Val);
 191
 192   /// This method removes a named type from the symbol table. The
 193   /// name of the type is extracted from \p T and used to look up
 194   /// the Type in the type map. If the Type is not in the symbol
 195   /// table, this method silently ignores the request.
 196   /// @brief Remove a named type from the symbol table.
 197   void remove(Type* Typ );
 198
 199   /// Remove a constant or type with the specified name from the
 200   /// symbol table.
 201   /// @returns the removed Value.
 202   /// @brief Remove a constant or type from the symbol table.
 203   inline Value* remove(const std::string &Name, Value *Val) {
 204     assert(Val && "Can't remove null value from symbol table!");
 205     assert(!isa<Type>(Val) && "Can't remove types with this interface!");
 206     plane_iterator PI = pmap.find(Val->getType());
 207     return removeEntry(PI, PI->second.find(Name));
 208   }
 209
 210   /// Remove a type at the specified position in the symbol table.
 211   /// @returns the removed Type.
 212   inline Type* remove(type_iterator TI) {
 213     return removeEntry(TI);
 214   }
 215
 216   /// Removes a specific value from the symbol table.
 217   /// @returns the removed value.
 218   /// @brief Remove a specific value given by an iterator
 219   inline Value *value_remove(const value_iterator &It) {
 220     return this->removeEntry(pmap.find(It->second->getType()), It);
 221   }
 222
 223   /// This method will strip the symbol table of its names leaving
 224   /// the type and values.
 225   /// @brief Strip the symbol table.
 226   bool strip();
 227
 228   /// @brief Empty the symbol table completely.
 229   inline void clear() { pmap.clear(); tmap.clear(); }
 230
 231 /// @}
 232 /// @name Iteration
 233 /// @{
 234 public:
 235
 236   /// Get an iterator that starts at the beginning of the type planes.
 237   /// The iterator will iterate over the Type/ValueMap pairs in the
 238   /// type planes.
 239   inline plane_iterator plane_begin() { return pmap.begin(); }
 240
 241   /// Get a const_iterator that starts at the beginning of the type
 242   /// planes.  The iterator will iterate over the Type/ValueMap pairs
 243   /// in the type planes.
 244   inline plane_const_iterator plane_begin() const { return pmap.begin(); }
 245
 246   /// Get an iterator at the end of the type planes. This serves as
 247   /// the marker for end of iteration over the type planes.
 248   inline plane_iterator plane_end() { return pmap.end(); }
 249
 250   /// Get a const_iterator at the end of the type planes. This serves as
 251   /// the marker for end of iteration over the type planes.
 252   inline plane_const_iterator plane_end() const { return pmap.end(); }
 253
 254   /// Get an iterator that starts at the beginning of a type plane.
 255   /// The iterator will iterate over the name/value pairs in the type plane.
 256   /// @note The type plane must already exist before using this.
 257   inline value_iterator value_begin(const Type *Typ) {
 258     assert(Typ && "Can't get value iterator with null type!");
 259     return pmap.find(Typ)->second.begin();
 260   }
 261
 262   /// Get a const_iterator that starts at the beginning of a type plane.
 263   /// The iterator will iterate over the name/value pairs in the type plane.
 264   /// @note The type plane must already exist before using this.
 265   inline value_const_iterator value_begin(const Type *Typ) const {
 266     assert(Typ && "Can't get value iterator with null type!");
 267     return pmap.find(Typ)->second.begin();
 268   }
 269
 270   /// Get an iterator to the end of a type plane. This serves as the marker
 271   /// for end of iteration of the type plane.
 272   /// @note The type plane must already exist before using this.
 273   inline value_iterator value_end(const Type *Typ) {
 274     assert(Typ && "Can't get value iterator with null type!");
 275     return pmap.find(Typ)->second.end();
 276   }
 277
 278   /// Get a const_iterator to the end of a type plane. This serves as the
 279   /// marker for end of iteration of the type plane.
 280   /// @note The type plane must already exist before using this.
 281   inline value_const_iterator value_end(const Type *Typ) const {
 282     assert(Typ && "Can't get value iterator with null type!");
 283     return pmap.find(Typ)->second.end();
 284   }
 285
 286   /// Get an iterator to the start of the name/Type map.
 287   inline type_iterator type_begin() { return tmap.begin(); }
 288
 289   /// @brief Get a const_iterator to the start of the name/Type map.
 290   inline type_const_iterator type_begin() const { return tmap.begin(); }
 291
 292   /// Get an iterator to the end of the name/Type map. This serves as the
 293   /// marker for end of iteration of the types.
 294   inline type_iterator type_end() { return tmap.end(); }
 295
 296   /// Get a const-iterator to the end of the name/Type map. This serves
 297   /// as the marker for end of iteration of the types.
 298   inline type_const_iterator type_end() const { return tmap.end(); }
 299
 300   /// This method returns a plane_const_iterator for iteration over
 301   /// the type planes starting at a specific plane, given by \p Ty.
 302   /// @brief Find a type plane.
 303   inline plane_const_iterator find(const Type* Typ ) const {
 304     assert(Typ && "Can't find type plane with null type!");
 305     return pmap.find( Typ );
 306   }
 307
 308   /// This method returns a plane_iterator for iteration over the
 309   /// type planes starting at a specific plane, given by \p Ty.
 310   /// @brief Find a type plane.
 311   inline plane_iterator find( const Type* Typ ) {
 312     assert(Typ && "Can't find type plane with null type!");
 313     return pmap.find(Typ);
 314   }
 315
 316   /// This method returns a ValueMap* for a specific type plane. This
 317   /// interface is deprecated and may go away in the future.
 318   /// @deprecated
 319   /// @brief Find a type plane
 320   inline const ValueMap* findPlane( const Type* Typ ) const {
 321     assert(Typ && "Can't find type plane with null type!");
 322     plane_const_iterator I = pmap.find( Typ );
 323     if ( I == pmap.end() ) return 0;
 324     return &I->second;
 325   }
 326
 327 /// @}
 328 /// @name Internal Methods
 329 /// @{
 330 private:
 331   /// @brief Insert a value into the symbol table with the specified name.
 332   void insertEntry(const std::string &Name, const Type *Ty, Value *V);
 333
 334   /// @brief Insert a type into the symbol table with the specified name.
 335   void insertEntry(const std::string &Name, Type *T);
 336
 337   /// Remove a specific value from a specific plane in the SymbolTable.
 338   /// @returns the removed Value.
 339   Value* removeEntry(plane_iterator Plane, value_iterator Entry);
 340
 341   /// Remove a specific type from the SymbolTable.
 342   /// @returns the removed Type.
 343   Type*  removeEntry(type_iterator Entry);
 344
 345   /// This function is called when one of the types in the type plane
 346   /// is refined.
 347   virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy);
 348
 349   /// This function markes a type as being concrete (defined).
 350   virtual void typeBecameConcrete(const DerivedType *AbsTy);
 351
 352 /// @}
 353 /// @name Internal Data
 354 /// @{
 355 private:
 356
 357   /// This is the main content of the symbol table. It provides
 358   /// separate type planes for named values. That is, each named
 359   /// value is organized into a separate dictionary based on
 360   /// Type. This means that the same name can be used for different
 361   /// types without conflict. Note that the Type::TypeTy plane is
 362   /// not stored in this map but is in tmap.
 363   /// @brief The mapping of types to names to values.
 364   PlaneMap pmap;
 365
 366   /// This is the Type::TypeTy plane. It is separated from the pmap
 367   /// because the elements of the map are name/Type pairs not
 368   /// name/Value pairs and Type is not a Value.
 369   TypeMap tmap;
 370
 371   /// There are times when the symbol table is internally inconsistent with
 372   /// the rest of the program.  In this one case, a value exists with a Name,
 373   /// and it's not in the symbol table.  When we call V->setName(""), it
 374   /// tries to remove itself from the symbol table and dies.  We know this
 375   /// is happening, and so if the flag InternallyInconsistent is set,
 376   /// removal from the symbol table is a noop.
 377   /// @brief Indicator of symbol table internal inconsistency.
 378   bool InternallyInconsistent;
 379
 380   /// This value is used to retain the last unique value used
 381   /// by getUniqueName to generate unique names.
 382   mutable unsigned long LastUnique;
 383
 384 /// @}
 385
 386 };
 387
 388 } // End llvm namespace
 389
 390 // vim: sw=2
 391
 392 #endif
 393