Använd-definierad kedja

Inom datavetenskap är en Use-Definition Chain ( UD Chain ) en datastruktur som består av en användning, U, av en variabel , och alla definitioner, D, av den variabeln som kan nå den användningen utan några andra mellanliggande definitioner. En UD-kedja betyder i allmänhet tilldelningen av något värde till en variabel.

En motsvarighet till en UD-kedja är en Definition-Use Chain ( DU-kedja ), som består av en definition, D, av en variabel och alla användningsområden, U, som kan nås från den definitionen utan några andra mellanliggande definitioner.

Både UD- och DU-kedjor skapas genom att använda en form av statisk kodanalys som kallas dataflödesanalys . Att känna till use-def- och def-use-kedjorna för ett program eller underprogram är en förutsättning för många kompilatoroptimeringar , inklusive konstant utbredning och eliminering av vanliga underuttryck .

Syfte

Att göra användningsdefiniera eller definiera användningskedjorna är ett steg i livskraftsanalys , så att logiska representationer av alla variabler kan identifieras och spåras genom koden.

Tänk på följande kodavsnitt:

    0    
         
 
          
  int  x  =  ;  /* A */  x  =  x  +  y  ;  /* B */  /* 1, vissa användningar av x */  x  =  35  ;  /* C */  /* 2, några fler användningsområden för x */ 

Lägg märke till att x tilldelas ett värde vid tre punkter (markerade A, B och C). Men vid punkten märkt "1" bör use-def-kedjan för x indikera att dess nuvarande värde måste ha kommit från linje B (och dess värde på linje B måste ha kommit från linje A). Tvärtom, vid punkten märkt "2", indikerar use-def-kedjan för x att dess nuvarande värde måste ha kommit från linje C. Eftersom värdet på x :et i block 2 inte beror på några definitioner i block 1 eller tidigare, x kan lika gärna vara en annan variabel där; praktiskt taget är det en annan variabel — kalla den x2 .

    0    
         
 
      
  int  x  =  ;  /* A */  x  =  x  +  y  ;  /* B */  /* 1, vissa användningar av x */  int  x2  =  35  ;  /* C */  /* 2, vissa användningsområden för x2 */ 

Processen att dela upp x i två separata variabler kallas live range-delning. Se även statisk singeluppgiftsblankett .

Uppstart

Listan med påståenden bestämmer en stark ordning bland påståenden.

• Påståenden är märkta med följande konventioner: $s(i)$ , där i är ett heltal i $[1,n]$ ; och n är antalet påståenden i grundblocket
• Variabler identifieras i kursiv stil (t.ex. v , u och t )
• Varje variabel antas ha en definition i sammanhanget eller omfattningen. (I statisk enkel tilldelningsform är användningsdefinierade kedjor explicita eftersom varje kedja innehåller ett enda element.)

För en variabel, såsom v , identifieras dess deklaration som V (kursiv versal), och kort sagt identifieras dess deklaration som $s(0)$ . I allmänhet kan en deklaration av en variabel vara i ett yttre omfång (t.ex. en global variabel ).

Definition av en variabel

När en variabel, v , finns på LHS för en tilldelningssats, såsom ${\displaystyle s(j)} ,$ då är $s(j)$ en definition av v . Varje variabel ( v ) har åtminstone en definition genom sin deklaration ( V ) (eller initialisering).

Användning av en variabel

Om variabeln, v , finns på RHS för sats $s(j)$ , finns det en sats, $s(i)$ med i < j och $\min(ji)$ , att det är en definition av v och det har en användning vid $s(j)$ (eller, kort sagt, när en variabel, v , är på RHS för ett påstående $s(j)$ , då har v en användning vid sats $s(j)$ ).

Avrättning

Betrakta den sekventiella exekveringen av listan med satser, $s(i)$ , och vad som nu kan observeras som beräkningen vid sats, j :

• En definition vid sats $s(i)$ med i < j är levande vid j , om den har en användning vid en sats $s(k)$ med k ≥ j . Uppsättningen av levande definitioner vid påstående i betecknas som $A(i)$ och antalet levande definitioner som $|A(i)|$ . ( $A(i)$ är ett enkelt men kraftfullt koncept: teoretiska och praktiska resultat i rymdkomplexitetsteori , åtkomstkomplexitet (I/O-komplexitet), registerallokering och exploatering av cachelokalitet är baserade på $A(i)$ .)
• En definition vid sats $s(i)$ dödar alla tidigare definitioner ( $s(k)$ med k < i ) för samma variabler.

Exekveringsexempel för def-use-chain

