В теории компиляции , достижение определения для данной инструкции является ранее инструкцией, цель которого переменный может достигать (присваиваются) данные один без промежуточного назначения. Например, в следующем коде:
d1: y: = 3d2: x: = y
d1
является подходящим определением для d2
. Однако в следующем примере:
d1: y: = 3d2: y: = 4d3: x: = y
d1
больше не является достижимым определением для d3
, потому что d2
убивает его охват: значение, определенное в d1
, больше не доступно и не может быть достигнуто d3
.
Как анализ
Аналогично названные определения достижения - это анализ потока данных, который статически определяет, какие определения могут достичь заданной точки в коде. Из-за своей простоты он часто используется в учебниках как канонический пример анализа потока данных. Используемый оператор слияния потоков данных - это объединение множеств, а анализ - прямой поток. Определения достижения используются для вычисления цепочек использования-определения .
Уравнения потока данных, используемые для данного базового блока в достижении определений:
Другими словами, набор достигаемых определений, входящих в все определения из предшественники, . состоит из всех основных блоков, предшествующих в графе потока управления . Достигающие определения, исходящие из все достигают определений своих предшественников минус те, которые достигают определений, переменная которых уничтожена плюс любые новые определения, созданные в .
Для общей инструкции мы определяем а также устанавливает следующее:
- , набор локально доступных определений в базовом блоке
- , набор определений (не доступных локально, но в остальной части программы), убитых определениями в базовом блоке.
где это набор всех определений, которые присваиваются переменной . Здесь- уникальная метка, прикрепленная к инструкции присваивания; таким образом, эти метки инструкций являются областью значений в определениях.
Алгоритм рабочего списка
Определение охвата обычно рассчитывается с использованием алгоритма итеративного рабочего списка.
Вход: граф потока управления CFG = (узлы, ребра, вход, выход)
// Инициализировать для всех CFG узлов п в N , OUT [ п ] = emptyset ; // можно оптимизировать по OUT [n] = GEN [n];// помещаем все узлы в измененный набор // N - все узлы в графе, Changed = N ;// Итерация в то время как ( Измененный =! Emptyset ) { выбрать в узел п в Изменено ; // удаляем его из измененного набора 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 в преемниках ( n ) Changed = Changed U { s }; } }
дальнейшее чтение
- Ахо, Альфред V .; Сетхи, Рави и Ульман, Джеффри Д. (1986). Компиляторы: принципы, методы и инструменты . Эддисон Уэсли. ISBN 0-201-10088-6.
- Аппель, Эндрю В. (1999). Современная реализация компилятора в ML . Издательство Кембриджского университета. ISBN 0-521-58274-1.
- Купер, Кейт Д. и Торцон, Линда. (2005). Разработка компилятора . Морган Кауфманн. ISBN 1-55860-698-X.
- Мучник, Стивен С. (1997). Расширенный дизайн и реализация компилятора . Морган Кауфманн. ISBN 1-55860-320-4.
- Нильсон Ф., Х.Р. Нильсон; , К. Ханкин (2005). Принципы анализа программ . Springer. ISBN 3-540-65410-0.