SSA ( Formula de atribuire unică statică ) este o reprezentare intermediară utilizată de compilatori , în care fiecărei variabile i se atribuie o valoare o singură dată . Variabilele programului sursă sunt versionate, de obicei prin adăugarea unui sufix, astfel încât fiecare atribuire să fie făcută unei versiuni unice a variabilei. În reprezentarea SSA, lanțurile DU ( def - use ) sunt definite în mod explicit și conțin un singur element.
Viziunea SSA a fost dezvoltată de cercetătorii IBM Ron Cytron , Jeanne Ferrante , Barry Rosen , Mark N. Wegman și Ken Zadeck în anii 1980. .
Compilatorii de limbaje de programare funcționale, cum ar fi Scheme , ML și Haskell , folosesc de obicei reprezentarea CPS ( stil de trecere de continuare ) în loc de SSA . Formal, aceste reprezentări sunt echivalente, astfel încât optimizările și transformările formulate într-una dintre reprezentări pot fi aplicate celeilalte.
Pentru codul în formă SSA, este mai ușor și mai eficient să efectuați mai multe tipuri de optimizări ale compilatorului . De exemplu, în următorul cod:
y := 1 y := 2 x := yeste evident pentru un om că prima atribuire este inutilă, deoarece valoarea lui y folosită în a treia linie corespunde celei de-a doua atribuiri. Cu toate acestea, pentru a înțelege acest lucru, compilatorul ar trebui să recurgă la analiza definițiilor care ajung . Dar cu reprezentarea SSA, devine mult mai ușor:
y1 := 1 y2 := 2 x1 := y2SSA face posibilă sau simplifică foarte mult următorii algoritmi de optimizare:
Traducerea codului obișnuit de program în reprezentarea SSA se realizează prin înlocuirea variabilei din partea stângă cu o nouă variabilă în fiecare operație de atribuire. Pentru fiecare utilizare a valorii variabilei, numele original este înlocuit cu numele „versiunii” corespunzătoare blocului de bază dorit. Luați în considerare următorul grafic al fluxului de control :
În conformitate cu definiția SSA, în loc de variabila x, vom crea două noi variabile x 1 și x 2 . Fiecare dintre ele va primi o valoare exact o dată. În mod similar, înlocuim variabilele rămase, după care obținem următorul grafic:
Nu este încă clar care valoare y va fi folosită în blocul de jos. Acolo numele y poate însemna fie y 1 , fie y 2 . Pentru a rezolva ambiguitățile de acest fel, în SSA a fost introdusă o funcție Φ specială. Această funcție creează o nouă versiune a variabilei y, căreia i se va atribui valoarea fie de la y 1 , fie de la y 2 , în funcție de ramura din care provine controlul.
Nu este nevoie să folosiți funcția Φ pe variabila x, deoarece doar o versiune a lui x (și anume, x 2 ) „atinge” ultimul bloc.
Funcția Φ nu este implementată efectiv; este doar o instrucțiune pentru compilator pentru a stoca toate variabilele listate în lista sa de argumente în același loc în memorie (sau registru ).
O întrebare mai generală este dacă, având în vedere un grafic de flux de control dat, este posibil să înțelegem unde și pentru ce variabile din reprezentarea SSA este necesar să se introducă funcții Φ? Răspunsul la această întrebare poate fi obținut cu ajutorul dominatorilor .