トレーシングと部分評価の比較 Part3
これは部分評価とトレーシングを比較するシリーズの三つ目のエントリです。最初のエントリでは、小さ FlowGraph 言語をインタプリタとともに紹介し、FlowGraph 言語の部分評価器をお見せしました。二つ目のエントリでは、トレーサが同じ言語にどのように働くかと、部分評価とトレーサの二つの実行がどのように関係するのかをお見せしまし、プロモーションの機能をトレーサに追加しました。
このエントリでは、トレーサによって生成されたトレースをどのように最適化するかをお見せし、部分評価のオプティマイザの構造とトレーサのオプティマイザの構造を比較します。
このエントリで使われているソースコードはここにあります: http://paste.pocoo.org/show/547304/
トレースの最適化
前回のエントリで、どのようにスペシャルモードでの制御フローグラフプログラムの実行によるガードとともに線形化したトレースを生成するかを見ました。トレースはいつも loop 文で終わり、開始地点にジャンプします。トレーサはインタプリタが実行したオペレーションのログを取るだけなので、出力されるトレースには余計なオペレーションが含まれてしまいます。一方で、トレースはプロモーションといくつかの決定を通して、最適化に利用できるいくつかの実行時の値も含みます。以下の例は、前回のエントリのサンプルのプロモーションによって生成されたトレースです。
op2(c,ge,var(i),const(0),
guard_true(c,[],l_done,
guard_value(x,5,[],b2,
op2(x2,mul,var(x),const(2),
op2(x3,add,var(x2),const(1),
op2(i,sub,var(i),var(x3),
loop))))))
guard_value(x, 5, ...) の操作の後、 x が 5 であるとわかります。ただし 5 ではない場合、実行はインタプリタにフォールバックされます。従って、 ガードの後の x に対するオペレーションは、定数に畳み込めます。定数畳み込みの並べ替えを行うために追加の最適化のステップが必要です。どの変数が定数として扱えるかと、どの値が部分環境で使われているかの情報を利用しながら最適化のステップはトレースに沿って動作します。オプティマイザは定数引数のみを持つオペレーションを取り除き、それ以外をトレースに残します。このプロセスは部分評価に実際に非常に似ていて、いくつかの分かっている変数は定数になり、定数引数のみのオペレーションは最適化によって取り去られ、残りはそのままです。
最適化を行うためのコードを以下に示します。
optimize(op1(ResultVar, Op, Arg, Rest), PEnv, NewOp) :-
presolve(Arg, PEnv, RArg),
(RArg = const(C) ->
do_op(Op, C, Res),
write_env(PEnv, ResultVar, Res, NEnv),
NewOp = RestResidual
;
remove_env(PEnv, ResultVar, NEnv),
NewOp = op1(ResultVar, Op, RArg, RestResidual)
),
optimize(Rest, NEnv, RestResidual).
optimize(op2(ResultVar, Op, Arg1, Arg2, Rest), PEnv, NewOp) :-
presolve(Arg1, PEnv, RArg1),
presolve(Arg2, PEnv, RArg2),
(RArg1 = const(C1), RArg2 = const(C2) ->
do_op(Op, C1, C2, Res),
write_env(PEnv, ResultVar, Res, NEnv),
NewOp = RestResidual
;
remove_env(PEnv, ResultVar, NEnv),
NewOp = op2(ResultVar, Op, RArg1, RArg2, RestResidual)
),
optimize(Rest, NEnv, RestResidual).
部分評価と同じですね!部分評価器からのヘルパ関数 presolve と部分環境 PEnv の再利用をしています。オペレーションの引数が部分環境の中で定数だと分かっている時、オペレーションは最適化の際に実行され、トレースから取り除かれます。そうでなければオペレーションは出力のトレースに残ります。結果の変数(部分評価器内にあるもの) は部分環境から取り除くために必要です。不明な結果によって上書きされるためです。
トレースの中でガードで対処する必要があります。
optimize(guard_true(V, [], L, Rest), PEnv, NewOp) :-
plookup(V, PEnv, Val),
(Val = const(C) ->
NewOp = RestResidual
;
NewOp = guard_true(V, PEnv, L, RestResidual)
),
optimize(Rest, PEnv, RestResidual).
optimize(guard_false(V, [], L, Rest), PEnv, NewOp) :-
plookup(V, PEnv, Val),
(Val = const(C) ->
NewOp = RestResidual,
NEnv = PEnv
;
write_env(PEnv, V, 0, NEnv),
NewOp = guard_false(V, PEnv, L, RestResidual)
),
optimize(Rest, NEnv, RestResidual).
ガードされた変数が実際は定数だとわかったとき、ガードを取り除けます。
注意としては、定数のガードが失敗したときは可能ではありません。 (??)
トレーサは実際の値で実行している間のオペレーションを記録します。
従って、値のガードが成功するにはオプティマイザが定数を検出する必要があります。
guard_false は guard_true と若干違います。guard_false の後は引数が実際に 0 だとわかりますが、 guard_true の後は値がゼロではないことのみ知り、正確な値はわかりません。
別の点に注目してください。カードによる最適化で、これまでのところ常に空リストだったガードオペレーションの二つ目の引数が部分環境 PEnv に置換されます。この置換がなぜ必要なのかを掘り下げて論じます。
変数の関係に関する本当に詳細な情報を提供することを除き、 guard_value の最適化はとても似ています。
optimize(guard_value(V, C, [], L, Rest), PEnv, NewOp) :-
plookup(V, PEnv, Val),
(Val = const(C1) ->
NewOp = RestResidual,
NEnv = PEnv
;
write_env(PEnv, V, C, NEnv),
NewOp = guard_value(V, C, PEnv, L, RestResidual)
),
optimize(Rest, NEnv, RestResidual).
このオペレーションは、オプティマイザが後のオペレーションで定数畳み込みのために利用する定数変数を得る主な方法です。以下が部分評価との主な違いです。
- オプティマイザは開始時にいくつかの変数の値を知っています。
- トレースの最適化時、最初はどの変数の値もわかりません。
- いくつかの変数についての情報は、ガードの実行後後にのみ得られます。
今はループ文で何が起こるのかの情報が不足しています。原則として、再度ループ文に入るとそれになる。(それって何? トレース状態?)
ただし、ループ文でいくつかの追加のオペレーションが出力のために必要です。出力とは、最適化して取り去ったオペレーションとそれによって定数として割り当てられる変数の結果の値です。それが意味するところは、関係する可能性のある変数がいくつかの古い値を持っている可能性があるということです。ループの次のイテレーションは、明らかに間違っているこの古い値で続けます。従って、ループ文以前にいくつか割り当てた部分環境のエントリごとに一つ出力する必要があります。
optimize(loop, PEnv, T) :-
generate_assignments(PEnv, T).
generate_assignments([], loop).
generate_assignments([Var/Val | Tail], op1(Var, same, const(Val), T)) :-
generate_assignments(Tail, T).
どのように割り当ての生成が働くかの例としては、以下の例を見てください。部分環境が [x/5, y/10] であるときに、続く割り当てが生成されます。
?- generate_assignments([x/5, y/10], Out).
Out = op1(x, same, const(5), op1(y, same, const(10), loop)).
それらがオプティマイザのコードの全てです。一方、基本的な構造は、部分評価器とよく似ていて、複雑な部分もあまりありません。部分評価器を作るのが難しいものは、制御フローステートメントへの対処と、同じブロックが同じ定数を使って部分評価されたときはコードが再利用可能かどうかの確認と対処の両方必要です。ここでは、全ての複雑なものは置いておきます。トレーサは既に全ての制御フローを削除してガードに置換していて、一回のループオペレーションが終わっています。従って、オプティマイザは単純に 1 パスのオペレーションを実行でき、いくつかを削除します。(ループ文へのいくつかの追加のケアも行います)
この機能を使うと、前回のエントリのプロモーションの例からトレースの最適化を行えます。
?- optimize(
guard_value(x,3,[],b2,
op2(x2,mul,var(x),const(2),
op2(x3,add,var(x2),const(1),
op2(i,sub,var(i),var(x3),
op2(c,ge,var(i),const(0),
guard_true(c,[],l_done, loop)))))),
[],
LoopOut).
LoopOut = guard_value(x, 3, [], b2, op2(i, sub, var(i), const(7), op2(c, ge, var(i), const(0), guard_true(c, [x/3, x2/6, x3/7], l_done, op1(x, same, const(3), op1(x2, same, const(6), op1(x3, same, const(7), loop)))))))
より読みやすく、最適化したバージョンは以下です:
guard_value(x, 3, [], b2,
op2(i, sub, var(i), const(7),
op2(c, ge, var(i), const(0),
guard_true(c, [x/3, x2/6, x3/7], l_done,
op1(x, same, const(3),
op1(x2, same, const(6),
op1(x3, same, const(7),
loop)))))))
意図したとおり、 guard_value の後の x へのオペレーションは全て削除されます。ただし、いくつか追加された割り当て (x, x2, x3) が最終的に生成されています。この追加の変数は余分なものに見えますが、オプティマイザにはそれを簡単に認識するための十分な情報がありません。この挙動は修正できますが、より複雑にするというコストをかける必要があります。(実際のシステムでは静的単一代入形式 (static single assignment/SSA) にトレースを変換することがこの問題への解となっています)
インタプリタの再開
なぜ上記のコードは最適化できないガードのために部分環境を追加する必要があるのでしょうか? 理由は、なぜループの前に割り当てを追加しなければならないのか、ということに関連します。問題は、オプティマイザが変数の値を知るとき、オプティマイザが変数への割り当てを取り除くことにあります。それが意味することは、実行中の最適化されたトレースからインタプリタへのスイッチバックを行うときに環境の中のいくつかの変数が更新されず、インタプリタの実行が不適切に行われてしまいます。
上記の例で、これを変数 x2 と x3 に適用します。二つ目のガードが失敗したとき、最適化された場合はそれらは代入されません。従って、ガードは変数とその値(常に定数です)をリストします。
スイッチバックするとき、インタプリタ側の対応する変数に対する割り当てを作らなければいけません。従って、前回のエントリのコードに以下のように resume_interp 関数を適用する必要があります。
write_resumevars([], Env, Env).
write_resumevars([Key / Value | Rest], Env, NEnv) :-
write_env(Env, Key, Value, Env1),
write_resumevars(Rest, Env1, NEnv).
resume_interp(Env, ResumeVars, L) :-
write_resumevars(ResumeVars, Env, NEnv),
block(L, Block),
interp(Block, NEnv).
再開時に、 ResumeVars (元の部分環境) は単に元の通常環境に追加され、インタプリタに戻ります。ガードの失敗時にトレースの実行を終了し、インタプリタの実行を再開するために必要な、ガードにアタッチされたデータは、多くの場合非常に複雑なトレースシステムの一部です。ほとんどのガードが失敗しないうちはデータは大きくなる可能性があります。従って、ほとんどの実際のシステムではアタッチされるデータの困難な圧縮を試みたりその後のガードとのデータの共有を試みたりしています。
まとめ
このエントリでは、部分環境の変数を適用してトレースを最適化方法とその原理について説明しました。
- 定数引数のみを持つ全てのオペレーションを実行し、それ以外を残すこと
- 制御フローを含まないため、トレースの最適化はとても単純であること
- 制御フローに関する全ての疑問はトレーシングコンポーネントによって予め解決しているということ
次の、そしてシリーズ最後のエントリでは、小さなバイトコードインタプリタを最適化できるトレーシングと部分評価のより大きな例をお見せします。
0 件のコメント:
コメントを投稿