LLVMのEFI Byte Codeバックエンドを作る

ここでは開発しているLLVMのEFI Byte Code (EBC)バックエンドの概要と EBCバックエンド固有の問題などについてみていく．

ソースコードは以下で公開している．

• yabits/llvm:retrage/ebc
• yabits/clang:retrage/ebc
• yabits/lld:retrage/ebc

動機

過去の記事[1] で説明したように，EBCに対応したコンパイラは 有料のIntel C Compiler for EFI Byte Code のみであり，GCC/ClangではEBC対応がない． そこで，EBC対応のコンパイラを作成する前段階として ELVMのEBCバックエンドを作成した． 詳しくは ELVMのEFI Byte Codeバックエンドを作る[2] を参照したい． しかし，ELVMで生成されるコードは各バックエンドに最適でなく， 生成されるバイナリサイズが大きい傾向にあるという問題がある． また，ELVMにはリンクという作業が存在せず， 各コンパイル時に指定できるのは1つのファイルのみであり， 実用に向かない．

そこでLLVMにEBCのバックエンドを追加する． 開発の対象となるのはLLVM CoreとClang，LLDである．

LLVMにEBCのバックエンドを追加するというアイデアは新しいものではなく， 以下のように過去にGoogle Summer of Codeのテーマとして検討されたこともある[3]．

• [LLVMdev] GSoC idea — C Compiler for EFI Byte Code implement in LLVM

EBCの現状

UEFI Specificationで定義されているEBCの仕様は 後述するように表現が曖昧であるという問題がある． EBCのVMのリファレンス実装は TianoCore/EDK2に含まれている MdeModulePkg/Universal/EbcDxe/EbcExecute.c[4] ため， 実際の仕様はソースコードで確認する必要がある．

Intel C Compiler for EFI Byte Code以外のEBCのツールチェーンには fasmg-ebc][5] というアセンブラがあり， これを利用することで有効なEBCのバイナリを生成できる． しかしfasmg-ebcにはバグがあり コーナーケースなオペランドを正しくエンコードできないという問題がある．

EBCのアセンブリレベルデバッガはUEFI driverとして実装されている． MdeModulePkg/Universal/EbcDxe/EbcDebugger[6] これらはQEMU上のOVMFで動作するが， UEFIではメモリ保護がなされないためバグのあるEBCのバイナリを実行すると システムごと巻き込んでハングしたりリセットされたりなど 生成したバイナリのテストが容易ではない．

そこで先に紹介したELVMのEBCバックエンドをテストできるだけの ユーザ空間で動作するEBCのVMを開発した． 詳しくは ebcvm: A Usermode EFI Byte Code Virtual Machine[7] で紹介している． しかし，この実装も完全な互換性はなく， 現状ではELVMのEBCバックエンドについてebcvmでは全てのテストが通るものの OVMFではいくつかのテストに失敗する．

以上のように正しいEBCのVMは容易に利用できず， また正しいEBCのバイナリも十分に得られないというのが現状である．

開発方針

LLVMはC++とDSLで書かれた巨大なプロジェクトであり， その全てを把握するのは難しい． LLVMバックエンドの追加については Writing an LLVM Backend[8] が公式ドキュメントとして存在する． LLVMバックエンドについて書かれたドキュメントは次の2つがある．

• Tutorial: Creating an LLVM Backend for the Cpu0 Architecture[8]
• きつねさんでもわかるLLVM[9]

しかし，これらが扱っているLLVMのバージョンは前者は3.1，後者は3.2であり， 2019年7月現在の最新版が8.0.0であることから情報が古いと言う問題がある． また，後述するようにこれらが対象とするCPUアーキテクチャはRISCであり， サポートするバイナリフォーマットもELFであるなど， EBCのバックエンドを作成する上で異なる点も多い． また，これらはLLVM Coreへのバックエンドの追加を対象としており， ClangやLLDの開発については言及されていない．

そこで今回は最近開発が進められているRISC-Vバックエンドを参考にする． lowRISC/riscv-llvm[10] には程よい粒度で綺麗にまとめられたRISC-Vバックエンドがパッチ形式で公開されている． 開発の順番もこれに準拠し，インクリメンタルに作成していくこととする． 目標としてはEBCの全ての命令をサポートし， かつ簡単なCのコードからEBCのバイナリをビルドできるようにする．

LLVMのバックエンドの概観

LLVMのバックエンドはLLVM IRからアセンブリへの変換と アセンブリからオブジェクトファイルの生成を担当する． 実際にターゲット上で実行されるバイナリはリンカによって生成されるため LLVM Coreの範囲外であることに注意したい． LLVMのバックエンドはMCLayerとCodeGenの2つの部分に分けられる． MCLayerではアセンブリとオブジェクトファイルの相互変換を行う． CodeGenではLLVM IRを入力としてアセンブリを生成する．

