6/2 (月)
[Prog] 動的バイナリ変換での Indirect Branch をどう扱うか
このところJITコンパイラや動的バイナリ変換は、 レジスタ間接分岐をどう扱うかという方法を調べて CGO や PLDI の論文を狩猟する。 まとまったところでは Derek L. Brauening の 博士論文が 読みやすい。
間接分岐命令は分岐先がレジスタに載っているのでこの値を決定できないと、 次に実行する命令が決まらない。 動的バイナリ変換の場合その位置でコンパイルがぶちぶち切れてしまうし、 次の飛び先は変換テーブルを納めたコードキャッシュから検索が必要になる。
解決策としては、 コンパイル時に静的に分岐先を予測する(Static branch prediction)か、 実行時に履歴を見て予測するか(Dynamic branch prediction)か、 あとはコードの検索テーブルの持ち方を工夫するぐらいの3通りしかない。
Static branch prediction の場合、 データフロー解析を行って間接分岐命令のターゲットレジスタの値を特定することになる。 静的な解析と言ってもコンパイル自体は動的に行うので、 コンパイルを開始した時点の実行コンテキスト(レジスタの値)は使える。
Dynamic branch prediction の場合、 CPU がやっている分岐予測機と同じようなことをする。
- 間接分岐命令が最後に実行した時の ターゲット計算機の分岐先アドレス(target_addr)と対応する変換コードのアドレス(host_addr)をキャッシュしておく。 次回の実行で target_addr がキャッシュした値と一致すれば host_addr を再利用できる。 変換コードのルックアップがスキップできるので高速化できる。
- ターゲット計算機の CALL 命令と RETURN 命令に着目して、
ランタイム内に Software Return Stack を作って
CALL 命令時にアドレスをプッシュして RETURN 時にポップする。
高級言語で書かれたプログラムの場合は CALL と RETURN がペアを作っていることが多いので、 RETURN 命令の飛び先を予測できる。
この場合、ターゲット計算機上の tail-call 最適化なんぞは邪魔にしかならない。
どの間接分岐最適化もコード書き換え対応との相性が悪いのが悲しいところ。 IBM 370 アーキってどうして最初から PC 相対分岐を作らなかったのかしら…
