Packed types, brought to you by Brad Jones

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

15 files changed, 460 insertions, 17 deletions

diff --git a/docs/BytecodeFormat.html b/docs/BytecodeFormat.html
index 51b56463bc..3345023112 100644
--- a/docs/BytecodeFormat.html
+++ b/docs/BytecodeFormat.html
@@ -888,6 +888,27 @@ missing otherwise.</td>
     </tr>
   </tbody>
 </table>
+<h3>Packed Types</h3>
+<table>
+  <tbody>
+    <tr>
+      <th><b>Type</b></th>
+      <th class="td_left"><b>Description</b></th>
+    </tr>
+    <tr>
+      <td><a href="#uint24_vbr">uint24_vbr</a></td>
+      <td class="td_left">Type ID for Packed Types (18)</td>
+    </tr>
+    <tr>
+      <td><a href="#uint24_vbr">uint24_vbr</a></td>
+      <td class="td_left">Slot number of packed vector's element type.</td>
+    </tr>
+    <tr>
+      <td><a href="#uint32_vbr">uint32_vbr</a></td>
+      <td class="td_left">The number of elements in the packed vector.</td>
+    </tr>
+  </tbody>
+</table>
 </div>
 <!-- _______________________________________________________________________ -->
 <div class="doc_subsection"><a name="globalinfo">Module Global Info</a>
diff --git a/include/llvm/Bytecode/BytecodeHandler.h b/include/llvm/Bytecode/BytecodeHandler.h
index 687bf806e0..5a022a04c0 100644
--- a/include/llvm/Bytecode/BytecodeHandler.h
+++ b/include/llvm/Bytecode/BytecodeHandler.h
@@ -23,6 +23,7 @@ namespace llvm {
 class ArrayType;
 class StructType;
 class PointerType;
+class PackedType;
 class ConstantArray;
 class Module;
 
@@ -250,6 +251,14 @@ public:
     Constant* Val                       ///< The constant value
   ) {}
 
