Precise Interprocedural Analysis using Random Interpretation
Abstract
We describe a unified framework for random interpretation that
generalizes previous randomized intraprocedural analyses, and also
extends naturally to efficient interprocedural analyses. There is no
such natural extension known for deterministic algorithms. We present
a general technique for extending any intraprocedural random
interpreter to perform a context-sensitive interprocedural analysis
with only polynomial increase in running time. This technique involves
computing random summaries of procedures, which are complete and
probabilistically sound.
As an instantiation of this general technique, we obtain the first
polynomial-time randomized algorithm that discovers all linear
relationships interprocedurally in a linear program. We also obtain
the first polynomial-time randomized algorithm for precise
interprocedural value numbering over a program with unary
uninterpreted functions.
We present experimental evidence that quantifies the precision and
relative speed of the analysis for discovering linear relationships
along two dimensions: intraprocedural vs. interprocedural, and
deterministic vs. randomized. We also present results that show the
variation of the error probability in the randomized analysis with
changes in algorithm parameters. These results suggest that the error
probability is much lower than the existing conservative theoretical bounds.