lib/Bytecode/Writer/SlotCalculator.cpp

   1 //===-- SlotCalculator.cpp - Calculate what slots values land in ------------=//
   2 //
   3 // This file implements a useful analysis step to figure out what numbered
   4 // slots values in a program will land in (keeping track of per plane
   5 // information as required.
   6 //
   7 // This is used primarily for when writing a file to disk, either in bytecode
   8 // or source format.
   9 //
  10 //===----------------------------------------------------------------------===//
  11
  12 #include "llvm/Analysis/SlotCalculator.h"
  13 #include "llvm/Analysis/ConstantsScanner.h"
  14 #include "llvm/Method.h"
  15 #include "llvm/GlobalVariable.h"
  16 #include "llvm/Module.h"
  17 #include "llvm/BasicBlock.h"
  18 #include "llvm/ConstPoolVals.h"
  19 #include "llvm/iOther.h"
  20 #include "llvm/DerivedTypes.h"
  21 #include "llvm/SymbolTable.h"
  22 #include "llvm/Support/STLExtras.h"
  23 #include "llvm/CFG.h"
  24 #include <algorithm>
  25
  26 #if 0
  27 #define SC_DEBUG(X) cerr << X
  28 #else
  29 #define SC_DEBUG(X)
  30 #endif
  31
  32 SlotCalculator::SlotCalculator(const Module *M, bool IgnoreNamed) {
  33   IgnoreNamedNodes = IgnoreNamed;
  34   TheModule = M;
  35
  36   // Preload table... Make sure that all of the primitive types are in the table
  37   // and that their Primitive ID is equal to their slot #
  38   //
  39   for (unsigned i = 0; i < Type::FirstDerivedTyID; ++i) {
  40     assert(Type::getPrimitiveType((Type::PrimitiveID)i));
  41     insertVal(Type::getPrimitiveType((Type::PrimitiveID)i), true);
  42   }
  43
  44   if (M == 0) return;   // Empty table...
  45   processModule();
  46 }
  47
  48 SlotCalculator::SlotCalculator(const Method *M, bool IgnoreNamed) {
  49   IgnoreNamedNodes = IgnoreNamed;
  50   TheModule = M ? M->getParent() : 0;
  51
  52   // Preload table... Make sure that all of the primitive types are in the table
  53   // and that their Primitive ID is equal to their slot #
  54   //
  55   for (unsigned i = 0; i < Type::FirstDerivedTyID; ++i) {
  56     assert(Type::getPrimitiveType((Type::PrimitiveID)i));
  57     insertVal(Type::getPrimitiveType((Type::PrimitiveID)i), true);
  58   }
  59
  60   if (TheModule == 0) return;   // Empty table...
  61
  62   processModule();              // Process module level stuff
  63   incorporateMethod(M);         // Start out in incorporated state
  64 }
  65
  66
  67 // processModule - Process all of the module level method declarations and
  68 // types that are available.
  69 //
  70 void SlotCalculator::processModule() {
  71   SC_DEBUG("begin processModule!\n");
  72
  73   // Add all of the global variables to the value table...
  74   //
  75   for_each(TheModule->gbegin(), TheModule->gend(),
  76            bind_obj(this, &SlotCalculator::insertValue));
  77
  78   // Scavenge the types out of the methods, then add the methods themselves to
  79   // the value table...
  80   //
  81   for_each(TheModule->begin(), TheModule->end(),  // Insert methods...
  82            bind_obj(this, &SlotCalculator::insertValue));
  83
  84   // Insert constants that are named at module level into the slot pool so that
  85   // the module symbol table can refer to them...
  86   //
  87   if (TheModule->hasSymbolTable() && !IgnoreNamedNodes) {
  88     SC_DEBUG("Inserting SymbolTable values:\n");
  89     processSymbolTable(TheModule->getSymbolTable());
  90   }
  91
  92   SC_DEBUG("end processModule!\n");
  93 }
  94
  95 // processSymbolTable - Insert all of the values in the specified symbol table
  96 // into the values table...
  97 //
  98 void SlotCalculator::processSymbolTable(const SymbolTable *ST) {
  99   for (SymbolTable::const_iterator I = ST->begin(), E = ST->end(); I != E; ++I)
 100     for (SymbolTable::type_const_iterator TI = I->second.begin(),
 101            TE = I->second.end(); TI != TE; ++TI)
 102       insertValue(TI->second);
 103 }
 104
 105 void SlotCalculator::processSymbolTableConstants(const SymbolTable *ST) {
 106   for (SymbolTable::const_iterator I = ST->begin(), E = ST->end(); I != E; ++I)
 107     for (SymbolTable::type_const_iterator TI = I->second.begin(),
 108            TE = I->second.end(); TI != TE; ++TI)
 109       if (TI->second->isConstant())
 110         insertValue(TI->second);
 111 }
 112
 113
 114 void SlotCalculator::incorporateMethod(const Method *M) {
 115   assert(ModuleLevel.size() == 0 && "Module already incorporated!");
 116
 117   SC_DEBUG("begin processMethod!\n");
 118
 119   // Save the Table state before we process the method...
 120   for (unsigned i = 0; i < Table.size(); ++i)
 121     ModuleLevel.push_back(Table[i].size());
 122
 123   SC_DEBUG("Inserting method arguments\n");
 124
 125   // Iterate over method arguments, adding them to the value table...
 126   for_each(M->getArgumentList().begin(), M->getArgumentList().end(),
 127            bind_obj(this, &SlotCalculator::insertValue));
 128
 129   // Iterate over all of the instructions in the method, looking for constant
 130   // values that are referenced.  Add these to the value pools before any
 131   // nonconstant values.  This will be turned into the constant pool for the
 132   // bytecode writer.
 133   //
 134   if (!IgnoreNamedNodes) {                // Assembly writer does not need this!
 135     SC_DEBUG("Inserting method constants:\n";
 136              for (constant_iterator I = constant_begin(M), E = constant_end(M);
 137                   I != E; ++I) {
 138                cerr << "  " << I->getType()->getDescription()
 139                     << " " << I->getStrValue() << endl;
 140              });
 141
 142     // Emit all of the constants that are being used by the instructions in the
 143     // method...
 144     for_each(constant_begin(M), constant_end(M),
 145              bind_obj(this, &SlotCalculator::insertValue));
 146
 147     // If there is a symbol table, it is possible that the user has names for
 148     // constants that are not being used.  In this case, we will have problems
 149     // if we don't emit the constants now, because otherwise we will get
 150     // symboltable references to constants not in the output.  Scan for these
 151     // constants now.
 152     //
 153     if (M->hasSymbolTable())
 154       processSymbolTableConstants(M->getSymbolTable());
 155   }
 156
 157   SC_DEBUG("Inserting Labels:\n");
 158
 159   // Iterate over basic blocks, adding them to the value table...
 160   for_each(M->begin(), M->end(),
 161            bind_obj(this, &SlotCalculator::insertValue));
 162
 163   SC_DEBUG("Inserting Instructions:\n");
 164
 165   // Add all of the instructions to the type planes...
 166   for_each(M->inst_begin(), M->inst_end(),
 167            bind_obj(this, &SlotCalculator::insertValue));
 168
 169   if (M->hasSymbolTable() && !IgnoreNamedNodes) {
 170     SC_DEBUG("Inserting SymbolTable values:\n");
 171     processSymbolTable(M->getSymbolTable());
 172   }
 173
 174   SC_DEBUG("end processMethod!\n");
 175 }
 176
 177 void SlotCalculator::purgeMethod() {
 178   assert(ModuleLevel.size() != 0 && "Module not incorporated!");
 179   unsigned NumModuleTypes = ModuleLevel.size();
 180
 181   SC_DEBUG("begin purgeMethod!\n");
 182
 183   // First, remove values from existing type planes
 184   for (unsigned i = 0; i < NumModuleTypes; ++i) {
 185     unsigned ModuleSize = ModuleLevel[i];  // Size of plane before method came
 186     TypePlane &CurPlane = Table[i];
 187     SC_DEBUG("Processing Plane " << i << " of size " << CurPlane.size() <<endl);
 188
 189     while (CurPlane.size() != ModuleSize) {
 190       SC_DEBUG("  Removing [" << i << "] Value=" << CurPlane.back() << "\n");
 191       map<const Value *, unsigned>::iterator NI = NodeMap.find(CurPlane.back());
 192       assert(NI != NodeMap.end() && "Node not in nodemap?");
 193       NodeMap.erase(NI);   // Erase from nodemap
 194       CurPlane.pop_back();                            // Shrink plane
 195     }
 196   }
 197
 198   // We don't need this state anymore, free it up.
 199   ModuleLevel.clear();
 200
 201   // Next, remove any type planes defined by the method...
 202   while (NumModuleTypes != Table.size()) {
 203     TypePlane &Plane = Table.back();
 204     SC_DEBUG("Removing Plane " << (Table.size()-1) << " of size "
 205              << Plane.size() << endl);
 206     while (Plane.size()) {
 207       NodeMap.erase(NodeMap.find(Plane.back()));   // Erase from nodemap
 208       Plane.pop_back();                            // Shrink plane
 209     }
 210
 211     Table.pop_back();                      // Nuke the plane, we don't like it.
 212   }
 213
 214   SC_DEBUG("end purgeMethod!\n");
 215 }
 216
 217 int SlotCalculator::getValSlot(const Value *D) const {
 218   map<const Value*, unsigned>::const_iterator I = NodeMap.find(D);
 219   if (I == NodeMap.end()) return -1;
 220
 221   return (int)I->second;
 222 }
 223
 224
 225 int SlotCalculator::insertValue(const Value *D) {
 226   if (const ConstPoolVal *CPV = D->castConstant()) {
 227     // This makes sure that if a constant has uses (for example an array
 228     // of const ints), that they are inserted also.
 229     //
 230     for_each(CPV->op_begin(), CPV->op_end(),
 231              bind_obj(this, &SlotCalculator::insertValue));
 232   }
 233
 234   int SlotNo = getValSlot(D);        // Check to see if it's already in!
 235   if (SlotNo != -1) return SlotNo;
 236   return insertVal(D);
 237 }
 238
 239
 240 int SlotCalculator::insertVal(const Value *D, bool dontIgnore = false) {
 241   assert(D && "Can't insert a null value!");
 242   assert(getValSlot(D) == -1 && "Value is already in the table!");
 243
 244   // If this node does not contribute to a plane, or if the node has a
 245   // name and we don't want names, then ignore the silly node... Note that types
 246   // do need slot numbers so that we can keep track of where other values land.
 247   //
 248   if (!dontIgnore)                               // Don't ignore nonignorables!
 249     if (D->getType() == Type::VoidTy ||          // Ignore void type nodes
 250         (IgnoreNamedNodes &&                     // Ignore named and constants
 251          (D->hasName() || D->isConstant()) && !D->isType())) {
 252       SC_DEBUG("ignored value " << D << endl);
 253       return -1;                  // We do need types unconditionally though
 254     }
 255
 256   // If it's a type, make sure that all subtypes of the type are included...
 257   if (const Type *TheTy = D->castType()) {
 258     SC_DEBUG("  Inserted type: " << TheTy->getDescription() << endl);
 259
 260     // Loop over any contained types in the definition... in reverse depth first
 261     // order.  This assures that all of the leafs of a type are output before
 262     // the type itself is. This also assures us that we will not hit infinite
 263     // recursion on recursive types...
 264     //
 265     for (cfg::tdf_iterator I = cfg::tdf_begin(TheTy, true),
 266                            E = cfg::tdf_end(TheTy); I != E; ++I)
 267       if (*I != TheTy) {
 268         // If we haven't seen this sub type before, add it to our type table!
 269         const Type *SubTy = *I;
 270         if (getValSlot(SubTy) == -1) {
 271           SC_DEBUG("  Inserting subtype: " << SubTy->getDescription() << endl);
 272           doInsertVal(SubTy);
 273         }
 274       }
 275   }
 276
 277   // Okay, everything is happy, actually insert the silly value now...
 278   return doInsertVal(D);
 279 }
 280
 281
 282 // doInsertVal - This is a small helper function to be called only be insertVal.
 283 //
 284 int SlotCalculator::doInsertVal(const Value *D) {
 285   const Type *Typ = D->getType();
 286   unsigned Ty;
 287
 288   // Used for debugging DefSlot=-1 assertion...
 289   //if (Typ == Type::TypeTy)
 290   //  cerr << "Inserting type '" << D->castTypeAsserting()->getDescription() << "'!\n";
 291
 292   if (Typ->isDerivedType()) {
 293     int DefSlot = getValSlot(Typ);
 294     if (DefSlot == -1) {                // Have we already entered this type?
 295       // Nope, this is the first we have seen the type, process it.
 296       DefSlot = insertVal(Typ, true);
 297       assert(DefSlot != -1 && "ProcessType returned -1 for a type?");
 298     }
 299     Ty = (unsigned)DefSlot;
 300   } else {
 301     Ty = Typ->getPrimitiveID();
 302   }
 303
 304   if (Table.size() <= Ty)    // Make sure we have the type plane allocated...
 305     Table.resize(Ty+1, TypePlane());
 306
 307   SC_DEBUG("  Inserting value [" << Ty << "] = " << D << endl);
 308
 309   // Insert node into table and NodeMap...
 310   unsigned DestSlot = NodeMap[D] = Table[Ty].size();
 311   Table[Ty].push_back(D);
 312
 313   return (int)DestSlot;
 314 }