LuaJIT – Just in Time překladač pro programovací jazyk Lua

Obsah

1. LuaJIT – Just in Time překladač pro programovací jazyk Lua

2. Formát instrukčních slov používaný v IR LuaJITu

3. Instrukce pro práci s konstantami a pro přesun hodnot mezi registry v IR LuaJITu

4. Základní instrukce pro volání funkcí a návrat z funkcí v IR LuaJITu

5. Demonstrační příklad číslo 1: zdrojový kód obsahující pouze příkaz return

6. Demonstrační příklad číslo 2: automatické přiřazení hodnoty nil k několika proměnným

7. Demonstrační příklad číslo 3: explicitní přiřazení hodnot k několika proměnným

8. Demonstrační příklad číslo 4: volání (builtin) funkce

9. Demonstrační příklad číslo 5: volání funkce s předáním parametru

10. Obsah následující části seriálu

11. Repositář se zdrojovými kódy dnešních pěti demonstračních příkladů

12. Odkazy na Internetu

1. LuaJIT – Just in Time překladač pro programovací jazyk Lua

Většina dosavadního obsahu seriálu o programovacím jazyku Java i o JVM byla skutečně věnována relativně podrobnému popisu vlastností virtuálního stroje Javy včetně jeho bajtkódu a taktéž principu činnosti Just in Time překladače (JIT Compiler). JITu JVM se ještě budeme věnovat podrobněji v budoucnosti, ovšem nebude na škodu se mezitím podívat na princip práce „konkurenčního“ JITu. Konkrétně se jedná o projekt LuaJIT. LuaJIT byl vybrán především s ohledem na jeho relativní jednoduchost (zejména v porovnání s monstrózním JVM JITem) a taktéž proto, že používá snadno pochopitelný mezijazyk (anglicky IR – Intermediate Representation), který je následně „JITován“. Tento IR je odlišný od bajtkódu jazyka Lua, s nímž jsme se již v tomto seriálu taktéž seznámili. Zatímco původní bajtkód jazyka Lua byl orientován především s ohledem na možnosti interpretru, je IR v LuaJITu navržen takovým způsobem, aby byl jeho následný překlad do nativního kódu poměrně snadný a rychlý, bez ohledu na architekturu použitého mikroprocesoru.

LuaJIT je z velké části dílem jediného programátora, který se jmenuje Mike Pall. To je velmi zajímavá skutečnost, zvláště když si uvědomíme, že LuaJIT je v současné verzi velmi kvalitní produkt podporující větší množství procesorových architektur (na tomto místě je pro porovnání důležité se zmínit o tom, jak dlouho trvalo, než byl JVM JIT adaptován například pro procesory ARM či ARM64; u dalších architektur jsme stále odkázáni na Zero a Shark). Jeden z problémů, kterým alespoň doposud LuaJIT trpí, je stále ještě nedokončená dokumentace, protože sám Mike píše: „I have little use for academic merits myself – I'm more interested in coding than writing papers“. Možná se nám v tomto seriálu podaří tuto mezeru v dokumentaci alespoň nepatrně zaplnit :-)

2. Formát instrukčních slov používaný v IR LuaJITu

Celý projekt LuaJIT se skládá z několika modulů, které při spuštění aplikace vytvořené v programovacím jazyku Lua musí vzájemně spolupracovat. Prvním modulem je překladač sloužící pro kompilaci zdrojového kódu napsaného v Lue do mezijazyka, který budeme v dalším textu zkráceně označovat IR – Intermediate Representation. IR je navržen takovým způsobem, aby mohl být buď interpretován (jde o ty části kódu, které nejsou spouštěny příliš často) nebo překládán do nativního strojového kódu s využitím JITu (většinou se jedná o opětovně spouštěné části kódu). Dnes se budeme zabývat především základními vlastnostmi IR, protože vlastní IR je dosti odlišný například od bajtkódu JVM, nehledě na to, že překlad do IR se provádí v případě LuaJITu zcela automaticky. IR používá takzvaný tříadresový kód a instrukce o pevné šířce třiceti dvou bitů. Přístup k instrukcím je tedy obecně mnohem rychlejší, než při použití instrukcí proměnné délky, tak jako je tomu v JVM.

