FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

RISC-V 64-bit LLVM Backendを試す (2. 独自RISC-V実装を追加する。アーキテクチャの追加とレジスタ)

LLVMについて理解するために、RISC-Vをネタにしていろいろ勉強してみたい。 Release 7.0では一応RISC-Vの32-bitと64-bit版がサポートされているようなので、ビルドに追加して様子を見てみる。

ここで追加するのは、新しい"RISCV_msyksphinz"というアーキテクチャ。基本的にRISC-Vと同じなのだが、Cpu0のサンプルをベースに作るので実装はLLVMの本体に登録されているものとは異なる。

とりあえず実装は以下のリポジトリで進める。ブランチはriscv_msyksphinzを作成した。

github.com

アーキテクチャの定義

アーキテクチャの定義は、CMakeLists.txtに追加する。

  • CMakeLists.txt
# List of all targets to be built by default:
set(LLVM_ALL_TARGETS
  AArch64
...  RISCV_msyksphinz
  )
  • cmake/config-ix.cmake
...
elseif (LLVM_NATIVE_ARCH MATCHES "riscv64-msyksphinz")
  set(LLVM_NATIVE_ARCH RISCV_msyksphinz)
...

include/llvm/BinaryFormat/ELFRelocs/RISCV.defRISC-VのABIで定義されているリロケーションテーブルを追加している。リロケーションについては以下のブログが非常に詳しかった。

intothevoid.hatenablog.com

この定義はRISC-V GCCにも同じような定義がある。

  • riscv-gnu-toolchain/riscv-binutils-gdb/include/elf/riscv.h
/* Relocation types.  */
START_RELOC_NUMBERS (elf_riscv_reloc_type)
  /* Relocation types used by the dynamic linker.  */
  RELOC_NUMBER (R_RISCV_NONE, 0)
  RELOC_NUMBER (R_RISCV_32, 1)
  RELOC_NUMBER (R_RISCV_64, 2)
  RELOC_NUMBER (R_RISCV_RELATIVE, 3)
...
  /* Relocation types not used by the dynamic linker.  */
  RELOC_NUMBER (R_RISCV_BRANCH, 16)
  RELOC_NUMBER (R_RISCV_JAL, 17)
  RELOC_NUMBER (R_RISCV_CALL, 18)
  RELOC_NUMBER (R_RISCV_CALL_PLT, 19)
  RELOC_NUMBER (R_RISCV_GOT_HI20, 20)

E_Flagsの設定。これは各アーキテクチャのプロセッサ固有のフラグについて示している。

  • include/llvm/BinaryFormat/ELF.h
// RISCV Specific e_flags
enum : unsigned {
  EF_RISCV_RVC = 0x0001,
  EF_RISCV_FLOAT_ABI = 0x0006,
  EF_RISCV_FLOAT_ABI_SOFT = 0x0000,
  EF_RISCV_FLOAT_ABI_SINGLE = 0x0002,
  EF_RISCV_FLOAT_ABI_DOUBLE = 0x0004,
  EF_RISCV_FLOAT_ABI_QUAD = 0x0006,
  EF_RISCV_RVE = 0x0008
};
  • riscv-gnu-toolchain/riscv-binutils-gdb/include/elf/riscv.h
/* Processor specific flags for the ELF header e_flags field.  */

/* File may contain compressed instructions.  */
#define EF_RISCV_RVC 0x0001

/* Which floating-point ABI a file uses.  */
#define EF_RISCV_FLOAT_ABI 0x0006

/* File uses the soft-float ABI.  */
#define EF_RISCV_FLOAT_ABI_SOFT 0x0000

/* File uses the single-float ABI.  */
#define EF_RISCV_FLOAT_ABI_SINGLE 0x0002

/* File uses the double-float ABI.  */
#define EF_RISCV_FLOAT_ABI_DOUBLE 0x0004

/* File uses the quad-float ABI.  */
#define EF_RISCV_FLOAT_ABI_QUAD 0x0006

/* The name of the global pointer symbol.  */
#define RISCV_GP_SYMBOL "__global_pointer$"

RISC-Vレジスタの定義

Encのビット数が5だったり、16だったり、32だったりする。これの理由は分からないが、5-bitあればよい気がするので5に削ってみる。

// We have banks of 32 registers each.
class RISCVReg<bits<5> Enc, string n> : Register<n> {
  let HWEncoding = Enc;
}

さらに、32個分のレジスタに対して名前を定義した。これはdefで行う。

  • lib/Target/RISCV_msysksphinz/RISCVRegisterInfo.td
