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

1、概念介紹

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

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

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

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

但是有一些優(yōu)化必須通過檢查整個程序來實現(xiàn)。如下圖所示：

從圖中可以看出：d3對c的初始化賦值是無用的，x的值恒定為6，d6可以簡化為：c = 7。

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

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

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

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

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

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

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

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

然而，圖(d)中節(jié)點B3、B4以及邊B3->B4組成的子圖（虛線部分）不形成區(qū)域，因為控制流既可以通過節(jié)點B3處進(jìn)入子圖，也可以通過節(jié)點B4進(jìn)入子圖。B3和B4都無法做到完全支配另一個，不符合區(qū)域的第一個條件。即使我們選擇B3作為頭h，也不符合區(qū)域的第二個條件。因為B1可以不經(jīng)過B3，沿著邊B1->B4到達(dá)B4，根據(jù)區(qū)域的第二個條件，B1應(yīng)該在該“區(qū)域”中，但這顯然不正確。

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

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

3、傳遞函數(shù)

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

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

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

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

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

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

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

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

4.1 組合（composition）

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

4.2 匯聚（meet）

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

4.3 閉包（closure）

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

5、處理可簡化流圖

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

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

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

• T2：刪除頂點

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

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

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

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

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

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

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

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

6、處理不可簡化流圖

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

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

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

總結(jié)

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