本文章是由機器翻譯。

編譯器

每個程式師應該知道的編譯器最優化,第 2 部分

Hadi Brais

下載代碼示例

歡迎來到我的編譯器優化的系列的第二部分。第一篇文章 (msdn.microsoft.com/magazine/dn904673),我討論了函數內聯、 迴圈展開、 迴圈不變式代碼議案、 自動向量化和 COMDAT 優化。在這第二篇文章中,我要去看看兩個其他的優化 — — 註冊分配與指令調度。一如往常,我會針對 Visual c + + 編譯器,淺的東西在 Microsoft.NET 框架的工作。我會使用Visual Studio2013年才能編譯的代碼。我們開始吧。

寄存器分配

寄存器分配是分配一組可用的寄存器變數,以便他們不需要在記憶體中分配的過程。這一過程通常是在整個函數的級別執行的。然而,尤其是當連結時間代碼生成 (/ ltcg 生成模式) 是啟用,進程可以執行跨職能,可能會導致更有效的分配。(在本節中,所有變數都是自動 — — 那些其存留期決意語法上 — — 除非有其它說明。)

寄存器分配是一個特別重要的優化。要理解這一點,讓我們看看花多少來訪問記憶體的不同級別。訪問一個登記冊需要少於一個處理器週期。訪問緩存是有點慢,從少到數萬週期。訪問 (遠端) 的 DRAM 記憶體是更為緩慢。最後,訪問硬碟非常緩慢,可以把數以百萬計的週期 !此外,記憶體訪問增加交通到共用快取服務器緩存和主儲存體。寄存器分配利用可用的寄存器,盡可能減少了記憶體訪問的數量。

編譯器將嘗試理想的情況下分配給每個變數,寄存器,直到執行涉及該變數的所有指令。如果這不是可能的這是常見的原因,我將討論不久,一個或多個變數必須灑到記憶體中,所以他們必須載入和存儲頻繁。寄存器壓力是指登記冊未能如期濺入的寄存器的數目。更大的寄存器壓力意味著更多的記憶體訪問,和更多的記憶體訪問可以減慢不僅程式本身,但也使整個系統對爬網。

現代 x86 處理器提供下列寄存器由編譯器分配:八個 32 位通用寄存器、 八個 80 位浮點寄存器和 8 個 128 位向量寄存器。所有x64處理器都提供 16 個 64 位通用寄存器、 八個 80 位浮點寄存器和至少 16 向量寄存器 — — 每個至少 128 位寬。現代的 32 位 ARM 處理器提供 15 32 位通用寄存器和 32 個 64 位浮點寄存器。所有的 64 位 ARM 處理器提供 31 64 位通用寄存器,32 個 128 位浮點寄存器和 16 128 位向量寄存器 (霓虹燈)。所有這些都是可用的寄存器分配 (和您還可以添加到清單中提供的圖形卡的選民登記冊)。當一個本地變數不能分配給任何可用的寄存器時,它必須在堆疊上分配。發生這種情況幾乎每個函數中由於種種原因,我將討論。考慮中的程式圖 1。這個程式不會做任何有意義的但它作為一個好的例子來證明寄存器分配。

圖 1 寄存器分配示常式序

#include <stdio.h>
int main() {
  int n = 0, m;
  scanf_s("%d", &m);
  for (int i = 0; i < m; ++i){
    n += i;
  }
  for (int j = 0; j < m; ++j){
    n += j;
  }
  printf("%d", n);
  return 0;
}

它分配給變數指定可用的寄存器之前,編譯器首先分析了所有聲明的變數在函數內 (或跨職能時 /LTCG) 使用以確定所設置的變數是生活的同時,並估計每個變數被訪問的次數。從不同的兩個變數可以分配同一個寄存器。如果有一些變數相同的一組沒有適用于選民登記冊,這些變數必須外溢。編譯器將嘗試選擇的最少訪問變數外溢時,在試圖儘量減少記憶體訪問的總數。這是一般的主意。然而,有很多特殊的情況下,有可能找到一個更好的分配。現代編譯器所能想出一個好的分配,但不是最優的一個。它是一個凡人做得更好,雖然非常,非常難。

