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