Flyktanalys

Vid kompilatoroptimering är escape-analys en metod för att bestämma pekarnas dynamiska omfattning – där i programmet en pekare kan nås . Det är relaterat till pekareanalys och formanalys .

När en variabel (eller ett objekt) allokeras i en subrutin , kan en pekare till variabeln försvinna till andra exekveringstrådar eller till anropande av subrutiner. Om en implementering använder slutanropsoptimering (vanligtvis krävs för funktionella språk ), kan objekt också ses som att fly till anropade subrutiner. Om ett språk stöder förstklassiga fortsättningar (som Scheme och Standard ML i New Jersey ), kan delar av samtalsstacken också komma ut.

Om en subrutin allokerar ett objekt och returnerar en pekare till det, kan objektet nås från obestämda platser i programmet – pekaren har "rymt". Pekare kan också escape om de lagras i globala variabler eller andra datastrukturer som i sin tur undkommer den aktuella proceduren.

Escape-analys avgör alla platser där en pekare kan lagras och om pekarens livslängd kan bevisas vara begränsad endast till den aktuella proceduren och/eller tråden.

Optimeringar

En kompilator kan använda resultaten av escape-analys som grund för optimeringar:

• Konvertera heap-allokeringar till stack-allokeringar . Om ett objekt allokeras i en subrutin och en pekare till objektet aldrig försvinner, kan objektet vara en kandidat för stackallokering istället för heapallokering. I sopsamlade språk kan detta minska hur ofta insamlaren behöver köra.
• Synkronisering elision . Om ett objekt visar sig vara tillgängligt endast från en tråd, kan operationer på objektet utföras utan synkronisering.
• Dela upp föremål eller skalär ersättning . Ett objekt kan hittas att nås på sätt som inte kräver att objektet existerar som en sekventiell minnesstruktur. Detta kan tillåta att delar (eller hela) av objektet lagras i CPU-register istället för i minnet.

Praktiska överväganden

I objektorienterade programmeringsspråk är dynamiska kompilatorer särskilt bra kandidater för att utföra escape-analys. I traditionell statisk kompilering kan metodöverstyrning göra escape-analys omöjlig, eftersom vilken metod som helst kan åsidosättas av en version som tillåter en pekare att escape . Dynamiska kompilatorer kan utföra escape-analyser med hjälp av tillgänglig information om överbelastning och göra om analysen när relevanta metoder åsidosätts av dynamisk kodladdning.

Populariteten för programmeringsspråket Java har gjort escape-analys till ett mål av intresse. Javas kombination av heap-only-objektallokering, inbyggd trådning, Sun HotSpots dynamiska kompilator och OpenJ9 :s just-in-time kompilator ( JIT) skapar en kandidatplattform för escape-analysrelaterade optimeringar (se Escape-analys i Java ). Escape-analys är implementerad i Java Standard Edition 6. Vissa JVM:er stöder en starkare variant av escape-analys som kallas partiell escape-analys som gör skalär ersättning av ett allokerat objekt möjligt även om objektet escapes i vissa sökvägar av en funktion.

Exempel (Java)

  
         
        
    
        
             
             
        
    


  

  
      
        
          
    
 class  Main  {  public  static  void  main  (  String  []  args  )  {  exempel  ();  }  public  static  void-  exempel  ()  {  Foo  foo  =  new  Foo  ();  //alloc  Bar  bar  =  new  Bar  ();  //alloc  bar  .  setFoo  (  foo  );  }  }  klass  Foo  {}  klass  Bar  {  privat  Foo  foo  ;  public  void  setFoo  (  Foo  foo  )  {  detta  .  foo  =  foo  ;  }  } 

I det här exemplet skapas två objekt (kommenteras med alloc), och ett av dem ges som argument till en annan metod. Metoden setFoo() lagrar en referens till ett mottaget Foo-objekt. Om Bar-objektet fanns på högen skulle hänvisningen till Foo försvinna. Men i det här fallet kan en kompilator fastställa, med escape-analys, att Bar-objektet självt inte undkommer anropet av example() . Som ett resultat kan referensen till Foo inte heller undkomma, och kompilatorn kan säkert allokera båda objekten i stacken.

Exempel (schema)

I följande exempel flyr vektorn p inte in i g , så den kan allokeras på stacken och sedan tas bort från stacken innan g anropas .

 
    
       
         (  definiera  (  f  x  )  (  låt  ((  p  (  gör-vektor  10000  )))  (  fyll-vektor-med-bra-grejer  p  )  (  g  (  vektor-ref  p  7023  )))) 

Om vi ​​däremot hade

 
    
       
        (  definiera  (  f  x  )  (  låt  ((  p  (  gör-vektor  10000  )))  (  fyll-vektor-med-bra-grejer  p  )  (  g  p  ))) 

då skulle antingen p behöva allokeras på högen eller (om g är känt för kompilatorn när f kompileras och fungerar bra) allokeras på stacken på ett sådant sätt att den kan förbli på plats när g anropas.

Om fortsättningar används för att implementera undantagsliknande kontrollstrukturer, kan escape-analys ofta upptäcka detta för att undvika att faktiskt allokera en fortsättning och kopiera anropsstacken till den. Till exempel i

  
    
        
          
              
               
              
     ;;Läser schemaobjekt som angetts av användaren. Om alla är siffror,   returnerar ;; en lista som innehåller alla i ordning. Om användaren anger ett som   ;;inte är ett tal, returnerar omedelbart #f.  (  definiera  (  getnumlist  )  (  call/cc  (  lambda  (  fortsättning  )  (  define  (  get-numbers  )  (  låt  ((  nästa-objekt  (  läs  )))  (  cond  ((  eof-object?  nästa-objekt  )  '  ())  ( (  nummer?  nästa-objekt  )  (  nackdelar  nästa-objekt  (  get-nummer )  ))  (  annars  (  fortsättning  # f  ))))  (  get-nummer )  ))) 

escape-analys kommer att avgöra att fortsättningen som fångas upp av call/cc inte escape, så ingen fortsättningsstruktur behöver allokeras, och att anropa fortsättningen genom att anropa fortsättning kan implementeras genom att avveckla stacken.

Se även

• Alias ​​analys
• Pekaranalys
• Formanalys