[PATCH] Add condition coverage profiling

["Jørgen Kvalsvik" <jorgen.kvalsvik@woven-planet.global>]

Hello, and thanks for the review!

> 1) Do I correctly understand that __conditions_accu_true/false track
> every short-circuit sub-expression of a condition and record
> if a given sub-expr is seen to be true or false?

Sort-of. It is not really aware of sub-expressions at all, but tracks every
boolean condition/term in the full expression, mapped to a bitvector. I usually
find it easier to understand visually:

if (a || (b && c) || d)

terms | a b c d
------|--------
true  | 0 0 0 0
false | 0 0 0 0

Whenever a = true, true becomes 1000 and false remains 0000. a = true would
short-circuit, (implemented as a normal edge to the "exit" node of the
expression) leaving bcd unevaluated. Coverage is then determined as the number
of unset bits in this vector. The accumulators are zero'd on every function
entry, and |= into the global "counter" on function exit.

> 2) As mentioned these are bit sets, can you please explain why you (&
> -value) from these sets?

Yes, excellent question. This should answer 3) too, and is the most surprsing
thing when unfamiliar with MC/DC.

For modified condition/decision coverage we need to prove that a condition's
value independently affects the outcome/decision. In other words, would
flipping a condition change the outcome?

Let's take your if (a || b) check, which says that 1/4 conditions are covered
on (0, 1). If a = 1, the expression is always true, and b is never evaluated.
In fact, the value of b does not change the outcome at all, so intuitively only
1/4 of the conditions are covered.

On (0, 1) b gets evaluated, so in a way we know that a = 0. However, the value
of a will no longer affect the outcome because (* || 1) is always true. In a
way, you can think of it as reverse short-circuiting, the same thing would
happen on (* && 0). This is what Wahlen, Heimdahl, and De Silva calls masking.
What I do is figure out when masking must happen by analyzing the CFG and zero
out the bits that are masked (i.e. no longer affect the outcome). This is in
practice what happens to the bits when regular short circuiting happen.

So while (0, 1) "sees" the condition a = false, it cannot prove that it
mattered based on your inputs. In general, you need N+1 test cases to cover N
conditionals with MC/DC. As a consequence, the only way of covering a = false
is (0, 0), which alone would be 2/4 cases covered.

I hope this made it clearer, if not I can write a more elaborate explanation
with more examples.

> 4) I noticed various CFG patterns in tree-profile.cc which are handled. Can
> you please explain how the algorithm works even without knowing the original
> paper?

My paper is not written yet, but I will describe the high-level algorithm (+
extracts from source comments) at the end of this email, as it is a bit long.

> 5) I noticed the following ICE:
Yes, this is an unfortunate flaw - I piggyback on the setup done by branch
coverage, which means I silently assume --coverage is used. I was unsure what
to do (and meant to ask, sorry!) as it is a larger decision - should
condition-coverage also imply branch coverage? Should condition coverage work
on its own? Other options?

I'm happy to implement either strategy - please advise on what you would
prefer.


> 6) Please follow the GNU coding style, most notable we replace 8 spaces with 
> a tab. And we break line before {, (, ... Remove noexcept specifiers for 
> functions and I think most of the newly added functions can be static. And 
> each newly added function should have a comment.

Sure thing, I'll add some tabs. All the helper functions are already static (in
an unnamed namespace), but I can remove the namespace and/or add static.

> 7) Please consider supporting of -profile-update=atomic where you'll need to
> utilize an atomic builts (see how other instrumentation looks like with
> it).
Will do! I always intended to support the atomics, not having them there is an
oversight. To confirm, I will only need to use atomics for the global counters,
right? The per-call accumulators are local to each activation record and should
not need the atomics, or am I missing something?

ALGORITHM

Phase 1: expression isolation from CFG analysis

Break the CFG into smaller pieces ("sections") by splitting it on dominators.
No expression can cross a dominator, so becomes a natural way of terminating
expression searches.

For each section, do a BFS from the root node and collect all reachable nodes
following edges that point to "conditional" nodes, i.e. nodes with outgoing
true&false edges. Series of single-parent single-exit nodes are contracted.
This gives a good estimate for an expression, but might include conditions in
the if/else blocks.

