The possibilities of static program analysis are often insufficient to investigate real-world applications. Complicated control-flow graph and memory access patterns lead to a conservative assumption of loop-carried data dependencies. To make decisions about the possibility to parallelize loops in a program, SAPFOR implemented a dynamic data dependence analysis. This analysis is based on the instrumentation of the LLVM representation of the analyzed programs and can be performed for applications in the C and Fortran languages. The use of static analysis allows to reduce the number of analyzed memory accesses and to ignore scalar variables, which can be explored in a static way. A selective analysis of program functions and loops is also allowed. These features allow us to significantly reduce the overhead of the program execution time, while maintaining the completeness of the analysis. The developed tool was tested on performance tests from the NAS Parallel Benchmarks package for C and Fortran languages. The implementation of dynamic analysis, in addition to traditional types of data dependencies (flow, anit, output), allows us to determine privitizable variables and a possibility of pipeline execution of loops. Together with the capabilities of DVM and OpenMP these greatly facilitates program parallelization and simplify insertion of the appropriate compiler directives.
Keywords:
program analysis, dynamic analysis, semi-automatic parallelization, SAPFOR, DVM, LLVM
