From: "Martin Liška" <mliska@suse.cz>
To: "Jørgen Kvalsvik" <j@lambda.is>,
"Richard Biener" <richard.guenther@gmail.com>
Cc: GCC Development <gcc@gcc.gnu.org>, jh@suse.cz
Subject: Re: Surprising CFG construction with goto from then to else
Date: Mon, 3 Oct 2022 12:59:00 +0200 [thread overview]
Message-ID: <a8200c9d-c3c5-addf-31a6-82e30ed2d4f8@suse.cz> (raw)
In-Reply-To: <6db0e9be-4143-abc4-d280-f550e8f68cac@lambda.is>
On 9/16/22 13:05, Jørgen Kvalsvik wrote:
> Gentle ping. Any idea if the edge split is still useful and/or how to test for it?
@Honza: Can you please reply here?
Thanks,
Martin
>
> Thanks,
> Jørgen
>
> On 08/09/2022 12:30, Jørgen Kvalsvik wrote:
>> On 02/09/2022 14:22, Richard Biener wrote:
>>> On Fri, Sep 2, 2022 at 11:50 AM Jørgen Kvalsvik <j@lambda.is> wrote:
>>>>
>>>>
>>>> Hello,
>>>>
>>>> I played some more with odd programs and the effect on control flow
>>>> graph construction (as a part of condition coverage support [1]) and
>>>> came across this:
>>>>
>>>> int fn (int a, int b, int c) {
>>>> int x = 0;
>>>> if (a && b) {
>>>> if (c) {
>>>> goto a_;
>>>> } else {
>>>> x = a;
>>>> }
>>>> } else {
>>>> a_:
>>>> x = (a - b);
>>>> }
>>>>
>>>> return x;
>>>> }
>>>>
>>>> Run through gcov --conditions I get:
>>>>
>>>> 4: 5: if (a && b) {
>>>> condition outcomes covered 2/2
>>>> condition outcomes covered 2/2
>>>> 2: 6: if (c) {
>>>> condition outcomes covered 2/2
>>>>
>>>> Which is clearly not correct. So I started digging into why and dump the
>>>> CFG as the coverage profiling sees it https://i.imgur.com/d0q72rA.png
>>>> [2]. I apologize for the labeling, but A2 = a, A3 = b, A5 = c and A9 the
>>>> else block. The problem, which is what confuses the algorithm, is that a
>>>> and b don't share A9 as a successor (on false) as I would expect.
>>>>
>>>> If I add some operation before the label the problem disappears and a
>>>> and b share false-destination again https://i.imgur.com/PSrfaLC.png [3].
>>>>
>>>> } else {
>>>> x++;
>>>> a_:
>>>> x = (a - b);
>>>> }
>>>>
>>>> 4: 5: if (a && b) {
>>>> condition outcomes covered 4/4
>>>> 2: 6: if (c) {
>>>> condition outcomes covered 2/2
>>>>
>>>>
>>>> When dumping the cfg in the former case with -fdump-tree-cfg-graph I get
>>>> a CFG without the split destinations in a and b
>>>> https://i.imgur.com/05MCjzp.png [3]. I would assume from this that the
>>>> graph dump happens after _more_ CFG transformations than the branch
>>>> profiling.
>>>>
>>>> So my questions are:
>>>>
>>>> 1. Is the control flow graph expected to be constructed as such where a
>>>> and b don't share outcome, or is it to be considered a bug?
>>>> 2. If yes, would it be problematic to push the branch coverage and
>>>> condition profiling to a later stage where the cfg has been fixed?
>>>
>>> I would say you should only see more nodes merged. It's a bit hard to follow
>>> what you say with the namings - I usually run cc1 in gdb, breaking at
>>> execute_build_cfg where you can do, after build_gimple_cfg finished
>>> (and before cleanup_tree_cfg ()) do a 'dot-fn' in gdb which produces a nice
>>> picture of the CFG and code with graphviz.
>>>
>>> It looks like I would have expected, in particular we do not force a
>>> new basic-block to be generated for a_: after the D.1991: artificial
>>> label we have for the else. That might be premature optimization
>>> for your case (but the cleanup_tree_cfg () would immediately do
>>> that as well).
>>>
>>> Richard.
>>
>> I did some more digging into this and have isolated the problem to edge splitting inside the branch_prob () function itself.
>>
>> gcc/profile.cc:1248
>>
>> if (last
>> && gimple_has_location (last)
>> && !RESERVED_LOCATION_P (e->goto_locus)
>> && !single_succ_p (bb)
>> && (LOCATION_FILE (e->goto_locus)
>> != LOCATION_FILE (gimple_location (last))
>> || (LOCATION_LINE (e->goto_locus)
>> != LOCATION_LINE (gimple_location (last)))))
>> {
>> basic_block new_bb = split_edge (e);
>> edge ne = single_succ_edge (new_bb);
>> ne->goto_locus = e->goto_locus;
>> }
>>
>> Based on the cleaned-up cfg that gcc dumps later it looks like this split only lives through the branch coverage/profiling phase (it may bleed slightly later but it shouldn't be of significance).
>>
>> Out of curiosity I removed the splitting altogether and no tests failed when running make check-gcc check-g++ RUNTESTFLAGS="gcov.exp". Either it was not covered by tests in the first place, or whatever behaviour this check is meant to fix is resolved elsewhere. I have to admit I don't really see a difference with/without this patch, but I don't know what to look for.
>>
>> The check was first introduced in 2005 by Jan (cc):
>>
>> commit d783b2a2dc91e1d2c1fea78cac2b6c6c73b3680d
>> Author: Jan Hubicka <jh@suse.cz>
>> Date: Thu Aug 4 00:10:54 2005 +0200
>>
>> profile.c (branch_prob): Split edges with goto locus on them to get proper line counts.
>>
>>
>> * profile.c (branch_prob): Split edges with goto locus on them
>> to get proper line counts.
>> * tree-cfg.c (make_cond_expr_edges): Record user goto locuses, if any.
>>
>> * gcov-1.C: Fix switch counts.
>> * gcov-4b.c: Likewise.
>>
>> What stands out to me in the check is that it uses location-file and location-line to decide if to split the edge. I added a few prints to see when the file/line is set:
>>
>> 2 int goto1 (int a) {
>>
>>
>> 3 if (a)
>> 4 goto end;
>> 5
>> 6 return 1;
>> 7 end:
>> 8 x += a;
>> 9 return 0;
>> 10 }
>>
>> if (a_5(D) != 0)
>>
>>
>> edge (true)
>> last goto2.c:3
>> goto (null):0
>>
>> if (a_5(D) != 0)
>> edge (false)
>> last goto2.c:3
>> goto (null):0
>>
>> // predicted unlikely by goto predictor.
>> edge (fallthru)
>> last goto2.c:4
>> goto goto2.c:4
>>
>> The goto statement is the only with with a location for both the basic block and the edge.
>>
>> 12 int goto2 (int a) {
>>
>>
>> 13 if (a) { goto end; }
>> 14 else { label: a++; }
>> 15
>> 16 return 1;
>> 17 end:
>> 18 x += a;
>> 19 return 0;
>> 20 }
>>
>> if (a_5(D) != 0)
>> edge (true)
>> last goto2.c:13
>> goto (null):0
>>
>> if (a_5(D) != 0)
>> edge (false)
>> last goto2.c:13
>> goto goto2.c:14
>>
>> // predicted unlikely by goto predictor.
>> edge (fallthru)
>> last goto2.c:13
>> goto goto2.c:13
>>
>> Now the else block has two locations as well, with the edge label e->goto_locus being inside the else block. Note that this label is _unrelated_ to the edge jump a (false) -> else.
>>
>> Now a function without gotos:
>>
>> 22 int goto3 (int a, int b) {
>> 23 if (a && b) {
>> 24 x += a * b;
>> 25 } else {
>> 26 x -= 1;
>> 27 }
>> 28 return 0;
>> 29 }
>>
>> if (a_7(D) != 0)
>> edge (true)
>> last goto2.c:23
>> goto (null):0
>>
>> if (a_7(D) != 0)
>> edge (false)
>> last goto2.c:23
>> goto (null):0
>>
>> if (b_8(D) != 0)
>> edge (true)
>> last goto2.c:23
>> goto (null):0
>>
>> if (b_8(D) != 0)
>> edge (false)
>> last goto2.c:23
>> goto (null):0
>>
>> x = _3;
>> edge (fallthru)
>> last goto2.c:24
>> goto goto2.c:24
>>
>> x = _5;
>> edge (fallthru)
>> last goto2.c:26
>> goto (null):0
>>
>> Now the checks if (a) and (b) don't have goto_locus on the edges. For completeness I included the implied jumps in the then/else blocks which _do_ have edge locus in the then case.
>>
>> Finally, the case that expose the problem for me:
>>
>> 31 int goto4 (int a, int b) {
>> 32 if (a) {
>> 33 if (b) goto elseblock;
>> 34 else a++;
>> 35 } else {
>> 36 elseblock:
>> 37 a--;
>> 38 }
>> 39
>> 40 return a;
>> 41 }
>>
>> if (a_2(D) != 0)
>> edge (true)
>> last goto2.c:32
>> goto (null):0
>>
>> if (a_2(D) != 0)
>> edge (false)
>> last goto2.c:32
>> goto goto2.c:36
>>
>> if (b_3(D) != 0)
>> edge (true)
>> last goto2.c:33
>> goto (null):0
>>
>> if (b_3(D) != 0)
>> edge (false)
>> last goto2.c:33
>> goto (null):0
>>
>> Again, a (false) has a goto_locus because there is an unrelated label at the top of the else block. For completeness, it also applies happens when there's a label on top of then:
>>
>> 43 int goto5 (int a, int b) {
>> 44 if (a) {
>> 45 then:
>> 46 a++;
>> 47 } else {
>> 48 a--;
>>
>>
>> 49 }
>> 50
>> 51 return a;
>> 52 }
>>
>> if (a_2(D) != 0)
>> edge (true)
>> last goto2.c:44
>> goto goto2.c:45
>>
>> if (a_2(D) != 0)
>> edge (false)
>> last goto2.c:44
>> goto (null):0
>>
>> This causes the edge to split which probably isn't a problem for the branch coverage, but it is problematic for my condition coverage algorithm. So how do we solve this?
>>
>> 1. Is the edge splitting necessary? I didn't find a test that covers this (there might be one, any idea?). If the edge splitting is not necessary anymore then removing it should be fine for my coverage needs.
>> 2. Assuming the edge split is necessary making a decision on source file + line seems vulnerable to source formatting:
>>
>> 54 int goto6 (int a) {
>> 55 if (a) label: goto end;
>>
>>
>> 56 return 0;
>> 57 end:
>> 58 return 1;
>> 59
>> 60 }
>>
>> if (a_2(D) != 0)
>> edge (true)
>> last goto2.c:55
>> goto goto2.c:55
>>
>> if (a_2(D) != 0)
>> edge (false)
>> last goto2.c:55
>> goto (null):0
>>
>> // predicted unlikely by goto predictor.
>> edge (fallthru)
>> last goto2.c:55
>> goto goto2.c:55
>>
>> Now unrelated gotos all have the same file/line signature. Since the edge to the goto_locus is unrelated to the label itself.
>> 3. Assuming the test is fine and necessary I *could* work around the problem by recording the original edge somewhere (it is very important that all conditions in an expression share the same then/else basic blocks), or enough metadata to make a virtual edge, but that is a hack I hope I don't have to do.
>>
>> Anyway, the problem is not with the cfg construction itself, but an edge splitting that happens specifically for profiling.
>>
>> CC Martin, maybe you have any idea?
>>
>> Thanks,
>> Jørgen.
>
next prev parent reply other threads:[~2022-10-03 10:59 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-09-02 9:49 Jørgen Kvalsvik
2022-09-02 12:22 ` Richard Biener
2022-09-08 10:30 ` Jørgen Kvalsvik
2022-09-16 11:05 ` Jørgen Kvalsvik
2022-10-03 10:59 ` Martin Liška [this message]
2022-10-03 12:22 ` Jørgen Kvalsvik
2022-10-06 7:55 ` Richard Biener
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=a8200c9d-c3c5-addf-31a6-82e30ed2d4f8@suse.cz \
--to=mliska@suse.cz \
--cc=gcc@gcc.gnu.org \
--cc=j@lambda.is \
--cc=jh@suse.cz \
--cc=richard.guenther@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).