LuaJIT – Just in Time překladač pro programovací jazyk Lua (10 – JIT překlad do nativního kódu)

Obsah

1. LuaJIT – Just in Time překladač pro programovací jazyk Lua (10 – JIT překlad do nativního kódu)

2. Zdrojový text → bajtkód → sekvence pseudoinstrukcí → nativní kód

3. Reprezentace nalezené trasy mezikódem (pseudoinstrukcemi)

   3.1 Typy operandů

   3.2 Vybrané pseudoinstrukce

   3.3 Formát výpisu sekvence pseudoinstrukcí

4. Demonstrační příklady – jednoduché programové smyčku přeložené do sekvence pseudoinstrukcí

   4.1 Just-in-time překlad počítané programové smyčky typu for

   4.2 Just-in-time překlad programové smyčky typu while

5. Demonstrační příklady – překlad smyček s podmínkami do sekvence pseudoinstrukcí

   5.1 Just-in-time překlad programové smyčky s jedním rozvětvením

   5.2 Just-in-time překlad programové smyčky se složitějším rozvětvením

6. Demonstrační příklad – překlad volání funkce do sekvence pseudoinstrukcí

7. Překlad ze sekvence pseudoinstrukcí do nativního kódu

8. Zdrojové kódy dnes použitých demonstračních příkladů i vygenerované sekvence pseudoinstrukcí

9. Literatura

10. Odkazy na Internetu

1. LuaJIT – Just in Time překladač pro programovací jazyk Lua (10 – JIT překlad do nativního kódu)

V minulé a taktéž i předminulé části tohoto seriálu jsme si vysvětlili princip činnosti trasovacího JITu, na němž je celý LuaJIT postaven. Ovšem samotné trasování slouží zejména pro zjištění, které části programového kódu, konkrétně které instrukce bajtkódu je zapotřebí přeložit, tj. jakou část bajtkódu lze považovat za hot loop či hot call. Jakmile jsou vhodné trasy detekovány, je nutné provést vlastní just-in-time překlad. Právě toto je téma, jemuž se budeme věnovat dnes. Na několika demonstračních příkladech, s nimiž jsme se již seznámili v předchozích částech tohoto seriálu, si ukážeme a taktéž zjednodušeně popíšeme způsob, jakým je proveden kýžený překlad a popř. i optimalizace nativního strojového kódu.

2. Zdrojový text → bajtkód → sekvence pseudoinstrukcí → nativní kód

Před podrobnějším popisem funkce překladače implementovaného v LuaJITu si zkusme stručně popsat, jaká cesta vede od zdrojového textu napsaného v jazyku Lua až k nativnímu (strojovému) kódu:

1. Na začátku celého řetězce se nachází zdrojový text, který typicky napíše vývojář v textovém editoru. V některých případech se jedná o generovaný zdrojový text, což se však nijak nedotýká problematiky JITu.
2. Při spuštění LuaJITu příkazem luajit jméno_projektu je zdrojový text postupně překládán do bajtkódu, kterému jsme se podrobně věnovali v šesti dílech tohoto seriálu: [2], [3], [4], [5], [6] a [7].
3. Bajtkód je ihned interpretován a současně se v něm vyhledávají hot calls a hot loops, tedy takové sekvence instrukcí bajtkódu, které by bylo vhodné JITovat.
4. Jakmile je nalezena vhodná stopa, je sekvence instrukcí bajtkódu tvořící tuto stopu přeložena do sekvence pseudoinstrukcí. V tomto mezistupni se již pracuje s konkrétními datovými typy a samotný formát pseudoinstrukcí je zvolen takovým způsobem, aby se dobře prováděly optimalizace i poslední krok.
5. Posledním krokem je transformace z pseudoinstrukcí do nativního strojového kódu. Zde se používají šablony připravené pro konkrétní typy mikroprocesorů a hlavním úkolem JITu je alokace registrů. Strojový kód však stále obsahuje vložené kontroly, zda jsou dodrženy výchozí podmínky provádění stopy. Pokud se například dojde k tomu, že se má vykonat jiná větev, je běh nativní části přerušen.

3. Reprezentace nalezené trasy mezikódem (pseudoinstrukcemi)

