手を動かせばできるLLVMバックエンドチュートリアル

FIXME

AsciiDocのコメントを用いて文中にFIXMEを仕込む。その他のFIXME（全般的なものなど）をここにリストにする。

だ・である調をです・ます調に変える。
実際にやってみる。
- 現状過去の作業ログを切り貼りしながら書いているので通してちゃんと動くかは良くわからない。
- ついでにLLVM v10.0.0に対応させる。

この文書について

この文書は Asciidoctorを用いて執筆されています。記述方法は Asciidoctor User Manualを参考にしてください。

この文書はGitによって管理されています。リポジトリはGitHubにて公開しています。

この文書に（おおよそ）則って開発されたLLVMバックエンドのソースコードを GitHubリポジトリにて公開しています。

この作品は、クリエイティブ・コモンズの表示 4.0 国際ライセンスで提供されています。ライセンスの写しをご覧になるには、 http://creativecommons.org/licenses/by/4.0/ をご覧頂くか、Creative Commons, PO Box 1866, Mountain View, CA 94042, USA までお手紙をお送りください^[1]。

本文書の内容は筆者が独自に調査したものです。 疑う余地なく誤りが含まれます。誤りに気づかれた方はGitHubリポジトリなどを通じてご連絡ください。なお誤っていそうな部分についてはAsciidoctorのコメント機能を用いてコメントを残しています。 FIXME というキーワードでソースコードの全文検索をしてください。

LLVMバックエンド概略

本書ではRISC-V風味の独自ISAを例にLLVMバックエンドを開発します。

使用するLLVMのバージョンはv9.0.0です。

ところで

一度もコンパイラを書いたことがない人は、この文書を読む前に『低レイヤを知りたい人のためのCコンパイラ作成入門』[50]などで一度フルスクラッチからコンパイラを書くことをおすすめします。

また[51]などを参考に、 LLVMではなくGCCにバックエンドを追加することも検討してみてはいかがでしょうか。

参考にすべき文献

LLVMバックエンドを開発する際に参考にできる書籍やWebサイトを以下に一覧します。なおこの文書では、RISC-Vバックエンド及びそれに関する技術資料を大いに参考しています。

Webページ

Writing an LLVM Backend[18]
- 分かりにくく読みにくい。正直あんまり見ていないが、たまに眺めると有益な情報を見つけたりもする。
The LLVM Target-Independent Code Generator[31]
- [18]よりもよほど参考になる。LLVMバックエンドがどのようにLLVM IRをアセンブリに落とすかが明記されている。必読。
TableGenのLLVMのドキュメント[21]
- 情報量が少ない。これを読むよりも各種バックエンドのTableGenファイルを読むほうが良い。
LLVM Language Reference Manual[43]
- LLVM IRについての言語リファレンス。LLVM IRの仕様などを参照できる。必要に応じて読む。
Architecture & Platform Information for Compiler Writers[68]
- LLVMで公式に実装されているバックエンドに関するISAの情報が集約されている。Lanaiの言語仕様へのリンクが貴重。
RISC-V support for LLVM projects[10]
- どちゃくそに参考になる。以下の開発はこれに基づいて行う。
- LLVMにRISC-Vサポートを追加するパッチ群。バックエンドを開発するためのチュートリアルも兼ねているらしく docs/ 及びそれと対応したpatchが参考になる。
- またこれについて、開発者が2018 LLVM Developers' Meetingで登壇したときの動画は[11]より閲覧できる。スライドは[30]より閲覧できる。
- そのときのCoding Labは[48]より閲覧できる。
Create an LLVM Backend for the Cpu0 Architecture[35]
- Cpu0という独自アーキテクチャのLLVMバックエンドを作成するチュートリアル。多少古いが、内容が網羅的で参考になる。英語が怪しい。
FPGA開発日記[44]
- Cpu0の資料[35]をもとに1からRISC-Vバックエンドを作成する過程がブログエントリとして公開されている。GitHubに実装も公開されている[65]。
ELVMバックエンド[36]
- 限られた命令でLLVM IRの機能を達成する例として貴重。でも意外とISAはリッチだったりする。
- 作成者のスライドも参考になる[37]。
2018年度東大CPU実験で開発されたLLVM Backend[40]
- これについて書かれたAdCのエントリもある[41]。
Tutorial: Building a backend in 24 hours[45]
- LLVMバックエンドの大まかな動きについてざっとまとめたあと、 ret だけが定義された最低限のLLVMバックエンド ("stub backend") を構成している。
- Instruction Selection の説明にある Does bunch of magic and crazy pattern-matching が好き。
2017 LLVM Developers’ Meeting: M. Braun "Welcome to the back-end: The LLVM machine representation"[46]
- スライドも公開されている[135]。
- 命令選択が終わったあとの中間表現であるLLVM MIR （ MachineFunction や MachineInstr など）や、それに対する操作の解説。 RegStateやframe index・register scavengerなどの説明が貴重。
Howto: Implementing LLVM Integrated Assembler[47]
- LLVM上でアセンブラを書くためのチュートリアル。アセンブラ単体に焦点を絞ったものは珍しい。
Building an LLVM Backend[49]
- 対応するレポジトリが[54]にある。
[LLVMdev] backend documentation[116]
- llvm-devメーリングリストのバックエンドのよいドキュメントは無いかというスレッド。Cpu0とTriCoreが挙げられているが、深くまで記述したものは無いという回答。
TriCore Backend[118]
- TriCoreというアーキテクチャ用のバックエンドを書いたという論文。スライドもある[117]。ソースコードもGitHub上に上がっているが、どれが公式かわからない^[2]。
Life of an instruction in LLVM[136]
- Cコードからassemblyまでの流れを概観。
LLVM Backendの紹介[138]
- 「コンパイラ勉強会」^[3]での、LLVMバックエンドの大きな流れ（特に命令選択）について概観した日本語スライド。

