Technologie mezijazyků (mezikódů) a bajtkódů: LLVM IR a SIMD

Obsah

1. Technologie mezijazyků (mezikódů) a bajtkódů v moderních interpretrech a překladačích: LLVM IR a SIMD

2. „Vektorové“ datové typy podporované v LLVM IR

3. Shrnutí: datové typy podporované v LLVM IR

4. První demonstrační příklad: součet dvou vektorů se šestnácti celočíselnými prvky

5. LLVM IR po rozšíření délky vektoru na 32 celočíselných prvků

6. Vektorový součet pro vektory s celočíselnými prvky různých typů

7. Vliv délky vektorů na instrukce LLVM IR

8. Překlad s povolením instrukcí AVX popř. AVX-512

9. Ostatní aritmetické operace s celočíselnými vektory

10. Operace s vektory obsahujícími hodnoty s plovoucí řádovou čárkou

11. Součet vektorů s hodnotami s plovoucí řádovou čárkou

12. Základní aritmetické operátory a vektory s prvky s plovoucí řádovou čárkou

13. Porovnání vektorů prvek po prvku

14. Demonstrační příklad: porovnání vektorů s prvky různých typů

15. Výpočet druhé odmocniny všech prvků vektorů + nové instrukce LLVM IR

16. Výpočet skalárního součinu

17. Příloha A: seznam doposud popsaných instrukcí používaných v LLVM IR

18. Příloha B: Makefile soubor pro překlad všech demonstračních příkladů

19. Repositář s demonstračními příklady

20. Odkazy na Internetu

1. Technologie mezijazyků (mezikódů) a bajtkódů v moderních interpretrech a překladačích: LLVM IR a SIMD

LLVM IR je navržen takovým způsobem, aby byl efektivně využitelný i na moderních architekturách mikroprocesorů. A prakticky všechny tyto architektury (tedy včetně x86, x86–64 i AArch64) podporují operace typu SIMD (Single Instruction Multiple Data), což znamená, že některé operace lze provádět nikoli pouze se skalárními hodnotami, ale i s vektory pevně dané délky. Moderní instrukční sady typicky podporují operace s vektory s šířkou 128 bitů, 256 bitů a v některých případech i 512 bitů. Takto široké vektory jsou rozdělovány na jednotlivé prvky, přičemž počet těchto prvků pochopitelně záleží na bitové šířce vektorů a současně na bitové šířce prvků. To například znamená, že 128bitový vektor může obsahovat šestnáct prvků typu byte, osm prvků typu half-float, čtyři prvky typu float/single nebo dva prvky typu double (dtto pro celočíselné datové typy se znaménkem nebo bez znaménka). Navíc LLVM IR generuje odlišné instrukce podle toho, jak široké registry cílová platforma podporuje.

2. „Vektorové“ datové typy podporované v LLVM IR

Mezikód LLVM IR práci s vektory podporuje, ovšem za předpokladu, že cílová platforma obsahuje příslušné SIMD operace. Tato podpora se projevuje i v nabídce podporovaných datových typů. Prozatím jsme mohli vidět celočíselné typy, typy s plovoucí řádovou čárkou, ukazatele (ty jsou plně typované) a typ void. Ovšem navíc se můžeme setkat právě s podporou vektorů a taktéž polí. U těchto datových typů se vždy udává počet prvků a typ prvků. Při čtení LLVM IR je snadné rozlišit, zda se jedná o pole nebo o vektor, a to konkrétně podle toho, jaké závorky jsou ve specifikaci typu použity. U polí je typ (počet prvků a typ prvků) zapsán do hranatých závorek, zatímco u vektorů se jedná o závorky úhlové.

To tedy znamená, že například typ „pole deseti 32bitových celočíselných prvků“ se zapíše takto:

[10 x i32]

Zatímco typ „vektor osmi 32bitových celočíselných prvků“ bude v LLVM IR zapsán tímto stylem:

< 8 x i32 >

3. Shrnutí: datové typy podporované v LLVM IR

V tabulce jsou pro úplnost vypsány všechny datové typy podporované v mezikódu LLVM IR:

4. První demonstrační příklad: součet dvou vektorů se šestnácti celočíselnými prvky

Otázkou ovšem zůstává, jakým způsobem se vlastně vektory zapisují ve vyšších programovacích jazycích. V případě jazyka C a překladače Clang byl převzat způsob navržený pro GCC. Podívejme se na následující příklad, v němž je definován nový typ nazvaný i8×16 (jméno může být pochopitelně jakékoli; zde se konkrétně ve jméně typu snažím naznačit jak typ prvků vektoru, tak i jejich počet). V tomto konkrétním případě se jedná o vektor o délce šestnácti bajtů, který obsahuje prvky typu signed char, což zde konkrétně může znamenat, že se do vektoru vejde celkem šestnáct těchto prvků za předpokladu, že sizeof(signed char)==1:

typedef signed char i8x16 __attribute__((vector_size(16)));

Na základě tohoto typu již snadno zapíšeme funkci, která provede součet dvou vektorů, tj. interně součty odpovídajících si prvků obou vstupních vektorů:

i8x16 add(i8x16 x, i8x16 y) {
    return x + y;
}

Po překladu do mezikódu LLVM IR je patrné, že se použije instrukce add (tu již dobře známe), ovšem se specifikací typu <16 x i8>, z čehož jasně plyne, že se sčítají vektory se šestnácti prvky typu i8:

; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <16 x i8> @add(<16 x i8> noundef %0, <16 x i8> noundef %1) local_unnamed_addr #0 {
  %3 = add <16 x i8> %1, %0
  ret <16 x i8> %3
}

Navíc si povšimněte, jak jsou specifikovány parametry funkce add i typ její návratové hodnoty:

5. LLVM IR po rozšíření délky vektoru na 32 celočíselných prvků

Pokusme se nyní vektor (resp. přesněji řečeno námi definovaný typ vektor) rozšířit ze šestnácti prvků na třicet dva prvků. Z pohledu céčkového programátora je změna nepatrná:

typedef signed char i8x32 __attribute__((vector_size(32)));
 
i8x32 add(i8x32 x, i8x32 y) {
    return x + y;
}

Ovšem mezikód LLVM IR již bude odlišný:

; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(argmem: read) uwtable
define dso_local <32 x i8> @add(ptr nocapture noundef readonly byval(<32 x i8>) align 32 %0, ptr nocapture noundef readonly byval(<32 x i8>) align 32 %1) local_unnamed_addr #0 {
  %3 = load <32 x i8>, ptr %0, align 32, !tbaa !3
  %4 = load <32 x i8>, ptr %1, align 32, !tbaa !3
  %5 = add <32 x i8> %4, %3
  ret <32 x i8> %5
}

Především se změní parametry funkce add (ovšem nikoli její návratová hodnota):

Metadata parametrů určují, že i když se předávají ukazatele, nebudou tyto ukazatele nikam ukládány a navíc se přes ně přistupuje do paměti, ze které se hodnoty pouze čtou. Ovšem to, že se nyní pracuje s ukazateli (evidentně se nepočítá s AVX), nutně znamená, že se změní i tělo funkce: oba vektory se nejdříve načtou do proměnných %3 a %4 a teprve poté je proveden vektorový součet:

  %3 = load <32 x i8>, ptr %0, align 32, !tbaa !3
  %4 = load <32 x i8>, ptr %1, align 32, !tbaa !3
  %5 = add <32 x i8> %4, %3

6. Vektorový součet pro vektory s celočíselnými prvky různých typů

Pokusme se nyní zjistit, jak bude vypadat mezikód LLVM v případě, že budeme chtít provádět vektorový součet pro vektory, které jsou uloženy v šestnácti bajtech, ovšem mají různý počet a typ prvků. Tento počet a typ je vždy zvolen takovým způsobem, abychom dostali délku 128 bitů, tedy oněch šestnáct bajtů:

typedef signed char        i8x16 __attribute__((vector_size(16)));
typedef unsigned char      u8x16 __attribute__((vector_size(16)));
typedef signed short int   i16x8 __attribute__((vector_size(16)));
typedef unsigned short int u16x8 __attribute__((vector_size(16)));
typedef signed int         i32x4 __attribute__((vector_size(16)));
typedef unsigned int       u32x4 __attribute__((vector_size(16)));
typedef signed long int    i64x2 __attribute__((vector_size(16)));
typedef unsigned long int  u64x2 __attribute__((vector_size(16)));
 
i8x16 add_i8x16(i8x16 x, i8x16 y) {
    return x + y;
}
 
u8x16 add_u8x16(u8x16 x, u8x16 y) {
    return x + y;
}
 
i16x8 add_i16x8(i16x8 x, i16x8 y) {
    return x + y;
}
 
u16x8 add_u16x8(u16x8 x, u16x8 y) {
    return x + y;
}
 
i32x4 add_i32x4(i32x4 x, i32x4 y) {
    return x + y;
}
 
u32x4 add_u32x4(u32x4 x, u32x4 y) {
    return x + y;
}
 
i64x2 add_i64x2(i64x2 x, i64x2 y) {
    return x + y;
}
 
