A Data-Flow Analysis Framework for Graal IR

Data-flow analysis is a common technique employed in optimizing compilers to infer
properties of a program at compile time. Although perfect evaluation is fundamen-
tally undecidable according to Rice’s theorem, useful results can be achieved trading
precision of the analysis for computational efficiency.
This thesis presents a novel framework for performing optimistic data-flow anal-
ysis in the Sea of Nodes program representation of GraalVM. Based on previous
work on Lazy Sparse Conditional Constant Propagation, we adapted and expanded
the underlying data-flow analysis algorithm, to allow the framework to handle more
general and complex analysis domains. One major goal building this framework is,
to preserve LSCCP’s lazy iteration property, which means, we want to leave large
parts of the graph unevaluated. Specifically, we want skip evaluating parts that do
not contribute to the analysis in a meaningful way. Another major goal is for the
framework to not require a total order of nodes, because calculating such an order
for the Sea of Nodes is a costly operation. However, this combination of a lack of
global order for general data-flow nodes in the Sea of Nodes program representation
and lazy iteration, poses unique difficulties our framework needs to overcome, to
allow for fast and precise analysis.
Additionally, our framework borrows the concept of widening from abstract in-
terpretation to support highly useful domains like the domain of ranges, which are
significantly more complex than regular data-flow analysis domains. Furthermore,
our framework aims to seamlessly integrate reachability analysis into the data-flow
analysis, to allow for increased precision for very little extra effort on the side of the
user of the framework.
To allow for quick and easy implementation of new data-flow analysis domains,
our framework provides a simple and flexible Java interface, which allows reusing
preexisting data-flow analysis code in new domains. Over the course of this thesis,
three distinct analysis domains were implemented to show the versatility and capa-
bilities of our framework. Finally, this thesis presents evaluations of two of those
three domains.