Flow Analysis, Linearity, and PTIME

DOI10.1007/978-3-540-69166-2_17MaRDI QIDQ3522075zbMATH OpenOpenAlexFDO

Authors David van Horn, Harry G. Mairson

Publication date 28 August 2008

Published in Static Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.5825

Mathematics Subject Classification ID

Functional programming and lambda calculus (68N18) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Abstract: Flow analysis is a ubiquitous and much-studied component of compiler technology---and its variations abound. Amongst the most well known is Shivers' 0CFA; however, the best known algorithm for 0CFA requires time cubic in the size of the analyzed program and is unlikely to be improved. Consequently, several analyses have been designed to approximate 0CFA by trading precision for faster computation. Henglein's simple closure analysis, for example, forfeits the notion of directionality in flows and enjoys an "almost linear" time algorithm. But in making trade-offs between precision and complexity, what has been given up and what has been gained? Where do these analyses differ and where do they coincide? We identify a core language---the linear $lambda$-calculus---where 0CFA, simple closure analysis, and many other known approximations or restrictions to 0CFA are rendered identical. Moreover, for this core language, analysis corresponds with (instrumented) evaluation. Because analysis faithfully captures evaluation, and because the linear $lambda$-calculus is complete for PTIME, we derive PTIME-completeness results for all of these analyses.

Recommendations

• Relating complexity and precision in control flow analysis
• scientific article; zbMATH DE number 1692944
• Exact flow analysis
• A Fast and Usually Linear Algorithm for Global Flow Analysis
• Comparing flow-based binding-time analyses

Cited in

(7)

• scientific article; zbMATH DE number 1692944 (Why is no real title available?)
• Exact flow analysis
• scientific article; zbMATH DE number 2087548 (Why is no real title available?)
• Comparing flow-based binding-time analyses
• Relating complexity and precision in control flow analysis
• Deciding kCFA is complete for EXPTIME
• Transforming flow information during code optimization for timing analysis

This page was built for publication: Flow Analysis, Linearity, and PTIME

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3522075)