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