畢昇編譯器優化：Lazy Code Motion

摘要：本文中，我們將介紹通過程式碼移動（插入）的方式消除冗餘計算的一個典型方法。

本文分享自華為雲社區《編譯器優化那些事兒（3）：Lazy Code Motion》，作者：畢昇小助手。

導語

本文中，我們將介紹通過程式碼移動（插入）的方式消除冗餘計算的一個典型方法。

下圖給出的簡要程式流圖中， ①是我們想要優化的程式碼，②和③是優化後的程式碼，讓我們先思考下面幾個問題：

②和③哪個優化效果更好一點？

③ 更好一點，相比 ② 暫存器生存周期更短

③這種情況，在 p 點直接插入 t=b+c 會帶來安全或性能問題嗎? 會改變程式的行為嗎?

這裡不會引入冗餘的計算，也沒有改變程式行為。但如果 p 是下文介紹的非預期的點，我們就需要使用在臨界邊上增加合成塊的方式避免這個問題了。

能否由編譯器來完成一個演算法，找到一個通用的、尋找到合適的插入點的方法以消除冗餘計算？

這是本文要介紹的內容，我們會在下面演算法章節引入四個定義，為程式在各個點上打上標籤，通過這些點的集合之間的運算，得到插入點的集合。

0.1 開始之前

介紹演算法之前，我們來看三個在寫應用層程式碼時可能會遇到的問題。

（1）我們可以把計算移動到不會重複計算的路徑嗎？

答案已在圖中給出：

左邊例子是可以的。這也是下文演算法要找的情景。當然實際應用程式中會更複雜，以致我們不能明顯看出或不經意間引入冗餘的計算，比如《Lazy code motion》1 里給出的例子。
中間不可以，因為 b 被重新定義了，所以 a = b + c 不是冗餘計算了。
右邊不可以，因為 a = b + c 可能一次也沒執行，移動到循環前可能會改變程式的行為。

（2）左圖到右圖的變化有優化效果嗎

有的，這也是下面演算法中要尋找的情景，左邊的路徑消除了一次冗餘計算，右邊為了保持程式正確性插入了一個計算，但並沒有引入冗餘的計算，所以總體是有優化的.

（3）下圖中，能否在 block d 的父項 p 上插入表達式 t=b+c：

不能，因為插入不能改變程式的行為: 這裡 t=b+c 可能難以看出問題，但如果表達式換成 b/c (c==0) 或 b^c 就能明顯的看到造成了運行問題或性能問題。

解決方法：可在臨界邊(Critical Edge)上增加合成塊(Synthetic Block)。

0.2 臨界邊(Critical Edge)的定義

定義：源基本塊有多個後繼，目標基本塊有多個前驅，連接它們的邊就叫臨界邊(Critical Edge)。

臨界邊如上圖紅色部分所示。

打破臨界邊(Critical Edge)的辦法：增加合成塊(Synthetic Block)

步驟：

為每個指向擁有多個前置的基本塊添加一個基本塊(不僅僅是在臨界邊上)。
為了保持演算法簡單，將每個語句視為其自己的基本塊，並將指令的放置限制在基本塊的開頭。

上圖中我們插入了兩個合成塊，其中一個是多餘的，但不用擔心，我們可以在最後消除它。

1、演算法

上文中，我們介紹了一個可以放心插入表達式而不會引入安全問題的方法，下面我們將正式介紹導語中提到的演算法。

部分冗餘消除演算法要儘可能延遲計算，這也是標題中 lazy 的含義。

程式流程圖如下：

演算法步驟：

首先計算預期表達式（Anticipated）集合
計算將可用的表達式（Will-be-Available）集合
從 AVAIL 和 ANT ，我們為每個表達式計算出最早的插入位置（Earliest）集合，這最大限度地消除了冗餘，但可能會增大暫存器生存期
再計算延遲表達式（Postponable）集合
經過上面的計算，引入 Latest 的定義，計算最晚插入的點的集合，實現與 earliest 相同數量的冗餘消除，但縮短了保存表達式值的暫存器的生存期
計算使用表達式(Used)
計算最後的插入位置的集合，替換冗餘表達式

我們會以下圖為例，說明整個計算過程。根據以往的經驗，下面給出的幾個公式，必須結合圖例去理解，文字無法闡述清楚準確定義。

1.1 預期表達式（Anticipated）

Anticipated：An expression is said to be anticipated at program point if all paths leading from eventually computes (from the values of 』s operands that are available at ).

預期表達式（Anticipated）的分析方向為後向(backword)。

圖示說明：

1 表示該點是可預期的（Anticipated），0 表示不是。該演算法的方向是後向（backword）的，對應到圖中，我們要從 p1 開始判斷：對於表達式 b+c 而言，p1 是非預期的，因為到該點為止，沒有 b+c 的計算，繼續往上，看到了 b+c 的計算，所以 p2 點是可預期的（Anticipated），這情況一直持續到 p3，到 p4，由於該點看到了 b=1，b 被重新定義了，就是公式里被 Kill 的表達式，所以 p4 點不是可預期的（Anticipated）點。

1.2 將可用的表達式（Will-be-Available）

Will-be-available：An expression is said to be will-be-available at program point if it is anticipated and not subsequently killed along all paths reaching .

將可用的表達式（Will-be-Available）的分析方向為前向(forward)。

圖中綠色的 1 表示表達式 b+c 該點是將可用的（Will-be-Available），0 表示不是。該演算法方向是前向的，就是分析時，我們從 p4 開始看，根據公式的定義，該點不是可預期的（Anticipated），也沒有計算表達式 b+c，所以該點不是將可用的（Will-be-Available），p3 雖然是可預期的（Anticipated），但因為 b=1 ，所以 p3 點對表達式 b+c 來說是 Ekillp ，所以該點仍不是將可用的，p5 點是可預期的（Anticipated），且該點沒有 kill 的操作，該點是將可用的（Will-be-Available），後續的點類似。

接下來可以通過以下公式進行最早插入點的計算：