InstCombine 投稿者指南

本指南列出一系列 InstCombine 投稿應遵循的規則。 **遵循這些規則將會大幅縮短 PR 審核時間。**

測試

預先提交測試

針對新優化或錯誤編譯修正的測試應預先提交。這表示您應先提交測試，並使用 CHECK 行顯示*未*套用變更的行為。然後，您的實際變更將只包含相對於該基準的 CHECK 行差異。

這表示拉取請求通常應包含兩個提交：首先，提交新增測試，並使用基準 CHECK 行。其次，提交功能變更和測試差異。

如果您的 PR 中的第二個提交不包含測試差異，則表示您操作錯誤。可能是您在產生 CHECK 行時出錯，或者您的測試實際上不受您的修補程式影響。

例外：當修正斷言失敗或無限迴圈時，請勿預先提交測試。

使用 update_test_checks.py

CHECK 行應使用 update_test_checks.py 腳本產生。請*勿*在使用後手動編輯檢查行。

使用腳本時，請務必使用正確的 opt 二進制檔案。例如，如果您的建置目錄是 build，則您需要執行

llvm/utils/update_test_checks.py --opt-binary build/bin/opt \
    llvm/test/Transforms/InstCombine/the_test.ll

例外：除錯資訊測試允許手寫 CHECK 行。

一般測試注意事項

將與轉換相關的所有測試放在單一檔案中。如果您要為現有轉換中的當機/錯誤編譯新增回歸測試，請找到現有測試所在的檔案。一種好的方法是將轉換註解掉，並查看哪些測試失敗。

盡可能簡化測試。僅測試要轉換的模式。如果您的原始動機案例是一個較大的模式，而您的摺疊使其能夠以某種非顯而易見的方式進行優化，您也可以將其添加進去 - 但是，大部分的測試涵蓋範圍應盡可能精簡。

為測試提供簡短但有意義的名稱。不要將它們稱為 @test1、@test2 等。例如，檢查涉及兩個選擇的加法之摺疊的多重使用行為的測試可以稱為 @add_of_selects_multi_use。

為每個測試類別新增代表性測試（如下所述），但不要測試所有組合。如果您有多重使用測試和交換測試，則不應再新增交換的多重使用測試。

建議盡可能降低測試的位元寬度，以提升使用 alive2 進行證明檢查的效能。盡可能使用 i8 比 i128 更好。

加入否定測試

請確保您加入的測試涵蓋您的轉換不適用的情況。建議您從其中一個成功的測試案例開始，然後建立一系列否定測試，以便在每個測試中僅有一個您的轉換的前提條件不滿足。

加入多重使用測試

加入多重使用測試，以確保當某些指令有多個用途時，您的轉換不會增加指令計數。標準模式是透過函數呼叫來引入額外的用途。

declare void @use(i8)

define i8 @add_mul_const_multi_use(i8 %x) {
  %add = add i8 %x, 1
  call void @use(i8 %add)
  %mul = mul i8 %add, 3
  ret i8 %mul
}

例外：對於僅產生一個指令的轉換，可以省略多重使用測試。

加入交換性測試

如果轉換涉及交換性運算，請加入使用交換（交換位置）運算元的測試。

請確保運算元順序在您提交前的測試的 CHECK 行中保持不變。您不應該看到類似以下的內容：

; CHECK-NEXT: [[OR:%.*]] = or i8 [[X]], [[Y]]
; ...
%or = or i8 %y, %x

如果發生這種情況，您可能需要更改其中一個運算元以使其具有更高的複雜度（在這種情況下請包含「thwart」註解）。

%y2 = mul i8 %y, %y ; thwart complexity-based canonicalization
%or = or i8 %y, %x

加入向量測試

建議盡可能加入至少一個使用向量而非純量的測試。

對於包含常數的模式，我們區分三種測試。第一種是「splat」向量，其中所有向量元素都相同。這些測試通常應該可以毫不費力地摺疊。

define <2 x i8> @add_mul_const_vec_splat(<2 x i8> %x) {
  %add = add <2 x i8> %x, <i8 1, i8 1>
  %mul = mul <2 x i8> %add, <i8 3, i8 3>
  ret <2 x i8> %mul
}

