LLVM API Documentation

SymbolTable.h

Go to the documentation of this file.
00001 //===-- llvm/SymbolTable.h - Implement a type plane'd symtab ----*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and re-written by Reid
00006 // Spencer. It is distributed under the University of Illinois Open Source
00007 // License. See LICENSE.TXT for details.
00008 //
00009 //===----------------------------------------------------------------------===//
00010 //
00011 // This file implements the main symbol table for LLVM.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #ifndef LLVM_SYMBOL_TABLE_H
00016 #define LLVM_SYMBOL_TABLE_H
00017 
00018 #include "llvm/Value.h"
00019 #include "llvm/Support/DataTypes.h"
00020 #include <map>
00021 
00022 namespace llvm {
00023 
00024 /// This class provides a symbol table of name/value pairs that is broken
00025 /// up by type. For each Type* there is a "plane" of name/value pairs in
00026 /// the symbol table.  Identical types may have overlapping symbol names as
00027 /// long as they are distinct. The SymbolTable also tracks,  separately, a
00028 /// map of name/type pairs. This allows types to be named. Types are treated
00029 /// distinctly from Values.
00030 ///
00031 /// The SymbolTable provides several utility functions for answering common
00032 /// questions about its contents as well as an iterator interface for
00033 /// directly iterating over the contents. To reduce confusion, the terms
00034 /// "type", "value", and "plane" are used consistently. For example,
00035 /// There is a TypeMap typedef that is the mapping of names to Types.
00036 /// Similarly there is a ValueMap typedef that is the mapping of
00037 /// names to Values. Finally, there is a PlaneMap typedef that is the
00038 /// mapping of types to planes of ValueMap. This is the basic structure
00039 /// of the symbol table. When you call type_begin() you're asking
00040 /// for an iterator at the start of the TypeMap. When you call
00041 /// plane_begin(), you're asking for an iterator at the start of
00042 /// the PlaneMap. Finally, when you call value_begin(), you're asking
00043 /// for an iterator at the start of a ValueMap for a specific type
00044 /// plane.
00045 class SymbolTable : public AbstractTypeUser {
00046 
00047 /// @name Types
00048 /// @{
00049 public:
00050 
00051   /// @brief A mapping of names to types.
00052   typedef std::map<const std::string, const Type*> TypeMap;
00053 
00054   /// @brief An iterator over the TypeMap.
00055   typedef TypeMap::iterator type_iterator;
00056 
00057   /// @brief A const_iterator over the TypeMap.
00058   typedef TypeMap::const_iterator type_const_iterator;
00059 
00060   /// @brief A mapping of names to values.
00061   typedef std::map<const std::string, Value *> ValueMap;
00062 
00063   /// @brief An iterator over a ValueMap.
00064   typedef ValueMap::iterator value_iterator;
00065 
00066   /// @brief A const_iterator over a ValueMap.
00067   typedef ValueMap::const_iterator value_const_iterator;
00068 
00069   /// @brief A mapping of types to names to values (type planes).
00070   typedef std::map<const Type *, ValueMap> PlaneMap;
00071 
00072   /// @brief An iterator over the type planes.
00073   typedef PlaneMap::iterator plane_iterator;
00074 
00075   /// @brief A const_iterator over the type planes
00076   typedef PlaneMap::const_iterator plane_const_iterator;
00077 
00078 /// @}
00079 /// @name Constructors
00080 /// @{
00081 public:
00082 
00083   SymbolTable() : LastUnique(0) {}
00084   ~SymbolTable();
00085 
00086 /// @}
00087 /// @name Accessors
00088 /// @{
00089 public:
00090 
00091   /// This method finds the value with the given \p name in the
00092   /// type plane \p Ty and returns it. This method will not find any
00093   /// Types, only Values. Use lookupType to find Types by name.
00094   /// @returns null on failure, otherwise the Value associated with
00095   /// the \p name in type plane \p Ty.
00096   /// @brief Lookup a named, typed value.
00097   Value *lookup(const Type *Ty, const std::string &name) const;
00098 
00099   /// This method finds the type with the given \p name in the
00100   /// type  map and returns it.
00101   /// @returns null if the name is not found, otherwise the Type
00102   /// associated with the \p name.
00103   /// @brief Lookup a type by name.
00104   Type* lookupType(const std::string& name) const;
00105 
00106   /// @returns true iff the type map and the type plane are both not
00107   /// empty.
00108   /// @brief Determine if the symbol table is empty
00109   inline bool isEmpty() const { return pmap.empty() && tmap.empty(); }
00110 
00111   /// @brief The number of name/type pairs is returned.
00112   inline unsigned num_types() const { return unsigned(tmap.size()); }
00113 
00114   /// Given a base name, return a string that is either equal to it or
00115   /// derived from it that does not already occur in the symbol table
00116   /// for the specified type.
00117   /// @brief Get a name unique to this symbol table
00118   std::string getUniqueName(const Type *Ty,
00119                             const std::string &BaseName) const;
00120 
00121   /// This function can be used from the debugger to display the
00122   /// content of the symbol table while debugging.
00123   /// @brief Print out symbol table on stderr
00124   void dump() const;
00125 
00126 /// @}
00127 /// @name Iteration
00128 /// @{
00129 public:
00130 
00131   /// Get an iterator that starts at the beginning of the type planes.
00132   /// The iterator will iterate over the Type/ValueMap pairs in the
00133   /// type planes.
00134   inline plane_iterator plane_begin() { return pmap.begin(); }
00135 
00136   /// Get a const_iterator that starts at the beginning of the type
00137   /// planes.  The iterator will iterate over the Type/ValueMap pairs
00138   /// in the type planes.
00139   inline plane_const_iterator plane_begin() const { return pmap.begin(); }
00140 
00141   /// Get an iterator at the end of the type planes. This serves as
00142   /// the marker for end of iteration over the type planes.
00143   inline plane_iterator plane_end() { return pmap.end(); }
00144 
00145   /// Get a const_iterator at the end of the type planes. This serves as
00146   /// the marker for end of iteration over the type planes.
00147   inline plane_const_iterator plane_end() const { return pmap.end(); }
00148 
00149   /// Get an iterator that starts at the beginning of a type plane.
00150   /// The iterator will iterate over the name/value pairs in the type plane.
00151   /// @note The type plane must already exist before using this.
00152   inline value_iterator value_begin(const Type *Typ) {
00153     assert(Typ && "Can't get value iterator with null type!");
00154     return pmap.find(Typ)->second.begin();
00155   }
00156 
00157   /// Get a const_iterator that starts at the beginning of a type plane.
00158   /// The iterator will iterate over the name/value pairs in the type plane.
00159   /// @note The type plane must already exist before using this.
00160   inline value_const_iterator value_begin(const Type *Typ) const {
00161     assert(Typ && "Can't get value iterator with null type!");
00162     return pmap.find(Typ)->second.begin();
00163   }
00164 
00165   /// Get an iterator to the end of a type plane. This serves as the marker
00166   /// for end of iteration of the type plane.
00167   /// @note The type plane must already exist before using this.
00168   inline value_iterator value_end(const Type *Typ) {
00169     assert(Typ && "Can't get value iterator with null type!");
00170     return pmap.find(Typ)->second.end();
00171   }
00172 
00173   /// Get a const_iterator to the end of a type plane. This serves as the
00174   /// marker for end of iteration of the type plane.
00175   /// @note The type plane must already exist before using this.
00176   inline value_const_iterator value_end(const Type *Typ) const {
00177     assert(Typ && "Can't get value iterator with null type!");
00178     return pmap.find(Typ)->second.end();
00179   }
00180 
00181   /// Get an iterator to the start of the name/Type map.
00182   inline type_iterator type_begin() { return tmap.begin(); }
00183 
00184   /// @brief Get a const_iterator to the start of the name/Type map.
00185   inline type_const_iterator type_begin() const { return tmap.begin(); }
00186 
00187   /// Get an iterator to the end of the name/Type map. This serves as the
00188   /// marker for end of iteration of the types.
00189   inline type_iterator type_end() { return tmap.end(); }
00190 
00191   /// Get a const-iterator to the end of the name/Type map. This serves
00192   /// as the marker for end of iteration of the types.
00193   inline type_const_iterator type_end() const { return tmap.end(); }
00194 
00195   /// This method returns a plane_const_iterator for iteration over
00196   /// the type planes starting at a specific plane, given by \p Ty.
00197   /// @brief Find a type plane.
00198   inline plane_const_iterator find(const Type* Typ) const {
00199     assert(Typ && "Can't find type plane with null type!");
00200     return pmap.find(Typ);
00201   }
00202 
00203   /// This method returns a plane_iterator for iteration over the
00204   /// type planes starting at a specific plane, given by \p Ty.
00205   /// @brief Find a type plane.
00206   inline plane_iterator find(const Type* Typ) {
00207     assert(Typ && "Can't find type plane with null type!");
00208     return pmap.find(Typ);
00209   }
00210 
00211 
00212 /// @}
00213 /// @name Mutators
00214 /// @{
00215 public:
00216 
00217   /// This method will strip the symbol table of its names leaving the type and
00218   /// values.
00219   /// @brief Strip the symbol table.
00220   bool strip();
00221 
00222   /// Inserts a type into the symbol table with the specified name. There can be
00223   /// a many-to-one mapping between names and types. This method allows a type
00224   /// with an existing entry in the symbol table to get a new name.
00225   /// @brief Insert a type under a new name.
00226   void insert(const std::string &Name, const Type *Typ);
00227 
00228   /// Remove a type at the specified position in the symbol table.
00229   /// @returns the removed Type.
00230   Type* remove(type_iterator TI);
00231 
00232 /// @}
00233 /// @name Mutators used by Value::setName and other LLVM internals.
00234 /// @{
00235 public:
00236 
00237   /// This method adds the provided value \p N to the symbol table.  The Value
00238   /// must have both a name and a type which are extracted and used to place the
00239   /// value in the correct type plane under the value's name.
00240   /// @brief Add a named value to the symbol table
00241   inline void insert(Value *Val) {
00242     assert(Val && "Can't insert null type into symbol table!");
00243     assert(Val->hasName() && "Value must be named to go into symbol table!");
00244     insertEntry(Val->getName(), Val->getType(), Val);
00245   }
00246 
00247   /// This method removes a named value from the symbol table. The type and name
00248   /// of the Value are extracted from \p N and used to lookup the Value in the
00249   /// correct type plane. If the Value is not in the symbol table, this method
00250   /// silently ignores the request.
00251   /// @brief Remove a named value from the symbol table.
00252   void remove(Value* Val);
00253 
00254   /// changeName - Given a value with a non-empty name, remove its existing
00255   /// entry from the symbol table and insert a new one for Name.  This is
00256   /// equivalent to doing "remove(V), V->Name = Name, insert(V)", but is faster,
00257   /// and will not temporarily remove the symbol table plane if V is the last
00258   /// value in the symtab with that name (which could invalidate iterators to
00259   /// that plane).
00260   void changeName(Value *V, const std::string &Name);
00261 
00262 /// @}
00263 /// @name Internal Methods
00264 /// @{
00265 private:
00266   /// @brief Insert a value into the symbol table with the specified name.
00267   void insertEntry(const std::string &Name, const Type *Ty, Value *V);
00268 
00269   /// This function is called when one of the types in the type plane
00270   /// is refined.
00271   virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy);
00272 
00273   /// This function markes a type as being concrete (defined).
00274   virtual void typeBecameConcrete(const DerivedType *AbsTy);
00275 
00276 /// @}
00277 /// @name Internal Data
00278 /// @{
00279 private:
00280 
00281   /// This is the main content of the symbol table. It provides
00282   /// separate type planes for named values. That is, each named
00283   /// value is organized into a separate dictionary based on
00284   /// Type. This means that the same name can be used for different
00285   /// types without conflict.
00286   /// @brief The mapping of types to names to values.
00287   PlaneMap pmap;
00288 
00289   /// This is the type plane. It is separated from the pmap
00290   /// because the elements of the map are name/Type pairs not
00291   /// name/Value pairs and Type is not a Value.
00292   TypeMap tmap;
00293 
00294   /// This value is used to retain the last unique value used
00295   /// by getUniqueName to generate unique names.
00296   mutable uint32_t LastUnique;
00297 
00298 /// @}
00299 
00300 };
00301 
00302 } // End llvm namespace
00303 
00304 // vim: sw=2
00305 
00306 #endif
00307