Existují dva formáty instrukcí, přesněji řečeno dva způsoby rozdělení 32bitového slova na jednotlivá bitová pole. V obou formátech má operační kód instrukce šířku osmi bitů, obsazení dalších 24 bitů je však odlišné.

První formát se používá u instrukcí s trojicí operandů. Typické použití tohoto formátu je u aritmetických instrukcí:

Druhý formát dokáže adresovat pouze dva operandy, ovšem operand označený písmenem D má šířku šestnáct bitů a lze ho v některých instrukcích použít například k přímému uložení šestnáctibitové celočíselné konstanty se znaménkem (srov. s poměrně velkým množstvím instrukcí v bajtkódu JVM, které se pokouší o totéž, ale mnohem komplikovanějším způsobem):

3. Instrukce pro práci s konstantami a pro přesun hodnot mezi registry v IR LuaJITu

Demonstrační příklady popsané v navazujících kapitolách obsahují při překladu do IR pouze velmi malé množství instrukcí. Mezi zcela základní instrukce patří operace používané pro načtení proměnné do zvoleného slotu (nyní pro jednoduchost předpokládejme, že slotem je myšlena globální či lokální proměnná). V IR se pro načtení konstanty do zvoleného slotu může použít jedna ze čtyř instrukcí vypsaných v tabulce pod tímto odstavcem. Povšimněte si, že i když by teoreticky bylo možné použít pouze jedinou instrukci, je z důvodu optimalizací a zmenšení celkové velikosti IR k dispozici i instrukce KNIL (mnoho proměnných je v reálných programech implicitně inicializováno na hodnotu nil) a taktéž instrukce KSHORT (použití malých celočíselných konstant 0, 1 atd. je taktéž velmi časté):

V předchozí tabulce jsou pro označení typu/významu operandu použity následující termíny:

4. Základní instrukce pro volání funkcí a návrat z funkcí v IR LuaJITu

V IR vygenerovaných při překladu dále popsaných demonstračních příkladů se používají i další typy instrukcí. Především se jedná o instrukci MOV sloužící pro jednoduchý přenos hodnoty z jednoho slotu do slotu jiného:

Mnohem komplikovanější jsou instrukce nazvané RET0 a CALL. První z těchto instrukcí slouží k návratu z aktuálně prováděné funkce, druhá instrukce pak k volání funkce a k předání parametrů do volané funkce. Reference na volanou funkci je uložena ve slotu specifikovaném v operandu A, parametry funkce pak v následujících slotech. Návratové hodnoty jsou uloženy do slotů s indexy A až A+B-2. Konstanty uložené v operandech B a C tedy určují počet návratových hodnot resp. počet předávaných parametrů:

Poslední instrukcí IR, s níž se v dále uvedených a přeložených demonstračních příkladech setkáme, je instrukce GGET, která slouží k přístupu do globální tabulky _G (tato tabulka obsahuje všechny globální symboly). Tato instrukce bude využita k získání reference na volané funkce:

5. Demonstrační příklad číslo 1: zdrojový kód obsahující pouze příkaz return

Dnešní první demonstrační příklad je velmi jednoduchý – jedná se ve skutečnosti o nejjednodušší možný program naprogramovaný v jazyku Lua vůbec :-) Tento příklad obsahuje jen příkaz return, která způsobí ukončení programu. Interpret jazyka Lua sám otestuje, zda se za tímto příkazem nenachází další příkazy:

--
-- LuaJIT: demonstrační příklad číslo 1
--
-- Tento příklad obsahuje pouze jediný příkaz return.
--
 
 
 
-- jediny prikaz
return
 
 
 
-- finito

Podívejme se na překlad tohoto demonstračního příkladu do IR LuaJITu. Podle očekávání bude IR velmi jednoduchý, konkrétně bude obsahovat pouze jedinou instrukci RET0, kterou jsme si popsali ve čtvrté kapitole:

-- BYTECODE -- test01.lua:0-11
0001    RET0     0   1   ; návrat z programu

6. Demonstrační příklad číslo 2: automatické přiřazení hodnoty nil k několika proměnným

Druhý demonstrační příklad je taktéž velmi jednoduchý, protože obsahuje pouze definici čtyř proměnných nazvaných a, b, c a d. Tyto proměnné jsou lokální v rámci aktuálně zpracovávaného modulu. Lokální proměnné, kterým není explicitně přiřazena jiná hodnota, jsou implicitně inicializovány na hodnotu nil:

--
-- LuaJIT: demonstrační příklad číslo 2
--
-- Automatické přiřazení hodnoty nil k několika proměnným.
--
 
 
 
-- čtyři automaticky inicializované proměnné
local a
local b
local c
local d
 
 
 
-- finito

Překlad tohoto demonstračního příkladu do IR může být poněkud překvapivý, protože zde je inicializace všech čtyř proměnných zajištěna jedinou instrukcí KNIL. Překladač zde využil faktu, že se všechny proměnné nachází ve zdrojovém kódu za sebou a přiřadil jim po sobě jdoucí sloty 0 až 3:

-- BYTECODE -- test02.lua:0-14
0001    KNIL     0   3   ; uložit hodnotu nil do slotů 0 až 3 (včetně)
0002    RET0     0   1   ; návrat z programu

7. Demonstrační příklad číslo 3: explicitní přiřazení hodnot k několika proměnným

Dnešní třetí demonstrační příklad se do značné míry podobá příkladu druhému, ovšem s tím rozdílem, že zde je deklarováno šest proměnných a každé proměnné je přiřazena explicitní hodnota:

--
-- LuaJIT: demonstrační příklad číslo 3
--
-- Explicitní přiřazení hodnot k několika proměnným.
--
 
 
 
-- šest explicitně inicializovaných proměnných
local a = nil
local b = 0
local c = 42
local d = 42*42
local e = 42*42*42
local f = 42*42*42*42
 
 
 
-- finito

Překlad třetího demonstračního příkladu do IR je opět poněkud zvláštní. Především překvapí absence instrukce KNIL, která byla použita v příkladu druhém. Ve skutečnosti se v LuaJITu použije instrukce KNIL pouze v případě, že je nutné inicializovat na hodnotu nil větší počet proměnných, nejenom proměnnou jedinou. Namísto KNIL je zde použita instrukce KPRI. Pro přiřazení hodnot 0, 42 a 1764 je v IR využita instrukce KSHORT, která obsahuje příslušnou celočíselnou konstantu přímo ve svém instrukčním slovu, což je zajisté výhodné z hlediska délky IR i případných optimalizací. Ovšem již hodnota 74088 je tak velká, že se namísto instrukce KSHORT používá instrukce KNUM, která se odkazuje do tabulky konstant:

-- BYTECODE -- test03.lua:0-16
0001    KPRI     0   0   ; do slotu číslo 0 uložit hodnotu nil
0002    KSHORT   1   0   ; do slotu číslo 1 uložit hodnotu 0
0003    KSHORT   2  42   ; do slotu číslo 2 uložit hodnotu 0
0004    KSHORT   3 1764  ; do slotu číslo 3 uložit hodnotu 42×42=1764
0005    KNUM     4   0   ; do slotu číslo 4 uložit hodnotu 42×42×42=74088 z tabulky konstant
0006    KNUM     5   1   ; do slotu číslo 4 uložit hodnotu 42×42×42×42=3111696 z tabulky konstant
0007    RET0     0   1   ; návrat z programu

8. Demonstrační příklad číslo 4: volání (builtin) funkce

Ve čtvrtém příkladu je ukázán způsob volání funkce, a to konkrétně funkce print() bez parametrů. Samotný zdrojový kód tohoto demonstračního příkladu je primitivní:

--
-- LuaJIT: demonstrační příklad číslo 4
--
-- Volání funkce.
--
 
 
 
-- volání funkce
print()
 
 
 
-- finito

