[下書き] LLVMバックエンド開発文書 for RV32Kv1

参照先[9]のパッチのとおりに書き換える。 基本的に riscv32 という文字列を検索し、都度 rv32k の項目を追加していけばよい。 ただし、RISC-Vには32bit（ riscv32 ）と64bit（ riscv64 ）の変種があるため変換テーブルを用意する必要があるが、 RV32Kにはその必要はない。 UnknownArch を返せば良い。

コードを改変した後 $ bin/llvm-lit -s --filter "Triple" test でテストを行う。

[13]を参考にファイルを書き換える。 途中 llvm-objdump.cpp の書き換え該当箇所が見当たらない。とりあえず放置（TODO）。

出力するELF形式のテストは、出力すべきELFの細部が決まっていないため、 とりあえず書かないでおく（TODO）^[1]。

[14]を参考にファイルを修正・追加する。 ただし RV32KTargetMachine::RV32KTargetMachine() の初期化子で使用している getEffectiveCodeModel() がそのままではコンパイルエラーを出すため修正する^[2]。

ファイル中のライセンス条項などは、将来的にはApache 2.0 Licenseを明記する予定だが、 とりあえず削除しておく^[3]。

さて追加したバックエンドも含めてLLVMの再ビルドを行う。 そのためには再び cmake を実行する必要がある：

無事 llc --version にRV32Kが含まれるようになった：

LLVMのDSLであるTableGenを使用し、RV32Kのレジスタや命令について記述する。 追加すべきTableGenファイルは次の通り：

RISCV ディレクトリ以下に RISCVInstrFormatsC.td や RISCVInstrInfoC.td などがあるので参考にする。 LWSP はエンコードされると SP の情報を持たないが、表記上は lwsp rd, 100(sp) と書くため SP をとる必要がある。 これのために RegisterClass として SP を定義している。ただし SP には X2 のみが所属する。 また、単純に全てのレジスタを GPR として1つの括りにしてしまうと、 sub 命令のオペランドとして x2 などが許容されてしまう。 これを防ぐため、 x8 から x15 を束ねて GPRC という名の RegisterClass を作成し、これを sub 命令のオペランドの型として指定する。

即値を単純にとる命令はそのまま記述すればよいが、デコードした値を左シフトするような命令は注意が必要である。 すなわち即値の [7:2] のみを生成コード中に持つような場合は Instruction 中に8bitの即値を宣言し、 その [7:2] 部分が Inst と対応するという形をとる。 なお、この点について RISCVInstrFormatsC.td に書いてある RVInst16CJ の実装が間違っている気がする。 offset は12bitではなかろうか（TODO [RVInst16CJ-offset]）。また Bcz も同様の問題があるように見える（TODO）。

文字列リテラル中の変数展開をTableGenはサポートしている。すなわち "$rd, ${imm}(${rs})" と書けばレジスタ rd や rs、 即値 imm の中身が展開される。 なおここで変数名を {} で囲む必要がある。というのもTableGenでは ( や ) もオペランドの名前として認識されてしまうからだ。 実際 $rd, $imm(${rs}) と書くと次のようなエラーになる。

なおここでの表記はパーズの際に行うパターンマッチのパターンとしての役割と、 アセンブリとして出力を行う際のパターンとしての役割があるようだ（TODO: ほんまか？）。

2アドレス方式などで、読み込むレジスタと書き込むレジスタが一致する場合 let Constraints = "$rd = $rd_wb"; などと書けばよい。

必要なTableGenファイルを追加した後、これらのTableGenファイルが正しいかどうか llvm-tblgen を用いて確認する：

初めて実行すると、おそらくたくさんエラーがでるので頑張って全て修正する。 変換が成功した場合、生成されたコードが、自分が得たいものになっているかどうかを確認する。

RV32KのELF形式オブジェクトファイルを出力できるようにする。そのために LLVMInitializeRV32KTargetMC() を実装する。 MCTargetDesc サブディレクトリを作成し、その中に RV32KMCTargetDesc.{cpp,h} を作成する。 他のファイルに依存する部分はコメントアウトして、適当な CMakeLists.txt や LLVMBuild.txt を作成・編集すると、 ビルドが通るようになる。そこで次に実装すべき場所を次のように特定する：

