1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
|
//===-- SymbolTable.cpp - Implement the SymbolTable class -------------------=//
//
// This file implements the SymbolTable class for the VMCore library.
//
//===----------------------------------------------------------------------===//
#include "llvm/SymbolTable.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Module.h"
#include "llvm/InstrTypes.h"
#include "Support/StringExtras.h"
#include <iostream>
#include <algorithm>
using std::string;
using std::pair;
using std::make_pair;
using std::map;
using std::cerr;
#define DEBUG_SYMBOL_TABLE 0
#define DEBUG_ABSTYPE 0
SymbolTable::~SymbolTable() {
// Drop all abstract type references in the type plane...
iterator TyPlane = find(Type::TypeTy);
if (TyPlane != end()) {
VarMap &TyP = TyPlane->second;
for (VarMap::iterator I = TyP.begin(), E = TyP.end(); I != E; ++I) {
const Type *Ty = cast<const Type>(I->second);
if (Ty->isAbstract()) // If abstract, drop the reference...
cast<DerivedType>(Ty)->removeAbstractTypeUser(this);
}
}
// TODO: FIXME: BIG ONE: This doesn't unreference abstract types for the planes
// that could still have entries!
#ifndef NDEBUG // Only do this in -g mode...
bool LeftoverValues = true;
for (iterator i = begin(); i != end(); ++i) {
for (type_iterator I = i->second.begin(); I != i->second.end(); ++I)
if (!isa<Constant>(I->second) && !isa<Type>(I->second)) {
cerr << "Value still in symbol table! Type = '"
<< i->first->getDescription() << "' Name = '"
<< I->first << "'\n";
LeftoverValues = false;
}
}
assert(LeftoverValues && "Values remain in symbol table!");
#endif
}
// getUniqueName - Given a base name, return a string that is either equal to
// it (or derived from it) that does not already occur in the symbol table for
// the specified type.
//
string SymbolTable::getUniqueName(const Type *Ty, const string &BaseName) {
iterator I = find(Ty);
if (I == end()) return BaseName;
string TryName = BaseName;
unsigned Counter = 0;
type_iterator End = I->second.end();
while (I->second.find(TryName) != End) // Loop until we find unoccupied
TryName = BaseName + utostr(++Counter); // Name in the symbol table
return TryName;
}
// lookup - Returns null on failure...
Value *SymbolTable::lookup(const Type *Ty, const string &Name) {
iterator I = find(Ty);
if (I != end()) { // We have symbols in that plane...
type_iterator J = I->second.find(Name);
if (J != I->second.end()) // and the name is in our hash table...
return J->second;
}
return 0;
}
void SymbolTable::remove(Value *N) {
assert(N->hasName() && "Value doesn't have name!");
if (InternallyInconsistent) return;
iterator I = find(N->getType());
assert(I != end() &&
"Trying to remove a type that doesn't have a plane yet!");
removeEntry(I, I->second.find(N->getName()));
}
// removeEntry - Remove a value from the symbol table...
//
Value *SymbolTable::removeEntry(iterator Plane, type_iterator Entry) {
if (InternallyInconsistent) return 0;
assert(Plane != super::end() &&
Entry != Plane->second.end() && "Invalid entry to remove!");
Value *Result = Entry->second;
const Type *Ty = Result->getType();
#if DEBUG_SYMBOL_TABLE
dump();
std::cerr << " Removing Value: " << Result->getName() << "\n";
#endif
// Remove the value from the plane...
Plane->second.erase(Entry);
// If the plane is empty, remove it now!
if (Plane->second.empty()) {
// If the plane represented an abstract type that we were interested in,
// unlink ourselves from this plane.
//
if (Plane->first->isAbstract()) {
#if DEBUG_ABSTYPE
cerr << "Plane Empty: Removing type: " << Plane->first->getDescription()
<< "\n";
#endif
cast<DerivedType>(Plane->first)->removeAbstractTypeUser(this);
}
erase(Plane);
}
// If we are removing an abstract type, remove the symbol table from it's use
// list...
if (Ty == Type::TypeTy) {
const Type *T = cast<const Type>(Result);
if (T->isAbstract()) {
#if DEBUG_ABSTYPE
cerr << "Removing abs type from symtab" << T->getDescription() << "\n";
#endif
cast<DerivedType>(T)->removeAbstractTypeUser(this);
}
}
return Result;
}
// insertEntry - Insert a value into the symbol table with the specified
// name...
//
void SymbolTable::insertEntry(const string &Name, const Type *VTy, Value *V) {
// Check to see if there is a naming conflict. If so, rename this value!
if (lookup(VTy, Name)) {
string UniqueName = getUniqueName(VTy, Name);
assert(InternallyInconsistent == false && "Infinite loop inserting entry!");
InternallyInconsistent = true;
V->setName(UniqueName, this);
InternallyInconsistent = false;
return;
}
#if DEBUG_SYMBOL_TABLE
dump();
cerr << " Inserting definition: " << Name << ": "
<< VTy->getDescription() << "\n";
#endif
iterator I = find(VTy);
if (I == end()) { // Not in collection yet... insert dummy entry
// Insert a new empty element. I points to the new elements.
I = super::insert(make_pair(VTy, VarMap())).first;
assert(I != end() && "How did insert fail?");
// Check to see if the type is abstract. If so, it might be refined in the
// future, which would cause the plane of the old type to get merged into
// a new type plane.
//
if (VTy->isAbstract()) {
cast<DerivedType>(VTy)->addAbstractTypeUser(this);
#if DEBUG_ABSTYPE
cerr << "Added abstract type value: " << VTy->getDescription() << "\n";
#endif
}
}
I->second.insert(make_pair(Name, V));
// If we are adding an abstract type, add the symbol table to it's use list.
if (VTy == Type::TypeTy) {
const Type *T = cast<const Type>(V);
if (T->isAbstract()) {
cast<DerivedType>(T)->addAbstractTypeUser(this);
#if DEBUG_ABSTYPE
cerr << "Added abstract type to ST: " << T->getDescription() << "\n";
#endif
}
}
}
// This function is called when one of the types in the type plane are refined
void SymbolTable::refineAbstractType(const DerivedType *OldType,
const Type *NewType) {
if (OldType == NewType && OldType->isAbstract())
return; // Noop, don't waste time dinking around
// Search to see if we have any values of the type oldtype. If so, we need to
// move them into the newtype plane...
iterator TPI = find(OldType);
if (OldType != NewType && TPI != end()) {
// Get a handle to the new type plane...
iterator NewTypeIt = find(NewType);
if (NewTypeIt == super::end()) { // If no plane exists, add one
NewTypeIt = super::insert(make_pair(NewType, VarMap())).first;
if (NewType->isAbstract()) {
cast<DerivedType>(NewType)->addAbstractTypeUser(this);
#if DEBUG_ABSTYPE
cerr << "[Added] refined to abstype: "<<NewType->getDescription()<<"\n";
#endif
}
}
VarMap &NewPlane = NewTypeIt->second;
VarMap &OldPlane = TPI->second;
while (!OldPlane.empty()) {
pair<const string, Value*> V = *OldPlane.begin();
// Check to see if there is already a value in the symbol table that this
// would collide with.
type_iterator TI = NewPlane.find(V.first);
if (TI != NewPlane.end() && TI->second == V.second) {
// No action
} else if (TI != NewPlane.end()) {
// The only thing we are allowing for now is two method prototypes being
// folded into one.
//
Function *ExistM = dyn_cast<Function>(TI->second);
Function *NewM = dyn_cast<Function>(V.second);
if (ExistM && NewM && ExistM->isExternal() && NewM->isExternal()) {
// Ok we have two external methods. Make all uses of the new one
// use the old one...
//
NewM->replaceAllUsesWith(ExistM);
// Now we just convert it to an unnamed method... which won't get
// added to our symbol table. The problem is that if we call
// setName on the method that it will try to remove itself from
// the symbol table and die... because it's not in the symtab
// right now. To fix this, we have an internally consistent flag
// that turns remove into a noop. Thus the name will get null'd
// out, but the symbol table won't get upset.
//
assert(InternallyInconsistent == false &&
"Symbol table already inconsistent!");
InternallyInconsistent = true;
// Remove newM from the symtab
NewM->setName("");
InternallyInconsistent = false;
// Now we can remove this method from the module entirely...
NewM->getParent()->getFunctionList().remove(NewM);
delete NewM;
} else {
assert(0 && "Two ploanes folded together with overlapping "
"value names!");
}
} else {
insertEntry(V.first, NewType, V.second);
}
// Remove the item from the old type plane
OldPlane.erase(OldPlane.begin());
}
// Ok, now we are not referencing the type anymore... take me off your user
// list please!
#if DEBUG_ABSTYPE
cerr << "Removing type " << OldType->getDescription() << "\n";
#endif
OldType->removeAbstractTypeUser(this);
// Remove the plane that is no longer used
erase(TPI);
} else if (TPI != end()) {
assert(OldType == NewType);
#if DEBUG_ABSTYPE
cerr << "Removing SELF type " << OldType->getDescription() << "\n";
#endif
OldType->removeAbstractTypeUser(this);
}
TPI = find(Type::TypeTy);
if (TPI != end()) {
// Loop over all of the types in the symbol table, replacing any references
// to OldType with references to NewType. Note that there may be multiple
// occurances, and although we only need to remove one at a time, it's
// faster to remove them all in one pass.
//
VarMap &TyPlane = TPI->second;
for (VarMap::iterator I = TyPlane.begin(), E = TyPlane.end(); I != E; ++I)
if (I->second == (Value*)OldType) { // FIXME when Types aren't const.
#if DEBUG_ABSTYPE
cerr << "Removing type " << OldType->getDescription() << "\n";
#endif
OldType->removeAbstractTypeUser(this);
I->second = (Value*)NewType; // TODO FIXME when types aren't const
if (NewType->isAbstract()) {
#if DEBUG_ABSTYPE
cerr << "Added type " << NewType->getDescription() << "\n";
#endif
cast<const DerivedType>(NewType)->addAbstractTypeUser(this);
}
}
}
}
static void DumpVal(const pair<const string, Value *> &V) {
std::cout << " '" << V.first << "' = ";
V.second->dump();
std::cout << "\n";
}
static void DumpPlane(const pair<const Type *, map<const string, Value *> >&P) {
std::cout << " Plane: ";
P.first->dump();
std::cout << "\n";
for_each(P.second.begin(), P.second.end(), DumpVal);
}
void SymbolTable::dump() const {
std::cout << "Symbol table dump:\n";
for_each(begin(), end(), DumpPlane);
}
|