為此,我會編譯中的程式圖 1 與優化已啟用,看看如何編譯器將分配到寄存器的本地變數。有四個變數來分配:n、 m、 i 和 j。 我將假定目標在這種情況下是 x86 平臺。通過檢查生成的程式集代碼 (/ FA),我注意到變數 n 已撥給 ESI 寄存器、 變數 m 已撥給 ECX,和 i 和 j 都被分配給 EAX。請注意如何編譯器巧妙地重用 EAX 兩個變數,因為它們的壽命並不相交。此外注意到編譯器已預留為 m 堆疊上的空間,因為它的位址採取。在x64平臺上,變數 n 將撥給該登記冊的電子資料交換、 變數 m 將撥給 EDX,到 EAX,i 和 j 到 EBX。出於某種原因,編譯器不分配第一和 j 向同一登記冊這一次。

那是最優的分配嗎?號 問題是在使用 ESI 和電子資料交換。這些寄存器是被呼叫者保存的寄存器,所調用的函數必須確保這些寄存器值持有出口處的含義都一樣在入口處。這就是為什麼編譯器不得不發出指示在入口處的功能推送到堆疊上的 ESI/EDI 與出口處的另一條指令從堆疊彈出他們。編譯器可能已經避免這兩個平臺上使用調用方保存的寄存器,如 EDX。有時可以通過函數內聯減輕這種缺陷在寄存器分配演算法。許多其他的優化可以使代碼服從更有效率的寄存器分配,如死代碼消除、 公共子運算式消除和指令調度。

這是實際上常見變數具有不相交的存留期,因此分配給所有同一個寄存器是非常經濟。但如果你運行寄存器以容納任何人嗎?你必須把它們灑。然而,你可以做到以巧妙的方式。你把他們到堆疊上的同一位置都灑出來。這種優化稱為堆疊包裝,它由 Visual c + + 支援。堆疊包裝減少了堆疊幀的大小,並可能提高的資料緩存命中的比率,更好的性能。

不幸的是,事情並非那麼簡單。從理論的角度來看,(近) 優化寄存器,可以實現分配。然而,實際上,有許多的原因,為什麼這可能不是可能:

  • 指定可用的寄存器 (如前所述) 的 x 86 和x64平臺和任何其他現代的平臺 (如 ARM) 不能任意使用。有複雜的限制。每條指令都有哪些可以作為運算元使用寄存器的限制。因此,如果您想要使用的指令,您必須使用允許的寄存器傳遞給所需的運算元。此外,一些指令的結果存儲在預定登記冊,其值由指令會波動。可能有不同的執行同樣的計算,但可讓您執行效率更高的寄存器分配的指令序列。問題的指令選擇指令調度、 寄存器分配得不得了糾纏。
  • 並不是所有的變數為基元類型。它並非罕見,具有自動結構和陣列。這樣的變數不能直接申請寄存器分配。然而,他們可以分離到寄存器分配。當前編譯器還不是很好。
  • 一個函數的調用約定規定,對於一些別人沒有資格獲得不論可用性的寄存器分配在呈現時固定的分配。更多關於這個問題有點晚。此外,保存調用方和被呼叫者保存的寄存器的概念讓情況更加撲朔迷離。
  • 如果採取了變數的位址,該變數更好地將存儲在有一個位址的位置。一份登記冊沒有位址,所以它必須存儲在記憶體中是否可用。

所有這一切都似乎給你當前編譯器很糟糕,寄存器分配。然而,他們相當不錯,它變得更好,非常緩慢。你也可以想像自己寫彙編代碼思維則是對這一切嗎?

