LLVM API Documentation
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