FPGA開発日記

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

LLVMのバックエンドを作るための第一歩 (43. インラインアセンブリをサポートする)

LLVM

llcにアセンブラをサポートする。具体的には、インラインアセンブリなどのC言語の内部にアセンブラを埋め込む処理をサポートする。これまで、さんざんアセンブリ言語のサポートを追加してきたじゃないか、と思うかもしれないが、インラインアセンブリでのアセンブリ記述をサポートするためには、さらにllcに改造を加える必要がある。

まずは、何も改造せずにCのソースコード内にアセンブリ命令を挿入するとどうなるのだろう。

  • assembly_code.cpp
void assembly_code_test ()
{
  asm("sub   x3, x2, x3");
  asm("mul   x2, x1, x3");

  asm("lw    x2, 8(x2)");
  asm("sw    zero, 4(x2)");
  asm("addi  x3, zero, 500");

  // asm("add   a0, a1, a2");

  asm("srai  x2, x2, 2");
  asm("slli  x2, x2, 2");
  asm("srli  x2, x3, 5");

  asm("jr    x6");

  asm("li    x3, 0x00700000");
  asm("la    x3, 0x00900000");
  //  asm("test_label: la    x3, test_label");
}

./bin/llc -debug -filetype=asm assembly_code.bc -mcpu=simple32 -march=myriscvx32  # アセンブリファイルを直接出力
  • 生成されたassembly_code.s (一部grepにより余分なコメントをフィルタしている)
# %bb.0:                                # %entry
        sub   x3, x2, x3
        mul   x2, x1, x3
        lw    x2, 8(x2)
        sw    zero, 4(x2)
        addi  x3, zero, 500
        srai  x2, x2, 2
        slli  x2, x2, 2
        srli  x2, x3, 5
        jr    x6
        li    x3, 0x00700000
        la    x3, 0x00900000
        test_label: la    x3, test_label
        ret     x1
...
./bin/llc -debug -filetype=obj assembly_code.bc -mcpu=simple32 -march=myriscvx32  # オブジェクトファイル
...
********** COMPUTING STACKMAP LIVENESS: _Z18assembly_code_testv **********
LLVM ERROR: Inline asm not supported by this streamer because we don't have an asm parser for this target

LLVM IRをアセンブリに直接変換することはできるが、ハンドコードしたアセンブリ命令をオブジェクトファイルに直接変換することはできないのだ。

これはなぜかというと、アセンブリ命令はAsmParserという機能が司っているからだ。 アセンブリ命令を読み取ると、AsmParserがParseInstruction()という関数を呼び、これがどの命令であるのかをチェックする。そして、このアセンブリ命令を読み取ったうえで、LLVM IRを作成し、それを返すというわけだ。

そのあとでMatchAndEmitInstruction()を呼び出して生成したLLVM IRをMCInstに変換する。面倒くさい。どうせなら一気通貫で何も考えずにやってくれればよいのに。

なぜこのような構成になっているかというと、アセンブリを直接埋め込む場合、様々な疑似命令を使用することができるからだ。アセンブリを直接使う場合にもよく使うような機能だ。

li  x3, 0x01   // Load Immediate. 実際にはluiとaddiで構成される疑似命令。
la  x3, 0xff   // Load Address. 実際にはluiとaddiで構成される疑似命令。

上記のような疑似命令は、LLVM IRに直接ベタ書きで記述され、その後llcのアセンブリにより解釈を変え、そしてMCInstの変換する必要がある。これらの機能はアーキテクチャ依存だので、自分で実装する必要がある訳だ。

しかしそうは言っても、LLVMはある程度アセンブリ命令にマッチするための関数を出力してくれます。この自動生成されたヘッダファイルを使用して、アセンブリ言語のサポートを少しでも簡単に実装していく。

具体的にどのような機能を自動生成してくれるかというと、

  • 命令定義から、想定されるParserツリーを生成する
    • Parseのコードはある程度自作する必要があるが、Parse結果、どのような命令と合致するかについてはある程度テンプレートを用いてチェックすることができる。
  • レジスタ名のマッチ。
    • 文字列を与えると、該当するレジスタを検索して返してくれます。
