Gles betingad konstant förökning
Inom datavetenskap är sparse conditional constant propagation ( SCCP) en optimering som ofta används i kompilatorer efter konvertering till static single assignment form ( SSA). Det tar samtidigt bort vissa typer av död kod och sprider konstanter genom ett program. Dessutom kan den hitta mer konstanta värden, och därmed fler möjligheter till förbättringar, än att separat tillämpa eliminering av död kod och konstant spridning i valfri ordning eller hur många repetitioner som helst.
Algoritmen fungerar genom att utföra abstrakt tolkning av koden i SSA-form . Under abstrakt tolkning använder den vanligtvis ett platt gitter av konstanter för värden och en global miljö som kartlägger SSA-variabler till värden i detta gitter. Kärnan i algoritmen kommer i hur den hanterar tolkningen av greninstruktioner . När det påträffas utvärderas villkoret för en gren så bra som möjligt givet precisionen hos de abstrakta värdena bundna till variabler i villkoret. Det kan vara så att värdena är helt exakta (varken topp eller botten) och därför kan abstrakt utförande avgöra i vilken riktning som ska förgrenas. Om värdena inte är konstanta, eller om en variabel i villkoret är odefinierad, måste båda grenriktningarna tas för att förbli konservativa.
När den abstrakta tolkningen är klar markeras instruktioner som aldrig nåddes som död kod. SSA-variabler som visar sig ha konstanta värden kan sedan infogas vid (propageras till) deras användningsställe. [ exempel behövs ]
Anteckningar
- ^ Wegman, Mark N. och Zadeck, F. Kenneth. " Konstant förökning med villkorliga grenar ." ACM Transactions on Programming Languages and Systems , 13(2), april 1991, sidorna 181-210.
- ^ Klicka, Clifford och Cooper, Keith. " Combining Analyses, Combining Optimizations ", ACM Transactions on Programming Languages and Systems , 17(2), mars 1995, sidorna 181-196
- Cooper, Keith D. och Torczon, Linda. Konstruera en kompilator . Morgan Kaufmann. 2005.