Az SSA ( Static single assignment form ) a fordítók által használt közbenső reprezentáció , amelyben minden változó csak egyszer kap értéket . A forrásprogram-változók verziószáma általában utótag hozzáadásával történik, így minden hozzárendelés a változó egyedi verziójához történik. Az SSA ábrázolásban a DU láncok ( def -use ) kifejezetten definiáltak, és egyetlen elemet tartalmaznak.
Az SSA nézetet az IBM kutatói, Ron Cytron , Jeanne Ferrante , Barry Rosen , Mark N. Wegman és Ken Zadeck fejlesztették ki az 1980-as években .
A funkcionális programozási nyelvek , például a Scheme , ML és Haskell fordítói általában a CPS - reprezentációt ( Continuation-passing style ) használják az SSA helyett . Formálisan ezek a reprezentációk ekvivalensek, így az egyik reprezentációban megfogalmazott optimalizálás, transzformáció alkalmazható a másikra is.
Az SSA formátumú kódok esetében egyszerűbb és hatékonyabb a különféle fordítóoptimalizálások végrehajtása . Például a következő kódban:
y := 1 y := 2 x := yAz ember számára nyilvánvaló, hogy az első hozzárendelés szükségtelen, mivel a harmadik sorban használt y értéke megegyezik a második hozzárendeléssel. Ennek kiderítéséhez azonban a fordítónak az elért definíciók elemzéséhez kell folyamodnia . De az SSA reprezentációval sokkal könnyebbé válik:
y1 := 1 y2 := 2 x1 := y2Az SSA lehetővé teszi vagy nagymértékben leegyszerűsíti a következő optimalizálási algoritmusokat:
A szokásos programkód SSA-reprezentációba való fordítását úgy érjük el, hogy minden hozzárendelési műveletnél a bal oldali változót egy új változóra cseréljük. A változó értékének minden egyes használatakor az eredeti nevet a kívánt alapblokknak megfelelő „verzió” nevére cseréljük. Tekintsük a következő szabályozási folyamatgrafikont :
Az SSA definíciójának megfelelően az x változó helyett két új, x 1 és x 2 változót fogunk létrehozni . Mindegyikhez pontosan egyszer lesz hozzárendelve egy érték. Hasonló módon lecseréljük a fennmaradó változókat, ami után a következő grafikont kapjuk:
Még nem világos, hogy az alsó blokkban melyik y értéket fogják használni. Ott az y név y 1 -et és y 2 -t is jelenthet . Az ilyen jellegű kétértelműségek feloldására egy speciális Φ-függvény került be az SSA-ba. Ez a függvény létrehozza az y változó új verzióját, amelyhez az y 1 vagy y 2 értéket rendeli , attól függően, hogy a vezérlő melyik ágból származik.
Az x változón nincs szükség a Φ-függvény használatára, mivel az x-nek csak egy változata (az x 2 ) "éri el" az utolsó blokkot.
A Φ-függvény valójában nincs megvalósítva; ez csupán egy utasítás a fordítónak, hogy az argumentumlistájában felsorolt összes változót ugyanazon a helyen tárolja a memóriában (vagy regiszterben ).
Általánosabb kérdés, hogy egy adott vezérlési folyamatgráf mellett megérthető-e, hogy az SSA reprezentációjában hol és mely változókhoz szükséges Φ-függvényeket beszúrni? Erre a kérdésre a dominátorok segítségével kaphatjuk meg a választ .