From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp-out2.suse.de (smtp-out2.suse.de [195.135.220.29]) by sourceware.org (Postfix) with ESMTPS id 8180B3858D3C for ; Thu, 24 Mar 2022 16:08:44 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 8180B3858D3C Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=suse.cz Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=suse.cz Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by smtp-out2.suse.de (Postfix) with ESMTPS id 3A93C1F38D; Thu, 24 Mar 2022 16:08:43 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1648138123; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=NSJgYV1CdIxY4ERJlV+3yuzApgSg/kZXK7XK20GhmmE=; b=CGZNgDSpIN5j75DeIAjgmWPk8gFErLHIHERe/VEMr7uYBxBl1Q6rYGs/4uqtdGyyshY20y NchFCBW8W9kKddh8kXdByxmO/+qWGOP5HKv+KRK6+Xqon6dk1A6LJ6AK3RHnant4CLDDAz mKumBWbbWuq8sjDuZ4hmx2JQiMfWTmU= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1648138123; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=NSJgYV1CdIxY4ERJlV+3yuzApgSg/kZXK7XK20GhmmE=; b=jankHq1rocdtZYVNZmWSVQeCrJD8TgEAyFnxXInbI0zTJywoOVoCYQ8pj2tuekUpTKCk8h WcOv4YrwW21+aSCA== Received: from imap2.suse-dmz.suse.de (imap2.suse-dmz.suse.de [192.168.254.74]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-521) server-digest SHA512) (No client certificate requested) by imap2.suse-dmz.suse.de (Postfix) with ESMTPS id 28F2612FF7; Thu, 24 Mar 2022 16:08:43 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap2.suse-dmz.suse.de with ESMTPSA id OsbsCIuXPGKhOAAAMHmgww (envelope-from ); Thu, 24 Mar 2022 16:08:43 +0000 Message-ID: Date: Thu, 24 Mar 2022 17:08:42 +0100 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:91.0) Gecko/20100101 Thunderbird/91.7.0 Subject: Re: [PATCH] Add condition coverage profiling Content-Language: en-US To: =?UTF-8?Q?J=c3=b8rgen_Kvalsvik?= , gcc-patches@gcc.gnu.org References: From: =?UTF-8?Q?Martin_Li=c5=a1ka?= In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-5.8 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, KAM_SHORT, NICE_REPLY_A, SPF_HELO_NONE, SPF_PASS, TXREP, T_SCC_BODY_TEXT_LINE, WEIRD_PORT autolearn=ham autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 24 Mar 2022 16:08:46 -0000 On 3/21/22 12:55, Jørgen Kvalsvik via Gcc-patches wrote: Hello. Thanks for very interesting extension of the existing GCOV profiling. I briefly read the patch and investigated what happens and I've got various questions/comments about it: 1) Do I correctly understand that __conditions_accu_true/false track every short-circuit sub-expression of a condition and record if a given sub-expr is seen to be true or false? 2) As mentioned these are bit sets, can you please explain why you (& -value) from these sets? 3) I noticed a false report for a simple test-case: $ cat cond.c int x; void foo (int a, int b) { if (a || b) x = 1; else x = 2; } int main() { foo (0, 1); return 0; } $ rm *gcda ; gcc --coverage cond.c -fprofile-conditions && ./a.out && gcov -g -t a-cond.c -: 0:Source:cond.c -: 0:Graph:a-cond.gcno -: 0:Data:a-cond.gcda -: 0:Runs:1 -: 1:int x; -: 2: 1: 3:void foo (int a, int b) -: 4:{ 1: 5: if (a || b) conditions covered 1/4 condition 0 not covered (true) condition 0 not covered (false) <-- this was executed if I'm correct condition 1 not covered (false) 1: 6: x = 1; -: 7: else #####: 8: x = 2; 1: 9:} -: 10: 1: 11:int main() -: 12:{ 1: 13: foo (0, 1); 1: 14: return 0; -: 15:} 4) I noticed various CFG patterns in tree-profile.cc which are handled. Can you please explain how the algorithm works even without knowing the original paper? 5) I noticed the following ICE: $ gcc cond.c -fprofile-conditions -fprofile-generate during IPA pass: profile cond.c: In function ‘foo’: cond.c:15:1: internal compiler error: Segmentation fault 15 | } | ^ 0xf4d64a crash_signal /home/marxin/Programming/gcc/gcc/toplev.cc:322 0x7ffff78b93cf ??? /usr/src/debug/glibc-2.35-2.1.x86_64/signal/../sysdeps/unix/sysv/linux/x86_64/libc_sigaction.c:0 0x7ffff78f29ed __GI__IO_ftell /usr/src/debug/glibc-2.35-2.1.x86_64/libio/ioftell.c:37 0xa9dfda gcov_position /home/marxin/Programming/gcc/gcc/gcov-io.cc:48 0xa9dfda gcov_write_tag(unsigned int) /home/marxin/Programming/gcc/gcc/gcov-io.cc:321 0xe9734a branch_prob(bool) /home/marxin/Programming/gcc/gcc/profile.cc:1542 0x1032e08 tree_profiling /home/marxin/Programming/gcc/gcc/tree-profile.cc:1620 0x1032e08 execute /home/marxin/Programming/gcc/gcc/tree-profile.cc:1726 Please submit a full bug report, with preprocessed source (by using -freport-bug). Please include the complete backtrace with any bug report. See for instructions. 6) Please follow the GNU coding style, most notable we replace 8 spaces with a tab. And we break line before {, (, ... Remove noexcept specifiers for functions and I think most of the newly added functions can be static. And each newly added function should have a comment. 7) Please consider supporting of -profile-update=atomic where you'll need to utilize an atomic builts (see how other instrumentation looks like with it). That's the very first round of the review. Hope it's helpful. Cheers, Martin > This patch adds support in gcc+gcov for modified condition/decision > coverage (MC/DC) with the -fprofile-conditions flag. MC/DC is a type of > test/code coverage, and it is particularly important in the avation and > automotive industries for safety-critical applications. In particular, > it is required or recommended by: > > * DO-178C for the most critical software (Level A) in avionics > * IEC 61508 for SIL 4 > * ISO 26262-6 for ASIL D > > From the SQLite webpage: > > Two methods of measuring test coverage were described above: > "statement" and "branch" coverage. There are many other test > coverage metrics besides these two. Another popular metric is > "Modified Condition/Decision Coverage" or MC/DC. Wikipedia defines > MC/DC as follows: > > * Each decision tries every possible outcome. > * Each condition in a decision takes on every possible outcome. > * Each entry and exit point is invoked. > * Each condition in a decision is shown to independently affect > the outcome of the decision. > > In the C programming language where && and || are "short-circuit" > operators, MC/DC and branch coverage are very nearly the same thing. > The primary difference is in boolean vector tests. One can test for > any of several bits in bit-vector and still obtain 100% branch test > coverage even though the second element of MC/DC - the requirement > that each condition in a decision take on every possible outcome - > might not be satisfied. > > https://sqlite.org/testing.html#mcdc > > Wahlen, Heimdahl, and De Silva "Efficient Test Coverage Measurement for > MC/DC" describes an algorithm for adding instrumentation by carrying > over information from the AST, but my algorithm does analysis on the > control flow graph. This should make it work for any language gcc > supports, although I have only tested it on constructs in C and C++, see > testsuite/gcc.misc-tests and testsuite/g++.dg. > > Like Wahlen et al this implementation uses bitsets to store conditions, > which gcov later interprets. This is very fast, but introduces an max > limit for the number of terms in a single boolean expression. This limit > is the number of bits in a gcov_unsigned_type (which is typedef'd to > uint64_t), so for most practical purposes this would be acceptable. > limitation can be relaxed with a more sophisticated way of storing and > updating bitsets (for example length-encoding). > > In action it looks pretty similar to the branch coverage. The -g short > opt carries no significance, but was chosen because it was an available > option with the upper-case free too. > > gcov --conditions: > > 3: 17:void fn (int a, int b, int c, int d) { > 3: 18: if ((a && (b || c)) && d) > conditions covered 5/8 > condition 1 not covered (false) > condition 2 not covered (true) > condition 2 not covered (false) > 1: 19: x = 1; > -: 20: else > 2: 21: x = 2; > 3: 22:} > > gcov --conditions --json-format: > > "conditions": [ > { > "not_covered_false": [ > 1, > 2 > ], > "count": 8, > "covered": 5, > "not_covered_true": [ > 2 > ] > } > ], > > C++ destructors will add extra conditionals that are not explicitly > present in source code. These are present in the CFG, which means the > condition coverage will show them. > > gcov --conditions > > -: 5:struct A { > 1: 6: explicit A (int x) : v (x) {} > 1: 7: operator bool () const { return bool(v); } > 1: 8: ~A() {} > -: 9: > -: 10: int v; > -: 11:}; > -: 12: > 2: 13:void fn (int a, int b) { > 2*: 14: x = a && A(b); > conditions covered 2/4 > condition 0 not covered (true) > condition 1 not covered (true) > conditions covered 2/2 > > They are also reported by the branch coverage. > > gcov -bc > > 2*: 14: x = a && A(b); > branch 0 taken 1 (fallthrough) > branch 1 taken 1 > call 2 returned 1 > call 3 returned 1 > branch 4 taken 0 (fallthrough) > branch 5 taken 1 > branch 6 taken 1 (fallthrough) > branch 7 taken 1 > > The algorithm struggles in a particular case where gcc would generate > identical CFGs for different expressions: > > and.c: > > if (a && b && c) > x = 1; > > ifs.c: > > if (a) > if (b) > if (c) > x = 1; > > if (a && b && c) > x = 1; > > and.c.gcov: > > #####: 2: if (a && b && c) > conditions covered 2/2 > conditions covered 2/2 > conditions covered 2/2 > #####: 3: x = 1; > > ifs.c.gcov: > #####: 2: if (a) > conditions covered 2/2 > #####: 3: 2 if (b) > conditions covered 2/2 > #####: 4: 2 if (c) > conditions covered 2/2 > #####: 5: x = 1; > > These programs are semantically equivalent, and are interpreted as 3 > separate conditional expressions. It does not matter w.r.t. coverage, > but is not ideal. Adding an else to and.c fixes the issue: > > #####: 2: if (a && b && c) > conditions covered 6/6 > #####: 3: x = 1; > #####: 4: else x = x; > > In the (a && b && c) case the else block must be shared between all > three conditionals, and for if (a) if (b) if (c) there would be three > *separate* else blocks. > > Since the algorithm works on CFGs, it cannot detect conditionals (from > ternaries) that don't get an entry in the cfg. For example, > int x = a ? 0 : 1 in gimple becomes _x = (_a == 0). From source you > would expect coverage, but it gets neither branch nor condition > coverage. For completeness, it could be achieved by scanning all gimple > statements for comparisons, and insert an extra instruction for > recording the outcome. > > The test suite consists of all different CFG kinds and control flow > structures I could find, but there is certainly room for many more. > > Alternative email: Jørgen Kvalsvik > > -- > > Some final remarks (not a part of the commit message), this is written in a C++ style that I felt meshed well with what was already there, but if the maintainers would prefer a different approach then I'm happy to to make adjustments. I plan to write a more thorough description of the algorithm, as well as adding the same feature to clang as it is very useful for us at Woven Planet. > > I tried to pick flag names and options that were comfortable and descriptive, but if you have better names or different ideas for flags then I am happy to change them. The --coverage flag was not changed to imply -fprofile-conditions, but it is possibly something to consider. > > gcc/ChangeLog: > > * common.opt: Add new options -fprofile-conditions and > -Wcoverage-too-many-conditions. > * doc/gcov.texi: Add --conditions documentation. > * doc/invoke.texi: Add -fprofile-conditions documentation. > * gcov-counter.def (GCOV_COUNTER_CONDS): New. > * gcov-io.h (GCOV_TAG_CONDS): New. > (GCOV_TAG_CONDS_LENGTH): Likewise. > (GCOV_TAG_CONDS_NUM): Likewise. > * gcov.cc (class condition_info): New. > (condition_info::condition_info): New. > (condition_info::popcount): New. > (struct coverage_info): New. > (add_condition_counts): New. > (output_conditions): New. > (print_usage): Add -g, --conditions. > (process_args): Likewise. > (output_intermediate_json_line): Output conditions. > (read_graph_file): Read conditions counters. > (read_count_file): Read conditions counters. > (file_summary): Print conditions. > (accumulate_line_info): Accumulate conditions. > (output_line_details): Print conditions. > * profile.cc (find_conditions): New declaration. > (instrument_decisions): New declaration. > (branch_prob): Call find_conditions, instrument_decisions. > (init_branch_prob): Add total_num_conds. > (end_branch_prob): Likewise. > * tree-profile.cc (INCLUDE_ALGORITHM): Define. > (struct conds_ctx): New. > (CONDITIONS_MAX_TERMS): New. > (index_of): New. > (index_lt): New. > (single): New. > (single_edge): New. > (contract_edge): New. > (contract_edge_up): New. > (is_conditional_p): New. > (collect_neighbors): New. > (find_first_conditional): New. > (emit_bitwise_op): New. > (collect_conditions): New. > (find_conditions): New. > (instrument_decisions): New. > > gcc/testsuite/ChangeLog: > > * lib/gcov.exp: > * g++.dg/gcov/gcov-18.C: New test. > * gcc.misc-tests/gcov-19.c: New test. > --- > gcc/common.opt | 8 + > gcc/doc/gcov.texi | 36 ++ > gcc/doc/invoke.texi | 19 + > gcc/gcov-counter.def | 3 + > gcc/gcov-io.h | 3 + > gcc/gcov.cc | 177 +++++- > gcc/profile.cc | 51 +- > gcc/testsuite/g++.dg/gcov/gcov-18.C | 209 ++++++ > gcc/testsuite/gcc.misc-tests/gcov-19.c | 726 +++++++++++++++++++++ > gcc/testsuite/lib/gcov.exp | 187 +++++- > gcc/tree-profile.cc | 838 +++++++++++++++++++++++++ > 11 files changed, 2248 insertions(+), 9 deletions(-) > create mode 100644 gcc/testsuite/g++.dg/gcov/gcov-18.C > create mode 100644 gcc/testsuite/gcc.misc-tests/gcov-19.c