FPGA開発日記

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

ハードウェアの構築からチップ設計までを一気通貫するフレームワークChipyardを試す(1. 環境構築とシミュレーション)

f:id:msyksphinz:20191020175831p:plain

ChipyardというのはRISC-Vをベースとしたチップ設計のためのフレームワークで、ツールセット・ライブラリ・デザインなどを一つにまとめたフレームワークのようだ。このフレームワークを使用することで、ハードウェアの設計からシミュレーション・論理合成・チップ設計まどを一気通貫するフローで行うことができるということを売りにしている。

chipyard.readthedocs.io

  • クイックスタート

まずはリポジトリをcloneして環境を構築する。大量のサブリポジトリがダウンロードされるので注意。

git clone https://github.com/ucb-bar/chipyard.git
cd chipyard
./scripts/init-submodules-no-riscv-tools.sh
  • RISC-Vツールセットのインストール

次に、RISC-Vのツールセット群をダウンロードしてビルドする。これも結構な量のツールをダウンロードしてくるのでディスク量に注意。duしてみると15GB程度ディスクを使用していた。

./scripts/build-toolchains.sh

ビルドは自動的に並列実行されるようになっているが、おかげさまで使っているPCのリソースを全部持って行かれた。完了するとenv.shをsourceしておく。

source ./env.sh
  • ハードウェアのシミュレーション

次に、サンプルプロジェクトをビルドしてRTLシミュレーションを行う。私はVerilatorしか持っていないのでVerilatorを使用する。

cd sims/verilator
make  # デザインのコンパイル

デザインの生成とコンパイルが行われる。しばらくすると終了するのでシミュレーションを実行する。

./simulator-example-DefaultRocketConfig $RISCV/riscv64-unknown-elf/share/riscv-tests/isa/rv64ui-p-simple +jtag_rbb_enable=1

This emulator compiled with JTAG Remote Bitbang client. To enable, use +jtag_rbb_enable=1.
Listening on port 54884

あれ、+jtag_rbb_enable=1を設定しているのになぜか上手く行かない。とりあえず全部のテストコードを流してみるとうまくいくだろうか。

make run-asm-tests
make run-bmark-tests

しばらく時間がかかるが正しく動作しているように見える。

最後に結果が表示され、すべてPASSとなった。

  [ PASSED ] /home/msyksphinz/work/riscv/chipyard/chipyard/sims/verilator/output/example.TestHarness.DefaultRocketConfig/rv64um-v-mul.out   Completed after 61431 cycles
  [ PASSED ] /home/msyksphinz/work/riscv/chipyard/chipyard/sims/verilator/output/example.TestHarness.DefaultRocketConfig/rv64um-v-mulh.out          Completed after 61444 cycles
  [ PASSED ] /home/msyksphinz/work/riscv/chipyard/chipyard/sims/verilator/output/example.TestHarness.DefaultRocketConfig/rv64um-v-mulhsu.out        Completed after 61519 cycles
  [ PASSED ] /home/msyksphinz/work/riscv/chipyard/chipyard/sims/verilator/output/example.TestHarness.DefaultRocketConfig/rv64um-v-mulhu.out         Completed after 61530 cycles
  ...
  [ PASSED ] /home/msyksphinz/work/riscv/chipyard/chipyard/sims/verilator/output/example.TestHarness.DefaultRocketConfig/rv64ui-v-sraw.out          Completed after 74209 cycles
  [ PASSED ] /home/msyksphinz/work/riscv/chipyard/chipyard/sims/verilator/output/example.TestHarness.DefaultRocketConfig/rv64ui-v-srliw.out         Completed after 54595 cycles
  [ PASSED ] /home/msyksphinz/work/riscv/chipyard/chipyard/sims/verilator/output/example.TestHarness.DefaultRocketConfig/rv64ui-v-srlw.out          Completed after 74166 cycles
  [ PASSED ] /home/msyksphinz/work/riscv/chipyard/chipyard/sims/verilator/output/example.TestHarness.DefaultRocketConfig/rv64ui-v-subw.out          Completed after 61322 cycles

make run-bmark-testsの方も問題ないようだ。

  [ PASSED ] /home/msyksphinz/work/riscv/chipyard/chipyard/sims/verilator/output/example.TestHarness.DefaultRocketConfig/mm.riscv.out    Completed after 408500 cycles
  [ PASSED ] /home/msyksphinz/work/riscv/chipyard/chipyard/sims/verilator/output/example.TestHarness.DefaultRocketConfig/spmv.riscv.out          Completed after 187129 cycles
  [ PASSED ] /home/msyksphinz/work/riscv/chipyard/chipyard/sims/verilator/output/example.TestHarness.DefaultRocketConfig/mt-vvadd.riscv.out      Completed after 147974 cycles
  [ PASSED ] /home/msyksphinz/work/riscv/chipyard/chipyard/sims/verilator/output/example.TestHarness.DefaultRocketConfig/median.riscv.out        Completed after 29220 cycles
  [ PASSED ] /home/msyksphinz/work/riscv/chipyard/chipyard/sims/verilator/output/example.TestHarness.DefaultRocketConfig/multiply.riscv.out      Completed after 66162 cycles
  [ PASSED ] /home/msyksphinz/work/riscv/chipyard/chipyard/sims/verilator/output/example.TestHarness.DefaultRocketConfig/qsort.riscv.out         Completed after 395238 cycles
  [ PASSED ] /home/msyksphinz/work/riscv/chipyard/chipyard/sims/verilator/output/example.TestHarness.DefaultRocketConfig/towers.riscv.out        Completed after 26010 cycles
  [ PASSED ] /home/msyksphinz/work/riscv/chipyard/chipyard/sims/verilator/output/example.TestHarness.DefaultRocketConfig/vvadd.riscv.out         Completed after 23160 cycles
  [ PASSED ] /home/msyksphinz/work/riscv/chipyard/chipyard/sims/verilator/output/example.TestHarness.DefaultRocketConfig/dhrystone.riscv.out     Completed after 302026 cycles
  [ PASSED ] /home/msyksphinz/work/riscv/chipyard/chipyard/sims/verilator/output/example.TestHarness.DefaultRocketConfig/mt-matmul.riscv.out     Completed after 62320 cycles

