/* Global, SSA-based optimizations using mathematical identities.
- Copyright (C) 2005-2014 Free Software Foundation, Inc.
+ Copyright (C) 2005-2015 Free Software Foundation, Inc.
This file is part of GCC.
#include "coretypes.h"
#include "tm.h"
#include "flags.h"
+#include "alias.h"
+#include "symtab.h"
#include "tree.h"
+#include "fold-const.h"
+#include "predict.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-fold.h"
#include "gimple-expr.h"
-#include "is-a.h"
#include "gimple.h"
#include "gimple-iterator.h"
#include "gimplify.h"
#include "ssa-iterators.h"
#include "stringpool.h"
#include "tree-ssanames.h"
+#include "rtl.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-dfa.h"
#include "tree-ssa.h"
#include "target.h"
#include "gimple-pretty-print.h"
#include "builtins.h"
+#include "params.h"
/* FIXME: RTL headers have to be included here for optabs. */
#include "rtl.h" /* Because optabs.h wants enum rtx_code. */
#include "expr.h" /* Because optabs.h wants sepops. */
+#include "insn-codes.h"
#include "optabs.h"
/* This structure represents one basic block that either computes a
static struct occurrence *occ_head;
/* Allocation pool for getting instances of "struct occurrence". */
-static alloc_pool occ_pool;
+static pool_allocator<occurrence> *occ_pool;
{
struct occurrence *occ;
- bb->aux = occ = (struct occurrence *) pool_alloc (occ_pool);
+ bb->aux = occ = occ_pool->allocate ();
memset (occ, 0, sizeof (struct occurrence));
occ->bb = bb;
tree def, tree recip_def, int threshold)
{
tree type;
- gimple new_stmt;
+ gassign *new_stmt;
gimple_stmt_iterator gsi;
struct occurrence *occ_child;
/* Make a variable with the replacement and substitute it. */
type = TREE_TYPE (def);
recip_def = create_tmp_reg (type, "reciptmp");
- new_stmt = gimple_build_assign_with_ops (RDIV_EXPR, recip_def,
- build_one_cst (type), def);
+ new_stmt = gimple_build_assign (recip_def, RDIV_EXPR,
+ build_one_cst (type), def);
if (occ->bb_has_division)
{
next = occ->next;
child = occ->children;
occ->bb->aux = NULL;
- pool_free (occ_pool, occ);
+ occ_pool->remove (occ);
/* Now ensure that we don't recurse unless it is necessary. */
if (!child)
GIMPLE_PASS, /* type */
"recip", /* name */
OPTGROUP_NONE, /* optinfo_flags */
- true, /* has_execute */
TV_NONE, /* tv_id */
PROP_ssa, /* properties_required */
0, /* properties_provided */
basic_block bb;
tree arg;
- occ_pool = create_alloc_pool ("dominators for recip",
- sizeof (struct occurrence),
- n_basic_blocks_for_fn (fun) / 3 + 1);
+ occ_pool = new pool_allocator<occurrence>
+ ("dominators for recip", n_basic_blocks_for_fn (fun) / 3 + 1);
memset (&reciprocal_stats, 0, sizeof (reciprocal_stats));
calculate_dominance_info (CDI_DOMINATORS);
FOR_EACH_BB_FN (bb, fun)
{
- gimple_stmt_iterator gsi;
- gimple phi;
tree def;
- for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
+ gsi_next (&gsi))
{
- phi = gsi_stmt (gsi);
+ gphi *phi = gsi.phi ();
def = PHI_RESULT (phi);
if (! virtual_operand_p (def)
&& FLOAT_TYPE_P (TREE_TYPE (def)))
execute_cse_reciprocals_1 (NULL, def);
}
- for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ for (gimple_stmt_iterator gsi = gsi_after_labels (bb); !gsi_end_p (gsi);
+ gsi_next (&gsi))
{
gimple stmt = gsi_stmt (gsi);
continue;
/* Scan for a/func(b) and convert it to reciprocal a*rfunc(b). */
- for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ for (gimple_stmt_iterator gsi = gsi_after_labels (bb); !gsi_end_p (gsi);
+ gsi_next (&gsi))
{
gimple stmt = gsi_stmt (gsi);
tree fndecl;
free_dominance_info (CDI_DOMINATORS);
free_dominance_info (CDI_POST_DOMINATORS);
- free_alloc_pool (occ_pool);
+ delete occ_pool;
return 0;
}
tree fndecl, res, type;
gimple def_stmt, use_stmt, stmt;
int seen_cos = 0, seen_sin = 0, seen_cexpi = 0;
- vec<gimple> stmts = vNULL;
+ auto_vec<gimple> stmts;
basic_block top_bb = NULL;
int i;
bool cfg_changed = false;
}
if (seen_cos + seen_sin + seen_cexpi <= 1)
- {
- stmts.release ();
- return false;
- }
+ return false;
/* Simply insert cexpi at the beginning of top_bb but not earlier than
the name def statement. */
cfg_changed = true;
}
- stmts.release ();
-
return cfg_changed;
}
{
tree op0, op1, ssa_target;
unsigned HOST_WIDE_INT digit;
- gimple mult_stmt;
+ gassign *mult_stmt;
if (n < POWI_TABLE_SIZE && cache[n])
return cache[n];
op1 = op0;
}
- mult_stmt = gimple_build_assign_with_ops (MULT_EXPR, ssa_target, op0, op1);
+ mult_stmt = gimple_build_assign (ssa_target, MULT_EXPR, op0, op1);
gimple_set_location (mult_stmt, loc);
gsi_insert_before (gsi, mult_stmt, GSI_SAME_STMT);
tree arg0, HOST_WIDE_INT n)
{
tree cache[POWI_TABLE_SIZE], result, type = TREE_TYPE (arg0);
- gimple div_stmt;
+ gassign *div_stmt;
tree target;
if (n == 0)
/* If the original exponent was negative, reciprocate the result. */
target = make_temp_ssa_name (type, NULL, "powmult");
- div_stmt = gimple_build_assign_with_ops (RDIV_EXPR, target,
- build_real (type, dconst1),
- result);
+ div_stmt = gimple_build_assign (target, RDIV_EXPR,
+ build_real (type, dconst1), result);
gimple_set_location (div_stmt, loc);
gsi_insert_before (gsi, div_stmt, GSI_SAME_STMT);
build_and_insert_call (gimple_stmt_iterator *gsi, location_t loc,
tree fn, tree arg)
{
- gimple call_stmt;
+ gcall *call_stmt;
tree ssa_target;
call_stmt = gimple_build_call (fn, 1, arg);
tree arg0, tree arg1)
{
tree result = make_temp_ssa_name (TREE_TYPE (arg0), NULL, name);
- gimple stmt = gimple_build_assign_with_ops (code, result, arg0, arg1);
+ gassign *stmt = gimple_build_assign (result, code, arg0, arg1);
gimple_set_location (stmt, loc);
gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
return result;
build_and_insert_cast (gimple_stmt_iterator *gsi, location_t loc,
tree type, tree val)
{
- tree result = make_ssa_name (type, NULL);
- gimple stmt = gimple_build_assign_with_ops (NOP_EXPR, result, val, NULL_TREE);
+ tree result = make_ssa_name (type);
+ gassign *stmt = gimple_build_assign (result, NOP_EXPR, val);
gimple_set_location (stmt, loc);
gsi_insert_before (gsi, stmt, GSI_SAME_STMT);
return result;
}
+struct pow_synth_sqrt_info
+{
+ bool *factors;
+ unsigned int deepest;
+ unsigned int num_mults;
+};
+
+/* Return true iff the real value C can be represented as a
+ sum of powers of 0.5 up to N. That is:
+ C == SUM<i from 1..N> (a[i]*(0.5**i)) where a[i] is either 0 or 1.
+ Record in INFO the various parameters of the synthesis algorithm such
+ as the factors a[i], the maximum 0.5 power and the number of
+ multiplications that will be required. */
+
+bool
+representable_as_half_series_p (REAL_VALUE_TYPE c, unsigned n,
+ struct pow_synth_sqrt_info *info)
+{
+ REAL_VALUE_TYPE factor = dconsthalf;
+ REAL_VALUE_TYPE remainder = c;
+
+ info->deepest = 0;
+ info->num_mults = 0;
+ memset (info->factors, 0, n * sizeof (bool));
+
+ for (unsigned i = 0; i < n; i++)
+ {
+ REAL_VALUE_TYPE res;
+
+ /* If something inexact happened bail out now. */
+ if (REAL_ARITHMETIC (res, MINUS_EXPR, remainder, factor))
+ return false;
+
+ /* We have hit zero. The number is representable as a sum
+ of powers of 0.5. */
+ if (REAL_VALUES_EQUAL (res, dconst0))
+ {
+ info->factors[i] = true;
+ info->deepest = i + 1;
+ return true;
+ }
+ else if (!REAL_VALUE_NEGATIVE (res))
+ {
+ remainder = res;
+ info->factors[i] = true;
+ info->num_mults++;
+ }
+ else
+ info->factors[i] = false;
+
+ REAL_ARITHMETIC (factor, MULT_EXPR, factor, dconsthalf);
+ }
+ return false;
+}
+
+/* Return the tree corresponding to FN being applied
+ to ARG N times at GSI and LOC.
+ Look up previous results from CACHE if need be.
+ cache[0] should contain just plain ARG i.e. FN applied to ARG 0 times. */
+
+static tree
+get_fn_chain (tree arg, unsigned int n, gimple_stmt_iterator *gsi,
+ tree fn, location_t loc, tree *cache)
+{
+ tree res = cache[n];
+ if (!res)
+ {
+ tree prev = get_fn_chain (arg, n - 1, gsi, fn, loc, cache);
+ res = build_and_insert_call (gsi, loc, fn, prev);
+ cache[n] = res;
+ }
+
+ return res;
+}
+
+/* Print to STREAM the repeated application of function FNAME to ARG
+ N times. So, for FNAME = "foo", ARG = "x", N = 2 it would print:
+ "foo (foo (x))". */
+
+static void
+print_nested_fn (FILE* stream, const char *fname, const char* arg,
+ unsigned int n)
+{
+ if (n == 0)
+ fprintf (stream, "%s", arg);
+ else
+ {
+ fprintf (stream, "%s (", fname);
+ print_nested_fn (stream, fname, arg, n - 1);
+ fprintf (stream, ")");
+ }
+}
+
+/* Print to STREAM the fractional sequence of sqrt chains
+ applied to ARG, described by INFO. Used for the dump file. */
+
+static void
+dump_fractional_sqrt_sequence (FILE *stream, const char *arg,
+ struct pow_synth_sqrt_info *info)
+{
+ for (unsigned int i = 0; i < info->deepest; i++)
+ {
+ bool is_set = info->factors[i];
+ if (is_set)
+ {
+ print_nested_fn (stream, "sqrt", arg, i + 1);
+ if (i != info->deepest - 1)
+ fprintf (stream, " * ");
+ }
+ }
+}
+
+/* Print to STREAM a representation of raising ARG to an integer
+ power N. Used for the dump file. */
+
+static void
+dump_integer_part (FILE *stream, const char* arg, HOST_WIDE_INT n)
+{
+ if (n > 1)
+ fprintf (stream, "powi (%s, " HOST_WIDE_INT_PRINT_DEC ")", arg, n);
+ else if (n == 1)
+ fprintf (stream, "%s", arg);
+}
+
+/* Attempt to synthesize a POW[F] (ARG0, ARG1) call using chains of
+ square roots. Place at GSI and LOC. Limit the maximum depth
+ of the sqrt chains to MAX_DEPTH. Return the tree holding the
+ result of the expanded sequence or NULL_TREE if the expansion failed.
+
+ This routine assumes that ARG1 is a real number with a fractional part
+ (the integer exponent case will have been handled earlier in
+ gimple_expand_builtin_pow).
+
+ For ARG1 > 0.0:
+ * For ARG1 composed of a whole part WHOLE_PART and a fractional part
+ FRAC_PART i.e. WHOLE_PART == floor (ARG1) and
+ FRAC_PART == ARG1 - WHOLE_PART:
+ Produce POWI (ARG0, WHOLE_PART) * POW (ARG0, FRAC_PART) where
+ POW (ARG0, FRAC_PART) is expanded as a product of square root chains
+ if it can be expressed as such, that is if FRAC_PART satisfies:
+ FRAC_PART == <SUM from i = 1 until MAX_DEPTH> (a[i] * (0.5**i))
+ where integer a[i] is either 0 or 1.
+
+ Example:
+ POW (x, 3.625) == POWI (x, 3) * POW (x, 0.625)
+ --> POWI (x, 3) * SQRT (x) * SQRT (SQRT (SQRT (x)))
+
+ For ARG1 < 0.0 there are two approaches:
+ * (A) Expand to 1.0 / POW (ARG0, -ARG1) where POW (ARG0, -ARG1)
+ is calculated as above.
+
+ Example:
+ POW (x, -5.625) == 1.0 / POW (x, 5.625)
+ --> 1.0 / (POWI (x, 5) * SQRT (x) * SQRT (SQRT (SQRT (x))))
+
+ * (B) : WHOLE_PART := - ceil (abs (ARG1))
+ FRAC_PART := ARG1 - WHOLE_PART
+ and expand to POW (x, FRAC_PART) / POWI (x, WHOLE_PART).
+ Example:
+ POW (x, -5.875) == POW (x, 0.125) / POWI (X, 6)
+ --> SQRT (SQRT (SQRT (x))) / (POWI (x, 6))
+
+ For ARG1 < 0.0 we choose between (A) and (B) depending on
+ how many multiplications we'd have to do.
+ So, for the example in (B): POW (x, -5.875), if we were to
+ follow algorithm (A) we would produce:
+ 1.0 / POWI (X, 5) * SQRT (X) * SQRT (SQRT (X)) * SQRT (SQRT (SQRT (X)))
+ which contains more multiplications than approach (B).
+
+ Hopefully, this approach will eliminate potentially expensive POW library
+ calls when unsafe floating point math is enabled and allow the compiler to
+ further optimise the multiplies, square roots and divides produced by this
+ function. */
+
+static tree
+expand_pow_as_sqrts (gimple_stmt_iterator *gsi, location_t loc,
+ tree arg0, tree arg1, HOST_WIDE_INT max_depth)
+{
+ tree type = TREE_TYPE (arg0);
+ machine_mode mode = TYPE_MODE (type);
+ tree sqrtfn = mathfn_built_in (type, BUILT_IN_SQRT);
+ bool one_over = true;
+
+ if (!sqrtfn)
+ return NULL_TREE;
+
+ if (TREE_CODE (arg1) != REAL_CST)
+ return NULL_TREE;
+
+ REAL_VALUE_TYPE exp_init = TREE_REAL_CST (arg1);
+
+ gcc_assert (max_depth > 0);
+ tree *cache = XALLOCAVEC (tree, max_depth + 1);
+
+ struct pow_synth_sqrt_info synth_info;
+ synth_info.factors = XALLOCAVEC (bool, max_depth + 1);
+ synth_info.deepest = 0;
+ synth_info.num_mults = 0;
+
+ bool neg_exp = REAL_VALUE_NEGATIVE (exp_init);
+ REAL_VALUE_TYPE exp = real_value_abs (&exp_init);
+
+ /* The whole and fractional parts of exp. */
+ REAL_VALUE_TYPE whole_part;
+ REAL_VALUE_TYPE frac_part;
+
+ real_floor (&whole_part, mode, &exp);
+ REAL_ARITHMETIC (frac_part, MINUS_EXPR, exp, whole_part);
+
+
+ REAL_VALUE_TYPE ceil_whole = dconst0;
+ REAL_VALUE_TYPE ceil_fract = dconst0;
+
+ if (neg_exp)
+ {
+ real_ceil (&ceil_whole, mode, &exp);
+ REAL_ARITHMETIC (ceil_fract, MINUS_EXPR, ceil_whole, exp);
+ }
+
+ if (!representable_as_half_series_p (frac_part, max_depth, &synth_info))
+ return NULL_TREE;
+
+ /* Check whether it's more profitable to not use 1.0 / ... */
+ if (neg_exp)
+ {
+ struct pow_synth_sqrt_info alt_synth_info;
+ alt_synth_info.factors = XALLOCAVEC (bool, max_depth + 1);
+ alt_synth_info.deepest = 0;
+ alt_synth_info.num_mults = 0;
+
+ if (representable_as_half_series_p (ceil_fract, max_depth,
+ &alt_synth_info)
+ && alt_synth_info.deepest <= synth_info.deepest
+ && alt_synth_info.num_mults < synth_info.num_mults)
+ {
+ whole_part = ceil_whole;
+ frac_part = ceil_fract;
+ synth_info.deepest = alt_synth_info.deepest;
+ synth_info.num_mults = alt_synth_info.num_mults;
+ memcpy (synth_info.factors, alt_synth_info.factors,
+ (max_depth + 1) * sizeof (bool));
+ one_over = false;
+ }
+ }
+
+ HOST_WIDE_INT n = real_to_integer (&whole_part);
+ REAL_VALUE_TYPE cint;
+ real_from_integer (&cint, VOIDmode, n, SIGNED);
+
+ if (!real_identical (&whole_part, &cint))
+ return NULL_TREE;
+
+ if (powi_cost (n) + synth_info.num_mults > POWI_MAX_MULTS)
+ return NULL_TREE;
+
+ memset (cache, 0, (max_depth + 1) * sizeof (tree));
+
+ tree integer_res = n == 0 ? build_real (type, dconst1) : arg0;
+
+ /* Calculate the integer part of the exponent. */
+ if (n > 1)
+ {
+ integer_res = gimple_expand_builtin_powi (gsi, loc, arg0, n);
+ if (!integer_res)
+ return NULL_TREE;
+ }
+
+ if (dump_file)
+ {
+ char string[64];
+
+ real_to_decimal (string, &exp_init, sizeof (string), 0, 1);
+ fprintf (dump_file, "synthesizing pow (x, %s) as:\n", string);
+
+ if (neg_exp)
+ {
+ if (one_over)
+ {
+ fprintf (dump_file, "1.0 / (");
+ dump_integer_part (dump_file, "x", n);
+ if (n > 0)
+ fprintf (dump_file, " * ");
+ dump_fractional_sqrt_sequence (dump_file, "x", &synth_info);
+ fprintf (dump_file, ")");
+ }
+ else
+ {
+ dump_fractional_sqrt_sequence (dump_file, "x", &synth_info);
+ fprintf (dump_file, " / (");
+ dump_integer_part (dump_file, "x", n);
+ fprintf (dump_file, ")");
+ }
+ }
+ else
+ {
+ dump_fractional_sqrt_sequence (dump_file, "x", &synth_info);
+ if (n > 0)
+ fprintf (dump_file, " * ");
+ dump_integer_part (dump_file, "x", n);
+ }
+
+ fprintf (dump_file, "\ndeepest sqrt chain: %d\n", synth_info.deepest);
+ }
+
+
+ tree fract_res = NULL_TREE;
+ cache[0] = arg0;
+
+ /* Calculate the fractional part of the exponent. */
+ for (unsigned i = 0; i < synth_info.deepest; i++)
+ {
+ if (synth_info.factors[i])
+ {
+ tree sqrt_chain = get_fn_chain (arg0, i + 1, gsi, sqrtfn, loc, cache);
+
+ if (!fract_res)
+ fract_res = sqrt_chain;
+
+ else
+ fract_res = build_and_insert_binop (gsi, loc, "powroot", MULT_EXPR,
+ fract_res, sqrt_chain);
+ }
+ }
+
+ tree res = NULL_TREE;
+
+ if (neg_exp)
+ {
+ if (one_over)
+ {
+ if (n > 0)
+ res = build_and_insert_binop (gsi, loc, "powroot", MULT_EXPR,
+ fract_res, integer_res);
+ else
+ res = fract_res;
+
+ res = build_and_insert_binop (gsi, loc, "powrootrecip", RDIV_EXPR,
+ build_real (type, dconst1), res);
+ }
+ else
+ {
+ res = build_and_insert_binop (gsi, loc, "powroot", RDIV_EXPR,
+ fract_res, integer_res);
+ }
+ }
+ else
+ res = build_and_insert_binop (gsi, loc, "powroot", MULT_EXPR,
+ fract_res, integer_res);
+ return res;
+}
+
/* ARG0 and ARG1 are the two arguments to a pow builtin call in GSI
with location info LOC. If possible, create an equivalent and
less expensive sequence of statements prior to GSI, and return an
gimple_expand_builtin_pow (gimple_stmt_iterator *gsi, location_t loc,
tree arg0, tree arg1)
{
- REAL_VALUE_TYPE c, cint, dconst1_4, dconst3_4, dconst1_3, dconst1_6;
+ REAL_VALUE_TYPE c, cint, dconst1_3, dconst1_4, dconst1_6;
REAL_VALUE_TYPE c2, dconst3;
HOST_WIDE_INT n;
- tree type, sqrtfn, cbrtfn, sqrt_arg0, sqrt_sqrt, result, cbrt_x, powi_cbrt_x;
- enum machine_mode mode;
+ tree type, sqrtfn, cbrtfn, sqrt_arg0, result, cbrt_x, powi_cbrt_x;
+ machine_mode mode;
+ bool speed_p = optimize_bb_for_speed_p (gsi_bb (*gsi));
bool hw_sqrt_exists, c_is_int, c2_is_int;
+ dconst1_4 = dconst1;
+ SET_REAL_EXP (&dconst1_4, REAL_EXP (&dconst1_4) - 2);
+
/* If the exponent isn't a constant, there's nothing of interest
to be done. */
if (TREE_CODE (arg1) != REAL_CST)
if (c_is_int
&& ((n >= -1 && n <= 2)
|| (flag_unsafe_math_optimizations
- && optimize_bb_for_speed_p (gsi_bb (*gsi))
+ && speed_p
&& powi_cost (n) <= POWI_MAX_MULTS)))
return gimple_expand_builtin_powi (gsi, loc, arg0, n);
&& !HONOR_SIGNED_ZEROS (mode))
return build_and_insert_call (gsi, loc, sqrtfn, arg0);
- /* Optimize pow(x,0.25) = sqrt(sqrt(x)). Assume on most machines that
- a builtin sqrt instruction is smaller than a call to pow with 0.25,
- so do this optimization even if -Os. Don't do this optimization
- if we don't have a hardware sqrt insn. */
- dconst1_4 = dconst1;
- SET_REAL_EXP (&dconst1_4, REAL_EXP (&dconst1_4) - 2);
hw_sqrt_exists = optab_handler (sqrt_optab, mode) != CODE_FOR_nothing;
- if (flag_unsafe_math_optimizations
- && sqrtfn
- && REAL_VALUES_EQUAL (c, dconst1_4)
- && hw_sqrt_exists)
- {
- /* sqrt(x) */
- sqrt_arg0 = build_and_insert_call (gsi, loc, sqrtfn, arg0);
-
- /* sqrt(sqrt(x)) */
- return build_and_insert_call (gsi, loc, sqrtfn, sqrt_arg0);
- }
-
- /* Optimize pow(x,0.75) = sqrt(x) * sqrt(sqrt(x)) unless we are
- optimizing for space. Don't do this optimization if we don't have
- a hardware sqrt insn. */
- real_from_integer (&dconst3_4, VOIDmode, 3, SIGNED);
- SET_REAL_EXP (&dconst3_4, REAL_EXP (&dconst3_4) - 2);
-
- if (flag_unsafe_math_optimizations
- && sqrtfn
- && optimize_function_for_speed_p (cfun)
- && REAL_VALUES_EQUAL (c, dconst3_4)
- && hw_sqrt_exists)
- {
- /* sqrt(x) */
- sqrt_arg0 = build_and_insert_call (gsi, loc, sqrtfn, arg0);
-
- /* sqrt(sqrt(x)) */
- sqrt_sqrt = build_and_insert_call (gsi, loc, sqrtfn, sqrt_arg0);
-
- /* sqrt(x) * sqrt(sqrt(x)) */
- return build_and_insert_binop (gsi, loc, "powroot", MULT_EXPR,
- sqrt_arg0, sqrt_sqrt);
- }
-
/* Optimize pow(x,1./3.) = cbrt(x). This requires unsafe math
optimizations since 1./3. is not exactly representable. If x
is negative and finite, the correct value of pow(x,1./3.) is
&& sqrtfn
&& cbrtfn
&& (gimple_val_nonnegative_real_p (arg0) || !HONOR_NANS (mode))
- && optimize_function_for_speed_p (cfun)
+ && speed_p
&& hw_sqrt_exists
&& REAL_VALUES_EQUAL (c, dconst1_6))
{
return build_and_insert_call (gsi, loc, cbrtfn, sqrt_arg0);
}
- /* Optimize pow(x,c), where n = 2c for some nonzero integer n
- and c not an integer, into
-
- sqrt(x) * powi(x, n/2), n > 0;
- 1.0 / (sqrt(x) * powi(x, abs(n/2))), n < 0.
-
- Do not calculate the powi factor when n/2 = 0. */
- real_arithmetic (&c2, MULT_EXPR, &c, &dconst2);
- n = real_to_integer (&c2);
- real_from_integer (&cint, VOIDmode, n, SIGNED);
- c2_is_int = real_identical (&c2, &cint);
+ /* Attempt to expand the POW as a product of square root chains.
+ Expand the 0.25 case even when otpimising for size. */
if (flag_unsafe_math_optimizations
&& sqrtfn
- && c2_is_int
- && !c_is_int
- && optimize_function_for_speed_p (cfun))
+ && hw_sqrt_exists
+ && (speed_p || REAL_VALUES_EQUAL (c, dconst1_4))
+ && !HONOR_SIGNED_ZEROS (mode))
{
- tree powi_x_ndiv2 = NULL_TREE;
-
- /* Attempt to fold powi(arg0, abs(n/2)) into multiplies. If not
- possible or profitable, give up. Skip the degenerate case when
- n is 1 or -1, where the result is always 1. */
- if (absu_hwi (n) != 1)
- {
- powi_x_ndiv2 = gimple_expand_builtin_powi (gsi, loc, arg0,
- abs_hwi (n / 2));
- if (!powi_x_ndiv2)
- return NULL_TREE;
- }
+ unsigned int max_depth = speed_p
+ ? PARAM_VALUE (PARAM_MAX_POW_SQRT_DEPTH)
+ : 2;
- /* Calculate sqrt(x). When n is not 1 or -1, multiply it by the
- result of the optimal multiply sequence just calculated. */
- sqrt_arg0 = build_and_insert_call (gsi, loc, sqrtfn, arg0);
+ tree expand_with_sqrts
+ = expand_pow_as_sqrts (gsi, loc, arg0, arg1, max_depth);
- if (absu_hwi (n) == 1)
- result = sqrt_arg0;
- else
- result = build_and_insert_binop (gsi, loc, "powroot", MULT_EXPR,
- sqrt_arg0, powi_x_ndiv2);
-
- /* If n is negative, reciprocate the result. */
- if (n < 0)
- result = build_and_insert_binop (gsi, loc, "powroot", RDIV_EXPR,
- build_real (type, dconst1), result);
- return result;
+ if (expand_with_sqrts)
+ return expand_with_sqrts;
}
+ real_arithmetic (&c2, MULT_EXPR, &c, &dconst2);
+ n = real_to_integer (&c2);
+ real_from_integer (&cint, VOIDmode, n, SIGNED);
+ c2_is_int = real_identical (&c2, &cint);
+
/* Optimize pow(x,c), where 3c = n for some nonzero integer n, into
powi(x, n/3) * powi(cbrt(x), n%3), n > 0;
tree real_part, imag_part, addend1, addend2, sum, result;
tree type = TREE_TYPE (TREE_TYPE (arg));
tree sqrtfn = mathfn_built_in (type, BUILT_IN_SQRT);
- enum machine_mode mode = TYPE_MODE (type);
+ machine_mode mode = TYPE_MODE (type);
if (!flag_unsafe_math_optimizations
|| !optimize_bb_for_speed_p (gimple_bb (gsi_stmt (*gsi)))
GIMPLE_PASS, /* type */
"sincos", /* name */
OPTGROUP_NONE, /* optinfo_flags */
- true, /* has_execute */
TV_NONE, /* tv_id */
PROP_ssa, /* properties_required */
0, /* properties_provided */
if (result)
{
tree lhs = gimple_get_lhs (stmt);
- gimple new_stmt = gimple_build_assign (lhs, result);
+ gassign *new_stmt = gimple_build_assign (lhs, result);
gimple_set_location (new_stmt, loc);
unlink_stmt_vdef (stmt);
gsi_replace (&gsi, new_stmt, true);
if (real_minus_onep (arg0))
{
tree t0, t1, cond, one, minus_one;
- gimple stmt;
+ gassign *stmt;
t0 = TREE_TYPE (arg0);
t1 = TREE_TYPE (arg1);
minus_one = build_real (t0, dconstm1);
cond = make_temp_ssa_name (t1, NULL, "powi_cond");
- stmt = gimple_build_assign_with_ops (BIT_AND_EXPR, cond,
- arg1,
- build_int_cst (t1,
- 1));
+ stmt = gimple_build_assign (cond, BIT_AND_EXPR,
+ arg1, build_int_cst (t1, 1));
gimple_set_location (stmt, loc);
gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
result = make_temp_ssa_name (t0, NULL, "powi");
- stmt = gimple_build_assign_with_ops (COND_EXPR, result,
- cond,
- minus_one, one);
+ stmt = gimple_build_assign (result, COND_EXPR, cond,
+ minus_one, one);
gimple_set_location (stmt, loc);
gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
}
if (result)
{
tree lhs = gimple_get_lhs (stmt);
- gimple new_stmt = gimple_build_assign (lhs, result);
+ gassign *new_stmt = gimple_build_assign (lhs, result);
gimple_set_location (new_stmt, loc);
unlink_stmt_vdef (stmt);
gsi_replace (&gsi, new_stmt, true);
if (result)
{
tree lhs = gimple_get_lhs (stmt);
- gimple new_stmt = gimple_build_assign (lhs, result);
+ gassign *new_stmt = gimple_build_assign (lhs, result);
gimple_set_location (new_stmt, loc);
unlink_stmt_vdef (stmt);
gsi_replace (&gsi, new_stmt, true);
/* A symbolic number is used to detect byte permutation and selection
patterns. Therefore the field N contains an artificial number
- consisting of byte size markers:
+ consisting of octet sized markers:
- 0 - byte has the value 0
- 1..size - byte contains the content of the byte
- number indexed with that value minus one.
+ 0 - target byte has the value 0
+ FF - target byte has an unknown value (eg. due to sign extension)
+ 1..size - marker value is the target byte index minus one.
To detect permutations on memory sources (arrays and structures), a symbolic
number is also associated a base address (the array or structure the load is
struct symbolic_number {
uint64_t n;
- int size;
+ tree type;
tree base_addr;
tree offset;
HOST_WIDE_INT bytepos;
unsigned HOST_WIDE_INT range;
};
+#define BITS_PER_MARKER 8
+#define MARKER_MASK ((1 << BITS_PER_MARKER) - 1)
+#define MARKER_BYTE_UNKNOWN MARKER_MASK
+#define HEAD_MARKER(n, size) \
+ ((n) & ((uint64_t) MARKER_MASK << (((size) - 1) * BITS_PER_MARKER)))
+
/* The number which the find_bswap_or_nop_1 result should match in
order to have a nop. The number is masked according to the size of
the symbolic number before using it. */
struct symbolic_number *n,
int count)
{
- if (count % 8 != 0)
+ int i, size = TYPE_PRECISION (n->type) / BITS_PER_UNIT;
+ unsigned head_marker;
+
+ if (count % BITS_PER_UNIT != 0)
return false;
+ count = (count / BITS_PER_UNIT) * BITS_PER_MARKER;
/* Zero out the extra bits of N in order to avoid them being shifted
into the significant bits. */
- if (n->size < (int)sizeof (int64_t))
- n->n &= ((uint64_t)1 << (n->size * BITS_PER_UNIT)) - 1;
+ if (size < 64 / BITS_PER_MARKER)
+ n->n &= ((uint64_t) 1 << (size * BITS_PER_MARKER)) - 1;
switch (code)
{
n->n <<= count;
break;
case RSHIFT_EXPR:
+ head_marker = HEAD_MARKER (n->n, size);
n->n >>= count;
+ /* Arithmetic shift of signed type: result is dependent on the value. */
+ if (!TYPE_UNSIGNED (n->type) && head_marker)
+ for (i = 0; i < count / BITS_PER_MARKER; i++)
+ n->n |= (uint64_t) MARKER_BYTE_UNKNOWN
+ << ((size - 1 - i) * BITS_PER_MARKER);
break;
case LROTATE_EXPR:
- n->n = (n->n << count) | (n->n >> ((n->size * BITS_PER_UNIT) - count));
+ n->n = (n->n << count) | (n->n >> ((size * BITS_PER_MARKER) - count));
break;
case RROTATE_EXPR:
- n->n = (n->n >> count) | (n->n << ((n->size * BITS_PER_UNIT) - count));
+ n->n = (n->n >> count) | (n->n << ((size * BITS_PER_MARKER) - count));
break;
default:
return false;
}
/* Zero unused bits for size. */
- if (n->size < (int)sizeof (int64_t))
- n->n &= ((uint64_t)1 << (n->size * BITS_PER_UNIT)) - 1;
+ if (size < 64 / BITS_PER_MARKER)
+ n->n &= ((uint64_t) 1 << (size * BITS_PER_MARKER)) - 1;
return true;
}
if (TREE_CODE (lhs_type) != INTEGER_TYPE)
return false;
- if (TYPE_PRECISION (lhs_type) != n->size * BITS_PER_UNIT)
+ if (TYPE_PRECISION (lhs_type) != TYPE_PRECISION (n->type))
return false;
return true;
static bool
init_symbolic_number (struct symbolic_number *n, tree src)
{
+ int size;
+
n->base_addr = n->offset = n->alias_set = n->vuse = NULL_TREE;
/* Set up the symbolic number N by setting each byte to a value between 1 and
the byte size of rhs1. The highest order byte is set to n->size and the
lowest order byte to 1. */
- n->size = TYPE_PRECISION (TREE_TYPE (src));
- if (n->size % BITS_PER_UNIT != 0)
+ n->type = TREE_TYPE (src);
+ size = TYPE_PRECISION (n->type);
+ if (size % BITS_PER_UNIT != 0)
+ return false;
+ size /= BITS_PER_UNIT;
+ if (size > 64 / BITS_PER_MARKER)
return false;
- n->size /= BITS_PER_UNIT;
- n->range = n->size;
+ n->range = size;
n->n = CMPNOP;
- if (n->size < (int)sizeof (int64_t))
- n->n &= ((uint64_t)1 << (n->size * BITS_PER_UNIT)) - 1;
+ if (size < 64 / BITS_PER_MARKER)
+ n->n &= ((uint64_t) 1 << (size * BITS_PER_MARKER)) - 1;
return true;
}
/* Leaf node is an array or component ref. Memorize its base and
offset from base to compare to other such leaf node. */
HOST_WIDE_INT bitsize, bitpos;
- enum machine_mode mode;
+ machine_mode mode;
int unsignedp, volatilep;
tree offset, base_addr;
+ /* Not prepared to handle PDP endian. */
+ if (BYTES_BIG_ENDIAN != WORDS_BIG_ENDIAN)
+ return false;
+
if (!gimple_assign_load_p (stmt) || gimple_has_volatile_ops (stmt))
return false;
if (bitsize % BITS_PER_UNIT)
return false;
- init_symbolic_number (n, ref);
+ if (!init_symbolic_number (n, ref))
+ return false;
n->base_addr = base_addr;
n->offset = offset;
n->bytepos = bitpos / BITS_PER_UNIT;
return true;
}
+/* Compute the symbolic number N representing the result of a bitwise OR on 2
+ symbolic number N1 and N2 whose source statements are respectively
+ SOURCE_STMT1 and SOURCE_STMT2. */
+
+static gimple
+perform_symbolic_merge (gimple source_stmt1, struct symbolic_number *n1,
+ gimple source_stmt2, struct symbolic_number *n2,
+ struct symbolic_number *n)
+{
+ int i, size;
+ uint64_t mask;
+ gimple source_stmt;
+ struct symbolic_number *n_start;
+
+ /* Sources are different, cancel bswap if they are not memory location with
+ the same base (array, structure, ...). */
+ if (gimple_assign_rhs1 (source_stmt1) != gimple_assign_rhs1 (source_stmt2))
+ {
+ int64_t inc;
+ HOST_WIDE_INT start_sub, end_sub, end1, end2, end;
+ struct symbolic_number *toinc_n_ptr, *n_end;
+
+ if (!n1->base_addr || !n2->base_addr
+ || !operand_equal_p (n1->base_addr, n2->base_addr, 0))
+ return NULL;
+
+ if (!n1->offset != !n2->offset
+ || (n1->offset && !operand_equal_p (n1->offset, n2->offset, 0)))
+ return NULL;
+
+ if (n1->bytepos < n2->bytepos)
+ {
+ n_start = n1;
+ start_sub = n2->bytepos - n1->bytepos;
+ source_stmt = source_stmt1;
+ }
+ else
+ {
+ n_start = n2;
+ start_sub = n1->bytepos - n2->bytepos;
+ source_stmt = source_stmt2;
+ }
+
+ /* Find the highest address at which a load is performed and
+ compute related info. */
+ end1 = n1->bytepos + (n1->range - 1);
+ end2 = n2->bytepos + (n2->range - 1);
+ if (end1 < end2)
+ {
+ end = end2;
+ end_sub = end2 - end1;
+ }
+ else
+ {
+ end = end1;
+ end_sub = end1 - end2;
+ }
+ n_end = (end2 > end1) ? n2 : n1;
+
+ /* Find symbolic number whose lsb is the most significant. */
+ if (BYTES_BIG_ENDIAN)
+ toinc_n_ptr = (n_end == n1) ? n2 : n1;
+ else
+ toinc_n_ptr = (n_start == n1) ? n2 : n1;
+
+ n->range = end - n_start->bytepos + 1;
+
+ /* Check that the range of memory covered can be represented by
+ a symbolic number. */
+ if (n->range > 64 / BITS_PER_MARKER)
+ return NULL;
+
+ /* Reinterpret byte marks in symbolic number holding the value of
+ bigger weight according to target endianness. */
+ inc = BYTES_BIG_ENDIAN ? end_sub : start_sub;
+ size = TYPE_PRECISION (n1->type) / BITS_PER_UNIT;
+ for (i = 0; i < size; i++, inc <<= BITS_PER_MARKER)
+ {
+ unsigned marker
+ = (toinc_n_ptr->n >> (i * BITS_PER_MARKER)) & MARKER_MASK;
+ if (marker && marker != MARKER_BYTE_UNKNOWN)
+ toinc_n_ptr->n += inc;
+ }
+ }
+ else
+ {
+ n->range = n1->range;
+ n_start = n1;
+ source_stmt = source_stmt1;
+ }
+
+ if (!n1->alias_set
+ || alias_ptr_types_compatible_p (n1->alias_set, n2->alias_set))
+ n->alias_set = n1->alias_set;
+ else
+ n->alias_set = ptr_type_node;
+ n->vuse = n_start->vuse;
+ n->base_addr = n_start->base_addr;
+ n->offset = n_start->offset;
+ n->bytepos = n_start->bytepos;
+ n->type = n_start->type;
+ size = TYPE_PRECISION (n->type) / BITS_PER_UNIT;
+
+ for (i = 0, mask = MARKER_MASK; i < size; i++, mask <<= BITS_PER_MARKER)
+ {
+ uint64_t masked1, masked2;
+
+ masked1 = n1->n & mask;
+ masked2 = n2->n & mask;
+ if (masked1 && masked2 && masked1 != masked2)
+ return NULL;
+ }
+ n->n = n1->n | n2->n;
+
+ return source_stmt;
+}
+
/* find_bswap_or_nop_1 invokes itself recursively with N and tries to perform
the operation given by the rhs of STMT on the result. If the operation
- could successfully be executed the function returns the tree expression of
- the source operand and NULL otherwise. */
+ could successfully be executed the function returns a gimple stmt whose
+ rhs's first tree is the expression of the source operand and NULL
+ otherwise. */
-static tree
+static gimple
find_bswap_or_nop_1 (gimple stmt, struct symbolic_number *n, int limit)
{
enum tree_code code;
tree rhs1, rhs2 = NULL;
- gimple rhs1_stmt, rhs2_stmt;
- tree source_expr1;
+ gimple rhs1_stmt, rhs2_stmt, source_stmt1;
enum gimple_rhs_class rhs_class;
if (!limit || !is_gimple_assign (stmt))
- return NULL_TREE;
+ return NULL;
rhs1 = gimple_assign_rhs1 (stmt);
if (find_bswap_or_nop_load (stmt, rhs1, n))
- return rhs1;
+ return stmt;
if (TREE_CODE (rhs1) != SSA_NAME)
- return NULL_TREE;
+ return NULL;
code = gimple_assign_rhs_code (stmt);
rhs_class = gimple_assign_rhs_class (stmt);
&& code != RSHIFT_EXPR
&& code != LROTATE_EXPR
&& code != RROTATE_EXPR
- && code != NOP_EXPR
- && code != CONVERT_EXPR)
- return NULL_TREE;
+ && !CONVERT_EXPR_CODE_P (code))
+ return NULL;
- source_expr1 = find_bswap_or_nop_1 (rhs1_stmt, n, limit - 1);
+ source_stmt1 = find_bswap_or_nop_1 (rhs1_stmt, n, limit - 1);
/* If find_bswap_or_nop_1 returned NULL, STMT is a leaf node and
we have to initialize the symbolic number. */
- if (!source_expr1)
+ if (!source_stmt1)
{
if (gimple_assign_load_p (stmt)
|| !init_symbolic_number (n, rhs1))
- return NULL_TREE;
- source_expr1 = rhs1;
+ return NULL;
+ source_stmt1 = stmt;
}
switch (code)
{
case BIT_AND_EXPR:
{
- int i;
- uint64_t val = int_cst_value (rhs2);
- uint64_t tmp = val;
+ int i, size = TYPE_PRECISION (n->type) / BITS_PER_UNIT;
+ uint64_t val = int_cst_value (rhs2), mask = 0;
+ uint64_t tmp = (1 << BITS_PER_UNIT) - 1;
/* Only constants masking full bytes are allowed. */
- for (i = 0; i < n->size; i++, tmp >>= BITS_PER_UNIT)
- if ((tmp & 0xff) != 0 && (tmp & 0xff) != 0xff)
- return NULL_TREE;
+ for (i = 0; i < size; i++, tmp <<= BITS_PER_UNIT)
+ if ((val & tmp) != 0 && (val & tmp) != tmp)
+ return NULL;
+ else if (val & tmp)
+ mask |= (uint64_t) MARKER_MASK << (i * BITS_PER_MARKER);
- n->n &= val;
+ n->n &= mask;
}
break;
case LSHIFT_EXPR:
case RSHIFT_EXPR:
case LROTATE_EXPR:
case RROTATE_EXPR:
- if (!do_shift_rotate (code, n, (int)TREE_INT_CST_LOW (rhs2)))
- return NULL_TREE;
+ if (!do_shift_rotate (code, n, (int) TREE_INT_CST_LOW (rhs2)))
+ return NULL;
break;
CASE_CONVERT:
{
- int type_size;
+ int i, type_size, old_type_size;
+ tree type;
- type_size = TYPE_PRECISION (gimple_expr_type (stmt));
+ type = gimple_expr_type (stmt);
+ type_size = TYPE_PRECISION (type);
if (type_size % BITS_PER_UNIT != 0)
- return NULL_TREE;
-
- if (type_size / BITS_PER_UNIT < (int)(sizeof (int64_t)))
+ return NULL;
+ type_size /= BITS_PER_UNIT;
+ if (type_size > 64 / BITS_PER_MARKER)
+ return NULL;
+
+ /* Sign extension: result is dependent on the value. */
+ old_type_size = TYPE_PRECISION (n->type) / BITS_PER_UNIT;
+ if (!TYPE_UNSIGNED (n->type) && type_size > old_type_size
+ && HEAD_MARKER (n->n, old_type_size))
+ for (i = 0; i < type_size - old_type_size; i++)
+ n->n |= (uint64_t) MARKER_BYTE_UNKNOWN
+ << ((type_size - 1 - i) * BITS_PER_MARKER);
+
+ if (type_size < 64 / BITS_PER_MARKER)
{
/* If STMT casts to a smaller type mask out the bits not
belonging to the target type. */
- n->n &= ((uint64_t)1 << type_size) - 1;
+ n->n &= ((uint64_t) 1 << (type_size * BITS_PER_MARKER)) - 1;
}
- n->size = type_size / BITS_PER_UNIT;
+ n->type = type;
if (!n->base_addr)
- n->range = n->size;
+ n->range = type_size;
}
break;
default:
- return NULL_TREE;
+ return NULL;
};
- return verify_symbolic_number_p (n, stmt) ? source_expr1 : NULL;
+ return verify_symbolic_number_p (n, stmt) ? source_stmt1 : NULL;
}
/* Handle binary rhs. */
if (rhs_class == GIMPLE_BINARY_RHS)
{
- int i;
struct symbolic_number n1, n2;
- uint64_t mask;
- tree source_expr2;
+ gimple source_stmt, source_stmt2;
if (code != BIT_IOR_EXPR)
- return NULL_TREE;
+ return NULL;
if (TREE_CODE (rhs2) != SSA_NAME)
- return NULL_TREE;
+ return NULL;
rhs2_stmt = SSA_NAME_DEF_STMT (rhs2);
switch (code)
{
case BIT_IOR_EXPR:
- source_expr1 = find_bswap_or_nop_1 (rhs1_stmt, &n1, limit - 1);
+ source_stmt1 = find_bswap_or_nop_1 (rhs1_stmt, &n1, limit - 1);
- if (!source_expr1)
- return NULL_TREE;
+ if (!source_stmt1)
+ return NULL;
- source_expr2 = find_bswap_or_nop_1 (rhs2_stmt, &n2, limit - 1);
-
- if (!source_expr2)
- return NULL_TREE;
+ source_stmt2 = find_bswap_or_nop_1 (rhs2_stmt, &n2, limit - 1);
- if (n1.size != n2.size)
- return NULL_TREE;
+ if (!source_stmt2)
+ return NULL;
- if (!n1.vuse != !n2.vuse ||
- (n1.vuse && !operand_equal_p (n1.vuse, n2.vuse, 0)))
- return NULL_TREE;
+ if (TYPE_PRECISION (n1.type) != TYPE_PRECISION (n2.type))
+ return NULL;
- if (source_expr1 != source_expr2)
- {
- int64_t inc, mask;
- unsigned i;
- HOST_WIDE_INT off_sub;
- struct symbolic_number *n_ptr;
-
- if (!n1.base_addr || !n2.base_addr
- || !operand_equal_p (n1.base_addr, n2.base_addr, 0))
- return NULL_TREE;
- if (!n1.offset != !n2.offset ||
- (n1.offset && !operand_equal_p (n1.offset, n2.offset, 0)))
- return NULL_TREE;
-
- /* We swap n1 with n2 to have n1 < n2. */
- if (n2.bytepos < n1.bytepos)
- {
- struct symbolic_number tmpn;
+ if (!n1.vuse != !n2.vuse
+ || (n1.vuse && !operand_equal_p (n1.vuse, n2.vuse, 0)))
+ return NULL;
- tmpn = n2;
- n2 = n1;
- n1 = tmpn;
- source_expr1 = source_expr2;
- }
+ source_stmt
+ = perform_symbolic_merge (source_stmt1, &n1, source_stmt2, &n2, n);
- off_sub = n2.bytepos - n1.bytepos;
-
- /* Check that the range of memory covered < biggest int size. */
- if (off_sub + n2.range > (int) sizeof (int64_t))
- return NULL_TREE;
- n->range = n2.range + off_sub;
-
- /* Reinterpret byte marks in symbolic number holding the value of
- bigger weight according to target endianness. */
- inc = BYTES_BIG_ENDIAN ? off_sub + n2.range - n1.range : off_sub;
- mask = 0xFF;
- if (BYTES_BIG_ENDIAN)
- n_ptr = &n1;
- else
- n_ptr = &n2;
- for (i = 0; i < sizeof (int64_t); i++, inc <<= 8,
- mask <<= 8)
- {
- if (n_ptr->n & mask)
- n_ptr->n += inc;
- }
- }
- else
- n->range = n1.range;
-
- if (!n1.alias_set
- || alias_ptr_types_compatible_p (n1.alias_set, n2.alias_set))
- n->alias_set = n1.alias_set;
- else
- n->alias_set = ptr_type_node;
- n->vuse = n1.vuse;
- n->base_addr = n1.base_addr;
- n->offset = n1.offset;
- n->bytepos = n1.bytepos;
- n->size = n1.size;
- for (i = 0, mask = 0xff; i < n->size; i++, mask <<= BITS_PER_UNIT)
- {
- uint64_t masked1, masked2;
-
- masked1 = n1.n & mask;
- masked2 = n2.n & mask;
- if (masked1 && masked2 && masked1 != masked2)
- return NULL_TREE;
- }
- n->n = n1.n | n2.n;
+ if (!source_stmt)
+ return NULL;
if (!verify_symbolic_number_p (n, stmt))
- return NULL_TREE;
+ return NULL;
break;
default:
- return NULL_TREE;
+ return NULL;
}
- return source_expr1;
+ return source_stmt;
}
- return NULL_TREE;
+ return NULL;
}
/* Check if STMT completes a bswap implementation or a read in a given
accordingly. It also sets N to represent the kind of operations
performed: size of the resulting expression and whether it works on
a memory source, and if so alias-set and vuse. At last, the
- function returns the source tree expression. */
+ function returns a stmt whose rhs's first tree is the source
+ expression. */
-static tree
+static gimple
find_bswap_or_nop (gimple stmt, struct symbolic_number *n, bool *bswap)
{
/* The number which the find_bswap_or_nop_1 result should match in order
uint64_t cmpxchg = CMPXCHG;
uint64_t cmpnop = CMPNOP;
- tree source_expr;
+ gimple source_stmt;
int limit;
/* The last parameter determines the depth search limit. It usually
in libgcc, and for initial shift/and operation of the src operand. */
limit = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (gimple_expr_type (stmt)));
limit += 1 + (int) ceil_log2 ((unsigned HOST_WIDE_INT) limit);
- source_expr = find_bswap_or_nop_1 (stmt, n, limit);
+ source_stmt = find_bswap_or_nop_1 (stmt, n, limit);
- if (!source_expr)
- return NULL_TREE;
+ if (!source_stmt)
+ return NULL;
- /* Find real size of result (highest non zero byte). */
+ /* Find real size of result (highest non-zero byte). */
if (n->base_addr)
{
int rsize;
uint64_t tmpn;
- for (tmpn = n->n, rsize = 0; tmpn; tmpn >>= BITS_PER_UNIT, rsize++);
+ for (tmpn = n->n, rsize = 0; tmpn; tmpn >>= BITS_PER_MARKER, rsize++);
n->range = rsize;
}
/* Zero out the extra bits of N and CMP*. */
- if (n->range < (int)sizeof (int64_t))
+ if (n->range < (int) sizeof (int64_t))
{
uint64_t mask;
- mask = ((uint64_t)1 << (n->range * BITS_PER_UNIT)) - 1;
- cmpxchg >>= (sizeof (int64_t) - n->range) * BITS_PER_UNIT;
+ mask = ((uint64_t) 1 << (n->range * BITS_PER_MARKER)) - 1;
+ cmpxchg >>= (64 / BITS_PER_MARKER - n->range) * BITS_PER_MARKER;
cmpnop &= mask;
}
else if (n->n == cmpxchg)
*bswap = true;
else
- return NULL_TREE;
+ return NULL;
/* Useless bit manipulation performed by code. */
if (!n->base_addr && n->n == cmpnop)
- return NULL_TREE;
+ return NULL;
n->range *= BITS_PER_UNIT;
- return source_expr;
+ return source_stmt;
}
namespace {
GIMPLE_PASS, /* type */
"bswap", /* name */
OPTGROUP_NONE, /* optinfo_flags */
- true, /* has_execute */
TV_NONE, /* tv_id */
PROP_ssa, /* properties_required */
0, /* properties_provided */
}; // class pass_optimize_bswap
-/* Perform the bswap optimization: replace the statement STMT at GSI
- with load type, VUSE and set-alias as described by N if a memory
- source is involved (N->base_addr is non null), followed by the
- builtin bswap invocation in FNDECL if BSWAP is true. SRC gives
- the source on which STMT is operating and N->range gives the
- size of the expression involved for maintaining some statistics. */
+/* Perform the bswap optimization: replace the expression computed in the rhs
+ of CUR_STMT by an equivalent bswap, load or load + bswap expression.
+ Which of these alternatives replace the rhs is given by N->base_addr (non
+ null if a load is needed) and BSWAP. The type, VUSE and set-alias of the
+ load to perform are also given in N while the builtin bswap invoke is given
+ in FNDEL. Finally, if a load is involved, SRC_STMT refers to one of the
+ load statements involved to construct the rhs in CUR_STMT and N->range gives
+ the size of the rhs expression for maintaining some statistics.
+
+ Note that if the replacement involve a load, CUR_STMT is moved just after
+ SRC_STMT to do the load with the same VUSE which can lead to CUR_STMT
+ changing of basic block. */
static bool
-bswap_replace (gimple stmt, gimple_stmt_iterator *gsi, tree src, tree fndecl,
- tree bswap_type, tree load_type, struct symbolic_number *n,
- bool bswap)
+bswap_replace (gimple cur_stmt, gimple src_stmt, tree fndecl, tree bswap_type,
+ tree load_type, struct symbolic_number *n, bool bswap)
{
- tree tmp, tgt;
- gimple call;
+ gimple_stmt_iterator gsi;
+ tree src, tmp, tgt;
+ gimple bswap_stmt;
- tgt = gimple_assign_lhs (stmt);
+ gsi = gsi_for_stmt (cur_stmt);
+ src = gimple_assign_rhs1 (src_stmt);
+ tgt = gimple_assign_lhs (cur_stmt);
/* Need to load the value from memory first. */
if (n->base_addr)
{
+ gimple_stmt_iterator gsi_ins = gsi_for_stmt (src_stmt);
tree addr_expr, addr_tmp, val_expr, val_tmp;
tree load_offset_ptr, aligned_load_type;
gimple addr_stmt, load_stmt;
unsigned align;
+ HOST_WIDE_INT load_offset = 0;
align = get_object_alignment (src);
- if (bswap && SLOW_UNALIGNED_ACCESS (TYPE_MODE (load_type), align))
+ /* If the new access is smaller than the original one, we need
+ to perform big endian adjustment. */
+ if (BYTES_BIG_ENDIAN)
+ {
+ HOST_WIDE_INT bitsize, bitpos;
+ machine_mode mode;
+ int unsignedp, volatilep;
+ tree offset;
+
+ get_inner_reference (src, &bitsize, &bitpos, &offset, &mode,
+ &unsignedp, &volatilep, false);
+ if (n->range < (unsigned HOST_WIDE_INT) bitsize)
+ {
+ load_offset = (bitsize - n->range) / BITS_PER_UNIT;
+ unsigned HOST_WIDE_INT l
+ = (load_offset * BITS_PER_UNIT) & (align - 1);
+ if (l)
+ align = l & -l;
+ }
+ }
+
+ if (bswap
+ && align < GET_MODE_ALIGNMENT (TYPE_MODE (load_type))
+ && SLOW_UNALIGNED_ACCESS (TYPE_MODE (load_type), align))
return false;
- /* Compute address to load from and cast according to the size
- of the load. */
+ /* Move cur_stmt just before one of the load of the original
+ to ensure it has the same VUSE. See PR61517 for what could
+ go wrong. */
+ gsi_move_before (&gsi, &gsi_ins);
+ gsi = gsi_for_stmt (cur_stmt);
+
+ /* Compute address to load from and cast according to the size
+ of the load. */
addr_expr = build_fold_addr_expr (unshare_expr (src));
- if (is_gimple_min_invariant (addr_expr))
+ if (is_gimple_mem_ref_addr (addr_expr))
addr_tmp = addr_expr;
else
{
addr_tmp = make_temp_ssa_name (TREE_TYPE (addr_expr), NULL,
"load_src");
addr_stmt = gimple_build_assign (addr_tmp, addr_expr);
- gsi_insert_before (gsi, addr_stmt, GSI_SAME_STMT);
+ gsi_insert_before (&gsi, addr_stmt, GSI_SAME_STMT);
}
/* Perform the load. */
aligned_load_type = load_type;
if (align < TYPE_ALIGN (load_type))
aligned_load_type = build_aligned_type (load_type, align);
- load_offset_ptr = build_int_cst (n->alias_set, 0);
+ load_offset_ptr = build_int_cst (n->alias_set, load_offset);
val_expr = fold_build2 (MEM_REF, aligned_load_type, addr_tmp,
load_offset_ptr);
"load_dst");
load_stmt = gimple_build_assign (val_tmp, val_expr);
gimple_set_vuse (load_stmt, n->vuse);
- gsi_insert_before (gsi, load_stmt, GSI_SAME_STMT);
- gimple_assign_set_rhs_with_ops_1 (gsi, NOP_EXPR, val_tmp,
- NULL_TREE, NULL_TREE);
+ gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
+ gimple_assign_set_rhs_with_ops (&gsi, NOP_EXPR, val_tmp);
}
else
- gimple_assign_set_rhs_with_ops_1 (gsi, MEM_REF, val_expr,
- NULL_TREE, NULL_TREE);
- update_stmt (gsi_stmt (*gsi));
+ {
+ gimple_assign_set_rhs_with_ops (&gsi, MEM_REF, val_expr);
+ gimple_set_vuse (cur_stmt, n->vuse);
+ }
+ update_stmt (cur_stmt);
if (dump_file)
{
fprintf (dump_file,
"%d bit load in target endianness found at: ",
- (int)n->range);
- print_gimple_stmt (dump_file, stmt, 0, 0);
+ (int) n->range);
+ print_gimple_stmt (dump_file, cur_stmt, 0, 0);
}
return true;
}
val_tmp = make_temp_ssa_name (aligned_load_type, NULL, "load_dst");
load_stmt = gimple_build_assign (val_tmp, val_expr);
gimple_set_vuse (load_stmt, n->vuse);
- gsi_insert_before (gsi, load_stmt, GSI_SAME_STMT);
+ gsi_insert_before (&gsi, load_stmt, GSI_SAME_STMT);
}
src = val_tmp;
}
if (!useless_type_conversion_p (TREE_TYPE (tmp), bswap_type))
{
gimple convert_stmt;
+
tmp = make_temp_ssa_name (bswap_type, NULL, "bswapsrc");
- convert_stmt = gimple_build_assign_with_ops (NOP_EXPR, tmp, src, NULL);
- gsi_insert_before (gsi, convert_stmt, GSI_SAME_STMT);
+ convert_stmt = gimple_build_assign (tmp, NOP_EXPR, src);
+ gsi_insert_before (&gsi, convert_stmt, GSI_SAME_STMT);
}
- call = gimple_build_call (fndecl, 1, tmp);
+ /* Canonical form for 16 bit bswap is a rotate expression. Only 16bit values
+ are considered as rotation of 2N bit values by N bits is generally not
+ equivalent to a bswap. Consider for instance 0x01020304 r>> 16 which
+ gives 0x03040102 while a bswap for that value is 0x04030201. */
+ if (bswap && n->range == 16)
+ {
+ tree count = build_int_cst (NULL, BITS_PER_UNIT);
+ src = fold_build2 (LROTATE_EXPR, bswap_type, tmp, count);
+ bswap_stmt = gimple_build_assign (NULL, src);
+ }
+ else
+ bswap_stmt = gimple_build_call (fndecl, 1, tmp);
tmp = tgt;
if (!useless_type_conversion_p (TREE_TYPE (tgt), bswap_type))
{
gimple convert_stmt;
+
tmp = make_temp_ssa_name (bswap_type, NULL, "bswapdst");
- convert_stmt = gimple_build_assign_with_ops (NOP_EXPR, tgt, tmp, NULL);
- gsi_insert_after (gsi, convert_stmt, GSI_SAME_STMT);
+ convert_stmt = gimple_build_assign (tgt, NOP_EXPR, tmp);
+ gsi_insert_after (&gsi, convert_stmt, GSI_SAME_STMT);
}
- gimple_call_set_lhs (call, tmp);
+ gimple_set_lhs (bswap_stmt, tmp);
if (dump_file)
{
fprintf (dump_file, "%d bit bswap implementation found at: ",
- (int)n->range);
- print_gimple_stmt (dump_file, stmt, 0, 0);
+ (int) n->range);
+ print_gimple_stmt (dump_file, cur_stmt, 0, 0);
}
- gsi_insert_after (gsi, call, GSI_SAME_STMT);
- gsi_remove (gsi, true);
+ gsi_insert_after (&gsi, bswap_stmt, GSI_SAME_STMT);
+ gsi_remove (&gsi, true);
return true;
}
pass_optimize_bswap::execute (function *fun)
{
basic_block bb;
- bool bswap16_p, bswap32_p, bswap64_p;
+ bool bswap32_p, bswap64_p;
bool changed = false;
- tree bswap16_type = NULL_TREE, bswap32_type = NULL_TREE, bswap64_type = NULL_TREE;
+ tree bswap32_type = NULL_TREE, bswap64_type = NULL_TREE;
if (BITS_PER_UNIT != 8)
return 0;
- bswap16_p = (builtin_decl_explicit_p (BUILT_IN_BSWAP16)
- && optab_handler (bswap_optab, HImode) != CODE_FOR_nothing);
bswap32_p = (builtin_decl_explicit_p (BUILT_IN_BSWAP32)
&& optab_handler (bswap_optab, SImode) != CODE_FOR_nothing);
bswap64_p = (builtin_decl_explicit_p (BUILT_IN_BSWAP64)
/* Determine the argument type of the builtins. The code later on
assumes that the return and argument type are the same. */
- if (bswap16_p)
- {
- tree fndecl = builtin_decl_explicit (BUILT_IN_BSWAP16);
- bswap16_type = TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fndecl)));
- }
-
if (bswap32_p)
{
tree fndecl = builtin_decl_explicit (BUILT_IN_BSWAP32);
gimple_stmt_iterator gsi;
/* We do a reverse scan for bswap patterns to make sure we get the
- widest match. As bswap pattern matching doesn't handle
- previously inserted smaller bswap replacements as sub-
- patterns, the wider variant wouldn't be detected. */
- for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
+ widest match. As bswap pattern matching doesn't handle previously
+ inserted smaller bswap replacements as sub-patterns, the wider
+ variant wouldn't be detected. */
+ for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
{
- gimple stmt = gsi_stmt (gsi);
- tree fndecl = NULL_TREE, bswap_type = NULL_TREE;
- tree src, load_type;
+ gimple src_stmt, cur_stmt = gsi_stmt (gsi);
+ tree fndecl = NULL_TREE, bswap_type = NULL_TREE, load_type;
+ enum tree_code code;
struct symbolic_number n;
bool bswap;
- if (!is_gimple_assign (stmt)
- || gimple_assign_rhs_code (stmt) != BIT_IOR_EXPR)
+ /* This gsi_prev (&gsi) is not part of the for loop because cur_stmt
+ might be moved to a different basic block by bswap_replace and gsi
+ must not points to it if that's the case. Moving the gsi_prev
+ there make sure that gsi points to the statement previous to
+ cur_stmt while still making sure that all statements are
+ considered in this basic block. */
+ gsi_prev (&gsi);
+
+ if (!is_gimple_assign (cur_stmt))
continue;
- src = find_bswap_or_nop (stmt, &n, &bswap);
+ code = gimple_assign_rhs_code (cur_stmt);
+ switch (code)
+ {
+ case LROTATE_EXPR:
+ case RROTATE_EXPR:
+ if (!tree_fits_uhwi_p (gimple_assign_rhs2 (cur_stmt))
+ || tree_to_uhwi (gimple_assign_rhs2 (cur_stmt))
+ % BITS_PER_UNIT)
+ continue;
+ /* Fall through. */
+ case BIT_IOR_EXPR:
+ break;
+ default:
+ continue;
+ }
+
+ src_stmt = find_bswap_or_nop (cur_stmt, &n, &bswap);
- if (!src)
+ if (!src_stmt)
continue;
switch (n.range)
{
case 16:
- load_type = uint16_type_node;
- if (bswap16_p)
- {
- fndecl = builtin_decl_explicit (BUILT_IN_BSWAP16);
- bswap_type = bswap16_type;
- }
+ /* Already in canonical form, nothing to do. */
+ if (code == LROTATE_EXPR || code == RROTATE_EXPR)
+ continue;
+ load_type = bswap_type = uint16_type_node;
break;
case 32:
load_type = uint32_type_node;
continue;
}
- if (bswap && !fndecl)
+ if (bswap && !fndecl && n.range != 16)
continue;
- if (bswap_replace (stmt, &gsi, src, fndecl, bswap_type, load_type,
+ if (bswap_replace (cur_stmt, src_stmt, fndecl, bswap_type, load_type,
&n, bswap))
changed = true;
}
/* Ensure that the larger of the two operands comes first. */
if (TYPE_PRECISION (*type1_out) < TYPE_PRECISION (*type2_out))
{
- tree tmp;
- tmp = *type1_out;
- *type1_out = *type2_out;
- *type2_out = tmp;
- tmp = *rhs1_out;
- *rhs1_out = *rhs2_out;
- *rhs2_out = tmp;
+ std::swap (*type1_out, *type2_out);
+ std::swap (*rhs1_out, *rhs2_out);
}
return true;
{
tree lhs, rhs1, rhs2, type, type1, type2;
enum insn_code handler;
- enum machine_mode to_mode, from_mode, actual_mode;
+ machine_mode to_mode, from_mode, actual_mode;
optab op;
int actual_precision;
location_t loc = gimple_location (stmt);
optab this_optab;
enum tree_code wmult_code;
enum insn_code handler;
- enum machine_mode to_mode, from_mode, actual_mode;
+ machine_mode to_mode, from_mode, actual_mode;
location_t loc = gimple_location (stmt);
int actual_precision;
bool from_unsigned1, from_unsigned2;
if (TREE_CODE (mult_rhs2) == INTEGER_CST)
mult_rhs2 = fold_convert (type2, mult_rhs2);
- gimple_assign_set_rhs_with_ops_1 (gsi, wmult_code, mult_rhs1, mult_rhs2,
- add_rhs);
+ gimple_assign_set_rhs_with_ops (gsi, wmult_code, mult_rhs1, mult_rhs2,
+ add_rhs);
update_stmt (gsi_stmt (*gsi));
widen_mul_stats.maccs_inserted++;
return true;
{
tree mul_result = gimple_get_lhs (mul_stmt);
tree type = TREE_TYPE (mul_result);
- gimple use_stmt, neguse_stmt, fma_stmt;
+ gimple use_stmt, neguse_stmt;
+ gassign *fma_stmt;
use_operand_p use_p;
imm_use_iterator imm_iter;
true, NULL_TREE, true,
GSI_SAME_STMT);
- fma_stmt = gimple_build_assign_with_ops (FMA_EXPR,
- gimple_assign_lhs (use_stmt),
- mulop1, op2,
- addop);
+ 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++;
}
GIMPLE_PASS, /* type */
"widening_mul", /* name */
OPTGROUP_NONE, /* optinfo_flags */
- true, /* has_execute */
TV_NONE, /* tv_id */
PROP_ssa, /* properties_required */
0, /* properties_provided */
projects / gcc.git / blobdiff