This is an archive of the discontinued LLVM Phabricator instance.

MC/DC in LLVM Source-Based Code Coverage: llvm-cov visualization
ClosedPublic

Authored by alanphipps on Nov 28 2022, 11:58 AM.

Details

Summary

MC/DC in LLVM Source-based Code Coverage: Review 2/3

Background
I previously upstreamed work to enable Branch Coverage (https://reviews.llvm.org/D84467), which was pushed in early 2021. MC/DC (Modified Condition/Decision Coverage) is a planned enhancement to Source-based Code Coverage. Implementation was completed in May for our downstream Arm compiler, and in general use it has not yielded any issues.

Patches have been tested on windows (stage1) and linux/mac (stage1 and stage2). Fuchsia is not yet supported.

See attached file for Background, Motivation, Design, and Implementation Concepts:

See attached PDF for Technical Talk slides from 2022 LLVM Developers' Meeting:

I am also available at Discord @alanphipps

Review
This review is for the Visualization and Evaluation components

  • Bitmask evaluation and MC/DC Region Analysis:
    • CoverageMapping.h, CoverageMapping.cpp
  • Creation of MC/DC Views with Records:
    • CodeCoverage.cpp
    • CoverageViewOptions.h
  • Text, HTML Visualization:
    • SourceCoverageView.h, SourceCoverageView.cpp
    • SourceCoverageViewHTML.h, SourceCoverageViewHTML.cpp
    • SourceCoverageViewText.h, SourceCoverageViewText.cpp
  • Summary Report Generation:
    • CoverageSummaryInfo.h, CoverageSummaryInfo.cpp
    • CoverageReport.cpp
  • JSON exporting:
    • CoverageExporterJson.cpp

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
Herald added a project: Restricted Project. · View Herald TranscriptNov 28 2022, 11:58 AM
alanphipps requested review of this revision.Nov 28 2022, 11:58 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 28 2022, 11:58 AM
alanphipps edited the summary of this revision. (Show Details)Nov 28 2022, 12:13 PM
alanphipps edited the summary of this revision. (Show Details)Nov 28 2022, 12:17 PM
bcain added a subscriber: bcain.Dec 15 2022, 8:48 AM

Overall, it looks good to me. I added a few minor things.
Please add --show-mcdc to the llvm-cov command guide.
https://github.com/llvm/llvm-project/blob/main/llvm/docs/CommandGuide/llvm-cov.rst

llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h
238

What is the purpose of MCDCBranchRegion? We already have branch regions, and why adding MCDCDecisionRegion is not enough?

llvm/tools/llvm-cov/CoverageSummaryInfo.h
147

This comment misses a dot at the end.

158

"Covered pairs over-counted"

179

"Covered pairs over-counted"

Ibnmardanis24 added inline comments.Mar 13 2023, 2:34 AM
llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h
238

My understanding is that MCDCDecisionRegion is used for storing the set of minimum condition permutations required for complete MC/DC coverage. This is fundamentally different from BranchRegion's purpose. BranchRegion records the path taken, rather than the condition set that produced it. There is an interesting interaction between the 2, which I believe to be the reason for MCDCBranchRegion: when on a given path, subsequent branching could be conditioned by the particular permutation that allowed it, meaning the path taken downstream could be guessed from MC/DC information. This condition projection can only be done when on MC/DC mode and it also requires more space to exercise. Therefore, this should justify having BranchRegion and MCDCBranchRegion separated.

alanphipps marked 2 inline comments as done.Mar 13 2023, 7:02 AM
alanphipps added inline comments.
llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h
238

Yes there are three region types that apply:

1.) "BranchRegion" applies to BranchCoverage when MC/DC is not enabled or to single conditions (where MC/DC doesn't make sense) and simply represents the True/False Counters for a condition. This is also maintained for backward compatibility in the format. It requires less data than MCDCBranchRegion.

2.) "MCDCBranchRegion" extends "BranchRegion" to also apply condition IDs to the condition and is only used when MC/DC is enabled and used.

