日本ソフトウェア科学会第 37 回大会 (2020 年度) 講演論文集

自然なデータ表現を持つ多相型言語のLLVM IR へのコンパイル方式 †上野 雄大
本論文では，SML# コンパイラのマシンコード生成方式の現状および新たな構想について述べる．SML# は，Standard ML を包摂しながら，マシンネイティブなデータ表現，正確なごみ集め（GC），および分割コンパイルを採用する関数型言語である．これらの特徴を実現する上での実装上の主要な課題は，多相関数を多相的な性質を持つマシンコードにコンパイルすることにある．型主導コンパイルに基づくビットマップコンパイルの理論はこの課題を解決する基礎を与えているが，実装技術についてはスタックフレームを巧みに制御することを示唆するに留まっており，その実装はコード生成器とコンパイラフロントエンドの強い結合を招き，LLVM など最先端のコンパイラ基盤の利用を難しくする．本論文では，SML# コンパイラ開発におけるこの課題へのこれまでの取り組みを報告した後，これまでのアプローチが抱える問題点を挙げ，それらを克服する新たなコンパイル方式について述べる．

べースサーバーやマルチスレッドライブラリなどと連

1 はじめに携を取り，それらとのシームレスな統合を実現するた

SML# [3] は，Standard ML を包摂しながら，C 言めに表層言語を拡張しランタイムライブラリを整備

語との高度な連携機構，SQL データベースとの統合，したものが，今日の SML# のおおよその構造である．

マルチスレッドサポート，分割コンパイルとシステム

多相型関数型言語において自然なデータ表現を実リンカによるリンク，正確でオブジェクトを移動しな現する鍵となった技術は，型注釈から実行コードを生い並行ごみ集め（GC）などの先進的機能を持つ関数成する型主導コンパイル [2] に基づくビットマップコ型言語である．これら SML# の機能の大半は，マシンパイル [1] である．自然なデータ表現を採用する多ンネイティブな（自然な）データ表現を基盤として構相型言語では，プログラムが取り扱うデータのレイア築されている．自然なデータ表現とは，例えば整数ウトは必ずしも静的に決まらない．例えば，関数やポインタの一部のビットをタグ等の特別な用途にfun α dup (x : α) = (x, x)使用したり，処理系の都合でデータサイズを統一したが作る組のレイアウトは，束縛型変数 α のインスタりしない，C 言語と同様の，CPU が直接サポートすンスに依存して動的に決まる．また，正確な GC のるデータ表現のことである．自然なデータ表現の採ためには，x の値が GC でトレースすべきポインタで用によって，SML# でない言語で書かれた様々なライあるかどうかを管理することも必要である．型主導

ブラリを SML# から直接利用し，システム共通のオコンパイルは，このようなインスタンスに依存するブジェクトファイル形式を通じてそれらライブラリを処理を，型抽象を関数抽象に，型適用を関数適用にコSML# プログラムに直接リンクすることが可能となっンパイルすることでコード化する．ビットマップコン

た．このシステムとの直接連携を核として，データパイルの結果，dup は以下のラムダ式にコンパイルさ

Katsuhiro Ueno, 東北大学, Tohoku University.
† 本稿は，第 22 回プログラミングおよびプログラミン
グ言語ワークショップ（PPL 2020）で発表された論文「自然なデータ表現を持つ多相型言語の LLVM IR へのコンパイル方式」の要約である．

れる．

dup = Λα. λS : size(α). λT : tag(α). λx : α.
⟨⟨(x, x) をアロケートするコード ⟩⟩ここで，S および T はインスタンスのサイズ（値のバイト数）およびポインタかどうかを表すタグをそれ「α 型の変数」に相当する汎用のストレージとみなし，ぞれ受け取るための追加の引数である．関数本体は，型主導コンパイルで受け渡される情報を用いてレジス

S から組のバイト数と第 2 要素のオフセットを計算

タの組からレジスタを選択するレジスタ選択方式であし，その大きさのメモリを確保し，そのオフセットにる．このうち第三の方式は SML# コンパイラに実装

