LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@Syuparn

【ストレンジコード】Filskaコンパイラ開発計画(2) ソースコードをパースする【MLIR】

Last updated at Posted at 2024-05-29

シリーズ一覧:

TL; DR

  • FilskaをMLIR製コンパイラへ移植
  • 最低限の命令のみ実装し、処理系の骨組みを作成
    • Lexer: 字句解析
    • Parser: 構文解析
    • Sema: 意味解析

はじめに

本シリーズでは、『ストレンジコード』に登場する難解プログラミング言語「Filska」をMLIRへ移植します。本家がPython製インタプリタなので、コンパイラにすることで高速化できるのでは？という淡い期待も寄せています。

（ストレンジコードにはFilska以外の難解プログラミング言語もたくさん登場します！言語好きは必見です （ダイマ））

今回は処理系に最低限の命令を実装し、ソースコードからASTを作成するところまで進めます。

思い立った背景や開発の概要については初回の記事をご覧ください。

記事投稿者のスペック

MLIRもC++も初心者のため、誤った記述があればコメントで指摘いただけますと幸いです :bow:

  • C++: 未経験
  • LLVM: 未経験
  • MLIR: 未経験
  • 言語処理系: インタプリタのみ自作経験あり

処理系の骨組みをつくる

まずは処理系の設計指針を立てるため、ソースコードを読み込んでからLLVM IRを出力するまでに必要な処理を一通り実装します。
（ただし、命令は動作確認できる最低限のみ対応）

  • Lexer: 字句解析
    • ソースコード→トークン列
  • Parser: 構文解析
    • トークン列→AST
  • Sema: 意味解析
    • ASTがFilskaの制約を満たしているかチェック
      • 例：同名のサブプログラムが存在した場合エラー
  • CodeGen: MLIR生成
    • AST→MLIR (filskalang dialect)
  • Lowering: MLIRをLLVM IRへ変換
    • MLIR→LLVM IR

記事が長くなってしまったので、今回はSemaでASTのチェックを行うところまでの紹介となります。

設計

以下の2つの言語処理系を参考にしています。

  • Toy
    • MLIRの公式チュートリアル
    • toyソースコードをMLIRを経由しLLVM IRへ変換、その後JITコンパイラで実行

  • tinylang
    • 書籍『Learn LLVM 17』の題材として取り上げられる言語
    • Modula-2のサブセット
    • tinylangソースコードをLLVM IRへ変換したのちバイナリ生成

『Learn LLVM 17』は比較的新しいバージョンのライブラリを紹介しているため、バージョン互換の問題等が起こらず写経を進めることができおすすめです1。

『ストレンジコード』の言語を『Learn LLVM 17』、MLIRチュートリアルの設計を真似して実装したというオリジナリティ0構成

コーディングルール

命名規則はLLVM Coding Standardsに従うようにしました。
『Learn LLVM 17』のtinylangもこの命名規則を採用しています。

ディレクトリ名や変数名を大文字始まりのPascalCaseで記述しているため、違和感がある場合脳内でcamelCaseに変換してください。

(とはいえ、肝心のllvm-projectのソースコードでは小文字始まりの変数も多く存在しています... :thinking:)

また、後で読み返した時にクラスが何のライブラリか分かりやすいよう、名前空間を略さずに記載しています（例： StringRef ではなく llvm::StringRef）。

開発環境

  • 使用バージョン
    • LLVM: 18.1.4
    • MLIR: 18.1.4
    • clang: 17.0.1
  • 開発環境
    • WSL2 Ubuntu 20.04

環境構築のあれこれに詰まると辛いので (2敗) 、LLVMとMLIRはaptでインストールしています。
また、こうすることで将来的にFilskaコンパイラをDockerイメージで配布できるようになります。

aptでの環境構築とコンパイラのイメージ化について詳細は以下の記事をご覧ください。

実装する命令

