CFA2: A CONTEXT-FREE APPROACH TO CONTROL-FLOW ANALYSIS
CFA2: A CONTEXT-FREE APPROACH TO CONTROL-FLOW ANALYSIS
复制标题
DOI：
10.2168/lmcs-7(2:3)2011
复制
发表时间：
2011-01-01
影响因子：
0.6
通讯作者：
Shivers, Olin
中科院分区：
文献类型：
--
作者：
Vardoulakis, Dimitrios;Shivers, Olin
在函数式语言中，主要的控制流机制是函数调用和返回。大多数高阶流分析，包括k-CFA，不能很好地处理调用和返回：它们只记住有限数量的待处理调用，因为它们用控制流图近似程序。调用/返回不匹配引入了降低精度的虚假控制流路径，并增加了分析时间。我们描述CFA2，这是第一个在高阶函数和尾调用存在时具有精确调用/返回匹配的流分析。我们将CFA2表述为连续传递风格的程序抽象解释，并为我们的抽象语义描述了一个健全和完整的摘要算法。初步评价表明，CFA2比0CFA和1CFA提供了更准确的数据流信息。
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.