Trasovací překladač při nalezení stopy vhodné pro JITování provede nejdříve překlad této stopy do sekvence pseudoinstrukcí. Přitom se využívá takzvaná SSA forma, jejíž základní vlastnosti jsou popsány například na stránce http://en.wikipedia.org/wi­ki/Static_single_assignmen­t_form. Většina pseudoinstrukcí používaných LuaJITem obsahuje dva operandy, až na několik výjimek (jednou z výjimek je pseudoinstrukce rezervovaná pro volání funkce). Navíc je u každé pseudoinstrukce specifikován i typ výsledku, což je možná poněkud překvapivé, protože jak programovací jazyk Lua, tak i bajtkód LuaJITu využívá dynamické typování. Nicméně na úrovni pseudoinstrukcí se již nacházíme na tak nízké úrovni, že je nutné začít pracovat s konkrétními datovými typy, protože i samotné instrukce mikroprocesoru pracují s konkrétními datovými typy (bajt, short, int, float atd. atd.). Pro nás je v tuto chvíli důležitý zejména fakt, že se na sekvenci pseudoinstrukcí můžeme snadno podívat, a to s využitím volby -jdump (s případnými parametry).

3.1 Typy operandů

V předchozím odstavci jsme se dozvěděli, že u každé pseudoinstrukce je kromě vlastního operačního kódu a popř. i operandů navíc specifikován i typ výsledku. To například znamená, že dále zmíněná pseudoinstrukce nazvaná SLOAD může načítat (a vracet) celá čísla (int), hodnoty s plovoucí řádovou čárkou (flt/num) atd. JIT překladač následně na základě páru datový_typ+pseudoinstrukce začne generovat nativní kód, samozřejmě s ohledem na vlastnosti instrukční sady cílového mikroprocesoru. V následující tabulce jsou vypsány typy výsledků, které se mohou objevit u všech pseudoinstrukcí:

Zajímavé je, že se v dalších čtyřech příkladech setkáme jen a pouze s typem int, tj. s pseudoinstrukcemi pracujícími s 32bitovými hodnotami se znaménkem a navíc ještě s typem num, který odpovídá běžným numerickým hodnotám používaným v jazyku Lua. Pouze u pátého příkladu se pracuje s typem fun (reference na funkci).

3.2 Vybrané pseudoinstrukce

V následujících demonstračních příkladech, resp. přesněji řečeno v sekvenci vygenerovaných pseudoinstrukcí, se setkáme s výpisem nalezených stop reprezentovaných jak bajtkódem, tak i posloupností pseudoinstrukcí. Kupodivu si v prvních čtyřech demonstračních příkladech vystačíme jen se šesti pseudoinstrukcemi, které jsou vypsány v tabulce umístěné pod tímto odstavcem:

Instrukce nazvaná SLOAD bude v demonstračních příkladech používána pravidelně. Slouží pro načtení hodnoty ze slotu, výsledkem instrukce je pak načtená hodnota (daného typu). Zajímavé je adresování slotů, protože index první lokální proměnné má hodnotu 1 a ne 0. Při porovnání bajtkódu s pseudoinstrukcemi to může být poněkud matoucí. Pseudoinstrukce ADD a ADDOV provádí součet obou operandů, druhá z těchto pseudoinstrukcí navíc provádí kontrolu, zda nedošlo k přetečení výsledku. Tato pseudoinstrukce se často používá právě při implementaci programových smyček.

Zvláštní postavení mají pseudoinstrukce LE, LT a ještě dalších deset podobných pseudoinstrukcí, o nichž se zmíníme příště. Tyto pseudoinstrukce se podobají podmíněným skokům, ovšem s tím rozdílem, že neobsahují explicitně zadanou adresu cíle. Pokud je podmínka reprezentovaná těmito pseudoinstrukcemi splněna, neprovede se žádná činnost, pokud však podmínka splněna není, dojde k ukončení běhu stopy a navíc k obnově předchozího stavu procesu. Díky tomuto mechanismu je možné v runtime reagovat na stav, kdy dojde k porušení nějaké podmínky, která platila při nalezení stopy – typickým příkladem je programová smyčka s větvením uvnitř této smyčky.

V pátém příkladu, kde je zpracováno volání funkce, se objevují i další pseudoinstrukce:

3.3 Formát výpisu sekvence pseudoinstrukcí

Sekvenci pseudoinstrukcí lze snadno vypsat s využitím přepínače -jdump. Při použití tohoto přepínače lze specifikovat poměrně velké množství voleb:

Podívejme se nyní na to, jak vypadá výchozí výstupní formát do plaintextu. Jedná se o stopu jednoduché programové smyčky, v níž se neprovádí větvení:

---- TRACE 1 IR
0001    int SLOAD  #3    I
0002 >  int SLOAD  #2    T
0003 >+ int ADDOV  0002  +1
0004  + int ADD    0001  +1
0005 >  int LE     0004  +60
0006 ------ LOOP ------------
0007 >+ int ADDOV  0003  +1
0008  + int ADD    0004  +1
0009 >  int LE     0008  +60
0010    int PHI    0004  0008
0011    int PHI    0003  0007
---- TRACE 1 stop -> loop

Význam údajů umístěných v jednotlivých sloupcích:

Typ operandů lze jednoduše rozpoznat podle jejich prvního znaku:

4. Demonstrační příklady – jednoduché programové smyčku přeložené do sekvence pseudoinstrukcí

Způsob činnosti just-in-time překladače implementovaného v LuaJITu si ukážeme na pětici demonstračních příkladů, s nimiž jsme se již setkali v minulé a předminulé části tohoto seriálu. U každého příkladu bude (znovu) uveden jeho zdrojový text, sekvence instrukcí bajtkódu detekovaná pro každou stopu a samozřejmě též sekvence pseudoinstrukcí vygenerovaných z bajtkódu.

4.1 Just-in-time překlad počítané programové smyčky typu for

Podívejme se na dnešní první demonstrační příklad nazvaný test41.lua (s tímto příkladem jsme se již setkali předminule). Tento demonstrační příklad je velmi jednoduchý, protože se v něm nachází pouze jediná počítaná programová smyčka typu for, která je prováděna celkem 60×. Toto číslo již zajistí detekci hot loop a tedy i JIT překlad:

--
-- LuaJIT: demonstrační příklad číslo 41.
--
-- Test JITu.
--
 
 
 
local i
local sum = 0
 
for i = 1,60 do
    sum = sum + 1
end
 
print(sum)
 
 
 
--
-- Finito.
--

Při běhu tohoto programu se nalezne pouze jediná stopa (trace) tvořená samozřejmě tělem programové smyčky. LuaJIT vypíše informace o této stopě následujícím způsobem (včetně instrukcí bajtkódu, které stopu tvoří):

---- TRACE 1 start test41.lua:12
0007  ADDVN    1   1   0  ; 1
0008  FORL     2 => 0007

Po transformaci do pseudoinstrukcí vypadá programová smyčka a její inicializační část následovně:

---- TRACE 1 IR
0001    int SLOAD  #3    I
0002 >  int SLOAD  #2    T
0003 >+ int ADDOV  0002  +1
0004  + int ADD    0001  +1
0005 >  int LE     0004  +60
0006 ------ LOOP ------------
0007 >+ int ADDOV  0003  +1
0008  + int ADD    0004  +1
0009 >  int LE     0008  +60
0010    int PHI    0004  0008
0011    int PHI    0003  0007
---- TRACE 1 stop -> loop

Za povšimnutí stojí několik zajímavostí. První z nich je, že řídicí proměnná (počitadlo) smyčky je typu int a nikoli num, což znamená, že LuaJIT korektně odhadl strukturu aplikace a datové typy použité v runtime. Dále zde můžeme vidět asserce (předpoklady) tvořené pseudoinstrukcemi LE použitými jak před vlastním tělem smyčky, tak i na začátku jejího těla. Instrukce ADD slouží ke zvýšení počitadla smyčky, zatímco instrukce ADDOV ke zvýšení hodnoty proměnné sum.

Pokud by se hodnota proměnné sum snižovala o jedničku, vypadal by bajtkód odlišně:

---- TRACE 1 start test41.lua:12
0007  SUBVN    1   1   0  ; 1
0008  FORL     2 => 0007

A samozřejmě by se změnila i sekvence pseudoinstrukcí (včetně změny typu dat):

---- TRACE 1 IR
0001    int SLOAD  #3    CI
0002 >  int SLOAD  #2    T
0003  + num SUB    0002  +1
0004  + int ADD    0001  +1
0005 >  int LE     0004  +60
0006 ------ LOOP ------------
0007  + num SUB    0003  +1
0008  + int ADD    0004  +1
0009 >  int LE     0008  +60
0010    int PHI    0004  0008
0011    int PHI    0003  0007
---- TRACE 1 stop -> loop

4.2 Just-in-time překlad programové smyčky typu while

V dnešním druhém demonstračním příkladu je namísto počítané programové smyčky typu for použita univerzální smyčka while s podmínkou vyhodnocovanou na začátku. V bajtkódu LuaJITu se namísto speciální instrukce FORI v tomto případě používá instrukce LOOP a podmíněný skok realizovaný instrukcí ISGE:

--
-- LuaJIT: demonstrační příklad číslo 43.
--
-- Test JITu.
--
 
 
 
local i = 0
local sum = 0
 
while i < 100 do
    sum = sum + 1
    i = i + 1
end
 
print(sum)
 
 
 
--
-- Finito.
--

Programová smyčka je opět – podle očekávání – detekována jako stopa vhodná pro JITování, ovšem na rozdíl od předchozího demonstračního příkladu je struktura bajtkódu zcela odlišná, protože se namísto speciální instrukce FORL používá instrukce LOOP doplněná o ISGE:

---- TRACE 1 start test43.lua:12
0007  ADDVN    1   1   0  ; 1
0008  ADDVN    0   0   0  ; 1
0009  JMP      2 => 0003
0003  KSHORT   2 100
0004  ISGE     0   2
0005  JMP      2 => 0010
0006  LOOP     2 => 0010

Odlišný bajtkód se samozřejmě projeví i na sekvenci pseudoinstrukcí:

---- TRACE 1 IR
0001 >  int SLOAD  #2    T
0002 >+ int ADDOV  0001  +1
0003 >  int SLOAD  #1    T
0004 >+ int ADDOV  0003  +1
0005 >  int LT     0004  +100
0006 ------ LOOP ------------
0007 >+ int ADDOV  0002  +1
0008 >+ int ADDOV  0004  +1
0009 >  int LT     0008  +100
0010    int PHI    0002  0007
0011    int PHI    0004  0008
---- TRACE 1 stop -> loop

Opět si povšimněte použití datového typu int a taktéž využití pseudoinstrukcí ADDOV. Příště uvidíme, že se tyto pseudoinstrukce překládají poměrně složitým způsobem, a to kvůli tomu, aby se detekovalo přetečení výsledku a přechod na použití jiného datového typu.

5. Demonstrační příklady – překlad smyček s podmínkami do sekvence pseudoinstrukcí

Již minule jsme se zabývali problematikou programových smyček obsahujících ve svém těle podmínku či větší množství podmínek (větvení). Víme již, že se větvení – pokud se samozřejmě provádí dostatečně často – přeloží do samostatné stopy, takže si pojďme toto tvrzení ověřit na dvojici demonstračních příkladů.

5.1 Just-in-time překlad programové smyčky s jedním rozvětvením

Donutit LuaJIT k tomu, aby provedl i překlad podmínky umístěné uvnitř počítané programové smyčky, je ve skutečnosti velmi snadné, jak jsme si ostatně vysvětlili minule – postačuje totiž zvýšit počet iterací smyčky a současně i počet vstupů do podmíněného bloku. Dnešní třetí demonstrační příklad pojmenovaný test49.lua používá pro smyčku tisíc iterací a uvnitř smyčky se po 500 iteracích provádí vnitřní větev:

--
-- LuaJIT: demonstrační příklad číslo 49.
--
-- Test JITu - programová smyčka s rozvětvením, zvýšení počtu iteraci.
--
 
 
 
-- deklarace a inicializace lokálních proměnných
local i
local x = 0
local y = 0
 
 
 
-- programová smyčka s rozvětvením
for i = 1,1000 do
    x = x + 1
    if i > 500 then
        y = y + 1
    end
end
 
print(x, y)
 
 
 
--
-- Finito.
--

Nyní si musíme ověřit, že se větvení skutečně přeložilo do samostatné stopy. Nejprve trasovací JIT odhalil celou programovou smyčku, a to včetně podmíněného skoku:

---- TRACE 1 start test49.lua:17
0008  ADDVN    1   1   0  ; 1
0009  KSHORT   7 500
0010  ISGE     7   6
0011  JMP      7 => 0013
0013  FORL     3 => 0008

A následně našel a JIToval i její větev (pouze tuto větev):

---- TRACE 2 start 1/1 test49.lua:20
0012  ADDVN    2   2   0  ; 1
0013  JFORL    3   1

Jak vypadá transformace bajtkódu do pseudokódu můžeme vidět níže:

---- TRACE 1 IR
0001    int SLOAD  #4    I
0002 >  int SLOAD  #2    T
0003 >+ int ADDOV  0002  +1
0004 >  int LE     0001  +500
0005  + int ADD    0001  +1
0006 >  int LE     0005  +1000
0007 ------ LOOP ------------
0008 >+ int ADDOV  0003  +1
0009 >  int LE     0005  +500
0010  + int ADD    0005  +1
0011 >  int LE     0010  +1000
0012    int PHI    0005  0010
0013    int PHI    0003  0008
---- TRACE 1 stop -> loop