x の値をストアし，タグをメタ情報（ビットマップ）されていない方式であり，本論文の執筆時点においてとしてそのメモリに付与するコードである．

はあくまで構想の段階にある．その他の方式は過去にビットマップコンパイルは，自然なデータ表現を実SML# コンパイラに実装され評価された方式である．

現する基礎をラムダ計算上の変換として与えていると言える．その一方で，ビットマップコンパイル後の2 フレームビットマップ方式

ラムダ式の操作的意味（自然意味論）をマシンコード

文献 [1] では，この問題に対し，全ての一時変数をで実装する方法については，十分な検討がなされていスタックフレームに割り当てる仮想機械に対して限定ない．ラムダ計算の自然意味論とマシンコードの最大的な解決策を与えている．その概要は以下の通りであの相違点は，ラムダ計算の自然意味論では任意の型る．まず，一時変数の型を，ポインタを表す boxed，の値を式の評価結果や関数の引数および返り値にすポインタでないデータを総称する unboxed，およびることができるのに対し，マシンコードでは途中のそのどちらかが型変数 t1 , . . . , tn のインスタンスに応

計算結果や関数の引数，返り値の型が静的に決まってじて実行時に現れることを表す型 t1 , . . . , tn に限定すいなければならないことである．例えば，前述の dup

る．次に，一時変数の生存区間解析を型ごとに行い，関数の引数 x は，ラムダ計算上では α 型を持ち，意コードの実行に必要な最小のフレームサイズを計算

味論上では，32 ビット整数，64 ビット浮動小数点数，し，フレームレイアウトを決定する．最後に，組に対ヒープにアロケートされたデータへのポインタなど，するメタ情報と同様に，決定されたフレームレイアウ

様々な大きさや表現を持つ任意の型の値に束縛されトに対してスタックフレームのビットマップを計算す得る．コンパイラはこの意味をマシンコードで表現る．スタックフレーム中の t1 , . . . , tn 型を持つ領域にしなければならない．しかし，このように多様な値対しては，動的に受け渡されたタグ T1 , . . . , Tn からを取りつつ正確な GC もサポートする「α 型の変数」ビットマップを計算するコードを出力する．に相当するレジスタはマシンコードには存在しない．

この方式を実現する上での最大の困難はフレーム自然な表現を持ちながら「α 型の変数」に相当する多ビットマップの管理である．フレームビットマップは相性を有するストレージをマシンコードで効率の良い動的に計算されるメタ情報であり，その計算にはコ形で表現できなければ，たとえビットマップコンパインパイラフロントエンドが行う型主導コンパイルと，ルを装備していたとしても，自然なデータ表現を装備コード生成器が生成するフレームレイアウトの連携した実用的なコンパイラを実現することはできない．

が不可欠である．このため，コンパイルフェーズ間の本論文では，LLVM IR を対象のマシンコードとし，独立性が失われる．型主導コンパイルとコード生成

SML# コンパイラの開発過程において試みた，あるい器は共に高度に複雑な処理であり，それらを相互依はこれから試みようとしている，「α 型の変数」を実現存させさらに複雑化することは現実的に困難である．

する方式を 3 つ報告する．第一の方式は，ビットマッまた，フレームビットマップのように実行時に計算さプコンパイルと共に提案されたフレームビットマップれるメタ情報をスタックフレームに含める仕組みを，方式 [1] である．第二の方式は，多相関数に渡すデー

LLVM などのコンパイラ基盤は一般に提供していな

タをヒープ上にアロケート（boxing）することで多い．SML# コンパイラが自前のネイティブコード生成相性を表現し，boxing されているかどうかの違いを器を有していた 1.2.0 版までは SML# コンパイラは動的な条件判定で吸収する呼び出し規約方式である．

この方式で実装されていたが，コンパイラコードの管第三の方式は，性質の異なる複数のレジスタの組を理コストと生成コードの品質の観点から LLVM の利用を検討したとき，フレームビットマップ方式は実現ロケートされている（boxing されている）ことを，u不可能と判断された．

