https://github.com/qiongsiwu created https://github.com/llvm/llvm-project/pull/223759
Source location delta encoding was removed by https://github.com/llvm/llvm-project/pull/145670 due to a difficult bug fix https://github.com/llvm/llvm-project/pull/145529. This PR reimplements the encoding to avoid the bug, and adjusts the order of the fields in the record so that delta encoding achieves more savings relative to the order we had before. >From ed805fc0e438d257c6bbd24a287e074d02db07a6 Mon Sep 17 00:00:00 2001 From: Qiongsi Wu <[email protected]> Date: Tue, 15 Sep 2026 09:28:51 -0700 Subject: [PATCH] [clang][Modules] Reimplement Macro Expansion Record Source Location Delta Encoding Source location delta encoding was removed by https://github.com/llvm/llvm-project/pull/145670 due to a difficult bug fix https://github.com/llvm/llvm-project/pull/145529. This PR reimplements the encoding to avoid the bug, and adjusts the order of the fields in the record so that delta encoding achieves more savings relative to the order we had before. --- .../include/clang/Serialization/ASTBitCodes.h | 2 +- .../Serialization/SourceLocationEncoding.h | 108 +++++++++++++++++ clang/lib/Serialization/ASTReader.cpp | 16 ++- clang/lib/Serialization/ASTWriter.cpp | 30 +++-- .../SourceLocationEncodingTest.cpp | 110 ++++++++++++++++++ 5 files changed, 252 insertions(+), 14 deletions(-) diff --git a/clang/include/clang/Serialization/ASTBitCodes.h b/clang/include/clang/Serialization/ASTBitCodes.h index 6a52a9e4fa780..4640d51d26b30 100644 --- a/clang/include/clang/Serialization/ASTBitCodes.h +++ b/clang/include/clang/Serialization/ASTBitCodes.h @@ -44,7 +44,7 @@ namespace serialization { /// Version 4 of AST files also requires that the version control branch and /// revision match exactly, since there is no backward compatibility of /// AST files at this time. -const unsigned VERSION_MAJOR = 39; +const unsigned VERSION_MAJOR = 40; /// AST file minor version number supported by this version of /// Clang. diff --git a/clang/include/clang/Serialization/SourceLocationEncoding.h b/clang/include/clang/Serialization/SourceLocationEncoding.h index 5b2485dbc719f..0c98839f8fd17 100644 --- a/clang/include/clang/Serialization/SourceLocationEncoding.h +++ b/clang/include/clang/Serialization/SourceLocationEncoding.h @@ -58,6 +58,114 @@ class SourceLocationEncoding { static RawLocEncoding encode(SourceLocation Loc, UIntTy BaseOffset, unsigned BaseModuleFileIndex); static std::pair<SourceLocation, unsigned> decode(RawLocEncoding); + + /// A delta encoder for a run of source locations. + /// The high level strategy of the chain to encode the run is the following. + /// Locations: SL0 SL1 SL2 + /// map to : (SL0 - seed) (SL1 - SL0) (SL2 - SL1) + /// + /// Two wrinkles complicate this strategy's implementation. + /// First, since the delta-encoded values are meant for VBR compression, they + /// are mapped from int to unsigned int with the zigZag method. + /// + /// Second, we are encoding an input value of 0 by 0, instead of using a + /// delta, and we are encoding a delta of zero by 1. This is because both + /// value 0 and a delta of zero show up frequently in source location delta + /// encoding. It would be wasteful to represent an absolute 0 using a delta + /// from a previous value in the run (the delta's absolute value may be big). + /// A consequence is that for a given Prev, zigZag(0 - Prev) should not be + /// used for any input, because 0 is encoded directly. This naturally allows + /// us to represent possible delta values in the following way: + /// + /// delta = V - prev + /// hole = zigZag(0 - prev) + /// encoded = zigZag(delta) + 1 if zigZag(delta) < hole + /// = zigZag(delta) if zigZag(delta) > hole + /// + /// Or pictorially: + /// zigZag(delta): 0, 1, ... hole - 1, hole + 1, hole + 2, ... + /// encoded: 1, 2, ... hole, hole + 1, hole + 2, ... + /// + /// Note it is impossible for zigZag(delta) to be equal to the hole as that + /// would imply V == 0. In other words, if zigZag(delta) < hole, we increment + /// the encoded value by 1 to leave 0 to represent V == 0. If zigZag(delta) + /// is larger than hole, we do not need to add 1. Therefore, we will + /// not accidentally add 1 to values that may overflow beyond 2^32 - 1, + /// which may lead to accidental change of the ModuleIndex bits. + /// This mapping avoids the issue llvm/llvm-project#145529 attempted to fix by + /// design. + class Chain { + UIntTy Prev; + + /// Maps an int to an unsigned int. + /// Explicitly, zigZag does the following mapping: + /// From: 0, -1, +1, -2, +2, ... + /// To: 0, 1, 2, 3, 4, ... + /// In other words, the mapping is the following: + /// zigZag(V) = 2 * V if V >= 0 + /// = 2 * |V| - 1 if V < 0 + static UIntTy zigZag(UIntTy V) { + return (V << 1) ^ (UIntTy(0) - (V >> (UIntBits - 1))); + } + + /// Reverse mapping of zigZag. + static UIntTy zagZig(UIntTy V) { return (V >> 1) ^ (UIntTy(0) - (V & 1)); } + + /// Computes the hole left by 0 - prev. + UIntTy hole() const { return zigZag(UIntTy(0) - Prev); } + + public: + /// Get the seed for a chain from an SM_SLOC_EXPANSION_ENTRY record's first + /// field, Offset. That field holds the entry's adjusted module-local offset + /// with the dummy entry subtracted out, so adding 2 recovers the entry's + /// own position in the source location space. encodeRaw then puts it in the + /// same rotated space as the locations the chain encodes, so the deltas + /// line up. Reader and writer both derive the seed from this one field, so + /// they cannot drift apart. + static UIntTy getSeedFrom(SourceLocation::UIntTy RecordOffset) { + return encodeRaw(RecordOffset + 2); + } + + explicit Chain(UIntTy Seed) : Prev(Seed) { + // Using zero as seed could make the chain very expensive since + // the deltas may be big. + assert(Seed != 0 && "Chain seed should anchor the run"); + } + + RawLocEncoding deltaEncode(RawLocEncoding V) { + // If the source location is external, do not encode. + if (V >> 32) + return V; + + // Use 0 to encode an input of 0. + if (V == 0) + return 0; + + // Delta encode the rest of the possible input values. + UIntTy SL = static_cast<UIntTy>(V); + UIntTy E = zigZag(SL - Prev); + UIntTy H = hole(); + assert(E != H && "Non-zero location cannot be mapped to the hole"); + Prev = SL; + return E < H ? static_cast<RawLocEncoding>(E) + 1 : E; + } + + RawLocEncoding deltaDecode(RawLocEncoding V) { + // If the source location is external, it is not delta encoded. + if (V >> 32) + return V; + + // If V is 0, it is not delta encoded. + if (V == 0) + return 0; + + // Delta-decode the value. + UIntTy H = hole(); + UIntTy D = static_cast<UIntTy>(V); + Prev += zagZig(D <= H ? D - 1 : D); + return Prev; + } + }; }; inline SourceLocationEncoding::RawLocEncoding diff --git a/clang/lib/Serialization/ASTReader.cpp b/clang/lib/Serialization/ASTReader.cpp index a9c230d767c50..09e8c3763a861 100644 --- a/clang/lib/Serialization/ASTReader.cpp +++ b/clang/lib/Serialization/ASTReader.cpp @@ -2064,12 +2064,20 @@ bool ASTReader::ReadSLocEntry(int ID) { } case SM_SLOC_EXPANSION_ENTRY: { - SourceLocation SpellingLoc = ReadSourceLocation(*F, Record[1]); - SourceLocation ExpansionBegin = ReadSourceLocation(*F, Record[2]); - SourceLocation ExpansionEnd = ReadSourceLocation(*F, Record[3]); + SourceLocation::UIntTy EntryOffset = Record[0]; + // The chain is stateful: decode in the same order the writer emitted, each + // in its own statement. See CreateSLocExpansionAbbrev for the field order. + SourceLocationEncoding::Chain Chain( + SourceLocationEncoding::Chain::getSeedFrom(EntryOffset)); + SourceLocation ExpansionEnd = + ReadSourceLocation(*F, Chain.deltaDecode(Record[1])); + SourceLocation ExpansionBegin = + ReadSourceLocation(*F, Chain.deltaDecode(Record[2])); + SourceLocation SpellingLoc = + ReadSourceLocation(*F, Chain.deltaDecode(Record[3])); SourceMgr.createExpansionLoc(SpellingLoc, ExpansionBegin, ExpansionEnd, Record[5], Record[4], ID, - BaseOffset + Record[0]); + BaseOffset + EntryOffset); break; } } diff --git a/clang/lib/Serialization/ASTWriter.cpp b/clang/lib/Serialization/ASTWriter.cpp index 944e68ea6481d..cb74df118ab89 100644 --- a/clang/lib/Serialization/ASTWriter.cpp +++ b/clang/lib/Serialization/ASTWriter.cpp @@ -2063,10 +2063,15 @@ static unsigned CreateSLocExpansionAbbrev(llvm::BitstreamWriter &Stream) { auto Abbrev = std::make_shared<BitCodeAbbrev>(); Abbrev->Add(BitCodeAbbrevOp(SM_SLOC_EXPANSION_ENTRY)); + // The static ordering of the four fields below is critical to getting good + // compression from the delta encoding. Specifically: + // Offset -> End location -> Start location -> Spelling location. + // Ordered this way, the delta between Offset and End location is usually + // small, and so is the delta between End location and Start location. Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // Offset - Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 8)); // Spelling location - Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // Start location Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // End location + Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // Start location + Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // Spelling location Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::Fixed, 1)); // Is token range Abbrev->Add(BitCodeAbbrevOp(BitCodeAbbrevOp::VBR, 6)); // Token length return Stream.EmitAbbrev(std::move(Abbrev)); @@ -2465,13 +2470,20 @@ void ASTWriter::WriteSourceManagerBlock(SourceManager &SourceMgr) { const SrcMgr::ExpansionInfo &Expansion = SLoc->getExpansion(); SLocEntryOffsets.push_back(Offset); // Starting offset of this entry within this module, so skip the dummy. - Record.push_back(getAdjustedOffset(SLoc->getOffset()) - 2); - AddSourceLocation(Expansion.getSpellingLoc(), Record); - AddSourceLocation(Expansion.getExpansionLocStart(), Record); - AddSourceLocation(Expansion.isMacroArgExpansion() - ? SourceLocation() - : Expansion.getExpansionLocEnd(), - Record); + SourceLocation::UIntTy EntryOffset = + getAdjustedOffset(SLoc->getOffset()) - 2; + Record.push_back(EntryOffset); + + SourceLocationEncoding::Chain Chain( + SourceLocationEncoding::Chain::getSeedFrom(EntryOffset)); + auto EmitLoc = [&](SourceLocation Loc) { + Record.push_back(Chain.deltaEncode( + getRawSourceLocationEncoding(getAdjustedLocation(Loc)))); + }; + EmitLoc(Expansion.isMacroArgExpansion() ? SourceLocation() + : Expansion.getExpansionLocEnd()); + EmitLoc(Expansion.getExpansionLocStart()); + EmitLoc(Expansion.getSpellingLoc()); Record.push_back(Expansion.isExpansionTokenRange()); // Compute the token length for this macro expansion. diff --git a/clang/unittests/Serialization/SourceLocationEncodingTest.cpp b/clang/unittests/Serialization/SourceLocationEncodingTest.cpp index 18fedd4de3973..75000aee0bb3b 100644 --- a/clang/unittests/Serialization/SourceLocationEncodingTest.cpp +++ b/clang/unittests/Serialization/SourceLocationEncodingTest.cpp @@ -8,6 +8,8 @@ #include "clang/Serialization/SourceLocationEncoding.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallVector.h" #include "gtest/gtest.h" #include <climits> #include <optional> @@ -36,6 +38,37 @@ void roundTrip(SourceLocation::UIntTy Loc, constexpr SourceLocation::UIntTy MacroBit = 1 << (sizeof(SourceLocation::UIntTy) * CHAR_BIT - 1); constexpr SourceLocation::UIntTy Big = MacroBit >> 1; +constexpr SourceLocation::UIntTy Biggest = ~SourceLocation::UIntTy(0); + +using Chain = SourceLocationEncoding::Chain; + +uint64_t encodeLocal(SourceLocation::UIntTy Loc) { + return SourceLocationEncoding::encode(SourceLocation::getFromRawEncoding(Loc), + /*BaseOffset=*/0, + /*BaseModuleFileIndex=*/0); +} + +// Round-trip a run of locations through a chain, the way ASTWriter and +// ASTReader use it for SM_SLOC_EXPANSION_ENTRY. +void roundTripChain(SourceLocation::UIntTy RecordOffset, + ArrayRef<SourceLocation::UIntTy> Locs) { + SmallVector<uint64_t> Encoded; + Chain Enc(Chain::getSeedFrom(RecordOffset)); + for (SourceLocation::UIntTy Loc : Locs) { + uint64_t E = Enc.deltaEncode(encodeLocal(Loc)); + // Nothing may spill into the module file index. + ASSERT_EQ(E >> 32, 0u) << "Encoding " << Loc; + Encoded.push_back(E); + } + + Chain Dec(Chain::getSeedFrom(RecordOffset)); + for (auto [E, Loc] : llvm::zip(Encoded, Locs)) { + auto [Decoded, ModuleFileIndex] = + SourceLocationEncoding::decode(Dec.deltaDecode(E)); + ASSERT_EQ(ModuleFileIndex, 0u) << "Decoding " << E; + ASSERT_EQ(Decoded.getRawEncoding(), Loc) << "Decoding " << E; + } +} TEST(SourceLocationEncoding, Individual) { roundTrip(1, 2); @@ -48,4 +81,81 @@ TEST(SourceLocationEncoding, Individual) { roundTrip(MacroBit | (Big + 1)); } +TEST(SourceLocationEncoding, Chained) { + // The chain must work wherever in the module the record happens to sit. + for (SourceLocation::UIntTy Off : {0u, 1u, 100u, 1u << 20, 1u << 30}) { + roundTripChain(Off, {1, 2, 3}); + roundTripChain(Off, {0, 0, 0}); // all null + roundTripChain(Off, {MacroBit | 5, 0, 17}); // null in the middle + roundTripChain(Off, {7, 7, 7}); // repeats + roundTripChain(Off, {Big, Big + 1, MacroBit | Big}); + roundTripChain(Off, {Biggest, 1, Biggest}); // large jumps + roundTripChain(Off, {MacroBit, MacroBit | 1, 1}); + } +} + +TEST(SourceLocationEncoding, NoSpillIntoModuleFileIndex) { + // No encoded value should spill to the upper 32 bit of the encoding. + // See llvm/llvm-project#145529. + roundTripChain(0, {1, (1u << 30) + 1}); + roundTripChain(0, {1, 9, Biggest, Big, Big + 1, 0, MacroBit | Big, 0}); + + // Sweep the extremes: whatever the seed, an encoded value stays in 32 bits. + for (SourceLocation::UIntTy Off : {0u, 1u, 1u << 30, (1u << 31) - 3}) { + for (SourceLocation::UIntTy Loc : {1u, 2u, MacroBit, MacroBit | 1u, Big, + Big + 1, Biggest, Biggest - 1}) { + Chain Enc(Chain::getSeedFrom(Off)); + uint64_t Raw = encodeLocal(Loc); + uint64_t E = Enc.deltaEncode(Raw); + ASSERT_LE(E, 0xFFFFFFFFull); + Chain Dec(Chain::getSeedFrom(Off)); + ASSERT_EQ(Dec.deltaDecode(E), Raw); + } + } +} + +// deltaEncode() and deltaDecode() split on either side of the hole, so an +// off-by-one there is a single-character mistake that silently turns a valid +// location into a null one. Pin both codes adjacent to the hole. The location +// whose raw value equals the seed lands just above it; MacroBit | (seed - 1) +// lands just below. +TEST(SourceLocationEncoding, HoleBoundary) { + for (SourceLocation::UIntTy Off : {0u, 1u, 100u, 4096u, 1u << 20}) { + SourceLocation::UIntTy Seed = Chain::getSeedFrom(Off); + roundTripChain(Off, {Seed}); // code == hole + 1 + roundTripChain(Off, {MacroBit | (Seed - 1)}); // code == hole + roundTripChain(Off, {MacroBit | (Seed - 1), Seed}); + } +} + +// Locations owned by an imported module file keep their module file index and +// are stored verbatim, and they must not disturb the chain around them. +TEST(SourceLocationEncoding, ImportedLocationsBypassChain) { + uint64_t Imported = SourceLocationEncoding::encode( + SourceLocation::getFromRawEncoding(4242), /*BaseOffset=*/100, + /*BaseModuleFileIndex=*/3); + ASSERT_NE(Imported >> 32, 0u); + + Chain WithImport(Chain::getSeedFrom(64)); + uint64_t A1 = WithImport.deltaEncode(encodeLocal(70)); + uint64_t I = WithImport.deltaEncode(Imported); + uint64_t B1 = WithImport.deltaEncode(encodeLocal(90)); + + EXPECT_EQ(I, Imported) << "Imported location must pass through unchanged"; + + // Dropping the imported location leaves the other two encodings untouched. + Chain WithoutImport(Chain::getSeedFrom(64)); + EXPECT_EQ(WithoutImport.deltaEncode(encodeLocal(70)), A1); + EXPECT_EQ(WithoutImport.deltaEncode(encodeLocal(90)), B1); + + Chain Dec(Chain::getSeedFrom(64)); + EXPECT_EQ(SourceLocationEncoding::decode(Dec.deltaDecode(A1)) + .first.getRawEncoding(), + 70u); + EXPECT_EQ(Dec.deltaDecode(I), Imported); + EXPECT_EQ(SourceLocationEncoding::decode(Dec.deltaDecode(B1)) + .first.getRawEncoding(), + 90u); +} + } // namespace _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
