Open2
MiniShade: レジスタ割付の試作
okuoku必要なレジスタ数の見積りを行うために、実際にレジスタアロケータを製作してしまうことにした。
基本的なアルゴリズム
今回は単純化したLinear scan法で実装する。レジスタ割付のために命令列は2回スキャンされる。
- 命令列に含まれる全てのIDについて、区間
[値の代入位置, 値の最終参照位置]およびレジスタ番号を保存できるようにバッファを確保する - 命令列をスキャンし、それぞれのIDについて
値の代入位置と値の最終参照位置を埋める。 - レジスタそれぞれについて
現在レジスタが保持しているデータの寿命を格納できるようにバッファを確保する - 再度命令列をスキャンし、レジスタの割り付けを行う。割り付けたレジスタに対応する
データ寿命として事前に求めておいた値の最終参照位置を格納しておき、これを過ぎているレジスタは空きレジスタと見做す
最適なレジスタ割付を行おうとするとグラフ彩色問題になってしまい単純に処理するのが難しい。この手法は実装が簡単で、まぁまぁの速度で動作する。
WebGL1制約の活用
レジスタアロケータではWebGL1の制約である "後方ジャンプができない" を活用することにした。これにより、 "一時変数に格納された値の生存期間は最後に参照されるタイミングまで" というのが保証される。
(前方ジャンプ = 命令のスキップ、 後方ジャンプ = 命令の再実行)
WebGL1でも for 等でループを記述することはできるので一見後方ジャンプが可能に見えるが、実際にはループは全てアンロールできることが保証されている。
後方ジャンプが可能な場合、後方ジャンプを含むブロックの末尾まで値の寿命を延長する必要がある。
okuokuとりあえずカウントだけ実装
実際にUTS2のシーンを実行してみると、 最大 99 レジスタ必要 という結果が出た。現状の実装では1つ1つのレジスタに無限のサイズがあると仮定しているので、実際にはもうちょっと効率が低下するものと見られる。というわけで、当初の想定である 128 レジスタというのは割と妥当な予想だったと言える。
mat4 が1つあたり64バイトあり、それが128個で8KiBあるのでシェーダ内で確保できる変数のサイズとしてはかなりギリギリになる。たぶんある程度真面目にパッキング( mat4 の中に vec4 の変数を4つ詰める等)した方が良いだろう。