Add support for a union type in LLVM IR. Patch by Talin!

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

24 files changed, 612 insertions, 59 deletions

diff --git a/docs/LangRef.html b/docs/LangRef.html
index 9590609..b337b6a 100644
--- a/docs/LangRef.html
+++ b/docs/LangRef.html
@@ -66,12 +66,17 @@
       </li>
       <li><a href="#t_derived">Derived Types</a>
         <ol>
-          <li><a href="#t_array">Array Type</a></li>
+          <li><a href="#t_aggregate">Aggregate Types</a>
+            <ol>
+              <li><a href="#t_array">Array Type</a></li>
+              <li><a href="#t_struct">Structure Type</a></li>
+              <li><a href="#t_pstruct">Packed Structure Type</a></li>
+              <li><a href="#t_union">Union Type</a></li>
+              <li><a href="#t_vector">Vector Type</a></li>
+            </ol>
+          </li>
           <li><a href="#t_function">Function Type</a></li>
           <li><a href="#t_pointer">Pointer Type</a></li>
-          <li><a href="#t_struct">Structure Type</a></li>
-          <li><a href="#t_pstruct">Packed Structure Type</a></li>
-          <li><a href="#t_vector">Vector Type</a></li>
           <li><a href="#t_opaque">Opaque Type</a></li>
         </ol>
       </li>
@@ -1404,6 +1409,7 @@ Classifications</a> </div>
           <a href="#t_pointer">pointer</a>,
           <a href="#t_vector">vector</a>,
           <a href="#t_struct">structure</a>,
+          <a href="#t_union">union</a>,
           <a href="#t_array">array</a>,
           <a href="#t_label">label</a>,
           <a href="#t_metadata">metadata</a>.
@@ -1418,12 +1424,12 @@ Classifications</a> </div>
     </tr>
     <tr>
       <td><a href="#t_derived">derived</a></td>
-      <td><a href="#t_integer">integer</a>,
-          <a href="#t_array">array</a>,
+      <td><a href="#t_array">array</a>,
           <a href="#t_function">function</a>,
           <a href="#t_pointer">pointer</a>,
           <a href="#t_struct">structure</a>,
           <a href="#t_pstruct">packed structure</a>,
+          <a href="#t_union">union</a>,
           <a href="#t_vector">vector</a>,
           <a href="#t_opaque">opaque</a>.
       </td>
@@ -1561,6 +1567,21 @@ Classifications</a> </div>
    possible to have a two dimensional array, using an array as the element type
    of another array.</p>
 
+   
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection"> <a name="t_aggregate">Aggregate Types</a> </div>
+
+<div class="doc_text">
+
+<p>Aggregate Types are a subset of derived types that can contain multiple
+  member types. <a href="#t_array">Arrays</a>,
+  <a href="#t_struct">structs</a>, <a href="#t_vector">vectors</a> and
+  <a href="#t_union">unions</a> are aggregate types.</p>
+
+</div>
+
 </div>
 
 <!-- _______________________________________________________________________ -->
@@ -1629,9 +1650,9 @@ Classifications</a> </div>
 <h5>Overview:</h5>
 <p>The function type can be thought of as a function signature.  It consists of
    a return type and a list of formal parameter types. The return type of a
-   function type is a scalar type, a void type, or a struct type.  If the return
-   type is a struct type then all struct elements must be of first class types,
-   and the struct must have at least one element.</p>
+   function type is a scalar type, a void type, a struct type, or a union
+   type.  If the return type is a struct type then all struct elements must be
+   of first class types, and the struct must have at least one element.</p>
 
 <h5>Syntax:</h5>
 <pre>
@@ -1754,6 +1775,53 @@ Classifications</a> </div>
 </div>
 
 <!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection"> <a name="t_union">Union Type</a> </div>
+
+<div class="doc_text">
+
+<h5>Overview:</h5>
+<p>A union type describes an object with size and alignment suitable for
+   an object of any one of a given set of types (also known as an "untagged"
+   union). It is similar in concept and usage to a
+   <a href="#t_struct">struct</a>, except that all members of the union
+   have an offset of zero. The elements of a union may be any type that has a
+   size. Unions must have at least one member - empty unions are not allowed.
+   </p>
+
+<p>The size of the union as a whole will be the size of its largest member,
+   and the alignment requirements of the union as a whole will be the largest
+   alignment requirement of any member.</p>
+
+<p>Unions members are accessed using '<tt><a href="#i_load">load</a></tt> and
+   '<tt><a href="#i_store">store</a></tt>' by getting a pointer to a field with
+   the '<tt><a href="#i_getelementptr">getelementptr</a></tt>' instruction.
+   Since all members are at offset zero, the getelementptr instruction does
+   not affect the address, only the type of the resulting pointer.</p>
+
+<h5>Syntax:</h5>
+<pre>
+  union { &lt;type list&gt; }
+</pre>
+
+<h5>Examples:</h5>
+<table class="layout">
+  <tr class="layout">
+    <td class="left"><tt>union { i32, i32*, float }</tt></td>
+    <td class="left">A union of three types: an <tt>i32</tt>, a pointer to
+      an <tt>i32</tt>, and a <tt>float</tt>.</td>
+  </tr><tr class="layout">
+    <td class="left">
+      <tt>union {&nbsp;float,&nbsp;i32&nbsp;(i32)&nbsp;*&nbsp;}</tt></td>
+    <td class="left">A union, where the first element is a <tt>float</tt> and the
+      second element is a <a href="#t_pointer">pointer</a> to a
+      <a href="#t_function">function</a> that takes an <tt>i32</tt>, returning
+      an <tt>i32</tt>.</td>
+  </tr>
+</table>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
 <div class="doc_subsubsection"> <a name="t_pointer">Pointer Type</a> </div>
 
 <div class="doc_text">
@@ -1991,6 +2059,14 @@ Classifications</a> </div>
       the number and types of elements must match those specified by the
       type.</dd>
 
