Pohled pod kapotu formátu WebAssembly: instrukce pro řízení toku dat

Obsah

1. Pohled pod kapotu formátu WebAssembly: instrukce pro řízení toku dat

2. Instrukce select

3. Příklad využití instrukce select

4. Překlad ternárního operátoru, ve kterém se nevyskytují pouze konstanty

5. Koncept bloků ve WebAssembly

6. Instrukce br a br_if

7. Překlad ternárního operátoru s využitím instrukce br_if

8. Instrukce WebAssembly určená pro realizaci programových smyček

9. Nekonečná programová smyčka

10. Příklady překladu počítaných programových smyček

11. Výpočty vykonávané uvnitř počítané programové smyčky

12. Vnořené počítané programové smyčky

13. Překlad zdrojových kódů, ve kterých se používá konstrukce goto

14. Instrukce br_table

15. Rozeskok realizovaný konstrukcí switch-case

16. Rozeskok s větví default

17. Podrobnější pohled na přeloženou funkci pro výpočet největšího společného dělitele

18. Obsah navazujícího článku

19. Tabulka se všemi doposud popsanými instrukcemi

20. Odkazy na Internetu

1. Pohled pod kapotu formátu WebAssembly: instrukce pro řízení toku dat

Ve třetím článku o formátu WebAssembly se zaměříme na popis instrukcí, které slouží pro řízení toku dat (control-flow). Tyto instrukce jsou použity při překladu zdrojových kódů, v nichž se vyskytuje běžné rozvětvení (if-else), vícenásobné rozvětvení (switch-case), různé varianty programových smyček (počítané i nepočítané), ale i některé výrazy s ternárními operátory (pochopitelně pouze v těch programovacích jazycích, které ternární operátory podporují). Na první pohled by se mohlo zdát, že techniky pro realizaci řízení toku dat jsou ve většině virtuálních strojů totožné, ale zrovna WebAssembly se od ostatních technologií v mnoha ohledech odlišuje, protože se namísto nepodmíněných a podmíněných skoků používají programové bloky definované již na úrovni bajtkóodu a namísto skutečných skoků se používají spíše instrukce typu „break“ a „continue“ (i když se tak nejmenují).

clang -Os --target=wasm32 -emit-llvm -c -S ${1}.c
llc -march=wasm32 -filetype=obj ${1}.ll -o ${1}.wasm
wasm-objdump -d ${1}.wasm

2. Instrukce select

S instrukcí nazvanou select jsme se již částečně seznámili v předchozím článku, takže jen krátce pro připomenutí:

Tato instrukce se typicky používá pro překlad výrazu s céčkovským ternárním operátorem ?:, tedy například tohoto výrazu:

podmínka ? první_podvýraz : druhý_podvýraz

Ovšem je nutné si uvědomit, že instrukce select vybírá ze zásobníku již předem vypočtené hodnoty, neprovádí tedy žádný rozeskok. To ovšem znamená, že v předchozím případě budou muset být oba podvýrazy první_podvýraz i druhý_podvýraz nejdříve vyhodnoceny – není zde realizováno takzvané zkrácené vyhodnocování (short-circuit). To ovšem znamená, že použití instrukce select je omezeno a zdaleka na všechny výrazy s ternárním operátorem budou přeloženy tak, aby tuto instrukci použily (což si ostatně ukážeme v dalších kapitolách).

3. Příklad využití instrukce select

Vyzkoušejme si, jestli Clang (resp. tomto případě backend překladač v LLVM) instrukci select dokáže využít. Pokusíme se přeložit následující jednoduchou céčkovou funkci s ternárním výrazem, který vrací jednu z konstant:

int foo(int x) {
    return x < 10 ? 1 : 2;
}

Z výsledného bajtkódu je zřejmé, že se instrukce select skutečně použila:

condition_1.wasm:       file format wasm 0x1
 
Code Disassembly:
 
000042 func[0] <foo>:
 000043: 41 01                      | i32.const 1
 000045: 41 02                      | i32.const 2
 000047: 20 00                      | local.get 0
 000049: 41 0a                      | i32.const 10
 00004b: 48                         | i32.lt_s
 00004c: 1b                         | select
 00004d: 0b                         | end

Nejdříve se na zásobník uložily obě konstanty, z nichž jedna se bude vracet (a druhá se zahodí):

 000043: 41 01                      | i32.const 1
 000045: 41 02                      | i32.const 2

Následně se vyhodnotila podmínka a na zásobníku zůstala její výsledná hodnota true nebo false:

 000049: 41 0a                      | i32.const 10
 00004b: 48                         | i32.lt_s

A následovala instrukce select, která na základě výsledku podmínky ponechá na zásobníku první nebo druhou konstantu:

 00004c: 1b                         | select

4. Překlad ternárního operátoru, ve kterém se nevyskytují pouze konstanty

Jak ovšem bude vypadat překlad výrazu s ternárním operátorem, ve kterém se nevyskytují pouze konstantní výrazy. Opět si to můžeme ověřit na jednoduchém příkladu:

int foo(int x) {
    return x < 10 ? x+1 : x*3;
}

Překlad do bajtkódu WebAssembly proběhne takto (resp. tak může proběhnout):

condition_2.wasm:       file format wasm 0x1
 
Code Disassembly:
 
