Re: Ping [PATCH] Add condition coverage profiling
On 11/2/22 07:16, Jørgen Kvalsvik via Gcc-patches wrote: Ping. I would like to see this become a part of gcc 13, will we be able to commit before the window closes? Hello. I'm sorry but I was interrupted by the Sphinx conversion task. Anyway, please update the coding style and I can return to patch review in the upcoming weeks. About the window closure: we still have (basically till the end of year) as stage1 closing period means that all patches should be *under review* until this deadline. And that's true for your patch. Cheers, Martin
[Ping 2][PATCH] Add condition coverage profiling
On 02/11/2022 07:16, Jørgen Kvalsvik wrote:
> On 25/10/2022 08:33, Jørgen Kvalsvik wrote:
>> On 12/10/2022 12:16, Jørgen Kvalsvik wrote:
>>> 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. MC/DC it is
>>> required for 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 analyses the the control
>>> flow graph to instrument for coverage. This has the benefit of being
>>> programming language independent and faithful to compiler decisions
>>> and transformations, 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 records coverage in fixed-size
>>> bitsets which gcov knows how to interpret. This is very fast, but
>>> introduces a limit on the number of terms in a single boolean
>>> expression, 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. This limitation is in the implementation and not the
>>> algorithm, so support for more conditions can be added by also
>>> introducing arbitrary-sized bitsets.
>>>
>>> For space overhead, the instrumentation needs two accumulators
>>> (gcov_unsigned_type) per condition in the program which will be written
>>> to the gcov file. In addition, every function gets a pair of local
>>> accumulators, but these accmulators are reused between conditions in the
>>> same function.
>>>
>>> For time overhead, there is a zeroing of the local accumulators for
>>> every condition and one or two bitwise operation on every edge taken in
>>> the an expression.
>>>
>>> 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)
>>> condition outcomes covered 3/8
>>> condition 0 not covered (true false)
>>> condition 1 not covered (true)
>>> condition 2 not covered (true)
>>> condition 3 not covered (true)
>>> 1: 19:x = 1;
>>> -: 20:else
>>> 2: 21:x = 2;
>>> 3: 22:}
>>>
>>> gcov --conditions --json-format:
>>>
>>> "conditions": [
>>> {
>>> "not_covered_false": [
>>> 0
>>> ],
>>> "count": 8,
>>> "covered": 3,
>>> "not_covered_true": [
>>> 0,
>>> 1,
>>> 2,
>>> 3
>>> ]
>>> }
>>> ],
>>>
>>> Some expressions, mostly those without else-blocks, are effectively
>>> "rewritten" in the CFG construction making the algorithm unable to
>>> distinguish them:
>>>
>>> and.c:
>>>
>>> if (a && b && c)
>>> x = 1;
>>>
>>> ifs.c:
>>>
>>> if (a)
>>> if (b)
>>> if (c)
>>> x = 1;
>>>
>>> gcc will build the same graph for both these programs, and gcov will
>>> report boths as 3-term expressions. It is vital that it is not
>>> interpreted the other way around (which is consistent with the shape of
>>> the graph) because otherwise the masking would be wrong for the and.c
Ping [PATCH] Add condition coverage profiling
On 25/10/2022 08:33, Jørgen Kvalsvik wrote:
> On 12/10/2022 12:16, Jørgen Kvalsvik wrote:
>> 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. MC/DC it is
>> required for 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 analyses the the control
>> flow graph to instrument for coverage. This has the benefit of being
>> programming language independent and faithful to compiler decisions
>> and transformations, 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 records coverage in fixed-size
>> bitsets which gcov knows how to interpret. This is very fast, but
>> introduces a limit on the number of terms in a single boolean
>> expression, 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. This limitation is in the implementation and not the
>> algorithm, so support for more conditions can be added by also
>> introducing arbitrary-sized bitsets.
>>
>> For space overhead, the instrumentation needs two accumulators
>> (gcov_unsigned_type) per condition in the program which will be written
>> to the gcov file. In addition, every function gets a pair of local
>> accumulators, but these accmulators are reused between conditions in the
>> same function.
>>
>> For time overhead, there is a zeroing of the local accumulators for
>> every condition and one or two bitwise operation on every edge taken in
>> the an expression.
>>
>> 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)
>> condition outcomes covered 3/8
>> condition 0 not covered (true false)
>> condition 1 not covered (true)
>> condition 2 not covered (true)
>> condition 3 not covered (true)
>> 1: 19:x = 1;
>> -: 20:else
>> 2: 21:x = 2;
>> 3: 22:}
>>
>> gcov --conditions --json-format:
>>
>> "conditions": [
>> {
>> "not_covered_false": [
>> 0
>> ],
>> "count": 8,
>> "covered": 3,
>> "not_covered_true": [
>> 0,
>> 1,
>> 2,
>> 3
>> ]
>> }
>> ],
>>
>> Some expressions, mostly those without else-blocks, are effectively
>> "rewritten" in the CFG construction making the algorithm unable to
>> distinguish them:
>>
>> and.c:
>>
>> if (a && b && c)
>> x = 1;
>>
>> ifs.c:
>>
>> if (a)
>> if (b)
>> if (c)
>> x = 1;
>>
>> gcc will build the same graph for both these programs, and gcov will
>> report boths as 3-term expressions. It is vital that it is not
>> interpreted the other way around (which is consistent with the shape of
>> the graph) because otherwise the masking would be wrong for the and.c
>> program which is a more severe error. While surprising, users would
>> probably expect some minor rewriting of semantically-identical
>> expressions.
>>
>>
Re: Ping [PATCH] Add condition coverage profiling
On 10/25/22 08:33, Jørgen Kvalsvik wrote:
Gentle ping. I have a tuned the summary output slightly (decisions covered ->
condition outcomes covered) already.
Sorry for a small delay, I'm working on it.
One general issue I noticed is you use an invalid coding style, where you use 4
spaces
for each level. Plus see the indentation for '{', '}':
diff --git a/gcc/tree-profile.cc b/gcc/tree-profile.cc
index 0b537d64d97..b661ed92045 100644
--- a/gcc/tree-profile.cc
+++ b/gcc/tree-profile.cc
@@ -553,11 +553,12 @@ masking_vectors (conds_ctx& ctx, array_slice
blocks,
body[0] = body.pop ();
for (const basic_block b : body)
-{
+ {
for (edge e1 : b->preds)
- for (edge e2 : b->preds)
- {
- const basic_block top = e1->src;
+ for (edge e2 : b->preds)
+ {
+ const basic_block top = e1->src;
+...
const basic_block bot = e2->src;
const unsigned cond = e1->flags & e2->flags & (EDGE_CONDITION);
Link: https://gcc.gnu.org/codingconventions.html
What editor do you use?
Cheers,
Martin
Ping [PATCH] Add condition coverage profiling
On 12/10/2022 12:16, Jørgen Kvalsvik wrote:
> 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. MC/DC it is
> required for 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 analyses the the control
> flow graph to instrument for coverage. This has the benefit of being
> programming language independent and faithful to compiler decisions
> and transformations, 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 records coverage in fixed-size
> bitsets which gcov knows how to interpret. This is very fast, but
> introduces a limit on the number of terms in a single boolean
> expression, 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. This limitation is in the implementation and not the
> algorithm, so support for more conditions can be added by also
> introducing arbitrary-sized bitsets.
>
> For space overhead, the instrumentation needs two accumulators
> (gcov_unsigned_type) per condition in the program which will be written
> to the gcov file. In addition, every function gets a pair of local
> accumulators, but these accmulators are reused between conditions in the
> same function.
>
> For time overhead, there is a zeroing of the local accumulators for
> every condition and one or two bitwise operation on every edge taken in
> the an expression.
>
> 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)
> condition outcomes covered 3/8
> condition 0 not covered (true false)
> condition 1 not covered (true)
> condition 2 not covered (true)
> condition 3 not covered (true)
> 1: 19:x = 1;
> -: 20:else
> 2: 21:x = 2;
> 3: 22:}
>
> gcov --conditions --json-format:
>
> "conditions": [
> {
> "not_covered_false": [
> 0
> ],
> "count": 8,
> "covered": 3,
> "not_covered_true": [
> 0,
> 1,
> 2,
> 3
> ]
> }
> ],
>
> Some expressions, mostly those without else-blocks, are effectively
> "rewritten" in the CFG construction making the algorithm unable to
> distinguish them:
>
> and.c:
>
> if (a && b && c)
> x = 1;
>
> ifs.c:
>
> if (a)
> if (b)
> if (c)
> x = 1;
>
> gcc will build the same graph for both these programs, and gcov will
> report boths as 3-term expressions. It is vital that it is not
> interpreted the other way around (which is consistent with the shape of
> the graph) because otherwise the masking would be wrong for the and.c
> program which is a more severe error. While surprising, users would
> probably expect some minor rewriting of semantically-identical
> expressions.
>
> and.c.gcov:
> #:2:if (a && b && c)
> decisions covered 6/6
> #:3:x = 1;
>
> ifs.c.gcov:
> #:2:if
Re: [PATCH] Add condition coverage profiling
On 18/10/2022 02:17, Hans-Peter Nilsson wrote:
> On Wed, 12 Oct 2022, Jørgen Kvalsvik via Gcc-patches wrote:
>> This patch adds support in gcc+gcov for modified condition/decision
>> coverage (MC/DC) with the -fprofile-conditions flag.
>
> I'd love improvements in this area.
>
> But this is a serious concern:
>
>> gcov --conditions:
>>
>> 3: 17:void fn (int a, int b, int c, int d) {
>> 3: 18:if ((a && (b || c)) && d)
>> condition outcomes covered 3/8
>> condition 0 not covered (true false)
>> condition 1 not covered (true)
>> condition 2 not covered (true)
>> condition 3 not covered (true)
>> 1: 19:x = 1;
>> -: 20:else
>> 2: 21:x = 2;
>> 3: 22:}
>
> Is this the suggested output from gcov?
>
> Sorry, but this is too hard to read; I can't read this. What
> does it mean? What's 0 and what's 1 and which are the 8
> conditions? (Why not 16 or more; which are redundant?) Or to
> wit, a glance, which parts of (a && (b || c)) && d are actually
> covered?
Hello,
Thanks for the feedback. I've modeled the output after the existing branch
coverage, but as you noticed conditions are slightly different because the
interesting output is what's _not_ taken. Like with branches, "conditions %d"
are the indices of the terms in the expression. The values in parenthesis are
the outcomes not found to be independent. Anything not listed is covered, guided
by the summary (conditions output covered n/m).
>
> There has got to be a better *intuitively* understandable
> presentation format than this. If you please forgive the errors
> in not matching the partal expressions like in your proposal and
> focus on the presentation format, I'd suggest something like,
> for a one-time run with a=true, b=false, c=true, d=false:
>
> "With:
> 3: 18:if ((a && (b || c)) && d)
> 0: ^^^
> 1: ^
> 2:^
> 3:
> 4: ^
> 5: ^
> condition 0 not covered (false)
> condition 1 not covered (true)
> condition 2 not covered (false)
> condition 3 not covered (false)
> condition 4 not covered (true)
> condition 5 not covered (false)"
> (etc)
>
> Possibly with each partial expression repeated above its
> underscoring for readability, because of the increasing distance
> between the underscoring and referred source.
>
> Actually, a separate indexed table like that isn't the best
> choice either. Perhaps better quoting the source:
>
> "condition (a && (b || c)) false not covered
> condition d false not covered
> condition (b || c) false not covered
> condition b true not covered
> condition c false not covered"
>
> Or, just underscoring as instead of quoting the source:
> "3: 18:if ((a && (b || c)) && d)
>
> In condition:^^^
> false not covered"
> (etc)
>
> It is possible I completely misunderstand your proposal, but
> there has to be something from the above to pick. I'd hate to
> see this go down because of usability problems. Hope this was
> constructive.
>
> brgds, H-P
I agree, all of these are good suggestions to better outputs. The problem is
that information needed to create this output is, as far as I know, not
available when gcov runs as it is not recorded. When the instrumentation for the
condition coverage itself is determined this information *is* available (basic
blocks with locus) so it should be possible to improve both the output of
condition coverage and maybe even the branch coverage too.
Thanks,
Jørgen
Re: [PATCH] Add condition coverage profiling
On Wed, 12 Oct 2022, Jørgen Kvalsvik via Gcc-patches wrote:
> This patch adds support in gcc+gcov for modified condition/decision
> coverage (MC/DC) with the -fprofile-conditions flag.
I'd love improvements in this area.
But this is a serious concern:
> gcov --conditions:
>
> 3: 17:void fn (int a, int b, int c, int d) {
> 3: 18:if ((a && (b || c)) && d)
> condition outcomes covered 3/8
> condition 0 not covered (true false)
> condition 1 not covered (true)
> condition 2 not covered (true)
> condition 3 not covered (true)
> 1: 19:x = 1;
> -: 20:else
> 2: 21:x = 2;
> 3: 22:}
Is this the suggested output from gcov?
Sorry, but this is too hard to read; I can't read this. What
does it mean? What's 0 and what's 1 and which are the 8
conditions? (Why not 16 or more; which are redundant?) Or to
wit, a glance, which parts of (a && (b || c)) && d are actually
covered?
There has got to be a better *intuitively* understandable
presentation format than this. If you please forgive the errors
in not matching the partal expressions like in your proposal and
focus on the presentation format, I'd suggest something like,
for a one-time run with a=true, b=false, c=true, d=false:
"With:
3: 18:if ((a && (b || c)) && d)
0: ^^^
1: ^
2:^
3:
4: ^
5: ^
condition 0 not covered (false)
condition 1 not covered (true)
condition 2 not covered (false)
condition 3 not covered (false)
condition 4 not covered (true)
condition 5 not covered (false)"
(etc)
Possibly with each partial expression repeated above its
underscoring for readability, because of the increasing distance
between the underscoring and referred source.
Actually, a separate indexed table like that isn't the best
choice either. Perhaps better quoting the source:
"condition (a && (b || c)) false not covered
condition d false not covered
condition (b || c) false not covered
condition b true not covered
condition c false not covered"
Or, just underscoring as instead of quoting the source:
"3: 18:if ((a && (b || c)) && d)
In condition:^^^
false not covered"
(etc)
It is possible I completely misunderstand your proposal, but
there has to be something from the above to pick. I'd hate to
see this go down because of usability problems. Hope this was
constructive.
brgds, H-P
[PATCH] Add condition coverage profiling
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. MC/DC it is
required for 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 analyses the the control
flow graph to instrument for coverage. This has the benefit of being
programming language independent and faithful to compiler decisions
and transformations, 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 records coverage in fixed-size
bitsets which gcov knows how to interpret. This is very fast, but
introduces a limit on the number of terms in a single boolean
expression, 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. This limitation is in the implementation and not the
algorithm, so support for more conditions can be added by also
introducing arbitrary-sized bitsets.
For space overhead, the instrumentation needs two accumulators
(gcov_unsigned_type) per condition in the program which will be written
to the gcov file. In addition, every function gets a pair of local
accumulators, but these accmulators are reused between conditions in the
same function.
For time overhead, there is a zeroing of the local accumulators for
every condition and one or two bitwise operation on every edge taken in
the an expression.
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)
condition outcomes covered 3/8
condition 0 not covered (true false)
condition 1 not covered (true)
condition 2 not covered (true)
condition 3 not covered (true)
1: 19:x = 1;
-: 20:else
2: 21:x = 2;
3: 22:}
gcov --conditions --json-format:
"conditions": [
{
"not_covered_false": [
0
],
"count": 8,
"covered": 3,
"not_covered_true": [
0,
1,
2,
3
]
}
],
Some expressions, mostly those without else-blocks, are effectively
"rewritten" in the CFG construction making the algorithm unable to
distinguish them:
and.c:
if (a && b && c)
x = 1;
ifs.c:
if (a)
if (b)
if (c)
x = 1;
gcc will build the same graph for both these programs, and gcov will
report boths as 3-term expressions. It is vital that it is not
interpreted the other way around (which is consistent with the shape of
the graph) because otherwise the masking would be wrong for the and.c
program which is a more severe error. While surprising, users would
probably expect some minor rewriting of semantically-identical
expressions.
and.c.gcov:
#:2:if (a && b && c)
decisions covered 6/6
#:3:x = 1;
ifs.c.gcov:
#:2:if (a)
#:3:if (b)
#:4:if (c)
#:5:x = 1;
condition outcomes covered 6/6
Adding else clauses alters the program (ifs.c can have 3 elses, and.c
only 1) and coverage becomes less surprising
ifs.c.gcov:
#:2:if (a)
Re: [PATCH] Add condition coverage profiling
On 04/08/2022 09:43, Sebastian Huber wrote: > On 02/08/2022 09:58, Jørgen Kvalsvik wrote: >> Based on this established terminology I can think of a few good candidates: >> >> condition outcomes covered n/m >> outcomes covered n/m >> >> What do you think? > > Both are fine, but I would prefer "condition outcomes covered n/m". > I'll update the patch. Maybe we should review the other outputs too? Something like: condition N missing outcome (true false)
Re: [PATCH] Add condition coverage profiling
On 02/08/2022 09:58, Jørgen Kvalsvik wrote: Based on this established terminology I can think of a few good candidates: condition outcomes covered n/m outcomes covered n/m What do you think? Both are fine, but I would prefer "condition outcomes covered n/m". -- embedded brains GmbH Herr Sebastian HUBER Dornierstr. 4 82178 Puchheim Germany email: sebastian.hu...@embedded-brains.de phone: +49-89-18 94 741 - 16 fax: +49-89-18 94 741 - 08 Registergericht: Amtsgericht München Registernummer: HRB 157899 Vertretungsberechtigte Geschäftsführer: Peter Rasmussen, Thomas Dörfler Unsere Datenschutzerklärung finden Sie hier: https://embedded-brains.de/datenschutzerklaerung/
Re: [PATCH] Add condition coverage profiling
On 15/07/2022 15:47, Jørgen Kvalsvik wrote: > On 15/07/2022 15:31, Sebastian Huber wrote: >> On 15.07.22 13:47, Jørgen Kvalsvik via Gcc-patches wrote: >>> 2. New vocabulary for the output - decisions for, well, the decisions. It >>> also >>> writes at most one line per condition: >>> >>> decisions covered 1/4 >>> condition 0 not covered (true false) >>> condition 1 not covered (true) >> >> Do we really have multiple decisions? I think we have only one decision >> composed >> of conditions and zero or more boolean operators. We have variants of >> condition >> outcomes. >> > > Maybe, I'm not sure - you could argue that since a fixture of boolean > "dominates" the outcome (either by short circuiting subsequent terms or > masking > preceding terms) then that fixture is a decision which leads to one of two > outcomes. The other parameters may change but they wouldn't change the > decision. You have 2^N inputs but only N+1 decisions. Personally the > "variants" > phrasing doesn't feel right to me. > > That being said I'm open to making this whatever the maintainers feel is > appropriate. Coming back to this, this is the terms + definitions gracefully borrowed from wiki [1]: Condition A condition is a leaf-level Boolean expression (it cannot be broken down into simpler Boolean expressions). Decision A Boolean expression composed of conditions and zero or more Boolean operators. A decision without a Boolean operator is a condition. Condition coverage Every condition in a decision in the program has taken all possible outcomes at least once. Decision coverage Every point of entry and exit in the program has been invoked at least once, and every decision in the program has taken all possible outcomes at least once. I agree that decisions n/m, based on these definitions, is not the best output unless it is specifically overloaded to mean "the family of bit vectors that cover some conditions". Not great. Based on this established terminology I can think of a few good candidates: condition outcomes covered n/m outcomes covered n/m What do you think? [1] https://en.wikipedia.org/wiki/Modified_condition/decision_coverage
Re: [PATCH] Add condition coverage profiling
On 15/07/2022 15:31, Sebastian Huber wrote: > On 15.07.22 13:47, Jørgen Kvalsvik via Gcc-patches wrote: >> 2. New vocabulary for the output - decisions for, well, the decisions. It >> also >> writes at most one line per condition: >> >> decisions covered 1/4 >> condition 0 not covered (true false) >> condition 1 not covered (true) > > Do we really have multiple decisions? I think we have only one decision > composed > of conditions and zero or more boolean operators. We have variants of > condition > outcomes. > Maybe, I'm not sure - you could argue that since a fixture of boolean "dominates" the outcome (either by short circuiting subsequent terms or masking preceding terms) then that fixture is a decision which leads to one of two outcomes. The other parameters may change but they wouldn't change the decision. You have 2^N inputs but only N+1 decisions. Personally the "variants" phrasing doesn't feel right to me. That being said I'm open to making this whatever the maintainers feel is appropriate.
Re: [PATCH] Add condition coverage profiling
On 15.07.22 13:47, Jørgen Kvalsvik via Gcc-patches wrote: 2. New vocabulary for the output - decisions for, well, the decisions. It also writes at most one line per condition: decisions covered 1/4 condition 0 not covered (true false) condition 1 not covered (true) Do we really have multiple decisions? I think we have only one decision composed of conditions and zero or more boolean operators. We have variants of condition outcomes. -- embedded brains GmbH Herr Sebastian HUBER Dornierstr. 4 82178 Puchheim Germany email: sebastian.hu...@embedded-brains.de phone: +49-89-18 94 741 - 16 fax: +49-89-18 94 741 - 08 Registergericht: Amtsgericht München Registernummer: HRB 157899 Vertretungsberechtigte Geschäftsführer: Peter Rasmussen, Thomas Dörfler Unsere Datenschutzerklärung finden Sie hier: https://embedded-brains.de/datenschutzerklaerung/
Re: [PATCH] Add condition coverage profiling
On 15/07/2022 13:39, Jørgen Kvalsvik wrote: > This patch adds support in gcc+gcov for modified condition/decision > coverage (MC/DC) with the -fprofile-conditions flag. Hello, I have updated this patch based on the feedback from Sebastian and Martin. 1. The description of the masking_vector function has been updated. 2. New vocabulary for the output - decisions for, well, the decisions. It also writes at most one line per condition: decisions covered 1/4 condition 0 not covered (true false) condition 1 not covered (true) 3. I applied Sebastian's patch and so it should work free standing. Thanks, Jørgen
[PATCH] Add condition coverage profiling
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. MC/DC it is
required for 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 analyses the the control
flow graph to instrument for coverage. This has the benefit of being
programming language independent and faithful to compiler decisions
and transformations, 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 records coverage in fixed-size
bitsets which gcov knows how to interpret. This is very fast, but
introduces a limit on the number of terms in a single boolean
expression, 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. This limitation is in the implementation and not the
algorithm, so support for more conditions can be added by also
introducing arbitrary-sized bitsets.
For space overhead, the instrumentation needs two accumulators
(gcov_unsigned_type) per condition in the program which will be written
to the gcov file. In addition, every function gets a pair of local
accumulators, but these accmulators are reused between conditions in the
same function.
For time overhead, there is a zeroing of the local accumulators for
every condition and one or two bitwise operation on every edge taken in
the an expression.
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)
decisions covered 3/8
condition 0 not covered (true false)
condition 1 not covered (true)
condition 2 not covered (true)
condition 3 not covered (true)
1: 19:x = 1;
-: 20:else
2: 21:x = 2;
3: 22:}
gcov --conditions --json-format:
"conditions": [
{
"not_covered_false": [
0
],
"count": 8,
"covered": 3,
"not_covered_true": [
0,
1,
2,
3
]
}
],
Some expressions, mostly those without else-blocks, are effectively
"rewritten" in the CFG construction making the algorithm unable to
distinguish them:
and.c:
if (a && b && c)
x = 1;
ifs.c:
if (a)
if (b)
if (c)
x = 1;
gcc will build the same graph for both these programs, and gcov will
report boths as 3-term expressions. It is vital that it is not
interpreted the other way around (which is consistent with the shape of
the graph) because otherwise the masking would be wrong for the and.c
program which is a more severe error. While surprising, users would
probably expect some minor rewriting of semantically-identical
expressions.
and.c.gcov:
#:2:if (a && b && c)
decisions covered 6/6
#:3:x = 1;
ifs.c.gcov:
#:2:if (a)
#:3:if (b)
#:4:if (c)
#:5:x = 1;
decisions covered 6/6
Adding else clauses alters the program (ifs.c can have 3 elses, and.c
only 1) and coverage becomes less surprising
ifs.c.gcov:
#:2:if (a)
decisions covered 2/2
Re: [PATCH] Add condition coverage profiling
On 12/07/2022 16:05, Sebastian Huber wrote:
> Hello Jørgen,
>
> thanks for the updated patch. I used it for a test suite run and the results
> look quite good.
>
> Could you please add this hunk to your patch set:
>
> diff --git a/libgcc/libgcov-merge.c b/libgcc/libgcov-merge.c
> index 89741f637e1..9e3e8ee5657 100644
> --- a/libgcc/libgcov-merge.c
> +++ b/libgcc/libgcov-merge.c
> @@ -33,6 +33,11 @@ void __gcov_merge_add (gcov_type *counters __attribute__
> ((unused)),
> unsigned n_counters __attribute__ ((unused))) {}
> #endif
>
> +#ifdef L_gcov_merge_ior
> +void __gcov_merge_ior (gcov_type *counters __attribute__ ((unused)),
> + unsigned n_counters __attribute__ ((unused))) {}
> +#endif
> +
> #ifdef L_gcov_merge_topn
> void __gcov_merge_topn (gcov_type *counters __attribute__ ((unused)),
> unsigned n_counters __attribute__ ((unused))) {}
>
> It is necessary to use gcov in freestanding environments (inhibit_libc is
> defined).
>
> The condition profiling found one spot for which we have insufficient
> condition
> coverage:
>
> function _Leap_year called 227 returned 100% blocks executed 100%
> 227: 54:static bool _Leap_year(
> -: 55: uint32_t year
> -: 56:)
> -: 57:{
> 227: 58: return (((year % 4) == 0) && ((year % 100) != 0)) || ((year
> %
> 400) == 0);
> branch 0 taken 19% (fallthrough)
> branch 1 taken 81%
> branch 2 taken 16% (fallthrough)
> branch 3 taken 84%
> branch 4 taken 4% (fallthrough)
> branch 5 taken 96%
> conditions covered 5/6
> condition 1 not covered (false)
> -: 59:}
>
> This is because we don't test with the year 2100 for example. This value would
> result in:
>
> year % 4 == 0: true
> year % 100 != 0: false
> year % 400 == 0: false
>
> It was not immediately clear to me what the
>
> "conditions covered 5/6
> condition 1 not covered (false)"
>
> is supposed to tell me. I guess a reasonable interpretation is: condition 1
> (which is "(year % 100) != 0" should be false and determine the outcome of the
> decision.
>
> What could be a bit confusing is that we have "conditions covered 5/6",
> however,
> there are only three conditions (0: (year % 4) == 0, 1: (year % 100) != 0, 2:
> (year % 400) == 0). Maybe it would be more clear if the report says "condition
> variants covered 5/6" or something like this.
>
Hello,
Thanks for the feedback. I'll apply the patch, no problem.
As for output I was honestly never really too happy with the output, and hoped
something would leap out during development (it didn't). I modeled most of it
after what the branch coverage output, and I'll give it a bit of thinking to see
if I can make it more intuitive at least.
Thanks,
Jørgen
Re: [PATCH] Add condition coverage profiling
Hello Jørgen,
thanks for the updated patch. I used it for a test suite run and the
results look quite good.
Could you please add this hunk to your patch set:
diff --git a/libgcc/libgcov-merge.c b/libgcc/libgcov-merge.c
index 89741f637e1..9e3e8ee5657 100644
--- a/libgcc/libgcov-merge.c
+++ b/libgcc/libgcov-merge.c
@@ -33,6 +33,11 @@ void __gcov_merge_add (gcov_type *counters
__attribute__ ((unused)),
unsigned n_counters __attribute__ ((unused))) {}
#endif
+#ifdef L_gcov_merge_ior
+void __gcov_merge_ior (gcov_type *counters __attribute__ ((unused)),
+ unsigned n_counters __attribute__ ((unused))) {}
+#endif
+
#ifdef L_gcov_merge_topn
void __gcov_merge_topn (gcov_type *counters __attribute__ ((unused)),
unsigned n_counters __attribute__ ((unused))) {}
It is necessary to use gcov in freestanding environments (inhibit_libc
is defined).
The condition profiling found one spot for which we have insufficient
condition coverage:
function _Leap_year called 227 returned 100% blocks executed 100%
227: 54:static bool _Leap_year(
-: 55: uint32_t year
-: 56:)
-: 57:{
227: 58: return (((year % 4) == 0) && ((year % 100) != 0)) ||
((year % 400) == 0);
branch 0 taken 19% (fallthrough)
branch 1 taken 81%
branch 2 taken 16% (fallthrough)
branch 3 taken 84%
branch 4 taken 4% (fallthrough)
branch 5 taken 96%
conditions covered 5/6
condition 1 not covered (false)
-: 59:}
This is because we don't test with the year 2100 for example. This value
would result in:
year % 4 == 0: true
year % 100 != 0: false
year % 400 == 0: false
It was not immediately clear to me what the
"conditions covered 5/6
condition 1 not covered (false)"
is supposed to tell me. I guess a reasonable interpretation is:
condition 1 (which is "(year % 100) != 0" should be false and determine
the outcome of the decision.
What could be a bit confusing is that we have "conditions covered 5/6",
however, there are only three conditions (0: (year % 4) == 0, 1: (year %
100) != 0, 2: (year % 400) == 0). Maybe it would be more clear if the
report says "condition variants covered 5/6" or something like this.
--
embedded brains GmbH
Herr Sebastian HUBER
Dornierstr. 4
82178 Puchheim
Germany
email: sebastian.hu...@embedded-brains.de
phone: +49-89-18 94 741 - 16
fax: +49-89-18 94 741 - 08
Registergericht: Amtsgericht München
Registernummer: HRB 157899
Vertretungsberechtigte Geschäftsführer: Peter Rasmussen, Thomas Dörfler
Unsere Datenschutzerklärung finden Sie hier:
https://embedded-brains.de/datenschutzerklaerung/
[PATCH] Add condition coverage profiling
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. MC/DC it is
required for 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 analyses the the control
flow graph to instrument for coverage. This has the benefit of being
programming language independent and faithful to compiler decisions
and transformations, 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 records coverage in fixed-size
bitsets which gcov knows how to interpret. This is very fast, but
introduces a limit on the number of terms in a single boolean
expression, 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. This limitation is in the implementation and not the
algorithm, so support for more conditions can be added by also
introducing arbitrary-sized bitsets.
For space overhead, the instrumentation needs two accumulators
(gcov_unsigned_type) per condition in the program which will be written
to the gcov file. In addition, every function gets a pair of local
accumulators, but these accmulators are reused between conditions in the
same function.
For time overhead, there is a zeroing of the local accumulators for
every condition and one or two bitwise operation on every edge taken in
the an expression.
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 3/8
condition 0 not covered (true)
condition 0 not covered (false)
condition 1 not covered (true)
condition 2 not covered (true)
condition 3 not covered (true)
1: 19:x = 1;
-: 20:else
2: 21:x = 2;
3: 22:}
gcov --conditions --json-format:
"conditions": [
{
"not_covered_false": [
0
],
"count": 8,
"covered": 3,
"not_covered_true": [
0,
1,
2,
3
]
}
],
Some expressions, mostly those without else-blocks, are effectively
"rewritten" in the CFG construction making the algorithm unable to
distinguish them:
and.c:
if (a && b && c)
x = 1;
ifs.c:
if (a)
if (b)
if (c)
x = 1;
gcc will build the same graph for both these programs, and gcov will
report boths as 3-term expressions. It is vital that it is not
interpreted the other way around (which is consistent with the shape of
the graph) because otherwise the masking would be wrong for the and.c
program which is a more severe error. While surprising, users would
probably expect some minor rewriting of semantically-identical
expressions.
and.c.gcov:
#:2:if (a && b && c)
conditions covered 6/6
#:3:x = 1;
ifs.c.gcov:
#:2:if (a)
#:3:if (b)
#:4:if (c)
#:5:x = 1;
conditions covered 6/6
Adding else clauses alters the program (ifs.c can have 3 elses, and.c
only 1) and coverage becomes less surprising
ifs.c.gcov:
#:2:
Re: [PATCH] Add condition coverage profiling
On 08/07/2022 15:45, Sebastian Huber wrote: > Hello Jørgen, > > some time passed. It would be nice if you could give a status update. I am > quite > interested in your work. > > Best regards, > Sebastian > I'm sorry for the late updates. There have have been a lot of issues (with the patch) to sort out and some other immediate priorities getting in the way. I will resubmit the updated patch now.
Re: [PATCH] Add condition coverage profiling
Hello Jørgen, some time passed. It would be nice if you could give a status update. I am quite interested in your work. Best regards, Sebastian -- embedded brains GmbH Herr Sebastian HUBER Dornierstr. 4 82178 Puchheim Germany email: sebastian.hu...@embedded-brains.de phone: +49-89-18 94 741 - 16 fax: +49-89-18 94 741 - 08 Registergericht: Amtsgericht München Registernummer: HRB 157899 Vertretungsberechtigte Geschäftsführer: Peter Rasmussen, Thomas Dörfler Unsere Datenschutzerklärung finden Sie hier: https://embedded-brains.de/datenschutzerklaerung/
Re: [PATCH] Add condition coverage profiling
On 22/04/2022 07:37, Sebastian Huber wrote: > > > On 17/04/2022 13:27, Jørgen Kvalsvik wrote: >>> In theory, would it be possible to print the state of the truth table with >>> the >>> information available in the gcda and gcno files? For example: >>> >>> Truth table for: a && (b || c)) && d >>> >>> 0 | 1 | 2 | 3 || covered >>> --+---+---+---++ >>> 0 | X | X | X || Y >>> 0 | X | X | X || Y >>> 0 | X | X | X || Y >>> 0 | X | X | X || Y >>> 0 | X | X | X || Y >>> 0 | X | X | X || Y >>> 0 | X | X | X || Y >>> 0 | X | X | X || Y >>> 1 | 0 | 0 | X || N >>> 1 | 0 | 0 | X || N >>> 1 | 0 | 1 | 0 || N >>> 1 | 0 | 1 | 1 || N >>> 1 | 1 | X | 0 || Y >>> 1 | 1 | X | 0 || Y >>> 1 | 1 | X | 1 || Y >>> 1 | 1 | X | 1 || Y >> Maybe? We would at least need to store the masking tables too, which right >> now >> are implicitly stored as in the instrumentation. It's not too bad, but it >> probably means the two functions should return some richer structure, which >> in >> turn means a little bit of redesign. Computing the truth table itself >> shouldn't >> be difficult. > > Using the tool in the context of safety-critical application would normally > require also a tool qualification. For GCC, this is a bit unrealistic. It > would > help if the tool output can be verified. Being able to inspect the masking > tables could help a reviewer to check what the tool did for a sample set of > inputs. > It would be useful for the developer too. Recording the masking vectors isn't hard (they have to be computed after all), maybe it as opt-in behind a flag?
Re: [PATCH] Add condition coverage profiling
On 17/04/2022 13:27, Jørgen Kvalsvik wrote: In theory, would it be possible to print the state of the truth table with the information available in the gcda and gcno files? For example: Truth table for: a && (b || c)) && d 0 | 1 | 2 | 3 || covered --+---+---+---++ 0 | X | X | X || Y 0 | X | X | X || Y 0 | X | X | X || Y 0 | X | X | X || Y 0 | X | X | X || Y 0 | X | X | X || Y 0 | X | X | X || Y 0 | X | X | X || Y 1 | 0 | 0 | X || N 1 | 0 | 0 | X || N 1 | 0 | 1 | 0 || N 1 | 0 | 1 | 1 || N 1 | 1 | X | 0 || Y 1 | 1 | X | 0 || Y 1 | 1 | X | 1 || Y 1 | 1 | X | 1 || Y Maybe? We would at least need to store the masking tables too, which right now are implicitly stored as in the instrumentation. It's not too bad, but it probably means the two functions should return some richer structure, which in turn means a little bit of redesign. Computing the truth table itself shouldn't be difficult. Using the tool in the context of safety-critical application would normally require also a tool qualification. For GCC, this is a bit unrealistic. It would help if the tool output can be verified. Being able to inspect the masking tables could help a reviewer to check what the tool did for a sample set of inputs. -- embedded brains GmbH Herr Sebastian HUBER Dornierstr. 4 82178 Puchheim Germany email: sebastian.hu...@embedded-brains.de phone: +49-89-18 94 741 - 16 fax: +49-89-18 94 741 - 08 Registergericht: Amtsgericht München Registernummer: HRB 157899 Vertretungsberechtigte Geschäftsführer: Peter Rasmussen, Thomas Dörfler Unsere Datenschutzerklärung finden Sie hier: https://embedded-brains.de/datenschutzerklaerung/
Re: [PATCH] Add condition coverage profiling
On 07/04/2022 14:04, Martin Liška wrote:
> On 3/28/22 16:40, Jørgen Kvalsvik via Gcc-patches wrote:
>> ... And with another tiny change that fixes Martin's while (1); case.
>
> Hello.
>
> Back to this ;) Thank you for the updated version of the patch. I have a
> couple
> of comments/requests:
Sorry for the late response, this email was eaten by spam filtering for some
reason.
> 1) I noticed the following cannot be linked:
>
> $ cat errors.C
> char trim_filename_name;
> int r;
>
> void trim_filename() {
> if (trim_filename_name)
> r = 123;
> while (trim_filename_name)
> ;
> }
>
> int
> main() {}
>
> $ g++ errors.C -fprofile-conditions -O2
> mold: error: undefined symbol: /tmp/ccmZANB5.o: __gcov8._Z13trim_filenamev
> collect2: error: ld returned 1 exit status
I was able to reproduce this, and I think I have it fixed (that is, I cannot
reproduce it anymore). I looks like the counters were allocated, but never used
in the absence of an output file. I changed it so that the writes are guarded
behind an output check and the counter instrumentation is unconditional which
makes it go away.
The coverage data dependencies are more interleaved (at least currently) than
all the other counters, which makes the flow awkward. I am not convinced a
proper fix is actually worth it, or if anything it would be an separate next
step.
> Btw. how much have you tested the patch set so far? Have you tried building
> something bigger
> with -fprofile-conditions enabled?
>
My own test suite plus zlib, and it looks like linux is compiling fine. I
haven't rigorously studied the _output_ in these projects yet, and it is very
time consuming without a benchmark.
> 2) As noticed by Sebastian, please support the new tag in gcov-dump:
>
> $ gcov-dump -l a.gcno
> ...
> a.gcno: 0145: 28:LINES
> a.gcno: block 7:`a.c':11
> a.gcno: 0147: 8:UNKNOWN
>
Will do.
> 3) Then I have some top-level formatting comments:
>
> a) please re-run check_GNU_style.py, I still see:
> === ERROR type #1: blocks of 8 spaces should be replaced with tabs (35
> error(s))
> ===
> ...
>
> b) write comments for each newly added function (and separate it by one empty
> line from
> the function definition)
>
> c) do not create visual alignment, we don't use it:
>
> + cond->set ("count", new json::integer_number (count));
> + cond->set ("covered", new json::integer_number (covered));
>
> and similar examples
>
> d) finish multiple comments after a dot on the same line:
>
> + /* Number of expressions found - this value is the number of entries in
> the
> + gcov output and the parameter to gcov_counter_alloc ().
> + */
>
> should be ... gcov_counter_alloc (). */
>
> e) for long lines with a function call like:
>
> + const int n = find_conditions_masked_by
> + (block, expr, flags + k, path, CONDITIONS_MAX_TERMS);
>
> do rather
> const int n
> = find_conditions_masked_by (block, expr,
> next_arg, ...);
>
> f) for function params:
>
> +int
> +collect_reachable_conditionals (
> + basic_block pre,
> + basic_block post,
> + basic_block *out,
> + int maxsize,
> + sbitmap expr)
>
> use rather:
>
> int
> collect_reachable_conditionals (basic_block pre,
> second_arg,...
>
Consider it done for the next revision.
> In the next round, I'm going to take a look at the CFG algorithm that
> identifies
> and instruments the sub-expressions.
Thank you.
Re: [PATCH] Add condition coverage profiling
On 06/04/2022 09:35, Sebastian Huber wrote:
> Ok, for the default output this is good. The output can be explained in the
> documentation. I will try to help here.
Splendid, thanks! I would be perfectly happy with better and/or more intuitive
messages too, but I figured it shouldn't delay the rest of the algorithm.
> In theory, would it be possible to print the state of the truth table with the
> information available in the gcda and gcno files? For example:
>
> Truth table for: a && (b || c)) && d
>
> 0 | 1 | 2 | 3 || covered
> --+---+---+---++
> 0 | X | X | X || Y
> 0 | X | X | X || Y
> 0 | X | X | X || Y
> 0 | X | X | X || Y
> 0 | X | X | X || Y
> 0 | X | X | X || Y
> 0 | X | X | X || Y
> 0 | X | X | X || Y
> 1 | 0 | 0 | X || N
> 1 | 0 | 0 | X || N
> 1 | 0 | 1 | 0 || N
> 1 | 0 | 1 | 1 || N
> 1 | 1 | X | 0 || Y
> 1 | 1 | X | 0 || Y
> 1 | 1 | X | 1 || Y
> 1 | 1 | X | 1 || Y
Maybe? We would at least need to store the masking tables too, which right now
are implicitly stored as in the instrumentation. It's not too bad, but it
probably means the two functions should return some richer structure, which in
turn means a little bit of redesign. Computing the truth table itself shouldn't
be difficult.
> Would it be possible to map the condition index to a source code snippet? For
> example condition 1 to "b"?
Not sure - I didn't find an obvious way from location, but gcc is already able
to point to bad names in complex expressions so I'm sure it is doable. If it can
warn about possibly-uninitialized there's no reason it shouldn't be able to
figure this out. It has the basic block for the condition.
-
I think I have figured out the correct approach for computing masking vectors,
which means I should be able to submit the updated patch next week. I have a
little bit more testing to do before that, including trying out the nested-for
error Sebastian found.
I also went back on a decision:
if (a) if (b) if (c) { ... }; // no else
should be treated as if (a && b && c) {}. It is to be expected that a compiler
makes some minor transformations, and it is more correct that masking works for
(a && b && c) than for the (equivalent) nested-if being different expressions.
The same kind of "reinterpretation" happens with branch coverage, so there is
some precedence. This also means updating a few tests and figuring out how to
handle the conditions inserted by destructors. Do they have some special basic
block flag or property?
--
Thanks,
Jørgen
Re: [PATCH] Add condition coverage profiling
On 08/04/2022 09:33, Jørgen Kvalsvik wrote:
On 08/04/2022 09:28, Jørgen Kvalsvik wrote:
On 07/04/2022 18:53, Sebastian Huber wrote:
Hello Jørgen,
there could be an issue with conditions in for loops:
3: 189: for (int a = 0; a <= 1; ++a) {
branch 0 taken 2
branch 1 taken 1 (fallthrough)
conditions covered 0/2
condition 0 not covered (true)
condition 0 not covered (false)
Hello,
Thanks, I'll have a look at it. There should be a for loop in the test suite,
but I'll add this exact example and see if I can reproduce it. This should
obviously be 100% covered.
Sebastian,
I added this exact example to the test suite, but it reports 2/2 for me (linux
amd64). Do you have a very different system, and what flags did you use?
Thanks for having a look at this. My setup is a bit more complicated. I
use an arm cross compiler and run an application on a simulator (Qemu).
The *.gcda files are created by gcov-tool. It is probably an issue with
my setup, so maybe we should ignore this issue at the moment.
When I move the code to a separate translation unit:
#include
static __attribute__((__noinline__)) int f(int a, int b, int c, int d)
{
if (a || (b && c) || d) {
return 1;
} else {
return 2;
}
}
void test(void)
{
for (int a = 0; a <= 1; ++a) {
for (int b = 0; b <= 1; ++b) {
for (int c = 0; c <= 1; ++c) {
for (int d = 0; d <= 1; ++d) {
printf("%i\n", f(a, b, c, d));
}
}
}
}
}
I get the right report:
-:0:Source:conds.c
-:0:Graph:b-xilinx_zynq_a9_qemu/conds.gcno
-:0:Data:b-xilinx_zynq_a9_qemu/conds.gcda
-:0:Runs:0
-:1:#include
-:2:
function f called 16 returned 100% blocks executed 100%
16:3:static __attribute__((__noinline__)) int f(int a, int
b, int c, int d)
-:4:{
16:5: if (a || (b && c) || d) {
branch 0 taken 8 (fallthrough)
branch 1 taken 8
branch 2 taken 4 (fallthrough)
branch 3 taken 4
branch 4 taken 2 (fallthrough)
branch 5 taken 2
branch 6 taken 3 (fallthrough)
branch 7 taken 3
conditions covered 8/8
13:6:return 1;
-:7: } else {
3:8:return 2;
-:9: }
-: 10:}
-: 11:
function test called 1 returned 100% blocks executed 100%
1: 12:void test(void)
-: 13:{
3: 14: for (int a = 0; a <= 1; ++a) {
branch 0 taken 2
branch 1 taken 1 (fallthrough)
conditions covered 2/2
6: 15:for (int b = 0; b <= 1; ++b) {
branch 0 taken 4
branch 1 taken 2 (fallthrough)
conditions covered 2/2
12: 16: for (int c = 0; c <= 1; ++c) {
branch 0 taken 8
branch 1 taken 4 (fallthrough)
conditions covered 2/2
24: 17:for (int d = 0; d <= 1; ++d) {
branch 0 taken 16
branch 1 taken 8 (fallthrough)
conditions covered 2/2
16: 18: printf("%i\n", f(a, b, c, d));
call0 returned 16
call1 returned 16
-: 19:}
-: 20: }
-: 21:}
-: 22: }
1: 23:}
For exactly the same code in another translation unit with more other
code I get this report:
function f called 16 returned 100% blocks executed 100%
16: 172:static __attribute__((__noinline__)) int f(int a, int
b, int c, int d)
-: 173:{
16: 174: if (a || (b && c) || d) {
branch 0 taken 8 (fallthrough)
branch 1 taken 8
branch 2 taken 4 (fallthrough)
branch 3 taken 4
branch 4 taken 2 (fallthrough)
branch 5 taken 2
branch 6 taken 3 (fallthrough)
branch 7 taken 3
conditions covered 8/8
13: 175:return 1;
-: 176: } else {
3: 177:return 2;
-: 178: }
-: 179:}
-: 180:
function Init called 1 returned 0% blocks executed 93%
1: 181:static void Init( rtems_task_argument arg )
-: 182:{
-: 183: struct ethernetif ethif;
-: 184: struct netif *netif;
-: 185:
-: 186: (void) arg;
1: 187: netif =
-: 188:
3: 189: for (int a = 0; a <= 1; ++a) {
branch 0 taken 2
branch 1 taken 1 (fallthrough)
conditions covered 0/2
condition 0 not covered (true)
condition 0 not covered (false)
6: 190:for (int b = 0; b <= 1; ++b) {
branch 0 taken 4
branch 1 taken 2 (fallthrough)
conditions covered 0/2
condition 0 not covered (true)
condition 0 not covered (false)
12: 191: for (int c = 0; c <= 1; ++c) {
branch 0 taken 8
branch 1 taken 4 (fallthrough)
conditions covered 0/2
condition 0 not covered (true)
condition 0 not covered (false)
24: 192:for (int d = 0; d <= 1; ++d) {
branch 0 taken 16
branch 1 taken 8 (fallthrough)
conditions covered 0/2
condition 0 not covered (true)
condition 0 not covered (false)
16: 193: printf("%i\n", f(a, b, c, d));
call0 returned 16
call1 returned 16
-: 194:}
-: 195: }
[PATCH] Add condition coverage profiling
On 08/04/2022 09:28, Jørgen Kvalsvik wrote:
> On 07/04/2022 18:53, Sebastian Huber wrote:
>> Hello Jørgen,
>>
>> there could be an issue with conditions in for loops:
>>
>> 3: 189: for (int a = 0; a <= 1; ++a) {
>> branch 0 taken 2
>> branch 1 taken 1 (fallthrough)
>> conditions covered 0/2
>> condition 0 not covered (true)
>> condition 0 not covered (false)
>>
>
> Hello,
>
> Thanks, I'll have a look at it. There should be a for loop in the test suite,
> but I'll add this exact example and see if I can reproduce it. This should
> obviously be 100% covered.
Sebastian,
I added this exact example to the test suite, but it reports 2/2 for me (linux
amd64). Do you have a very different system, and what flags did you use?
Cheers,
Jørgen
[PATCH] Add condition coverage profiling
On 07/04/2022 18:53, Sebastian Huber wrote:
> Hello Jørgen,
>
> there could be an issue with conditions in for loops:
>
> 3: 189: for (int a = 0; a <= 1; ++a) {
> branch 0 taken 2
> branch 1 taken 1 (fallthrough)
> conditions covered 0/2
> condition 0 not covered (true)
> condition 0 not covered (false)
>
Hello,
Thanks, I'll have a look at it. There should be a for loop in the test suite,
but I'll add this exact example and see if I can reproduce it. This should
obviously be 100% covered.
Re: [PATCH] Add condition coverage profiling
Hello Jørgen,
there could be an issue with conditions in for loops:
3: 189: for (int a = 0; a <= 1; ++a) {
branch 0 taken 2
branch 1 taken 1 (fallthrough)
conditions covered 0/2
condition 0 not covered (true)
condition 0 not covered (false)
--
embedded brains GmbH
Herr Sebastian HUBER
Dornierstr. 4
82178 Puchheim
Germany
email: sebastian.hu...@embedded-brains.de
phone: +49-89-18 94 741 - 16
fax: +49-89-18 94 741 - 08
Registergericht: Amtsgericht München
Registernummer: HRB 157899
Vertretungsberechtigte Geschäftsführer: Peter Rasmussen, Thomas Dörfler
Unsere Datenschutzerklärung finden Sie hier:
https://embedded-brains.de/datenschutzerklaerung/
Re: [PATCH] Add condition coverage profiling
On 3/28/22 16:40, Jørgen Kvalsvik via Gcc-patches wrote:
... And with another tiny change that fixes Martin's while (1); case.
Hello.
Back to this ;) Thank you for the updated version of the patch. I have a couple
of comments/requests:
1) I noticed the following cannot be linked:
$ cat errors.C
char trim_filename_name;
int r;
void trim_filename() {
if (trim_filename_name)
r = 123;
while (trim_filename_name)
;
}
int
main() {}
$ g++ errors.C -fprofile-conditions -O2
mold: error: undefined symbol: /tmp/ccmZANB5.o: __gcov8._Z13trim_filenamev
collect2: error: ld returned 1 exit status
Btw. how much have you tested the patch set so far? Have you tried building
something bigger
with -fprofile-conditions enabled?
2) As noticed by Sebastian, please support the new tag in gcov-dump:
$ gcov-dump -l a.gcno
...
a.gcno:0145: 28:LINES
a.gcno: block 7:`a.c':11
a.gcno:0147: 8:UNKNOWN
3) Then I have some top-level formatting comments:
a) please re-run check_GNU_style.py, I still see:
=== ERROR type #1: blocks of 8 spaces should be replaced with tabs (35
error(s)) ===
...
b) write comments for each newly added function (and separate it by one empty
line from
the function definition)
c) do not create visual alignment, we don't use it:
+ cond->set ("count", new json::integer_number (count));
+ cond->set ("covered", new json::integer_number (covered));
and similar examples
d) finish multiple comments after a dot on the same line:
+/* Number of expressions found - this value is the number of entries in the
+ gcov output and the parameter to gcov_counter_alloc ().
+ */
should be ... gcov_counter_alloc (). */
e) for long lines with a function call like:
+ const int n = find_conditions_masked_by
+ (block, expr, flags + k, path, CONDITIONS_MAX_TERMS);
do rather
const int n
= find_conditions_masked_by (block, expr,
next_arg, ...);
f) for function params:
+int
+collect_reachable_conditionals (
+basic_block pre,
+basic_block post,
+basic_block *out,
+int maxsize,
+sbitmap expr)
use rather:
int
collect_reachable_conditionals (basic_block pre,
second_arg,...
In the next round, I'm going to take a look at the CFG algorithm that identifies
and instruments the sub-expressions.
Thanks.
Cheers,
Martin
Re: [PATCH] Add condition coverage profiling
On 05/04/2022 22:07, Jørgen Kvalsvik wrote:
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:}
I have some trouble to understand the output. Would 8/8 mean that we have 100%
MC/DC coverage? What does "not covered (false)" or "not covered (true)" mean?
Yes, 8/8 would mean that the expression is 100% covered (all conditions take on
both values and have independent effect on the outcome).
This is really great.
"not covered" is a
report of missing coverage, that is "condition 1 not covered (false)" means
that bit N (N = 1, b in this case) has not taken on false yet, and to achieve
100% coverage you need a test case where b = false.
The wording is arbitrary, and I tried to strike a balance between density,
clarity, grepability and noise. I am open to other suggestions that would
improve this.
Ok, for the default output this is good. The output can be explained in
the documentation. I will try to help here.
In theory, would it be possible to print the state of the truth table
with the information available in the gcda and gcno files? For example:
Truth table for: a && (b || c)) && d
0 | 1 | 2 | 3 || covered
--+---+---+---++
0 | X | X | X || Y
0 | X | X | X || Y
0 | X | X | X || Y
0 | X | X | X || Y
0 | X | X | X || Y
0 | X | X | X || Y
0 | X | X | X || Y
0 | X | X | X || Y
1 | 0 | 0 | X || N
1 | 0 | 0 | X || N
1 | 0 | 1 | 0 || N
1 | 0 | 1 | 1 || N
1 | 1 | X | 0 || Y
1 | 1 | X | 0 || Y
1 | 1 | X | 1 || Y
1 | 1 | X | 1 || Y
Would it be possible to map the condition index to a source code
snippet? For example condition 1 to "b"?
Unrelated to this, in typing up some notes on this I found a few minor and one
quite significant (really, the masking algorithm is broken) error in the
algorithm, which I am working on correcting. I will propose the new patch with
these fixes too once I have finished writing and testing it.
Thanks a lot for this work.
--
embedded brains GmbH
Herr Sebastian HUBER
Dornierstr. 4
82178 Puchheim
Germany
email: sebastian.hu...@embedded-brains.de
phone: +49-89-18 94 741 - 16
fax: +49-89-18 94 741 - 08
Registergericht: Amtsgericht München
Registernummer: HRB 157899
Vertretungsberechtigte Geschäftsführer: Peter Rasmussen, Thomas Dörfler
Unsere Datenschutzerklärung finden Sie hier:
https://embedded-brains.de/datenschutzerklaerung/
[PATCH] Add condition coverage profiling
On 04/04/2022 10:14, Sebastian Huber wrote:
> Hello Jørgen,
>
> having support for MC/DC coverage in GCC would be really nice. I tried out
> your
> latest patch on an arm cross-compiler with Newlib (inhibit_libc is defined).
> Could you please add the following fix to your patch:
>
> diff --git a/libgcc/libgcov-merge.c b/libgcc/libgcov-merge.c
> index 89741f637e1..9e3e8ee5657 100644
> --- a/libgcc/libgcov-merge.c
> +++ b/libgcc/libgcov-merge.c
> @@ -33,6 +33,11 @@ void __gcov_merge_add (gcov_type *counters __attribute__
> ((unused)),
> unsigned n_counters __attribute__ ((unused))) {}
> #endif
>
> +#ifdef L_gcov_merge_ior
> +void __gcov_merge_ior (gcov_type *counters __attribute__ ((unused)),
> + unsigned n_counters __attribute__ ((unused))) {}
> +#endif
> +
> #ifdef L_gcov_merge_topn
> void __gcov_merge_topn (gcov_type *counters __attribute__ ((unused)),
> unsigned n_counters __attribute__ ((unused))) {}
>
> It seems that support for the new GCOV_TAG_CONDS is missing in gcov-tool and
> gcov-dump, see "tag_table" in gcc/gcov-dump.c and libgcc/libgcov-util.c.
>
> On 21/03/2022 12:55, Jørgen Kvalsvik via Gcc-patches wrote:
> [...]
>> 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).
>
> For multi-threaded applications using -fprofile-update=atomic is quite
> important. Unfortunately, not all 32-bit targets support 64-bit atomic
> operations in hardware. There is a target hook to select the size of
> gcov_type.
> Maybe a dedicated 64-bit type should be used for the bitfield using two 32-bit
> atomic OR if necessary.
I was not very clear here - I select operations (and limits) based on the width
of gcov_unsigned_type, which (judging from other snippets in tree-profile.cc)
can be 32 or 64-bit depending on platform. I assume gcov_type is 32 bit on the
platforms you allude to, in which case it should still work fine but fail on
expressions that would work on 64-bit systems.
If I am wrong here I suppose we should consider what you propose (concatenating
bitfields would also be a strategy for supporting >64 conditions), but in that
case I think the other counters are wrong.
I would appreciate it if someone would take a closer look at the code touching
the gcov type to see if I got it right, which also includes the atomic code.
Should something need fixing I will be happy to do it.
>
>>
>> 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:}
>
> I have some trouble to understand the output. Would 8/8 mean that we have 100%
> MC/DC coverage? What does "not covered (false)" or "not covered (true)" mean?
>
Yes, 8/8 would mean that the expression is 100% covered (all conditions take on
both values and have independent effect on the outcome). "not covered" is a
report of missing coverage, that is "condition 1 not covered (false)" means
that bit N (N = 1, b in this case) has not taken on false yet, and to achieve
100% coverage you need a test case where b = false.
The wording is arbitrary, and I tried to strike a balance between density,
clarity, grepability and noise. I am open to other suggestions that would
improve this.
Unrelated to this, in typing up some notes on this I found a few minor and one
quite significant (really, the masking algorithm is broken) error in the
algorithm, which I am working on correcting. I will propose the new patch with
these fixes too once I have finished writing and testing it.
Re: [PATCH] Add condition coverage profiling
Hello Jørgen, On 04/04/2022 10:14, Sebastian Huber wrote: It seems that support for the new GCOV_TAG_CONDS is missing in gcov-tool and gcov-dump, see "tag_table" in gcc/gcov-dump.c and libgcc/libgcov-util.c. it seems that for gcov-tool no changes are necessary. You added the condition bit fields as a new counter to gcov-counter.def and they are already properly merged with the help of __gcov_merge_ior(). I guess for gcov-dump it could be useful to add support for GCOV_TAG_CONDS used in the notes files. -- embedded brains GmbH Herr Sebastian HUBER Dornierstr. 4 82178 Puchheim Germany email: sebastian.hu...@embedded-brains.de phone: +49-89-18 94 741 - 16 fax: +49-89-18 94 741 - 08 Registergericht: Amtsgericht München Registernummer: HRB 157899 Vertretungsberechtigte Geschäftsführer: Peter Rasmussen, Thomas Dörfler Unsere Datenschutzerklärung finden Sie hier: https://embedded-brains.de/datenschutzerklaerung/
Re: [PATCH] Add condition coverage profiling
Hello Jørgen,
having support for MC/DC coverage in GCC would be really nice. I tried
out your latest patch on an arm cross-compiler with Newlib (inhibit_libc
is defined). Could you please add the following fix to your patch:
diff --git a/libgcc/libgcov-merge.c b/libgcc/libgcov-merge.c
index 89741f637e1..9e3e8ee5657 100644
--- a/libgcc/libgcov-merge.c
+++ b/libgcc/libgcov-merge.c
@@ -33,6 +33,11 @@ void __gcov_merge_add (gcov_type *counters
__attribute__ ((unused)),
unsigned n_counters __attribute__ ((unused))) {}
#endif
+#ifdef L_gcov_merge_ior
+void __gcov_merge_ior (gcov_type *counters __attribute__ ((unused)),
+ unsigned n_counters __attribute__ ((unused))) {}
+#endif
+
#ifdef L_gcov_merge_topn
void __gcov_merge_topn (gcov_type *counters __attribute__ ((unused)),
unsigned n_counters __attribute__ ((unused))) {}
It seems that support for the new GCOV_TAG_CONDS is missing in gcov-tool
and gcov-dump, see "tag_table" in gcc/gcov-dump.c and libgcc/libgcov-util.c.
On 21/03/2022 12:55, Jørgen Kvalsvik via Gcc-patches wrote:
[...]
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).
For multi-threaded applications using -fprofile-update=atomic is quite
important. Unfortunately, not all 32-bit targets support 64-bit atomic
operations in hardware. There is a target hook to select the size of
gcov_type. Maybe a dedicated 64-bit type should be used for the bitfield
using two 32-bit atomic OR if necessary.
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:}
I have some trouble to understand the output. Would 8/8 mean that we
have 100% MC/DC coverage? What does "not covered (false)" or "not
covered (true)" mean?
--
embedded brains GmbH
Herr Sebastian HUBER
Dornierstr. 4
82178 Puchheim
Germany
email: sebastian.hu...@embedded-brains.de
phone: +49-89-18 94 741 - 16
fax: +49-89-18 94 741 - 08
Registergericht: Amtsgericht München
Registernummer: HRB 157899
Vertretungsberechtigte Geschäftsführer: Peter Rasmussen, Thomas Dörfler
Unsere Datenschutzerklärung finden Sie hier:
https://embedded-brains.de/datenschutzerklaerung/
Re: [PATCH] Add condition coverage profiling
On 3/25/22 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 . 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.
Hello.
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.
Oh, now I've got it. It makes sense, what a clever idea.
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?
Yes, I think the option (-fprofile-conditions) should imply -fprofile-arcs
(or maybe even --coverage which is -fprofile-arcs + -ftest-coverage).
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.
Oh, you use an anonymous namespace, then I'm fine with any approach you prefer.
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?
Yes.
The per-call accumulators are local to each activation record and should
not need the atomics, or am I missing something?
Correct.
About the algorithm itself. I must confess it's quite hard for me to fully
understand
it and it can be made easier by providing an article you're planning to write.
Anyway, I guess some more experiences guys like Richi can help with the CFG
tree decomposition.
Note I noticed an ICE for a simple test-case:
$ cat demangle.i
int
cplus_demangle_mangled_name() {
while (1)
;
}
$ /dev/shm/objdir/gcc/xgcc -B/dev/shm/objdir/gcc/ --coverage
-fprofile-conditions demangle.i -O2 -c
xgcc: internal compiler error: Segmentation
[PATCH] Add condition coverage profiling
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 . 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 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
Re: [PATCH] Add condition coverage profiling
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
0x778b93cf ???
/usr/src/debug/glibc-2.35-2.1.x86_64/signal/../sysdeps/unix/sysv/linux/x86_64/libc_sigaction.c:0
0x778f29ed __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
[PATCH] Add condition coverage profiling
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 -- 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 6d0650340e538d8dd0ccc8369a89ba9b99d7904c Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=B8rgen=20Kvalsvik?= 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 impo
