程式分析與優化 - 7 靜態單賦值(SSA)

来源:https://www.cnblogs.com/zhouronghua/archive/2022/06/19/16390138.html
-Advertisement-
Play Games

本章是系列文章的第七章,終於來到了鼎鼎大名的SSA,SSA是編譯器領域最偉大的發明之一,也是影響最廣的發明。 本文中的所有內容來自學習DCC888的學習筆記或者自己理解的整理,如需轉載請註明出處。周榮華@燧原科技 7.1 控制流圖回顧 對下麵的c代碼保存成7.1.cc: 1 int max(int ...


本章是系列文章的第七章,終於來到了鼎鼎大名的SSA,SSA是編譯器領域最偉大的發明之一,也是影響最廣的發明。

本文中的所有內容來自學習DCC888的學習筆記或者自己理解的整理,如需轉載請註明出處。周榮華@燧原科技

7.1 控制流圖回顧

對下麵的c代碼保存成7.1.cc:

1 int max(int a, int b) {
2   int ans = a;
3   if (b > a) {
4     ans = b;
5   }
6   return ans;
7 }

 

 

直接用clang生成bc → dot → svg,最終svg的結果如下:

 

 

如果經過一輪opt的優化“opt -mem2reg 7.1.ll -o 7.1.1.bc”之後的結果,就變成了這樣(註意,需要刪除ll裡面的optnone屬性,否則opt不會生效):

 

 除了我們本來準備跑的mem2reg的pass外,優化前後最後一個BB里是不是還多了一個phi函數?

 

7.1.1 靜態單賦值範式(SSA Form)

靜態單賦值,字面意思是對靜態的變數只有一次賦值點。這是現在所有編譯器都廣泛使用的屬性,也是編譯器歷史上最具有突破性意義的屬性,簡化了各種分析和優化的過程。

1991年SSA的奠基論文被引用打到2800+次,這還是截止2019年的數據,這個引用次數每年還在增加。

幾乎每本講編譯器的書都會說到SSA。google學術上用SSA能搜到5000+個結果。

每年來自全世界的編譯器專家,都會在SSA研討會上慶祝一次SSA的誕生。

和靜態單賦值對應的是動態單賦值,也就是程式執行過程中,每個變數只能賦值一次。和動態單賦值不同,靜態單賦值,只要求每個變數的賦值程式點只能有一個,這個程式點可以出現在迴圈內部(這意味著動態執行過程中這個程式點會多次執行)。

7.2 從SSA來到SSA去

7.2.1 將線性代碼轉換成SSA Form

如果一個程式沒有任何分叉,則稱這個程式是線性代碼。

例如下麵的代碼:

1 double baskhara(double a, double b, double c) {
2   double delta = b * b - 4 * a * c;
3   double sqrDelta = sqrt(delta);
4   double root = (b + sqrDelta) / 2 * a;
5   return root;
6 }

 

 

其實它本身就是符合SSA定義的(每個變數只定義一次),但一般經過opt轉換之後的代碼是這樣:

 1 define double @baskhara(double %a, double %b, double %c) {
 2   %1 = fmul double %b, %b
 3   %2 = fmul double 4.000000e+00, %a
 4   %3 = fmul double %2, %c
 5   %4 = fsub double %1, %3
 6   %5 = call double @sqrt(double %4)
 7   %6 = fadd double %b, %5
 8   %7 = fdiv double %6, 2.000000e+00
 9   %8 = fmul double %7, %a
10   ret double %8
11 }

 

 

線性代碼轉換成SSA範式的的演算法比較直接:

 1 for each variable a:
 2     Count[a] = 0
 3     Stack[a] = [0]
 4 rename_basic_block(B) =
 5     for each instruction S in block B:
 6         for each use of a variable x in S:
 7             i = top(Stack[x])
 8             replace the use of x with xi
 9         for each variable a that S defines
10             count[a] = Count[a] + 1
11             i = Count[a]
12             push i onto Stack[a]
13             replace definition of a with ai

 

 

例如,下麵的c代碼:

1 a = x + y;
2 b = a - 1;
3 a = y + b;
4 b = 4 * x;
5 a = a + b;

 

 

經過SSA轉換之後會變成這樣:

1 a1 = x0 + y0;
2 b1 = a1 - 1;
3 a2 = y0 + b1;
4 b2 = 4 * x0;
5 a3 = a2 + b2;

 

 

7.2.2 Phi函數

前面說了線性代碼的SSA轉換過程,那非線性代碼應該怎麼處理呢?

例如下麵的控制流圖,SSA轉換之後L5處使用的b是哪一個b?:

 

 

答案是要看情況,如果控制流圖上從L4執行到L5,則L5處的b應該是b1;如果是從L2執行到L5,則L5處的b應該是b0。

為了處理這種情況,需要引入phi函數(φ),φ函數會根據路徑做選擇,根據進入φ函數的路徑選擇不同的定義。

插入φ函數之後的SSA轉換結果如下:

 

 

φ函數會插入到每個基本塊的最開始地方,對N個變數生成N個φ函數,φ函數的參數個數取決於執行到該基本塊的直接前驅有幾個。

 

 

7.2.3 臨界邊

如果一條邊的起始點BB有多個直接後繼BB,終止點的BB有多個前驅BB,則稱為該邊為臨界邊。

7.2.4 臨界邊分裂

在臨界邊上插入一個空的BB(這個BB只有一個簡單的goto語句),來解決臨界邊的上的φ函數自動註入問題。

7.2.5 φ函數的插入策略

  • 存在一個基本塊x包含b的定義
  • 存在一個非x的基本塊y包含b的定義
  • 存在至少一條路徑Pxz從x到z
  • 存在至少一條路徑Pyz從y到z
  • Pyz和Pxz除了z節點外,沒有其他公共節點
  • z不會同時出現在Pxz和Pyz路徑中間,但可以出現在其中一條路徑的中間

7.2.6 SSA範式的支配屬性

在一個有根的有向圖中,d支配n的意思是所有從根節點到n的路徑都通過d。

在嚴格SSA範式(嚴格的意思是所有變數都是在使用前初始化)程式中,每個變數的定義都支配它的使用:

在基本塊n中,如果x是φ函數的第i個參數,則x的定義支配n的第3個前驅。

在一個使用x的不存在φ函數的基本塊n中,x的定義支配基本塊n。

7.2.7 支配前沿(The Dominance Frontier)

一個節點x嚴格支配節點w,當且僅當x支配w,並且x≠w。

節點x的支配前沿是所有具有下麵屬性的節點w的集合:x支配w的前驅,但不嚴格支配w。

支配前沿策略:如果節點x函數變數a的定義,那麼x的支配前沿中的任意節點z都需要一個a的φ函數。

支配前沿迭代:因為φ函數本身會產生一個定義,所以需要迴圈執行支配前沿策略,直到沒有節點需要額外增加φ函數。

定理:迭代支配前沿策略和迭代路徑覆蓋策略生成同樣的φ函數集合。

7.2.8 支配前沿的計算

 

DF[n] = DFlocal[n] ∪ { DFup[c] | c ∈ children[n] }
Where:
DFlocal[n]: 不被n嚴格支配(SSA的1989年版本要求的是嚴格支配,但1991年版本優化成直接支配,前一篇在ACM會議上,後一篇在ACM期刊上,Cytron果然是混職級的高手(smile))的n的後繼節點
DFup[c]: c的支配前沿集合中被n嚴格支配的節點
children[n]: 支配樹中n的子結點集合

轉換成演算法之後的偽代碼如下:

 1 computeDF[n]:
 2 S = {}
 3 for each node y in succ[n]
 4     if idom(y) ≠ n
 5         S = S ∪ {y}
 6 for each child c of n in the dom-tree
 7     computeDF[c]
 8     for each w ∈ DF[c]
 9         if n does not dom w, or n = w
10             S = S ∪ {w}
11 DF[n] = S

 

7.2.9 插入φ函數

插入的演算法描述如下:

 1 place-phi-functions:
 2   for each node n:
 3     for each variable a ∈ Aorig[n]:
 4       defsites[a] = defsites[a] ∪ [n]
 5   for each variable a:
 6     W = defsites[a]
 7     while W ≠ empty list
 8       remove some node n from W
 9       for each y in DF[n]:
10       if a ∉ Aphi[y]
11         insert-phi(y, a)
12         Aphi[y] = Aphi[y] ∪ {a}
13         if a ∉ Aorig[y]
14         W = W ∪ {y}
15  
16 insert-phi(y, a):
17   insert the statement a = ϕ(a, a, …, a)
18   at the top of block y, where the
19   phi-function has as many arguments
20   as y has predecessors
21 Where: 
22 Aorig[n]:  the  set  of  variables  defined  at  node  "n" 
23 Aphi[y]:  the  set  of  variables  that  have  phi-functions  at  node  "y"

 

7.2.10 變數重命名

 1 rename(n):
 2   rename-basic-block(n)
 3   for each successor Y of n, where n is the j-th predecessor of Y:
 4     for each phi-function f in Y, where the operand of f is ‘a’
 5       i = top(Stack[a])
 6       replace j-th operand with ai
 7   for each child X of n:
 8     rename(X)
 9   for each instruction S ∈ n:
10     for each variable v that S defines:
11       pop Stack[v]
rename-basic-block的定義參照之前的,這裡只是增加了一些場景。

7.3 跑一下整個流程

7.3.1 偽代碼

 1 i = 1
 2 j = 1
 3 k = 0
 4 while k < 100
 5   if j < 20
 6     j = i
 7     k = k + 1
 8   else
 9     j = k
10     k = k + 2
11 return j

 

 

7.3.2 生成控制流圖

 

 

7.3.3 根據控制流圖生成支配樹

 

 

7.3.4 計算支配前沿

一般從支配樹的葉子節點開始計算,第一輪計算所有葉子節點:

DF(7) = {9}, DF(9) = {3}, DF(5) = {9}, DF(10) = {}

第二輪去掉支配樹的所有葉子節點,計算第二輪葉子節點的支配前沿:

DF(4) = {3}

第三輪刪掉葉子節點,並計算當前葉子節點的支配前沿:

DF(3) = {3}

第四輪刪掉葉子節點,並計算當前葉子節點的支配前沿:

DF(0) = {}

7.3.5 插入φ函數

上一節求出來的DF集合其實只有2個元素,所以只需要在L3和L9的基本塊開始處插入φ函數,存在多種定義的變數只有j和k,所以下麵在L3和L9插入j和k的φ函數:

 

 

7.3.6 φ函數的參數個數

是否存在只有一個前驅的φ函數?如果只有一個前驅,那說明變數只有一個定義,自然就不需要φ函數。

是否存在參數多餘2個的φ函數?如果前驅個數大於2,自然就會出現參數多餘2的φ函數。

7.3.7 變數重命名

 

 

 

7.3.8 優化SSA範式

上面生成的SSA範式,從SSA的定義上看雖然已經是最簡的了,但可能存在一些用不上的變數定義,砍掉這些冗餘的定義是生命周期檢查的工作,經過生命周期檢查,僅在變數i還處在生命周期範圍內的程式點才需要插入i的φ函數。

下麵L1處的i的定義後面沒機會使用了,所以L1處的φ函數插入是不必要的:

 

 

7.4 使用SSA簡化分析

SSA範式可以用來簡化各種基於數據流的分析。SSA範式之前,數據流分析的某個變數的定義是一個集合,SSA範式轉換之後這些變數都變成了唯一定義;而且由於每個變數只有一次定義,相當於說每個變數都可以轉換成常量(迴圈內定義的變數除外,每次迴圈迭代,變數都會被重新定義)。

7.4.1 簡化冗餘代碼刪除

如果一個變數定義了,沒有使用,並且該定義的語句也沒有其他副作用,可以將該變數定義的語句刪除。(SSA之前變數是否被使用的含義就要複雜多了,因為會有多個版本的變數定義)

給每個SSA轉換之後的每個變數保存一個計數器,初始化為0。遍歷一遍代碼,每次使用就將計數器加一,遍歷完如果某個變數的使用計數器為0,則可以刪除變數的定義語句。

7.4.2 簡化常量傳播

因為每個變數的定義都只有一個定義,所以在變數定義時就能判斷變數是常量,還是真的變數。如果變數的定義依賴某個外部輸入,則它不是常量。如果變數的定義依賴的是一個常量,或者依賴的變數是一個常量,則常量可以一直傳播下去,所有類似的變數都能轉換成常量。直到明確所有變數都是依賴某個外部輸入。

如果碰到φ函數怎麼辦?因為φ函數會給變數的賦值增加多種可能性,所以變數的定義變成了一個集合,只有當集合中所有定義都是常量的情況下,才能將該變數轉換成常量。

下麵是llvm的常量傳播的實現:

 

 

7.4.3 SSA範式轉換之後的生命周期分析

新的生命周期分析演算法如下:

 1 For each statement S in the program:
 2   IN[S] = OUT[S] = {}
 3 For each variable v in the program:
 4   For each statement S that uses v:
 5     live(S, v)
 6 live(S, v):
 7   IN[S] = IN[S] ∪ {v}
 8   For each P in pred(S):
 9     OUT[P] = OUT[P] ∪ {v}
10     if P does not define v
11       live(P, v)

 

7.5 SSA簡史

  1. “An Efficient Method of Computing Static Single Assignment Form, ” appeared in the conference Record of the 16th ACM Symposium on principles of Programming Languages (Jan. 1989). https://c9x.me/compile/bib/ssa.pdf 
  2. Efficiently Computing Static Single Assignment Form and the Control Dependence Graph, ACM Transact~ons on Programmmg Languages and Systems, VO1 13, NO 4, October, le91, Pages 451.490. Efficiently computing static single assignment form and the control dependence graph (utexas.edu)
  3. Lengauer, T. and Tarjan, R. "A Fast Algorithm for Finding Dominators in a Flowgraph", TOPLAS, 1:1 (1979) pp 121-141
  4. Briggs, P. and Cooper, K. and Harvey, J. and Simpson, L. "Practical Improvements to the Construction and Destruction of Static Single Assignment Form", SP&E (28:8), (1998) pp 859-881

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 目錄 一、前景回顧 二、規劃頁表 三、實現頁表 四、運行測試 一、前景回顧 前面我們已經介紹了分頁機制的運行原理,那麼如何開啟分頁機制呢,也簡單,分為如下三個步驟: 1、創建頁目錄表並初始化頁記憶體。 2、將頁目錄表地址賦值為CR3。 3、打開CR0寄存器的PG位。 可以看出頁表是分頁機制的核心,接下 ...
  • 一、CDN是什麼? CDN的全稱是Content Delivery Network,即內容分髮網絡。其目的是通過在現有的Internet中增加一層新的CACHE(緩存)層,將網站的內容發佈到最接近用戶的網路”邊緣“的節點,使用戶可以就近取得所需的內容(就近原則),提高用戶訪問網站的響應速度。從技術上 ...
  • 分享嘉賓:葉聰 騰訊 技術專家 編輯整理:張智躍 內容來源:DataFun AI Talk「智能技術前沿實踐分享」 出品社區:DataFun 導讀: 本次分享系統介紹電腦視覺的基礎知識,如何利用這些識別演算法實現一個應用,同時進行部署、推廣這一整套流程。主要包括以下六個部分: 1、朋友圈爆款活動背後 ...
  • 6月15日,由中國信通院主辦的以 “原生聚力,雲數賦能”為主題的“2022雲原生產業大會”在北京舉行。憑藉創新技術和領先實踐,騰訊云云巢榮獲“雲原生技術創新案例”獎。 騰訊云云巢是騰訊雲自主研發的一站式雲原生有狀態服務平臺,基於Kubernetes容器化架構,為各類有狀態服務提供統一的集群管理、資源 ...
  • 一、開發背景 產品出設計稿要求做一個仿原生app簡訊驗證碼組件,花了兩小時搞出來一個還可以的組件,支持屏幕自適應,可以用於彈出框,或自己封裝的vue組件里,希望可以幫助那些被產品壓榨的同學,哈哈。😄 其核心思想就是利用一個輸入框使用css3,translate屬性,每輸入一次後向右位移一個單位位置 ...
  • 認識WEB **「網頁」**主要是由文字、圖像和超鏈接等元素構成,當然除了這些元素,網頁中還可以包括音頻、視頻以及Flash等。 **「瀏覽器」**是網頁顯示、運行的平臺。 「瀏覽器內核」(排版引擎、解釋引擎、渲染引擎) 常見的瀏覽器及其內核 瀏覽器 內核 備註 IE Trident IE、獵豹安全 ...
  • HTML各知識點總結: 基本標簽 標題標簽、段落標簽、換行標簽、水平線標簽、字體樣式標簽、註釋和特殊符號 網頁插入 圖像、超鏈接,視頻、音頻、列表、表格、表單、內聯框架等 超鏈接 錨鏈接、功能性鏈接 列表 有序列表、無序列表、自定義列表 表格 行、列、跨行、跨列 表單 提交格式、文本框、密碼框、單選 ...
  • 昨天太晚就沒來得及更新,今天是spu管理界面,這個界面一共有三個界面需要切換,完成了兩個界面,而且今天的難度在於最後兩個章節,富有一定的邏輯性,當然中間也有很多需要註意的,比如ElementUI的照片牆需要添加list屬性而且值為你的數據並且必須是一個數組必須有name、url屬性 一.spu管理 ...
一周排行
    -Advertisement-
    Play Games
  • Timer是什麼 Timer 是一種用於創建定期粒度行為的機制。 與標準的 .NET System.Threading.Timer 類相似,Orleans 的 Timer 允許在一段時間後執行特定的操作,或者在特定的時間間隔內重覆執行操作。 它在分散式系統中具有重要作用,特別是在處理需要周期性執行的 ...
  • 前言 相信很多做WPF開發的小伙伴都遇到過表格類的需求,雖然現有的Grid控制項也能實現,但是使用起來的體驗感並不好,比如要實現一個Excel中的表格效果,估計你能想到的第一個方法就是套Border控制項,用這種方法你需要控制每個Border的邊框,並且在一堆Bordr中找到Grid.Row,Grid. ...
  • .NET C#程式啟動閃退,目錄導致的問題 這是第2次踩這個坑了,很小的編程細節,容易忽略,所以寫個博客,分享給大家。 1.第一次坑:是windows 系統把程式運行成服務,找不到配置文件,原因是以服務運行它的工作目錄是在C:\Windows\System32 2.本次坑:WPF桌面程式通過註冊表設 ...
  • 在分散式系統中,數據的持久化是至關重要的一環。 Orleans 7 引入了強大的持久化功能,使得在分散式環境下管理數據變得更加輕鬆和可靠。 本文將介紹什麼是 Orleans 7 的持久化,如何設置它以及相應的代碼示例。 什麼是 Orleans 7 的持久化? Orleans 7 的持久化是指將 Or ...
  • 前言 .NET Feature Management 是一個用於管理應用程式功能的庫,它可以幫助開發人員在應用程式中輕鬆地添加、移除和管理功能。使用 Feature Management,開發人員可以根據不同用戶、環境或其他條件來動態地控制應用程式中的功能。這使得開發人員可以更靈活地管理應用程式的功 ...
  • 在 WPF 應用程式中,拖放操作是實現用戶交互的重要組成部分。通過拖放操作,用戶可以輕鬆地將數據從一個位置移動到另一個位置,或者將控制項從一個容器移動到另一個容器。然而,WPF 中預設的拖放操作可能並不是那麼好用。為瞭解決這個問題,我們可以自定義一個 Panel 來實現更簡單的拖拽操作。 自定義 Pa ...
  • 在實際使用中,由於涉及到不同編程語言之間互相調用,導致C++ 中的OpenCV與C#中的OpenCvSharp 圖像數據在不同編程語言之間難以有效傳遞。在本文中我們將結合OpenCvSharp源碼實現原理,探究兩種數據之間的通信方式。 ...
  • 一、前言 這是一篇搭建許可權管理系統的系列文章。 隨著網路的發展,信息安全對應任何企業來說都越發的重要,而本系列文章將和大家一起一步一步搭建一個全新的許可權管理系統。 說明:由於搭建一個全新的項目過於繁瑣,所有作者將挑選核心代碼和核心思路進行分享。 二、技術選擇 三、開始設計 1、自主搭建vue前端和. ...
  • Csharper中的表達式樹 這節課來瞭解一下表示式樹是什麼? 在C#中,表達式樹是一種數據結構,它可以表示一些代碼塊,如Lambda表達式或查詢表達式。表達式樹使你能夠查看和操作數據,就像你可以查看和操作代碼一樣。它們通常用於創建動態查詢和解析表達式。 一、認識表達式樹 為什麼要這樣說?它和委托有 ...
  • 在使用Django等框架來操作MySQL時,實際上底層還是通過Python來操作的,首先需要安裝一個驅動程式,在Python3中,驅動程式有多種選擇,比如有pymysql以及mysqlclient等。使用pip命令安裝mysqlclient失敗應如何解決? 安裝的python版本說明 機器同時安裝了 ...