Compiler Design – kode optimering

optimering er en programtransformationsteknik, der forsøger at forbedre koden ved at få den til at forbruge mindre ressourcer (dvs.CPU, hukommelse) og levere høj hastighed.

i optimering erstattes generelle programmeringskonstruktioner på højt niveau med meget effektive programmeringskoder på lavt niveau. En kodeoptimeringsproces skal følge de tre regler, der er angivet nedenfor:

• outputkoden må på ingen måde ændre programmets betydning.

• optimering skal øge programmets hastighed, og hvis det er muligt, skal programmet kræve mindre antal ressourcer.

• optimering skal i sig selv være hurtig og bør ikke forsinke den samlede kompileringsproces.

indsatsen for en optimeret kode kan gøres på forskellige niveauer af kompilering af processen.

• i begyndelsen kan brugerne ændre / omarrangere koden eller bruge bedre algoritmer til at skrive koden.

• efter generering af mellemkode kan kompilatoren ændre mellemkoden ved adresseberegninger og forbedre sløjfer.

• mens der produceres målmaskinkoden, kan kompilatoren gøre brug af hukommelseshierarki og CPU-registre.

optimering kan kategoriseres bredt i to typer : maskinuafhængig og maskinafhængig.

Maskinuafhængig optimering

i denne optimering tager kompilatoren mellemkoden og transformerer en del af koden, der ikke involverer nogen CPU-registre og/eller absolutte hukommelsessteder. 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øg header udsagn af alle de grundlæggende blokke fra hvor en grundlæggende blok starter:

første redegørelse for et program.
 udsagn, der er mål for enhver gren (betinget/ubetinget).
 udsagn, der følger enhver gren erklæring.



Header-udsagn og udsagnene, der følger dem, danner en grundlæggende blok.


en grundlæggende blok inkluderer ikke nogen header-erklæring for nogen anden grundlæggende blok.


grundlæggende blokke er vigtige begreber fra både kodegenerering og optimering synspunkt.

 grundlæggende blokke spiller en vigtig rolle i identificeringen af variabler, som bruges mere end en gang i en enkelt grundlæggende blok. Hvis en variabel bruges mere end en gang, behøver den registerhukommelse, der er tildelt denne variabel, ikke tømmes, medmindre blokken afslutter udførelsen.
 Kontrolstrømsgraf
 grundlæggende blokke i et program kan repræsenteres ved hjælp af kontrolstrømsgrafer. En kontrolstrømsgraf viser, hvordan programstyringen overføres mellem blokkene. Det er et nyttigt værktøj, der hjælper med optimering ved hjælp af lokalisering af uønskede sløjfer i programmet.

 Loop optimering
 de fleste programmer kører som en loop i systemet. Det bliver nødvendigt at optimere sløjferne for at gemme CPU-cyklusser og hukommelse. Loops kan optimeres ved hjælp af følgende teknikker:


Invariant kode: et fragment af kode, der befinder sig i sløjfen og beregner den samme værdi ved hver iteration kaldes en loop-invariant kode. Denne kode kan flyttes ud af løkken ved at gemme den, der kun skal beregnes en gang, snarere end med hver iteration.


Induktionsanalyse: en variabel kaldes en induktionsvariabel, hvis dens værdi ændres inden for sløjfen af en loop-invariant værdi.


styrkereduktion: der er udtryk, der bruger flere CPU-cyklusser, tid og hukommelse. Disse udtryk skal erstattes med billigere udtryk uden at gå på kompromis med udtrykket. For eksempel er multiplikation (*2) dyrt med hensyn til CPU-cyklusser end ( * 


 Dead-code Elimination
Dead code er en eller flere kodeerklæringer, som er:

enten aldrig udført eller uopnåelig,
 eller hvis udført, bliver deres output aldrig brugt.

 således spiller dead code ingen rolle i nogen programoperation, og derfor kan den simpelthen elimineres.
 delvist død kode
 der er nogle kodesætninger, hvis beregnede værdier kun bruges under visse omstændigheder, dvs.nogle gange bruges værdierne, og nogle gange er de ikke. Sådanne koder er kendt som delvist død-kode.

 ovenstående kontrolstrømsgraf viser en del af programmet, hvor variabel ‘a’ bruges til at tildele output af udtryk ‘h * y’. Lad os antage, at værdien tildelt ‘a’ aldrig bruges inde i sløjfen.Umiddelbart efter at kontrollen forlader sløjfen, tildeles ‘a’ værdien af variabel ‘Å’, som vil blive brugt senere i programmet. Vi konkluderer her, at tildelingskoden for ‘a’ aldrig bruges overalt, derfor er den berettiget til at blive elimineret.

 på samme måde viser billedet ovenfor, at den betingede erklæring altid er falsk, hvilket antyder, at koden, skrevet i sandt tilfælde, aldrig vil blive udført, derfor kan den fjernes.
 delvis redundans 
 overflødige udtryk beregnes mere end en gang i parallel sti uden nogen ændring i operander.mens delvise redundante udtryk beregnes mere end en gang i en sti uden nogen ændring i operander. For eksempel,

Loop-invariant kode er delvist overflødig og kan elimineres ved hjælp af en kode-motion teknik.
 et andet eksempel på en delvist overflødig kode kan være:
If (condition){ a = y OP z;}else{ ...}c = y OP z;
 vi antager, at værdierne for operander (y OG Å) ikke ændres fra tildeling af variabel A til variabel c. her, hvis tilstandsopgørelsen er sand, beregnes y op å to gange, ellers en gang. Kode bevægelse kan bruges til at eliminere denne redundans, som vist nedenfor:
If (condition){ ... tmp = y OP z; a = tmp; ...}else{ ... tmp = y OP z;}c = tmp;
her, om betingelsen er sand eller falsk; y op å skal kun beregnes en gang.


annoncer