Optimering af compiler - Optimizing compiler

I computing er en optimerende compiler en compiler, der forsøger at minimere eller maksimere nogle attributter for et eksekverbart computerprogram. Almindelige krav er at minimere et programs udførelsestid, hukommelsesaftryk , lagringsstørrelse og strømforbrug (de sidste tre er populære til bærbare computere ).

Compileroptimering implementeres generelt ved hjælp af en sekvens af optimering af transformationer , algoritmer, der tager et program og transformerer det til at producere et semantisk ækvivalent outputprogram, der bruger færre ressourcer eller udfører hurtigere. Det har vist sig, at nogle problemer med kodeoptimering er NP-komplette eller endda uafgjort . I praksis sætter faktorer som f.eks. Programmørens vilje til at vente på, at kompilatoren fuldfører sin opgave, øvre grænser for de optimeringer, som en kompilator muligvis giver. Optimering er generelt en meget CPU - og hukommelseskrævende proces. Tidligere var computerhukommelsesbegrænsninger også en vigtig faktor for at begrænse, hvilke optimeringer der kunne udføres.

På grund af disse faktorer producerer optimering sjældent "optimal" output i nogen forstand, og faktisk kan en "optimering" hæmme ydeevnen i nogle tilfælde. De er snarere heuristiske metoder til forbedring af ressourceforbrug i typiske programmer.

Typer af optimering

Teknikker, der bruges til optimering, kan opdeles mellem forskellige anvendelsesområder, som kan påvirke alt fra en enkelt erklæring til hele programmet. Generelt er lokalt anvendte teknikker lettere at implementere end globale, men resulterer i mindre gevinster. Nogle eksempler på omfang omfatter:

Kighul -optimeringer
Disse udføres normalt sent i kompilationsprocessen, efter at maskinkode er blevet genereret. Denne form for optimering undersøger et par tilstødende instruktioner (f.eks. "At kigge gennem et kighul" på koden) for at se, om de kan erstattes af en enkelt instruktion eller en kortere række af instruktioner. For eksempel kan en multiplikation af en værdi med 2 udføres mere effektivt ved at venstre-flytte værdien eller ved at tilføje værdien til sig selv (dette eksempel er også et eksempel på styrkereduktion ).
Lokale optimeringer
Disse betragter kun oplysninger som lokale for en grundlæggende blok . Da grundlæggende blokke ikke har noget kontrolflow, kræver disse optimeringer meget lidt analyse, hvilket sparer tid og reducerer lagerkrav, men det betyder også, at der ikke bevares oplysninger på tværs af spring.
Globale optimeringer
Disse kaldes også "intraprocedurelle metoder" og virker på hele funktioner. Dette giver dem mere information at arbejde med, men gør ofte dyre beregninger nødvendige. Antagelser i værste tilfælde skal gøres, når der opstår funktionsopkald, eller der åbnes globale variabler, fordi der er få oplysninger om dem.
Loop optimeringer
Disse virker på udsagnene, der udgør en loop, såsom en for loop, for eksempel loop-invariant kodebevægelse . Loopoptimeringer kan have en betydelig indvirkning, fordi mange programmer bruger en stor procentdel af deres tid inde i loops.
Nærværende butiksoptimeringer
Disse tillader butiksoperationer at forekomme tidligere end ellers ville være tilladt i forbindelse med tråde og låse. Processen har brug for en eller anden måde at vide på forhånd, hvilken værdi der vil blive gemt af den opgave, den skulle have fulgt. Formålet med denne lempelse er at tillade kompileroptimering at udføre visse former for kodeomlægning, der bevarer semantikken i korrekt synkroniserede programmer.
Interprocedurel, hel-program eller link-time optimering
Disse analyserer alle programmets kildekode. Den større mængde information, der udtrækkes, betyder, at optimeringer kan være mere effektive i forhold til, når de kun har adgang til lokal information, dvs. inden for en enkelt funktion. Denne form for optimering kan også gøre det muligt at udføre nye teknikker. For eksempel funktion inlining , hvor et opkald til en funktion erstattes af en kopi af funktionsdelen.
Maskinkodeoptimering og objektkodeoptimering
Disse analyserer programmets eksekverbare opgavebillede, efter at en eksekverbar maskinkode er blevet linket . Nogle af de teknikker, der kan anvendes i et mere begrænset omfang, f.eks. Makrokomprimering, der sparer plads ved at kollapse almindelige sekvenser af instruktioner, er mere effektive, når hele det eksekverbare opgavebillede er tilgængeligt til analyse.

