Loop detection

レジスタ割り当てにおいて、どの変数をレジスタに割り当ててどの変数をスタックに追い出すか(Spill)はパフォーマンスに大きく影響するため非常に重要です。できるだけメモリへのアクセスが少なくなるようにレジスタを割り当てなければなりません。

そのためにはプログラムのホットスポットで使われている変数を重点的にレジスタに割り当てるようにします。ホットスポットがどこなのかはコードを実行してみるまでわからないというのが正確なところですが、それはさておき、ループがホットスポットだろうということにして考えます。それぞれのループがどれくらい回るのかは実行してみないとわかりませんので（頑張れば分かる場合もありますが）とりあえずそこそこ(?!)回されるということにします。。ループが何重にもなっている場合はそれに応じた重み付けを行って、変数がどの程度使われるかを推定し、最もよく使われる変数から優先的にレジスタに割り当てるようにします。

さて、ここからが本題です。
Control Flow Graphにおけるループの検出について。

以下はとりあえずここを見ながら読んでいただくと理解しやすいと思います。自分も見ながら書いてます。

まず結論から言うと、バックエッジ(Back edge)があるところがループです。
（強連結成分(Strongly connected component)をループとするのかなーと想像していたら違った。。）

バックエッジとは支配ノード(Dominator)への後退辺(Retreating edge)のこと。

後退辺とは深さ優先探索を行ったときの探索順序が前のノードに対する辺のことです。

支配ノードの説明はwikipediaを参照していただくとして、それを見つけるアルゴリズムは少々複雑です。Dominator (graph theory) - Wikipedia にあるとおり、研究対象になって色々と論文がでるくらい複雑です。jitasmではLengauer-Tarjanアルゴリズムを実装しています。


参考
Control Flow II: Dominators, Loop Detection
Control-Flow Analysis and Loop Detection

Control flow graphの構築

書きかけのまま1年以上放置してしまいました。

jitasmにおけるControl flow graphの構築について。

Control flow graphはBasic blockをノードして実行の流れをエッジとして接続して構築します。

分岐やジャンプなど命令の実行の流れが変わる可能性がある命令と、そのジャンプ先がBasic blockの区切りになります。

• jmp - jmp命令からジャンプ先へのエッジ
• jcc/loop - jcc/loop命令の次の命令へのエッジとジャンプ先へのエッジ
• ret/iret - Exit blockへのエッジ

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

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引数以降に渡される。