および r は boxing されていない 32 ビット整数および64 ビット浮動小数点数をそれぞれ表す．λk1 k2 x:τ.M

3 呼び出し規約コンパイル方式

は，引数の受け方に関する規約を k1 ，返り値の渡し

LLVM IR で多相関数を実装する方式を検討するに方に関する規約を k2 とする関数である．M1k1 k2 M2あたり最初に採用した想定は，最も汎用なデータストは，引数の渡し方に関する規約を k1 ，返り値の受けレージはメモリであり，従ってコードの多相性はポイ方に関する規約を k2 とする関数呼び出し式である．

ンタを介して表現するのが自然であろう，ということ

呼び出し規約注釈のないラムダ計算から呼び出しである．例えば，多相的な dup 関数の場合，規約注釈付きラムダ計算への変換は，各部分式の型とfun α dup (x : α) = (x, x)整合するように規約を選択することで行われる．例

この x は α のインスタンスに依らず常にポインタとしえば，整数型には規約 b（boxing された整数）またて実装する．この関数を整数 n に適用した場合，dupは u（boxing されていない整数）が整合し，浮動小を呼ぶ前に n はヒープにアロケート（boxing）され，数点型には b または r が整合する．関数型や組型なそのポインタが dup に渡されるとする．多相性はポどヒープにアロケートされるデータ型には b のみがインタを介して表現されるから，コードに現れる全て整合する．の一時変数の型は静的に定まる．以下，本節では，引呼び出し規約コンパイルによって，λk1 k2 x:τ.M は数や返り値が boxing されていなければならないかど

注釈付きのクロージャを生成するコードに，M1k1 k2 M2うかを関数ごとに定める規約を呼び出し規約と呼ぶ．

は自身の注釈とクロージャの注釈を比較して分岐する

多相関数をこのように実装する一方で，単相関数はコードにそれぞれコンパイルされる．この分岐には，可能な限り boxing しない方式で実装したい．そのた全ての注釈の組み合わせを網羅する数の分岐先が必めには，呼び出し元から呼び出し先の関数が多相関数要である．すなわち，もし m 個の組み込み型と n 引であるかどうかを何らかの方法で判断する必要があ数の関数が存在するならば，最大で (m + 1)n+1 通りる．しかし，多相型言語の場合，多相関数に対する型の分岐が必要となる．この指数オーダーの分岐コー適用が存在するため，この判断を静的に行うことは一ド生成を避けるため，SML# コンパイラでは，関数般に難しい．の型から定まる最も自然（speciﬁc）な規約と最も一

この問題をビットマップコンパイルとは独立に解決般的（generic）な規約 bb にのみ着目した．関数クするため，SML# コンパイラでは，呼び出し先の関数

ロージャは，最も自然な規約で呼び出される関数本が boxing を必要とする関数かどうかを実行時に判定体と，最も一般的な規約で呼び出されるラッパーの 2し呼び出し規約を変換する方針を取った．この判定のつのコードを持つ．関数呼び出し側では，クロージャために，関数クロージャに呼び出し規約を表すフラグの持つ最も自然な規約が呼び出し側の規約と一致してを追加する．各呼び出し元において，このフラグを参いる場合，最も自然な規約を用いて関数を呼び出す．

照して呼び出し規約を判定し boxing や unboxing をそうでなければ，最も一般的な規約を用いる．

行う条件分岐コードを生成する．このコード生成を行

本方式は SML# 2.0.0 版から採用されており，SML#

うコンパイルフェーズを呼び出し規約コンパイルとコンパイラ自身を含む多くの動作実績を持つ．それ呼ぶ．

ら動作実績を通じて，動的な呼び出し規約の判定や呼び出し規約が注釈として付加されたラムダ計算

boxing によって極端なオーバーヘッドは発生しないことは確認されている．その一方で，本方式の弱点もを考える．

M::=c | x | λ x:τ.M | M

k::=b|u|rkkkk

M | ···

