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
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
|
//===-- SymbolTable.cpp - Implement the SymbolTable class -----------------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and revised by Reid
// Spencer. It is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the SymbolTable class for the VMCore library.
//
//===----------------------------------------------------------------------===//
#include "llvm/SymbolTable.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Module.h"
#include "llvm/ADT/StringExtras.h"
#include <algorithm>
#include <iostream>
using namespace llvm;
#define DEBUG_SYMBOL_TABLE 0
#define DEBUG_ABSTYPE 0
SymbolTable::~SymbolTable() {
// Drop all abstract type references in the type plane...
for (type_iterator TI = tmap.begin(), TE = tmap.end(); TI != TE; ++TI) {
if (TI->second->isAbstract()) // If abstract, drop the reference...
cast<DerivedType>(TI->second)->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 (plane_iterator PI = pmap.begin(); PI != pmap.end(); ++PI) {
for (value_iterator VI = PI->second.begin(); VI != PI->second.end(); ++VI)
if (!isa<Constant>(VI->second) ) {
std::cerr << "Value still in symbol table! Type = '"
<< PI->first->getDescription() << "' Name = '"
<< VI->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.
//
std::string SymbolTable::getUniqueName(const Type *Ty,
const std::string &BaseName) const {
// Find the plane
plane_const_iterator PI = pmap.find(Ty);
if (PI == pmap.end()) return BaseName;
std::string TryName = BaseName;
const ValueMap& vmap = PI->second;
value_const_iterator End = vmap.end();
// See if the name exists
while (vmap.find(TryName) != End) // Loop until we find a free
TryName = BaseName + utostr(++LastUnique); // name in the symbol table
return TryName;
}
// lookup a value - Returns null on failure...
Value *SymbolTable::lookup(const Type *Ty, const std::string &Name) const {
plane_const_iterator PI = pmap.find(Ty);
if (PI != pmap.end()) { // We have symbols in that plane.
value_const_iterator VI = PI->second.find(Name);
if (VI != PI->second.end()) // and the name is in our hash table.
return VI->second;
}
return 0;
}
// lookup a type by name - returns null on failure
Type* SymbolTable::lookupType( const std::string& Name ) const {
type_const_iterator TI = tmap.find( Name );
if ( TI != tmap.end() )
return const_cast<Type*>(TI->second);
return 0;
}
// Remove a value
void SymbolTable::remove(Value *N) {
assert(N->hasName() && "Value doesn't have name!");
plane_iterator PI = pmap.find(N->getType());
assert(PI != pmap.end() &&
"Trying to remove a value that doesn't have a type plane yet!");
removeEntry(PI, PI->second.find(N->getName()));
}
/// changeName - Given a value with a non-empty name, remove its existing entry
/// from the symbol table and insert a new one for Name. This is equivalent to
/// doing "remove(V), V->Name = Name, insert(V)", but is faster, and will not
/// temporarily remove the symbol table plane if V is the last value in the
/// symtab with that name (which could invalidate iterators to that plane).
void SymbolTable::changeName(Value *V, const std::string &name) {
assert(!V->getName().empty() && !name.empty() && V->getName() != name &&
"Illegal use of this method!");
plane_iterator PI = pmap.find(V->getType());
assert(PI != pmap.end() && "Value doesn't have an entry in this table?");
ValueMap &VM = PI->second;
value_iterator VI = VM.find(V->getName());
assert(VI != VM.end() && "Value does have an entry in this table?");
// Remove the old entry.
VM.erase(VI);
// See if we can insert the new name.
VI = VM.lower_bound(name);
// Is there a naming conflict?
if (VI != VM.end() && VI->first == name) {
V->Name = getUniqueName(V->getType(), name);
VM.insert(make_pair(V->Name, V));
} else {
V->Name = name;
VM.insert(VI, make_pair(name, V));
}
}
// removeEntry - Remove a value from the symbol table...
Value *SymbolTable::removeEntry(plane_iterator Plane, value_iterator Entry) {
assert(Plane != pmap.end() &&
Entry != Plane->second.end() && "Invalid entry to remove!");
Value *Result = Entry->second;
#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
std::cerr << "Plane Empty: Removing type: "
<< Plane->first->getDescription() << "\n";
#endif
cast<DerivedType>(Plane->first)->removeAbstractTypeUser(this);
}
pmap.erase(Plane);
}
return Result;
}
// remove - Remove a type
void SymbolTable::remove(const Type* Ty ) {
type_iterator TI = this->type_begin();
type_iterator TE = this->type_end();
// Search for the entry
while ( TI != TE && TI->second != Ty )
++TI;
if ( TI != TE )
this->removeEntry( TI );
}
// removeEntry - Remove a type from the symbol table...
Type* SymbolTable::removeEntry(type_iterator Entry) {
assert( Entry != tmap.end() && "Invalid entry to remove!");
const Type* Result = Entry->second;
#if DEBUG_SYMBOL_TABLE
dump();
std::cerr << " Removing Value: " << Result->getName() << "\n";
#endif
tmap.erase(Entry);
// If we are removing an abstract type, remove the symbol table from it's use
// list...
if (Result->isAbstract()) {
#if DEBUG_ABSTYPE
std::cerr << "Removing abstract type from symtab" << Result->getDescription()<<"\n";
#endif
cast<DerivedType>(Result)->removeAbstractTypeUser(this);
}
return const_cast<Type*>(Result);
}
// insertEntry - Insert a value into the symbol table with the specified name.
void SymbolTable::insertEntry(const std::string &Name, const Type *VTy,
Value *V) {
plane_iterator PI = pmap.find(VTy); // Plane iterator
value_iterator VI; // Actual value iterator
ValueMap *VM; // The plane we care about.
#if DEBUG_SYMBOL_TABLE
dump();
std::cerr << " Inserting definition: " << Name << ": "
<< VTy->getDescription() << "\n";
#endif
if (PI == pmap.end()) { // Not in collection yet... insert dummy entry
// Insert a new empty element. I points to the new elements.
VM = &pmap.insert(make_pair(VTy, ValueMap())).first->second;
VI = VM->end();
// 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
std::cerr << "Added abstract type value: " << VTy->getDescription()
<< "\n";
#endif
}
} else {
// Check to see if there is a naming conflict. If so, rename this value!
VM = &PI->second;
VI = VM->lower_bound(Name);
if (VI != VM->end() && VI->first == Name) {
V->Name = getUniqueName(VTy, Name);
VM->insert(make_pair(V->Name, V));
return;
}
}
VM->insert(VI, make_pair(Name, V));
}
// insertEntry - Insert a value into the symbol table with the specified
// name...
//
void SymbolTable::insertEntry(const std::string& Name, const Type* T) {
// Check to see if there is a naming conflict. If so, rename this type!
std::string UniqueName = Name;
if (lookupType(Name))
UniqueName = getUniqueName(T, Name);
#if DEBUG_SYMBOL_TABLE
dump();
std::cerr << " Inserting type: " << UniqueName << ": "
<< T->getDescription() << "\n";
#endif
// Insert the tmap entry
tmap.insert(make_pair(UniqueName, T));
// If we are adding an abstract type, add the symbol table to it's use list.
if (T->isAbstract()) {
cast<DerivedType>(T)->addAbstractTypeUser(this);
#if DEBUG_ABSTYPE
std::cerr << "Added abstract type to ST: " << T->getDescription() << "\n";
#endif
}
}
// Strip the symbol table of its names.
bool SymbolTable::strip() {
bool RemovedSymbol = false;
for (plane_iterator I = pmap.begin(); I != pmap.end();) {
// Removing items from the plane can cause the plane itself to get deleted.
// If this happens, make sure we incremented our plane iterator already!
ValueMap &Plane = (I++)->second;
value_iterator B = Plane.begin(), Bend = Plane.end();
while (B != Bend) { // Found nonempty type plane!
Value *V = B->second;
if (!isa<GlobalValue>(V) || cast<GlobalValue>(V)->hasInternalLinkage()) {
// Set name to "", removing from symbol table!
V->setName("");
RemovedSymbol = true;
}
++B;
}
}
for (type_iterator TI = tmap.begin(); TI != tmap.end(); ) {
const Type* T = (TI++)->second;
remove(T);
RemovedSymbol = true;
}
return RemovedSymbol;
}
// This function is called when one of the types in the type plane are refined
void SymbolTable::refineAbstractType(const DerivedType *OldType,
const Type *NewType) {
// Search to see if we have any values of the type Oldtype. If so, we need to
// move them into the newtype plane...
plane_iterator PI = pmap.find(OldType);
if (PI != pmap.end()) {
// Get a handle to the new type plane...
plane_iterator NewTypeIt = pmap.find(NewType);
if (NewTypeIt == pmap.end()) { // If no plane exists, add one
NewTypeIt = pmap.insert(make_pair(NewType, ValueMap())).first;
if (NewType->isAbstract()) {
cast<DerivedType>(NewType)->addAbstractTypeUser(this);
#if DEBUG_ABSTYPE
std::cerr << "[Added] refined to abstype: " << NewType->getDescription()
<< "\n";
#endif
}
}
ValueMap &NewPlane = NewTypeIt->second;
ValueMap &OldPlane = PI->second;
while (!OldPlane.empty()) {
std::pair<const std::string, Value*> V = *OldPlane.begin();
// Check to see if there is already a value in the symbol table that this
// would collide with.
value_iterator VI = NewPlane.find(V.first);
if (VI != NewPlane.end() && VI->second == V.second) {
// No action
} else if (VI != NewPlane.end()) {
// The only thing we are allowing for now is two external global values
// folded into one.
//
GlobalValue *ExistGV = dyn_cast<GlobalValue>(VI->second);
GlobalValue *NewGV = dyn_cast<GlobalValue>(V.second);
if (ExistGV && NewGV) {
assert((ExistGV->isExternal() || NewGV->isExternal()) &&
"Two planes folded together with overlapping value names!");
// Make sure that ExistGV is the one we want to keep!
if (!NewGV->isExternal())
std::swap(NewGV, ExistGV);
// Ok we have two external global values. Make all uses of the new
// one use the old one...
NewGV->uncheckedReplaceAllUsesWith(ExistGV);
// Update NewGV's name, we're about the remove it from the symbol
// table.
NewGV->Name = "";
// Now we can remove this global from the module entirely...
Module *M = NewGV->getParent();
if (Function *F = dyn_cast<Function>(NewGV))
M->getFunctionList().remove(F);
else
M->getGlobalList().remove(cast<GlobalVariable>(NewGV));
delete NewGV;
} else {
// If they are not global values, they must be just random values who
// happen to conflict now that types have been resolved. If this is
// the case, reinsert the value into the new plane, allowing it to get
// renamed.
assert(V.second->getType() == NewType &&"Type resolution is broken!");
insert(V.second);
}
} 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
std::cerr << "Removing type " << OldType->getDescription() << "\n";
#endif
OldType->removeAbstractTypeUser(this);
// Remove the plane that is no longer used
pmap.erase(PI);
}
// 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
// occurrences, and although we only need to remove one at a time, it's
// faster to remove them all in one pass.
//
for (type_iterator I = type_begin(), E = type_end(); I != E; ++I) {
if (I->second == (Type*)OldType) { // FIXME when Types aren't const.
#if DEBUG_ABSTYPE
std::cerr << "Removing type " << OldType->getDescription() << "\n";
#endif
OldType->removeAbstractTypeUser(this);
I->second = (Type*)NewType; // TODO FIXME when types aren't const
if (NewType->isAbstract()) {
#if DEBUG_ABSTYPE
std::cerr << "Added type " << NewType->getDescription() << "\n";
#endif
cast<DerivedType>(NewType)->addAbstractTypeUser(this);
}
}
}
}
// Handle situation where type becomes Concreate from Abstract
void SymbolTable::typeBecameConcrete(const DerivedType *AbsTy) {
plane_iterator PI = pmap.find(AbsTy);
// If there are any values in the symbol table of this type, then the type
// plane is a use of the abstract type which must be dropped.
if (PI != pmap.end())
AbsTy->removeAbstractTypeUser(this);
// Loop over all of the types in the symbol table, dropping any abstract
// type user entries for AbsTy which occur because there are names for the
// type.
for (type_iterator TI = type_begin(), TE = type_end(); TI != TE; ++TI)
if (TI->second == (Type*)AbsTy) // FIXME when Types aren't const.
AbsTy->removeAbstractTypeUser(this);
}
static void DumpVal(const std::pair<const std::string, Value *> &V) {
std::cerr << " '" << V.first << "' = ";
V.second->dump();
std::cerr << "\n";
}
static void DumpPlane(const std::pair<const Type *,
std::map<const std::string, Value *> >&P){
P.first->dump();
std::cerr << "\n";
for_each(P.second.begin(), P.second.end(), DumpVal);
}
static void DumpTypes(const std::pair<const std::string, const Type*>& T ) {
std::cerr << " '" << T.first << "' = ";
T.second->dump();
std::cerr << "\n";
}
void SymbolTable::dump() const {
std::cerr << "Symbol table dump:\n Plane:";
for_each(pmap.begin(), pmap.end(), DumpPlane);
std::cerr << " Types: ";
for_each(tmap.begin(), tmap.end(), DumpTypes);
}
// vim: sw=2 ai
|