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

関数型言語 SML#における 64 ビット対応への取り組み
逢坂 美冬

佐々木 智啓Charles Mejia Cruz

上野 雄大

大堀 淳

本稿では，SML#コンパイラにおける x86 64 プラットフォームへの対応について報告する．SML#は，StandardML を包摂し，C とのシームレスな連携などの実用機能を備えた関数型言語である．これまでの SML#は，32 ビットの x86 プラットフォームをターゲットとして開発が続けられてきた．一方，近年，主要な計算機のアーキテクチャは 32 ビットから 64 ビットへ急速に変移している．SML#が実用言語であり続けるためには，64 ビットへの対応は必須の課題である．現在の SML#は LLVM バックエンドを有しているものの，SML#コンパイラはフロントエンドでポインタサイズに依存したコンパイルを行うため，LLVM のターゲットプラットフォームを切り替えるだけでは，この対応は不十分である．本稿では，この課題に対する SML#コンパイラへの変更，および 64 ビット
SML#コンパイラのテスト状況の概要を報告する．

る．言語がいかに優れている場合においても，それを1 はじめに使いこなせるプラットフォームが無く，その結果ユー最先端のプログラミング言語を最先端たらしめるた

ザーを失うならば，その言語に未来はない．

めには，最先端のコード生成器が必須である．計算機東北大学で開発を進めている関数型言語 SML# [5]アーキテクチャやオペレーティングシステムは日々急においても，この状況は深刻である．SML#は C と速に進歩しており，その進歩に合わせてコンパイラをの高水準な相互運用や SQL のシームレスな統合など維持および開発し続けなければ，プログラミング言語の先進的かつ実用的な言語機能を有する次世代のプは急速に陳腐化するからである．コンパイラ開発者かログラミング言語であり，産学連携研究におけるソフら見て最近起こった最も大きな転換のひとつは，PC

トウェア開発事例の成功 [4] などを通じて，その有用市場における 32 ビットアーキテクチャから 64 ビット性は高く評価されている．その一方で，その先進的機アーキテクチャへの移行である．多くの 64 ビットオ能のサポートのため，2.0 版以前の SML#コンパイラ

ペレーティングシステムでは 32 ビットコードへの後は，x86 プラットフォームのみをターゲットとする独方互換性がサポートされているものの，システムのパ自のコード生成器をコンパイラバックエンドに実装フォーマンスを最大限に引き出すためには 64 ビットしていた．この設計のままでは，SML#コンパイラコードが必須である．また，64 ビットオペレーティを 64 ビットコードに移行するためには，既存の x86ングシステムへの 32 ビット開発環境の導入には非常バックエンドを置き換え，新たに x86 64 バックエンに煩雑な作業が必要であり，32 ビットコードのみをドを実装し直すことが必要である．しかし，そのようサポートするコンパイラの導入障壁は日々高まっていなバックエンドの開発には，最新のプラットフォーム

本研究は JSPS 科研費 24700021, 25280019 の助成を受けたものです．

Developing a 64-bit Version of SML# Compiler
Mifuyu Osaka, Tomohiro Sasaki, Charles Mejia Cruz,
Katsuhiro Ueno, Atsushi Ohori, 東北大学, Tohoku
University.

やコード生成技術に関する専門知識はもとより，莫大な開発リソースが必要であり，この方針は全く現実的ではない．
この問題に対する理想的な解決策のひとつは，言語とは独立に活発に開発が続けられているような，マルチターゲットコンパイラ基盤を採用することであの一つは，C 言語とのシームレスな相互運用である．

る．最近では LLVM [2] が，C 言語とその派生言語，SML#プログラムは，この C との相互運用機構を通Java，Ruby，Python，Lua などの手続き型言語のコじて，データ変換などのオーバーヘッドを払うことなンパイラ基盤として注目を集めている．LLVM を採く，C 関数を呼び出すことができる．

用することにより，コンパイラは，ほぼ全ての主要なこの機構を実現するために，SML#では，C 関数

ターゲットプラットフォームに対する，最新の最適化と相互運用可能な全てのデータ型について，C 言語と技術が反映されたコード生成器を，将来にわたって手同等の内部表現を採用している．例えば，32 ビットに入れることができる．

マシンでは，SML#の int 型の値はメモリ上で 4 バ

SML#コンパイラ開発チームは，コンパイラ全体イト（32 ビット），real 型の値は 8 バイト（64 ビッの設計を見直すことにより，既存の独自バックエント）の大きさを持つ．また，SML#の組型の表現は Cドから LLVM バックエンドへの移行に成功した [6]．の構造体へのポインタ型と互換の表現を持ち，組の各LLVM を利用した SML#コンパイラは，SML# 2.0.0

