[modules] Support zstd in .pcm file

[MaskRay]

Summary

Extend SM_SLOC_BUFFER_BLOB_COMPRESSED to allow zstd, which is much faster
(compression/decompression) than zlib with a similar compression ratio.

An alternative is to add a value beside SM_SLOC_BUFFER_BLOB_COMPRESSED, but
reusing SM_SLOC_BUFFER_BLOB_COMPRESSED slightly simplifies the implementation
and leads to better diagnostics when a slightly older Clang consumes zstd
compressed blob.

Compressing AST takes a small portion of WriteAST, so we can pick a higher
compression level.

Compiling a relatively large .pcm (absl endian) with -fmodules-embed-all-files,
zstd level 9 has comparable performance with zlib-chromium level 6 (default),
but provides smaller output (5809156 => 5796016). Higher zstd levels will make
"Compress AST" notably slower and do not provide significant more size saving.

2.219345 Total ExecuteCompiler
0.746799 Total Frontend
0.736862 Total Source
0.339434 Total ReadAST
0.165452 Total WriteAST
0.043045 Total Compress AST
0.008236 Total ParseClass
0.00633 Total InstantiateClass
0.001887 Total isPotentialConstantExpr
0.001808 Total InstantiateFunction
0.001535 Total EvaluateForOverflow
0.000986 Total EvaluateAsRValue
0.000536 Total EvaluateAsBooleanCondition
0.000308 Total EvaluateAsConstantExpr
0.000156 Total EvaluateAsInt
3.4e-05 Total EvaluateKnownConstInt
8e-06 Total EvaluateAsInitializer
0 Total PerformPendingInstantiations

[MaskRay]

use level 9

[dblaikie]

clang/lib/Serialization/ASTReader.cpp

1456

Worth a comment about this magic number?

[MaskRay]

add a comment about the zlib header

[tschuett]

Release note?

clang/lib/Serialization/ASTReader.cpp

1457

Could you put the magic number into a named constant?

[dblaikie]

clang/lib/Serialization/ASTReader.cpp

1457

& perhaps we should have/test a magic number for zstd too, so it's clear it's one or the other and not something else added in the future (since this isn't reving the bitcode version or anything - reading zstd compressed data with the library before this version will I guess/hopefully appear corrupted, but we could avoid that being the failure mode in the future when another compression scheme is added by checking explicitly for zstd/zlib now and reporting unknown compression scheme otherwise?)?

[MaskRay]

clang/lib/Serialization/ASTReader.cpp

1457

Could you put the magic number into a named constant?

I think a constant doesn't improve readability of this used-once value with a comment.

& perhaps we should have/test a magic number for zstd too, so it's clear it's one or the other and not something else added in the future

Since the version number keeps increasing, when a new algorithm is added, they will see a version mismatch error...

[dblaikie]

clang/lib/Serialization/ASTReader.cpp

1457

& perhaps we should have/test a magic number for zstd too, so it's clear it's one or the other and not something else added in the future

Since the version number keeps increasing, when a new algorithm is added, they will see a version mismatch error...

Oh, right, sorry, got muddled - thinking bitcode & then thinking LLVM IR bitcode guarantees, super stable, but the AST's super unstable/closely version locked anyway.

[MaskRay]

Ping:)

[dblaikie]

Sounds good

[dyung]

@MaskRay your change seems to be causing 1509 failures on the linux PS4 bot. Most of the errors look similar to this:

error: 'error' diagnostics seen but not expected: 
  (frontend): malformed or corrupted AST file: 'LLVM was not built with LLVM_ENABLE_ZSTD or did not find zstd at build time'
1 error generated.

Can you take a look?

[dyung]

In D137885#3947532, @dyung wrote:

@MaskRay your change seems to be causing 1509 failures on the linux PS4 bot. Most of the errors look similar to this:

error: 'error' diagnostics seen but not expected: 
  (frontend): malformed or corrupted AST file: 'LLVM was not built with LLVM_ENABLE_ZSTD or did not find zstd at build time'
1 error generated.

Can you take a look?

Sorry, forgot to include a link to the failing buildbot: https://lab.llvm.org/buildbot/#/builders/139/builds/31513

[MaskRay]

In D137885#3947532, @dyung wrote:

@MaskRay your change seems to be causing 1509 failures on the linux PS4 bot. Most of the errors look similar to this:

error: 'error' diagnostics seen but not expected: 
  (frontend): malformed or corrupted AST file: 'LLVM was not built with LLVM_ENABLE_ZSTD or did not find zstd at build time'
1 error generated.

Can you take a look?

Back from lunch. Sorry for the breakage. I picked the wrong zlib header... Fixed now.

clang/lib/Serialization/ASTReader.cpp

Expected<unsigned> MaybeRecCode =
         SLocEntryCursor.readRecord(Code, Record, &Blob);
     if (!MaybeRecCode) {
       Error(MaybeRecCode.takeError());
       return nullptr;
     }
     unsigned RecCode = MaybeRecCode.get();
 
     if (RecCode == SM_SLOC_BUFFER_BLOB_COMPRESSED) {
-      if (!llvm::compression::zlib::isAvailable()) {
-        Error("zlib is not available");
+      // Inspect the first two bytes to differentiate zlib (\x1f\x8b) and zstd.
+      const llvm::compression::Format F =
+          Blob.size() >= 2 && memcmp(Blob.data(), "\x1f\x8b", 2) == 0
+              ? llvm::compression::Format::Zlib
+              : llvm::compression::Format::Zstd;
+      if (const char *Reason = llvm::compression::getReasonIfUnsupported(F)) {
+        Error(Reason);
         return nullptr;
       }
-      SmallVector<uint8_t, 0> Uncompressed;
-      if (llvm::Error E = llvm::compression::zlib::decompress(
-              llvm::arrayRefFromStringRef(Blob), Uncompressed, Record[0])) {
+      SmallVector<uint8_t, 0> Decompressed;
+      if (llvm::Error E = llvm::compression::decompress(
+              F, llvm::arrayRefFromStringRef(Blob), Decompressed, Record[0])) {
         Error("could not decompress embedded file contents: " +
               llvm::toString(std::move(E)));
         return nullptr;
       }
       return llvm::MemoryBuffer::getMemBufferCopy(
-          llvm::toStringRef(Uncompressed), Name);
+          llvm::toStringRef(Decompressed), Name);
     } else if (RecCode == SM_SLOC_BUFFER_BLOB) {
       return llvm::MemoryBuffer::getMemBuffer(Blob.drop_back(1), Name, true);
     } else {
       Error("AST record has invalid code");
       return nullptr;
     }
   };
 

clang/lib/Serialization/ASTWriter.cpp

 static void emitBlob(llvm::BitstreamWriter &Stream, StringRef Blob,
                      unsigned SLocBufferBlobCompressedAbbrv,
                      unsigned SLocBufferBlobAbbrv) {
   using RecordDataType = ASTWriter::RecordData::value_type;
 
   // Compress the buffer if possible. We expect that almost all PCM
   // consumers will not want its contents.
   SmallVector<uint8_t, 0> CompressedBuffer;
+  if (llvm::compression::zstd::isAvailable()) {
+    llvm::compression::zstd::compress(
+        llvm::arrayRefFromStringRef(Blob.drop_back(1)), CompressedBuffer, 9);
+    RecordDataType Record[] = {SM_SLOC_BUFFER_BLOB_COMPRESSED, Blob.size() - 1};
+    Stream.EmitRecordWithBlob(SLocBufferBlobCompressedAbbrv, Record,
+                              llvm::toStringRef(CompressedBuffer));
+    return;
+  }
   if (llvm::compression::zlib::isAvailable()) {
     llvm::compression::zlib::compress(
         llvm::arrayRefFromStringRef(Blob.drop_back(1)), CompressedBuffer);
     RecordDataType Record[] = {SM_SLOC_BUFFER_BLOB_COMPRESSED, Blob.size() - 1};
     Stream.EmitRecordWithBlob(SLocBufferBlobCompressedAbbrv, Record,
                               llvm::toStringRef(CompressedBuffer));
     return;
   }

clang/test/Modules/embed-files-compressed.cpp

-// REQUIRES: zlib
+// REQUIRES: zlib || zstd
 // REQUIRES: shell
 //
 // RUN: rm -rf %t
 // RUN: mkdir %t
 // RUN: echo '//////////////////////////////////////////////////////////////////////' > %t/a.h
 // RUN: cat %t/a.h %t/a.h %t/a.h %t/a.h > %t/b.h
 // RUN: cat %t/b.h %t/b.h %t/b.h %t/b.h > %t/a.h
 // RUN: cat %t/a.h %t/a.h %t/a.h %t/a.h > %t/b.h