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 multidimensional 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 multidimensional arrays allows us to use a multi-dimensional processor matrix and to parallelize a whole loop nests, rather than a single loop in the nest. This way, 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.
The multi-dimensional arrays are widely used in many computational programs. For
example, they enable descriptions of the object properties at various points in a
multidimensional computing space. The DVM system [
SAPFOR (System FOR Automated Parallelization) [
Data dependence analysis is obviously required for program parallelization. The
visibility of multi-dimensional view of data allows us to significantly increase the
accuracy and reduce the computational complexity of data dependency analysis in
many cases. To compute loop-carried data dependencies it is possible to perform the
pairwise comparison of expressions which calculate the addresses of accessed
elements. If the expressions that calculate the offset relative to the beginning of the array
are affine with respect to the induction variables of the enclosing loops, then
computation of data dependencies becomes NP-hard problem. In this case integer linear
programming (ILP) solvers are applicable. Moreover, to reduce the complexity of the
problem being solved, heuristics are used. If subscript expressions in a delinearized
accesses satisfy some conditions (for example, expressions are SIV [
It should be noted that a parametric size of an array makes the linearized accesses non-affine so it becomes almost impossible to verify the absence of data dependencies.
The SAPFOR system uses LLVM [
There are two purposes of array delinearization in the context of SAPFOR. The first one is the reconstruction of the array view which was multi-dimensional in the source code. And the second one is the search for equivalent the multi-dimensional view for arrays represented in the program source code in a linearized form. In this paper, we are primarily interested in the approach to recover multi-dimensional view of arrays which were originally multi-dimensional. This follows from the restrictions which DVM system imposes on the programs: the use of multi-dimensional arrays in the source code is required. 2
The paper [
The paper [
If some of array dimensions have parametric sizes while other dimensions have known constant sizes the whole array is treated as an array of parametric size. So, the recovered number of dimensions and recovered multi-dimensional view may differ from the definition of array in the original program.
It also should be noted that to implement delinearization Polly uses its internal data structures which are only partially included in the LLVM core.
Thus, the use of the proposed algorithms in SAPFOR directly becomes impossible.
Let us consider the main points of the approach presented in [
In this case, D_I is the size of the dimension I and S_I is the corresponding subscript expression, I takes values from 0 to N – 1. This equation implies the following ones:
C_N–1 * D_N–1=GCD(S_0 * D_1 * … * D_N–1, …, S_N–2 * D_N–1), (2) C_I * D_I=GCD(S_0 * D_1 * … * D_N–1, … S_I–1 * D_I * … D_N–1) / (D_I+1 *…* D_N–1), 0<I<N–1. (3)
Thus, in order to calculate the size of the dimension I, it is necessary to find the largest common divisor (GCD) of the terms in (1) which are located to the left of the term I, and to divide the GCD into the product of the previously calculated sizes of dimensions from I + 1 to N – 1. The factor C_I is not equal to 1, for example, if the same factor is present in each subscript expression. The GCD function performs a symbolic calculation of the largest common divisor of all its parameters.
The main difficulties of delinearization are as follows: 1. extract the correct number of terms (equal to the dimensionality of the array) from the equation (1) which calculates the address of the array element, 2. arrange these terms in accordance with the order of dimensions, 3. determine the value of the coefficient C_I.
The number of terms in the equation (1) may differ from the number of array dimensions, if some of the subscript expressions are equal to zero, if some of products have computable constant values or if in (1) some of brackets were removed.
The authors of [
The delinearization in SAPFOR is based on the idea of the algorithm used in Polly, but contains some features that enables the recovering a multi-dimensional view of the array in the correspondence with the original array definition in a source program. 3
First of all, it is worth noting that we are considering delinearization for arrays that were multi-dimensional in the original program. For the rest of the arrays, a reconstruction of multi-dimensional view may be useful in order to replace accesses to these arrays in a source code with equivalent accesses to multi-dimensional arrays. In this case delinearization does not depend on representation of arrays in a source code, so the approach implemented in LLVM can be used.
As mentioned above, for arrays of known constant size delinearization is not required. Thus, we consider arrays which have at least one dimension with unknown size.
The getelementptr LLVM instruction is used to get the address of an element of
some aggregate data structure (see Fig. 1).
Fig. 1. An example of LLVM IR which calculates an address of an element A[I][J][
The arguments of this instruction are the address of the beginning of the memory location and one or more indices which are used to calculate the offset relative to the specified base address. In the case of multi-dimensional arrays, the indices are terms from (1) which determine an offset according to each array dimension or explicit subscript expressions (without multiplying by sizes of the array dimensions).
Consider the example of calculating the address of an array element in Fig. 1. The first getelementptr instruction shifts the address of the beginning of the array A (%vla) by the value I*N (%7), the next instruction shifts the received address by the value J*2(%8). It should be noted that multiplication by the size of the last dimension of the array is performed implicitly by the getelementptr instruction (register %8 contains only the value of the variable J). This is due to the fact that the size of the last dimension is fixed, and the array A in LLVM IR is of the type [2 x double]*.
The dependence of the number of arguments of the getelementptr instruction on the
dimensionality of the array can be considered a heuristic (it is possible to construct
the equivalent LLVM IR by replacing all the getelementptr instructions in Fig. 1 with
two parameters: the address of the array and the previously calculated offset), similar
to that used in [
To investigate the dimensionality we use instructions that obviously refer to individual elements of the array, such as load and store. Other instructions (for example, function calls) may take as an argument an entire dimension of an array. This means that the number of arguments in the getelementptr instruction may be less than the number of array dimensions. Another obstacle is the use of zero subscript expressions. Such expressions will be omitted from the getelementptr instruction. To accurately determine the dimensionality of an array, all accesses to its elements are considered and among them, accesses with the maximum number of dimensions are selected.
In many cases the dimensionality is also presented in the debug information. It also contains description of dimensions of the known constant size. Moreover, a variable which specifies size of a dimension in a source code sometimes is also known.
As the next step, we derive the sizes of unknown array dimensions. For this we use equations (2) and (3) mentioned in the previous section. To reduce the error probability, we calculate the largest common divisor of terms obtained for all elementwise accesses to a given array within the analyzed function. We use the shape of getelementptr instruction to extract terms so it allows us to process accesses with non-affine and constant subscript expressions. It should be noted that the C_I coefficient is not equal to 1 only if all subscript expressions that correspond to dimensions in the range [0, I-1] are products with the same factor. In this case it is not possible to accurately determine value of C_I, so we assume it is equal to 1. Hence, the size of the corresponding dimension considered a product with C_I factor. Then the correspondence of a recovered multi-dimensional view with array declaration in a source code will be examined later when a source-to-source transformation is performed.
After the size of the array has been calculated, we extract subscript expressions for each access to the array. Starting from the 0 dimension, the terms are symbolically divided by the product of the sizes of the subsequent dimensions. If the number of terms for a given access is less than the dimensionality of the array, and the product of the sizes of the subsequent dimensions does not divide the current term, then we assume the subscript expression is equal to 0. Thus, zero indices omitted in the getelementptr instruction are restored. It is important to note that at this step we process all accesses to arrays, including those that could not be used to extract the dimensionality of the array.
Arguments of the getelementptr instruction can have a rather complex structure and nested type casts. For the successful computation of the greatest common divisor, as well as for performing symbolic division of terms, it is necessary to simplify expressions and to remove brackets. However, a type casting may change the results of calculations. This means that compilers disallow brackets elimination in many cases to keep precision of computations. This restriction often prevents Polly from realizing delinearization opportunity. In the SAPFOR system, a recovered multi-dimensional view is not used to generate executable code. This view allows us to investigate data dependencies, to build data distribution, and then to insert corresponding DVMH directives into the source code. The DVM system gives a dynamic tool for a functional debugging. So, if necessary it could be used to check correctness of inserted DVMH-directives in the program. In addition, SAPFOR static analyzer implements a command line option -fsafe-type-cast, which prevents analysis and transform passes from unsafe type casting. 4
We used automatically generated test programs to check the capabilities of the described approach and its implementation. In order to cover maximally all possible cases of using arrays, the generated tests were classified by the following parameters: the number of dimensions of the array, a way in which sizes of dimensions are specified (variables (C99 variable length arrays), enumerators, macros, and literal constants of various integer types), memory allocation: dynamic and compile-time arrays, scope of an array which can be local (array declared in the function body or passed as a parameter) or global, various kinds of subscript expressions (containing constants, loop induction variables and other integer variables) the presence of type conversion (explicit and implicit) in array declarations and accesses to arrays.
Each generated test contains a C99 program as well as the expected delinearization result presented in the JSON format. The ability to generate the delinearization result in JSON format was also added to SAPFOR static analyzer.
We use Ctestgen library [
Table 1 shows an example of a generator which creates functions that compute the sum of their arguments. An example of a generated program is shown in Table 2.
A generated test program is an object of the Program class, which consists of include directives (Include class), macro definitions (Define class), enumerations (Enum class), global variables (Var class) and functions (Function class). A function definition comprises a name, a list of arguments and a body which is a block of code. To create a generator, you need to inherit the abstract class ctestgen.generator.TestGenerator and to override the _generate_programs() method, which returns the abstract syntax trees of the described program in the C programming language. int sum_3_nums(int num_0, int num_1, int num_2) { int sum = num_0 + num_1 + num_2; return sum; }
All generated programs are used as input for an application that should be tested (for example, SAPFOR static analyzer). The library determines whether each test is successfully completed and collects statistic of execution of the whole test suite. It is also possible to compare results of a new launch against results of any previous launches. To run tests, you should inherit the abstract class ctestgen.runner.TestRunner and override the _on_test() method, which is called for each program in the given directory.
In the context of SAPFOR the delinearization module is used to construct a parallel
version of the original sequential program, as well as to analyze program properties
(for example, to determine data dependencies). As was noted in [
The implemented delinearization module in conjunctions with data dependence
analysis was also manually checked on NAS Parallel Benchmarks 3.3 [
In this paper, we propose an approach to reconstruction the multi-dimensional view of arrays in the C99 language, which presented in lower level LLVM representation in a linearized form. The presented approach relies on the debug information available in LLVM and the view of low-level instructions which calculate the offsets relative to the address of the array beginning. LLVM uses common debugging format to address the requirements of diverse programming languages. In the future works, this format allows us to apply the developed approach to recovering multi-dimensional arrays in Fortran and to avoid additional analysis of constructs in higher language.
The discussed approach is based on the idea used in the delinearization module, which is implemented in LLVM and Polly. However, in contrast to it our implementation, it provides a more accurate correspondence between the delinearized array and the original definition of a multi-dimensional array in the original program. This advantage is essential in the context of source-level parallelization which is a primary goal of SAPFOR development.
It may be useful to apply the presented approach along with the approach implemented in LLVM to recover multi-dimensional view of arrays which are explicitly linearized in a source code. We believe that such research will allow us to implement source-to-source program transformation which replaces linearized array accesses with delinearized ones.
The source code for the SAPFOR system is available on GitHub [
This work was partially supported by Presidium RAS, program I.26 "Fundamentals of creating algorithms and software for advanced ultra-high performance computing".