Re: [tree-ssa] CCP inefficiencies

[Diego Novillo <dnovillo at redhat dot com>]

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_nondestructive
> > or whatever.  The number of cases we care about are actually a small subset
> > 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_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.


Diego.