<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;}
p.msonormal0, li.msonormal0, div.msonormal0
{mso-style-name:msonormal;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
span.EmailStyle19
{mso-style-type:personal;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.EmailStyle20
{mso-style-type:personal-reply;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@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:1456485605;
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;}
@list l2
{mso-list-id:1701125319;
mso-list-type:hybrid;
mso-list-template-ids:98705246 415529554 67698713 67698715 67698703 67698713 67698715 67698703 67698713 67698715;}
@list l2:level1
{mso-level-text:"%1\.\)";
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level2
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level3
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l2:level4
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level5
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level6
{mso-level-number-format:roman-lower;
mso-level-tab-stop:none;
mso-level-number-position:right;
text-indent:-9.0pt;}
@list l2:level7
{mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2:level8
{mso-level-number-format:alpha-lower;
mso-level-tab-stop:none;
mso-level-number-position:left;
text-indent:-.25in;}
@list l2: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">FYI for the llvm-dev list, I have decided to change my originally proposed design after some email exchanges with Vedant Kumar that will prevent the exponential counter explosion I identified in #2.b. of the original proposal. Instead,
I’d like to implement a log-based solution that tracks executed test vectors using an instrumented, variable-length
<i>bitmap</i>, one per Boolean expression. The log-based approach scales much better, seems like a cleaner design, and is closer to what other vendors do to implement MC/DC.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Here is an outline of the new design proposal overall:<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:l2 level1 lfo1"><b>Profile Bitmap Coverage Object<o:p></o:p></b>
<ol style="margin-top:0in" start="1" type="a">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l2 level2 lfo1">Introduce a variable-length, counter-like object that functions as a bitmap. It is allocated once for each Boolean expression. Each bit index represents a possible test vector through
the Boolean expression, so it is sized as being 2^n bits in length, where ‘n’ is the number of conditions (min size 1-byte, which will encode up to 3 conditions).<b><o:p></o:p></b></li></ol>
</li></ol>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l2 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]>These bitmap objects are allocated in terms of a simple array of bytes in a new section, similar to how counters are handled.<o:p></o:p></p>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l2 level3 lfo1">
<![if !supportLists]><span style="mso-list:Ignore"><span style="font:7.0pt "Times New Roman"">
</span>ii.<span style="font:7.0pt "Times New Roman""> </span></span><![endif]>When merging profile data (either during runtime or using profdata), the bitmap objects simply OR together rather than accumulate.<o:p></o:p></p>
<ol style="margin-top:0in" start="1" type="1">
<ol style="margin-top:0in" start="2" type="a">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l2 level2 lfo1">Initially, I plan to limit the size of these bitmasks to (up to) 64bits, which can encode Boolean expressions up to 6 conditions, but we can extend this further in later patches.
Six conditions is more than sufficient to cover most functional safety, embedded applications, but I acknowledge there is a case for more flexible support.
<b><o:p></o:p></b></li></ol>
</ol>
<p class="MsoListParagraph" style="margin-left:1.5in;text-indent:-1.5in;mso-text-indent-alt:-9.0pt;mso-list:l2 level3 lfo1">
<![if !supportLists]><b><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></b><![endif]>Note that other vendors also limit the number of covered conditions (usually adjustable using an option).<b><o:p></o:p></b></p>
<p class="MsoListParagraph" style="margin-left:1.0in"><b><o:p> </o:p></b></p>
<ol style="margin-top:0in" start="2" type="1">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l2 level1 lfo1"><b>CounterMappingRegion changes<o:p></o:p></b>
<ol style="margin-top:0in" start="1" type="a">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l2 level2 lfo1">Introduce a new region type to annotate source information for a Boolean expression together with an ID of an allocated bitmap and number of individual conditions.<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l2 level2 lfo1">Extend the “BranchRegion” to include an ID. BranchRegions already correspond to individual conditions in a Boolean expression.<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:l2 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]>The same as what I originally proposed – that is, add an ID to BranchRegion-typed regions to allow llvm-cov to reconstruct the list of possible test vectors without language-specific
knowledge. The IDs are used only in the MC/DC use case, so this should be backward compatible with older formats.<o:p></o:p></p>
<p class="MsoListParagraph"><o:p> </o:p></p>
<ol style="margin-top:0in" start="3" type="1">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l2 level1 lfo1"><b>Counter Instrumentation</b>
<b><o:p></o:p></b>
<ol style="margin-top:0in" start="1" type="a">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l2 level2 lfo1">For each boolean expression, the evaluation of each constituent condition is a Boolean value (obviously) representing True or False. I propose to Shift-OR this value into a temporary
bitmap representing a single test vector execution. Each bit in this temp bitmap corresponds to whether a condition evaluated to True (1) or False (0). Unevaluated conditions due to short-circuited operations are
<i>don’t-cares</i> and left as ‘0’. <o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l2 level2 lfo1">When the overall outcome is reached, the executed test vector is ‘logged’ by taking the numerical value of this bitmap as the index into the expression’s Profile Bitmask Object (mentioned
above in 1.a), which is set to ‘1’. Each test vector will always have a unique value made up of a unique path of True and False conditions.<o:p></o:p></li></ol>
</li></ol>
<p class="MsoNormal"><o:p> </o:p></p>
<ol style="margin-top:0in" start="4" type="1">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l2 level1 lfo1"><b>Visualization using llvm-cov</b>
<b><o:p></o:p></b>
<ol style="margin-top:0in" start="1" type="a">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l2 level2 lfo1">llvm-cov extracts the executed test vectors by looking at the True bits in the Profile Bitmask Object and matching the index of that bit against the set of possible test vectors for
that Boolean expression (extracted from the BranchRegion IDs).<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l2 level2 lfo1">It would visualize as something like this in text-mode (same as below):<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="4" type="1">
<ol style="margin-top:0in" start="3" type="a">
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l2 level2 lfo1">We could optionally show all possible test vectors here as well, since llvm-cov has that information.<o:p></o:p></li><li class="MsoListParagraph" style="margin-left:0in;mso-list:l2 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">I’d like to shoot to have something in phabricator early next year.<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" align="right" style="text-align:right"><o:p> </o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<div style="border:none;border-top:solid #E1E1E1 1.0pt;padding:3.0pt 0in 0in 0in">
<p class="MsoNormal"><b>From:</b> llvm-dev <llvm-dev-bounces@lists.llvm.org> <b>On Behalf Of
</b>Phipps, Alan via llvm-dev<br>
<b>Sent:</b> Tuesday, November 9, 2021 3:21 PM<br>
<b>To:</b> llvm-dev@lists.llvm.org; Vedant Kumar <vedant_kumar@apple.com><br>
<b>Subject:</b> [EXTERNAL] [llvm-dev] RFC: Source-based MC/DC Code Coverage<o:p></o:p></p>
</div>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<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 lfo4"><b>Extend the notion of “BranchRegion”</b>
<b><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 lfo4">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 lfo4">
<![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 lfo4">{F, -, -}, {T, T, F}, etc.
<o:p></o:p></li></ol>
</ol>
<li class="MsoListParagraph" style="margin-left:0in;mso-list:l1 level2 lfo4">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 lfo4"><b>Counter Instrumentation</b>
<b><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 lfo4">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 lfo4">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 lfo4">
<![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 lfo4"><b>Visualization using llvm-cov</b>
<b><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 lfo4">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 lfo4">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 lfo4">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 lfo4">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>