你可以説明編譯器可能會找到一個更好的分配通過啟用 /LTCG,當基於 x86 體系結構。如果您指定 /GL 編譯器開關,生成的 OBJ 檔將包含 C 中間語言 (CIL) 代碼,而不是程式集代碼。函數的調用約定不列入 CIL 代碼。如果某一特定功能並不定義為從輸出可執行檔匯出,編譯器可以違反其調用的公約,以提高其性能。這是可能的因為它可以識別的函數的所有調用網站。Visual c + + 並採取讓函數的所有參數寄存器分配無論調用約定有資格這樣做的優點。即使註冊分配得不到改善,編譯器將嘗試重新排列參數更經濟的對齊方式和甚至刪除未使用的參數。無 /GL 開關,生成的 OBJ 檔包含二進位代碼調用約定已經被考慮。如果程式集 OBJ 檔在 CIL OBJ 檔中有對函數的調用網站,或如果函數的位址攜帶到任何地方或如果它是虛擬,編譯器可以不再進行優化,其調用約定。/LTCG,預設情況下,所有的函數和方法沒有外部連結,因此編譯器無法應用這種技術。然而,如果 OBJ 檔中的函數已顯式定義與內在的聯繫,編譯器可以應用這種技術,但僅在 OBJ 檔內。這種技術,提到的檔作為自訂調用約定,是重要的當基於 x86 體系結構因為的預設調用約定,即 >__cdecl 效率並不高。另一方面,__fastcall 調用約定的x64體系結構是非常有效的因為前四個參數都通過寄存器傳遞。出於此原因,只有當面向 x86 執行自訂調用約定。

請注意即使啟用了 /LTCG,不能違背匯出的函數或方法的調用約定,因為它是不可能的編譯器可以找到所有的調用網站,正如前面所提到的所有案件。

寄存器分配的有效性取決於對精度的估計數目對變數的訪問。大多數函數包含條件陳述式,危及這些估計的準確性。按設定檔優化可以用來微調這些估計數。

當啟用了 /LTCG 和目標平臺是x64時,編譯器執行過程間的寄存器分配。這意味著它將考慮鏈函數內聲明的變數,並試圖找到更好的分配取決於每個函數中的代碼所施加的限制。否則,編譯器執行全域寄存器分配的每個函數均單獨處理 ("全球化"在這裡指的整體功能)。

