This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH]: Rewrite reassociation pass
- From: Daniel Berlin <dberlin at dberlin dot org>
- To: Jeffrey A Law <law at redhat dot com>
- Cc: GCC Patches <gcc-patches at gcc dot gnu dot org>, Diego Novillo <dnovillo at redhat dot com>
- Date: Wed, 30 Nov 2005 17:47:34 -0500 (EST)
- Subject: Re: [PATCH]: Rewrite reassociation pass
- References: <1132963540.10982.25.camel@linux.site> <1133387154.1047.124.camel@fuel98>
* 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.