Nå definition

I kompilatorteori är en nå-definition för en given instruktion en tidigare instruktion vars målvariabel kan nå (tilldelas) den givna utan en mellanliggande tilldelning. Till exempel i följande kod:

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

d1 är en räckande definition för d2 . Men i följande exempel:

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

d1 är inte längre en räckviddsdefinition för d3 , eftersom d2 dödar dess räckvidd: värdet definierat i d1 är inte längre tillgängligt och kan inte nå d3 .

Som analys

De på liknande sätt namngivna nå-definitionerna är en dataflödesanalys som statiskt bestämmer vilka definitioner som kan nå en given punkt i koden. På grund av sin enkelhet används den ofta som det kanoniska exemplet på en dataflödesanalys i läroböcker. Den dataflödeskonfluensoperator som används är set union, och analysen är framåtflöde. Reaching-definitioner används för att beräkna use-def-kedjor .

Dataflödesekvationerna som används för ett givet grundblock $S$ för att nå definitioner är:

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

Med andra ord, uppsättningen av att nå definitioner som går in i $S$ är alla nåde definitioner från $S$ s föregångare, $pred[S]$ . $pred[S]$ består av alla de grundläggande blocken som kommer före $S$ i kontrollflödesdiagrammet . De nå-definitioner som kommer ut från $S$ är alla nå-definitioner av dess föregångare minus de som når definitioner vars variabel dödas av $S$ plus eventuella nya definitioner som genereras inom $S$ .

För en generisk instruktion definierar vi ${\rm {GEN}}$ och ${\rm {KILL}}$ enligt följande:

${\rm {GEN}}[d:y\leftarrow f(x_{1},\cdots ,x_ {n})]=\{d\}$ , en uppsättning lokalt tillgängliga definitioner i ett grundläggande block
${\displaystyle {\rm {KILL}}[d:y\leftarrow f( x_{1},\cdots ,x_{n})]={\rm {DEFS}}[y]-\{d\}} , en$ uppsättning definitioner (inte lokalt tillgängliga, men i resten av programmet) dödade av definitioner i grundblocket.

där ${\rm {DEFS}}[y]$ är uppsättningen av alla definitioner som tilldelar variabeln $y$ . Här $d$ en unik etikett kopplad till tilldelningsinstruktionen; sålunda är domänen av värden för att nå definitioner dessa instruktionsetiketter.

Arbetslista algoritm

Reaching definition beräknas vanligtvis med hjälp av en iterativ arbetslistalgoritm.

Ingång: kontrollflödesdiagram CFG = (Noder, Edges, Entry, Exit)


      
       



  


   

         
    
         

    
      

    
         
             

       
    
    
         

    
       
        
        
             
                   
    
 // Initiera  för  alla  CFG-  noder  n  i  N  ,  OUT  [  n  ]  =  tomt uppsättning  ;  // kan optimera med OUT[n] = GEN[n];  // lägg alla noder i den ändrade mängden  // N är alla noder i grafen,  Ändrad  =  N  ;  // Iterate  while  (  Changed  !=  emptyset  )  {  välj  en  nod  n  i  Changed  ;  // ta bort den från den ändrade uppsättningen  Ändrad  =  Ändrad  -  {  n  };  // init IN[n] att vara tom  IN  [  n  ]  =  tomt uppsättning  ;  // beräkna IN[n] från föregångares OUT[p]  för  alla  noder  p  i  föregångare  (  n  )  IN  [  n  ]  =  IN  [  n  ]  Union  OUT  [  p  ];  oldout  =  UT  [  n  ];  // spara gammal UT[n]  // uppdatera UT[n] med hjälp av överföringsfunktionen f_n ()  UT  [  n  ]  =  GEN  [  n  ]  Union  (  IN  [  n  ]  -  DÖDA  [  n  ]);  // någon förändring av OUT[n] jämfört med tidigare värde?  if  (  OUT  [  n  ]  ändrad  )  // jämför oldout vs. OUT[n]  {  // om ja, lägg in alla efterföljare av n i den ändrade uppsättningen  för  alla  noder  s  i  efterföljare  (  n  )  Changed  =  Changed  U  {  s  };  }  }

Se även

Vidare läsning

Aho, Alfred V.; Sethi, Ravi & Ullman, Jeffrey D. (1986). Kompilatorer: principer, tekniker och verktyg . Addison Wesley. ISBN 0-201-10088-6 .
Appel, Andrew W. (1999). Modern kompilatorimplementering i ML . Cambridge University Press. ISBN 0-521-58274-1 .
Cooper, Keith D. & Torczon, Linda. (2005). Konstruera en kompilator . Morgan Kaufmann. ISBN 1-55860-698-X .
Muchnick, Steven S. (1997). Avancerad kompilatordesign och implementering . Morgan Kaufmann. ISBN 1-55860-320-4 .
Nielson F., HR Nielson; , C. Hankin (2005). Principer för programanalys . Springer. ISBN 3-540-65410-0 .