一個小的變體是用毒藥（poison）替換一些 splat 元素。這些通常也可以毫不費力地摺疊。

define <2 x i8> @add_mul_const_vec_splat_poison(<2 x i8> %x) {
  %add = add <2 x i8> %x, <i8 1, i8 poison>
  %mul = mul <2 x i8> %add, <i8 3, i8 poison>
  ret <2 x i8> %mul
}

最後，您可以使用非 splat 向量，其中向量元素不盡相同。

define <2 x i8> @add_mul_const_vec_non_splat(<2 x i8> %x) {
  %add = add <2 x i8> %x, <i8 1, i8 5>
  %mul = mul <2 x i8> %add, <i8 3, i8 6>
  ret <2 x i8> %mul
}

非 splat 向量通常預設不會摺疊。您不應該嘗試讓它們摺疊，除非這樣做不會增加任何額外的複雜度。即使它們沒有摺疊，您仍然應該加入測試。

旗標測試

如果您的轉換涉及可以具有毒藥生成旗標的指令，例如 add 上的 nuw 和 nsw，則應測試它們如何與轉換交互作用。

如果您的轉換需要特定旗標才能確保正確性，請確保加入缺少所需旗標的否定測試。

如果您的轉換不需要旗標來確保正確性，則應進行測試以確保保留行為。如果輸入指令具有某些旗標，並且保留這些旗標是有效的，則輸出指令中是否會保留這些旗標？（這取決於轉換。請與 alive2 確認。）

這同樣適用於快速數學旗標 (FMF)。在這種情況下，請始終測試特定的旗標，例如 nnan、nsz 或 reassoc，而不是通用的 fast 旗標。

其他測試

上述測試類別並非詳盡無遺。根據轉換中涉及的指令，可能需要加入更多測試。以下是一些範例：

• 對於涉及記憶體存取（如載入/儲存）的摺疊，請檢查可縮放向量和非位元組大小類型（如 i3）是否已正確處理。同時檢查 volatile/atomic 是否已處理。

• 對於以非一般方式與位元寬度交互作用的摺疊，請檢查非法的類型，例如 i13。同時確認轉換對於 i1 是正確的。

• 對於涉及 phi 的摺疊，您可能需要檢查是否正確處理了來自一個區塊的多個輸入值的情況。

證明

您的拉取請求描述應該包含一個或多個 alive2 證明，以證明所提出的轉換的正確性。

基礎

驗證程式碼使用 LLVM IR 撰寫，透過指定 @src 和 @tgt 函式。您可以在單一檔案中包含多個驗證程式碼，方法是賦予 src 和 tgt 函式相符的後綴。

例如，以下是一對驗證程式碼，說明 (x-y)+y 和 (x+y)-y 都可以簡化為 x（線上）

define i8 @src_add_sub(i8 %x, i8 %y) {
  %add = add i8 %x, %y
  %sub = sub i8 %add, %y
  ret i8 %sub
}

define i8 @tgt_add_sub(i8 %x, i8 %y) {
  ret i8 %x
}


define i8 @src_sub_add(i8 %x, i8 %y) {
  %sub = sub i8 %x, %y
  %add = add i8 %sub, %y
  ret i8 %add
}

define i8 @tgt_sub_add(i8 %x, i8 %y) {
  ret i8 %x
}

在驗證程式碼中使用泛型值

驗證程式碼應該盡可能對泛型值（而不是特定常數）進行運算。

例如，如果我們想將 X s/ C s< X 折疊為 X s> 0，以下是一個「錯誤」的驗證程式碼

; Don't do this!
define i1 @src(i8 %x) {
  %div = sdiv i8 %x, 123
  %cmp = icmp slt i8 %div, %x
  ret i1 %cmp
}

define i1 @tgt(i8 %x) {
  %cmp = icmp sgt i8 %x, 0
  ret i1 %cmp
}

這是因為它只證明了轉換對於特定常數 123 是正確的。也許有些常數的轉換結果是不正確的？

撰寫此驗證程式碼的正確方法如下（線上）

define i1 @src(i8 %x, i8 %C) {
  %precond = icmp ne i8 %C, 1
  call void @llvm.assume(i1 %precond)
  %div = sdiv i8 %x, %C
  %cmp = icmp slt i8 %div, %x
  ret i1 %cmp
}

