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"
19 #include "llvm/Support/DataTypes.h"
24 /// This class provides a symbol table of name/value pairs that is broken
25 /// up by type. For each Type* there is a "plane" of name/value pairs in
26 /// the symbol table. Identical types may have overlapping symbol names as
27 /// long as they are distinct. The SymbolTable also tracks, separately, a
28 /// map of name/type pairs. This allows types to be named. Types are treated
29 /// distinctly from Values.
31 /// The SymbolTable provides several utility functions for answering common
32 /// questions about its contents as well as an iterator interface for
33 /// directly iterating over the contents. To reduce confusion, the terms
34 /// "type", "value", and "plane" are used consistently. For example,
35 /// There is a TypeMap typedef that is the mapping of names to Types.
36 /// Similarly there is a ValueMap typedef that is the mapping of
37 /// names to Values. Finally, there is a PlaneMap typedef that is the
38 /// mapping of types to planes of ValueMap. This is the basic structure
39 /// of the symbol table. When you call type_begin() you're asking
40 /// for an iterator at the start of the TypeMap. When you call
41 /// plane_begin(), you're asking for an iterator at the start of
42 /// the PlaneMap. Finally, when you call value_begin(), you're asking
43 /// for an iterator at the start of a ValueMap for a specific type
45 class SymbolTable : public AbstractTypeUser {
50 /// @brief A mapping of names to values.
51 typedef std::map<const std::string, Value *> ValueMap;
53 /// @brief An iterator over a ValueMap.
54 typedef ValueMap::iterator value_iterator;
56 /// @brief A const_iterator over a ValueMap.
57 typedef ValueMap::const_iterator value_const_iterator;
59 /// @brief A mapping of types to names to values (type planes).
60 typedef std::map<const Type *, ValueMap> PlaneMap;
62 /// @brief An iterator over the type planes.
63 typedef PlaneMap::iterator plane_iterator;
65 /// @brief A const_iterator over the type planes
66 typedef PlaneMap::const_iterator plane_const_iterator;
69 /// @name Constructors
73 SymbolTable() : LastUnique(0) {}
81 /// This method finds the value with the given \p name in the
82 /// type plane \p Ty and returns it. This method will not find any
83 /// Types, only Values. Use lookupType to find Types by name.
84 /// @returns null on failure, otherwise the Value associated with
85 /// the \p name in type plane \p Ty.
86 /// @brief Lookup a named, typed value.
87 Value *lookup(const Type *Ty, const std::string &name) const;
89 /// @returns true iff the type map and the type plane are both not
91 /// @brief Determine if the symbol table is empty
92 inline bool isEmpty() const { return pmap.empty(); }
94 /// Given a base name, return a string that is either equal to it or
95 /// derived from it that does not already occur in the symbol table
96 /// for the specified type.
97 /// @brief Get a name unique to this symbol table
98 std::string getUniqueName(const Type *Ty,
99 const std::string &BaseName) const;
101 /// This function can be used from the debugger to display the
102 /// content of the symbol table while debugging.
103 /// @brief Print out symbol table on stderr
111 /// Get an iterator that starts at the beginning of the type planes.
112 /// The iterator will iterate over the Type/ValueMap pairs in the
114 inline plane_iterator plane_begin() { return pmap.begin(); }
116 /// Get a const_iterator that starts at the beginning of the type
117 /// planes. The iterator will iterate over the Type/ValueMap pairs
118 /// in the type planes.
119 inline plane_const_iterator plane_begin() const { return pmap.begin(); }
121 /// Get an iterator at the end of the type planes. This serves as
122 /// the marker for end of iteration over the type planes.
123 inline plane_iterator plane_end() { return pmap.end(); }
125 /// Get a const_iterator at the end of the type planes. This serves as
126 /// the marker for end of iteration over the type planes.
127 inline plane_const_iterator plane_end() const { return pmap.end(); }
129 /// Get an iterator that starts at the beginning of a type plane.
130 /// The iterator will iterate over the name/value pairs in the type plane.
131 /// @note The type plane must already exist before using this.
132 inline value_iterator value_begin(const Type *Typ) {
133 assert(Typ && "Can't get value iterator with null type!");
134 return pmap.find(Typ)->second.begin();
137 /// Get a const_iterator that starts at the beginning of a type plane.
138 /// The iterator will iterate over the name/value pairs in the type plane.
139 /// @note The type plane must already exist before using this.
140 inline value_const_iterator value_begin(const Type *Typ) const {
141 assert(Typ && "Can't get value iterator with null type!");
142 return pmap.find(Typ)->second.begin();
145 /// Get an iterator to the end of a type plane. This serves as the marker
146 /// for end of iteration of the type plane.
147 /// @note The type plane must already exist before using this.
148 inline value_iterator value_end(const Type *Typ) {
149 assert(Typ && "Can't get value iterator with null type!");
150 return pmap.find(Typ)->second.end();
153 /// Get a const_iterator to the end of a type plane. This serves as the
154 /// marker for end of iteration of the type plane.
155 /// @note The type plane must already exist before using this.
156 inline value_const_iterator value_end(const Type *Typ) const {
157 assert(Typ && "Can't get value iterator with null type!");
158 return pmap.find(Typ)->second.end();
161 /// This method returns a plane_const_iterator for iteration over
162 /// the type planes starting at a specific plane, given by \p Ty.
163 /// @brief Find a type plane.
164 inline plane_const_iterator find(const Type* Typ) const {
165 assert(Typ && "Can't find type plane with null type!");
166 return pmap.find(Typ);
169 /// This method returns a plane_iterator for iteration over the
170 /// type planes starting at a specific plane, given by \p Ty.
171 /// @brief Find a type plane.
172 inline plane_iterator find(const Type* Typ) {
173 assert(Typ && "Can't find type plane with null type!");
174 return pmap.find(Typ);
183 /// This method will strip the symbol table of its names leaving the type and
185 /// @brief Strip the symbol table.
189 /// @name Mutators used by Value::setName and other LLVM internals.
193 /// This method adds the provided value \p N to the symbol table. The Value
194 /// must have both a name and a type which are extracted and used to place the
195 /// value in the correct type plane under the value's name.
196 /// @brief Add a named value to the symbol table
197 inline void insert(Value *Val) {
198 assert(Val && "Can't insert null type into symbol table!");
199 assert(Val->hasName() && "Value must be named to go into symbol table!");
200 insertEntry(Val->getName(), Val->getType(), Val);
203 /// This method removes a named value from the symbol table. The type and name
204 /// of the Value are extracted from \p N and used to lookup the Value in the
205 /// correct type plane. If the Value is not in the symbol table, this method
206 /// silently ignores the request.
207 /// @brief Remove a named value from the symbol table.
208 void remove(Value* Val);
210 /// changeName - Given a value with a non-empty name, remove its existing
211 /// entry from the symbol table and insert a new one for Name. This is
212 /// equivalent to doing "remove(V), V->Name = Name, insert(V)", but is faster,
213 /// and will not temporarily remove the symbol table plane if V is the last
214 /// value in the symtab with that name (which could invalidate iterators to
216 void changeName(Value *V, const std::string &Name);
219 /// @name Internal Methods
222 /// @brief Insert a value into the symbol table with the specified name.
223 void insertEntry(const std::string &Name, const Type *Ty, Value *V);
225 /// This function is called when one of the types in the type plane
227 virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy);
229 /// This function markes a type as being concrete (defined).
230 virtual void typeBecameConcrete(const DerivedType *AbsTy);
233 /// @name Internal Data
237 /// This is the main content of the symbol table. It provides
238 /// separate type planes for named values. That is, each named
239 /// value is organized into a separate dictionary based on
240 /// Type. This means that the same name can be used for different
241 /// types without conflict.
242 /// @brief The mapping of types to names to values.
245 /// This value is used to retain the last unique value used
246 /// by getUniqueName to generate unique names.
247 mutable uint32_t LastUnique;
252 } // End llvm namespace