ベクトル化計画¶
概要¶
ベクトル化変換は、特に外側ループ[1]だけでなく、場合によっては最内ループでも、いくつかの代替案を含む、かなり複雑になる可能性があります。これらの代替案は、正負の両方で、パフォーマンスに大きな影響を与える可能性があります。したがって、変換を一切回避するという代替案も含め、最適な代替案を特定するために、コストモデルが採用されています。
ベクトル化計画は、ベクトル化候補を記述するための明示的なモデルです。候補のコストを確実に推定することを含め、候補を最適化し、最終的にIRに変換するのに役立ちます。これにより、複数のベクトル化候補を扱うことが容易になります。
現状¶
VPlanは現在、LoopVectorizeでコード生成を駆動するために使用されています。 VPlanは、すべてのコストベースの決定と、ほとんどの合法性関連の決定が行われた後に構築されます。レシピ間のdef-useチェーンがVPlanで完全にモデル化されるようになったため、VPlanベースの分析と変換を使用して、ベクトル化プロセスを簡素化およびモジュール化しています[10]。これらには、以下のような変換が含まれます。
初期VPlanを合法化します。たとえば、リダクションとインターリーブグループに特化したレシピを導入します。
合法化されたVPlanを最適化します。たとえば、冗長なレシピを削除したり、アクティブレーンマスクを導入したりします。
アンロールとベクトル化係数固有の最適化を適用します。たとえば、VFとUFに基づいてベクトルループを反復するバックエッジを削除します。
現在の変換パイプラインの概要については、図3を参照してください。
固定順序の再帰のすべてのユーザーが並替え替え可能かどうかを確認するなど、一部の合法性チェックはVPlanですでに実行されています。これは、有効な並べ替えを適用するか、VPlanを無効としてマークしてベイルアウトするVPlanからVPlanへの変換として実装されます。
図3 2024年のVPlan変換パイプライン¶
VPlanは現在、完全なベクトルループと、ベクトル化スケルトンの追加部分をモデル化しています。 VPlanでカバーされるスコープの概要については、図4を参照してください。
図4 2024年にVPlanでモデル化されたスコープ¶
高レベル設計¶
ベクトル化ワークフロー¶
VPlanベースのベクトル化は、ベクトル化計画に「シナリオベースのアプローチ」を採用した、3つの主要なステップで構成されます。
合法化ステップ：ループを合法的にベクトル化できるかどうかを確認します。可能であれば、制約とアーティファクトをエンコードします。
計画ステップ
合法化ステップ1で決定された制約と決定に従って初期VPlanを構築し、そのコストを計算します。
VPlanに最適化を適用し、場合によっては追加のVPlanをフォークします。比較的高コストの準最適なVPlanをプルーニングします。
実行ステップ：最適なVPlanを具体化します。IRを変更するのはこのステップのみであることに注意してください。
設計ガイドライン¶
以下では、「入力IR」という用語はベクトル化装置に供給されるコードを指し、「出力IR」という用語はベクトル化装置によって生成されるコードを指します。出力IRには、ループベクトル化係数（VF）に従ってベクトル化または「ワイド化」されたコード、および/またはアンロール係数（UF）に従ってループアンロールアンドジャムされたコードが含まれています。 VPlanの設計は、いくつかの高レベルのガイドラインに従います。
分析のようなもの：VPlanの構築と操作は、入力IRを変更してはなりません。特に、最良のオプションがまったくベクトル化しない場合、ベクトル化プロセスはステップ3に到達する前に終了し、コンパイルはVPlanが構築されていないかのように続行する必要があります。
コストと実行の調整：各VPlanは、コストの推定と出力IRコードの生成の両方をサポートする必要があるため、コスト推定は生成されるコードを確実に評価します。
追加の構成体のベクトル化をサポート
複数の候補を効率的にサポートします。特に、可能なVFとUFの範囲に関連する類似の候補は、効率的に表現する必要があります。潜在的なバージョン管理を効率的にサポートする必要があります。
ストライドロードまたはストアのインターリーブグループなどのイディオムのベクトル化をサポートします。これは、「レシピ」を使用して一連の出力命令をモデル化することによって実現されます。レシピは、そのコストを計算し、そのコードを生成する役割を担います。
単一エントリ単一出口領域（SESE）をカプセル化します。ベクトル化中に、このような領域は、たとえば、述語化および線形化、またはスカラー化および述語化された命令を処理するためにVF * UF回複製する必要がある場合があります。内側ループもSESE領域としてモデル化されます。
計画ステップ2.bの一部として、命令レベルの分析と変換をサポートします。ベクトル化中に、命令をトラバース、移動、他の命令に置き換え、または作成する必要がある場合があります。たとえば、ベクトルイディオムの検出と形成には、命令パターンの検索と最適化が含まれます。
定義¶
VPlanの低レベル設計は、次のクラスで構成されています。
- LoopVectorizationPlanner：
LoopVectorizationPlannerは、ループまたはループネストのベクトル化を処理するように設計されています。 1つ以上のVPlanを構築、最適化、および破棄できます。各VPlanは、ループまたはループネストをベクトル化する明確な方法をモデル化します。最良のVFとUFを含む最良のVPlanが決定されると、このVPlanは出力IRの生成を駆動します。
- VPlan：
特定の入力IRループまたはループネストのベクトル化された候補のモデル。この候補は、階層CFGを使用して表されます。 VPlanは、コストの推定と、それが表す出力IRコードの生成の駆動をサポートします。
- 階層CFG：
ノードが基本ブロックまたは階層CFGである制御フローグラフ。階層CFGデータ構造は、タイルツリー[5]に似ています。Sharir[6]のように元の基本ブロックではなくタイルを接続するためにクロスタイルエッジが持ち上げられ、タイルのカプセル化が促進されます。ループタイリングとの混同を避けるために、タイル[5]ではなく、リージョンとブロックという用語が使用されます。
- VPBlockBase：
階層CFGの構成要素。 VPBasicBlockとVPRegionBlockの純粋仮想基底クラス。以下を参照してください。 VPBlockBaseは、他のVPBlockとの階層的な制御フロー関係をモデル化します。 IR BasicBlockとは対照的に、VPBlockBaseは、TerminatorブランチまたはVPBlockBaseを「使用する」先行ブランチではなく、制御フローの後続と先行を直接モデル化することに注意してください。
- VPBasicBlock：
VPBasicBlockはVPBlockBaseのサブクラスであり、階層CFGのリーフとして機能します。出力IR基本ブロックに連続して表示される一連の出力IR命令を表します。この基本ブロックの命令は、1つ以上のVPBasicBlockに由来します。 VPBasicBlockは、出力IR命令のコストと生成をモデル化する、ゼロ以上のVPRecipesのシーケンスを保持します。
- VPRegionBlock：
VPRegionBlockはVPBlockBaseのサブクラスです。出力IR CFGのSESEサブグラフを形成するVPBasicBlockとVPRegionBlockのコレクションをモデル化します。 VPRegionBlockは、出力IRが生成されるときに、その内容が一定回数複製されることを示している場合があります。これは、完全にアンロールされる一定のトリップカウントを持つループを効果的に表します。これは、複数の候補VFとUFの単一モデルで、スカラー化および述語化された命令をサポートするために使用されます。
- VPRecipeBase：
1つ以上の入力IR命令に基づいて、1つ以上の出力IR命令のシーケンスをモデル化する純粋仮想基底クラス。これらの入力IR命令は、レシピの「材料」と呼ばれます。レシピは、出力IR命令を生成するために材料をどのように変換するかを指定する場合があります。たとえば、一度クローン作成、複数回複製、または選択したVFに従ってワイド化されます。
- VPValue：
VPlanのdef-use関係クラス階層の基盤。インスタンス化されると、VPlanの定数またはライブイン値をモデル化します。ユーザーはVPUser型ですが、オペランドはありません。
- VPUser：
VPUserは、多数のVPValueをオペランドとして使用するエンティティを表します。 VPUserは、いくつかの点でLLVMのUserクラスに似ています。
- VPDef：
VPDefは、ゼロ、1つ、または複数のVPValueを定義するエンティティを表します。 VPlanのレシピが複数のVPValueを定義できるという事実をモデル化するために使用されます。
- VPInstruction：
VPInstructionは、単一のオペコードとオプションのフラグによって特徴付けられるレシピであり、材料やその他のメタデータがありません。 VPInstructionsは、LLVM IRのオペコードを、ベクトル化装置のセマンティクスを豊かにする慣用的な操作で拡張します。
- VPTransformState:
出力 IR の生成に使用される情報を格納し、LoopVectorizationPlanner から選択された VPlan に実行のために渡され、追加情報を VPBlock と VPRecipe に渡すために使用されます。
計画プロセスと VPlan ロードマップ¶
ループベクトル化ツールを VPlan を使用するように変換するには、段階的なアプローチに従います。まず、VPlan は最終的なベクトル化の決定を記録し、それらを実行するためにのみ使用されました。階層 CFG は計画された制御フローをモデル化し、レシピは基本ブロック内で下された決定をキャプチャします。現在、VPlan はこれらの決定を下すための基礎としても使用されており、効果的に一連の VPlan から VPlan へのアルゴリズムに変換しています。最終的に、VPlan はこれらの決定を行うためのコストベースの分析を含む計画プロセス自体をサポートし、構成的かつ反復的な意思決定を完全にサポートします。
一部の決定は、ループ内の命令に対してローカルであり、たとえば、ベクトル命令に拡張するか、複製して生成された命令をそのままにするかなどです。ただし、他の決定には、命令の移動、他の命令への置換、および/または新しい命令の導入が含まれます。たとえば、キャストは後続の命令を通過して沈み、一次の再帰を処理するために拡張される場合があります。ストライドされたギャザーまたはスキャッターのインターリーブグループは、効果的に 1 つの場所に移動し、そこでシャッフルと共通のワイドベクトルロードまたはストアに置き換えられる場合があります。マスクを計算し、ベクトルの要素をシャッフルし、スカラー値をベクトルにパックしたり、その逆を行ったりするために、新しい命令が導入される場合があります。
VPlan が命令レベルの決定と分析をサポートするには、関連する命令とその定義/使用関係をモデル化する必要があります。これも段階的なアプローチに従います。まず、マスクを計算する新しい命令は、誘導された定義/使用サブグラフとともに、VPInstructions としてモデル化されます。これは、VPlan でマスクを効果的にモデル化し、VPlan ベースの述語化を促進します。次に、VPlan 実行時に命令を生成するための各レシピに埋め込まれたロジックは、代わりにそれらを VPInstructions としてモデル化することにより、計画プロセスに参加します。最終的に、インターリーブグループや相乗効果のあるコストを持つ他のイディオムグループなど、命令のグループに適用されるロジックのみがレシピに残ります。