4 ms·

Compiling a Lisp to x86-64: Labelled procedure calls

93 points by tekknolagi 6y ago

tekknolagi 6y ago
I'd love to hear feedback!
- UncleOxidant 6y ago
  Could you do a series like this targeting ARM or RISC-V?
  - tekknolagi 6y ago
    I think that would be a lot of fun! I'm vaguely planning to target RISC-V eventually, because I bought a couple of dev boards. But for now you should check out Vladimir Keleshev's book! His book targets ARM. Book: https://keleshev.com/compiling-to-assembly-from-scratch/ https://keleshev.com/compiling-to-assembly-from-scratch/
- z3phyr 6y ago
  I discovered this writing a few weeks back, and enjoying it. Just the thing to go through after Lisp in Small Pieces, very well written! Looking forward to more content from you! Thanks!
  - tekknolagi 6y ago
    Glad you're enjoying! Let me know if you come across things that could be better explained, etc.
jsmith45 6y ago
Because I have not yet figured out how to start executing at somewhere other than the beginning of the generated code, and because I don’t store generated code in any intermediate buffers, and because we don’t know the sizes of any code in advance, I do this funky thing where I emit a jmp to the body code. If you, dear reader, have a better solution, please let me know. Assuming you know the byte offset into the code buffer, of your "main" equivalent label, you should be able to use the following: byte* start_address = buf->address + offset; JitFunction function = *(JitFunction*)(&start_address); return function(heap); I'm guessing you were running into the issue that you can't do this in one line while also suppressing the warning about the data pointer to function pointer. The "normal" way to do this would be the following, but it has the downside of the compiler warning: JitFunction function = (JitFunction)(buf->address + offset); return function(heap);
- tekknolagi 6y ago
  So I was doing this (storing the main entry point) but it was crashing. I'll have to try again, I suppose.
  - oso2k 6y ago
    Is `kLabelPlaceholder` an absolute or relative address? If it's absolute, you start executing at `kLabelPlaceholder`. If it's relative, you start executing at `buf + kLabelPlaceholder`. You could see the final value if you compile with debug info and run the binary under `gdb` or some other debugger. It might help to read skeeto's blogs [0][1][2]. [0] https://nullprogram.com/blog/2015/03/19/ https://nullprogram.com/blog/2015/03/19/ [1] https://nullprogram.com/blog/2016/12/11/ https://nullprogram.com/blog/2016/12/11/ [2] https://nullprogram.com/blog/2018/11/15/ https://nullprogram.com/blog/2018/11/15/
    - tekknolagi 6y ago
      It's a placeholder. It's meant to fill in before actual addresses are filled in. But all the call targets are relative addresses.
- tekknolagi 6y ago
  Alright, I got it to work! I think I might have done something stupid like forget to move the prologue, too, in the past revision. Now it works. Thanks! I've updated the post.
amelius 6y ago
Somewhat related question: which book is the modern-day equivalent of the Dragon Book? And does it cover subjects such as JIT, the innards of virtual machines and concurrent garbage collection?
- tekknolagi 6y ago
  I have not found one book, but there are a lot of different papers and blog posts floating around about different aspects. Some focus on GC, some codegen, ...
- icandoit 6y ago
  I like these resources. The most general are first, more specific toward the end. https://pragprog.com/titles/tpdsl/language-implementation-patterns/ https://pragprog.com/titles/tpdsl/language-implementation-pa... Language Implementation Patterns Create Your Own Domain-Specific and General Programming Languages by Terence Parr (Antlr) https://craftinginterpreters.com/ https://craftinginterpreters.com/ by Bob Nystrom https://interpreterbook.com/ https://interpreterbook.com/ Writing An Interpreter In Go by Thorsten Ball (also has a compiler book) The Implementation of Lua 5.0 (short) https://www.lua.org/doc/jucs05.pdf https://www.lua.org/doc/jucs05.pdf A Deep Introduction to JIT Compilers: JITs are not very Just-in-time https://carolchen.me/blog/jits-intro/ https://carolchen.me/blog/jits-intro/ by Carol Chen video series: JIT programming language development in C https://www.youtube.com/watch?v=k3gDvF-Fbpw&list=PLvdK1vRmp8wMzH4w_8sQ30NKU3Bt4Cc-M https://www.youtube.com/watch?v=k3gDvF-Fbpw&list=PLvdK1vRmp8... by Dmitriy Kubyshkin
