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

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

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

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

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

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

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

Примечания

1. Компиляторы: принципы, технологии и инструменты, 2008, с. 735.
2. Компиляторы: принципы, технологии и инструменты, 2008, с. 736.

Литература

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