Odstranění společných podvýrazů ( angl. Common subexpression eliminace nebo CSE) je optimalizace kompilátoru , která hledá v programu výpočty , které se v uvažované sekci provádějí více než jednou, a pokud je to možné a efektivní , odstraňuje druhou a další stejné operace . Tato optimalizace vyžaduje analýzu toku datpro hledání nadbytečných výpočtů a téměř vždy zkracuje dobu provádění programu při použití [1] .
Podvýraz v programu se nazývá společný podvýraz , pokud existuje jiný takový podvýraz, který je vždy vyhodnocen před daným a operandy se mezi vyhodnoceními nemění. Například v níže uvedeném příkladu je výraz b * c obecným podvýrazem.
Na základě této definice je odstranění společných podvýrazů transformací , která eliminuje opakované vyhodnocování společných podvýrazů a nahrazuje je použitím hodnoty uložené po prvním vyhodnocení. V uvažovaném příkladu však není možné při výpočtu d okamžitě nahradit společný podvýraz hodnotou proměnné a, protože tato proměnná se může mezi příslušnými výpočty měnit.
Zvažte následující fragment kódu:
a = b * c + g ; d = b * c * d _Platí pro něj následující transformace:
tmp = b * c ; a = tmp + g ; d = tmp * d ;což bude účinné, pokud je celkový čas pro zápis a několik čtení nové proměnné "tmp" menší než celkový čas strávený vyhodnocením výrazu "b * c" pokaždé, když se v kódu objeví.
Existují dva typy této optimalizace:
Obě optimalizace jsou založeny na analýze toku dat, během kterého se zjišťuje dostupnost výrazu v každém bodě programu.
Optimalizační aplikace je založena na analýze dostupných výrazů . Výraz x + yje dostupný v určitém bodě pprogramu, pokud: [2]
Účinnost převodu je dána především skutečností, že celková doba zápisu a několika čtení nové proměnné „tmp“ se ukáže být menší než celková doba strávená vyhodnocením výrazu „b * c“ pokaždé, když se objeví v kód. V praxi ovlivňuje výslednou efektivitu i řada dalších faktorů, zejména distribuce proměnných mezi registry .
V jednoduchých případech, jako je ten diskutovaný výše, je odstraněna duplikace výpočtů aritmetických výrazů. Tato optimalizace je nejvýznamnější pro vnitřní reprezentaci kompilátoru, například při výpočtu indexů polí, kde je ruční optimalizace velmi obtížná nebo nemožná. V některých programovacích jazycích je možné vytvořit mnoho stejných výpočtů. Například makra jazyka C, která ve zdrojovém kódu netvoří stejné výrazy, ale po nahrazení názvu makra při zpracování preprocesorem posloupností programových instrukcí se taková mohou objevit.
V případě globální aplikace optimalizace ovlivňují přínos další kritéria. Například je třeba vzít v úvahu počítadla provádění základních bloků, protože snížením statického počtu vyhodnocení výrazů můžete zvýšit dynamické číslo, což negativně ovlivňuje počet operací prováděných v programu. To vede k tomu, že zpětná optimalizace související s třídou PRE (partial redundancy eliminace) může být přínosná.