フィールドは，構造体のメンバと同様に整列される．

版として，BSD ライセンスのオープンソースソフト

例えば，int 型の 2 つ組はヒープ中で 8 バイト，realウェアとして公開されている．ただし，2.0.0 版はそ型の 2 つ組は 16 バイトの大きさを持つ．組型の値はれ以前の版と同様に，x86 プラットフォームのみをポインタであり，32 ビットアーキテクチャでは 4 バターゲットとする．これは，たとえ x86 64 コード生イト，64 ビットアーキテクチャでは 8 バイトとなる．

成器を手に入れたとしても，SML#の 64 ビット化のこの C と同等の内部表現を実現するために，ためには，コンパイラフロントエンドの変更，自動メ

SML#コンパイラは，C 言語のコンパイラと同様モリ管理や例外処理を含むランタイムライブラリでに，各型のデータのサイズを計算する．データのサの新プラットフォームへの対応，基本ライブラリの変イズは，ターゲットプラットフォームに依存して決ま更など，言語処理系全体での包括的なサポートが必要る．従って，SML#コンパイラは，コード生成以外にだからである．また，このような大域的な変更を加えもターゲットプラットフォームに依存するコンパイルたならば，システム全体の品質を保つため，網羅的なを行っている．SML#コンパイラでは，このようなテストも必須である．

ターゲットに依存するコンパイルをビットマップコン

著者らは，これら課題への対応を検討し，SML#コパイル [3] フェーズで集約して行う．

ンパイラの 64 ビット化への改良を進めている．本稿

2.0.0 版の SML#コンパイラは，構文解析，型推論，では，その開発の詳細について報告する．本稿で報告

型主導コンパイル，ビットマップコンパイルなど，ラする 64 ビット SML#は，近い将来，2.1 版として公ムダ計算に由来する構造の中間表現を扱うコンパイル開する予定である．

フェーズからなるコンパイラフロントエンドと，ター

本稿の構成は以下の通りである．2 節では，SML#言ゲットプラットフォームのマシンコードを生成するコ語および 2.0.0 版 SML#コンパイラの内部構造につンパイラバックエンドからなる．このうち，コンパイ

いて概説し，64 ビット化のために克服すべき課題をラバックエンドの大部分は LLVM をそのまま利用し述べる．3 節では，それら課題に対する具体的な対応ている．LLVM に渡すターゲットプラットフォーム

方針と，その実施状況について詳述する．4 節では，指示文字列（ターゲットトリプル）を切り替えるこより品質の高いマルチターゲット SML#コンパイラとにより，コンパイラバックエンドは，様々なプラッの開発に向けた課題を議論する．5 節で結論を述べる．

トフォームへのコードの生成に対応する．一方，コンパイラフロントエンドは，ターゲットプラットフォー

2 64 ビット SML#の開発方針

ムに依存するビットマップコンパイルを含むものの，SML#は Standard ML を実用上必須の言語機能でターゲットを切り替える機能を持たない．切り替えに拡張した関数型プログラミング言語である．その特徴

は，ハードコードされたサイズ情報をソースコードを編集して変更する必要がある．すなわち，64 ビットを進める．

対応のためには，少なくとも，ポインタ型のサイズに1. フロントエンドでのデータサイズ計算における関する情報を，4 バイトから 8 バイトに変更する必要

ポインタサイズをコンパイラのソースコードをがある．

編集して変更する．

SML#コンパイラが出力するコードは，ごみ集め

2. ランタイムライブラリのソースコードをレビューを含む自動的なメモリ管理などのサポートがあることし，ポインタサイズに依存するアドレス計算，おを仮定している．これらのサポートを提供するのが，よびターゲットプラットフォームに依存する箇所

SML#ランタイムライブラリである．コンパイラとの変更を検討する．

同様に，ランタイムライブラリにおいても 64 ビット

3. 基本ライブラリの単体テスト，および SML#コ対応が必要となる．例えば，このメモリ管理機構はメンパイラ全体の動作確認を行い，システム全体モリイメージを操作するためにアドレス計算を多用の変更によって問題が生じていないことを確認する．このアドレス計算の多くは，ヒープ中に存在すする．

るポインタのアドレスを得るために，ポインタサイズに依存して行われる．従って，ランタイムライブラリ

3 64 ビット対応 SML#の開発においても，ポインタサイズに依存する箇所を洗い

