# Simple

[English](README.md) | 日本語 | [翻訳について](docs/japanese-translation.md)

この文書は [Simple の README](README.md) の日本語訳です。

Sea of Nodes コンパイラ中間表現（IR）を紹介する Simple

このリポジトリは、Sea of Nodes コンパイラ IR を実演するためのものです。

Sea of Nodes は、HotSpot の C2 コンパイラ、Google の V8 コンパイラ、
Sun/Oracle の Graal コンパイラで使われる中核的な IR です。

SoN IR の紹介が目的なので、実装する*言語*そのものの重要性は高くありません。
C や Java に似た、機能がずっと少ない非常に単純な言語を使います。
Simple は強い型付けを持つオブジェクト指向言語で、*クロージャ*ではなく*関数*が第一級の値です。
オブジェクト参照はポインタであり、型システムによって null ポインタ例外を禁止します。
配列にもいずれ範囲チェックが導入されると考えられ、その場合 Simple は完全に安全な言語になります。
Simple の構文は最小限で、再帰下降パーサーで解析できます。

実用システムでは Sea of Nodes を機械語生成に使いますが、
この実演ではバックエンドの実装は難しく、重要性も比較的低くなります。
このリポジトリは x86-64、RISC-V、ARM64 を対象に事前（AOT）コンパイルを行いますが、
JIT コンパイルも視野に入れています。

このリポジトリは、どの意味でも完全な言語を目指してはいません。
そのため、バックエンドは SoN IR を直接解釈する Java の評価器から始まります
（第8章で初めて導入します）。コード生成は第19章で初めて登場します。

## 各章

以下は大まかな計画であり、変更されることがあります。

各章は自己完結した完全な実装です。Simple 言語の一部を完全に実装し、
前の章で作成したものをすべて含みます。また、各章には Sea of Nodes
中間表現の関連する側面について詳しい解説を付けます。

Simple 言語のスタイルは、C または Java のサブセットに倣っています。

* [第1章](docs/chapter01/README.ja.md)：整数リテラルを返すスクリプト。引数を受け取らず、整数値を1つ返す空の関数。`return` 文。
* [第2章](docs/chapter02/README.ja.md)：定数を使う加算、減算、乗算、除算などの単純な二項算術演算。ピープホール最適化と単純な定数畳み込み。
* [第3章](docs/chapter03/README.ja.md)：ローカル変数と代入文。右辺での読み取り、SSA、ローカル変数が定数の場合の追加のピープホール最適化。
* [第4章](docs/chapter04/README.ja.md)：`arg` という名前の、定数ではない外部入力変数。定数と `arg` を使う二項演算と比較演算。ゼロ以外の値は真とみなします。代数的簡約によるピープホール最適化。
* [第5章](docs/chapter05/README.ja.md)：`if` 文。制御フローグラフ（CFG）の構築。
* [第6章](docs/chapter06/README.ja.md)：実行されない制御フローに対するピープホール最適化。
* [第7章](docs/chapter07/README.ja.md)：`while` 文。ループ構造と先行的な Phi の導入。
* [第8章](docs/chapter08/README.ja.md)：ループ構造の続き。必要時の Phi の生成、`break` 文と `continue` 文。
* [第9章](docs/chapter09/README.ja.md)：大域的値番号付け。不動点に達するまでのピープホール最適化の反復。ワークリスト。
* [第10章](docs/chapter10/README.ja.md)：ユーザー定義の構造体、ポインタ、null 解析。SSA で表す単一のメモリ値。ロード、ストア、実行可能な評価器。
* [第11章](docs/chapter11/README.ja.md)：同値類によるエイリアス解析。`MemMerge`、`MemPhi`、`BulkMemPhi` による必要時のメモリ分割。
* [第12章](docs/chapter12/README.ja.md)：参照フィールド、前方参照、再帰的な構造体。
* [第13章](docs/chapter13/README.ja.md)：大域的コード移動とスケジューリング。
* [第14章](docs/chapter14/README.ja.md)：数値型。浮動小数点数、狭い整数型、範囲、`f32` への丸め。
* [第15章](docs/chapter15/README.ja.md)：静的な長さを持つ一次元配列型。配列のロードとストア。
* [第16章](docs/chapter16/README.ja.md)：コンストラクタ。
* [第17a章](docs/chapter17a/README.ja.md)：束縛の可変性、参照の権限、深い読み取り専用ビュー。
* [第17b章](docs/chapter17b/README.ja.md)：糖衣構文。`var`、`val`、`x+=y`、`for(init; test; next) body`。
* 第18章：関数と呼び出し。
* 第19章：命令選択と移植可能なコンパイル。
* 第20章：グラフ彩色によるレジスタ割り当て。
* 第21章：命令エンコーディングと ELF。
* 第22章：Simple の Hello, World!
* 第23章：メソッドと型の再検討。
* 第24章：連鎖した条件分岐と SCCP。
* 第25章：モジュール、分割コンパイル、不完全な型を使う SSA の構築。

## 章をまたぐビルド

任意で使える[対話的なグラフビューア（英語）](graph/README.md)は `graph/` で共有しています。
第1〜25章では、章のディレクトリで `make view` を実行して起動します。

[デバッグ用プリンタ（英語）](print/README.md)は `print/` で共有しています。
第2章で必要なのは1行の式形式だけです。共通の `BaseNode` が、プリンタとビューアの両方に
ノードの同一性とエッジへのアクセスを提供します。IR が拡張されるにつれて、
各章のアダプタが意味に関する詳細を追加します。

[命令エンコーダ（英語）](isa/README.md)は、第21〜25章の x86-64、ARM、RISC-V の
バイト出力処理と、ARM/RISC-V のテスト用評価器を共有します。
機械命令ノードの選択、レジスタ割り当て、コード配置は各章に残ります。
共通層は具体的なオペランドを受け取り、バイト列を書き出します。

最上位の Makefile は、各章の `tests`、`tags`（または `tag`）、`release`、`lib` ターゲットを実行します。
新しく取得したチェックアウトでは、まず `make lib`、続いて `make tests` を実行してください。

CI は Linux と JDK 21 で `make lib tests CTAGS=` を実行します。
Make のターゲットは、それらを使うテストの実行前に、第25章のネイティブランタイムと
`sys` ライブラリもビルドします。Maven の Java ビルドだけでは、これらの前提となる成果物は生成されません。

[章へのバックポート一覧（英語）](docs/chapter-backports.md)には、提案された小さな修正と
各章のテスト・レビューワークフローを記録しています。大規模なアーキテクチャ変更は、そこで別に管理します。
第10〜14章は現在、メモリ全体、必要時のエイリアス分割、参照、GCM、数値型の順に構成されています。
このメモリ表現は第25章まで引き継がれています。

メモリに関する章だけをビルドしてテストするには、次を実行します。

```sh
make lib tests release CHAPTERS="chapter10 chapter11 chapter12"
```

ルートの Maven リアクターはすべての章を含みます。
第10〜14章には、共通の `graph` と `print` モジュールに依存する、移植可能な IDEA モジュール記述子があります。
Make と直線的な履歴を作るワークフローは、番号付きの章ディレクトリを検出します。