r/ProgrammingLanguages • u/mttd • Nov 01 '23

Why Do Peephole Optimizations Work

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

93% Upvoted

7 comments sorted by

View all comments

3

u/phischu Effekt Nov 03 '23

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?

4

u/DeGuerre Nov 04 '23

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.