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 "ValueEnumerator.h"
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/Triple.h"
17 #include "llvm/Analysis/BlockFrequencyInfo.h"
18 #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
19 #include "llvm/Analysis/BranchProbabilityInfo.h"
20 #include "llvm/Analysis/LoopInfo.h"
21 #include "llvm/Bitcode/BitstreamWriter.h"
22 #include "llvm/Bitcode/LLVMBitCodes.h"
23 #include "llvm/Bitcode/ReaderWriter.h"
24 #include "llvm/IR/CallSite.h"
25 #include "llvm/IR/Constants.h"
26 #include "llvm/IR/DebugInfoMetadata.h"
27 #include "llvm/IR/DerivedTypes.h"
28 #include "llvm/IR/Dominators.h"
29 #include "llvm/IR/InlineAsm.h"
30 #include "llvm/IR/Instructions.h"
31 #include "llvm/IR/IntrinsicInst.h"
32 #include "llvm/IR/LLVMContext.h"
33 #include "llvm/IR/Module.h"
34 #include "llvm/IR/Operator.h"
35 #include "llvm/IR/UseListOrder.h"
36 #include "llvm/IR/ValueSymbolTable.h"
37 #include "llvm/Support/CommandLine.h"
38 #include "llvm/Support/ErrorHandling.h"
39 #include "llvm/Support/MathExtras.h"
40 #include "llvm/Support/Program.h"
41 #include "llvm/Support/raw_ostream.h"
42 #include <cctype>
43 #include <map>
44 using namespace llvm;
45 
46 /// These are manifest constants used by the bitcode writer. They do not need to
47 /// be kept in sync with the reader, but need to be consistent within this file.
48 enum {
49   // VALUE_SYMTAB_BLOCK abbrev id's.
50   VST_ENTRY_8_ABBREV = bitc::FIRST_APPLICATION_ABBREV,
51   VST_ENTRY_7_ABBREV,
52   VST_ENTRY_6_ABBREV,
53   VST_BBENTRY_6_ABBREV,
54 
55   // CONSTANTS_BLOCK abbrev id's.
56   CONSTANTS_SETTYPE_ABBREV = bitc::FIRST_APPLICATION_ABBREV,
57   CONSTANTS_INTEGER_ABBREV,
58   CONSTANTS_CE_CAST_Abbrev,
59   CONSTANTS_NULL_Abbrev,
60 
61   // FUNCTION_BLOCK abbrev id's.
62   FUNCTION_INST_LOAD_ABBREV = bitc::FIRST_APPLICATION_ABBREV,
63   FUNCTION_INST_BINOP_ABBREV,
64   FUNCTION_INST_BINOP_FLAGS_ABBREV,
65   FUNCTION_INST_CAST_ABBREV,
66   FUNCTION_INST_RET_VOID_ABBREV,
67   FUNCTION_INST_RET_VAL_ABBREV,
68   FUNCTION_INST_UNREACHABLE_ABBREV,
69   FUNCTION_INST_GEP_ABBREV,
70 };
71 
72 static unsigned GetEncodedCastOpcode(unsigned Opcode) {
73   switch (Opcode) {
74   default: llvm_unreachable("Unknown cast instruction!");
75   case Instruction::Trunc   : return bitc::CAST_TRUNC;
76   case Instruction::ZExt    : return bitc::CAST_ZEXT;
77   case Instruction::SExt    : return bitc::CAST_SEXT;
78   case Instruction::FPToUI  : return bitc::CAST_FPTOUI;
79   case Instruction::FPToSI  : return bitc::CAST_FPTOSI;
80   case Instruction::UIToFP  : return bitc::CAST_UITOFP;
81   case Instruction::SIToFP  : return bitc::CAST_SITOFP;
82   case Instruction::FPTrunc : return bitc::CAST_FPTRUNC;
83   case Instruction::FPExt   : return bitc::CAST_FPEXT;
84   case Instruction::PtrToInt: return bitc::CAST_PTRTOINT;
85   case Instruction::IntToPtr: return bitc::CAST_INTTOPTR;
86   case Instruction::BitCast : return bitc::CAST_BITCAST;
87   case Instruction::AddrSpaceCast: return bitc::CAST_ADDRSPACECAST;
88   }
89 }
90 
91 static unsigned GetEncodedBinaryOpcode(unsigned Opcode) {
92   switch (Opcode) {
93   default: llvm_unreachable("Unknown binary instruction!");
94   case Instruction::Add:
95   case Instruction::FAdd: return bitc::BINOP_ADD;
96   case Instruction::Sub:
97   case Instruction::FSub: return bitc::BINOP_SUB;
98   case Instruction::Mul:
99   case Instruction::FMul: return bitc::BINOP_MUL;
100   case Instruction::UDiv: return bitc::BINOP_UDIV;
101   case Instruction::FDiv:
102   case Instruction::SDiv: return bitc::BINOP_SDIV;
103   case Instruction::URem: return bitc::BINOP_UREM;
104   case Instruction::FRem:
105   case Instruction::SRem: return bitc::BINOP_SREM;
106   case Instruction::Shl:  return bitc::BINOP_SHL;
107   case Instruction::LShr: return bitc::BINOP_LSHR;
108   case Instruction::AShr: return bitc::BINOP_ASHR;
109   case Instruction::And:  return bitc::BINOP_AND;
110   case Instruction::Or:   return bitc::BINOP_OR;
111   case Instruction::Xor:  return bitc::BINOP_XOR;
112   }
113 }
114 
115 static unsigned GetEncodedRMWOperation(AtomicRMWInst::BinOp Op) {
116   switch (Op) {
117   default: llvm_unreachable("Unknown RMW operation!");
118   case AtomicRMWInst::Xchg: return bitc::RMW_XCHG;
119   case AtomicRMWInst::Add: return bitc::RMW_ADD;
120   case AtomicRMWInst::Sub: return bitc::RMW_SUB;
121   case AtomicRMWInst::And: return bitc::RMW_AND;
122   case AtomicRMWInst::Nand: return bitc::RMW_NAND;
123   case AtomicRMWInst::Or: return bitc::RMW_OR;
124   case AtomicRMWInst::Xor: return bitc::RMW_XOR;
125   case AtomicRMWInst::Max: return bitc::RMW_MAX;
126   case AtomicRMWInst::Min: return bitc::RMW_MIN;
127   case AtomicRMWInst::UMax: return bitc::RMW_UMAX;
128   case AtomicRMWInst::UMin: return bitc::RMW_UMIN;
129   }
130 }
131 
132 static unsigned GetEncodedOrdering(AtomicOrdering Ordering) {
133   switch (Ordering) {
134   case NotAtomic: return bitc::ORDERING_NOTATOMIC;
135   case Unordered: return bitc::ORDERING_UNORDERED;
136   case Monotonic: return bitc::ORDERING_MONOTONIC;
137   case Acquire: return bitc::ORDERING_ACQUIRE;
138   case Release: return bitc::ORDERING_RELEASE;
139   case AcquireRelease: return bitc::ORDERING_ACQREL;
140   case SequentiallyConsistent: return bitc::ORDERING_SEQCST;
141   }
142   llvm_unreachable("Invalid ordering");
143 }
144 
145 static unsigned GetEncodedSynchScope(SynchronizationScope SynchScope) {
146   switch (SynchScope) {
147   case SingleThread: return bitc::SYNCHSCOPE_SINGLETHREAD;
148   case CrossThread: return bitc::SYNCHSCOPE_CROSSTHREAD;
149   }
150   llvm_unreachable("Invalid synch scope");
151 }
152 
153 static void WriteStringRecord(unsigned Code, StringRef Str,
154                               unsigned AbbrevToUse, BitstreamWriter &Stream) {
155   SmallVector<unsigned, 64> Vals;
156 
157   // Code: [strchar x N]
158   for (unsigned i = 0, e = Str.size(); i != e; ++i) {
159     if (AbbrevToUse && !BitCodeAbbrevOp::isChar6(Str[i]))
160       AbbrevToUse = 0;
161     Vals.push_back(Str[i]);
162   }
163 
164   // Emit the finished record.
165   Stream.EmitRecord(Code, Vals, AbbrevToUse);
166 }
167 
168 static uint64_t getAttrKindEncoding(Attribute::AttrKind Kind) {
169   switch (Kind) {
170   case Attribute::Alignment:
171     return bitc::ATTR_KIND_ALIGNMENT;
172   case Attribute::AlwaysInline:
173     return bitc::ATTR_KIND_ALWAYS_INLINE;
174   case Attribute::ArgMemOnly:
175     return bitc::ATTR_KIND_ARGMEMONLY;
176   case Attribute::Builtin:
177     return bitc::ATTR_KIND_BUILTIN;
178   case Attribute::ByVal:
179     return bitc::ATTR_KIND_BY_VAL;
180   case Attribute::Convergent:
181     return bitc::ATTR_KIND_CONVERGENT;
182   case Attribute::InAlloca:
183     return bitc::ATTR_KIND_IN_ALLOCA;
184   case Attribute::Cold:
185     return bitc::ATTR_KIND_COLD;
186   case Attribute::InaccessibleMemOnly:
187     return bitc::ATTR_KIND_INACCESSIBLEMEM_ONLY;
188   case Attribute::InaccessibleMemOrArgMemOnly:
189     return bitc::ATTR_KIND_INACCESSIBLEMEM_OR_ARGMEMONLY;
190   case Attribute::InlineHint:
191     return bitc::ATTR_KIND_INLINE_HINT;
192   case Attribute::InReg:
193     return bitc::ATTR_KIND_IN_REG;
194   case Attribute::JumpTable:
195     return bitc::ATTR_KIND_JUMP_TABLE;
196   case Attribute::MinSize:
197     return bitc::ATTR_KIND_MIN_SIZE;
198   case Attribute::Naked:
199     return bitc::ATTR_KIND_NAKED;
200   case Attribute::Nest:
201     return bitc::ATTR_KIND_NEST;
202   case Attribute::NoAlias:
203     return bitc::ATTR_KIND_NO_ALIAS;
204   case Attribute::NoBuiltin:
205     return bitc::ATTR_KIND_NO_BUILTIN;
206   case Attribute::NoCapture:
207     return bitc::ATTR_KIND_NO_CAPTURE;
208   case Attribute::NoDuplicate:
209     return bitc::ATTR_KIND_NO_DUPLICATE;
210   case Attribute::NoImplicitFloat:
211     return bitc::ATTR_KIND_NO_IMPLICIT_FLOAT;
212   case Attribute::NoInline:
213     return bitc::ATTR_KIND_NO_INLINE;
214   case Attribute::NoRecurse:
215     return bitc::ATTR_KIND_NO_RECURSE;
216   case Attribute::NonLazyBind:
217     return bitc::ATTR_KIND_NON_LAZY_BIND;
218   case Attribute::NonNull:
219     return bitc::ATTR_KIND_NON_NULL;
220   case Attribute::Dereferenceable:
221     return bitc::ATTR_KIND_DEREFERENCEABLE;
222   case Attribute::DereferenceableOrNull:
223     return bitc::ATTR_KIND_DEREFERENCEABLE_OR_NULL;
224   case Attribute::NoRedZone:
225     return bitc::ATTR_KIND_NO_RED_ZONE;
226   case Attribute::NoReturn:
227     return bitc::ATTR_KIND_NO_RETURN;
228   case Attribute::NoUnwind:
229     return bitc::ATTR_KIND_NO_UNWIND;
230   case Attribute::OptimizeForSize:
231     return bitc::ATTR_KIND_OPTIMIZE_FOR_SIZE;
232   case Attribute::OptimizeNone:
233     return bitc::ATTR_KIND_OPTIMIZE_NONE;
234   case Attribute::ReadNone:
235     return bitc::ATTR_KIND_READ_NONE;
236   case Attribute::ReadOnly:
237     return bitc::ATTR_KIND_READ_ONLY;
238   case Attribute::Returned:
239     return bitc::ATTR_KIND_RETURNED;
240   case Attribute::ReturnsTwice:
241     return bitc::ATTR_KIND_RETURNS_TWICE;
242   case Attribute::SExt:
243     return bitc::ATTR_KIND_S_EXT;
244   case Attribute::StackAlignment:
245     return bitc::ATTR_KIND_STACK_ALIGNMENT;
246   case Attribute::StackProtect:
247     return bitc::ATTR_KIND_STACK_PROTECT;
248   case Attribute::StackProtectReq:
249     return bitc::ATTR_KIND_STACK_PROTECT_REQ;
250   case Attribute::StackProtectStrong:
251     return bitc::ATTR_KIND_STACK_PROTECT_STRONG;
252   case Attribute::SafeStack:
253     return bitc::ATTR_KIND_SAFESTACK;
254   case Attribute::StructRet:
255     return bitc::ATTR_KIND_STRUCT_RET;
256   case Attribute::SanitizeAddress:
257     return bitc::ATTR_KIND_SANITIZE_ADDRESS;
258   case Attribute::SanitizeThread:
259     return bitc::ATTR_KIND_SANITIZE_THREAD;
260   case Attribute::SanitizeMemory:
261     return bitc::ATTR_KIND_SANITIZE_MEMORY;
262   case Attribute::UWTable:
263     return bitc::ATTR_KIND_UW_TABLE;
264   case Attribute::ZExt:
265     return bitc::ATTR_KIND_Z_EXT;
266   case Attribute::EndAttrKinds:
267     llvm_unreachable("Can not encode end-attribute kinds marker.");
268   case Attribute::None:
269     llvm_unreachable("Can not encode none-attribute.");
270   }
271 
272   llvm_unreachable("Trying to encode unknown attribute");
273 }
274 
275 static void WriteAttributeGroupTable(const ValueEnumerator &VE,
276                                      BitstreamWriter &Stream) {
277   const std::vector<AttributeSet> &AttrGrps = VE.getAttributeGroups();
278   if (AttrGrps.empty()) return;
279 
280   Stream.EnterSubblock(bitc::PARAMATTR_GROUP_BLOCK_ID, 3);
281 
282   SmallVector<uint64_t, 64> Record;
283   for (unsigned i = 0, e = AttrGrps.size(); i != e; ++i) {
284     AttributeSet AS = AttrGrps[i];
285     for (unsigned i = 0, e = AS.getNumSlots(); i != e; ++i) {
286       AttributeSet A = AS.getSlotAttributes(i);
287 
288       Record.push_back(VE.getAttributeGroupID(A));
289       Record.push_back(AS.getSlotIndex(i));
290 
291       for (AttributeSet::iterator I = AS.begin(0), E = AS.end(0);
292            I != E; ++I) {
293         Attribute Attr = *I;
294         if (Attr.isEnumAttribute()) {
295           Record.push_back(0);
296           Record.push_back(getAttrKindEncoding(Attr.getKindAsEnum()));
297         } else if (Attr.isIntAttribute()) {
298           Record.push_back(1);
299           Record.push_back(getAttrKindEncoding(Attr.getKindAsEnum()));
300           Record.push_back(Attr.getValueAsInt());
301         } else {
302           StringRef Kind = Attr.getKindAsString();
303           StringRef Val = Attr.getValueAsString();
304 
305           Record.push_back(Val.empty() ? 3 : 4);
306           Record.append(Kind.begin(), Kind.end());
307           Record.push_back(0);
308           if (!Val.empty()) {
309             Record.append(Val.begin(), Val.end());
310             Record.push_back(0);
311           }
312         }
313       }
314 
315       Stream.EmitRecord(bitc::PARAMATTR_GRP_CODE_ENTRY, Record);
316       Record.clear();
317     }
318   }
319 
320   Stream.ExitBlock();
321 }
322 
323 static void WriteAttributeTable(const ValueEnumerator &VE,
324                                 BitstreamWriter &Stream) {
325   const std::vector<AttributeSet> &Attrs = VE.getAttributes();
326   if (Attrs.empty()) return;
327 
328   Stream.EnterSubblock(bitc::PARAMATTR_BLOCK_ID, 3);
329 
330   SmallVector<uint64_t, 64> Record;
331   for (unsigned i = 0, e = Attrs.size(); i != e; ++i) {
332     const AttributeSet &A = Attrs[i];
333     for (unsigned i = 0, e = A.getNumSlots(); i != e; ++i)
334       Record.push_back(VE.getAttributeGroupID(A.getSlotAttributes(i)));
335 
336     Stream.EmitRecord(bitc::PARAMATTR_CODE_ENTRY, Record);
337     Record.clear();
338   }
339 
340   Stream.ExitBlock();
341 }
342 
343 /// WriteTypeTable - Write out the type table for a module.
344 static void WriteTypeTable(const ValueEnumerator &VE, BitstreamWriter &Stream) {
345   const ValueEnumerator::TypeList &TypeList = VE.getTypes();
346 
347   Stream.EnterSubblock(bitc::TYPE_BLOCK_ID_NEW, 4 /*count from # abbrevs */);
348   SmallVector<uint64_t, 64> TypeVals;
349 
350   uint64_t NumBits = VE.computeBitsRequiredForTypeIndicies();
351 
352   // Abbrev for TYPE_CODE_POINTER.
353   BitCodeAbbrev *Abbv = new BitCodeAbbrev();
354   Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_POINTER));
355   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, NumBits));
356   Abbv->Add(BitCodeAbbrevOp(0));  // Addrspace = 0
357   unsigned PtrAbbrev = Stream.EmitAbbrev(Abbv);
358 
359   // Abbrev for TYPE_CODE_FUNCTION.
360   Abbv = new BitCodeAbbrev();
361   Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_FUNCTION));
362   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1));  // isvararg
363   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
364   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, NumBits));
365 
366   unsigned FunctionAbbrev = Stream.EmitAbbrev(Abbv);
367 
368   // Abbrev for TYPE_CODE_STRUCT_ANON.
369   Abbv = new BitCodeAbbrev();
370   Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_STRUCT_ANON));
371   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1));  // ispacked
372   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
373   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, NumBits));
374 
375   unsigned StructAnonAbbrev = Stream.EmitAbbrev(Abbv);
376 
377   // Abbrev for TYPE_CODE_STRUCT_NAME.
378   Abbv = new BitCodeAbbrev();
379   Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_STRUCT_NAME));
380   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
381   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Char6));
382   unsigned StructNameAbbrev = Stream.EmitAbbrev(Abbv);
383 
384   // Abbrev for TYPE_CODE_STRUCT_NAMED.
385   Abbv = new BitCodeAbbrev();
386   Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_STRUCT_NAMED));
387   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1));  // ispacked
388   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
389   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, NumBits));
390 
391   unsigned StructNamedAbbrev = Stream.EmitAbbrev(Abbv);
392 
393   // Abbrev for TYPE_CODE_ARRAY.
394   Abbv = new BitCodeAbbrev();
395   Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_ARRAY));
396   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // size
397   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, NumBits));
398 
399   unsigned ArrayAbbrev = Stream.EmitAbbrev(Abbv);
400 
401   // Emit an entry count so the reader can reserve space.
402   TypeVals.push_back(TypeList.size());
403   Stream.EmitRecord(bitc::TYPE_CODE_NUMENTRY, TypeVals);
404   TypeVals.clear();
405 
406   // Loop over all of the types, emitting each in turn.
407   for (unsigned i = 0, e = TypeList.size(); i != e; ++i) {
408     Type *T = TypeList[i];
409     int AbbrevToUse = 0;
410     unsigned Code = 0;
411 
412     switch (T->getTypeID()) {
413     case Type::VoidTyID:      Code = bitc::TYPE_CODE_VOID;      break;
414     case Type::HalfTyID:      Code = bitc::TYPE_CODE_HALF;      break;
415     case Type::FloatTyID:     Code = bitc::TYPE_CODE_FLOAT;     break;
416     case Type::DoubleTyID:    Code = bitc::TYPE_CODE_DOUBLE;    break;
417     case Type::X86_FP80TyID:  Code = bitc::TYPE_CODE_X86_FP80;  break;
418     case Type::FP128TyID:     Code = bitc::TYPE_CODE_FP128;     break;
419     case Type::PPC_FP128TyID: Code = bitc::TYPE_CODE_PPC_FP128; break;
420     case Type::LabelTyID:     Code = bitc::TYPE_CODE_LABEL;     break;
421     case Type::MetadataTyID:  Code = bitc::TYPE_CODE_METADATA;  break;
422     case Type::X86_MMXTyID:   Code = bitc::TYPE_CODE_X86_MMX;   break;
423     case Type::TokenTyID:     Code = bitc::TYPE_CODE_TOKEN;     break;
424     case Type::IntegerTyID:
425       // INTEGER: [width]
426       Code = bitc::TYPE_CODE_INTEGER;
427       TypeVals.push_back(cast<IntegerType>(T)->getBitWidth());
428       break;
429     case Type::PointerTyID: {
430       PointerType *PTy = cast<PointerType>(T);
431       // POINTER: [pointee type, address space]
432       Code = bitc::TYPE_CODE_POINTER;
433       TypeVals.push_back(VE.getTypeID(PTy->getElementType()));
434       unsigned AddressSpace = PTy->getAddressSpace();
435       TypeVals.push_back(AddressSpace);
436       if (AddressSpace == 0) AbbrevToUse = PtrAbbrev;
437       break;
438     }
439     case Type::FunctionTyID: {
440       FunctionType *FT = cast<FunctionType>(T);
441       // FUNCTION: [isvararg, retty, paramty x N]
442       Code = bitc::TYPE_CODE_FUNCTION;
443       TypeVals.push_back(FT->isVarArg());
444       TypeVals.push_back(VE.getTypeID(FT->getReturnType()));
445       for (unsigned i = 0, e = FT->getNumParams(); i != e; ++i)
446         TypeVals.push_back(VE.getTypeID(FT->getParamType(i)));
447       AbbrevToUse = FunctionAbbrev;
448       break;
449     }
450     case Type::StructTyID: {
451       StructType *ST = cast<StructType>(T);
452       // STRUCT: [ispacked, eltty x N]
453       TypeVals.push_back(ST->isPacked());
454       // Output all of the element types.
455       for (StructType::element_iterator I = ST->element_begin(),
456            E = ST->element_end(); I != E; ++I)
457         TypeVals.push_back(VE.getTypeID(*I));
458 
459       if (ST->isLiteral()) {
460         Code = bitc::TYPE_CODE_STRUCT_ANON;
461         AbbrevToUse = StructAnonAbbrev;
462       } else {
463         if (ST->isOpaque()) {
464           Code = bitc::TYPE_CODE_OPAQUE;
465         } else {
466           Code = bitc::TYPE_CODE_STRUCT_NAMED;
467           AbbrevToUse = StructNamedAbbrev;
468         }
469 
470         // Emit the name if it is present.
471         if (!ST->getName().empty())
472           WriteStringRecord(bitc::TYPE_CODE_STRUCT_NAME, ST->getName(),
473                             StructNameAbbrev, Stream);
474       }
475       break;
476     }
477     case Type::ArrayTyID: {
478       ArrayType *AT = cast<ArrayType>(T);
479       // ARRAY: [numelts, eltty]
480       Code = bitc::TYPE_CODE_ARRAY;
481       TypeVals.push_back(AT->getNumElements());
482       TypeVals.push_back(VE.getTypeID(AT->getElementType()));
483       AbbrevToUse = ArrayAbbrev;
484       break;
485     }
486     case Type::VectorTyID: {
487       VectorType *VT = cast<VectorType>(T);
488       // VECTOR [numelts, eltty]
489       Code = bitc::TYPE_CODE_VECTOR;
490       TypeVals.push_back(VT->getNumElements());
491       TypeVals.push_back(VE.getTypeID(VT->getElementType()));
492       break;
493     }
494     }
495 
496     // Emit the finished record.
497     Stream.EmitRecord(Code, TypeVals, AbbrevToUse);
498     TypeVals.clear();
499   }
500 
501   Stream.ExitBlock();
502 }
503 
504 static unsigned getEncodedLinkage(const GlobalValue::LinkageTypes Linkage) {
505   switch (Linkage) {
506   case GlobalValue::ExternalLinkage:
507     return 0;
508   case GlobalValue::WeakAnyLinkage:
509     return 16;
510   case GlobalValue::AppendingLinkage:
511     return 2;
512   case GlobalValue::InternalLinkage:
513     return 3;
514   case GlobalValue::LinkOnceAnyLinkage:
515     return 18;
516   case GlobalValue::ExternalWeakLinkage:
517     return 7;
518   case GlobalValue::CommonLinkage:
519     return 8;
520   case GlobalValue::PrivateLinkage:
521     return 9;
522   case GlobalValue::WeakODRLinkage:
523     return 17;
524   case GlobalValue::LinkOnceODRLinkage:
525     return 19;
526   case GlobalValue::AvailableExternallyLinkage:
527     return 12;
528   }
529   llvm_unreachable("Invalid linkage");
530 }
531 
532 static unsigned getEncodedLinkage(const GlobalValue &GV) {
533   return getEncodedLinkage(GV.getLinkage());
534 }
535 
536 static unsigned getEncodedVisibility(const GlobalValue &GV) {
537   switch (GV.getVisibility()) {
538   case GlobalValue::DefaultVisibility:   return 0;
539   case GlobalValue::HiddenVisibility:    return 1;
540   case GlobalValue::ProtectedVisibility: return 2;
541   }
542   llvm_unreachable("Invalid visibility");
543 }
544 
545 static unsigned getEncodedDLLStorageClass(const GlobalValue &GV) {
546   switch (GV.getDLLStorageClass()) {
547   case GlobalValue::DefaultStorageClass:   return 0;
548   case GlobalValue::DLLImportStorageClass: return 1;
549   case GlobalValue::DLLExportStorageClass: return 2;
550   }
551   llvm_unreachable("Invalid DLL storage class");
552 }
553 
554 static unsigned getEncodedThreadLocalMode(const GlobalValue &GV) {
555   switch (GV.getThreadLocalMode()) {
556     case GlobalVariable::NotThreadLocal:         return 0;
557     case GlobalVariable::GeneralDynamicTLSModel: return 1;
558     case GlobalVariable::LocalDynamicTLSModel:   return 2;
559     case GlobalVariable::InitialExecTLSModel:    return 3;
560     case GlobalVariable::LocalExecTLSModel:      return 4;
561   }
562   llvm_unreachable("Invalid TLS model");
563 }
564 
565 static unsigned getEncodedComdatSelectionKind(const Comdat &C) {
566   switch (C.getSelectionKind()) {
567   case Comdat::Any:
568     return bitc::COMDAT_SELECTION_KIND_ANY;
569   case Comdat::ExactMatch:
570     return bitc::COMDAT_SELECTION_KIND_EXACT_MATCH;
571   case Comdat::Largest:
572     return bitc::COMDAT_SELECTION_KIND_LARGEST;
573   case Comdat::NoDuplicates:
574     return bitc::COMDAT_SELECTION_KIND_NO_DUPLICATES;
575   case Comdat::SameSize:
576     return bitc::COMDAT_SELECTION_KIND_SAME_SIZE;
577   }
578   llvm_unreachable("Invalid selection kind");
579 }
580 
581 static void writeComdats(const ValueEnumerator &VE, BitstreamWriter &Stream) {
582   SmallVector<unsigned, 64> Vals;
583   for (const Comdat *C : VE.getComdats()) {
584     // COMDAT: [selection_kind, name]
585     Vals.push_back(getEncodedComdatSelectionKind(*C));
586     size_t Size = C->getName().size();
587     assert(isUInt<32>(Size));
588     Vals.push_back(Size);
589     for (char Chr : C->getName())
590       Vals.push_back((unsigned char)Chr);
591     Stream.EmitRecord(bitc::MODULE_CODE_COMDAT, Vals, /*AbbrevToUse=*/0);
592     Vals.clear();
593   }
594 }
595 
596 /// Write a record that will eventually hold the word offset of the
597 /// module-level VST. For now the offset is 0, which will be backpatched
598 /// after the real VST is written. Returns the bit offset to backpatch.
599 static uint64_t WriteValueSymbolTableForwardDecl(BitstreamWriter &Stream) {
600   // Write a placeholder value in for the offset of the real VST,
601   // which is written after the function blocks so that it can include
602   // the offset of each function. The placeholder offset will be
603   // updated when the real VST is written.
604   BitCodeAbbrev *Abbv = new BitCodeAbbrev();
605   Abbv->Add(BitCodeAbbrevOp(bitc::MODULE_CODE_VSTOFFSET));
606   // Blocks are 32-bit aligned, so we can use a 32-bit word offset to
607   // hold the real VST offset. Must use fixed instead of VBR as we don't
608   // know how many VBR chunks to reserve ahead of time.
609   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 32));
610   unsigned VSTOffsetAbbrev = Stream.EmitAbbrev(Abbv);
611 
612   // Emit the placeholder
613   uint64_t Vals[] = {bitc::MODULE_CODE_VSTOFFSET, 0};
614   Stream.EmitRecordWithAbbrev(VSTOffsetAbbrev, Vals);
615 
616   // Compute and return the bit offset to the placeholder, which will be
617   // patched when the real VST is written. We can simply subtract the 32-bit
618   // fixed size from the current bit number to get the location to backpatch.
619   return Stream.GetCurrentBitNo() - 32;
620 }
621 
622 enum StringEncoding { SE_Char6, SE_Fixed7, SE_Fixed8 };
623 
624 /// Determine the encoding to use for the given string name and length.
625 static StringEncoding getStringEncoding(const char *Str, unsigned StrLen) {
626   bool isChar6 = true;
627   for (const char *C = Str, *E = C + StrLen; C != E; ++C) {
628     if (isChar6)
629       isChar6 = BitCodeAbbrevOp::isChar6(*C);
630     if ((unsigned char)*C & 128)
631       // don't bother scanning the rest.
632       return SE_Fixed8;
633   }
634   if (isChar6)
635     return SE_Char6;
636   else
637     return SE_Fixed7;
638 }
639 
640 /// Emit top-level description of module, including target triple, inline asm,
641 /// descriptors for global variables, and function prototype info.
642 /// Returns the bit offset to backpatch with the location of the real VST.
643 static uint64_t WriteModuleInfo(const Module *M, const ValueEnumerator &VE,
644                                 BitstreamWriter &Stream) {
645   // Emit various pieces of data attached to a module.
646   if (!M->getTargetTriple().empty())
647     WriteStringRecord(bitc::MODULE_CODE_TRIPLE, M->getTargetTriple(),
648                       0/*TODO*/, Stream);
649   const std::string &DL = M->getDataLayoutStr();
650   if (!DL.empty())
651     WriteStringRecord(bitc::MODULE_CODE_DATALAYOUT, DL, 0 /*TODO*/, Stream);
652   if (!M->getModuleInlineAsm().empty())
653     WriteStringRecord(bitc::MODULE_CODE_ASM, M->getModuleInlineAsm(),
654                       0/*TODO*/, Stream);
655 
656   // Emit information about sections and GC, computing how many there are. Also
657   // compute the maximum alignment value.
658   std::map<std::string, unsigned> SectionMap;
659   std::map<std::string, unsigned> GCMap;
660   unsigned MaxAlignment = 0;
661   unsigned MaxGlobalType = 0;
662   for (const GlobalValue &GV : M->globals()) {
663     MaxAlignment = std::max(MaxAlignment, GV.getAlignment());
664     MaxGlobalType = std::max(MaxGlobalType, VE.getTypeID(GV.getValueType()));
665     if (GV.hasSection()) {
666       // Give section names unique ID's.
667       unsigned &Entry = SectionMap[GV.getSection()];
668       if (!Entry) {
669         WriteStringRecord(bitc::MODULE_CODE_SECTIONNAME, GV.getSection(),
670                           0/*TODO*/, Stream);
671         Entry = SectionMap.size();
672       }
673     }
674   }
675   for (const Function &F : *M) {
676     MaxAlignment = std::max(MaxAlignment, F.getAlignment());
677     if (F.hasSection()) {
678       // Give section names unique ID's.
679       unsigned &Entry = SectionMap[F.getSection()];
680       if (!Entry) {
681         WriteStringRecord(bitc::MODULE_CODE_SECTIONNAME, F.getSection(),
682                           0/*TODO*/, Stream);
683         Entry = SectionMap.size();
684       }
685     }
686     if (F.hasGC()) {
687       // Same for GC names.
688       unsigned &Entry = GCMap[F.getGC()];
689       if (!Entry) {
690         WriteStringRecord(bitc::MODULE_CODE_GCNAME, F.getGC(),
691                           0/*TODO*/, Stream);
692         Entry = GCMap.size();
693       }
694     }
695   }
696 
697   // Emit abbrev for globals, now that we know # sections and max alignment.
698   unsigned SimpleGVarAbbrev = 0;
699   if (!M->global_empty()) {
700     // Add an abbrev for common globals with no visibility or thread localness.
701     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
702     Abbv->Add(BitCodeAbbrevOp(bitc::MODULE_CODE_GLOBALVAR));
703     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,
704                               Log2_32_Ceil(MaxGlobalType+1)));
705     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));   // AddrSpace << 2
706                                                            //| explicitType << 1
707                                                            //| constant
708     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));   // Initializer.
709     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // Linkage.
710     if (MaxAlignment == 0)                                 // Alignment.
711       Abbv->Add(BitCodeAbbrevOp(0));
712     else {
713       unsigned MaxEncAlignment = Log2_32(MaxAlignment)+1;
714       Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,
715                                Log2_32_Ceil(MaxEncAlignment+1)));
716     }
717     if (SectionMap.empty())                                    // Section.
718       Abbv->Add(BitCodeAbbrevOp(0));
719     else
720       Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,
721                                Log2_32_Ceil(SectionMap.size()+1)));
722     // Don't bother emitting vis + thread local.
723     SimpleGVarAbbrev = Stream.EmitAbbrev(Abbv);
724   }
725 
726   // Emit the global variable information.
727   SmallVector<unsigned, 64> Vals;
728   for (const GlobalVariable &GV : M->globals()) {
729     unsigned AbbrevToUse = 0;
730 
731     // GLOBALVAR: [type, isconst, initid,
732     //             linkage, alignment, section, visibility, threadlocal,
733     //             unnamed_addr, externally_initialized, dllstorageclass,
734     //             comdat]
735     Vals.push_back(VE.getTypeID(GV.getValueType()));
736     Vals.push_back(GV.getType()->getAddressSpace() << 2 | 2 | GV.isConstant());
737     Vals.push_back(GV.isDeclaration() ? 0 :
738                    (VE.getValueID(GV.getInitializer()) + 1));
739     Vals.push_back(getEncodedLinkage(GV));
740     Vals.push_back(Log2_32(GV.getAlignment())+1);
741     Vals.push_back(GV.hasSection() ? SectionMap[GV.getSection()] : 0);
742     if (GV.isThreadLocal() ||
743         GV.getVisibility() != GlobalValue::DefaultVisibility ||
744         GV.hasUnnamedAddr() || GV.isExternallyInitialized() ||
745         GV.getDLLStorageClass() != GlobalValue::DefaultStorageClass ||
746         GV.hasComdat()) {
747       Vals.push_back(getEncodedVisibility(GV));
748       Vals.push_back(getEncodedThreadLocalMode(GV));
749       Vals.push_back(GV.hasUnnamedAddr());
750       Vals.push_back(GV.isExternallyInitialized());
751       Vals.push_back(getEncodedDLLStorageClass(GV));
752       Vals.push_back(GV.hasComdat() ? VE.getComdatID(GV.getComdat()) : 0);
753     } else {
754       AbbrevToUse = SimpleGVarAbbrev;
755     }
756 
757     Stream.EmitRecord(bitc::MODULE_CODE_GLOBALVAR, Vals, AbbrevToUse);
758     Vals.clear();
759   }
760 
761   // Emit the function proto information.
762   for (const Function &F : *M) {
763     // FUNCTION:  [type, callingconv, isproto, linkage, paramattrs, alignment,
764     //             section, visibility, gc, unnamed_addr, prologuedata,
765     //             dllstorageclass, comdat, prefixdata, personalityfn]
766     Vals.push_back(VE.getTypeID(F.getFunctionType()));
767     Vals.push_back(F.getCallingConv());
768     Vals.push_back(F.isDeclaration());
769     Vals.push_back(getEncodedLinkage(F));
770     Vals.push_back(VE.getAttributeID(F.getAttributes()));
771     Vals.push_back(Log2_32(F.getAlignment())+1);
772     Vals.push_back(F.hasSection() ? SectionMap[F.getSection()] : 0);
773     Vals.push_back(getEncodedVisibility(F));
774     Vals.push_back(F.hasGC() ? GCMap[F.getGC()] : 0);
775     Vals.push_back(F.hasUnnamedAddr());
776     Vals.push_back(F.hasPrologueData() ? (VE.getValueID(F.getPrologueData()) + 1)
777                                        : 0);
778     Vals.push_back(getEncodedDLLStorageClass(F));
779     Vals.push_back(F.hasComdat() ? VE.getComdatID(F.getComdat()) : 0);
780     Vals.push_back(F.hasPrefixData() ? (VE.getValueID(F.getPrefixData()) + 1)
781                                      : 0);
782     Vals.push_back(
783         F.hasPersonalityFn() ? (VE.getValueID(F.getPersonalityFn()) + 1) : 0);
784 
785     unsigned AbbrevToUse = 0;
786     Stream.EmitRecord(bitc::MODULE_CODE_FUNCTION, Vals, AbbrevToUse);
787     Vals.clear();
788   }
789 
790   // Emit the alias information.
791   for (const GlobalAlias &A : M->aliases()) {
792     // ALIAS: [alias type, aliasee val#, linkage, visibility]
793     Vals.push_back(VE.getTypeID(A.getValueType()));
794     Vals.push_back(A.getType()->getAddressSpace());
795     Vals.push_back(VE.getValueID(A.getAliasee()));
796     Vals.push_back(getEncodedLinkage(A));
797     Vals.push_back(getEncodedVisibility(A));
798     Vals.push_back(getEncodedDLLStorageClass(A));
799     Vals.push_back(getEncodedThreadLocalMode(A));
800     Vals.push_back(A.hasUnnamedAddr());
801     unsigned AbbrevToUse = 0;
802     Stream.EmitRecord(bitc::MODULE_CODE_ALIAS, Vals, AbbrevToUse);
803     Vals.clear();
804   }
805 
806   // Emit the module's source file name.
807   {
808     StringEncoding Bits = getStringEncoding(M->getSourceFileName().data(),
809                                             M->getSourceFileName().size());
810     BitCodeAbbrevOp AbbrevOpToUse = BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 8);
811     if (Bits == SE_Char6)
812       AbbrevOpToUse = BitCodeAbbrevOp(BitCodeAbbrevOp::Char6);
813     else if (Bits == SE_Fixed7)
814       AbbrevOpToUse = BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 7);
815 
816     // MODULE_CODE_SOURCE_FILENAME: [namechar x N]
817     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
818     Abbv->Add(BitCodeAbbrevOp(bitc::MODULE_CODE_SOURCE_FILENAME));
819     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
820     Abbv->Add(AbbrevOpToUse);
821     unsigned FilenameAbbrev = Stream.EmitAbbrev(Abbv);
822 
823     for (const auto P : M->getSourceFileName())
824       Vals.push_back((unsigned char)P);
825 
826     // Emit the finished record.
827     Stream.EmitRecord(bitc::MODULE_CODE_SOURCE_FILENAME, Vals, FilenameAbbrev);
828     Vals.clear();
829   }
830 
831   // If we have a VST, write the VSTOFFSET record placeholder and return
832   // its offset.
833   if (M->getValueSymbolTable().empty())
834     return 0;
835   return WriteValueSymbolTableForwardDecl(Stream);
836 }
837 
838 static uint64_t GetOptimizationFlags(const Value *V) {
839   uint64_t Flags = 0;
840 
841   if (const auto *OBO = dyn_cast<OverflowingBinaryOperator>(V)) {
842     if (OBO->hasNoSignedWrap())
843       Flags |= 1 << bitc::OBO_NO_SIGNED_WRAP;
844     if (OBO->hasNoUnsignedWrap())
845       Flags |= 1 << bitc::OBO_NO_UNSIGNED_WRAP;
846   } else if (const auto *PEO = dyn_cast<PossiblyExactOperator>(V)) {
847     if (PEO->isExact())
848       Flags |= 1 << bitc::PEO_EXACT;
849   } else if (const auto *FPMO = dyn_cast<FPMathOperator>(V)) {
850     if (FPMO->hasUnsafeAlgebra())
851       Flags |= FastMathFlags::UnsafeAlgebra;
852     if (FPMO->hasNoNaNs())
853       Flags |= FastMathFlags::NoNaNs;
854     if (FPMO->hasNoInfs())
855       Flags |= FastMathFlags::NoInfs;
856     if (FPMO->hasNoSignedZeros())
857       Flags |= FastMathFlags::NoSignedZeros;
858     if (FPMO->hasAllowReciprocal())
859       Flags |= FastMathFlags::AllowReciprocal;
860   }
861 
862   return Flags;
863 }
864 
865 static void WriteValueAsMetadata(const ValueAsMetadata *MD,
866                                  const ValueEnumerator &VE,
867                                  BitstreamWriter &Stream,
868                                  SmallVectorImpl<uint64_t> &Record) {
869   // Mimic an MDNode with a value as one operand.
870   Value *V = MD->getValue();
871   Record.push_back(VE.getTypeID(V->getType()));
872   Record.push_back(VE.getValueID(V));
873   Stream.EmitRecord(bitc::METADATA_VALUE, Record, 0);
874   Record.clear();
875 }
876 
877 static void WriteMDTuple(const MDTuple *N, const ValueEnumerator &VE,
878                          BitstreamWriter &Stream,
879                          SmallVectorImpl<uint64_t> &Record, unsigned Abbrev) {
880   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
881     Metadata *MD = N->getOperand(i);
882     assert(!(MD && isa<LocalAsMetadata>(MD)) &&
883            "Unexpected function-local metadata");
884     Record.push_back(VE.getMetadataOrNullID(MD));
885   }
886   Stream.EmitRecord(N->isDistinct() ? bitc::METADATA_DISTINCT_NODE
887                                     : bitc::METADATA_NODE,
888                     Record, Abbrev);
889   Record.clear();
890 }
891 
892 static unsigned createDILocationAbbrev(BitstreamWriter &Stream) {
893   // Assume the column is usually under 128, and always output the inlined-at
894   // location (it's never more expensive than building an array size 1).
895   BitCodeAbbrev *Abbv = new BitCodeAbbrev();
896   Abbv->Add(BitCodeAbbrevOp(bitc::METADATA_LOCATION));
897   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1));
898   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));
899   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
900   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));
901   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));
902   return Stream.EmitAbbrev(Abbv);
903 }
904 
905 static void WriteDILocation(const DILocation *N, const ValueEnumerator &VE,
906                             BitstreamWriter &Stream,
907                             SmallVectorImpl<uint64_t> &Record,
908                             unsigned &Abbrev) {
909   if (!Abbrev)
910     Abbrev = createDILocationAbbrev(Stream);
911 
912   Record.push_back(N->isDistinct());
913   Record.push_back(N->getLine());
914   Record.push_back(N->getColumn());
915   Record.push_back(VE.getMetadataID(N->getScope()));
916   Record.push_back(VE.getMetadataOrNullID(N->getInlinedAt()));
917 
918   Stream.EmitRecord(bitc::METADATA_LOCATION, Record, Abbrev);
919   Record.clear();
920 }
921 
922 static unsigned createGenericDINodeAbbrev(BitstreamWriter &Stream) {
923   // Assume the column is usually under 128, and always output the inlined-at
924   // location (it's never more expensive than building an array size 1).
925   BitCodeAbbrev *Abbv = new BitCodeAbbrev();
926   Abbv->Add(BitCodeAbbrevOp(bitc::METADATA_GENERIC_DEBUG));
927   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1));
928   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));
929   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1));
930   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));
931   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
932   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));
933   return Stream.EmitAbbrev(Abbv);
934 }
935 
936 static void WriteGenericDINode(const GenericDINode *N,
937                                const ValueEnumerator &VE,
938                                BitstreamWriter &Stream,
939                                SmallVectorImpl<uint64_t> &Record,
940                                unsigned &Abbrev) {
941   if (!Abbrev)
942     Abbrev = createGenericDINodeAbbrev(Stream);
943 
944   Record.push_back(N->isDistinct());
945   Record.push_back(N->getTag());
946   Record.push_back(0); // Per-tag version field; unused for now.
947 
948   for (auto &I : N->operands())
949     Record.push_back(VE.getMetadataOrNullID(I));
950 
951   Stream.EmitRecord(bitc::METADATA_GENERIC_DEBUG, Record, Abbrev);
952   Record.clear();
953 }
954 
955 static uint64_t rotateSign(int64_t I) {
956   uint64_t U = I;
957   return I < 0 ? ~(U << 1) : U << 1;
958 }
959 
960 static void WriteDISubrange(const DISubrange *N, const ValueEnumerator &,
961                             BitstreamWriter &Stream,
962                             SmallVectorImpl<uint64_t> &Record,
963                             unsigned Abbrev) {
964   Record.push_back(N->isDistinct());
965   Record.push_back(N->getCount());
966   Record.push_back(rotateSign(N->getLowerBound()));
967 
968   Stream.EmitRecord(bitc::METADATA_SUBRANGE, Record, Abbrev);
969   Record.clear();
970 }
971 
972 static void WriteDIEnumerator(const DIEnumerator *N, const ValueEnumerator &VE,
973                               BitstreamWriter &Stream,
974                               SmallVectorImpl<uint64_t> &Record,
975                               unsigned Abbrev) {
976   Record.push_back(N->isDistinct());
977   Record.push_back(rotateSign(N->getValue()));
978   Record.push_back(VE.getMetadataOrNullID(N->getRawName()));
979 
980   Stream.EmitRecord(bitc::METADATA_ENUMERATOR, Record, Abbrev);
981   Record.clear();
982 }
983 
984 static void WriteDIBasicType(const DIBasicType *N, const ValueEnumerator &VE,
985                              BitstreamWriter &Stream,
986                              SmallVectorImpl<uint64_t> &Record,
987                              unsigned Abbrev) {
988   Record.push_back(N->isDistinct());
989   Record.push_back(N->getTag());
990   Record.push_back(VE.getMetadataOrNullID(N->getRawName()));
991   Record.push_back(N->getSizeInBits());
992   Record.push_back(N->getAlignInBits());
993   Record.push_back(N->getEncoding());
994 
995   Stream.EmitRecord(bitc::METADATA_BASIC_TYPE, Record, Abbrev);
996   Record.clear();
997 }
998 
999 static void WriteDIDerivedType(const DIDerivedType *N,
1000                                const ValueEnumerator &VE,
1001                                BitstreamWriter &Stream,
1002                                SmallVectorImpl<uint64_t> &Record,
1003                                unsigned Abbrev) {
1004   Record.push_back(N->isDistinct());
1005   Record.push_back(N->getTag());
1006   Record.push_back(VE.getMetadataOrNullID(N->getRawName()));
1007   Record.push_back(VE.getMetadataOrNullID(N->getFile()));
1008   Record.push_back(N->getLine());
1009   Record.push_back(VE.getMetadataOrNullID(N->getScope()));
1010   Record.push_back(VE.getMetadataOrNullID(N->getBaseType()));
1011   Record.push_back(N->getSizeInBits());
1012   Record.push_back(N->getAlignInBits());
1013   Record.push_back(N->getOffsetInBits());
1014   Record.push_back(N->getFlags());
1015   Record.push_back(VE.getMetadataOrNullID(N->getExtraData()));
1016 
1017   Stream.EmitRecord(bitc::METADATA_DERIVED_TYPE, Record, Abbrev);
1018   Record.clear();
1019 }
1020 
1021 static void WriteDICompositeType(const DICompositeType *N,
1022                                  const ValueEnumerator &VE,
1023                                  BitstreamWriter &Stream,
1024                                  SmallVectorImpl<uint64_t> &Record,
1025                                  unsigned Abbrev) {
1026   Record.push_back(N->isDistinct());
1027   Record.push_back(N->getTag());
1028   Record.push_back(VE.getMetadataOrNullID(N->getRawName()));
1029   Record.push_back(VE.getMetadataOrNullID(N->getFile()));
1030   Record.push_back(N->getLine());
1031   Record.push_back(VE.getMetadataOrNullID(N->getScope()));
1032   Record.push_back(VE.getMetadataOrNullID(N->getBaseType()));
1033   Record.push_back(N->getSizeInBits());
1034   Record.push_back(N->getAlignInBits());
1035   Record.push_back(N->getOffsetInBits());
1036   Record.push_back(N->getFlags());
1037   Record.push_back(VE.getMetadataOrNullID(N->getElements().get()));
1038   Record.push_back(N->getRuntimeLang());
1039   Record.push_back(VE.getMetadataOrNullID(N->getVTableHolder()));
1040   Record.push_back(VE.getMetadataOrNullID(N->getTemplateParams().get()));
1041   Record.push_back(VE.getMetadataOrNullID(N->getRawIdentifier()));
1042 
1043   Stream.EmitRecord(bitc::METADATA_COMPOSITE_TYPE, Record, Abbrev);
1044   Record.clear();
1045 }
1046 
1047 static void WriteDISubroutineType(const DISubroutineType *N,
1048                                   const ValueEnumerator &VE,
1049                                   BitstreamWriter &Stream,
1050                                   SmallVectorImpl<uint64_t> &Record,
1051                                   unsigned Abbrev) {
1052   Record.push_back(N->isDistinct());
1053   Record.push_back(N->getFlags());
1054   Record.push_back(VE.getMetadataOrNullID(N->getTypeArray().get()));
1055 
1056   Stream.EmitRecord(bitc::METADATA_SUBROUTINE_TYPE, Record, Abbrev);
1057   Record.clear();
1058 }
1059 
1060 static void WriteDIFile(const DIFile *N, const ValueEnumerator &VE,
1061                         BitstreamWriter &Stream,
1062                         SmallVectorImpl<uint64_t> &Record, unsigned Abbrev) {
1063   Record.push_back(N->isDistinct());
1064   Record.push_back(VE.getMetadataOrNullID(N->getRawFilename()));
1065   Record.push_back(VE.getMetadataOrNullID(N->getRawDirectory()));
1066 
1067   Stream.EmitRecord(bitc::METADATA_FILE, Record, Abbrev);
1068   Record.clear();
1069 }
1070 
1071 static void WriteDICompileUnit(const DICompileUnit *N,
1072                                const ValueEnumerator &VE,
1073                                BitstreamWriter &Stream,
1074                                SmallVectorImpl<uint64_t> &Record,
1075                                unsigned Abbrev) {
1076   assert(N->isDistinct() && "Expected distinct compile units");
1077   Record.push_back(/* IsDistinct */ true);
1078   Record.push_back(N->getSourceLanguage());
1079   Record.push_back(VE.getMetadataOrNullID(N->getFile()));
1080   Record.push_back(VE.getMetadataOrNullID(N->getRawProducer()));
1081   Record.push_back(N->isOptimized());
1082   Record.push_back(VE.getMetadataOrNullID(N->getRawFlags()));
1083   Record.push_back(N->getRuntimeVersion());
1084   Record.push_back(VE.getMetadataOrNullID(N->getRawSplitDebugFilename()));
1085   Record.push_back(N->getEmissionKind());
1086   Record.push_back(VE.getMetadataOrNullID(N->getEnumTypes().get()));
1087   Record.push_back(VE.getMetadataOrNullID(N->getRetainedTypes().get()));
1088   Record.push_back(VE.getMetadataOrNullID(N->getSubprograms().get()));
1089   Record.push_back(VE.getMetadataOrNullID(N->getGlobalVariables().get()));
1090   Record.push_back(VE.getMetadataOrNullID(N->getImportedEntities().get()));
1091   Record.push_back(N->getDWOId());
1092   Record.push_back(VE.getMetadataOrNullID(N->getMacros().get()));
1093 
1094   Stream.EmitRecord(bitc::METADATA_COMPILE_UNIT, Record, Abbrev);
1095   Record.clear();
1096 }
1097 
1098 static void WriteDISubprogram(const DISubprogram *N, const ValueEnumerator &VE,
1099                               BitstreamWriter &Stream,
1100                               SmallVectorImpl<uint64_t> &Record,
1101                               unsigned Abbrev) {
1102   Record.push_back(N->isDistinct());
1103   Record.push_back(VE.getMetadataOrNullID(N->getScope()));
1104   Record.push_back(VE.getMetadataOrNullID(N->getRawName()));
1105   Record.push_back(VE.getMetadataOrNullID(N->getRawLinkageName()));
1106   Record.push_back(VE.getMetadataOrNullID(N->getFile()));
1107   Record.push_back(N->getLine());
1108   Record.push_back(VE.getMetadataOrNullID(N->getType()));
1109   Record.push_back(N->isLocalToUnit());
1110   Record.push_back(N->isDefinition());
1111   Record.push_back(N->getScopeLine());
1112   Record.push_back(VE.getMetadataOrNullID(N->getContainingType()));
1113   Record.push_back(N->getVirtuality());
1114   Record.push_back(N->getVirtualIndex());
1115   Record.push_back(N->getFlags());
1116   Record.push_back(N->isOptimized());
1117   Record.push_back(VE.getMetadataOrNullID(N->getTemplateParams().get()));
1118   Record.push_back(VE.getMetadataOrNullID(N->getDeclaration()));
1119   Record.push_back(VE.getMetadataOrNullID(N->getVariables().get()));
1120 
1121   Stream.EmitRecord(bitc::METADATA_SUBPROGRAM, Record, Abbrev);
1122   Record.clear();
1123 }
1124 
1125 static void WriteDILexicalBlock(const DILexicalBlock *N,
1126                                 const ValueEnumerator &VE,
1127                                 BitstreamWriter &Stream,
1128                                 SmallVectorImpl<uint64_t> &Record,
1129                                 unsigned Abbrev) {
1130   Record.push_back(N->isDistinct());
1131   Record.push_back(VE.getMetadataOrNullID(N->getScope()));
1132   Record.push_back(VE.getMetadataOrNullID(N->getFile()));
1133   Record.push_back(N->getLine());
1134   Record.push_back(N->getColumn());
1135 
1136   Stream.EmitRecord(bitc::METADATA_LEXICAL_BLOCK, Record, Abbrev);
1137   Record.clear();
1138 }
1139 
1140 static void WriteDILexicalBlockFile(const DILexicalBlockFile *N,
1141                                     const ValueEnumerator &VE,
1142                                     BitstreamWriter &Stream,
1143                                     SmallVectorImpl<uint64_t> &Record,
1144                                     unsigned Abbrev) {
1145   Record.push_back(N->isDistinct());
1146   Record.push_back(VE.getMetadataOrNullID(N->getScope()));
1147   Record.push_back(VE.getMetadataOrNullID(N->getFile()));
1148   Record.push_back(N->getDiscriminator());
1149 
1150   Stream.EmitRecord(bitc::METADATA_LEXICAL_BLOCK_FILE, Record, Abbrev);
1151   Record.clear();
1152 }
1153 
1154 static void WriteDINamespace(const DINamespace *N, const ValueEnumerator &VE,
1155                              BitstreamWriter &Stream,
1156                              SmallVectorImpl<uint64_t> &Record,
1157                              unsigned Abbrev) {
1158   Record.push_back(N->isDistinct());
1159   Record.push_back(VE.getMetadataOrNullID(N->getScope()));
1160   Record.push_back(VE.getMetadataOrNullID(N->getFile()));
1161   Record.push_back(VE.getMetadataOrNullID(N->getRawName()));
1162   Record.push_back(N->getLine());
1163 
1164   Stream.EmitRecord(bitc::METADATA_NAMESPACE, Record, Abbrev);
1165   Record.clear();
1166 }
1167 
1168 static void WriteDIMacro(const DIMacro *N, const ValueEnumerator &VE,
1169                          BitstreamWriter &Stream,
1170                          SmallVectorImpl<uint64_t> &Record, unsigned Abbrev) {
1171   Record.push_back(N->isDistinct());
1172   Record.push_back(N->getMacinfoType());
1173   Record.push_back(N->getLine());
1174   Record.push_back(VE.getMetadataOrNullID(N->getRawName()));
1175   Record.push_back(VE.getMetadataOrNullID(N->getRawValue()));
1176 
1177   Stream.EmitRecord(bitc::METADATA_MACRO, Record, Abbrev);
1178   Record.clear();
1179 }
1180 
1181 static void WriteDIMacroFile(const DIMacroFile *N, const ValueEnumerator &VE,
1182                              BitstreamWriter &Stream,
1183                              SmallVectorImpl<uint64_t> &Record,
1184                              unsigned Abbrev) {
1185   Record.push_back(N->isDistinct());
1186   Record.push_back(N->getMacinfoType());
1187   Record.push_back(N->getLine());
1188   Record.push_back(VE.getMetadataOrNullID(N->getFile()));
1189   Record.push_back(VE.getMetadataOrNullID(N->getElements().get()));
1190 
1191   Stream.EmitRecord(bitc::METADATA_MACRO_FILE, Record, Abbrev);
1192   Record.clear();
1193 }
1194 
1195 static void WriteDIModule(const DIModule *N, const ValueEnumerator &VE,
1196                           BitstreamWriter &Stream,
1197                           SmallVectorImpl<uint64_t> &Record, unsigned Abbrev) {
1198   Record.push_back(N->isDistinct());
1199   for (auto &I : N->operands())
1200     Record.push_back(VE.getMetadataOrNullID(I));
1201 
1202   Stream.EmitRecord(bitc::METADATA_MODULE, Record, Abbrev);
1203   Record.clear();
1204 }
1205 
1206 static void WriteDITemplateTypeParameter(const DITemplateTypeParameter *N,
1207                                          const ValueEnumerator &VE,
1208                                          BitstreamWriter &Stream,
1209                                          SmallVectorImpl<uint64_t> &Record,
1210                                          unsigned Abbrev) {
1211   Record.push_back(N->isDistinct());
1212   Record.push_back(VE.getMetadataOrNullID(N->getRawName()));
1213   Record.push_back(VE.getMetadataOrNullID(N->getType()));
1214 
1215   Stream.EmitRecord(bitc::METADATA_TEMPLATE_TYPE, Record, Abbrev);
1216   Record.clear();
1217 }
1218 
1219 static void WriteDITemplateValueParameter(const DITemplateValueParameter *N,
1220                                           const ValueEnumerator &VE,
1221                                           BitstreamWriter &Stream,
1222                                           SmallVectorImpl<uint64_t> &Record,
1223                                           unsigned Abbrev) {
1224   Record.push_back(N->isDistinct());
1225   Record.push_back(N->getTag());
1226   Record.push_back(VE.getMetadataOrNullID(N->getRawName()));
1227   Record.push_back(VE.getMetadataOrNullID(N->getType()));
1228   Record.push_back(VE.getMetadataOrNullID(N->getValue()));
1229 
1230   Stream.EmitRecord(bitc::METADATA_TEMPLATE_VALUE, Record, Abbrev);
1231   Record.clear();
1232 }
1233 
1234 static void WriteDIGlobalVariable(const DIGlobalVariable *N,
1235                                   const ValueEnumerator &VE,
1236                                   BitstreamWriter &Stream,
1237                                   SmallVectorImpl<uint64_t> &Record,
1238                                   unsigned Abbrev) {
1239   Record.push_back(N->isDistinct());
1240   Record.push_back(VE.getMetadataOrNullID(N->getScope()));
1241   Record.push_back(VE.getMetadataOrNullID(N->getRawName()));
1242   Record.push_back(VE.getMetadataOrNullID(N->getRawLinkageName()));
1243   Record.push_back(VE.getMetadataOrNullID(N->getFile()));
1244   Record.push_back(N->getLine());
1245   Record.push_back(VE.getMetadataOrNullID(N->getType()));
1246   Record.push_back(N->isLocalToUnit());
1247   Record.push_back(N->isDefinition());
1248   Record.push_back(VE.getMetadataOrNullID(N->getRawVariable()));
1249   Record.push_back(VE.getMetadataOrNullID(N->getStaticDataMemberDeclaration()));
1250 
1251   Stream.EmitRecord(bitc::METADATA_GLOBAL_VAR, Record, Abbrev);
1252   Record.clear();
1253 }
1254 
1255 static void WriteDILocalVariable(const DILocalVariable *N,
1256                                  const ValueEnumerator &VE,
1257                                  BitstreamWriter &Stream,
1258                                  SmallVectorImpl<uint64_t> &Record,
1259                                  unsigned Abbrev) {
1260   Record.push_back(N->isDistinct());
1261   Record.push_back(VE.getMetadataOrNullID(N->getScope()));
1262   Record.push_back(VE.getMetadataOrNullID(N->getRawName()));
1263   Record.push_back(VE.getMetadataOrNullID(N->getFile()));
1264   Record.push_back(N->getLine());
1265   Record.push_back(VE.getMetadataOrNullID(N->getType()));
1266   Record.push_back(N->getArg());
1267   Record.push_back(N->getFlags());
1268 
1269   Stream.EmitRecord(bitc::METADATA_LOCAL_VAR, Record, Abbrev);
1270   Record.clear();
1271 }
1272 
1273 static void WriteDIExpression(const DIExpression *N, const ValueEnumerator &,
1274                               BitstreamWriter &Stream,
1275                               SmallVectorImpl<uint64_t> &Record,
1276                               unsigned Abbrev) {
1277   Record.reserve(N->getElements().size() + 1);
1278 
1279   Record.push_back(N->isDistinct());
1280   Record.append(N->elements_begin(), N->elements_end());
1281 
1282   Stream.EmitRecord(bitc::METADATA_EXPRESSION, Record, Abbrev);
1283   Record.clear();
1284 }
1285 
1286 static void WriteDIObjCProperty(const DIObjCProperty *N,
1287                                 const ValueEnumerator &VE,
1288                                 BitstreamWriter &Stream,
1289                                 SmallVectorImpl<uint64_t> &Record,
1290                                 unsigned Abbrev) {
1291   Record.push_back(N->isDistinct());
1292   Record.push_back(VE.getMetadataOrNullID(N->getRawName()));
1293   Record.push_back(VE.getMetadataOrNullID(N->getFile()));
1294   Record.push_back(N->getLine());
1295   Record.push_back(VE.getMetadataOrNullID(N->getRawSetterName()));
1296   Record.push_back(VE.getMetadataOrNullID(N->getRawGetterName()));
1297   Record.push_back(N->getAttributes());
1298   Record.push_back(VE.getMetadataOrNullID(N->getType()));
1299 
1300   Stream.EmitRecord(bitc::METADATA_OBJC_PROPERTY, Record, Abbrev);
1301   Record.clear();
1302 }
1303 
1304 static void WriteDIImportedEntity(const DIImportedEntity *N,
1305                                   const ValueEnumerator &VE,
1306                                   BitstreamWriter &Stream,
1307                                   SmallVectorImpl<uint64_t> &Record,
1308                                   unsigned Abbrev) {
1309   Record.push_back(N->isDistinct());
1310   Record.push_back(N->getTag());
1311   Record.push_back(VE.getMetadataOrNullID(N->getScope()));
1312   Record.push_back(VE.getMetadataOrNullID(N->getEntity()));
1313   Record.push_back(N->getLine());
1314   Record.push_back(VE.getMetadataOrNullID(N->getRawName()));
1315 
1316   Stream.EmitRecord(bitc::METADATA_IMPORTED_ENTITY, Record, Abbrev);
1317   Record.clear();
1318 }
1319 
1320 static unsigned createNamedMetadataAbbrev(BitstreamWriter &Stream) {
1321   BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1322   Abbv->Add(BitCodeAbbrevOp(bitc::METADATA_NAME));
1323   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
1324   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 8));
1325   return Stream.EmitAbbrev(Abbv);
1326 }
1327 
1328 static void writeNamedMetadata(const Module &M, const ValueEnumerator &VE,
1329                                BitstreamWriter &Stream,
1330                                SmallVectorImpl<uint64_t> &Record) {
1331   if (M.named_metadata_empty())
1332     return;
1333 
1334   unsigned Abbrev = createNamedMetadataAbbrev(Stream);
1335   for (const NamedMDNode &NMD : M.named_metadata()) {
1336     // Write name.
1337     StringRef Str = NMD.getName();
1338     Record.append(Str.bytes_begin(), Str.bytes_end());
1339     Stream.EmitRecord(bitc::METADATA_NAME, Record, Abbrev);
1340     Record.clear();
1341 
1342     // Write named metadata operands.
1343     for (const MDNode *N : NMD.operands())
1344       Record.push_back(VE.getMetadataID(N));
1345     Stream.EmitRecord(bitc::METADATA_NAMED_NODE, Record, 0);
1346     Record.clear();
1347   }
1348 }
1349 
1350 static unsigned createMetadataStringsAbbrev(BitstreamWriter &Stream) {
1351   BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1352   Abbv->Add(BitCodeAbbrevOp(bitc::METADATA_STRINGS));
1353   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // # of strings
1354   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // offset to chars
1355   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Blob));
1356   return Stream.EmitAbbrev(Abbv);
1357 }
1358 
1359 /// Write out a record for MDString.
1360 ///
1361 /// All the metadata strings in a metadata block are emitted in a single
1362 /// record.  The sizes and strings themselves are shoved into a blob.
1363 static void writeMetadataStrings(ArrayRef<const Metadata *> Strings,
1364                                  BitstreamWriter &Stream,
1365                                  SmallVectorImpl<uint64_t> &Record) {
1366   if (Strings.empty())
1367     return;
1368 
1369   // Start the record with the number of strings.
1370   Record.push_back(bitc::METADATA_STRINGS);
1371   Record.push_back(Strings.size());
1372 
1373   // Emit the sizes of the strings in the blob.
1374   SmallString<256> Blob;
1375   {
1376     BitstreamWriter W(Blob);
1377     for (const Metadata *MD : Strings)
1378       W.EmitVBR(cast<MDString>(MD)->getLength(), 6);
1379     W.FlushToWord();
1380   }
1381 
1382   // Add the offset to the strings to the record.
1383   Record.push_back(Blob.size());
1384 
1385   // Add the strings to the blob.
1386   for (const Metadata *MD : Strings)
1387     Blob.append(cast<MDString>(MD)->getString());
1388 
1389   // Emit the final record.
1390   Stream.EmitRecordWithBlob(createMetadataStringsAbbrev(Stream), Record, Blob);
1391   Record.clear();
1392 }
1393 
1394 static void WriteModuleMetadata(const Module &M,
1395                                 const ValueEnumerator &VE,
1396                                 BitstreamWriter &Stream) {
1397   if (VE.getMDs().empty() && M.named_metadata_empty())
1398     return;
1399 
1400   Stream.EnterSubblock(bitc::METADATA_BLOCK_ID, 3);
1401 
1402   // Initialize MDNode abbreviations.
1403 #define HANDLE_MDNODE_LEAF(CLASS) unsigned CLASS##Abbrev = 0;
1404 #include "llvm/IR/Metadata.def"
1405 
1406   SmallVector<uint64_t, 64> Record;
1407   writeMetadataStrings(VE.getMDStrings(), Stream, Record);
1408   for (const Metadata *MD : VE.getNonMDStrings()) {
1409     if (const MDNode *N = dyn_cast<MDNode>(MD)) {
1410       assert(N->isResolved() && "Expected forward references to be resolved");
1411 
1412       switch (N->getMetadataID()) {
1413       default:
1414         llvm_unreachable("Invalid MDNode subclass");
1415 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
1416   case Metadata::CLASS##Kind:                                                  \
1417     Write##CLASS(cast<CLASS>(N), VE, Stream, Record, CLASS##Abbrev);           \
1418     continue;
1419 #include "llvm/IR/Metadata.def"
1420       }
1421     }
1422     WriteValueAsMetadata(cast<ConstantAsMetadata>(MD), VE, Stream, Record);
1423   }
1424 
1425   writeNamedMetadata(M, VE, Stream, Record);
1426   Stream.ExitBlock();
1427 }
1428 
1429 static void WriteFunctionLocalMetadata(const Function &F,
1430                                        const ValueEnumerator &VE,
1431                                        BitstreamWriter &Stream) {
1432   bool StartedMetadataBlock = false;
1433   SmallVector<uint64_t, 64> Record;
1434   for (const Metadata *MD : VE.getFunctionMDs()) {
1435     auto *Local = cast<LocalAsMetadata>(MD);
1436     if (!StartedMetadataBlock) {
1437       Stream.EnterSubblock(bitc::METADATA_BLOCK_ID, 3);
1438       StartedMetadataBlock = true;
1439     }
1440     WriteValueAsMetadata(Local, VE, Stream, Record);
1441   }
1442 
1443   if (StartedMetadataBlock)
1444     Stream.ExitBlock();
1445 }
1446 
1447 static void WriteMetadataAttachment(const Function &F,
1448                                     const ValueEnumerator &VE,
1449                                     BitstreamWriter &Stream) {
1450   Stream.EnterSubblock(bitc::METADATA_ATTACHMENT_ID, 3);
1451 
1452   SmallVector<uint64_t, 64> Record;
1453 
1454   // Write metadata attachments
1455   // METADATA_ATTACHMENT - [m x [value, [n x [id, mdnode]]]
1456   SmallVector<std::pair<unsigned, MDNode *>, 4> MDs;
1457   F.getAllMetadata(MDs);
1458   if (!MDs.empty()) {
1459     for (const auto &I : MDs) {
1460       Record.push_back(I.first);
1461       Record.push_back(VE.getMetadataID(I.second));
1462     }
1463     Stream.EmitRecord(bitc::METADATA_ATTACHMENT, Record, 0);
1464     Record.clear();
1465   }
1466 
1467   for (const BasicBlock &BB : F)
1468     for (const Instruction &I : BB) {
1469       MDs.clear();
1470       I.getAllMetadataOtherThanDebugLoc(MDs);
1471 
1472       // If no metadata, ignore instruction.
1473       if (MDs.empty()) continue;
1474 
1475       Record.push_back(VE.getInstructionID(&I));
1476 
1477       for (unsigned i = 0, e = MDs.size(); i != e; ++i) {
1478         Record.push_back(MDs[i].first);
1479         Record.push_back(VE.getMetadataID(MDs[i].second));
1480       }
1481       Stream.EmitRecord(bitc::METADATA_ATTACHMENT, Record, 0);
1482       Record.clear();
1483     }
1484 
1485   Stream.ExitBlock();
1486 }
1487 
1488 static void WriteModuleMetadataStore(const Module *M, BitstreamWriter &Stream) {
1489   SmallVector<uint64_t, 64> Record;
1490 
1491   // Write metadata kinds
1492   // METADATA_KIND - [n x [id, name]]
1493   SmallVector<StringRef, 8> Names;
1494   M->getMDKindNames(Names);
1495 
1496   if (Names.empty()) return;
1497 
1498   Stream.EnterSubblock(bitc::METADATA_KIND_BLOCK_ID, 3);
1499 
1500   for (unsigned MDKindID = 0, e = Names.size(); MDKindID != e; ++MDKindID) {
1501     Record.push_back(MDKindID);
1502     StringRef KName = Names[MDKindID];
1503     Record.append(KName.begin(), KName.end());
1504 
1505     Stream.EmitRecord(bitc::METADATA_KIND, Record, 0);
1506     Record.clear();
1507   }
1508 
1509   Stream.ExitBlock();
1510 }
1511 
1512 static void WriteOperandBundleTags(const Module *M, BitstreamWriter &Stream) {
1513   // Write metadata kinds
1514   //
1515   // OPERAND_BUNDLE_TAGS_BLOCK_ID : N x OPERAND_BUNDLE_TAG
1516   //
1517   // OPERAND_BUNDLE_TAG - [strchr x N]
1518 
1519   SmallVector<StringRef, 8> Tags;
1520   M->getOperandBundleTags(Tags);
1521 
1522   if (Tags.empty())
1523     return;
1524 
1525   Stream.EnterSubblock(bitc::OPERAND_BUNDLE_TAGS_BLOCK_ID, 3);
1526 
1527   SmallVector<uint64_t, 64> Record;
1528 
1529   for (auto Tag : Tags) {
1530     Record.append(Tag.begin(), Tag.end());
1531 
1532     Stream.EmitRecord(bitc::OPERAND_BUNDLE_TAG, Record, 0);
1533     Record.clear();
1534   }
1535 
1536   Stream.ExitBlock();
1537 }
1538 
1539 static void emitSignedInt64(SmallVectorImpl<uint64_t> &Vals, uint64_t V) {
1540   if ((int64_t)V >= 0)
1541     Vals.push_back(V << 1);
1542   else
1543     Vals.push_back((-V << 1) | 1);
1544 }
1545 
1546 static void WriteConstants(unsigned FirstVal, unsigned LastVal,
1547                            const ValueEnumerator &VE,
1548                            BitstreamWriter &Stream, bool isGlobal) {
1549   if (FirstVal == LastVal) return;
1550 
1551   Stream.EnterSubblock(bitc::CONSTANTS_BLOCK_ID, 4);
1552 
1553   unsigned AggregateAbbrev = 0;
1554   unsigned String8Abbrev = 0;
1555   unsigned CString7Abbrev = 0;
1556   unsigned CString6Abbrev = 0;
1557   // If this is a constant pool for the module, emit module-specific abbrevs.
1558   if (isGlobal) {
1559     // Abbrev for CST_CODE_AGGREGATE.
1560     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1561     Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_AGGREGATE));
1562     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
1563     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, Log2_32_Ceil(LastVal+1)));
1564     AggregateAbbrev = Stream.EmitAbbrev(Abbv);
1565 
1566     // Abbrev for CST_CODE_STRING.
1567     Abbv = new BitCodeAbbrev();
1568     Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_STRING));
1569     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
1570     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 8));
1571     String8Abbrev = Stream.EmitAbbrev(Abbv);
1572     // Abbrev for CST_CODE_CSTRING.
1573     Abbv = new BitCodeAbbrev();
1574     Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_CSTRING));
1575     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
1576     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 7));
1577     CString7Abbrev = Stream.EmitAbbrev(Abbv);
1578     // Abbrev for CST_CODE_CSTRING.
1579     Abbv = new BitCodeAbbrev();
1580     Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_CSTRING));
1581     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
1582     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Char6));
1583     CString6Abbrev = Stream.EmitAbbrev(Abbv);
1584   }
1585 
1586   SmallVector<uint64_t, 64> Record;
1587 
1588   const ValueEnumerator::ValueList &Vals = VE.getValues();
1589   Type *LastTy = nullptr;
1590   for (unsigned i = FirstVal; i != LastVal; ++i) {
1591     const Value *V = Vals[i].first;
1592     // If we need to switch types, do so now.
1593     if (V->getType() != LastTy) {
1594       LastTy = V->getType();
1595       Record.push_back(VE.getTypeID(LastTy));
1596       Stream.EmitRecord(bitc::CST_CODE_SETTYPE, Record,
1597                         CONSTANTS_SETTYPE_ABBREV);
1598       Record.clear();
1599     }
1600 
1601     if (const InlineAsm *IA = dyn_cast<InlineAsm>(V)) {
1602       Record.push_back(unsigned(IA->hasSideEffects()) |
1603                        unsigned(IA->isAlignStack()) << 1 |
1604                        unsigned(IA->getDialect()&1) << 2);
1605 
1606       // Add the asm string.
1607       const std::string &AsmStr = IA->getAsmString();
1608       Record.push_back(AsmStr.size());
1609       Record.append(AsmStr.begin(), AsmStr.end());
1610 
1611       // Add the constraint string.
1612       const std::string &ConstraintStr = IA->getConstraintString();
1613       Record.push_back(ConstraintStr.size());
1614       Record.append(ConstraintStr.begin(), ConstraintStr.end());
1615       Stream.EmitRecord(bitc::CST_CODE_INLINEASM, Record);
1616       Record.clear();
1617       continue;
1618     }
1619     const Constant *C = cast<Constant>(V);
1620     unsigned Code = -1U;
1621     unsigned AbbrevToUse = 0;
1622     if (C->isNullValue()) {
1623       Code = bitc::CST_CODE_NULL;
1624     } else if (isa<UndefValue>(C)) {
1625       Code = bitc::CST_CODE_UNDEF;
1626     } else if (const ConstantInt *IV = dyn_cast<ConstantInt>(C)) {
1627       if (IV->getBitWidth() <= 64) {
1628         uint64_t V = IV->getSExtValue();
1629         emitSignedInt64(Record, V);
1630         Code = bitc::CST_CODE_INTEGER;
1631         AbbrevToUse = CONSTANTS_INTEGER_ABBREV;
1632       } else {                             // Wide integers, > 64 bits in size.
1633         // We have an arbitrary precision integer value to write whose
1634         // bit width is > 64. However, in canonical unsigned integer
1635         // format it is likely that the high bits are going to be zero.
1636         // So, we only write the number of active words.
1637         unsigned NWords = IV->getValue().getActiveWords();
1638         const uint64_t *RawWords = IV->getValue().getRawData();
1639         for (unsigned i = 0; i != NWords; ++i) {
1640           emitSignedInt64(Record, RawWords[i]);
1641         }
1642         Code = bitc::CST_CODE_WIDE_INTEGER;
1643       }
1644     } else if (const ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
1645       Code = bitc::CST_CODE_FLOAT;
1646       Type *Ty = CFP->getType();
1647       if (Ty->isHalfTy() || Ty->isFloatTy() || Ty->isDoubleTy()) {
1648         Record.push_back(CFP->getValueAPF().bitcastToAPInt().getZExtValue());
1649       } else if (Ty->isX86_FP80Ty()) {
1650         // api needed to prevent premature destruction
1651         // bits are not in the same order as a normal i80 APInt, compensate.
1652         APInt api = CFP->getValueAPF().bitcastToAPInt();
1653         const uint64_t *p = api.getRawData();
1654         Record.push_back((p[1] << 48) | (p[0] >> 16));
1655         Record.push_back(p[0] & 0xffffLL);
1656       } else if (Ty->isFP128Ty() || Ty->isPPC_FP128Ty()) {
1657         APInt api = CFP->getValueAPF().bitcastToAPInt();
1658         const uint64_t *p = api.getRawData();
1659         Record.push_back(p[0]);
1660         Record.push_back(p[1]);
1661       } else {
1662         assert (0 && "Unknown FP type!");
1663       }
1664     } else if (isa<ConstantDataSequential>(C) &&
1665                cast<ConstantDataSequential>(C)->isString()) {
1666       const ConstantDataSequential *Str = cast<ConstantDataSequential>(C);
1667       // Emit constant strings specially.
1668       unsigned NumElts = Str->getNumElements();
1669       // If this is a null-terminated string, use the denser CSTRING encoding.
1670       if (Str->isCString()) {
1671         Code = bitc::CST_CODE_CSTRING;
1672         --NumElts;  // Don't encode the null, which isn't allowed by char6.
1673       } else {
1674         Code = bitc::CST_CODE_STRING;
1675         AbbrevToUse = String8Abbrev;
1676       }
1677       bool isCStr7 = Code == bitc::CST_CODE_CSTRING;
1678       bool isCStrChar6 = Code == bitc::CST_CODE_CSTRING;
1679       for (unsigned i = 0; i != NumElts; ++i) {
1680         unsigned char V = Str->getElementAsInteger(i);
1681         Record.push_back(V);
1682         isCStr7 &= (V & 128) == 0;
1683         if (isCStrChar6)
1684           isCStrChar6 = BitCodeAbbrevOp::isChar6(V);
1685       }
1686 
1687       if (isCStrChar6)
1688         AbbrevToUse = CString6Abbrev;
1689       else if (isCStr7)
1690         AbbrevToUse = CString7Abbrev;
1691     } else if (const ConstantDataSequential *CDS =
1692                   dyn_cast<ConstantDataSequential>(C)) {
1693       Code = bitc::CST_CODE_DATA;
1694       Type *EltTy = CDS->getType()->getElementType();
1695       if (isa<IntegerType>(EltTy)) {
1696         for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i)
1697           Record.push_back(CDS->getElementAsInteger(i));
1698       } else {
1699         for (unsigned i = 0, e = CDS->getNumElements(); i != e; ++i)
1700           Record.push_back(
1701               CDS->getElementAsAPFloat(i).bitcastToAPInt().getLimitedValue());
1702       }
1703     } else if (isa<ConstantArray>(C) || isa<ConstantStruct>(C) ||
1704                isa<ConstantVector>(C)) {
1705       Code = bitc::CST_CODE_AGGREGATE;
1706       for (const Value *Op : C->operands())
1707         Record.push_back(VE.getValueID(Op));
1708       AbbrevToUse = AggregateAbbrev;
1709     } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
1710       switch (CE->getOpcode()) {
1711       default:
1712         if (Instruction::isCast(CE->getOpcode())) {
1713           Code = bitc::CST_CODE_CE_CAST;
1714           Record.push_back(GetEncodedCastOpcode(CE->getOpcode()));
1715           Record.push_back(VE.getTypeID(C->getOperand(0)->getType()));
1716           Record.push_back(VE.getValueID(C->getOperand(0)));
1717           AbbrevToUse = CONSTANTS_CE_CAST_Abbrev;
1718         } else {
1719           assert(CE->getNumOperands() == 2 && "Unknown constant expr!");
1720           Code = bitc::CST_CODE_CE_BINOP;
1721           Record.push_back(GetEncodedBinaryOpcode(CE->getOpcode()));
1722           Record.push_back(VE.getValueID(C->getOperand(0)));
1723           Record.push_back(VE.getValueID(C->getOperand(1)));
1724           uint64_t Flags = GetOptimizationFlags(CE);
1725           if (Flags != 0)
1726             Record.push_back(Flags);
1727         }
1728         break;
1729       case Instruction::GetElementPtr: {
1730         Code = bitc::CST_CODE_CE_GEP;
1731         const auto *GO = cast<GEPOperator>(C);
1732         if (GO->isInBounds())
1733           Code = bitc::CST_CODE_CE_INBOUNDS_GEP;
1734         Record.push_back(VE.getTypeID(GO->getSourceElementType()));
1735         for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i) {
1736           Record.push_back(VE.getTypeID(C->getOperand(i)->getType()));
1737           Record.push_back(VE.getValueID(C->getOperand(i)));
1738         }
1739         break;
1740       }
1741       case Instruction::Select:
1742         Code = bitc::CST_CODE_CE_SELECT;
1743         Record.push_back(VE.getValueID(C->getOperand(0)));
1744         Record.push_back(VE.getValueID(C->getOperand(1)));
1745         Record.push_back(VE.getValueID(C->getOperand(2)));
1746         break;
1747       case Instruction::ExtractElement:
1748         Code = bitc::CST_CODE_CE_EXTRACTELT;
1749         Record.push_back(VE.getTypeID(C->getOperand(0)->getType()));
1750         Record.push_back(VE.getValueID(C->getOperand(0)));
1751         Record.push_back(VE.getTypeID(C->getOperand(1)->getType()));
1752         Record.push_back(VE.getValueID(C->getOperand(1)));
1753         break;
1754       case Instruction::InsertElement:
1755         Code = bitc::CST_CODE_CE_INSERTELT;
1756         Record.push_back(VE.getValueID(C->getOperand(0)));
1757         Record.push_back(VE.getValueID(C->getOperand(1)));
1758         Record.push_back(VE.getTypeID(C->getOperand(2)->getType()));
1759         Record.push_back(VE.getValueID(C->getOperand(2)));
1760         break;
1761       case Instruction::ShuffleVector:
1762         // If the return type and argument types are the same, this is a
1763         // standard shufflevector instruction.  If the types are different,
1764         // then the shuffle is widening or truncating the input vectors, and
1765         // the argument type must also be encoded.
1766         if (C->getType() == C->getOperand(0)->getType()) {
1767           Code = bitc::CST_CODE_CE_SHUFFLEVEC;
1768         } else {
1769           Code = bitc::CST_CODE_CE_SHUFVEC_EX;
1770           Record.push_back(VE.getTypeID(C->getOperand(0)->getType()));
1771         }
1772         Record.push_back(VE.getValueID(C->getOperand(0)));
1773         Record.push_back(VE.getValueID(C->getOperand(1)));
1774         Record.push_back(VE.getValueID(C->getOperand(2)));
1775         break;
1776       case Instruction::ICmp:
1777       case Instruction::FCmp:
1778         Code = bitc::CST_CODE_CE_CMP;
1779         Record.push_back(VE.getTypeID(C->getOperand(0)->getType()));
1780         Record.push_back(VE.getValueID(C->getOperand(0)));
1781         Record.push_back(VE.getValueID(C->getOperand(1)));
1782         Record.push_back(CE->getPredicate());
1783         break;
1784       }
1785     } else if (const BlockAddress *BA = dyn_cast<BlockAddress>(C)) {
1786       Code = bitc::CST_CODE_BLOCKADDRESS;
1787       Record.push_back(VE.getTypeID(BA->getFunction()->getType()));
1788       Record.push_back(VE.getValueID(BA->getFunction()));
1789       Record.push_back(VE.getGlobalBasicBlockID(BA->getBasicBlock()));
1790     } else {
1791 #ifndef NDEBUG
1792       C->dump();
1793 #endif
1794       llvm_unreachable("Unknown constant!");
1795     }
1796     Stream.EmitRecord(Code, Record, AbbrevToUse);
1797     Record.clear();
1798   }
1799 
1800   Stream.ExitBlock();
1801 }
1802 
1803 static void WriteModuleConstants(const ValueEnumerator &VE,
1804                                  BitstreamWriter &Stream) {
1805   const ValueEnumerator::ValueList &Vals = VE.getValues();
1806 
1807   // Find the first constant to emit, which is the first non-globalvalue value.
1808   // We know globalvalues have been emitted by WriteModuleInfo.
1809   for (unsigned i = 0, e = Vals.size(); i != e; ++i) {
1810     if (!isa<GlobalValue>(Vals[i].first)) {
1811       WriteConstants(i, Vals.size(), VE, Stream, true);
1812       return;
1813     }
1814   }
1815 }
1816 
1817 /// PushValueAndType - The file has to encode both the value and type id for
1818 /// many values, because we need to know what type to create for forward
1819 /// references.  However, most operands are not forward references, so this type
1820 /// field is not needed.
1821 ///
1822 /// This function adds V's value ID to Vals.  If the value ID is higher than the
1823 /// instruction ID, then it is a forward reference, and it also includes the
1824 /// type ID.  The value ID that is written is encoded relative to the InstID.
1825 static bool PushValueAndType(const Value *V, unsigned InstID,
1826                              SmallVectorImpl<unsigned> &Vals,
1827                              ValueEnumerator &VE) {
1828   unsigned ValID = VE.getValueID(V);
1829   // Make encoding relative to the InstID.
1830   Vals.push_back(InstID - ValID);
1831   if (ValID >= InstID) {
1832     Vals.push_back(VE.getTypeID(V->getType()));
1833     return true;
1834   }
1835   return false;
1836 }
1837 
1838 static void WriteOperandBundles(BitstreamWriter &Stream, ImmutableCallSite CS,
1839                                 unsigned InstID, ValueEnumerator &VE) {
1840   SmallVector<unsigned, 64> Record;
1841   LLVMContext &C = CS.getInstruction()->getContext();
1842 
1843   for (unsigned i = 0, e = CS.getNumOperandBundles(); i != e; ++i) {
1844     const auto &Bundle = CS.getOperandBundleAt(i);
1845     Record.push_back(C.getOperandBundleTagID(Bundle.getTagName()));
1846 
1847     for (auto &Input : Bundle.Inputs)
1848       PushValueAndType(Input, InstID, Record, VE);
1849 
1850     Stream.EmitRecord(bitc::FUNC_CODE_OPERAND_BUNDLE, Record);
1851     Record.clear();
1852   }
1853 }
1854 
1855 /// pushValue - Like PushValueAndType, but where the type of the value is
1856 /// omitted (perhaps it was already encoded in an earlier operand).
1857 static void pushValue(const Value *V, unsigned InstID,
1858                       SmallVectorImpl<unsigned> &Vals,
1859                       ValueEnumerator &VE) {
1860   unsigned ValID = VE.getValueID(V);
1861   Vals.push_back(InstID - ValID);
1862 }
1863 
1864 static void pushValueSigned(const Value *V, unsigned InstID,
1865                             SmallVectorImpl<uint64_t> &Vals,
1866                             ValueEnumerator &VE) {
1867   unsigned ValID = VE.getValueID(V);
1868   int64_t diff = ((int32_t)InstID - (int32_t)ValID);
1869   emitSignedInt64(Vals, diff);
1870 }
1871 
1872 /// WriteInstruction - Emit an instruction to the specified stream.
1873 static void WriteInstruction(const Instruction &I, unsigned InstID,
1874                              ValueEnumerator &VE, BitstreamWriter &Stream,
1875                              SmallVectorImpl<unsigned> &Vals) {
1876   unsigned Code = 0;
1877   unsigned AbbrevToUse = 0;
1878   VE.setInstructionID(&I);
1879   switch (I.getOpcode()) {
1880   default:
1881     if (Instruction::isCast(I.getOpcode())) {
1882       Code = bitc::FUNC_CODE_INST_CAST;
1883       if (!PushValueAndType(I.getOperand(0), InstID, Vals, VE))
1884         AbbrevToUse = FUNCTION_INST_CAST_ABBREV;
1885       Vals.push_back(VE.getTypeID(I.getType()));
1886       Vals.push_back(GetEncodedCastOpcode(I.getOpcode()));
1887     } else {
1888       assert(isa<BinaryOperator>(I) && "Unknown instruction!");
1889       Code = bitc::FUNC_CODE_INST_BINOP;
1890       if (!PushValueAndType(I.getOperand(0), InstID, Vals, VE))
1891         AbbrevToUse = FUNCTION_INST_BINOP_ABBREV;
1892       pushValue(I.getOperand(1), InstID, Vals, VE);
1893       Vals.push_back(GetEncodedBinaryOpcode(I.getOpcode()));
1894       uint64_t Flags = GetOptimizationFlags(&I);
1895       if (Flags != 0) {
1896         if (AbbrevToUse == FUNCTION_INST_BINOP_ABBREV)
1897           AbbrevToUse = FUNCTION_INST_BINOP_FLAGS_ABBREV;
1898         Vals.push_back(Flags);
1899       }
1900     }
1901     break;
1902 
1903   case Instruction::GetElementPtr: {
1904     Code = bitc::FUNC_CODE_INST_GEP;
1905     AbbrevToUse = FUNCTION_INST_GEP_ABBREV;
1906     auto &GEPInst = cast<GetElementPtrInst>(I);
1907     Vals.push_back(GEPInst.isInBounds());
1908     Vals.push_back(VE.getTypeID(GEPInst.getSourceElementType()));
1909     for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
1910       PushValueAndType(I.getOperand(i), InstID, Vals, VE);
1911     break;
1912   }
1913   case Instruction::ExtractValue: {
1914     Code = bitc::FUNC_CODE_INST_EXTRACTVAL;
1915     PushValueAndType(I.getOperand(0), InstID, Vals, VE);
1916     const ExtractValueInst *EVI = cast<ExtractValueInst>(&I);
1917     Vals.append(EVI->idx_begin(), EVI->idx_end());
1918     break;
1919   }
1920   case Instruction::InsertValue: {
1921     Code = bitc::FUNC_CODE_INST_INSERTVAL;
1922     PushValueAndType(I.getOperand(0), InstID, Vals, VE);
1923     PushValueAndType(I.getOperand(1), InstID, Vals, VE);
1924     const InsertValueInst *IVI = cast<InsertValueInst>(&I);
1925     Vals.append(IVI->idx_begin(), IVI->idx_end());
1926     break;
1927   }
1928   case Instruction::Select:
1929     Code = bitc::FUNC_CODE_INST_VSELECT;
1930     PushValueAndType(I.getOperand(1), InstID, Vals, VE);
1931     pushValue(I.getOperand(2), InstID, Vals, VE);
1932     PushValueAndType(I.getOperand(0), InstID, Vals, VE);
1933     break;
1934   case Instruction::ExtractElement:
1935     Code = bitc::FUNC_CODE_INST_EXTRACTELT;
1936     PushValueAndType(I.getOperand(0), InstID, Vals, VE);
1937     PushValueAndType(I.getOperand(1), InstID, Vals, VE);
1938     break;
1939   case Instruction::InsertElement:
1940     Code = bitc::FUNC_CODE_INST_INSERTELT;
1941     PushValueAndType(I.getOperand(0), InstID, Vals, VE);
1942     pushValue(I.getOperand(1), InstID, Vals, VE);
1943     PushValueAndType(I.getOperand(2), InstID, Vals, VE);
1944     break;
1945   case Instruction::ShuffleVector:
1946     Code = bitc::FUNC_CODE_INST_SHUFFLEVEC;
1947     PushValueAndType(I.getOperand(0), InstID, Vals, VE);
1948     pushValue(I.getOperand(1), InstID, Vals, VE);
1949     pushValue(I.getOperand(2), InstID, Vals, VE);
1950     break;
1951   case Instruction::ICmp:
1952   case Instruction::FCmp: {
1953     // compare returning Int1Ty or vector of Int1Ty
1954     Code = bitc::FUNC_CODE_INST_CMP2;
1955     PushValueAndType(I.getOperand(0), InstID, Vals, VE);
1956     pushValue(I.getOperand(1), InstID, Vals, VE);
1957     Vals.push_back(cast<CmpInst>(I).getPredicate());
1958     uint64_t Flags = GetOptimizationFlags(&I);
1959     if (Flags != 0)
1960       Vals.push_back(Flags);
1961     break;
1962   }
1963 
1964   case Instruction::Ret:
1965     {
1966       Code = bitc::FUNC_CODE_INST_RET;
1967       unsigned NumOperands = I.getNumOperands();
1968       if (NumOperands == 0)
1969         AbbrevToUse = FUNCTION_INST_RET_VOID_ABBREV;
1970       else if (NumOperands == 1) {
1971         if (!PushValueAndType(I.getOperand(0), InstID, Vals, VE))
1972           AbbrevToUse = FUNCTION_INST_RET_VAL_ABBREV;
1973       } else {
1974         for (unsigned i = 0, e = NumOperands; i != e; ++i)
1975           PushValueAndType(I.getOperand(i), InstID, Vals, VE);
1976       }
1977     }
1978     break;
1979   case Instruction::Br:
1980     {
1981       Code = bitc::FUNC_CODE_INST_BR;
1982       const BranchInst &II = cast<BranchInst>(I);
1983       Vals.push_back(VE.getValueID(II.getSuccessor(0)));
1984       if (II.isConditional()) {
1985         Vals.push_back(VE.getValueID(II.getSuccessor(1)));
1986         pushValue(II.getCondition(), InstID, Vals, VE);
1987       }
1988     }
1989     break;
1990   case Instruction::Switch:
1991     {
1992       Code = bitc::FUNC_CODE_INST_SWITCH;
1993       const SwitchInst &SI = cast<SwitchInst>(I);
1994       Vals.push_back(VE.getTypeID(SI.getCondition()->getType()));
1995       pushValue(SI.getCondition(), InstID, Vals, VE);
1996       Vals.push_back(VE.getValueID(SI.getDefaultDest()));
1997       for (SwitchInst::ConstCaseIt Case : SI.cases()) {
1998         Vals.push_back(VE.getValueID(Case.getCaseValue()));
1999         Vals.push_back(VE.getValueID(Case.getCaseSuccessor()));
2000       }
2001     }
2002     break;
2003   case Instruction::IndirectBr:
2004     Code = bitc::FUNC_CODE_INST_INDIRECTBR;
2005     Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));
2006     // Encode the address operand as relative, but not the basic blocks.
2007     pushValue(I.getOperand(0), InstID, Vals, VE);
2008     for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i)
2009       Vals.push_back(VE.getValueID(I.getOperand(i)));
2010     break;
2011 
2012   case Instruction::Invoke: {
2013     const InvokeInst *II = cast<InvokeInst>(&I);
2014     const Value *Callee = II->getCalledValue();
2015     FunctionType *FTy = II->getFunctionType();
2016 
2017     if (II->hasOperandBundles())
2018       WriteOperandBundles(Stream, II, InstID, VE);
2019 
2020     Code = bitc::FUNC_CODE_INST_INVOKE;
2021 
2022     Vals.push_back(VE.getAttributeID(II->getAttributes()));
2023     Vals.push_back(II->getCallingConv() | 1 << 13);
2024     Vals.push_back(VE.getValueID(II->getNormalDest()));
2025     Vals.push_back(VE.getValueID(II->getUnwindDest()));
2026     Vals.push_back(VE.getTypeID(FTy));
2027     PushValueAndType(Callee, InstID, Vals, VE);
2028 
2029     // Emit value #'s for the fixed parameters.
2030     for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
2031       pushValue(I.getOperand(i), InstID, Vals, VE);  // fixed param.
2032 
2033     // Emit type/value pairs for varargs params.
2034     if (FTy->isVarArg()) {
2035       for (unsigned i = FTy->getNumParams(), e = I.getNumOperands()-3;
2036            i != e; ++i)
2037         PushValueAndType(I.getOperand(i), InstID, Vals, VE); // vararg
2038     }
2039     break;
2040   }
2041   case Instruction::Resume:
2042     Code = bitc::FUNC_CODE_INST_RESUME;
2043     PushValueAndType(I.getOperand(0), InstID, Vals, VE);
2044     break;
2045   case Instruction::CleanupRet: {
2046     Code = bitc::FUNC_CODE_INST_CLEANUPRET;
2047     const auto &CRI = cast<CleanupReturnInst>(I);
2048     pushValue(CRI.getCleanupPad(), InstID, Vals, VE);
2049     if (CRI.hasUnwindDest())
2050       Vals.push_back(VE.getValueID(CRI.getUnwindDest()));
2051     break;
2052   }
2053   case Instruction::CatchRet: {
2054     Code = bitc::FUNC_CODE_INST_CATCHRET;
2055     const auto &CRI = cast<CatchReturnInst>(I);
2056     pushValue(CRI.getCatchPad(), InstID, Vals, VE);
2057     Vals.push_back(VE.getValueID(CRI.getSuccessor()));
2058     break;
2059   }
2060   case Instruction::CleanupPad:
2061   case Instruction::CatchPad: {
2062     const auto &FuncletPad = cast<FuncletPadInst>(I);
2063     Code = isa<CatchPadInst>(FuncletPad) ? bitc::FUNC_CODE_INST_CATCHPAD
2064                                          : bitc::FUNC_CODE_INST_CLEANUPPAD;
2065     pushValue(FuncletPad.getParentPad(), InstID, Vals, VE);
2066 
2067     unsigned NumArgOperands = FuncletPad.getNumArgOperands();
2068     Vals.push_back(NumArgOperands);
2069     for (unsigned Op = 0; Op != NumArgOperands; ++Op)
2070       PushValueAndType(FuncletPad.getArgOperand(Op), InstID, Vals, VE);
2071     break;
2072   }
2073   case Instruction::CatchSwitch: {
2074     Code = bitc::FUNC_CODE_INST_CATCHSWITCH;
2075     const auto &CatchSwitch = cast<CatchSwitchInst>(I);
2076 
2077     pushValue(CatchSwitch.getParentPad(), InstID, Vals, VE);
2078 
2079     unsigned NumHandlers = CatchSwitch.getNumHandlers();
2080     Vals.push_back(NumHandlers);
2081     for (const BasicBlock *CatchPadBB : CatchSwitch.handlers())
2082       Vals.push_back(VE.getValueID(CatchPadBB));
2083 
2084     if (CatchSwitch.hasUnwindDest())
2085       Vals.push_back(VE.getValueID(CatchSwitch.getUnwindDest()));
2086     break;
2087   }
2088   case Instruction::Unreachable:
2089     Code = bitc::FUNC_CODE_INST_UNREACHABLE;
2090     AbbrevToUse = FUNCTION_INST_UNREACHABLE_ABBREV;
2091     break;
2092 
2093   case Instruction::PHI: {
2094     const PHINode &PN = cast<PHINode>(I);
2095     Code = bitc::FUNC_CODE_INST_PHI;
2096     // With the newer instruction encoding, forward references could give
2097     // negative valued IDs.  This is most common for PHIs, so we use
2098     // signed VBRs.
2099     SmallVector<uint64_t, 128> Vals64;
2100     Vals64.push_back(VE.getTypeID(PN.getType()));
2101     for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
2102       pushValueSigned(PN.getIncomingValue(i), InstID, Vals64, VE);
2103       Vals64.push_back(VE.getValueID(PN.getIncomingBlock(i)));
2104     }
2105     // Emit a Vals64 vector and exit.
2106     Stream.EmitRecord(Code, Vals64, AbbrevToUse);
2107     Vals64.clear();
2108     return;
2109   }
2110 
2111   case Instruction::LandingPad: {
2112     const LandingPadInst &LP = cast<LandingPadInst>(I);
2113     Code = bitc::FUNC_CODE_INST_LANDINGPAD;
2114     Vals.push_back(VE.getTypeID(LP.getType()));
2115     Vals.push_back(LP.isCleanup());
2116     Vals.push_back(LP.getNumClauses());
2117     for (unsigned I = 0, E = LP.getNumClauses(); I != E; ++I) {
2118       if (LP.isCatch(I))
2119         Vals.push_back(LandingPadInst::Catch);
2120       else
2121         Vals.push_back(LandingPadInst::Filter);
2122       PushValueAndType(LP.getClause(I), InstID, Vals, VE);
2123     }
2124     break;
2125   }
2126 
2127   case Instruction::Alloca: {
2128     Code = bitc::FUNC_CODE_INST_ALLOCA;
2129     const AllocaInst &AI = cast<AllocaInst>(I);
2130     Vals.push_back(VE.getTypeID(AI.getAllocatedType()));
2131     Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));
2132     Vals.push_back(VE.getValueID(I.getOperand(0))); // size.
2133     unsigned AlignRecord = Log2_32(AI.getAlignment()) + 1;
2134     assert(Log2_32(Value::MaximumAlignment) + 1 < 1 << 5 &&
2135            "not enough bits for maximum alignment");
2136     assert(AlignRecord < 1 << 5 && "alignment greater than 1 << 64");
2137     AlignRecord |= AI.isUsedWithInAlloca() << 5;
2138     AlignRecord |= 1 << 6;
2139     // Reserve bit 7 for SwiftError flag.
2140     // AlignRecord |= AI.isSwiftError() << 7;
2141     Vals.push_back(AlignRecord);
2142     break;
2143   }
2144 
2145   case Instruction::Load:
2146     if (cast<LoadInst>(I).isAtomic()) {
2147       Code = bitc::FUNC_CODE_INST_LOADATOMIC;
2148       PushValueAndType(I.getOperand(0), InstID, Vals, VE);
2149     } else {
2150       Code = bitc::FUNC_CODE_INST_LOAD;
2151       if (!PushValueAndType(I.getOperand(0), InstID, Vals, VE))  // ptr
2152         AbbrevToUse = FUNCTION_INST_LOAD_ABBREV;
2153     }
2154     Vals.push_back(VE.getTypeID(I.getType()));
2155     Vals.push_back(Log2_32(cast<LoadInst>(I).getAlignment())+1);
2156     Vals.push_back(cast<LoadInst>(I).isVolatile());
2157     if (cast<LoadInst>(I).isAtomic()) {
2158       Vals.push_back(GetEncodedOrdering(cast<LoadInst>(I).getOrdering()));
2159       Vals.push_back(GetEncodedSynchScope(cast<LoadInst>(I).getSynchScope()));
2160     }
2161     break;
2162   case Instruction::Store:
2163     if (cast<StoreInst>(I).isAtomic())
2164       Code = bitc::FUNC_CODE_INST_STOREATOMIC;
2165     else
2166       Code = bitc::FUNC_CODE_INST_STORE;
2167     PushValueAndType(I.getOperand(1), InstID, Vals, VE);  // ptrty + ptr
2168     PushValueAndType(I.getOperand(0), InstID, Vals, VE);  // valty + val
2169     Vals.push_back(Log2_32(cast<StoreInst>(I).getAlignment())+1);
2170     Vals.push_back(cast<StoreInst>(I).isVolatile());
2171     if (cast<StoreInst>(I).isAtomic()) {
2172       Vals.push_back(GetEncodedOrdering(cast<StoreInst>(I).getOrdering()));
2173       Vals.push_back(GetEncodedSynchScope(cast<StoreInst>(I).getSynchScope()));
2174     }
2175     break;
2176   case Instruction::AtomicCmpXchg:
2177     Code = bitc::FUNC_CODE_INST_CMPXCHG;
2178     PushValueAndType(I.getOperand(0), InstID, Vals, VE);  // ptrty + ptr
2179     PushValueAndType(I.getOperand(1), InstID, Vals, VE);  // cmp.
2180     pushValue(I.getOperand(2), InstID, Vals, VE);         // newval.
2181     Vals.push_back(cast<AtomicCmpXchgInst>(I).isVolatile());
2182     Vals.push_back(GetEncodedOrdering(
2183                      cast<AtomicCmpXchgInst>(I).getSuccessOrdering()));
2184     Vals.push_back(GetEncodedSynchScope(
2185                      cast<AtomicCmpXchgInst>(I).getSynchScope()));
2186     Vals.push_back(GetEncodedOrdering(
2187                      cast<AtomicCmpXchgInst>(I).getFailureOrdering()));
2188     Vals.push_back(cast<AtomicCmpXchgInst>(I).isWeak());
2189     break;
2190   case Instruction::AtomicRMW:
2191     Code = bitc::FUNC_CODE_INST_ATOMICRMW;
2192     PushValueAndType(I.getOperand(0), InstID, Vals, VE);  // ptrty + ptr
2193     pushValue(I.getOperand(1), InstID, Vals, VE);         // val.
2194     Vals.push_back(GetEncodedRMWOperation(
2195                      cast<AtomicRMWInst>(I).getOperation()));
2196     Vals.push_back(cast<AtomicRMWInst>(I).isVolatile());
2197     Vals.push_back(GetEncodedOrdering(cast<AtomicRMWInst>(I).getOrdering()));
2198     Vals.push_back(GetEncodedSynchScope(
2199                      cast<AtomicRMWInst>(I).getSynchScope()));
2200     break;
2201   case Instruction::Fence:
2202     Code = bitc::FUNC_CODE_INST_FENCE;
2203     Vals.push_back(GetEncodedOrdering(cast<FenceInst>(I).getOrdering()));
2204     Vals.push_back(GetEncodedSynchScope(cast<FenceInst>(I).getSynchScope()));
2205     break;
2206   case Instruction::Call: {
2207     const CallInst &CI = cast<CallInst>(I);
2208     FunctionType *FTy = CI.getFunctionType();
2209 
2210     if (CI.hasOperandBundles())
2211       WriteOperandBundles(Stream, &CI, InstID, VE);
2212 
2213     Code = bitc::FUNC_CODE_INST_CALL;
2214 
2215     Vals.push_back(VE.getAttributeID(CI.getAttributes()));
2216 
2217     unsigned Flags = GetOptimizationFlags(&I);
2218     Vals.push_back(CI.getCallingConv() << bitc::CALL_CCONV |
2219                    unsigned(CI.isTailCall()) << bitc::CALL_TAIL |
2220                    unsigned(CI.isMustTailCall()) << bitc::CALL_MUSTTAIL |
2221                    1 << bitc::CALL_EXPLICIT_TYPE |
2222                    unsigned(CI.isNoTailCall()) << bitc::CALL_NOTAIL |
2223                    unsigned(Flags != 0) << bitc::CALL_FMF);
2224     if (Flags != 0)
2225       Vals.push_back(Flags);
2226 
2227     Vals.push_back(VE.getTypeID(FTy));
2228     PushValueAndType(CI.getCalledValue(), InstID, Vals, VE);  // Callee
2229 
2230     // Emit value #'s for the fixed parameters.
2231     for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i) {
2232       // Check for labels (can happen with asm labels).
2233       if (FTy->getParamType(i)->isLabelTy())
2234         Vals.push_back(VE.getValueID(CI.getArgOperand(i)));
2235       else
2236         pushValue(CI.getArgOperand(i), InstID, Vals, VE);  // fixed param.
2237     }
2238 
2239     // Emit type/value pairs for varargs params.
2240     if (FTy->isVarArg()) {
2241       for (unsigned i = FTy->getNumParams(), e = CI.getNumArgOperands();
2242            i != e; ++i)
2243         PushValueAndType(CI.getArgOperand(i), InstID, Vals, VE);  // varargs
2244     }
2245     break;
2246   }
2247   case Instruction::VAArg:
2248     Code = bitc::FUNC_CODE_INST_VAARG;
2249     Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));   // valistty
2250     pushValue(I.getOperand(0), InstID, Vals, VE); // valist.
2251     Vals.push_back(VE.getTypeID(I.getType())); // restype.
2252     break;
2253   }
2254 
2255   Stream.EmitRecord(Code, Vals, AbbrevToUse);
2256   Vals.clear();
2257 }
2258 
2259 /// Emit names for globals/functions etc. The VSTOffsetPlaceholder,
2260 /// BitcodeStartBit and ModuleSummaryIndex are only passed for the module-level
2261 /// VST, where we are including a function bitcode index and need to
2262 /// backpatch the VST forward declaration record.
2263 static void WriteValueSymbolTable(
2264     const ValueSymbolTable &VST, const ValueEnumerator &VE,
2265     BitstreamWriter &Stream, uint64_t VSTOffsetPlaceholder = 0,
2266     uint64_t BitcodeStartBit = 0,
2267     DenseMap<const Function *, std::unique_ptr<GlobalValueInfo>>
2268         *FunctionIndex = nullptr) {
2269   if (VST.empty()) {
2270     // WriteValueSymbolTableForwardDecl should have returned early as
2271     // well. Ensure this handling remains in sync by asserting that
2272     // the placeholder offset is not set.
2273     assert(VSTOffsetPlaceholder == 0);
2274     return;
2275   }
2276 
2277   if (VSTOffsetPlaceholder > 0) {
2278     // Get the offset of the VST we are writing, and backpatch it into
2279     // the VST forward declaration record.
2280     uint64_t VSTOffset = Stream.GetCurrentBitNo();
2281     // The BitcodeStartBit was the stream offset of the actual bitcode
2282     // (e.g. excluding any initial darwin header).
2283     VSTOffset -= BitcodeStartBit;
2284     assert((VSTOffset & 31) == 0 && "VST block not 32-bit aligned");
2285     Stream.BackpatchWord(VSTOffsetPlaceholder, VSTOffset / 32);
2286   }
2287 
2288   Stream.EnterSubblock(bitc::VALUE_SYMTAB_BLOCK_ID, 4);
2289 
2290   // For the module-level VST, add abbrev Ids for the VST_CODE_FNENTRY
2291   // records, which are not used in the per-function VSTs.
2292   unsigned FnEntry8BitAbbrev;
2293   unsigned FnEntry7BitAbbrev;
2294   unsigned FnEntry6BitAbbrev;
2295   if (VSTOffsetPlaceholder > 0) {
2296     // 8-bit fixed-width VST_CODE_FNENTRY function strings.
2297     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2298     Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_FNENTRY));
2299     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // value id
2300     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // funcoffset
2301     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
2302     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 8));
2303     FnEntry8BitAbbrev = Stream.EmitAbbrev(Abbv);
2304 
2305     // 7-bit fixed width VST_CODE_FNENTRY function strings.
2306     Abbv = new BitCodeAbbrev();
2307     Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_FNENTRY));
2308     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // value id
2309     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // funcoffset
2310     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
2311     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 7));
2312     FnEntry7BitAbbrev = Stream.EmitAbbrev(Abbv);
2313 
2314     // 6-bit char6 VST_CODE_FNENTRY function strings.
2315     Abbv = new BitCodeAbbrev();
2316     Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_FNENTRY));
2317     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // value id
2318     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // funcoffset
2319     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
2320     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Char6));
2321     FnEntry6BitAbbrev = Stream.EmitAbbrev(Abbv);
2322   }
2323 
2324   // FIXME: Set up the abbrev, we know how many values there are!
2325   // FIXME: We know if the type names can use 7-bit ascii.
2326   SmallVector<unsigned, 64> NameVals;
2327 
2328   for (const ValueName &Name : VST) {
2329     // Figure out the encoding to use for the name.
2330     StringEncoding Bits =
2331         getStringEncoding(Name.getKeyData(), Name.getKeyLength());
2332 
2333     unsigned AbbrevToUse = VST_ENTRY_8_ABBREV;
2334     NameVals.push_back(VE.getValueID(Name.getValue()));
2335 
2336     Function *F = dyn_cast<Function>(Name.getValue());
2337     if (!F) {
2338       // If value is an alias, need to get the aliased base object to
2339       // see if it is a function.
2340       auto *GA = dyn_cast<GlobalAlias>(Name.getValue());
2341       if (GA && GA->getBaseObject())
2342         F = dyn_cast<Function>(GA->getBaseObject());
2343     }
2344 
2345     // VST_CODE_ENTRY:   [valueid, namechar x N]
2346     // VST_CODE_FNENTRY: [valueid, funcoffset, namechar x N]
2347     // VST_CODE_BBENTRY: [bbid, namechar x N]
2348     unsigned Code;
2349     if (isa<BasicBlock>(Name.getValue())) {
2350       Code = bitc::VST_CODE_BBENTRY;
2351       if (Bits == SE_Char6)
2352         AbbrevToUse = VST_BBENTRY_6_ABBREV;
2353     } else if (F && !F->isDeclaration()) {
2354       // Must be the module-level VST, where we pass in the Index and
2355       // have a VSTOffsetPlaceholder. The function-level VST should not
2356       // contain any Function symbols.
2357       assert(FunctionIndex);
2358       assert(VSTOffsetPlaceholder > 0);
2359 
2360       // Save the word offset of the function (from the start of the
2361       // actual bitcode written to the stream).
2362       uint64_t BitcodeIndex =
2363           (*FunctionIndex)[F]->bitcodeIndex() - BitcodeStartBit;
2364       assert((BitcodeIndex & 31) == 0 && "function block not 32-bit aligned");
2365       NameVals.push_back(BitcodeIndex / 32);
2366 
2367       Code = bitc::VST_CODE_FNENTRY;
2368       AbbrevToUse = FnEntry8BitAbbrev;
2369       if (Bits == SE_Char6)
2370         AbbrevToUse = FnEntry6BitAbbrev;
2371       else if (Bits == SE_Fixed7)
2372         AbbrevToUse = FnEntry7BitAbbrev;
2373     } else {
2374       Code = bitc::VST_CODE_ENTRY;
2375       if (Bits == SE_Char6)
2376         AbbrevToUse = VST_ENTRY_6_ABBREV;
2377       else if (Bits == SE_Fixed7)
2378         AbbrevToUse = VST_ENTRY_7_ABBREV;
2379     }
2380 
2381     for (const auto P : Name.getKey())
2382       NameVals.push_back((unsigned char)P);
2383 
2384     // Emit the finished record.
2385     Stream.EmitRecord(Code, NameVals, AbbrevToUse);
2386     NameVals.clear();
2387   }
2388   Stream.ExitBlock();
2389 }
2390 
2391 /// Emit function names and summary offsets for the combined index
2392 /// used by ThinLTO.
2393 static void
2394 WriteCombinedValueSymbolTable(const ModuleSummaryIndex &Index,
2395                               BitstreamWriter &Stream,
2396                               std::map<uint64_t, unsigned> &GUIDToValueIdMap,
2397                               uint64_t VSTOffsetPlaceholder) {
2398   assert(VSTOffsetPlaceholder > 0 && "Expected non-zero VSTOffsetPlaceholder");
2399   // Get the offset of the VST we are writing, and backpatch it into
2400   // the VST forward declaration record.
2401   uint64_t VSTOffset = Stream.GetCurrentBitNo();
2402   assert((VSTOffset & 31) == 0 && "VST block not 32-bit aligned");
2403   Stream.BackpatchWord(VSTOffsetPlaceholder, VSTOffset / 32);
2404 
2405   Stream.EnterSubblock(bitc::VALUE_SYMTAB_BLOCK_ID, 4);
2406 
2407   BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2408   Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_COMBINED_GVDEFENTRY));
2409   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // valueid
2410   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // sumoffset
2411   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // guid
2412   unsigned DefEntryAbbrev = Stream.EmitAbbrev(Abbv);
2413 
2414   Abbv = new BitCodeAbbrev();
2415   Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_COMBINED_ENTRY));
2416   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // valueid
2417   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // refguid
2418   unsigned EntryAbbrev = Stream.EmitAbbrev(Abbv);
2419 
2420   SmallVector<uint64_t, 64> NameVals;
2421 
2422   for (const auto &FII : Index) {
2423     uint64_t FuncGUID = FII.first;
2424     const auto &VMI = GUIDToValueIdMap.find(FuncGUID);
2425     assert(VMI != GUIDToValueIdMap.end());
2426 
2427     for (const auto &FI : FII.second) {
2428       // VST_CODE_COMBINED_GVDEFENTRY: [valueid, sumoffset, guid]
2429       NameVals.push_back(VMI->second);
2430       NameVals.push_back(FI->bitcodeIndex());
2431       NameVals.push_back(FuncGUID);
2432 
2433       // Emit the finished record.
2434       Stream.EmitRecord(bitc::VST_CODE_COMBINED_GVDEFENTRY, NameVals,
2435                         DefEntryAbbrev);
2436       NameVals.clear();
2437     }
2438     GUIDToValueIdMap.erase(VMI);
2439   }
2440   for (const auto &GVI : GUIDToValueIdMap) {
2441     // VST_CODE_COMBINED_ENTRY: [valueid, refguid]
2442     NameVals.push_back(GVI.second);
2443     NameVals.push_back(GVI.first);
2444 
2445     // Emit the finished record.
2446     Stream.EmitRecord(bitc::VST_CODE_COMBINED_ENTRY, NameVals, EntryAbbrev);
2447     NameVals.clear();
2448   }
2449   Stream.ExitBlock();
2450 }
2451 
2452 static void WriteUseList(ValueEnumerator &VE, UseListOrder &&Order,
2453                          BitstreamWriter &Stream) {
2454   assert(Order.Shuffle.size() >= 2 && "Shuffle too small");
2455   unsigned Code;
2456   if (isa<BasicBlock>(Order.V))
2457     Code = bitc::USELIST_CODE_BB;
2458   else
2459     Code = bitc::USELIST_CODE_DEFAULT;
2460 
2461   SmallVector<uint64_t, 64> Record(Order.Shuffle.begin(), Order.Shuffle.end());
2462   Record.push_back(VE.getValueID(Order.V));
2463   Stream.EmitRecord(Code, Record);
2464 }
2465 
2466 static void WriteUseListBlock(const Function *F, ValueEnumerator &VE,
2467                               BitstreamWriter &Stream) {
2468   assert(VE.shouldPreserveUseListOrder() &&
2469          "Expected to be preserving use-list order");
2470 
2471   auto hasMore = [&]() {
2472     return !VE.UseListOrders.empty() && VE.UseListOrders.back().F == F;
2473   };
2474   if (!hasMore())
2475     // Nothing to do.
2476     return;
2477 
2478   Stream.EnterSubblock(bitc::USELIST_BLOCK_ID, 3);
2479   while (hasMore()) {
2480     WriteUseList(VE, std::move(VE.UseListOrders.back()), Stream);
2481     VE.UseListOrders.pop_back();
2482   }
2483   Stream.ExitBlock();
2484 }
2485 
2486 // Walk through the operands of a given User via worklist iteration and populate
2487 // the set of GlobalValue references encountered. Invoked either on an
2488 // Instruction or a GlobalVariable (which walks its initializer).
2489 static void findRefEdges(const User *CurUser, const ValueEnumerator &VE,
2490                          DenseSet<unsigned> &RefEdges,
2491                          SmallPtrSet<const User *, 8> &Visited) {
2492   SmallVector<const User *, 32> Worklist;
2493   Worklist.push_back(CurUser);
2494 
2495   while (!Worklist.empty()) {
2496     const User *U = Worklist.pop_back_val();
2497 
2498     if (!Visited.insert(U).second)
2499       continue;
2500 
2501     ImmutableCallSite CS(U);
2502 
2503     for (const auto &OI : U->operands()) {
2504       const User *Operand = dyn_cast<User>(OI);
2505       if (!Operand)
2506         continue;
2507       if (isa<BlockAddress>(Operand))
2508         continue;
2509       if (isa<GlobalValue>(Operand)) {
2510         // We have a reference to a global value. This should be added to
2511         // the reference set unless it is a callee. Callees are handled
2512         // specially by WriteFunction and are added to a separate list.
2513         if (!(CS && CS.isCallee(&OI)))
2514           RefEdges.insert(VE.getValueID(Operand));
2515         continue;
2516       }
2517       Worklist.push_back(Operand);
2518     }
2519   }
2520 }
2521 
2522 /// Emit a function body to the module stream.
2523 static void WriteFunction(
2524     const Function &F, const Module *M, ValueEnumerator &VE,
2525     BitstreamWriter &Stream,
2526     DenseMap<const Function *, std::unique_ptr<GlobalValueInfo>> &FunctionIndex,
2527     bool EmitSummaryIndex) {
2528   // Save the bitcode index of the start of this function block for recording
2529   // in the VST.
2530   uint64_t BitcodeIndex = Stream.GetCurrentBitNo();
2531 
2532   bool HasProfileData = F.getEntryCount().hasValue();
2533   std::unique_ptr<BlockFrequencyInfo> BFI;
2534   if (EmitSummaryIndex && HasProfileData) {
2535     Function &Func = const_cast<Function &>(F);
2536     LoopInfo LI{DominatorTree(Func)};
2537     BranchProbabilityInfo BPI{Func, LI};
2538     BFI = llvm::make_unique<BlockFrequencyInfo>(Func, BPI, LI);
2539   }
2540 
2541   Stream.EnterSubblock(bitc::FUNCTION_BLOCK_ID, 4);
2542   VE.incorporateFunction(F);
2543 
2544   SmallVector<unsigned, 64> Vals;
2545 
2546   // Emit the number of basic blocks, so the reader can create them ahead of
2547   // time.
2548   Vals.push_back(VE.getBasicBlocks().size());
2549   Stream.EmitRecord(bitc::FUNC_CODE_DECLAREBLOCKS, Vals);
2550   Vals.clear();
2551 
2552   // If there are function-local constants, emit them now.
2553   unsigned CstStart, CstEnd;
2554   VE.getFunctionConstantRange(CstStart, CstEnd);
2555   WriteConstants(CstStart, CstEnd, VE, Stream, false);
2556 
2557   // If there is function-local metadata, emit it now.
2558   WriteFunctionLocalMetadata(F, VE, Stream);
2559 
2560   // Keep a running idea of what the instruction ID is.
2561   unsigned InstID = CstEnd;
2562 
2563   bool NeedsMetadataAttachment = F.hasMetadata();
2564 
2565   DILocation *LastDL = nullptr;
2566   unsigned NumInsts = 0;
2567   // Map from callee ValueId to profile count. Used to accumulate profile
2568   // counts for all static calls to a given callee.
2569   DenseMap<unsigned, CalleeInfo> CallGraphEdges;
2570   DenseSet<unsigned> RefEdges;
2571 
2572   SmallPtrSet<const User *, 8> Visited;
2573   // Finally, emit all the instructions, in order.
2574   for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
2575     for (BasicBlock::const_iterator I = BB->begin(), E = BB->end();
2576          I != E; ++I) {
2577       WriteInstruction(*I, InstID, VE, Stream, Vals);
2578 
2579       if (!isa<DbgInfoIntrinsic>(I))
2580         ++NumInsts;
2581 
2582       if (!I->getType()->isVoidTy())
2583         ++InstID;
2584 
2585       if (EmitSummaryIndex) {
2586         if (auto CS = ImmutableCallSite(&*I)) {
2587           auto *CalledFunction = CS.getCalledFunction();
2588           if (CalledFunction && CalledFunction->hasName() &&
2589               !CalledFunction->isIntrinsic()) {
2590             auto ScaledCount = BFI ? BFI->getBlockProfileCount(&*BB) : None;
2591             unsigned CalleeId = VE.getValueID(
2592                 M->getValueSymbolTable().lookup(CalledFunction->getName()));
2593             CallGraphEdges[CalleeId] +=
2594                 (ScaledCount ? ScaledCount.getValue() : 0);
2595           }
2596         }
2597         findRefEdges(&*I, VE, RefEdges, Visited);
2598       }
2599 
2600       // If the instruction has metadata, write a metadata attachment later.
2601       NeedsMetadataAttachment |= I->hasMetadataOtherThanDebugLoc();
2602 
2603       // If the instruction has a debug location, emit it.
2604       DILocation *DL = I->getDebugLoc();
2605       if (!DL)
2606         continue;
2607 
2608       if (DL == LastDL) {
2609         // Just repeat the same debug loc as last time.
2610         Stream.EmitRecord(bitc::FUNC_CODE_DEBUG_LOC_AGAIN, Vals);
2611         continue;
2612       }
2613 
2614       Vals.push_back(DL->getLine());
2615       Vals.push_back(DL->getColumn());
2616       Vals.push_back(VE.getMetadataOrNullID(DL->getScope()));
2617       Vals.push_back(VE.getMetadataOrNullID(DL->getInlinedAt()));
2618       Stream.EmitRecord(bitc::FUNC_CODE_DEBUG_LOC, Vals);
2619       Vals.clear();
2620 
2621       LastDL = DL;
2622     }
2623 
2624   std::unique_ptr<FunctionSummary> FuncSummary;
2625   if (EmitSummaryIndex) {
2626     FuncSummary = llvm::make_unique<FunctionSummary>(F.getLinkage(), NumInsts);
2627     FuncSummary->addCallGraphEdges(CallGraphEdges);
2628     FuncSummary->addRefEdges(RefEdges);
2629   }
2630   FunctionIndex[&F] =
2631       llvm::make_unique<GlobalValueInfo>(BitcodeIndex, std::move(FuncSummary));
2632 
2633   // Emit names for all the instructions etc.
2634   WriteValueSymbolTable(F.getValueSymbolTable(), VE, Stream);
2635 
2636   if (NeedsMetadataAttachment)
2637     WriteMetadataAttachment(F, VE, Stream);
2638   if (VE.shouldPreserveUseListOrder())
2639     WriteUseListBlock(&F, VE, Stream);
2640   VE.purgeFunction();
2641   Stream.ExitBlock();
2642 }
2643 
2644 // Emit blockinfo, which defines the standard abbreviations etc.
2645 static void WriteBlockInfo(const ValueEnumerator &VE, BitstreamWriter &Stream) {
2646   // We only want to emit block info records for blocks that have multiple
2647   // instances: CONSTANTS_BLOCK, FUNCTION_BLOCK and VALUE_SYMTAB_BLOCK.
2648   // Other blocks can define their abbrevs inline.
2649   Stream.EnterBlockInfoBlock(2);
2650 
2651   { // 8-bit fixed-width VST_CODE_ENTRY/VST_CODE_BBENTRY strings.
2652     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2653     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 3));
2654     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
2655     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
2656     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 8));
2657     if (Stream.EmitBlockInfoAbbrev(bitc::VALUE_SYMTAB_BLOCK_ID,
2658                                    Abbv) != VST_ENTRY_8_ABBREV)
2659       llvm_unreachable("Unexpected abbrev ordering!");
2660   }
2661 
2662   { // 7-bit fixed width VST_CODE_ENTRY strings.
2663     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2664     Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_ENTRY));
2665     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
2666     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
2667     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 7));
2668     if (Stream.EmitBlockInfoAbbrev(bitc::VALUE_SYMTAB_BLOCK_ID,
2669                                    Abbv) != VST_ENTRY_7_ABBREV)
2670       llvm_unreachable("Unexpected abbrev ordering!");
2671   }
2672   { // 6-bit char6 VST_CODE_ENTRY strings.
2673     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2674     Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_ENTRY));
2675     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
2676     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
2677     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Char6));
2678     if (Stream.EmitBlockInfoAbbrev(bitc::VALUE_SYMTAB_BLOCK_ID,
2679                                    Abbv) != VST_ENTRY_6_ABBREV)
2680       llvm_unreachable("Unexpected abbrev ordering!");
2681   }
2682   { // 6-bit char6 VST_CODE_BBENTRY strings.
2683     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2684     Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_BBENTRY));
2685     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
2686     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
2687     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Char6));
2688     if (Stream.EmitBlockInfoAbbrev(bitc::VALUE_SYMTAB_BLOCK_ID,
2689                                    Abbv) != VST_BBENTRY_6_ABBREV)
2690       llvm_unreachable("Unexpected abbrev ordering!");
2691   }
2692 
2693 
2694 
2695   { // SETTYPE abbrev for CONSTANTS_BLOCK.
2696     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2697     Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_SETTYPE));
2698     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,
2699                               VE.computeBitsRequiredForTypeIndicies()));
2700     if (Stream.EmitBlockInfoAbbrev(bitc::CONSTANTS_BLOCK_ID,
2701                                    Abbv) != CONSTANTS_SETTYPE_ABBREV)
2702       llvm_unreachable("Unexpected abbrev ordering!");
2703   }
2704 
2705   { // INTEGER abbrev for CONSTANTS_BLOCK.
2706     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2707     Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_INTEGER));
2708     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
2709     if (Stream.EmitBlockInfoAbbrev(bitc::CONSTANTS_BLOCK_ID,
2710                                    Abbv) != CONSTANTS_INTEGER_ABBREV)
2711       llvm_unreachable("Unexpected abbrev ordering!");
2712   }
2713 
2714   { // CE_CAST abbrev for CONSTANTS_BLOCK.
2715     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2716     Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_CE_CAST));
2717     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 4));  // cast opc
2718     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,       // typeid
2719                               VE.computeBitsRequiredForTypeIndicies()));
2720     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));    // value id
2721 
2722     if (Stream.EmitBlockInfoAbbrev(bitc::CONSTANTS_BLOCK_ID,
2723                                    Abbv) != CONSTANTS_CE_CAST_Abbrev)
2724       llvm_unreachable("Unexpected abbrev ordering!");
2725   }
2726   { // NULL abbrev for CONSTANTS_BLOCK.
2727     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2728     Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_NULL));
2729     if (Stream.EmitBlockInfoAbbrev(bitc::CONSTANTS_BLOCK_ID,
2730                                    Abbv) != CONSTANTS_NULL_Abbrev)
2731       llvm_unreachable("Unexpected abbrev ordering!");
2732   }
2733 
2734   // FIXME: This should only use space for first class types!
2735 
2736   { // INST_LOAD abbrev for FUNCTION_BLOCK.
2737     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2738     Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_LOAD));
2739     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // Ptr
2740     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,    // dest ty
2741                               VE.computeBitsRequiredForTypeIndicies()));
2742     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4)); // Align
2743     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1)); // volatile
2744     if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
2745                                    Abbv) != FUNCTION_INST_LOAD_ABBREV)
2746       llvm_unreachable("Unexpected abbrev ordering!");
2747   }
2748   { // INST_BINOP abbrev for FUNCTION_BLOCK.
2749     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2750     Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_BINOP));
2751     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // LHS
2752     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // RHS
2753     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 4)); // opc
2754     if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
2755                                    Abbv) != FUNCTION_INST_BINOP_ABBREV)
2756       llvm_unreachable("Unexpected abbrev ordering!");
2757   }
2758   { // INST_BINOP_FLAGS abbrev for FUNCTION_BLOCK.
2759     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2760     Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_BINOP));
2761     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // LHS
2762     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // RHS
2763     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 4)); // opc
2764     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 7)); // flags
2765     if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
2766                                    Abbv) != FUNCTION_INST_BINOP_FLAGS_ABBREV)
2767       llvm_unreachable("Unexpected abbrev ordering!");
2768   }
2769   { // INST_CAST abbrev for FUNCTION_BLOCK.
2770     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2771     Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_CAST));
2772     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));    // OpVal
2773     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,       // dest ty
2774                               VE.computeBitsRequiredForTypeIndicies()));
2775     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 4));  // opc
2776     if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
2777                                    Abbv) != FUNCTION_INST_CAST_ABBREV)
2778       llvm_unreachable("Unexpected abbrev ordering!");
2779   }
2780 
2781   { // INST_RET abbrev for FUNCTION_BLOCK.
2782     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2783     Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_RET));
2784     if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
2785                                    Abbv) != FUNCTION_INST_RET_VOID_ABBREV)
2786       llvm_unreachable("Unexpected abbrev ordering!");
2787   }
2788   { // INST_RET abbrev for FUNCTION_BLOCK.
2789     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2790     Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_RET));
2791     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // ValID
2792     if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
2793                                    Abbv) != FUNCTION_INST_RET_VAL_ABBREV)
2794       llvm_unreachable("Unexpected abbrev ordering!");
2795   }
2796   { // INST_UNREACHABLE abbrev for FUNCTION_BLOCK.
2797     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2798     Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_UNREACHABLE));
2799     if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
2800                                    Abbv) != FUNCTION_INST_UNREACHABLE_ABBREV)
2801       llvm_unreachable("Unexpected abbrev ordering!");
2802   }
2803   {
2804     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2805     Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_GEP));
2806     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1));
2807     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, // dest ty
2808                               Log2_32_Ceil(VE.getTypes().size() + 1)));
2809     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
2810     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));
2811     if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID, Abbv) !=
2812         FUNCTION_INST_GEP_ABBREV)
2813       llvm_unreachable("Unexpected abbrev ordering!");
2814   }
2815 
2816   Stream.ExitBlock();
2817 }
2818 
2819 /// Write the module path strings, currently only used when generating
2820 /// a combined index file.
2821 static void WriteModStrings(const ModuleSummaryIndex &I,
2822                             BitstreamWriter &Stream) {
2823   Stream.EnterSubblock(bitc::MODULE_STRTAB_BLOCK_ID, 3);
2824 
2825   // TODO: See which abbrev sizes we actually need to emit
2826 
2827   // 8-bit fixed-width MST_ENTRY strings.
2828   BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2829   Abbv->Add(BitCodeAbbrevOp(bitc::MST_CODE_ENTRY));
2830   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
2831   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
2832   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 8));
2833   unsigned Abbrev8Bit = Stream.EmitAbbrev(Abbv);
2834 
2835   // 7-bit fixed width MST_ENTRY strings.
2836   Abbv = new BitCodeAbbrev();
2837   Abbv->Add(BitCodeAbbrevOp(bitc::MST_CODE_ENTRY));
2838   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
2839   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
2840   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 7));
2841   unsigned Abbrev7Bit = Stream.EmitAbbrev(Abbv);
2842 
2843   // 6-bit char6 MST_ENTRY strings.
2844   Abbv = new BitCodeAbbrev();
2845   Abbv->Add(BitCodeAbbrevOp(bitc::MST_CODE_ENTRY));
2846   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
2847   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
2848   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Char6));
2849   unsigned Abbrev6Bit = Stream.EmitAbbrev(Abbv);
2850 
2851   SmallVector<unsigned, 64> NameVals;
2852   for (const StringMapEntry<uint64_t> &MPSE : I.modulePaths()) {
2853     StringEncoding Bits =
2854         getStringEncoding(MPSE.getKey().data(), MPSE.getKey().size());
2855     unsigned AbbrevToUse = Abbrev8Bit;
2856     if (Bits == SE_Char6)
2857       AbbrevToUse = Abbrev6Bit;
2858     else if (Bits == SE_Fixed7)
2859       AbbrevToUse = Abbrev7Bit;
2860 
2861     NameVals.push_back(MPSE.getValue());
2862 
2863     for (const auto P : MPSE.getKey())
2864       NameVals.push_back((unsigned char)P);
2865 
2866     // Emit the finished record.
2867     Stream.EmitRecord(bitc::MST_CODE_ENTRY, NameVals, AbbrevToUse);
2868     NameVals.clear();
2869   }
2870   Stream.ExitBlock();
2871 }
2872 
2873 // Helper to emit a single function summary record.
2874 static void WritePerModuleFunctionSummaryRecord(
2875     SmallVector<uint64_t, 64> &NameVals, FunctionSummary *FS, unsigned ValueID,
2876     unsigned FSCallsAbbrev, unsigned FSCallsProfileAbbrev,
2877     BitstreamWriter &Stream, const Function &F) {
2878   assert(FS);
2879   NameVals.push_back(ValueID);
2880   NameVals.push_back(getEncodedLinkage(FS->linkage()));
2881   NameVals.push_back(FS->instCount());
2882   NameVals.push_back(FS->refs().size());
2883 
2884   for (auto &RI : FS->refs())
2885     NameVals.push_back(RI);
2886 
2887   bool HasProfileData = F.getEntryCount().hasValue();
2888   for (auto &ECI : FS->calls()) {
2889     NameVals.push_back(ECI.first);
2890     assert(ECI.second.CallsiteCount > 0 && "Expected at least one callsite");
2891     NameVals.push_back(ECI.second.CallsiteCount);
2892     if (HasProfileData)
2893       NameVals.push_back(ECI.second.ProfileCount);
2894   }
2895 
2896   unsigned FSAbbrev = (HasProfileData ? FSCallsProfileAbbrev : FSCallsAbbrev);
2897   unsigned Code =
2898       (HasProfileData ? bitc::FS_PERMODULE_PROFILE : bitc::FS_PERMODULE);
2899 
2900   // Emit the finished record.
2901   Stream.EmitRecord(Code, NameVals, FSAbbrev);
2902   NameVals.clear();
2903 }
2904 
2905 // Collect the global value references in the given variable's initializer,
2906 // and emit them in a summary record.
2907 static void WriteModuleLevelReferences(const GlobalVariable &V,
2908                                        const ValueEnumerator &VE,
2909                                        SmallVector<uint64_t, 64> &NameVals,
2910                                        unsigned FSModRefsAbbrev,
2911                                        BitstreamWriter &Stream) {
2912   // Only interested in recording variable defs in the summary.
2913   if (V.isDeclaration())
2914     return;
2915   DenseSet<unsigned> RefEdges;
2916   SmallPtrSet<const User *, 8> Visited;
2917   findRefEdges(&V, VE, RefEdges, Visited);
2918   NameVals.push_back(VE.getValueID(&V));
2919   NameVals.push_back(getEncodedLinkage(V.getLinkage()));
2920   for (auto RefId : RefEdges) {
2921     NameVals.push_back(RefId);
2922   }
2923   Stream.EmitRecord(bitc::FS_PERMODULE_GLOBALVAR_INIT_REFS, NameVals,
2924                     FSModRefsAbbrev);
2925   NameVals.clear();
2926 }
2927 
2928 /// Emit the per-module summary section alongside the rest of
2929 /// the module's bitcode.
2930 static void WritePerModuleGlobalValueSummary(
2931     DenseMap<const Function *, std::unique_ptr<GlobalValueInfo>> &FunctionIndex,
2932     const Module *M, const ValueEnumerator &VE, BitstreamWriter &Stream) {
2933   if (M->empty())
2934     return;
2935 
2936   Stream.EnterSubblock(bitc::GLOBALVAL_SUMMARY_BLOCK_ID, 3);
2937 
2938   // Abbrev for FS_PERMODULE.
2939   BitCodeAbbrev *Abbv = new BitCodeAbbrev();
2940   Abbv->Add(BitCodeAbbrevOp(bitc::FS_PERMODULE));
2941   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // valueid
2942   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage
2943   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // instcount
2944   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // numrefs
2945   // numrefs x valueid, n x (valueid, callsitecount)
2946   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
2947   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
2948   unsigned FSCallsAbbrev = Stream.EmitAbbrev(Abbv);
2949 
2950   // Abbrev for FS_PERMODULE_PROFILE.
2951   Abbv = new BitCodeAbbrev();
2952   Abbv->Add(BitCodeAbbrevOp(bitc::FS_PERMODULE_PROFILE));
2953   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // valueid
2954   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage
2955   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // instcount
2956   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // numrefs
2957   // numrefs x valueid, n x (valueid, callsitecount, profilecount)
2958   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
2959   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
2960   unsigned FSCallsProfileAbbrev = Stream.EmitAbbrev(Abbv);
2961 
2962   // Abbrev for FS_PERMODULE_GLOBALVAR_INIT_REFS.
2963   Abbv = new BitCodeAbbrev();
2964   Abbv->Add(BitCodeAbbrevOp(bitc::FS_PERMODULE_GLOBALVAR_INIT_REFS));
2965   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // valueid
2966   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage
2967   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));  // valueids
2968   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
2969   unsigned FSModRefsAbbrev = Stream.EmitAbbrev(Abbv);
2970 
2971   SmallVector<uint64_t, 64> NameVals;
2972   // Iterate over the list of functions instead of the FunctionIndex map to
2973   // ensure the ordering is stable.
2974   for (const Function &F : *M) {
2975     if (F.isDeclaration())
2976       continue;
2977     // Skip anonymous functions. We will emit a function summary for
2978     // any aliases below.
2979     if (!F.hasName())
2980       continue;
2981 
2982     assert(FunctionIndex.count(&F) == 1);
2983 
2984     WritePerModuleFunctionSummaryRecord(
2985         NameVals, cast<FunctionSummary>(FunctionIndex[&F]->summary()),
2986         VE.getValueID(M->getValueSymbolTable().lookup(F.getName())),
2987         FSCallsAbbrev, FSCallsProfileAbbrev, Stream, F);
2988   }
2989 
2990   for (const GlobalAlias &A : M->aliases()) {
2991     if (!A.getBaseObject())
2992       continue;
2993     const Function *F = dyn_cast<Function>(A.getBaseObject());
2994     if (!F || F->isDeclaration())
2995       continue;
2996 
2997     assert(FunctionIndex.count(F) == 1);
2998     FunctionSummary *FS =
2999         cast<FunctionSummary>(FunctionIndex[F]->summary());
3000     // Add the alias to the reference list of aliasee function.
3001     FS->addRefEdge(
3002         VE.getValueID(M->getValueSymbolTable().lookup(A.getName())));
3003     WritePerModuleFunctionSummaryRecord(
3004         NameVals, FS,
3005         VE.getValueID(M->getValueSymbolTable().lookup(A.getName())),
3006         FSCallsAbbrev, FSCallsProfileAbbrev, Stream, *F);
3007   }
3008 
3009   // Capture references from GlobalVariable initializers, which are outside
3010   // of a function scope.
3011   for (const GlobalVariable &G : M->globals())
3012     WriteModuleLevelReferences(G, VE, NameVals, FSModRefsAbbrev, Stream);
3013   for (const GlobalAlias &A : M->aliases())
3014     if (auto *GV = dyn_cast<GlobalVariable>(A.getBaseObject()))
3015       WriteModuleLevelReferences(*GV, VE, NameVals, FSModRefsAbbrev, Stream);
3016 
3017   Stream.ExitBlock();
3018 }
3019 
3020 /// Emit the combined summary section into the combined index file.
3021 static void WriteCombinedGlobalValueSummary(
3022     const ModuleSummaryIndex &I, BitstreamWriter &Stream,
3023     std::map<uint64_t, unsigned> &GUIDToValueIdMap, unsigned GlobalValueId) {
3024   Stream.EnterSubblock(bitc::GLOBALVAL_SUMMARY_BLOCK_ID, 3);
3025 
3026   // Abbrev for FS_COMBINED.
3027   BitCodeAbbrev *Abbv = new BitCodeAbbrev();
3028   Abbv->Add(BitCodeAbbrevOp(bitc::FS_COMBINED));
3029   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // modid
3030   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage
3031   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // instcount
3032   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // numrefs
3033   // numrefs x valueid, n x (valueid, callsitecount)
3034   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
3035   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
3036   unsigned FSCallsAbbrev = Stream.EmitAbbrev(Abbv);
3037 
3038   // Abbrev for FS_COMBINED_PROFILE.
3039   Abbv = new BitCodeAbbrev();
3040   Abbv->Add(BitCodeAbbrevOp(bitc::FS_COMBINED_PROFILE));
3041   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // modid
3042   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage
3043   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // instcount
3044   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4));   // numrefs
3045   // numrefs x valueid, n x (valueid, callsitecount, profilecount)
3046   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
3047   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
3048   unsigned FSCallsProfileAbbrev = Stream.EmitAbbrev(Abbv);
3049 
3050   // Abbrev for FS_COMBINED_GLOBALVAR_INIT_REFS.
3051   Abbv = new BitCodeAbbrev();
3052   Abbv->Add(BitCodeAbbrevOp(bitc::FS_COMBINED_GLOBALVAR_INIT_REFS));
3053   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // modid
3054   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 5)); // linkage
3055   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));    // valueids
3056   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
3057   unsigned FSModRefsAbbrev = Stream.EmitAbbrev(Abbv);
3058 
3059   SmallVector<uint64_t, 64> NameVals;
3060   for (const auto &FII : I) {
3061     for (auto &FI : FII.second) {
3062       GlobalValueSummary *S = FI->summary();
3063       assert(S);
3064 
3065       if (auto *VS = dyn_cast<GlobalVarSummary>(S)) {
3066         NameVals.push_back(I.getModuleId(VS->modulePath()));
3067         NameVals.push_back(getEncodedLinkage(VS->linkage()));
3068         for (auto &RI : VS->refs()) {
3069           const auto &VMI = GUIDToValueIdMap.find(RI);
3070           unsigned RefId;
3071           // If this GUID doesn't have an entry, assign one.
3072           if (VMI == GUIDToValueIdMap.end()) {
3073             GUIDToValueIdMap[RI] = ++GlobalValueId;
3074             RefId = GlobalValueId;
3075           } else {
3076             RefId = VMI->second;
3077           }
3078           NameVals.push_back(RefId);
3079         }
3080 
3081         // Record the starting offset of this summary entry for use
3082         // in the VST entry. Add the current code size since the
3083         // reader will invoke readRecord after the abbrev id read.
3084         FI->setBitcodeIndex(Stream.GetCurrentBitNo() +
3085                             Stream.GetAbbrevIDWidth());
3086 
3087         // Emit the finished record.
3088         Stream.EmitRecord(bitc::FS_COMBINED_GLOBALVAR_INIT_REFS, NameVals,
3089                           FSModRefsAbbrev);
3090         NameVals.clear();
3091         continue;
3092       }
3093 
3094       auto *FS = cast<FunctionSummary>(S);
3095       NameVals.push_back(I.getModuleId(FS->modulePath()));
3096       NameVals.push_back(getEncodedLinkage(FS->linkage()));
3097       NameVals.push_back(FS->instCount());
3098       NameVals.push_back(FS->refs().size());
3099 
3100       for (auto &RI : FS->refs()) {
3101         const auto &VMI = GUIDToValueIdMap.find(RI);
3102         unsigned RefId;
3103         // If this GUID doesn't have an entry, assign one.
3104         if (VMI == GUIDToValueIdMap.end()) {
3105           GUIDToValueIdMap[RI] = ++GlobalValueId;
3106           RefId = GlobalValueId;
3107         } else {
3108           RefId = VMI->second;
3109         }
3110         NameVals.push_back(RefId);
3111       }
3112 
3113       bool HasProfileData = false;
3114       for (auto &EI : FS->calls()) {
3115         HasProfileData |= EI.second.ProfileCount != 0;
3116         if (HasProfileData)
3117           break;
3118       }
3119 
3120       for (auto &EI : FS->calls()) {
3121         const auto &VMI = GUIDToValueIdMap.find(EI.first);
3122         // If this GUID doesn't have an entry, it doesn't have a function
3123         // summary and we don't need to record any calls to it.
3124         if (VMI == GUIDToValueIdMap.end())
3125           continue;
3126         NameVals.push_back(VMI->second);
3127         assert(EI.second.CallsiteCount > 0 && "Expected at least one callsite");
3128         NameVals.push_back(EI.second.CallsiteCount);
3129         if (HasProfileData)
3130           NameVals.push_back(EI.second.ProfileCount);
3131       }
3132 
3133       // Record the starting offset of this summary entry for use
3134       // in the VST entry. Add the current code size since the
3135       // reader will invoke readRecord after the abbrev id read.
3136       FI->setBitcodeIndex(Stream.GetCurrentBitNo() + Stream.GetAbbrevIDWidth());
3137 
3138       unsigned FSAbbrev =
3139           (HasProfileData ? FSCallsProfileAbbrev : FSCallsAbbrev);
3140       unsigned Code =
3141           (HasProfileData ? bitc::FS_COMBINED_PROFILE : bitc::FS_COMBINED);
3142 
3143       // Emit the finished record.
3144       Stream.EmitRecord(Code, NameVals, FSAbbrev);
3145       NameVals.clear();
3146     }
3147   }
3148 
3149   Stream.ExitBlock();
3150 }
3151 
3152 // Create the "IDENTIFICATION_BLOCK_ID" containing a single string with the
3153 // current llvm version, and a record for the epoch number.
3154 static void WriteIdentificationBlock(const Module *M, BitstreamWriter &Stream) {
3155   Stream.EnterSubblock(bitc::IDENTIFICATION_BLOCK_ID, 5);
3156 
3157   // Write the "user readable" string identifying the bitcode producer
3158   BitCodeAbbrev *Abbv = new BitCodeAbbrev();
3159   Abbv->Add(BitCodeAbbrevOp(bitc::IDENTIFICATION_CODE_STRING));
3160   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
3161   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Char6));
3162   auto StringAbbrev = Stream.EmitAbbrev(Abbv);
3163   WriteStringRecord(bitc::IDENTIFICATION_CODE_STRING,
3164                     "LLVM" LLVM_VERSION_STRING, StringAbbrev, Stream);
3165 
3166   // Write the epoch version
3167   Abbv = new BitCodeAbbrev();
3168   Abbv->Add(BitCodeAbbrevOp(bitc::IDENTIFICATION_CODE_EPOCH));
3169   Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));
3170   auto EpochAbbrev = Stream.EmitAbbrev(Abbv);
3171   SmallVector<unsigned, 1> Vals = {bitc::BITCODE_CURRENT_EPOCH};
3172   Stream.EmitRecord(bitc::IDENTIFICATION_CODE_EPOCH, Vals, EpochAbbrev);
3173   Stream.ExitBlock();
3174 }
3175 
3176 /// WriteModule - Emit the specified module to the bitstream.
3177 static void WriteModule(const Module *M, BitstreamWriter &Stream,
3178                         bool ShouldPreserveUseListOrder,
3179                         uint64_t BitcodeStartBit, bool EmitSummaryIndex) {
3180   Stream.EnterSubblock(bitc::MODULE_BLOCK_ID, 3);
3181 
3182   SmallVector<unsigned, 1> Vals;
3183   unsigned CurVersion = 1;
3184   Vals.push_back(CurVersion);
3185   Stream.EmitRecord(bitc::MODULE_CODE_VERSION, Vals);
3186 
3187   // Analyze the module, enumerating globals, functions, etc.
3188   ValueEnumerator VE(*M, ShouldPreserveUseListOrder);
3189 
3190   // Emit blockinfo, which defines the standard abbreviations etc.
3191   WriteBlockInfo(VE, Stream);
3192 
3193   // Emit information about attribute groups.
3194   WriteAttributeGroupTable(VE, Stream);
3195 
3196   // Emit information about parameter attributes.
3197   WriteAttributeTable(VE, Stream);
3198 
3199   // Emit information describing all of the types in the module.
3200   WriteTypeTable(VE, Stream);
3201 
3202   writeComdats(VE, Stream);
3203 
3204   // Emit top-level description of module, including target triple, inline asm,
3205   // descriptors for global variables, and function prototype info.
3206   uint64_t VSTOffsetPlaceholder = WriteModuleInfo(M, VE, Stream);
3207 
3208   // Emit constants.
3209   WriteModuleConstants(VE, Stream);
3210 
3211   // Emit metadata.
3212   WriteModuleMetadata(*M, VE, Stream);
3213 
3214   // Emit metadata.
3215   WriteModuleMetadataStore(M, Stream);
3216 
3217   // Emit module-level use-lists.
3218   if (VE.shouldPreserveUseListOrder())
3219     WriteUseListBlock(nullptr, VE, Stream);
3220 
3221   WriteOperandBundleTags(M, Stream);
3222 
3223   // Emit function bodies.
3224   DenseMap<const Function *, std::unique_ptr<GlobalValueInfo>> FunctionIndex;
3225   for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F)
3226     if (!F->isDeclaration())
3227       WriteFunction(*F, M, VE, Stream, FunctionIndex, EmitSummaryIndex);
3228 
3229   // Need to write after the above call to WriteFunction which populates
3230   // the summary information in the index.
3231   if (EmitSummaryIndex)
3232     WritePerModuleGlobalValueSummary(FunctionIndex, M, VE, Stream);
3233 
3234   WriteValueSymbolTable(M->getValueSymbolTable(), VE, Stream,
3235                         VSTOffsetPlaceholder, BitcodeStartBit, &FunctionIndex);
3236 
3237   Stream.ExitBlock();
3238 }
3239 
3240 /// EmitDarwinBCHeader - If generating a bc file on darwin, we have to emit a
3241 /// header and trailer to make it compatible with the system archiver.  To do
3242 /// this we emit the following header, and then emit a trailer that pads the
3243 /// file out to be a multiple of 16 bytes.
3244 ///
3245 /// struct bc_header {
3246 ///   uint32_t Magic;         // 0x0B17C0DE
3247 ///   uint32_t Version;       // Version, currently always 0.
3248 ///   uint32_t BitcodeOffset; // Offset to traditional bitcode file.
3249 ///   uint32_t BitcodeSize;   // Size of traditional bitcode file.
3250 ///   uint32_t CPUType;       // CPU specifier.
3251 ///   ... potentially more later ...
3252 /// };
3253 
3254 static void WriteInt32ToBuffer(uint32_t Value, SmallVectorImpl<char> &Buffer,
3255                                uint32_t &Position) {
3256   support::endian::write32le(&Buffer[Position], Value);
3257   Position += 4;
3258 }
3259 
3260 static void EmitDarwinBCHeaderAndTrailer(SmallVectorImpl<char> &Buffer,
3261                                          const Triple &TT) {
3262   unsigned CPUType = ~0U;
3263 
3264   // Match x86_64-*, i[3-9]86-*, powerpc-*, powerpc64-*, arm-*, thumb-*,
3265   // armv[0-9]-*, thumbv[0-9]-*, armv5te-*, or armv6t2-*. The CPUType is a magic
3266   // number from /usr/include/mach/machine.h.  It is ok to reproduce the
3267   // specific constants here because they are implicitly part of the Darwin ABI.
3268   enum {
3269     DARWIN_CPU_ARCH_ABI64      = 0x01000000,
3270     DARWIN_CPU_TYPE_X86        = 7,
3271     DARWIN_CPU_TYPE_ARM        = 12,
3272     DARWIN_CPU_TYPE_POWERPC    = 18
3273   };
3274 
3275   Triple::ArchType Arch = TT.getArch();
3276   if (Arch == Triple::x86_64)
3277     CPUType = DARWIN_CPU_TYPE_X86 | DARWIN_CPU_ARCH_ABI64;
3278   else if (Arch == Triple::x86)
3279     CPUType = DARWIN_CPU_TYPE_X86;
3280   else if (Arch == Triple::ppc)
3281     CPUType = DARWIN_CPU_TYPE_POWERPC;
3282   else if (Arch == Triple::ppc64)
3283     CPUType = DARWIN_CPU_TYPE_POWERPC | DARWIN_CPU_ARCH_ABI64;
3284   else if (Arch == Triple::arm || Arch == Triple::thumb)
3285     CPUType = DARWIN_CPU_TYPE_ARM;
3286 
3287   // Traditional Bitcode starts after header.
3288   assert(Buffer.size() >= BWH_HeaderSize &&
3289          "Expected header size to be reserved");
3290   unsigned BCOffset = BWH_HeaderSize;
3291   unsigned BCSize = Buffer.size() - BWH_HeaderSize;
3292 
3293   // Write the magic and version.
3294   unsigned Position = 0;
3295   WriteInt32ToBuffer(0x0B17C0DE , Buffer, Position);
3296   WriteInt32ToBuffer(0          , Buffer, Position); // Version.
3297   WriteInt32ToBuffer(BCOffset   , Buffer, Position);
3298   WriteInt32ToBuffer(BCSize     , Buffer, Position);
3299   WriteInt32ToBuffer(CPUType    , Buffer, Position);
3300 
3301   // If the file is not a multiple of 16 bytes, insert dummy padding.
3302   while (Buffer.size() & 15)
3303     Buffer.push_back(0);
3304 }
3305 
3306 /// Helper to write the header common to all bitcode files.
3307 static void WriteBitcodeHeader(BitstreamWriter &Stream) {
3308   // Emit the file header.
3309   Stream.Emit((unsigned)'B', 8);
3310   Stream.Emit((unsigned)'C', 8);
3311   Stream.Emit(0x0, 4);
3312   Stream.Emit(0xC, 4);
3313   Stream.Emit(0xE, 4);
3314   Stream.Emit(0xD, 4);
3315 }
3316 
3317 /// WriteBitcodeToFile - Write the specified module to the specified output
3318 /// stream.
3319 void llvm::WriteBitcodeToFile(const Module *M, raw_ostream &Out,
3320                               bool ShouldPreserveUseListOrder,
3321                               bool EmitSummaryIndex) {
3322   SmallVector<char, 0> Buffer;
3323   Buffer.reserve(256*1024);
3324 
3325   // If this is darwin or another generic macho target, reserve space for the
3326   // header.
3327   Triple TT(M->getTargetTriple());
3328   if (TT.isOSDarwin() || TT.isOSBinFormatMachO())
3329     Buffer.insert(Buffer.begin(), BWH_HeaderSize, 0);
3330 
3331   // Emit the module into the buffer.
3332   {
3333     BitstreamWriter Stream(Buffer);
3334     // Save the start bit of the actual bitcode, in case there is space
3335     // saved at the start for the darwin header above. The reader stream
3336     // will start at the bitcode, and we need the offset of the VST
3337     // to line up.
3338     uint64_t BitcodeStartBit = Stream.GetCurrentBitNo();
3339 
3340     // Emit the file header.
3341     WriteBitcodeHeader(Stream);
3342 
3343     WriteIdentificationBlock(M, Stream);
3344 
3345     // Emit the module.
3346     WriteModule(M, Stream, ShouldPreserveUseListOrder, BitcodeStartBit,
3347                 EmitSummaryIndex);
3348   }
3349 
3350   if (TT.isOSDarwin() || TT.isOSBinFormatMachO())
3351     EmitDarwinBCHeaderAndTrailer(Buffer, TT);
3352 
3353   // Write the generated bitstream to "Out".
3354   Out.write((char*)&Buffer.front(), Buffer.size());
3355 }
3356 
3357 // Write the specified module summary index to the given raw output stream,
3358 // where it will be written in a new bitcode block. This is used when
3359 // writing the combined index file for ThinLTO.
3360 void llvm::WriteIndexToFile(const ModuleSummaryIndex &Index, raw_ostream &Out) {
3361   SmallVector<char, 0> Buffer;
3362   Buffer.reserve(256 * 1024);
3363 
3364   BitstreamWriter Stream(Buffer);
3365 
3366   // Emit the bitcode header.
3367   WriteBitcodeHeader(Stream);
3368 
3369   Stream.EnterSubblock(bitc::MODULE_BLOCK_ID, 3);
3370 
3371   SmallVector<unsigned, 1> Vals;
3372   unsigned CurVersion = 1;
3373   Vals.push_back(CurVersion);
3374   Stream.EmitRecord(bitc::MODULE_CODE_VERSION, Vals);
3375 
3376   // If we have a VST, write the VSTOFFSET record placeholder and record
3377   // its offset.
3378   uint64_t VSTOffsetPlaceholder = WriteValueSymbolTableForwardDecl(Stream);
3379 
3380   // Write the module paths in the combined index.
3381   WriteModStrings(Index, Stream);
3382 
3383   // Assign unique value ids to all functions in the index for use
3384   // in writing out the call graph edges. Save the mapping from GUID
3385   // to the new global value id to use when writing those edges, which
3386   // are currently saved in the index in terms of GUID.
3387   std::map<uint64_t, unsigned> GUIDToValueIdMap;
3388   unsigned GlobalValueId = 0;
3389   for (auto &II : Index)
3390     GUIDToValueIdMap[II.first] = ++GlobalValueId;
3391 
3392   // Write the summary combined index records.
3393   WriteCombinedGlobalValueSummary(Index, Stream, GUIDToValueIdMap,
3394                                   GlobalValueId);
3395 
3396   // Need a special VST writer for the combined index (we don't have a
3397   // real VST and real values when this is invoked).
3398   WriteCombinedValueSymbolTable(Index, Stream, GUIDToValueIdMap,
3399                                 VSTOffsetPlaceholder);
3400 
3401   Stream.ExitBlock();
3402 
3403   Out.write((char *)&Buffer.front(), Buffer.size());
3404 }
3405