InstCombine 貢獻者指南

本指南列出了一系列 InstCombine 貢獻應遵循的規則。遵循這些規則將能大幅加快 PR 審核速度。

測試

預提交測試

針對新的最佳化或錯誤編譯修復的測試應預先提交。這表示您首先提交測試，其中 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 等。例如，檢查涉及兩個 select 相加的折疊的多重使用行為的測試可以稱為 @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 向量通常不會折疊。您應該不要嘗試讓它們折疊，除非這樣做不會增加任何額外複雜性。您仍然應該新增測試，即使它沒有折疊。

旗標測試

如果您的轉換涉及可能具有 poison 生成旗標的指令，例如 add 上的 nuw 和 nsw，您應該測試這些旗標如何與轉換互動。

如果您的轉換需要特定旗標才能正確，請務必新增缺少所需旗標的負面測試。

如果您的轉換不需要旗標也能正確，您應該進行保留行為的測試。如果輸入指令具有某些旗標，在可以保留它們的情況下，它們是否在輸出指令中被保留？（這取決於轉換。請使用 alive2 檢查。）

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

其他測試

上面提到的測試類別並非詳盡無遺。根據轉換中涉及的指令，可能需要新增更多測試。一些範例

• 對於涉及記憶體存取的折疊，如 load/store，請檢查是否正確處理了可縮放向量和非位元組大小類型（如 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 值的轉換正確性。如果轉換沒有增加任何值的用途數量，這通常沒問題。

最後，可以本地建置 alive2 並使用 -smt-to=<m> 來驗證具有更長逾時時間的證明。如果您不想這樣做（或者仍然無效），請提交您擁有的證明，即使逾時。

實作

真實世界的實用性

可以實作的轉換數量非常多，但只有極少一部分對真實世界的程式碼有用。

不具有真實世界實用性的轉換為 LLVM 專案帶來負面價值，因為它們佔用了寶貴的審核人員時間、增加了程式碼複雜性並增加了編譯時間開銷。

我們不要求每個轉換都有明確的真實世界實用性證明——在大多數情況下，實用性相當 “明顯”。但是，對於複雜或不尋常的折疊，可能會出現這個問題。在選擇您的工作內容時，請記住這一點。

特別是，如果沒有真實世界實用性的證據，則很可能會拒絕針對模糊測試器產生的錯過最佳化報告的修復。

選擇正確的最佳化 pass

InstCombine 系列中有許多 pass 和實用程式，實作折疊時選擇正確的位置非常重要。

• ConstantFolding：用於將帶有常數引數的指令折疊為常數。（主要與 intrinsics 相關。）

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

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

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

• AggressiveInstCombine：用於昂貴或違反 InstCombine 要求的折疊。

• VectorCombine：用於需要目標相關成本建模的向量運算折疊。

有時，邏輯上屬於 InstSimplify 的折疊會放在 InstCombine 中，例如因為它們太昂貴，或者因為它們在 InstCombine 中實作起來結構更簡單。

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

規範化和目標獨立性

InstCombine 是一個目標獨立的規範化 pass。這表示它嘗試將 IR 帶入 “規範形式”，以便其他最佳化（在 InstCombine 內部和外部）可以依賴它。因此，所選的規範形式需要對所有目標都相同，並且不依賴於目標特定的成本建模。

在許多情況下，“規範化” 和 “最佳化” 是同時發生的。例如，如果我們將 x * 2 轉換為 x << 1，這既使 IR 更規範化（因為現在只有一種方式可以表達相同的運算，而不是兩種），也更快（因為移位通常比乘法具有更低的延遲）。

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

如果某些規範化對於特定目標沒有利潤，則需要在後端新增反向轉換。將不接受在某些目標上停用特定 InstCombine 轉換或使用目標特定成本建模來驅動它們的修補程式。唯一允許的目標依賴性是 DataLayout 和 TargetLibraryInfo。

TargetTransformInfo 的使用僅允許用於目標特定 intrinsics 的 hooks，例如 TargetTransformInfo::instCombineIntrinsic()。無論如何，這些本質上已經是目標相關的。

對於需要成本建模的向量特定轉換，可以使用 VectorCombine pass 來代替。在極少數情況下，如果沒有其他替代方案，則目標相關轉換可能會被接受到 AggressiveInstCombine 中。

PatternMatch

許多轉換都使用了在 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));

一些常見的 matcher 是

• 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) 等：匹配一個 add/sub/etc，其中第一個運算元匹配 M1，第二個匹配 M2。

• m_c_Add(M1, M2) 等：可交換地匹配一個 add。運算元必須匹配 M1 和 M2 或 M2 和 M1。大多數指令 matcher 都有一個可交換變體。

• 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(...))。請參閱下一節以取得更多資訊。

請參閱標頭以取得可用 matcher 的完整列表。

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() matcher 或 V->hasOneUse() 方法執行一次使用檢查。

一般化

轉換可能既太具體（僅處理模式的某些奇怪子集，導致意外的最佳化懸崖），也可能太通用（引入複雜性來處理沒有真實世界相關性的情況）。正確的通用性程度非常主觀，因此本節僅提供一些廣泛的準則。

• 避免硬編碼為特定常數的轉換。嘗試找出任意常數的通用規則是什麼。

• 新增共軛模式的處理。例如，如果您為 icmp eq 實作折疊，您幾乎肯定也想支援 icmp ne，結果相反。同樣，如果您為 icmp 的 and 實作模式，您也應該使用 or 來處理 de-Morgan 共軛。

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

• 除非有特定的動機這樣做，否則不要處理非規範模式。例如，有時可能值得處理通常會轉換為不同規範形式的模式，但仍可能在多重使用場景中發生。如果存在特定的真實世界動機，則可以這樣做，但否則您不應刻意這樣做。

• 有時，動機模式使用具有某些屬性的常數值，但可以透過使用 ValueTracking 查詢將折疊推廣到非常數值。這是否有意義取決於具體情況，但通常最好首先僅處理常數模式，然後在看起來有用時再進行推廣。

審核人員準則

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