/* Straight-line strength reduction.
- Copyright (C) 2012-2013 Free Software Foundation, Inc.
+ Copyright (C) 2012-2015 Free Software Foundation, Inc.
Contributed by Bill Schmidt, IBM <wschmidt@linux.ibm.com>
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
+#include "alias.h"
+#include "symtab.h"
+#include "options.h"
#include "tree.h"
-#include "gimple.h"
+#include "fold-const.h"
+#include "predict.h"
+#include "tm.h"
+#include "hard-reg-set.h"
+#include "function.h"
+#include "dominance.h"
+#include "cfg.h"
#include "basic-block.h"
+#include "tree-ssa-alias.h"
+#include "internal-fn.h"
+#include "gimple-expr.h"
+#include "gimple.h"
+#include "gimple-iterator.h"
+#include "gimplify-me.h"
+#include "stor-layout.h"
+#include "rtl.h"
+#include "flags.h"
+#include "insn-config.h"
+#include "expmed.h"
+#include "dojump.h"
+#include "explow.h"
+#include "calls.h"
+#include "emit-rtl.h"
+#include "varasm.h"
+#include "stmt.h"
+#include "expr.h"
#include "tree-pass.h"
#include "cfgloop.h"
#include "gimple-pretty-print.h"
-#include "tree-flow.h"
+#include "gimple-ssa.h"
+#include "tree-cfg.h"
+#include "tree-phinodes.h"
+#include "ssa-iterators.h"
+#include "stringpool.h"
+#include "tree-ssanames.h"
#include "domwalk.h"
-#include "pointer-set.h"
-#include "expmed.h"
#include "params.h"
-#include "hash-table.h"
+#include "tree-ssa-address.h"
+#include "tree-affine.h"
+#include "wide-int-print.h"
+#include "builtins.h"
\f
/* Information about a strength reduction candidate. Each statement
in the candidate table represents an expression of one of the
tree stride;
/* The index constant i. */
- double_int index;
+ widest_int index;
/* The type of the candidate. This is normally the type of base_expr,
but casts may have occurred when combining feeding instructions.
struct incr_info_d
{
/* The increment that relates a candidate to its basis. */
- double_int incr;
+ widest_int incr;
/* How many times the increment occurs in the candidate tree. */
unsigned count;
};
/* Pointer map embodying a mapping from statements to candidates. */
-static struct pointer_map_t *stmt_cand_map;
+static hash_map<gimple, slsr_cand_t> *stmt_cand_map;
/* Obstack for candidates. */
static struct obstack cand_obstack;
/* Forward function declarations. */
static slsr_cand_t base_cand_from_table (tree);
static tree introduce_cast_before_cand (slsr_cand_t, tree, tree);
+static bool legal_cast_p_1 (tree, tree);
\f
/* Produce a pointer to the IDX'th candidate in the candidate vector. */
/* Helper for hashing a candidate chain header. */
-struct cand_chain_hasher : typed_noop_remove <cand_chain>
+struct cand_chain_hasher : nofree_ptr_hash <cand_chain>
{
- typedef cand_chain value_type;
- typedef cand_chain compare_type;
- static inline hashval_t hash (const value_type *);
- static inline bool equal (const value_type *, const compare_type *);
+ static inline hashval_t hash (const cand_chain *);
+ static inline bool equal (const cand_chain *, const cand_chain *);
};
inline hashval_t
-cand_chain_hasher::hash (const value_type *p)
+cand_chain_hasher::hash (const cand_chain *p)
{
tree base_expr = p->base_expr;
return iterative_hash_expr (base_expr, 0);
}
inline bool
-cand_chain_hasher::equal (const value_type *chain1, const compare_type *chain2)
+cand_chain_hasher::equal (const cand_chain *chain1, const cand_chain *chain2)
{
return operand_equal_p (chain1->base_expr, chain2->base_expr, 0);
}
/* Hash table embodying a mapping from base exprs to chains of candidates. */
-static hash_table <cand_chain_hasher> base_cand_map;
+static hash_table<cand_chain_hasher> *base_cand_map;
\f
+/* Pointer map used by tree_to_aff_combination_expand. */
+static hash_map<tree, name_expansion *> *name_expansions;
+/* Pointer map embodying a mapping from bases to alternative bases. */
+static hash_map<tree, tree> *alt_base_map;
+
+/* Given BASE, use the tree affine combiniation facilities to
+ find the underlying tree expression for BASE, with any
+ immediate offset excluded.
+
+ N.B. we should eliminate this backtracking with better forward
+ analysis in a future release. */
+
+static tree
+get_alternative_base (tree base)
+{
+ tree *result = alt_base_map->get (base);
+
+ if (result == NULL)
+ {
+ tree expr;
+ aff_tree aff;
+
+ tree_to_aff_combination_expand (base, TREE_TYPE (base),
+ &aff, &name_expansions);
+ aff.offset = 0;
+ expr = aff_combination_to_tree (&aff);
+
+ gcc_assert (!alt_base_map->put (base, base == expr ? NULL : expr));
+
+ return expr == base ? NULL : expr;
+ }
+
+ return *result;
+}
+
/* Look in the candidate table for a CAND_PHI that defines BASE and
return it if found; otherwise return NULL. */
}
/* Helper routine for find_basis_for_candidate. May be called twice:
- once for the candidate's base expr, and optionally again for the
- candidate's phi definition. */
+ once for the candidate's base expr, and optionally again either for
+ the candidate's phi definition or for a CAND_REF's alternative base
+ expression. */
static slsr_cand_t
find_basis_for_base_expr (slsr_cand_t c, tree base_expr)
int max_iters = PARAM_VALUE (PARAM_MAX_SLSR_CANDIDATE_SCAN);
mapping_key.base_expr = base_expr;
- chain = base_cand_map.find (&mapping_key);
+ chain = base_cand_map->find (&mapping_key);
for (; chain && iters < max_iters; chain = chain->next, ++iters)
{
}
}
+ if (flag_expensive_optimizations && !basis && c->kind == CAND_REF)
+ {
+ tree alt_base_expr = get_alternative_base (c->base_expr);
+ if (alt_base_expr)
+ basis = find_basis_for_base_expr (c, alt_base_expr);
+ }
+
if (basis)
{
c->sibling = basis->dependent;
return 0;
}
-/* Record a mapping from the base expression of C to C itself, indicating that
- C may potentially serve as a basis using that base expression. */
+/* Record a mapping from BASE to C, indicating that C may potentially serve
+ as a basis using that base expression. BASE may be the same as
+ C->BASE_EXPR; alternatively BASE can be a different tree that share the
+ underlining expression of C->BASE_EXPR. */
static void
-record_potential_basis (slsr_cand_t c)
+record_potential_basis (slsr_cand_t c, tree base)
{
cand_chain_t node;
cand_chain **slot;
+ gcc_assert (base);
+
node = (cand_chain_t) obstack_alloc (&chain_obstack, sizeof (cand_chain));
- node->base_expr = c->base_expr;
+ node->base_expr = base;
node->cand = c;
node->next = NULL;
- slot = base_cand_map.find_slot (node, INSERT);
+ slot = base_cand_map->find_slot (node, INSERT);
if (*slot)
{
}
/* Allocate storage for a new candidate and initialize its fields.
- Attempt to find a basis for the candidate. */
+ Attempt to find a basis for the candidate.
+
+ For CAND_REF, an alternative base may also be recorded and used
+ to find a basis. This helps cases where the expression hidden
+ behind BASE (which is usually an SSA_NAME) has immediate offset,
+ e.g.
+
+ a2[i][j] = 1;
+ a2[i + 20][j] = 2; */
static slsr_cand_t
-alloc_cand_and_find_basis (enum cand_kind kind, gimple gs, tree base,
- double_int index, tree stride, tree ctype,
+alloc_cand_and_find_basis (enum cand_kind kind, gimple gs, tree base,
+ const widest_int &index, tree stride, tree ctype,
unsigned savings)
{
slsr_cand_t c = (slsr_cand_t) obstack_alloc (&cand_obstack,
else
c->basis = find_basis_for_candidate (c);
- record_potential_basis (c);
+ record_potential_basis (c, base);
+ if (flag_expensive_optimizations && kind == CAND_REF)
+ {
+ tree alt_base = get_alternative_base (base);
+ if (alt_base)
+ record_potential_basis (c, alt_base);
+ }
return c;
}
stmt_cost (gimple gs, bool speed)
{
tree lhs, rhs1, rhs2;
- enum machine_mode lhs_mode;
+ machine_mode lhs_mode;
gcc_assert (is_gimple_assign (gs));
lhs = gimple_assign_lhs (gs);
case MULT_EXPR:
rhs2 = gimple_assign_rhs2 (gs);
- if (host_integerp (rhs2, 0))
- return mult_by_coeff_cost (TREE_INT_CST_LOW (rhs2), lhs_mode, speed);
+ if (tree_fits_shwi_p (rhs2))
+ return mult_by_coeff_cost (tree_to_shwi (rhs2), lhs_mode, speed);
gcc_assert (TREE_CODE (rhs1) != INTEGER_CST);
return mul_cost (speed, lhs_mode);
case NEGATE_EXPR:
return neg_cost (speed, lhs_mode);
- case NOP_EXPR:
+ CASE_CONVERT:
return convert_cost (lhs_mode, TYPE_MODE (TREE_TYPE (rhs1)), speed);
/* Note that we don't assign costs to copies that in most cases
if (!def)
return (slsr_cand_t) NULL;
- result = (slsr_cand_t *) pointer_map_contains (stmt_cand_map, def);
+ result = stmt_cand_map->get (def);
if (result && (*result)->kind != CAND_REF)
return *result;
static void
add_cand_for_stmt (gimple gs, slsr_cand_t c)
{
- void **slot = pointer_map_insert (stmt_cand_map, gs);
- gcc_assert (!*slot);
- *slot = c;
+ gcc_assert (!stmt_cand_map->put (gs, c));
}
\f
/* Given PHI which contains a phi statement, determine whether it
is used to help find a basis for subsequent candidates. */
static void
-slsr_process_phi (gimple phi, bool speed)
+slsr_process_phi (gphi *phi, bool speed)
{
unsigned i;
tree arg0_base = NULL_TREE, base_type;
derived_base_name = arg;
if (SSA_NAME_IS_DEFAULT_DEF (arg))
- arg_bb = single_succ (ENTRY_BLOCK_PTR);
+ arg_bb = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
else
gimple_bb (SSA_NAME_DEF_STMT (arg));
}
CAND_PHI. */
base_type = TREE_TYPE (arg0_base);
- c = alloc_cand_and_find_basis (CAND_PHI, phi, arg0_base, double_int_zero,
- integer_one_node, base_type, savings);
+ c = alloc_cand_and_find_basis (CAND_PHI, phi, arg0_base,
+ 0, integer_one_node, base_type, savings);
/* Add the candidate to the statement-candidate mapping. */
add_cand_for_stmt (phi, c);
}
+/* Given PBASE which is a pointer to tree, look up the defining
+ statement for it and check whether the candidate is in the
+ form of:
+
+ X = B + (1 * S), S is integer constant
+ X = B + (i * S), S is integer one
+
+ If so, set PBASE to the candidate's base_expr and return double
+ int (i * S).
+ Otherwise, just return double int zero. */
+
+static widest_int
+backtrace_base_for_ref (tree *pbase)
+{
+ tree base_in = *pbase;
+ slsr_cand_t base_cand;
+
+ STRIP_NOPS (base_in);
+
+ /* Strip off widening conversion(s) to handle cases where
+ e.g. 'B' is widened from an 'int' in order to calculate
+ a 64-bit address. */
+ if (CONVERT_EXPR_P (base_in)
+ && legal_cast_p_1 (base_in, TREE_OPERAND (base_in, 0)))
+ base_in = get_unwidened (base_in, NULL_TREE);
+
+ if (TREE_CODE (base_in) != SSA_NAME)
+ return 0;
+
+ base_cand = base_cand_from_table (base_in);
+
+ while (base_cand && base_cand->kind != CAND_PHI)
+ {
+ if (base_cand->kind == CAND_ADD
+ && base_cand->index == 1
+ && TREE_CODE (base_cand->stride) == INTEGER_CST)
+ {
+ /* X = B + (1 * S), S is integer constant. */
+ *pbase = base_cand->base_expr;
+ return wi::to_widest (base_cand->stride);
+ }
+ else if (base_cand->kind == CAND_ADD
+ && TREE_CODE (base_cand->stride) == INTEGER_CST
+ && integer_onep (base_cand->stride))
+ {
+ /* X = B + (i * S), S is integer one. */
+ *pbase = base_cand->base_expr;
+ return base_cand->index;
+ }
+
+ if (base_cand->next_interp)
+ base_cand = lookup_cand (base_cand->next_interp);
+ else
+ base_cand = NULL;
+ }
+
+ return 0;
+}
+
/* Look for the following pattern:
*PBASE: MEM_REF (T1, C1)
*PBASE: T1
*POFFSET: MULT_EXPR (T2, C3)
- *PINDEX: C1 + (C2 * C3) + C4 */
+ *PINDEX: C1 + (C2 * C3) + C4
+
+ When T2 is recorded by a CAND_ADD in the form of (T2' + C5), it
+ will be further restructured to:
+
+ *PBASE: T1
+ *POFFSET: MULT_EXPR (T2', C3)
+ *PINDEX: C1 + (C2 * C3) + C4 + (C5 * C3) */
static bool
-restructure_reference (tree *pbase, tree *poffset, double_int *pindex,
+restructure_reference (tree *pbase, tree *poffset, widest_int *pindex,
tree *ptype)
{
tree base = *pbase, offset = *poffset;
- double_int index = *pindex;
- double_int bpu = double_int::from_uhwi (BITS_PER_UNIT);
- tree mult_op0, mult_op1, t1, t2, type;
- double_int c1, c2, c3, c4;
+ widest_int index = *pindex;
+ tree mult_op0, t1, t2, type;
+ widest_int c1, c2, c3, c4, c5;
if (!base
|| !offset
|| TREE_CODE (base) != MEM_REF
|| TREE_CODE (offset) != MULT_EXPR
|| TREE_CODE (TREE_OPERAND (offset, 1)) != INTEGER_CST
- || !index.umod (bpu, FLOOR_MOD_EXPR).is_zero ())
+ || wi::umod_floor (index, BITS_PER_UNIT) != 0)
return false;
t1 = TREE_OPERAND (base, 0);
- c1 = mem_ref_offset (base);
+ c1 = widest_int::from (mem_ref_offset (base), SIGNED);
type = TREE_TYPE (TREE_OPERAND (base, 1));
mult_op0 = TREE_OPERAND (offset, 0);
- mult_op1 = TREE_OPERAND (offset, 1);
-
- c3 = tree_to_double_int (mult_op1);
+ c3 = wi::to_widest (TREE_OPERAND (offset, 1));
if (TREE_CODE (mult_op0) == PLUS_EXPR)
if (TREE_CODE (TREE_OPERAND (mult_op0, 1)) == INTEGER_CST)
{
t2 = TREE_OPERAND (mult_op0, 0);
- c2 = tree_to_double_int (TREE_OPERAND (mult_op0, 1));
+ c2 = wi::to_widest (TREE_OPERAND (mult_op0, 1));
}
else
return false;
if (TREE_CODE (TREE_OPERAND (mult_op0, 1)) == INTEGER_CST)
{
t2 = TREE_OPERAND (mult_op0, 0);
- c2 = -tree_to_double_int (TREE_OPERAND (mult_op0, 1));
+ c2 = -wi::to_widest (TREE_OPERAND (mult_op0, 1));
}
else
return false;
else
{
t2 = mult_op0;
- c2 = double_int_zero;
+ c2 = 0;
}
- c4 = index.udiv (bpu, FLOOR_DIV_EXPR);
+ c4 = wi::lrshift (index, LOG2_BITS_PER_UNIT);
+ c5 = backtrace_base_for_ref (&t2);
*pbase = t1;
- *poffset = fold_build2 (MULT_EXPR, sizetype, t2,
- double_int_to_tree (sizetype, c3));
- *pindex = c1 + c2 * c3 + c4;
+ *poffset = fold_build2 (MULT_EXPR, sizetype, fold_convert (sizetype, t2),
+ wide_int_to_tree (sizetype, c3));
+ *pindex = c1 + c2 * c3 + c4 + c5 * c3;
*ptype = type;
return true;
{
tree ref_expr, base, offset, type;
HOST_WIDE_INT bitsize, bitpos;
- enum machine_mode mode;
+ machine_mode mode;
int unsignedp, volatilep;
- double_int index;
slsr_cand_t c;
if (gimple_vdef (gs))
base = get_inner_reference (ref_expr, &bitsize, &bitpos, &offset, &mode,
&unsignedp, &volatilep, false);
- index = double_int::from_uhwi (bitpos);
+ widest_int index = bitpos;
if (!restructure_reference (&base, &offset, &index, &type))
return;
create_mul_ssa_cand (gimple gs, tree base_in, tree stride_in, bool speed)
{
tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE;
- double_int index;
+ widest_int index;
unsigned savings = 0;
slsr_cand_t c;
slsr_cand_t base_cand = base_cand_from_table (base_in);
============================
X = B + ((i' * S) * Z) */
base = base_cand->base_expr;
- index = base_cand->index * tree_to_double_int (base_cand->stride);
+ index = base_cand->index * wi::to_widest (base_cand->stride);
stride = stride_in;
ctype = base_cand->cand_type;
if (has_single_use (base_in))
/* No interpretations had anything useful to propagate, so
produce X = (Y + 0) * Z. */
base = base_in;
- index = double_int_zero;
+ index = 0;
stride = stride_in;
ctype = TREE_TYPE (base_in);
}
create_mul_imm_cand (gimple gs, tree base_in, tree stride_in, bool speed)
{
tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE;
- double_int index, temp;
+ widest_int index, temp;
unsigned savings = 0;
slsr_cand_t c;
slsr_cand_t base_cand = base_cand_from_table (base_in);
X = Y * c
============================
X = (B + i') * (S * c) */
- base = base_cand->base_expr;
- index = base_cand->index;
- temp = tree_to_double_int (base_cand->stride)
- * tree_to_double_int (stride_in);
- stride = double_int_to_tree (TREE_TYPE (stride_in), temp);
- ctype = base_cand->cand_type;
- if (has_single_use (base_in))
- savings = (base_cand->dead_savings
- + stmt_cost (base_cand->cand_stmt, speed));
+ temp = wi::to_widest (base_cand->stride) * wi::to_widest (stride_in);
+ if (wi::fits_to_tree_p (temp, TREE_TYPE (stride_in)))
+ {
+ base = base_cand->base_expr;
+ index = base_cand->index;
+ stride = wide_int_to_tree (TREE_TYPE (stride_in), temp);
+ ctype = base_cand->cand_type;
+ if (has_single_use (base_in))
+ savings = (base_cand->dead_savings
+ + stmt_cost (base_cand->cand_stmt, speed));
+ }
}
else if (base_cand->kind == CAND_ADD && integer_onep (base_cand->stride))
{
+ stmt_cost (base_cand->cand_stmt, speed));
}
else if (base_cand->kind == CAND_ADD
- && base_cand->index.is_one ()
+ && base_cand->index == 1
&& TREE_CODE (base_cand->stride) == INTEGER_CST)
{
/* Y = B + (1 * S), S constant
===========================
X = (B + S) * c */
base = base_cand->base_expr;
- index = tree_to_double_int (base_cand->stride);
+ index = wi::to_widest (base_cand->stride);
stride = stride_in;
ctype = base_cand->cand_type;
if (has_single_use (base_in))
/* No interpretations had anything useful to propagate, so
produce X = (Y + 0) * c. */
base = base_in;
- index = double_int_zero;
+ index = 0;
stride = stride_in;
ctype = TREE_TYPE (base_in);
}
bool subtract_p, bool speed)
{
tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL;
- double_int index;
+ widest_int index;
unsigned savings = 0;
slsr_cand_t c;
slsr_cand_t base_cand = base_cand_from_table (base_in);
while (addend_cand && !base && addend_cand->kind != CAND_PHI)
{
if (addend_cand->kind == CAND_MULT
- && addend_cand->index.is_zero ()
+ && addend_cand->index == 0
&& TREE_CODE (addend_cand->stride) == INTEGER_CST)
{
/* Z = (B + 0) * S, S constant
===========================
X = Y + ((+/-1 * S) * B) */
base = base_in;
- index = tree_to_double_int (addend_cand->stride);
+ index = wi::to_widest (addend_cand->stride);
if (subtract_p)
index = -index;
stride = addend_cand->base_expr;
while (base_cand && !base && base_cand->kind != CAND_PHI)
{
if (base_cand->kind == CAND_ADD
- && (base_cand->index.is_zero ()
+ && (base_cand->index == 0
|| operand_equal_p (base_cand->stride,
integer_zero_node, 0)))
{
============================
X = B + (+/-1 * Z) */
base = base_cand->base_expr;
- index = subtract_p ? double_int_minus_one : double_int_one;
+ index = subtract_p ? -1 : 1;
stride = addend_in;
ctype = base_cand->cand_type;
if (has_single_use (base_in))
while (subtrahend_cand && !base && subtrahend_cand->kind != CAND_PHI)
{
if (subtrahend_cand->kind == CAND_MULT
- && subtrahend_cand->index.is_zero ()
+ && subtrahend_cand->index == 0
&& TREE_CODE (subtrahend_cand->stride) == INTEGER_CST)
{
/* Z = (B + 0) * S, S constant
===========================
Value: X = Y + ((-1 * S) * B) */
base = base_in;
- index = tree_to_double_int (subtrahend_cand->stride);
+ index = wi::to_widest (subtrahend_cand->stride);
index = -index;
stride = subtrahend_cand->base_expr;
ctype = TREE_TYPE (base_in);
/* No interpretations had anything useful to propagate, so
produce X = Y + (1 * Z). */
base = base_in;
- index = subtract_p ? double_int_minus_one : double_int_one;
+ index = subtract_p ? -1 : 1;
stride = addend_in;
ctype = TREE_TYPE (base_in);
}
about BASE_IN into the new candidate. Return the new candidate. */
static slsr_cand_t
-create_add_imm_cand (gimple gs, tree base_in, double_int index_in, bool speed)
+create_add_imm_cand (gimple gs, tree base_in, const widest_int &index_in,
+ bool speed)
{
enum cand_kind kind = CAND_ADD;
tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE;
- double_int index, multiple;
+ widest_int index, multiple;
unsigned savings = 0;
slsr_cand_t c;
slsr_cand_t base_cand = base_cand_from_table (base_in);
while (base_cand && !base && base_cand->kind != CAND_PHI)
{
- bool unsigned_p = TYPE_UNSIGNED (TREE_TYPE (base_cand->stride));
+ signop sign = TYPE_SIGN (TREE_TYPE (base_cand->stride));
if (TREE_CODE (base_cand->stride) == INTEGER_CST
- && index_in.multiple_of (tree_to_double_int (base_cand->stride),
- unsigned_p, &multiple))
+ && wi::multiple_of_p (index_in, wi::to_widest (base_cand->stride),
+ sign, &multiple))
{
/* Y = (B + i') * S, S constant, c = kS for some integer k
X = Y + c
}
else
{
- double_int index;
-
/* Record an interpretation for the add-immediate. */
- index = tree_to_double_int (rhs2);
+ widest_int index = wi::to_widest (rhs2);
if (subtract_p)
index = -index;
rhs_type = TREE_TYPE (rhs);
lhs_size = TYPE_PRECISION (lhs_type);
rhs_size = TYPE_PRECISION (rhs_type);
- lhs_wraps = TYPE_OVERFLOW_WRAPS (lhs_type);
- rhs_wraps = TYPE_OVERFLOW_WRAPS (rhs_type);
+ lhs_wraps = ANY_INTEGRAL_TYPE_P (lhs_type) && TYPE_OVERFLOW_WRAPS (lhs_type);
+ rhs_wraps = ANY_INTEGRAL_TYPE_P (rhs_type) && TYPE_OVERFLOW_WRAPS (rhs_type);
if (lhs_size < rhs_size
|| (rhs_wraps && !lhs_wraps)
The first of these is somewhat arbitrary, but the choice of
1 for the stride simplifies the logic for propagating casts
into their uses. */
- c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1, double_int_zero,
- integer_one_node, ctype, 0);
- c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, double_int_zero,
- integer_one_node, ctype, 0);
+ c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1,
+ 0, integer_one_node, ctype, 0);
+ c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1,
+ 0, integer_one_node, ctype, 0);
c->next_interp = c2->cand_num;
}
The first of these is somewhat arbitrary, but the choice of
1 for the stride simplifies the logic for propagating casts
into their uses. */
- c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1, double_int_zero,
- integer_one_node, TREE_TYPE (rhs1), 0);
- c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, double_int_zero,
- integer_one_node, TREE_TYPE (rhs1), 0);
+ c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1,
+ 0, integer_one_node, TREE_TYPE (rhs1), 0);
+ c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1,
+ 0, integer_one_node, TREE_TYPE (rhs1), 0);
c->next_interp = c2->cand_num;
}
add_cand_for_stmt (gs, c);
}
\f
+class find_candidates_dom_walker : public dom_walker
+{
+public:
+ find_candidates_dom_walker (cdi_direction direction)
+ : dom_walker (direction) {}
+ virtual void before_dom_children (basic_block);
+};
+
/* Find strength-reduction candidates in block BB. */
-static void
-find_candidates_in_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
- basic_block bb)
+void
+find_candidates_dom_walker::before_dom_children (basic_block bb)
{
bool speed = optimize_bb_for_speed_p (bb);
- gimple_stmt_iterator gsi;
- for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
- slsr_process_phi (gsi_stmt (gsi), speed);
+ for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ slsr_process_phi (gsi.phi (), speed);
- for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
+ gsi_next (&gsi))
{
gimple gs = gsi_stmt (gsi);
rhs2 = gimple_assign_rhs2 (gs);
/* Fall-through. */
- case NOP_EXPR:
+ CASE_CONVERT:
case MODIFY_EXPR:
case NEGATE_EXPR:
rhs1 = gimple_assign_rhs1 (gs);
slsr_process_neg (gs, rhs1, speed);
break;
- case NOP_EXPR:
+ CASE_CONVERT:
slsr_process_cast (gs, rhs1, speed);
break;
fputs (" MULT : (", dump_file);
print_generic_expr (dump_file, c->base_expr, 0);
fputs (" + ", dump_file);
- dump_double_int (dump_file, c->index, false);
+ print_decs (c->index, dump_file);
fputs (") * ", dump_file);
print_generic_expr (dump_file, c->stride, 0);
fputs (" : ", dump_file);
fputs (" ADD : ", dump_file);
print_generic_expr (dump_file, c->base_expr, 0);
fputs (" + (", dump_file);
- dump_double_int (dump_file, c->index, false);
+ print_decs (c->index, dump_file);
fputs (" * ", dump_file);
print_generic_expr (dump_file, c->stride, 0);
fputs (") : ", dump_file);
fputs (" + (", dump_file);
print_generic_expr (dump_file, c->stride, 0);
fputs (") + ", dump_file);
- dump_double_int (dump_file, c->index, false);
+ print_decs (c->index, dump_file);
fputs (" : ", dump_file);
break;
case CAND_PHI:
dump_cand_chains (void)
{
fprintf (dump_file, "\nStrength reduction candidate chains:\n\n");
- base_cand_map.traverse_noresize <void *, ssa_base_cand_dump_callback> (NULL);
+ base_cand_map->traverse_noresize <void *, ssa_base_cand_dump_callback>
+ (NULL);
fputs ("\n", dump_file);
}
for (i = 0; i < incr_vec_len; i++)
{
fprintf (dump_file, "%3d increment: ", i);
- dump_double_int (dump_file, incr_vec[i].incr, false);
+ print_decs (incr_vec[i].incr, dump_file);
fprintf (dump_file, "\n count: %d", incr_vec[i].count);
fprintf (dump_file, "\n cost: %d", incr_vec[i].cost);
fputs ("\n initializer: ", dump_file);
static void
replace_ref (tree *expr, slsr_cand_t c)
{
- tree add_expr = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (c->base_expr),
- c->base_expr, c->stride);
- tree mem_ref = fold_build2 (MEM_REF, TREE_TYPE (*expr), add_expr,
- double_int_to_tree (c->cand_type, c->index));
-
+ tree add_expr, mem_ref, acc_type = TREE_TYPE (*expr);
+ unsigned HOST_WIDE_INT misalign;
+ unsigned align;
+
+ /* Ensure the memory reference carries the minimum alignment
+ requirement for the data type. See PR58041. */
+ get_object_alignment_1 (*expr, &align, &misalign);
+ if (misalign != 0)
+ align = (misalign & -misalign);
+ if (align < TYPE_ALIGN (acc_type))
+ acc_type = build_aligned_type (acc_type, align);
+
+ add_expr = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (c->base_expr),
+ c->base_expr, c->stride);
+ mem_ref = fold_build2 (MEM_REF, acc_type, add_expr,
+ wide_int_to_tree (c->cand_type, c->index));
+
/* Gimplify the base addressing expression for the new MEM_REF tree. */
gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
TREE_OPERAND (mem_ref, 0)
static void
replace_refs (slsr_cand_t c)
{
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fputs ("Replacing reference: ", dump_file);
+ print_gimple_stmt (dump_file, c->cand_stmt, 0, 0);
+ }
+
if (gimple_vdef (c->cand_stmt))
{
tree *lhs = gimple_assign_lhs_ptr (c->cand_stmt);
replace_ref (rhs, c);
}
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fputs ("With: ", dump_file);
+ print_gimple_stmt (dump_file, c->cand_stmt, 0, 0);
+ fputs ("\n", dump_file);
+ }
+
if (c->sibling)
replace_refs (lookup_cand (c->sibling));
/* Calculate the increment required for candidate C relative to
its basis. */
-static double_int
+static widest_int
cand_increment (slsr_cand_t c)
{
slsr_cand_t basis;
for this candidate, return the absolute value of that increment
instead. */
-static inline double_int
+static inline widest_int
cand_abs_increment (slsr_cand_t c)
{
- double_int increment = cand_increment (c);
+ widest_int increment = cand_increment (c);
- if (!address_arithmetic_p && increment.is_negative ())
+ if (!address_arithmetic_p && wi::neg_p (increment))
increment = -increment;
return increment;
replace_conditional_candidate. */
static void
-replace_mult_candidate (slsr_cand_t c, tree basis_name, double_int bump)
+replace_mult_candidate (slsr_cand_t c, tree basis_name, widest_int bump)
{
tree target_type = TREE_TYPE (gimple_assign_lhs (c->cand_stmt));
enum tree_code cand_code = gimple_assign_rhs_code (c->cand_stmt);
in this case. This does not affect siblings or dependents
of C. Restriction to signed HWI is conservative for unsigned
types but allows for safe negation without twisted logic. */
- if (bump.fits_shwi ()
+ if (wi::fits_shwi_p (bump)
&& bump.to_shwi () != HOST_WIDE_INT_MIN
/* It is not useful to replace casts, copies, or adds of
an SSA name and a constant. */
&& cand_code != MODIFY_EXPR
- && cand_code != NOP_EXPR
+ && !CONVERT_EXPR_CODE_P (cand_code)
&& cand_code != PLUS_EXPR
&& cand_code != POINTER_PLUS_EXPR
&& cand_code != MINUS_EXPR)
types, introduce a cast. */
if (!useless_type_conversion_p (target_type, TREE_TYPE (basis_name)))
basis_name = introduce_cast_before_cand (c, target_type, basis_name);
- if (bump.is_negative ())
+ if (wi::neg_p (bump))
{
code = MINUS_EXPR;
bump = -bump;
}
- bump_tree = double_int_to_tree (target_type, bump);
+ bump_tree = wide_int_to_tree (target_type, bump);
if (dump_file && (dump_flags & TDF_DETAILS))
{
print_gimple_stmt (dump_file, c->cand_stmt, 0, 0);
}
- if (bump.is_zero ())
+ if (bump == 0)
{
tree lhs = gimple_assign_lhs (c->cand_stmt);
- gimple copy_stmt = gimple_build_assign (lhs, basis_name);
+ gassign *copy_stmt = gimple_build_assign (lhs, basis_name);
gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
gimple_set_location (copy_stmt, gimple_location (c->cand_stmt));
gsi_replace (&gsi, copy_stmt, false);
+ c->cand_stmt = copy_stmt;
if (dump_file && (dump_flags & TDF_DETAILS))
stmt_to_print = copy_stmt;
}
gimple_assign_set_rhs_with_ops (&gsi, code,
basis_name, bump_tree);
update_stmt (gsi_stmt (gsi));
+ c->cand_stmt = gsi_stmt (gsi);
if (dump_file && (dump_flags & TDF_DETAILS))
stmt_to_print = gsi_stmt (gsi);
}
replace_unconditional_candidate (slsr_cand_t c)
{
slsr_cand_t basis;
- double_int stride, bump;
if (cand_already_replaced (c))
return;
basis = lookup_cand (c->basis);
- stride = tree_to_double_int (c->stride);
- bump = cand_increment (c) * stride;
+ widest_int bump = cand_increment (c) * wi::to_widest (c->stride);
replace_mult_candidate (c, gimple_assign_lhs (basis->cand_stmt), bump);
}
MAX_INCR_VEC_LEN increments have been found. */
static inline int
-incr_vec_index (double_int increment)
+incr_vec_index (const widest_int &increment)
{
unsigned i;
static tree
create_add_on_incoming_edge (slsr_cand_t c, tree basis_name,
- double_int increment, edge e, location_t loc,
+ widest_int increment, edge e, location_t loc,
bool known_stride)
{
basic_block insert_bb;
gimple_stmt_iterator gsi;
tree lhs, basis_type;
- gimple new_stmt;
+ gassign *new_stmt;
/* If the add candidate along this incoming edge has the same
index as C's hidden basis, the hidden basis represents this
edge correctly. */
- if (increment.is_zero ())
+ if (increment == 0)
return basis_name;
basis_type = TREE_TYPE (basis_name);
{
tree bump_tree;
enum tree_code code = PLUS_EXPR;
- double_int bump = increment * tree_to_double_int (c->stride);
- if (bump.is_negative ())
+ widest_int bump = increment * wi::to_widest (c->stride);
+ if (wi::neg_p (bump))
{
code = MINUS_EXPR;
bump = -bump;
}
- bump_tree = double_int_to_tree (basis_type, bump);
- new_stmt = gimple_build_assign_with_ops (code, lhs, basis_name,
- bump_tree);
+ bump_tree = wide_int_to_tree (basis_type, bump);
+ new_stmt = gimple_build_assign (lhs, code, basis_name, bump_tree);
}
else
{
int i;
- bool negate_incr = (!address_arithmetic_p && increment.is_negative ());
+ bool negate_incr = (!address_arithmetic_p && wi::neg_p (increment));
i = incr_vec_index (negate_incr ? -increment : increment);
gcc_assert (i >= 0);
if (incr_vec[i].initializer)
{
enum tree_code code = negate_incr ? MINUS_EXPR : PLUS_EXPR;
- new_stmt = gimple_build_assign_with_ops (code, lhs, basis_name,
- incr_vec[i].initializer);
+ new_stmt = gimple_build_assign (lhs, code, basis_name,
+ incr_vec[i].initializer);
}
- else if (increment.is_one ())
- new_stmt = gimple_build_assign_with_ops (PLUS_EXPR, lhs, basis_name,
- c->stride);
- else if (increment.is_minus_one ())
- new_stmt = gimple_build_assign_with_ops (MINUS_EXPR, lhs, basis_name,
- c->stride);
+ else if (increment == 1)
+ new_stmt = gimple_build_assign (lhs, PLUS_EXPR, basis_name, c->stride);
+ else if (increment == -1)
+ new_stmt = gimple_build_assign (lhs, MINUS_EXPR, basis_name,
+ c->stride);
else
gcc_unreachable ();
}
{
int i;
tree name, phi_arg;
- gimple phi;
+ gphi *phi;
vec<tree> phi_args;
slsr_cand_t basis = lookup_cand (c->basis);
int nargs = gimple_phi_num_args (from_phi);
/* If the phi argument is the base name of the CAND_PHI, then
this incoming arc should use the hidden basis. */
if (operand_equal_p (arg, phi_cand->base_expr, 0))
- if (basis->index.is_zero ())
+ if (basis->index == 0)
feeding_def = gimple_assign_lhs (basis->cand_stmt);
else
{
- double_int incr = -basis->index;
+ widest_int incr = -basis->index;
feeding_def = create_add_on_incoming_edge (c, basis_name, incr,
e, loc, known_stride);
}
else
{
slsr_cand_t arg_cand = base_cand_from_table (arg);
- double_int diff = arg_cand->index - basis->index;
+ widest_int diff = arg_cand->index - basis->index;
feeding_def = create_add_on_incoming_edge (c, basis_name, diff,
e, loc, known_stride);
}
tree basis_name, name;
slsr_cand_t basis;
location_t loc;
- double_int stride, bump;
/* Look up the LHS SSA name from C's basis. This will be the
RHS1 of the adds we will introduce to create new phi arguments. */
name = create_phi_basis (c, lookup_cand (c->def_phi)->cand_stmt,
basis_name, loc, KNOWN_STRIDE);
/* Replace C with an add of the new basis phi and a constant. */
- stride = tree_to_double_int (c->stride);
- bump = c->index * stride;
+ widest_int bump = c->index * wi::to_widest (c->stride);
replace_mult_candidate (c, name, bump);
}
int cost = 0;
slsr_cand_t phi_cand = base_cand_from_table (gimple_phi_result (phi));
+ /* If we work our way back to a phi that isn't dominated by the hidden
+ basis, this isn't a candidate for replacement. Indicate this by
+ returning an unreasonably high cost. It's not easy to detect
+ these situations when determining the basis, so we defer the
+ decision until now. */
+ basic_block phi_bb = gimple_bb (phi);
+ slsr_cand_t basis = lookup_cand (c->basis);
+ basic_block basis_bb = gimple_bb (basis->cand_stmt);
+
+ if (phi_bb == basis_bb || !dominated_by_p (CDI_DOMINATORS, phi_bb, basis_bb))
+ return COST_INFINITE;
+
for (i = 0; i < gimple_phi_num_args (phi); i++)
{
tree arg = gimple_phi_arg_def (phi, i);
/* Count the number of candidates in the tree rooted at C that have
not already been replaced under other interpretations. */
-static unsigned
+static int
count_candidates (slsr_cand_t c)
{
unsigned count = cand_already_replaced (c) ? 0 : 1;
candidates with the same increment, also record T_0 for subsequent use. */
static void
-record_increment (slsr_cand_t c, double_int increment, bool is_phi_adjust)
+record_increment (slsr_cand_t c, widest_int increment, bool is_phi_adjust)
{
bool found = false;
unsigned i;
/* Treat increments that differ only in sign as identical so as to
share initializers, unless we are generating pointer arithmetic. */
- if (!address_arithmetic_p && increment.is_negative ())
+ if (!address_arithmetic_p && wi::neg_p (increment))
increment = -increment;
for (i = 0; i < incr_vec_len; i++)
if (c->kind == CAND_ADD
&& !is_phi_adjust
&& c->index == increment
- && (increment.sgt (double_int_one)
- || increment.slt (double_int_minus_one))
+ && (wi::gts_p (increment, 1)
+ || wi::lts_p (increment, -1))
&& (gimple_assign_rhs_code (c->cand_stmt) == PLUS_EXPR
|| gimple_assign_rhs_code (c->cand_stmt) == POINTER_PLUS_EXPR))
{
else
{
slsr_cand_t arg_cand = base_cand_from_table (arg);
- double_int diff = arg_cand->index - basis->index;
+ widest_int diff = arg_cand->index - basis->index;
record_increment (arg_cand, diff, PHI_ADJUST);
}
}
uses. */
static int
-phi_incr_cost (slsr_cand_t c, double_int incr, gimple phi, int *savings)
+phi_incr_cost (slsr_cand_t c, const widest_int &incr, gimple phi, int *savings)
{
unsigned i;
int cost = 0;
else
{
slsr_cand_t arg_cand = base_cand_from_table (arg);
- double_int diff = arg_cand->index - basis->index;
+ widest_int diff = arg_cand->index - basis->index;
if (incr == diff)
{
static int
lowest_cost_path (int cost_in, int repl_savings, slsr_cand_t c,
- double_int incr, bool count_phis)
+ const widest_int &incr, bool count_phis)
{
int local_cost, sib_cost, savings = 0;
- double_int cand_incr = cand_abs_increment (c);
+ widest_int cand_incr = cand_abs_increment (c);
if (cand_already_replaced (c))
local_cost = cost_in;
would go dead. */
static int
-total_savings (int repl_savings, slsr_cand_t c, double_int incr,
+total_savings (int repl_savings, slsr_cand_t c, const widest_int &incr,
bool count_phis)
{
int savings = 0;
- double_int cand_incr = cand_abs_increment (c);
+ widest_int cand_incr = cand_abs_increment (c);
if (incr == cand_incr && !cand_already_replaced (c))
savings += repl_savings + c->dead_savings;
up sometime. */
static void
-analyze_increments (slsr_cand_t first_dep, enum machine_mode mode, bool speed)
+analyze_increments (slsr_cand_t first_dep, machine_mode mode, bool speed)
{
unsigned i;
/* If somehow this increment is bigger than a HWI, we won't
be optimizing candidates that use it. And if the increment
has a count of zero, nothing will be done with it. */
- if (!incr_vec[i].incr.fits_shwi () || !incr_vec[i].count)
+ if (!wi::fits_shwi_p (incr_vec[i].incr) || !incr_vec[i].count)
incr_vec[i].cost = COST_INFINITE;
/* Increments of 0, 1, and -1 are always profitable to replace,
candidates, return the earliest candidate in the block in *WHERE. */
static basic_block
-ncd_with_phi (slsr_cand_t c, double_int incr, gimple phi,
+ncd_with_phi (slsr_cand_t c, const widest_int &incr, gphi *phi,
basic_block ncd, slsr_cand_t *where)
{
unsigned i;
gimple arg_def = SSA_NAME_DEF_STMT (arg);
if (gimple_code (arg_def) == GIMPLE_PHI)
- ncd = ncd_with_phi (c, incr, arg_def, ncd, where);
+ ncd = ncd_with_phi (c, incr, as_a <gphi *> (arg_def), ncd,
+ where);
else
{
slsr_cand_t arg_cand = base_cand_from_table (arg);
- double_int diff = arg_cand->index - basis->index;
+ 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, gimple_bb (arg_cand->cand_stmt),
- *where, arg_cand, where);
+ ncd = ncd_for_two_cands (ncd, pred, *where, NULL, where);
}
}
}
return the earliest candidate in the block in *WHERE. */
static basic_block
-ncd_of_cand_and_phis (slsr_cand_t c, double_int incr, slsr_cand_t *where)
+ncd_of_cand_and_phis (slsr_cand_t c, const widest_int &incr, slsr_cand_t *where)
{
basic_block ncd = NULL;
}
if (phi_dependent_cand_p (c))
- ncd = ncd_with_phi (c, incr, lookup_cand (c->def_phi)->cand_stmt,
+ ncd = ncd_with_phi (c, incr,
+ as_a <gphi *> (lookup_cand (c->def_phi)->cand_stmt),
ncd, where);
return ncd;
*WHERE. */
static basic_block
-nearest_common_dominator_for_cands (slsr_cand_t c, double_int incr,
+nearest_common_dominator_for_cands (slsr_cand_t c, const widest_int &incr,
slsr_cand_t *where)
{
basic_block sib_ncd = NULL, dep_ncd = NULL, this_ncd = NULL, ncd;
{
basic_block bb;
slsr_cand_t where = NULL;
- gimple init_stmt;
+ gassign *init_stmt;
tree stride_type, new_name, incr_tree;
- double_int incr = incr_vec[i].incr;
+ widest_int incr = incr_vec[i].incr;
if (!profitable_increment_p (i)
- || incr.is_one ()
- || (incr.is_minus_one ()
+ || incr == 1
+ || (incr == -1
&& gimple_assign_rhs_code (c->cand_stmt) != POINTER_PLUS_EXPR)
- || incr.is_zero ())
+ || incr == 0)
continue;
/* We may have already identified an existing initializer that
/* Create the initializer and insert it in the latest possible
dominating position. */
- incr_tree = double_int_to_tree (stride_type, incr);
- init_stmt = gimple_build_assign_with_ops (MULT_EXPR, new_name,
- c->stride, incr_tree);
+ incr_tree = wide_int_to_tree (stride_type, incr);
+ init_stmt = gimple_build_assign (new_name, MULT_EXPR,
+ c->stride, incr_tree);
if (where)
{
gimple_stmt_iterator gsi = gsi_for_stmt (where->cand_stmt);
{
int j;
slsr_cand_t arg_cand = base_cand_from_table (arg);
- double_int increment = arg_cand->index - basis->index;
+ widest_int increment = arg_cand->index - basis->index;
- if (!address_arithmetic_p && increment.is_negative ())
+ if (!address_arithmetic_p && wi::neg_p (increment))
increment = -increment;
j = incr_vec_index (increment);
c->cand_num);
print_gimple_stmt (dump_file, phi, 0, 0);
fputs (" increment: ", dump_file);
- dump_double_int (dump_file, increment, false);
+ print_decs (increment, dump_file);
if (j < 0)
fprintf (dump_file,
"\n Not replaced; incr_vec overflow.\n");
introduce_cast_before_cand (slsr_cand_t c, tree to_type, tree from_expr)
{
tree cast_lhs;
- gimple cast_stmt;
+ gassign *cast_stmt;
gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
cast_lhs = make_temp_ssa_name (to_type, NULL, "slsr");
- cast_stmt = gimple_build_assign_with_ops (NOP_EXPR, cast_lhs,
- from_expr, NULL_TREE);
+ cast_stmt = gimple_build_assign (cast_lhs, NOP_EXPR, from_expr);
gimple_set_location (cast_stmt, gimple_location (c->cand_stmt));
gsi_insert_before (&gsi, cast_stmt, GSI_SAME_STMT);
gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
gimple_assign_set_rhs_with_ops (&gsi, new_code, new_rhs1, new_rhs2);
update_stmt (gsi_stmt (gsi));
+ c->cand_stmt = gsi_stmt (gsi);
if (dump_file && (dump_flags & TDF_DETAILS))
return gsi_stmt (gsi);
tree orig_rhs1, orig_rhs2;
tree rhs2;
enum tree_code orig_code, repl_code;
- double_int cand_incr;
+ widest_int cand_incr;
orig_code = gimple_assign_rhs_code (c->cand_stmt);
orig_rhs1 = gimple_assign_rhs1 (c->cand_stmt);
from the basis name, or an add of the stride to the basis
name, respectively. It may be necessary to introduce a
cast (or reuse an existing cast). */
- else if (cand_incr.is_one ())
+ else if (cand_incr == 1)
{
tree stride_type = TREE_TYPE (c->stride);
tree orig_type = TREE_TYPE (orig_rhs2);
c);
}
- else if (cand_incr.is_minus_one ())
+ else if (cand_incr == -1)
{
tree stride_type = TREE_TYPE (c->stride);
tree orig_type = TREE_TYPE (orig_rhs2);
gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, basis_name, rhs2);
update_stmt (gsi_stmt (gsi));
+ c->cand_stmt = gsi_stmt (gsi);
if (dump_file && (dump_flags & TDF_DETAILS))
stmt_to_print = gsi_stmt (gsi);
fputs (" (duplicate, not actually replacing)\n", dump_file);
}
- else if (cand_incr.is_zero ())
+ else if (cand_incr == 0)
{
tree lhs = gimple_assign_lhs (c->cand_stmt);
tree lhs_type = TREE_TYPE (lhs);
if (types_compatible_p (lhs_type, basis_type))
{
- gimple copy_stmt = gimple_build_assign (lhs, basis_name);
+ gassign *copy_stmt = gimple_build_assign (lhs, basis_name);
gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
gimple_set_location (copy_stmt, gimple_location (c->cand_stmt));
gsi_replace (&gsi, copy_stmt, false);
+ c->cand_stmt = copy_stmt;
if (dump_file && (dump_flags & TDF_DETAILS))
stmt_to_print = copy_stmt;
else
{
gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
- gimple cast_stmt = gimple_build_assign_with_ops (NOP_EXPR, lhs,
- basis_name,
- NULL_TREE);
+ gassign *cast_stmt = gimple_build_assign (lhs, NOP_EXPR, basis_name);
gimple_set_location (cast_stmt, gimple_location (c->cand_stmt));
gsi_replace (&gsi, cast_stmt, false);
+ c->cand_stmt = cast_stmt;
if (dump_file && (dump_flags & TDF_DETAILS))
stmt_to_print = cast_stmt;
{
if (!cand_already_replaced (c))
{
- double_int increment = cand_abs_increment (c);
+ widest_int increment = cand_abs_increment (c);
enum tree_code orig_code = gimple_assign_rhs_code (c->cand_stmt);
int i;
if (i >= 0
&& profitable_increment_p (i)
&& orig_code != MODIFY_EXPR
- && orig_code != NOP_EXPR)
+ && !CONVERT_EXPR_CODE_P (orig_code))
{
if (phi_dependent_cand_p (c))
{
less expensive to calculate than the replaced statements. */
else
{
- unsigned length;
- enum machine_mode mode;
+ machine_mode mode;
bool speed;
/* Determine whether we'll be generating pointer arithmetic
/* If all candidates have already been replaced under other
interpretations, nothing remains to be done. */
- length = count_candidates (c);
- if (!length)
+ if (!count_candidates (c))
continue;
- if (length > MAX_INCR_VEC_LEN)
- length = MAX_INCR_VEC_LEN;
/* Construct an array of increments for this candidate chain. */
- incr_vec = XNEWVEC (incr_info, length);
+ incr_vec = XNEWVEC (incr_info, MAX_INCR_VEC_LEN);
incr_vec_len = 0;
record_increments (c);
}
}
-static unsigned
-execute_strength_reduction (void)
+namespace {
+
+const pass_data pass_data_strength_reduction =
+{
+ GIMPLE_PASS, /* type */
+ "slsr", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_GIMPLE_SLSR, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0, /* todo_flags_finish */
+};
+
+class pass_strength_reduction : public gimple_opt_pass
{
- struct dom_walk_data walk_data;
+public:
+ pass_strength_reduction (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_strength_reduction, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ virtual bool gate (function *) { return flag_tree_slsr; }
+ virtual unsigned int execute (function *);
+
+}; // class pass_strength_reduction
+unsigned
+pass_strength_reduction::execute (function *fun)
+{
/* Create the obstack where candidates will reside. */
gcc_obstack_init (&cand_obstack);
cand_vec.create (128);
/* Allocate the mapping from statements to candidate indices. */
- stmt_cand_map = pointer_map_create ();
+ stmt_cand_map = new hash_map<gimple, slsr_cand_t>;
/* Create the obstack where candidate chains will reside. */
gcc_obstack_init (&chain_obstack);
/* Allocate the mapping from base expressions to candidate chains. */
- base_cand_map.create (500);
+ base_cand_map = new hash_table<cand_chain_hasher> (500);
+
+ /* Allocate the mapping from bases to alternative bases. */
+ alt_base_map = new hash_map<tree, tree>;
/* Initialize the loop optimizer. We need to detect flow across
back edges, and this gives us dominator information as well. */
loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
- /* Set up callbacks for the generic dominator tree walker. */
- walk_data.dom_direction = CDI_DOMINATORS;
- walk_data.initialize_block_local_data = NULL;
- walk_data.before_dom_children = find_candidates_in_block;
- walk_data.after_dom_children = NULL;
- walk_data.global_data = NULL;
- walk_data.block_local_data_size = 0;
- init_walk_dominator_tree (&walk_data);
-
/* Walk the CFG in predominator order looking for strength reduction
candidates. */
- walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
+ find_candidates_dom_walker (CDI_DOMINATORS)
+ .walk (fun->cfg->x_entry_block_ptr);
if (dump_file && (dump_flags & TDF_DETAILS))
{
dump_cand_chains ();
}
+ delete alt_base_map;
+ free_affine_expand_cache (&name_expansions);
+
/* Analyze costs and make appropriate replacements. */
analyze_candidates_and_replace ();
- /* Free resources. */
- fini_walk_dominator_tree (&walk_data);
loop_optimizer_finalize ();
- base_cand_map.dispose ();
+ delete base_cand_map;
+ base_cand_map = NULL;
obstack_free (&chain_obstack, NULL);
- pointer_map_destroy (stmt_cand_map);
+ delete stmt_cand_map;
cand_vec.release ();
obstack_free (&cand_obstack, NULL);
return 0;
}
-static bool
-gate_strength_reduction (void)
-{
- return flag_tree_slsr;
-}
-
-struct gimple_opt_pass pass_strength_reduction =
-{
- {
- GIMPLE_PASS,
- "slsr", /* name */
- OPTGROUP_NONE, /* optinfo_flags */
- gate_strength_reduction, /* gate */
- execute_strength_reduction, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_GIMPLE_SLSR, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_verify_ssa /* todo_flags_finish */
- }
-};
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_strength_reduction (gcc::context *ctxt)
+{
+ return new pass_strength_reduction (ctxt);
+}
projects / gcc.git / blobdiff