On Wed, 9 Feb 2005 11:43:34 +0200, Radu Grigore <radugrigore@gmail.com> wrote:

> 1. hold the original value of a variable
> 2. hold the result of an expression and write it later to the destination
> 
> Point (1) requires one extra assignment, while point (2) requires two
> extra assignments. The effect is however the same: one of the
> variable's value can be computed as soon as desired. Therefore we will
> only use (1). [NOTE that your approach used (2) and hence is clearly
> sub-optimal].

One more mistake. Both approaches introduce _one_ extra assignment and
the algorithm described subsequently is independent on the choice of
(1) or (2).

For the problem:
a = b+c
b = c
c = a+b

The algorithm says: introduce a temporary for c, and the order is c, a, b.
With choice (1) the solution is the one I already wrote. With choice (2) it is:

// compute temporaries
t = a+b

// compute c, a, b (skip c because we have temporary, this is what I missed)
a = b+c
b = c

// use temporaries
c = t

... for a total of 4 assignments (same as with choice 1). This is
better than the 5 assignments given by your algorithm and it does NOT
depend on breaking the rule about using temporaries only to save
results of expressions (but not initial values).

-- 
regards,
 radu
http://rgrig.idilis.ro/