この場合 AsmInfo が次に実装すべき場所だと分かる。

具体的な編集方法はパッチ[15]を参考にする。

RV32KAsmBackend.cpp の作成時に多くのコンパイルエラーが出た。どうやらこのあたりの仕様変更があったようだ。 具体的には下記のとおりである。

以上を実装して動かすとSEGVで落ちる。デバッガで追いかけると、どうやら MCSubtargetInfo の生成関数である createRV32KMCSubtargetInfo を実装しなければならないようだ。RISC Vの最新のソースコードを参考に実装する。 基本的にはTableGenが生成する createRV32KMCSubtargetInfoImpl をそのまま使えば良いが、これを使用するためには CMakeLists.txt に tablegen(LLVM RISCVGenSubtargetInfo.inc -gen-subtarget) を追加する必要があるため注意が必要だ。 ちなみにRISC Vのパッチ群では、これらは[16]で実装されている。なぜここで実装しなければならなくなったかは、よくわからない。

諸々実装すると、次のように出力される：

なお createRV32KMCCodeEmitter を実装しなくてもこの表示が出るが、それでいいのかはよくわからない。 とりあえずパッチ[15]にある分は全て実装する。

createRV32KMCCodeEmitter を実装する過程で、TableGenがどのように InstrFormats でのフィルード名と InstrInfo での ins と outs の名前を対応付けるのか調べた。例えば次のように BEQZ 命令をTableGenにて宣言したとする。

このときこのTableGenソースコードは期待通りに動かない（多分：TODO）。 なぜなら class RVInstCB で指定した offset と rs1 が、 def で指定した $rs1 と $imm に対応しないからである。 TableGenの実装^[6]や ドキュメント[17]によると、これらを対応させる方法には2種類ある：

上の例では RVInstCB では offset が先に宣言されているにも関わらず、 BEQZ では $rs1 を先に使用した。 この結果 $rs1 には offset と rs1 の両方が結びつくことになる^[8]。 なおこのような重複が発生してもTableGenは特に警告等を表示しないようだ。よくわからない ^[9]。

RV32KMCCodeEmitter::encodeInstruction 内で使用している support::endian::Writer<support::little>(OS).write(Bits); はそのままでは通らない。 RISC Vを参考に support::endian::write<uint16_t>(OS, Bits, support::little); としておく。

アセンブリをパーズするための RV32KAsmParser を追加する。これによってアセンブリをオブジェクトファイルに直すことができるようになる。 新しく AsmParser ディレクトリを作成し、その中に RV32KAsmParser.cpp 及びそれに付随するファイルを作成する。 例によって、パッチ[19]を参考に実装をすすめる。

RV32KAsmParser.cpp に記述するコード量がそれなりにあるため少々面食らうが、 要するに RV32KAsmParser と RV32KOperand の2つのクラスを作成し、実装を行っている。 パーズの本体は RV32KAsmParser::ParseInstruction である。これを起点に考えれば、それほど複雑な操作はしていない。

即値に関して SImm6 を SImm12 に直す必要がある。これらはTableGenが生成するコードから呼ばれるようだ。

ところでRV32Kの命令には add などレジスタを5bitで指定する命令と、 sub などレジスタを3bitで指定する命令の2種類がある。エンコードに際して、これらの区別のための特別な処理は必要ない。 というのも、3bitでレジスタを指定する場合その添字の下位3bit以外が無視されるため、 結果的に正しいコードが出力される^[10]。 例えば x8 を指定すると、これに 1000 という添字が振られ、4bit目を無視することで 000 となるため、 3bitでのレジスタ指定方法として正しいものになる。

そうこうしていると簡易的なアセンブラが完成する：

0x34から0x3dにある 8d 44 86 85 89 8c 06 94 01 00 が出力であり、 正しく生成されていることが分かる^[11]。 We made it!

テストを書くために、まずRV32Kのためのinstruction printerを作成する。 これは内部表現である MCInst から文字列表現であるアセンブリに変換するための機構である。 この後で作成するテストでは、アセンブリを MCInst に変換した上で、 それをアセンブリに逆変換したものがもとのアセンブリと同じであるか否かでテストを行う。

