Automatic Inference of Optimizer Flow Functions from Semantic Meanings

Erika Rice Scherpelz, Sorin Lerner, and Craig Chambers

Previous work presented a language called Rhodium for writing program analyses and transformations, in the form of declarative flow functions that propagate instances of user-defined dataflow fact schemas. Each dataflow fact schema specifies a semantic meaning, which allows the Rhodium system to automatically verify the correctness of the user's flow functions. In this work, we have reversed the roles of the flow functions and semantic meanings: rather than \emph{checking} the correctness of the user-written flow functions using the facts' semantic meanings, we automatically \emph{infer} correct flow functions solely from the meanings of the dataflow fact schemas. We have implemented our algorithm for inferring flow functions from fact schemas in the context of the Whirlwind compiler, and have used this implementation to infer flow functions for a variety of fact schemas. The automatically generated flow functions cover most of the situations covered by an earlier suite of handwritten rules.

Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2007), San Diego, California, June 11-13, 2007.

Download: [PDF]