Progress report - prime path coverage in gcc 3
The prime path coverage support is shaping up nicely, so I wanted to write a bit about the last series of improvements to the upcoming prime path coverage feature in gcc.
gcov reports
Path coverage differs from statement, branch, and condition coverage in that coverage ties to the function and not individual lines. This is quite different from how gcov has reported up until now. Furthermore, it is not necessarily easy to look at some code and figure out even what the paths even are, in particular after compiler transformations.
I have written three different reporting formats: summary, dense, and detailed.
Summary
The summary is always included, and is quite simply:
-: 0:Source:tmp.cpp
-: 0:Graph:tmp.gcno
-: 0:Data:-
-: 0:Runs:0
-: 1:#include <stdio.h>
-: 2:
paths covered 0 of 15
#####: 3:int main ()
-: 4:{This is nice when glancing at a file to get an overview of the state
of the coverage. The --function-summaries flag has also been taught
how to include path information:
Function 'usage'
Lines executed:0.00% of 5
Branches executed:0.00% of 4
Taken at least once:0.00% of 4
Calls executed:0.00% of 3
Prime paths covered:0.00% of 4
Function 'setoutput'
Lines executed:0.00% of 8
Branches executed:0.00% of 6
Taken at least once:0.00% of 6
Calls executed:0.00% of 3
Prime paths covered:0.00% of 4
Function 'main'
Lines executed:0.00% of 358
Branches executed:0.00% of 192
Taken at least once:0.00% of 192
Calls executed:0.00% of 76
No path informationNote the No path information in main. This happens when a function
has too many paths and gcc gives up instrumenting it, a mechanism to
cope with path explosion to keep compile times low. The main in
question has about a million paths which is more-or-less infeasible to
cover anyway.
Dense
Moving on to the dense format. This format is line-oriented to work well with grep, while at the same time having enough information to figure out what’s going on.
$ gcov -te --prime-paths-lines tmp
-: 0:Source:tmp.cpp
-: 0:Graph:tmp.gcno
-: 0:Data:-
-: 0:Runs:0
-: 1:#include <stdio.h>
-: 2:
paths covered 0 of 15
path 0 not covered: lines 8 8(true) 9
path 1 not covered: lines 8 8(false) 11(true) 11 13(true) 13(true) 14 17
path 2 not covered: lines 8 8(false) 11(true) 11 13(true) 13(false) 16 17
path 3 not covered: lines 8 8(false) 11(true) 11 13(false) 16 17
path 4 not covered: lines 8 8(false) 11(false) 11 13(true) 13(true) 14 17
path 5 not covered: lines 8 8(false) 11(false) 11 13(true) 13(false) 16 17
path 6 not covered: lines 8 8(false) 11(false) 11 13(false) 16 17
path 7 not covered: lines 9 8(true) 9
path 8 not covered: lines 9 8(false) 11(true) 11 13(true) 13(true) 14 17
path 9 not covered: lines 9 8(false) 11(true) 11 13(true) 13(false) 16 17
path 10 not covered: lines 9 8(false) 11(true) 11 13(false) 16 17
path 11 not covered: lines 9 8(false) 11(false) 11 13(true) 13(true) 14 17
path 12 not covered: lines 9 8(false) 11(false) 11 13(true) 13(false) 16 17
path 13 not covered: lines 9 8(false) 11(false) 11 13(false) 16 17
path 14 not covered: lines 8(true) 9 8
#####: 3:int main ()
-: 4:{
-: 5: int i, total;
#####: 6: total = 0;
-: 7:
#####: 8: for (i = 0; i < 10; i++)
#####: 9: total += i;
-: 10:
#####: 11: int v = total > 100 ? 1 : 2;
-: 12:
#####: 13: if (total != 45 && v == 1)
#####: 14: printf ("Failure\n");
-: 15: else
#####: 16: printf ("Success\n");
#####: 17: return 0;
-: 18:}In this mode gcov will list every uncovered path and the lines in the order you need to execute them to cover the path. If there is a decision on that line, gcov will tell you what outcome it expects for the decision. The decision could be inferred from the next line in the sequence, but I found that hard to follow and unecessary friction. If a transition happens to be a throw rather than a decision, gcov will print that, too. Note that gcov only prints the last line in each basic block, which is why there are no paths thart start with line 4 or 5.
I find this mode very useful when playing with different inputs and
following how paths are eliminated. The fact that it plays well with
grep means it is easy to quickly determine if an input covered a
specific path, without having to manually inspect. Something along the
lines of gcov --stdout --prime-paths-lines --include main | grep "path 11". Because it is denser it is easier to map several paths to
the source code.
Detailed
Finally, there’s my favourite mode, the detailed
--prime-paths-source, which gives me x-ray goggles for paths. This
mode is similar to --prime-paths-lines in the sense that it will
show you the lines and decisions you need to run to cover a path,
but it will show it alongside the source itself. Here is an example
for paths 2, 3, and 4 from the dense example:
path 2:
BB 2: 3:int main ()
BB 2: 6: total = 0;
BB 2: 8: for (i = 0; i < 10; i++)
BB 4: (false) 8: for (i = 0; i < 10; i++)
BB 5: (true) 11: int v = total > 100 ? 1 : 2;
BB 6: 11: int v = total > 100 ? 1 : 2;
BB 8: (true) 13: if (total != 45 && v == 1)
BB 9: (false) 13: if (total != 45 && v == 1)
BB 11: 16: printf ("Success\n");
BB 12: 17: return 0;
path 3:
BB 2: 3:int main ()
BB 2: 6: total = 0;
BB 2: 8: for (i = 0; i < 10; i++)
BB 4: (false) 8: for (i = 0; i < 10; i++)
BB 5: (true) 11: int v = total > 100 ? 1 : 2;
BB 6: 11: int v = total > 100 ? 1 : 2;
BB 8: (false) 13: if (total != 45 && v == 1)
BB 11: 16: printf ("Success\n");
BB 12: 17: return 0;
path 4:
BB 2: 3:int main ()
BB 2: 6: total = 0;
BB 2: 8: for (i = 0; i < 10; i++)
BB 4: (false) 8: for (i = 0; i < 10; i++)
BB 5: (false) 11: int v = total > 100 ? 1 : 2;
BB 7: 11: int v = total > 100 ? 1 : 2;
BB 8: (true) 13: if (total != 45 && v == 1)
BB 9: (true) 13: if (total != 45 && v == 1)
BB 10: 14: printf ("Failure\n");
BB 12: 17: return 0;Here we see the basic blocks (BB), decisions, line number, and source code in the order it needs to be run in order to cover. I have played a bit with it and I find it an excellent tool for understanding exactly what the paths are, and find interesting interactions, and I am always surprised at what I learn when I use it. For example, I tested it on a binary search with some obvious inputs: a few hits, misses, lower-than-lowest, higher-than-highest. The test suite seemed ok, but I never actually tried the item in the exact middle, the one with no jumps. With this, I noticed right away.
This output is also great for identifying and understanding code which is made unreachable by earlier decisions. This can be approached both ways, even - if you expect code to be unreachable, run a lot of inputs and verify that it is never actually taken. If it disappears from the coverage report (which means it is now covered), it would be reachable under certain conditions. Likewise, if you run lots of different inputs, but never seem to cover that one path it could be worth investing if it is accidentally path sensitive.
Both the dense and detailed reports are aware of inlining, which is particularly relevant for C++, and would otherwise make the annotated source difficult to follow. This is what it looks like – notice how the basic blocks weave through the inlined function:
BB 2: (true) 4:int notmain(const char *entity)
== inlined from hello.h ==
BB 2: (true) 6: if (s)
BB 3: 7: printf ("hello, %s!\n", s);
BB 5: 10: return 0;
-------------------------
BB 7: 6: return hello (entity);
BB 8: 6: return hello (entity);The inlined code is rendered directly in the caller, which would otherwise print line numbers and decisions which does not actually map to the source line, something like this:
BB 2: (true) 4:int notmain(const char *entity)
BB 3: 4:int notmain(const char *entity)
BB 5: 4:int notmain(const char *entity)
BB 7: 6: return hello (entity);
BB 8: 6: return hello (entity);I find the former easier to follow, personally.
Limits and Robustness
I did a rebuild-the-world experiment this time, too, like I did for MC/DC, all the way through tree, cpio, git, and openjdk with dependencies. This did uncover a few cases which crashed, mostly with setjmp/longjmp. These have been fixed.
Sometimes, functions are so complex with so many paths that the only
thing we can do is give up. The problem is that there is no obvious
relationship between graph size (number of nodes and edges) and the
number of paths, and even small graphs may explode in size. For
example, the number of paths in a series of $n$ non-nested ifs is
$2^n$.
My solution has been to introduce a limit with -fpath-coverage-limit
which currently defaults to 250000. We keep track of an approximate
running count of number of paths seen so far, and apply a few
heuristics. When the number of paths exceeds the limit, the function
is aborted and gcc warns that it gives up coverage. If you are willing
to work with the compile time, gcc will let you increase this limit,
at the cost of compile time (and memory). This is a blunt instrument
as gcc will overestimate the number of paths, but it is meant as a
failsafe for exploding compile times, and not as fine-grained control
on which functions to instrument or not.
I would say that if you are aiming for path coverage it is likely than anything about a few thousand paths is a no-go anyway, and I hope this will not be a problem in practice. In fact, I would say that aiming for path coverage forces you to write in a very specific style, which should be part of the motivation for shooting for path coverage anyway.
Closing
There has been a some minor performance improvements, bugfixes, and json output. This work will be the topic of my NDC Techtown talk this year, which I am very much looking forward to. The patch has been posted on the gcc mailing list for review, and I hope to get it merged with time to spare for gcc 15.