В составителях , анализ живой переменный (или просто живучесть анализ ) представляет собой классический анализ потока данных для расчета переменных , которые живут в каждой точке программы. Переменная является живой в какой - то момент , если это имеет значение , которое может понадобиться в будущем, или что то же самое , если его значение может быть прочитан до следующего раза , когда переменная написанном.
Пример
Рассмотрим следующую программу:
б = 3с = 5а = е (Ь * с)
Набор живых переменных между строками 2 и 3 равен { b
, c
}, потому что оба используются в умножении в строке 3. Но набор живых переменных после строки 1 равен только { b
}, поскольку переменная c
обновляется позже, в строке 2. значение переменной a
в этом коде не используется.
Обратите внимание, что присвоение a
можно исключить, поскольку a
оно не используется позже, но недостаточно информации, чтобы оправдать удаление всей строки 3, так как это f
может иметь побочные эффекты ( b * c
возможно, печать ).
Выражение в терминах уравнений потока данных
Анализ жизнеспособности - это анализ «обратного может». Анализ производится в обратном порядке, и поток данных оператор слияния является множественным объединением . Другими словами, если применить анализ жизнеспособности к функции с определенным количеством логических ветвей внутри нее, анализ выполняется, начиная с конца функции, двигаясь к началу (отсюда «назад»), и переменная считается действующей, если любая из ветвей, движущихся вперед внутри функции, потенциально может (следовательно, «может») нуждаться в текущем значении переменной. Это контрастирует с анализом «обратное обязательство», которое вместо этого применяет это условие ко всем ветвям, движущимся вперед.
Уравнения потока данных, используемые для данного базового блока s и выходящего из блока f при анализе переменных в реальном времени, следующие:
- : Набор переменных, которые используются в s перед любым назначением.
- : Набор переменных, которым присвоено значение в s (во многих книгах [ требуется пояснение ] , KILL (s) также определяется как набор переменных, которым присвоено значение в s перед любым использованием , но это не меняет решения уравнение потока данных):
Состояние блока - это набор переменных, которые действуют в начале блока. Его исходное состояние - это набор переменных, которые находятся в его конце. Выходное состояние - это объединение внутренних состояний наследников блока. Передаточная функция оператора применяется, делая переменные, которые записываются, мертвыми, а затем делая переменные, которые читаются, активными.
Второй пример
// в: {}b1: а = 3; b = 5; d = 4; х = 100; // x никогда не используется позже, поэтому не в исходном наборе {a, b, d} если a> b, то// out: {a, b, d} // объединение всех (входящих) наследников b1 => b2: {a, b} и b3: {b, d} // в: {a, b}b2: c = a + b; d = 2;// выход: {b, d}// в: {b, d}b3: endif c = 4; вернуть b * d + c;// вне:{} |
Состояние in b3 содержит только b и d , так как c было записано. Выходное состояние b1 - это объединение внутренних состояний b2 и b3. Определение c в b2 может быть удалено, поскольку c не является действующим сразу после оператора.
Решение уравнений потока данных начинается с инициализации всех входящих и исходящих состояний пустым набором. Список работ инициализируется путем вставки точки выхода (b3) в список работ (типично для обратного потока). Его вычисленное состояние in-state отличается от предыдущего, поэтому вставляются его предшественники b1 и b2, и процесс продолжается. Прогресс суммирован в таблице ниже.
обработка | за пределами штата | старый в штате | новый в штате | список работ |
---|---|---|---|---|
b3 | {} | {} | {б, г} | (b1, b2) |
b1 | {б, г} | {} | {} | (Би 2) |
Би 2 | {б, г} | {} | {а, б} | (b1) |
b1 | {а, б, г} | {} | {} | () |
Обратите внимание, что b1 был введен в список перед b2, что заставило обработать b1 дважды (b1 был повторно введен как предшественник b2). Вставка b2 перед b1 позволила бы выполнить более раннее завершение.
Инициализация с пустым набором - оптимистическая инициализация: все переменные начинаются как мертвые. Обратите внимание, что исходящие состояния не могут сокращаться от одной итерации к следующей, хотя исходное состояние может быть меньше внутреннего. Это видно из того факта, что после первой итерации выходное состояние может измениться только изменением входящего состояния. Поскольку состояние in-state начинается с пустого набора, оно может только увеличиваться в следующих итерациях.