V IR čtvrtého demonstračního příkladu můžeme vidět dvě instrukce, o nichž jsme se zmínili ve čtvrté kapitole. Jedná se o instrukci GGET, která přečte z globální tabulky _G[] referenci na funkci print() a uloží ji do zvoleného slotu (zde slotu číslo 0). Následně je použita instrukce CALL, která zavolá funkci, jejíž reference je uložena do slotu číslo 0. Operand B má hodnotu 1 a operand C má taktéž hodnotu 1. Tyto hodnoty znamenají: počet parametrů volané funkce = (C-A)-1 = 0, počet návratových hodnot volané funkce = (B-A)-1 = 0:

-- BYTECODE -- test04.lua:0-11
0001    GGET     0   0      ; získání reference na funkci se jménem  "print"
0002    CALL     0   1   1  ; volání funkce print()
 
0003    RET0     0   1      ; návrat z programu

9. Demonstrační příklad číslo 5: volání funkce s předáním parametru

Syntézou předchozích dvou demonstračních příkladů vznikl poslední dnes uváděný demonstrační příklad, v němž je nejprve inicializováno šest proměnných a následně jsou tyto proměnné předány do volané funkce print():

--
-- LuaJIT: demonstrační příklad číslo 5
--
-- Volání funkce s předáním parametru.
--
 
 
 
-- inicializace proměnných
local a = nil
local b = 0
local c = 42
local d = 42*42
local e = 42*42*42
local f = 42*42*42*42
 
-- volání funkci s použitím různých parametru
print(a)
print(b)
print(c)
print(d)
print(e)
print(f,a)
 
 
 
-- finito

Překladem pátého demonstračního příkladu do IR se opět dozvíme novou informaci o vlastnostech LuaJITu. Tentokrát se setkáme s instrukcí MOV, která zde poslouží k přípravě parametrů volané funkce print(), protože parametry musí být umístěny do slotu/slotů umístěných ihned za slotem obsahujícím referenci volané funkce:

-- BYTECODE -- test05.lua:0-23
0001    KPRI     0   0   ; do slotu číslo 0 uložit hodnotu nil
0002    KSHORT   1   0   ; do slotu číslo 1 uložit hodnotu 0
0003    KSHORT   2  42   ; do slotu číslo 2 uložit hodnotu 0
0004    KSHORT   3 1764  ; do slotu číslo 3 uložit hodnotu 42×42=1764
0005    KNUM     4   0   ; do slotu číslo 4 uložit hodnotu 42×42×42=74088 z tabulky konstant
0006    KNUM     5   1   ; do slotu číslo 4 uložit hodnotu 42×42×42×42=3111696 z tabulky konstant
 
0007    GGET     6   0      ; získání reference na funkci se jménem  "print", uložení do slotu 6
0008    MOV      7   0      ; jediným parametrem funkce je hodnota proměnné "a" (slot 0)
0009    CALL     6   1   2  ; volání funkce print()
 
0010    GGET     6   0      ; získání reference na funkci se jménem  "print", uložení do slotu 6
0011    MOV      7   1      ; jediným parametrem funkce je hodnota proměnné "b" (slot 1)
0012    CALL     6   1   2  ; volání funkce print()
 
0013    GGET     6   0      ; získání reference na funkci se jménem  "print", uložení do slotu 6
0014    MOV      7   2      ; jediným parametrem funkce je hodnota proměnné "c" (slot 2)
0015    CALL     6   1   2  ; volání funkce print()
 
0016    GGET     6   0      ; získání reference na funkci se jménem  "print", uložení do slotu 6
0017    MOV      7   3      ; jediným parametrem funkce je hodnota proměnné "d" (slot 3)
0018    CALL     6   1   2  ; volání funkce print()
 
0019    GGET     6   0      ; získání reference na funkci se jménem  "print", uložení do slotu 6
0020    MOV      7   4      ; jediným parametrem funkce je hodnota proměnné "e" (slot 4)
0021    CALL     6   1   2  ; volání funkce print()
 
