Частный случай достижения определения проблемы потока данных

Question

Проблема определения определений является одной из наиболее фундаментальных проблем анализа потоков данных.Учитывая график потока управления, который содержит определения и использования переменных, проблема приводит к вычислению того, какие определения переменных могут достигать определенного использования.

Например, рассмотрим график потока:

                    ____________
                 1:|   x <- ... |
                    ------------
                     |            \
                     |              __________
                     |           2:| x <- ... |
                     |              -----------
                     |            /
                    ____________    
                 3:|  ... <- x  |
                    ------------

Использованиепеременной x в блоке 3 можно получить либо из определений в блоке 1, либо из блока 2.

Алгоритм вычисления того, какие определения могут использовать, является классической проблемой потока данных.Используя нотацию из сборника драконов (новая редакция), проблема с потоком данных для определения определений выглядит следующим образом:

Область: наборы определений (например, {x <- .., ...})Направление: впередПередаточная функция: fb (x) = gen (B) U (x - kill (B)), где gen (B) - набор определений, которые генерирует блок B, и уничтожают (B) набор определений, которые убивает блок BГраница: OUT [ENTRY] = {} т.е. нет потока определений для входа в функциюОператор Meet: U (union), то есть определения, которые передаются в блок, представляют собой объединение определений из предшествующих блоков.Уравнения: OUT [B] = fb (IN [B]), IN [B] = U (P в пред.) OUT [P]Initialize: OUT [B] = {} </p>

Однако, не все определения одинаковы.Например, определение в блоке 1 может никогда не достичь использования в блоке 3, поскольку оно может быть уничтожено определением в блоке 2. С другой стороны, определение в блоке 2, если оно выполнится, сохранит свое значение до его использования в блоке.3.

Я хочу найти исчерпывающие определения использования, для которого нет определений убийства ни на одном пути от определения до использования.Мой вопрос заключается в том, существует ли подобная проблема с потоком данных (возможно, распространение и т. Д.).Как это можно решить с точки зрения анализа потока данных.

У меня есть одно возможное решение проблемы, но я бы не хотел изобретать велосипед, если решение уже существует.

Answer 1

Вот как я решил проблему. Возможно, это не самый эффективный способ, но я считаю, что это работает. Я собираюсь упомянуть проблему как проблему сохраненных определений. Сначала я вычисляю достигающие определения. Я использую алгоритм итеративного потока данных для наборов определений, представленных битовыми наборами.

Для этого мне нужно сначала вычислить gen (B) и kill (B) каждого блока. Это определения, генерируемые и уничтожаемые каждым блоком соответственно. Обратите внимание, что kill (B) является надмножеством фактического kill (B), потому что я не знаю, какие определения и из каких блоков действительно уничтожаются, поскольку я не учитываю поток данных на этом этапе.

После применения определений достижения у меня есть наборы REACH_IN (B) и REACH_OUT (B) для каждого блока в графе потока управления. Я знаю, что сохраненные определения являются подмножеством определяющих определений. Чтобы их вычислить, мне нужно выяснить, какие определения никогда не могли быть уничтожены после входа программы в каждый блок. Я буду называть эти наборы не уничтожающими наборами, и я предоставлю алгоритм для вычисления NO_KILL_IN (B) и NO_KILL_OUT (B) для каждого блока в графе. Вот алгоритм с точки зрения анализа потока данных.

Домен: наборы определений (например, {x <- .., ...}) <br /> Направление: вперед
Передаточная функция: fb (x) = x - (kill (B) ∩ REACH_IN (B)) где kill (B) - это набор определений, которые блокирует B, а REACH_IN (B) - набор определений, поступающих в B.
Граница: NO_KILL_OUT [ENTRY] = U (универсальный набор), т. Е. Все определения не уничтожаются при входе в функцию
Оператор Meet: ∩ (пересечение), то есть определение не уничтожается, если оно не уничтожается ни в одном из предшествующих блоков.
Уравнения: NO_KILL_OUT [B] = fb (IN [B]), NO_KILL_IN [B] = ∩ (P в пред.) NO_KILL_OUT [P]
Инициализировать: NO_KILL_OUT [B] = U

Обратите внимание, что в функции переноса мы вычисляем kill (B) ∩ REACH_IN (B), которая представляет собой набор фактических определений, уничтожаемых в блоке B. Если мы не будем использовать это, мы будем чрезмерно проницательны. Алгоритм вычисляет, какие определения не могли быть уничтожены до и после каждого блока, без учета того, были ли они созданы или нет. Чтобы вычислить сохраненные определения, мы просто предварительно пересечем пересечение:

PRESERVE_IN (B) = REACH_IN (B) ∩ NO_KILL_IN (B)
PRESERVE_OUT (B) = REACH_OUT (B) ∩ NO_KILL_OUT (B)

Answer 2

Вместо этого вы можете захотеть взглянуть на временную логику, логика дерева вычислений прекрасно подходит для определения свойств путей в графе потока управления. Некоторые примеры свойств потока данных в CTL показаны в этой статье:

Доказательство правильности оптимизации компилятора с помощью временной логики

Answer 3

Измените определение проблемы следующим образом:

Оператор Meet: ∩ (Пересечение), то есть определения, которые передаются в блок, являются пересечением определений из предшествующих блоков.

Уравнения:OUT [B] = fb (IN [B]), IN [B] = ∩ (P в пред.) OUT [P]