LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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 <map>
00020 
00021 namespace llvm {
00022 
00023 /// This class provides a symbol table of name/value pairs that is broken
00024 /// up by type. For each Type* there is a "plane" of name/value pairs in 
00025 /// the symbol table.  Identical types may have overlapping symbol names as 
00026 /// long as they are distinct. The SymbolTable also tracks,  separately, a 
00027 /// map of name/type pairs. This allows types to be named. Types are treated 
00028 /// distinctly from Values.
00029 /// 
00030 /// The SymbolTable provides several utility functions for answering common
00031 /// questions about its contents as well as an iterator interface for
00032 /// directly iterating over the contents. To reduce confusion, the terms 
00033 /// "type", "value", and "plane" are used consistently. For example,
00034 /// There is a TypeMap typedef that is the mapping of names to Types. 
00035 /// Similarly there is a ValueMap typedef that is the mapping of 
00036 /// names to Values. Finally, there is a PlaneMap typedef that is the
00037 /// mapping of types to planes of ValueMap. This is the basic structure
00038 /// of the symbol table. When you call type_begin() you're asking
00039 /// for an iterator at the start of the TypeMap. When you call
00040 /// plane_begin(), you're asking for an iterator at the start of 
00041 /// the PlaneMap. Finally, when you call value_begin(), you're asking
00042 /// for an iterator at the start of a ValueMap for a specific type
00043 /// plane.
00044 class SymbolTable : public AbstractTypeUser {
00045 
00046 /// @name Types
00047 /// @{
00048 public:
00049 
00050   /// @brief A mapping of names to types.
00051   typedef std::map<const std::string, const Type*> TypeMap;
00052 
00053   /// @brief An iterator over the TypeMap.
00054   typedef TypeMap::iterator type_iterator;
00055 
00056   /// @brief A const_iterator over the TypeMap.
00057   typedef TypeMap::const_iterator type_const_iterator;
00058 
00059   /// @brief A mapping of names to values.
00060   typedef std::map<const std::string, Value *> ValueMap;
00061 
00062   /// @brief An iterator over a ValueMap.
00063   typedef ValueMap::iterator value_iterator;
00064 
00065   /// @brief A const_iterator over a ValueMap.
00066   typedef ValueMap::const_iterator value_const_iterator;
00067 
00068   /// @brief A mapping of types to names to values (type planes).
00069   typedef std::map<const Type *, ValueMap> PlaneMap;
00070 
00071   /// @brief An iterator over the type planes.
00072   typedef PlaneMap::iterator plane_iterator;
00073 
00074   /// @brief A const_iterator over the type planes
00075   typedef PlaneMap::const_iterator plane_const_iterator;
00076 
00077 /// @}
00078 /// @name Constructors
00079 /// @{
00080 public:
00081 
00082   inline SymbolTable() 
00083     : pmap(), tmap(), InternallyInconsistent(false), 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 is not empty.
00107   /// @brief Determine if there are types in the symbol table
00108   inline bool hasTypes() const { return ! tmap.empty(); }
00109 
00110   /// @returns true iff the type map and the type plane are both not 
00111   /// empty.
00112   /// @brief Determine if the symbol table is empty
00113   inline bool isEmpty() const { return pmap.empty() && tmap.empty(); }
00114 
00115   /// The plane associated with the \p TypeID parameter is found
00116   /// and the number of entries in the plane is returned.
00117   /// @returns Number of entries in the specified type plane or 0.
00118   /// @brief Get the size of a type plane.
00119   unsigned type_size(const Type *TypeID) const;
00120 
00121   /// @brief The number of name/type pairs is returned.
00122   inline unsigned num_types() const { return (unsigned)tmap.size(); }
00123 
00124   /// Finds the value \p val in the symbol table and returns its
00125   /// name. Only the type plane associated with the type of \p val
00126   /// is searched.
00127   /// @brief Return the name of a value
00128   std::string get_name( const Value* Val ) const;
00129 
00130   /// Finds the type \p Ty in the symbol table and returns its name.
00131   /// @brief Return the name of a type
00132   std::string get_name( const Type* Ty ) const;
00133 
00134   /// Given a base name, return a string that is either equal to it or 
00135   /// derived from it that does not already occur in the symbol table 
00136   /// for the specified type.
00137   /// @brief Get a name unique to this symbol table
00138   std::string getUniqueName(const Type *Ty, 
00139     const std::string &BaseName) const;
00140 
00141   /// This function can be used from the debugger to display the
00142   /// content of the symbol table while debugging.
00143   /// @brief Print out symbol table on stderr
00144   void dump() const;  
00145 
00146 /// @}
00147 /// @name Mutators
00148 /// @{
00149 public:
00150 
00151   /// This method adds the provided value \p N to the symbol table. 
00152   /// The Value must have both a name and a type which are extracted 
00153   /// and used to place the value in the correct type plane under 
00154   /// the value's name.
00155   /// @brief Add a named value to the symbol table
00156   inline void insert(Value *Val) {
00157     assert(Val && "Can't insert null type into symbol table!");
00158     assert(Val->hasName() && "Value must be named to go into symbol table!");
00159     insertEntry(Val->getName(), Val->getType(), Val);
00160   }
00161 
00162   /// Inserts a constant into the symbol table with the specified
00163   /// name. There can be a many to one mapping between names and constants.
00164   /// @brief Insert a constant or type.
00165   inline void insert(const std::string &Name, Value *Val) {
00166     assert(Val && "Can't insert null type into symbol table!");
00167     assert(isa<Constant>(Val) &&
00168            "Can only insert constants into a symbol table!");
00169     insertEntry(Name, Val->getType(), Val);
00170   }
00171 
00172   /// Inserts a type into the symbol table with the specified name. There
00173   /// can be a many-to-one mapping between names and types. This method
00174   /// allows a type with an existing entry in the symbol table to get
00175   /// a new name.
00176   /// @brief Insert a type under a new name.
00177   inline void insert(const std::string &Name, const Type *Typ) {
00178     assert(Typ && "Can't insert null type into symbol table!");
00179     insertEntry(Name, Typ );
00180   }
00181 
00182   /// This method removes a named value from the symbol table. The
00183   /// type and name of the Value are extracted from \p N and used to
00184   /// lookup the Value in the correct type plane. If the Value is
00185   /// not in the symbol table, this method silently ignores the
00186   /// request.
00187   /// @brief Remove a named value from the symbol table.
00188   void remove(Value* Val);
00189 
00190   /// This method removes a named type from the symbol table. The
00191   /// name of the type is extracted from \p T and used to look up
00192   /// the Type in the type map. If the Type is not in the symbol
00193   /// table, this method silently ignores the request.
00194   /// @brief Remove a named type from the symbol table.
00195   void remove(const Type* Typ );
00196 
00197   /// Remove a constant or type with the specified name from the 
00198   /// symbol table.
00199   /// @returns the removed Value.
00200   /// @brief Remove a constant or type from the symbol table.
00201   inline Value* remove(const std::string &Name, Value *Val) {
00202     assert(Val && "Can't remove null value from symbol table!");
00203     plane_iterator PI = pmap.find(Val->getType());
00204     return removeEntry(PI, PI->second.find(Name));
00205   }
00206 
00207   /// Remove a type at the specified position in the symbol table.
00208   /// @returns the removed Type.
00209   inline Type* remove(type_iterator TI) {
00210     return removeEntry(TI);
00211   }
00212 
00213   /// Removes a specific value from the symbol table. 
00214   /// @returns the removed value.
00215   /// @brief Remove a specific value given by an iterator
00216   inline Value *value_remove(const value_iterator &It) {
00217     return this->removeEntry(pmap.find(It->second->getType()), It);
00218   }
00219 
00220   /// This method will strip the symbol table of its names leaving
00221   /// the type and values. 
00222   /// @brief Strip the symbol table. 
00223   bool strip();
00224 
00225   /// @brief Empty the symbol table completely.
00226   inline void clear() { pmap.clear(); tmap.clear(); }
00227 
00228 /// @}
00229 /// @name Iteration
00230 /// @{
00231 public:
00232 
00233   /// Get an iterator that starts at the beginning of the type planes.
00234   /// The iterator will iterate over the Type/ValueMap pairs in the
00235   /// type planes. 
00236   inline plane_iterator plane_begin() { return pmap.begin(); }
00237 
00238   /// Get a const_iterator that starts at the beginning of the type 
00239   /// planes.  The iterator will iterate over the Type/ValueMap pairs 
00240   /// in the type planes. 
00241   inline plane_const_iterator plane_begin() const { return pmap.begin(); }
00242 
00243   /// Get an iterator at the end of the type planes. This serves as
00244   /// the marker for end of iteration over the type planes.
00245   inline plane_iterator plane_end() { return pmap.end(); }
00246 
00247   /// Get a const_iterator at the end of the type planes. This serves as
00248   /// the marker for end of iteration over the type planes.
00249   inline plane_const_iterator plane_end() const { return pmap.end(); }
00250 
00251   /// Get an iterator that starts at the beginning of a type plane.
00252   /// The iterator will iterate over the name/value pairs in the type plane.
00253   /// @note The type plane must already exist before using this.
00254   inline value_iterator value_begin(const Type *Typ) { 
00255     assert(Typ && "Can't get value iterator with null type!");
00256     return pmap.find(Typ)->second.begin(); 
00257   }
00258 
00259   /// Get a const_iterator that starts at the beginning of a type plane.
00260   /// The iterator will iterate over the name/value pairs in the type plane.
00261   /// @note The type plane must already exist before using this.
00262   inline value_const_iterator value_begin(const Type *Typ) const {
00263     assert(Typ && "Can't get value iterator with null type!");
00264     return pmap.find(Typ)->second.begin(); 
00265   }
00266 
00267   /// Get an iterator to the end of a type plane. This serves as the marker
00268   /// for end of iteration of the type plane.
00269   /// @note The type plane must already exist before using this.
00270   inline value_iterator value_end(const Type *Typ) { 
00271     assert(Typ && "Can't get value iterator with null type!");
00272     return pmap.find(Typ)->second.end(); 
00273   }
00274 
00275   /// Get a const_iterator to the end of a type plane. This serves as the
00276   /// marker for end of iteration of the type plane.
00277   /// @note The type plane must already exist before using this.
00278   inline value_const_iterator value_end(const Type *Typ) const { 
00279     assert(Typ && "Can't get value iterator with null type!");
00280     return pmap.find(Typ)->second.end(); 
00281   }
00282 
00283   /// Get an iterator to the start of the name/Type map.
00284   inline type_iterator type_begin() { return tmap.begin(); }
00285 
00286   /// @brief Get a const_iterator to the start of the name/Type map.
00287   inline type_const_iterator type_begin() const { return tmap.begin(); }
00288 
00289   /// Get an iterator to the end of the name/Type map. This serves as the
00290   /// marker for end of iteration of the types.
00291   inline type_iterator type_end() { return tmap.end(); }
00292 
00293   /// Get a const-iterator to the end of the name/Type map. This serves 
00294   /// as the marker for end of iteration of the types.
00295   inline type_const_iterator type_end() const { return tmap.end(); }
00296 
00297   /// This method returns a plane_const_iterator for iteration over
00298   /// the type planes starting at a specific plane, given by \p Ty.
00299   /// @brief Find a type plane.
00300   inline plane_const_iterator find(const Type* Typ ) const {
00301     assert(Typ && "Can't find type plane with null type!");
00302     return pmap.find( Typ );
00303   }
00304 
00305   /// This method returns a plane_iterator for iteration over the
00306   /// type planes starting at a specific plane, given by \p Ty.
00307   /// @brief Find a type plane.
00308   inline plane_iterator find( const Type* Typ ) { 
00309     assert(Typ && "Can't find type plane with null type!");
00310     return pmap.find(Typ); 
00311   }
00312 
00313   /// This method returns a ValueMap* for a specific type plane. This
00314   /// interface is deprecated and may go away in the future.
00315   /// @deprecated
00316   /// @brief Find a type plane
00317   inline const ValueMap* findPlane( const Type* Typ ) const {
00318     assert(Typ && "Can't find type plane with null type!");
00319     plane_const_iterator I = pmap.find( Typ );
00320     if ( I == pmap.end() ) return 0;
00321     return &I->second;
00322   }
00323 
00324 /// @}
00325 /// @name Internal Methods
00326 /// @{
00327 private:
00328   /// @brief Insert a value into the symbol table with the specified name.
00329   void insertEntry(const std::string &Name, const Type *Ty, Value *V);
00330 
00331   /// @brief Insert a type into the symbol table with the specified name.
00332   void insertEntry(const std::string &Name, const Type *T);
00333 
00334   /// Remove a specific value from a specific plane in the SymbolTable.
00335   /// @returns the removed Value.
00336   Value* removeEntry(plane_iterator Plane, value_iterator Entry);
00337 
00338   /// Remove a specific type from the SymbolTable.
00339   /// @returns the removed Type.
00340   Type*  removeEntry(type_iterator Entry);
00341 
00342   /// This function is called when one of the types in the type plane 
00343   /// is refined.
00344   virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy);
00345 
00346   /// This function markes a type as being concrete (defined).
00347   virtual void typeBecameConcrete(const DerivedType *AbsTy);
00348 
00349 /// @}
00350 /// @name Internal Data 
00351 /// @{
00352 private:
00353 
00354   /// This is the main content of the symbol table. It provides
00355   /// separate type planes for named values. That is, each named
00356   /// value is organized into a separate dictionary based on 
00357   /// Type. This means that the same name can be used for different
00358   /// types without conflict. 
00359   /// @brief The mapping of types to names to values.
00360   PlaneMap pmap;
00361 
00362   /// This is the type plane. It is separated from the pmap
00363   /// because the elements of the map are name/Type pairs not 
00364   /// name/Value pairs and Type is not a Value.
00365   TypeMap tmap;
00366 
00367   /// There are times when the symbol table is internally inconsistent with 
00368   /// the rest of the program.  In this one case, a value exists with a Name, 
00369   /// and it's not in the symbol table.  When we call V->setName(""), it 
00370   /// tries to remove itself from the symbol table and dies.  We know this 
00371   /// is happening, and so if the flag InternallyInconsistent is set, 
00372   /// removal from the symbol table is a noop.
00373   /// @brief Indicator of symbol table internal inconsistency.
00374   bool InternallyInconsistent;
00375 
00376   /// This value is used to retain the last unique value used
00377   /// by getUniqueName to generate unique names.
00378   mutable unsigned long LastUnique;
00379 
00380 /// @}
00381 
00382 };
00383 
00384 } // End llvm namespace
00385 
00386 // vim: sw=2
00387 
00388 #endif
00389