Ud over omfangsoptimeringer er der yderligere to generelle kategorier af optimering:

Programmeringssprog- uafhængigt vs. sprogafhængigt
De fleste sprog på højt niveau deler fælles programmeringskonstruktioner og abstraktioner: beslutning (hvis, switch, case), looping (for, mens, gentag .. indtil, do .. while) og indkapsling (strukturer, objekter). Således kan lignende optimeringsteknikker bruges på tværs af sprog. Visse sprogfunktioner gør imidlertid visse former for optimeringer vanskelige. Eksempelvis gør eksistensen af ​​pointer i C og C ++ det svært at optimere array -adgang (se aliasanalyse ). Sprog som PL/1 (der også understøtter pointer) har dog ikke desto mindre tilgængelige sofistikerede optimeringskompilatorer for at opnå bedre ydeevne på forskellige andre måder. Omvendt gør nogle sprogfunktioner visse optimeringer lettere. For eksempel må funktioner på nogle sprog ikke have bivirkninger . Derfor, hvis et program foretager flere opkald til den samme funktion med de samme argumenter, kan kompilatoren straks udlede, at funktionens resultat kun skal beregnes én gang. På sprog, hvor funktioner får lov til at have bivirkninger, er en anden strategi mulig. Optimizer kan bestemme, hvilken funktion der ikke har nogen bivirkninger, og begrænse sådanne optimeringer til bivirkningsfrie funktioner. Denne optimering er kun mulig, når optimeren har adgang til den kaldte funktion.
Maskinuafhængig vs. maskinafhængig
Mange optimeringer, der fungerer på abstrakte programmeringskoncepter (sløjfer, objekter, strukturer) er uafhængige af den maskine, som kompilatoren retter sig mod, men mange af de mest effektive optimeringer er dem, der bedst udnytter særlige funktioner i målplatformen. Eksempler er instruktioner, der gør flere ting på én gang, f.eks. Dekrementeringsregister og forgrening, hvis ikke nul.

Følgende er et eksempel på en lokal maskinafhængig optimering. For at indstille et register til 0 er den oplagte måde at bruge konstanten '0' i en instruktion, der sætter en registerværdi til en konstant. En mindre oplagt måde er at XOR et register med sig selv. Det er op til kompilatoren at vide, hvilken instruktionsvariant der skal bruges. På mange RISC -maskiner ville begge instruktioner være lige passende, da de begge ville have samme længde og tage samme tid. På mange andre mikroprocessorer som f.eks. Intel x86 -familien viser det sig, at XOR -varianten er kortere og sandsynligvis hurtigere, da der ikke er behov for at afkode en umiddelbar operand eller bruge det interne "umiddelbare operandregister". Et potentielt problem med dette er, at XOR kan indføre en dataafhængighed af den tidligere værdi af registret, hvilket forårsager en pipeline -standsning. Imidlertid har processorer ofte XOR af et register med sig selv som et specielt tilfælde, der ikke forårsager boder.

Faktorer, der påvirker optimering

Selve maskinen
Mange af de valg, om hvilke optimeringer der kan og bør foretages, afhænger af målmaskinens egenskaber. Det er undertiden muligt at parametre nogle af disse maskinafhængige faktorer, så et enkelt stykke kompilatorkode kan bruges til at optimere forskellige maskiner ved blot at ændre maskinbeskrivelsesparametrene. GCC fra GNU Project og Clang fra LLVM Compiler Infrastructure er eksempler på optimering af kompilatorer, der følger denne tilgang.
Arkitekturen for mål -CPU'en
Antal CPU -registre : I et vist omfang, jo flere registre, jo lettere er det at optimere til ydeevne. Lokale variabler kan tildeles i registre og ikke på stakken . Midlertidige/mellemliggende resultater kan efterlades i registre uden at skrive til og læse tilbage fra hukommelsen.
  • RISC vs CISC : CISC -instruktionssæt har ofte variable instruktionslængder, har ofte et større antal mulige instruktioner, der kan bruges, og hver instruktion kan tage forskellige tid. RISC -instruktionssæt forsøger at begrænse variationen i hvert af disse: instruktionssæt er normalt konstant længde, med få undtagelser, der er normalt færre kombinationer af registre og hukommelsesoperationer og instruktionsudstedelsesfrekvensen (antallet af instruktioner udført pr. Periode, normalt et heltal af urcyklussen) er normalt konstant i tilfælde, hvor hukommelseslatens ikke er en faktor. Der kan være flere måder at udføre en bestemt opgave på, idet CISC normalt tilbyder flere alternativer end RISC. Kompilatorer skal kende de relative omkostninger blandt de forskellige instruktioner og vælge den bedste instruktionssekvens (se instruktionsvalg ).
  • Rørledninger : En rørledning er i det væsentlige en CPU opdelt i en samlebånd . Det tillader brug af dele af CPU'en til forskellige instruktioner ved at opdele eksekveringen af ​​instruktioner i forskellige faser: instruktionsafkodning, adresseafkodning, hukommelseshentning, registerhentning, beregning, registerlager osv. En instruktion kan være i registerlagerstadiet , mens en anden kunne være i registerhentningsfasen. Rørledningskonflikter opstår, når en instruktion i et trin i rørledningen afhænger af resultatet af en anden instruktion foran den i rørledningen, men endnu ikke afsluttet. Rørledningskonflikter kan føre til rørledningsboder : hvor CPU'en spilder cykler, der venter på, at en konflikt skal løses.
