[PATCH] Fix various reassoc issues (PR tree-optimization/58791, tree-optimization/58775)

[H.J. Lu]

On Tue, Oct 22, 2013 at 6:09 AM, Jakub Jelinek <jakub@redhat.com> wrote:
> Hi!
>
> I've spent over two days looking at reassoc, fixing spots where
> we invalidly reused SSA_NAMEs (this results in wrong-debug, as the added
> guality testcases show, even some ICEs (pr58791-3.c) and wrong range info
> for SSA_NAMEs) and cleaning up the stmt scheduling stuff (e.g. all gsi_move*
> calls are gone, if we need to "move" something or set an SSA_NAME to
> different value than previously, we'll now always create new
> stmt and the old one depending on the case either remove or mark as visited
> zero uses, so that it will be removed later on by reassociate_bb.
> Of course some gimple_assign_set_rhs* etc. calls are still valid even
> without creating new stmts, optimizing some statement to equivalent
> computation is fine, but computing something different in an old SSA_NAME
> is not.
>
> I've also noticed that build_and_add_sum was using different framework from
> rewrite_expr_tree, the former was using stmt_dominates_stmt_p (which is IMHO
> quite clean interface, but with the added uid stuff in reassoc can be
> unnecessarily slow on large basic blocks) and rewrite_expr_tree was using
> worse APIs, but using the uids.  So, the patch also unifies that, into
> a new reassoc_stmt_dominates_stmt_p that has the same semantics as the
> tree-ssa-loop-niter.c function, but uses uids internally.  rewrite_expr_tree
> is changed so that it recurses first, then handles current level (which is
> needed if the recursion needs to create new stmt and give back a new
> SSA_NAME), which allowed removing the ensure_ops_are_available recursive
> stuff.  Also, uids are now computed in break_up_subtract_bb (and are per-bb,
> starting with 1, we never compare uids from different bbs), which allows
> us to get rid of an extra whole IL walk.
>
> For the inter-bb optimization, I had to stop modifying stmts right away
> in update_range_test, because we don't want to reuse SSA_NAMEs and if we
> modified there, we'd need to modify potentially many dependent SSA_NAMEs
> and sometimes many times.  So, now it instead just updates oe->op values
> and maybe_optimize_range_tests just looks at those values and updates
> what is needed.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?
>
> For 4.8 a partial backport would be possible, but quite a lot of work,
> for 4.7 I'd prefer not to backport given that there gsi_for_stmt isn't O(1).
>
> 2013-10-22  Jakub Jelinek  <jakub@redhat.com>
>
>         PR tree-optimization/58775
>         PR tree-optimization/58791
>         * tree-ssa-reassoc.c (reassoc_stmt_dominates_stmt_p): New function.
>         (insert_stmt_after): Rewritten, don't move the stmt, but really
>         insert it.
>         (get_stmt_uid_with_default): Remove.
>         (build_and_add_sum): Use insert_stmt_after and
>         reassoc_stmt_dominates_stmt_p.  Fix up uid if bb contains only
>         labels.
>         (update_range_test): Set uid on stmts added by
>         force_gimple_operand_gsi.  Don't immediately modify statements
>         in inter-bb optimization, just update oe->op values.
>         (optimize_range_tests): Return bool whether any changed have
>         been made.
>         (update_ops): New function.
>         (struct inter_bb_range_test_entry): New type.
>         (maybe_optimize_range_tests): Perform statement changes here.
>         (not_dominated_by, appears_later_in_bb, get_def_stmt,
>         ensure_ops_are_available): Remove.
>         (find_insert_point): Rewritten.
>         (rewrite_expr_tree): Remove MOVED argument, add CHANGED argument,
>         return LHS of the (new resp. old) stmt.  Don't call
>         ensure_ops_are_available, don't reuse SSA_NAMEs, recurse first
>         instead of last, move new stmt at the right place.
>         (linearize_expr, repropagate_negates): Don't reuse SSA_NAMEs.
>         (negate_value): Likewise.  Set uids.
>         (break_up_subtract_bb): Initialize uids.
>         (reassociate_bb): Adjust rewrite_expr_tree caller.
>         (do_reassoc): Don't call renumber_gimple_stmt_uids.
>

It caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59154

H.J.