lib/Bytecode/Writer/Writer.cpp

   1 //===-- Writer.cpp - Library for writing LLVM bytecode files --------------===//
   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 library implements the functionality defined in llvm/Bytecode/Writer.h
  11 //
  12 // Note that this file uses an unusual technique of outputting all the bytecode
  13 // to a deque of unsigned char, then copies the deque to an ostream.  The
  14 // reason for this is that we must do "seeking" in the stream to do back-
  15 // patching, and some very important ostreams that we want to support (like
  16 // pipes) do not support seeking.  :( :( :(
  17 //
  18 // The choice of the deque data structure is influenced by the extremely fast
  19 // "append" speed, plus the free "seek"/replace in the middle of the stream. I
  20 // didn't use a vector because the stream could end up very large and copying
  21 // the whole thing to reallocate would be kinda silly.
  22 //
  23 //===----------------------------------------------------------------------===//
  24
  25 #include "WriterInternals.h"
  26 #include "llvm/Bytecode/WriteBytecodePass.h"
  27 #include "llvm/Constants.h"
  28 #include "llvm/DerivedTypes.h"
  29 #include "llvm/Module.h"
  30 #include "llvm/SymbolTable.h"
  31 #include "Support/STLExtras.h"
  32 #include "Support/Statistic.h"
  33 #include <cstring>
  34 #include <algorithm>
  35 using namespace llvm;
  36
  37 static RegisterPass<WriteBytecodePass> X("emitbytecode", "Bytecode Writer");
  38
  39 static Statistic<>
  40 BytesWritten("bytecodewriter", "Number of bytecode bytes written");
  41 static Statistic<>
  42 ConstantTotalBytes("bytecodewriter", "Bytes of constants total");
  43 static Statistic<>
  44 ConstantPlaneHeaderBytes("bytecodewriter", "Constant plane header bytes");
  45 static Statistic<>
  46 InstructionBytes("bytecodewriter", "Bytes of bytes of instructions");
  47 static Statistic<>
  48 SymTabBytes("bytecodewriter", "Bytes of symbol table");
  49 static Statistic<>
  50 ModuleInfoBytes("bytecodewriter", "Bytes of module info");
  51 static Statistic<>
  52 CompactionTableBytes("bytecodewriter", "Bytes of compaction tables");
  53
  54 BytecodeWriter::BytecodeWriter(std::deque<unsigned char> &o, const Module *M)
  55   : Out(o), Table(M, true) {
  56
  57   // Emit the signature...
  58   static const unsigned char *Sig =  (const unsigned char*)"llvm";
  59   output_data(Sig, Sig+4, Out);
  60
  61   // Emit the top level CLASS block.
  62   BytecodeBlock ModuleBlock(BytecodeFormat::Module, Out);
  63
  64   bool isBigEndian      = M->getEndianness() == Module::BigEndian;
  65   bool hasLongPointers  = M->getPointerSize() == Module::Pointer64;
  66   bool hasNoEndianness  = M->getEndianness() == Module::AnyEndianness;
  67   bool hasNoPointerSize = M->getPointerSize() == Module::AnyPointerSize;
  68
  69   // Output the version identifier... we are currently on bytecode version #1,
  70   // which corresponds to LLVM v1.2.
  71   unsigned Version = (1 << 4) | isBigEndian | (hasLongPointers << 1) |
  72                      (hasNoEndianness << 2) | (hasNoPointerSize << 3);
  73   output_vbr(Version, Out);
  74   align32(Out);
  75
  76   {
  77     BytecodeBlock CPool(BytecodeFormat::GlobalTypePlane, Out);
  78
  79     // Write the type plane for types first because earlier planes (e.g. for a
  80     // primitive type like float) may have constants constructed using types
  81     // coming later (e.g., via getelementptr from a pointer type).  The type
  82     // plane is needed before types can be fwd or bkwd referenced.
  83     const std::vector<const Value*> &Plane = Table.getPlane(Type::TypeTyID);
  84     assert(!Plane.empty() && "No types at all?");
  85     unsigned ValNo = Type::FirstDerivedTyID; // Start at the derived types...
  86     outputConstantsInPlane(Plane, ValNo);      // Write out the types
  87   }
  88
  89   // The ModuleInfoBlock follows directly after the type information
  90   outputModuleInfoBlock(M);
  91
  92   // Output module level constants, used for global variable initializers
  93   outputConstants(false);
  94
  95   // Do the whole module now! Process each function at a time...
  96   for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I)
  97     outputFunction(I);
  98
  99   // If needed, output the symbol table for the module...
 100   outputSymbolTable(M->getSymbolTable());
 101 }
 102
 103 // Helper function for outputConstants().
 104 // Writes out all the constants in the plane Plane starting at entry StartNo.
 105 //
 106 void BytecodeWriter::outputConstantsInPlane(const std::vector<const Value*>
 107                                             &Plane, unsigned StartNo) {
 108   unsigned ValNo = StartNo;
 109
 110   // Scan through and ignore function arguments, global values, and constant
 111   // strings.
 112   for (; ValNo < Plane.size() &&
 113          (isa<Argument>(Plane[ValNo]) || isa<GlobalValue>(Plane[ValNo]) ||
 114           (isa<ConstantArray>(Plane[ValNo]) &&
 115            cast<ConstantArray>(Plane[ValNo])->isString())); ValNo++)
 116     /*empty*/;
 117
 118   unsigned NC = ValNo;              // Number of constants
 119   for (; NC < Plane.size() &&
 120          (isa<Constant>(Plane[NC]) || isa<Type>(Plane[NC])); NC++)
 121     /*empty*/;
 122   NC -= ValNo;                      // Convert from index into count
 123   if (NC == 0) return;              // Skip empty type planes...
 124
 125   // FIXME: Most slabs only have 1 or 2 entries!  We should encode this much
 126   // more compactly.
 127
 128   ConstantPlaneHeaderBytes -= Out.size();
 129
 130   // Output type header: [num entries][type id number]
 131   //
 132   output_vbr(NC, Out);
 133
 134   // Output the Type ID Number...
 135   int Slot = Table.getSlot(Plane.front()->getType());
 136   assert (Slot != -1 && "Type in constant pool but not in function!!");
 137   output_vbr((unsigned)Slot, Out);
 138
 139   ConstantPlaneHeaderBytes += Out.size();
 140
 141
 142   //cerr << "Emitting " << NC << " constants of type '"
 143   //     << Plane.front()->getType()->getName() << "' = Slot #" << Slot << "\n";
 144
 145   for (unsigned i = ValNo; i < ValNo+NC; ++i) {
 146     const Value *V = Plane[i];
 147     if (const Constant *CPV = dyn_cast<Constant>(V)) {
 148       //cerr << "Serializing value: <" << V->getType() << ">: " << V << ":"
 149       //     << Out.size() << "\n";
 150       outputConstant(CPV);
 151     } else {
 152       outputType(cast<Type>(V));
 153     }
 154   }
 155 }
 156
 157 static inline bool hasNullValue(unsigned TyID) {
 158   return TyID != Type::LabelTyID && TyID != Type::TypeTyID &&
 159          TyID != Type::VoidTyID;
 160 }
 161
 162 void BytecodeWriter::outputConstants(bool isFunction) {
 163   ConstantTotalBytes -= Out.size();
 164   BytecodeBlock CPool(BytecodeFormat::ConstantPool, Out,
 165                       true  /* Elide block if empty */);
 166
 167   unsigned NumPlanes = Table.getNumPlanes();
 168
 169   // Output the type plane before any constants!
 170   if (isFunction && NumPlanes > Type::TypeTyID) {
 171     const std::vector<const Value*> &Plane = Table.getPlane(Type::TypeTyID);
 172     if (!Plane.empty()) {              // Skip empty type planes...
 173       unsigned ValNo = Table.getModuleLevel(Type::TypeTyID);
 174       outputConstantsInPlane(Plane, ValNo);
 175     }
 176   }
 177
 178   // Output module-level string constants before any other constants.x
 179   if (!isFunction)
 180     outputConstantStrings();
 181
 182   for (unsigned pno = 0; pno != NumPlanes; pno++)
 183     if (pno != Type::TypeTyID) {         // Type plane handled above.
 184       const std::vector<const Value*> &Plane = Table.getPlane(pno);
 185       if (!Plane.empty()) {              // Skip empty type planes...
 186         unsigned ValNo = 0;
 187         if (isFunction)                  // Don't re-emit module constants
 188           ValNo += Table.getModuleLevel(pno);
 189
 190         if (hasNullValue(pno)) {
 191           // Skip zero initializer
 192           if (ValNo == 0)
 193             ValNo = 1;
 194         }
 195
 196         // Write out constants in the plane
 197         outputConstantsInPlane(Plane, ValNo);
 198       }
 199     }
 200   ConstantTotalBytes += Out.size();
 201 }
 202
 203 static unsigned getEncodedLinkage(const GlobalValue *GV) {
 204   switch (GV->getLinkage()) {
 205   default: assert(0 && "Invalid linkage!");
 206   case GlobalValue::ExternalLinkage:  return 0;
 207   case GlobalValue::WeakLinkage:      return 1;
 208   case GlobalValue::AppendingLinkage: return 2;
 209   case GlobalValue::InternalLinkage:  return 3;
 210   case GlobalValue::LinkOnceLinkage:  return 4;
 211   }
 212 }
 213
 214 void BytecodeWriter::outputModuleInfoBlock(const Module *M) {
 215   ModuleInfoBytes -= Out.size();
 216
 217   BytecodeBlock ModuleInfoBlock(BytecodeFormat::ModuleGlobalInfo, Out);
 218
 219   // Output the types for the global variables in the module...
 220   for (Module::const_giterator I = M->gbegin(), End = M->gend(); I != End;++I) {
 221     int Slot = Table.getSlot(I->getType());
 222     assert(Slot != -1 && "Module global vars is broken!");
 223
 224     // Fields: bit0 = isConstant, bit1 = hasInitializer, bit2-4=Linkage,
 225     // bit5+ = Slot # for type
 226     unsigned oSlot = ((unsigned)Slot << 5) | (getEncodedLinkage(I) << 2) |
 227                      (I->hasInitializer() << 1) | I->isConstant();
 228     output_vbr(oSlot, Out);
 229
 230     // If we have an initializer, output it now.
 231     if (I->hasInitializer()) {
 232       Slot = Table.getSlot((Value*)I->getInitializer());
 233       assert(Slot != -1 && "No slot for global var initializer!");
 234       output_vbr((unsigned)Slot, Out);
 235     }
 236   }
 237   output_vbr((unsigned)Table.getSlot(Type::VoidTy), Out);
 238
 239   // Output the types of the functions in this module...
 240   for (Module::const_iterator I = M->begin(), End = M->end(); I != End; ++I) {
 241     int Slot = Table.getSlot(I->getType());
 242     assert(Slot != -1 && "Module const pool is broken!");
 243     assert(Slot >= Type::FirstDerivedTyID && "Derived type not in range!");
 244     output_vbr((unsigned)Slot, Out);
 245   }
 246   output_vbr((unsigned)Table.getSlot(Type::VoidTy), Out);
 247
 248   ModuleInfoBytes += Out.size();
 249 }
 250
 251 void BytecodeWriter::outputInstructions(const Function *F) {
 252   BytecodeBlock ILBlock(BytecodeFormat::InstructionList, Out);
 253   InstructionBytes -= Out.size();
 254   for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
 255     for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I)
 256       outputInstruction(*I);
 257   InstructionBytes += Out.size();
 258 }
 259
 260 void BytecodeWriter::outputFunction(const Function *F) {
 261   BytecodeBlock FunctionBlock(BytecodeFormat::Function, Out);
 262   output_vbr(getEncodedLinkage(F), Out);
 263
 264   // If this is an external function, there is nothing else to emit!
 265   if (F->isExternal()) return;
 266
 267   // Get slot information about the function...
 268   Table.incorporateFunction(F);
 269
 270   if (Table.getCompactionTable().empty()) {
 271     // Output information about the constants in the function if the compaction
 272     // table is not being used.
 273     outputConstants(true);
 274   } else {
 275     // Otherwise, emit the compaction table.
 276     outputCompactionTable();
 277   }
 278
 279   // Output all of the instructions in the body of the function
 280   outputInstructions(F);
 281
 282   // If needed, output the symbol table for the function...
 283   outputSymbolTable(F->getSymbolTable());
 284
 285   Table.purgeFunction();
 286 }
 287
 288 void BytecodeWriter::outputCompactionTablePlane(unsigned PlaneNo,
 289                                          const std::vector<const Value*> &Plane,
 290                                                 unsigned StartNo) {
 291   unsigned End = Table.getModuleLevel(PlaneNo);
 292   if (StartNo == End || End == 0) return;   // Nothing to emit
 293   assert(StartNo < End && "Cannot emit negative range!");
 294   assert(StartNo < Plane.size() && End <= Plane.size());
 295
 296   // Do not emit the null initializer!
 297   if (PlaneNo != Type::TypeTyID) ++StartNo;
 298
 299   // Figure out which encoding to use.  By far the most common case we have is
 300   // to emit 0-2 entries in a compaction table plane.
 301   switch (End-StartNo) {
 302   case 0:         // Avoid emitting two vbr's if possible.
 303   case 1:
 304   case 2:
 305     output_vbr((PlaneNo << 2) | End-StartNo, Out);
 306     break;
 307   default:
 308     // Output the number of things.
 309     output_vbr((unsigned(End-StartNo) << 2) | 3, Out);
 310     output_vbr(PlaneNo, Out);                 // Emit the type plane this is
 311     break;
 312   }
 313
 314   for (unsigned i = StartNo; i != End; ++i)
 315     output_vbr(Table.getGlobalSlot(Plane[i]), Out);
 316 }
 317
 318 void BytecodeWriter::outputCompactionTable() {
 319   CompactionTableBytes -= Out.size();
 320   BytecodeBlock CTB(BytecodeFormat::CompactionTable, Out, true/*ElideIfEmpty*/);
 321   const std::vector<std::vector<const Value*> > &CT =Table.getCompactionTable();
 322
 323   // First thing is first, emit the type compaction table if there is one.
 324   if (CT.size() > Type::TypeTyID)
 325     outputCompactionTablePlane(Type::TypeTyID, CT[Type::TypeTyID],
 326                                Type::FirstDerivedTyID);
 327
 328   for (unsigned i = 0, e = CT.size(); i != e; ++i)
 329     if (i != Type::TypeTyID)
 330       outputCompactionTablePlane(i, CT[i], 0);
 331   CompactionTableBytes += Out.size();
 332 }
 333
 334 void BytecodeWriter::outputSymbolTable(const SymbolTable &MST) {
 335   // Do not output the Bytecode block for an empty symbol table, it just wastes
 336   // space!
 337   if (MST.begin() == MST.end()) return;
 338
 339   SymTabBytes -= Out.size();
 340
 341   BytecodeBlock SymTabBlock(BytecodeFormat::SymbolTable, Out,
 342                             true/* ElideIfEmpty*/);
 343
 344   for (SymbolTable::const_iterator TI = MST.begin(); TI != MST.end(); ++TI) {
 345     SymbolTable::type_const_iterator I = MST.type_begin(TI->first);
 346     SymbolTable::type_const_iterator End = MST.type_end(TI->first);
 347     int Slot;
 348
 349     if (I == End) continue;  // Don't mess with an absent type...
 350
 351     // Symtab block header: [num entries][type id number]
 352     output_vbr(MST.type_size(TI->first), Out);
 353
 354     Slot = Table.getSlot(TI->first);
 355     assert(Slot != -1 && "Type in symtab, but not in table!");
 356     output_vbr((unsigned)Slot, Out);
 357
 358     for (; I != End; ++I) {
 359       // Symtab entry: [def slot #][name]
 360       Slot = Table.getSlot(I->second);
 361       assert(Slot != -1 && "Value in symtab but has no slot number!!");
 362       output_vbr((unsigned)Slot, Out);
 363       output(I->first, Out, false); // Don't force alignment...
 364     }
 365   }
 366
 367   SymTabBytes += Out.size();
 368 }
 369
 370 void llvm::WriteBytecodeToFile(const Module *C, std::ostream &Out) {
 371   assert(C && "You can't write a null module!!");
 372
 373   std::deque<unsigned char> Buffer;
 374
 375   // This object populates buffer for us...
 376   BytecodeWriter BCW(Buffer, C);
 377
 378   // Keep track of how much we've written...
 379   BytesWritten += Buffer.size();
 380
 381   // Okay, write the deque out to the ostream now... the deque is not
 382   // sequential in memory, however, so write out as much as possible in big
 383   // chunks, until we're done.
 384   //
 385   std::deque<unsigned char>::const_iterator I = Buffer.begin(),E = Buffer.end();
 386   while (I != E) {                           // Loop until it's all written
 387     // Scan to see how big this chunk is...
 388     const unsigned char *ChunkPtr = &*I;
 389     const unsigned char *LastPtr = ChunkPtr;
 390     while (I != E) {
 391       const unsigned char *ThisPtr = &*++I;
 392       if (LastPtr+1 != ThisPtr) {   // Advanced by more than a byte of memory?
 393         ++LastPtr;
 394         break;
 395       }
 396       LastPtr = ThisPtr;
 397     }
 398
 399     // Write out the chunk...
 400     Out.write((char*)ChunkPtr, LastPtr-ChunkPtr);
 401   }
 402
 403   Out.flush();
 404 }