/* Straight-line strength reduction.
- Copyright (C) 2012-2018 Free Software Foundation, Inc.
+ Copyright (C) 2012-2021 Free Software Foundation, Inc.
Contributed by Bill Schmidt, IBM <wschmidt@linux.ibm.com>
This file is part of GCC.
#include "cfgloop.h"
#include "tree-cfg.h"
#include "domwalk.h"
-#include "params.h"
#include "tree-ssa-address.h"
#include "tree-affine.h"
+#include "tree-eh.h"
#include "builtins.h"
\f
/* Information about a strength reduction candidate. Each statement
CAND_PHI
};
-struct slsr_cand_d
+class slsr_cand_d
{
+public:
/* The candidate statement S1. */
gimple *cand_stmt;
of a statement. */
cand_idx next_interp;
+ /* Index of the first candidate record in a chain for the same
+ statement. */
+ cand_idx first_interp;
+
/* Index of the basis statement S0, if any, in the candidate vector. */
cand_idx basis;
tree cached_basis;
};
-typedef struct slsr_cand_d slsr_cand, *slsr_cand_t;
-typedef const struct slsr_cand_d *const_slsr_cand_t;
+typedef class slsr_cand_d slsr_cand, *slsr_cand_t;
+typedef const class slsr_cand_d *const_slsr_cand_t;
/* Pointers to candidates are chained together as part of a mapping
from base expressions to the candidates that use them. */
of the cost of initializers. The absolute value of the increment
is stored in the incr_info. */
-struct incr_info_d
+class incr_info_d
{
+public:
/* The increment that relates a candidate to its basis. */
widest_int incr;
basic_block init_bb;
};
-typedef struct incr_info_d incr_info, *incr_info_t;
+typedef class incr_info_d incr_info, *incr_info_t;
/* Candidates are maintained in a vector. If candidate X dominates
candidate Y, then X appears before Y in the vector; but the
static slsr_cand_t
lookup_cand (cand_idx idx)
{
- return cand_vec[idx - 1];
+ return cand_vec[idx];
}
/* Helper for hashing a candidate chain header. */
recurse + 1))
{
retval = false;
- BREAK_FROM_IMM_USE_STMT (iter);
+ break;
}
}
// Limit potential of N^2 behavior for long candidate chains.
int iters = 0;
- int max_iters = PARAM_VALUE (PARAM_MAX_SLSR_CANDIDATE_SCAN);
+ int max_iters = param_max_slsr_candidate_scan;
mapping_key.base_expr = base_expr;
chain = base_cand_map->find (&mapping_key);
c->cand_type = ctype;
c->stride_type = stype;
c->kind = kind;
- c->cand_num = cand_vec.length () + 1;
+ c->cand_num = cand_vec.length ();
c->next_interp = 0;
+ c->first_interp = c->cand_num;
c->dependent = 0;
c->sibling = 0;
c->def_phi = kind == CAND_MULT ? find_phi_def (base) : 0;
unsigned i;
tree arg0_base = NULL_TREE, base_type;
slsr_cand_t c;
- struct loop *cand_loop = gimple_bb (phi)->loop_father;
+ class loop *cand_loop = gimple_bb (phi)->loop_father;
unsigned savings = 0;
/* A CAND_PHI requires each of its arguments to have the same
return base_cand->index;
}
- if (base_cand->next_interp)
- base_cand = lookup_cand (base_cand->next_interp);
- else
- base_cand = NULL;
+ base_cand = lookup_cand (base_cand->next_interp);
}
return 0;
+ stmt_cost (base_cand->cand_stmt, speed));
}
- if (base_cand->next_interp)
- base_cand = lookup_cand (base_cand->next_interp);
- else
- base_cand = NULL;
+ base_cand = lookup_cand (base_cand->next_interp);
}
if (!base)
+ stmt_cost (base_cand->cand_stmt, speed));
}
- if (base_cand->next_interp)
- base_cand = lookup_cand (base_cand->next_interp);
- else
- base_cand = NULL;
+ base_cand = lookup_cand (base_cand->next_interp);
}
if (!base)
is the stride and RHS2 is the base expression. */
c2 = create_mul_ssa_cand (gs, rhs2, rhs1, speed);
c->next_interp = c2->cand_num;
+ c2->first_interp = c->cand_num;
}
- else if (TREE_CODE (rhs2) == INTEGER_CST)
+ else if (TREE_CODE (rhs2) == INTEGER_CST && !integer_zerop (rhs2))
{
/* Record an interpretation for the multiply-immediate. */
c = create_mul_imm_cand (gs, rhs1, rhs2, speed);
+ stmt_cost (addend_cand->cand_stmt, speed));
}
- if (addend_cand->next_interp)
- addend_cand = lookup_cand (addend_cand->next_interp);
- else
- addend_cand = NULL;
+ addend_cand = lookup_cand (addend_cand->next_interp);
}
while (base_cand && !base && base_cand->kind != CAND_PHI)
savings = (subtrahend_cand->dead_savings
+ stmt_cost (subtrahend_cand->cand_stmt, speed));
}
-
- if (subtrahend_cand->next_interp)
- subtrahend_cand = lookup_cand (subtrahend_cand->next_interp);
- else
- subtrahend_cand = NULL;
+
+ subtrahend_cand = lookup_cand (subtrahend_cand->next_interp);
}
}
- if (base_cand->next_interp)
- base_cand = lookup_cand (base_cand->next_interp);
- else
- base_cand = NULL;
+ base_cand = lookup_cand (base_cand->next_interp);
}
if (!base)
+ stmt_cost (base_cand->cand_stmt, speed));
}
- if (base_cand->next_interp)
- base_cand = lookup_cand (base_cand->next_interp);
- else
- base_cand = NULL;
+ base_cand = lookup_cand (base_cand->next_interp);
}
if (!base)
{
c2 = create_add_ssa_cand (gs, rhs2, rhs1, false, speed);
if (c)
- c->next_interp = c2->cand_num;
+ {
+ c->next_interp = c2->cand_num;
+ c2->first_interp = c->cand_num;
+ }
else
add_cand_for_stmt (gs, c2);
}
if (base_cand && base_cand->kind != CAND_PHI)
{
+ slsr_cand_t first_cand = NULL;
+
while (base_cand)
{
/* Propagate all data from the base candidate except the type,
base_cand->index, base_cand->stride,
ctype, base_cand->stride_type,
savings);
- if (base_cand->next_interp)
- base_cand = lookup_cand (base_cand->next_interp);
- else
- base_cand = NULL;
+ if (!first_cand)
+ first_cand = c;
+
+ if (first_cand != c)
+ c->first_interp = first_cand->cand_num;
+
+ base_cand = lookup_cand (base_cand->next_interp);
}
}
else
c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0,
integer_one_node, ctype, sizetype, 0);
c->next_interp = c2->cand_num;
+ c2->first_interp = c->cand_num;
}
/* Add the first (or only) interpretation to the statement-candidate
if (base_cand && base_cand->kind != CAND_PHI)
{
+ slsr_cand_t first_cand = NULL;
+
while (base_cand)
{
/* Propagate all data from the base candidate. */
base_cand->index, base_cand->stride,
base_cand->cand_type,
base_cand->stride_type, savings);
- if (base_cand->next_interp)
- base_cand = lookup_cand (base_cand->next_interp);
- else
- base_cand = NULL;
+ if (!first_cand)
+ first_cand = c;
+
+ if (first_cand != c)
+ c->first_interp = first_cand->cand_num;
+
+ base_cand = lookup_cand (base_cand->next_interp);
}
}
else
integer_one_node, TREE_TYPE (rhs1),
sizetype, 0);
c->next_interp = c2->cand_num;
+ c2->first_interp = c->cand_num;
}
/* Add the first (or only) interpretation to the statement-candidate
{
gimple *gs = gsi_stmt (gsi);
+ if (stmt_could_throw_p (cfun, gs))
+ continue;
+
if (gimple_vuse (gs) && gimple_assign_single_p (gs))
slsr_process_ref (gs);
print_generic_expr (dump_file, c->cand_type);
fprintf (dump_file, "\n basis: %d dependent: %d sibling: %d\n",
c->basis, c->dependent, c->sibling);
- fprintf (dump_file, " next-interp: %d dead-savings: %d\n",
- c->next_interp, c->dead_savings);
+ fprintf (dump_file,
+ " next-interp: %d first-interp: %d dead-savings: %d\n",
+ c->next_interp, c->first_interp, c->dead_savings);
if (c->def_phi)
fprintf (dump_file, " phi: %d\n", c->def_phi);
fputs ("\n", dump_file);
fprintf (dump_file, "\nStrength reduction candidate vector:\n\n");
FOR_EACH_VEC_ELT (cand_vec, i, c)
- dump_candidate (c);
+ if (c != NULL)
+ dump_candidate (c);
}
/* Callback used to dump the candidate chains hash table. */
update_stmt (c->cand_stmt);
}
+/* Return true if CAND_REF candidate C is a valid memory reference. */
+
+static bool
+valid_mem_ref_cand_p (slsr_cand_t c)
+{
+ if (TREE_CODE (TREE_OPERAND (c->stride, 1)) != INTEGER_CST)
+ return false;
+
+ struct mem_address addr
+ = { NULL_TREE, c->base_expr, TREE_OPERAND (c->stride, 0),
+ TREE_OPERAND (c->stride, 1), wide_int_to_tree (sizetype, c->index) };
+
+ return
+ valid_mem_ref_p (TYPE_MODE (c->cand_type), TYPE_ADDR_SPACE (c->cand_type),
+ &addr);
+}
+
/* Replace CAND_REF candidate C, each sibling of candidate C, and each
dependent of candidate C with an equivalent strength-reduced data
reference. */
static void
replace_refs (slsr_cand_t c)
{
+ /* Replacing a chain of only 2 candidates which are valid memory references
+ is generally counter-productive because you cannot recoup the additional
+ calculation added in front of them. */
+ if (c->basis == 0
+ && c->dependent
+ && !lookup_cand (c->dependent)->dependent
+ && valid_mem_ref_cand_p (c)
+ && valid_mem_ref_cand_p (lookup_cand (c->dependent)))
+ return;
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fputs ("Replacing reference: ", dump_file);
tree lhs = gimple_assign_lhs (c->cand_stmt);
gassign *copy_stmt = gimple_build_assign (lhs, basis_name);
gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
- slsr_cand_t cc = c;
+ slsr_cand_t cc = lookup_cand (c->first_interp);
gimple_set_location (copy_stmt, gimple_location (c->cand_stmt));
gsi_replace (&gsi, copy_stmt, false);
- c->cand_stmt = copy_stmt;
- while (cc->next_interp)
+ while (cc)
{
- cc = lookup_cand (cc->next_interp);
cc->cand_stmt = copy_stmt;
+ cc = lookup_cand (cc->next_interp);
}
if (dump_file && (dump_flags & TDF_DETAILS))
stmt_to_print = copy_stmt;
else
{
gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
- slsr_cand_t cc = c;
+ slsr_cand_t cc = lookup_cand (c->first_interp);
gimple_assign_set_rhs_with_ops (&gsi, code, basis_name, bump_tree);
update_stmt (gsi_stmt (gsi));
- c->cand_stmt = gsi_stmt (gsi);
- while (cc->next_interp)
+ while (cc)
{
- cc = lookup_cand (cc->next_interp);
cc->cand_stmt = gsi_stmt (gsi);
+ cc = lookup_cand (cc->next_interp);
}
if (dump_file && (dump_flags & TDF_DETAILS))
stmt_to_print = gsi_stmt (gsi);
for (i = 0; i < gimple_phi_num_args (phi); i++)
{
tree arg = gimple_phi_arg_def (phi, i);
+ gimple *arg_def = SSA_NAME_DEF_STMT (arg);
- if (!operand_equal_p (arg, phi_cand->base_expr, 0))
+ if (gimple_code (arg_def) == GIMPLE_PHI)
+ record_phi_increments_1 (basis, arg_def);
+ else
{
- gimple *arg_def = SSA_NAME_DEF_STMT (arg);
+ widest_int diff;
- if (gimple_code (arg_def) == GIMPLE_PHI)
- record_phi_increments_1 (basis, arg_def);
+ if (operand_equal_p (arg, phi_cand->base_expr, 0))
+ {
+ diff = -basis->index;
+ record_increment (phi_cand, diff, PHI_ADJUST);
+ }
else
{
slsr_cand_t arg_cand = base_cand_from_table (arg);
- widest_int diff = arg_cand->index - basis->index;
+ diff = arg_cand->index - basis->index;
record_increment (arg_cand, diff, PHI_ADJUST);
}
}
for (i = 0; i < gimple_phi_num_args (phi); i++)
{
tree arg = gimple_phi_arg_def (phi, i);
+ gimple *arg_def = SSA_NAME_DEF_STMT (arg);
- if (!operand_equal_p (arg, phi_cand->base_expr, 0))
+ if (gimple_code (arg_def) == GIMPLE_PHI)
{
- gimple *arg_def = SSA_NAME_DEF_STMT (arg);
-
- if (gimple_code (arg_def) == GIMPLE_PHI)
+ int feeding_savings = 0;
+ tree feeding_var = gimple_phi_result (arg_def);
+ cost += phi_incr_cost_1 (c, incr, arg_def, &feeding_savings);
+ if (uses_consumed_by_stmt (feeding_var, phi))
+ *savings += feeding_savings;
+ }
+ else
+ {
+ widest_int diff;
+ slsr_cand_t arg_cand;
+
+ /* When the PHI argument is just a pass-through to the base
+ expression of the hidden basis, the difference is zero minus
+ the index of the basis. There is no potential savings by
+ eliminating a statement in this case. */
+ if (operand_equal_p (arg, phi_cand->base_expr, 0))
{
- int feeding_savings = 0;
- tree feeding_var = gimple_phi_result (arg_def);
- cost += phi_incr_cost_1 (c, incr, arg_def, &feeding_savings);
- if (uses_consumed_by_stmt (feeding_var, phi))
- *savings += feeding_savings;
+ arg_cand = (slsr_cand_t)NULL;
+ diff = -basis->index;
}
else
{
- slsr_cand_t arg_cand = base_cand_from_table (arg);
- widest_int diff = arg_cand->index - basis->index;
-
- if (incr == diff)
+ arg_cand = base_cand_from_table (arg);
+ diff = arg_cand->index - basis->index;
+ }
+
+ if (incr == diff)
+ {
+ tree basis_lhs = gimple_assign_lhs (basis->cand_stmt);
+ cost += add_cost (true, TYPE_MODE (TREE_TYPE (basis_lhs)));
+ if (arg_cand)
{
- tree basis_lhs = gimple_assign_lhs (basis->cand_stmt);
tree lhs = gimple_assign_lhs (arg_cand->cand_stmt);
- cost += add_cost (true, TYPE_MODE (TREE_TYPE (basis_lhs)));
if (uses_consumed_by_stmt (lhs, phi))
*savings += stmt_cost (arg_cand->cand_stmt, true);
}
for (i = 0; i < gimple_phi_num_args (phi); i++)
{
tree arg = gimple_phi_arg_def (phi, i);
+ gimple *arg_def = SSA_NAME_DEF_STMT (arg);
- if (!operand_equal_p (arg, phi_cand->base_expr, 0))
+ if (gimple_code (arg_def) == GIMPLE_PHI)
+ ncd = ncd_with_phi (c, incr, as_a <gphi *> (arg_def), ncd, where);
+ else
{
- gimple *arg_def = SSA_NAME_DEF_STMT (arg);
+ widest_int diff;
- if (gimple_code (arg_def) == GIMPLE_PHI)
- ncd = ncd_with_phi (c, incr, as_a <gphi *> (arg_def), ncd,
- where);
- else
+ if (operand_equal_p (arg, phi_cand->base_expr, 0))
+ diff = -basis->index;
+ else
{
slsr_cand_t arg_cand = base_cand_from_table (arg);
- widest_int diff = arg_cand->index - basis->index;
- basic_block pred = gimple_phi_arg_edge (phi, i)->src;
-
- if ((incr == diff) || (!address_arithmetic_p && incr == -diff))
- ncd = ncd_for_two_cands (ncd, pred, *where, NULL, where);
+ diff = arg_cand->index - basis->index;
}
+
+ basic_block pred = gimple_phi_arg_edge (phi, i)->src;
+
+ if ((incr == diff) || (!address_arithmetic_p && incr == -diff))
+ ncd = ncd_for_two_cands (ncd, pred, *where, NULL, where);
}
}
fputs ("Using existing initializer: ", dump_file);
print_gimple_stmt (dump_file,
SSA_NAME_DEF_STMT (incr_vec[i].initializer),
- 0, 0);
+ 0, TDF_NONE);
}
continue;
}
return false;
tree arg = gimple_phi_arg_def (phi, i);
+ gimple *arg_def = SSA_NAME_DEF_STMT (arg);
- if (!operand_equal_p (arg, phi_cand->base_expr, 0))
+ if (gimple_code (arg_def) == GIMPLE_PHI)
{
- gimple *arg_def = SSA_NAME_DEF_STMT (arg);
+ if (!all_phi_incrs_profitable_1 (c, as_a <gphi *> (arg_def), spread)
+ || *spread > MAX_SPREAD)
+ return false;
+ }
+ else
+ {
+ int j;
+ widest_int increment;
- if (gimple_code (arg_def) == GIMPLE_PHI)
- {
- if (!all_phi_incrs_profitable_1 (c, as_a <gphi *> (arg_def),
- spread)
- || *spread > MAX_SPREAD)
- return false;
- }
+ if (operand_equal_p (arg, phi_cand->base_expr, 0))
+ increment = -basis->index;
else
{
- int j;
slsr_cand_t arg_cand = base_cand_from_table (arg);
- widest_int increment = arg_cand->index - basis->index;
+ increment = arg_cand->index - basis->index;
+ }
- if (!address_arithmetic_p && wi::neg_p (increment))
- increment = -increment;
+ if (!address_arithmetic_p && wi::neg_p (increment))
+ increment = -increment;
- j = incr_vec_index (increment);
+ j = incr_vec_index (increment);
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, " Conditional candidate %d, phi: ",
- c->cand_num);
- print_gimple_stmt (dump_file, phi, 0);
- fputs (" increment: ", dump_file);
- print_decs (increment, dump_file);
- if (j < 0)
- fprintf (dump_file,
- "\n Not replaced; incr_vec overflow.\n");
- else {
- fprintf (dump_file, "\n cost: %d\n", incr_vec[j].cost);
- if (profitable_increment_p (j))
- fputs (" Replacing...\n", dump_file);
- else
- fputs (" Not replaced.\n", dump_file);
- }
- }
-
- if (j < 0 || !profitable_increment_p (j))
- return false;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " Conditional candidate %d, phi: ",
+ c->cand_num);
+ print_gimple_stmt (dump_file, phi, 0);
+ fputs (" increment: ", dump_file);
+ print_decs (increment, dump_file);
+ if (j < 0)
+ fprintf (dump_file,
+ "\n Not replaced; incr_vec overflow.\n");
+ else {
+ fprintf (dump_file, "\n cost: %d\n", incr_vec[j].cost);
+ if (profitable_increment_p (j))
+ fputs (" Replacing...\n", dump_file);
+ else
+ fputs (" Not replaced.\n", dump_file);
+ }
}
+
+ if (j < 0 || !profitable_increment_p (j))
+ return false;
}
}
|| !operand_equal_p (new_rhs2, old_rhs1, 0))))
{
gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
- slsr_cand_t cc = c;
+ slsr_cand_t cc = lookup_cand (c->first_interp);
gimple_assign_set_rhs_with_ops (&gsi, new_code, new_rhs1, new_rhs2);
update_stmt (gsi_stmt (gsi));
- c->cand_stmt = gsi_stmt (gsi);
- while (cc->next_interp)
+ while (cc)
{
- cc = lookup_cand (cc->next_interp);
cc->cand_stmt = gsi_stmt (gsi);
+ cc = lookup_cand (cc->next_interp);
}
if (dump_file && (dump_flags & TDF_DETAILS))
orig_rhs2 = gimple_assign_rhs2 (c->cand_stmt);
cand_incr = cand_increment (c);
+ /* If orig_rhs2 is NULL, we have already replaced this in situ with
+ a copy statement under another interpretation. */
+ if (!orig_rhs2)
+ return;
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fputs ("Replacing: ", dump_file);
|| !operand_equal_p (rhs2, orig_rhs2, 0))
{
gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
- slsr_cand_t cc = c;
+ slsr_cand_t cc = lookup_cand (c->first_interp);
gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, basis_name, rhs2);
update_stmt (gsi_stmt (gsi));
- c->cand_stmt = gsi_stmt (gsi);
- while (cc->next_interp)
+ while (cc)
{
- cc = lookup_cand (cc->next_interp);
cc->cand_stmt = gsi_stmt (gsi);
+ cc = lookup_cand (cc->next_interp);
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
gassign *copy_stmt = gimple_build_assign (lhs, basis_name);
gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
- slsr_cand_t cc = c;
+ slsr_cand_t cc = lookup_cand (c->first_interp);
gimple_set_location (copy_stmt, gimple_location (c->cand_stmt));
gsi_replace (&gsi, copy_stmt, false);
- c->cand_stmt = copy_stmt;
- while (cc->next_interp)
+ while (cc)
{
- cc = lookup_cand (cc->next_interp);
cc->cand_stmt = copy_stmt;
+ cc = lookup_cand (cc->next_interp);
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
gassign *cast_stmt = gimple_build_assign (lhs, NOP_EXPR, basis_name);
- slsr_cand_t cc = c;
+ slsr_cand_t cc = lookup_cand (c->first_interp);
gimple_set_location (cast_stmt, gimple_location (c->cand_stmt));
gsi_replace (&gsi, cast_stmt, false);
- c->cand_stmt = cast_stmt;
- while (cc->next_interp)
+ while (cc)
{
- cc = lookup_cand (cc->next_interp);
cc->cand_stmt = cast_stmt;
+ cc = lookup_cand (cc->next_interp);
}
if (dump_file && (dump_flags & TDF_DETAILS))
/* Each candidate that has a null basis and a non-null
dependent is the root of a tree of related statements.
Analyze each tree to determine a subset of those
- statements that can be replaced with maximum benefit. */
- FOR_EACH_VEC_ELT (cand_vec, i, c)
+ statements that can be replaced with maximum benefit.
+
+ Note the first NULL element is skipped. */
+ FOR_EACH_VEC_ELT_FROM (cand_vec, i, c, 1)
{
slsr_cand_t first_dep;
/* Create the obstack where candidates will reside. */
gcc_obstack_init (&cand_obstack);
- /* Allocate the candidate vector. */
+ /* Allocate the candidate vector and initialize the first NULL element. */
cand_vec.create (128);
+ cand_vec.safe_push (NULL);
/* Allocate the mapping from statements to candidate indices. */
stmt_cand_map = new hash_map<gimple *, slsr_cand_t>;
git://gcc.gnu.org / gcc.git / blobdiff