Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Efficient Demand Evaluation of Fixed-Point Attributes using Static Analysis

Riouak, Idriss LU orcid ; Fors, Niklas LU orcid ; Öqvist, Jesper LU ; Hedin, Görel LU orcid and Reichenbach, Christoph LU orcid (2024) 17th ACM SIGPLAN International Conference on Software Language Engineering (SLE), p.56-69
Abstract
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... (More)
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 the fact 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 and s22x for dead-assignment and null-pointer dereference analyses, respectively. (Less)
Please use this url to cite or link to this publication:
author
; ; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
Attribute Grammars, Circular Attributes, Static Analysis, Demand Analysis, Fixpoint Computations
host publication
SLE '24: Proceedings of the 17th ACM SIGPLAN International Conference on Software Language Engineering
pages
12 pages
publisher
Association for Computing Machinery (ACM)
conference name
17th ACM SIGPLAN International Conference on Software Language Engineering (SLE),
conference location
Pasadena, United States
conference dates
2024-10-20 - 2024-10-21
external identifiers
  • scopus:85210844489
ISBN
979-8-4007-1180-0
DOI
10.1145/3687997.3695644
language
English
LU publication?
yes
id
a5fac70c-4615-4cf2-9bc5-faa497d3c834
date added to LUP
2024-11-07 15:19:32
date last changed
2024-12-28 04:02:17
@inproceedings{a5fac70c-4615-4cf2-9bc5-faa497d3c834,
  abstract     = {{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 the fact 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 and  s22x for dead-assignment and null-pointer dereference analyses, respectively.}},
  author       = {{Riouak, Idriss and Fors, Niklas and Öqvist, Jesper and Hedin, Görel and Reichenbach, Christoph}},
  booktitle    = {{SLE '24: Proceedings of the 17th ACM SIGPLAN International Conference on Software Language Engineering}},
  isbn         = {{979-8-4007-1180-0}},
  keywords     = {{Attribute Grammars; Circular Attributes; Static Analysis; Demand Analysis; Fixpoint Computations}},
  language     = {{eng}},
  month        = {{10}},
  pages        = {{56--69}},
  publisher    = {{Association for Computing Machinery (ACM)}},
  title        = {{Efficient Demand Evaluation of Fixed-Point Attributes using Static Analysis}},
  url          = {{http://dx.doi.org/10.1145/3687997.3695644}},
  doi          = {{10.1145/3687997.3695644}},
  year         = {{2024}},
}