編譯器優(yōu)化那些事兒之區(qū)域分析

1、概念介紹

為了有效地優(yōu)化代碼，編譯器需要在程序的各個(gè)節(jié)點(diǎn)建立并求解與信息有關(guān)的方程來(lái)收集數(shù)據(jù)流信息，并將這些信息分發(fā)給流程圖的每個(gè)塊，這個(gè)過(guò)程被稱為數(shù)據(jù)流分析。

通過(guò)檢查程序的一部分（基本程序塊），編譯器可以執(zhí)行一些優(yōu)化。如下圖所示：

• 在此程序中, d1是無(wú)用的，d1中x的值永遠(yuǎn)不會(huì)在程序中被使用；
• 在編譯時(shí)，d2中的表達(dá)式(1 + 2)將被計(jì)算；

所以該基本程序塊可以被優(yōu)化為：x = 3。

但是有一些優(yōu)化必須通過(guò)檢查整個(gè)程序來(lái)實(shí)現(xiàn)。如下圖所示：

從圖中可以看出：d3對(duì)c的初始化賦值是無(wú)用的，x的值恒定為6，d6可以簡(jiǎn)化為：c = 7。

從上面這個(gè)例子可以看出，僅通過(guò)一兩個(gè)連續(xù)語(yǔ)句，編譯器無(wú)法發(fā)現(xiàn)這些優(yōu)化信息。必須通過(guò)更加全面的數(shù)據(jù)流分析，以便編譯器在程序的每個(gè)節(jié)點(diǎn)都了解以下內(nèi)容：

• 保證哪些變量具有恒定值
• 重新定義之前將使用哪些變量

這篇文章將會(huì)介紹一種數(shù)據(jù)流分析方法——區(qū)域分析，在正式開始之前，我們先來(lái)了解幾個(gè)概念：

• 嚴(yán)格支配：如果不首先通過(guò)x就不可能到達(dá)w，則稱x嚴(yán)格支配w。
• 支配：如果x嚴(yán)格支配w或x=w，則稱x支配w。

以下圖為例，如果想要到達(dá)2、3或4，必須要先通過(guò)1，所以在{1,2,3,4}集合中1占支配地位，1嚴(yán)格支配集合{2,3,4}。

流圖的區(qū)域是節(jié)點(diǎn)N和控制流邊E的集合，必須滿足以下條件：

• N中存在一個(gè)節(jié)點(diǎn)頭h，它支配了N中的所有節(jié)點(diǎn)。
• 如果存在節(jié)點(diǎn)m可以在不經(jīng)過(guò)節(jié)點(diǎn)頭h的情況下到達(dá)N中的節(jié)點(diǎn)n，則m也必然在N中。
• E是N中節(jié)點(diǎn)之間所有控制流邊的集合，進(jìn)入h的循環(huán)邊可以不包含在內(nèi)。

以下圖為例，節(jié)點(diǎn)B1、B2、B3和B4都可以單獨(dú)看做一個(gè)區(qū)域（圖(a)）；節(jié)點(diǎn)B1和B2以及邊B1->B2和循環(huán)邊B2->B1組成的循環(huán)也是一個(gè)區(qū)域（圖(b)）；根據(jù)區(qū)域的第三個(gè)條件，循環(huán)邊可以不包含在區(qū)域內(nèi)，所以節(jié)點(diǎn)B1和B2以及邊B1->B2也可以形成一個(gè)區(qū)域（圖(c)）。

然而，圖(d)中節(jié)點(diǎn)B3、B4以及邊B3->B4組成的子圖（虛線部分）不形成區(qū)域，因?yàn)榭刂屏骷瓤梢酝ㄟ^(guò)節(jié)點(diǎn)B3處進(jìn)入子圖，也可以通過(guò)節(jié)點(diǎn)B4進(jìn)入子圖。B3和B4都無(wú)法做到完全支配另一個(gè)，不符合區(qū)域的第一個(gè)條件。即使我們選擇B3作為頭h，也不符合區(qū)域的第二個(gè)條件。因?yàn)锽1可以不經(jīng)過(guò)B3，沿著邊B1->B4到達(dá)B4，根據(jù)區(qū)域的第二個(gè)條件，B1應(yīng)該在該“區(qū)域”中，但這顯然不正確。

2、區(qū)域分析的基本思想

