May/must analysis and the DFAGen data-flow analysis generator

Andrew Stone, Michelle Strout, Shweta Behere

Research output: Contribution to journalArticlepeer-review

4 Scopus citations


Data-flow analysis is a common technique for gathering program information for use in program transformations such as register allocation, dead-code elimination, common subexpression elimination, and scheduling. Current tools for generating data-flow analysis implementations enable analysis details to be specified orthogonally to the iterative analysis algorithm but still require implementation details regarding the may and must use and definition sets that occur due to the effects of pointers, side effects, arrays, and user-defined structures. This paper presents the Data-Flow Analysis Generator tool (DFAGen), which enables analysis writers to generate analyses for separable and nonseparable data-flow analyses that are pointer, aggregate, and side-effect cognizant from a specification that assumes only scalars. By hiding the compiler-specific details behind predefined set definitions, the analysis specifications for the DFAGen tool are typically less than ten lines long and similar to those in standard compiler textbooks. The main contribution of this work is the automatic determination of when to use the may or must variant of a predefined set usage in the analysis specification.

Original languageEnglish (US)
Pages (from-to)1440-1453
Number of pages14
JournalInformation and Software Technology
Issue number10
StatePublished - Oct 2009
Externally publishedYes


  • Compilers
  • Data-flow analysis
  • May
  • Must
  • Program analysis
  • Static analysis

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'May/must analysis and the DFAGen data-flow analysis generator'. Together they form a unique fingerprint.

Cite this