tag:blogger.com,1999:blog-63312921810283065632023-06-20T21:26:57.110-07:00Roman Gareev's BlogAnonymoushttp://www.blogger.com/profile/15362496381373801396noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-6331292181028306563.post-42249231033693432462016-08-31T03:05:00.000-07:002016-08-31T03:06:21.784-07:00#GSoC 2016 Final report<div dir="ltr" style="text-align: left;" trbidi="on">
Hi everyone!<br />
<br />
I have successfully passed the Google Summer of Code 2016 and below is the copy of my final report.<br />
<br />
Dear LLVM contributors,<br />
<br />
during the Google Summer of Code 2016 I have been working on the "Improvement of vectorization process in Polly" project.<br />
<br />
I planned to add a mode that uses the same Polly tool flow and processes statements, which contain only matrix multiplication of the following form, in a special way.<br />
<br />
C := AB + C, where C, A, and B are matrices of sizes m × n, m × k, and k × n, respectively.<br />
<br />
It was also planned to implement determination of vectorization factors and profitability of vectorization.<br />
<br />
We decided to adjust the goals and focus only on the optimization of matrix multiplication and its generalization. In the result, we optimize a class of statements (see [1] for further details), which also contains the matrix multiplication.<br />
<br />
The result of evaluations of the corresponding code compiled with r279395 of Clang on the Intel Core i7-3820 SandyBridge, for different values of m, n, k and different compiler options can be found on the following link [2].<br />
<br />
According to the figure [2], the algorithm for the computation of the optimal values of the parameters of matrix multiplication can be improved. One way is a new algorithm for the computation of the parameter Mc (see [1] for further details). If we, for example, manually equate the Mc to Nc we get the following results [3]. Its improvement is planned for the future.<br />
<br />
The class also contains general matrix multiplication of the form C := αAB + βC, where C, A, and B are matrices of sizes m × n, m × k, and k × n, respectively. In case, for example, of m = n = 1056 and k = 1024, α = 32412, β = 2123, the corresponding code compiled with r278666 of Clang with following options<br />
<br />
clang -O3 gemm.c -I utilities/ utilities/polybench.c -DPOLYBENCH_TIME -march=native -mllvm -polly -mllvm -polly-pattern-matching-based-opts=true -DPOLYBENCH_USE_SCALAR_LB -mllvm -polly-target-cache-level-associativity=8,8 -mllvm -polly-target-cache-level-sizes=32768,262144 -mllvm -polly-target-througput-vector-fma=1 -mllvm -polly-target-latency-vector-fma=8<br />
<br />
takes about 0.30 on the Intel Core i7-3820 SandyBridge. In case the described optimization is disabled, it takes about 0.75 and 2.1 in case Polly is not used.<br />
<br />
Furthermore, using the optimization we can optimize the following examples of code:<br />
<br />
Loop 1 for i = 0, …, UpperBound1 - 1 in steps of 1<br />
Loop 2 for j = 0, …, UpperBound2 - 1 in steps of 1<br />
Loop 3 for k = 0, …, UpperBound3 - 1 in steps of 1<br />
C[i][j] += 32412 Op1 B[k][j]<br />
endfor<br />
endfor<br />
endfor<br />
<br />
Loop 1 for i = 0, …, UpperBound1 - 1 in steps of 1<br />
Loop 2 for j = 0, …, UpperBound2 - 1 in steps of 1<br />
Loop 3 for k = 0, …, UpperBound3 - 1 in steps of 1<br />
C[i][j] = C[i][j] Op1 A[i][k] Op2 B[k][j]<br />
endfor<br />
endfor<br />
endfor<br />
<br />
where Opi is an operation from the set {+, -, /, *} (see [4], [5], [6], [7] for results of their evaluations).<br />
<br />
The described optimization is implemented in [8], [9], [10], [11], [12], [13], [14] that are already committed and [15] that is under review. For further details about the project, what code got merged, what code did not get merged, and what is left to do, please see my blog posts [1], [16].<br />
<br />
I am planning to continue working on the project as part of my Ph.D. thesis and implement the following:<br />
<br />
1. Prefetching of the certain cache lines<br />
<br />
The BLIS implementation of matrix-matrix multiplication prefetches only the first cache line, before traversing a given interval of memory. This could confirm that the implementation relies on hardware preteching to prefetch the subsequent lines [17]. Consequently, there is a possibility that its utilization could improve the described optimization.<br />
<br />
2. Reduction of the number of the parameters of a target architecture that require to be specified as command line parameters<br />
<br />
At the moment, to be able to use the implemented optimization, one should specify parameters of a target architecture like, for example, throughput of vector instructions per clock cycle (see [1] for further details). Reduction of the number of such parameters using the information about the target architecture of the LLVM (e.g., TargetTransformInfo::getArithmeticInstrCost) could be preferable.<br />
<br />
3. Generalization of determination of parameters of the transformation<br />
<br />
At the moment, for this purpose, we use an algorithm described in "Analytical Modeling is Enough for High Performance BLIS" [1] that was designed to optimize a subclass of the class and could possibly cause performance regression, if we try to apply it to all statements of the class. We could try to create a new algorithm specialized for the whole class.<br />
<br />
I would like to thank Michael Kruse, Albert Cohen, Johannes Doerfert and the LLVM community for your comments, reviews, ideas and the opportunity to work on this project.<br />
<br />
I would like to especially thank Tobias Grosser for his encouragement and excellent support.<br />
<br />
Refs.:<br />
<br />
[1] - http://romangareev.blogspot.ru/2016/06/gsoc-2016-report-i.html<br />
[2] - https://drive.google.com/file/d/0B2Wloo-931AoVTRINXp0dDZPSjQ/view?usp=sharing<br />
[3] - https://drive.google.com/file/d/0B2Wloo-931AoWG9jTjg3aEVxRG8/view?usp=sharing<br />
[4] - https://docs.google.com/spreadsheets/d/1RtioBokRePdX2zdFxGxOxTbtY_WnI4moYFCfbujr7S8/pubhtml?gid=0&single=true<br />
[5] - https://docs.google.com/spreadsheets/d/1hUtXH9JsgYUhHCdydVtE7ayNupc9ViZuAG8z_JKevP0/pubhtml?gid=0&single=true<br />
[6] - https://docs.google.com/spreadsheets/d/1NQHqCuhc1A8pVJtN3FuTHrQ2gcyXUYs5T2L8tMXqLE4/pubhtml?gid=0&single=true<br />
[7] - https://docs.google.com/spreadsheets/d/1nr4qZpG5V--Cq5cTLX1TLA7OpfdFqhIGr6-IFuoq1yw/pubhtml?gid=0&single=true<br />
[8] - http://reviews.llvm.org/D21140<br />
[9] - http://reviews.llvm.org/D21491<br />
[10] - http://reviews.llvm.org/D20575<br />
[11] - https://reviews.llvm.org/D22187<br />
[12] - https://reviews.llvm.org/D22828<br />
[13] - https://reviews.llvm.org/D23740<br />
[14] - https://reviews.llvm.org/D23759<br />
[15] - https://reviews.llvm.org/D23260<br />
[16] - http://romangareev.blogspot.ru/2016/08/gsoc-2016-report-ii.html<br />
[17] - http://lists.llvm.org/pipermail/llvm-dev/2016-May/100229.html</div>
Anonymoushttp://www.blogger.com/profile/15362496381373801396noreply@blogger.com0tag:blogger.com,1999:blog-6331292181028306563.post-45855261252007980532016-08-22T09:55:00.001-07:002016-11-04T09:26:34.521-07:00#GSoC 2016 Report II<div dir="ltr" style="text-align: left;" trbidi="on">
Hi everyone!<br />
<br />
As was mentioned previously, my next task is to implement the packing transformation. It can be described as a data-layout transformation that requires to introduce a new array, copy data to it and change memory access locations to reference the array (see [1], p. 6 for further details).<br />
<br />
By the moment of implementation of the packing transformation, Polly supported the only one data-layout transformation, namely changing of memory access locations. The remaining tasks were to implement creation of empty arrays and copying data to it. However, it was first required to identify the locations that should be changed.<br />
<br />
In case of the following code that could correspond to the matrix-matrix multiplication,<br />
<br />
Loop 1 for i = 0, …, UpperBound1 - 1 in steps of 1<br />
Loop 2 for j = 0, …, UpperBound2 - 1 in steps of 1<br />
Loop 3 for k = 0, …, UpperBound3 - 1 in steps of 1<br />
C[i][j] += A[i][k] * B[k][j]<br />
endfor<br />
endfor<br />
endfor<br />
<br />
the following access function can be built:<br />
<br />
S[i, j, k]->A[i][k], S[i, j, k]->B[k][j].<br />
<br />
According to the algorithm used to optimize matrix multiplication and described in "Analytical Modeling is Enough for High Performance BLIS" [1] they should be changed to the following access relations:<br />
<br />
S[O0, O1, O2, O3, O4, O5, O6, O7, O8]->Ac[O5 + K * O3, O6] and<br />
<br />
S[O0, O1, O2, O3, O4, O5, O6, O7, O8]->Bc[O5 + K * O4, O7], respectively.<br />
<br />
The transformation helps to access elements of operands of a matrix multiplication after creation of the BLIS micro and macro kernels. The described approach is implemented in [3] and also already<br />
available from the main repository.<br />
<br />
The next task was to create an empty array. To do it, we use an object of the ScopArrayInfo class<br />
that is designed to store information (e.g., the type of the elements, dimension sizes) about arrays in the SCoP (see [2] for further details). In our case, it is not a part of the SCoP originally. Furthermore, the array would be allocated only during the work of the CodeGeneration pass that takes a mathematical model derived and optimized using Polly and translates it back to LLVM-IR. The described approach is implemented in [3] and already available from the main repository.<br />
<br />
The last task was to copy data to the newly created arrays according to the packing transformation.<br />
<br />
To implement it, we decided to introduce a new type of SCoP statement that has one read memory access and one write memory access (in this very order). In particular, data is loaded from the location described by the read memory access and written to the location described by the<br />
write memory access. To describe the domain of such a statement, we use extension nodes of the integer set library [4].<br />
<br />
The described approach is implemented in [5]. It helps to get the following execution time improvements of benchmarks from PolyBench [6], which correspond to matrix multiplications.<br />
<br />
Performance Improvements - Execution Time Δ Previous Current<br />
SingleSource/Benchmarks/Polybench/linear-algebra/kernels/3mm/3mm -70.59% 7.1680 2.1080<br />
SingleSource/Benchmarks/Polybench/linear-algebra/kernels/2mm/2mm -68.85% 4.7640 1.4840<br />
SingleSource/Benchmarks/Polybench/linear-algebra/kernels/gemm/gemm -66.61% 2.3720 0.7920<br />
<br />
The results obtained from the Polly buildbot perf-x86_64-penryn-O3-polly are available on the following link [7].<br />
<br />
Although it is already implemented, we continue to improve the patch and general Polly infrastructure related to it. In particular, we are planning to implement the ability to introduce the SCoP statements via the JSCoP that helps to test new optimizations without any knowledge about compiler internals [8]. During this GSoC we’ve already extended the JSCoP to allow the user to declare new arrays and to reference these arrays from access expressions. It is implemented in [9] and<br />
already available from the main repository.<br />
<br />
Refs.:<br />
<br />
[1] - http://www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf<br />
[2] - http://llvm.org/viewvc/llvm-project/polly/trunk/include/polly/ScopInfo.h?view=markup<br />
[3] - https://reviews.llvm.org/D22187<br />
[4] - http://isl.gforge.inria.fr<br />
[5] - https://reviews.llvm.org/D23260<br />
[6] - http://web.cs.ucla.edu/~pouchet/software/polybench/<br />
[7] - https://gareevroman.github.io<br />
[8] - http://www.infosun.fim.uni-passau.de/cl/arbeiten/grosser-d.pdf<br />
[9] - https://reviews.llvm.org/D22828</div>
Anonymoushttp://www.blogger.com/profile/15362496381373801396noreply@blogger.com0tag:blogger.com,1999:blog-6331292181028306563.post-39638881270661979562016-06-21T00:27:00.000-07:002016-06-22T08:56:48.228-07:00#GSoC 2016 Report I<div dir="ltr" style="text-align: left;" trbidi="on">
Hi everyone!<br />
<br />
As was mentioned in my previous blog post, one of the first tasks is to implement tilings and interchangings of specific loops based on the algorithm used to optimize matrix multiplication and described in "Analytical Modeling is Enough for High Performance BLIS" [1]. It was decided to do it step-by-step. This blog post is devoted to its description.<br />
<br />
Let's assume that matrix multiplication has the following form and matrices A, B and C stored into row-major order, in contrast to column-major order used in [1].<br />
<br />
Loop 1 for i = 0, …, UpperBound1 - 1 in steps of 1<br />
Loop 2 for j = 0, …, UpperBound2 - 1 in steps of 1<br />
Loop 3 for k = 0, …, UpperBound3 - 1 in steps of 1<br />
C[i][j] += A[i][k] * B[k][j]<br />
endfor<br />
endfor<br />
endfor<br />
<br />
In this case, the optimized code could look like this,<br />
<br />
Loop 1 for ic = 0, ..., UpperBound1 − 1 in steps of mc<br />
Loop 2 for pc = 0, ..., UpperBound3 − 1 in steps of kc<br />
Ac = Pack(A(ic : ic + mc − 1, pc : pc + kc − 1))<br />
Loop 3 for jc = 0, ..., UpperBound2 − 1 in steps of nc<br />
Bc = Pack(B(pc : pc + kc − 1, jc : jc + nc − 1))<br />
Loop 4 for ir = 0, ..., mc − 1 in steps of mr<br />
Loop 5 for jr = 0, ..., nc − 1 in steps of nr<br />
Loop 6 for pr = 0, ..., kc − 1 in steps of 1<br />
Cc(ir :ir +mr 1,jr :jr +nr 1) += Ac (ir : ir + mr 1, pr ) * Bc(pr, jr:jr+nr 1)<br />
endfor<br />
endfor<br />
endfor<br />
endfor<br />
endfor<br />
endfor<br />
<br />
where Loop 4 and Loop 5 form a macro-kernel around Loop 6, which contains rank-1 updates and forms a micro-kernel.<br />
<br />
The first step was to create a micro-kernel. To do it, we tile the first two loops of the matrix multiplication and consequently unroll them. In the result we get this code:<br />
<br />
Loop 1 for ir = 0, …, UpperBound1 - 1 in steps of mr<br />
Loop 2 for jr = 0, …, UpperBound2 - 1 in steps of nr<br />
Loop 3 for k = 0, …, UpperBound3 - 1 in steps of 1<br />
C[i][j] += A[i][k] * B[k][j]<br />
…<br />
C[i][j + nr - 1] += A[i][k] * B[k][j + nr - 1]<br />
…<br />
C[i + mr - 1][j + nr - 1] += A[i + mr - 1][k] * B[k][j + nr - 1]<br />
endfor<br />
endfor<br />
endfor<br />
<br />
If auto-vectorization is enabled in LLVM, the body of Loop 3 may be replaced with rank-1 updates and we'll get a mirco-kernel. It's utilized in [2].<br />
<br />
The second step was the creation of a macro-kernel by applying a combination of tiling of the first three loops and interchanging Loop 3 and Loop 2. This approach was implemented in [3].<br />
<br />
However, without the optimal parameter values creation of the described kernels could lead to not highly optimized implementations or even increase execution time of generated code. To address the issue, we use the optimization model for mapping the GEMM algorithm described in [1].<br />
<br />
It requires information about the following parameters of a target architecture:<br />
<br />
1. Size of double-precision floating-point number.<br />
<br />
2. Number of double-precision floating-point numbers that can be hold by a vector register.<br />
<br />
3. Throughput of vector instructions per clock cycle.<br />
<br />
4. Latency of instructions (i.e., the minimum number of cycles between the issuance of two dependent consecutive instructions).<br />
<br />
5. Paramaters of cache levels (size of cache lines, associativity degrees, size, number of cache sets).<br />
<br />
The first two parameters can be obtained from the TargetTransformInfo class. Therefore, since the product of a number of cache sets and a size of cache lines is a size divided by an associativity degree, we should determine only the four parameters. At the moment they can be specified as command line parameters.<br />
<br />
Even if we able to get close-to-peak performance of matrix multiplication, we have to determine that the code under consideration contains matrix multiplication. To address the issue, we specified the following class of statements, which contains matrix multiplication:<br />
<br />
1. There are exactly three input dimensions<br />
2. All memory accesses of the statement will have stride 0 or 1, if we interchange loops (switch the variable used in the inner loop to the outer loop)<br />
3. All memory accesses of the statement except from the last one, are read memory access and the last one is write memory access<br />
4. All subscripts of the last memory access of the statement don't contain the variable used in the inner loop<br />
<br />
The larger class was introduced in [4] to simplify its determination and to make a step toward generalization, which is planned for the future.<br />
<br />
Refs.:<br />
<br />
[1] - http://www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf<br />
[2] - http://reviews.llvm.org/D21140<br />
[3] - http://reviews.llvm.org/D21491<br />
[4] - http://reviews.llvm.org/D20575<br />
<div>
<br /></div>
</div>
Anonymoushttp://www.blogger.com/profile/15362496381373801396noreply@blogger.com0tag:blogger.com,1999:blog-6331292181028306563.post-12149739727406254842016-06-21T00:20:00.001-07:002016-06-21T00:20:41.306-07:00My GSOC 2016 Proposal: Improvement of vectorization process in Polly<div dir="ltr" style="text-align: left;" trbidi="on">
Hi everyone!<br />
<br />
At the moment I'm participating in Google Summer of Code 2016. My next blog posts will be devoted to the updates of the project after reaching the mile stones. Below is the accepted proposal.<br />
<div>
<br /></div>
<div>
<span id="docs-internal-guid-a7297157-71cf-c8c3-d526-593dbaa074f8"><div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">Title:</span><span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"> Improvement of vectorization process in Polly</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">Abstract</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt; text-indent: 12.75pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Polly can perform classical loop transformations, exploit OpenMP level parallelism, expose SIMDization opportunities. However, due to the lack of a machine-specific performance model and missing optimizations, these transformations sometimes lead to compile and execution time regressions, and the generated code is at least one order of magnitude off in comparison to the corresponding vendor implementations. The goal of the project is to reduce such influence through implementation of optimizations aimed to produce code compatible with the best implementations of BLAS and an attempt to avoid vectorization of loops, when it is not profitable for the target architecture. It could be a step in transformation of Polly into an optimization pass used in standard -O3 optimizations.</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">1 Summary</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt; text-indent: 12.75pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">A Polly framework is applied to a broad class of programs that sometimes causes a regression and is not reasonable. Our project aims to reduce such influence, which could be a step in transformation of Polly into an optimization pass used in standard -O3 optimizations.</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">2 The project</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt; text-indent: 12.75pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Although Polly performs classical loop transformations, especially tiling and loop fusion to improve data-locality, it can also be used to expose SIMDization opportunities. To do so, we can utilize, for example, a prevectorization, the choice of a possible outer loop that is strip-mined to the innermost level to enable inner-loop vectorization. In certain cases, it could give 50.31% of execution-time improvement [1].</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt; text-indent: 12.75pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">However, tests such as the SingleSource/Benchmarks/Polybench/linear-algebra/ solvers/lu/lu from the LLVM test-suite show that sometimes these transformations are not reasonable and only result in the compile time regression. Furthermore, the result of SingleSource/Benchmarks/Polybench/medley/floyd-warshall/floyd-warshall stated in [2] demonstrates that there are cases when utilization of Polly leads to the execution time regression.</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt; text-indent: 12.75pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Even if the issues mentioned above are solved, Polly is about 3x off in comparison to the vendor implementations of BLAS. For example, let us consider the GEMM operation of the form C := AB + C, where C, A, and B are matrices of sizes 1056 × 1056, 1056 × 1024, and 1024 × 1056, respectively. A corresponding code compiled with r262915 of Clang takes about 2.02. Polly and its prevectorization help to attain 0.26. However, usage of BLAS routines such as a dgemm from the Intel MKL even in sequential mode can reduce this number to 0.086.</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt; text-indent: 12.75pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">The goal of our project is to improve the vectorization process in Polly by working in two directions: first, reduction of compile and execution time regressions; second, reduction of execution time in situations when speedup is already achieved. In the first case, it is planned to estimate loops and determine their optimal vectorization factors based on the LLVM vectorization cost model in order to expose SIMDization opportunities only in those loops, which are estimated as profitable. In the second case, the best implementations of the GEMM operation will be considered in order to find and implement things missed in both default optimizations of Polly and transformation to expose SIMDization opportunities. Furthermore, we’ll add a new mode that uses the same Polly tool flow, processes statements, which contain only matrix multiplication, and helps reduce the regressions.</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">3 Benefits for Polly</span></div>
<ul style="margin-bottom: 0pt; margin-top: 0pt;">
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">A new mode of Polly could be interested for people who would like to use Polly and worry about compile and execution time regressions.</span></div>
</li>
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Specific optimization of the GEMM operation along with determination of optimal vectorization factors of loop will reduce the execution time of code generated by Polly.</span></div>
</li>
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Vectorization of loops, which are profitable according to the LLVM vectorization cost model, will reduce the average compile time of Polly.</span></div>
</li>
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Determination of loops, which are not profitable according to the LLVM vectorization cost model, allow to optimize them with different optimization strategies (e.g., register tiling), which could probably produce speed up.</span></div>
</li>
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Implementations of things related to the effective optimization of the GEMM operation (i.e., a packing transformation) could probably improve default optimization sequence of Polly.</span></div>
</li>
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Even though Polly is already able to speed up compute kernels significantly, when comparing to the best BLAS routines we still are at least one order of magnitude off [3]. This project could be a step toward obtaining fast BLAS kernels, which are competitive with vendor math libraries.</span></div>
</li>
</ul>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">4 Details about the project</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">Performance of single-threaded GEMM with different implementations</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt; text-indent: 12.75pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">The GEMM operation computes C := αAB + βC, where C, A, and B are matrices of sizes m × n, m × k, and k × n, respectively. For simplicity, we will assume that α = β = 1. In case, for example, of m = n = 1056 and k = 1024, a corresponding implementation [4] compiled with r262915 of Clang with following options takes about 2.02 on the Intel Core i7-3820 SandyBridge.</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt; text-indent: 12.75pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">-O3 -I /utilities/ /utilities/polybench.c -DPOLYBENCH_TIME -DPOLYBENCH_USE_SCALAR_LB -march=native</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt; text-indent: 12.75pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">However, a code based on the BLIS framework [5], the Intel MKL or the OpenBLAS can reduce this number even in case of a sequential implementation and take 0.088, 0.086 and 0.0865, respectively.</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt; text-indent: 12.75pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">The following figure shows the result of evaluations of these implementations on the Intel Core i7-3820 SandyBridge, for different values of m, n, k.</span></div>
<br /><img height="285" src="https://lh6.googleusercontent.com/_v0mdeefQBTK-ef4UvY6IitNfAY-tdVLaotF4V1FIVRZSgSJovgoeYjgENZnSe4V_vQCy5hbTI1Aul741mMxE7XpRUuDg8TuJBt0flK3PmrwKzKN1cWm2mA6xNxFv9MnUYJpDyFl" style="border: none; transform: rotate(0rad);" width="400" /><br /><br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">Porting to Polly</span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt; text-indent: 12.75pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Polly is another way to optimize [4], which doesn’t require usage of external libraries and helps to get the results presented in the following figure that shows a performance gap between code optimized with Polly and implementations stated above. </span><img height="188" src="https://lh5.googleusercontent.com/U3H4OP4zan0iKZkLC94q-l8yMU9HXHGYrn9JOyqrj5HjXVqlasS7E-CtM4PXEE8G6B8hC0iCbfKUlxovT_U3yBWYUWP63c0V_ws2hDiUy8QhmVgIuwCuVyrHLcuex7P6pNkmlGUx" style="border: none; transform: rotate(0rad);" width="400" /></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 9pt; margin-top: 0pt; text-indent: 12.75pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Consideration of an algorithm from [6], which is used to perform the GEMM operation in the BLIS framework, and its implementation written in C [7] for Intel Core i7-3820 SandyBridge reveals the following things, which could be added to Polly to try to achieve the same performance:</span></div>
<ul style="margin-bottom: 0pt; margin-top: 0pt;">
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Tilings and interchanges of specific loops can produce loop nests which are similar to those presented in [6]. Furthermore, [6] describes an algorithm of determination of tiling parameters based on the following properties of the target architecture: sizes of cache lines, associativity degrees and sizes of caches, parameters of fused multiply-add instructions. Consequently, an implementation of matrix multiplication can be tuned without access to the target machine.</span></div>
</li>
</ul>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">However, these transformations can not always improve generated code on its own. For example, a JSoP, which can be found on the following link [8], helps to generate a loop nest, which is similar to the one stated in [6], but increases the execution time to 0.62. It reveals the next missing piece, a packing transformation.</span></div>
<br /><ul style="margin-bottom: 0pt; margin-top: 0pt;">
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">A packing transformation can be described as a transformation, which replaces accesses to a tile of a matrix with accesses to a temporary block of consecutive memory locations that contain elements of the replaced tile. For example, its utilization helps to reduce execution time from 0.78 to 0.27.</span></div>
</li>
</ul>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Although Polly doesn’t perform the transformation at the moment, it can be modeled using the memory address modification support.</span></div>
<br /><ul style="margin-bottom: 0pt; margin-top: 0pt;">
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Further improvements can be achieved taking into account information about SIMD registers usage during matrix multiplication from [6]. For example, micro-tiles Cr and br, the result of tiling of loops 5 and 6 from [6], can be loaded from memory, employed in the multiplication and only after this stored. This helps to reduce the execution time from 0.27 to 0.10.</span></div>
</li>
</ul>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 12.75pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">The following figure shows the result of evaluations of the implementation of [6] written in C on the Intel Core i7-3820 SandyBridge, for different values of m, n, k.</span></div>
<br /><img height="188" src="https://lh5.googleusercontent.com/A0jjkMloDkAUi0lNgxibu5NovQ3wfbj9VWTFZrLfVo-JdrEqBqchMjIb276uoQGHnaEG_8f6zPrWGWmjoyXfZbr2rviR3lYo2aagOazmmgVe3pBwDFMXTuzFzocAwzH1lLdeemCF" style="border: none; transform: rotate(0rad);" width="400" /><br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 12.75pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">It shows that there is still a gap between the mentioned implementation written in C and those based on the BLIS framework, the Intel MKL or the OpenBLAS, which use inline assembly. A possible way to attain the same performance is an improvement of instruction selection as well as register allocation, which could probably influence on the translation from LLVM-IR.</span></div>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Of course, Polly is used to optimize a broader class of programs, which includes the matrix multiplication. Sometimes this causes a regression (for example, in case of SingleSource/Benchmarks/Polybench/medley/floyd-warshall/floyd-warshall from the LLVM test suite [2]) and is not reasonable (for example, in case of SingleSource/Benchmarks/Polybench/linear-algebra/solvers/lu/lu from the LLVM test suite [1]). In this project we aim to add a new mode that uses the same Polly tool flow, processes statements, which contain only matrix multiplication, and helps reduce the regression. It can also be used by default optimization sequence of Polly to handle matrix multiplication in a special way.</span></div>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">Determination of profitability of vectorization</span></div>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Although, in certain cases, vectorization could give 50.31% of execution-time improvement of generated code [1]. Tests such as the SingleSource/Benchmarks/Polybench/ linear-algebra/solvers/lu/lu from the LLVM test-suite show that sometimes these transformations are not reasonable and only result in the compile time regression [2]. Furthermore, let us consider work of the prevectorization, a main transformation of vectorization in Polly. The prevectorization is the choice of a possible outer loop that is strip-mined to the innermost level to enable inner-loop vectorization. The goal of this transformation implemented in Polly is to create a trivially vectorizable loop. This means a parallel loop at the innermost level that has a constant number of iterations corresponding to the target vector width and, therefore, can be easily vectorized by LLVM’s inner loop vectorizer (or Polly's simple vectorizer). However, its implementation has a drawback, because it always uses a vectorization factor of four, even in case the vector registers of a target architecture can’t hold these number of elements or would allow even wider vector operations</span></div>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">To address these issues, we aim to implement a determination of vectorization factors and profitability of vectorization based on the LLVM vectorization cost model. It uses an algorithm, which can be roughly described as follows:</span></div>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;">// A vectorization factor. In the end its value will be equal to one, if vectorization is not profitable.</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;">unsigned VF;</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;">TargetTransformInfo TTI;</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;">unsigned WidestRegister = TTI.getRegisterBitWidth(true);</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;">// Traverse each instruction in the loop and examine only Loads, Stores and PHINodes in order to determine the minimal and the maximal sizes in bits of used types.</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;">std::tie(SmallestType, WidestType) = getSmallestAndWidestTypes();</span></span></div>
<span style="font-size: xx-small;"><br /></span><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;">unsigned MaxVectorSize = WidestRegister / WidestType;</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;">unsigned NewMaxVectorSize = WidestRegister / SmallestType;</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;">// Select the largest VF which doesn't require more registers than existing ones.</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;">for (unsigned VS = MaxVectorSize; VS <= NewMaxVectorSize; VS *= 2) </span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;"> if (calculateRegisterUsage(VS) < TargetNumRegisters)</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;"> VF = VS;</span></span></div>
<span style="font-size: xx-small;"><br /></span><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;">// Computation of expectedCost based on cost of every instruction from the loop computed in LoopVectorizationCostModel::getInstructionCost.</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;">float Cost = expectedCost(1);</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;">for (unsigned i=2; i <= VF; i*=2) {</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;"> float VectorCost = expectedCost(i) / (float)i;</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;"> if (VectorCost < Cost) {</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;"> Cost = VectorCost;</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;"> Width = i;</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;"> }</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Courier New'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: xx-small;">}</span></span></div>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">It is planned to apply the algorithm in the ScheduleTreeOptimizer::optimizeBand to call the ScheduleTreeOptimizer::prevectSchedBand only in case it is profitable.</span></div>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">Timeline</span></div>
<br /><ul style="margin-bottom: 0pt; margin-top: 0pt;">
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">23 May – 29 May: Get more familiar with things missed in Polly to attain the best implementation of the gemm.</span></div>
</li>
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">30 May – 5 June: Get more familiar with the LLVM vectorization cost model.</span></div>
</li>
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">6 June – 19 June: Implement tilings and interchanges of specific loops based on the algorithm presented in [6].</span></div>
</li>
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">20 June – 27 June: Vacation.</span></div>
</li>
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">28 July – 3 July: Implementation of the packing transformation.</span></div>
</li>
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">4 July – 10 July: Testing and fixing bugs.</span></div>
</li>
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">11 July – 24 July: Add generation of specific code, which takes into account information </span><span style="font-size: 16px; white-space: pre-wrap;">about SIMD registers.</span></div>
</li>
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">25 July - 31 July: Testing and fixing bugs.</span></div>
</li>
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">1 August - 7 August: Implement a determination of vectorization factors and profitability of vectorization based on the LLVM vectorization cost model.</span></div>
</li>
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">8 August - 23 August: Testing and fixing bugs.</span></div>
</li>
</ul>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">5 Required deliverables</span></div>
<br /><ul style="margin-bottom: 0pt; margin-top: 0pt;">
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Add a mode that uses the same Polly tool flow and processes statements, which contain only matrix multiplication, in a special way</span></div>
</li>
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Implement determination of vectorization factors and profitability of vectorization.</span></div>
</li>
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Pass regression tests</span></div>
</li>
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Add new tests to testsuite</span></div>
</li>
</ul>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">6 Nice to have</span></div>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">According to advancement in work on the integration and results, we want to:</span></div>
<ul style="margin-bottom: 0pt; margin-top: 0pt;">
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Extend a new mode to hold statements, which contain different code along with matrix multiplication.</span></div>
</li>
<li dir="ltr" style="font-family: 'Times New Roman'; font-size: 10.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; list-style-type: disc; vertical-align: baseline;"><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt;">
<span style="font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">Implement a heuristic to choose which dimension to prevectorize, if they are multiple. At the moment Polly always uses the first coincident dimension.</span></div>
</li>
</ul>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">About me</span></div>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">I am a first year P.h.D. student at Ural Federal University majoring in "Mathematical modelling, numerical methods, and software complexes". At the moment my research focuses on a machine-specific performance modelling and polyhedral optimizations. </span></div>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">I have been interested for years in compiler development and, in particular, in polyhedral compilation. Along with academic experience in writing compilers using ANTLR, Flex, Bison, I have experience of working in the LLVM Compiler Infrastructure and the GNU Compiler Collection. I successfully completed the project "Integration of ISL code generator into Graphite" during the participation in the GSoC 2014 in the GNU Compiler Collection. Its description and code samples can be found on the following link [9]. As part of my research, I have added new features to Polly and its vectorization process [10], [11], [12]. I have also fixed a bug of LICM [13], [14] fixed the following bugs of Polly [15], [16], [17], [18], [19], [20].</span></div>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: 11pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">I will be available to work full time (40 hours per week) on this project.</span></div>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-size: 16px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; font-weight: 700; vertical-align: baseline; white-space: pre-wrap;">Ref</span></div>
<br /><div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[1] - https://drive.google.com/file/d/0B2Wloo-931AoQ1FRa0ZVbWdzc28/view?usp=sharing</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[2] - https://drive.google.com/file/d/0B2Wloo-931AoLWFjeVZMbDF3UE0/view?usp=sharing</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[3] - http://polly.llvm.org/projects.html</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[4] - https://drive.google.com/file/d/0B2Wloo-931AoRTlVUVRKb1h6TFk/view?usp=sharing</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[5] - https://github.com/flame/blis</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[6] - http://www.cs.utexas.edu/users/flame/pubs/TOMS-BLIS-Analytical.pdf</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[7] - https://drive.google.com/file/d/0B2Wloo-931AoUUU1T2ZLTDFHNFk/view?usp=sharing</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[8] - https://drive.google.com/file/d/0B2Wloo-931AoR0tYOVJDbXRPMTQ/view?usp=sharing</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[9] - https://www.google-melange.com/gsoc/project/details/google/gsoc2014/groman/5639274879778816</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[10] - http://reviews.llvm.org/D13779</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[11] - http://reviews.llvm.org/D14491</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[12] - http://repo.or.cz/polly-mirror.git/commit/4d9f318d4114d64062f38b0c7efd9e0ef647cc8f</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[13] - https://llvm.org/bugs/show_bug.cgi?id=23077</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[14] - http://reviews.llvm.org/D16753</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[15] - http://repo.or.cz/polly-mirror.git/commit/defbd21a86ca0c3b595096720a49428c014b2c55</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[16] - http://reviews.llvm.org/D15563</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[17] - https://llvm.org/bugs/show_bug.cgi?id=25759</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[18] - https://llvm.org/bugs/show_bug.cgi?id=19422</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[19] - https://llvm.org/bugs/show_bug.cgi?id=25760</span></span></div>
<div dir="ltr" style="line-height: 1.38; margin-bottom: 0pt; margin-right: -36pt; margin-top: 0pt; text-indent: -1.5pt;">
<span style="font-family: 'Times New Roman'; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><span style="font-size: x-small;">[20] - http://repo.or.cz/polly-mirror.git/commit/f95553beea5c274749d3ddad61c4e7c06f6dafaf</span></span></div>
<div>
<span style="font-family: 'Times New Roman'; font-size: 14.666666666666666px; font-variant-alternates: normal; font-variant-east-asian: normal; font-variant-ligatures: normal; font-variant-numeric: normal; font-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;"><br /></span></div>
</span></div>
</div>
Anonymoushttp://www.blogger.com/profile/15362496381373801396noreply@blogger.com0tag:blogger.com,1999:blog-6331292181028306563.post-64302355078132257912014-05-31T15:51:00.001-07:002014-05-31T16:24:16.632-07:00#GSoC Report II<div dir="ltr" style="text-align: left;" trbidi="on">
<div align="LEFT" style="border: none; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<div style="font-style: normal; font-variant: normal; font-weight: normal; margin-bottom: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">Hi
everyone!</span></span></div>
<div align="LEFT" style="font-style: normal; font-variant: normal; font-weight: normal; margin-bottom: 0cm;">
<br /></div>
<div align="LEFT" style="font-style: normal; font-variant: normal; font-weight: normal; margin-bottom: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">As
I told you before, my second task is to get more familiar with CLooG
generation. In this post, I'll consider an example of it.</span></span></div>
<br />
<div align="LEFT" style="margin-bottom: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">If
we give the following code as an input to Graphite</span></span></div>
</div>
<div align="LEFT" style="border: none; margin-bottom: 0cm; padding: 0cm;">
<div align="LEFT" style="border: none; margin-bottom: 0cm; padding: 0cm;">
<pre class="cpp" name="code" style="line-height: 0.4cm;">#include <stdio.h>
#define N 16
int
main1 (int n, int *a)
{
int i, j;
for (i = 0; i < n - 1; i++)
for (j = 0; j < n; j++)
a[j] = i + n;
for (j = 0; j < n; j++)
if (a[j] != i + n - 1)
__builtin_abort ();
return 0;
}
int
main ()
{
int a[N];
main1 (N, a);
return 0;
} </pre>
<div align="LEFT" style="border: none; margin-bottom: 0cm; padding: 0cm;">
<div align="LEFT" style="border: none; margin-bottom: 0cm; padding: 0cm;">
<div style="line-height: 0.4cm;">
<br />
<div align="LEFT" style="margin-bottom: 0cm;">
<span style="font-family: 'Times New Roman', serif; line-height: 0.4cm;">Graphite will</span><span style="color: black;"><span style="font-family: Times New Roman, serif;"> outline the following SCoP:</span></span></div>
</div>
<div style="line-height: 0.4cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><br /></span></span></div>
<div align="LEFT" style="border: none; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">Schedule of the basic block: [n, P_37] -> { S_5[i0, i1] -> [0, i0, 0, i1, 0] }</span></span></div>
<div align="LEFT" style="border: none; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><br /></span></span></div>
<div align="LEFT" style="border: none; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
</div>
<div align="LEFT" style="border: none; margin-bottom: 0cm; padding: 0cm;">
<div style="line-height: 0.4cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">Domain of the basic block: [n, P_37] -> { S_5[i0, i1] : exists (e0 = [(-2 + n)/4294967296], e1 = [(-1 + n)/4294967296]: i0 >= 0 and 4294967296e0 <= -2 + n and 4294967296e0 >= -4294967297 + n and 4294967296e0 <= -2 + n - i0 and i0 <= 2147483645 and i1 >= 0 and 4294967296e1 <= -1 + n and 4294967296e1 >= -4294967296 + n and 4294967296e1 <= -1 + n - i1 and i1 <= 2147483646 and n >= 1) }</span></span></div>
<div style="line-height: 0.4cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><br /></span></span>
</div>
<div align="LEFT" style="line-height: 0.4cm; margin-bottom: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">Let's
generate a CLoogInput</span></span><br />
<pre class="cpp" name="code" style="line-height: 0.4cm;">static CloogInput *
generate_cloog_input (scop_p scop)
{
CloogUnionDomain *union_domain;
CloogInput *cloog_input;
CloogDomain *context;
union_domain = build_cloog_union_domain (scop);
context = cloog_domain_from_isl_set (isl_set_copy (scop->context));
cloog_input = cloog_input_alloc (context, union_domain);
return cloog_input;
}
</pre>
<br />
<div align="LEFT" style="margin-bottom: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">A
CloogInput structure represents the input to CLooG. It is essentially
a CloogUnionDomain along with a context
CloogDomain. CloogDomain is
an type representing a polyhedral domain (a union of polyhedra).
“generate_cloog_input()” transforms
type of scop's context to type, which is
appropriate for CloogInput.
“build_cloog_union_domain” is used for generation of
CloogUnionDomain, which contains all
CloogUnion corresponding to all
basic blocks in the given scop. </span></span></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><br /></span></span></div>
</div>
<pre class="cpp" name="code" style="line-height: 0.4cm;">static CloogUnionDomain *
build_cloog_union_domain (scop_p scop)
{
int i;
poly_bb_p pbb;
CloogUnionDomain *union_domain =
cloog_union_domain_alloc (scop_nb_params (scop));
FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
{
CloogDomain *domain;
CloogScattering *scattering;
/* Dead code elimination: when the domain of a PBB is empty,
don't generate code for the PBB. */
if (isl_set_is_empty (pbb->domain))
continue;
domain = cloog_domain_from_isl_set (isl_set_copy (pbb->domain));
scattering = cloog_scattering_from_isl_map
(isl_map_copy (pbb->transformed));
union_domain = cloog_union_domain_add_domain (union_domain, "", domain,
scattering, pbb);
}
return union_domain;
}
</pre>
<div style="line-height: 0.4cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<div style="line-height: 0.4cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">Let's
pass the previously generated cloog_input
to to the CLooG code
generator</span></span></div>
<pre class="cpp" name="code" style="line-height: 0.4cm;">static struct clast_stmt *
scop_to_clast (scop_p scop)
{
CloogInput *cloog_input;
struct clast_stmt *clast;
CloogOptions *options = cloog_options_malloc (cloog_state);
options->language = CLOOG_LANGUAGE_C;
cloog_input = generate_cloog_input (scop);
clast = cloog_clast_create_from_input (cloog_input, options);
cloog_options_free (options);
return clast;
}
</pre>
<div style="line-height: 0.4cm;">
<br /></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<div style="line-height: 0.4cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">We
can produce the following dump now:</span></span></div>
<div style="line-height: 0.4cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><br /></span></span></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<span style="font-family: Times New Roman, serif;"><span style="line-height: 15.118110656738281px;">for (c2=0;c2<=M-2;c2++) {</span></span></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<span style="font-family: Times New Roman, serif;"><span style="line-height: 15.118110656738281px;"> for (c4=0;c4<=M-1;c4++) {</span></span></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<span style="font-family: Times New Roman, serif;"><span style="line-height: 15.118110656738281px;"> (c2,c4);</span></span></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<span style="font-family: Times New Roman, serif;"><span style="line-height: 15.118110656738281px;"> }</span></span></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<span style="font-family: Times New Roman, serif;"><span style="line-height: 15.118110656738281px;">}</span></span></div>
<div align="LEFT" style="margin-bottom: 0cm;">
<span style="font-family: Times New Roman, serif;"><span style="line-height: 15.118110656738281px;"><br /></span></span></div>
<div align="LEFT" style="font-style: normal; font-variant: normal; font-weight: normal; margin-bottom: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">In
CLooG An AST constructed by cloog_clast_create_from_input has the
type clast_stmt, which represents a linked list of </span></span>“<span style="font-family: Times New Roman, serif;">statements”,
which allows to traverse an AST tree. Let's do this</span></div>
<pre class="cpp" name="code" style="line-height: 0.4cm;">static void
translate_clast (CloogOptions *options, int indent,
FILE *file, struct clast_stmt *);
static void
translate_clast_for (CloogOptions *options, int indent,
FILE *file, struct clast_for *stmt)
{
fprintf (file, "%*s", indent, "");
fprintf(file, "for (");
if (stmt->LB)
{
fprintf(file, "%s=LB", stmt->iterator);
}
fprintf(file,";");
if (stmt->UB)
{
fprintf (file,"%s<=UB", stmt->iterator);
}
if (cloog_int_gt_si(stmt->stride, 1))
{
fprintf (file,";%s+=", stmt->iterator);
cloog_int_print (file, stmt->stride);
fprintf (file, ") \n");
}
else
fprintf(file, ";%s++) \n", stmt->iterator);
translate_clast (options, indent + 2, file, stmt->body);
}
static void
translate_clast_guard (CloogOptions *options, int indent,
FILE *file, struct clast_guard *stmt)
{
fprintf (file, "%*s", indent, "");
fprintf(file,"if ");
if (stmt->n > 1)
fprintf(file, "(");
int i;
for (i = 0; i < stmt->n; i++)
{
if (i > 0)
{
fprintf(file, " && ");
}
fprintf(file, "(eq)");
}
if (stmt->n > 1)
fprintf(file, ")");
translate_clast (options, indent + 2, file, stmt->then);
}
static void
translate_clast_user (int indent, FILE *file, struct clast_stmt *stmt)
{
fprintf (file, "%*s", indent, "");
print_clast_stmt (file, stmt);
}
static void
translate_clast_assignment (int indent, FILE *file, struct clast_stmt *stmt)
{
fprintf (file, "%*s", indent, "");
print_clast_stmt (file, stmt);
}
static void
translate_clast (CloogOptions *options, int indent,
FILE *file, struct clast_stmt *stmt)
{
if (!stmt)
return;
if (CLAST_STMT_IS_A (stmt, stmt_root))
; /* Do nothing. */
else if (CLAST_STMT_IS_A (stmt, stmt_user))
translate_clast_user (indent, file, stmt);
else if (CLAST_STMT_IS_A (stmt, stmt_for))
translate_clast_for (options, indent, file, (struct clast_for *) stmt);
else if (CLAST_STMT_IS_A (stmt, stmt_guard))
translate_clast_guard (options, indent, file, (struct clast_guard *) stmt);
else if (CLAST_STMT_IS_A (stmt, stmt_block))
translate_clast (options, indent, file, ((struct clast_block *) stmt)->body);
else if (CLAST_STMT_IS_A (stmt, stmt_ass))
translate_clast_assignment (indent, file, stmt);
else
gcc_unreachable ();
translate_clast (options, indent, file, stmt->next);
}
</pre>
<div align="LEFT" style="margin-bottom: 0cm;">
<div style="font-style: normal; font-variant: normal; font-weight: normal; margin-bottom: 0cm;">
<span style="font-family: inherit;">Finally we get the following
</span></div>
<div style="font-style: normal; font-variant: normal; font-weight: normal; margin-bottom: 0cm;">
<span style="font-family: inherit;"><br />
</span></div>
<div style="margin-bottom: 0cm;">
<span style="font-family: inherit;">for (c2=LB;c2<=UB;c2++) </span></div>
<div style="margin-bottom: 0cm;">
<span style="font-family: inherit;"> for (c4=LB;c4<=UB;c4++) </span></div>
<div style="margin-bottom: 0cm;">
<span style="font-family: inherit;"> (c2,c4);</span></div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
Anonymoushttp://www.blogger.com/profile/15362496381373801396noreply@blogger.com0tag:blogger.com,1999:blog-6331292181028306563.post-65098687190854877972014-05-25T04:05:00.002-07:002014-05-25T04:24:58.933-07:00#GSoC Report I<div dir="ltr" style="text-align: left;" trbidi="on">
<div align="LEFT" style="border: none; margin-bottom: 0cm; padding: 0cm;">
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">Hi
everyone!</span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm; text-indent: 1.03cm;">
<br /></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">As
I told you before, my first task is to get more familiar with ISL AST
generation. In this post, I'll describe a solution for it.</span></span></div>
<div style="font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm;">
<br /></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">First
of all, I added a new command line flag (fgraphite-isl-code-gen) to
GCC. That was implemented with addition of the following code to
gcc/common.opt:</span></span></div>
<pre class="cpp" name="code" style="font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm;">fgraphite-isl-code-gen
Common Report Var(flag_graphite_isl_code_gen) Optimization
Enable isl code generator in Graphite
</pre>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;">fgraphite-isl-code-gen
will be used to generate new code in parallel, when it's necessary.</span></span></span></div>
<pre class="cpp" name="code">if (flag_graphite_isl_code_gen)
{
//generation of new code
}
</pre>
</div>
<div align="LEFT" style="border: none; margin-bottom: 0cm; padding: 0cm;">
<div align="LEFT" style="border: none; margin-bottom: 0cm; padding: 0cm;">
<div style="font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">Let's
consider the following code: </span></span>
</div>
<pre class="cpp" name="code" style="font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm;">#include <stdio.h>
#define N 16
int
main1 (int n, int *a)
{
int i, j;
for (i = 0; i < n - 1; i++)
for (j = 0; j < n; j++)
a[j] = i + n;
for (j = 0; j < n; j++)
if (a[j] != i + n - 1)
__builtin_abort ();
return 0;
}
int
main ()
{
int a[N];
main1 (N, a);
return 0;
} </pre>
<div align="LEFT" style="border: none; margin-bottom: 0cm; padding: 0cm;">
<div align="LEFT" style="border: none; margin-bottom: 0cm; padding: 0cm;">
<div style="font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm;">
<span style="font-family: 'Times New Roman', serif; line-height: 0.4cm;">Graphite
outlines the following SCoP from it:</span><span style="color: black;"><span style="font-family: Times New Roman, serif;"> </span></span>
</div>
<div style="font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><br /></span></span>
</div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">Schedule
of the basic block: [n, P_37] -> { S_5[i0, i1] -> [0, i0, 0,
i1, 0] }</span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><br /></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
</div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">Domain
of the basic block: [n, P_37] -> { S_5[i0, i1] : exists (e0 = [(-2
+ n)/4294967296], e1 = [(-1 + n)/4294967296]: i0 >= 0 and
4294967296e0 <= -2 + n and 4294967296e0 >= -4294967297 + n and
4294967296e0 <= -2 + n - i0 and i0 <= 2147483645 and i1 >= 0
and 4294967296e1 <= -1 + n and 4294967296e1 >= -4294967296 + n
and 4294967296e1 <= -1 + n - i1 and i1 <= 2147483646 and n >=
1) }</span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><br /></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
</div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">After
addition of a new flag I set up generation of isl_union_map, which
specifies an order used to
visit elements in a domain. </span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: 13pt;"><br /></span></span></span></div>
<pre class="cpp" name="code" style="font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm;">static isl_union_map *
generate_isl_schedule (scop_p scop)
{
int i;
poly_bb_p pbb;
isl_union_map *schedule_isl =
isl_union_map_empty (isl_set_get_space (scop->context));
FOR_EACH_VEC_ELT (SCOP_BBS (scop), i, pbb)
{
/* Dead code elimination: when the domain of a PBB is empty,
don't generate code for the PBB. */
if (isl_set_is_empty (pbb->domain))
continue;
isl_map *bb_schedule = isl_map_copy (pbb->transformed);
bb_schedule = isl_map_intersect_domain (bb_schedule,
isl_set_copy (pbb->domain));
schedule_isl =
isl_union_map_union (schedule_isl,
isl_union_map_from_map (bb_schedule));
}
return schedule_isl;
}
</pre>
<div align="LEFT" style="border: none; margin-bottom: 0cm; padding: 0cm;">
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;">You
can see that this function returns the union of all maps constructed
by intersection of scattering functions' domains with corresponding
domains of all basic blocks in the given SCoP. </span></span></span>
</div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<br /></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;">In
our case we get the following isl_union_map:</span></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<br /></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;">[n,
P_37] -> { S_5[i0, i1] -> [0, i0, 0, i1, 0] : exists (e0 = [(-2
+ n)/4294967296], e1 = [(-1 + n)/4294967296]: i0 >= 0 and
4294967296e0 <= -2 + n and 4294967296e0 >= -4294967297 + n and
4294967296e0 <= -2 + n - i0 and i0 <= 2147483645 and i1 >= 0
and 4294967296e1 <= -1 + n and 4294967296e1 >= -4294967296 + n
and 4294967296e1 <= -1 + n - i1 and i1 <= 2147483646 and n >=
1) }</span></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;"><br /></span></span></span></div>
<div style="font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm;">
<br /></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">After
this I set up generation of isl_ast_build, which specifies the
constraints on the parameters.</span></span></div>
<pre class="cpp" name="code" style="font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm;">static isl_ast_build *
generate_isl_context (scop_p scop)
{
isl_set * context_isl = isl_set_params (isl_set_copy (scop->context));
return isl_ast_build_from_context (context_isl);
}
</pre>
<div align="LEFT" style="border: none; margin-bottom: 0cm; padding: 0cm;">
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;">Unfortunately,
I haven't found any opportunity to dump isl_ast_build in ISL. That's
why I'll provide a dump of universe set, which is used by
isl_ast_build_from_context to generate isl_ast_build and generated
from our SCoP.</span></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"> </span>
</div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;">[n,
P_37] -> { : n <= 2147483647 and n >= 2 and P_37 <=
2147483647 and P_37 >= -2147483648 }</span></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;"><br /></span></span></span></div>
<div style="font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm;">
<br /></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">After
this generation, I finally set up generation of a ISL AST.</span></span></div>
<pre class="cpp" name="code" style="font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm;">static isl_ast_node *
scop_to_isl_ast (scop_p scop)
{
isl_union_map *schedule_isl = generate_isl_schedule (scop);
isl_ast_build *context_isl = generate_isl_context (scop);
isl_ast_node *ast_isl = isl_ast_build_ast_from_schedule (context_isl,
schedule_isl);
isl_ast_build_free (context_isl);
return ast_isl;
}
</pre>
<div align="LEFT" style="border: none; margin-bottom: 0cm; padding: 0cm;">
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;">Let's
consider a dump of the ISL AST, which is generated in our case.</span></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<br /></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;">for
(int c1 = 0; c1 < n - 1; c1 += 1)
</span></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;"> for
(int c3 = 0; c3 < n; c3 += 1)
</span></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;"> S_5(c1,
c3);</span></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<br /></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;">Now
we can compare it with ClooG, which is also generated from our
SCoP.</span></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<br /></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;">for
(scat_1=0;scat_1<=n_7-2;scat_1++) {
</span></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;"> for
(scat_3=0;scat_3<=n_7-1;scat_3++) {
</span></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;"> (scat_1,scat_3);
</span></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;"> }
</span></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;">}</span></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<br /></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;"><span style="font-variant: normal;"><span style="font-style: normal;">You
could see that they are generally similar.</span></span></span></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<br /></div>
<div style="font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm;">
<br /></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;">After
this generation, I traversed the ISL AST with the following code:</span></span></div>
<pre class="cpp" name="code" style="font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm;">void
print_indent (int indent, isl_printer *prn)
{
int i;
for (i = 0; i < indent; i++)
{
prn = isl_printer_print_str (prn, " ");
}
}
static void
translate_isl_ast (int indent, __isl_keep isl_ast_node *node,
isl_printer *prn);
/* Translates a isl_ast_node_for STMT to gimple.
TODO: replace output to FILE with translation
to GCC representation. */
static void
translate_isl_ast_node_for (int indent, __isl_keep isl_ast_node *node_for,
isl_printer *prn)
{
isl_id *id;
const char *name;
const char *type;
type = isl_options_get_ast_iterator_type (isl_printer_get_ctx (prn));
isl_ast_expr *for_iterator = isl_ast_node_for_get_iterator (node_for);
isl_ast_expr_free (for_iterator);
id = isl_ast_expr_get_id (for_iterator);
name = isl_id_get_name (id);
isl_id_free (id);
prn = isl_printer_print_str (prn, "\n");
print_indent (indent, prn);
prn = isl_printer_print_str (prn, "for (");
prn = isl_printer_print_str (prn, type);
prn = isl_printer_print_str (prn, " ");
prn = isl_printer_print_str (prn, name);
prn = isl_printer_print_str (prn, " = ");
isl_ast_expr *for_init = isl_ast_node_for_get_init (node_for);
prn = isl_printer_print_ast_expr (prn, for_init);
isl_ast_expr_free (for_init);
prn = isl_printer_print_str (prn, "; ");
isl_ast_expr *for_cond = isl_ast_node_for_get_cond (node_for);
prn = isl_printer_print_ast_expr (prn, for_cond);
isl_ast_expr_free (for_cond);
prn = isl_printer_print_str (prn, "; ");
prn = isl_printer_print_str (prn, name);
prn = isl_printer_print_str (prn, " += ");
isl_ast_expr *for_inc = isl_ast_node_for_get_inc (node_for);
prn = isl_printer_print_ast_expr (prn, for_inc);
isl_ast_expr_free (for_inc);
prn = isl_printer_print_str (prn, ")");
isl_ast_node *for_body = isl_ast_node_for_get_body (node_for);
translate_isl_ast (indent + 2, for_body, prn);
isl_ast_node_free (for_body);
}
/* Translates a clast guard statement STMT to gimple.
TODO: replace output to FILE with translation
to GCC representation. */
static void
translate_isl_ast_node_if (int indent, __isl_keep isl_ast_node *node_if,
isl_printer *prn)
{
prn = isl_printer_print_str (prn, "\n");
print_indent (indent, prn);
prn = isl_printer_print_str (prn, "if (");
isl_ast_expr *if_cond = isl_ast_node_if_get_cond (node_if);
prn = isl_printer_print_ast_expr (prn, if_cond);
isl_ast_expr_free (if_cond);
prn = isl_printer_print_str (prn, ")");
isl_ast_node *if_then = isl_ast_node_if_get_then (node_if);
translate_isl_ast (indent + 2, if_then, prn);
isl_ast_node_free (if_then);
if (isl_ast_node_if_has_else (node_if))
{
prn = isl_printer_print_str (prn, "else");
isl_ast_node *if_else = isl_ast_node_if_get_else(node_if);
translate_isl_ast (indent + 2, if_else, prn);
isl_ast_node_free (if_else);
}
}
/* Translates a clast guard statement STMT to gimple.
TODO: replace output to FILE with translation
to GCC representation. */
static void
translate_isl_ast_node_user (int indent, __isl_keep isl_ast_node *node_user,
isl_printer *prn)
{
prn = isl_printer_print_str (prn, "\n");
prn = isl_printer_set_indent (prn, indent);
prn = isl_printer_print_ast_node (prn, node_user);
}
/* Translates a clast guard statement STMT to gimple.
TODO: replace output to FILE with translation
to GCC representation. */
static void
translate_isl_ast_node_block (int indent, __isl_keep isl_ast_node *node_block,
isl_printer *prn)
{
isl_ast_node_list *node_list = isl_ast_node_block_get_children (node_block);
int i;
for (i = 0; i < isl_ast_node_list_n_ast_node (node_list); i++)
{
translate_isl_ast (indent + 2,
isl_ast_node_list_get_ast_node (node_list, i), prn);
}
isl_ast_node_list_free (node_list);
}
/* Translates a ISL AST node NODE to GCC representation in the
context of a SESE.
TODO: replace output to FILE with translation
to GCC representation. */
static void
translate_isl_ast (int indent, __isl_keep isl_ast_node *node, isl_printer *prn)
{
switch (isl_ast_node_get_type (node))
{
case isl_ast_node_error:
gcc_unreachable ();
case isl_ast_node_for:
translate_isl_ast_node_for (indent, node, prn);
return;
case isl_ast_node_if:
translate_isl_ast_node_if (indent, node, prn);
return;
case isl_ast_node_user:
translate_isl_ast_node_user (indent, node, prn);
return;
case isl_ast_node_block:
translate_isl_ast_node_block (indent, node, prn);
return;
default:
gcc_unreachable ();
}
}
/* Prints NODE to FILE. */
void
print_isl_ast_node (FILE *file, __isl_keep isl_ast_node *node,
__isl_keep isl_ctx *ctx)
{
isl_printer *prn = isl_printer_to_file (ctx, file);
prn = isl_printer_set_output_format (prn, ISL_FORMAT_C);
prn = isl_printer_print_ast_node (prn, node);
isl_printer_free (prn);
}
</pre>
<div align="LEFT" style="border: none; margin-bottom: 0cm; padding: 0cm;">
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;"><span style="font-variant: normal;"><span style="font-style: normal;">You
could make sure, that traversing is correct by comparing it with </span></span><span style="font-variant: normal;"><span style="font-style: normal;">the</span></span><span style="font-variant: normal;"><span style="font-style: normal;">
dump of the ISL AST.</span></span></span></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<br /></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;"><span style="font-variant: normal;"><span style="font-style: normal;">for
(int c1 = 0; c1 < n - 1; c1 += 1)
</span></span></span></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-variant: normal;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;"><span style="font-style: normal;"> for
(int c3 = 0; c3 < n; c3 += 1)
</span></span></span></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black;"><span style="font-variant: normal;"><span style="font-family: Times New Roman, serif;"><span style="font-size: small;"><span style="font-style: normal;"> S_5(c1,
c3);
</span></span></span></span></span></div>
<div align="LEFT" style="border: none; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm; margin-bottom: 0cm; padding: 0cm;">
<br /></div>
<div style="font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm;">
<br /></div>
<div align="LEFT" style="border: none; margin-bottom: 0cm; padding: 0cm;">
<span style="color: black; font-style: normal; font-variant: normal; font-weight: normal; line-height: 0.4cm;"><span style="font-family: Times New Roman, serif;">You
can find all the mentioned changes in the following patch, wich can be found at the following link </span></span><span style="font-family: Times New Roman, serif;"><span style="line-height: 15.118110656738281px;">http://gcc.1065356.n5.nabble.com/attachment/1037729/0/patch</span></span></div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
</div>
Anonymoushttp://www.blogger.com/profile/15362496381373801396noreply@blogger.com0tag:blogger.com,1999:blog-6331292181028306563.post-49828388454237223242014-05-01T09:21:00.001-07:002014-05-01T09:29:57.170-07:00My GSOC 2014 Proposal: Integration of ISL code generator into Graphite<div dir="ltr" style="text-align: left;" trbidi="on">
<div style="text-align: left;">
<span style="background-color: white; font-family: Times, Times New Roman, serif;">Hi everyone! To start this blog I’m posting my accepted proposal on Google Summer of Code. From this day forward I will post the updates of the project after reaching my mile stones. Maybe It would be useful for everyone who wants to know about the code generation of Graphite through CLooG and the Integer Set Library.</span></div>
<div style="text-align: left;">
<span style="background-color: white; font-family: Times, Times New Roman, serif;"><br /></span></div>
<div style="text-align: left;">
<span style="background-color: white; font-family: Times, Times New Roman, serif;"><strong style="border: 0px; line-height: 19.200000762939453px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">Short description:</strong><span style="line-height: 19.200000762939453px;"> For a long period of time Graphite was relying on CLooG to produce GIMPLE code. The Integer Set Library (ISL) recently became available in this project to be used as a back end of CLooG. ISL is nowadays mature enough to replace CLooG with own code generation that sometimes is better. This project aims to integrate ISL code generation into Graphite and avoid necessity of CLooG in GCC.</span></span></div>
<div style="text-align: left;">
<span style="font-family: Times, Times New Roman, serif;"><span style="background-color: white; line-height: 19.200000762939453px;"><br /></span></span></div>
<div style="border: 0px; line-height: 1.6em; margin-bottom: 10px; outline: 0px; padding: 0px; text-align: left; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><strong style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">Student:</strong> Roman Gareev</span><br />
<span style="background-color: white;"><strong style="border: 0px; font-family: Times, 'Times New Roman', serif; line-height: 1.6em; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">Email Address:</strong><span style="font-family: Times, 'Times New Roman', serif; line-height: 1.6em;"> gareevroman at gmail dot com</span></span><br />
<span style="background-color: white;"><strong style="border: 0px; line-height: 19.5px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><span style="border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></strong>
<strong style="border: 0px; line-height: 19.5px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><span style="border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">1 Summary</span></strong></span><br />
<span style="background-color: white;"><span style="font-family: Times, 'Times New Roman', serif; line-height: 19.5px;"><br /></span>
<span style="font-family: Times, 'Times New Roman', serif; line-height: 19.5px;">ISL is nowadays mature enough to replace CLooG with own code generation that sometimes is better. Our project aims to integrate ISL code generation into Graphite and avoid necessity of CLooG in GCC.</span></span><br />
<span style="background-color: white;"><strong style="border: 0px; line-height: 19.5px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><span style="border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></strong>
<strong style="border: 0px; line-height: 19.5px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><span style="border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">2 The project</span></strong></span><br />
<span style="background-color: white;"><span style="font-family: Times, 'Times New Roman', serif; line-height: 19.5px;"><br /></span>
<span style="font-family: Times, 'Times New Roman', serif; line-height: 19.5px;">For a long period of time Graphite was relying on CLooG [1] to produce GIMPLE code. The Integer Set Library (ISL) [2] recently became available in this project to be used as a back end of CLooG. ISL is nowadays mature enough to replace CLooG with own code generation that sometimes is better. Our proposal aims to integrate ISL code generation into Graphite and avoid necessity of CLooG in GCC.</span></span><br />
<span style="background-color: white;"><span style="font-family: Times, 'Times New Roman', serif; line-height: 19.5px;"><br /></span>
<span style="font-family: Times, 'Times New Roman', serif; line-height: 19.5px;">Graphite uses the polyhedral model as a basic model for loop optimization and parallelization. Subsequently, it uses CLooG to perform code generation for loops represented in the polyhedral model. Graphite is now able to use ISL back end of CLooG for generating code out of polyhedral program representation.</span></span><br />
<span style="background-color: white;"><span style="font-family: Times, 'Times New Roman', serif; line-height: 19.5px;"><br /></span>
<span style="font-family: Times, 'Times New Roman', serif; line-height: 19.5px;">The goal of our project is to totally replace CLooG with ISL to perform code generation. ISL will generate ISL AST, which is a simple abstract-syntax tree containing only loops, conditions, and statements. GIMPLE code corresponding to transformed polyhedral model will be then regenerated from this representation.</span></span></div>
<div style="border: 0px; line-height: 19.5px; margin: 0px; outline: 0px; padding: 0px; text-align: left; vertical-align: baseline;">
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<div style="text-align: left;">
<strong style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></strong></div>
<div style="text-align: left;">
<strong style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">3 Benefits for Graphite</span></strong></div>
<div style="text-align: left;">
<strong style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></strong></div>
</div>
</div>
<div style="border: 0px; line-height: 19.5px; margin: 0px; outline: 0px; padding: 0px; text-align: left; vertical-align: baseline;">
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">• This project could help to eliminate CLooG library installation dependency from GCC,</span><br />
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">• ISL code generator has already shown compile-time performance improvements [3] in Polly project [4]. There is a possibility of the performance improvement in Graphite,</span><br />
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">• ISL code generator supports unrolling, full/partial tile separation, fine-grained code size adjustments. It allows to improve quality of generated code.</span><br />
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
</div>
<div style="border: 0px; line-height: 19.5px; margin: 0px; outline: 0px; padding: 0px; text-align: left; vertical-align: baseline;">
<strong style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">4 Details about the project</span></strong><br />
<strong style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></strong></div>
<div style="border: 0px; line-height: 19.5px; margin: 0px; outline: 0px; padding: 0px; text-align: left; vertical-align: baseline;">
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">In source-to-source polyhedral compilers, the code generation pass is the last one, generating the new loop structures to scan statement instances in the order defined by the modified schedule. CLooG is used in graphite as the major component of code generation.</span><br />
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">In Graphite it is not the syntactical source code that is the final result of the pass: graphite should be able to regenerate the GIMPLE code. Furthermore, the generated GIMPLE code has to be reinserted back into the CFG, respecting the SSA form invariants and passed to the further passes after Graphite.</span><br />
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">Graphite uses CLooG as the major component of this code generation. CLooG generates an internal representation called CLAST which is a simple abstract-syntax tree containing only loops, conditions, and statements. In our case statements are replaced with basic blocks.</span><br />
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">CLooG is fed by the polyhedral representation (GPOLY) and is asked to generate a CLAST through GLooG (GIMPLE Loop Generator) “scop_to_clast()”. The nodes of the abstract-syntax tree are pointers to original basic blocks. Depending on the loop transformations, the basic blocks might be rescheduled, moved to other loops, or even replicated (when performing a transformation). The final effect is represented in the CLAST. The CLAST tree is traversed through GLooG “translate_clast()” and the basic blocks are put into the their new positions in the GIMPLE CFG, loop structures are regenerated and some basic blocks are replicated.</span><br />
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">Even in the case of the identity transformation (no schedule modification), the newly generated loops according to the CLAST tree have the new induction variables. All the basic blocks belonging to a SCoP have to be scanned, and the old induction variables have to be replaced with new induction variables.</span><br />
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">ISL will generate ISL AST, which is a simple abstract-syntax tree containing only loops, conditions, and statements. Its statements also will be pointers to original basic blocks. After this it will be traversed and transformed into the GIMPLE CFG.</span><br />
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
</div>
<div style="border: 0px; line-height: 19.5px; margin: 0px; outline: 0px; padding: 0px; text-align: left; vertical-align: baseline;">
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">An API introduced by ISL for code generation is generally similar to the API introduced by CLooG, but has differences. In this section, we present a list of some differences between them:</span><br />
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">• An AST generation:</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
</div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">In CLooG an AST can be constructed using “cloog_clast_create_from_input()”. “cloog_clast_create_from_input()” must be called with two arguments. The first of them influences on constructed AST and has type of pointer to CloogInput. A CloogInput structure represents the input to CLooG. It is essentially a CloogUnionDomain along with a context CloogDomain. CloogDomain is an type representing a polyhedral domain (a union of polyhedra).</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
</div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">Graphite uses “cloog_clast_create_from_input()” to generate CLAST representation and “generate_cloog_input()” to create its first argument mentioned previously. “generate_cloog_input()” transforms type of scop's context to type, which is appropriate for CloogInput. “build_cloog_union_domain” is used for generation of CloogUnionDomain, which contains all CloogUnion corresponding to all basic blocks in the given scop.</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">In ISL an AST can be constructed using “isl_ast_build_ast_from_schedule”. “isl_ast_build_ast_from_schedule” also must be called with two arguments. The first of them must have isl_ast_build type, which specifies the context and can be created using isl_ast_build_from_context. The second argument of “isl_ast_build_ast_from_schedule” must have isl_union_map type. In particular, given a isl_union_map, an AST is generated that visits all the elements in the domain of the isl_union_map according to the lexicographic order of the corresponding image element(s).</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">In our case the second argument can be the union of all maps constructed by intersection of scattering functions' domains with corresponding domains of all basic blocks in the given scop.</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">• The AST format:</span></div>
</div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
</div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">In CLooG An AST constructed by cloog_clast_create_from_input has the type clast_stmt, which represents a linked list of “statements”, which allows to traverse an AST tree.</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
</div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">The following statement types are defined by CLooG: clast_root, clast_assignment, clast_block, clast_user_stmt, clast_for, clast_guard.</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
</div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">The clast_stmt returned by cloog_clast_create is a clast_root. It contains a placeholder for all the variable names that appear in the AST and a (list of) nested statement(s).</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">A clast_assignment assigns the value given by the clast_expr RHS to a variable named LHS. </span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
</div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">A clast_block groups a list of statements into one statement. </span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
</div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">A clast_user_stmt represents a call to a statement specified by the user. </span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
</div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">A clast_for represents a for loop. </span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">A clast_guard represents the guarded execution of the then (list of) statement(s).</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">ISL has similar representation of an AST and own mechanism to traverse it.</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
</div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
</div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
</div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">In ISL the type of an AST node is one of isl_ast_node_for, isl_ast_node_if, isl_ast_node_block or isl_ast_node_user.</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">An isl_ast_node_for represents a for node. </span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
</div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">An isl_ast_node_if represents an if node. </span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
</div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">An isl_ast_node_block represents a compound node. </span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
</div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">An isl_ast_node_user represents an expression statement. An expression statement typically corresponds to a domain element, i.e., one of the elements that is visited by the AST.</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
</div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 60px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">ISL uses the following functions to get child nodes of AST tree: “isl_ast_node_for_get_body()”, “isl_ast_node_if_get_then()”, “isl_ast_node_if_get_else()”, “isl_ast_node_block_get_children()”.</span><br />
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; font-family: Times, Times New Roman, serif;">• <strong style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">Timeline</strong>: </span><br />
<span style="background-color: white; font-family: Times, Times New Roman, serif;"><br /></span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">◦ 19 May – 25 May: Get more familiar with ISL AST generation: generate an isl_ast_build and an isl_union_map, pass them to the ISL code generator, traverse the resulting AST and dump it to a file.</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">◦ 26 May – 31 May: Get more familiar with CLooG generation: generate a CloogInput, pass it to the CLooG code generator, traverse the resulting AST and dump it to a file.</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"> ◦ 1 June – 15 June: Vacation (I have some university exams).</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">◦ 16 June – 22 June: Add ISL AST generation to Graphite and dumps generated ISL AST to a file.</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">◦ 23 June – 29 June: Testing and fixing bugs.</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">◦ 30 June – 6 July: Begin generation of Gimple from ISL AST: remove CLAST generation, generate loops without any basic blocks, extend to generation of loops with a single basic block.</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">◦ 7 July – 13 July: Testing and fixing bugs.</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">◦ 14 July – 20 July: Extension to generation of loops with nested loops and if expressions.</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">◦ 21 July – 27 July: Testing and fixing bugs.</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">◦ 28 July – 3 August: Adding new tests, removing CLooG library installation dependency from GCC.</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">◦ 4 August – 17 August: Testing and fixing bugs, writing documentation.</span><br />
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
</div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<strong style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; font-size: small; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">5 Required deliverables</span></strong><br />
<strong style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; font-size: small; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></strong></div>
</div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">• Graphite must become fully independent of CLooG library,</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">• GCC should be able to bootstrap,</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">• Pass regression tests,</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">• Add new tests to testsuite.</span><br />
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
</div>
</div>
</div>
</div>
</div>
<div style="border: 0px; line-height: 19.5px; margin: 0px; outline: 0px; padding: 0px; text-align: left; vertical-align: baseline;">
<span style="border: 0px; font-family: Times, Times New Roman, serif; font-size: small; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><strong style="background-color: white; border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">6 Nice to have</strong></span><br />
<span style="border: 0px; font-family: Times, Times New Roman, serif; font-size: small; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><strong style="background-color: white; border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></strong></span></div>
<div style="border: 0px; line-height: 19.5px; margin: 0px; outline: 0px; padding: 0px; text-align: left; vertical-align: baseline;">
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">According to advancement in work on the integration and results, we want to :</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">• Make execution-time and compile-time performance comparisons between CLooG and ISL code generation in Graphite.</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">• Use the full/partial tile separation for the tiles generated by the isl scheduler.</span><br />
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
</div>
<div style="border: 0px; line-height: 19.5px; margin: 0px; outline: 0px; padding: 0px; text-align: left; vertical-align: baseline;">
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="border: 0px; font-family: Times, Times New Roman, serif; font-size: small; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><strong style="background-color: white; border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">Experience</strong></span><br />
<span style="border: 0px; font-family: Times, Times New Roman, serif; font-size: small; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><strong style="background-color: white; border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></strong></span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">• Experience in fixing PR59586 of Graphite project [10], [7], [8], [9].</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">• Experience in replacement of GCC code. I switched the resolution strategy of a hash table used in the symbol table of identifiers from open addressing to separate chaining with linked list [5], [6].</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px 0px 0px 30px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">• Academic experience in writing compilers using ANTLR [11], Flex [12], Bison [13].</span><br />
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></div>
</div>
<div style="border: 0px; line-height: 19.5px; margin: 0px; outline: 0px; padding: 0px; text-align: left; vertical-align: baseline;">
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<strong style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; font-size: small; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">Ref:</span></strong><br />
<strong style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; font-size: small; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;"><br /></span></strong></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">[1] http://www.cloog.org/</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">[2] http://isl.gforge.inria.fr/</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">[3] http://www.marshut.com/whwvq/performance-comparison-between-cloog-and-isl-code-generation.html</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">[4] http://polly.llvm.org/index.html</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">[5] http://gcc.gnu.org/ml/gcc-patches/2013-10/msg01653.html</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">[6] http://gcc.gnu.org/ml/gcc-patches/2013-11/msg00265.html</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">[7] http://gcc.gnu.org/ml/gcc-patches/2014-03/msg00475.html</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">[8] http://gcc.gnu.org/ml/gcc-patches/2014-03/msg00462.html</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">[9] http://gcc.gnu.org/ml/gcc-patches/2014-03/msg00463.html</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">[10] http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59586</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">[11] http://www.antlr.org/</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">[12] http://flex.sourceforge.net/</span></div>
<div style="border: 0px; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">
<span style="background-color: white; border: 0px; font-family: Times, Times New Roman, serif; margin: 0px; outline: 0px; padding: 0px; vertical-align: baseline;">[13] http://www.gnu.org/software/bison/</span></div>
</div>
</div>
Anonymoushttp://www.blogger.com/profile/15362496381373801396noreply@blogger.com0