u64x2 add_u64x2(u64x2 x, u64x2 y) {
    return x + y;
}

Způsob překladu do mezikódu LLVM IR naznačuje, že se vždy použije naprosto stejná sekvence instrukcí add + ret; bude se odlišovat pouze typ parametrů funkce, typ návratové hodnoty i typ přiřazený k instrukci add:

<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <16 x i8> @add_i8x16(<16 x i8> noundef %0, <16 x i8> noundef %1) local_unnamed_addr #0 {
  %3 = add <16 x i8> %1, %0
  ret <16 x i8> %3
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <16 x i8> @add_u8x16(<16 x i8> noundef %0, <16 x i8> noundef %1) local_unnamed_addr #0 {
  %3 = add <16 x i8> %1, %0
  ret <16 x i8> %3
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <8 x i16> @add_i16x8(<8 x i16> noundef %0, <8 x i16> noundef %1) local_unnamed_addr #0 {
  %3 = add <8 x i16> %1, %0
  ret <8 x i16> %3
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <8 x i16> @add_u16x8(<8 x i16> noundef %0, <8 x i16> noundef %1) local_unnamed_addr #0 {
  %3 = add <8 x i16> %1, %0
  ret <8 x i16> %3
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <4 x i32> @add_i32x4(<4 x i32> noundef %0, <4 x i32> noundef %1) local_unnamed_addr #0 {
  %3 = add <4 x i32> %1, %0
  ret <4 x i32> %3
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <4 x i32> @add_u32x4(<4 x i32> noundef %0, <4 x i32> noundef %1) local_unnamed_addr #0 {
  %3 = add <4 x i32> %1, %0
  ret <4 x i32> %3
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <2 x i64> @add_i64x2(<2 x i64> noundef %0, <2 x i64> noundef %1) local_unnamed_addr #0 {
  %3 = add <2 x i64> %1, %0
  ret <2 x i64> %3
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <2 x i64> @add_u64x2(<2 x i64> noundef %0, <2 x i64> noundef %1) local_unnamed_addr #0 {
  %3 = add <2 x i64> %1, %0
  ret <2 x i64> %3
}

7. Vliv délky vektorů na instrukce LLVM IR

Pokusme se nyní zjistit přesněji, jaký vliv má vlastně celková délka (resp. šířka) vektorů na mezikód, který je vygenerovaný překladačem Clang. K tomuto účelu naprogramujeme realizaci součtu vektorů různé délky, ovšem ve všech případech budou tyto vektory obsahovat prvky typu signed char. Počet prvků vektorů se bude lišit: 4, 8, … až 128 prvků. Realizaci součtů dvojice vektorů se stejným počtem a typem prvků je možné v programovacím jazyce C realizovat snadno:

typedef signed char i8x4 __attribute__((vector_size(4)));
typedef signed char i8x8 __attribute__((vector_size(8)));
typedef signed char i8x16 __attribute__((vector_size(16)));
typedef signed char i8x32 __attribute__((vector_size(32)));
typedef signed char i8x64 __attribute__((vector_size(64)));
typedef signed char i8x128 __attribute__((vector_size(128)));
 
i8x4 add_i8x4(i8x4 x, i8x4 y) {
    return x + y;
}
 
i8x8 add_i8x8(i8x8 x, i8x8 y) {
    return x + y;
}
 
i8x16 add_i8x16(i8x16 x, i8x16 y) {
    return x + y;
}
 
i8x32 add_i8x32(i8x32 x, i8x32 y) {
    return x + y;
}
 
i8x64 add_i8x64(i8x64 x, i8x64 y) {
    return x + y;
}
 
i8x128 add_i8x128(i8x128 x, i8x128 y) {
    return x + y;
}

Překlad do mezikódu LLVM IR dopadne následovně:

<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef i32 @add_i8x4(i32 noundef %0, i32 noundef %1) local_unnamed_addr #0 {
  %3 = bitcast i32 %0 to <4 x i8>
  %4 = bitcast i32 %1 to <4 x i8>
  %5 = add <4 x i8> %4, %3
  %6 = bitcast <4 x i8> %5 to i32
  ret i32 %6
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef double @add_i8x8(double noundef %0, double noundef %1) local_unnamed_addr #0 {
  %3 = bitcast double %0 to <8 x i8>
  %4 = bitcast double %1 to <8 x i8>
  %5 = add <8 x i8> %4, %3
  %6 = bitcast <8 x i8> %5 to double
  ret double %6
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <16 x i8> @add_i8x16(<16 x i8> noundef %0, <16 x i8> noundef %1) local_unnamed_addr #1 {
  %3 = add <16 x i8> %1, %0
  ret <16 x i8> %3
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(argmem: read) uwtable</i>
define dso_local <32 x i8> @add_i8x32(ptr nocapture noundef readonly byval(<32 x i8>) align 32 %0, ptr nocapture noundef readonly byval(<32 x i8>) align 32 %1) local_unnamed_addr #2 {
  %3 = load <32 x i8>, ptr %0, align 32, !tbaa !3
  %4 = load <32 x i8>, ptr %1, align 32, !tbaa !3
  %5 = add <32 x i8> %4, %3
  ret <32 x i8> %5
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(argmem: read) uwtable</i>
define dso_local <64 x i8> @add_i8x64(ptr nocapture noundef readonly byval(<64 x i8>) align 64 %0, ptr nocapture noundef readonly byval(<64 x i8>) align 64 %1) local_unnamed_addr #3 {
  %3 = load <64 x i8>, ptr %0, align 64, !tbaa !3
  %4 = load <64 x i8>, ptr %1, align 64, !tbaa !3
  %5 = add <64 x i8> %4, %3
  ret <64 x i8> %5
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(argmem: read) uwtable</i>
define dso_local <128 x i8> @add_i8x128(ptr nocapture noundef readonly byval(<128 x i8>) align 128 %0, ptr nocapture noundef readonly byval(<128 x i8>) align 128 %1) local_unnamed_addr #4 {
  %3 = load <128 x i8>, ptr %0, align 128, !tbaa !3
  %4 = load <128 x i8>, ptr %1, align 128, !tbaa !3
  %5 = add <128 x i8> %4, %3
  ret <128 x i8> %5
}

Výsledný mezikód můžeme rozdělit do čtyř kategorií:

1. „Nativní“ zpracování vektorů šířky 128 bitů (to plyne z použité architektury, viz další kapitolu)
2. Práce s vektory šířky větší než 128 bitů, které se přenáší přes reference, čemuž taktéž odpovídá delší mezikód
3. Vektory se šířkou 32 bitů jsou přenášeny jako běžné 32bitové parametry, ovšem v mezikódu je nutné explicitně provést typovou konverzi instrukcí bitcast (což je pro nás nová instrukce!)
4. Vektory se šířkou 64 bitů jsou přenášeny jako 64bitové parametry typu double (!!!). A opět platí, že je vyžadována explicitní typová konverze instrukcí bitcast

8. Překlad s povolením instrukcí AVX popř. AVX-512

V předchozím textu jsme si řekli, že způsob překladu do LLVM IR v případě vektorových instrukcí (ovšem nejenom zde) do jisté míry závisí na použité architektuře mikroprocesorů. To si ostatně můžeme snadno ověřit. Příklad z předchozí kapitoly přeložíme s použitím přepínače -mavx, čímž se povolí využití instrukční sady AVX s 256bitovými registry. Výsledný mezikód se změní zejména pro funkci add_i8×32. Nyní se do této funkce předávají vektory hodnotou (tedy ve výsledném kódu přes registr) a odpadly tak instrukce load (ovšem pro úplnost uvádím i výpisy funkcí pro kratší a delší vektory):

<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <16 x i8> @add_i8x16(<16 x i8> noundef %0, <16 x i8> noundef %1) local_unnamed_addr #1 {
  %3 = add <16 x i8> %1, %0
  ret <16 x i8> %3
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <32 x i8> @add_i8x32(<32 x i8> noundef %0, <32 x i8> noundef %1) local_unnamed_addr #2 {
  %3 = add <32 x i8> %1, %0
  ret <32 x i8> %3
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(argmem: read) uwtable</i>
define dso_local <64 x i8> @add_i8x64(ptr nocapture noundef readonly byval(<64 x i8>) align 64 %0, ptr nocapture noundef readonly byval(<64 x i8>) align 64 %1) local_unnamed_addr #3 {
  %3 = load <64 x i8>, ptr %0, align 64, !tbaa !3
  %4 = load <64 x i8>, ptr %1, align 64, !tbaa !3
  %5 = add <64 x i8> %4, %3
  ret <64 x i8> %5
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(argmem: read) uwtable</i>
define dso_local <128 x i8> @add_i8x128(ptr nocapture noundef readonly byval(<128 x i8>) align 128 %0, ptr nocapture noundef readonly byval(<128 x i8>) align 128 %1) local_unnamed_addr #4 {
  %3 = load <128 x i8>, ptr %0, align 128, !tbaa !3
  %4 = load <128 x i8>, ptr %1, align 128, !tbaa !3
  %5 = add <128 x i8> %4, %3
  ret <128 x i8> %5
}

