Land the long talked about "type system rewrite" patch. This

patch brings numerous advantages to LLVM.  One way to look at it
is through diffstat:
 109 files changed, 3005 insertions(+), 5906 deletions(-)

Removing almost 3K lines of code is a good thing.  Other advantages
include:

1. Value::getType() is a simple load that can be CSE'd, not a mutating
   union-find operation.
2. Types a uniqued and never move once created, defining away PATypeHolder.
3. Structs can be "named" now, and their name is part of the identity that
   uniques them.  This means that the compiler doesn't merge them structurally
   which makes the IR much less confusing.
4. Now that there is no way to get a cycle in a type graph without a named
   struct type, "upreferences" go away.
5. Type refinement is completely gone, which should make LTO much MUCH faster
   in some common cases with C++ code.
6. Types are now generally immutable, so we can use "Type *" instead 
   "const Type *" everywhere.

Downsides of this patch are that it removes some functions from the C API,
so people using those will have to upgrade to (not yet added) new API.  
"LLVM 3.0" is the right time to do this.

There are still some cleanups pending after this, this patch is large enough
as-is.




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

1 files changed, 322 insertions, 68 deletions

diff --git a/lib/Bitcode/Reader/BitcodeReader.cpp b/lib/Bitcode/Reader/BitcodeReader.cpp
index 963791f5d6..1bdcfe98d4 100644
--- a/lib/Bitcode/Reader/BitcodeReader.cpp
+++ b/lib/Bitcode/Reader/BitcodeReader.cpp
@@ -31,7 +31,7 @@ void BitcodeReader::FreeState() {
   if (BufferOwned)
     delete Buffer;
   Buffer = 0;
-  std::vector<PATypeHolder>().swap(TypeList);
+  std::vector<Type*>().swap(TypeList);
   ValueList.clear();
   MDValueList.clear();
 
@@ -352,19 +352,28 @@ Value *BitcodeReaderMDValueList::getValueFwdRef(unsigned Idx) {
   return V;
 }
 
-const Type *BitcodeReader::getTypeByID(unsigned ID, bool isTypeTable) {
-  // If the TypeID is in range, return it.
-  if (ID < TypeList.size())
-    return TypeList[ID].get();
-  if (!isTypeTable) return 0;
-
-  // The type table allows forward references.  Push as many Opaque types as
-  // needed to get up to ID.
-  while (TypeList.size() <= ID)
-    TypeList.push_back(OpaqueType::get(Context));
-  return TypeList.back().get();
+Type *BitcodeReader::getTypeByID(unsigned ID) {
+  // The type table size is always specified correctly.
+  if (ID >= TypeList.size())
+    return 0;
+  
+  if (Type *Ty = TypeList[ID])
+    return Ty;
+
+  // If we have a forward reference, the only possible case is when it is to a
+  // named struct.  Just create a placeholder for now.
+  return TypeList[ID] = StructType::createNamed(Context, "");
+}
+
+/// FIXME: Remove in LLVM 3.1, only used by ParseOldTypeTable.
+Type *BitcodeReader::getTypeByIDOrNull(unsigned ID) {
+  if (ID >= TypeList.size())
+    TypeList.resize(ID+1);
+  
+  return TypeList[ID];
 }
 
+
 //===----------------------------------------------------------------------===//
 //  Functions for parsing blocks from the bitcode file
 //===----------------------------------------------------------------------===//
@@ -471,17 +480,22 @@ bool BitcodeReader::ParseAttributeBlock() {
   }
 }
 
-
 bool BitcodeReader::ParseTypeTable() {
-  if (Stream.EnterSubBlock(bitc::TYPE_BLOCK_ID))
+  if (Stream.EnterSubBlock(bitc::TYPE_BLOCK_ID_NEW))
     return Error("Malformed block record");
+  
+  return ParseTypeTableBody();
+}
 
+bool BitcodeReader::ParseTypeTableBody() {
   if (!TypeList.empty())
     return Error("Multiple TYPE_BLOCKs found!");
 
   SmallVector<uint64_t, 64> Record;
   unsigned NumRecords = 0;
 
+  SmallString<64> TypeName;
+  
   // Read all the records for this type table.
   while (1) {
     unsigned Code = Stream.ReadCode();
@@ -508,17 +522,15 @@ bool BitcodeReader::ParseTypeTable() {
 
     // Read a record.
     Record.clear();
-    const Type *ResultTy = 0;
+    Type *ResultTy = 0;
     switch (Stream.ReadRecord(Code, Record)) {
-    default:  // Default behavior: unknown type.
-      ResultTy = 0;
-      break;
+    default: return Error("unknown type in type table");
     case bitc::TYPE_CODE_NUMENTRY: // TYPE_CODE_NUMENTRY: [numentries]
       // TYPE_CODE_NUMENTRY contains a count of the number of types in the
       // type list.  This allows us to reserve space.
       if (Record.size() < 1)
         return Error("Invalid TYPE_CODE_NUMENTRY record");
-      TypeList.reserve(Record[0]);
+      TypeList.resize(Record[0]);
       continue;
     case bitc::TYPE_CODE_VOID:      // VOID
       ResultTy = Type::getVoidTy(Context);
@@ -541,9 +553,6 @@ bool BitcodeReader::ParseTypeTable() {
     case bitc::TYPE_CODE_LABEL:     // LABEL
       ResultTy = Type::getLabelTy(Context);
       break;
-    case bitc::TYPE_CODE_OPAQUE:    // OPAQUE
-      ResultTy = 0;
-      break;
     case bitc::TYPE_CODE_METADATA:  // METADATA
       ResultTy = Type::getMetadataTy(Context);
       break;
@@ -563,8 +572,9 @@ bool BitcodeReader::ParseTypeTable() {
       unsigned AddressSpace = 0;
       if (Record.size() == 2)
         AddressSpace = Record[1];
-      ResultTy = PointerType::get(getTypeByID(Record[0], true),
-                                        AddressSpace);
+      ResultTy = getTypeByID(Record[0]);
+      if (ResultTy == 0) return Error("invalid element type in pointer type");
+      ResultTy = PointerType::get(ResultTy, AddressSpace);
       break;
     }
     case bitc::TYPE_CODE_FUNCTION: {
@@ -573,68 +583,305 @@ bool BitcodeReader::ParseTypeTable() {
       if (Record.size() < 3)
         return Error("Invalid FUNCTION type record");
       std::vector<const Type*> ArgTys;
-      for (unsigned i = 3, e = Record.size(); i != e; ++i)
-        ArgTys.push_back(getTypeByID(Record[i], true));
+      for (unsigned i = 3, e = Record.size(); i != e; ++i) {
+        if (Type *T = getTypeByID(Record[i]))
+          ArgTys.push_back(T);
+        else
+          break;
+      }
+      
+      ResultTy = getTypeByID(Record[2]);
+      if (ResultTy == 0 || ArgTys.size() < Record.size()-3)
+        return Error("invalid type in function type");
 
-      ResultTy = FunctionType::get(getTypeByID(Record[2], true), ArgTys,
-                                   Record[0]);
+      ResultTy = FunctionType::get(ResultTy, ArgTys, Record[0]);
       break;
     }
-    case bitc::TYPE_CODE_STRUCT: {  // STRUCT: [ispacked, eltty x N]
+    case bitc::TYPE_CODE_STRUCT_ANON: {  // STRUCT: [ispacked, eltty x N]
       if (Record.size() < 1)
         return Error("Invalid STRUCT type record");
-      std::vector<const Type*> EltTys;
-      for (unsigned i = 1, e = Record.size(); i != e; ++i)
-        EltTys.push_back(getTypeByID(Record[i], true));
+      std::vector<Type*> EltTys;
+      for (unsigned i = 1, e = Record.size(); i != e; ++i) {
+        if (Type *T = getTypeByID(Record[i]))
+          EltTys.push_back(T);
+        else
+          break;
+      }
+      if (EltTys.size() != Record.size()-1)
+        return Error("invalid type in struct type");
       ResultTy = StructType::get(Context, EltTys, Record[0]);
       break;
     }
+    case bitc::TYPE_CODE_STRUCT_NAME:   // STRUCT_NAME: [strchr x N]
+      if (ConvertToString(Record, 0, TypeName))
+        return Error("Invalid STRUCT_NAME record");
+      continue;
+
+    case bitc::TYPE_CODE_STRUCT_NAMED: { // STRUCT: [ispacked, eltty x N]
+      if (Record.size() < 1)
+        return Error("Invalid STRUCT type record");
+      
+      if (NumRecords >= TypeList.size())
+        return Error("invalid TYPE table");
+      
+      // Check to see if this was forward referenced, if so fill in the temp.
+      StructType *Res = cast_or_null<StructType>(TypeList[NumRecords]);
+      if (Res) {
+        Res->setName(TypeName);
+        TypeList[NumRecords] = 0;
+      } else  // Otherwise, create a new struct.
+        Res = StructType::createNamed(Context, TypeName);
+      TypeName.clear();
+      
+      SmallVector<Type*, 8> EltTys;
+      for (unsigned i = 1, e = Record.size(); i != e; ++i) {
+        if (Type *T = getTypeByID(Record[i]))
+          EltTys.push_back(T);
+        else
+          break;
+      }
+      if (EltTys.size() != Record.size()-1)
+        return Error("invalid STRUCT type record");
+      Res->setBody(EltTys, Record[0]);
+      ResultTy = Res;
+      break;
+    }
+    case bitc::TYPE_CODE_OPAQUE: {       // OPAQUE: []
+      if (Record.size() != 1)
+        return Error("Invalid OPAQUE type record");
+
+      if (NumRecords >= TypeList.size())
+        return Error("invalid TYPE table");
+      
+      // Check to see if this was forward referenced, if so fill in the temp.
+      StructType *Res = cast_or_null<StructType>(TypeList[NumRecords]);
+      if (Res) {
+        Res->setName(TypeName);
+        TypeList[NumRecords] = 0;
+      } else  // Otherwise, create a new struct with no body.
+        Res = StructType::createNamed(Context, TypeName);
+      TypeName.clear();
+      ResultTy = Res;
+      break;
+    }        
     case bitc::TYPE_CODE_ARRAY:     // ARRAY: [numelts, eltty]
       if (Record.size() < 2)
         return Error("Invalid ARRAY type record");
-      ResultTy = ArrayType::get(getTypeByID(Record[1], true), Record[0]);
+      if ((ResultTy = getTypeByID(Record[1])))
+        ResultTy = ArrayType::get(ResultTy, Record[0]);
+      else
+        return Error("Invalid ARRAY type element");
       break;
     case bitc::TYPE_CODE_VECTOR:    // VECTOR: [numelts, eltty]
       if (Record.size() < 2)
         return Error("Invalid VECTOR type record");
-      ResultTy = VectorType::get(getTypeByID(Record[1], true), Record[0]);
+      if ((ResultTy = getTypeByID(Record[1])))
+        ResultTy = VectorType::get(ResultTy, Record[0]);
+      else
+        return Error("Invalid ARRAY type element");
       break;
     }
 
-    if (NumRecords == TypeList.size()) {
-      // If this is a new type slot, just append it.
-      TypeList.push_back(ResultTy ? ResultTy : OpaqueType::get(Context));
-      ++NumRecords;
-    } else if (ResultTy == 0) {
-      // Otherwise, this was forward referenced, so an opaque type was created,
-      // but the result type is actually just an opaque.  Leave the one we
-      // created previously.
-      ++NumRecords;
-    } else {
-      // Otherwise, this was forward referenced, so an opaque type was created.
-      // Resolve the opaque type to the real type now.
-      assert(NumRecords < TypeList.size() && "Typelist imbalance");
-      const OpaqueType *OldTy = cast<OpaqueType>(TypeList[NumRecords++].get());
-
-      // Don't directly push the new type on the Tab. Instead we want to replace
-      // the opaque type we previously inserted with the new concrete value. The
-      // refinement from the abstract (opaque) type to the new type causes all
-      // uses of the abstract type to use the concrete type (NewTy). This will
-      // also cause the opaque type to be deleted.
-      const_cast<OpaqueType*>(OldTy)->refineAbstractTypeTo(ResultTy);
-
-      // This should have replaced the old opaque type with the new type in the
-      // value table... or with a preexisting type that was already in the
-      // system.  Let's just make sure it did.
-      assert(TypeList[NumRecords-1].get() != OldTy &&
-             "refineAbstractType didn't work!");
+    if (NumRecords >= TypeList.size())
+      return Error("invalid TYPE table");
+    assert(ResultTy && "Didn't read a type?");
+    assert(TypeList[NumRecords] == 0 && "Already read type?");
+    TypeList[NumRecords++] = ResultTy;
+  }
+}
+
+// FIXME: Remove in LLVM 3.1
+bool BitcodeReader::ParseOldTypeTable() {
+  if (Stream.EnterSubBlock(bitc::TYPE_BLOCK_ID_OLD))
+    return Error("Malformed block record");
+
+  if (!TypeList.empty())
+    return Error("Multiple TYPE_BLOCKs found!");
+  
+  
+  // While horrible, we have no good ordering of types in the bc file.  Just
+  // iteratively parse types out of the bc file in multiple passes until we get
+  // them all.  Do this by saving a cursor for the start of the type block.
+  BitstreamCursor StartOfTypeBlockCursor(Stream);
+  
+  unsigned NumTypesRead = 0;
+  
+  SmallVector<uint64_t, 64> Record;
+RestartScan:
+  unsigned NextTypeID = 0;
+  bool ReadAnyTypes = false;
+  
+  // Read all the records for this type table.
+  while (1) {
+    unsigned Code = Stream.ReadCode();
+    if (Code == bitc::END_BLOCK) {
+      if (NextTypeID != TypeList.size())
+        return Error("Invalid type forward reference in TYPE_BLOCK_ID_OLD");
+      
+      // If we haven't read all of the types yet, iterate again.
+      if (NumTypesRead != TypeList.size()) {
+        // If we didn't successfully read any types in this pass, then we must
+        // have an unhandled forward reference.
+        if (!ReadAnyTypes)
+          return Error("Obsolete bitcode contains unhandled recursive type");
+        
+        Stream = StartOfTypeBlockCursor;
+        goto RestartScan;
+      }
+      
+      if (Stream.ReadBlockEnd())
+        return Error("Error at end of type table block");
+      return false;
+    }
+    
+    if (Code == bitc::ENTER_SUBBLOCK) {
+      // No known subblocks, always skip them.
+      Stream.ReadSubBlockID();
+      if (Stream.SkipBlock())
+        return Error("Malformed block record");
+      continue;
     }
+    
+    if (Code == bitc::DEFINE_ABBREV) {
+      Stream.ReadAbbrevRecord();
+      continue;
+    }
+    
+    // Read a record.
+    Record.clear();
+    Type *ResultTy = 0;
+    switch (Stream.ReadRecord(Code, Record)) {
+    default: return Error("unknown type in type table");
+    case bitc::TYPE_CODE_NUMENTRY: // TYPE_CODE_NUMENTRY: [numentries]
+      // TYPE_CODE_NUMENTRY contains a count of the number of types in the
+      // type list.  This allows us to reserve space.
+      if (Record.size() < 1)
+        return Error("Invalid TYPE_CODE_NUMENTRY record");
+      TypeList.resize(Record[0]);
+      continue;
+    case bitc::TYPE_CODE_VOID:      // VOID
+      ResultTy = Type::getVoidTy(Context);
+      break;
+    case bitc::TYPE_CODE_FLOAT:     // FLOAT
+      ResultTy = Type::getFloatTy(Context);
+      break;
+    case bitc::TYPE_CODE_DOUBLE:    // DOUBLE
+      ResultTy = Type::getDoubleTy(Context);
+      break;
+    case bitc::TYPE_CODE_X86_FP80:  // X86_FP80
+      ResultTy = Type::getX86_FP80Ty(Context);
+      break;
+    case bitc::TYPE_CODE_FP128:     // FP128
+      ResultTy = Type::getFP128Ty(Context);
+      break;
+    case bitc::TYPE_CODE_PPC_FP128: // PPC_FP128
+      ResultTy = Type::getPPC_FP128Ty(Context);
+      break;
+    case bitc::TYPE_CODE_LABEL:     // LABEL
+      ResultTy = Type::getLabelTy(Context);
+      break;
+    case bitc::TYPE_CODE_METADATA:  // METADATA
+      ResultTy = Type::getMetadataTy(Context);
+      break;
+    case bitc::TYPE_CODE_X86_MMX:   // X86_MMX
+      ResultTy = Type::getX86_MMXTy(Context);
+      break;
+    case bitc::TYPE_CODE_INTEGER:   // INTEGER: [width]
+      if (Record.size() < 1)
+        return Error("Invalid Integer type record");
+      ResultTy = IntegerType::get(Context, Record[0]);
+      break;
+    case bitc::TYPE_CODE_OPAQUE:    // OPAQUE
+      if (NextTypeID < TypeList.size() && TypeList[NextTypeID] == 0)
+        ResultTy = StructType::createNamed(Context, "");
+      break;
+    case bitc::TYPE_CODE_STRUCT_OLD: {// STRUCT_OLD
+      if (NextTypeID >= TypeList.size()) break;
+      // If we already read it, don't reprocess.
+      if (TypeList[NextTypeID] &&
+          !cast<StructType>(TypeList[NextTypeID])->isOpaque())
+        break;
+
+      // Set a type.
+      if (TypeList[NextTypeID] == 0)
+        TypeList[NextTypeID] = StructType::createNamed(Context, "");
+
+      std::vector<Type*> EltTys;
+      for (unsigned i = 1, e = Record.size(); i != e; ++i) {
+        if (Type *Elt = getTypeByIDOrNull(Record[i]))
+          EltTys.push_back(Elt);
+        else
+          break;
+      }
+
+      if (EltTys.size() != Record.size()-1)
+        break;      // Not all elements are ready.
+      
+      cast<StructType>(TypeList[NextTypeID])->setBody(EltTys, Record[0]);
+      ResultTy = TypeList[NextTypeID];
+      TypeList[NextTypeID] = 0;
+      break;
+    }
+    case bitc::TYPE_CODE_POINTER: { // POINTER: [pointee type] or
+      //          [pointee type, address space]
+      if (Record.size() < 1)
+        return Error("Invalid POINTER type record");
+      unsigned AddressSpace = 0;
+      if (Record.size() == 2)
+        AddressSpace = Record[1];
+      if ((ResultTy = getTypeByIDOrNull(Record[0])))
+        ResultTy = PointerType::get(ResultTy, AddressSpace);
+      break;
+    }
+    case bitc::TYPE_CODE_FUNCTION: {
+      // FIXME: attrid is dead, remove it in LLVM 3.0
+      // FUNCTION: [vararg, attrid, retty, paramty x N]
+      if (Record.size() < 3)
+        return Error("Invalid FUNCTION type record");
+      std::vector<const Type*> ArgTys;
+      for (unsigned i = 3, e = Record.size(); i != e; ++i) {
+        if (Type *Elt = getTypeByIDOrNull(Record[i]))
+          ArgTys.push_back(Elt);
+        else
+          break;
+      }
+      if (ArgTys.size()+3 != Record.size())
+        break;  // Something was null.
+      if ((ResultTy = getTypeByIDOrNull(Record[2])))
+        ResultTy = FunctionType::get(ResultTy, ArgTys, Record[0]);
+      break;
+    }
+    case bitc::TYPE_CODE_ARRAY:     // ARRAY: [numelts, eltty]
+      if (Record.size() < 2)
+        return Error("Invalid ARRAY type record");
+      if ((ResultTy = getTypeByIDOrNull(Record[1])))
+        ResultTy = ArrayType::get(ResultTy, Record[0]);
+      break;
+    case bitc::TYPE_CODE_VECTOR:    // VECTOR: [numelts, eltty]
+      if (Record.size() < 2)
+        return Error("Invalid VECTOR type record");
+      if ((ResultTy = getTypeByIDOrNull(Record[1])))
+        ResultTy = VectorType::get(ResultTy, Record[0]);
+      break;
+    }
+    
+    if (NextTypeID >= TypeList.size())
+      return Error("invalid TYPE table");
+    
+    if (ResultTy && TypeList[NextTypeID] == 0) {
+      ++NumTypesRead;
+      ReadAnyTypes = true;
+      
+      TypeList[NextTypeID] = ResultTy;
+    }
+    
+    ++NextTypeID;
   }
 }
 
 
-bool BitcodeReader::ParseTypeSymbolTable() {
-  if (Stream.EnterSubBlock(bitc::TYPE_SYMTAB_BLOCK_ID))
+bool BitcodeReader::ParseOldTypeSymbolTable() {
+  if (Stream.EnterSubBlock(bitc::TYPE_SYMTAB_BLOCK_ID_OLD))
     return Error("Malformed block record");
 
   SmallVector<uint64_t, 64> Record;
@@ -674,7 +921,10 @@ bool BitcodeReader::ParseTypeSymbolTable() {
       if (TypeID >= TypeList.size())
         return Error("Invalid Type ID in TST_ENTRY record");
 
-      TheModule->addTypeName(TypeName, TypeList[TypeID].get());
+      // Only apply the type name to a struct type with no name.
+      if (StructType *STy = dyn_cast<StructType>(TypeList[TypeID]))
+        if (!STy->isAnonymous() && !STy->hasName())
+          STy->setName(TypeName);
       TypeName.clear();
       break;
     }
@@ -1310,12 +1560,16 @@ bool BitcodeReader::ParseModule() {
         if (ParseAttributeBlock())
           return true;
         break;
-      case bitc::TYPE_BLOCK_ID:
+      case bitc::TYPE_BLOCK_ID_NEW:
         if (ParseTypeTable())
           return true;
         break;
-      case bitc::TYPE_SYMTAB_BLOCK_ID:
-        if (ParseTypeSymbolTable())
+      case bitc::TYPE_BLOCK_ID_OLD:
+        if (ParseOldTypeTable())
+          return true;
+        break;
+      case bitc::TYPE_SYMTAB_BLOCK_ID_OLD:
+        if (ParseOldTypeSymbolTable())
           return true;
         break;
       case bitc::VALUE_SYMTAB_BLOCK_ID:
@@ -2307,7 +2561,7 @@ bool BitcodeReader::ParseFunctionBody(Function *F) {
       SmallVector<Value*, 16> Args;
       // Read the fixed params.
       for (unsigned i = 0, e = FTy->getNumParams(); i != e; ++i, ++OpNum) {
-        if (FTy->getParamType(i)->getTypeID()==Type::LabelTyID)
+        if (FTy->getParamType(i)->isLabelTy())
           Args.push_back(getBasicBlock(Record[OpNum]));
         else
           Args.push_back(getFnValueByID(Record[OpNum], FTy->getParamType(i)));