+  /// @brief Handle a constant packed
+  virtual void handleConstantPacked( 
+    const PackedType* PT,                ///< Type of the array
+    std::vector<Constant*>& ElementSlots,///< Slot nums for packed values
+    unsigned TypeSlot,                  ///< Slot # of type
+    Constant* Val                       ///< The constant value
+  ) {}
+
   /// @brief Handle a constant pointer
   virtual void handleConstantPointer( 
     const PointerType* PT, ///< Type of the pointer
diff --git a/include/llvm/Constants.h b/include/llvm/Constants.h
index 74541c9ef4..5ef2cb0132 100644
--- a/include/llvm/Constants.h
+++ b/include/llvm/Constants.h
@@ -24,6 +24,7 @@ namespace llvm {
 class ArrayType;
 class StructType;
 class PointerType;
+class PackedType;
 
 template<class ConstantClass, class TypeClass, class ValType>
 struct ConstantCreator;
@@ -426,6 +427,44 @@ public:
 };
 
 //===---------------------------------------------------------------------------
+/// ConstantPacked - Constant Packed Declarations
+///
+class ConstantPacked : public Constant {
+  friend struct ConstantCreator<ConstantPacked, PackedType,
+                                    std::vector<Constant*> >;
+  ConstantPacked(const ConstantPacked &);      // DO NOT IMPLEMENT
+protected:
+  ConstantPacked(const PackedType *T, const std::vector<Constant*> &Val);
+public:
+  /// get() - Static factory methods - Return objects of the specified value
+  static Constant *get(const PackedType *T, const std::vector<Constant*> &);
+  static Constant *get(const std::vector<Constant*> &V);
+  
+  /// getType - Specialize the getType() method to always return an PackedType,
+  /// which reduces the amount of casting needed in parts of the compiler.
+  ///
+  inline const PackedType *getType() const {
+    return reinterpret_cast<const PackedType*>(Value::getType());
+  }
+
+  /// isNullValue - Return true if this is the value that would be returned by
+  /// getNullValue.  This always returns false because zero arrays are always
+  /// created as ConstantAggregateZero objects.
+  virtual bool isNullValue() const { return false; }
+
+  virtual void destroyConstant();
+  virtual void replaceUsesOfWithOnConstant(Value *From, Value *To,
+                                           bool DisableChecking = false);
+
+  /// Methods for support type inquiry through isa, cast, and dyn_cast:
+  static inline bool classof(const ConstantPacked *) { return true; }
+  static bool classof(const Value *V) {
+    return V->getValueType() == SimpleConstantVal &&
+           V->getType()->getTypeID() == Type::PackedTyID;
+  }
+};
+
+//===---------------------------------------------------------------------------
 /// ConstantPointerNull - a constant pointer value that points to null
 ///
 class ConstantPointerNull : public Constant {
diff --git a/include/llvm/DerivedTypes.h b/include/llvm/DerivedTypes.h
index 8720ca6815..10f74dc4f0 100644
--- a/include/llvm/DerivedTypes.h
+++ b/include/llvm/DerivedTypes.h
@@ -28,6 +28,7 @@ class FunctionValType;
 class ArrayValType;
 class StructValType;
 class PointerValType;
+class PackedValType;
 
 class DerivedType : public Type, public AbstractTypeUser {
   // AbstractTypeUsers - Implement a list of the users that need to be notified
@@ -152,8 +153,8 @@ public:
 };
 
 
-/// CompositeType - Common super class of ArrayType, StructType, and PointerType
-///
+/// CompositeType - Common super class of ArrayType, StructType, PointerType
+/// and PackedType
 class CompositeType : public DerivedType {
 protected:
   inline CompositeType(TypeID id) : DerivedType(id) { }
@@ -170,7 +171,8 @@ public:
   static inline bool classof(const Type *T) {
     return T->getTypeID() == ArrayTyID || 
            T->getTypeID() == StructTyID ||
-           T->getTypeID() == PointerTyID;
+           T->getTypeID() == PointerTyID ||
+           T->getTypeID() == PackedTyID;
   }
 };
 
@@ -227,11 +229,13 @@ public:
 };
 
 
-/// SequentialType - This is the superclass of the array and pointer type
-/// classes.  Both of these represent "arrays" in memory.  The array type
+/// SequentialType - This is the superclass of the array, pointer and packed 
+/// type classes.  All of these represent "arrays" in memory.  The array type
 /// represents a specifically sized array, pointer types are unsized/unknown
-/// size arrays.  SequentialType holds the common features of both, which stem
-/// from the fact that both lay their components out in memory identically.
+/// size arrays, packed types represent specifically sized arrays that 
+/// allow for use of SIMD instructions.  SequentialType holds the common 
+/// features of all, which stem from the fact that all three lay their 
+/// components out in memory identically.
 ///
 class SequentialType : public CompositeType {
   SequentialType(const SequentialType &);                  // Do not implement!
@@ -258,7 +262,8 @@ public:
   static inline bool classof(const SequentialType *T) { return true; }
   static inline bool classof(const Type *T) {
     return T->getTypeID() == ArrayTyID ||
-           T->getTypeID() == PointerTyID;
+           T->getTypeID() == PointerTyID ||
+           T->getTypeID() == PackedTyID;
   }
 };
 
@@ -299,6 +304,42 @@ public:
   }
 };
 
+/// PackedType - Class to represent packed types
+///
+class PackedType : public SequentialType {
+  friend class TypeMap<PackedValType, PackedType>;
+  unsigned NumElements;
+
+  PackedType(const PackedType &);                   // Do not implement
+  const PackedType &operator=(const PackedType &);  // Do not implement
+protected:
+  /// This should really be private, but it squelches a bogus warning
+  /// from GCC to make them protected:  warning: `class PackedType' only 
+  /// defines private constructors and has no friends
+  ///
+  /// Private ctor - Only can be created by a static member...
+  ///
+  PackedType(const Type *ElType, unsigned NumEl);
+
+public:
+  /// PackedType::get - This static method is the primary way to construct an
+  /// PackedType
+  ///
+  static PackedType *get(const Type *ElementType, unsigned NumElements);
+
+  inline unsigned    getNumElements() const { return NumElements; }
+
+  // Implement the AbstractTypeUser interface.
+  virtual void refineAbstractType(const DerivedType *OldTy, const Type *NewTy);
+  virtual void typeBecameConcrete(const DerivedType *AbsTy);
+
+  // Methods for support type inquiry through isa, cast, and dyn_cast:
+  static inline bool classof(const PackedType *T) { return true; }
+  static inline bool classof(const Type *T) {
+    return T->getTypeID() == PackedTyID;
+  }
+};
+
 
 /// PointerType - Class to represent pointers
 ///