000042 func[0] <foo>:
 000043: 20 00                      | local.get 0
 000045: 41 01                      | i32.const 1
 000047: 6a                         | i32.add
 000048: 20 00                      | local.get 0
 00004a: 41 03                      | i32.const 3
 00004c: 6c                         | i32.mul
 00004d: 20 00                      | local.get 0
 00004f: 41 0a                      | i32.const 10
 000051: 48                         | i32.lt_s
 000052: 1b                         | select
 000053: 0b                         | end

Toto je ovšem zajímavé, protože se ve skutečnosti vyhodnotily oba podvýrazy – jeden ovšem zbytečně. Vyhodnocení prvního podvýrazu s uložením výsledku na zásobník:

 000043: 20 00                      | local.get 0
 000045: 41 01                      | i32.const 1
 000047: 6a                         | i32.add

Vyhodnocení podvýrazu druhého, opět s uložením výsledku na zásobník:

 000048: 20 00                      | local.get 0
 00004a: 41 03                      | i32.const 3
 00004c: 6c                         | i32.mul

Výběr jednoho z výsledků na základě vyhodnocené podmínky:

 00004d: 20 00                      | local.get 0
 00004f: 41 0a                      | i32.const 10
 000051: 48                         | i32.lt_s
 000052: 1b                         | select

Prakticky stejně dopadneme při překladu programu, který pracuje s hodnotami s plovoucí řádovou čárkou:

float foo(float x) {
    return x < 10 ? x+1 : x*3;
}

Výsledek překladu do WebAssembly:

condition_3.wasm:       file format wasm 0x1
 
Code Disassembly:
 
000042 func[0] <foo>:
 000043: 20 00                      | local.get 0
 000045: 43 00 00 80 3f             | f32.const 0x1p+0
 00004a: 92                         | f32.add
 00004b: 20 00                      | local.get 0
 00004d: 43 00 00 40 40             | f32.const 0x1.8p+1
 000052: 94                         | f32.mul
 000053: 20 00                      | local.get 0
 000055: 43 00 00 20 41             | f32.const 0x1.4p+3
 00005a: 5d                         | f32.lt
 00005b: 1b                         | select
 00005c: 0b                         | end

5. Koncept bloků ve WebAssembly

Bajtkód WebAssembly je v mnoha ohledech podobný dalším typům bajtkódů, zejména těch, které jsou založeny na výpočtech s hodnotami uloženými na zásobníku operandů (operand stack). Ovšem realizace skoků a rozeskoků je ve WebAssembly poněkud odlišná. V dalších bajtkódech najdeme instrukce určené pro skok na určitou adresu, ať již absolutní nebo relativní, zatímco WebAssembly je založena na konceptu takzvaných bloků. Základ tohoto konceptu tvoří dvojice instrukcí nazvaných block a end, které určují začátek a konec bloku. Při vykonávání těchto instrukcí se na takzvaný zásobník řízení toku (control-flow stack) ukládají nebo naopak odstraňují návěští (label):

Dále existují instrukce, které dokážou provést podmíněný nebo nepodmíněný skok na začátek nebo na konec bloku. U těchto instrukcí je navíc možné zvolit, začátek či konec kterého bloku bude použit – bloky totiž mohou být vnořeny a bajtkód musí nabízet instrukce pro výskok z několika vnořených bloků atd.

6. Instrukce br a br_if

Nyní již máme k dispozici všechny důležité informace potřebné pro popis instrukcí br a br_if. Jedná se o instrukce nepodmíněného resp. ve druhém případě podmíněného skoku, což je patrné z mnemotechnických zkratek těchto instrukcí, které znamenají „branch“ a „branch if“:

Instrukce br_if očekává, že se na vrcholu zásobníku operandů nachází hodnota libovolného typu. Pokud je tato hodnota nenulová (což odpovídá true), provede se skok. Pokud je hodnota nulová, pokračuje se další instrukcí. Instrukce br provede skok vždy, bez ohledu na obsah zásobníku operandů. Nyní je ovšem důležité vysvětlit, co vlastně znamená sousloví „provede se skok“. Pracuje se zde se zásobníkem řízení toku (control-flow stack), ze kterého se přečte TOP-n tá položka. Typicky se setkáme s instrukcí br_if 0, která pracuje s nejvyšší položkou na zásobníku. Na základě přečtené položky se hledá konec příslušného bloku a skok je proveden za tento konec (samozřejmě se v praxi adresy konců bloků mohou předpočítat dopředu).

7. Překlad ternárního operátoru s využitím instrukce br_if

Instrukce br_if musí být použita například v případě, že se ve výrazu s ternárním operátorem volají nějaké funkce popř. jsou zde zapsány podvýrazy, které mění obsah proměnné (++, –). V takových případech již není možné vypočítat hodnoty podvýrazů v obou větvích a poté pouze instrukcí SELECT vybrat jeden z výsledků, ale musí se použít skutečný podmíněný skok.

Ukažme si tento koncept na jednoduchém programu, který ve funkci foo provádí rozvětvení na základě zapsané podmínky, která je vhodně nastavena tak, aby ji překladač nemohl vyhodnotit již v době překladu:

int bar(int x);
int baz(int x);
 
int foo(int x) {
    return x < 42 ? bar(x) : baz(x);
}

Překlad tohoto programu do bajtkódu WebAssembly bude vypadat následovně:

