[Serialization] Stable serialization order for OpenCLTypeExtMap and OpenCLDeclExtMap

[riccibruno]

Summary

Sort the elements of Sema::OpenCLTypeExtMap and Sema::OpenCLDeclExtMap by TypeIDs and DeclIDs to guarantee a stable serialization order.

[riccibruno]

By the way, I am wondering about how much this is tested. I did look quickly in test/PCH and it appears that there are only 3 (short) tests : ocl_types.cl, opencl-extensions.cl and no-validate-pch.

[Anastasia]

In D60835#1470805, @riccibruno wrote:

By the way, I am wondering about how much this is tested. I did look quickly in test/PCH and it appears that there are only 3 (short) tests : ocl_types.cl, opencl-extensions.cl and no-validate-pch.

This is tested in test/SemaOpenCL/extension-begin.cl: https://reviews.llvm.org/D53200

The ordering in PCH isn't tested anywhere however, but I am not clear how to check for nondeterminism properly. Because the fact that the same output is generated N times won't guarantee that it's the same N+1 times. Especially I do believe it's likely on the same revision the same output to be produced but it's less likely across revisions. :(

We could still go for something like the following but accept that some a random failure might happen not necessarily on a commit that introduces it?

In D60778#1468825, @lebedev.ri wrote:

Not sure how to test this though? I guess we can trust that std::map is always sorted just as it says in its description.

You could add a test that contains several entries in OpenCLTypeExtMap and several entries in OpenCLDeclExtMap.
In that test, write te PCH, and then apply llvm-bcanalyzer to that PCH. It should dump it the bitcode in textual dump.
And then simply apply FileCheck to that textual dump, with CHECK lines requiring the specific order of these entries.
If the order is not deterministic in PCH, then that test would (should!) fail sporadically.
At least that is my guess.

[riccibruno]

In D60835#1471498, @Anastasia wrote:

In D60835#1470805, @riccibruno wrote:

By the way, I am wondering about how much this is tested. I did look quickly in test/PCH and it appears that there are only 3 (short) tests : ocl_types.cl, opencl-extensions.cl and no-validate-pch.

This is tested in test/SemaOpenCL/extension-begin.cl: https://reviews.llvm.org/D53200

Ah I see, I did indeed miss that.

The ordering in PCH isn't tested anywhere however, but I am not clear how to check for nondeterminism properly. Because the fact that the same output is generated N times won't guarantee that it's the same N+1 times. Especially I do believe it's likely on the same revision the same output to be produced but it's less likely across revisions. :(

We could still go for something like the following but accept that some a random failure might happen not necessarily on a commit that introduces it?

I am not sure that this is needed. Non-deterministic tests are really annoying.

In D60778#1468825, @lebedev.ri wrote:

Not sure how to test this though? I guess we can trust that std::map is always sorted just as it says in its description.

You could add a test that contains several entries in OpenCLTypeExtMap and several entries in OpenCLDeclExtMap.
In that test, write te PCH, and then apply llvm-bcanalyzer to that PCH. It should dump it the bitcode in textual dump.
And then simply apply FileCheck to that textual dump, with CHECK lines requiring the specific order of these entries.
If the order is not deterministic in PCH, then that test would (should!) fail sporadically.
At least that is my guess.

[Anastasia]

We could still go for something like the following but accept that some a random failure might happen not necessarily on a commit that introduces it?

I am not sure that this is needed. Non-deterministic tests are really annoying.

Yes. I think this might be a wider topic to address if we happen to have more issues of this kind.

cfe/trunk/lib/Serialization/ASTWriter.cpp

