C-- Mizukami Tatsuo 2001/07/18

コンパイラを書こう！ ⇒時間・人力がとてもかかる 以下の性質がほしいよね 出力コードが最適化されてて、暴速 Intra- inter- procedual register allocation Instruction selection, scheduling Jump elimination, et al どのマシン用にもバイナリが出力できる SPARC, MIPS, Alpha, PowerPC, Pentium … ⇒時間・人力がとてもかかる

解決方法1 中間言語にCを使用する 長所 短所 ほとんどのマシン言語にコンパイル可能 プラットホームに特化した最適化も豊富 そもそも中間言語用として設計されてない GC, tail call, multiple result, …

C code My source code My favoriate Front end SPARC x86 PowerPC Arm MIPS Alpha

解決方法２ 中間言語にJVMLを使用する 長所 短所 write-once, run-anywhere 抽象化レベルが高い Java用にのみ設計されている。 write-once, test-anywhere

JVML My source code My favoriate Front end SPARC x86 PowerPC Arm MIPS Alpha

解決方法３ 新たな中間言語を設計する どのようなソース言語にも対応 どのようなマシン言語も出力可能 従来のコンパイラ技術も使える GC,例外処理にも対応 だから、作ってみました。 「 C-- 」

？ C-- My source code My favoriate Front end SPARC x86 PowerPC Arm MIPS Alpha

誰もが気にする名前の由来 C--は Cのサブセットではない ‘C’は設計の基準となったのが、Cだから では、‘--’は？ より、アセンブラに近いから?　(推論) C++に対抗意識をもった？ (推論)

C--の目標 C--は実装が難しいコンパイラ技術をカプセル化する。ただし、 コード出力はCと同じくらい簡単 最適化はCと同じくらい良い GC, 例外処理のポリシーは利用者が決定

C--の特徴 Portable High-Performance Exploits existing code generator Independent of particular generator Independent of target architecture Inter-operable Human writable, readable

C--とCの差異 ローカル変数はレジスタに割り当て (レジスタは無限) 明示的なメモリアクセス tail call 　(レジスタは無限) 明示的なメモリアクセス tail call multiple result 自由なCalling conventions (指定も可能) その他 (GC, 例外はそのときに説明)

/* Ordinary recursion */ sp1(word4 n) { word4 s, p; if n==1 { return( 1, 1); } else { s, p = sp1(n-1); return( s+n, p*n); } }

/* Tail recursion */ sp2(word4 n) { jump sp2_help(n, 1, 1); } sp2_help(word4 n, word4 s, word4 p) { if n==1 { return( s, p); } else { jump su_2help(n-1, s+n, p*n); } }

C-- Status Optimization Tail Calls Garbage Collection Exception Dispatch Concurrency Debugging IMPLEM. DESIGN.

GC : 概論 C--にはどのようなGCが望まれるのか？ accurate garbage collection not conservative GC ソース言語の特徴に対応したGC オブジェクトのサイズ・数... Mark, Copy, et al

GC : 問題点と解決方法 データの型 メモリ管理（マシン非依存、ポリシー決定可) front endがポインタ型の情報を作成 Runtime Systemに登録して使用 メモリ管理（マシン非依存、ポリシー決定可) Runtime Systemを導入 Interfaceを使用して、好きなGCを作成

GC : データ型 関数で使用されるレジスタの型を静的に決定し、保存した構造体をDescriptorという 使用者が好きにデザインしてよい f(x : pointer, y : int) 例) data { gc1 : bit32 2; /* this procedure has 2 variable */ bit8 1; /* x is a pinter */ bit8 0; /* y is a non-pointer */ }

GC : データ型の登録・取得 コンパイラが登録を行う。 データ型の動的な取得 span GC gc1 { f(bits32 x, bits y) { ... code for f ... } } データ型の動的な取得 現在のProgram Counterをキーとして、対応するProcedureのDescriptorを得る。

GC : メモリ管理 例えば、以下のようなCopy GCが行われる (次のページはそのソースコード) gc関数の呼び出し 現在のStack frameから最古のStack frameまでスイッチし、以下の手順を行う。 フレーム内の変数のアドレスを得る。 その変数がポインタか判断 ポインタならその先をcopyする from-spaceとto-spaceのスイッチ

Copy GCの作成例 struct gc_descriptor { unsigned var_count; char heap_ptr[1]; }; void gc(void) { activation a; FirstActivation(tcb, &a); for(;;) { struct gc_descriptor *d = GetDescriptor(&a, GC); if(d != NULL) { int i; for(i = 0; i < d->var_count; i++) if(d->heap_ptr[i]) { typedef void *pointer; pointer *rootp = FindVar(a, i); if(rootp != NUL) *rootp = gc_forward(*rootp); } if(NextActivation(&a) == NULL) break; gc_copy(); Copy GCの作成例

Walking a stack Botton of stack Activation handle record Botton of stack Top of stack Activation handle Pointer to an activation record Pointer to first calle-save register Pointer to second calle-save register

例外処理 GCのところで説明したRuntime Interfaceを再利用しても、実現可能。 GCではProcedureに対応するポインタ情報を登録していた 例外用の情報も登録可能。

C--は特定の例外処理に束縛してよいのか 例外処理の対処方法 主に４つの実装方法がある Continuation-passing style (SML/NJ) Constant-time "stack-cutting" (OCaml) Unwind stack in run-time system (Poly M3) Custom code to unwind stack (Self) C--は特定の例外処理に束縛してよいのか

最新の論文の例外処理機構 例外処理の方式をfront endが選択でくるようにC--を拡張している 例外処理の選択には、次の視点がある [Norman and Simon, 2000] 例外処理の選択には、次の視点がある stackを一段づつ上るか Runtimeが処理するか

Alternatives for control transfer Stack walk required? No Yes Generated code cut to return <m/n> Run-time system SetCutToCont SetActivation and SetUnwindCont

Stack cutting Stackを頭から順に調べることなく、例外ハンドラにジャンプする 長所 短所 Constant timeでTrap可能 短所 callee-save registerの復帰ができない

Stack unwinding スタックを頭から順に調べて、例外がキャッチされるかを調べる 長所 短所 callee-save registerの復帰が可能 短所 Stackの深さの分だけ時間がかかる

Reference(1) Simon Peyton Jones, Thomas Nordin, and Dino Oliva. C--: A Portable Assembly Language. In Proceedings of the 1997 Workshop on Implementing Functional Languages, St Andrews, ed C Clack, Springer Verlag LNCS, 1998. Simon Peyton Jones, Norman Ramsey, Fermin Reig. C--: a portable assembly language that supports garbage collection.  International Conference on Principles and Practice of Declarative Programming, 1999.

Reference(2) Norman Ramsey, Simon L. Peyton Jones: A single intermediate language that supports multiple implementations of exceptions. PLDI 2000: 285-298