4 ms·

Why Do Peephole Optimizations Work

35 points by matt_d 3y ago

cdcarter 3y ago
Peeps are the type of thing that, once you realize what's going on, you can solve a whole new class of problems as if by magic. The cpython compiler's peephole optimizer is an easy code read and a great example of this in practice. The Apex compiler at Salesforce ONLY does peephole optimizations.
pfdietz 3y ago
That was not the kind of answer I was looking for. I was hoping to see "why is it that when peephole optimizations are applied, they often speed up the program?"
- phkahler 3y ago
  >> I was hoping to see "why is it that when peephole optimizations are applied, they often speed up the program?" Because that's what the optimizations are designed to do? The example in the post replaces 3 instructions with 2 that produce the same result. Assuming all the instructions involved take the same number of clock cycles, 2 < 3 will run faster. My understanding is that peephole optimizations usually get implemented when people study the output of the compiler and notice instruction sequences that can be shortened. Usually the sequences are somewhat common, so the optimization makes sense to implement.
  - tedunangst 3y ago
    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?
russdill 3y ago
lol, had no idea what peephole optimizations were, but reading about them instantly brought back memories of reverse engineering byte code obfuscation as some 99% of the generated byte code is useless moving around of data that could be compacted into tighter representations. And yes, it consisted of a set of a large pattern matching rules that would be matched against windows of the code.

35 points by matt_d 3y ago

Peeps are the type of thing that, once you realize what's going on, you can solve a whole new class of problems as if by magic. The cpython compiler's peephole optimizer is an easy code read and a great example of this in practice. The Apex compiler at Salesforce ONLY does peephole optimizations.

pfdietz 3y ago

That was not the kind of answer I was looking for. I was hoping to see "why is it that when peephole optimizations are applied, they often speed up the program?"

phkahler 3y ago
>> I was hoping to see "why is it that when peephole optimizations are applied, they often speed up the program?" Because that's what the optimizations are designed to do? The example in the post replaces 3 instructions with 2 that produce the same result. Assuming all the instructions involved take the same number of clock cycles, 2 < 3 will run faster. My understanding is that peephole optimizations usually get implemented when people study the output of the compiler and notice instruction sequences that can be shortened. Usually the sequences are somewhat common, so the optimization makes sense to implement.
- tedunangst 3y ago
  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?

russdill 3y ago

lol, had no idea what peephole optimizations were, but reading about them instantly brought back memories of reverse engineering byte code obfuscation as some 99% of the generated byte code is useless moving around of data that could be compacted into tighter representations. And yes, it consisted of a set of a large pattern matching rules that would be matched against windows of the code.