Můžeme pokračovat ještě dále a povolit použití instrukční sady AVX-512 (resp. jedné množiny instrukcí patřících do AVX-512). Postačuje použít přepínač -mavx512f. V takovém případě budou předávány „celé vektory“ do funkcí add_i8×16, add_i8×32 i add_i8×64, tedy vektory s šířkou 128, 256 i 512 bitů. Ovšem 1024bitové vektory jsou stále předávány referencí, což se týká funkce add_i8×128:

<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <16 x i8> @add_i8x16(<16 x i8> noundef %0, <16 x i8> noundef %1) local_unnamed_addr #1 {
  %3 = add <16 x i8> %1, %0
  ret <16 x i8> %3
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <32 x i8> @add_i8x32(<32 x i8> noundef %0, <32 x i8> noundef %1) local_unnamed_addr #2 {
  %3 = add <32 x i8> %1, %0
  ret <32 x i8> %3
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <64 x i8> @add_i8x64(<64 x i8> noundef %0, <64 x i8> noundef %1) local_unnamed_addr #3 {
  %3 = add <64 x i8> %1, %0
  ret <64 x i8> %3
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(argmem: read) uwtable</i>
define dso_local <128 x i8> @add_i8x128(ptr nocapture noundef readonly byval(<128 x i8>) align 128 %0, ptr nocapture noundef readonly byval(<128 x i8>) align 128 %1) local_unnamed_addr #4 {
  %3 = load <128 x i8>, ptr %0, align 128, !tbaa !3
  %4 = load <128 x i8>, ptr %1, align 128, !tbaa !3
  %5 = add <128 x i8> %4, %3
  ret <128 x i8> %5
}

9. Ostatní aritmetické operace s celočíselnými vektory

typedef unsigned int i32x4 __attribute__((vector_size(16)));
 
i32x4 neg(i32x4 x) {
    return -x;
}
 
i32x4 add(i32x4 x, i32x4 y) {
    return x + y;
}
 
i32x4 sub(i32x4 x, i32x4 y) {
    return x - y;
}
 
i32x4 mul(i32x4 x, i32x4 y) {
    return x * y;
}
 
i32x4 div(i32x4 x, i32x4 y) {
    return x / y;
}
 
i32x4 rem(i32x4 x, i32x4 y) {
    return x % y;
}

Ze způsobu překladu tohoto zdrojového kódu do mezikódu LLVM IR vyplývá, že se používají stále stejné instrukce (které již známe), ovšem s typem „vektor“. Jediná podstatnější změna je patrná u první funkce, v jejímž mezikódu můžeme vidět použití klauzule zeroinitializer pro specifikaci, že první vektor použitý jako operand v instrukci sub má obsahovat samé nulové prvky:

<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <4 x i32> @neg(<4 x i32> noundef %0) local_unnamed_addr #0 {
  %2 = sub <4 x i32> zeroinitializer, %0
  ret <4 x i32> %2
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <4 x i32> @add(<4 x i32> noundef %0, <4 x i32> noundef %1) local_unnamed_addr #0 {
  %3 = add <4 x i32> %1, %0
  ret <4 x i32> %3
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <4 x i32> @sub(<4 x i32> noundef %0, <4 x i32> noundef %1) local_unnamed_addr #0 {
  %3 = sub <4 x i32> %0, %1
  ret <4 x i32> %3
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <4 x i32> @mul(<4 x i32> noundef %0, <4 x i32> noundef %1) local_unnamed_addr #0 {
  %3 = mul <4 x i32> %1, %0
  ret <4 x i32> %3
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <4 x i32> @div(<4 x i32> noundef %0, <4 x i32> noundef %1) local_unnamed_addr #0 {
  %3 = udiv <4 x i32> %0, %1
  ret <4 x i32> %3
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local range(i32 0, -1) <4 x i32> @rem(<4 x i32> noundef %0, <4 x i32> noundef %1) local_unnamed_addr #0 {
  %3 = urem <4 x i32> %0, %1
  ret <4 x i32> %3
}

10. Operace s vektory obsahujícími hodnoty s plovoucí řádovou čárkou

Všechny operace, které je možné v mezikódu LLVM IR provádět s hodnotami s plovoucí řádovou čárkou, jsou podporovány i pro vektory se stejnými typy prvků. Připomeňme si, že se jedná o tyto instrukce:

Dále jsou podporovány různé FP funkce, ovšem jen za předpokladu, že jsou do zdrojového kódu zapsány ve formě volání intrinsic (vestavěných prvků jazyka, což ovšem nebývá běžné). Ke způsobům využití těchto „speciálních“ instrukcí se ještě v tomto seriálu vrátíme.

11. Součet vektorů s hodnotami s plovoucí řádovou čárkou

Připomeňme si, že jak Clang, tak i LLVM IR plně podporují zpracování hodnot s plovoucí řádovou čárkou ve formátech half-float (16 bitů), float/single (32 bitů) a double (64 bitů). To ovšem znamená, že je možné vytvářet i vektory obsahující prvky těchto typů. Z předchozích pokusů víme, že na architektuře x86–64 je možné bez problémů pracovat s vektory šířky 128 bitů (podporováno v SSE, SSE2 atd.), takže si naprogramujeme funkce provádějící součet dvojic vektorů, které postupně obsahují osm prvků typu half-float, čtyři prvky typu float nebo dva prvky typu double. Realizace takového programu je snadná:

typedef float  f32x4 __attribute__((vector_size(16)));
typedef double f64x2 __attribute__((vector_size(16)));
typedef __fp16 f16x8 __attribute__((vector_size(16)));
 
f16x8 add_f16x8(f16x8 x, f16x8 y) {
    return x + y;
}
 
f32x4 add_f32x4(f32x4 x, f32x4 y) {
    return x + y;
}
 
f64x2 add_f64x2(f64x2 x, f64x2 y) {
    return x + y;
}

Z překladu do bajtkódu je patrné, že se ve všech případech použije instrukce fadd s přidanou informací o typech vektorů, které jsou použity jako operandy této instrukce:

<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <8 x half> @add_f16x8(<8 x half> noundef %0, <8 x half> noundef %1) local_unnamed_addr #0 {
  %3 = fadd <8 x half> %0, %1
  ret <8 x half> %3
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <4 x float> @add_f32x4(<4 x float> noundef %0, <4 x float> noundef %1) local_unnamed_addr #0 {
  %3 = fadd <4 x float> %0, %1
  ret <4 x float> %3
}
 
<i>; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable</i>
define dso_local noundef <2 x double> @add_f64x2(<2 x double> noundef %0, <2 x double> noundef %1) local_unnamed_addr #0 {
  %3 = fadd <2 x double> %0, %1
  ret <2 x double> %3
}

Pro úplnost si ještě ukažme podobný příklad, ovšem zpracovávající vektory s šířkou 256 bitů:

typedef float  f32x8 __attribute__((vector_size(32)));
typedef double f64x4 __attribute__((vector_size(32)));
typedef __fp16 f16x16 __attribute__((vector_size(32)));
 
f16x16 add_f16x8(f16x16 x, f16x16 y) {
    return x + y;
}
 
f32x8 add_f32x8(f32x8 x, f32x8 y) {
    return x + y;
}
 
f64x4 add_f64x4(f64x4 x, f64x4 y) {
    return x + y;
}

Překlad pro x86–64 s SSEx, ale nikoli pro mikroprocesory s instrukční sadou AVX:

; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(argmem: read) uwtable
define dso_local <16 x half> @add_f16x8(ptr nocapture noundef readonly byval(<16 x half>) align 32 %0, ptr nocapture noundef readonly byval(<16 x half>) align 32 %1) local_unnamed_addr #0 {
  %3 = load <16 x half>, ptr %0, align 32, !tbaa !3
  %4 = load <16 x half>, ptr %1, align 32, !tbaa !3
  %5 = fadd <16 x half> %3, %4
  ret <16 x half> %5
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(argmem: read) uwtable
define dso_local <8 x float> @add_f32x8(ptr nocapture noundef readonly byval(<8 x float>) align 32 %0, ptr nocapture noundef readonly byval(<8 x float>) align 32 %1) local_unnamed_addr #0 {
  %3 = load <8 x float>, ptr %0, align 32, !tbaa !3
  %4 = load <8 x float>, ptr %1, align 32, !tbaa !3
  %5 = fadd <8 x float> %3, %4
  ret <8 x float> %5
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(argmem: read) uwtable
define dso_local <4 x double> @add_f64x4(ptr nocapture noundef readonly byval(<4 x double>) align 32 %0, ptr nocapture noundef readonly byval(<4 x double>) align 32 %1) local_unnamed_addr #0 {
  %3 = load <4 x double>, ptr %0, align 32, !tbaa !3
  %4 = load <4 x double>, ptr %1, align 32, !tbaa !3
  %5 = fadd <4 x double> %3, %4
  ret <4 x double> %5
}

Překlad s přepínačem -mavx povede k vygenerování odlišného mezikódu:

; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <16 x half> @add_f16x8(<16 x half> noundef %0, <16 x half> noundef %1) local_unnamed_addr #0 {
  %3 = fadd <16 x half> %0, %1
  ret <16 x half> %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <8 x float> @add_f32x8(<8 x float> noundef %0, <8 x float> noundef %1) local_unnamed_addr #0 {
  %3 = fadd <8 x float> %0, %1
  ret <8 x float> %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <4 x double> @add_f64x4(<4 x double> noundef %0, <4 x double> noundef %1) local_unnamed_addr #0 {
  %3 = fadd <4 x double> %0, %1
  ret <4 x double> %3
}

12. Základní aritmetické operátory a vektory s prvky s plovoucí řádovou čárkou

Podobné aritmetické operace, které je možné provádět s vektory obsahujícími celočíselné prvky, jsou samozřejmě podporovány i pro vektory s prvky s plovoucí řádovou čárkou, a to v poloviční, jednoduché i dvojité přesnosti. Jedinou nepodporovanou operací je výpočet zbytku po dělení – což je sice podporováno v LLVM IR (existuje příslušná instrukce), ale nikoli v céčku.

V následujícím demonstračním příkladu jsou všechny základní „vektorové“ operace s hodnotami s plovoucí řádovou čárkou použity:

typedef float  f32x4 __attribute__((vector_size(16)));
typedef double f64x2 __attribute__((vector_size(16)));
typedef __fp16 f16x8 __attribute__((vector_size(16)));
 
#define NEG(type) \
    type neg_##type(type x) { return -x; }
#define ADD(type) \
    type add_##type(type x, type y) { return x + y; }
#define SUB(type) \
    type sub_##type(type x, type y) { return x - y; }
#define MUL(type) \
    type mul_##type(type x, type y) { return x * y; }
#define DIV(type) \
    type div_##type(type x, type y) { return x / y; }
#define REM(type) \
    type rem_##type(type x, type y) { return x % y; }
 
#define ALL_BUT_REM(type) \
    NEG(type)     \
    ADD(type)     \
    SUB(type)     \
    MUL(type)     \
    DIV(type)
 
ALL_BUT_REM(f16x8)
ALL_BUT_REM(f32x4)
ALL_BUT_REM(f64x2)

Výsledek po zpracování preprocesorem programovacího jazyka C:

typedef float  f32x4 __attribute__((vector_size(16)));
typedef double f64x2 __attribute__((vector_size(16)));
typedef __fp16 f16x8 __attribute__((vector_size(16)));
 
f16x8 neg_f16x8(f16x8 x) { return -x; }
f16x8 add_f16x8(f16x8 x, f16x8 y) { return x + y; }
f16x8 sub_f16x8(f16x8 x, f16x8 y) { return x - y; }
f16x8 mul_f16x8(f16x8 x, f16x8 y) { return x * y; }
f16x8 div_f16x8(f16x8 x, f16x8 y) { return x / y; }
f32x4 neg_f32x4(f32x4 x) { return -x; }
f32x4 add_f32x4(f32x4 x, f32x4 y) { return x + y; }
f32x4 sub_f32x4(f32x4 x, f32x4 y) { return x - y; }
f32x4 mul_f32x4(f32x4 x, f32x4 y) { return x * y; }
f32x4 div_f32x4(f32x4 x, f32x4 y) { return x / y; }
f64x2 neg_f64x2(f64x2 x) { return -x; }
f64x2 add_f64x2(f64x2 x, f64x2 y) { return x + y; }
f64x2 sub_f64x2(f64x2 x, f64x2 y) { return x - y; }
f64x2 mul_f64x2(f64x2 x, f64x2 y) { return x * y; }
f64x2 div_f64x2(f64x2 x, f64x2 y) { return x / y; }

Výše uvedené funkce byly přeloženy do LLVM IR následujícím způsobem:

; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <8 x half> @neg_f16x8(<8 x half> noundef %0) local_unnamed_addr #0 {
  %2 = fneg <8 x half> %0
  ret <8 x half> %2
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <8 x half> @add_f16x8(<8 x half> noundef %0, <8 x half> noundef %1) local_unnamed_addr #0 {
  %3 = fadd <8 x half> %0, %1
  ret <8 x half> %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <8 x half> @sub_f16x8(<8 x half> noundef %0, <8 x half> noundef %1) local_unnamed_addr #0 {
  %3 = fsub <8 x half> %0, %1
  ret <8 x half> %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <8 x half> @mul_f16x8(<8 x half> noundef %0, <8 x half> noundef %1) local_unnamed_addr #0 {
  %3 = fmul <8 x half> %0, %1
  ret <8 x half> %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <8 x half> @div_f16x8(<8 x half> noundef %0, <8 x half> noundef %1) local_unnamed_addr #0 {
  %3 = fdiv <8 x half> %0, %1
  ret <8 x half> %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <4 x float> @neg_f32x4(<4 x float> noundef %0) local_unnamed_addr #0 {
  %2 = fneg <4 x float> %0
  ret <4 x float> %2
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <4 x float> @add_f32x4(<4 x float> noundef %0, <4 x float> noundef %1) local_unnamed_addr #0 {
  %3 = fadd <4 x float> %0, %1
  ret <4 x float> %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <4 x float> @sub_f32x4(<4 x float> noundef %0, <4 x float> noundef %1) local_unnamed_addr #0 {
  %3 = fsub <4 x float> %0, %1
  ret <4 x float> %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <4 x float> @mul_f32x4(<4 x float> noundef %0, <4 x float> noundef %1) local_unnamed_addr #0 {
  %3 = fmul <4 x float> %0, %1
  ret <4 x float> %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <4 x float> @div_f32x4(<4 x float> noundef %0, <4 x float> noundef %1) local_unnamed_addr #0 {
  %3 = fdiv <4 x float> %0, %1
  ret <4 x float> %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <2 x double> @neg_f64x2(<2 x double> noundef %0) local_unnamed_addr #0 {
  %2 = fneg <2 x double> %0
  ret <2 x double> %2
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <2 x double> @add_f64x2(<2 x double> noundef %0, <2 x double> noundef %1) local_unnamed_addr #0 {
  %3 = fadd <2 x double> %0, %1
  ret <2 x double> %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <2 x double> @sub_f64x2(<2 x double> noundef %0, <2 x double> noundef %1) local_unnamed_addr #0 {
  %3 = fsub <2 x double> %0, %1
  ret <2 x double> %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <2 x double> @mul_f64x2(<2 x double> noundef %0, <2 x double> noundef %1) local_unnamed_addr #0 {
  %3 = fmul <2 x double> %0, %1
  ret <2 x double> %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <2 x double> @div_f64x2(<2 x double> noundef %0, <2 x double> noundef %1) local_unnamed_addr #0 {
  %3 = fdiv <2 x double> %0, %1
  ret <2 x double> %3
}

13. Porovnání vektorů prvek po prvku

V předchozích dvou článcích jsme se mj. zmínili i o operacích, které slouží pro porovnání dvou skalárních hodnot, ať již se jedná o celá čísla nebo o hodnoty s plovoucí řádovou čárkou. Připomeňme si, že v LLVM IR k tomuto účelu slouží dvojice instrukcí pojmenovaných icmp a fcmp:

Tyto instrukce se používají i pro porovnání dvojice vektorů, přičemž (pochopitelně) dochází k porovnání stylem „prvek po prvku“ a výsledkem nový vektor s pravdivostními hodnotami 1 a 0 (nebo 1.0 a 0.0).

14. Demonstrační příklad: porovnání vektorů s prvky různých typů

Nyní nám pouze zbývá zjistit, jak je vlastně porovnání vektorů stylem prvek po prvku v mezikódu LLVM IR realizováno. Porovnání budeme provádět s vektory s prvky všech základních datových typů:

typedef signed char            i8x16 __attribute__((vector_size(16)));
typedef unsigned char          u8x16 __attribute__((vector_size(16)));
typedef signed short int       i16x8 __attribute__((vector_size(16)));
typedef unsigned short int     u16x8 __attribute__((vector_size(16)));
typedef signed int             i32x4 __attribute__((vector_size(16)));
typedef unsigned int           u32x4 __attribute__((vector_size(16)));
typedef signed long long int   i64x2 __attribute__((vector_size(16)));
typedef unsigned long long int u64x2 __attribute__((vector_size(16)));
typedef float                  f32x4 __attribute__((vector_size(16)));
typedef double                 f64x2 __attribute__((vector_size(16)));
typedef __fp16                 f16x8 __attribute__((vector_size(16)));
 
#define EQ(type) \
    type eq_##type(type x, type y) { return x == y; }
#define LT(type) \
    type lt_##type(type x, type y) { return x < y; }
#define LE(type) \
    type le_##type(type x, type y) { return x <= y; }
#define GT(type) \
    type gt_##type(type x, type y) { return x > y; }
#define GE(type) \
    type ge_##type(type x, type y) { return x >= y; }
#define NE(type) \
    type ne_##type(type x, type y) { return x != y; }
 