def ZERO : RISCVGPRReg<0,  "x0">,    DwarfRegNum<[0]>;
def RA   : RISCVGPRReg<1,  "x1">,    DwarfRegNum<[1]>;
def SP   : RISCVGPRReg<2,  "x2">,    DwarfRegNum<[2]>;
def GP   : RISCVGPRReg<3,  "x3">,    DwarfRegNum<[3]>;
...

LLVMBuild.txt と CMakeLists.txt

f:id:msyksphinz:20190103014852p:plain
LLVMディレクトリ構造と追加したファイル群

lib/Target/RISCV_msyksphinz には、CMakeLists.txtとLLVMBuild.txtが配置されている。 さらに、サブディレクトリとしてMCTargetDescTargetInfoを作成したのだが、そのどちらにもCMakeLists.txtとLLVMBuild.txtを配置した。

LLVMBuild.txtはどうやらそのディレクトリがどのコンポーネントについてのディレクトリなのかを示しているらしい。

一方で、CMakeLists.txtはそのディレクトリのビルド対象となるファイルと、どのようなライブラリを作成するのかが記述される。

  • RISCV_msyksphinz/MCTargetDesc/LLVMBuild.txt
[component_0]
type = Library
name = RISCV_msyksphinzDesc
parent = RISCV_msyksphinz
required_libraries = MC RISCV_msyksphinzInfo Support
add_to_library_groups = RISCV_msyksphinz
  • RISCV_msyksphinz/MCTargetDesc/CMakeLists.txt
# MCTargetDesc/CMakeLists.txt

add_llvm_library(LLVMRISCV_msyskphinzDesc
  RISCV_msyksphinz_MCTargetDesc.cpp
  )

ビルドできなくて猛烈に迷ったのだが、どうやらMCTargetDescとTargetInfoレジスタは必須で作らなければならないようだ。 そして定義するライブラリの名前も、${ターゲット名}Descとか、${ターゲット名}Infoなどにしなければならない。つまり、今回の場合はRISCV_msyksphinzDescとか、RISCV_msyksphinzInfoというちょっと格好悪い名前になる。

これで、ビルドを試行した。というか、まずはCMakeで最低限エラーが発生しないところまで進めよう。

cmake -G Ninja -DCMAKE_BUILD_TYPE="Debug" -DLLVM_TARGETS_TO_BUILD="RISCV_msyksphinz" ../llvm-riscv-msyksphinz
...
CMake Error in lib/Target/RISCV_msyksphinz/MCTargetDesc/CMakeLists.txt:
  Exporting the target "LLVMRISCV_msyskphinzDesc" is not allowed since its
  linker language cannot be determined


CMake Error in lib/Target/RISCV_msyksphinz/MCTargetDesc/CMakeLists.txt:
  Exporting the target "LLVMRISCV_msyskphinzDesc" is not allowed since its
  linker language cannot be determined

とりあえずエラーは大量に出ているのだが、「ファイルがねえよ」とか、「そんなライブラリねえよ」という問題外のエラーは出なくなったので良しとする。

RISC-V 64-bit LLVM Backendを試す

f:id:msyksphinz:20181111134229p:plain

LLVMについて理解するために、RISC-Vをネタにしていろいろ勉強してみたい。 Release 7.0では一応RISC-Vの32-bitと64-bit版がサポートされているようなので、ビルドに追加して様子を見てみる。

$ cmake -G Ninja -DCMAKE_BUILD_TYPE="Debug" -DLLVM_TARGETS_TO_BUILD="Cpu0" -DLLVM_EXPERIMENTAL_TARGETS_TO_BUILD="RISCV" ../llvm-msyksphinz
$ cmake --build .

まずは、32‐bitと64‐bitで単純な関数をビルドして様子を見る。LLVM Backend tutorialに出てくるch3_1.cppをビルドして様子を見る。

  • ch3_1.cpp
int main()
{
  return 0;
}
$ riscv64-unknown-elf-gcc -c ../lbdex/input/ch3.cpp
$ riscv64-unknown-elf-objdump -d ch3.o

ch3.o:     file format elf64-littleriscv


Disassembly of section .text:

0000000000000000 <main>:
   0:   1141                    addi    sp,sp,-16
   2:   e422                    sd      s0,8(sp)
   4:   0800                    addi    s0,sp,16
   6:   4791                    li      a5,4
   8:   853e                    mv      a0,a5
   a:   6422                    ld      s0,8(sp)
   c:   0141                    addi    sp,sp,16
   e:   8082                    ret
  • LLVMの場合(32-bit)
$ ./bin/clang -target riscv32-unknown-linux-gnu -c ../lbdex/input/ch3.cpp -emit-llvm -o ch3.riscv32.bc
$ ./bin/llvm-dis ch3.riscv32.bc -o -
; ModuleID = 'ch3.riscv32.bc'
source_filename = "../lbdex/input/ch3.cpp"
target datalayout = "e-m:e-p:32:32-i64:64-n32-S128"
target triple = "riscv32-unknown-linux-gnu"

