Definicija dostignuća

U kompilaciji, definicija dostignuća za konkretnu instrukciju je ranija instrukcija čija promenljiva može biti dodeljena (da dostigne) trenutnoj instrukciji bez spoljašnjih uticaja. Na primer, u sledećem kodu:

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

d1 je definicija dostignuća za d2. Ali, u narednom primeru:

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

d1 nije više definicija dostignuća za d3, jer d2 smanjuje njeno dostignuće: zato što vrednost definisina u d1 ne može da dostigne d3.

Kao tehnika

Slično imenovane, definicije dostignuća su tehnike u data-flow analizi koje statistički izračunavaju koje definicije će dostići koji deo koda. Zbog jednostavnosti, se često koriste kao kanonski primer data-flow analize u knjigama. Data-flow operator spajanja je skup unija koji koristi forward-flow analizu. Definicija dostignuća se koristi za računanje use-def lanaca i def-use lanca.

Data-flow jednačine korišćene za neki osnovni blok $S$ u definiciji dostignuća su:

• ${\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])$

Drugim rečima, skup definicija dostignuća koje stižu do $S$ su sve definicije dostignuća $S$-ovih prethodnika, $pred[S]$. $pred[S]$ se sastoji od osnovnih blokova koji stižu pre $S$ u grafu kontrole toka. Definicija dostignuća koja dolaze od $S$ su sve definicije dostignuća njegovih prethodnika minus one definicije dostignuća čije su promenljive ubijene od strane $S$ plus bilo koja definicija generisana u $S$.

Za obične instrukcije, definišemo skupove ${\rm {GEN}}$ i ${\rm {KILL}}$ na sledeći način:

• ${\rm {GEN}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]=\{d\}$ , skup lokalno dostupnih definicija u osnovnim blokovima
• ${\rm {KILL}}[d:y\leftarrow f(x_{1},\cdots ,x_{n})]={\rm {DEFS}}[y]-\{d\}$, skup definicija (nedostupne lokalno, ali dostupne u ostatku programa) ubijenih od strane drugih definicija u osnovnom bloku.

gde je ${\rm {DEFS}}[y]$ skup svih definicija koje zadavaju vrednost promenljivoj $y$. Ovde je $d$ jedinstvena oznaka zakačena za naredbu dodele; Dakle, domeni promenljivih u definiciji dostignuća su oznake instrukcija.

Algoritam

Definicje dostignuća su obično izračunate korišćenjem sledećeg iterativnog algoritma:

Ulaz: graf kotrole toka CFG = (Čvorovi, Ivice, Ulaz, Izlaz)

// 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 };  
  }
}

Dodatna literatura

• Aho, Alfred V.; Sethi, Ravi & Ullman, Jeffrey D. (1986). Compilers: Principles, Techniques, and Tools. Addison Wesley. ISBN 978-0-201-10088-4. 
• Appel, Andrew W. (1999). Modern Compiler Implementation in ML. Cambridge University Press. ISBN 978-0-521-58274-2. 
• Cooper, Keith D. & Torczon, Linda. (2005). Engineering a Compiler. Morgan Kaufmann. ISBN 978-1-55860-698-2. 
• Muchnick, Steven S. (1997). Advanced Compiler Design and Implementation. Morgan Kaufmann. ISBN 978-1-55860-320-2. 
• Nielson F., H.R. Nielson; , C. Hankin (2005). Principles of Program Analysis. Springer. ISBN 978-3-540-65410-0. 

Vidi još

• Static single assignment form