The algorithm then collects the immediate neighborhood, i.e. all nodes adjacent
to the collected set, dropping everything in the set itself. Then, a new BFS is
performed, but now "upwards" (i.e. following predecessors), skipping any
neighbor not dominated by the root (this eliminates loops and other expressions
with the same "exit" block, see BFS-up). The intersection of all the paths
found with this BFS is the isolated expression.

If the root is not a conditional, it is skipped and it's successor
becomes the new root. If an expression is found it has a pair of "expression
sucessors", and the algorithm recurses into both, evaluating this sub-section
in isolation, i.e.

if (a || b) {
root:
    if (c && d) {
        ...
    }
    ...
sink:
}

The sections between the root and sink labels are evaulated as if the outer
expression did not exist.

From the comments:

    1. Collect all nodes reachable from the root node through (contracted) paths
       of true/false edges.
    2. Collect the neighbors of the reachable node (set).
    3. From every node in the neighborhood, walk the up the CFG and mark every
       reachable node. Only the nodes reachable from *every* node in the
       neighborhood are a part of the first expression.
    4. Record the expression plus the two successors of the last (highest-index)
       node in the expression, i.e. the last term.
    5. Repeat using the two successors as new root nodes.

    It is not guaranteed to find nodes in the order of the expression, i.e. it
    might find (a || b) && c as [a c b], so the output is sorted by
    basic_block->index.

    Steps 2 and 3 are necessary to distinguish chained conditionals from
    multi-term conditionals, e.g. to separate

        if (a)
        {
            if (b)
                work ();
        }
        if (a && b)
            work ();


On BFS-up:

    Either block of a conditional could have more decisions and loops, so
    isolate the first decision by set-intersecting all paths from the
    post-dominator to the entry block.

    The function returns the number of blocks from n that make up the leading
    expression in prefix order (i.e. the order expected by the instrumenting
    code).  When this function returns 0 there are no decisions between pre and
    post, and this segment of the CFG can safely be skipped.

    The post nodes can have predecessors that do not belong to this subgraph,
    which are skipped.  This is expected, for example when there is a
    conditional in the else-block of a larger expression:

    if (A)
    {
       if (B) {}
    } else {
       if (C) {} else {}
    }

             A
          t / \ f
           /   \
          B     C
         /\    / \
        /  \  T   F
       T    \  \ /
        \   |   o
         \  |  /
          \ | /
           \|/
            E

    Processing [B, E) which looks like:

       B
      /|
     / |
    T  |
     \ /
      E ----> o // predecessor outside [B, e)


Phase 2: Masking vector and instrumentation

The input to this phase is the basic blocks that make up every expression, plus
its two exit nodes, i.e. the 3-term expression (a || b || c) yields the input
[a b c T F] to phase 2.

For every expression, allocate two local accumulators (bit-vectors), one for
the true-vector, one for the false-vector. These are zero'd on function entry
and flushed on function exit.

For each "conditional" block (a b c), unconditionally set the corresponding bit
when an edge in the CFG is taken. Rough pseudo-gimple illustration:

if (a) {
    accu_true |= 1 << 0
    goto done;
} else {
    accu_false |= 1 << 0
    if (b) {
        accu_true |= 1 << 1;
        goto done;
    } else {
        accu_false |= 1 << 1;
        ...
    }
}

global_true[expr_n]  |= accu_true
global_false[expr_n] |= accu_false

This alone would more-or-less be branch coverage, but would not prove that
terms would independently decide the outcome. To find masking, the expression
is walked in search of triangles. A || B as a decision diagram becomes

   A
  t|\f
   | \
   |  B
   |t/ \f
   |/   \
   T     F

and we search for triangles like ATB, that is nodes with 2 predecessors with
the same boolean value, where the two predecessors are connected with the
opposite value. This marks a candidate for masking, and the terms masked are
determined by chasing predecessors starting at the top of the triangle for as
long as the chain of predecessors have the same truth value as the "exit"
edges. This set is often empty.

The edge that triggers masking is then instrumented with a accu &= mask which
wipes out anything that does not independently affect the outcome. Note that
nothing is ever wiped from the global accumulator, only the local. The (a || b)
example had a false vector of [1, 0] at some point, but it was wiped by the
masking operation (b = 1 is the only masking value for a || b).

