algorithm - 順序付けられたツリーを有向非巡回グラフに変換するためのアルゴリズム

Question

次のように記述できるプログラミング言語があるとします。x=f（g（1）、h（1））この場合、有向非巡回グラフは、スプレッドシートのように計算の依存関係を示します（非再帰式を想定）。

 1
| \
g  h
 \ /
  f

これは単純な例ですが、DAG内でより複雑な式を「圧縮」しようとすると興味深いものになります。ここでの目標は、依存関係に基づいて再計算の数を最適化することです。

この問題に対処するために利用できるアルゴリズムと論文は何ですか？

Answer 1

もう少し具体的には、ローカル共通部分式除去です。アルゴリズムは、DragonBookの「6.1.2DAGを構築するための値-数値法」に記載されています。

Answer 2

コンパイラの作成者は、この問題を共通部分式除去と呼んでいます。その塩に値するすべてのコンパイラの教科書がこのトピックをカバーしています。

制御フローがなければ、ハッシュconsingに似た単純なことを実行できるはずです。