Stopa nalezená pro větvení ve smyčce je oproti kódu celé smyčky dosti krátká, a to z toho důvodu, že tato stopa má přímou návaznost na stopu vlastní smyčky:

---- TRACE 2 IR
0001    int SLOAD  #2    PI
0002    int SLOAD  #4    PI
0003 >  int SLOAD  #3    T
0004 >  int ADDOV  0003  +1
0005    int ADD    0002  +1
0006 >  int LE     0005  +1000
---- TRACE 2 stop -> 1

Poprvé zde vidíme, že pseudoinstrukce jsou v každé stopě indexovány od jedničky.

5.2 Just-in-time překlad programové smyčky se složitějším rozvětvením

V demonstračním příkladu se jménem test50.lua se ve vnější programové smyčce nachází hned tři větve. Vzhledem k tomu, že je počet iterací nastaven na hodnotu 1000 a podmínky ve větvích umožní vstup do podmíněných bloků v 1000–100=900, 1000–200=800 a 1000–300=700 iteracích, budou detekovány a následně přeloženy celkem čtyři stopy – vlastní programová smyčka a tři stopy obsahující jednotlivé větve:

--
-- LuaJIT: demonstrační příklad číslo 50.
--
-- Test JITu - programová smyčka se složitějším rozvětvením
--
 
 
 
-- deklarace a inicializace lokálních proměnných
local i
local x = 0
local y = 0
local z = 0
 
 
 
-- programová smyčka s rozvětvením
for i = 1,1000 do
    if i > 100 then
        x = x + 1
    end
    if i > 200 then
        y = y + 1
    end
    if i > 300 then
        z = z + 1
    end
end
 
print(x, y, z)
 
 
 
--
-- Finito.
--

Nyní bude velmi zajímavé sledovat především strukturu bajtkódu. Podle očekávání dostaneme celkem čtyři stopy, přičemž tři stopy budou navázány na nadřazenou stopu programové smyčky.

Stopa celé smyčky, včetně přeskoků větvení (jednotlivé větve se totiž neprovádí od začátku!):

---- TRACE 1 start test50.lua:18
0009  KSHORT   8 100
0010  ISGE     8   7
0011  JMP      8 => 0013
0013  KSHORT   8 200
0014  ISGE     8   7
0015  JMP      8 => 0017
0017  KSHORT   8 300
0018  ISGE     8   7
0019  JMP      8 => 0021
0021  FORL     4 => 0009

Stopa prvního větvení, včetně přeskoku dalších dvou větvení (důvod je stejný jako důvod uvedený výše):

---- TRACE 2 start 1/1 test50.lua:20
0012  ADDVN    1   1   0  ; 1
0013  KSHORT   8 200
0014  ISGE     8   7
0015  JMP      8 => 0017
0017  KSHORT   8 300
0018  ISGE     8   7
0019  JMP      8 => 0021
0021  JFORL    4   1

Stopa druhého větvení, včetně přeskoku třetí podmínky:

---- TRACE 3 start 2/1 test50.lua:23
0016  ADDVN    2   2   0  ; 1
0017  KSHORT   8 300
0018  ISGE     8   7
0019  JMP      8 => 0021
0021  JFORL    4   1

Konečně zbývá třetí podmínka, která je splněna a tudíž i detekována naposledy:

---- TRACE 4 start 3/1 test50.lua:26
0020  ADDVN    3   3   0  ; 1
0021  JFORL    4   1

Sekvence pseudoinstrukcí vygenerovaných z výše vypsaných bajtkódů jsou již poměrně složité (a ještě složitější bude transformace do nativního strojového kódu :-):

---- TRACE 1 IR
0001    int SLOAD  #5    I
0002 >  int LE     0001  +100
0003 >  int LE     0001  +200
0004 >  int LE     0001  +300
0005  + int ADD    0001  +1
0006 >  int LE     0005  +1000
0007 ------ LOOP ------------
0008 >  int LE     0005  +100
0009 >  int LE     0005  +200
0010 >  int LE     0005  +300
0011  + int ADD    0005  +1
0012 >  int LE     0011  +1000
0013    int PHI    0005  0011
---- TRACE 1 stop -> loop
 
