https://github.com/fmeum created https://github.com/llvm/llvm-project/pull/233136
For every used function, `gatherSkippedRegions` copied the list of all comments, empty lines and skipped preprocessor blocks seen so far in the translation unit, computed the adjusted line range of each one in the files of the function and then discarded those outside of the function. This makes coverage mapping generation quadratic in the size of a translation unit. Instead, index the skipped ranges by file and begin location on demand and only adjust the ones that begin between the line before and the last line of the regions of the function in each of its files. Adjusting a skipped range moves its start by at most one line and never past its end, so these are a superset of the ranges that pass the existing filter. The index stores positions in `SkippedRanges` since the last range may still be extended or get its `NextTokLoc` after it has been indexed. The generated mappings are unchanged, except that comments in `_Pragma` strings, which are lexed in macro expansions, no longer trigger the "region spans multiple files" assertion. CPU time of `clang -O0 -fprofile-instr-generate -fcoverage-mapping -emit-llvm -S` (Release build with assertions, best of 3 runs): | File | Before | After | |---|---:|---:| | `clang/lib/Sema/SemaExpr.cpp` | 24.3 s | 8.1 s | | `llvm/lib/CodeGen/SelectionDAG/DAGCombiner.cpp` | 6.0 s | 3.8 s | | `llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp` | 3.7 s | 2.3 s | | `llvm/lib/IR/Instructions.cpp` | 2.4 s | 1.8 s | The `-dump-coverage-mapping` output for these and six other LLVM source files (about 35k skipped regions in total) is byte-identical before and after this change. This also prepares #232831, which emits skipped regions in the mappings of unused functions and can use the same lookup. https://claude.ai/code/session_01SMjpGgdj23E2Nz1dKmfcyp >From 3c1acfdc1db7f2110d66bc935838dbc0ed072622 Mon Sep 17 00:00:00 2001 From: Fabian Meumertzheim <[email protected]> Date: Sat, 17 Oct 2026 22:56:52 +0200 Subject: [PATCH] [Coverage] Only look at skipped ranges near the regions of a function For every used function, gatherSkippedRegions copied the list of all comments, empty lines and skipped preprocessor blocks seen so far in the translation unit, computed the adjusted line range of each one in the files of the function and then discarded those outside of the function. This makes coverage mapping generation quadratic in the size of a translation unit. Instead, index the skipped ranges by file and begin location on demand and only adjust the ones that begin between the line before and the last line of the regions of the function in each of its files. Adjusting a skipped range moves its start by at most one line and never past its end, so these are a superset of the ranges that pass the existing filter. The index stores positions in SkippedRanges since the last range may still be extended or get its NextTokLoc after it has been indexed. The generated mappings are unchanged, except that comments in _Pragma strings, which are lexed in macro expansions, no longer trigger the "region spans multiple files" assertion. Claude-Session: https://claude.ai/code/session_01SMjpGgdj23E2Nz1dKmfcyp --- clang/lib/CodeGen/CoverageMappingGen.cpp | 101 ++++++++++++++------ clang/lib/CodeGen/CoverageMappingGen.h | 17 +++- clang/test/CoverageMapping/pragma-comment.c | 11 +++ 3 files changed, 96 insertions(+), 33 deletions(-) create mode 100644 clang/test/CoverageMapping/pragma-comment.c diff --git a/clang/lib/CodeGen/CoverageMappingGen.cpp b/clang/lib/CodeGen/CoverageMappingGen.cpp index 970812f7b0f754..43d8858eef0338 100644 --- a/clang/lib/CodeGen/CoverageMappingGen.cpp +++ b/clang/lib/CodeGen/CoverageMappingGen.cpp @@ -103,6 +103,38 @@ void CoverageSourceInfo::updateNextTokLoc(SourceLocation Loc) { SkippedRanges.back().NextTokLoc = Loc; } +SmallVector<SkippedRange, 0> +CoverageSourceInfo::getSkippedRangesIn(SourceRange Range) { + // Index the skipped ranges added since the last call. As they are mostly + // added in source order, they usually end up at the end of their file's list. + for (unsigned I = NumIndexedSkippedRanges; I < SkippedRanges.size(); ++I) { + SourceLocation Begin = SkippedRanges[I].Range.getBegin(); + auto &Indices = SkippedRangesByFile[SourceMgr.getFileID(Begin)]; + Indices.insert(llvm::upper_bound(Indices, Begin, + [&](SourceLocation Loc, unsigned J) { + return Loc < + SkippedRanges[J].Range.getBegin(); + }), + I); + } + NumIndexedSkippedRanges = SkippedRanges.size(); + + SmallVector<SkippedRange, 0> Result; + auto It = SkippedRangesByFile.find(SourceMgr.getFileID(Range.getBegin())); + if (It == SkippedRangesByFile.end()) + return Result; + ArrayRef<unsigned> Indices = It->second; + const unsigned *First = llvm::partition_point(Indices, [&](unsigned I) { + return SkippedRanges[I].Range.getBegin() < Range.getBegin(); + }); + for (unsigned I : llvm::make_range(First, Indices.end())) { + if (Range.getEnd() < SkippedRanges[I].Range.getBegin()) + break; + Result.push_back(SkippedRanges[I]); + } + return Result; +} + namespace { /// A region of source code that can be mapped to a counter. class SourceMappingRegion { @@ -463,8 +495,8 @@ class CoverageMappingBuilder { return std::nullopt; } - /// Gather all the regions that were skipped by the preprocessor - /// using the constructs like #if or comments. + /// Gather the regions within the source code of this function that were + /// skipped by the preprocessor using the constructs like #if or comments. void gatherSkippedRegions() { /// An array of the minimum lineStarts and the maximum lineEnds /// for mapping regions from the appropriate source files. @@ -479,34 +511,45 @@ class CoverageMappingBuilder { std::max(FileLineRanges[R.FileID].second, R.LineEnd); } - auto SkippedRanges = CVM.getSourceInfo().getSkippedRanges(); - for (auto &I : SkippedRanges) { - SourceRange Range = I.Range; - auto LocStart = Range.getBegin(); - auto LocEnd = Range.getEnd(); - assert(SM.isWrittenInSameFile(LocStart, LocEnd) && - "region spans multiple files"); - - auto CovFileID = getCoverageFileID(LocStart); - if (!CovFileID) - continue; - std::optional<SpellingRegion> SR; - if (I.isComment()) - SR = adjustSkippedRange(SM, LocStart, LocEnd, I.PrevTokLoc, - I.NextTokLoc); - else if (I.isPPIfElse() || I.isEmptyLine()) - SR = {SM, LocStart, LocEnd}; - - if (!SR) + for (const auto &[File, Mapping] : FileIDMapping) { + unsigned CovFileID = Mapping.first; + auto [FirstLine, LastLine] = FileLineRanges[CovFileID]; + // Skipped ranges in macro expansions, e.g. for comments in _Pragma + // strings, don't correspond to lines in a file. + if (!SM.getSLocEntry(File).isFile() || FirstLine > LastLine) continue; - auto Region = CounterMappingRegion::makeSkipped( - *CovFileID, SR->LineStart, SR->ColumnStart, SR->LineEnd, - SR->ColumnEnd); - // Make sure that we only collect the regions that are inside - // the source code of this function. - if (Region.LineStart >= FileLineRanges[*CovFileID].first && - Region.LineEnd <= FileLineRanges[*CovFileID].second) - MappingRegions.push_back(Region); + // Adjusting a skipped range moves its start by at most one line and + // never past its end, so only the ranges that begin between the line + // before and the last line of the regions of this function can end up + // within them. + SourceLocation Begin = + SM.translateLineCol(File, std::max(FirstLine, 2u) - 1, 1); + SourceLocation End = SM.translateLineCol(File, LastLine + 1, 1); + for (const SkippedRange &I : + CVM.getSourceInfo().getSkippedRangesIn({Begin, End})) { + SourceRange Range = I.Range; + auto LocStart = Range.getBegin(); + auto LocEnd = Range.getEnd(); + assert(SM.isWrittenInSameFile(LocStart, LocEnd) && + "region spans multiple files"); + + std::optional<SpellingRegion> SR; + if (I.isComment()) + SR = adjustSkippedRange(SM, LocStart, LocEnd, I.PrevTokLoc, + I.NextTokLoc); + else if (I.isPPIfElse() || I.isEmptyLine()) + SR = {SM, LocStart, LocEnd}; + + if (!SR) + continue; + auto Region = CounterMappingRegion::makeSkipped( + CovFileID, SR->LineStart, SR->ColumnStart, SR->LineEnd, + SR->ColumnEnd); + // Make sure that we only collect the regions that are inside + // the source code of this function. + if (Region.LineStart >= FirstLine && Region.LineEnd <= LastLine) + MappingRegions.push_back(Region); + } } } diff --git a/clang/lib/CodeGen/CoverageMappingGen.h b/clang/lib/CodeGen/CoverageMappingGen.h index 0ed50597e1dc3e..dbddec81f1ab8a 100644 --- a/clang/lib/CodeGen/CoverageMappingGen.h +++ b/clang/lib/CodeGen/CoverageMappingGen.h @@ -50,9 +50,9 @@ struct SkippedRange { // The nature of this skipped range Kind RangeKind; - bool isComment() { return RangeKind == Comment; } - bool isEmptyLine() { return RangeKind == EmptyLine; } - bool isPPIfElse() { return RangeKind == PPIfElse; } + bool isComment() const { return RangeKind == Comment; } + bool isEmptyLine() const { return RangeKind == EmptyLine; } + bool isPPIfElse() const { return RangeKind == PPIfElse; } SkippedRange(SourceRange Range, Kind K, SourceLocation PrevTokLoc = SourceLocation(), @@ -70,6 +70,13 @@ class CoverageSourceInfo : public PPCallbacks, // A vector of skipped source ranges and PrevTokLoc with NextTokLoc. std::vector<SkippedRange> SkippedRanges; + // Indices into SkippedRanges grouped by file and sorted by begin location. + // This is updated on demand by getSkippedRangesIn. + llvm::DenseMap<FileID, SmallVector<unsigned, 0>> SkippedRangesByFile; + + // The number of SkippedRanges that have been added to SkippedRangesByFile. + unsigned NumIndexedSkippedRanges = 0; + SourceManager &SourceMgr; public: @@ -79,7 +86,9 @@ class CoverageSourceInfo : public PPCallbacks, CoverageSourceInfo(SourceManager &SourceMgr) : SourceMgr(SourceMgr) {} - std::vector<SkippedRange> &getSkippedRanges() { return SkippedRanges; } + /// Returns the skipped ranges that begin within \p Range, which must be + /// contained in a single file, ordered by their begin locations. + SmallVector<SkippedRange, 0> getSkippedRangesIn(SourceRange Range); void AddSkippedRange(SourceRange Range, SkippedRange::Kind RangeKind); diff --git a/clang/test/CoverageMapping/pragma-comment.c b/clang/test/CoverageMapping/pragma-comment.c new file mode 100644 index 00000000000000..3c868b1ac5dcbc --- /dev/null +++ b/clang/test/CoverageMapping/pragma-comment.c @@ -0,0 +1,11 @@ +// RUN: %clang_cc1 -fprofile-instrument=clang -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only %s | FileCheck %s + +// Comments in _Pragma strings are lexed in macro expansions. + +void f(void) { + _Pragma("clang diagnostic push /* comment */") +} + +// CHECK-LABEL: f: +// CHECK-NEXT: File 0, [[@LINE-5]]:14 -> [[@LINE-3]]:2 = #0 +// CHECK-NOT: Skipped _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