Detta exempel är baserat på en Java-algoritm för att hitta gcd . (Det är inte viktigt att förstå vad den här funktionen gör.)

      
       
        
       0
         
       0  
           
                
        
                
     
      
 /**  * @param(a, b) Värdena som används för att beräkna divisorn.  * @return Den största gemensamma delaren för a och b.  */  int  gcd  (  int  a  ,  int  b  )  {  int  c  =  a  ;  int  d  =  b  ;  if  (  c  ==  )  returnera  d  ;  while  (  d  !=  )  {  if  (  c  >  d  )  c  =  c  -  d  ;  annars  d  =  d  -  c  ;  }  returnera  c  ;  } 

För att ta reda på alla def-use-kedjor för variabel d, gör följande steg:

1. Sök efter första gången variabeln definieras (skrivåtkomst).

   I det här fallet är det " d=b " (l.7)

2. Sök efter första gången variabeln läses.

   I det här fallet är det " retur d "

3. Skriv ner denna information i följande stil: [namnet på variabeln du skapar en def-use-kedja för, den konkreta skrivåtkomsten, den konkreta läsbehörigheten] I det här fallet är det: [d, d=b,

   return d ]

Upprepa dessa steg i följande stil: kombinera varje skrivåtkomst med varje läsbehörighet (men INTE tvärtom).

Resultatet bör bli:

     
   0 
    
    
   
   0 
    
    
    [  d  ,  d  =  b  ,  returnera  d  ]  [  d  ,  d  =  b  ,  medan  (  d  !=  ) ]  [  d  ,  d  =  b  ,  om  (  c  >  d  ) ]  [  d  ,  d  =  b  ,  c  =  c  -  d  ]  [  d  ,  d  =  b  ,  d  =  d  -  c  ]  [  d  ,  d  =  d  -  c  ,  medan  (  d  !=  ) ]  [  d  ,  d  =  d  -  c  ,  om  (  c  >  d  ) ]  [  d  ,  d  =  d  -  c  ,  c  =  c  -  d  ]  [  d  ,  d  =  d  -  c  ,  d  =  d  -  c  ] 

Du måste vara försiktig om variabeln ändras med tiden.

Till exempel: Från rad 7 ner till rad 13 i källkoden, d omdefinieras/ändras inte. Vid linje 14 d omdefinieras. Det är därför du måste kombinera denna skrivåtkomst på d med alla möjliga läsåtkomster som kan nås. I detta fall är endast koden bortom rad 10 relevant. Linje 7 kan till exempel inte nås igen. För din förståelse kan du föreställa dig 2 olika variabler d :

     
   0 
    
    
   
   0 
    
    
   [  d1  ,  d1  =  b  ,  returnera  d1  ]  [  d1  ,  d1  =  b  ,  medan  (  d1  !=  ) ]  [  d1  ,  d1  =  b  ,  if  (  c  >  d1  ) ]  [  d1  ,  d1  =  b  ,  c  =  c  -  d1  ]  [  d1  ,  d1  =  b  ,  d1  =  d1  -  c  ]  [  d2  ,  d2  =  d2  -  c  ,  medan  (  d2  !=  ) ]  [  d2  ,  d2  =  d2  -  c  ,  if  (  c  >  d2  ) ]  [  d2  ,  d2  =  d2  -  c  ,  c  =  c  -  d2  ]  [  d2  ,  d2  =  d2  -  c  ,  d2  =  d2  -  c  ]  

Som ett resultat kan du få något liknande. Variabeln d1 skulle ersättas med b

     
       
      
       0
         
       0 
            
                
              
        
        
                
           0  
               
                    
            
                    
        
     
      
 /**  * @param(a, b) Värdena som används för att beräkna divisorn.  * @return Den största gemensamma delaren för a och b.  **/  int  gcd  (  int  a  ,  int  b  )  {  int  c  =  a  ;  int  d  ;  if  (  c  ==  )  returnera  b  ;  if  (  b  !=  )  {  if  (  c  >  b  )  {  c  =  c  -  b  ;  d  =  b  ;  }  annat  d  =  b  -  c  ;  while  (  d  !=  )  {  if  (  c  >  d  )  c  =  c  -  d  ;  annars  d  =  d  -  c  ;  }  }  returnera  c  ;  } 

Metod för att bygga en use-def (eller ud ) kedja

1. Ange definitioner i satsen $s(0)$
2. För varje i i $[1,n]$ , hitta levande definitioner som har användning i satsen $s(i)$
3. Gör en länk mellan definitioner och användningsområden
4. Ställ in satsen $s(i)$ , som definitionssats
5. Döda tidigare definitioner

Med denna algoritm uppnås två saker:

1. En riktad acyklisk graf (DAG) skapas på variabelanvändningar och definitioner. DAG specificerar ett databeroende bland tilldelningssatser, såväl som en partiell ordning (därför parallellitet mellan satser).
2. När satsen $s(i)$ nås, finns det en lista med levande variabeltilldelningar. Om bara en tilldelning är live, till exempel, konstant spridning användas.