; Function Attrs: noinline norecurse nounwind optnone
define dso_local i32 @main() #0 {
entry:
  %retval = alloca i32, align 4
  store i32 0, i32* %retval, align 4
  ret i32 0
}
$ ./bin/llc -march=riscv32 -relocation-model=pic -filetype=asm ch3.riscv32.bc -o -
main:                                   # @main
# %bb.0:                                # %entry
        addi    sp, sp, -16
        sw      ra, 12(sp)
        sw      s0, 8(sp)
        addi    s0, sp, 16
        sw      zero, -12(s0)
        mv      a0, zero
        lw      s0, 8(sp)
        lw      ra, 12(sp)
        addi    sp, sp, 16
        ret
  • LLVMの場合(64-bit)
$ ./bin/clang -target riscv64-unknown-linux-gnu -c ../lbdex/input/ch3.cpp -emit-llvm -o ch3.riscv64.bc
$ ./bin/llvm-dis ch3.riscv64.bc -o -
; ModuleID = 'ch3.riscv64.bc'
source_filename = "../lbdex/input/ch3.cpp"
target datalayout = "e-m:e-p:64:64-i64:64-i128:128-n64-S128"
target triple = "riscv64-unknown-linux-gnu"

; Function Attrs: noinline norecurse nounwind optnone
define dso_local signext i32 @main() #0 {
entry:
  %retval = alloca i32, align 4
  store i32 0, i32* %retval, align 4
  ret i32 4
}
$ ./bin/llc -march=riscv64 -relocation-model=pic -filetype=asm ch3.riscv64.bc -o -
        .text
        .file   "ch3.cpp"
LLVM ERROR: Cannot select: t12: ch = store<(store 4 into %ir.retval), trunc to i32> t0, Constant:i64<0>, FrameIndex:i64<0>, undef:i64
  t11: i64 = Constant<0>
  t2: i64 = FrameIndex<0>
  t4: i64 = undef
In function: main

うーん、何故か64-bitでllcを実行すると落ちてしまう。どこかDAGが足りていないのか?解析するのにはどうしたらいいんだ?

"Creating an LLVM Backend for the Cpu0 Architecture"をやってみる(15. 関数コール2)

f:id:msyksphinz:20181123225150p:plain

Cpu0のバックエンドをLLVMに追加するプロジェクト、9章の後半では、関数コールの様々な方法についてみてみる。

今回も非常にファイル量が多くて、とりあえずLLVMをビルドするためだけにパッチを作って当てているが、LLVM 7.0は未サポートになっている部分が多く、ソースコードを書き直す必要があった。

github.com

そろそろチュートリアルを読んだだけでは訳が分からなくなってきたので、自分で手を動かしてRISC-Vのバックエンドを追加できるように頑張ってみたい。

Cpu0のバックエンドをLLVMに追加するプロジェクト、9章の後半では、さまざまな形の関数コールをサポートする。

今回も非常にファイル量が多くて、とりあえずLLVMをビルドするためだけにパッチを作って当てているが、LLVM 7.0は未サポートになっている部分が多く、ソースコードを書き直す必要があった。

github.com



構造体のサポート

初期の構造体のサポート

関数コール内での構造体のサポートを行う。

def RetCC_Cpu0EABI : CallingConv<[
  // i32 are returned in registers V0, V1, A0, A1
  CCIfType<[i32], CCAssignToReg<[V0, V1, A0, A1]>>
]>;

構造体の帰り値は帰り値が4つのレジスタを超えない場合、V0, V1, A0, A1に格納する。 もし次の4つのレジスタを超える倍、Cpu0は値をメモリに格納して、レジスタにはそのポインタの場所を格納する。

byval構造体

関数コールの最適化

末尾再帰の最適化(Tail call optimization)

幾つかの状況では、関数の呼び出し元と呼び出し先は同じメモリスタックを共有する。この場合再帰的な関数呼び出しでは、漸近的にスタックの必要量が線形になるか、O(n)か定数かO(1)になる。LLVM IRは末尾呼び出しをサポートする。

  • lbdex/input/ch9_2_tailcall.cpp
int factorial(int x)
{
  if (x > 0)
    return x*factorial(x-1);
  else
    return 1;
}

int test_tailcall(int a)
{
  return factorial(a);
}
$ ./bin/clang -target mips-unknown-linux-gnu -c ../lbdex/input/ch9_2_tailcall.cpp -emit-llvm -o ch9_2_tailcall.bc
$ ./bin/llvm-dis ch9_2_tailcall.bc -o -