動作確認をするための最小構成として、今回は以下の要素のみ実装します。

  • プログラム
  • サブプログラム: Filskaの命令をまとめた単位（他言語の「関数」に相当）
  • set 命令: サブプログラムのレジスタ m に指定した数値リテラルを格納
  • prt 命令: サブプログラムのレジスタ m の内容を数値として標準出力へ表示
  • hlt 命令: プログラムを終了する（サブプログラムはデフォルトで無限ループする）

下記のソースコードをパースできるようにします。

{ main
    set,10
    prt
    hlt
}

Lexer

『Learn LLVM 17』のtinylangを参考にしています。特に特殊な処理はなく、先頭から1文字ずつ読んでパターンと突合しています。

数値リテラルの指数部分の解析だけ少し骨が折れました。本家ではPythonの float 関数で手軽に変換しているところですが、この処理系では愚直に判別する必要があります2。

以下すべて数値リテラルとして正しい形式
1
1.23
1e+04
1.23e+04
-1
-1.23
-1.23e+04
-1.23e-04
Lexerの実装
lib/Lexer/Lexer.cpp
void Lexer::next(Token &Result) {
  // ...
  if (charinfo::isDigit(*CurPtr) || *CurPtr == '-') {
    number(Result);
    return;
  }
  // ...
}

void Lexer::number(Token &Result) {
  const char *End = CurPtr + 1;
  bool IsFloat = false;
  bool IsExponent = false;

  // 2文字目以降を解析
  // NOTE: 符号は先頭にしかないため確認不要
  for (; *End; End++) {
    if (charinfo::isDigit(*End)) {
      continue;
    }

    if (*End == '.') {
      if (!IsFloat && !IsExponent) {
        IsFloat = true;
        continue;
      }
      Diags.report(getLoc().getLoc(), diag::err_invalid_number_token);
    }

    if (*End == 'e') {
      if (!IsExponent) {
        IsExponent = true;
        End++;
        if (*End == '+' || *End == '-') {
          continue;
        }
      }
      Diags.report(getLoc().getLoc(), diag::err_invalid_number_token);
    }

    // number ends
    break;
  }
  formToken(Result, End, tok::number_literal);
}

Parser

こちらも『Learn LLVM 17』のtinylangを参考にしています。
Filskaの構文は前回の記事の通りです。中値演算子が無くLL(1)なので次のトークンを先読みするだけでよく、parserの実装がシンプルになっています。

引数（オペランド）の個数違いによるエラーはMLIR変換後追跡に難航しそうなため、一律構文エラーへ倒すことにしました。

オペランドの異なる命令は構文レベルで区別
{ main
    set,10 " 1引数の命令
    prt    " 0引数の命令
    prt,20 " 間違い!
    hlt
}

a.filska:4:8: error: instruction kw_prt requires 0 operands
    prt,20 " 間違い!

ちなみに、エラーメッセージ中のトークン名(kw_prt)はMagic Enumで取得しています。ヘッダファイルをコピペするだけで使えるので便利です。

Sema

同じくtinylangを参考にしています。
parserの各メソッドが対応するsemaのメソッドを呼び出し、AST構築前に静的解析を行います。
チェックに成功した場合のみ構築済みのASTをparserへ返すため、ASTが常に言語仕様上正しいことが保証されます。

現状チェックしているのは以下の2点のみです。

  • main という名前のサブプログラムが存在する（プログラムの意味解析）
  • 同名のサブプログラムが存在しない（サブプログラムの意味解析）

実装としては、シンプルにSemaのメンバ変数にサブプログラム名のsetを持たせて管理しています。

Semaの実装
lib/Sema/Sema.cpp
ast::Program *Sema::actOnProgram(Location Loc,
                                 std::vector<ast::Subprogram *> &Subprograms) {
  // mainが無ければエラー
  if (SubprogramNames.find("main") == SubprogramNames.end()) {
    Diags.report(Loc.getLoc(), diag::err_no_main);
  }

  return new ast::Program(Loc, Subprograms);
}

