InstCombine 貢献者ガイド¶
このガイドでは、InstCombineへの貢献が従うべき一連のルールを説明します。 **これらのルールに従うことで、PRの承認がはるかに速くなります。**
テスト¶
プレコミットテスト¶
新しい最適化または誤ったコンパイルの修正のためのテストは、プレコミットする必要があります。つまり、最初に変更*なし*の動作を示すCHECK行を含むテストをコミットします。実際の変更には、そのベースラインに対するCHECK行の差分のみが含まれます。
これは、プルリクエストには一般的に2つのコミットが含まれることを意味します。まず、ベースラインのチェック行を追加するコミット。次に、機能の変更とテストの差分を含むコミット。
PRの2番目のコミットにテストの差分が含まれていない場合は、何か間違えています。CHECK行の生成時にミスをしたか、テストが実際にはパッチの影響を受けていません。
例外: アサーションの失敗または無限ループを修正する場合は、テストをプレコミットしないでください。
update_test_checks.pyを使用する¶
CHECK行は、update_test_checks.pyスクリプトを使用して生成する必要があります。使用後にCHECK行を手動で編集*しないでください*。
スクリプトを使用する際には、正しいoptバイナリを使用してください。たとえば、ビルドディレクトリがbuildの場合、次を実行します。
llvm/utils/update_test_checks.py --opt-binary build/bin/opt \
llvm/test/Transforms/InstCombine/the_test.ll
例外: デバッグ情報テストでは、手書きのCHECK行が許可されています。
一般的なテストに関する考慮事項¶
変換に関連するすべてのテストを1つのファイルに配置します。既存の変換でクラッシュ/誤コンパイルの回帰テストを追加する場合は、既存のテストがあるファイルを見つけます。良い方法は、変換をコメントアウトして、どのテストが失敗するかを確認することです。
テストを最小限にします。変換されるパターンだけをテストします。元の動機となるケースが、フォールドによって何らかの重要な方法で最適化できるより大きなパターンである場合は、それも追加できます。ただし、テストカバレッジの大部分は最小限にする必要があります。
テストに短いが意味のある名前を付けます。@test1、@test2などとは呼ばないでください。たとえば、2つのselectの加算を含むフォールドの複数使用の動作をチェックするテストは、@add_of_selects_multi_useと呼ぶことができます。
各テストカテゴリ（以下で説明）の代表的なテストを追加しますが、すべての組み合わせをテストしないでください。複数使用テストと可換テストがある場合、可換複数使用テストも追加するべきではありません。
alive2を使用した証明のチェックのパフォーマンスを向上させるために、テストのビット幅を低く保つことが望ましいです。可能な場合は、i128よりもi8を使用する方が良いです。
負のテストを追加する¶
変換が*適用されない*テストを追加してください。成功するテストケースの1つから始めて、負のテストのシーケンスを作成します。各テストでは、変換の**1つだけ**の異なる前提条件が満たされないようにします。
複数使用テストを追加する¶
一部の命令が追加で使用されている場合、変換によって命令数が増加しないことを保証する複数使用テストを追加します。標準的なパターンは、関数呼び出しで追加の使用を導入することです。
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
}
例外: 1つの命令のみを生成する変換の場合、複数使用テストは省略できます。
可換テストを追加する¶
変換に可換演算が含まれる場合は、可換（交換された）オペランドを含むテストを追加します。
プレコミットされたテストのCHECK行で、オペランドの順序がそのまま維持されていることを確認してください。次のようなものは表示されません。
; CHECK-NEXT: [[OR:%.*]] = or i8 [[X]], [[Y]]
; ...
%or = or i8 %y, %x
これが発生した場合は、オペランドの1つをより複雑なものに変更する必要がある場合があります（その場合は「thwart」コメントを含めます）。
%y2 = mul i8 %y, %y ; thwart complexity-based canonicalization
%or = or i8 %y, %x
ベクトルテストを追加する¶
可能な場合は、スカラーではなくベクトルを使用するテストを少なくとも1つ追加することをお勧めします。
定数を含むパターンの場合、3種類のテストを区別します。1つ目は「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
}
マイナーバリアントは、一部のsplat要素をpoisonに置き換えることです。これらも多くの場合、追加の労力なしでフォールドされます。
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など、poison生成フラグを持つ可能性のある命令が含まれる場合は、これらが変換とどのように相互作用するかをテストする必要があります。
変換に正確性のために特定のフラグが*必要な*場合は、必要なフラグがない負のテストを追加してください。
変換に正確性のためにフラグが不要な場合は、保存動作のテストが必要です。入力命令に特定のフラグがある場合、保存することが有効であれば、出力命令に保存されますか？（これは変換によって異なります。alive2で確認してください。）
同じことが高速数学フラグ（FMF）にも当てはまります。その場合は、包括的なfastフラグではなく、nnan、nsz、reassocなどの特定のフラグを常にテストしてください。
その他のテスト¶
上記のテストカテゴリは網羅的ではありません。変換に含まれる命令によっては、追加する必要があるテストがさらにあります。いくつかの例：
load/storeなどのメモリアクセスを含むフォールドの場合、スケーラブルベクトルとバイトサイズではないタイプ（i3など）が正しく処理されていることを確認します。また、volatile/atomicが処理されていることを確認します。
ビット幅と何らかの重要な方法で相互作用するフォールドの場合、i13などの不正なタイプを確認します。また、変換がi1に対して正しいことを確認します。
phiを含むフォールドの場合、1つのブロックからの複数の入力値の場合が正しく処理されていることを確認することをお勧めします。
証明¶
プルリクエストの説明には、提案された変換の正確性について、1つ以上のalive2証明を含める必要があります。
基本¶
証明は、@src関数と@tgt関数を指定することにより、LLVM IRを使用して記述されます。src関数とtgt関数に一致するサフィックスを付けることにより、1つのファイルに複数の証明を含めることができます。
たとえば、(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組み込み関数は、変換の前提条件を指定するために使用されることに注意してください。この場合、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プロジェクトに*負の*価値をもたらします。
すべての変換について実世界の有用性の明確な証明を要求するわけではありません。ほとんどの場合、有用性は非常に「明白」です。ただし、複雑なfoldや珍しいfoldの場合は、その点が問題になる可能性があります。作業内容を選択する際には、この点を念頭に置いてください。
特に、ファザーによって生成された見逃された最適化レポートの修正は、実世界の有用性の証拠がない場合、却下される可能性があります。
正しい最適化パスを選択する¶
InstCombineファミリーには、多くのパスとユーティリティがあり、foldを実装する際に適切な場所を選択することが重要です。
ConstantFolding: 定数引数を持つ命令を定数にfoldする場合。（主に組み込み関数に関連します。）ValueTracking: 命令を分析する場合、例えば既知のビット、非ゼロなどを調べる場合。テストでは通常、-passes=instsimplifyを使用してください。InstructionSimplify: 新しい命令を作成しないfoldの場合（既存の値または定数にfoldする場合）。InstCombine: 命令を作成または変更するfoldの場合。AggressiveInstCombine: コストがかかるfoldや、InstCombineの要件に違反するfoldの場合。VectorCombine: ターゲット依存のコストモデリングを必要とするベクトル演算のfoldの場合。
論理的にはInstructionSimplifyに属するfoldが、コストがかかりすぎる、またはInstCombineで実装する方が構造的に単純であるなどの理由で、InstCombineに配置される場合があります。
たとえば、foldが場合によっては新しい命令を生成し、他の場合は既存の値を返す場合、InstCombineとInstructionSimplifyに分割しようとするよりも、すべてのケースをInstCombineに保持する方が望ましい場合があります。
正規化とターゲット非依存性¶
InstCombineは、ターゲット非依存の正規化パスです。これは、IRを、他の最適化（InstCombineの内外両方）が依存できる「正規形」にすることを試みることを意味します。このため、選択された正規形はすべてのターゲットで同じである必要があり、ターゲット固有のコストモデリングに依存してはいけません。
多くの場合、「正規化」と「最適化」は一致します。たとえば、x * 2 を x << 1 に変換すると、IRがより正規化され（同じ操作を表す方法が2つではなく1つになるため）、高速になります（シフトは通常、乗算よりもレイテンシが低いため）。
ただし、直接的な最適化の目的を果たさない正規化もあります。たとえば、InstCombineは、ule のような非厳密な述語を、ult のような厳密な述語に正規化します。icmp ule i8 %x, 7 は icmp ult i8 %x, 8 になります。これは、意味のある最適化ではありませんが、他の変換が処理する必要があるケースの数を減らします。
特定のターゲットに対して一部の正規化が有益でない場合は、バックエンドに逆変換を追加する必要があります。特定のターゲットで特定のInstCombine変換を無効にする、またはターゲット固有のコストモデリングを使用してそれらを駆動するパッチは、**受け入れられません**。許可されるターゲット依存性は、DataLayoutとTargetLibraryInfoのみです。
TargetTransformInfoの使用は、TargetTransformInfo::instCombineIntrinsic() などのターゲット固有の組み込み関数のフックに対してのみ許可されています。これらはすでに本質的にターゲットに依存しています。
コストモデリングを必要とするベクトル固有の変換の場合は、代わりにVectorCombineパスを使用できます。非常にまれな状況で、他に選択肢がない場合は、ターゲット依存の変換が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;
もう1つの例です
// 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と一致し、2番目のオペランドが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): 値が1つのユースのみを持ち、Mとも一致することを確認します。たとえば、m_OneUse(m_Add(...))です。詳細については、次のセクションを参照してください。
使用可能なマッチャーの完全なリストについては、ヘッダーを参照してください。
InstCombine API¶
InstCombine変換は、visitXYZ() メソッドによって処理されます。ここで、XYZは変換のルート命令に対応します。一致させるパターンの最も外側の命令がicmpの場合、foldはvisitICmpInst() 内のどこかに配置されます。
visitメソッドの戻り値は命令です。新しい命令を返すことも、古い命令の前に挿入し、古い命令のユースを新しい命令に置き換えることもできます。または、元の命令を返して、*何らかの*種類の変更が行われたことを示すこともできます。最後に、nullptrの戻り値は、変更が発生しなかったことを示します。
たとえば、変換によって新しいicmp命令が1つ生成される場合は、次のように記述できます
if (...)
return new ICmpInst(Pred, X, Y);
この場合、メインのInstCombineループが命令の挿入と古い命令のユースの置換を処理します。
または、次のように記述することもできます
if (...)
return replaceInstUsesWith(OrigI, Builder.CreateICmp(Pred, X, Y));
この場合、IRBuilder が命令を挿入し、replaceInstUsesWith() が古い命令のユースを置き換え、変更が発生したことを示すためにそれを返します。
どちらの形式も同等であり、コンテキストでより便利な方を使用できます。たとえば、foldがValue * を返すヘルパー関数内にあり、そのヘルパーの結果に対してreplaceInstUsesWith() が呼び出されることはよくあります。
InstCombineはワークリストを使用しており、変換中に正しく更新する必要があります。これは通常自動的に行われますが、注意すべき点がいくつかあります
Value::replaceAllUsesWith()APIを使用しないでください。代わりに、InstCombineのreplaceInstUsesWith()ヘルパーを使用してください。Instruction::eraseFromParent()APIを使用しないでください。代わりに、InstCombineのeraseInstFromFunction()ヘルパーを使用してください。（ユーザーのない副作用のない命令は自動的に削除されるため、明示的に命令を削除する必要は通常ありません。）上記の「命令を直接返す」パターンとは別に、IRBuilderを使用してすべての命令を作成します。手動で作成して挿入しないでください。
命令のオペランドまたはユースを置き換える場合は、
setOperand()の代わりにreplaceOperand()およびreplaceUse()を使用してください。
複数ユースの処理¶
変換は通常、命令の総数を増やすべきではありません。これは厳格な要件ではありません。たとえば、単一の除算命令を複数の他の命令に置き換えることは通常価値があります。
たとえば、2つの命令を2つの他の命令に置き換える変換がある場合、これは（通常）*両方*の元の命令を削除できる場合にのみ有益です。両方の命令が削除されるようにするには、内部命令に1ユースチェックを追加する必要があります。
1ユースチェックは、m_OneUse() マッチャー、または V->hasOneUse() メソッドを使用して実行できます。
汎化¶
変換は、特化しすぎる（パターンの奇妙なサブセットのみを処理し、予期しない最適化の崖につながる）と、汎化しすぎる（実世界の関連性のないケースを処理するための複雑さを導入する）の両方があります。適切な汎化レベルは非常に主観的であるため、このセクションでは大まかなガイドラインのみを提供します。
特定の定数にハードコードされた変換は避けてください。任意の定数に対する一般的なルールを理解するようにしてください。
共役パターン
スプラットされていないベクトル定数の処理は、それがコストなしでできる場合にのみ行います。コードの複雑さが増す場合は、処理を追加しないでください。
正規化されていないパターンは、特別な理由がない限り処理しないでください。たとえば、通常は別の正規形に変換されるパターンでも、複数回使用されるシナリオで発生する可能性がある場合は、処理する価値がある場合があります。具体的な現実世界の動機があれば、これを行うのは問題ありませんが、そうでない場合は、無理して行うべきではありません。
動機となるパターンが特定のプロパティを持つ定数値を使用する場合がありますが、ValueTrackingクエリを使用することで、foldを非定数値に一般化できます。これが理にかなっているかどうかはケースバイケースですが、通常は最初に定数パターンのみを処理し、後で有用と思われる場合に一般化するのが良い方法です。
レビュアー向けのガイドライン¶
コードレビューで、新しいコントリビューターにスプラットされていないベクトルのサポートを実装するように依頼しないでください。foldに対するスプラットされていないベクトルのサポートが価値があり、ポリシーに準拠している（つまり、処理によってコードの複雑さが著しく増加しない）と思われる場合は、フォローアップパッチで自分で実装してください。