MCLayerの作成

最初にアセンブラやディスアセンブラを担当するMCLayerを作成する． 具体的には以下のようなことを行う．

• Tripleの追加とEBC COFFの定義
• レジスタとinstruction formatsの定義
• instructionとoperand typeの定義
• MCTargetDesc/ と InstPrinter/ の追加
• AsmParserの追加
• Disassemblerの追加
• fixupのサポート
• テストの追加

実装の全てを紹介することは困難なため詳しくはリポジトリを参照して欲しいが， ここではEBCバックエンドの固有の問題をみていく．

Natural Indexing

過去の記事でも言及している通り， EBCはホスト(native)のアーキテクチャに依存しない 64-bit little endianなバイトコードとその仮想マシンとなっている． EBCは単体では何もできないため，nativeで定義されている関数を EBCから呼び出すことができるようになっている．

native向けUEFI imageはentry pointで 以下のような2つの引数を受け取る．

typedef
EFI_STATUS
(EFIAPI *EFI_IMAGE_ENTRY_POINT) (
    IN EFI_HANDLE       ImageHandle,
    IN EFI_SYSTEM_TABLE *SystemTable
);

ImageHandleはロードされたUEFI imageを指し， SystemTableはUEFIの用意する関数などへのポインタが 含まれた構造体へのポインタである．

これらの引数がどのように渡されるかはアーキテクチャ依存であるが， EBCの場合はスタック経由で逆順にプッシュされた状態で渡される．

ではEBCからSystemTableにアクセスすることを考えてみる． SystemTableは2番目の引数なので最初にプッシュされるため， ImageHanle分をオフセットとして計算する必要がある． しかし，ここで問題がある． EFI_HANDLEの大きさはアーキテクチャ依存であり， 32-bitでは4-byte，64-bitでは8-byteとなっている． しかもEBCではnativeのアーキテクチャは知らされていない． このようにnativeでのアーキテクチャを考える必要があり， 通常のようにオフセットが既知でないという問題がある．

そこでEBCではアドレスのオフセットを計算するために Natural Indexという仕組みを導入している． Natural Indexはnatural unitnとconstant unitcの2つの値をとる． runtimeでこれらの値を以下のように計算して実際のオフセットを計算する．

    Offset = c + n * sizeof(void *)

ここでsizeof(void *)はnativeでのポインタの大きさであある． このようにnでアーキテクチャ依存のオフセットを計算し， cでアーキテクチャ非依存のオフセットを加算する．

Natural IndexingはEBC内部で完結する操作では constant unitのみを使い， nativeとやりとりをする場合のみnatural unitを使うような使い方が考えられる．

Natural Indexingの仕組みはEBC固有のものであり， LLVMには対応するものが存在しない． このため1つのNatural Indexingを2つのImmediateとして扱い， アセンブリ時とディスアセンブル時にそれぞれ独自に エンコードとデコードを行うようにした．

EBC命令の定義が不明瞭

EBCの命令ではよく次のようなオペランドが定義される．

{@} R {Index}

ここでRはレジスタを表し，@はindirectであることを示しており， IndexはNatural Indexがあることを示している． さて，多くのEBCの命令では次のような説明があり， これはIndexつきのdirectなOperand 1は禁止されていることを示している．

Specifying an index value with Operand 1 direct results in an instruction encoding exception.

しかしMOV命令のOperand2も同じような定義を持つ一方で 上記のような説明がなく，明確に可能であるとも書かれていない． EDK2の実装をみるとMOV命令に限ってIndexつきdirectなOperand 2が可能となっている． このようにUEFI SepcificationにあるEBCの定義は不明瞭に場合がある．

EBC命令の定義例

RISCアーキテクチャではエンコードされた命令の長さが固定長であることが多いが， EBCではx86などのCISCアーキテクチャのように可変長である． 厄介なことににEBCでは同一のオペコードを持った命令でも長さが異なる場合がある． これはEBCではOptional Immediate/Indexと呼ばれるオペランドを持っているためである． 例として以下にDIV命令のエンコーディングを示す．

EBCのDIV命令のエンコーディング

0-byte目の7-bit目のビットがセットされていれば 後ろのOptional 16-bit Immediate/Indexが存在することを示す． さらにImmediate/Indexとあるように同じフィールドでも 別のビットがセットされていればエンコードやデコードの方法が異なる． この場合，1-byte目の7-bit目のビットがセットされていれば Natural Indexとして扱い，クリアされていればImmediateとして扱う必要がある．

