支援LLVM編譯器架構之基於通用圖型處理器別名分析之研究

A GPGPU-based Alias Analysis for LLVM Compiler Infrastructure

許展富(Chan-Fu Hsu)

指導教授 ： 陳鵬升

國立中正大學/工學院/資訊工程學系/碩士(2013年)

摘要

別名分析 (Alias analysis) 在編譯器上，是用來決定兩次記憶體存取是否參考到相同的記憶體位置的一個方法，大部分的別名分析過程都採用循序執行 (Sequential execution) 程式架構。然而別名分析本身是一個NP問題 (NP-hard problem)，在近年來軟體開發越來越龐大導致分析不易，在分析的過程中往往需要在有限制的記憶體內尋求時間與精度的平衡點。

在追求分析時間縮短的方式，不外乎硬體的演進、演算法的改良。隨著摩爾定律 (Moore's law) 硬體演進逐漸達到新的狀態，硬體開始改變成多核心 (multi-core)，開始改變許多的議題延伸至用多核心執行平行化運算方式來改進分析的速度。

而近年來開始將議題延伸至通用圖形處理器 (General-purpose computing on graphics processing units, GPGPU)，開始有利用GPU用來計算的程式語言，在本文中我們將在 LLVM (Low Level Virtual Machine) 編譯器上以 GPU 的計算程式語言 OpenCL(Open Computing Language )實作別名分析，進一步來提升計算效能。

並列摘要

On the compiler alias analysis, is used to determine whether two memory accesses refer to the same memory location of a method. Most of the alias analysis processes are performed using sequential program architecture. However alias analysis itself is an NP-hard problem. Software development increasingly large cause analysis is not easy in recent years. On the analysis of the process often requires limited memory seek time and precision balance.

In the pursuit of ways to shorten the analysis time, the hardware or algorithm improvements evolution. With the gradual evolution of Moore's law hardware to reach a new state. Hardware began to change into multi-core and the issues extend to perform parallel implementation of multi-core to improve the speed of analysis.

In recent years extends to GPGPU (General-purpose computing on graphics processing units), began to take advantage of GPU programming language to calculation. In this paper we will LLVM (Low Level Virtual Machine) compiler by GPU computing programming language OpenCL (Open Computing Language) implementations alias analysis and further to improve computing performance.

並列關鍵字

Inclusion-based Points-to Analysis ； Open Computing Language (OpenCL) ； Low Level Virtual Machine(LLVM) ； GPGPU ； Data Compression

參考文獻

[1] Jungwon Kim, Honggyu Kim, Joo Hwan Lee, and Jaejin Lee. Achieving a single

[4] Dzintars Avots, Michael Dalton, V Benjamin Livshits, and Monica S Lam. Im-

[18] Lars Ole Andersen. Program analysis and specialization for the C programming

compute device image in opencl for multiple gpus. In Proceedings of the 16th

288. ACM, 2011.