Index: lib/IR/Function.cpp
===================================================================
--- lib/IR/Function.cpp
+++ lib/IR/Function.cpp
@@ -533,10 +533,18 @@
   } else if (ArrayType* ATyp = dyn_cast<ArrayType>(Ty)) {
     Result += "a" + llvm::utostr(ATyp->getNumElements()) +
       getMangledTypeStr(ATyp->getElementType());
-  } else if (StructType* STyp = dyn_cast<StructType>(Ty)) {
-    assert(!STyp->isLiteral() && "TODO: implement literal types");
-    Result += STyp->getName();
-  } else if (FunctionType* FT = dyn_cast<FunctionType>(Ty)) {
+  } else if (StructType *STyp = dyn_cast<StructType>(Ty)) {
+    if (!STyp->isLiteral()) {
+      Result += "s_";
+      Result += STyp->getName();
+    } else {
+      Result += "sl_";
+      for (auto Elem : STyp->elements())
+        Result += getMangledTypeStr(Elem);
+    }
+    // Ensure nested structs are distinguishable.
+    Result += "s";
+  } else if (FunctionType *FT = dyn_cast<FunctionType>(Ty)) {
     Result += "f_" + getMangledTypeStr(FT->getReturnType());
     for (size_t i = 0; i < FT->getNumParams(); i++)
       Result += getMangledTypeStr(FT->getParamType(i));
Index: test/CodeGen/Generic/overloaded-intrinsic-name.ll
===================================================================
--- test/CodeGen/Generic/overloaded-intrinsic-name.ll
+++ test/CodeGen/Generic/overloaded-intrinsic-name.ll
@@ -44,14 +44,31 @@
 ; struct
 define %struct.test* @test_struct(%struct.test* %v) gc "statepoint-example" {
        %tok = call token (i64, i32, i1 ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_i1f(i64 0, i32 0, i1 ()* @return_i1, i32 0, i32 0, i32 0, i32 0, %struct.test* %v)
-       %v-new = call %struct.test* @llvm.experimental.gc.relocate.p0struct.test(token %tok,  i32 7, i32 7)
+       %v-new = call %struct.test* @llvm.experimental.gc.relocate.p0s_struct.tests(token %tok,  i32 7, i32 7)
        ret %struct.test* %v-new
 }
 
+; literal struct with nested literal struct
+define {i64, i64, {i64} }* @test_literal_struct({i64, i64, {i64}}* %v) gc "statepoint-example" {
+       %tok = call token (i64, i32, i1 ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_i1f(i64 0, i32 0, i1 ()* @return_i1, i32 0, i32 0, i32 0, i32 0, {i64, i64, {i64}} *%v)
+       %v-new = call {i64, i64, {i64}}* @llvm.experimental.gc.relocate.p0sl_i64i64sl_i64ss.test(token %tok,  i32 7, i32 7)
+       ret {i64, i64, {i64}}* %v-new
+}
+; struct with a horrible name, broken when structs were unprefixed
+%i32 = type { i32 }
+
+define %i32* @test_i32_struct(%i32* %v) gc "statepoint-example" {
+entry:
+      %tok = call token (i64, i32, i1 ()*, i32, i32, ...) @llvm.experimental.gc.statepoint.p0f_i1f(i64 0, i32 0, i1 ()* @return_i1, i32 0, i32 0, i32 0, i32 0, %i32* %v)
+      %v-new = call %i32* @llvm.experimental.gc.relocate.p0s_i32s(token %tok,  i32 7, i32 7)
+      ret %i32* %v-new
+}
 declare zeroext i1 @return_i1()
 declare token @llvm.experimental.gc.statepoint.p0f_i1f(i64, i32, i1 ()*, i32, i32, ...)
 declare i32* @llvm.experimental.gc.relocate.p0i32(token, i32, i32)
 declare float* @llvm.experimental.gc.relocate.p0f32(token, i32, i32)
 declare [3 x i32]* @llvm.experimental.gc.relocate.p0a3i32(token, i32, i32)
 declare <3 x i32>* @llvm.experimental.gc.relocate.p0v3i32(token, i32, i32)
-declare %struct.test* @llvm.experimental.gc.relocate.p0struct.test(token, i32, i32)
+declare %struct.test* @llvm.experimental.gc.relocate.p0s_struct.tests(token, i32, i32)
+declare {i64, i64, {i64}}* @llvm.experimental.gc.relocate.p0sl_i64i64sl_i64ss.test(token, i32, i32)
+declare %i32* @llvm.experimental.gc.relocate.p0s_i32s(token, i32, i32)