/* Reassociation for trees.
- Copyright (C) 2005-2014 Free Software Foundation, Inc.
+ Copyright (C) 2005-2015 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dan@dberlin.org>
This file is part of GCC.
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "hash-table.h"
#include "tm.h"
#include "rtl.h"
#include "tm_p.h"
+#include "alias.h"
+#include "symtab.h"
#include "tree.h"
+#include "fold-const.h"
#include "stor-layout.h"
+#include "predict.h"
+#include "hard-reg-set.h"
+#include "function.h"
+#include "dominance.h"
+#include "cfg.h"
+#include "cfganal.h"
#include "basic-block.h"
#include "gimple-pretty-print.h"
#include "tree-inline.h"
-#include "hash-map.h"
#include "tree-ssa-alias.h"
#include "internal-fn.h"
#include "gimple-fold.h"
#include "tree-eh.h"
#include "gimple-expr.h"
-#include "is-a.h"
#include "gimple.h"
#include "gimple-iterator.h"
#include "gimplify-me.h"
#include "tree-ssanames.h"
#include "tree-ssa-loop-niter.h"
#include "tree-ssa-loop.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-dfa.h"
#include "tree-ssa.h"
#include "alloc-pool.h"
#include "langhooks.h"
#include "cfgloop.h"
-#include "flags.h"
#include "target.h"
#include "params.h"
#include "diagnostic-core.h"
#include "builtins.h"
+#include "gimplify.h"
+#include "insn-codes.h"
+#include "optabs.h"
/* This is a simple global reassociation pass. It is, in part, based
on the LLVM pass of the same name (They do some things more/less
unsigned int count;
} *operand_entry_t;
-static alloc_pool operand_entry_pool;
+static pool_allocator<operand_entry> operand_entry_pool ("operand entry pool",
+ 30);
/* This is used to assign a unique ID to each struct operand_entry
so that qsort results are identical on different hosts. */
/* Operand->rank hashtable. */
static hash_map<tree, long> *operand_rank;
+/* Vector of SSA_NAMEs on which after reassociate_bb is done with
+ all basic blocks the CFG should be adjusted - basic blocks
+ split right after that SSA_NAME's definition statement and before
+ the only use, which must be a bit ior. */
+static vec<tree> reassoc_branch_fixups;
+
/* Forward decls. */
static long get_rank (tree);
static bool reassoc_stmt_dominates_stmt_p (gimple, gimple);
static long
get_rank (tree e)
{
- /* Constants have rank 0. */
- if (is_gimple_min_invariant (e))
- return 0;
-
/* SSA_NAME's have the rank of the expression they are the result
of.
For globals and uninitialized values, the rank is 0.
if (TREE_CODE (e) == SSA_NAME)
{
+ ssa_op_iter iter;
gimple stmt;
long rank;
- int i, n;
tree op;
if (SSA_NAME_IS_DEFAULT_DEF (e))
if (gimple_code (stmt) == GIMPLE_PHI)
return phi_rank (stmt);
- if (!is_gimple_assign (stmt)
- || gimple_vdef (stmt))
+ if (!is_gimple_assign (stmt))
return bb_rank[gimple_bb (stmt)->index];
/* If we already have a rank for this expression, use that. */
/* Otherwise, find the maximum rank for the operands. As an
exception, remove the bias from loop-carried phis when propagating
the rank so that dependent operations are not also biased. */
+ /* Simply walk over all SSA uses - this takes advatage of the
+ fact that non-SSA operands are is_gimple_min_invariant and
+ thus have rank 0. */
rank = 0;
- if (gimple_assign_single_p (stmt))
- {
- tree rhs = gimple_assign_rhs1 (stmt);
- n = TREE_OPERAND_LENGTH (rhs);
- if (n == 0)
- rank = propagate_rank (rank, rhs);
- else
- {
- for (i = 0; i < n; i++)
- {
- op = TREE_OPERAND (rhs, i);
-
- if (op != NULL_TREE)
- rank = propagate_rank (rank, op);
- }
- }
- }
- else
- {
- n = gimple_num_ops (stmt);
- for (i = 1; i < n; i++)
- {
- op = gimple_op (stmt, i);
- gcc_assert (op);
- rank = propagate_rank (rank, op);
- }
- }
+ FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
+ rank = propagate_rank (rank, op);
if (dump_file && (dump_flags & TDF_DETAILS))
{
return (rank + 1);
}
- /* Globals, etc, are rank 0 */
+ /* Constants, globals, etc., are rank 0 */
return 0;
}
static void
add_to_ops_vec (vec<operand_entry_t> *ops, tree op)
{
- operand_entry_t oe = (operand_entry_t) pool_alloc (operand_entry_pool);
+ operand_entry_t oe = operand_entry_pool.allocate ();
oe->op = op;
oe->rank = get_rank (op);
add_repeat_to_ops_vec (vec<operand_entry_t> *ops, tree op,
HOST_WIDE_INT repeat)
{
- operand_entry_t oe = (operand_entry_t) pool_alloc (operand_entry_pool);
+ operand_entry_t oe = operand_entry_pool.allocate ();
oe->op = op;
oe->rank = get_rank (op);
case MULT_EXPR:
if (integer_zerop (oelast->op)
|| (FLOAT_TYPE_P (type)
- && !HONOR_NANS (TYPE_MODE (type))
- && !HONOR_SIGNED_ZEROS (TYPE_MODE (type))
+ && !HONOR_NANS (type)
+ && !HONOR_SIGNED_ZEROS (type)
&& real_zerop (oelast->op)))
{
if (ops->length () != 1)
}
else if (integer_onep (oelast->op)
|| (FLOAT_TYPE_P (type)
- && !HONOR_SNANS (TYPE_MODE (type))
+ && !HONOR_SNANS (type)
&& real_onep (oelast->op)))
{
if (ops->length () != 1)
/* Oecount hashtable helpers. */
-struct oecount_hasher
+struct oecount_hasher : int_hash <int, 0, 1>
{
- typedef int value_type;
- typedef int compare_type;
- typedef int store_values_directly;
- static inline hashval_t hash (const value_type &);
- static inline bool equal (const value_type &, const compare_type &);
- static bool is_deleted (int &v) { return v == 1; }
- static void mark_deleted (int &e) { e = 1; }
- static bool is_empty (int &v) { return v == 0; }
- static void mark_empty (int &e) { e = 0; }
- static void remove (int &) {}
+ static inline hashval_t hash (int);
+ static inline bool equal (int, int);
};
/* Hash function for oecount. */
inline hashval_t
-oecount_hasher::hash (const value_type &p)
+oecount_hasher::hash (int p)
{
const oecount *c = &cvec[p - 42];
return htab_hash_pointer (c->op) ^ (hashval_t)c->oecode;
/* Comparison function for oecount. */
inline bool
-oecount_hasher::equal (const value_type &p1, const compare_type &p2)
+oecount_hasher::equal (int p1, int p2)
{
const oecount *c1 = &cvec[p1 - 42];
const oecount *c2 = &cvec[p2 - 42];
gimple op1def = NULL, op2def = NULL;
gimple_stmt_iterator gsi;
tree op;
- gimple sum;
+ gassign *sum;
/* Create the addition statement. */
- op = make_ssa_name (type, NULL);
- sum = gimple_build_assign_with_ops (opcode, op, op1, op2);
+ op = make_ssa_name (type);
+ sum = gimple_build_assign (op, opcode, op1, op2);
/* Find an insertion place and insert. */
if (TREE_CODE (op1) == SSA_NAME)
else
return -1;
}
- else if (p->high != NULL_TREE)
+ else if (q->high != NULL_TREE)
return 1;
/* If both ranges are the same, sort below by ascending idx. */
}
/* Helper routine of optimize_range_test.
[EXP, IN_P, LOW, HIGH, STRICT_OVERFLOW_P] is a merged range for
RANGE and OTHERRANGE through OTHERRANGE + COUNT - 1 ranges,
- OPCODE and OPS are arguments of optimize_range_tests. Return
+ OPCODE and OPS are arguments of optimize_range_tests. If OTHERRANGE
+ is NULL, OTHERRANGEP should not be and then OTHERRANGEP points to
+ an array of COUNT pointers to other ranges. Return
true if the range merge has been successful.
If OPCODE is ERROR_MARK, this is called from within
maybe_optimize_range_tests and is performing inter-bb range optimization.
static bool
update_range_test (struct range_entry *range, struct range_entry *otherrange,
+ struct range_entry **otherrangep,
unsigned int count, enum tree_code opcode,
- vec<operand_entry_t> *ops, tree exp, bool in_p,
- tree low, tree high, bool strict_overflow_p)
+ vec<operand_entry_t> *ops, tree exp, gimple_seq seq,
+ bool in_p, tree low, tree high, bool strict_overflow_p)
{
operand_entry_t oe = (*ops)[range->idx];
tree op = oe->op;
last_stmt (BASIC_BLOCK_FOR_FN (cfun, oe->id));
location_t loc = gimple_location (stmt);
tree optype = op ? TREE_TYPE (op) : boolean_type_node;
- tree tem = build_range_check (loc, optype, exp, in_p, low, high);
+ tree tem = build_range_check (loc, optype, unshare_expr (exp),
+ in_p, low, high);
enum warn_strict_overflow_code wc = WARN_STRICT_OVERFLOW_COMPARISON;
gimple_stmt_iterator gsi;
+ unsigned int i;
if (tem == NULL_TREE)
return false;
fprintf (dump_file, ", ");
print_generic_expr (dump_file, range->high, 0);
fprintf (dump_file, "]");
- for (r = otherrange; r < otherrange + count; r++)
+ for (i = 0; i < count; i++)
{
+ if (otherrange)
+ r = otherrange + i;
+ else
+ r = otherrangep[i];
fprintf (dump_file, " and %c[", r->in_p ? '+' : '-');
print_generic_expr (dump_file, r->low, 0);
fprintf (dump_file, ", ");
tem = fold_convert_loc (loc, optype, tem);
gsi = gsi_for_stmt (stmt);
+ unsigned int uid = gimple_uid (stmt);
/* In rare cases range->exp can be equal to lhs of stmt.
In that case we have to insert after the stmt rather then before
- it. */
- if (op == range->exp)
- tem = force_gimple_operand_gsi (&gsi, tem, true, NULL_TREE, false,
- GSI_CONTINUE_LINKING);
- else
+ it. If stmt is a PHI, insert it at the start of the basic block. */
+ if (op != range->exp)
{
+ gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
tem = force_gimple_operand_gsi (&gsi, tem, true, NULL_TREE, true,
GSI_SAME_STMT);
gsi_prev (&gsi);
}
+ else if (gimple_code (stmt) != GIMPLE_PHI)
+ {
+ gsi_insert_seq_after (&gsi, seq, GSI_CONTINUE_LINKING);
+ tem = force_gimple_operand_gsi (&gsi, tem, true, NULL_TREE, false,
+ GSI_CONTINUE_LINKING);
+ }
+ else
+ {
+ gsi = gsi_after_labels (gimple_bb (stmt));
+ if (!gsi_end_p (gsi))
+ uid = gimple_uid (gsi_stmt (gsi));
+ else
+ {
+ gsi = gsi_start_bb (gimple_bb (stmt));
+ uid = 1;
+ while (!gsi_end_p (gsi))
+ {
+ uid = gimple_uid (gsi_stmt (gsi));
+ gsi_next (&gsi);
+ }
+ }
+ gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT);
+ tem = force_gimple_operand_gsi (&gsi, tem, true, NULL_TREE, true,
+ GSI_SAME_STMT);
+ if (gsi_end_p (gsi))
+ gsi = gsi_last_bb (gimple_bb (stmt));
+ else
+ gsi_prev (&gsi);
+ }
for (; !gsi_end_p (gsi); gsi_prev (&gsi))
if (gimple_uid (gsi_stmt (gsi)))
break;
else
- gimple_set_uid (gsi_stmt (gsi), gimple_uid (stmt));
+ gimple_set_uid (gsi_stmt (gsi), uid);
oe->op = tem;
range->exp = exp;
range->in_p = in_p;
range->strict_overflow_p = false;
- for (range = otherrange; range < otherrange + count; range++)
+ for (i = 0; i < count; i++)
{
+ if (otherrange)
+ range = otherrange + i;
+ else
+ range = otherrangep[i];
oe = (*ops)[range->idx];
/* Now change all the other range test immediate uses, so that
those tests will be optimized away. */
struct range_entry *rangej)
{
tree lowxor, highxor, tem, exp;
- /* Check highi ^ lowi == highj ^ lowj and
- popcount (highi ^ lowi) == 1. */
+ /* Check lowi ^ lowj == highi ^ highj and
+ popcount (lowi ^ lowj) == 1. */
lowxor = fold_binary (BIT_XOR_EXPR, type, lowi, lowj);
if (lowxor == NULL_TREE || TREE_CODE (lowxor) != INTEGER_CST)
return false;
exp = fold_build2 (BIT_AND_EXPR, type, rangei->exp, tem);
lowj = fold_build2 (BIT_AND_EXPR, type, lowi, tem);
highj = fold_build2 (BIT_AND_EXPR, type, highi, tem);
- if (update_range_test (rangei, rangej, 1, opcode, ops, exp,
- rangei->in_p, lowj, highj,
+ if (update_range_test (rangei, rangej, NULL, 1, opcode, ops, exp,
+ NULL, rangei->in_p, lowj, highj,
rangei->strict_overflow_p
|| rangej->strict_overflow_p))
return true;
fold_convert (type, rangei->exp), lowi);
tem1 = fold_build2 (BIT_AND_EXPR, type, tem1, mask);
lowj = build_int_cst (type, 0);
- if (update_range_test (rangei, rangej, 1, opcode, ops, tem1,
- rangei->in_p, lowj, tem2,
+ if (update_range_test (rangei, rangej, NULL, 1, opcode, ops, tem1,
+ NULL, rangei->in_p, lowj, tem2,
rangei->strict_overflow_p
|| rangej->strict_overflow_p))
return true;
return any_changes;
}
+/* Helper function of optimize_range_tests_to_bit_test. Handle a single
+ range, EXP, LOW, HIGH, compute bit mask of bits to test and return
+ EXP on success, NULL otherwise. */
+
+static tree
+extract_bit_test_mask (tree exp, int prec, tree totallow, tree low, tree high,
+ wide_int *mask, tree *totallowp)
+{
+ tree tem = int_const_binop (MINUS_EXPR, high, low);
+ if (tem == NULL_TREE
+ || TREE_CODE (tem) != INTEGER_CST
+ || TREE_OVERFLOW (tem)
+ || tree_int_cst_sgn (tem) == -1
+ || compare_tree_int (tem, prec) != -1)
+ return NULL_TREE;
+
+ unsigned HOST_WIDE_INT max = tree_to_uhwi (tem) + 1;
+ *mask = wi::shifted_mask (0, max, false, prec);
+ if (TREE_CODE (exp) == BIT_AND_EXPR
+ && TREE_CODE (TREE_OPERAND (exp, 1)) == INTEGER_CST)
+ {
+ widest_int msk = wi::to_widest (TREE_OPERAND (exp, 1));
+ msk = wi::zext (~msk, TYPE_PRECISION (TREE_TYPE (exp)));
+ if (wi::popcount (msk) == 1
+ && wi::ltu_p (msk, prec - max))
+ {
+ *mask |= wi::shifted_mask (msk.to_uhwi (), max, false, prec);
+ max += msk.to_uhwi ();
+ exp = TREE_OPERAND (exp, 0);
+ if (integer_zerop (low)
+ && TREE_CODE (exp) == PLUS_EXPR
+ && TREE_CODE (TREE_OPERAND (exp, 1)) == INTEGER_CST)
+ {
+ tree ret = TREE_OPERAND (exp, 0);
+ STRIP_NOPS (ret);
+ widest_int bias
+ = wi::neg (wi::sext (wi::to_widest (TREE_OPERAND (exp, 1)),
+ TYPE_PRECISION (TREE_TYPE (low))));
+ tree tbias = wide_int_to_tree (TREE_TYPE (ret), bias);
+ if (totallowp)
+ {
+ *totallowp = tbias;
+ return ret;
+ }
+ else if (!tree_int_cst_lt (totallow, tbias))
+ return NULL_TREE;
+ bias = wi::to_widest (tbias);
+ bias -= wi::to_widest (totallow);
+ if (wi::ges_p (bias, 0) && wi::lts_p (bias, prec - max))
+ {
+ *mask = wi::lshift (*mask, bias);
+ return ret;
+ }
+ }
+ }
+ }
+ if (totallowp)
+ return exp;
+ if (!tree_int_cst_lt (totallow, low))
+ return exp;
+ tem = int_const_binop (MINUS_EXPR, low, totallow);
+ if (tem == NULL_TREE
+ || TREE_CODE (tem) != INTEGER_CST
+ || TREE_OVERFLOW (tem)
+ || compare_tree_int (tem, prec - max) == 1)
+ return NULL_TREE;
+
+ *mask = wi::lshift (*mask, wi::to_widest (tem));
+ return exp;
+}
+
+/* Attempt to optimize small range tests using bit test.
+ E.g.
+ X != 43 && X != 76 && X != 44 && X != 78 && X != 49
+ && X != 77 && X != 46 && X != 75 && X != 45 && X != 82
+ has been by earlier optimizations optimized into:
+ ((X - 43U) & ~32U) > 3U && X != 49 && X != 82
+ As all the 43 through 82 range is less than 64 numbers,
+ for 64-bit word targets optimize that into:
+ (X - 43U) > 40U && ((1 << (X - 43U)) & 0x8F0000004FULL) == 0 */
+
+static bool
+optimize_range_tests_to_bit_test (enum tree_code opcode, int first, int length,
+ vec<operand_entry_t> *ops,
+ struct range_entry *ranges)
+{
+ int i, j;
+ bool any_changes = false;
+ int prec = GET_MODE_BITSIZE (word_mode);
+ auto_vec<struct range_entry *, 64> candidates;
+
+ for (i = first; i < length - 2; i++)
+ {
+ tree lowi, highi, lowj, highj, type;
+
+ if (ranges[i].exp == NULL_TREE || ranges[i].in_p)
+ continue;
+ type = TREE_TYPE (ranges[i].exp);
+ if (!INTEGRAL_TYPE_P (type))
+ continue;
+ lowi = ranges[i].low;
+ if (lowi == NULL_TREE)
+ lowi = TYPE_MIN_VALUE (type);
+ highi = ranges[i].high;
+ if (highi == NULL_TREE)
+ continue;
+ wide_int mask;
+ tree exp = extract_bit_test_mask (ranges[i].exp, prec, lowi, lowi,
+ highi, &mask, &lowi);
+ if (exp == NULL_TREE)
+ continue;
+ bool strict_overflow_p = ranges[i].strict_overflow_p;
+ candidates.truncate (0);
+ int end = MIN (i + 64, length);
+ for (j = i + 1; j < end; j++)
+ {
+ tree exp2;
+ if (ranges[j].exp == NULL_TREE || ranges[j].in_p)
+ continue;
+ if (ranges[j].exp == exp)
+ ;
+ else if (TREE_CODE (ranges[j].exp) == BIT_AND_EXPR)
+ {
+ exp2 = TREE_OPERAND (ranges[j].exp, 0);
+ if (exp2 == exp)
+ ;
+ else if (TREE_CODE (exp2) == PLUS_EXPR)
+ {
+ exp2 = TREE_OPERAND (exp2, 0);
+ STRIP_NOPS (exp2);
+ if (exp2 != exp)
+ continue;
+ }
+ else
+ continue;
+ }
+ else
+ continue;
+ lowj = ranges[j].low;
+ if (lowj == NULL_TREE)
+ continue;
+ highj = ranges[j].high;
+ if (highj == NULL_TREE)
+ highj = TYPE_MAX_VALUE (type);
+ wide_int mask2;
+ exp2 = extract_bit_test_mask (ranges[j].exp, prec, lowi, lowj,
+ highj, &mask2, NULL);
+ if (exp2 != exp)
+ continue;
+ mask |= mask2;
+ strict_overflow_p |= ranges[j].strict_overflow_p;
+ candidates.safe_push (&ranges[j]);
+ }
+
+ /* If we need otherwise 3 or more comparisons, use a bit test. */
+ if (candidates.length () >= 2)
+ {
+ tree high = wide_int_to_tree (TREE_TYPE (lowi),
+ wi::to_widest (lowi)
+ + prec - 1 - wi::clz (mask));
+ operand_entry_t oe = (*ops)[ranges[i].idx];
+ tree op = oe->op;
+ gimple stmt = op ? SSA_NAME_DEF_STMT (op)
+ : last_stmt (BASIC_BLOCK_FOR_FN (cfun, oe->id));
+ location_t loc = gimple_location (stmt);
+ tree optype = op ? TREE_TYPE (op) : boolean_type_node;
+
+ /* See if it isn't cheaper to pretend the minimum value of the
+ range is 0, if maximum value is small enough.
+ We can avoid then subtraction of the minimum value, but the
+ mask constant could be perhaps more expensive. */
+ if (compare_tree_int (lowi, 0) > 0
+ && compare_tree_int (high, prec) < 0)
+ {
+ int cost_diff;
+ HOST_WIDE_INT m = tree_to_uhwi (lowi);
+ rtx reg = gen_raw_REG (word_mode, 10000);
+ bool speed_p = optimize_bb_for_speed_p (gimple_bb (stmt));
+ cost_diff = set_rtx_cost (gen_rtx_PLUS (word_mode, reg,
+ GEN_INT (-m)), speed_p);
+ rtx r = immed_wide_int_const (mask, word_mode);
+ cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r),
+ speed_p);
+ r = immed_wide_int_const (wi::lshift (mask, m), word_mode);
+ cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r),
+ speed_p);
+ if (cost_diff > 0)
+ {
+ mask = wi::lshift (mask, m);
+ lowi = build_zero_cst (TREE_TYPE (lowi));
+ }
+ }
+
+ tree tem = build_range_check (loc, optype, unshare_expr (exp),
+ false, lowi, high);
+ if (tem == NULL_TREE || is_gimple_val (tem))
+ continue;
+ tree etype = unsigned_type_for (TREE_TYPE (exp));
+ exp = fold_build2_loc (loc, MINUS_EXPR, etype,
+ fold_convert_loc (loc, etype, exp),
+ fold_convert_loc (loc, etype, lowi));
+ exp = fold_convert_loc (loc, integer_type_node, exp);
+ tree word_type = lang_hooks.types.type_for_mode (word_mode, 1);
+ exp = fold_build2_loc (loc, LSHIFT_EXPR, word_type,
+ build_int_cst (word_type, 1), exp);
+ exp = fold_build2_loc (loc, BIT_AND_EXPR, word_type, exp,
+ wide_int_to_tree (word_type, mask));
+ exp = fold_build2_loc (loc, EQ_EXPR, optype, exp,
+ build_zero_cst (word_type));
+ if (is_gimple_val (exp))
+ continue;
+
+ /* The shift might have undefined behavior if TEM is true,
+ but reassociate_bb isn't prepared to have basic blocks
+ split when it is running. So, temporarily emit a code
+ with BIT_IOR_EXPR instead of &&, and fix it up in
+ branch_fixup. */
+ gimple_seq seq;
+ tem = force_gimple_operand (tem, &seq, true, NULL_TREE);
+ gcc_assert (TREE_CODE (tem) == SSA_NAME);
+ gimple_set_visited (SSA_NAME_DEF_STMT (tem), true);
+ gimple_seq seq2;
+ exp = force_gimple_operand (exp, &seq2, true, NULL_TREE);
+ gimple_seq_add_seq_without_update (&seq, seq2);
+ gcc_assert (TREE_CODE (exp) == SSA_NAME);
+ gimple_set_visited (SSA_NAME_DEF_STMT (exp), true);
+ gimple g = gimple_build_assign (make_ssa_name (optype),
+ BIT_IOR_EXPR, tem, exp);
+ gimple_set_location (g, loc);
+ gimple_seq_add_stmt_without_update (&seq, g);
+ exp = gimple_assign_lhs (g);
+ tree val = build_zero_cst (optype);
+ if (update_range_test (&ranges[i], NULL, candidates.address (),
+ candidates.length (), opcode, ops, exp,
+ seq, false, val, val, strict_overflow_p))
+ {
+ any_changes = true;
+ reassoc_branch_fixups.safe_push (tem);
+ }
+ else
+ gimple_seq_discard (seq);
+ }
+ }
+ return any_changes;
+}
+
/* Optimize range tests, similarly how fold_range_test optimizes
it on trees. The tree code for the binary
operation between all the operands is OPCODE.
if (j == i + 1)
continue;
- if (update_range_test (ranges + i, ranges + i + 1, j - i - 1, opcode,
- ops, ranges[i].exp, in_p, low, high,
- strict_overflow_p))
+ if (update_range_test (ranges + i, ranges + i + 1, NULL, j - i - 1,
+ opcode, ops, ranges[i].exp, NULL, in_p,
+ low, high, strict_overflow_p))
{
i = j - 1;
any_changes = true;
if (BRANCH_COST (optimize_function_for_speed_p (cfun), false) >= 2)
any_changes |= optimize_range_tests_1 (opcode, first, length, false,
ops, ranges);
+ if (lshift_cheap_p (optimize_function_for_speed_p (cfun)))
+ any_changes |= optimize_range_tests_to_bit_test (opcode, first, length,
+ ops, ranges);
if (any_changes && opcode != ERROR_MARK)
{
edge_iterator ei, ei2;
edge e, e2;
gimple stmt;
- gimple_stmt_iterator gsi;
+ gphi_iterator gsi;
bool other_edge_seen = false;
bool is_cond;
e2 = find_edge (test_bb, *other_bb);
for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple phi = gsi_stmt (gsi);
+ gphi *phi = gsi.phi ();
/* If both BB and TEST_BB end with GIMPLE_COND, all PHI arguments
corresponding to BB and TEST_BB predecessor must be the same. */
if (!operand_equal_p (gimple_phi_arg_def (phi, e->dest_idx),
&& !get_ops (rhs[i], code, ops, loop)
&& has_single_use (rhs[i]))
{
- operand_entry_t oe = (operand_entry_t) pool_alloc (operand_entry_pool);
+ operand_entry_t oe = operand_entry_pool.allocate ();
oe->op = rhs[i];
oe->rank = code;
&& (rhs[2] != rhs[1] || rhs[3] != rhs[0]))
{
gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
- var = make_ssa_name (TREE_TYPE (var), NULL);
- gimple g = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt),
- var, rhs[2], rhs[3]);
+ var = make_ssa_name (TREE_TYPE (var));
+ gassign *g = gimple_build_assign (var, gimple_assign_rhs_code (stmt),
+ rhs[2], rhs[3]);
gimple_set_uid (g, gimple_uid (stmt));
gimple_set_visited (g, true);
gsi_insert_before (&gsi, g, GSI_SAME_STMT);
&& has_single_use (rhs))
{
/* Otherwise, push the _234 range test itself. */
- operand_entry_t oe
- = (operand_entry_t) pool_alloc (operand_entry_pool);
+ operand_entry_t oe = operand_entry_pool.allocate ();
oe->op = rhs;
oe->rank = code;
loop_containing_stmt (stmt))))
{
/* Or push the GIMPLE_COND stmt itself. */
- operand_entry_t oe
- = (operand_entry_t) pool_alloc (operand_entry_pool);
+ operand_entry_t oe = operand_entry_pool.allocate ();
oe->op = NULL;
oe->rank = (e->flags & EDGE_TRUE_VALUE)
{
gcc_assert (bb == last_bb);
tree lhs = gimple_assign_lhs (cast_stmt);
- tree new_lhs = make_ssa_name (TREE_TYPE (lhs), NULL);
+ tree new_lhs = make_ssa_name (TREE_TYPE (lhs));
enum tree_code rhs_code
= gimple_assign_rhs_code (cast_stmt);
- gimple g;
+ gassign *g;
if (is_gimple_min_invariant (new_op))
{
new_op = fold_convert (TREE_TYPE (lhs), new_op);
g = gimple_build_assign (new_lhs, new_op);
}
else
- g = gimple_build_assign_with_ops (rhs_code, new_lhs,
- new_op, NULL_TREE);
+ g = gimple_build_assign (new_lhs, rhs_code, new_op);
gimple_stmt_iterator gsi = gsi_for_stmt (cast_stmt);
gimple_set_uid (g, gimple_uid (cast_stmt));
gimple_set_visited (g, true);
&& bbinfo[idx].op == NULL_TREE
&& ops[bbinfo[idx].first_idx]->op != NULL_TREE)
{
- stmt = last_stmt (bb);
+ gcond *cond_stmt = as_a <gcond *> (last_stmt (bb));
if (integer_zerop (ops[bbinfo[idx].first_idx]->op))
- gimple_cond_make_false (stmt);
+ gimple_cond_make_false (cond_stmt);
else if (integer_onep (ops[bbinfo[idx].first_idx]->op))
- gimple_cond_make_true (stmt);
+ gimple_cond_make_true (cond_stmt);
else
{
- gimple_cond_set_code (stmt, NE_EXPR);
- gimple_cond_set_lhs (stmt, ops[bbinfo[idx].first_idx]->op);
- gimple_cond_set_rhs (stmt, boolean_false_node);
+ gimple_cond_set_code (cond_stmt, NE_EXPR);
+ gimple_cond_set_lhs (cond_stmt,
+ ops[bbinfo[idx].first_idx]->op);
+ gimple_cond_set_rhs (cond_stmt, boolean_false_node);
}
- update_stmt (stmt);
+ update_stmt (cond_stmt);
}
if (bb == first_bb)
break;
is_phi_for_stmt (gimple stmt, tree operand)
{
gimple def_stmt;
+ gphi *def_phi;
tree lhs;
use_operand_p arg_p;
ssa_op_iter i;
lhs = gimple_assign_lhs (stmt);
def_stmt = SSA_NAME_DEF_STMT (operand);
- if (gimple_code (def_stmt) != GIMPLE_PHI)
+ def_phi = dyn_cast <gphi *> (def_stmt);
+ if (!def_phi)
return false;
- FOR_EACH_PHI_ARG (arg_p, def_stmt, i, SSA_OP_USE)
+ FOR_EACH_PHI_ARG (arg_p, def_phi, i, SSA_OP_USE)
if (lhs == USE_FROM_PTR (arg_p))
return true;
return false;
/* The final recursion case for this function is that you have
exactly two operations left.
- If we had one exactly one op in the entire list to start with, we
+ If we had exactly one op in the entire list to start with, we
would have never called this function, and the tail recursion
rewrites them one at a time. */
if (opindex + 2 == ops.length ())
print_gimple_stmt (dump_file, stmt, 0, 0);
}
- if (changed)
+ /* Even when changed is false, reassociation could have e.g. removed
+ some redundant operations, so unless we are just swapping the
+ arguments or unless there is no change at all (then we just
+ return lhs), force creation of a new SSA_NAME. */
+ if (changed || ((rhs1 != oe2->op || rhs2 != oe1->op) && opindex))
{
gimple insert_point = find_insert_point (stmt, oe1->op, oe2->op);
- lhs = make_ssa_name (TREE_TYPE (lhs), NULL);
+ lhs = make_ssa_name (TREE_TYPE (lhs));
stmt
- = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt),
- lhs, oe1->op, oe2->op);
+ = gimple_build_assign (lhs, gimple_assign_rhs_code (stmt),
+ oe1->op, oe2->op);
gimple_set_uid (stmt, uid);
gimple_set_visited (stmt, true);
if (insert_point == gsi_stmt (gsi))
unsigned int uid = gimple_uid (stmt);
gimple insert_point = find_insert_point (stmt, new_rhs1, oe->op);
- lhs = make_ssa_name (TREE_TYPE (lhs), NULL);
- stmt = gimple_build_assign_with_ops (gimple_assign_rhs_code (stmt),
- lhs, new_rhs1, oe->op);
+ lhs = make_ssa_name (TREE_TYPE (lhs));
+ stmt = gimple_build_assign (lhs, gimple_assign_rhs_code (stmt),
+ new_rhs1, oe->op);
gimple_set_uid (stmt, uid);
gimple_set_visited (stmt, true);
if (insert_point == gsi_stmt (gsi))
static int
get_reassociation_width (int ops_num, enum tree_code opc,
- enum machine_mode mode)
+ machine_mode mode)
{
int param_width = PARAM_VALUE (PARAM_TREE_REASSOC_WIDTH);
int width;
parallel. */
static void
-rewrite_expr_tree_parallel (gimple stmt, int width,
+rewrite_expr_tree_parallel (gassign *stmt, int width,
vec<operand_entry_t> ops)
{
enum tree_code opcode = gimple_assign_rhs_code (stmt);
gsi = gsi_for_stmt (stmt);
gimple_assign_set_rhs2 (stmt, gimple_assign_rhs1 (binrhs));
- binrhs = gimple_build_assign_with_ops (gimple_assign_rhs_code (binrhs),
- make_ssa_name (TREE_TYPE (lhs), NULL),
- gimple_assign_lhs (binlhs),
- gimple_assign_rhs2 (binrhs));
+ binrhs = gimple_build_assign (make_ssa_name (TREE_TYPE (lhs)),
+ gimple_assign_rhs_code (binrhs),
+ gimple_assign_lhs (binlhs),
+ gimple_assign_rhs2 (binrhs));
gimple_assign_set_rhs1 (stmt, gimple_assign_lhs (binrhs));
gsi_insert_before (&gsi, binrhs, GSI_SAME_STMT);
gimple_set_uid (binrhs, gimple_uid (stmt));
rhs2 = negate_value (rhs2, &gsi);
gsi = gsi_for_stmt (negatedefstmt);
- lhs = make_ssa_name (TREE_TYPE (lhs), NULL);
+ lhs = make_ssa_name (TREE_TYPE (lhs));
gimple_set_visited (negatedefstmt, true);
- g = gimple_build_assign_with_ops (PLUS_EXPR, lhs, rhs1, rhs2);
+ g = gimple_build_assign (lhs, PLUS_EXPR, rhs1, rhs2);
gimple_set_uid (g, gimple_uid (negatedefstmt));
gsi_insert_before (&gsi, g, GSI_SAME_STMT);
return lhs;
switch (DECL_FUNCTION_CODE (fndecl))
{
CASE_FLT_FN (BUILT_IN_POW):
+ if (flag_errno_math)
+ return false;
+
*base = gimple_call_arg (stmt, 0);
arg1 = gimple_call_arg (stmt, 1);
if (!binlhsisreassoc)
{
- tree temp;
-
/* If this is not a associative operation like division, give up. */
if (!is_associative)
{
/* We want to make it so the lhs is always the reassociative op,
so swap. */
- temp = binlhs;
- binlhs = binrhs;
- binrhs = temp;
+ std::swap (binlhs, binrhs);
}
else if (binrhsisreassoc)
{
tree b = gimple_assign_rhs2 (user);
gimple_stmt_iterator gsi = gsi_for_stmt (feed);
gimple_stmt_iterator gsi2 = gsi_for_stmt (user);
- tree x = make_ssa_name (TREE_TYPE (gimple_assign_lhs (feed)), NULL);
- gimple g = gimple_build_assign_with_ops (PLUS_EXPR, x, a, b);
+ tree x = make_ssa_name (TREE_TYPE (gimple_assign_lhs (feed)));
+ gimple g = gimple_build_assign (x, PLUS_EXPR, a, b);
gsi_insert_before (&gsi2, g, GSI_SAME_STMT);
- gimple_assign_set_rhs_with_ops (&gsi2, NEGATE_EXPR, x, NULL);
+ gimple_assign_set_rhs_with_ops (&gsi2, NEGATE_EXPR, x);
user = gsi_stmt (gsi2);
update_stmt (user);
reassoc_remove_stmt (&gsi);
if (elt < vec_len - 1)
fputs (" * ", dump_file);
}
- fprintf (dump_file, ")^"HOST_WIDE_INT_PRINT_DEC"\n",
+ fprintf (dump_file, ")^" HOST_WIDE_INT_PRINT_DEC"\n",
power);
}
}
if (elt < vec_len - 1)
fputs (" * ", dump_file);
}
- fprintf (dump_file, ")^"HOST_WIDE_INT_PRINT_DEC"\n", power);
+ fprintf (dump_file, ")^" HOST_WIDE_INT_PRINT_DEC"\n", power);
}
reassociate_stats.pows_created++;
op2 = rf2->repr;
target_ssa = make_temp_ssa_name (type, NULL, "reassocpow");
- mul_stmt = gimple_build_assign_with_ops (MULT_EXPR,
- target_ssa,
- op1, op2);
+ mul_stmt = gimple_build_assign (target_ssa, MULT_EXPR,
+ op1, op2);
gimple_set_location (mul_stmt, gimple_location (stmt));
gsi_insert_before (&gsi, mul_stmt, GSI_SAME_STMT);
rf1->repr = target_ssa;
if (result)
{
tree new_result = make_temp_ssa_name (type, NULL, "reassocpow");
- mul_stmt = gimple_build_assign_with_ops (MULT_EXPR, new_result,
- result, iter_result);
+ mul_stmt = gimple_build_assign (new_result, MULT_EXPR,
+ result, iter_result);
gimple_set_location (mul_stmt, gimple_location (stmt));
gsi_insert_before (&gsi, mul_stmt, GSI_SAME_STMT);
gimple_set_visited (mul_stmt, true);
}
else
{
- enum machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
+ machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
int ops_num = ops.length ();
int width = get_reassociation_width (ops_num, rhs_code, mode);
tree new_lhs = lhs;
if (width > 1
&& ops.length () > 3)
- rewrite_expr_tree_parallel (stmt, width, ops);
+ rewrite_expr_tree_parallel (as_a <gassign *> (stmt),
+ width, ops);
else
{
/* When there are three operands left, we want
update_stmt (lhs_stmt);
if (lhs != new_lhs)
target_ssa = new_lhs;
- mul_stmt = gimple_build_assign_with_ops (MULT_EXPR, lhs,
- powi_result,
- target_ssa);
+ mul_stmt = gimple_build_assign (lhs, MULT_EXPR,
+ powi_result, target_ssa);
gimple_set_location (mul_stmt, gimple_location (stmt));
gsi_insert_after (&gsi, mul_stmt, GSI_NEW_STMT);
}
reassociate_bb (son);
}
+/* Add jumps around shifts for range tests turned into bit tests.
+ For each SSA_NAME VAR we have code like:
+ VAR = ...; // final stmt of range comparison
+ // bit test here...;
+ OTHERVAR = ...; // final stmt of the bit test sequence
+ RES = VAR | OTHERVAR;
+ Turn the above into:
+ VAR = ...;
+ if (VAR != 0)
+ goto <l3>;
+ else
+ goto <l2>;
+ <l2>:
+ // bit test here...;
+ OTHERVAR = ...;
+ <l3>:
+ # RES = PHI<1(l1), OTHERVAR(l2)>; */
+
+static void
+branch_fixup (void)
+{
+ tree var;
+ unsigned int i;
+
+ FOR_EACH_VEC_ELT (reassoc_branch_fixups, i, var)
+ {
+ gimple def_stmt = SSA_NAME_DEF_STMT (var);
+ gimple use_stmt;
+ use_operand_p use;
+ bool ok = single_imm_use (var, &use, &use_stmt);
+ gcc_assert (ok
+ && is_gimple_assign (use_stmt)
+ && gimple_assign_rhs_code (use_stmt) == BIT_IOR_EXPR
+ && gimple_bb (def_stmt) == gimple_bb (use_stmt));
+
+ basic_block cond_bb = gimple_bb (def_stmt);
+ basic_block then_bb = split_block (cond_bb, def_stmt)->dest;
+ basic_block merge_bb = split_block (then_bb, use_stmt)->dest;
+
+ gimple_stmt_iterator gsi = gsi_for_stmt (def_stmt);
+ gimple g = gimple_build_cond (NE_EXPR, var,
+ build_zero_cst (TREE_TYPE (var)),
+ NULL_TREE, NULL_TREE);
+ location_t loc = gimple_location (use_stmt);
+ gimple_set_location (g, loc);
+ gsi_insert_after (&gsi, g, GSI_NEW_STMT);
+
+ edge etrue = make_edge (cond_bb, merge_bb, EDGE_TRUE_VALUE);
+ etrue->probability = REG_BR_PROB_BASE / 2;
+ etrue->count = cond_bb->count / 2;
+ edge efalse = find_edge (cond_bb, then_bb);
+ efalse->flags = EDGE_FALSE_VALUE;
+ efalse->probability -= etrue->probability;
+ efalse->count -= etrue->count;
+ then_bb->count -= etrue->count;
+
+ tree othervar = NULL_TREE;
+ if (gimple_assign_rhs1 (use_stmt) == var)
+ othervar = gimple_assign_rhs2 (use_stmt);
+ else if (gimple_assign_rhs2 (use_stmt) == var)
+ othervar = gimple_assign_rhs1 (use_stmt);
+ else
+ gcc_unreachable ();
+ tree lhs = gimple_assign_lhs (use_stmt);
+ gphi *phi = create_phi_node (lhs, merge_bb);
+ add_phi_arg (phi, build_one_cst (TREE_TYPE (lhs)), etrue, loc);
+ add_phi_arg (phi, othervar, single_succ_edge (then_bb), loc);
+ gsi = gsi_for_stmt (use_stmt);
+ gsi_remove (&gsi, true);
+
+ set_immediate_dominator (CDI_DOMINATORS, merge_bb, cond_bb);
+ set_immediate_dominator (CDI_POST_DOMINATORS, cond_bb, merge_bb);
+ }
+ reassoc_branch_fixups.release ();
+}
+
void dump_ops_vector (FILE *file, vec<operand_entry_t> ops);
void debug_ops_vector (vec<operand_entry_t> ops);
memset (&reassociate_stats, 0, sizeof (reassociate_stats));
- operand_entry_pool = create_alloc_pool ("operand entry pool",
- sizeof (struct operand_entry), 30);
next_operand_entry_id = 0;
/* Reverse RPO (Reverse Post Order) will give us something where
reassociate_stats.pows_created);
delete operand_rank;
- free_alloc_pool (operand_entry_pool);
+ operand_entry_pool.release ();
free (bb_rank);
plus_negates.release ();
free_dominance_info (CDI_POST_DOMINATORS);
do_reassoc ();
repropagate_negates ();
+ branch_fixup ();
fini_reassoc ();
return 0;