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

Obsah

1. Překlad jazykové konstrukce goto

2. Podmínky a instrukce select

3. Rekurzivní volání funkcí

4. Manipulace s poli

5. Přečtení hodnoty prvku z pole

6. Modifikace hodnoty prvku v poli

7. Modifikace prvků v poli přes ukazatel

8. Instrukce LLVM určené pro manipulaci s prvky pole

9. Výpočet součtu prvků pole

10. Způsob překladu bez použití vektorových instrukcí

11. Doplnění instrukčního souboru: co nebylo popsáno minule

12. Bitové operace součtu, součinu a exkluzivního součtu

13. Výpočet zbytku po dělení

14. Operace s hodnotami s plovoucí řádovou čárkou s poloviční přesností

15. Aritmetické operace s hodnotami typu half float

16. Porovnání hodnot typu half float

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. Překlad jazykové konstrukce goto

V prvním příkladu, který si v dnešním článku ukážeme, prozkoumáme, jakou sekvencí instrukcí mezikódu je realizována konstrukce goto. Jedná se o nepodmíněný skok, takže se dá předpokládat, že v LLMV IR bude použita „univerzální“ instrukce br (branch):

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();
}

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

; Function Attrs: nounwind optsize uwtable
define dso_local void @bar(i32 noundef %0) local_unnamed_addr #0 {
  %2 = icmp sgt i32 %0, 0
  br i1 %2, label %4, label %3
 
3:                                                ; preds = %1
  tail call void @positive_case() #2
  br label %5

4:                                                ; preds = %1
  tail call void @negative_case() #2
  br label %5

5:                                                ; preds = %4, %3
  tail call void @finish() #2
  ret void
}

2. Podmínky a instrukce select

Ve skutečnosti se v mezikódu LLVM IR můžeme setkat ještě s jednou zajímavou instrukcí. Tato instrukce se jmenuje select a slouží nikoli k rozvětvení na základě podmínky, ale k výběru hodnoty, taktéž na základě podmínky. Ukažme si jednoduchý příklad, který v LLVM IR vede k použití této instrukce:

int decision(int a) {
  if (a < 0) {
    return 42;
  }
  return 9999;
}

Teoreticky by bylo možné tuto funkci přeložit s využitím podmíněného skoku atd., ovšem v mezikódu namísto toho nalezneme právě instrukci select. Povšimněte si, jak se používá – na základě podmínky (první operand) se vybere buď hodnota druhá nebo třetí. Všechny hodnoty jsou v LLVM IR doplněny o typy:

; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef range(i32 42, 10000) i32 @decision(i32 noundef %0) local_unnamed_addr #0 {
  %2 = icmp slt i32 %0, 0
  %3 = select i1 %2, i32 42, i32 9999
  ret i32 %3
}

Naši tabulku instrukcí LLVM IR tedy rozšíříme o:

3. Rekurzivní volání funkcí

V LLVM IR je umožněno, aby nějaká funkce volala sebe samu. Pro tento účel se používá již popsaná instrukce call popř. její „koncová“ varianta tail call. Ukažme si celý postup na známé Ackermannově funkci, která není primitivně rekurzivní:

unsigned int ackermann(unsigned int m, unsigned int n) {
    if (m == 0)
        return n + 1;
    else if (n == 0)
        return ackermann(m - 1, 1);
    else
        return ackermann(m - 1, ackermann(m, n - 1));
}

Výsledek překladu do mezikódu LLVM IR dopadne následovně. Připomínám, že jsou povoleny optimalizace na velikost výsledného kódu:

; Function Attrs: nofree nosync nounwind optsize memory(none) uwtable
define dso_local i32 @ackermann(i32 noundef %0, i32 noundef %1) local_unnamed_addr #0 {
  %3 = icmp eq i32 %0, 0
  br i1 %3, label %4, label %7
 
4:                                                ; preds = %11, %2
  %5 = phi i32 [ %1, %2 ], [ %12, %11 ]
  %6 = add i32 %5, 1
  ret i32 %6
 
