1 //===-- llvm/SymbolTable.h - Implement a type plane'd symtab ----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
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.
9 //===----------------------------------------------------------------------===//
11 // This file implements the main symbol table for LLVM.
13 //===----------------------------------------------------------------------===//
15 #ifndef LLVM_SYMBOL_TABLE_H
16 #define LLVM_SYMBOL_TABLE_H
18 #include "llvm/Value.h"
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.
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
44 class SymbolTable : public AbstractTypeUser {
50 /// @brief A mapping of names to types.
51 typedef std::map<const std::string, Type*> TypeMap;
53 /// @brief An iterator over the TypeMap.
54 typedef TypeMap::iterator type_iterator;
56 /// @brief A const_iterator over the TypeMap.
57 typedef TypeMap::const_iterator type_const_iterator;
59 /// @brief A mapping of names to values.
60 typedef std::map<const std::string, Value *> ValueMap;
62 /// @brief An iterator over a ValueMap.
63 typedef ValueMap::iterator value_iterator;
65 /// @brief A const_iterator over a ValueMap.
66 typedef ValueMap::const_iterator value_const_iterator;
68 /// @brief A mapping of types to names to values (type planes).
69 typedef std::map<const Type *, ValueMap> PlaneMap;
71 /// @brief An iterator over the type planes.
72 typedef PlaneMap::iterator plane_iterator;
74 /// @brief A const_iterator over the type planes
75 typedef PlaneMap::const_iterator plane_const_iterator;
78 /// @name Constructors
83 : pmap(), tmap(), InternallyInconsistent(false), LastUnique(0) {}
91 /// This method finds the value with the given \p name in the
92 /// type plane \p Ty and returns it. This method will not find any
93 /// Types, only Values. Use lookupType to find Types by name.
94 /// @returns null on failure, otherwise the Value associated with
95 /// the \p name in type plane \p Ty.
96 /// @brief Lookup a named, typed value.
97 Value *lookup(const Type *Ty, const std::string &name) const;
99 /// This method finds the type with the given \p name in the
100 /// type map and returns it.
101 /// @returns null if the name is not found, otherwise the Type
102 /// associated with the \p name.
103 /// @brief Lookup a type by name.
104 Type* lookupType( const std::string& name ) const;
106 /// @returns true iff the type map is not empty.
107 /// @brief Determine if there are types in the symbol table
108 inline bool hasTypes() const { return ! tmap.empty(); }
110 /// @returns true iff the type map and the type plane are both not
112 /// @brief Determine if the symbol table is empty
113 inline bool isEmpty() const { return pmap.empty() && tmap.empty(); }
115 /// The plane associated with the \p TypeID parameter is found
116 /// and the number of entries in the plane is returned.
117 /// @returns Number of entries in the specified type plane or 0.
118 /// @brief Get the size of a type plane.
119 unsigned type_size(const Type *TypeID) const;
121 /// @brief The number of name/type pairs is returned.
122 inline unsigned num_types() const { return tmap.size(); }
124 /// Finds the value \p val in the symbol table and returns its
125 /// name. Only the type plane associated with the type of \p val
127 /// @brief Return the name of a value
128 std::string get_name( const Value* Val ) const;
130 /// Finds the type \p Ty in the symbol table and returns its name.
131 /// @brief Return the name of a type
132 std::string get_name( const Type* Ty ) const;
134 /// Given a base name, return a string that is either equal to it or
135 /// derived from it that does not already occur in the symbol table
136 /// for the specified type.
137 /// @brief Get a name unique to this symbol table
138 std::string getUniqueName(const Type *Ty,
139 const std::string &BaseName) const;
141 /// This function can be used from the debugger to display the
142 /// content of the symbol table while debugging.
143 /// @brief Print out symbol table on stderr
151 /// This method adds the provided value \p N to the symbol table.
152 /// The Value must have both a name and a type which are extracted
153 /// and used to place the value in the correct type plane under
154 /// the value's name.
155 /// @brief Add a named value to the symbol table
156 inline void insert(Value *Val) {
157 assert(Val && "Can't insert null type into symbol table!");
158 assert(Val->hasName() && "Value must be named to go into symbol table!");
159 insertEntry(Val->getName(), Val->getType(), Val);
162 /// Inserts a constant or type into the symbol table with the specified
163 /// name. There can be a many to one mapping between names and constants
165 /// @brief Insert a constant or type.
166 inline void insert(const std::string &Name, Value *Val) {
167 assert(Val && "Can't insert null type into symbol table!");
168 assert(!isa<Type>(Val) && "Cannot insert types with this interface!");
169 assert(isa<Constant>(Val) &&
170 "Can only insert constants into a symbol table!");
171 insertEntry(Name, Val->getType(), Val);
174 /// Inserts a type into the symbol table with the specified name. There
175 /// can be a many-to-one mapping between names and types. This method
176 /// allows a type with an existing entry in the symbol table to get
178 /// @brief Insert a type under a new name.
179 inline void insert(const std::string &Name, Type *Typ) {
180 assert(Typ && "Can't insert null type into symbol table!");
181 insertEntry(Name, Typ );
184 /// This method removes a named value from the symbol table. The
185 /// type and name of the Value are extracted from \p N and used to
186 /// lookup the Value in the correct type plane. If the Value is
187 /// not in the symbol table, this method silently ignores the
189 /// @brief Remove a named value from the symbol table.
190 void remove(Value* Val);
192 /// This method removes a named type from the symbol table. The
193 /// name of the type is extracted from \p T and used to look up
194 /// the Type in the type map. If the Type is not in the symbol
195 /// table, this method silently ignores the request.
196 /// @brief Remove a named type from the symbol table.
197 void remove(Type* Typ );
199 /// Remove a constant or type with the specified name from the
201 /// @returns the removed Value.
202 /// @brief Remove a constant or type from the symbol table.
203 inline Value* remove(const std::string &Name, Value *Val) {
204 assert(Val && "Can't remove null value from symbol table!");
205 assert(!isa<Type>(Val) && "Can't remove types with this interface!");
206 plane_iterator PI = pmap.find(Val->getType());
207 return removeEntry(PI, PI->second.find(Name));
210 /// Remove a type at the specified position in the symbol table.
211 /// @returns the removed Type.
212 inline Type* remove(type_iterator TI) {
213 return removeEntry(TI);
216 /// Removes a specific value from the symbol table.
217 /// @returns the removed value.
218 /// @brief Remove a specific value given by an iterator
219 inline Value *value_remove(const value_iterator &It) {
220 return this->removeEntry(pmap.find(It->second->getType()), It);
223 /// This method will strip the symbol table of its names leaving
224 /// the type and values.
225 /// @brief Strip the symbol table.
228 /// @brief Empty the symbol table completely.
229 inline void clear() { pmap.clear(); tmap.clear(); }
236 /// Get an iterator that starts at the beginning of the type planes.
237 /// The iterator will iterate over the Type/ValueMap pairs in the
239 inline plane_iterator plane_begin() { return pmap.begin(); }
241 /// Get a const_iterator that starts at the beginning of the type
242 /// planes. The iterator will iterate over the Type/ValueMap pairs
243 /// in the type planes.
244 inline plane_const_iterator plane_begin() const { return pmap.begin(); }
246 /// Get an iterator at the end of the type planes. This serves as
247 /// the marker for end of iteration over the type planes.
248 inline plane_iterator plane_end() { return pmap.end(); }
250 /// Get a const_iterator at the end of the type planes. This serves as
251 /// the marker for end of iteration over the type planes.
252 inline plane_const_iterator plane_end() const { return pmap.end(); }
254 /// Get an iterator that starts at the beginning of a type plane.
255 /// The iterator will iterate over the name/value pairs in the type plane.
256 /// @note The type plane must already exist before using this.
257 inline value_iterator value_begin(const Type *Typ) {
258 assert(Typ && "Can't get value iterator with null type!");
259 return pmap.find(Typ)->second.begin();
262 /// Get a const_iterator that starts at the beginning of a type plane.
263 /// The iterator will iterate over the name/value pairs in the type plane.
264 /// @note The type plane must already exist before using this.
265 inline value_const_iterator value_begin(const Type *Typ) const {
266 assert(Typ && "Can't get value iterator with null type!");
267 return pmap.find(Typ)->second.begin();
270 /// Get an iterator to the end of a type plane. This serves as the marker
271 /// for end of iteration of the type plane.
272 /// @note The type plane must already exist before using this.
273 inline value_iterator value_end(const Type *Typ) {
274 assert(Typ && "Can't get value iterator with null type!");
275 return pmap.find(Typ)->second.end();
278 /// Get a const_iterator to the end of a type plane. This serves as the
279 /// marker for end of iteration of the type plane.
280 /// @note The type plane must already exist before using this.
281 inline value_const_iterator value_end(const Type *Typ) const {
282 assert(Typ && "Can't get value iterator with null type!");
283 return pmap.find(Typ)->second.end();
286 /// Get an iterator to the start of the name/Type map.
287 inline type_iterator type_begin() { return tmap.begin(); }
289 /// @brief Get a const_iterator to the start of the name/Type map.
290 inline type_const_iterator type_begin() const { return tmap.begin(); }
292 /// Get an iterator to the end of the name/Type map. This serves as the
293 /// marker for end of iteration of the types.
294 inline type_iterator type_end() { return tmap.end(); }
296 /// Get a const-iterator to the end of the name/Type map. This serves
297 /// as the marker for end of iteration of the types.
298 inline type_const_iterator type_end() const { return tmap.end(); }
300 /// This method returns a plane_const_iterator for iteration over
301 /// the type planes starting at a specific plane, given by \p Ty.
302 /// @brief Find a type plane.
303 inline plane_const_iterator find(const Type* Typ ) const {
304 assert(Typ && "Can't find type plane with null type!");
305 return pmap.find( Typ );
308 /// This method returns a plane_iterator for iteration over the
309 /// type planes starting at a specific plane, given by \p Ty.
310 /// @brief Find a type plane.
311 inline plane_iterator find( const Type* Typ ) {
312 assert(Typ && "Can't find type plane with null type!");
313 return pmap.find(Typ);
316 /// This method returns a ValueMap* for a specific type plane. This
317 /// interface is deprecated and may go away in the future.
319 /// @brief Find a type plane
320 inline const ValueMap* findPlane( const Type* Typ ) const {
321 assert(Typ && "Can't find type plane with null type!");
322 plane_const_iterator I = pmap.find( Typ );
323 if ( I == pmap.end() ) return 0;
328 /// @name Internal Methods
331 /// @brief Insert a value into the symbol table with the specified name.
332 void insertEntry(const std::string &Name, const Type *Ty, Value *V);
334 /// @brief Insert a type into the symbol table with the specified name.
335 void insertEntry(const std::string &Name, Type *T);
337 /// Remove a specific value from a specific plane in the SymbolTable.
338 /// @returns the removed Value.
339 Value* removeEntry(plane_iterator Plane, value_iterator Entry);
341 /// Remove a specific type from the SymbolTable.
342 /// @returns the removed Type.
343 Type* removeEntry(type_iterator Entry);
345 /// This function is called when one of the types in the type plane
347 virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy);
349 /// This function markes a type as being concrete (defined).
350 virtual void typeBecameConcrete(const DerivedType *AbsTy);
353 /// @name Internal Data
357 /// This is the main content of the symbol table. It provides
358 /// separate type planes for named values. That is, each named
359 /// value is organized into a separate dictionary based on
360 /// Type. This means that the same name can be used for different
361 /// types without conflict. Note that the Type::TypeTy plane is
362 /// not stored in this map but is in tmap.
363 /// @brief The mapping of types to names to values.
366 /// This is the Type::TypeTy plane. It is separated from the pmap
367 /// because the elements of the map are name/Type pairs not
368 /// name/Value pairs and Type is not a Value.
371 /// There are times when the symbol table is internally inconsistent with
372 /// the rest of the program. In this one case, a value exists with a Name,
373 /// and it's not in the symbol table. When we call V->setName(""), it
374 /// tries to remove itself from the symbol table and dies. We know this
375 /// is happening, and so if the flag InternallyInconsistent is set,
376 /// removal from the symbol table is a noop.
377 /// @brief Indicator of symbol table internal inconsistency.
378 bool InternallyInconsistent;
380 /// This value is used to retain the last unique value used
381 /// by getUniqueName to generate unique names.
382 mutable unsigned long LastUnique;
388 } // End llvm namespace