1 //===-- SlotCalculator.cpp - Calculate what slots values land in ----------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements a useful analysis step to figure out what numbered slots
11 // values in a program will land in (keeping track of per plane information).
13 // This is used when writing a file to disk, either in bytecode or assembly.
15 //===----------------------------------------------------------------------===//
17 #include "SlotCalculator.h"
18 #include "llvm/Constants.h"
19 #include "llvm/DerivedTypes.h"
20 #include "llvm/Function.h"
21 #include "llvm/InlineAsm.h"
22 #include "llvm/Instructions.h"
23 #include "llvm/Module.h"
24 #include "llvm/TypeSymbolTable.h"
25 #include "llvm/Type.h"
26 #include "llvm/ValueSymbolTable.h"
27 #include "llvm/Analysis/ConstantsScanner.h"
28 #include "llvm/ADT/PostOrderIterator.h"
29 #include "llvm/ADT/STLExtras.h"
35 #include "llvm/Support/Streams.h"
36 #include "llvm/Support/CommandLine.h"
37 static cl::opt<bool> SlotCalculatorDebugOption("scdebug",cl::init(false),
38 cl::desc("Enable SlotCalculator debug output"), cl::Hidden);
39 #define SC_DEBUG(X) if (SlotCalculatorDebugOption) cerr << X
44 void SlotCalculator::insertPrimitives() {
45 // Preload the table with the built-in types. These built-in types are
46 // inserted first to ensure that they have low integer indices which helps to
47 // keep bytecode sizes small. Note that the first group of indices must match
48 // the Type::TypeIDs for the primitive types. After that the integer types are
49 // added, but the order and value is not critical. What is critical is that
50 // the indices of these "well known" slot numbers be properly maintained in
51 // Reader.h which uses them directly to extract values of these types.
52 SC_DEBUG("Inserting primitive types:\n");
53 // See WellKnownTypeSlots in Reader.h
54 insertType(Type::VoidTy, true); // 0: VoidTySlot
55 insertType(Type::FloatTy, true); // 1: FloatTySlot
56 insertType(Type::DoubleTy, true); // 2: DoubleTySlot
57 insertType(Type::LabelTy, true); // 3: LabelTySlot
58 assert(TypeMap.size() == Type::FirstDerivedTyID && "Invalid primitive insert");
59 // Above here *must* correspond 1:1 with the primitive types.
60 insertType(Type::Int1Ty, true); // 4: BoolTySlot
61 insertType(Type::Int8Ty, true); // 5: Int8TySlot
62 insertType(Type::Int16Ty, true); // 6: Int16TySlot
63 insertType(Type::Int32Ty, true); // 7: Int32TySlot
64 insertType(Type::Int64Ty, true); // 8: Int64TySlot
67 SlotCalculator::SlotCalculator(const Module *M ) {
68 ModuleContainsAllFunctionConstants = false;
74 if (M == 0) return; // Empty table...
78 SlotCalculator::SlotCalculator(const Function *M ) {
79 ModuleContainsAllFunctionConstants = false;
80 TheModule = M ? M->getParent() : 0;
84 if (TheModule == 0) return; // Empty table...
86 processModule(); // Process module level stuff
87 incorporateFunction(M); // Start out in incorporated state
90 SlotCalculator::TypePlane &SlotCalculator::getPlane(unsigned Plane) {
91 // Okay we are just returning an entry out of the main Table. Make sure the
92 // plane exists and return it.
93 if (Plane >= Table.size())
94 Table.resize(Plane+1);
98 // processModule - Process all of the module level function declarations and
99 // types that are available.
101 void SlotCalculator::processModule() {
102 SC_DEBUG("begin processModule!\n");
104 // Add all of the global variables to the value table...
106 for (Module::const_global_iterator I = TheModule->global_begin(),
107 E = TheModule->global_end(); I != E; ++I)
110 // Scavenge the types out of the functions, then add the functions themselves
111 // to the value table...
113 for (Module::const_iterator I = TheModule->begin(), E = TheModule->end();
117 // Add all of the module level constants used as initializers
119 for (Module::const_global_iterator I = TheModule->global_begin(),
120 E = TheModule->global_end(); I != E; ++I)
121 if (I->hasInitializer())
122 getOrCreateSlot(I->getInitializer());
124 // Now that all global constants have been added, rearrange constant planes
125 // that contain constant strings so that the strings occur at the start of the
126 // plane, not somewhere in the middle.
128 for (unsigned plane = 0, e = Table.size(); plane != e; ++plane) {
129 if (const ArrayType *AT = dyn_cast<ArrayType>(Types[plane]))
130 if (AT->getElementType() == Type::Int8Ty) {
131 TypePlane &Plane = Table[plane];
132 unsigned FirstNonStringID = 0;
133 for (unsigned i = 0, e = Plane.size(); i != e; ++i)
134 if (isa<ConstantAggregateZero>(Plane[i]) ||
135 (isa<ConstantArray>(Plane[i]) &&
136 cast<ConstantArray>(Plane[i])->isString())) {
137 // Check to see if we have to shuffle this string around. If not,
138 // don't do anything.
139 if (i != FirstNonStringID) {
140 // Swap the plane entries....
141 std::swap(Plane[i], Plane[FirstNonStringID]);
143 // Keep the NodeMap up to date.
144 NodeMap[Plane[i]] = i;
145 NodeMap[Plane[FirstNonStringID]] = FirstNonStringID;
152 // Scan all of the functions for their constants, which allows us to emit
153 // more compact modules. This is optional, and is just used to compactify
154 // the constants used by different functions together.
156 // This functionality tends to produce smaller bytecode files. This should
157 // not be used in the future by clients that want to, for example, build and
158 // emit functions on the fly. For now, however, it is unconditionally
160 ModuleContainsAllFunctionConstants = true;
162 SC_DEBUG("Inserting function constants:\n");
163 for (Module::const_iterator F = TheModule->begin(), E = TheModule->end();
165 for (const_inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
166 for (User::const_op_iterator OI = I->op_begin(), E = I->op_end();
168 if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) ||
170 getOrCreateSlot(*OI);
172 getOrCreateSlot(I->getType());
174 processSymbolTableConstants(&F->getValueSymbolTable());
177 // Insert constants that are named at module level into the slot pool so that
178 // the module symbol table can refer to them...
179 SC_DEBUG("Inserting SymbolTable values:\n");
180 processTypeSymbolTable(&TheModule->getTypeSymbolTable());
181 processValueSymbolTable(&TheModule->getValueSymbolTable());
183 // Now that we have collected together all of the information relevant to the
184 // module, compactify the type table if it is particularly big and outputting
185 // a bytecode file. The basic problem we run into is that some programs have
186 // a large number of types, which causes the type field to overflow its size,
187 // which causes instructions to explode in size (particularly call
188 // instructions). To avoid this behavior, we "sort" the type table so that
189 // all non-value types are pushed to the end of the type table, giving nice
190 // low numbers to the types that can be used by instructions, thus reducing
191 // the amount of explodage we suffer.
192 if (Types.size() >= 64) {
193 unsigned FirstNonValueTypeID = 0;
194 for (unsigned i = 0, e = Types.size(); i != e; ++i)
195 if (Types[i]->isFirstClassType() || Types[i]->isPrimitiveType()) {
196 // Check to see if we have to shuffle this type around. If not, don't
198 if (i != FirstNonValueTypeID) {
199 // Swap the type ID's.
200 std::swap(Types[i], Types[FirstNonValueTypeID]);
202 // Keep the TypeMap up to date.
203 TypeMap[Types[i]] = i;
204 TypeMap[Types[FirstNonValueTypeID]] = FirstNonValueTypeID;
206 // When we move a type, make sure to move its value plane as needed.
207 if (Table.size() > FirstNonValueTypeID) {
208 if (Table.size() <= i) Table.resize(i+1);
209 std::swap(Table[i], Table[FirstNonValueTypeID]);
212 ++FirstNonValueTypeID;
216 SC_DEBUG("end processModule!\n");
219 // processTypeSymbolTable - Insert all of the type sin the specified symbol
221 void SlotCalculator::processTypeSymbolTable(const TypeSymbolTable *TST) {
222 for (TypeSymbolTable::const_iterator TI = TST->begin(), TE = TST->end();
224 getOrCreateSlot(TI->second);
227 // processSymbolTable - Insert all of the values in the specified symbol table
228 // into the values table...
230 void SlotCalculator::processValueSymbolTable(const ValueSymbolTable *VST) {
231 for (ValueSymbolTable::const_iterator VI = VST->begin(), VE = VST->end();
233 getOrCreateSlot(VI->second);
236 void SlotCalculator::processSymbolTableConstants(const ValueSymbolTable *VST) {
237 // Now do the constant values in all planes
238 for (ValueSymbolTable::const_iterator VI = VST->begin(), VE = VST->end();
240 if (isa<Constant>(VI->second) && !isa<GlobalValue>(VI->second))
241 getOrCreateSlot(VI->second);
245 void SlotCalculator::incorporateFunction(const Function *F) {
246 assert((ModuleLevel.empty() ||
247 ModuleTypeLevel == 0) && "Module already incorporated!");
249 SC_DEBUG("begin processFunction!\n");
251 // Update the ModuleLevel entries to be accurate.
252 ModuleLevel.resize(getNumPlanes());
253 for (unsigned i = 0, e = getNumPlanes(); i != e; ++i)
254 ModuleLevel[i] = getPlane(i).size();
255 ModuleTypeLevel = Types.size();
257 // Iterate over function arguments, adding them to the value table...
258 for(Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; ++I)
261 if (!ModuleContainsAllFunctionConstants) {
262 // Iterate over all of the instructions in the function, looking for
263 // constant values that are referenced. Add these to the value pools
264 // before any nonconstant values. This will be turned into the constant
265 // pool for the bytecode writer.
268 // Emit all of the constants that are being used by the instructions in
270 for (constant_iterator CI = constant_begin(F), CE = constant_end(F);
272 getOrCreateSlot(*CI);
274 // If there is a symbol table, it is possible that the user has names for
275 // constants that are not being used. In this case, we will have problems
276 // if we don't emit the constants now, because otherwise we will get
277 // symbol table references to constants not in the output. Scan for these
280 processSymbolTableConstants(&F->getValueSymbolTable());
283 SC_DEBUG("Inserting Instructions:\n");
285 // Add all of the instructions to the type planes...
286 for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
288 for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) {
293 SC_DEBUG("end processFunction!\n");
296 void SlotCalculator::purgeFunction() {
297 assert((ModuleLevel.size() != 0 ||
298 ModuleTypeLevel != 0) && "Module not incorporated!");
299 unsigned NumModuleTypes = ModuleLevel.size();
301 SC_DEBUG("begin purgeFunction!\n");
303 // Next, remove values from existing type planes
304 for (unsigned i = 0; i != NumModuleTypes; ++i) {
305 // Size of plane before function came
306 unsigned ModuleLev = getModuleLevel(i);
307 assert(int(ModuleLev) >= 0 && "BAD!");
309 TypePlane &Plane = getPlane(i);
311 assert(ModuleLev <= Plane.size() && "module levels higher than elements?");
312 while (Plane.size() != ModuleLev) {
313 assert(!isa<GlobalValue>(Plane.back()) &&
314 "Functions cannot define globals!");
315 NodeMap.erase(Plane.back()); // Erase from nodemap
316 Plane.pop_back(); // Shrink plane
320 // We don't need this state anymore, free it up.
324 // Finally, remove any type planes defined by the function...
325 while (Table.size() > NumModuleTypes) {
326 TypePlane &Plane = Table.back();
327 SC_DEBUG("Removing Plane " << (Table.size()-1) << " of size "
328 << Plane.size() << "\n");
329 while (Plane.size()) {
330 assert(!isa<GlobalValue>(Plane.back()) &&
331 "Functions cannot define globals!");
332 NodeMap.erase(Plane.back()); // Erase from nodemap
333 Plane.pop_back(); // Shrink plane
336 Table.pop_back(); // Nuke the plane, we don't like it.
339 SC_DEBUG("end purgeFunction!\n");
342 static inline bool hasNullValue(const Type *Ty) {
343 return Ty != Type::LabelTy && Ty != Type::VoidTy && !isa<OpaqueType>(Ty);
347 int SlotCalculator::getSlot(const Value *V) const {
348 std::map<const Value*, unsigned>::const_iterator I = NodeMap.find(V);
349 if (I != NodeMap.end())
350 return (int)I->second;
355 int SlotCalculator::getSlot(const Type*T) const {
356 std::map<const Type*, unsigned>::const_iterator I = TypeMap.find(T);
357 if (I != TypeMap.end())
358 return (int)I->second;
363 int SlotCalculator::getOrCreateSlot(const Value *V) {
364 if (V->getType() == Type::VoidTy) return -1;
366 int SlotNo = getSlot(V); // Check to see if it's already in!
367 if (SlotNo != -1) return SlotNo;
369 if (const GlobalValue *GV = dyn_cast<GlobalValue>(V))
370 assert(GV->getParent() != 0 && "Global not embedded into a module!");
372 if (!isa<GlobalValue>(V)) // Initializers for globals are handled explicitly
373 if (const Constant *C = dyn_cast<Constant>(V)) {
375 // Do not index the characters that make up constant strings. We emit
376 // constant strings as special entities that don't require their
377 // individual characters to be emitted.
378 if (!isa<ConstantArray>(C) || !cast<ConstantArray>(C)->isString()) {
379 // This makes sure that if a constant has uses (for example an array of
380 // const ints), that they are inserted also.
382 for (User::const_op_iterator I = C->op_begin(), E = C->op_end();
386 assert(ModuleLevel.empty() &&
387 "How can a constant string be directly accessed in a function?");
388 // Otherwise, if we are emitting a bytecode file and this IS a string,
390 if (!C->isNullValue())
391 ConstantStrings.push_back(cast<ConstantArray>(C));
395 return insertValue(V);
398 int SlotCalculator::getOrCreateSlot(const Type* T) {
399 int SlotNo = getSlot(T); // Check to see if it's already in!
400 if (SlotNo != -1) return SlotNo;
401 return insertType(T);
404 int SlotCalculator::insertValue(const Value *D, bool dontIgnore) {
405 assert(D && "Can't insert a null value!");
406 assert(getSlot(D) == -1 && "Value is already in the table!");
408 // If this node does not contribute to a plane, or if the node has a
409 // name and we don't want names, then ignore the silly node... Note that types
410 // do need slot numbers so that we can keep track of where other values land.
412 if (!dontIgnore) // Don't ignore nonignorables!
413 if (D->getType() == Type::VoidTy ) { // Ignore void type nodes
414 SC_DEBUG("ignored value " << *D << "\n");
415 return -1; // We do need types unconditionally though
418 // Okay, everything is happy, actually insert the silly value now...
419 return doInsertValue(D);
422 int SlotCalculator::insertType(const Type *Ty, bool dontIgnore) {
423 assert(Ty && "Can't insert a null type!");
424 assert(getSlot(Ty) == -1 && "Type is already in the table!");
426 // Insert the current type before any subtypes. This is important because
427 // recursive types elements are inserted in a bottom up order. Changing
428 // this here can break things. For example:
430 // global { \2 * } { { \2 }* null }
432 int ResultSlot = doInsertType(Ty);
433 SC_DEBUG(" Inserted type: " << Ty->getDescription() << " slot=" <<
436 // Loop over any contained types in the definition... in post
438 for (po_iterator<const Type*> I = po_begin(Ty), E = po_end(Ty);
441 const Type *SubTy = *I;
442 // If we haven't seen this sub type before, add it to our type table!
443 if (getSlot(SubTy) == -1) {
444 SC_DEBUG(" Inserting subtype: " << SubTy->getDescription() << "\n");
446 SC_DEBUG(" Inserted subtype: " << SubTy->getDescription() << "\n");
453 // doInsertValue - This is a small helper function to be called only
456 int SlotCalculator::doInsertValue(const Value *D) {
457 const Type *Typ = D->getType();
460 // Used for debugging DefSlot=-1 assertion...
461 //if (Typ == Type::TypeTy)
462 // llvm_cerr << "Inserting type '"<<cast<Type>(D)->getDescription() <<"'!\n";
464 if (Typ->isDerivedType()) {
465 int ValSlot = getSlot(Typ);
466 if (ValSlot == -1) { // Have we already entered this type?
467 // Nope, this is the first we have seen the type, process it.
468 ValSlot = insertType(Typ, true);
469 assert(ValSlot != -1 && "ProcessType returned -1 for a type?");
471 Ty = (unsigned)ValSlot;
473 Ty = Typ->getTypeID();
476 if (Table.size() <= Ty) // Make sure we have the type plane allocated...
477 Table.resize(Ty+1, TypePlane());
479 // If this is the first value to get inserted into the type plane, make sure
480 // to insert the implicit null value...
481 if (Table[Ty].empty() && hasNullValue(Typ)) {
482 Value *ZeroInitializer = Constant::getNullValue(Typ);
484 // If we are pushing zeroinit, it will be handled below.
485 if (D != ZeroInitializer) {
486 Table[Ty].push_back(ZeroInitializer);
487 NodeMap[ZeroInitializer] = 0;
491 // Insert node into table and NodeMap...
492 unsigned DestSlot = NodeMap[D] = Table[Ty].size();
493 Table[Ty].push_back(D);
495 SC_DEBUG(" Inserting value [" << Ty << "] = " << *D << " slot=" <<
497 // G = Global, C = Constant, T = Type, F = Function, o = other
498 SC_DEBUG((isa<GlobalVariable>(D) ? "G" : (isa<Constant>(D) ? "C" :
499 (isa<Function>(D) ? "F" : "o"))));
501 return (int)DestSlot;
504 // doInsertType - This is a small helper function to be called only
507 int SlotCalculator::doInsertType(const Type *Ty) {
509 // Insert node into table and NodeMap...
510 unsigned DestSlot = TypeMap[Ty] = Types.size();
513 SC_DEBUG(" Inserting type [" << DestSlot << "] = " << *Ty << "\n" );
514 return (int)DestSlot;