Compilator cu optimizator

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

Compilatorul cu optimizator sau compilator de optimizare este un compilator care optimizează automat un program în timpul procesului de compilare. Având în vedere o arhitectură în trei etape a unui compilator, cum ar fi cea a LLVM , aceasta implică faptul că în etapele de mijloc și / sau de back-end se iau pași pentru a îmbunătăți codul compilat produs. În cazul unei arhitecturi în două etape (doar front-end și back-end ), optimizările sunt considerate parte a back-end-ului . [1]

Schema în trei etape a unui compilator. Optimizările independente de țintă sunt realizate în cele din mijloc , care sunt dependente de țintă în cele din spate .

Efectuarea optimizărilor în timpul compilării unui program este importantă pentru a compensa ineficiențele care decurg din traducerea construcțiilor de nivel înalt în reprezentare intermediară sau în codul mașinii ( coborâre ). Aceste ineficiențe pot fi simple redundanțe în cod sau caracteristici mai profunde care reduc paralelizabilitatea programului sau alte caracteristici de eficiență. [2]

Istorie

Primii compilatori capabili să realizeze optimizări datează din a doua jumătate a anilor șaizeci. De exemplu, compilatorul IBM FORTRAN H, disponibil comercial în 1969 , și compilatorul Alpha , dezvoltat în 1966 , sunt considerați primii compilatori de acest gen. Structura pasului și analizele și optimizările mai simple au fost introduse în aceeași perioadă. [3]

Compilatorul GCC , introdus în 1987 [4] , și Clang , bazat pe LLVM și introdus în 2007 [5], sunt ambele compilatoare de optimizare. [6] [7]

Clase de arhitectură și optimizare

Optimizările sunt clasificate în optimizări independente de țintă ( dependente de țintă ) sau dependente de ținte (independente de țintă ). [8] Optimizările dependente de țintă funcționează pe proprietățile generale ale codului și, prin urmare, nu necesită cunoașterea arhitecturii pe care va rula codul compilat. Prin urmare, ele pot fi făcute direct pe reprezentarea intermediară. Dimpotrivă, optimizările independente de țintă sunt eficiente numai pe una sau mai multe platforme țintă specifice; prin urmare, acestea trebuie efectuate în timpul etapei de generare a codului țintă. [1]

Fiecare optimizare constituie un subrutin separat, numit pas de compilare. [9] Compilatorul decide pe baza steagurilor de compilare ce optimizări să efectueze. [10] Această decizie poate fi luată și pe baza datelor privind execuția programului; în acest caz vorbim de optimizare ghidată de profil . [11]

Algoritmii de transformare a programului implementați în optimizări necesită uneori o analiză preliminară a codului pentru a identifica unde poate fi aplicată optimizarea. Aceste analize sunt adesea comune pentru mai multe optimizări, deci sunt separate de optimizarea în sine pentru a evita duplicarea codului și recalcularea inutilă. În consecință, vorbim și de pași de analiză. [12] [13]

Optimizările pot fi clasificate după funcția lor, după analiza pe care se bazează sau după locația optimizării. În special, în ceea ce privește locația optimizării, vorbim despre: [14]

  • Optimizări peep-hole (optimizări care funcționează pe o cantitate limitată de instrucțiuni adiacente)
  • Optimizări locale (optimizări care funcționează într-un singur bloc de bază )
  • Optimizări intra-procedurale [15] (optimizări care funcționează în cadrul aceleiași proceduri )
  • Optimizări inter-procedurale [15] (optimizări care afectează mai multe proceduri)
  • Optimizarea întregului program [16] (optimizări care afectează întregul program)

În limbajele de programare în care programul este împărțit în mai multe unități de compilare, cum ar fi C și C ++, inter-procedurale și optimizări ale întregului program pot fi realizate de linker . În acest caz, aceasta este denumită optimizarea link-time . [17]

Optimizări SSA și non-SSA

Reprezentări intermediare singure atribuire statică (sau SSA) sunt reprezentări intermediare în care fiecare variabilă temporară este definită o singură dată în listarea reprezentării intermediare. Au avantajul că sunt mai ușor de analizat, dar păstrarea proprietății care le definește necesită utilizarea unor algoritmi de transformare a codului mai complexe. [18]

În scopul optimizării programului, reprezentările SSA fac ca unele analize și optimizări să fie redundante, deoarece proprietatea SSA este suficientă pentru a le realiza implicit. [18]

Optimizări independente de țintă

Mai jos sunt enumerate câteva optimizări independente de țintă de importanță generală, bazate pe o clasificare care acordă prioritate funcției față de analiza utilizată și locație.

Optimizările ciclului

