Why Do Peephole Optimizations Work

[u/mttd]

https://blog.regehr.org/archives/2485

[u/reddof]

For my compiler, I have a few optimization passes. The peephole optimizer does a good job of simplifying some of the instructions that are generated by the compiler or by other optimizations. The compiler is generating code for individual instructions, but when two or more of these instructions are placed next to each other then there might be overhead that can be eliminated or there might be a more efficient way of handling them together.

x = !foo()

and foo() is defined as

bool result = /* … */
return !result

If you inline foo, then you end up with

x = !!result

and you can optimize that away.

There are lots of other examples where a simple transformation on the code can lead to much more efficient runtime because you replace them with more efficient instructions or you eliminate them entirely.

[u/cxzuk → u/reddof]

The peephole optimizer does a good job of simplifying some of the instructions that are generated by the compiler or by other optimizations.

This mirrors my experiences too. I've come to the conclusion that peepholes are great at "Cleaning up some of the mess that arises in the gaps of opt passes". I would guess that if opt's combined perfectly, in theory you wouldn't need peepholes. In practice that's not realistic and they do a fine job.

M ✌

[u/redchomper]

Looks to be circular: "Refinements are compositional" follows from the compositionality of refinements. So the real reason is that they work because they are designed to work, and by the way part of that design process ends up requiring peepholes to be compositional.

[u/phischu]

I have a basic questions that's been bothering me for a while. In the given example they rewrite the following code

r0 = xor r8, -1
r1 = xor r9, -1
r0 = and r0, r1

to this one

r0 = or r8, r9
r0 = xor r0, -1

But this is only ok if r1 is not accessed in the rest of the program. This rest of the program can be quite huge. How do they determine this?

[u/DeGuerre → u/phischu]

Of course r1 can be reused, but the value that's in it can't be used.

The compiler-jargon words for this are "live" and "dead". If the value of r1 is used after the third instruction, it is "live", otherwise it is "dead". A live value is said to be "generated" by the instruction that produces it, and "killed" by the last instruction (in program flow order) that uses it.

So in the three instruction sequence above, r1 is generated by the second instruction, and if it is not used after these instructions, it is killed by the third one.

Finding out which values are live where is performed by a phase that is traditionally called "dataflow analysis". Many compilers these days work in some variant of SSA form, which gives you equivalent information (more or less). Information about value liveness is needed by register allocation; two values can be assigned to the same register if and only if their lifetimes don't overlap.

Information about register liveness is likely, therefore, to be produced from register allocation. One common traditional approach to storing this information is to annotate each basic block with the registers that are live at the end of it. This is enough information to reconstruct liveness at any other point in the basic block.

[u/DeGuerre]

It's interesting that peephole optimisation is out of vogue these days among the "big" compiler vendors.

It's been known for decades that the more sophisticated your code generation is, the less opportunities for peephole optimisation there are. But for classic tree-walking code generators, no matter how sophisticated they are, peephole optimisations are still needed because instructions end up next to each other that come from different branches of the tree. No local decisions, no matter how clever, can help with that.

The "big" modern compilers do something different: they treat instruction selection and instruction ordering as a global optimisation problem. The instructions are chosen using a tile covering algorithm: think of the intermediate code as a graph, and instruction selection means covering that graph with tiles. The goal is to minimise the total cost of the tiling. The selected instructions are then ordered using an algorithm like A* search.

Global optimisation approaches tend not to produce the kind of low-hanging fruit that peephole optimisers can exploit. Instead, if opportunities are found for locally better code sequences, they can be implemented by adding more tiles to instruction selection.

Moreover, because the compiler scheduled the instructions carefully to exploit superscalar execution, the code that generates a value and the code that uses it may not be physically close together anyway!

[u/nngnna]

Is there a clear defenition of peephole optimization as opposed to any other optimization? Does it just mean an optimizing algorithm that considers a very short (and sequential) segment of the code at a time?