Title: Bridging Static and Dynamic Program Analysis using Fuzzy Logic,
Abstract: Static program analysis is used to summarize properties over all dynamic
executions. In a unifying approach based on 3-valued logic properties are
either assigned a definite value or unknown. But in summarizing a set of
executions, a property is more accurately represented as being biased towards
true, or towards false. Compilers use program analysis to determine benefit of
an optimization. Since benefit (e.g., performance) is justified based on the
common case understanding bias is essential in guiding the compiler.
Furthermore, successful optimization also relies on understanding the quality
of the information, i.e. the plausibility of the bias. If the quality of the
static information is too low to form a decision we would like a mechanism that
improves dynamically.
We consider the problem of building such a reasoning framework and present
the fuzzy data-flow analysis. Our approach generalize previous work that use
3-valued logic. We derive fuzzy extensions of data-flow analyses used by the
lazy code motion optimization and unveil opportunities previous work would not
detect due to limited expressiveness. Furthermore we show how the results of
our analysis can be used in an adaptive classifier that improve as the
application executes.