condition_4.wasm:       file format wasm 0x1
 
Code Disassembly:
 
000056 func[2] <foo>:
 000057: 02 40                      | block
 000059: 20 00                      |   local.get 0
 00005b: 41 29                      |   i32.const 41
 00005d: 4a                         |   i32.gt_s
 00005e: 0d 00                      |   br_if 0
 000060: 20 00                      |   local.get 0
 000062: 10 80 80 80 80 00          |   call 0 <env.bar>
 000068: 0f                         |   return
 000069: 0b                         | end
 00006a: 20 00                      | local.get 0
 00006c: 10 81 80 80 80 00          | call 1 <env.baz>
 000072: 0b                         | end

V bajtkódu je definován samostatný blok. V rámci tohoto bloku je vypočtena podmínka a na základě jejího výsledku buď dojde k výskoku z tohoto bloku instrukcí br_if nebo se pokračuje v dalších instrukcích které zavolají funkci bar a následně se funkce ukončí. Při skoku (výskoku z bloku) se naopak zavolá funkce baz a opět dojde k ukončení funkce.

Pro zajímavost se podívejme, jak se bude bajtkód odlišovat v případě, že všechny výpočty budou používat hodnoty s plovoucí řádovou čárkou:

float bar(float x);
float baz(float x);
 
float foo(float x) {
    return x < 42 ? bar(x) : baz(x);
}

Výsledek překladu do bajtkódu WebAssembly ukazuje, že se vlastně pouze mění způsob výpočtu podmínky. Další instrukce zůstanou prakticky stejné:

condition_5.wasm:       file format wasm 0x1
 
Code Disassembly:
 
000056 func[2] <foo>:
 000057: 02 40                      | block
 000059: 20 00                      |   local.get 0
 00005b: 43 00 00 28 42             |   f32.const 0x1.5p+5
 000060: 5d                         |   f32.lt
 000061: 45                         |   i32.eqz
 000062: 0d 00                      |   br_if 0
 000064: 20 00                      |   local.get 0
 000066: 10 80 80 80 80 00          |   call 0 <env.bar>
 00006c: 0f                         |   return
 00006d: 0b                         | end
 00006e: 20 00                      | local.get 0
 000070: 10 81 80 80 80 00          | call 1 <env.baz>
 000076: 0b                         | end

8. Instrukce WebAssembly určená pro realizaci programových smyček

V klasických virtuálních strojích se většinou programové smyčky (jak počítané, tak i nepočítané) realizují nějakou formou podmíněného skoku. Podobně je tomu i v běžných instrukčních sadách. Instrukce podmíněného skoku v takových případech obsahuje absolutní nebo relativní adresu, na kterou bude skok proveden. Ovšem ve WebAssembly je tomu jinak. Už v předchozím textu jsme se setkali s konceptem bloků realizovaných instrukcemi block a end. Tyto instrukce jsou doplněny instrukcemi podmíněného a nepodmíněného skoku: br_if a br. Ovšem, jak již víme, tyto instrukce neobsahují adresy cíle skoku, ale „pouze“ relativní číslo bloku, z něhož má být výskok proveden.

Instrukce br a br_if tedy v takovém případě skáčou na (za) konec bloku, tedy za instrukci end. Ovšem ve WebAssembly nalezneme ještě jednu instrukci, která se jmenuje loop:

Tato instrukce se používá na stejném místě, jako již popsaná instrukce block, ovšem její sémantika je odlišná. Pokud se provede instrukce br nebo br_if, bude skok realizován nikoli za konec bloku (tedy za end), ale naopak za instrukci loop, tedy vlastně na začátek bloku loop-end.

Nekonečná smyčka by tedy mohla vypadat přibližně takto:

loop
  ...
  ...
  ...
  br 0
end

Naopak programová smyčka s testem na konci by mohla vypadat následovně:

loop
  ...
  ...
  ....
  br_if 0
end

9. Nekonečná programová smyčka

Základ konceptu smyček ve WebAssembly si ukážeme na příkladu, ve kterém je definována nekonečná smyčka, v níž se volá nějaká další funkce:

void foo(void);
 
void loop(void) {
    while (1) {
        foo();
    }
}

V bajtkódu můžeme vidět blok smyčky vytvořený dvojicí instrukcí loop a end. Uvnitř smyčky se pak nachází instrukce br 0, která provádí nepodmíněný skok na začátek smyčky, protože samotná instrukce loop ve skutečnosti není implementací smyčky, ale jen definice bloku:

loop_0.wasm:    file format wasm 0x1
 
Code Disassembly:
 
00004a func[1] <loop>:
 00004b: 03 40                      | loop
 00004d: 10 80 80 80 80 00          |   call 0 <env.foo>
 000053: 0c 00                      |   br 0
 000055: 0b                         | end
 000056: 0b                         | end

10. Příklady překladu počítaných programových smyček

V předchozí kapitole jsme si ukázali způsob překladu nekonečné smyčky, tj. smyčky, na jejímž konci se nachází instrukce br 0, která realizuje skok na její začátek. Ovšem v praxi se setkáme spíše se sofistikovanějšími programovými smyčkami, například se smyčkami s počitadlem. Příkladem může být klasická smyčka typu for v jazyku C:

int foo(void);
 
void loop(void) {
    int i;
    for (i=0; i<10; i++) {
        foo();
    }
}

