Search code examples
optimizationcompiler-constructioncompiler-development

Compiler Optimizations Questions

  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?
Solution

    1. I believe many compilers use SSAPRE (Static Single Assignment Partial Redundancy Elimination) to eliminate repeated expressions. This requires the code to be in SSA form, allowing many more optimizations.

    2. I'm not really sure about this one, but look at this list of LLVM passes. LLVM is an optimizing IR for compilers that is often faster than even GCC. There is a small explanation of each pass. If you need more info, look at the LLVM source for these passes. It is written in C++ but is quite clean and understandable.

    Edit: By the way, if you're developing a compiler, I highly recommend LLVM, it is very easy to use and generates highly optimized code.