bug 263:

- encode/decode target triple and dependent libraries
bug 401:
- fix encoding/decoding of FP values to be little-endian only
bug 402:
- initial (compatible) cut at 24-bit types instead of 32-bit
- reduce size of block headers by 50%
Other:
- cleanup Writer by consolidating to one compilation unit, rem. other files
- use a std::vector instead of std::deque so the buffer can be allocated
  in multiples of 64KByte chunks rather than in multiples of some smaller
  (default) number.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@15210 91177308-0d34-0410-b5e6-96231b3b80d8

7 files changed, 1003 insertions, 811 deletions

diff --git a/lib/Bytecode/Reader/Reader.cpp b/lib/Bytecode/Reader/Reader.cpp
index 4d1ee41242..d19651ffb4 100644
--- a/lib/Bytecode/Reader/Reader.cpp
+++ b/lib/Bytecode/Reader/Reader.cpp
@@ -156,24 +156,79 @@ inline void BytecodeReader::read_data(void *Ptr, void *End) {
 
 /// Read a float value in little-endian order
 inline void BytecodeReader::read_float(float& FloatVal) {
-  /// FIXME: This is a broken implementation! It reads
-  /// it in a platform-specific endianess. Need to make
-  /// it little endian always.
-  read_data(&FloatVal, &FloatVal+1);
+  if (hasPlatformSpecificFloatingPoint) {
+    read_data(&FloatVal, &FloatVal+1);
+  } else {
+    /// FIXME: This isn't optimal, it has size problems on some platforms
+    /// where FP is not IEEE.
+    union {
+      float f;
+      uint32_t i;
+    } FloatUnion;
+    FloatUnion.i = At[0] | (At[1] << 8) | (At[2] << 16) | (At[3] << 24);
+    At+=sizeof(uint32_t);
+    FloatVal = FloatUnion.f;
+  }
 }
 
 /// Read a double value in little-endian order
 inline void BytecodeReader::read_double(double& DoubleVal) {
-  /// FIXME: This is a broken implementation! It reads
-  /// it in a platform-specific endianess. Need to make
-  /// it little endian always.
-  read_data(&DoubleVal, &DoubleVal+1);
+  if (hasPlatformSpecificFloatingPoint) {
+    read_data(&DoubleVal, &DoubleVal+1);
+  } else {
+    /// FIXME: This isn't optimal, it has size problems on some platforms
+    /// where FP is not IEEE.
+    union {
+      double d;
+      uint64_t i;
+    } DoubleUnion;
+    DoubleUnion.i = At[0] | (At[1] << 8) | (At[2] << 16) | (At[3] << 24) |
+                    (uint64_t(At[4]) << 32) | (uint64_t(At[5]) << 40) | 
+                    (uint64_t(At[6]) << 48) | (uint64_t(At[7]) << 56);
+    At+=sizeof(uint64_t);
+    DoubleVal = DoubleUnion.d;
+  }
 }
 
 /// Read a block header and obtain its type and size
 inline void BytecodeReader::read_block(unsigned &Type, unsigned &Size) {
-  Type = read_uint();
-  Size = read_uint();
+  if ( hasLongBlockHeaders ) {
+    Type = read_uint();
+    Size = read_uint();
+    switch (Type) {
+    case BytecodeFormat::Reserved_DoNotUse : 
+      error("Reserved_DoNotUse used as Module Type?");
+      Type = BytecodeFormat::Module; break;
+    case BytecodeFormat::Module: 
+      Type = BytecodeFormat::ModuleBlockID; break;
+    case BytecodeFormat::Function:
+      Type = BytecodeFormat::FunctionBlockID; break;
+    case BytecodeFormat::ConstantPool:
+      Type = BytecodeFormat::ConstantPoolBlockID; break;
+    case BytecodeFormat::SymbolTable:
+      Type = BytecodeFormat::SymbolTableBlockID; break;
+    case BytecodeFormat::ModuleGlobalInfo:
+      Type = BytecodeFormat::ModuleGlobalInfoBlockID; break;
+    case BytecodeFormat::GlobalTypePlane:
+      Type = BytecodeFormat::GlobalTypePlaneBlockID; break;
+    case BytecodeFormat::InstructionList:
+      Type = BytecodeFormat::InstructionListBlockID; break;
+    case BytecodeFormat::CompactionTable:
+      Type = BytecodeFormat::CompactionTableBlockID; break;
+    case BytecodeFormat::BasicBlock:
+      /// This block type isn't used after version 1.1. However, we have to
+      /// still allow the value in case this is an old bc format file.
+      /// We just let its value creep thru.
+      break;
+    default:
+      error("Invalid module type found: " + utostr(Type));
+      break;
+    }
+  } else {
+    Size = read_uint();
+    Type = Size & 0x1F; // mask low order five bits
+    Size >>= 5; // get rid of five low order bits, leaving high 27
+  }
   BlockStart = At;
   if (At + Size > BlockEnd)
     error("Attempt to size a block past end of memory");
@@ -216,6 +271,9 @@ inline bool BytecodeReader::sanitizeTypeId(unsigned &TypeId) {
 /// @see sanitizeTypeId
 inline bool BytecodeReader::read_typeid(unsigned &TypeId) {
   TypeId = read_vbr_uint();
+  if ( !has32BitTypes )
+    if ( TypeId == 0x00FFFFFF )
+      TypeId = read_vbr_uint();
   return sanitizeTypeId(TypeId);
 }
 
@@ -1504,7 +1562,7 @@ void BytecodeReader::ParseFunctionBody(Function* F) {
     read_block(Type, Size);
 
     switch (Type) {
-    case BytecodeFormat::ConstantPool:
+    case BytecodeFormat::ConstantPoolBlockID:
       if (!InsertedArguments) {
         // Insert arguments into the value table before we parse the first basic
         // block in the function, but after we potentially read in the
@@ -1516,7 +1574,7 @@ void BytecodeReader::ParseFunctionBody(Function* F) {
       ParseConstantPool(FunctionValues, FunctionTypes, true);
       break;
 
-    case BytecodeFormat::CompactionTable:
+    case BytecodeFormat::CompactionTableBlockID:
       ParseCompactionTable();
       break;
 
@@ -1534,7 +1592,7 @@ void BytecodeReader::ParseFunctionBody(Function* F) {
       break;
     }
 
-    case BytecodeFormat::InstructionList: {
+    case BytecodeFormat::InstructionListBlockID: {
       // Insert arguments into the value table before we parse the instruction
       // list for the function, but after we potentially read in the compaction
       // table.
@@ -1549,7 +1607,7 @@ void BytecodeReader::ParseFunctionBody(Function* F) {
       break;
     }
 
-    case BytecodeFormat::SymbolTable:
+    case BytecodeFormat::SymbolTableBlockID:
       ParseSymbolTable(F, &F->getSymbolTable());
       break;
 
@@ -1784,13 +1842,28 @@ void BytecodeReader::ParseModuleGlobalInfo() {
       error("Invalid function type (type type) found");
   }
 
-  if (hasInconsistentModuleGlobalInfo)
-    align32();
-
   // Now that the function signature list is set up, reverse it so that we can 
   // remove elements efficiently from the back of the vector.
   std::reverse(FunctionSignatureList.begin(), FunctionSignatureList.end());
 
+  // If this bytecode format has dependent library information in it ..
+  if (!hasNoDependentLibraries) {
+    // Read in the number of dependent library items that follow
+    unsigned num_dep_libs = read_vbr_uint();
+    std::string dep_lib;
+    while( num_dep_libs-- ) {
+      dep_lib = read_str();
+      TheModule->linsert(dep_lib);
+    }
+
+    // Read target triple and place into the module
+    std::string triple = read_str();
+    TheModule->setTargetTriple(triple);
+  }
+
+  if (hasInconsistentModuleGlobalInfo)
+    align32();
+
   // This is for future proofing... in the future extra fields may be added that
   // we don't understand, so we transparently ignore them.
   //
@@ -1820,6 +1893,10 @@ void BytecodeReader::ParseVersionInfo() {
   hasExplicitPrimitiveZeros = false;
   hasRestrictedGEPTypes = false;
   hasTypeDerivedFromValue = false;
+  hasLongBlockHeaders = false;
+  hasPlatformSpecificFloatingPoint = false;
+  has32BitTypes = false;
+  hasNoDependentLibraries = false;
 
   switch (RevisionNum) {
   case 0:               //  LLVM 1.0, 1.1 release version
@@ -1827,6 +1904,7 @@ void BytecodeReader::ParseVersionInfo() {
     hasInconsistentModuleGlobalInfo = true;
     hasExplicitPrimitiveZeros = true;
 
+
     // FALL THROUGH
   case 1:               // LLVM 1.2 release version
     // LLVM 1.2 added explicit support for emitting strings efficiently.
@@ -1846,7 +1924,35 @@ void BytecodeReader::ParseVersionInfo() {
     hasTypeDerivedFromValue = true;
 
     // FALL THROUGH
-  case 2:               // LLVM 1.3 release version
+    
+  case 2:  /// 1.2.5 (mid-release) version
+
+    /// LLVM 1.2 and earlier had two-word block headers. This is a bit wasteful,
+    /// especially for small files where the 8 bytes per block is a large fraction
+    /// of the total block size. In LLVM 1.3, the block type and length are 
+    /// compressed into a single 32-bit unsigned integer. 27 bits for length, 5
+    /// bits for block type.
+    hasLongBlockHeaders = true;
+
+    /// LLVM 1.2 and earlier wrote floating point values in a platform specific
+    /// bit ordering. This was fixed in LLVM 1.3, but we still need to be backwards
+    /// compatible.
+    hasPlatformSpecificFloatingPoint = true;
+
+    /// LLVM 1.2 and earlier wrote type slot numbers as vbr_uint32. In LLVM 1.3
+    /// this has been reduced to vbr_uint24. It shouldn't make much difference 
+    /// since we haven't run into a module with > 24 million types, but for safety
+    /// the 24-bit restriction has been enforced in 1.3 to free some bits in
+    /// various places and to ensure consistency.
+    has32BitTypes = true;
+
+    /// LLVM 1.2 and earlier did not provide a target triple nor a list of 
+    /// libraries on which the bytecode is dependent. LLVM 1.3 provides these
+    /// features, for use in future versions of LLVM.
+    hasNoDependentLibraries = true;
+
+    // FALL THROUGH
+  case 3:               // LLVM 1.3 release version
     break;
 
   default:
@@ -1870,7 +1976,7 @@ void BytecodeReader::ParseModule() {
 
   // Read into instance variables...
   ParseVersionInfo();
-  align32(); /// FIXME: Is this redundant? VI is first and 4 bytes!
+  align32();
 
   bool SeenModuleGlobalInfo = false;
   bool SeenGlobalTypePlane = false;
@@ -1881,7 +1987,7 @@ void BytecodeReader::ParseModule() {
 
     switch (Type) {
 
-    case BytecodeFormat::GlobalTypePlane:
+    case BytecodeFormat::GlobalTypePlaneBlockID:
       if (SeenGlobalTypePlane)
         error("Two GlobalTypePlane Blocks Encountered!");
 
@@ -1889,22 +1995,22 @@ void BytecodeReader::ParseModule() {
       SeenGlobalTypePlane = true;
       break;
 
-    case BytecodeFormat::ModuleGlobalInfo: 
+    case BytecodeFormat::ModuleGlobalInfoBlockID: 
       if (SeenModuleGlobalInfo)
         error("Two ModuleGlobalInfo Blocks Encountered!");
       ParseModuleGlobalInfo();
       SeenModuleGlobalInfo = true;
       break;
 
-    case BytecodeFormat::ConstantPool:
+    case BytecodeFormat::ConstantPoolBlockID:
       ParseConstantPool(ModuleValues, ModuleTypes,false);
       break;
 
-    case BytecodeFormat::Function:
+    case BytecodeFormat::FunctionBlockID:
       ParseFunctionLazily();
       break;
 
-    case BytecodeFormat::SymbolTable:
+    case BytecodeFormat::SymbolTableBlockID:
       ParseSymbolTable(0, &TheModule->getSymbolTable());
       break;
 
@@ -1967,14 +2073,16 @@ void BytecodeReader::ParseBytecode(BufPtr Buf, unsigned Length,
       error("Invalid bytecode signature: " + utostr(Sig));
     }
 
-
     // Tell the handler we're starting a module
     if (Handler) Handler->handleModuleBegin(ModuleID);
 
-    // Get the module block and size and verify
+    // Get the module block and size and verify. This is handled specially
+    // because the module block/size is always written in long format. Other
+    // blocks are written in short format so the read_block method is used.
     unsigned Type, Size;
-    read_block(Type, Size);
-    if (Type != BytecodeFormat::Module) {
+    Type = read_uint();
+    Size = read_uint();
+    if (Type != BytecodeFormat::ModuleBlockID) {
       error("Expected Module Block! Type:" + utostr(Type) + ", Size:" 
             + utostr(Size));
     }
diff --git a/lib/Bytecode/Reader/Reader.h b/lib/Bytecode/Reader/Reader.h
index 9120377130..c93958419c 100644
--- a/lib/Bytecode/Reader/Reader.h
+++ b/lib/Bytecode/Reader/Reader.h
@@ -56,6 +56,7 @@ public:
 /// @name Types
 /// @{
 public:
+
   /// @brief A convenience type for the buffer pointer
   typedef const unsigned char* BufPtr;
 
@@ -268,6 +269,36 @@ private:
   /// from Value style of bytecode file is being read.
   bool hasTypeDerivedFromValue;
 
+  /// LLVM 1.2 and earlier encoded block headers as two uint (8 bytes), one for
+  /// the size and one for the type. This is a bit wasteful, especially for small 
+  /// files where the 8 bytes per block is a large fraction of the total block 
+  /// size. In LLVM 1.3, the block type and length are encoded into a single 
+  /// uint32 by restricting the number of block types (limit 31) and the maximum
+  /// size of a block (limit 2^27-1=134,217,727). Note that the module block
+  /// still uses the 8-byte format so the maximum size of a file can be
+  /// 2^32-1 bytes long.
+  bool hasLongBlockHeaders;
+
+  /// LLVM 1.2 and earlier wrote floating point values in a platform specific
+  /// bit ordering. This was fixed in LLVM 1.3
+  bool hasPlatformSpecificFloatingPoint;
+
+  /// LLVM 1.2 and earlier wrote type slot numbers as vbr_uint32. In LLVM 1.3
+  /// this has been reduced to vbr_uint24. It shouldn't make much difference 
+  /// since we haven't run into a module with > 24 million types, but for safety
+  /// the 24-bit restriction has been enforced in 1.3 to free some bits in
+  /// various places and to ensure consistency. In particular, global vars are
+  /// restricted to 24-bits.
+  bool has32BitTypes;
+
+  /// LLVM 1.2 and earlier did not provide a target triple nor a list of 
+  /// libraries on which the bytecode is dependent. LLVM 1.3 provides these
+  /// features, for use in future versions of LLVM.
+  bool hasNoDependentLibraries;
+
+  /// LLVM 1.2 and earlier encoded the file version as part of the module block
+  /// but this information may be needed to
+
   /// CompactionTable - If a compaction table is active in the current function,
   /// this is the mapping that it contains.
   std::vector<const Type*> CompactionTypes;
@@ -430,6 +461,10 @@ private:
   /// @brief Read an unsigned integer with variable bit rate encoding
   inline unsigned read_vbr_uint();
 
+  /// @brief Read an unsigned integer of no more than 24-bits with variable
+  /// bit rate encoding.
+  inline unsigned read_vbr_uint24();
+
   /// @brief Read an unsigned 64-bit integer with variable bit rate encoding.
   inline uint64_t read_vbr_uint64();
 
diff --git a/lib/Bytecode/Writer/ConstantWriter.cpp b/lib/Bytecode/Writer/ConstantWriter.cpp
deleted file mode 100644
index 7aa8febda3..0000000000
--- a/lib/Bytecode/Writer/ConstantWriter.cpp
+++ /dev/null
@@ -1,220 +0,0 @@
-//===-- ConstantWriter.cpp - Functions for writing constants --------------===//
-// 
-//                     The LLVM Compiler Infrastructure
-//
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
-// 
-//===----------------------------------------------------------------------===//
-//
-// This file implements the routines for encoding constants to a bytecode 
-// stream.
-//
-//===----------------------------------------------------------------------===//
-
-#include "WriterInternals.h"
-#include "llvm/Constants.h"
-#include "llvm/SymbolTable.h"
-#include "llvm/DerivedTypes.h"
-#include "Support/Statistic.h"
-using namespace llvm;
-
-void BytecodeWriter::outputType(const Type *T) {
-  output_vbr((unsigned)T->getTypeID(), Out);
-  
-  // That's all there is to handling primitive types...
-  if (T->isPrimitiveType()) {
-    return;     // We might do this if we alias a prim type: %x = type int
-  }
-
-  switch (T->getTypeID()) {   // Handle derived types now.
-  case Type::FunctionTyID: {
-    const FunctionType *MT = cast<FunctionType>(T);
-    int Slot = Table.getSlot(MT->getReturnType());
-    assert(Slot != -1 && "Type used but not available!!");
-    output_vbr((unsigned)Slot, Out);
-
-    // Output the number of arguments to function (+1 if varargs):
-    output_vbr((unsigned)MT->getNumParams()+MT->isVarArg(), Out);
-
-    // Output all of the arguments...
-    FunctionType::param_iterator I = MT->param_begin();
-    for (; I != MT->param_end(); ++I) {
-      Slot = Table.getSlot(*I);
-      assert(Slot != -1 && "Type used but not available!!");
-      output_vbr((unsigned)Slot, Out);
-    }
-
-    // Terminate list with VoidTy if we are a varargs function...
-    if (MT->isVarArg())
-      output_vbr((unsigned)Type::VoidTyID, Out);
-    break;
-  }
-
-  case Type::ArrayTyID: {
-    const ArrayType *AT = cast<ArrayType>(T);
-    int Slot = Table.getSlot(AT->getElementType());
-    assert(Slot != -1 && "Type used but not available!!");
-    output_vbr((unsigned)Slot, Out);
-    //std::cerr << "Type slot = " << Slot << " Type = " << T->getName() << endl;
-
-    output_vbr(AT->getNumElements(), Out);
-    break;
-  }
-
-  case Type::StructTyID: {
-    const StructType *ST = cast<StructType>(T);
-
-    // Output all of the element types...
-    for (StructType::element_iterator I = ST->element_begin(),
-           E = ST->element_end(); I != E; ++I) {
-      int Slot = Table.getSlot(*I);
-      assert(Slot != -1 && "Type used but not available!!");
-      output_vbr((unsigned)Slot, Out);
-    }
-
-    // Terminate list with VoidTy
-    output_vbr((unsigned)Type::VoidTyID, Out);
-    break;
-  }
-
-  case Type::PointerTyID: {
-    const PointerType *PT = cast<PointerType>(T);
-    int Slot = Table.getSlot(PT->getElementType());
-    assert(Slot != -1 && "Type used but not available!!");
-    output_vbr((unsigned)Slot, Out);
-    break;
-  }
-
-  case Type::OpaqueTyID: {
-    // No need to emit anything, just the count of opaque types is enough.
-    break;
-  }
-
-  //case Type::PackedTyID:
-  default:
-    std::cerr << __FILE__ << ":" << __LINE__ << ": Don't know how to serialize"
-              << " Type '" << T->getDescription() << "'\n";
-    break;
-  }
-}
-
-void BytecodeWriter::outputConstant(const Constant *CPV) {
-  assert((CPV->getType()->isPrimitiveType() || !CPV->isNullValue()) &&
-         "Shouldn't output null constants!");
-
-  // We must check for a ConstantExpr before switching by type because
-  // a ConstantExpr can be of any type, and has no explicit value.
-  // 
-  if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(CPV)) {
-    // FIXME: Encoding of constant exprs could be much more compact!
-    assert(CE->getNumOperands() > 0 && "ConstantExpr with 0 operands");
-    output_vbr(CE->getNumOperands(), Out);   // flags as an expr
-    output_vbr(CE->getOpcode(), Out);        // flags as an expr
-    
-    for (User::const_op_iterator OI = CE->op_begin(); OI != CE->op_end(); ++OI){
-      int Slot = Table.getSlot(*OI);
-      assert(Slot != -1 && "Unknown constant used in ConstantExpr!!");
-      output_vbr((unsigned)Slot, Out);
-      Slot = Table.getSlot((*OI)->getType());
-      output_vbr((unsigned)Slot, Out);
-    }
-    return;
-  } else {
-    output_vbr(0U, Out);       // flag as not a ConstantExpr
-  }
-  
-  switch (CPV->getType()->getTypeID()) {
-  case Type::BoolTyID:    // Boolean Types
-    if (cast<ConstantBool>(CPV)->getValue())
-      output_vbr(1U, Out);
-    else
-      output_vbr(0U, Out);
-    break;
-
-  case Type::UByteTyID:   // Unsigned integer types...
-  case Type::UShortTyID:
-  case Type::UIntTyID:
-  case Type::ULongTyID:
-    output_vbr(cast<ConstantUInt>(CPV)->getValue(), Out);
-    break;
-
-  case Type::SByteTyID:   // Signed integer types...
-  case Type::ShortTyID:
-  case Type::IntTyID:
-  case Type::LongTyID:
-    output_vbr(cast<ConstantSInt>(CPV)->getValue(), Out);
-    break;
-
-  case Type::ArrayTyID: {
-    const ConstantArray *CPA = cast<ConstantArray>(CPV);
-    assert(!CPA->isString() && "Constant strings should be handled specially!");
-
-    for (unsigned i = 0; i != CPA->getNumOperands(); ++i) {
-      int Slot = Table.getSlot(CPA->getOperand(i));
-      assert(Slot != -1 && "Constant used but not available!!");
-      output_vbr((unsigned)Slot, Out);
-    }
-    break;
-  }
-
-  case Type::StructTyID: {
-    const ConstantStruct *CPS = cast<ConstantStruct>(CPV);
-    const std::vector<Use> &Vals = CPS->getValues();
-
-    for (unsigned i = 0; i < Vals.size(); ++i) {
-      int Slot = Table.getSlot(Vals[i]);
-      assert(Slot != -1 && "Constant used but not available!!");
-      output_vbr((unsigned)Slot, Out);
-    }
-    break;
-  }
-
-  case Type::PointerTyID:
-    assert(0 && "No non-null, non-constant-expr constants allowed!");
-    abort();
-
-  case Type::FloatTyID: {   // Floating point types...
-    float Tmp = (float)cast<ConstantFP>(CPV)->getValue();
-    output_float(Tmp, Out);
-    break;
-  }
-  case Type::DoubleTyID: {
-    double Tmp = cast<ConstantFP>(CPV)->getValue();
-    output_double(Tmp, Out);
-    break;
-  }
-
-  case Type::VoidTyID: 
-  case Type::LabelTyID:
-  default:
-    std::cerr << __FILE__ << ":" << __LINE__ << ": Don't know how to serialize"
-              << " type '" << *CPV->getType() << "'\n";
-    break;
-  }
-  return;
-}
-
-void BytecodeWriter::outputConstantStrings() {
-  SlotCalculator::string_iterator I = Table.string_begin();
-  SlotCalculator::string_iterator E = Table.string_end();
-  if (I == E) return;  // No strings to emit
-
-  // If we have != 0 strings to emit, output them now.  Strings are emitted into
-  // the 'void' type plane.
-  output_vbr(unsigned(E-I), Out);
-  output_vbr(Type::VoidTyID, Out);
-    
-  // Emit all of the strings.
-  for (I = Table.string_begin(); I != E; ++I) {
-    const ConstantArray *Str = *I;
-    int Slot = Table.getSlot(Str->getType());
-    assert(Slot != -1 && "Constant string of unknown type?");
-    output_vbr((unsigned)Slot, Out);
-    
-    // Now that we emitted the type (which indicates the size of the string),
-    // emit all of the characters.
-    std::string Val = Str->getAsString();
-    output_data(Val.c_str(), Val.c_str()+Val.size(), Out);
-  }
-}
diff --git a/lib/Bytecode/Writer/InstructionWriter.cpp b/lib/Bytecode/Writer/InstructionWriter.cpp
deleted file mode 100644
index 188136718d..0000000000
--- a/lib/Bytecode/Writer/InstructionWriter.cpp
+++ /dev/null
@@ -1,348 +0,0 @@
-//===-- InstructionWriter.cpp - Functions for writing instructions --------===//
-// 
-//                     The LLVM Compiler Infrastructure
-//
-// This file was developed by the LLVM research group and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
-// 
-//===----------------------------------------------------------------------===//
-//
-// This file implements the routines for encoding instruction opcodes to a 
-// bytecode stream.
-//
-//===----------------------------------------------------------------------===//
-
-#include "WriterInternals.h"
-#include "llvm/Module.h"
-#include "llvm/DerivedTypes.h"
-#include "llvm/Instructions.h"
-#include "llvm/Support/GetElementPtrTypeIterator.h"
-#include "Support/Statistic.h"
-#include <algorithm>
-using namespace llvm;
-
-typedef unsigned char uchar;
-
-// outputInstructionFormat0 - Output those wierd instructions that have a large
-// number of operands or have large operands themselves...
-//
-// Format: [opcode] [type] [numargs] [arg0] [arg1] ... [arg<numargs-1>]
-//
-static void outputInstructionFormat0(const Instruction *I, unsigned Opcode,
-				     const SlotCalculator &Table,
-				     unsigned Type, std::deque<uchar> &Out) {
-  // Opcode must have top two bits clear...
-  output_vbr(Opcode << 2, Out);                  // Instruction Opcode ID
-  output_vbr(Type, Out);                         // Result type
-
-  unsigned NumArgs = I->getNumOperands();
-  output_vbr(NumArgs + (isa<CastInst>(I) || isa<VANextInst>(I) ||
-                        isa<VAArgInst>(I)), Out);
-
-  if (!isa<GetElementPtrInst>(&I)) {
-    for (unsigned i = 0; i < NumArgs; ++i) {
-      int Slot = Table.getSlot(I->getOperand(i));
-      assert(Slot >= 0 && "No slot number for value!?!?");      
-      output_vbr((unsigned)Slot, Out);
-    }
-
-    if (isa<CastInst>(I) || isa<VAArgInst>(I)) {
-      int Slot = Table.getSlot(I->getType());
-      assert(Slot != -1 && "Cast return type unknown?");
-      output_vbr((unsigned)Slot, Out);
-    } else if (const VANextInst *VAI = dyn_cast<VANextInst>(I)) {
-      int Slot = Table.getSlot(VAI->getArgType());
-      assert(Slot != -1 && "VarArg argument type unknown?");
-      output_vbr((unsigned)Slot, Out);
-    }
-
-  } else {
-    int Slot = Table.getSlot(I->getOperand(0));
-    assert(Slot >= 0 && "No slot number for value!?!?");      
-    output_vbr(unsigned(Slot), Out);
-
-    // We need to encode the type of sequential type indices into their slot #
-    unsigned Idx = 1;
-    for (gep_type_iterator TI = gep_type_begin(I), E = gep_type_end(I);
-         Idx != NumArgs; ++TI, ++Idx) {
-      Slot = Table.getSlot(I->getOperand(Idx));
-      assert(Slot >= 0 && "No slot number for value!?!?");      
-    
-      if (isa<SequentialType>(*TI)) {
-        unsigned IdxId;
-        switch (I->getOperand(Idx)->getType()->getTypeID()) {
-        default: assert(0 && "Unknown index type!");
-        case Type::UIntTyID:  IdxId = 0; break;
-        case Type::IntTyID:   IdxId = 1; break;
-        case Type::ULongTyID: IdxId = 2; break;
-        case Type::LongTyID:  IdxId = 3; break;
-        }
-        Slot = (Slot << 2) | IdxId;
-      }
-      output_vbr(unsigned(Slot), Out);
-    }
-  }
-
-  align32(Out);    // We must maintain correct alignment!
-}
-
-
-// outputInstrVarArgsCall - Output the absurdly annoying varargs function calls.
-// This are more annoying than most because the signature of the call does not
-// tell us anything about the types of the arguments in the varargs portion.
-// Because of this, we encode (as type 0) all of the argument types explicitly
-// before the argument value.  This really sucks, but you shouldn't be using
-// varargs functions in your code! *death to printf*!
-//
-// Format: [opcode] [type] [numargs] [arg0] [arg1] ... [arg<numargs-1>]
-//
-static void outputInstrVarArgsCall(const Instruction *I, unsigned Opcode,
-				   const SlotCalculator &Table, unsigned Type,
-				   std::deque<uchar> &Out) {
-  assert(isa<CallInst>(I) || isa<InvokeInst>(I));
-  // Opcode must have top two bits clear...
-  output_vbr(Opcode << 2, Out);                  // Instruction Opcode ID
-  output_vbr(Type, Out);                         // Result type (varargs type)
-
-  const PointerType *PTy = cast<PointerType>(I->getOperand(0)->getType());
-  const FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
-  unsigned NumParams = FTy->getNumParams();
-
-  unsigned NumFixedOperands;
-  if (isa<CallInst>(I)) {
-    // Output an operand for the callee and each fixed argument, then two for
-    // each variable argument.
-    NumFixedOperands = 1+NumParams;
-  } else {
-    assert(isa<InvokeInst>(I) && "Not call or invoke??");
-    // Output an operand for the callee and destinations, then two for each
-    // variable argument.
-    NumFixedOperands = 3+NumParams;
-  }
-  output_vbr(2 * I->getNumOperands()-NumFixedOperands, Out);
-
-  // The type for the function has already been emitted in the type field of the
-  // instruction.  Just emit the slot # now.
-  for (unsigned i = 0; i != NumFixedOperands; ++i) {
-    int Slot = Table.getSlot(I->getOperand(i));
-    assert(Slot >= 0 && "No slot number for value!?!?");      
-    output_vbr((unsigned)Slot, Out);
-  }
-
-  for (unsigned i = NumFixedOperands, e = I->getNumOperands(); i != e; ++i) {
-    // Output Arg Type ID
-    int Slot = Table.getSlot(I->getOperand(i)->getType());
-    assert(Slot >= 0 && "No slot number for value!?!?");      
-    output_vbr((unsigned)Slot, Out);
-    
-    // Output arg ID itself
-    Slot = Table.getSlot(I->getOperand(i));
-    assert(Slot >= 0 && "No slot number for value!?!?");      
-    output_vbr((unsigned)Slot, Out);
-  }
-  align32(Out);    // We must maintain correct alignment!
-}
-
-
-// outputInstructionFormat1 - Output one operand instructions, knowing that no
-// operand index is >= 2^12.
-//
-static void outputInstructionFormat1(const Instruction *I, unsigned Opcode,
-				     const SlotCalculator &Table,
-                                     unsigned *Slots, unsigned Type, 
-                                     std::deque<uchar> &Out) {
-  // bits   Instruction format:
-  // --------------------------
-  // 01-00: Opcode type, fixed to 1.
-  // 07-02: Opcode
-  // 19-08: Resulting type plane
-  // 31-20: Operand #1 (if set to (2^12-1), then zero operands)
-  //
-  unsigned Bits = 1 | (Opcode << 2) | (Type << 8) | (Slots[0] << 20);
-  //  cerr << "1 " << IType << " " << Type << " " << Slots[0] << endl;
-  output(Bits, Out);
-}
-
-
-// outputInstructionFormat2 - Output two operand instructions, knowing that no
-// operand index is >= 2^8.
-//
-static void outputInstructionFormat2(const Instruction *I, unsigned Opcode,
-				     const SlotCalculator &Table,
-                                     unsigned *Slots, unsigned Type, 
-                                     std::deque<uchar> &Out) {
-  // bits   Instruction format:
-  // --------------------------
-  // 01-00: Opcode type, fixed to 2.
-  // 07-02: Opcode
-  // 15-08: Resulting type plane
-  // 23-16: Operand #1
-  // 31-24: Operand #2  
-  //
-  unsigned Bits = 2 | (Opcode << 2) | (Type << 8) |
-                    (Slots[0] << 16) | (Slots[1] << 24);
-  //  cerr << "2 " << IType << " " << Type << " " << Slots[0] << " " 
-  //       << Slots[1] << endl;
-  output(Bits, Out);
-}
-
-
-// outputInstructionFormat3 - Output three operand instructions, knowing that no
-// operand index is >= 2^6.
-//
-static void outputInstructionFormat3(const Instruction *I, unsigned Opcode,
-				     const SlotCalculator &Table,
-                                     unsigned *Slots, unsigned Type,
-                                     std::deque<uchar> &Out) {
-  // bits   Instruction format:
-  // --------------------------
-  // 01-00: Opcode type, fixed to 3.
-  // 07-02: Opcode
-  // 13-08: Resulting type plane
-  // 19-14: Operand #1
-  // 25-20: Operand #2
-  // 31-26: Operand #3
-  //
-  unsigned Bits = 3 | (Opcode << 2) | (Type << 8) |
-          (Slots[0] << 14) | (Slots[1] << 20) | (Slots[2] << 26);
-  //cerr << "3 " << IType << " " << Type << " " << Slots[0] << " " 
-  //     << Slots[1] << " " << Slots[2] << endl;
-  output(Bits, Out);
-}
-
-void BytecodeWriter::outputInstruction(const Instruction &I) {
-  assert(I.getOpcode() < 62 && "Opcode too big???");
-  unsigned Opcode = I.getOpcode();
-  unsigned NumOperands = I.getNumOperands();
-
-  // Encode 'volatile load' as 62 and 'volatile store' as 63.
-  if (isa<LoadInst>(I) && cast<LoadInst>(I).isVolatile())
-    Opcode = 62;
-  if (isa<StoreInst>(I) && cast<StoreInst>(I).isVolatile())
-    Opcode = 63;
-
-  // Figure out which type to encode with the instruction.  Typically we want
-  // the type of the first parameter, as opposed to the type of the instruction
-  // (for example, with setcc, we always know it returns bool, but the type of
-  // the first param is actually interesting).  But if we have no arguments
-  // we take the type of the instruction itself.  
-  //
-  const Type *Ty;
-  switch (I.getOpcode()) {
-  case Instruction::Select:
-  case Instruction::Malloc:
-  case Instruction::Alloca:
-    Ty = I.getType();  // These ALWAYS want to encode the return type
-    break;
-  case Instruction::Store:
-    Ty = I.getOperand(1)->getType();  // Encode the pointer type...
-    assert(isa<PointerType>(Ty) && "Store to nonpointer type!?!?");
-    break;
-  default:              // Otherwise use the default behavior...
-    Ty = NumOperands ? I.getOperand(0)->getType() : I.getType();
-    break;
-  }
-
-  unsigned Type;
-  int Slot = Table.getSlot(Ty);
-  assert(Slot != -1 && "Type not available!!?!");
-  Type = (unsigned)Slot;
-
-  // Varargs calls and invokes are encoded entirely different from any other
-  // instructions.
-  if (const CallInst *CI = dyn_cast<CallInst>(&I)){
-    const PointerType *Ty =cast<PointerType>(CI->getCalledValue()->getType());
-    if (cast<FunctionType>(Ty->getElementType())->isVarArg()) {
-      outputInstrVarArgsCall(CI, Opcode, Table, Type, Out);
-      return;
-    }
-  } else if (const InvokeInst *II = dyn_cast<InvokeInst>(&I)) {
-    const PointerType *Ty =cast<PointerType>(II->getCalledValue()->getType());
-    if (cast<FunctionType>(Ty->getElementType())->isVarArg()) {
-      outputInstrVarArgsCall(II, Opcode, Table, Type, Out);
-      return;
-    }
-  }
-
-  if (NumOperands <= 3) {
-    // Make sure that we take the type number into consideration.  We don't want
-    // to overflow the field size for the instruction format we select.
-    //
-    unsigned MaxOpSlot = Type;
-    unsigned Slots[3]; Slots[0] = (1 << 12)-1;   // Marker to signify 0 operands
-    
-    for (unsigned i = 0; i != NumOperands; ++i) {
-      int slot = Table.getSlot(I.getOperand(i));
-      assert(slot != -1 && "Broken bytecode!");
-      if (unsigned(slot) > MaxOpSlot) MaxOpSlot = unsigned(slot);
-      Slots[i] = unsigned(slot);
-    }
-
-    // Handle the special cases for various instructions...
-    if (isa<CastInst>(I) || isa<VAArgInst>(I)) {
-      // Cast has to encode the destination type as the second argument in the
-      // packet, or else we won't know what type to cast to!
-      Slots[1] = Table.getSlot(I.getType());
-      assert(Slots[1] != ~0U && "Cast return type unknown?");
-      if (Slots[1] > MaxOpSlot) MaxOpSlot = Slots[1];
-      NumOperands++;
-    } else if (const VANextInst *VANI = dyn_cast<VANextInst>(&I)) {
-      Slots[1] = Table.getSlot(VANI->getArgType());
-      assert(Slots[1] != ~0U && "va_next return type unknown?");
-      if (Slots[1] > MaxOpSlot) MaxOpSlot = Slots[1];
-      NumOperands++;
-    } else if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&I)) {
-      // We need to encode the type of sequential type indices into their slot #
-      unsigned Idx = 1;
-      for (gep_type_iterator I = gep_type_begin(GEP), E = gep_type_end(GEP);
-           I != E; ++I, ++Idx)
-        if (isa<SequentialType>(*I)) {
-          unsigned IdxId;
-          switch (GEP->getOperand(Idx)->getType()->getTypeID()) {