Categories |
CPUの創りかた |
Modern Compiler Implementation in ML |
NerdTV |
PDP-11シミュレータで古代のUNIXを動かしてみる |
The Yakumo Project |
やさぐれ読書録
最近のツッコミ:1.Braritemeal(2008-08-25 00:41)
2.dyendignify(2008-08-18 10:20)
3.Dominic(2008-06-23 05:05)
最近のトラックバック:1.濃縮還元オレンジニュース:プロ.. (2006-12-22 22:02)
ここ2週間ほど書きつづけていたLiveness Analysisまわりのモジュールもいよいよ終盤である。今週は"interference graph"を構築する部分を組み上げた。アセンブリコード中の仮変数は最終的にはレジスタに割り振られるワケだが、コード中、ある二つの仮変数が互いに干渉(interference)するような場合、これらを同じレジスタに割り付けることは出来ない。"interference graph"とはその干渉関係をまとめたグラフのことを指す。グラフであるからには当然Graphvizの出番も回ってくる。今回は無向グラフを描画するためのツール"neato"を使ったお絵かきである。
まずは11月14日に使ったテストプログラムをネタにしたinterference graph。
面白みのない至極真っ当なグラフが出てくる。グラフ中において線で直接結ばれた仮変数は、同じレジスタに割り付けることが出来ない。ということでいずれの仮変数も%ebpレジスタに割り当てることは不可能である（というかそもそもそんなヘンなことをするヤツはいない）し、t1001とt1002は同じレジスタに割り付けることができないということが明らかとなる（これは元のアセンブリコードと比べるとよく分かる）。
これは少々単純すぎたので、もう少し複雑なものを相手にしてみようと思い、同じく11月14日に使ったマージソートのプログラムのinterference graphを出してみた。すると…
うげげ。まさに阿鼻叫喚と呼ぶにふさわしい図である。もっと簡単な例題でじっくりと確認した方が良さそうだ。