「実践Rust入門」に入門している

Rust

少し前から、「実践Rust入門」を読み始めている。Rust自体は前に触ったことがあるのだが、ジェネリクスとかトレイトとか、基本的な知識が不足しているので、評判が良さそうな本を購入して読み進めていくことにした。

実践Rust入門[言語仕様から開発手法まで]

実践Rust入門[言語仕様から開発手法まで]

まずは、クイックツアーということでバイトニックソートの実装を追いかけていくことにした。バイトニックソートを機能を追加しながら順番に実装していくのでわかりやすい。

  1. 単純な整数のみでバイトニックソートを実装
  2. 順序付け可能な型に限定してバイトニックソートを拡張 (浮動小数点などはNaNが入るため対象外)
  3. 一般的な型(Structなど)に拡張してバイトニックソートを拡張(クロージャを活用する)
  4. 並列化ライブラリを使用してマルチコアでバイトニックソートを実装する

という流れになっており、少しずつ進めていくことで私でもなんとか最後のバイトニックソートのベンチマークまで動かすことができた。

本文自体にいくつか間違いがあるようで、サポートページの正誤表は確認する必要がある。私も「あれ、コンパイルできねえなあ。。」と何回か立ち止まってしまった。

gihyo.jp

最後のベンチマークプログラムでは私の環境(4コア8スレッド)で2の28乗の整数をソートして性能差は約2.5倍程度であった。

sorting 268435456 integers (1024.0 MB)
cpu info: 4 physical cores, 8 logical cores
seq_sort: sorted 268435456 integers in 167.6089117 seconds
par_sort: sorted 268435456 integers in 68.1228797 seconds
speed up: 2.46x

PDFにソースコードが載っているのでコピーしようとしたらコピー禁止？が掛かっていたのでひたすら写経していたのだが、GitHubにも上がっていた。

github.com

でもここから先、第4章から第8章まで適当に読んで実践編に入っちゃダメかな... やはり理解できないかな...

中国語版RISC-Vの入門書を買ってみた

f:id:msyksphinz:20191020220152p:plain

RISC-Vの入門書といえば、RISC-V Readerなど基本的に英語のものが日本語に翻訳されるという形式が多いが、中国語版の良さそうなものがあったので無理やり買ってみた。

2冊セットで、結構分厚い。漢字ばっかりで、眩暈がしてくるぞ。。。

とりあえず、スマホの翻訳アプリで目次から眺めている。

  • 1冊目 : 「RISC-V架构与 嵌入式开发快速入门」。日本語で「RISC-Vアーキテクチャと組み込み開発クイックスタート入門」
  • 2冊目 : 「手把手教你设计 RISC-V处理器」。日本語で「RISC-Vプロセッサの設計方法」

目次と中身をざっくりとしか眺めていないが、日本語でもこのレベルでRISC-Vの仕様から実装までまとめた本は存在しないのでは？と思うくらいに内容はしっかりしている。

1冊目の方はRISC-Vの仕様から始まり、SoCの構成と組み込み向けの開発方法、アセンブリの紹介などがメインである。

2冊目の方はRISC-VのCPU設計らしく、Verilogが登場する。HummingBirdという著者の独自の設計に基づいて解説をしているが、これがまたAtomic命令などもちゃんと設計してあり、品質は良さそうである。勉強には良いかもしれない。

あと、紙質は意外と良くない。日本語化したいけど、とりあえず全く読み進められる気がしないので、少しずつ読んでいく。。。

f:id:msyksphinz:20191020232045p:plain

オリジナルLLVMバックエンド実装をまとめる(25. LLVM IRをサポートするためのIntrinsicsのサポート)

LLVM IRには、いくつかの特殊な構文が存在し、これらをサポートすることでより多くのコードを生成できるようになる。 これらについては、clang側からIntrinsic関数を呼び出すことでLLVM IRを生成し、llcに渡してテストすることができる。

f:id:msyksphinz:20191017002523p:plain
frame_addres, return_addressの取得と命令の生成。

FRAMEADDR

関数のフレームポインタを取得する。C言語では、__builtin_frame_address()により取得することができる。

  • func_frame_addr.cpp
void* display_frameaddress() {
  return (void *)__builtin_frame_address(0);
}

上記のプログラムからLLVMの中間表現を作ってみると、以下のようになった。 llvm.frameaddressが使用されている。llvm.frameaddressはスタックフレームのフレームポインタの値を返す。以下のウェブサイトに使用が説明されている。

https://llvm.org/docs/LangRef.html#llvm-frameaddress-intrinsic

./bin/clang ../myriscvx-tests/tests/func_frame_return_addr.cpp -c -emit-llvm -o - | ./bin/llvm-dis -o -

define dso_local i8* @_Z20display_frameaddressv() #0 {
entry:
  %0 = call i8* @llvm.frameaddress(i32 0)
  ret i8* %0
}

