Kompilatordesign – Kodeoptimalisering

Optimalisering Er en programtransformasjonsteknikk, som forsøker å forbedre koden ved å få den til å forbruke mindre ressurser (DVS.CPU, Minne) og levere høy hastighet.

i optimalisering erstattes generelle programmeringskonstruksjoner på høyt nivå med svært effektive programmeringskoder på lavt nivå. En kodeoptimaliseringsprosess må følge de tre reglene som er gitt nedenfor:

• utgangskoden må ikke på noen måte endre betydningen av programmet.

• Optimalisering bør øke hastigheten på programmet, og hvis det er mulig, bør programmet kreve mindre antall ressurser.

• Optimalisering bør i seg selv være rask og bør ikke forsinke den samlede kompileringsprosessen.

Innsats for en optimalisert kode kan gjøres på ulike nivåer av kompilering prosessen.

• i begynnelsen kan brukerne endre / omorganisere koden eller bruke bedre algoritmer for å skrive koden.

• etter å ha generert mellomkode, kan kompilatoren endre mellomkoden ved å adressere beregninger og forbedre sløyfer.

• mens produsere målet maskinkode, kan kompilatoren gjøre bruk av minne hierarki OG CPU registre.

Optimalisering kan kategoriseres bredt i to typer: maskinuavhengig og maskinavhengig.

Maskinuavhengig Optimalisering

i denne optimaliseringen tar kompilatoren inn mellomkoden og forvandler en del av koden som ikke involverer NOEN CPU-registre og / eller absolutte minneplasseringer. For eksempel:

do{ item = 10; value = value + item; } while(value
This code involves repeated assignment of the identifier item, which if we put this way:
Item = 10;do{ value = value + item; } while(value
should not only save the CPU cycles, but can be used on any processor.
Machine-dependent Optimization
Machine-dependent optimization is done after the target code has been generated and when the code is transformed according to the target machine architecture. It involves CPU registers and may have absolute memory references rather than relative references. Machine-dependent optimizers put efforts to take maximum advantage of memory hierarchy.
Basic Blocks
Source codes generally have a number of instructions, which are always executed in sequence and are considered as the basic blocks of the code. These basic blocks do not have any jump statements among them, i.e., when the first instruction is executed, all the instructions in the same basic block will be executed in their sequence of appearance without losing the flow control of the program.
A program can have various constructs as basic blocks, like IF-THEN-ELSE, SWITCH-CASE conditional statements and loops such as DO-WHILE, FOR, and REPEAT-UNTIL, etc.
Basic block identification
We may use the following algorithm to find the basic blocks in a program:



Søk header uttalelser av alle de grunnleggende blokker fra der en grunnleggende blokk starter:

Første uttalelse av et program.
 Setninger som er mål for en gren (betinget / ubetinget).
 Uttalelser som følger en gren uttalelse.



Header setninger og uttalelsene som følger dem danner en grunnleggende blokk.


en grunnleggende blokk inneholder ikke noen header-setning av noen annen grunnleggende blokk.


Grunnleggende blokker er viktige begreper fra både kodegenerering og optimaliseringssynspunkt.

 Grunnleggende blokker spiller en viktig rolle i å identifisere variabler, som brukes mer enn en gang i en enkelt grunnleggende blokk. Hvis en variabel brukes mer enn en gang, må registerminnet som er tildelt den variabelen ikke tømmes med mindre blokken fullfører utførelsen.
 Kontrollflyt Graf
 Grunnleggende blokker i et program kan representeres ved hjelp av kontrollflyt grafer. En kontrollflyt-graf viser hvordan programkontrollen sendes mellom blokkene. Det er et nyttig verktøy som hjelper til med optimalisering ved å finne uønskede løkker i programmet.

 Sløyfeoptimalisering 
 De fleste programmer kjører som en sløyfe i systemet. Det blir nødvendig å optimalisere løkkene for å lagre CPU-sykluser og minne. Looper kan optimaliseres ved hjelp av følgende teknikker:


Invariant kode: et fragment av kode som ligger i sløyfen og beregner samme verdi ved hver iterasjon kalles en loop-invariant kode. Denne koden kan flyttes ut av løkken ved å lagre den som skal beregnes bare en gang, snarere enn med hver iterasjon.


Induksjonsanalyse: en variabel kalles en induksjonsvariabel hvis verdien endres i sløyfen med en loop-invariant verdi.


Styrkereduksjon: det er uttrykk som bruker MER CPU-sykluser, tid og minne. Disse uttrykkene bør erstattes med billigere uttrykk uten å kompromittere uttrykkets utgang. For eksempel er multiplikasjon (x * 2) dyrt NÅR DET gjelder CPU-sykluser enn (x 


Død kode Eliminering
 Død kode er en eller flere enn en kode setninger, som er:

enten aldri utført eller uoppnåelig,
eller hvis utført, blir utdataene aldri brukt.

dermed spiller død kode ingen rolle i noen programoperasjon, og derfor kan den enkelt elimineres.
 Delvis død kode
 det er noen kodesetninger hvis beregnede verdier bare brukes under visse omstendigheter, dvs. noen ganger brukes verdiene og noen ganger er de ikke. Slike koder er kjent som delvis død-kode.

 ovennevnte kontrollflyt graf viser en del av programmet der variabel ‘a’ brukes til å tildele utdata av uttrykket ‘x * y’. La oss anta at verdien tildelt ‘ a ‘ aldri brukes inne i sløyfen.Umiddelbart etter at kontrollen forlater sløyfen, tildeles’ a ‘verdien av variabelen ‘z’, som vil bli brukt senere i programmet. Vi konkluderer her med at oppdragskoden til ‘ a ‘ aldri brukes hvor som helst, derfor er den kvalifisert til å bli eliminert.

 på samme måte viser bildet over at den betingede setningen alltid er falsk, noe som betyr at koden, skrevet i sann sak, aldri vil bli utført, derfor kan den fjernes.
 Delvis Redundans 
 Redundante uttrykk beregnes mer enn en gang i parallell bane, uten endring i operander.mens delvis redundante uttrykk beregnes mer enn en gang i en bane, uten endring i operander. For eksempel,

Loop-invariant kode er delvis overflødig og kan elimineres ved hjelp av en kodebevegelsesteknikk.
 Et annet eksempel på en delvis redundant kode kan være:
If (condition){ a = y OP z;}else{ ...}c = y OP z;
 vi antar at verdiene av operander (y og z) ikke endres fra tildeling av variabel a til variabel c. her, Hvis betingelseserklæringen er sant, beregnes y OP z to ganger, ellers en gang. Kodebevegelse kan brukes til å eliminere denne redundansen, som vist nedenfor:
If (condition){ ... tmp = y OP z; a = tmp; ...}else{ ... tmp = y OP z;}c = tmp;
Her, om tilstanden er sann eller falsk; Y OP z skal bare beregnes en gang.


Annonser