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 "llvm/Support/DataTypes.h"
  20 #include <map>
  21
  22 namespace llvm {
  23
  24 /// This class provides a symbol table of name/value pairs that is broken
  25 /// up by type. For each Type* there is a "plane" of name/value pairs in
  26 /// the symbol table.  Identical types may have overlapping symbol names as
  27 /// long as they are distinct. The SymbolTable also tracks,  separately, a
  28 /// map of name/type pairs. This allows types to be named. Types are treated
  29 /// distinctly from Values.
  30 ///
  31 /// The SymbolTable provides several utility functions for answering common
  32 /// questions about its contents as well as an iterator interface for
  33 /// directly iterating over the contents. To reduce confusion, the terms
  34 /// "type", "value", and "plane" are used consistently. For example,
  35 /// There is a TypeMap typedef that is the mapping of names to Types.
  36 /// Similarly there is a ValueMap typedef that is the mapping of
  37 /// names to Values. Finally, there is a PlaneMap typedef that is the
  38 /// mapping of types to planes of ValueMap. This is the basic structure
  39 /// of the symbol table. When you call type_begin() you're asking
  40 /// for an iterator at the start of the TypeMap. When you call
  41 /// plane_begin(), you're asking for an iterator at the start of
  42 /// the PlaneMap. Finally, when you call value_begin(), you're asking
  43 /// for an iterator at the start of a ValueMap for a specific type
  44 /// plane.
  45 class SymbolTable : public AbstractTypeUser {
  46
  47 /// @name Types
  48 /// @{
  49 public:
  50
  51   /// @brief A mapping of names to types.
  52   typedef std::map<const std::string, const Type*> TypeMap;
  53
  54   /// @brief An iterator over the TypeMap.
  55   typedef TypeMap::iterator type_iterator;
  56
  57   /// @brief A const_iterator over the TypeMap.
  58   typedef TypeMap::const_iterator type_const_iterator;
  59
  60   /// @brief A mapping of names to values.
  61   typedef std::map<const std::string, Value *> ValueMap;
  62
  63   /// @brief An iterator over a ValueMap.
  64   typedef ValueMap::iterator value_iterator;
  65
  66   /// @brief A const_iterator over a ValueMap.
  67   typedef ValueMap::const_iterator value_const_iterator;
  68
  69   /// @brief A mapping of types to names to values (type planes).
  70   typedef std::map<const Type *, ValueMap> PlaneMap;
  71
  72   /// @brief An iterator over the type planes.
  73   typedef PlaneMap::iterator plane_iterator;
  74
  75   /// @brief A const_iterator over the type planes
  76   typedef PlaneMap::const_iterator plane_const_iterator;
  77
  78 /// @}
  79 /// @name Constructors
  80 /// @{
  81 public:
  82
  83   SymbolTable() : 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 and the type plane are both not
 107   /// empty.
 108   /// @brief Determine if the symbol table is empty
 109   inline bool isEmpty() const { return pmap.empty() && tmap.empty(); }
 110
 111   /// @brief The number of name/type pairs is returned.
 112   inline unsigned num_types() const { return unsigned(tmap.size()); }
 113
 114   /// Given a base name, return a string that is either equal to it or
 115   /// derived from it that does not already occur in the symbol table
 116   /// for the specified type.
 117   /// @brief Get a name unique to this symbol table
 118   std::string getUniqueName(const Type *Ty,
 119                             const std::string &BaseName) const;
 120
 121   /// This function can be used from the debugger to display the
 122   /// content of the symbol table while debugging.
 123   /// @brief Print out symbol table on stderr
 124   void dump() const;
 125
 126 /// @}
 127 /// @name Iteration
 128 /// @{
 129 public:
 130
 131   /// Get an iterator that starts at the beginning of the type planes.
 132   /// The iterator will iterate over the Type/ValueMap pairs in the
 133   /// type planes.
 134   inline plane_iterator plane_begin() { return pmap.begin(); }
 135
 136   /// Get a const_iterator that starts at the beginning of the type
 137   /// planes.  The iterator will iterate over the Type/ValueMap pairs
 138   /// in the type planes.
 139   inline plane_const_iterator plane_begin() const { return pmap.begin(); }
 140
 141   /// Get an iterator at the end of the type planes. This serves as
 142   /// the marker for end of iteration over the type planes.
 143   inline plane_iterator plane_end() { return pmap.end(); }
 144
 145   /// Get a const_iterator at the end of the type planes. This serves as
 146   /// the marker for end of iteration over the type planes.
 147   inline plane_const_iterator plane_end() const { return pmap.end(); }
 148
 149   /// Get an iterator that starts at the beginning of a type plane.
 150   /// The iterator will iterate over the name/value pairs in the type plane.
 151   /// @note The type plane must already exist before using this.
 152   inline value_iterator value_begin(const Type *Typ) {
 153     assert(Typ && "Can't get value iterator with null type!");
 154     return pmap.find(Typ)->second.begin();
 155   }
 156
 157   /// Get a const_iterator that starts at the beginning of a type plane.
 158   /// The iterator will iterate over the name/value pairs in the type plane.
 159   /// @note The type plane must already exist before using this.
 160   inline value_const_iterator value_begin(const Type *Typ) const {
 161     assert(Typ && "Can't get value iterator with null type!");
 162     return pmap.find(Typ)->second.begin();
 163   }
 164
 165   /// Get an iterator to the end of a type plane. This serves as the marker
 166   /// for end of iteration of the type plane.
 167   /// @note The type plane must already exist before using this.
 168   inline value_iterator value_end(const Type *Typ) {
 169     assert(Typ && "Can't get value iterator with null type!");
 170     return pmap.find(Typ)->second.end();
 171   }
 172
 173   /// Get a const_iterator to the end of a type plane. This serves as the
 174   /// marker for end of iteration of the type plane.
 175   /// @note The type plane must already exist before using this.
 176   inline value_const_iterator value_end(const Type *Typ) const {
 177     assert(Typ && "Can't get value iterator with null type!");
 178     return pmap.find(Typ)->second.end();
 179   }
 180
 181   /// Get an iterator to the start of the name/Type map.
 182   inline type_iterator type_begin() { return tmap.begin(); }
 183
 184   /// @brief Get a const_iterator to the start of the name/Type map.
 185   inline type_const_iterator type_begin() const { return tmap.begin(); }
 186
 187   /// Get an iterator to the end of the name/Type map. This serves as the
 188   /// marker for end of iteration of the types.
 189   inline type_iterator type_end() { return tmap.end(); }
 190
 191   /// Get a const-iterator to the end of the name/Type map. This serves
 192   /// as the marker for end of iteration of the types.
 193   inline type_const_iterator type_end() const { return tmap.end(); }
 194
 195   /// This method returns a plane_const_iterator for iteration over
 196   /// the type planes starting at a specific plane, given by \p Ty.
 197   /// @brief Find a type plane.
 198   inline plane_const_iterator find(const Type* Typ) const {
 199     assert(Typ && "Can't find type plane with null type!");
 200     return pmap.find(Typ);
 201   }
 202
 203   /// This method returns a plane_iterator for iteration over the
 204   /// type planes starting at a specific plane, given by \p Ty.
 205   /// @brief Find a type plane.
 206   inline plane_iterator find(const Type* Typ) {
 207     assert(Typ && "Can't find type plane with null type!");
 208     return pmap.find(Typ);
 209   }
 210
 211
 212 /// @}
 213 /// @name Mutators
 214 /// @{
 215 public:
 216
 217   /// This method will strip the symbol table of its names leaving the type and
 218   /// values.
 219   /// @brief Strip the symbol table.
 220   bool strip();
 221
 222   /// Inserts a type into the symbol table with the specified name. There can be
 223   /// a many-to-one mapping between names and types. This method allows a type
 224   /// with an existing entry in the symbol table to get a new name.
 225   /// @brief Insert a type under a new name.
 226   void insert(const std::string &Name, const Type *Typ);
 227
 228   /// Remove a type at the specified position in the symbol table.
 229   /// @returns the removed Type.
 230   Type* remove(type_iterator TI);
 231
 232 /// @}
 233 /// @name Mutators used by Value::setName and other LLVM internals.
 234 /// @{
 235 public:
 236
 237   /// This method adds the provided value \p N to the symbol table.  The Value
 238   /// must have both a name and a type which are extracted and used to place the
 239   /// value in the correct type plane under the value's name.
 240   /// @brief Add a named value to the symbol table
 241   inline void insert(Value *Val) {
 242     assert(Val && "Can't insert null type into symbol table!");
 243     assert(Val->hasName() && "Value must be named to go into symbol table!");
 244     insertEntry(Val->getName(), Val->getType(), Val);
 245   }
 246
 247   /// This method removes a named value from the symbol table. The type and name
 248   /// of the Value are extracted from \p N and used to lookup the Value in the
 249   /// correct type plane. If the Value is not in the symbol table, this method
 250   /// silently ignores the request.
 251   /// @brief Remove a named value from the symbol table.
 252   void remove(Value* Val);
 253
 254   /// changeName - Given a value with a non-empty name, remove its existing
 255   /// entry from the symbol table and insert a new one for Name.  This is
 256   /// equivalent to doing "remove(V), V->Name = Name, insert(V)", but is faster,
 257   /// and will not temporarily remove the symbol table plane if V is the last
 258   /// value in the symtab with that name (which could invalidate iterators to
 259   /// that plane).
 260   void changeName(Value *V, const std::string &Name);
 261
 262 /// @}
 263 /// @name Internal Methods
 264 /// @{
 265 private:
 266   /// @brief Insert a value into the symbol table with the specified name.
 267   void insertEntry(const std::string &Name, const Type *Ty, Value *V);
 268
 269   /// This function is called when one of the types in the type plane
 270   /// is refined.
 271   virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy);
 272
 273   /// This function markes a type as being concrete (defined).
 274   virtual void typeBecameConcrete(const DerivedType *AbsTy);
 275
 276 /// @}
 277 /// @name Internal Data
 278 /// @{
 279 private:
 280
 281   /// This is the main content of the symbol table. It provides
 282   /// separate type planes for named values. That is, each named
 283   /// value is organized into a separate dictionary based on
 284   /// Type. This means that the same name can be used for different
 285   /// types without conflict.
 286   /// @brief The mapping of types to names to values.
 287   PlaneMap pmap;
 288
 289   /// This is the type plane. It is separated from the pmap
 290   /// because the elements of the map are name/Type pairs not
 291   /// name/Value pairs and Type is not a Value.
 292   TypeMap tmap;
 293
 294   /// This value is used to retain the last unique value used
 295   /// by getUniqueName to generate unique names.
 296   mutable uint32_t LastUnique;
 297
 298 /// @}
 299
 300 };
 301
 302 } // End llvm namespace
 303
 304 // vim: sw=2
 305
 306 #endif
 307