■ register allocation(レジスタの割り当て)

	MCIiJ Chapter 11


● 干渉グラフ(interference graph)

	無向グラフ

	ノード --- 一時的な値(temporary value) ... 一時変数

	エッジ(t1,t2) --- 一時変数t1とt2が同時に生きてきることがある。

		生きている変数の解析を行っておく。

	色 --- レジスタ

	隣り合う(adjacentな)ノードが同じ色にならないように、
	グラフのノードに色を付ける。
	すると、ノードに対応する一時変数には、
	色に対応するレジスタを割り当てればよい。

	一般にグラフの色分け問題はNP完全。


● 線形近似アルゴリズム

	Ｋ --- 色の数

	Build: 干渉グラフの生成

	Simplify: Ｋより少ない数のノードと隣り合うノードを除く。
	          (node of insignificant degree)

		結果得られたグラフがＫ色で色分けできれば、
		もとのグラフもＫ色で色分けできる。

		取り除いたノードはスタックにプッシュ。

		繰り返す。

		Coalesceを行う場合は、複写に関係しないノードのみを除く。
		                      (non-move-related node)

	Coalesce: 下記参照

	Freeze: 複写削除の諦め

		複写に関係しているノードで、
		(move-related node)
		Ｋより少ない数のノードと隣り合うノードを選び、
		(of insignificant degree)
		これに関連するcoalescingを諦め、
		複写に関係しないものとする。
		(non-move-related)

		再びSimplify(およびCoalesce)を試みる。

	Spill: メモリへの溢れ

		すべてのノードがＫ個以上のノードと隣り合うとき、
		(of significant degree)
		いづれかのノードをメモリ上に割り付けることにして、
		グラフから取り除く。

		取り除いたノードはスタックにプッシュ。
		(potential spill)

		Spillの後、再びSimplifyを試みる。

	Select: 色付け

		空グラフからはじめて、
		スタックからノードをポップしながら色付けする。

		Spillがプッシュしたノードも色付けできるかもしれない。
		このときはレジスタに割り付けられる。
		色付けできない場合は本当にメモリに割り付ける。
		(actual spill)


● Coalesce

	複写文(move)

		a := b

	がある場合、ノードaとノードbをcoalesce(融合)させれば、
	複写文を消去することができる。
	ただし、coalesceされたノードabは、より多くのノードと隣り合うので、
	もとのグラフが色付け可能であっても、
	融合後のグラフは色付けできなくなるかもしれない。

	そこで、次のような場合にのみcoalesceを行う。
	(concervative coalescing)

	Briggs:	融合ノードabと隣り合うノードのうち、
		Ｋ個以上のノードと隣り合うものの数はＫより小さい。
		(ab will have fewer than K neighbors of significant degree)

	George:	aと隣り合う任意のノードtに対して、
		tはbと干渉しているか(tとbは隣り合うか)、
		tはＫより少ない数のノードとしか隣り合わない。
		(t is of insignificant degree)


● 例(Coalesceなし) (p.240, GRAPH 11.1)

	live-in: k j
		g := mem[j+12]
		h := k - 1
		f := g * h
		e := mem[j+8]
		m := mem[j+16]
		b := mem[f]
		c := e + 8
		d := c
		k := m + 4
		j := b
	live-out: d k j

	４レジスタ

		g --- h j k		4
		h --- g j		2
		k --- b d g j		1
		d --- b j k m		4
		j --- d e f g h k	3
		e --- b f j m		4
		f --- e j m		2
		b --- c d e k m		2
		c --- b m		3
		m --- b c d e f		1
	
	複写

		b ... j
		c ... d

● 例(Coalesceあり)

	g	1
	h	2
	k	2
	c&d	1
	j&b	4
	f	3
	m	2
	e	1


● 攻撃的なcoalescing(aggressive coalescing)

	1. 溢れたノード(spilled node)に対する干渉グラフを作る。

	2. 干渉しないノードを結ぶ複写文はすべてcoalesceする。

	3. SimplifyとSelectを用いて色の上限を設けずに色付けする。
	   Simplifyは隣り合うノードが最も少ないノードから順に選び、
	   Selectは使用できる最初の色を割り当てる。

	4. レジスタ数を越えた色はフレーム上の場所に対応させる。


● 既に色付けされたノード(precolored node)

	特定のレジスタが既に割り当てられているノード。
	例えば、フレーム・ポインタ、引数１レジスタ、引数２レジスタ、などなど。

	これらのノードは、他のノードとcoalesceすることも可能である。
	しかし、Simplifyによって除くことはできない。
	また、Selectにおいては決まった色を与えなければならない。
	Spillによってメモリに割り当てることもできない。


● callee-saveレジスタ

	callee-saveレジスタは、

		enter:	def(r7)
			...
		exit:	use(r7)

	のような関数を、

		enter:	def(r7)
			t231 ← r7
			...
			r7 ← t231
		exit:	use(r7)

	と変換することによって自然に実現することができる。

	この関数が多くのレジスタを必要とすれば、
	t231はSpillによって自然とメモリに割り当てられるだろう。