Доступное выражение

Доступное выражение (англ. Available expression) в теории построения компиляторов — некоторое выражение $x+y$ в точке $p$ такое, что если любой путь от входного узла к $p$ вычисляет $x+y$ и после последнего вычисления до достижения $p$ нет последующих присваиваний переменным $x$ и $y$:

• Блок уничтожает выражение $x+y$, если он присваивает (или может присваивать) $x$ и $y$ и после этого не вычисляет $x+y$ заново.
• Блок генерирует выражение $x+y$, если он вычисляет $x+y$ и не выполняет последующих переопределений $x$ и $y$.

Основное применение информации о доступных выражениях — поиск глобальных общих подвыражений.

Можно вычислить множество генерируемых выражений для каждой точки блока, проходя от начала до конца блока. В точке, предшествующей блоку, сгенерированных выражений нет. Если в точке $p$ доступно множество выражений $S$, a $q$ представляет собой точку после $p$ с инструкцией $x=y+z$ между ними, то мы образуем множество доступных в $q$ выражений следующим образом:

1. Добавляем к $S$ выражение $y+z$.
2. Удаляем из $S$ все выражения, включающие переменную $x$.

Описанные действия должны выполняться в указанном порядке, так как $x$ может совпадать с $y$ или $z$. После того, как достигнут конец блока, $S$ будет представлять собой множество сгенерированных выражений блока. Множество уничтоженных выражений представляет собой множество всех выражений, например, $y+z$, таких, что $y$ или $z$ определяется в блоке, и при этом $y+z$ блоком не генерируется.

Литература

• Альфред Ахо, Моника Лам, Рави Сети, Джеффри Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. — 2-е издание. — М.: «Вильямс», 2008. — 1184 с. — 1500 экз. — ISBN 978-5-8459-1349-4.