define dso_local i32 @_Z9factoriali(i32 signext %x) #0 {
entry:
  %retval = alloca i32, align 4
  %x.addr = alloca i32, align 4
  store i32 %x, i32* %x.addr, align 4
  %0 = load i32, i32* %x.addr, align 4
  %cmp = icmp sgt i32 %0, 0
  br i1 %cmp, label %if.then, label %if.else

if.then:                                          ; preds = %entry
  %1 = load i32, i32* %x.addr, align 4
  %2 = load i32, i32* %x.addr, align 4
  %sub = sub nsw i32 %2, 1
  %call = call i32 @_Z9factoriali(i32 signext %sub)
  %mul = mul nsw i32 %1, %call
  store i32 %mul, i32* %retval, align 4
  br label %return

if.else:                                          ; preds = %entry
  store i32 1, i32* %retval, align 4
  br label %return

return:                                           ; preds = %if.else, %if.then
  %3 = load i32, i32* %retval, align 4
  ret i32 %3
}



再帰の最適化

他の機能のサポート

このセクションでは、

  • PICアドレッシングモードの場合の$gpレジスタの呼び出し元保存
    • jsub命令では24ビットのアドレス範囲のみをサポートしている。これをjalrにより32ビットのアドレス範囲まで拡張した。これには、Cpu0が1命令で32ビットのアドレッシングを可能にさせるためにある。そしてjalrをPICモードの動的リンク関数にも使用する。
  • 可変長引数のサポート
  • 動的なスタックの割り当て

をサポートする。

あけましておめでとうございます 2019

あけましておめでとうございます。本年も、「FPGA開発日記」をよろしくおねがい致します。

f:id:msyksphinz:20171231133926p:plain:w300

昨年は、

  • RISC-Vに関連して4件の発表を行った。特に福岡のMICRO51で発表できたのは貴重な機会だった。
  • ディープラーニングについて理解を深めた。keras2cppを通じて、CNNをC++で実装した。
  • RISC-VのISSを完成させた。ISS上でLinuxを起動させることに成功した。
  • 量子コンピュータの勉強を始めた。量子コンピュータのシミュレータを作って、アルゴリズムの理解を深めた。
  • Chiselの勉強を始めた。5ステージパイプラインのRISC-VプロセッサをChiselで作成し、Chiselの分かるようになってきた。

など、様々なことに手を出した一年でした。

今年の目標として、

  • 引き続きRISC-Vをベースとしたエコシステムの勉強。自分でOSSへの貢献をしていきたい。
  • Vivado-HLSを使って、いろんなシステムを作っていきたい。
    • これは、2017年からの継続目標。何か目標となるアプリケーション(ディープラーニングなども)を、Vivado HLSを使って勉強していきたい。
  • ディープラーニングなどの理解を深め、RISC-Vエコシステムとの連携にも挑戦していきたい。
  • なにか一つ新しい言語を覚えたい。今のブームだとRustかな。Rust, LLVM, RISC-Vなどの関連性も見ていきたい。

去年の目標も継続しているけども!

頑張っていきたいと思います。よろしくお願いします。

年末年始なので今年のまとめをしよう2018

このブログも始めてから4年が経った。 年末年始なので、今年一年はどうだったかな、ということでまとめてみよう。

今年の元旦には、こんな目標を立てていたのだった。

msyksphinz.hatenablog.com

  • 引き続きRISC-Vをベースとしたエコシステムの勉強。自分でOSSへの貢献をしていきたい。
  • Vivado-HLSを使って、いろんなシステムを作っていきたい。ディープラーニングなども、Vivado HLSを使って勉強していきたい。
  • ディープラーニングなどの理解を深め、RISC-Vエコシステムとの連携にも挑戦していきたい
  • モバイルアプリケーションやVoice Kitを活用して、面白いものを作っていきたい。
  • より多くの人に出会いたい。去年はRISC-Vを通じて多くの人々と知り合えた。今年も、RISC-Vと言わず、様々なことにチャレンジして、コミュニティを広げていきたい。

あれー、ほとんどできていない!

  • 引き続きRISC-Vをベースとしたエコシステムの勉強。自分でOSSへの貢献をしていきたい。RISC-Vをベースとしたエコシステムの理解は進んだが、OSSへの貢献はまだまだ。
  • Vivado-HLSを使って、いろんなシステムを作っていきたい。ディープラーニングなども、Vivado HLSを使って勉強していきたい。→ Vivado HLSをほとんど触らなかった。残念。
  • ディープラーニングなどの理解を深め、RISC-Vエコシステムとの連携にも挑戦していきたい→ CNNの実装やNVDLAなどの理解を深めた。RISC-Vエコシステムとの連携はまだまだ。
  • モバイルアプリケーションやVoice Kitを活用して、面白いものを作っていきたい。→ 結局Androidアプリケーションなどの実装はできなかった。
  • より多くの人に出会いたい。去年はRISC-Vを通じて多くの人々と知り合えた。今年も、RISC-Vと言わず、様々なことにチャレンジして、コミュニティを広げていきたい。→ これは達成できたかも。4件の発表と雑誌への寄稿を行った。