7:                                                ; preds = %2, %11
  %8 = phi i32 [ %12, %11 ], [ %1, %2 ]
  %9 = phi i32 [ %13, %11 ], [ %0, %2 ]
  %10 = icmp eq i32 %8, 0
  br i1 %10, label %11, label %15
 
11:                                               ; preds = %7, %15
  %12 = phi i32 [ %17, %15 ], [ 1, %7 ]
  %13 = add i32 %9, -1
  %14 = icmp eq i32 %13, 0
  br i1 %14, label %4, label %7
 
15:                                               ; preds = %7
  %16 = add i32 %8, -1
  %17 = tail call i32 @ackermann(i32 noundef %9, i32 noundef %16) #1
  br label %11
}

4. Manipulace s poli

Mezikód LLVM IR obsahuje i instrukce (resp. přesněji řečeno jednu instrukci) pro manipulaci s poli (array). Od mezikódu vyžadujeme dvě operace: přečtení i-tého prvku pole a zápis do i-tého prvku pole, samozřejmě za předpokladu, že je pole měnitelné (mutable). Tyto operace sice přímo podporovány nejsou, ovšem v LLVM IR je k dispozici instrukce, která na základě ukazatele na pole a indexu prvku vypočte a vrátí ukazatel na tento prvek. To je plně dostačující, protože čtení a zápisy přes ukazatel již známe – k tomuto účelu se používají instrukce load a store, které jsme si popsali již předminule v osmé kapitole. V navazujících kapitolách si ukážeme, jak se do LLVM IR přeloží operace s poli prováděné buď indexováním prvků nebo přístupem k prvkům přes ukazatel.

5. Přečtení hodnoty prvku z pole

První (a dosti základní) operací, která se s poli provádí, je přečtení hodnoty prvku pole, přičemž prvek je identifikován svým indexem. Programovací jazyk C přitom žádným způsobem nekontroluje meze indexů. Můžeme tedy naprogramovat obecnou funkci, která z pole hodnot typu celé číslo vrátí prvek s indexem index:

unsigned int set(unsigned int *array, int index) {
    return array[index];
}

Překlad do mezikódu LLVM IR bude vypadat takto:

; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(argmem: read) uwtable
define dso_local i32 @set(ptr nocapture noundef readonly %0, i32 noundef %1) local_unnamed_addr #0 {
  %3 = sext i32 %1 to i64
  %4 = getelementptr inbounds i32, ptr %0, i64 %3
  %5 = load i32, ptr %4, align 4, !tbaa !3
  ret i32 %5
}

V mezikódu se nejdříve 32bitový index rozšíří na 64 bitů (se znaménkem, takže se korektně řeší i záporné indexy) a dále se zavolá instrukce nazvaná getelementptr. U této instrukce je specifikován typ prvků pole, adresa pole (což je vlastně adresa prvního prvku v poli) a 64bitový index prvku. Výsledkem je ukazatel na tento prvek, takže bylo možné pokračovat instrukcí load, kterou již dobře známe.

6. Modifikace hodnoty prvku v poli

Druhou operací, kterou musí LLVM IR při práci s poli nějakým způsobem podporovat, je modifikace (zápis) prvku pole; samozřejmě za předpokladu, že je pole modifikovatelné. Vyzkoušejme si, jakým způsobem Clang přeloží následující funkci, která nastaví všechny prvky pole (resp. size prvků) na hodnotu value. První implementace algoritmu používá při přístupu k prvkům pole běžné indexování:

void set(unsigned int *array, int size, unsigned int value) {
    int i;
    for (i = 0; i < size; i++) {
        array[i] = value;
    }
}

Po překladu tohoto demonstračního příkladu do mezikódu LLVM IR je opět patrné, že se použila instrukce getelementptr. Zápis prvků pole je proveden ve smyčce, i když LLVM IR podporuje i vektorové operace (s těmi se podrobněji seznámíme příště):

