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, const 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   SymbolTable() : LastUnique(0) {}
  83   ~SymbolTable();
  84
  85 /// @}
  86 /// @name Accessors
  87 /// @{
  88 public:
  89
  90   /// This method finds the value with the given \p name in the
  91   /// type plane \p Ty and returns it. This method will not find any
  92   /// Types, only Values. Use lookupType to find Types by name.
  93   /// @returns null on failure, otherwise the Value associated with
  94   /// the \p name in type plane \p Ty.
  95   /// @brief Lookup a named, typed value.
  96   Value *lookup(const Type *Ty, const std::string &name) const;
  97
  98   /// This method finds the type with the given \p name in the
  99   /// type  map and returns it.
 100   /// @returns null if the name is not found, otherwise the Type
 101   /// associated with the \p name.
 102   /// @brief Lookup a type by name.
 103   Type* lookupType(const std::string& name) const;
 104
 105   /// @returns true iff the type map and the type plane are both not
 106   /// empty.
 107   /// @brief Determine if the symbol table is empty
 108   inline bool isEmpty() const { return pmap.empty() && tmap.empty(); }
 109
 110   /// @brief The number of name/type pairs is returned.
 111   inline unsigned num_types() const { return (unsigned)tmap.size(); }
 112
 113   /// Given a base name, return a string that is either equal to it or
 114   /// derived from it that does not already occur in the symbol table
 115   /// for the specified type.
 116   /// @brief Get a name unique to this symbol table
 117   std::string getUniqueName(const Type *Ty,
 118                             const std::string &BaseName) const;
 119
 120   /// This function can be used from the debugger to display the
 121   /// content of the symbol table while debugging.
 122   /// @brief Print out symbol table on stderr
 123   void dump() const;
 124
 125 /// @}
 126 /// @name Iteration
 127 /// @{
 128 public:
 129
 130   /// Get an iterator that starts at the beginning of the type planes.
 131   /// The iterator will iterate over the Type/ValueMap pairs in the
 132   /// type planes.
 133   inline plane_iterator plane_begin() { return pmap.begin(); }
 134
 135   /// Get a const_iterator that starts at the beginning of the type
 136   /// planes.  The iterator will iterate over the Type/ValueMap pairs
 137   /// in the type planes.
 138   inline plane_const_iterator plane_begin() const { return pmap.begin(); }
 139
 140   /// Get an iterator at the end of the type planes. This serves as
 141   /// the marker for end of iteration over the type planes.
 142   inline plane_iterator plane_end() { return pmap.end(); }
 143
 144   /// Get a const_iterator at the end of the type planes. This serves as
 145   /// the marker for end of iteration over the type planes.
 146   inline plane_const_iterator plane_end() const { return pmap.end(); }
 147
 148   /// Get an iterator that starts at the beginning of a type plane.
 149   /// The iterator will iterate over the name/value pairs in the type plane.
 150   /// @note The type plane must already exist before using this.
 151   inline value_iterator value_begin(const Type *Typ) {
 152     assert(Typ && "Can't get value iterator with null type!");
 153     return pmap.find(Typ)->second.begin();
 154   }
 155
 156   /// Get a const_iterator that starts at the beginning of a type plane.
 157   /// The iterator will iterate over the name/value pairs in the type plane.
 158   /// @note The type plane must already exist before using this.
 159   inline value_const_iterator value_begin(const Type *Typ) const {
 160     assert(Typ && "Can't get value iterator with null type!");
 161     return pmap.find(Typ)->second.begin();
 162   }
 163
 164   /// Get an iterator to the end of a type plane. This serves as the marker
 165   /// for end of iteration of the type plane.
 166   /// @note The type plane must already exist before using this.
 167   inline value_iterator value_end(const Type *Typ) {
 168     assert(Typ && "Can't get value iterator with null type!");
 169     return pmap.find(Typ)->second.end();
 170   }
 171
 172   /// Get a const_iterator to the end of a type plane. This serves as the
 173   /// marker for end of iteration of the type plane.
 174   /// @note The type plane must already exist before using this.
 175   inline value_const_iterator value_end(const Type *Typ) const {
 176     assert(Typ && "Can't get value iterator with null type!");
 177     return pmap.find(Typ)->second.end();
 178   }
 179
 180   /// Get an iterator to the start of the name/Type map.
 181   inline type_iterator type_begin() { return tmap.begin(); }
 182
 183   /// @brief Get a const_iterator to the start of the name/Type map.
 184   inline type_const_iterator type_begin() const { return tmap.begin(); }
 185
 186   /// Get an iterator to the end of the name/Type map. This serves as the
 187   /// marker for end of iteration of the types.
 188   inline type_iterator type_end() { return tmap.end(); }
 189
 190   /// Get a const-iterator to the end of the name/Type map. This serves
 191   /// as the marker for end of iteration of the types.
 192   inline type_const_iterator type_end() const { return tmap.end(); }
 193
 194   /// This method returns a plane_const_iterator for iteration over
 195   /// the type planes starting at a specific plane, given by \p Ty.
 196   /// @brief Find a type plane.
 197   inline plane_const_iterator find(const Type* Typ) const {
 198     assert(Typ && "Can't find type plane with null type!");
 199     return pmap.find(Typ);
 200   }
 201
 202   /// This method returns a plane_iterator for iteration over the
 203   /// type planes starting at a specific plane, given by \p Ty.
 204   /// @brief Find a type plane.
 205   inline plane_iterator find(const Type* Typ) {
 206     assert(Typ && "Can't find type plane with null type!");
 207     return pmap.find(Typ);
 208   }
 209
 210
 211 /// @}
 212 /// @name Mutators
 213 /// @{
 214 public:
 215
 216   /// This method will strip the symbol table of its names leaving the type and
 217   /// values.
 218   /// @brief Strip the symbol table.
 219   bool strip();
 220
 221   /// Inserts a type into the symbol table with the specified name. There can be
 222   /// a many-to-one mapping between names and types. This method allows a type
 223   /// with an existing entry in the symbol table to get a new name.
 224   /// @brief Insert a type under a new name.
 225   void insert(const std::string &Name, const Type *Typ);
 226
 227   /// Remove a type at the specified position in the symbol table.
 228   /// @returns the removed Type.
 229   Type* remove(type_iterator TI);
 230
 231 /// @}
 232 /// @name Mutators used by Value::setName and other LLVM internals.
 233 /// @{
 234 public:
 235
 236   /// This method adds the provided value \p N to the symbol table.  The Value
 237   /// must have both a name and a type which are extracted and used to place the
 238   /// value in the correct type plane under the value's name.
 239   /// @brief Add a named value to the symbol table
 240   inline void insert(Value *Val) {
 241     assert(Val && "Can't insert null type into symbol table!");
 242     assert(Val->hasName() && "Value must be named to go into symbol table!");
 243     insertEntry(Val->getName(), Val->getType(), Val);
 244   }
 245
 246   /// This method removes a named value from the symbol table. The type and name
 247   /// of the Value are extracted from \p N and used to lookup the Value in the
 248   /// correct type plane. If the Value is not in the symbol table, this method
 249   /// silently ignores the request.
 250   /// @brief Remove a named value from the symbol table.
 251   void remove(Value* Val);
 252
 253   /// changeName - Given a value with a non-empty name, remove its existing
 254   /// entry from the symbol table and insert a new one for Name.  This is
 255   /// equivalent to doing "remove(V), V->Name = Name, insert(V)", but is faster,
 256   /// and will not temporarily remove the symbol table plane if V is the last
 257   /// value in the symtab with that name (which could invalidate iterators to
 258   /// that plane).
 259   void changeName(Value *V, const std::string &Name);
 260
 261 /// @}
 262 /// @name Internal Methods
 263 /// @{
 264 private:
 265   /// @brief Insert a value into the symbol table with the specified name.
 266   void insertEntry(const std::string &Name, const Type *Ty, Value *V);
 267
 268   /// This function is called when one of the types in the type plane
 269   /// is refined.
 270   virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy);
 271
 272   /// This function markes a type as being concrete (defined).
 273   virtual void typeBecameConcrete(const DerivedType *AbsTy);
 274
 275 /// @}
 276 /// @name Internal Data
 277 /// @{
 278 private:
 279
 280   /// This is the main content of the symbol table. It provides
 281   /// separate type planes for named values. That is, each named
 282   /// value is organized into a separate dictionary based on
 283   /// Type. This means that the same name can be used for different
 284   /// types without conflict.
 285   /// @brief The mapping of types to names to values.
 286   PlaneMap pmap;
 287
 288   /// This is the type plane. It is separated from the pmap
 289   /// because the elements of the map are name/Type pairs not
 290   /// name/Value pairs and Type is not a Value.
 291   TypeMap tmap;
 292
 293   /// This value is used to retain the last unique value used
 294   /// by getUniqueName to generate unique names.
 295   mutable unsigned long LastUnique;
 296
 297 /// @}
 298
 299 };
 300
 301 } // End llvm namespace
 302
 303 // vim: sw=2
 304
 305 #endif
 306