návrh kompilátoru-Optimalizace kódu

optimalizace je technika transformace programu, která se snaží vylepšit kód tím, že spotřebovává méně zdrojů (tj.

v optimalizaci jsou obecné programovací konstrukty na vysoké úrovni nahrazeny velmi účinnými nízkoúrovňovými programovacími kódy. Proces optimalizace kódu se musí řídit třemi níže uvedenými pravidly:

• výstupní kód nesmí v žádném případě měnit význam programu.

• optimalizace by měla zvýšit rychlost programu a pokud je to možné, program by měl vyžadovat menší počet zdrojů.

• optimalizace by měla být sama o sobě rychlá a neměla by zdržovat celkový proces kompilace.

úsilí o optimalizovaný kód lze vyvinout na různých úrovních kompilace procesu.

• na začátku mohou uživatelé změnit / uspořádat kód nebo použít lepší algoritmy pro zápis kódu.

• po vygenerování mezilehlého kódu může kompilátor upravit mezilehlý kód pomocí výpočtů adres a zlepšení smyček.

• při vytváření cílového strojového kódu může kompilátor využívat hierarchii paměti a registry CPU.

optimalizace může být rozdělena do dvou typů: nezávislá na stroji a závislá na stroji.

strojově nezávislá optimalizace

v této optimalizaci kompilátor přebírá mezilehlý kód a transformuje část kódu, která nezahrnuje žádné registry CPU a / nebo absolutní umístění paměti. Například:

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:



hledat příkazy záhlaví všech základních bloků, odkud začíná základní blok:

první prohlášení o programu.
příkazy, které jsou cílem jakékoli větve (podmíněné / bezpodmínečné).
příkazy, které následují po každém příkazu větve.



příkazy záhlaví a příkazy za nimi tvoří základní blok.


základní blok neobsahuje žádný příkaz záhlaví žádného jiného základního bloku.


základní bloky jsou důležité pojmy jak z hlediska generování kódu, tak z hlediska optimalizace.

základní bloky hrají důležitou roli při identifikaci proměnných, které se používají více než jednou v jednom základním bloku. Pokud je nějaká proměnná používána více než jednou, nemusí být paměť registru přidělená této proměnné vyprázdněna, pokud blok nedokončí spuštění.
 Graf řídicího toku
základní bloky v programu lze reprezentovat pomocí grafů řídicího toku. Graf řídicího toku zobrazuje, jak je řízení programu předáno mezi bloky. Je to užitečný nástroj, který pomáhá při optimalizaci pomocí vyhledání nežádoucích smyček v programu.

 optimalizace smyčky
 většina programů běží jako smyčka v systému. Je nutné optimalizovat smyčky, aby se ušetřily cykly CPU a paměť. Smyčky lze optimalizovat následujícími technikami:


invariantní kód: fragment kódu, který je umístěn ve smyčce a počítá stejnou hodnotu při každé iteraci, se nazývá kód invariantní smyčky. Tento kód může být přesunut ze smyčky uložením, aby byl vypočítán pouze jednou, spíše než s každou iterací.


indukční analýza: proměnná se nazývá indukční proměnná, pokud je její hodnota změněna ve smyčce invariantní hodnotou smyčky.


snížení síly: existují výrazy, které spotřebovávají více cyklů CPU, času a paměti. Tyto výrazy by měly být nahrazeny levnějšími výrazy, aniž by byl ohrožen výstup výrazu. Například násobení (x * 2) je drahé z hlediska cyklů CPU než (x 


eliminace Mrtvého kódu
mrtvý kód je jeden nebo více příkazů kódu, které jsou:

buď nikdy spuštěn nebo nedosažitelný,
, nebo je-li proveden, jejich výstup není nikdy použit.

mrtvý kód tedy nehraje žádnou roli v žádné operaci programu, a proto jej lze jednoduše odstranit.
částečně mrtvý kód
existují některé příkazy kódu, jejichž vypočtené hodnoty se používají pouze za určitých okolností, tj. Takové kódy jsou známé jako částečně mrtvý kód.

výše uvedený graf řídicího toku zobrazuje kus programu, kde proměnná “ a „slouží k přiřazení výstupu výrazu „x * y“. Předpokládejme, že hodnota přiřazená „a“ není nikdy použita uvnitř smyčky.Ihned poté, co ovládací prvek opustí smyčku, je “ a „přiřazena hodnota proměnné „z“, která by byla použita později v programu. Zde jsme dospěli k závěru, že kód přiřazení „a“ se nikde nepoužívá, proto je způsobilý k vyloučení.

 stejně tak na obrázku výše je znázorněno, že podmíněné prohlášení je vždy nepravdivé, což znamená, že kód, napsaný ve skutečném případě, nebude nikdy proveden, a proto může být odstraněn.
částečná redundance
redundantní výrazy se počítají více než jednou v paralelní cestě, bez jakékoli změny operandů.zatímco parciální redundantní výrazy jsou počítány více než jednou v cestě, bez jakékoli změny operandů. Například,

Loop-invariantní kód je částečně redundantní a může být eliminován pomocí techniky code-motion.
dalším příkladem částečně redundantního kódu může být:
If (condition){ a = y OP z;}else{ ...}c = y OP z;
předpokládáme, že hodnoty operandů (y A Z) se nemění z přiřazení proměnné a proměnné c. zde, pokud je příkaz podmínka pravdivý, pak se y OP z vypočítá dvakrát, jinak jednou. K odstranění této redundance lze použít pohyb kódu, jak je uvedeno níže:
If (condition){ ... tmp = y OP z; a = tmp; ...}else{ ... tmp = y OP z;}c = tmp;
zde, zda je podmínka pravdivá nebo nepravdivá; y OP z by měl být vypočítán pouze jednou.


inzeráty