Алгоритмы преобразования упорядоченного дерева в ориентированный ациклический граф

Question

Допустим, у меня есть язык программирования, на котором я могу написать: x = f (g (1), h (1)), в этом случае ориентированный ациклический граф покажет зависимости вычисления, как в электронной таблице (при условии, что не рекурсивновыражения):

 1
| \
g  h
 \ /
  f

Это простой пример, но он оказывается интересным при попытке "сжать" более сложные выражения в группе обеспечения доступности баз данных.Целью здесь является оптимизация количества пересчетов на основе зависимостей.

Какие алгоритмы и статьи доступны для решения этой проблемы?

Answer 1

Немного конкретнее, это локальное устранение общего выражения. Алгоритм приведен в Dragon Book , «6.1.2 Метод числа-значений для построения DAG» *

Answer 2

Авторы компиляторов называют эту проблему устранение общего подвыражения .Эту тему освещает каждый учебник по компиляторам.

Без управления потоком вы сможете сделать что-то простое, похожее на хеш-код .