書籍

『きつねさんでもわかるLLVM〜コンパイラを自作するためのガイドブック〜』[7]
- 数少ない日本語資料。Passやバックエンドの各クラスについて説明している。[31]と合わせて大まかな流れを掴むのに良い。
- ただし書籍中で作成されているバックエンドは機能が制限されており、またコードベースも多少古い。

なおLLVMについてGoogleで検索していると"LLVM Cookbook"なる謎の書籍（の電子コピー）が見つかるが、内容はLLVM公式文書のパクリのようだ[139]。

バックエンド

RISC-V[5]
- パッチ群が開発ドキュメントとともに公開されている[10]。以降の開発はこれをベースに行う。
Lanai[103]
- Googleが開発した32bit RISCの謎アーキテクチャ。全く実用されていないが、バックエンドが単純に設計されておりコメントも豊富のためかなり参考になる^[4]^[5]。
Sparc
- [18]でも説明に使われており、コメントが豊富。
x86
- みんな大好きx86。貴重なCISCの資料であり、かつ2オペランド方式を採用する場合に実装例を与えてくれる。あと EFLAGS の取り回しなども参考になるが、全体的にコードは読みにくい。ただLLVMの命名規則には従うため、他のバックエンドからある程度推論をして読むのが良い。

ISAの仕様を決める

本書で使用するISAであるCAHPv3について説明します。

cahpv3.pdfを参考のこと。

スケルトンバックエンドを追加する

d0b8dd14570dc9efac09d3c5fd6e8512980fd7b7

CAHPのためのビルドを行うために、中身のないバックエンド（スケルトンバックエンド）を LLVMに追加します。

CAHPをTripleに追加する

[8]を参考にして CAHPをLLVMに認識させます。LLVMではコンパイル先のターゲットをTripleという単位で管理しています。そのTripleの一つとしてCAHPを追加します。

llvm/include/llvm/ADT/Triple.h や llvm/lib/Support/Triple.cpp などのファイルにTripleが列挙されているため、そこにCAHPを追加します。また llvm/unittests/ADT/TripleTest.cpp にTripleが正しく認識されているかをチェックするテストを書きます。

CAHPのELFフォーマットを定義する

[13]を参考にして、CAHPのためのELFフォーマットを定義します。具体的にはCAHPのマシンを表す識別コードや再配置情報などを記述し、 ELFファイルの出力が動作するようにします。ただし独自ISAではそのような情報が決まっていないため、適当にでっちあげます。

バックエンドを追加する

[14]を参考に llvm/lib/Target ディレクトリ内に CAHP ディレクトリを作成し、最低限必要なファイルを用意します。

まずビルドのために CMakeLists.txt と LLVMBuild.txt を用意します。またCAHPに関する情報を提供するために CAHPTargetInfo.cpp や CAHPTargetMachine.cpp などを記述します。

CAHPTargetMachine.cpp ではdata layoutを文字列で指定します。詳細はLLVM IRの言語仕様[53]を参考してください。

以上で必要最小限のファイルを用意することができました。

LLVMをビルドする

LLVMは巨大なプロジェクトで、ビルドするだけでも一苦労です。以下では継続的な開発のために、高速にLLVMをデバッグビルドする手法を紹介します。 [1]・[2]・[3]を参考にしています。

ビルドの際には以下のソフトウェアが必要になります。

cmake
ninja
clang
clang++
lld

まずLLVMのソースコードをGitを用いて取得します。前述したように、今回の開発ではLLVM v9.0.0をベースとします。そこでブランチ llvmorg-9.0.0 から独自実装のためのブランチ cahp を生成し、以降の開発はこのブランチ上で行うことにします。

$ git clone https://github.com/llvm/llvm-project.git
$ cd llvm-project
$ git switch llvmorg-9.0.0
$ git checkout -b cahp

続いて、ビルドを行うための設定をCMakeを用いて行います。大量のオプションはビルドを早くするためのものです[96]。

$ mkdir build
$ cd build
$ cmake -G Ninja \
    -DLLVM_ENABLE_PROJECTS="clang;lld" \
    -DCMAKE_BUILD_TYPE="Debug" \
    -DBUILD_SHARED_LIBS=True \
    -DLLVM_USE_SPLIT_DWARF=True \
    -DLLVM_OPTIMIZED_TABLEGEN=True \
    -DLLVM_BUILD_TESTS=True \
    -DCMAKE_C_COMPILER=clang \
    -DCMAKE_CXX_COMPILER=clang++ \
    -DLLVM_USE_LINKER=lld \
    -DLLVM_TARGETS_TO_BUILD="" \
    -DLLVM_EXPERIMENTAL_TARGETS_TO_BUILD="CAHP" \
    ../llvm

