Removing operand normalizaiton in get_expr_operands

Removing operand normalizaiton in get_expr_operands

[Daniel Berlin]

Currently, get_expr_operands "renormalizes" the actual tree operands on
it's own whim , such that if you call update_stmt on something like "a +
c", it may be "c + a" after the call to update_stmt.
This is not the same as sorting the use operands, vuses, etc, which is
fine.

This is actually modifying the expression, so that TREE_OPERAND (rhs, 0)
before the call is not necessarily TREE_OPERAND (rhs, 0) after the call.

In the reassociation rewrite (which rewrites the resasoc pass so that it
catches all the things we've been looking for, like a & b & ~a & ~b,
etc), it's very nice if we can reorder the operands temporarily so that
the leaves are all to one side.
We also need to keep the immediate uses up to date as we move things
around, so that we have to call update_stmt.

If update_stmt reorders things, then you have to keep checking whether
the  thing you thought was a leaf before update_stmt, is still in the
same place, and reverse your operands, recurse on the correct side, etc.
It's quite ugly.  This ugliness happens during both linearization, and
later rewriting.

So I proposed to Andrew Macleod that we have an update_stmt interface
that lets us choose not to resort the actual operands, and i'll just
resort the expressions i touch when we are done.  He went me one better
and said we should just remove the code that is swapping the actual
operands around.

He didn't seem to remember why it was added.

Here's why i agree that it should be removed entirely:

1. operand_equal_p already takes into account commutative operations.
2. iterative_hash_expr does as well.
3. None of the optimizations are trying to use simple pointer
equivalence on actual binary operator arguments, AFAICT (Andrew said DOM
might, but i don't see where).
4. Calling update_stmt on a statement should not actually change the
statement itself.  It seems completely counter-intuitive.
5. Fold will already do this, and we should be using it where necessary
anyway.
6. It wastes some small amount of time to do this :)

The counter arguments i can see are:
1. Auto-canonicalization is theoretically nice.

Which is good and all, but it only helps if you are trying to see if the
expressions are exactly the same, and 
1. we use operand_equal_p for that anyway, because it knows more than we
do about which operands are really equal.
2. fold will put them in the right order anyway, and things that modify
or generate operations generally call fold.

So my proposal is to simply remove the code that does this in
tree-ssa-operands.c:get_expr_operands (search for tree_swap_operands to
see it).

Alternatively, i can just add the "no resort" interface.
(or of course, write the ugly code to keep rechecking which operands got
switched after each call to update_stmt :P)

Re: Removing operand normalizaiton in get_expr_operands

[Jeffrey A Law]

On Wed, 2005-08-24 at 13:22 -0400, Daniel Berlin wrote:
> Currently, get_expr_operands "renormalizes" the actual tree operands on
> it's own whim , such that if you call update_stmt on something like "a +
> c", it may be "c + a" after the call to update_stmt.
> This is not the same as sorting the use operands, vuses, etc, which is
> fine.
> 
> This is actually modifying the expression, so that TREE_OPERAND (rhs, 0)
> before the call is not necessarily TREE_OPERAND (rhs, 0) after the call.
> 
> In the reassociation rewrite (which rewrites the resasoc pass so that it
> catches all the things we've been looking for, like a & b & ~a & ~b,
> etc), it's very nice if we can reorder the operands temporarily so that
> the leaves are all to one side.
> We also need to keep the immediate uses up to date as we move things
> around, so that we have to call update_stmt.
> 
> If update_stmt reorders things, then you have to keep checking whether
> the  thing you thought was a leaf before update_stmt, is still in the
> same place, and reverse your operands, recurse on the correct side, etc.
> It's quite ugly.  This ugliness happens during both linearization, and
> later rewriting.
> 
> So I proposed to Andrew Macleod that we have an update_stmt interface
> that lets us choose not to resort the actual operands, and i'll just
> resort the expressions i touch when we are done.  He went me one better
> and said we should just remove the code that is swapping the actual
> operands around.
> 
> He didn't seem to remember why it was added.
> 
> Here's why i agree that it should be removed entirely:
> 
> 1. operand_equal_p already takes into account commutative operations.
> 2. iterative_hash_expr does as well.
> 3. None of the optimizations are trying to use simple pointer
> equivalence on actual binary operator arguments, AFAICT (Andrew said DOM
> might, but i don't see where).
> 4. Calling update_stmt on a statement should not actually change the
> statement itself.  It seems completely counter-intuitive.
> 5. Fold will already do this, and we should be using it where necessary
> anyway.
> 6. It wastes some small amount of time to do this :)
> 
> The counter arguments i can see are:
> 1. Auto-canonicalization is theoretically nice.
> 
> Which is good and all, but it only helps if you are trying to see if the
> expressions are exactly the same, and 
> 1. we use operand_equal_p for that anyway, because it knows more than we
> do about which operands are really equal.
> 2. fold will put them in the right order anyway, and things that modify
> or generate operations generally call fold.
> 
> So my proposal is to simply remove the code that does this in
> tree-ssa-operands.c:get_expr_operands (search for tree_swap_operands to
> see it).
The auto-canonicalization does present some problems.  No doubt about
that.  However, I was added specifically because it was allowing us
to eliminate more useless crud.  IIRC it was comparison elimination
that primarily benefited from auto canonicalization.

I don't recall any changes which would make the auto canonicalization
no longer necessary, but if you can show no ill effects before/after
removing auto canonicalization, then I won't object.


jeff

Re: Removing operand normalizaiton in get_expr_operands

[Richard Henderson]

On Wed, Aug 24, 2005 at 01:22:09PM -0400, Daniel Berlin wrote:
> Alternatively, i can just add the "no resort" interface.
> (or of course, write the ugly code to keep rechecking which operands got
> switched after each call to update_stmt :P)

I'd prefer we kill it.  Anything that relies on it ought to be
fairly localized, and we can adjust there.  But my guess is 
that nothing relies on it.


r~

Re: Removing operand normalizaiton in get_expr_operands

[Daniel Berlin]

> The auto-canonicalization does present some problems.  No doubt about
> that.  However, I was added specifically because it was allowing us
> to eliminate more useless crud.  IIRC it was comparison elimination
> that primarily benefited from auto canonicalization.

I think that part may have been superseded by VRP, which uses
operand_equal_p

(the remainings parts of DOM, including avail_expr_eq, for example, uses
operand_equal_p, which should handle that situation)

> 
> I don't recall any changes which would make the auto canonicalization
> no longer necessary, but if you can show no ill effects before/after
> removing auto canonicalization, then I won't object.

I'll run some numbers.

> 
> 
> jeff
> 
> 

Re: Removing operand normalizaiton in get_expr_operands

[Diego Novillo]

On 08/24/05 13:40, Richard Henderson wrote:
> On Wed, Aug 24, 2005 at 01:22:09PM -0400, Daniel Berlin wrote:
> 
>>Alternatively, i can just add the "no resort" interface.
>>(or of course, write the ugly code to keep rechecking which operands got
>>switched after each call to update_stmt :P)
> 
> 
> I'd prefer we kill it.
> 
That'd be my preference as well.