f:id:msyksphinz:20181115000946p:plain

これ以外にも、いろいろ達成できたかな。

  • RISC-Vに関連して4件の発表を行った。特に福岡のMICRO51で発表できたのは貴重な機会だった。
  • ディープラーニングについて理解を深めた。keras2cppを通じて、CNNをC++で実装した。
  • RISC-VのISSを完成させた。ISS上でLinuxを起動させることに成功した。
  • 量子コンピュータの勉強を始めた。量子コンピュータのシミュレータを作って、アルゴリズムの理解を深めた。
  • Chiselの勉強を始めた。5ステージパイプラインのRISC-VプロセッサをChiselで作成し、Chiselの分かるようになってきた。

ブログの記事数

今年は、この記事を含めて348記事を書いた。去年が349記事なのでとんとんだ。

Jan Feb Mar Apr Mar Jun Jul Aug Sep Oct Nov Dec Total
2018 33 29 29 29 30 31 27 26 27 30 28 29 348
2017 27 21 30 24 33 30 30 29 29 31 33 32 349
2016 32 31 22 28 25 20 23 19 23 30 29 26 308
2015 20 27 17 6 28 29 35 31 44 31 34 27 329

このブログ自身のこと

おかげさまで多くの人にこのブログを読んでもらっている。記事もたくさん書いたし、連載もたくさんさせてもらった。 自分自身、ちょっとだけHW界隈のインフルエンサーとして、正確かつ公平な記事ということにより注意しなければならない。

半面、あくまでこれは自分自身の趣味のブログだということ。 基本方針は、人に見られるための記事を書くのではなく、「自分のためになる記事」を書くことだ。その方針はずっと崩さずにおきたい。

ツイッターのフォロワー数も、この1年でぐっと増えた。ありがたいことだ。

  • 2016/01/01のフォロワー数: 5
  • 2016/12/31のフォロワー数: 86
  • 2017/12/31のフォロワー数: 292
  • 2018/12/31のフォロワー数: 768

Twitterのフォロワー数はあくまで参考値でしかないが、これほどまでに増えたのは自分でもびっくりしている。

さらに、このブログのアクセス数も、記録を取っている3年前からのグラフを作ってみた。

f:id:msyksphinz:20181227235643p:plain

2018年の後半はすごい事になった。2018年の1月はMeltdown / Spectreの記事がヒットしたことによる。

という訳で、来年もよろしくお願いします。来年も自分の好きなことを、好き勝手にやっていこうと思います。

"Creating an LLVM Backend for the Cpu0 Architecture"をやってみる(14. 関数コール)

f:id:msyksphinz:20181123225150p:plain

Cpu0のバックエンドをLLVMに追加するプロジェクト、9章では、さまざまな形の関数コールをサポートする。

今回も非常にファイル量が多くて、とりあえずLLVMをビルドするためだけにパッチを作って当てているが、LLVM 7.0は未サポートになっている部分が多く、ソースコードを書き直す必要があった。

github.com

関数コールについて。まずは、MIPSのスタックフレームの構造について見ていく。

Mipsのスタックフレーム

まずはCpu0の関数コールの方法について見ていく。Cpu0の関数コールについては2つの方法が存在する。

  • 全ての引数をスタックに積み上げていく。
  • 関数の引数用に予約されたレジスタを経由して渡す。入りきらなかった関数はスタックに積み上げられる。

例えば、Mipsは最初の4つの引数をレジスタ$a0, $a1, $a2, $a3に格納し、それ以外はスタックに積み上げる。

https://jonathan2251.github.io/lbd/_images/13.png
図. Mipsのスタックフレームの構造(https://jonathan2251.github.io/lbd/_images/13.png より引用)
  • lbdex/input/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;
}

最初の4つの引数はレジスタ$a0, - $a3 に格納されることが分かる。残りの2つの引数は 16($sp) と 20($sp) に格納される。以下の図は、引数の渡される方式を示している。 関数の呼び出される側にとって、5番目の引数は48($sp)をロードすることにより呼ばれる。sum_i()のスタックサイズは32であり、16+32($sp)が5番目の引数の格納場所である。

