Uefi-jitfuck – A JIT Brainfuck compiler running on x86_64 UEFI
github.com
github.com
The author is lucky brainfuck is so simple, no need for the hairy generic MOD/RM [0] addressing mode encoding.
Of course instruction encoding is far from the hairiest part of the process of JITting. Data flow simplification (= don't generate unnecessary intermediates, like target architecture flag register bits that never affect execution), register allocation and instruction selection are pretty complicated optimization problems.
Oh, and indirect calls and jumps. How you'll hate those when writing a CPU JIT... Especially those that very inconveniently jump in the middle of a previously generated JIT trace.
[0]: MOD/RM is has four modes (MOD).
One for simply accessing a register. Three for addressing memory through pointers in various ways. The most complicated case is SIB (scale + index + base) addressing mode. In C, it'd be something like:
addr = (reg1<<scale) + reg2 + <immediate>;
Some x86(-64) register combinations can't be encoded directly, so the encoder will need to play around and possibly "upgrade" the addressing mode to a more complicated SIB version.
For more curious, this page was very informative for writing my addressing mode encoder:
https://wiki.osdev.org/X86-64_Instruction_Encoding#ModR.2FM_...
You said you were working on another JIT - what was that? Also, do you have any suggestions of another project/language to implement compiler for to gain some knowledge about writing optimizations, actual intepretation/compilation logic, etc?
Thanks for the additional resources about the instruction encoding - seems like this is a bit easier to understand than AMD64 documentation!
> You said you were working on another JIT - what was that?
A JIT for a custom 32-bit RISC soft-CPU (FPGA).
> Also, do you have any suggestions of another project/language to implement compiler for to gain some knowledge about writing optimizations, actual intepretation/compilation logic, etc?
You could write another C compiler. Or a JIT for some scripting language. Lua is about as simple as it gets when it comes to JITtable scripting languages. Of course amazing http://luajit.org/ already exists.
Existing CPUs and bytecode formats are also potentially good.
In particular, other people might actually want to use a small WebAssembly (https://webassembly.org/) AOT/JIT compiler. I know I would. :)
Some source code I've personally found educating on this topic:
1) Lots of easier stuff (ARM/x86 encoding, basic optimizations, etc.) can be found in JITting emulators, like Dolphin: (https://github.com/dolphin-emu/dolphin)
2) Web browser Javascript engines, like (https://github.com/v8/v8/tree/master/src). And of course LuaJIT.
3) Compiler codegen, like LLVM (https://github.com/llvm-mirror/llvm)
It may not be a JIT compiler, but back in 5th grade I vaguely remember writing an extended brainfuck interpreter that fit within the boot sector of my HDD. It pulled some brainfuck code I wrote (fuckboot I believe it was called) from a FAT partition designed to bootstrap the Linux kernel. I recall being absolutely amazed at how simple yet advanced the language was.
And it’s mainly used to execute OS-loaders.
Some firmwares even come with a MS-DOS like UEFI shell.
[1] https://trmm.net/Thunderstrike [2] https://www.linuxboot.org [3] https://trmm.net/LinuxBoot_34c3
Kudos, though, this is really cool!