Write a Blog >>
Fri 22 Jan 2016 11:20 - 11:45 at Grand Bay North - Track 1: Program Design and Analysis Chair(s): Manu Sridharan

Traditional control-flow analysis (CFA) for higher-order languages, whether implemented by constraint-solving or abstract interpretation, introduces spurious connections between callers and callees. Two distinct invocations of a function will necessarily pollute one another’s return-flow. Recently, three distinct approaches have been published which provide perfect call-stack precision in a computable manner: CFA2, PDCFA, and AAC. Unfortunately, CFA2 and PDCFA are difficult to implement and require significant engineering effort. Furthermore, all three are computationally expensive; for a monovariant analysis, CFA2 is in O(2^n), PDCFA is in O(n^6), and AAC is in O(n^8).

In this paper, we describe a new technique that builds on these but is both straightforward to implement and computationally inexpensive. The crucial insight is an unusual state-dependent allocation strategy for the addresses of continuation. Our technique imposes only a constant-factor overhead on the underlying analysis and, with monovariance, costs only O(n^3) in the worst case.

This paper presents the intuitions behind this development, a proof of the precision of this analysis, and benchmarks demonstrating its efficacy.

Conference Day
Fri 22 Jan

Displayed time zone: Guadalajara, Mexico City, Monterrey change

10:30 - 12:10
Track 1: Program Design and AnalysisResearch Papers at Grand Bay North
Chair(s): Manu SridharanSamsung Research America
10:30
25m
Talk
Newtonian Program Analysis via Tensor Product
Research Papers
Thomas RepsUniversity of Wisconsin - Madison and Grammatech Inc., Emma TuretskyCS Dept., Univ. of Wisconsin-Madison, Prathmesh PrabhuGoogle
Media Attached
10:55
25m
Talk
Casper: An Efficient Approach to Call Trace Collection
Research Papers
Rongxin WuDepartment of Computer Science and Engineering, The Hong Kong University of Science and Technology, Xiao XiaoThe Hong Kong University of Science and Technology, Shing-Chi CheungDepartment of Computer Science and Engineering, The Hong Kong University of Science and Technology, Hongyu ZhangMicrosoft Research, Charles ZhangHKUST
Media Attached
11:20
25m
Talk
Pushdown Control-flow Analysis for Free
Research Papers
Thomas GilrayUniversity of Utah, Steven Lyde, Michael D. AdamsUniversity of Utah, Matthew MightUniversity of Utah, USA, David Van HornUniversity of Maryland, College Park
Pre-print Media Attached
11:45
25m
Talk
Binding as Sets of Scopes
Research Papers
Matthew FlattUniversity of Utah
Pre-print Media Attached