レジスタ割り当てに関する資料 - 書籍

Modern Compiler Implementation in C

Andrew W. Appel, Maia Ginsburg

Googleブック検索

Amazon

Advanced Compiler Design and Implementation

Steven S. Muchnick

Googleブック検索

Amazon

知りたいところをGoogleブック検索でプレビューできる範囲で読んだだけですが参考になりました。。

レジスタ割り当てに関する資料

グラフ彩色アルゴリズム

グラフ彩色アルゴリズムとJIT向けの改良版。

Register allocation and spilling via graph coloring
GJ Chaitin

Tailoring Graph-coloring Register Allocation For Runtime Compilation
Keith D. Cooper, Anshuman Dasgupta


Linear Scan Algorithm

Linear scan algorithmとその改良版。

Linear Scan Register Allocation
Massimiliano Poletto, Vivek Sarkar

Quality and Speed in Linear-scan Register Allocation
Omri Traub, Glenn Holloway, Michael D. Smith

Optimized Interval Splitting in a Linear Scan Register Allocator
Christian Wimmer, Hanspeter Mossenbock

Extended Linear Scan: an Alternate Foundation for Global Register Allocation
Vivek Sarkar, Rajkishore Barik


その他

様々なレジスタ割り当てのまとめ(?)

SSA-Based Register Allocation

A Survey on Register Allocation

レジスタ割り当てへの道

jitasmにレジスタ割り当て機能が欲しいなぁと思っています。

動機

1つのコードでx86/x64どちらでも動かしたい。今のjitasmではeaxやraxの代わりにzaxという名前のレジスタを使えばx86ではeaxになりx64ではraxになるというコードが書けますが、x64で追加されたr8~r15レジスタを使ったポータブルなコードは書けません。レジスタ割り当て機能があればx86なら8個のレジスタを使い、x64なら16個のレジスタを使ったコードを自動的に生成することができます。


基礎

レジスタ割り当てについては右も左もわからないド素人なので基礎の基礎から勉強するところからはじめます。

レジスタ割り付け - Wikipedia

どうやら「グラフ彩色アルゴリズム」と「Linear Scan Algorithm」という大きく2つの手法があるようです。そしてどちらにおいてもレジスタ割り当ての前に生存変数解析(Live variable analysis)というデータフロー解析を行う必要があります。

データフロー解析 - Wikipedia
Live variable analysis - Wikipedia, the free encyclopedia

データフロー解析を行うには制御フローグラフ(Control flow graph)が必要です。

制御フローグラフ - Wikipedia


なかなか道のりは長そうです。。。

Microsoft x64 呼び出し規約

x86はcdeclやstdcall, fastcallなどいくつかの呼び出し規約がありますが、x64はfastcallしかありません。

引数

• 第1引数 rcx もしくは xmm0
• 第2引数 rdx もしくは xmm1
• 第3引数 r8 もしくは xmm2
• 第4引数 r9 もしくは xmm3
• 第5引数以降 スタック

第1引数から第4引数については型によって以下のような値が渡されます。

• 整数型、1, 2, 4, 8バイトの構造体、__m64 は汎用レジスタに値として渡される。未使用上位ビットはクリアされない。
• float/double はxmmレジスタに値として渡される。未使用上位ビットはクリアされない。
• 上記以外（1, 2, 4, 8バイト以外の構造体、__m128）は汎用レジスタにポインタとして渡される。ポインタは16byteでアラインメントされている。

戻り値

• 整数型、1, 2, 4, 8バイトの構造体、__m64 はraxに値として返される。
• float/double/__m128 はxmm0に値として返される。
• 上記以外は関数呼び出し時の最初の引数(rcx)として戻り値のポインタを渡し、そのアドレスに戻り値の内容がコピーされる。raxにはそのポインタ(つまり第1引数と同じ値)が返される。 第1引数が戻り値のポインタとなるため、関数の本来の引数は第2引数以降に渡される。

呼び出し直後のスタック

関数呼び出し時は呼び出し側で32バイト以上のスタック領域を確保してからcallを行う必要があります。
32バイトというのはレジスタ渡しとなる4つの引数をスタックに退避するのに必要となるサイズです。これは呼び出したい関数の実際の引数が3つ以下のときでも確保しておく必要があります。確保したスタックの中身は未初期化のままで構いません。5つ目以降の引数はそれに続くようにpushされます。
さらにもう一つの決まりとしてcall直前のスタックポインタが16バイトアラインされている必要があります。

引数が4つ以下の関数を呼び出した直後のスタックの状態

引数が5つの関数を呼び出した直後のスタックの状態

参考

x64 ソフトウェア規約(MSDN)
x64: Starting Out in 64-Bit Windows Systems with Visual C++
The Old New Thing : The history of calling conventions, part 5: amd64

cdecl 呼び出し規約

cdecl 関数呼び出し規約についてMSDNやVCが生成するコードを基に調べてみました。

引数

• 引数は最後から順にスタックにpushされる。（4バイト境界）
• 4バイト以上の構造体を引数に値渡しした場合でも、構造体の内容がそのままスタックに追加される。（4バイト境界でスタックに入れられる）
• __m64 は3つまではmm0, mm1, mm2に渡される。4つ以上はコンパイルエラー。スタックにはpushされない。
• __m128 は3つまではxmm0, xmm1, xmm2に渡される。4つ以上はコンパイルエラー。スタックにはpushされない。

戻り値

• 整数型、1, 2, 4バイトの構造体はeaxに値として返される。
• 8byteの構造体は上位32bitはedx、下位32bitはeax
• float/double はFPU ST(0)に値として渡される。
• __m64 はmm0に値として返される。
• __m128 はxmm0に値として返される。
• 上記以外は関数呼び出し時の最初の引数として戻り値のポインタを渡し、そのアドレスに戻り値の内容がコピーされる。eaxにはそのポインタが返される。
  第1引数が戻り値のポインタとなるため、関数の本来の引数は第2引数以降に渡される。

jitasm

最近jitasmなるオープンソースのプロジェクトをやっています。インラインアセンブラ風の構文で動的にコード生成を行うためのC++ライブラリです。
この手のライブラリとしてはxbyakが有名ですが、jitasmは後発なりに特色を出していけたらと思っています。

目標

• MASM, VCのインラインアセンブラ風
• 美しく書ける
• 簡単に使える
• 軽い
• x86/x64のソースコードポータビリティ

特徴 (version 0.2.0)

• x86/x64汎用命令
• x87 FPU命令
• MMX, SSE, SSE2, SSE3, SSSE3, SSE4.1, SSE4.2
• naked, cdecl, Microsoft x64 fastcall の関数呼び出し規約サポート
• 関数呼び出し規約に沿ったprolog/epilogの自動生成
• 制御構文(If, Repeat, While)
• VC8, VC9対応