高性能プロセッサの分岐予測のサーベイ論文を読んで分岐予測について学ぶ (1. 分岐予測のサーベイと分類)

最近はプロセッサアーキテクチャについて再度復習しようかと思っている。

読んでいるのはA Survey of Techniques for Dynamic Branch Predictionという論文で、新規技術の解説ではないのだが、現在の有名どころの分岐予測技術についてまんべんなく解説してくれている論文だ。 これを読み進めていこうと思っている。といっても最初の方はからにGoogle翻訳に頼っているけれども。次からはもう少し自分の言葉でまとめる。

• A Survey of Techniques for Dynamic Branch Prediction
  • Sparsh Mittal

https://arxiv.org/pdf/1804.00261.pdf

---

本稿では動的分岐予測手法について概説する。 図1は、このホワイトペーパーの構成を示しています。

• 第2章 : BPに関する簡単な背景を説明し、BPを管理する上での課題について説明し、研究成果の概要を示します。
• セクション3と4では、一般的な分岐と特定の分岐用のいくつかのBPデザインについて説明し、
• セクション5ではハイブリッドBPデザインについて説明します。
• 第6節では血圧の正確性を改善するための技術について論じる。
• セクション7では、ニューラルBPとそれらの実装オーバーヘッドを削減するための手法について説明します。
• セクション8では、BPの待ち時間とエネルギーのオーバーヘッドを削減するための手法について説明します。
• 私たちは将来の課題に言及して第9章でこの論文を締めくくります。

ページ制限内で何十年ものBP調査を効果的に要約するために、我々は以下の方法でこの論文の範囲を制限しなければなりませんでした。我々は、条件付き分岐がとられるかどうかを推測する分岐方向(結果)予測に焦点を合わせる。分岐目標予測や、間接分岐または無条件分岐の手法は含みません。静的分岐予測は分岐を予測するためにソースコードの知識またはコンパイル分析のみを使用します[5]一方、動的予測は分岐の時変および入力依存実行パターンを説明します。静的予測の手法と動的BPを支援するためのコンパイラのヒントを含む手法は別の調査に値するので、ここではそれらを含めず、動的予測のみに焦点を当てます。我々は一般的に各論文の重要な考えに焦点を当てており、選択された定量的結果のみを含む。この論文は、コンピュータアーキテクト、チップ設計者、そしてパフォーマンスの最適化に興味を持っている研究者に役立つと期待されています。

2. Background and Motivation

ここでは、分類法[6]、値局所性[7]、静的BP [5]、複数BPの比較評価[2, 3, 8–10]および商用のBPについての議論[3,11-15]について議論を行います。3.1章では、BPの命令体系[6, 16]について議論します。

2.1 有用な用語と概念

分岐の種類(Types of branches)：分岐の種類

• 条件付きまたは無条件
• 直接または間接
  • 直接分岐 : 命令自体の中で目標アドレスを指定する
  • 間接分岐 : 目標アドレスが見つかるべき場所(例えばメモリまたはレジスタ位置)を指定する。

偏った分岐(Biased branches)：ほとんどの場合、分岐は実行されるか、行われないかのどちらかです。偏った分岐というのは、分岐の結果が、分岐・非分岐のどちらかに偏ったような状況を意味します。例えばfor文で、ループ中は大部分が分岐しますが、最後の1回だけは分岐せずに抜けます。このような一度だけ分岐が成立しないような分岐ケースを、偏った分岐(Biased Branches)と呼んでいます。

偏った分岐は方向に変化がないことを示すもの[17]またはパーセプトロンの重みが最大/最小値に達したもの[18]として検出されます。

エイリアシングまたは干渉(Aliasing or interference)：複数の無関係な分岐が同じ予測器エントリを使用すると、それらはエイリアシングと呼ばれる破壊的な干渉を発生させます。図2は分岐間の干渉の例を示しています。 予測が変化しない場合、干渉は中立(無害)、予測を修正する場合は正(有益)、誤予測を引き起こす場合は負(有害)です。 一般的にワーキングセットが大きくなると、有害なエイリアシングの方が無害なエイリアシングよりも影響が大きくなる。

サイドプレディクター：一般的に使用されるBP(例：TAGE [20])は、ほとんどの分岐を正確に予測できますが、他の比較的頻度の低い分岐クラスを予測することはできません。そのような分岐を予測するために、全体的な正確性を改善するために、主BPを副(補完的または補完的または修正子とも呼ばれる)BPで増強することができます。

ローカルおよびグローバルの履歴(Local and global history)：いくつかの分岐はそれら自身の実行パターンによってのみ予測することができ、したがって「ローカル」(または自己もしくは分岐ごとの)履歴に基づいて動くと言われています。たとえば、for(i = 1; i <= 4; i ++)というループ制御分岐を考えます。ループ本体の最後でループテストを実行すると、パターン$(1110)ⁿ$が表示されます。したがって、最後の3つのインスタンスの分岐の結果を知ることで、次の結果を予測できます。

比較すると、以前の分岐の実行が候補分岐の結果についてのヒントを提供できる場合、そのような分岐は相関していると言われ、この情報を利用するBPは「グローバル履歴」に取り組むと言われます。分岐相関は、複数の理由で発生する可能性があります[8, 21]。

1. 2つの分岐が関連情報によって決定されてもよく、例えば図3(a)において分岐B1が取られると、分岐B3も取られる。
2. 1つの分岐の結果が他の分岐の結果に影響を及ぼす条件を変更する、例えば図3(B)において、分岐B4が取られるとB5は取られない。この場合と前の場合が「方向相関(Directional correlation)」の例です。

1. 現在の分岐にたどり着いたパスについての情報は、相関分岐の前の分岐についてのヒントを与えてくれます。例えば、図3(c)では、分岐B8の方向は分岐B9の方向と相関していないが、分岐B8が経路上で観察された(すなわち、前のK個の分岐の1つであった)場合、分岐B9の結果は予測された。このような相関は「経路内相関(Path-based correlation)」と呼ばれる。経路履歴は現在の分岐への経路上に見られる分岐からなり、パターン履歴は現在の分岐に至った分岐の結果(方向)パターンを示す。パターン履歴と比較して、パスの履歴の使用は相関のより良い活用を可能にします[8]。

一般に、より多数の分岐を考慮すると、例えば図3(a)において、B1の結果を知るだけではB3を予測するのに十分ではなく、B1とB2の両方の結果を知ることはB3を予測するのに十分です。ニューラルBPに関するいくつかの研究では、分岐間の相関の強さの尺度としてパーセプトロン重みを使用していることに注意してください[2, 22–24]。

基本ブロック(Basic Block) : 基本ブロックは、分岐のないコードの最大長シーケンスです[25]。例外が発生しない限り、BB内の命令は常に一緒に実行されます。

評価基準(Metrics) : BPを評価するための評価基準に関しては、研究では、

