lib/Bitcode/Writer/BitcodeWriter.cpp

   1 //===--- Bitcode/Writer/BitcodeWriter.cpp - Bitcode Writer ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Chris Lattner and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Bitcode writer implementation.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Bitcode/ReaderWriter.h"
  15 #include "llvm/Bitcode/BitstreamWriter.h"
  16 #include "llvm/Bitcode/LLVMBitCodes.h"
  17 #include "ValueEnumerator.h"
  18 #include "llvm/Constants.h"
  19 #include "llvm/DerivedTypes.h"
  20 #include "llvm/Instructions.h"
  21 #include "llvm/Module.h"
  22 #include "llvm/TypeSymbolTable.h"
  23 #include "llvm/ValueSymbolTable.h"
  24 #include "llvm/Support/MathExtras.h"
  25 using namespace llvm;
  26
  27 static const unsigned CurVersion = 0;
  28
  29 static unsigned GetEncodedCastOpcode(unsigned Opcode) {
  30   switch (Opcode) {
  31   default: assert(0 && "Unknown cast instruction!");
  32   case Instruction::Trunc   : return bitc::CAST_TRUNC;
  33   case Instruction::ZExt    : return bitc::CAST_ZEXT;
  34   case Instruction::SExt    : return bitc::CAST_SEXT;
  35   case Instruction::FPToUI  : return bitc::CAST_FPTOUI;
  36   case Instruction::FPToSI  : return bitc::CAST_FPTOSI;
  37   case Instruction::UIToFP  : return bitc::CAST_UITOFP;
  38   case Instruction::SIToFP  : return bitc::CAST_SITOFP;
  39   case Instruction::FPTrunc : return bitc::CAST_FPTRUNC;
  40   case Instruction::FPExt   : return bitc::CAST_FPEXT;
  41   case Instruction::PtrToInt: return bitc::CAST_PTRTOINT;
  42   case Instruction::IntToPtr: return bitc::CAST_INTTOPTR;
  43   case Instruction::BitCast : return bitc::CAST_BITCAST;
  44   }
  45 }
  46
  47 static unsigned GetEncodedBinaryOpcode(unsigned Opcode) {
  48   switch (Opcode) {
  49   default: assert(0 && "Unknown binary instruction!");
  50   case Instruction::Add:  return bitc::BINOP_ADD;
  51   case Instruction::Sub:  return bitc::BINOP_SUB;
  52   case Instruction::Mul:  return bitc::BINOP_MUL;
  53   case Instruction::UDiv: return bitc::BINOP_UDIV;
  54   case Instruction::FDiv:
  55   case Instruction::SDiv: return bitc::BINOP_SDIV;
  56   case Instruction::URem: return bitc::BINOP_UREM;
  57   case Instruction::FRem:
  58   case Instruction::SRem: return bitc::BINOP_SREM;
  59   case Instruction::Shl:  return bitc::BINOP_SHL;
  60   case Instruction::LShr: return bitc::BINOP_LSHR;
  61   case Instruction::AShr: return bitc::BINOP_ASHR;
  62   case Instruction::And:  return bitc::BINOP_AND;
  63   case Instruction::Or:   return bitc::BINOP_OR;
  64   case Instruction::Xor:  return bitc::BINOP_XOR;
  65   }
  66 }
  67
  68
  69
  70 static void WriteStringRecord(unsigned Code, const std::string &Str,
  71                               unsigned AbbrevToUse, BitstreamWriter &Stream) {
  72   SmallVector<unsigned, 64> Vals;
  73
  74   // Code: [strlen, strchar x N]
  75   Vals.push_back(Str.size());
  76   for (unsigned i = 0, e = Str.size(); i != e; ++i)
  77     Vals.push_back(Str[i]);
  78
  79   // Emit the finished record.
  80   Stream.EmitRecord(Code, Vals, AbbrevToUse);
  81 }
  82
  83
  84 /// WriteTypeTable - Write out the type table for a module.
  85 static void WriteTypeTable(const ValueEnumerator &VE, BitstreamWriter &Stream) {
  86   const ValueEnumerator::TypeList &TypeList = VE.getTypes();
  87
  88   Stream.EnterSubblock(bitc::TYPE_BLOCK_ID, 4 /*count from # abbrevs */);
  89   SmallVector<uint64_t, 64> TypeVals;
  90
  91   // FIXME: Set up abbrevs now that we know the width of the type fields, etc.
  92
  93   // Emit an entry count so the reader can reserve space.
  94   TypeVals.push_back(TypeList.size());
  95   Stream.EmitRecord(bitc::TYPE_CODE_NUMENTRY, TypeVals);
  96   TypeVals.clear();
  97
  98   // Loop over all of the types, emitting each in turn.
  99   for (unsigned i = 0, e = TypeList.size(); i != e; ++i) {
 100     const Type *T = TypeList[i].first;
 101     int AbbrevToUse = 0;
 102     unsigned Code = 0;
 103
 104     switch (T->getTypeID()) {
 105     case Type::PackedStructTyID: // FIXME: Delete Type::PackedStructTyID.
 106     default: assert(0 && "Unknown type!");
 107     case Type::VoidTyID:   Code = bitc::TYPE_CODE_VOID;   break;
 108     case Type::FloatTyID:  Code = bitc::TYPE_CODE_FLOAT;  break;
 109     case Type::DoubleTyID: Code = bitc::TYPE_CODE_DOUBLE; break;
 110     case Type::LabelTyID:  Code = bitc::TYPE_CODE_LABEL;  break;
 111     case Type::OpaqueTyID: Code = bitc::TYPE_CODE_OPAQUE; break;
 112     case Type::IntegerTyID:
 113       // INTEGER: [width]
 114       Code = bitc::TYPE_CODE_INTEGER;
 115       TypeVals.push_back(cast<IntegerType>(T)->getBitWidth());
 116       break;
 117     case Type::PointerTyID:
 118       // POINTER: [pointee type]
 119       Code = bitc::TYPE_CODE_POINTER;
 120       TypeVals.push_back(VE.getTypeID(cast<PointerType>(T)->getElementType()));
 121       break;
 122
 123     case Type::FunctionTyID: {
 124       const FunctionType *FT = cast<FunctionType>(T);
 125       // FUNCTION: [isvararg, #pararms, paramty x N]
 126       Code = bitc::TYPE_CODE_FUNCTION;
 127       TypeVals.push_back(FT->isVarArg());
 128       TypeVals.push_back(VE.getTypeID(FT->getReturnType()));
 129       // FIXME: PARAM ATTR ID!
 130       TypeVals.push_back(FT->getNumParams());
 131       for (unsigned i = 0, e = FT->getNumParams(); i != e; ++i)
 132         TypeVals.push_back(VE.getTypeID(FT->getParamType(i)));
 133       break;
 134     }
 135     case Type::StructTyID: {
 136       const StructType *ST = cast<StructType>(T);
 137       // STRUCT: [ispacked, #elts, eltty x N]
 138       Code = bitc::TYPE_CODE_STRUCT;
 139       TypeVals.push_back(ST->isPacked());
 140       TypeVals.push_back(ST->getNumElements());
 141       // Output all of the element types...
 142       for (StructType::element_iterator I = ST->element_begin(),
 143            E = ST->element_end(); I != E; ++I)
 144         TypeVals.push_back(VE.getTypeID(*I));
 145       break;
 146     }
 147     case Type::ArrayTyID: {
 148       const ArrayType *AT = cast<ArrayType>(T);
 149       // ARRAY: [numelts, eltty]
 150       Code = bitc::TYPE_CODE_ARRAY;
 151       TypeVals.push_back(AT->getNumElements());
 152       TypeVals.push_back(VE.getTypeID(AT->getElementType()));
 153       break;
 154     }
 155     case Type::VectorTyID: {
 156       const VectorType *VT = cast<VectorType>(T);
 157       // VECTOR [numelts, eltty]
 158       Code = bitc::TYPE_CODE_VECTOR;
 159       TypeVals.push_back(VT->getNumElements());
 160       TypeVals.push_back(VE.getTypeID(VT->getElementType()));
 161       break;
 162     }
 163     }
 164
 165     // Emit the finished record.
 166     Stream.EmitRecord(Code, TypeVals, AbbrevToUse);
 167     TypeVals.clear();
 168   }
 169
 170   Stream.ExitBlock();
 171 }
 172
 173 static unsigned getEncodedLinkage(const GlobalValue *GV) {
 174   switch (GV->getLinkage()) {
 175   default: assert(0 && "Invalid linkage!");
 176   case GlobalValue::ExternalLinkage:     return 0;
 177   case GlobalValue::WeakLinkage:         return 1;
 178   case GlobalValue::AppendingLinkage:    return 2;
 179   case GlobalValue::InternalLinkage:     return 3;
 180   case GlobalValue::LinkOnceLinkage:     return 4;
 181   case GlobalValue::DLLImportLinkage:    return 5;
 182   case GlobalValue::DLLExportLinkage:    return 6;
 183   case GlobalValue::ExternalWeakLinkage: return 7;
 184   }
 185 }
 186
 187 static unsigned getEncodedVisibility(const GlobalValue *GV) {
 188   switch (GV->getVisibility()) {
 189   default: assert(0 && "Invalid visibility!");
 190   case GlobalValue::DefaultVisibility:   return 0;
 191   case GlobalValue::HiddenVisibility:    return 1;
 192   case GlobalValue::ProtectedVisibility: return 2;
 193   }
 194 }
 195
 196 // Emit top-level description of module, including target triple, inline asm,
 197 // descriptors for global variables, and function prototype info.
 198 static void WriteModuleInfo(const Module *M, const ValueEnumerator &VE,
 199                             BitstreamWriter &Stream) {
 200   // Emit the list of dependent libraries for the Module.
 201   for (Module::lib_iterator I = M->lib_begin(), E = M->lib_end(); I != E; ++I)
 202     WriteStringRecord(bitc::MODULE_CODE_DEPLIB, *I, 0/*TODO*/, Stream);
 203
 204   // Emit various pieces of data attached to a module.
 205   if (!M->getTargetTriple().empty())
 206     WriteStringRecord(bitc::MODULE_CODE_TRIPLE, M->getTargetTriple(),
 207                       0/*TODO*/, Stream);
 208   if (!M->getDataLayout().empty())
 209     WriteStringRecord(bitc::MODULE_CODE_DATALAYOUT, M->getDataLayout(),
 210                       0/*TODO*/, Stream);
 211   if (!M->getModuleInlineAsm().empty())
 212     WriteStringRecord(bitc::MODULE_CODE_ASM, M->getModuleInlineAsm(),
 213                       0/*TODO*/, Stream);
 214
 215   // Emit information about sections, computing how many there are.  Also
 216   // compute the maximum alignment value.
 217   std::map<std::string, unsigned> SectionMap;
 218   unsigned MaxAlignment = 0;
 219   unsigned MaxGlobalType = 0;
 220   for (Module::const_global_iterator GV = M->global_begin(),E = M->global_end();
 221        GV != E; ++GV) {
 222     MaxAlignment = std::max(MaxAlignment, GV->getAlignment());
 223     MaxGlobalType = std::max(MaxGlobalType, VE.getTypeID(GV->getType()));
 224
 225     if (!GV->hasSection()) continue;
 226     // Give section names unique ID's.
 227     unsigned &Entry = SectionMap[GV->getSection()];
 228     if (Entry != 0) continue;
 229     WriteStringRecord(bitc::MODULE_CODE_SECTIONNAME, GV->getSection(),
 230                       0/*TODO*/, Stream);
 231     Entry = SectionMap.size();
 232   }
 233   for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) {
 234     MaxAlignment = std::max(MaxAlignment, F->getAlignment());
 235     if (!F->hasSection()) continue;
 236     // Give section names unique ID's.
 237     unsigned &Entry = SectionMap[F->getSection()];
 238     if (Entry != 0) continue;
 239     WriteStringRecord(bitc::MODULE_CODE_SECTIONNAME, F->getSection(),
 240                       0/*TODO*/, Stream);
 241     Entry = SectionMap.size();
 242   }
 243
 244   // Emit abbrev for globals, now that we know # sections and max alignment.
 245   unsigned SimpleGVarAbbrev = 0;
 246   if (!M->global_empty()) {
 247     // Add an abbrev for common globals with no visibility or thread localness.
 248     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
 249     Abbv->Add(BitCodeAbbrevOp(bitc::MODULE_CODE_GLOBALVAR));
 250     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::FixedWidth,
 251                               Log2_32_Ceil(MaxGlobalType+1)));
 252     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::FixedWidth, 1)); // Constant.
 253     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));        // Initializer.
 254     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::FixedWidth, 3)); // Linkage.
 255     if (MaxAlignment == 0)                                     // Alignment.
 256       Abbv->Add(BitCodeAbbrevOp(0));
 257     else {
 258       unsigned MaxEncAlignment = Log2_32(MaxAlignment)+1;
 259       Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::FixedWidth,
 260                                Log2_32_Ceil(MaxEncAlignment+1)));
 261     }
 262     if (SectionMap.empty())                                    // Section.
 263       Abbv->Add(BitCodeAbbrevOp(0));
 264     else
 265       Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::FixedWidth,
 266                                Log2_32_Ceil(SectionMap.size()+1)));
 267     // Don't bother emitting vis + thread local.
 268     SimpleGVarAbbrev = Stream.EmitAbbrev(Abbv);
 269   }
 270
 271   // Emit the global variable information.
 272   SmallVector<unsigned, 64> Vals;
 273   for (Module::const_global_iterator GV = M->global_begin(),E = M->global_end();
 274        GV != E; ++GV) {
 275     unsigned AbbrevToUse = 0;
 276
 277     // GLOBALVAR: [type, isconst, initid,
 278     //             linkage, alignment, section, visibility, threadlocal]
 279     Vals.push_back(VE.getTypeID(GV->getType()));
 280     Vals.push_back(GV->isConstant());
 281     Vals.push_back(GV->isDeclaration() ? 0 :
 282                    (VE.getValueID(GV->getInitializer()) + 1));
 283     Vals.push_back(getEncodedLinkage(GV));
 284     Vals.push_back(Log2_32(GV->getAlignment())+1);
 285     Vals.push_back(GV->hasSection() ? SectionMap[GV->getSection()] : 0);
 286     if (GV->isThreadLocal() ||
 287         GV->getVisibility() != GlobalValue::DefaultVisibility) {
 288       Vals.push_back(getEncodedVisibility(GV));
 289       Vals.push_back(GV->isThreadLocal());
 290     } else {
 291       AbbrevToUse = SimpleGVarAbbrev;
 292     }
 293
 294     Stream.EmitRecord(bitc::MODULE_CODE_GLOBALVAR, Vals, AbbrevToUse);
 295     Vals.clear();
 296   }
 297
 298   // Emit the function proto information.
 299   for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) {
 300     // FUNCTION:  [type, callingconv, isproto, linkage, alignment, section,
 301     //             visibility]
 302     Vals.push_back(VE.getTypeID(F->getType()));
 303     Vals.push_back(F->getCallingConv());
 304     Vals.push_back(F->isDeclaration());
 305     Vals.push_back(getEncodedLinkage(F));
 306     Vals.push_back(Log2_32(F->getAlignment())+1);
 307     Vals.push_back(F->hasSection() ? SectionMap[F->getSection()] : 0);
 308     Vals.push_back(getEncodedVisibility(F));
 309
 310     unsigned AbbrevToUse = 0;
 311     Stream.EmitRecord(bitc::MODULE_CODE_FUNCTION, Vals, AbbrevToUse);
 312     Vals.clear();
 313   }
 314
 315
 316   // Emit the alias information.
 317   for (Module::const_alias_iterator AI = M->alias_begin(), E = M->alias_end();
 318        AI != E; ++AI) {
 319     Vals.push_back(VE.getTypeID(AI->getType()));
 320     Vals.push_back(VE.getValueID(AI->getAliasee()));
 321     Vals.push_back(getEncodedLinkage(AI));
 322     unsigned AbbrevToUse = 0;
 323     Stream.EmitRecord(bitc::MODULE_CODE_ALIAS, Vals, AbbrevToUse);
 324     Vals.clear();
 325   }
 326 }
 327
 328
 329 static void WriteConstants(unsigned FirstVal, unsigned LastVal,
 330                            const ValueEnumerator &VE,
 331                            BitstreamWriter &Stream) {
 332   if (FirstVal == LastVal) return;
 333
 334   Stream.EnterSubblock(bitc::CONSTANTS_BLOCK_ID, 2);
 335
 336   // FIXME: Install and use abbrevs to reduce size.  Install them globally so
 337   // they don't need to be reemitted for each function body.
 338
 339   SmallVector<uint64_t, 64> Record;
 340
 341   const ValueEnumerator::ValueList &Vals = VE.getValues();
 342   const Type *LastTy = 0;
 343   for (unsigned i = FirstVal; i != LastVal; ++i) {
 344     const Value *V = Vals[i].first;
 345     // If we need to switch types, do so now.
 346     if (V->getType() != LastTy) {
 347       LastTy = V->getType();
 348       Record.push_back(VE.getTypeID(LastTy));
 349       Stream.EmitRecord(bitc::CST_CODE_SETTYPE, Record);
 350       Record.clear();
 351     }
 352
 353     if (const InlineAsm *IA = dyn_cast<InlineAsm>(V)) {
 354       assert(0 && IA && "FIXME: Inline asm writing unimp!");
 355       continue;
 356     }
 357     const Constant *C = cast<Constant>(V);
 358     unsigned Code = -1U;
 359     unsigned AbbrevToUse = 0;
 360     if (C->isNullValue()) {
 361       Code = bitc::CST_CODE_NULL;
 362     } else if (isa<UndefValue>(C)) {
 363       Code = bitc::CST_CODE_UNDEF;
 364     } else if (const ConstantInt *IV = dyn_cast<ConstantInt>(C)) {
 365       if (IV->getBitWidth() <= 64) {
 366         int64_t V = IV->getSExtValue();
 367         if (V >= 0)
 368           Record.push_back(V << 1);
 369         else
 370           Record.push_back((-V << 1) | 1);
 371         Code = bitc::CST_CODE_INTEGER;
 372       } else {                             // Wide integers, > 64 bits in size.
 373         // We have an arbitrary precision integer value to write whose
 374         // bit width is > 64. However, in canonical unsigned integer
 375         // format it is likely that the high bits are going to be zero.
 376         // So, we only write the number of active words.
 377         unsigned NWords = IV->getValue().getActiveWords();
 378         const uint64_t *RawWords = IV->getValue().getRawData();
 379         Record.push_back(NWords);
 380         for (unsigned i = 0; i != NWords; ++i) {
 381           int64_t V = RawWords[i];
 382           if (V >= 0)
 383             Record.push_back(V << 1);
 384           else
 385             Record.push_back((-V << 1) | 1);
 386         }
 387         Code = bitc::CST_CODE_WIDE_INTEGER;
 388       }
 389     } else if (const ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
 390       Code = bitc::CST_CODE_FLOAT;
 391       if (CFP->getType() == Type::FloatTy) {
 392         Record.push_back(FloatToBits((float)CFP->getValue()));
 393       } else {
 394         assert (CFP->getType() == Type::DoubleTy && "Unknown FP type!");
 395         Record.push_back(DoubleToBits((double)CFP->getValue()));
 396       }
 397     } else if (isa<ConstantArray>(C) || isa<ConstantStruct>(V) ||
 398                isa<ConstantVector>(V)) {
 399       Code = bitc::CST_CODE_AGGREGATE;
 400       Record.push_back(C->getNumOperands());
 401       for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i)
 402         Record.push_back(VE.getValueID(C->getOperand(i)));
 403     } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
 404       switch (CE->getOpcode()) {
 405       default:
 406         if (Instruction::isCast(CE->getOpcode())) {
 407           Code = bitc::CST_CODE_CE_CAST;
 408           Record.push_back(GetEncodedCastOpcode(CE->getOpcode()));
 409           Record.push_back(VE.getTypeID(C->getOperand(0)->getType()));
 410           Record.push_back(VE.getValueID(C->getOperand(0)));
 411         } else {
 412           assert(CE->getNumOperands() == 2 && "Unknown constant expr!");
 413           Code = bitc::CST_CODE_CE_BINOP;
 414           Record.push_back(GetEncodedBinaryOpcode(CE->getOpcode()));
 415           Record.push_back(VE.getValueID(C->getOperand(0)));
 416           Record.push_back(VE.getValueID(C->getOperand(1)));
 417         }
 418         break;
 419       case Instruction::GetElementPtr:
 420         Code = bitc::CST_CODE_CE_GEP;
 421         Record.push_back(CE->getNumOperands());
 422         for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i) {
 423           Record.push_back(VE.getTypeID(C->getOperand(i)->getType()));
 424           Record.push_back(VE.getValueID(C->getOperand(i)));
 425         }
 426         break;
 427       case Instruction::Select:
 428         Code = bitc::CST_CODE_CE_SELECT;
 429         Record.push_back(VE.getValueID(C->getOperand(0)));
 430         Record.push_back(VE.getValueID(C->getOperand(1)));
 431         Record.push_back(VE.getValueID(C->getOperand(2)));
 432         break;
 433       case Instruction::ExtractElement:
 434         Code = bitc::CST_CODE_CE_EXTRACTELT;
 435         Record.push_back(VE.getTypeID(C->getOperand(0)->getType()));
 436         Record.push_back(VE.getValueID(C->getOperand(0)));
 437         Record.push_back(VE.getValueID(C->getOperand(1)));
 438         break;
 439       case Instruction::InsertElement:
 440         Code = bitc::CST_CODE_CE_INSERTELT;
 441         Record.push_back(VE.getValueID(C->getOperand(0)));
 442         Record.push_back(VE.getValueID(C->getOperand(1)));
 443         Record.push_back(VE.getValueID(C->getOperand(2)));
 444         break;
 445       case Instruction::ShuffleVector:
 446         Code = bitc::CST_CODE_CE_SHUFFLEVEC;
 447         Record.push_back(VE.getValueID(C->getOperand(0)));
 448         Record.push_back(VE.getValueID(C->getOperand(1)));
 449         Record.push_back(VE.getValueID(C->getOperand(2)));
 450         break;
 451       case Instruction::ICmp:
 452       case Instruction::FCmp:
 453         Code = bitc::CST_CODE_CE_CMP;
 454         Record.push_back(VE.getTypeID(C->getOperand(0)->getType()));
 455         Record.push_back(VE.getValueID(C->getOperand(0)));
 456         Record.push_back(VE.getValueID(C->getOperand(1)));
 457         Record.push_back(CE->getPredicate());
 458         break;
 459       }
 460     } else {
 461       assert(0 && "Unknown constant!");
 462     }
 463     Stream.EmitRecord(Code, Record, AbbrevToUse);
 464     Record.clear();
 465   }
 466
 467   Stream.ExitBlock();
 468 }
 469
 470 static void WriteModuleConstants(const ValueEnumerator &VE,
 471                                  BitstreamWriter &Stream) {
 472   const ValueEnumerator::ValueList &Vals = VE.getValues();
 473
 474   // Find the first constant to emit, which is the first non-globalvalue value.
 475   // We know globalvalues have been emitted by WriteModuleInfo.
 476   for (unsigned i = 0, e = Vals.size(); i != e; ++i) {
 477     if (!isa<GlobalValue>(Vals[i].first)) {
 478       WriteConstants(i, Vals.size(), VE, Stream);
 479       return;
 480     }
 481   }
 482 }
 483
 484 /// WriteInstruction - Emit an instruction to the specified stream.
 485 static void WriteInstruction(const Instruction &I, ValueEnumerator &VE,
 486                              BitstreamWriter &Stream,
 487                              SmallVector<unsigned, 64> &Vals) {
 488   unsigned Code = 0;
 489   unsigned AbbrevToUse = 0;
 490   switch (I.getOpcode()) {
 491   default:
 492     if (Instruction::isCast(I.getOpcode())) {
 493       Code = bitc::FUNC_CODE_INST_CAST;
 494       Vals.push_back(GetEncodedCastOpcode(I.getOpcode()));
 495       Vals.push_back(VE.getTypeID(I.getType()));
 496       Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));
 497       Vals.push_back(VE.getValueID(I.getOperand(0)));
 498     } else {
 499       assert(isa<BinaryOperator>(I) && "Unknown instruction!");
 500       Code = bitc::CST_CODE_CE_BINOP;
 501       Vals.push_back(GetEncodedBinaryOpcode(I.getOpcode()));
 502       Vals.push_back(VE.getTypeID(I.getType()));
 503       Vals.push_back(VE.getValueID(I.getOperand(0)));
 504       Vals.push_back(VE.getValueID(I.getOperand(1)));
 505     }
 506     break;
 507
 508   case Instruction::GetElementPtr:
 509     Code = bitc::FUNC_CODE_INST_GEP;
 510     Vals.push_back(I.getNumOperands());
 511     for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) {
 512       Vals.push_back(VE.getTypeID(I.getOperand(i)->getType()));
 513       Vals.push_back(VE.getValueID(I.getOperand(i)));
 514     }
 515     break;
 516   case Instruction::Select:
 517     Code = bitc::FUNC_CODE_INST_SELECT;
 518     Vals.push_back(VE.getTypeID(I.getType()));
 519     Vals.push_back(VE.getValueID(I.getOperand(0)));
 520     Vals.push_back(VE.getValueID(I.getOperand(1)));
 521     Vals.push_back(VE.getValueID(I.getOperand(2)));
 522     break;
 523   case Instruction::ExtractElement:
 524     Code = bitc::FUNC_CODE_INST_EXTRACTELT;
 525     Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));
 526     Vals.push_back(VE.getValueID(I.getOperand(0)));
 527     Vals.push_back(VE.getValueID(I.getOperand(1)));
 528     break;
 529   case Instruction::InsertElement:
 530     Code = bitc::FUNC_CODE_INST_INSERTELT;
 531     Vals.push_back(VE.getTypeID(I.getType()));
 532     Vals.push_back(VE.getValueID(I.getOperand(0)));
 533     Vals.push_back(VE.getValueID(I.getOperand(1)));
 534     Vals.push_back(VE.getValueID(I.getOperand(2)));
 535     break;
 536   case Instruction::ShuffleVector:
 537     Code = bitc::FUNC_CODE_INST_SHUFFLEVEC;
 538     Vals.push_back(VE.getTypeID(I.getType()));
 539     Vals.push_back(VE.getValueID(I.getOperand(0)));
 540     Vals.push_back(VE.getValueID(I.getOperand(1)));
 541     Vals.push_back(VE.getValueID(I.getOperand(2)));
 542     break;
 543   case Instruction::ICmp:
 544   case Instruction::FCmp:
 545     Code = bitc::FUNC_CODE_INST_CMP;
 546     Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));
 547     Vals.push_back(VE.getValueID(I.getOperand(0)));
 548     Vals.push_back(VE.getValueID(I.getOperand(1)));
 549     Vals.push_back(cast<CmpInst>(I).getPredicate());
 550     break;
 551
 552   case Instruction::Ret:
 553     Code = bitc::FUNC_CODE_INST_RET;
 554     if (I.getNumOperands()) {
 555       Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));
 556       Vals.push_back(VE.getValueID(I.getOperand(0)));
 557     }
 558     break;
 559   case Instruction::Br:
 560     Code = bitc::FUNC_CODE_INST_BR;
 561     Vals.push_back(VE.getValueID(I.getOperand(0)));
 562     if (cast<BranchInst>(I).isConditional()) {
 563       Vals.push_back(VE.getValueID(I.getOperand(1)));
 564       Vals.push_back(VE.getValueID(I.getOperand(2)));
 565     }
 566     break;
 567   case Instruction::Switch:
 568     Code = bitc::FUNC_CODE_INST_SWITCH;
 569     Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));
 570     Vals.push_back(I.getNumOperands());
 571     for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
 572       Vals.push_back(VE.getValueID(I.getOperand(i)));
 573     break;
 574   case Instruction::Invoke:
 575     Code = bitc::FUNC_CODE_INST_INVOKE;
 576     // FIXME: param attrs
 577     Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));
 578     Vals.push_back(VE.getValueID(I.getOperand(0)));  // callee
 579     Vals.push_back(VE.getValueID(I.getOperand(1)));  // normal
 580     Vals.push_back(VE.getValueID(I.getOperand(2)));  // unwind
 581
 582     // Emit value #'s for the fixed parameters.
 583     const PointerType *PTy = cast<PointerType>(I.getOperand(0)->getType());
 584     const FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
 585     for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
 586       Vals.push_back(VE.getValueID(I.getOperand(i+3)));  // fixed param.
 587
 588     // Emit type/value pairs for varargs params.
 589     if (FTy->isVarArg()) {
 590       unsigned NumVarargs = I.getNumOperands()-3-FTy->getNumParams();
 591       Vals.push_back(NumVarargs);
 592       for (unsigned i = I.getNumOperands()-NumVarargs, e = I.getNumOperands();
 593            i != e; ++i) {
 594         Vals.push_back(VE.getTypeID(I.getOperand(i)->getType()));
 595         Vals.push_back(VE.getValueID(I.getOperand(i)));
 596       }
 597     }
 598     break;
 599   case Instruction::Unwind:
 600     Code = bitc::FUNC_CODE_INST_UNWIND;
 601     break;
 602   case Instruction::Unreachable:
 603     Code = bitc::FUNC_CODE_INST_UNREACHABLE;
 604     break;
 605
 606   case Instruction::PHI:
 607     Code = bitc::FUNC_CODE_INST_PHI;
 608     Vals.push_back(VE.getTypeID(I.getType()));
 609     Vals.push_back(I.getNumOperands());
 610     for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
 611       Vals.push_back(VE.getValueID(I.getOperand(i)));
 612     break;
 613
 614   case Instruction::Malloc:
 615     Code = bitc::FUNC_CODE_INST_MALLOC;
 616     Vals.push_back(VE.getTypeID(I.getType()));
 617     Vals.push_back(VE.getValueID(I.getOperand(0))); // size.
 618     Vals.push_back(Log2_32(cast<MallocInst>(I).getAlignment())+1);
 619     break;
 620
 621   case Instruction::Free:
 622     Code = bitc::FUNC_CODE_INST_FREE;
 623     Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));
 624     Vals.push_back(VE.getValueID(I.getOperand(0)));
 625     break;
 626
 627   case Instruction::Alloca:
 628     Code = bitc::FUNC_CODE_INST_ALLOCA;
 629     Vals.push_back(VE.getTypeID(I.getType()));
 630     Vals.push_back(VE.getValueID(I.getOperand(0))); // size.
 631     Vals.push_back(Log2_32(cast<AllocaInst>(I).getAlignment())+1);
 632     break;
 633
 634   case Instruction::Load:
 635     Code = bitc::FUNC_CODE_INST_LOAD;
 636     Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));
 637     Vals.push_back(VE.getValueID(I.getOperand(0))); // ptr.
 638     Vals.push_back(Log2_32(cast<LoadInst>(I).getAlignment())+1);
 639     Vals.push_back(cast<LoadInst>(I).isVolatile());
 640     break;
 641   case Instruction::Store:
 642     Code = bitc::FUNC_CODE_INST_STORE;
 643     Vals.push_back(VE.getTypeID(I.getOperand(1)->getType()));   // Pointer
 644     Vals.push_back(VE.getValueID(I.getOperand(0))); // val.
 645     Vals.push_back(VE.getValueID(I.getOperand(1))); // ptr.
 646     Vals.push_back(Log2_32(cast<StoreInst>(I).getAlignment())+1);
 647     Vals.push_back(cast<StoreInst>(I).isVolatile());
 648     break;
 649   case Instruction::Call: {
 650     Code = bitc::FUNC_CODE_INST_CALL;
 651     // FIXME: param attrs
 652     Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));
 653     Vals.push_back(VE.getValueID(I.getOperand(0)));  // callee
 654
 655     // Emit value #'s for the fixed parameters.
 656     const PointerType *PTy = cast<PointerType>(I.getOperand(0)->getType());
 657     const FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
 658     for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
 659       Vals.push_back(VE.getValueID(I.getOperand(i+1)));  // fixed param.
 660
 661       // Emit type/value pairs for varargs params.
 662       if (FTy->isVarArg()) {
 663         unsigned NumVarargs = I.getNumOperands()-1-FTy->getNumParams();
 664         Vals.push_back(NumVarargs);
 665         for (unsigned i = I.getNumOperands()-NumVarargs, e = I.getNumOperands();
 666              i != e; ++i) {
 667           Vals.push_back(VE.getTypeID(I.getOperand(i)->getType()));
 668           Vals.push_back(VE.getValueID(I.getOperand(i)));
 669         }
 670       }
 671     }
 672     break;
 673
 674   case Instruction::VAArg:
 675     Code = bitc::FUNC_CODE_INST_VAARG;
 676     Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));   // valistty
 677     Vals.push_back(VE.getValueID(I.getOperand(0))); // valist.
 678     Vals.push_back(VE.getTypeID(I.getType())); // restype.
 679     break;
 680   }
 681
 682   Stream.EmitRecord(Code, Vals, AbbrevToUse);
 683   Vals.clear();
 684 }
 685
 686 /// WriteFunction - Emit a function body to the module stream.
 687 static void WriteFunction(const Function &F, ValueEnumerator &VE,
 688                           BitstreamWriter &Stream) {
 689   Stream.EnterSubblock(bitc::FUNCTION_BLOCK_ID, 3);
 690   VE.incorporateFunction(F);
 691
 692   SmallVector<unsigned, 64> Vals;
 693
 694   // Emit the number of basic blocks, so the reader can create them ahead of
 695   // time.
 696   Vals.push_back(VE.getBasicBlocks().size());
 697   Stream.EmitRecord(bitc::FUNC_CODE_DECLAREBLOCKS, Vals);
 698   Vals.clear();
 699
 700   // FIXME: Function attributes?
 701
 702   // If there are function-local constants, emit them now.
 703   unsigned CstStart, CstEnd;
 704   VE.getFunctionConstantRange(CstStart, CstEnd);
 705   WriteConstants(CstStart, CstEnd, VE, Stream);
 706
 707   // Finally, emit all the instructions, in order.
 708   for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
 709     for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I)
 710       WriteInstruction(*I, VE, Stream, Vals);
 711
 712   VE.purgeFunction();
 713   Stream.ExitBlock();
 714 }
 715
 716 /// WriteTypeSymbolTable - Emit a block for the specified type symtab.
 717 static void WriteTypeSymbolTable(const TypeSymbolTable &TST,
 718                                  const ValueEnumerator &VE,
 719                                  BitstreamWriter &Stream) {
 720   if (TST.empty()) return;
 721
 722   Stream.EnterSubblock(bitc::TYPE_SYMTAB_BLOCK_ID, 3);
 723
 724   // FIXME: Set up the abbrev, we know how many types there are!
 725   // FIXME: We know if the type names can use 7-bit ascii.
 726
 727   SmallVector<unsigned, 64> NameVals;
 728
 729   for (TypeSymbolTable::const_iterator TI = TST.begin(), TE = TST.end();
 730        TI != TE; ++TI) {
 731     unsigned AbbrevToUse = 0;
 732
 733     // TST_ENTRY: [typeid, namelen, namechar x N]
 734     NameVals.push_back(VE.getTypeID(TI->second));
 735
 736     const std::string &Str = TI->first;
 737     NameVals.push_back(Str.size());
 738     for (unsigned i = 0, e = Str.size(); i != e; ++i)
 739       NameVals.push_back(Str[i]);
 740
 741     // Emit the finished record.
 742     Stream.EmitRecord(bitc::VST_CODE_ENTRY, NameVals, AbbrevToUse);
 743     NameVals.clear();
 744   }
 745
 746   Stream.ExitBlock();
 747 }
 748
 749 // Emit names for globals/functions etc.
 750 static void WriteValueSymbolTable(const ValueSymbolTable &VST,
 751                                   const ValueEnumerator &VE,
 752                                   BitstreamWriter &Stream) {
 753   if (VST.empty()) return;
 754   Stream.EnterSubblock(bitc::VALUE_SYMTAB_BLOCK_ID, 3);
 755
 756   // FIXME: Set up the abbrev, we know how many values there are!
 757   // FIXME: We know if the type names can use 7-bit ascii.
 758   SmallVector<unsigned, 64> NameVals;
 759
 760   for (ValueSymbolTable::const_iterator SI = VST.begin(), SE = VST.end();
 761        SI != SE; ++SI) {
 762     unsigned AbbrevToUse = 0;
 763
 764     // VST_ENTRY: [valueid, namelen, namechar x N]
 765     NameVals.push_back(VE.getValueID(SI->getValue()));
 766
 767     NameVals.push_back(SI->getKeyLength());
 768     for (const char *P = SI->getKeyData(),
 769          *E = SI->getKeyData()+SI->getKeyLength(); P != E; ++P)
 770       NameVals.push_back((unsigned char)*P);
 771
 772     // Emit the finished record.
 773     Stream.EmitRecord(bitc::VST_CODE_ENTRY, NameVals, AbbrevToUse);
 774     NameVals.clear();
 775   }
 776   Stream.ExitBlock();
 777 }
 778
 779
 780 /// WriteModule - Emit the specified module to the bitstream.
 781 static void WriteModule(const Module *M, BitstreamWriter &Stream) {
 782   Stream.EnterSubblock(bitc::MODULE_BLOCK_ID, 3);
 783
 784   // Emit the version number if it is non-zero.
 785   if (CurVersion) {
 786     SmallVector<unsigned, 1> Vals;
 787     Vals.push_back(CurVersion);
 788     Stream.EmitRecord(bitc::MODULE_CODE_VERSION, Vals);
 789   }
 790
 791   // Analyze the module, enumerating globals, functions, etc.
 792   ValueEnumerator VE(M);
 793
 794   // Emit information describing all of the types in the module.
 795   WriteTypeTable(VE, Stream);
 796
 797   // Emit top-level description of module, including target triple, inline asm,
 798   // descriptors for global variables, and function prototype info.
 799   WriteModuleInfo(M, VE, Stream);
 800
 801   // Emit constants.
 802   WriteModuleConstants(VE, Stream);
 803
 804   // If we have any aggregate values in the value table, purge them - these can
 805   // only be used to initialize global variables.  Doing so makes the value
 806   // namespace smaller for code in functions.
 807   int NumNonAggregates = VE.PurgeAggregateValues();
 808   if (NumNonAggregates != -1) {
 809     SmallVector<unsigned, 1> Vals;
 810     Vals.push_back(NumNonAggregates);
 811     Stream.EmitRecord(bitc::MODULE_CODE_PURGEVALS, Vals);
 812   }
 813
 814   // Emit function bodies.
 815   for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I)
 816     if (!I->isDeclaration())
 817       WriteFunction(*I, VE, Stream);
 818
 819   // Emit the type symbol table information.
 820   WriteTypeSymbolTable(M->getTypeSymbolTable(), VE, Stream);
 821
 822   // Emit names for globals/functions etc.
 823   WriteValueSymbolTable(M->getValueSymbolTable(), VE, Stream);
 824
 825   Stream.ExitBlock();
 826 }
 827
 828 /// WriteBitcodeToFile - Write the specified module to the specified output
 829 /// stream.
 830 void llvm::WriteBitcodeToFile(const Module *M, std::ostream &Out) {
 831   std::vector<unsigned char> Buffer;
 832   BitstreamWriter Stream(Buffer);
 833
 834   Buffer.reserve(256*1024);
 835
 836   // Emit the file header.
 837   Stream.Emit((unsigned)'B', 8);
 838   Stream.Emit((unsigned)'C', 8);
 839   Stream.Emit(0x0, 4);
 840   Stream.Emit(0xC, 4);
 841   Stream.Emit(0xE, 4);
 842   Stream.Emit(0xD, 4);
 843
 844   // Emit the module.
 845   WriteModule(M, Stream);
 846
 847   // Write the generated bitstream to "Out".
 848   Out.write((char*)&Buffer.front(), Buffer.size());
 849 }