#define ALL(type) \
    EQ(type)      \
    LT(type)      \
    LE(type)      \
    GT(type)      \
    GE(type)      \
    NE(type)
 
ALL(i8x16)
ALL(u8x16)
ALL(i16x8)
ALL(u16x8)
ALL(i32x4)
ALL(u32x4)
ALL(i64x2)
ALL(u64x2)
ALL(f16x8)
ALL(f32x4)
ALL(f64x2)

Výsledek po zpracování tohoto zdrojového kódu preprocesorem jazyka C:

typedef signed char            i8x16 __attribute__((vector_size(16)));
typedef unsigned char          u8x16 __attribute__((vector_size(16)));
typedef signed short int       i16x8 __attribute__((vector_size(16)));
typedef unsigned short int     u16x8 __attribute__((vector_size(16)));
typedef signed int             i32x4 __attribute__((vector_size(16)));
typedef unsigned int           u32x4 __attribute__((vector_size(16)));
typedef signed long long int   i64x2 __attribute__((vector_size(16)));
typedef unsigned long long int u64x2 __attribute__((vector_size(16)));
typedef float                  f32x4 __attribute__((vector_size(16)));
typedef double                 f64x2 __attribute__((vector_size(16)));
typedef __fp16                 f16x8 __attribute__((vector_size(16)));
 
i8x16 neg_i8x16(i8x16 x) { return -x; }
i8x16 add_i8x16(i8x16 x, i8x16 y) { return x + y; }
i8x16 sub_i8x16(i8x16 x, i8x16 y) { return x - y; }
i8x16 mul_i8x16(i8x16 x, i8x16 y) { return x * y; }
i8x16 div_i8x16(i8x16 x, i8x16 y) { return x / y; }
i8x16 rem_i8x16(i8x16 x, i8x16 y) { return x % y; }
u8x16 neg_u8x16(u8x16 x) { return -x; }
u8x16 add_u8x16(u8x16 x, u8x16 y) { return x + y; }
u8x16 sub_u8x16(u8x16 x, u8x16 y) { return x - y; }
u8x16 mul_u8x16(u8x16 x, u8x16 y) { return x * y; }
u8x16 div_u8x16(u8x16 x, u8x16 y) { return x / y; }
u8x16 rem_u8x16(u8x16 x, u8x16 y) { return x % y; }
i16x8 neg_i16x8(i16x8 x) { return -x; }
i16x8 add_i16x8(i16x8 x, i16x8 y) { return x + y; }
i16x8 sub_i16x8(i16x8 x, i16x8 y) { return x - y; }
i16x8 mul_i16x8(i16x8 x, i16x8 y) { return x * y; }
i16x8 div_i16x8(i16x8 x, i16x8 y) { return x / y; }
i16x8 rem_i16x8(i16x8 x, i16x8 y) { return x % y; }
u16x8 neg_u16x8(u16x8 x) { return -x; }
u16x8 add_u16x8(u16x8 x, u16x8 y) { return x + y; }
u16x8 sub_u16x8(u16x8 x, u16x8 y) { return x - y; }
u16x8 mul_u16x8(u16x8 x, u16x8 y) { return x * y; }
u16x8 div_u16x8(u16x8 x, u16x8 y) { return x / y; }
u16x8 rem_u16x8(u16x8 x, u16x8 y) { return x % y; }
i32x4 neg_i32x4(i32x4 x) { return -x; }
i32x4 add_i32x4(i32x4 x, i32x4 y) { return x + y; }
i32x4 sub_i32x4(i32x4 x, i32x4 y) { return x - y; }
i32x4 mul_i32x4(i32x4 x, i32x4 y) { return x * y; }
i32x4 div_i32x4(i32x4 x, i32x4 y) { return x / y; }
i32x4 rem_i32x4(i32x4 x, i32x4 y) { return x % y; }
u32x4 neg_u32x4(u32x4 x) { return -x; }
u32x4 add_u32x4(u32x4 x, u32x4 y) { return x + y; }
u32x4 sub_u32x4(u32x4 x, u32x4 y) { return x - y; }
u32x4 mul_u32x4(u32x4 x, u32x4 y) { return x * y; }
u32x4 div_u32x4(u32x4 x, u32x4 y) { return x / y; }
u32x4 rem_u32x4(u32x4 x, u32x4 y) { return x % y; }
i64x2 neg_i64x2(i64x2 x) { return -x; }
i64x2 add_i64x2(i64x2 x, i64x2 y) { return x + y; }
i64x2 sub_i64x2(i64x2 x, i64x2 y) { return x - y; }
i64x2 mul_i64x2(i64x2 x, i64x2 y) { return x * y; }
i64x2 div_i64x2(i64x2 x, i64x2 y) { return x / y; }
i64x2 rem_i64x2(i64x2 x, i64x2 y) { return x % y; }
u64x2 neg_u64x2(u64x2 x) { return -x; }
u64x2 add_u64x2(u64x2 x, u64x2 y) { return x + y; }
u64x2 sub_u64x2(u64x2 x, u64x2 y) { return x - y; }
u64x2 mul_u64x2(u64x2 x, u64x2 y) { return x * y; }
u64x2 div_u64x2(u64x2 x, u64x2 y) { return x / y; }
u64x2 rem_u64x2(u64x2 x, u64x2 y) { return x % y; }
f16x8 neg_f16x8(f16x8 x) { return -x; }
f16x8 add_f16x8(f16x8 x, f16x8 y) { return x + y; }
f16x8 sub_f16x8(f16x8 x, f16x8 y) { return x - y; }
f16x8 mul_f16x8(f16x8 x, f16x8 y) { return x * y; }
f16x8 div_f16x8(f16x8 x, f16x8 y) { return x / y; }
f32x4 neg_f32x4(f32x4 x) { return -x; }
f32x4 add_f32x4(f32x4 x, f32x4 y) { return x + y; }
f32x4 sub_f32x4(f32x4 x, f32x4 y) { return x - y; }
f32x4 mul_f32x4(f32x4 x, f32x4 y) { return x * y; }
f32x4 div_f32x4(f32x4 x, f32x4 y) { return x / y; }
f64x2 neg_f64x2(f64x2 x) { return -x; }
f64x2 add_f64x2(f64x2 x, f64x2 y) { return x + y; }
f64x2 sub_f64x2(f64x2 x, f64x2 y) { return x - y; }
f64x2 mul_f64x2(f64x2 x, f64x2 y) { return x * y; }
f64x2 div_f64x2(f64x2 x, f64x2 y) { return x / y; }

Porovnání vektorů se šestnácti prvky typu char je snadné:

; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local range(i8 -1, 1) <16 x i8> @eq_i8x16(<16 x i8> noundef %0, <16 x i8> noundef %1) local_unnamed_addr #0 {
  %3 = icmp eq <16 x i8> %0, %1
  %4 = sext <16 x i1> %3 to <16 x i8>
  ret <16 x i8> %4
}

Totéž platí i pro další vektory s celočíselnými prvky, například pro vektory 4×int:

; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local range(i32 -1, 1) <4 x i32> @eq_i32x4(<4 x i32> noundef %0, <4 x i32> noundef %1) local_unnamed_addr #0 {
  %3 = icmp eq <4 x i32> %0, %1
  %4 = sext <4 x i1> %3 to <4 x i32>
  ret <4 x i32> %4
}

Zajímavější je porovnání vektorů s hodnotami s plovoucí řádovou čárkou, kde se provádí zpětný převod výsledků porovnání:

; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef <8 x half> @eq_f16x8(<8 x half> noundef %0, <8 x half> noundef %1) local_unnamed_addr #0 {
  %3 = fcmp oeq <8 x half> %0, %1
  %4 = sext <8 x i1> %3 to <8 x i16>
  %5 = bitcast <8 x i16> %4 to <8 x half>
  ret <8 x half> %5
}

Ve všech případech je však patrné, že se používají již známé instrukce icmp a fcmp.

15. Výpočet druhé odmocniny všech prvků vektorů + nové instrukce LLVM IR

Všechny operace s vektory, které jsme si až doposud ukázali, vedly k využití takových variant instrukcí mezikódu LLVM IR, které umožnily s vektory pracovat jako s ucelenou hodnotou (i když byla vnitřně rozdělena na jednotlivé prvky). Snadno si tedy dovedeme představit, že instrukce LLVM IR lze přímo namapovat na reálné instrukce SSE, SSE2, AVX či AVX-512. Vyzkoušejme si však, jaká situace nastane ve chvíli, kdy budeme chtít pro všechny prvky vektoru vypočítat nějakou známou funkci, například druhou odmocninu. Samotné naprogramování takové operace je v jazyku C snadné, protože postačuje vytvořit počítanou programovou smyčku, která projde všemi prvky vstupního vektoru a do vektoru výstupního zapíše vypočtený výsledek funkce.

Zdrojový kód takto navrženého příkladu vypadá následovně:

float  sqrtf(float x);
double sqrt(double x);
 
typedef float  f32x4 __attribute__((vector_size(16)));
typedef double f64x2 __attribute__((vector_size(16)));
 
