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/SymbolTable.h"
25 #include "llvm/TypeSymbolTable.h"
26 #include "llvm/Type.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 *ST) {
222 for (TypeSymbolTable::const_iterator TI = ST->begin(), TE = ST->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 SymbolTable *ST) {
231 for (SymbolTable::plane_const_iterator PI = ST->plane_begin(),
232 PE = ST->plane_end(); PI != PE; ++PI)
233 for (SymbolTable::value_const_iterator VI = PI->second.begin(),
234 VE = PI->second.end(); VI != VE; ++VI)
235 getOrCreateSlot(VI->second);
238 void SlotCalculator::processSymbolTableConstants(const SymbolTable *ST) {
239 // Now do the constant values in all planes
240 for (SymbolTable::plane_const_iterator PI = ST->plane_begin(),
241 PE = ST->plane_end(); PI != PE; ++PI)
242 for (SymbolTable::value_const_iterator VI = PI->second.begin(),
243 VE = PI->second.end(); VI != VE; ++VI)
244 if (isa<Constant>(VI->second) &&
245 !isa<GlobalValue>(VI->second))
246 getOrCreateSlot(VI->second);
250 void SlotCalculator::incorporateFunction(const Function *F) {
251 assert((ModuleLevel.empty() ||
252 ModuleTypeLevel == 0) && "Module already incorporated!");
254 SC_DEBUG("begin processFunction!\n");
256 // Update the ModuleLevel entries to be accurate.
257 ModuleLevel.resize(getNumPlanes());
258 for (unsigned i = 0, e = getNumPlanes(); i != e; ++i)
259 ModuleLevel[i] = getPlane(i).size();
260 ModuleTypeLevel = Types.size();
262 // Iterate over function arguments, adding them to the value table...
263 for(Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; ++I)
266 if (!ModuleContainsAllFunctionConstants) {
267 // Iterate over all of the instructions in the function, looking for
268 // constant values that are referenced. Add these to the value pools
269 // before any nonconstant values. This will be turned into the constant
270 // pool for the bytecode writer.
273 // Emit all of the constants that are being used by the instructions in
275 for (constant_iterator CI = constant_begin(F), CE = constant_end(F);
277 getOrCreateSlot(*CI);
279 // If there is a symbol table, it is possible that the user has names for
280 // constants that are not being used. In this case, we will have problems
281 // if we don't emit the constants now, because otherwise we will get
282 // symbol table references to constants not in the output. Scan for these
285 processSymbolTableConstants(&F->getValueSymbolTable());
288 SC_DEBUG("Inserting Instructions:\n");
290 // Add all of the instructions to the type planes...
291 for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
293 for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) {
298 SC_DEBUG("end processFunction!\n");
301 void SlotCalculator::purgeFunction() {
302 assert((ModuleLevel.size() != 0 ||
303 ModuleTypeLevel != 0) && "Module not incorporated!");
304 unsigned NumModuleTypes = ModuleLevel.size();
306 SC_DEBUG("begin purgeFunction!\n");
308 // Next, remove values from existing type planes
309 for (unsigned i = 0; i != NumModuleTypes; ++i) {
310 // Size of plane before function came
311 unsigned ModuleLev = getModuleLevel(i);
312 assert(int(ModuleLev) >= 0 && "BAD!");
314 TypePlane &Plane = getPlane(i);
316 assert(ModuleLev <= Plane.size() && "module levels higher than elements?");
317 while (Plane.size() != ModuleLev) {
318 assert(!isa<GlobalValue>(Plane.back()) &&
319 "Functions cannot define globals!");
320 NodeMap.erase(Plane.back()); // Erase from nodemap
321 Plane.pop_back(); // Shrink plane
325 // We don't need this state anymore, free it up.
329 // Finally, remove any type planes defined by the function...
330 while (Table.size() > NumModuleTypes) {
331 TypePlane &Plane = Table.back();
332 SC_DEBUG("Removing Plane " << (Table.size()-1) << " of size "
333 << Plane.size() << "\n");
334 while (Plane.size()) {
335 assert(!isa<GlobalValue>(Plane.back()) &&
336 "Functions cannot define globals!");
337 NodeMap.erase(Plane.back()); // Erase from nodemap
338 Plane.pop_back(); // Shrink plane
341 Table.pop_back(); // Nuke the plane, we don't like it.
344 SC_DEBUG("end purgeFunction!\n");
347 static inline bool hasNullValue(const Type *Ty) {
348 return Ty != Type::LabelTy && Ty != Type::VoidTy && !isa<OpaqueType>(Ty);
352 int SlotCalculator::getSlot(const Value *V) const {
353 std::map<const Value*, unsigned>::const_iterator I = NodeMap.find(V);
354 if (I != NodeMap.end())
355 return (int)I->second;
360 int SlotCalculator::getSlot(const Type*T) const {
361 std::map<const Type*, unsigned>::const_iterator I = TypeMap.find(T);
362 if (I != TypeMap.end())
363 return (int)I->second;
368 int SlotCalculator::getOrCreateSlot(const Value *V) {
369 if (V->getType() == Type::VoidTy) return -1;
371 int SlotNo = getSlot(V); // Check to see if it's already in!
372 if (SlotNo != -1) return SlotNo;
374 if (const GlobalValue *GV = dyn_cast<GlobalValue>(V))
375 assert(GV->getParent() != 0 && "Global not embedded into a module!");
377 if (!isa<GlobalValue>(V)) // Initializers for globals are handled explicitly
378 if (const Constant *C = dyn_cast<Constant>(V)) {
380 // Do not index the characters that make up constant strings. We emit
381 // constant strings as special entities that don't require their
382 // individual characters to be emitted.
383 if (!isa<ConstantArray>(C) || !cast<ConstantArray>(C)->isString()) {
384 // This makes sure that if a constant has uses (for example an array of
385 // const ints), that they are inserted also.
387 for (User::const_op_iterator I = C->op_begin(), E = C->op_end();
391 assert(ModuleLevel.empty() &&
392 "How can a constant string be directly accessed in a function?");
393 // Otherwise, if we are emitting a bytecode file and this IS a string,
395 if (!C->isNullValue())
396 ConstantStrings.push_back(cast<ConstantArray>(C));
400 return insertValue(V);
403 int SlotCalculator::getOrCreateSlot(const Type* T) {
404 int SlotNo = getSlot(T); // Check to see if it's already in!
405 if (SlotNo != -1) return SlotNo;
406 return insertType(T);
409 int SlotCalculator::insertValue(const Value *D, bool dontIgnore) {
410 assert(D && "Can't insert a null value!");
411 assert(getSlot(D) == -1 && "Value is already in the table!");
413 // If this node does not contribute to a plane, or if the node has a
414 // name and we don't want names, then ignore the silly node... Note that types
415 // do need slot numbers so that we can keep track of where other values land.
417 if (!dontIgnore) // Don't ignore nonignorables!
418 if (D->getType() == Type::VoidTy ) { // Ignore void type nodes
419 SC_DEBUG("ignored value " << *D << "\n");
420 return -1; // We do need types unconditionally though
423 // Okay, everything is happy, actually insert the silly value now...
424 return doInsertValue(D);
427 int SlotCalculator::insertType(const Type *Ty, bool dontIgnore) {
428 assert(Ty && "Can't insert a null type!");
429 assert(getSlot(Ty) == -1 && "Type is already in the table!");
431 // Insert the current type before any subtypes. This is important because
432 // recursive types elements are inserted in a bottom up order. Changing
433 // this here can break things. For example:
435 // global { \2 * } { { \2 }* null }
437 int ResultSlot = doInsertType(Ty);
438 SC_DEBUG(" Inserted type: " << Ty->getDescription() << " slot=" <<
441 // Loop over any contained types in the definition... in post
443 for (po_iterator<const Type*> I = po_begin(Ty), E = po_end(Ty);
446 const Type *SubTy = *I;
447 // If we haven't seen this sub type before, add it to our type table!
448 if (getSlot(SubTy) == -1) {
449 SC_DEBUG(" Inserting subtype: " << SubTy->getDescription() << "\n");
451 SC_DEBUG(" Inserted subtype: " << SubTy->getDescription() << "\n");
458 // doInsertValue - This is a small helper function to be called only
461 int SlotCalculator::doInsertValue(const Value *D) {
462 const Type *Typ = D->getType();
465 // Used for debugging DefSlot=-1 assertion...
466 //if (Typ == Type::TypeTy)
467 // llvm_cerr << "Inserting type '"<<cast<Type>(D)->getDescription() <<"'!\n";
469 if (Typ->isDerivedType()) {
470 int ValSlot = getSlot(Typ);
471 if (ValSlot == -1) { // Have we already entered this type?
472 // Nope, this is the first we have seen the type, process it.
473 ValSlot = insertType(Typ, true);
474 assert(ValSlot != -1 && "ProcessType returned -1 for a type?");
476 Ty = (unsigned)ValSlot;
478 Ty = Typ->getTypeID();
481 if (Table.size() <= Ty) // Make sure we have the type plane allocated...
482 Table.resize(Ty+1, TypePlane());
484 // If this is the first value to get inserted into the type plane, make sure
485 // to insert the implicit null value...
486 if (Table[Ty].empty() && hasNullValue(Typ)) {
487 Value *ZeroInitializer = Constant::getNullValue(Typ);
489 // If we are pushing zeroinit, it will be handled below.
490 if (D != ZeroInitializer) {
491 Table[Ty].push_back(ZeroInitializer);
492 NodeMap[ZeroInitializer] = 0;
496 // Insert node into table and NodeMap...
497 unsigned DestSlot = NodeMap[D] = Table[Ty].size();
498 Table[Ty].push_back(D);
500 SC_DEBUG(" Inserting value [" << Ty << "] = " << *D << " slot=" <<
502 // G = Global, C = Constant, T = Type, F = Function, o = other
503 SC_DEBUG((isa<GlobalVariable>(D) ? "G" : (isa<Constant>(D) ? "C" :
504 (isa<Function>(D) ? "F" : "o"))));
506 return (int)DestSlot;
509 // doInsertType - This is a small helper function to be called only
512 int SlotCalculator::doInsertType(const Type *Ty) {
514 // Insert node into table and NodeMap...
515 unsigned DestSlot = TypeMap[Ty] = Types.size();
518 SC_DEBUG(" Inserting type [" << DestSlot << "] = " << *Ty << "\n" );
519 return (int)DestSlot;