; Function Attrs: nofree norecurse nosync nounwind optsize memory(argmem: write) uwtable
define dso_local void @set(ptr nocapture noundef writeonly %0, i32 noundef %1, i32 noundef %2) local_unnamed_addr #0 {
  %4 = icmp sgt i32 %1, 0
  br i1 %4, label %5, label %12
 
5:                                                ; preds = %3
  %6 = zext nneg i32 %1 to i64
  br label %7
 
7:                                                ; preds = %5, %7
  %8 = phi i64 [ 0, %5 ], [ %10, %7 ]
  %9 = getelementptr inbounds nuw i32, ptr %0, i64 %8
  store i32 %2, ptr %9, align 4, !tbaa !3
  %10 = add nuw nsw i64 %8, 1
  %11 = icmp eq i64 %10, %6
  br i1 %11, label %12, label %7, !llvm.loop !7
 
12:                                               ; preds = %7, %3
  ret void
}

7. Modifikace prvků v poli přes ukazatel

Demonstrační příklad z předchozí kapitoly můžeme snadno upravit tak, aby se namísto operátoru indexování prováděl zápis přes ukazatel. V dávných dobách se jednalo o rychlejší řešení a proto bude zajímavé zjistit, jak se změní LLVM IR pro upravenou funkci set:

void set(unsigned int *array, int size, unsigned int value) {
    unsigned int *p = array;
    int           i;
 
    for (i = 0; i < size; i++) {
        *p++ = value;
    }
}

Výsledek překladu do bajtkódu:

; Function Attrs: nofree norecurse nosync nounwind optsize memory(argmem: write) uwtable
define dso_local void @set(ptr nocapture noundef writeonly %0, i32 noundef %1, i32 noundef %2) local_unnamed_addr #0 {
  %4 = icmp sgt i32 %1, 0
  br i1 %4, label %5, label %11
 
5:                                                ; preds = %3, %5
  %6 = phi i32 [ %9, %5 ], [ 0, %3 ]
  %7 = phi ptr [ %8, %5 ], [ %0, %3 ]
  %8 = getelementptr inbounds nuw i8, ptr %7, i64 4
  store i32 %2, ptr %7, align 4, !tbaa !3
  %9 = add nuw nsw i32 %6, 1
  %10 = icmp eq i32 %9, %1
  br i1 %10, label %11, label %5, !llvm.loop !7
 
11:                                               ; preds = %5, %3
  ret void
}

Výsledek je skutečně nepatrně kratší, protože chybí konverze indexu na 64bitovou hodnotu a přímý skok na začátek smyčky (ten by ovšem byl stejně odstraněn v dalších krocích optimalizace):

  %4 = icmp sgt i32 %1, 0                                   %4 = icmp sgt i32 %1, 0
  br i1 %4, label %5, label %12                             br i1 %4, label %5, label %11
                                                        
5:                                                       5:
  %6 = zext nneg i32 %1 to i64
  br label %7
                                                       %6 = phi i32 [ %9, %5 ], [ 0, %3 ]
7:                                                          %7 = phi ptr [ %8, %5 ], [ %0, %3 ]
  %8 = phi i64 [ 0, %5 ], [ %10, %7 ]
  %9 = getelementptr inbounds nuw i32, ptr %0, i64 %8       %8 = getelementptr inbounds nuw i8, ptr %7, i64 4
  store i32 %2, ptr %9, align 4, !tbaa !3                   store i32 %2, ptr %7, align 4, !tbaa !3
  %10 = add nuw nsw i64 %8, 1                               %9 = add nuw nsw i32 %6, 1
  %11 = icmp eq i64 %10, %6                                 %10 = icmp eq i32 %9, %1
  br i1 %11, label %12, label %7, !llvm.loop !7             br i1 %10, label %11, label %5, !llvm.loop !7
                                                    
12:                                                     11:
  ret void                                                ret void

8. Instrukce LLVM určené pro manipulaci s prvky pole

Ve všech třech demonstračních příkladech, která četly nebo zapisovaly prvky do pole, se používala jediná nová instrukce getelementptr:

Typické použití této instrukce při čtení hodnoty prvku:

  %x = getelementptr inbounds typ, ukazatel, index
  %y = load typ, ptr %x

Typické použití instrukce při modifikaci prvku:

  %x = getelementptr inbounds typ, ukazatel, index
  store typ hodnota, ptr ukazatel

9. Výpočet součtu prvků pole

Ještě se pro zajímavost podívejme na způsob překladu funkcí, které provedou součet size prvků v poli. První implementace výpočtu bude opět používat operátor indexování:

unsigned int sum(unsigned int *array, int size) {
    unsigned int s = 0;
    int          i;
 
    for (i = 0; i < size; i++) {
        s += array[i];
    }
    return s;
}

Druhá varianta téže funkce naproti tomu přistupuje k prvkům přes ukazatel:

unsigned int sum(unsigned int *array, int size) {
    unsigned int  s = 0;
    unsigned int *p = array;
    int           i;
 
    for (i = 0; i < size; i++) {
        s += *p++;
    }
    return s;
}

10. Způsob překladu bez použití vektorových instrukcí

Překlad obou demonstračních příkladů z předchozí kapitoly provedeme s vypnutím „vektorizaci“, což se konkrétně na platformě x86(64) provádí přepínačem -mno-sse. Z výsledků je opět patrné použití výše uvedené instrukce getelementptr:

; Function Attrs: nofree norecurse nosync nounwind optsize memory(argmem: read) uwtable
define dso_local i32 @sum(ptr nocapture noundef readonly %0, i32 noundef %1) local_unnamed_addr #0 {
  %3 = icmp sgt i32 %1, 0
  br i1 %3, label %4, label %14
 
4:                                                ; preds = %2
  %5 = zext nneg i32 %1 to i64
  br label %6
 
6:                                                ; preds = %4, %6
  %7 = phi i64 [ 0, %4 ], [ %12, %6 ]
  %8 = phi i32 [ 0, %4 ], [ %11, %6 ]
  %9 = getelementptr inbounds nuw i32, ptr %0, i64 %7
  %10 = load i32, ptr %9, align 4, !tbaa !3
  %11 = add i32 %10, %8
  %12 = add nuw nsw i64 %7, 1
  %13 = icmp eq i64 %12, %5
  br i1 %13, label %14, label %6, !llvm.loop !7
 
14:                                               ; preds = %6, %2
  %15 = phi i32 [ 0, %2 ], [ %11, %6 ]
  ret i32 %15
}

Překlad varianty postavené na přístupu k prvkům polí přes ukazatel:

; Function Attrs: nofree norecurse nosync nounwind optsize memory(argmem: read) uwtable
define dso_local i32 @sum(ptr nocapture noundef readonly %0, i32 noundef %1) local_unnamed_addr #0 {
  %3 = icmp sgt i32 %1, 0
  br i1 %3, label %4, label %13
 
4:                                                ; preds = %2, %4
  %5 = phi i32 [ %11, %4 ], [ 0, %2 ]
  %6 = phi ptr [ %8, %4 ], [ %0, %2 ]
  %7 = phi i32 [ %10, %4 ], [ 0, %2 ]
  %8 = getelementptr inbounds nuw i8, ptr %6, i64 4
  %9 = load i32, ptr %6, align 4, !tbaa !3
  %10 = add i32 %9, %7
  %11 = add nuw nsw i32 %5, 1
  %12 = icmp eq i32 %11, %1
  br i1 %12, label %13, label %4, !llvm.loop !7
 
13:                                               ; preds = %4, %2
  %14 = phi i32 [ 0, %2 ], [ %10, %4 ]
  ret i32 %14
}

Porovnání po instrukcích:

  %3 = icmp sgt i32 %1, 0                                   %3 = icmp sgt i32 %1, 0
  br i1 %3, label %4, label %14                             br i1 %3, label %4, label %13
                                                      
4:                                                        4:
  %5 = zext nneg i32 %1 to i64
  br label %6
 