+  <dt><b>Union constants</b></dt>
+  <dd>Union constants are represented with notation similar to a structure with
+      a single element - that is, a single typed element surrounded
+      by braces (<tt>{}</tt>)).  For example: "<tt>{ i32 4 }</tt>".  The
+      <a href="#t_union">union type</a> can be initialized with a single-element
+      struct as long as the type of the struct element matches the type of
+      one of the union members.</dd>
+
   <dt><b>Array constants</b></dt>
   <dd>Array constants are represented with notation similar to array type
      definitions (a comma separated list of elements, surrounded by square
@@ -2009,7 +2085,8 @@ Classifications</a> </div>
 
   <dt><b>Zero initialization</b></dt>
   <dd>The string '<tt>zeroinitializer</tt>' can be used to zero initialize a
-      value to zero of <em>any</em> type, including scalar and aggregate types.
+      value to zero of <em>any</em> type, including scalar and
+      <a href="#t_aggregate">aggregate</a> types.
       This is often used to avoid having to print large zero initializers
       (e.g. for large arrays) and is always exactly equivalent to using explicit
       zero initializers.</dd>
@@ -3845,7 +3922,8 @@ Instruction</a> </div>
 
 <div class="doc_text">
 
-<p>LLVM supports several instructions for working with aggregate values.</p>
+<p>LLVM supports several instructions for working with
+  <a href="#t_aggregate">aggregate</a> values.</p>
 
 </div>
 
@@ -3862,14 +3940,14 @@ Instruction</a> </div>
 </pre>
 
 <h5>Overview:</h5>
-<p>The '<tt>extractvalue</tt>' instruction extracts the value of a struct field
-   or array element from an aggregate value.</p>
+<p>The '<tt>extractvalue</tt>' instruction extracts the value of a member field
+   from an <a href="#t_aggregate">aggregate</a> value.</p>
 
 <h5>Arguments:</h5>
 <p>The first operand of an '<tt>extractvalue</tt>' instruction is a value
-   of <a href="#t_struct">struct</a> or <a href="#t_array">array</a> type.  The
-   operands are constant indices to specify which value to extract in a similar
-   manner as indices in a
+   of <a href="#t_struct">struct</a>, <a href="#t_union">union</a>  or
+   <a href="#t_array">array</a> type.  The operands are constant indices to
+   specify which value to extract in a similar manner as indices in a
    '<tt><a href="#i_getelementptr">getelementptr</a></tt>' instruction.</p>
 
 <h5>Semantics:</h5>
@@ -3896,16 +3974,15 @@ Instruction</a> </div>
 </pre>
 
 <h5>Overview:</h5>
-<p>The '<tt>insertvalue</tt>' instruction inserts a value into a struct field or
-   array element in an aggregate.</p>
-
+<p>The '<tt>insertvalue</tt>' instruction inserts a value into a member field
+   in an <a href="#t_aggregate">aggregate</a> value.</p>
 
 <h5>Arguments:</h5>
 <p>The first operand of an '<tt>insertvalue</tt>' instruction is a value
-   of <a href="#t_struct">struct</a> or <a href="#t_array">array</a> type.  The
-   second operand is a first-class value to insert.  The following operands are
-   constant indices indicating the position at which to insert the value in a
-   similar manner as indices in a
+   of <a href="#t_struct">struct</a>, <a href="#t_union">union</a> or
+   <a href="#t_array">array</a> type.  The second operand is a first-class
+   value to insert.  The following operands are constant indices indicating
+   the position at which to insert the value in a similar manner as indices in a
    '<tt><a href="#i_getelementptr">getelementptr</a></tt>' instruction.  The
    value to insert must have the same type as the value identified by the
    indices.</p>
@@ -4107,8 +4184,8 @@ Instruction</a> </div>
 
 <h5>Overview:</h5>
 <p>The '<tt>getelementptr</tt>' instruction is used to get the address of a
-   subelement of an aggregate data structure. It performs address calculation
-   only and does not access memory.</p>
+   subelement of an <a href="#t_aggregate">aggregate</a> data structure.
+   It performs address calculation only and does not access memory.</p>
 
 <h5>Arguments:</h5>
 <p>The first argument is always a pointer, and forms the basis of the
@@ -4118,15 +4195,15 @@ Instruction</a> </div>
    indexes the pointer value given as the first argument, the second index
    indexes a value of the type pointed to (not necessarily the value directly
    pointed to, since the first index can be non-zero), etc. The first type
-   indexed into must be a pointer value, subsequent types can be arrays, vectors
-   and structs. Note that subsequent types being indexed into can never be
-   pointers, since that would require loading the pointer before continuing
-   calculation.</p>
+   indexed into must be a pointer value, subsequent types can be arrays,
+   vectors, structs and unions. Note that subsequent types being indexed into
+   can never be pointers, since that would require loading the pointer before
+   continuing calculation.</p>
 
 <p>The type of each index argument depends on the type it is indexing into.
-   When indexing into a (optionally packed) structure, only <tt>i32</tt> integer
-   <b>constants</b> are allowed.  When indexing into an array, pointer or
-   vector, integers of any width are allowed, and they are not required to be
+   When indexing into a (optionally packed) structure or union, only <tt>i32</tt>
+   integer <b>constants</b> are allowed.  When indexing into an array, pointer
+   or vector, integers of any width are allowed, and they are not required to be
    constant.</p>
 
 <p>For example, let's consider a C code fragment and how it gets compiled to
diff --git a/include/llvm-c/Core.h b/include/llvm-c/Core.h
index 98358fe..4500fcc 100644
--- a/include/llvm-c/Core.h
+++ b/include/llvm-c/Core.h
@@ -193,7 +193,8 @@ typedef enum {
   LLVMPointerTypeKind,     /**< Pointers */
   LLVMOpaqueTypeKind,      /**< Opaque: type with unknown structure */
   LLVMVectorTypeKind,      /**< SIMD 'packed' format, or other vector type */
-  LLVMMetadataTypeKind     /**< Metadata */
+  LLVMMetadataTypeKind,    /**< Metadata */
+  LLVMUnionTypeKind        /**< Unions */
 } LLVMTypeKind;
 
 typedef enum {
@@ -372,6 +373,13 @@ unsigned LLVMCountStructElementTypes(LLVMTypeRef StructTy);
 void LLVMGetStructElementTypes(LLVMTypeRef StructTy, LLVMTypeRef *Dest);
 LLVMBool LLVMIsPackedStruct(LLVMTypeRef StructTy);
 
+/* Operations on union types */
+LLVMTypeRef LLVMUnionTypeInContext(LLVMContextRef C, LLVMTypeRef *ElementTypes,
+                                   unsigned ElementCount);
+LLVMTypeRef LLVMUnionType(LLVMTypeRef *ElementTypes, unsigned ElementCount);
+unsigned LLVMCountUnionElementTypes(LLVMTypeRef UnionTy);
+void LLVMGetUnionElementTypes(LLVMTypeRef UnionTy, LLVMTypeRef *Dest);
+
 /* Operations on array, pointer, and vector types (sequence types) */
 LLVMTypeRef LLVMArrayType(LLVMTypeRef ElementType, unsigned ElementCount);
 LLVMTypeRef LLVMPointerType(LLVMTypeRef ElementType, unsigned AddressSpace);
diff --git a/include/llvm/Bitcode/LLVMBitCodes.h b/include/llvm/Bitcode/LLVMBitCodes.h
index 9bb50d4..a980df8 100644
--- a/include/llvm/Bitcode/LLVMBitCodes.h
+++ b/include/llvm/Bitcode/LLVMBitCodes.h
@@ -94,7 +94,8 @@ namespace bitc {
     TYPE_CODE_FP128    = 14,   // LONG DOUBLE (112 bit mantissa)
     TYPE_CODE_PPC_FP128= 15,   // PPC LONG DOUBLE (2 doubles)
 
-    TYPE_CODE_METADATA = 16    // METADATA
+    TYPE_CODE_METADATA = 16,   // METADATA
+    TYPE_CODE_UNION    = 17    // UNION: [eltty x N]
   };
 
   // The type symbol table only has one code (TST_ENTRY_CODE).
diff --git a/include/llvm/Constants.h b/include/llvm/Constants.h
index ff1be05..bd14303 100644
--- a/include/llvm/Constants.h
+++ b/include/llvm/Constants.h
@@ -33,6 +33,7 @@ namespace llvm {
 class ArrayType;
 class IntegerType;
 class StructType;
+class UnionType;
 class PointerType;
 class VectorType;
 
@@ -453,6 +454,50 @@ struct OperandTraits<ConstantStruct> : public VariadicOperandTraits<> {
 DEFINE_TRANSPARENT_CASTED_OPERAND_ACCESSORS(ConstantStruct, Constant)
 
 //===----------------------------------------------------------------------===//
+// ConstantUnion - Constant Union Declarations
+//
+class ConstantUnion : public Constant {
+  friend struct ConstantCreator<ConstantUnion, UnionType, Constant*>;
+  ConstantUnion(const ConstantUnion &);      // DO NOT IMPLEMENT
+protected:
+  ConstantUnion(const UnionType *T, Constant* Val);
+public:
+  // ConstantUnion accessors
+  static Constant *get(const UnionType *T, Constant* V);
+
+  /// Transparently provide more efficient getOperand methods.
+  DECLARE_TRANSPARENT_OPERAND_ACCESSORS(Constant);
+  
+  /// getType() specialization - Reduce amount of casting...
+  ///
+  inline const UnionType *getType() const {
+    return reinterpret_cast<const UnionType*>(Value::getType());
+  }
+
+  /// isNullValue - Return true if this is the value that would be returned by
+  /// getNullValue.  This always returns false because zero structs are always
+  /// created as ConstantAggregateZero objects.
+  virtual bool isNullValue() const {
+    return false;
+  }
+
+  virtual void destroyConstant();
+  virtual void replaceUsesOfWithOnConstant(Value *From, Value *To, Use *U);
+
+  /// Methods for support type inquiry through isa, cast, and dyn_cast:
+  static inline bool classof(const ConstantUnion *) { return true; }
+  static bool classof(const Value *V) {
+    return V->getValueID() == ConstantUnionVal;
+  }
+};
+
+template <>
+struct OperandTraits<ConstantUnion> : public FixedNumOperandTraits<1> {
+};
+
+DEFINE_TRANSPARENT_CASTED_OPERAND_ACCESSORS(ConstantUnion, Constant)
+
+//===----------------------------------------------------------------------===//
 /// ConstantVector - Constant Vector Declarations
 ///
 class ConstantVector : public Constant {
diff --git a/include/llvm/DerivedTypes.h b/include/llvm/DerivedTypes.h
index 881fbc8..912bb6d 100644
--- a/include/llvm/DerivedTypes.h
+++ b/include/llvm/DerivedTypes.h
@@ -27,6 +27,7 @@ template<class ValType, class TypeClass> class TypeMap;
 class FunctionValType;
 class ArrayValType;
 class StructValType;
+class UnionValType;
 class PointerValType;
 class VectorValType;
 class IntegerValType;
@@ -229,7 +230,8 @@ public:
     return T->getTypeID() == ArrayTyID ||
            T->getTypeID() == StructTyID ||
            T->getTypeID() == PointerTyID ||
-           T->getTypeID() == VectorTyID;
+           T->getTypeID() == VectorTyID ||
+           T->getTypeID() == UnionTyID;
   }
 };
 
@@ -301,6 +303,63 @@ public:
 };
 
 
+/// UnionType - Class to represent union types. A union type is similar to
+/// a structure, except that all member fields begin at offset 0.
+///
+class UnionType : public CompositeType {
+  friend class TypeMap<UnionValType, UnionType>;
+  UnionType(const UnionType &);                   // Do not implement
+  const UnionType &operator=(const UnionType &);  // Do not implement
+  UnionType(LLVMContext &C, const Type* const* Types, unsigned NumTypes);
+public:
+  /// UnionType::get - This static method is the primary way to create a
+  /// UnionType.
+  static UnionType *get(const Type* const* Types, unsigned NumTypes);
+
+  /// UnionType::get - This static method is a convenience method for
+  /// creating union types by specifying the elements as arguments.
+  static UnionType *get(const Type *type, ...) END_WITH_NULL;
+
+  /// isValidElementType - Return true if the specified type is valid as a
+  /// element type.
+  static bool isValidElementType(const Type *ElemTy);
+  
+  /// Given an element type, return the member index of that type, or -1
+  /// if there is no such member type.
+  int getElementTypeIndex(const Type *ElemTy) const;
+
+  // Iterator access to the elements
+  typedef Type::subtype_iterator element_iterator;
+  element_iterator element_begin() const { return ContainedTys; }
+  element_iterator element_end() const { return &ContainedTys[NumContainedTys];}
+
+  // Random access to the elements
+  unsigned getNumElements() const { return NumContainedTys; }
+  const Type *getElementType(unsigned N) const {
+    assert(N < NumContainedTys && "Element number out of range!");
+    return ContainedTys[N];
+  }
+
+  /// getTypeAtIndex - Given an index value into the type, return the type of
+  /// the element.  For a union type, this must be a constant value...
+  ///
+  virtual const Type *getTypeAtIndex(const Value *V) const;
+  virtual const Type *getTypeAtIndex(unsigned Idx) const;
+  virtual bool indexValid(const Value *V) const;
+  virtual bool indexValid(unsigned Idx) const;
+
+  // 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 UnionType *) { return true; }
+  static inline bool classof(const Type *T) {
+    return T->getTypeID() == UnionTyID;
+  }
+};
+
+
 /// SequentialType - This is the superclass of the array, pointer and vector
 /// type classes.  All of these represent "arrays" in memory.  The array type
 /// represents a specifically sized array, pointer types are unsized/unknown
diff --git a/include/llvm/Type.h b/include/llvm/Type.h
index bc319c6..52b2c84 100644
--- a/include/llvm/Type.h
+++ b/include/llvm/Type.h
@@ -82,10 +82,11 @@ public:
     IntegerTyID,     ///<  8: Arbitrary bit width integers
     FunctionTyID,    ///<  9: Functions
     StructTyID,      ///< 10: Structures
-    ArrayTyID,       ///< 11: Arrays
-    PointerTyID,     ///< 12: Pointers
-    OpaqueTyID,      ///< 13: Opaque: type with unknown structure
-    VectorTyID,      ///< 14: SIMD 'packed' format, or other vector type
+    UnionTyID,       ///< 11: Unions
+    ArrayTyID,       ///< 12: Arrays
+    PointerTyID,     ///< 13: Pointers
+    OpaqueTyID,      ///< 14: Opaque: type with unknown structure
+    VectorTyID,      ///< 15: SIMD 'packed' format, or other vector type
 
     NumTypeIDs,                         // Must remain as last defined ID
     LastPrimitiveTyID = LabelTyID,
@@ -297,7 +298,7 @@ public:
   /// does not include vector types.
   ///
   inline bool isAggregateType() const {
-    return ID == StructTyID || ID == ArrayTyID;
+    return ID == StructTyID || ID == ArrayTyID || ID == UnionTyID;
   }
 
   /// isSized - Return true if it makes sense to take the size of this type.  To
@@ -310,7 +311,8 @@ public:
       return true;
     // If it is not something that can have a size (e.g. a function or label),
     // it doesn't have a size.
-    if (ID != StructTyID && ID != ArrayTyID && ID != VectorTyID)
+    if (ID != StructTyID && ID != ArrayTyID && ID != VectorTyID &&
+        ID != UnionTyID)
       return false;
     // If it is something that can have a size and it's concrete, it definitely
     // has a size, otherwise we have to try harder to decide.
diff --git a/include/llvm/Value.h b/include/llvm/Value.h
index 9045906..d06cbc0 100644
--- a/include/llvm/Value.h
+++ b/include/llvm/Value.h
@@ -215,6 +215,7 @@ public:
     ConstantFPVal,            // This is an instance of ConstantFP
     ConstantArrayVal,         // This is an instance of ConstantArray
     ConstantStructVal,        // This is an instance of ConstantStruct
+    ConstantUnionVal,         // This is an instance of ConstantUnion
     ConstantVectorVal,        // This is an instance of ConstantVector
     ConstantPointerNullVal,   // This is an instance of ConstantPointerNull
     MDNodeVal,                // This is an instance of MDNode
diff --git a/lib/AsmParser/LLLexer.cpp b/lib/AsmParser/LLLexer.cpp
index 8ad658d..46f3cbc 100644
--- a/lib/AsmParser/LLLexer.cpp
+++ b/lib/AsmParser/LLLexer.cpp
@@ -570,6 +570,7 @@ lltok::Kind LLLexer::LexIdentifier() {
 
   KEYWORD(type);
   KEYWORD(opaque);
+  KEYWORD(union);
 
   KEYWORD(eq); KEYWORD(ne); KEYWORD(slt); KEYWORD(sgt); KEYWORD(sle);
   KEYWORD(sge); KEYWORD(ult); KEYWORD(ugt); KEYWORD(ule); KEYWORD(uge);
diff --git a/lib/AsmParser/LLParser.cpp b/lib/AsmParser/LLParser.cpp
index 4dab118..5cff310 100644
--- a/lib/AsmParser/LLParser.cpp
+++ b/lib/AsmParser/LLParser.cpp
@@ -1295,6 +1295,11 @@ bool LLParser::ParseTypeRec(PATypeHolder &Result) {
     if (ParseStructType(Result, false))
       return true;
     break;
+  case lltok::kw_union:
+    // TypeRec ::= 'union' '{' ... '}'
+    if (ParseUnionType(Result))
+      return true;
+    break;
   case lltok::lsquare:
     // TypeRec ::= '[' ... ']'
     Lex.Lex(); // eat the lsquare.
@@ -1604,6 +1609,38 @@ bool LLParser::ParseStructType(PATypeHolder &Result, bool Packed) {
   return false;
 }
 
+/// ParseUnionType
+///   TypeRec
+///     ::= 'union' '{' TypeRec (',' TypeRec)* '}'
+bool LLParser::ParseUnionType(PATypeHolder &Result) {
+  assert(Lex.getKind() == lltok::kw_union);
+  Lex.Lex(); // Consume the 'union'
+
+  if (ParseToken(lltok::lbrace, "'{' expected after 'union'")) return true;
+
+  SmallVector<PATypeHolder, 8> ParamsList;
+  do {
+    LocTy EltTyLoc = Lex.getLoc();
+    if (ParseTypeRec(Result)) return true;
+    ParamsList.push_back(Result);
+
+    if (Result->isVoidTy())
+      return Error(EltTyLoc, "union element can not have void type");
+    if (!UnionType::isValidElementType(Result))
+      return Error(EltTyLoc, "invalid element type for union");
+
+  } while (EatIfPresent(lltok::comma)) ;
+
+  if (ParseToken(lltok::rbrace, "expected '}' at end of union"))
+    return true;
+
+  SmallVector<const Type*, 8> ParamsListTy;
+  for (unsigned i = 0, e = ParamsList.size(); i != e; ++i)
+    ParamsListTy.push_back(ParamsList[i].get());
+  Result = HandleUpRefs(UnionType::get(&ParamsListTy[0], ParamsListTy.size()));
+  return false;
+}
+
 /// ParseArrayVectorType - Parse an array or vector type, assuming the first
 /// token has already been consumed.
 ///   TypeRec
@@ -2163,8 +2200,8 @@ bool LLParser::ParseValID(ValID &ID, PerFunctionState *PFS) {
         ParseToken(lltok::rparen, "expected ')' in extractvalue constantexpr"))
       return true;
 
-    if (!isa<StructType>(Val->getType()) && !isa<ArrayType>(Val->getType()))
-      return Error(ID.Loc, "extractvalue operand must be array or struct");
+    if (!Val->getType()->isAggregateType())
+      return Error(ID.Loc, "extractvalue operand must be aggregate type");
     if (!ExtractValueInst::getIndexedType(Val->getType(), Indices.begin(),
                                           Indices.end()))
       return Error(ID.Loc, "invalid indices for extractvalue");
@@ -2184,8 +2221,8 @@ bool LLParser::ParseValID(ValID &ID, PerFunctionState *PFS) {
         ParseIndexList(Indices) ||
         ParseToken(lltok::rparen, "expected ')' in insertvalue constantexpr"))
       return true;
-    if (!isa<StructType>(Val0->getType()) && !isa<ArrayType>(Val0->getType()))
-      return Error(ID.Loc, "extractvalue operand must be array or struct");
+    if (!Val0->getType()->isAggregateType())
+      return Error(ID.Loc, "insertvalue operand must be aggregate type");
     if (!ExtractValueInst::getIndexedType(Val0->getType(), Indices.begin(),
                                           Indices.end()))
       return Error(ID.Loc, "invalid indices for insertvalue");
@@ -2521,8 +2558,17 @@ bool LLParser::ConvertValIDToValue(const Type *Ty, ValID &ID, Value *&V,
     V = Constant::getNullValue(Ty);
     return false;
   case ValID::t_Constant:
-    if (ID.ConstantVal->getType() != Ty)
+    if (ID.ConstantVal->getType() != Ty) {
+      // Allow a constant struct with a single member to be converted
+      // to a union, if the union has a member which is the same type
+      // as the struct member.
+      if (const UnionType* utype = dyn_cast<UnionType>(Ty)) {
+        return ParseUnionValue(utype, ID, V);
+      }
+
       return Error(ID.Loc, "constant expression type mismatch");
+    }
+
     V = ID.ConstantVal;
     return false;
   }
@@ -2552,6 +2598,22 @@ bool LLParser::ParseTypeAndBasicBlock(BasicBlock *&BB, LocTy &Loc,
   return false;
 }
 
+bool LLParser::ParseUnionValue(const UnionType* utype, ValID &ID, Value *&V) {
+  if (const StructType* stype = dyn_cast<StructType>(ID.ConstantVal->getType())) {
+    if (stype->getNumContainedTypes() != 1)
+      return Error(ID.Loc, "constant expression type mismatch");
+    int index = utype->getElementTypeIndex(stype->getContainedType(0));
+    if (index < 0)
+      return Error(ID.Loc, "initializer type is not a member of the union");
+
+    V = ConstantUnion::get(
+        utype, cast<Constant>(ID.ConstantVal->getOperand(0)));
+    return false;
+  }
+
+  return Error(ID.Loc, "constant expression type mismatch");
+}
+
 
 /// FunctionHeader
 ///   ::= OptionalLinkage OptionalVisibility OptionalCallingConv OptRetAttrs
@@ -3811,8 +3873,8 @@ int LLParser::ParseExtractValue(Instruction *&Inst, PerFunctionState &PFS) {
       ParseIndexList(Indices, AteExtraComma))
     return true;
 
-  if (!isa<StructType>(Val->getType()) && !isa<ArrayType>(Val->getType()))
-    return Error(Loc, "extractvalue operand must be array or struct");
+  if (!Val->getType()->isAggregateType())
+    return Error(Loc, "extractvalue operand must be aggregate type");
 
   if (!ExtractValueInst::getIndexedType(Val->getType(), Indices.begin(),
                                         Indices.end()))
@@ -3833,8 +3895,8 @@ int LLParser::ParseInsertValue(Instruction *&Inst, PerFunctionState &PFS) {
       ParseIndexList(Indices, AteExtraComma))
     return true;
   
-  if (!isa<StructType>(Val0->getType()) && !isa<ArrayType>(Val0->getType()))
-    return Error(Loc0, "extractvalue operand must be array or struct");
+  if (!Val0->getType()->isAggregateType())
+    return Error(Loc0, "insertvalue operand must be aggregate type");
 
   if (!ExtractValueInst::getIndexedType(Val0->getType(), Indices.begin(),
                                         Indices.end()))
diff --git a/lib/AsmParser/LLParser.h b/lib/AsmParser/LLParser.h
index ed7a1d7..9abe404 100644
--- a/lib/AsmParser/LLParser.h
+++ b/lib/AsmParser/LLParser.h
@@ -31,6 +31,7 @@ namespace llvm {
   class GlobalValue;
   class MDString;
   class MDNode;
+  class UnionType;
 
   /// ValID - Represents a reference of a definition of some sort with no type.
   /// There are several cases where we have to parse the value but where the
@@ -212,6 +213,7 @@ namespace llvm {
     }
     bool ParseTypeRec(PATypeHolder &H);
     bool ParseStructType(PATypeHolder &H, bool Packed);
+    bool ParseUnionType(PATypeHolder &H);
     bool ParseArrayVectorType(PATypeHolder &H, bool isVector);
     bool ParseFunctionType(PATypeHolder &Result);
     PATypeHolder HandleUpRefs(const Type *Ty);
@@ -280,6 +282,8 @@ namespace llvm {
       return ParseTypeAndBasicBlock(BB, Loc, PFS);
     }
 
+    bool ParseUnionValue(const UnionType* utype, ValID &ID, Value *&V);
+
     struct ParamInfo {
       LocTy Loc;
       Value *V;
diff --git a/lib/AsmParser/LLToken.h b/lib/AsmParser/LLToken.h
index 7f1807c..3ac9169 100644
--- a/lib/AsmParser/LLToken.h
+++ b/lib/AsmParser/LLToken.h
@@ -97,6 +97,7 @@ namespace lltok {
 
     kw_type,
     kw_opaque,
+    kw_union,
 
     kw_eq, kw_ne, kw_slt, kw_sgt, kw_sle, kw_sge, kw_ult, kw_ugt, kw_ule,
     kw_uge, kw_oeq, kw_one, kw_olt, kw_ogt, kw_ole, kw_oge, kw_ord, kw_uno,
diff --git a/lib/Bitcode/Reader/BitcodeReader.cpp b/lib/Bitcode/Reader/BitcodeReader.cpp
index 4dfc6ce..a0402ca 100644
--- a/lib/Bitcode/Reader/BitcodeReader.cpp
+++ b/lib/Bitcode/Reader/BitcodeReader.cpp
@@ -585,6 +585,13 @@ bool BitcodeReader::ParseTypeTable() {
       ResultTy = StructType::get(Context, EltTys, Record[0]);
       break;
     }
+    case bitc::TYPE_CODE_UNION: {  // UNION: [eltty x N]
+      SmallVector<const Type*, 8> EltTys;
+      for (unsigned i = 0, e = Record.size(); i != e; ++i)
+        EltTys.push_back(getTypeByID(Record[i], true));
+      ResultTy = UnionType::get(&EltTys[0], EltTys.size());
+      break;
+    }
     case bitc::TYPE_CODE_ARRAY:     // ARRAY: [numelts, eltty]
       if (Record.size() < 2)
         return Error("Invalid ARRAY type record");
diff --git a/lib/Bitcode/Writer/BitcodeWriter.cpp b/lib/Bitcode/Writer/BitcodeWriter.cpp
index ec081d5..82e73b5 100644
--- a/lib/Bitcode/Writer/BitcodeWriter.cpp
+++ b/lib/Bitcode/Writer/BitcodeWriter.cpp
@@ -181,6 +181,14 @@ static void WriteTypeTable(const ValueEnumerator &VE, BitstreamWriter &Stream) {
                             Log2_32_Ceil(VE.getTypes().size()+1)));
   unsigned StructAbbrev = Stream.EmitAbbrev(Abbv);
 
+  // Abbrev for TYPE_CODE_UNION.
+  Abbv = new BitCodeAbbrev();
+  Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_UNION));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Array));
+  Abbv->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed,
+                            Log2_32_Ceil(VE.getTypes().size()+1)));
+  unsigned UnionAbbrev = Stream.EmitAbbrev(Abbv);
+
   // Abbrev for TYPE_CODE_ARRAY.
   Abbv = new BitCodeAbbrev();
   Abbv->Add(BitCodeAbbrevOp(bitc::TYPE_CODE_ARRAY));
