Computer systems of any size are unlikely to be simple programs. Extracted from some sort of source code control, they will be configured and targeted for deployment using preprocessors, configuration, and make tools. These aspects are often neglected--for example, does your favorite refactoring tool ensure that tests and makefiles are refactored in step with the code?

One approach to taming this complexity is to use software product lines (SPLs), which the authors of this paper describe by means of sets of features (or configurations) that (de)activate certain program artifacts. They ask the following question: Given an SPL description, how does one analyze that description, for example, in a dataflow analysis? The naive approach is to analyze all the instances of the SPL, but in this paper, the authors show that a more thoughtful approach pays performance dividends, at least in the case of a number of intraprocedural analyses.

The first step of the new approach is to build an analysis that is feature sensitive so that each analysis can be performed for the features enabled by the configuration of the particular instance of the SPL, rather than making the analysis on the compiled version of the configuration. The second innovation is to perform an analysis of all the configurations simultaneously, by means of a product lattice. This has the distinct advantage of performing the fixed-point calculation once and for all, rather than repeating it for each configuration. The final innovation is to share computations in the simultaneous calculation of the analysis.

The paper gives a theoretical analysis of the speedups and presents data gathered in a number of real-world case studies. The simultaneous analysis performs particularly well in the case where the SPL is feature rich, producing a substantial speedup. Sharing computations can reduce the memory footprint of the analysis as well.

It will be interesting to see how the results of this well-written paper scale to larger systems and to interprocedural analyses in particular.