Evaluating lexical approximation of program dependence
Evaluating lexical approximation of program dependence
复制标题
评估程序依赖的词法近似
DOI：
10.1016/j.jss.2019.110459
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
S. Yoo
中科院分区：
文献类型：
--
作者：
Seongmin Lee;D. Binkley;N. Gold;Syed S. Islam;J. Krinke;S. Yoo
复杂依赖分析通常提供真正的程序依赖的基本近似。我们研究了使用词法信息来近似这种依赖的有效性，并在基于观察的切片（ORBS）中引入了两个新的删除操作符。ORBS提供对程序依赖性的直接观察，使用迭代的、推测性的删除程序部分来计算切片。如果删除不影响切片标准，则删除是永久的。原始的ORBS使用有界删除窗口操作符，该操作符尝试同时删除连续的行。新的删除操作符尝试删除词法上彼此相似的多个不连续行。我们通过探索使用新删除操作符执行的依赖分析的精度和速度之间的权衡来评估词法依赖近似。删除操作符可以独立评估，也可以通过利用多个删除操作符的ORBS的新泛化来集体评估：多操作符基于观察的切片（MOBS）。使用三个Java项目、六个C项目和一个用Python和C编写的多语言项目进行的经验评估发现，词法信息提供了对底层依赖的有用近似。平均而言，MOBS可以删除原始ORBS删除的69%的行，而仅占用ORBS所需时钟时间的36%。
Complex dependence analysis typically provides an underpinning approximation of true program dependence. We investigate the effectiveness of using lexical information to approximate such dependence, introducing two new deletion operators to Observation-Based Slicing (ORBS). ORBS provides direct observation of program dependence, computing a slice using iterative, speculative deletion of program parts. Deletions become permanent if they do not affect the slicing criterion. The original ORBS uses a bounded deletion window operator that attempts to delete consecutive lines together. Our new deletion operators attempt to delete multiple, non-contiguous lines that are lexically similar to each other. We evaluate the lexical dependence approximation by exploring the trade-off between the precision and the speed of dependence analysis performed with new deletion operators. The deletion operators are evaluated independently, as well as collectively via a novel generalization of ORBS that exploits multiple deletion operators: Multi-operator Observation-Based Slicing (MOBS). An empirical evaluation using three Java projects, six C projects, and one multi-lingual project written in Python and C finds that the lexical information provides a useful approximation to the underlying dependence. On average, MOBS can delete 69% of lines deleted by the original ORBS, while taking only 36% of the wall clock time required by ORBS.