FIXME

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

  • だ・である調をです・ます調に変える。

  • 実際にやってみる。

    • 現状過去の作業ログを切り貼りしながら書いているので通してちゃんと動くかは良くわからない。

  • LLVM 12.0.0に対応させる

この文書について

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

この文書はGitによって管理されています。 リポジトリはGitHubにて 公開しています。同じリポジトリで、この文書を書くにあたってベースとしている メモ（ RV32Kv1・ RV16Kv2・ CAHPv3）を読むことができます。

この文書に（おおよそ）則って開発された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のバージョンはv12.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開発日記[164]

    • Cpu0の資料[35]をもとに1からRISC-Vバックエンドを作成する過程がブログ[44]として公開されている。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-2003f 処理の流れの例[163]

    • 2003f用のLLVMバックエンドの処理について説明したページ。

書籍

  • 『きつねさんでもわかるLLVM〜コンパイラを自作するためのガイドブック〜』[7]

    • 数少ない日本語資料。Passやバックエンドの各クラスについて説明している。[31]と合わせて大まかな流れを掴むのに良い。

    • ただし書籍中で作成されているバックエンドは機能が制限されており、またコードベースも多少古い。

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

バックエンド

  • RISC-V[5]

    • パッチ群が開発ドキュメントとともに公開されている[10]。以降の開発はこれをベースに行う。

  • Lanai[103]

    • Googleが開発した32bit RISCの謎アーキテクチャ。全く実用されていないが、バックエンドが単純に設計されておりコメントも豊富のためかなり参考になる[4][5]。

  • Sparc

    • [18]でも説明に使われており、コメントが豊富。

  • M68k[170]

    • 最近（2021年）追加された[170]バックエンド。新し目のLLVMにバックエンドを追加する例として貴重。

  • C-SKY[167]

    • 最近（2020年）追加された[166]バックエンド。新し目のLLVMにバックエンドを追加する例として貴重。

  • x86

    • みんな大好きx86。貴重なCISCの資料であり、かつ2オペランド方式を採用する場合に実装例を与えてくれる。あと EFLAGS の取り回しなども参考になるが、全体的にコードは読みにくい。ただLLVMの命名規則には従うため、他のバックエンドからある程度推論をして読むのが良い。

ISAの仕様を決める

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

命令の一覧

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

47ed98f09cd52a746c7ba2a0404758d3c1e047bc

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

LLVMのコードを取得する

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

$ git clone https://github.com/llvm/llvm-project.git
$ cd llvm-project
$ git checkout llvmorg-12.0.0
$ git switch -c cahpv4

CAHPv4をTripleに追加する

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

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

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

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

バックエンドを追加する

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

まずビルドのために CMakeLists.txt を用意します。 またCAHPv4に関する情報を提供するために CAHPV4TargetInfo.cpp や CAHPV4TargetMachine.cpp などを記述します。

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

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

LLVM 11までは、ビルドのために CMakeLists.txt の他に LLVMBuild.txt が必要でしたが、 外部ツールへの依存を避けるために CMakeLists.txt のみで全てを賄うようになりました[169]。

LLVMをビルドする

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

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

  • cmake

  • ninja

  • clang

  • clang++

  • lld

ビルドを行うための設定を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="CAHPV4" \
    ../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/ ディレクトリ以下にコンパイルされたバイナリが生成されます。 例えば次のようにして、CAHPv4バックエンドが含まれていることを確認できます。

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

  Registered Targets:
    cahpv4 - CAHPV4

ここでは開発用にデバッグビルドを行いました。 一方で、他人に配布する場合などはリリースビルドを行います。 その際は次のように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="CAHPV4" \
    ../llvm

LLVMをテストする

llvm-lit を使用してLLVMをテストできます。 例えば先程追加したテストを実行するには次のようにします。

$ bin/llvm-lit -s --filter "Triple" test # Tripleに関するテストを実行する。

他にも次のように実行できます。

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

アセンブラを作る

1093d7862020d0e98195c47e7f00294415803d0c

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

