En optimeringskompiler er en compiler , der bruger forskellige metoder til at opnå mere optimal programkode, mens dens funktionalitet bevares. De mest almindelige optimeringsmål er: at reducere programudførelsestiden, øge ydeevnen, komprimere programkoden, spare hukommelse, minimere energiomkostningerne, reducere antallet af I/O- operationer .
Optimering kan forekomme implicit under oversættelse af et program, men betragtes generelt som et separat trin i compilerens arbejde. Linkere kan også udføre en del af optimeringerne, såsom at fjerne ubrugte underrutiner eller omarrangere dem .
Optimering implementeres typisk gennem en række optimerende transformationer, algoritmer , der tager et program og modificerer det for at producere en semantisk ækvivalent variant, der er mere effektiv til nogle sæt af optimeringsmål. Nogle kodeoptimeringsproblemer har vist sig at være NP-komplette [1] eller endda uafklarelige [2] . Ikke desto mindre løses praktisk talt mange af dem ved heuristiske metoder, som giver ganske tilfredsstillende resultater.
Skelne mellem lav- og højniveauoptimering. Lav-niveau optimering transformerer programmet på niveau med elementære instruktioner, for eksempel instruktioner fra en processor af en bestemt arkitektur . Optimering på højt niveau udføres på niveau med strukturelle elementer i programmet, såsom moduler, funktioner, grene, cyklusser.
Metoderne, der bruges i optimeringer, kan klassificeres efter omfang: de kan påvirke både en enkelt sætning og et helt program. Lokale metoder (som påvirker en lille del af programmet) er lettere at implementere end globale metoder (gælder for hele programmet), men globale metoder er ofte mere gavnlige.
Lokale kighulsoptimeringer overvejer flere tilstødende (i form af en af graferne i programrepræsentationen) instruktioner (som om man "kigger gennem kighullet " på koden) for at se, om det er muligt at udføre nogen transformation med dem med hensyn til optimeringen mål. De kan især erstattes af en enkelt instruktion eller en kortere række af instruktioner.
For eksempel kan fordobling af et tal gøres mere effektivt ved at bruge et venstreskift eller ved at lægge tallet til det samme.
Ved lokal optimering tages der kun hensyn til informationen om én grundlæggende blok pr. trin [3] . Da der ikke er nogen kontrolflowovergange i basisblokke , kræver disse optimeringer kun lidt analyse (sparer tid og reducerer hukommelseskrav), men det betyder også, at der ikke gemmes information til næste trin.
Intraprocessuelle optimeringer ( engelsk intraprocedural ) er globale optimeringer, der udføres helt inden for rammerne af en oversættelsesenhed (f.eks. funktioner eller procedurer) [4] . Med en sådan optimering involveres meget mere information end i den lokale, hvilket giver mulighed for at opnå mere markante effekter, men det kræver ofte ressourcekrævende beregninger. Hvis der er globale variable i den programenhed, der optimeres, kan optimering af denne art være vanskelig.
Der er et stort antal optimeringer anvendt på loops. Med et stort antal iterationer af løkken er sådanne optimeringer ekstremt effektive, da en væsentlig del af programudførelsen påvirkes af en lille transformation. Da loops er en væsentlig del af udførelsestiden for mange programmer, findes loop-optimeringer i næsten alle compilere og er de vigtigste.
For eksempel ved at identificere sløjfeinvarianter er det nogle gange muligt at fjerne nogle af operationerne fra løkken for ikke at udføre redundante gentagne beregninger.
Sådanne typer optimeringer analyserer hele programmets kildekode på én gang. Den større mængde information, der udvindes af disse metoder, betyder, at optimeringer kan være mere effektive end andre metoder. Sådanne optimeringer kan bruge ret komplekse metoder, for eksempel erstattes et funktionskald med en kopi af funktionslegemet (inline eller inline).
Eksempel Lad der være en funktion:
int pred ( int x ) { hvis ( x == 0 ) returnere 0 ; andet returnere x - 1 ; }Inden den blev indlejret, så koden sådan ud:
int f ( int y ) { returnere pred ( y ) + pred ( 0 ) + pred ( y + 1 ); }Efter optimering:
int f ( int y ) { int temp = 0 ; hvis ( y == 0 ) temp += 0 ; ellers temp += y - 1 ; /* (en) */ hvis ( 0 == 0 ) temp += 0 ; ellers temp += 0 - 1 ; /* (2) */ hvis ( y + 1 == 0 ) temp += 0 ; ellers temp += ( y + 1 ) - 1 ; /* (3) */ retur temp ; }Funktionsinlining eliminerer overhead forbundet med funktionskald. Derudover er det efter inlining muligt at anvende intra-procedurelige optimeringer, som var umulige eller for svære at implementere før. Imidlertid har inlining sine ulemper, ligesom næsten enhver optimering - det øger den statiske størrelse af koden, hvilket kan føre til negative effekter i dele af udstyret, der er følsomme over for denne faktor.
Blandt de faktorer, der påvirker optimering, er både målmaskinens computeregenskaber (for eksempel antallet og klokhastigheden af processorkerner, størrelsen af processorcachen , systembusbåndbredden , mængden af RAM) og målets arkitektur. processor (især i forskellige arkitekturer er et forskelligt antal generelle registre tilgængelige, den beregningsmæssige pipeline er implementeret forskelligt ). En anden klasse af faktorer, der påvirker optimering, er scenarier for brug af målkode, for eksempel kan optimeringsmål variere betydeligt for fejlretnings- og testkode, lejlighedsvis kørsel, kontinuerlig brug, indlejrede eller selvstændige applikationer.
Blandt de optimeringsprincipper, der bruges i forskellige optimeringsmetoder i compilere (nogle af dem kan modsige hinanden eller være uanvendelige til forskellige optimeringsmål):
Dataflow- optimeringer er baseret på data - flow-analyse og betragter normalt kontrolflowgrafen og dataflowgrafen forbundet med hinanden som inputdata, såvel som ofte sløjfetræet og sløjfemærkningen af kontrolflowgrafen. Ved at analysere især udbredelsen af information, på disse grafer, afsløres muligheden for optimering i forhold til de ønskede mål, og derefter anvendes optimeringerne.
Fjernelse af almindelige underudtryk Fælles fjernelse af underudtryk er en compiler-optimering, der ser efter forekomster af identiske udtryk og analyserer muligheden for at erstatte dem med en enkelt variabel, der indeholder den beregnede værdi. Konvolution af konstanter Optimeringer, der reducerer overflødige beregninger ved at erstatte konstante udtryk og variable med deres værdier. Analyse af induktive variable ( eng. Induktionsvariabelanalyse ) Se beskrivelsen i Cycle Optimization . Sletning af blindgydeposter Slet tildelinger til variabler, der ikke efterfølgende læses. Tildelingen fjernes enten fordi variablen ikke er blevet læst inden udløbet af variablens levetid, eller fordi en efterfølgende tildeling vil overskrive den.SSA (Single Static Assignment, Single Static Assignment) er en form for Data Flow Graph (DFG)-repræsentation, hvor hver variabel kun tildeles en værdi én gang. Dette undgår multiplikation af buer i grafen under flere skrivninger og læsninger af en variabel og letter grafanalyse. For at gøre dette introducerer SSA-visningen specielle Phi-funktioner (dataflow-grafnoder) ved nogle konvergenspunkter i kontrolflowgrafen. Disse nye noder er de såkaldte pseudo-opgaver.
Flere definitioner er mulige ikke kun på grund af kontrolstrømskonvergenser ("eller"), men på grund af muligheden for at læse en sammensat værdi som en helhed, som blev skrevet i dele af mere end én operation ("og"). I dette tilfælde, for at vedligeholde SSA-formularen, introduceres yderligere pseudo-tildelinger i de grundlæggende blokke, som samler en værdi fra flere.
Nogle optimeringer er baseret på SSA. Selvom nogle af dem kan fungere uden SSA, er de mest effektive, når SSA er til stede.