編譯器設計 - 程式碼最佳化

---

---

最佳化是一種程式轉換技術，它試圖透過減少資源消耗（即CPU、記憶體）並提高速度來改進程式碼。

在最佳化中，高階通用程式設計結構被替換為非常高效的低階程式設計程式碼。程式碼最佳化過程必須遵循以下三個規則：

• 輸出程式碼絕不能以任何方式更改程式的含義。

• 最佳化應提高程式速度，如果可能，程式應減少資源需求。

• 最佳化本身應該很快，並且不應延遲整個編譯過程。

可以在編譯過程的各個階段努力最佳化程式碼。

• 首先，使用者可以更改/重新排列程式碼或使用更好的演算法來編寫程式碼。

• 在生成中間程式碼後，編譯器可以透過地址計算和改進迴圈來修改中間程式碼。

• 在生成目標機器程式碼時，編譯器可以利用記憶體層次結構和CPU暫存器。

最佳化大致可以分為兩種型別：機器無關和機器相關。

機器無關最佳化

在這種最佳化中，編譯器接收中間程式碼並轉換不涉及任何CPU暫存器和/或絕對記憶體位置的程式碼部分。例如：

do
{
   item = 10;
   value = value + item; 
} while(value<100);

此程式碼涉及識別符號item的重複賦值，如果我們這樣寫：

Item = 10;
do
{
   value = value + item; 
} while(value<100);

不僅可以節省CPU週期，而且可以在任何處理器上使用。

機器相關最佳化

機器相關最佳化是在生成目的碼之後進行的，此時程式碼根據目標機器架構進行轉換。它涉及CPU暫存器，並且可能具有絕對記憶體引用而不是相對引用。機器相關最佳化器努力最大限度地利用記憶體層次結構。

基本塊

原始碼通常包含許多指令，這些指令總是按順序執行，並被視為程式碼的基本塊。這些基本塊之間沒有任何跳轉語句，即，當執行第一條指令時，同一基本塊中的所有指令都將按其出現的順序執行，而不會丟失程式的流程控制。

程式可以將各種結構作為基本塊，例如IF-THEN-ELSE、SWITCH-CASE條件語句和迴圈，例如DO-WHILE、FOR和REPEAT-UNTIL等。

基本塊識別

我們可以使用以下演算法來查詢程式中的基本塊：

• 搜尋所有基本塊的頭部語句，從中開始一個基本塊。

  • 程式的第一條語句。
  • 任何分支（條件/無條件）的目標語句。
  • 任何分支語句之後的語句。

• 頭部語句及其後的語句構成一個基本塊。

• 基本塊不包含任何其他基本塊的頭部語句。

從程式碼生成和最佳化的角度來看，基本塊都是重要的概念。

基本塊在識別變數方面起著重要作用，這些變數在單個基本塊中被使用多次。如果任何變數被使用多次，則分配給該變數的暫存器記憶體無需清空，除非塊執行完畢。

控制流圖

程式中的基本塊可以用控制流圖來表示。控制流圖描述了程式控制如何在塊之間傳遞。它是一個有用的工具，可以透過幫助定位程式中任何不需要的迴圈來幫助最佳化。

迴圈最佳化

大多數程式在系統中作為迴圈執行。為了節省CPU週期和記憶體，最佳化迴圈是必要的。可以使用以下技術最佳化迴圈：

• 不變程式碼：位於迴圈中並在每次迭代中計算相同值的程式碼片段稱為迴圈不變程式碼。可以透過將其儲存為僅計算一次而不是每次迭代來將其移出迴圈。

• 歸納分析：如果變數的值在迴圈內透過迴圈不變值更改，則該變數稱為歸納變數。

• 強度削弱：有些表示式會消耗更多的CPU週期、時間和記憶體。這些表示式應該用更便宜的表示式替換，而不會影響表示式的輸出。例如，乘法 (x * 2) 比 (x << 1) 在CPU週期方面更昂貴，但產生相同的結果。

死程式碼消除

死程式碼是一個或多個程式碼語句，這些語句：

• 要麼從未執行或無法訪問，
• 要麼如果執行，則其輸出從未使用。

因此，死程式碼在任何程式操作中都不起作用，因此可以簡單地將其消除。

部分死程式碼

有些程式碼語句的計算值僅在某些情況下使用，即有時使用這些值，有時不使用。此類程式碼稱為部分死程式碼。

上面的控制流圖描述了一段程式，其中變數“a”用於賦值表示式“x * y”的輸出。讓我們假設分配給“a”的值在迴圈內從未使用過。在控制離開迴圈後立即，將變數“z”的值賦給“a”，這將在程式的後面使用。我們在此得出結論， “a”的賦值程式碼在任何地方都沒有使用，因此它有資格被消除。

同樣，上圖顯示條件語句始終為假，這意味著在真情況下編寫的程式碼將永遠不會執行，因此可以將其刪除。

部分冗餘

冗餘表示式在並行路徑中被計算多次，而運算元沒有變化。而部分冗餘表示式在路徑中被計算多次，而運算元沒有變化。例如：

迴圈不變程式碼是部分冗餘的，可以使用程式碼移動技術消除。

部分冗餘程式碼的另一個示例可以是：

If (condition)
{
   a = y OP z;
}
else
{
   ...
}
c = y OP z;

我們假設運算元（y 和 z）的值從變數a賦值給變數c沒有改變。在這裡，如果條件語句為真，則 y OP z 計算兩次，否則計算一次。程式碼移動可以用來消除這種冗餘，如下所示：

If (condition)
{
   ...
   tmp = y OP z;
   a = tmp;
   ...
}
else
{
   ...
   tmp = y OP z;
}
c = tmp;

在這裡，無論條件是真還是假； y OP z 只應計算一次。