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 "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