語(yǔ)法分析樹(shù)是對(duì)輸入程序的推導(dǎo)或語(yǔ)法分析的圖表示。
相對(duì)于源程序文本，語(yǔ)法分析樹(shù)比較大，因?yàn)樗硎玖送暾耐茖?dǎo)過(guò)程，樹(shù)中的每個(gè)結(jié)點(diǎn)分別對(duì)應(yīng)于推導(dǎo)過(guò)程中的各個(gè)語(yǔ)法符號(hào)。編譯器必須為每個(gè)結(jié)點(diǎn)和邊分配內(nèi)存，并必須在編譯期間遍歷所有的邊和結(jié)點(diǎn)。
語(yǔ)法分析樹(shù)主要用于語(yǔ)法分析的討論中和屬性語(yǔ)法系統(tǒng)中，此時(shí)語(yǔ)法分析樹(shù)是主要的IR。
抽象語(yǔ)法樹(shù)保留了語(yǔ)法分析樹(shù)個(gè)基本結(jié)構(gòu)，但剔除了其中非必要的結(jié)點(diǎn)（主要是忽略了非終結(jié)符的大部分結(jié)點(diǎn)）。表達(dá)式地優(yōu)先級(jí)和語(yǔ)法保持原樣，但無(wú)關(guān)的結(jié)點(diǎn)已經(jīng)消失了。
a×2+a×2×b的AST：
AST是一種接近源碼層次的表示。因?yàn)槠渑c語(yǔ)法分析樹(shù)大致對(duì)應(yīng)，語(yǔ)法分析器可以直接建立AST。
程序中最簡(jiǎn)單的控制流單位是一個(gè)basic block（基本程序塊），即（最大長(zhǎng)度的）無(wú)分支代碼序列?；境绦驂K是一個(gè)操作序列，其中的各個(gè)操作總是按序全部執(zhí)行，除非某個(gè)操作引發(fā)了異常?？刂瓶偸菑牡谝粋€(gè)操作進(jìn)入基本程序塊，在完成最后一個(gè)操作后退出基本程序塊。
在CFG中，每一個(gè)結(jié)點(diǎn)都代表一個(gè)basic
block（基本快， a straight-line piece of code without any jumps or jump
targets；jump targets start a block, and jumps end a
block）。CFG中的有向邊用于表示控制流中的跳轉(zhuǎn)。在大多數(shù)的表示中，有兩種特殊指向塊：
entry block，通過(guò)它控制進(jìn)入流圖
exit block，經(jīng)由它所有控制離開(kāi)流圖
根據(jù)其構(gòu)造過(guò)程，在CFG中，每一條 A→B的邊擁有以下屬性：
outdegree(A) > 1 or indegree(B) > 1 (or both).
控制流圖對(duì)程序中各個(gè)基本程序塊之間的控制流建立了模型。一個(gè)CFG是一個(gè)有向圖。每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)基本程序塊，每一條邊對(duì)應(yīng)于一個(gè)可能的控制轉(zhuǎn)移。
CFG對(duì)各種可能的運(yùn)行時(shí)控制流路徑提供了一種圖表示法。CFG不同于面向語(yǔ)法的IR（如AST），后者的表明了語(yǔ)法結(jié)構(gòu)。
while循環(huán)的CFG：
if-then-else的CFG：
編譯器通常把CFG和另一種IR聯(lián)用。CFG表示了塊之間的關(guān)系，而塊內(nèi)的操作則用另一種IR表示（例如表達(dá)層次上的AST、DAG或某種線(xiàn)性IR，這種得到的組合是一種混合IR）。
匯編語(yǔ)言就是一種線(xiàn)性代碼，其包含一個(gè)指令序列，其中的各個(gè)指令出現(xiàn)的按順序執(zhí)行。編譯器中使用的線(xiàn)性IR類(lèi)似于抽象機(jī)的匯編代碼
使用線(xiàn)性形式的邏輯為：充當(dāng)編譯器輸入的源代碼是一種線(xiàn)性形式，而編譯器輸出的目標(biāo)機(jī)代碼也是線(xiàn)性的。線(xiàn)性IR中控制流通常模擬了目標(biāo)機(jī)上控制流的實(shí)現(xiàn)，故線(xiàn)性代碼通常包含條件分支和跳轉(zhuǎn)。控制流將線(xiàn)性IR中基本程序塊劃分下來(lái)，塊結(jié)束于分支、跳轉(zhuǎn)或有標(biāo)號(hào)的操作之前
堆棧機(jī)代碼是一種單地址代碼，假設(shè)操作數(shù)存在于一個(gè)棧中。大多數(shù)操作從棧中獲得操作數(shù)，并將其結(jié)果存入棧中。堆棧機(jī)代碼比較緊湊，棧本身建立了一個(gè)隱式地命名空間，從而消除了IR中的許多名字。這縮減了IR形式下程序的大小，但使用棧意味著所有的結(jié)果和參數(shù)都是暫態(tài)的，除非代碼將其顯示地移入內(nèi)存中
Java使用了字節(jié)碼（這是一種緊湊的IR，在概念上類(lèi)似于堆棧機(jī)代碼）。這種字節(jié)碼在解釋器上運(yùn)行，或者先轉(zhuǎn)換為目標(biāo)機(jī)代碼后執(zhí)行。
字節(jié)碼：
為具有緊湊的形式而特地設(shè)計(jì)的IR
通常針對(duì)抽象堆棧機(jī)的代碼
字節(jié)碼得名于其受限的大小
其操作通常是一個(gè)字節(jié)或者更小
Java 編譯器并不像 C/C++ 那樣直接將高級(jí)語(yǔ)言轉(zhuǎn)換成為機(jī)器語(yǔ)言（直接的 CPU 指令）；它將 Java 語(yǔ)言轉(zhuǎn)換成為 JVM 可以理解的 Java 字節(jié)碼。因?yàn)?Java 字節(jié)碼沒(méi)有任何依賴(lài)于平臺(tái)的代碼，它可以在任意安裝好 JVM （準(zhǔn)確的說(shuō)是 JRE）的硬件上運(yùn)行，即使當(dāng) CPU 或 OS 不同時(shí)也如此。編譯好的文件的大小與源碼的大小幾乎一樣，這讓通過(guò)網(wǎng)絡(luò)來(lái)傳輸和運(yùn)行編譯的代碼變得簡(jiǎn)單。
【注】棧IR通常包含一個(gè)swap操作，該操作魂環(huán)棧頂兩個(gè)元素的值
在靜態(tài)單賦值形式中，名字唯一地對(duì)應(yīng)到代碼中特定的定義位置
每個(gè)名字都是通過(guò)單個(gè)操作定義的，這也是靜態(tài)單賦值形式名稱(chēng)的來(lái)歷
每次在操作中使用某個(gè)名字作為參數(shù)時(shí)，這個(gè)名字都編碼了對(duì)應(yīng)值的來(lái)源地信息
文本化的名字實(shí)際上指向了一個(gè)特定的定義位置
wikipedia的解釋?zhuān)?/p>
static
single assignment form (often abbreviated as SSA form or simply SSA) is
a property of an intermediate representation (IR), which requires that
each variable is assigned exactly once, and every variable is defined
before it is used. Existing variables in the original IR are split into
versions, new variables typically indicated by the original name with a
subscript in textbooks, so that every definition gets its own version.
In SSA form, use-def chains are explicit and each contains a single
element.
該代碼的SSA形式包含了新的賦值（x3、x5和x6），這些使得x的各個(gè)SSA形式名與x的各處使用（在對(duì)s和z的賦值中）協(xié)調(diào)起來(lái)。這些賦值確保了沿CFG中的每條邊，x的當(dāng)前值都分配了唯一的名字，名字的分配與控制流沿哪條代碼路徑轉(zhuǎn)移到該邊無(wú)關(guān)。這些賦值操作的右側(cè)都包含了一個(gè)操作—φ函數(shù)，用于合并來(lái)自不同的邊（φ函數(shù)獲取幾個(gè)名字并將其合并，以定義一個(gè)新的名字）。
φ函數(shù)的行為取決于上下文，它選擇其中一個(gè)參數(shù)的值來(lái)定義其目標(biāo)SSA的名字，該參數(shù)對(duì)應(yīng)于CFG中控制流進(jìn)入當(dāng)前的邊。
在基本程序塊的入口處，其所有φ函數(shù)都將在任何其他語(yǔ)句之前并發(fā)執(zhí)行。
首先，它們都會(huì)讀取適當(dāng)參數(shù)的值
然后，定義其目標(biāo)SSA名字
用這種方法定義φ函數(shù)地行為允許操控SSA形式的算法在處理基本程序塊的頂部時(shí)可以忽略φ函數(shù)的順序
【注】
φ函數(shù)的參數(shù)為進(jìn)入進(jìn)本程序塊的各條邊相關(guān)聯(lián)的值的SSA形式名。
在控制流進(jìn)入一個(gè)basic program block時(shí)，該程序塊中的所有φ函數(shù)都將并行執(zhí)行
構(gòu)造SSA形式的過(guò)程會(huì)在CFG中的每個(gè)匯合點(diǎn)之后插入φ函數(shù)。匯合點(diǎn)即為CFG中多條代碼路徑匯合的地方。在匯合點(diǎn)處，不同的SSA形式名必須調(diào)和為一個(gè)名字。
在整個(gè)過(guò)程已經(jīng)轉(zhuǎn)換為SSA賦值形式之后，需遵守兩條規(guī)則：
過(guò)程中的每個(gè)定義都創(chuàng)建了一個(gè)唯一的名字
每個(gè)使用處都引用了一個(gè)定義
引入SSA意在代碼優(yōu)化。SSA中φ函數(shù)的放置包含了值的產(chǎn)生和使用兩方面的信息。命名空間的單賦值特性，使得編譯器可以規(guī)避許多與值的生命周期有關(guān)的問(wèn)題。
數(shù)據(jù)流分析是指一組用來(lái)獲取有關(guān)數(shù)據(jù)如何沿著程序的執(zhí)行路徑流動(dòng)的相關(guān)信息的技術(shù)。【例如某一個(gè)賦值語(yǔ)句的結(jié)果在任何后續(xù)的執(zhí)行路徑中都沒(méi)有被使用，則可以吧這個(gè)賦值語(yǔ)句當(dāng)作死代碼消除】
程序的執(zhí)行可以看作是對(duì)程序狀態(tài)的一系列轉(zhuǎn)換。程序狀態(tài)由程序中的所有變量的值的組成，同時(shí)包括運(yùn)行時(shí)刻棧的棧頂之下的各個(gè)幀棧的相關(guān)值。一個(gè)中間代碼語(yǔ)句的每次執(zhí)行都會(huì)把一個(gè)輸入狀態(tài)轉(zhuǎn)換成一個(gè)新的輸入狀態(tài)。這個(gè)新的輸入狀態(tài)和處于該語(yǔ)句之前的程序點(diǎn)相關(guān)聯(lián)，而輸出狀態(tài)和該語(yǔ)句之后的程序點(diǎn)相關(guān)聯(lián)。
當(dāng)在分析一個(gè)程序的行為時(shí)，必須考慮程序執(zhí)行時(shí)可能采取的各種通過(guò)程序的流圖的程序點(diǎn)序列（“路徑”）。然后從各個(gè)程序點(diǎn)上可能的程序狀態(tài)中抽取出需要的信息，用以解決特定數(shù)據(jù)流分析問(wèn)題。
流圖會(huì)給出的可能的執(zhí)行路徑的信息為：
在一個(gè)基本快內(nèi)部，一個(gè)語(yǔ)句之后的 數(shù)據(jù)點(diǎn)和它的下一個(gè)語(yǔ)句之前的程序點(diǎn)相同
如果有一個(gè)從基本快B1到基本快B2的邊，那么B2的第一個(gè)語(yǔ)句之前的程序點(diǎn)可能緊跟在B1的最后一個(gè)語(yǔ)句后的程序點(diǎn)之后
可以把從點(diǎn)P1到點(diǎn)P2的一個(gè)執(zhí)行路徑（execution path，簡(jiǎn)稱(chēng)路徑）定義為滿(mǎn)足下列條件的點(diǎn)序列P1,P2,...,Pn:
要么Pi是緊靠在一個(gè)語(yǔ)句前面的點(diǎn)，且Pi+1是緊跟在該語(yǔ)句后的點(diǎn)
要么Pi是某個(gè)基本塊的結(jié)尾，且Pi+1是該基本塊的一個(gè)后繼基本塊的開(kāi)頭
到達(dá)定值是最常見(jiàn)和有用的數(shù)據(jù)流模式之一。編譯器能夠根據(jù)到達(dá)定值信息知道x在點(diǎn)p上的值是否為常量，而如果x在點(diǎn)p上被使用，則調(diào)試器可以指出x是否未經(jīng)定值就被使用。
如果存在一條從緊跟在定值d后面的程序點(diǎn)到達(dá)某一程序點(diǎn)p的路徑，并且在這條路徑上d沒(méi)有被“殺死”，就說(shuō)定值d到達(dá)程序點(diǎn)p（如果在這條路徑上有對(duì)變量x的其他定值，就說(shuō)變量x的這個(gè)定值被“殺死”了）。
來(lái)自wikipedia的解釋?zhuān)?/p>
In compiler theory, a reaching definition for a given instruction is an earlier instruction whose target variable can reach (be assigned to) the given one without an intervening assignment.
例如：
d1 : y :=3d2 : x := y
對(duì)于d2而言，d1是達(dá)到i定值
d1 : y :=3d2 : y :=4d3 : x := y
對(duì)于d3而言，d1不在是到達(dá)定值，因?yàn)閐2“殺死”了它：在d1中定義的值再也無(wú)法到達(dá)d3。
變量x的一個(gè)定值是（可能）將一個(gè)值賦給x的語(yǔ)句。過(guò)程參數(shù)、數(shù)組訪問(wèn)和間接引用都可以有別名，因此指出一個(gè)語(yǔ)句是否向特定程序變量x賦值并不是一件容易的事。
在所有的數(shù)據(jù)流分析應(yīng)用中，則會(huì)把每個(gè)程序點(diǎn)和一個(gè)數(shù)據(jù)流值（data-flow value）關(guān)聯(lián)起來(lái)。這個(gè)值是在該點(diǎn)可能觀察到的所有程序狀態(tài)的集合的抽象表示。所有可能的數(shù)據(jù)流值的集合稱(chēng)為這個(gè)數(shù)據(jù)流應(yīng)用的域（domain）。【例如，到達(dá)定值的數(shù)據(jù)流值的域是程序的定值集合的所有子集的集合】
把每個(gè)語(yǔ)句s之前和之后的數(shù)據(jù)流值分別記為IN[s]和OUT[s]。數(shù)據(jù)流問(wèn)題（data-flow problem）就是要對(duì)一組約束求解（這組約束對(duì)所有的語(yǔ)句s限定了IN[s]和OUT[s]之間的關(guān)系）。
約束分為兩種：
基于語(yǔ)句語(yǔ)義（傳遞函數(shù)）的約束
基于控制流的約束
在一個(gè)語(yǔ)句之前和之后的數(shù)據(jù)流值受該語(yǔ)句的語(yǔ)義的約束。一個(gè)賦值語(yǔ)句之前和之后的數(shù)據(jù)流值的關(guān)系被稱(chēng)為傳遞函數(shù)（transfer function）。
迭代數(shù)據(jù)流分析（ITERATIVE DATA-FLOW ANALYSIS）
編譯器使用數(shù)據(jù)流分析來(lái)確定進(jìn)行優(yōu)化的機(jī)會(huì)，并證明特定變換的安全性。即Cytron et al.’s algorithm。
傳統(tǒng)SSA構(gòu)造算法（即從線(xiàn)性IR到SSA的構(gòu)造）的具體步驟
遍歷IR構(gòu)造CFG
計(jì)算支配邊界
確定φ函數(shù)（Phi函數(shù)）的位置
變量重命名
確定基本塊（basic block）的算法：
（1）查找基本塊入口源代碼的首行、轉(zhuǎn)移代碼（有條件和無(wú)條件）、轉(zhuǎn)移代碼的下一行
（2）基本塊構(gòu)造：由入口點(diǎn)開(kāi)始，將其組織成各自的基本塊。
（3）如果有語(yǔ)句不在任一基本塊中，則稱(chēng)之為“死代碼”，刪除
當(dāng)確定基本塊之后，接著構(gòu)造CFG
CFG構(gòu)造如果在一個(gè)有序代碼中，基本塊B2跟在B1后，那么產(chǎn)生一個(gè)B1到B2的有向邊
（1）有跳轉(zhuǎn)點(diǎn)。這個(gè)點(diǎn)從B1的結(jié)束點(diǎn)跳轉(zhuǎn)到B2的開(kāi)始點(diǎn)
（2）無(wú)跳轉(zhuǎn)點(diǎn)（有序代碼中），B2跟在B1后，且B1的結(jié)束點(diǎn)不是無(wú)條件跳轉(zhuǎn)語(yǔ)句
例如，從B0到B6的每條代碼路徑都包含了結(jié)點(diǎn)B0、B1、B5和B6。因此，Dom(B6)為{B0，B1，B5，B6}。
集合Dom(Bi)中包含了支配Bi的所有結(jié)點(diǎn)。
支配性：在入口結(jié)點(diǎn)B0的流圖中，當(dāng)且僅當(dāng)Bi位于從B0到Bj的每條路徑上時(shí)，結(jié)點(diǎn)Bi才支配結(jié)點(diǎn)Bj。
求解數(shù)據(jù)流問(wèn)題的方程：
為使用上述方程，需要使用三個(gè)步驟：
（1） 構(gòu)建一個(gè)CFG
（2） 收集各個(gè)程序塊的初始信息
（3） 求解方程，生成各個(gè)程序塊的Dom集合
考慮CFG的結(jié)點(diǎn)n中的一個(gè)定義。該值到達(dá)某個(gè)結(jié)點(diǎn)m時(shí)，如果n∈Dom(m)，則該值不需要φ函數(shù)，因?yàn)榈竭_(dá)m的每條代碼路徑都必然經(jīng)由n。該值無(wú)法到達(dá)m的唯一可能就是有一個(gè)同名定義的干擾，即在n和m之間的某個(gè)結(jié)點(diǎn)p中，出現(xiàn)了與該值同名的另一個(gè)定義。在這種情況下，在n中的定義無(wú)需φ函數(shù)，而p中的重新定義則需要。
結(jié)點(diǎn)n中的定義，僅在滿(mǎn)足下列條件的匯合點(diǎn)才需要插入對(duì)應(yīng)的φ函數(shù)：
（1）n支配m的一個(gè)前驅(qū)
（2）n并不嚴(yán)格支配m
嚴(yán)格支配性：當(dāng)且僅當(dāng)a∈Dom(b)-時(shí)，a嚴(yán)格支配b。
【注】：DF(n)表示：在離開(kāi)n的每條CFG路徑上，從結(jié)點(diǎn)n可達(dá)但不支配的第一個(gè)結(jié)點(diǎn)。
此例中，B5支配B6、B7和B8，但不支配B3。在每條離開(kāi)B5的路徑上，B3都是B5不支配的第一個(gè)結(jié)點(diǎn)，因而，DF(B5)={B3}。
給出流圖中的一個(gè)結(jié)點(diǎn)n，嚴(yán)格支配n的結(jié)點(diǎn)集是Dom(n)-{n}。該集合中與n最接近的結(jié)點(diǎn)稱(chēng)為n的直接支配結(jié)點(diǎn)，記為IDom(n)。流圖的入口沒(méi)有直接支配結(jié)點(diǎn)。
流圖的支配者樹(shù)包含流圖中的每個(gè)結(jié)點(diǎn)。如果m為IDom(n)，那么支配者樹(shù)中有一條邊從m指向n。
偽代碼實(shí)現(xiàn)：
放置φ函數(shù)的關(guān)鍵在于判斷何處真正需要φ函數(shù)，以及哪個(gè)變量需要φ函數(shù)。
由于CFG中只有匯合點(diǎn)才是支配邊界的成員，故首先識(shí)別出圖中的所有匯合點(diǎn)。對(duì)于一個(gè)匯合點(diǎn)j，我們考察其在CFG中的每個(gè)前驅(qū)結(jié)點(diǎn)。
計(jì)算支配邊界的算法：
常規(guī)算法會(huì)在每個(gè)匯合點(diǎn)起始處，為每個(gè)變量放置一個(gè)φ函數(shù)。有了支配邊界之后，編譯器便可以更加準(zhǔn)確地判斷在何處可能需要φ函數(shù)。
基本思想是：基本塊b中對(duì)x的定義，要求在DF(b)集合包含的每個(gè)結(jié)點(diǎn)起始處都放置一個(gè)對(duì)應(yīng)的φ函數(shù)。因?yàn)棣蘸瘮?shù)是對(duì)x的一個(gè)新的定義，此處插入φ函數(shù)，進(jìn)而可能導(dǎo)致額外的φ函數(shù)。
編譯器可以進(jìn)一步縮小插入的φ函數(shù)集合。只在單個(gè)基本塊中活動(dòng)的變量，絕不會(huì)出現(xiàn)與之相應(yīng)的活動(dòng)φ函數(shù)。為了實(shí)現(xiàn)這一規(guī)則，編譯器可以計(jì)算跨多個(gè)程序塊的活動(dòng)變量名的集合，該集合稱(chēng)為全局名字（global name）。它可以對(duì)該集合中的名字插入φ函數(shù)，而忽略不在該集合中的名字。
插入φ函數(shù)的算法：
對(duì)于每個(gè)全乎名字x，算法將WorkList初始化為Blocks(x)。對(duì)于WorkList中的每個(gè)基本塊b，算法在b的支配邊界中每個(gè)程序塊d的起始位置插入φ函數(shù)。在向d添加對(duì)應(yīng)于x的φ函數(shù)之后，算法將d添加到WorkList，以反映d中對(duì)x的新賦值操作。
φ函數(shù)插入算法中的第一步是找到全局名字集合并為每個(gè)名字計(jì)算Blocks集合。
圖(a)中代碼，全局名字集合為{a，b，c，d，i}。
圖(d)給出了Blocks集合。
【注意】：算法為y和z創(chuàng)建了Blocks集合，雖然二者不屬于Globals中。將Globals和Blocks集合的計(jì)算分離開(kāi)來(lái)，可以避免實(shí)例化這些額外的集合，但代價(jià)是需要增加一趟對(duì)代碼的處理。
在最終的靜態(tài)單賦值形式中，每個(gè)全局名字都變?yōu)橐粋€(gè)基本名，而對(duì)該基本名的各個(gè)定義則通過(guò)添加數(shù)字下標(biāo)來(lái)區(qū)分。對(duì)于對(duì)應(yīng)到源語(yǔ)言變量的名字，比如說(shuō)x，算法使用x作為基本名。因而，重命名算法遇到對(duì)x的第一個(gè)定義將被命名為x0，第二個(gè)將被命名為x1。對(duì)于編譯器產(chǎn)生的臨時(shí)值，算法必須產(chǎn)生一個(gè)不同的基本名。
算法（插入φ函數(shù)之后的重命名）實(shí)現(xiàn)為：
foreach global name i? ? counter[i] ←0stack[i] ← ?Rename(n0)NewName(n)? ? i ← counter[n]? ? counter[n] ← counter[n] +1push i ontostack[n]return"ni"Rename(b)foreach φ-function in b,"x ← φ(...)"rewrite x asNewName(x)foreach operation "x ← y op z" in b? ? ? ? rewrite y with subscripttop(stack[y])rewrite z with subscripttop(stack[z])rewrite x asNewName(x)foreach successor of b in the cfg? ? ? ? fill in φ-function parametersforeach successor s of b in the dominator treeRename(s)foreach operation "x ← y op z" in b and each φ-function "x ← φ(...)"pop(stack[x])
該算法對(duì)過(guò)程的支配者樹(shù)進(jìn)行先序遍歷，其中對(duì)定義和使用都進(jìn)行可重命名。在每個(gè)基本塊中，算法首先重命名由程序塊頂部的φ函數(shù)定義的值，然后按序訪問(wèn)程序塊中的各個(gè)操作。算法會(huì)用當(dāng)前的靜態(tài)單賦值形式重寫(xiě)各個(gè)操作數(shù)，接下來(lái)為操作的結(jié)果創(chuàng)建一個(gè)新的靜態(tài)單賦值形式名。算法的后一步使得新名字成為當(dāng)前的名字。在程序塊中所有的操作都已經(jīng)重寫(xiě)之后，算法將使用當(dāng)前的靜態(tài)單賦值形式名，重寫(xiě)程序塊在CFG中各后繼結(jié)點(diǎn)中的適當(dāng)φ函數(shù)參數(shù)。最后，算法對(duì)當(dāng)前程序塊在支配者樹(shù)中的子結(jié)點(diǎn)進(jìn)行遞歸處理。當(dāng)算法從這些遞歸調(diào)用返回時(shí)，它會(huì)將當(dāng)前靜態(tài)單賦值形式名的集合恢復(fù)到訪問(wèn)當(dāng)前程序塊之前的狀態(tài)。
為了管理這一處理過(guò)程，算法對(duì)每個(gè)全局名字使用一個(gè)計(jì)數(shù)器和一個(gè)棧。全局名字的棧包含了該名字當(dāng)前靜態(tài)單賦值形式的下標(biāo)。在每個(gè)定義處，算法通過(guò)將目標(biāo)名字的當(dāng)前計(jì)數(shù)器壓棧來(lái)產(chǎn)生新的下標(biāo)，并將計(jì)數(shù)器加1。因而，名字n棧頂?shù)闹悼偸莕當(dāng)前靜態(tài)單賦值形式名的下標(biāo)。作為處理程序塊的最后一步，算法會(huì)將該程序塊中產(chǎn)生的所有名字從棧中彈出，以恢復(fù)在該程序塊的直接支配結(jié)點(diǎn)末尾處的的當(dāng)前靜態(tài)單賦值形式名字集合。處理當(dāng)前程序塊在支配者樹(shù)中余下的兄弟結(jié)點(diǎn)，可能需要這些名字。
當(dāng)算法中的控制流在支配者樹(shù)中上下移動(dòng)時(shí)，棧模擬了當(dāng)前程序塊中最新定義的生命周期。而在這一方面，計(jì)數(shù)器則是單調(diào)遞增的，以確保各個(gè)連續(xù)的定義都能分配一個(gè)唯一的靜態(tài)單賦值形式名
該算法初始化了棧和計(jì)數(shù)器，然后對(duì)支配者樹(shù)的根結(jié)點(diǎn)（即CFG的入口結(jié)點(diǎn)）調(diào)用Rename。Rename會(huì)重寫(xiě)該程序塊，并下降到其在支配者樹(shù)的各個(gè)后繼結(jié)點(diǎn)上遞歸處理。為完成對(duì)該程序塊的處理，Rename會(huì)彈出處理該程序塊期間壓棧的任何名字，而NewName會(huì)操作計(jì)數(shù)器和棧，以按需創(chuàng)建新的靜態(tài)單賦值形式名。
Simple and Direction SSA Constriruction Algorithm
傳統(tǒng)的SSA構(gòu)造算法（如之前的Cytron et al.’s algorithm），是直接從線(xiàn)性IR構(gòu)造SSA。而Simple and Efficient Construction of Static Single Assignment Form這一論文則是允許從AST、Bytecode甚至源碼直接構(gòu)造SSA。
LLVM IR雖然為為SSA形式，但如果所有生成的LLVM IR都要前端自己計(jì)算好如何生成SSA形式，對(duì)于前端而言將十分棘手。故LLVM IR借助“memory不是SSA value”的特點(diǎn)，給用戶(hù)留了一個(gè)后門(mén)：前端在生成LLVM IR時(shí)，可以選擇不生成真正的SSA形式，而是把局部變量生成alloca/load/store形式：
用alloca來(lái)“聲明”變量，得到一個(gè)指向該變量的指針；
用store來(lái)把值存進(jìn)變量里；
用load來(lái)把值讀出為SSA value。
此時(shí)，對(duì)局部變量的讀寫(xiě)就變得跟普通內(nèi)存的讀寫(xiě)一樣，不需要SSA形式。接著，LLVM利用mem2reg pass，識(shí)別出這種模式的alloca，并將它提升為SSA value（并消除掉store與load，改為普通的SSA層面的def-use/use-def關(guān)系，并且在合適的位置安插φ函數(shù)和變量重命名）。
Clang就是講生成SSA形式的任務(wù)交給LLVM處理：Clang的前端只會(huì)把某些臨時(shí)值生成SSA value；對(duì)于顯示的局部變量，Clang前端都只是生成alloca/load/store形式的LLVM IR；交給LLVM IR之后，經(jīng)過(guò)mem2reg pass，IR才真正進(jìn)入了普通的SSA形式。
LLVM的mem2reg pass本質(zhì)上就是識(shí)別“局部變量”的模式，并對(duì)它們構(gòu)建SSA形式。
LLVMmem2reg pass的實(shí)現(xiàn)：
// 遍歷指令序列找到 allocafor(Instruction instr : instructions){if(isa(instr))? ? ? ? allocas.push_back(instr);}// 一個(gè)一個(gè)的提升 alloca 指令for(Alloca alloca : allocas){// 判斷是否可以提升if(!alloca.isAllocaPromoteable())continue;// 跳過(guò)無(wú)使用者的alloca指令if(alloca.user_begin() == alloca.user_end())continue;// 收集alloca指令的使用，定義信息info.analyzeAlloca(alloca);// 下面的函數(shù)，對(duì)只有一次定義（即只有一條 store 指令）的 alloca 進(jìn)行優(yōu)化// 把所有的 load 指令全部用定義時(shí)保存的 value 替換if(info.definingBlocks.size() ==1)? ? ? ? rewriteSingleStoreAlloca(alloca, info);// 下面的代碼僅僅對(duì)只在一個(gè)基本塊中使用和定義的alloca指令進(jìn)行優(yōu)化if(info.onlyUsedOneBlock)? ? ? ? promoteSingleBlockAlloca(alloca, info);// 插入無(wú)參數(shù)的Phi函數(shù)，使用標(biāo)準(zhǔn)的基于支配邊界的算法，其中使用DJ圖的方式進(jìn)行了優(yōu)化determineInsertionPoint(alloca, allocaNum, info);// 使用 IDF 和標(biāo)準(zhǔn) ssa 構(gòu)造算法提升 alloca ，決定那些需要插入 Phi 函數(shù)DefBlocks.insert(Info.DefiningBlocks.begin(), Info.DefiningBlocks.end());? ? ComputeLiveInBlocks(AI, Info, DefBlocks, LiveInBlocks);? ? IDF.setLiveInBlocks(LiveInBlocks);? ? IDF.setDefiningBlocks(DefBlocks);? ? IDF.calculate(PHIBlocks);// 執(zhí)行 SSA 重命名算法，并插入 Phi 節(jié)點(diǎn)RenamePassWorkList.emplace_back(&F.front(),nullptr,std::move(Values));do{// RenamePass may add new worklist entries.RenamePass(RPD.BB, RPD.Pred, RPD.Values, RenamePassWorkList);? ? }while(!RenamePassWorkList.empty());// 移除 allocasfor(unsignedi =0, e = Allocas.size(); i != e; ++i)? ? {? ? ? ? Instruction *A = Allocas[i];? ? ? ? A->replaceAllUsesWith(UndefValue::get(A->getType()));? ? ? ? A->eraseFromParent();? ? }// 最后執(zhí)行一趟消除平凡Phi函數(shù)的操作，while(eliminatedAPHI)? ? {// if the phi merges one value and/or undefs, get the valueif((V = simplifyInstruction(phi, DT)) != null)? ? ? ? {? ? ? ? ? ? phi.replaceAllUsesWith(V);? ? ? ? ? ? phi.eraseFromBasicBlock();? ? ? ? ? ? newPhiNodes.remove(entity);? ? ? ? ? ? eliminatedAPHI =true;continue;? ? ? ? }? ? }}
來(lái)自論文
Simple and E?cient Construction of Static Single Assignment Form
Matthias Braun1, Sebastian Buchwald1, Sebastian Hack2, Roland Lei?a2, Christoph Mallon2, and Andreas Zwinkau1
Cytron et al.’s algorithm的缺點(diǎn)：
其輸入程序必須表示為CFG的非SSA形式
為保證放置φ函數(shù)的代價(jià)最小，此算法依賴(lài)以下幾點(diǎn)：
為了計(jì)算φ函數(shù)的放置位置，需要計(jì)算支配樹(shù)和迭代支配邊界
為避免死亡φ函數(shù)，需要執(zhí)行活性分析或者死代碼消除
在translate源程序的時(shí)候，需要注意：一組statements的IR通常會(huì)出現(xiàn)在一個(gè)basic block中。因此，此方法按照程序的執(zhí)行順序（execution order）處理所有表達(dá)式，并且在每個(gè)基本塊中的變量和其當(dāng)前的定義表達(dá)式（ defining expression）之間建立映射。當(dāng)遇到對(duì)變量賦值情況，需要將賦值號(hào)右側(cè)的IR作為當(dāng)前變量的定義。當(dāng)一個(gè)變量被訪問(wèn)時(shí)，就尋找其當(dāng)前定義（current definition，通過(guò)algo 1實(shí)現(xiàn)），這一過(guò)程就稱(chēng)為local value numbering。當(dāng)一個(gè)basic block完成了local value numbering，就稱(chēng)這個(gè)基本塊為filled。只有當(dāng)一個(gè)basic block完成了local value numbering，才能夠繼續(xù)添加后繼基本塊（這一性質(zhì)在處理incomplete CFG時(shí)會(huì)用到）。
Algorithm 1: Implementation of local value numbering
writeVariable(variable, block, value):? ? currentDef[variable][block] ←valuereadVariable(variable, block):ifcurrentDef[variable] contains block:# local value numberingreturn currentDef[variable][block]# global value numberingreturnreadVariableRecursive(variable, block)
【注意】:
如果在對(duì)一個(gè)基本塊進(jìn)行賦值之前，對(duì)其進(jìn)行訪問(wèn)則會(huì)出現(xiàn)問(wèn)題。例如上例中的變量d與之對(duì)應(yīng)的值v？，d的定義不能從CFG的root到當(dāng)前basic block的路徑上查找到。此外，程序中的多個(gè)定義也許會(huì)reach到相同的use。
如果當(dāng)前塊沒(méi)有變量的定義，便遞歸地在其前驅(qū)（predecessors）基本塊中查找定義。
**遞歸查找算法為：
如果基本塊只有一個(gè)前驅(qū)，就只在其前驅(qū)中遞歸地查詢(xún)定義
否則，從其所有predecessors中collect它的definitions，并構(gòu)造一個(gè)φ函數(shù)，將φ函數(shù)加入其所有前驅(qū)中定義中，并將該φ函數(shù)作為該basic block中variable的當(dāng)前定義。**
在前驅(qū)中查找的方式可能導(dǎo)致循環(huán)查找（recursive look-ups），比如在循環(huán)中進(jìn)行查找（Due to loops in the program, those might lead to endless recursion）。為了避免程序出現(xiàn)死循環(huán)，在查找前先創(chuàng)建一個(gè)沒(méi)有operands的φ函數(shù)，并將其記錄為basic block中變量的當(dāng)前定義。然后，我們確定φ函數(shù)的operands。如果遞歸查找arrive back到該基本塊，則此φ函數(shù)將提供一個(gè)定義，并且遞歸將結(jié)束。
為了更輕易的展示global value numbering，值vi的index按照算法在插入它們的順序進(jìn)行assigning。我們假設(shè)在讀取x之前已經(jīng)構(gòu)造好了loop，也就是說(shuō)，已經(jīng)通過(guò)local value numbering將v0和v1作為為x的definition，而利用loop之后的statement來(lái)查找x。由于在loop之后的block中沒(méi)有x的定義，因此執(zhí)行遞歸查找。 該block只有一個(gè)predecessor，所以在這里不需要φ函數(shù)。 這個(gè)predecessor只是一個(gè)loop header，它也沒(méi)有x的定義，但有兩個(gè)predecessors。因此，我們放置一個(gè)沒(méi)有任何操作的（operandless）φ函數(shù)v2。 它的第一個(gè)operand是流入loop的值v0，第二個(gè)operand需要進(jìn)一步遞歸。φ函數(shù)v3被創(chuàng)建并從其direct predecessors處獲得其operands。 此外，之前放置的v2終止了遞歸。
Algorithm 2: Implementation of global value numbering
readVariableRecursive(variable, block):ifblock not in sealedBlocks:# Incomplete CFG val ←newPhi(block)? ? ? ? incompletePhis[block][variable] ← valelseif|block.preds| =1:# Optimize the common case of one predecessor: No phi needed val ← readVariable(variable, block.preds[0])else:# Break potential cycles with operandless phi val ←newPhi(block)? ? ? ? writeVariable(variable, block, val)? ? ? ? val ← addPhiOperands(variable, val)? ? writeVariable(variable, block, val)returnvaladdPhiOperands(variable, phi):# Determine operands from predecessors forpred in phi.block.preds:? ? ? ? phi.appendOperand(readVariable(variable, pred))? ? returntryRemoveTrivialPhi(phi)
這種遞歸查找方法可能會(huì)導(dǎo)致冗余的φ函數(shù)，稱(chēng)之為trivial。如果一個(gè)φ函數(shù)references itself and one other valuevany number of times，則稱(chēng)此φ函數(shù)為trivialφ函數(shù)。比如有a.1 = φ(a.1, a.0)。這個(gè)φ函數(shù)完全可以被另一個(gè)定義給替換。還有一種特殊的情況，φ函數(shù)僅僅引用了自身，這種情況僅僅發(fā)生在不可達(dá)或者開(kāi)始基本塊，這時(shí)用一個(gè)Undef值（未定義值）代替。
【注意】:
如果一個(gè)trivial φ函數(shù)被替換，這可能導(dǎo)致引用了此φ函數(shù)的值也變?yōu)閠rivial φ函數(shù)，所以需要遞歸地進(jìn)行替換操作。
Algorithm 3: Detect and recursively remove a trivial φ function
tryRemoveTrivialPhi(phi):? ? same ← Noneforop in phi.operands:ifop = same || op = phi:# Unique value or self?referencecontinueifsame = None:# The phi merges at least two values: not trivial returnphi? ? ? ? same ← opifsame = None:# The phi is unreachable or in the start blocksame ←newUndef()# Remember all users except the phi itselfusers ← phi.users.remove(phi)# Reroute all uses of phi to same and remove phiphi .replaceBy(same)# Try to recursively remove all phi users, # which might have become trivial foruse in users:ifuse is a Phi:? ? ? ? ? ? ? ? tryRemoveTrivialPhi(use)returnsame
如果再也沒(méi)有predes被加入到當(dāng)前basic block時(shí)，就稱(chēng)此basic block 為sealed。只要filled blocks還有successors，則其predecessors一定會(huì)被filled。注意，一個(gè)sealed block不一定會(huì)被filled。一個(gè)filled block包含其自身所有的instructions，并且可以為其successors提供變量定義（variable definitions）。 相反，一個(gè)sealed block可以從其predecessors中查找變量定義，因?yàn)槠渌衟redecessors都是已知的。
即，如果一個(gè)基本塊不會(huì)再加入任何前驅(qū)結(jié)點(diǎn)，那么就可以稱(chēng)為sealed基本塊。因?yàn)橹挥衒illed基本塊擁有后繼，所以前驅(qū)基本塊必須是filled。
Algorithm 4: Handling incomplete CFGs
sealBlock(block):forvariable in incompletePhis[block]:? ? ? ? addPhiOperands(variable, incompletePhis[block][variable])? ? sealedBlocks.add(block)
seal操作會(huì)對(duì)該基本塊的所有incompletePhis進(jìn)行處理，完成處理后將該基本塊加入sealed集合。
如何在一個(gè)unsealed block中處理變量（該變量沒(méi)有當(dāng)前定義）的查找問(wèn)題呢？ 在這種情況下，我們將一個(gè)operandless的φ函數(shù)放入block中，并將其記錄為proxy definition（參見(jiàn)algo 2中的第一種情況）。 此外，我們?yōu)槊總€(gè)block維護(hù)一組proxies：incomplete_phis。 當(dāng)block隨后成為sealed時(shí)，我們將operands添加到這些φ函數(shù)中（參見(jiàn)algo 4）。 此外，當(dāng)φ函數(shù)is complete時(shí)，無(wú)論它是為trivial，我們都需要進(jìn)行check。
在IR構(gòu)造期間，sealing a block是一種explicit action。我們通過(guò)下圖所示的while循環(huán)來(lái)說(shuō)明如何incorporate此步驟。 首先，我們構(gòu)造一個(gè)while headerblock，并以while entryblock為起始，添加一條control flow edge（控制流邊）。 由于隨后需要添加一個(gè)body exit的jump，所以還不能sealwhile header。 接下來(lái)，我們創(chuàng)建body entry和while exitblocks，并且以while header起始，分別為這兩個(gè)blocks添加conditional control flow（條件控制流）。由于再也沒(méi)有predecessors會(huì)被添加到body entryblock中，所以此時(shí)便可以seal它。 由于循環(huán)體中的break instructions（中斷指令），while exitblock可能會(huì)get further predecessors。 現(xiàn)在開(kāi)始fill循環(huán)體。 這可能會(huì)包括更多的inner
control structures（內(nèi)部控制結(jié)構(gòu)），如下圖（b）所示的ifstatement。最后，它們會(huì)converge（聚集）在body exitblock處。 此時(shí)形成body的所有blocks都將被seal。 現(xiàn)在我們將edge添加回while header，并sealwhile header，至此循環(huán)完成。 在最后一步中，我們seal thewhile exit，然后在while循環(huán)后繼續(xù)使用source statement進(jìn)行IR的construction。
【注】：圖中，附屬在basic block旁邊的數(shù)字代表了sealing（上面的數(shù)字）和filling（下面的數(shù)字）的順序。
通過(guò)IO_FILE來(lái)leak出libc地址
?-2021 大專(zhuān)欄|粵ICP備18064926號(hào)-2
