递归子程序的依赖性分析及其应用

程序依赖性是一种重要的程序分析、理解与维护方法，广泛应用于软件工程及软件逆向工程的各个方面，但递归子程序间的依赖分析一直是依赖性分析中的难点。为此，该文提出了一种新的递归子程序间的依赖性分析方法，它首先分析子程序内部的各种依赖关系；然后，结合子程序调用图分析子程序参数间的依赖关系；最后，通过模拟递归子程序的执行过程来分析它们之间的依赖关系。利用该文提供的方法可得到比较精确的递归子程序间的依赖关系。

Dependence Analysis of Recursive Subprograms and Its Applications

Dependence analysis is an important approach to analyze, understand and maintain programs, which has been widely used in software engineering and reengineering. Of all the dependence analysis methods, an approach to analyze dependencies of recursive subprograms is one of the main difficulties. Therefore, the paper proposes a new approach to analyze dependencies among recursive subprograms. In this paper, firstly, we discuss methods to analyze the data dependence and control dependence of a single subprogram in detail. Then, according to the subprogram call graphs, we compute dependence relationships among formal parameters of subprograms i.e. the parameter dependence sets. Then, using the information obtained in the precious steps and by simulating the executions of the recursive subprograms,we propose methods to analyze dependencies among the recursive calls in two cases: direct recursive and indirect recursive calls. The proof of the correctness of our method is presented at the same time. We also present one of the most important applications of dependence analysis--program slicing, using the method presented in this paper. Our method can obtain more precise dependencies among recursive subprograms than any other methods we know.