Tato smyčka se do WebAssembly přeloží následujícím způsobem:

loop_1.wasm:    file format wasm 0x1
 
Code Disassembly:
 
00004e func[1] <loop>:
 00004f: 01 7f                      | local[0] type=i32
 000051: 41 0a                      | i32.const 10
 000053: 21 00                      | local.set 0
 000055: 03 40                      | loop
 000057: 10 80 80 80 80 00          |   call 0 <env.foo>
 00005d: 1a                         |   drop
 00005e: 20 00                      |   local.get 0
 000060: 41 7f                      |   i32.const 4294967295
 000062: 6a                         |   i32.add
 000063: 22 00                      |   local.tee 0
 000065: 0d 00                      |   br_if 0
 000067: 0b                         | end
 000068: 0b                         | end

Stále můžeme vidět prakticky stejný základ programové smyčky, nyní se ovšem skok zpět na začátek smyčky provádí instrukcí br_if v případě, že je splněna podmínka „na vrcholu zásobníku je nenulová hodnota“ (mimochodem, povšimněte si uložení hodnoty do lokální proměnné, ovšem s jejím zachováním na zásobníku instrukcí local.tee):

loop
  ...
  ...
  ...
  br_if 0
end

Vyzkoušejme si podobný zdrojový kód, ovšem nyní je aktuální hodnota počitadla smyčky předána do volané funkce foo:

int foo(int);
 
void loop(void) {
    int i;
    for (i=0; i<10; i++) {
        foo(i);
    }
}

Opět zde můžeme vidět základ celé programové smyčky realizovaný dvojicí instrukcí loop a end. Ty jsou doplněny podmíněným skokem na začátek smyčky instrukcí br_if. Čítání nyní musí být provedeno ve správném pořadí, protože skutečně pracujeme s hodnotou počitadla a funkce foo se musí volat ve správném pořadí:

loop_2.wasm:    file format wasm 0x1
 
Code Disassembly:
 
00004f func[1] <loop>:
 000050: 01 7f                      | local[1] type=i32
 000052: 41 00                      | i32.const 0
 000054: 21 00                      | local.set 0
 000056: 03 40                      | loop
 000058: 20 00                      |   local.get 0
 00005a: 10 80 80 80 80 00          |   call 0 <env.foo>
 000060: 1a                         |   drop
 000061: 20 00                      |   local.get 0
 000063: 41 01                      |   i32.const 1
 000065: 6a                         |   i32.add
 000066: 22 00                      |   local.tee 0
 000068: 41 0a                      |   i32.const 10
 00006a: 47                         |   i32.ne
 00006b: 0d 00                      |   br_if 0
 00006d: 0b                         | end
 00006e: 0b                         | end

11. Výpočty vykonávané uvnitř počítané programové smyčky

Samozřejmě se můžeme setkat s algoritmy, které využívají počitadlo smyčky pro provádění dalších operací. V dalším demonstračním příkladu je realizována počítaná programová smyčka, která využívá hodnotu počitadla pro iterativní výpočet:

int loop(int start) {
    int i;
    int s=start;
    for (i=0; i<10; i++) {
        s*=42;
    }
    return s;
}

Způsob překladu tohoto zdrojového kódu do WebAssembly může vypadat následovně:

loop_3.wasm:    file format wasm 0x1
 
Code Disassembly:
 
000042 func[0] <loop>:
 000043: 01 7f                      | local[1] type=i32
 000045: 41 0a                      | i32.const 10
 000047: 21 01                      | local.set 1
 000049: 03 40                      | loop
 00004b: 20 00                      |   local.get 0
 00004d: 41 2a                      |   i32.const 42
 00004f: 6c                         |   i32.mul
 000050: 21 00                      |   local.set 0
 000052: 20 01                      |   local.get 1
 000054: 41 7f                      |   i32.const 4294967295
 000056: 6a                         |   i32.add
 000057: 22 01                      |   local.tee 1
 000059: 0d 00                      |   br_if 0
 00005b: 0b                         | end
 00005c: 20 00                      | local.get 0
 00005e: 0b                         | end

Základ počítané smyčky:

loop
  ...
  ...
  ...
  br_if 0
end

Zajímavé je, že v tomto případě si mohl překladač dovolit celý výpočet otočit a začít s nejvyšší hodnotou počitadla, protože jeho aktuální hodnota není ve výpočtu použita. Další příklad je však odlišný:

int loop(int start) {
    int i;
    int s=start;
    for (i=1; i<10; i++) {
        s*=i;
    }
    return s;
}

Překlad do WebAssembly ukazuje, že nyní se s počitadlem pracuje tak, jak je to zapsáno ve zdrojovém kódu, tedy od 1 do 10 (kromě):

Code Disassembly:
 
000042 func[0] <loop>:
 000043: 01 7f                      | local[1] type=i32
 000045: 41 01                      | i32.const 1
 000047: 21 01                      | local.set 1
 000049: 03 40                      | loop
 00004b: 20 00                      |   local.get 0
 00004d: 20 01                      |   local.get 1
 00004f: 6c                         |   i32.mul
 000050: 21 00                      |   local.set 0
 000052: 20 01                      |   local.get 1
 000054: 41 01                      |   i32.const 1
 000056: 6a                         |   i32.add
 000057: 22 01                      |   local.tee 1
 000059: 41 0a                      |   i32.const 10
 00005b: 47                         |   i32.ne
 00005c: 0d 00                      |   br_if 0
 00005e: 0b                         | end
 00005f: 20 00                      | local.get 0
 000061: 0b                         | end