Kompilatorer kan planlægge eller ombestille instruktioner, så rørledningens boder forekommer sjældnere.
  • Antal funktionelle enheder : Nogle CPU'er har flere ALU'er og FPU'er . Dette giver dem mulighed for at udføre flere instruktioner samtidigt. Der kan være begrænsninger for, hvilke instruktioner der kan parre med hvilke andre instruktioner ("parring" er samtidig udførelse af to eller flere instruktioner), og hvilken funktionel enhed der kan udføre hvilken instruktion. De har også problemer, der ligner pipeline -konflikter.
Også her skal instruktioner planlægges, så de forskellige funktionelle enheder er fuldt ud fodret med instruktioner til at udføre.
Maskinens arkitektur
  • Cache størrelse (256 KIB-12 MiB) og type (direkte kortlagt, 2- / 4- / 8- / 16-vejs associative, fuldt associativ): Teknikker, såsom inline ekspansion og loop udrulning kan øge størrelsen af den genererede kode og reducere kodelokalitet. Programmet kan bremse drastisk, hvis en stærkt udnyttet sektion af kode (som indre sløjfer i forskellige algoritmer) pludselig ikke kan passe i cachen. Caches, der ikke er fuldt associerede, har også større chancer for cache -kollisioner, selv i en ufyldt cache.
  • Cache-/hukommelsesoverførselshastigheder: Disse giver kompilatoren en indikation af straffen for cache -misser. Dette bruges hovedsageligt i specialiserede applikationer.
Tilsigtet brug af den genererede kode
Debugging
Mens du skriver en applikation, vil en programmør genkompilere og teste ofte, og kompilering skal derfor være hurtig. Dette er en af ​​grundene til, at de fleste optimeringer bevidst undgås under test-/fejlfindingsfasen. Også programkoden er normalt "trinvis" (se programanimation ) ved hjælp af en symbolsk fejlfinding , og optimering af transformationer, især dem, der omordner kode, kan gøre det svært at relatere outputkoden med linjenumrene i den originale kildekode. Dette kan forvirre både fejlfindingsværktøjerne og programmørerne, der bruger dem.
Generel brug
Færdigpakket software forventes meget ofte at blive udført på en række maskiner og CPU'er, der kan dele det samme instruktionssæt, men har forskellige timing, cache eller hukommelsesegenskaber. Som følge heraf er koden muligvis ikke indstillet til en bestemt CPU eller er indstillet til at fungere bedst på den mest populære CPU og alligevel fungerer den acceptabelt godt på andre CPU'er.
Brug til særlige formål
Hvis softwaren er kompileret til at blive brugt på en eller et par meget lignende maskiner med kendte egenskaber, kan kompilatoren kraftigt tune den genererede kode til de specifikke maskiner, forudsat at sådanne muligheder er tilgængelige. Vigtige specialtilfælde omfatter kode designet til parallel- og vektorprocessorer , til hvilke der anvendes specielle paralleliserende kompilatorer .
Indlejrede systemer
Disse er et almindeligt tilfælde af særlig anvendelse. Indlejret software kan indstilles tæt til en præcis CPU og hukommelsesstørrelse. Systemomkostninger eller pålidelighed kan også være vigtigere end kodens hastighed. For eksempel tilbyder kompilatorer til integreret software normalt muligheder, der reducerer kodestørrelse på bekostning af hastighed, fordi hukommelse er hovedomkostningerne ved en integreret computer. Kodens timing skal muligvis være forudsigelig, snarere end så hurtigt som muligt, så kodebuffer kan blive deaktiveret sammen med kompilatoroptimeringer, der kræver det.