From the comments:

    Scan the blocks that make up an expression and look for conditions that
    would mask other conditions.  For a deeper discussion on masking, see
    Whalen, Heimdahl, De Silva "Efficient Test Coverage Measurement for MC/DC".
    Masking is best illustrated with an example:

    A || B.  If B is true then A will does not independently affect the
    decision.  In a way, this is "reverse" short circuiting, and always work on
    the right-hand side of expressions.  * || true is always true and * &&
    false is always false - the left-hand-side does not affect the outcome, and
    their values should not contribute to modified condition/decision coverage.

    A || B interpreted as a decision diagram becomes:

     A
    t|\f
     | \
     |  B
     |t/ \f
     |/   \
     T     F

    The algorithm looks for triangles like ATB.  Masking right-hand sides happen
    when a block has a pair of incoming edges of the same boolean value, and
    there is an edge connecting the two predecessors with the *opposite* boolean
    value.  The masking block is B, and the masked block is A.  In this
    particular example:

    Masking can affect "outside" its own subexpression; in A || (B && C) if C is
    false, B is masked.  However, if (B && C) is true, A gets masked.  B && C
    can be determined from evaluating C since !B would short-circuit, so a true
    C would mask A.

     A
    t|\f
     | \
     |  \
     |   \
     |    B
     |  t/ \f
     |  C   |
     |t/ \f |
     |/   \ |
     T     F

    Notice how BFC forms a triangle.  Expressions masked by an edge are
    determined by:
    * Go to the predecessor with truth value b (if it exists).
    * Follow the path of ancestors with taking only !b edges, recording every
      node from here on.

    For the case where C can mask A, the path goes C [true]-> B -> [false] A, so
    C [true] masks A.

    The mask is output as a bit-set stored in a gcov_type_unsigned.  The
    bit-sets are output in pairs, one for each decision (the outcome of the
    boolean expression, or which arc to take in the CFG).

Phase 3: reading the report

This is pretty standard gcov stuff, except the "counters" are interpreted as
bitsets, and the number of terms in the expressions is stored. Coverage then
becomes popcount / expected.

Final remarks:

Granted, this is a bit dense, but I think the overall approach is easy to grasp
when supported by a lot of example graphs and stepping. I will try to type up a
bunch with the paper and publish, but for now all I have is the code (which I
hope for the most part is easy to follow). I'll update this with style updates
and atomics support, but I would prefer a maintainer to make the call if this
condition coverage should imply branch coverage, or if it should work without it.

Thanks,
Jørgen