このframeaddressは、LLVM IRノードのFRAMEADDRに相当する。このFRAMEADDRを処理するために、MYRISCVXISelLowering.cppに処理を付け加える。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp
//@MYRISCVXTargetLowering {
MYRISCVXTargetLowering::MYRISCVXTargetLowering(const MYRISCVXTargetMachine &TM,
                                               const MYRISCVXSubtarget &STI)
...
  setOperationAction(ISD::FRAMEADDR,     MVT::Other, Custom);
...
}

まず、setOperationAction()にてISD::FRAMEADDRの処理をカスタム関数に投げるように設定する。そして、実際にカスタム関数を作成して命令生成のためのノードを構築する。

SDValue MYRISCVXTargetLowering::
LowerOperation(SDValue Op, SelectionDAG &DAG) const
{
  switch (Op.getOpcode())
  {
...
     case ISD::FRAMEADDR    : return lowerFRAMEADDR(Op, DAG);
...
  }
}
...
SDValue MYRISCVXTargetLowering::
lowerFRAMEADDR(SDValue Op, SelectionDAG &DAG) const {
  // check the depth
  assert((cast<ConstantSDNode>(Op.getOperand(0))->getZExtValue() == 0) &&
         "Frame address can only be determined for current frame.");

  MachineFrameInfo &MFI = DAG.getMachineFunction().getFrameInfo();
  MFI.setFrameAddressIsTaken(true);
  EVT VT = Op.getValueType();
  SDLoc DL(Op);
  SDValue FrameAddr = DAG.getCopyFromReg(
      DAG.getEntryNode(), DL, MYRISCVX::FP, VT);
  return FrameAddr;
}

lowerFRAMEADDRでは、フレームポインタレジスタFPの値を読み取り、getCopyFromReg()でノードを作成し、そのノードを返す。

_Z20display_frameaddressv:              # @_Z20display_frameaddressv
        .cfi_startproc

# %bb.0:                                # %entry
        addi    x10, x8, 0
        ret

フレームポインタレジスタFP(x8)の値を、戻地理レジスタx10にコピーしてから戻る。正しく動作しているようだ。

RETURNADDR

関数の戻りアドレスを取得する。つまり、関数実行中の戻りアドレス、レジスタで言うとraレジスタの中身を戻す。C言語では、__builtin_return_address()により取得することができる。

  • func_return_addr.cpp
extern int fn();

int display_returnaddress() {
  int a = (int)__builtin_return_address(0);
  fn();
  return a;
}

どのようなLLVM中間表現が生成されているか確認してみる。

./bin/clang func_return_addr.cpp -c -emit-llvm --target=riscv32-unknown-elf -o - | ./bin/llvm-dis -o -

define dso_local i32 @_Z21display_returnaddressv() #0 {
entry:
  %a = alloca i32, align 4
  %0 = call i8* @llvm.returnaddress(i32 0)
  %1 = ptrtoint i8* %0 to i32
  store i32 %1, i32* %a, align 4
  %call = call i32 @_Z2fnv()
  %2 = load i32, i32* %a, align 4
  ret i32 %2
}

llvm.returnaddressというノードが生成されており、frameaddress同様、戻りアドレスを示すノードになる。 このノードは、LLVM IRのRETURNADDRに相当する。このノードを処理するための実装を加える。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp
//@MYRISCVXTargetLowering {
MYRISCVXTargetLowering::MYRISCVXTargetLowering(const MYRISCVXTargetMachine &TM,
                                               const MYRISCVXSubtarget &STI)
...
      setOperationAction(ISD::RETURNADDR,    MVT::Other, Custom);
...
}

SDValue MYRISCVXTargetLowering::
LowerOperation(SDValue Op, SelectionDAG &DAG) const
{
  switch (Op.getOpcode())
  {
...
    case ISD::RETURNADDR   : return lowerRETURNADDR(Op, DAG);
  }
}

SDValue MYRISCVXTargetLowering::lowerRETURNADDR(SDValue Op,
                                                SelectionDAG &DAG) const {
  if (verifyReturnAddressArgumentIsConstant(Op, DAG))
    return SDValue();

  // check the depth
  assert((cast<ConstantSDNode>(Op.getOperand(0))->getZExtValue() == 0) &&
         "Return address can be determined only for current frame.");

  MachineFunction &MF = DAG.getMachineFunction();
  MachineFrameInfo &MFI = MF.getFrameInfo();
  MVT VT = Op.getSimpleValueType();
  unsigned RA = MYRISCVX::RA;
  MFI.setReturnAddressIsTaken(true);

  // Return RA, which contains the return address. Mark it an implicit live-in.
  unsigned Reg = MF.addLiveIn(RA, getRegClassFor(VT));
  return DAG.getCopyFromReg(DAG.getEntryNode(), SDLoc(Op), Reg, VT);
}

FRAMEADDR同様、raレジスタをgetCopyFromRegでノードに取り込み、ノードを返すという仕組みになっている。

実際にコンパイルしてみる。

./bin/clang func_return_addr.cpp -c -emit-llvm --target=riscv32-unknown-elf -o func_return_addr.rv32.bc
./bin/llc -mtriple=myriscvx32 -filetype=asm -target-abi=lp func_return_addr.rv32.bc -o 

_Z21display_returnaddressv:             # @_Z21display_returnaddressv
        .cfi_startproc

# %bb.0:                                # %entry
        addi    x2, x2, -16
        .cfi_def_cfa_offset 16
        sw      x2, 12(x2)              # 4-byte Folded Spill
        .cfi_offset 2, -4
        sw      x1, 8(x2)
        addi    x2, x2, 0
        jal     _Z2fnv
        addi    x2, x2, 0
        lw      x10, 8(x2)
        lw      x2, 12(x2)              # 4-byte Folded Reload
        addi    x2, x2, 16
        ret

