Selectors Make Set-Based Analysis Too Hard

摘要

A set-based program analysis establishes constraints between sets of abstract values for all expressions in a program. Solving the system of constraints produces a conservative approximation to the program's runtime flow of values. Some practical set-based analyses use explicit selectors to extract the relevant values from an approximation set. For example, if the analysis needs to determine the possible return values of a procedure, it uses the appropriate selector to extract the relevant component from the abstract representation of the procedure. In this paper, we show that this selector-based approach complicates the constraint solving phase of the analysis too much and thus fails to scale up to realistic programming languages. We demonstrate this claim with a full-fledged value flow analysis for case-lambda, a multi-branched version of lambda. We show how both the theoretical underpinnings and the practical implementation become too complex. In response, we present a variant of set-based closure analysis that computes equivalent results in a much more efficient manner.