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

Pavel Tišnovský 14. 10. 2014

Pro doplnění informací, které jsme si doposud v seriálu o jazyce Java (JVM) uvedli, si v několika článcích popíšeme velmi zajímavý projekt LuaJIT. Již z názvu tohoto projektu je zřejmé, že se jedná o „konkurenční “Just in Time překladač, který je možné použít společně s programovacím jazykem 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 ZeroShark). 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í:

Označení Šířka (bitů) Popis
B 8 první vstupní operand (zdrojová proměnná)
C 8 druhý vstupní operand (zdrojová proměnná, numerická konstanta atd.)
A 8 výsledek operace (proměnná pro uložení výsledku)
OP 8 operační kód instrukce
Celkem 32  

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):

Označení Šířka (bitů) Popis
D 16 vstupní operand (zdrojová proměnná)
A 8 první operand nebo proměnná pro uložení výsledku
OP 8 operační kód instrukce
Celkem 32  

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é):

Instrukce Operand A Operand D Popis
KNIL base base nastaví sloty číslo A až D na hodnotu nil
KPRI dest pri nastaví dest na hodnotu specifikovanou v D
KSHORT dest const přenese do dest šestnáctibitovou celočíselnou konstantu
KNUM dest number přenese do dest zvolenou numerickou konstantu

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

base číslo, hodnota pouze pro čtení
dest číslo slotu, použito pro specifikaci cíle
number index do tabulky konstant (lze považovat za zjednodušenou obdobu constant poolu)

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:

Instrukce Operand A Operand D Popis
MOV dest var kopie dat z D do A

Mnohem komplikovanější jsou instrukce nazvané RET0CALL. 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ů:

Instrukce Operand A Operand B Operandy C/D Popis
RET0 rbase lit   návrat z funkce
CALL base lit lit volání funkce
reference na funkci je v A
parametry A+1, A+2, … A+C-1
návratové hodnoty A, A+1, … A+B-2

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:

Instrukce Operand A Operand B Operandy C/D Popis
GGET var × str tzv. „global get“, A=_G[D]

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, cd. 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:

widgety

-- 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
Našli jste v článku chybu?
DigiZone.cz: Sony MP-CL1A: miniaturní projektor

Sony MP-CL1A: miniaturní projektor

DigiZone.cz: DVB-T2 ověřeno: ČRa doplňují seznam

DVB-T2 ověřeno: ČRa doplňují seznam

DigiZone.cz: Nova opět stahuje „milionáře“

Nova opět stahuje „milionáře“

Lupa.cz: Patička e-mailu závazná jako vlastnoruční podpis?

Patička e-mailu závazná jako vlastnoruční podpis?

Podnikatel.cz: Poslanci chtějí sebrat majetek Bakalovi

Poslanci chtějí sebrat majetek Bakalovi

Lupa.cz: Hackeři mají data z půlmiliardy účtů Yahoo

Hackeři mají data z půlmiliardy účtů Yahoo

DigiZone.cz: Rapl: seriál, který vás smíří s ČT

Rapl: seriál, který vás smíří s ČT

Podnikatel.cz: Byla finanční manažerka, teď cvičí jógu

Byla finanční manažerka, teď cvičí jógu

Vitalia.cz: Tohle jsou nejlepší česká piva podle odborníků

Tohle jsou nejlepší česká piva podle odborníků

Lupa.cz: Jak levné procesory změnily svět?

Jak levné procesory změnily svět?

Podnikatel.cz: Babišovi se nedá věřit, stěžovali si hospodští

Babišovi se nedá věřit, stěžovali si hospodští

DigiZone.cz: DVB-T2 ověřeno: seznam TV zveřejněn

DVB-T2 ověřeno: seznam TV zveřejněn

Vitalia.cz: Tahák, jak vyzrát nad zápachem z úst

Tahák, jak vyzrát nad zápachem z úst

DigiZone.cz: Digi Slovakia zařazuje stanice SPI

Digi Slovakia zařazuje stanice SPI

DigiZone.cz: Samsung EVO-S: novinka pro Skylink

Samsung EVO-S: novinka pro Skylink

Vitalia.cz: Voda z Vltavy před a po úpravě na pitnou

Voda z Vltavy před a po úpravě na pitnou

Vitalia.cz: Jsou vegani a vyrábějí nemléko

Jsou vegani a vyrábějí nemléko

DigiZone.cz: Funbox 4K v DVB-T2 má ostrý provoz

Funbox 4K v DVB-T2 má ostrý provoz

Podnikatel.cz: Takhle se prodávají mražené potraviny

Takhle se prodávají mražené potraviny

Lupa.cz: Cimrman má hry na YouTube i vlastní doodle

Cimrman má hry na YouTube i vlastní doodle