我々は ，前 節 の 方 針 に 基 づ き ，64 ビット 対 応出す必要がある．ごみ集め以外にも，ランタイムライ

SML#の開発を進めている．本節では，その詳細

ブラリには例外処理などの OS が提供するサービスを報告する．開発のおおよその流れは以下の通りでに依存する低レベルなサポートを要するものがある．

ある．まず，x86 版 SML#コンパイラを改造し，x86ターゲットプラットフォームに応じて，これらも再検プラットフォームで動作し x86 64 向けの LLVM IR討する必要がある．

コードを出力する SML#コンパイラを構築する．次基本ライブラリの実装においても，64 ビット対応に，ランタイムも同様に，x86 版ランタイムライブラが必要である．基本ライブラリは，整数の四則演算

リを変更して x86 64 プラットフォームに対応したランや配列などの基本的なデータ構造とその操作関数をタイムライブラリを構築する．そして，これら x86 64ユーザーに提供するライブラリである．基本ライブラ

対応コンパイラとランタイムを用いて，SML#コンパ

リは，その性質上，高度に最適化されている必要があ

イラを構成するモジュールをひとつずつコンパイルし，る．2.0.0 版の SML#における基本ライブラリの実装テストプログラムとリンクし，x86 64 版 SML#のテは，32 ビットアーキテクチャを仮定して最適化されストを行う．最終的には，ブートストラップを完了た実装を含む．これらの実装についても，64 ビットし，x86 64 プラットフォーム上で動作する 64 ビット対応のための検討が必要である．

SML#コンパイラを完成させることを目指す．以下，上述した変更は SML#システム全体にわたる変更

それぞれの項目ごとに節を分けて報告する．

であり，網羅的なテストが必要である．網羅的なテストを行うためのひとつの戦略は，基本ライブラリの3. 1 コンパイラの 64 ビット対応モジュールごとの単体テストである．基本ライブラリ

前節で述べたように，SML#コンパイラフロントのモジュールには，簡潔なものから複雑な構造を持つエンドはターゲットプラットフォームにおける実行ものまで，様々な規模のモジュールがあるため，単体時データのサイズと配置情報を必要とする．SML#

テストは SML#システム全体の様々な機能のテスト

2.0.0 版では，この情報はひとつのモジュールに集約にもなる．もうひとつの戦略は，最終目的である 64されており，コンパイラのソースコードの中に実行時ビット SML#コンパイラ全体が正しく動作すること型とサイズのテーブルとしてハードコードされていを確認することである．

る．このテーブルを適切に書き換えれば，SML#コ以上の検討から，我々は以下の方針で 64 ビット化

ンパイラは x86 64 プラットフォームにおいて適切な実行時データ表現を計算するはずである．

ンタイムライブラリを改良した．x86 および x86 64

本開発では，LP64 規約，すなわち int 型は 32 ビップラットフォームの類似性のため，この改良は，ポイトおよびポインタ型は 64 ビットとする規約を仮定し，ンタ演算におけるポインタ型の取り扱いを見直すこと

SML#コンパイラの実行時サイズテーブルを変更しで完了した．具体的には，ポインタ演算式における定た．具体的には，このテーブルのうち，ポインタ型数はすべて sizeof 演算子で与えるように，整数型とのサイズを 4 バイト（32 ビット）から 8 バイト（64ポインタ型の相互変換が必要な箇所は，uintptr_t 型ビット）に変更した．データの配置制約は，SML#コと void*型の間のキャストを用いるように変更した．

ンパイラにすでに実装されている制約をそのまま採用した．この制約は，各データをそのデータのサイズ3. 3 ブートストラップの倍数のアドレスに配置するものである．以上の規約

SML#コンパイラは SML#で書かれている．新たは，Unix 系オペレーティングシステムで標準的に採なプラットフォーム上で SML#コンパイラ自体を起用されているものであり，試験的実装として適切な選動するためには，対応済みのプラットフォーム上から択である．より広範囲なプラットフォームへの対応は始めて段階的な手続きを経る必要がある．

4 節で議論する．
以上のフロントエンドへの変更に加え，バックエンドでは，x86 64 コードを出力するように LLVM のオ

本開発では，最終目的である x86 64 プラットフォー
ム上で動作する 64 ビット SML#コンパイラを以下の手順で構成した．

プションを変更した．この変更は，LLVM の API に

1. x86 版 SML#コンパイラをそのままビルドす受け渡すターゲットトリプルを変更するだけで完了

る．以下，このコンパイラをステージ 0 コンパイした．

ラと呼ぶ．ステージ 0 コンパイラは，x86 プラットフォームで動作し，x86 コードを生成する．

