[llvm-dev] Adding support for LLVM Branch Condition Coverage

[Phipps, Alan via llvm-dev]

Vedant Kumar asked me to post my design thoughts concerning branch coverage at llvm-dev since there is general interest.

My team at Texas Instruments is developing an embedded ARM C/C++ compiler with LLVM.  I would like to enhance LLVM's code coverage capability with branch condition coverage (for C/C++), similar to GCC/GCOV support for branch coverage.  This is useful for TI, and I think this will be a useful feature enhancement to LLVM that I can upstream.

In a nutshell, the functionality boils down to tracking how many times a generated "branch" instruction (based on a source code condition) is taken or not taken (i.e. evaluated into "True" and "False").  This applies to decision points in control flow (if, for, while, ...) as well as individual conditions on logical operators ("&&", "||") in Boolean expressions.

In sketching out a design, there are three primary areas in the design that I am proposing:


1.)    Add a new CounterMappingRegion kind for branch conditions

a.      This new region kind would track two counters, one for the "True" branch taken count of a branch condition, and one for the "False" branch taken count.

                                                    i.     Alternatively, I could use two separate CounterMappingRegions to track individual counters since this is how the class was originally written to be used.  However, using a single region kind to represent a single branch condition that ties all of the pertinent counter information together seems like a cleaner design.

                                                   ii.     Just as for all counters, the two branch condition counters can represent a reference to an instrumentation counter or to a counter expression.  The two counters are encoded along with the MappingRegions and distinguished based on the region kind.

                                                  iii.     All other CounterMappingRegion kinds simply ignore the second counter; nothing changes in how they're encoded, which preserves format backward compatibility.

b.      I think this change also requires an adjustment to the class SourceMappingRegion to support branch conditions that can be generated into CounterMappingRegion instances.



2.)    Counter Instrumentation

a.      We can reuse most of the existing profile instrumentation counters that are emitted as part of profiling/coverage to calculate branch condition counts (True/False).

                                                    i.     This assumption leverages the fact that logical operators in C are "short-circuit" operators.  For example, the "False-taken" count for the left-hand-side condition in a logical-or expression (e.g. condition "C1" in "C1 || C2") can be derived from the execution count we already track for the right-hand-side (condition "C2" in "C1 || C2").

b.      There does exist a case when evaluating the right-hand-side condition of a logical operator that isn't part of a control-flow statement (e.g. condition "C2" in "x = C1 || C2;") that will require instrumenting a new counter in order to properly derive that condition's "true" count and "false" count.

c.      I'll avoid going too deep into detail here, but my goal is to ensure we reuse existing profile counters as much as possible.



3.)    Visualization using llvm-cov

a.      The notion of CoverageSegment needs to be extended to comprehend the branch condition data represented by a CounterMappingRegion above.  But then llvm-cov can treat the segment distinctly when displaying True/False counts for each branch condition as well as tracking total missed branches.

b.      We can also add a BranchCoverageInfo class to track branch coverage data, similar to LineCoverageInfo and RegionCoverageInfo.

c.      The text output could look something like GCOV but with more detail that we know (I prototyped this using logical-or):


    9|       |int main(int argc, char *argv[])
   10|      3|{
   11|      3|    if (argc == 1)
Branch (11:9): [True: 1, False: 2]
   12|      1|    {
   13|      1|        return 0;
   14|      1|    }
. . .

  23|      2|    if (a == 0 || b == 2 || b == 34 || a == b)
Branch (23:9):  [True: 1, False: 1]
Branch (23:19): [True: 1, False: 0]
Branch (23:29): [True: 0, False: 0]
Branch (23:40): [True: 0, False: 0]
. . .

  31|      2|    b = a || c;
Branch (31:9):  [True: 1, False: 1]
Branch (31:14): [True: 1, False: 0]


d.      I thought about extending the "region-count" carat markers in the text display, but it could get messy.  For the HTML output, we can get a bit more fancy.

e.      Branch miss percentages/totals will be added to the coverage report.



Additional Notes

-        I'm aware that constant condition folding in CodeGenFunction::EmitBranchOnBoolExpr() needs to be taken into account.  Is there anything else related to branch optimization that I ought to be aware of?





Please let me know if these design thoughts look reasonable and if this would be useful.  The goal is to start full implementation soon and upstream in a few months.



Thanks!

Alan Phipps

Texas Instruments, Inc.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200124/fe43b752/attachment.html>