12. Vnořené počítané programové smyčky

Pro zajímavost si taktéž vyzkoušíme, jakým způsobem se přeloží zdrojový kód s vnořenými smyčkami. V tomto případě se totiž instrukce pro skok na začátek smyčky (br nebo br_if) sice nebudou lišit svým parametrem (bude se stále jednat o nulu), ovšem blok, na jehož začátek bude skok prováděn, bude odlišný, a to v závislosti na kontextu (vnitřní nebo vnější smyčka):

void print(int);
 
void nested_loops(void) {
    int x, y;
    for (y=1; y<=10; y++) {
        for (x=1; x<=10; x++) {
            print(x*y);
        }
    }
}

Překlad do WebAssembly bude nyní vypadat následovně:

loop_4.wasm:    file format wasm 0x1
 
Code Disassembly:
 
000050 func[1] <nested_loops>:
 000051: 03 7f                      | local[1..3] type=i32
 000053: 41 01                      | i32.const 1
 000055: 21 00                      | local.set 0
 000057: 03 40                      | loop
 000059: 41 0a                      |   i32.const 10
 00005b: 21 01                      |   local.set 1
 00005d: 20 00                      |   local.get 0
 00005f: 21 02                      |   local.set 2
 000061: 03 40                      |   loop
 000063: 20 02                      |     local.get 2
 000065: 10 80 80 80 80 00          |     call 0 <env.print>
 00006b: 20 02                      |     local.get 2
 00006d: 20 00                      |     local.get 0
 00006f: 6a                         |     i32.add
 000070: 21 02                      |     local.set 2
 000072: 20 01                      |     local.get 1
 000074: 41 7f                      |     i32.const 4294967295
 000076: 6a                         |     i32.add
 000077: 22 01                      |     local.tee 1
 000079: 0d 00                      |     br_if 0
 00007b: 0b                         |   end
 00007c: 20 00                      |   local.get 0
 00007e: 41 01                      |   i32.const 1
 000080: 6a                         |   i32.add
 000081: 22 00                      |   local.tee 0
 000083: 41 0b                      |   i32.const 11
 000085: 47                         |   i32.ne
 000086: 0d 00                      |   br_if 0
 000088: 0b                         | end
 000089: 0b                         | end

Jedná se o dlouhou sekvenci instrukcí, ovšem vlastní smyčky v ní nalezneme snadno:

loop
  loop
    ...
    ...
    ...
    br_if 0
  end
  ...
  ...
  ...
  br_if 0
end

Instrukce br_if je sice stále stejná, ovšem cíle skoků se budou lišit – a to podle obsahu zásobníku řízení toku.

Pro zajímavost nyní výpočty pozměníme takovým způsobem, aby se namísto celočíselných hodnot používaly hodnoty s plovoucí řádovou čárkou:

void print(double);
 
void nested_loops(void) {
    double x, y;
    for (y=1; y<=10; y++) {
        for (x=1; x<=10; x++) {
            print(x*y);
        }
    }
}

Způsob překladu do WebAssembly:

loop_5.wasm:    file format wasm 0x1
 
Code Disassembly:
 
000050 func[1] <nested_loops>:
 000051: 01 7c                      | local[1] type=f64
 000053: 02 7f                      | local[2..3] type=i32
 000055: 01 7c                      | local[4] type=f64
 000057: 44 00 00 00 00 00 00 f0 3f | f64.const 0x1p+0
 000060: 21 00                      | local.set 0
 000062: 41 01                      | i32.const 1
 000064: 21 01                      | local.set 1
 000066: 03 40                      | loop
 000068: 41 0a                      |   i32.const 10
 00006a: 21 02                      |   local.set 2
 00006c: 44 00 00 00 00 00 00 f0 3f |   f64.const 0x1p+0
 000075: 21 03                      |   local.set 3
 000077: 03 40                      |   loop
 000079: 20 00                      |     local.get 0
 00007b: 20 03                      |     local.get 3
 00007d: a2                         |     f64.mul
 00007e: 10 80 80 80 80 00          |     call 0 <env.print>
 000084: 20 03                      |     local.get 3
 000086: 44 00 00 00 00 00 00 f0 3f |     f64.const 0x1p+0
 00008f: a0                         |     f64.add
 000090: 21 03                      |     local.set 3
 000092: 20 02                      |     local.get 2
 000094: 41 7f                      |     i32.const 4294967295
 000096: 6a                         |     i32.add
 000097: 22 02                      |     local.tee 2
 000099: 0d 00                      |     br_if 0
 00009b: 0b                         |   end
 00009c: 20 00                      |   local.get 0
 00009e: 44 00 00 00 00 00 00 f0 3f |   f64.const 0x1p+0
 0000a7: a0                         |   f64.add
 0000a8: 21 00                      |   local.set 0
 0000aa: 20 01                      |   local.get 1
 0000ac: 41 01                      |   i32.const 1
 0000ae: 6a                         |   i32.add
 0000af: 22 01                      |   local.tee 1
 0000b1: 41 0b                      |   i32.const 11
 0000b3: 47                         |   i32.ne
 0000b4: 0d 00                      |   br_if 0
 0000b6: 0b                         | end
 0000b7: 0b                         | end