diff --git a/include/llvm/Type.def b/include/llvm/Type.def
index 8e59c7adb6..25ad5cd3bd 100644
--- a/include/llvm/Type.def
+++ b/include/llvm/Type.def
@@ -58,6 +58,7 @@ HANDLE_DERV_TYPE(Array   , ArrayType)
 HANDLE_DERV_TYPE(Pointer , PointerType)
 HANDLE_DERV_TYPE(Struct  , StructType)
 HANDLE_DERV_TYPE(Opaque  , OpaqueType)
+HANDLE_DERV_TYPE(Packed  , PackedType)
 
 // Kill the macros on exit...
 #undef HANDLE_PRIM_TYPE
diff --git a/include/llvm/Type.h b/include/llvm/Type.h
index 273cd439c8..fcaa9f5669 100644
--- a/include/llvm/Type.h
+++ b/include/llvm/Type.h
@@ -48,6 +48,7 @@ class FunctionType;
 class OpaqueType;
 class PointerType;
 class StructType;
+class PackedType;
 
 struct Type {
   ///===-------------------------------------------------------------------===//
@@ -71,7 +72,7 @@ struct Type {
     FunctionTyID  , StructTyID,         // Functions... Structs...
     ArrayTyID     , PointerTyID,        // Array... pointer...
     OpaqueTyID,                         // Opaque type instances...
-    //PackedTyID  ,                     // SIMD 'packed' format... TODO
+    PackedTyID,                         // SIMD 'packed' format... 
     //...
 
     NumTypeIDs,                         // Must remain as last defined ID
@@ -189,7 +190,8 @@ public:
 
   /// isFirstClassType - Return true if the value is holdable in a register.
   inline bool isFirstClassType() const {
-    return (ID != VoidTyID && ID <= LastPrimitiveTyID) || ID == PointerTyID;
+    return (ID != VoidTyID && ID <= LastPrimitiveTyID) || 
+            ID == PointerTyID || ID == PackedTyID;
   }
 
   /// isSized - Return true if it makes sense to take the size of this type.  To
@@ -197,7 +199,7 @@ public:
   /// TargetData subsystem to do this.
   ///
   bool isSized() const {
-    return (ID >= BoolTyID && ID <= DoubleTyID) || ID == PointerTyID ||
+    return (ID >= BoolTyID && ID <= DoubleTyID) || ID == PointerTyID || 
            isSizedDerivedType();
   }
 
diff --git a/lib/AsmParser/llvmAsmParser.y b/lib/AsmParser/llvmAsmParser.y
index e48d6cfc9f..1a4ad32a97 100644
--- a/lib/AsmParser/llvmAsmParser.y
+++ b/lib/AsmParser/llvmAsmParser.y
@@ -1033,6 +1033,17 @@ UpRTypes : '\\' EUINT64VAL {                   // Type UpReference
     $$ = new PATypeHolder(HandleUpRefs(ArrayType::get(*$4, (unsigned)$2)));
     delete $4;
   }
+  | '<' EUINT64VAL 'x' UpRTypes '>' {          // Packed array type?
+     const llvm::Type* ElemTy = $4->get();
+     if ((unsigned)$2 != $2) {
+        ThrowException("Unsigned result not equal to signed result");
+     }
+     if(!ElemTy->isPrimitiveType()) {
+        ThrowException("Elemental type of a PackedType must be primitive");
+     }
+     $$ = new PATypeHolder(HandleUpRefs(PackedType::get(*$4, (unsigned)$2)));
+     delete $4;
+  }
   | '{' TypeListI '}' {                        // Structure type?
     std::vector<const Type*> Elements;
     mapto($2->begin(), $2->end(), std::back_inserter(Elements), 
@@ -1144,6 +1155,31 @@ ConstVal: Types '[' ConstVector ']' { // Nonempty unsized arr
     $$ = ConstantArray::get(ATy, Vals);
     delete $1;
   }
+  | Types '<' ConstVector '>' { // Nonempty unsized arr
+    const PackedType *PTy = dyn_cast<PackedType>($1->get());
+    if (PTy == 0)
+      ThrowException("Cannot make packed constant with type: '" + 
+                     (*$1)->getDescription() + "'!");
+    const Type *ETy = PTy->getElementType();
+    int NumElements = PTy->getNumElements();
+
+    // Verify that we have the correct size...
+    if (NumElements != -1 && NumElements != (int)$3->size())
+      ThrowException("Type mismatch: constant sized packed initialized with " +
+                     utostr($3->size()) +  " arguments, but has size of " + 
+                     itostr(NumElements) + "!");
+
+    // Verify all elements are correct type!
+    for (unsigned i = 0; i < $3->size(); i++) {
+      if (ETy != (*$3)[i]->getType())
+        ThrowException("Element #" + utostr(i) + " is not of type '" + 
+           ETy->getDescription() +"' as required!\nIt is of type '"+
+           (*$3)[i]->getType()->getDescription() + "'.");
+    }
+
+    $$ = ConstantPacked::get(PTy, *$3);
+    delete $1; delete $3;
+  }
   | Types '{' ConstVector '}' {
     const StructType *STy = dyn_cast<StructType>($1->get());
     if (STy == 0)
@@ -1651,6 +1687,30 @@ ConstValueRef : ESINT64VAL {    // A reference to a direct constant
   | NULL_TOK {
     $$ = ValID::createNull();
   }
+  | '<' ConstVector '>' { // Nonempty unsized packed vector
+    const Type *ETy = (*$2)[0]->getType();
+    int NumElements = $2->size(); 
+    
+    PackedType* pt = PackedType::get(ETy, NumElements);
+    PATypeHolder* PTy = new PATypeHolder(
+                                         HandleUpRefs(
+                                            PackedType::get(
+                                                ETy, 
+                                                NumElements)
+                                            )
+                                         );
+    
+    // Verify all elements are correct type!
+    for (unsigned i = 0; i < $2->size(); i++) {
+      if (ETy != (*$2)[i]->getType())
+        ThrowException("Element #" + utostr(i) + " is not of type '" + 
+                     ETy->getDescription() +"' as required!\nIt is of type '" +
+                     (*$2)[i]->getType()->getDescription() + "'.");
+    }
+
+    $$ = ValID::create(ConstantPacked::get(pt, *$2));
+    delete PTy; delete $2;
+  }
   | ConstExpr {
     $$ = ValID::create($1);
   };
@@ -1852,8 +1912,14 @@ ValueRefList : ResolvedVal {    // Used for call statements, and memory insts...
 ValueRefListE : ValueRefList | /*empty*/ { $$ = 0; };
 
 InstVal : ArithmeticOps Types ValueRef ',' ValueRef {
-    if (!(*$2)->isInteger() && !(*$2)->isFloatingPoint())
-      ThrowException("Arithmetic operator requires integer or FP operands!");
+    if (!(*$2)->isInteger() && !(*$2)->isFloatingPoint() && 
+        !isa<PackedType>((*$2).get()))
+      ThrowException(
+        "Arithmetic operator requires integer, FP, or packed operands!");
+    if(isa<PackedType>((*$2).get()) && $1 == Instruction::Rem) {
+      ThrowException(
+        "Rem not supported on packed types!");
+    }
     $$ = BinaryOperator::create($1, getVal(*$2, $3), getVal(*$2, $5));
     if ($$ == 0)
       ThrowException("binary operator returned null!");
diff --git a/lib/Bytecode/Reader/Analyzer.cpp b/lib/Bytecode/Reader/Analyzer.cpp
index f6739ae3c6..bc1f0c74cd 100644
--- a/lib/Bytecode/Reader/Analyzer.cpp
+++ b/lib/Bytecode/Reader/Analyzer.cpp
@@ -387,6 +387,27 @@ public:
     bca.numValues++;
   }
 
+  virtual void handleConstantPacked( 
+    const PackedType* PT,                
+    std::vector<Constant*>& Elements,
+    unsigned TypeSlot,                  
+    Constant* PackedVal) 
+  {
+    dump << "      PACKD: " << PT->getDescription() 
+         << " TypeSlot=" << TypeSlot << "\n";
+    for ( unsigned i = 0; i < Elements.size(); ++i ) {
+      dump << "        #" << i;
+      Elements[i]->print(dump);
+      dump << "\n";
+    }
+    dump << "        Value=";
+    PackedVal->print(dump);
+    dump << "\n";
+
+    bca.numConstants++;
+    bca.numValues++;
+  }
+
   virtual void handleConstantPointer( const PointerType* PT, 
       unsigned Slot, GlobalValue* GV ) {
     dump << "       PNTR: " << PT->getDescription() 
diff --git a/lib/Bytecode/Reader/Reader.cpp b/lib/Bytecode/Reader/Reader.cpp
index 85a890dbc4..a9dbe9d545 100644
--- a/lib/Bytecode/Reader/Reader.cpp
+++ b/lib/Bytecode/Reader/Reader.cpp
@@ -1170,6 +1170,12 @@ const Type *BytecodeReader::ParseType() {
     Result =  ArrayType::get(ElementType, NumElements);
     break;
   }
+  case Type::PackedTyID: {
+    const Type *ElementType = readSanitizedType();
+    unsigned NumElements = read_vbr_uint();
+    Result =  PackedType::get(ElementType, NumElements);
+    break;
+  }
   case Type::StructTyID: {
     std::vector<const Type*> Elements;
     unsigned Typ = 0;
@@ -1396,6 +1402,20 @@ Constant *BytecodeReader::ParseConstantValue(unsigned TypeID) {
     return Result;
   }    
 
+  case Type::PackedTyID: {
+    const PackedType *PT = cast<PackedType>(Ty);
+    unsigned NumElements = PT->getNumElements();
+    unsigned TypeSlot = getTypeSlot(PT->getElementType());
+    std::vector<Constant*> Elements;
+    Elements.reserve(NumElements);
+    while (NumElements--)     // Read all of the elements of the constant.
+      Elements.push_back(getConstantValue(TypeSlot,
+                                          read_vbr_uint()));
+    Constant* Result = ConstantPacked::get(PT, Elements);
+    if (Handler) Handler->handleConstantPacked(PT, Elements, TypeSlot, Result);
+    return Result;
+  }
+
   case Type::PointerTyID: {  // ConstantPointerRef value...
     const PointerType *PT = cast<PointerType>(Ty);
     unsigned Slot = read_vbr_uint();
diff --git a/lib/Bytecode/Writer/Writer.cpp b/lib/Bytecode/Writer/Writer.cpp
index c3fad712f2..6654fd1b02 100644
--- a/lib/Bytecode/Writer/Writer.cpp
+++ b/lib/Bytecode/Writer/Writer.cpp
@@ -243,6 +243,16 @@ void BytecodeWriter::outputType(const Type *T) {
     break;
   }
 
+ case Type::PackedTyID: {
+    const PackedType *PT = cast<PackedType>(T);
+    int Slot = Table.getSlot(PT->getElementType());
+    assert(Slot != -1 && "Type used but not available!!");
+    output_typeid((unsigned)Slot);
+    output_vbr(PT->getNumElements());
+    break;
+  }
+
+
   case Type::StructTyID: {
     const StructType *ST = cast<StructType>(T);
 
@@ -339,6 +349,17 @@ void BytecodeWriter::outputConstant(const Constant *CPV) {
     break;
   }
 
+  case Type::PackedTyID: {
+    const ConstantPacked *CP = cast<ConstantPacked>(CPV);
+
+    for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i) {
+      int Slot = Table.getSlot(CP->getOperand(i));
+      assert(Slot != -1 && "Constant used but not available!!");
+      output_vbr((unsigned)Slot);
+    }
+    break;
+  }
+
   case Type::StructTyID: {
     const ConstantStruct *CPS = cast<ConstantStruct>(CPV);
 
diff --git a/lib/VMCore/AsmWriter.cpp b/lib/VMCore/AsmWriter.cpp
index 4cfba7668f..9fc772ecba 100644
--- a/lib/VMCore/AsmWriter.cpp
+++ b/lib/VMCore/AsmWriter.cpp
@@ -323,6 +323,13 @@ static void calcTypeName(const Type *Ty,
     Result += "]";
     break;
   }
+  case Type::PackedTyID: {
+    const PackedType *PTy = cast<PackedType>(Ty);
+    Result += "<" + utostr(PTy->getNumElements()) + " x ";
+    calcTypeName(PTy->getElementType(), TypeStack, TypeNames, Result);
+    Result += ">";
+    break;
+  }
   case Type::OpaqueTyID:
     Result += "opaque";
     break;
@@ -492,6 +499,22 @@ static void WriteConstantInt(std::ostream &Out, const Constant *CV,
     }
 
     Out << " }";
+  } else if (const ConstantPacked *CP = dyn_cast<ConstantPacked>(CV)) {
+      const Type *ETy = CP->getType()->getElementType();
+      assert(CP->getNumOperands() > 0 && 
+             "Number of operands for a PackedConst must be > 0");
+      Out << '<';
+      Out << ' ';
+      printTypeInt(Out, ETy, TypeTable);
+      WriteAsOperandInternal(Out, CP->getOperand(0),
+                             PrintName, TypeTable, Machine);
+      for (unsigned i = 1, e = CP->getNumOperands(); i != e; ++i) {
+          Out << ", ";
+          printTypeInt(Out, ETy, TypeTable);
+          WriteAsOperandInternal(Out, CP->getOperand(i), PrintName,
+                                 TypeTable, Machine);
+      }
+      Out << " >";
   } else if (isa<ConstantPointerNull>(CV)) {
     Out << "null";
 
diff --git a/lib/VMCore/Constants.cpp b/lib/VMCore/Constants.cpp
index 69f1a78412..8b28c0d3ff 100644
--- a/lib/VMCore/Constants.cpp
+++ b/lib/VMCore/Constants.cpp
@@ -120,6 +120,7 @@ Constant *Constant::getNullValue(const Type *Ty) {
 
   case Type::StructTyID:
   case Type::ArrayTyID:
+  case Type::PackedTyID:
     return ConstantAggregateZero::get(Ty);
   default:
     // Function, Label, or Opaque type?
@@ -268,6 +269,17 @@ ConstantStruct::ConstantStruct(const StructType *T,
   }
 }
 
+ConstantPacked::ConstantPacked(const PackedType *T,
+                               const std::vector<Constant*> &V) : Constant(T) {
+  Operands.reserve(V.size());
+  for (unsigned i = 0, e = V.size(); i != e; ++i) {
+    assert(V[i]->getType() == T->getElementType() ||
+           (T->isAbstract() &&
+            V[i]->getType()->getTypeID() == T->getElementType()->getTypeID()));
+    Operands.push_back(Use(V[i], this));
+  }
+}
+
 ConstantExpr::ConstantExpr(unsigned Opcode, Constant *C, const Type *Ty)
   : Constant(Ty, ConstantExprVal), iType(Opcode) {
   Operands.reserve(1);
@@ -484,6 +496,31 @@ void ConstantStruct::replaceUsesOfWithOnConstant(Value *From, Value *To,
   destroyConstant();
 }
 
+void ConstantPacked::replaceUsesOfWithOnConstant(Value *From, Value *To,
+                                                 bool DisableChecking) {
+  assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
+
+  std::vector<Constant*> Values;
+  Values.reserve(getNumOperands());  // Build replacement array...
+  for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {
+    Constant *Val = getOperand(i);
+    if (Val == From) Val = cast<Constant>(To);
+    Values.push_back(Val);
+  }
+  
+  Constant *Replacement = ConstantPacked::get(getType(), Values);
+  assert(Replacement != this && "I didn't contain From!");
+
+  // Everyone using this now uses the replacement...
+  if (DisableChecking)
+    uncheckedReplaceAllUsesWith(Replacement);
+  else
+    replaceAllUsesWith(Replacement);
+  
+  // Delete the old constant!
+  destroyConstant();  
+}
+
 void ConstantExpr::replaceUsesOfWithOnConstant(Value *From, Value *ToV,
                                                bool DisableChecking) {
   assert(isa<Constant>(ToV) && "Cannot make Constant refer to non-constant!");
@@ -959,6 +996,61 @@ void ConstantStruct::destroyConstant() {
   destroyConstantImpl();
 }
 
+//---- ConstantPacked::get() implementation...
+//
+namespace llvm {
+  template<>
+  struct ConvertConstantType<ConstantPacked, PackedType> {
+    static void convert(ConstantPacked *OldC, const PackedType *NewTy) {
+      // Make everyone now use a constant of the new type...
+      std::vector<Constant*> C;
+      for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
+        C.push_back(cast<Constant>(OldC->getOperand(i)));
+      Constant *New = ConstantPacked::get(NewTy, C);
+      assert(New != OldC && "Didn't replace constant??");
+      OldC->uncheckedReplaceAllUsesWith(New);
+      OldC->destroyConstant();    // This constant is now dead, destroy it.
+    }
+  };
+}
+
+static std::vector<Constant*> getValType(ConstantPacked *CP) {
+  std::vector<Constant*> Elements;
+  Elements.reserve(CP->getNumOperands());
+  for (unsigned i = 0, e = CP->getNumOperands(); i != e; ++i)
+    Elements.push_back(CP->getOperand(i));
+  return Elements;
+}
+
+static ValueMap<std::vector<Constant*>, PackedType,
+                ConstantPacked> PackedConstants;
+
+Constant *ConstantPacked::get(const PackedType *Ty,
+                              const std::vector<Constant*> &V) {
+  // If this is an all-zero packed, return a ConstantAggregateZero object
+  if (!V.empty()) {
+    Constant *C = V[0];
+    if (!C->isNullValue())
+      return PackedConstants.getOrCreate(Ty, V);
+    for (unsigned i = 1, e = V.size(); i != e; ++i)
+      if (V[i] != C)
+        return PackedConstants.getOrCreate(Ty, V);
+  }
+  return ConstantAggregateZero::get(Ty);
+}
+
+Constant *ConstantPacked::get(const std::vector<Constant*> &V) {
+  assert(!V.empty() && "Cannot infer type if V is empty");
+  return get(PackedType::get(V.front()->getType(),V.size()), V);
+}
+
+// destroyConstant - Remove the constant from the constant table...
+//
+void ConstantPacked::destroyConstant() {
+  PackedConstants.remove(this);
+  destroyConstantImpl();
+}
+
 //---- ConstantPointerNull::get() implementation...
 //
 
diff --git a/lib/VMCore/Instructions.cpp b/lib/VMCore/Instructions.cpp
index 205f32b460..74907dd7c4 100644
--- a/lib/VMCore/Instructions.cpp
+++ b/lib/VMCore/Instructions.cpp
@@ -564,8 +564,10 @@ void BinaryOperator::init(BinaryOps iType, Value *S1, Value *S2)
   case Rem:
     assert(getType() == S1->getType() &&
            "Arithmetic operation should return same type as operands!");
-    assert((getType()->isInteger() || getType()->isFloatingPoint()) && 
-           "Tried to create an arithmetic operation on a non-arithmetic type!");
+    assert((getType()->isInteger() || 
+            getType()->isFloatingPoint() || 
+            isa<PackedType>(getType()) ) && 
+          "Tried to create an arithmetic operation on a non-arithmetic type!");
     break;
   case And: case Or:
   case Xor:
diff --git a/lib/VMCore/Type.cpp b/lib/VMCore/Type.cpp
index c6ce34701c..bd0da45f46 100644
--- a/lib/VMCore/Type.cpp
+++ b/lib/VMCore/Type.cpp
@@ -261,6 +261,14 @@ static std::string getTypeDescription(const Type *Ty,
     Result += getTypeDescription(ATy->getElementType(), TypeStack) + "]";
     break;
   }
+  case Type::PackedTyID: {
+    const PackedType *PTy = cast<PackedType>(Ty);
+    unsigned NumElements = PTy->getNumElements();
+    Result = "<";
+    Result += utostr(NumElements) + " x ";
+    Result += getTypeDescription(PTy->getElementType(), TypeStack) + ">";
+    break;
+  }
   default:
     Result = "<error>";
     assert(0 && "Unhandled type in getTypeDescription!");
@@ -397,6 +405,16 @@ ArrayType::ArrayType(const Type *ElType, unsigned NumEl)
   setAbstract(ElType->isAbstract());
 }
 
+PackedType::PackedType(const Type *ElType, unsigned NumEl)
+  : SequentialType(PackedTyID, ElType) {
+  NumElements = NumEl;
+
+  assert(NumEl > 0 && "NumEl of a PackedType must be greater than 0");
+  assert((ElType->isIntegral() || ElType->isFloatingPoint()) && 
+         "Elements of a PackedType must be a primitive type");
+}
+
+
 PointerType::PointerType(const Type *E) : SequentialType(PointerTyID, E) {
   // Calculate whether or not this type is abstract
   setAbstract(E->isAbstract());
@@ -503,6 +521,10 @@ static bool TypesEqual(const Type *Ty, const Type *Ty2,
     const ArrayType *ATy2 = cast<ArrayType>(Ty2);
     return ATy->getNumElements() == ATy2->getNumElements() &&
            TypesEqual(ATy->getElementType(), ATy2->getElementType(), EqTypes);
+  } else if (const PackedType *PTy = dyn_cast<PackedType>(Ty)) {
+    const PackedType *PTy2 = cast<PackedType>(Ty2);
+    return PTy->getNumElements() == PTy2->getNumElements() &&
+           TypesEqual(PTy->getElementType(), PTy2->getElementType(), EqTypes);
   } else if (const FunctionType *FTy = dyn_cast<FunctionType>(Ty)) {
     const FunctionType *FTy2 = cast<FunctionType>(Ty2);
     if (FTy->isVarArg() != FTy2->isVarArg() ||
@@ -846,6 +868,56 @@ ArrayType *ArrayType::get(const Type *ElementType, unsigned NumElements) {
   return AT;
 }
 
+
+//===----------------------------------------------------------------------===//
+// Packed Type Factory...
+//
+namespace llvm {
+class PackedValType {
+  const Type *ValTy;
+  unsigned Size;
+public:
+  PackedValType(const Type *val, int sz) : ValTy(val), Size(sz) {}
+
+  static PackedValType get(const PackedType *PT) {
+    return PackedValType(PT->getElementType(), PT->getNumElements());
+  }
+
+  static unsigned hashTypeStructure(const PackedType *PT) {
+    return PT->getNumElements();
+  }
+
+  // Subclass should override this... to update self as usual
+  void doRefinement(const DerivedType *OldType, const Type *NewType) {
+    assert(ValTy == OldType);
+    ValTy = NewType;
+  }
+
+  inline bool operator<(const PackedValType &MTV) const {
+    if (Size < MTV.Size) return true;
+    return Size == MTV.Size && ValTy < MTV.ValTy;
+  }
+};
+}
+static TypeMap<PackedValType, PackedType> PackedTypes;
+
+
+PackedType *PackedType::get(const Type *ElementType, unsigned NumElements) {
+  assert(ElementType && "Can't get packed of null types!");
+
+  PackedValType PVT(ElementType, NumElements);
+  PackedType *PT = PackedTypes.get(PVT);
+  if (PT) return PT;           // Found a match, return it!
+
+  // Value not found.  Derive a new type!
+  PackedTypes.add(PVT, PT = new PackedType(ElementType, NumElements));
+
+#ifdef DEBUG_MERGE_TYPES
+  std::cerr << "Derived new type: " << *PT << "\n";
+#endif
+  return PT;
+}
+
 //===----------------------------------------------------------------------===//
 // Struct Type Factory...
 //
@@ -1107,6 +1179,18 @@ void ArrayType::typeBecameConcrete(const DerivedType *AbsTy) {
   refineAbstractType(AbsTy, AbsTy);
 }
 
+// refineAbstractType - Called when a contained type is found to be more
+// concrete - this could potentially change us from an abstract type to a
+// concrete type.
+//
+void PackedType::refineAbstractType(const DerivedType *OldType,
+                                   const Type *NewType) {
+  PackedTypes.finishRefinement(this, OldType, NewType);
+}
+
+void PackedType::typeBecameConcrete(const DerivedType *AbsTy) {
+  refineAbstractType(AbsTy, AbsTy);
+}
 
 // refineAbstractType - Called when a contained type is found to be more
 // concrete - this could potentially change us from an abstract type to a
diff --git a/lib/VMCore/Verifier.cpp b/lib/VMCore/Verifier.cpp
index 2005dbf584..9e99fe0136 100644
--- a/lib/VMCore/Verifier.cpp
+++ b/lib/VMCore/Verifier.cpp
@@ -488,8 +488,9 @@ void Verifier::visitBinaryOperator(BinaryOperator &B) {
     Assert1(B.getType() == B.getOperand(0)->getType(),
             "Arithmetic operators must have same type for operands and result!",
             &B);
-    Assert1(B.getType()->isInteger() || B.getType()->isFloatingPoint(),
-            "Arithmetic operators must have integer or fp type!", &B);
+    Assert1(B.getType()->isInteger() || B.getType()->isFloatingPoint() || 
+            isa<PackedType>(B.getType()),
+            "Arithmetic operators must have integer, fp, or packed type!", &B);
   }
   
   visitInstruction(B);