C 和 c + + 提供的註冊紀錄冊的關鍵字,使程式師能夠提供關於哪些變數來存儲在寄存器中編譯器提示。事實上,C 的第一個版本介紹了此關鍵字,它當時有用 (大約 1972) 因為沒人知道如何有效地執行寄存器分配。(四、 FORTRAN 編譯器由 IBM 公司開發 在 60 年代末為 S/360 系列雖然可以執行簡單的移位暫存器分配。最 S/360 模型提供 16 個 32 位通用寄存器和四個 64 位浮點寄存器 !)此外,與很多其他功能的 C,一樣註冊關鍵字可以輕鬆地編寫 C 語言編譯器。近十年後,c + + 創建和它提供的註冊關鍵字,因為 C 被認為是 c + + 的一個子集。(不幸的是,有許多細微的差別。)自 80 年代初,許多有效的寄存器的分配演算法已經得到執行,所以存在的關鍵字創造了很多混亂到這一天。大多數生產語言創建了然後不提供 (包括 C# 和Visual Basic) 的關鍵字。因為 C + + 11,而不是最新版本的 C,C11 已棄用此關鍵字。此關鍵字應僅用於寫作的基準。Visual c + + 編譯器並尊重這一關鍵字,如果可能的話。C 不允許採取寄存器變數的位址。C + +,但是,允許它但是然後編譯器必須將變數存儲在可定址的位置,而不是在一個登記冊,違反其手動指定的存儲類。

當面向 CLR,編譯器便要發出模特堆疊式機器的通用中間語言 (CIL) 代碼。在這種情況下,編譯器不會執行寄存器分配 (雖然如果發出的代碼的一些是本機程式,註冊將它,當然在分配) 和推遲運行時由即時 (JIT) 編譯器 (或 Visual c + + 後端在.NET 本地編譯的情況下) 執行。RyuJIT,JIT 編譯器和.NET framework 4.5.1 船,後來,實現相當不錯寄存器分配演算法。

指令調度

寄存器分配和指令調度是由編譯器執行之前它發出該二進位檔案的最後一個優化。

所有但最簡單的指令都執行在多個階段,在每個階段由特定單位的處理器。能夠利用所有這些單位盡可能多地,處理器問題這樣不同的指令在同一時間在不同階段執行多個指令以流水線的方式。這可以顯著提高性能。然而,如果出於某種原因,這些指令之一不是準備執行,整個管道的攤位。這可能是由於很多原因,包括等待另一條指令要提交其結果 ; 等待資料來從記憶體或磁片 ; 或等待 I/O 操作完成。

指令調度是一種技術,可以減輕這一問題。指令調度的兩個種類:

  • 基於編譯器:編譯器分析函數的指令,以確定那些可能停滯的管道的指令。然後,它試圖尋找不同指令的順序,儘量減少成本的同時保留程式正確性的預期攤位。這就被所謂指令重新排序。
  • 基於硬體:大多數的現代 x 86,x64和 ARM 處理器是可以展望指令 (micro-ops,必須準確) 流和發出這些指令的運算元,用於執行所需功能單元。這稱為順序出 (亂或 3OE) 或動態執行。其結果是是不同于原始訂單正在執行的程式。

還有其他原因,可能會導致編譯器重新排序某些指令。例如,編譯器可能重新排序嵌套的迴圈,從而使代碼具有更好的引用位址 (這種優化稱為環交匯處)。另一個例子是寄存器的降低成本溢出進行說明,使用相同的值,從記憶體連續載入,以便一次載入的值。然而,另一個例子是,減少資料和指令緩存錯過。

作為一個程式師,你不需要知道如何編譯器或處理器執行指令調度。然而,你應該意識到這種技術以及如何處理它們的後果。

雖然指令調度保留大多數程式的正確性,它可能會產生一些非直觀和令人驚訝的結果。圖 2 舉例說明在哪裡指令調度使編譯器將發出不正確的代碼。若要查看此,編譯該程式作為 C 代碼 (/ TC) 在發佈模式下。你可以將目標平臺設置為 x86 或x64。因為你要檢查生成的彙編代碼,指定 /FA,所以編譯器將發出清單的程式集。

圖 2 指令調度的示常式序

#include <stdio.h>
#include <time.h>
__declspec(noinline) int compute(){
  /* Some code here */
  return 0;
}
int main() {
  time_t t0 = clock();
  /* Target location */
  int result = compute();
  time_t t1 = clock(); /* Function call to be moved */
  printf("Result (%d) computed in %lld ticks.", result, t1 - t0);
  return 0;
}

在這個程式中,我想要測量計算函數的執行時間。要做到這一點,我通常封裝通過時鐘計時功能調用對函數的調用。然後,通過計算時鐘的值的差異,我得到的函數執行所花費的時間的估計。請注意,此代碼的目的不是展示你最好的方式來衡量性能的代碼的某些部分,但證明指令調度的危害。

因為這是 C 代碼,程式是非常簡單的因為它很容易理解生成的程式集代碼。通過查看程式集代碼和側重于調用指令,您會注意到時鐘功能第二次調用之前計算函式呼叫 (已被移動到"目標位置"),使測量完全錯了。

請注意該重新排序不違反徵收的標準一致的實現,所以它是法律的最低要求。

但是,編譯器為什麼那樣做?編譯器認為第二個調用時鐘並不取決於調用來計算 (事實上,給了編譯器,這些功能不會影響彼此根本)。此外,在第一次調用後,時鐘,它亦可能指令緩存包含一些該函數的指令和資料緩存中包含一些這些指令所需的資料。調用計算可能會導致這些指令和資料將被覆蓋,所以編譯器進行相應重新排序代碼。

Visual c + + 編譯器不提供一個開關來關閉指令調度功能,同時保留所有其他優化。此外,這一問題可能會導致動態執行,如果計算函數內聯。取決於如何執行計算函數和一個處理器能看多遠的前方,3OE 處理器可能會決定開始執行第二個調用之前計算功能時鐘完成。只是隨著編譯器,大部分處理器不讓你關閉動態執行。但為了公平起見,是不太可能,因為動態執行將會發生此問題。你怎麼能告訴是否它發生了,不管怎麼說?

Visual c + + 編譯器是實際上非常小心,當執行這種優化。它是如此認真,有許多的事情,防止重新排序的指令 (如調用指令)。我已經注意到以下情況導致編譯器不會移動到特定的位置 (目標位置) 的時鐘函式呼叫:

  • 從任何函式呼叫的位置和目標位置之間正在調用的函數中調用導入的函數。這段代碼所示,從計算函式呼叫任何導入的函數使編譯器不移動時鐘第二個調用:
__declspec(noinline) int compute(){
  int x;
  scanf_s("%d", &x); /* Calling an imported function */
  return x;
}
  • 調用導入的函式呼叫來計算和時鐘第二個調用之間:
int main() {
  time_t t0 = clock();
  int result = compute();
  printf("%d", result); /* Calling an imported function */
  time_t t1 = clock();
  printf("Result (%d) computed in %lld.", result, t1 - t0);
  return 0;
}
  • 從被調用函式呼叫的位置和目標位置之間的函數中的任何訪問任何全域變數或靜態變數。這個擁有該變數是否正在讀取或寫入。下面的顯示從計算函數訪問全域變數會導致編譯器不會移動時鐘第二個調用:
int x = 0;
__declspec(noinline) int compute(){
  return x;
}
  • 將 t1 標記為易失性。

還有其他一些防止編譯器指令重新排序的情況。它是所有關于 c + + 的 — — 如果說編譯器可以變換的一個程式,它不包含的規則未定義操作無論如何它喜歡,只要保證代碼的可觀察行為保持不變。Visual c + + 不僅堅持這一規則,而且也是更加保守,以減少對代碼進行編譯所需時間。導入的函數可能會引起副作用。 庫 I/O 函數和訪問 volatile 變數引起的副作用。

易揮發,限制和 /favor

排位賽與 volatile 關鍵字的變數會影響寄存器分配演算法和指令重新排序。第一,該變數不會分配給任何註冊紀錄冊。(大多數指令要求一些存儲在寄存器中,這意味著該變數將載入進寄存器,而只是執行一些使用該變數的說明其運算元)。那就是,讀取或寫入該變數總是會導致記憶體訪問。第二,寫入 volatile 變數具有釋放語義,意味著所有語法上發生之前寫給該變數的記憶體訪問前它會發生。第三,從 volatile 變數中的讀取已獲取語義,意味著在它以後會發生所有語法上發生後讀取從該變數的記憶體訪問。但這裡有一個問題:這些重新排序的保障只能由指定 /volatile:ms 開關提供。與此相反的是,/volatile:iso 開關告訴編譯器要堅持語言標準,不能提供任何此類保證通過此關鍵字。手臂,/volatile:iso,預設情況下將生效。其他體系結構中,預設值為 /volatile:ms。 在 C + + 11 前, /volatile:ms 開關是有用的因為標準沒有提供什麼對於多執行緒程式。 然而,從開始與 C11 / C + + 11,/volatile:ms 的使用使您的代碼不是可攜性和強烈建議不要和您應改用原子。如果您的程式在 /volatile:iso 下正常工作,它將正常工作下 /volatile:ms,它是值得的。 更重要的是,然而,如果它能否正常工作下 /volatile:ms 它可能無法正常工作下 /volatile:iso 因為前者比後者更強的保障。

/Volatile:ms 開關實現獲取和釋放的語義。它並不足以維持這些在編譯時 ; 編譯器可能會 (具體取決於目標平臺) 發出額外的指令 (如 mfence 和 xchg) 告訴 3OE 處理器執行代碼時保持這些語義。因此,volatile 變數會降低性能,不只是因為變數不會緩存在寄存器中,而也被排放的其他說明。

Volatile 關鍵字根據 C# 語言規範的語義是類似于那些提供由 Visual c + + 編譯器開關指定的 /volatile:ms。然而還有差異。Volatile 關鍵字在 C# 中實現按順序一致 (SC) Acq/Rel 語義,而 C/c + + 不穩定在 /volatile:ms 下實現純 Acq/Rel 語義。記住 /volatile:iso 下揮發的 C/c + + 有沒有 Acq/Rel 語義。有關詳情已超出了本文的範圍。一般情況下,記憶體圍欄可能會阻止編譯器跨他們執行許多優化。

它是非常重要的是要明白是否編譯器沒有提供這種保障放在第一位,那麼任何相應的擔保提供的處理器是自動作廢。

__Restrict 關鍵字 (或限制) 也會影響寄存器分配和指令調度的有效性。然而,與揮發性,限制可以大大提高這些優化。用在一個範圍內此關鍵字標記的指標變數表示沒有其他任何變數指向相同的物件,創建範圍之外,並用來對其進行修改。此關鍵字也可能會使編譯器能夠執行許多優化指標,滿懷信心地包括自動向量化和迴圈優化,它減少了生成的代碼大小。可以限制關鍵字視為最高機密、 高科技、 反反-優化的武器。值得一整條本身 ; 因此,它將不討論在這裡。

如果一個變數用這兩種易失性標記和 __restrict,volatile 關鍵字將優先決策有關如何優化的代碼時。事實上,編譯器可以完全忽略限制,但必須尊重易失性。

/Favor 開關可能會使編譯器執行指令調度,調到指定體系結構。因為編譯器可能有能力不會排放檢查是否支援特定功能的支援,是處理器的指令,它還可以減少生成的代碼大小。這輪導致改進的指令緩存命中率及更好的性能。預設值是 /favor:blend,跨 x 86 和x64處理器英特爾公司從生成的代碼具有良好的性能 和 AMD。

接近尾聲了

我討論了由 Visual c + + 編譯器執行的兩個重要的優化:寄存器分配演算法和指令調度。

寄存器分配是由編譯器執行,因為比訪問甚至緩存快得多訪問寄存器的最重要的優化。指令調度也是重要的。然而,最近的處理器具有出色的動態執行能力,使指令調度不那麼重要,比以前。儘管如此,編譯器可以看到所有指令的函數,不管它有多大,而處理器只能都看到有限的數目的說明。此外,無序執行硬體是相當耗電,因為它總是在起作用,只要工作的核心。此外,x 86 和x64處理器執行比 C11 記憶體模型 / C + + 11 記憶體模型,並防止某些指令重新排列,可以提高性能。因此,基於編譯器指令調度仍然是極其重要的權力有限的設備。

幾個關鍵字和編譯器開關可以影響的性能或消極或積極,所以請確保適當地使用,以確保您的代碼盡可能快地運行,並生成正確的結果。還有很多更多的優化,以談論 — — 呆在調諧 !


Hadi Bras 是一個博士學位 印度研究所的技術德里 (駕禦),研究的下一代存儲技術的編譯器優化的學者。他花了他大部分的時間編寫的代碼在 C / C + + / C# 和挖深到 CLR 和 CRT。他的博客 hadibrais.wordpress.com。聯繫到他在 hadi.b@live.com

由於下面的技術專家,檢討這篇文章:Jim霍格 (Microsoft Visual c + + 團隊)