[Modules] Remove non-determinism while serializing DECL_CONTEXT_LEXICAL and DECL_RECORD

[bruno]

Summary

A module signature hashes out all relevant content in a module in order
to guarantee that in a dep chain, an inconsistent module never gets
imported. When using implicit modules, clang is capable of rebuilding a
module in case its signature doesn't match what's expected in the
importer. However, when using PCHs + implicit modules, clang cannot
rebuild a imported module with a signature mismatch, since it doesn't
know how to rebuild PCHs.

Non-determinism in the module content, can lead to changes to the
signature of a PCM across compiler invocations that are expected to
produce the same result, causing:

• Build time penalties: rebuilding modules can be expensive.
• Failures: when using PCHs, leads to hard errors one cannot recover

from.

This patch address non-determinism when serializing DECL_CONTEXT_LEXICAL
and DECL_RECORD by sorting the decls by ID (which is supposed to be
deterministic across multiple invocations) prior to writing out the
records. Another approach would be to fix all the places that trigger
adding a Decl to a DeclContext in non deterministic order, but I
couldn't spot any after an audit, but probably didn't look at everything
since the number of different sites and nested calls that do that is
pretty high. Also, by fixing it right before serialization, we enforce
that future changes also don't mess up with the order.

This isn't new, I consistently tracked this behavior in clang all the
way back to 2016, where my testcase stops working for other reasons.

I have no sensible and reduced testcases to add to this patch.

rdar://problem/43442957

[bruno]

Although we can't synthesize a testcase for inclusion in the patch. Here is how one should attempt to reproduce the problem in macOS 10.14.

echo '@import Foundation;' > test.m
clang -fmodules test.m -o test.o -c \
      -fmodules-cache-path=/tmp/cache \
      -isysroot /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.14.sdk
mv /tmp/cache /tmp/cache1

clang -fmodules test.m -o test.o -c \
      -fmodules-cache-path=/tmp/cache \
      -isysroot /Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform/Developer/SDKs/MacOSX10.14.sdk
mv /tmp/cache /tmp/cache2

HASH=`ls /tmp/cache1`
for i in `find /tmp/cache1 -type f -iname "*.pcm"`; do
  F=`basename $i`;
  diff /tmp/cache1/$HASH/$F /tmp/cache2/$HASH/$F;
done

[bruno]

@rsmith this is on the non-determinism issue we discussed offline. Do you have any concerns with this approach?

[bruno]

Ping!

[bruno]

Ping

[bruno]

Abandon this one in favor of https://reviews.llvm.org/D55676

lib/Serialization/ASTCommon.h

 /// declaration number.
 bool needsAnonymousDeclarationNumber(const NamedDecl *D);
 
 /// Visit each declaration within \c DC that needs an anonymous
 /// declaration number and call \p Visit with the declaration and its number.
 template<typename Fn> void numberAnonymousDeclsWithin(const DeclContext *DC,
                                                       Fn Visit) {
   unsigned Index = 0;
+  SmallVector<NamedDecl *, 2> DeclsToVisit;
   for (Decl *LexicalD : DC->decls()) {
     // For a friend decl, we care about the declaration within it, if any.
     if (auto *FD = dyn_cast<FriendDecl>(LexicalD))
       LexicalD = FD->getFriendDecl();
 
     auto *ND = dyn_cast_or_null<NamedDecl>(LexicalD);
     if (!ND || !needsAnonymousDeclarationNumber(ND))
       continue;
 
-    Visit(ND, Index++);
+    DeclsToVisit.push_back(ND);
   }
+
+  // Decls have deterministic IDs, but they might show up in different order in
+  // a DeclContext. Make sure serialization gets the same order everytime by
+  // sorting the decls by ID.
+  llvm::sort(DeclsToVisit, [](const NamedDecl *L, const NamedDecl *R) {
+    return L->getID() < R->getID();
+  });
+  for (auto *ND : DeclsToVisit)
+    Visit(ND, Index++);
 }
 
 } // namespace serialization
 
 } // namespace clang
 
 #endif

lib/Serialization/ASTWriter.cpp

 /// bitstream, or 0 if no block was written.
 uint64_t ASTWriter::WriteDeclContextLexicalBlock(ASTContext &Context,
                                                  DeclContext *DC) {
   if (DC->decls_empty())
     return 0;
 
   uint64_t Offset = Stream.GetCurrentBitNo();
   SmallVector<uint32_t, 128> KindDeclPairs;
-  for (const auto *D : DC->decls()) {
+
+  // Decls have deterministic IDs, but they might show up in different order in
+  // a DeclContext. Make sure serialization gets the same order everytime by
+  // sorting the decls by ID.
+  SmallVector<Decl *, 64> SortedDecls(DC->decls());
+  llvm::sort(SortedDecls, [](const Decl *L, const Decl *R) {
+    return L->getID() < R->getID();
+  });
+
+  for (const auto *D : SortedDecls) {
     KindDeclPairs.push_back(D->getKind());
     KindDeclPairs.push_back(GetDeclRef(D));
   }
 
   ++NumLexicalDeclContexts;
   RecordData::value_type Record[] = {DECL_CONTEXT_LEXICAL};
   Stream.EmitRecordWithBlob(DeclContextLexicalAbbrev, Record,
                             bytes(KindDeclPairs));