Compiler Optimizations Questions

Question

1. What are some of the ways a compiler eliminates repeated subexpressions recomputations? How do you keep track of the sub-expressions? And How do you identify the repeated ones?
2. Besides the usage of bitwise operators, what are some of the strength reduction techniques common compilers use?

Answer 1

For 1, The name of the optimization you're looking for is common subexpression elimination (CSE). Depending on your representation, this can be fairly easy. Usually, a compiler will have some intermediate representation of a program where operations are broken down as much as possible and linearized. So for example, the expression c = a * b + a * b might be broken down as:

v1 = a * b
v2 = a * b
c = v1 + v2

So you could do CSE at a very low level by looking for operations with the same operator and operands. When you encounter a duplicate (v2 in this case), you replace all instances of it with the original. So we could simplify the code above to be:

v1 = a * b
c = v1 + v1

This generally assumes that you only assign each variable once (single static assignment form), but you can implement something like this without that restriction. This gets more complicated when you try and perform this optimization across branches. As Zifre mentions, look into Partial Redundancy Elimination.

Either way, you get some basic improvement, and all you need to keep track of are basic expressions. You may want to take this a step further and look for arithmetic identities. For instance, a * b is the same as b * a. Also, x * (y + z) = x * y + x * z. This makes your optimization more complicated, and it's not clear that it would give you that much performance improvement. Anecdotally, most of the benefit from a CSE optimization comes from address computations like array accesses, and you won't need complicated identities like the ones above.

For 2, what strength reductions are useful really depends on the architecture you compile for. Usually this just involves transforming multiplications and divisions into shifts, additions, and subtractions.