void Sema::actOnSubprogram(Location Loc, llvm::StringRef Name,
                           std::vector<ast::Instruction *> &Instructions,
                           std::vector<ast::Subprogram *> &Subprograms) {
  // 重複していたらエラー
  if (SubprogramNames.find(Name.str()) != SubprogramNames.end()) {
    Diags.report(Loc.getLoc(), diag::err_duplicated_subprogram, Name.str());
  }

  ast::Subprogram *Sub = new ast::Subprogram(Loc, Name, Instructions);
  Subprograms.push_back(Sub);
  SubprogramNames.insert(Name.str());
}

はまったところ

以下はまった点と解消方法についてです。
（備忘録なので適当に読み飛ばしてください）

環境構築

MLIRのヘッダが読み込めない

ビルド時に以下のエラーが発生しました。

in function `mlir::Operation::getSuccessors()':
Driver.cpp:(.text._ZN4mlir9Operation13getSuccessorsEv[_ZN4mlir9Operation13getSuccessorsEv]+0x15): undefined reference to `mlir::SuccessorRange::SuccessorRange(mlir::Operation*)'

CMakeLists.txt の target_link_libraries にMLIR関連の設定が入っていないのが原因だったのでこちらのプロジェクトを参考に設定を追加しました。

追加した設定

VSCode上でMLIRのヘッダが見つからない

コンパイルはできるようになったもののVSCode上でヘッダファイルが見つからずインテリセンスが効きませんでした。
clangdがビルドのオプションを認識できていないのが原因だったので、オプションを compile_commands.json に自動生成するようにしたら直りました。

CMakeLists.txt
set(CMAKE_EXPORT_COMPILE_COMMANDS ON)
compile_commands.json
[
{
  "directory": "/home/syuparn/filskalang",
  "command": "/usr/local/bin/clang++ -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS -I/home/syuparn/filskalang/include -I/usr/lib/llvm-18/include  -fPIC -fno-semantic-interposition -fvisibility-inlines-hidden -Werror=date-time -Werror=unguarded-availability-new -Wall -Wextra -Wno-unused-parameter -Wwrite-strings -Wcast-qual -Wmissing-field-initializers -Wimplicit-fallthrough -Wcovered-switch-default -Wno-noexcept-type -Wnon-virtual-dtor -Wdelete-non-virtual-dtor -Wsuggest-override -Wstring-conversion -Wmisleading-indentation -Wctad-maybe-unsupported -fdiagnostics-color -g -std=gnu++17   -D__STDC_CONSTANT_MACROS -D__STDC_FORMAT_MACROS -D__STDC_LIMIT_MACROS  -fno-exceptions -funwind-tables -o lib/Basic/CMakeFiles/filskalangBasic.dir/Diagnostic.cpp.o -c /home/syuparn/filskalang/lib/Basic/Diagnostic.cpp",
  "file": "/home/syuparn/filskalang/lib/Basic/Diagnostic.cpp",
  "output": "lib/Basic/CMakeFiles/filskalangBasic.dir/Diagnostic.cpp.o"
},
// ...
]

Segmentation Fault

lldb を使ってスタックトレースをたどりながら調査していました。 lldb を使うにはコアダンプが必要なため、-DCMAKE_BUILD_TYPE=DEBUG をビルド時に指定しています。

$ cmake -G Ninja . -DCMAKE_BUILD_TYPE=DEBUG
$ cmake --build .

# lldbを使用する場合、runの引数にfilskalang実行時の引数を指定する必要がある
$ lldb ./bin/filskalang
(lldb) run example/simple.filska

しかし、lldbを使っても shared libraryの中のスタックトレースは追えません 。今回私は横着してMLIRをaptでインストールしたため、 MLIR内部での関数呼び出しは一切スタックトレースに現れませんでした。調査が難航するので、本格的に使用する場合はソースコードからビルドした方が良いと感じました。

そもそもC++の所有権をちゃんと理解できていないのが原因です

おわりに

以上、Filskaコンパイラの設計の骨組みの紹介でした。次回はASTからMLIRを生成し、LLVM IRまで変換する処理を取り上げます。

  1. まだコンパイラフロントエンドの章しか読んでいませんが... ↩

  2. 自作言語だったら仕様を減らして実装をサボっていたところです。題材に既存言語の移植を選んだのは正解でした。 ↩

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?