type t (* void *)

関数型言語や英語学習の事とか。

レジスタ割付けにグラフ彩色を使うの微妙だなという話

レジスタ割付け

コンパイラはコード生成の最後に変数(無限にレジスタがあると仮定したときの仮想レジスタ)を実際のレジスタに対応付ける、レジスタ割付けを行う。 この際には一般的にはグラフの彩色問題に帰着して解く事が多い。

彩色問題の色を使用レジスタに見立てて、何色で塗ることができるかというのを求め、それが実際のレジスタ数を超えていれば spill(メモリに退避)/fill(メモリから復帰)の処理を追加して仮装レジスタの生存区間を分割し、もう一度彩色を試みる。

疑問

  • コンパイルターゲットが分かっているわけだからNはもう分かっており、N色で塗れるかどうかを解くべきで、何色で塗ることができるのかという問題を解くのは変なのでは? これはRegister-Pressure-Aware schedulingの論文を読んで、これでこんなに性能が向上するのか、、、今まで何をしていたんだ感を感じました(@tanimocchi さん @khibino さんに感謝) Register pressure aware scheduling for high level synthesis - IEEE Conference Publication
  • CPUでしかうまく動かなくないですか?
    例えばVideoCore4というGPUでは自由に読み書きできるローカルメモリがないので、スピルを行うためにはCPU側のメモリにDMA転送でに書き戻さなければならないが、スタックポインタというものはない。アドレッシングモードでBase+Offsetを計算せずにいっぺんに行うLoad命令みたいなものがないので多数の演算が必要である。 更に書き戻す先のアドレスを保持する変数が生きている必要があり、Base+Offsetの計算のための演算命令を挿入する必要がありそのレジスタも要求するようになる。

    そうすると次はその命令をスケジューリングしたり、共通式の除去などの最適化を行いたくなるだろう。フェーズ間で影響を与え合いすぎてしまう。

    スピルをしやすいアーキテクチャでしかうまくいかないのでは?という疑問