Compiler Design – Key Optimizations Explained

compiler

While studying about Optimization in Compiler Design I went through an article that tells about 'Algebraic Simplification And Reassociation' in optimization.It tells that using this(algebraic simplication) we could ignore code statements such as X = X * 1.

But I would like to know whether anyone uses these type of statements because naturally no one might never do such an multiplication.Or whether it shows any indirect optimization like breaking a huge code into statements then atlast getting these(X = X * 1) types of code statements.Could anyone help me.

Best Answer

The examples in the document you're linking to are (and are intended to be) simplified examples of a particular type of optimization. In the real world, of course, it isn't particularly likely that a developer is going to explicitly write a statement like x = x * 1 so it isn't particularly important that a compiler optimizes that specific statement. On the other hand, there are plenty of more complex transforms of this type that a compiler can implement that would be much more likely to come in handy for actual programs.

The article that you links to talks about how applying algebraic simplification and reassociationis frequently used to complement other optimizations. It can be used to rearrange expressions in order to implement operator strength reduction or constant folding or loop-invariant code motion. A lot of the algebraic transforms that the compiler is going to apply will be with the goal of doing things like collecting all the constant terms of an expression together so they can be factored out, collecting all the loop invariant terms together so that they can be moved outside the loop, etc.

One nice example of this is the "Algebraic Simplifications of Addressing Expressions" section in this word doc.

If you want an example of a case where a very simple transform would be used, imagine something like

[(4*(a + b))/ (4*a)] * c

doing algebraic simplification, you get

[(4*a + 4*b)/ (4*a)] * c
[(4*a)/(4*a) + (4*b)/(4*a)] * c
[1 + b/a] * c
(1*c) + (b/a)*c
c + (b*c)/a

The simplification 1*c = c comes toward the end and only after several other algebraic simplifications and transforms created that expression. Generally, it's not human developers that are writing that, it's the compiler applying other transforms that ultimately rely on the simple rules.

Related Topic