BitcodeWriter.cpp revision 80a75bfae980df96f969f1c05b0c4a80ce975240
1//===--- Bitcode/Writer/BitcodeWriter.cpp - Bitcode Writer ----------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by Chris Lattner and is distributed under
6// the University of Illinois Open Source License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// Bitcode writer implementation.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Bitcode/ReaderWriter.h"
15#include "llvm/Bitcode/BitstreamWriter.h"
16#include "llvm/Bitcode/LLVMBitCodes.h"
17#include "ValueEnumerator.h"
18#include "llvm/Constants.h"
19#include "llvm/DerivedTypes.h"
20#include "llvm/InlineAsm.h"
21#include "llvm/Instructions.h"
22#include "llvm/Module.h"
23#include "llvm/ParameterAttributes.h"
24#include "llvm/TypeSymbolTable.h"
25#include "llvm/ValueSymbolTable.h"
26#include "llvm/Support/MathExtras.h"
27using namespace llvm;
28
29/// These are manifest constants used by the bitcode writer. They do not need to
30/// be kept in sync with the reader, but need to be consistent within this file.
31enum {
32  CurVersion = 0,
33
34  // VALUE_SYMTAB_BLOCK abbrev id's.
35  VST_ENTRY_8_ABBREV = bitc::FIRST_APPLICATION_ABBREV,
36  VST_ENTRY_7_ABBREV,
37  VST_ENTRY_6_ABBREV,
38  VST_BBENTRY_6_ABBREV,
39
40  // CONSTANTS_BLOCK abbrev id's.
41  CONSTANTS_SETTYPE_ABBREV = bitc::FIRST_APPLICATION_ABBREV,
42  CONSTANTS_INTEGER_ABBREV,
43  CONSTANTS_CE_CAST_Abbrev,
44  CONSTANTS_NULL_Abbrev,
45
46  // FUNCTION_BLOCK abbrev id's.
47  FUNCTION_INST_LOAD_ABBREV = bitc::FIRST_APPLICATION_ABBREV,
48  FUNCTION_INST_BINOP_ABBREV,
49  FUNCTION_INST_CAST_ABBREV,
50  FUNCTION_INST_RET_VOID_ABBREV,
51  FUNCTION_INST_RET_VAL_ABBREV,
52  FUNCTION_INST_UNREACHABLE_ABBREV
53};
54
55
56static unsigned GetEncodedCastOpcode(unsigned Opcode) {
57  switch (Opcode) {
58  default: assert(0 && "Unknown cast instruction!");
59  case Instruction::Trunc   : return bitc::CAST_TRUNC;
60  case Instruction::ZExt    : return bitc::CAST_ZEXT;
61  case Instruction::SExt    : return bitc::CAST_SEXT;
62  case Instruction::FPToUI  : return bitc::CAST_FPTOUI;
63  case Instruction::FPToSI  : return bitc::CAST_FPTOSI;
64  case Instruction::UIToFP  : return bitc::CAST_UITOFP;
65  case Instruction::SIToFP  : return bitc::CAST_SITOFP;
66  case Instruction::FPTrunc : return bitc::CAST_FPTRUNC;
67  case Instruction::FPExt   : return bitc::CAST_FPEXT;
68  case Instruction::PtrToInt: return bitc::CAST_PTRTOINT;
69  case Instruction::IntToPtr: return bitc::CAST_INTTOPTR;
70  case Instruction::BitCast : return bitc::CAST_BITCAST;
71  }
72}
73
74static unsigned GetEncodedBinaryOpcode(unsigned Opcode) {
75  switch (Opcode) {
76  default: assert(0 && "Unknown binary instruction!");
77  case Instruction::Add:  return bitc::BINOP_ADD;
78  case Instruction::Sub:  return bitc::BINOP_SUB;
79  case Instruction::Mul:  return bitc::BINOP_MUL;
80  case Instruction::UDiv: return bitc::BINOP_UDIV;
81  case Instruction::FDiv:
82  case Instruction::SDiv: return bitc::BINOP_SDIV;
83  case Instruction::URem: return bitc::BINOP_UREM;
84  case Instruction::FRem:
85  case Instruction::SRem: return bitc::BINOP_SREM;
86  case Instruction::Shl:  return bitc::BINOP_SHL;
87  case Instruction::LShr: return bitc::BINOP_LSHR;
88  case Instruction::AShr: return bitc::BINOP_ASHR;
89  case Instruction::And:  return bitc::BINOP_AND;
90  case Instruction::Or:   return bitc::BINOP_OR;
91  case Instruction::Xor:  return bitc::BINOP_XOR;
92  }
93}
94
95
96
97static void WriteStringRecord(unsigned Code, const std::string &Str,
98                              unsigned AbbrevToUse, BitstreamWriter &Stream) {
99  SmallVector<unsigned, 64> Vals;
100
101  // Code: [strchar x N]
102  for (unsigned i = 0, e = Str.size(); i != e; ++i)
103    Vals.push_back(Str[i]);
104
105  // Emit the finished record.
106  Stream.EmitRecord(Code, Vals, AbbrevToUse);
107}
108
109// Emit information about parameter attributes.
110static void WriteParamAttrTable(const ValueEnumerator &VE,
111                                BitstreamWriter &Stream) {
112  const std::vector<const ParamAttrsList*> &Attrs = VE.getParamAttrs();
113  if (Attrs.empty()) return;
114
115  Stream.EnterSubblock(bitc::PARAMATTR_BLOCK_ID, 3);
116
117  SmallVector<uint64_t, 64> Record;
118  for (unsigned i = 0, e = Attrs.size(); i != e; ++i) {
119    const ParamAttrsList *A = Attrs[i];
120    for (unsigned op = 0, e = A->size(); op != e; ++op) {
121      Record.push_back(A->getParamIndex(op));
122      Record.push_back(A->getParamAttrsAtIndex(op));
123    }
124
125    Stream.EmitRecord(bitc::PARAMATTR_CODE_ENTRY, Record);
126    Record.clear();
127  }
128
129  Stream.ExitBlock();
130}
131
132/// WriteTypeTable - Write out the type table for a module.
133static void WriteTypeTable(const ValueEnumerator &VE, BitstreamWriter &Stream) {
134  const ValueEnumerator::TypeList &TypeList = VE.getTypes();
135
136  Stream.EnterSubblock(bitc::TYPE_BLOCK_ID, 4 /*count from # abbrevs */);
137  SmallVector<uint64_t, 64> TypeVals;
138
139  // Abbrev for TYPE_CODE_POINTER.
140  BitCodeAbbrev *Abbv = new BitCodeAbbrev();
141  Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_POINTER));
142  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,
143                            Log2_32_Ceil(VE.getTypes().size()+1)));
144  unsigned PtrAbbrev = Stream.EmitAbbrev(Abbv);
145
146  // Abbrev for TYPE_CODE_FUNCTION.
147  Abbv = new BitCodeAbbrev();
148  Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_FUNCTION));
149  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1));  // isvararg
150  Abbv->Add(BitCodeAbbrevOp(0));  // FIXME: DEAD value, remove in LLVM 3.0
151  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
152  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,
153                            Log2_32_Ceil(VE.getTypes().size()+1)));
154  unsigned FunctionAbbrev = Stream.EmitAbbrev(Abbv);
155
156  // Abbrev for TYPE_CODE_STRUCT.
157  Abbv = new BitCodeAbbrev();
158  Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_STRUCT));
159  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1));  // ispacked
160  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
161  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,
162                            Log2_32_Ceil(VE.getTypes().size()+1)));
163  unsigned StructAbbrev = Stream.EmitAbbrev(Abbv);
164
165  // Abbrev for TYPE_CODE_ARRAY.
166  Abbv = new BitCodeAbbrev();
167  Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_ARRAY));
168  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));   // size
169  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,
170                            Log2_32_Ceil(VE.getTypes().size()+1)));
171  unsigned ArrayAbbrev = Stream.EmitAbbrev(Abbv);
172
173  // Emit an entry count so the reader can reserve space.
174  TypeVals.push_back(TypeList.size());
175  Stream.EmitRecord(bitc::TYPE_CODE_NUMENTRY, TypeVals);
176  TypeVals.clear();
177
178  // Loop over all of the types, emitting each in turn.
179  for (unsigned i = 0, e = TypeList.size(); i != e; ++i) {
180    const Type *T = TypeList[i].first;
181    int AbbrevToUse = 0;
182    unsigned Code = 0;
183
184    switch (T->getTypeID()) {
185    default: assert(0 && "Unknown type!");
186    case Type::VoidTyID:   Code = bitc::TYPE_CODE_VOID;   break;
187    case Type::FloatTyID:  Code = bitc::TYPE_CODE_FLOAT;  break;
188    case Type::DoubleTyID: Code = bitc::TYPE_CODE_DOUBLE; break;
189    case Type::X86_FP80TyID: Code = bitc::TYPE_CODE_X86_FP80; break;
190    case Type::FP128TyID: Code = bitc::TYPE_CODE_FP128; break;
191    case Type::PPC_FP128TyID: Code = bitc::TYPE_CODE_PPC_FP128; break;
192    case Type::LabelTyID:  Code = bitc::TYPE_CODE_LABEL;  break;
193    case Type::OpaqueTyID: Code = bitc::TYPE_CODE_OPAQUE; break;
194    case Type::IntegerTyID:
195      // INTEGER: [width]
196      Code = bitc::TYPE_CODE_INTEGER;
197      TypeVals.push_back(cast<IntegerType>(T)->getBitWidth());
198      break;
199    case Type::PointerTyID:
200      // POINTER: [pointee type]
201      Code = bitc::TYPE_CODE_POINTER;
202      TypeVals.push_back(VE.getTypeID(cast<PointerType>(T)->getElementType()));
203      AbbrevToUse = PtrAbbrev;
204      break;
205
206    case Type::FunctionTyID: {
207      const FunctionType *FT = cast<FunctionType>(T);
208      // FUNCTION: [isvararg, attrid, retty, paramty x N]
209      Code = bitc::TYPE_CODE_FUNCTION;
210      TypeVals.push_back(FT->isVarArg());
211      TypeVals.push_back(0);  // FIXME: DEAD: remove in llvm 3.0
212      TypeVals.push_back(VE.getTypeID(FT->getReturnType()));
213      for (unsigned i = 0, e = FT->getNumParams(); i != e; ++i)
214        TypeVals.push_back(VE.getTypeID(FT->getParamType(i)));
215      AbbrevToUse = FunctionAbbrev;
216      break;
217    }
218    case Type::StructTyID: {
219      const StructType *ST = cast<StructType>(T);
220      // STRUCT: [ispacked, eltty x N]
221      Code = bitc::TYPE_CODE_STRUCT;
222      TypeVals.push_back(ST->isPacked());
223      // Output all of the element types.
224      for (StructType::element_iterator I = ST->element_begin(),
225           E = ST->element_end(); I != E; ++I)
226        TypeVals.push_back(VE.getTypeID(*I));
227      AbbrevToUse = StructAbbrev;
228      break;
229    }
230    case Type::ArrayTyID: {
231      const ArrayType *AT = cast<ArrayType>(T);
232      // ARRAY: [numelts, eltty]
233      Code = bitc::TYPE_CODE_ARRAY;
234      TypeVals.push_back(AT->getNumElements());
235      TypeVals.push_back(VE.getTypeID(AT->getElementType()));
236      AbbrevToUse = ArrayAbbrev;
237      break;
238    }
239    case Type::VectorTyID: {
240      const VectorType *VT = cast<VectorType>(T);
241      // VECTOR [numelts, eltty]
242      Code = bitc::TYPE_CODE_VECTOR;
243      TypeVals.push_back(VT->getNumElements());
244      TypeVals.push_back(VE.getTypeID(VT->getElementType()));
245      break;
246    }
247    }
248
249    // Emit the finished record.
250    Stream.EmitRecord(Code, TypeVals, AbbrevToUse);
251    TypeVals.clear();
252  }
253
254  Stream.ExitBlock();
255}
256
257static unsigned getEncodedLinkage(const GlobalValue *GV) {
258  switch (GV->getLinkage()) {
259  default: assert(0 && "Invalid linkage!");
260  case GlobalValue::GhostLinkage:  // Map ghost linkage onto external.
261  case GlobalValue::ExternalLinkage:     return 0;
262  case GlobalValue::WeakLinkage:         return 1;
263  case GlobalValue::AppendingLinkage:    return 2;
264  case GlobalValue::InternalLinkage:     return 3;
265  case GlobalValue::LinkOnceLinkage:     return 4;
266  case GlobalValue::DLLImportLinkage:    return 5;
267  case GlobalValue::DLLExportLinkage:    return 6;
268  case GlobalValue::ExternalWeakLinkage: return 7;
269  }
270}
271
272static unsigned getEncodedVisibility(const GlobalValue *GV) {
273  switch (GV->getVisibility()) {
274  default: assert(0 && "Invalid visibility!");
275  case GlobalValue::DefaultVisibility:   return 0;
276  case GlobalValue::HiddenVisibility:    return 1;
277  case GlobalValue::ProtectedVisibility: return 2;
278  }
279}
280
281// Emit top-level description of module, including target triple, inline asm,
282// descriptors for global variables, and function prototype info.
283static void WriteModuleInfo(const Module *M, const ValueEnumerator &VE,
284                            BitstreamWriter &Stream) {
285  // Emit the list of dependent libraries for the Module.
286  for (Module::lib_iterator I = M->lib_begin(), E = M->lib_end(); I != E; ++I)
287    WriteStringRecord(bitc::MODULE_CODE_DEPLIB, *I, 0/*TODO*/, Stream);
288
289  // Emit various pieces of data attached to a module.
290  if (!M->getTargetTriple().empty())
291    WriteStringRecord(bitc::MODULE_CODE_TRIPLE, M->getTargetTriple(),
292                      0/*TODO*/, Stream);
293  if (!M->getDataLayout().empty())
294    WriteStringRecord(bitc::MODULE_CODE_DATALAYOUT, M->getDataLayout(),
295                      0/*TODO*/, Stream);
296  if (!M->getModuleInlineAsm().empty())
297    WriteStringRecord(bitc::MODULE_CODE_ASM, M->getModuleInlineAsm(),
298                      0/*TODO*/, Stream);
299
300  // Emit information about sections and collectors, computing how many there
301  // are.  Also compute the maximum alignment value.
302  std::map<std::string, unsigned> SectionMap;
303  std::map<std::string, unsigned> CollectorMap;
304  unsigned MaxAlignment = 0;
305  unsigned MaxGlobalType = 0;
306  for (Module::const_global_iterator GV = M->global_begin(),E = M->global_end();
307       GV != E; ++GV) {
308    MaxAlignment = std::max(MaxAlignment, GV->getAlignment());
309    MaxGlobalType = std::max(MaxGlobalType, VE.getTypeID(GV->getType()));
310
311    if (!GV->hasSection()) continue;
312    // Give section names unique ID's.
313    unsigned &Entry = SectionMap[GV->getSection()];
314    if (Entry != 0) continue;
315    WriteStringRecord(bitc::MODULE_CODE_SECTIONNAME, GV->getSection(),
316                      0/*TODO*/, Stream);
317    Entry = SectionMap.size();
318  }
319  for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) {
320    MaxAlignment = std::max(MaxAlignment, F->getAlignment());
321    if (F->hasSection()) {
322      // Give section names unique ID's.
323      unsigned &Entry = SectionMap[F->getSection()];
324      if (!Entry) {
325        WriteStringRecord(bitc::MODULE_CODE_SECTIONNAME, F->getSection(),
326                          0/*TODO*/, Stream);
327        Entry = SectionMap.size();
328      }
329    }
330    if (F->hasCollector()) {
331      // Same for collector names.
332      unsigned &Entry = CollectorMap[F->getCollector()];
333      if (!Entry) {
334        WriteStringRecord(bitc::MODULE_CODE_COLLECTORNAME, F->getCollector(),
335                          0/*TODO*/, Stream);
336        Entry = CollectorMap.size();
337      }
338    }
339  }
340
341  // Emit abbrev for globals, now that we know # sections and max alignment.
342  unsigned SimpleGVarAbbrev = 0;
343  if (!M->global_empty()) {
344    // Add an abbrev for common globals with no visibility or thread localness.
345    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
346    Abbv->Add(BitCodeAbbrevOp(bitc::MODULE_CODE_GLOBALVAR));
347    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,
348                              Log2_32_Ceil(MaxGlobalType+1)));
349    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1));      // Constant.
350    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));        // Initializer.
351    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 3));      // Linkage.
352    if (MaxAlignment == 0)                                      // Alignment.
353      Abbv->Add(BitCodeAbbrevOp(0));
354    else {
355      unsigned MaxEncAlignment = Log2_32(MaxAlignment)+1;
356      Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,
357                               Log2_32_Ceil(MaxEncAlignment+1)));
358    }
359    if (SectionMap.empty())                                    // Section.
360      Abbv->Add(BitCodeAbbrevOp(0));
361    else
362      Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,
363                               Log2_32_Ceil(SectionMap.size()+1)));
364    // Don't bother emitting vis + thread local.
365    SimpleGVarAbbrev = Stream.EmitAbbrev(Abbv);
366  }
367
368  // Emit the global variable information.
369  SmallVector<unsigned, 64> Vals;
370  for (Module::const_global_iterator GV = M->global_begin(),E = M->global_end();
371       GV != E; ++GV) {
372    unsigned AbbrevToUse = 0;
373
374    // GLOBALVAR: [type, isconst, initid,
375    //             linkage, alignment, section, visibility, threadlocal]
376    Vals.push_back(VE.getTypeID(GV->getType()));
377    Vals.push_back(GV->isConstant());
378    Vals.push_back(GV->isDeclaration() ? 0 :
379                   (VE.getValueID(GV->getInitializer()) + 1));
380    Vals.push_back(getEncodedLinkage(GV));
381    Vals.push_back(Log2_32(GV->getAlignment())+1);
382    Vals.push_back(GV->hasSection() ? SectionMap[GV->getSection()] : 0);
383    if (GV->isThreadLocal() ||
384        GV->getVisibility() != GlobalValue::DefaultVisibility) {
385      Vals.push_back(getEncodedVisibility(GV));
386      Vals.push_back(GV->isThreadLocal());
387    } else {
388      AbbrevToUse = SimpleGVarAbbrev;
389    }
390
391    Stream.EmitRecord(bitc::MODULE_CODE_GLOBALVAR, Vals, AbbrevToUse);
392    Vals.clear();
393  }
394
395  // Emit the function proto information.
396  for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) {
397    // FUNCTION:  [type, callingconv, isproto, paramattr,
398    //             linkage, alignment, section, visibility, collector]
399    Vals.push_back(VE.getTypeID(F->getType()));
400    Vals.push_back(F->getCallingConv());
401    Vals.push_back(F->isDeclaration());
402    Vals.push_back(getEncodedLinkage(F));
403    Vals.push_back(VE.getParamAttrID(F->getParamAttrs()));
404    Vals.push_back(Log2_32(F->getAlignment())+1);
405    Vals.push_back(F->hasSection() ? SectionMap[F->getSection()] : 0);
406    Vals.push_back(getEncodedVisibility(F));
407    Vals.push_back(F->hasCollector() ? CollectorMap[F->getCollector()] : 0);
408
409    unsigned AbbrevToUse = 0;
410    Stream.EmitRecord(bitc::MODULE_CODE_FUNCTION, Vals, AbbrevToUse);
411    Vals.clear();
412  }
413
414
415  // Emit the alias information.
416  for (Module::const_alias_iterator AI = M->alias_begin(), E = M->alias_end();
417       AI != E; ++AI) {
418    Vals.push_back(VE.getTypeID(AI->getType()));
419    Vals.push_back(VE.getValueID(AI->getAliasee()));
420    Vals.push_back(getEncodedLinkage(AI));
421    unsigned AbbrevToUse = 0;
422    Stream.EmitRecord(bitc::MODULE_CODE_ALIAS, Vals, AbbrevToUse);
423    Vals.clear();
424  }
425}
426
427
428static void WriteConstants(unsigned FirstVal, unsigned LastVal,
429                           const ValueEnumerator &VE,
430                           BitstreamWriter &Stream, bool isGlobal) {
431  if (FirstVal == LastVal) return;
432
433  Stream.EnterSubblock(bitc::CONSTANTS_BLOCK_ID, 4);
434
435  unsigned AggregateAbbrev = 0;
436  unsigned String8Abbrev = 0;
437  unsigned CString7Abbrev = 0;
438  unsigned CString6Abbrev = 0;
439  // If this is a constant pool for the module, emit module-specific abbrevs.
440  if (isGlobal) {
441    // Abbrev for CST_CODE_AGGREGATE.
442    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
443    Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_AGGREGATE));
444    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
445    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, Log2_32_Ceil(LastVal+1)));
446    AggregateAbbrev = Stream.EmitAbbrev(Abbv);
447
448    // Abbrev for CST_CODE_STRING.
449    Abbv = new BitCodeAbbrev();
450    Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_STRING));
451    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
452    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 8));
453    String8Abbrev = Stream.EmitAbbrev(Abbv);
454    // Abbrev for CST_CODE_CSTRING.
455    Abbv = new BitCodeAbbrev();
456    Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_CSTRING));
457    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
458    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 7));
459    CString7Abbrev = Stream.EmitAbbrev(Abbv);
460    // Abbrev for CST_CODE_CSTRING.
461    Abbv = new BitCodeAbbrev();
462    Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_CSTRING));
463    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
464    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Char6));
465    CString6Abbrev = Stream.EmitAbbrev(Abbv);
466  }
467
468  SmallVector<uint64_t, 64> Record;
469
470  const ValueEnumerator::ValueList &Vals = VE.getValues();
471  const Type *LastTy = 0;
472  for (unsigned i = FirstVal; i != LastVal; ++i) {
473    const Value *V = Vals[i].first;
474    // If we need to switch types, do so now.
475    if (V->getType() != LastTy) {
476      LastTy = V->getType();
477      Record.push_back(VE.getTypeID(LastTy));
478      Stream.EmitRecord(bitc::CST_CODE_SETTYPE, Record,
479                        CONSTANTS_SETTYPE_ABBREV);
480      Record.clear();
481    }
482
483    if (const InlineAsm *IA = dyn_cast<InlineAsm>(V)) {
484      Record.push_back(unsigned(IA->hasSideEffects()));
485
486      // Add the asm string.
487      const std::string &AsmStr = IA->getAsmString();
488      Record.push_back(AsmStr.size());
489      for (unsigned i = 0, e = AsmStr.size(); i != e; ++i)
490        Record.push_back(AsmStr[i]);
491
492      // Add the constraint string.
493      const std::string &ConstraintStr = IA->getConstraintString();
494      Record.push_back(ConstraintStr.size());
495      for (unsigned i = 0, e = ConstraintStr.size(); i != e; ++i)
496        Record.push_back(ConstraintStr[i]);
497      Stream.EmitRecord(bitc::CST_CODE_INLINEASM, Record);
498      Record.clear();
499      continue;
500    }
501    const Constant *C = cast<Constant>(V);
502    unsigned Code = -1U;
503    unsigned AbbrevToUse = 0;
504    if (C->isNullValue()) {
505      Code = bitc::CST_CODE_NULL;
506    } else if (isa<UndefValue>(C)) {
507      Code = bitc::CST_CODE_UNDEF;
508    } else if (const ConstantInt *IV = dyn_cast<ConstantInt>(C)) {
509      if (IV->getBitWidth() <= 64) {
510        int64_t V = IV->getSExtValue();
511        if (V >= 0)
512          Record.push_back(V << 1);
513        else
514          Record.push_back((-V << 1) | 1);
515        Code = bitc::CST_CODE_INTEGER;
516        AbbrevToUse = CONSTANTS_INTEGER_ABBREV;
517      } else {                             // Wide integers, > 64 bits in size.
518        // We have an arbitrary precision integer value to write whose
519        // bit width is > 64. However, in canonical unsigned integer
520        // format it is likely that the high bits are going to be zero.
521        // So, we only write the number of active words.
522        unsigned NWords = IV->getValue().getActiveWords();
523        const uint64_t *RawWords = IV->getValue().getRawData();
524        for (unsigned i = 0; i != NWords; ++i) {
525          int64_t V = RawWords[i];
526          if (V >= 0)
527            Record.push_back(V << 1);
528          else
529            Record.push_back((-V << 1) | 1);
530        }
531        Code = bitc::CST_CODE_WIDE_INTEGER;
532      }
533    } else if (const ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
534      Code = bitc::CST_CODE_FLOAT;
535      const Type *Ty = CFP->getType();
536      if (Ty == Type::FloatTy || Ty == Type::DoubleTy) {
537        Record.push_back(CFP->getValueAPF().convertToAPInt().getZExtValue());
538      } else if (Ty == Type::X86_FP80Ty) {
539        // api needed to prevent premature destruction
540        APInt api = CFP->getValueAPF().convertToAPInt();
541        const uint64_t *p = api.getRawData();
542        Record.push_back(p[0]);
543        Record.push_back((uint16_t)p[1]);
544      } else if (Ty == Type::FP128Ty || Ty == Type::PPC_FP128Ty) {
545        APInt api = CFP->getValueAPF().convertToAPInt();
546        const uint64_t *p = api.getRawData();
547        Record.push_back(p[0]);
548        Record.push_back(p[1]);
549      } else {
550        assert (0 && "Unknown FP type!");
551      }
552    } else if (isa<ConstantArray>(C) && cast<ConstantArray>(C)->isString()) {
553      // Emit constant strings specially.
554      unsigned NumOps = C->getNumOperands();
555      // If this is a null-terminated string, use the denser CSTRING encoding.
556      if (C->getOperand(NumOps-1)->isNullValue()) {
557        Code = bitc::CST_CODE_CSTRING;
558        --NumOps;  // Don't encode the null, which isn't allowed by char6.
559      } else {
560        Code = bitc::CST_CODE_STRING;
561        AbbrevToUse = String8Abbrev;
562      }
563      bool isCStr7 = Code == bitc::CST_CODE_CSTRING;
564      bool isCStrChar6 = Code == bitc::CST_CODE_CSTRING;
565      for (unsigned i = 0; i != NumOps; ++i) {
566        unsigned char V = cast<ConstantInt>(C->getOperand(i))->getZExtValue();
567        Record.push_back(V);
568        isCStr7 &= (V & 128) == 0;
569        if (isCStrChar6)
570          isCStrChar6 = BitCodeAbbrevOp::isChar6(V);
571      }
572
573      if (isCStrChar6)
574        AbbrevToUse = CString6Abbrev;
575      else if (isCStr7)
576        AbbrevToUse = CString7Abbrev;
577    } else if (isa<ConstantArray>(C) || isa<ConstantStruct>(V) ||
578               isa<ConstantVector>(V)) {
579      Code = bitc::CST_CODE_AGGREGATE;
580      for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i)
581        Record.push_back(VE.getValueID(C->getOperand(i)));
582      AbbrevToUse = AggregateAbbrev;
583    } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
584      switch (CE->getOpcode()) {
585      default:
586        if (Instruction::isCast(CE->getOpcode())) {
587          Code = bitc::CST_CODE_CE_CAST;
588          Record.push_back(GetEncodedCastOpcode(CE->getOpcode()));
589          Record.push_back(VE.getTypeID(C->getOperand(0)->getType()));
590          Record.push_back(VE.getValueID(C->getOperand(0)));
591          AbbrevToUse = CONSTANTS_CE_CAST_Abbrev;
592        } else {
593          assert(CE->getNumOperands() == 2 && "Unknown constant expr!");
594          Code = bitc::CST_CODE_CE_BINOP;
595          Record.push_back(GetEncodedBinaryOpcode(CE->getOpcode()));
596          Record.push_back(VE.getValueID(C->getOperand(0)));
597          Record.push_back(VE.getValueID(C->getOperand(1)));
598        }
599        break;
600      case Instruction::GetElementPtr:
601        Code = bitc::CST_CODE_CE_GEP;
602        for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i) {
603          Record.push_back(VE.getTypeID(C->getOperand(i)->getType()));
604          Record.push_back(VE.getValueID(C->getOperand(i)));
605        }
606        break;
607      case Instruction::Select:
608        Code = bitc::CST_CODE_CE_SELECT;
609        Record.push_back(VE.getValueID(C->getOperand(0)));
610        Record.push_back(VE.getValueID(C->getOperand(1)));
611        Record.push_back(VE.getValueID(C->getOperand(2)));
612        break;
613      case Instruction::ExtractElement:
614        Code = bitc::CST_CODE_CE_EXTRACTELT;
615        Record.push_back(VE.getTypeID(C->getOperand(0)->getType()));
616        Record.push_back(VE.getValueID(C->getOperand(0)));
617        Record.push_back(VE.getValueID(C->getOperand(1)));
618        break;
619      case Instruction::InsertElement:
620        Code = bitc::CST_CODE_CE_INSERTELT;
621        Record.push_back(VE.getValueID(C->getOperand(0)));
622        Record.push_back(VE.getValueID(C->getOperand(1)));
623        Record.push_back(VE.getValueID(C->getOperand(2)));
624        break;
625      case Instruction::ShuffleVector:
626        Code = bitc::CST_CODE_CE_SHUFFLEVEC;
627        Record.push_back(VE.getValueID(C->getOperand(0)));
628        Record.push_back(VE.getValueID(C->getOperand(1)));
629        Record.push_back(VE.getValueID(C->getOperand(2)));
630        break;
631      case Instruction::ICmp:
632      case Instruction::FCmp:
633        Code = bitc::CST_CODE_CE_CMP;
634        Record.push_back(VE.getTypeID(C->getOperand(0)->getType()));
635        Record.push_back(VE.getValueID(C->getOperand(0)));
636        Record.push_back(VE.getValueID(C->getOperand(1)));
637        Record.push_back(CE->getPredicate());
638        break;
639      }
640    } else {
641      assert(0 && "Unknown constant!");
642    }
643    Stream.EmitRecord(Code, Record, AbbrevToUse);
644    Record.clear();
645  }
646
647  Stream.ExitBlock();
648}
649
650static void WriteModuleConstants(const ValueEnumerator &VE,
651                                 BitstreamWriter &Stream) {
652  const ValueEnumerator::ValueList &Vals = VE.getValues();
653
654  // Find the first constant to emit, which is the first non-globalvalue value.
655  // We know globalvalues have been emitted by WriteModuleInfo.
656  for (unsigned i = 0, e = Vals.size(); i != e; ++i) {
657    if (!isa<GlobalValue>(Vals[i].first)) {
658      WriteConstants(i, Vals.size(), VE, Stream, true);
659      return;
660    }
661  }
662}
663
664/// PushValueAndType - The file has to encode both the value and type id for
665/// many values, because we need to know what type to create for forward
666/// references.  However, most operands are not forward references, so this type
667/// field is not needed.
668///
669/// This function adds V's value ID to Vals.  If the value ID is higher than the
670/// instruction ID, then it is a forward reference, and it also includes the
671/// type ID.
672static bool PushValueAndType(Value *V, unsigned InstID,
673                             SmallVector<unsigned, 64> &Vals,
674                             ValueEnumerator &VE) {
675  unsigned ValID = VE.getValueID(V);
676  Vals.push_back(ValID);
677  if (ValID >= InstID) {
678    Vals.push_back(VE.getTypeID(V->getType()));
679    return true;
680  }
681  return false;
682}
683
684/// WriteInstruction - Emit an instruction to the specified stream.
685static void WriteInstruction(const Instruction &I, unsigned InstID,
686                             ValueEnumerator &VE, BitstreamWriter &Stream,
687                             SmallVector<unsigned, 64> &Vals) {
688  unsigned Code = 0;
689  unsigned AbbrevToUse = 0;
690  switch (I.getOpcode()) {
691  default:
692    if (Instruction::isCast(I.getOpcode())) {
693      Code = bitc::FUNC_CODE_INST_CAST;
694      if (!PushValueAndType(I.getOperand(0), InstID, Vals, VE))
695        AbbrevToUse = FUNCTION_INST_CAST_ABBREV;
696      Vals.push_back(VE.getTypeID(I.getType()));
697      Vals.push_back(GetEncodedCastOpcode(I.getOpcode()));
698    } else {
699      assert(isa<BinaryOperator>(I) && "Unknown instruction!");
700      Code = bitc::FUNC_CODE_INST_BINOP;
701      if (!PushValueAndType(I.getOperand(0), InstID, Vals, VE))
702        AbbrevToUse = FUNCTION_INST_BINOP_ABBREV;
703      Vals.push_back(VE.getValueID(I.getOperand(1)));
704      Vals.push_back(GetEncodedBinaryOpcode(I.getOpcode()));
705    }
706    break;
707
708  case Instruction::GetElementPtr:
709    Code = bitc::FUNC_CODE_INST_GEP;
710    for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
711      PushValueAndType(I.getOperand(i), InstID, Vals, VE);
712    break;
713  case Instruction::Select:
714    Code = bitc::FUNC_CODE_INST_SELECT;
715    PushValueAndType(I.getOperand(1), InstID, Vals, VE);
716    Vals.push_back(VE.getValueID(I.getOperand(2)));
717    Vals.push_back(VE.getValueID(I.getOperand(0)));
718    break;
719  case Instruction::ExtractElement:
720    Code = bitc::FUNC_CODE_INST_EXTRACTELT;
721    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
722    Vals.push_back(VE.getValueID(I.getOperand(1)));
723    break;
724  case Instruction::InsertElement:
725    Code = bitc::FUNC_CODE_INST_INSERTELT;
726    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
727    Vals.push_back(VE.getValueID(I.getOperand(1)));
728    Vals.push_back(VE.getValueID(I.getOperand(2)));
729    break;
730  case Instruction::ShuffleVector:
731    Code = bitc::FUNC_CODE_INST_SHUFFLEVEC;
732    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
733    Vals.push_back(VE.getValueID(I.getOperand(1)));
734    Vals.push_back(VE.getValueID(I.getOperand(2)));
735    break;
736  case Instruction::ICmp:
737  case Instruction::FCmp:
738    Code = bitc::FUNC_CODE_INST_CMP;
739    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
740    Vals.push_back(VE.getValueID(I.getOperand(1)));
741    Vals.push_back(cast<CmpInst>(I).getPredicate());
742    break;
743
744  case Instruction::Ret:
745    Code = bitc::FUNC_CODE_INST_RET;
746    if (!I.getNumOperands())
747      AbbrevToUse = FUNCTION_INST_RET_VOID_ABBREV;
748    else if (!PushValueAndType(I.getOperand(0), InstID, Vals, VE))
749      AbbrevToUse = FUNCTION_INST_RET_VAL_ABBREV;
750    break;
751  case Instruction::Br:
752    Code = bitc::FUNC_CODE_INST_BR;
753    Vals.push_back(VE.getValueID(I.getOperand(0)));
754    if (cast<BranchInst>(I).isConditional()) {
755      Vals.push_back(VE.getValueID(I.getOperand(1)));
756      Vals.push_back(VE.getValueID(I.getOperand(2)));
757    }
758    break;
759  case Instruction::Switch:
760    Code = bitc::FUNC_CODE_INST_SWITCH;
761    Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));
762    for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
763      Vals.push_back(VE.getValueID(I.getOperand(i)));
764    break;
765  case Instruction::Invoke: {
766    const PointerType *PTy = cast<PointerType>(I.getOperand(0)->getType());
767    const FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
768    Code = bitc::FUNC_CODE_INST_INVOKE;
769
770    const InvokeInst *II = cast<InvokeInst>(&I);
771    Vals.push_back(VE.getParamAttrID(II->getParamAttrs()));
772    Vals.push_back(II->getCallingConv());
773    Vals.push_back(VE.getValueID(I.getOperand(1)));      // normal dest
774    Vals.push_back(VE.getValueID(I.getOperand(2)));      // unwind dest
775    PushValueAndType(I.getOperand(0), InstID, Vals, VE); // callee
776
777    // Emit value #'s for the fixed parameters.
778    for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
779      Vals.push_back(VE.getValueID(I.getOperand(i+3)));  // fixed param.
780
781    // Emit type/value pairs for varargs params.
782    if (FTy->isVarArg()) {
783      for (unsigned i = 3+FTy->getNumParams(), e = I.getNumOperands();
784           i != e; ++i)
785        PushValueAndType(I.getOperand(i), InstID, Vals, VE); // vararg
786    }
787    break;
788  }
789  case Instruction::Unwind:
790    Code = bitc::FUNC_CODE_INST_UNWIND;
791    break;
792  case Instruction::Unreachable:
793    Code = bitc::FUNC_CODE_INST_UNREACHABLE;
794    AbbrevToUse = FUNCTION_INST_UNREACHABLE_ABBREV;
795    break;
796
797  case Instruction::PHI:
798    Code = bitc::FUNC_CODE_INST_PHI;
799    Vals.push_back(VE.getTypeID(I.getType()));
800    for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
801      Vals.push_back(VE.getValueID(I.getOperand(i)));
802    break;
803
804  case Instruction::Malloc:
805    Code = bitc::FUNC_CODE_INST_MALLOC;
806    Vals.push_back(VE.getTypeID(I.getType()));
807    Vals.push_back(VE.getValueID(I.getOperand(0))); // size.
808    Vals.push_back(Log2_32(cast<MallocInst>(I).getAlignment())+1);
809    break;
810
811  case Instruction::Free:
812    Code = bitc::FUNC_CODE_INST_FREE;
813    PushValueAndType(I.getOperand(0), InstID, Vals, VE);
814    break;
815
816  case Instruction::Alloca:
817    Code = bitc::FUNC_CODE_INST_ALLOCA;
818    Vals.push_back(VE.getTypeID(I.getType()));
819    Vals.push_back(VE.getValueID(I.getOperand(0))); // size.
820    Vals.push_back(Log2_32(cast<AllocaInst>(I).getAlignment())+1);
821    break;
822
823  case Instruction::Load:
824    Code = bitc::FUNC_CODE_INST_LOAD;
825    if (!PushValueAndType(I.getOperand(0), InstID, Vals, VE))  // ptr
826      AbbrevToUse = FUNCTION_INST_LOAD_ABBREV;
827
828    Vals.push_back(Log2_32(cast<LoadInst>(I).getAlignment())+1);
829    Vals.push_back(cast<LoadInst>(I).isVolatile());
830    break;
831  case Instruction::Store:
832    Code = bitc::FUNC_CODE_INST_STORE;
833    PushValueAndType(I.getOperand(0), InstID, Vals, VE);  // val.
834    Vals.push_back(VE.getValueID(I.getOperand(1)));       // ptr.
835    Vals.push_back(Log2_32(cast<StoreInst>(I).getAlignment())+1);
836    Vals.push_back(cast<StoreInst>(I).isVolatile());
837    break;
838  case Instruction::Call: {
839    const PointerType *PTy = cast<PointerType>(I.getOperand(0)->getType());
840    const FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
841
842    Code = bitc::FUNC_CODE_INST_CALL;
843
844    const CallInst *CI = cast<CallInst>(&I);
845    Vals.push_back(VE.getParamAttrID(CI->getParamAttrs()));
846    Vals.push_back((CI->getCallingConv() << 1) | unsigned(CI->isTailCall()));
847    PushValueAndType(CI->getOperand(0), InstID, Vals, VE);  // Callee
848
849    // Emit value #'s for the fixed parameters.
850    for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i)
851      Vals.push_back(VE.getValueID(I.getOperand(i+1)));  // fixed param.
852
853    // Emit type/value pairs for varargs params.
854    if (FTy->isVarArg()) {
855      unsigned NumVarargs = I.getNumOperands()-1-FTy->getNumParams();
856      for (unsigned i = I.getNumOperands()-NumVarargs, e = I.getNumOperands();
857           i != e; ++i)
858        PushValueAndType(I.getOperand(i), InstID, Vals, VE);  // varargs
859    }
860    break;
861  }
862  case Instruction::VAArg:
863    Code = bitc::FUNC_CODE_INST_VAARG;
864    Vals.push_back(VE.getTypeID(I.getOperand(0)->getType()));   // valistty
865    Vals.push_back(VE.getValueID(I.getOperand(0))); // valist.
866    Vals.push_back(VE.getTypeID(I.getType())); // restype.
867    break;
868  }
869
870  Stream.EmitRecord(Code, Vals, AbbrevToUse);
871  Vals.clear();
872}
873
874// Emit names for globals/functions etc.
875static void WriteValueSymbolTable(const ValueSymbolTable &VST,
876                                  const ValueEnumerator &VE,
877                                  BitstreamWriter &Stream) {
878  if (VST.empty()) return;
879  Stream.EnterSubblock(bitc::VALUE_SYMTAB_BLOCK_ID, 4);
880
881  // FIXME: Set up the abbrev, we know how many values there are!
882  // FIXME: We know if the type names can use 7-bit ascii.
883  SmallVector<unsigned, 64> NameVals;
884
885  for (ValueSymbolTable::const_iterator SI = VST.begin(), SE = VST.end();
886       SI != SE; ++SI) {
887
888    const ValueName &Name = *SI;
889
890    // Figure out the encoding to use for the name.
891    bool is7Bit = true;
892    bool isChar6 = true;
893    for (const char *C = Name.getKeyData(), *E = C+Name.getKeyLength();
894         C != E; ++C) {
895      if (isChar6)
896        isChar6 = BitCodeAbbrevOp::isChar6(*C);
897      if ((unsigned char)*C & 128) {
898        is7Bit = false;
899        break;  // don't bother scanning the rest.
900      }
901    }
902
903    unsigned AbbrevToUse = VST_ENTRY_8_ABBREV;
904
905    // VST_ENTRY:   [valueid, namechar x N]
906    // VST_BBENTRY: [bbid, namechar x N]
907    unsigned Code;
908    if (isa<BasicBlock>(SI->getValue())) {
909      Code = bitc::VST_CODE_BBENTRY;
910      if (isChar6)
911        AbbrevToUse = VST_BBENTRY_6_ABBREV;
912    } else {
913      Code = bitc::VST_CODE_ENTRY;
914      if (isChar6)
915        AbbrevToUse = VST_ENTRY_6_ABBREV;
916      else if (is7Bit)
917        AbbrevToUse = VST_ENTRY_7_ABBREV;
918    }
919
920    NameVals.push_back(VE.getValueID(SI->getValue()));
921    for (const char *P = Name.getKeyData(),
922         *E = Name.getKeyData()+Name.getKeyLength(); P != E; ++P)
923      NameVals.push_back((unsigned char)*P);
924
925    // Emit the finished record.
926    Stream.EmitRecord(Code, NameVals, AbbrevToUse);
927    NameVals.clear();
928  }
929  Stream.ExitBlock();
930}
931
932/// WriteFunction - Emit a function body to the module stream.
933static void WriteFunction(const Function &F, ValueEnumerator &VE,
934                          BitstreamWriter &Stream) {
935  Stream.EnterSubblock(bitc::FUNCTION_BLOCK_ID, 4);
936  VE.incorporateFunction(F);
937
938  SmallVector<unsigned, 64> Vals;
939
940  // Emit the number of basic blocks, so the reader can create them ahead of
941  // time.
942  Vals.push_back(VE.getBasicBlocks().size());
943  Stream.EmitRecord(bitc::FUNC_CODE_DECLAREBLOCKS, Vals);
944  Vals.clear();
945
946  // If there are function-local constants, emit them now.
947  unsigned CstStart, CstEnd;
948  VE.getFunctionConstantRange(CstStart, CstEnd);
949  WriteConstants(CstStart, CstEnd, VE, Stream, false);
950
951  // Keep a running idea of what the instruction ID is.
952  unsigned InstID = CstEnd;
953
954  // Finally, emit all the instructions, in order.
955  for (Function::const_iterator BB = F.begin(), E = F.end(); BB != E; ++BB)
956    for (BasicBlock::const_iterator I = BB->begin(), E = BB->end();
957         I != E; ++I) {
958      WriteInstruction(*I, InstID, VE, Stream, Vals);
959      if (I->getType() != Type::VoidTy)
960        ++InstID;
961    }
962
963  // Emit names for all the instructions etc.
964  WriteValueSymbolTable(F.getValueSymbolTable(), VE, Stream);
965
966  VE.purgeFunction();
967  Stream.ExitBlock();
968}
969
970/// WriteTypeSymbolTable - Emit a block for the specified type symtab.
971static void WriteTypeSymbolTable(const TypeSymbolTable &TST,
972                                 const ValueEnumerator &VE,
973                                 BitstreamWriter &Stream) {
974  if (TST.empty()) return;
975
976  Stream.EnterSubblock(bitc::TYPE_SYMTAB_BLOCK_ID, 3);
977
978  // 7-bit fixed width VST_CODE_ENTRY strings.
979  BitCodeAbbrev *Abbv = new BitCodeAbbrev();
980  Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_ENTRY));
981  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,
982                            Log2_32_Ceil(VE.getTypes().size()+1)));
983  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
984  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 7));
985  unsigned V7Abbrev = Stream.EmitAbbrev(Abbv);
986
987  SmallVector<unsigned, 64> NameVals;
988
989  for (TypeSymbolTable::const_iterator TI = TST.begin(), TE = TST.end();
990       TI != TE; ++TI) {
991    // TST_ENTRY: [typeid, namechar x N]
992    NameVals.push_back(VE.getTypeID(TI->second));
993
994    const std::string &Str = TI->first;
995    bool is7Bit = true;
996    for (unsigned i = 0, e = Str.size(); i != e; ++i) {
997      NameVals.push_back((unsigned char)Str[i]);
998      if (Str[i] & 128)
999        is7Bit = false;
1000    }
1001
1002    // Emit the finished record.
1003    Stream.EmitRecord(bitc::VST_CODE_ENTRY, NameVals, is7Bit ? V7Abbrev : 0);
1004    NameVals.clear();
1005  }
1006
1007  Stream.ExitBlock();
1008}
1009
1010// Emit blockinfo, which defines the standard abbreviations etc.
1011static void WriteBlockInfo(const ValueEnumerator &VE, BitstreamWriter &Stream) {
1012  // We only want to emit block info records for blocks that have multiple
1013  // instances: CONSTANTS_BLOCK, FUNCTION_BLOCK and VALUE_SYMTAB_BLOCK.  Other
1014  // blocks can defined their abbrevs inline.
1015  Stream.EnterBlockInfoBlock(2);
1016
1017  { // 8-bit fixed-width VST_ENTRY/VST_BBENTRY strings.
1018    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1019    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 3));
1020    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
1021    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
1022    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 8));
1023    if (Stream.EmitBlockInfoAbbrev(bitc::VALUE_SYMTAB_BLOCK_ID,
1024                                   Abbv) != VST_ENTRY_8_ABBREV)
1025      assert(0 && "Unexpected abbrev ordering!");
1026  }
1027
1028  { // 7-bit fixed width VST_ENTRY strings.
1029    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1030    Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_ENTRY));
1031    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
1032    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
1033    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 7));
1034    if (Stream.EmitBlockInfoAbbrev(bitc::VALUE_SYMTAB_BLOCK_ID,
1035                                   Abbv) != VST_ENTRY_7_ABBREV)
1036      assert(0 && "Unexpected abbrev ordering!");
1037  }
1038  { // 6-bit char6 VST_ENTRY strings.
1039    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1040    Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_ENTRY));
1041    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
1042    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
1043    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Char6));
1044    if (Stream.EmitBlockInfoAbbrev(bitc::VALUE_SYMTAB_BLOCK_ID,
1045                                   Abbv) != VST_ENTRY_6_ABBREV)
1046      assert(0 && "Unexpected abbrev ordering!");
1047  }
1048  { // 6-bit char6 VST_BBENTRY strings.
1049    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1050    Abbv->Add(BitCodeAbbrevOp(bitc::VST_CODE_BBENTRY));
1051    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
1052    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
1053    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Char6));
1054    if (Stream.EmitBlockInfoAbbrev(bitc::VALUE_SYMTAB_BLOCK_ID,
1055                                   Abbv) != VST_BBENTRY_6_ABBREV)
1056      assert(0 && "Unexpected abbrev ordering!");
1057  }
1058
1059
1060
1061  { // SETTYPE abbrev for CONSTANTS_BLOCK.
1062    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1063    Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_SETTYPE));
1064    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,
1065                              Log2_32_Ceil(VE.getTypes().size()+1)));
1066    if (Stream.EmitBlockInfoAbbrev(bitc::CONSTANTS_BLOCK_ID,
1067                                   Abbv) != CONSTANTS_SETTYPE_ABBREV)
1068      assert(0 && "Unexpected abbrev ordering!");
1069  }
1070
1071  { // INTEGER abbrev for CONSTANTS_BLOCK.
1072    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1073    Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_INTEGER));
1074    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));
1075    if (Stream.EmitBlockInfoAbbrev(bitc::CONSTANTS_BLOCK_ID,
1076                                   Abbv) != CONSTANTS_INTEGER_ABBREV)
1077      assert(0 && "Unexpected abbrev ordering!");
1078  }
1079
1080  { // CE_CAST abbrev for CONSTANTS_BLOCK.
1081    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1082    Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_CE_CAST));
1083    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 4));  // cast opc
1084    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,       // typeid
1085                              Log2_32_Ceil(VE.getTypes().size()+1)));
1086    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8));    // value id
1087
1088    if (Stream.EmitBlockInfoAbbrev(bitc::CONSTANTS_BLOCK_ID,
1089                                   Abbv) != CONSTANTS_CE_CAST_Abbrev)
1090      assert(0 && "Unexpected abbrev ordering!");
1091  }
1092  { // NULL abbrev for CONSTANTS_BLOCK.
1093    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1094    Abbv->Add(BitCodeAbbrevOp(bitc::CST_CODE_NULL));
1095    if (Stream.EmitBlockInfoAbbrev(bitc::CONSTANTS_BLOCK_ID,
1096                                   Abbv) != CONSTANTS_NULL_Abbrev)
1097      assert(0 && "Unexpected abbrev ordering!");
1098  }
1099
1100  // FIXME: This should only use space for first class types!
1101
1102  { // INST_LOAD abbrev for FUNCTION_BLOCK.
1103    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1104    Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_LOAD));
1105    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // Ptr
1106    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 4)); // Align
1107    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1)); // volatile
1108    if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
1109                                   Abbv) != FUNCTION_INST_LOAD_ABBREV)
1110      assert(0 && "Unexpected abbrev ordering!");
1111  }
1112  { // INST_BINOP abbrev for FUNCTION_BLOCK.
1113    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1114    Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_BINOP));
1115    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // LHS
1116    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // RHS
1117    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 4)); // opc
1118    if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
1119                                   Abbv) != FUNCTION_INST_BINOP_ABBREV)
1120      assert(0 && "Unexpected abbrev ordering!");
1121  }
1122  { // INST_CAST abbrev for FUNCTION_BLOCK.
1123    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1124    Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_CAST));
1125    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));    // OpVal
1126    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,       // dest ty
1127                              Log2_32_Ceil(VE.getTypes().size()+1)));
1128    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 4));  // opc
1129    if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
1130                                   Abbv) != FUNCTION_INST_CAST_ABBREV)
1131      assert(0 && "Unexpected abbrev ordering!");
1132  }
1133
1134  { // INST_RET abbrev for FUNCTION_BLOCK.
1135    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1136    Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_RET));
1137    if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
1138                                   Abbv) != FUNCTION_INST_RET_VOID_ABBREV)
1139      assert(0 && "Unexpected abbrev ordering!");
1140  }
1141  { // INST_RET abbrev for FUNCTION_BLOCK.
1142    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1143    Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_RET));
1144    Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // ValID
1145    if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
1146                                   Abbv) != FUNCTION_INST_RET_VAL_ABBREV)
1147      assert(0 && "Unexpected abbrev ordering!");
1148  }
1149  { // INST_UNREACHABLE abbrev for FUNCTION_BLOCK.
1150    BitCodeAbbrev *Abbv = new BitCodeAbbrev();
1151    Abbv->Add(BitCodeAbbrevOp(bitc::FUNC_CODE_INST_UNREACHABLE));
1152    if (Stream.EmitBlockInfoAbbrev(bitc::FUNCTION_BLOCK_ID,
1153                                   Abbv) != FUNCTION_INST_UNREACHABLE_ABBREV)
1154      assert(0 && "Unexpected abbrev ordering!");
1155  }
1156
1157  Stream.ExitBlock();
1158}
1159
1160
1161/// WriteModule - Emit the specified module to the bitstream.
1162static void WriteModule(const Module *M, BitstreamWriter &Stream) {
1163  Stream.EnterSubblock(bitc::MODULE_BLOCK_ID, 3);
1164
1165  // Emit the version number if it is non-zero.
1166  if (CurVersion) {
1167    SmallVector<unsigned, 1> Vals;
1168    Vals.push_back(CurVersion);
1169    Stream.EmitRecord(bitc::MODULE_CODE_VERSION, Vals);
1170  }
1171
1172  // Analyze the module, enumerating globals, functions, etc.
1173  ValueEnumerator VE(M);
1174
1175  // Emit blockinfo, which defines the standard abbreviations etc.
1176  WriteBlockInfo(VE, Stream);
1177
1178  // Emit information about parameter attributes.
1179  WriteParamAttrTable(VE, Stream);
1180
1181  // Emit information describing all of the types in the module.
1182  WriteTypeTable(VE, Stream);
1183
1184  // Emit top-level description of module, including target triple, inline asm,
1185  // descriptors for global variables, and function prototype info.
1186  WriteModuleInfo(M, VE, Stream);
1187
1188  // Emit constants.
1189  WriteModuleConstants(VE, Stream);
1190
1191  // If we have any aggregate values in the value table, purge them - these can
1192  // only be used to initialize global variables.  Doing so makes the value
1193  // namespace smaller for code in functions.
1194  int NumNonAggregates = VE.PurgeAggregateValues();
1195  if (NumNonAggregates != -1) {
1196    SmallVector<unsigned, 1> Vals;
1197    Vals.push_back(NumNonAggregates);
1198    Stream.EmitRecord(bitc::MODULE_CODE_PURGEVALS, Vals);
1199  }
1200
1201  // Emit function bodies.
1202  for (Module::const_iterator I = M->begin(), E = M->end(); I != E; ++I)
1203    if (!I->isDeclaration())
1204      WriteFunction(*I, VE, Stream);
1205
1206  // Emit the type symbol table information.
1207  WriteTypeSymbolTable(M->getTypeSymbolTable(), VE, Stream);
1208
1209  // Emit names for globals/functions etc.
1210  WriteValueSymbolTable(M->getValueSymbolTable(), VE, Stream);
1211
1212  Stream.ExitBlock();
1213}
1214
1215
1216/// WriteBitcodeToFile - Write the specified module to the specified output
1217/// stream.
1218void llvm::WriteBitcodeToFile(const Module *M, std::ostream &Out) {
1219  std::vector<unsigned char> Buffer;
1220  BitstreamWriter Stream(Buffer);
1221
1222  Buffer.reserve(256*1024);
1223
1224  // Emit the file header.
1225  Stream.Emit((unsigned)'B', 8);
1226  Stream.Emit((unsigned)'C', 8);
1227  Stream.Emit(0x0, 4);
1228  Stream.Emit(0xC, 4);
1229  Stream.Emit(0xE, 4);
1230  Stream.Emit(0xD, 4);
1231
1232  // Emit the module.
1233  WriteModule(M, Stream);
1234
1235  // Write the generated bitstream to "Out".
1236  Out.write((char*)&Buffer.front(), Buffer.size());
1237
1238  // Make sure it hits disk now.
1239  Out.flush();
1240}
1241