f:id:msyksphinz:20181230205201p:plain
Mipsのスタックフレーム(https://jonathan2251.github.io/lbd/_images/21.pngより引用)

スタックフレームから引数をロードする

ここでは、スタックフレームから引数を渡すための方法を実装する必要がある。 Chapter8_2では、LoawerFormalArguments()を空にしていたためエラーが発生した。Cpu0ではレジスタ経由で2つの引数を渡すことができる。 llc -cpu0-s32-calls=falseだとこの設定が有効になり、llc -cpu0-s32-calls=trueでは、全ての引数がスタック経由で渡されるようになる。

  • analyzeFormalArguments()を定義する。

ArgLocs.size()は6となり、書く引数の情報はArgLocs[i]に格納されている。bool IsRegLoc = VA.isRegLoc();がTrueならば、引数はレジスタ渡しされる。VA.isMemLoc()がTrueならば、引数はスタック経由でアクセスされる。

さらに、呼び出し規約に基づいて、以下の命令を追加する。

  • swi(Software Interrupt)
  • jsub(Jump to subroutine)
  • jalr(Indirect Jump)

/// Jump & link and Return Instructions
let Predicates = [Ch9_1] in {
def JSUB    : JumpLink<0x3b, "jsub">;
}

let Predicates = [Ch9_1] in {
def JALR    : JumpLinkReg<0x39, "jalr", GPROut>;
}

命令の生成は以下となる。関数のジャンプアドレスがtglobaladdrまたはtexternalsymにマッチするとJSUBが呼び出される。

  • lbdex/chapters/Chapter9_1/Cpu0InstrInfo.td

let Predicates = [Ch9_1] in {
def : Pat<(Cpu0JmpLink (i32 tglobaladdr:$dst)),
          (JSUB tglobaladdr:$dst)>;
def : Pat<(Cpu0JmpLink (i32 texternalsym:$dst)),
          (JSUB texternalsym:$dst)>;

入りきらない引数をスタックフレームに格納する。

引数の数が多すぎるとき、入りきらない引数をメモリに格納し、呼び出された側の関数でメモリに格納された引数を取り出す。

Pseudo hook instruction ADJCALLSTACKDOWN and ADJCALLSTACKUP

DAG.getCALLSEQ_START()

Graphvizを使いながらLowercall()を読む

DAGを使うと、lowerCall()の挙動を確認することができる。

文字列の初期化

以下のような文字列の初期化に対しての処理を考える。初期化する文字列が長い場合は、memcpyを使って初期値を設定する。短めの文字列の場合は、初期値をメモリにストアする方式をとる。

  • lbdex/input/ch9_1_2.cpp

int main()
{
  char str[81] = "Hello world";
  char s[6] = "Hello";

return 0; }

$ ./bin/clang  -target mips-unknown-linux-gnu -c ../lbdex/input/ch9_1_2.cpp -emit-llvm -o ch9_1_2.bc
$ ./bin/llvm-dis ch9_1_2.bc -o -
...
  %0 = bitcast [81 x i8] %str to i8
  call void @llvm.memcpy.p0i8.p0i8.i32(i8 align 1 %0, i8 align 1 getelementptr inbounds ([81 x i8], [81 x i8] @_ZZ4mainE3str, i32 0, i32 0), i32 81, i1 false)
  %1 = bitcast [6 x i8] %s to i8
  call void @llvm.memcpy.p0i8.p0i8.i32(i8 align 1 %1, i8 align 1 getelementptr inbounds ([6 x i8], [6 x i8] @_ZZ4mainE1s, i32 0, i32 0), i32 6, i1 false)
...

$ ./bin/llc -march=cpu0 -mcpu=cpu032II -filetype=asm ch9_1_2.bc -o -
...
        lui     $2, %hi($ZZ4mainE3str)
        ori     $5, $2, %lo($ZZ4mainE3str)
        addiu   $4, $sp, 24
        jsub    memcpy
        nop
...
        lbu     $3, 5($2)
        lbu     $4, 4($2)
        shl     $4, $4, 8
        or      $3, $4, $3
        sh      $3, 20($sp)
        lbu     $3, 3($2)
        lbu     $4, 2($2)
        shl     $4, $4, 8
        or      $3, $4, $3
        lbu     $4, 1($2)
        lbu     $2, 0($2)
        shl     $2, $2, 8
        or      $2, $2, $4
        shl     $2, $2, 16
        or      $2, $2, $3
        st      $2, 16($sp)
        addu    $2, $zero, $9
...

"Creating an LLVM Backend for the Cpu0 Architecture"をやってみる(13. 制御文のサポート)

f:id:msyksphinz:20181123225150p:plain

Cpu0のバックエンドをLLVMに追加するプロジェクト、8章では、if文などの制御文をサポートする。

今回も非常にファイル量が多くて、とりあえずLLVMをビルドするためだけにパッチを作って当てているが、LLVM 7.0は未サポートになっている部分が多く、ソースコードを書き直す必要があった。

  • Chapter8の実装を追加したもの

github.com

github.com

制御フロー文

分岐命令のサポートを行う。if文をコンパイルすると、icmp文が生成される。

  %cmp = icmp eq i32 %0, 0
  br i1 %cmp, label %if.then, label %if.end

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
}

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

$ bin/llc -march=cpu0 -mcpu=cpu032I -relocation-model=pic -filetype=asm ch8_1_1.bc -o -
        ld      $3, 4($sp)
        cmp     $sw, $3, $2
        jne     $sw, $BB0_2
        jmp     $BB0_1
$BB0_1:                                 # %if.then
        ld      $2, 4($sp)
        addiu   $2, $2, 1
        st      $2, 4($sp)
        jmp     $BB0_2
$BB0_2:                                 # %if.end
        ld      $2, 4($sp)
        addiu   $sp, $sp, 8
        ret     $lr

cpu032Iとcpu032IIで生成される命令が異なる。cpu032IIはconditional branchが使えるので生成される命令が異なる。

$ bin/llc -march=cpu0 -mcpu=cpu032II -relocation-model=pic -filetype=asm ch8_1_1.bc -o -
        ld      $2, 4($sp)
        bne     $2, $zero, $BB0_2
        jmp     $BB0_1
$BB0_1:                                 # %if.then
        ld      $2, 4($sp)
        addiu   $2, $2, 1
        st      $2, 4($sp)
        jmp     $BB0_2
$BB0_2:                                 # %if.end
        ld      $2, 4($sp)
        addiu   $sp, $sp, 8
        ret     $lr

長距離分岐サポート

cpu032IIでは、ジャンプのオフセットが24-bitから16-bitに削減されている。もしも16-bitよりも遠い距離をジャンプすることになると、cpu032IIはコードの生成に失敗する。そこで、長距離分岐をサポートする。

./bin/clang -c -target mips-unknown-linux-gnu ../lbdex/input/ch8_2_longbranch.cpp -emit-llvm -o ch8_2_longbranch.bc
        ld      $2, 12($sp)
        ld      $3, 8($sp)
        slt     $2, $2, $3
        beq     $2, $zero, $BB0_2
        nop
# %bb.1:                                # %if.then
        addiu   $2, $zero, 1
        st      $2, 4($sp)
$BB0_2:                                 # %if.end
        ld      $2, 4($sp)
        addiu   $sp, $sp, 16
        ret     $lr

Cpu0バックエンド最適化: 未使用JMP命令の削除

ここでは、未使用のJMP命令を削除するバックエンド最適化を追加する。このアルゴリズムはシンプルで、最適化のチュートリアルに適している。

DelJmp関数は不要なジャンプ命令を削除している。不要なジャンプ命令とは、ジャンプ先が次の命令だった場合である。Cpu0::JMPのジャンプ先が次のブロック(=&MBBN)出会った場合に削除する。

  if (I->getOpcode() == Cpu0::JMP && I->getOperand(0).getMBB() == &MBBN) {
    // I is the instruction of "jmp #offset=0", as follows,
    //     jmp  $BB0_3
    // $BB0_3:
    //     ld   $4, 28($sp)
    ++NumDelJmp;
    MBB.erase(I);   // delete the "JMP 0" instruction
    Changed = true; // Notify LLVM kernel Changed
  }
./bin/clang -c -target mips-unknown-linux-gnu ../lbdex/input/ch8_2_deluselessjmp.cpp -emit-llvm -o ch8_2_deluselessjmp.bc
bin/llc -march=cpu0 -mcpu=cpu032II -relocation-model=pic -filetype=asm -stats ch8_2_deluselessjmp.bc -o -

del-jmp8が8回適用されている。

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

46 asm-printer       - Number of machine instrs printed
34 bitcode-reader    - Number of Metadata records loaded
 2 bitcode-reader    - Number of MDStrings loaded
14 dagcombine        - Number of dag nodes combined
 8 del-jmp           - Number of useless jmp deleted
 5 delay-slot-filler - Number of delay slots filled
10 isel              - Number of blocks selected using DAG
32 isel              - Number of times dag isel has to try another path
 1 isel              - Number of entry blocks encountered
16 prologepilog      - Number of bytes used for stack in all functions
28 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

分岐遅延スロットを埋める最適化

まずは、分岐遅延スロットをNOPで埋める処理を行う。

  for (Iter I = MBB.begin(); I != MBB.end(); ++I) {
    if (!hasUnoccupiedSlot(&*I))
      continue;

    ++FilledSlots;
    Changed = true;

    // Bundle the NOP to the instruction with the delay slot.
    BuildMI(MBB, std::next(I), I->getDebugLoc(), TII->get(Cpu0::NOP));
    MIBundleBuilder(MBB, I, std::next(I, 2));
  }

分岐命令

分岐命令を生成する。2項演算子による選択は、selectが使用される。

./bin/clang -c -target mips-unknown-linux-gnu ../lbdex/input/ch8_2_select.cpp -emit-llvm -o ch8_2_select.bc
./bin/llvm-dis ch8_2_select.bc -o -
entry:
  %a = alloca i32, align 4
  %c = alloca i32, align 4
  store volatile i32 1, i32* %a, align 4
  store i32 0, i32* %c, align 4
  %0 = load volatile i32, i32* %a, align 4
  %tobool = icmp ne i32 %0, 0
  %lnot = xor i1 %tobool, true
  %1 = zext i1 %lnot to i64
  %cond = select i1 %lnot, i32 1, i32 3
  store i32 %cond, i32* %c, align 4
  %2 = load i32, i32* %c, align 4
  ret i32 %2
}

