<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
@font-face
{font-family:Consolas;
panose-1:2 11 6 9 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
p.MsoListParagraph, li.MsoListParagraph, div.MsoListParagraph
{mso-style-priority:34;
margin-top:0in;
margin-right:0in;
margin-bottom:0in;
margin-left:.5in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
/* List Definitions */
@list l0
{mso-list-id:1160462608;
mso-list-type:hybrid;
mso-list-template-ids:-525017038 -1408594648 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l0:level1
{mso-level-text:"%1\.\)";
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l0:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l0:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l1
{mso-list-id:1701125319;
mso-list-type:hybrid;
mso-list-template-ids:98705246 415529554 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l1:level1
{mso-level-text:"%1\.\)";
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l1:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l1:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l1:level9
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
ol
{margin-bottom:0in;}
ul
{margin-bottom:0in;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal">Last January, I upstreamed support for Source-based Branch Coverage (Revision
<a href="https://reviews.llvm.org/D84467">https://reviews.llvm.org/D84467</a>). I also spoke about this work at the 2020 LLVM Developers’ Meeting. It was a lot of fun to work on!<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">As I mentioned then, I have had an interest in extending this support to enable Modified Condition/Decision Coverage (MC/DC), and I’d like to start working on that very soon. Based on what I learned from others, there is a lot of interest
in supporting MC/DC with LLVM. MC/DC is a requirement for functional safety critical development, in particular, in the embedded space. More about MC/DC:
<a href="https://en.wikipedia.org/wiki/Modified_condition/decision_coverage">https://en.wikipedia.org/wiki/Modified_condition/decision_coverage</a><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><b>Background<o:p></o:p></b></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">The key thing added by MC/DC (from the DO-178C standard) is to show that, “<b>Each condition in a decision is shown to independently affect the outcome of a decision.</b>” A condition is shown to affect a decision’s outcome independently
“<i>by varying just that condition while holding fixed all other possible conditions”</i>. An addendum to the DO-178C standard definition clarifies, “or varying just that condition while holding fixed all other possible conditions
<i>that could affect the outcome</i>”, which allows us to ignore unevaluatable conditions in languages that have short-circuit behavior on logical operations && and || (like C/C++). This is what I plan to implement.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">For a Boolean logical expression consisting of one or more logical operators, the individual condition True/False path of execution constitutes a ‘test vector’ yielding a decision outcome. For example, for “a && b”, there are three possible
test vectors (‘-‘ signifies an unevaluatable ‘don’t-care’ condition due to short-circuit semantics).<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:Consolas"> a b Result<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:Consolas">1: F, -, F {F,-,F}<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:Consolas">2: T, F, F {T,F,F}<o:p></o:p></span></p>
<p class="MsoNormal" style="margin-left:.5in"><span style="font-family:Consolas">3: T, T, T {T,T,T}<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">MC/DC effectively requires N+1 test vectors to verify (where N is the number of conditions). In the example above, all of the test vectors must be executed in order to show that both conditions, a and b, independently affect the outcome.
More precisely, two test vectors are required for each condition to show MC/DC, forming an “independence pair” for each condition (in the above example, ‘a’ can be shown via test vectors 1 and 3, and ‘b’ can be shown via test vectors 2 and 3). The goal for
LLVM is to enable llvm-cov to determine the executed test vectors and analyze them for each condition/decision outcome to prove that each condition independently affects the outcome. The overall metric is simply the number of executed “independence pairs”
vs. total expected for each condition.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">I’m just sketching out the design. Similar to Branch Coverage, there are three primary areas that I am proposing to extend:<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<ol style="margin-top:0in" start="1" type="1">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l1 level1 lfo1"><b>Extend the notion of “BranchRegion”<o:p></o:p></b>
<ol style="margin-top:0in" start="1" type="a">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l1 level2 lfo1">When I implemented support for branch coverage, I defined a new BranchRegion region type to encompass a single condition and its True and False counters. What I’d like to do here
is add an ID for the region as well as IDs that correspond to branch regions for each True/False counter (if it exists). What this does is link branch regions together according to an execution path, and this enables llvm-cov to construct the True/False test
vectors and the associated execution counts for each path to ascertain whether that test vector was executed. For example:<o:p></o:p></li></ol>
</li></ol>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l1 level3 lfo1">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>i.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>Given a Boolean expression like “(a && b && c)”, independent branch regions are already created for conditions ‘a’, ‘b’, ‘c’. The extension would allow llvm-cov to determine
that a <b>true</b> path for ‘a’ leads to condition ‘b’, a <b>false</b> path leads to a False decision (short-cutting ‘b’ and ‘c’), etc…<o:p></o:p></p>
<ol style="margin-top:0in" start="1" type="1">
<ol style="margin-top:0in" start="1" type="a">
<ol style="margin-top:0in" start="1" type="i">
<ol style="margin-top:0in" start="1" type="1">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l1 level4 lfo1">{F, -, -}, {T, T, F}, etc.
<o:p></o:p></li></ol>
</ol>
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l1 level2 lfo1">I’d like to extend this in a backward-compatible way, so that if a BranchRegion isn’t encoded with the IDs, Branch Coverage can still be visualized.<o:p></o:p></li></ol>
</ol>
<p class="MsoListParagraph"><o:p> </o:p></p>
<ol style="margin-top:0in" start="2" type="1">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l1 level1 lfo1"><b>Counter Instrumentation<o:p></o:p></b>
<ol style="margin-top:0in" start="1" type="a">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l1 level2 lfo1">For basic cases like ‘a && b && c’ and “a && (b || c)”, no new counter instrumentation is needed. The existing ‘True/False’ counts (based on counters or counter expressions) yield
test vectors that llvm-cov can check. What’s most important are the True/False leaf-node counters in the decision because these indicate whether a full test vector was executed or not. In these basic cases, each condition node has a single parent.<o:p></o:p></li></ol>
</li></ol>
<p class="MsoListParagraph" style="margin-left:1.0in"><o:p> </o:p></p>
<ol style="margin-top:0in" start="2" type="1">
<ol style="margin-top:0in" start="2" type="a">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l1 level2 lfo1">Where things get sticky is with Boolean expressions such as “(a && b) || c” or “(a && b) || (c && d)”. In these cases, the short-circuiting behavior of “a && b” means that two execution
paths lead to condition ‘c’, thereby forming a join point in the control flow. In these cases, we’ll have to introduce a counter for conditions on the right-hand-side of the ‘||’ in order to disambiguate the execution paths that lead to ‘c’.
<o:p></o:p></li></ol>
</ol>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l1 level3 lfo1">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>i.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]><b>Note</b>: Unfortunately, the number of new counters here can grow exponentially for really complicated Boolean expressions, “(a && b && c) || (c && d && f)”, so this is definitely
a downside with this particular design. However, these complicated expressions are not common in MC/DC code. The changes I propose are enough to easily target the common cases, but we may be able to mitigate against really complicated cases through different
means (e.g. by limiting the forms of conditions/expressions instrumented and issuing a warning). There is also an effort to reduce the size of counters (we already facilitate this in our downstream compiler). MC/DC will also be disabled by default in clang.
<b>I’m open to other suggestions here.</b><o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<ol style="margin-top:0in" start="3" type="1">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l1 level1 lfo1"><b>Visualization using llvm-cov<o:p></o:p></b>
<ol style="margin-top:0in" start="1" type="a">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l1 level2 lfo1">Given regions (1. above) that identify the execution paths in a Boolean expression and counters that identify what paths were actually executed, llvm-cov will assemble a test vector
table and check for “independence pairs” for each condition to prove whether the executed test vectors sufficiently show that “<b>Each condition in a decision is shown to independently affect the outcome of a decision”.
</b> <o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l1 level2 lfo1">It would visualize as something like this in text-mode:<o:p></o:p></li></ol>
</li></ol>
<p class="MsoListParagraph" style="margin-left:1.0in"><o:p> </o:p></p>
<p class="MsoNormal" style="margin-left:1.0in"><b><span style="font-size:9.0pt;font-family:Consolas"> 32| 20| if (arg1 == 0 || arg2 == 2 || arg2 == 34)<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:1.0in"><b><span style="font-size:9.0pt;font-family:Consolas"> ------------------<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:1.0in"><b><span style="font-size:9.0pt;font-family:Consolas"> | C1 Branch (32:13): [True: 10, False: 10]<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:1.0in"><b><span style="font-size:9.0pt;font-family:Consolas"> | C2 Branch (32:26): [True: 5, False: 5]<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:1.0in"><b><span style="font-size:9.0pt;font-family:Consolas"> | C3 Branch (32:39): [True: 0, False: 5]<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:1.0in"><b><span style="font-size:9.0pt;font-family:Consolas"> ------------------<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:1.0in"><b><span style="font-size:9.0pt;font-family:Consolas"> ------------------<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:1.0in"><b><span style="font-size:9.0pt;font-family:Consolas"> | Executed Test Vectors:<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:1.0in"><b><span style="font-size:9.0pt;font-family:Consolas"> |<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:1.0in"><b><span style="font-size:9.0pt;font-family:Consolas"> | C1, C2, C3 Res<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:1.0in"><b><span style="font-size:9.0pt;font-family:Consolas"> | { T, -, -, = T }<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:1.0in"><b><span style="font-size:9.0pt;font-family:Consolas"> | { F, T, -, = T }<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:1.0in"><b><span style="font-size:9.0pt;font-family:Consolas"> | { F, F, F, = F }<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:1.0in"><b><span style="font-size:9.0pt;font-family:Consolas"> |<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:1.0in"><b><span style="font-size:9.0pt;font-family:Consolas"> | C1-Pair: covered<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:1.0in"><b><span style="font-size:9.0pt;font-family:Consolas"> | C2-Pair: covered<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:1.0in"><b><span style="font-size:9.0pt;font-family:Consolas"> | C3-Pair: not covered<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:1.0in"><b><span style="font-size:9.0pt;font-family:Consolas"> | MC/DC Coverage for Expression: 67%<o:p></o:p></span></b></p>
<p class="MsoNormal" style="margin-left:1.0in"><b><span style="font-size:9.0pt;font-family:Consolas"> ------------------<o:p></o:p></span></b></p>
<p class="MsoListParagraph" style="margin-left:1.0in"><o:p> </o:p></p>
<ol style="margin-top:0in" start="3" type="1">
<ol style="margin-top:0in" start="3" type="a">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l1 level2 lfo1">Some vendors show all possible test vectors and identify the executed ones.<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l1 level2 lfo1">HTML output can look similar, although I’d still like to improve HTML output for both branch coverage and MC/DC using tooltips.<o:p></o:p></li></ol>
</ol>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><b>Alternatives<o:p></o:p></b></p>
<p class="MsoNormal">In looking at what other vendors do, I also looked into some alternative designs that are definitely worth mentioning.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<ol style="margin-top:0in" start="1" type="1">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l0 level1 lfo2">Log-based trace output<o:p></o:p>
<ol style="margin-top:0in" start="1" type="a">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l0 level2 lfo2">Some vendors track the control-flow through the conditions in a Boolean expression and simply emit log-data during execution. While this makes the instrumentation very straightforward,
particularly for more complicated Boolean expressions, supporting this in LLVM would require llvm-profdata/llvm-cov to understand additional sets of data in addition to counter data and region data. I’d rather build on what’s already supported.<o:p></o:p></li></ol>
</li></ol>
<p class="MsoListParagraph"><o:p> </o:p></p>
<ol style="margin-top:0in" start="2" type="1">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l0 level1 lfo2">Counter-based trace output<o:p></o:p>
<ol style="margin-top:0in" start="1" type="a">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l0 level2 lfo2">Another option would be to track the control-flow through the conditions and simply map test-vector execution directly to its own counter. However, this would require many more additional
counters than are required by the design proposed above because each possible test-vector would have a counter.<o:p></o:p></li></ol>
</li></ol>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l0 level3 lfo2">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>i.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>We could mitigate this by introducing variable sized counters (since we only need to know whether a test-vector was executed, which only requires one bit), or by mapping test
vectors to a bitmap in a single counter, but this undermines the way counters are designed to work in LLVM and would require more extensive work to support in a first-class way (and not a hack). However, if this could be done easily, I’m open to suggestions.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">In the end, the design I propose above extends what’s already there and targets the common use cases most likely to be encountered for MC/DC.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Please let me know if my design proposal looks reasonable. I’d like to start implementation and upstream early next year.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Thanks!<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Alan Phipps<o:p></o:p></p>
<p class="MsoNormal">Texas Instruments, Inc.<o:p></o:p></p>
</div>
</body>
</html>