0022    GGET     6   0      ; získání reference na funkci se jménem  "print", uložení do slotu 6
0023    MOV      7   5      ; prvním parametrem funkce je hodnota proměnné "f" (slot 5)
0024    MOV      8   0      ; druhým parametrem funkce je hodnota proměnné "a" (slot 0)
0025    CALL     6   1   3  ; volání funkce print()
 
0026    RET0     0   1      ; návrat z programu

10. Obsah následující části seriálu

V následující části tohoto seriálu si popíšeme způsob překladu aritmetických a logických výrazů do mezijazyka LuaJITu. Kromě toho se taktéž budeme zabývat instrukcemi IR, které slouží pro implementaci podmínek a skoků. Tyto instrukce jsou použity jak při větvení (programové konstrukce typu if-then, if-then-else atd.), tak i při překladu programových smyček (for, while a relativně málo používané smyčky typu repeat-until).

11. Repositář se zdrojovými kódy dnešních pěti demonstračních příkladů

Všech pět dnes popsaných a taktéž „disasemblovaných“ demonstračních příkladů bylo uloženo do Git repositáře umístěného na adrese https://github.com/tisnik/luajit-examples. Odkazy na prozatím poslední verze těchto pěti příkladů naleznete v tabulce umístěné pod tímto odstavcem:

12. Odkazy na Internetu

1. Wikipedia: Mezijazyk
   http://cs.wikipedia.org/wi­ki/Mezijazyk
2. The LuaJIT Project
   http://luajit.org/index.html
3. LuaJIT FAQ
   http://luajit.org/faq.html
4. LuaJIT Performance Comparison
   http://luajit.org/performance.html
5. LuaJIT 2.0 intellectual property disclosure and research opportunities
   http://article.gmane.org/gma­ne.comp.lang.lua.general/58908
6. LuaJIT Wiki
   http://wiki.luajit.org/Home
7. LuaJIT 2.0 Bytecode Instructions
   http://wiki.luajit.org/Bytecode-2.0
8. Programming in Lua 9.1 – Coroutine Basics,
   http://www.lua.org/pil/9.1.html
9. Programming in Lua (first edition)
   http://www.lua.org/pil/contents.html
10. Programming in Lua: 6 – More about Functions
    http://www.lua.org/pil/6.html
11. Lua Lanes,
    http://kotisivu.dnainternet­.net/askok/bin/lanes/
12. Programming in Lua: 6.1 – Closures
    http://www.lua.org/pil/6.1.html
13. Programming in Lua: 9.1 – Coroutine Basics
    http://www.lua.org/pil/9.1.html
14. Programming in Lua: Numeric for
    http://www.lua.org/pil/4.3.4.html
15. Programming in Lua: break and return
    http://www.lua.org/pil/4.4.html
16. Programming in Lua: Tables
    http://www.lua.org/pil/2.5.html
17. Programming in Lua: Table Constructors
    http://www.lua.org/pil/3.6.html
18. Programovací jazyk Lua
    http://palmknihy.cz/web/kni­ha/programovaci-jazyk-lua-12651.htm
19. Lua: Tables Tutorial
    http://lua-users.org/wiki/TablesTutorial
20. Lua: Control Structure Tutorial
    http://lua-users.org/wiki/ControlStruc­tureTutorial
21. Lua Types Tutorial
    http://lua-users.org/wiki/LuaTypesTutorial
22. Goto Statement in Lua
    http://lua-users.org/wiki/GotoStatement
23. Lua 5.2 sources
    http://www.lua.org/source/5.2/
24. Lua 5.2 sources – lopcodes.h
    http://www.lua.org/source/5­.2/lopcodes.h.html
25. Lua 5.2 sources – lopcodes.c
    http://www.lua.org/source/5­.2/lopcodes.c.html
26. Lambda the Ultimate: Coroutines in Lua,
    http://lambda-the-ultimate.org/node/438
27. Coroutines Tutorial,
    http://lua-users.org/wiki/CoroutinesTutorial
28. Lua Coroutines Versus Python Generators,
    http://lua-users.org/wiki/LuaCorouti­nesVersusPythonGenerators