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

シリーズ一覧:

- [【ストレンジコード】Filskaコンパイラ開発計画(1) 言語仕様を整理する【MLIR】](https://qiita.com/Syuparn/items/e8f4046c4a5b551db310)
- 【ストレンジコード】Filskaコンパイラ開発計画(2) ソースコードをパースする【MLIR】(本記事)
- [【ストレンジコード】Filskaコンパイラ開発計画(3) LLVM IRを出力する【MLIR】](https://qiita.com/Syuparn/items/1b6fc01bbe7370578756)
- [【ストレンジコード】Filskaコンパイラ開発計画(4) 実行ファイル出力【MLIR】](https://qiita.com/Syuparn/items/24ac10c76b73485ff85d)
- [【ストレンジコード】Filskaコンパイラ開発計画(5) サブプログラムを複数作成可能にする【MLIR】](https://qiita.com/Syuparn/items/35ee40e8b77bb8657cee)
- [【ストレンジコード】Filskaコンパイラ開発計画(6) llvmir以外のdialectを経由したloweringを可能にする【MLIR】](https://qiita.com/drafts/0c327b5af5bfed62e4d0)

# TL; DR

- [Filska](https://esolangs.org/wiki/Filska)をMLIR製コンパイラへ移植
- 最低限の命令のみ実装し、処理系の骨組みを作成
    - Lexer: 字句解析
    - Parser: 構文解析
    - Sema: 意味解析

https://github.com/Syuparn/filskalang

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

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

https://www.shuwasystem.co.jp/book/9784798069746.html

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

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

https://qiita.com/Syuparn/items/e8f4046c4a5b551db310

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

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

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

https://github.com/Syuparn/filskalang

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

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

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

- [Toy](https://github.com/llvm/llvm-project/tree/main/mlir/examples/toy/Ch7)
    - MLIRの公式チュートリアル
    - toyソースコードをMLIRを経由しLLVM IRへ変換、その後JITコンパイラで実行

https://mlir.llvm.org/docs/Tutorials/Toy/Ch-1/

- [tinylang](https://github.com/PacktPublishing/Learn-LLVM-17/tree/main/Chapter05/tinylang)
    - 書籍『Learn LLVM 17』の題材として取り上げられる言語
    - Modula-2のサブセット
    - tinylangソースコードをLLVM IRへ変換したのちバイナリ生成

https://www.packtpub.com/product/learn-llvm-17-second-edition/9781837631346

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

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

## コーディングルール
命名規則は[LLVM Coding Standards](https://llvm.org/docs/CodingStandards.html)に従うようにしました。
『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での環境構築とコンパイラのイメージ化について詳細は以下の記事をご覧ください。

https://qiita.com/Syuparn/items/1de554d862b5de4bc76f

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

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

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

```filska
{ main
    set,10
    prt
    hlt
}
```

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

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

```:以下すべて数値リテラルとして正しい形式
1
1.23
1e+04
1.23e+04
-1
-1.23
-1.23e+04
-1.23e-04
```

<details><summary>Lexerの実装</summary>

```cpp: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);
}
```
</details>

## Parser
こちらも『Learn LLVM 17』のtinylangを参考にしています。
Filskaの構文は[前回の記事](https://qiita.com/Syuparn/items/e8f4046c4a5b551db310#%E4%BB%95%E6%A7%98%E3%81%AE%E6%95%B4%E7%90%86)の通りです。中値演算子が無くLL(1)なので次のトークンを先読みするだけでよく、parserの実装がシンプルになっています。

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

```filska:オペランドの異なる命令は構文レベルで区別
{ 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で取得しています。ヘッダファイルをコピペするだけで使えるので便利です。

https://github.com/Neargye/magic_enum/tree/master?tab=readme-ov-file

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

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

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

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

<details><summary>Semaの実装</summary>

```cpp: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());
}
```
</details>

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

## 環境構築
### 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関連の設定が入っていないのが原因だったのでこちらのプロジェクトを参考に設定を追加しました。

https://github.com/Lewuathe/mlir-hello

追加した設定

https://github.com/Syuparn/filskalang/commit/8d89269735339e9b18f6afeebe11e038d8b1e74c#diff-6e3ee3c715bee8c42943812c74c6a99a6ade0c0a2a30983e5b4967cf3252b34cR13

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

```cmake:CMakeLists.txt
set(CMAKE_EXPORT_COMPILE_COMMANDS ON)
```

```js: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` をビルド時に指定しています。

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

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

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

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

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

[^learn-llvm17]: まだコンパイラフロントエンドの章しか読んでいませんが...
[^number]: 自作言語だったら仕様を減らして実装をサボっていたところです。~~題材に既存言語の移植を選んだのは正解でした。~~
[^llvmir]: まだ使っていないだけで、今後数学関連の命令は `math`, `arith` dialectへloweringする予定です。
[^tablegen]: ビルド時にTableGenファイルからC++ソースコードが生成されます。
[^mem2reg]: この例だと、さらに最適化されて引数に直接定数が入る形になっています。
[^include]: `filskalang/CodeGen/Ops.cpp.inc` を2回includeしていますが、defineで定義されている定数によって内容が変わるためいずれも必要です。（この仕組みはどこかで記事にしたい）
[^smloc]: コード生成時に `llvm::SMLoc` から行番号、列番号を抽出できないか試しましたがSegmentation Faultが発生してしまいました。lexer稼働時にリアルタイムで抽出する必要がありそうです。