Řídké podmíněné konstantní šíření - Sparse conditional constant propagation

V počítačové vědě je řídké podmíněné konstantní šíření optimalizací často používanou v kompilátorech po převodu na statický jednotný formulář přiřazení (SSA). Současně odstraňuje některé druhy mrtvého kódu a šíří konstanty v celém programu. Kromě toho může najít více stálých hodnot, a tedy více příležitostí ke zlepšení, než samostatně aplikovat eliminaci mrtvého kódu a konstantní šíření v jakémkoli pořadí nebo libovolném počtu opakování.

Algoritmus pracuje provedením abstraktní interpretaci kódu v SSA formě. Během abstraktní interpretace obvykle používá plochou mřížku konstant pro hodnoty a globální prostředí mapující proměnné SSA na hodnoty v této mřížce. Jádro algoritmu spočívá v tom, jak zachází s interpretací větvových instrukcí . Při zjištění se podmínka pro větev vyhodnotí co nejlépe vzhledem k přesnosti abstraktních hodnot vázaných na proměnné v podmínce. Může se stát, že hodnoty jsou naprosto přesné (ani horní ani dolní), a proto může abstraktní provedení rozhodnout, kterým směrem se má větvit. Pokud hodnoty nejsou konstantní nebo není proměnná v podmínce definována, musí být oba směry větve brány, aby zůstaly konzervativní.

Po dokončení abstraktního výkladu jsou instrukce, které nebyly nikdy dosaženy, označeny jako mrtvý kód. SSA proměnné, u nichž se zjistí, že mají konstantní hodnoty, mohou být poté vloženy do (rozšířeny) v místě jejich použití.

Poznámky

  1. ^ Wegman, Mark N. a Zadeck, F. Kenneth. „ Neustálé šíření s podmíněnými větvemi .“ Transakce ACM o programovacích jazycích a systémech , 13 (2), duben 1991, strany 181-210.
  2. ^ Klikněte, Clifford a Cooper, Keith. „ Kombinování analýz, kombinace optimalizací “, Transakce ACM v programovacích jazycích a systémech , 17 (2), březen 1995, strany 181-196

Reference

  • Cooper, Keith D. a Torczon, Linda. Inženýrství překladače . Morgan Kaufmann. 2005.