Packed types, brought to you by Brad Jones

llvm-svn: 15938

9 files changed, 336 insertions, 6 deletions

diff --git a/llvm/lib/AsmParser/llvmAsmParser.y b/llvm/lib/AsmParser/llvmAsmParser.y
index e48d6cfc9fc..1a4ad32a972 100644
--- a/llvm/lib/AsmParser/llvmAsmParser.y
+++ b/llvm/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/llvm/lib/Bytecode/Reader/Analyzer.cpp b/llvm/lib/Bytecode/Reader/Analyzer.cpp
index f6739ae3c6f..bc1f0c74cdd 100644
--- a/llvm/lib/Bytecode/Reader/Analyzer.cpp
+++ b/llvm/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/llvm/lib/Bytecode/Reader/Reader.cpp b/llvm/lib/Bytecode/Reader/Reader.cpp
index 85a890dbc43..a9dbe9d5455 100644
--- a/llvm/lib/Bytecode/Reader/Reader.cpp
+++ b/llvm/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/llvm/lib/Bytecode/Writer/Writer.cpp b/llvm/lib/Bytecode/Writer/Writer.cpp
index c3fad712f2b..6654fd1b023 100644
--- a/llvm/lib/Bytecode/Writer/Writer.cpp
+++ b/llvm/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/llvm/lib/VMCore/AsmWriter.cpp b/llvm/lib/VMCore/AsmWriter.cpp
index 4cfba7668f5..9fc772ecba5 100644
--- a/llvm/lib/VMCore/AsmWriter.cpp
+++ b/llvm/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/llvm/lib/VMCore/Constants.cpp b/llvm/lib/VMCore/Constants.cpp
index 69f1a78412e..8b28c0d3ff6 100644
--- a/llvm/lib/VMCore/Constants.cpp
+++ b/llvm/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/llvm/lib/VMCore/Instructions.cpp b/llvm/lib/VMCore/Instructions.cpp
index 205f32b4605..74907dd7c44 100644
--- a/llvm/lib/VMCore/Instructions.cpp
+++ b/llvm/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/llvm/lib/VMCore/Type.cpp b/llvm/lib/VMCore/Type.cpp
index c6ce34701cf..bd0da45f460 100644
--- a/llvm/lib/VMCore/Type.cpp
+++ b/llvm/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/llvm/lib/VMCore/Verifier.cpp b/llvm/lib/VMCore/Verifier.cpp
index 2005dbf5845..9e99fe0136c 100644
--- a/llvm/lib/VMCore/Verifier.cpp
+++ b/llvm/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);