Fælles temaer

I vid udstrækning har kompileroptimeringsteknikker følgende temaer, som undertiden er i konflikt.

Optimer den almindelige sag
Den almindelige sag kan have unikke egenskaber, der tillader en hurtig sti på bekostning af en langsom sti . Hvis den hurtige vej tages oftest, er resultatet en bedre samlet ydeevne.
Undgå redundans
Genbrug resultater, der allerede er beregnet, og gem dem til senere brug i stedet for at genberegne dem.
Mindre kode
Fjern unødvendige beregninger og mellemværdier. Mindre arbejde for CPU, cache og hukommelse resulterer normalt i hurtigere udførelse. Alternativt medfører indbyggede systemer mindre kode en lavere produktomkostning.
Færre spring ved hjælp af lige liniekode , også kaldet grenfri kode
Mindre kompliceret kode. Spring (betingede eller ubetingede grene ) forstyrrer forhåndshentning af instruktioner og bremser dermed koden. Brug af inlining eller sløjfeudrulning kan reducere forgrening på bekostning af at øge binær filstørrelse med længden af ​​den gentagne kode. Dette har en tendens til at flette flere grundlæggende blokke til en.
Lokalitet
Kode og data, der tilgås tæt sammen i tide, bør placeres tæt sammen i hukommelsen for at øge den rumlige lokalitet af reference .
Udnyt hukommelseshierarkiet
Adgang til hukommelse bliver stadig dyrere for hvert niveau i hukommelseshierarkiet , så placer de mest almindeligt anvendte poster i registre først, derefter cacher, derefter hovedhukommelse, før du går til disk.
Paralleliser
Omarranger operationer, så flere beregninger kan ske parallelt, enten på instruktions-, hukommelses- eller trådniveau.
Mere præcise oplysninger er bedre
Jo mere præcis information kompilatoren har, jo bedre kan den anvende nogen af ​​eller alle disse optimeringsteknikker.
Kørselsmetrik kan hjælpe
Oplysninger indsamlet under en testkørsel kan bruges til profilstyret optimering . Information indsamlet ved runtime, ideelt set med minimal overhead , kan bruges af en JIT -kompilator til dynamisk at forbedre optimeringen.
Styrke reduktion
Udskift komplekse eller vanskelige eller dyre operationer med enklere. For eksempel at erstatte division med en konstant med multiplikation med dens gensidige eller ved hjælp af induktionsvariabelanalyse til at erstatte multiplikation med et loop -indeks med addition.

Specifikke teknikker

Loop optimeringer

Hovedartikel: Loopoptimering

Nogle optimeringsteknikker, der primært er designet til at fungere på sløjfer, omfatter:

Induktionsvariabel analyse
Groft, hvis en variabel i en loop er en simpel lineær funktion af indeksvariablen, f.eks. j := 4*i + 1, Kan den opdateres passende hver gang loopvariablen ændres. Dette er en styrkereduktion og kan også tillade, at indeksvariabelens definitioner bliver til død kode . Disse oplysninger er også nyttige til blandt andet grænsekontrol af eliminering og afhængighedsanalyse .
Loop fission eller loop distribution
Loop fission forsøger at bryde en loop i flere loops over det samme indeksområde, men hver tager kun en del af loopens krop. Dette kan forbedre lokaliteten af ​​reference , både for de data, der er adgang til i sløjfen, og koden i loopens krop.
Loop -fusion eller loop -kombination eller loop -ramming eller loop -jamming
En anden teknik, der forsøger at reducere loop -overhead. Når to tilstødende sløjfer gentager det samme antal gange, uanset om det tal kendes på kompileringstidspunktet, kan deres kroppe kombineres, så længe de ikke refererer til hinandens data.
Loop inversion
Denne teknik ændrer en standard mens loop til en do/while (også kendt som repeat/until ) loop indpakket i en if betinget, hvilket reducerer antallet af spring med to i tilfælde, hvor loopet udføres. Hvis du gør det, kopieres tilstandskontrollen (forøgelse af kodens størrelse), men er mere effektiv, fordi spring normalt forårsager en pipeline -stall . Hvis den oprindelige tilstand er kendt ved kompileringstidspunktet og vides at være bivirkningsfri , kan if- beskyttelsen desuden springes over.
Sløjfeudveksling
Disse optimeringer bytter indre sløjfer med ydre sløjfer. Når loop -variablerne indekserer i en matrix, kan en sådan transformation forbedre referencelokaliteten afhængigt af arrayets layout.
Loop-invariant kodebevægelse
Hvis en mængde beregnes inde i en sløjfe under hver iteration, og dens værdi er den samme for hver iteration, kan det forbedre effektiviteten betydeligt ved at hejse den uden for sløjfen og beregne dens værdi bare én gang, før sløjfen begynder. Dette er især vigtigt med de adresseberegningsudtryk, der genereres af sløjfer over arrays. For korrekt implementering skal denne teknik bruges med loop inversion , fordi ikke alle koder er sikre at blive hejst uden for loop.
Loop reden optimering
Nogle gennemgående algoritmer, såsom matrixmultiplikation, har meget dårlig cacheadfærd og overdreven hukommelsesadgang. Loop reden optimering øger antallet af cache hits ved at udføre operationen over små blokke og ved hjælp af en loop interchange.
Loop vending
Loop -reversering vender den rækkefølge, i hvilken værdier er tildelt indeksvariablen. Dette er en subtil optimering, som kan hjælpe med at eliminere afhængigheder og dermed muliggøre andre optimeringer. På nogle arkitekturer bidrager loop -reversering desuden til mindre kode, da loop -indekset reduceres, da betingelsen, der skal opfyldes for at det kørende program skal forlade loopet, er en sammenligning med nul. Dette er ofte en speciel, parameterløs instruktion, i modsætning til en sammenligning med et tal, som skal have tallet at sammenligne med. Derfor gemmes mængden af ​​bytes, der er nødvendig for at gemme parameteren, ved hjælp af loop -vending. Hvis sammenligningstallet derudover overstiger platformens ordstørrelse i standard loop -rækkefølge, skal der udføres flere instruktioner for at evaluere sammenligningen, hvilket ikke er tilfældet med loop -reversering.
Sløjfe afrulning
Afrulning duplikerer loopens krop flere gange for at reducere antallet af gange loop -tilstanden testes og antallet af spring, der skader ydeevnen ved at forringe instruktionsrørledningen. En "færre spring" -optimering. Helt afrulning af en loop eliminerer al overhead, men kræver, at antallet af iterationer kendes på kompileringstidspunktet.
Sløjfeopdeling
Sløjfeopdeling forsøger at forenkle en sløjfe eller eliminere afhængigheder ved at bryde den i flere sløjfer, der har de samme legemer, men gentages over forskellige sammenhængende dele af indeksområdet. Et nyttigt specialtilfælde er loop -peeling , som kan forenkle en loop med en problematisk første iteration ved at udføre denne iteration separat, før den går ind i loop.
Sløjfe afbryder
Afbrydelse flytter en betinget fra inde i en sløjfe til uden for løkken ved at duplikere løkkens krop inde i hver af betingelsens if og ellers -klausuler.
Software pipelining
Sløjfen omstruktureres på en sådan måde, at arbejde udført i en iteration deles i flere dele og udføres over flere iterationer. I en stram sløjfe skjuler denne teknik forsinkelsen mellem indlæsning og brug af værdier.
Automatisk parallelisering
En sløjfe konverteres til multi-threaded eller vektoriseret (eller endda begge) kode for at udnytte flere processorer samtidigt i en shared-memory multiprocessor (SMP) maskine, herunder multi-core maskiner.

Dataflowoptimeringer

Datastrømsoptimeringer , baseret på dataflowanalyse , afhænger primært af, hvordan bestemte egenskaber for data udbredes af kontrolkanter i kontrol-flow-grafen . Nogle af disse inkluderer:

Almindelig eliminering af subexpression
I udtrykket (a + b) - (a + b)/4refererer "almindelig subexpression" til det duplikerede (a + b). Kompilatorer, der implementerer denne teknik, indser, at (a + b)det ikke vil ændre sig, og derfor beregner man kun dens værdi én gang.
Konstant foldning og formering
erstatte udtryk bestående af konstanter (f.eks. 3 + 5) med deres endelige værdi ( 8) på kompileringstidspunktet, frem for at foretage beregningen i løbetid. Bruges på de fleste moderne sprog.
Induktionsvariabel genkendelse og eliminering
se diskussion ovenfor om analyse af induktionsvariabler .
Alias ​​klassificering og pointer analyse
i nærvær af pointer er det svært at foretage nogen optimeringer overhovedet, da potentielt enhver variabel kan være blevet ændret, når en hukommelsesplacering er tildelt. Ved at specificere hvilke pointers der kan alias hvilke variabler, kan ikke -relaterede pointer ignoreres.
Elimination af døde butikker
fjernelse af tildelinger til variabler, der ikke efterfølgende læses, enten fordi variabelens levetid slutter eller på grund af en efterfølgende tildeling, der vil overskrive den første værdi.

