2009年5月18日月曜日

レジスタ割り当てに関する資料

グラフ彩色アルゴリズム

グラフ彩色アルゴリズムとJIT向けの改良版。

Register allocation and spilling via graph coloring
GJ Chaitin

Tailoring Graph-coloring Register Allocation For Runtime Compilation
Keith D. Cooper, Anshuman Dasgupta


Linear Scan Algorithm

Linear scan algorithmとその改良版。

Linear Scan Register Allocation
Massimiliano Poletto, Vivek Sarkar

Quality and Speed in Linear-scan Register Allocation
Omri Traub, Glenn Holloway, Michael D. Smith

Optimized Interval Splitting in a Linear Scan Register Allocator
Christian Wimmer, Hanspeter Mossenbock

Extended Linear Scan: an Alternate Foundation for Global Register Allocation
Vivek Sarkar, Rajkishore Barik


その他

様々なレジスタ割り当てのまとめ(?)

SSA-Based Register Allocation

A Survey on Register Allocation

2009年5月17日日曜日

レジスタ割り当てへの道

jitasmにレジスタ割り当て機能が欲しいなぁと思っています。

動機

1つのコードでx86/x64どちらでも動かしたい。今のjitasmではeaxやraxの代わりにzaxという名前のレジスタを使えばx86ではeaxになりx64ではraxになるというコードが書けますが、x64で追加されたr8~r15レジスタを使ったポータブルなコードは書けません。レジスタ割り当て機能があればx86なら8個のレジスタを使い、x64なら16個のレジスタを使ったコードを自動的に生成することができます。


基礎

レジスタ割り当てについては右も左もわからないド素人なので基礎の基礎から勉強するところからはじめます。

レジスタ割り付け - Wikipedia

どうやら「グラフ彩色アルゴリズム」と「Linear Scan Algorithm」という大きく2つの手法があるようです。そしてどちらにおいてもレジスタ割り当ての前に生存変数解析(Live variable analysis)というデータフロー解析を行う必要があります。

データフロー解析 - Wikipedia
Live variable analysis - Wikipedia, the free encyclopedia

データフロー解析を行うには制御フローグラフ(Control flow graph)が必要です。

制御フローグラフ - Wikipedia


なかなか道のりは長そうです。。。

  © Blogger template 'Isolation' by Ourblogtemplates.com 2008

Back to TOP