Základ je stále stejný.

13. Překlad zdrojových kódů, ve kterých se používá konstrukce goto

Některé programovací jazyky podporují příkaz goto, takže je nutné, aby bylo možné tuto jazykovou konstrukci do WebAssembly nějakým způsobem přeložit. Samozřejmě si otestujeme, jakým způsobem je to zařízeno, což bude zajímavé, protože bajtkód WebAssembly vyžaduje pro všechny skoky blokové instrukce.

Překládat budeme následující (jak je patrné, tak zcela umělý) zdrojový kód:

void positive_case(void);
void negative_case(void);
void finish(void);
 
void bar(int i) {
    if (i>0) {
        goto positive;
    }
    positive_case();
    goto end;
positive:
    negative_case();
end:
    finish();
}

Výsledek překladu do bajtkódu WebAssembly může vypadat následovně:

goto_1.wasm:    file format wasm 0x1
 
Code Disassembly:
 
000079 func[3] <bar>:
 00007a: 02 40                      | block
 00007c: 02 40                      |   block
 00007e: 20 00                      |     local.get 0
 000080: 41 00                      |     i32.const 0
 000082: 4a                         |     i32.gt_s
 000083: 0d 00                      |     br_if 0
 000085: 10 80 80 80 80 00          |     call 0 <env.positive_case>
 00008b: 0c 01                      |     br 1
 00008d: 0b                         |   end
 00008e: 10 81 80 80 80 00          |   call 1 <env.negative_case>
 000094: 0b                         | end
 000095: 10 82 80 80 80 00          | call 2 <env.finish>
 00009b: 0b                         | end

Podívejme se na základní strukturu kódu, ze kterého je patrné, že se v tomto případě musely uměle vytvořit bloky tvořené instrukcemi block a end:

block
  block
    ...
    ...
    ...
    br_if 0
    ...
    ...
    ...
    br 1
  end
end
end

Pro zajímavost se ještě podívejme na to, jak dobře je tento kód zpětně přeložen do čitelné podoby nástrojem wasm-decompile:

import memory env_linear_memory;
 
import function env_positive_case();
 
import function env_negative_case();
 
import function env_finish();
 
function bar(a:int) {
  if (a > 0) goto B_b;
  env_positive_case();
  goto B_a;
  label B_b:
  env_negative_case();
  label B_a:
  env_finish();
}

14. Instrukce br_table

Poslední instrukcí WebAssembly, se kterou se dnes seznámíme, je instrukce nazvaná br_table. Jedná se o instrukci, která umožňuje realizovat vícenásobné rozvětvení na základě tabulky hodnot, které následují za operačním kódem instrukce. Tyto hodnoty mají stejný význam, jako parametry instrukcí br a br_if, tj. pozici od vrcholu zásobníku řízení toku (control-flow stack):

V bajktódu může tato instrukce vypadat následovně:

br_table 9 5 0 1 2

Na základě hodnoty uložené na běžném zásobníku operandů (operand stack) se z tabulky hodnot za instrukcí br_table vybere n-tá hodnota. To například znamená, že pokud je na vrcholu zásobníku operandů uložena hodnota 1, vybere se z tabulky 5 atd. Jak však hodnoty uložené v této tabulce interpretovat? Hodnota 0 znamená ukončení nejvnitřnějšího bloku, hodnota 1 ukončení (výskok) z bloku vnějšího atd. Stále se tedy pracuje s blokovou strukturou, tj. s instrukcemi block a end.

15. Rozeskok realizovaný konstrukcí switch-case

V dalším zdrojovém kódu je realizován rozeskok zapsaný v programovacím jazyku C s využitím konstrukce switch-case. Tento kód si necháme běžným způsobem přeložit do WebAssembly:

void foo(void);
void bar(void);
void baz(void);
void bzz(void);
 
void numeric_value(int x) {
    switch (x) {
        case 0:
            foo();
            break;
        case 1:
            bar();
            break;
        case 2:
            baz();
            break;
        case 3:
            bzz();
            break;
    }
}

Překlad tohoto zdrojového kódu do WebAssembly dopadne následovně:

switch_1.wasm:  file format wasm 0x1
 
Code Disassembly:
 
00006c func[4] <numeric_value>:
 00006d: 02 40                      | block
 00006f: 02 40                      |   block
 000071: 02 40                      |     block
 000073: 02 40                      |       block
 000075: 02 40                      |         block
 000077: 20 00                      |           local.get 0
 000079: 0e 04 00 01 02 03 04       |           br_table 0 1 2 3 4
 000080: 0b                         |         end
 000081: 10 80 80 80 80 00          |         call 0 <env.foo>
 000087: 0f                         |         return
 000088: 0b                         |       end
 000089: 10 81 80 80 80 00          |       call 1 <env.bar>
 00008f: 0f                         |       return
 000090: 0b                         |     end
 000091: 10 82 80 80 80 00          |     call 2 <env.baz>
 000097: 0f                         |     return
 000098: 0b                         |   end
 000099: 10 83 80 80 80 00          |   call 3 <env.bzz>
 00009f: 0b                         | end
 0000a0: 0b                         | end

