式木で同じ式が使われるときの先行評価について

Question

式木を最適化してるんですがかなり色々いじって思ったように変換するためのいい方法とかテクニックは独学ですがみついてきました。

今詰まっているのはif,elseブロック内を含む共通部分式の先行評価ってどういう戦略でやればいいんでしょうか？
以下の例を単純にやると

a+a==1?
	b+b==1?
		a+a
	:
		b+b
:
	a+a

を単純に先行評価すると

aa=a+a
bb=b+b
aa=1?
	bb==1?
		aa
	:
		bb
:	
　　　　aa

問題点は
aaは2回参照されることが確実なら有効だと思いますがaa==1でbb!=1の条件では1度しか使われません。
bbも2回参照されることが確実なら有効だと思いますがaa==1でbb==1の条件では1度しか使われません。
評価にコストがかかるなら遅延評価として先行評価しないというのが正しいと思いますが静的に先行評価すべきしないべきといった指針はあるのでしょうか？こういう確実に2回以上使う割れることのない式というのは共通部分式しないというのが一般的ってなにかわかりませんがそういうものなのでしょうか？

Answer 1

そういうことはJITが実行時に行っています。というのも静的には変数であっても実行時には値が更新されず実質的な定数式な場合もあるため、静的解析には限界があるためです。

質問にあるような努力をするのであれば、C#やJavaなどJIT最適化が行われるプラットフォームでなく、C++などネイティブ環境で行わないと意味がないです。

Answer 2

想定している実行環境はDynamicMethodなのですがどうも動的にアセンブリを作ってメソッド作るより速度の差から最適化が働かないようです。どの程度最適化に差があるのは調べていません。なので可能な限りJIT前に最適化したいと考えています。

なので最適化方針としてConditionExpressionの

1. IfTrueで2度以上出現する式を先行評価
2. IfFalseで2度以上出現する式を先行評価
3. Testで2度以上出現する式を先行評価
4. IfTrueとIfFalseとTest全てでそれぞれ1度以上出現する式は先行評価

するようにしたいと思います。

Answer 3

わかっててやっているのかわかりませんでしたので指摘しておきますが、

比較式・true式・false式いずれにも該当する話として、変数・フィールドの参照は副作用なく実行できますが、プロパティは単なる参照であっても副作用が含まれていることがあります。評価順序を入れ替えてしまうと見えていない副作用によって比較式の評価結果が変わることもありますし、またtrue式・false式は一方しか評価されない仕様なので、本来実行されない側の副作用によって結果が変わることもあります。

a < b ? ++a : ++b

とかもどうするつもりでしょう？

# こんなの実行時間よりも解析時間やコンパイル時間の方がよっぽど長いと思う…

Answer 4

和和和 さん、こんにちは
フォーラム オペレーターの星 睦美です。

引き続き返信がありませんので、佐祐理 さんからのアドバイスが参考になったのではないかと思います。
私のほうで[回答としてマーク] させていただきました。

今後ともMSDN フォーラムをよろしくお願いします。

---

フォーラム オペレーター　星 睦美 - MSDN Community Support

Answer 5

 星 睦美さん、遅れました。

副作用の件に関してですが今回の最適化の方針としては副作用はない、という前提で式を変形するので副作用を考慮すると結果が変わってしまうことは許容しています。

式木をExpressionメソッドではなくラムダ式で書いた場合のみを最適化対象にするため++や代入などは考慮しません。

Enumerable拡張メソッドを含む式全体を式木として書いたものを最適化するため沢山の要素に対して実行するため最適化、コンパイルの時間は相対的に小さいの十分に効果でました。