Re: [RFC PATCH] Reassociate MINUS_EXPRs

[Richard Guenther <richard dot guenther at gmail dot com>]

On Tue, Apr 13, 2010 at 7:02 PM, Alexander Monakov <amonakov@ispras.ru> wrote:
> Hi,
>
> [Michael, I have verified that your testcases pass with this approach;
> ?Maxim, this patch collides with the reassoc bug you are working on. ?]
>
> This makes MINUS_EXPRs reassociable with PLUS_EXPRs in tree-ssa-reassoc.c,
> en passant getting rid of somewhat expensive gimple rewriting that happens in
> break_up_subtract and repropagate_negates.
>
> The patch now allows not only SSA_NAMEs and constants, but also NEGATE_EXPRs
> as operands in struct operand_entry. ?Thus, linearize_expr_tree collects
> operands from trees of {PLUS,MINUS}_EXPRs into additive pool (thus, walking
> A - (B - C) places A, -B, C into ops vector). ?Later, rewrite_expr initially
> produces statements with PLUS_EXPRs and possibly negated operands; such
> statements are fixed by fixup_negates that does some minimal surgery on gimple
> to restore correctness.
>
> The patch is not complete -- at the very least I'll have to add testcase(s)
> and update some comments. ?I thought I'd get some initial review first.
>
> Bootstrapped and regtested on x86_64-linux. ?There is a couple of test
> failures where the patch negates a floating-point constant, producing x + -5.0
> instead of x - 5.0. ?What should I do about those?

The canonical form is 5.0, not -5.0 to save in constant pool size and
constant pool references.

I didn't look at the patch at all.

Richard.