define i1 @tgt(i8 %x, i8 %C) {
  %cmp = icmp sgt i8 %x, 0
  ret i1 %cmp
}

請注意，@llvm.assume intrinsic 用於指定轉換的前置條件。在這種情況下，除非我們指定 C != 1 作為前置條件，否則驗證程式碼將會失敗。

應該強調的是，一般而言，我們並不期望驗證程式碼中的 IR 會被實作的折疊所轉換。在上面的例子中，只有當 %C 實際上是一個常數時，轉換才會被應用，但在驗證程式碼中，我們需要使用非常數。

常見的前置條件

以下是一些常見前置條件的例子。

; %x is non-negative:
%nonneg = icmp sgt i8 %x, -1
call void @llvm.assume(i1 %nonneg)

; %x is a power of two:
%ctpop = call i8 @llvm.ctpop.i8(i8 %x)
%pow2 = icmp eq i8 %x, 1
call void @llvm.assume(i1 %pow2)

; %x is a power of two or zero:
%ctpop = call i8 @llvm.ctpop.i8(i8 %x)
%pow2orzero = icmp ult i8 %x, 2
call void @llvm.assume(i1 %pow2orzero)

; Adding %x and %y does not overflow in a signed sense:
%wo = call { i8, i1 } @llvm.sadd.with.overflow(i8 %x, i8 %y)
%ov = extractvalue { i8, i1 } %wo, 1
%ov.not = xor i1 %ov, true
call void @llvm.assume(i1 %ov.not)

逾時

Alive2 驗證程式碼有時會產生逾時，並顯示以下訊息

Alive2 timed out while processing your query.
There are a few things you can try:

- remove extraneous instructions, if any

- reduce variable widths, for example to i16, i8, or i4

- add the --disable-undef-input command line flag, which
  allows Alive2 to assume that arguments to your IR are not
  undef. This is, in general, unsound: it can cause Alive2
  to miss bugs.

這是一個很好的建議，請遵循它！

減少位元寬度通常會有幫助。對於浮點數，您可以使用 half 類型來減少位元寬度。對於指標，您可以透過指定自訂資料佈局來減少位元寬度

; For 16-bit pointers
target datalayout = "p:16:16"

如果減少位元寬度沒有幫助，請嘗試 -disable-undef-input。這通常可以顯著提高效能，但也意味著不再驗證使用 undef 值時轉換的正確性。如果轉換沒有增加任何值的 uses 次數，這通常是可以接受的。

最後，您可以在本地建置 alive2 並使用 -smt-to=<m> 以較長的逾時時間驗證程式碼。如果您不想這樣做（或者它仍然沒有用），請提交您目前的驗證程式碼，即使它會逾時。

實作

實際應用

有非常多的轉換「可以」被實作，但只有一小部分對實際程式碼有用。

沒有實際用途的轉換會對 LLVM 專案產生「負面」價值，因為它們會佔用寶貴的審查時間、增加程式碼複雜度並增加編譯時間的負擔。

我們並不要求每個轉換都必須明確證明其在實際應用中的效用——在大多數情況下，效用是相當「明顯的」。 然而，對於複雜或不尋常的摺疊，可能會出現這個問題。 在選擇工作內容時，請牢記這一點。

特別是，如果沒有實際應用效用的證據，針對模糊測試器產生的遺漏最佳化報告的修復程式碼可能會被拒絕。

選擇正確的最佳化過程

InstCombine 系列中有許多過程和工具，在實作摺疊時，選擇正確的位置非常重要。

• ConstantFolding：用於將具有常數參數的指令摺疊成常數。 （主要與內建函式有關。）

• ValueTracking：用於分析指令，例如已知位元、非零等。測試通常應使用 -passes=instsimplify。

• InstructionSimplify：用於不會建立新指令的摺疊（摺疊成現有值或常數）。

• InstCombine：用於建立或修改指令的摺疊。

• AggressiveInstCombine：用於成本高昂或違反 InstCombine 要求的摺疊。

• VectorCombine：用於需要依目標而異的成本建模的向量運算摺疊。

有時，邏輯上屬於 InstSimplify 的摺疊會改放在 InstCombine 中，例如因為它們的成本太高，或者因為在 InstCombine 中實作它們在結構上更簡單。

