Flow analysis, linearity, and PTIME. David Van Horn and Harry G. Mairson. 2008.

[ PDF ]

We examine the computational complexity of flow analyses that approximate Shivers' 0CFA by trading precision for faster computation. As a motivating example, we consider Henglein's simple closure analysis, which forfeits the notion of directionality in flows and enjoys an "almost linear" time algorithm, whereas the best known algorithm for 0CFA is cubic. We show that despite near linear time computability, simple closure analysis, like 0CFA, is complete for PTIME.

Proof of this lower bound relies on the insight that linearity of programs subverts the approximation of analysis and renders it equivalent to evaluation. We establish a correspondence between Henglein's simple closure analysis and evaluation for linear terms. In doing so, we derive sufficient conditions effectively characterizing not only simple closure analysis, but many known flow analyses computable in less than cubic time, such as Ahsley and Dybvig's sub-0CFA, Heintze and McAllester's subtransitive flow analysis, and Mossin's single source/use analysis.

By using a nonstandard, symmetric implementation of Boolean logic within the linear lambda calculus, it is possible to simulate circuits at analysis-time, and as a consequence, we prove that all of the above analyses are complete for ptime. Any subpolynomial algorithm for these problems would require (unlikely) breakthrough results in complexity, such as PTIME = LOGSPACE.