この記事は
言語実装 Advent Calendar 2022 - Qiita
の5日目のために書いた。
累積レジスタマシンで命令単位JITコンパイラの夢を見るで書いた去年の方法では、AOTコンパイラがJITコンパイラに伝達した情報は、
- 仮想レジスタの優先順位と、
- レジスタに格納される変数が外部関数呼出で破壊されてもいい「破壊変数」なのか、それとも、保存しなければならない「保存変数」か
だけだった。
外部関数で破壊される物理レジスタをcN(clobbered register)(Nは適当につけたレジスタ番号)、保存されるレジスタをsN(saved register)、仮想累積レジスタをVN(Virtual register)(累積レジスタなら、Nは適当ではなく優先順位)とすると、以下の図1のように仮想レジスタに物理レジスタが割り付けられることになる。
図1
[V0][V1][V2][V3][V4][V5]...
[s0][s1][s2][c0][c1]
累積レジスタ割付では、仮想レジスタの優先順位が高いほど高性能の記憶装置が割り付けられるというのが、AOTコンパイラに対するJITコンパイラのお約束だ。
なので、外部関数呼出を跨ぐ場合はメモリに保存場所がコンパイルされてしまう物理破壊レジスタは優先順位のやや低い仮想レジスタに割り付けられ、優先順位最高の仮想レジスタには物理保存レジスタが割り付けられる。
一方、変数にレジスタを割り付けるアルゴリズムの多くは、なるべく多くの変数に物理レジスタを割り付けるため、寿命の短い変数に優先度の高い記憶装置を割り付けがちだ。
このため、外部関数呼出により寿命の制限される破壊変数の方が、保存変数より優先順位の高い仮想レジスタを割り付けられがちになる。
つまり、優先順位の高い累積レジスタには破壊変数と物理保存レジスタが割り付けられ、優先度の低い累積レジスタには保存変数と物理破壊レジスタが割り付けられる。
変数と物理レジスタで、破壊・保存のミスマッチが生じるのだ。
これの改善策が11月に見つかった。
まず、累積レジスタ列をふたつ、仮想破壊レジスタの列と仮想保存レジスタの列を用意する。
そして、それぞれの仮想破壊レジスタに変数を格納する度に、その変数より優先度が高くて同時に生存する変数を格納する仮想保存レジスタの、最大レジスタ番号を付記するのだ。
仮想保存レジスタ側にも同様に、仮想破壊レジスタについての情報を付記する。
そしてJITコンパイル時には、図2のように、仮想破壊レジスタ列(図2での[Sn])と仮想保存レジスタ列([Cn])とで向きを反転させ、物理レジスタの数だけ重複させて、物理レジスタと対応させる。
図2
...[S5][S4][S3][S2][S1][S0]
[s0][s2][s3]
[c1][c0]
[C0][C1][C2][C3][C4][C5]...
破壊専用・保存専用に累積レジスタ列が別々になっており、変数と物理レジスタとの間での破壊・保存のミスマッチはなくなる。
問題は、破壊・保存のどちらにも使い回せる、物理保存レジスタの割付だ。
ここで変数格納時に付記していた、他方のレジスタ列についての情報が役立つ。
それにより、優先度の高い値を格納している仮想破壊レジスタ・仮想保存レジスタの最大個数をJITコンパイラは決定できる。
例えば、ある仮想破壊レジスタに割り付ける記憶装置を考える時。
優先度の高い仮想破壊レジスタの数は、当該仮想破壊レジスタのレジスタ番号そのものだし。
仮想保存レジスタの方は、付記された最大レジスタ番号になる。
これら、当該仮想レジスタより優先度の高い仮想レジスタの数と、扱える物理レジスタの数とを比べれば、当該仮想レジスタに物理レジスタを割り付けるかメモリで済ますか、JITコンパイラは判断できる。
レジスタ割り付け - Wikipediaでは、各変数が別の変数と同時生存するか否かを表す二項関係を「干渉グラフ」と呼ぶ。
この干渉グラフは構築だけでも変数の数の二乗の計算量が掛かるので、線形の計算量しか掛けられないJITコンパイラでは扱えないが、処理時間の制限が緩いAOTコンパイラでは扱える。
変数に仮想レジスタを割り付けたあと、変数を仮想レジスタに置き換えて、同じ仮想レジスタを割り付けられた頂点を統合した干渉グラフも、AOTコンパイラで扱える。
なので原理上は、任意の変数や仮想レジスタについて、それより優先度が高くて同時生存し、破壊・保存の別が異なる変数・仮想レジスタの「集合」をAOTコンパイラは扱える。
なのに、その集合の最大レジスタ番号しかJITコンパイラに伝達しないのは、これもJITコンパイラの時間制限のためだ。
取り敢えずの概念実証コードをGitHub - abo-junghichi/crjitに上げた。
JITコンパイラまでの道程のスタート地点に過ぎないが、興味のある向きによる追試に役立てば良し。