• パフォーマンス(IPC)
• 予測ミスされた分岐の数(1キロ命令あたり)
• フェッチされたマイクロオペマイクロ操作ごとのフラッシュ
• 予測ミスのペナルティ[26]

などが挙げられる。

2.2 Challenges in managing BPs

以下に示すように、BPの効果的な設計と運用にはいくつかの課題があります。

• 高速な分岐予測の必要性 : 分岐予測は、分岐命令と分かってから高々1サイクル以内に予測を行う必要があり、非常にクリティカルな論理を必要とする。しかし、複雑な予測を行えば行うほど論理は増大し、クリティカルパスは長くなってしまう。クロック周波数の向上とともに、分岐予測のアクセスサイクルは1サイクルを超える場合が発生してしまう。また、分岐予測のアップデートも高速に実行する必要があり、これも性能に大きな影響を与える。
• 面積オーバヘッドと分岐予測の精度 : 分岐予測テーブルのサイズを大きくするだけでは、予測精度は向上しない。例えば、2BP + gskew BPのサイズを64kBから1MBに増やしても分岐予測の精度はほとんど向上しない。分岐予測の精度と面積オーバヘッドを考慮する必要がある。
• エネルギーオーバヘッド : 分岐予測はほぼ毎サイクルアクセスが発生するため、エネルギー消費が大きくオーバヘッドになりやすい。分岐予測器のエネルギー効率の向上は不可欠となっている。
• 分岐予測のウォームアップ : コンテキストスイッチングの発生などにより、分岐予測のウォームアップの向上は重要な要素となりうる。ウォームアップが長ければ、現代のコンテキストスイッチングの多いプロセッサでは真の効率を発揮することができないかもしれない。
• 分岐予測のタグにおける課題 : 分岐予測は失敗しても性能に影響を与えるだけで機能的な影響を与える事は無い。したがってタグを実装する必要は必ずしも無いが、エイリアシングが発生することを防ぐためにタグは必要となる。分岐予測においてタグサイズとエントリサイズと比較して必ずしも無視できるサイズではないので(キャッシュの場合はキャッシュのエントリの方がタグよりもはるかに大きいため無視できる)、タグの実装方法について考える必要がある。
• ハイブリッド分岐予測 : 分岐予測は各種予測アルゴリズムを複数動かして、そのコンポーネントから正確なものを選択する(セレクタ、もしくはチューザ)。複数の予測器から正確な予測器を選択するためのメタ予測器が必要となり、単独に予測器を使う場合に比べて有効性が低下する可能性がある。
• プロセッサ設計要因 : パイプライン化した場合、GHRを更新する前に同じアドレスに対して分岐予測が必要なる可能性があり、アウトオブオーダコアの分岐予測はインオーダのコアよりも予測精度が低くなる可能性が高い。また、パイプラインが深くなると分岐解決時間が長くなり、分岐予測ミスの可能性とコストが増大する。

LLVMのバックエンドを作るための第一歩 (29. 関数コールのサポート: Calling Conventionの定義)

今までのバックエンドの実装では、関数の取り扱いについていろいろとさぼっている部分があった。今回は、関数の定義と関数コールをきちんとサポートしようと思う。このためには、

• スタックフレームの定義
• 引数の処理

などを実装していく。

現状では、引数のある関数を定義してllcに入力すると以下のようなエラーが発生する。

• ch9_1.cpp

int gI = 100;

int sum_i(int x1, int x2, int x3, int x4, int x5, int x6)
{
  int sum = gI + x1 + x2 + x3 + x4 + x5 + x6;

  return sum;
}

int main()
{
  int a = sum_i(1, 2, 3, 4, 5, 6);

  return a;
}

./bin/clang -target mips-unknown-linux-gnu -c ../lbdex/input/ch9_1.cpp -emit-llvm
./bin/llc -march=myriscvx32 -mcpu=simple32 -relocation-model=pic -stats -filetype=asm ch9_1.bc -o -