また， 表からわかるようにビットの立て方によって計算が32-bit/64-bitに変わり， Operand 2やOperand 1がdirect/indirectに変わる． 以上のように一つの命令であっても取りうるビットや命令長が異なる．

以上を踏まえてEBCの命令をLLVMで定義する． LLVMでは基本的にTableGenと呼ばれるDSLを用いて命令を記述する． TableGenはC++のようなクラスの概念があり， 複数の命令で共通する部分がある場合などにクラスを定義して 実際の命令の定義でインスタンス化を行う方法をとることができる． EBCでのDIVの定義は次の通りである．

defm DIV    : EBCALU<0b010000, "div">;

defmは後述するmulticlassをインスタンス化するものである． EBCALUは他の計算操作と共通のmulticlassであり 1番目の引数がオペコード，2番目の引数がニーモニックである． EBCALUは次のような定義である．

multiclass EBCALU<bits<6> opcode, string opcodestr> {
  foreach hasImmIdx = [0b0, 0b1] in {
    foreach is64Bit = [0b0, 0b1] in {
      foreach Op1Indirect = [0b0, 0b1] in {
        foreach Op2Indirect = [0b0, 0b1] in
        def !if(is64Bit, "64", "32")
          # !if(Op1Indirect, "Op1I", "Op1D")
          # !if(Op2Indirect, "Op2I", "Op2D")
          # !cond(!eq(hasImmIdx, 0) : "",
                  !eq(!and(hasImmIdx, Op2Indirect), 0) : "Imm",
                  !eq(!and(hasImmIdx, Op2Indirect), 1) : "Idx")
          : EBCALUBase<opcode, hasImmIdx, is64Bit, Op1Indirect, Op2Indirect,
            (outs GPR:$dst), (ins GPR:$op1, GPR:$op2),
            (ins imm16:$imm), (ins idxn16:$idxn, idxc16:$idxc),
            opcodestr, "$op1", "$op2", "$imm", "(${idxn},${idxc})">;
      }
    }
  }
}

multiclassは複数のclassをまとめて定義するものである． ここではhasImmIdx，is64Bit，Op1Indirect，Op2Indirectをパラメータとして EBCALUBaseを継承したclassを定義する． 詳細には解説しないが，EBCALUBaseは次のような定義となっている． 命令の大きさを示すCodeSizeはhasImmIdxによって定められている．

class EBCALUBase<bits<6> opcode, bit hasImmIdx, bit is64Bit,
          bit Op1Indirect, bit Op2Indirect,
          dag outs, dag ins, dag immins, dag idxins,
          string opcodestr, string op1str, string op2str,
          string immstr, string idxstr>
      : EBCInst2Op<opcode, hasImmIdx, is64Bit, Op1Indirect, Op2Indirect, outs,
        !cond(!eq(hasImmIdx, 0) : ins,
              !eq(!and(hasImmIdx, Op2Indirect), 0) : !con(ins, immins),
              !eq(!and(hasImmIdx, Op2Indirect), 1) : !con(ins, idxins)),
        opcodestr # !if(is64Bit, "64", "32"),
        !if(Op1Indirect, "@", "") # op1str # ", "
      # !if(Op2Indirect, "@", "") # op2str # !if(hasImmIdx, " ", "")
      # !cond(!eq(hasImmIdx, 0) : "",
              !eq(!and(hasImmIdx, Op2Indirect), 0) : immstr,
              !eq(!and(hasImmIdx, Op2Indirect), 1) : idxstr),
        []> {
  bits<3> dst;
  let CodeSize = !if(hasImmIdx, 4, 2);
  let mayLoad = !if(Op2Indirect, 1, 0);
  let mayStore = !if(Op1Indirect, 1, 0);
}

以上のように，EBCの命令をLLVMのTableGenで表現するのは複雑であることがわかる． しかし，EBCでnativeの関数を呼び出す場合， 後述のCodeGenでは取り扱えないのでinline assemblyをサポートしなければならず， 全てのEBCの命令をサポートする必要がある． このため，CodeGenでは使われない命令でも正しく定義する必要がある．

ディスアセンブラの実装

LLVMでは命令をTableGenで記述するとアセンブラだけでなくディスアセンブラも生成してくれるが， 先のmulticlassを使った命令の定義ではNatural IndexingなどEBC固有の命令も含まれているため， TableGenの生成するディスアセンブラでは全てを正しくディスアセンブルできない． このため，EBCバックエンドでは オペコードのデコードにはTablgeGenで生成されるデコーダを利用し， かつOptional Immediate/Indexが存在するかどうかを調べるため TableGenで生成されるデコーダとは別に再度オペコードをデコードし， フラグの有無を調べた上でOptional Immediate/Indexをデコードするように実装している．