まず例によって InstPrinter ディレクトリを作成した後、適切に CMakeLists.txt や LLVMBuild.txt を作成・編集する。 また RV32KInstPrinter を作成するための関数を LLVMInitializeRV32KTargetMC にて登録する必要がある。

その後 InstPrinter/RV32KInstPrinter.{cpp,h} を作成する。 いつものようにこれはパッチ[20]を参考にして行う。

RV32KInstPrinter::printRegName の実装で用いる getRegisterName の第二引数に 何も渡さなければAltNameを出力に使用する。第二引数に RV32K::NoRegAltName を渡すことで、 レジスタを X0, X1, …​ と表示することができる。

上記をビルドした後、 実際にアセンブリを MCInst に変換し、さらにそれをアセンブリに戻すには、 llvm-mc を用いる：

-show-encoding を指定することよって当該アセンブリがどのような機械語に 翻訳されるか確認することができる。テストではこの機械語の正誤も確認する。

簡易アセンブラが正しく動作していることを保証するためにテストを書く。 ここでは「適当な入力を与えたときに正しく解釈し正しい機械語を生成するか」を確認する。

前節と同様にパッチ[20]を参考に記述する。 まず test/MC/RISCV ディレクトリを作成する。 その中に rv32k-valid.s と rv32k-invalid.s を作成し、 前者で正しいアセンブリが適切に処理されるか、 後者で誤ったアセンブリに正しくエラーを出力するかを確認する。

記述後 llvm-lit を用いてテストを行う：

テストに通っていることが分かる。YATTA!

lw 命令は7bit符号なし即値をとる。この即値の下位2ビットは0であることが要求される。 この即値はアセンブリ中でもLLVM内部でも7bitのまま保持される。

ParserMatchClass は AsmParser がどのようにそのオペランドを読めばよいか指定する。 TableGenで直接指定できない性質は EncoderMethod などを用いてフックし、C\++側から指定する[23]。

uimm8_lsb00 の let EncoderMethod = "getImmOpValue"; は一見不思議に見えるが正常で、 ここでえられた即値は lw の imm になり、そちらで整形される。 だが simm12_lsb0 は getImmOpValueAsr が指定されるので offset は12bitではなく11bitになっている。

uimm8_lsb00 をつくると RV32KOperand::isUImm7Lsb00 が無いと言われるので追加する必要がある。 この UImm7Lsb00 という名前は ImmAsmOperand の Name に従って作られているようだ。

generateImmOutOfRangeError の実装に使われているおもしろデータ構造 Twine は 文字列の連結を二分木で持つことで高速に行うことができるらしい[24]。

メモリ表記のアセンブリをパーズするためには RV32KAsmParser を変更する必要がある。 この処理のエントリポイントは parseOperand で、ここから parseMemOpBaseReg を呼び出す。

li x11, x12, x13 というアセンブリを流し込むと invalid operand for instruction を期待 しているにもかかわらず immediate must be an integer in the range [-32, 31] と出てしまう。 LW を追加する前はそのメッセージが出ていたのでいろいろ調査したが原因不明。 git stash してもとのコードをテストしてみると、実際には

となっている。すなわちエラーが発生している位置がずれている。もとからおかしかったのだ。 おそらくこれは将来的に解決されるだろうという判断のもと保留（TODO）。

テストを忘れずに追加してコミット。

ところで getImmOpValue はオペランドにある即値をそのまま返す関数であり、 即値の EncoderMethod にフックとして使用する。 しかしこれは simm6 の実装時には不要であり、 実際 let EncoderMethod = "getImmOpValue"; をコメントアウトしてもテストには通る。 [22]では getImmOpValueAsr1 のみが実装されている。 RISC Vの最終的なコードで getImmOpValue は、即値として使えるような複雑な命令を解釈している。

lw 命令を追加する際に諸々を整えたので、やるだけ。

tdファイルに lwsp を追加してビルドしようとすると次のようなエラーが出た。

どうやら imm が6bit即値として扱われているようだ。原因を探すと RVInstCI 内で imm を 6bitと定義していたことが原因だったようだ。RISC V側での実装に合わせ、これを10bitに変更する。 同様に RVInstCI である li の定義も変更し、即値については各々の def で適切に処理するようにした。