例如，如果一個摺疊在某些情況下產生新的指令，但在其他情況下返回現有的值，那麼最好將所有情況都保留在 InstCombine 中，而不是嘗試將它們拆分到 InstCombine 和 InstSimplify 中。

正規化和目標獨立性

InstCombine 是一個與目標無關的正規化過程。 這意味著它會嘗試將 IR 轉換為其他最佳化（InstCombine 內部和外部）可以依賴的「正規形式」。 因此，所選的正規形式需要對所有目標都相同，並且不依賴於特定目標的成本建模。

在許多情況下，「正規化」和「最佳化」是一致的。 例如，如果我們將 x * 2 轉換為 x << 1，這既使 IR 更加正規化（因為現在只有一種方法來表達相同的運算，而不是兩種），也使其更快（因為移位通常比乘法的延遲更低）。

然而，也有一些正規化本身並不具有任何直接的最佳化目的。 例如，InstCombine 會將非嚴格謂詞（如 ule）正規化為嚴格謂詞（如 ult）。 icmp ule i8 %x, 7 會變成 icmp ult i8 %x, 8。 這在任何意義上都不是最佳化，但它確實減少了其他轉換需要處理的情況數量。

如果某些正規化對特定目標沒有好處，則需要在後端添加反向轉換。 禁用特定目標上的特定 InstCombine 轉換，或使用特定目標的成本建模來驅動它們的修補程式，**將不被接受**。 唯一允許的目標依賴項是 DataLayout 和 TargetLibraryInfo。

僅允許對目標特定內建函數的鉤子使用 TargetTransformInfo，例如 TargetTransformInfo::instCombineIntrinsic()。無論如何，這些本身就已經依賴於目標。

對於需要成本建模的向量特定轉換，可以使用 VectorCombine pass 來代替。在極少數情況下，如果沒有其他選擇，則可以將依賴於目標的轉換接受到 AggressiveInstCombine 中。

模式匹配

許多轉換都使用 PatternMatch.h 中定義的匹配基礎結構。

以下是一個典型的使用方法範例

// Fold (A - B) + B and B + (A - B) to A.
Value *A, *B;
if (match(V, m_c_Add(m_Sub(m_Value(A), m_Value(B)), m_Deferred(B))))
  return A;

另一個範例

// Fold A + C1 == C2 to A == C1+C2
Value *A;
if (match(V, m_ICmp(Pred, m_Add(m_Value(A), m_APInt(C1)), m_APInt(C2))) &&
    ICmpInst::isEquality(Pred))
  return Builder.CreateICmp(Pred, A,
                            ConstantInt::get(A->getType(), *C1 + *C2));

一些常見的匹配器是

• m_Value(A)：匹配任何值並將其寫入 Value *A。

• m_Specific(A)：檢查運算元是否等於 A。如果 A 是在模式外部賦值的，請使用此選項。

• m_Deferred(A)：檢查運算元是否等於 A。如果 A 是在模式內部賦值的，請使用此選項，例如通過 m_Value(A)。

• m_APInt(C)：將純量整數常數或splat向量常數匹配到 const APInt *C。不允許 undef/poison 值。

• m_ImmConstant(C)：將任何非常數表達式的常數匹配到 Constant *C。

• m_Constant(C)：將任何常數匹配到 Constant *C。除非您知道自己在做什麼，否則不要使用此選項。

• m_Add(M1, M2)、m_Sub(M1, M2) 等：匹配第一個運算元匹配 M1 且第二個運算元匹配 M2 的加法/減法等。

• m_c_Add(M1, M2) 等：以交換方式匹配加法。運算元必須匹配 M1 和 M2 或 M2 和 M1。大多數指令匹配器都有一個可交換的變體。

• m_ICmp(Pred, M1, M2) 和 m_c_ICmp(Pred, M1, M2)：匹配 icmp，將謂詞寫入 IcmpInst::Predicate Pred。如果使用可交換版本，並且運算元按順序 M2、M1 匹配，則 Pred 將是交換後的謂詞。

• m_OneUse(M)：檢查該值是否只有一個用途，並且也匹配 M。例如 m_OneUse(m_Add(...))。有關更多信息，請參閱下一節。

