Based On The Path Symbolic Execution Data Analysis

In this thesis, we will review some traditional methods of detecting data dependence and analyze the relation between the data dependence and the mechanism of parallelism. Based on path analysis and symbolic execution, we describe two methods, static analysis and dynamic analysis, for detecting data dependence of array variables in loops of sequential programs.In static analysis, we generate the control flow graph of the sequential program and convert the graph to an extended finite state machine (EFSM). By analyzing the paths of the EFSM, we can find whether there is data dependence in the program or not. We can also find unexecutable paths of the sequential program. When we find them we will stop the analysis. We enhance the capability of the traditional methods of detecting data dependence. We can deal with the programs that contain some input variables, the programs with control structures and unexecutable paths. With our method more information will be acquired and the accuracy of the analysis will be improved. In some sense, our data dependence analysis is an exact method.We also describe a dynamic method of detecting data dependence. While executing the program, we memorize all the values of each array variable. The analysis will stop if data dependence is found. Although it is not an exact method in data dependence analysis, it can also process some difficult problems, for example, programs with complex subscripts in loops.