1 //===-- ValueEnumerator.cpp - Number values and types for bitcode writer --===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Chris Lattner and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements the ValueEnumerator class.
12 //===----------------------------------------------------------------------===//
14 #include "ValueEnumerator.h"
15 #include "llvm/Module.h"
16 #include "llvm/TypeSymbolTable.h"
17 #include "llvm/ValueSymbolTable.h"
20 /// ValueEnumerator - Enumerate module-level information.
21 ValueEnumerator::ValueEnumerator(const Module *M) {
22 // Enumerate the global variables.
23 for (Module::const_global_iterator I = M->global_begin(),
24 E = M->global_end(); I != E; ++I)
27 // Enumerate the functions.
28 for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I)
31 // Enumerate the global variable initializers.
32 for (Module::const_global_iterator I = M->global_begin(),
33 E = M->global_end(); I != E; ++I)
34 if (I->hasInitializer())
35 EnumerateValue(I->getInitializer());
37 // FIXME: Implement the 'string constant' optimization.
39 // Enumerate types used by the type symbol table.
40 EnumerateTypeSymbolTable(M->getTypeSymbolTable());
42 // Insert constants that are named at module level into the slot pool so that
43 // the module symbol table can refer to them...
44 EnumerateValueSymbolTable(M->getValueSymbolTable());
46 // Enumerate types used by function bodies.
47 for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) {
48 for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
49 for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E;++I){
50 for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
52 EnumerateType((*OI)->getType());
53 EnumerateType(I->getType());
58 // FIXME: std::partition the type and value tables so that first-class types
59 // come earlier than aggregates. FIXME: Emit a marker into the module
60 // indicating which aggregates types AND values can be dropped form the table.
62 // FIXME: Sort type/value tables by frequency.
64 // FIXME: Sort constants by type to reduce size.
67 /// EnumerateTypeSymbolTable - Insert all of the types in the specified symbol
69 void ValueEnumerator::EnumerateTypeSymbolTable(const TypeSymbolTable &TST) {
70 for (TypeSymbolTable::const_iterator TI = TST.begin(), TE = TST.end();
72 EnumerateType(TI->second);
75 /// EnumerateValueSymbolTable - Insert all of the values in the specified symbol
76 /// table into the values table.
77 void ValueEnumerator::EnumerateValueSymbolTable(const ValueSymbolTable &VST) {
78 for (ValueSymbolTable::const_iterator VI = VST.begin(), VE = VST.end();
80 EnumerateValue(VI->getValue());
83 void ValueEnumerator::EnumerateValue(const Value *V) {
84 assert(V->getType() != Type::VoidTy && "Can't insert void values!");
86 // Check to see if it's already in!
87 unsigned &ValueID = ValueMap[V];
89 // Increment use count.
90 Values[ValueID-1].second++;
95 Values.push_back(std::make_pair(V, 1U));
96 ValueID = Values.size();
98 if (const Constant *C = dyn_cast<Constant>(V)) {
99 if (isa<GlobalValue>(C)) {
100 // Initializers for globals are handled explicitly elsewhere.
102 // This makes sure that if a constant has uses (for example an array of
103 // const ints), that they are inserted also.
104 for (User::const_op_iterator I = C->op_begin(), E = C->op_end();
110 EnumerateType(V->getType());
114 void ValueEnumerator::EnumerateType(const Type *Ty) {
115 unsigned &TypeID = TypeMap[Ty];
118 // If we've already seen this type, just increase its occurrence count.
119 Types[TypeID-1].second++;
123 // First time we saw this type, add it.
124 Types.push_back(std::make_pair(Ty, 1U));
125 TypeID = Types.size();
127 // Enumerate subtypes.
128 for (Type::subtype_iterator I = Ty->subtype_begin(), E = Ty->subtype_end();
137 void SlotCalculator::incorporateFunction(const Function *F) {
138 SC_DEBUG("begin processFunction!\n");
140 // Iterate over function arguments, adding them to the value table...
141 for(Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
143 CreateFunctionValueSlot(I);
145 SC_DEBUG("Inserting Instructions:\n");
147 // Add all of the instructions to the type planes...
148 for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
149 CreateFunctionValueSlot(BB);
150 for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) {
151 if (I->getType() != Type::VoidTy)
152 CreateFunctionValueSlot(I);
156 SC_DEBUG("end processFunction!\n");
159 void SlotCalculator::purgeFunction() {
160 SC_DEBUG("begin purgeFunction!\n");
162 // Next, remove values from existing type planes
163 for (DenseMap<unsigned,unsigned,
164 ModuleLevelDenseMapKeyInfo>::iterator I = ModuleLevel.begin(),
165 E = ModuleLevel.end(); I != E; ++I) {
166 unsigned PlaneNo = I->first;
167 unsigned ModuleLev = I->second;
169 // Pop all function-local values in this type-plane off of Table.
170 TypePlane &Plane = getPlane(PlaneNo);
171 assert(ModuleLev < Plane.size() && "module levels higher than elements?");
172 for (unsigned i = ModuleLev, e = Plane.size(); i != e; ++i) {
173 NodeMap.erase(Plane.back()); // Erase from nodemap
174 Plane.pop_back(); // Shrink plane
180 // Finally, remove any type planes defined by the function...
181 while (Table.size() > NumModuleTypes) {
182 TypePlane &Plane = Table.back();
183 SC_DEBUG("Removing Plane " << (Table.size()-1) << " of size "
184 << Plane.size() << "\n");
185 for (unsigned i = 0, e = Plane.size(); i != e; ++i)
186 NodeMap.erase(Plane[i]); // Erase from nodemap
188 Table.pop_back(); // Nuke the plane, we don't like it.
191 SC_DEBUG("end purgeFunction!\n");
194 inline static bool hasImplicitNull(const Type* Ty) {
195 return Ty != Type::LabelTy && Ty != Type::VoidTy && !isa<OpaqueType>(Ty);
198 void SlotCalculator::CreateFunctionValueSlot(const Value *V) {
199 assert(!NodeMap.count(V) && "Function-local value can't be inserted!");
201 const Type *Ty = V->getType();
202 assert(Ty != Type::VoidTy && "Can't insert void values!");
203 assert(!isa<Constant>(V) && "Not a function-local value!");
205 unsigned TyPlane = getOrCreateTypeSlot(Ty);
206 if (Table.size() <= TyPlane) // Make sure we have the type plane allocated.
207 Table.resize(TyPlane+1, TypePlane());
209 // If this is the first value noticed of this type within this function,
210 // remember the module level for this type plane in ModuleLevel. This reminds
211 // us to remove the values in purgeFunction and tells us how many to remove.
212 if (TyPlane < NumModuleTypes)
213 ModuleLevel.insert(std::make_pair(TyPlane, Table[TyPlane].size()));
215 // If this is the first value to get inserted into the type plane, make sure
216 // to insert the implicit null value.
217 if (Table[TyPlane].empty()) {
218 // Label's and opaque types can't have a null value.
219 if (hasImplicitNull(Ty)) {
220 Value *ZeroInitializer = Constant::getNullValue(Ty);
222 // If we are pushing zeroinit, it will be handled below.
223 if (V != ZeroInitializer) {
224 Table[TyPlane].push_back(ZeroInitializer);
225 NodeMap[ZeroInitializer] = 0;
230 // Insert node into table and NodeMap...
231 NodeMap[V] = Table[TyPlane].size();
232 Table[TyPlane].push_back(V);
234 SC_DEBUG(" Inserting value [" << TyPlane << "] = " << *V << " slot=" <<