Efficient Demand Evaluation of Fixed-Point Attributes Using Static Analysis
Declarative approaches to program analysis promise a number of practical advantages over imperative approaches, from eliminating manual worklist management to increasing modularity. Reference Attribute Grammars (RAGs) are one such approach. One particular advantage of RAGs is the automatic generation of on-demand implementations, suitable for query-based interactive tooling as well as for client analyses that do not require full evaluation of underlying analyses. While historically aimed at compiler frontend construction, the addition of circular (fixed-point) attributes also makes them suitable for dataflow problems. However, prior algorithms for on-demand circular RAG evaluation can be inefficient or even impractical for dataflow analysis of realistic programming languages like Java. We propose a new demand algorithm for attribute evaluation that addresses these weaknesses, and apply it to a number of real-world case studies. Our algorithm exploits that some attributes can never be circular, and we describe a static meta-analysis that identifies such attributes, and obtains a median steady-state performance speedup of ~2.5x for a dead-assignment analysis and ~22x for a null-pointer dereference analysis.
Sun 20 OctDisplayed time zone: Pacific Time (US & Canada) change
14:00 - 15:30 | Software Language Design and Implementation ISLE at IBR East Chair(s): L. Thomas van Binsbergen University of Amsterdam | ||
14:00 30mTalk | Concrete Syntax Metapatterns SLE Luka Miljak Delft University of Technology, Casper Bach Poulsen Delft University of Technology, Rosilde Corvino TNO-ESI DOI | ||
14:30 30mTalk | Efficient Demand Evaluation of Fixed-Point Attributes Using Static Analysis SLE Idriss Riouak Department of Computer Science, Lund University, Sweden, Niklas Fors Lund University, Jesper Öqvist Cognibotics, Görel Hedin Lund University, Christoph Reichenbach Lund University DOI Pre-print | ||
15:00 30mTalk | The Design of a Self-Compiling C Transpiler Targeting POSIX Shell SLE Laurent Huberdeau Université de Montréal, Cassandre Hamel Université de Montréal, Stefan Monnier Université de Montréal, Marc Feeley Université de Montréal DOI |