rcgorton 6y ago
Not sure why Lisp is actually relevant IN THE REAL WORLD.

93 points by tekknolagi 6y ago

tekknolagi 6y ago

I'd love to hear feedback!

UncleOxidant 6y ago
Could you do a series like this targeting ARM or RISC-V?
- tekknolagi 6y ago
  I think that would be a lot of fun! I'm vaguely planning to target RISC-V eventually, because I bought a couple of dev boards. But for now you should check out Vladimir Keleshev's book! His book targets ARM. Book: https://keleshev.com/compiling-to-assembly-from-scratch/ https://keleshev.com/compiling-to-assembly-from-scratch/
z3phyr 6y ago
I discovered this writing a few weeks back, and enjoying it. Just the thing to go through after Lisp in Small Pieces, very well written! Looking forward to more content from you! Thanks!
- tekknolagi 6y ago
  Glad you're enjoying! Let me know if you come across things that could be better explained, etc.

jsmith45 6y ago

Because I have not yet figured out how to start executing at somewhere other than the beginning of the generated code, and because I don’t store generated code in any intermediate buffers, and because we don’t know the sizes of any code in advance, I do this funky thing where I emit a jmp to the body code. If you, dear reader, have a better solution, please let me know. Assuming you know the byte offset into the code buffer, of your "main" equivalent label, you should be able to use the following: byte* start_address = buf->address + offset; JitFunction function = *(JitFunction*)(&start_address); return function(heap); I'm guessing you were running into the issue that you can't do this in one line while also suppressing the warning about the data pointer to function pointer. The "normal" way to do this would be the following, but it has the downside of the compiler warning: JitFunction function = (JitFunction)(buf->address + offset); return function(heap);

tekknolagi 6y ago
So I was doing this (storing the main entry point) but it was crashing. I'll have to try again, I suppose.
- oso2k 6y ago
  Is `kLabelPlaceholder` an absolute or relative address? If it's absolute, you start executing at `kLabelPlaceholder`. If it's relative, you start executing at `buf + kLabelPlaceholder`. You could see the final value if you compile with debug info and run the binary under `gdb` or some other debugger. It might help to read skeeto's blogs [0][1][2]. [0] https://nullprogram.com/blog/2015/03/19/ https://nullprogram.com/blog/2015/03/19/ [1] https://nullprogram.com/blog/2016/12/11/ https://nullprogram.com/blog/2016/12/11/ [2] https://nullprogram.com/blog/2018/11/15/ https://nullprogram.com/blog/2018/11/15/
  - tekknolagi 6y ago
    It's a placeholder. It's meant to fill in before actual addresses are filled in. But all the call targets are relative addresses.
tekknolagi 6y ago
Alright, I got it to work! I think I might have done something stupid like forget to move the prologue, too, in the past revision. Now it works. Thanks! I've updated the post.

amelius 6y ago

Somewhat related question: which book is the modern-day equivalent of the Dragon Book? And does it cover subjects such as JIT, the innards of virtual machines and concurrent garbage collection?

tekknolagi 6y ago
I have not found one book, but there are a lot of different papers and blog posts floating around about different aspects. Some focus on GC, some codegen, ...
icandoit 6y ago
I like these resources. The most general are first, more specific toward the end. https://pragprog.com/titles/tpdsl/language-implementation-patterns/ https://pragprog.com/titles/tpdsl/language-implementation-pa... Language Implementation Patterns Create Your Own Domain-Specific and General Programming Languages by Terence Parr (Antlr) https://craftinginterpreters.com/ https://craftinginterpreters.com/ by Bob Nystrom https://interpreterbook.com/ https://interpreterbook.com/ Writing An Interpreter In Go by Thorsten Ball (also has a compiler book) The Implementation of Lua 5.0 (short) https://www.lua.org/doc/jucs05.pdf https://www.lua.org/doc/jucs05.pdf A Deep Introduction to JIT Compilers: JITs are not very Just-in-time https://carolchen.me/blog/jits-intro/ https://carolchen.me/blog/jits-intro/ by Carol Chen video series: JIT programming language development in C https://www.youtube.com/watch?v=k3gDvF-Fbpw&list=PLvdK1vRmp8wMzH4w_8sQ30NKU3Bt4Cc-M https://www.youtube.com/watch?v=k3gDvF-Fbpw&list=PLvdK1vRmp8... by Dmitriy Kubyshkin

rcgorton 6y ago

Not sure why Lisp is actually relevant IN THE REAL WORLD.