Index: include/llvm/IR/Type.h
===================================================================
--- include/llvm/IR/Type.h
+++ include/llvm/IR/Type.h
@@ -17,6 +17,7 @@
 
 #include "llvm/ADT/APFloat.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/Support/CBindingWrapping.h"
 #include "llvm/Support/Casting.h"
@@ -440,6 +441,9 @@
   static PointerType *getInt32PtrTy(LLVMContext &C, unsigned AS = 0);
   static PointerType *getInt64PtrTy(LLVMContext &C, unsigned AS = 0);
 
+  /// Return a map containing identifiers for the created unnamed types.
+  static MapVector<Type *, unsigned> &getUnnamedTypes(LLVMContext &C);
+
   /// Return a pointer to the current type. This is equivalent to
   /// PointerType::get(Foo, AddrSpace).
   PointerType *getPointerTo(unsigned AddrSpace = 0) const;
Index: lib/Bitcode/Writer/ValueEnumerator.cpp
===================================================================
--- lib/Bitcode/Writer/ValueEnumerator.cpp
+++ lib/Bitcode/Writer/ValueEnumerator.cpp
@@ -324,6 +324,11 @@
   if (ShouldPreserveUseListOrder)
     UseListOrders = predictUseListOrder(M);
 
+  // Enumerate unnamed types first, so they are created in a deterministic
+  // order.
+  for (auto &T : Type::getUnnamedTypes(M.getContext()))
+    EnumerateType(T.first);
+
   // Enumerate the global variables.
   for (const GlobalVariable &GV : M.globals())
     EnumerateValue(&GV);
