Re: [PATCH 2/2] Split edge when edge locus and dest don't match

["Jørgen Kvalsvik" <jorgen.kvalsvik@woven-planet.global>]

On 07/10/2022 13:45, Jørgen Kvalsvik wrote:
> On 07/10/2022 08:53, Richard Biener wrote:
>> On Thu, Oct 6, 2022 at 4:28 PM Jørgen Kvalsvik
>> <jorgen.kvalsvik@woven-planet.global> wrote:
>>>
>>> On 06/10/2022 10:12, Richard Biener wrote:
>>>> On Wed, Oct 5, 2022 at 2:49 PM Martin Liška <mliska@suse.cz> wrote:
>>>>>
>>>>> On 10/5/22 14:04, Jørgen Kvalsvik via Gcc-patches wrote:
>>>>>> Edges with locus are candidates for splitting so that the edge with
>>>>>> locus is the only edge out of a basic block, except when the locuses
>>>>>> match. The test checks the last (non-debug) statement in a basic block,
>>>>>> but this causes an unnecessary split when the edge locus go to a block
>>>>>> which coincidentally has an unrelated label. Comparing the first
>>>>>> statement of the destination block is the same check but does not get
>>>>>> tripped up by labels.
>>>>>>
>>>>>> An example with source/edge/dest locus when an edge is split:
>>>>>>
>>>>>>       1  int fn (int a, int b, int c) {
>>>>>>       2        int x = 0;
>>>>>>       3        if (a && b) {
>>>>>>       4                x = a;
>>>>>>       5        } else {
>>>>>>       6  a_:
>>>>>>       7            x = (a - b);
>>>>>>       8        }
>>>>>>       9
>>>>>>      10        return x;
>>>>>>      11  }
>>>>>>
>>>>>> block  file  line   col  stmt
>>>>>>
>>>>>> src     t.c     3    10  if (a_3(D) != 0)
>>>>>> edge    t.c     6     1
>>>>>> dest    t.c     6     1  a_:
>>>>>>
>>>>>> src     t.c     3    13  if (b_4(D) != 0)
>>>>>> edge    t.c     6     1
>>>>>> dst     t.c     6     1  a_:
>>>>>>
>>>>>> With label removed:
>>>>>>
>>>>>>       1  int fn (int a, int b, int c) {
>>>>>>       2        int x = 0;
>>>>>>       3        if (a && b) {
>>>>>>       4                x = a;
>>>>>>       5        } else {
>>>>>>       6  // a_: <- label removed
>>>>>>       7            x = (a - b);
>>>>>>       8        }
>>>>>>       9
>>>>>>      10        return x;
>>>>>>      11
>>>>>>
>>>>>> block  file  line   col  stmt
>>>>>>
>>>>>> src     t.c     3    10  if (a_3(D) != 0)
>>>>>> edge  (null)    0     0
>>>>>> dest    t.c     6     1  a_:
>>>>>>
>>>>>> src     t.c     3    13  if (b_4(D) != 0)
>>>>>> edge  (null)    0     0
>>>>>> dst     t.c     6     1  a_:
>>>>>>
>>>>>> and this is extract from gcov-4b.c which *should* split:
>>>>>>
>>>>>>     205  int
>>>>>>     206  test_switch (int i, int j)
>>>>>>     207  {
>>>>>>     208    int result = 0;
>>>>>>     209
>>>>>>     210    switch (i)                            /* branch(80 25) */
>>>>>>     211                                          /* branch(end) */
>>>>>>     212      {
>>>>>>     213        case 1:
>>>>>>     214          result = do_something (2);
>>>>>>     215          break;
>>>>>>     216        case 2:
>>>>>>     217          result = do_something (1024);
>>>>>>     218          break;
>>>>>>     219        case 3:
>>>>>>     220        case 4:
>>>>>>     221          if (j == 2)                     /* branch(67) */
>>>>>>     222                                          /* branch(end) */
>>>>>>     223            return do_something (4);
>>>>>>     224          result = do_something (8);
>>>>>>     225          break;
>>>>>>     226        default:
>>>>>>     227          result = do_something (32);
>>>>>>     228          switch_m++;
>>>>>>     229          break;
>>>>>>     230      }
>>>>>>     231    return result;
>>>>>>     231  }
>>>>>>
>>>>>> block  file  line   col  stmt
>>>>>>
>>>>>> src    4b.c   214    18  result_18 = do_something (2);
>>>>>> edge   4b.c   215     9
>>>>>> dst    4b.c   231    10  _22 = result_3;
>>>>>>
>>>>>> src    4b.c   217    18  result_16 = do_something (1024);
>>>>>> edge   4b.c   218     9
>>>>>> dst    4b.c   231    10  _22 = result_3;
>>>>>>
>>>>>> src    4b.c   224    18  result_12 = do_something (8);
>>>>>> edge   4b.c   225     9
>>>>>> dst    4b.c   231    10  _22 = result_3;
>>>>>>
>>>>>> Note that the behaviour of comparison is preserved for the (switch) edge
>>>>>> splitting case. The former case now fails the check (even though
>>>>>> e->goto_locus is no longer a reserved location) because the dest matches
>>>>>> the e->locus.
>>>>>
>>>>> It's fine, please install it.
>>>>> I verified tramp3d coverage output is the same as before the patch.
>>>>>
>>>>> Martin
>>>>>
>>>>>>
>>>>>> gcc/ChangeLog:
>>>>>>
>>>>>>         * profile.cc (branch_prob): Compare edge locus to dest, not src.
>>>>>> ---
>>>>>>  gcc/profile.cc | 18 +++++++++---------
>>>>>>  1 file changed, 9 insertions(+), 9 deletions(-)
>>>>>>
>>>>>> diff --git a/gcc/profile.cc b/gcc/profile.cc
>>>>>> index 96121d60711..c13a79a84c2 100644
>>>>>> --- a/gcc/profile.cc
>>>>>> +++ b/gcc/profile.cc
>>>>>> @@ -1208,17 +1208,17 @@ branch_prob (bool thunk)
>>>>>>         FOR_EACH_EDGE (e, ei, bb->succs)
>>>>>>           {
>>>>>>             gimple_stmt_iterator gsi;
>>>>>> -           gimple *last = NULL;
>>>>>> +           gimple *dest = NULL;
>>>>>>
>>>>>>             /* It may happen that there are compiler generated statements
>>>>>>                without a locus at all.  Go through the basic block from the
>>>>>>                last to the first statement looking for a locus.  */
>>>>
>>>> The comment no longer matches the code.>
>>>>>> -           for (gsi = gsi_last_nondebug_bb (bb);
>>>>>> +           for (gsi = gsi_start_nondebug_bb (bb);
>>>>
>>>> ^^^ and you are looking at the branch block stmts (bb), not the destination
>>>> block stmts (e->dest)
>>>>
>>>>>>                  !gsi_end_p (gsi);
>>>>>> -                gsi_prev_nondebug (&gsi))
>>>>>> +                gsi_next_nondebug (&gsi))
>>>>>>               {
>>>>>> -               last = gsi_stmt (gsi);
>>>>>> -               if (!RESERVED_LOCATION_P (gimple_location (last)))
>>>>>> +               dest = gsi_stmt (gsi);
>>>>>> +               if (!RESERVED_LOCATION_P (gimple_location (dest)))
>>>>>>                   break;
>>>>>>               }
>>>>>>
>>>>>> @@ -1227,14 +1227,14 @@ branch_prob (bool thunk)
>>>>>>                Don't do that when the locuses match, so
>>>>>>                if (blah) goto something;
>>>>>>                is not computed twice.  */
>>>>>> -           if (last
>>>>>> -               && gimple_has_location (last)
>>>>>> +           if (dest
>>>>>> +               && gimple_has_location (dest)
>>>>>>                 && !RESERVED_LOCATION_P (e->goto_locus)
>>>>>>                 && !single_succ_p (bb)
>>>>>>                 && (LOCATION_FILE (e->goto_locus)
>>>>>> -                   != LOCATION_FILE (gimple_location (last))
>>>>>> +                   != LOCATION_FILE (gimple_location (dest))
>>>>>>                     || (LOCATION_LINE (e->goto_locus)
>>>>>> -                       != LOCATION_LINE (gimple_location (last)))))
>>>>>> +                       != LOCATION_LINE (gimple_location (dest)))))
>>>>
>>>> this heuristic needs to be in sync with how we insert edge counters
>>>> which seems to be hidden in the MST compute (and/or edge insertion).
>>>> I don't see how it's a win to disregard 'last' and only consider 'dest' here.
>>>>
>>>> I think the patch is wrong.  Please revert if you applied it already.
>>>
>>> I haven't applied it yet, so unless someone beat me to it there's fortunately
>>> nothing to revert.
>>>
>>>> I don't see how it's a win to disregard 'last' and only consider 'dest' here.
>>>
>>> It might not be other than that it unbreaks my condition profiling by not
>>> splitting condition edges and apparently doesn't cause a regression (one caught
>>> by tests anyway). That being said the heuristic may very well be wrong (as is
>>> the implementation since it considers bb and not e->dest, although I'm sure I
>>> tested it with e->dest at some point).
>>>
>>> I guess the most important question is if the if (a && b) {} {label:} edges
>>> should be split in the first place. As mentioned in the patch set, the only
>>> difference in the test suite happens on break in switches. I'll tinker a bit
>>> more to see if I can figure out what's going on or if the heuristic can
>>> otherwise be improved.
>>>
>>> Then, when does a block with a goto_locus edge have multiple successors? From my
>>> previous testing it doesn't seem like it's the conditions make a goto_locus, but
>>> it's more than just plain gotos right? When would it then have multiple
>>> successors? Switches and exception handling? If that's the case then maybe the
>>> heuristic can be improved by simply checking the edge type.
>>
>> The goto_locus of an edge is usually either the locus of the control stmt or the
>> locus of the stmt the control transfers to.  The most important case is for
>> 'goto' stmts themselves since those are elided and become edges (thus
>> 'goto_locus').
>>
>> My understanding as of why we split edges at all is that we want to instrument
>> different locations with different counters and since we cannot have counters on
>> edges itself but have to either insert the counter on the source or
>> the destination
>> we in some cases have to split the edge to create an insert location
>> to not falsely
>> account.  instrument_edges seems to simply use gsi_insert_on_edge which
>> inserts with the gimple_find_edge_insert_loc logic which doesn't look
>> at goto_locus
>> at all.  So the existing heuristic must be fragile as well.
>>
>> BUT - as you say, the plain goto shouldn't be subject to edge instrumentation.
>> The interesting case is probably computed goto (which has multiple successors)
>> and from what I can see a branch where we take the goto_locus from the
>> COND_EXPRs then/else goto stmt which in theory could have different locations.
>>
>> I don't fully understand your requirement of not splitting edges -
>> I'll just note that
>> the place you are patching is not the only place where edges are split (but
>> the insert location computation only sees those splits).
>>
>> Richard.
> 
> Ok, I think I understand. To move forward I propose this additional test case,
> if anything to catch regressions. Naturally, it fails when the split does not
> happen because the 'first' label gets incremented twice (I'll probably rename it
> pre application, assuming it gets approved) not once.
> 
> This also means I need to change strategy for condition coverage - either, I
> must snapshot these splits and make a mapping table for the "original"
> identities or maybe run the analysis before this splitting happens.
> 
> 
> diff --git a/gcc/testsuite/gcc.misc-tests/gcov-4.c
> b/gcc/testsuite/gcc.misc-tests/gcov-4.c
> index 498d299b66b..b1dc29b573a 100644
> --- a/gcc/testsuite/gcc.misc-tests/gcov-4.c
> +++ b/gcc/testsuite/gcc.misc-tests/gcov-4.c
> @@ -110,6 +110,29 @@ lab2:
>    return 8;				/* count(1) */
>  }
> 
> +int
> +test_goto3 (int i, int j)
> +{
> +    if (j) goto first;		/* count(1) */
> +
> +top:
> +    if (i)			/* count(1) */
> +      {
> +	i = do_something (i);
> +      }
> +    else
> +      {
> +first:				/* count(1) */
> +	j = do_something (j);	/* count(2) */
> +	if (j)			/* count(2) */
> +	  {
> +	    j = 0;		/* count(1) */
> +	    goto top;		/* count(1) */
> +	  }
> +      }
> +    return 16;
> +}
> +
>  void
>  call_goto ()
>  {
> @@ -117,6 +140,7 @@ call_goto ()
>    goto_val += test_goto1 (1);
>    goto_val += test_goto2 (3);
>    goto_val += test_goto2 (30);
> +  goto_val += test_goto3 (0, 1);
>  }
> 
>  /* Check nested if-then-else statements. */
> @@ -260,7 +284,7 @@ main()
>    call_unref ();
>    if ((for_val1 != 12)
>        || (for_val2 != 87)
> -      || (goto_val != 15)
> +      || (goto_val != 31)
>        || (ifelse_val1 != 31)
>        || (ifelse_val2 != 23)
>        || (ifelse_val3 != 246)
> 
> What do you think?
> 
> Thanks,
> Jørgen

Hello,

After tinkering a bit more I figured out a patch I could do to merge these
splits in the condition coverage code, rather than relying on the splits not
happening. I still think the tests are a good addition, but there's no longer a
reason for me to change the splitting heuristics.

Should I prepare a separate patch set for the tests?

Thanks,
Jørgen