Paper: Backwards Data-Flow Analysis using Prophecy Variable in the BuildIt System

This paper takes an unusual approach to program optimization, adding
"prophecy variables" to programs that predict program behavior, then
adjusting the prophecies and rerunning the programs until they get it
right. They claim it's a lot faster and easier than traditional program
analysis.


Abstract
Many program transformations and optimizations require information about
the future behavior of the program. A standard way to obtain this
information is to build an intermediate program representation, then use a
backwards program analysis to propagate relevant information against the
flow of control back to the transformation/optimization site. We instead
propose to use prophecy variables, which predict information about the
future execution of the program, to enable such transformations and
optimizations. We implement prophecy variables in BuildIt, a lightweight
domain specific language implementation system. BuildIt uses staged
compilation to implement high performance domain specific languages
embedded within a standard general purpose programming language (C++). The
BuildIt first phase uses standard C++ program execution to generate
optimized C, C++, and CUDA second phase code. This approach enables
BuildIt to eliminate programming language implementation components such
as parsers and intermediate representations, delivering a dramatic
decrease in the engineering effort required to implement domain specific
languages. The combination of prophecy variables and repeated forward
program execution enables BuildIt to extend this approach to include
transformations and optimizations that require information about the
future execution of the program without backwards analyses and without the
engineering overhead associated with implementing these analyses. We
formalize the use of prophecy variables for this purpose, discuss the
implementation of prophecy variables and repeated execution in BuildIt,
and present experimental results for BuildIt computations that benefit
from optimizations enabled by the information that prophecy variables
provide.


https://arxiv.org/abs/2601.02653


Regards,
John Levine, johnl@taugh.com, Taughannock Networks, Trumansburg NY
Please consider the environment before reading this e-mail. https://jl.ly

Return to the comp.compilers page.
Search the comp.compilers archives again.