lib/Bytecode/Writer/SlotCalculator.cpp

   1 //===-- SlotCalculator.cpp - Calculate what slots values land in ----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   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.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements a useful analysis step to figure out what numbered
  11 // slots values in a program will land in (keeping track of per plane
  12 // information as required.
  13 //
  14 // This is used primarily for when writing a file to disk, either in bytecode
  15 // or source format.
  16 //
  17 //===----------------------------------------------------------------------===//
  18
  19 #include "llvm/SlotCalculator.h"
  20 #include "llvm/Analysis/ConstantsScanner.h"
  21 #include "llvm/Constants.h"
  22 #include "llvm/DerivedTypes.h"
  23 #include "llvm/iOther.h"
  24 #include "llvm/Module.h"
  25 #include "llvm/SymbolTable.h"
  26 #include "Support/PostOrderIterator.h"
  27 #include "Support/STLExtras.h"
  28 #include <algorithm>
  29 using namespace llvm;
  30
  31 #if 0
  32 #define SC_DEBUG(X) std::cerr << X
  33 #else
  34 #define SC_DEBUG(X)
  35 #endif
  36
  37 SlotCalculator::SlotCalculator(const Module *M, bool buildBytecodeInfo) {
  38   BuildBytecodeInfo = buildBytecodeInfo;
  39   ModuleContainsAllFunctionConstants = false;
  40   TheModule = M;
  41
  42   // Preload table... Make sure that all of the primitive types are in the table
  43   // and that their Primitive ID is equal to their slot #
  44   //
  45   SC_DEBUG("Inserting primitive types:\n");
  46   for (unsigned i = 0; i < Type::FirstDerivedTyID; ++i) {
  47     assert(Type::getPrimitiveType((Type::PrimitiveID)i));
  48     insertValue(Type::getPrimitiveType((Type::PrimitiveID)i), true);
  49   }
  50
  51   if (M == 0) return;   // Empty table...
  52   processModule();
  53 }
  54
  55 SlotCalculator::SlotCalculator(const Function *M, bool buildBytecodeInfo) {
  56   BuildBytecodeInfo = buildBytecodeInfo;
  57   ModuleContainsAllFunctionConstants = false;
  58   TheModule = M ? M->getParent() : 0;
  59
  60   // Preload table... Make sure that all of the primitive types are in the table
  61   // and that their Primitive ID is equal to their slot #
  62   //
  63   SC_DEBUG("Inserting primitive types:\n");
  64   for (unsigned i = 0; i < Type::FirstDerivedTyID; ++i) {
  65     assert(Type::getPrimitiveType((Type::PrimitiveID)i));
  66     insertValue(Type::getPrimitiveType((Type::PrimitiveID)i), true);
  67   }
  68
  69   if (TheModule == 0) return;   // Empty table...
  70
  71   processModule();              // Process module level stuff
  72   incorporateFunction(M);         // Start out in incorporated state
  73 }
  74
  75 unsigned SlotCalculator::getGlobalSlot(const Value *V) const {
  76   assert(!CompactionTable.empty() &&
  77          "This method can only be used when compaction is enabled!");
  78   if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V))
  79     V = CPR->getValue();
  80   std::map<const Value*, unsigned>::const_iterator I = NodeMap.find(V);
  81   assert(I != NodeMap.end() && "Didn't find entry!");
  82   return I->second;
  83 }
  84
  85
  86
  87 // processModule - Process all of the module level function declarations and
  88 // types that are available.
  89 //
  90 void SlotCalculator::processModule() {
  91   SC_DEBUG("begin processModule!\n");
  92
  93   // Add all of the global variables to the value table...
  94   //
  95   for (Module::const_giterator I = TheModule->gbegin(), E = TheModule->gend();
  96        I != E; ++I)
  97     getOrCreateSlot(I);
  98
  99   // Scavenge the types out of the functions, then add the functions themselves
 100   // to the value table...
 101   //
 102   for (Module::const_iterator I = TheModule->begin(), E = TheModule->end();
 103        I != E; ++I)
 104     getOrCreateSlot(I);
 105
 106   // Add all of the module level constants used as initializers
 107   //
 108   for (Module::const_giterator I = TheModule->gbegin(), E = TheModule->gend();
 109        I != E; ++I)
 110     if (I->hasInitializer())
 111       getOrCreateSlot(I->getInitializer());
 112
 113   // Now that all global constants have been added, rearrange constant planes
 114   // that contain constant strings so that the strings occur at the start of the
 115   // plane, not somewhere in the middle.
 116   //
 117   if (BuildBytecodeInfo) {
 118     TypePlane &Types = Table[Type::TypeTyID];
 119     for (unsigned plane = 0, e = Table.size(); plane != e; ++plane) {
 120       if (const ArrayType *AT = dyn_cast<ArrayType>(Types[plane]))
 121         if (AT->getElementType() == Type::SByteTy ||
 122             AT->getElementType() == Type::UByteTy) {
 123           TypePlane &Plane = Table[plane];
 124           unsigned FirstNonStringID = 0;
 125           for (unsigned i = 0, e = Plane.size(); i != e; ++i)
 126             if (cast<ConstantArray>(Plane[i])->isString()) {
 127               // Check to see if we have to shuffle this string around.  If not,
 128               // don't do anything.
 129               if (i != FirstNonStringID) {
 130                 // Swap the plane entries....
 131                 std::swap(Plane[i], Plane[FirstNonStringID]);
 132
 133                 // Keep the NodeMap up to date.
 134                 NodeMap[Plane[i]] = i;
 135                 NodeMap[Plane[FirstNonStringID]] = FirstNonStringID;
 136               }
 137               ++FirstNonStringID;
 138             }
 139         }
 140     }
 141   }
 142
 143   // If we are emitting a bytecode file, scan all of the functions for their
 144   // constants, which allows us to emit more compact modules.  This is optional,
 145   // and is just used to compactify the constants used by different functions
 146   // together.
 147   //
 148   // This functionality is completely optional for the bytecode writer, but
 149   // tends to produce smaller bytecode files.  This should not be used in the
 150   // future by clients that want to, for example, build and emit functions on
 151   // the fly.  For now, however, it is unconditionally enabled when building
 152   // bytecode information.
 153   //
 154   if (BuildBytecodeInfo) {
 155     ModuleContainsAllFunctionConstants = true;
 156
 157     SC_DEBUG("Inserting function constants:\n");
 158     for (Module::const_iterator F = TheModule->begin(), E = TheModule->end();
 159          F != E; ++F) {
 160       for (const_inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I){
 161         for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op)
 162           if (isa<Constant>(I->getOperand(op)))
 163             getOrCreateSlot(I->getOperand(op));
 164         getOrCreateSlot(I->getType());
 165         if (const VANextInst *VAN = dyn_cast<VANextInst>(*I))
 166           getOrCreateSlot(VAN->getArgType());
 167       }
 168       processSymbolTableConstants(&F->getSymbolTable());
 169     }
 170
 171
 172   }
 173
 174   // Insert constants that are named at module level into the slot pool so that
 175   // the module symbol table can refer to them...
 176   //
 177   if (BuildBytecodeInfo) {
 178     SC_DEBUG("Inserting SymbolTable values:\n");
 179     processSymbolTable(&TheModule->getSymbolTable());
 180   }
 181
 182   // Now that we have collected together all of the information relevant to the
 183   // module, compactify the type table if it is particularly big and outputting
 184   // a bytecode file.  The basic problem we run into is that some programs have
 185   // a large number of types, which causes the type field to overflow its size,
 186   // which causes instructions to explode in size (particularly call
 187   // instructions).  To avoid this behavior, we "sort" the type table so that
 188   // all non-value types are pushed to the end of the type table, giving nice
 189   // low numbers to the types that can be used by instructions, thus reducing
 190   // the amount of explodage we suffer.
 191   if (BuildBytecodeInfo && Table[Type::TypeTyID].size() >= 64) {
 192     // Scan through the type table moving value types to the start of the table.
 193     TypePlane *Types = &Table[Type::TypeTyID];
 194     unsigned FirstNonValueTypeID = 0;
 195     for (unsigned i = 0, e = Types->size(); i != e; ++i)
 196       if (cast<Type>((*Types)[i])->isFirstClassType() ||
 197           cast<Type>((*Types)[i])->isPrimitiveType()) {
 198         // Check to see if we have to shuffle this type around.  If not, don't
 199         // do anything.
 200         if (i != FirstNonValueTypeID) {
 201           assert(i != Type::TypeTyID && FirstNonValueTypeID != Type::TypeTyID &&
 202                  "Cannot move around the type plane!");
 203
 204           // Swap the type ID's.
 205           std::swap((*Types)[i], (*Types)[FirstNonValueTypeID]);
 206
 207           // Keep the NodeMap up to date.
 208           NodeMap[(*Types)[i]] = i;
 209           NodeMap[(*Types)[FirstNonValueTypeID]] = FirstNonValueTypeID;
 210
 211           // When we move a type, make sure to move its value plane as needed.
 212           if (Table.size() > FirstNonValueTypeID) {
 213             if (Table.size() <= i) Table.resize(i+1);
 214             std::swap(Table[i], Table[FirstNonValueTypeID]);
 215             Types = &Table[Type::TypeTyID];
 216           }
 217         }
 218         ++FirstNonValueTypeID;
 219       }
 220   }
 221
 222   SC_DEBUG("end processModule!\n");
 223 }
 224
 225 // processSymbolTable - Insert all of the values in the specified symbol table
 226 // into the values table...
 227 //
 228 void SlotCalculator::processSymbolTable(const SymbolTable *ST) {
 229   for (SymbolTable::const_iterator I = ST->begin(), E = ST->end(); I != E; ++I)
 230     for (SymbolTable::type_const_iterator TI = I->second.begin(),
 231            TE = I->second.end(); TI != TE; ++TI)
 232       getOrCreateSlot(TI->second);
 233 }
 234
 235 void SlotCalculator::processSymbolTableConstants(const SymbolTable *ST) {
 236   for (SymbolTable::const_iterator I = ST->begin(), E = ST->end(); I != E; ++I)
 237     for (SymbolTable::type_const_iterator TI = I->second.begin(),
 238            TE = I->second.end(); TI != TE; ++TI)
 239       if (isa<Constant>(TI->second) || isa<Type>(TI->second))
 240         getOrCreateSlot(TI->second);
 241 }
 242
 243
 244 void SlotCalculator::incorporateFunction(const Function *F) {
 245   assert(ModuleLevel.size() == 0 && "Module already incorporated!");
 246
 247   SC_DEBUG("begin processFunction!\n");
 248
 249   // If we emitted all of the function constants, build a compaction table.
 250   if (BuildBytecodeInfo && ModuleContainsAllFunctionConstants)
 251     buildCompactionTable(F);
 252   else {
 253     // Save the Table state before we process the function...
 254     for (unsigned i = 0, e = Table.size(); i != e; ++i)
 255       ModuleLevel.push_back(Table[i].size());
 256   }
 257
 258   // Iterate over function arguments, adding them to the value table...
 259   for(Function::const_aiterator I = F->abegin(), E = F->aend(); I != E; ++I)
 260     getOrCreateSlot(I);
 261
 262   if (BuildBytecodeInfo &&              // Assembly writer does not need this!
 263       !ModuleContainsAllFunctionConstants) {
 264     // Iterate over all of the instructions in the function, looking for
 265     // constant values that are referenced.  Add these to the value pools
 266     // before any nonconstant values.  This will be turned into the constant
 267     // pool for the bytecode writer.
 268     //
 269
 270     // Emit all of the constants that are being used by the instructions in
 271     // the function...
 272     for_each(constant_begin(F), constant_end(F),
 273              bind_obj(this, &SlotCalculator::getOrCreateSlot));
 274
 275     // If there is a symbol table, it is possible that the user has names for
 276     // constants that are not being used.  In this case, we will have problems
 277     // if we don't emit the constants now, because otherwise we will get
 278     // symbol table references to constants not in the output.  Scan for these
 279     // constants now.
 280     //
 281     processSymbolTableConstants(&F->getSymbolTable());
 282   }
 283
 284   SC_DEBUG("Inserting Instructions:\n");
 285
 286   // Add all of the instructions to the type planes...
 287   for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
 288     getOrCreateSlot(BB);
 289     for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I) {
 290       getOrCreateSlot(I);
 291       if (const VANextInst *VAN = dyn_cast<VANextInst>(I))
 292         getOrCreateSlot(VAN->getArgType());
 293     }
 294   }
 295
 296   SC_DEBUG("end processFunction!\n");
 297 }
 298
 299 void SlotCalculator::purgeFunction() {
 300   assert(ModuleLevel.size() != 0 && "Module not incorporated!");
 301   unsigned NumModuleTypes = ModuleLevel.size();
 302
 303   SC_DEBUG("begin purgeFunction!\n");
 304
 305   // First, free the compaction map if used.
 306   CompactionNodeMap.clear();
 307
 308   // Next, remove values from existing type planes
 309   for (unsigned i = 0; i != NumModuleTypes; ++i)
 310     if (i >= CompactionTable.size() || CompactionTable[i].empty()) {
 311       unsigned ModuleSize = ModuleLevel[i];// Size of plane before function came
 312       TypePlane &CurPlane = Table[i];
 313
 314       while (CurPlane.size() != ModuleSize) {
 315         std::map<const Value *, unsigned>::iterator NI =
 316           NodeMap.find(CurPlane.back());
 317         assert(NI != NodeMap.end() && "Node not in nodemap?");
 318         NodeMap.erase(NI);       // Erase from nodemap
 319         CurPlane.pop_back();     // Shrink plane
 320       }
 321     }
 322
 323   // We don't need this state anymore, free it up.
 324   ModuleLevel.clear();
 325
 326   if (!CompactionTable.empty()) {
 327     CompactionTable.clear();
 328   } else {
 329     //  FIXME: this will require adjustment when we don't compact everything.
 330
 331     // Finally, remove any type planes defined by the function...
 332     while (NumModuleTypes != Table.size()) {
 333       TypePlane &Plane = Table.back();
 334       SC_DEBUG("Removing Plane " << (Table.size()-1) << " of size "
 335                << Plane.size() << "\n");
 336       while (Plane.size()) {
 337         NodeMap.erase(NodeMap.find(Plane.back()));   // Erase from nodemap
 338         Plane.pop_back();                            // Shrink plane
 339       }
 340
 341       Table.pop_back();                    // Nuke the plane, we don't like it.
 342     }
 343   }
 344   SC_DEBUG("end purgeFunction!\n");
 345 }
 346
 347 static inline bool hasNullValue(unsigned TyID) {
 348   return TyID != Type::LabelTyID && TyID != Type::TypeTyID &&
 349          TyID != Type::VoidTyID;
 350 }
 351
 352 /// getOrCreateCompactionTableSlot - This method is used to build up the initial
 353 /// approximation of the compaction table.
 354 unsigned SlotCalculator::getOrCreateCompactionTableSlot(const Value *V) {
 355   std::map<const Value*, unsigned>::iterator I =
 356     CompactionNodeMap.lower_bound(V);
 357   if (I != CompactionNodeMap.end() && I->first == V)
 358     return I->second;  // Already exists?
 359
 360   // Make sure the type is in the table.
 361   unsigned Ty = getOrCreateCompactionTableSlot(V->getType());
 362   if (CompactionTable.size() <= Ty)
 363     CompactionTable.resize(Ty+1);
 364
 365   assert(!isa<Type>(V) || ModuleLevel.empty());
 366
 367   TypePlane &TyPlane = CompactionTable[Ty];
 368
 369   // Make sure to insert the null entry if the thing we are inserting is not a
 370   // null constant.
 371   if (TyPlane.empty() && hasNullValue(V->getType()->getPrimitiveID())) {
 372     Value *ZeroInitializer = Constant::getNullValue(V->getType());
 373     if (V != ZeroInitializer) {
 374       TyPlane.push_back(ZeroInitializer);
 375       CompactionNodeMap[ZeroInitializer] = 0;
 376     }
 377   }
 378
 379   unsigned SlotNo = TyPlane.size();
 380   TyPlane.push_back(V);
 381   CompactionNodeMap.insert(std::make_pair(V, SlotNo));
 382   return SlotNo;
 383 }
 384
 385
 386 /// buildCompactionTable - Since all of the function constants and types are
 387 /// stored in the module-level constant table, we don't need to emit a function
 388 /// constant table.  Also due to this, the indices for various constants and
 389 /// types might be very large in large programs.  In order to avoid blowing up
 390 /// the size of instructions in the bytecode encoding, we build a compaction
 391 /// table, which defines a mapping from function-local identifiers to global
 392 /// identifiers.
 393 void SlotCalculator::buildCompactionTable(const Function *F) {
 394   assert(CompactionNodeMap.empty() && "Compaction table already built!");
 395   // First step, insert the primitive types.
 396   CompactionTable.resize(Type::TypeTyID+1);
 397   for (unsigned i = 0; i != Type::FirstDerivedTyID; ++i) {
 398     const Type *PrimTy = Type::getPrimitiveType((Type::PrimitiveID)i);
 399     CompactionTable[Type::TypeTyID].push_back(PrimTy);
 400     CompactionNodeMap[PrimTy] = i;
 401   }
 402
 403   // Next, include any types used by function arguments.
 404   for (Function::const_aiterator I = F->abegin(), E = F->aend(); I != E; ++I)
 405     getOrCreateCompactionTableSlot(I->getType());
 406
 407   // Next, find all of the types and values that are referred to by the
 408   // instructions in the program.
 409   for (const_inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
 410     getOrCreateCompactionTableSlot(I->getType());
 411     for (unsigned op = 0, e = I->getNumOperands(); op != e; ++op)
 412       if (isa<Constant>(I->getOperand(op)) ||
 413           isa<GlobalValue>(I->getOperand(op)))
 414         getOrCreateCompactionTableSlot(I->getOperand(op));
 415     if (const VANextInst *VAN = dyn_cast<VANextInst>(*I))
 416       getOrCreateCompactionTableSlot(VAN->getArgType());
 417   }
 418
 419   const SymbolTable &ST = F->getSymbolTable();
 420   for (SymbolTable::const_iterator I = ST.begin(), E = ST.end(); I != E; ++I)
 421     for (SymbolTable::type_const_iterator TI = I->second.begin(),
 422            TE = I->second.end(); TI != TE; ++TI)
 423       if (isa<Constant>(TI->second) || isa<Type>(TI->second) ||
 424           isa<GlobalValue>(TI->second))
 425         getOrCreateCompactionTableSlot(TI->second);
 426
 427   // Now that we have all of the values in the table, and know what types are
 428   // referenced, make sure that there is at least the zero initializer in any
 429   // used type plane.  Since the type was used, we will be emitting instructions
 430   // to the plane even if there are no constants in it.
 431   CompactionTable.resize(CompactionTable[Type::TypeTyID].size());
 432   for (unsigned i = 0, e = CompactionTable.size(); i != e; ++i)
 433     if (CompactionTable[i].empty() && i != Type::VoidTyID &&
 434         i != Type::LabelTyID) {
 435       const Type *Ty = cast<Type>(CompactionTable[Type::TypeTyID][i]);
 436       getOrCreateCompactionTableSlot(Constant::getNullValue(Ty));
 437     }
 438
 439   // Okay, now at this point, we have a legal compaction table.  Since we want
 440   // to emit the smallest possible binaries, we delete planes that do not NEED
 441   // to be compacted, starting with the type plane.
 442
 443
 444   // If decided not to compact anything, do not modify ModuleLevels.
 445   if (CompactionTable.empty())
 446     // FIXME: must update ModuleLevel.
 447     return;
 448
 449   // Finally, for any planes that we have decided to compact, update the
 450   // ModuleLevel entries to be accurate.
 451
 452   // FIXME: This does not yet work for partially compacted tables.
 453   ModuleLevel.resize(CompactionTable.size());
 454   for (unsigned i = 0, e = CompactionTable.size(); i != e; ++i)
 455     ModuleLevel[i] = CompactionTable[i].size();
 456 }
 457
 458 int SlotCalculator::getSlot(const Value *V) const {
 459   // If there is a CompactionTable active...
 460   if (!CompactionNodeMap.empty()) {
 461     std::map<const Value*, unsigned>::const_iterator I =
 462       CompactionNodeMap.find(V);
 463     if (I != CompactionNodeMap.end())
 464       return (int)I->second;
 465     return -1;
 466   }
 467
 468   std::map<const Value*, unsigned>::const_iterator I = NodeMap.find(V);
 469   if (I != NodeMap.end())
 470     return (int)I->second;
 471
 472   // Do not number ConstantPointerRef's at all.  They are an abomination.
 473   if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V))
 474     return getSlot(CPR->getValue());
 475
 476   return -1;
 477 }
 478
 479
 480 int SlotCalculator::getOrCreateSlot(const Value *V) {
 481   int SlotNo = getSlot(V);        // Check to see if it's already in!
 482   if (SlotNo != -1) return SlotNo;
 483
 484   // Do not number ConstantPointerRef's at all.  They are an abomination.
 485   if (const ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(V))
 486     return getOrCreateSlot(CPR->getValue());
 487
 488   if (!isa<GlobalValue>(V))  // Initializers for globals are handled explicitly
 489     if (const Constant *C = dyn_cast<Constant>(V)) {
 490       assert(CompactionNodeMap.empty() &&
 491              "All needed constants should be in the compaction map already!");
 492
 493       // If we are emitting a bytecode file, do not index the characters that
 494       // make up constant strings.  We emit constant strings as special
 495       // entities that don't require their individual characters to be emitted.
 496       if (!BuildBytecodeInfo || !isa<ConstantArray>(C) ||
 497           !cast<ConstantArray>(C)->isString()) {
 498         // This makes sure that if a constant has uses (for example an array of
 499         // const ints), that they are inserted also.
 500         //
 501         for (User::const_op_iterator I = C->op_begin(), E = C->op_end();
 502              I != E; ++I)
 503           getOrCreateSlot(*I);
 504       } else {
 505         assert(ModuleLevel.empty() &&
 506                "How can a constant string be directly accessed in a function?");
 507         // Otherwise, if we are emitting a bytecode file and this IS a string,
 508         // remember it.
 509         if (!C->isNullValue())
 510           ConstantStrings.push_back(cast<ConstantArray>(C));
 511       }
 512     }
 513
 514   return insertValue(V);
 515 }
 516
 517
 518 int SlotCalculator::insertValue(const Value *D, bool dontIgnore) {
 519   assert(D && "Can't insert a null value!");
 520   assert(getSlot(D) == -1 && "Value is already in the table!");
 521
 522   // If we are building a compaction map, and if this plane is being compacted,
 523   // insert the value into the compaction map, not into the global map.
 524   if (!CompactionNodeMap.empty()) {
 525     if (D->getType() == Type::VoidTy) return -1;  // Do not insert void values
 526     assert(!isa<Type>(D) && !isa<Constant>(D) && !isa<GlobalValue>(D) &&
 527            "Types, constants, and globals should be in global SymTab!");
 528
 529     // FIXME: this does not yet handle partially compacted tables yet!
 530     return getOrCreateCompactionTableSlot(D);
 531   }
 532
 533   // If this node does not contribute to a plane, or if the node has a
 534   // name and we don't want names, then ignore the silly node... Note that types
 535   // do need slot numbers so that we can keep track of where other values land.
 536   //
 537   if (!dontIgnore)                               // Don't ignore nonignorables!
 538     if (D->getType() == Type::VoidTy ||          // Ignore void type nodes
 539         (!BuildBytecodeInfo &&                   // Ignore named and constants
 540          (D->hasName() || isa<Constant>(D)) && !isa<Type>(D))) {
 541       SC_DEBUG("ignored value " << *D << "\n");
 542       return -1;                  // We do need types unconditionally though
 543     }
 544
 545   // If it's a type, make sure that all subtypes of the type are included...
 546   if (const Type *TheTy = dyn_cast<Type>(D)) {
 547
 548     // Insert the current type before any subtypes.  This is important because
 549     // recursive types elements are inserted in a bottom up order.  Changing
 550     // this here can break things.  For example:
 551     //
 552     //    global { \2 * } { { \2 }* null }
 553     //
 554     int ResultSlot = doInsertValue(TheTy);
 555     SC_DEBUG("  Inserted type: " << TheTy->getDescription() << " slot=" <<
 556              ResultSlot << "\n");
 557
 558     // Loop over any contained types in the definition... in post
 559     // order.
 560     //
 561     for (po_iterator<const Type*> I = po_begin(TheTy), E = po_end(TheTy);
 562          I != E; ++I) {
 563       if (*I != TheTy) {
 564         const Type *SubTy = *I;
 565         // If we haven't seen this sub type before, add it to our type table!
 566         if (getSlot(SubTy) == -1) {
 567           SC_DEBUG("  Inserting subtype: " << SubTy->getDescription() << "\n");
 568           int Slot = doInsertValue(SubTy);
 569           SC_DEBUG("  Inserted subtype: " << SubTy->getDescription() <<
 570                    " slot=" << Slot << "\n");
 571         }
 572       }
 573     }
 574     return ResultSlot;
 575   }
 576
 577   // Okay, everything is happy, actually insert the silly value now...
 578   return doInsertValue(D);
 579 }
 580
 581 // doInsertValue - This is a small helper function to be called only
 582 // be insertValue.
 583 //
 584 int SlotCalculator::doInsertValue(const Value *D) {
 585   const Type *Typ = D->getType();
 586   unsigned Ty;
 587
 588   // Used for debugging DefSlot=-1 assertion...
 589   //if (Typ == Type::TypeTy)
 590   //  cerr << "Inserting type '" << cast<Type>(D)->getDescription() << "'!\n";
 591
 592   if (Typ->isDerivedType()) {
 593     int ValSlot = getSlot(Typ);
 594     if (ValSlot == -1) {                // Have we already entered this type?
 595       // Nope, this is the first we have seen the type, process it.
 596       ValSlot = insertValue(Typ, true);
 597       assert(ValSlot != -1 && "ProcessType returned -1 for a type?");
 598     }
 599     Ty = (unsigned)ValSlot;
 600   } else {
 601     Ty = Typ->getPrimitiveID();
 602   }
 603
 604   if (Table.size() <= Ty)    // Make sure we have the type plane allocated...
 605     Table.resize(Ty+1, TypePlane());
 606
 607   // If this is the first value to get inserted into the type plane, make sure
 608   // to insert the implicit null value...
 609   if (Table[Ty].empty() && BuildBytecodeInfo && hasNullValue(Ty)) {
 610     Value *ZeroInitializer = Constant::getNullValue(Typ);
 611
 612     // If we are pushing zeroinit, it will be handled below.
 613     if (D != ZeroInitializer) {
 614       Table[Ty].push_back(ZeroInitializer);
 615       NodeMap[ZeroInitializer] = 0;
 616     }
 617   }
 618
 619   // Insert node into table and NodeMap...
 620   unsigned DestSlot = NodeMap[D] = Table[Ty].size();
 621   Table[Ty].push_back(D);
 622
 623   SC_DEBUG("  Inserting value [" << Ty << "] = " << D << " slot=" <<
 624            DestSlot << " [");
 625   // G = Global, C = Constant, T = Type, F = Function, o = other
 626   SC_DEBUG((isa<GlobalVariable>(D) ? "G" : (isa<Constant>(D) ? "C" :
 627            (isa<Type>(D) ? "T" : (isa<Function>(D) ? "F" : "o")))));
 628   SC_DEBUG("]\n");
 629   return (int)DestSlot;
 630 }