@@ -250,6 +258,17 @@ static void WriteTypeTable(const ValueEnumerator &VE, BitstreamWriter &Stream) {
       AbbrevToUse = StructAbbrev;
       break;
     }
+    case Type::UnionTyID: {
+      const UnionType *UT = cast<UnionType>(T);
+      // UNION: [eltty x N]
+      Code = bitc::TYPE_CODE_UNION;
+      // Output all of the element types.
+      for (UnionType::element_iterator I = UT->element_begin(),
+           E = UT->element_end(); I != E; ++I)
+        TypeVals.push_back(VE.getTypeID(*I));
+      AbbrevToUse = UnionAbbrev;
+      break;
+    }
     case Type::ArrayTyID: {
       const ArrayType *AT = cast<ArrayType>(T);
       // ARRAY: [numelts, eltty]
@@ -789,7 +808,7 @@ static void WriteConstants(unsigned FirstVal, unsigned LastVal,
       else if (isCStr7)
         AbbrevToUse = CString7Abbrev;
     } else if (isa<ConstantArray>(C) || isa<ConstantStruct>(V) ||
-               isa<ConstantVector>(V)) {
+               isa<ConstantUnion>(C) || isa<ConstantVector>(V)) {
       Code = bitc::CST_CODE_AGGREGATE;
       for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i)
         Record.push_back(VE.getValueID(C->getOperand(i)));
diff --git a/lib/Target/X86/X86InstrInfo.td b/lib/Target/X86/X86InstrInfo.td
index d0be4f7..de085f5 100644
--- a/lib/Target/X86/X86InstrInfo.td
+++ b/lib/Target/X86/X86InstrInfo.td
@@ -4242,7 +4242,7 @@ def INVEPT : I<0x38, RawFrm, (outs), (ins), "invept", []>, OpSize, TB;
 // 66 0F 38 81
 def INVVPID : I<0x38, RawFrm, (outs), (ins), "invvpid", []>, OpSize, TB;
 // 0F 01 C1
-def VMCALL : I<0x01, RawFrm, (outs), (ins), "vmcall", []>, TB;
+def VMCALL : I<0x01, MRM_C1, (outs), (ins), "vmcall", []>, TB;
 def VMCLEARm : I<0xC7, MRM6m, (outs), (ins i64mem:$vmcs),
   "vmclear\t$vmcs", []>, OpSize, TB;
 // 0F 01 C2
diff --git a/lib/VMCore/AsmWriter.cpp b/lib/VMCore/AsmWriter.cpp
index 7d6e0a7..4fe1eee 100644
--- a/lib/VMCore/AsmWriter.cpp
+++ b/lib/VMCore/AsmWriter.cpp
@@ -239,6 +239,19 @@ void TypePrinting::CalcTypeName(const Type *Ty,
       OS << '>';
     break;
   }
+  case Type::UnionTyID: {
+    const UnionType *UTy = cast<UnionType>(Ty);
+    OS << "union { ";
+    for (StructType::element_iterator I = UTy->element_begin(),
+         E = UTy->element_end(); I != E; ++I) {
+      CalcTypeName(*I, TypeStack, OS);
+      if (next(I) != UTy->element_end())
+        OS << ',';
+      OS << ' ';
+    }
+    OS << '}';
+    break;
+  }
   case Type::PointerTyID: {
     const PointerType *PTy = cast<PointerType>(Ty);
     CalcTypeName(PTy->getElementType(), TypeStack, OS);
diff --git a/lib/VMCore/ConstantFold.cpp b/lib/VMCore/ConstantFold.cpp
index 5c117d8..4a245d2 100644
--- a/lib/VMCore/ConstantFold.cpp
+++ b/lib/VMCore/ConstantFold.cpp
@@ -885,6 +885,8 @@ Constant *llvm::ConstantFoldInsertValueInstruction(Constant *Agg,
     unsigned numOps;
     if (const ArrayType *AR = dyn_cast<ArrayType>(AggTy))
       numOps = AR->getNumElements();
+    else if (isa<UnionType>(AggTy))
+      numOps = 1;
     else
       numOps = cast<StructType>(AggTy)->getNumElements();
     
@@ -901,6 +903,10 @@ Constant *llvm::ConstantFoldInsertValueInstruction(Constant *Agg,
     
     if (const StructType* ST = dyn_cast<StructType>(AggTy))
       return ConstantStruct::get(ST->getContext(), Ops, ST->isPacked());
+    if (const UnionType* UT = dyn_cast<UnionType>(AggTy)) {
+      assert(Ops.size() == 1 && "Union can only contain a single value!");
+      return ConstantUnion::get(UT, Ops[0]);
+    }
     return ConstantArray::get(cast<ArrayType>(AggTy), Ops);
   }
   
diff --git a/lib/VMCore/Constants.cpp b/lib/VMCore/Constants.cpp
index 2250626..8cc6e94 100644
--- a/lib/VMCore/Constants.cpp
+++ b/lib/VMCore/Constants.cpp
@@ -585,6 +585,27 @@ Constant* ConstantStruct::get(LLVMContext &Context,
   return get(Context, std::vector<Constant*>(Vals, Vals+NumVals), Packed);
 }
 
+ConstantUnion::ConstantUnion(const UnionType *T, Constant* V)
+  : Constant(T, ConstantUnionVal,
+             OperandTraits<ConstantUnion>::op_end(this) - 1, 1) {
+  Use *OL = OperandList;
+  assert(T->getElementTypeIndex(V->getType()) >= 0 &&
+      "Initializer for union element isn't a member of union type!");
+  *OL = V;
+}
+
+// ConstantUnion accessors.
+Constant* ConstantUnion::get(const UnionType* T, Constant* V) {
+  LLVMContextImpl* pImpl = T->getContext().pImpl;
+  
+  // Create a ConstantAggregateZero value if all elements are zeros...
+  if (!V->isNullValue())
+    return pImpl->UnionConstants.getOrCreate(T, V);
+
+  return ConstantAggregateZero::get(T);
+}
+
+
 ConstantVector::ConstantVector(const VectorType *T,
                                const std::vector<Constant*> &V)
   : Constant(T, ConstantVectorVal,
@@ -1010,6 +1031,13 @@ void ConstantStruct::destroyConstant() {
 
 // destroyConstant - Remove the constant from the constant table...
 //
+void ConstantUnion::destroyConstant() {
+  getType()->getContext().pImpl->UnionConstants.remove(this);
+  destroyConstantImpl();
+}
+
+// destroyConstant - Remove the constant from the constant table...
+//
 void ConstantVector::destroyConstant() {
   getType()->getContext().pImpl->VectorConstants.remove(this);
   destroyConstantImpl();
@@ -2083,6 +2111,11 @@ void ConstantStruct::replaceUsesOfWithOnConstant(Value *From, Value *To,
   destroyConstant();
 }
 
+void ConstantUnion::replaceUsesOfWithOnConstant(Value *From, Value *To,
+                                                 Use *U) {
+  assert(false && "Implement replaceUsesOfWithOnConstant for unions");
+}
+
 void ConstantVector::replaceUsesOfWithOnConstant(Value *From, Value *To,
                                                  Use *U) {
   assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
diff --git a/lib/VMCore/ConstantsContext.h b/lib/VMCore/ConstantsContext.h
index 08224e4..c798ba2 100644
--- a/lib/VMCore/ConstantsContext.h
+++ b/lib/VMCore/ConstantsContext.h
@@ -341,6 +341,13 @@ struct ConstantTraits< std::vector<T, Alloc> > {
   }
 };
 
+template<>
+struct ConstantTraits<Constant *> {
+  static unsigned uses(Constant * const & v) {
+    return 1;
+  }
+};
+
 template<class ConstantClass, class TypeClass, class ValType>
 struct ConstantCreator {
   static ConstantClass *create(const TypeClass *Ty, const ValType &V) {
@@ -470,6 +477,14 @@ struct ConstantKeyData<ConstantStruct> {
   }
 };
 
+template<>
+struct ConstantKeyData<ConstantUnion> {
+  typedef Constant* ValType;
+  static ValType getValType(ConstantUnion *CU) {
+    return cast<Constant>(CU->getOperand(0));
+  }
+};
+
 // ConstantPointerNull does not take extra "value" argument...
 template<class ValType>
 struct ConstantCreator<ConstantPointerNull, PointerType, ValType> {
diff --git a/lib/VMCore/Core.cpp b/lib/VMCore/Core.cpp
index 1755cd2..a044fc5 100644
--- a/lib/VMCore/Core.cpp
+++ b/lib/VMCore/Core.cpp
@@ -141,6 +141,8 @@ LLVMTypeKind LLVMGetTypeKind(LLVMTypeRef Ty) {
     return LLVMFunctionTypeKind;
   case Type::StructTyID:
     return LLVMStructTypeKind;
+  case Type::UnionTyID:
+    return LLVMUnionTypeKind;
   case Type::ArrayTyID:
     return LLVMArrayTypeKind;
   case Type::PointerTyID:
@@ -299,6 +301,35 @@ LLVMBool LLVMIsPackedStruct(LLVMTypeRef StructTy) {
   return unwrap<StructType>(StructTy)->isPacked();
 }
 
+/*--.. Operations on union types ..........................................--*/
+
+LLVMTypeRef LLVMUnionTypeInContext(LLVMContextRef C, LLVMTypeRef *ElementTypes,
+                                   unsigned ElementCount) {
+  SmallVector<const Type*, 8> Tys;
+  for (LLVMTypeRef *I = ElementTypes,
+                   *E = ElementTypes + ElementCount; I != E; ++I)
+    Tys.push_back(unwrap(*I));
+  
+  return wrap(UnionType::get(&Tys[0], Tys.size()));
+}
+
+LLVMTypeRef LLVMUnionType(LLVMTypeRef *ElementTypes,
+                           unsigned ElementCount, int Packed) {
+  return LLVMUnionTypeInContext(LLVMGetGlobalContext(), ElementTypes,
+                                ElementCount);
+}
+
+unsigned LLVMCountUnionElementTypes(LLVMTypeRef UnionTy) {
+  return unwrap<UnionType>(UnionTy)->getNumElements();
+}
+
+void LLVMGetUnionElementTypes(LLVMTypeRef UnionTy, LLVMTypeRef *Dest) {
+  UnionType *Ty = unwrap<UnionType>(UnionTy);
+  for (FunctionType::param_iterator I = Ty->element_begin(),
+                                    E = Ty->element_end(); I != E; ++I)
+    *Dest++ = wrap(*I);
+}
+
 /*--.. Operations on array, pointer, and vector types (sequence types) .....--*/
 
 LLVMTypeRef LLVMArrayType(LLVMTypeRef ElementType, unsigned ElementCount) {
diff --git a/lib/VMCore/LLVMContextImpl.h b/lib/VMCore/LLVMContextImpl.h
index f7f4860..62491d8 100644
--- a/lib/VMCore/LLVMContextImpl.h
+++ b/lib/VMCore/LLVMContextImpl.h
@@ -116,6 +116,10 @@ public:
     ConstantStruct, true /*largekey*/> StructConstantsTy;
   StructConstantsTy StructConstants;
   
+  typedef ConstantUniqueMap<Constant*, UnionType, ConstantUnion>
+      UnionConstantsTy;
+  UnionConstantsTy UnionConstants;
+  
   typedef ConstantUniqueMap<std::vector<Constant*>, VectorType,
                             ConstantVector> VectorConstantsTy;
   VectorConstantsTy VectorConstants;
@@ -159,6 +163,7 @@ public:
   TypeMap<PointerValType, PointerType> PointerTypes;
   TypeMap<FunctionValType, FunctionType> FunctionTypes;
   TypeMap<StructValType, StructType> StructTypes;
+  TypeMap<UnionValType, UnionType> UnionTypes;
   TypeMap<IntegerValType, IntegerType> IntegerTypes;
 
   // Opaque types are not structurally uniqued, so don't use TypeMap.
diff --git a/lib/VMCore/Type.cpp b/lib/VMCore/Type.cpp
index cf85198..b1cdad5 100644
--- a/lib/VMCore/Type.cpp
+++ b/lib/VMCore/Type.cpp
@@ -50,8 +50,8 @@ void AbstractTypeUser::setType(Value *V, const Type *NewTy) {
 
 /// Because of the way Type subclasses are allocated, this function is necessary
 /// to use the correct kind of "delete" operator to deallocate the Type object.
-/// Some type objects (FunctionTy, StructTy) allocate additional space after 
-/// the space for their derived type to hold the contained types array of
+/// Some type objects (FunctionTy, StructTy, UnionTy) allocate additional space
+/// after the space for their derived type to hold the contained types array of
 /// PATypeHandles. Using this allocation scheme means all the PATypeHandles are
 /// allocated with the type object, decreasing allocations and eliminating the
 /// need for a std::vector to be used in the Type class itself. 
@@ -61,7 +61,8 @@ void Type::destroy() const {
   // Structures and Functions allocate their contained types past the end of
   // the type object itself. These need to be destroyed differently than the
   // other types.
-  if (isa<FunctionType>(this) || isa<StructType>(this)) {
+  if (isa<FunctionType>(this) || isa<StructType>(this) ||
+      isa<UnionType>(this)) {
     // First, make sure we destruct any PATypeHandles allocated by these
     // subclasses.  They must be manually destructed. 
     for (unsigned i = 0; i < NumContainedTys; ++i)
@@ -71,8 +72,10 @@ void Type::destroy() const {
     // to delete this as an array of char.
     if (isa<FunctionType>(this))
       static_cast<const FunctionType*>(this)->FunctionType::~FunctionType();
-    else
+    else if (isa<StructType>(this))
       static_cast<const StructType*>(this)->StructType::~StructType();
+    else
+      static_cast<const UnionType*>(this)->UnionType::~UnionType();
 
     // Finally, remove the memory as an array deallocation of the chars it was
     // constructed from.
@@ -226,7 +229,7 @@ bool Type::isSizedDerivedType() const {
   if (const VectorType *PTy = dyn_cast<VectorType>(this))
     return PTy->getElementType()->isSized();
 
-  if (!isa<StructType>(this)) 
+  if (!isa<StructType>(this) && !isa<UnionType>(this)) 
     return false;
 
   // Okay, our struct is sized if all of the elements are...
@@ -308,6 +311,32 @@ const Type *StructType::getTypeAtIndex(unsigned Idx) const {
   return ContainedTys[Idx];
 }
 
+
+bool UnionType::indexValid(const Value *V) const {
+  // Union indexes require 32-bit integer constants.
+  if (V->getType()->isInteger(32))
+    if (const ConstantInt *CU = dyn_cast<ConstantInt>(V))
+      return indexValid(CU->getZExtValue());
+  return false;
+}
+
+bool UnionType::indexValid(unsigned V) const {
+  return V < NumContainedTys;
+}
+
+// getTypeAtIndex - Given an index value into the type, return the type of the
+// element.  For a structure type, this must be a constant value...
+//
+const Type *UnionType::getTypeAtIndex(const Value *V) const {
+  unsigned Idx = (unsigned)cast<ConstantInt>(V)->getZExtValue();
+  return getTypeAtIndex(Idx);
+}
+
+const Type *UnionType::getTypeAtIndex(unsigned Idx) const {
+  assert(indexValid(Idx) && "Invalid structure index!");
+  return ContainedTys[Idx];
+}
+
 //===----------------------------------------------------------------------===//
 //                          Primitive 'Type' data
 //===----------------------------------------------------------------------===//
@@ -463,6 +492,23 @@ StructType::StructType(LLVMContext &C,
   setAbstract(isAbstract);
 }
 
+UnionType::UnionType(LLVMContext &C,const Type* const* Types, unsigned NumTypes)
+  : CompositeType(C, UnionTyID) {
+  ContainedTys = reinterpret_cast<PATypeHandle*>(this + 1);
+  NumContainedTys = NumTypes;
+  bool isAbstract = false;
+  for (unsigned i = 0; i < NumTypes; ++i) {
+    assert(Types[i] && "<null> type for union field!");
+    assert(isValidElementType(Types[i]) &&
+           "Invalid type for union element!");
+    new (&ContainedTys[i]) PATypeHandle(Types[i], this);
+    isAbstract |= Types[i]->isAbstract();
+  }
+
+  // Calculate whether or not this type is abstract
+  setAbstract(isAbstract);
+}
+
 ArrayType::ArrayType(const Type *ElType, uint64_t NumEl)
   : SequentialType(ArrayTyID, ElType) {
   NumElements = NumEl;
@@ -644,6 +690,13 @@ static bool TypesEqual(const Type *Ty, const Type *Ty2,
       if (!TypesEqual(STy->getElementType(i), STy2->getElementType(i), EqTypes))
         return false;
     return true;
+  } else if (const UnionType *UTy = dyn_cast<UnionType>(Ty)) {
+    const UnionType *UTy2 = cast<UnionType>(Ty2);
+    if (UTy->getNumElements() != UTy2->getNumElements()) return false;
+    for (unsigned i = 0, e = UTy2->getNumElements(); i != e; ++i)
+      if (!TypesEqual(UTy->getElementType(i), UTy2->getElementType(i), EqTypes))
+        return false;
+    return true;
   } else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
     const ArrayType *ATy2 = cast<ArrayType>(Ty2);
     return ATy->getNumElements() == ATy2->getNumElements() &&
@@ -901,12 +954,66 @@ StructType *StructType::get(LLVMContext &Context, const Type *type, ...) {
 }
 
 bool StructType::isValidElementType(const Type *ElemTy) {
-  return ElemTy->getTypeID() != VoidTyID && ElemTy->getTypeID() != LabelTyID &&
-         ElemTy->getTypeID() != MetadataTyID && !isa<FunctionType>(ElemTy);
+  return !ElemTy->isVoidTy() && !ElemTy->isLabelTy() &&
+         !ElemTy->isMetadataTy() && !isa<FunctionType>(ElemTy);
 }
 
 
 //===----------------------------------------------------------------------===//
+// Union Type Factory...
+//
+
+UnionType *UnionType::get(const Type* const* Types, unsigned NumTypes) {
+  assert(NumTypes > 0 && "union must have at least one member type!");
+  UnionValType UTV(Types, NumTypes);
+  UnionType *UT = 0;
+  
+  LLVMContextImpl *pImpl = Types[0]->getContext().pImpl;
+  
+  UT = pImpl->UnionTypes.get(UTV);
+    
+  if (!UT) {
+    // Value not found.  Derive a new type!
+    UT = (UnionType*) operator new(sizeof(UnionType) +
+                                   sizeof(PATypeHandle) * NumTypes);
+    new (UT) UnionType(Types[0]->getContext(), Types, NumTypes);
+    pImpl->UnionTypes.add(UTV, UT);
+  }
+#ifdef DEBUG_MERGE_TYPES
+  DEBUG(dbgs() << "Derived new type: " << *UT << "\n");
+#endif
+  return UT;
+}
+
+UnionType *UnionType::get(const Type *type, ...) {
+  va_list ap;
+  SmallVector<const llvm::Type*, 8> UnionFields;
+  va_start(ap, type);
+  while (type) {
+    UnionFields.push_back(type);
+    type = va_arg(ap, llvm::Type*);
+  }
+  unsigned NumTypes = UnionFields.size();
+  assert(NumTypes > 0 && "union must have at least one member type!");
+  return llvm::UnionType::get(&UnionFields[0], NumTypes);
+}
+
+bool UnionType::isValidElementType(const Type *ElemTy) {
+  return !ElemTy->isVoidTy() && !ElemTy->isLabelTy() &&
+         !ElemTy->isMetadataTy() && !ElemTy->isFunction();
+}
+
+int UnionType::getElementTypeIndex(const Type *ElemTy) const {
+  int index = 0;
+  for (UnionType::element_iterator I = element_begin(), E = element_end();
+       I != E; ++I, ++index) {
+     if (ElemTy == *I) return index;
+  }
+  
+  return -1;
+}
+
+//===----------------------------------------------------------------------===//
 // Pointer Type Factory...
 //
 
@@ -1169,6 +1276,21 @@ void StructType::typeBecameConcrete(const DerivedType *AbsTy) {
 // concrete - this could potentially change us from an abstract type to a
 // concrete type.
 //
+void UnionType::refineAbstractType(const DerivedType *OldType,
+                                    const Type *NewType) {
+  LLVMContextImpl *pImpl = OldType->getContext().pImpl;
+  pImpl->UnionTypes.RefineAbstractType(this, OldType, NewType);
+}
+
+void UnionType::typeBecameConcrete(const DerivedType *AbsTy) {
+  LLVMContextImpl *pImpl = AbsTy->getContext().pImpl;
+  pImpl->UnionTypes.TypeBecameConcrete(this, 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 PointerType::refineAbstractType(const DerivedType *OldType,
                                      const Type *NewType) {
   LLVMContextImpl *pImpl = OldType->getContext().pImpl;
diff --git a/lib/VMCore/TypesContext.h b/lib/VMCore/TypesContext.h
index 4842845..02ab113 100644
--- a/lib/VMCore/TypesContext.h
+++ b/lib/VMCore/TypesContext.h
@@ -180,6 +180,32 @@ public:
   }
 };
 
+// UnionValType - Define a class to hold the key that goes into the TypeMap
+//
+class UnionValType {
+  std::vector<const Type*> ElTypes;
+public:
+  UnionValType(const Type* const* Types, unsigned NumTypes)
+    : ElTypes(&Types[0], &Types[NumTypes]) {}
+
+  static UnionValType get(const UnionType *UT) {
+    std::vector<const Type *> ElTypes;
+    ElTypes.reserve(UT->getNumElements());
+    for (unsigned i = 0, e = UT->getNumElements(); i != e; ++i)
+      ElTypes.push_back(UT->getElementType(i));
+
+    return UnionValType(&ElTypes[0], ElTypes.size());
+  }
+
+  static unsigned hashTypeStructure(const UnionType *UT) {
+    return UT->getNumElements();
+  }
+
+  inline bool operator<(const UnionValType &UTV) const {
+    return (ElTypes < UTV.ElTypes);
+  }
+};
+
 // FunctionValType - Define a class to hold the key that goes into the TypeMap
 //
 class FunctionValType {
diff --git a/test/Assembler/2010-01-06-UnionType.ll b/test/Assembler/2010-01-06-UnionType.ll
new file mode 100644
index 0000000..37130d6
--- /dev/null
+++ b/test/Assembler/2010-01-06-UnionType.ll
@@ -0,0 +1,3 @@
+; RUN: llvm-as %s -o /dev/null
+
+%X = type union { i32, i32* }
diff --git a/test/Feature/unions.ll b/test/Feature/unions.ll
new file mode 100644
index 0000000..9d6c36b
--- /dev/null
+++ b/test/Feature/unions.ll
@@ -0,0 +1,12 @@
+; RUN: llvm-as < %s | llvm-dis > %t1.ll
+; RUN: llvm-as %t1.ll -o - | llvm-dis > %t2.ll
+; RUN: diff %t1.ll %t2.ll
+
+%union.anon = type union { i8, i32, float }
+
+@union1 = constant union { i32, i8 } { i32 4 }
+@union2 = constant union { i32, i8 } insertvalue(union { i32, i8 } undef, i32 4, 0)
+
+define void @"Unions" () {
+  ret void
+}