fixupの実装

アセンブラはアセンブリをエンコードするだけでなくシンボルの参照を解決するという役割も担っている． 実際にはこの役割は参照するシンボルがどこにあるかによって誰が解決するかが異なってくるが， 参照するシンボルが同一オブジェクトファイル内にある場合はアセンブラが担当することとなる． LLVMのMCLayerではアセンブラによるシンボル参照の解決をfixupという． EBCのバイナリは通常のUEFIのapplicationやdriverのように再配置可能である必要があるため， シンボル参照は相対的ものでなければならない． しかし，EBCでは相対アドレスのオフセットが命令ごとに微妙に異なっているという問題がある．

CodeGenの実装

次にLLVM IRからアセンブリへの変換を行うCodeGenについてみていく． CodeGenではDAGで表現されたコードをターゲットのコードに置き換えていく． 簡単なノードの置き換えで変換できる場合にはTableGenでパターンを書くことで ターゲットのコードへの変換を記述できる． 一方で関数呼出などの一般にターゲットに依存する部分については C++で記述する必要がある．

CodeGenで実装するものは以下の通りである．

• ALU operantions
• Materializing constants
• Memory operation
• Global address operation
• Conditional branches
• Function calls
• SELECT/SELECT_CC
• FrameIndex lowering
• Prologue/Epilogue insertion
• dynamic_stackalloc, stacksave, stackrestore
• Inline assembly

基本的に実装を頑張るしかないのだが， Global address operationでの問題を取り上げる．

アドレス計算の仕組みが十分でない

EBCのバイナリは他のUEFI application/driver同様に relocatableである必要がある． これはUEFIでは対象がどこにロードされるかをUEFI側で決定するためである． このため，EBCでのアドレスの表現が相対アドレスでの表現でなければならない．

EBCには相対アドレスから値を取得するMOVREL命令がある． これは以下のような操作を行う．

    Op1 = [IP + SizeOfThisInstruction + Offset]

図で表すと次のようになる．

MOVREL命令の概略図

さて，Global Addressを扱いたい場合， MOVRELのように相対アドレスの計算を行うが 値の取得まではしない，という命令が欲しくなる． つまり次のような操作が求められている．

    Op1 = IP + SizeOfThisInstruction + Offset

EBCにはこの操作に相当する1命令は存在しない． このため，STORESP+MOVI+ADDの3つの命令を組み合わせることで これを実現する． 具体的には次のような表現になる．

  STORESP R1, IP
  MOVI R2, .Target
  ADD R1, R2
  ...

.Target:
  ...

最初にSTORESP命令で次の命令を指すIPの値をR1に取得する． 次にMOVIで埋め込まれている.Target:へのオフセットをR2に代入する． 最後にR1とR2を足し合わせることで現在ロードされているアドレスでの .Target:の絶対アドレスが計算できる．

ClangとLLD

ClangではTripleとTargetInfoの追加，EBC specific driverを追加した． このdriverのコードの多くはMSVC driverに由来する． LLDではEBCをtargetに加え， SectionChunk::applyRelEBC()という 別オブジェクトファイルのシンボル参照を解決する部分を加えるなどを行った． なお，UEFIではDLLのサポートやPDBのサポートもないため これらの実装は行っていない．

まとめ

本記事ではLLVMのEBCバックエンドについて簡単に紹介した． EBCはあまり洗練された設計になっておらず， 扱いにくいというのが正直な感想である． UEFIも2.8になりEBC自体がOptionalの扱いとなったため， 今後EBCはより一層使われなくなるものと考えられる．

参考文献

• [1] https://retrage.github.io/2018/11/11/efi-byte-code-myth.html
• [2] https://retrage.github.io/2019/07/13/elvm-ebc.html
• [3] https://lists.llvm.org/pipermail/llvm-dev/2010-April/030814.html
• [4] https://github.com/tianocore/edk2/blob/master/MdeModulePkg/Universal/EbcDxe/EbcExecute.c
• [5] https://github.com/pbatard/fasmg-ebc
• [6] https://github.com/tianocore/edk2/tree/master/MdeModulePkg/Universal/EbcDxe/EbcDebugger
• [7] https://retrage.github.io/2018/12/19/introduction-to-ebcvm.html
• [8] https://llvm.org/docs/WritingAnLLVMBackend.html
• [9] https://tatsu-zine.com/books/llvm
• [10] https://github.com/lowRISC/riscv-llvm