SSA ( Static single assignment form ) är en mellanrepresentation som används av kompilatorer , där varje variabel endast tilldelas ett värde en gång . Källprogramvariabler versioneras, vanligtvis genom att lägga till ett suffix, så att varje tilldelning görs till en unik version av variabeln. I SSA-representationen är DU-kedjor ( def -use ) uttryckligen definierade och innehåller ett enda element.
SSA-vyn utvecklades av IBM -forskarna Ron Cytron , Jeanne Ferrante , Barry Rosen , Mark N. Wegman och Ken Zadeck på 1980 - talet .
Kompilatorer av funktionella programmeringsspråk som Scheme , ML och Haskell använder vanligtvis CPS - representationen ( Continuation-passing style ) istället för SSA . Formellt är dessa representationer likvärdiga, så de optimeringar och transformationer som formulerats i en av representationerna kan tillämpas på den andra.
För kod i SSA-form är det enklare och mer effektivt att utföra många typer av kompilatoroptimeringar . Till exempel i följande kod:
y := 1 y := 2 x := ydet är uppenbart för en människa att den första uppgiften är onödig, eftersom värdet på y som används i den tredje raden motsvarar den andra uppgiften. Men för att ta reda på detta måste kompilatorn tillgripa analys av de uppnående definitionerna . Men med SSA-representationen blir det mycket lättare:
y1 := 1 y2 := 2 x1 := y2SSA möjliggör eller avsevärt förenklar följande optimeringsalgoritmer:
Översättningen av den vanliga programkoden till SSA-representationen uppnås genom att variabeln från vänster sida ersätts med en ny variabel i varje tilldelningsoperation. För varje användning av variabelns värde ersätts det ursprungliga namnet med namnet på "versionen" som motsvarar det önskade basblocket. Tänk på följande kontrollflödesdiagram :
I enlighet med definitionen av SSA kommer vi istället för variabeln x att skapa två nya variabler x 1 och x 2 . Var och en av dem kommer att tilldelas ett värde exakt en gång. På samma sätt ersätter vi de återstående variablerna, varefter vi får följande graf:
Det är ännu inte klart vilket y-värde som kommer att användas i det nedre blocket. Där kan namnet y betyda antingen y 1 eller y 2 . För att lösa otydligheter av detta slag har en speciell Φ-funktion införts i SSA. Denna funktion skapar en ny version av variabeln y, som kommer att tilldelas värdet från antingen y 1 eller y 2 , beroende på vilken gren kontrollen kom från.
Det finns inget behov av att använda Φ-funktionen på variabeln x, eftersom endast en version av x (nämligen x 2 ) "når" det sista blocket.
Φ-funktionen är faktiskt inte implementerad; det är bara en instruktion till kompilatorn att lagra alla variabler listade i dess argumentlista på samma plats i minnet (eller register ).
En mer generell fråga är om det, givet en given kontrollflödesgraf, är möjligt att förstå var och för vilka variabler i SSA-representationen det är nödvändigt att infoga Φ-funktioner? Svaret på denna fråga kan erhållas med hjälp av dominatorer .