/* Global, SSA-based optimizations using mathematical identities.
- Copyright (C) 2005-2018 Free Software Foundation, Inc.
+ Copyright (C) 2005-2019 Free Software Foundation, Inc.
This file is part of GCC.
#include "optabs-libfuncs.h"
#include "tree-eh.h"
#include "targhooks.h"
+#include "domwalk.h"
/* This structure represents one basic block that either computes a
division, or is a common dominator for basic block that compute a
/* Do not recognize x / x as valid division, as we are getting
confused later by replacing all immediate uses x in such
a stmt. */
- && gimple_assign_rhs1 (use_stmt) != def;
+ && gimple_assign_rhs1 (use_stmt) != def
+ && !stmt_can_throw_internal (cfun, use_stmt);
}
-/* Return whether USE_STMT is DEF * DEF. */
+/* Return TRUE if USE_STMT is a multiplication of DEF by A. */
static inline bool
-is_square_of (gimple *use_stmt, tree def)
+is_mult_by (gimple *use_stmt, tree def, tree a)
{
if (gimple_code (use_stmt) == GIMPLE_ASSIGN
&& gimple_assign_rhs_code (use_stmt) == MULT_EXPR)
tree op0 = gimple_assign_rhs1 (use_stmt);
tree op1 = gimple_assign_rhs2 (use_stmt);
- return op0 == op1 && op0 == def;
+ return (op0 == def && op1 == a)
+ || (op0 == a && op1 == def);
}
return 0;
}
+/* Return whether USE_STMT is DEF * DEF. */
+static inline bool
+is_square_of (gimple *use_stmt, tree def)
+{
+ return is_mult_by (use_stmt, def, def);
+}
+
/* Return whether USE_STMT is a floating-point division by
DEF * DEF. */
static inline bool
{
if (gimple_code (use_stmt) == GIMPLE_ASSIGN
&& gimple_assign_rhs_code (use_stmt) == RDIV_EXPR
- && gimple_assign_rhs1 (use_stmt) != gimple_assign_rhs2 (use_stmt))
+ && gimple_assign_rhs1 (use_stmt) != gimple_assign_rhs2 (use_stmt)
+ && !stmt_can_throw_internal (cfun, use_stmt))
{
tree denominator = gimple_assign_rhs2 (use_stmt);
if (TREE_CODE (denominator) == SSA_NAME)
- {
- return is_square_of (SSA_NAME_DEF_STMT (denominator), def);
- }
+ return is_square_of (SSA_NAME_DEF_STMT (denominator), def);
}
return 0;
}
gsi_next (&gsi);
gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
+ if (should_insert_square_recip)
+ gsi_insert_before (&gsi, new_square_stmt, GSI_SAME_STMT);
}
else if (def_gsi && occ->bb == def_gsi->bb)
{
never happen if the definition statement can throw, because in
that case the sole successor of the statement's basic block will
dominate all the uses as well. */
- gsi = *def_gsi;
gsi_insert_after (def_gsi, new_stmt, GSI_NEW_STMT);
+ if (should_insert_square_recip)
+ gsi_insert_after (def_gsi, new_square_stmt, GSI_NEW_STMT);
}
else
{
/* Case 3: insert in a basic block not containing defs/uses. */
gsi = gsi_after_labels (occ->bb);
gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT);
+ if (should_insert_square_recip)
+ gsi_insert_before (&gsi, new_square_stmt, GSI_SAME_STMT);
}
- /* Regardless of which case the reciprocal as inserted in,
- we insert the square immediately after the reciprocal. */
- if (should_insert_square_recip)
- gsi_insert_before (&gsi, new_square_stmt, GSI_SAME_STMT);
-
reciprocal_stats.rdivs_inserted++;
occ->recip_def_stmt = new_stmt;
}
}
+/* Transform sequences like
+ t = sqrt (a)
+ x = 1.0 / t;
+ r1 = x * x;
+ r2 = a * x;
+ into:
+ t = sqrt (a)
+ r1 = 1.0 / a;
+ r2 = t;
+ x = r1 * r2;
+ depending on the uses of x, r1, r2. This removes one multiplication and
+ allows the sqrt and division operations to execute in parallel.
+ DEF_GSI is the gsi of the initial division by sqrt that defines
+ DEF (x in the example above). */
+
+static void
+optimize_recip_sqrt (gimple_stmt_iterator *def_gsi, tree def)
+{
+ gimple *use_stmt;
+ imm_use_iterator use_iter;
+ gimple *stmt = gsi_stmt (*def_gsi);
+ tree x = def;
+ tree orig_sqrt_ssa_name = gimple_assign_rhs2 (stmt);
+ tree div_rhs1 = gimple_assign_rhs1 (stmt);
+
+ if (TREE_CODE (orig_sqrt_ssa_name) != SSA_NAME
+ || TREE_CODE (div_rhs1) != REAL_CST
+ || !real_equal (&TREE_REAL_CST (div_rhs1), &dconst1))
+ return;
+
+ gcall *sqrt_stmt
+ = dyn_cast <gcall *> (SSA_NAME_DEF_STMT (orig_sqrt_ssa_name));
+
+ if (!sqrt_stmt || !gimple_call_lhs (sqrt_stmt))
+ return;
+
+ switch (gimple_call_combined_fn (sqrt_stmt))
+ {
+ CASE_CFN_SQRT:
+ CASE_CFN_SQRT_FN:
+ break;
+
+ default:
+ return;
+ }
+ tree a = gimple_call_arg (sqrt_stmt, 0);
+
+ /* We have 'a' and 'x'. Now analyze the uses of 'x'. */
+
+ /* Statements that use x in x * x. */
+ auto_vec<gimple *> sqr_stmts;
+ /* Statements that use x in a * x. */
+ auto_vec<gimple *> mult_stmts;
+ bool has_other_use = false;
+ bool mult_on_main_path = false;
+
+ FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, x)
+ {
+ if (is_gimple_debug (use_stmt))
+ continue;
+ if (is_square_of (use_stmt, x))
+ {
+ sqr_stmts.safe_push (use_stmt);
+ if (gimple_bb (use_stmt) == gimple_bb (stmt))
+ mult_on_main_path = true;
+ }
+ else if (is_mult_by (use_stmt, x, a))
+ {
+ mult_stmts.safe_push (use_stmt);
+ if (gimple_bb (use_stmt) == gimple_bb (stmt))
+ mult_on_main_path = true;
+ }
+ else
+ has_other_use = true;
+ }
+
+ /* In the x * x and a * x cases we just rewire stmt operands or
+ remove multiplications. In the has_other_use case we introduce
+ a multiplication so make sure we don't introduce a multiplication
+ on a path where there was none. */
+ if (has_other_use && !mult_on_main_path)
+ return;
+
+ if (sqr_stmts.is_empty () && mult_stmts.is_empty ())
+ return;
+
+ /* If x = 1.0 / sqrt (a) has uses other than those optimized here we want
+ to be able to compose it from the sqr and mult cases. */
+ if (has_other_use && (sqr_stmts.is_empty () || mult_stmts.is_empty ()))
+ return;
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Optimizing reciprocal sqrt multiplications of\n");
+ print_gimple_stmt (dump_file, sqrt_stmt, 0, TDF_NONE);
+ print_gimple_stmt (dump_file, stmt, 0, TDF_NONE);
+ fprintf (dump_file, "\n");
+ }
+
+ bool delete_div = !has_other_use;
+ tree sqr_ssa_name = NULL_TREE;
+ if (!sqr_stmts.is_empty ())
+ {
+ /* r1 = x * x. Transform the original
+ x = 1.0 / t
+ into
+ tmp1 = 1.0 / a
+ r1 = tmp1. */
+
+ sqr_ssa_name
+ = make_temp_ssa_name (TREE_TYPE (a), NULL, "recip_sqrt_sqr");
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Replacing original division\n");
+ print_gimple_stmt (dump_file, stmt, 0, TDF_NONE);
+ fprintf (dump_file, "with new division\n");
+ }
+ stmt
+ = gimple_build_assign (sqr_ssa_name, gimple_assign_rhs_code (stmt),
+ gimple_assign_rhs1 (stmt), a);
+ gsi_insert_before (def_gsi, stmt, GSI_SAME_STMT);
+ gsi_remove (def_gsi, true);
+ *def_gsi = gsi_for_stmt (stmt);
+ fold_stmt_inplace (def_gsi);
+ update_stmt (stmt);
+
+ if (dump_file)
+ print_gimple_stmt (dump_file, stmt, 0, TDF_NONE);
+
+ delete_div = false;
+ gimple *sqr_stmt;
+ unsigned int i;
+ FOR_EACH_VEC_ELT (sqr_stmts, i, sqr_stmt)
+ {
+ gimple_stmt_iterator gsi2 = gsi_for_stmt (sqr_stmt);
+ gimple_assign_set_rhs_from_tree (&gsi2, sqr_ssa_name);
+ update_stmt (sqr_stmt);
+ }
+ }
+ if (!mult_stmts.is_empty ())
+ {
+ /* r2 = a * x. Transform this into:
+ r2 = t (The original sqrt (a)). */
+ unsigned int i;
+ gimple *mult_stmt = NULL;
+ FOR_EACH_VEC_ELT (mult_stmts, i, mult_stmt)
+ {
+ gimple_stmt_iterator gsi2 = gsi_for_stmt (mult_stmt);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Replacing squaring multiplication\n");
+ print_gimple_stmt (dump_file, mult_stmt, 0, TDF_NONE);
+ fprintf (dump_file, "with assignment\n");
+ }
+ gimple_assign_set_rhs_from_tree (&gsi2, orig_sqrt_ssa_name);
+ fold_stmt_inplace (&gsi2);
+ update_stmt (mult_stmt);
+ if (dump_file)
+ print_gimple_stmt (dump_file, mult_stmt, 0, TDF_NONE);
+ }
+ }
+
+ if (has_other_use)
+ {
+ /* Using the two temporaries tmp1, tmp2 from above
+ the original x is now:
+ x = tmp1 * tmp2. */
+ gcc_assert (orig_sqrt_ssa_name);
+ gcc_assert (sqr_ssa_name);
+
+ gimple *new_stmt
+ = gimple_build_assign (x, MULT_EXPR,
+ orig_sqrt_ssa_name, sqr_ssa_name);
+ gsi_insert_after (def_gsi, new_stmt, GSI_NEW_STMT);
+ update_stmt (stmt);
+ }
+ else if (delete_div)
+ {
+ /* Remove the original division. */
+ gimple_stmt_iterator gsi2 = gsi_for_stmt (stmt);
+ gsi_remove (&gsi2, true);
+ release_defs (stmt);
+ }
+ else
+ release_ssa_name (x);
+}
/* Look for floating-point divisions among DEF's uses, and try to
replace them by multiplications with the reciprocal. Add
/* If it is more profitable to optimize 1 / x, don't optimize 1 / (x * x). */
if (sqrt_recip_count > square_recip_count)
- return;
+ goto out;
/* Do the expensive part only if we can hope to optimize something. */
if (count + square_recip_count >= threshold && count >= 1)
}
}
+out:
for (occ = occ_head; occ; )
occ = free_bb (occ);
&& (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL
&& FLOAT_TYPE_P (TREE_TYPE (def))
&& TREE_CODE (def) == SSA_NAME)
- execute_cse_reciprocals_1 (&gsi, def);
+ {
+ execute_cse_reciprocals_1 (&gsi, def);
+ stmt = gsi_stmt (gsi);
+ if (flag_unsafe_math_optimizations
+ && is_gimple_assign (stmt)
+ && gimple_assign_lhs (stmt) == def
+ && !stmt_can_throw_internal (cfun, stmt)
+ && gimple_assign_rhs_code (stmt) == RDIV_EXPR)
+ optimize_recip_sqrt (&gsi, def);
+ }
}
if (optimize_bb_for_size_p (bb))
{
fndecl = gimple_call_fndecl (call);
if (!fndecl
- || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_MD)
+ || !fndecl_built_in_p (fndecl, BUILT_IN_MD))
continue;
fndecl = targetm.builtin_reciprocal (fndecl);
if (!fndecl)
return true;
}
+/* Given a result MUL_RESULT which is a result of a multiplication of OP1 and
+ OP2 and which we know is used in statements that can be, together with the
+ multiplication, converted to FMAs, perform the transformation. */
+
+static void
+convert_mult_to_fma_1 (tree mul_result, tree op1, tree op2)
+{
+ tree type = TREE_TYPE (mul_result);
+ gimple *use_stmt;
+ imm_use_iterator imm_iter;
+ gcall *fma_stmt;
+
+ FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, mul_result)
+ {
+ gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
+ tree addop, mulop1 = op1, result = mul_result;
+ bool negate_p = false;
+ gimple_seq seq = NULL;
+
+ if (is_gimple_debug (use_stmt))
+ continue;
+
+ if (is_gimple_assign (use_stmt)
+ && gimple_assign_rhs_code (use_stmt) == NEGATE_EXPR)
+ {
+ result = gimple_assign_lhs (use_stmt);
+ use_operand_p use_p;
+ gimple *neguse_stmt;
+ single_imm_use (gimple_assign_lhs (use_stmt), &use_p, &neguse_stmt);
+ gsi_remove (&gsi, true);
+ release_defs (use_stmt);
+
+ use_stmt = neguse_stmt;
+ gsi = gsi_for_stmt (use_stmt);
+ negate_p = true;
+ }
+
+ tree cond, else_value, ops[3];
+ tree_code code;
+ if (!can_interpret_as_conditional_op_p (use_stmt, &cond, &code,
+ ops, &else_value))
+ gcc_unreachable ();
+ addop = ops[0] == result ? ops[1] : ops[0];
+
+ if (code == MINUS_EXPR)
+ {
+ if (ops[0] == result)
+ /* a * b - c -> a * b + (-c) */
+ addop = gimple_build (&seq, NEGATE_EXPR, type, addop);
+ else
+ /* a - b * c -> (-b) * c + a */
+ negate_p = !negate_p;
+ }
+
+ if (negate_p)
+ mulop1 = gimple_build (&seq, NEGATE_EXPR, type, mulop1);
+
+ if (seq)
+ gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
+
+ if (cond)
+ fma_stmt = gimple_build_call_internal (IFN_COND_FMA, 5, cond, mulop1,
+ op2, addop, else_value);
+ else
+ fma_stmt = gimple_build_call_internal (IFN_FMA, 3, mulop1, op2, addop);
+ gimple_set_lhs (fma_stmt, gimple_get_lhs (use_stmt));
+ gimple_call_set_nothrow (fma_stmt, !stmt_can_throw_internal (cfun,
+ use_stmt));
+ gsi_replace (&gsi, fma_stmt, true);
+ /* Follow all SSA edges so that we generate FMS, FNMA and FNMS
+ regardless of where the negation occurs. */
+ gimple *orig_stmt = gsi_stmt (gsi);
+ if (fold_stmt (&gsi, follow_all_ssa_edges))
+ {
+ if (maybe_clean_or_replace_eh_stmt (orig_stmt, gsi_stmt (gsi)))
+ gcc_unreachable ();
+ update_stmt (gsi_stmt (gsi));
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Generated FMA ");
+ print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, TDF_NONE);
+ fprintf (dump_file, "\n");
+ }
+
+ widen_mul_stats.fmas_inserted++;
+ }
+}
+
+/* Data necessary to perform the actual transformation from a multiplication
+ and an addition to an FMA after decision is taken it should be done and to
+ then delete the multiplication statement from the function IL. */
+
+struct fma_transformation_info
+{
+ gimple *mul_stmt;
+ tree mul_result;
+ tree op1;
+ tree op2;
+};
+
+/* Structure containing the current state of FMA deferring, i.e. whether we are
+ deferring, whether to continue deferring, and all data necessary to come
+ back and perform all deferred transformations. */
+
+class fma_deferring_state
+{
+public:
+ /* Class constructor. Pass true as PERFORM_DEFERRING in order to actually
+ do any deferring. */
+
+ fma_deferring_state (bool perform_deferring)
+ : m_candidates (), m_mul_result_set (), m_initial_phi (NULL),
+ m_last_result (NULL_TREE), m_deferring_p (perform_deferring) {}
+
+ /* List of FMA candidates for which we the transformation has been determined
+ possible but we at this point in BB analysis we do not consider them
+ beneficial. */
+ auto_vec<fma_transformation_info, 8> m_candidates;
+
+ /* Set of results of multiplication that are part of an already deferred FMA
+ candidates. */
+ hash_set<tree> m_mul_result_set;
+
+ /* The PHI that supposedly feeds back result of a FMA to another over loop
+ boundary. */
+ gphi *m_initial_phi;
+
+ /* Result of the last produced FMA candidate or NULL if there has not been
+ one. */
+ tree m_last_result;
+
+ /* If true, deferring might still be profitable. If false, transform all
+ candidates and no longer defer. */
+ bool m_deferring_p;
+};
+
+/* Transform all deferred FMA candidates and mark STATE as no longer
+ deferring. */
+
+static void
+cancel_fma_deferring (fma_deferring_state *state)
+{
+ if (!state->m_deferring_p)
+ return;
+
+ for (unsigned i = 0; i < state->m_candidates.length (); i++)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "Generating deferred FMA\n");
+
+ const fma_transformation_info &fti = state->m_candidates[i];
+ convert_mult_to_fma_1 (fti.mul_result, fti.op1, fti.op2);
+
+ gimple_stmt_iterator gsi = gsi_for_stmt (fti.mul_stmt);
+ gsi_remove (&gsi, true);
+ release_defs (fti.mul_stmt);
+ }
+ state->m_deferring_p = false;
+}
+
+/* If OP is an SSA name defined by a PHI node, return the PHI statement.
+ Otherwise return NULL. */
+
+static gphi *
+result_of_phi (tree op)
+{
+ if (TREE_CODE (op) != SSA_NAME)
+ return NULL;
+
+ return dyn_cast <gphi *> (SSA_NAME_DEF_STMT (op));
+}
+
+/* After processing statements of a BB and recording STATE, return true if the
+ initial phi is fed by the last FMA candidate result ore one such result from
+ previously processed BBs marked in LAST_RESULT_SET. */
+
+static bool
+last_fma_candidate_feeds_initial_phi (fma_deferring_state *state,
+ hash_set<tree> *last_result_set)
+{
+ ssa_op_iter iter;
+ use_operand_p use;
+ FOR_EACH_PHI_ARG (use, state->m_initial_phi, iter, SSA_OP_USE)
+ {
+ tree t = USE_FROM_PTR (use);
+ if (t == state->m_last_result
+ || last_result_set->contains (t))
+ return true;
+ }
+
+ return false;
+}
+
/* Combine the multiplication at MUL_STMT with operands MULOP1 and MULOP2
with uses in additions and subtractions to form fused multiply-add
- operations. Returns true if successful and MUL_STMT should be removed. */
+ operations. Returns true if successful and MUL_STMT should be removed.
+
+ If STATE indicates that we are deferring FMA transformation, that means
+ that we do not produce FMAs for basic blocks which look like:
+
+ <bb 6>
+ # accumulator_111 = PHI <0.0(5), accumulator_66(6)>
+ _65 = _14 * _16;
+ accumulator_66 = _65 + accumulator_111;
+
+ or its unrolled version, i.e. with several FMA candidates that feed result
+ of one into the addend of another. Instead, we add them to a list in STATE
+ and if we later discover an FMA candidate that is not part of such a chain,
+ we go back and perform all deferred past candidates. */
static bool
-convert_mult_to_fma (gimple *mul_stmt, tree op1, tree op2)
+convert_mult_to_fma (gimple *mul_stmt, tree op1, tree op2,
+ fma_deferring_state *state)
{
tree mul_result = gimple_get_lhs (mul_stmt);
tree type = TREE_TYPE (mul_result);
gimple *use_stmt, *neguse_stmt;
- gassign *fma_stmt;
use_operand_p use_p;
imm_use_iterator imm_iter;
/* If the target doesn't support it, don't generate it. We assume that
if fma isn't available then fms, fnma or fnms are not either. */
- if (optab_handler (fma_optab, TYPE_MODE (type)) == CODE_FOR_nothing)
+ optimization_type opt_type = bb_optimization_type (gimple_bb (mul_stmt));
+ if (!direct_internal_fn_supported_p (IFN_FMA, type, opt_type))
return false;
/* If the multiplication has zero uses, it is kept around probably because
if (has_zero_uses (mul_result))
return false;
+ bool check_defer
+ = (state->m_deferring_p
+ && (tree_to_shwi (TYPE_SIZE (type))
+ <= PARAM_VALUE (PARAM_AVOID_FMA_MAX_BITS)));
+ bool defer = check_defer;
+ bool seen_negate_p = false;
/* Make sure that the multiplication statement becomes dead after
the transformation, thus that all uses are transformed to FMAs.
This means we assume that an FMA operation has the same cost
as an addition. */
FOR_EACH_IMM_USE_FAST (use_p, imm_iter, mul_result)
{
- enum tree_code use_code;
tree result = mul_result;
bool negate_p = false;
if (gimple_bb (use_stmt) != gimple_bb (mul_stmt))
return false;
- if (!is_gimple_assign (use_stmt))
- return false;
-
- use_code = gimple_assign_rhs_code (use_stmt);
-
/* A negate on the multiplication leads to FNMA. */
- if (use_code == NEGATE_EXPR)
+ if (is_gimple_assign (use_stmt)
+ && gimple_assign_rhs_code (use_stmt) == NEGATE_EXPR)
{
ssa_op_iter iter;
use_operand_p usep;
+ /* If (due to earlier missed optimizations) we have two
+ negates of the same value, treat them as equivalent
+ to a single negate with multiple uses. */
+ if (seen_negate_p)
+ return false;
+
result = gimple_assign_lhs (use_stmt);
/* Make sure the negate statement becomes dead with this
use_stmt = neguse_stmt;
if (gimple_bb (use_stmt) != gimple_bb (mul_stmt))
return false;
- if (!is_gimple_assign (use_stmt))
- return false;
- use_code = gimple_assign_rhs_code (use_stmt);
- negate_p = true;
+ negate_p = seen_negate_p = true;
}
- switch (use_code)
+ tree cond, else_value, ops[3];
+ tree_code code;
+ if (!can_interpret_as_conditional_op_p (use_stmt, &cond, &code, ops,
+ &else_value))
+ return false;
+
+ switch (code)
{
case MINUS_EXPR:
- if (gimple_assign_rhs2 (use_stmt) == result)
+ if (ops[1] == result)
negate_p = !negate_p;
break;
case PLUS_EXPR:
return false;
}
- /* If the subtrahend (gimple_assign_rhs2 (use_stmt)) is computed
- by a MULT_EXPR that we'll visit later, we might be able to
- get a more profitable match with fnma.
+ if (cond)
+ {
+ if (cond == result || else_value == result)
+ return false;
+ if (!direct_internal_fn_supported_p (IFN_COND_FMA, type, opt_type))
+ return false;
+ }
+
+ /* If the subtrahend (OPS[1]) is computed by a MULT_EXPR that
+ we'll visit later, we might be able to get a more profitable
+ match with fnma.
OTOH, if we don't, a negate / fma pair has likely lower latency
that a mult / subtract pair. */
- if (use_code == MINUS_EXPR && !negate_p
- && gimple_assign_rhs1 (use_stmt) == result
- && optab_handler (fms_optab, TYPE_MODE (type)) == CODE_FOR_nothing
- && optab_handler (fnma_optab, TYPE_MODE (type)) != CODE_FOR_nothing)
+ if (code == MINUS_EXPR
+ && !negate_p
+ && ops[0] == result
+ && !direct_internal_fn_supported_p (IFN_FMS, type, opt_type)
+ && direct_internal_fn_supported_p (IFN_FNMA, type, opt_type)
+ && TREE_CODE (ops[1]) == SSA_NAME
+ && has_single_use (ops[1]))
{
- tree rhs2 = gimple_assign_rhs2 (use_stmt);
-
- if (TREE_CODE (rhs2) == SSA_NAME)
- {
- gimple *stmt2 = SSA_NAME_DEF_STMT (rhs2);
- if (has_single_use (rhs2)
- && is_gimple_assign (stmt2)
- && gimple_assign_rhs_code (stmt2) == MULT_EXPR)
- return false;
- }
+ gimple *stmt2 = SSA_NAME_DEF_STMT (ops[1]);
+ if (is_gimple_assign (stmt2)
+ && gimple_assign_rhs_code (stmt2) == MULT_EXPR)
+ return false;
}
/* We can't handle a * b + a * b. */
- if (gimple_assign_rhs1 (use_stmt) == gimple_assign_rhs2 (use_stmt))
+ if (ops[0] == ops[1])
+ return false;
+ /* If deferring, make sure we are not looking at an instruction that
+ wouldn't have existed if we were not. */
+ if (state->m_deferring_p
+ && (state->m_mul_result_set.contains (ops[0])
+ || state->m_mul_result_set.contains (ops[1])))
return false;
- /* While it is possible to validate whether or not the exact form
- that we've recognized is available in the backend, the assumption
- is that the transformation is never a loss. For instance, suppose
- the target only has the plain FMA pattern available. Consider
- a*b-c -> fma(a,b,-c): we've exchanged MUL+SUB for FMA+NEG, which
- is still two operations. Consider -(a*b)-c -> fma(-a,b,-c): we
- still have 3 operations, but in the FMA form the two NEGs are
- independent and could be run in parallel. */
- }
-
- FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, mul_result)
- {
- gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
- enum tree_code use_code;
- tree addop, mulop1 = op1, result = mul_result;
- bool negate_p = false;
-
- if (is_gimple_debug (use_stmt))
- continue;
-
- use_code = gimple_assign_rhs_code (use_stmt);
- if (use_code == NEGATE_EXPR)
+ if (check_defer)
{
- result = gimple_assign_lhs (use_stmt);
- single_imm_use (gimple_assign_lhs (use_stmt), &use_p, &neguse_stmt);
- gsi_remove (&gsi, true);
- release_defs (use_stmt);
+ tree use_lhs = gimple_get_lhs (use_stmt);
+ if (state->m_last_result)
+ {
+ if (ops[1] == state->m_last_result
+ || ops[0] == state->m_last_result)
+ defer = true;
+ else
+ defer = false;
+ }
+ else
+ {
+ gcc_checking_assert (!state->m_initial_phi);
+ gphi *phi;
+ if (ops[0] == result)
+ phi = result_of_phi (ops[1]);
+ else
+ {
+ gcc_assert (ops[1] == result);
+ phi = result_of_phi (ops[0]);
+ }
- use_stmt = neguse_stmt;
- gsi = gsi_for_stmt (use_stmt);
- use_code = gimple_assign_rhs_code (use_stmt);
- negate_p = true;
- }
+ if (phi)
+ {
+ state->m_initial_phi = phi;
+ defer = true;
+ }
+ else
+ defer = false;
+ }
- if (gimple_assign_rhs1 (use_stmt) == result)
- {
- addop = gimple_assign_rhs2 (use_stmt);
- /* a * b - c -> a * b + (-c) */
- if (gimple_assign_rhs_code (use_stmt) == MINUS_EXPR)
- addop = force_gimple_operand_gsi (&gsi,
- build1 (NEGATE_EXPR,
- type, addop),
- true, NULL_TREE, true,
- GSI_SAME_STMT);
+ state->m_last_result = use_lhs;
+ check_defer = false;
}
else
+ defer = false;
+
+ /* While it is possible to validate whether or not the exact form that
+ we've recognized is available in the backend, the assumption is that
+ if the deferring logic above did not trigger, the transformation is
+ never a loss. For instance, suppose the target only has the plain FMA
+ pattern available. Consider a*b-c -> fma(a,b,-c): we've exchanged
+ MUL+SUB for FMA+NEG, which is still two operations. Consider
+ -(a*b)-c -> fma(-a,b,-c): we still have 3 operations, but in the FMA
+ form the two NEGs are independent and could be run in parallel. */
+ }
+
+ if (defer)
+ {
+ fma_transformation_info fti;
+ fti.mul_stmt = mul_stmt;
+ fti.mul_result = mul_result;
+ fti.op1 = op1;
+ fti.op2 = op2;
+ state->m_candidates.safe_push (fti);
+ state->m_mul_result_set.add (mul_result);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- addop = gimple_assign_rhs1 (use_stmt);
- /* a - b * c -> (-b) * c + a */
- if (gimple_assign_rhs_code (use_stmt) == MINUS_EXPR)
- negate_p = !negate_p;
+ fprintf (dump_file, "Deferred generating FMA for multiplication ");
+ print_gimple_stmt (dump_file, mul_stmt, 0, TDF_NONE);
+ fprintf (dump_file, "\n");
}
- if (negate_p)
- mulop1 = force_gimple_operand_gsi (&gsi,
- build1 (NEGATE_EXPR,
- type, mulop1),
- true, NULL_TREE, true,
- GSI_SAME_STMT);
-
- fma_stmt = gimple_build_assign (gimple_assign_lhs (use_stmt),
- FMA_EXPR, mulop1, op2, addop);
- gsi_replace (&gsi, fma_stmt, true);
- widen_mul_stats.fmas_inserted++;
+ return false;
+ }
+ else
+ {
+ if (state->m_deferring_p)
+ cancel_fma_deferring (state);
+ convert_mult_to_fma_1 (mul_result, op1, op2);
+ return true;
}
-
- return true;
}
static bool
convert_to_divmod (gassign *stmt)
{
- if (stmt_can_throw_internal (stmt)
+ if (stmt_can_throw_internal (cfun, stmt)
|| !divmod_candidate_p (stmt))
return false;
&& operand_equal_p (op1, gimple_assign_rhs1 (use_stmt), 0)
&& operand_equal_p (op2, gimple_assign_rhs2 (use_stmt), 0))
{
- if (stmt_can_throw_internal (use_stmt))
+ if (stmt_can_throw_internal (cfun, use_stmt))
continue;
basic_block bb = gimple_bb (use_stmt);
&& operand_equal_p (top_op2, gimple_assign_rhs2 (use_stmt), 0))
{
if (use_stmt == top_stmt
- || stmt_can_throw_internal (use_stmt)
+ || stmt_can_throw_internal (cfun, use_stmt)
|| !dominated_by_p (CDI_DOMINATORS, gimple_bb (use_stmt), top_bb))
continue;
}; // class pass_optimize_widening_mul
-unsigned int
-pass_optimize_widening_mul::execute (function *fun)
+/* Walker class to perform the transformation in reverse dominance order. */
+
+class math_opts_dom_walker : public dom_walker
{
- basic_block bb;
- bool cfg_changed = false;
+public:
+ /* Constructor, CFG_CHANGED is a pointer to a boolean flag that will be set
+ if walking modidifes the CFG. */
- memset (&widen_mul_stats, 0, sizeof (widen_mul_stats));
- calculate_dominance_info (CDI_DOMINATORS);
- renumber_gimple_stmt_uids ();
+ math_opts_dom_walker (bool *cfg_changed_p)
+ : dom_walker (CDI_DOMINATORS), m_last_result_set (),
+ m_cfg_changed_p (cfg_changed_p) {}
- FOR_EACH_BB_FN (bb, fun)
+ /* The actual actions performed in the walk. */
+
+ virtual void after_dom_children (basic_block);
+
+ /* Set of results of chains of multiply and add statement combinations that
+ were not transformed into FMAs because of active deferring. */
+ hash_set<tree> m_last_result_set;
+
+ /* Pointer to a flag of the user that needs to be set if CFG has been
+ modified. */
+ bool *m_cfg_changed_p;
+};
+
+void
+math_opts_dom_walker::after_dom_children (basic_block bb)
+{
+ gimple_stmt_iterator gsi;
+
+ fma_deferring_state fma_state (PARAM_VALUE (PARAM_AVOID_FMA_MAX_BITS) > 0);
+
+ for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
{
- gimple_stmt_iterator gsi;
+ gimple *stmt = gsi_stmt (gsi);
+ enum tree_code code;
- for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi);)
- {
- gimple *stmt = gsi_stmt (gsi);
- enum tree_code code;
+ if (is_gimple_assign (stmt))
+ {
+ code = gimple_assign_rhs_code (stmt);
+ switch (code)
+ {
+ case MULT_EXPR:
+ if (!convert_mult_to_widen (stmt, &gsi)
+ && !convert_expand_mult_copysign (stmt, &gsi)
+ && convert_mult_to_fma (stmt,
+ gimple_assign_rhs1 (stmt),
+ gimple_assign_rhs2 (stmt),
+ &fma_state))
+ {
+ gsi_remove (&gsi, true);
+ release_defs (stmt);
+ continue;
+ }
+ break;
+
+ case PLUS_EXPR:
+ case MINUS_EXPR:
+ if (!convert_plusminus_to_widen (&gsi, stmt, code))
+ match_uaddsub_overflow (&gsi, stmt, code);
+ break;
+
+ case TRUNC_MOD_EXPR:
+ convert_to_divmod (as_a<gassign *> (stmt));
+ break;
- if (is_gimple_assign (stmt))
+ default:;
+ }
+ }
+ else if (is_gimple_call (stmt))
+ {
+ tree fndecl = gimple_call_fndecl (stmt);
+ if (fndecl && gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
{
- code = gimple_assign_rhs_code (stmt);
- switch (code)
+ switch (DECL_FUNCTION_CODE (fndecl))
{
- case MULT_EXPR:
- if (!convert_mult_to_widen (stmt, &gsi)
- && !convert_expand_mult_copysign (stmt, &gsi)
+ case BUILT_IN_POWF:
+ case BUILT_IN_POW:
+ case BUILT_IN_POWL:
+ if (gimple_call_lhs (stmt)
+ && TREE_CODE (gimple_call_arg (stmt, 1)) == REAL_CST
+ && real_equal
+ (&TREE_REAL_CST (gimple_call_arg (stmt, 1)),
+ &dconst2)
&& convert_mult_to_fma (stmt,
- gimple_assign_rhs1 (stmt),
- gimple_assign_rhs2 (stmt)))
+ gimple_call_arg (stmt, 0),
+ gimple_call_arg (stmt, 0),
+ &fma_state))
{
- gsi_remove (&gsi, true);
+ unlink_stmt_vdef (stmt);
+ if (gsi_remove (&gsi, true)
+ && gimple_purge_dead_eh_edges (bb))
+ *m_cfg_changed_p = true;
release_defs (stmt);
continue;
}
break;
- case PLUS_EXPR:
- case MINUS_EXPR:
- if (!convert_plusminus_to_widen (&gsi, stmt, code))
- match_uaddsub_overflow (&gsi, stmt, code);
- break;
-
- case TRUNC_MOD_EXPR:
- convert_to_divmod (as_a<gassign *> (stmt));
- break;
-
default:;
}
}
- else if (is_gimple_call (stmt)
- && gimple_call_lhs (stmt))
- {
- tree fndecl = gimple_call_fndecl (stmt);
- if (fndecl
- && gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
- {
- switch (DECL_FUNCTION_CODE (fndecl))
- {
- case BUILT_IN_POWF:
- case BUILT_IN_POW:
- case BUILT_IN_POWL:
- if (TREE_CODE (gimple_call_arg (stmt, 1)) == REAL_CST
- && real_equal
- (&TREE_REAL_CST (gimple_call_arg (stmt, 1)),
- &dconst2)
- && convert_mult_to_fma (stmt,
- gimple_call_arg (stmt, 0),
- gimple_call_arg (stmt, 0)))
- {
- unlink_stmt_vdef (stmt);
- if (gsi_remove (&gsi, true)
- && gimple_purge_dead_eh_edges (bb))
- cfg_changed = true;
- release_defs (stmt);
- continue;
- }
- break;
-
- default:;
- }
- }
- }
- gsi_next (&gsi);
+ else
+ cancel_fma_deferring (&fma_state);
}
+ gsi_next (&gsi);
}
+ if (fma_state.m_deferring_p
+ && fma_state.m_initial_phi)
+ {
+ gcc_checking_assert (fma_state.m_last_result);
+ if (!last_fma_candidate_feeds_initial_phi (&fma_state,
+ &m_last_result_set))
+ cancel_fma_deferring (&fma_state);
+ else
+ m_last_result_set.add (fma_state.m_last_result);
+ }
+}
+
+
+unsigned int
+pass_optimize_widening_mul::execute (function *fun)
+{
+ bool cfg_changed = false;
+
+ memset (&widen_mul_stats, 0, sizeof (widen_mul_stats));
+ calculate_dominance_info (CDI_DOMINATORS);
+ renumber_gimple_stmt_uids ();
+
+ math_opts_dom_walker (&cfg_changed).walk (ENTRY_BLOCK_PTR_FOR_FN (cfun));
statistics_counter_event (fun, "widening multiplications inserted",
widen_mul_stats.widen_mults_inserted);
projects / thirdparty / gcc.git / blobdiff