From f5d5d35e7e7744aa4dde1ed9180a3212fd9eb7f7 Mon Sep 17 00:00:00 2001 From: Justin Bogner Date: Wed, 1 Oct 2014 03:33:52 +0000 Subject: [PATCH] InstrProf: Avoid repeated linear searches in a hot path When generating coverage regions, we were doing a linear search through the existing regions in order to try to merge related ones. Most of the time this would find what it was looking for in a small number of steps and it wasn't a big deal, but in cases with many regions and few mergeable ones this leads to an absurd compile time regression. This changes the coverage mapping logic to do a single sort and then merge as we go, which is a bit simpler and about 100 times faster. I've also added FIXMEs on a couple of behaviours that seem a little suspect, while keeping them behaving as they were - I'll look into these soon. The test changes here are mostly tedious reorganization, because the ordering of regions we output has become slightly (but not completely) more consistent from the almost completely arbitrary ordering we got before. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@218738 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/CodeGen/CoverageMappingGen.cpp | 84 +++++++++++----------------- test/CoverageMapping/includehell.cpp | 14 ++--- test/CoverageMapping/loopmacro.c | 8 +-- test/CoverageMapping/macroception.c | 49 ++++++++-------- test/CoverageMapping/macroparams.c | 11 ++-- 5 files changed, 76 insertions(+), 90 deletions(-) diff --git a/lib/CodeGen/CoverageMappingGen.cpp b/lib/CodeGen/CoverageMappingGen.cpp index b7cbd33a3b..2bfe0fb860 100644 --- a/lib/CodeGen/CoverageMappingGen.cpp +++ b/lib/CodeGen/CoverageMappingGen.cpp @@ -101,26 +101,19 @@ public: /// \brief Return true if two regions can be merged together. bool isMergeable(SourceMappingRegion &R) { + // FIXME: We allow merging regions with a gap in between them. Should we? return File == R.File && MacroArgumentFile == R.MacroArgumentFile && Count == R.Count && UnreachableInitiator == R.UnreachableInitiator && Group == R.Group; } - bool isMergeable(FileID File, FileID MacroArgumentFile, Counter Count, - const Stmt *UnreachableInitiator, const Stmt *Group) { - return this->File == File && this->MacroArgumentFile == MacroArgumentFile && - this->Count == Count && - this->UnreachableInitiator == UnreachableInitiator && - this->Group == Group; - } - - /// \brief Merge two regions by extending the 'this' region to cover the - /// given region. - void mergeByExtendingTo(SourceMappingRegion &R) { - LocEnd = R.LocEnd; - AlternativeLocEnd = R.LocStart; - if (hasFlag(IgnoreIfNotExtended)) - clearFlag(IgnoreIfNotExtended); + /// \brief A comparison that sorts such that mergeable regions are adjacent. + friend bool operator<(const SourceMappingRegion &LHS, + const SourceMappingRegion &RHS) { + return std::tie(LHS.File, LHS.MacroArgumentFile, LHS.Count, + LHS.UnreachableInitiator, LHS.Group) < + std::tie(RHS.File, RHS.MacroArgumentFile, RHS.Count, + RHS.UnreachableInitiator, RHS.Group); } }; @@ -169,7 +162,7 @@ public: /// \brief The coverage mapping regions for this function llvm::SmallVector MappingRegions; /// \brief The source mapping regions for this function. - llvm::SmallVector SourceRegions; + std::vector SourceRegions; CoverageMappingBuilder(CoverageMappingModuleGen &CVM, SourceManager &SM, const LangOptions &LangOpts) @@ -327,23 +320,6 @@ public: /// \brief Exit the current source region group. void endSourceRegionGroup() { CurrentSourceGroup = nullptr; } - /// \brief Brings a region that has the same counter and file to the back - /// of the source regions array. - void bringSimilarRegionBack(Counter Count, FileID File, - FileID MacroArgumentFile, - const Stmt *UnreachableInitiator, - const Stmt *SourceGroup) { - for (size_t I = SourceRegions.size(); I != 0;) { - --I; - if (SourceRegions[I].isMergeable(File, MacroArgumentFile, Count, - UnreachableInitiator, SourceGroup)) { - if (I != SourceRegions.size() - 1) - std::swap(SourceRegions[I], SourceRegions.back()); - return; - } - } - } - /// \brief Associate a counter with a given source code range. void mapSourceCodeRange(SourceLocation LocStart, SourceLocation LocEnd, Counter Count, const Stmt *UnreachableInitiator, @@ -370,15 +346,9 @@ public: // Make sure that the file id is valid. if (File.isInvalid()) return; - bringSimilarRegionBack(Count, File, MacroArgumentFile, UnreachableInitiator, - SourceGroup); - SourceMappingRegion R(File, MacroArgumentFile, Count, UnreachableInitiator, - SourceGroup, LocStart, LocEnd, Flags); - if (SourceRegions.empty() || !SourceRegions.back().isMergeable(R)) { - SourceRegions.push_back(R); - return; - } - SourceRegions.back().mergeByExtendingTo(R); + SourceRegions.emplace_back(File, MacroArgumentFile, Count, + UnreachableInitiator, SourceGroup, LocStart, + LocEnd, Flags); } void mapSourceCodeRange(SourceLocation LocStart, SourceLocation LocEnd, @@ -399,14 +369,26 @@ public: /// \brief Generate the coverage counter mapping regions from collected /// source regions. void emitSourceRegions() { - for (const auto &R : SourceRegions) { - SourceLocation LocStart = R.getStartLoc(); - SourceLocation LocEnd = R.getEndLoc(SM); - - if (R.hasFlag(SourceMappingRegion::IgnoreIfNotExtended) && - LocStart == LocEnd) + std::sort(SourceRegions.begin(), SourceRegions.end()); + + for (auto I = SourceRegions.begin(), E = SourceRegions.end(); I != E; ++I) { + // Keep the original start location of this region. + SourceLocation LocStart = I->getStartLoc(); + SourceLocation LocEnd = I->getEndLoc(SM); + + bool Ignore = I->hasFlag(SourceMappingRegion::IgnoreIfNotExtended); + // We need to handle mergeable regions together. + for (auto Next = I + 1; Next != E && Next->isMergeable(*I); ++Next) { + ++I; + LocStart = std::min(LocStart, I->getStartLoc()); + LocEnd = std::max(LocEnd, I->getEndLoc(SM)); + // FIXME: Should we && together the Ignore flag of multiple regions? + Ignore = false; + } + if (Ignore) continue; + // Find the spilling locations for the mapping region. LocEnd = getPreciseTokenLocEnd(LocEnd); unsigned LineStart = SM.getSpellingLineNumber(LocStart); unsigned ColumnStart = SM.getSpellingColumnNumber(LocStart); @@ -415,13 +397,13 @@ public: auto SpellingFile = SM.getDecomposedSpellingLoc(LocStart).first; unsigned CovFileID; - if (getCoverageFileID(LocStart, R.getFile(), SpellingFile, CovFileID)) + if (getCoverageFileID(LocStart, I->getFile(), SpellingFile, CovFileID)) continue; assert(LineStart <= LineEnd); MappingRegions.push_back(CounterMappingRegion( - R.getCounter(), CovFileID, LineStart, ColumnStart, LineEnd, ColumnEnd, - false, CounterMappingRegion::CodeRegion)); + I->getCounter(), CovFileID, LineStart, ColumnStart, LineEnd, + ColumnEnd, false, CounterMappingRegion::CodeRegion)); } } }; diff --git a/test/CoverageMapping/includehell.cpp b/test/CoverageMapping/includehell.cpp index 4f4028d454..653f41464d 100644 --- a/test/CoverageMapping/includehell.cpp +++ b/test/CoverageMapping/includehell.cpp @@ -1,12 +1,12 @@ // RUN: %clang_cc1 -fprofile-instr-generate -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only -main-file-name includehell.cpp %s | FileCheck %s -// CHECK: File 0, 1:1 -> 9:7 = #0 (HasCodeBefore = 0) -// CHECK-NEXT: File 0, 2:13 -> 4:2 = #1 (HasCodeBefore = 0) -// CHECK-NEXT: File 0, 4:8 -> 6:2 = (#0 - #1) (HasCodeBefore = 0) -// CHECK-NEXT: File 0, 7:11 -> 9:2 = #2 (HasCodeBefore = 0) -// CHECK-NEXT: File 0, 9:8 -> 11:2 = (#0 - #2) (HasCodeBefore = 0) -int main() { // CHECK-NEXT: File 1, [[@LINE]]:12 -> [[@LINE+4]]:2 = #0 (HasCodeBefore = 0) +int main() { // CHECK: File 0, [[@LINE]]:12 -> [[@LINE+4]]:2 = #0 (HasCodeBefore = 0) int x = 0; - #include "Inputs/code.h" // CHECK-NEXT: Expansion,File 1, [[@LINE]]:12 -> [[@LINE]]:27 = #0 (HasCodeBefore = 0, Expanded file = 0) + #include "Inputs/code.h" // CHECK-NEXT: Expansion,File 0, [[@LINE]]:12 -> [[@LINE]]:27 = #0 (HasCodeBefore = 0, Expanded file = 1) return 0; } +// CHECK-NEXT: File 1, 1:1 -> 9:7 = #0 (HasCodeBefore = 0) +// CHECK-NEXT: File 1, 2:13 -> 4:2 = #1 (HasCodeBefore = 0) +// CHECK-NEXT: File 1, 4:8 -> 6:2 = (#0 - #1) (HasCodeBefore = 0) +// CHECK-NEXT: File 1, 7:11 -> 9:2 = #2 (HasCodeBefore = 0) +// CHECK-NEXT: File 1, 9:8 -> 11:2 = (#0 - #2) (HasCodeBefore = 0) diff --git a/test/CoverageMapping/loopmacro.c b/test/CoverageMapping/loopmacro.c index cd93878fb7..8480dbdc37 100644 --- a/test/CoverageMapping/loopmacro.c +++ b/test/CoverageMapping/loopmacro.c @@ -29,12 +29,12 @@ int main() { // CHECK: File 0, [[@LINE]]:12 -> [[ // CHECK-NEXT: File 0, 24:21 -> 24:29 = (#0 + #1) (HasCodeBefore = 0) // CHECK-NEXT: File 0, 24:31 -> 24:40 = (#0 + #1) (HasCodeBefore = 0) // CHECK-NEXT: File 1, 10:4 -> 12:23 = (#0 + #1) (HasCodeBefore = 0) -// CHECK-NEXT: Expansion,File 1, 10:5 -> 10:16 = (#0 + #1) (HasCodeBefore = 0, Expanded file = 3) +// CHECK-NEXT: Expansion,File 1, 10:5 -> 10:16 = (#0 + #1) (HasCodeBefore = 0, Expanded file = 2) // CHECK-NEXT: File 1, 10:17 -> 10:22 = (#0 + #1) (HasCodeBefore = 0) // CHECK-NEXT: File 1, 10:17 -> 10:22 = (#0 + #1) (HasCodeBefore = 0) // CHECK-NEXT: File 1, 10:24 -> 10:32 = (#0 + #1) (HasCodeBefore = 0) // CHECK-NEXT: File 1, 10:33 -> 10:36 = (#0 + #1) (HasCodeBefore = 0) // CHECK-NEXT: File 1, 10:46 -> 10:49 = (#0 + #1) (HasCodeBefore = 0) -// CHECK-NEXT: File 2, 5:18 -> 5:53 = (#0 + #1) (HasCodeBefore = 0) -// CHECK-NEXT: File 3, 8:26 -> 8:66 = (#0 + #1) (HasCodeBefore = 0) -// CHECK-NEXT: Expansion,File 3, 8:38 -> 8:45 = (#0 + #1) (HasCodeBefore = 0, Expanded file = 2) +// CHECK-NEXT: File 2, 8:26 -> 8:66 = (#0 + #1) (HasCodeBefore = 0) +// CHECK-NEXT: Expansion,File 2, 8:38 -> 8:45 = (#0 + #1) (HasCodeBefore = 0, Expanded file = 3) +// CHECK-NEXT: File 3, 5:18 -> 5:53 = (#0 + #1) (HasCodeBefore = 0) diff --git a/test/CoverageMapping/macroception.c b/test/CoverageMapping/macroception.c index 7db02be5a6..edbd84a017 100644 --- a/test/CoverageMapping/macroception.c +++ b/test/CoverageMapping/macroception.c @@ -5,33 +5,36 @@ #define M22 } #define M11 M22 - // CHECK: main - // CHECK-NEXT: File 0, 3:12 -> 3:13 = #0 (HasCodeBefore = 0) - // CHECK-NEXT: Expansion,File 1, 4:12 -> 4:14 = #0 (HasCodeBefore = 0, Expanded file = 0) -int main() M1 // CHECK-NEXT: Expansion,File 2, [[@LINE]]:12 -> [[@LINE]]:14 = #0 (HasCodeBefore = 0, Expanded file = 1) - return 0; // CHECK-NEXT: File 2, [[@LINE]]:3 -> [[@LINE+1]]:2 = #0 (HasCodeBefore = 0) +// CHECK-LABEL: main: +int main() M1 // CHECK-NEXT: Expansion,File 0, [[@LINE]]:12 -> [[@LINE]]:14 = #0 (HasCodeBefore = 0, Expanded file = 2) + return 0; // CHECK-NEXT: File 0, [[@LINE]]:3 -> [[@LINE+1]]:2 = #0 (HasCodeBefore = 0) } +// CHECK-NEXT: File 1, 3:12 -> 3:13 = #0 (HasCodeBefore = 0) +// CHECK-NEXT: Expansion,File 2, 4:12 -> 4:14 = #0 (HasCodeBefore = 0, Expanded file = 1) - // CHECK-NEXT: func2 + +// CHECK-LABEL: func2: void func2() { // CHECK-NEXT: File 0, [[@LINE]]:14 -> [[@LINE+1]]:12 = #0 (HasCodeBefore = 0) int x = 0; M11 // CHECK-NEXT: Expansion,File 0, [[@LINE]]:1 -> [[@LINE]]:4 = #0 (HasCodeBefore = 0, Expanded file = 2) - // CHECK-NEXT: File 1, 5:13 -> 5:14 = #0 (HasCodeBefore = 0) - // CHECK-NEXT: Expansion,File 2, 6:13 -> 6:16 = #0 (HasCodeBefore = 0, Expanded file = 1) +// CHECK-NEXT: File 1, 5:13 -> 5:14 = #0 (HasCodeBefore = 0) +// CHECK-NEXT: Expansion,File 2, 6:13 -> 6:16 = #0 (HasCodeBefore = 0, Expanded file = 1) + +// CHECK-LABEL: func3: +void func3() M1 // CHECK-NEXT: Expansion,File 0, [[@LINE]]:14 -> [[@LINE]]:16 = #0 (HasCodeBefore = 0, Expanded file = 2) + int x = 0; // CHECK-NEXT: File 0, [[@LINE]]:3 -> [[@LINE]]:12 = #0 (HasCodeBefore = 0) +M11 // CHECK-NEXT: Expansion,File 0, [[@LINE]]:1 -> [[@LINE]]:4 = #0 (HasCodeBefore = 0, Expanded file = 4) - // CHECK-NEXT: func3 - // CHECK-NEXT: File 0, 3:12 -> 3:13 = #0 (HasCodeBefore = 0) - // CHECK-NEXT: Expansion,File 1, 4:12 -> 4:14 = #0 (HasCodeBefore = 0, Expanded file = 0) -void func3() M1 // CHECK-NEXT: Expansion,File 2, [[@LINE]]:14 -> [[@LINE]]:16 = #0 (HasCodeBefore = 0, Expanded file = 1) - int x = 0; // CHECK-NEXT: File 2, [[@LINE]]:3 -> [[@LINE]]:12 = #0 (HasCodeBefore = 0) -M11 // CHECK-NEXT: Expansion,File 2, [[@LINE]]:1 -> [[@LINE]]:4 = #0 (HasCodeBefore = 0, Expanded file = 4) - // CHECK-NEXT: File 3, 5:13 -> 5:14 = #0 (HasCodeBefore = 0) - // CHECK-NEXT: Expansion,File 4, 6:13 -> 6:16 = #0 (HasCodeBefore = 0, Expanded file = 3) +// CHECK-NEXT: File 1, 3:12 -> 3:13 = #0 (HasCodeBefore = 0) +// CHECK-NEXT: Expansion,File 2, 4:12 -> 4:14 = #0 (HasCodeBefore = 0, Expanded file = 1) +// CHECK-NEXT: File 3, 5:13 -> 5:14 = #0 (HasCodeBefore = 0) +// CHECK-NEXT: Expansion,File 4, 6:13 -> 6:16 = #0 (HasCodeBefore = 0, Expanded file = 3) - // CHECK-NEXT: func4 - // CHECK-NEXT: File 0, 3:12 -> 3:13 = #0 (HasCodeBefore = 0) - // CHECK-NEXT: Expansion,File 1, 4:12 -> 4:14 = #0 (HasCodeBefore = 0, Expanded file = 0) - // CHECK-NEXT: Expansion,File 2, [[@LINE+1]]:14 -> [[@LINE+1]]:16 = #0 (HasCodeBefore = 0, Expanded file = 1) -void func4() M1 M11 // CHECK-NEXT: Expansion,File 2, [[@LINE]]:17 -> [[@LINE]]:20 = #0 (HasCodeBefore = 0, Expanded file = 4) - // CHECK-NEXT: File 3, 5:13 -> 5:14 = #0 (HasCodeBefore = 0) - // CHECK-NEXT: Expansion,File 4, 6:13 -> 6:16 = #0 (HasCodeBefore = 0, Expanded file = 3) +// CHECK-LABEL: func4: +// CHECK-NEXT: File 0, 3:12 -> 3:13 = #0 (HasCodeBefore = 0) +// CHECK-NEXT: Expansion,File 1, 4:12 -> 4:14 = #0 (HasCodeBefore = 0, Expanded file = 0) +void func4() M1 M11 +// CHECK-NEXT: Expansion,File 2, [[@LINE-1]]:14 -> [[@LINE-1]]:16 = #0 (HasCodeBefore = 0, Expanded file = 1) +// CHECK-NEXT: Expansion,File 2, [[@LINE-2]]:17 -> [[@LINE-2]]:20 = #0 (HasCodeBefore = 0, Expanded file = 4) +// CHECK-NEXT: File 3, 5:13 -> 5:14 = #0 (HasCodeBefore = 0) +// CHECK-NEXT: Expansion,File 4, 6:13 -> 6:16 = #0 (HasCodeBefore = 0, Expanded file = 3) diff --git a/test/CoverageMapping/macroparams.c b/test/CoverageMapping/macroparams.c index b28aca3ed7..adf01ec09b 100644 --- a/test/CoverageMapping/macroparams.c +++ b/test/CoverageMapping/macroparams.c @@ -1,11 +1,12 @@ // RUN: %clang_cc1 -fprofile-instr-generate -fcoverage-mapping -dump-coverage-mapping -emit-llvm-only -main-file-name macroparams.c %s | FileCheck %s -#define MACRO2(X2) (X2 + 2) // CHECK: File 0, [[@LINE]]:20 -> [[@LINE]]:28 = #0 (HasCodeBefore = 0) -#define MACRO(X) MACRO2(x) // CHECK-NEXT: Expansion,File 1, [[@LINE]]:18 -> [[@LINE]]:24 = #0 (HasCodeBefore = 0, Expanded file = 0) - // CHECK-NEXT: File 1, [[@LINE-1]]:25 -> [[@LINE-1]]:26 = #0 (HasCodeBefore = 0) +#define MACRO2(X2) (X2 + 2) // CHECK-DAG: File 2, [[@LINE]]:20 -> [[@LINE]]:28 = #0 (HasCodeBefore = 0) +#define MACRO(X) MACRO2(x) // CHECK-DAG: File 1, [[@LINE]]:25 -> [[@LINE]]:26 = #0 (HasCodeBefore = 0) + // CHECK-DAG: Expansion,File 1, [[@LINE-1]]:18 -> [[@LINE-1]]:24 = #0 (HasCodeBefore = 0, Expanded file = 2) -int main() { // CHECK-NEXT: File 2, [[@LINE]]:12 -> [[@LINE+4]]:2 = #0 (HasCodeBefore = 0) + +int main() { // CHECK-DAG: File 0, [[@LINE]]:12 -> [[@LINE+4]]:2 = #0 (HasCodeBefore = 0) int x = 0; - MACRO(x); // CHECK-NEXT: Expansion,File 2, [[@LINE]]:3 -> [[@LINE]]:8 = #0 (HasCodeBefore = 0, Expanded file = 1) + MACRO(x); // CHECK-DAG: Expansion,File 0, [[@LINE]]:3 -> [[@LINE]]:8 = #0 (HasCodeBefore = 0, Expanded file = 1) return 0; } -- 2.40.0