最終的には、movzなどの命令が使用される。

$ ./bin/llc -march=cpu0 -mcpu=cpu032I -relocation-model=pic -filetype=asm ch8_2_select.bc -o -
        ld      $3, 4($sp)
        addiu   $4, $zero, 3
        movn    $2, $4, $3
        st      $2, 0($sp)
        ld      $2, 0($sp)
        addiu   $sp, $sp, 8
        ret     $lr

Phiノード

ここでは、Phiノードのサポートを行う。Phiノードというのは知らなかったのだが、SSAにおける最適化の一手法らしい。

Phiノードの説明はWikipediaが分かりやすかった。

静的単一代入 - Wikipedia

f:id:msyksphinz:20181227232842p:plain
https://upload.wikimedia.org/wikipedia/commons/8/84/SSA_example1.3.png より引用。

条件に合わせてy1とy2のどちらかがy3に格納されるのだが、通常はそれを決める手段がない。 そこで、PhiノードというΦ(y1, y2)の関数を追加して、最後のブロックで正しいyを参照できるようになる。

これを試験するためには、lbdex/inputs/ch8_2_phinode.cppを使用する。

  • lbdex/inputs/ch8_2_phinode.cpp
/// start
int test_phinode(int a , int b, int c)
{
  int d = 2;

  if (a == 0) {
    a++; // a = 1
  }
  else if (b != 0) {
    a--; // b = 2
  }
  else if (c == 0) {
    a += 2;
  }
  d = a + b;

  return d;
}