f:id:msyksphinz:20190723231858p:plain

(https://jonathan2251.github.io/lbd/asm.html より抜粋)

まず、上記のサンプルプログラムに対して、clangにより生成されたllを見てみる。

./bin/clang assembly_code.c --emit-llvm
./bin/llvm-disasm assembly_code.bc

define dso_local void @_Z18assembly_code_testv() local_unnamed_addr #0 {
entry:
  tail call void asm sideeffect "sub   x3, x2, x3", "~{dirflag},~{fpsr},~{flags}"() #1, !srcloc !2
  tail call void asm sideeffect "mul   x2, x1, x3", "~{dirflag},~{fpsr},~{flags}"() #1, !srcloc !3
  tail call void asm sideeffect "lw    x2, 8(x2)", "~{dirflag},~{fpsr},~{flags}"() #1, !srcloc !4
  tail call void asm sideeffect "sw    zero, 4(x2)", "~{dirflag},~{fpsr},~{flags}"() #1, !srcloc !5
  tail call void asm sideeffect "addi  x3, zero, 500", "~{dirflag},~{fpsr},~{flags}"() #1, !srcloc !6
  tail call void asm sideeffect "srai  x2, x2, 2", "~{dirflag},~{fpsr},~{flags}"() #1, !srcloc !7
  tail call void asm sideeffect "slli  x2, x2, 2", "~{dirflag},~{fpsr},~{flags}"() #1, !srcloc !8
  tail call void asm sideeffect "srli  x2, x3, 5", "~{dirflag},~{fpsr},~{flags}"() #1, !srcloc !9
  tail call void asm sideeffect "jr    x6", "~{dirflag},~{fpsr},~{flags}"() #1, !srcloc !10
  tail call void asm sideeffect "li    x3, 0x00700000", "~{dirflag},~{fpsr},~{flags}"() #1, !srcloc !11
  tail call void asm sideeffect "la    x3, 0x00900000", "~{dirflag},~{fpsr},~{flags}"() #1, !srcloc !12
  tail call void asm sideeffect "test_label: la    x3, test_label", "~{dirflag},~{fpsr},~{flags}"() #1, !srcloc !13
  ret void
}

そのままアセンブリが埋め込まれている。つまり、これをParseして、MCInstを作り上げなければならないのだ。

では、AsmParserディレクトリを作成し、そこに実装を追加していく。

AsmParser
├── CMakeLists.txt
├── LLVMBuild.txt
└── MYRISCVXAsmParser.cpp
  • llvm-myriscvx/lib/Target/MYRISCVX/AsmParser/CMakeLists.txt
add_llvm_library(LLVMMYRISCVXAsmParser
  MYRISCVXAsmParser.cpp
  )

まず、ParseInstruction()について見て行く。 ParseInstruction()はAsmParserにより呼び出され、埋め込まれたインラインアセンブリを解析するために呼び出される。ここから先は、アセンブリ命令を人力でParseする必要がある。

作り上げていくのはParseInstruction()内のOperandVector &Operandsだ。ここにインラインアセンブリをParseした結果として、

を追加していく。

bool MYRISCVXAsmParser::
ParseInstruction(ParseInstructionInfo &Info, StringRef Name, SMLoc NameLoc,
                 OperandVector &Operands) {

  // Create the leading tokens for the mnemonic, split by '.' characters.
  size_t Start = 0, Next = Name.find('.');
  StringRef Mnemonic = Name.slice(Start, Next);


  // Read the remaining operands.
  if (getLexer().isNot(AsmToken::EndOfStatement)) {
    // Read the first operand.
    if (ParseOperand(Operands, Name)) {
      SMLoc Loc = getLexer().getLoc();
      Parser.eatToEndOfStatement();
      return Error(Loc, "unexpected token in argument list");
    }

    while (getLexer().is(AsmToken::Comma) ) {
      Parser.Lex();  // Eat the comma.

      // Parse and remember the operand.
      if (ParseOperand(Operands, Name)) {
        SMLoc Loc = getLexer().getLoc();
        Parser.eatToEndOfStatement();
        return Error(Loc, "unexpected token in argument list");
      }
    }
  }

  if (getLexer().isNot(AsmToken::EndOfStatement)) {
    SMLoc Loc = getLexer().getLoc();
    Parser.eatToEndOfStatement();
    return Error(Loc, "unexpected token in argument list");
  }

  Parser.Lex(); // Consume the EndOfStatement
  return false;
}

