lib/Bitcode/Writer/BitcodeWriter.cpp

   1 //===--- Bitcode/Writer/Writer.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/Module.h"
  21 #include "llvm/TypeSymbolTable.h"
  22 #include "llvm/ValueSymbolTable.h"
  23 #include "llvm/Support/MathExtras.h"
  24 using namespace llvm;
  25
  26 static const unsigned CurVersion = 0;
  27
  28 static void WriteStringRecord(unsigned Code, const std::string &Str,
  29                               unsigned AbbrevToUse, BitstreamWriter &Stream) {
  30   SmallVector<unsigned, 64> Vals;
  31
  32   // Code: [strlen, strchar x N]
  33   Vals.push_back(Str.size());
  34   for (unsigned i = 0, e = Str.size(); i != e; ++i)
  35     Vals.push_back(Str[i]);
  36
  37   // Emit the finished record.
  38   Stream.EmitRecord(Code, Vals, AbbrevToUse);
  39 }
  40
  41
  42 /// WriteTypeTable - Write out the type table for a module.
  43 static void WriteTypeTable(const ValueEnumerator &VE, BitstreamWriter &Stream) {
  44   const ValueEnumerator::TypeList &TypeList = VE.getTypes();
  45
  46   Stream.EnterSubblock(bitc::TYPE_BLOCK_ID, 4 /*count from # abbrevs */);
  47   SmallVector<uint64_t, 64> TypeVals;
  48
  49   // FIXME: Set up abbrevs now that we know the width of the type fields, etc.
  50
  51   // Emit an entry count so the reader can reserve space.
  52   TypeVals.push_back(TypeList.size());
  53   Stream.EmitRecord(bitc::TYPE_CODE_NUMENTRY, TypeVals);
  54   TypeVals.clear();
  55
  56   // Loop over all of the types, emitting each in turn.
  57   for (unsigned i = 0, e = TypeList.size(); i != e; ++i) {
  58     const Type *T = TypeList[i].first;
  59     int AbbrevToUse = 0;
  60     unsigned Code = 0;
  61
  62     switch (T->getTypeID()) {
  63     case Type::PackedStructTyID: // FIXME: Delete Type::PackedStructTyID.
  64     default: assert(0 && "Unknown type!");
  65     case Type::VoidTyID:   Code = bitc::TYPE_CODE_VOID;   break;
  66     case Type::FloatTyID:  Code = bitc::TYPE_CODE_FLOAT;  break;
  67     case Type::DoubleTyID: Code = bitc::TYPE_CODE_DOUBLE; break;
  68     case Type::LabelTyID:  Code = bitc::TYPE_CODE_LABEL;  break;
  69     case Type::OpaqueTyID: Code = bitc::TYPE_CODE_OPAQUE; break;
  70     case Type::IntegerTyID:
  71       // INTEGER: [width]
  72       Code = bitc::TYPE_CODE_INTEGER;
  73       TypeVals.push_back(cast<IntegerType>(T)->getBitWidth());
  74       break;
  75     case Type::PointerTyID:
  76       // POINTER: [pointee type]
  77       Code = bitc::TYPE_CODE_POINTER;
  78       TypeVals.push_back(VE.getTypeID(cast<PointerType>(T)->getElementType()));
  79       break;
  80
  81     case Type::FunctionTyID: {
  82       const FunctionType *FT = cast<FunctionType>(T);
  83       // FUNCTION: [isvararg, #pararms, paramty x N]
  84       Code = bitc::TYPE_CODE_FUNCTION;
  85       TypeVals.push_back(FT->isVarArg());
  86       TypeVals.push_back(VE.getTypeID(FT->getReturnType()));
  87       // FIXME: PARAM ATTR ID!
  88       TypeVals.push_back(FT->getNumParams());
  89       for (unsigned i = 0, e = FT->getNumParams(); i != e; ++i)
  90         TypeVals.push_back(VE.getTypeID(FT->getParamType(i)));
  91       break;
  92     }
  93     case Type::StructTyID: {
  94       const StructType *ST = cast<StructType>(T);
  95       // STRUCT: [ispacked, #elts, eltty x N]
  96       Code = bitc::TYPE_CODE_STRUCT;
  97       TypeVals.push_back(ST->isPacked());
  98       TypeVals.push_back(ST->getNumElements());
  99       // Output all of the element types...
 100       for (StructType::element_iterator I = ST->element_begin(),
 101            E = ST->element_end(); I != E; ++I)
 102         TypeVals.push_back(VE.getTypeID(*I));
 103       break;
 104     }
 105     case Type::ArrayTyID: {
 106       const ArrayType *AT = cast<ArrayType>(T);
 107       // ARRAY: [numelts, eltty]
 108       Code = bitc::TYPE_CODE_ARRAY;
 109       TypeVals.push_back(AT->getNumElements());
 110       TypeVals.push_back(VE.getTypeID(AT->getElementType()));
 111       break;
 112     }
 113     case Type::VectorTyID: {
 114       const VectorType *VT = cast<VectorType>(T);
 115       // VECTOR [numelts, eltty]
 116       Code = bitc::TYPE_CODE_VECTOR;
 117       TypeVals.push_back(VT->getNumElements());
 118       TypeVals.push_back(VE.getTypeID(VT->getElementType()));
 119       break;
 120     }
 121     }
 122
 123     // Emit the finished record.
 124     Stream.EmitRecord(Code, TypeVals, AbbrevToUse);
 125     TypeVals.clear();
 126   }
 127
 128   Stream.ExitBlock();
 129 }
 130
 131 static unsigned getEncodedLinkage(const GlobalValue *GV) {
 132   switch (GV->getLinkage()) {
 133   default: assert(0 && "Invalid linkage!");
 134   case GlobalValue::ExternalLinkage:     return 0;
 135   case GlobalValue::WeakLinkage:         return 1;
 136   case GlobalValue::AppendingLinkage:    return 2;
 137   case GlobalValue::InternalLinkage:     return 3;
 138   case GlobalValue::LinkOnceLinkage:     return 4;
 139   case GlobalValue::DLLImportLinkage:    return 5;
 140   case GlobalValue::DLLExportLinkage:    return 6;
 141   case GlobalValue::ExternalWeakLinkage: return 7;
 142   }
 143 }
 144
 145 static unsigned getEncodedVisibility(const GlobalValue *GV) {
 146   switch (GV->getVisibility()) {
 147   default: assert(0 && "Invalid visibility!");
 148   case GlobalValue::DefaultVisibility: return 0;
 149   case GlobalValue::HiddenVisibility:  return 1;
 150   }
 151 }
 152
 153 // Emit top-level description of module, including target triple, inline asm,
 154 // descriptors for global variables, and function prototype info.
 155 static void WriteModuleInfo(const Module *M, const ValueEnumerator &VE,
 156                             BitstreamWriter &Stream) {
 157   // Emit the list of dependent libraries for the Module.
 158   for (Module::lib_iterator I = M->lib_begin(), E = M->lib_end(); I != E; ++I)
 159     WriteStringRecord(bitc::MODULE_CODE_DEPLIB, *I, 0/*TODO*/, Stream);
 160
 161   // Emit various pieces of data attached to a module.
 162   if (!M->getTargetTriple().empty())
 163     WriteStringRecord(bitc::MODULE_CODE_TRIPLE, M->getTargetTriple(),
 164                       0/*TODO*/, Stream);
 165   if (!M->getDataLayout().empty())
 166     WriteStringRecord(bitc::MODULE_CODE_DATALAYOUT, M->getDataLayout(),
 167                       0/*TODO*/, Stream);
 168   if (!M->getModuleInlineAsm().empty())
 169     WriteStringRecord(bitc::MODULE_CODE_ASM, M->getModuleInlineAsm(),
 170                       0/*TODO*/, Stream);
 171
 172   // Emit information about sections, computing how many there are.  Also
 173   // compute the maximum alignment value.
 174   std::map<std::string, unsigned> SectionMap;
 175   unsigned MaxAlignment = 0;
 176   unsigned MaxGlobalType = 0;
 177   for (Module::const_global_iterator GV = M->global_begin(),E = M->global_end();
 178        GV != E; ++GV) {
 179     MaxAlignment = std::max(MaxAlignment, GV->getAlignment());
 180     MaxGlobalType = std::max(MaxGlobalType, VE.getTypeID(GV->getType()));
 181
 182     if (!GV->hasSection()) continue;
 183     // Give section names unique ID's.
 184     unsigned &Entry = SectionMap[GV->getSection()];
 185     if (Entry != 0) continue;
 186     WriteStringRecord(bitc::MODULE_CODE_SECTIONNAME, GV->getSection(),
 187                       0/*TODO*/, Stream);
 188     Entry = SectionMap.size();
 189   }
 190   for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) {
 191     MaxAlignment = std::max(MaxAlignment, F->getAlignment());
 192     if (!F->hasSection()) continue;
 193     // Give section names unique ID's.
 194     unsigned &Entry = SectionMap[F->getSection()];
 195     if (Entry != 0) continue;
 196     WriteStringRecord(bitc::MODULE_CODE_SECTIONNAME, F->getSection(),
 197                       0/*TODO*/, Stream);
 198     Entry = SectionMap.size();
 199   }
 200
 201   // Emit abbrev for globals, now that we know # sections and max alignment.
 202   unsigned SimpleGVarAbbrev = 0;
 203   if (!M->global_empty()) {
 204     // Add an abbrev for common globals with no visibility or thread localness.
 205     BitCodeAbbrev *Abbv = new BitCodeAbbrev();
 206     Abbv->Add(BitCodeAbbrevOp(bitc::MODULE_CODE_GLOBALVAR));
 207     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::FixedWidth,
 208                               Log2_32_Ceil(MaxGlobalType+1)));
 209     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::FixedWidth, 1)); // Constant.
 210     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6));        // Initializer.
 211     Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::FixedWidth, 3)); // Linkage.
 212     if (MaxAlignment == 0)                                     // Alignment.
 213       Abbv->Add(BitCodeAbbrevOp(0));
 214     else {
 215       unsigned MaxEncAlignment = Log2_32(MaxAlignment)+1;
 216       Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::FixedWidth,
 217                                Log2_32_Ceil(MaxEncAlignment+1)));
 218     }
 219     if (SectionMap.empty())                                    // Section.
 220       Abbv->Add(BitCodeAbbrevOp(0));
 221     else
 222       Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::FixedWidth,
 223                                Log2_32_Ceil(SectionMap.size()+1)));
 224     // Don't bother emitting vis + thread local.
 225     SimpleGVarAbbrev = Stream.EmitAbbrev(Abbv);
 226   }
 227
 228   // Emit the global variable information.
 229   SmallVector<unsigned, 64> Vals;
 230   for (Module::const_global_iterator GV = M->global_begin(),E = M->global_end();
 231        GV != E; ++GV) {
 232     unsigned AbbrevToUse = 0;
 233
 234     // GLOBALVAR: [type, isconst, initid,
 235     //             linkage, alignment, section, visibility, threadlocal]
 236     Vals.push_back(VE.getTypeID(GV->getType()));
 237     Vals.push_back(GV->isConstant());
 238     Vals.push_back(GV->isDeclaration() ? 0 :
 239                    (VE.getValueID(GV->getInitializer()) + 1));
 240     Vals.push_back(getEncodedLinkage(GV));
 241     Vals.push_back(Log2_32(GV->getAlignment())+1);
 242     Vals.push_back(GV->hasSection() ? SectionMap[GV->getSection()] : 0);
 243     if (GV->isThreadLocal() ||
 244         GV->getVisibility() != GlobalValue::DefaultVisibility) {
 245       Vals.push_back(getEncodedVisibility(GV));
 246       Vals.push_back(GV->isThreadLocal());
 247     } else {
 248       AbbrevToUse = SimpleGVarAbbrev;
 249     }
 250
 251     Stream.EmitRecord(bitc::MODULE_CODE_GLOBALVAR, Vals, AbbrevToUse);
 252     Vals.clear();
 253   }
 254
 255   // Emit the function proto information.
 256   for (Module::const_iterator F = M->begin(), E = M->end(); F != E; ++F) {
 257     // FUNCTION:  [type, callingconv, isproto, linkage, alignment, section,
 258     //             visibility]
 259     Vals.push_back(VE.getTypeID(F->getType()));
 260     Vals.push_back(F->getCallingConv());
 261     Vals.push_back(F->isDeclaration());
 262     Vals.push_back(getEncodedLinkage(F));
 263     Vals.push_back(Log2_32(F->getAlignment())+1);
 264     Vals.push_back(F->hasSection() ? SectionMap[F->getSection()] : 0);
 265     Vals.push_back(getEncodedVisibility(F));
 266
 267     unsigned AbbrevToUse = 0;
 268     Stream.EmitRecord(bitc::MODULE_CODE_FUNCTION, Vals, AbbrevToUse);
 269     Vals.clear();
 270   }
 271 }
 272
 273
 274 /// WriteTypeSymbolTable - Emit a block for the specified type symtab.
 275 static void WriteTypeSymbolTable(const TypeSymbolTable &TST,
 276                                  const ValueEnumerator &VE,
 277                                  BitstreamWriter &Stream) {
 278   if (TST.empty()) return;
 279
 280   Stream.EnterSubblock(bitc::TYPE_SYMTAB_BLOCK_ID, 3);
 281
 282   // FIXME: Set up the abbrev, we know how many types there are!
 283   // FIXME: We know if the type names can use 7-bit ascii.
 284
 285   SmallVector<unsigned, 64> NameVals;
 286
 287   for (TypeSymbolTable::const_iterator TI = TST.begin(), TE = TST.end();
 288        TI != TE; ++TI) {
 289     unsigned AbbrevToUse = 0;
 290
 291     // TST_ENTRY: [typeid, namelen, namechar x N]
 292     NameVals.push_back(VE.getTypeID(TI->second));
 293
 294     const std::string &Str = TI->first;
 295     NameVals.push_back(Str.size());
 296     for (unsigned i = 0, e = Str.size(); i != e; ++i)
 297       NameVals.push_back(Str[i]);
 298
 299     // Emit the finished record.
 300     Stream.EmitRecord(bitc::VST_CODE_ENTRY, NameVals, AbbrevToUse);
 301     NameVals.clear();
 302   }
 303
 304   Stream.ExitBlock();
 305 }
 306
 307 // Emit names for globals/functions etc.
 308 static void WriteValueSymbolTable(const ValueSymbolTable &VST,
 309                                   const ValueEnumerator &VE,
 310                                   BitstreamWriter &Stream) {
 311   if (VST.empty()) return;
 312   Stream.EnterSubblock(bitc::VALUE_SYMTAB_BLOCK_ID, 3);
 313
 314   // FIXME: Set up the abbrev, we know how many values there are!
 315   // FIXME: We know if the type names can use 7-bit ascii.
 316   SmallVector<unsigned, 64> NameVals;
 317
 318   for (ValueSymbolTable::const_iterator SI = VST.begin(), SE = VST.end();
 319        SI != SE; ++SI) {
 320     unsigned AbbrevToUse = 0;
 321
 322     // VST_ENTRY: [valueid, namelen, namechar x N]
 323     NameVals.push_back(VE.getValueID(SI->getValue()));
 324
 325     NameVals.push_back(SI->getKeyLength());
 326     for (const char *P = SI->getKeyData(),
 327          *E = SI->getKeyData()+SI->getKeyLength(); P != E; ++P)
 328       NameVals.push_back((unsigned char)*P);
 329
 330     // Emit the finished record.
 331     Stream.EmitRecord(bitc::VST_CODE_ENTRY, NameVals, AbbrevToUse);
 332     NameVals.clear();
 333   }
 334   Stream.ExitBlock();
 335 }
 336
 337 static void WriteConstants(unsigned FirstVal, unsigned LastVal,
 338                            const ValueEnumerator &VE,
 339                            BitstreamWriter &Stream) {
 340   if (FirstVal == LastVal) return;
 341
 342   Stream.EnterSubblock(bitc::CONSTANTS_BLOCK_ID, 2);
 343
 344   // FIXME: Install and use abbrevs to reduce size.
 345
 346   SmallVector<uint64_t, 64> Record;
 347
 348   const ValueEnumerator::ValueList &Vals = VE.getValues();
 349   const Type *LastTy = 0;
 350   for (unsigned i = FirstVal; i != LastVal; ++i) {
 351     const Value *V = Vals[i].first;
 352     // If we need to switch types, do so now.
 353     if (V->getType() != LastTy) {
 354       LastTy = V->getType();
 355       Record.push_back(VE.getTypeID(LastTy));
 356       Stream.EmitRecord(bitc::CST_CODE_SETTYPE, Record);
 357       Record.clear();
 358     }
 359
 360     if (const InlineAsm *IA = dyn_cast<InlineAsm>(V)) {
 361       assert(0 && IA && "FIXME: Inline asm writing unimp!");
 362       continue;
 363     }
 364     const Constant *C = cast<Constant>(V);
 365     unsigned Code = -1U;
 366     unsigned AbbrevToUse = 0;
 367     if (C->isNullValue()) {
 368       Code = bitc::CST_CODE_NULL;
 369     } else if (isa<UndefValue>(C)) {
 370       Code = bitc::CST_CODE_UNDEF;
 371     } else if (const ConstantInt *IV = dyn_cast<ConstantInt>(C)) {
 372       if (IV->getBitWidth() <= 64) {
 373         int64_t V = IV->getSExtValue();
 374         if (V >= 0)
 375           Record.push_back(V << 1);
 376         else
 377           Record.push_back((-V << 1) | 1);
 378         Code = bitc::CST_CODE_INTEGER;
 379       } else {                             // Wide integers, > 64 bits in size.
 380         // We have an arbitrary precision integer value to write whose
 381         // bit width is > 64. However, in canonical unsigned integer
 382         // format it is likely that the high bits are going to be zero.
 383         // So, we only write the number of active words.
 384         unsigned NWords = IV->getValue().getActiveWords();
 385         const uint64_t *RawWords = IV->getValue().getRawData();
 386         Record.push_back(NWords);
 387         for (unsigned i = 0; i != NWords; ++i) {
 388           int64_t V = RawWords[i];
 389           if (V >= 0)
 390             Record.push_back(V << 1);
 391           else
 392             Record.push_back((-V << 1) | 1);
 393         }
 394         Code = bitc::CST_CODE_WIDE_INTEGER;
 395       }
 396     } else if (const ConstantFP *CFP = dyn_cast<ConstantFP>(C)) {
 397       Code = bitc::CST_CODE_FLOAT;
 398       if (CFP->getType() == Type::FloatTy) {
 399         Record.push_back(FloatToBits((float)CFP->getValue()));
 400       } else {
 401         assert (CFP->getType() == Type::DoubleTy && "Unknown FP type!");
 402         Record.push_back(DoubleToBits((double)CFP->getValue()));
 403       }
 404     } else if (isa<ConstantArray>(C) || isa<ConstantStruct>(V) ||
 405                isa<ConstantVector>(V)) {
 406       Code = bitc::CST_CODE_AGGREGATE;
 407       Record.push_back(C->getNumOperands());
 408       for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i)
 409         Record.push_back(VE.getValueID(C->getOperand(i)));
 410     } else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
 411       Code = bitc::CST_CODE_CONSTEXPR;
 412       // FIXME: optimize for binops, compares, etc.
 413       Record.push_back(CE->getOpcode());
 414       Record.push_back(CE->getNumOperands());
 415       for (unsigned i = 0, e = CE->getNumOperands(); i != e; ++i)
 416         Record.push_back(VE.getValueID(C->getOperand(i)));
 417       // Compares also pass their predicate.
 418       if (CE->isCompare())
 419         Record.push_back((unsigned)CE->getPredicate());
 420     } else {
 421       assert(0 && "Unknown constant!");
 422     }
 423     Stream.EmitRecord(Code, Record, AbbrevToUse);
 424     Record.clear();
 425   }
 426
 427   Stream.ExitBlock();
 428 }
 429
 430 static void WriteModuleConstants(const ValueEnumerator &VE,
 431                                  BitstreamWriter &Stream) {
 432   const ValueEnumerator::ValueList &Vals = VE.getValues();
 433
 434   // Find the first constant to emit, which is the first non-globalvalue value.
 435   // We know globalvalues have been emitted by WriteModuleInfo.
 436   for (unsigned i = 0, e = Vals.size(); i != e; ++i) {
 437     if (!isa<GlobalValue>(Vals[i].first)) {
 438       WriteConstants(i, Vals.size(), VE, Stream);
 439       return;
 440     }
 441   }
 442 }
 443
 444 /// WriteModule - Emit the specified module to the bitstream.
 445 static void WriteModule(const Module *M, BitstreamWriter &Stream) {
 446   Stream.EnterSubblock(bitc::MODULE_BLOCK_ID, 3);
 447
 448   // Emit the version number if it is non-zero.
 449   if (CurVersion) {
 450     SmallVector<unsigned, 1> VersionVals;
 451     VersionVals.push_back(CurVersion);
 452     Stream.EmitRecord(bitc::MODULE_CODE_VERSION, VersionVals);
 453   }
 454
 455   // Analyze the module, enumerating globals, functions, etc.
 456   ValueEnumerator VE(M);
 457
 458   // Emit information describing all of the types in the module.
 459   WriteTypeTable(VE, Stream);
 460
 461   // Emit top-level description of module, including target triple, inline asm,
 462   // descriptors for global variables, and function prototype info.
 463   WriteModuleInfo(M, VE, Stream);
 464
 465   // Emit constants.
 466   WriteModuleConstants(VE, Stream);
 467
 468   // Emit the type symbol table information.
 469   WriteTypeSymbolTable(M->getTypeSymbolTable(), VE, Stream);
 470
 471   // Emit names for globals/functions etc.
 472   WriteValueSymbolTable(M->getValueSymbolTable(), VE, Stream);
 473
 474   Stream.ExitBlock();
 475 }
 476
 477 /// WriteBitcodeToFile - Write the specified module to the specified output
 478 /// stream.
 479 void llvm::WriteBitcodeToFile(const Module *M, std::ostream &Out) {
 480   std::vector<unsigned char> Buffer;
 481   BitstreamWriter Stream(Buffer);
 482
 483   Buffer.reserve(256*1024);
 484
 485   // Emit the file header.
 486   Stream.Emit((unsigned)'B', 8);
 487   Stream.Emit((unsigned)'C', 8);
 488   Stream.Emit(0x0, 4);
 489   Stream.Emit(0xC, 4);
 490   Stream.Emit(0xE, 4);
 491   Stream.Emit(0xD, 4);
 492
 493   // Emit the module.
 494   WriteModule(M, Stream);
 495
 496   // Write the generated bitstream to "Out".
 497   Out.write((char*)&Buffer.front(), Buffer.size());
 498 }