• 對(duì)于每個(gè)區(qū)域R，以及R中的每個(gè)子區(qū)域R'，我們計(jì)算一個(gè)傳遞函數(shù)，該函數(shù)總結(jié)了從區(qū)域R開始到基本塊B結(jié)束執(zhí)行所有可能路徑的效果。
• 如果基本塊B是區(qū)域R的出口塊（即區(qū)域R內(nèi)的基本塊B有到R外的某個(gè)塊的傳出邊），計(jì)算區(qū)域R的每個(gè)出口塊B的傳遞函數(shù)就是計(jì)算從區(qū)域R的入口通向B過(guò)程中，執(zhí)行所有可能路徑的效果，即整個(gè)區(qū)域R的傳遞函數(shù)。
• 從單個(gè)基本塊組成的區(qū)域開始，逐步構(gòu)造更大的區(qū)域，計(jì)算更大區(qū)域的傳遞函數(shù)。
• 在構(gòu)造更大的上層區(qū)域時(shí)，如果區(qū)域R的邊在R的上層區(qū)域上形成一個(gè)非循環(huán)流圖。我們可以繼續(xù)按上層區(qū)域的拓?fù)漤樞蛴?jì)算傳遞函數(shù)。
• 如果R是一個(gè)循環(huán)區(qū)域，那么我們只需要考慮循環(huán)邊對(duì)R入口節(jié)點(diǎn)的影響。
• 直到整個(gè)程序組成一個(gè)區(qū)域，并計(jì)算整個(gè)程序組成的區(qū)域P的傳遞函數(shù)，若入口節(jié)點(diǎn)處的初始值為V，則：

3、傳遞函數(shù)

在一個(gè)語(yǔ)句之前和之后的數(shù)據(jù)流值受該語(yǔ)句的語(yǔ)義約束，即語(yǔ)句前后的程序點(diǎn)的數(shù)據(jù)流值受該語(yǔ)句語(yǔ)義的約束，這種約束關(guān)系稱為傳遞函數(shù)?；緣K的傳遞函數(shù)表示為（以下都以Reaching Definitions 為例）：F(x) = Gen U (x - Kill)

其中，x表示基本塊B的輸入；F(x)表示基本塊B的輸出；kill表示被基本塊B中各語(yǔ)句殺死的變量的集合；Gen表示基本塊中沒(méi)有被各語(yǔ)句殺死的定值的集合。

上圖顯示了流圖中各基本塊的Gen和Kill集合。以基本塊B1為例，該基本塊有三條語(yǔ)句：

• d1: i = f-1，“生成”了一個(gè)對(duì)變量i的賦值d1，并“殺死”了程序中其它對(duì)i的賦值，即d4和d7；
• d2: j = n，“生成”了一個(gè)對(duì)變量j的賦值d2，并“殺死”了程序中其它對(duì)j的賦值，即d5；
• d3: a = u1，“生成”了一個(gè)對(duì)變量a的賦值d3，并“殺死”了程序中其它對(duì)a的賦值，即d6。

所以基本塊B1的Gen為{d1,d2,d3}，kill為{d4,d5,d6,d7}。

對(duì)于區(qū)域分析，構(gòu)造更大的區(qū)域?qū)嶋H上就是更新了Gen和Kill集合的值。

4、關(guān)于傳遞函數(shù)的必要假設(shè)

為了使區(qū)域分析發(fā)揮作用，我們需要對(duì)區(qū)域中傳遞函數(shù)集的屬性做出某些假設(shè)。具體來(lái)說(shuō)，我們需要對(duì)傳遞函數(shù)進(jìn)行三個(gè)基本操作： 組合 、匯聚和 閉包 。

4.1 組合（composition）

節(jié)點(diǎn)序列的傳遞函數(shù)可以通過(guò)各個(gè)節(jié)點(diǎn)的傳遞函數(shù)的組合來(lái)導(dǎo)出。設(shè)F1和F2是兩個(gè)節(jié)點(diǎn)的傳遞函數(shù)，執(zhí)行F1后執(zhí)行F2的效果用F2(F1(x))表示：

4.2 匯聚（meet）

匯聚用于導(dǎo)出執(zhí)行路徑不同，但輸入端點(diǎn)與輸出端點(diǎn)相同的節(jié)點(diǎn)。一般用F1(x)∧F2(x)表示：

4.3 閉包（closure）

如果F表示循環(huán)的傳遞函數(shù)，那么Fn表示循環(huán)n次的效果。在迭代次數(shù)未知的情況下，我們必須假設(shè)循環(huán)可以執(zhí)行0次或多次。我們用F*(x)表示這樣一個(gè)循環(huán)的傳遞函數(shù)，則F的閉包如下圖所示：

5、處理可簡(jiǎn)化流圖