sp を用いたテストを書くと、出力時にこれが x2 に変換されてしまうためにエラーになってしまう。 RegisterInfo.td の RegAltNameIndices の定義を変更しAltNameで出力をまかなえるようにした上で、 RV32KInstPrinter::printRegName の実装を改変した。

tdファイルに swsp を追加するだけ。

RISC Vの仕様上 c.j 命令は12bitの即値フィールドを持つ。 しかしLLVMのRISC Vバックエンド実装では RVInst16CJ は11bitの即値を持つ。 これは末尾1bitが必ず0であるために（ lsb0 ）この1bitを捨てることができるためである。 しかしこの実装は lw などがとる即値をそのままのビット数でデータを持つことと一貫性がないように 見受けられる。そこでRV32K実装では j 命令などもすべてそのままのビット数でデータを持つことにする。 したがって simm12_lsb0 などに指定する EncoderMethod は getImmOpValueAsr1 ではなく simm6_lsb00 と同様の getImmOpValue となる。

やるだけ。

isBranch やら isTerminator やら hasSideEffects やらを命令毎にちゃんと設定する。 これはアセンブラでは意味をなさないが、コンパイラ部分を作り始めると重要になるのだろう。多分（TODO: ほんまか？）。

ところでどのような属性フィールドがあるのかはリファレンスを読んでも判然としない。 TableGenのソースコードを読みに行くと llvm/utils/TableGen/CodeGenInstruction.h にて 属性のための大量のフラグが定義されているが、各々がどのような目的で使用されるかは書いていない。 llvm/include/llvm/CodeGen.h に mayLoad や isTerminator ・ isBarrier などの一部分のフラグについて説明がある一方、 hasSideEffects などのフラグについては説明がない。

hasSideEffects は llvm/lib/Target/RISCV/RISCVInstrInfoC.td の中で C_UNIMP と C_EBREAK でのみ 1 に設定されている。 特殊な事象が起こらない限り 0 にしておいて良さそうだ。

class や def の中に let field = value; と書くのと、外に let field = value in …​ ないし let field = value in { …​ } と書くのは同じ効果を持つが、外に書くと複数の class ・ def にまとめて効果を持つという点においてのみ異なる[25]。

class の段階で hasSideEffects などについて列挙するのは、あまりよいスタイルと思えない。 というのもRV32CなどのISAでは、エンコーディングフォーマットが同じでも全く違う意味をもつ命令を 意味することが往々にしてあるからだ。また我々の開発のように後々ISAを変更することが半ば確定している状況において、 class と複数の def におけるフラグの整合を保ちつつ変更するのは骨が折れる。 それなら class はビットパターンのみを扱うものとし、 def にその意味的な部分（フラグの上げ下げ）を書くほうが、後々の拡張性を考えるとよいと思う^[12]。

RV32KRegisterInfo.td において GPRC は X8 から X15 までの汎用レジスタを指し、 GPR は X1 と X2 を含むすべてのレジスタを指すように定義されている。 RV32Kの命令のうち3bit幅でレジスタ番号を指定する命令には GPRC を用い、 5bit幅でレジスタ番号を指定する命令には GPR を用いるようにすることで、 LLVMに適切なレジスタを教えることができる。

この別はディスアセンブラを開発する段になって重要になる。というのも、バイナリ中にレジスタ番号として 1 と出てきた場合、 このオペランドが GPR か GPRC かによって指すレジスタが x1 または x9 と異なるからである。

*_lsb0 や *_lsb00 の取り回しがよくわからなくなったので整理^[14]する。 TableGenで指定するビットによって、即値のどの部分をどのように命令コード中に配置するかを決定することができる。 これによって RV32KCodeEmitter::getImmOpValueAsr1 などの EncoderMethod に頼る必要がなくなる。 同様にディスアセンブラについても RV32KDisassembler::decodeSImmOperandAndLsl1 などの DecoderMethod に 頼る必要がなくなる。言い換えれば、これらのフック関数が受け取る即値は、TableGenで指定したビット単位の エンコード・デコードをすでに受けた値になる^[15]。 RV32KAsmParser::isUImm12 などが呼び出す getConstantImm が返す即値も同様である。

ナイーブに実装すると lwsp や swsp が入ったバイナリをディスアセンブルしようとしたときに エラーがでる。これは例えば次のようにして確認することができる。

