靜態單賦值形式支援機率化指標分析

Support of Probabilistic Pointer Analysis in the SSA Form

洪明郁(Ming-Yu Hung)

指導教授 ： 李政崑

國立清華大學/電機資訊學院/資訊工程學系/博士(2012年)

https://doi.org/10.6843/NTHU.2012.00025

摘要

機率化指標分析是一種編譯器時期的分析方法，它可以估計在程式中某
一個位置的指標指向關係機率。這種分析的結果可以用於需要量化資訊的
最佳化和平行化的編譯器。本論文提出一種使用靜態單賦值形式完成的機
率化指標分析。
當計算某一個指標的指向機率時，必須先建立指標相依圖形，指標相依
圖形可以表示出此指標的所有可能指向關係，之後經過一連串的圖形簡化
程序，指標相依圖形會被轉成精簡的指標相依圖形，而這個精簡的相依圖
形，正是機率化指標分析的結果。除此之外，透過加入考慮函數相關的敘
述，機率化指標分析更進一步的被擴充為跨程序的分析。
我們基於提出的理論在開放研究編譯器( Open64 ) 上實作兩種版本，
包含靜態與剖面資訊賦予。靜態資訊賦予的版本是靜態給定程式分歧機率
各半；離開迴圈的機率是一成。相對的，剖面資訊賦予的版本是使用開放
研究編譯器的剖面工具，取得程式實際執行的分歧機率。
實驗結果顯示剖面資訊賦予的版本平均誤差為3.80%，而靜態資訊賦予
的版本是9.13%。最後使用SPEC CPU2006 基準程式，測出機率化指標分
析的可擴展性。
更進一步的，我們將機率化指標分析的結果，用於引導編譯器去進行更
積極的最佳化：臆測執行最佳化。臆測執行最佳化的缺點就是，當執行臆
測錯誤時，就會有額外的恢復重新執行的效能損失。因為機率化指標分析
的資訊可以引導編譯器該不該執行這個最佳化，讓程式可以具有臆測執行
最佳化帶來的平行效果，而不用承擔臆測太多錯誤帶來的效能衰減。

關鍵詞：編譯器、指標分析、控制流程圖、靜態單賦值形式。

關鍵字

編譯器 ； 指標分析 ； 機率化 ； 靜態單賦值形式

並列摘要

Probabilistic pointer analysis (PPA) is a compile-time analysis method
that estimates the probability that a points-to relationship will hold at a particular
program point. The results are useful for optimizing and parallelizing
compilers, which need to quantitatively assess the profitability of transformations
when performing aggressive optimizations and parallelization. This dissertation
presents a PPA technique using the static single assignment (SSA)
form. When computing the probabilistic points-to relationships of a specific
pointer, a pointer relation graph (PRG) is first built to represent all of the
possible points-to relationships of the pointer. The PRG is transformed by
a sequence of reduction operations into a compact graph, from which the
probabilistic points-to relationships of the pointer can be determined. In
addition, PPA is further extended to interprocedural cases by considering
function related statements. We have implemented our proposed scheme including
static and profiling versions in the Open64 compiler, and performed
experiments to obtain the accuracy and scalability. The static version estimates
branch probabilities by assuming that every conditional is equally
likely to be true or false, and that every loop executes ten times before terminating.
The profiling version measures branch probabilities dynamically
from past program executions using a default workload provided with the
benchmark. The average errors for selected benchmarks were 3.80% in the
profiling version and 9.13% in the static version. Finally, SPEC CPU2006
is used to evaluate the scalability, and the result indicates that our scheme
is sufficiently efficient in practical use. The average analysis time was 35.59
seconds for an average of 98696 lines of code.
In addition to evaluating the correctness and scalability of PPA, a PPAguided
speculation optimization is proposed. Originally, speculation execution
may cause performance decrease, because of many mis-speculations.
With the aid of PPA, a proposed cost model can guide compiler to do the
speculation execution or not. Thus, the compiler can always get the better
performance by executing parallely and avoiding mis-speculations.

Keywords:
compiler, pointer analysis, static single assignment (SSA) form

並列關鍵字

compiler ； pointer analysis ； probabilistic ； SSA form

參考文獻

Symposium on Principles of Programming Languages. New

[2] B. Steensgaard, “Points-to analysis in almost linear time,” in POPL

Principles of Programming Languages. New York, NY, USA: ACM,

[4] A. Deutsch, “Interprocedural may-alias analysis for pointers: beyond

on Programming Language Design and Implementation. New