TY - JOUR
T1 - May/must analysis and the DFAGen data-flow analysis generator
AU - Stone, Andrew
AU - Strout, Michelle
AU - Behere, Shweta
N1 - Funding Information:
This work was supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, Office of Science, US Department of Energy, under award #ER25724. We would like to thank Paul Hovland and Amer Diwan for their comments and suggestions with regard to this paper, and Lisa Knebl for her editorial suggestions. We would like to thank the reviewers for their extensive comments and suggestions on this paper and our prior conference paper.
PY - 2009/10
Y1 - 2009/10
N2 - 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.
AB - 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.
KW - Compilers
KW - Data-flow analysis
KW - May
KW - Must
KW - Program analysis
KW - Static analysis
UR - http://www.scopus.com/inward/record.url?scp=67650101248&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=67650101248&partnerID=8YFLogxK
U2 - 10.1016/j.infsof.2009.04.014
DO - 10.1016/j.infsof.2009.04.014
M3 - Article
AN - SCOPUS:67650101248
VL - 51
SP - 1440
EP - 1453
JO - Information and Software Technology
JF - Information and Software Technology
SN - 0950-5849
IS - 10
ER -