我承認這個問題的答案可能是“一些非常特殊的魔法”，但我對我在這里觀察到的情況感到有點震驚。我想知道是否有人了解這些型別的優化是如何作業的。我發現編譯器設計很有趣，我真的無法想象它是如何作業的。我確定答案在 clang 源代碼中的某處，但我什至不知道我會去哪里找。
我是大學班級的助教，最近有人要求我幫忙做一道簡單的家庭作業題。這讓我走上了一條有趣的道路......
問題很簡單：在 x86_64 匯編中，撰寫一個給定（正）整數 n 回傳的函式1^2 2^2 3^2 ... n^2。
我決定嘗試一下，在幫助他們用 x86_64 匯編撰寫這個之后，我有一臺 M1 macbook，決定看看我是否可以在 arm64 匯編中創建一個不錯的解決方案。我想出了相對簡單直接的解決方案：
_sum_squares:
mov x1, x0 ; Do multiplication from x1
mov x0, xzr ; Clear x0
Lloop:
; x0 <-- (x1 * x1) x0
madd x0, x1, x1, x0
; Loop until x1 == 0
subs x1, x1, #1
bne Lloop
ret
（我希望在一條指令中有某種很好的方法來做分支--x1 == 0，但我想不出任何）
注意：任何基礎數論課程都有一個簡單的公式，它是[n(n 1)(2n 1)] / 6，但我認為這不符合問題的精神。
然后我想知道 clang 如何為簡單的 C 版本生成程式集。在撰寫簡單的 C 實作時，我發現 clang-Og生成的程式集看起來有點冗長，但通常可以按預期使用回圈和累加器作業（盡管它非常低效）：
int sum_squares(int n)
{
int a = 0;
while (n--)
a = (n * n);
return a;
}
( clang -Og -S, 注釋了我自己，洗掉了 cfi，重命名了標簽)
_sum_squares:
sub sp, sp, #16 ; create stack space
str w0, [sp, #12] ; store n
str wzr, [sp, #8] ; store 0
b Ldec ; silly clang, this just falls through...
Ldec: ; n-- and return if n == 0
ldr w8, [sp, #12] ; load n
subs w9, w8, #1 ; w9 = (n - 1)
str w9, [sp, #12] ; store (n - 1) over n
subs w8, w8, #0 ; w8 = n - 0 (set flags based on n)
cset w8, eq ; set w8 = 1 if n == 0 else w8 = 0
tbnz w8, #0, Lret ; branch to return if n == 0, else fall through
b Ladd ; silly clang, this falls through again...
Ladd: ; a = n^2
ldr w8, [sp, #12] ; load n
ldr w9, [sp, #12] ; load n
mul w9, w8, w9 ; w9 = n * n
ldr w8, [sp, #8] ; load a
add w8, w8, w9 ; a = w9
str w8, [sp, #8] ; store a
b Ldec ; go back to start of look
Lret: ; return a from top of stack
ldr w0, [sp, #8] ; w0 = a
add sp, sp, #16 ; cleanup temp stack
ret ; back to caller
這對于將 C 代碼直接轉換為 arm64 匯編來說是完全合理的。經過一些優化（O1 使用類似的公式，O2 和 O3 相同），clang 產生了一些魔力。我不知道這段代碼是怎么想出來的，它看起來有點類似于這個求和的基本公式，除了有點魔法。我沒想到編譯器能夠在沒有回圈的情況下為此推匯出一個公式，但看來我錯了。生成的代碼如下（我盡最大努力在評論中，n是輸入w0）：
_sum_squares:
cbz w0, Lret ; return if n == 0
sub w8, w0, #1 ; w8 = (n - 1)
mul w9, w8, w8 ; w9 = (n - 1)^2
orr w9, w9, #0x2 ; w9 = ((n - 1)^2) | 2
sub w9, w9, w0 ; w9 = [((n - 1)^2) | 2] - n
mov w10, #5 ; w10 = 5
sub w10, w10, w0, lsl #1 ; w10 = 5 - (n / 2)
sub w11, w0, #2 ; w11 = n - 2
umull x11, w8, w11 ; w11 = (n - 1)(n - 2)
lsr x12, x11, #1 ; x12 = ((n - 1)(n - 2)) / 2
mul w10, w10, w12 ; w10 = (5 - (n / 2))(((n - 1)(n - 2)) / 2)
sub w12, w0, #3 ; w12 = n - 3
mul x11, x11, x12 ; x11 = (n - 1)(n - 2)(n - 3)
lsr x11, x11, #1 ; x11 = ((n - 1)(n - 2)(n - 3)) / 2
mov w12, #21846 ; w12 = 0x5556
movk w12, #21845, lsl #16 ; w12 = 0x55555556
; w8 = ((n - 1)([((n - 1)^2) | 2] - n)) (5 - (n / 2))(((n - 1)(n - 2)) / 2)
madd w8, w9, w8, w10
; let A = w8 (set in last instruction)
; w0 = (0x55555556 * (((n - 1)(n - 2)(n - 3)) / 2)) A
madd w0, w11, w12, w8
; somehow, this is the correct result?
; this feels like magic to me...
Lret:
ret ; return. Result already in w0.
我的問題：這究竟是如何運作的？C 編譯器怎么能被賦予這樣的回圈并推匯出一個甚至不涉及回圈的公式？我預計可能會有一些回圈展開，但不是這樣的。有沒有人有涉及這種優化的參考資料？
我特別不明白某些步驟orr w9, w9, #0x2或神奇數字 0x55555556 的作用。任何對這些步驟的深入了解將不勝感激。
uj5u.com熱心網友回復：
TL:DR: 是的，clang 知道整數冪級數和的閉式公式，并且可以檢測到這樣的回圈。 聰明的人已經教會現代編譯器識別某些操作模式并用源代碼中不存在的操作替換它們，例如旋轉甚至 popcount 回圈和 bithacks。特別是對于 clang/LLVM，還有 i^power 總和的封閉形式公式，包括步幅不是 1 的情況。耶數學！因此，您可以獲得 asm 邏輯，而不僅僅是源代碼的展開或矢量化版本。
另請參閱博客文章LLVM 如何優化冪和，其中討論了編譯器如何通過查看變數如何跨回圈迭代更新來找到這些回圈。
Matthieu M. 評論說封閉式公式是由 LLVM 中的標量演化優化匯出的。 代碼中的注釋說它主要用于分析回圈中涉及歸納變數的運算式。并參考了它用于重復鏈的技術的參考資料。
現代 C 編譯器可以在代碼的內部表示中識別某些回圈或短邏輯序列中的模式。人類（編譯器開發人員）已經告訴編譯器要尋找什么，并提供了一個手工制作的替換“公式”。我希望在 GIMPLE (GCC) 或 LLVM-IR 中，在生成 asm 時，不僅僅是像窺孔優化這樣的編譯后期。
所以我猜想 LLVM 優化器內部的邏輯會檢查它找到的每個回圈是否存在以下一種或多種可能性，并使用一些代碼來查找代表該回圈程式邏輯的 LLVM-IR 的某些屬性：
- 它是否將一個陣列原封不動地復制到另一個陣列？如果是，則替換為
__builtin_memcpy，稍后可能會行內擴展或編譯為call memcpy. 如果它有其他副作用，比如讓指標變數遞增，那么在包含回圈的函式的新 LLVM-IR 中也表示它。 - 它是否將記憶體范圍的每個位元組設定為一個常量位元組值？如果是這樣，
memset - 它的操作順序是否等同于這個popcnt的順序？如果存在硬體支持，則發出一個
popcnt，否則保持回圈策略。（所以它不只是把它當作它__builtin_popcount，而不是用 bithack 或呼叫輔助函式替換回圈。這是有道理的，因為有些策略適用于設定了少量位的數字，程式員可能已經選擇了那個心里。） - 回圈變數是用一系列整數的總和（有一定步幅）更新的，還是用整數的總和更新的？然后使用避免固定寬度整數溢位的封閉式公式。（如果起點和步幅不是
1，則添加偏移量和/或比例因子。）
檢查可能在考慮由回圈修改的變數方面起作用，該變數在回圈后讀取。所以它知道在查看操作時要考慮什么變數。（沒有使用結果的回圈被洗掉。）
GCC 不會尋找整數序列的總和，但 clang 會。IDK 這實際上加速了多少真實世界的代碼庫；封閉形式的公式相當有名，著名的是它在小時候被高斯重新發現。（所以希望很多代碼使用公式而不是回圈）。沒有多少程式需要完全做到這一點，我曾想，除非作為練習。
（封閉形式的平方和公式的存在不太為人所知，但有一個，而且顯然也適用于一般的冪。）
Clang 的公式實作當然必須為每個輸入整數給出準確正確的結果，其中 C 抽象機不會遇到未定義的行為（對于有符號整數溢位），或者匹配無符號乘法的截斷。否則它不會滿足 as-if 規則，或者只能在行內到具有已知有限值范圍的地方時使用。（在實踐中，似乎 clang 沒有使用無符號的封閉形式優化，但也許我只是在我嘗試的版本中犯了一個錯誤。使用 64 位整數可以安全地計算 32 位整數的總和。并且然后截斷可能會產生與源相同的結果。）
n*(n 1)n*(n 1)/2在仍在范圍內的情況下可能會溢位，因此這很重要。對于int64 位機器上的 32 位，LLVM 可以并且確實簡單地使用 64 位乘法和右移。這可能是對使用雙寬度輸出和擴展精度右移的一般情況的窺孔優化，如果產品不適合一個，則跨兩個暫存器。（例如，在 EDX:EAX 中生成 64 位乘積后， x86shrd edx, eax, 1將低位從高位轉移到 EAX 的頂部。）mul r32
它也n * (n-1) / 2 n代替了通常的n * (n 1)/2; 不知道這有什么幫助。它避免了輸入型別的溢位，我猜，以防萬一對于unsigned原始回圈只有包裝而不是 UB 的型別很重要。除了它不對無符號進行此優化。（順便說一句，要么是偶數，n要么n -1是偶數，所以除法（右移）是精確的；這很好，因為整數之和最好是整數。）
在您的平方和 asm 中，您可以看到它umull x, w, w用于進行擴大乘法和 64 位右移，然后再進行除以 3 的 32 位乘法逆運算。
玩弄您的代碼和簡化版本而不是平方，當您倒數或倒數時，它對代碼生成的影響很小。
int sum_ints(int n) {
int a = 0;
//for (int i=0 ; i<n ; i ) a = i; // count up, skipping n
while (n--) a = n; // count down, skipping n
return a;
}
否定n會與您的版本有 UB，因為回圈會運行到INT_MIN--, 并首先溢位a。所以 clang 可能會也可能不會使用它來假設初始n值是非負的。但如果不是，IDK 為什么它會生成更復雜的乘以兩倍的代碼。
// count down version, starting with a = n-1, so x = n-1 in the usual formulae.
// clang15 -O3
sum_ints(int):
cbz w0, .LBB0_2 // only bail on zero, not negative.
sub w8, w0, #1 // n-1
sub w9, w0, #2 // n-2
umull x10, w8, w9 // (n-1)*(n-2)
madd w8, w8, w9, w0 // w8 = (n-1)*(n-2) n
lsr x9, x10, #1 // w9 = (n-1)*(n-2)/2
mvn w9, w9 // w9 = ~w9 = -w9 - 1
add w0, w8, w9 // (n-1)*(n-2) - (n-1)*(n-2)/2 n - 1 I think?
.LBB0_2:
ret
// count up version, ending with n-1. clang15 -O3
sum_ints(int):
subs w8, w0, #1 // n-1
b.lt .LBB0_2
sub w9, w0, #2 // n-2
umull x9, w8, w9 // (n-1)*(n-2)
lsr x9, x9, #1 // . / 2
add w0, w8, w9 // (n-1)*(n-2)/2 (n-1) = (n-1)*(n-2 2)/2
// = the usual x * (x 1 )/2 for x=n-1
ret
.LBB0_2:
mov w0, wzr // separate return path for all negative inputs
ret
其他型別的回圈模式-識別/替換
GCC 和 clang 對計算設定位的回圈進行模式識別，以及人們將從 SO 復制/粘貼的標準 bithack 。（這很有用，因為 ISO C 無法提供一種可移植的方式來表達大多數現代 CPU 所具有的這種操作。而 ISO C 僅使用<bit>或通過修復了 C 20 中的該缺陷std::bitset<32> .count()）。所以一些真正的代碼庫只是在設定位上有一個 bithack 或簡單的回圈而不是__builtin_popcount因為人們更喜歡簡單并且希望將性能留給編譯器。
這些模式識別器僅在某些特定的實作方式上起作用popcount，即x &= x-1; count ；試圖證明每個可能回圈的等價性可能會花費太多編譯時間。由此，我們可以非常確定這些通過尋找特定的實作來作業，而不是尋找每個可能的整數的實際結果。
變數名當然無關緊要，但對輸入變數的操作順序很重要。我假設在檢查等效性時以給出相同結果的方式重新排序操作有一定的靈活性。在 GCC 的例子中，顯然number_of_iterations_popcount是發現這個的函式的名稱：編譯器通常想知道一個回圈將運行多少次迭代：如果它是一個小常量，他們可能會完全展開它。如果它可以在開始回圈之前從其他變數中計算出來，它就是自動矢量化的候選物件。（GCC/clang 無法自動向量化搜索回圈，或任何其他具有資料依賴 if() 中斷的內容。）
如Count the number of set bits in a 32-bit integer的頂部答案所示，GCC10 和 clang10 ( Godbolt ) 也可以popcount使用 SWAR bithack 識別 a，因此您可以兩全其美：理想情況下是一條指令，但如果不是那么至少是一個好策略。
當預期的設定位數較小時，計算x &= x-1until的迭代次數x == 0是可以的，因此有時也是一個明智的選擇，因為如果硬體 popcount 可用，GCC / clang 可以替代的另一件事。（并且撰寫簡單，不需要屏蔽常量，并且可以編譯成小的機器代碼大小，-Os如果不被單個指令替換的話。）
int popcount_blsr_until_zero(unsigned x){
int count = 0;
while (x){
count ; // loop trip-count = popcount, this is what GCC looks for
x &= x - 1;
}
return count;
}
用于 x86-64 的 GCC 和 clang，-O3 -march=nehalem或更高版本，用于此版本和其他一些版本的 Godbolt 。
# gcc12 -O3 -march=znver2
popcount_blsr_until_zero(unsigned int):
popcnt eax, edi
ret
// clang -O3 for AArch64
popcount_blsr_until_zero(unsigned int):
mov w8, w0 // this is pointless, GCC doesn't do it.
fmov d0, x8
cnt v0.8b, v0.8b // ARM unfortunately only has vector popcnt
uaddlv h0, v0.8b // hsum bytes
fmov w0, s0 // copy back to GP-integer
ret
通過模式識別進行代碼替換的最簡單形式之一是編譯(n<<5) | (n>>(32-5))成 rotate-left by 5。（請參閱此 Q&A以了解運行時變數計數，以及如何安全地撰寫能夠被識別的內容，但即使是計數也能避免 UB 0.)
但這可能會在編譯程序中發生得足夠晚，您將其稱為窺孔優化。CISC ISA 往往有更多的窺孔優化，比如 x86 有特殊情況的更短指令來在累加器中簽名（cdqe而不是movzx eax, ax）。x86 xor-將暫存器設定為零的歸零仍然可以稱為窺孔，盡管有時需要重新排列東西，因為它會破壞 FLAGS 而mov eax, 0不會。
-fpeephole2GCC 使用（部分）啟用異或歸零-O2；也許把它當作一個窺視孔就是為什么 GCC 有時做得不好并且無法找到重新排序的方法所以xor-zero //cmp而setcc不是cmp/ setcc/ movzx，因為 x86 setcc 根據 FLAGS 條件設定暫存器很糟糕，只寫低 8 位。AArch64 有更好的指令，例如csinc可以與零暫存器一起使用以實作 0/1，或與其他暫存器一起使用以有條件地選擇和遞增。
但是級數和回圈是一種更大規模的替代，而不是我認為的窺孔，特別是因為它不是特定于目標的。
還相關：
是否允許 C 編譯器用另一種演算法替換演算法？- 是的。但通常他們不會這樣做，因為編譯器足夠機械以至于它們并不總是正確的，并且為資料選擇一種有效的演算法是 C 程式員希望編譯器尊重的東西，除非有一條指令顯然總是更快.
clang 知道如何
__builtin_popcount使用 AVX2 自動矢量化陣列vpshub作為半位元組查找表。它不僅僅是通過相同的操作制作 SIMD 版本，它再次使用了人類編譯器開發人員放在那里供其使用的擴展。為什么編譯器優化不為 1..N 的整數總和生成回圈？是關于這種優化不會發生的情況，例如一個帶有
j <= nfor unsigned 的情況，這是一個潛在的無限回圈。那里的評論發現了一些關于何時可以優化 clang 的有趣限制：例如，如果回圈是
for (int j=0 ; j < n; j = 3)，則行程計數將難以預測/計算，并且會破壞此優化。
uj5u.com熱心網友回復：
至少要開始，這是您的“基本數論”公式，盡管形式相當混亂且效率低下。clang 開發人員顯然也參加了該課程。
一些幫助驗證它的提示：
您的
sum_squares函式有一個差一錯誤，總和僅為n-1. 因此我們期望得到的公式是n(n-1)(2n-1)/6。在
orr w9, w9, #0x2這種情況下，等同于add w9, w9, #0x2。前面的指令，mul w9, w8, w8加載w9了 的平方w8。現在唯一的完美平方模 4 是 0 和 1，它們的第 1 位都是清零的，因此第 1 位w9將永遠是清零的。所以w9 | 2相當于w9 2. （不，我不知道為什么 clang 會這樣做。）正如哈羅德評論的那樣，乘以
0x55555556mod 2^32 相當于除以 3 和乘以 2（假設沒有余數）。這種技術有時被稱為“幻數除法”。請參閱為什么 GCC 在實作整數除法時使用乘以一個奇怪的數字？. 因此，在此之前x11 = ((n - 1)(n - 2)(n - 3)) / 2，請注意，您始終是 3 的倍數（除以 2 始終是精確的，因為分子始終是偶數）。因此w11 * w12導致(n-1)(n-2)(n-3)/6.
將所有這些放在一起，您可以檢查代數以驗證最終結果是否等同于n(n-1)(2n-1)/6。
我不能說 clang 如何執行此優化。我想我曾經經歷過弄清楚哪個 LLVM 優化程序使它發生的練習，但我不記得它是什么。但是有一些已知的演算法可以自動匯出這種封閉形式的運算式，例如Gosper 演算法。所以 clang 可能正在應用類似的東西。我現在在猜測，但也許演算法以未簡化的形式吐出一個公式，也許 clang 只是發出直接對應的代碼，而不是首先嘗試進行代數簡化。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/533856.html