From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ed1-x52c.google.com (mail-ed1-x52c.google.com [IPv6:2a00:1450:4864:20::52c]) by sourceware.org (Postfix) with ESMTPS id B3ABC3858C20 for ; Tue, 11 Oct 2022 11:27:34 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org B3ABC3858C20 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-ed1-x52c.google.com with SMTP id w10so19670840edd.4 for ; Tue, 11 Oct 2022 04:27:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=HegLRS7omOuzipZimi792UgHnCYKFHy6ZJ5K/EvmS9g=; b=QPO81/2Sj9nvJruI50gY/e+bYly+OofmCk3v4ErwjLyabwHOYgcybRML9RuHH12Z4O eYlE2EdshApNZtNp+/D0uZ30ebfBA7ZMglnP/hg5klb+TCDYNpteHpdK8c7uTkxQWYCu +Mp7iH1Rn50AbjMN1H8E0wjbWv0+XnwKrpE+fn3ACZNRj0Grvplu+77b7gII4Yw/A/Jf scl7wiRrYFrTGWRypdQTc0LNnQTi6TedpL0lqRU3t27ejONJg1DvQrKLNb3XxraADfbo v2iY8u3MZOjK37UAK4v7Bn7hOslYpfS+sfXHR+g0vPQnlNXR1xhJw+ThkFLJ6Bac6YWZ DI7A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=HegLRS7omOuzipZimi792UgHnCYKFHy6ZJ5K/EvmS9g=; b=DJaLB3COckwopGBAv/jYK9F6Dut2WWtys+AXSQTyqfbW8L4PbNfNvIT1mJn2lZ3L/B dofbvxJhNiems6Brzkt6qFrlEuLCBLPAL4nG7O7XhhiJVteS605kuOQU7pENnY40mHaJ Laag8Tj1ikugJ6YLwEwvni+NLx1fXmff7S9owCIAJeoTaZ1O2kxiZFw3jCaEIWAZ1ZDD XFvh4Kk+QjqJcAXqj61T9WOiGk5vmRGRDoy/nuC6LUVT/HoJHQDT76WCYm/UsqJyVuwb xA92gVbb6odig1x1ZoLTH8uwW5vtS99xu0skPkQNAn9Cj9wHsLkxF2P8/S+fbULVJ7wN l9Dg== X-Gm-Message-State: ACrzQf06d7kezfZqAqcX9tNoj9rPcpm32oCEV7oXcIpj4fQSPvqy/1V7 gPWCjBSIoCsT7gWJVVaipDRSzLLTL4/t3IiEoCM= X-Google-Smtp-Source: AMsMyM5XmPluA7Hj4TZU4hj30BP52+YQ/Y8T7YLBUAal1r2lIis8MtMxLipH8Nfoi+/LKBY2CPVmLUiSwKM7bOdPd5A= X-Received: by 2002:a05:6402:27c9:b0:45c:3c77:8881 with SMTP id c9-20020a05640227c900b0045c3c778881mr6851717ede.250.1665487653038; Tue, 11 Oct 2022 04:27:33 -0700 (PDT) MIME-Version: 1.0 References: <20221005120403.68935-1-jorgen.kvalsvik@woven-planet.global> <20221005120403.68935-3-jorgen.kvalsvik@woven-planet.global> <97cd4512-9515-1860-266d-a0bfc809e85f@suse.cz> <6f5e10cb-12e3-823c-21bd-33d75777809c@woven-planet.global> <72022bc6-6c7f-0b30-9fff-c2b6807d0d93@woven-planet.global> In-Reply-To: <72022bc6-6c7f-0b30-9fff-c2b6807d0d93@woven-planet.global> From: Richard Biener Date: Tue, 11 Oct 2022 13:27:20 +0200 Message-ID: Subject: Re: [PATCH 2/2] Split edge when edge locus and dest don't match To: =?UTF-8?Q?J=C3=B8rgen_Kvalsvik?= Cc: =?UTF-8?Q?Martin_Li=C5=A1ka?= , gcc-patches@gcc.gnu.org Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Status: No, score=-8.1 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Tue, Oct 11, 2022 at 12:57 PM J=C3=B8rgen Kvalsvik wrote: > > On 07/10/2022 13:45, J=C3=B8rgen Kvalsvik wrote: > > On 07/10/2022 08:53, Richard Biener wrote: > >> On Thu, Oct 6, 2022 at 4:28 PM J=C3=B8rgen Kvalsvik > >> wrote: > >>> > >>> On 06/10/2022 10:12, Richard Biener wrote: > >>>> On Wed, Oct 5, 2022 at 2:49 PM Martin Li=C5=A1ka wr= ote: > >>>>> > >>>>> On 10/5/22 14:04, J=C3=B8rgen Kvalsvik via Gcc-patches wrote: > >>>>>> Edges with locus are candidates for splitting so that the edge wit= h > >>>>>> locus is the only edge out of a basic block, except when the locus= es > >>>>>> match. The test checks the last (non-debug) statement in a basic b= lock, > >>>>>> but this causes an unnecessary split when the edge locus go to a b= lock > >>>>>> 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 =3D 0; > >>>>>> 3 if (a && b) { > >>>>>> 4 x =3D a; > >>>>>> 5 } else { > >>>>>> 6 a_: > >>>>>> 7 x =3D (a - b); > >>>>>> 8 } > >>>>>> 9 > >>>>>> 10 return x; > >>>>>> 11 } > >>>>>> > >>>>>> block file line col stmt > >>>>>> > >>>>>> src t.c 3 10 if (a_3(D) !=3D 0) > >>>>>> edge t.c 6 1 > >>>>>> dest t.c 6 1 a_: > >>>>>> > >>>>>> src t.c 3 13 if (b_4(D) !=3D 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 =3D 0; > >>>>>> 3 if (a && b) { > >>>>>> 4 x =3D a; > >>>>>> 5 } else { > >>>>>> 6 // a_: <- label removed > >>>>>> 7 x =3D (a - b); > >>>>>> 8 } > >>>>>> 9 > >>>>>> 10 return x; > >>>>>> 11 > >>>>>> > >>>>>> block file line col stmt > >>>>>> > >>>>>> src t.c 3 10 if (a_3(D) !=3D 0) > >>>>>> edge (null) 0 0 > >>>>>> dest t.c 6 1 a_: > >>>>>> > >>>>>> src t.c 3 13 if (b_4(D) !=3D 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 =3D 0; > >>>>>> 209 > >>>>>> 210 switch (i) /* branch(80 25) = */ > >>>>>> 211 /* branch(end) */ > >>>>>> 212 { > >>>>>> 213 case 1: > >>>>>> 214 result =3D do_something (2); > >>>>>> 215 break; > >>>>>> 216 case 2: > >>>>>> 217 result =3D do_something (1024); > >>>>>> 218 break; > >>>>>> 219 case 3: > >>>>>> 220 case 4: > >>>>>> 221 if (j =3D=3D 2) /* branch(67)= */ > >>>>>> 222 /* branch(end) */ > >>>>>> 223 return do_something (4); > >>>>>> 224 result =3D do_something (8); > >>>>>> 225 break; > >>>>>> 226 default: > >>>>>> 227 result =3D 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 =3D do_something (2); > >>>>>> edge 4b.c 215 9 > >>>>>> dst 4b.c 231 10 _22 =3D result_3; > >>>>>> > >>>>>> src 4b.c 217 18 result_16 =3D do_something (1024); > >>>>>> edge 4b.c 218 9 > >>>>>> dst 4b.c 231 10 _22 =3D result_3; > >>>>>> > >>>>>> src 4b.c 224 18 result_12 =3D do_something (8); > >>>>>> edge 4b.c 225 9 > >>>>>> dst 4b.c 231 10 _22 =3D 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 m= atches > >>>>>> 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, no= t 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 =3D NULL; > >>>>>> + gimple *dest =3D NULL; > >>>>>> > >>>>>> /* It may happen that there are compiler generated sta= tements > >>>>>> 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 =3D gsi_last_nondebug_bb (bb); > >>>>>> + for (gsi =3D gsi_start_nondebug_bb (bb); > >>>> > >>>> ^^^ and you are looking at the branch block stmts (bb), not the dest= ination > >>>> block stmts (e->dest) > >>>> > >>>>>> !gsi_end_p (gsi); > >>>>>> - gsi_prev_nondebug (&gsi)) > >>>>>> + gsi_next_nondebug (&gsi)) > >>>>>> { > >>>>>> - last =3D gsi_stmt (gsi); > >>>>>> - if (!RESERVED_LOCATION_P (gimple_location (last))) > >>>>>> + dest =3D 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) > >>>>>> - !=3D LOCATION_FILE (gimple_location (last)) > >>>>>> + !=3D LOCATION_FILE (gimple_location (dest)) > >>>>>> || (LOCATION_LINE (e->goto_locus) > >>>>>> - !=3D LOCATION_LINE (gimple_location (last)= )))) > >>>>>> + !=3D 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 'de= st' 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 for= tunately > >>> nothing to revert. > >>> > >>>> I don't see how it's a win to disregard 'last' and only consider 'de= st' 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 wron= g (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, th= e only > >>> difference in the test suite happens on break in switches. I'll tinke= r a bit > >>> more to see if I can figure out what's going on or if the heuristic c= an > >>> otherwise be improved. > >>> > >>> Then, when does a block with a goto_locus edge have multiple successo= rs? 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 multip= le > >>> 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 s= tmt or the > >> locus of the stmt the control transfers to. The most important case i= s 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 in= strument > >> different locations with different counters and since we cannot have c= ounters 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 whic= h > >> 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 instrume= ntation. > >> The interesting case is probably computed goto (which has multiple suc= cessors) > >> 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 lo= cations. > >> > >> 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 tes= t case, > > if anything to catch regressions. Naturally, it fails when the split do= es 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 - eith= er, 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 =3D do_something (i); > > + } > > + else > > + { > > +first: /* count(1) */ > > + j =3D do_something (j); /* count(2) */ > > + if (j) /* count(2) */ > > + { > > + j =3D 0; /* count(1) */ > > + goto top; /* count(1) */ > > + } > > + } > > + return 16; > > +} > > + > > void > > call_goto () > > { > > @@ -117,6 +140,7 @@ call_goto () > > goto_val +=3D test_goto1 (1); > > goto_val +=3D test_goto2 (3); > > goto_val +=3D test_goto2 (30); > > + goto_val +=3D test_goto3 (0, 1); > > } > > > > /* Check nested if-then-else statements. */ > > @@ -260,7 +284,7 @@ main() > > call_unref (); > > if ((for_val1 !=3D 12) > > || (for_val2 !=3D 87) > > - || (goto_val !=3D 15) > > + || (goto_val !=3D 31) > > || (ifelse_val1 !=3D 31) > > || (ifelse_val2 !=3D 23) > > || (ifelse_val3 !=3D 246) > > > > What do you think? > > > > Thanks, > > J=C3=B8rgen > > Hello, > > After tinkering a bit more I figured out a patch I could do to merge thes= e > 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 lo= nger 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=C3=B8rgen