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 vector of unsigned char, then copies the vector 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 //===----------------------------------------------------------------------===//
  19
  20 #define DEBUG_TYPE "bytecodewriter"
  21 #include "WriterInternals.h"
  22 #include "llvm/Bytecode/WriteBytecodePass.h"
  23 #include "llvm/CallingConv.h"
  24 #include "llvm/Constants.h"
  25 #include "llvm/DerivedTypes.h"
  26 #include "llvm/InlineAsm.h"
  27 #include "llvm/Instructions.h"
  28 #include "llvm/Module.h"
  29 #include "llvm/TypeSymbolTable.h"
  30 #include "llvm/ValueSymbolTable.h"
  31 #include "llvm/Support/GetElementPtrTypeIterator.h"
  32 #include "llvm/Support/Compressor.h"
  33 #include "llvm/Support/MathExtras.h"
  34 #include "llvm/Support/Streams.h"
  35 #include "llvm/System/Program.h"
  36 #include "llvm/ADT/STLExtras.h"
  37 #include "llvm/ADT/Statistic.h"
  38 #include <cstring>
  39 #include <algorithm>
  40 using namespace llvm;
  41
  42 /// This value needs to be incremented every time the bytecode format changes
  43 /// so that the reader can distinguish which format of the bytecode file has
  44 /// been written.
  45 /// @brief The bytecode version number
  46 const unsigned BCVersionNum = 7;
  47
  48 static RegisterPass<WriteBytecodePass> X("emitbytecode", "Bytecode Writer");
  49
  50 STATISTIC(BytesWritten, "Number of bytecode bytes written");
  51
  52 //===----------------------------------------------------------------------===//
  53 //===                           Output Primitives                          ===//
  54 //===----------------------------------------------------------------------===//
  55
  56 // output - If a position is specified, it must be in the valid portion of the
  57 // string... note that this should be inlined always so only the relevant IF
  58 // body should be included.
  59 inline void BytecodeWriter::output(unsigned i, int pos) {
  60   if (pos == -1) { // Be endian clean, little endian is our friend
  61     Out.push_back((unsigned char)i);
  62     Out.push_back((unsigned char)(i >> 8));
  63     Out.push_back((unsigned char)(i >> 16));
  64     Out.push_back((unsigned char)(i >> 24));
  65   } else {
  66     Out[pos  ] = (unsigned char)i;
  67     Out[pos+1] = (unsigned char)(i >> 8);
  68     Out[pos+2] = (unsigned char)(i >> 16);
  69     Out[pos+3] = (unsigned char)(i >> 24);
  70   }
  71 }
  72
  73 inline void BytecodeWriter::output(int i) {
  74   output((unsigned)i);
  75 }
  76
  77 /// output_vbr - Output an unsigned value, by using the least number of bytes
  78 /// possible.  This is useful because many of our "infinite" values are really
  79 /// very small most of the time; but can be large a few times.
  80 /// Data format used:  If you read a byte with the high bit set, use the low
  81 /// seven bits as data and then read another byte.
  82 inline void BytecodeWriter::output_vbr(uint64_t i) {
  83   while (1) {
  84     if (i < 0x80) { // done?
  85       Out.push_back((unsigned char)i);   // We know the high bit is clear...
  86       return;
  87     }
  88
  89     // Nope, we are bigger than a character, output the next 7 bits and set the
  90     // high bit to say that there is more coming...
  91     Out.push_back(0x80 | ((unsigned char)i & 0x7F));
  92     i >>= 7;  // Shift out 7 bits now...
  93   }
  94 }
  95
  96 inline void BytecodeWriter::output_vbr(unsigned i) {
  97   while (1) {
  98     if (i < 0x80) { // done?
  99       Out.push_back((unsigned char)i);   // We know the high bit is clear...
 100       return;
 101     }
 102
 103     // Nope, we are bigger than a character, output the next 7 bits and set the
 104     // high bit to say that there is more coming...
 105     Out.push_back(0x80 | ((unsigned char)i & 0x7F));
 106     i >>= 7;  // Shift out 7 bits now...
 107   }
 108 }
 109
 110 inline void BytecodeWriter::output_typeid(unsigned i) {
 111   if (i <= 0x00FFFFFF)
 112     this->output_vbr(i);
 113   else {
 114     this->output_vbr(0x00FFFFFF);
 115     this->output_vbr(i);
 116   }
 117 }
 118
 119 inline void BytecodeWriter::output_vbr(int64_t i) {
 120   if (i < 0)
 121     output_vbr(((uint64_t)(-i) << 1) | 1); // Set low order sign bit...
 122   else
 123     output_vbr((uint64_t)i << 1);          // Low order bit is clear.
 124 }
 125
 126
 127 inline void BytecodeWriter::output_vbr(int i) {
 128   if (i < 0)
 129     output_vbr(((unsigned)(-i) << 1) | 1); // Set low order sign bit...
 130   else
 131     output_vbr((unsigned)i << 1);          // Low order bit is clear.
 132 }
 133
 134 inline void BytecodeWriter::output(const std::string &s) {
 135   unsigned Len = s.length();
 136   output_vbr(Len);             // Strings may have an arbitrary length.
 137   Out.insert(Out.end(), s.begin(), s.end());
 138 }
 139
 140 inline void BytecodeWriter::output_data(const void *Ptr, const void *End) {
 141   Out.insert(Out.end(), (const unsigned char*)Ptr, (const unsigned char*)End);
 142 }
 143
 144 inline void BytecodeWriter::output_float(float& FloatVal) {
 145   /// FIXME: This isn't optimal, it has size problems on some platforms
 146   /// where FP is not IEEE.
 147   uint32_t i = FloatToBits(FloatVal);
 148   Out.push_back( static_cast<unsigned char>( (i      ) & 0xFF));
 149   Out.push_back( static_cast<unsigned char>( (i >> 8 ) & 0xFF));
 150   Out.push_back( static_cast<unsigned char>( (i >> 16) & 0xFF));
 151   Out.push_back( static_cast<unsigned char>( (i >> 24) & 0xFF));
 152 }
 153
 154 inline void BytecodeWriter::output_double(double& DoubleVal) {
 155   /// FIXME: This isn't optimal, it has size problems on some platforms
 156   /// where FP is not IEEE.
 157   uint64_t i = DoubleToBits(DoubleVal);
 158   Out.push_back( static_cast<unsigned char>( (i      ) & 0xFF));
 159   Out.push_back( static_cast<unsigned char>( (i >> 8 ) & 0xFF));
 160   Out.push_back( static_cast<unsigned char>( (i >> 16) & 0xFF));
 161   Out.push_back( static_cast<unsigned char>( (i >> 24) & 0xFF));
 162   Out.push_back( static_cast<unsigned char>( (i >> 32) & 0xFF));
 163   Out.push_back( static_cast<unsigned char>( (i >> 40) & 0xFF));
 164   Out.push_back( static_cast<unsigned char>( (i >> 48) & 0xFF));
 165   Out.push_back( static_cast<unsigned char>( (i >> 56) & 0xFF));
 166 }
 167
 168 inline BytecodeBlock::BytecodeBlock(unsigned ID, BytecodeWriter &w,
 169                                     bool elideIfEmpty, bool hasLongFormat)
 170   : Id(ID), Writer(w), ElideIfEmpty(elideIfEmpty), HasLongFormat(hasLongFormat){
 171
 172   if (HasLongFormat) {
 173     w.output(ID);
 174     w.output(0U); // For length in long format
 175   } else {
 176     w.output(0U); /// Place holder for ID and length for this block
 177   }
 178   Loc = w.size();
 179 }
 180
 181 inline BytecodeBlock::~BytecodeBlock() { // Do backpatch when block goes out
 182                                          // of scope...
 183   if (Loc == Writer.size() && ElideIfEmpty) {
 184     // If the block is empty, and we are allowed to, do not emit the block at
 185     // all!
 186     Writer.resize(Writer.size()-(HasLongFormat?8:4));
 187     return;
 188   }
 189
 190   if (HasLongFormat)
 191     Writer.output(unsigned(Writer.size()-Loc), int(Loc-4));
 192   else
 193     Writer.output(unsigned(Writer.size()-Loc) << 5 | (Id & 0x1F), int(Loc-4));
 194 }
 195
 196 //===----------------------------------------------------------------------===//
 197 //===                           Constant Output                            ===//
 198 //===----------------------------------------------------------------------===//
 199
 200 void BytecodeWriter::outputType(const Type *T) {
 201   const StructType* STy = dyn_cast<StructType>(T);
 202   if(STy && STy->isPacked())
 203     output_vbr((unsigned)Type::PackedStructTyID);
 204   else
 205     output_vbr((unsigned)T->getTypeID());
 206
 207   // That's all there is to handling primitive types...
 208   if (T->isPrimitiveType())
 209     return;     // We might do this if we alias a prim type: %x = type int
 210
 211   switch (T->getTypeID()) {   // Handle derived types now.
 212   case Type::IntegerTyID:
 213     output_vbr(cast<IntegerType>(T)->getBitWidth());
 214     break;
 215   case Type::FunctionTyID: {
 216     const FunctionType *MT = cast<FunctionType>(T);
 217     int Slot = Table.getSlot(MT->getReturnType());
 218     assert(Slot != -1 && "Type used but not available!!");
 219     output_typeid((unsigned)Slot);
 220     output_vbr(unsigned(MT->getParamAttrs(0)));
 221
 222     // Output the number of arguments to function (+1 if varargs):
 223     output_vbr((unsigned)MT->getNumParams()+MT->isVarArg());
 224
 225     // Output all of the arguments...
 226     FunctionType::param_iterator I = MT->param_begin();
 227     unsigned Idx = 1;
 228     for (; I != MT->param_end(); ++I) {
 229       Slot = Table.getSlot(*I);
 230       assert(Slot != -1 && "Type used but not available!!");
 231       output_typeid((unsigned)Slot);
 232       output_vbr(unsigned(MT->getParamAttrs(Idx)));
 233       Idx++;
 234     }
 235
 236     // Terminate list with VoidTy if we are a varargs function...
 237     if (MT->isVarArg())
 238       output_typeid((unsigned)Type::VoidTyID);
 239     break;
 240   }
 241
 242   case Type::ArrayTyID: {
 243     const ArrayType *AT = cast<ArrayType>(T);
 244     int Slot = Table.getSlot(AT->getElementType());
 245     assert(Slot != -1 && "Type used but not available!!");
 246     output_typeid((unsigned)Slot);
 247     output_vbr(AT->getNumElements());
 248     break;
 249   }
 250
 251  case Type::PackedTyID: {
 252     const PackedType *PT = cast<PackedType>(T);
 253     int Slot = Table.getSlot(PT->getElementType());
 254     assert(Slot != -1 && "Type used but not available!!");
 255     output_typeid((unsigned)Slot);
 256     output_vbr(PT->getNumElements());
 257     break;
 258   }
 259
 260   case Type::StructTyID: {
 261     const StructType *ST = cast<StructType>(T);
 262     // Output all of the element types...
 263     for (StructType::element_iterator I = ST->element_begin(),
 264            E = ST->element_end(); I != E; ++I) {
 265       int Slot = Table.getSlot(*I);
 266       assert(Slot != -1 && "Type used but not available!!");
 267       output_typeid((unsigned)Slot);
 268     }
 269
 270     // Terminate list with VoidTy
 271     output_typeid((unsigned)Type::VoidTyID);
 272     break;
 273   }
 274
 275   case Type::PointerTyID: {
 276     const PointerType *PT = cast<PointerType>(T);
 277     int Slot = Table.getSlot(PT->getElementType());
 278     assert(Slot != -1 && "Type used but not available!!");
 279     output_typeid((unsigned)Slot);
 280     break;
 281   }
 282
 283   case Type::OpaqueTyID:
 284     // No need to emit anything, just the count of opaque types is enough.
 285     break;
 286
 287   default:
 288     cerr << __FILE__ << ":" << __LINE__ << ": Don't know how to serialize"
 289          << " Type '" << T->getDescription() << "'\n";
 290     break;
 291   }
 292 }
 293
 294 void BytecodeWriter::outputConstant(const Constant *CPV) {
 295   assert(((CPV->getType()->isPrimitiveType() || CPV->getType()->isInteger()) ||
 296           !CPV->isNullValue()) && "Shouldn't output null constants!");
 297
 298   // We must check for a ConstantExpr before switching by type because
 299   // a ConstantExpr can be of any type, and has no explicit value.
 300   //
 301   if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(CPV)) {
 302     // FIXME: Encoding of constant exprs could be much more compact!
 303     assert(CE->getNumOperands() > 0 && "ConstantExpr with 0 operands");
 304     assert(CE->getNumOperands() != 1 || CE->isCast());
 305     output_vbr(1+CE->getNumOperands());   // flags as an expr
 306     output_vbr(CE->getOpcode());          // Put out the CE op code
 307
 308     for (User::const_op_iterator OI = CE->op_begin(); OI != CE->op_end(); ++OI){
 309       int Slot = Table.getSlot(*OI);
 310       assert(Slot != -1 && "Unknown constant used in ConstantExpr!!");
 311       output_vbr((unsigned)Slot);
 312       Slot = Table.getSlot((*OI)->getType());
 313       output_typeid((unsigned)Slot);
 314     }
 315     if (CE->isCompare())
 316       output_vbr((unsigned)CE->getPredicate());
 317     return;
 318   } else if (isa<UndefValue>(CPV)) {
 319     output_vbr(1U);       // 1 -> UndefValue constant.
 320     return;
 321   } else {
 322     output_vbr(0U);       // flag as not a ConstantExpr (i.e. 0 operands)
 323   }
 324
 325   switch (CPV->getType()->getTypeID()) {
 326   case Type::IntegerTyID: { // Integer types...
 327     unsigned NumBits = cast<IntegerType>(CPV->getType())->getBitWidth();
 328     if (NumBits <= 32)
 329       output_vbr(uint32_t(cast<ConstantInt>(CPV)->getZExtValue()));
 330     else if (NumBits <= 64)
 331       output_vbr(uint64_t(cast<ConstantInt>(CPV)->getZExtValue()));
 332     else
 333       assert("Integer types > 64 bits not supported.");
 334     break;
 335   }
 336
 337   case Type::ArrayTyID: {
 338     const ConstantArray *CPA = cast<ConstantArray>(CPV);
 339     assert(!CPA->isString() && "Constant strings should be handled specially!");
 340
 341     for (unsigned i = 0, e = CPA->getNumOperands(); i != e; ++i) {
 342       int Slot = Table.getSlot(CPA->getOperand(i));
 343       assert(Slot != -1 && "Constant used but not available!!");
 344       output_vbr((unsigned)Slot);
 345     }
 346     break;
 347   }
 348
 349   case Type::PackedTyID: {
 350     const ConstantPacked *CP = cast<ConstantPacked>(CPV);
 351
 352     for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) {
 353       int Slot = Table.getSlot(CP->getOperand(i));
 354       assert(Slot != -1 && "Constant used but not available!!");
 355       output_vbr((unsigned)Slot);
 356     }
 357     break;
 358   }
 359
 360   case Type::StructTyID: {
 361     const ConstantStruct *CPS = cast<ConstantStruct>(CPV);
 362
 363     for (unsigned i = 0, e = CPS->getNumOperands(); i != e; ++i) {
 364       int Slot = Table.getSlot(CPS->getOperand(i));
 365       assert(Slot != -1 && "Constant used but not available!!");
 366       output_vbr((unsigned)Slot);
 367     }
 368     break;
 369   }
 370
 371   case Type::PointerTyID:
 372     assert(0 && "No non-null, non-constant-expr constants allowed!");
 373     abort();
 374
 375   case Type::FloatTyID: {   // Floating point types...
 376     float Tmp = (float)cast<ConstantFP>(CPV)->getValue();
 377     output_float(Tmp);
 378     break;
 379   }
 380   case Type::DoubleTyID: {
 381     double Tmp = cast<ConstantFP>(CPV)->getValue();
 382     output_double(Tmp);
 383     break;
 384   }
 385
 386   case Type::VoidTyID:
 387   case Type::LabelTyID:
 388   default:
 389     cerr << __FILE__ << ":" << __LINE__ << ": Don't know how to serialize"
 390          << " type '" << *CPV->getType() << "'\n";
 391     break;
 392   }
 393   return;
 394 }
 395
 396 /// outputInlineAsm - InlineAsm's get emitted to the constant pool, so they can
 397 /// be shared by multiple uses.
 398 void BytecodeWriter::outputInlineAsm(const InlineAsm *IA) {
 399   // Output a marker, so we know when we have one one parsing the constant pool.
 400   // Note that this encoding is 5 bytes: not very efficient for a marker.  Since
 401   // unique inline asms are rare, this should hardly matter.
 402   output_vbr(~0U);
 403
 404   output(IA->getAsmString());
 405   output(IA->getConstraintString());
 406   output_vbr(unsigned(IA->hasSideEffects()));
 407 }
 408
 409 void BytecodeWriter::outputConstantStrings() {
 410   SlotCalculator::string_iterator I = Table.string_begin();
 411   SlotCalculator::string_iterator E = Table.string_end();
 412   if (I == E) return;  // No strings to emit
 413
 414   // If we have != 0 strings to emit, output them now.  Strings are emitted into
 415   // the 'void' type plane.
 416   output_vbr(unsigned(E-I));
 417   output_typeid(Type::VoidTyID);
 418
 419   // Emit all of the strings.
 420   for (I = Table.string_begin(); I != E; ++I) {
 421     const ConstantArray *Str = *I;
 422     int Slot = Table.getSlot(Str->getType());
 423     assert(Slot != -1 && "Constant string of unknown type?");
 424     output_typeid((unsigned)Slot);
 425
 426     // Now that we emitted the type (which indicates the size of the string),
 427     // emit all of the characters.
 428     std::string Val = Str->getAsString();
 429     output_data(Val.c_str(), Val.c_str()+Val.size());
 430   }
 431 }
 432
 433 //===----------------------------------------------------------------------===//
 434 //===                           Instruction Output                         ===//
 435 //===----------------------------------------------------------------------===//
 436
 437 // outputInstructionFormat0 - Output those weird instructions that have a large
 438 // number of operands or have large operands themselves.
 439 //
 440 // Format: [opcode] [type] [numargs] [arg0] [arg1] ... [arg<numargs-1>]
 441 //
 442 void BytecodeWriter::outputInstructionFormat0(const Instruction *I,
 443                                               unsigned Opcode,
 444                                               const SlotCalculator &Table,
 445                                               unsigned Type) {
 446   // Opcode must have top two bits clear...
 447   output_vbr(Opcode << 2);                  // Instruction Opcode ID
 448   output_typeid(Type);                      // Result type
 449
 450   unsigned NumArgs = I->getNumOperands();
 451   output_vbr(NumArgs + (isa<CastInst>(I)  || isa<InvokeInst>(I) ||
 452                         isa<CmpInst>(I) || isa<VAArgInst>(I) || Opcode == 58));
 453
 454   if (!isa<GetElementPtrInst>(&I)) {
 455     for (unsigned i = 0; i < NumArgs; ++i) {
 456       int Slot = Table.getSlot(I->getOperand(i));
 457       assert(Slot >= 0 && "No slot number for value!?!?");
 458       output_vbr((unsigned)Slot);
 459     }
 460
 461     if (isa<CastInst>(I) || isa<VAArgInst>(I)) {
 462       int Slot = Table.getSlot(I->getType());
 463       assert(Slot != -1 && "Cast return type unknown?");
 464       output_typeid((unsigned)Slot);
 465     } else if (isa<CmpInst>(I)) {
 466       output_vbr(unsigned(cast<CmpInst>(I)->getPredicate()));
 467     } else if (isa<InvokeInst>(I)) {
 468       output_vbr(cast<InvokeInst>(I)->getCallingConv());
 469     } else if (Opcode == 58) {  // Call escape sequence
 470       output_vbr((cast<CallInst>(I)->getCallingConv() << 1) |
 471                  unsigned(cast<CallInst>(I)->isTailCall()));
 472     }
 473   } else {
 474     int Slot = Table.getSlot(I->getOperand(0));
 475     assert(Slot >= 0 && "No slot number for value!?!?");
 476     output_vbr(unsigned(Slot));
 477
 478     // We need to encode the type of sequential type indices into their slot #
 479     unsigned Idx = 1;
 480     for (gep_type_iterator TI = gep_type_begin(I), E = gep_type_end(I);
 481          Idx != NumArgs; ++TI, ++Idx) {
 482       Slot = Table.getSlot(I->getOperand(Idx));
 483       assert(Slot >= 0 && "No slot number for value!?!?");
 484
 485       if (isa<SequentialType>(*TI)) {
 486         // These should be either 32-bits or 64-bits, however, with bit
 487         // accurate types we just distinguish between less than or equal to
 488         // 32-bits or greater than 32-bits.
 489         unsigned BitWidth =
 490           cast<IntegerType>(I->getOperand(Idx)->getType())->getBitWidth();
 491         assert(BitWidth == 32 || BitWidth == 64 &&
 492                "Invalid bitwidth for GEP index");
 493         unsigned IdxId = BitWidth == 32 ? 0 : 1;
 494         Slot = (Slot << 1) | IdxId;
 495       }
 496       output_vbr(unsigned(Slot));
 497     }
 498   }
 499 }
 500
 501
 502 // outputInstrVarArgsCall - Output the absurdly annoying varargs function calls.
 503 // This are more annoying than most because the signature of the call does not
 504 // tell us anything about the types of the arguments in the varargs portion.
 505 // Because of this, we encode (as type 0) all of the argument types explicitly
 506 // before the argument value.  This really sucks, but you shouldn't be using
 507 // varargs functions in your code! *death to printf*!
 508 //
 509 // Format: [opcode] [type] [numargs] [arg0] [arg1] ... [arg<numargs-1>]
 510 //
 511 void BytecodeWriter::outputInstrVarArgsCall(const Instruction *I,
 512                                             unsigned Opcode,
 513                                             const SlotCalculator &Table,
 514                                             unsigned Type) {
 515   assert(isa<CallInst>(I) || isa<InvokeInst>(I));
 516   // Opcode must have top two bits clear...
 517   output_vbr(Opcode << 2);                  // Instruction Opcode ID
 518   output_typeid(Type);                      // Result type (varargs type)
 519
 520   const PointerType *PTy = cast<PointerType>(I->getOperand(0)->getType());
 521   const FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
 522   unsigned NumParams = FTy->getNumParams();
 523
 524   unsigned NumFixedOperands;
 525   if (isa<CallInst>(I)) {
 526     // Output an operand for the callee and each fixed argument, then two for
 527     // each variable argument.
 528     NumFixedOperands = 1+NumParams;
 529   } else {
 530     assert(isa<InvokeInst>(I) && "Not call or invoke??");
 531     // Output an operand for the callee and destinations, then two for each
 532     // variable argument.
 533     NumFixedOperands = 3+NumParams;
 534   }
 535   output_vbr(2 * I->getNumOperands()-NumFixedOperands +
 536       unsigned(Opcode == 58 || isa<InvokeInst>(I)));
 537
 538   // The type for the function has already been emitted in the type field of the
 539   // instruction.  Just emit the slot # now.
 540   for (unsigned i = 0; i != NumFixedOperands; ++i) {
 541     int Slot = Table.getSlot(I->getOperand(i));
 542     assert(Slot >= 0 && "No slot number for value!?!?");
 543     output_vbr((unsigned)Slot);
 544   }
 545
 546   for (unsigned i = NumFixedOperands, e = I->getNumOperands(); i != e; ++i) {
 547     // Output Arg Type ID
 548     int Slot = Table.getSlot(I->getOperand(i)->getType());
 549     assert(Slot >= 0 && "No slot number for value!?!?");
 550     output_typeid((unsigned)Slot);
 551
 552     // Output arg ID itself
 553     Slot = Table.getSlot(I->getOperand(i));
 554     assert(Slot >= 0 && "No slot number for value!?!?");
 555     output_vbr((unsigned)Slot);
 556   }
 557
 558   if (isa<InvokeInst>(I)) {
 559     // Emit the tail call/calling conv for invoke instructions
 560     output_vbr(cast<InvokeInst>(I)->getCallingConv());
 561   } else if (Opcode == 58) {
 562     const CallInst *CI = cast<CallInst>(I);
 563     output_vbr((CI->getCallingConv() << 1) | unsigned(CI->isTailCall()));
 564   }
 565 }
 566
 567
 568 // outputInstructionFormat1 - Output one operand instructions, knowing that no
 569 // operand index is >= 2^12.
 570 //
 571 inline void BytecodeWriter::outputInstructionFormat1(const Instruction *I,
 572                                                      unsigned Opcode,
 573                                                      unsigned *Slots,
 574                                                      unsigned Type) {
 575   // bits   Instruction format:
 576   // --------------------------
 577   // 01-00: Opcode type, fixed to 1.
 578   // 07-02: Opcode
 579   // 19-08: Resulting type plane
 580   // 31-20: Operand #1 (if set to (2^12-1), then zero operands)
 581   //
 582   output(1 | (Opcode << 2) | (Type << 8) | (Slots[0] << 20));
 583 }
 584
 585
 586 // outputInstructionFormat2 - Output two operand instructions, knowing that no
 587 // operand index is >= 2^8.
 588 //
 589 inline void BytecodeWriter::outputInstructionFormat2(const Instruction *I,
 590                                                      unsigned Opcode,
 591                                                      unsigned *Slots,
 592                                                      unsigned Type) {
 593   // bits   Instruction format:
 594   // --------------------------
 595   // 01-00: Opcode type, fixed to 2.
 596   // 07-02: Opcode
 597   // 15-08: Resulting type plane
 598   // 23-16: Operand #1
 599   // 31-24: Operand #2
 600   //
 601   output(2 | (Opcode << 2) | (Type << 8) | (Slots[0] << 16) | (Slots[1] << 24));
 602 }
 603
 604
 605 // outputInstructionFormat3 - Output three operand instructions, knowing that no
 606 // operand index is >= 2^6.
 607 //
 608 inline void BytecodeWriter::outputInstructionFormat3(const Instruction *I,
 609                                                      unsigned Opcode,
 610                                                      unsigned *Slots,
 611                                                      unsigned Type) {
 612   // bits   Instruction format:
 613   // --------------------------
 614   // 01-00: Opcode type, fixed to 3.
 615   // 07-02: Opcode
 616   // 13-08: Resulting type plane
 617   // 19-14: Operand #1
 618   // 25-20: Operand #2
 619   // 31-26: Operand #3
 620   //
 621   output(3 | (Opcode << 2) | (Type << 8) |
 622           (Slots[0] << 14) | (Slots[1] << 20) | (Slots[2] << 26));
 623 }
 624
 625 void BytecodeWriter::outputInstruction(const Instruction &I) {
 626   assert(I.getOpcode() < 57 && "Opcode too big???");
 627   unsigned Opcode = I.getOpcode();
 628   unsigned NumOperands = I.getNumOperands();
 629
 630   // Encode 'tail call' as 61, 'volatile load' as 62, and 'volatile store' as
 631   // 63.
 632   if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
 633     if (CI->getCallingConv() == CallingConv::C) {
 634       if (CI->isTailCall())
 635         Opcode = 61;   // CCC + Tail Call
 636       else
 637         ;     // Opcode = Instruction::Call
 638     } else if (CI->getCallingConv() == CallingConv::Fast) {
 639       if (CI->isTailCall())
 640         Opcode = 59;    // FastCC + TailCall
 641       else
 642         Opcode = 60;    // FastCC + Not Tail Call
 643     } else {
 644       Opcode = 58;      // Call escape sequence.
 645     }
 646   } else if (isa<LoadInst>(I) && cast<LoadInst>(I).isVolatile()) {
 647     Opcode = 62;
 648   } else if (isa<StoreInst>(I) && cast<StoreInst>(I).isVolatile()) {
 649     Opcode = 63;
 650   }
 651
 652   // Figure out which type to encode with the instruction.  Typically we want
 653   // the type of the first parameter, as opposed to the type of the instruction
 654   // (for example, with setcc, we always know it returns bool, but the type of
 655   // the first param is actually interesting).  But if we have no arguments
 656   // we take the type of the instruction itself.
 657   //
 658   const Type *Ty;
 659   switch (I.getOpcode()) {
 660   case Instruction::Select:
 661   case Instruction::Malloc:
 662   case Instruction::Alloca:
 663     Ty = I.getType();  // These ALWAYS want to encode the return type
 664     break;
 665   case Instruction::Store:
 666     Ty = I.getOperand(1)->getType();  // Encode the pointer type...
 667     assert(isa<PointerType>(Ty) && "Store to nonpointer type!?!?");
 668     break;
 669   default:              // Otherwise use the default behavior...
 670     Ty = NumOperands ? I.getOperand(0)->getType() : I.getType();
 671     break;
 672   }
 673
 674   unsigned Type;
 675   int Slot = Table.getSlot(Ty);
 676   assert(Slot != -1 && "Type not available!!?!");
 677   Type = (unsigned)Slot;
 678
 679   // Varargs calls and invokes are encoded entirely different from any other
 680   // instructions.
 681   if (const CallInst *CI = dyn_cast<CallInst>(&I)){
 682     const PointerType *Ty =cast<PointerType>(CI->getCalledValue()->getType());
 683     if (cast<FunctionType>(Ty->getElementType())->isVarArg()) {
 684       outputInstrVarArgsCall(CI, Opcode, Table, Type);
 685       return;
 686     }
 687   } else if (const InvokeInst *II = dyn_cast<InvokeInst>(&I)) {
 688     const PointerType *Ty =cast<PointerType>(II->getCalledValue()->getType());
 689     if (cast<FunctionType>(Ty->getElementType())->isVarArg()) {
 690       outputInstrVarArgsCall(II, Opcode, Table, Type);
 691       return;
 692     }
 693   }
 694
 695   if (NumOperands <= 3) {
 696     // Make sure that we take the type number into consideration.  We don't want
 697     // to overflow the field size for the instruction format we select.
 698     //
 699     unsigned MaxOpSlot = Type;
 700     unsigned Slots[3]; Slots[0] = (1 << 12)-1;   // Marker to signify 0 operands
 701
 702     for (unsigned i = 0; i != NumOperands; ++i) {
 703       int slot = Table.getSlot(I.getOperand(i));
 704       assert(slot != -1 && "Broken bytecode!");
 705       if (unsigned(slot) > MaxOpSlot) MaxOpSlot = unsigned(slot);
 706       Slots[i] = unsigned(slot);
 707     }
 708
 709     // Handle the special cases for various instructions...
 710     if (isa<CastInst>(I) || isa<VAArgInst>(I)) {
 711       // Cast has to encode the destination type as the second argument in the
 712       // packet, or else we won't know what type to cast to!
 713       Slots[1] = Table.getSlot(I.getType());
 714       assert(Slots[1] != ~0U && "Cast return type unknown?");
 715       if (Slots[1] > MaxOpSlot) MaxOpSlot = Slots[1];
 716       NumOperands++;
 717     } else if (const AllocationInst *AI = dyn_cast<AllocationInst>(&I)) {
 718       assert(NumOperands == 1 && "Bogus allocation!");
 719       if (AI->getAlignment()) {
 720         Slots[1] = Log2_32(AI->getAlignment())+1;
 721         if (Slots[1] > MaxOpSlot) MaxOpSlot = Slots[1];
 722         NumOperands = 2;
 723       }
 724     } else if (isa<ICmpInst>(I) || isa<FCmpInst>(I)) {
 725       // We need to encode the compare instruction's predicate as the third
 726       // operand. Its not really a slot, but we don't want to break the
 727       // instruction format for these instructions.
 728       NumOperands++;
 729       assert(NumOperands == 3 && "CmpInst with wrong number of operands?");
 730       Slots[2] = unsigned(cast<CmpInst>(&I)->getPredicate());
 731       if (Slots[2] > MaxOpSlot)
 732         MaxOpSlot = Slots[2];
 733     } else if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&I)) {
 734       // We need to encode the type of sequential type indices into their slot #
 735       unsigned Idx = 1;
 736       for (gep_type_iterator I = gep_type_begin(GEP), E = gep_type_end(GEP);
 737            I != E; ++I, ++Idx)
 738         if (isa<SequentialType>(*I)) {
 739           // These should be either 32-bits or 64-bits, however, with bit
 740           // accurate types we just distinguish between less than or equal to
 741           // 32-bits or greater than 32-bits.
 742           unsigned BitWidth =
 743             cast<IntegerType>(GEP->getOperand(Idx)->getType())->getBitWidth();
 744           assert(BitWidth == 32 || BitWidth == 64 &&
 745                  "Invalid bitwidth for GEP index");
 746           unsigned IdxId = BitWidth == 32 ? 0 : 1;
 747           Slots[Idx] = (Slots[Idx] << 1) | IdxId;
 748           if (Slots[Idx] > MaxOpSlot) MaxOpSlot = Slots[Idx];
 749         }
 750     } else if (Opcode == 58) {
 751       // If this is the escape sequence for call, emit the tailcall/cc info.
 752       const CallInst &CI = cast<CallInst>(I);
 753       ++NumOperands;
 754       if (NumOperands <= 3) {
 755         Slots[NumOperands-1] =
 756           (CI.getCallingConv() << 1)|unsigned(CI.isTailCall());
 757         if (Slots[NumOperands-1] > MaxOpSlot)
 758           MaxOpSlot = Slots[NumOperands-1];
 759       }
 760     } else if (isa<InvokeInst>(I)) {
 761       // Invoke escape seq has at least 4 operands to encode.
 762       ++NumOperands;
 763     }
 764
 765     // Decide which instruction encoding to use.  This is determined primarily
 766     // by the number of operands, and secondarily by whether or not the max
 767     // operand will fit into the instruction encoding.  More operands == fewer
 768     // bits per operand.
 769     //
 770     switch (NumOperands) {
 771     case 0:
 772     case 1:
 773       if (MaxOpSlot < (1 << 12)-1) { // -1 because we use 4095 to indicate 0 ops
 774         outputInstructionFormat1(&I, Opcode, Slots, Type);
 775         return;
 776       }
 777       break;
 778
 779     case 2:
 780       if (MaxOpSlot < (1 << 8)) {
 781         outputInstructionFormat2(&I, Opcode, Slots, Type);
 782         return;
 783       }
 784       break;
 785
 786     case 3:
 787       if (MaxOpSlot < (1 << 6)) {
 788         outputInstructionFormat3(&I, Opcode, Slots, Type);
 789         return;
 790       }
 791       break;
 792     default:
 793       break;
 794     }
 795   }
 796
 797   // If we weren't handled before here, we either have a large number of
 798   // operands or a large operand index that we are referring to.
 799   outputInstructionFormat0(&I, Opcode, Table, Type);
 800 }
 801
 802 //===----------------------------------------------------------------------===//
 803 //===                              Block Output                            ===//
 804 //===----------------------------------------------------------------------===//
 805
 806 BytecodeWriter::BytecodeWriter(std::vector<unsigned char> &o, const Module *M)
 807   : Out(o), Table(M) {
 808
 809   // Emit the signature...
 810   static const unsigned char *Sig = (const unsigned char*)"llvm";
 811   output_data(Sig, Sig+4);
 812
 813   // Emit the top level CLASS block.
 814   BytecodeBlock ModuleBlock(BytecodeFormat::ModuleBlockID, *this, false, true);
 815
 816   // Output the version identifier
 817   output_vbr(BCVersionNum);
 818
 819   // The Global type plane comes first
 820   {
 821     BytecodeBlock CPool(BytecodeFormat::GlobalTypePlaneBlockID, *this);
 822     outputTypes(Type::FirstDerivedTyID);
 823   }
 824
 825   // The ModuleInfoBlock follows directly after the type information
 826   outputModuleInfoBlock(M);
 827
 828   // Output module level constants, used for global variable initializers
 829   outputConstants(false);
 830
 831   // Do the whole module now! Process each function at a time...
 832   for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I)
 833     outputFunction(I);
 834
 835   // Output the symbole table for types
 836   outputTypeSymbolTable(M->getTypeSymbolTable());
 837
 838   // Output the symbol table for values
 839   outputValueSymbolTable(M->getValueSymbolTable());
 840 }
 841
 842 void BytecodeWriter::outputTypes(unsigned TypeNum) {
 843   // Write the type plane for types first because earlier planes (e.g. for a
 844   // primitive type like float) may have constants constructed using types
 845   // coming later (e.g., via getelementptr from a pointer type).  The type
 846   // plane is needed before types can be fwd or bkwd referenced.
 847   const std::vector<const Type*>& Types = Table.getTypes();
 848   assert(!Types.empty() && "No types at all?");
 849   assert(TypeNum <= Types.size() && "Invalid TypeNo index");
 850
 851   unsigned NumEntries = Types.size() - TypeNum;
 852
 853   // Output type header: [num entries]
 854   output_vbr(NumEntries);
 855
 856   for (unsigned i = TypeNum; i < TypeNum+NumEntries; ++i)
 857     outputType(Types[i]);
 858 }
 859
 860 // Helper function for outputConstants().
 861 // Writes out all the constants in the plane Plane starting at entry StartNo.
 862 //
 863 void BytecodeWriter::outputConstantsInPlane(const std::vector<const Value*>
 864                                             &Plane, unsigned StartNo) {
 865   unsigned ValNo = StartNo;
 866
 867   // Scan through and ignore function arguments, global values, and constant
 868   // strings.
 869   for (; ValNo < Plane.size() &&
 870          (isa<Argument>(Plane[ValNo]) || isa<GlobalValue>(Plane[ValNo]) ||
 871           (isa<ConstantArray>(Plane[ValNo]) &&
 872            cast<ConstantArray>(Plane[ValNo])->isString())); ValNo++)
 873     /*empty*/;
 874
 875   unsigned NC = ValNo;              // Number of constants
 876   for (; NC < Plane.size() && (isa<Constant>(Plane[NC]) ||
 877                                isa<InlineAsm>(Plane[NC])); NC++)
 878     /*empty*/;
 879   NC -= ValNo;                      // Convert from index into count
 880   if (NC == 0) return;              // Skip empty type planes...
 881
 882   // FIXME: Most slabs only have 1 or 2 entries!  We should encode this much
 883   // more compactly.
 884
 885   // Put out type header: [num entries][type id number]
 886   //
 887   output_vbr(NC);
 888
 889   // Put out the Type ID Number...
 890   int Slot = Table.getSlot(Plane.front()->getType());
 891   assert (Slot != -1 && "Type in constant pool but not in function!!");
 892   output_typeid((unsigned)Slot);
 893
 894   for (unsigned i = ValNo; i < ValNo+NC; ++i) {
 895     const Value *V = Plane[i];
 896     if (const Constant *C = dyn_cast<Constant>(V))
 897       outputConstant(C);
 898     else
 899       outputInlineAsm(cast<InlineAsm>(V));
 900   }
 901 }
 902
 903 static inline bool hasNullValue(const Type *Ty) {
 904   return Ty != Type::LabelTy && Ty != Type::VoidTy && !isa<OpaqueType>(Ty);
 905 }
 906
 907 void BytecodeWriter::outputConstants(bool isFunction) {
 908   BytecodeBlock CPool(BytecodeFormat::ConstantPoolBlockID, *this,
 909                       true  /* Elide block if empty */);
 910
 911   unsigned NumPlanes = Table.getNumPlanes();
 912
 913   if (isFunction)
 914     // Output the type plane before any constants!
 915     outputTypes(Table.getModuleTypeLevel());
 916   else
 917     // Output module-level string constants before any other constants.
 918     outputConstantStrings();
 919
 920   for (unsigned pno = 0; pno != NumPlanes; pno++) {
 921     const std::vector<const Value*> &Plane = Table.getPlane(pno);
 922     if (!Plane.empty()) {              // Skip empty type planes...
 923       unsigned ValNo = 0;
 924       if (isFunction)                  // Don't re-emit module constants
 925         ValNo += Table.getModuleLevel(pno);
 926
 927       if (hasNullValue(Plane[0]->getType())) {
 928         // Skip zero initializer
 929         if (ValNo == 0)
 930           ValNo = 1;
 931       }
 932
 933       // Write out constants in the plane
 934       outputConstantsInPlane(Plane, ValNo);
 935     }
 936   }
 937 }
 938
 939 static unsigned getEncodedLinkage(const GlobalValue *GV) {
 940   switch (GV->getLinkage()) {
 941   default: assert(0 && "Invalid linkage!");
 942   case GlobalValue::ExternalLinkage:     return 0;
 943   case GlobalValue::WeakLinkage:         return 1;
 944   case GlobalValue::AppendingLinkage:    return 2;
 945   case GlobalValue::InternalLinkage:     return 3;
 946   case GlobalValue::LinkOnceLinkage:     return 4;
 947   case GlobalValue::DLLImportLinkage:    return 5;
 948   case GlobalValue::DLLExportLinkage:    return 6;
 949   case GlobalValue::ExternalWeakLinkage: return 7;
 950   }
 951 }
 952
 953 static unsigned getEncodedVisibility(const GlobalValue *GV) {
 954   switch (GV->getVisibility()) {
 955   default: assert(0 && "Invalid visibility!");
 956   case GlobalValue::DefaultVisibility: return 0;
 957   case GlobalValue::HiddenVisibility:  return 1;
 958   }
 959 }
 960
 961 void BytecodeWriter::outputModuleInfoBlock(const Module *M) {
 962   BytecodeBlock ModuleInfoBlock(BytecodeFormat::ModuleGlobalInfoBlockID, *this);
 963
 964   // Give numbers to sections as we encounter them.
 965   unsigned SectionIDCounter = 0;
 966   std::vector<std::string> SectionNames;
 967   std::map<std::string, unsigned> SectionID;
 968
 969   // Output the types for the global variables in the module...
 970   for (Module::const_global_iterator I = M->global_begin(),
 971          End = M->global_end(); I != End; ++I) {
 972     int Slot = Table.getSlot(I->getType());
 973     assert(Slot != -1 && "Module global vars is broken!");
 974
 975     assert((I->hasInitializer() || !I->hasInternalLinkage()) &&
 976            "Global must have an initializer or have external linkage!");
 977
 978     // Fields: bit0 = isConstant, bit1 = hasInitializer, bit2-4=Linkage,
 979     // bit5+ = Slot # for type.
 980     bool HasExtensionWord = (I->getAlignment() != 0) ||
 981                             I->hasSection() ||
 982       (I->getVisibility() != GlobalValue::DefaultVisibility);
 983
 984     // If we need to use the extension byte, set linkage=3(internal) and
 985     // initializer = 0 (impossible!).
 986     if (!HasExtensionWord) {
 987       unsigned oSlot = ((unsigned)Slot << 5) | (getEncodedLinkage(I) << 2) |
 988                         (I->hasInitializer() << 1) | (unsigned)I->isConstant();
 989       output_vbr(oSlot);
 990     } else {
 991       unsigned oSlot = ((unsigned)Slot << 5) | (3 << 2) |
 992                         (0 << 1) | (unsigned)I->isConstant();
 993       output_vbr(oSlot);
 994
 995       // The extension word has this format: bit 0 = has initializer, bit 1-3 =
 996       // linkage, bit 4-8 = alignment (log2), bit 9 = has SectionID,
 997       // bits 10-12 = visibility, bits 13+ = future use.
 998       unsigned ExtWord = (unsigned)I->hasInitializer() |
 999                          (getEncodedLinkage(I) << 1) |
1000                          ((Log2_32(I->getAlignment())+1) << 4) |
1001                          ((unsigned)I->hasSection() << 9) |
1002                          (getEncodedVisibility(I) << 10);
1003       output_vbr(ExtWord);
1004       if (I->hasSection()) {
1005         // Give section names unique ID's.
1006         unsigned &Entry = SectionID[I->getSection()];
1007         if (Entry == 0) {
1008           Entry = ++SectionIDCounter;
1009           SectionNames.push_back(I->getSection());
1010         }
1011         output_vbr(Entry);
1012       }
1013     }
1014
1015     // If we have an initializer, output it now.
1016     if (I->hasInitializer()) {
1017       Slot = Table.getSlot((Value*)I->getInitializer());
1018       assert(Slot != -1 && "No slot for global var initializer!");
1019       output_vbr((unsigned)Slot);
1020     }
1021   }
1022   output_typeid((unsigned)Table.getSlot(Type::VoidTy));
1023
1024   // Output the types of the functions in this module.
1025   for (Module::const_iterator I = M->begin(), End = M->end(); I != End; ++I) {
1026     int Slot = Table.getSlot(I->getType());
1027     assert(Slot != -1 && "Module slot calculator is broken!");
1028     assert(Slot >= Type::FirstDerivedTyID && "Derived type not in range!");
1029     assert(((Slot << 6) >> 6) == Slot && "Slot # too big!");
1030     unsigned CC = I->getCallingConv()+1;
1031     unsigned ID = (Slot << 5) | (CC & 15);
1032
1033     if (I->isDeclaration())   // If external, we don't have an FunctionInfo block.
1034       ID |= 1 << 4;
1035
1036     if (I->getAlignment() || I->hasSection() || (CC & ~15) != 0 ||
1037         (I->isDeclaration() && I->hasDLLImportLinkage()) ||
1038         (I->isDeclaration() && I->hasExternalWeakLinkage())
1039        )
1040       ID |= 1 << 31;       // Do we need an extension word?
1041
1042     output_vbr(ID);
1043
1044     if (ID & (1 << 31)) {
1045       // Extension byte: bits 0-4 = alignment, bits 5-9 = top nibble of calling
1046       // convention, bit 10 = hasSectionID., bits 11-12 = external linkage type
1047       unsigned extLinkage = 0;
1048
1049       if (I->isDeclaration()) {
1050         if (I->hasDLLImportLinkage()) {
1051           extLinkage = 1;
1052         } else if (I->hasExternalWeakLinkage()) {
1053           extLinkage = 2;
1054         }
1055       }
1056
1057       ID = (Log2_32(I->getAlignment())+1) | ((CC >> 4) << 5) |
1058         (I->hasSection() << 10) |
1059         ((extLinkage & 3) << 11);
1060       output_vbr(ID);
1061
1062       // Give section names unique ID's.
1063       if (I->hasSection()) {
1064         unsigned &Entry = SectionID[I->getSection()];
1065         if (Entry == 0) {
1066           Entry = ++SectionIDCounter;
1067           SectionNames.push_back(I->getSection());
1068         }
1069         output_vbr(Entry);
1070       }
1071     }
1072   }
1073   output_vbr((unsigned)Table.getSlot(Type::VoidTy) << 5);
1074
1075   // Emit the list of dependent libraries for the Module.
1076   Module::lib_iterator LI = M->lib_begin();
1077   Module::lib_iterator LE = M->lib_end();
1078   output_vbr(unsigned(LE - LI));   // Emit the number of dependent libraries.
1079   for (; LI != LE; ++LI)
1080     output(*LI);
1081
1082   // Output the target triple from the module
1083   output(M->getTargetTriple());
1084
1085   // Output the data layout from the module
1086   output(M->getDataLayout());
1087
1088   // Emit the table of section names.
1089   output_vbr((unsigned)SectionNames.size());
1090   for (unsigned i = 0, e = SectionNames.size(); i != e; ++i)
1091     output(SectionNames[i]);
1092
1093   // Output the inline asm string.
1094   output(M->getModuleInlineAsm());
1095 }
1096
1097 void BytecodeWriter::outputInstructions(const Function *F) {
1098   BytecodeBlock ILBlock(BytecodeFormat::InstructionListBlockID, *this);
1099   for (Function::const_iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
1100     for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I!=E; ++I)
1101       outputInstruction(*I);
1102 }
1103
1104 void BytecodeWriter::outputFunction(const Function *F) {
1105   // If this is an external function, there is nothing else to emit!
1106   if (F->isDeclaration()) return;
1107
1108   BytecodeBlock FunctionBlock(BytecodeFormat::FunctionBlockID, *this);
1109   unsigned rWord = (getEncodedVisibility(F) << 16) | getEncodedLinkage(F);
1110   output_vbr(rWord);
1111
1112   // Get slot information about the function...
1113   Table.incorporateFunction(F);
1114
1115   outputConstants(true);
1116
1117   // Output all of the instructions in the body of the function
1118   outputInstructions(F);
1119
1120   // If needed, output the symbol table for the function...
1121   outputValueSymbolTable(F->getValueSymbolTable());
1122
1123   Table.purgeFunction();
1124 }
1125
1126
1127 void BytecodeWriter::outputTypeSymbolTable(const TypeSymbolTable &TST) {
1128   // Do not output the block for an empty symbol table, it just wastes
1129   // space!
1130   if (TST.empty()) return;
1131
1132   // Create a header for the symbol table
1133   BytecodeBlock SymTabBlock(BytecodeFormat::TypeSymbolTableBlockID, *this,
1134                             true/*ElideIfEmpty*/);
1135   // Write the number of types
1136   output_vbr(TST.size());
1137
1138   // Write each of the types
1139   for (TypeSymbolTable::const_iterator TI = TST.begin(), TE = TST.end();
1140        TI != TE; ++TI) {
1141     // Symtab entry:[def slot #][name]
1142     output_typeid((unsigned)Table.getSlot(TI->second));
1143     output(TI->first);
1144   }
1145 }
1146
1147 void BytecodeWriter::outputValueSymbolTable(const ValueSymbolTable &VST) {
1148   // Do not output the Bytecode block for an empty symbol table, it just wastes
1149   // space!
1150   if (VST.empty()) return;
1151
1152   BytecodeBlock SymTabBlock(BytecodeFormat::ValueSymbolTableBlockID, *this,
1153                             true/*ElideIfEmpty*/);
1154
1155   // Organize the symbol table by type
1156   typedef std::pair<std::string, const Value*> PlaneMapEntry;
1157   typedef std::vector<PlaneMapEntry> PlaneMapVector;
1158   typedef std::map<const Type*, PlaneMapVector > PlaneMap;
1159   PlaneMap Planes;
1160   for (ValueSymbolTable::const_iterator SI = VST.begin(), SE = VST.end();
1161        SI != SE; ++SI)
1162     Planes[SI->second->getType()].push_back(
1163         std::make_pair(SI->first,SI->second));
1164
1165   for (PlaneMap::const_iterator PI = Planes.begin(), PE = Planes.end();
1166        PI != PE; ++PI) {
1167     int Slot;
1168
1169     PlaneMapVector::const_iterator I = PI->second.begin();
1170     PlaneMapVector::const_iterator End = PI->second.end();
1171
1172     if (I == End) continue;  // Don't mess with an absent type...
1173
1174     // Write the number of values in this plane
1175     output_vbr((unsigned)PI->second.size());
1176
1177     // Write the slot number of the type for this plane
1178     Slot = Table.getSlot(PI->first);
1179     assert(Slot != -1 && "Type in symtab, but not in table!");
1180     output_typeid((unsigned)Slot);
1181
1182     // Write each of the values in this plane
1183     for (; I != End; ++I) {
1184       // Symtab entry: [def slot #][name]
1185       Slot = Table.getSlot(I->second);
1186       assert(Slot != -1 && "Value in symtab but has no slot number!!");
1187       output_vbr((unsigned)Slot);
1188       output(I->first);
1189     }
1190   }
1191 }
1192
1193 void llvm::WriteBytecodeToFile(const Module *M, OStream &Out,
1194                                bool compress) {
1195   assert(M && "You can't write a null module!!");
1196
1197   // Make sure that std::cout is put into binary mode for systems
1198   // that care.
1199   if (Out == cout)
1200     sys::Program::ChangeStdoutToBinary();
1201
1202   // Create a vector of unsigned char for the bytecode output. We
1203   // reserve 256KBytes of space in the vector so that we avoid doing
1204   // lots of little allocations. 256KBytes is sufficient for a large
1205   // proportion of the bytecode files we will encounter. Larger files
1206   // will be automatically doubled in size as needed (std::vector
1207   // behavior).
1208   std::vector<unsigned char> Buffer;
1209   Buffer.reserve(256 * 1024);
1210
1211   // The BytecodeWriter populates Buffer for us.
1212   BytecodeWriter BCW(Buffer, M);
1213
1214   // Keep track of how much we've written
1215   BytesWritten += Buffer.size();
1216
1217   // Determine start and end points of the Buffer
1218   const unsigned char *FirstByte = &Buffer.front();
1219
1220   // If we're supposed to compress this mess ...
1221   if (compress) {
1222
1223     // We signal compression by using an alternate magic number for the
1224     // file. The compressed bytecode file's magic number is "llvc" instead
1225     // of "llvm".
1226     char compressed_magic[4];
1227     compressed_magic[0] = 'l';
1228     compressed_magic[1] = 'l';
1229     compressed_magic[2] = 'v';
1230     compressed_magic[3] = 'c';
1231
1232     Out.stream()->write(compressed_magic,4);
1233
1234     // Compress everything after the magic number (which we altered)
1235     Compressor::compressToStream(
1236       (char*)(FirstByte+4),        // Skip the magic number
1237       Buffer.size()-4,             // Skip the magic number
1238       *Out.stream()                // Where to write compressed data
1239     );
1240
1241   } else {
1242
1243     // We're not compressing, so just write the entire block.
1244     Out.stream()->write((char*)FirstByte, Buffer.size());
1245   }
1246
1247   // make sure it hits disk now
1248   Out.stream()->flush();
1249 }