f32x4 vector_sqrt_f32x4(f32x4 x) {
    f32x4 result;
    int   i;
    for (i = 0; i < 4; i++) {
        result[i] = sqrtf(x[i]);
    }
    return result;
}
 
f64x2 vector_sqrt_f64x2(f64x2 x) {
    f64x2 result;
    int   i;
    for (i = 0; i < 2; i++) {
        result[i] = sqrt(x[i]);
    }
    return result;
}

Překlad do mezikódu LLVM IR ovšem dopadne … zvláštně. Konkrétně v případě první funkce dostaneme:

<i>; Function Attrs: nofree nounwind optsize memory(write) uwtable</i>
define dso_local <4 x float> @vector_sqrt_f32x4(<4 x float> noundef %0) local_unnamed_addr #0 {
  br label %2
 
2:                                                ; preds = %1, %2
  %3 = phi i32 [ 0, %1 ], [ %8, %2 ]
  %4 = phi <4 x float> [ undef, %1 ], [ %7, %2 ]
  %5 = extractelement <4 x float> %0, i32 %3
  %6 = tail call float @sqrtf(float noundef %5) #3, !tbaa !3
  %7 = insertelement <4 x float> %4, float %6, i32 %3
  %8 = add nuw nsw i32 %3, 1
  %9 = icmp eq i32 %8, 4
  br i1 %9, label %10, label %2, !llvm.loop !7
 
10:                                               ; preds = %2
  ret <4 x float> %7
}

Můžeme zde vidět exaktní přepis programové smyčky, tj. (pokud nenařídíme jinak) neprovede se „autovektorizace“ kódu. Ovšem pro nás je zajímavější, že byly použity dvě nové instrukce nazvané extractelement a insertelement

Tyto instrukce nalezneme i v mezikódu druhé céčkové funkce. Zde je ovšem zajímavé, že namísto počítané programové smyčky došlo k jejímu rozbalení, takže se dvakrát provedou operace přečtení_prvku+zavolání sqrt+zápis prvku:

<i>; Function Attrs: mustprogress nofree nounwind optsize willreturn memory(write)</i>
declare dso_local float @sqrtf(float noundef) local_unnamed_addr #1
 
<i>; Function Attrs: mustprogress nofree nounwind optsize willreturn memory(write) uwtable</i>
define dso_local <2 x double> @vector_sqrt_f64x2(<2 x double> noundef %0) local_unnamed_addr #2 {
  %2 = extractelement <2 x double> %0, i64 0
  %3 = tail call double @sqrt(double noundef %2) #3, !tbaa !3
  %4 = insertelement <2 x double> poison, double %3, i64 0
  %5 = extractelement <2 x double> %0, i64 1
  %6 = tail call double @sqrt(double noundef %5) #3, !tbaa !3
  %7 = insertelement <2 x double> %4, double %6, i64 1
  ret <2 x double> %7
}

16. Výpočet skalárního součinu

Instrukce extractelement je použita i při překladu kódu, ve kterém je implementován výpočet skalárního součinu, což je jedna z nejčastěji využívaných „vektorových“ operací (i když výsledkem je skalární hodnota). Pokusme se nejdříve o implementaci skalárního součinu pro vektory s prvky s plovoucí řádovou čárkou:

typedef float  f32x4 __attribute__((vector_size(16)));
typedef double f64x2 __attribute__((vector_size(16)));
typedef __fp16 f16x8 __attribute__((vector_size(16)));
 
float dot_fp16(f16x8 x , f16x8 y) {
    return x[0] * y[0] + x[1] * y[1] + x[2] * y[2] + x[3] * y[3] +
           x[4] * y[4] + x[5] * y[5] + x[6] * y[6] + x[7] * y[7];
}
 
float dot_float(f32x4 x, f32x4 y) {
    return x[0] * y[0] + x[1] * y[1] + x[2] * y[2] + x[3] * y[3];
}
 
double dot_double(f64x2 x, f64x2 y) {
    return x[0] * y[0] + x[1] * y[1];
}

Překlad do mezikódu LLVM IR ukazuje „rozbalení“ výpočtu, prozatím bez provádění optimalizací, které by v tomto případě bylo možné provádět. Zajímavé je, že byly vytvořeny nové pomocné funkce fmuladd, které umožnily refaktoring mezikódu. Ovšem ztratili jsme veškeré možnosti, které nám poskytuje SIMD (o tom, jak je využít, se zmíníme příště):

; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local float @dot_fp16(<8 x half> noundef %0, <8 x half> noundef %1) local_unnamed_addr #0 {
  %3 = extractelement <8 x half> %0, i64 0
  %4 = fpext half %3 to float
  %5 = extractelement <8 x half> %1, i64 0
  %6 = fpext half %5 to float
  %7 = extractelement <8 x half> %0, i64 1
  %8 = fpext half %7 to float
  %9 = extractelement <8 x half> %1, i64 1
  %10 = fpext half %9 to float
  %11 = fmul float %8, %10
  %12 = tail call float @llvm.fmuladd.f32(float %4, float %6, float %11)
  %13 = extractelement <8 x half> %0, i64 2
  %14 = fpext half %13 to float
  %15 = extractelement <8 x half> %1, i64 2
  %16 = fpext half %15 to float
  %17 = tail call float @llvm.fmuladd.f32(float %14, float %16, float %12)
  %18 = extractelement <8 x half> %0, i64 3
  %19 = fpext half %18 to float
  %20 = extractelement <8 x half> %1, i64 3
  %21 = fpext half %20 to float
  %22 = tail call float @llvm.fmuladd.f32(float %19, float %21, float %17)
  %23 = extractelement <8 x half> %0, i64 4
  %24 = fpext half %23 to float
  %25 = extractelement <8 x half> %1, i64 4
  %26 = fpext half %25 to float
  %27 = tail call float @llvm.fmuladd.f32(float %24, float %26, float %22)
  %28 = extractelement <8 x half> %0, i64 5
  %29 = fpext half %28 to float
  %30 = extractelement <8 x half> %1, i64 5
  %31 = fpext half %30 to float
  %32 = tail call float @llvm.fmuladd.f32(float %29, float %31, float %27)
  %33 = extractelement <8 x half> %0, i64 6
  %34 = fpext half %33 to float
  %35 = extractelement <8 x half> %1, i64 6
  %36 = fpext half %35 to float
  %37 = tail call float @llvm.fmuladd.f32(float %34, float %36, float %32)
  %38 = extractelement <8 x half> %0, i64 7
  %39 = fpext half %38 to float
  %40 = extractelement <8 x half> %1, i64 7
  %41 = fpext half %40 to float
  %42 = tail call float @llvm.fmuladd.f32(float %39, float %41, float %37)
  ret float %42
}
 
; Function Attrs: mustprogress nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare float @llvm.fmuladd.f32(float, float, float) #1
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef float @dot_float(<4 x float> noundef %0, <4 x float> noundef %1) local_unnamed_addr #0 {
  %3 = extractelement <4 x float> %0, i64 0
  %4 = extractelement <4 x float> %1, i64 0
  %5 = fmul <4 x float> %0, %1
  %6 = extractelement <4 x float> %5, i64 1
  %7 = tail call float @llvm.fmuladd.f32(float %3, float %4, float %6)
  %8 = extractelement <4 x float> %0, i64 2
  %9 = extractelement <4 x float> %1, i64 2
  %10 = tail call float @llvm.fmuladd.f32(float %8, float %9, float %7)
  %11 = extractelement <4 x float> %0, i64 3
  %12 = extractelement <4 x float> %1, i64 3
  %13 = tail call float @llvm.fmuladd.f32(float %11, float %12, float %10)
  ret float %13
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef double @dot_double(<2 x double> noundef %0, <2 x double> noundef %1) local_unnamed_addr #0 {
  %3 = extractelement <2 x double> %0, i64 0
  %4 = extractelement <2 x double> %1, i64 0
  %5 = fmul <2 x double> %0, %1
  %6 = extractelement <2 x double> %5, i64 1
  %7 = tail call double @llvm.fmuladd.f64(double %3, double %4, double %6)
  ret double %7
}
 
; Function Attrs: mustprogress nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare double @llvm.fmuladd.f64(double, double, double) #1

Ovšem po dalších, zejména -ffast-math je výsledek mnohem lepší – provádí skutečně operace nad celými vektory:

; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(none) uwtable
define dso_local nofpclass(nan inf) float @dot_fp16(<8 x half> noundef nofpclass(nan inf) %0, <8 x half> noundef nofpclass(nan inf) %1) local_unnamed_addr #0 {
  %3 = fpext <8 x half> %0 to <8 x float>
  %4 = fpext <8 x half> %1 to <8 x float>
  %5 = fmul fast <8 x float> %4, %3
  %6 = tail call fast float @llvm.vector.reduce.fadd.v8f32(float 0.000000e+00, <8 x float> %5)
  ret float %6
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(none) uwtable
define dso_local nofpclass(nan inf) float @dot_float(<4 x float> noundef nofpclass(nan inf) %0, <4 x float> noundef nofpclass(nan inf) %1) local_unnamed_addr #0 {
  %3 = fmul fast <4 x float> %1, %0
  %4 = tail call fast float @llvm.vector.reduce.fadd.v4f32(float 0.000000e+00, <4 x float> %3)
  ret float %4
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind willreturn memory(none) uwtable
define dso_local nofpclass(nan inf) double @dot_double(<2 x double> noundef nofpclass(nan inf) %0, <2 x double> noundef nofpclass(nan inf) %1) local_unnamed_addr #0 {
  %3 = fmul fast <2 x double> %1, %0
  %4 = shufflevector <2 x double> %3, <2 x double> poison, <2 x i32> <i32 1, i32 poison>
  %5 = fadd fast <2 x double> %3, %4
  %6 = extractelement <2 x double> %5, i64 0
  ret double %6
}
 
; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare float @llvm.vector.reduce.fadd.v8f32(float, <8 x float>) #1
 
; Function Attrs: nocallback nofree nosync nounwind speculatable willreturn memory(none)
declare float @llvm.vector.reduce.fadd.v4f32(float, <4 x float>) #1

17. Příloha A: seznam doposud popsaných instrukcí používaných v LLVM IR

V tabulce vypsané pod tímto odstavcem jsou vypsány všechny doposud popsané a použité instrukce LLVM IR:

18. Příloha B: Makefile soubor pro překlad všech demonstračních příkladů

Všechny demonstrační příklady využívající překladač Clang, které byly použity v dnešním článku i ve všech článcích předchozích, je možné přeložit do mezijazyka LLVM IR s využitím souboru Makefile, jehož obsah je vypsán pod tímto odstavcem:

CC=clang
 
outputs := noop.ll noop_no_opt.ll noop_wasm.ll noop_aarch64.ll \
           add_unsigned.ll add_unsigned_no_opt.ll \
           add_signed.ll numeric_types.ll \
           arith_operators.ll arith_operators_float.ll arith_operators_fp16.ll \
           comparison_operators.ll comparison_operators_float.ll comparison_operators_fp16.ll \
           branching_1.ll branching_2.ll pointers_1.ll pointers_2.ll \
           add_arrays_1.ll add_arrays_2.ll \
           fibonacci.ll \
           numeric_conversions_1.ll numeric_conversions_2.ll numeric_conversions_3.ll \
           switch_1.ll switch_2.ll switch_3.ll switch_4.ll switch_5.ll switch_6.ll \
           array_set_int_1.ll array_set_int_2.ll array_get_int.ll \
           array_sum_int_1.ll array_sum_int_2.ll \
           bitwise_operators.ll remainder.ll \
           goto.ll stack.ll select.ll \
           simd_add_float.ll simd_add_i8x16.ll simd_add_i8x32.ll simd_add_integers.ll \
           simd_dot_product.ll simd_dot_product_int.ll simd_int_arithmetic.ll simd_sqrt.ll \
           simd_operators_arith.ll simd_operators_comparison.ll \
           simd_add_vector_sizes.ll simd_add_vector_sizes_avx.ll simd_add_vector_sizes_avx512.ll
 
all:    $(outputs)
 
clean:
        rm -f *.ll
 
.PHONY: all clean
 
 
%.ll:   %.c
        $(CC) -Os -S -emit-llvm $< -o $@
 
add_unsigned_no_opt.ll: add_unsigned.c
        $(CC) -S -emit-llvm $< -o $@
 
noop_no_opt.ll: noop.c
        $(CC) -S -emit-llvm $< -o $@
 
noop_wasm.ll:   noop.c
        $(CC) -Os -S -emit-llvm --target=wasm32 $< -o $@
 
noop_aarch64.ll:        noop.c
        $(CC) -Os -S -emit-llvm --target=aarch64 $< -o $@
 
array_set_int_1.ll:     array_set_int_1.c
        $(CC) -Os -S -mno-sse -emit-llvm $< -o $@
 
array_set_int_2.ll:     array_set_int_2.c
        $(CC) -Os -S -mno-sse -emit-llvm $< -o $@
 
array_sum_int_1.ll:     array_sum_int_1.c
        $(CC) -Os -S -mno-sse -emit-llvm $< -o $@
 
array_sum_int_2.ll:     array_sum_int_2.c
        $(CC) -Os -S -mno-sse -emit-llvm $< -o $@
 
simd_add_vector_sizes_avx.ll:   simd_add_vector_sizes.c
        $(CC) -Os -S -mavx -emit-llvm $< -o $@
 
simd_add_vector_sizes_avx512.ll:        simd_add_vector_sizes.c
        $(CC) -Os -S -mavx512f -emit-llvm $< -o $@

Pro překlad všech demonstračních příkladů postačuje zadat příkaz:

$ make

Pro smazání všech vytvářených souborů s LLVM IR (ty mají koncovku .ll) použijte příkaz:

$ make clean

19. Repositář s demonstračními příklady

Demonstrační příklady, s nimiž jsme se v předchozích článcích i v dnešním článku seznámili a které jsou určeny pro překlad s využitím Clangu, jsou dostupné, jak je v tomto seriálu zvykem, na GitHubu. V tabulce níže jsou uvedeny odkazy na jednotlivé zdrojové kódy psané v jazyku C i soubory v mezijazyku LLVM IR získané překladem Clangem:

20. Odkazy na Internetu

1. Is intermediate representation (such as bytecodes or .net IL) still an advantage?
   https://stackoverflow.com/qu­estions/35061333/is-intermediate-representation-such-as-bytecodes-or-net-il-still-an-advantage
2. Intermediate Representation vs Byte Code
   https://cs.stackexchange.com/qu­estions/163398/intermedia­te-representation-vs-byte-code
3. Getting the intermediate representation in gcc
   https://forum.osdev.org/vi­ewtopic.php?t=22845&sid=11f6e77­d24bda7fcc2c9ef6a5be4e6b2
4. Intermediate Representations
   https://www.cs.cornell.edu/cou­rses/cs4120/2023sp/notes/ir/
5. Why do we use intermediate representations / languages?
   https://mortoray.com/why-we-use-intermediate-representations/
6. Unwrapping intermediate representations
   https://mortoray.com/unwrapping-intermediate-representations/
7. Understanding Python Code Flow From Source to Execution
   https://medium.com/@azan96593/un­derstanding-python-code-flow-from-source-to-execution-ebeea870ef83
8. Why most compilers use AST, instead generate IR directly?
   https://stackoverflow.com/qu­estions/60870622/why-most-compilers-use-ast-instead-generate-ir-directly#60902159
9. A Gentle Introduction to LLVM IR
   https://mcyoung.xyz/2023/08/01/llvm-ir/
10. Why does the compiler need the intermediate representations for link time optimization?
    https://stackoverflow.com/qu­estions/75586563/why-does-the-compiler-need-the-intermediate-representations-for-link-time-optimi
11. pyrefact na PyPi
    https://pypi.org/project/pyrefact/
12. Repositář projektu pyrefact
    https://github.com/OlleLin­dgren/pyrefact
13. pyrefact jako plugin do VSCode
    https://marketplace.visual­studio.com/items?itemName=o­lleln.pyrefact
14. pyrefact-vscode-extension (repositář)
    https://github.com/OlleLin­dgren/pyrefact-vscode-extension
15. Best Python Refactoring Tools for 2023
    https://www.developer.com/lan­guages/python/best-python-refactoring-tools/
16. Python Refactoring: Techniques, Tools, and Best Practices
    https://www.codesee.io/learning-center/python-refactoring
17. Lexikální a syntaktická analýza zdrojových kódů programovacího jazyka Python
    https://www.root.cz/clanky/lexikalni-a-syntakticka-analyza-zdrojovych-kodu-programovaciho-jazyka-python/
18. Lexikální a syntaktická analýza zdrojových kódů programovacího jazyka Python (2.část)
    https://www.root.cz/clanky/lexikalni-a-syntakticka-analyza-zdrojovych-kodu-programovaciho-jazyka-python-2-cast/
19. Lexikální a syntaktická analýza zdrojových kódů programovacího jazyka Python (3.část)
    https://www.root.cz/clanky/lexikalni-a-syntakticka-analyza-zdrojovych-kodu-programovaciho-jazyka-python-3-cast/
20. Lexikální a syntaktická analýza zdrojových kódů jazyka Python (4.část)
    https://www.root.cz/clanky/lexikalni-a-syntakticka-analyza-zdrojovych-kodu-jazyka-python-4-cast/
21. Knihovna LibCST umožňující snadnou modifikaci zdrojových kódů Pythonu
    https://www.root.cz/clanky/knihovna-libcst-umoznujici-snadnou-modifikaci-zdrojovych-kodu-pythonu/
22. LibCST – dokumentace
    https://libcst.readthedoc­s.io/en/latest/index.html
23. libCST na PyPi
    https://pypi.org/project/libcst/
24. libCST na GitHubu
    https://github.com/Instagram/LibCST
25. Inside The Python Virtual Machine
    https://leanpub.com/insidet­hepythonvirtualmachine
26. module-py_compile
    https://docs.python.org/3­.8/library/py_compile.html
