Obsah
1. Compiler Explorer – až nečekaně užitečný nástroj
2. Překlad zdrojových kódů do assembleru
3. Zkoumání specifických vlastností některých mikroprocesorů
5. Porovnání dvou či více variant překladu
6. Zobrazení bajtkódu u vybraných programovacích jazyků
7. Transformace zdrojového kódu do AST
8. Zobrazení AST v Compiler Exploreru
9. Překlad do mezikódu (intermediate representation)
11. Zajímavosti na konec: detekce memset z programové smyčky a překlad pro osmibitové čipy
12. Seznam podporovaných jazyků
13. Seznam integrovaných překladačů
1. Compiler Explorer – až nečekaně užitečný nástroj
V dnešním článku se, jak již ostatně bylo zmíněno v perexu, seznámíme se zajímavým a mnohdy i velmi užitečným projektem. Tento projekt se jmenuje Compiler Explorer a za jeho vývojem a provozem stojí Matt Godbolt. Jedná se o webovou aplikaci dostupnou na adrese https://godbolt.org/, která dokáže přeložit zdrojové kódy napsané v různých programovacích jazycích buď do assembleru zvoleného mikroprocesoru nebo (pro určité vybrané jazyky) do bajtkódu příslušného virtuálního stroje. Překlad je přitom proveden vybraným překladačem (podle zvoleného jazyka existuje jen jeden překladač nebo i několik desítek překladačů), který je navíc nabízen v různých verzích, takže je například možné porovnat, jak se způsob překladu postupně měnil. V dalších kapitolách si ve stručnosti ukážeme některé způsoby použití tohoto zajímavého nástroje.
Obrázek 1: Úvodní stránka nástroje Compiler Explorer.
Obrázek 2: Compiler Explorer má na straně klienta (tedy prohlížeče) vlastně velmi malé paměťové nároky, dokonce menší, než například samotná stránka Roota a mnohem menší, než stránka s pozastaveným videem na Youtube nebo dokonce samotného Task Manažeru webového prohlížeče :-)
Compiler Explorer si můžete spustit i lokálně s využitím kódu a konfigurace získaného z tohoto repositáře.
2. Překlad zdrojových kódů do assembleru
Již název projektu Compiler Explorer naznačuje, že umožňuje překládat zdrojové kódy napsané v některém z překládaných (kompilovaných) jazyků do assembleru s možností prohlédnutí výsledného vygenerovaného kódu. To je operace, kterou pochopitelně dokáže provést prakticky jakýkoli překladač, ovšem Compiler Explorer programátorům nabízí především velký výběr překládaných programovacích jazyků (včetně C, C++, Rustu a Go) a taktéž velký výběr překladačů, včetně různých verzí těchto překladačů (v případě C a C++ je to GCC, LLVM, MSVC, překlad do WebAssembly apod.). Navíc je nabízeno velké množství cílových platforem, pro které je možné provést překlad, od historických osmibitových mikroprocesorů, až po moderní x86–64, ARMv8 či RISC-V. Ovšem Compiler Explorer uživatelům navíc nabízí možnost specifikovat parametry překladu, tedy většinou zapínat a vypínat optimalizace (prováděné s ohledem na rychlost či velikost cílového strojového kódu), popř. zapínat a vypínat různá rozšíření instrukční sady či určit typ procesoru, což je v současnosti důležité pro všechny tři výše zmíněné platformy: x86–64, ARM a taktéž RISC-V.
Obrázek 3: Takto vypadá překlad zdrojového kódu zapsaného v Rustu (demonstrační příklad s jednoduchým pattern matchingem) do assembleru. Korespondující řádky zdrojového kódu a instrukcí assembleru jsou v tomto případě zvýrazněny odlišnou barvou podkladu.
Poměrně důležitou vlastností Compiler Exploreru je fakt, že se překlad provádí (z pohledu uživatele) na pozadí, a to i v průběhu editace. Je tak možné vlastně „naživo“ vidět, jak se projeví změna algoritmu na efektivitě výsledného strojového kódu. Odpovídající si řádky zdrojového kódu a assembleru jsou přitom zvýrazněny různými barvami, takže je zřejmé, jak se jednotlivé řádky překládají (což pochopitelně nebude vždy zcela funkční, zejména při zapnutí optimalizací).
Dále je možné ve zkoumaných kódech používat různé knihovny. Seznam předinstalovaných knihoven lze najít na adrese https://godbolt.org/admin/libraries.html.
Obrázek 4: Překlad prográmku napsaného v jazyce F# do assembleru x86–64 s využitím překladače dodávaného v .NETu. Povšimněte si, že v tomto konkrétním případě neexistuje vazba mezi řádky zdrojového kódu a assemblerem.
3. Zkoumání specifických vlastností některých mikroprocesorů
Asi nejzajímavější je použití Compiler Exploreru pro zkoumání různých instrukčních sad a jejich rozšíření. Například jsme se na stránkách Roota ve stručnosti seznámili s rozšířením instrukční sady procesorů ARM, které se jmenuje NEON (což je jedna z mnoha variant implementace SIMD – Single Instruction Multiple Data). I na běžném desktopu a bez nutnosti instalace jakéhokoli (cross) překladače je možné zjistit, jak fungují takzvané intrinsic, tedy konstrukce zapsané v jazyku C či C++, které vedou k překladu kódu s využitím právě instrukcí NEON, i když původně C/C++ sémantiku NEONu neobsahuje (tedy neobsahuje možnost specifikovat například požadavek „tento kód ať je vykonán po 16bitových slovech zpracovaných ve čtyřech paralelních ALU“. Viz například NEON Intrinsics Quick Guide:
Obrázek 5: Překlad kódu zapsaného v jazyku C, v němž se využívají „intrinsic“ vektorové instrukční sady NEON.
Obrázek 6: V Compiler Exploreru jsou podporovány i některé méně známé či méně často používané překladače, například tcc.
4. Podpora historických CPU
V Compiler Exploreru jsou nabízeny (typicky pro programovací jazyk C) i překladače některých historických mikroprocesorů. Příkladem je překladač cc65 určený pro známý osmibitový čip MOS 6502 i pro všechny jeho varianty (viz též https://cc65.github.io/doc/cc65.html). Jedná se o poměrně dobrou pomůcku při vysvětlování, v čem se tyto starší mikroprocesory odlišují od jejich moderních protějšků. Příkladem je nutnost rozkladu operací s 16bitovými a 32bitovými operandy (nemluvě o číslech s plovoucí řádovou čárkou) na sekvenci osmibitových operací. Tato znalost je pochopitelně důležitá i jinde, například při práci s osmibitovými mikrořadiči.
Obrázek 7: Součet dvou celých šestnáctibitových čísel není na osmibitovém čipu MOS 6502 zcela triviální operací. Je nutné ji rozložit na součet spodních bajtů následovaných součtem vyšších bajtů, navíc je nutno brát ohled na přenos (carry) při prvním součtu.
Obrázek 8: Naproti tomu součet dvou osmibitových celých čísel je na tomtéž čipu již triviální – pokud překladači cc65 odpustíme zcela neefektivní způsob překladu (ten lze ovšem do určité míry ladit – a to použitím přepínačů překladače).
5. Porovnání dvou či více variant překladu
V mnoha diskusích se vývojáři snaží o porovnávání kvality různých překladačů, typicky z hlediska optimalizace generovaného strojového kódu. Popř. se vedou diskuse o tom, zda je například v případě překladače GCC pro určitou aplikaci (nebo i pro jádro operačního systému) lepší zapnout optimalizaci -O2 nebo -O3 atd. Při použití Compiler Exploreru je možné v rámci jednoho tabu v prohlížeči zobrazit výstup z několika překladačů (a to i pro různé platformy), několika verzí překladačů nebo například překlad v rámci jedné verze překladače, ale s odlišnými příznaky (flags). A stále platí, že modifikace ve zdrojovém kódu vede k prakticky okamžitému překladu se zobrazením všech nakonfigurovaných výstupů v assembleru:
Obrázek 9: Porovnání překladu s využitím různých variant Rustu.
Obrázek 10: Porovnání překladu s využitím stejného překladače, ale s odlišnými přepínači (flags).
Obrázek 11: Překlad stejného kódu na tři zcela odlišné platformy: MOS 6502, x86–64 a 32bitový ARM.
Obrázek 12: Porovnání překladu stejného kódu pomocí MSVC a icc.
6. Zobrazení bajtkódu u vybraných programovacích jazyků
Na stránkách Roota jsme se podrobně zabývali studiem bajtkódu některých programovacích jazyků (viz odkazy na konci článku). Projekt Compiler Explorer některé z těchto bajtkódů taktéž podporuje. Týká se to především Pythonu a taktéž Javy, resp. přesněji řečeno jazyků postavených nad virtuálním strojem Javy (JVM). Ovšem některé další jazyky a jejich bajtkódy (alespoň prozatím) podporovány nejsou; což je konkrétně případ programovacího jazyka Lua či technologie Parrot. Z novějších bajtkódů je pravděpodobně nejzajímavější WebAssembly, tedy bajtkód, který lze interpretovat či JITovat v moderních prohlížečích (což po odstranění podpory JVM může vypadat jako snaha o znovuobjevení kola :-) ). Pro zajímavost se podívejme na několik jednoduchých příkladů, konkrétně na překlad do bajtkódu JVM, dále na překlad do bajtkódu Pythonu a konečně překlad do bajtkódu WebAssembly:
Obrázek 13: Překlad konstruktoru třídy Square a metody square naprogramovaného v Javě do bajtkódu virtuálního stroje Javy (JVM). Barevně jsou odlišeny bloky instrukcí implicitního konstruktoru a bloky instrukcí z metody (ty by byly dále rozděleny na jednotlivé řádky).
Obrázek 14: Překlad jednoduché funkce napsané v Pythonu do bajtkódu Pythonu. V tomto případě existuje vazba mezi řádkem zdrojového kódu a blokem v bajtkódu; z tohoto důvodu jsou jednotlivé vazby zvýrazněny odlišným barevným pozadím.
Obrázek 15: Překlad výpočtu zapsaného v jazyku C do WebAssembly.
7. Transformace zdrojového kódu do AST
Současné překladače rozdělují překlad zdrojových kódů do několika kroků. Dnes bývá typické hlavní dělení na front end a back end překladače (někdy se zavádí i pojem middle end, což je poněkud zvláštní označení). V rámci frontendu překladače se postupně provádí jednotlivé dílčí kroky, a to jak v klasických překladačích (C, Rust, Go), tak i v jazycích, které provádí překlad „jen“ do bajtkódu s jeho pozdější interpretací (Python) nebo JITováním (Java). Díky rozdělení celého zpracování do několika konfigurovatelných kroků je zajištěna velká flexibilita a možnost případného relativně snadného rozšiřování o další syntaktické prvky, existuje možnost použití jediné sady nástrojů více jazyky, lze přidat podporu pro různé výstupní formáty (překlad do nativního kódu nebo do WebAssembly atd.), podporu speciální filtry apod. (nehledě na to, že každá činnost je založena na odlišné teorii a mohou na nic pracovat jiní vývojáři). Celý průběh zpracování vypadá při určitém zjednodušení následovně:
- Na začátku zpracování se nachází takzvaný lexer, který postupně načítá jednotlivé znaky ze vstupního řetězce (resp. ze vstupního souboru) a vytváří z nich lexikální tokeny. Teoreticky se pro každý programovací jazyk používá odlišný lexer a samozřejmě je možné v případě potřeby si napsat lexer vlastní. V případě Pythonu můžeme použít například standardní modul tokenizer, nebo lze alternativně použít například projekt Pygments, jenž obsahuje lexery pro mnoho dalších programovacích jazyků.
- Výstup z lexeru může procházet libovolným počtem filtrů sloužících pro odstranění nebo (častěji) modifikaci jednotlivých tokenů; ať již jejich typů či přímo textu, který tvoří hodnotu tokenu. Díky existenci filtrů je například možné nechat si zvýraznit vybrané bílé znaky, slova se speciálním významem v komentářích (TODO:, FIX:) apod. Některé lexery obsahují filtr přímo ve svém modulu.
- Sekvence tokenů tvoří základ pro syntaktickou analýzu. Nástroj, který syntaktickou analýzu provádí, se většinou nazývá parser a proto se taktéž někdy setkáme s pojmem parsing (tento termín je ovšem chybně používán i v těch případech, kdy se provádí „pouze“ lexikální analýza). Výsledkem činnosti parseru je vhodně zvolená datová struktura, typicky abstraktní syntaktický strom (AST); někdy též strom derivační. V případě Pythonu vypadá postupné zpracování vstupního zdrojového textu takto: lexer → derivační strom (parse tree) → AST.
Obrázek 16: AST s vizualizací výrazu 1+2*3.
Obrázek 17: AST s vizualizací výrazu (1+2)*3.
8. Zobrazení AST v Compiler Exploreru
Vzhledem k tomu, jak je AST důležitý pro front end překladače, může být užitečné mít možnost si prohlédnout i tuto datovou strukturu. Dostupná je pouze pro některé překladače, typicky pro ty, které skutečně striktně rozdělují jednotlivé fáze zpracování a dokážou produkovat výstup z každé této fáze. Dobrým příkladem takového typu překladače je Clang, který si později zaslouží samostatný článek. Tento překladač může (pochopitelně kromě dalších výstupů) generovat i výstup z parseru, a to právě ve formě AST:
Obrázek 18: AST vygenerovaný překladačem Clang.
9. Překlad do mezikódu (intermediate representation)
Některé typy překladačů, mezi nimi i již výše zmíněný Clang v první fázi překladu (front end) vygenerují mezikód), který je nezávislý na konkrétním typu procesoru. Teprve na tento mezikód jsou aplikovány různé (obecné) optimalizace a následně je provedena transformace do strojového kódu zvoleného mikroprocesoru. V případě, že zvolený překladač dokáže vygenerovat a především vyexportovat mezikód, je tato volba dostupná i v Compiler Exploreru, o čemž se opět můžeme velmi snadno přesvědčit:
Obrázek 19: Výstup do assembleru a mezikód, který k tomuto výstupu vedl na architektuře x86–64.
Obrázek 20: Tentýž program, tentýž mezikód, ovšem tentokrát přeložený pro ARMv7.
10. Přímá podpora assemblerů
Výsledkem překladu je typicky strojový kód popř. v některých případech (Python, Java, Lua) bajtkód. To platí i pro assemblery, které jsou Compiler Explorerem taktéž podporovány, takže je možné si nechat zobrazit, jak se zdrojový kód v „symbolickém“ assembleru překládá do strojového kódu, který je pro lepší čitelnost zobrazen s využitím disassembleru (což znamená oproti původnímu kódu ztrátu informací). Díky této podpoře si můžete snadno vyzkoušet různé assemblery, které se liší svou syntaxí, a to i tehdy, pokud jsou určeny pro stejnou platformu (viz například rozdíly mezi GNU Assemblerem, NASMem, assemblerem integrovaným do LLVM atd.):
Obrázek 21: Kostra programu napsaného pro AArch64 (ARMv8) s běžícím Linuxem.
Obrázek 22: Můžeme si nechat zobrazit i kódy instrukcí, tedy vlastní strojový kód.
Obrázek 23: „Hello world“ v assembleru i386.
11. Zajímavosti na konec: detekce memset z programové smyčky a překlad pro osmibitové čipy
Clang obsahuje některé zajímavé optimalizace, například dokáže rozpoznat, že programátor zapsal smyčky sémanticky odpovídající standardní funkci memset:
Obrázek 24: Volba -O1 zajistí, že Clang nahradí celou smyčku voláním standardní funkce memset.
Tentýž příklad, ovšem přeložený GCC (kde jsem se snažil přesvědčit překladač, aby smyčku alespoň rozbalil):
Obrázek 25: Překlad stejného příkladu, nyní ovšem s využitím GCC.
Příklad překladu zdrojového programu naprogramovaného v céčko do strojového kódu pro osmibitový mikrořadič, konkrétně pro ATmega328:
Obrázek 26: Kód získaný při vypnutí optimalizací není příliš dobrý…
12. Seznam podporovaných jazyků
Seznam podporovaných jazyků lze získat přes REST API:
Id | Name csharp | C# fsharp | F# vb | Visual Basic go | Go c | C c++ | C++ fortran | Fortran assembly | Assembly circle | C++ (Circle) circt | CIRCT cppx | Cppx crystal | Crystal hlsl | HLSL dart | Dart erlang | Erlang carbon | Carbon cppx_blue | Cppx-Blue cppx_gold | Cppx-Gold mlir | MLIR cuda | CUDA C++ analysis | Analysis python | Python ruby | Ruby typescript | TypeScript Native ada | Ada cpp_for_opencl | C++ for OpenCL openclc | OpenCL C llvm | LLVM IR d | D rust | Rust ispc | ispc jakt | Jakt java | Java kotlin | Kotlin nim | Nim pony | Pony scala | Scala solidity | Solidity clean | Clean pascal | Pascal haskell | Haskell ocaml | OCaml swift | Swift zig | Zig
13. Seznam integrovaných překladačů
I seznam podporovaných překladačů je možné získat přes REST API. Celkem se v současnosti jedná o 1489 kombinací platforma+překladač+verze:
Compiler Name | Name dotnet601csharp | .NET 6.0.101 dotnet601fsharp | .NET 6.0.101 dotnet601vb | .NET 6.0.101 386_gltip | 386 gc (tip) 386_gl114 | 386 gc 1.14 386_gl115 | 386 gc 1.15 386_gl116 | 386 gc 1.16 386_gl117 | 386 gc 1.17 386_gl118 | 386 gc 1.18 386_gl119 | 386 gc 1.19 cc65_217 | 6502 cc65 2.17 cc65_218 | 6502 cc65 2.18 cc65_219 | 6502 cc65 2.19 cc65_trunk | 6502 cc65 trunk ... ... ... zcxx060 | zig c++ 0.6.0 zcxx070 | zig c++ 0.7.0 zcxx071 | zig c++ 0.7.1 zcxx080 | zig c++ 0.8.0 zcxx090 | zig c++ 0.9.0 zcxxtrunk | zig c++ trunk zcc060 | zig cc 0.6.0 zcc070 | zig cc 0.7.0 zcc071 | zig cc 0.7.1 zcc080 | zig cc 0.8.0 zcc090 | zig cc 0.9.0 zcctrunk | zig cc trunk ztrunk | zig trunk
14. Odkazy na Internetu
- Stránka projektu Compiler Explorer
https://godbolt.org/ - The LLVM Compiler Infrastructure
https://llvm.org/ - GCC, the GNU Compiler Collection
https://gcc.gnu.org/ - Java quick guide: JVM Instruction Set (tabulka všech instrukcí JVM)
http://www.mobilefish.com/tutorials/java/java_quickguide_jvm_instruction_set.html - The JVM Instruction Set
http://mpdeboer.home.xs4all.nl/scriptie/node14.html - PrintAssembly
https://wikis.oracle.com/display/HotSpotInternals/PrintAssembly - Open Source ByteCode Libraries in Java
http://java-source.net/open-source/bytecode-libraries - The class File Format
http://java.sun.com/docs/books/jvms/second_edition/html/ClassFile.doc.html - javap – The Java Class File Disassembler
http://docs.oracle.com/javase/1.4.2/docs/tooldocs/windows/javap.html - Inside The Python Virtual Machine
https://leanpub.com/insidethepythonvirtualmachine - module-py_compile
https://docs.python.org/3.8/library/py_compile.html - Given a python .pyc file, is there a tool that let me view the bytecode?
https://stackoverflow.com/questions/11141387/given-a-python-pyc-file-is-there-a-tool-that-let-me-view-the-bytecode - The structure of .pyc files
https://nedbatchelder.com/blog/200804/the_structure_of_pyc_files.html - Python Bytecode: Fun With Dis
http://akaptur.github.io/blog/2013/08/14/python-bytecode-fun-with-dis/ - Python's Innards: Hello, ceval.c!
http://tech.blog.aknin.name/category/my-projects/pythons-innards/ - Byterun
https://github.com/nedbat/byterun - Python Byte Code Instructions
http://document.ihg.uni-duisburg.de/Documentation/Python/lib/node56.html - Python Byte Code Instructions
https://docs.python.org/3.2/library/dis.html#python-bytecode-instructions - dis – Python module
https://docs.python.org/2/library/dis.html - Comparison of Python virtual machines
http://polishlinux.org/apps/cli/comparison-of-python-virtual-machines/ - O-code
http://en.wikipedia.org/wiki/O-code_machine - ARM GCC Inline Assembler Cookbook
http://www.ethernut.de/en/documents/arm-inline-asm.html - Extended Asm – Assembler Instructions with C Expression Operands
https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html - ARM inline asm secrets
http://hardwarebug.org/2010/07/06/arm-inline-asm-secrets/ - The ARMv8 instruction sets
http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.den0024a/ch05s01.html - A64 Instruction Set
https://developer.arm.com/products/architecture/instruction-sets/a64-instruction-set - The ARM Instruction Set
http://simplemachines.it/doc/arm_inst.pdf - ARM Architecture (Wikipedia)
http://en.wikipedia.org/wiki/ARM_architecture - The GNU Assembler Tutorial
http://tigcc.ticalc.org/doc/gnuasm.html - The GNU Assembler – macros
http://tigcc.ticalc.org/doc/gnuasm.html#SEC109 - 6502 – the first RISC µP
http://ericclever.com/6500/ - ca65 Users Guide
https://cc65.github.io/doc/ca65.html - cc65 Users Guide
https://cc65.github.io/doc/cc65.html - Adventures with ca65
https://atariage.com/forums/topic/312451-adventures-with-ca65/ - Assembly Language Misconceptions
https://www.youtube.com/watch?v=8_0tbkbSGRE - How Machine Language Works
https://www.youtube.com/watch?v=HWpi9n2H3kE - Instrukční sada AArch64: technologie NEON
https://www.root.cz/clanky/instrukcni-sada-aarch64-technologie-neon/ - Seriál Programovací jazyk Go
https://www.root.cz/serialy/programovaci-jazyk-go/ - Seriál Programovací jazyk Rust
https://www.root.cz/serialy/programovaci-jazyk-rust/ - Instrukční sada procesorových jader s otevřenou architekturou RISC-V
https://www.root.cz/clanky/instrukcni-sada-procesorovych-jader-s-otevrenou-architekturou-risc-v/ - 64bitové mikroprocesory s architekturou AArch64
https://www.root.cz/clanky/64bitove-mikroprocesory-s-architekturou-aarch64/ - Jak se zrodil procesor?
https://www.root.cz/clanky/jak-se-zrodil-procesor/ - Cross assemblery a cross překladače pro platformu osmibitových domácích mikropočítačů Atari
https://www.root.cz/clanky/cross-assemblery-a-cross-prekladace-pro-platformu-osmibitovych-domacich-mikropocitacu-atari/ - CppCon 2016: Jason Turner “Rich Code for Tiny Computers: A Simple Commodore 64 Game in C++17”
https://www.youtube.com/watch?v=zBkNBP00wJE - Vektorové procesory aneb další pokus o zvýšení výpočetního výkonu počítačů
https://www.root.cz/clanky/vektorove-procesory-aneb-dalsi-pokus-o-zvyseni-vypocetniho-vykonu-pocitacu/ - Intermediate representation
https://en.wikipedia.org/wiki/Intermediate_representation - Abstract syntax tree
https://en.wikipedia.org/wiki/Abstract_syntax_tree - Lexical analysis
https://en.wikipedia.org/wiki/Lexical_analysis - Parser
https://en.wikipedia.org/wiki/Parsing#Parser - Parse tree
https://en.wikipedia.org/wiki/Parse_tree - Derivační strom
https://cs.wikipedia.org/wiki/Deriva%C4%8Dn%C3%AD_strom - Python doc: ast — Abstract Syntax Trees
https://docs.python.org/3/library/ast.html - Python doc: tokenize — Tokenizer for Python source
https://docs.python.org/3/library/tokenize.html - Mikropočítač KIM-1: jeden ze zvěstovatelů osmibitové revoluce
https://www.root.cz/clanky/mikropocitac-kim-1-jeden-ze-zvestovatelu-osmibitove-revoluce/ - Compiler Explorer Libraries
https://godbolt.org/admin/libraries.html - Stav jednotlivých překladačů v Compiler Exploreru
https://compiler-explorer.github.io/compiler-workflows/build-status - WebAssembly
https://webassembly.org/ - Clang
https://clang.llvm.org/ - Clang: Assembling a Complete Toolchain
https://clang.llvm.org/docs/Toolchain.html
ČLÁNKY DO MAILU