Дефиниција достигнућа

У компилацији, дефиниција достигнућа за конкретну инструкцију је ранија инструкција чија променљива може бити додељена (да достигне) тренутној инструкцији без спољашњих утицаја. На пример, у следећем коду:

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

d1 је дефиниција достигнућа за d2. Али, у наредном примеру:

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

d1 није више дефиниција достигнућа за d3, јер d2 смањује њено достигнуће: зато што вредност дефинисина у d1 не може да достигне d3.

Као техника

Слично именоване, дефиниције достигнућа су технике у дата-флоw анализи које статистички израчунавају које дефиниције ће достићи који део кода. Због једноставности, се често користе као канонски пример дата-флоw анализе у књигама. Дата-флоw оператор спајања је скуп унија који користи форwард-флоw анализу. Дефиниција достигнућа се користи за рачунање усе-деф ланаца и деф-усе ланца.

Дата-флоw једначине коришћене за неки основни блок $S$ у дефиницији достигнућа су:

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

Другим речима, скуп дефиниција достигнућа које стижу до $S$ су све дефиниције достигнућа $S$-ових претходника, $pred[S]$. $pred[S]$ се састоји од основних блокова који стижу пре $S$ у графу контроле тока. Дефиниција достигнућа која долазе од $S$ су све дефиниције достигнућа његових претходника минус оне дефиниције достигнућа чије су променљиве убијене од стране $S$ плус било која дефиниција генерисана у $S$.

За обичне инструкције, дефинишемо скупове ${\rm {GEN}}$ и ${\rm {KILL}}$ на следећи начин:

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

где је ${\rm {DEFS}}[y]$ скуп свих дефиниција које задавају вредност променљивој $y$. Овде је $d$ јединствена ознака закачена за наредбу доделе; Дакле, домени променљивих у дефиницији достигнућа су ознаке инструкција.

Алгоритам

Дефиницје достигнућа су обично израчунате коришћењем следећег итеративног алгоритма:

Улаз: граф котроле тока ЦФГ = (Чворови, Ивице, Улаз, Излаз)

// Inicijalizacija
za sve CFG čvorove n u N, 
  OUT[n] = prazan_skup; // može se optimizovati OUT[n] = GEN[n];

// stavi sve čvorove u skup Changed
// N su svi čvorovi grafa, 
Changed = N; 

//Iteracija
while (Changed != prazan_skup)
{
  izaberu čvor n u skupu Changed;
  // Izbriši ga iz skupa Changed
  Changed = Changed - { n }; 

  // postavi IN[n] da bude prazan
  IN[n] = prazan_skup;  

  // izračunaj IN[n] od prethodnika OUT[p]
  za sve čvorove p u prethodnik(n) 
     IN[n] = IN[n] unija OUT[p]; 

  oldout = OUT[n]; // čuvamo stari OUT[n]
  
  // postavljamo OUT[n] koristeći funkciju prenosa f_n ()
  OUT[n] = GEN[n] unija (IN[n] - KILL[n]);   

  // bilo koja promena OUT[n] poredi se sa prethodnom vrednošću
  if (OUT[n] je promenjena) // poredi staru vrednost i OUT[n]
  {  
    // Ako jeste, stavi sve naslednike od n u skup Changed
    za sve čvorove s u naslednici(n) 
       Changed = Changed U { s };  
  }
}

Додатна литература

• Ахо, Алфред V.; Сетхи, Рави & Уллман, Јеффреy D. (1986). Цомпилерс: Принциплес, Тецхниqуес, анд Тоолс. Аддисон Wеслеy. ISBN 978-0-201-10088-4. 
• Аппел, Андреw W. (1999). Модерн Цомпилер Имплементатион ин ML. Цамбридге Университy Пресс. ISBN 978-0-521-58274-2. 
• Цоопер, Кеитх D. & Торцзон, Линда. (2005). Енгинееринг а Цомпилер. Морган Кауфманн. ISBN 978-1-55860-698-2. 
• Муцхницк, Стевен С. (1997). Адванцед Цомпилер Десигн анд Имплементатион. Морган Кауфманн. ISBN 978-1-55860-320-2. 
• Ниелсон Ф., Х.Р. Ниелсон; , C. Ханкин (2005). Принциплес оф Програм Аналyсис. Спрингер. ISBN 978-3-540-65410-0. 

Види још

• Статиц сингле ассигнмент форм