3 ms·

What would you suggest instead? Being able to link pre-compiled object files to a new program is certainly a bit more than "a kind of incremental compilation",

by unwind 4y ago

What would you suggest instead? Being able to link pre-compiled object files to a new program is certainly a bit more than "a kind of incremental compilation", in my opinion. It's also a fairly clean solution to the problem of not recompiling code that hasn't changed.

moring 4y ago
Depends on the definition of "linking". Having multiple source files each compiled to LLVM bitcode and not re-doing this if another file changes is fine. Turning the bitcode to native code is where traditionally the compiler back-end, assembler and linker are involved, and these are steps you want to re-do to enable global optimization (e.g. inlining functions from another source file, followed by dead code elimitation -- these two steps give you no-cost "runtime" parameter checks, for example). The traditional 3-step split is just becoming cumbersome there, and linker relaxation is treating that symptom.
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 ago
  I mean... what you're describing is basically what lld with ThinLTO does?
  - mort96 4y ago
    My 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 ago
  Sounds somewhat like ANDF: https://en.wikipedia.org/wiki/Architecture_Neutral_Distribution_Format https://en.wikipedia.org/wiki/Architecture_Neutral_Distribut...
- rvbissell 4y ago
  AST in the object files, maybe?

by unwind 4y ago

moring 4y ago

Depends on the definition of "linking". Having multiple source files each compiled to LLVM bitcode and not re-doing this if another file changes is fine. Turning the bitcode to native code is where traditionally the compiler back-end, assembler and linker are involved, and these are steps you want to re-do to enable global optimization (e.g. inlining functions from another source file, followed by dead code elimitation -- these two steps give you no-cost "runtime" parameter checks, for example). The traditional 3-step split is just becoming cumbersome there, and linker relaxation is treating that symptom.

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 ago
I mean... what you're describing is basically what lld with ThinLTO does?
- mort96 4y ago
  My 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 ago
Sounds somewhat like ANDF: https://en.wikipedia.org/wiki/Architecture_Neutral_Distribution_Format https://en.wikipedia.org/wiki/Architecture_Neutral_Distribut...
rvbissell 4y ago
AST in the object files, maybe?