SSA-baserede optimeringer

Disse optimeringer er beregnet til at blive udført efter omdannelse af programmet til en særlig form kaldet Statisk enkelt tildeling , hvor hver variabel kun er tildelt ét sted. Selvom nogle fungerer uden SSA, er de mest effektive med SSA. Mange optimeringer, der er anført i andre sektioner, nyder også fordel uden særlige ændringer, f.eks. Registerallokering.

Global værdinummering
GVN eliminerer redundans ved at konstruere en værdi graf af programmet, og derefter bestemme, hvilke værdier beregnes ved ækvivalente udtryk. GVN er i stand til at identificere en redundans, som almindelig eliminering af subexpression ikke kan, og omvendt.
Sparsom betinget konstant udbredelse
Kombinerer konstant udbredelse, konstant foldning og eliminering af død kode og forbedrer hvad der er muligt ved at køre dem separat. Denne optimering udfører symbolsk programmet, samtidig udbreder konstante værdier og eliminerer dele af kontrol-flow-grafen, som dette gør utilgængelig.

Kodegenerator optimeringer

Registrer tildeling
De hyppigst anvendte variabler bør opbevares i processorregistre for hurtigst adgang. For at finde hvilke variabler der skal indsættes i registre, oprettes en interferensgraf. Hver variabel er et toppunkt, og når der bruges to variabler på samme tid (har en krydsende liverange) har de en kant mellem sig. Denne graf er farvet ved hjælp af f.eks. Chaitins algoritme ved hjælp af det samme antal farver, som der er registre. Hvis farvningen mislykkes, spildes en variabel til hukommelsen, og farvningen afprøves igen.
Instruktionsvalg
De fleste arkitekturer, især CISC -arkitekturer og dem med mange adresseringstilstande , tilbyder flere forskellige måder at udføre en bestemt operation på ved hjælp af helt forskellige sekvenser af instruktioner. Instruktionsvælgerens opgave er generelt at gøre et godt stykke arbejde med at vælge, hvilke instruktioner der skal implementeres, hvilke operatører i lavniveau mellemrepræsentation med. For eksempel på mange processorer i 68000 -familien og på x86 -arkitekturen kan komplekse adresseringstilstande bruges i udsagn som "lea 25 (a1, d5*4), a0", så en enkelt instruktion kan udføre en betydelig mængde regning med mindre opbevaring.
Instruktionsplanlægning
Instruktionsplanlægning er en vigtig optimering for moderne rørledede processorer, som undgår boder eller bobler i rørledningen ved at samle instruktioner uden afhængigheder sammen, samtidig med at man er omhyggelig med at bevare den originale semantik.
Rematerialisering
Rematerialisering genberegner en værdi i stedet for at indlæse den fra hukommelsen, hvilket forhindrer en hukommelsesadgang. Dette udføres i takt med registerallokering for at undgå spild.
Kodefaktorering
Hvis flere sekvenser af kode er identiske eller kan parametreres eller omordnes til at være identiske, kan de erstattes med opkald til en delt underprogram. Dette kan ofte dele kode til opsætning af underrutiner og undertiden hale-rekursion.
Trampoliner
Mange CPU'er har mindre underrutineopkaldsinstruktioner for at få adgang til lav hukommelse. En kompilator kan spare plads ved at bruge disse små opkald i hovedkoden. Spring instruktioner i lav hukommelse kan få adgang til rutinerne på enhver adresse. Dette multiplicerer pladsbesparelser fra kodefaktorering.
Omorganisering af beregninger
Baseret på heltal lineær programmering forbedrer omstruktureringskompilatorer datalokaliteten og afslører mere parallelisme ved at omarrangere beregninger. Pladsoptimerende kompilatorer kan omarrangere kode for at forlænge sekvenser, der kan indregnes i underrutiner.

Funktionelle sprogoptimeringer

Selvom mange af disse også gælder for ikke-funktionelle sprog, stammer de enten fra eller er særligt kritiske i funktionelle sprog som Lisp og ML .

