[tree-ssa] CCP and non-destructive folding problems

[law@redhat.com]

In message <1046195984.1798.49.camel@shadowfax>, Diego Novillo writes:
 >On Tue, 2003-02-25 at 12:48, law@redhat.com wrote:
 >
 >> Noted.  I'll probably pick them up after the bootstrap & test is finished
 >> which fixes how we handled undefined expressions and re-enables the
 >> VARYING->CONSTANT state checking.
 >> 
 >OK.
 >
 >>  >Au contraire.  The algorithm completes in fewer iterations.  Remember
 >>  >that UNDEFINED values are short circuit for PHI expression evaluations. 
 >>  >They imply no change of state.  Ergo, the main loop finishes sooner.
 >> But if you've got a transition from VARYING back to CONSTANT, what's to
 >> stop you from ping-ponging between VARYING and CONSTANT?  That's one of
 >> the key concepts behind the algorithm and its allowable state changes.
 >> 
 >I was talking about evaluate_stmt() returning UNDEFINED.  There are two
 >cases:
 >
 >(a) If evaluate_stmt() returns UNDEFINED on something that really is
 >VARYING or CONSTANT, we have a hard bug.  The short circuit evaluation
 >of PHI nodes for UNDEFINED values will cut CCP short and produce wrong
 >results.
We must be talking past each other.

If evaluate_stmt only returns UNDEFINED when one or more of the operands
is UNDEFINED, then we are safe -- unless there a bugs elsewhere in our
implementation.  That's a fundamental part of the CCP algorithm.

The case you pointed out in an earlier message was mis-compiled because
evaluate_stmt returned UNDEFINED when all of the operands to a particular
expression were constants, but we were unable to fold the expression.
If instead it returned VARYING (which is the correct return value if we
can't fold something which has all constants), then things would have 
worked just fine.

Now in the case where all the operands are constants, but we failed to
fold the expression we have a "soft" failure if we return VARYING.  ie,
we fail to optimize the code as much as we should.  Investigating to see
how many of these are still lurking would be a good thing to do.


 >(b) If evaluate_stmt() returns VARYING on something that really is
 >UNDEFINED or VARYING, we have a soft bug.  We will merely be producing
 >worse code because we won't propagate as many constants.  We will also
 >probably abort compilation if CCP tries to do a VARYING->anything
 >transition (I'm assuming that you will reinstate the checks that I
 >#ifdef'd out).
 >
 >It's (a) that I'm more concerned about.
If we get any VARYING->anything transitions, then that indicates a bug
in our implementation.  Such transitions should never occur.  If they do,
then we've got a bug.

Jeff