Re: Surprising CFG construction with goto from then to else

["Jørgen Kvalsvik" <j@lambda.is>]

Gentle ping. Any idea if the edge split is still useful and/or how to 
test for it?

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.