Jump to content

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

(Перенаправлено из Достижение определений )

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

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

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

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

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

В качестве анализа

[ редактировать ]

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

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

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

Для общей инструкции мы определяем и устанавливает следующим образом:

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

где это набор всех определений, которые присваиваются переменной . Здесь — уникальная метка, прикрепленная к инструкции назначения; таким образом, областью значений при достижении определений являются эти метки инструкций.

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

[ редактировать ]

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

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

// Initialize
for all CFG nodes n in N,
    OUT[n] = emptyset; // can optimize by OUT[n] = GEN[n];

// put all nodes into the changed set
// N is all nodes in graph,
Changed = N;

// Iterate 
while (Changed != emptyset)
{
    choose a node n in Changed;
    // remove it from the changed set
    Changed = Changed -{ n };

    // init IN[n] to be empty
    IN[n] = emptyset;

    // calculate IN[n] from predecessors' OUT[p]
    for all nodes p in predecessors(n)
         IN[n] = IN[n] Union OUT[p];

    oldout = OUT[n]; // save old OUT[n]
    
    // update OUT[n] using transfer function f_n ()
    OUT[n] = GEN[n] Union (IN[n] -KILL[n]);

    // any change to OUT[n] compared to previous value?
    if (OUT[n] changed) // compare oldout vs. OUT[n]
    {    
        // if yes, put all successors of n into the changed set
        for all nodes s in successors(n)
             Changed = Changed U { s };
    }
}

См. также

[ редактировать ]

Дальнейшее чтение

[ редактировать ]
  • Ахо, Альфред В.; Сети, Рави и Уллман, Джеффри Д. (1986). Составители: принципы, методы и инструменты . Эддисон Уэсли. ISBN  0-201-10088-6 .
  • Аппель, Эндрю В. (1999). Современная реализация компилятора в ML . Издательство Кембриджского университета. ISBN  0-521-58274-1 .
  • Купер, Кейт Д. и Торчон, Линда. (2005). Разработка компилятора . Морган Кауфманн. ISBN  1-55860-698-Х .
  • Мучник, Стивен С. (1997). Расширенное проектирование и реализация компилятора . Морган Кауфманн. ISBN  1-55860-320-4 .
  • Нильсон Ф., HR Нильсон; , К. Ханкин (2005). Принципы анализа программ . Спрингер. ISBN  3-540-65410-0 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 3f967ad2c9874745fec52632944a9027__1689068160
URL1:https://arc.ask3.ru/arc/aa/3f/27/3f967ad2c9874745fec52632944a9027.html
Заголовок, (Title) документа по адресу, URL1:
Reaching definition - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)