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

Obsah

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

   1.1 Základní aritmetické instrukce

   1.2 Instrukce pro podmíněné a nepodmíněné skoky

   1.3 Instrukce počítané programové smyčky for

2. Demonstrační příklad číslo 6: překlad jednoduchých aritmetických výrazů

3. Demonstrační příklad číslo 7: překlad složitějších aritmetických výrazů

4. Demonstrační příklad číslo 8: rozhodovací konstrukce if-then

5. Demonstrační příklad číslo 9: rozhodovací konstrukce if-then-else

6. Demonstrační příklad číslo 10: rozhodovací konstrukce if-then-elseif-else

7. Demonstrační příklad číslo 11: počítaná programová smyčka typu for

8. Demonstrační příklad číslo 12: složitější počítaná programová smyčka typu for

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

10. Odkazy na Internetu

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

V první části článku o Just in Time překladači LuaJIT jsme si mj. popsali i několik základních instrukcí použitých v mezijazyku (IR – Intermediate Representation). Připomeňme si, že každý program napsaný v Lue je nejprve překompilován do tohoto mezijazyka a teprve poté může být přeložen do nativního strojového kódu. Dnes si popíšeme další instrukce, které jsou v IR použity. Instrukční soubor IR lze považovat za reprezentaci ekvivalentní bajtkódům používaným v JVM, Lua VM či Python VM, ovšem jak uvidíme dále, je IR LuaJITu v některých ohledech velmi elegantní a lépe připraven pro překlad do nativního kódu než například zásobníkově orientovaný bajtkód JVM.

1.1 Základní aritmetické instrukce

V IR LuaJITu se nachází poměrně velké množství aritmetických instrukcí, přičemž všechny instrukce využívají takzvaný tříadresový kód. To znamená, že se v instrukci nachází jak adresy či indexy dvou zdrojových operandů, tak i adresa/index operandu cílového. Díky tomu se i poměrně složité aritmetické výrazy daří překládat do velmi krátké sekvence instrukcí, na rozdíl od zásobníkově orientovaného bajtkódu, který sice bude obsahovat instrukce s menší bitovou šířkou, ale manipulací s operandy bude prováděno větší množství. Následující pětice instrukcí slouží k provedení základních aritmetických operací nad operandy uloženými ve slotech (pro práci s konstantami se používají odlišné instrukce):

1.2 Instrukce pro podmíněné a nepodmíněné skoky

Následují instrukce pro podmíněné a nepodmíněné skoky. Instrukcí pro podmíněné skoky taktéž existuje velké množství; my se však dnes seznámíme jen s šesti instrukcemi, které porovnají dva operandy uložené ve slotech. Jedná se o instrukce ISLT, ISGE, ISLE, ISGT, ISEQV a ISNEV. Na těchto instrukcích je zvláštní fakt, že pouze provedou test na splnění či nesplnění dané podmínky, ovšem skok musí být proveden až instrukcí JMP. Pokud je před JMP uvedena některá z instrukcí I*, jedná se o podmíněný skok provedený pouze ve chvíli, kdy je podmínka splněna. Pokud se však před instrukcí skoku JMP nachází jiná instrukce, jde o skok nepodmíněný. Toto řešení je velmi zajímavé a v určitém ohledu připomíná instrukční sadu mikroprocesorů ARM:

1.3 Instrukce počítané programové smyčky for

Poslední dvě dnes popsané instrukce slouží pro implementaci počítané programové smyčky typu for. Jedná se o instrukce nazvané FORI a FORL. První z těchto instrukcí se používá na začátku smyčky (před jejím tělem), druhá instrukce se používá vždy jako poslední instrukce v těle smyčky for. V obou případech se testuje podmínka na ukončení smyčky, což je opět zajímavé, protože u jiných VM/bajtkódů je typicky podmínka testována jen na začátku smyčky, kdežto na jejím konci je umístěn nepodmíněný skok (které řešení je elegantnější, je nasnadě):

2. Demonstrační příklad číslo 6: překlad jednoduchých aritmetických výrazů

V (celkově) šestém demonstračním příkladu si ukážeme, jak se do IR přeloží jednoduché aritmetické výrazy, konkrétně výrazy s jedinou operací a dvěma operandy:

--
-- LuaJIT: demonstrační příklad číslo 6
--
-- Jednoduché výrazy.
--
 
 
 
-- inicializace proměnných konstantami
local a = 1
local b = 2
 
