Достижение определения - Reaching definition

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

d1: y: = 3d2: x: = y

d1 является подходящим определением для d2. Однако в следующем примере:

d1: y: = 3d2: y: = 4d3: x: = y

d1 больше не является исчерпывающим определением для d3, потому что d2 убивает его охват: значение, определенное в d1 больше не доступен и не может достичь d3.

Как анализ

Одноименный достижение определений это анализ потока данных который статически определяет, какие определения могут достигать заданного места в коде. Из-за своей простоты он часто используется в учебниках как канонический пример анализа потока данных. В оператор слияния потока данных используется набор соединений, а анализ - прямоточный. Определения достижения используются для вычисления цепочки use-def.

Уравнения потока данных, используемые для данного базового блока ${\displaystyle S}$ в достижении определений:

• ${\displaystyle {\rm {REACH}}_{\rm {in}}[S]=\bigcup _{p\in pred[S]}{\rm {REACH}}_{\rm {out}}[p]}$
• ${\displaystyle {\rm {REACH}}_{\rm {out}}[S]={\rm {GEN}}[S]\cup ({\rm {REACH}}_{\rm {in}}[S]-{\rm {KILL}}[S])}$

Другими словами, набор достигаемых определений, входящих в ${\displaystyle S}$ все определения из ${\displaystyle S}$предшественники, ${\displaystyle pred[S]}$. ${\displaystyle pred[S]}$ состоит из всех основных блоков, предшествующих ${\displaystyle S}$ в граф потока управления. Достигающие определения, исходящие из ${\displaystyle S}$ все достигают определений своих предшественников, за вычетом тех достижений определений, переменная которых уничтожена ${\displaystyle S}$ плюс любые новые определения, созданные в ${\displaystyle S}$.

Для общей инструкции мы определяем ${\displaystyle {\rm {GEN}}}$ и ${\displaystyle {\rm {KILL}}}$ устанавливает следующее:

• ${\displaystyle {\rm {GEN}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{d\}}$ , набор локально доступных определений в базовом блоке
• ${\displaystyle {\rm {KILL}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]={\rm {DEFS}}[y]-\{d\}}$, набор определений (не доступен локально, но в остальной части программы), убитый определениями в базовом блоке.

куда ${\displaystyle {\rm {DEFS}}[y]}$ это набор всех определений, которые присваиваются переменной ${\displaystyle y}$. Здесь ${\displaystyle d}$ - уникальная метка, прикрепленная к инструкции присвоения; таким образом, эти метки инструкций являются областью значений в определениях.

Алгоритм рабочего списка

Определение охвата обычно рассчитывается с использованием алгоритма итеративного рабочего списка.

Вход: граф потока управления CFG = (узлы, края, вход, выход)

// Инициализироватьза все CFG узлы п в N,    ИЗ[п] = пустой набор; // можно оптимизировать по OUT [n] = GEN [n];// помещаем все узлы в измененный набор// N - это все узлы в графе,Измененный = N;// Итерация пока (Измененный != пустой набор){    выберите а узел п в Измененный;    // удаляем его из измененного набора    Измененный = Измененный -{ п };    // init IN [n] должен быть пустым    В[п] = пустой набор;    // вычисляем IN [n] из OUT [p] предшественников    за все узлы п в предшественники(п)         В[п] = В[п] Союз ИЗ[п];    старый = ИЗ[п]; // сохраняем старый OUT [n]        // обновляем OUT [n] с помощью передаточной функции f_n ()    ИЗ[п] = GEN[п] Союз (В[п] -УБИЙСТВО[п]);    // любое изменение OUT [n] по сравнению с предыдущим значением?    если (ИЗ[п] измененный) // сравниваем oldout с OUT [n]    {            // если да, помещаем всех наследников n в измененный набор        за все узлы s в преемники(п)             Измененный = Измененный 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.

Смотрите также

• Статическая форма однократного назначения
• Доступное использование