The Design And Implementation Of Dynamic Data Dependence Analysis Tool For C Program Based On LLVM

Nowadays, with the improvement of Internet technology, in order to meet the needs of hundreds of millions of users, computers are starting to use multi-core processors.However,if you want to play full function of these computers,you must ensure the program code will be executed on the computers in parallel.So serial programs parallelization becomes a hotpot. Dependence analysis technology is the key technologies used in the process of program parallelization, hence the computers domain at home and abroad In this regard have corresponding research,in which the static dependence analysis technology in FORTRAN program has achieved some success, but for C program is limited to the alias analysis and shape analysis constraints, resulting in producing too many false dependencies and so on. In view of this situation, in recent years, many new technologies and methods are introduced and used to reduce the parallel overhead and improve the efficiency of parallel computing.This paper mainly analyzes the existing dependence technology and principle,aiming at the cyclic code in C language, which is a typical high concurrent region,and puts forward a dynamic data dependence analysis technique that based on LLVM compiler, at the same time designs and realizes a corresponding dependence analysis tool. The tool can accurate analysis of data dependencies that in loop or between circulations of C programs, and export data dependence analysis results in real time,the main contribution are as follows:1.In terms of dependence technology, this article uses the dynamic data dependence analysis technique to detect the loop level parallelism of C language, and obtains the effective and accurate dependence analysis results at run time. The technology has a wide application scope, at the same time it avoids the shortcomings of static analysis technology in pointer analysis, alias analysis and so on.2.In the aspect of algorithm design and implementation, the paper mainly puts forward a dynamic data dependence analysis algorithm, which is divided into twostages. The first stage is to detect code injection and the static analysis, its duty is to inject test code in the source program code in run time, meanwhile to detect and analysis information of program and other optimization. In static analysis stage mainly uses static analysis technology of LLVM to eliminate undesired data manipulation, subsequently inserts operation monitoring code into the interested data access; The second stage is the stage of data dependence analysis phase, the main principles of code design in this period is that the monitor operation which compiler inserted will continue to collect memory access information at the beginning of the program operation, while calling the run time library to analyze the relationship of recorded memory access information between data dependencies.3. At the same time in study of the parallel conversion in a program, present and realize a dynamic data dependence analysis tool of C program based on LLVM(this paper says “DDA”). This tool is based on the LLVM compiler as a development reference,and reduces the cost by using the compiler’s own advantage, at the same time inserts test code to control the region that may produce dependence,last exports basic information of data dependence.The main innovation of this paper is to expand new functions based on LLVM, so that the compiler not only has a static analysis and Instrumentation, but also can get dependence of accessed data by inserting test code in real time, moreover implements a dynamic data dependence analysis tool that solves the loop level dependency of C program. In the course of the study,the thesis marries static dependence analysis technique and dynamic dependence technology, also combines with the current mainstream Instrumentation to complete the tracking of data dependent information.Through testing with the simple examples and examples of the application. It is proved that the tool is capable of getting the data dependence in loop and providing the results which mainly include dependency type, distance and variables so on.