Compositional Dataflow Via Abstract Transition Systems

Abstract

Despite decades of research and development of dataflow analyses within dozens of different compiler infrastructures, analysis of real programs is intractable in practice. The reason is that although a single research group is equipped to model a single well-defined aspect of application behavior, application developers use a very wide range of abstractions and coding techniques within a single application. Since to analyze even a single application all of its complexities must be modeled, researchers must combine analyses from multiple groups into comprehensive analysis frameworks such as OpenAnalysis or LLVM. Analysis composition is expensive in practice, requiring development effort that is quadratic in the number of analyses as well as tight inter-group coordination to maintain consistent APIs to each other’s symbolic abstractions. This paper proposes an approach to building compiler analysis frameworks that simplifies the composition of independently-developed analyses. It formalizes the operation of dataflow analyses in a way that simplifies reasoning about various types of analysis composition. Further, it defines a portable abstraction that can represent the results of many real analyses, making it possible for different analyses to leverage each other’s results with no knowledge of their APIs or internal abstractions and without any coordination between the groups that developed them. We have developed the Fuse compositional analysis framework based on this abstraction, and integrated it in the ROSE [15] compilation system. Our experience is that this approach greatly simplifies composition of program analyses, making it easy to tailor different combinations of program analyses to different input programs.