V případě, že odstraníme nepodstatné instrukce a zaměříme se pouze na blokovou strukturu, bude výsledná struktura bajtkódu vypadat tak, že instrukce br_table (s tabulkou 0 1 2 3 4) dokáže vyskočit z libovolného z pěti zanořených bloků:

block
  block
    block
      block
        block
          local.get 0
          br_table 0 1 2 3 4
        end
      end
    end
  end
end

Pokus o zpětný překlad naznačuje, že bloková struktura je vlastně v tomto případě poměrně umělá, protože se jen snaží napodobit běžné skoky:

import memory env_linear_memory;
 
import function env_foo();
 
import function env_bar();
 
import function env_baz();
 
import function env_bzz();
 
function numeric_value(a:int) {
  br_table[B_e, B_d, B_c, B_b, ..B_a](a)
  label B_e:
  env_foo();
  return ;
  label B_d:
  env_bar();
  return ;
  label B_c:
  env_baz();
  return ;
  label B_b:
  env_bzz();
  label B_a:
}

16. Rozeskok s větví default

V dalším kroku zdrojový kód demonstračního příkladu z předchozí kapitoly upravíme, a to takovým způsobem, že v něm bude zapsána i větev default, tj. větev, u které se neuvádí žádná konstanta (v jiných jazycích podmínka). Nový tvar zdrojového kódu bude v tomto případě vypadat následovně:

void foo(void);
void bar(void);
void baz(void);
void bzz(void);
 
void numeric_value(int x) {
    switch (x) {
        case 0:
            foo();
            break;
        case 1:
            bar();
            break;
        case 2:
            baz();
            break;
        default:
            bzz();
            break;
    }
}

Způsob překladu do WebAssembly v tomto případě dopadne následovně:

switch_2.wasm:  file format wasm 0x1
 
Code Disassembly:
 
00006c func[4] <numeric_value>:
 00006d: 02 40                      | block
 00006f: 02 40                      |   block
 000071: 02 40                      |     block
 000073: 02 40                      |       block
 000075: 20 00                      |         local.get 0
 000077: 0e 03 00 01 02 03          |         br_table 0 1 2 3
 00007d: 0b                         |       end
 00007e: 10 80 80 80 80 00          |       call 0 <env.foo>
 000084: 0f                         |       return
 000085: 0b                         |     end
 000086: 10 81 80 80 80 00          |     call 1 <env.bar>
 00008c: 0f                         |     return
 00008d: 0b                         |   end
 00008e: 10 82 80 80 80 00          |   call 2 <env.baz>
 000094: 0f                         |   return
 000095: 0b                         | end
 000096: 10 83 80 80 80 00          | call 3 <env.bzz>
 00009c: 0b                         | end

Povšimněte si, že ve výsledném bajtkódu jeden ze zanořených bloků chybí a instrukce br_table obsahuje tabulku se čtyřmi hodnotami:

block
  block
    block
      block
        local.get 0
        br_table 0 1 2 3
      end
    end
  end
end

Odlišný je i výsledek, který získáme při pokusu o zpětný překlad z WebAssembly do čitelného vysokoúrovňového jazyka:

import memory env_linear_memory;
 
import function env_foo();
 
import function env_bar();
 
import function env_baz();
 
import function env_bzz();
 
function numeric_value(a:int) {
  br_table[B_d, B_c, B_b, ..B_a](a)
  label B_d:
  env_foo();
  return ;
  label B_c:
  env_bar();
  return ;
  label B_b:
  env_baz();
  return ;
  label B_a:
  env_bzz();
}

17. Podrobnější pohled na přeloženou funkci pro výpočet největšího společného dělitele

V tomto okamžiku máme k dispozici všechny informace potřebné k pochopení toho, jakým způsobem byla přeložena funkce pro výpočet největšího společného dělitele, kterou jsme si ukázali v úvodním článku o WebAssembly. Připomeňme si, jak vypadal původní zdrojový kód této funkce naprogramované v jazyku C:

int gcd(int u, int v) {
    while (v) {
        int t = u;
        u = v;
        v = t % v;
    }
    return u;
}

Překlad do WebAssembly je na první pohled poněkud zvláštní, ovšem to si hned vysvětlíme:

gcd.wasm:       file format wasm 0x1
 
Code Disassembly:
 
000043 func[0] <gcd>:
 000044: 01 7f                      | local[2] type=i32
 000046: 02 40                      | block
 000048: 20 01                      |   local.get 1
 00004a: 0d 00                      |   br_if 0
 00004c: 20 00                      |   local.get 0
 00004e: 0f                         |   return
 00004f: 0b                         | end
 000050: 03 40                      | loop
 000052: 20 00                      |   local.get 0
 000054: 20 01                      |   local.get 1
 000056: 22 02                      |   local.tee 2
 000058: 6f                         |   i32.rem_s
 000059: 21 01                      |   local.set 1
 00005b: 20 02                      |   local.get 2
 00005d: 21 00                      |   local.set 0
 00005f: 20 01                      |   local.get 1
 000061: 0d 00                      |   br_if 0
 000063: 0b                         | end
 000064: 20 02                      | local.get 2
 000066: 0b                         | end

Ve vygenerovaném bajtkódu můžeme vidět běžný blok s podmínkou a taktéž s instrukcí return. Tento blok hlídá, jestli vstup do smyčky „strážený“ podmínkou while(u) není již na začátku vyhodnocen jako nepravdivý. Pokud tomu tak je, vrátí se nula a funkci je možné ihned ukončit:

block
  ...
  ...
  ...
  br_if 0
  ...
  ...
  ...
  return
end

Následuje implementace vlastní programové smyčky, na jejímž konci se vyhodnocuje obsah proměnné v. Skok na začátek smyčky je proveden pouze za předpokladu, že je v nenulové:

loop
  ...
  ...
  ...
  br_if 0
end

18. Obsah navazujícího článku

Do specifikace WebAssembly byly později přidány i další rozšiřující instrukce. Mezi tyto instrukce patří zejména instrukce umožňující provádět vektorové operace (resp. přesněji řečeno SIMD operace). Překladače LLVM tyto instrukce podporují a navíc pro ně máme přímou podporu i přímo v Clangu (dokonce na několika úrovních). A právě s tímto (ve světě videí a umělé inteligence) velmi důležitým rozšířením WebAssembly se budeme zabývat v navazujícím článku.

19. Tabulka se všemi doposud popsanými instrukcemi

Všechny instrukce WebAssembly, které jsme si až doposud popsali, jsou vypsány v následující tabulce, kde jsou seřazeny podle svého operačního kódu (tedy na základě hodnoty svého prvního bajtu). Aby bylo zřejmé, jaký rozsah instrukčního souboru již byl popsán, obsahuje tabulka i (prozatím) prázdné řádky:

20. Odkazy na Internetu

1. Compiling C to WebAssembly without Emscripten
   https://surma.dev/things/c-to-webassembly/
2. Web Assemply: Text Format
   https://webassembly.github­.io/spec/core/text/index.html
3. WebAssembly: Binary Format
   https://webassembly.github­.io/spec/core/binary/index­.html
4. WebAssembly
   https://webassembly.org/
5. WebAssembly na Wiki Golangu
   https://github.com/golang/go/wi­ki/WebAssembly
6. The future of WebAssembly – A look at upcoming features and proposals
   https://blog.scottlogic.com/2018/07/20/wasm-future.html
7. WebAssembly Design
   https://github.com/WebAssembly/design
8. Využití WebAssembly z programovacího jazyka Go
   https://www.root.cz/clanky/vyuziti-webassembly-z-programovaciho-jazyka-go/
9. WebAssembly slibuje podstatné zrychlení webů, konec JavaScriptu se ale nekoná
   https://www.lupa.cz/clanky/webassembly-slibuje-podstatne-zrychleni-webu-konec-javascriptu-se-ale-nekona/
10. List of languages that compile to JS
    https://github.com/jashke­nas/coffeescript/wiki/List-of-languages-that-compile-to-JS
11. asm.js
    http://asmjs.org/
12. Top 23 WASM Open-Source Projects
    https://www.libhunt.com/topic/wasm
13. Made with WebAssembly
    https://madewithwebassembly.com/
14. The Top 1,790 Wasm Open Source Projects on Github
    https://awesomeopensource­.com/projects/wasm
15. Sanspiel
    https://sandspiel.club/
16. Painting on HTML5 Canvas with Rust WASM
    https://www.subarctic.org/pa­inting_on_html5_canvas_wit­h_rust_wasm.html
17. Writing WebAssembly By Hand
    https://blog.scottlogic.com/2018/04/26/we­bassembly-by-hand.html
18. WebAssembly Specification
    https://webassembly.github­.io/spec/core/index.html
19. Index of Instructions
    https://webassembly.github­.io/spec/core/appendix/in­dex-instructions.html
20. The WebAssembly Binary Toolkit
    https://github.com/WebAssembly/wabt
21. Will WebAssembly replace JavaScript? Or Will WASM Make JavaScript More Valuable in Future?
    https://dev.to/vaibhavshah/will-webassembly-replace-javascript-or-will-wasm-make-javascript-more-valuable-in-future-5c6e
22. Webassembly as 32bit and 64bit
    https://stackoverflow.com/qu­estions/78580226/webassem­bly-as-32bit-and-64bit
23. Portability
    https://webassembly.org/doc­s/portability/
24. Hexadecimální prohlížeče a editory s textovým uživatelským rozhraním
    https://www.root.cz/clanky/he­xadecimalni-prohlizece-a-editory-s-textovym-uzivatelskym-rozhranim/
25. Nástroj objdump: švýcarský nožík pro vývojáře
    https://www.root.cz/clanky/nastroj-objdump-svycarsky-nozik-pro-vyvojare/
26. Getting Started: Building and Running Clang
    https://clang.llvm.org/get_star­ted.html
27. Clang: a C language family frontend for LLVM
    https://clang.llvm.org/
28. Scheduling LLVM Passes with the New Pass Manager
    https://stephenverderame.git­hub.io/blog/scheduling_llvm/
29. C data types
    https://en.wikipedia.org/wi­ki/C_data_types
30. WebAssembly data types
    https://webassembly.github­.io/spec/core/syntax/types­.html
31. WebAssembly Opcodes
    https://pengowray.github.io/wasm-ops/
32. Advanced tools (for WebAssembly)
    https://webassembly.org/getting-started/advanced-tools/
33. Binaryen
    https://github.com/WebAssem­bly/binaryen
34. Using SIMD with WebAssembly
    https://emscripten.org/doc­s/porting/simd.html