3 ms·

I think the expected "why" here relates to why compilers produce suboptimal sequences, like moving a register into itself. In a world with better initial codege

I think the expected "why" here relates to why compilers produce suboptimal sequences, like moving a register into itself. In a world with better initial codegen, peephole optimizers wouldn't (practically) work because there wouldn't be much to shorten.

astrange 3y ago
SSA form doesn't have a concept of moving into itself (because it doesn't have moves at all), but the reason it might be messy is that other optimization passes would prefer to stick to their specific jobs and not reimplement every kind of cleaning up after themselves. Once you get past the SSA stages, sometimes you just can't describe the target instructions perfectly enough to emit something clean without cleanup passes.
UncleOxidant 3y ago
I've done some peephole optimizations at the initial machine instruction lowering phase (in LLVM) because there were some quirks of the register files in the target architecture and that was just the best place to optimize (after register allocation) - you didn't want to access two operands from the same register bank and have the result go back into the same register bank (if you could avoid it) because it would cost an extra cycle or two. So we went through and identified those cases and fixed them up (where possible).
Arelius 3y ago
Yes, it's sortof tautologically true that if you generate the optimized code during initial codegen then optimization wouldn't optimize. No, that's not really how we build compilers. I guess you're trying to get is what structures make it easier to defer the optimal code generation. And I think that's somewhat a hard answer since it generally has many answers.
aaron695 3y ago
[dead]
JonChesterfield 3y ago
Function inlining is a big source of suboptimal sequences. Even if your codegen for a function is perfect up front, as soon as it is inlined into some other perfect code the combination tends to be decidedly non-perfect, and hence fed into CSE and so forth. Plus unless you can persuade programmers to write perfectly efficient functions in the first place you need that optimiser to produce the initially perfect codegen.
- pfdietz 3y ago
  That's assuming the inlining occurs at the level of machine code, not at that of the IR.
phkahler 3y ago
A simple compiler could just assume all registers are available when it generates code from a line of source because the language (C for example) has no conception of CPU registers. That approach would lead to a LOT of redundant loads and stores for example. Register allocation to the rescue! But how smart can a single code generator be? How much can the process be holistic vs sequential steps. There is a complexity nightmare here and it needs to be broken down some way right?

astrange 3y ago

SSA form doesn't have a concept of moving into itself (because it doesn't have moves at all), but the reason it might be messy is that other optimization passes would prefer to stick to their specific jobs and not reimplement every kind of cleaning up after themselves. Once you get past the SSA stages, sometimes you just can't describe the target instructions perfectly enough to emit something clean without cleanup passes.

UncleOxidant 3y ago

I've done some peephole optimizations at the initial machine instruction lowering phase (in LLVM) because there were some quirks of the register files in the target architecture and that was just the best place to optimize (after register allocation) - you didn't want to access two operands from the same register bank and have the result go back into the same register bank (if you could avoid it) because it would cost an extra cycle or two. So we went through and identified those cases and fixed them up (where possible).

Arelius 3y ago

Yes, it's sortof tautologically true that if you generate the optimized code during initial codegen then optimization wouldn't optimize. No, that's not really how we build compilers. I guess you're trying to get is what structures make it easier to defer the optimal code generation. And I think that's somewhat a hard answer since it generally has many answers.

aaron695 3y ago

[dead]

JonChesterfield 3y ago

Function inlining is a big source of suboptimal sequences. Even if your codegen for a function is perfect up front, as soon as it is inlined into some other perfect code the combination tends to be decidedly non-perfect, and hence fed into CSE and so forth. Plus unless you can persuade programmers to write perfectly efficient functions in the first place you need that optimiser to produce the initially perfect codegen.

pfdietz 3y ago
That's assuming the inlining occurs at the level of machine code, not at that of the IR.

phkahler 3y ago

A simple compiler could just assume all registers are available when it generates code from a line of source because the language (C for example) has no conception of CPU registers. That approach would lead to a LOT of redundant loads and stores for example. Register allocation to the rescue! But how smart can a single code generator be? How much can the process be holistic vs sequential steps. There is a complexity nightmare here and it needs to be broken down some way right?