-- inicializace proměnných s využitím aritmetických výrazů
local c = a + b
local d = a - b
local e = a * b
local f = a / b
local g = a % b
 
 
 
-- tisk hodnot všech proměnných
print(a)
print(b)
print(c)
print(d)
print(e)
print(f)
print(g)
 
 
 
-- finito

Samotný překlad aritmetických výrazů je velmi přímočarý, a to díky již zmíněnému tříadresovému kódu. Dále si povšimněte, že tisk hodnot s využitím funkce print() není žádným způsobem optimalizován a každé volání print(proměnná) je otrocky přeloženo do sekvence tří instrukcí:

-- BYTECODE -- test06.lua:0-24
0001    KSHORT   0   1       ; do slotu číslo 0 uložit hodnotu 1
0002    KSHORT   1   2       ; do slotu číslo 1 uložit hodnotu 2
 
0003    ADDVV    2   0   1   ; součet hodnot ve slotech 0 a 1, výsledek se ukládá do slotu 2
0004    SUBVV    3   0   1   ; rozdíl hodnot ve slotech 0 a 1, výsledek se ukládá do slotu 3
0005    MULVV    4   0   1   ; součin hodnot ve slotech 0 a 1, výsledek se ukládá do slotu 4
0006    DIVVV    5   0   1   ; podíl hodnot ve slotech 0 a 1, výsledek se ukládá do slotu 5
0007    MODVV    6   0   1   ; podíl modulo hodnot ve slotech 0 a 1, výsledek se ukládá do slotu 6
 
0008    GGET     7   0       ; získání reference na funkci se jménem "print"
0009    MOV      8   0       ; parametr pro funkci print se uloží do slotu číslo 8
0010    CALL     7   1   2   ; volání funkce print()
 
0011    GGET     7   0       ; získání reference na funkci se jménem "print"
0012    MOV      8   1       ; parametr pro funkci print se uloží do slotu číslo 8
0013    CALL     7   1   2   ; volání funkce print()
 
0014    GGET     7   0       ; získání reference na funkci se jménem "print"
0015    MOV      8   2       ; parametr pro funkci print se uloží do slotu číslo 8
0016    CALL     7   1   2   ; volání funkce print()
 
0017    GGET     7   0       ; získání reference na funkci se jménem "print"
0018    MOV      8   3       ; parametr pro funkci print se uloží do slotu číslo 8
0019    CALL     7   1   2   ; volání funkce print()
 
0020    GGET     7   0       ; získání reference na funkci se jménem "print"
0021    MOV      8   4       ; parametr pro funkci print se uloží do slotu číslo 8
0022    CALL     7   1   2   ; volání funkce print()
 
0023    GGET     7   0       ; získání reference na funkci se jménem "print"
0024    MOV      8   5       ; parametr pro funkci print se uloží do slotu číslo 8
0025    CALL     7   1   2   ; volání funkce print()
 
0026    GGET     7   0       ; získání reference na funkci se jménem "print"
0027    MOV      8   6       ; parametr pro funkci print se uloží do slotu číslo 8
0028    CALL     7   1   2   ; volání funkce print()
 
0029    RET0     0   1       ; návrat z programu

3. Demonstrační příklad číslo 7: překlad složitějších aritmetických výrazů

Nyní se podívejme na to, jak si LuaJIT poradí s překladem složitějších aritmetických výrazů, konkrétně výrazů se dvěma až třemi operacemi a tím pádem se třemi či čtyřmi operandy:

--
-- LuaJIT: demonstrační příklad číslo 7
--
-- Složitější aritmetické výrazy.
--
 
 
 
-- inicializace proměnných konstantami
local a = 1
local b = 2
local c = 3
 
-- inicializace proměnných s využitím aritmetických výrazů
local x = a + b + c
local y = a - b * c
local z = a * (b + c)
local w = (a + b) * (b + c)
local q = (a % b) / (b % c)
 
 
 
-- tisk hodnot všech proměnných
print(a)
print(b)
print(c)
print(x)
print(y)
print(z)
print(w)
print(q)
 
 
 
-- finito

Překlad aritmetických výrazů je stále velmi jednoduchý, a to opět díky použití tříadresového kódu. Nejsložitější výraz w = (a + b) * (b + c) je přeložen do dvou instrukcí ADDVV s uložením mezivýsledků do slotů 6 a 7. Za těmito instrukcemi následuje instrukce MULVV, která oba mezivýsledky vynásobí:

-- BYTECODE -- test07.lua:0-37
0001    KSHORT   0   1       ; do slotu číslo 0 uložit hodnotu 1
0002    KSHORT   1   2       ; do slotu číslo 1 uložit hodnotu 2
0003    KSHORT   2   3       ; do slotu číslo 2 uložit hodnotu 3
 
0004    ADDVV    3   0   1
0005    ADDVV    3   3   2   ; x = a + b + c
 
0006    MULVV    4   1   2
0007    SUBVV    4   0   4   ; y = a - b * c
 
0008    ADDVV    5   1   2
0009    MULVV    5   0   5   ; z = a * (b + c)
 
0010    ADDVV    6   0   1
0011    ADDVV    7   1   2
0012    MULVV    6   6   7   ; w = (a + b) * (b + c)
 
0013    MODVV    7   0   1
0014    MODVV    8   1   2
0015    DIVVV    7   7   8   ; q = (a % b) / (b % c)
 
0016    GGET     8   0       ; získání reference na funkci se jménem "print"
0017    MOV      9   0       ; parametr pro funkci print se uloží do slotu číslo 9
0018    CALL     8   1   2   ; volání funkce print()
 
0019    GGET     8   0       ; získání reference na funkci se jménem "print"
0020    MOV      9   1       ; parametr pro funkci print se uloží do slotu číslo 9
0021    CALL     8   1   2   ; volání funkce print()
 
0022    GGET     8   0       ; získání reference na funkci se jménem "print"
0023    MOV      9   2       ; parametr pro funkci print se uloží do slotu číslo 9
0024    CALL     8   1   2   ; volání funkce print()
 
0025    GGET     8   0       ; získání reference na funkci se jménem "print"
0026    MOV      9   3       ; parametr pro funkci print se uloží do slotu číslo 9
0027    CALL     8   1   2   ; volání funkce print()
 
0028    GGET     8   0       ; získání reference na funkci se jménem "print"
0029    MOV      9   4       ; parametr pro funkci print se uloží do slotu číslo 9
0030    CALL     8   1   2   ; volání funkce print()
 
0031    GGET     8   0       ; získání reference na funkci se jménem "print"
0032    MOV      9   5       ; parametr pro funkci print se uloží do slotu číslo 9
0033    CALL     8   1   2   ; volání funkce print()
 
0034    GGET     8   0       ; získání reference na funkci se jménem "print"
0035    MOV      9   6       ; parametr pro funkci print se uloží do slotu číslo 9
0036    CALL     8   1   2   ; volání funkce print()
 
0037    GGET     8   0       ; získání reference na funkci se jménem "print"
0038    MOV      9   7       ; parametr pro funkci print se uloží do slotu číslo 9
0039    CALL     8   1   2   ; volání funkce print()
 
0040    RET0     0   1       ; návrat z programu

4. Demonstrační příklad číslo 8: rozhodovací konstrukce if-then

V celkově osmém demonstračním příkladu si ukážeme způsob překladu programové konstrukce if-then, tj. jednoduchého větvení. V podmínce se vyskytuje prosté porovnání hodnot dvou proměnných, tj. jedná se o jednu z nejjednodušších a pravděpodobně i nejpoužívanějších podmínek vůbec:

--
-- LuaJIT: demonstrační příklad číslo 8
--
-- Rozhodovací konstrukce if-then
--
 
 
 
-- inicializace proměnných konstantami
local a = 1
local b = 2
 
-- rozhodovací konstrukce if-then
if a > b then
    print("a > b")
end
 
 
 
-- finito

V IR tohoto demonstračního příkladu se poprvé setkáváme s instrukcí typu I*, za níž následuje instrukce skoku JMP. Pokud je podmínka splněna, dojde ke skoku a tím pádem i k přeskočení celého těla větve then:

-- BYTECODE -- test08.lua:0-22
0001    KSHORT   0   1        ; do slotu číslo 0 uložit hodnotu 1
0002    KSHORT   1   2        ; do slotu číslo 1 uložit hodnotu 2
 
0003    ISGE     1   0        ; porovnání hodnot ve slotech 1 a 0
0004    JMP      2 => 0008    ; podmíněný skok na adresu 0008
 
0005    GGET     2   0        ; získání reference na funkci se jménem "print"
0006    KSTR     3   1        ; řetězec "a >b", který se bude tisknout na obrazovku
0007    CALL     2   1   2    ; volání funkce print()
 
0008 => RET0     0   1        ; návrat z programu

Poznámka: instrukce KSTR získá referenci na konstantní řetězec, tato reference je následně použita při volání funkce print().

