tags: 授業 情報工学実験II

情報工学実験B: LLVMを用いた簡単なコンパイラの作成

実験の目的

極めて小規模な（とはいえ十分に汎用的な）C言語サブセットのコンパイラをLLVMコンパイラ基盤とC言語を用いて実現することで

• コンパイラが原始言語を対象（目的）言語に翻訳する仕組みを具体的に理解する
• 広く利用されているLLVMコンパイラ基盤の中間言語の初歩を理解する
• C言語についてよりよく理解し使いこなせるようになる

全体の構成

本実験で作成するのはC言語の小さなサブセット（以下，Pico-C）のコンパイラである。
中間言語としてLLVMコンパイラ基盤の中間言語（LLVM-IR）を用いる。この実験の主要な対象はLLVM-IRを出力するまでの工程（フロントエンド(の一部)）である。LLVM-IRを実際のハードウェアの目的言語に翻訳する工程（バックエンド）はLLVMに対応したC言語コンパイラであるclang（クラン）をはじめとする既存のLLVMのツールチェーンを使用する。

実験1では実際に様々なツールをシェル上でパイプして実行しながらこのコンパイルの流れ作業を理解する。コンパイラフロントエンドpicocのソースコードの本体はファイルpicoc.cで，実験2（LLVM-IR）が済むと理解できるようになる。実験3ではこのファイルにコードを追加・変更しフロントエンドの機能を強化する。

字句解析器(scan.c)やハッシュ表(hashmap.c)のソースコードは別のファイルに分離してあり、今回の実験ではこの内容を理解・変更する必要は一切ない。

ソースコードはすべてC99(ISO9899:1999, JIS X3010:2003) / C11(ISO9899:2011)に準拠したC言語の基本的な機能と標準ライブラリの関数だけを用い，理解し易さを重視して平易に記述されている。

実験環境の準備（事前に必ず準備・確認しておくこと）

実験にはWindow11のインストールされた各自のラップトップ（ノート）PCを用いる。事前に以下の環境を準備・確認しておくこと。

OS

WSL2（Windows Sybsystem for Linux version 2)上のUbuntu Linuxの24.04 LTSを用いる。他の授業で24.04を既にインストール済みの人はそのまま使えばよい。現在用いているバージョンが古い人は，公式解説を参考に24.04をインストールすること（既に使用しているディストリビューションと共存可能）。基本的には管理者権限で起動したPowerShellで以下のコマンドを実行し，ユーザ名とパスワードを設定するだけでよいはず。

wsl --install -d Ubuntu-24.04

ターミナル（端末）

