LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

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/Instructions.h"
00022 #include "llvm/Module.h"
00023 #include "llvm/SymbolTable.h"
00024 #include "llvm/Type.h"
00025 #include "llvm/Analysis/ConstantsScanner.h"
00026 #include "llvm/ADT/PostOrderIterator.h"
00027 #include "llvm/ADT/STLExtras.h"
00028 #include <algorithm>
00029 #include <functional>
00030 
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_giterator I = TheModule->gbegin(), E = TheModule->gend();
00125        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_giterator I = TheModule->gbegin(), E = TheModule->gend();
00138        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 (unsigned op = 0, e = I->getNumOperands(); op != e; ++op)
00186         if (isa<Constant>(I->getOperand(op)) && 
00187             !isa<GlobalValue>(I->getOperand(op)))
00188           getOrCreateSlot(I->getOperand(op));
00189       getOrCreateSlot(I->getType());
00190       if (const VANextInst *VAN = dyn_cast<VANextInst>(&*I))
00191         getOrCreateSlot(VAN->getArgType());
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_aiterator I = F->abegin(), E = F->aend(); 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     constant_iterator CI = constant_begin(F);
00301     constant_iterator CE = constant_end(F);
00302     while ( CI != CE ) {
00303       this->getOrCreateSlot(*CI);
00304       ++CI;
00305     }
00306     
00307     // If there is a symbol table, it is possible that the user has names for
00308     // constants that are not being used.  In this case, we will have problems
00309     // if we don't emit the constants now, because otherwise we will get 
00310     // symbol table references to constants not in the output.  Scan for these
00311     // constants now.
00312     //
00313     processSymbolTableConstants(&F->getSymbolTable());
00314   }
00315 
00316   SC_DEBUG("Inserting Instructions:\n");
00317 
00318   // Add all of the instructions to the type planes...
00319   for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
00320     getOrCreateSlot(BB);
00321     for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) {
00322       getOrCreateSlot(I);
00323       if (const VANextInst *VAN = dyn_cast<VANextInst>(I))
00324         getOrCreateSlot(VAN->getArgType());
00325     }
00326   }
00327 
00328   // If we are building a compaction table, prune out planes that do not benefit
00329   // from being compactified.
00330   if (!CompactionTable.empty())
00331     pruneCompactionTable();
00332 
00333   SC_DEBUG("end processFunction!\n");
00334 }
00335 
00336 void SlotCalculator::purgeFunction() {
00337   assert((ModuleLevel.size() != 0 ||
00338           ModuleTypeLevel != 0) && "Module not incorporated!");
00339   unsigned NumModuleTypes = ModuleLevel.size();
00340 
00341   SC_DEBUG("begin purgeFunction!\n");
00342 
00343   // First, free the compaction map if used.
00344   CompactionNodeMap.clear();
00345   CompactionTypeMap.clear();
00346 
00347   // Next, remove values from existing type planes
00348   for (unsigned i = 0; i != NumModuleTypes; ++i) {
00349     // Size of plane before function came
00350     unsigned ModuleLev = getModuleLevel(i);
00351     assert(int(ModuleLev) >= 0 && "BAD!");
00352 
00353     TypePlane &Plane = getPlane(i);
00354 
00355     assert(ModuleLev <= Plane.size() && "module levels higher than elements?");
00356     while (Plane.size() != ModuleLev) {
00357       assert(!isa<GlobalValue>(Plane.back()) &&
00358              "Functions cannot define globals!");
00359       NodeMap.erase(Plane.back());       // Erase from nodemap
00360       Plane.pop_back();                  // Shrink plane
00361     }
00362   }
00363 
00364   // We don't need this state anymore, free it up.
00365   ModuleLevel.clear();
00366   ModuleTypeLevel = 0;
00367 
00368   // Finally, remove any type planes defined by the function...
00369   CompactionTypes.clear();
00370   if (!CompactionTable.empty()) {
00371     CompactionTable.clear();
00372   } else {
00373     while (Table.size() > NumModuleTypes) {
00374       TypePlane &Plane = Table.back();
00375       SC_DEBUG("Removing Plane " << (Table.size()-1) << " of size "
00376                << Plane.size() << "\n");
00377       while (Plane.size()) {
00378         assert(!isa<GlobalValue>(Plane.back()) &&
00379                "Functions cannot define globals!");
00380         NodeMap.erase(Plane.back());   // Erase from nodemap
00381         Plane.pop_back();              // Shrink plane
00382       }
00383       
00384       Table.pop_back();                // Nuke the plane, we don't like it.
00385     }
00386   }
00387 
00388   SC_DEBUG("end purgeFunction!\n");
00389 }
00390 
00391 static inline bool hasNullValue(unsigned TyID) {
00392   return TyID != Type::LabelTyID && TyID != Type::VoidTyID;
00393 }
00394 
00395 /// getOrCreateCompactionTableSlot - This method is used to build up the initial
00396 /// approximation of the compaction table.
00397 unsigned SlotCalculator::getOrCreateCompactionTableSlot(const Value *V) {
00398   std::map<const Value*, unsigned>::iterator I =
00399     CompactionNodeMap.lower_bound(V);
00400   if (I != CompactionNodeMap.end() && I->first == V)
00401     return I->second;  // Already exists?
00402 
00403   // Make sure the type is in the table.
00404   unsigned Ty;
00405   if (!CompactionTypes.empty())
00406     Ty = getOrCreateCompactionTableSlot(V->getType());
00407   else    // If the type plane was decompactified, use the global plane ID
00408     Ty = getSlot(V->getType());
00409   if (CompactionTable.size() <= Ty)
00410     CompactionTable.resize(Ty+1);
00411 
00412   TypePlane &TyPlane = CompactionTable[Ty];
00413 
00414   // Make sure to insert the null entry if the thing we are inserting is not a
00415   // null constant.
00416   if (TyPlane.empty() && hasNullValue(V->getType()->getTypeID())) {
00417     Value *ZeroInitializer = Constant::getNullValue(V->getType());
00418     if (V != ZeroInitializer) {
00419       TyPlane.push_back(ZeroInitializer);
00420       CompactionNodeMap[ZeroInitializer] = 0;
00421     }
00422   }
00423 
00424   unsigned SlotNo = TyPlane.size();
00425   TyPlane.push_back(V);
00426   CompactionNodeMap.insert(std::make_pair(V, SlotNo));
00427   return SlotNo;
00428 }
00429 
00430 /// getOrCreateCompactionTableSlot - This method is used to build up the initial
00431 /// approximation of the compaction table.
00432 unsigned SlotCalculator::getOrCreateCompactionTableSlot(const Type *T) {
00433   std::map<const Type*, unsigned>::iterator I =
00434     CompactionTypeMap.lower_bound(T);
00435   if (I != CompactionTypeMap.end() && I->first == T)
00436     return I->second;  // Already exists?
00437 
00438   unsigned SlotNo = CompactionTypes.size();
00439   SC_DEBUG("Inserting Compaction Type #" << SlotNo << ": " << T << "\n");
00440   CompactionTypes.push_back(T);
00441   CompactionTypeMap.insert(std::make_pair(T, SlotNo));
00442   return SlotNo;
00443 }
00444 
00445 /// buildCompactionTable - Since all of the function constants and types are
00446 /// stored in the module-level constant table, we don't need to emit a function
00447 /// constant table.  Also due to this, the indices for various constants and
00448 /// types might be very large in large programs.  In order to avoid blowing up
00449 /// the size of instructions in the bytecode encoding, we build a compaction
00450 /// table, which defines a mapping from function-local identifiers to global
00451 /// identifiers.
00452 void SlotCalculator::buildCompactionTable(const Function *F) {
00453   assert(CompactionNodeMap.empty() && "Compaction table already built!");
00454   assert(CompactionTypeMap.empty() && "Compaction types already built!");
00455   // First step, insert the primitive types.
00456   CompactionTable.resize(Type::LastPrimitiveTyID+1);
00457   for (unsigned i = 0; i <= Type::LastPrimitiveTyID; ++i) {
00458     const Type *PrimTy = Type::getPrimitiveType((Type::TypeID)i);
00459     CompactionTypes.push_back(PrimTy);
00460     CompactionTypeMap[PrimTy] = i;
00461   }
00462 
00463   // Next, include any types used by function arguments.
00464   for (Function::const_aiterator I = F->abegin(), E = F->aend(); I != E; ++I)
00465     getOrCreateCompactionTableSlot(I->getType());
00466 
00467   // Next, find all of the types and values that are referred to by the
00468   // instructions in the function.
00469   for (const_inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
00470     getOrCreateCompactionTableSlot(I->getType());
00471     for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op)
00472       if (isa<Constant>(I->getOperand(op)))
00473         getOrCreateCompactionTableSlot(I->getOperand(op));
00474     if (const VANextInst *VAN = dyn_cast<VANextInst>(&*I))
00475       getOrCreateCompactionTableSlot(VAN->getArgType());
00476   }
00477 
00478   // Do the types in the symbol table
00479   const SymbolTable &ST = F->getSymbolTable();
00480   for (SymbolTable::type_const_iterator TI = ST.type_begin(),
00481        TE = ST.type_end(); TI != TE; ++TI)
00482     getOrCreateCompactionTableSlot(TI->second);
00483 
00484   // Now do the constants and global values
00485   for (SymbolTable::plane_const_iterator PI = ST.plane_begin(), 
00486        PE = ST.plane_end(); PI != PE; ++PI)
00487     for (SymbolTable::value_const_iterator VI = PI->second.begin(),
00488            VE = PI->second.end(); VI != VE; ++VI)
00489       if (isa<Constant>(VI->second) && !isa<GlobalValue>(VI->second))
00490         getOrCreateCompactionTableSlot(VI->second);
00491 
00492   // Now that we have all of the values in the table, and know what types are
00493   // referenced, make sure that there is at least the zero initializer in any
00494   // used type plane.  Since the type was used, we will be emitting instructions
00495   // to the plane even if there are no constants in it.
00496   CompactionTable.resize(CompactionTypes.size());
00497   for (unsigned i = 0, e = CompactionTable.size(); i != e; ++i)
00498     if (CompactionTable[i].empty() && (i != Type::VoidTyID) &&
00499         i != Type::LabelTyID) {
00500       const Type *Ty = CompactionTypes[i];
00501       SC_DEBUG("Getting Null Value #" << i << " for Type " << Ty << "\n");
00502       assert(Ty->getTypeID() != Type::VoidTyID);
00503       assert(Ty->getTypeID() != Type::LabelTyID);
00504       getOrCreateCompactionTableSlot(Constant::getNullValue(Ty));
00505     }
00506   
00507   // Okay, now at this point, we have a legal compaction table.  Since we want
00508   // to emit the smallest possible binaries, do not compactify the type plane if
00509   // it will not save us anything.  Because we have not yet incorporated the
00510   // function body itself yet, we don't know whether or not it's a good idea to
00511   // compactify other planes.  We will defer this decision until later.
00512   TypeList &GlobalTypes = Types;
00513   
00514   // All of the values types will be scrunched to the start of the types plane
00515   // of the global table.  Figure out just how many there are.
00516   assert(!GlobalTypes.empty() && "No global types???");
00517   unsigned NumFCTypes = GlobalTypes.size()-1;
00518   while (!GlobalTypes[NumFCTypes]->isFirstClassType())
00519     --NumFCTypes;
00520 
00521   // If there are fewer that 64 types, no instructions will be exploded due to
00522   // the size of the type operands.  Thus there is no need to compactify types.
00523   // Also, if the compaction table contains most of the entries in the global
00524   // table, there really is no reason to compactify either.
00525   if (NumFCTypes < 64) {
00526     // Decompactifying types is tricky, because we have to move type planes all
00527     // over the place.  At least we don't need to worry about updating the
00528     // CompactionNodeMap for non-types though.
00529     std::vector<TypePlane> TmpCompactionTable;
00530     std::swap(CompactionTable, TmpCompactionTable);
00531     TypeList TmpTypes;
00532     std::swap(TmpTypes, CompactionTypes);
00533     
00534     // Move each plane back over to the uncompactified plane
00535     while (!TmpTypes.empty()) {
00536       const Type *Ty = TmpTypes.back();
00537       TmpTypes.pop_back();
00538       CompactionTypeMap.erase(Ty);  // Decompactify type!
00539 
00540       // Find the global slot number for this type.
00541       int TySlot = getSlot(Ty);
00542       assert(TySlot != -1 && "Type doesn't exist in global table?");
00543       
00544       // Now we know where to put the compaction table plane.
00545       if (CompactionTable.size() <= unsigned(TySlot))
00546         CompactionTable.resize(TySlot+1);
00547       // Move the plane back into the compaction table.
00548       std::swap(CompactionTable[TySlot], TmpCompactionTable[TmpTypes.size()]);
00549 
00550       // And remove the empty plane we just moved in.
00551       TmpCompactionTable.pop_back();
00552     }
00553   }
00554 }
00555 
00556 
00557 /// pruneCompactionTable - Once the entire function being processed has been
00558 /// incorporated into the current compaction table, look over the compaction
00559 /// table and check to see if there are any values whose compaction will not
00560 /// save us any space in the bytecode file.  If compactifying these values
00561 /// serves no purpose, then we might as well not even emit the compactification
00562 /// information to the bytecode file, saving a bit more space.
00563 ///
00564 /// Note that the type plane has already been compactified if possible.
00565 ///
00566 void SlotCalculator::pruneCompactionTable() {
00567   TypeList &TyPlane = CompactionTypes;
00568   for (unsigned ctp = 0, e = CompactionTable.size(); ctp != e; ++ctp)
00569     if (!CompactionTable[ctp].empty()) {
00570       TypePlane &CPlane = CompactionTable[ctp];
00571       unsigned GlobalSlot = ctp;
00572       if (!TyPlane.empty())
00573         GlobalSlot = getGlobalSlot(TyPlane[ctp]);
00574 
00575       if (GlobalSlot >= Table.size())
00576         Table.resize(GlobalSlot+1);
00577       TypePlane &GPlane = Table[GlobalSlot];
00578       
00579       unsigned ModLevel = getModuleLevel(ctp);
00580       unsigned NumFunctionObjs = CPlane.size()-ModLevel;
00581 
00582       // If the maximum index required if all entries in this plane were merged
00583       // into the global plane is less than 64, go ahead and eliminate the
00584       // plane.
00585       bool PrunePlane = GPlane.size() + NumFunctionObjs < 64;
00586 
00587       // If there are no function-local values defined, and the maximum
00588       // referenced global entry is less than 64, we don't need to compactify.
00589       if (!PrunePlane && NumFunctionObjs == 0) {
00590         unsigned MaxIdx = 0;
00591         for (unsigned i = 0; i != ModLevel; ++i) {
00592           unsigned Idx = NodeMap[CPlane[i]];
00593           if (Idx > MaxIdx) MaxIdx = Idx;
00594         }
00595         PrunePlane = MaxIdx < 64;
00596       }
00597 
00598       // Ok, finally, if we decided to prune this plane out of the compaction
00599       // table, do so now.
00600       if (PrunePlane) {
00601         TypePlane OldPlane;
00602         std::swap(OldPlane, CPlane);
00603 
00604         // Loop over the function local objects, relocating them to the global
00605         // table plane.
00606         for (unsigned i = ModLevel, e = OldPlane.size(); i != e; ++i) {
00607           const Value *V = OldPlane[i];
00608           CompactionNodeMap.erase(V);
00609           assert(NodeMap.count(V) == 0 && "Value already in table??");
00610           getOrCreateSlot(V);
00611         }
00612 
00613         // For compactified global values, just remove them from the compaction
00614         // node map.
00615         for (unsigned i = 0; i != ModLevel; ++i)
00616           CompactionNodeMap.erase(OldPlane[i]);
00617 
00618         // Update the new modulelevel for this plane.
00619         assert(ctp < ModuleLevel.size() && "Cannot set modulelevel!");
00620         ModuleLevel[ctp] = GPlane.size()-NumFunctionObjs;
00621         assert((int)ModuleLevel[ctp] >= 0 && "Bad computation!");
00622       }
00623     }
00624 }
00625 
00626 /// Determine if the compaction table is actually empty. Because the
00627 /// compaction table always includes the primitive type planes, we 
00628 /// can't just check getCompactionTable().size() because it will never
00629 /// be zero. Furthermore, the ModuleLevel factors into whether a given
00630 /// plane is empty or not. This function does the necessary computation
00631 /// to determine if its actually empty.
00632 bool SlotCalculator::CompactionTableIsEmpty() const {
00633   // Check a degenerate case, just in case.
00634   if (CompactionTable.size() == 0) return true;
00635 
00636   // Check each plane
00637   for (unsigned i = 0, e = CompactionTable.size(); i < e; ++i) {
00638     // If the plane is not empty
00639     if (!CompactionTable[i].empty()) {
00640       // If the module level is non-zero then at least the
00641       // first element of the plane is valid and therefore not empty.
00642       unsigned End = getModuleLevel(i);
00643       if (End != 0) 
00644         return false;
00645     }
00646   }
00647   // All the compaction table planes are empty so the table is
00648   // considered empty too.
00649   return true;
00650 }
00651 
00652 int SlotCalculator::getSlot(const Value *V) const {
00653   // If there is a CompactionTable active...
00654   if (!CompactionNodeMap.empty()) {
00655     std::map<const Value*, unsigned>::const_iterator I =
00656       CompactionNodeMap.find(V);
00657     if (I != CompactionNodeMap.end())
00658       return (int)I->second;
00659     // Otherwise, if it's not in the compaction table, it must be in a
00660     // non-compactified plane.
00661   }
00662 
00663   std::map<const Value*, unsigned>::const_iterator I = NodeMap.find(V);
00664   if (I != NodeMap.end())
00665     return (int)I->second;
00666 
00667   return -1;
00668 }
00669 
00670 int SlotCalculator::getSlot(const Type*T) const {
00671   // If there is a CompactionTable active...
00672   if (!CompactionTypeMap.empty()) {
00673     std::map<const Type*, unsigned>::const_iterator I =
00674       CompactionTypeMap.find(T);
00675     if (I != CompactionTypeMap.end())
00676       return (int)I->second;
00677     // Otherwise, if it's not in the compaction table, it must be in a
00678     // non-compactified plane.
00679   }
00680 
00681   std::map<const Type*, unsigned>::const_iterator I = TypeMap.find(T);
00682   if (I != TypeMap.end())
00683     return (int)I->second;
00684 
00685   return -1;
00686 }
00687 
00688 int SlotCalculator::getOrCreateSlot(const Value *V) {
00689   if (V->getType() == Type::VoidTy) return -1;
00690 
00691   int SlotNo = getSlot(V);        // Check to see if it's already in!
00692   if (SlotNo != -1) return SlotNo;
00693 
00694   if (const GlobalValue *GV = dyn_cast<GlobalValue>(V))
00695     assert(GV->getParent() != 0 && "Global not embedded into a module!");
00696 
00697   if (!isa<GlobalValue>(V))  // Initializers for globals are handled explicitly
00698     if (const Constant *C = dyn_cast<Constant>(V)) {
00699       assert(CompactionNodeMap.empty() &&
00700              "All needed constants should be in the compaction map already!");
00701 
00702       // Do not index the characters that make up constant strings.  We emit 
00703       // constant strings as special entities that don't require their 
00704       // individual characters to be emitted.
00705       if (!isa<ConstantArray>(C) || !cast<ConstantArray>(C)->isString()) {
00706         // This makes sure that if a constant has uses (for example an array of
00707         // const ints), that they are inserted also.
00708         //
00709         for (User::const_op_iterator I = C->op_begin(), E = C->op_end();
00710              I != E; ++I)
00711           getOrCreateSlot(*I);
00712       } else {
00713         assert(ModuleLevel.empty() &&
00714                "How can a constant string be directly accessed in a function?");
00715         // Otherwise, if we are emitting a bytecode file and this IS a string,
00716         // remember it.
00717         if (!C->isNullValue())
00718           ConstantStrings.push_back(cast<ConstantArray>(C));
00719       }
00720     }
00721 
00722   return insertValue(V);
00723 }
00724 
00725 int SlotCalculator::getOrCreateSlot(const Type* T) {
00726   int SlotNo = getSlot(T);        // Check to see if it's already in!
00727   if (SlotNo != -1) return SlotNo;
00728   return insertType(T);
00729 }
00730 
00731 int SlotCalculator::insertValue(const Value *D, bool dontIgnore) {
00732   assert(D && "Can't insert a null value!");
00733   assert(getSlot(D) == -1 && "Value is already in the table!");
00734 
00735   // If we are building a compaction map, and if this plane is being compacted,
00736   // insert the value into the compaction map, not into the global map.
00737   if (!CompactionNodeMap.empty()) {
00738     if (D->getType() == Type::VoidTy) return -1;  // Do not insert void values
00739     assert(!isa<Constant>(D) &&
00740            "Types, constants, and globals should be in global table!");
00741 
00742     int Plane = getSlot(D->getType());
00743     assert(Plane != -1 && CompactionTable.size() > (unsigned)Plane &&
00744            "Didn't find value type!");
00745     if (!CompactionTable[Plane].empty())
00746       return getOrCreateCompactionTableSlot(D);
00747   }
00748 
00749   // If this node does not contribute to a plane, or if the node has a 
00750   // name and we don't want names, then ignore the silly node... Note that types
00751   // do need slot numbers so that we can keep track of where other values land.
00752   //
00753   if (!dontIgnore)                               // Don't ignore nonignorables!
00754     if (D->getType() == Type::VoidTy ) {         // Ignore void type nodes
00755       SC_DEBUG("ignored value " << *D << "\n");
00756       return -1;                  // We do need types unconditionally though
00757     }
00758 
00759   // Okay, everything is happy, actually insert the silly value now...
00760   return doInsertValue(D);
00761 }
00762 
00763 int SlotCalculator::insertType(const Type *Ty, bool dontIgnore) {
00764   assert(Ty && "Can't insert a null type!");
00765   assert(getSlot(Ty) == -1 && "Type is already in the table!");
00766 
00767   // If we are building a compaction map, and if this plane is being compacted,
00768   // insert the value into the compaction map, not into the global map.
00769   if (!CompactionTypeMap.empty()) {
00770     getOrCreateCompactionTableSlot(Ty);
00771   }
00772 
00773   // Insert the current type before any subtypes.  This is important because
00774   // recursive types elements are inserted in a bottom up order.  Changing
00775   // this here can break things.  For example:
00776   //
00777   //    global { \2 * } { { \2 }* null }
00778   //
00779   int ResultSlot = doInsertType(Ty);
00780   SC_DEBUG("  Inserted type: " << Ty->getDescription() << " slot=" <<
00781            ResultSlot << "\n");
00782 
00783   // Loop over any contained types in the definition... in post
00784   // order.
00785   for (po_iterator<const Type*> I = po_begin(Ty), E = po_end(Ty);
00786        I != E; ++I) {
00787     if (*I != Ty) {
00788       const Type *SubTy = *I;
00789       // If we haven't seen this sub type before, add it to our type table!
00790       if (getSlot(SubTy) == -1) {
00791         SC_DEBUG("  Inserting subtype: " << SubTy->getDescription() << "\n");
00792         doInsertType(SubTy);
00793         SC_DEBUG("  Inserted subtype: " << SubTy->getDescription() << "\n");
00794       }
00795     }
00796   }
00797   return ResultSlot;
00798 }
00799 
00800 // doInsertValue - This is a small helper function to be called only
00801 // be insertValue.
00802 //
00803 int SlotCalculator::doInsertValue(const Value *D) {
00804   const Type *Typ = D->getType();
00805   unsigned Ty;
00806 
00807   // Used for debugging DefSlot=-1 assertion...
00808   //if (Typ == Type::TypeTy)
00809   //  cerr << "Inserting type '" << cast<Type>(D)->getDescription() << "'!\n";
00810 
00811   if (Typ->isDerivedType()) {
00812     int ValSlot;
00813     if (CompactionTable.empty())
00814       ValSlot = getSlot(Typ);
00815     else
00816       ValSlot = getGlobalSlot(Typ);
00817     if (ValSlot == -1) {                // Have we already entered this type?
00818       // Nope, this is the first we have seen the type, process it.
00819       ValSlot = insertType(Typ, true);
00820       assert(ValSlot != -1 && "ProcessType returned -1 for a type?");
00821     }
00822     Ty = (unsigned)ValSlot;
00823   } else {
00824     Ty = Typ->getTypeID();
00825   }
00826   
00827   if (Table.size() <= Ty)    // Make sure we have the type plane allocated...
00828     Table.resize(Ty+1, TypePlane());
00829 
00830   // If this is the first value to get inserted into the type plane, make sure
00831   // to insert the implicit null value...
00832   if (Table[Ty].empty() &&  hasNullValue(Ty)) {
00833     Value *ZeroInitializer = Constant::getNullValue(Typ);
00834 
00835     // If we are pushing zeroinit, it will be handled below.
00836     if (D != ZeroInitializer) {
00837       Table[Ty].push_back(ZeroInitializer);
00838       NodeMap[ZeroInitializer] = 0;
00839     }
00840   }
00841 
00842   // Insert node into table and NodeMap...
00843   unsigned DestSlot = NodeMap[D] = Table[Ty].size();
00844   Table[Ty].push_back(D);
00845 
00846   SC_DEBUG("  Inserting value [" << Ty << "] = " << D << " slot=" << 
00847            DestSlot << " [");
00848   // G = Global, C = Constant, T = Type, F = Function, o = other
00849   SC_DEBUG((isa<GlobalVariable>(D) ? "G" : (isa<Constant>(D) ? "C" : 
00850            (isa<Function>(D) ? "F" : "o"))));
00851   SC_DEBUG("]\n");
00852   return (int)DestSlot;
00853 }
00854 
00855 // doInsertType - This is a small helper function to be called only
00856 // be insertType.
00857 //
00858 int SlotCalculator::doInsertType(const Type *Ty) {
00859 
00860   // Insert node into table and NodeMap...
00861   unsigned DestSlot = TypeMap[Ty] = Types.size();
00862   Types.push_back(Ty);
00863 
00864   SC_DEBUG("  Inserting type [" << DestSlot << "] = " << Ty << "\n" );
00865   return (int)DestSlot;
00866 }
00867 
00868 // vim: sw=2 ai