Достижение определения - Википедия - 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}} [ п]}$
• ${ displaystyle { rm {REACH}} _ { rm {out}} [S] = { rm {GEN}} [S] cup ({ rm {REACH}} _ { rm {in}} [S] - { rm {УБИЙСТВО}} [S])}$

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

Для общей инструкции мы определяем ${ displaystyle { rm {GEN}}}$ и ${ displaystyle { rm {УБИЙСТВО}}}$ устанавливает следующее:

• ${ 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.

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

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