一种基于程序可达图的并发程序依赖性分析方法

An Approach to Analyzing Dependence of Concurrent Programs Based on Program Reachability Graphs

依赖性分析是一种重要的程序分析手段.针对多线程共享变量通信机制,本文在提出一种新的并发程序表示—线程交互可达图(tIRG)的基础上,从全局分析并发程序的依赖关系,构建了以程序状态和语句二元组为节点的并发程序依赖图(MSDG).与传统的以语句为节点的并发程序依赖图相比,MSDG图中依赖关系不仅精确,且具有可传递性,对其遍历可获得高精度的并发程序切片,精度和效率较其它高精度切片方法有显著提高.

Dependence analysis is an important technique to analyze programs. This paper proposes a novel representation for multi-threaded programs with shared variables, which is called thread interaction reachabih＇ty graph （tlRG）.Based on tlRG, dependences in concurrent programs are analyzed globally and a new dependence graph called MSDG, which vertex is a 2-tuple composed of program state and statement, is constructed. Compared with traditional concurrent program dependence graph which vertex is statement, dependence relation in MSDG is precise and transitive. In contrast to other high-precision slicing methods,more precise slice will be obtained efficiently by traversing MSDG.