[tree-ssa] CCP inefficiencies

[law@redhat.com]

In message <1045190219.13192.138.camel@frodo>, Diego Novillo writes:
 >On Thu, 2003-02-13 at 11:42, Diego Novillo wrote:
 >> On Thu, 2003-02-13 at 11:38, law@redhat.com wrote:
 >> 
 >> > Rather than "fixing" fold, we introduce a new, simpler fold_nondestructiv
 >e
 >> > or whatever.  The number of cases we care about are actually a small subs
 >et
 >> > of the cases fold currently handles.
 >> > 
 >> OK.  I guess that we only need something along the lines of what Dan
 >> suggested: 'is this expression going to be folded into a constant?' 
 >> 
 >On second thought, what I said above is completely wrong.  Knowing that
 >the expression is constant is not enough, we *really* need to fold it to
 >compute and return its lattice value from tree-ssa-ccp.c:evaluate_stmt.
 >
 >The problem is that during the CCP pass, an expression may alternate
 >between constant and varying values.  Take for instance this code:
A value can only change twice.  The valid state changes are:
UNDEF->CONSTANT
UNDEF->VARYING
CONSTANT->VARYING

Ping-ponging isn't allowed.  CONSTANT->CONSTANT is not allowed (which is
something your code gets wrong).

 >a_1 = 5;
 >b_1 = 3;
 >a_2 = phi (a_1, a_3);
 >while (a < 10)
 >{
 >  c_1 = a_2 + b_1;
 >  if (c_1)
 >    d_1 = c_1 - 1;
 >  a_3 = a_2 + 1;
 >}
 >
 >On the first iteration, we enter the assignment to c_1 and find that all
 >its operands are constant, a_2 is 5 (because the only executable
 >argument for the phi node is a_1), and b_1 is 3.  However, knowing that
 >c_1 is a constant doesn't help us.  We need to fold the expression so
 >that we can set c_1's lattice value to 8.
 >
 >Suppose that we fold the original statement from 'c_1 = a_2 + b_1' to
 >'c_1 = 8'.  Now fast forward to the assignment 'a_3 = a_2 + 1'.  Again,
 >the same problem, knowing that a_3 is a constant doesn't help, you need
 >to fold it to find out that its value is 6.
 >
 >And now, we are screwed.  When we iterate back to a_2's phi node, we
 >find out that it isn't really constant, because it evaluates to 
 >'a_2 = phi (5, 6)'.  We now need to go back to 'c_1 = 8' and restore the
 >original expression.
 >
 >I guess what we could do is keep a deep copy of the original expression
 >in evaluate_stmt only if we determine that the call to fold() will
 >return a constant value.  But we must be able to fold and unfold
 >expressions at will.
A non-destructive folder will handle this just fine.

jeff