TableGenファイルを追加する

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

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

  • CAHPV4.td: 下のTableGenファイルをincludeし、その他もろもろを定義。

  • CAHPV4RegisterInfo.td: レジスタを定義。

  • CAHPV4InstrFormats.td: 命令形式を定義。

  • CAHPV4InstrInfo.td: 命令を定義。

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

include "llvm/Target/Target.td"
include "CAHPV4RegisterInfo.td"
include "CAHPV4InstrInfo.td"

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

CAHPV4RegisterInfo.td ではCAHPV4に存在するレジスタを定義します。 まず Register を継承して class CAHPV4Reg を作り、これに基本的なレジスタの性質をもたせます。 ついで class CAHPV4Reg の実体として X0 から X31 を作成します。 alt にはレジスタの別名を指定します。 最後に、レジスタをまとめて RegisterClass である GPR （General Purpose Register; 汎用レジスタの意）を定義します。 ここでレジスタを並べる順番が先であるほどレジスタ割り付けで割り付けられやすいため、 caller-savedなもの（使ってもspill outが起こりにくいもの）を先に並べておきます。 並べる際には X0, X1, …​ と並べてもよいのですが、連番の場合は sequence を使うことができます。 RegisterClass のテンプレート引数には、他に、名前空間・レジスタの型・ メモリ上に保存されるときのアラインメントを指定します。

def GPR : RegisterClass<"CAHPV4", [i16], 16, (add
    (sequence "X%u", 10, 17), // X10, X11, ..., X17, と明示的に書いても同じ意味
    (sequence "X%u", 5, 7),
    (sequence "X%u", 28, 31),
    (sequence "X%u", 8, 9),
    (sequence "X%u", 18, 27),
    (sequence "X%u", 0, 4)
  )>;

このあと命令を定義する際にはこの RegisterClass 単位で指定するため、 特定のレジスタしか取らないような命令では、その都度新しい RegisterClass を作る必要があります。

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

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

  dag OutOperandList = outs;
  dag InOperandList = ins;

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

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

  let Size = 4;
  bits<32> Inst;
}

次いで、R形式（オペランドにレジスタを3つとる）命令を class CAHPV4InstR として定義します。 class CAHPV4Inst を継承します。

// R-instruction format
class CAHPV4InstR<bits<11> opcode, dag outs, dag ins, string opcodestr, string argstr>
: CAHPV4Inst<outs, ins, opcodestr, argstr> {
  bits<5> rd;
  bits<5> rs1;
  bits<5> rs2;

  let Inst{31-26} = 0;
  let Inst{25-21} = rs2;
  let Inst{20-16} = rd;
  let Inst{15-11} = rs1;
  let Inst{10-0} = opcode;
}

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

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

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

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

  let Pattern = [];

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

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

  // 命令のエンコーディングは次の通り。
  let Inst{31-26} = 0;               // 26〜31bit目は0
  let Inst{25-21} = rs2;             // 21〜25bit目はrs2
  let Inst{20-16} = rd;              // 16〜20bit目はrd
  let Inst{15-11} = rs1;             // 11〜15bit目はrs1
  let Inst{10-0} = 0b00000001000;    // 0〜10bit目はADDのopcode

  // 出力はレジスタクラス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]。

（CAHPv3の） 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/CAHPV4/ -I ../llvm/include/ -I ../llvm/lib/Target/ ../llvm/lib/Target/CAHPV4/CAHPV4.td

なおTableGenファイル中で使用した RegisterClass や Instruction などは llvm/include/llvm/Target/Target.td にてコメントとともに定義されています。 フィールドの値が何を意味するかわからない場合に参照してください。

MCTargetDesc を追加する

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

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

  • CAHPV4MCAsmInfo

  • CAHPV4MCInstrInfo

  • CAHPV4MCRegisterInfo

  • CAHPV4MCSubtargetInfo

  • CAHPV4MCCodeEmitter

  • CAHPV4AsmBackend

  • CAHPV4ELFObjectWriter

順に説明します。

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

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

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

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

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

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

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

上記を実装してビルドします。一度使ってみましょう。 まずテスト用の入力アセンブリファイルを用意します。