On 24/03/2022 17:08, Martin Liška via Gcc-patches wrote:
> On 3/21/22 12:55, Jørgen Kvalsvik via Gcc-patches wrote:
> 
> Hello.
> 
> Thanks for very interesting extension of the existing GCOV profiling.
> 
> I briefly read the patch and investigated what happens and I've got various
> questions/comments about it:
> 
> 1) Do I correctly understand that __conditions_accu_true/false track
> every short-circuit sub-expression of a condition and record
> if a given sub-expr is seen to be true or false?
> 
> 2) As mentioned these are bit sets, can you please explain why you (& -value)
> from these sets?
> 
> 3) I noticed a false report for a simple test-case:
> 
> $ cat cond.c
> int x;
> 
> void foo (int a, int b)
> {
>      if (a || b)
>        x = 1;
>      else
>        x = 2;
> }
> 
> int main()
> {
>    foo (0, 1);
>    return 0;
> }
> 
> $ rm *gcda ; gcc --coverage cond.c -fprofile-conditions && ./a.out && gcov -g -t a-cond.c
>          -:    0:Source:cond.c
>          -:    0:Graph:a-cond.gcno
>          -:    0:Data:a-cond.gcda
>          -:    0:Runs:1
>          -:    1:int x;
>          -:    2:
>          1:    3:void foo (int a, int b)
>          -:    4:{
>          1:    5:    if (a || b)
> conditions covered 1/4
> condition  0 not covered (true)
> condition  0 not covered (false) <-- this was executed if I'm correct
> condition  1 not covered (false)
>          1:    6:      x = 1;
>          -:    7:    else
>      #####:    8:      x = 2;
>          1:    9:}
>          -:   10:
>          1:   11:int main()
>          -:   12:{
>          1:   13:  foo (0, 1);
>          1:   14:  return 0;
>          -:   15:}
> 
> 4) I noticed various CFG patterns in tree-profile.cc which are handled. Can you please
> explain how the algorithm works even without knowing the original paper?
> 
> 5) I noticed the following ICE:
> 
> $ gcc cond.c -fprofile-conditions -fprofile-generate
> during IPA pass: profile
> cond.c: In function ?foo?:
> cond.c:15:1: internal compiler error: Segmentation fault
>     15 | }
>        | ^
> 0xf4d64a crash_signal
> 	/home/marxin/Programming/gcc/gcc/toplev.cc:322
> 0x7ffff78b93cf ???
> 	/usr/src/debug/glibc-2.35-2.1.x86_64/signal/../sysdeps/unix/sysv/linux/x86_64/libc_sigaction.c:0
> 0x7ffff78f29ed __GI__IO_ftell
> 	/usr/src/debug/glibc-2.35-2.1.x86_64/libio/ioftell.c:37
> 0xa9dfda gcov_position
> 	/home/marxin/Programming/gcc/gcc/gcov-io.cc:48
> 0xa9dfda gcov_write_tag(unsigned int)
> 	/home/marxin/Programming/gcc/gcc/gcov-io.cc:321
> 0xe9734a branch_prob(bool)
> 	/home/marxin/Programming/gcc/gcc/profile.cc:1542
> 0x1032e08 tree_profiling
> 	/home/marxin/Programming/gcc/gcc/tree-profile.cc:1620
> 0x1032e08 execute
> 	/home/marxin/Programming/gcc/gcc/tree-profile.cc:1726
> Please submit a full bug report, with preprocessed source (by using -freport-bug).
> Please include the complete backtrace with any bug report.
> See <https://gcc.gnu.org/bugs/> for instructions.
> 
> 6) Please follow the GNU coding style, most notable we replace 8 spaces with a tab.
> And we break line before {, (, ... Remove noexcept specifiers for functions and I think
> most of the newly added functions can be static. And each newly added function should
> have a comment.
> 
> 7) Please consider supporting of -profile-update=atomic where you'll need to utilize
> an atomic builts (see how other instrumentation looks like with it).
> 
> That's the very first round of the review. Hope it's helpful.
> 
> Cheers,
> Martin
> 
>> This patch adds support in gcc+gcov for modified condition/decision
>> coverage (MC/DC) with the -fprofile-conditions flag. MC/DC is a type of
>> test/code coverage, and it is particularly important in the avation and
>> automotive industries for safety-critical applications. In particular,
>> it is required or recommended by:
>>
>>      * DO-178C for the most critical software (Level A) in avionics
>>      * IEC 61508 for SIL 4
>>      * ISO 26262-6 for ASIL D
>>
>>  From the SQLite webpage:
>>
>>      Two methods of measuring test coverage were described above:
>>      "statement" and "branch" coverage. There are many other test
>>      coverage metrics besides these two. Another popular metric is
>>      "Modified Condition/Decision Coverage" or MC/DC. Wikipedia defines
>>      MC/DC as follows:
>>
>>          * Each decision tries every possible outcome.
>>          * Each condition in a decision takes on every possible outcome.
>>          * Each entry and exit point is invoked.
>>          * Each condition in a decision is shown to independently affect
>>            the outcome of the decision.
>>
>>      In the C programming language where && and || are "short-circuit"
>>      operators, MC/DC and branch coverage are very nearly the same thing.
>>      The primary difference is in boolean vector tests. One can test for
>>      any of several bits in bit-vector and still obtain 100% branch test
>>      coverage even though the second element of MC/DC - the requirement
>>      that each condition in a decision take on every possible outcome -
>>      might not be satisfied.
>>
>>      https://sqlite.org/testing.html#mcdc
>>
>> Wahlen, Heimdahl, and De Silva "Efficient Test Coverage Measurement for
>> MC/DC" describes an algorithm for adding instrumentation by carrying
>> over information from the AST, but my algorithm does analysis on the
>> control flow graph. This should make it work for any language gcc
>> supports, although I have only tested it on constructs in C and C++, see
>> testsuite/gcc.misc-tests and testsuite/g++.dg.
>>
>> Like Wahlen et al this implementation uses bitsets to store conditions,
>> which gcov later interprets. This is very fast, but introduces an max
>> limit for the number of terms in a single boolean expression. This limit
>> is the number of bits in a gcov_unsigned_type (which is typedef'd to
>> uint64_t), so for most practical purposes this would be acceptable.
>> limitation can be relaxed with a more sophisticated way of storing and
>> updating bitsets (for example length-encoding).
>>
>> In action it looks pretty similar to the branch coverage. The -g short
>> opt carries no significance, but was chosen because it was an available
>> option with the upper-case free too.
>>
>> gcov --conditions:
>>
>>          3:   17:void fn (int a, int b, int c, int d) {
>>          3:   18:    if ((a && (b || c)) && d)
>> conditions covered 5/8
>> condition  1 not covered (false)
>> condition  2 not covered (true)
>> condition  2 not covered (false)
>>          1:   19:        x = 1;
>>          -:   20:    else
>>          2:   21:        x = 2;
>>          3:   22:}
>>
>> gcov --conditions --json-format:
>>
>>      "conditions": [
>>          {
>>              "not_covered_false": [
>>                  1,
>>                  2
>>              ],
>>              "count": 8,
>>              "covered": 5,
>>              "not_covered_true": [
>>                  2
>>              ]
>>          }
>>      ],
>>
>> C++ destructors will add extra conditionals that are not explicitly
>> present in source code. These are present in the CFG, which means the
>> condition coverage will show them.
>>
>> gcov --conditions
>>
>>          -:    5:struct A {
>>          1:    6:    explicit A (int x) : v (x) {}
>>          1:    7:    operator bool () const { return bool(v); }
>>          1:    8:    ~A() {}
>>          -:    9:
>>          -:   10:    int v;
>>          -:   11:};
>>          -:   12:
>>          2:   13:void fn (int a, int b) {
>>         2*:   14:    x = a && A(b);
>> conditions covered 2/4
>> condition  0 not covered (true)
>> condition  1 not covered (true)
>> conditions covered 2/2
>>
>> They are also reported by the branch coverage.
>>
>> gcov -bc
>>
>>         2*:   14:    x = a && A(b);
>> branch  0 taken 1 (fallthrough)
>> branch  1 taken 1
>> call    2 returned 1
>> call    3 returned 1
>> branch  4 taken 0 (fallthrough)
>> branch  5 taken 1
>> branch  6 taken 1 (fallthrough)
>> branch  7 taken 1
>>
>> The algorithm struggles in a particular case where gcc would generate
>> identical CFGs for different expressions:
>>
>> and.c:
>>
>>      if (a && b && c)
>>          x = 1;
>>
>> ifs.c:
>>
>>      if (a)
>>          if (b)
>>              if (c)
>>                  x = 1;
>>
>>      if (a && b && c)
>>          x = 1;
>>
>> and.c.gcov:
>>
>>              #####:    2:    if (a && b && c)
>> conditions covered 2/2
>> conditions covered 2/2
>> conditions covered 2/2
>>      #####:    3:        x = 1;
>>
>> ifs.c.gcov:
>>      #####:    2:    if (a)
>> conditions covered 2/2
>>      #####:    3:   2    if (b)
>> conditions covered 2/2
>>      #####:    4:   2        if (c)
>> conditions covered 2/2
>>      #####:    5:                x = 1;
>>
>> These programs are semantically equivalent, and are interpreted as 3
>> separate conditional expressions. It does not matter w.r.t. coverage,
>> but is not ideal. Adding an else to and.c fixes the issue:
>>
>>      #####:    2:    if (a && b && c)
>> conditions covered 6/6
>>      #####:    3:        x = 1;
>>      #####:    4:    else x = x;
>>
>> In the (a && b && c) case the else block must be shared between all
>> three conditionals, and for if (a) if (b) if (c) there would be three
>> *separate* else blocks.
>>
>> Since the algorithm works on CFGs, it cannot detect conditionals (from
>> ternaries) that don't get an entry in the cfg. For example,
>> int x = a ? 0 : 1 in gimple becomes _x = (_a == 0). From source you
>> would expect coverage, but it gets neither branch nor condition
>> coverage. For completeness, it could be achieved by scanning all gimple
>> statements for comparisons, and insert an extra instruction for
>> recording the outcome.
>>
>> The test suite consists of all different CFG kinds and control flow
>> structures I could find, but there is certainly room for many more.
>>
>> Alternative email: J?rgen Kvalsvik <j@lambda.is>
>>
>> --
>>
>> Some final remarks (not a part of the commit message), this is written in a C++ style that I felt meshed well with what was already there, but if the maintainers would prefer a different approach then I'm happy to to make adjustments. I plan to write a more thorough description of the algorithm, as well as adding the same feature to clang as it is very useful for us at Woven Planet.
>>
>> I tried to pick flag names and options that were comfortable and descriptive, but if you have better names or different ideas for flags then I am happy to change them. The --coverage flag was not changed to imply -fprofile-conditions, but it is possibly something to consider.
>>
>> gcc/ChangeLog:
>>
>> 	* common.opt: Add new options -fprofile-conditions and
>> 	-Wcoverage-too-many-conditions.
>> 	* doc/gcov.texi: Add --conditions documentation.
>> 	* doc/invoke.texi: Add -fprofile-conditions documentation.
>> 	* gcov-counter.def (GCOV_COUNTER_CONDS): New.
>> 	* gcov-io.h (GCOV_TAG_CONDS): New.
>> 	(GCOV_TAG_CONDS_LENGTH): Likewise.
>> 	(GCOV_TAG_CONDS_NUM): Likewise.
>> 	* gcov.cc (class condition_info): New.
>> 	(condition_info::condition_info): New.
>> 	(condition_info::popcount): New.
>> 	(struct coverage_info): New.
>> 	(add_condition_counts): New.
>> 	(output_conditions): New.
>> 	(print_usage): Add -g, --conditions.
>> 	(process_args): Likewise.
>> 	(output_intermediate_json_line): Output conditions.
>> 	(read_graph_file): Read conditions counters.
>> 	(read_count_file): Read conditions counters.
>> 	(file_summary): Print conditions.
>> 	(accumulate_line_info): Accumulate conditions.
>> 	(output_line_details): Print conditions.
>> 	* profile.cc (find_conditions): New declaration.
>> 	(instrument_decisions): New declaration.
>> 	(branch_prob): Call find_conditions, instrument_decisions.
>> 	(init_branch_prob): Add total_num_conds.
>> 	(end_branch_prob): Likewise.
>> 	* tree-profile.cc (INCLUDE_ALGORITHM): Define.
>> 	(struct conds_ctx): New.
>> 	(CONDITIONS_MAX_TERMS): New.
>> 	(index_of): New.
>> 	(index_lt): New.
>> 	(single): New.
>> 	(single_edge): New.
>> 	(contract_edge): New.
>> 	(contract_edge_up): New.
>> 	(is_conditional_p): New.
>> 	(collect_neighbors): New.
>> 	(find_first_conditional): New.
>> 	(emit_bitwise_op): New.
>> 	(collect_conditions): New.
>> 	(find_conditions): New.
>> 	(instrument_decisions): New.
>>
>> gcc/testsuite/ChangeLog:
>>
>> 	* lib/gcov.exp:
>> 	* g++.dg/gcov/gcov-18.C: New test.
>> 	* gcc.misc-tests/gcov-19.c: New test.
>> ---
>>   gcc/common.opt                         |   8 +
>>   gcc/doc/gcov.texi                      |  36 ++
>>   gcc/doc/invoke.texi                    |  19 +
>>   gcc/gcov-counter.def                   |   3 +
>>   gcc/gcov-io.h                          |   3 +
>>   gcc/gcov.cc                            | 177 +++++-
>>   gcc/profile.cc                         |  51 +-
>>   gcc/testsuite/g++.dg/gcov/gcov-18.C    | 209 ++++++
>>   gcc/testsuite/gcc.misc-tests/gcov-19.c | 726 +++++++++++++++++++++
>>   gcc/testsuite/lib/gcov.exp             | 187 +++++-
>>   gcc/tree-profile.cc                    | 838 +++++++++++++++++++++++++
>>   11 files changed, 2248 insertions(+), 9 deletions(-)
>>   create mode 100644 gcc/testsuite/g++.dg/gcov/gcov-18.C
>>   create mode 100644 gcc/testsuite/gcc.misc-tests/gcov-19.c