Optimizările ciclului sunt acele optimizări care funcționează pe cicluri. În general, acestea se bazează pe analiza fluxului de date și pe arborele dominator pentru a identifica ce blocuri de bază alcătuiesc ciclul. [19]

Aceste optimizări operează adesea pe variabile de inducție . O variabilă este inducție dacă și numai dacă respectă una dintre următoarele proprietăți: [20]

  1. În interiorul buclei este definit ca o sumă algebrică cu o variabilă invariantă de buclă, adică constantă în timpul execuției buclei (variabila de inducție de bază)
  2. În buclă este definit pornind de la o altă variabilă de inducție prin multiplicare sau sumă algebrică cu o variabilă invariantă de buclă (variabilă de inducție derivată)

Contoare ale unui ciclu sunt variabile de inducție, prin urmare această definiție permite efectuarea de analize și optimizări asupra acestora. [20]

Ridicarea buclei sau mișcarea codului invariant în buclă
Instrucțiuni de mișcare care definesc variabile invariante în bucla în afara buclei în sine. [21]
Reducerea puterii
Simplifică variabilele calculate începând de la variabila de inducție a ciclului prin înmulțirea acesteia cu un factor constant, modificându-le în adaosuri. [22]
Desfășurarea buclei
„Derulează” un ciclu, duplicându-și corpul de câte ori este efectuat ciclul. Reduce cheltuielile generale de calcul ale variabilei de inducție a buclei în sine. [23]
Schimb de bucle
În cazul a două sau mai multe cicluri angajate, inversează un ciclu intern cu un ciclu extern. Permite îmbunătățirea locației acceselor de memorie, de exemplu atunci când bucla efectuează accesuri la matrice . [24]

Optimizări ale fluxului de date

Aceste optimizări funcționează modificând fluxul de date al unui program, adică secvența de instrucțiuni din reprezentarea intermediară necesară pentru a calcula una sau mai multe variabile. [25] [26]

Eliminare comună a subexpresiei
Dacă două expresii au aceeași sub-expresie, aceasta este partajată între cele două. [27] [26]
Propagare constantă sau pliere constantă
Dacă o expresie este compusă numai din operanzi constanți, valoarea acesteia este calculată în timpul compilării. [28] [26]
Propagarea copiilor
Dacă o variabilă este alocată alteia în reprezentarea intermediară, toate utilizările ulterioare ale celei de-a doua variabile sunt înlocuite cu utilizările primei. Într-o reprezentare non-SSA, această operațiune trebuie limitată până când prima sau a doua variabilă este definită din nou. Într-o reprezentare SSA acest lucru nu este necesar. [26]
Eliminarea codului mort
Această optimizare elimină acele instrucțiuni care efectuează calcule care nu sunt utilizate niciodată. [29] Este posibil ca această optimizare să fie mai agresivă prin exploatarea informațiilor derivate din graficul fluxului de control . [30] [31]

Optimizări dependente de țintă

În timp ce optimizările independente de țintă sunt realizate la mijloc pentru a îmbunătăți proprietățile de importanță generală, optimizările dependente de țintă sunt realizate în back-end pentru a permite programului să exploateze caracteristicile specifice ale arhitecturii țintă. Aceste caracteristici pot fi, de exemplu, utilizarea instrucțiunilor pentru paralelism Instrucțiuni multiple cu date multiple (SIMD). [1]

Programarea instrucțiunilor
Instrucțiunile codului mașinii sunt reordonate pentru a îmbunătăți paralelizabilitatea într-o arhitectură de cuvinte de instrucțiuni cu linii de conducte , suprascalare sau foarte lungi . [32]
Alocarea registrului
Variabilele temporare în transformarea intermediară sunt asociate cu unul sau mai multe registre ale arhitecturii țintă, dacă este posibil, în loc să le aloce în memoria principală. [33]

Etape de analiză

Unele dintre optimizările menționate mai sus trebuie să analizeze codul pentru a culege informațiile necesare pentru a putea modifica. Mai jos enumerăm câteva dintre aceste analize. [12]

Analiza vieții
Această analiză calculează în ce domenii de cod este utilizată fiecare variabilă (numită și registru virtual) a reprezentării intermediare . O variabilă este utilizată dacă a fost definită (adică dacă i s-a atribuit o valoare) și dacă este posibil să fie utilizată în viitor. [34]
Se ajunge la definiții
Calculați ce instrucțiune din reprezentarea intermediară a definit valoarea unui anumit registru virtual utilizat de o altă instrucțiune. Această analiză este critică în compilatoarele care nu utilizează reprezentarea SSA. [35]
Construirea arborelui Dominator
Această analiză face posibilă distincția dacă o instrucțiune a reprezentării intermediare este dominată de alta. O instrucțiune este dominată de alta, dacă în orice pistă de execuție a programului, a doua trebuie executată mai întâi pentru a ajunge la prima instrucțiune. [36]
Analiza pointer-alias
Detectează dacă un indicator poate face referire la aceeași zonă de memorie ca un alt indicator. Nu este posibil să efectuați această analiză cu precizie în unele limbaje de programare (cum ar fi C ), deoarece acestea permit calcule arbitrare pe pointeri. [37]

