[tree-ssa] CCP inefficiencies

[law@redhat.com]

In message <20030214141504.GA2330@tornado.toronto.redhat.com>, Diego Novillo wr
ites:
 >On Fri, 14 Feb 2003, Jeff Law wrote:
 >
 >> Ping-ponging isn't allowed.
 >>
 >Of course not.  Not only it's not allowed, it's impossible.  The
 >algorigthm is designed to only make state changes that move up
 >the lattice, you cannot transition down.  I didn't want to imply
 >ping-pong effects.  My point was that once folded, an expression
 >may need to be unfolded.
Or we do non-destructive folds.  

 >> CONSTANT->CONSTANT is not allowed (which is
 >> something your code gets wrong).
 >> 
 >C -> C is not a state change.  How can we get it wrong?  Are you
 >saying that there are cases where we transition sideways in the
 >lattice?  We can switch a variable from one constant value C1 to
 >different constant value C2?  Eek, that shouldn't.  Do you have a
 >testcase?
I was pretty sure I saw sideways transitions, but I can't trigger
one right now.  Odd.  Regardless if you look at how set_lattice_value
works, it'll claim the value is still a constant even if it has
two different constant values.  It's easy enough to fix.

I also believe we should be checking for invalid transitions under 
ENABLE_CHECKING.  

Checks for invalid transitions into CONSTANT are easy.
(UNDEFINED->CONSTANT is OK, VARYING->CONSTANT is not)

It's easy to check CONSTANT->UNDEFINED, which is of course invalid.
Unfortunately, adding checks for VARYING->UNDEFINED is not possible
at this time due to our implementation of CCP.

Let's say we've just evaluated a node for the first time and the
evaluation returned UNDEFINED (say for the SSA_NAME destination of a
PHI node).  We go to set the lattice value to undefined (def_to_undefined).
The first thing that routine does is call get_value to get the object's
old value.  Since this is the first time we've accessed the value for this
SSA_NAME object, we get it's default value from get_default_value, which
is VARYING.  So it appears as if we're doing an UNDEFINED->VARYING
transition (which is of course invalid).   Oh well, it's not the end of
the world...

BTW, it's rather silly to call set_value if the lattice value hasn't
changed.


 >> A non-destructive folder will handle this just fine.
 >> 
 >Well, of course, that's the point :)  Do you think we should
 >re-implement fold()?  I think may_fold_p() should be good enough
 >for the time being.  But if you want to implement a
 >non-destructive folder, that's also fine with me.
Again, the number of cases we need to handle is drastically smaller
than what's dealt with in fold.  I really don't think it's going to 
be terribly difficult.


Jeff