5. Demonstrační příklad číslo 9: rozhodovací konstrukce if-then-else

V dalším – již devátém – demonstračním příkladu se namísto jednoduchého větvení typu if-then používá úplné rozvětvení typu if-then-else, tj. na základě splnění či naopak nesplnění zadané podmínky se vykoná první či druhá větev programu:

--
-- LuaJIT: demonstrační příklad číslo 9
--
-- Rozhodovací konstrukce if-then-else
--
 
 
 
-- inicializace proměnných konstantami
local a = 1
local b = 2
 
-- rozhodovací konstrukce if-then-else
if a > b then
    print("a > b")
else
    print("a <= b")
end
 
 
 
-- finito

IR tohoto demonstračního příkladu je již velmi zajímavý, a to především proto, že se zde vyskytuje instrukce JMP, a to dokonce dvakrát. Poprvé zde najdeme dvojici ISGE+JMP sloužící k podmíněnému přeskočení větve then, podruhé je instrukce JMP použita ve větvi then k nepodmíněnému přeskočení větve else. Bajtkód je však stále velmi dobře čitelný a samotná rozhodovací konstrukce je vlastně vytvořena jen třemi instrukcemi:

-- BYTECODE -- test09.lua:0-24
0001    KSHORT   0   1        ; do slotu číslo 0 uložit hodnotu 1
0002    KSHORT   1   2        ; do slotu číslo 1 uložit hodnotu 2
 
0003    ISGE     1   0        ; porovnání hodnot ve slotech 0 a 1
0004    JMP      2 => 0009    ; podmíněný skok na adresu 0009
 
0005    GGET     2   0        ; získání reference na funkci se jménem "print"
0006    KSTR     3   1        ; řetězec "a > b"
0007    CALL     2   1   2    ; volání funkce print()
0008    JMP      2 => 0012    ; nepodmíněný skok na adresu 0012
 
0009 => GGET     2   0        ; získání reference na funkci se jménem "print"
0010    KSTR     3   2        ; řetězec "a <= b"
0011    CALL     2   1   2    ; volání funkce print()
 
0012 => RET0     0   1        ; návrat z programu

6. Demonstrační příklad číslo 10: rozhodovací konstrukce if-then-elseif-else

Zkusme si nyní předchozí dva příklady udělat ještě složitější a to konkrétně použitím úplné rozhodovací konstrukce typu if-then-elseif-else. V takto vytvořeném větvení se již nachází dvě podmínky a překladač LuaJITu bude mít při překladu zdrojového kódu do IR ještě více zábavy :-)

--
-- LuaJIT: demonstrační příklad číslo 10
--
-- Rozhodovací konstrukce if-then-elseif--else
--
 
 
 
-- inicializace proměnných konstantami
local a = 1
local b = 2
 
-- rozhodovací konstrukce if-then-else
if a > b then
    print("a > b")
elseif a < b then
    print("a < b")
else
    print("a == b")
end
 
 
 
-- finito

V IR tohoto demonstračního příkladu můžeme nalézt jednu zajímavost – pro překlad obou opačných podmínek je použita táž dvojice instrukcí ISGE + JMP, ovšem operandy jsou ve druhém případu přehozeny. Ostatní části IR se do značné míry podobají nám již známému kódu, včetně použití samostatné instrukce JMP pro nepodmíněné přeskočení větví elseif i else:

-- BYTECODE -- test10.lua:0-26
0001    KSHORT   0   1        ; do slotu číslo 0 uložit hodnotu 1
0002    KSHORT   1   2        ; do slotu číslo 1 uložit hodnotu 2
 
0003    ISGE     1   0        ; porovnání hodnot ve slotech 0 a 1
0004    JMP      2 => 0009    ; podmíněný skok na adresu 0009
 
0005    GGET     2   0        ; získání reference na funkci se jménem "print"
0006    KSTR     3   1        ; řetězec "a > b"
0007    CALL     2   1   2    ; volání funkce print()
0008    JMP      2 => 0018    ; nepodmíněný skok na adresu 0018
 
0009 => ISGE     0   1        ; opačné porovnání hodnot ve slotech 0 a 1
0010    JMP      2 => 0015    ; podmíněný skok na adresu 0015
 
0011    GGET     2   0        ; získání reference na funkci se jménem "print"
0012    KSTR     3   2        ; řetězec "a < b"
0013    CALL     2   1   2    ; volání funkce print()
0014    JMP      2 => 0018    ; nepodmíněný skok na adresu 0018
 