6:
  %7 = phi i64 [ 0, %4 ], [ %12, %6 ]                       %5 = phi i32 [ %11, %4 ], [ 0, %2 ]
  %8 = phi i32 [ 0, %4 ], [ %11, %6 ]                       %6 = phi ptr [ %8, %4 ], [ %0, %2 ]
                                                            %7 = phi i32 [ %10, %4 ], [ 0, %2 ]
  %9 = getelementptr inbounds nuw i32, ptr %0, i64 %7       %8 = getelementptr inbounds nuw i8, ptr %6, i64 4
  %10 = load i32, ptr %9, align 4, !tbaa !3                 %9 = load i32, ptr %6, align 4, !tbaa !3
  %11 = add i32 %10, %8                                     %10 = add i32 %9, %7
  %12 = add nuw nsw i64 %7, 1                               %11 = add nuw nsw i32 %5, 1
  %13 = icmp eq i64 %12, %5                                 %12 = icmp eq i32 %11, %1
  br i1 %13, label %14, label %6, !llvm.loop !7             br i1 %12, label %13, label %4, !llvm.loop !7
 
14:                                                       13:
  %15 = phi i32 [ 0, %2 ], [ %11, %6 ]                      %14 = phi i32 [ 0, %2 ], [ %10, %4 ]
  ret i32 %15                                               ret i32 %14

11. Doplnění instrukčního souboru: co nebylo popsáno minule

V navazujícím článku se budeme zabývat vektorovými (SIMD) instrukcemi, které LLVM IR taktéž podporuje. Ovšem nejprve musíme dokončit popis „skalárních“ instrukcí, přesněji řečeno instrukcí, které pracují se skalárními operandy. Většinu instrukcí (alespoň těch, které jsou vztaženy k jazyku C) jsme si již popsali, ovšem ještě nám zbývá popis bitových operací, výpočet zbytku po dělení a v neposlední řadě taktéž zpracování hodnot s plovoucí řádovou čárkou s poloviční přesností (half floating point).

12. Bitové operace součtu, součinu a exkluzivního součtu

Programovací jazyk C podporuje provádění bitových operací, což znamená, že tyto operace musí být nějakým způsobem reprezentovány i v mezikódu LLVM IR. Ostatně není nic snadnějšího, než si tyto operace otestovat. Opět použijeme příklad postavený nad makrosystémem jazyka C:

#define AND(type) type and_##type(type x, type y) {return x&y;}
#define OR(type) type or_##type(type x, type y) {return x|y;}
#define XOR(type) type xor_##type(type x, type y) {return x^y;}
 
#define ALL(type) \
    AND(type) \
    OR(type) \
    XOR(type)
 
ALL(int)
ALL(unsigned)

Po expanzi všech maker získáme tento zdrojový kód:

int and_int(int x, int y) {return x&y;}
int or_int(int x, int y) {return x|y;}
int xor_int(int x, int y) {return x^y;}
 
unsigned and_unsigned(unsigned x, unsigned y) {return x&y;}
unsigned or_unsigned(unsigned x, unsigned y) {return x|y;}
unsigned xor_unsigned(unsigned x, unsigned y) {return x^y;}

A po překladu do mezikódu LLVM IR můžeme vidět použití nových instrukcí (plně typovaných):

; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef i32 @and_int(i32 noundef %0, i32 noundef %1) local_unnamed_addr #0 {
  %3 = and i32 %1, %0
  ret i32 %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef i32 @or_int(i32 noundef %0, i32 noundef %1) local_unnamed_addr #0 {
  %3 = or i32 %1, %0
  ret i32 %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef i32 @xor_int(i32 noundef %0, i32 noundef %1) local_unnamed_addr #0 {
  %3 = xor i32 %1, %0
  ret i32 %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef i32 @and_unsigned(i32 noundef %0, i32 noundef %1) local_unnamed_addr #0 {
  %3 = and i32 %1, %0
  ret i32 %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef i32 @or_unsigned(i32 noundef %0, i32 noundef %1) local_unnamed_addr #0 {
  %3 = or i32 %1, %0
  ret i32 %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef i32 @xor_unsigned(i32 noundef %0, i32 noundef %1) local_unnamed_addr #0 {
  %3 = xor i32 %1, %0
  ret i32 %3
}

