Minimum Coverage Instrumentation

Modern compilers leverage block coverage profile data to carry out downstream profile-guided optimizations to improve the runtime performance and the size of a binary. Given a control-flow graph $G=(V, E)$ of a function in the binary, where nodes in $V$ correspond to basic blocks (sequences of instructions that are always executed sequentially) and edges in $E$ represent jumps in the control flow, the goal is to know for each block $u \in V$ whether $u$ was executed during a session. To this end, extra instrumentation code that records when a block is executed needs to be added to the binary. This extra code creates a time and space overhead, which one would like to minimize as much as possible. Motivated by this application, we study the Minimum Coverage Instrumentation problem, where the goal is to find a minimum size subset of blocks to instrument such that the coverage of the remaining blocks in the graph can be inferred from the coverage status of the instrumented subset. Our main result is an algorithm to find an optimal instrumentation strategy and to carry out the inference in $O(|E|)$ time. We also study variants of this basic problem in which we are interested in learning the coverage of edges instead of the nodes, or when we are only allowed to instrument edges instead of the nodes.