SSA ( Static single assignment form ) on kääntäjien käyttämä väliesitys , jossa kullekin muuttujalle annetaan arvo vain kerran . Lähdeohjelman muuttujat versioitetaan, yleensä lisäämällä pääte, niin että jokainen määritys tehdään muuttujan yksilölliseen versioon. SSA-esityksessä DU-ketjut ( def - use ) on määritelty eksplisiittisesti ja sisältävät yhden elementin.
SSA-näkymän kehittivät IBM :n tutkijat Ron Cytron , Jeanne Ferrante , Barry Rosen , Mark N. Wegman ja Ken Zadeck 1980 - luvulla .
Toiminnallisten ohjelmointikielten , kuten Scheme , ML ja Haskell , kääntäjät käyttävät yleensä CPS - esitystä ( Continuation-passing style ) SSA:n sijaan . Muodollisesti nämä esitykset ovat ekvivalentteja, joten yhdessä esityksessä muotoiltuja optimointeja ja muunnoksia voidaan soveltaa toiseen.
SSA-muodossa olevalle koodille on helpompaa ja tehokkaampaa suorittaa monenlaisia kääntäjien optimointeja . Esimerkiksi seuraavassa koodissa:
v := 1 v := 2 x := yihmiselle on selvää, että ensimmäinen tehtävä on tarpeeton, koska kolmannella rivillä käytetty y:n arvo vastaa toista tehtävää. Tämän selvittämiseksi kääntäjän olisi kuitenkin turvauduttava saavuttavien määritelmien analyysiin . Mutta SSA-edustuksen avulla siitä tulee paljon helpompaa:
y1 := 1 y2 := 2 x1 := y2SSA mahdollistaa tai yksinkertaistaa suuresti seuraavat optimointialgoritmit:
Tavanomaisen ohjelmakoodin käännös SSA-esitykseen saadaan aikaan korvaamalla vasemman puolen muuttuja uudella muuttujalla jokaisessa osoitusoperaatiossa. Jokaisen muuttujan arvon käytön yhteydessä alkuperäinen nimi korvataan haluttua peruslohkoa vastaavan "version" nimellä. Harkitse seuraavaa ohjausvirtakaaviota :
SSA:n määritelmän mukaisesti luomme muuttujan x sijasta kaksi uutta muuttujaa x 1 ja x 2 . Jokaiselle niistä annetaan arvo tasan kerran. Vastaavasti korvaamme loput muuttujat, minkä jälkeen saamme seuraavan kaavion:
Vielä ei ole selvää, mitä y-arvoa käytetään alalohkossa. Siellä nimi y voi tarkoittaa sekä y 1 että y 2 . Tällaisten epäselvyyksien ratkaisemiseksi SSA:han on lisätty erityinen Φ-funktio. Tämä funktio luo muuttujasta y uuden version, jolle annetaan arvo joko y 1 :stä tai y 2 :sta riippuen siitä, mistä haarasta ohjaus tuli.
Ei ole tarvetta käyttää Φ-funktiota muuttujassa x, koska vain yksi x:n versio (eli x 2 ) "pääsee" viimeisen lohkon.
Φ-funktiota ei ole varsinaisesti toteutettu; se on vain ohje kääntäjälle tallentaa kaikki argumenttiluettelossaan luetellut muuttujat samaan paikkaan muistissa (tai rekisterissä ).
Yleisempi kysymys on, onko tietyllä ohjausvuokaaviolla mahdollista ymmärtää, missä ja mille muuttujille SSA-esitykseen on tarpeen lisätä Φ-funktioita? Vastaus tähän kysymykseen voidaan saada dominatoreiden avulla .