Re: [PATCH]: Rewrite reassociation pass

[Jeffrey A Law <law at redhat dot com>]

On Fri, 2005-11-25 at 19:05 -0500, Daniel Berlin wrote:
> This rewrites the reassociation pass, with the following goals (over and
> above the current reassociation pass) in mind:
> 
> 1. Handle operands of binary operators, defined by binary operators,
> recursively. (the current reassoc can't do this because of the
> auto-canonicalization)
> 2. Combine and optimize these operand chains using various simple
> identities that other optimizations do not perform.
> 3. Preserve vector sum reduction opportunities, and try to create new
> ones where possible.
> 
> The new pass creates about 200 new redundancy elimination opportunities
> during a bootstrap, and optimizes a ton of operations that no other tree
> pass was getting when they were in any way split up into multiple
> statements.
> 
> It also disables the auto-canonicalization of operands, which only DOM
> depended on (as discussed during 4.1), in favor of simply doing that in
> DOM when necessary.  This is a small speedup.  The one case we can't
> auto-update the operand cache in swap_tree_operand (and have to call
> update_stmt) occurs exactly once during a gcc bootstrap, in a fortran
> testcase.
> 
> The new pass is roughly as fast as the old reassociation, it is
> basically bound by the time to compute post-dominators (since that is
> not usually up-to-date).  It rarely even shows up in time output, let
> alone profiles.
> 
> Because it can create dead code when it combines operations, i have
> moved reassoc to be placed before a DCE pass, rather than add a new one.
> 
> All of the reassoc-* testcases (new and old), and the better ssa-pre-2.c
> result, are still done with this moved, as is the optimization required
> to fix PR tree-optimization/15878.
> 
> I've attached tree-ssa-reassoc.c as a seperate file as well, since it
> has been mostly rewritten.
> 
> This patch is also part of a patch necessary to resolve PR
> tree-optimization/23619.
> 
> It also explains how to fix PR 16157 (the algorithm at the top), but we
> don't do it because it's expensive and rarely occurs.
> 
> Bootstrapped and regtested on i686-pc-linux-gnu.
> Okay for mainline?
> 
> 2005-11-25  Daniel Berlin  <dberlin@dberlin.org>
> 
> 	Fix PR tree-optimization/15878
>         * Makefile.in (tree-ssa-reassoc.o): Update dependencies.
>         * passes.c (init_optimization_passes): Move reassoc.
>         * tree-flow.h (swap_tree_operands): Declare.
>         * 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?

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.

  /* Set up rank for each BB  */
  for (i = 0; i < n_basic_blocks; i++)
    bb_rank[bbs[i]] = ++rank  << 16;

Given a large number of SSA_NAMEs (each with their own rank), we could
get a conflict between a bb rank and the rank for a totally unrelated
SSA_NAME.

If that bb rank were then used to determine the rank of some other
SSA_NAME, then we'd have two different SSA_NAMEs with the same
rank, which could then lead to incorrect transformations since we
don't check the underlying operands when (for example) we're
applying not-not optimizations.


I doubt this is likely to happen in practice, but it would probably
be good if we could bullet proof this code a little better.

What about the case where distinct SSA_NAMEs get the same rank from
a basic block rank?



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?


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

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

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.

BIT_AND_EXPR
   integer_zero
      wipe entire operand array
      add single zero entry into operand array
   all_ones
      remove last entry in operand array
   break;


BIT_IOR_EXPR
   integer_zero
     remove last entry in operand array
   all_ones
     wipe entire array
     add single all-ones entry into operand array
   break;

In linearize_expr_tree, I don't see where we linearize the 
lhs of the expression at all.  Nor do I see where we
linearize the rhs of the expression  if the lhs is not
reassociable.  Am I reading something wrong?

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

Jeff