Kompilatordesign-kodoptimering

optimering är en programtransformationsteknik som försöker förbättra koden genom att få den att konsumera mindre resurser (dvs CPU, minne) och leverera hög hastighet.

i optimering ersätts allmänna programmeringskonstruktioner på hög nivå med mycket effektiva programmeringskoder på låg nivå. En kodoptimeringsprocess måste följa de tre reglerna nedan:

• utgångskoden får inte på något sätt ändra programmets betydelse.

• optimering bör öka programmets hastighet och om möjligt bör programmet kräva mindre antal resurser.

• optimering bör i sig vara snabb och bör inte fördröja den övergripande kompileringsprocessen.

ansträngningar för en optimerad kod kan göras på olika nivåer för att sammanställa processen.

• i början kan användare ändra / ordna om koden eller använda bättre algoritmer för att skriva koden.

• efter att ha genererat mellankod kan kompilatorn ändra mellankoden genom adresskalkyler och förbättra slingor.

• när du producerar målmaskinkoden kan kompilatorn använda sig av minneshierarki och CPU-register.

optimering kan kategoriseras i stort sett i två typer : maskinoberoende och maskinberoende.

Maskinoberoende optimering

i denna optimering tar kompilatorn in mellankoden och omvandlar en del av koden som inte involverar några CPU-register och/eller absoluta minnesplatser. Till exempel:

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 uttalanden av alla grundläggande block från där en grundläggande block startar:

första uttalandet av ett program.
uttalanden som är mål för någon gren (villkorlig/ovillkorlig).
uttalanden som följer någon gren uttalande.



Header-uttalanden och uttalandena som följer dem utgör ett grundläggande block.


ett grundläggande block innehåller inte någon rubrik uttalande av någon annan grundläggande block.


grundläggande block är viktiga begrepp från både kodgenerering och optimeringssynpunkt.

grundläggande block spelar en viktig roll för att identifiera variabler, som används mer än en gång i ett enda grundläggande block. Om någon variabel används mer än en gång behöver registerminnet som tilldelats den variabeln inte tömmas om inte blocket Slutför körning.
 Styrflödesdiagram
 grundläggande block i ett program kan representeras med hjälp av styrflödesdiagram. En kontrollflödesdiagram visar hur programkontrollen passeras mellan blocken. Det är ett användbart verktyg som hjälper till att optimera genom att hitta oönskade slingor i programmet.

Loopoptimering
 de flesta program körs som en slinga i systemet. Det blir nödvändigt att optimera slingorna för att spara CPU-cykler och minne. Slingor kan optimeras med följande tekniker:


Invariant kod: ett fragment av kod som finns i slingan och beräknar samma värde vid varje iteration kallas en loop-invariant kod. Denna kod kan flyttas ut ur slingan genom att spara den för att beräknas endast en gång, snarare än med varje iteration.


Induktionsanalys: en variabel kallas en induktionsvariabel om dess värde ändras inom slingan med ett loop-invariant värde.


styrka minskning: det finns uttryck som förbrukar mer CPU-cykler, tid och minne. Dessa uttryck bör ersättas med billigare uttryck utan att kompromissa med uttrycket. Till exempel är multiplikation (x * 2) dyr när det gäller CPU-cykler än (x 


död kod eliminering
 död kod är en eller flera kod uttalanden, som är:

antingen aldrig exekverad eller oåtkomlig,
eller om den körs, används deras utdata aldrig.

 således spelar död kod ingen roll i någon programoperation och därför kan den helt enkelt elimineras.
 delvis död kod
 det finns några kodsatser vars beräknade värden endast används under vissa omständigheter, dvs ibland används värdena och ibland inte. Sådana koder är kända som delvis dödkod.

ovanstående kontrollflödesdiagram visar en bit av program där variabeln ’a’ används för att tilldela utmatningen av uttrycket ’x * y’. Låt oss anta att värdet som tilldelats ’a’ aldrig används inuti slingan.Omedelbart efter att kontrollen lämnar slingan tilldelas ’a’ värdet av variabeln ’z’, som skulle användas senare i programmet. Vi drar här slutsatsen att tilldelningskoden för ’a’ aldrig används någonstans, därför är den berättigad att elimineras.

 på samma sätt visar bilden ovan att det villkorliga uttalandet alltid är falskt, vilket innebär att koden, skriven i Sant fall, aldrig kommer att utföras, därför kan den tas bort.
 partiell redundans
 redundanta uttryck beräknas mer än en gång parallellt, utan någon förändring i operander.medan partiella överflödiga uttryck beräknas mer än en gång i en sökväg, utan någon förändring i operander. Till exempel,

Loop-invariant kod är delvis överflödig och kan elimineras med hjälp av en kod-rörelse teknik.
 ett annat exempel på en delvis redundant kod kan vara:
If (condition){ a = y OP z;}else{ ...}c = y OP z;
vi antar att värdena för operander (y och z) inte ändras från tilldelning av variabel A till variabel c. här, om tillståndsdeklarationen är sant, beräknas y OP z två gånger, annars en gång. Kodrörelse kan användas för att eliminera denna redundans, som visas nedan:
If (condition){ ... tmp = y OP z; a = tmp; ...}else{ ... tmp = y OP z;}c = tmp;
här, om villkoret är sant eller falskt; y OP z bör beräknas endast en gång.


annonser