$ cat foo.s
add x1, x2, x3
add x16, x17, x18
sub x1, x2, x3
xor x1, x2, x3
or x1, x2, x3

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]。 このエラーメッセージはCAHPV4ターゲットがアセンブリのパーズ（構文解析）に対応していない ことを意味しています。これは次の節で実装します。

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;
}

CAHPV4AsmParser を追加する

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

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

この際にオペランドを表すクラスとして CAHPV4Operand を定義・使用しています。 現在はオペランドとして現れうるのはレジスタと命令などのトークンなので、 その旨を記述します。即値のオペランドなどは後ほど対応します。 なおラベルなどの識別子がオペランドに来るアセンブリには まだ対応していませんが、後ほど対応する際にはトークンではなく 即値として対応することになります。

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

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

# 先ほどと同じfoo.sを入力として使用します。
$ cat foo.s
add x1, x2, x3
add x16, x17, x18
sub x1, x2, x3
xor x1, x2, x3
or x1, x2, x3

$ bin/llvm-mc -arch=cahpv4 -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 f6 00 01 00 00 00 00 00 00 00 00 00 00 00  >................<
000020 70 00 00 00 00 00 00 00 34 00 00 00 00 00 28 00  >p.......4.....(.<
000030 04 00 01 00 08 10 61 00 08 88 50 02 18 10 61 00  >......a...P...a.<
000040 28 10 61 00 38 10 61 00 00 00 00 00 00 00 00 00  >(.a.8.a.........<
000050 00 00 00 00 00 00 00 00 00 2e 74 65 78 74 00 2e  >..........text..<
000060 73 74 72 74 61 62 00 2e 73 79 6d 74 61 62 00 00  >strtab..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 00 00 00 00 00 00 00 00 07 00 00 00 03 00 00 00  >................<
0000a0 00 00 00 00 00 00 00 00 58 00 00 00 17 00 00 00  >........X.......<
0000b0 00 00 00 00 00 00 00 00 01 00 00 00 00 00 00 00  >................<
0000c0 01 00 00 00 01 00 00 00 06 00 00 00 00 00 00 00  >................<
0000d0 34 00 00 00 14 00 00 00 00 00 00 00 00 00 00 00  >4...............<
0000e0 04 00 00 00 00 00 00 00 0f 00 00 00 02 00 00 00  >................<
0000f0 00 00 00 00 00 00 00 00 48 00 00 00 10 00 00 00  >........H.......<
000100 01 00 00 00 01 00 00 00 04 00 00 00 10 00 00 00  >................<
000110

0x34から0x3dにある 08 10 61 00 …​ が出力であり、 正しく生成されていることが分かります[11]。

CAHPV4InstPrinter を実装する

bc9465e32f41842ea6cc5796f166fe594635c830

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

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

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

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

# 前の節と同じfoo.sを使用
$ bin/llvm-mc -arch=cahpv4 -show-encoding foo.s
	.text
	add	x1, x2, x3                      # encoding: [0x08,0x10,0x61,0x00]
	add	x16, x17, x18                   # encoding: [0x08,0x88,0x50,0x02]
	sub	x1, x2, x3                      # encoding: [0x18,0x10,0x61,0x00]
	xor	x1, x2, x3                      # encoding: [0x28,0x10,0x61,0x00]
	or	x1, x2, x3                      # encoding: [0x38,0x10,0x61,0x00]

InstPrinter は、以前はそれ専用のディレクトリを作成してコードを記述していましたが、 バックエンドによっては不都合があるということで MCTargetDesc ディレクトリに配置する形に 変更されました[171]。

テストを書く

964d687f03455d613cb718bc36f62479c2ff2193

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

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

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

$ bin/llvm-lit -as --filter "CAHPV4" test
PASS: LLVM :: MC/CAHPV4/valid.s (1 of 2)
Script:
--
: 'RUN: at line 1';   /home/anqou/ano/secure_vm/llvm-project/build/bin/llvm-mc /home/anqou/workspace/anqura/ano/secure_vm/llvm-project/llvm/test/MC/CAHPV4/valid.s -triple=cahpv4 -show-encoding      | /home/anqou/ano/secure_vm/llvm-project/build/bin/FileCheck --allow-unused-prefixes=false -check-prefixes=CHECK,CHECK-INST /home/anqou/workspace/anqura/ano/secure_vm/llvm-project/llvm/test/MC/CAHPV4/valid.s
--
Exit Code: 0


********************
PASS: LLVM :: MC/CAHPV4/invalid.s (2 of 2)
Script:
--
: 'RUN: at line 1';   not /home/anqou/ano/secure_vm/llvm-project/build/bin/llvm-mc -triple cahpv4 < /home/anqou/workspace/anqura/ano/secure_vm/llvm-project/llvm/test/MC/CAHPV4/invalid.s 2>&1 | /home/anqou/ano/secure_vm/llvm-project/build/bin/FileCheck --allow-unused-prefixes=false /home/anqou/workspace/anqura/ano/secure_vm/llvm-project/llvm/test/MC/CAHPV4/invalid.s
--
Exit Code: 0


********************

Testing Time: 0.03s
  Excluded: 41952
  Passed  :     2

即値を扱う命令を追加する

b12b28fc5a9e544fef657f45ffafb900cdf5e4e0

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

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 simm11 : Operand<i16> {
  let ParserMatchClass = SImmAsmOperand<11>;
}

続いて命令の「形」を定義します。

class CAHPV4InstIS11<bits<11> opcode, dag outs, dag ins, string opcodestr, string argstr>
: CAHPV4Inst<outs, ins, opcodestr, argstr> {
  bits<5> rd;
  bits<5> rs1;
  bits<11> imm;

  let Inst{31-21} = imm;
  let Inst{20-16} = rd;
  let Inst{15-11} = rs1;
  let Inst{10-0} = opcode;
}

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

def ADDI : CAHPV4InstIS11<0b01000001000, (outs GPR:$rd), (ins GPR:$rs1, simm11:$imm),
                          "addi", "$rd, $rs1, $imm">;

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

TableGenにて定義・使用した即値を正しく認識するために isSImm11 などの メンバ関数を定義する必要があります。これらの関数は後述の MatchInstructionImpl 内で 使用されます。

!!!ここより下はまだ書き直されていません!!!

メモリ演算を追加する

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( という識別子として 認識されてしまうためです。

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

次いでこれらのアセンブリをパーズできるように 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に変換する。

%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に対応する

参考文献

1. この 段落はクリエイティブ・コモンズより引用。
2. 論文とスライドも怪しいものだが、著者が一致しているので多分正しいだろう。
3. これとは別の発表で「コンパイラ開発してない人生はFAKE」という名言が飛び出した勉強会[114]。
4. LLVMバックエンドの開発を円滑にするためのアーキテクチャなのではと思うほどに分かりやすい。
5. 後のSparcについて[116] にて指摘されているように、商業的に成功しなかったバックエンドほどコードが単純で分かりやすい。
6. 一方でx86など 複雑なエンコーディングを行うISAの場合は Inst フィールドを使用せず、 自前で変換を行っている。
7. 内部で llvm::MCRegisterInfo::InitMCRegisterInfo [55] を呼び出していることからわかります。
8. CAHPv4マシンの仕様などはこの世に存在しないので、 これらは勝手に決めたものです。
9. 失敗した場合は assertなどで異常終了し、スタックトレースなどが表示されます。
10. なお以下では しばらくの間、命令を表す add などの文字列そのものも「オペランド」として扱います。
11. このアセンブリはcahpv4-simのテストと 同じものになっているので、cahpv4-simのテストと比較することで正しいかを（ある程度）判断できます。
12. この場合 AltNames が指定されていないレジスタ（条件分岐のためのフラグなど）があるとエラーとなります。 アセンブリ中に表示され得ないレジスタにもダミーの名前をつける必要があります。
13. この実装手法はRISC Vのそれによる。かなりad-hocだと感じるが、他の方法が分からないのでとりあえず真似る。