27. Given a python .pyc file, is there a tool that let me view the bytecode?
    https://stackoverflow.com/qu­estions/11141387/given-a-python-pyc-file-is-there-a-tool-that-let-me-view-the-bytecode
28. The structure of .pyc files
    https://nedbatchelder.com/blog/200804/the_str­ucture_of_pyc_files.html
29. Python Bytecode: Fun With Dis
    http://akaptur.github.io/blog/2013/08/14/pyt­hon-bytecode-fun-with-dis/
30. Python's Innards: Hello, ceval.c!
    http://tech.blog.aknin.na­me/category/my-projects/pythons-innards/
31. Golang Compilation and Execution
    https://golangtutorial.com/golang-compilation-and-execution/
32. Mezijazyk (Wikipedie)
    https://cs.wikipedia.org/wi­ki/Mezijazyk
33. The LLVM Compiler Infrastructure
    https://www.llvm.org/
34. GCC internals
    https://gcc.gnu.org/online­docs/gccint/index.html
35. GCC Developer Options
    https://gcc.gnu.org/online­docs/gcc/Developer-Options.html
36. What is Gimple?
    https://mschiralli1.wordpres­s.com/2024/12/01/what-is-gimple/
37. The Conceptual Structure of GCC
    https://www.cse.iitb.ac.in/grc/in­tdocs/gcc-conceptual-structure.html
38. Open Source ByteCode Libraries in Java
    http://java-source.net/open-source/bytecode-libraries
39. ASM Home page
    http://asm.ow2.org/
40. Seznam nástrojů využívajících projekt ASM
    http://asm.ow2.org/users.html
41. ObjectWeb ASM (Wikipedia)
    http://en.wikipedia.org/wi­ki/ObjectWeb_ASM
42. Java Bytecode BCEL vs ASM
    http://james.onegoodcooki­e.com/2005/10/26/java-bytecode-bcel-vs-asm/
43. BCEL Home page
    http://commons.apache.org/bcel/
44. Byte Code Engineering Library (před verzí 5.0)
    http://bcel.sourceforge.net/
45. Byte Code Engineering Library (verze >= 5.0)
    http://commons.apache.org/pro­per/commons-bcel/
46. BCEL Manual
    http://commons.apache.org/bcel/ma­nual.html
47. Byte Code Engineering Library (Wikipedia)
    http://en.wikipedia.org/wiki/BCEL
48. BCEL Tutorial
    http://www.smfsupport.com/sup­port/java/bcel-tutorial!/
49. Bytecode Engineering
    http://book.chinaunix.net/spe­cial/ebook/Core_Java2_Volu­me2AF/0131118269/ch13lev1sec6­.html
50. Bytecode Outline plugin for Eclipse (screenshoty + info)
    http://asm.ow2.org/eclipse/index.html
51. Javassist
    http://www.jboss.org/javassist/
52. Byteman
    http://www.jboss.org/byteman
53. Java programming dynamics, Part 7: Bytecode engineering with BCEL
    http://www.ibm.com/develo­perworks/java/library/j-dyn0414/
54. The Java^TM Virtual Machine Specification, Second Edition
    http://java.sun.com/docs/bo­oks/jvms/second_edition/html/VMSpec­TOC.doc.html
55. The class File Format
    http://java.sun.com/docs/bo­oks/jvms/second_edition/html/Clas­sFile.doc.html
56. javap – The Java Class File Disassembler
    http://docs.oracle.com/ja­vase/1.4.2/docs/tooldocs/win­dows/javap.html
57. javap-java-1.6.0-openjdk(1) – Linux man page
    http://linux.die.net/man/1/javap-java-1.6.0-openjdk
58. Using javap
    http://www.idevelopment.in­fo/data/Programming/java/mis­cellaneous_java/Using_javap­.html
59. Examine class files with the javap command
    http://www.techrepublic.com/ar­ticle/examine-class-files-with-the-javap-command/5815354
60. Abstract syntax tree
    https://en.wikipedia.org/wi­ki/Abstract_syntax_tree
61. Lexical analysis
    https://en.wikipedia.org/wi­ki/Lexical_analysis
62. Parser
    https://en.wikipedia.org/wi­ki/Parsing#Parser
63. Parse tree
    https://en.wikipedia.org/wi­ki/Parse_tree
64. Derivační strom
    https://cs.wikipedia.org/wi­ki/Deriva%C4%8Dn%C3%AD_strom
65. Python doc: ast — Abstract Syntax Trees
    https://docs.python.org/3/li­brary/ast.html
66. Python doc: tokenize — Tokenizer for Python source
    https://docs.python.org/3/li­brary/tokenize.html
67. SymbolTable
    https://docs.python.org/3­.8/library/symtable.html
68. 5 Amazing Python AST Module Examples
    https://www.pythonpool.com/python-ast/
69. Intro to Python ast Module
    https://medium.com/@wshanshan/intro-to-python-ast-module-bbd22cd505f7
70. Golang AST Package
    https://golangdocs.com/golang-ast-package
71. AP8, IN8 Regulární jazyky
    http://statnice.dqd.cz/home:inf:ap8
72. AP9, IN9 Konečné automaty
    http://statnice.dqd.cz/home:inf:ap9
73. AP10, IN10 Bezkontextové jazyky
    http://statnice.dqd.cz/home:inf:ap10
74. AP11, IN11 Zásobníkové automaty, Syntaktická analýza
    http://statnice.dqd.cz/home:inf:ap11
75. Introduction to YACC
    https://www.geeksforgeeks­.org/introduction-to-yacc/
76. Introduction of Lexical Analysis
    https://www.geeksforgeeks­.org/introduction-of-lexical-analysis/?ref=lbp
77. Write your own filter
    http://pygments.org/docs/fil­terdevelopment/
78. Write your own lexer
    http://pygments.org/docs/le­xerdevelopment/
79. Write your own formatter
    http://pygments.org/docs/for­matterdevelopment/
80. Compiler Construction/Lexical analysis
    https://en.wikibooks.org/wi­ki/Compiler_Construction/Le­xical_analysis
81. Compiler Design – Lexical Analysis
    https://www.tutorialspoin­t.com/compiler_design/com­piler_design_lexical_analy­sis.htm
82. Lexical Analysis – An Intro
    https://www.scribd.com/do­cument/383765692/Lexical-Analysis
83. Python AST Visualizer
    https://github.com/pombredanne/python-ast-visualizer
84. What is an Abstract Syntax Tree
    https://blog.bitsrc.io/what-is-an-abstract-syntax-tree-7502b71bde27
85. Why is AST so important
    https://medium.com/@obernar­dovieira/why-is-ast-so-important-b1e7d6c29260
86. Emily Morehouse-Valcarcel – The AST and Me – PyCon 2018
    https://www.youtube.com/wat­ch?v=XhWvz4dK4ng
87. Python AST Parsing and Custom Linting
    https://www.youtube.com/wat­ch?v=OjPT15y2EpE
88. Chase Stevens – Exploring the Python AST Ecosystem
    https://www.youtube.com/wat­ch?v=Yq3wTWkoaYY
89. Full Grammar specification
    https://docs.python.org/3/re­ference/grammar.html
90. Playing with GCC’s GIMPLE: How to Generate, Save, and Modify Intermediate Code (Tutorial + Examples)
    https://www.tutorialpedia­.org/blog/playing-with-gcc-s-intermediate-gimple-format/
91. A Deep Dive Into LLVM IR
    https://medium.com/@abdulraheembeigh/a-deep-dive-into-llvm-ir-b5aa81beb474
92. Nulová operace
    https://cs.wikipedia.org/wi­ki/Nulov%C3%A1_operace
93. NOP (code)
    https://en.wikipedia.org/wi­ki/NOP_(code)
94. LLVM Bitcode File Format
    https://llvm.org/docs/Bit­CodeFormat.html
95. LLVM IR Language Reference
    https://deepwiki.com/llvm-mirror/llvm/2.1-llvm-ir-language-reference
96. Ackermann function
    https://en.wikipedia.org/wi­ki/Ackermann_function
97. Primitive recursive function
    https://en.wikipedia.org/wi­ki/Primitive_recursive_fun­ction
98. Užitečné rozšíření GCC: podpora SIMD (vektorových) instrukcí
    https://www.root.cz/clanky/uzitecne-rozsireni-gcc-podpora-simd-vektorovych-instrukci/
99. Užitečné rozšíření GCC – podpora SIMD (vektorových) instrukcí: nedostatky technologie
    https://www.root.cz/clanky/uzitecne-rozsireni-gcc-podpora-simd-vektorovych-instrukci-nedostatky-technologie/
100. Podpora SIMD (vektorových) instrukcí na RISCových procesorech
     https://www.root.cz/clanky/podpora-simd-vektorovych-instrukci-na-riscovych-procesorech/
101. Podpora SIMD operací v GCC s využitím intrinsic pro nízkoúrovňové optimalizace
     https://www.root.cz/clanky/podpora-simd-operaci-v-gcc-s-vyuzitim-intrinsic-pro-nizkourovnove-optimalizace/