Dosažení definice - Reaching definition - Wikipedia

v teorie překladače, a dosažení definice pro danou instrukci je dřívější instrukce, jejíž cílová proměnná může dosáhnout (přiřadit jí) danou instrukci bez vedlejšího přiřazení. Například v následujícím kódu:

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

d1 je dosažitelná definice pro d2. V následujícím příkladu však:

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

d1 již není definicí pro d3, protože d2 zabije jeho dosah: hodnota definovaná v d1 již není k dispozici a nelze jej dosáhnout d3.

Jako analýza

Podobně pojmenovaný dosažení definic je analýza toku dat který staticky určuje, které definice mohou dosáhnout určitého bodu v kódu. Kvůli své jednoduchosti se často používá jako kanonický příklad analýzy toku dat v učebnicích. The operátor soutoku datových toků used is set union, and the analysis is forward flow. Dosahující definice se používají k výpočtu řetězce použití-def.

Rovnice toku dat použité pro daný základní blok ${ displaystyle S}$ při dosahování definic jsou:

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

Jinými slovy, soubor dosažitelných definic ${ displaystyle S}$ jsou všechny dosažitelné definice z ${ displaystyle S}$předchůdci, ${ displaystyle pred [S]}$. ${ displaystyle pred [S]}$ se skládá ze všech základních bloků, které přicházejí dříve ${ displaystyle S}$ v kontrolní tokový graf. Dosahující definice vycházející z ${ displaystyle S}$ všechny dosahují definic svých předchůdců minus ty, které dosahují definic, jejichž proměnná je zabita ${ displaystyle S}$ plus všechny nové definice generované v rámci ${ displaystyle S}$.

Pro obecnou instrukci definujeme ${ displaystyle { rm {GEN}}}$ a ${ displaystyle { rm {ZABÍT}}}$ nastavuje takto:

• ${ displaystyle { rm {GEN}} [d: y leftarrow f (x_ {1}, cdots, x_ {n})] = {d }}$ , sada lokálně dostupných definic v základním bloku
• ${ displaystyle { rm {KILL}} [d: y leftarrow f (x_ {1}, cdots, x_ {n})] = { rm {DEFS}} [y] - {d }}$, soubor definic (není k dispozici místně, ale ve zbytku programu) zabitý definicemi v základním bloku.

kde ${ displaystyle { rm {DEFS}} [y]}$ je sada všech definic, které jsou proměnné přiřazeny ${ displaystyle y}$. Tady ${ displaystyle d}$ je jedinečný štítek připojený k přiřazovací instrukci; tedy doménou hodnot při dosahování definic jsou tyto návěští instrukcí.

Algoritmus pracovního seznamu

Dosažení definice se obvykle počítá pomocí iteračního algoritmu pracovního seznamu.

Vstup: kontrolní vývojový graf CFG = (uzly, hrany, vstup, výstup)

// Inicializovatpro Všechno CFG uzly n v N,    VEN[n] = prázdná; // lze optimalizovat pomocí OUT [n] = GEN [n];// vloží všechny uzly do změněné sady// N jsou všechny uzly v grafu,Změněno = N;// Opakovat zatímco (Změněno != prázdná){    Vybrat A uzel n v Změněno;    // odebrat ze změněné sady    Změněno = Změněno -{ n };    // init IN [n] být prázdný    V[n] = prázdná;    // vypočítat IN [n] z OUT předchůdců [p]    pro Všechno uzly p v předchůdci(n)         V[n] = V[n] svaz VEN[p];    oldout = VEN[n]; // uložit staré OUT [n]        // aktualizace OUT [n] pomocí přenosové funkce f_n ()    VEN[n] = GEN[n] svaz (V[n] -ZABÍT[n]);    // nějaká změna OUT [n] ve srovnání s předchozí hodnotou?    -li (VEN[n] změněno) // porovnat oldout vs. OUT [n]    {            // pokud ano, vložte všechny nástupce n do změněné množiny        pro Všechno uzly s v nástupci(n)             Změněno = Změněno U { s };    }}

Další čtení

• Aho, Alfred V .; Sethi, Ravi & Ullman, Jeffrey D. (1986). Překladače: Zásady, techniky a nástroje. Addison Wesley. ISBN  0-201-10088-6.
• Appel, Andrew W. (1999). Moderní implementace kompilátoru v ML. Cambridge University Press. ISBN  0-521-58274-1.
• Cooper, Keith D. & Torczon, Linda. (2005). Inženýrství překladače. Morgan Kaufmann. ISBN  1-55860-698-X.
• Muchnick, Steven S. (1997). Pokročilý návrh a implementace kompilátoru. Morgan Kaufmann. ISBN  1-55860-320-4.
• Nielson F., H. R. Nielson; , C. Hankin (2005). Principy programové analýzy. Springer. ISBN  3-540-65410-0.

Viz také

• Statický jednotný formulář přiřazení
• Dosažitelné použití