---- TRACE 2 IR
0001    int SLOAD  #5    PI
0002 >  int SLOAD  #2    T
0003 >  int ADDOV  0002  +1
0004 >  int LE     0001  +200
0005 >  int LE     0001  +300
0006    int ADD    0001  +1
0007 >  int LE     0006  +1000
---- TRACE 2 stop -> 1
 
---- TRACE 3 IR
0001    int SLOAD  #2    PI
0002    int SLOAD  #5    PI
0003 >  int SLOAD  #3    T
0004 >  int ADDOV  0003  +1
0005 >  int LE     0002  +300
0006    int ADD    0002  +1
0007 >  int LE     0006  +1000
---- TRACE 3 stop -> 1
 
---- TRACE 4 IR
0001    int SLOAD  #2    PI
0002    int SLOAD  #3    PI
0003    int SLOAD  #5    PI
0004 >  int SLOAD  #4    T
0005 >  int ADDOV  0004  +1
0006    int ADD    0003  +1
0007 >  int LE     0006  +1000
---- TRACE 4 stop -> 1

6. Demonstrační příklad – překlad volání funkce do sekvence pseudoinstrukcí

Dnešní pátý a současně i poslední demonstrační příklad je založen na deklaraci funkce adder. Tato funkce je volána v trojici programových smyček. V první smyčce se provede prvních padesát volání, v další smyčce dalších padesát volání a konečně ve smyčce třetí se funkce zavolá po 101 až 150. Proč je příklad organizován takovým způsobem? Jde nám o to zabránit LuaJITu v detekci smyček s velkým počtem iterací, přičemž hodnota 50 leží pod hraniční hodnotou hotcall=56, takže smyčky samotné JITovány nebudou, ale funkce adder nakonec ano (samozřejmě až v poslední smyčce):

--
-- LuaJIT: demonstrační příklad číslo 53.
--
-- Test JITu - volání funkce
--
 
 
 
-- deklarace a inicializace lokálních proměnných
local i
local x = 0
local y = 0
 
 
 
-- funkce, která se bude JITovat
function adder()
    x = x + 1
    y = y + 1
end
 
 
 
-- programová smyčka, která se neJITuje
for i = 1,50 do
    adder()
end
print("1")
 
-- programová smyčka, která se neJITuje
for i = 1,50 do
    adder()
end
print("2")
 
-- programová smyčka, která se neJITuje
for i = 1,50 do
    adder()
end
print("3")
 
print(x,y)
 
 
 
--
-- Finito.
--

Instrukce bajtkódu v detekované stopě nám prozradí, že je stopa skutečně nalezena ve funkci adder, protože zde můžeme vidět přístup k vázaným proměnným x a y. Instrukcí UGET se přečte aktuální hodnota vázané proměnné a instrukcí USETV se do této proměnné uloží nová hodnota z registru (zde konkrétně z registru číslo 1):

---- TRACE 1 start test53.lua:17
0001  UGET     0   0      ; x
0002  ADDVN    0   0   0  ; 1
0003  USETV    0   0      ; x
0004  UGET     0   1      ; y
0005  ADDVN    0   0   0  ; 1
0006  USETV    1   0      ; y
0007  RET0     0   1

Po transformaci do sekvence pseudoinstrukcí můžeme vidět náhradu UGET za ULOAD a USETV za USTORE. Navíc se zde – zcela poprvé – objevuje i pseudoinstrukce UREFO vracející referenci na funkci:

---- TRACE 1 IR
0001    fun SLOAD  #0    R
0002 >  p32 UREFO  0001  #0
0003 >  int ULOAD  0002
0004 >  int ADDOV  0003  +1
0005    int USTORE 0002  0004
0006 >  p32 UREFO  0001  #1
0007 >  int ULOAD  0006
0008 >  int ADDOV  0007  +1
0009    int USTORE 0006  0008
---- TRACE 1 stop -> return

7. Překlad ze sekvence pseudoinstrukcí do nativního kódu

Posledním krokem JIT překladu je transformace pseudoinstrukcí do nativního kódu. Ukažme si transformaci stopy z dnešního druhého demonstračního příkladu:

---- TRACE 1 IR
0001 >  int SLOAD  #2    T
0002 >+ int ADDOV  0001  +1
0003 >  int SLOAD  #1    T
0004 >+ int ADDOV  0003  +1
0005 >  int LT     0004  +100
0006 ------ LOOP ------------
0007 >+ int ADDOV  0002  +1
0008 >+ int ADDOV  0004  +1
0009 >  int LT     0008  +100
0010    int PHI    0002  0007
0011    int PHI    0004  0008
---- TRACE 1 stop -> loop