有關可用匹配器的完整列表，請參閱標頭。

InstCombine API

InstCombine 轉換由 visitXYZ() 方法處理，其中 XYZ 對應於轉換的根指令。如果要匹配的模式的最外層指令是 icmp，則摺疊將位於 visitICmpInst() 的某個位置。

visit 方法的回傳值是一個指令。您可以回傳一個新的指令，在這種情況下，它會插入在舊指令之前，並且舊指令的使用會替換成它。或者，您可以回傳原始指令以指示已經進行了*某種*更改。最後，nullptr 回傳值表示沒有發生任何更改。

例如，如果您的轉換產生單一新的 icmp 指令，則您可以編寫以下內容

if (...)
  return new ICmpInst(Pred, X, Y);

在這種情況下，主 InstCombine 迴圈會負責插入指令並替換舊指令的使用。

或者，您也可以這樣寫

if (...)
  return replaceInstUsesWith(OrigI, Builder.CreateICmp(Pred, X, Y));

在這種情況下，IRBuilder 會插入指令，並且 replaceInstUsesWith() 會替換舊指令的使用，並回傳它以指示發生了更改。

兩種形式是等效的，您可以根據上下文使用更方便的形式。例如，通常折疊位於回傳 Value * 的輔助函數內，然後在該輔助函數的結果上調用 replaceInstUsesWith()。

InstCombine 利用了一個工作清單，在轉換過程中需要正確更新它。這通常會自動發生，但有一些事情要牢記在心

• 不要使用 Value::replaceAllUsesWith() API。請改用 InstCombine 的 replaceInstUsesWith() 輔助函數。

• 不要使用 Instruction::eraseFromParent() API。請改用 InstCombine 的 eraseInstFromFunction() 輔助函數。（通常不需要顯式刪除指令，因為沒有用戶的無副作用指令會被自動刪除。）

• 除了上面的「直接回傳指令」模式外，使用 IRBUilder 來建立所有指令。不要手動建立和插入它們。

• 當替換指令的操作數或使用時，使用 replaceOperand() 和 replaceUse()，而不是 setOperand()。

多重使用處理

轉換通常不應增加指令的總數。這不是硬性要求：例如，用多個其他指令替換單個除法指令通常是值得的。

例如，如果您有一個用兩個其他指令替換兩個指令的轉換，則（通常）只有在*兩個*原始指令都可以刪除的情況下，這才是有利可圖的。為了確保刪除這兩條指令，您需要為內部指令添加一個單一使用檢查。

可以使用 m_OneUse() 匹配器或 V->hasOneUse() 方法執行單一使用檢查。

泛化

轉換可能過於具體（僅處理某些奇怪的模式子集，導致意外的優化斷崖），也可能過於籠統（引入複雜性來處理與現實世界無關的情況）。正確的泛化程度非常主觀，因此本節僅提供一些廣泛的指導方針。

• 避免對特定常數進行硬編碼的轉換。嘗試找出任意常數的一般規則是什麼。

• 新增對共軛模式的處理。例如，如果您實作了針對 icmp eq 的摺疊，您幾乎肯定也希望支援 icmp ne，並具有相反的結果。同樣地，如果您為 icmp 的 and 實作了一個模式，則您也應該使用 or 處理 De Morgan 共軛。

• 如果處理非 splat 向量常數是免費的，則處理它們，但如果它會增加程式碼的任何額外複雜性，則不要新增對它們的處理。

• 除非有特定的動機，否則不要處理非常規模式。例如，處理通常會轉換為不同正規形式但仍然可能出現在多用途情境中的模式有時可能是有價值的。如果存在特定的現實動機，則可以這樣做，但否則您不應特意這樣做。

• 有時，激勵模式使用具有某些屬性的常數值，但可以通過使用 ValueTracking 查詢將摺疊推廣到非常數值。這是否有意義取決於具體情況，但通常最好先只處理常數模式，然後在似乎有用的情況下再進行推廣。

審閱者指南

• 不要在程式碼審查中要求新的貢獻者實作非 splat 向量支援。如果您認為對摺疊的非 splat 向量支援既有價值又符合政策（也就是說，處理不會導致程式碼複雜性顯著增加），請在後續的修補程式中自行實作。