一句话:提出 DoDCFA,一种穷尽式与需求驱动混合的控制流分析,在提升需求驱动 CFA 速度的同时恢复经典 CFA 的适用性,足以支撑内联优化。
函数式程序中调用目标通常由运行时计算得出,使得控制流推理变得困难。经典控制流分析(CFA)虽能有效推理控制流及环境行为,但代价高昂;需求驱动 CFA 虽更廉价,却通用性较差,难以完成经典 CFA 所能承担的任务,而许多基础优化恰恰依赖控制流推理。本文提出按需再按需控制流分析(DoDCFA),一种将穷尽式分析与需求驱动分析相结合的混合 CFA。该方法旨在恢复经典 CFA 的部分通用性与适用性,同时改善需求驱动 CFA 的速度,从而能够以较低成本有效分析控制流与环境行为,为内联(inlining)等优化提供依据。
Understanding program behaviors requires reasoning about control flow. Functional programs complicate this reasoning since call targets are computed in general. Control-flow analysis (CFA) can effectively reason about control flow (and much more) but is costly. Demand-driven CFA is less expensive but less versatile, and it is difficult to make it do what classical CFA does. This is unfortunate because many fundamental optimizations rely on control flow reasoning. In this paper, we present Demand-on-Demand Control-Flow Analysis (DoDCFA), a hybrid exhaustive--demand-driven CFA that recovers some of the versatility/applicability of classical CFA while improving on the speed of Demand CFA. The result is an analysis that can inexpensively and effectively analyze control flow and environment behavior sufficient to justify inlining.