Běžná eliminace subexprese - Common subexpression elimination

v teorie překladače, běžná eliminace subexprese (CSE) je optimalizace kompilátoru který hledá instance identických výrazy (tj. všichni hodnotí stejnou hodnotu) a analyzuje, zda má smysl je nahradit jedinou proměnnou obsahující vypočítanou hodnotu.[1]

Příklad

V následujícím kódu:

a = b * c + g; d = b * c * e;

může být vhodné transformovat kód na:

tmp = b * c; a = tmp + g; d = tmp * e;

pokud náklady na skladování a načítání tmp je menší než náklady na výpočet před naším letopočtem čas navíc.

Zásada

Možnost provádět CSE je založena na dostupný výraz analýza (a analýza toku dat ). Výraz před naším letopočtem je k dispozici na místě str v programu, pokud:

  • každá cesta od počátečního uzlu po p se vyhodnotí před naším letopočtem před dosažením str,
  • a neexistují žádné úkoly b nebo C po hodnocení, ale dříve str.

Analýza nákladů a přínosů prováděná optimalizátorem vypočítá, zda jsou náklady na obchod tmp je menší než náklady na násobení; v praxi další faktory, například to, které hodnoty jsou uchovávány a v nichž jsou také významné registry.

Autoři překladačů rozlišují dva druhy CSE:

  • lokální společná eliminace subexprese pracuje v jednom základní blok
  • globální společná eliminace subexprese pracuje na celém postupu,

Oba druhy se spoléhají analýza toku dat z nichž výrazů je k dispozici které místo v programu.

Výhody

Výhody provádění CSE jsou dostatečně velké, že se jedná o běžně používanou optimalizaci.

V jednoduchých případech, jako v předchozím příkladu, mohou programátoři při psaní kódu ručně eliminovat duplicitní výrazy. Největším zdrojem CSE jsou mezilehlé sekvence kódu generované kompilátorem, například for pole výpočty indexování, kde není možné, aby vývojář ručně zasáhl. V některých případech mohou jazykové funkce vytvořit mnoho duplicitních výrazů. Například, C makra, kde rozšíření maker může vést k běžným dílčím výrazům, které nejsou patrné v původním zdrojovém kódu.

Překladatelé musí být obezřetní, pokud jde o počet dočasných položek vytvořených k udržení hodnot. Vytvoří se nadměrný počet dočasných hodnot zaregistrujte tlak možná vedoucí k rozlití registrů do paměti, což může trvat déle než jednoduše přepočítat aritmetický výsledek, když je to potřeba.

Viz také

Reference

  1. ^ Steven Muchnick; Muchnick and Associates (15. srpna 1997). Pokročilá implementace návrhu kompilátoru. Morgan Kaufmann. ISBN  978-1-55860-320-2. Běžná eliminace subexprese.