Add condition coverage profiling

From: =?UTF-8?q?J=C3=B8rgen=20Kvalsvik?=

  Hello,

I have made some changes based on the review feedback, please have a look. In
summary:

* Support for -profile=atomic
* gcc -fprofile-conditions does not ICE without -fprofile-arcs
* Indentation and formatting complies with contrib/GNU_style_check
* Some small adjustment to documentation, phrasing

As mentioned in the previous message, I think it should only be necessary to do
atomic fetch/store on the global accumulators, not the locals (as they are
specific to the activation record). If is wrong then I have no problems
extending the atomics to the function-local accumulators too, please let me
know. I added a simple test case for -profile=update, gcov-20.c.

I've added checks for profile_condition_flag everywhere the profile_arc_flag is
checked, as they share the same code paths and infrastructure. I also made it so
that -fprofile-conditions is sufficient for linking gcov.

gcc will no longer crash on -fprofile-conditions -fprofile-generate by
explicitly checking coverage_begin_*. I'm not too happy with how it turned out,
but the condition coverage needs a lot more analysis before it can write out its
gcov structure, which doesn't fit with the flow of branch_prob ().

Thanks,
Jørgen

On 25/03/2022 20:44, Jørgen Kvalsvik wrote:
> 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
>
From 53d404a6e836875d8243ea71c2aeb92115224f98 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=B8rgen=20Kvalsvik?=
 <jorgen.kvalsvik@woven-planet.global>
Date: Mon, 31 Jan 2022 12:49:37 +0100
Subject: [PATCH] Add condition coverage profiling
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

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>

gcc/ChangeLog:

	* builtins.cc (expand_builtin_fork_or_exec): Check
	profile_condition_flag.
	* 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.
	* gcc.cc: Link gcov on -fprofile-conditions.
	* 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.
	* ipa-inline.cc (can_early_inline_edge_p): Check
	profile_condition_flag.
	* ipa-split.cc (pass_split_functions::gate): Likewise.
	* passes.cc (finish_optimization_passes): Likewise.
	* 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.
	(pass_ipa_tree_profile::gate): Check profile_condition_flag.

gcc/testsuite/ChangeLog:

	* lib/gcov.exp: Add condition coverage test function.
	* g++.dg/gcov/gcov-18.C: New test.
	* gcc.misc-tests/gcov-19.c: New test.
	* gcc.misc-tests/gcov-20.c: New test.
---
 gcc/builtins.cc                        |   2 +-
 gcc/common.opt                         |   8 +
 gcc/doc/gcov.texi                      |  36 +
 gcc/doc/invoke.texi                    |  19 +
 gcc/gcc.cc                             |   2 +-
 gcc/gcov-counter.def                   |   3 +
 gcc/gcov-io.h                          |   3 +
 gcc/gcov.cc                            | 193 +++++-
 gcc/ipa-inline.cc                      |   2 +-
 gcc/ipa-split.cc                       |   3 +-
 gcc/passes.cc                          |   3 +-
 gcc/profile.cc                         |  72 +-
 gcc/testsuite/g++.dg/gcov/gcov-18.C    | 227 +++++++
 gcc/testsuite/gcc.misc-tests/gcov-19.c | 727 ++++++++++++++++++++
 gcc/testsuite/gcc.misc-tests/gcov-20.c |  21 +
 gcc/testsuite/lib/gcov.exp             | 187 +++++-
 gcc/tree-profile.cc                    | 883 ++++++++++++++++++++++++-
 17 files changed, 2366 insertions(+), 25 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/gcov/gcov-18.C
 create mode 100644 gcc/testsuite/gcc.misc-tests/gcov-19.c
 create mode 100644 gcc/testsuite/gcc.misc-tests/gcov-20.c

