Study On The Memory Access Pattern Analysis And Application Of Loop

With the advancement in hardware technology, the processor chip integrates more and more transistors, resulting in a growing speed gap between the processor and memory. In modern mainstream architectures, hierarchical cache architectures are utilized to moderate the access speed gap between them. Efficient usage of the cache has become one of the key factors affecting system performance. In addition to design considerations of hardware, the common practice now is that converting codes in the level of intermediate code with the powerful analysis and optimization capabilities of compiler, making the program instructions and data locality as high as possible, which can help to reduce the number of cache miss and improve overall system performance. Program transformation techniques based on compiler to optimize program locality can be divided into software pre-fetching, code conversion and data transformation.Based on the above research ideas, in this paper we are dedicated to developing a cache optimization prototype system on the LLVM (Low Level Virtual Machine) compiler, utilizing powerful analysis and optimization capabilities of LLVM to achieve a LLVM-based cache optimization platform. In this paper, we have done the following works:1. We design and implement a prototype system based on LLVM for cache optimization by data transformation techniques (APCache), involving the complete process of code analysis and code optimization. The system analyzes access patterns of loops in the intermediate code as LLVM pass and updates the intermediate code based on the new access patterns optimized from analysis results.2. We investigate the required technologies of implementing classical algorithms on LLVM on the focus of the array layout optimization in loops. The method of array in loops is often used in memory intensive programs. In this paper we implement the classical algorithm proposed by Leung to improve locality by relocating arrays in loops.3. We propose a lightweight function pointer analysis algorithm (FP) to provide accurate call graph support for inter-procedural cache optimization. It ensures the analysis accuracy by the strongly connected component (SCC) flow-sensitive and context-sensitive technology and increases the analysis speed by narrowing the scope of the analysis object. The cross-file function call graph based on analysis results of FP algorithm provides some technical support for inter-procedural cache optimization.