BitcodeWriter.cpp revision f12b379448a9f2131feba15c01714e44bedda120 
1//===--- Bitcode/Writer/BitcodeWriter.cpp - Bitcode Writer ----------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// Bitcode writer implementation.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Bitcode/ReaderWriter.h"
15#include "ValueEnumerator.h"
16#include "llvm/ADT/Triple.h"
17#include "llvm/Bitcode/BitstreamWriter.h"
18#include "llvm/Bitcode/LLVMBitCodes.h"
19#include "llvm/IR/Constants.h"
20#include "llvm/IR/DerivedTypes.h"
21#include "llvm/IR/InlineAsm.h"
22#include "llvm/IR/Instructions.h"
23#include "llvm/IR/Module.h"
24#include "llvm/IR/Operator.h"
25#include "llvm/IR/ValueSymbolTable.h"
26#include "llvm/Support/CommandLine.h"
27#include "llvm/Support/ErrorHandling.h"
28#include "llvm/Support/MathExtras.h"
29#include "llvm/Support/Program.h"
30#include "llvm/Support/raw_ostream.h"
31#include <cctype>
32#include <map>
33using namespace llvm;
34
35static cl::opt<bool>
36EnablePreserveUseListOrdering("enable-bc-uselist-preserve",
37                              cl::desc("Turn on experimental support for "
38                                       "use-list order preservation."),
39                              cl::init(false), cl::Hidden);
40
41/// These are manifest constants used by the bitcode writer. They do not need to
42/// be kept in sync with the reader, but need to be consistent within this file.
43enum {
44  // VALUE_SYMTAB_BLOCK abbrev id's.
45  VST_ENTRY_8_ABBREV = bitc::FIRST_APPLICATION_ABBREV,
46  VST_ENTRY_7_ABBREV,
47  VST_ENTRY_6_ABBREV,
48  VST_BBENTRY_6_ABBREV,
49
50  // CONSTANTS_BLOCK abbrev id's.
51  CONSTANTS_SETTYPE_ABBREV = bitc::FIRST_APPLICATION_ABBREV,
52  CONSTANTS_INTEGER_ABBREV,
53  CONSTANTS_CE_CAST_Abbrev,
54  CONSTANTS_NULL_Abbrev,
55
56  // FUNCTION_BLOCK abbrev id's.
57  FUNCTION_INST_LOAD_ABBREV = bitc::FIRST_APPLICATION_ABBREV,
58  FUNCTION_INST_BINOP_ABBREV,
59  FUNCTION_INST_BINOP_FLAGS_ABBREV,
60  FUNCTION_INST_CAST_ABBREV,
61  FUNCTION_INST_RET_VOID_ABBREV,
62  FUNCTION_INST_RET_VAL_ABBREV,
63  FUNCTION_INST_UNREACHABLE_ABBREV,
64
65  // SwitchInst Magic
66  SWITCH_INST_MAGIC = 0x4B5 // May 2012 => 1205 => Hex
67};
68
69static unsigned GetEncodedCastOpcode(unsigned Opcode) {
70  switch (Opcode) {
71  default: llvm_unreachable("Unknown cast instruction!");
72  case Instruction::Trunc   : return bitc::CAST_TRUNC;
73  case Instruction::ZExt    : return bitc::CAST_ZEXT;
74  case Instruction::SExt    : return bitc::CAST_SEXT;
75  case Instruction::FPToUI  : return bitc::CAST_FPTOUI;
76  case Instruction::FPToSI  : return bitc::CAST_FPTOSI;
77  case Instruction::UIToFP  : return bitc::CAST_UITOFP;
78  case Instruction::SIToFP  : return bitc::CAST_SITOFP;
79  case Instruction::FPTrunc : return bitc::CAST_FPTRUNC;
80  case Instruction::FPExt   : return bitc::CAST_FPEXT;
81  case Instruction::PtrToInt: return bitc::CAST_PTRTOINT;
82  case Instruction::IntToPtr: return bitc::CAST_INTTOPTR;
83  case Instruction::BitCast : return bitc::CAST_BITCAST;
84  }
85}
86
87static unsigned GetEncodedBinaryOpcode(unsigned Opcode) {
88  switch (Opcode) {
89  default: llvm_unreachable("Unknown binary instruction!");
90  case Instruction::Add:
91  case Instruction::FAdd: return bitc::BINOP_ADD;
92  case Instruction::Sub:
93  case Instruction::FSub: return bitc::BINOP_SUB;
94  case Instruction::Mul:
95  case Instruction::FMul: return bitc::BINOP_MUL;
96  case Instruction::UDiv: return bitc::BINOP_UDIV;
97  case Instruction::FDiv:
98  case Instruction::SDiv: return bitc::BINOP_SDIV;
99  case Instruction::URem: return bitc::BINOP_UREM;
100  case Instruction::FRem:
101  case Instruction::SRem: return bitc::BINOP_SREM;
102  case Instruction::Shl:  return bitc::BINOP_SHL;
103  case Instruction::LShr: return bitc::BINOP_LSHR;
104  case Instruction::AShr: return bitc::BINOP_ASHR;
105  case Instruction::And:  return bitc::BINOP_AND;
106  case Instruction::Or:   return bitc::BINOP_OR;
107  case Instruction::Xor:  return bitc::BINOP_XOR;
108  }
109}
110
111static unsigned GetEncodedRMWOperation(AtomicRMWInst::BinOp Op) {
112  switch (Op) {
113  default: llvm_unreachable("Unknown RMW operation!");
114  case AtomicRMWInst::Xchg: return bitc::RMW_XCHG;
115  case AtomicRMWInst::Add: return bitc::RMW_ADD;
116  case AtomicRMWInst::Sub: return bitc::RMW_SUB;
117  case AtomicRMWInst::And: return bitc::RMW_AND;
118  case AtomicRMWInst::Nand: return bitc::RMW_NAND;
119  case AtomicRMWInst::Or: return bitc::RMW_OR;
120  case AtomicRMWInst::Xor: return bitc::RMW_XOR;
121  case AtomicRMWInst::Max: return bitc::RMW_MAX;
122  case AtomicRMWInst::Min: return bitc::RMW_MIN;
123  case AtomicRMWInst::UMax: return bitc::RMW_UMAX;
124  case AtomicRMWInst::UMin: return bitc::RMW_UMIN;
125  }
126}
127
128static unsigned GetEncodedOrdering(AtomicOrdering Ordering) {
129  switch (Ordering) {
130  case NotAtomic: return bitc::ORDERING_NOTATOMIC;
131  case Unordered: return bitc::ORDERING_UNORDERED;
132  case Monotonic: return bitc::ORDERING_MONOTONIC;
133  case Acquire: return bitc::ORDERING_ACQUIRE;
134  case Release: return bitc::ORDERING_RELEASE;
135  case AcquireRelease: return bitc::ORDERING_ACQREL;
136  case SequentiallyConsistent: return bitc::ORDERING_SEQCST;
137  }
138  llvm_unreachable("Invalid ordering");
139}
140
141static unsigned GetEncodedSynchScope(SynchronizationScope SynchScope) {
142  switch (SynchScope) {
143  case SingleThread: return bitc::SYNCHSCOPE_SINGLETHREAD;
144  case CrossThread: return bitc::SYNCHSCOPE_CROSSTHREAD;
145  }
146  llvm_unreachable("Invalid synch scope");
147}
148
149static void WriteStringRecord(unsigned Code, StringRef Str,
150                              unsigned AbbrevToUse, BitstreamWriter &Stream) {
151  SmallVector<unsigned, 64> Vals;
152
153  // Code: [strchar x N]
154  for (unsigned i = 0, e = Str.size(); i != e; ++i) {
155    if (AbbrevToUse && !BitCodeAbbrevOp::isChar6(Str[i]))
156      AbbrevToUse = 0;
157    Vals.push_back(Str[i]);
158  }
159
160  // Emit the finished record.
161  Stream.EmitRecord(Code, Vals, AbbrevToUse);
162}
163
164/// \brief This returns an integer containing an encoding of all the LLVM
165/// attributes found in the given attribute bitset.  Any change to this encoding
166/// is a breaking change to bitcode compatibility.
167/// N.B. This should be used only by the bitcode writer!
168static uint64_t encodeLLVMAttributesForBitcode(AttributeSet Attrs,
169                                               unsigned Index) {
170  // FIXME: Remove in 4.0!
171
172  // FIXME: It doesn't make sense to store the alignment information as an
173  // expanded out value, we should store it as a log2 value.  However, we can't
174  // just change that here without breaking bitcode compatibility.  If this ever
175  // becomes a problem in practice, we should introduce new tag numbers in the
176  // bitcode file and have those tags use a more efficiently encoded alignment
177  // field.
178
179  // Store the alignment in the bitcode as a 16-bit raw value instead of a 5-bit
180  // log2 encoded value. Shift the bits above the alignment up by 11 bits.
181  uint64_t EncodedAttrs = Attrs.Raw(Index) & 0xffff;
182  if (Attrs.hasAttribute(Index, Attribute::Alignment))
183    EncodedAttrs |= Attrs.getParamAlignment(Index) << 16;
184  EncodedAttrs |= (Attrs.Raw(Index) & (0xffffULL << 21)) << 11;
185  return EncodedAttrs;
186}
187
188static void WriteAttributeGroupTable(const ValueEnumerator &VE,
189                                     BitstreamWriter &Stream) {
190  const std::vector<AttributeSet> &Attrs = VE.getAttributeSets();
191  if (Attrs.empty()) return;
192
193  Stream.EnterSubblock(bitc::PARAMATTR_GROUP_BLOCK_ID, 3);
194
195  SmallVector<uint64_t, 64> Record;
196  for (unsigned i = 0, e = Attrs.size(); i != e; ++i) {
197    AttributeSet AS = Attrs[i];
198    for (unsigned i = 0, e = AS.getNumSlots(); i != e; ++i) {
199      AttributeSet A = AS.getSlotAttributes(i);
200
201      Record.push_back(VE.getAttributeSetID(A));
202      Record.push_back(AS.getSlotIndex(i));
203
204      for (AttributeSet::iterator I = AS.begin(0), E = AS.end(0);
205           I != E; ++I) {
206        Attribute Attr = *I;
207        if (Attr.isEnumAttribute()) {
208          Record.push_back(0);
209          Record.push_back(Attr.getKindAsEnum());
210        } else if (Attr.isAlignAttribute()) {
211          Record.push_back(1);
212          Record.push_back(Attr.getKindAsEnum());
213          Record.push_back(Attr.getValueAsInt());
214        } else {
215          StringRef Kind = Attr.getKindAsString();
216          StringRef Val = Attr.getValueAsString();
217
218          Record.push_back(Val.empty() ? 3 : 4);
219          Record.append(Kind.begin(), Kind.end());
220          Record.push_back(0);
221          if (!Val.empty()) {
222            Record.append(Val.begin(), Val.end());
223            Record.push_back(0);
224          }
225        }
226      }
227
228      Stream.EmitRecord(bitc::PARAMATTR_GRP_CODE_ENTRY, Record);
229      Record.clear();
230    }
231  }
232
233  Stream.ExitBlock();
234}
235
236static void WriteAttributeTable(const ValueEnumerator &VE,
237                                BitstreamWriter &Stream) {
238  const std::vector<AttributeSet> &Attrs = VE.getAttributes();
239  if (Attrs.empty()) return;
240
241  Stream.EnterSubblock(bitc::PARAMATTR_BLOCK_ID, 3);
242
243  // FIXME: Remove this! It no longer works with the current attributes classes.
244
245  SmallVector<uint64_t, 64> Record;
246  for (unsigned i = 0, e = Attrs.size(); i != e; ++i) {
247    const AttributeSet &A = Attrs[i];
248    for (unsigned i = 0, e = A.getNumSlots(); i != e; ++i) {
249      unsigned Index = A.getSlotIndex(i);
250      Record.push_back(Index);
251      Record.push_back(encodeLLVMAttributesForBitcode(A.getSlotAttributes(i),
252                                                      Index));
253    }
254
255    Stream.EmitRecord(bitc::PARAMATTR_CODE_ENTRY_OLD, Record);
256    Record.clear();
257  }
258
259  Stream.ExitBlock();
260}
261
262/// WriteTypeTable - Write out the type table for a module.
263static void WriteTypeTable(const ValueEnumerator &VE, BitstreamWriter &Stream) {
264  const ValueEnumerator::TypeList &TypeList = VE.getTypes();
265
266  Stream.EnterSubblock(bitc::TYPE_BLOCK_ID_NEW, 4 /*count from # abbrevs */);
267  SmallVector<uint64_t, 64> TypeVals;
268
269  uint64_t NumBits = Log2_32_Ceil(VE.getTypes().size()+1);
270
271  // Abbrev for TYPE_CODE_POINTER.
272  BitCodeAbbrev *Abbv = new BitCodeAbbrev();
273  Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_POINTER));
274  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, NumBits));
275  Abbv->Add(BitCodeAbbrevOp(0));  // Addrspace = 0
276  unsigned PtrAbbrev = Stream.EmitAbbrev(Abbv);
277
278  // Abbrev for TYPE_CODE_FUNCTION.
279  Abbv = new BitCodeAbbrev();
280  Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_FUNCTION));
281  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1));  // isvararg
282  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
283  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, NumBits));
284
285  unsigned FunctionAbbrev = Stream.EmitAbbrev(Abbv);
286
287  // Abbrev for TYPE_CODE_STRUCT_ANON.
288  Abbv = new BitCodeAbbrev();
289  Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_STRUCT_ANON));
290  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1));  // ispacked
291  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
292  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, NumBits));
293
294  unsigned StructAnonAbbrev = Stream.EmitAbbrev(Abbv);
295
296  // Abbrev for TYPE_CODE_STRUCT_NAME.
297  Abbv = new BitCodeAbbrev();
298  Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_STRUCT_NAME));
299  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
300  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Char6));
301  unsigned StructNameAbbrev = Stream.EmitAbbrev(Abbv);
302
303  // Abbrev for TYPE_CODE_STRUCT_NAMED.
304  Abbv = new BitCodeAbbrev();
305  Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_STRUCT_NAMED));
306  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1));  // ispacked
307  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
308  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, NumBits));
309
310  unsigned StructNamedAbbrev = Stream.EmitAbbrev(Abbv);
311
312  // Abbrev for TYPE_CODE_ARRAY.
313  Abbv = new BitCodeAbbrev();
314  Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_ARRAY));
315  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // size
316  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, NumBits));
317
318  unsigned ArrayAbbrev = Stream.EmitAbbrev(Abbv);
319
320  // Emit an entry count so the reader can reserve space.
321  TypeVals.push_back(TypeList.size());
322  Stream.EmitRecord(bitc::TYPE_CODE_NUMENTRY, TypeVals);
323  TypeVals.clear();
324
325  // Loop over all of the types, emitting each in turn.
326  for (unsigned i = 0, e = TypeList.size(); i != e; ++i) {
327    Type *T = TypeList[i];
328    int AbbrevToUse = 0;
329    unsigned Code = 0;
330
331    switch (T->getTypeID()) {
332    default: llvm_unreachable("Unknown type!");
333    case Type::VoidTyID:      Code = bitc::TYPE_CODE_VOID;      break;
334    case Type::HalfTyID:      Code = bitc::TYPE_CODE_HALF;      break;
335    case Type::FloatTyID:     Code = bitc::TYPE_CODE_FLOAT;     break;
336    case Type::DoubleTyID:    Code = bitc::TYPE_CODE_DOUBLE;    break;
337    case Type::X86_FP80TyID:  Code = bitc::TYPE_CODE_X86_FP80;  break;
338    case Type::FP128TyID:     Code = bitc::TYPE_CODE_FP128;     break;
339    case Type::PPC_FP128TyID: Code = bitc::TYPE_CODE_PPC_FP128; break;
340    case Type::LabelTyID:     Code = bitc::TYPE_CODE_LABEL;     break;
341    case Type::MetadataTyID:  Code = bitc::TYPE_CODE_METADATA;  break;
342    case Type::X86_MMXTyID:   Code = bitc::TYPE_CODE_X86_MMX;   break;
343    case Type::IntegerTyID:
344      // INTEGER: [width]
345      Code = bitc::TYPE_CODE_INTEGER;
346      TypeVals.push_back(cast<IntegerType>(T)->getBitWidth());
347      break;
348    case Type::PointerTyID: {
349      PointerType *PTy = cast<PointerType>(T);
350      // POINTER: [pointee type, address space]
351      Code = bitc::TYPE_CODE_POINTER;
352      TypeVals.push_back(VE.getTypeID(PTy->getElementType()));
353      unsigned AddressSpace = PTy->getAddressSpace();
354      TypeVals.push_back(AddressSpace);
355      if (AddressSpace == 0) AbbrevToUse = PtrAbbrev;
356      break;
357    }
358    case Type::FunctionTyID: {
359      FunctionType *FT = cast<FunctionType>(T);
360      // FUNCTION: [isvararg, retty, paramty x N]
361      Code = bitc::TYPE_CODE_FUNCTION;
362      TypeVals.push_back(FT->isVarArg());
363      TypeVals.push_back(VE.getTypeID(FT->getReturnType()));
364      for (unsigned i = 0, e = FT->getNumParams(); i != e; ++i)
365        TypeVals.push_back(VE.getTypeID(FT->getParamType(i)));
366      AbbrevToUse = FunctionAbbrev;
367      break;
368    }
369    case Type::StructTyID: {
370      StructType *ST = cast<StructType>(T);
371      // STRUCT: [ispacked, eltty x N]
372      TypeVals.push_back(ST->isPacked());
373      // Output all of the element types.
374      for (StructType::element_iterator I = ST->element_begin(),
375           E = ST->element_end(); I != E; ++I)
376        TypeVals.push_back(VE.getTypeID(*I));
377
378      if (ST->isLiteral()) {
379        Code = bitc::TYPE_CODE_STRUCT_ANON;
380        AbbrevToUse = StructAnonAbbrev;
381      } else {
382        if (ST->isOpaque()) {
383          Code = bitc::TYPE_CODE_OPAQUE;
384        } else {
385          Code = bitc::TYPE_CODE_STRUCT_NAMED;
386          AbbrevToUse = StructNamedAbbrev;
387        }
388
389        // Emit the name if it is present.
390        if (!ST->getName().empty())
391          WriteStringRecord(bitc::TYPE_CODE_STRUCT_NAME, ST->getName(),
392                            StructNameAbbrev, Stream);
393      }
394      break;
395    }
396    case Type::ArrayTyID: {
397      ArrayType *AT = cast<ArrayType>(T);
398      // ARRAY: [numelts, eltty]
399      Code = bitc::TYPE_CODE_ARRAY;
400      TypeVals.push_back(AT->getNumElements());
401      TypeVals.push_back(VE.getTypeID(AT->getElementType()));
402      AbbrevToUse = ArrayAbbrev;
403      break;
404    }
405    case Type::VectorTyID: {
406      VectorType *VT = cast<VectorType>(T);
407      // VECTOR [numelts, eltty]
408      Code = bitc::TYPE_CODE_VECTOR;
409      TypeVals.push_back(VT->getNumElements());
410      TypeVals.push_back(VE.getTypeID(VT->getElementType()));
411      break;
412    }
413    }
414
415    // Emit the finished record.
416    Stream.EmitRecord(Code, TypeVals, AbbrevToUse);
417    TypeVals.clear();
418  }
419
420  Stream.ExitBlock();
421}
422
423static unsigned getEncodedLinkage(const GlobalValue *GV) {
424  switch (GV->getLinkage()) {
425  case GlobalValue::ExternalLinkage:                 return 0;
426  case GlobalValue::WeakAnyLinkage:                  return 1;
427  case GlobalValue::AppendingLinkage:                return 2;
428  case GlobalValue::InternalLinkage:                 return 3;
429  case GlobalValue::LinkOnceAnyLinkage:              return 4;
430  case GlobalValue::DLLImportLinkage:                return 5;
431  case GlobalValue::DLLExportLinkage:                return 6;
432  case GlobalValue::ExternalWeakLinkage:             return 7;
433  case GlobalValue::CommonLinkage:                   return 8;
434  case GlobalValue::PrivateLinkage:                  return 9;
435  case GlobalValue::WeakODRLinkage:                  return 10;
436  case GlobalValue::LinkOnceODRLinkage:              return 11;
437  case GlobalValue::AvailableExternallyLinkage:      return 12;
438  case GlobalValue::LinkerPrivateLinkage:            return 13;
439  case GlobalValue::LinkerPrivateWeakLinkage:        return 14;
440  case GlobalValue::LinkOnceODRAutoHideLinkage:      return 15;
441  }
442  llvm_unreachable("Invalid linkage");
443}
444
445static unsigned getEncodedVisibility(const GlobalValue *GV) {
446  switch (GV->getVisibility()) {
447  case GlobalValue::DefaultVisibility:   return 0;
448  case GlobalValue::HiddenVisibility:    return 1;
449  case GlobalValue::ProtectedVisibility: return 2;
450  }
451  llvm_unreachable("Invalid visibility");
452}
453
454static unsigned getEncodedThreadLocalMode(const GlobalVariable *GV) {
455  switch (GV->getThreadLocalMode()) {
456    case GlobalVariable::NotThreadLocal:         return 0;
457    case GlobalVariable::GeneralDynamicTLSModel: return 1;
458    case GlobalVariable::LocalDynamicTLSModel:   return 2;
459    case GlobalVariable::InitialExecTLSModel:    return 3;
460    case GlobalVariable::LocalExecTLSModel:      return 4;
461  }
462  llvm_unreachable("Invalid TLS model");
463}
464
465// Emit top-level description of module, including target triple, inline asm,
466// descriptors for global variables, and function prototype info.
467static void WriteModuleInfo(const Module *M, const ValueEnumerator &VE,
468                            BitstreamWriter &Stream) {
469  // Emit various pieces of data attached to a module.
470  if (!M->getTargetTriple().empty())
471    WriteStringRecord(bitc::MODULE_CODE_TRIPLE, M->getTargetTriple(),
472                      0/*TODO*/, Stream);
473  if (!M->getDataLayout().empty())
474    WriteStringRecord(bitc::MODULE_CODE_DATALAYOUT, M->getDataLayout(),
475                      0/*TODO*/, Stream);
476  if (!M->getModuleInlineAsm().empty())
477    WriteStringRecord(bitc::MODULE_CODE_ASM, M->getModuleInlineAsm(),
478                      0/*TODO*/, Stream);
479
480  // Emit information about sections and GC, computing how many there are. Also
481  // compute the maximum alignment value.
482  std::map<std::string, unsigned> SectionMap;
483  std::map<std::string, unsigned> GCMap;
484  unsigned MaxAlignment = 0;
485  unsigned MaxGlobalType = 0;
486  for (Module::const_global_iterator GV = M->global_begin(),E = M->global_end();
487       GV != E; ++GV) {
488    MaxAlignment = std::max(MaxAlignment, GV->getAlignment());
489    MaxGlobalType = std::max(MaxGlobalType, VE.getTypeID(GV->getType()));
490    if (GV->hasSection()) {
491      // Give section names unique ID's.
492      unsigned &Entry = SectionMap[GV->getSection()];
493      if (!Entry) {
494        WriteStringRecord(bitc::MODULE_CODE_SECTIONNAME, GV->getSection(),
495                          0/*TODO*/, Stream);
496        Entry = SectionMap.size();
497      }
498    }
499  }
500  for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) {
501    MaxAlignment = std::max(MaxAlignment, F->getAlignment());
502    if (F->hasSection()) {
503      // Give section names unique ID's.
504      unsigned &Entry = SectionMap[F->getSection()];
505      if (!Entry) {
506        WriteStringRecord(bitc::MODULE_CODE_SECTIONNAME, F->getSection(),
507                          0/*TODO*/, Stream);
508        Entry = SectionMap.size();
509      }
510    }
511    if (F->hasGC()) {
512      // Same for GC names.
513      unsigned &Entry = GCMap[F->getGC()];
514      if (!Entry) {
515        WriteStringRecord(bitc::MODULE_CODE_GCNAME, F->getGC(),
516                          0/*TODO*/, Stream);
517        Entry = GCMap.size();
518      }
519    }
520  }
521
522  // Emit abbrev for globals, now that we know # sections and max alignment.
523  unsigned SimpleGVarAbbrev = 0;
524  if (!M->global_empty()) {
525    // Add an abbrev for common globals with no visibility or thread localness.
526    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
527    Abbv->Add(BitCodeAbbrevOp(bitc::MODULE_CODE_GLOBALVAR));
528    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,
529                              Log2_32_Ceil(MaxGlobalType+1)));
530    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1));      // Constant.
531    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));        // Initializer.
532    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 4));      // Linkage.
533    if (MaxAlignment == 0)                                      // Alignment.
534      Abbv->Add(BitCodeAbbrevOp(0));
535    else {
536      unsigned MaxEncAlignment = Log2_32(MaxAlignment)+1;
537      Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,
538                               Log2_32_Ceil(MaxEncAlignment+1)));
539    }
540    if (SectionMap.empty())                                    // Section.
541      Abbv->Add(BitCodeAbbrevOp(0));
542    else
543      Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,
544                               Log2_32_Ceil(SectionMap.size()+1)));
545    // Don't bother emitting vis + thread local.
546    SimpleGVarAbbrev = Stream.EmitAbbrev(Abbv);
547  }
548
549  // Emit the global variable information.
550  SmallVector<unsigned, 64> Vals;
551  for (Module::const_global_iterator GV = M->global_begin(),E = M->global_end();
552       GV != E; ++GV) {
553    unsigned AbbrevToUse = 0;
554
555    // GLOBALVAR: [type, isconst, initid,
556    //             linkage, alignment, section, visibility, threadlocal,
557    //             unnamed_addr]
558    Vals.push_back(VE.getTypeID(GV->getType()));
559    Vals.push_back(GV->isConstant());
560    Vals.push_back(GV->isDeclaration() ? 0 :
561                   (VE.getValueID(GV->getInitializer()) + 1));
562    Vals.push_back(getEncodedLinkage(GV));
563    Vals.push_back(Log2_32(GV->getAlignment())+1);
564    Vals.push_back(GV->hasSection() ? SectionMap[GV->getSection()] : 0);
565    if (GV->isThreadLocal() ||
566        GV->getVisibility() != GlobalValue::DefaultVisibility ||
567        GV->hasUnnamedAddr() || GV->isExternallyInitialized()) {
568      Vals.push_back(getEncodedVisibility(GV));
569      Vals.push_back(getEncodedThreadLocalMode(GV));
570      Vals.push_back(GV->hasUnnamedAddr());
571      Vals.push_back(GV->isExternallyInitialized());
572    } else {
573      AbbrevToUse = SimpleGVarAbbrev;
574    }
575
576    Stream.EmitRecord(bitc::MODULE_CODE_GLOBALVAR, Vals, AbbrevToUse);
577    Vals.clear();
578  }
579
580  // Emit the function proto information.
581  for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) {
582    // FUNCTION:  [type, callingconv, isproto, linkage, paramattrs, alignment,
583    //             section, visibility, gc, unnamed_addr]
584    Vals.push_back(VE.getTypeID(F->getType()));
585    Vals.push_back(F->getCallingConv());
586    Vals.push_back(F->isDeclaration());
587    Vals.push_back(getEncodedLinkage(F));
588    Vals.push_back(VE.getAttributeID(F->getAttributes()));
589    Vals.push_back(Log2_32(F->getAlignment())+1);
590    Vals.push_back(F->hasSection() ? SectionMap[F->getSection()] : 0);
591    Vals.push_back(getEncodedVisibility(F));
592    Vals.push_back(F->hasGC() ? GCMap[F->getGC()] : 0);
593    Vals.push_back(F->hasUnnamedAddr());
594
595    unsigned AbbrevToUse = 0;
596    Stream.EmitRecord(bitc::MODULE_CODE_FUNCTION, Vals, AbbrevToUse);
597    Vals.clear();
598  }
599
600  // Emit the alias information.
601  for (Module::const_alias_iterator AI = M->alias_begin(), E = M->alias_end();
602       AI != E; ++AI) {
603    // ALIAS: [alias type, aliasee val#, linkage, visibility]
604    Vals.push_back(VE.getTypeID(AI->getType()));
605    Vals.push_back(VE.getValueID(AI->getAliasee()));
606    Vals.push_back(getEncodedLinkage(AI));
607    Vals.push_back(getEncodedVisibility(AI));
608    unsigned AbbrevToUse = 0;
609    Stream.EmitRecord(bitc::MODULE_CODE_ALIAS, Vals, AbbrevToUse);
610    Vals.clear();
611  }
612}
613
614static uint64_t GetOptimizationFlags(const Value *V) {
615  uint64_t Flags = 0;
616
617  if (const OverflowingBinaryOperator *OBO =
618        dyn_cast<OverflowingBinaryOperator>(V)) {
619    if (OBO->hasNoSignedWrap())
620      Flags |= 1 << bitc::OBO_NO_SIGNED_WRAP;
621    if (OBO->hasNoUnsignedWrap())
622      Flags |= 1 << bitc::OBO_NO_UNSIGNED_WRAP;
623  } else if (const PossiblyExactOperator *PEO =
624               dyn_cast<PossiblyExactOperator>(V)) {
625    if (PEO->isExact())
626      Flags |= 1 << bitc::PEO_EXACT;
627  } else if (const FPMathOperator *FPMO =
628             dyn_cast<const FPMathOperator>(V)) {
629    if (FPMO->hasUnsafeAlgebra())
630      Flags |= FastMathFlags::UnsafeAlgebra;
631    if (FPMO->hasNoNaNs())
632      Flags |= FastMathFlags::NoNaNs;
633    if (FPMO->hasNoInfs())
634      Flags |= FastMathFlags::NoInfs;
635    if (FPMO->hasNoSignedZeros())
636      Flags |= FastMathFlags::NoSignedZeros;
637    if (FPMO->hasAllowReciprocal())
638      Flags |= FastMathFlags::AllowReciprocal;
639  }
640
641  return Flags;
642}
643
644static void WriteMDNode(const MDNode *N,
645                        const ValueEnumerator &VE,
646                        BitstreamWriter &Stream,
647                        SmallVector<uint64_t, 64> &Record) {
648  for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
649    if (N->getOperand(i)) {
650      Record.push_back(VE.getTypeID(N->getOperand(i)->getType()));
651      Record.push_back(VE.getValueID(N->getOperand(i)));
652    } else {
653      Record.push_back(VE.getTypeID(Type::getVoidTy(N->getContext())));
654      Record.push_back(0);
655    }
656  }
657  unsigned MDCode = N->isFunctionLocal() ? bitc::METADATA_FN_NODE :
658                                           bitc::METADATA_NODE;
659  Stream.EmitRecord(MDCode, Record, 0);
660  Record.clear();
661}
662
663static void WriteModuleMetadata(const Module *M,
664                                const ValueEnumerator &VE,
665                                BitstreamWriter &Stream) {
666  const ValueEnumerator::ValueList &Vals = VE.getMDValues();
667  bool StartedMetadataBlock = false;
668  unsigned MDSAbbrev = 0;
669  SmallVector<uint64_t, 64> Record;
670  for (unsigned i = 0, e = Vals.size(); i != e; ++i) {
671
672    if (const MDNode *N = dyn_cast<MDNode>(Vals[i].first)) {
673      if (!N->isFunctionLocal() || !N->getFunction()) {
674        if (!StartedMetadataBlock) {
675          Stream.EnterSubblock(bitc::METADATA_BLOCK_ID, 3);
676          StartedMetadataBlock = true;
677        }
678        WriteMDNode(N, VE, Stream, Record);
679      }
680    } else if (const MDString *MDS = dyn_cast<MDString>(Vals[i].first)) {
681      if (!StartedMetadataBlock)  {
682        Stream.EnterSubblock(bitc::METADATA_BLOCK_ID, 3);
683
684        // Abbrev for METADATA_STRING.
685        BitCodeAbbrev *Abbv = new BitCodeAbbrev();
686        Abbv->Add(BitCodeAbbrevOp(bitc::METADATA_STRING));
687        Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
688        Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 8));
689        MDSAbbrev = Stream.EmitAbbrev(Abbv);
690        StartedMetadataBlock = true;
691      }
692
693      // Code: [strchar x N]
694      Record.append(MDS->begin(), MDS->end());
695
696      // Emit the finished record.
697      Stream.EmitRecord(bitc::METADATA_STRING, Record, MDSAbbrev);
698      Record.clear();
699    }
700  }
701
702  // Write named metadata.
703  for (Module::const_named_metadata_iterator I = M->named_metadata_begin(),
704       E = M->named_metadata_end(); I != E; ++I) {
705    const NamedMDNode *NMD = I;
706    if (!StartedMetadataBlock)  {
707      Stream.EnterSubblock(bitc::METADATA_BLOCK_ID, 3);
708      StartedMetadataBlock = true;
709    }
710
711    // Write name.
712    StringRef Str = NMD->getName();
713    for (unsigned i = 0, e = Str.size(); i != e; ++i)
714      Record.push_back(Str[i]);
715    Stream.EmitRecord(bitc::METADATA_NAME, Record, 0/*TODO*/);
716    Record.clear();
717
718    // Write named metadata operands.
719    for (unsigned i = 0, e = NMD->getNumOperands(); i != e; ++i)
720      Record.push_back(VE.getValueID(NMD->getOperand(i)));
721    Stream.EmitRecord(bitc::METADATA_NAMED_NODE, Record, 0);
722    Record.clear();
723  }
724
725  if (StartedMetadataBlock)
726    Stream.ExitBlock();
727}
728
729static void WriteFunctionLocalMetadata(const Function &F,
730                                       const ValueEnumerator &VE,
731                                       BitstreamWriter &Stream) {
732  bool StartedMetadataBlock = false;
733  SmallVector<uint64_t, 64> Record;
734  const SmallVector<const MDNode *, 8> &Vals = VE.getFunctionLocalMDValues();
735  for (unsigned i = 0, e = Vals.size(); i != e; ++i)
736    if (const MDNode *N = Vals[i])
737      if (N->isFunctionLocal() && N->getFunction() == &F) {
738        if (!StartedMetadataBlock) {
739          Stream.EnterSubblock(bitc::METADATA_BLOCK_ID, 3);
740          StartedMetadataBlock = true;
741        }
742        WriteMDNode(N, VE, Stream, Record);
743      }
744
745  if (StartedMetadataBlock)
746    Stream.ExitBlock();
747}
748
749static void WriteMetadataAttachment(const Function &F,
750                                    const ValueEnumerator &VE,
751                                    BitstreamWriter &Stream) {
752  Stream.EnterSubblock(bitc::METADATA_ATTACHMENT_ID, 3);
753
754  SmallVector<uint64_t, 64> Record;
755
756  // Write metadata attachments
757  // METADATA_ATTACHMENT - [m x [value, [n x [id, mdnode]]]
758  SmallVector<std::pair<unsigned, MDNode*>, 4> MDs;
759
760  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
761    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end();
762         I != E; ++I) {
763      MDs.clear();
764      I->getAllMetadataOtherThanDebugLoc(MDs);
765
766      // If no metadata, ignore instruction.
767      if (MDs.empty()) continue;
768
769      Record.push_back(VE.getInstructionID(I));
770
771      for (unsigned i = 0, e = MDs.size(); i != e; ++i) {
772        Record.push_back(MDs[i].first);
773        Record.push_back(VE.getValueID(MDs[i].second));
774      }
775      Stream.EmitRecord(bitc::METADATA_ATTACHMENT, Record, 0);
776      Record.clear();
777    }
778
779  Stream.ExitBlock();
780}
781
782static void WriteModuleMetadataStore(const Module *M, BitstreamWriter &Stream) {
783  SmallVector<uint64_t, 64> Record;
784
785  // Write metadata kinds
786  // METADATA_KIND - [n x [id, name]]
787  SmallVector<StringRef, 8> Names;
788  M->getMDKindNames(Names);
789
790  if (Names.empty()) return;
791
792  Stream.EnterSubblock(bitc::METADATA_BLOCK_ID, 3);
793
794  for (unsigned MDKindID = 0, e = Names.size(); MDKindID != e; ++MDKindID) {
795    Record.push_back(MDKindID);
796    StringRef KName = Names[MDKindID];
797    Record.append(KName.begin(), KName.end());
798
799    Stream.EmitRecord(bitc::METADATA_KIND, Record, 0);
800    Record.clear();
801  }
802
803  Stream.ExitBlock();
804}
805
806static void emitSignedInt64(SmallVectorImpl<uint64_t> &Vals, uint64_t V) {
807  if ((int64_t)V >= 0)
808    Vals.push_back(V << 1);
809  else
810    Vals.push_back((-V << 1) | 1);
811}
812
813static void EmitAPInt(SmallVectorImpl<uint64_t> &Vals,
814                      unsigned &Code, unsigned &AbbrevToUse, const APInt &Val,
815                      bool EmitSizeForWideNumbers = false
816                      ) {
817  if (Val.getBitWidth() <= 64) {
818    uint64_t V = Val.getSExtValue();
819    emitSignedInt64(Vals, V);
820    Code = bitc::CST_CODE_INTEGER;
821    AbbrevToUse = CONSTANTS_INTEGER_ABBREV;
822  } else {
823    // Wide integers, > 64 bits in size.
824    // We have an arbitrary precision integer value to write whose
825    // bit width is > 64. However, in canonical unsigned integer
826    // format it is likely that the high bits are going to be zero.
827    // So, we only write the number of active words.
828    unsigned NWords = Val.getActiveWords();
829
830    if (EmitSizeForWideNumbers)
831      Vals.push_back(NWords);
832
833    const uint64_t *RawWords = Val.getRawData();
834    for (unsigned i = 0; i != NWords; ++i) {
835      emitSignedInt64(Vals, RawWords[i]);
836    }
837    Code = bitc::CST_CODE_WIDE_INTEGER;
838  }
839}
840
841static void WriteConstants(unsigned FirstVal, unsigned LastVal,
842                           const ValueEnumerator &VE,
843                           BitstreamWriter &Stream, bool isGlobal) {
844  if (FirstVal == LastVal) return;
845
846  Stream.EnterSubblock(bitc::CONSTANTS_BLOCK_ID, 4);
847
848  unsigned AggregateAbbrev = 0;
849  unsigned String8Abbrev = 0;
850  unsigned CString7Abbrev = 0;
851  unsigned CString6Abbrev = 0;
852  // If this is a constant pool for the module, emit module-specific abbrevs.
853  if (isGlobal) {
854    // Abbrev for CST_CODE_AGGREGATE.
855    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
856    Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_AGGREGATE));
857    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
858    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, Log2_32_Ceil(LastVal+1)));
859    AggregateAbbrev = Stream.EmitAbbrev(Abbv);
860
861    // Abbrev for CST_CODE_STRING.
862    Abbv = new BitCodeAbbrev();
863    Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_STRING));
864    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
865    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 8));
866    String8Abbrev = Stream.EmitAbbrev(Abbv);
867    // Abbrev for CST_CODE_CSTRING.
868    Abbv = new BitCodeAbbrev();
869    Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_CSTRING));
870    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
871    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 7));
872    CString7Abbrev = Stream.EmitAbbrev(Abbv);
873    // Abbrev for CST_CODE_CSTRING.
874    Abbv = new BitCodeAbbrev();
875    Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_CSTRING));
876    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
877    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Char6));
878    CString6Abbrev = Stream.EmitAbbrev(Abbv);
879  }
880
881  SmallVector<uint64_t, 64> Record;
882
883  const ValueEnumerator::ValueList &Vals = VE.getValues();
884  Type *LastTy = 0;
885  for (unsigned i = FirstVal; i != LastVal; ++i) {
886    const Value *V = Vals[i].first;
887    // If we need to switch types, do so now.
888    if (V->getType() != LastTy) {
889      LastTy = V->getType();
890      Record.push_back(VE.getTypeID(LastTy));
891      Stream.EmitRecord(bitc::CST_CODE_SETTYPE, Record,
892                        CONSTANTS_SETTYPE_ABBREV);
893      Record.clear();
894    }
895
896    if (const InlineAsm *IA = dyn_cast<InlineAsm>(V)) {
897      Record.push_back(unsigned(IA->hasSideEffects()) |
898                       unsigned(IA->isAlignStack()) << 1 |
899                       unsigned(IA->getDialect()&1) << 2);
900
901      // Add the asm string.
902      const std::string &AsmStr = IA->getAsmString();
903      Record.push_back(AsmStr.size());
904      for (unsigned i = 0, e = AsmStr.size(); i != e; ++i)
905        Record.push_back(AsmStr[i]);
906
907      // Add the constraint string.
908      const std::string &ConstraintStr = IA->getConstraintString();
909      Record.push_back(ConstraintStr.size());
910      for (unsigned i = 0, e = ConstraintStr.size(); i != e; ++i)
911        Record.push_back(ConstraintStr[i]);
912      Stream.EmitRecord(bitc::CST_CODE_INLINEASM, Record);
913      Record.clear();
914      continue;
915    }
916    const Constant *C = cast<Constant>(V);
917    unsigned Code = -1U;
918    unsigned AbbrevToUse = 0;
919    if (C->isNullValue()) {
920      Code = bitc::CST_CODE_NULL;
921    } else if (isa<UndefValue>(C)) {
922      Code = bitc::CST_CODE_UNDEF;
923    } else if (const ConstantInt *IV = dyn_cast<ConstantInt>(C)) {
924      EmitAPInt(Record, Code, AbbrevToUse, IV->getValue());
925    } else if (const ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
926      Code = bitc::CST_CODE_FLOAT;
927      Type *Ty = CFP->getType();
928      if (Ty->isHalfTy() || Ty->isFloatTy() || Ty->isDoubleTy()) {
929        Record.push_back(CFP->getValueAPF().bitcastToAPInt().getZExtValue());
930      } else if (Ty->isX86_FP80Ty()) {
931        // api needed to prevent premature destruction
932        // bits are not in the same order as a normal i80 APInt, compensate.
933        APInt api = CFP->getValueAPF().bitcastToAPInt();
934        const uint64_t *p = api.getRawData();
935        Record.push_back((p[1] << 48) | (p[0] >> 16));
936        Record.push_back(p[0] & 0xffffLL);
937      } else if (Ty->isFP128Ty() || Ty->isPPC_FP128Ty()) {
938        APInt api = CFP->getValueAPF().bitcastToAPInt();
939        const uint64_t *p = api.getRawData();
940        Record.push_back(p[0]);
941        Record.push_back(p[1]);
942      } else {
943        assert (0 && "Unknown FP type!");
944      }
945    } else if (isa<ConstantDataSequential>(C) &&
946               cast<ConstantDataSequential>(C)->isString()) {
947      const ConstantDataSequential *Str = cast<ConstantDataSequential>(C);
948      // Emit constant strings specially.
949      unsigned NumElts = Str->getNumElements();
950      // If this is a null-terminated string, use the denser CSTRING encoding.
951      if (Str->isCString()) {
952        Code = bitc::CST_CODE_CSTRING;
953        --NumElts;  // Don't encode the null, which isn't allowed by char6.
954      } else {
955        Code = bitc::CST_CODE_STRING;
956        AbbrevToUse = String8Abbrev;
957      }
958      bool isCStr7 = Code == bitc::CST_CODE_CSTRING;
959      bool isCStrChar6 = Code == bitc::CST_CODE_CSTRING;
960      for (unsigned i = 0; i != NumElts; ++i) {
961        unsigned char V = Str->getElementAsInteger(i);
962        Record.push_back(V);
963        isCStr7 &= (V & 128) == 0;
964        if (isCStrChar6)
965          isCStrChar6 = BitCodeAbbrevOp::isChar6(V);
966      }
967
968      if (isCStrChar6)
969        AbbrevToUse = CString6Abbrev;
970      else if (isCStr7)
971        AbbrevToUse = CString7Abbrev;
972    } else if (const ConstantDataSequential *CDS =
973                  dyn_cast<ConstantDataSequential>(C)) {
974      Code = bitc::CST_CODE_DATA;
975      Type *EltTy = CDS->getType()->getElementType();
976      if (isa<IntegerType>(EltTy)) {
977        for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i)
978          Record.push_back(CDS->getElementAsInteger(i));
979      } else if (EltTy->isFloatTy()) {
980        for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) {
981          union { float F; uint32_t I; };
982          F = CDS->getElementAsFloat(i);
983          Record.push_back(I);
984        }
985      } else {
986        assert(EltTy->isDoubleTy() && "Unknown ConstantData element type");
987        for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i) {
988          union { double F; uint64_t I; };
989          F = CDS->getElementAsDouble(i);
990          Record.push_back(I);
991        }
992      }
993    } else if (isa<ConstantArray>(C) || isa<ConstantStruct>(C) ||
994               isa<ConstantVector>(C)) {
995      Code = bitc::CST_CODE_AGGREGATE;
996      for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i)
997        Record.push_back(VE.getValueID(C->getOperand(i)));
998      AbbrevToUse = AggregateAbbrev;
999    } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
1000      switch (CE->getOpcode()) {
1001      default:
1002        if (Instruction::isCast(CE->getOpcode())) {
1003          Code = bitc::CST_CODE_CE_CAST;
1004          Record.push_back(GetEncodedCastOpcode(CE->getOpcode()));
1005          Record.push_back(VE.getTypeID(C->getOperand(0)->getType()));
1006          Record.push_back(VE.getValueID(C->getOperand(0)));
1007          AbbrevToUse = CONSTANTS_CE_CAST_Abbrev;
1008        } else {
1009          assert(CE->getNumOperands() == 2 && "Unknown constant expr!");
1010          Code = bitc::CST_CODE_CE_BINOP;
1011          Record.push_back(GetEncodedBinaryOpcode(CE->getOpcode()));
1012          Record.push_back(VE.getValueID(C->getOperand(0)));
1013          Record.push_back(VE.getValueID(C->getOperand(1)));
1014          uint64_t Flags = GetOptimizationFlags(CE);
1015          if (Flags != 0)
1016            Record.push_back(Flags);
1017        }
1018        break;
1019      case Instruction::GetElementPtr:
1020        Code = bitc::CST_CODE_CE_GEP;
1021        if (cast<GEPOperator>(C)->isInBounds())
1022          Code = bitc::CST_CODE_CE_INBOUNDS_GEP;
1023        for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i) {
1024          Record.push_back(VE.getTypeID(C->getOperand(i)->getType()));
1025          Record.push_back(VE.getValueID(C->getOperand(i)));
1026        }
1027        break;
1028      case Instruction::Select:
1029        Code = bitc::CST_CODE_CE_SELECT;
1030        Record.push_back(VE.getValueID(C->getOperand(0)));
1031        Record.push_back(VE.getValueID(C->getOperand(1)));
1032        Record.push_back(VE.getValueID(C->getOperand(2)));
1033        break;
1034      case Instruction::ExtractElement:
1035        Code = bitc::CST_CODE_CE_EXTRACTELT;
1036        Record.push_back(VE.getTypeID(C->getOperand(0)->getType()));
1037        Record.push_back(VE.getValueID(C->getOperand(0)));
1038        Record.push_back(VE.getValueID(C->getOperand(1)));
1039        break;
1040      case Instruction::InsertElement:
1041        Code = bitc::CST_CODE_CE_INSERTELT;
1042        Record.push_back(VE.getValueID(C->getOperand(0)));
1043        Record.push_back(VE.getValueID(C->getOperand(1)));
1044        Record.push_back(VE.getValueID(C->getOperand(2)));
1045        break;
1046      case Instruction::ShuffleVector:
1047        // If the return type and argument types are the same, this is a
1048        // standard shufflevector instruction.  If the types are different,
1049        // then the shuffle is widening or truncating the input vectors, and
1050        // the argument type must also be encoded.
1051        if (C->getType() == C->getOperand(0)->getType()) {
1052          Code = bitc::CST_CODE_CE_SHUFFLEVEC;
1053        } else {
1054          Code = bitc::CST_CODE_CE_SHUFVEC_EX;
1055          Record.push_back(VE.getTypeID(C->getOperand(0)->getType()));
1056        }
1057        Record.push_back(VE.getValueID(C->getOperand(0)));
1058        Record.push_back(VE.getValueID(C->getOperand(1)));
1059        Record.push_back(VE.getValueID(C->getOperand(2)));
1060        break;
1061      case Instruction::ICmp:
1062      case Instruction::FCmp:
1063        Code = bitc::CST_CODE_CE_CMP;
1064        Record.push_back(VE.getTypeID(C->getOperand(0)->getType()));
1065        Record.push_back(VE.getValueID(C->getOperand(0)));
1066        Record.push_back(VE.getValueID(C->getOperand(1)));
1067        Record.push_back(CE->getPredicate());
1068        break;
1069      }
1070    } else if (const BlockAddress *BA = dyn_cast<BlockAddress>(C)) {
1071      Code = bitc::CST_CODE_BLOCKADDRESS;
1072      Record.push_back(VE.getTypeID(BA->getFunction()->getType()));
1073      Record.push_back(VE.getValueID(BA->getFunction()));
1074      Record.push_back(VE.getGlobalBasicBlockID(BA->getBasicBlock()));
1075    } else {
1076#ifndef NDEBUG
1077      C->dump();
1078#endif
1079      llvm_unreachable("Unknown constant!");
1080    }
1081    Stream.EmitRecord(Code, Record, AbbrevToUse);
1082    Record.clear();
1083  }
1084
1085  Stream.ExitBlock();
1086}
1087
1088static void WriteModuleConstants(const ValueEnumerator &VE,
1089                                 BitstreamWriter &Stream) {
1090  const ValueEnumerator::ValueList &Vals = VE.getValues();
1091
1092  // Find the first constant to emit, which is the first non-globalvalue value.
1093  // We know globalvalues have been emitted by WriteModuleInfo.
1094  for (unsigned i = 0, e = Vals.size(); i != e; ++i) {
1095    if (!isa<GlobalValue>(Vals[i].first)) {
1096      WriteConstants(i, Vals.size(), VE, Stream, true);
1097      return;
1098    }
1099  }
1100}
1101
1102/// PushValueAndType - The file has to encode both the value and type id for
1103/// many values, because we need to know what type to create for forward
1104/// references.  However, most operands are not forward references, so this type
1105/// field is not needed.
1106///
1107/// This function adds V's value ID to Vals.  If the value ID is higher than the
1108/// instruction ID, then it is a forward reference, and it also includes the
1109/// type ID.  The value ID that is written is encoded relative to the InstID.
1110static bool PushValueAndType(const Value *V, unsigned InstID,
1111                             SmallVector<unsigned, 64> &Vals,
1112                             ValueEnumerator &VE) {
1113  unsigned ValID = VE.getValueID(V);
1114  // Make encoding relative to the InstID.
1115  Vals.push_back(InstID - ValID);
1116  if (ValID >= InstID) {
1117    Vals.push_back(VE.getTypeID(V->getType()));
1118    return true;
1119  }
1120  return false;
1121}
1122
1123/// pushValue - Like PushValueAndType, but where the type of the value is
1124/// omitted (perhaps it was already encoded in an earlier operand).
1125static void pushValue(const Value *V, unsigned InstID,
1126                      SmallVector<unsigned, 64> &Vals,
1127                      ValueEnumerator &VE) {
1128  unsigned ValID = VE.getValueID(V);
1129  Vals.push_back(InstID - ValID);
1130}
1131
1132static void pushValue64(const Value *V, unsigned InstID,
1133                        SmallVector<uint64_t, 128> &Vals,
1134                        ValueEnumerator &VE) {
1135  uint64_t ValID = VE.getValueID(V);
1136  Vals.push_back(InstID - ValID);
1137}
1138
1139static void pushValueSigned(const Value *V, unsigned InstID,
1140                            SmallVector<uint64_t, 128> &Vals,
1141                            ValueEnumerator &VE) {
1142  unsigned ValID = VE.getValueID(V);
1143  int64_t diff = ((int32_t)InstID - (int32_t)ValID);
1144  emitSignedInt64(Vals, diff);
1145}
1146
1147/// WriteInstruction - Emit an instruction to the specified stream.
1148static void WriteInstruction(const Instruction &I, unsigned InstID,
1149                             ValueEnumerator &VE, BitstreamWriter &Stream,
1150                             SmallVector<unsigned, 64> &Vals) {
1151  unsigned Code = 0;
1152  unsigned AbbrevToUse = 0;
1153  VE.setInstructionID(&I);
1154  switch (I.getOpcode()) {
1155  default:
1156    if (Instruction::isCast(I.getOpcode())) {
1157      Code = bitc::FUNC_CODE_INST_CAST;
1158      if (!PushValueAndType(I.getOperand(0), InstID, Vals, VE))
1159        AbbrevToUse = FUNCTION_INST_CAST_ABBREV;
1160      Vals.push_back(VE.getTypeID(I.getType()));
1161      Vals.push_back(GetEncodedCastOpcode(I.getOpcode()));
1162    } else {
1163      assert(isa<BinaryOperator>(I) && "Unknown instruction!");
1164      Code = bitc::FUNC_CODE_INST_BINOP;
1165      if (!PushValueAndType(I.getOperand(0), InstID, Vals, VE))
1166        AbbrevToUse = FUNCTION_INST_BINOP_ABBREV;
1167      pushValue(I.getOperand(1), InstID, Vals, VE);
1168      Vals.push_back(GetEncodedBinaryOpcode(I.getOpcode()));
1169      uint64_t Flags = GetOptimizationFlags(&I);
1170      if (Flags != 0) {
1171        if (AbbrevToUse == FUNCTION_INST_BINOP_ABBREV)
1172          AbbrevToUse = FUNCTION_INST_BINOP_FLAGS_ABBREV;
1173        Vals.push_back(Flags);
1174      }
1175    }
1176    break;
1177
1178  case Instruction::GetElementPtr:
1179    Code = bitc::FUNC_CODE_INST_GEP;
1180    if (cast<GEPOperator>(&I)->isInBounds())
1181      Code = bitc::FUNC_CODE_INST_INBOUNDS_GEP;
1182    for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
1183      PushValueAndType(I.getOperand(i), InstID, Vals, VE);
1184    break;
1185  case Instruction::ExtractValue: {
1186    Code = bitc::FUNC_CODE_INST_EXTRACTVAL;
1187    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
1188    const ExtractValueInst *EVI = cast<ExtractValueInst>(&I);
1189    for (const unsigned *i = EVI->idx_begin(), *e = EVI->idx_end(); i != e; ++i)
1190      Vals.push_back(*i);
1191    break;
1192  }
1193  case Instruction::InsertValue: {
1194    Code = bitc::FUNC_CODE_INST_INSERTVAL;
1195    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
1196    PushValueAndType(I.getOperand(1), InstID, Vals, VE);
1197    const InsertValueInst *IVI = cast<InsertValueInst>(&I);
1198    for (const unsigned *i = IVI->idx_begin(), *e = IVI->idx_end(); i != e; ++i)
1199      Vals.push_back(*i);
1200    break;
1201  }
1202  case Instruction::Select:
1203    Code = bitc::FUNC_CODE_INST_VSELECT;
1204    PushValueAndType(I.getOperand(1), InstID, Vals, VE);
1205    pushValue(I.getOperand(2), InstID, Vals, VE);
1206    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
1207    break;
1208  case Instruction::ExtractElement:
1209    Code = bitc::FUNC_CODE_INST_EXTRACTELT;
1210    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
1211    pushValue(I.getOperand(1), InstID, Vals, VE);
1212    break;
1213  case Instruction::InsertElement:
1214    Code = bitc::FUNC_CODE_INST_INSERTELT;
1215    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
1216    pushValue(I.getOperand(1), InstID, Vals, VE);
1217    pushValue(I.getOperand(2), InstID, Vals, VE);
1218    break;
1219  case Instruction::ShuffleVector:
1220    Code = bitc::FUNC_CODE_INST_SHUFFLEVEC;
1221    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
1222    pushValue(I.getOperand(1), InstID, Vals, VE);
1223    pushValue(I.getOperand(2), InstID, Vals, VE);
1224    break;
1225  case Instruction::ICmp:
1226  case Instruction::FCmp:
1227    // compare returning Int1Ty or vector of Int1Ty
1228    Code = bitc::FUNC_CODE_INST_CMP2;
1229    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
1230    pushValue(I.getOperand(1), InstID, Vals, VE);
1231    Vals.push_back(cast<CmpInst>(I).getPredicate());
1232    break;
1233
1234  case Instruction::Ret:
1235    {
1236      Code = bitc::FUNC_CODE_INST_RET;
1237      unsigned NumOperands = I.getNumOperands();
1238      if (NumOperands == 0)
1239        AbbrevToUse = FUNCTION_INST_RET_VOID_ABBREV;
1240      else if (NumOperands == 1) {
1241        if (!PushValueAndType(I.getOperand(0), InstID, Vals, VE))
1242          AbbrevToUse = FUNCTION_INST_RET_VAL_ABBREV;
1243      } else {
1244        for (unsigned i = 0, e = NumOperands; i != e; ++i)
1245          PushValueAndType(I.getOperand(i), InstID, Vals, VE);
1246      }
1247    }
1248    break;
1249  case Instruction::Br:
1250    {
1251      Code = bitc::FUNC_CODE_INST_BR;
1252      const BranchInst &II = cast<BranchInst>(I);
1253      Vals.push_back(VE.getValueID(II.getSuccessor(0)));
1254      if (II.isConditional()) {
1255        Vals.push_back(VE.getValueID(II.getSuccessor(1)));
1256        pushValue(II.getCondition(), InstID, Vals, VE);
1257      }
1258    }
1259    break;
1260  case Instruction::Switch:
1261    {
1262      // Redefine Vals, since here we need to use 64 bit values
1263      // explicitly to store large APInt numbers.
1264      SmallVector<uint64_t, 128> Vals64;
1265
1266      Code = bitc::FUNC_CODE_INST_SWITCH;
1267      const SwitchInst &SI = cast<SwitchInst>(I);
1268
1269      uint32_t SwitchRecordHeader = SI.hash() | (SWITCH_INST_MAGIC << 16);
1270      Vals64.push_back(SwitchRecordHeader);
1271
1272      Vals64.push_back(VE.getTypeID(SI.getCondition()->getType()));
1273      pushValue64(SI.getCondition(), InstID, Vals64, VE);
1274      Vals64.push_back(VE.getValueID(SI.getDefaultDest()));
1275      Vals64.push_back(SI.getNumCases());
1276      for (SwitchInst::ConstCaseIt i = SI.case_begin(), e = SI.case_end();
1277           i != e; ++i) {
1278        const IntegersSubset& CaseRanges = i.getCaseValueEx();
1279        unsigned Code, Abbrev; // will unused.
1280
1281        if (CaseRanges.isSingleNumber()) {
1282          Vals64.push_back(1/*NumItems = 1*/);
1283          Vals64.push_back(true/*IsSingleNumber = true*/);
1284          EmitAPInt(Vals64, Code, Abbrev, CaseRanges.getSingleNumber(0), true);
1285        } else {
1286
1287          Vals64.push_back(CaseRanges.getNumItems());
1288
1289          if (CaseRanges.isSingleNumbersOnly()) {
1290            for (unsigned ri = 0, rn = CaseRanges.getNumItems();
1291                 ri != rn; ++ri) {
1292
1293              Vals64.push_back(true/*IsSingleNumber = true*/);
1294
1295              EmitAPInt(Vals64, Code, Abbrev,
1296                        CaseRanges.getSingleNumber(ri), true);
1297            }
1298          } else
1299            for (unsigned ri = 0, rn = CaseRanges.getNumItems();
1300                 ri != rn; ++ri) {
1301              IntegersSubset::Range r = CaseRanges.getItem(ri);
1302              bool IsSingleNumber = CaseRanges.isSingleNumber(ri);
1303
1304              Vals64.push_back(IsSingleNumber);
1305
1306              EmitAPInt(Vals64, Code, Abbrev, r.getLow(), true);
1307              if (!IsSingleNumber)
1308                EmitAPInt(Vals64, Code, Abbrev, r.getHigh(), true);
1309            }
1310        }
1311        Vals64.push_back(VE.getValueID(i.getCaseSuccessor()));
1312      }
1313
1314      Stream.EmitRecord(Code, Vals64, AbbrevToUse);
1315
1316      // Also do expected action - clear external Vals collection:
1317      Vals.clear();
1318      return;
1319    }
1320    break;
1321  case Instruction::IndirectBr:
1322    Code = bitc::FUNC_CODE_INST_INDIRECTBR;
1323    Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));
1324    // Encode the address operand as relative, but not the basic blocks.
1325    pushValue(I.getOperand(0), InstID, Vals, VE);
1326    for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i)
1327      Vals.push_back(VE.getValueID(I.getOperand(i)));
1328    break;
1329
1330  case Instruction::Invoke: {
1331    const InvokeInst *II = cast<InvokeInst>(&I);
1332    const Value *Callee(II->getCalledValue());
1333    PointerType *PTy = cast<PointerType>(Callee->getType());
1334    FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
1335    Code = bitc::FUNC_CODE_INST_INVOKE;
1336
1337    Vals.push_back(VE.getAttributeID(II->getAttributes()));
1338    Vals.push_back(II->getCallingConv());
1339    Vals.push_back(VE.getValueID(II->getNormalDest()));
1340    Vals.push_back(VE.getValueID(II->getUnwindDest()));
1341    PushValueAndType(Callee, InstID, Vals, VE);
1342
1343    // Emit value #'s for the fixed parameters.
1344    for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
1345      pushValue(I.getOperand(i), InstID, Vals, VE);  // fixed param.
1346
1347    // Emit type/value pairs for varargs params.
1348    if (FTy->isVarArg()) {
1349      for (unsigned i = FTy->getNumParams(), e = I.getNumOperands()-3;
1350           i != e; ++i)
1351        PushValueAndType(I.getOperand(i), InstID, Vals, VE); // vararg
1352    }
1353    break;
1354  }
1355  case Instruction::Resume:
1356    Code = bitc::FUNC_CODE_INST_RESUME;
1357    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
1358    break;
1359  case Instruction::Unreachable:
1360    Code = bitc::FUNC_CODE_INST_UNREACHABLE;
1361    AbbrevToUse = FUNCTION_INST_UNREACHABLE_ABBREV;
1362    break;
1363
1364  case Instruction::PHI: {
1365    const PHINode &PN = cast<PHINode>(I);
1366    Code = bitc::FUNC_CODE_INST_PHI;
1367    // With the newer instruction encoding, forward references could give
1368    // negative valued IDs.  This is most common for PHIs, so we use
1369    // signed VBRs.
1370    SmallVector<uint64_t, 128> Vals64;
1371    Vals64.push_back(VE.getTypeID(PN.getType()));
1372    for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
1373      pushValueSigned(PN.getIncomingValue(i), InstID, Vals64, VE);
1374      Vals64.push_back(VE.getValueID(PN.getIncomingBlock(i)));
1375    }
1376    // Emit a Vals64 vector and exit.
1377    Stream.EmitRecord(Code, Vals64, AbbrevToUse);
1378    Vals64.clear();
1379    return;
1380  }
1381
1382  case Instruction::LandingPad: {
1383    const LandingPadInst &LP = cast<LandingPadInst>(I);
1384    Code = bitc::FUNC_CODE_INST_LANDINGPAD;
1385    Vals.push_back(VE.getTypeID(LP.getType()));
1386    PushValueAndType(LP.getPersonalityFn(), InstID, Vals, VE);
1387    Vals.push_back(LP.isCleanup());
1388    Vals.push_back(LP.getNumClauses());
1389    for (unsigned I = 0, E = LP.getNumClauses(); I != E; ++I) {
1390      if (LP.isCatch(I))
1391        Vals.push_back(LandingPadInst::Catch);
1392      else
1393        Vals.push_back(LandingPadInst::Filter);
1394      PushValueAndType(LP.getClause(I), InstID, Vals, VE);
1395    }
1396    break;
1397  }
1398
1399  case Instruction::Alloca:
1400    Code = bitc::FUNC_CODE_INST_ALLOCA;
1401    Vals.push_back(VE.getTypeID(I.getType()));
1402    Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));
1403    Vals.push_back(VE.getValueID(I.getOperand(0))); // size.
1404    Vals.push_back(Log2_32(cast<AllocaInst>(I).getAlignment())+1);
1405    break;
1406
1407  case Instruction::Load:
1408    if (cast<LoadInst>(I).isAtomic()) {
1409      Code = bitc::FUNC_CODE_INST_LOADATOMIC;
1410      PushValueAndType(I.getOperand(0), InstID, Vals, VE);
1411    } else {
1412      Code = bitc::FUNC_CODE_INST_LOAD;
1413      if (!PushValueAndType(I.getOperand(0), InstID, Vals, VE))  // ptr
1414        AbbrevToUse = FUNCTION_INST_LOAD_ABBREV;
1415    }
1416    Vals.push_back(Log2_32(cast<LoadInst>(I).getAlignment())+1);
1417    Vals.push_back(cast<LoadInst>(I).isVolatile());
1418    if (cast<LoadInst>(I).isAtomic()) {
1419      Vals.push_back(GetEncodedOrdering(cast<LoadInst>(I).getOrdering()));
1420      Vals.push_back(GetEncodedSynchScope(cast<LoadInst>(I).getSynchScope()));
1421    }
1422    break;
1423  case Instruction::Store:
1424    if (cast<StoreInst>(I).isAtomic())
1425      Code = bitc::FUNC_CODE_INST_STOREATOMIC;
1426    else
1427      Code = bitc::FUNC_CODE_INST_STORE;
1428    PushValueAndType(I.getOperand(1), InstID, Vals, VE);  // ptrty + ptr
1429    pushValue(I.getOperand(0), InstID, Vals, VE);         // val.
1430    Vals.push_back(Log2_32(cast<StoreInst>(I).getAlignment())+1);
1431    Vals.push_back(cast<StoreInst>(I).isVolatile());
1432    if (cast<StoreInst>(I).isAtomic()) {
1433      Vals.push_back(GetEncodedOrdering(cast<StoreInst>(I).getOrdering()));
1434      Vals.push_back(GetEncodedSynchScope(cast<StoreInst>(I).getSynchScope()));
1435    }
1436    break;
1437  case Instruction::AtomicCmpXchg:
1438    Code = bitc::FUNC_CODE_INST_CMPXCHG;
1439    PushValueAndType(I.getOperand(0), InstID, Vals, VE);  // ptrty + ptr
1440    pushValue(I.getOperand(1), InstID, Vals, VE);         // cmp.
1441    pushValue(I.getOperand(2), InstID, Vals, VE);         // newval.
1442    Vals.push_back(cast<AtomicCmpXchgInst>(I).isVolatile());
1443    Vals.push_back(GetEncodedOrdering(
1444                     cast<AtomicCmpXchgInst>(I).getOrdering()));
1445    Vals.push_back(GetEncodedSynchScope(
1446                     cast<AtomicCmpXchgInst>(I).getSynchScope()));
1447    break;
1448  case Instruction::AtomicRMW:
1449    Code = bitc::FUNC_CODE_INST_ATOMICRMW;
1450    PushValueAndType(I.getOperand(0), InstID, Vals, VE);  // ptrty + ptr
1451    pushValue(I.getOperand(1), InstID, Vals, VE);         // val.
1452    Vals.push_back(GetEncodedRMWOperation(
1453                     cast<AtomicRMWInst>(I).getOperation()));
1454    Vals.push_back(cast<AtomicRMWInst>(I).isVolatile());
1455    Vals.push_back(GetEncodedOrdering(cast<AtomicRMWInst>(I).getOrdering()));
1456    Vals.push_back(GetEncodedSynchScope(
1457                     cast<AtomicRMWInst>(I).getSynchScope()));
1458    break;
1459  case Instruction::Fence:
1460    Code = bitc::FUNC_CODE_INST_FENCE;
1461    Vals.push_back(GetEncodedOrdering(cast<FenceInst>(I).getOrdering()));
1462    Vals.push_back(GetEncodedSynchScope(cast<FenceInst>(I).getSynchScope()));
1463    break;
1464  case Instruction::Call: {
1465    const CallInst &CI = cast<CallInst>(I);
1466    PointerType *PTy = cast<PointerType>(CI.getCalledValue()->getType());
1467    FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
1468
1469    Code = bitc::FUNC_CODE_INST_CALL;
1470
1471    Vals.push_back(VE.getAttributeID(CI.getAttributes()));
1472    Vals.push_back((CI.getCallingConv() << 1) | unsigned(CI.isTailCall()));
1473    PushValueAndType(CI.getCalledValue(), InstID, Vals, VE);  // Callee
1474
1475    // Emit value #'s for the fixed parameters.
1476    for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i) {
1477      // Check for labels (can happen with asm labels).
1478      if (FTy->getParamType(i)->isLabelTy())
1479        Vals.push_back(VE.getValueID(CI.getArgOperand(i)));
1480      else
1481        pushValue(CI.getArgOperand(i), InstID, Vals, VE);  // fixed param.
1482    }
1483
1484    // Emit type/value pairs for varargs params.
1485    if (FTy->isVarArg()) {
1486      for (unsigned i = FTy->getNumParams(), e = CI.getNumArgOperands();
1487           i != e; ++i)
1488        PushValueAndType(CI.getArgOperand(i), InstID, Vals, VE);  // varargs
1489    }
1490    break;
1491  }
1492  case Instruction::VAArg:
1493    Code = bitc::FUNC_CODE_INST_VAARG;
1494    Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));   // valistty
1495    pushValue(I.getOperand(0), InstID, Vals, VE); // valist.
1496    Vals.push_back(VE.getTypeID(I.getType())); // restype.
1497    break;
1498  }
1499
1500  Stream.EmitRecord(Code, Vals, AbbrevToUse);
1501  Vals.clear();
1502}
1503
1504// Emit names for globals/functions etc.
1505static void WriteValueSymbolTable(const ValueSymbolTable &VST,
1506                                  const ValueEnumerator &VE,
1507                                  BitstreamWriter &Stream) {
1508  if (VST.empty()) return;
1509  Stream.EnterSubblock(bitc::VALUE_SYMTAB_BLOCK_ID, 4);
1510
1511  // FIXME: Set up the abbrev, we know how many values there are!
1512  // FIXME: We know if the type names can use 7-bit ascii.
1513  SmallVector<unsigned, 64> NameVals;
1514
1515  for (ValueSymbolTable::const_iterator SI = VST.begin(), SE = VST.end();
1516       SI != SE; ++SI) {
1517
1518    const ValueName &Name = *SI;
1519
1520    // Figure out the encoding to use for the name.
1521    bool is7Bit = true;
1522    bool isChar6 = true;
1523    for (const char *C = Name.getKeyData(), *E = C+Name.getKeyLength();
1524         C != E; ++C) {
1525      if (isChar6)
1526        isChar6 = BitCodeAbbrevOp::isChar6(*C);
1527      if ((unsigned char)*C & 128) {
1528        is7Bit = false;
1529        break;  // don't bother scanning the rest.
1530      }
1531    }
1532
1533    unsigned AbbrevToUse = VST_ENTRY_8_ABBREV;
1534
1535    // VST_ENTRY:   [valueid, namechar x N]
1536    // VST_BBENTRY: [bbid, namechar x N]
1537    unsigned Code;
1538    if (isa<BasicBlock>(SI->getValue())) {
1539      Code = bitc::VST_CODE_BBENTRY;
1540      if (isChar6)
1541        AbbrevToUse = VST_BBENTRY_6_ABBREV;
1542    } else {
1543      Code = bitc::VST_CODE_ENTRY;
1544      if (isChar6)
1545        AbbrevToUse = VST_ENTRY_6_ABBREV;
1546      else if (is7Bit)
1547        AbbrevToUse = VST_ENTRY_7_ABBREV;
1548    }
1549
1550    NameVals.push_back(VE.getValueID(SI->getValue()));
1551    for (const char *P = Name.getKeyData(),
1552         *E = Name.getKeyData()+Name.getKeyLength(); P != E; ++P)
1553      NameVals.push_back((unsigned char)*P);
1554
1555    // Emit the finished record.
1556    Stream.EmitRecord(Code, NameVals, AbbrevToUse);
1557    NameVals.clear();
1558  }
1559  Stream.ExitBlock();
1560}
1561
1562/// WriteFunction - Emit a function body to the module stream.
1563static void WriteFunction(const Function &F, ValueEnumerator &VE,
1564                          BitstreamWriter &Stream) {
1565  Stream.EnterSubblock(bitc::FUNCTION_BLOCK_ID, 4);
1566  VE.incorporateFunction(F);
1567
1568  SmallVector<unsigned, 64> Vals;
1569
1570  // Emit the number of basic blocks, so the reader can create them ahead of
1571  // time.
1572  Vals.push_back(VE.getBasicBlocks().size());
1573  Stream.EmitRecord(bitc::FUNC_CODE_DECLAREBLOCKS, Vals);
1574  Vals.clear();
1575
1576  // If there are function-local constants, emit them now.
1577  unsigned CstStart, CstEnd;
1578  VE.getFunctionConstantRange(CstStart, CstEnd);
1579  WriteConstants(CstStart, CstEnd, VE, Stream, false);
1580
1581  // If there is function-local metadata, emit it now.
1582  WriteFunctionLocalMetadata(F, VE, Stream);
1583
1584  // Keep a running idea of what the instruction ID is.
1585  unsigned InstID = CstEnd;
1586
1587  bool NeedsMetadataAttachment = false;
1588
1589  DebugLoc LastDL;
1590
1591  // Finally, emit all the instructions, in order.
1592  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
1593    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end();
1594         I != E; ++I) {
1595      WriteInstruction(*I, InstID, VE, Stream, Vals);
1596
1597      if (!I->getType()->isVoidTy())
1598        ++InstID;
1599
1600      // If the instruction has metadata, write a metadata attachment later.
1601      NeedsMetadataAttachment |= I->hasMetadataOtherThanDebugLoc();
1602
1603      // If the instruction has a debug location, emit it.
1604      DebugLoc DL = I->getDebugLoc();
1605      if (DL.isUnknown()) {
1606        // nothing todo.
1607      } else if (DL == LastDL) {
1608        // Just repeat the same debug loc as last time.
1609        Stream.EmitRecord(bitc::FUNC_CODE_DEBUG_LOC_AGAIN, Vals);
1610      } else {
1611        MDNode *Scope, *IA;
1612        DL.getScopeAndInlinedAt(Scope, IA, I->getContext());
1613
1614        Vals.push_back(DL.getLine());
1615        Vals.push_back(DL.getCol());
1616        Vals.push_back(Scope ? VE.getValueID(Scope)+1 : 0);
1617        Vals.push_back(IA ? VE.getValueID(IA)+1 : 0);
1618        Stream.EmitRecord(bitc::FUNC_CODE_DEBUG_LOC, Vals);
1619        Vals.clear();
1620
1621        LastDL = DL;
1622      }
1623    }
1624
1625  // Emit names for all the instructions etc.
1626  WriteValueSymbolTable(F.getValueSymbolTable(), VE, Stream);
1627
1628  if (NeedsMetadataAttachment)
1629    WriteMetadataAttachment(F, VE, Stream);
1630  VE.purgeFunction();
1631  Stream.ExitBlock();
1632}
1633
1634// Emit blockinfo, which defines the standard abbreviations etc.
1635static void WriteBlockInfo(const ValueEnumerator &VE, BitstreamWriter &Stream) {
1636  // We only want to emit block info records for blocks that have multiple
1637  // instances: CONSTANTS_BLOCK, FUNCTION_BLOCK and VALUE_SYMTAB_BLOCK.
1638  // Other blocks can define their abbrevs inline.
1639  Stream.EnterBlockInfoBlock(2);
1640
1641  { // 8-bit fixed-width VST_ENTRY/VST_BBENTRY strings.
1642    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1643    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 3));
1644    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
1645    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
1646    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 8));
1647    if (Stream.EmitBlockInfoAbbrev(bitc::VALUE_SYMTAB_BLOCK_ID,
1648                                   Abbv) != VST_ENTRY_8_ABBREV)
1649      llvm_unreachable("Unexpected abbrev ordering!");
1650  }
1651
1652  { // 7-bit fixed width VST_ENTRY strings.
1653    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1654    Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_ENTRY));
1655    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
1656    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
1657    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 7));
1658    if (Stream.EmitBlockInfoAbbrev(bitc::VALUE_SYMTAB_BLOCK_ID,
1659                                   Abbv) != VST_ENTRY_7_ABBREV)
1660      llvm_unreachable("Unexpected abbrev ordering!");
1661  }
1662  { // 6-bit char6 VST_ENTRY strings.
1663    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1664    Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_ENTRY));
1665    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
1666    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
1667    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Char6));
1668    if (Stream.EmitBlockInfoAbbrev(bitc::VALUE_SYMTAB_BLOCK_ID,
1669                                   Abbv) != VST_ENTRY_6_ABBREV)
1670      llvm_unreachable("Unexpected abbrev ordering!");
1671  }
1672  { // 6-bit char6 VST_BBENTRY strings.
1673    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1674    Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_BBENTRY));
1675    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
1676    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
1677    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Char6));
1678    if (Stream.EmitBlockInfoAbbrev(bitc::VALUE_SYMTAB_BLOCK_ID,
1679                                   Abbv) != VST_BBENTRY_6_ABBREV)
1680      llvm_unreachable("Unexpected abbrev ordering!");
1681  }
1682
1683
1684
1685  { // SETTYPE abbrev for CONSTANTS_BLOCK.
1686    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1687    Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_SETTYPE));
1688    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,
1689                              Log2_32_Ceil(VE.getTypes().size()+1)));
1690    if (Stream.EmitBlockInfoAbbrev(bitc::CONSTANTS_BLOCK_ID,
1691                                   Abbv) != CONSTANTS_SETTYPE_ABBREV)
1692      llvm_unreachable("Unexpected abbrev ordering!");
1693  }
1694
1695  { // INTEGER abbrev for CONSTANTS_BLOCK.
1696    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1697    Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_INTEGER));
1698    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
1699    if (Stream.EmitBlockInfoAbbrev(bitc::CONSTANTS_BLOCK_ID,
1700                                   Abbv) != CONSTANTS_INTEGER_ABBREV)
1701      llvm_unreachable("Unexpected abbrev ordering!");
1702  }
1703
1704  { // CE_CAST abbrev for CONSTANTS_BLOCK.
1705    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1706    Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_CE_CAST));
1707    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 4));  // cast opc
1708    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,       // typeid
1709                              Log2_32_Ceil(VE.getTypes().size()+1)));
1710    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));    // value id
1711
1712    if (Stream.EmitBlockInfoAbbrev(bitc::CONSTANTS_BLOCK_ID,
1713                                   Abbv) != CONSTANTS_CE_CAST_Abbrev)
1714      llvm_unreachable("Unexpected abbrev ordering!");
1715  }
1716  { // NULL abbrev for CONSTANTS_BLOCK.
1717    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1718    Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_NULL));
1719    if (Stream.EmitBlockInfoAbbrev(bitc::CONSTANTS_BLOCK_ID,
1720                                   Abbv) != CONSTANTS_NULL_Abbrev)
1721      llvm_unreachable("Unexpected abbrev ordering!");
1722  }
1723
1724  // FIXME: This should only use space for first class types!
1725
1726  { // INST_LOAD abbrev for FUNCTION_BLOCK.
1727    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1728    Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_LOAD));
1729    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // Ptr
1730    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4)); // Align
1731    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1)); // volatile
1732    if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
1733                                   Abbv) != FUNCTION_INST_LOAD_ABBREV)
1734      llvm_unreachable("Unexpected abbrev ordering!");
1735  }
1736  { // INST_BINOP abbrev for FUNCTION_BLOCK.
1737    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1738    Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_BINOP));
1739    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // LHS
1740    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // RHS
1741    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 4)); // opc
1742    if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
1743                                   Abbv) != FUNCTION_INST_BINOP_ABBREV)
1744      llvm_unreachable("Unexpected abbrev ordering!");
1745  }
1746  { // INST_BINOP_FLAGS abbrev for FUNCTION_BLOCK.
1747    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1748    Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_BINOP));
1749    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // LHS
1750    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // RHS
1751    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 4)); // opc
1752    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 7)); // flags
1753    if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
1754                                   Abbv) != FUNCTION_INST_BINOP_FLAGS_ABBREV)
1755      llvm_unreachable("Unexpected abbrev ordering!");
1756  }
1757  { // INST_CAST abbrev for FUNCTION_BLOCK.
1758    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1759    Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_CAST));
1760    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));    // OpVal
1761    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,       // dest ty
1762                              Log2_32_Ceil(VE.getTypes().size()+1)));
1763    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 4));  // opc
1764    if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
1765                                   Abbv) != FUNCTION_INST_CAST_ABBREV)
1766      llvm_unreachable("Unexpected abbrev ordering!");
1767  }
1768
1769  { // INST_RET abbrev for FUNCTION_BLOCK.
1770    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1771    Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_RET));
1772    if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
1773                                   Abbv) != FUNCTION_INST_RET_VOID_ABBREV)
1774      llvm_unreachable("Unexpected abbrev ordering!");
1775  }
1776  { // INST_RET abbrev for FUNCTION_BLOCK.
1777    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1778    Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_RET));
1779    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // ValID
1780    if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
1781                                   Abbv) != FUNCTION_INST_RET_VAL_ABBREV)
1782      llvm_unreachable("Unexpected abbrev ordering!");
1783  }
1784  { // INST_UNREACHABLE abbrev for FUNCTION_BLOCK.
1785    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1786    Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_UNREACHABLE));
1787    if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
1788                                   Abbv) != FUNCTION_INST_UNREACHABLE_ABBREV)
1789      llvm_unreachable("Unexpected abbrev ordering!");
1790  }
1791
1792  Stream.ExitBlock();
1793}
1794
1795// Sort the Users based on the order in which the reader parses the bitcode
1796// file.
1797static bool bitcodereader_order(const User *lhs, const User *rhs) {
1798  // TODO: Implement.
1799  return true;
1800}
1801
1802static void WriteUseList(const Value *V, const ValueEnumerator &VE,
1803                         BitstreamWriter &Stream) {
1804
1805  // One or zero uses can't get out of order.
1806  if (V->use_empty() || V->hasNUses(1))
1807    return;
1808
1809  // Make a copy of the in-memory use-list for sorting.
1810  unsigned UseListSize = std::distance(V->use_begin(), V->use_end());
1811  SmallVector<const User*, 8> UseList;
1812  UseList.reserve(UseListSize);
1813  for (Value::const_use_iterator I = V->use_begin(), E = V->use_end();
1814       I != E; ++I) {
1815    const User *U = *I;
1816    UseList.push_back(U);
1817  }
1818
1819  // Sort the copy based on the order read by the BitcodeReader.
1820  std::sort(UseList.begin(), UseList.end(), bitcodereader_order);
1821
1822  // TODO: Generate a diff between the BitcodeWriter in-memory use-list and the
1823  // sorted list (i.e., the expected BitcodeReader in-memory use-list).
1824
1825  // TODO: Emit the USELIST_CODE_ENTRYs.
1826}
1827
1828static void WriteFunctionUseList(const Function *F, ValueEnumerator &VE,
1829                                 BitstreamWriter &Stream) {
1830  VE.incorporateFunction(*F);
1831
1832  for (Function::const_arg_iterator AI = F->arg_begin(), AE = F->arg_end();
1833       AI != AE; ++AI)
1834    WriteUseList(AI, VE, Stream);
1835  for (Function::const_iterator BB = F->begin(), FE = F->end(); BB != FE;
1836       ++BB) {
1837    WriteUseList(BB, VE, Stream);
1838    for (BasicBlock::const_iterator II = BB->begin(), IE = BB->end(); II != IE;
1839         ++II) {
1840      WriteUseList(II, VE, Stream);
1841      for (User::const_op_iterator OI = II->op_begin(), E = II->op_end();
1842           OI != E; ++OI) {
1843        if ((isa<Constant>(*OI) && !isa<GlobalValue>(*OI)) ||
1844            isa<InlineAsm>(*OI))
1845          WriteUseList(*OI, VE, Stream);
1846      }
1847    }
1848  }
1849  VE.purgeFunction();
1850}
1851
1852// Emit use-lists.
1853static void WriteModuleUseLists(const Module *M, ValueEnumerator &VE,
1854                                BitstreamWriter &Stream) {
1855  Stream.EnterSubblock(bitc::USELIST_BLOCK_ID, 3);
1856
1857  // XXX: this modifies the module, but in a way that should never change the
1858  // behavior of any pass or codegen in LLVM. The problem is that GVs may
1859  // contain entries in the use_list that do not exist in the Module and are
1860  // not stored in the .bc file.
1861  for (Module::const_global_iterator I = M->global_begin(), E = M->global_end();
1862       I != E; ++I)
1863    I->removeDeadConstantUsers();
1864
1865  // Write the global variables.
1866  for (Module::const_global_iterator GI = M->global_begin(),
1867         GE = M->global_end(); GI != GE; ++GI) {
1868    WriteUseList(GI, VE, Stream);
1869
1870    // Write the global variable initializers.
1871    if (GI->hasInitializer())
1872      WriteUseList(GI->getInitializer(), VE, Stream);
1873  }
1874
1875  // Write the functions.
1876  for (Module::const_iterator FI = M->begin(), FE = M->end(); FI != FE; ++FI) {
1877    WriteUseList(FI, VE, Stream);
1878    if (!FI->isDeclaration())
1879      WriteFunctionUseList(FI, VE, Stream);
1880  }
1881
1882  // Write the aliases.
1883  for (Module::const_alias_iterator AI = M->alias_begin(), AE = M->alias_end();
1884       AI != AE; ++AI) {
1885    WriteUseList(AI, VE, Stream);
1886    WriteUseList(AI->getAliasee(), VE, Stream);
1887  }
1888
1889  Stream.ExitBlock();
1890}
1891
1892/// WriteModule - Emit the specified module to the bitstream.
1893static void WriteModule(const Module *M, BitstreamWriter &Stream) {
1894  Stream.EnterSubblock(bitc::MODULE_BLOCK_ID, 3);
1895
1896  SmallVector<unsigned, 1> Vals;
1897  unsigned CurVersion = 1;
1898  Vals.push_back(CurVersion);
1899  Stream.EmitRecord(bitc::MODULE_CODE_VERSION, Vals);
1900
1901  // Analyze the module, enumerating globals, functions, etc.
1902  ValueEnumerator VE(M);
1903
1904  // Emit blockinfo, which defines the standard abbreviations etc.
1905  WriteBlockInfo(VE, Stream);
1906
1907  // Emit information about attribute groups.
1908  WriteAttributeGroupTable(VE, Stream);
1909
1910  // Emit information about parameter attributes.
1911  WriteAttributeTable(VE, Stream);
1912
1913  // Emit information describing all of the types in the module.
1914  WriteTypeTable(VE, Stream);
1915
1916  // Emit top-level description of module, including target triple, inline asm,
1917  // descriptors for global variables, and function prototype info.
1918  WriteModuleInfo(M, VE, Stream);
1919
1920  // Emit constants.
1921  WriteModuleConstants(VE, Stream);
1922
1923  // Emit metadata.
1924  WriteModuleMetadata(M, VE, Stream);
1925
1926  // Emit metadata.
1927  WriteModuleMetadataStore(M, Stream);
1928
1929  // Emit names for globals/functions etc.
1930  WriteValueSymbolTable(M->getValueSymbolTable(), VE, Stream);
1931
1932  // Emit use-lists.
1933  if (EnablePreserveUseListOrdering)
1934    WriteModuleUseLists(M, VE, Stream);
1935
1936  // Emit function bodies.
1937  for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F)
1938    if (!F->isDeclaration())
1939      WriteFunction(*F, VE, Stream);
1940
1941  Stream.ExitBlock();
1942}
1943
1944/// EmitDarwinBCHeader - If generating a bc file on darwin, we have to emit a
1945/// header and trailer to make it compatible with the system archiver.  To do
1946/// this we emit the following header, and then emit a trailer that pads the
1947/// file out to be a multiple of 16 bytes.
1948///
1949/// struct bc_header {
1950///   uint32_t Magic;         // 0x0B17C0DE
1951///   uint32_t Version;       // Version, currently always 0.
1952///   uint32_t BitcodeOffset; // Offset to traditional bitcode file.
1953///   uint32_t BitcodeSize;   // Size of traditional bitcode file.
1954///   uint32_t CPUType;       // CPU specifier.
1955///   ... potentially more later ...
1956/// };
1957enum {
1958  DarwinBCSizeFieldOffset = 3*4, // Offset to bitcode_size.
1959  DarwinBCHeaderSize = 5*4
1960};
1961
1962static void WriteInt32ToBuffer(uint32_t Value, SmallVectorImpl<char> &Buffer,
1963                               uint32_t &Position) {
1964  Buffer[Position + 0] = (unsigned char) (Value >>  0);
1965  Buffer[Position + 1] = (unsigned char) (Value >>  8);
1966  Buffer[Position + 2] = (unsigned char) (Value >> 16);
1967  Buffer[Position + 3] = (unsigned char) (Value >> 24);
1968  Position += 4;
1969}
1970
1971static void EmitDarwinBCHeaderAndTrailer(SmallVectorImpl<char> &Buffer,
1972                                         const Triple &TT) {
1973  unsigned CPUType = ~0U;
1974
1975  // Match x86_64-*, i[3-9]86-*, powerpc-*, powerpc64-*, arm-*, thumb-*,
1976  // armv[0-9]-*, thumbv[0-9]-*, armv5te-*, or armv6t2-*. The CPUType is a magic
1977  // number from /usr/include/mach/machine.h.  It is ok to reproduce the
1978  // specific constants here because they are implicitly part of the Darwin ABI.
1979  enum {
1980    DARWIN_CPU_ARCH_ABI64      = 0x01000000,
1981    DARWIN_CPU_TYPE_X86        = 7,
1982    DARWIN_CPU_TYPE_ARM        = 12,
1983    DARWIN_CPU_TYPE_POWERPC    = 18
1984  };
1985
1986  Triple::ArchType Arch = TT.getArch();
1987  if (Arch == Triple::x86_64)
1988    CPUType = DARWIN_CPU_TYPE_X86 | DARWIN_CPU_ARCH_ABI64;
1989  else if (Arch == Triple::x86)
1990    CPUType = DARWIN_CPU_TYPE_X86;
1991  else if (Arch == Triple::ppc)
1992    CPUType = DARWIN_CPU_TYPE_POWERPC;
1993  else if (Arch == Triple::ppc64)
1994    CPUType = DARWIN_CPU_TYPE_POWERPC | DARWIN_CPU_ARCH_ABI64;
1995  else if (Arch == Triple::arm || Arch == Triple::thumb)
1996    CPUType = DARWIN_CPU_TYPE_ARM;
1997
1998  // Traditional Bitcode starts after header.
1999  assert(Buffer.size() >= DarwinBCHeaderSize &&
2000         "Expected header size to be reserved");
2001  unsigned BCOffset = DarwinBCHeaderSize;
2002  unsigned BCSize = Buffer.size()-DarwinBCHeaderSize;
2003
2004  // Write the magic and version.
2005  unsigned Position = 0;
2006  WriteInt32ToBuffer(0x0B17C0DE , Buffer, Position);
2007  WriteInt32ToBuffer(0          , Buffer, Position); // Version.
2008  WriteInt32ToBuffer(BCOffset   , Buffer, Position);
2009  WriteInt32ToBuffer(BCSize     , Buffer, Position);
2010  WriteInt32ToBuffer(CPUType    , Buffer, Position);
2011
2012  // If the file is not a multiple of 16 bytes, insert dummy padding.
2013  while (Buffer.size() & 15)
2014    Buffer.push_back(0);
2015}
2016
2017/// WriteBitcodeToFile - Write the specified module to the specified output
2018/// stream.
2019void llvm::WriteBitcodeToFile(const Module *M, raw_ostream &Out) {
2020  SmallVector<char, 0> Buffer;
2021  Buffer.reserve(256*1024);
2022
2023  // If this is darwin or another generic macho target, reserve space for the
2024  // header.
2025  Triple TT(M->getTargetTriple());
2026  if (TT.isOSDarwin())
2027    Buffer.insert(Buffer.begin(), DarwinBCHeaderSize, 0);
2028
2029  // Emit the module into the buffer.
2030  {
2031    BitstreamWriter Stream(Buffer);
2032
2033    // Emit the file header.
2034    Stream.Emit((unsigned)'B', 8);
2035    Stream.Emit((unsigned)'C', 8);
2036    Stream.Emit(0x0, 4);
2037    Stream.Emit(0xC, 4);
2038    Stream.Emit(0xE, 4);
2039    Stream.Emit(0xD, 4);
2040
2041    // Emit the module.
2042    WriteModule(M, Stream);
2043  }
2044
2045  if (TT.isOSDarwin())
2046    EmitDarwinBCHeaderAndTrailer(Buffer, TT);
2047
2048  // Write the generated bitstream to "Out".
2049  Out.write((char*)&Buffer.front(), Buffer.size());
2050}
2051