以下のように-O3を追加することでPhiノードを追加する。

$ ./bin/clang -O3 -c -target mips-unknown-linux-gnu ../lbdex/input/ch8_2_phinode.cpp -emit-llvm -o ch8_2_phinode.bc
$ bin/llvm-dis ch8_2_phinode.bc -o -
entry:
  %cmp = icmp eq i32 %a, 0
  br i1 %cmp, label %if.end7, label %if.else

if.else:                                          ; preds = %entry
  %cmp1 = icmp eq i32 %b, 0
  br i1 %cmp1, label %if.else3, label %if.then2

if.then2:                                         ; preds = %if.else
  %dec = add nsw i32 %a, -1
  br label %if.end7

if.else3:                                         ; preds = %if.else
  %cmp4 = icmp eq i32 %c, 0
  %add = add nsw i32 %a, 2
  %spec.select = select i1 %cmp4, i32 %add, i32 %a
  br label %if.end7

if.end7:                                          ; preds = %entry, %if.else3, %if.then2
  %a.addr.0 = phi i32 [ %dec, %if.then2 ], [ %spec.select, %if.else3 ], [ 1, %entry ]
  %add8 = add nsw i32 %a.addr.0, %b
  ret i32 %add8

最後に、%a.addr.0 = phi i32 [ %dec, %if.then2 ], [ %spec.select, %if.else3 ], [ 1, %entry ]が追加されている。これがPhiノードというものらしい。

実際にllcを実行してみると、エラーとなった。これはノードが足りないらしい。

$ bin/llc -march=cpu0 -mcpu=cpu032I -relocation-model=pic -filetype=asm ch8_2_phinode.bc -o -
        .text
        .section .mdebug.abiO32
        .previous
        .file   "ch8_2_phinode.cpp"
llc: /home/msyksphinz/work/riscv/llvm-msyksphinz/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp:9025: void llvm::SelectionDAGISel::LowerArguments(const llvm::Function &): Assertion `InVals.size() == Ins.size() && "LowerFormalArguments didn't emit the correct number of values!"' failed.
Stack dump:
0.      Program arguments: bin/llc -march=cpu0 -mcpu=cpu032I -relocation-model=pic -filetype=asm ch8_2_phinode.bc -o -
1.      Running pass 'Function Pass Manager' on module 'ch8_2_phinode.bc'.
2.      Running pass 'CPU0 DAG->DAG Pattern Instruction Selection' on function '@_Z12test_phinodeiii'