|
CSC766: Project - Fall 2010
Vivek Deshpande Kishor Kharbas
Auto-vectorizating compiler for pseudo language
Problem Description
Many modern CPUs have SIMD instruction extensions like Intel’s MMX, SSE and ARM’s NEON. This means that the CPU can perform same computation on an array of data values in a single instruction cycle. Programs can leverage this capability by using vector instructions in their programs to gain better performance.
The pseudo language used for the course assignments does not have the facility for the user to specify vector operations. We would like to propose developing a compiler for the pseudo language with auto vectorization capability. This essentially means that the developed compiler analyses the code to find opportunities to perform vector computations without the programmer having to deal with it.
Techniques to be used
LLVM is a compiler infrastructure project [1] which is a collection of modular and reusable compiler modules. The intermediate representation(IR) used by LLVM compiler provides support for vector data types and vector instructions. There are back-ends available for all major architectures like ARM, Intel which transform such instructions in IR of the underlying SIMD instruction set.
We have 2 choices for implementation the project, each having its own merits. After evaluating the strengths and complexity of each, we will go ahead with one approach:
Write a front-end for the pseudo language which will perform loop analysis to identify vectorization and generate LLVM IR as output. The later stages of LLVM IR will perform rest of the optimizations and the target back-end will take care of converting LLVM IR vector instructions to the native vector instructions.
Write a front-end which will generate LLVM IR, then we will modify LLVM middle end to perform vectorization at LLVM IR level.
High level plan of implementation of vectorization:
Following are the projected steps involved in the implementation:
1. Identification of loops and nesting levels of loops.
2. Identification of loop index bounds and increment/decrement steps.
3. Analysis of loop statements to find whether they are amenable to vectorization.
4. Analysis of statement access patterns and finding dependencies that exist between them.
5. Finding statements which can be vectorized and converting them into corresponding vector instructions.
Task division:
One person will write the front-end for LLVM IR generation, which is relatively simpler than other tasks.
In the remaining work following things will be done by both members:
· Studying LLVM IR
· Studying vectorization and other related techniques
Independent set the tasks are as follows, which will be divided among the two members:
· Dependency analysis
· Analyzing loops using dependency information and use vector instructions when possible.
|
 |
|
