摘要： 分析了Krinke切片算法对循环体内嵌套有线程的程序结构会产生切片不精确的现象，认为其原因是该算法对线程间数据依赖的定义过于粗糙，且对程序行为约束不够。该文提出一种新算法，在并发程序内部表示中，增加跨线程边界循环-承载数据依赖，并引入区域化执行证据约束程序行为。实例研究表明，该算法克服了Krinke算法的不精确现象。

关键词: 静态程序切片, 并发程序, 切片算法, 程序依赖图, 执行证据

Abstract: This paper proposes a algorithm for static slicing of concurrent programs. Based on the analysis of the fact that Krinke’s slicing algorithm produces imprecise program slice for the program structure which has loops embedded with one or more threads, a conclusion is drawn that the reason for the impreciseness is that Krinke’s data structure which threads program dependence graph and has over coarse definitions of data dependence relations between threads, The constraint puts on the execution path in concurrent program is too loose. An improved algorithm is proposed which added a new kind of data dependence relation between threads-loop carries data dependence crossing thread boundaries and introduces a new concept of regioned execution witness to further constrain the execution path. Examples show that the improved slicing algorithm could restrain the impreciseness of Krinke’s.

Key words: Static slicing of programs, Concurrent programs, Slicing algorithm, Program dependence graph, Execution witness

中图分类号: 

• TP311.1