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

[Richard Biener <richard.guenther@gmail.com>]

On Tue, Oct 11, 2022 at 12:57 PM Jørgen Kvalsvik
<jorgen.kvalsvik@woven-planet.global> wrote:
>
> 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?

Yes, enhancing test coverage is always good and should be done
separately.

Thanks a lot,
Richard.

>
> Thanks,
> Jørgen