0

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.

  • 3
    It is pretty common in surprising places, and if applied inside a loop body, can save lots of cycles. I don't have time to write a thorough answer, but yes, there are lots of places where these algebraic facts can be used to simplify the code and turn expressions to constants at compile-time rather than evaluating them at runtime. Take a look at peephole optimizations. – zxcdw Nov 15 '14 at 6:43
  • 1
    One thing to point out is that in a language that uses templates, like c++, compile time constants are frequently passed in, which could generate code that has lots of "obvious" algebraic optimizations to the compiler (optimizations which are not possible if used as a run time variable). This is a useful side effect of using templates. – Red Alert Nov 15 '14 at 8:25
4

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.

  • Could you list out any one complex transform of this (x=x*1) type of statement.I would like to know if one really exist. – justin Nov 15 '14 at 7:35
  • @justin - I updated the answer with one example of a complex multi-step simplification that would use various simple transforms such as x=x*1. – Justin Cave Nov 15 '14 at 7:47
2

Statements like x = x * 1 or y = y + 0 are more common than you might think. They may not be written exactly in that form in the (high-level) source code, but they occur frequently after converting the high-level code to three-address code.
Other optimisations, such as constant propagation, may also result in such trivial expressions.

A very common construct that can yield the expression y = y + 0 in three-address code is accessing the very first member of a compound data structure or class (in OO languages, this is often the vtable used for virtual dispatch).

  • But could you tell me what do you mean by 'virtual dispatch' and 'vtable'. – justin Nov 15 '14 at 7:52
  • @justin: Wikipedia can explain it better: en.wikipedia.org/wiki/Virtual_method_table. virtual dispatch is also known as dynamic dispatch. – Bart van Ingen Schenau Nov 15 '14 at 7:58
  • :I looked wikipedia but couldn't really get the cat and lion example for 'virtual method table'.Could you explain in it in simple terms. – justin Nov 15 '14 at 8:03
  • @justin:Are you comfortable with programming in OO languages? – Bart van Ingen Schenau Nov 15 '14 at 8:14
  • 1
    @justin: A proper explanation takes too much room for a comment. A vtable is basically how a C++ compiler knows which method from a derived class to invoke when you call a virtual method. – Bart van Ingen Schenau Nov 15 '14 at 8:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.