3.) "MCDCDecisionRegion" is intended to apply to the entire set of conditions in the boolean expression, supplying the source begin/end for the whole region, and supply bitmap index used to track the test vectors for the region.

llvm-cov associates MCDCDecisionRegion with a set of MCDCBranchRegions based on its tie to the source code.

alanphipps marked an inline comment as done.Mar 13 2023, 7:04 AM

Overall, it looks good to me. I added a few minor things.
Please add --show-mcdc to the llvm-cov command guide.
https://github.com/llvm/llvm-project/blob/main/llvm/docs/CommandGuide/llvm-cov.rst

Thanks! -- yes I need to add the documentation. I'll make the adjustments with a rebase soon.

gulfem added a comment.EditedMar 13 2023, 12:19 PM

Your commit message mentioned: "Fuchsia is not yet supported."
Is there anything that stops us generating MC/DC coverage in Fuchsia or is it just not tested yet?

llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h
238

Thanks for the explanation!

alanphipps marked 3 inline comments as done.Jun 14 2023, 7:55 AM

Your commit message mentioned: "Fuchsia is not yet supported."
Is there anything that stops us generating MC/DC coverage in Fuchsia or is it just not tested yet?

Right, there's nothing that would stop us from enabling MC/DC for Fuchsia; it's not tested. I was planning to leave it separate, so if you or someone wants to enable it and test it, I would be happy to help!

Rebase and update based on review comments.