原因は lwsp や swsp がアセンブリ上はspというオペランドをとるにも関わらず、 バイナリにはその情報が埋め込まれないためである。このためディスアセンブル時に オペランドが一つ足りない状態になり、配列の添字チェックに引っかかってしまう。

これを修正するためには lwsp や swsp に含まれる即値のDecoderが呼ばれたときをフックし、 sp のオペランドが必要ならばこれを補えばよい^[16]。 この関数を addImplySP という名前で実装する。ここで即値をオペランドに追加するために呼ぶ Inst.addOperand と addImplySP の呼び出しの順序に注意が必要である。 すなわち LWSP を RV32KInstrInfo.td で定義したときのオペランドの順序で呼ばなければ lwsp x11, sp(0) のようなおかしなアセンブリが生成されてしまう。

ちなみにエンコード方式にコンフリクトがある場合はビルド時に教えてくれる。

これを防ぐためには、もちろん異なるエンコード方式を指定すればよいのだが、 他にディスアセンブル時に命令を無効化する方法としてTableGenファイルで isPseudo = 1 を指定して疑似命令にしたり isCodeGen = 1 を指定してコード生成時にのみ効力を持つ 命令にすることなどができる。

RV32KFixupKinds.h を新規に作成し enum Fixups を定義する。 RV32Kv1では beqz ・ bnez がとる8bitの即値と j ・ jal がとる11bitの即値のために 必要なFixupを定義する。 なお enum の最初のフィールドには FirstTargetFixupKind を設定し、 最後のフィールドは NumTargetFixupKinds として、定義した enum のフィールドの個数を設定する。

Fixupの種類からその情報を返すのは RV32KAsmBackend::getFixupKindInfo が行う。 ここでの offset の値は、Fixupのために得られた即値を何ビット左シフトするかを意味し、 bits は TODO を意味している。そこで、即値のフィールドが命令中で2つに分かれている命令のためのFixup である fixup_rv32k_branch では offset と bits を各々 0 と 16 にしておく ^[17]。

要するに RV32KAsmBackend::applyFixup の実装である。補助関数として adjustFixupValue も実装する ^[18]

AsmParser と CodeEmitter を書き換え、必要なときにアセンブラにFixupを生成させるようにする。

さてRISC Vでは %hi や %lo などが使えるために、これらを評価するための機構として RISCVMCExpr を導入している。 具体的には RISCVAsmParser::parseImmediate でトークンに AsmToken::Percent が現れた場合に RISCVAsmParser::parseOperandWithModifier を呼び出し、この中でこれらをパーズして RISCVMCExpr を生成している。

しかしRV32Kではこれらの % から始まる特殊な即値^[19] に対応せず^[20]、あくまで分岐命令の即値におけるラベルのFixupのみが行えれば十分である。 ^[21]。

そこでまず isSImm9Lsb0 などにシンボルが来た場合には true を返すようにする。 これはすなわち、即値を指定するべきところにラベル名が来た場合は true とするということである ^[22]。 その次に getImmOpValue を変更し、即値を書くべき場所にシンボルが来ている場合にはFixupを生成するようにする。 このとき fixup_rv32k_branch と fixup_rv32k_jump のいずれを発行するかは、 オペランドの種類で switch-case して判断している。 これは良くないコーディングスタイルであり、実際[28]ではこれを避けるために 種々のInstFormatに手を加えるとはっきり書いてあるのだが、ここでは作業の単純さを重視して ハードコーディングすることにする。

それから RV32KAsmParser::parseImmediate を変更し AsmToken::Identifier が来たときには MCSymbolRefExpr を生成するようにしておく。この変更は[22]に含まれていたものだが、 取り込み忘れていた。

RV32KELFObjectWriter::getRelocType を実装すればよいのだが、実のところRV32Kにおけるrelocationはほとんど想定おらず、 仕様も決まっていない。そこでここでは実装を省略する。

.space を使って適当に間隔を開けながら命令を並べ、正しく動作しているかを確かめる。

これでアセンブラ部分は終了。We made it!

update_llc_test_checks.py を使用するために必要な変更らしい。RISCVのための記述を参考にしながら追記すれば良い。

