Úniková analýza - Escape analysis

v optimalizace kompilátoru, úniková analýza je metoda pro stanovení dynamického rozsahu ukazatele - kde v programu lze přistupovat k ukazateli. Souvisí to s analýza ukazatele a tvarová analýza.

Když je proměnná (nebo objekt) přidělena v a podprogram, a ukazatel do proměnné plechovky uniknout jiným vlákna provádění nebo volání podprogramů. Pokud implementace používá zadní volání optimalizace (obvykle požadována pro funkční jazyky ), objekty mohou být také považovány za unikající do volala podprogramy. Pokud jazyk podporuje prvotřídní pokračování (stejně jako Systém a Standardní ML z New Jersey ), části zásobník volání může také uniknout.

Pokud podprogram alokuje objekt a vrátí na něj ukazatel, lze k objektu přistupovat z neurčených míst v programu - ukazatel „unikl“. Ukazatele mohou také uniknout, pokud jsou uloženy v globálních proměnných nebo jiných datových strukturách, které naopak uniknou aktuální proceduře.

Úniková analýza určuje všechna místa, kde lze ukazatel uložit, a zda může být prokázáno, že životnost ukazatele je omezena pouze na aktuální proceduru a / nebo vlákno.

Optimalizace

Kompilátor může použít výsledky únikové analýzy jako základ pro optimalizace:[1]

  • Konvertování přidělení haldy na přidělení zásobníku.[2] Pokud je objekt přidělen v podprogramu a ukazatel na objekt nikdy neunikne, může být objekt kandidátem na přidělení zásobníku namísto přidělení haldy. V jazycích sbíraných odpadky to může snížit, jak často musí sběratel běžet.
  • Vynechání synchronizace. Pokud se zjistí, že je objekt přístupný pouze z jednoho vlákna, lze operace s objektem provádět bez synchronizace.
  • Rozbíjení předmětů nebo skalární náhrada.[3] Lze nalézt objekt, ke kterému lze přistupovat způsoby, které nevyžadují existenci objektu jako struktury sekvenční paměti. To může umožnit uložení částí (nebo všech) objektu do registrů CPU namísto do paměti.

Praktické úvahy

v objektově orientovaný programovací jazyky, dynamické překladače jsou zvláště dobrými kandidáty na provedení únikové analýzy. V tradiční statické kompilaci může přepsání metody znemožnit únikovou analýzu, protože jakákoli volaná metoda může být přepsána verzí, která umožňuje úniku ukazatele. Dynamické kompilátory mohou provádět únikovou analýzu pomocí dostupných informací o přetížení a znovu provést analýzu, když jsou relevantní metody přepsány dynamickým načítáním kódu.[1]

Popularita Programovací jazyk Java učinil z únikové analýzy cíl zájmu. Java je kombinace alokace objektů pouze na haldu, vestavěné vlákno, slunce HotSpot dynamický překladač a OpenJ9 je Just-in-time kompilátor (JIT) vytváří kandidátskou platformu pro optimalizaci související s únikovou analýzou (viz Úniková analýza v Javě ). Úniková analýza je implementována v prostředí Java Standard Edition 6. Některé prostředí JVM podporují silnější variantu únikové analýzy s názvem částečná úniková analýza který umožňuje skalární nahrazení přiděleného objektu, i když objekt unikne některými cestami funkce.[4]

Příklad (Java)

třída Hlavní {  veřejnost statický prázdnota hlavní(Tětiva[] args) {    příklad();  }  veřejnost statický prázdnota příklad() {    Foo foo = Nový Foo(); // alokace    Bar bar = Nový Bar(); // alokace    bar.setFoo(foo);  }}třída Foo {}třída Bar {  soukromé Foo foo;  veřejnost prázdnota setFoo(Foo foo) {    tento.foo = foo;  }}

V tomto příkladu jsou vytvořeny dva objekty (komentovány pomocí alloc) a jeden z nich je uveden jako argument metody jiné. Metoda setFoo () ukládá odkaz na přijatý objekt Foo. Pokud by byl objekt Bar na hromadě, pak by odkaz na Foo unikl. Ale v tomto případě může kompilátor určit pomocí únikové analýzy, že samotný objekt Bar neunikne vyvolání příklad(). Což znamená, že ani odkaz na Foo nemůže uniknout. Kompilátor tedy může bezpečně přidělit oba objekty na zásobníku.

Příklady (schéma)

V následujícím příkladu vektor str neunikne do G, takže to může být přiděleno na zásobníku a poté odstraněno ze zásobníku před voláním G.

(definovat (F X)   (nechat ((str (make-vektor 10000)))      (vyplnit-vektor-s-dobrými věcmi str)      (G (vektorový ref str 7023))))

Pokud bychom však měli

(definovat (F X)   (nechat ((str (make-vektor 10000)))      (vyplnit-vektor-s-dobrými věcmi str)      (G str)))

pak buď str bude třeba přidělit na hromadu nebo (pokud G je známo kompilátoru, když F je zkompilován a chová se dobře) alokovaný na zásobníku takovým způsobem, že může zůstat na místě, když G je nazýván.

Pokud se k implementaci řídicích struktur podobných výjimkám používají pokračování, analýza úniku to může často detekovat, aby se zabránilo nutnosti skutečně přidělit pokračování a zkopírovat do něj zásobník volání. Například v

;; Přečte objekty schématu zadané uživatelem. Pokud jsou všechna čísla,;; vrací seznam obsahující všechny v pořadí. Pokud uživatel zadá jeden, který;; není číslo, okamžitě vrátí #f.(definovat (getnumlist)  (call / cc (lambda (pokračování)    (definovat (získat čísla)       (nechat ((další objekt (číst)))          (kond             ((eof-objekt? další objekt) '())             ((číslo? další objekt) (nevýhody další objekt (získat čísla)))             (jiný (pokračování #F)))))    (získat čísla))))

úniková analýza určí, že pokračování zachyceno call / cc neunikne, takže není třeba přidělit žádnou strukturu pokračování a vyvolání pokračování voláním pokračování lze implementovat zkrácením zásobníku.

Viz také

Reference

  1. ^ A b T. Kotzmann a H. Mössenböck, „Úniková analýza v kontextu dynamické kompilace a deoptimalizace“, v Proceedings of the 1st ACM / USENIX international conference on Virtual execution environment, New York, NY, USA, 2005, str. 111–120 .
  2. ^ Blanchet, Bruno (listopad 2003). "Escape Analysis for JavaTM: Theory and Practice". Transakce ACM v programovacích jazycích a systémech. 25 (6): 713–775. doi:10.1145/945885.945886. ISSN  0164-0925.
  3. ^ Kotzmann, Thomas; Mössenböck, Hanspeter (březen 2007). Podpora běhu pro optimalizace založené na únikové analýze. Mezinárodní symposium o generování a optimalizaci kódu (CGO'07). str. 49–60. CiteSeerX  10.1.1.394.5944. doi:10.1109 / CGO.2007.34. ISBN  978-0-7695-2764-2.
  4. ^ Stadler, Lukas; Würthinger, Thomas; Mössenböck, Hanspeter (2014). "Částečná analýza úniku a skalární nahrazení pro Javu". Sborník z každoročního mezinárodního sympozia IEEE / ACM o generování a optimalizaci kódu - CGO '14. str. 165–174. doi:10.1145/2581122.2544157. ISBN  9781450326704.