llc: /home/msyksphinz/work/llvm/llvm-myriscvx/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp:9135: void llvm::SelectionDAGISel::LowerArguments(const llvm::Function&): Assertion `InVals.size() == Ins.size() && "LowerFormalArguments didn't emit the correct number of values!"' failed.

そこで、

• MYRISCVXTargetLowering::analyzeFormalArguments()
• MYRISCVXTargetLowering::LowerFormalArguments()
• MYRISCVXTargetLowering::MYRISCVXCC::analyzeFormalArguments()
• MYRISCVXTargetLowering::MYRISCVXCC::handleByValArg()
• MYRISCVXTargetLowering::MYRISCVXCC::numIntArgRegs()
• MYRISCVXTargetLowering::MYRISCVXCC::intArgRegs()
• MYRISCVXTargetLowering::MYRISCVXCC::fixedArgFn()
• MYRISCVXTargetLowering::MYRISCVXCC::allocateRegs()
• MYRISCVXTargetLowering::LowerCall

の変更を加える。

MYRISCVXの関数呼び出し規約

関数コールをサポートするにあたり、まず決めなければならないのはサブルーチンコールのルール、つまり呼び出し規約だ。

呼び出し規約では、関数呼び出しの規約、つまり関数コールの際の引数をどのような形で渡すのか、戻り値はどのような形式で返すのかと言う事を規定している。呼び出し規約はISAと直接関係ある訳ではなく、ソフトウェアによって独自に決めることができる。しかし、呼び出し規約が異なるバイナリどうしは互いに呼び出すことができないため、ISA毎に標準的な呼び出し規約が決められているのが一般的だ。RISC-Vでは複数の呼び出し規約が決められている。その中で、整数レジスタの動作について定義しているのはILP32だ。これは、

• 整数値の引数渡しはA0-A7レジスタを経由して渡す。それよりも多い引数はスタックを経由して渡す。
• 戻り値はA0-A1レジスタを経由して呼び出し元に戻す。

というルールだ。これをMYRISCVXの呼び出し規約としてそのまま採用する。

もう一つ、LLVMの動作を理解するために、独自の呼び出し規約を定義する。

• 全ての引数はスタックを経由して渡す。
• 戻り値はA0-A1レジスタを経由して呼び出し元に戻す。

というものである。この呼び出し規約をSTACK32と呼ぶことにする。MYRISCVXでは、この2つの呼び出し規約を実装することにする。

MYRISCVXの関数引数を渡すための2つのABI

Target Descriptionに呼び出し規約を定義する

MYRISCVXの呼び出し規約をLLVMに教えるためには、Target Description(.td)ファイルにルールを記述する必要がある。 tdファイルではMYRISCVXのレジスタなどの要素を定義しているので、これらを使ってルールを作る。 呼び出し規約は、一般的に[アーキテクチャ名]_CallingConv.tdというファイルに記述する。

まず、LP32 呼び出し規約を定義する。

• llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXCallingConv.td

//===----------------------------------------------------------------------===//
// MYRISCVX LP32 呼び出し規約
//===----------------------------------------------------------------------===//

def CC_LP32 : CallingConv<[
  // i1, i8, i16型(i32)よりも小さい型の値は、i32として取り扱う。
  CCIfType<[i1, i8, i16], CCPromoteToType<i32>>,

  // i32型の値は、A0-A7のレジスタを使って値渡しを行う。
  CCIfType<[i32], CCAssignToReg<[A0, A1, A2, A3, A4, A5, A6, A7]>>,

  // i32型のスタックを経由して渡す引数は、4バイトのスタックスロットを使用し、アドレスは4バイトにアラインする。
  CCIfType<[i32], CCAssignToStack<4, 4>>
]>;

LP32 呼び出し規約のミソは、CCIfTypeとCCAssignToRegを使用してレジスタ渡しに使用できるレジスタを指定している点だ。 A0-A7までは引数渡しのために使用できる。一方で、それ以上の引数を渡す場合はスタックを経由して渡す。 このときのルールとして、1データ分のスタックのサイズと、スタックのアドレスアラインのルールを決めている。

では、次にSTACK32 呼び出し規約を定義する。

• llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXCallingConv.td

//===----------------------------------------------------------------------===//
// MYRISCVX STACK32 呼び出し規約
//===----------------------------------------------------------------------===//

def CC_STACK32 : CallingConv<[
  // i1, i8, i16型(i32)よりも小さい型の値は、i32として取り扱う。
  CCIfType<[i1, i8, i16], CCPromoteToType<i32>>,

  // i32型のスタックを経由して渡す引数は、4バイトのスタックスロットを使用し、アドレスは4バイトにアラインする。
  CCIfType<[i32], CCAssignToStack<4, 4>>
]>;

STACK32 呼び出し規約は、LP32 呼び出し規約に比べてCCAssignToRegを使用している。 関数呼び出しの時に引数渡しをすべてスタック経由で行うのでこのような実装になっている。

最後に、2つの呼び出し規約を定義したので、これをまとめた1つの呼び出し規約を定義する。

• llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXCallingConv.td

/// CCIfSubtarget - Match if the current subtarget has a feature F.
class CCIfSubtarget<string F, CCAction A, string Invert = "">
    : CCIf<!strconcat(Invert,
                      "static_cast<const MYRISCVXSubtarget&>"
            "(State.getMachineFunction().getSubtarget()).",
                      F),
           A>;

def CC_MYRISCVX : CallingConv<[
  CCIfSubtarget<"isABI_STACK32()", CCDelegateTo<CC_STACK32>>,
  CCDelegateTo<CC_LP32>
]>;

CCIfSubtargetは、MIPSの実装から引き抜いてきた。 条件によって呼び出し規約を切り替えるためのものである。 ここでは、isABI_STACK32()がTrueならばSTACK32が有効となり、そうでなければLP32が有効となる。

LLVMのバックエンドを作るための第一歩 (30. 関数コールのサポート: LowerFormalArgumentsの実装)

関数の呼び出し規約が決まったので、関数呼び出しを含むLLVM IRを処理するフェーズに入る。 まず、LLVM IRをDAGに変換する。 LLVM IRをDAGに変換するのはMYRISCVXTaregtLowerigの仕事だ。 その中で引数の解析とDAG変換を行うための関数はLowerFormalArguments()をオーバーライドする。 LowerFormalArguments()を実装してみる。

関数の定義にあたり、2つのISELLoweringの関数を実装する必要がある。

• LowerFormalArguments() : 引数をDAGに変換する。呼び出し規約に基づいて引数の位置を決定する。つまり、
  • スタック経由で渡す引数 : フレームインデックスとスタックロード命令を定義する。
  • レジスタ経由で渡す引数 : CopyFromRegノードを生成する。
• LowerReturn() : 戻り値の処理をDAGに変換する。
  • 戻り値を探索し、それに基づいてMYRISCVXISD::Retノードを生成する。

LowerFormalArguments()の解析をする。

MYRISCVXTargetLowering::LowerFormalArguments (SDValue Chain,
                                              CallingConv::ID CallConv,
                                              bool IsVarArg,
                                              const SmallVectorImpl<ISD::InputArg> &Ins,
                                              const SDLoc &DL, SelectionDAG &DAG,
                                              SmallVectorImpl<SDValue> &InVals) const {

...
   Function::const_arg_iterator FuncArg =
      DAG.getMachineFunction().getFunction().arg_begin();
...
   CCInfo.AnalyzeFormalArguments (Ins, CC_MYRISCVX);
...

CCInfo.AnalyzeFormalArguments()で引数の解析を行っている。解析というのはつまり、関数の引数に対して

• この引数はレジスタ渡しをするのか。どのレジスタを使うのか。
• この引数はスタック渡しをするのか。スタックのアドレスは何処を使うのか。

と言う事を決定する。すべての引数についてこの情報を決めるための処理だが、実際にはAnalyzeFormalArgumentsの引数として指定したCC_MYRISCVXを呼び出している。

このCC_MYRISCVXがまさに、先ほどtdファイルに記述した関数呼び出し規約のルールを記載した関数に他なりません。これはbuild-myriscvx/lib/Target/MYRISCVX/MYRISCVXGenCallingConv.incに生成されている。

• build-myriscvx/lib/Target/MYRISCVX/MYRISCVXGenCallingConv.inc

static bool CC_MYRISCVX(unsigned ValNo, MVT ValVT,
                        MVT LocVT, CCValAssign::LocInfo LocInfo,
                        ISD::ArgFlagsTy ArgFlags, CCState &State) {

  if (static_cast<const MYRISCVXSubtarget&>(State.getMachineFunction().getSubtarget()).isABI_STACK32()) {
    if (!CC_STACK32(ValNo, ValVT, LocVT, LocInfo, ArgFlags, State))
      return false;
  }

  if (!CC_LP32(ValNo, ValVT, LocVT, LocInfo, ArgFlags, State))
    return false;

  return true;  // CC didn't match.
}

上記で説明した通り、CC_STACK32とCC_LP32が条件分岐によって使い分けられている。

static bool CC_LP32(unsigned ValNo, MVT ValVT,
                    MVT LocVT, CCValAssign::LocInfo LocInfo,
                    ISD::ArgFlagsTy ArgFlags, CCState &State) {
...

詳細はここでは掲載しないが、上記のLP32のルールと全く同じことを計算している。AnalyzeFormalArguments()の引数として渡されたCCStateが情報を記憶しておき、一つ一つの引数に対してレジスタの割り当て、もしくはスタックの割り当てを行っている。

STACK32も同様だ。こちらには、レジスタ割り当てに関する記述が入っている。

static bool CC_STACK32(unsigned ValNo, MVT ValVT,
                       MVT LocVT, CCValAssign::LocInfo LocInfo,
                       ISD::ArgFlagsTy ArgFlags, CCState &State) {
...

引数の解析が終了すると、次にDAGの生成に入る。引数の数だけループが実行されます。

  for (unsigned i = 0, e = ArgLocs.size(); i != e; ++i) {
...

レジスタ渡しの場合はあまりやることは少ないのだが、一点ほど、32ビットよりも小さな値を渡しているときに限り、呼び出し規約のルールで型の拡張を行っていました。この時には、AssertSextもしくはAssertZextノードを挿入する必要がある。このノードは2つのオペランドを持っており、1つは拡張された値そのもの、そしてもう一つは拡張前の値のビットサイズだ。

      // If this is an 8 or 16-bit value, it has been passed promoted
      // to 32 bits.  Insert an assert[sz]ext to capture this, then
      // truncate to the right size.
      if (VA.getLocInfo() != CCValAssign::Full) {
        unsigned Opcode = 0;
        if (VA.getLocInfo() == CCValAssign::SExt)
          Opcode = ISD::AssertSext;
        else if (VA.getLocInfo() == CCValAssign::ZExt)
          Opcode = ISD::AssertZext;
        if (Opcode)
          ArgValue = DAG.getNode(Opcode, DL, RegVT, ArgValue,
                                 DAG.getValueType(ValVT));
        ArgValue = DAG.getNode(ISD::TRUNCATE, DL, ValVT, ArgValue);
      }

一方、スタック渡しの場合はスタックフレームから当該引数が格納されているスタックまでの距離を計算し、それに基づいてメモリロードのノードを生成する。

      MVT LocVT = VA.getLocVT();

      // sanity check
      assert(VA.isMemLoc());

      // The stack pointer offset is relative to the caller stack frame.
      int FI = MFI.CreateFixedObject(ValVT.getSizeInBits()/8,
                                     VA.getLocMemOffset(), true);

      // Create load nodes to retrieve arguments from the stack
      SDValue FIN = DAG.getFrameIndex(FI, getPointerTy(DAG.getDataLayout()));
      SDValue Load = DAG.getLoad(
          LocVT, DL, Chain, FIN,
          MachinePointerInfo::getFixedStack(DAG.getMachineFunction(), FI));
      InVals.push_back(Load);
      OutChains.push_back(Load.getValue(1));

MYRISCVXの関数引数を渡すための2つのABI

念のため、ILP32のレジスタ渡し出来る数を1に限定して、以下のプログラムでDAGを作ってみた。

int sum_i(int x1, int x2)
{
  int sum = x1 + x2;

  return sum;
}

ILP32とSTACK32でDAGを作ってみる。赤い四角がLoad命令、青い四角がCopyToRegだ。ILP32では最初の引数がレジスタ渡しで、STACK32ではすべてスタック渡しとなっていることが分かる。

LLVMのバックエンドを作るための第一歩 (28. 分岐の際に発生する不要なジャンプを削除するPassの追加)

前回の制御構文を追加した際に、不要なジャンプ命令が発生しているのが気になる。例えば、LLVM IRをダンプし時に以下のようなIRが出力されたはずだ。この時、br label %if.endはすぐ後ろのif.endにジャンプするため、このジャンプ文は不要なはずだ。ここでは、このような不要なジャンプ命令を削除して、コードの最適化を図ってみる。

DelJmp Passにより削除する命令のパタン

if.then:                                          ; preds = %entry
  %1 = load i32, i32* %a, align 4
  %inc = add i32 %1, 1
  store i32 %inc, i32* %a, align 4
  br label %if.end

if.end:                                           ; preds = %if.then, %entry
  %2 = load i32, i32* %a, align 4
  ret i32 %2
}

最適化のPassを追加する

ここで最適化のPassを追加するのだが、マシンコードが生成される前に最適化のPassを追加する。この場合、TargetPassConfig::addPreEmitPassを通じてPassを追加する。

• llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXTargetMachine.cpp

//@MYRISCVXPassConfig {
/// MYRISCVX Code Generator Pass Configuration Options.
class MYRISCVXPassConfig : public TargetPassConfig {
 public:
...
   void addPreEmitPass() override;
...

void MYRISCVXPassConfig::addPreEmitPass() {
  MYRISCVXTargetMachine &TM = getMYRISCVXTargetMachine();
  addPass (createMYRISCVXDelJmpPass(TM));
  return;
}

createMYRISCVXDelJmpPassというPassを追加した。このPassはMYRISCVXDelUselessJMP.cppで追加する。

• llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXDelUselessJMP.cpp

#define DEBUG_TYPE "del-jmp"

STATISTIC(NumDelJmp, "Number of useless jmp deleted");

static cl::opt<bool> EnableDelJmp(
    "enable-MYRISCVX-del-useless-jmp",
    cl::init(true),
    cl::desc("Delete useless jmp instructions: jmp 0."),
    cl::Hidden);

Passの定義を行う。このPassはDelJmpというもので、デフォルトで有効だ。-enable-MYRISCVX-del-useless-jmpオプションで有効無効を制御することができる。例えば、-enable-MYRISCVX-del-useless-jmp=falseとすることでこのPassを無効化することができる。

DelJmpクラスを定義する。このクラスは、MachineFunctionPassクラスから派生している。MachineFunctionPassクラスに記述したPassは、runOnMachineFunction()関数を呼び出すことにより実行される。

virtual bool runOnMachineFunction(MachineFunction &MF) = 0;

では、DelJmpクラスのrunOnMachineFunction()関数を実装してみる。

  bool runOnMachineFunction(MachineFunction &F) {
    bool Changed = false;
    if (EnableDelJmp) {
      MachineFunction::iterator FJ = F.begin();
      if (FJ != F.end())
        FJ++;
      if (FJ == F.end())
        return Changed;
      for (MachineFunction::iterator FI = F.begin(), FE = F.end();
           FJ != FE; ++FI, ++FJ)
        // In STL style, F.end() is the dummy BasicBlock() like '\0' in
        //  C string.
        // FJ is the next BasicBlock of FI; When FI range from F.begin() to
        //  the PreviousBasicBlock of F.end() call runOnMachineBasicBlock().
        Changed |= runOnMachineBasicBlock(*FI, *FJ);
    }
    return Changed;
  }

このコードでは、マシンコードからBasicBlockをひとつづつ取り出してPassを適用するという形をとっている。FIイテレータがターゲットとなるBasic Blockを示しており、一つずらしたFJイテレータがFIの次のブロックを示している。つまり、

• FIイテレータの一番最後のコードがジャンプ命令であり、
• ジャンプ先がFJの先頭であれば、FIの最後のジャンプ命令を削除しても良い

ということになり、この処理をrunOnMachineBasicBlock()に記述している。最終的にコードの変更を行った場合は、Changed変数をTrueに設定して戻る。

bool DelJmp::
runOnMachineBasicBlock(MachineBasicBlock &MBB, MachineBasicBlock &MBBN) {
  bool Changed = false;

  MachineBasicBlock::iterator I = MBB.end();
  if (I != MBB.begin())
    I--;    // set I to the last instruction
  else
    return Changed;

  if (I->getOpcode() == MYRISCVX::J && I->getOperand(0).getMBB() == &MBBN) {
    // I is the instruction of "jmp #offset=0", as follows,
    //     j   $BB0_3
    // $BB0_3:
    //     ld  $4, 28($sp)
    ++NumDelJmp;
    MBB.erase(I);   // delete the "JMP 0" instruction
    Changed = true;    // Notify LLVM kernel Changed
  }
  return Changed;
}

runOnMachineBasicBasicBlockでは、BasicBlockMBBと次のBasicBlockMBBNを使って最適化処理を行っている。MBBの最後の命令が対象となる命令で、イテレータIで示されている。IがRISC-VのJ命令であり、さらに第1オペランドが示している先がMBBN(次のBasic Blockの先頭)であれば、削除可能だ。MBB.erase(I)により命令の削除を行い、ChangeをTrueに設定、そして最適化を行った回数を示すNumDelJmpをインクリメントする。

このNumDelJmp変数は、llcの-statsオプションにより参照することができる。

では、ここまでの変更を施したコードでLLVMをビルドしてみる。

# DelJmpPassを有効にした場合
./bin/llc -debug -march=myriscvx32 -mcpu=simple32 -relocation-model=pic -filetype=asm ch8_1_br_simple.bc -stats -o -

# DelJmpPassを無効にした場合
./bin/llc -debug -march=myriscvx32 -mcpu=simple32 -relocation-model=pic -enable-MYRISCVX-del-useless-jmp=false -filetype=asm ch8_1_br_simple.bc -o -

それぞれ生成されたコードは以下のようになる。

• DelJmpPassを無効にした場合

_Z14test_br_simplev:
        .frame  $x8,8,$x1
        .mask   0x00000000,0
        .set    noreorder
        .set    nomacro
# %bb.0:                                # %entry
        addi    x2, x2, -8
        addi    x10, zero, 0
        sb      x10, 4(x2)
        lbu     x10, 4(x2)
        andi    x10, x10, 1
        beq     x10, zero, $BB0_2
        j       $BB0_1
$BB0_1:                                 # %if.then
        addi    x10, zero, 10
        sw      x10, 0(x2)
        j       $BB0_3
$BB0_2:                                 # %if.else
        addi    x10, zero, 20
        sw      x10, 0(x2)
        j       $BB0_3
$BB0_3:                                 # %if.end
        lw      x10, 0(x2)
        addi    x2, x2, 8
        ret     x1
        .set    macro
        .set    reorder
        .end    _Z14test_br_simplev
$func_end0:

• DelJmpPassを有効にした場合

_Z14test_br_simplev:
        .frame  $x8,8,$x1
        .mask   0x00000000,0
        .set    noreorder
        .set    nomacro
# %bb.0:                                # %entry
        addi    x2, x2, -8
        addi    x10, zero, 0
        sb      x10, 4(x2)
        lbu     x10, 4(x2)
        andi    x10, x10, 1
        beq     x10, zero, $BB0_2
# %bb.1:                                # %if.then
        addi    x10, zero, 10
        sw      x10, 0(x2)
        j       $BB0_3
$BB0_2:                                 # %if.else
        addi    x10, zero, 20
        sw      x10, 0(x2)
$BB0_3:                                 # %if.end
        lw      x10, 0(x2)
        addi    x2, x2, 8
        ret     x1
        .set    macro
        .set    reorder
        .end    _Z14test_br_simplev
$func_end0:

不要なJ命令が削除されているのが分かる。不要なJ命令がどれだけ削除されたのか-statsオプションを付けて確認してみようと思う。

./bin/llc -march=myriscvx32 -mcpu=simple32 -relocation-model=pic -stats -filetype=asm ch8_1_br_simple.bc -o -

===-------------------------------------------------------------------------===
                          ... Statistics Collected ...
===-------------------------------------------------------------------------===

14 asm-printer    - Number of machine instrs printed
35 bitcode-reader - Number of Metadata records loaded
 2 bitcode-reader - Number of MDStrings loaded
 6 dagcombine     - Number of dag nodes combined
 2 del-jmp        - Number of useless jmp deleted
 4 isel           - Number of blocks selected using DAG
 4 isel           - Number of times dag isel has to try another path
 1 isel           - Number of entry blocks encountered
 8 prologepilog   - Number of bytes used for stack in all functions
 1 prologepilog   - Number of functions seen in PEI
 6 regalloc       - Number of registers assigned
 1 regalloc       - Number of identity moves eliminated after rewriting
 1 stackmaps      - Number of functions skipped
 1 stackmaps      - Number of functions visited

del-jmpPassにより、2つの命令が削除されていることが分かる。

RISC-V Workshop Zurichで発表されたOpenHWグループの概要

RISC-V Workshop Zurichで発表された、RISC-Vのオープンソースのプロセッサコアと環境を提供するためのグループ、OpenHWの概要が発表され、その資料を読んだ。

• OpenHW Group Proven Processor IP Corporate & CORE-V Overview

https://content.riscv.org/wp-content/uploads/2019/06/11.05-Rick-OConnor-OpenHW-Group-CORE-V-Launch-11June2019.pdf

https://content.riscv.org/wp-content/uploads/2019/06/11.05-Rick-OConnor-OpenHW-Group-CORE-V-Launch-11June2019.pdf より抜粋

---

OpenHWグループとは

OpenHWグループは非営利のグルーバル団体であり、ハードウェアとソフトウェアのデザイナがコラボレーションしてオープンソースコア、関連するIP、ソフトウェアなどのツールを開発するための団体である。より品質の高いオープンソースハードウェアを提供することが目的となる。

CORE-VシリーズはRISC-Vをベースとしたオープンソースのコアおよびサブシステム、そしてソフトウェアツールなどの集合体である。CORE-Vファミリは品質の高いオープンソースコアを提供することを目的とする。

• オープンソースプロセッサコアのロードマップを公式に作成する。
  • オンライン上のソースコードリポジトリとドキュメントを管理する。
  • オンラインイベントとライブイベントを通じて採択をプロモートする。
• プロセッサコアおよびハードウェア/ソフトウェアエコシステムの維持、進化、およびオープンソースライセンスを担当します。
  • ユーザーコミュニティの技術やニーズの変化に対応する
• 商標または認証マークのライセンスを管理することで、プロジェクトまたは製品がそのマークを使用できるかどうかを決定します。

メンバーシップ・コントリビュータ

• プラチナメンバ - 多くの投資＋最大3人までのアクティブなコントリビュータ
  • プラチナメンバはBoard of Directorsの選出のための投票権を持ち、テクニカルとマーケティングのワーキンググループおよびサブタスクグループの投票権を持つ。
• ゴールドメンバ - Mediumな投資 + 2人までのアクティブなコントリビュータ
  • ゴールドメンバはテクニカル・マーケティング ワーキンググループとサブタスクグループのChairの投票権を持つ。
• シルバーメンバ - Smallな投資
  • テクニカル・マーケティングワーキンググループとサブタスクグループに参加することができる。
• プラチナ・ゴールド・シルバーメンバは所属しているワーキンググループの投票権を、1人1票持っている。
• アソシエイト メンバ(投票権を持たない)
  • テクニカル・マーケティング ワーキンググループとサブタスクグループへの参加する権利を持つ。

複数の多国籍なパートナーから構成される

https://content.riscv.org/wp-content/uploads/2019/06/11.05-Rick-OConnor-OpenHW-Group-CORE-V-Launch-11June2019.pdf より抜粋

OpenHWグループの初期スポンサー

https://content.riscv.org/wp-content/uploads/2019/06/11.05-Rick-OConnor-OpenHW-Group-CORE-V-Launch-11June2019.pdf より抜粋

SoC開発に必要なコスト

• ソフトウェア、RTL設計、検証、物理設計がSoC設計に必要なコストの90%を占める。
• 高度に差別化されたIPブロックと機能であれば、この投資は問題ないが、汎用CPUはオープンソースモデルを使用することでこれらのコストを削減できないか？

どのような問題を解決しようとしているのか？

• IPの品質
  • ハーネスコミュニティ最高クラスの設計と検証の貢献
• エコシステム
  • IDE, RTOS, OSのポーティング、物理設計などが行えることを保証し、PPAのメトリクスうにおいてロードマップを作成する
• 許容された用途
  • ビジネス上、および法律上のリスクを最小化するために寛容なオープンソースライセンスとする。

RISC-VのCORE-Vファミリ

ETH ZurichのPULP Platformから、RISC-Vコアの最初の提供を受ける

• Ri5cy : 32-bit, 4ステージパイプライン, RV32IMC (https://github.com/pulp-platform/riscv)
• Ariane : 64-bit, 6ステージパイプライン, RV64IMCD (https://github.com/pulp-platform/ariane)

ワーキンググループ

• テクニカルワーキンググループ
  • コアタスクグループ
    • コアIPのロードマップをおよび各種アプリケーション向けのISAおよびマイクロアーキテクチャを定義する。
      • ロードマップに基づき、新しいコアIPなどを開発する。
  • 検証タスクグループ
    • RTLコアの産業標準のDVに対する貢献を行い、RTLの品質を保証しボリュームプロダクションを行える品質まで仕上げる。
    • System Verilogテストベンチを開発する。
      • UVMジェネレータ、ダイレクトテスト、コンプライアンステスト
    • RTLコアの品質を達成するためにどのようなターゲットのDVを開発するか、DVの開発状況をトラックする。
    • コーポレートメンバからのコントリビューションを受け入れる、個人コントリビュータからのコントリビューションを受け入れ、最適なテストセットを管理する。
  • プラットフォームタスクグループ
    • コアのハードウェアプラットフォームを定義する。
      • 組み込み(ベアメタル・RTOS)、ミッドレンジ(Linux/FreeBSD)、高性能
      • RISC-V Foundationの貢献を促進する。
    • サポートしているコア・プラットフォームのスタンダードを定義する。
    • プラットフォームのコンフォーマンステストを作成する。
    • プラットフォームのソフトウェア環境を構築する。
• マーケティングワーキンググループ
  • コンテントタスクグループ
  • イベントタスクグループ

デモンストレーション

• CORE-V NXP VEGA
  • RI5CY、Cortex-M4F、Zero-RISCY、Cortex-M0+のチップ

• CORE-V検証テストベンチ
  • Google Cloud上で動作するシステムVerilogシミュレータ
  • RISC-V CPUのゴールデンモデルとしてImperasを使用する。

• GreenWaveのCORE-Vデモ : GAP-8

• OpeSpin CORE-V

LLVMのバックエンドを作るための第一歩 (28. SELECTノードをMYRISCVXISD::SELECT_CCに変換する)

SELECTノードは以下の実装を用いてMYRISCVXISD::SELECT_CCに変換する。SELECTノードはカスタム実装に置き換え、(MYRISCVXISDではないデフォルトの)SELECT_CCはCombine時に生成しないようにする。

• llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp

MYRISCVXTargetLowering::MYRISCVXTargetLowering(const MYRISCVXTargetMachine &TM,
                                               const MYRISCVXSubtarget &STI)
...
  // SELECTノードはカスタム実装に置き換え
  setOperationAction(ISD::SELECT,    MVT::i32, Custom);
  // MYRISCVXISDではないデフォルトのSELECT_CCはCombine時に生成しない
  setOperationAction(ISD::SELECT_CC, MVT::i32, Expand);

そして、MYRISCVXTargetLowering::lowerOperation()でSELECTノードの処理をMYRISCVXTargetLowering::lowerSELECT()で処理するように仕向ける。

• llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp

SDValue MYRISCVXTargetLowering::
LowerOperation(SDValue Op, SelectionDAG &DAG) const
{
  switch (Op.getOpcode())
  {
    case ISD::SELECT           : return lowerSELECT(Op, DAG);
...

MYRISCVXTargetLowering::lowerSELECT()の実装を覗いてみる。

• llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp

SDValue MYRISCVXTargetLowering::
lowerSELECT(SDValue Op, SelectionDAG &DAG) const
{
  SDValue CondV = Op.getOperand(0);
  SDValue TrueV = Op.getOperand(1);
  SDValue FalseV = Op.getOperand(2);
  SDLoc DL(Op);

  // (select condv, truev, falsev)
  // -> (MYRISCVXISD::SELECT_CC condv, zero, setne, truev, falsev)
  SDValue Zero = DAG.getConstant(0, DL, MVT::i32);
  SDValue SetNE = DAG.getConstant(ISD::SETNE, DL, MVT::i32);

  SDVTList VTs = DAG.getVTList(Op.getValueType(), MVT::Glue);
  SDValue Ops[] = {CondV, Zero, SetNE, TrueV, FalseV};

  return DAG.getNode(MYRISCVXISD::SELECT_CC, DL, VTs, Ops);
}

ここでは、SELECTノードをMYRISCVXISD::SELECT_CCに置き換えるためのノードの組み立てを行っている。比較対象のオペランドOpとZeroをSETNEで比較し、比較結果によってTrueVとFalseVのどちらかを選択するというSELECT_CCを組み立てた。SELECTはMYRISCVXISD::SELECT_CCに置き換えられ、最終的に命令に変換されることになる。

MYRISCVXISD::SELECT_CCノードから命令を組み立てる

MYRISCVXISD::SELECT_CCノードは以下のように定義されている。MYRISCVXSelectCCというノードを作り、その制約条件をSDT_MYRISCVXSelectCCに記述する。この制約はISD::SelectCCと同様だ。

• llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXInstrInfo.td

# MYRISCVX::SELECT_CCの条件。出力ノードは1つ、入力ノードは5つ。
def SDT_MYRISCVXSelectCC   : SDTypeProfile<1, 5, [SDTCisSameAs<1, 2>,
                                               SDTCisSameAs<0, 4>,
                                               SDTCisSameAs<4, 5>]>;
# MYRISCVX::SELECT_CCを定義する。SDT_MYRISCVXSelectCCのノード制約を使用する。
def MYRISCVXSelectCC : SDNode<"MYRISCVXISD::SELECT_CC", SDT_MYRISCVXSelectCC,
                      [SDNPInGlue]>;

let usesCustomInserter = 1 in
class SelectCC_rrirr<RegisterClass RC, RegisterClass cmpty>
    : MYRISCVXPseudo<(outs RC:$dst),
             (ins cmpty:$lhs, cmpty:$rhs, simm12:$imm,
              RC:$truev, RC:$falsev),
              "",
             [(set RC:$dst,
               (MYRISCVXSelectCC cmpty:$lhs,
                         cmpty:$rhs,
                         (i32 imm:$imm),
                         RC:$truev,
                         RC:$falsev))]>;

def Select_GPR_Using_CC_GPR : SelectCC_rrirr<GPR, GPR>;

このMYRISCVXSelectCCを用いてパタンを作成する。比較対象のcmpty:$lhs, cmpty:$rhsに対して比較結果がTrueの場合にはRC:$truevが、不成立の場合にはRC:$falsevが選択され出力RC:$dstが返されるようにしている。ただし、このままではどのような比較演算が実行されるのかが分からない。これは、実際にCコード側で組み立てていくことになる。

このとき、このusesCustomInserterがとても大切になる。これは、この変換後に作られたMYRISCVXSelectCCのIRを、手動で変換する処理が入る、という印になる。逆に言うと、このusesCustomInserterを置いておかないと、後続の命令変換の最中にSELECT_CCを変換することができないとしてエラーが出力されてしまうのだ。

以下に、MYRISCVXISD::SELECT_CCを具体的な命令に置き換える実装を示す。

3項演算子を実現するので、以下のようなフローになる。

1. 比較演算が成立した場合の値を、Destination Registerに格納しておく。
2. 比較演算を実行する。
3. 比較結果がFalseであれば、Destination RegisterにFalse側の値を格納する。

このため、大きく分けて以下のマシンコードブロックを作成する。

• HeadMBB : 先頭のブロック(与えられたMachineBasicBlock *BBに相当)
• TailMBB : 3項演算子ブロックの末尾。TrueでもFalseでも最終的にここに飛んでくる。

• IfFalseMBB : 比較結果がFalseである場合飛んでくる。False時の値を設定する。

• llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp

MachineBasicBlock *
MYRISCVXTargetLowering::EmitInstrWithCustomInserter(MachineInstr &MI,
                                                    MachineBasicBlock *BB) const {

  const TargetInstrInfo &TII = *BB->getParent()->getSubtarget().getInstrInfo();
  const BasicBlock *LLVM_BB = BB->getBasicBlock();
  DebugLoc DL = MI.getDebugLoc();
  MachineFunction::iterator I = ++BB->getIterator();

  MachineBasicBlock *HeadMBB = BB;
  MachineFunction *F = BB->getParent();
  MachineBasicBlock *TailMBB = F->CreateMachineBasicBlock(LLVM_BB);
  MachineBasicBlock *IfFalseMBB = F->CreateMachineBasicBlock(LLVM_BB);

  F->insert(I, IfFalseMBB);
  F->insert(I, TailMBB);
  // Move all remaining instructions to TailMBB.
  TailMBB->splice(TailMBB->begin(), HeadMBB,
                  std::next(MachineBasicBlock::iterator(MI)), HeadMBB->end());
  // Update machine-CFG edges by transferring all successors of the current
  // block to the new block which will contain the Phi node for the select.
  TailMBB->transferSuccessorsAndUpdatePHIs(HeadMBB);
  // Set the successors for HeadMBB.
  HeadMBB->addSuccessor(IfFalseMBB);
  HeadMBB->addSuccessor(TailMBB);

  // Insert appropriate branch.
  unsigned LHS = MI.getOperand(1).getReg();
  unsigned RHS = MI.getOperand(2).getReg();
  auto CC = static_cast<ISD::CondCode>(MI.getOperand(3).getImm());
  unsigned Opcode = getBranchOpcodeForIntCondCode(CC);

  BuildMI(HeadMBB, DL, TII.get(Opcode))
    .addReg(LHS)
    .addReg(RHS)
    .addMBB(TailMBB);

  // IfFalseMBB just falls through to TailMBB.
  IfFalseMBB->addSuccessor(TailMBB);

  // %Result = phi [ %TrueValue, HeadMBB ], [ %FalseValue, IfFalseMBB ]
  BuildMI(*TailMBB, TailMBB->begin(), DL, TII.get(MYRISCVX::PHI),
          MI.getOperand(0).getReg())
      .addReg(MI.getOperand(4).getReg())
      .addMBB(HeadMBB)
      .addReg(MI.getOperand(5).getReg())
      .addMBB(IfFalseMBB);

  MI.eraseFromParent(); // The pseudo instruction is gone now.
  return TailMBB;
}

EmitInstrWithCustomInserter()の中で比較とその結果に基づく選択の命令を抽出する。まず左右の条件どうしを比較する命令を作成する。

  BuildMI(HeadMBB, DL, TII.get(Opcode))
    .addReg(LHS)
    .addReg(RHS)
    .addMBB(TailMBB);

OpCodeはgetBranchOpcodeForIntCondCode()で選択する。比較演算によって条件分岐命令を選択しているが、つまりBEQ LHS, RHS, TailMBBという命令を組み立て、LHSとRHSの比較を行っている。

次に、PHIノードを組み立てる。PHIノードはざっくりと説明すると、「飛んできたブロックによって選択する値を選ぶ」というノードだ。上記の比較命令により、LHSとRHSの比較結果がTrueである場合TailMBBに飛ぶ訳だが、そうでない場合は、HeadMBBからIfFalseMBBに飛ぶわけだので、

  HeadMBB->addSuccessor(IfFalseMBB);

IfFalseMBBから来た場合はオペランド5(False時の値)、そうでなくHeadMBBから来た場合はオペランド4(True時の値)を選択するようにPHIノードを構築している。これは最終的に分岐命令に分解され、命令が出力される。

  BuildMI(*TailMBB, TailMBB->begin(), DL, TII.get(MYRISCVX::PHI),
          MI.getOperand(0).getReg())
      .addReg(MI.getOperand(4).getReg())
      .addMBB(HeadMBB)
      .addReg(MI.getOperand(5).getReg())
      .addMBB(IfFalseMBB);

MYRISCVXISD::SELECTを変換したときのDAGグラフ

再ビルドを行い、上記のサンプルプログラムを動かした時の出力結果は以下のようになる。

# %bb.0:                                # %entry
        addi    x2, x2, -8
        addi    x10, zero, 1
        sb      x10, 4(x2)
        addi    x12, zero, 0
        sw      x12, 0(x2)
        lbu     x10, 4(x2)
        andi    x13, x10, 1
        addi    x11, zero, 20
        addi    x10, zero, 10
        bne     x13, x12, $BB0_2
# %bb.1:                                # %entry
        addi    x10, x11, 0
$BB0_2:                                 # %entry
        sw      x10, 0(x2)
        lw      x10, 0(x2)
        addi    x2, x2, 8
        ret     x1

LLVMのバックエンドを作るための第一歩 (27. 3項演算子のためのSELECTノードの処理)

3項演算子をコンパイルしてみると、以下のようなLLVM IRが生成されることが分かる。

int test_movx_1()
{
  volatile int a = 1;
  int c = 0;

  c = !a ? 1:3;

  return c;
}

./bin/clang --target=mips-unknown-elf ../lbdex/input/ch8_2_select.cpp -c -emit-llvm
./bin/llvm-dis ch8_2_select.bc -o -

...
  %lnot = xor i1 %tobool, true
  %1 = zext i1 %lnot to i64
  %cond = select i1 %lnot, i32 1, i32 3
...

SELECTノードが生成されている。SELECTノードはそのまま3項演算子で、これをそのままRISC-Vの命令に変換できればいいのだが、RISC-VにはConditional Moveのような命令が存在しないので別の命令に変換しなければならない。

SEELCT	SELECT (COND, TRUEVAL, FALSEVAL). 3項演算子を構築する。 引数1. 1ビットの整数 引数2. 引数1がTrueの場合に選択される値 引数3. 引数1がFalseの場合に選択される値 選択される値(引数0)と、TRUEVAL、FALSEVALはすべて同じ型でなければならない。

3項演算子を実現するためには単純に命令の置き換えで実現できないので、分岐命令を活用する必要がありる。そのためにはラベルを作成したり、複雑な処理が必要なので、ノードの生成はC++で実装することにする。

もう一つ、SELECTノードに似ているノードとしてSELECT_CCというノードが存在する。SELECT_CCはより複雑で、比較対象のオペランドの指定、比較命令、True時、False時の選択するオペランドを設定できる。

SELECT_CC	SELECT_CC (LHS, RHS, TRUEVAL, FALSEVAL, OP) 3項演算子だ。LHSとRHSをOPで比較し、比較結果がTrueならばTRUEVALを返し、比較結果がFALSEならばFALSEVALを返する。 引数1. 比較オペランド1 引数2. 比較オペランド2 引数3. 比較結果がTrueである場合の選択される値 比較4. 比較結果がFalseである場合の選択される値 引数5. 比較演算 選択される値(引数0)と、TRUEVAL, FALSEVALはすべて同じ型でなければならない。 比較オペランド1と比較オペランド2は同じ型でなければならない。

SELECTとSELECT_CC、両方対応しても良いのだが、SELECT_CCに対応しておき、SELECTはSELECT_CCに変換する、という作戦を取ろうと思う。以下のようにSELECTノードはSELECT_CCに変換されるようにする。

Successfully custom legalized node
 ... replacing: t13: i32 = select t23, Constant:i32<10>, Constant:i32<20>
     with:      t26: i32,glue = MYRISCVXISD::SELECT_CC t23, Constant:i32<0>, Constant:i32<22>, Constant:i32<10>, Constant:i32<20>

SELECT(t23, 10, 20)というノードが、SELECT_CC (t23, 0, OP, 10, 20)に変換されていることが分かる。

SELECTノードをMYRISCVXISD::SELECT_CCに変換する

SELECTノードは以下の実装を用いてMYRISCVXISD::SELECT_CCに変換する。SELECTノードはカスタム実装に置き換え、(MYRISCVXISDではないデフォルトの)SELECT_CCはCombine時に生成しないようにする。

• llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp

MYRISCVXTargetLowering::MYRISCVXTargetLowering(const MYRISCVXTargetMachine &TM,
                                               const MYRISCVXSubtarget &STI)
...
  // SELECTノードはカスタム実装に置き換え
  setOperationAction(ISD::SELECT,    MVT::i32, Custom);
  // MYRISCVXISDではないデフォルトのSELECT_CCはCombine時に生成しない
  setOperationAction(ISD::SELECT_CC, MVT::i32, Expand);

そして、MYRISCVXTargetLowering::lowerOperation()でSELECTノードの処理をMYRISCVXTargetLowering::lowerSELECT()で処理するように仕向ける。

• llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp

SDValue MYRISCVXTargetLowering::
LowerOperation(SDValue Op, SelectionDAG &DAG) const
{
  switch (Op.getOpcode())
  {
    case ISD::SELECT           : return lowerSELECT(Op, DAG);
...

MYRISCVXTargetLowering::lowerSELECT()の実装を覗いてみる。

• llvm-myriscvx/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp

SDValue MYRISCVXTargetLowering::
lowerSELECT(SDValue Op, SelectionDAG &DAG) const
{
  SDValue CondV = Op.getOperand(0);
  SDValue TrueV = Op.getOperand(1);
  SDValue FalseV = Op.getOperand(2);
  SDLoc DL(Op);

  // (select condv, truev, falsev)
  // -> (MYRISCVXISD::SELECT_CC condv, zero, setne, truev, falsev)
  SDValue Zero = DAG.getConstant(0, DL, MVT::i32);
  SDValue SetNE = DAG.getConstant(ISD::SETNE, DL, MVT::i32);

  SDVTList VTs = DAG.getVTList(Op.getValueType(), MVT::Glue);
  SDValue Ops[] = {CondV, Zero, SetNE, TrueV, FalseV};

  return DAG.getNode(MYRISCVXISD::SELECT_CC, DL, VTs, Ops);
}

ここでは、SELECTノードをMYRISCVXISD::SELECT_CCに置き換えるためのノードの組み立てを行っている。比較対象のオペランドOpとZeroをSETNEで比較し、比較結果によってTrueVとFalseVのどちらかを選択するというSELECT_CCを組み立てた。SELECTはMYRISCVXISD::SELECT_CCに置き換えられ、最終的に命令に変換されることになる。