オペコードとオペランドを分離する処理から始まる。先頭のオペランドをOperands.push_back(MYRISCVXOperand::CreateToken(Mnemonic, NameLoc));でpushし、そこからコンマで区切りながらオペランドをデコードする。ParseOperand(Operands, Name)で、それぞれのオペランドをデコードする。

bool MYRISCVXAsmParser::ParseOperand(OperandVector &Operands,
                                     StringRef Mnemonic) {
...
  // Attempt to parse token as a register.
  if (parseRegister(Operands, true) == MatchOperand_Success)
    return false;

  // Attempt to parse token as an immediate
  if (parseImmediate(Operands) == MatchOperand_Success) {
    // Parse memory base register if present
    if (getLexer().is(AsmToken::LParen))
      return parseMemOperand(Operands) != MatchOperand_Success;
    return false;
  }

  LLVM_DEBUG(dbgs() << "unknown operand\n");
  return true;
}

オペランドのデコードに関しては ParseOperand()を使用する。

  • parseRegister() : レジスタのデコードを試行する。デコードに成功すれば戻る。

  • parseImmediate() : 即値をデコードを試行する。成功し、かつ"("が続いている場合は、メモリオペランドとしてのデコードparseMemOperand()を試行する。これは、即値だけでなく、lw x1, 100(x2)のような"即値 + (汎用レジスタ)"という構文があるためだ。

parseRegister()を見てみる。

OperandMatchResultTy MYRISCVXAsmParser::parseRegister(OperandVector &Operands)
{
  switch (getLexer().getKind()) {
    default:
      return MatchOperand_NoMatch;
    case AsmToken::Identifier:
      StringRef Name = getLexer().getTok().getIdentifier();
      unsigned RegNo = MatchRegisterName(Name);
      if (RegNo == 0) {
        RegNum = MatchRegisterAltName(Name);
        if (RegNo == -1) {
          return MatchOperand_NoMatch;
        }
      }
      SMLoc S = getLoc();
      SMLoc E = SMLoc::getFromPointer(S.getPointer() - 1);
      getLexer().Lex();
      Operands.push_back(MYRISCVXOperand::createReg(RegNo, S, E));
  }

  return MatchOperand_Success;
}

MatchRegisterName()を呼び出している。これはtblgenで生成された関数で、MYRISCVXGenAsmMatcher.incに生成されている。文字通り、文字列として与えられたレジスタ名がどのレジスタにマッチするかを判定する処理だ。

判定に成功すると、Operandsベクタにレジスタオペランドを追加するOperands.push_back(MYRISCVXOperand::createReg(RegNo, S, E))処理を行いる。

  • build-myriscvx/lib/Target/MYRISCVX/MYRISCVXGenAsmMatcher.inc