とりあえずLLVM IRに近いところから実装していくことにする。 RV32KTargetLowering はLLVM IRを SelectionDAG に変換するためのクラスである。 RV32KISelLowering.{h,cpp} で定義される。

まずこのクラスのコンストラクタで、ターゲットの仕様を指定する。

次いでメンバ関数の LowerFormalArguments で関数呼び出し時の引数の扱いについて記述する。 ここでは引数はすべてレジスタ経由で渡されることにする。 その場合、使用するレジスタクラスを指定して仮想レジスタを作成し、引数に割り付けて追加する。

最後に LowerReturn で、関数呼び出しから戻るときの戻り値の扱いについて記述する。 戻り値を解析し、そのすべてをレジスタに詰め込み（複数個あることを前提？）、最後に RET_FLAG を出力している ^[23]。 ここの処理は全体的によくわからない（TODO；特に Chain, Flag, RetOps がどのような働きをしているのか判然としない）。 Chain を通じて SelectionDAG がじゅじゅつなぎになっている？

引数が渡ってくるレジスタを CopyFromReg でくるむことで、その（仮想的/物理的）レジスタがこの SelectionDAG の 外側で定義されたものであることを示している。

なおRV32Kは下位（sub）に位置づけられるべきターゲットが存在しないが、 それでもターゲットの情報を保持するために RV32KSubTarget を定義することが必要である。 CPUName は RV32K.td や RV32KMCTargetDesc と合わせて generic-rv32k としておく。 Lanaiの実装を見ると generic だけで統一しても良いようだ（TODO）。

setBooleanContents(ZeroOrOneBooleanContent); はターゲットが1/0でtrue/falseを判定することを設定する。

さて上記のように関数呼び出し時の処理を記述するためには、 そもそも関数呼び出し規約の定義を行う必要がある。これは RV32KCallingConv.td にて行う。 関数呼び出し時の引数・戻り値を処理するためのレジスタを指定する。またcallee-savedなレジスタも指定する。

ここで戻り値を返すためのレジスタを複数指定することができるようだ。 これはおそらくLLVM IRが複数の戻り値を扱うことができることの単純な反映であろうし（TODO；ほんまか？）、 また例えばRISC VのCalling conventionではa0とa1が戻り値を返すためのレジスタとして指定されているためでも あると思う。

なおここで sp である x2 をcallee-savedとして指定する必要はない。 というのもこの処理は関数プロローグ・エピローグで行うことに（将来的に）なるからだ ^[24]。

SelectionDAG をRV32Kコードに変換するためのクラスを実装する。 RV32KISelDAGToDAG.cpp で実装される。 このクラスのエントリポイントは Select であるが、これ自体はTableGenが生成する関数である SelectCode を 呼び出すだけである。そこでこの処理の本体は RV32KInstrInfo.td に記述されることになる。

RISCVのCompressedの実装を見ると Pat を継承しない方法で処理をしていた。よくわからない（TODO）。

ALU操作のみにとりあえず対応するため、現状対応するのは ADD と SUB 、それから便宜上必要になる PseudoRET の3つのみである。

関数のプロローグとエピローグを出力するためのクラスを実装する。 これらではスタックフレームサイズの調整を行う。 とはいいつつもこれらはまだ実装の必要がないため、ただのプレースホルダになっている。

スタックがアドレス負方向に伸びることを TargetFrameLowering のコンストラクタの第一引数に StackGrowDown を渡すことで表現している。

まず RV32KRegisterInfo.td を変更し、レジスタを割付優先度順に並び替える。

続いて RV32KRegisterInfo クラスを実装する。 getReservedRegs で通常のレジスタ割り付けでは使用しないレジスタを指定する。

[29]と同様の実装をすればよい。 本体の処理は LowerRV32KMachineInstrToMCInst である。 これは MachineInstr を MCInst に変換している。

ビルドに必要なファイルなどを実装する。

RV32KInstrInfo に let guessInstructionProperties = 0; という文を追加している。 命令の属性（ hasSideEffects など）を推論するためのオプションのようだ（TODO）。

RV32KGenInstrInfo.inc を読み込むため RV32KInstrInfo.{h,cpp} を追加する。