> 2010-04-13 ?Alexander Monakov ?<amonakov@ispras.ru>
>
> ? ? ? ?* tree-ssa-reassoc.c (get_rank): Handle NEGATE_EXPRs in operands.
> ? ? ? ?(get_unary_op): Likewise.
> ? ? ? ?(eliminate_plus_minus_pair): Likewise.
> ? ? ? ?(is_reassociable_op): Reassociate PLUS_EXPRs with MINUS_EXPRs and vice
> ? ? ? ?versa.
> ? ? ? ?(fixup_negates): New. ?Use it...
> ? ? ? ?(rewrite_expr_tree): ... here. ?If the statement RHS was MINUS_EXPR
> ? ? ? ?originally, change it to PLUS_EXPR. ?Strip NEGATE_EXPRs from operands
> ? ? ? ?before testing whether rhs1 is no longer used.
> ? ? ? ?(linearize_expr): Handle MINUS_EXPRs.
> ? ? ? ?(reassociate_bb): Ditto.
> ? ? ? ?(negate_and_add_to_ops_vec): New. ?Use it...
> ? ? ? ?(linearize_expr_tree): ... here. ?Handle MINUS_EXPRs. ?Add new
> ? ? ? ?argument (negate). ?Update prototype and all callers.
> ? ? ? ?(dump_ops_vector): Print a new line between entries.
> ? ? ? ?(get_single_immediate_use): Remove.
> ? ? ? ?(negate_value): Ditto.
> ? ? ? ?(should_break_up_subtract): Ditto.
> ? ? ? ?(break_up_subtract): Ditto.
> ? ? ? ?(repropagate_negates): Ditto.
> ? ? ? ?(break_up_subtract_bb): Ditto.
>
> diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c
> index 54a0413..0e01f44 100644
> --- a/gcc/tree-ssa-reassoc.c
> +++ b/gcc/tree-ssa-reassoc.c
> @@ -289,6 +289,12 @@ get_rank (tree e)
> ? ? ? insert_operand_rank (e, (rank + 1));
> ? ? ? return (rank + 1);
> ? ? }
> + ?else if (TREE_CODE (e) == NEGATE_EXPR)
> + ? ?{
> + ? ? ?long rank = get_rank (TREE_OPERAND (e, 0));
> + ? ? ?insert_operand_rank (e, (rank + 1));
> + ? ? ?return (rank + 1);
> + ? ?}
>
> ? /* Globals, etc, ?are rank 0 */
> ? return 0;
> @@ -367,9 +373,16 @@ is_reassociable_op (gimple stmt, enum tree_code code, struct loop *loop)
> ? ? return false;
>
> ? if (is_gimple_assign (stmt)
> - ? ? ?&& gimple_assign_rhs_code (stmt) == code
> ? ? ? && has_single_use (gimple_assign_lhs (stmt)))
> - ? ?return true;
> + ? ?{
> + ? ? ?enum tree_code rhscode = gimple_assign_rhs_code (stmt);
> + ? ? ?if (rhscode == MINUS_EXPR)
> + ? ? ? rhscode = PLUS_EXPR;
> + ? ? ?if (code == MINUS_EXPR)
> + ? ? ? code = PLUS_EXPR;
> + ? ? ?if (rhscode == code)
> + ? ? ? return true;
> + ? ?}
>
> ? return false;
> ?}
> @@ -381,7 +394,16 @@ is_reassociable_op (gimple stmt, enum tree_code code, struct loop *loop)
> ?static tree
> ?get_unary_op (tree name, enum tree_code opcode)
> ?{
> - ?gimple stmt = SSA_NAME_DEF_STMT (name);
> + ?gimple stmt;
> +
> + ?if (TREE_CODE (name) == NEGATE_EXPR)
> + ? ?{
> + ? ? ?if (opcode == NEGATE_EXPR)
> + ? ? ? return TREE_OPERAND (name, 0);
> + ? ? ?return NULL_TREE;
> + ? ?}
> +
> + ?stmt = SSA_NAME_DEF_STMT (name);
>
> ? if (!is_gimple_assign (stmt))
> ? ? return NULL_TREE;
> @@ -486,7 +508,8 @@ eliminate_plus_minus_pair (enum tree_code opcode,
> ? unsigned int i;
> ? operand_entry_t oe;
>
> - ?if (opcode != PLUS_EXPR || TREE_CODE (curr->op) != SSA_NAME)
> + ?if (opcode != PLUS_EXPR || (TREE_CODE (curr->op) != SSA_NAME
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? && TREE_CODE (curr->op) != NEGATE_EXPR))
> ? ? return false;
>
> ? negateop = get_unary_op (curr->op, NEGATE_EXPR);
> @@ -759,7 +782,7 @@ eliminate_using_constants (enum tree_code opcode,
>
>
> ?static void linearize_expr_tree (VEC(operand_entry_t, heap) **, gimple,
> - ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?bool, bool);
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?bool, bool, bool);
>
> ?/* Structure for tracking and counting operands. ?*/
> ?typedef struct oecount_s {
> @@ -1041,7 +1064,7 @@ undistribute_ops_list (enum tree_code opcode,
> ? ? ? oedef = SSA_NAME_DEF_STMT (VEC_index (operand_entry_t, *ops, i)->op);
> ? ? ? oecode = gimple_assign_rhs_code (oedef);
> ? ? ? linearize_expr_tree (&subops[i], oedef,
> - ? ? ? ? ? ? ? ? ? ? ? ? ?associative_tree_code (oecode), false);
> + ? ? ? ? ? ? ? ? ? ? ? ? ?associative_tree_code (oecode), false, false);
>
> ? ? ? for (j = 0; VEC_iterate (operand_entry_t, subops[i], j, oe1); ++j)
> ? ? ? ?{
> @@ -1320,6 +1343,98 @@ remove_visited_stmt_chain (tree var)
> ? ? }
> ?}
>
> +/* Adjust STMT if it has NEGATE_EXPRs as operands by swapping them or changing
> + ? operation from PLUS_EXPR to MINUS_EXPR or vice versa. ?If that fails,
> + ? negate the LHS of the STMT and fixup the single use of LHS. ?If LHS has
> + ? multiple uses or is not used in a {PLUS,MINUS}_EXPR, emit a new statement
> + ? that negates the LHS. ?*/
> +
> +static void
> +fixup_negates (gimple stmt)
> +{
> + ?enum tree_code rhscode, negcode;
> + ?tree rhs1 = gimple_assign_rhs1 (stmt);
> + ?tree rhs2 = gimple_assign_rhs2 (stmt);
> + ?bool need_update = false;
> + ?rhscode = gimple_assign_rhs_code (stmt);
> + ?negcode = rhscode == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR;
> +
> + ?if (rhscode != PLUS_EXPR && rhscode != MINUS_EXPR)
> + ? ?return;
> +
> + ?if (TREE_CODE (rhs2) == NEGATE_EXPR)
> + ? ?{
> + ? ? ?/* Change A + -B to A - B, A - -B to A + B */
> + ? ? ?gimple_assign_set_rhs_code (stmt, negcode);
> + ? ? ?gimple_assign_set_rhs2 (stmt, TREE_OPERAND (rhs2, 0));
> + ? ? ?need_update = true;
> + ? ? ?rhscode = negcode;
> + ? ? ?negcode = rhscode == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR;
> + ? ?}
> + ?if (TREE_CODE (rhs1) == NEGATE_EXPR)
> + ? ?{
> + ? ? ?/* Change -A + B to A - B, -A - B to A + B */
> + ? ? ?gimple_assign_set_rhs_code (stmt, negcode);
> + ? ? ?gimple_assign_set_rhs1 (stmt, TREE_OPERAND (rhs1, 0));
> + ? ? ?need_update = true;
> + ? ? ?if (rhscode == PLUS_EXPR)
> + ? ? ? {
> + ? ? ? ? /* If we had -A + B, this results in B - A */
> + ? ? ? ? swap_tree_operands (stmt,
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? gimple_assign_rhs1_ptr (stmt),
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? gimple_assign_rhs2_ptr (stmt));
> + ? ? ? }
> + ? ? ?else
> + ? ? ? {
> + ? ? ? ? /* We have just changed -A - B to A + B. ?Deal with the fact that
> + ? ? ? ? ? ?LHS is now opposite to what it originally was. ?*/
> + ? ? ? ? use_operand_p immuse;
> + ? ? ? ? gimple immusestmt;
> + ? ? ? ? tree negated, lhs = gimple_assign_lhs (stmt);
> +
> + ? ? ? ? gcc_assert (TREE_CODE (lhs) == SSA_NAME);
> + ? ? ? ? single_imm_use (lhs, &immuse, &immusestmt);
> + ? ? ? ? if (immusestmt && is_gimple_assign (immusestmt))
> + ? ? ? ? ? {
> + ? ? ? ? ? ? enum tree_code immusecode = gimple_assign_rhs_code (immusestmt);
> +
> + ? ? ? ? ? ? if (immusecode == PLUS_EXPR || immusecode == MINUS_EXPR)
> + ? ? ? ? ? ? ? {
> + ? ? ? ? ? ? ? ? /* Propagate (-LHS) into single use and tail recurse. ?*/
> + ? ? ? ? ? ? ? ? negated = build1 (NEGATE_EXPR, TREE_TYPE (lhs), lhs);
> + ? ? ? ? ? ? ? ? SET_USE (immuse, negated);
> +
> + ? ? ? ? ? ? ? ? update_stmt (stmt);
> + ? ? ? ? ? ? ? ? fixup_negates (immusestmt);
> + ? ? ? ? ? ? ? ? return;
> + ? ? ? ? ? ? ? }
> + ? ? ? ? ? ? else if (immusecode == NEGATE_EXPR)
> + ? ? ? ? ? ? ? {
> + ? ? ? ? ? ? ? ? /* LHS was used in NEGATE_EXPR and is now negated itself. ?*/
> + ? ? ? ? ? ? ? ? SET_USE (immuse, lhs);
> + ? ? ? ? ? ? ? ? update_stmt (stmt);
> + ? ? ? ? ? ? ? ? return;
> + ? ? ? ? ? ? ? }
> + ? ? ? ? ? }
> + ? ? ? ? ? {
> + ? ? ? ? ? ? /* We could not propagate (-LHS) into its use(s). ?Emit a new
> + ? ? ? ? ? ? ? ?statement with the negation. ?*/
> + ? ? ? ? ? ? gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
> + ? ? ? ? ? ? tree new_lhs = make_ssa_name (SSA_NAME_VAR (lhs), NULL);
> + ? ? ? ? ? ? gimple new_stmt;
> +
> + ? ? ? ? ? ? gimple_assign_set_lhs (stmt, new_lhs);
> + ? ? ? ? ? ? negated = build1 (NEGATE_EXPR, TREE_TYPE (new_lhs), new_lhs);
> + ? ? ? ? ? ? new_stmt = gimple_build_assign (lhs, negated);
> + ? ? ? ? ? ? gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
> + ? ? ? ? ? ? need_update = true;
> + ? ? ? ? ? }
> + ? ? ? }
> + ? ?}
> + ?if (need_update)
> + ? ?update_stmt (stmt);
> +}
> +
> ?/* Recursively rewrite our linearized statements so that the operators
> ? ?match those in OPS[OPINDEX], putting the computation in rank
> ? ?order. ?*/
> @@ -1332,6 +1447,9 @@ rewrite_expr_tree (gimple stmt, unsigned int opindex,
> ? tree rhs2 = gimple_assign_rhs2 (stmt);
> ? operand_entry_t oe;
>
> + ?if (gimple_assign_rhs_code (stmt) == MINUS_EXPR)
> + ? ?gimple_assign_set_rhs_code (stmt, PLUS_EXPR);
> +
> ? /* If we have three operands left, then we want to make sure the one
> ? ? ?that gets the double binary op are the ones with the same rank.
>
> @@ -1402,7 +1520,14 @@ rewrite_expr_tree (gimple stmt, unsigned int opindex,
>
> ? ? ? ? ?gimple_assign_set_rhs1 (stmt, oe1->op);
> ? ? ? ? ?gimple_assign_set_rhs2 (stmt, oe2->op);
> + ? ? ? ? fixup_negates (stmt);
> ? ? ? ? ?update_stmt (stmt);
> +
> + ? ? ? ? if (TREE_CODE (oe1->op) == NEGATE_EXPR)
> + ? ? ? ? ? oe1->op = TREE_OPERAND (oe1->op, 0);
> + ? ? ? ? if (TREE_CODE (oe2->op) == NEGATE_EXPR)
> + ? ? ? ? ? oe2->op = TREE_OPERAND (oe2->op, 0);
> +
> ? ? ? ? ?if (rhs1 != oe1->op && rhs1 != oe2->op)
> ? ? ? ? ? ?remove_visited_stmt_chain (rhs1);
>
> @@ -1450,6 +1575,7 @@ rewrite_expr_tree (gimple stmt, unsigned int opindex,
> ? ? ? ?}
>
> ? ? ? gimple_assign_set_rhs2 (stmt, oe->op);
> + ? ? ?fixup_negates (stmt);
> ? ? ? update_stmt (stmt);
>
> ? ? ? if (dump_file && (dump_flags & TDF_DETAILS))
> @@ -1474,6 +1600,7 @@ linearize_expr (gimple stmt)
> ? gimple binlhs = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
> ? gimple binrhs = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
> ? enum tree_code rhscode = gimple_assign_rhs_code (stmt);
> + ?enum tree_code binrhscode = gimple_assign_rhs_code (binrhs);
> ? gimple newbinrhs = NULL;
> ? struct loop *loop = loop_containing_stmt (stmt);
>
> @@ -1484,8 +1611,16 @@ linearize_expr (gimple stmt)
> ? gsirhs = gsi_for_stmt (binrhs);
> ? gsi_move_before (&gsirhs, &gsinow);
>
> + ?/* (A+B)+-(C+D) -> (A+B)+-C */
> ? gimple_assign_set_rhs2 (stmt, gimple_assign_rhs1 (binrhs));
> + ?/* C+D -> (A+B)+D */
> ? gimple_assign_set_rhs1 (binrhs, gimple_assign_lhs (binlhs));
> + ?if (rhscode == MINUS_EXPR)
> + ? ?gimple_assign_set_rhs_code (binrhs,
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? binrhscode == MINUS_EXPR
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? PLUS_EXPR
> + ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? : MINUS_EXPR);
> + ?/* (A+B)+-C -> ((A+B)+D)+-C */
> ? gimple_assign_set_rhs1 (stmt, gimple_assign_lhs (binrhs));
>
> ? if (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
> @@ -1513,117 +1648,21 @@ linearize_expr (gimple stmt)
> ? ? linearize_expr (stmt);
> ?}
>
> -/* If LHS has a single immediate use that is a GIMPLE_ASSIGN statement, return
> - ? it. ?Otherwise, return NULL. ?*/
> -
> -static gimple
> -get_single_immediate_use (tree lhs)
> -{
> - ?use_operand_p immuse;
> - ?gimple immusestmt;
> -
> - ?if (TREE_CODE (lhs) == SSA_NAME
> - ? ? ?&& single_imm_use (lhs, &immuse, &immusestmt)
> - ? ? ?&& is_gimple_assign (immusestmt))
> - ? ?return immusestmt;
> -
> - ?return NULL;
> -}
> -
> -/* Recursively negate the value of TONEGATE, and return the SSA_NAME
> - ? representing the negated value. ?Insertions of any necessary
> - ? instructions go before GSI.
> - ? This function is recursive in that, if you hand it "a_5" as the
> - ? value to negate, and a_5 is defined by "a_5 = b_3 + b_4", it will
> - ? transform b_3 + b_4 into a_5 = -b_3 + -b_4. ?*/
> -
> -static tree
> -negate_value (tree tonegate, gimple_stmt_iterator *gsi)
> -{
> - ?gimple negatedefstmt= NULL;
> - ?tree resultofnegate;
> -
> - ?/* If we are trying to negate a name, defined by an add, negate the
> - ? ? add operands instead. ?*/
> - ?if (TREE_CODE (tonegate) == SSA_NAME)
> - ? ?negatedefstmt = SSA_NAME_DEF_STMT (tonegate);
> - ?if (TREE_CODE (tonegate) == SSA_NAME
> - ? ? ?&& is_gimple_assign (negatedefstmt)
> - ? ? ?&& TREE_CODE (gimple_assign_lhs (negatedefstmt)) == SSA_NAME
> - ? ? ?&& has_single_use (gimple_assign_lhs (negatedefstmt))
> - ? ? ?&& gimple_assign_rhs_code (negatedefstmt) == PLUS_EXPR)
> - ? ?{
> - ? ? ?gimple_stmt_iterator gsi;
> - ? ? ?tree rhs1 = gimple_assign_rhs1 (negatedefstmt);
> - ? ? ?tree rhs2 = gimple_assign_rhs2 (negatedefstmt);
> -
> - ? ? ?gsi = gsi_for_stmt (negatedefstmt);
> - ? ? ?rhs1 = negate_value (rhs1, &gsi);
> - ? ? ?gimple_assign_set_rhs1 (negatedefstmt, rhs1);
> -
> - ? ? ?gsi = gsi_for_stmt (negatedefstmt);
> - ? ? ?rhs2 = negate_value (rhs2, &gsi);
> - ? ? ?gimple_assign_set_rhs2 (negatedefstmt, rhs2);
> -
> - ? ? ?update_stmt (negatedefstmt);
> - ? ? ?return gimple_assign_lhs (negatedefstmt);
> - ? ?}
> -
> - ?tonegate = fold_build1 (NEGATE_EXPR, TREE_TYPE (tonegate), tonegate);
> - ?resultofnegate = force_gimple_operand_gsi (gsi, tonegate, true,
> - ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?NULL_TREE, true, GSI_SAME_STMT);
> - ?return resultofnegate;
> -}
> -
> -/* Return true if we should break up the subtract in STMT into an add
> - ? with negate. ?This is true when we the subtract operands are really
> - ? adds, or the subtract itself is used in an add expression. ?In
> - ? either case, breaking up the subtract into an add with negate
> - ? exposes the adds to reassociation. ?*/
> -
> -static bool
> -should_break_up_subtract (gimple stmt)
> -{
> - ?tree lhs = gimple_assign_lhs (stmt);
> - ?tree binlhs = gimple_assign_rhs1 (stmt);
> - ?tree binrhs = gimple_assign_rhs2 (stmt);
> - ?gimple immusestmt;
> - ?struct loop *loop = loop_containing_stmt (stmt);
> -
> - ?if (TREE_CODE (binlhs) == SSA_NAME
> - ? ? ?&& is_reassociable_op (SSA_NAME_DEF_STMT (binlhs), PLUS_EXPR, loop))
> - ? ?return true;
> -
> - ?if (TREE_CODE (binrhs) == SSA_NAME
> - ? ? ?&& is_reassociable_op (SSA_NAME_DEF_STMT (binrhs), PLUS_EXPR, loop))
> - ? ?return true;
> -
> - ?if (TREE_CODE (lhs) == SSA_NAME
> - ? ? ?&& (immusestmt = get_single_immediate_use (lhs))
> - ? ? ?&& is_gimple_assign (immusestmt)
> - ? ? ?&& (gimple_assign_rhs_code (immusestmt) == PLUS_EXPR
> - ? ? ? ? || ?gimple_assign_rhs_code (immusestmt) == MULT_EXPR))
> - ? ?return true;
> - ?return false;
> -}
> -
> -/* Transform STMT from A - B into A + -B. ?*/
> -
> ?static void
> -break_up_subtract (gimple stmt, gimple_stmt_iterator *gsip)
> +negate_and_add_to_ops_vec (VEC(operand_entry_t, heap) **ops, tree op,
> + ? ? ? ? ? ? ? ? ? ? ? ? ?enum tree_code code, bool negate)
> ?{
> - ?tree rhs1 = gimple_assign_rhs1 (stmt);
> - ?tree rhs2 = gimple_assign_rhs2 (stmt);
> -
> - ?if (dump_file && (dump_flags & TDF_DETAILS))
> + ?if ((code == PLUS_EXPR || code == MINUS_EXPR)
> + ? ? ?&& TREE_CODE (op) == SSA_NAME
> + ? ? ?&& is_gimple_assign (SSA_NAME_DEF_STMT (op))
> + ? ? ?&& gimple_assign_rhs_code (SSA_NAME_DEF_STMT (op)) == NEGATE_EXPR)
> ? ? {
> - ? ? ?fprintf (dump_file, "Breaking up subtract ");
> - ? ? ?print_gimple_stmt (dump_file, stmt, 0, 0);
> + ? ? ?negate = !negate;
> + ? ? ?op = gimple_assign_rhs1 (SSA_NAME_DEF_STMT (op));
> ? ? }
> -
> - ?rhs2 = negate_value (rhs2, gsip);
> - ?gimple_assign_set_rhs_with_ops (gsip, PLUS_EXPR, rhs1, rhs2);
> - ?update_stmt (stmt);
> + ?if (negate)
> + ? ?op = fold_build1 (NEGATE_EXPR, TREE_TYPE (op), op);
> + ?add_to_ops_vec (ops, op);
> ?}
>
> ?/* Recursively linearize a binary expression that is the RHS of STMT.
> @@ -1631,7 +1670,7 @@ break_up_subtract (gimple stmt, gimple_stmt_iterator *gsip)
>
> ?static void
> ?linearize_expr_tree (VEC(operand_entry_t, heap) **ops, gimple stmt,
> - ? ? ? ? ? ? ? ? ? ?bool is_associative, bool set_visited)
> + ? ? ? ? ? ? ? ? ? ?bool is_associative, bool set_visited, bool negate)
> ?{
> ? tree binlhs = gimple_assign_rhs1 (stmt);
> ? tree binrhs = gimple_assign_rhs2 (stmt);
> @@ -1639,6 +1678,7 @@ linearize_expr_tree (VEC(operand_entry_t, heap) **ops, gimple stmt,
> ? bool binlhsisreassoc = false;
> ? bool binrhsisreassoc = false;
> ? enum tree_code rhscode = gimple_assign_rhs_code (stmt);
> + ?bool negate_rhs = negate ^ (rhscode == MINUS_EXPR);
> ? struct loop *loop = loop_containing_stmt (stmt);
>
> ? if (set_visited)
> @@ -1669,14 +1709,14 @@ linearize_expr_tree (VEC(operand_entry_t, heap) **ops, gimple stmt,
> ? ? ? /* If this is not a associative operation like division, give up. ?*/
> ? ? ? if (!is_associative)
> ? ? ? ?{
> - ? ? ? ? add_to_ops_vec (ops, binrhs);
> + ? ? ? ? negate_and_add_to_ops_vec (ops, binrhs, rhscode, negate_rhs);
> ? ? ? ? ?return;
> ? ? ? ?}
>
> ? ? ? if (!binrhsisreassoc)
> ? ? ? ?{
> - ? ? ? ? add_to_ops_vec (ops, binrhs);
> - ? ? ? ? add_to_ops_vec (ops, binlhs);
> + ? ? ? ? negate_and_add_to_ops_vec (ops, binrhs, rhscode, negate_rhs);
> + ? ? ? ? negate_and_add_to_ops_vec (ops, binlhs, rhscode, negate);
> ? ? ? ? ?return;
> ? ? ? ?}
>
> @@ -1690,6 +1730,11 @@ linearize_expr_tree (VEC(operand_entry_t, heap) **ops, gimple stmt,
> ? ? ? ? ? ? ? ? ? ? ? ? ?gimple_assign_rhs1_ptr (stmt),
> ? ? ? ? ? ? ? ? ? ? ? ? ?gimple_assign_rhs2_ptr (stmt));
> ? ? ? update_stmt (stmt);
> + ? ? ?if (rhscode == MINUS_EXPR)
> + ? ? ? {
> + ? ? ? ? negate = !negate;
> + ? ? ? ? negate_rhs = !negate_rhs;
> + ? ? ? }
>
> ? ? ? if (dump_file && (dump_flags & TDF_DETAILS))
> ? ? ? ?{
> @@ -1714,119 +1759,8 @@ linearize_expr_tree (VEC(operand_entry_t, heap) **ops, gimple stmt,
> ? ? ? ? ? ? ?|| !is_reassociable_op (SSA_NAME_DEF_STMT (binrhs),
> ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?rhscode, loop));
> ? linearize_expr_tree (ops, SSA_NAME_DEF_STMT (binlhs),
> - ? ? ? ? ? ? ? ? ? ? ?is_associative, set_visited);
> - ?add_to_ops_vec (ops, binrhs);
> -}
> -
> -/* Repropagate the negates back into subtracts, since no other pass
> - ? currently does it. ?*/
> -
> -static void
> -repropagate_negates (void)
> -{
> - ?unsigned int i = 0;
> - ?tree negate;
> -
> - ?for (i = 0; VEC_iterate (tree, plus_negates, i, negate); i++)
> - ? ?{
> - ? ? ?gimple user = get_single_immediate_use (negate);
> -
> - ? ? ?/* The negate operand can be either operand of a PLUS_EXPR
> - ? ? ? ?(it can be the LHS if the RHS is a constant for example).
> -
> - ? ? ? ?Force the negate operand to the RHS of the PLUS_EXPR, then
> - ? ? ? ?transform the PLUS_EXPR into a MINUS_EXPR. ?*/
> - ? ? ?if (user
> - ? ? ? ? && is_gimple_assign (user)
> - ? ? ? ? && gimple_assign_rhs_code (user) == PLUS_EXPR)
> - ? ? ? {
> - ? ? ? ? /* If the negated operand appears on the LHS of the
> - ? ? ? ? ? ?PLUS_EXPR, exchange the operands of the PLUS_EXPR
> - ? ? ? ? ? ?to force the negated operand to the RHS of the PLUS_EXPR. ?*/
> - ? ? ? ? if (gimple_assign_rhs1 (user) == negate)
> - ? ? ? ? ? {
> - ? ? ? ? ? ? swap_tree_operands (user,
> - ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? gimple_assign_rhs1_ptr (user),
> - ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? gimple_assign_rhs2_ptr (user));
> - ? ? ? ? ? }
> -
> - ? ? ? ? /* Now transform the PLUS_EXPR into a MINUS_EXPR and replace
> - ? ? ? ? ? ?the RHS of the PLUS_EXPR with the operand of the NEGATE_EXPR. ?*/
> - ? ? ? ? if (gimple_assign_rhs2 (user) == negate)
> - ? ? ? ? ? {
> - ? ? ? ? ? ? tree rhs1 = gimple_assign_rhs1 (user);
> - ? ? ? ? ? ? tree rhs2 = get_unary_op (negate, NEGATE_EXPR);
> - ? ? ? ? ? ? gimple_stmt_iterator gsi = gsi_for_stmt (user);
> - ? ? ? ? ? ? gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, rhs1, rhs2);
> - ? ? ? ? ? ? update_stmt (user);
> - ? ? ? ? ? }
> - ? ? ? }
> - ? ?}
> -}
> -
> -/* Break up subtract operations in block BB.
> -
> - ? We do this top down because we don't know whether the subtract is
> - ? part of a possible chain of reassociation except at the top.
> -
> - ? IE given
> - ? d = f + g
> - ? c = a + e
> - ? b = c - d
> - ? q = b - r
> - ? k = t - q
> -
> - ? we want to break up k = t - q, but we won't until we've transformed q
> - ? = b - r, which won't be broken up until we transform b = c - d.
> -
> - ? En passant, clear the GIMPLE visited flag on every statement. ?*/
> -
> -static void
> -break_up_subtract_bb (basic_block bb)
> -{
> - ?gimple_stmt_iterator gsi;
> - ?basic_block son;
> -
> - ?for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> - ? ?{
> - ? ? ?gimple stmt = gsi_stmt (gsi);
> - ? ? ?gimple_set_visited (stmt, false);
> -
> - ? ? ?/* Look for simple gimple subtract operations. ?*/
> - ? ? ?if (is_gimple_assign (stmt)
> - ? ? ? ? && gimple_assign_rhs_code (stmt) == MINUS_EXPR)
> - ? ? ? {
> - ? ? ? ? tree lhs = gimple_assign_lhs (stmt);
> - ? ? ? ? tree rhs1 = gimple_assign_rhs1 (stmt);
> - ? ? ? ? tree rhs2 = gimple_assign_rhs2 (stmt);
> -
> - ? ? ? ? /* If associative-math we can do reassociation for
> - ? ? ? ? ? ?non-integral types. ?Or, we can do reassociation for
> - ? ? ? ? ? ?non-saturating fixed-point types. ?*/
> - ? ? ? ? if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
> - ? ? ? ? ? ? ?|| !INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
> - ? ? ? ? ? ? ?|| !INTEGRAL_TYPE_P (TREE_TYPE (rhs2)))
> - ? ? ? ? ? ? && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (lhs))
> - ? ? ? ? ? ? ? ? || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs1))
> - ? ? ? ? ? ? ? ? || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(rhs2))
> - ? ? ? ? ? ? ? ? || !flag_associative_math)
> - ? ? ? ? ? ? && (!NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE (lhs))
> - ? ? ? ? ? ? ? ? || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs1))
> - ? ? ? ? ? ? ? ? || !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs2))))
> - ? ? ? ? ? continue;
> -
> - ? ? ? ? /* Check for a subtract used only in an addition. ?If this
> - ? ? ? ? ? ?is the case, transform it into add of a negate for better
> - ? ? ? ? ? ?reassociation. ?IE transform C = A-B into C = A + -B if C
> - ? ? ? ? ? ?is only used in an addition. ?*/
> - ? ? ? ? if (should_break_up_subtract (stmt))
> - ? ? ? ? ? break_up_subtract (stmt, &gsi);
> - ? ? ? }
> - ? ?}
> - ?for (son = first_dom_son (CDI_DOMINATORS, bb);
> - ? ? ? son;
> - ? ? ? son = next_dom_son (CDI_DOMINATORS, son))
> - ? ?break_up_subtract_bb (son);
> + ? ? ? ? ? ? ? ? ? ? ?is_associative, set_visited, negate);
> + ?negate_and_add_to_ops_vec (ops, binrhs, rhscode, negate_rhs);
> ?}
>
> ?/* Reassociate expressions in basic block BB and its post-dominator as
> @@ -1897,7 +1831,8 @@ reassociate_bb (basic_block bb)
> ? ? ? ? ? ? ? ? ?|| !NON_SAT_FIXED_POINT_TYPE_P (TREE_TYPE(rhs2))))
> ? ? ? ? ? ?continue;
>
> - ? ? ? ? if (associative_tree_code (rhs_code))
> + ? ? ? ? if (associative_tree_code (rhs_code)
> + ? ? ? ? ? ? || rhs_code == MINUS_EXPR)
> ? ? ? ? ? ?{
> ? ? ? ? ? ? ?VEC(operand_entry_t, heap) *ops = NULL;
>
> @@ -1906,8 +1841,10 @@ reassociate_bb (basic_block bb)
> ? ? ? ? ? ? ?if (TREE_CODE (lhs) == SSA_NAME && has_zero_uses (lhs))
> ? ? ? ? ? ? ? ?continue;
>
> + ? ? ? ? ? ? if (rhs_code == MINUS_EXPR)
> + ? ? ? ? ? ? ? rhs_code = PLUS_EXPR;
> ? ? ? ? ? ? ?gimple_set_visited (stmt, true);
> - ? ? ? ? ? ? linearize_expr_tree (&ops, stmt, true, true);
> + ? ? ? ? ? ? linearize_expr_tree (&ops, stmt, true, true, false);
> ? ? ? ? ? ? ?qsort (VEC_address (operand_entry_t, ops),
> ? ? ? ? ? ? ? ? ? ? VEC_length (operand_entry_t, ops),
> ? ? ? ? ? ? ? ? ? ? sizeof (operand_entry_t),
> @@ -1972,6 +1909,7 @@ dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops)
> ? ? {
> ? ? ? fprintf (file, "Op %d -> rank: %d, tree: ", i, oe->rank);
> ? ? ? print_generic_expr (file, oe->op, 0);
> + ? ? ?fprintf (file, "\n");
> ? ? }
> ?}
>
> @@ -1986,7 +1924,6 @@ debug_ops_vector (VEC (operand_entry_t, heap) *ops)
> ?static void
> ?do_reassoc (void)
> ?{
> - ?break_up_subtract_bb (ENTRY_BLOCK_PTR);
> ? reassociate_bb (EXIT_BLOCK_PTR);
> ?}
>
> @@ -2041,7 +1978,6 @@ init_reassoc (void)
>
> ? free (bbs);
> ? calculate_dominance_info (CDI_POST_DOMINATORS);
> - ?plus_negates = NULL;
> ?}
>
> ?/* Cleanup after the reassociation pass, and print stats if
> @@ -2062,7 +1998,6 @@ fini_reassoc (void)
> ? pointer_map_destroy (operand_rank);
> ? free_alloc_pool (operand_entry_pool);
> ? free (bb_rank);
> - ?VEC_free (tree, heap, plus_negates);
> ? free_dominance_info (CDI_POST_DOMINATORS);
> ? loop_optimizer_finalize ();
> ?}
> @@ -2075,7 +2010,6 @@ execute_reassoc (void)
> ? init_reassoc ();
>
> ? do_reassoc ();
> - ?repropagate_negates ();
>
> ? fini_reassoc ();
> ? return 0;
>
>