3. 2 ランタイムの 64 ビット対応

2. 3. 1 節の変更を加えた SML#コンパイラを，ス

SML#ランタイムライブラリは，ごみ集めを含むテージ 0 コンパイラでコンパイルする．以下，こ自動的なメモリ管理モジュール，マルチスレッド機のコンパイラをステージ 1 コンパイラと呼ぶ．ス

能，コールスタックの巻き戻しのサポートなどを含

テージ 1 コンパイラは，x86 プラットフォームでむ，C で書かれたライブラリである．これらの機能動作し，x86 64 コードを生成する．

は，バイト単位でのポインタ操作や低レベルな API

3. 3. 2 節の改良を加えたランタイムライブラリをの使用など，プラットフォームに依存するシステムプ

x86 64 版 C コンパイラでコンパイルする．以下，ログラミングによって実装されている．そのため，対このライブラリを 64 ビットランタイムと呼ぶ．

応するターゲットプラットフォームに応じて，ランタ

4. 3. 1 節の変更を加えた SML#コンパイラを構成

イムライブラリを書き換えなければならない．一方，する各モジュールをそれぞれ，ステージ 1 コン

C 言語は移植性の高いシステムプログラミング言語

パイラで x86 64 コードのオブジェクトファイルであるから，マクロなどを用いて適切に設計すれば，に分割コンパイルする．

プラットフォームに依存する箇所を最小限にし，単一

5. 64 ビットランタイム，全てのオブジェクトファのコードベースで複数のプラットフォームに対応可能

イル，および LLVM などのコンパイラが要求すとなるはずである．

る外部ライブラリを，システムリンカを用いて本開発では，コードレビューおよび後述するテスト実行形式ファイルにリンクする．この実行形式

ケースの実行をデバッガでトレースすることにより，ファイルが，x86 64 プラットフォームで動作しランタイムライブラリのうち x86 プラットフォーム

x86 64 コードを生成する SML#コンパイラであを仮定して書かれている箇所を洗い出し，x86 およびる．以下，このコンパイラをステージ 2 コンパイx86 64 プラットフォームの両方に対応するようにララと呼ぶ．

我々はこれらの手順を x86 64 版の Linux システムをfun test1_getOpt () =用いて実行した．x86 64 システムは，x86 コードへ

case Option.getOpt (SOME 1, 2) ofの後方互換性を持つため，単一の計算機を用いて以

1 => puts "test1_getOpt passed"

上の手順を実行することができる．ただし，システム| _ => puts "test1_getOpt failed"が標準で提供する 64 ビット開発環境に加え，32 ビット開発環境が必要である．

fun test2_getOpt () =case Option.getOpt (NONE, 2) of

3. 4 テスト
多くの問題をより迅速に特定するために，SML#コ

2 => puts "test2_getOpt passed"| _ => puts "test2_getOpt failed"

ンパイラ全体のテストに先立って，簡単なテストプログラムを用いて基本ライブラリの各モジュールの単体

val _ = test1_getOpt ()テストを行った．モジュール単体テストは，エラーがval _ = test2_getOpt ()発生した段階の特定を容易にするため，他のモジュー

図1

Option ストラクチャのテストケース（一部）

ルへの依存関係が低い順番にテストを行う．
テストケースは，SML 基本ライブラリの仕様 [1]で行っている．このビルドが正常に終了し，得られを参照し，本開発のために書き下ろした．例として，

た SML#コンパイラコマンドのファイル内容が，スOption ストラクチャに関するテストケースを図 1 にテージ 2 コンパイラコマンドのファイル内容と一致示す．最小の依存関係でテストを実行するため，テするならば，このテストは完了である．本稿執筆時点

ストケースは，テスト対象以外の基本ライブラリモ

では，ステージ 2 コンパイラのビルドに成功しておジュールを使用せずに，コンパイラが直接提供するプらず，現在デバッグ作業を続けている．

リミティブのみを用いて実装した．テストプログラム
は，各テストケースを実行し，テストの合否を標準出力にプリントする．このプリントは，SML#の外部4 マルチターゲットコンパイラの実現に向けて関数インターフェースを通じて C 言語の puts 関数

これまでに報告した 64 ビット SML#の開発は，32を呼び出すことで行った．このテストの実行には，スビットコードのみに対応する SML#をベースに，新テージ 1 コンパイラおよび 64 ビットランタイムを使たに 64 ビットコードのみに対応する SML#コンパ用し，3. 3 節に示した手順 4 および 5 と同様にしてテイラを構築するものである．一方，PC 市場においてストプログラムをコンパイルおよびリンクすることは主要なプラットフォームが x86 から x86 64 に転換によって行った．

