畢昇編譯器優化:Lazy Code Motion

語言: CN / TW / HK
摘要:本文中,我們將介紹通過程式碼移動(插入)的方式消除冗餘計算的一個典型方法。

本文分享自華為雲社群《編譯器優化那些事兒(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. 為每個指向擁有多個前置的基本塊新增一個基本塊(不僅僅是在 臨界邊 上)。
  2. 為了保持演算法簡單,將每個語句視為其自己的基本塊,並將指令的放置限制在基本塊的開頭。

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

1、演算法

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

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

程式流程圖如下:

演算法步驟:

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

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

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),後續的點類似。

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

根據公式,最早可插入的點的集合是 可預期點的(Anticipated)集合(圖中紅色1部分) 減去 將可用點的(Will-be-Available)集合,得到圖中標記的點。

目前為止我們已經找了一種通用的消除重複計算的方法,就是在上圖中標註 Earliest 的點插入表示式 t=b+c, 然後在後面所有用到 b+c 的地方替換成 t,但這樣做會帶來一個問題,就是暫存器的生存期會很長。通過下一小節引入的定義,我們可以解決這個暫存器生存期的問題。

1.3 延緩表示式(Postponable)

An expression is said to be postponable at program point if all paths leading to have seen earliest placement of but not a subsequent use.

延緩表示式(Postponable)的分析方向為前向(forward)。

延遲建立冗餘計算表示式可以減少暫存器壓力:從公式看,Postponable點一定是在 Earliest 點的後面的,更接近表示式要被替換的地方,就是說,從表示式第一次被計算的點(結果在暫存器)到該結果被複用的點距離更近。

對於該圖的講解,可以參考 YouTube2 中的講解。

接下來可以通過以下公式進行最晚插入點(Latest)的計算:

  1. 先在 Earliest 與 postpobable 集合的並集位置放置表示式 e 。
  2. 對上一步的點進行篩選,需要滿足:表示式 e 在 b 點(隨後的基本塊)被Use 或 它不是上一步點的後繼。

這裡插入的點(圖中黃色方塊)是增加的合成塊,是出於安全性的考慮。

1.4 已用表示式(Used Expressions)

An expression is said to be used at program point if there exists a path leading from that uses the expression before the operands are reevaluated.

已用表示式(Used Expressions)的分析方向為後向(backword)。

如圖所示,從下往上看,未使用的點標記為0,直到使用的地方被標記為1。

引入這個定義主要是為了消除當前塊之外未使用的臨時變數賦值,計算方式: Used.out: sets of used (live) expressions at exit of b.

2、最終的解決方案

對所有的基本塊/表示式 b,如果表示式屬於最晚插入點的集合與已用點位置的交集,

則在基本塊b的開頭,先建立 t = a + b,然後把所有的 x+y 替換為 t。

目前為止演算法的介紹部分就已經全部講完了,但是有些定義還是比較模糊,需要結合程式碼才能講清楚, 大家可以翻看LLVM 原始碼3中關於該程式碼的具體實現: MachineCSE 類與 NaryReassociatePass 等類的實現。

參考

1. https://dl.acm.org/doi/abs/10.1145/143095.143136

2. https://www.youtube.com/watch?v=3s4oST3oZzQ&t=20s

3. https://github.com/llvm/llvm-project

 

 

點選關注,第一時間瞭解華為雲新鮮技術~