Low-level representation of programs in the form of LLVM IR allows for various optimizations to improve the quality of program analysis in SAPFOR (System FOR Automated Parallelization). Being the same for different high-level languages, LLVM IR allows us to explore multilingual applications. At the same time, it loses some features of the program, which are available in its higher level representation. One of these features is the multi-dimensional structure of the arrays. Multi-dimensional view improves the accuracy of data dependency analysis, since the linearized representation of arrays with parametric sizes may not be an affine expression and it will not be possible to apply integer linear programming to analyze it. In addition, the use of multi-dimensional arrays allows us to use multi-dimensional processor matrix and to parallelize a whole loop nests, rather than a single loop in the nest. So, parallelism of a program is going to be increased. These opportunities are natively supported in the DVM system. This paper discusses the approach used in the SAPFOR system to recover the form of multi-dimensional arrays by their linearized representation in LLVM IR. The proposed approach has been successfully evaluated on various applications.

program analysis, semi-automatic parallelization, SAPFOR, DVM, LLVM

Kataev Nikita Andreevich,  ,  orcid.org/0000-0002-7603-4026,  KIAM RAS

Vasilkin Vladislav Nikolaevich,  ,  orcid.org/0000-0002-7918-1849,  CMC MSU