むだなアセンブリ命令が多くて分かりにくいが、要点は、最初のsw x1, 8(x2)でraレジスタの値をスタックに退避し、lw x10, 8(x2)で戻り値レジスタに書き戻している。これで、現在の戻りアドレスを参照することができる。

オリジナルLLVMバックエンド実装をまとめる(24. 末尾再帰関数呼び出しの実装2.)

f:id:msyksphinz:20191016013631p:plain

前回の続き。末尾再帰の生成について。

LowerCallに戻る。IsTailCallがTrueとなり、末尾関数呼び出し最適化が有効として読み進める。

...
  if (!IsTailCall)
    Chain = DAG.getCALLSEQ_START(Chain, NextStackOffset, 0, DL);
...

末尾関数呼び出し最適化が有効の場合は、新たにスタックフレームを作らないのでCALLSEQ_STARTは生成しない。

  /* 引数渡しのDAG生成部 */
  for (unsigned i = 0, e = ArgLocs.size(); i != e; ++i) {
...
    MemOpChains.push_back(passArgOnStack(StackPtr, VA.getLocMemOffset(),
                                         Chain, Arg, DL, IsTailCall, DAG));
  }

スタック渡しの引数の場合は、少し細工をする。

SDValue
MYRISCVXTargetLowering::passArgOnStack(SDValue StackPtr, unsigned Offset,
                                       SDValue Chain, SDValue Arg, const SDLoc &DL,
                                       bool IsTailCall, SelectionDAG &DAG) const {
  if (!IsTailCall) {
...
  }

  MachineFrameInfo &MFI = DAG.getMachineFunction().getFrameInfo();
  int FI = MFI.CreateFixedObject(Arg.getValueSizeInBits() / 8, Offset, false);
  SDValue FIN = DAG.getFrameIndex(FI, getPointerTy(DAG.getDataLayout()));
  return DAG.getStore(Chain, DL, Arg, FIN, MachinePointerInfo(),
                      /* Alignment = */ 0, MachineMemOperand::MOVolatile);
}

LowerCallに戻る。TailCallノードを挿入する。

  if (IsTailCall)
    return DAG.getNode(MYRISCVXISD::TailCall, DL, MVT::Other, Ops);

上記で使用したMYRISCVXISD::TailCallノードも定義しておく必要がある。これはMYRISCVXInstrInfo.tdで新たなノードとして定義する。 MYRISCVXCallSeqStartやMYRISCVXCallSeqEndのように、TailCallノードもノードとして定義しておく(後で除去するため)。

このMYRISCVXISD::TailCallはMYRISCVXInstrInfo.tdの中でパタンとして変換される。つまり、

  1. LowerCall内でMYRISCVXISD::TailCallノードを生成する。
  2. MYRISCVXISD::TailCallノードはMYRISCVXInstrInfo.tdで定義した生成パタンに基づいて変換される。
  3. 変換されたパタンに基づいて命令が生成される。

という手順になる。では具体的にMYRISCVXInstrInfo.tdでどのような変換ノードを定義すれば良いのか見てみる。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXInstrInfo.td
let isCall = 1, isTerminator = 1, isReturn = 1, isBarrier = 1, hasDelaySlot = 0,
    hasExtraSrcRegAllocReq = 1 in {
  class TailCall<Instruction JumpInst> :
    MYRISCVXPseudo<(outs), (ins brtarget20:$target), "", []>,
    PseudoInstExpansion<(JumpInst ZERO, brtarget20:$target)>;

  class TailCallReg<Instruction JRInst, RegisterClass RC> :
    MYRISCVXPseudo<(outs), (ins RC:$rs), "", [(MYRISCVXTailCall RC:$rs)]>,
    PseudoInstExpansion<(JRInst ZERO, RC:$rs, 0)>;
}

まず、テンプレートとなるTailCallとTailCallRegクラスを定義した。TailCallは最終的にJAL命令(即値ジャンプ命令)、TailCallReg命令は最終的に命令(レジスタ間接ジャンプ命令)に変換されることを狙っている。見てわかる通り、それぞれPseudoInstExpansionにおいてジャンプ元を格納するリンクレジスタにZEROを指定している。これによりTailCallは単なるリンクをしない単なるジャンプ命令となり、リンクレジスタの内容は保持されるため、ジャンプ先でそのまま呼び出し元に戻ることができる、という仕組みだ。

さて、TailCallとTailCallRegを定義した。最終的にはJAL命令もしくはJALRに置き換えられる。

def TAILCALL : TailCall<JAL>;
def TAILCALL_R : TailCallReg<JALR, GPR>;

そして、TAILCALL側にはDAG生成パタンを登録していないので、パタンを登録しておく。 TAILCALL_R側は、TailCallRegの定義ですでに生成パタンMYRISCVXTailCall RC:$rsを登録済みである。

def : Pat<(MYRISCVXTailCall (iPTR tglobaladdr:$dst)), (TAILCALL tglobaladdr:$dst)>;
def : Pat<(MYRISCVXTailCall (iPTR texternalsym:$dst)), (TAILCALL texternalsym:$dst)>;

最後に、アセンブリの生成だ。TAILCALLとTAILCALL_Rは疑似命令なのでそのままではアセンブリ命令を出力することができない。 これを置き換える処理は、tdファイルからすでに生成されている。MYRISCVXGenMCPseudoLowering.incを見てみる。

  • build-myriscvx80/lib/Target/MYRISCVX/MYRISCVXGenMCPseudoLowering.inc
