/* Straight-line strength reduction.
- Copyright (C) 2012-2017 Free Software Foundation, Inc.
+ Copyright (C) 2012-2019 Free Software Foundation, Inc.
Contributed by Bill Schmidt, IBM <wschmidt@linux.ibm.com>
This file is part of GCC.
#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
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;
c = base_cand_from_table (base);
- if (!c || c->kind != CAND_PHI)
+ if (!c || c->kind != CAND_PHI
+ || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (c->cand_stmt)))
return 0;
return c->cand_num;
gimple_bb (one_basis->cand_stmt)))
continue;
+ tree lhs = gimple_assign_lhs (one_basis->cand_stmt);
+ if (lhs && TREE_CODE (lhs) == SSA_NAME
+ && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
+ continue;
+
if (!basis || basis->cand_num < one_basis->cand_num)
basis = one_basis;
}
c->kind = kind;
c->cand_num = cand_vec.length () + 1;
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;
widest_int index = *pindex;
tree mult_op0, t1, t2, type;
widest_int c1, c2, c3, c4, c5;
+ offset_int mem_offset;
if (!base
|| !offset
|| TREE_CODE (base) != MEM_REF
+ || !mem_ref_offset (base).is_constant (&mem_offset)
|| TREE_CODE (offset) != MULT_EXPR
|| TREE_CODE (TREE_OPERAND (offset, 1)) != INTEGER_CST
|| wi::umod_floor (index, BITS_PER_UNIT) != 0)
return false;
t1 = TREE_OPERAND (base, 0);
- c1 = widest_int::from (mem_ref_offset (base), SIGNED);
+ c1 = widest_int::from (mem_offset, SIGNED);
type = TREE_TYPE (TREE_OPERAND (base, 1));
mult_op0 = TREE_OPERAND (offset, 0);
slsr_process_ref (gimple *gs)
{
tree ref_expr, base, offset, type;
- HOST_WIDE_INT bitsize, bitpos;
+ poly_int64 bitsize, bitpos;
machine_mode mode;
int unsignedp, reversep, volatilep;
slsr_cand_t c;
base = get_inner_reference (ref_expr, &bitsize, &bitpos, &offset, &mode,
&unsignedp, &reversep, &volatilep);
- if (reversep)
+ HOST_WIDE_INT cbitpos;
+ if (reversep || !bitpos.is_constant (&cbitpos))
return;
- widest_int index = bitpos;
+ widest_int index = cbitpos;
if (!restructure_reference (&base, &offset, &index, &type))
return;
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
+ else if (TREE_CODE (rhs2) == INTEGER_CST)
{
/* Record an interpretation for the multiply-immediate. */
c = create_mul_imm_cand (gs, rhs1, rhs2, speed);
{
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);
}
}
- else
+ else if (TREE_CODE (rhs2) == INTEGER_CST)
{
/* Record an interpretation for the add-immediate. */
widest_int index = wi::to_widest (rhs2);
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 (!first_cand)
+ first_cand = c;
+
+ if (first_cand != c)
+ c->first_interp = first_cand->cand_num;
+
if (base_cand->next_interp)
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 (!first_cand)
+ first_cand = c;
+
+ if (first_cand != c)
+ c->first_interp = first_cand->cand_num;
+
if (base_cand->next_interp)
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);
else if (is_gimple_assign (gs)
- && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (gs))))
+ && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (gs)))
+ || POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (gs)))))
{
tree rhs1 = NULL_TREE, rhs2 = NULL_TREE;
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);
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 = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;
}
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 = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;
}
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);
}
else if (first_dep->kind == CAND_MULT)
{
int cost = mult_by_coeff_cost (incr, mode, speed);
- int repl_savings = mul_cost (speed, mode) - add_cost (speed, mode);
+ int repl_savings;
+
+ if (tree_fits_shwi_p (first_dep->stride))
+ {
+ HOST_WIDE_INT hwi_stride = tree_to_shwi (first_dep->stride);
+ repl_savings = mult_by_coeff_cost (hwi_stride, mode, speed);
+ }
+ else
+ repl_savings = mul_cost (speed, mode);
+ repl_savings -= add_cost (speed, mode);
+
if (speed)
cost = lowest_cost_path (cost, repl_savings, first_dep,
incr_vec[i].incr, COUNT_PHIS);
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;
}
gsi_insert_after (&gsi, cast_stmt, GSI_NEW_STMT);
gimple_set_location (cast_stmt, loc);
}
- gsi_insert_after (&gsi, init_stmt, GSI_SAME_STMT);
+ gsi_insert_after (&gsi, init_stmt, GSI_NEW_STMT);
}
gimple_set_location (init_stmt, gimple_location (basis_stmt));
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 = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;
}
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 = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;
}
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 = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;
}
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 = cc->next_interp ? lookup_cand (cc->next_interp) : NULL;
}
if (dump_file && (dump_flags & TDF_DETAILS))