llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-pgo Author: NAKAMURA Takumi (chapuni) <details> <summary>Changes</summary> `MergeStrategy` has options: - Merge: (default) Calculate metrics with merged `CoverageData`. - Any: Take `std::max` for each counter. This will show "Covered if any instances are satisfied". - All: Take `std::min` for each counter. This enforces "Covered if all instances are satisfied". T.B.D. TODO: Merging MC/DC is delegated to "Any" for now. Fixes #<!-- -->119299 Depends on: #<!-- -->121192 --- Patch is 32.78 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/121194.diff 15 Files Affected: - (modified) llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h (+78-4) - (modified) llvm/lib/ProfileData/Coverage/CoverageMapping.cpp (+155-15) - (modified) llvm/test/tools/llvm-cov/Inputs/branch-templates.cpp (+3-3) - (added) llvm/test/tools/llvm-cov/Inputs/mcdc-templates-merge.cpp (+54) - (added) llvm/test/tools/llvm-cov/Inputs/mcdc-templates-merge.proftext (+73) - (added) llvm/test/tools/llvm-cov/Inputs/mcdc-templates-merge.yaml (+105) - (modified) llvm/test/tools/llvm-cov/branch-export-json.test (+1-1) - (modified) llvm/test/tools/llvm-cov/branch-export-lcov.test (+2-2) - (modified) llvm/test/tools/llvm-cov/branch-macros.test (+9) - (modified) llvm/test/tools/llvm-cov/branch-templates.test (+2-2) - (added) llvm/test/tools/llvm-cov/mcdc-templates-merge.test (+41) - (modified) llvm/tools/llvm-cov/CodeCoverage.cpp (+11-1) - (modified) llvm/tools/llvm-cov/CoverageReport.cpp (+2-2) - (modified) llvm/tools/llvm-cov/CoverageViewOptions.h (+2) - (modified) llvm/tools/llvm-cov/SourceCoverageView.cpp (+2-2) ``````````diff diff --git a/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h b/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h index 64416fdba1b247..d6df8403a2cd1c 100644 --- a/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h +++ b/llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h @@ -59,6 +59,12 @@ namespace coverage { class CoverageMappingReader; struct CoverageMappingRecord; +enum class MergeStrategy { + Merge, + Any, + All, +}; + enum class coveragemap_error { success = 0, eof, @@ -375,6 +381,32 @@ struct CountedRegion : public CounterMappingRegion { : CounterMappingRegion(R), ExecutionCount(ExecutionCount), FalseExecutionCount(FalseExecutionCount), TrueFolded(false), FalseFolded(false) {} + + LineColPair viewLoc() const { return startLoc(); } + + bool isMergeable(const CountedRegion &RHS) const { + return (this->viewLoc() == RHS.viewLoc()); + } + + void merge(const CountedRegion &RHS, MergeStrategy Strategy); + + /// Returns comparable rank value in selecting a better Record for merging. + auto getMergeRank(MergeStrategy Strategy) const { + assert(isBranch() && "Dedicated to Branch"); + assert(Strategy == MergeStrategy::Any && "Dedicated to Any"); + unsigned m = 0; + // Prefer both Counts have values. + m = (m << 1) | (ExecutionCount != 0 && FalseExecutionCount != 0); + // Prefer both are unfolded. + m = (m << 1) | (!TrueFolded && !FalseFolded); + // Prefer either Count has value. + m = (m << 1) | (ExecutionCount != 0 || FalseExecutionCount != 0); + // Prefer either is unfolded. + m = (m << 1) | (!TrueFolded || !FalseFolded); + return std::make_pair(m, ExecutionCount + FalseExecutionCount); + } + + void commit() const {} }; /// MCDC Record grouping all information together. @@ -462,6 +494,19 @@ struct MCDCRecord { findIndependencePairs(); } + inline LineColPair viewLoc() const { return Region.endLoc(); } + + bool isMergeable(const MCDCRecord &RHS) const { + return (this->viewLoc() == RHS.viewLoc() && this->PosToID == RHS.PosToID && + this->CondLoc == RHS.CondLoc); + } + + // This may invalidate IndependencePairs + // MCDCRecord &operator+=(const MCDCRecord &RHS); + void merge(MCDCRecord &&RHS, MergeStrategy Strategy); + + void commit() { findIndependencePairs(); } + // Compare executed test vectors against each other to find an independence // pairs for each condition. This processing takes the most time. void findIndependencePairs(); @@ -512,15 +557,42 @@ struct MCDCRecord { return (*IndependencePairs)[PosToID[Condition]]; } - float getPercentCovered() const { - unsigned Folded = 0; + std::pair<unsigned, unsigned> getCoveredCount() const { unsigned Covered = 0; + unsigned Folded = 0; for (unsigned C = 0; C < getNumConditions(); C++) { if (isCondFolded(C)) Folded++; else if (isConditionIndependencePairCovered(C)) Covered++; } + return {Covered, Folded}; + } + + /// Returns comparable rank value in selecting a better Record for merging. + std::tuple<unsigned, unsigned, unsigned> + getMergeRank(MergeStrategy Strategy) const { + auto [Covered, Folded] = getCoveredCount(); + auto NumTVs = getNumTestVectors(); + switch (Strategy) { + case MergeStrategy::Merge: + case MergeStrategy::Any: + return { + Covered, // The largest covered number + ~Folded, // Less folded is better + NumTVs, // Show more test vectors + }; + case MergeStrategy::All: + return { + ~Covered, // The smallest covered number + ~Folded, // Less folded is better + NumTVs, // Show more test vectors + }; + } + } + + float getPercentCovered() const { + auto [Covered, Folded] = getCoveredCount(); unsigned Total = getNumConditions() - Folded; if (Total == 0) @@ -1013,11 +1085,13 @@ class CoverageMapping { /// information. That is, only names returned from getUniqueSourceFiles will /// yield a result. CoverageData getCoverageForFile( - StringRef Filename, + StringRef Filename, MergeStrategy Strategy = MergeStrategy::Merge, const DenseSet<const FunctionRecord *> &FilteredOutFunctions = {}) const; /// Get the coverage for a particular function. - CoverageData getCoverageForFunction(const FunctionRecord &Function) const; + CoverageData + getCoverageForFunction(const FunctionRecord &Function, + MergeStrategy Strategy = MergeStrategy::Merge) const; /// Get the coverage for an expansion within a coverage set. CoverageData getCoverageForExpansion(const ExpansionRecord &Expansion) const; diff --git a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp index e7780b465186df..dbbf5b03d0205e 100644 --- a/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp +++ b/llvm/lib/ProfileData/Coverage/CoverageMapping.cpp @@ -221,6 +221,58 @@ Expected<int64_t> CounterMappingContext::evaluate(const Counter &C) const { return LastPoppedValue; } +void CountedRegion::merge(const CountedRegion &RHS, MergeStrategy Strategy) { + assert(this->isBranch() && RHS.isBranch()); + auto MergeCounts = [Strategy](uint64_t &LHSCount, bool &LHSFolded, + uint64_t RHSCount, bool RHSFolded) { + switch (Strategy) { + default: + llvm_unreachable("Don't perform by-parameter merging"); + case MergeStrategy::Merge: + LHSCount += RHSCount; + LHSFolded = (LHSFolded && !LHSCount && RHSFolded); + break; + case MergeStrategy::All: + LHSCount = (LHSFolded ? RHSCount + : RHSFolded ? LHSCount + : std::min(LHSCount, RHSCount)); + LHSFolded = (LHSFolded && RHSFolded); + break; + } + }; + + switch (Strategy) { + case MergeStrategy::Any: + // Take either better (more satisfied) hand side. + // FIXME: Really needed? Better just to merge? + if (this->getMergeRank(Strategy) < RHS.getMergeRank(Strategy)) + *this = RHS; + break; + case MergeStrategy::Merge: + case MergeStrategy::All: + // Able to merge by parameter. + MergeCounts(this->ExecutionCount, this->TrueFolded, RHS.ExecutionCount, + RHS.TrueFolded); + MergeCounts(this->FalseExecutionCount, this->FalseFolded, + RHS.FalseExecutionCount, RHS.FalseFolded); + break; + } +} + +void MCDCRecord::merge(MCDCRecord &&RHS, MergeStrategy Strategy) { + assert(this->PosToID == RHS.PosToID); + assert(this->CondLoc == RHS.CondLoc); + + switch (Strategy) { + case MergeStrategy::Merge: + case MergeStrategy::Any: + case MergeStrategy::All: + if (this->getMergeRank(Strategy) < RHS.getMergeRank(Strategy)) + *this = std::move(RHS); + return; + } +} + // Find an independence pair for each condition: // - The condition is true in one test and false in the other. // - The decision outcome is true one test and false in the other. @@ -1272,7 +1324,8 @@ class SegmentBuilder { /// Combine counts of regions which cover the same area. static ArrayRef<CountedRegion> - combineRegions(MutableArrayRef<CountedRegion> Regions) { + combineRegions(MutableArrayRef<CountedRegion> Regions, + MergeStrategy Strategy) { if (Regions.empty()) return Regions; auto Active = Regions.begin(); @@ -1298,8 +1351,22 @@ class SegmentBuilder { // value for that area. // We add counts of the regions of the same kind as the active region // to handle the both situations. - if (I->Kind == Active->Kind) + if (I->Kind != Active->Kind) + continue; + + switch (Strategy) { + case MergeStrategy::Merge: Active->ExecutionCount += I->ExecutionCount; + break; + case MergeStrategy::Any: + Active->ExecutionCount = + std::max(Active->ExecutionCount, I->ExecutionCount); + break; + case MergeStrategy::All: + Active->ExecutionCount = + std::min(Active->ExecutionCount, I->ExecutionCount); + break; + } } return Regions.drop_back(std::distance(++Active, End)); } @@ -1307,12 +1374,13 @@ class SegmentBuilder { public: /// Build a sorted list of CoverageSegments from a list of Regions. static std::vector<CoverageSegment> - buildSegments(MutableArrayRef<CountedRegion> Regions) { + buildSegments(MutableArrayRef<CountedRegion> Regions, + MergeStrategy Strategy) { std::vector<CoverageSegment> Segments; SegmentBuilder Builder(Segments); sortNestedRegions(Regions); - ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions); + ArrayRef<CountedRegion> CombinedRegions = combineRegions(Regions, Strategy); LLVM_DEBUG({ dbgs() << "Combined regions:\n"; @@ -1342,11 +1410,78 @@ class SegmentBuilder { } }; +template <class RecTy> +static void mergeRecords(std::vector<RecTy> &Records, MergeStrategy Strategy) { + if (Records.empty()) + return; + + std::vector<RecTy> NewRecords; + + assert(Records.size() <= std::numeric_limits<unsigned>::max()); + + // Build up sorted indices (rather than pointers) of Records. + SmallVector<unsigned, 1> BIdxs(Records.size()); + std::iota(BIdxs.begin(), BIdxs.end(), 0); + llvm::stable_sort(BIdxs, [&](auto A, auto B) { + auto StartA = Records[A].viewLoc(); + auto StartB = Records[B].viewLoc(); + return (std::tie(StartA, A) < std::tie(StartB, B)); + }); + + // 1st element should be stored into SubView. + auto I = BIdxs.begin(), E = BIdxs.end(); + SmallVector<RecTy, 1> ViewRecords{Records[*I++]}; + + auto findMergeableInViewRecords = [&](const RecTy &Branch) { + auto I = ViewRecords.rbegin(), E = ViewRecords.rend(); + for (; I != E; ++I) + if (I->isMergeable(Branch)) + return I; + + // Not mergeable. + return E; + }; + + auto addRecordToSubView = [&] { + assert(!ViewRecords.empty() && "Should have the back"); + for (auto &Acc : ViewRecords) { + Acc.commit(); + NewRecords.push_back(std::move(Acc)); + } + }; + + for (; I != E; ++I) { + assert(!ViewRecords.empty() && "Should have the back in the loop"); + auto &AccB = ViewRecords.back(); + auto &Branch = Records[*I]; + + // Flush current and create the next SubView at the different line. + if (AccB.viewLoc().first != Branch.viewLoc().first) { + addRecordToSubView(); + ViewRecords = {Branch}; + } else if (auto AccI = findMergeableInViewRecords(Branch); + AccI != ViewRecords.rend()) { + // Merge the current Branch into the back of SubView. + AccI->merge(std::move(Branch), Strategy); + } else { + // Not mergeable. + ViewRecords.push_back(Branch); + } + } + + // Flush the last SubView. + addRecordToSubView(); + + // Replace + Records = std::move(NewRecords); +} + struct MergeableCoverageData : public CoverageData { std::vector<CountedRegion> CodeRegions; + MergeStrategy Strategy; - MergeableCoverageData(bool Single, StringRef Filename) - : CoverageData(Single, Filename) {} + MergeableCoverageData(MergeStrategy Strategy, bool Single, StringRef Filename) + : CoverageData(Single, Filename), Strategy(Strategy) {} void addFunctionRegions( const FunctionRecord &Function, @@ -1368,8 +1503,11 @@ struct MergeableCoverageData : public CoverageData { MCDCRecords.push_back(MR); } - CoverageData buildSegments() { - Segments = SegmentBuilder::buildSegments(CodeRegions); + CoverageData merge(MergeStrategy Strategy) { + mergeRecords(BranchRegions, Strategy); + mergeRecords(MCDCRecords, Strategy); + + Segments = SegmentBuilder::buildSegments(CodeRegions, Strategy); return CoverageData(std::move(*this)); } }; @@ -1423,10 +1561,10 @@ static bool isExpansion(const CountedRegion &R, unsigned FileID) { } CoverageData CoverageMapping::getCoverageForFile( - StringRef Filename, + StringRef Filename, MergeStrategy Strategy, const DenseSet<const FunctionRecord *> &FilteredOutFunctions) const { assert(SingleByteCoverage); - MergeableCoverageData FileCoverage(*SingleByteCoverage, Filename); + MergeableCoverageData FileCoverage(Strategy, *SingleByteCoverage, Filename); // Look up the function records in the given file. Due to hash collisions on // the filename, we may get back some records that are not in the file. @@ -1445,7 +1583,7 @@ CoverageData CoverageMapping::getCoverageForFile( LLVM_DEBUG(dbgs() << "Emitting segments for file: " << Filename << "\n"); - return FileCoverage.buildSegments(); + return FileCoverage.merge(Strategy); } std::vector<InstantiationGroup> @@ -1474,13 +1612,14 @@ CoverageMapping::getInstantiationGroups(StringRef Filename) const { } CoverageData -CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const { +CoverageMapping::getCoverageForFunction(const FunctionRecord &Function, + MergeStrategy Strategy) const { auto MainFileID = findMainViewFileID(Function); if (!MainFileID) return CoverageData(); assert(SingleByteCoverage); - MergeableCoverageData FunctionCoverage(*SingleByteCoverage, + MergeableCoverageData FunctionCoverage(Strategy, *SingleByteCoverage, Function.Filenames[*MainFileID]); FunctionCoverage.addFunctionRegions( Function, [&](auto &CR) { return (CR.FileID == *MainFileID); }, @@ -1489,7 +1628,7 @@ CoverageMapping::getCoverageForFunction(const FunctionRecord &Function) const { LLVM_DEBUG(dbgs() << "Emitting segments for function: " << Function.Name << "\n"); - return FunctionCoverage.buildSegments(); + return FunctionCoverage.merge(Strategy); } CoverageData CoverageMapping::getCoverageForExpansion( @@ -1511,7 +1650,8 @@ CoverageData CoverageMapping::getCoverageForExpansion( LLVM_DEBUG(dbgs() << "Emitting segments for expansion of file " << Expansion.FileID << "\n"); - ExpansionCoverage.Segments = SegmentBuilder::buildSegments(Regions); + ExpansionCoverage.Segments = + SegmentBuilder::buildSegments(Regions, MergeStrategy::Merge); return ExpansionCoverage; } diff --git a/llvm/test/tools/llvm-cov/Inputs/branch-templates.cpp b/llvm/test/tools/llvm-cov/Inputs/branch-templates.cpp index 4d932eaf5944a8..d8a7c056f36779 100644 --- a/llvm/test/tools/llvm-cov/Inputs/branch-templates.cpp +++ b/llvm/test/tools/llvm-cov/Inputs/branch-templates.cpp @@ -11,9 +11,9 @@ void unused(T x) { template<typename T> int func(T x) { - if(x) // BRCOV: | Branch ([[@LINE]]:6): [True: 0, False: 1] - return 0; // BRCOV: | Branch ([[@LINE-1]]:6): [True: 1, False: 0] - else // BRCOV: | Branch ([[@LINE-2]]:6): [True: 0, False: 1] + if(x) // BRCOV: | Branch ([[@LINE]]:6): [True: 1, False: {{2|1}}] + return 0; + else return 1; int j = 1; } diff --git a/llvm/test/tools/llvm-cov/Inputs/mcdc-templates-merge.cpp b/llvm/test/tools/llvm-cov/Inputs/mcdc-templates-merge.cpp new file mode 100644 index 00000000000000..09c2e0980cca85 --- /dev/null +++ b/llvm/test/tools/llvm-cov/Inputs/mcdc-templates-merge.cpp @@ -0,0 +1,54 @@ +#include <cstdio> + +template <typename Ty> +bool ab(Ty a, Ty b) { + return (a && b); +} +// MERGE: [[@LINE-2]]| 4| return +// ANY: [[@LINE-3]]| 2| return +// ALL: [[@LINE-4]]| 0| return + +// MERGE: MC/DC Coverage for Decision{{[:]}} 50.00% +// ANY: MC/DC Coverage for Decision{{[:]}} 50.00% +// ALL: MC/DC Coverage for Decision{{[:]}} 0.00% + +// CHECK: _Z2abIbEbT_S0_{{[:]}} +// CHECK: MC/DC Coverage for Decision{{[:]}} 50.00% + +// CHECK: _Z2abIxEbT_S0_{{[:]}} +// CHECK: MC/DC Coverage for Decision{{[:]}} 50.00% + +// CHECK: Unexecuted instantiation{{[:]}} _Z2abIdEbT_S0_ + +template <bool C> +bool Cab(bool a, bool b) { + return (a && b && C); +} +// MERGE: [[@LINE-2]]| 4| return +// ANY: [[@LINE-3]]| 2| return +// ALL: [[@LINE-4]]| 2| return + +// MERGE: MC/DC Coverage for Decision{{[:]}} 50.00% +// ANY: MC/DC Coverage for Decision{{[:]}} 50.00% +// ALL: MC/DC Coverage for Decision{{[:]}} 0.00% + +// CHECK: _Z3CabILb0EEbbb{{[:]}} +// CHECK: MC/DC Coverage for Decision{{[:]}} 0.00% + +// CHECK: _Z3CabILb1EEbbb{{[:]}} +// CHECK: MC/DC Coverage for Decision{{[:]}} 50.00% + +// CHECK: [[@LINE+1]]| 1|int main +int main(int argc, char **argv) { + printf("%d\n", Cab<false>(false, false)); + printf("%d\n", Cab<false>(true, true)); + printf("%d\n", Cab<true>(true, false)); + printf("%d\n", Cab<true>(true, true)); + printf("%d\n", ab(false, false)); + printf("%d\n", ab(true, true)); + printf("%d\n", ab(1LL, 0LL)); + printf("%d\n", ab(1LL, 1LL)); + if (argc == 2) + printf("%d\n", ab(0.0, 0.0)); + return 0; +} diff --git a/llvm/test/tools/llvm-cov/Inputs/mcdc-templates-merge.proftext b/llvm/test/tools/llvm-cov/Inputs/mcdc-templates-merge.proftext new file mode 100644 index 00000000000000..61369462b2fd46 --- /dev/null +++ b/llvm/test/tools/llvm-cov/Inputs/mcdc-templates-merge.proftext @@ -0,0 +1,73 @@ +_Z2abIbEbT_S0_ +# Func Hash: +1550 +# Num Counters: +3 +# Counter Values: +2 +1 +1 +# Num Bitmap Bytes: +$1 +# Bitmap Byte Values: +0x5 + + +_Z2abIxEbT_S0_ +# Func Hash: +1550 +# Num Counters: +3 +# Counter Values: +2 +2 +1 +# Num Bitmap Bytes: +$1 +# Bitmap Byte Values: +0x6 + + +_Z3CabILb0EEbbb +# Func Hash: +99214 +# Num Counters: +5 +# Counter Values: +2 +1 +0 +1 +1 +# Num Bitmap Bytes: +$1 +# Bitmap Byte Values: +0x5 + + +_Z3CabILb1EEbbb +# Func Hash: +99214 +# Num Counters: +5 +# Counter Values: +2 +1 +1 +2 +1 +# Num Bitmap Bytes: +$1 +# Bitmap Byte Values: +0xa + + +main +# Func Hash: +175973464 +# Num Counters: +2 +# Counter Values: +1 +0 + diff --git a/llvm/test/tools/llvm-cov/Inputs/mcdc-templates-merge.yaml b/llvm/test/tools/llvm-cov/Inputs/mcdc-templates-merge.yaml new file mode 100644 index 00000000000000..91d701a2172f82 --- /dev/null +++ b/llvm/test/tools/llvm-cov/Inputs/mcdc-templates-merge.yaml @@ -0,0 +1,105 @@ +--- !ELF +FileHeader: + Class: ELFCLASS64 + Data: ELFDATA2LSB + OSABI: ELFOSABI_GNU + Type: ET_REL + Machine: EM_X86_64 + SectionHeaderStringTable: .strtab +Sections: + - Name: __llvm_covfun + Type: SHT_PROGBITS + Flags: [ SHF_GNU_RETAIN ] + AddressAlign: 0x8 + Content: FAD58DE7366495DB2500000058247D0A00000000249EC986A505B62F010101010505012A210C020109070010200502000700100500110185808080080501050021 + - Name: '__llvm_covfun (1)' + Type: SHT_PROGBITS + Flags: [ SHF_GNU_RETAIN ] + AddressAlign: 0x8 + Content: 9CC3B348501DBFE8480000008E83010000000000249EC986A505B62F010103010D0D1105090901181A020201010B000C01000B0011280403000B0016300D02010300000B000C0D0010001130110603020000100011050015001630000A02000000150016 + - Name: '__llvm_covfun (2)' + Type: SHT_PROGBITS + Flags: [ SHF_GNU_RETAIN ] + AddressAlign: 0x8 + Content: 9873627177A03F8E460000008E83010000000000249EC986A505B62F010102010D0D110901181A020201010B000C01000B0011280403000B0016300D02010300000B000C0D0010001130110603020000100011050015001630090002000000150016 + - Name: '__llvm_covfun (3)' + Type: SHT_PROGBITS + Flags: [ SHF_GNU_RETAIN ] + AddressAlign: 0x8 + Content: BF407A207503B266320000000E06000000000000249EC986A505B62F0101020105050906010415020201010B000C280302000B0011300502010200000B000C050010001130090602000000100011 + - Name: '__llvm_covfun (4)' + Type: SHT_PROGBITS + Flags: [ SHF_GNU_RETAIN ] + AddressAlign: 0x8 + Content: 8A05A22CB467C37D320000000E06000000000000249EC986A505B62F0101020105050906010415020201010B000C280302000B0011300502010200000B000C050010001130090602000000100011 + - Name: '__llvm_covfun (5)' + Type: SHT_PROGBITS + Flags: [ SHF_GNU_RETAIN ] + AddressAlign: 0x8 + Content: 1700192CAC8F3F26320000000E06000000000000249EC986A505B62F0101020105050906010415020201010B000C280302000B0011300502010200000B000C050010001130090602000000100011 + - Name: __llvm_covmap + Type: SHT_PROGBITS + Flags: [ SHF_GNU_RETAIN ] + AddressAlign: 0x8 + ... [truncated] `````````` </details> https://github.com/llvm/llvm-project/pull/121194 _______________________________________________ llvm-branch-commits mailing list llvm-branch-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