したとはいえ，x86 コードの必要性が失われたわけで我々はこのテストを，入出力処理を行うものを除くはない．また，組み込み分野では，ARM などの 32全ての必須ストラクチャに対して行い，テストが正ビット CPU がいまだ主流である．プログラミング言常に動作することを確認した．この過程において我々語の利用可能性を最大化するためには，単一のソースは，SML#の 64 ビット対応とは無関係のバグをいくコードベースで，これらあらゆる主要プラットフォーつか発見し修正した．本開発で実装したテストプログ

ムに対するサポートを備えた，マルチターゲットコラムは，基本ライブラリのテストケースとして再利用ンパイラの開発が肝心である．本節では，64 ビットする予定である．

SML#の開発を通じて得た知見に基づき，SML#コ単体テストに加えて，SML#コンパイラ全体の動作を確認するため，ステージ 2 コンパイラのテストンパイラをマルチターゲットコンパイラとするための今後の展望について述べる．

を行っている．このテストは，ステージ 2 コンパイ

本稿で報告した SML#コンパイラがマルチターゲッラを用いて SML#コンパイラ自体をビルドすることトコンパイラではない要因のひとつは，3. 1 節で述べたように，データサイズなどターゲットに依存する情報が，単一のテーブルとして，コンパイラフロントエ

5 まとめンドにハードコードされていることにある．この問題

本稿では，SML#の 64 ビット対応におけるコンパに対する対応策のひとつは，このテーブルを抽象化イラの変更とテスト状況の概要を報告した．SML#コし，バックエンドのターゲット選択に合わせて，このンパイラの変更においてはフロントエンドの変更，テーブルを切り替えるようにすることである．LLVMバックエンドの再実装が課題であった．フロントエには，この方針でフロントエンドをマルチターゲット

ンドの変更はソースコードの変更により解決した．

化するための機構がすでに備わっている．従って，フバックエンドの再実装はコンパイラの設計を見直しロントエンドを，この機構を通じてターゲット情報をLLVM バックエンドに移行することにより解決した．

取得するように改良すれば，この問題を解消すること

本稿で報告した 64 ビット SML#は近い将来，2.1ができると考えられる．
ランタイムライブラリは，本開発によって 32 ビット/64 ビットの両方に対応するための改良が完了した版として公開する予定である．
謝辞 本開発プロジェクトの初期段階において開発に協力を頂いた百足勇人氏に感謝する．

ものの，例えば ARM などの，Intel 系 CPU 以外のプラットフォームへの対応はしていない．この対応の参 考 文 献ためには，システムスタックの拡張方向やスタック[1] Gansner, E. and Reppy, J.: The Standard ML
Basis Library, Cambridge University Press, 2004.
[2] Lattner, C. and Adve, V.: LLVM: A Compilation Framework for Lifelong Program Analysis &Transformation, Proceedings of the 2004 International Symposium on Code Generation and Optimization (CGO’04), Mar 2004, pp. 75–88.
[3] 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,ACM, 2006, pp. 237–248.
[4] Ohori, A., Ueno, K., Hoshi, K., Nozaki, S., Sato,T., Makabe, T., and Ito, Y.: SML# in Industry:A Practical ERP System Development, Proceedingsof the 19th ACM SIGPLAN International Conference on Functional Programming, ICFP ’14, 2014.
to appear.
[5] SML# Compiler, http://www.pllab.riec.tohoku.ac.jp/smlsharp/[6] Ueno, K. and Ohori, A.: Compiling SML# with
LLVM: a Challenge of Implementing ML on aCommon Compiler Infrastructure, ACM SIGPLAN
Workshop on ML, 2014. to appear.

巻き戻し機構など，プラットフォームごとに異なるABI を調査し，実装する必要がある．
基本ライブラリの実装にも，現時点では int 型が32 ビットであることに依存するコードが存在する．
整数型の値の大きさを仮定することで，一部のライブラリ関数を最適化して実装している．そのため，整数が 64 ビットであるようなプラットフォームへの対応は，現在のコードベースのままでは難しい．この問題に対応し，かつメンテナンス可能なソースコードの構造を維持するためのひとつの案は，ターゲットプラットフォームの選択に応じて基本ライブラリの実装の一部を切り替えることができる言語機能，あるいは選択的なコンパイル機構の導入である．この機構の実現のためには，C 言語のプリプロセッサが提供する機能などが参考になると思われる．