This is the mail archive of the
mailing list for the GCC project.
Re: [tree-ssa] CCP inefficiencies
On Thu, 2003-02-13 at 11:42, Diego Novillo wrote:
> On Thu, 2003-02-13 at 11:38, email@example.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;
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
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.