Všechny tři nové instrukce LLVM IR jsou vypsány v tabulce:

13. Výpočet zbytku po dělení

Při popisu aritmetických operací jsme opomenuli výpočet zbytku po dělení (resp. operaci modulo – což pro záporné operandy nemusí být totéž). Doplníme si tedy i znalosti o této operaci a o způsobu jejího překladu do LLVM IR:

#define REM(type) type remainder_##type(type x, type y) {return x%y;}
 
#define ALL(type) \
    REM(type)
 
ALL(int)
ALL(unsigned)

Výsledek expanze maker:

int remainder_int(int x, int y) {return x%y;}
unsigned remainder_unsigned(unsigned x, unsigned y) {return x%y;}

Překlad do mezikódu LLVM IR:

; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local range(i32 -2147483647, -2147483648) i32 @remainder_int(i32 noundef %0, i32 noundef %1) local_unnamed_addr #0 {
  %3 = srem i32 %0, %1
  ret i32 %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local range(i32 0, -1) i32 @remainder_unsigned(i32 noundef %0, i32 noundef %1) local_unnamed_addr #0 {
  %3 = urem i32 %0, %1
  ret i32 %3
}

Máme tedy dvě nové instrukce, ke kterým ještě přidám instrukci frem, kterou lze v C těžko „vyrobit“:

14. Operace s hodnotami s plovoucí řádovou čárkou s poloviční přesností

Programátoři, kteří se zabývají vývojem v oblasti generativní AI, zpracování přirozeného jazyka, embeddingu a embedding modelů atd., se mohou setkat s nutností zpracování skalárních hodnot či celých vektorů s prvky typu half float (FP16). Důvody jsou zřejmé: pro mnoho účelů rozsah i přesnost hodnot uložených jako half float plně vyhovuje požadavkům řešeného algoritmu a oproti hodnotám single jsou paměťové požadavky poloviční (a v praxi je velký finanční rozdíl v tom, jestli servery vyžadují například 16GB RAM nebo 32GB RAM).

Formát half float, jenž je dnes standardizován v IEEE 754–2008, používá pro ukládání hodnot s plovoucí řádovou čárkou pouhých šestnáct bitů, tj. dva byty. Maximální hodnota je rovna 65504, minimální hodnota (větší než nula) přibližně 5,9×10^-8. Předností tohoto formátu je malá bitová šířka (umožňuje paralelní přenos po interních sběrnicích GPU) a také větší rychlost zpracování základních operací, protože pro tak malou bitovou šířku mantisy je možné některé operace „zadrátovat“ a nepočítat pomocí ALU. Také některé iterativní výpočty (sin, cos, sqrt) mohou být provedeny rychleji, než v případě plnohodnotných typů float a single.

15. Aritmetické operace s hodnotami typu half float

Clang a současně i LLVM IR hodnoty typu half float podporují. Pokusme se tedy zjistit, jaké se vlastně v LLVM IR pro tento účel používají instrukce. Nejprve se zaměříme na základní aritmetické operace, které otestujeme tímto kódem:

#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 ALL(type) \
    NEG(type) \
    ADD(type) \
    SUB(type) \
    MUL(type) \
    DIV(type)
 
ALL(_Float16)

Po expanzi maker preprocesorem získáme tuto pětici funkcí:

_Float16 neg__Float16(_Float16 x) {return -x;}
_Float16 add__Float16(_Float16 x, _Float16 y) {return x+y;}
_Float16 sub__Float16(_Float16 x, _Float16 y) {return x-y;}
_Float16 mul__Float16(_Float16 x, _Float16 y) {return x*y;}
_Float16 div__Float16(_Float16 x, _Float16 y) {return x/y;}

Výsledek překladu do mezikódu LLVM IR:

; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef half @neg__Float16(half noundef %0) local_unnamed_addr #0 {
  %2 = fneg half %0
  ret half %2
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef half @add__Float16(half noundef %0, half noundef %1) local_unnamed_addr #0 {
  %3 = fadd half %0, %1
  ret half %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef half @sub__Float16(half noundef %0, half noundef %1) local_unnamed_addr #0 {
  %3 = fsub half %0, %1
  ret half %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef half @mul__Float16(half noundef %0, half noundef %1) local_unnamed_addr #0 {
  %3 = fmul half %0, %1
  ret half %3
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local noundef half @div__Float16(half noundef %0, half noundef %1) local_unnamed_addr #0 {
  %3 = fdiv half %0, %1
  ret half %3
}

Z tohoto výpisu je patrné, že se používají již známé instrukce pro práci s hodnotami s plovoucí řádovou čárkou. Pouze se změnil identifikátor typu (modifikátor) zapsaný za jménem instrukce:

16. Porovnání hodnot typu half float

Podobným způsobem můžeme prozkoumat instrukce použité při porovnání dvou hodnot typu half float. K tomuto účelu opět využijeme variantu příkladu z předchozího článku:

#define EQ(type) int eq_##type(type x, type y) {return x==y;}
#define NE(type) int ne_##type(type x, type y) {return x!=y;}
#define LT(type) int lt_##type(type x, type y) {return x<y;}
#define LE(type) int le_##type(type x, type y) {return x<=y;}
#define GT(type) int gt_##type(type x, type y) {return x>y;}
#define GE(type) int ge_##type(type x, type y) {return x>=y;}
 
#define ALL(type) \
    EQ(type) \
    NE(type) \
    LT(type) \
    LE(type) \
    GT(type) \
    GE(type)
 
ALL(_Float16)

Výsledek činnosti preprocesoru jazyka C:

int eq__Float16(_Float16 x, _Float16 y) {return x==y;}
int ne__Float16(_Float16 x, _Float16 y) {return x!=y;}
int lt__Float16(_Float16 x, _Float16 y) {return x<y;}
int le__Float16(_Float16 x, _Float16 y) {return x<=y;}
int gt__Float16(_Float16 x, _Float16 y) {return x>y;}
int ge__Float16(_Float16 x, _Float16 y) {return x>=y;}

Překlad do LLVM IR:

; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local range(i32 0, 2) i32 @eq__Float16(half noundef %0, half noundef %1) local_unnamed_addr #0 {
  %3 = fcmp oeq half %0, %1
  %4 = zext i1 %3 to i32
  ret i32 %4
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local range(i32 0, 2) i32 @ne__Float16(half noundef %0, half noundef %1) local_unnamed_addr #0 {
  %3 = fcmp une half %0, %1
  %4 = zext i1 %3 to i32
  ret i32 %4
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local range(i32 0, 2) i32 @lt__Float16(half noundef %0, half noundef %1) local_unnamed_addr #0 {
  %3 = fcmp olt half %0, %1
  %4 = zext i1 %3 to i32
  ret i32 %4
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local range(i32 0, 2) i32 @le__Float16(half noundef %0, half noundef %1) local_unnamed_addr #0 {
  %3 = fcmp ole half %0, %1
  %4 = zext i1 %3 to i32
  ret i32 %4
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local range(i32 0, 2) i32 @gt__Float16(half noundef %0, half noundef %1) local_unnamed_addr #0 {
  %3 = fcmp ogt half %0, %1
  %4 = zext i1 %3 to i32
  ret i32 %4
}
 
; Function Attrs: mustprogress nofree norecurse nosync nounwind optsize willreturn memory(none) uwtable
define dso_local range(i32 0, 2) i32 @ge__Float16(half noundef %0, half noundef %1) local_unnamed_addr #0 {
  %3 = fcmp oge half %0, %1
  %4 = zext i1 %3 to i32
  ret i32 %4
}

Opět je patrné, že se používá již známá instrukce fcmp, ovšem s odlišným modifikátorem typu:

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 v obou č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
 
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 $@

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 (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 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