Message ID	8041d06d-219d-c83a-ff8f-9c75227cb072@woven-planet.global
State	New
Headers	Return-Path: <gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org> X-Original-To: patchwork@sourceware.org Delivered-To: patchwork@sourceware.org Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 4B6913857805 for <patchwork@sourceware.org>; Mon, 28 Mar 2022 13:56:04 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 4B6913857805 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1648475764; bh=NxlSon7CChsdSfqGTRJ9G7nKraz9O9sufCq4agvCrFM=; h=Date:Subject:To:References:In-Reply-To:List-Id:List-Unsubscribe: List-Archive:List-Post:List-Help:List-Subscribe:From:Reply-To: From; b=ByuFhgBVJ532VTni8B/o8q72JBe/G09yVvbVP7/0W0YWbN2rFTjyvyMRTNTcmPtYW 3sPPRqf2LpDXoa/AOLYwHx8DjCL185cKvcS2CxtMANeCj1N/O/dMvM+r2xlYwaRwVa vY6GbnfGQmu5achxDaKjjvuJHRdPtRliKUzaA9Y8= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from mail-pj1-x102e.google.com (mail-pj1-x102e.google.com [IPv6:2607:f8b0:4864:20::102e]) by sourceware.org (Postfix) with ESMTPS id 6AF38385782D for <gcc-patches@gcc.gnu.org>; Mon, 28 Mar 2022 13:52:26 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 6AF38385782D Received: by mail-pj1-x102e.google.com with SMTP id p4-20020a17090ad30400b001c7ca87c05bso9996904pju.1 for <gcc-patches@gcc.gnu.org>; Mon, 28 Mar 2022 06:52:26 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:message-id:date:mime-version:user-agent:from :subject:to:cc:references:content-language:in-reply-to; bh=NxlSon7CChsdSfqGTRJ9G7nKraz9O9sufCq4agvCrFM=; b=icntnm0SrLXyqUCzytGRTQ5ispOOCQ5AzT8yFKPNSgKXqPjncZmQp8hwbMyoIqZaIL CpqSz9+9LR+r4U1JOSsK0PBVWmuqNJikJFifeP6MNlgHOVNsnF4gg4DxuUeWo3hp64c1 wndu0plwa5kS8ptiSOeUSDeIE5AvNG9IQirENPAmRo9NBWo4AJN/LSTI/+o2wkZNk3AA /zD6oPMHsBympVXhf0nfRVq3c5hLqA0Vj4j0oF8CcDhl4pkXaFUM6RNKubqMkp2gDFrN 1w1w6BfMpvlasYEsRGmfboNe8KAMburi0TvrzLtfML3dBBznZ4Dw0PEZFb2Ue3vBnRbU XCYA== X-Gm-Message-State: AOAM531HYFBZSt7s5WuuXAO3RTqcYKnQGXCzMaOzE2VZ0AhWlL2Kmcyc 5qxSyPz/F+Mhv0uxmcH9WFCWxBles94g1FdbxJsiqaUKFyY80sY6PRxdHOV49Hoel8r1w9d+a4a Kkk8vGDu26/RTrdjWbFlDWPivi2G4jojDugia/EkMM0Yd55crpcoqWm4KC2up+sz0vQtiQ7PO6H dEP8ikcz3bRBvpLf4tWBc= X-Google-Smtp-Source: ABdhPJyTINtqFJMvvA7CB8eQTqJIDsrnPmoeqQTLMBoa3f9EIUt7GjzOxQh0CUcTrtk3QjfOjXeAcg== X-Received: by 2002:a17:90b:3ec9:b0:1c7:74f6:ae6e with SMTP id rm9-20020a17090b3ec900b001c774f6ae6emr36710518pjb.212.1648475544464; Mon, 28 Mar 2022 06:52:24 -0700 (PDT) Received: from [172.16.185.109] ([103.175.111.222]) by smtp.gmail.com with ESMTPSA id i128-20020a639d86000000b00381f29d87aasm12909452pgd.92.2022.03.28.06.52.21 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 28 Mar 2022 06:52:23 -0700 (PDT) Content-Type: multipart/mixed; boundary="------------DX2gGx7OWgaoz6YgdSKBs14e" Message-ID: <8041d06d-219d-c83a-ff8f-9c75227cb072@woven-planet.global> Date: Mon, 28 Mar 2022 15:52:15 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:91.0) Gecko/20100101 Thunderbird/91.7.0 Subject: [PATCH] Add condition coverage profiling To: gcc-patches@gcc.gnu.org References: <b53507bf-1c1f-d946-00a5-10143fa647b4@woven-planet.global> <fbe1575d-e3be-6c02-332b-5ecc9410467d@suse.cz> <a16e2ac4-10d7-c1c7-e0bc-07ee427de376@woven-planet.global> Content-Language: en-US In-Reply-To: <a16e2ac4-10d7-c1c7-e0bc-07ee427de376@woven-planet.global> X-Spam-Status: No, score=-12.1 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, KAM_SHORT, RCVD_IN_DNSWL_NONE, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE, WEIRD_PORT autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list <gcc-patches.gcc.gnu.org> List-Unsubscribe: <https://gcc.gnu.org/mailman/options/gcc-patches>, <mailto:gcc-patches-request@gcc.gnu.org?subject=unsubscribe> List-Archive: <https://gcc.gnu.org/pipermail/gcc-patches/> List-Post: <mailto:gcc-patches@gcc.gnu.org> List-Help: <mailto:gcc-patches-request@gcc.gnu.org?subject=help> List-Subscribe: <https://gcc.gnu.org/mailman/listinfo/gcc-patches>, <mailto:gcc-patches-request@gcc.gnu.org?subject=subscribe> From: =?utf-8?q?J=C3=B8rgen_Kvalsvik_via_Gcc-patches?= <gcc-patches@gcc.gnu.org> Reply-To: =?utf-8?q?J=C3=B8rgen_Kvalsvik?= <jorgen.kvalsvik@woven-planet.global> Errors-To: gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org Sender: "Gcc-patches" <gcc-patches-bounces+patchwork=sourceware.org@gcc.gnu.org>
Series	Add condition coverage profiling \| Add condition coverage profiling

Add condition coverage profiling

Commit Message

Patch