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

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

Пример

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

b = 3
c = 5
a = f(b * c)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

// in: {}; predecessor blocks: none b1: a = 3; b = 5; d = 4; x = 100; //x is never being used later thus not in the out set {a,b,d} if a > b then // out: {a,b,d} //union of all (in) successors of b1 => b2: {a,b}, and b3:{b,d} // in: {a,b}; predecessor blocks: b1 b2: c = a + b; d = 2; // out: {b,d} // in: {b,d}; predecessor blocks: b1 and b2 b3: endif c = 4; return b * d + c; // out:{}

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

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

обработка	за пределами штата	старый в штате	новый в штате	список работ
б3	{}	{}	{б, г}	(б1,б2)
б1	{б, г}	{}	{}	(б2)
б2	{б, г}	{}	{а, б}	(б1)
б1	{а, б, г}	{}	{}	()

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

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

Ссылки

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