SSA ( Static single assignment form ) er en mellemrepræsentation, der bruges af compilere , hvor hver variabel kun tildeles en værdi én gang . Kildeprogramvariabler versioneres, normalt ved at tilføje et suffiks, så hver tildeling laves til en unik version af variablen. I SSA-repræsentationen er DU-kæder ( def -use ) eksplicit defineret og indeholder et enkelt element.
SSA-synet blev udviklet af IBM -forskerne Ron Cytron , Jeanne Ferrante , Barry Rosen , Mark N. Wegman og Ken Zadeck i 1980'erne .
Kompilere af funktionelle programmeringssprog som Scheme , ML og Haskell bruger normalt CPS - repræsentationen ( Continuation-passing style ) i stedet for SSA . Formelt er disse repræsentationer ækvivalente, så de optimeringer og transformationer, der er formuleret i en af repræsentationerne, kan anvendes på den anden.
For kode i SSA-form er det nemmere og mere effektivt at udføre mange slags compiler-optimeringer . For eksempel i følgende kode:
y := 1 y := 2 x := ydet er indlysende for et menneske, at den første opgave er unødvendig, da værdien af y brugt i den tredje linje svarer til den anden opgave. Men for at finde ud af dette, ville compileren være nødt til at ty til analyse af de nående definitioner . Men med SSA-repræsentationen bliver det meget nemmere:
y1 := 1 y2 := 2 x1 := y2SSA muliggør eller i høj grad forenkler følgende optimeringsalgoritmer:
Oversættelsen af den sædvanlige programkode til SSA-repræsentationen opnås ved at erstatte variablen fra venstre side med en ny variabel i hver tildelingsoperation. For hver brug af variablens værdi erstattes det oprindelige navn med navnet på den "version", der svarer til den ønskede basisblok. Overvej følgende kontrolflowgraf :
I overensstemmelse med definitionen af SSA vil vi i stedet for variablen x oprette to nye variable x 1 og x 2 . Hver af dem vil blive tildelt en værdi nøjagtigt én gang. På samme måde erstatter vi de resterende variable, hvorefter vi får følgende graf:
Det er endnu ikke klart, hvilken y-værdi der vil blive brugt i den nederste blok. Der kan navnet y både betyde y 1 og y 2 . For at løse uklarheder af denne art er der indført en særlig Φ-funktion i SSA. Denne funktion opretter en ny version af variablen y, som vil blive tildelt værdien fra enten y 1 eller y 2 , afhængigt af hvilken gren styringen kom fra.
Det er ikke nødvendigt at bruge Φ-funktionen på variablen x, da kun én version af x (nemlig x 2 ) "når" den sidste blok.
Φ-funktionen er faktisk ikke implementeret; det er blot en instruktion til compileren om at gemme alle variablerne i dens argumentliste på samme sted i hukommelsen (eller register ).
Et mere generelt spørgsmål er, om det givet en given kontrolflowgraf er muligt at forstå, hvor og for hvilke variabler i SSA-repræsentationen det er nødvendigt at indsætte Φ-funktioner? Svaret på dette spørgsmål kan fås ved hjælp af dominatorer .