bool MYRISCVXAsmPrinter::
emitPseudoExpansionLowering(MCStreamer &OutStreamer,
                            const MachineInstr *MI) {
  switch (MI->getOpcode()) {
    default: return false;
    case MYRISCVX::TAILCALL: {
      MCInst TmpInst;
      MCOperand MCOp;
      TmpInst.setOpcode(MYRISCVX::JAL);
      // Operand: target
      lowerOperand(MI->getOperand(0), MCOp);
      TmpInst.addOperand(MCOp);
      EmitToStreamer(OutStreamer, TmpInst);
      break;
    }
    case MYRISCVX::TAILCALL_R: {
      MCInst TmpInst;
      MCOperand MCOp;
      TmpInst.setOpcode(MYRISCVX::JALR);
      // Operand: rs1
      lowerOperand(MI->getOperand(0), MCOp);
      TmpInst.addOperand(MCOp);
      EmitToStreamer(OutStreamer, TmpInst);
      break;
    }
  }
  return true;
}

TAILCALLではJAL命令に置き換え、TAILCALL_RノードではJALR命令に置き換えるシーケンスが生成されていることが分かる。 なぜこれが生成されたかというと、これらのノードにはPseudoInstExpansionが追加されており、自動的に展開することができるようになっていたからだ。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXAsmPrinter.cpp
//- EmitInstruction() must exists or will have run time error.
void MYRISCVXAsmPrinter::EmitInstruction(const MachineInstr *MI) {
...
  do {
    // Do any auto-generated pseudo lowerings.
    if (emitPseudoExpansionLowering(*OutStreamer, &*I))
      continue;
...

ここまでで、末尾関数呼び出し最適化を適用した場合とそうでない場合についてアセンブリ命令を生成してみる。

# 末尾関数呼び出し最適化を適用した場合
./bin/llc -stats -debug -target-abi=lp64 -march=myriscvx32 -mcpu=simple32 -enable-MYRISCVX-tail-calls=true -relocation-model=static -filetype=asm result/tailcall_-O1_-march=myriscvx32_-mcpu=simple32_static_lp64_-enable-MYRISCVX-tail-calls=true/tailcall.bc -o -
# 末尾関数呼び出し最適化を適用しない場合
./bin/llc -stats -debug -target-abi=lp64 -march=myriscvx32 -mcpu=simple32 -enable-MYRISCVX-tail-calls=false -relocation-model=static -filetype=asm result/tailcall_-O1_-march=myriscvx32_-mcpu=simple32_static_lp64_-enable-MYRISCVX-tail-calls=false/tailcall.bc -o -

- 末尾関数呼び出し最適化を適用した場合の生成されたアセンブリ命令

​```asm
// 関数呼び出され側 (Callee)
_Z14tail_call_funcii:
...
# %bb.0:                                # %entry
    add x10, x11, x10
    ret x1

// 関数呼び出し側 (Caller)
_Z14tail_call_mainiiii:
...
# %bb.0:                                # %entry
    sub x10, x10, x11
    mul x11, x13, x12
    jal _Z14tail_call_funcii
...
  • 末尾関数呼び出し最適化を適用しない場合の生成されたアセンブリ命令
// 関数呼び出され側 (Callee)
_Z14tail_call_funcii:
...
# %bb.0:                                # %entry
    add x10, x11, x10
    ret x1

_Z14tail_call_mainiiii:
...
# %bb.0:                                # %entry
    addi    x2, x2, -8
    .cfi_def_cfa_offset 8
    sw  x2, 4(x2)               # 4-byte Folded Spill
    .cfi_offset 2, -4
    sub x10, x10, x11
    mul x11, x13, x12
    jal _Z14tail_call_funcii
    lw  x2, 4(x2)               # 4-byte Folded Reload
    addi    x2, x2, 8
    ret x1

末尾関数呼び出し最適化を適用しない場合場合は、_Z14tail_call_funcii呼び出し前にスタックの調整が行われていることが確認できる。一方で、末尾関数呼び出し最適化を適用した場合はスタックの調整コードが省略されている。これにより、関数呼び出しの場合のスタックフレームの消費を抑え、動作を高速化することができる。

オリジナルLLVMバックエンド実装をまとめる(23. 末尾再帰関数呼び出しの実装1.)

関数呼び出しには様々な最適化の形があるが、その中の一つである末尾関数呼び出しでの最適化を実行してみる。 末尾関数呼び出しとは、ある関数f1()が関数f2()の最後の処理として呼び出されるケースを言う。

int f1(a, b) { a + b; }
int f2(c, d, e, f) {
    /* 様々な処理*/
    return f1(10, 20);
}

この場合、関数f1()を呼び出すためには引数渡しの処理、スタックの処理、そして呼び出しから戻ってきた場合には戻り値の処理やスタックの後片付けを行う必要がある。

f:id:msyksphinz:20191016013535p:plain
通常のスタックフレームの作成手順。関数が呼び出されると新たなスタックフレームが作成される。

しかし、場合によってはこれが不要なことがある。つまり、どっちにしろf1から戻った後はf2からも戻ってしまうのだから、せっかくなのでf2のスタック領域などもf1で使わせてもらって、関数呼び出し時のスタックの掘り下げを省略してしまう。つまり、末尾呼び出しではスタックフレームを追加することなくf1を呼び出すことができる。

f:id:msyksphinz:20191016013631p:plain
Tail Callのスタックフレームの作成手順。スタックフレームは新たに作成されず、引数の調整だけを行って関数に飛ぶ。

しかし、この末尾呼び出しはすべての条件下で実現可能なわけではない。 上記で説明した通り、f2のスタックフレームを使用してf1が実行される。 つまり、f1が使う予定であるスタックフレームのサイズがf2のスタックフレームのサイズを超えていてはならない。 また、f1のスタックフレームのサイズが最初から算出できない場合にも末尾関数呼び出し最適化は適用できない。 f1のスタックフレーム以外の場所まで破壊してしまう可能性があるからだ。

では、実際にLLVMで末尾関数呼び出しの最適化を実行してみる。clangでは-O1オプションを付加することで末尾関数呼び出し最適化を施したIRを生成することができる。以下のプログラムをclangでIRを生成してみる。

int tail_call_func(int a, int b) {
    return a + b;
}
int tail_call_main (int a, int b, int c, int d) {
    int e = a + b;
    int f = c + d;
    return tail_call_func(e, f);  /* 末尾関数呼び出し */
}

./bin/clang -O1 --target=riscv32-unknown-elf tailcall.cpp -c -emit-llvm -o tailcall.o1.bc
./bin/clang -O0 --target=riscv32-unknown-elf tailcall.cpp -c -emit-llvm -o tailcall.o0.bc

生成されたバイナリをダンプしてみると、tailcall.o1の方ではf1の呼び出しの部分がtail callとなっていることが分かる。

./bin/llvm-dis tailcall.o1.bc -o -

  %sub = sub nsw i32 %a, %b
  %mul = mul nsw i32 %d, %c
  /* Tail Call が使用されている */
  %call = tail call i32 @_Z14tail_call_funcii(i32 signext %sub, i32 signext %mul)
  ret i32 %call
./bin/llvm-dis tailcall.o0.bc -o -

  /* -O0なので最適化が施されていない */
  store i32 %sub, i32* %e, align 4
...
  %mul = mul nsw i32 %2, %3
...
  /* 普通のCallが使用されている */
  %call = call i32 @_Z14tail_call_funcii(i32 signext %4, i32 signext %5)
  ret i32 %call

では、このIRを処理して末尾関数呼び出し最適化を適用してみる。実装しなければならないのは、

  • 末尾関数呼び出し最適化が適用可能かチェックする
  • スタックフレームの生成を実行しないように制御
  • 引数渡しの処理を行う
  • 関数ジャンプ
  • 戻り値処理

と、とりあえずは関数呼び出しのシーケンスの部分に手を加えれば良さそうだ。 これらはすべてIRからDAGへの変換時に適用できるので、MYRISCVXISelLowering.cppに記述されているMYRISCVXTargetloweringクラスに手を加える。 関数呼び出しの部分なので、MYRISCVXTargetLowering:::LowerCallを改造すれば良さそうだ。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp
SDValue
MYRISCVXTargetLowering::LowerCall(TargetLowering::CallLoweringInfo &CLI,
                                  SmallVectorImpl<SDValue> &InVals) const {
...
  bool &IsTailCall                      = CLI.IsTailCall;
...
  // Get a count of how many bytes are to be pushed on the stack.
  unsigned NextStackOffset = CCInfo.getNextStackOffset();

  // Check if it's really possible to do a tail call.
  if (IsTailCall)
    IsTailCall = isEligibleForTailCallOptimization(CCInfo, NextStackOffset,
                                                   *MF.getInfo<MYRISCVXFunctionInfo>());
...

IsTailCall変数は関数呼び出しが末尾関数呼び出しになっている場合にまずはTrueとなる。 次に、本当に末尾関数呼び出し最適化が適用可能かチェックする。 これを行っているのがisEligibleForTailCallOptimizationである。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXSEISelLowering.cpp
/// isEligibleForTailCallOptimization - Check whether the call is eligible
/// for tail call optimization.
/// Note: This is modelled after ARM's IsEligibleForTailCallOptimization.
bool MYRISCVXTargetLowering::
isEligibleForTailCallOptimization(
    CCState &CCInfo,
    unsigned NextStackOffset, const MYRISCVXFunctionInfo& FI) const {

  // Return false if either the callee or caller has a byval argument.
  if (CCInfo.getInRegsParamsCount() > 0 || FI.hasByvalArg())
    return false;

  // Return true if the callee's argument area is no larger than the
  // caller's.
  return NextStackOffset <= FI.getIncomingArgSize();
}

末尾関数呼び出し最適化が適用できる条件としては、

  • 呼び出し先もしくは呼び出し元がbyvalの引数を持っている場合はダメ。
  • 呼び出し先が使用する予定のスタックサイズ(NextStackOffset)よりも呼び出し元が持っているスタックのサイズFI.getIncomingArgSize()が大きい場合はダメ。

上記をすべてクリアできれば末尾関数呼び出し最適化が適用できる。

オリジナルLLVMバックエンド実装をまとめる(22. 可変長引数をサポートするための処理)

C言語の可変長引数では、例えば以下のような記述が可能となる。

  • vararg.cpp
#include <stdarg.h>

int sum_i(int amount, ...)
{
  int i = 0;
  int val = 0;
  int sum = 0;
    
  va_list vl;
  va_start(vl, amount);
  for (i = 0; i < amount; i++)
  {
    val = va_arg(vl, int);
    sum += val;
  }
  va_end(vl);
  
  return sum; 
}

int test_vararg()
{
  int a = sum_i(10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
  return a;
}

C言語の文法としては少し特殊な形をしているかもしれないが、フロントエンドによって一度IRの形式になってしまえば、あとはレジスタを割り当てて命令を生成するだけなのでそこまで難しくはない。 ただし、この可変長引数をサポートするためには、DAGによってさらに別の種類のノードをサポートする必要がある。

しかし、可変長引数でも基本的な考え方は変わらない。 関数を呼び出す側は、可能な数だけレジスタに引数を渡し、レジスタに入りきらなければスタックに積み上げていく。 呼び出された関数の処理が、これまでと異なる。 つまり、効率的に可変長引数を扱うために、レジスタ経由で受け付けた引数をいったんスタックにすべて退避していく処理が追加される。 これにより、実際の引数を処理するプログラムを効率的に扱うことができるようになる。

f:id:msyksphinz:20191013114926p:plain
可変長引数での引数の受け渡し方。関数呼び出し側は変更ないが、呼び出され側はスタックへの退避処理が追加される。
  1. 可変長引数に関係するノードの生成条件を変更する。VASTARTのみを取り扱うように変更する。
  2. VASTARTに基づいてDAGを生成するためのMYRISCVXTarget::selectVASTART()を実装する。これにより可変長引数の情報がメモリに渡されるDAGが生成される。
  3. MYRISCVXTargetLowering::LowerFormalArguments()内にwriteVarArgRegs()の呼び出しを追加し、可変長引数を受け取るとその値をスタックに積み上げる操作を追加する。

まずは、可変長引数のC言語プログラムから生成されたLLVM IRを見てみる。

./bin/clang vararg.cpp -emit-llvm -o vararg.rv32.bc --target=riscv32-unknown-elf
./bin/llvm-dis vararg.rv32.bc -o -

define dso_local i32 @_Z11test_varargv() #0 {
entry:
...
   %call = call i32 (i32, ...) @_Z5sum_iiz(i32 10, i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7, i32 8, i32 9)
...
define dso_local i32 @_Z5sum_iiz(i32 %amount, ...) #0 {
entry:
...
  %arraydecay = getelementptr inbounds [1 x %struct.__va_list_tag], [1 x %struct.__va_list_tag]* %vl, i32 0, i32 0
  %arraydecay1 = bitcast %struct.__va_list_tag* %arraydecay to i8*
  // va_start()を呼ぶ
  call void @llvm.va_start(i8* %arraydecay1)
...
vaarg.in_reg:                                     ; preds = %for.body
...
for.end:                                          ; preds = %for.cond
  // va_end()を呼ぶ
  call void @llvm.va_end(i8* %arraydecay34)
    ret i32 %11
}

in_regの場合と、in_memの場合が挙げられている。 for.bodyから進んでいき、%gp_offsetが40よりも小さい場合、in_regに飛んでいき、そうでない場合はin_memに飛んでいくようです。

このコードの意図をはっきりと説明した文章は見つけられなかったが、考えられるのは、Callee側が受け入れることのできる引数が可変長だと、コンパイル時にCalleeが使用するスタックの量をあらかじめ算出することができない、こうすると面倒なので、40バイトまでの可変引数までならスタック経由で渡せるようにする、それ以降はグローバル領域を確保して受け渡す、というようにしていると思われる。

可変長引数を取り扱う関数の処理

SelectionDAGの生成

VAARG, VACOPY, VAENDの3つは最適化の最中に生成されないように抑制する。 つまり、MYRISCVXTargetLoweringにて、setOperationInAction()で対象となるノードの生成を抑制する。

  • llvm-myriscvx80/lib/Target/MYRISCVX/MYRISCVXISelLowering.cpp
MYRISCVXTargetLowering::MYRISCVXTargetLowering(const MYRISCVXTargetMachine &TM,
                                               const MYRISCVXSubtarget &STI)
...
  // For Var Arguments
  setOperationAction(ISD::VASTART,   MVT::Other, Custom);

  // Support va_arg(): variable numbers (not fixed numbers) of arguments
  //  (parameters) for function all
  setOperationAction(ISD::VAARG,        MVT::Other, Expand);
  setOperationAction(ISD::VACOPY,       MVT::Other, Expand);
  setOperationAction(ISD::VAEND,        MVT::Other, Expand);
...
  • VASTART : 可変長引数の処理を開始する。
  • VAARG : 可変長引数から実際の値を取り出する。
  • VACOPY
  • VAEND : 可変長引数の処理を終了する。

VASTARTだけはカスタム実装に設定したので、lowerVASTART()のみ実装する。

SDValue MYRISCVXTargetLowering::
LowerOperation(SDValue Op, SelectionDAG &DAG) const
{
  switch (Op.getOpcode())
  {
    case ISD::SELECT        : return lowerSELECT(Op, DAG);
    case ISD::GlobalAddress : return lowerGlobalAddress(Op, DAG);
    case ISD::VASTART       : return lowerVASTART(Op, DAG);
  }
  return SDValue();
}

lowerVASTARTでは、可変長引数のアドレスをメモリにストアする。

SDValue MYRISCVXTargetLowering::lowerVASTART(SDValue Op, SelectionDAG &DAG) const {
  MachineFunction &MF = DAG.getMachineFunction();
  MYRISCVXFunctionInfo *FuncInfo = MF.getInfo<MYRISCVXFunctionInfo>();

  SDLoc DL = SDLoc(Op);
  SDValue FI = DAG.getFrameIndex(FuncInfo->getVarArgsFrameIndex(),
                                 getPointerTy(MF.getDataLayout()));

  // vastart just stores the address of the VarArgsFrameIndex slot into the
  // memory location argument.
  const Value *SV = cast<SrcValueSDNode>(Op.getOperand(2))->getValue();
  return DAG.getStore(Op.getOperand(0), DL, FI, Op.getOperand(1),
                      MachinePointerInfo(SV));
}

LowerFormalArguments()つまり可変長引数を持つ関数が呼び出されたときの引数の処理について、可変長引数であれば専用のルーチンを呼び出する。writeVarArgRegsを呼び出する。

SDValue
MYRISCVXTargetLowering::LowerFormalArguments (SDValue Chain,
                                              CallingConv::ID CallConv,
                                              bool IsVarArg,
                                              const SmallVectorImpl<ISD::InputArg> &Ins,
                                              const SDLoc &DL, SelectionDAG &DAG,
                                              SmallVectorImpl<SDValue> &InVals) const {
...
  // 可変長引数を処理する場合は、特殊なwriteVarArgRegsに飛ぶ。
  if (IsVarArg)
    writeVarArgRegs(OutChains, Chain, DL, DAG, CCInfo);

  return Chain;
}

このwriteVarArgRegsは、ABIがLP32の時にレジスタ渡しをしたデータをスタックに戻す。 せっかくレジスタ渡しをしたのにどうしてスタックに戻すんだ？と思われるかもしれないが、それ以降の処理は一律してfor文の処理で統一するため、レジスタ渡し、メモリロードの2種類でアセンブリを生成したくない、という意図があると思われる。

  /* for文の前に、レジスタ渡しした可変長引数の要素をスタックに置いておく。 */
  for (i = 0; i < amount; i++)
  {
    /* valの取得はスタックから一律に受け取る */
    val = va_arg(vl, int);
    sum += val;
  }

void MYRISCVXTargetLowering::writeVarArgRegs(std::vector<SDValue> &OutChains,
                                             SDValue Chain, const SDLoc &DL,
                                             SelectionDAG &DAG,
                                             CCState &State) const {
  ArrayRef<MCPhysReg> ArgRegs = ABI.GetVarArgRegs();
  unsigned Idx = State.getFirstUnallocated(ArgRegs);
  unsigned RegSizeInBytes = Subtarget.getGPRSizeInBytes();
  MVT RegTy = MVT::getIntegerVT(RegSizeInBytes * 8);

  ...
  /* 引数渡しに使用しているレジスタを1つ1つ退避していく */
  for (unsigned I = Idx; I < ArgRegs.size();
       ++I, VaArgOffset += RegSizeInBytes) {

    unsigned Reg = addLiveIn(MF, ArgRegs[I], RC);
    SDValue ArgValue = DAG.getCopyFromReg(Chain, DL, Reg, RegTy);
    FI = MFI.CreateFixedObject(RegSizeInBytes, VaArgOffset, true);
    SDValue PtrOff = DAG.getFrameIndex(FI, getPointerTy(DAG.getDataLayout()));
    /* Store命令を生成 */
    SDValue Store =
        DAG.getStore(Chain, DL, ArgValue, PtrOff, MachinePointerInfo());
    cast<StoreSDNode>(Store.getNode())->getMemOperand()->setValue(
        (Value *)nullptr);
    OutChains.push_back(Store);
  }
}

可変長引数の関数を呼び出す側の処理

次に、可変長引数の関数を呼び出す側の処理が、これは追加の実装は必要ない。

これまで通り引数をレジスタに渡し、レジスタに収まりきらなければスタックに積んでいけば良い。

上記のコードをコンパイルして、どのようなコードが生成されているのか見てみる。

./bin/clang -O0 -c vararg.cpp -emit-llvm -o vararg.bc
# ABI=LP64でコンパイルした場合
./bin/llc -stats -debug -target-abi=lp -march=myriscvx32 -filetype=asm vararg.bc -o -
# ABI=STACK32でコンパイルした場合
./bin/llc -stats -debug -target-abi=stack -march=myriscvx32 -filetype=asm vararg.bc -o -
  • 可変長引数を渡す側
    • ABI=LP64の場合
        addi    x10, zero, 7    # レジスタ経由で入りきらない引数はスタックを経由する。第8引数
        sw      x10, 0(x2)
        addi    x10, x2, 8
        addi    x11, zero, 9    # レジスタ経由で入りきらない引数はスタックを経由する。第10引数
        sw      x11, 0(x10)
        addi    x10, x2, 4
        addi    x11, zero, 8    # レジスタ経由で入りきらない引数はスタックを経由する。第9引数
        sw      x11, 0(x10)
        addi    x10, zero, 10   # 引数の数 : amount
        addi    x11, zero, 0    # 第1引数
        addi    x12, zero, 1    # 第2引数 ...
        addi    x13, zero, 2
        addi    x14, zero, 3
        addi    x15, zero, 4
        addi    x16, zero, 5
        addi    x17, zero, 6    # レジスタ経由はこれが限界
        jal     _Z5sum_iiz

レジスタ渡しできる限りはレジスタ経由で渡す。A0-A7までのレジスタを使って引数を渡し、それでも足りないので残りはスタック経由で渡している。

  • 可変長引数を受け取る側
    • ABI=LP64の場合
_Z5sum_iiz:
        .cfi_startproc
...
# %bb.0:                                # %entry
        addi    x2, x2, -64
        .cfi_def_cfa_offset 64
        sw      x17, 60(x2)     # 可変引数8をスタックに格納
        sw      x16, 56(x2)     # 可変引数7をスタックに格納
        sw      x15, 52(x2)     # ....
        sw      x14, 48(x2)
        sw      x13, 44(x2)
        sw      x12, 40(x2)
        sw      x11, 36(x2)     # 可変引数1をスタックに格納
        sw      x10, 32(x2)     # 引数amountをスタックに格納
        addi    x10, zero, 0

まず、レジスタ経由で渡した引数をすべてスタックに格納する。もったいないが、こうすることで以降の処理コードをより簡潔にする。