LLVM API Documentation

SlotCalculator.cpp

Go to the documentation of this file.
00001 //===-- SlotCalculator.cpp - Calculate what slots values land in ----------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements a useful analysis step to figure out what numbered slots
00011 // values in a program will land in (keeping track of per plane information).
00012 //
00013 // This is used when writing a file to disk, either in bytecode or assembly.
00014 //
00015 //===----------------------------------------------------------------------===//
00016 
00017 #include "SlotCalculator.h"
00018 #include "llvm/Constants.h"
00019 #include "llvm/DerivedTypes.h"
00020 #include "llvm/Function.h"
00021 #include "llvm/InlineAsm.h"
00022 #include "llvm/Instructions.h"
00023 #include "llvm/Module.h"
00024 #include "llvm/SymbolTable.h"
00025 #include "llvm/Type.h"
00026 #include "llvm/Analysis/ConstantsScanner.h"
00027 #include "llvm/ADT/PostOrderIterator.h"
00028 #include "llvm/ADT/STLExtras.h"
00029 #include <algorithm>
00030 #include <functional>
00031 using namespace llvm;
00032 
00033 #if 0
00034 #include <iostream>
00035 #define SC_DEBUG(X) std::cerr << X
00036 #else
00037 #define SC_DEBUG(X)
00038 #endif
00039 
00040 SlotCalculator::SlotCalculator(const Module *M ) {
00041   ModuleContainsAllFunctionConstants = false;
00042   ModuleTypeLevel = 0;
00043   TheModule = M;
00044 
00045   // Preload table... Make sure that all of the primitive types are in the table
00046   // and that their Primitive ID is equal to their slot #
00047   //
00048   SC_DEBUG("Inserting primitive types:\n");
00049   for (unsigned i = 0; i < Type::FirstDerivedTyID; ++i) {
00050     assert(Type::getPrimitiveType((Type::TypeID)i));
00051     insertType(Type::getPrimitiveType((Type::TypeID)i), true);
00052   }
00053 
00054   if (M == 0) return;   // Empty table...
00055   processModule();
00056 }
00057 
00058 SlotCalculator::SlotCalculator(const Function *M ) {
00059   ModuleContainsAllFunctionConstants = false;
00060   TheModule = M ? M->getParent() : 0;
00061 
00062   // Preload table... Make sure that all of the primitive types are in the table
00063   // and that their Primitive ID is equal to their slot #
00064   //
00065   SC_DEBUG("Inserting primitive types:\n");
00066   for (unsigned i = 0; i < Type::FirstDerivedTyID; ++i) {
00067     assert(Type::getPrimitiveType((Type::TypeID)i));
00068     insertType(Type::getPrimitiveType((Type::TypeID)i), true);
00069   }
00070 
00071   if (TheModule == 0) return;   // Empty table...
00072 
00073   processModule();              // Process module level stuff
00074   incorporateFunction(M);       // Start out in incorporated state
00075 }
00076 
00077 unsigned SlotCalculator::getGlobalSlot(const Value *V) const {
00078   assert(!CompactionTable.empty() &&
00079          "This method can only be used when compaction is enabled!");
00080   std::map<const Value*, unsigned>::const_iterator I = NodeMap.find(V);
00081   assert(I != NodeMap.end() && "Didn't find global slot entry!");
00082   return I->second;
00083 }
00084 
00085 unsigned SlotCalculator::getGlobalSlot(const Type* T) const {
00086   std::map<const Type*, unsigned>::const_iterator I = TypeMap.find(T);
00087   assert(I != TypeMap.end() && "Didn't find global slot entry!");
00088   return I->second;
00089 }
00090 
00091 SlotCalculator::TypePlane &SlotCalculator::getPlane(unsigned Plane) {
00092   if (CompactionTable.empty()) {                // No compaction table active?
00093     // fall out
00094   } else if (!CompactionTable[Plane].empty()) { // Compaction table active.
00095     assert(Plane < CompactionTable.size());
00096     return CompactionTable[Plane];
00097   } else {
00098     // Final case: compaction table active, but this plane is not
00099     // compactified.  If the type plane is compactified, unmap back to the
00100     // global type plane corresponding to "Plane".
00101     if (!CompactionTypes.empty()) {
00102       const Type *Ty = CompactionTypes[Plane];
00103       TypeMapType::iterator It = TypeMap.find(Ty);
00104       assert(It != TypeMap.end() && "Type not in global constant map?");
00105       Plane = It->second;
00106     }
00107   }
00108 
00109   // Okay we are just returning an entry out of the main Table.  Make sure the
00110   // plane exists and return it.
00111   if (Plane >= Table.size())
00112     Table.resize(Plane+1);
00113   return Table[Plane];
00114 }
00115 
00116 // processModule - Process all of the module level function declarations and
00117 // types that are available.
00118 //
00119 void SlotCalculator::processModule() {
00120   SC_DEBUG("begin processModule!\n");
00121 
00122   // Add all of the global variables to the value table...
00123   //
00124   for (Module::const_global_iterator I = TheModule->global_begin(),
00125          E = TheModule->global_end(); I != E; ++I)
00126     getOrCreateSlot(I);
00127 
00128   // Scavenge the types out of the functions, then add the functions themselves
00129   // to the value table...
00130   //
00131   for (Module::const_iterator I = TheModule->begin(), E = TheModule->end();
00132        I != E; ++I)
00133     getOrCreateSlot(I);
00134 
00135   // Add all of the module level constants used as initializers
00136   //
00137   for (Module::const_global_iterator I = TheModule->global_begin(),
00138          E = TheModule->global_end(); I != E; ++I)
00139     if (I->hasInitializer())
00140       getOrCreateSlot(I->getInitializer());
00141 
00142   // Now that all global constants have been added, rearrange constant planes
00143   // that contain constant strings so that the strings occur at the start of the
00144   // plane, not somewhere in the middle.
00145   //
00146   for (unsigned plane = 0, e = Table.size(); plane != e; ++plane) {
00147     if (const ArrayType *AT = dyn_cast<ArrayType>(Types[plane]))
00148       if (AT->getElementType() == Type::SByteTy ||
00149           AT->getElementType() == Type::UByteTy) {
00150         TypePlane &Plane = Table[plane];
00151         unsigned FirstNonStringID = 0;
00152         for (unsigned i = 0, e = Plane.size(); i != e; ++i)
00153           if (isa<ConstantAggregateZero>(Plane[i]) ||
00154               (isa<ConstantArray>(Plane[i]) &&
00155                cast<ConstantArray>(Plane[i])->isString())) {
00156             // Check to see if we have to shuffle this string around.  If not,
00157             // don't do anything.
00158             if (i != FirstNonStringID) {
00159               // Swap the plane entries....
00160               std::swap(Plane[i], Plane[FirstNonStringID]);
00161 
00162               // Keep the NodeMap up to date.
00163               NodeMap[Plane[i]] = i;
00164               NodeMap[Plane[FirstNonStringID]] = FirstNonStringID;
00165             }
00166             ++FirstNonStringID;
00167           }
00168       }
00169   }
00170 
00171   // Scan all of the functions for their constants, which allows us to emit
00172   // more compact modules.  This is optional, and is just used to compactify
00173   // the constants used by different functions together.
00174   //
00175   // This functionality tends to produce smaller bytecode files.  This should
00176   // not be used in the future by clients that want to, for example, build and
00177   // emit functions on the fly.  For now, however, it is unconditionally
00178   // enabled.
00179   ModuleContainsAllFunctionConstants = true;
00180 
00181   SC_DEBUG("Inserting function constants:\n");
00182   for (Module::const_iterator F = TheModule->begin(), E = TheModule->end();
00183        F != E; ++F) {
00184     for (const_inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
00185       for (User::const_op_iterator OI = I->op_begin(), E = I->op_end(); 
00186            OI != E; ++OI) {
00187         if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) ||
00188             isa<InlineAsm>(*OI))
00189           getOrCreateSlot(*OI);
00190       }
00191       getOrCreateSlot(I->getType());
00192     }
00193     processSymbolTableConstants(&F->getSymbolTable());
00194   }
00195 
00196   // Insert constants that are named at module level into the slot pool so that
00197   // the module symbol table can refer to them...
00198   SC_DEBUG("Inserting SymbolTable values:\n");
00199   processSymbolTable(&TheModule->getSymbolTable());
00200 
00201   // Now that we have collected together all of the information relevant to the
00202   // module, compactify the type table if it is particularly big and outputting
00203   // a bytecode file.  The basic problem we run into is that some programs have
00204   // a large number of types, which causes the type field to overflow its size,
00205   // which causes instructions to explode in size (particularly call
00206   // instructions).  To avoid this behavior, we "sort" the type table so that
00207   // all non-value types are pushed to the end of the type table, giving nice
00208   // low numbers to the types that can be used by instructions, thus reducing
00209   // the amount of explodage we suffer.
00210   if (Types.size() >= 64) {
00211     unsigned FirstNonValueTypeID = 0;
00212     for (unsigned i = 0, e = Types.size(); i != e; ++i)
00213       if (Types[i]->isFirstClassType() || Types[i]->isPrimitiveType()) {
00214         // Check to see if we have to shuffle this type around.  If not, don't
00215         // do anything.
00216         if (i != FirstNonValueTypeID) {
00217           // Swap the type ID's.
00218           std::swap(Types[i], Types[FirstNonValueTypeID]);
00219 
00220           // Keep the TypeMap up to date.
00221           TypeMap[Types[i]] = i;
00222           TypeMap[Types[FirstNonValueTypeID]] = FirstNonValueTypeID;
00223 
00224           // When we move a type, make sure to move its value plane as needed.
00225           if (Table.size() > FirstNonValueTypeID) {
00226             if (Table.size() <= i) Table.resize(i+1);
00227             std::swap(Table[i], Table[FirstNonValueTypeID]);
00228           }
00229         }
00230         ++FirstNonValueTypeID;
00231       }
00232   }
00233 
00234   SC_DEBUG("end processModule!\n");
00235 }
00236 
00237 // processSymbolTable - Insert all of the values in the specified symbol table
00238 // into the values table...
00239 //
00240 void SlotCalculator::processSymbolTable(const SymbolTable *ST) {
00241   // Do the types first.
00242   for (SymbolTable::type_const_iterator TI = ST->type_begin(),
00243        TE = ST->type_end(); TI != TE; ++TI )
00244     getOrCreateSlot(TI->second);
00245 
00246   // Now do the values.
00247   for (SymbolTable::plane_const_iterator PI = ST->plane_begin(),
00248        PE = ST->plane_end(); PI != PE; ++PI)
00249     for (SymbolTable::value_const_iterator VI = PI->second.begin(),
00250            VE = PI->second.end(); VI != VE; ++VI)
00251       getOrCreateSlot(VI->second);
00252 }
00253 
00254 void SlotCalculator::processSymbolTableConstants(const SymbolTable *ST) {
00255   // Do the types first
00256   for (SymbolTable::type_const_iterator TI = ST->type_begin(),
00257        TE = ST->type_end(); TI != TE; ++TI )
00258     getOrCreateSlot(TI->second);
00259 
00260   // Now do the constant values in all planes
00261   for (SymbolTable::plane_const_iterator PI = ST->plane_begin(),
00262        PE = ST->plane_end(); PI != PE; ++PI)
00263     for (SymbolTable::value_const_iterator VI = PI->second.begin(),
00264            VE = PI->second.end(); VI != VE; ++VI)
00265       if (isa<Constant>(VI->second) &&
00266           !isa<GlobalValue>(VI->second))
00267         getOrCreateSlot(VI->second);
00268 }
00269 
00270 
00271 void SlotCalculator::incorporateFunction(const Function *F) {
00272   assert((ModuleLevel.size() == 0 ||
00273           ModuleTypeLevel == 0) && "Module already incorporated!");
00274 
00275   SC_DEBUG("begin processFunction!\n");
00276 
00277   // If we emitted all of the function constants, build a compaction table.
00278   if ( ModuleContainsAllFunctionConstants)
00279     buildCompactionTable(F);
00280 
00281   // Update the ModuleLevel entries to be accurate.
00282   ModuleLevel.resize(getNumPlanes());
00283   for (unsigned i = 0, e = getNumPlanes(); i != e; ++i)
00284     ModuleLevel[i] = getPlane(i).size();
00285   ModuleTypeLevel = Types.size();
00286 
00287   // Iterate over function arguments, adding them to the value table...
00288   for(Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end(); I != E; ++I)
00289     getOrCreateSlot(I);
00290 
00291   if (!ModuleContainsAllFunctionConstants) {
00292     // Iterate over all of the instructions in the function, looking for
00293     // constant values that are referenced.  Add these to the value pools
00294     // before any nonconstant values.  This will be turned into the constant
00295     // pool for the bytecode writer.
00296     //
00297 
00298     // Emit all of the constants that are being used by the instructions in
00299     // the function...
00300     for (constant_iterator CI = constant_begin(F), CE = constant_end(F);
00301          CI != CE; ++CI)
00302       getOrCreateSlot(*CI);
00303 
00304     // If there is a symbol table, it is possible that the user has names for
00305     // constants that are not being used.  In this case, we will have problems
00306     // if we don't emit the constants now, because otherwise we will get
00307     // symbol table references to constants not in the output.  Scan for these
00308     // constants now.
00309     //
00310     processSymbolTableConstants(&F->getSymbolTable());
00311   }
00312 
00313   SC_DEBUG("Inserting Instructions:\n");
00314 
00315   // Add all of the instructions to the type planes...
00316   for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
00317     getOrCreateSlot(BB);
00318     for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) {
00319       getOrCreateSlot(I);
00320     }
00321   }
00322 
00323   // If we are building a compaction table, prune out planes that do not benefit
00324   // from being compactified.
00325   if (!CompactionTable.empty())
00326     pruneCompactionTable();
00327 
00328   SC_DEBUG("end processFunction!\n");
00329 }
00330 
00331 void SlotCalculator::purgeFunction() {
00332   assert((ModuleLevel.size() != 0 ||
00333           ModuleTypeLevel != 0) && "Module not incorporated!");
00334   unsigned NumModuleTypes = ModuleLevel.size();
00335 
00336   SC_DEBUG("begin purgeFunction!\n");
00337 
00338   // First, free the compaction map if used.
00339   CompactionNodeMap.clear();
00340   CompactionTypeMap.clear();
00341 
00342   // Next, remove values from existing type planes
00343   for (unsigned i = 0; i != NumModuleTypes; ++i) {
00344     // Size of plane before function came
00345     unsigned ModuleLev = getModuleLevel(i);
00346     assert(int(ModuleLev) >= 0 && "BAD!");
00347 
00348     TypePlane &Plane = getPlane(i);
00349 
00350     assert(ModuleLev <= Plane.size() && "module levels higher than elements?");
00351     while (Plane.size() != ModuleLev) {
00352       assert(!isa<GlobalValue>(Plane.back()) &&
00353              "Functions cannot define globals!");
00354       NodeMap.erase(Plane.back());       // Erase from nodemap
00355       Plane.pop_back();                  // Shrink plane
00356     }
00357   }
00358 
00359   // We don't need this state anymore, free it up.
00360   ModuleLevel.clear();
00361   ModuleTypeLevel = 0;
00362 
00363   // Finally, remove any type planes defined by the function...
00364   CompactionTypes.clear();
00365   if (!CompactionTable.empty()) {
00366     CompactionTable.clear();
00367   } else {
00368     while (Table.size() > NumModuleTypes) {
00369       TypePlane &Plane = Table.back();
00370       SC_DEBUG("Removing Plane " << (Table.size()-1) << " of size "
00371                << Plane.size() << "\n");
00372       while (Plane.size()) {
00373         assert(!isa<GlobalValue>(Plane.back()) &&
00374                "Functions cannot define globals!");
00375         NodeMap.erase(Plane.back());   // Erase from nodemap
00376         Plane.pop_back();              // Shrink plane
00377       }
00378 
00379       Table.pop_back();                // Nuke the plane, we don't like it.
00380     }
00381   }
00382 
00383   SC_DEBUG("end purgeFunction!\n");
00384 }
00385 
00386 static inline bool hasNullValue(const Type *Ty) {
00387   return Ty != Type::LabelTy && Ty != Type::VoidTy && !isa<OpaqueType>(Ty);
00388 }
00389 
00390 /// getOrCreateCompactionTableSlot - This method is used to build up the initial
00391 /// approximation of the compaction table.
00392 unsigned SlotCalculator::getOrCreateCompactionTableSlot(const Value *V) {
00393   std::map<const Value*, unsigned>::iterator I =
00394     CompactionNodeMap.lower_bound(V);
00395   if (I != CompactionNodeMap.end() && I->first == V)
00396     return I->second;  // Already exists?
00397 
00398   // Make sure the type is in the table.
00399   unsigned Ty;
00400   if (!CompactionTypes.empty())
00401     Ty = getOrCreateCompactionTableSlot(V->getType());
00402   else    // If the type plane was decompactified, use the global plane ID
00403     Ty = getSlot(V->getType());
00404   if (CompactionTable.size() <= Ty)
00405     CompactionTable.resize(Ty+1);
00406 
00407   TypePlane &TyPlane = CompactionTable[Ty];
00408 
00409   // Make sure to insert the null entry if the thing we are inserting is not a
00410   // null constant.
00411   if (TyPlane.empty() && hasNullValue(V->getType())) {
00412     Value *ZeroInitializer = Constant::getNullValue(V->getType());
00413     if (V != ZeroInitializer) {
00414       TyPlane.push_back(ZeroInitializer);
00415       CompactionNodeMap[ZeroInitializer] = 0;
00416     }
00417   }
00418 
00419   unsigned SlotNo = TyPlane.size();
00420   TyPlane.push_back(V);
00421   CompactionNodeMap.insert(std::make_pair(V, SlotNo));
00422   return SlotNo;
00423 }
00424 
00425 /// getOrCreateCompactionTableSlot - This method is used to build up the initial
00426 /// approximation of the compaction table.
00427 unsigned SlotCalculator::getOrCreateCompactionTableSlot(const Type *T) {
00428   std::map<const Type*, unsigned>::iterator I =
00429     CompactionTypeMap.lower_bound(T);
00430   if (I != CompactionTypeMap.end() && I->first == T)
00431     return I->second;  // Already exists?
00432 
00433   unsigned SlotNo = CompactionTypes.size();
00434   SC_DEBUG("Inserting Compaction Type #" << SlotNo << ": " << T << "\n");
00435   CompactionTypes.push_back(T);
00436   CompactionTypeMap.insert(std::make_pair(T, SlotNo));
00437   return SlotNo;
00438 }
00439 
00440 /// buildCompactionTable - Since all of the function constants and types are
00441 /// stored in the module-level constant table, we don't need to emit a function
00442 /// constant table.  Also due to this, the indices for various constants and
00443 /// types might be very large in large programs.  In order to avoid blowing up
00444 /// the size of instructions in the bytecode encoding, we build a compaction
00445 /// table, which defines a mapping from function-local identifiers to global
00446 /// identifiers.
00447 void SlotCalculator::buildCompactionTable(const Function *F) {
00448   assert(CompactionNodeMap.empty() && "Compaction table already built!");
00449   assert(CompactionTypeMap.empty() && "Compaction types already built!");
00450   // First step, insert the primitive types.
00451   CompactionTable.resize(Type::LastPrimitiveTyID+1);
00452   for (unsigned i = 0; i <= Type::LastPrimitiveTyID; ++i) {
00453     const Type *PrimTy = Type::getPrimitiveType((Type::TypeID)i);
00454     CompactionTypes.push_back(PrimTy);
00455     CompactionTypeMap[PrimTy] = i;
00456   }
00457 
00458   // Next, include any types used by function arguments.
00459   for (Function::const_arg_iterator I = F->arg_begin(), E = F->arg_end();
00460        I != E; ++I)
00461     getOrCreateCompactionTableSlot(I->getType());
00462 
00463   // Next, find all of the types and values that are referred to by the
00464   // instructions in the function.
00465   for (const_inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
00466     getOrCreateCompactionTableSlot(I->getType());
00467     for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op)
00468       if (isa<Constant>(I->getOperand(op)))
00469         getOrCreateCompactionTableSlot(I->getOperand(op));
00470   }
00471 
00472   // Do the types in the symbol table
00473   const SymbolTable &ST = F->getSymbolTable();
00474   for (SymbolTable::type_const_iterator TI = ST.type_begin(),
00475        TE = ST.type_end(); TI != TE; ++TI)
00476     getOrCreateCompactionTableSlot(TI->second);
00477 
00478   // Now do the constants and global values
00479   for (SymbolTable::plane_const_iterator PI = ST.plane_begin(),
00480        PE = ST.plane_end(); PI != PE; ++PI)
00481     for (SymbolTable::value_const_iterator VI = PI->second.begin(),
00482            VE = PI->second.end(); VI != VE; ++VI)
00483       if (isa<Constant>(VI->second) && !isa<GlobalValue>(VI->second))
00484         getOrCreateCompactionTableSlot(VI->second);
00485 
00486   // Now that we have all of the values in the table, and know what types are
00487   // referenced, make sure that there is at least the zero initializer in any
00488   // used type plane.  Since the type was used, we will be emitting instructions
00489   // to the plane even if there are no constants in it.
00490   CompactionTable.resize(CompactionTypes.size());
00491   for (unsigned i = 0, e = CompactionTable.size(); i != e; ++i)
00492     if (CompactionTable[i].empty() && (i != Type::VoidTyID) &&
00493         i != Type::LabelTyID) {
00494       const Type *Ty = CompactionTypes[i];
00495       SC_DEBUG("Getting Null Value #" << i << " for Type " << Ty << "\n");
00496       assert(Ty->getTypeID() != Type::VoidTyID);
00497       assert(Ty->getTypeID() != Type::LabelTyID);
00498       getOrCreateCompactionTableSlot(Constant::getNullValue(Ty));
00499     }
00500 
00501   // Okay, now at this point, we have a legal compaction table.  Since we want
00502   // to emit the smallest possible binaries, do not compactify the type plane if
00503   // it will not save us anything.  Because we have not yet incorporated the
00504   // function body itself yet, we don't know whether or not it's a good idea to
00505   // compactify other planes.  We will defer this decision until later.
00506   TypeList &GlobalTypes = Types;
00507 
00508   // All of the values types will be scrunched to the start of the types plane
00509   // of the global table.  Figure out just how many there are.
00510   assert(!GlobalTypes.empty() && "No global types???");
00511   unsigned NumFCTypes = GlobalTypes.size()-1;
00512   while (!GlobalTypes[NumFCTypes]->isFirstClassType())
00513     --NumFCTypes;
00514 
00515   // If there are fewer that 64 types, no instructions will be exploded due to
00516   // the size of the type operands.  Thus there is no need to compactify types.
00517   // Also, if the compaction table contains most of the entries in the global
00518   // table, there really is no reason to compactify either.
00519   if (NumFCTypes < 64) {
00520     // Decompactifying types is tricky, because we have to move type planes all
00521     // over the place.  At least we don't need to worry about updating the
00522     // CompactionNodeMap for non-types though.
00523     std::vector<TypePlane> TmpCompactionTable;
00524     std::swap(CompactionTable, TmpCompactionTable);
00525     TypeList TmpTypes;
00526     std::swap(TmpTypes, CompactionTypes);
00527 
00528     // Move each plane back over to the uncompactified plane
00529     while (!TmpTypes.empty()) {
00530       const Type *Ty = TmpTypes.back();
00531       TmpTypes.pop_back();
00532       CompactionTypeMap.erase(Ty);  // Decompactify type!
00533 
00534       // Find the global slot number for this type.
00535       int TySlot = getSlot(Ty);
00536       assert(TySlot != -1 && "Type doesn't exist in global table?");
00537 
00538       // Now we know where to put the compaction table plane.
00539       if (CompactionTable.size() <= unsigned(TySlot))
00540         CompactionTable.resize(TySlot+1);
00541       // Move the plane back into the compaction table.
00542       std::swap(CompactionTable[TySlot], TmpCompactionTable[TmpTypes.size()]);
00543 
00544       // And remove the empty plane we just moved in.
00545       TmpCompactionTable.pop_back();
00546     }
00547   }
00548 }
00549 
00550 
00551 /// pruneCompactionTable - Once the entire function being processed has been
00552 /// incorporated into the current compaction table, look over the compaction
00553 /// table and check to see if there are any values whose compaction will not
00554 /// save us any space in the bytecode file.  If compactifying these values
00555 /// serves no purpose, then we might as well not even emit the compactification
00556 /// information to the bytecode file, saving a bit more space.
00557 ///
00558 /// Note that the type plane has already been compactified if possible.
00559 ///
00560 void SlotCalculator::pruneCompactionTable() {
00561   TypeList &TyPlane = CompactionTypes;
00562   for (unsigned ctp = 0, e = CompactionTable.size(); ctp != e; ++ctp)
00563     if (!CompactionTable[ctp].empty()) {
00564       TypePlane &CPlane = CompactionTable[ctp];
00565       unsigned GlobalSlot = ctp;
00566       if (!TyPlane.empty())
00567         GlobalSlot = getGlobalSlot(TyPlane[ctp]);
00568 
00569       if (GlobalSlot >= Table.size())
00570         Table.resize(GlobalSlot+1);
00571       TypePlane &GPlane = Table[GlobalSlot];
00572 
00573       unsigned ModLevel = getModuleLevel(ctp);
00574       unsigned NumFunctionObjs = CPlane.size()-ModLevel;
00575 
00576       // If the maximum index required if all entries in this plane were merged
00577       // into the global plane is less than 64, go ahead and eliminate the
00578       // plane.
00579       bool PrunePlane = GPlane.size() + NumFunctionObjs < 64;
00580 
00581       // If there are no function-local values defined, and the maximum
00582       // referenced global entry is less than 64, we don't need to compactify.
00583       if (!PrunePlane && NumFunctionObjs == 0) {
00584         unsigned MaxIdx = 0;
00585         for (unsigned i = 0; i != ModLevel; ++i) {
00586           unsigned Idx = NodeMap[CPlane[i]];
00587           if (Idx > MaxIdx) MaxIdx = Idx;
00588         }
00589         PrunePlane = MaxIdx < 64;
00590       }
00591 
00592       // Ok, finally, if we decided to prune this plane out of the compaction
00593       // table, do so now.
00594       if (PrunePlane) {
00595         TypePlane OldPlane;
00596         std::swap(OldPlane, CPlane);
00597 
00598         // Loop over the function local objects, relocating them to the global
00599         // table plane.
00600         for (unsigned i = ModLevel, e = OldPlane.size(); i != e; ++i) {
00601           const Value *V = OldPlane[i];
00602           CompactionNodeMap.erase(V);
00603           assert(NodeMap.count(V) == 0 && "Value already in table??");
00604           getOrCreateSlot(V);
00605         }
00606 
00607         // For compactified global values, just remove them from the compaction
00608         // node map.
00609         for (unsigned i = 0; i != ModLevel; ++i)
00610           CompactionNodeMap.erase(OldPlane[i]);
00611 
00612         // Update the new modulelevel for this plane.
00613         assert(ctp < ModuleLevel.size() && "Cannot set modulelevel!");
00614         ModuleLevel[ctp] = GPlane.size()-NumFunctionObjs;
00615         assert((int)ModuleLevel[ctp] >= 0 && "Bad computation!");
00616       }
00617     }
00618 }
00619 
00620 /// Determine if the compaction table is actually empty. Because the
00621 /// compaction table always includes the primitive type planes, we
00622 /// can't just check getCompactionTable().size() because it will never
00623 /// be zero. Furthermore, the ModuleLevel factors into whether a given
00624 /// plane is empty or not. This function does the necessary computation
00625 /// to determine if its actually empty.
00626 bool SlotCalculator::CompactionTableIsEmpty() const {
00627   // Check a degenerate case, just in case.
00628   if (CompactionTable.size() == 0) return true;
00629 
00630   // Check each plane
00631   for (unsigned i = 0, e = CompactionTable.size(); i < e; ++i) {
00632     // If the plane is not empty
00633     if (!CompactionTable[i].empty()) {
00634       // If the module level is non-zero then at least the
00635       // first element of the plane is valid and therefore not empty.
00636       unsigned End = getModuleLevel(i);
00637       if (End != 0)
00638         return false;
00639     }
00640   }
00641   // All the compaction table planes are empty so the table is
00642   // considered empty too.
00643   return true;
00644 }
00645 
00646 int SlotCalculator::getSlot(const Value *V) const {
00647   // If there is a CompactionTable active...
00648   if (!CompactionNodeMap.empty()) {
00649     std::map<const Value*, unsigned>::const_iterator I =
00650       CompactionNodeMap.find(V);
00651     if (I != CompactionNodeMap.end())
00652       return (int)I->second;
00653     // Otherwise, if it's not in the compaction table, it must be in a
00654     // non-compactified plane.
00655   }
00656 
00657   std::map<const Value*, unsigned>::const_iterator I = NodeMap.find(V);
00658   if (I != NodeMap.end())
00659     return (int)I->second;
00660 
00661   return -1;
00662 }
00663 
00664 int SlotCalculator::getSlot(const Type*T) const {
00665   // If there is a CompactionTable active...
00666   if (!CompactionTypeMap.empty()) {
00667     std::map<const Type*, unsigned>::const_iterator I =
00668       CompactionTypeMap.find(T);
00669     if (I != CompactionTypeMap.end())
00670       return (int)I->second;
00671     // Otherwise, if it's not in the compaction table, it must be in a
00672     // non-compactified plane.
00673   }
00674 
00675   std::map<const Type*, unsigned>::const_iterator I = TypeMap.find(T);
00676   if (I != TypeMap.end())
00677     return (int)I->second;
00678 
00679   return -1;
00680 }
00681 
00682 int SlotCalculator::getOrCreateSlot(const Value *V) {
00683   if (V->getType() == Type::VoidTy) return -1;
00684 
00685   int SlotNo = getSlot(V);        // Check to see if it's already in!
00686   if (SlotNo != -1) return SlotNo;
00687 
00688   if (const GlobalValue *GV = dyn_cast<GlobalValue>(V))
00689     assert(GV->getParent() != 0 && "Global not embedded into a module!");
00690 
00691   if (!isa<GlobalValue>(V))  // Initializers for globals are handled explicitly
00692     if (const Constant *C = dyn_cast<Constant>(V)) {
00693       assert(CompactionNodeMap.empty() &&
00694              "All needed constants should be in the compaction map already!");
00695 
00696       // Do not index the characters that make up constant strings.  We emit
00697       // constant strings as special entities that don't require their
00698       // individual characters to be emitted.
00699       if (!isa<ConstantArray>(C) || !cast<ConstantArray>(C)->isString()) {
00700         // This makes sure that if a constant has uses (for example an array of
00701         // const ints), that they are inserted also.
00702         //
00703         for (User::const_op_iterator I = C->op_begin(), E = C->op_end();
00704              I != E; ++I)
00705           getOrCreateSlot(*I);
00706       } else {
00707         assert(ModuleLevel.empty() &&
00708                "How can a constant string be directly accessed in a function?");
00709         // Otherwise, if we are emitting a bytecode file and this IS a string,
00710         // remember it.
00711         if (!C->isNullValue())
00712           ConstantStrings.push_back(cast<ConstantArray>(C));
00713       }
00714     }
00715 
00716   return insertValue(V);
00717 }
00718 
00719 int SlotCalculator::getOrCreateSlot(const Type* T) {
00720   int SlotNo = getSlot(T);        // Check to see if it's already in!
00721   if (SlotNo != -1) return SlotNo;
00722   return insertType(T);
00723 }
00724 
00725 int SlotCalculator::insertValue(const Value *D, bool dontIgnore) {
00726   assert(D && "Can't insert a null value!");
00727   assert(getSlot(D) == -1 && "Value is already in the table!");
00728 
00729   // If we are building a compaction map, and if this plane is being compacted,
00730   // insert the value into the compaction map, not into the global map.
00731   if (!CompactionNodeMap.empty()) {
00732     if (D->getType() == Type::VoidTy) return -1;  // Do not insert void values
00733     assert(!isa<Constant>(D) &&
00734            "Types, constants, and globals should be in global table!");
00735 
00736     int Plane = getSlot(D->getType());
00737     assert(Plane != -1 && CompactionTable.size() > (unsigned)Plane &&
00738            "Didn't find value type!");
00739     if (!CompactionTable[Plane].empty())
00740       return getOrCreateCompactionTableSlot(D);
00741   }
00742 
00743   // If this node does not contribute to a plane, or if the node has a
00744   // name and we don't want names, then ignore the silly node... Note that types
00745   // do need slot numbers so that we can keep track of where other values land.
00746   //
00747   if (!dontIgnore)                               // Don't ignore nonignorables!
00748     if (D->getType() == Type::VoidTy ) {         // Ignore void type nodes
00749       SC_DEBUG("ignored value " << *D << "\n");
00750       return -1;                  // We do need types unconditionally though
00751     }
00752 
00753   // Okay, everything is happy, actually insert the silly value now...
00754   return doInsertValue(D);
00755 }
00756 
00757 int SlotCalculator::insertType(const Type *Ty, bool dontIgnore) {
00758   assert(Ty && "Can't insert a null type!");
00759   assert(getSlot(Ty) == -1 && "Type is already in the table!");
00760 
00761   // If we are building a compaction map, and if this plane is being compacted,
00762   // insert the value into the compaction map, not into the global map.
00763   if (!CompactionTypeMap.empty()) {
00764     getOrCreateCompactionTableSlot(Ty);
00765   }
00766 
00767   // Insert the current type before any subtypes.  This is important because
00768   // recursive types elements are inserted in a bottom up order.  Changing
00769   // this here can break things.  For example:
00770   //
00771   //    global { \2 * } { { \2 }* null }
00772   //
00773   int ResultSlot = doInsertType(Ty);
00774   SC_DEBUG("  Inserted type: " << Ty->getDescription() << " slot=" <<
00775            ResultSlot << "\n");
00776 
00777   // Loop over any contained types in the definition... in post
00778   // order.
00779   for (po_iterator<const Type*> I = po_begin(Ty), E = po_end(Ty);
00780        I != E; ++I) {
00781     if (*I != Ty) {
00782       const Type *SubTy = *I;
00783       // If we haven't seen this sub type before, add it to our type table!
00784       if (getSlot(SubTy) == -1) {
00785         SC_DEBUG("  Inserting subtype: " << SubTy->getDescription() << "\n");
00786         doInsertType(SubTy);
00787         SC_DEBUG("  Inserted subtype: " << SubTy->getDescription() << "\n");
00788       }
00789     }
00790   }
00791   return ResultSlot;
00792 }
00793 
00794 // doInsertValue - This is a small helper function to be called only
00795 // be insertValue.
00796 //
00797 int SlotCalculator::doInsertValue(const Value *D) {
00798   const Type *Typ = D->getType();
00799   unsigned Ty;
00800 
00801   // Used for debugging DefSlot=-1 assertion...
00802   //if (Typ == Type::TypeTy)
00803   //  cerr << "Inserting type '" << cast<Type>(D)->getDescription() << "'!\n";
00804 
00805   if (Typ->isDerivedType()) {
00806     int ValSlot;
00807     if (CompactionTable.empty())
00808       ValSlot = getSlot(Typ);
00809     else
00810       ValSlot = getGlobalSlot(Typ);
00811     if (ValSlot == -1) {                // Have we already entered this type?
00812       // Nope, this is the first we have seen the type, process it.
00813       ValSlot = insertType(Typ, true);
00814       assert(ValSlot != -1 && "ProcessType returned -1 for a type?");
00815     }
00816     Ty = (unsigned)ValSlot;
00817   } else {
00818     Ty = Typ->getTypeID();
00819   }
00820 
00821   if (Table.size() <= Ty)    // Make sure we have the type plane allocated...
00822     Table.resize(Ty+1, TypePlane());
00823 
00824   // If this is the first value to get inserted into the type plane, make sure
00825   // to insert the implicit null value...
00826   if (Table[Ty].empty() && hasNullValue(Typ)) {
00827     Value *ZeroInitializer = Constant::getNullValue(Typ);
00828 
00829     // If we are pushing zeroinit, it will be handled below.
00830     if (D != ZeroInitializer) {
00831       Table[Ty].push_back(ZeroInitializer);
00832       NodeMap[ZeroInitializer] = 0;
00833     }
00834   }
00835 
00836   // Insert node into table and NodeMap...
00837   unsigned DestSlot = NodeMap[D] = Table[Ty].size();
00838   Table[Ty].push_back(D);
00839 
00840   SC_DEBUG("  Inserting value [" << Ty << "] = " << D << " slot=" <<
00841            DestSlot << " [");
00842   // G = Global, C = Constant, T = Type, F = Function, o = other
00843   SC_DEBUG((isa<GlobalVariable>(D) ? "G" : (isa<Constant>(D) ? "C" :
00844            (isa<Function>(D) ? "F" : "o"))));
00845   SC_DEBUG("]\n");
00846   return (int)DestSlot;
00847 }
00848 
00849 // doInsertType - This is a small helper function to be called only
00850 // be insertType.
00851 //
00852 int SlotCalculator::doInsertType(const Type *Ty) {
00853 
00854   // Insert node into table and NodeMap...
00855   unsigned DestSlot = TypeMap[Ty] = Types.size();
00856   Types.push_back(Ty);
00857 
00858   SC_DEBUG("  Inserting type [" << DestSlot << "] = " << Ty << "\n" );
00859   return (int)DestSlot;
00860 }
00861