From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-pl1-x62c.google.com (mail-pl1-x62c.google.com [IPv6:2607:f8b0:4864:20::62c]) by sourceware.org (Postfix) with ESMTPS id 86B0E3858434 for ; Fri, 2 Dec 2022 01:03:25 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 86B0E3858434 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-pl1-x62c.google.com with SMTP id jn7so3247003plb.13 for ; Thu, 01 Dec 2022 17:03:25 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=woven-planet.global; s=google; h=content-transfer-encoding:in-reply-to:from:references:cc:to :content-language:subject:user-agent:mime-version:date:message-id :from:to:cc:subject:date:message-id:reply-to; bh=qHsEaVfETKe2hmUXwWoAiS+OJbdZphYYW/BFJb9B8kA=; b=J4OqmAnLyTrjA/SLSE6AiDC6EyZHahOCzq7sQ12LrOJZAnUZkmFrqBZcK+gd/thlgE RmOYu6h1Pr1gjNkDYtQWBcPJRDakmjwHx4lG9D7vKpWk4npyL5tX3q1MH4yrm6uIvIGz gJ1FSdqErog2cWD88phzm5rVNKRPraTLTagOc= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=content-transfer-encoding:in-reply-to:from:references:cc:to :content-language:subject:user-agent:mime-version:date:message-id :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=qHsEaVfETKe2hmUXwWoAiS+OJbdZphYYW/BFJb9B8kA=; b=Ixn9Ws/B/WlpQpoXmlGtlVZw6dZu7pVhVZh7arvRM0miEOwF9PVwxmLlNoraCbEvOW arhf0kRa4XoCKPI41Q54cdprd/HQHEpmgbQ9LVniCIZ5Xgx5MatlPK6GjBu7soao3tlb dIH691G4UBbbD4WVXzZK1+UOiV0ahU5gbxt5TURSdpUsdt2G4hf1Cb0u5RnDgUeQLjYJ GohLE2DhuYmGJ8/8I2AVsTHYvMESpvtWmf+1YbkowequFIySbl13ZJLcjWEitMUO2lZW jctugb8jhnWnSBHNf2wIi6W3EhyS98+jPC18ZC0YfNXs+BuWwFsecWUr7HZ5Kizkv9ki 7gRw== X-Gm-Message-State: ANoB5pnnz64zz35clTuvc+QkJHUjPJNFuAfO3lHH/sZ2gAxKUBumnU+l jLF4BVrL2YjOQf+MZWqYXP+bhw== X-Google-Smtp-Source: AA0mqf57WsWMTX3uR2i4CFEWEOQIUno1JYFSPvYppZve5WS5/250L0wIuigmhIfApO9EQcnOsQS1Fg== X-Received: by 2002:a17:903:40c5:b0:189:6f76:9b59 with SMTP id t5-20020a17090340c500b001896f769b59mr31707984pld.68.1669943004415; Thu, 01 Dec 2022 17:03:24 -0800 (PST) Received: from [172.18.22.210] ([103.175.111.222]) by smtp.gmail.com with ESMTPSA id e9-20020aa79809000000b0057507bbd704sm3852052pfl.5.2022.12.01.17.03.22 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 01 Dec 2022 17:03:23 -0800 (PST) Message-ID: Date: Fri, 2 Dec 2022 10:03:21 +0900 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; 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?Martin_Li=c5=a1ka?= , gcc-patches@gcc.gnu.org Cc: =?UTF-8?Q?J=c3=b8rgen_Kvalsvik?= References: <20221111052141.29815-1-jorgen.kvalsvik@woven-planet.global> <8a187659-7f64-e760-5732-6bbd6f18eb11@suse.cz> From: =?UTF-8?Q?J=c3=b8rgen_Kvalsvik?= In-Reply-To: <8a187659-7f64-e760-5732-6bbd6f18eb11@suse.cz> Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Spam-Status: No, score=-5.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,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 02/12/2022 00:05, Martin Liška wrote: > 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 > Hello, Thanks! I'll revert the documentation back to texinfo, I'm sorry sphinx fell through. Who can approve the remaining bits (the tree-profile presumably)? I'll submit v3 shortly. Thanks, Jørgen