k は呼び出し規約を表す注釈であり，b はヒープにアいくつか見つかっている．第一の弱点は，多相性を取り除く最適化を進めるたびに分岐の数が増えることである．例えば以下の関数を考える．

fun apply f x = f x

するレジスタの種類が限定され，その結果 LLVM IR

関数適用式 f x は，その最も自然な規約が最も一般での実装が可能となる．そこで，全ての種類のレジス的な規約であることから，最も一般的な規約で f を呼タを使うように多相関数を実装しておき，そのうちのび出す分岐のないコードにコンパイルされる．一方，ひとつを実行時に選択できるならば，多相関数の個々プログラムの最適化を進めた結果，f には int → intのインスタンスと同じ振る舞いをする単一のコード型の関数しか来ないことがわかり，以下のように型注が実現できるはずである．この選択は，ビットマップ釈を付けて多相性を除去したとしよう．

コンパイルで受け渡される情報を利用することで実

fun apply (f : int -> int) x = f x

現できる．汎用のストレージをレジスタで実現できる

すると，関数適用式 f x の規約は uu となるため，規ならば，呼び出し規約方式のように boxing を行う必約を動的に判定する条件分岐コードが現れる．もし f要はなく，従って boxing に由来する一切のオーバーに単相関数しか来ない場合，この分岐コードは無駄ヘッドは原理的に生じない．になり，一般的な規約で呼び出す側のコードはデッド

この方針を素直に実装した場合，関数呼び出し時コードとなる．ゆえに，多相性を除去することが分岐は，関数の型に依らず，レジスタの組を用いて引数とやデッドコードが増える要因となる．

返り値を受け渡すことになる．例えば，整数に 1 を第二の弱点は，多相性を伴わないはずの関数呼び出足す関数

fun inc x = x + 1

しでも boxing が発生し得ることである．例として以下の関数を考える．

fun fact 0 k = k 1| fact n k = fact (n-1) (fn z => k (z*n))は整数しか操作しないが，以下のようなコードにコンパイルすることになる．

define fastcc {i32, double, i8*}@inc(i32 %a, double %b, i8* %c) {この関数の型は ∀α. int → (int → α) → α である．継続 k の型は int → α であるから，k 1 および k (z*n)%d = add i32 %a, 1は最も一般的な規約で k を呼ぶことになる．従って，%r = insertvalue {i32, double, i8*} undef,継続が呼ばれるたびに整数の boxing と unboxing がi32 %d, 0行われる．計算の途中で作られる全ての継続の呼び出

ret {i32, double, i8*} %r

しで boxing を行うのは効率が悪く，またプログラマ}の直感にも反する．

LLVM IR コードは複雑になるものの，引数および返り値が caller-save レジスタを介して受け渡しされる

4 レジスタ選択方式

ならば，undef に関する最適化により，不要なレジス次期 SML# コンパイラに向けて，上述のような弱タ操作を含まない最適なマシンコードがこの LLVM

点を持つ呼び出し規約方式に代わる，「α 型の変数」を構成する別のアプローチを検討している．本節ではその構想を述べる．

IR コードから生成されるはずである．
引数および返り値の受け渡し方の更なる最適化として，レジスタの組を大きなレジスタ（例えば i64 型新たな実装方式を展開するにあたっての洞察は，全のレジスタ）1 つに集約する方法が考えられる．引数てのインスタンスを実装するために必要なレジスタを渡す際は，引数の値を持つレジスタから引数の受け全てを組にしたものを汎用のストレージとして利用渡しのために一時的に用いるレジスタに値をコピーすすることである．多相関数の実装に必要な汎用のストる．返り値を受け取る際もレジスタ間コピーを行う．

レージは LLVM IR には存在しないが，その一方で，この方法の利点は，LLVM による最適化を頼らなく多相関数の個々のインスタンスを静的に決めたならても最も少ない数のレジスタだけを使用した関数呼ば，多相関数のインスタンスの決定によって値を保持び出しコードを実現できることである．例えば前述のinc 関数は以下のコードにコンパイルされる．

