● コード改良変換

* 大域的な共通部分式の削除

    アルゴリズム10.5 (p.773)

	＼                    ／
	w := y+z        w' := y+z  ← ブロックの先頭に最も近いy+zの計算
	    ＼            ／↑
	      ＼        ／  ｜yの定義もzの定義もない
	        ＼    ／    ↓
	    ┌──────┐ブロックの先頭で式y+zが利用可能
	    │            │↑
	    │            │｜yの定義もzの定義もない
	    │s: x := y+z │↓
	    │            │
	    │            │
	    └──────┘

    uを新しい変数として、次のように変換。

	＼                    ／
	u := y+z         u := y+z
        w := u           w' := u
	    ＼            ／
	      ＼        ／
	        ＼    ／
	    ┌──────┐
	    │            │
	    │            │
	    │s: x := u   │
	    │            │
	    │            │
	    └──────┘


* 複写伝搬

    x := y という複写文を削除する。

    アルゴリズム10.6

           xの定義
           ↓
	s: x := y  ← 削除したい複写文
	    ＼
	      ＼ 
	        ＼        ／
	          ＼    ／    xの使用
	            ＼／      ↓
                 u: ... := ...x...  ← xをyに置き換えたい

	条件:

	 1. uに到達するxの定義はsしかない。

	 2. uに到達するyの定義は必ずsを通る。

    1についてはud連鎖(使用と定義の連鎖)でチェックできる。
    2については別の解析が必要。

    新しい解析 --- 二つの条件を一度にチェック

    (複写文の集合を求める)

    e_gen[B]:  Bで生成される複写文の集合
    e_kill[B]: Bで消滅する複写文の集合

	B┌───────┐
	 │              │
	 │              │
	 │x := ...      │← ここで、y:=x と x:=y の
	 │              │   両方の複写文が消滅する。
	 │              │
	 └───────┘

    前進  集合積
          ^^^^^^
          必ず到達することを知りたい。

	cf. ud連鎖(到達定義)の解析は、前進・合併型であった。

    アルゴリズム10.6 (p.777)

	   s: x := y
	       ｜
	       ｜
	       ↓
	┌───────┐
	│              │
	│              │
	│... := ...x...│xの使用
	│              │
	│              │
	└───────┘

	sが到達するような任意のxの使用に対して、

	(*) sが上の解析によるin[B]に入っている。かつ、

	(*) Bの中でxの使用に至るまでにxまたはyの定義がない。

	以上の二つの条件が満たされているならば、
	sを削除して、(sが到達する)xの使用をすべてyで置き換える。


* ループ不変計算

    ここでいうループとは、ヘッダと呼ばれるブロックを持ち、
    ループ内のブロックへ行くには必ずヘッダを通る。
    また、ループ内の各ブロックからヘッダへ行く経路がある、
    という部分グラフのこと。

    アルゴリズム10.7 (p.779)

	ループLの中の定義に不変の印をつける。
	                   ^^^^
	                   ループに入ってから出るまで、
	                   いつも右辺は同じ値になる。

	ud連鎖を用いる。

	次のステップを繰り返す。

	    各定義 x := y+z に対して、yとzが、

	    (*) 定数であるか、もしくは、

	    (*) そこに到達する定義がループの外か、
		既に不変の印がついている、

	    ならば、不変の印をつける。


* コード移動 (p.781)

    不変な文をヘッダーの前へ移動する。
              (前ヘッダー)

    s: x := y+z を移動できる条件:

     1. sを含むブロックはループのすべての出口を支配。
	(つまり、ループから出るにはsを含むブロックを必ず通る)

		この条件は効率の向上を保証している。

     2. ループ内でxへの代入はsのみ。

     3. ループ内にはs以外のxの定義は到達しない。
                                    (xの使用に)


* 誘導変数 (p.784)

    ループ中で、変数iに対して、

	i := i±c

    という形の代入が一つのみである
    (代入が一つのみで上の形をしている)とき、
    iを、

	基本誘導変数

    という。

    jがiに対する誘導変数であるとは、
    (定数cとdが存在して)
    jへの代入の後で、常に、

	j = c*i + d

    という等式が成り立っていること。

    jが(iに対する)誘導変数で、kへの代入が常に、

	k := j*b
	k := b*j
	k := j/b
	k := j±b
	k := b±j

    のいづれか一つの形をしているとき、
    jが基本誘導変数であるか、または、

	(a) jへの代入は一つでそれとkへの代入の間にiへの代入がない
	(b) ループの外側のjの定義はkに到達しない

    の二つの条件が成り立っているならば、
    kも(iに対する)誘導変数になる。

    誘導変数に対する強さの軽減 (p.786)

	jとj'がiに対する誘導変数で、

	    j = c*i + d
	    j' = c*i + d

	が成り立つとき、sを新しい変数として、

	    i := i±n	  ⇒	i := i±n
				s := s±c*n
	      ...		        ^^^
				        定数
	    j := ...		j := s

	      ...

	    j' := ...		j' := s

    誘導変数の削除 (p.789)

     1. iが基本誘導変数で、分岐と
	更新 (i := i±n) のときのみに参照されるとする。
	j = c*i+d (c＞0) のとき、

				r := c*x
				r := r+d
	...			...
	if i≧x goto B    ⇒	if j≧r goto B

        iの定義を削除。

	xが定数である場合が典型的。

     2. 上記の誘導変数に対する強さの軽減を行う。

	(jをsで置き換えて) j := s を削除。