実験の作業は専らターミナル(正確にはターミナル・エミュレータ）からコマンドを投入して（つまりCLI操作で）おこなう。Windows 11に標準でインストールされているWindowsターミナルを推奨する。もしなければStoreからインストールできる。あるいは，PowerShellでwingetコマンドを用いるとより簡単にインストールできる。

winget update -e --id Microsoft.WindowsTerminal

実験で用いる各種ツール

本実験で用いるCコンパイラ、LLVMツールチェーン等はすべてUbuntuのaptコマンドを用いて以下のようにパッケージでインストールできる。

sudo apt update && sudo apt install -y \
  curl git gcc make cgdb tree nkf bat \
  clang clangd llvm lld libclang-rt-dev-wasm32 wasi-libc \
  g++-aarch64-linux-gnu qemu-user \
  graphviz wl-clipboard libsixel-bin

テキストエディタ

コードの編集作業に用いるテキストエディタを準備しておくこと。C言語の授業等で普段使いのテキストエディタ（vim, emacs, nano, microなど）がある人はUbuntuにインストールしてそれを使い続ければよい。エディタを使い慣れない人（というのが情報工学科の3年次にいるのか疑問だが）には最近マイクロソフトが公開したEditがある。機能は最小限で誰でも直感的に使える。PowerShellで

winget install Microsoft.Edit

とすれば簡単にインストールできる（近い将来Windows11に標準でインストールされる予定）。WSLのUbuntuから起動するにはコマンド

edit.exe

を実行する。

Editより高機能なエディタを求める人には、マイクロソフトのVisual Studio Code (以下，VSCode)がある（公式解説）。VSCodeはStoreからインストールできる。あるいは，PowerShellでwingetコマンドを用いるとより簡単に導入できる。

winget install -e --id Microsoft.VisualStudioCode

上記のVSCodeはWindows版だが，WSLと連携する機能があるのでUbuntuからも簡単に起動できる。ただしそのためには拡張機能のインストールが必要。WSLが既に有効になっているとVSCodeを起動したときに導入を促す通知が表示されるのでそれに従えばよい。あるいは，PowerShellで以下のコマンドを実行するとより簡単確実に導入できる。

code --install-extension ms-vscode-remote.remote-wsl

もしよくわからないときは上記の公式解説を参照。

VSCodeと拡張機能が正しくインストールされていれば，WSLのUbuntuからコマンド

code .

でVSCodeが起動する。

[追記] 2025-10-16にv0.208.4でWindowsに正式対応したばかりのZedも動作が非常に高速かつ高機能でおすすめできる。Linux版をWSLのUbuntuにインストールするのではなく，Windows版をダウンロードしてインストールすること（WSLからの起動にも標準で対応している）。

WSLのUbuntuから起動するにはコマンド

zed ファイル名

を実行する。初回起動時にVimモードを選べば，普段Vimを使っている人にも使いやすい。また，clangdがインストールされていればそれを自動的に使うので，C言語のソースコードの編集が便利になる。

作業を効率化するための事前設定

Ubuntuで~/.profileに以下の設定を追記しておくと実験の作業が格段に効率化できる。詳しくはこの資料の最後の付録2,3を参照。

alias bat='batcat --theme Nord'

function open() {
    explorer.exe $(wslpath -w "$1")
}

alias pbcopy='(nkf -Lw | wl-copy)'
alias pbpaste='(wl-paste | nkf -Lu)'
alias pbrun='echo "$(pbpaste)"; read -p "y/n?: " c; [[ "$c" == y ]] && . <(pbpaste)'

# 以下はWSL 2.5.7以前のバグへの対応：
if [ ! -S "$XDG_RUNTIME_DIR/wayland-0" ]; then
    ln -s /mnt/wslg/runtime-dir/wayland-0* "$XDG_RUNTIME_DIR"
fi

設定は

. ~/.profile

を実行して即時有効にするか，あるいは次回WSL2のUbuntu起動時から有効になる。

実験で用いるコード一式のダウンロード

gitコマンドを用いてダウンロードする。

git clone https://github.com/okuisatoshi/jikkenB.git

カレントディレクトリにjikkenBというディレクトリがつくられる。このディレクトリ名は自由に変更してよい。実験の作業はすべてこのディレクトリに移動しておこなう。

cd jikkenB

実験1. コンパイルの流れ

シェルのパイプを用いてソースコードが実行ファイルにコンパイルされる各段階を確認する。また，中間言語の意義，クロスコンパイルと最適化の効果について理解する。

コンパイルの過程

Pico-Cコンパイラpicocの構築

make

フィボナッチ数列を求めるPico-Cソースコード（C言語のサブセット）

cat example/fib.pc

中間言語（LLVM-IR）への翻訳

cat example/fib.pc | ./picoc

さらにLLVMのバックエンドllcを用いてx86_64のアセンブリ言語に翻訳

cat example/fib.pc \
| ./picoc \
| llc

llc -march aarch64 # 64bit ARMのアセンブリを出力
llc -march wasm32  # 32bitのwebアセンブリを出力

さらにx86_64のアセンブラ(x86_64-linux-gnu-asあるいは短くas)を用いてx86_64のオブジェクトファイルfib.oを生成

cat example/fib.pc \
| ./picoc \
| llc \
| as -o fib.o

さらにリンカー（x86_64-linux-gnu-ldあるいは短くld）を用いてランタイムルーチンやライブラリを結合して最終的にx86_64の実行可能ファイル（バイナリ）fibを生成。手動でリンカーを呼び出すのは面倒なのでclangコンパイラを経由して間接的にldを呼び出す。

clang -o fib fib.o -static

x86_64マシン上でネイティブ実行

./fib

最適化

最適化器（オプティマイザ）optを用いて中間言語を最適化する段階を挿入する。example/fib.pcは計算が速すぎて効果が分かりずらいので，代わりに2,147,483,647回ループするexample/loop.pcで試す。

cat example/loop.pc \
| ./picoc \
| llc \
| as -o loop.o \
; clang -o loop loop.o -static

これにopt -S -O2をパイプに挿入するとLLVM-IRのコードが最適化され実行ファイルの実行速度が著しく高速化される。

cat example/loop.pc \
| ./picoc \
| opt -S -O2 \
| llc \
| as -o loop.o \
; clang -o loop loop.o -static

実際，

cat example/loop.pc \
| ./picoc \
| opt -S -O2

の出力をみるとループが消え，2147483647を出力するだけのコードに最適化されていることが確認できる。

LLVMバックエンドとしてのclang / lli

clangはLLVMコンパイラ基盤を用いて作られたコンパイラなので，実はLLVM-IRのコードも受け付ける。Pico-Cのコードを実行可能ファイルにコンパイルするには，単にpicocとclangをパイプして以下のようにするだけでよい。

cat example/fib.pc \
| ./picoc \
| clang -Wno-override-module -x ir - -O2 -o fib -static

以下の課題1の作業ではこの方法を用いるとよい。

あるいはバックエンドに中間言語LLVM-IRのインタプリタlliを用いて直ちに解釈実行することもできる（実行可能ファイルは生成されない）。実験2ではこの方法が便利である。

cat example/fib.pc | ./picoc | lli

クロスコンパイル

ここまではx86_64アーキテクチャのマシン上でx86_64向けのバイナリを生成してきた（いわゆるネイティブコンパイル）が，ターゲットを指定して他のアーキテクチャのマシン向けのバイナリを生成することもできる（クロスコンパイル）。

64bit ARM（aarch64）用にクロスコンパイル

cat example/fib.pc \
| ./picoc \
| clang -Wno-override-module \
  -x ir - -O2 -o fib.aarch64 -static \
  -target aarch64-linux-gnu

aarch64用の実行可能ファイルであることを確認

file fib.aarch64
# (出力)
# fib.aarch64: ELF 64-bit LSB executable, ARM aarch64, version 1 (GNU/Linux), statically linked, (以下略)

エミュレータqemu-aarch64を用いてx86_64マシン上でaarch64用の実行可能ファイルをエミュレーション実行

qemu-aarch64 fib.aarch64

./fib.aarch64

ソフトウェアでエミュレートするので，当然ながらネイティブ実行よりも実行が遅い。fib.aarch64はライブラリを静的にリンクした単一バイナリなので，このファイルをaarch64マシン（例：Raspberry Pi 3以降や，ARM CPUのMacやWindows PC）上のLinuxに移してネイティブ実行すればもっと高速になる（該当のマシンを持っている人はどのくらい速くなるか試してみるとよい）。

ターゲットをwasm32-wasiにしてWebAssemblyを出力することもできる．

cat example/fib.pc \
| ./picoc \
| clang -Wno-override-module \
  -x ir - -O2 -o dist/fib.wasm -static \
  -target wasm32-wasi

file dist/fib.wasm
# (出力)
# fib.wasm: WebAssembly (wasm) binary module version 0x1 (MVP)

WebAssemblyの実行環境であるwasmerをダウンロードし

make wasmer

これを用いて実行する。

~/.wasmer/bin/wasmer dist/fib.wasm

次にwebブラウザでの実行を確認する。

(cd dist; python3 server.py)

でwebサーバを起動し，webブラウザでlocalhost:8000/にアクセスするとfib.wasmの実行結果が表示される。

\time -f "real=%e[s] user=%U[s] (%P)"　計測したいコマンド

make asciinema

./asciinema rec -i 1 -c 'bash -l' a.cast

./asciinema rec -i 1 -c 'bash -l' --append a.cast

./asciinema play -s 5 a.cast

./asciinema play https://asciinema.org/a/xxxyyyzzz

./asciinema cat part1.cast part2.cast part3.cast > one.cast

./asciinema upload a.cast

実験2. LLVM中間言語

現代の多くのコンパイラで用いられるLLVM中間言語（LLVM-IR）の基本を理解し，簡単なC言語のコードを手作業でLLVM-IRに翻訳できるようになる。

初めてのLLVM-IRコード

define i32 @main() {
  ret i32 123
}

これはC言語の

int main()
{
    return 123;
}

に相当する。ret命令は関数から呼び出し元に復帰する命令である。i32はret命令の引数123の型が32ビットの符号付き整数であることを示している。@mainの前のi32も同様で、@main関数の返り値の型を表している。

LLVM-IRのコードの実行

LLVM-IRのコードを実行確認するときは実験1で学んだインタープリタlliを用いるのが簡便である。ファイルa.llにLLVM-IRのコードが保存されているとすると

lli a.ll

のようにして解釈実行できる。実験1でみたようにlliは標準入力を受け付けるので，以下のようにすればいちいちファイルに保存しなくて済む。

lli
# LLVM-IRのコードをコピペしてctrl-d

pbpaste | lli

OSに123が戻されたことは以下のように確認できる。

echo $? 
# 123と表示

式の計算

LLVM-IRでは式は書けないので分解して計算したい順序通り並べる必要がある（これがLLVM-IRと高級言語との一番の大きな違いである）。よって、例えばC言語の

int main()
{
    return 1+2*3;
}

に相当するLLVM-IRコードは

define i32 @main() {
  ret i32 1+2*3   ; 間違い！
}

ではなく

define i32 @main() {
  %t.1 = mul i32 2, 3
  %t.2 = add i32 1, %t.1
  ret i32 %t.2
}

のようになる。

ブラウザで実行してみる

仮想レジスタ（一時的な値の保持）

%t.1, %t.2は計算の途中の値に付けられた一時的な名前（仮想レジスタを表すローカル識別子）である。変数とは異なり値の変更はできない。上のコードを

; このコードは誤り
define i32 @main() {
  %t = mul i32 2, 3
  %t = add i32 1, %t
  ret i32 %t
}

のようにするのは間違いである（%tの値を再設定して変更しているから）。必ず他と重複しない新しい名前を用いる必要がある。%で始まっていればどんな名前でもよいが、以下では原則%t.に接尾辞として数字を付加して新しい名前をつくりだすことにする。

算術演算命令

add (+), mul (*)以外にもsub (-), sdiv (/), srem (%)などの命令が用意されている。

printf()の呼び出し

LLVM-IRはC言語の関数を呼び出すことが可能である。C言語の標準ライブラリにあるprintf()関数を呼び出して標準出力ストリームに整数1234567を出力するコードは以下のようになる。

declare i32 @printf(ptr, ...)
@fmt = constant [4 x i8] c"%d\0A\00"

define i32 @main()
{
  %t.1 = call i32 (ptr, ...) @printf(ptr @fmt, i32 1234567)
  ret i32 0
}

ブラウザで実行してみる

これはC言語のコード

extern int printf (const char *, ...);
const char fmt[4] = "%d\n";

int main()
{
    printf(fmt, 1234567);
    return 0;
}

にほぼ相当する。

LLVM-IRのコードの1行目は外部の関数printf()のプロトタイプ（引数や返り値の型等）を宣言している。printf()は可変引数なので第2引数以降は...になっている。2行目ではフォーマット文字列"%d\n"を用意している。6行目のcall命令は関数を呼び出す命令である。

変数（ローカル変数）

ローカル変数を（スタックに）割り当てるには alloca命令を用いる。

%t.1 = alloca i32

は32ビット整数型のローカル変数をスタックに割り当てており、C言語の変数宣言

int x;

に相当する。%t.1は変数xへのポインタ（変数xが割り当てられている最初のアドレス）を表す。割り当てた変数への読み書きはこのポインタ（アドレス）を経由して行なわれる。

LLVM-IRコードの可読性を高めるために、以降では allocaの値の一時名には宣言したい変数の名前の最初に%を補ったものを使う約束にする（また，後のコンパイラ作成も簡単になる）。

%x = alloca i32

変数に値を格納するには store命令を用いる。以下の

%x = alloca i32
store i32 123, ptr %x

はC言語の

int x;
x = 123;

に相当する。

逆に、変数に格納されている値を読み出すには load命令を用いる。上記の変数xの値を読み出すには

%t.1 = load i32, ptr %x

とする。%t.1が読み出した値を表している。

alloca, load, storeを用いたまとまった例：C言語の

int main()
{
	int x = 2;
	int y = x * 2;
	x = x + 1;
	return x + y;
}

に相当するLLVM-IRのコードは以下のようになる。

define i32 @main()
{
       ; int x = 2;
	%x = alloca i32
	store i32 2, ptr %x
	
	; int y = x * 2;
	%y = alloca i32
	%t.1 = load i32, ptr %x
	%t.2 = mul i32 %t.1, 2
	store i32 %t.2, ptr %y
	
	; x = x + 1;
	%t.3 = load i32, ptr %x
	%t.4 = add i32 %t.3, 1
	store i32 %t.4, ptr %x
	
	; return x + y;
	%t.5 = load i32, ptr %x
	%t.6 = load i32, ptr %y
	%t.7 = add i32 %t.5, %t.6
	ret i32 %t.7
}

ブラウザで実行してみる

scanf()の呼び出し

以下のコードでは，scanf()を呼び出して標準入力ストリームから入力した整数値を変数xに格納している。

declare i32 @scanf(ptr, ...)
@fmt = constant [3 x i8] c"%d\00"

define i32 @main()
{
  %x = alloca i32;
  %t.1 = call i32 (ptr, ...) @scanf(ptr @fmt, ptr %x)
  %t.2 = load i32, ptr %x;
  ret i32 %t.2
}

これはC言語のコード

extern int scanf (const char *, ...);
const char fmt[3] = "%d";

int main()
{
    int x;
    scanf(fmt, &x);
    return x;
}

にほぼ相当する。

scanf()も標準入力からデータを読み取るので，LLVM-IRのコードをコピペしてctrl-dしたあとで123を入力する。

lli; echo $?
# コードをコピペしてctrl-d
# 123を入力
# 123が出力

もちろん一旦ファイル（例：a.ll）に保存しておいて引数としてlliに与えてもよい。

echo 123 | lli a.ll ; echo $?

制御構造

LLVM-IRと高級言語のもうひとつの大きな違いは、前者には後者のような構造化された制御構造が用意されていないことである。代わりにC言語のgoto文に相当する br命令（分岐命令）を用いて任意の制御構造を実現する。

例：while文を含むコードの翻訳

C言語のコード

#include <stdio.h>
int main()
{
    int n = 10;
    while (n) {
        printf("%d\n", n);
        n = n - 1;
    }
    return 0;
}

をフローチャートで表せば

これはフローチャートの矢印に相当するgoto文と矢印の指すボックスに付けられたラベル(L1〜L3）を用いて以下のように表せる。

#include <stdio.h>
int main()
{
    int n = 10;
    goto L1;
    
L1: // while冒頭
    if (n) goto L2; else goto L3;
    
L2: // while本体
    printf("%d\n", n);
    n = n - 1;
    goto L1;
    
L3: // while直後
    return 0;
}

元のコードにあったwhile文はなくなっている。またif文はgoto文と組み合わされた

if (式) goto ラベル; else goto ラベル;

という限定された形でのみ出現する。これを以下ではif-goto文と呼ぶ。

goto文

goto <ラベル>;

は

br label %<ラベル>

に翻訳される。一方、if-goto文

if (式) goto <ラベル1> else goto <ラベル2>

は式の値をa (aは仮想レジスタや整数）とすると

%t.1 = icmp ne a, 0
br i1 %t.1, label %<ラベル1>, label %<ラベル2>

のように翻訳される。ここでicmp命令はa != 0なら（1ビット整数の）1を，そうでなければ0を返す。次の行のbr命令はこの%t.1の値をみて，1(真)なら%<ラベル1>へ0(偽)なら%<ラベル2>へと条件分岐する。

icmp命令にはne (!=)の他にもeq (==)，slt (<), sgt (>), sle (<=), sge (>=)などが指定できる。よって上記はeqを用いて

%t.1 = icmp eq a, 0
br i1 %t.1, label %<ラベル2>, label %<ラベル1>

でもよい（ラベルの順序が交換されているのに注意）。

このようにして最終的にコード全体は以下のように翻訳される。

declare i32 @printf(ptr, ...)
@fmt = constant [4 x i8] c"%d\0A\00"

define i32 @main()
{
; 開始(ラベル省略)
  %n = alloca i32
  store i32 10, ptr %n
  br label %L.1
  
L.1: 
; while冒頭
  %t.1 = load i32, ptr %n
  %t.2 = icmp eq i32 %t.1, 0
  br i1 %t.2, label %L.3, label %L.2
  
L.2: 
; while本体
  %t.3 = call i32 (ptr, ...) @printf(ptr @fmt, i32 %t.1)
  %t.4 = sub i32 %t.1, 1
  store i32 %t.4, ptr %n
  br label %L.1
  
L.3: 
; while直後
  ret i32 0
}

ブラウザで実行してみる

制御フローグラフ

上記のような制御フローグラフ(CFG)を用いるとLLVM-IRのコードの流れが分かりやすく可視化できる。CFGはLLVMのoptコマンドとGraphvizのdotコマンドを用いれば簡単に描ける。例えばファイルexample/prime.pcのmain関数の内容をCFGで描き画像ファイルprime.pdfとして出力するには以下のようにする。

cat example/prime.pc \
| ./picoc \
| opt -passes=dot-cfg >&- \
; dot -T pdf .main.dot >prime.pdf \
; rm -f .main.dot

シェルスクリプトを用意したので例えば

cat example/prime.pc \
| ./picoc \
| ./misc/cfg.sh pdf >prime.pdf

のようにするだけでよい。

画像の形式はpdfの他にpng、gif, jpg，svgなど様々な画像形式が指定できる。

open prime.pdf

img2sixel -w 800 prime.png

基本ブロック

フローチャートから忠実に実現した（すなわち矢印をgoto文で置き換えた）C言語のコードは

• ラベルで始まり
• goto文/if-goto文/return文で終わる

ようなコードの集まりになるはずである。よって，これから逐語訳で変換したLLVM-IRのコードも，CFGが示すように

• ラベルで始まり
• br命令/ret命令で終わる

ようなコード（基本ブロック）の集まりになる。

各命令の構文に間違いがないはずなのに自分の書いたLLVM-IRのコードが構文エラーになるようなときは，goto文/if-goto文を用いたC言語のコードに戻って忠実にフローチャートを実現しているか確認し，正しく基本ブロックになっているかチェックするとよい。

真偽値から整数への変換

icmp命令の返す真偽値(0,1)は1ビットの整数である。真偽値a(aは仮想レジスタや0,1）を32ビット整数にキャスト（型変換）するにはゼロ拡張命令zextをつかって

%t.1 = zext i1 a to i32

のようにする。%t.1が結果として得られるi32型の値としての0,1を表している。

picoc.cではicmp命令で計算した不等号<,>,<=,>=の値を32ビット整数に統一するのにこれを用いている。

#include <stdio.h>

int main()
{
    int n;
    scanf("%d", &n);
    int i = 1;
    while (i * i <= n) {
        if (n % i == 0) {
	    printf("%d\n", i);
	    printf("%d\n", n / i);
	}
        i = i + 1;
    }
    return 0;
}

実験3. コンパイラの機能拡張

コンパイラフロントエンドのコード（picoc.c）を理解し，新たにif文をサポートする機能を実現する。さらに余力のある人は配列をサポートする機能も実現する。

Pico-Cの文法

Pico-Cは標準C言語の（ほぼ）サブセットである。扱うデータ型はint型だけで，他の整数型や浮動小数型はない。また，配列，構造体，ポインタ等の派生型もない。よって文字列もない。ローカル変数が宣言できるが，初期値は代入で設定する。代入は式文としてしか出現できない。制御構造はwhile文だけで，if文等はない。演算子も9個しかない（後述）。関数はmain()しかなく他の関数を呼び出す機能もない。このため，scanf()/printf()関数を呼び出す代わりに，標準入力ストリームから10進整数を読み込むscan文と標準出力ストリームに10進整数を書き出すprint文が追加されている。以上の文法をBNFと構文図式でまとめると以下の通りである。

Program   ::= 'int' 'id' '(' ')' Block
Block     ::= '{' ( Decl | Statement )* '}'
Decl      ::= 'int' 'id' ';'
Statement ::= Assign_st | Scan_st | Print_st | While_st | Block
Assign_st ::= 'id' '=' Expr ';'
Scan_st   ::= 'scan' 'id' ';'
Print_st  ::= 'print' Expr ';'
While_st  ::= 'while' '(' Expr ')' Statement
Expr      ::= Additive_1 ( ( '<' | '>' | '<=' | '>=') Additive_2 )*
Additive  ::= Term_1 ( ( '+' | '-' ) Term_2 )*
Term      ::= Factor_1 ( ( '*' | '/' | '%') Factor_2 )*
Factor    ::= 'id' | 'num' | '(' Expr ')'

Program:

Block:

Decl:

Statement:

Assign_st:

Scan_st:

Print_st:

While_st:

Expr:

Additive:

Term:

Factor:

標準C言語と同じく整数0が偽値falseを表し、0以外の整数(典型的には1)が真値trueを表す。式を構成する演算子は+, -, *, /, %,<, >, <=, >=の9個ですべて左結合の二項演算子である。このうち<, >, <=, >=は成り立てば1をそうでなければ0を返す。演算子の結合順位は標準C言語と同じである。

工夫次第でより複雑な条件式を表せる。以下c,dを値0か1を取る式とすると，条件cの否定「cでない」(!c)はc < 1と表せる．「cかつd」はc * dと表せる．よって，「cまたはd」はド=モルガンの法則を用いて((c < 1) * (d < 1)) < 1と表せる。あるいはより簡単にc + d > 0でもよい。

（不）等号==, !=は用意されていないが，a == bは(a <= b) * (b <= a)で表せる。よってa != bは((a <= b) * (b <= a)) < 1で表せる。あるいは
(a < b) + (b < a) > 0でもよい。

変数の宣言では初期化はできないので

int n = 0;

は

int n; n = 0;

とする必要がある。

代入は式文としての出現に制限しているので，例えば入れ子になった代入式

x = y = 0;

は記述できない。代わりに２文に分けて

y = 0; x = y;

のように書く必要がある。データ型はint型だけなので代入式の左辺は変数名を表す識別子しか出現しない。

while文は標準Cのそれと同じである。条件式の値が0でない間，反復する。反復される文が1つしかないときは，それを囲むブラケット{ ... }は不要である。

if文は用意されていないが，高々1回だけ反復するwhile文で模倣できる。具体的には

if (C) S;

は

int c; c = C;
while (c) { S; c = 0; }

で実現できる。

if (C) S1 else S2;

も

int c1; int c2;
c1 = C; c2 = c1 < 1;
while (c1) { S1; c1 = 0; }
while (c2) { S2; c2 = 0; }

のようにすればよい。短絡論理演算(&&, ||)はif文で

c = a && b

if (a) c = b; else c = 0;

c = a || b

if (a) c = 1; else c = b;

のように実現できるので上記のようにwhile文になおせる。

ディレクトリexampleにはPico-Cで書かれたコードのサンプルがいくつかある。

fib.pc    フィボナッチ数列を求める
gcd.pc    ユークリッドの互助法で最大公約数を求める
prime.pc  素数列を求める
binary.pc バイナリー法でべき剰余を高速に求める
bench.pc  10億回程度反復するベンチマーク

prime.pcとbinary.pcあたりをみるとPico-Cのだいたいの感じがつかめる。

コンパイラのソースコード(picoc.c)

/*
 * Pico-Cコンパイラ
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "scan.h"
#include "hashmap.h"

int token;             // 最後に読んだトークン
char name[MAX_TK_LEN]; // ...の名前
int vsuffix = 1;       // 値の一時名の接尾番号
int lsuffix = 1;       // ラベルの接尾番号
struct hashmap *hmap;  // 変数名と行番号の対を保存するハッシュ表
#define MAX_TMP_LEN (MAX_TK_LEN + 1) // 値の一時名の最大長

// デバッグモードでは標準エラー出力に構文解析木が出力される
//#define DEBUG
int findent = 0;
#ifdef DEBUG
#define ENTER() { findent += 3; fprintf(stderr, "%*c|- %s\n", findent, ' ', __func__); }
#define LEAVE() findent -= 3
#define FEED() fprintf(stderr, "%*c   \'\e[7m%s\e[0m\' \e[2m (行%d:%d)\e[0m\n", findent, ' ', name, row, col)
#else
#define ENTER()
#define LEAVE()
#define FEED()
#endif

void statement(void);
void expr(char *ret);


void expect(int expected)
{
    if (token == expected) {
        FEED();
        token = get_next_token(name);
        return;
    }
    fprintf(stderr, "期待されない字句(行%d:%d): %s\n", row, col, name);
    exit(1);
}


void lval(char *x)
{
    ENTER();
    if (hget(hmap, name) < 0) {
        fprintf(stderr, "不明な変数(行%d:%d): %s\n", row, col, name);
        exit(1);
    }
    sprintf(x, "%%%s", name);
    expect(TK_ID);
    LEAVE();
}


void num(char *ret)
{
    ENTER();
    strcpy(ret, name);
    expect(TK_NUM);
    LEAVE();
}


void factor(char *ret)
{
    ENTER();
    char x[MAX_TMP_LEN];
    int v = vsuffix++;
    switch (token) {
        case TK_ID:
            lval(x);
            // 代入の左辺以外に出現する左辺値は参照を外す
            printf("  %%t.%d = load i32, ptr %s\n", v, x);
            sprintf(ret, "%%t.%d", v);
            break;
        case TK_NUM:
            num(ret);
            break;
        case  '(':
            expect('(');
            expr(ret);
            expect(')');
            break;
        default:
            fprintf(stderr, "期待されない字句(行%d:%d): %s\n", row, col, name);
            exit(1);
    }
    LEAVE();
}


void term(char *left)
{
    ENTER();
    factor(left);
    while (token == '*' || token == '/' || token == '%') {
        int op = token;
        expect(op);
        char right[MAX_TMP_LEN];
        factor(right);
        int v = vsuffix++;
        const char *f = op == '*' ? "mul" : op == '/' ? "sdiv" : "srem";
        printf("  %%t.%d = %s i32 %s, %s\n", v, f, left, right);
        sprintf(left, "%%t.%d", v);
    }
    LEAVE();
}


void additive(char *left)
{
    ENTER();
    term(left);
    while (token == '+' || token == '-') {
        int op = token;
        expect(op);
        char right[MAX_TMP_LEN];
        term(right);
        int v = vsuffix++;
        const char *f = op == '+' ? "add" : "sub";
        printf("  %%t.%d = %s i32 %s, %s\n", v, f, left, right);
        sprintf(left, "%%t.%d", v);
    }
    LEAVE();
}


void expr(char *left)
{
    ENTER();
    additive(left);
    while (token == '<' || token == '>' || token == TK_LEQ || token == TK_GEQ) {
        int op = token;
        expect(op);
        char right[MAX_TMP_LEN];
        additive(right);
        int u = vsuffix++, v = vsuffix++;
        const char *f = op == '<' ? "slt" : op == '>' ? "sgt" : op == TK_LEQ ? "sle" : "sge";
        printf("  %%t.%d = icmp %s i32 %s, %s\n", u, f, left, right);
        printf("  %%t.%d = zext i1 %%t.%d to i32\n", v, u);
        sprintf(left, "%%t.%d", v);
    }
    LEAVE();
}


void print_st(void)
{
    ENTER();
    expect(TK_PRINT);
    char e[MAX_TMP_LEN];
    expr(e);
    printf("  %%t.%d = call i32 (ptr, ...) @printf(ptr @fmt_printf, i32 %s)\n", vsuffix++, e);
    expect(';');
    LEAVE();
}


void scan_st(void)
{
    ENTER();
    expect(TK_SCAN);
    char x[MAX_TMP_LEN];
    lval(x);
    printf("  %%t.%d = call i32 (ptr, ...) @scanf(ptr @fmt_scanf, ptr %s)\n", vsuffix++, x);
    expect(';');
    LEAVE();
}


void assign_st(void)
{
    ENTER();
    char x[MAX_TMP_LEN];
    lval(x);
    expect('=');
    char e[MAX_TMP_LEN];
    expr(e);
    printf("  store i32 %s, ptr %s\n", e, x);
    expect(';');
    LEAVE();
}


void while_st(void)
{
    ENTER();
    int while_entry = lsuffix++;
    int while_body = lsuffix++;
    int while_end = lsuffix++;
    printf("  br label %%L.%d\n", while_entry);

    // whileループ冒頭のブロック
    printf("L.%d:\n", while_entry);
    expect(TK_WHILE);
    expect('(');
    char e[MAX_TMP_LEN];
    expr(e);
    expect(')');
    int c = vsuffix++;
    printf("  %%t.%d = icmp eq i32 %s, 0\n", c, e);
    printf("  br i1 %%t.%d, label %%L.%d, label %%L.%d\n", c, while_end, while_body);

    // whileループ本体のブロック
    printf("L.%d:\n", while_body);
    statement();
    printf("  br label %%L.%d\n", while_entry);

    // whileループの直後のブロック
    printf("L.%d:\n", while_end);
    LEAVE();
}


void decl(void)
{
    ENTER();
    expect(TK_INT);
    int r = hget(hmap, name);
    if (r >= 0) {
        fprintf(stderr, "宣言の重複(行%d:%d): %s (行%dで既出)\n", row, col, name, r);
        exit(1);
    }
    char *x = malloc(MAX_TK_LEN); // hdestroy()内でfree()される
    strcpy(x, name);
    hinsert(hmap, x, row); // xの宣言の行番号を記録
    expect(TK_ID);
    printf("  %%%s = alloca i32\n", x);
    expect(';');
    LEAVE();
}


void block(void)
{
    ENTER();
    expect('{');
    while (token != '}') {
        if (token == TK_INT) decl(); else statement();
    }
    expect('}');
    LEAVE();
}


void statement(void)
{
    ENTER();
    switch (token) {
        case TK_PRINT:
            print_st();
            break;
        case TK_SCAN:
            scan_st();
            break;
        case TK_ID:
            assign_st();
            break;
        case TK_WHILE:
            while_st();
            break;
        case '{':
            block();
            break;
        default:
            fprintf(stderr, "期待されない字句(行%d:%d): %s\n", row, col, name);
            exit(1);
    }
    LEAVE();
}


void program(void)
{
    ENTER();
    printf("@fmt_printf = constant [4 x i8] c\"%%d\\0A\\00\"\n");
    printf("@fmt_scanf  = constant [3 x i8] c\"%%d\\00\"\n");
    printf("declare i32 @printf(ptr, ...)\n");
    printf("declare i32 @scanf(ptr, ...)\n");
    printf("@__main_void = alias i32 (), ptr @main\n\n"); // target:wasm32-wasiで必要

    expect(TK_INT);
    if (strcmp(name, "main") != 0) {
        fprintf(stderr, "main関数が必要(行%d:%d): %s\n", row, col, name);
        exit(1);
    }
    expect(TK_ID);
    expect('(');
    expect(')');
    printf("define i32 @main() {\n");
    block();
    printf("  ret i32 0\n");
    printf("}\n");
    LEAVE();
}


int main()
{
    hmap = hnew();
    token = get_next_token(name);
    program();
    hdestroy(hmap); // キーもここでfreeしている
}

picoc.cの概要

ファイルpicoc.cはおよそ300行のC言語のコードで、5つのグローバル変数と16個の関数定義が含まれている。

グローバル変数と字句解析器の呼び出し

各グローバル変数の役割は以下の通りである。

token    次に処理する字句の識別番号(scan.h参照)
name     その名前
vsuffix  次に用いる仮想レジスタ名の添字番号
lsuffix  次に用いるラベル名の添字番号
hmap     変数名を管理するハッシュ表

グローバル変数tokenは次に処理すべき字句の識別番号を常に保持している。またその字句の名前（文字列）はnameというグローバル変数に保持されている。字句解析器(scan.c)を呼び出してこれらを更新するにはget_next_token()という関数を呼び出す。

token = get_next_token(name);

vsuffixやlsuffixは重複のない仮想レジスタ名やラベル名を生成するための添え字として使用される。使用する毎にカウントアップし，重複を避ける。hmapは宣言された変数の名前をコンパイル作業の間、いつでも参照できるよう保存しておくためのハッシュ表で，宣言のし忘れや重複宣言を検出するのに用いられる。

再帰下降型解析

16個の関数のうち、12個は上述の12個の構文図式と１対１に対応しており、各図式にしたがって字句を読み進めながらLLVM-IRの命令列を（printf()関数を用いて）出力する。構文の解析が終了した時点でコードの生成も同時に完了している。このように構文解析とコード生成を同時におこなうコンパイラは1パス方式と呼ばれる。抽象構文木を生成しないので仕組みが簡単であり、単純な言語のコンパイラでしばしば用いられる。また、構文図式にそって各構文に対応する関数を（再帰）呼び出ししながら解析を進める方法は再帰下降型構文解析と呼ばれる。

残りの4つの関数はmain()と下請け関数である。

main()   処理の開始
expect() 字句をひとつ読み進めたりエラーを検出する下請け関数
num()    数を処理する下請け関数
lval()   左辺値（変数）を処理する下請け関数

式

式の構文図式に対応する4つの関数

factor()   因子（これ以上分割できない基本的な式）の処理
term()　　　項（1つ以上の因子を乗除余算でつないだ式）の処理
additive() 加法式（1つ以上の項を加減算でつないだ式）の処理
expr()　　　式（1つ以上の加法式を不等号でつないだ式）の処理

にnum(), lval()を加えた6つの関数は、呼び出されるときに文字列を格納するためのバッファ（char型の配列）を実引数として渡される（正確にはその先頭要素へのポインタを渡される）。復帰（リターン）の際にはこのバッファに式の計算結果を表す"%t.1"のような仮想レジスタ名かあるいは十進整数を表す"123"のような文字列を書き戻す。

変数の宣言と参照

変数の宣言（図式Decl）は関数decl()で処理される。まず，hget(hmap, name)を呼び出して変数が既に登録されていないかチェックし，登録済みの場合は重複宣言のエラーにしている。登録されていない場合はhinsert(hmap, x, row)を呼び出してハッシュ表に登録し，

printf("  %%%s = alloca i32\n", x);

でalloca命令を出力する。

変数名を表す文字列はdecl()関数から抜けた後も随時参照されるのでヒープに動的に割り付ける必要がある。

char *x = malloc(MAX_TK_LEN); // hdestroy()内でfree()される
strcpy(x, name);

割り付けられた記憶域は，最後にhdestroy()を呼んでハッシュ表を解放する際にあわせて解放される（ので自分でfreeしないこと）。

左辺値（変数）の参照に関する処理は下請けの関数lval(char *x)として共通化されており，関数factor()やassign_st()から呼び出される。lval()は次に出現する字句をハッシュ表から検索し宣言済みの変数名であることを確認する（なければエラーにする）。確認した変数名の最初に'%'を補った文字列を、引数として与えられたバッファに書き込む（このような文字列の加工にはsprintf()が便利）。

約束により変数名の前に'%'を付けるとその変数を指すポインタ（アドレス）を意味するので、これをstore/load命令に渡せば変数を読み書きできる。代入文（図式Assign_st）を処理するassign_st()ではこれを用いてstore命令を出力している。

printf("  store i32 %s, ptr %s\n", e, x);

因子（図式Factor）を処理するfactor()関数ではこれを用いてload命令を出力している。

printf("  %%t.%d = load i32, ptr %s\n", v, x);

printf()の書式文字列の中で'%'そのものを表すには%を重ね書きして%%のようにすることに注意。

while文

while文（図式While_st）に対応する関数while_st()では実験2（LLVM-IR）のwhile文の実現方法にしたがって、3つのブロックのためのラベルを用意する。

int while_entry = lsuffix++;
int while_body  = lsuffix++;
int while_end   = lsuffix++;

冒頭ブロック（while_entry)では，まず条件式の値eを計算するコードを出力する。この値はi32（32ビットの整数）である。次にこれが0かどうかによってwhile_endかwhile_bodyに条件分岐するコード

int c = vsuffix++;
printf("  %%t%d = icmp eq i32 %s, 0\n", c, e); 
printf("  br i1 %%t%d, label %%L%d, label %%L%d\n", c, while_end, while_body);

を出力している。

while_bodyの末尾では反復のために

printf("  br label %%L%d\n", while_entry);

で冒頭のブロックに無条件に戻る命令を出力している。

git diff --color=always picoc.c

git diff --diff-algorithm=histogram --color=always picoc.c

make

#define TK_IF 134     // if
#define TK_ELSE 135   // else

課題4（配列のサポート）[提出は任意，加点対象]

注意：これは課題1〜3に取り組んだ人だけが提出できる余力と意欲のある人向けのオプション課題である．課題1〜3にやり残しがあると採点されない。また，再提出レポートでの追加提出はできない。

課題3に加え、int型の要素の（1次元）配列をサポートするようにpicoc.cを拡張せよ。example/arrayにあるサンプルコードが正しくコンパイル・実行できるか確認せよ。

配列をサポートしたPicoc-Cの構文は以下のようになる（変更のある箇所のみ記載）。

Decl      ::= 'int' id ( '[' 'num' ']' )? ';'
Assign_st ::= 'id' ( '[' Expr ']' )? '=' Expr ';'
Factor    ::= 'id' ( '[' Expr ']' )? | 'num' | '(' Expr ')'

Decl:

Assign_st:

Factor:

Pico-Cはポインタをサポートしないので，式の中に配列名aが出現するときは必ずブラケットを伴ってa[...]という形で出現する。

実験上のヒント

配列の宣言もalloca命令でおこなえる。例えばint型の要素3つの配列aを宣言するには

%a = alloca [3 x i32]

とすればよい。%aは確保された配列を指すポインタである。

（参考）LLVMはバージョン15でopaque pointer （ポインタの指す先のオブジェクトの型情報を持たないポインタ，C言語でいえばvoid *のようなもの）がデフォルトになったので，「配列全体の先頭を指すポインタ」と「配列の先頭要素を指すポインタ」は区別されない。アドレスとしては両者は同一だからである。

alloca命令が返す配列の先頭を指すポインタから各要素を指すポインタを得るにLLVM-IRのgetelementptr (GEP)命令を用いる。GEP命令は配列や構造体等を指すポインタ（アドレス）からその要素やメンバを指すポインタ（アドレス）を算出するための汎用的な命令である。

The Often Misunderstood GEP Instruction
LLVM's getelementptr, by example

例えば&a[2]（= a + 2）を得るにはgetelementptr命令を用いて

%t.1 = getelementptr i32, ptr %a, i32 2

のようにする。最初のi32がポインタの指す先のオブジェクト（要素）の型を，最後の2が要素2つ分ずらすことを指定している部分である。GEP命令の返すポインタ（アドレス）をload命令やstore命令に渡せば，通常の変数と同じように配列の要素の読み書きができる。

例えば

int main()
{
  int a[3];
  a[0] = 12;
  a[1] = 34;
  a[2] = a[0] + a[1];
  return a[2];
}

は以下のように実現できる。

define i32 @main()
{
    %a = alloca [3 x i32]
    %t.1 = getelementptr i32, ptr %a, i32 0 ; &a[0]
    %t.2 = getelementptr i32, ptr %a, i32 1 ; &a[1]
    %t.3 = getelementptr i32, ptr %a, i32 2 ; &a[2]
    store i32 12, ptr %t.1 ; a[0] = 12
    store i32 34, ptr %t.2 ; a[1] = 34
    %t.4 = load i32, ptr %t.1
    %t.5 = load i32, ptr %t.2
    %t.6 = add i32 %t.4, %t.5
    store i32 %t.6, ptr %t.3 ; a[2] = a[0] + a[1]
    ret i32 %t.6
}

%aと%t.1は同じアドレスなのでGEP命令

%t.1 = getelementptr i32, ptr %a, i32 0 ; &a[0]

は冗長だが，&a[0]を&a[1]や&a[2]と統一的に扱うために敢えて入れた。

図式Assign_st，Factorの左辺値（変数）を参照する部分は下請けの関数lval()に共通化されているので，関数assign_st()とfactor()に手を加えるよりlval()に手を加えるほうが作業が簡単に済む。lval()とdecl()への追加・変更は合わせてもわずか20行程度である。

付録1：デバッグのヒント

デバッグ出力を有効にする

変数DEBUGをセットしてpicocをコンパイルしなおすと標準エラー出力ストリームに構文解析木を出力するようになる。

make clean; CFLAGS=-DDEBUG make

もとに戻すには

make clean; make

CFLAGSでDEBUGを定義する代わりにpetitc.cの中で

// #define DEBUG

のコメントを外して有効化してもよい。

これでコンパイルの過程を（標準エラー出力ストリームに）ツリー表示するようになるのでデバッグに役立つ。以下はfib.pcを処理したときの出力の冒頭部分。どのように関数が呼ばれてどの関数でどの字句を処理したのかが分かるのでデバッグに役立つ。

実行例：

cat example/fib.pc | ./picoc 2>&1 1>- |  bat

  |- program
      'int'  (行1:1)
      'main'  (行1:5)
      '('  (行1:9)
      ')'  (行1:10)
      |- block
         '{'  (行2:1)
         |- statement
            |- print_st
               'print'  (行3:5)
               |- expr
                  |- additive
                     |- term
                        |- factor
                           |- num
                              '1'  (行3:11)
               ';'  (行3:12)
         |- decl
            'int'  (行4:5)
            'f0'  (行4:9)
            ';'  (行4:11)
         |- statement
            |- assign_st
               |- lval
                  'f0'  (行4:13)
               '='  (行4:16)
(以下省略)

想定外のことが起こったときに実行を強制終了させる

assert(式)マクロを挿入すると式が成り立たないときに実行を強制終了し、その行番号を表示できる。

例：

assert(token == '+');

は、tokenの値が'+'でなかった場合に強制終了し、行番号を表示する。

assert()マクロを用いるには

#include <assert.h>

を加える。コード完成後、assert.hを読み込むより前で

#define NDEBUG

しておけば、assert()を無効化できる(無害なvoid式で置換される)ので、手作業でassert()式をわざわざ取り除く必要はない。

デバッガgdb/cgdbを活用する

別ページを用意した。

コンパイラ実験に便利なgdb (cgdb)の使い方

付録2 WSL2のファイルをエクスプローラで開く

WSLのファイルやディレクトリもexplorer.exeで開けるが，パスの仕様がWindowsとLinuxでは異なるのでやや不便である．~/.profileに下記の設定

function open() {
    explorer.exe $(wslpath -w "$1")
}

を追記しておくと

open example/kadai3/prime_kadai3.pc

のように深い階層にあるファイルやディレクトリもLinuxのパス指定の方法で簡単に開けるようになる．

付録3 コマンドとクリップボードを連携する

~/.profileに以下の設定

alias pbcopy='(nkf -Lw | wl-copy)'
alias pbpaste='(wl-paste | nkf -Lu)'
alias pbrun='echo "$(pbpaste)"; read -p "y/n?: " c; [[ "$c" == y ]] && . <(pbpaste)'

# 以下はWSL 2.5.7以前のバグへの対応：
if [ ! -S "$XDG_RUNTIME_DIR/wayland-0" ]; then
    ln -s /mnt/wslg/runtime-dir/wayland-0* "$XDG_RUNTIME_DIR"
fi

を追記しておくとコマンドの出力をクリップボードにコピーしてWindowsアプリで用いたり，逆にクリップボードの内容をコマンドにパイプして利用したりできるようになる。

(別の方法) 上記の方法が上手く動作しない環境では、win32yank.exeというWindowsアプリ（リンク先のwin32yank-x64.zipをダウンロードして解凍すると得られる）をCドライブ直下C:\に置き，~/.profileに以下の設定を書いておくのでもよい。

alias pbcopy="/mnt/c/win32yank.exe -i --crlf"
alias pbpaste="/mnt/c/win32yank.exe -o --lf"
alias pbrun='echo "$(pbpaste)"; read -p "y/n?: " c; [[ "$c" == y ]] && . <(pbpaste)'

pbcopy/pbpaste/pbrunの使用例

例：（Webブラウザ上で）クリップボードにコピーしたLLVM中間言語のコードをhello.llというファイルに保存。

pbpaste > hello.ll

例：（Webブラウザ上で）クリップボードにコピーしたLLVM中間言語のコードをインタプリタlliで実行。

pbpaste | lli

例：（Webブラウザ上で）クリップボードにコピーしたC言語のコードをclangでコンパイルして実行し，実行結果をクリップボードにコピー（してWord/LaTeXなどで利用）。

pbpaste | clang -x c -; ./a.out | pbcopy

例：（Webブラウザ上で）クリップボードにコピーしたPico-Cのコードをpicocとclangでコンパイル。

pbpaste \
| ./picoc \
| clang -Wno-override-module -x ir - -O2

例：example/fib.pcをpicocでコンパイルし，その出力したLLVM中間言語をクリップボードにコピー（してワードやLaTeXで利用）。

cat example/fib.pc | ./picoc | pbcopy

例：（Webブラウザ等から）クリップボードにコピーしたコマンド行をターミナルで実行

pbrun 

例：最後に実行したコマンド行をクリップボードにコピー

echo "!!" | pbcopy

例：最後に実行したclangで始まるコマンド行をクリップボードにコピー

echo "!clang" | pbcopy