[RFC][Coverage] New algorithm and file format for MC/DC

LLVM Project
1

Alan Phipps @evodius96 has introduced MC/DC Code Coverage in Clang/LLVM. Thanks for the great work.

It has a limitation of “The maximum number of conditions is 6”. I have designed to work for more than 6, possibly hundreds of conditions. The limitation will come from the number of possible test vectors.

Design abstract

Clang emits executed test vectors as bitmap. It is smaller than the combination of all combinations. For example:

((n1 && n4) || (n3 && n5) || (n2 && n6))

In the current implementation, this has 6 conditions and uses 64 (1 << 6) bits of bitmap for possible combinations as executed test vectors. The number of possibly executed test vector is 15 in this case. The bitmap will be sparse (15/64) even if all possible combinations are executed.

I will introduce the design to emit possible test vectors. Of course in this case, the length of bitmap is 15.

Design involved

The decision graph represents the expression above. Each quadrangle node is a condition. Each circular node is the final decision.

graphviz (1)

w in each decision is the number of possible paths. The sum of each w is 15. in in each node is the number of incomings. Each w can be calculated with the sum of incoming w(s).

idx in each edge is assigned based on the number of incomings and each w in precedent nodes.

  • n3 (w=[n1:w:1, n4:w:1])
    • 1st edge (n1->n3)
      • idx is 0.
      • The next number of idx is 1 by adding n1:w.
    • 2nd edge (n4->n3)
      • idx is 1.
      • The next number of idx is 2 by adding n4:w. It should be equivalent to n3:w:2.
  • n2 (w=[n3:w:2, n5:w:2])
    • 1st edge (n3->n2)
      • idx is 0.
      • The next number of idx is 2 by adding n3:w.
    • 2nd edge (n5->n2)
      • idx is 2.
      • The next number of idx is 4 by adding n5:w. It should be equivalent to n2:w:4.

Each idx in decisions should be assigned identically. I am sorting nodes ORDER BY w DESC, NodeID.

  • F2:idx=0
  • F6:idx=4
  • T6:idx=8
  • T5:idx=12
  • T4:idx=14

Indexes should be deterministic between Clang and llvm-cov.

Clang CodeGen

The initial value of the accumulator %acc is 0. the accumulator is increased conditionally by its condition.

%idx = select %cond,TrueIdx,FalseIdx
%acc = add %acc,%idx
br %cond,%TrueLabel,%FalseLabel

The final value of %acc is the ID of the test vector.

LLVMCoverage (llvm-cov)

The ID of the test vector can be calculated with idx in each node in CoverageMapping.cpp:buildTestVector().

Other minor implementations

I will propose Bitmap as not byte-aligned but packed. I have committed the preparation.

In the case above, final decisions with w=1 is identical and will be equivalent of the branch count of the final condition. We could reduce Bitmap little a bit. This is effective for expressions with a sequence of a single operator, like (a0 && a1 && ... && a999).

Format compatibility

This design requires the change of file format. I wonder what could be compatible.

  • llvm-cov (*.profdata) – Easy to read and merge the previous format.
  • Clang’s emission %.o %.s %.bc %.ll – I guess they would require the previous version (18.x) of clang toolchain. Maybe unsupported?

Efforts

I have tried this to the LLVM tree. A few expressions are tough. Fine almost!

  1. clang-tidy/MisleadingIdentifier.cpp was impossible due to billions of test vectors!
  2. LLVMAnalysis::ConstantFolding.cpp has 45931 of test vectors.
  3. X86OptimizeLEAs.cpp has 6561 of test vectors.

Thank you.

2 Likes
2

I have pushed LLVM part of this.

FYI, Fangrui Song @MaskRay wrote a good sumary of MC/DC Coverage. Let me introduce it.

3

Thank you @chapuni!

I will introduce the design to emit possible test vectors.

So, conceptually this yields a compact storage of bitmap data than what I implemented – limiting the bitmap to the number of possible test vectors only rather than a bitmap that becomes more sparse as the number of conditions increases. It looks like your design simply maps the test vector to a 2nd-level index that llvm-cov also does. I think that’s a good improvement to optimize the space.

I sought a design that minimized instrumentation in order to target more typical MC/DC use cases – expressions with low numbers of conditions – particularly with our downstream embedded toolchain. It doesn’t look like your extension radically impacts this.

I have tried this to the LLVM tree. A few expressions are tough. Fine almost!

It looks like the time complexity of the consumer side (llvm-cov) to calculate independence pairs is still high for large numbers of conditions. I suspected this was the bigger concern for those care about large numbers of conditions on expressions.

I will propose Bitmap as not byte-aligned but packed.

Are you proposing to have DecisionRegion reference a bit index rather than a byte index? It makes sense that all decisions within a function will be packed. I think I’m OK with this as long as the individual function subsections __llvm_prf_bits are byte aligned.

Future thoughts
Over time, I would like to understand more about the different upstream use cases that people care about when using MC/DC. If increasing numbers of conditions really is broadly important, it might be better to introduce a new (non-embedded-tuned) mode that instruments the independence pair calculation, along the lines of other proposed designs and reduces the time complexity in llvm-cov and the memory overhead. This would involve balancing trade-offs to optimize for different use cases.

-Alan

1 Like
4

@jkv

5

Hello @evodius96 Thanks for the comment!

It doesn’t look like your extension radically impacts this.

I am certain my impl is more efficient in both instrumented code and profdata.
Practically, it emits at most one add for each edge. Nothing is added if the edge is idx=+0. Using select is just a cheat for minimalizing change of clangCodeGen.

I think we could reintroduce the option “maximum conds”. I guess some restricted coding rules would be there.

By the way, for concerns about memory footprint, Could we implement boolean values for the branch coverage? I guess my TestVectorIdx would help.

It looks like the time complexity of the consumer side (llvm-cov) to calculate independence pairs is still high for large numbers of conditions.

It was out of scope for me for now. Yes, we should improve it. My improvement will discover additional issues.

Are you proposing to have DecisionRegion reference a bit index rather than a byte index?

Yes. Of course I am aware of subsections. It’d be so difficult for llvm-profdata merge to extract and repack bitmaps.
Let me explain more elaborated.
Let Decision.BitmapIdx have “the tail position in the bitmap”. The addressing uses negative indices. This simplifies the implementation, since the length of TestVectors cannot be calculated without traversing MCDCBranches.
As a trivia, getMaxBitmapSize() can be simplified just to scan max(BitmapIdx).

Future thoughts

We could have other options for instrumentation. In fact, IIUC, MC/DC doesn’t require “All executed test vectors”. However I guess my impl would satisfy most cases.

For now, I have to implement the warning for the maxmum test vectors.

Thank you.

6

I have pushed the draft. It should work (except for tests).

7

Landed. Thanks.

I expect this will discover more issues in coverage.
Have fun!

1 Like