Copyright (c) 2002, 2018, Oracle and/or its affiliates. All rights reserved.
DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

This code is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License version 2 only, as
published by the Free Software Foundation.

This code is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
version 2 for more details (a copy is included in the LICENSE file that
accompanied this code).

You should have received a copy of the GNU General Public License version
2 along with this work; if not, write to the Free Software Foundation,
Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
or visit www.oracle.com if you need additional information or have any
questions.

Eliminating common sub-expressions
----------------------------------

An expression E is called a common subexpression if E is previously computed,
and the values of variables in E have not changed since the previous computation.
We can then avoid recomputing the expression and use the previously computed value.

Consider the assignment statements below:

     -------------------------------------------
     |   Normal Code     |    Optimized Code   |
     -------------------------------------------
     |   T1 = B + C      |    T1 = B + C       |
     |   T2 = T1 - D     |    T2 = T1 - D      |
     |   A  = T2         |    A  = T2          |
     |   T3 = B + C      |    X  = T2          |
     |   T4 = T3 - D     |                     |
     |   X  = T4         |                     |
     -------------------------------------------

Notice that the expression assigned to T3 has already been computed and assigned
to T1, hence T3 is not needed, and T1 can be used instead.

Associative laws may also be applied to expose common subexpressions.

Example 1
---------
if the source code has the assignments

	a = b + c;
	e = c + d + b;

the following intermediate code might be generated:
	a = b + c;
	t = c + d;
	e = t + b;

If t is not needed outside of this block, this sequence can be changed to
	a = b + c;
	e = a + d;

Using both the associativity and commutativity of +.

Example 2
---------
        X = A * LOG(Y) + (LOG(Y) ** 2)

We introduce an explicit temporary variable t:

        t = LOG(Y)
        X = A * t + (t ** 2)

We saved one 'heavy' function call, by an elimination of
the common sub-expression LOG(Y), now we will save the
exponentiation by:

        X = (A + t) * t

which is much better. This is an old optimization trick that compilers are able to
perform quite well.

Example 3 - computing the value of a polynomial
-----------------------------------------------
Eliminating Common Subexpressions may inspire good algorithms like
the classic 'Horner's rule' for computing the value of a polynomial.

        y = A + B*x + C*(x**2) + D*(x**3)       (canonical form)

It is more efficient (i.e. executes faster) to perform the two
exponentiations by converting them to multiplications. In this way we
will get 3 additions and 5 multiplications in all.

The following forms are more efficient to compute, they require less
operations, and the operations that are saved are the 'heavy' ones
(multiplication is an operation that takes a lot of CPU time, much more
than addition).

Stage #1:

        y = A + (B + C*x + D*(x**2))*x

Stage #2 and last:

        y => A + (B + (C + D*x)*x)*x

The last form requires 3 additions and only 3 multiplications!

The algorithm hinted here, can be implemented with one loop to compute
an arbitrary order polynomial. It may also be better numerically than
direct computation of the canonical form.