可簡(jiǎn)化流圖是指那些可以通過(guò)以下兩個(gè)規(guī)則轉(zhuǎn)換簡(jiǎn)化為單個(gè)節(jié)點(diǎn)的流圖：

• T1：刪除循環(huán)。如果n是具有循環(huán)的節(jié)點(diǎn)，即邊n->n，刪除該邊（n的所有此類邊）。

如上圖所示：R是執(zhí)行T1規(guī)則后形成的新區(qū)域，原區(qū)域n的頭結(jié)點(diǎn)H也是新區(qū)域R的頭結(jié)點(diǎn)，n中H到每一個(gè)基本塊B的傳遞函數(shù)為Fn,B，則在新區(qū)域R中的傳遞函數(shù)為：

• T2：刪除頂點(diǎn)

  如果有一個(gè)節(jié)點(diǎn)n具有唯一的前置節(jié)點(diǎn)m，則將m和n合并[2]。

如上圖所示：R是執(zhí)行T2規(guī)則后形成的新區(qū)域，對(duì)于n中的基本塊B，傳遞函數(shù)未改變（FR,B = Fn,B）；對(duì)于m中的基本塊：

為了構(gòu)建區(qū)域的層次結(jié)構(gòu)，我們需要識(shí)別循環(huán)。在可簡(jiǎn)化流圖中（這里，我們假設(shè)流程圖都是可簡(jiǎn)化的），任何兩個(gè)循環(huán)要么是不相交的，要么一個(gè)嵌套在另一個(gè)循環(huán)中。可簡(jiǎn)化流圖解析到循環(huán)層次結(jié)構(gòu)時(shí)，先將每個(gè)基本塊本身作為一個(gè)區(qū)域。我們將這些區(qū)域稱為葉區(qū)域。然后，從里到外排序循環(huán)，即從最里面的循環(huán)開始。處理循環(huán)時(shí)，我們通過(guò)兩個(gè)步驟將整個(gè)循環(huán)替換為一個(gè)節(jié)點(diǎn)：

1. 將循環(huán)L的主體（除報(bào)頭的循環(huán)邊外的所有節(jié)點(diǎn)和邊）替換為代表區(qū)域R的節(jié)點(diǎn)。L報(bào)頭的邊現(xiàn)在并入R的節(jié)點(diǎn)。循環(huán)L的任何出口的邊被R到同一目的節(jié)點(diǎn)的邊替換。但是，如果控制流邊是循環(huán)邊，那么它就會(huì)成為R上的循環(huán)邊。我們稱R為主體區(qū)域。
2. 構(gòu)造一個(gè)代表整個(gè)循環(huán)L的區(qū)域R'。我們可以把R'稱作循環(huán)區(qū)域。R和R'之間唯一的區(qū)別是，后者包括循環(huán)L的循環(huán)邊。換句話說(shuō)，當(dāng)R'替換流圖中的R時(shí)，我們所要做的就是將R的循環(huán)邊刪除[3]。

通過(guò)重復(fù)上述操作，我們可以逐漸將大的循環(huán)減少到單個(gè)節(jié)點(diǎn)。由于可簡(jiǎn)化流圖的循環(huán)是嵌套的或不相交的，因此循環(huán)區(qū)域的節(jié)點(diǎn)可以表示在此簡(jiǎn)化過(guò)程中構(gòu)建的一系列流圖中循環(huán)的所有節(jié)點(diǎn)。

最終，所有循環(huán)都被簡(jiǎn)化為單個(gè)節(jié)點(diǎn)。此時(shí)，流程圖有兩種情況：一是簡(jiǎn)化為單個(gè)節(jié)點(diǎn)；二是有幾個(gè)節(jié)點(diǎn)剩余，具有HO循環(huán)（即，簡(jiǎn)化的流圖是多個(gè)節(jié)點(diǎn)的非循環(huán)圖）。在前一種情況下，我們完成了區(qū)域?qū)哟谓Y(jié)構(gòu)的構(gòu)建，而在后一種情況下，我們?yōu)檎麄€(gè)流圖再次構(gòu)建出一個(gè)主體區(qū)域。

以下圖為例，圖(a)為控制流圖。此流程圖中有一個(gè)循環(huán)邊(B4->B2)。區(qū)域的層次結(jié)構(gòu)如圖(b)所示，共有8個(gè)區(qū)域：