0015 => GGET     2   00       ; získání reference na funkci se jménem "print"
0016    KSTR     3   3        ; řetězec "a == b"
0017    CALL     2   1   2    ; volání funkce print()
 
0018 => RET0     0   1        ; návrat z programu

7. Demonstrační příklad číslo 11: počítaná programová smyčka typu for

V dalším demonstračním příkladu je implementována počítaná programová smyčka typu for, zde ve velmi jednoduché formě, kdy se postupně čítají hodnoty od 1 do 10 s krokem automaticky nastaveným na jedničku:

--
-- LuaJIT: demonstrační příklad číslo 11
--
-- Počítaná programová smyčka for.
--
 
 
 
-- počítaná programová smyčka for
for i = 1,10 do
    print(i)
end
 
 
 
-- finito

V přeloženém IR můžeme vidět použití dvojice instrukcí FORI a FORL. Instrukce FORI je skutečně použita na začátku programové smyčky, ještě před jejím tělem, a to pro zjištění, zda již před vstupem do smyčky náhodou nedošlo k situaci typu for i = 10,9 atd. Naopak instrukce FORL na konci smyčky provádí mnoho operací – zvýšení hodnoty počitadla, test na ukončení smyčky a současně i podmíněný skok na začátek smyčky. Jak FORI tak i FORL pracuje se třemi sloty – počitadlem, koncovou hodnotou a krokem:

-- BYTECODE -- test11.lua:0-18
0001    KSHORT   0   1        ; do slotu číslo 0 uložit hodnotu 1 (počáteční hodnota počitadla)
0002    KSHORT   1  10        ; do slotu číslo 1 uložit hodnotu 10 (koncová hodnota počitadla)
0003    KSHORT   2   1        ; do slotu číslo 2 uložit hodnotu 1 (krok)
 
0004    FORI     0 => 0009    ; vstup do počítané programové smyčky typu for, první instrukce za smyčkou je na adrese 0009
 
0005 => GGET     4   0        ; získání reference na funkci se jménem "print"
0006    MOV      5   3        ; parametr použitý při volání funkce print()
0007    CALL     4   1   2    ; volání funkce print()
0008    FORL     0 => 0005    ; další iterace, tělo smyčky začíná na adrese 0005
 
0009 => RET0     0   1        ; návrat z programu

8. Demonstrační příklad číslo 12: složitější počítaná programová smyčka typu for

Zkusme nyní vytvořit počítanou programovou smyčku typu for, v níž se hodnota počitadla naopak snižuje, a to s krokem 1. Pro tento typ smyčky v jazyce Lua existuje jednoduchý zápis for i = začátek,konec,záporný_krok do:

--
-- LuaJIT: demonstrační příklad číslo 12
--
-- Počítaná programová smyčka for.
--
 
 
 
-- počítaná programová smyčka for
for i = 10,1,-1 do
    print(i)
end
 
 
 
-- finito

Tato programová smyčka se přeloží naprosto stejným způsobem jako smyčka implementovaná v předchozím demonstračním příkladu. Tento příklad jsme si uváděli zejména z toho důvodu, že v jiných VM (a taktéž v mnoha instrukčních sadách reálných mikroprocesorů) se v některých příkladech programové smyčky s kladným krokem rovným jedné dokáží přeložit efektivnějším způsobem. V LuaJITu tomu tak však není a všechny počítané smyčky for jsou si z tohoto hlediska rovnocenné:

-- BYTECODE -- test12.lua:0-18
0001    KSHORT   0  10        ; do slotu číslo 0 uložit hodnotu 10 (počáteční hodnota počitadla)
0002    KSHORT   1   1        ; do slotu číslo 1 uložit hodnotu 1 (koncová hodnota počitadla)
0003    KSHORT   2  -1        ; do slotu číslo 2 uložit hodnotu -1 (krok)
 
0004    FORI     0 => 0009    ; vstup do počítané programové smyčky typu for, první instrukce za smyčkou je na adrese 0009
 
0005 => GGET     4   0        ; získání reference na funkci se jménem "print"
0006    MOV      5   3        ; parametr použitý při volání funkce print()
0007    CALL     4   1   2    ; volání funkce print()
0008    FORL     0 => 0005    ; další iterace, tělo smyčky začíná na adrese 0005
 
0009 => RET0     0   1        ; návrat z programu

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

Všechny dnes popsané a taktéž „disasemblované“ demonstrační příklady byly uloženy 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říkladů naleznete v tabulce umístěné pod tímto odstavcem:

10. 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