void ASTWriter::WriteOpenCLExtensions(Sema &SemaRef) {
   }
   Stream.EmitRecord(OPENCL_EXTENSIONS, Record);
 }
 
 void ASTWriter::WriteOpenCLExtensionTypes(Sema &SemaRef) {
   if (!SemaRef.Context.getLangOpts().OpenCL)
     return;
 
+  // Sort the elements of the map OpenCLTypeExtMap by TypeIDs,
+  // without copying them.
+  const llvm::DenseMap<const Type *, std::set<std::string>> &OpenCLTypeExtMap =
+      SemaRef.OpenCLTypeExtMap;
+  using ElementTy = std::pair<TypeID, const std::set<std::string> *>;
+  llvm::SmallVector<ElementTy, 8> StableOpenCLTypeExtMap;
+  StableOpenCLTypeExtMap.reserve(OpenCLTypeExtMap.size());
+
+  for (const auto &I : OpenCLTypeExtMap)
+    StableOpenCLTypeExtMap.emplace_back(
+        getTypeID(I.first->getCanonicalTypeInternal()), &I.second);
+
+  auto CompareByTypeID = [](const ElementTy &E1, const ElementTy &E2) -> bool {
+    return E1.first < E2.first;
+  };
+  llvm::sort(StableOpenCLTypeExtMap, CompareByTypeID);
+
   RecordData Record;
-  for (const auto &I : SemaRef.OpenCLTypeExtMap) {
-    Record.push_back(
-        static_cast<unsigned>(getTypeID(I.first->getCanonicalTypeInternal())));
-    Record.push_back(I.second.size());
-    for (auto Ext : I.second)
+  for (const ElementTy &E : StableOpenCLTypeExtMap) {
+    Record.push_back(E.first); // TypeID
+    const std::set<std::string> *ExtSet = E.second;
+    Record.push_back(static_cast<unsigned>(ExtSet->size()));
+    for (const std::string &Ext : *ExtSet)
       AddString(Ext, Record);
   }
+
   Stream.EmitRecord(OPENCL_EXTENSION_TYPES, Record);
 }
 
 void ASTWriter::WriteOpenCLExtensionDecls(Sema &SemaRef) {
   if (!SemaRef.Context.getLangOpts().OpenCL)
     return;
 
+  // Sort the elements of the map OpenCLDeclExtMap by DeclIDs,
+  // without copying them.
+  const llvm::DenseMap<const Decl *, std::set<std::string>> &OpenCLDeclExtMap =
+      SemaRef.OpenCLDeclExtMap;
+  using ElementTy = std::pair<DeclID, const std::set<std::string> *>;
+  llvm::SmallVector<ElementTy, 8> StableOpenCLDeclExtMap;
+  StableOpenCLDeclExtMap.reserve(OpenCLDeclExtMap.size());
+
+  for (const auto &I : OpenCLDeclExtMap)
+    StableOpenCLDeclExtMap.emplace_back(getDeclID(I.first), &I.second);
+
+  auto CompareByDeclID = [](const ElementTy &E1, const ElementTy &E2) -> bool {
+    return E1.first < E2.first;
+  };
+  llvm::sort(StableOpenCLDeclExtMap, CompareByDeclID);
+
   RecordData Record;
-  for (const auto &I : SemaRef.OpenCLDeclExtMap) {
-    Record.push_back(getDeclID(I.first));
-    Record.push_back(static_cast<unsigned>(I.second.size()));
-    for (auto Ext : I.second)
+  for (const ElementTy &E : StableOpenCLDeclExtMap) {
+    Record.push_back(E.first); // DeclID
+    const std::set<std::string> *ExtSet = E.second;
+    Record.push_back(static_cast<unsigned>(ExtSet->size()));
+    for (const std::string &Ext : *ExtSet)
       AddString(Ext, Record);
   }
+
   Stream.EmitRecord(OPENCL_EXTENSION_DECLS, Record);
 }
 
 void ASTWriter::WriteCUDAPragmas(Sema &SemaRef) {
   if (SemaRef.ForceCUDAHostDeviceDepth > 0) {
     RecordData::value_type Record[] = {SemaRef.ForceCUDAHostDeviceDepth};
     Stream.EmitRecord(CUDA_PRAGMA_FORCE_HOST_DEVICE_DEPTH, Record);
   }