Haleopkaldsoptimering
Et funktionsopkald forbruger stakplads og involverer noget overhead relateret til parameteroverførsel og skylning af instruktionscachen. Hale rekursive algoritmer kan konverteres til iteration gennem en proces kaldet tail recursion elimination eller tail call optimization.
Skovrydning ( fusion af datastruktur )
På sprog, hvor det er almindeligt, at en sekvens af transformationer anvendes på en liste, forsøger skovrydning at fjerne konstruktionen af ​​mellemliggende datastrukturer.
Delvis evaluering

Andre optimeringer

Elimination af grænsekontrol
Mange sprog, f.eks. Java , håndhæver grænsekontrol af alle array -adganger. Dette er en alvorlig flaskehals for ydeevne på visse applikationer, f.eks. Videnskabelig kode. Eliminering af grænsekontrol gør det muligt for kompilatoren at fjerne grænsekontrol sikkert i mange situationer, hvor det kan afgøre, at indekset skal falde inden for gyldige grænser; for eksempel hvis det er en simpel loop -variabel.
Grenoptimering optimering (maskinafhængig)
Vælg den korteste grenforskydning, der når målet.
Omlægning af kodeblok
Omrangering af kodeblok ændrer rækkefølgen af ​​de grundlæggende blokke i et program for at reducere betingede grene og forbedre lokaliteten af ​​reference.
Eliminering af død kode
Fjerner instruktioner, der ikke påvirker programmets adfærd, f.eks. Definitioner, der ikke har nogen anvendelse, kaldet død kode . Dette reducerer kodestørrelse og eliminerer unødvendig beregning.
Factoring ud af invarianter ( loop invariants )
Hvis et udtryk udføres både når en betingelse er opfyldt og ikke er opfyldt, kan det skrives bare en gang uden for den betingede erklæring. På samme måde, hvis visse typer udtryk (f.eks. Tildeling af en konstant til en variabel) vises inde i en sløjfe, kan de flyttes ud af den, fordi deres virkning vil være den samme, uanset om de udføres mange gange eller bare en gang . Dette er også kendt som eliminering af total redundans. En lignende, men mere kraftfuld optimering er delvis redundanseliminering (PRE).
Inline ekspansion eller makro ekspansion
Når en eller anden kode påkalder en procedure , er det muligt direkte at indsætte procedurens krop inde i opkaldskoden i stedet for at overføre kontrol til den. Dette sparer overhead i forbindelse med procedureopkald, samt giver mulighed for mange forskellige parameterspecifikke optimeringer, men kommer på bekostning af plads; procedureorganet duplikeres hver gang proceduren kaldes inline. Generelt er inlining nyttig i præstationskritisk kode, der foretager et stort antal opkald til små procedurer. En "færre spring" -optimering. De udsagn af tvingende programmering sprog er også et eksempel på en sådan optimering. Selvom udsagn kunne implementeres med funktionsopkald, implementeres de næsten altid med kodeinline.
Spring trådning
I denne optimering flettes på hinanden følgende betingede spring helt eller delvist baseret på den samme tilstand.
Fx til ,if (c) { foo; } if (c) { bar; }if (c) { foo; bar; }
og til .if (c) { foo; } if (!c) { bar; }if (c) { foo; } else { bar; }
Makrokomprimering
En rumoptimering, der genkender fælles kodesekvenser, opretter underprogrammer ("kode -makroer"), der indeholder den fælles kode, og erstatter forekomsten af ​​de almindelige kodesekvenser med opkald til de tilsvarende underprogrammer. Dette udføres mest effektivt som en maskinkodeoptimering , når al koden er til stede. Teknikken blev først brugt til at spare plads i en fortolkende byte -strøm, der blev brugt i en implementering af Macro Spitbol på mikrocomputere . Problemet med at bestemme et optimalt sæt makroer, der minimerer den plads, der kræves af et givet kodesegment, vides at være NP-komplet , men effektive heuristikker opnår næsten optimale resultater.
Reduktion af cache kollisioner
(f.eks. ved at afbryde justeringen inden for en side)
Stak reduktion højde
Omarrangér udtrykstræ for at minimere de ressourcer, der er nødvendige til udtryksevaluering.
Test rækkefølge
Hvis vi har to tests, der er betingelsen for noget, kan vi først håndtere de enklere tests (f.eks. Sammenligne en variabel med noget) og først derefter med de komplekse tests (f.eks. Dem, der kræver et funktionsopkald). Denne teknik supplerer doven evaluering , men kan kun bruges, når testene ikke er afhængige af hinanden. Kortslutende semantik kan gøre dette svært.