Překlad do nativního strojového kódu pro 32bitové mikroprocesory ARM vypadá následovně:

---- TRACE 1 start test43.lua:12
---- TRACE 1 mcode 84
00397fac  ldrd  r4, [r9, #8]
00397fb0  cmn   r5, #14
00397fb4  blne  0x00390018      ->0
00397fb8  adds  r4, r4, #1
00397fbc  blvs  0x00390018      ->0
00397fc0  ldrd  r6, [r9]
00397fc4  cmn   r7, #14
00397fc8  blne  0x00390018      ->0
00397fcc  adds  r6, r6, #1
00397fd0  blvs  0x00390018      ->0
00397fd4  cmp   r6, #100
00397fd8  blge  0x0039001c      ->1
->LOOP:
00397fdc  mov   r11, r6
00397fe0  mov   r10, r4
00397fe4  adds  r4, r10, #1
00397fe8  blvs  0x00390020      ->2
00397fec  adds  r6, r11, #1
00397ff0  blvs  0x00390020      ->2
00397ff4  cmp   r6, #100
00397ff8  blt   0x00397fdc      ->LOOP
00397ffc  bl    0x00390024      ->3
---- TRACE 1 stop -> loop

Povšimněte si především množství podmíněných skoků (blne, blvs), kterými jsou realizovány asserce zmíněné v předchozím textu.

Pro platformu x86_64 dostaneme – podle očekávání – sice identický, ale v detailech přece jen odlišný „stroják“:

---- TRACE 1 mcode 104
0bceff8e  mov dword [0x409604a0], 0x1
0bceff99  movsd xmm1, [0x404b0d38]
0bceffa2  movsd xmm0, [0x404b0d40]
0bceffab  cmp dword [rdx+0xc], 0xfffeffff
0bceffb2  jnb 0x0bce0010        ->0
0bceffb8  movsd xmm6, [rdx+0x8]
0bceffbd  addsd xmm6, xmm1
0bceffc1  cmp dword [rdx+0x4], 0xfffeffff
0bceffc8  jnb 0x0bce0010        ->0
0bceffce  movsd xmm7, [rdx]
0bceffd2  addsd xmm7, xmm1
0bceffd6  ucomisd xmm0, xmm7
0bceffda  jbe 0x0bce0014        ->1
->LOOP:
0bceffe0  addsd xmm6, xmm1
0bceffe4  movaps xmm5, xmm7
0bceffe7  addsd xmm7, xmm1
0bceffeb  ucomisd xmm0, xmm7
0bceffef  ja 0x0bceffe0 ->LOOP
0bcefff1  jmp 0x0bce001c        ->3
---- TRACE 1 stop -> loop

I zde můžeme vidět několik podmíněných skoků (jnb, jbe) s podobným významem jako v předchozím nativním kódu. Podrobnosti si v případě zájmu vysvětlíme příště.

8. Zdrojové kódy dnes použitých demonstračních příkladů i vygenerované sekvence pseudoinstrukcí

Všechny dnes použité demonstrační příklady byly, jak je tomu ostatně v tomto seriálu již dlouhodobějším zvykem, uloženy do Git (přesněji řečeno do GitHub) repositáře umístěného na adrese https://github.com/tisnik/luajit-examples.

Následuje tabulka obsahující odkazy na poslední verze dnešních příkladů i výstupních souborů: trasovací informace, mezikód i nově upravený Makefile:

9. Literatura

1. Bolz, Cuni, Fijalkowski, Rigo:
   „Tracing the Meta-Level: PyPy's Tracing JIT Compiler“
2. Vasanth Bala, Evelyn Duesterwald, Sanjeev Banerjia:
   „Dynamo: A Transparent Dynamic Optimization System“
3. Bolz, Cuni, Fijalkowski, Leuschel, Pedroni, Rigo: „Allocation removal by partial evaluation in a tracing JIT“
4. Bolz:
   „Automatic JIT Compiler Generation with Runtime Partial Evaluation“
5. Bolz, Kuhn, Lienhard, Matsakis, Nierstrasz, Renggli, Rigo and T. Verwaest:
   „Back to the Future in One Week – Implementing a Smalltalk VM in PyPy“
   pages 123–139. 2008.
6. Bolz and Rigo:
   „How to not write a virtual machine“
   In Proceedings of the 3rd Workshop on Dynamic Languages and Applications (DYLA), 2007
7. Bruni, Verwaest:
   „PyGirl: generating Whole-System VMs from High-Level prototypes using PyPy“
   In Tools, accepted for publication, 2009.
8. Sullivan, Bruening, Baron, Garnett and Amarasinghe:
   „Dynamic native optimization of interpreters“
   In Proceedings of the 2003 Workshop on Interpreters,
   Virtual Machines and Emulators pages 50–57, San Diego, California, 2003. ACM.

10. Odkazy na Internetu

1. Static single assignment form (SSA)
   http://en.wikipedia.org/wi­ki/Static_single_assignmen­t_form
2. LuaJIT 2.0 SSA IR
   http://wiki.luajit.org/SSA-IR-2.0
3. Dynamic Assembler
   http://luajit.org/dynasm.html
4. The Unofficial DynASM Documentation: Introduction
   http://corsix.github.io/dynasm-doc/index.html
5. Have tracing JIT compilers won?
   http://lambda-the-ultimate.org/node/3851
6. Tracing just-in-time compilation
   http://en.wikipedia.org/wi­ki/Tracing_just-in-time_compilation
7. How does LuaJIT's trace compiler work?
   http://www.freelists.org/pos­t/luajit/How-does-LuaJITs-trace-compiler-work,1
8. How does LuaJIT's trace compiler work?
   http://stackoverflow.com/qu­estions/20266523/how-does-luajits-trace-compiler-work
9. TraceMonkey
   https://wiki.mozilla.org/Ja­vaScript:TraceMonkey
10. TraceMonkey
    http://brendaneich.com/2008/08/tra­cemonkey-javascript-lightspeed/
11. improving JavaScript performance with JägerMonkey
    http://hacks.mozilla.org/2010/03/im­proving-javascript-performance-with-jagermonkey/
12. Wikipedia: Mezijazyk
    http://cs.wikipedia.org/wi­ki/Mezijazyk
13. The LuaJIT Project
    http://luajit.org/index.html
14. LuaJIT FAQ
    http://luajit.org/faq.html
15. LuaJIT Performance Comparison
    http://luajit.org/performance.html
16. LuaJIT 2.0 intellectual property disclosure and research opportunities
    http://article.gmane.org/gma­ne.comp.lang.lua.general/58908
17. LuaJIT Wiki
    http://wiki.luajit.org/Home
18. LuaJIT 2.0 Bytecode Instructions
    http://wiki.luajit.org/Bytecode-2.0
19. Programming in Lua 9.1 – Coroutine Basics,
    http://www.lua.org/pil/9.1.html
20. Programming in Lua (first edition)
    http://www.lua.org/pil/contents.html
21. Programming in Lua: 6 – More about Functions
    http://www.lua.org/pil/6.html
22. Lua Lanes
    http://kotisivu.dnainternet­.net/askok/bin/lanes/
23. Programming in Lua: 6.1 – Closures
    http://www.lua.org/pil/6.1.html
24. Programming in Lua: 9.1 – Coroutine Basics
    http://www.lua.org/pil/9.1.html
25. Programming in Lua: Numeric for
    http://www.lua.org/pil/4.3.4.html
26. Programming in Lua: break and return
    http://www.lua.org/pil/4.4.html
27. Programming in Lua: Tables
    http://www.lua.org/pil/2.5.html
28. Programming in Lua: Table Constructors
    http://www.lua.org/pil/3.6.html
29. Programovací jazyk Lua
    http://palmknihy.cz/web/kni­ha/programovaci-jazyk-lua-12651.htm
30. Lua: Tables Tutorial
    http://lua-users.org/wiki/TablesTutorial
31. Lua: Control Structure Tutorial
    http://lua-users.org/wiki/ControlStruc­tureTutorial
32. Lua Types Tutorial
    http://lua-users.org/wiki/LuaTypesTutorial
33. Goto Statement in Lua
    http://lua-users.org/wiki/GotoStatement
34. Lua 5.2 sources
    http://www.lua.org/source/5.2/
35. Lua 5.2 sources – lopcodes.h
    http://www.lua.org/source/5­.2/lopcodes.h.html
36. Lua 5.2 sources – lopcodes.c
    http://www.lua.org/source/5­.2/lopcodes.c.html
37. Lambda the Ultimate: Coroutines in Lua,
    http://lambda-the-ultimate.org/node/438
38. Coroutines Tutorial,
    http://lua-users.org/wiki/CoroutinesTutorial
39. Lua Coroutines Versus Python Generators,
    http://lua-users.org/wiki/LuaCorouti­nesVersusPythonGenerators