4 ms·
The problem is of course that it's kind of a fairy tale. The compiler (or assembler) can generate object code, but it needs placeholders for function calls obvi
by mort96 4y ago
The problem is of course that it's kind of a fairy tale. The compiler (or assembler) can generate object code, but it needs placeholders for function calls obviously. The problem is, depending on where exactly the called function ends up, the function call might be more or fewer instructions long. That means, depending on what exact kind of call sequence is required, all the other code in the function has to be shifted around, since all jump targets shift around. Even worse, the length of the instruction sequence necessary for a relative jump depends on how far the jump is, so all intra-function jumps may be longer or shorter based on which instruction sequence is required for the inter-function jumps.
Linking sounds like a clean solution, but it really, really isn't. It's messy as all hell.
I think maybe, if I was to design a solution from scratch, I'd make object files basically a binary encoding of assembly code rather than true machine code; notably, I would keep jumps as abstract "jump to this label" instructions rather than proper machine code. This would put the assembler in the linker, where we actually have enough information to do instruction selection, rather than in the assembler where we don't.
We could also just put straight-up compiler IR in the object files, which puts a whole compiler back-end in the linker. This opens the door for LTO. Obviously, there are performance implications of this; if most of the hard work happens in the linker, linking can't be a stupid single-threaded serial operation anymore. But we could just make multi-threaded linkers and we get back our parallelism. We do lose some of the incrementalness of incremental compilation though.
- PoignardAzur 4y agoI mean... what you're describing is basically what lld with ThinLTO does?
- mort96 4y agoMy understanding is that ThinLTO (and other existing forms of LTO) does put IR in the object file and a compiler back-end in the linker, yes. But as far as I understand, the linker relaxations mentioned in the linked article are about when you emit traditional object files with machine code + relocation tables, and that's what I described as messy.
- moring 4y ago> We could also just put straight-up compiler IR in the object files (...) Just a reminder that we're talking about LLVM here, whose whole point from the beginning was exactly what you described ;)
- glandium 4y ago> The problem is, depending on where exactly the called function ends up, the function call might be more or fewer instructions long. That means, depending on what exact kind of call sequence is required, all the other code in the function has to be shifted around, since all jump targets shift around. Linkers actually don't change instruction lengths. If they need to jump further away than what the instruction allows, they add trampolines, which are chunks of code with the appropriate instruction for the long jump, and place the trampoline at a good distance of the relocatable short jump. Edit: well, except in the proposed case of relaxation, where they'd want to shorten jump instructions.
- twic 4y agoSounds somewhat like ANDF: https://en.wikipedia.org/wiki/Architecture_Neutral_Distribution_Format https://en.wikipedia.org/wiki/Architecture_Neutral_Distribut...
- rvbissell 4y agoAST in the object files, maybe?