Анализ живых переменных

В компиляторах анализ живых переменных (или просто анализ живости ) — это классический анализ потока данных для вычисления переменных , которые являются живыми в каждой точке программы. Переменная является живой в какой-то момент, если она содержит значение , которое может понадобиться в будущем, или, что эквивалентно, если ее значение может быть прочитано до следующей записи в переменную.

Пример

Рассмотрим следующую программу:

б = 3с = 5а = f(b * с)

Набор активных переменных между строками 2 и 3 — это { b, c}, поскольку обе они используются при умножении в строке 3. Но набор активных переменных после строки 1 — это только { b}, поскольку переменная cобновляется позже, в строке 2. Значение переменной aв этом коде не используется.

Обратите внимание, что присвоение aможет быть исключено, поскольку aоно не будет использоваться в дальнейшем, но недостаточно информации, чтобы оправдать удаление всей строки 3, поскольку это fможет иметь побочные эффекты (возможно, печать b * c).

Выражение в терминах уравнений потока данных

Анализ живучести — это анализ «обратно может». Анализ выполняется в обратном порядке, а оператор слияния потока данных — set union . Другими словами, если применять анализ живучести к функции с определенным количеством логических ветвей внутри нее, анализ выполняется, начиная с конца функции, двигаясь к началу (отсюда «назад»), и переменная считается живой, если любая из ветвей, движущихся вперед внутри функции, потенциально может (отсюда «может») нуждаться в текущем значении переменной. Это контрастирует с анализом «обратно должен», который вместо этого применяет это условие ко всем ветвям, движущимся вперед.

Уравнения потока данных, используемые для заданного базового блока s и выходного блока f в анализе живых переменных, следующие:

${\displaystyle {\mbox{GEN}}[s]}$: Набор переменных, которые используются в s перед любым назначением в том же базовом блоке.

${\displaystyle {\mbox{KILL}}[s]}$: Набор переменных, которым присвоено значение в s (во многих книгах, посвященных проектированию компиляторов, KILL (s) также определяется как набор переменных, которым присвоено значение в s перед любым использованием , но это не меняет решения уравнения потока данных):

${\displaystyle {\mbox{LIVE}}_{in}[s]={\mbox{GEN}}[s]\cup ({\mbox{LIVE}}_{out}[s]-{\mbox{KILL}}[s])}$

${\displaystyle {\mbox{LIVE}}_{out}[final]={\emptyset }}$

${\displaystyle {\mbox{LIVE}}_{out}[s]=\bigcup _{p\in succ[s]}{\mbox{LIVE}}_{in}[p]}$

${\displaystyle {\mbox{GEN}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{x_{1},...,x_{n}\}}$

${\displaystyle {\mbox{KILL}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{y\}}$

Входное состояние блока — это набор переменных, которые активны в начале блока. Его выходное состояние — это набор переменных, которые активны в конце блока. Выходное состояние — это объединение входных состояний последователей блока. Передаточная функция оператора применяется путем объявления переменных, которые записываются, мертвыми, а затем объявления переменных, которые считываются, живыми.

Второй пример

Входящее состояние b3 содержит только b и d , так как c было записано. Выходное состояние b1 является объединением входящих состояний b2 и b3. Определение c в b2 можно удалить, так как c не является активным сразу после оператора.

Решение уравнений потока данных начинается с инициализации всех входящих и исходящих состояний в пустой набор. Рабочий список инициализируется путем вставки точки выхода (b3) в рабочий список (типично для обратного потока). Его вычисленное входящее состояние отличается от предыдущего, поэтому вставляются его предшественники b1 и b2, и процесс продолжается. Прогресс суммирован в таблице ниже.

Обратите внимание, что b1 был введен в список до b2, что заставило обрабатывать b1 дважды (b1 был повторно введен как предшественник b2). Вставка b2 перед b1 позволила бы выполнить завершение раньше.

Инициализация с пустым набором — это оптимистичная инициализация: все переменные изначально мертвы. Обратите внимание, что выходные состояния не могут уменьшаться от одной итерации к другой, хотя выходное состояние может быть меньше входного. Это видно из того факта, что после первой итерации выходное состояние может измениться только путем изменения входного состояния. Поскольку входное состояние изначально пустое множество, оно может только расти в дальнейших итерациях.

Ссылки

Ахо, Альфред; Лам, Моника; Сетхи, Рави; Ульман, Джеффри (2007). Составители: принципы, методы и инструменты (2-е изд.). стр. 608.