* [PATCH] Always generate else-block in gimplify
@ 2023-09-24 13:06 Jørgen Kvalsvik
2023-09-25 10:51 ` Richard Biener
0 siblings, 1 reply; 3+ messages in thread
From: Jørgen Kvalsvik @ 2023-09-24 13:06 UTC (permalink / raw)
To: gcc-patches; +Cc: Jørgen Kvalsvik
This is a request for feedback and a proof-of-concept, not something I
intend to merge as-is. It would be nice if gcc, maybe just under some
circumstances, always generated an else-block for coverage purposes.
I am working on the MC/DC support by CFG analysis for a while
https://gcc.gnu.org/pipermail/gcc-patches/2023-June/621449.html and have
ironed out a lot of problems. The last problem I know about, which is
impossible to actually fix right now, is the "fusing" of nested ifs.
Here is an example:
if (a) if (b) if (c) { ... } // 3 conditions, 6 outcomes
if (a && b && c) { ... } // 3 conditions, 6 outcomes
These form isomorphic CFGs which means there is no way for my algorithm
to distinguish them. This is sort-of acceptable since the coverage
measurements more accurately measure the semantics (and not the syntax),
but this also happens when there is code in-between the nesting:
if (a) // measures to 2 conditions, 4 outcomes
{
a += b * 10;
b -= a + 2;
if (b)
{
...
}
}
You would expect this to be measured as:
if (a) // 1 condition, 2 outcomes
{
a += b * 10;
b -= a + 2;
if (b) // 1 condition, 2 outcomes
{
...
}
}
The source of the problem is the missing (or empty) else block, as the
algorithm uses the outcome (then/else) edges to determine the limits of
expressions. If, however, the else blocks are generated, the conditions
are counted as you would expect.
So I have a few questions:
1. Is something like this even acceptable? The semantics of the program
should not change, assuming the else-block only exists but is without
significant behavior. It will only be generated if there is no
explicit else in source.
2. Should this only be generated when necessary (e.g. under condition
coverage? No optimization?)
3. I used a simple int-init { int __mcdc_barrier = 0; } but there might
be better contents for the block that does not add anything
operationally. I am not very familiar with this part of gcc and would
like to see someting better. Any suggestions?
---
gcc/gimplify.cc | 8 ++++++++
1 file changed, 8 insertions(+)
diff --git a/gcc/gimplify.cc b/gcc/gimplify.cc
index ade6e335da7..43af38df742 100644
--- a/gcc/gimplify.cc
+++ b/gcc/gimplify.cc
@@ -4370,6 +4370,14 @@ gimplify_cond_expr (tree *expr_p, gimple_seq *pre_p, fallback_t fallback)
enum tree_code pred_code;
gimple_seq seq = NULL;
+ if (TREE_OPERAND (expr, 2) == NULL_TREE)
+ {
+ tree var = build_decl (UNKNOWN_LOCATION, VAR_DECL, get_identifier
+ ("__mcdc_barrier"), integer_type_node);
+ tree val = build_int_cst (integer_type_node, 0);
+ TREE_OPERAND (expr, 2) = build2 (INIT_EXPR, TREE_TYPE (var), var, val);
+ }
+
/* If this COND_EXPR has a value, copy the values into a temporary within
the arms. */
if (!VOID_TYPE_P (type))
--
2.30.2
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] Always generate else-block in gimplify
2023-09-24 13:06 [PATCH] Always generate else-block in gimplify Jørgen Kvalsvik
@ 2023-09-25 10:51 ` Richard Biener
2023-09-25 12:17 ` Jørgen Kvalsvik
0 siblings, 1 reply; 3+ messages in thread
From: Richard Biener @ 2023-09-25 10:51 UTC (permalink / raw)
To: Jørgen Kvalsvik; +Cc: gcc-patches
On Sun, Sep 24, 2023 at 3:09 PM Jørgen Kvalsvik <j@lambda.is> wrote:
>
> This is a request for feedback and a proof-of-concept, not something I
> intend to merge as-is. It would be nice if gcc, maybe just under some
> circumstances, always generated an else-block for coverage purposes.
>
> I am working on the MC/DC support by CFG analysis for a while
> https://gcc.gnu.org/pipermail/gcc-patches/2023-June/621449.html and have
> ironed out a lot of problems. The last problem I know about, which is
> impossible to actually fix right now, is the "fusing" of nested ifs.
> Here is an example:
>
> if (a) if (b) if (c) { ... } // 3 conditions, 6 outcomes
> if (a && b && c) { ... } // 3 conditions, 6 outcomes
>
> These form isomorphic CFGs which means there is no way for my algorithm
> to distinguish them. This is sort-of acceptable since the coverage
> measurements more accurately measure the semantics (and not the syntax),
> but this also happens when there is code in-between the nesting:
>
> if (a) // measures to 2 conditions, 4 outcomes
> {
> a += b * 10;
> b -= a + 2;
> if (b)
> {
> ...
> }
> }
>
> You would expect this to be measured as:
>
> if (a) // 1 condition, 2 outcomes
> {
> a += b * 10;
> b -= a + 2;
> if (b) // 1 condition, 2 outcomes
> {
> ...
> }
> }
>
> The source of the problem is the missing (or empty) else block, as the
> algorithm uses the outcome (then/else) edges to determine the limits of
> expressions. If, however, the else blocks are generated, the conditions
> are counted as you would expect.
>
> So I have a few questions:
>
> 1. Is something like this even acceptable? The semantics of the program
> should not change, assuming the else-block only exists but is without
> significant behavior. It will only be generated if there is no
> explicit else in source.
> 2. Should this only be generated when necessary (e.g. under condition
> coverage? No optimization?)
> 3. I used a simple int-init { int __mcdc_barrier = 0; } but there might
> be better contents for the block that does not add anything
> operationally. I am not very familiar with this part of gcc and would
> like to see someting better. Any suggestions?
Can you in theory handle this by splitting the 'else' edge before
coverage instrumentation rather than using a stmt inserted during
gimplification?
> ---
> gcc/gimplify.cc | 8 ++++++++
> 1 file changed, 8 insertions(+)
>
> diff --git a/gcc/gimplify.cc b/gcc/gimplify.cc
> index ade6e335da7..43af38df742 100644
> --- a/gcc/gimplify.cc
> +++ b/gcc/gimplify.cc
> @@ -4370,6 +4370,14 @@ gimplify_cond_expr (tree *expr_p, gimple_seq *pre_p, fallback_t fallback)
> enum tree_code pred_code;
> gimple_seq seq = NULL;
>
> + if (TREE_OPERAND (expr, 2) == NULL_TREE)
> + {
> + tree var = build_decl (UNKNOWN_LOCATION, VAR_DECL, get_identifier
> + ("__mcdc_barrier"), integer_type_node);
> + tree val = build_int_cst (integer_type_node, 0);
> + TREE_OPERAND (expr, 2) = build2 (INIT_EXPR, TREE_TYPE (var), var, val);
> + }
> +
> /* If this COND_EXPR has a value, copy the values into a temporary within
> the arms. */
> if (!VOID_TYPE_P (type))
> --
> 2.30.2
>
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] Always generate else-block in gimplify
2023-09-25 10:51 ` Richard Biener
@ 2023-09-25 12:17 ` Jørgen Kvalsvik
0 siblings, 0 replies; 3+ messages in thread
From: Jørgen Kvalsvik @ 2023-09-25 12:17 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
On 25/09/2023 19:51, Richard Biener wrote:
> On Sun, Sep 24, 2023 at 3:09 PM Jørgen Kvalsvik <j@lambda.is> wrote:
>>
>> This is a request for feedback and a proof-of-concept, not something I
>> intend to merge as-is. It would be nice if gcc, maybe just under some
>> circumstances, always generated an else-block for coverage purposes.
>>
>> I am working on the MC/DC support by CFG analysis for a while
>> https://gcc.gnu.org/pipermail/gcc-patches/2023-June/621449.html and have
>> ironed out a lot of problems. The last problem I know about, which is
>> impossible to actually fix right now, is the "fusing" of nested ifs.
>> Here is an example:
>>
>> if (a) if (b) if (c) { ... } // 3 conditions, 6 outcomes
>> if (a && b && c) { ... } // 3 conditions, 6 outcomes
>>
>> These form isomorphic CFGs which means there is no way for my algorithm
>> to distinguish them. This is sort-of acceptable since the coverage
>> measurements more accurately measure the semantics (and not the syntax),
>> but this also happens when there is code in-between the nesting:
>>
>> if (a) // measures to 2 conditions, 4 outcomes
>> {
>> a += b * 10;
>> b -= a + 2;
>> if (b)
>> {
>> ...
>> }
>> }
>>
>> You would expect this to be measured as:
>>
>> if (a) // 1 condition, 2 outcomes
>> {
>> a += b * 10;
>> b -= a + 2;
>> if (b) // 1 condition, 2 outcomes
>> {
>> ...
>> }
>> }
>>
>> The source of the problem is the missing (or empty) else block, as the
>> algorithm uses the outcome (then/else) edges to determine the limits of
>> expressions. If, however, the else blocks are generated, the conditions
>> are counted as you would expect.
>>
>> So I have a few questions:
>>
>> 1. Is something like this even acceptable? The semantics of the program
>> should not change, assuming the else-block only exists but is without
>> significant behavior. It will only be generated if there is no
>> explicit else in source.
>> 2. Should this only be generated when necessary (e.g. under condition
>> coverage? No optimization?)
>> 3. I used a simple int-init { int __mcdc_barrier = 0; } but there might
>> be better contents for the block that does not add anything
>> operationally. I am not very familiar with this part of gcc and would
>> like to see someting better. Any suggestions?
>
> Can you in theory handle this by splitting the 'else' edge before
> coverage instrumentation rather than using a stmt inserted during
> gimplification?
I don't think so. By the time we get to the instrumentation we do not
know in if the false edge is to a proper else. The simplest example is
really:
if (a) if (b) if (c) { ... }
if (a && b && c) { ... }
And the dot representation for both graphs:
digraph {
subgraph cluster_ifs {
label = "ifs";
A0 -> A2 [label="fallthru "];
A2 -> A3 [label="true "];
A2 -> A6 [label="false "];
A3 -> A4 [label="true "];
A3 -> A6 [label="false "];
A6 -> A7 [label="fallthru "];
A7 -> A1 [label=""];
A4 -> A5 [label="true "];
A4 -> A6 [label="false "];
A5 -> A7 [label="fallthru "];
}
subgraph cluster_and {
label = "and";
B0 -> B2 [label="fallthru "];
B2 -> B3 [label="true "];
B2 -> B6 [label="false "];
B3 -> B4 [label="true "];
B3 -> B6 [label="false "];
B6 -> B7 [label="fallthru "];
B7 -> B1 [label=""];
B4 -> B5 [label="true "];
B4 -> B6 [label="false "];
B5 -> B7 [label="fallthru "];
}
}
The CFGs are identical, so there is no way to recover the else block at
this stage.
Now, it might be possible to do or recover this in other phases than the
gimplify, and I am very open for suggestions to where and how.
PS. my patch (maybe unsurprisingly) breaks a bunch of tests, so it is
obviously not fit as-is.
Thanks,
Jørgen
>
>> ---
>> gcc/gimplify.cc | 8 ++++++++
>> 1 file changed, 8 insertions(+)
>>
>> diff --git a/gcc/gimplify.cc b/gcc/gimplify.cc
>> index ade6e335da7..43af38df742 100644
>> --- a/gcc/gimplify.cc
>> +++ b/gcc/gimplify.cc
>> @@ -4370,6 +4370,14 @@ gimplify_cond_expr (tree *expr_p, gimple_seq *pre_p, fallback_t fallback)
>> enum tree_code pred_code;
>> gimple_seq seq = NULL;
>>
>> + if (TREE_OPERAND (expr, 2) == NULL_TREE)
>> + {
>> + tree var = build_decl (UNKNOWN_LOCATION, VAR_DECL, get_identifier
>> + ("__mcdc_barrier"), integer_type_node);
>> + tree val = build_int_cst (integer_type_node, 0);
>> + TREE_OPERAND (expr, 2) = build2 (INIT_EXPR, TREE_TYPE (var), var, val);
>> + }
>> +
>> /* If this COND_EXPR has a value, copy the values into a temporary within
>> the arms. */
>> if (!VOID_TYPE_P (type))
>> --
>> 2.30.2
>>
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2023-09-25 12:17 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-09-24 13:06 [PATCH] Always generate else-block in gimplify Jørgen Kvalsvik
2023-09-25 10:51 ` Richard Biener
2023-09-25 12:17 ` Jørgen Kvalsvik
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).