RV32KTarget>achine.{h,cpp} を変更する。ここでは RV32KSubtarget のインスタンスを 得るための getSubtargetImpl を実装すると同時に、実行パスに RV32KDagToDAGISel を挿入するために RV32KPassConfig を実装する ^[25]。

CodeGen のためのテストを作成する。これはLLVM IRを入力し、出力されるアセンブリが正しいかどうかを判定するものである。

テストの枠組みに頼らず、手でテストを行うためには次のようにする。

ついに我々はLLVM IRからコード生成を行うその第一歩を踏み出せたようだ。Here we go! ^[26]

[32]を参考にまとめる。

SelectionDAG を用いたinstruction selectionは SelectionDAG を最適化・正規化することで行われる [33]。 この過程は -view-dag-combine1-dags などのオプションを llc に与えることでグラフとして見ることができる。

それっぽい。

TableGenを用いて brcond に対するパターンマッチを記述する。

RV32Kv1では BEQZ と BNEZ のみが定義されている^[30]。 そこで setlt と setgt が自然に定義できる。すなわち $a < $b という比較なら SLT $a, $b 後 BNEZ $a, hoge とする。

分岐命令のパターンマッチでは bb というクラスがよく登場する。（ bb:$imm9 ）。これはおそらくbasic blockで、 分岐の際に用いるプリミティブな型のようだ。パターンマッチの後半で正しい型を指定することで、実際の型を指定できる気がする。TODO これと絡む即値の型は Operand<i32> の代わりに Operand<OtherVT> を継承する必要があるようだ。 なおbasic blockを処理するために MachineOperand::MO_MachineBasicBlock についての場合分けを LowerRV32KMachineOperandToMCOperand に追加する必要がある。

LLVM IRをテキスト形式で書く際 brcond という命令は直接は存在せず br 命令を介してこれを使うことになる。 その際 false 部の処理を行うため br 命令も発行されることに注意が必要である。 すなわち brcond のためのパターンマッチのみならず br のためのパターンマッチも潜在的に不可欠である。 これを解決するために

としても良いように見えるし、実際動く。 しかしRISC Vの実装では PseudoBR を定義して解消しているため、とりあえずこれを採用してみる ^[31]。

このPseudo命令を定義するためには RV32KAsmPrinter::lowerOperand を [38]を参考にして実装する必要がある。

RV32Kv1の現在の定義では SLT のみが存在するため、ナイーブに定義できるのは setlt のみである。 これを使用するようにSelectionDAGを構成するためには次のようなLLVM IRを入力する。

ここで

とすると途中で setge に変換されてしまうため注意が必要である。

引数を逆転させることで setgt についてもパターンマッチ可能である。

なお setlt などを挟まず brcond が単体で現れる場合についてもパターンマッチが可能だが、 これについてLLVM IRでテストを書くと and のSelectionDAGが現れてしまうためRV32Kv1では コンパイルできない。仕方がないのでテストはなしにしておく。

sub と beqz を組み合わせることで seteq を実現可能である。 また sub と bnez を組み合わせることで setne を実現可能である。 しかし sub は左辺を破壊する命令のため、前後の命令との兼ね合いによってはレジスタの値を別のレジスタに移したり、 スタックに保存する必要がある^[32]。そこで[implement-copyPhysReg]で示唆したように [34]を参考にして RV32KInstrInfo::copyPhysReg を実装し、 さらに[39]を参考にして RV32KInstrInfo::storeRegToStackSlot と RV32KInstrInfo::loadRegFromStackSlot を実装する。 またこれに必要な RV32KRegisterInfo::eliminateFrameIndex も実装する。 この関数は MachineInstr にオペランドとして含まれる FrameIndex を FrameReg と Offset に変換するための関数である。 storeRegToStackSlot などではオペランドとして FrameIndex を指定し、 即値は 0 にしておく。そのうえで eliminateFrameIndex を呼び出し、 正しいオペランドに変換している^[33]。 ここでRV32Kv1の lw と sw が符号なし即値をとることが問題になる。 すなわち Offset が負数になる場合に対処できない。 この問題はどうすることもできないので、とりあえず放置する。 また FrameReg はRV32Kv1でははっきりと決まっていいないがとりあえず X15 にしておく。

ここまでで次のようなLLVM IRが

次のようなRV32Kv1コードに変換される。