Re: PRE and loop invariants - or: how to wave a dead chicken and get away with it.

[Jeffrey A Law <law at cygnus dot com>]

  In message <9805231931.AA02263@moene.indiv.nluug.nl>you write:
  > >  If you think about it for a while you'll realize that
  > >  evaluating a loop invariant is a redundant evaluation on
  > >  a particular path (the path that loops).  PRE treats it
  > >  just like any other redundant expression.
  > 
  > But in what sense it's redundant (assuming no loop unrolling for  
  > the moment) ?
The expression may be evaluated more than once for some path through
the function (ie if the loop iterates more than once)

If its operands are invariant, then PRE will move the expression
into the loop header.

That's a slight over simplification, but that's the net result of
PRE's loop invariant code motion.

--

With newer PRE implementations (based on lazy code motion with full
critical edge splitting) it is even possible to prove that PRE
optimizations will produce a computationally optimal cfg.

I would expect lazy code motion along with conservative critical edge
splitting to be contributed later this year.  lcm will also serve
as the foundation for future stuff like spill code motion, downward
store motion, shrink wrapping, etc

--




  > Before you move the invariant, there's only the  
  > expression inside the loop; after you've moved it, there's the same  
  > expression outside the loop and the register containing its value  
  > referenced inside the loop.  I don't see any redundancy here (I only  
  > see a twisty maze of DAGs, all slightly different).
Imagine computing a + b in a loop when a & b are loop invariants.

PRE will move the computation of a+b outside the loop and store its
result into a new pseudoreg.  The expression in the loop then becomes
a copy from the new pseudo to the original target register (and often
the copy will be eliminated later by global copy propagation :-)


  > Strange - why don't I see that benefit then ?
Depends on what code you run :-)  Try spice2g6, it benefits from PRE's
loop invariant code motion.

One could certainly argue that if PRE's loop invariant code motion is
improving code that loop.c has some deficiencies.  I would agree :-)


jeff