some image logo

HOME

SEARCH

CURRENT ISSUE

REGULAR ISSUES

   Volume 1 (2005)

   Volume 2 (2006)

   Volume 3 (2007)

   Volume 4 (2008)

   Volume 5 (2009)

   Volume 6 (2010)

   Volume 7 (2011)

      Issue 1

      Issue 2

      Issue 3

      Issue 4

   Volume 8 (2012)

   Volume 9 (2013)

   Volume 10 (2014)

SPECIAL ISSUES

SURVEY ARTICLES

AUTHORS

ABOUT

SERVICE

LOGIN

FAQ

SUPPORT

CONTACT

VOLUME 7, ISSUE 2, PAPER 3


CFA2: a Context-Free Approach to Control-Flow Analysis

©Dimitrios Vardoulakis, Northeastern University
©Olin Shivers, Northeastern University

Abstract
In a functional language, the dominant control-flow mechanism is function call and return. Most higher-order flow analyses, including k-CFA, do not handle call and return well: they remember only a bounded number of pending calls because they approximate programs with control-flow graphs. Call/return mismatch introduces precision-degrading spurious control-flow paths and increases the analysis time. We describe CFA2, the first flow analysis with precise call/return matching in the presence of higher-order functions and tail calls. We formulate CFA2 as an abstract interpretation of programs in continuation-passing style and describe a sound and complete summarization algorithm for our abstract semantics. A preliminary evaluation shows that CFA2 gives more accurate data-flow information than 0CFA and 1CFA.

Publication date: May 1, 2011

Full Text: PDF | PostScript
DOI: 10.2168/LMCS-7(2:3)2011

Hit Counts: 3619

Creative Commons