From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf1-x135.google.com (mail-lf1-x135.google.com [IPv6:2a00:1450:4864:20::135]) by sourceware.org (Postfix) with ESMTPS id F23E43858C20 for ; Tue, 11 Oct 2022 10:57:12 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org F23E43858C20 Authentication-Results: sourceware.org; dmarc=fail (p=none dis=none) header.from=woven-planet.global Authentication-Results: sourceware.org; spf=fail smtp.mailfrom=woven-planet.global Received: by mail-lf1-x135.google.com with SMTP id s20so20483912lfi.11 for ; Tue, 11 Oct 2022 03:57:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=woven-planet.global; s=google; h=content-transfer-encoding:in-reply-to:content-language:references :cc:to:from:subject:user-agent:mime-version:date:message-id:from:to :cc:subject:date:message-id:reply-to; bh=r7SEP6KeSgt85geHJjF8pwrmM1s0SqiAkcM3JPfqPVo=; b=euMV73ULj8I/kU9JZ3Q0sird93VsWU+5QfehZMCd2AjKsvdJtizZ26P+cReuD72GhZ fhlw8mGZnOeSsm3Yq1RKV9ytTqTMp4x4JhXSboDfcxXGSBpMWZl0tArE04xi/78dAkU8 OUsUgp4w1QI++/v8c7ydryWY3yubTAgvORDwA= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:in-reply-to:content-language:references :cc:to:from:subject:user-agent:mime-version:date:message-id :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=r7SEP6KeSgt85geHJjF8pwrmM1s0SqiAkcM3JPfqPVo=; b=OI/JYzEYBY0oi2z3wRTeaws7OiOXZUcn6/F3UZs1wKwxCuWCCgURHtGS72JX7wkX92 E/Udym+GVV9P2N7bWL95W14cQ2GAtNooeSB3ylReAMzjbxZeiHhfUFKElkFga8kwsNrH WC3ldCExL0mheVURAQFRmO5ywF/RcdLrS0gxf159qkwEj3WS3Cp1tE9KJF6RluJPuApd MFdF4aUe3ZSx4U1XvwhJflNknH2M1xyCyGfTBQSzb2LAxs62mUpCM3VdVq73rBE1Sgbu g10YcfYdBoEjSe6IYKXxZhH9nAFNhbxQSo+tsmcXnsft+sqaeMZCSJURXa0BplnwzH3S TcdA== X-Gm-Message-State: ACrzQf1ZSKlrcQUSFJ65nwM3qFcHEtD6oeIcfbsm8ArqMznITuOh0Uj3 Kq5HAK/wuBFjitmy8AtceLAm1g== X-Google-Smtp-Source: AMsMyM4Bqyyt2aTtB0soCItpPYX14wzY2dRwMdTuj9Gyup0mHMiz5/xrinxfjG0Lvfd2Tz4FGQxwuw== X-Received: by 2002:ac2:4ecc:0:b0:4a2:2ed2:9400 with SMTP id p12-20020ac24ecc000000b004a22ed29400mr8552311lfr.432.1665485831427; Tue, 11 Oct 2022 03:57:11 -0700 (PDT) Received: from [172.16.8.240] ([85.252.14.111]) by smtp.gmail.com with ESMTPSA id c9-20020ac244a9000000b0048cf43c3a85sm1810166lfm.238.2022.10.11.03.57.10 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 11 Oct 2022 03:57:10 -0700 (PDT) Message-ID: <72022bc6-6c7f-0b30-9fff-c2b6807d0d93@woven-planet.global> Date: Tue, 11 Oct 2022 12:57:07 +0200 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.3.2 Subject: Re: [PATCH 2/2] Split edge when edge locus and dest don't match From: =?UTF-8?Q?J=c3=b8rgen_Kvalsvik?= To: Richard Biener Cc: =?UTF-8?Q?Martin_Li=c5=a1ka?= , gcc-patches@gcc.gnu.org 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> Content-Language: en-US In-Reply-To: <6f5e10cb-12e3-823c-21bd-33d75777809c@woven-planet.global> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-13.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,GIT_PATCH_0,NICE_REPLY_A,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,TXREP,T_SPF_PERMERROR 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 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 >> wrote: >>> >>> On 06/10/2022 10:12, Richard Biener wrote: >>>> On Wed, Oct 5, 2022 at 2:49 PM Martin Liška 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