define fastcc i64 @inc(i64 %x) {を選択することになると思われる．どちらの場合でも%a = bitcast i64 %x to i32

LLVM IR での関数の型を変える変更となり，しかも%b = add i32 %a, 1この変更は ZMM レジスタを用いない関数に対して%c = bitcast i32 %b to i64
ret i64 %c}
この方式には，呼び出し規約コンパイル方式にあっも適用されなければならない．これは，オブジェクトファイルの互換性を失う変更になると考えられる．

5 まとめたような弱点は無い．分岐コードはレジスタ選択コー

型主導コンパイル後のラムダ式を LLVM IR コー

ドでしか生成されず，またそれらのコードが生成されドにコンパイルする方式として，フレームビットマッるのは多相関数内に限られる．そのため，多相性を除プ方式，呼び出し規約コンパイル方式，およびレジス去する最適化によりコードが増えることはない．まタ選択方式の 3 つを紹介し，SML# コンパイラに実た，引数と返り値は多相関数においてもレジスタを介装した上での評価を述べた．マシンコードへのコンして受け渡され，関数呼び出し時に boxing が行われパイルする上での課題は，多彩な値を取りつつ正確ることはなく，メモリアクセスと GC の起動回数のな GC をサポートする「α 型の変数」に相当するレ両方が減ることが期待できる．

ジスタがマシンコードに存在しないことである．フ

この方式には 2 つの欠点が考えられる．ひとつは，レームビットマップ方式は全ての一時変数をスタックLLVM IR レベルでの引数および返り値の型が全てフレームに割り付けることでこの課題を解決したが，i64 に固定されるため，浮動小数点数を扱う関数の呼型主導コンパイルフェーズとコード生成器の分離を難

び出しのたびに浮動小数点数レジスタと整数レジスしくするため，LLVM IR コード生成での採用を諦めタの間でのムーブが発生することである．そのため，た．呼び出し規約コンパイル方式は boxing 操作を行浮動小数点レジスタを用いて浮動小数点引数を受けうことでこの課題を解決し，LLVM IR へのコード生渡す C などに比べて，浮動小数点演算を多用するプ成を達成したものの，プログラマの直感に反するコーログラムが遅くなる可能性がある．ただし，少なくとドの増加や boxing のコストがかかり，最適とは言いも呼び出し規約コンパイル方式よりは実行効率の良難い．レジスタ選択方式は構想段階にあり未実装であいコードが生成されるはずである．

るが，前方式の欠点を克服する最適な方式であると期

もうひとつの欠点は，表層言語における関数の型とは無関係に関数の実装型が決定されることである．
このことは，将来の言語拡張による互換性の喪失を待している．
謝辞 本研究の一部は JSPS 科研費 19K11893 の助成を受けたものです．

引き起こす恐れがある．例えば，SIMD 命令で用いるベクトルレジスタの値など，64 ビットよりも大き

参 考 文 献な値を SML# がサポートした場合，i64 に集約する[1] Nguyen, H.-D. and Ohori, A.: Compiling ML
Polymorphism with Explicit Layout Bitmap, Proceedings of the 8th ACM SIGPLAN International
Conference on Principles and Practice of Declarative Programming, PPDP 06, New York, NY,USA, Association for Computing Machinery, 2006,
pp. 237–248.
[2] Ohori, A.: A Polymorphic Record Calculus andIts Compilation, ACM Trans. Program. Lang. Syst.,
Vol. 17, No. 6(1995), pp. 844–895.
[3] : SML# Project, http://www.riec.tohoku.ac.
jp/smlsharp/.

最適化が行えなくなる．本論文の執筆時点において

x86 64 アーキテクチャで最大のレジスタは ZMM レジスタであり，その大きさは 512 ビット（64 バイト）である．ZMM レジスタをサポートする場合，わずか32 ビットの整数を受け渡す時も ZMM レジスタを使うようにするか，あるいは i64 レジスタと ZMM レジスタの組を引数の受け渡しに用いるかのどちらか