Updated diff based on some of the review comments in the clang review (https://reviews.llvm.org/D138849)

Reapply clang-format and minor cleanup

@alanphipps Thanks for the update.

Can I regenerate test imputs in tests? (eg. *.o32l)
I suggest adding command lines as comments in each source file.

I don't know how to obtain blobs from phab.

This is cool!

llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h
257

On AArch64 Darwin (with clang-1403), FileID is set to 1 when used uninitialised. Somewhere in this patch set we create a default CounterMappingRegion struct.

This causes ParameterizedCovMapTest/CoverageMappingTest.non_code_region_bitmask/0 to assert.

Can we explicitly initialise these values to 0?

paquette added inline comments.Jun 27 2023, 11:53 PM
llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h
242

Style nit: I don't think I've ever seen an underscore at the beginning of a struct name? Maybe I'm wrong.

374

Why not SmallVector?

375

Why not SmallVector?

376

Why not SmallVector?

432

Variables in this function should start with a capital letter.

https://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly

Variable names should be nouns (as they represent state). The name should be camel case, and start with an upper case letter (e.g. Leader or Boats).

444

Nit: prefer static cast for greppability

447

Nit: Prefer whole words? (Ditto for the other Hdr function)

470

Nit: prefer whole words?

Also when I read "TestVector" I assume the type is going to be some sort of vector. Could you give this a different name?

471

In asserts, a string describing why the assert is there can be very helpful.

473

Maybe there should be a function called printConditions?

495

Maybe there should be a function called printResult?

506
507
llvm/lib/ProfileData/Coverage/CoverageMapping.cpp
210

Can you add Doxygen comments to the member variables in this class?

211

Looking at the later code, it looks like this indicates whether or not something was run. How about renaming it so that's clear?

E.g. VectorAtIdxWasExecuted or something?

236

LLVM style guide for variables

254

How about some helper functions for this instead of a comment?

shouldCopyOffTestVectorForTruePath(Branch);
shouldCopyOffTestVectorForFalsePath(Branch);
279

How about let's get rid of the braces here to make this a little easier to read.

for (unsigned Idx = 0; Idx < Bitmap.size(); ++Idx) {
   if (!Bitmap[Idx])
     continue;
   assert(!TestVectors[i].empty() && "Test vector doesn't exist.");
   ExecVectors.push_back(TestVectors[i]);
}
285

Can you add a comment explaining what this function is supposed to do?

Also can you give a more descriptive name to C? Maybe ConditionIdx?

301

How about

// Look for other conditions that don't match.
// Skip over C and don't care values (because we don't care about them).
const auto ARecordTyForCond = A[i];
const auto BRecordTyForCond = B[i];
if (i == C ||
    ARecordTyForCond == MCDCRecord::MCDC_DontCare ||
    BRecordTyForCond == MCDCRecord::MCDC_DontCare)
  continue;

// Condition mismatch, so we don't have a match.
if (ARecordTyForCond != BRecordTyForCond)
  return false;

The checks for don't-cares are technically "skip this" statements, so it feels clearer to include them in the continue branch.

310

Can you add a comment to this function?

paquette added inline comments.Jun 28 2023, 12:05 AM
llvm/lib/ProfileData/Coverage/CoverageMapping.cpp
334

Doxygen comment?

339

this comment probably could be adapted into a doxygen comment

478

LLVM coding standards say to avoid else after return.

https://llvm.org/docs/CodingStandards.html#don-t-use-else-after-a-return

526

Can you explain why you are decrementing this?

533

Why not rewrite evaluateBitmap so that it passes the whole MCDCDecision struct?

Thank you for the comments! I appreciate the attention on this review. I hope to address them within the next few days.

No problem, thanks for doing this work, it's very exciting!

Update forthcoming for this review this weekend... Sorry for the delay!

alanphipps marked 27 inline comments as done.Jul 15 2023, 3:45 PM
alanphipps added inline comments.
llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h
473

The function is really constructing a string. I'm going to leave the function intact but it makes sense that the comments shouldn't say "print" when that's not really what it's doing.

alanphipps marked an inline comment as done.
alanphipps added a reviewer: paquette.

Update diff...

This revision is now accepted and ready to land.Jul 17 2023, 8:18 PM

Thank you for the working and excuse my nitpicks.

llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h
260–261

Could this be reformatted?

545–546

Could this be reformatted?

llvm/lib/ProfileData/Coverage/CoverageMapping.cpp
546–548

Could this be reformatted?

llvm/test/tools/llvm-cov/mcdc-const.test
5

I am afraid this would fail if LLVM is not configured for the arch of mcdc-*.o.

phosek added inline comments.Jul 20 2023, 9:24 AM
llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h
242

No need for typedef in C++.

254–263

I'd consider omitting these constructors altogether and just use aggregate initialization with default values.

phosek added inline comments.Jul 20 2023, 9:24 AM
llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h
372

No need for typedef in C++.

413

I'd consider spelling it out in full, it took me a second to realize that Indep means "Independent", or at least I assume it does?

448
456
473
510
llvm/lib/ProfileData/Coverage/CoverageMapping.cpp
204
205
361
362
365
368
llvm/tools/llvm-cov/CoverageSummaryInfo.cpp
50
phosek added inline comments.Jul 25 2023, 12:22 AM
llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h
241

I think that MCDCConditionID would be a more idiomatic LLVM type name.

alanphipps marked 20 inline comments as done.

Update diff based clang-format and review comments...

llvm/test/tools/llvm-cov/mcdc-const.test
5

Support for different binary formats is tested by binary-formats.c, but I'm not sure this matters for the documented coverage format anyway because it isn't architecture specific, unless I'm overlooking something. I've not seen any issues with others tests in the same directory that follow the same pattern (e.g. branch-c-general.test et al.) that are also built for a single arch and binary format.

I confirmed all tests passing (with applying three diffs and generated blobs). Thanks.

llvm/test/tools/llvm-cov/mcdc-const.test
5

I generated wrong object mcdc-const*.o. (I didn't copy mcdc-const*.cpp to /tmp)
It caused test failures when directory layout differs.
Sorry for bothering you.

I have reconfirmed mcdc-const*.o generated on aarch64 working on amd64 as well.

I confirmed all tests passing (with applying three diffs and generated blobs). Thanks.

@chapuni Thank you so much for confirming this on your end!

Thank you @phosek for your comments. Do you see anything else on your end?

A merge conflict to D151283. Could you catch up?

HI, I just started to look into MC/DC, and if I understand correctly, with the current implementation, you can have 100% MC/DC coverage in the following case:

void test(bool a, bool b, bool c) {

  if (a && b)
    std::cout << "test_1 decision true\n";

  if (c)
    std::cout << "test_2 decision true\n";

}

int main() {
    test(true, false, false);
    test(true, true, false);
    test(false, true, false);
}

This gives you 100% MC/DC coverage (with 2 MC/DC conditions considered). However, with the tests executed, 'c' did not meet the requirements imposed by MC/DC (for example the condition did not take every possible value)

If you change 'if (c)' to 'if (c && 1)' the MC/DC coverage changes to 66.67% (with 3 MC/DC conditions considered), which should be the result for the original use case I think.
Also if you consider branch coverage as well, it will show that the tests missed some spots.

As far as I understood, MC/DC coverage should be more strict than branch coverage, so 100% MC/CD coverage should imply 100% branch coverage. Or do I miss something here?

alanphipps marked an inline comment as done.Sep 4 2023, 7:40 AM

Hello! Thanks for your question.

Also if you consider branch coverage as well, it will show that the tests missed some spots.

As far as I understood, MC/DC coverage should be more strict than branch coverage, so 100% MC/CD coverage should imply 100% branch coverage. Or do I miss something here?

This implementation of MC/DC is similar to that of other vendors (e.g. LDRA) in that MC/DC coverage for single condition expressions is trivially derivable via branch coverage, which ought to be considered together with the MC/DC metric. A “test vector” for a single condition (boolean expression without operators) is simply true or false. Strictly speaking, branch coverage also gives you a metrics for other things that don’t involve an explicit Boolean expression, such as switch statements and loop ranges. The metric itself need not imply 100% branch coverage.

As this is a good observation, I can make sure the documentation is clear on this point.

phosek accepted this revision.Sep 19 2023, 3:04 PM

LGTM

llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h
418

Nit: This name doesn't follow LLVM naming conventions.

This revision was landed with ongoing or failed builds.Sep 20 2023, 1:33 PM
This revision was automatically updated to reflect the committed changes.
MaskRay reopened this revision.Sep 20 2023, 2:45 PM
This revision is now accepted and ready to land.Sep 20 2023, 2:45 PM
MaskRay requested changes to this revision.Sep 20 2023, 2:47 PM
MaskRay added a subscriber: MaskRay.

Please, when landing a large patch, check whether clang can build the project. The original commit caused -Wswitch failure which I fixed in ca22d6e40508f6d24a9352835bda9c152e3eee1b.

When reverting a patch, run the test as well. ninja clang did not build due to ca22d6e40508f6d24a9352835bda9c152e3eee1b not being part of the revert.

This revision now requires changes to proceed.Sep 20 2023, 2:47 PM

Please, when landing a large patch, check whether clang can build the project. The original commit caused -Wswitch failure which I fixed in ca22d6e40508f6d24a9352835bda9c152e3eee1b.

When reverting a patch, run the test as well. ninja clang did not build due to ca22d6e40508f6d24a9352835bda9c152e3eee1b not being part of the revert.

Yes, thanks -- I did build my changes prior to landing them, but I did not see the -Wswitch failure until it landed, not sure why. These changes are actually addressed in the successive commit, which I will now apply here. I reverted due to test failures on windows and did not see your commit to address the -Wswitch failure.

Eliminated -Wswitch build issues in CoverageMappingGen.cpp. The actual code for this originally ended up in D138849 after I split up the patches, but it should've been included in this one.

Fixed windows test failures, which were due to relative coverage compilation path inconsistencies in the generated object files used in the test cases. I addressed this by using -fcoverage-compilation-dir and verified the tests now pass on windows, linux, and mac.

Also rebased.

@phosek @paquette buildbot issues have been addressed -- could you reapprove? Thanks!

alanphipps marked an inline comment as done.Nov 1 2023, 8:18 AM

Thanks @MaskRay I've addressed the build issues and buildbot failures encountered with the previous attempt to land this. Can you re-approve?

MaskRay added inline comments.Nov 5 2023, 10:40 AM
llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h
37

This is an uncommon include in LLVM. We usually use format, formatv, etc.

llvm/tools/llvm-cov/CoverageSummaryInfo.cpp
47
50
MaskRay added inline comments.Nov 5 2023, 10:42 AM
llvm/test/tools/llvm-cov/mcdc-const.test
73

Prefer -NEXT for adjacent lines

llvm/tools/llvm-cov/SourceCoverageViewHTML.cpp
741
paquette added inline comments.Nov 5 2023, 6:50 PM
llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h
244

Would it make sense to drop "(MC/DC only)" on this and other member vars in this class?

372

Can you put a doxygen comment on this explaining what each of the members are?

403

I think this comment should be changed into a Doxygen comment that explains what this function is doing to TestVectorIndex and Condition.

408

Could use a doxygen comment here

414

doxygen

424

doxygen

435

Would it be valid for getNumConditions to ever be 0? Would it make sense to add an assert somewhere if it doesn't make sense?

493

might as well pull this into a variable instead of calling it here and in the loop

const auto NumConditions = getNumConditions();
llvm/lib/ProfileData/Coverage/CoverageMapping.cpp
297

simple explanation in doxygen comment?

306

this should be a doxygen comment imo

316

doxygenify

llvm/tools/llvm-cov/CodeCoverage.cpp
373

can reduce indentation here

if (ViewMCDCRecords.empty())
  return;
auto ...
llvm/tools/llvm-cov/CoverageSummaryInfo.h
145

might as well say this is MC/DC here

148

init to 0?

151

init to 0?

MaskRay added inline comments.Nov 10 2023, 10:47 AM
llvm/test/tools/llvm-cov/mcdc-const.test
39

I am also concerned of prebuilt relocatable object files checked into the repository.
They are target-specific, opaque, and difficult to update.

I am well aware of https://maskray.me/blog/2021-08-08-toolchain-testing#the-test-checks-at-the-wrong-layer
but in this case perhaps we should use compiler-rt/test/profile

alanphipps marked 21 inline comments as done.

Rebase and update based on recent review comments.

llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h
37

I get that it's uncommon, though there appears to be some precedent, plus it's very useful. The Coding Standards seem to suggest <sstream> is OK (just not <iostream>).

435

Yep, added an assertion inside getNumConditions() itself.

llvm/test/tools/llvm-cov/mcdc-const.test
39

Ah I see -- you're suggesting using compiler-rt/test/profile so that object files can be generated directly as input to these tools. I think that's a good idea. I'd like to address that in a subsequent PR since this particular patch doesn't include the changes that enable MC/DC in clang.

I understand the concern about adding prebuilt object files to the repo. However, I really like the testing granularity it provides. I've added the steps to reproduce them. But if there is a strong desire, perhaps I can remove them in the subsequent PR and keep them in our downstream repo only (where it's easier to test our baremetal toolchain).

llvm/tools/llvm-cov/CoverageSummaryInfo.h
148

The pattern across all of the *Info classes in this file appears to be to set the member vars on construction. I'm OK with changing it if it's important.

Ping @MaskRay @paquette -- thanks for your help! As this review is now over a year old, I'd like to get it merged soon.

MaskRay accepted this revision.Dec 11 2023, 7:22 PM

LGTM.

llvm/include/llvm/ProfileData/Coverage/CoverageMapping.h
474

const { ?

llvm/lib/ProfileData/Coverage/CoverageMapping.cpp
332

For booleans, if (!((a ^ b) == 1) looks strange. Just use if (a != b)

339

llvm style prefers pre-increment

371

delete blank line immediately after openning a scope.

This revision is now accepted and ready to land.Dec 11 2023, 7:22 PM
paquette accepted this revision.Dec 12 2023, 5:52 PM

LGTM after you address @MaskRay's comments.

This revision was landed with ongoing or failed builds.Dec 13 2023, 1:10 PM
This revision was automatically updated to reflect the committed changes.
alanphipps marked 4 inline comments as done.
Herald added a project: Restricted Project. · View Herald TranscriptDec 13 2023, 1:10 PM
Herald added a subscriber: cfe-commits. · View Herald Transcript