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

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対応

exeやdllにPDBの絶対パスではなくファイル名だけ含める方法

以下のコンパイルオプションを指定する。
/pdbpath:none

WinDbgでハンドルリークのデバッグ

WinDbgを使ってハンドル（カーネルオブジェクト）のリークをデバッグする方法

1. !htrace -enable
2. !handle コマンドでリーク前のハンドル使用状況を出力し、テキストに保存
3. アプリケーションを動かしてリークさせる
4. !handle コマンドでリーク後のハンドル使用状況を出力し、テキストに保存
5. diff BeforeLeak.txt AfterLeak.txt | grep '> Handle' > LeakHandles.txt
6. LeakHandles.txt をエディタで開いて、"> Handle "を"0x"に置換してリークしたと疑われるハンドルIDのリスト完成
7. .foreach /f (hid "C:\LeakHandles.txt") { !htrace hid 1 }

これで、リークしたと疑われるハンドルを最後に操作したコードのスタックトレースが表示されます。

WinDbgすごい！

関数の戻り値で配列の参照を返す(C++)

int型の配列へのconst参照を返す関数

const int (&GetArray())[4] {
　const static int s_array[4] = {1, 2, 3, 4};
　return s_array;
}

はっきり言って、読めません。関数名の後に配列の長さがあったりとか。。。

普通こういう場合はポインタを返すように書くと思いますが、型から「配列の長さ」の情報が失われてしまうという欠点があります。
どうしても戻り値の型に「配列の長さ」を残しておきたいという場合は使えます。

参照元

"基底クラスからの派生クラスのメソッドの呼び出し" と CRTP

まずはコード。

template<class Derived>
class Base {
public:
　　void Process() {
        // 派生クラスのメソッド呼び出し
        static_cast<Derived*>(this)->SubProcess();
　　}
};

class Hoge : public Base<Hoge> {
public:
　　void SubProcess() {
　　　　std::cout << "Hoge!" << std::endl;
　}
};

派生クラスに実装した処理を基底クラスから呼び出してます。
普通なら、SubProcessメソッドはvirtualにしてBaseクラスに定義しておくところですが、virtualにするとメソッドの呼び出しに多少なりともコストがかかってしまいます。
そのコストを避けるためのカギがCRTP (Curiously Recurring Template Pattern)です。
CRTPを使えば呼び出すメソッドが静的に決まるので、うまくいけばメソッドがインライン展開されて呼び出しコストがゼロになる可能性も期待できます。

virtualにする方が一般的でわかりやすいですが、ここぞという所で使えば威力を発揮してくれそうなイディオムです。

テンプレートクラスにネストされたテンプレートクラスのテンプレートメソッド

テンプレートクラスにネストされた、テンプレートクラスのテンプレートメソッドの実装を
クラスの定義と切り離してみました。

Before:

template<class T>
struct Hoge
{
　　template<class U>
　　struct NestedHoge
　　{
　　　　template<class V>
　　　　void Process()
　　　　{
　　　　　　std::cout << "Hoge Hoge!!" << std::endl;
　　　　}
　　};
};

After:

template<class T>
struct Hoge
{
　　template<class U>
　　struct NestedHoge
　　{
　　　　template<class V>
　　　　void Process();
　　};
};

template<class T>
template<class U>
template<class V>
inline void Hoge<T>::NestedHoge<U>::Process()
{
　　std::cout << "Hoge Hoge!!" << std::endl;
}

えぐい。。。

シフト命令で割り算の落とし穴

整数を2のべき乗で割り算したいとき、割り算の代わりに右算術シフトを使うことがあります。
特に割り算の処理コストが無視できないときにはよく右算術シフトを利用します。

が、今日1つ落とし穴があることに気付きました。

(-1) >> 1

が0になってくれません。

当然といえば当然ですね。0xFFFFFFFF はどれだけ右算術シフトしても 0xFFFFFFFF です。。。

見事にはまってしまいました。

A Lock-Free Hash Table

Google TeckTalksで見つけた、Lock-FreeなHash Tableのビデオ。



まだみてません。

How To Design A Good API and Why it Matters

Google TeckTalks でみつけたAPIデザインに関するビデオ。



もう少しゆっくり喋ってもらえるとありがたいなぁ。。

PDFも発見。

templateクラスでMFCのメッセージ処理

templateクラスでMFCのメッセージハンドラを使おうと思ったんですが、肝心のBEGIN_MESSAGE_MAPが書けない！

と思って調べてみたら色々出てきました。

MSDNのもヒットして、ちゃんとMSDNにも載ってるんだなーと思って読んでいたら、
VC8でちゃっかりBEGIN_TEMPLATE_MESSAGE_MAPなるマクロが追加されているではないですか！
やるなぁ。ありがたく使わせて頂きます。

How to: Create a Message Map for a Template Class

std::auto_ptrの新たな罠(VC8)

VC8では以下のコードがあっさりコンパイルされるようです。

std::auto_ptr<int> p(new char);

これのせいでバッファオーバーフローに半日悩まされました。どう考えても罠です！親切でもなんでもないです。キャストしたかったら自分でします！
boost::shared_ptr使うほどでもないかなというケースでstd::auto_ptr使っていましたがそれすらやめたほうがよさそうですね。。

ちなみに、VC7.1でもgcc 3.4.4でも確認してみましたが、コンパイルエラーになりました。
そりゃ普通そうですよね。

FreeBSDハードディスク交換

FreeBSD環境のハードディスクを交換する際に、古いディスクの内容をまるごと新しいディスクに移す際の手順。

1. 古いHDDをプライマリ、新しいHDDをセカンダリに接続して起動

2. 古いHDDに新しいディスクのマウント先ディレクトリを作成しておく。（スライスの構成と同じだけ）

mkdir /mnt
mkdir /mnt/var
mkdir /mnt/tmp
mkdir /mnt/usr

2. 古いHDDと同じような構成で、新しいHDDのパーティションを切る。
sysinstall -> Fdisk

3. 古いHDDと同じような構成で、新しいHDDのスライスを設定する。
マウント先は先ほど作成したディレクトリ。
sysinstall -> label

4. 各スライスをコピーする

dump -0af - -C 32 / | ( cd /mnt ; restore xf - )
dump -0af - -C 32 /var | ( cd /mnt/var ; restore xf - )
dump -0af - -C 32 /tmp | ( cd /mnt/tmp ; restore xf - )
dump -0af - -C 32 /usr | ( cd /mnt/usr ; restore xf - )

参照：FreeBSD QandA 1859

VisualStudio2005 cppとhファイルの切り替え

VisualStudio 2005でcppファイルとhファイルを切り替えるためのマクロ

参照 BorisJ's Blog