Research On LLVM Inter-iteration Data Reuse Optimization

With the development of programming languages and computer architectures,optimization for new language features and new architectures is becoming the heart of modern compiler design. Since "Memory Wall" problem,time spent on array access in loops accounted for the proportion of total execution time is usually large. Therefore optimization on array access in loops has been one of the key problems for improving compilers'performance.LLVM is a popular optimizing compiler framework currently. More and more researches on compiling optimization turn to this framework for its good performance on code optimization. When dealing with array access in loops, traditional induction variable optimization is used in LLVM, which results in the complication of array reference. To solve this problem, an inter-iteration data reuse optimization algorithm is proposed in this thesis,which makes up for the deficiencies of LLVM in array access.The inter-iteration data reuse optimization algorithm is used to simplify the calculation of array reference in loops based on LLVM loop canonicalization and optimization. This algorithm combines induction variable optimization and scalar replacement of array reference.At each iteration, array reference is substituted with scalar, which converts address variables to recognizable induction variables, and makes register allocation effective for array reference.Then strength reduction is implemented on induction variables by setting stride for different architecture,which converts address calculations to simple scalar ones. At last,the result is stored in a register for the next iteration,so that data can be reused between iterations. This algorithm can effectively reduce the complexity of address computation in loops, and improve the whole program's performance, coupled with the advantage of LLVM itself.The experiment results show that both assembly code and execution time are better when adding the inter-iteration data reuse optimization presented in the thesis, compared with the result generated by GCC or LLVM without this optimization.