GHCの最適化まとめ(Core to Core編)
随時更新
最適化の流れ
上から順番に行われる．
static argument transformation
再帰呼び出しのために使われる余分な引数を自由変数に変換する．-fstatic-argument-transformationが有効のときのみ行われる．
ここでの余分な引数とは，再帰全体を通して変化しない(static argument)のことをいい，foldr f z lを再帰で実装する場合は，lは消費されるため変わるが，zとfは変わらないため，これらがstatic argumentとなる．これらを自由変数に変換して再帰呼び出しの引数から消すのがstatic argument transformationである．
メリットとして，
スタックにpushされる引数が減るので，各再帰呼出しでのスタックの使用量が減る
外側が再帰ではなくなる(内側のlet束縛に再帰が移る)ので，インライン展開できる可能性が出てくる(再帰する関数の呼び出しはインライン展開できないが，再帰呼び出しが関数の内側に閉じ込められるので，この関数自体はインライン展開できるようになる)．
再帰を閉じ込める部分の閉包の自由変数が必ず減る(末尾呼び出し場合はこの限りではない)．これはSTGの閉包のサイズが自由変数の数に依存するということから考えても良い性質である．
static argumentとなる自由変数はすべて削除され，(ほとんどの場合1個)の再帰関数(これは自由変数となる)に変換される
再帰の中にstatic argumentのみに依存する部分式があった場合，それをfull laziness transfomrationにより再帰の外にだし，再帰の回数だけ計算されるような非効率な実行を避けることができる．
デメリットとして，
ローカルな再帰関数のために余分な閉包を作ってしまう
実際問題として，多くの抽象機械の実装ではlambda lifitingを使っているが，これはSATの逆変換になっており，上記のメリットのうちインライン展開の機会が増えるという点以外消滅してしまう．なのでlambda liftingの実装を考える必要がある．(late lambda liftingが実装されここの問題が解決された．)
効率として，余分な閉包ができるためその関数の呼び出し回数だけアロケートの数は増えてしまうが，自由変数のheapアロケートで4bytes以上(GHCの場合)使うため，SATをしたあとの関数は(static argumentの数) × (呼び出し回数) × (再帰の回数) × (4bytes)分だけメモリを節約することができる．
注意点として，
当然だが，static argumentの数が1個の場合(e.g. map)，heap消費量は変わらない
末尾呼び出しの場合，新しく作られる再帰関数が閉包内で呼ばれないので，閉包の自由変数の数は変わらない．
vectorisation
Nested Data ParallelismをGHCでしたいときに使われるっぽい．よくわからん．
[:*:]といった特殊なリテラルを使うとPAクラスのインスタンスであれば並列化してくれるようで，その並列化を行うのがこの処理．スレッド並列な関数が書けたりするようである．まだ実験段階の機能のようで，普通に使う分にはRepaを使おうという感じっぽい．要-fvectorise, ParallelArrays拡張`．参考 Simplifier, gentle run
インライン化とRewrite Ruleに従った融合変換，η簡約，let-floatなどを行う(詳しくは #Simplifier を参照)．gentle runではsimplifierは二回行われる．インライン化は昔はgentle runでは行われていなかったが，これはユーザの直感に反するため，8.6.4ではすでにインライン化が行われるように改修された．gentle runでRuleが有効である理由は2つある． spliceをsimplifyするときに，lift String ===> ...といったルールをTHで有効化させたいため，文字列リテラルのための単純なコードを得る．
op (df d1 d2) --> $cop3 d1 d2となるときに，これはopとdfの相互再帰を壊してしまうため，class-opの取り消しが起こってほしい．
しかい，Listのfusionはfloatを防いでしまうため，フェーズ制御でfloatをするまでこれらのルールはオフになっている．
ここではcase of case変換は行われない．これはfull laziness変換がよく適用されるようにするためである．
Specialisation
オーバロードを排除して特殊化することを試みる．
特殊化に関する重要な考え
オーバーロードされた関数に渡されるTypesと渡される「辞書」は互いに重複している．同じ関数が同じ型に適用されるならば，同じ辞書(というよりかはむしろ同じ値)が確実に適用される(引数は異なって見えるかもしれないが，それらは同じ値に評価される)．
辞書の引数を静的で特殊なものとして扱うことで，発展的なことができる．束縛時分析を行わずに，代わりに辞書の引数にの特殊化にだけ専念できる．
Full laziness, 1st pass
ラムダの外側にlet束縛をfloatさせる．このパスには，束縛にレベル情報をアノテーションしてからfloat-outパスを実行することを含んでいる．このFull laziness 1st passでは，部分適用と自由変数を含む束縛のfloatをしない．これらはパイプライン後半の2番目のパスで行われる．
Full laziness変換はlet-out変換の一種で，再帰の際に何回も計算されるlet束縛を，再帰の外側に追いやることで計算量を節約しようとする変換である．SATと似たような最適化と考えることもできるだろう．当然だが，let束縛されてないような自由変数に対しては効果がない(let束縛を外側にするだけなのでそれはそう)．ちゃんと束縛するのが大事．場合によっては，float-inによって効率が改善することもあり，一概にfloat-outするのが良いとも言えない(詳しくは #float-in を参照)．したがって，Full laziness変換が行われるのは限られた場合である．一例として，以下のいずれかの条件が当てはまる場合は適用すべきではない． 1. 束縛の右辺がはすでに値であるか，または無視できる回数で値に簡約される．RHSが値である場合，アロケーションはいくらか節約されるかもしれないが，同じ関数の多数の呼び出しの間でそれらが共有されても，いくらも作業は節約されない．
2. ラムダ抽象は一度ならず，適用される．我々はラムダ抽象が一度だけ適用されるいくつかの状況を分析するプログラムを実験している．
加えて，Full laziness変換をした結果スペースリークを引き起こす可能性があるが，実際はこのスペークリークが実際のプログラムにとって問題になることはほとんどない．面倒な理由から，式をGCするのは難しいため，式を最上位レベルまで移動させることに関して，GHCはかなり保守的になっている．
Simplifier, main run
行われる具体的な最適化の一例として
定数畳み込み
書き換え規則の適用
インライン展開
case of case変換
case of known constructor
η展開/簡約
β簡約
隣接するキャストの結合
適用の邪魔にならないようにキャストを外に押し出す．例えば，(f |> k) a ==> f (a |> k1) |> k2．ここで，k1, k2は適切なもの．
Float in, 1st pass
full lazinessとは反対に，let束縛を可能な限り使用されている場所に近づけるようにfloatさせる．ラムダが一回きりしか使われないのではない限り，ラムダ内の束縛を深くすることがfull laziness変換を元に戻すようなことはない．この段階ではまだdemand analysisをしていないため，インポートしたものに関するdemand 情報しかない．
float in変換は，次のような観察に基づいている．他のものが同じであればあるほど，束縛を内側に動かすことができればよい．例えば，ある選択肢でしか使わない式を外側で束縛している場合，それを内側に移動させれば選択肢が選ばれない限りアロケートされることはないため，メモリ使用量が節約される．let束縛を内側に移動させる利点は少なくとも以下の3つがある．
code: core1.hs
-- Before transformation
let x = y+1
in case z of
[] -> x*x
(p:ps) -> 1
-- After transformation
case z of
[] -> let x = y+1
in x*x
(p:ps) -> 1
束縛は実行されないかもしれない．この例では，zは(p : ps)の形式になることがある．その場合，xの束縛を処理するコードは実行されない．変換の前では，xのサンクは zの値にかかわらず確保される．
正格性解析をより良くする可能性がある．束縛が配置された時点で，束縛された変数が確実に評価されることがわかっている可能性が高くなる．これにより，他の正格性関連の変換を実行することが可能になる．この例では，xにサンクを割り当てるのではなく，適切なコンパイラであれば，単純にyを評価し，それをインクリメントしてその結果を二乗するだけで，サンクを全く割り当てない．
余分な評価が排除される可能性がある．右辺が以前よりも多くの変数の評価状態を「知る」可能性がある．
code: core2.hs
-- Before transformation
let x = case y of (a,b) -> a
in
case y of
(p,q) -> x+p
-- After transformation
case y of
(p,q) -> let x = case y of (a,b) -> a
in
x+p
ここで，コンパイラはyの内側のcaseが，yを参照している外側のcaseの右辺にあることに気づける．したがって，次のようにすることで，内部のcaseを取り除くことができる．
code: core3.hs
case y of
(p,q) -> p+p
束縛が別の束縛の右辺に移動されると，最初の2つの利点も生じる．例えば，内側に動くことは次のような変形が起きるだろう．
code: core4.hs
-- Before transformation
let x = v+w
y = ...x...x...
in
<body> -- where <body> dose not mention x
-- After transformation
let y = let x = v + w in ... x ... x ...
in
<body>
この例では，束縛を移動することによるもう一つの小さな影響も示している．
floatすると，アロケートされたサンクのサイズが変わる可能性がある．(GHCの実装では)それぞれのlet(rec)束縛はそれぞれの自由変数に対して一つのスロットを持つヒープオブジェクトをアロケートする．自由変数が多いほど，アロケートされるオブジェクトは大きくなる．例では，xをyの右辺に入れると，yの自由変数からxが削除されるが，vとwが追加される．それによって，yのサンクが大きくなったり，小さくなったりするかどうかは，v及び/またはwがyの中ですでに開放されているかどうかによって異なる．
これまでのところ，束縛は「可能な限り」内側へfloatすることが有用であると示唆している．つまり，束縛された変数のすべての出現箇所をスコープ内に保ちながら，それ以上floatできなくなる場所までfloatするということである．このルールには重要な例外がある．ラムダ抽象の中に束縛をfloatするのは危険である．なぜなら，ラムダ抽象が何度も適用されると，各適用が束縛の新しいコピーをインスタンス化することになる．さらにわるいことに，束縛が簡約可能な式を含んでいる場合，後者はラムダ抽象が適用されるたびに再評価される．
これの単純な解決策は，ラムダ抽象内に束縛を決してfloatさせないことである．これがGHCが現在行っていることである．最初からラムダ抽象内に束縛がある場合，full laziness変換によって外側にfloatする．
Call Arity
ローカル関数の使用方法に基づいて，η展開を試みる．実行された場合，このパスの後にSimplfierの0フェーズが続く．
通常は高階のコンビネータは，いくつかの関数定義がη展開される場合，かなり効率的なコードになる可能性があるが，既存の解析方法は常に効率的な実装を施せるほど正確ではなかった．例えば，foldrを使ったfoldlの実装ではこれのせいでリストの融合変換がうまく機能しない．Call Arityでは定義ではなく使用方法でη展開をするかを分析するものであり，これは非常に正確に動作する．
Demand analysis, 1st pass (正格性解析)
demand analyserを実行し，続いてworker-wrapper変換と0フェーズのsimplifierを実行する．このパスでは，いくつかの式が確実に使用されるかどうか，そしてそれらが1回または複数回使用されるかどうかを判断しようとする(濃度分析 cardinality analysis)．現在のところ，束縛が何度も使用されることが確実であるという手段はない．一度限りであることが確実であるか，または一度限りである可能性が高いと判断することしかできない．demand analysisでは正格性情報を含むCoreにのみアノテーションを渡す．この情報は，あとでworker/wrapperパスで変換の実行に使用される．CPR解析はdemand analysis中にも行われる．
Full laziness, 2nd pass
1st passで行わなかった部分適用と，自由変数を持つ関数のfloat outを行う．
Common Sub-expression elimnation
共通部分式を取り除く．
Float in, 2nd pass
Float in, 1st passと同様．2回目のfloat outしたからね．
Check rules, 1st pass
このパスは最適化用ではなく，Ruleのトラブルシューティング用である．文字列パターンを受け付ける-frule-checkフラグでのみ有効になる．このパスでは，文字列パターンで始まるRuleが発火したか否かを標準出力に出力する．
Liberate case
自由変数のcase分析が繰り返されるのを避けるために，再帰関数をそれぞれ自身の右辺に1回展開する．これはcall-pattern specialisationに少し似ているが，引数ではなく自由変数のためのものである．この後に0フェーズのsimplifierが実行される．-fliberate-caseフラグでのみ有効である．
Call-pattern specialisation
-fspec-constrフラグでのみ有効である．再帰関数のインライン化を行う．WHNFの引数を含む呼び出しパターンの再帰関数を特殊化して，simplifierが本体内の新しく表れた不要な書き換え可能な式を取り除けるようにする．詳しくは #Call-pattern-specialisation を参照せよ． Check rules, 2nd pass
二回目
Demand analysis, 2nd pass (late demand analysis)
やることは1st passと一緒．これが再度行われる理由は，正格性を発見するためのいくつかの機会が以前には発見できなかったためである．call-pattern specialisationのような最適化は，late demand analysisによって排除される未使用の引数を持つ関数を作成することがある．-flate-dmd-analでのみ有効である．
Demand analysis, final pass
worker/wrapper変換は行われない．これは，demand analyserが以前に実行された場合は必ず実行される．これは単一のエントリのサンクを検出するためのものである．worker/wrapperのもう一回のラウンドではその情報を無効にするので，行われない．