Notă

  1. ^ a b c Aho, Lam, Sethi, Ullman , p. 5 .
  2. ^ (RO) Monica S. Lam, „Introducere avansată a cursului de compilatori” (PDF) pe suif.stanford.edu. Adus la 25 iunie 2020 .
  3. ^ Aho, Lam, Sethi, Ullman , pp. 703-704 .
  4. ^ (EN) O scurtă istorie a GCC , pe gcc.gnu.org. Adus pe 26 iunie 2020 .
  5. ^ (EN)Note de lansare LLVM 2.1 , pe releases.llvm.org. Adus pe 26 iunie 2020 .
  6. ^ (RO) Declarația misiunii de dezvoltare GCC (22/04/1999) , pe gcc.gnu.org. Adus pe 26 iunie 2020 .
  7. ^ (EN) Clang - Caracteristici și obiective , pe clang.llvm.org. Adus pe 26 iunie 2020 .
  8. ^ Aho, Lam, Sethi, Ullman , p. 10 .
  9. ^ Aho, Lam, Sethi, Ullman , p. 11 .
  10. ^ (EN) Amy Brown și Greg Wilson (eds), LLVM , în The Architecture of Open Source Applications , 2011, p. 158, ISBN 978-1-257-63801-7 .
  11. ^ (EN) Profile-Guided Optimization (PGO) , pe software.intel.com. Adus la 25 iunie 2020 .
  12. ^ a b ( EN ) Monica Lam, Prezentare generală a sistemului SUIF ( ps ), su suif.stanford.edu . Adus la 25 iunie 2020 .
  13. ^ (EN) Pass-uri de analiză și transformare LLVM pe llvm.org. Adus la 25 iunie 2020 .
  14. ^ (EN) Craig Chambers, Optimisations (PDF) pe courses.cs.washington.edu. Adus la 25 iunie 2020 .
  15. ^ a b Aho, Lam, Sethi, Ullman , p. 903 .
  16. ^ ( EN ) / GL (Whole Program Optimization) , pe docs.microsoft.com . Adus la 25 iunie 2020 .
  17. ^ (RO) LLVM Link Time Optimization Design and Implementation , of llvm.org. Adus pe 5 iunie 2020 .
  18. ^ a b Appel , pp. 399-402 .
  19. ^ Appel , pp. 376-396 .
  20. ^ a b Appel , p. 387 .
  21. ^ Appel , p. 384 .
  22. ^ Appel , p. 388 .
  23. ^ Appel , p. 395 .
  24. ^ Appel , p. 476 .
  25. ^ Aho, Lam, Sethi, Ullman , p. 597 .
  26. ^ a b c d Appel , p. 359 .
  27. ^ Aho, Lam, Sethi, Ullman , p. 639 .
  28. ^ Aho, Lam, Sethi, Ullman , p. 632 .
  29. ^ Appel , p. 360 .
  30. ^ Appel , p. 426 .
  31. ^ Aho, Lam, Sethi, Ullman , p. 535 .
  32. ^ (EN) Monica S. Lam, Instruction Scheduling (PDF), pe suif.stanford.edu. Adus la 25 iunie 2020 .
  33. ^ (EN) Monica S. Lam, Register Allocation (PDF), pe suif.stanford.edu. Adus la 25 iunie 2020 .
  34. ^ Appel , pp. 203-214 .
  35. ^ Appel , p. 354 .
  36. ^ Appel , pp. 379-381 .
  37. ^ Appel , pp. 369-374 .

Bibliografie

  • (EN) Andrew W. Appel și Jens Palsberg, Modern Compiler Implementation in Java, ediția a doua, Cambridge University Press, 2004, ISBN 0-521-82060-X .
  • ( EN ) Alfred V. Aho, Monica S. Lam, Ravi Sethi și Jeffrey D. Ullman, Compilers: Principles, Techniques & Tools , ediția a II-a, Pearson Education, 2007, ISBN 0-321-48681-1 .

Elemente conexe

linkuri externe

Adus de la „ https://it.wikipedia.org/w/index.php?title=Compiler_with_optimizer&oldid=121854352 ”