• 區(qū)域R1-R5分別代表塊B1-B5的葉區(qū)域。每個(gè)塊也是其區(qū)域中的出口塊。
• 區(qū)域R6表示流圖中唯一循環(huán)的主體；它包含區(qū)域R2、R3和R4以及三個(gè)區(qū)域間控制流邊R2->R3、R2->R4和R3->R4。它有R3和R4兩個(gè)出口塊，因?yàn)樗鼈兌加胁话趨^(qū)域中的輸出邊。圖(c)顯示了R6簡(jiǎn)化為單個(gè)節(jié)點(diǎn)的流程圖。請(qǐng)注意，邊R3->R5和R4->R5都被邊R6->R5取代。因?yàn)閺腞3和R4兩個(gè)區(qū)域的輸出都將到達(dá)到達(dá)R5的輸入，因此簡(jiǎn)化后用一條邊代表之前兩條邊。
• 循環(huán)區(qū)域R7代表整個(gè)循環(huán)。它包括一個(gè)子區(qū)域R6和一個(gè)循環(huán)邊R4->R2。它還有兩個(gè)出口節(jié)點(diǎn)，也就是R3和R4。圖(d)顯示了整個(gè)循環(huán)簡(jiǎn)化到R7后的流程圖。
• 最后，主體區(qū)域R8是頂部區(qū)域。它包括三個(gè)區(qū)域，R1、R7、R5和三個(gè)區(qū)域間控制流邊R1->R2、R3->R5和R4->R5。當(dāng)我們將流程圖縮小到R8時(shí)，它將成為一個(gè)單一節(jié)點(diǎn)。由于其頭B1沒(méi)有循環(huán)邊，因此不需要將此主體區(qū)域減少為循環(huán)區(qū)域。

6、處理不可簡(jiǎn)化流圖

對(duì)于不可簡(jiǎn)化流圖，我們建議使用迭代數(shù)據(jù)流分析算法來(lái)進(jìn)行數(shù)據(jù)流分析。但是如果只是偶爾處理不可簡(jiǎn)化流圖的話，可以使用節(jié)點(diǎn)分裂方法進(jìn)行分析。

下面圖(a)就是一個(gè)典型的不可簡(jiǎn)化流圖。R2和R3之間存在循環(huán)，但R2和R3又都不占支配地位，導(dǎo)致我們無(wú)法進(jìn)一步解析該圖。我們選擇一些區(qū)域R（如R2），該區(qū)域R具有多個(gè)前置節(jié)點(diǎn)（R2的前置節(jié)點(diǎn)為R1和R3），并且不是整個(gè)流圖的頭。如果有k個(gè)前置節(jié)點(diǎn)，則制作流圖R的k個(gè)副本，并將每個(gè)前置節(jié)點(diǎn)連接到R的不同副本。這里需要注意，只有區(qū)域的頭才可能有該區(qū)域之外的前置節(jié)點(diǎn)。在識(shí)別新的循環(huán)邊并構(gòu)建其區(qū)域后，這種節(jié)點(diǎn)分裂使得區(qū)域數(shù)量減少。由此產(chǎn)生的流圖可能仍然不可簡(jiǎn)化，但通過(guò)分裂階與新的循環(huán)被識(shí)別并折疊到區(qū)域的階段交替使用，我們最終只剩下一個(gè)區(qū)域，即流圖已經(jīng)被約化。

圖(b)中所示的分裂將邊R2b->R3變成了循環(huán)邊，此時(shí)R3支配R2b,這兩個(gè)區(qū)域可以合并為一個(gè)新區(qū)域。由此產(chǎn)生的三個(gè)區(qū)域（R1、R2a和新區(qū)域）形成一個(gè)非循環(huán)圖。此時(shí)，我們可以將整個(gè)流程圖簡(jiǎn)化為單個(gè)區(qū)域。一般來(lái)說(shuō)，可能需要額外的拆分，在最壞的情況下，基本塊的總數(shù)可能會(huì)成為原始流圖中塊數(shù)的指數(shù)。

總結(jié)

本文簡(jiǎn)單介紹了一種解決數(shù)據(jù)流問(wèn)題的方法——區(qū)域分析。在區(qū)域分析過(guò)程中，我們首先為基本塊創(chuàng)建傳遞函數(shù)，然后通過(guò)組合、匯聚和閉包等操作總結(jié)加大區(qū)域的傳遞函數(shù)，最終構(gòu)造出整個(gè)數(shù)據(jù)流圖的傳遞函數(shù)。通過(guò)區(qū)域分析等數(shù)據(jù)分析的方法，可以發(fā)現(xiàn)更多的優(yōu)化機(jī)會(huì)，如將代碼從循環(huán)內(nèi)部移動(dòng)到循環(huán)外部、冗余的代碼刪除等。