В теории компиляторов достигающее определение для данной инструкции — это более ранняя инструкция, целевая переменная которой может достичь (быть назначена) данной без промежуточного назначения. Например, в следующем коде:
d1 : у := 3d2 : х := у
d1является идущим определением для d2. В следующем примере, однако:
d1 : у := 3d2 : у := 4d3 : х := у
d1больше не является определением достижения для d3, поскольку d2убивает его достижение: значение, определенное в , d1больше недоступно и не может достичь d3.
Аналогично названные определения достижения — это анализ потока данных , который статически определяет, какие определения могут достичь заданной точки в коде. Из-за своей простоты он часто используется как канонический пример анализа потока данных в учебниках. Используемый оператор слияния потока данных — это объединение множеств, а анализ — прямой поток. Определения достижения используются для вычисления цепочек использования-определений .
Уравнения потока данных, используемые для данного базового блока при достижении определений, следующие:
Другими словами, набор достигающих определений, входящих в , — это все достигающие определения из предшественников . состоит из всех базовых блоков, которые идут до этого в графе потока управления . Достигающие определения, выходящие из , — это все достигающие определения его предшественников за вычетом тех достигающих определений, переменная которых уничтожается , плюс любые новые определения, сгенерированные внутри .
Для общей инструкции мы определяем наборы и следующим образом:
где — множество всех определений, которые присваиваются переменной . Здесь — уникальная метка, прикрепленная к инструкции присваивания; таким образом, область значений при достижении определений — это эти метки инструкций.
Достижение определения обычно рассчитывается с использованием итеративного алгоритма рабочего списка.
Вход: граф потока управления CFG = (Узлы, Ребра, Вход, Выход)
![{\displaystyle {\rm {REACH}}_{\rm {in}}[S]=\bigcup _{p\in pred[S]}{\rm {REACH}}_{\rm {out}}[p]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/88d90a4df4dc3fd7d5f07094e1c86593b00e56c2)
![{\displaystyle {\rm {REACH}}_{\rm {out}}[S]={\rm {GEN}}[S]\cup ({\rm {REACH}}_{\rm {in}}[S]-{\rm {KILL}}[S])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fc62c65a0828cf46b792d3a87e3cffc4161382f0)
![{\displaystyle pred[S]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/14ff3a07bc9cc297ab8420c3251155d4b066f742)
![{\displaystyle {\rm {GEN}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{d\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ff7f9be7d2dc36f753cceeddbbef71e9fab32e1a)
![{\displaystyle {\rm {KILL}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]={\rm {DEFS}}[y]-\{d\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2da33640a2d7c543238f975c03ffdc9caeb4481a)
![{\displaystyle {\rm {DEFS}}[y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ac2a74eaf464d0299fede5fd0aa0868aa2f78ad)
// Инициализация для всех узлов CFG n в N , OUT [ n ] = emptyset ; // можно оптимизировать с помощью OUT[n] = GEN[n]; // помещаем все узлы в измененный набор // N — все узлы в графе, Changed = N ; // Итерация while ( Changed != emptyset ) { выбрать узел n в Changed ; // удалить его из измененного набора Changed = Changed - { n } ; // инициализируем IN[n] как пустой IN [ n ] = emptyset ; // вычислить IN[n] из OUT[p] предшественников для всех узлов p в предшественниках ( n ) IN [ n ] = IN [ n ] Union OUT [ p ]; oldout = OUT [ n ]; // сохраняем старый OUT[n] // обновляем OUT[n] с помощью передаточной функции f_n() OUT [ n ] = GEN [ n ] Union ( IN [ n ] - KILL [ n ]); // есть ли изменения в OUT[n] по сравнению с предыдущим значением? if ( OUT [ n ] changed ) // сравнить oldout с OUT[n] { // если да, поместить всех последователей n в измененный набор для всех узлов s в successors ( n ) Changed = Changed U { s }; } }