[PATCH]: Rewrite reassociation pass

[Daniel Berlin]

>>         * tree-ssa-dom.c (thread_across_edge): Canonicalize condition if
>>         necessary.
>>         (optimize_stmt): Ditto.
>>         (canonicalize_comparison): New function.
>>         * tree-ssa-operands.c (swap_tree_operands): Make external.
>>         (get_expr_operands): Stop auto-canonicalization.
>>         * tree-ssa-reassoc.c: Rewrite.
>
> It appears this pass relies heavily upon uniqueness of ranks,
> particularly in the simplication code.  ie, it assumes that
> entries in the op array with the same rank are equivalent
> (with the exception of rank 0).  Right?

No.
It doesn't assume things with the same rank are equivalent in value, but 
it does assume things with different ranks *do not have the 
same value* (which isn't quite the same).

IE it assumes rank(a) != rank(b) -> a != b, but not that rank(a) == 
rank(b) -> a == b

This is only for purposes of simplification.  It compares ->op == ->op in 
order to ensure they are actually the same name before doing anything.

If you see somewhere assuming this without checking, it's a bug, so please 
let me know where it is.  :)

>
> Assuming that's the case then it seems to me that we have a
> potential problem as we could have two SSA_NAMEs with the
> same rank with different values due to the way ranks are
> set of for BBs.

Yeah, it's unfortunate, but you can't win, because the rank isn't just a 
feature of the place in the BB, but of the place in the program as well, 
and we want to consider loop depth in what operands go where, to try to 
maximize the amount of code that can be moved for things that move 
statements at a time (which is most of our infrastructure).

I didn't want to make the comparison three way (rank, then loop depth, 
then value), because it makes other code more complex, and the current 
ranking scheme does "good enough" for all practical purposes.

> In eliminate_not_pairs, I don't understand how not-not should result
> in the value 0 being entered into the operand array for BIT_AND_EXPR,
> nor I do see how we should use -1 for BIT_IOR_EXPR.  It seems to me
> that in both cases we should just be eliminating the second not
> operation, rather than replacing the operand with 0 or -1.  What
> am I missing?

It's looking for A & ~A and A | ~A, not ~A & ~A, or ~A | ~A.

A & ~A -> 0
A | ~A -> -1

>
>
> You have a commented-out call to rewrite_expr_tree_new, which you
> should probably just delete.

yup.

>
> Over-long lines when incrementing reassociate_stats.opts_eliminated in
> a few places.

Fixed, thanks.
>
> In eliminate_using_constants, you've got BIT_AND_EXPR falling into
> BIT_IOR_EXPR.  It really seems to me that you want to keep those
> two cases separate.


I'm happy to do so.

>
> In linearize_expr_tree, I don't see where we linearize the
> lhs of the expression at all.

What do you mean LHS? It certainly recurses on the LHS of the binary 
operator.

You don't need to linearize the LHS of the *entire expression*, you 
can rewrite the operands and get the same result.

It is enough to
1. Collect all the operands that you need
2. Rewrite the binary operators that have the operands are both > depth 1 
directly into a linearize form.
3. Swap the operands so the > depth1 operator appears on the 
lhs (to make rewrite easier).

There are three cases to #2 above.

1. Both operands of the binary operator are leaves -> do nothing, it's 
linearized already (!binrhsreassoc && !binlhsreassoc)
2. One operand of the binary operator is a leave -> make sure the non-leaf 
appears on the left. (!binlhsreassoc && binrhsreassoc)
3. Both operands are non-leaves -> linearize so only one operation is 
a leaf. linearize_expr_tree calls linearize_expr to do this. YOu 
also need to recurse on the new non-leaf to make sure the condition holds 
there too (this is what linearize_expr does).  This is the binlhsreassoc 
&& binrhsreassoc case.

linearize_expr_tree recurses on the LHS in case it needs to linearize some 
subtree of it.  By the time we have hit that code, the LHS is always the 
operand that will be a non-leaf (if one exists in the expression).

So after linearize_expr_tree is done, you will end up with a left linear 
form tree, because only the deepest statement will have more than one 
leaf operand.

> Nor do I see where we
> linearize the rhs of the expression  if the lhs is not
> reassociable.

We do if the rhs of the binary op is still reassociable, because it 
switches the operands and recurses on the LHS one.


>  Am I reading something wrong?
It may be a bit hard to follow, but if you turn off the elimination, and 
look at the results of rewriting, you will see it will linearize 
everything fine :)

  >
> Have you tested to see if we can zap the not-not, neg-neg
> and reassociation code in DOM?

Nope.
That was never my goal, so i didn't check :)

I did want to provide a framework for someone more familiar with DOM, like 
you, to be able to easily remove the rest of the binary operator 
reassociation code that may exist there.  I'm just not familiar enough 
with the code to go there.