Alias ​​analys

Aliasanalys är en teknik inom kompilatorteorin , som används för att avgöra om en lagringsplats kan nås på mer än ett sätt. Två pekare sägs ha alias om de pekar på samma plats.

Aliasanalystekniker klassificeras vanligtvis efter flödeskänslighet och kontextkänslighet. De kan fastställa may-alias eller must-alias information. Termen aliasanalys används ofta omväxlande med punkt-till-analys , ett specifikt fall.

Aliasanalysatorer avser att skapa och beräkna användbar information för att förstå aliasing i program.

Översikt

I allmänhet avgör aliasanalys om separata minnesreferenser pekar på samma minnesområde eller inte. Detta gör det möjligt för kompilatorn att avgöra vilka variabler i programmet som kommer att påverkas av en sats. Tänk till exempel på följande kodavsnitt som har åtkomst till medlemmar av strukturer:

  
  
     sid  .  foo  =  1  ;  q  .  foo  =  2  ;  i  =  p  .  foo  +  3  ; 

Det finns tre möjliga aliasfall här:

1. Variablerna p och q kan inte alias (dvs. de pekar aldrig på samma minnesplats).
2. Variablerna p och q måste alias (dvs. de pekar alltid på samma minnesplats).
3. Det kan inte slutgiltigt fastställas vid kompileringstidpunkten om p och q alias eller inte.

Om p och q inte kan alias, då i = p.foo + 3; kan ändras till i = 4 . Om p och q måste alias, då i = p.foo + 3; kan ändras till i = 5 eftersom p.foo + 3 = q.foo + 3 . I båda fallen kan vi utföra optimeringar från alias-kunskapen (förutsatt att ingen annan tråd som uppdaterar samma platser kan interfoliera med den aktuella tråden, eller att språkminnesmodellen tillåter att dessa uppdateringar inte är omedelbart synliga för den aktuella tråden i frånvaro av explicita synkroniseringskonstruktioner ). Å andra sidan, om det inte är känt om p och q alias eller inte, så kan inga optimeringar utföras och hela koden måste exekveras för att få resultatet. Två minnesreferenser sägs ha en maj-alias- relation om deras alias är okänd.

Utföra aliasanalys

I aliasanalys delar vi in ​​programmets minne i aliasklasser . Aliasklasser är osammanhängande uppsättningar av platser som inte kan alias till varandra. För diskussionen här antas det att de optimeringar som görs här sker på en lågnivå mellanrepresentation av programmet. Det vill säga att programmet har kompilerats till binära operationer, hoppar, flyttar mellan register, flyttar från register till minne, flyttar från minne till register, grenar och funktionsanrop/returer.

Typbaserad aliasanalys

Om språket som kompileras är typsäkert , kompilatorns typkontroll är korrekt och språket saknar förmågan att skapa pekare som refererar till lokala variabler (som ML , Haskell eller Java ) så kan några användbara optimeringar göras. Det finns många fall där vi vet att två minnesplatser måste vara i olika aliasklasser:

1. Två variabler av olika typer kan inte vara i samma aliasklass eftersom det är en egenskap hos starkt typade, minnesreferensfria (dvs referenser till minnesplatser kan inte ändras direkt) språk som två variabler av olika typer inte kan dela samma minnesplats samtidigt.
2. Lokala tilldelningar för den aktuella stackramen kan inte vara i samma aliasklass som någon tidigare allokering från en annan stackram. Detta är fallet eftersom nya minnesallokeringar måste skiljas från alla andra minnesallokeringar.
3. Varje postfält av varje posttyp har sin egen aliasklass, i allmänhet, eftersom skrivdisciplinen vanligtvis bara tillåter poster av samma typ till alias. Eftersom alla poster av en typ kommer att lagras i ett identiskt format i minnet, kan ett fält bara alias sig själv.
4. På liknande sätt har varje array av en given typ sin egen aliasklass.

När du utför aliasanalys för kod måste varje laddning och lagring i minnet märkas med sin klass. Vi har då den användbara egenskapen, givet minnesplatserna $A_{i}$ och $B_{j}$ med $i,j$ aliasklasser, att om $i=j$ sedan $A_{i}$ kan-alias $B_{j}$ , och om $i\neq j$ kommer minnesplatserna inte alias.

Flödesbaserad aliasanalys

Analys baserad på flöde, kan appliceras på program på ett språk med referenser eller typcasting. Flödesbaserad analys kan användas i stället för eller för att komplettera typbaserad analys. I flödesbaserad analys skapas nya aliasklasser för varje minnesallokering och för varje global och lokal variabel vars adress har använts. Referenser kan peka på mer än ett värde över tiden och kan därför vara i mer än en aliasklass. Detta innebär att varje minnesplats har en uppsättning aliasklasser istället för en enda aliasklass.

Se även

• Escape analys
• Pekaranalys
• Formanalys

•   Appel, Andrew W. (1998). Modern kompilatorimplementering i ML . Cambridge, Storbritannien: Cambridge University Press. ISBN 0-521-60764-7 .

externa länkar

• Taxonomi och tillämpningar av aliasanalys - Magisteruppsats som ger en introduktion till området.