Interprocedurelle optimeringer

Interprocedurel optimering fungerer på hele programmet, på tværs af procedure- og filgrænser. Det arbejder tæt sammen med intraprocessuelle modparter, udført i samarbejde med en lokal del og en global del. Typiske interprocedurelle optimeringer er: procedure inlining , interprocedural dead code elimination, interprocedural constant propagation, and procedure reordord . Som sædvanlig skal kompilatoren udføre interprocedureanalyse før dens egentlige optimeringer. Interprocedureanalyser omfatter aliasanalyse, array -adgangsanalyse og konstruktion af en opkaldsgraf .

Interprocedurel optimering er almindelig i moderne kommercielle kompilatorer fra SGI , Intel , Microsoft og Sun Microsystems . I lang tid blev open source GCC kritiseret for mangel på effektive interprocedureanalyser og optimeringer, selvom dette nu forbedres. En anden open source -compiler med fuld analyse- og optimeringsinfrastruktur er Open64 .

På grund af den ekstra tid og plads, der kræves ved interprocedureanalyse, udfører de fleste kompilatorer det ikke som standard. Brugere skal eksplicit bruge kompilatorindstillinger til at fortælle kompilatoren om at muliggøre interprocedureanalyse og andre dyre optimeringer.

Praktiske overvejelser

Der kan være en lang række optimeringer, som en kompilator kan udføre, lige fra det enkle og ligetil, der tager lidt kompileringstid til det omfattende og komplekse, der involverer betydelige mængder kompileringstid. Følgelig giver kompilatorer ofte muligheder for deres kontrolkommando eller -procedure, så kompilatorbrugeren kan vælge, hvor meget optimering der skal anmodes om. for eksempel tillod IBM FORTRAN H -kompilatoren brugeren at angive ingen optimering, optimering kun på registerniveau eller fuld optimering. I 2000'erne var det almindeligt, at kompilatorer, f.eks. Clang , havde en række kompileringskommandoindstillinger, der kunne påvirke en række optimeringsvalg, startende med den velkendte -O2switch.

En tilgang til isolering af optimering er brugen af ​​såkaldte post-pass optimizers (nogle kommercielle versioner heraf stammer fra mainframe software fra slutningen af ​​1970'erne). Disse værktøjer tager det eksekverbare output med en optimerende compiler og optimerer det endnu mere. Post-pass optimeringsprogrammer fungerer normalt på samlingssprog eller maskinkodeniveau (i modsætning til kompilatorer, der optimerer mellemliggende repræsentationer af programmer). Et sådant eksempel er Portable C Compiler (pcc) fra 1980'erne, som havde et valgfrit pass, der ville udføre efteroptimeringer på den genererede samlingskode.

En anden overvejelse er, at optimeringsalgoritmer er komplicerede, og især når de bruges til at kompilere store, komplekse programmeringssprog, kan indeholde fejl, der introducerer fejl i den genererede kode eller forårsager interne fejl under kompilering. Compilerfejl af enhver art kan være foruroligende for brugeren, men især i dette tilfælde, da det måske ikke er klart, at optimeringslogikken er skyld. I tilfælde af interne fejl kan problemet delvist forbedres med en "fejlsikker" programmeringsteknik, hvor optimeringslogikken i kompilatoren er kodet, så en fejl bliver fanget, en advarselsmeddelelse udsendt og resten af ​​kompilationen fortsætter til vellykket afslutning.

Historie

Tidlige kompilatorer i 1960'erne var ofte primært optaget af blot at sammensætte kode korrekt eller effektivt, således at kompileringstider var en stor bekymring. En bemærkelsesværdig tidlig optimering af kompilatoren var IBM FORTRAN H -kompilatoren i slutningen af ​​1960'erne. En anden af ​​de tidligste og vigtige optimeringskompilatorer, der var banebrydende for flere avancerede teknikker, var den for BLISS (1970), som blev beskrevet i The Design of an Optimizing Compiler (1975). I slutningen af ​​1980'erne var optimering af kompilatorer tilstrækkeligt effektive til, at programmering i samlingssprog faldt. Dette udviklede sig sammen med udviklingen af ​​RISC-chips og avancerede processorfunktioner såsom instruktionsplanlægning og spekulativ udførelse, som var designet til at målrettes ved at optimere kompilatorer frem for ved hjælp af menneskeskrevet samlingskode.

Liste over statiske kodeanalyser

Se også

Referencer

eksterne links