Ninjaを用いてビルドを行います。直接Ninjaを実行しても構いません（ $ ninja ）が、 CMakeを用いて間接的に実行することもできます。

$ cmake --build .

手元の環境（CPUはIntel Core i7-8700で6コア12スレッド、RAMは16GB）では 30分弱でビルドが完了しました。また別の環境（CPUはIntel Core i5-7200Uで2コア4スレッド、RAMは8GB）では 1時間半程度かかりました。以上から類推すると、 $n$コアのCPUを使用する場合およそ$\frac{180}{n}$分程度かかるようです。

ビルドが終了すると bin/ ディレクトリ以下にコンパイルされたバイナリが生成されます。例えば次のようにして、CAHPバックエンドが含まれていることを確認できます。

$ bin/llc --version
LLVM (http://llvm.org/):
  LLVM version 9.0.0
  DEBUG build with assertions.
  Default target: x86_64-unknown-linux-gnu
  Host CPU: skylake

  Registered Targets:
    cahp    - CAHP

ここでは開発用にデバッグビルドを行いました。一方で、他人に配布する場合などはリリースビルドを行います。その際は次のようにCMakeのオプションを指定します。

$ cmake -G Ninja \
    -DLLVM_ENABLE_PROJECTS="lld;clang" \
    -DCMAKE_BUILD_TYPE="Release" \
    -DLLVM_BUILD_TESTS=True \
    -DCMAKE_C_COMPILER=clang \
    -DCMAKE_CXX_COMPILER=clang++ \
    -DLLVM_USE_LINKER=lld \
    -DLLVM_TARGETS_TO_BUILD="" \
    -DLLVM_EXPERIMENTAL_TARGETS_TO_BUILD="CAHP" \
    ../llvm

LLVMをテストする

llvm-lit を使用してLLVMをテストできます。

$ bin/llvm-lit test -s  # 全てのテストを実行する。
$ bin/llvm-lit -s --filter "Triple" test # Tripleに関するテストを実行する。
$ bin/llvm-lit -s --filter 'CAHP' test # CAHPを含むテストを実行する。
$ bin/llvm-lit -as --filter 'CAHP' test # テスト結果を詳細に表示する。
$ bin/llvm-lit -as --filter 'CAHP' --debug test # デバッグ情報を表示する。

アセンブラを作る

2c31c0a80020cc50bba6df1c35da228905190d97

この章ではLLVMバックエンドの一部としてアセンブラを実装します。具体的にはLLVMのMCLayerを実装し、アセンブリからオブジェクトファイルへの変換を可能にします。一度にアセンブラ全体を作るのは難しいため、まずレジスタのみを使用する演算命令に絞って実装し、その後メモリを使用する命令をカバーします。

TableGenファイルを追加する

LLVM coreは基本的にC++によって記述されています。一方で、多くの箇所で共通する処理などは独自のDSL（ドメイン固有言語）であるTableGenを用いて記述し llvm-tblgen というソフトウェアを用いてこれをC++コードに変換しています。こうすることによって記述量を減らし、ヒューマンエラーを少なくするという考え方のようです[21]。

LLVMバックエンドでは、アーキテクチャが持つレジスタや命令などの情報をTableGenによって記述します。大まかに言って、TableGenで書ける場所はTableGenによって書き、対応できない部分をC++で直に書くというのがLLVM coreの方針のようです。ここでは、簡単なアセンブラを実装するために最低限必要なTableGenファイルを追加します。内訳は次のとおりです。

CAHP.td: 下のTableGenファイルをincludeし、その他もろもろを定義。
CAHPRegisterInfo.td: レジスタを定義。
CAHPInstrFormats.td: 命令形式を定義。
CAHPInstrInfo.td: 命令を定義。

順に説明します。 CAHP.td がTableGenファイル全体をまとめているTableGenファイルで、内部では include を使って他のファイルを読み込んでいます。

include "llvm/Target/Target.td"

include "CAHPRegisterInfo.td"
include "CAHPInstrInfo.td"

また同時に、今回想定するプロセッサを表す ProcessorModel や、現在実装しているターゲットの CAHP について定義しています。

CAHPRegisterInfo.td ではCAHPに存在するレジスタを定義します。まず Register を継承して class CAHPReg を作り、これに基本的なレジスタの性質をもたせます。ついで class CAHPReg の実体として X0 から X15 を作成します。 alt にはレジスタの別名を指定します。最後に、レジスタをまとめて RegisterClass である GPR （General Purpose Register; 汎用レジスタの意）を定義します。このあと命令を定義する際にはこの RegisterClass 単位で指定します。ここでレジスタを並べる順番が先であるほどレジスタ割り付けで割り付けられやすいため、 caller-savedなもの（使ってもspill outが起こりにくいもの）を先に並べておきます。

GPR と同様に SP という RegisterClass も作成し、 X1 、つまりスタックポインタを表すレジスタのみを追加しておきます。この RegisterClass を命令のオペランドに指定することで lwsp や swsp などの「スタックポインタのみを取る命令」を表現することができます。

命令は CAHPInstrFormats.td と CAHPInstrInfo.td に分けて記述します。 CAHPInstrFormats.td ではおおよその命令の「形」を定義しておき、 CAHPInstrInfo.td でそれを具体化します。言葉で言ってもわかりにくいので、コードで見ます。例えば24bit長の加算命令は次のように定義されます。まずCAHPの命令全体に共通する事項を class CAHPInst として定義します。

class CAHPInst<dag outs, dag ins, string opcodestr, string argstr, list<dag> pattern = []>
: Instruction {
  let Namespace = "CAHP";

  dag OutOperandList = outs;
  dag InOperandList = ins;

  let AsmString = opcodestr # "\t" # argstr;

  // Matching patterns used when converting SelectionDAG into MachineDAG.
  let Pattern = pattern;
}

次に、CAHPの24bit命令に共通する事項を class CAHPInst を継承した class CAHP24Inst として定義します。

// 24-bit instruction format.
class CAHPInst24<dag outs, dag ins, string opcodestr, string argstr, list<dag> pattern = []>
: CAHPInst<outs, ins, opcodestr, argstr, pattern> {
  let Size = 3;
  bits<24> Inst;
}

さらに、24bit長加算命令の「形」である24bit R形式（オペランドにレジスタを3つとる）を class CAHPInst24R として定義します。 class CAHPInst24 を継承します。

// 24-bit R-instruction format.
class CAHPInst24R<bits<8> opcode, dag outs, dag ins, string opcodestr, string argstr>
: CAHPInst24<outs, ins, opcodestr, argstr> {
  bits<4> rd;
  bits<4> rs1;
  bits<4> rs2;

  let Inst{23-20} = 0;
  let Inst{19-16} = rs2;
  let Inst{15-12} = rs1;
  let Inst{11-8} = rd;
  let Inst{7-0} = opcode;
}

最後にこれを使って加算命令 ADD を定義します。

def ADD : CAHPInst24R<0b00000001, (outs GPR:$rd), (ins GPR:$rs1, GPR:$rs2),
                      "add", "$rd, $rs1, $rs2">;

上記の継承による構造を展開すると、結局 class Instruction を使って次のような定義を行ったことになります。

def ADD : Instruction {
  let Namespace = "CAHP";

  let Pattern = [];

  let Size = 3; // 命令長は8bit * 3 = 24bit
  bits<24> Inst;

  bits<4> rd;  // オペランドrdは4bit
  bits<4> rs1; // オペランドrs1は4bit
  bits<4> rs2; // オペランドrs2は4bit

  // 命令のエンコーディングは次の通り。
  let Inst{23-20} = 0;        // 20〜23bit目は0
  let Inst{19-16} = rs2;      // 16〜19bit目はrs2
  let Inst{15-12} = rs1;      // 12〜15bit目はrs1
  let Inst{11-8} = rd;        // 8〜11bit目はrd
  let Inst{7-0} = 0b00000001; // 0〜7bit目は0bit目だけが1で残りは0

  // 出力はレジスタクラスGPRのrdに入る。
  dag OutOperandList = (outs GPR:$rd);
  // 入力はレジスタクラスGPRのrs1とrs2に入る。
  dag InOperandList = (ins GPR:$rs1, GPR:$rs2);

  // アセンブリ上では「add rd, rs1, rs2」という形で与えられる。
  let AsmString = "add\t$rd, $rs1, $rs2";
}

Inst フィールドにエンコーディングを設定することで、 TableGenにエンコードの処理を移譲することができます^[6]。

続いて即値を用いる命令を見ます。例として addi を取り上げます。 addi は8bit符号付き即値をオペランドに取ります。まずこれを定義します。

class ImmAsmOperand<string prefix, int width, string suffix> : AsmOperandClass {
  let Name = prefix # "Imm" # width # suffix;
  let RenderMethod = "addImmOperands";
  let DiagnosticType = "Invalid" # Name;
}

class SImmAsmOperand<int width, string suffix = "">
    : ImmAsmOperand<"S", width, suffix> {
}

def simm8 : Operand<i16> {
  let ParserMatchClass = SImmAsmOperand<8>;
}

続いて命令の「形」を定義します。 addi は24bit I形式です。

class CAHPInst24I<bits<8> opcode, dag outs, dag ins, string opcodestr, string argstr>
: CAHPInst24<outs, ins, opcodestr, argstr> {
  bits<4> rd;
  bits<4> rs1;
  bits<8> imm;

  let Inst{23-16} = imm;
  let Inst{15-12} = rs1;
  let Inst{11-8} = rd;
  let Inst{7-0} = opcode;
}

最後に、これを用いて addi を定義します。

def ADDI : CAHPInst24I<0b11000011, (outs GPR:$rd), (ins GPR:$rs1, simm8:$imm),
                       "addi", "$rd, $rs1, $imm">;

add の際には GPR とした第三オペランドが simm8 となっています。これによって、この部分に符号付き8bit即値が来ることを指定しています。

即値のうち、下位1bitが0になるものは _lsb0 というサフィックスを名前につけ区別しておきます。 uimm7_lsb0 と simm11_lsb0 がそれに当たります。後々、C++コードにてこの制限が守られているかをチェックします。

add2 のような2オペランドの命令を記述する場合、上の方法では問題があります。というのも add2 の第一オペランドは入力であると同時に出力先でもあるためです。このような場合は次のように Constraints フィールドにその旨を記述します。

let Constraints = "$rd = $rd_w" in {
  def ADD2 : CAHPInst16R<0b10000000, (outs GPR:$rd_w), (ins GPR:$rd, GPR:$rs),
                        "add2", "$rd, $rs">;
}

なおTableGenでは let で囲むレコードが一つの場合は括弧 { } は必要ありません。また let で外からフィールドを上書きするのと、 def の中身に記載するのとで意味は変わりません。すなわち、上のコードは次の2通りと意味は異なりません[25]。

let Constraints = "$rd = $rd_w" in
def ADD2 : CAHPInst16R<0b10000000, (outs GPR:$rd_w), (ins GPR:$rd, GPR:$rs),
                      "add2", "$rd, $rs">;

def ADD2 : CAHPInst16R<0b10000000, (outs GPR:$rd_w), (ins GPR:$rd, GPR:$rs),
                      "add2", "$rd, $rs"> {
  let Constraints = "$rd = $rd_w";
}

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

$ bin/llvm-tblgen -I ../llvm/lib/Target/CAHP/ -I ../llvm/include/ -I ../llvm/lib/Target/ ../llvm/lib/Target/CAHP/CAHP.td

`MCTargetDesc` を追加する

アセンブラ本体のC++コードを作成します。ここでは、アセンブリのエンコードからバイナリ生成部分を担当する MCTargetDesc ディレクトリを追加し、必要なファイルを揃えます。複数のクラスを定義しますが、それらは全て MCTargetDesc/CAHPMCTargetDesc.cpp にある LLVMInitializeCAHPTargetMC 関数でLLVM coreに登録されます。

定義するクラスは次のとおりです。

CAHPMCAsmInfo
CAHPMCInstrInfo
CAHPMCRegisterInfo
CAHPMCSubtargetInfo
CAHPMCCodeEmitter
CAHPAsmBackend
CAHPELFObjectWriter

順に説明します。

CAHPMCAsmInfo にはアセンブリがどのように表記されるかを主に記述します。 MCTargetDesc/CAHPMCAsmInfo.{h,cpp} に記述します。

CAHPMCInstrInfo は先程記述したTableGenファイルから、 TableGenによって InitCAHPMCInstrInfo 関数として自動的に生成されます。 CAHPMCTargetDesc.cpp 内でこれを呼び出して作成します。

CAHPMCRegisterInfo も同様に自動的に生成されます。 InitCAHPMCRegisterInfo 関数を呼び出します。なおこの関数の第二引数には関数の戻りアドレスが入るレジスタを指定します^[7]。 CAHPではx0を表す CAHP::X0 を渡すことになります。

CAHPMCSubtargetInfo も同様に自動生成されます。 createCAHPMCSubtargetInfoImpl を呼び出します。この関数の第二引数には CAHP.td で ProcessorModel として定義したCPUの名前を指定します。

CAHPMCCodeEmitter はアセンブリのエンコード作業を行います。 MCTargetDesc/CAHPMCCodeEmitter.cpp に記述します。主要なエンコード処理はTableGenによって自動生成された getBinaryCodeForInstr を CAHPMCCodeEmitter::encodeInstruction から呼び出すことによって行われます。この関数は CAHPGenMCCodeEmitter.inc というファイルに定義されるため、これを MCTargetDesc/CAHPMCCodeEmitter.cpp 末尾で #include しておきます。

CAHPAsmBackend にはオブジェクトファイルを作成する際に必要な fixupの操作（ applyFixup ）や指定バイト数分の無効命令を書き出す処理（ writeNopData ）などを記述します。 MCTargetDesc/CAHPAsmBackend.cpp に記述します。 fixupについては後ほど実装するためここではスタブにしておきます。

CAHPELFObjectWriter にはELFファイル（の特にヘッダ）を作成する際に必要な情報を記載します。このクラスは LLVMInitializeCAHPTargetMC ではなく CAHPAsmBackend の createObjectTargetWriter メンバ関数として紐付けられます。親クラス MCELFObjectTargetWriter のコンストラクタに、 CAHPマシンを表す ELF::EM_CAHP と、 .rel ではなく .rela を使用する旨を示す true を渡しておきます^[8]。また getRelocType メンバ関数はどのような再配置を行うかを見繕うためのものですが、ここではスタブにしておきます。

上記を実装してビルドします。一度使ってみましょう。 LLVMのアセンブラを単体で使う場合は llvm-mc というコマンドを使用します。次のようにすると foo.s というアセンブリファイルをオブジェクトファイルに変換できます。

$ bin/llvm-mc -arch=cahp -filetype=obj foo.s
bin/llvm-mc: error: this target does not support assembly parsing.

このようなエラーメッセージが出れば成功です^[9]。このエラーメッセージはCAHPターゲットがアセンブリのパーズ（構文解析）に対応していないことを意味しています。これは次の節で実装します。

RISC-Vの拡張C命令には add などレジスタを5bitで指定する命令と、 sub などレジスタを3bitで指定する命令の2種類があります。 LLVM RISC-Vバックエンドを見ると、エンコードに際してこれらの区別のための特別な処理は行っていません。というのも、3bitでレジスタを指定する場合その添字の下位3bit以外が無視されるため、結果的に正しいコードが出力されるのです。例えば x8 を指定すると、これに 1000 という添字が振られ、 4bit目を無視することで 000 となるため、 3bitでのレジスタ指定方法として正しいものになります。

独自ISAなどで、このような手法が取れないレジスタの並びを使用する場合は、アセンブリをコードに変換する際にそのレジスタのエンコーディングを補正します。このようなレジスタオペランドエンコードのフックを行う関数を指定する場所として RegisterOperand の EncoderMethod があります。例えば sub で X3 から X10 を0〜7というエンコードで用いたい場合、 X3 から X10 を GPRC という RegisterClass とした上で、これを RegisterOperand で包み ShiftedGPRC とします。これの EncoderMethod として RV32KEncodeShiftedGPRCRegisterOperand という関数を指定します。これは RV32KMCCodeEmitter クラスのメンバ関数として定義する。これによって任意の処理をフックすることができる。https://reviews.llvm.org/rL303044

def GPRC : RegisterClass<"RV32K", [i32], 32, (add
            X3, X4, X5, X6, X7, X8, X9, X10
    )>;

def ShiftedGPRC : RegisterOperand<GPRC> {
  let EncoderMethod = "RV32KEncodeShiftedGPRCRegisterOperand";
  //let DecoderMethod = "RV32KDecodeShiftedGPRCRegisterOperand";
}

uint64_t
RV32KEncodeShiftedGPRCRegisterOperand(const MCInst &MI, unsigned no,
                                      SmallVectorImpl<MCFixup> &Fixups,
                                      const MCSubtargetInfo &STI) const;

uint64_t RV32KMCCodeEmitter::RV32KEncodeShiftedGPRCRegisterOperand(
    const MCInst &MI, unsigned no, SmallVectorImpl<MCFixup> &Fixups,
    const MCSubtargetInfo &STI) const {
  const MCOperand &MO = MI.getOperand(no);
  if (MO.isReg()) {
    uint64_t op = Ctx.getRegisterInfo()->getEncodingValue(MO.getReg());
    assert(3 <= op && op <= 10 && "op should belong to GPRC.");
    return op - 3;
  }

  llvm_unreachable("Unhandled expression!");
  return 0;
}

`CAHPAsmParser` を追加する

アセンブリのパーズは CAHPAsmParser クラスが取り仕切っています。新しく AsmParser ディレクトリを作成し、その中に CAHPAsmParser.cpp を作成してパーズ処理を記述します。[19]を参考にします。

CAHPAsmParser::ParseInstruction がパーズ処理のエントリポイントです。 CAHPAsmParser::parseOperand や CAHPAsmParser::parseRegister ・ CAHPAsmParser::parseImmediate を適宜用いながら、アセンブリのトークンを切り出し Operands に詰め込みます^[10]。

この際にオペランドを表すクラスとして CAHPOperand を定義・使用しています。オペランドとして現れうるのはレジスタと即値とその他のトークン（命令や括弧文字など）なのでその旨を記述します^[11]。 TableGenにて定義・使用した即値を正しく認識するために isUImm4 や isSImm11Lsb0 などのメンバ関数を定義する必要があります。これらの関数は後述の MatchInstructionImpl 内で使用されます。

切り出されたオペランドのリストを命令としてLLVMに認識させるのは MatchAndEmitInstruction で行います。具体的には、先程の Operands を読み込んで MCInst に変換します。ただし実際の処理の殆どはTableGenによって自動生成された MatchInstructionImpl によって行われます。実際に書く必要があるのはこの関数が失敗した場合のエラーメッセージ等です。

CAHPAsmParser を実装するとアセンブラが完成します。使ってみましょう。

$ cat foo.s
li x9, 3
mv x11, x1
sub x9, x10
add x8, x1
nop

$ bin/llvm-mc -arch=rv32k -filetype=obj foo.s | od -tx1z -Ax -v
000000 7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00  >.ELF............<
000010 01 00 f5 00 01 00 00 00 00 00 00 00 00 00 00 00  >................<
000020 68 00 00 00 00 00 00 00 34 00 00 00 00 00 28 00  >h.......4.....(.<
000030 04 00 01 00 8d 44 86 85 89 8c 06 94 01 00 00 00  >.....D..........<
000040 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  >................<
000050 00 2e 74 65 78 74 00 2e 73 74 72 74 61 62 00 2e  >..text..strtab..<
000060 73 79 6d 74 61 62 00 00 00 00 00 00 00 00 00 00  >symtab..........<
000070 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  >................<
000080 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  >................<
000090 07 00 00 00 03 00 00 00 00 00 00 00 00 00 00 00  >................<
0000a0 50 00 00 00 17 00 00 00 00 00 00 00 00 00 00 00  >P...............<
0000b0 01 00 00 00 00 00 00 00 01 00 00 00 01 00 00 00  >................<
0000c0 06 00 00 00 00 00 00 00 34 00 00 00 0a 00 00 00  >........4.......<
0000d0 00 00 00 00 00 00 00 00 04 00 00 00 00 00 00 00  >................<
0000e0 0f 00 00 00 02 00 00 00 00 00 00 00 00 00 00 00  >................<
0000f0 40 00 00 00 10 00 00 00 01 00 00 00 01 00 00 00  >@...............<
000100 04 00 00 00 10 00 00 00                          >........<
000108

0x34から0x3dにある 8d 44 86 85 89 8c 06 94 01 00 が出力であり、正しく生成されていることが分かります。

`CAHPInstPrinter` を実装する

aa66568c3dfe1d80a83a96bd0437a26fdb96872a

次の節では、上記までで作成したアセンブラのテストを記述します。その際、アセンブリを MCInst に変換した上でそれをアセンブリに逆変換したものが、もとのアセンブリと同じであるか否かをチェックします。このテストを行うためには MCInst からアセンブリを得るための仕組みが必要です。この節ではこれを行う CAHPInstPrinter クラスを実装します。 [20]を参考にします。

InstPrinter ディレクトリを作成し InstPrinter/CAHPInstPrinter.{cpp,h} を作成します。命令印字処理の本体は CAHPInstPrinter::printInst ですが、そのほとんどの処理は CAHPInstPrinter::printInstruction というTableGenが生成するメンバ関数により実行されます。 CAHPInstPrinter::printRegName はレジスタ名を出力する関数で CAHPInstPrinter::printOperand から呼ばれますが、これも CAHPInstPrinter::getRegisterName という自動生成されたメンバ関数に処理を移譲します。この CAHPInstPrinter::getRegisterName の第二引数に何も渡さなければ（デフォルト引数 CAHP::ABIRegAltName を利用すれば） TableGenで定義したAltNameが出力に使用されます^[12]。 CAHP::NoRegAltName を渡すと本来の名前（CAHPでは x0 〜 x15 ）が使用されます。

CAHPInstPrinter クラスは MCTargetDesc/CAHPMCTargetDesc.cpp にて作成・登録されます。

節の冒頭で説明した「アセンブリを MCInst に変換した上でそれをアセンブリに逆変換」は llvm-mc の -show-encoding オプションを用いて行うことができます。 -show-encoding を指定することよって当該アセンブリがどのような機械語に翻訳されるか確認することができます。

$ cat foo.s
// FIXME

$ bin/llvm-mc -arch=rv32k -show-encoding foo.s
    .text
    li	x9, 3                   # encoding: [0x8d,0x44]
    mv	x11, x1                 # encoding: [0x86,0x85]
    sub	x9, x10                 # encoding: [0x89,0x8c]
    add	x8, x1                  # encoding: [0x06,0x94]
    nop	                        # encoding: [0x01,0x00]

テストを書く

c8bbf894c7ba046ddd3f55677f2d4512dd944aa0

前節で動作させた -show-encoding オプションを用いて、アセンブラが正しく動作していることを確認するためのテストを記述します。前節と同様にパッチ[20]を参考にします。

まず test/MC/CAHP ディレクトリを作成し、その中に cahp-valid.s と cahp-invalid.s を作成します。前者で正しいアセンブリが適切に処理されるか、後者で誤ったアセンブリに正しくエラーを出力するかを確認します。

記述後 llvm-lit を用いてテストを行います。

$ bin/llvm-lit -as --filter 'RV32K' test
PASS: LLVM :: MC/RV32K/rv32k-valid.s (1 of 2)
Script:
--
: 'RUN: at line 1';   /home/anqou/workspace/llvm-project/build/bin/llvm-mc /data/anqou/workspace/llvm-project/llvm/test/MC/RV32K/rv32k-valid.s -triple=rv32k -show-encoding      | /home/anqou/workspace/llvm-project/build/bin/FileCheck -check-prefixes=CHECK,CHECK-INST /data/anqou/workspace/llvm-project/llvm/test/MC/RV32K/rv32k-valid.s
--
Exit Code: 0


********************
PASS: LLVM :: MC/RV32K/rv32k-invalid.s (2 of 2)
Script:
--
: 'RUN: at line 1';   not /home/anqou/workspace/llvm-project/build/bin/llvm-mc -triple rv32k < /data/anqou/workspace/llvm-project/llvm/test/MC/RV32K/rv32k-invalid.s 2>&1 | /home/anqou/workspace/llvm-project/build/bin/FileCheck /data/anqou/workspace/llvm-project/llvm/test/MC/RV32K/rv32k-invalid.s
--
Exit Code: 0


********************
Testing Time: 0.11s
  Expected Passes    : 2

メモリ演算を追加する

43145f861dc729756a8a85df13a7257248e98169

前節までで、レジスタのみを使用する命令に対応しました。この節ではメモリを使用する命令に対応します。具体的にはメモリから1ワード（2バイト）読み込む lw と 1ワード書き込む sw 、及びその1バイト版である lb/lbu/sb 、更にスタックへの読み書きに特化した lwsp/swsp を追加します。

まずTableGenにこれらの命令を定義します。 CAHPアセンブリ中ではメモリは即値とレジスタの組み合わせで表現されます。例えば x8 に入っている値に 4 足した番地から1ワード読み込んで x9 に入れる場合は lw x9, 4(x8) と書きます。これを正しく表示するために AsmString にはこのように書きます。

def LW  : CAHPInst24MLoad <0b010101, (outs GPR:$rd), (ins GPR:$rs, simm11_lsb0:$imm),
                           "lw",  "$rd, ${imm}(${rs})">

ここで ${imm} と括弧でくくっているのは、単に $imm( とかくと imm( という識別子として認識されてしまうためです。

次いでこれらのアセンブリをパーズできるように CAHPAsmParser に手を加えます。 CAHPAsmParser::parseMemOpBaseReg メンバ関数を定義してメモリ指定のアセンブリである 即値(レジスタ) という形を読み込めるようにし、これを CAHPAsmParser::parseOperand から呼び出します。

最後にテストを書きます。

フィールドを詳細に指定する

1963e0288a450c3785723861c7c5d5c7280186fc

各命令がどのような特性を持つかをTableGenで指定します。この情報はコード生成の際に使用されます。これらのフィールドは llvm/include/llvm/Target/Target.td にてコメントとともに定義されています。

以下に主要なフィールドについて説明します。

ディスアセンブラを実装する

01fdfc0e1a5281527e339913ee08cb0da9d75f46

[16]を参考にしてディスアセンブラを実装します。 Disassembler ディレクトリを作成して Disassembler/CAHPDisassembler.cpp を追加・記述します。

ディスアセンブラの本体は CAHPDisassembler::getInstruction です。ディスアセンブルの処理のほとんどはTableGenが生成する decodeInstruction 関数によって行われます。CAHPでは24bitの命令と16bitの命令が混在するため、バイナリ列を解析してどちらの命令かを判断し、 decodeInstruction の第一引数に渡すテーブルを選びます。

レジスタのディスアセンブルは DecodeGPRRegisterClass にて行います。

即値のディスアセンブルは decodeUImmOperand と decodeSImmOperand にて行います。これらの関数は CAHPInstrInfo.td にて即値オペランドの DecoderMethod として指定します。

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

$ cat test.s
lwsp x11, 0(sp)

$ bin/llvm-mc -filetype=obj -triple=rv32k < test.s | bin/llvm-objdump -d -

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

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

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

Decoding Conflict:
		111...........01
		111.............
		................
	BNEZ 111___________01
	BNEZhoge 111___________01

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

relocationとfixupに対応する

a03e70e9157510937ca522f14ca0c64c61d47ca7

ワンパスでは決められない値についてあとから補うための機構であるfixupと、コンパイル時には決定できない値に対してリンカにその処理を任せるためのrelocationについて対応する。参考にするパッチは[27]。

必要な作業は大きく分けて次の通り。 * Fixupの種類とその内容を定義する。 * Fixupを適用する関数を定義する。 * アセンブラがFixupを生成するように改変する。 * Fixupが解決されないまま最後まで残る場合は、これをrelocationに変換する。

手を動かせばできるLLVMバックエンド チュートリアル

FIXME

この文書について

LLVMバックエンド概略

ところで

参考にすべき文献

Webページ

書籍

バックエンド

ISAの仕様を決める

スケルトンバックエンドを追加する

CAHPをTripleに追加する

CAHPのELFフォーマットを定義する

バックエンドを追加する

LLVMをビルドする

LLVMをテストする

アセンブラを作る

TableGenファイルを追加する

MCTargetDesc を追加する

CAHPAsmParser を追加する

CAHPInstPrinter を実装する

テストを書く

メモリ演算を追加する

フィールドを詳細に指定する

ディスアセンブラを実装する

relocationとfixupに対応する

%hi と %lo に対応する

li a0, foo をエラーにする

llvm-objdump の調査

hlt 疑似命令を追加する

コード生成部を作る

コンパイラのスケルトンを作成する

基本的な演算に対応する

定数の実体化に対応する

メモリ演算に対応する

relocationに対応する

条件分岐に対応する

関数呼び出しに対応する

関数プロローグ・エピローグを実装する

frame pointer eliminationを実装する

select に対応する

FrameIndex をlowerする。

大きなスタックフレームに対応する

SETCC に対応する

ExternalSymbol に対応する

jump tableを無効化する

インラインアセンブリに対応する

fastccに対応する

Cコンパイラに仕立てる

LLDにCAHPバックエンドを追加する

ClangをCAHPに対応させる

crt0.o と cahp.lds の導入

--nmagic の有効化

libcの有効化

まともなコードを生成する

分岐解析に対応する

branch relaxationに対応する

16bit命令を活用する

jal を活用する

命令スケジューリングを設定する

末尾再帰に対応する

落ち穂拾い

スタックを利用した引数渡し

byval の対応

動的なスタック領域確保に対応する

emergency spillに対応する

可変長引数関数に対応する

単体の sext/zext/trunc に対応する

乗算に対応する

除算・剰余に対応する

frameaddr/returnaddr に対応する

ROTL/ROTR/BSWAP/CTTZ/CTLZ/CTPOP に対応する

32bitのシフトに対応する

間接ジャンプに対応する

BlockAddress のlowerに対応する

参考文献

手を動かせばできるLLVMバックエンドチュートリアル

`MCTargetDesc` を追加する

`CAHPAsmParser` を追加する

`CAHPInstPrinter` を実装する

`%hi` と `%lo` に対応する

`li a0, foo` をエラーにする

`hlt` 疑似命令を追加する

`select` に対応する

`FrameIndex` をlowerする。

`SETCC` に対応する

`ExternalSymbol` に対応する

`crt0.o` と `cahp.lds` の導入

`--nmagic` の有効化

`jal` を活用する

`byval` の対応

単体の `sext/zext/trunc` に対応する

`frameaddr/returnaddr` に対応する

`ROTL/ROTR/BSWAP/CTTZ/CTLZ/CTPOP` に対応する

`BlockAddress` のlowerに対応する