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 04BB93858D32 for ; Thu, 1 Dec 2022 15:05:26 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 04BB93858D32 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 imap1.suse-dmz.suse.de (imap1.suse-dmz.suse.de [192.168.254.73]) (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 B46441F896; Thu, 1 Dec 2022 15:05:24 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_rsa; t=1669907124; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=QyO6wJjpUyrsjevnID0rf8bKE5OAxOVewI2J8v1OdW4=; b=J6GpHFghVC34apNtHri7NKL3ylHb2xc/eBKkxZ8mRESnXGvc23OwTrokHWMbP4BIRHNyl3 tpZ0To9otjDNmvUNlllOsrH27EZib0ejProg50DDAPI3lbgb4VN0FJZcv8Vud3PtuHDV1W Hy4MZsmTOVPFgm7+VcsslnFNBxF5y88= DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; d=suse.cz; s=susede2_ed25519; t=1669907124; h=from:from:reply-to:date:date:message-id:message-id:to:to:cc:cc: mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references; bh=QyO6wJjpUyrsjevnID0rf8bKE5OAxOVewI2J8v1OdW4=; b=Ko67EaS2EA+GzAwYwGI5uS8pu6gChrdZcWD9fWFvmUtLhgwjSQOrjuxZg35kOrIDttTXsT fg0AwU20DgkIkqCA== Received: from imap1.suse-dmz.suse.de (imap1.suse-dmz.suse.de [192.168.254.73]) (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 imap1.suse-dmz.suse.de (Postfix) with ESMTPS id 9C07613503; Thu, 1 Dec 2022 15:05:24 +0000 (UTC) Received: from dovecot-director2.suse.de ([192.168.254.65]) by imap1.suse-dmz.suse.de with ESMTPSA id 4FjUJLTCiGMYRwAAGKfGzw (envelope-from ); Thu, 01 Dec 2022 15:05:24 +0000 Message-ID: <8a187659-7f64-e760-5732-6bbd6f18eb11@suse.cz> Date: Thu, 1 Dec 2022 16:05:24 +0100 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101 Thunderbird/102.5.0 Subject: Re: [PATCH v2] Add condition coverage profiling Content-Language: en-US To: =?UTF-8?Q?J=c3=b8rgen_Kvalsvik?= , gcc-patches@gcc.gnu.org Cc: =?UTF-8?Q?J=c3=b8rgen_Kvalsvik?= References: <20221111052141.29815-1-jorgen.kvalsvik@woven-planet.global> From: =?UTF-8?Q?Martin_Li=c5=a1ka?= In-Reply-To: <20221111052141.29815-1-jorgen.kvalsvik@woven-planet.global> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-6.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,NICE_REPLY_A,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 11/11/22 06:21, Jørgen Kvalsvik wrote: > From: Jørgen Kvalsvik > > 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. MC/DC it is > required for 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 analyses the the control > flow graph to instrument for coverage. This has the benefit of being > programming language independent and faithful to compiler decisions > and transformations, 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 records coverage in fixed-size > bitsets which gcov knows how to interpret. This is very fast, but > introduces a limit on the number of terms in a single boolean > expression, 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. This limitation is in the implementation and not the > algorithm, so support for more conditions can be added by also > introducing arbitrary-sized bitsets. > > For space overhead, the instrumentation needs two accumulators > (gcov_unsigned_type) per condition in the program which will be written > to the gcov file. In addition, every function gets a pair of local > accumulators, but these accmulators are reused between conditions in the > same function. > > For time overhead, there is a zeroing of the local accumulators for > every condition and one or two bitwise operation on every edge taken in > the an expression. > > 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) > condition outcomes covered 3/8 > condition 0 not covered (true false) > condition 1 not covered (true) > condition 2 not covered (true) > condition 3 not covered (true) > 1: 19: x = 1; > -: 20: else > 2: 21: x = 2; > 3: 22:} > > gcov --conditions --json-format: > > "conditions": [ > { > "not_covered_false": [ > 0 > ], > "count": 8, > "covered": 3, > "not_covered_true": [ > 0, > 1, > 2, > 3 > ] > } > ], > > Some expressions, mostly those without else-blocks, are effectively > "rewritten" in the CFG construction making the algorithm unable to > distinguish them: > > and.c: > > if (a && b && c) > x = 1; > > ifs.c: > > if (a) > if (b) > if (c) > x = 1; > > gcc will build the same graph for both these programs, and gcov will > report boths as 3-term expressions. It is vital that it is not > interpreted the other way around (which is consistent with the shape of > the graph) because otherwise the masking would be wrong for the and.c > program which is a more severe error. While surprising, users would > probably expect some minor rewriting of semantically-identical > expressions. > > and.c.gcov: > #####: 2: if (a && b && c) > condition outcomes covered 6/6 > #####: 3: x = 1; > > ifs.c.gcov: > #####: 2: if (a) > #####: 3: if (b) > #####: 4: if (c) > #####: 5: x = 1; > condition outcomes covered 6/6 > > Adding else clauses alters the program (ifs.c can have 3 elses, and.c > only 1) and coverage becomes less surprising > > ifs.c.gcov: > #####: 2: if (a) > condition outcomes covered 2/2 > #####: 4: { > #####: 4: if (b) > condition outcomes covered 2/2 > 5: { > #####: 6: if (c) > condition outcomes covered 2/2 > #####: 7: x = 1; > #####: 8: } > #####: 9: else > #####: 10: x = 2; > #####: 11: } > #####: 12: else > #####: 13: x = 3; > > Since the algorithm works on CFGs, it cannot detect some ternary > operator introduced conditionals. 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 such > comparisons, and insert an extra instruction for recording the outcome. > Hello. Thanks for the rebased version of the patch. Please, update the documentation bits as the Sphinx conversion didn't make it. Sorry for that. I approve the GCOV-part of the patch and I'm fine with the rest of the patch (though I can't approve it). What a nice work! Cheers, Martin