static unsigned MatchRegisterName(StringRef Name) {
  switch (Name.size()) {
  default: break;
  case 2:     // 9 strings to match.
    if (Name[0] != 'x')
      break;
    switch (Name[1]) {
    default: break;
...
  case 4:     // 1 string to match.
    if (memcmp(Name.data()+0, "zero", 4) != 0)
      break;
    return 6;     // "zero"
  }
  return 0;
}

レジスタのマッチに成功すると0以外が返され、どのレジスタともマッチしなければ0が返される。

MatchRegisterNameに失敗すると、今度はABI名でのレジスタ名の検索にトライする。これはMatchRegisterAltName()という関数を作って試行する。

int MYRISCVXAsmParser::MatchRegisterAltName(StringRef Name) {

  int CC;
  CC = StringSwitch<unsigned>(Name)
      .Case("zero",  MYRISCVX::ZERO)
      .Case("ra",  MYRISCVX::RA)
      .Case("sp",  MYRISCVX::SP)
      .Case("gp",  MYRISCVX::GP)
      .Case("tp",  MYRISCVX::TP)
      .Case("t0",  MYRISCVX::T0)
...
      .Default(-1);

  if (CC != -1)
    return CC;

  return -1;
}

これでもマッチしない場合はレジスタではない。エラーを返す。

parseImmediate()を見てみる。

OperandMatchResultTy MYRISCVXAsmParser::parseImmediate(OperandVector &Operands) {
  SMLoc S = getLoc();
  SMLoc E = SMLoc::getFromPointer(S.getPointer() - 1);
  const MCExpr *Res;

  switch (getLexer().getKind()) {
  default:
    return MatchOperand_NoMatch;
  case AsmToken::LParen:
  case AsmToken::Minus:
  case AsmToken::Plus:
  case AsmToken::Integer:
  case AsmToken::String:
  case AsmToken::Identifier:
    if (getParser().parseExpression(Res))
      return MatchOperand_ParseFail;
    break;
  // case AsmToken::Percent:
  //   return parseOperandWithModifier(Operands);
  }

  Operands.push_back(MYRISCVXOperand::createImm(Res, S, E));
  return MatchOperand_Success;
}

これは即値のParseを行っている。即値は「かっこ、マイナス符号、プラス符号、整数、文字列、など」から構成され、これをgetParser().parseExpression(Res)でParseする。Parseに成功すると即値として認識するが、失敗すると即値とは判定されない。

成功すると、Operandsベクトルに対して即値オブジェクトを追加する(Operands.push_back(MYRISCVXOperand::createImm(Res, S, E)))。

次はparseMemOperand()だ。先ほどの実装では、即値をparseImmediate()で即値はParseしたので、左かっこ、レジスタ、右かっこという並びでParseできることが想定だ。100(x1)のような形が作れれば成功だ。

OperandMatchResultTy MYRISCVXAsmParser::parseMemOperand(OperandVector &Operands) {

  const MCExpr *IdVal = 0;
  SMLoc S;
  // first operand is the offset
  S = Parser.getTok().getLoc();

  if (parseMemOffset(IdVal))
    return MatchOperand_ParseFail;

  const AsmToken &Tok = Parser.getTok(); // get next token
  if (Tok.isNot(AsmToken::LParen)) {
    Error(Parser.getTok().getLoc(), "'(' expected");
    return MatchOperand_ParseFail;
  }

  Parser.Lex(); // Eat '(' token.
  Operands.push_back(MYRISCVXOperand::CreateToken("(", getLoc()));

  const AsmToken &Tok1 = Parser.getTok(); // get next token
  if (tryParseRegisterOperand(Operands,"")) {
    Error(Parser.getTok().getLoc(), "unexpected token in operand");
  }

  const AsmToken &Tok2 = Parser.getTok(); // get next token
  if (Tok2.isNot(AsmToken::RParen)) {
    Error(Parser.getTok().getLoc(), "')' expected");
    return MatchOperand_ParseFail;
  }

  SMLoc E = SMLoc::getFromPointer(Parser.getTok().getLoc().getPointer() - 1);

  Parser.Lex(); // Eat ')' token.
  Operands.push_back(MYRISCVXOperand::CreateToken(")", getLoc()));

  if (!IdVal)
    IdVal = MCConstantExpr::create(0, getContext());

  return MatchOperand_Success;
}

先頭文字が左かっこでなければまず失敗だ。(if (Tok.isNot(AsmToken::LParen))。tryParseRegisterOperandレジスタオペランドのParseを行いる。最後に右かっこが登場すれば全体のParseが完了となる(if (Tok2.isNot(AsmToken::RParen)))。

このようにして、すべてオペランドを探索し、最終的にアセンブリ言語の最後まで行けばParse完了だ。

f:id:msyksphinz:20190723231953p:plain
インラインアセンブリをParseしてMCInstを生成する仕組み。