Index: lib/IR/Function.cpp
===================================================================
--- lib/IR/Function.cpp
+++ lib/IR/Function.cpp
@@ -570,7 +570,14 @@
   } else if (StructType *STyp = dyn_cast<StructType>(Ty)) {
     if (!STyp->isLiteral()) {
       Result += "s_";
-      Result += STyp->getName();
+      if (STyp->hasName())
+        Result += STyp->getName();
+      else {
+        // Different unnamed struct types should get mangled to different names,
+        // so we use the generated ID here.
+        auto &UnnamedIDs = Type::getUnnamedTypes(STyp->getContext());
+        Result += Twine(UnnamedIDs[STyp]).str();
+      }
     } else {
       Result += "sl_";
       for (auto Elem : STyp->elements())
Index: lib/IR/LLVMContextImpl.h
===================================================================
--- lib/IR/LLVMContextImpl.h
+++ lib/IR/LLVMContextImpl.h
@@ -25,6 +25,7 @@
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/Hashing.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallPtrSet.h"
@@ -1306,7 +1307,12 @@
   StructTypeSet AnonStructTypes;
   StringMap<StructType*> NamedStructTypes;
   unsigned NamedStructTypesUniqueID = 0;
-    
+
+  /// Mapping from unnamed types to a deterministic ID for mangling.
+  /// It is populated at type creation time.
+  MapVector<Type *, unsigned> UnnamedTypeIDs;
+  unsigned UnnamedTypesUniqueID = 0;
+
   DenseMap<std::pair<Type *, uint64_t>, ArrayType*> ArrayTypes;
   DenseMap<std::pair<Type *, unsigned>, VectorType*> VectorTypes;
   DenseMap<Type*, PointerType*> PointerTypes;  // Pointers in AddrSpace = 0
Index: lib/IR/Type.cpp
===================================================================
--- lib/IR/Type.cpp
+++ lib/IR/Type.cpp
@@ -177,6 +177,10 @@
 IntegerType *Type::getInt64Ty(LLVMContext &C) { return &C.pImpl->Int64Ty; }
 IntegerType *Type::getInt128Ty(LLVMContext &C) { return &C.pImpl->Int128Ty; }
 
+MapVector<Type *, unsigned> &Type::getUnnamedTypes(LLVMContext &C) {
+  return C.pImpl->UnnamedTypeIDs;
+}
+
 IntegerType *Type::getIntNTy(LLVMContext &C, unsigned N) {
   return IntegerType::get(C, N);
 }
@@ -425,6 +429,13 @@
   StructType *ST = new (Context.pImpl->TypeAllocator) StructType(Context);
   if (!Name.empty())
     ST->setName(Name);
+  else {
+    auto *Impl = Context.pImpl;
+    auto I =
+        Type::getUnnamedTypes(Context).insert({ST, Impl->UnnamedTypesUniqueID});
+    if (I.second)
+      Impl->UnnamedTypesUniqueID++;
+  }
   return ST;
 }
 
Index: test/Bitcode/intrinsics-with-unnamed-types.ll
===================================================================
--- /dev/null
+++ test/Bitcode/intrinsics-with-unnamed-types.ll
@@ -0,0 +1,23 @@
+; RUN: llvm-as -o - %s | llvm-dis -o - 2>&1 | FileCheck %s
+
+; Make sure we can assemble and disassemble IR containing intrinsics with
+; unnamed types.
+
+%1 = type opaque
+%0 = type opaque
+
+; CHECK-LABEL: @f0(
+; CHECK: %c1 = call %0* @llvm.ssa.copy.p0s_1s(%0* %arg)
+; CHECK: %c2 = call %1* @llvm.ssa.copy.p0s_0s(%1* %tmp)
+
+define void @f0(%0* %arg, %1* %tmp) {
+bb:
+  %cmp1 = icmp ne %0* %arg, null
+  %c1 = call %0* @llvm.ssa.copy.p0s_1s(%0* %arg)
+  %c2 = call %1* @llvm.ssa.copy.p0s_0s(%1* %tmp)
+  ret void
+}
+
+declare %0* @llvm.ssa.copy.p0s_1s(%0* returned)
+
+declare %1* @llvm.ssa.copy.p0s_0s(%1* returned)
Index: test/Transforms/Util/PredicateInfo/unnamed-types.ll
===================================================================
--- /dev/null
+++ test/Transforms/Util/PredicateInfo/unnamed-types.ll
@@ -0,0 +1,40 @@
+; RUN: opt < %s -print-predicateinfo 2>&1 | FileCheck %s
+
+%1 = type opaque
+%0 = type opaque
+
+; Check we can use ssa.copy with unnamed types.
+
+; CHECK-LABEL: bb:
+; CHECK: Has predicate info
+; CHECK: branch predicate info { TrueEdge: 1 Comparison:  %cmp1 = icmp ne %0* %arg, null Edge: [label %bb,label %bb1] }
+; CHECK-NEXT:  %arg.0 = call %0* @llvm.ssa.copy.p0s_1s(%0* %arg)
+
+; CHECK-LABEL: bb1:
+; CHECK: Has predicate info
+; CHECK-NEXT: branch predicate info { TrueEdge: 0 Comparison:  %cmp2 = icmp ne %1* null, %tmp Edge: [label %bb1,label %bb3] }
+; CHECK-NAME: %tmp.0 = call %1* @llvm.ssa.copy.p0s_0s(%1* %tmp)
+
+define void @f0(%0* %arg, %1* %tmp) {
+bb:
+  %cmp1 = icmp ne %0* %arg, null
+  br i1 %cmp1, label %bb1, label %bb2
+
+bb1:                                              ; preds = %bb
+  %cmp2 = icmp ne %1* null, %tmp
+  br i1 %cmp2, label %bb2, label %bb3
+
+bb2:                                              ; preds = %bb
+  ret void
+
+bb3:                                              ; preds = %bb
+  %u1 = call i8* @fun(%1* %tmp)
+  %tmp2 = bitcast %0* %arg to i8*
+  ret void
+}
+
+declare %0* @llvm.ssa.copy.p0s_1s(%0* returned)
+
+declare %1* @llvm.ssa.copy.p0s_0s(%1* returned)
+
+declare i8* @fun(%1*)