/* Reassociation for trees.
- Copyright (C) 2005, 2007, 2008, 2009, 2010, 2011
- 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 "hash-set.h"
+#include "machmode.h"
+#include "vec.h"
+#include "double-int.h"
+#include "input.h"
+#include "alias.h"
+#include "symtab.h"
+#include "wide-int.h"
+#include "inchash.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 "tree-flow.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 "gimple-ssa.h"
+#include "tree-cfg.h"
+#include "tree-phinodes.h"
+#include "ssa-iterators.h"
+#include "stringpool.h"
+#include "tree-ssanames.h"
+#include "tree-ssa-loop-niter.h"
+#include "tree-ssa-loop.h"
+#include "hashtab.h"
+#include "flags.h"
+#include "statistics.h"
+#include "real.h"
+#include "fixed-value.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 "tree-iterator.h"
#include "tree-pass.h"
#include "alloc-pool.h"
-#include "vec.h"
#include "langhooks.h"
-#include "pointer-set.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
static long *bb_rank;
/* Operand->rank hashtable. */
-static struct pointer_map_t *operand_rank;
+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);
+
+/* Wrapper around gsi_remove, which adjusts gimple_uid of debug stmts
+ possibly added by gsi_remove. */
+
+bool
+reassoc_remove_stmt (gimple_stmt_iterator *gsi)
+{
+ gimple stmt = gsi_stmt (*gsi);
+ if (!MAY_HAVE_DEBUG_STMTS || gimple_code (stmt) == GIMPLE_PHI)
+ return gsi_remove (gsi, true);
+
+ gimple_stmt_iterator prev = *gsi;
+ gsi_prev (&prev);
+ unsigned uid = gimple_uid (stmt);
+ basic_block bb = gimple_bb (stmt);
+ bool ret = gsi_remove (gsi, true);
+ if (!gsi_end_p (prev))
+ gsi_next (&prev);
+ else
+ prev = gsi_start_bb (bb);
+ gimple end_stmt = gsi_stmt (*gsi);
+ while ((stmt = gsi_stmt (prev)) != end_stmt)
+ {
+ gcc_assert (stmt && is_gimple_debug (stmt) && gimple_uid (stmt) == 0);
+ gimple_set_uid (stmt, uid);
+ gsi_next (&prev);
+ }
+ return ret;
+}
/* Bias amount for loop-carried phis. We want this to be larger than
the depth of any reassociation tree we can see, but not larger than
static inline long
find_operand_rank (tree e)
{
- void **slot = pointer_map_contains (operand_rank, e);
- return slot ? (long) (intptr_t) *slot : -1;
+ long *slot = operand_rank->get (e);
+ return slot ? *slot : -1;
}
/* Insert {E,RANK} into the operand rank hashtable. */
static inline void
insert_operand_rank (tree e, long rank)
{
- void **slot;
gcc_assert (rank > 0);
- slot = pointer_map_insert (operand_rank, e);
- gcc_assert (!*slot);
- *slot = (void *) (intptr_t) rank;
+ gcc_assert (!operand_rank->put (e, rank));
}
/* Given an expression E, return the rank of the expression. */
return 0;
}
-DEF_VEC_P(operand_entry_t);
-DEF_VEC_ALLOC_P(operand_entry_t, heap);
/* We want integer ones to end up last no matter what, since they are
the ones we can do the most with. */
}
/* Lastly, make sure the versions that are the same go next to each
- other. We use SSA_NAME_VERSION because it's stable. */
+ other. */
if ((oeb->rank - oea->rank == 0)
&& TREE_CODE (oea->op) == SSA_NAME
&& TREE_CODE (oeb->op) == SSA_NAME)
{
+ /* As SSA_NAME_VERSION is assigned pretty randomly, because we reuse
+ versions of removed SSA_NAMEs, so if possible, prefer to sort
+ based on basic block and gimple_uid of the SSA_NAME_DEF_STMT.
+ See PR60418. */
+ if (!SSA_NAME_IS_DEFAULT_DEF (oea->op)
+ && !SSA_NAME_IS_DEFAULT_DEF (oeb->op)
+ && SSA_NAME_VERSION (oeb->op) != SSA_NAME_VERSION (oea->op))
+ {
+ gimple stmta = SSA_NAME_DEF_STMT (oea->op);
+ gimple stmtb = SSA_NAME_DEF_STMT (oeb->op);
+ basic_block bba = gimple_bb (stmta);
+ basic_block bbb = gimple_bb (stmtb);
+ if (bbb != bba)
+ {
+ if (bb_rank[bbb->index] != bb_rank[bba->index])
+ return bb_rank[bbb->index] - bb_rank[bba->index];
+ }
+ else
+ {
+ bool da = reassoc_stmt_dominates_stmt_p (stmta, stmtb);
+ bool db = reassoc_stmt_dominates_stmt_p (stmtb, stmta);
+ if (da != db)
+ return da ? 1 : -1;
+ }
+ }
+
if (SSA_NAME_VERSION (oeb->op) != SSA_NAME_VERSION (oea->op))
return SSA_NAME_VERSION (oeb->op) - SSA_NAME_VERSION (oea->op);
else
/* Add an operand entry to *OPS for the tree operand OP. */
static void
-add_to_ops_vec (VEC(operand_entry_t, heap) **ops, tree op)
+add_to_ops_vec (vec<operand_entry_t> *ops, tree op)
{
operand_entry_t oe = (operand_entry_t) pool_alloc (operand_entry_pool);
oe->rank = get_rank (op);
oe->id = next_operand_entry_id++;
oe->count = 1;
- VEC_safe_push (operand_entry_t, heap, *ops, oe);
+ ops->safe_push (oe);
}
/* Add an operand entry to *OPS for the tree operand OP with repeat
count REPEAT. */
static void
-add_repeat_to_ops_vec (VEC(operand_entry_t, heap) **ops, tree 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);
oe->rank = get_rank (op);
oe->id = next_operand_entry_id++;
oe->count = repeat;
- VEC_safe_push (operand_entry_t, heap, *ops, oe);
+ ops->safe_push (oe);
reassociate_stats.pows_encountered++;
}
static bool
eliminate_duplicate_pair (enum tree_code opcode,
- VEC (operand_entry_t, heap) **ops,
+ vec<operand_entry_t> *ops,
bool *all_done,
unsigned int i,
operand_entry_t curr,
print_generic_stmt (dump_file, last->op, 0);
}
- VEC_ordered_remove (operand_entry_t, *ops, i);
+ ops->ordered_remove (i);
reassociate_stats.ops_eliminated ++;
return true;
reassociate_stats.ops_eliminated += 2;
- if (VEC_length (operand_entry_t, *ops) == 2)
+ if (ops->length () == 2)
{
- VEC_free (operand_entry_t, heap, *ops);
- *ops = NULL;
+ ops->create (0);
add_to_ops_vec (ops, build_zero_cst (TREE_TYPE (last->op)));
*all_done = true;
}
else
{
- VEC_ordered_remove (operand_entry_t, *ops, i-1);
- VEC_ordered_remove (operand_entry_t, *ops, i-1);
+ ops->ordered_remove (i-1);
+ ops->ordered_remove (i-1);
}
return true;
return false;
}
-static VEC(tree, heap) *plus_negates;
+static vec<tree> plus_negates;
/* If OPCODE is PLUS_EXPR, CURR->OP is a negate expression or a bitwise not
expression, look in OPS for a corresponding positive operation to cancel
static bool
eliminate_plus_minus_pair (enum tree_code opcode,
- VEC (operand_entry_t, heap) **ops,
+ vec<operand_entry_t> *ops,
unsigned int currindex,
operand_entry_t curr)
{
one, we can stop. */
for (i = currindex + 1;
- VEC_iterate (operand_entry_t, *ops, i, oe)
+ ops->iterate (i, &oe)
&& oe->rank >= curr->rank - 1 ;
i++)
{
fprintf (dump_file, " -> 0\n");
}
- VEC_ordered_remove (operand_entry_t, *ops, i);
+ ops->ordered_remove (i);
add_to_ops_vec (ops, build_zero_cst (TREE_TYPE (oe->op)));
- VEC_ordered_remove (operand_entry_t, *ops, currindex);
+ ops->ordered_remove (currindex);
reassociate_stats.ops_eliminated ++;
return true;
fprintf (dump_file, " -> -1\n");
}
- VEC_ordered_remove (operand_entry_t, *ops, i);
+ ops->ordered_remove (i);
add_to_ops_vec (ops, build_int_cst_type (op_type, -1));
- VEC_ordered_remove (operand_entry_t, *ops, currindex);
+ ops->ordered_remove (currindex);
reassociate_stats.ops_eliminated ++;
return true;
/* CURR->OP is a negate expr in a plus expr: save it for later
inspection in repropagate_negates(). */
if (negateop != NULL_TREE)
- VEC_safe_push (tree, heap, plus_negates, curr->op);
+ plus_negates.safe_push (curr->op);
return false;
}
static bool
eliminate_not_pairs (enum tree_code opcode,
- VEC (operand_entry_t, heap) **ops,
+ vec<operand_entry_t> *ops,
unsigned int currindex,
operand_entry_t curr)
{
one, we can stop. */
for (i = currindex + 1;
- VEC_iterate (operand_entry_t, *ops, i, oe)
+ ops->iterate (i, &oe)
&& oe->rank >= curr->rank - 1;
i++)
{
if (opcode == BIT_AND_EXPR)
oe->op = build_zero_cst (TREE_TYPE (oe->op));
else if (opcode == BIT_IOR_EXPR)
- oe->op = build_low_bits_mask (TREE_TYPE (oe->op),
- TYPE_PRECISION (TREE_TYPE (oe->op)));
-
- reassociate_stats.ops_eliminated
- += VEC_length (operand_entry_t, *ops) - 1;
- VEC_free (operand_entry_t, heap, *ops);
- *ops = NULL;
- VEC_safe_push (operand_entry_t, heap, *ops, oe);
+ oe->op = build_all_ones_cst (TREE_TYPE (oe->op));
+
+ reassociate_stats.ops_eliminated += ops->length () - 1;
+ ops->truncate (0);
+ ops->quick_push (oe);
return true;
}
}
static void
eliminate_using_constants (enum tree_code opcode,
- VEC(operand_entry_t, heap) **ops)
+ vec<operand_entry_t> *ops)
{
- operand_entry_t oelast = VEC_last (operand_entry_t, *ops);
+ operand_entry_t oelast = ops->last ();
tree type = TREE_TYPE (oelast->op);
if (oelast->rank == 0
case BIT_AND_EXPR:
if (integer_zerop (oelast->op))
{
- if (VEC_length (operand_entry_t, *ops) != 1)
+ if (ops->length () != 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Found & 0, removing all other ops\n");
- reassociate_stats.ops_eliminated
- += VEC_length (operand_entry_t, *ops) - 1;
+ reassociate_stats.ops_eliminated += ops->length () - 1;
- VEC_free (operand_entry_t, heap, *ops);
- *ops = NULL;
- VEC_safe_push (operand_entry_t, heap, *ops, oelast);
+ ops->truncate (0);
+ ops->quick_push (oelast);
return;
}
}
else if (integer_all_onesp (oelast->op))
{
- if (VEC_length (operand_entry_t, *ops) != 1)
+ if (ops->length () != 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Found & -1, removing\n");
- VEC_pop (operand_entry_t, *ops);
+ ops->pop ();
reassociate_stats.ops_eliminated++;
}
}
case BIT_IOR_EXPR:
if (integer_all_onesp (oelast->op))
{
- if (VEC_length (operand_entry_t, *ops) != 1)
+ if (ops->length () != 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Found | -1, removing all other ops\n");
- reassociate_stats.ops_eliminated
- += VEC_length (operand_entry_t, *ops) - 1;
+ reassociate_stats.ops_eliminated += ops->length () - 1;
- VEC_free (operand_entry_t, heap, *ops);
- *ops = NULL;
- VEC_safe_push (operand_entry_t, heap, *ops, oelast);
+ ops->truncate (0);
+ ops->quick_push (oelast);
return;
}
}
else if (integer_zerop (oelast->op))
{
- if (VEC_length (operand_entry_t, *ops) != 1)
+ if (ops->length () != 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Found | 0, removing\n");
- VEC_pop (operand_entry_t, *ops);
+ ops->pop ();
reassociate_stats.ops_eliminated++;
}
}
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 (VEC_length (operand_entry_t, *ops) != 1)
+ if (ops->length () != 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Found * 0, removing all other ops\n");
- reassociate_stats.ops_eliminated
- += VEC_length (operand_entry_t, *ops) - 1;
- VEC_free (operand_entry_t, heap, *ops);
- *ops = NULL;
- VEC_safe_push (operand_entry_t, heap, *ops, oelast);
+ reassociate_stats.ops_eliminated += ops->length () - 1;
+ ops->truncate (1);
+ ops->quick_push (oelast);
return;
}
}
else if (integer_onep (oelast->op)
|| (FLOAT_TYPE_P (type)
- && !HONOR_SNANS (TYPE_MODE (type))
+ && !HONOR_SNANS (type)
&& real_onep (oelast->op)))
{
- if (VEC_length (operand_entry_t, *ops) != 1)
+ if (ops->length () != 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Found * 1, removing\n");
- VEC_pop (operand_entry_t, *ops);
+ ops->pop ();
reassociate_stats.ops_eliminated++;
return;
}
&& fold_real_zero_addition_p (type, oelast->op,
opcode == MINUS_EXPR)))
{
- if (VEC_length (operand_entry_t, *ops) != 1)
+ if (ops->length () != 1)
{
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Found [|^+] 0, removing\n");
- VEC_pop (operand_entry_t, *ops);
+ ops->pop ();
reassociate_stats.ops_eliminated++;
return;
}
}
-static void linearize_expr_tree (VEC(operand_entry_t, heap) **, gimple,
+static void linearize_expr_tree (vec<operand_entry_t> *, gimple,
bool, bool);
/* Structure for tracking and counting operands. */
tree op;
} oecount;
-DEF_VEC_O(oecount);
-DEF_VEC_ALLOC_O(oecount,heap);
/* The heap for the oecount hashtable and the sorted list of operands. */
-static VEC (oecount, heap) *cvec;
+static vec<oecount> cvec;
+
+
+/* Oecount hashtable helpers. */
+
+struct oecount_hasher
+{
+ 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 &) {}
+};
/* Hash function for oecount. */
-static hashval_t
-oecount_hash (const void *p)
+inline hashval_t
+oecount_hasher::hash (const value_type &p)
{
- const oecount *c = VEC_index (oecount, cvec, (size_t)p - 42);
+ const oecount *c = &cvec[p - 42];
return htab_hash_pointer (c->op) ^ (hashval_t)c->oecode;
}
/* Comparison function for oecount. */
-static int
-oecount_eq (const void *p1, const void *p2)
+inline bool
+oecount_hasher::equal (const value_type &p1, const compare_type &p2)
{
- const oecount *c1 = VEC_index (oecount, cvec, (size_t)p1 - 42);
- const oecount *c2 = VEC_index (oecount, cvec, (size_t)p2 - 42);
+ const oecount *c1 = &cvec[p1 - 42];
+ const oecount *c2 = &cvec[p2 - 42];
return (c1->oecode == c2->oecode
&& c1->op == c2->op);
}
arg1 = gimple_call_arg (stmt, 1);
c = TREE_REAL_CST (arg1);
power = real_to_integer (&c) - 1;
- real_from_integer (&cint, VOIDmode, power, 0, 0);
+ real_from_integer (&cint, VOIDmode, power, SIGNED);
gimple_call_set_arg (stmt, 1, build_real (TREE_TYPE (arg1), cint));
return power;
if (TREE_CODE (op) != SSA_NAME)
update_stmt (use_stmt);
gsi = gsi_for_stmt (stmt);
- gsi_remove (&gsi, true);
+ unlink_stmt_vdef (stmt);
+ reassoc_remove_stmt (&gsi);
release_defs (stmt);
-
- if (is_gimple_call (stmt))
- unlink_stmt_vdef (stmt);
}
/* Walks the linear chain with result *DEF searching for an operation
the operand might be hiding in the rightmost one. */
if (opcode == MULT_EXPR
&& gimple_assign_rhs_code (stmt) == opcode
- && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
+ && TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME
+ && has_single_use (gimple_assign_rhs2 (stmt)))
{
gimple stmt2 = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
if (stmt_is_power_of_op (stmt2, op))
while (1);
}
+/* Returns true if statement S1 dominates statement S2. Like
+ stmt_dominates_stmt_p, but uses stmt UIDs to optimize. */
+
+static bool
+reassoc_stmt_dominates_stmt_p (gimple s1, gimple s2)
+{
+ basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
+
+ /* If bb1 is NULL, it should be a GIMPLE_NOP def stmt of an (D)
+ SSA_NAME. Assume it lives at the beginning of function and
+ thus dominates everything. */
+ if (!bb1 || s1 == s2)
+ return true;
+
+ /* If bb2 is NULL, it doesn't dominate any stmt with a bb. */
+ if (!bb2)
+ return false;
+
+ if (bb1 == bb2)
+ {
+ /* PHIs in the same basic block are assumed to be
+ executed all in parallel, if only one stmt is a PHI,
+ it dominates the other stmt in the same basic block. */
+ if (gimple_code (s1) == GIMPLE_PHI)
+ return true;
+
+ if (gimple_code (s2) == GIMPLE_PHI)
+ return false;
+
+ gcc_assert (gimple_uid (s1) && gimple_uid (s2));
+
+ if (gimple_uid (s1) < gimple_uid (s2))
+ return true;
+
+ if (gimple_uid (s1) > gimple_uid (s2))
+ return false;
+
+ gimple_stmt_iterator gsi = gsi_for_stmt (s1);
+ unsigned int uid = gimple_uid (s1);
+ for (gsi_next (&gsi); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple s = gsi_stmt (gsi);
+ if (gimple_uid (s) != uid)
+ break;
+ if (s == s2)
+ return true;
+ }
+
+ return false;
+ }
+
+ return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
+}
+
+/* Insert STMT after INSERT_POINT. */
+
+static void
+insert_stmt_after (gimple stmt, gimple insert_point)
+{
+ gimple_stmt_iterator gsi;
+ basic_block bb;
+
+ if (gimple_code (insert_point) == GIMPLE_PHI)
+ bb = gimple_bb (insert_point);
+ else if (!stmt_ends_bb_p (insert_point))
+ {
+ gsi = gsi_for_stmt (insert_point);
+ gimple_set_uid (stmt, gimple_uid (insert_point));
+ gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
+ return;
+ }
+ else
+ /* We assume INSERT_POINT is a SSA_NAME_DEF_STMT of some SSA_NAME,
+ thus if it must end a basic block, it should be a call that can
+ throw, or some assignment that can throw. If it throws, the LHS
+ of it will not be initialized though, so only valid places using
+ the SSA_NAME should be dominated by the fallthru edge. */
+ bb = find_fallthru_edge (gimple_bb (insert_point)->succs)->dest;
+ gsi = gsi_after_labels (bb);
+ if (gsi_end_p (gsi))
+ {
+ gimple_stmt_iterator gsi2 = gsi_last_bb (bb);
+ gimple_set_uid (stmt,
+ gsi_end_p (gsi2) ? 1 : gimple_uid (gsi_stmt (gsi2)));
+ }
+ else
+ gimple_set_uid (stmt, gimple_uid (gsi_stmt (gsi)));
+ gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
+}
+
/* Builds one statement performing OP1 OPCODE OP2 using TMPVAR for
the result. Places the statement after the definition of either
OP1 or OP2. Returns the new statement. */
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)
if ((!op1def || gimple_nop_p (op1def))
&& (!op2def || gimple_nop_p (op2def)))
{
- gsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR));
- gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
- }
- else if ((!op1def || gimple_nop_p (op1def))
- || (op2def && !gimple_nop_p (op2def)
- && stmt_dominates_stmt_p (op1def, op2def)))
- {
- if (gimple_code (op2def) == GIMPLE_PHI)
+ gsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
+ if (gsi_end_p (gsi))
{
- gsi = gsi_after_labels (gimple_bb (op2def));
- gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
+ gimple_stmt_iterator gsi2
+ = gsi_last_bb (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
+ gimple_set_uid (sum,
+ gsi_end_p (gsi2) ? 1 : gimple_uid (gsi_stmt (gsi2)));
}
else
- {
- if (!stmt_ends_bb_p (op2def))
- {
- gsi = gsi_for_stmt (op2def);
- gsi_insert_after (&gsi, sum, GSI_NEW_STMT);
- }
- else
- {
- edge e;
- edge_iterator ei;
-
- FOR_EACH_EDGE (e, ei, gimple_bb (op2def)->succs)
- if (e->flags & EDGE_FALLTHRU)
- gsi_insert_on_edge_immediate (e, sum);
- }
- }
+ gimple_set_uid (sum, gimple_uid (gsi_stmt (gsi)));
+ gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
}
else
{
- if (gimple_code (op1def) == GIMPLE_PHI)
- {
- gsi = gsi_after_labels (gimple_bb (op1def));
- gsi_insert_before (&gsi, sum, GSI_NEW_STMT);
- }
+ gimple insert_point;
+ if ((!op1def || gimple_nop_p (op1def))
+ || (op2def && !gimple_nop_p (op2def)
+ && reassoc_stmt_dominates_stmt_p (op1def, op2def)))
+ insert_point = op2def;
else
- {
- if (!stmt_ends_bb_p (op1def))
- {
- gsi = gsi_for_stmt (op1def);
- gsi_insert_after (&gsi, sum, GSI_NEW_STMT);
- }
- else
- {
- edge e;
- edge_iterator ei;
-
- FOR_EACH_EDGE (e, ei, gimple_bb (op1def)->succs)
- if (e->flags & EDGE_FALLTHRU)
- gsi_insert_on_edge_immediate (e, sum);
- }
- }
+ insert_point = op1def;
+ insert_stmt_after (sum, insert_point);
}
update_stmt (sum);
static bool
undistribute_ops_list (enum tree_code opcode,
- VEC (operand_entry_t, heap) **ops, struct loop *loop)
+ vec<operand_entry_t> *ops, struct loop *loop)
{
- unsigned int length = VEC_length (operand_entry_t, *ops);
+ unsigned int length = ops->length ();
operand_entry_t oe1;
unsigned i, j;
sbitmap candidates, candidates2;
unsigned nr_candidates, nr_candidates2;
sbitmap_iterator sbi0;
- VEC (operand_entry_t, heap) **subops;
- htab_t ctable;
+ vec<operand_entry_t> *subops;
bool changed = false;
int next_oecount_id = 0;
/* Build a list of candidates to process. */
candidates = sbitmap_alloc (length);
- sbitmap_zero (candidates);
+ bitmap_clear (candidates);
nr_candidates = 0;
- FOR_EACH_VEC_ELT (operand_entry_t, *ops, i, oe1)
+ FOR_EACH_VEC_ELT (*ops, i, oe1)
{
enum tree_code dcode;
gimple oe1def;
|| !is_reassociable_op (oe1def, dcode, loop))
continue;
- SET_BIT (candidates, i);
+ bitmap_set_bit (candidates, i);
nr_candidates++;
}
{
fprintf (dump_file, "searching for un-distribute opportunities ");
print_generic_expr (dump_file,
- VEC_index (operand_entry_t, *ops,
- sbitmap_first_set_bit (candidates))->op, 0);
+ (*ops)[bitmap_first_set_bit (candidates)]->op, 0);
fprintf (dump_file, " %d\n", nr_candidates);
}
/* Build linearized sub-operand lists and the counting table. */
- cvec = NULL;
- ctable = htab_create (15, oecount_hash, oecount_eq, NULL);
- subops = XCNEWVEC (VEC (operand_entry_t, heap) *,
- VEC_length (operand_entry_t, *ops));
- EXECUTE_IF_SET_IN_SBITMAP (candidates, 0, i, sbi0)
+ cvec.create (0);
+
+ hash_table<oecount_hasher> ctable (15);
+
+ /* ??? Macro arguments cannot have multi-argument template types in
+ them. This typedef is needed to workaround that limitation. */
+ typedef vec<operand_entry_t> vec_operand_entry_t_heap;
+ subops = XCNEWVEC (vec_operand_entry_t_heap, ops->length ());
+ EXECUTE_IF_SET_IN_BITMAP (candidates, 0, i, sbi0)
{
gimple oedef;
enum tree_code oecode;
unsigned j;
- oedef = SSA_NAME_DEF_STMT (VEC_index (operand_entry_t, *ops, i)->op);
+ oedef = SSA_NAME_DEF_STMT ((*ops)[i]->op);
oecode = gimple_assign_rhs_code (oedef);
linearize_expr_tree (&subops[i], oedef,
associative_tree_code (oecode), false);
- FOR_EACH_VEC_ELT (operand_entry_t, subops[i], j, oe1)
+ FOR_EACH_VEC_ELT (subops[i], j, oe1)
{
oecount c;
- void **slot;
- size_t idx;
+ int *slot;
+ int idx;
c.oecode = oecode;
c.cnt = 1;
c.id = next_oecount_id++;
c.op = oe1->op;
- VEC_safe_push (oecount, heap, cvec, &c);
- idx = VEC_length (oecount, cvec) + 41;
- slot = htab_find_slot (ctable, (void *)idx, INSERT);
+ cvec.safe_push (c);
+ idx = cvec.length () + 41;
+ slot = ctable.find_slot (idx, INSERT);
if (!*slot)
{
- *slot = (void *)idx;
+ *slot = idx;
}
else
{
- VEC_pop (oecount, cvec);
- VEC_index (oecount, cvec, (size_t)*slot - 42)->cnt++;
+ cvec.pop ();
+ cvec[*slot - 42].cnt++;
}
}
}
- htab_delete (ctable);
/* Sort the counting table. */
- VEC_qsort (oecount, cvec, oecount_cmp);
+ cvec.qsort (oecount_cmp);
if (dump_file && (dump_flags & TDF_DETAILS))
{
oecount *c;
fprintf (dump_file, "Candidates:\n");
- FOR_EACH_VEC_ELT (oecount, cvec, j, c)
+ FOR_EACH_VEC_ELT (cvec, j, c)
{
fprintf (dump_file, " %u %s: ", c->cnt,
c->oecode == MULT_EXPR
}
}
- /* Process the (operand, code) pairs in order of most occurence. */
+ /* Process the (operand, code) pairs in order of most occurrence. */
candidates2 = sbitmap_alloc (length);
- while (!VEC_empty (oecount, cvec))
+ while (!cvec.is_empty ())
{
- oecount *c = VEC_last (oecount, cvec);
+ oecount *c = &cvec.last ();
if (c->cnt < 2)
break;
/* Now collect the operands in the outer chain that contain
the common operand in their inner chain. */
- sbitmap_zero (candidates2);
+ bitmap_clear (candidates2);
nr_candidates2 = 0;
- EXECUTE_IF_SET_IN_SBITMAP (candidates, 0, i, sbi0)
+ EXECUTE_IF_SET_IN_BITMAP (candidates, 0, i, sbi0)
{
gimple oedef;
enum tree_code oecode;
unsigned j;
- tree op = VEC_index (operand_entry_t, *ops, i)->op;
+ tree op = (*ops)[i]->op;
/* If we undistributed in this chain already this may be
a constant. */
if (oecode != c->oecode)
continue;
- FOR_EACH_VEC_ELT (operand_entry_t, subops[i], j, oe1)
+ FOR_EACH_VEC_ELT (subops[i], j, oe1)
{
if (oe1->op == c->op)
{
- SET_BIT (candidates2, i);
+ bitmap_set_bit (candidates2, i);
++nr_candidates2;
break;
}
{
operand_entry_t oe1, oe2;
gimple prod;
- int first = sbitmap_first_set_bit (candidates2);
+ int first = bitmap_first_set_bit (candidates2);
/* Build the new addition chain. */
- oe1 = VEC_index (operand_entry_t, *ops, first);
+ oe1 = (*ops)[first];
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Building (");
print_generic_expr (dump_file, oe1->op, 0);
}
zero_one_operation (&oe1->op, c->oecode, c->op);
- EXECUTE_IF_SET_IN_SBITMAP (candidates2, first+1, i, sbi0)
+ EXECUTE_IF_SET_IN_BITMAP (candidates2, first+1, i, sbi0)
{
gimple sum;
- oe2 = VEC_index (operand_entry_t, *ops, i);
+ oe2 = (*ops)[i];
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " + ");
undistribution with this op. */
oe1->op = gimple_assign_lhs (prod);
oe1->rank = get_rank (oe1->op);
- VEC_free (operand_entry_t, heap, subops[first]);
+ subops[first].release ();
changed = true;
}
- VEC_pop (oecount, cvec);
+ cvec.pop ();
}
- for (i = 0; i < VEC_length (operand_entry_t, *ops); ++i)
- VEC_free (operand_entry_t, heap, subops[i]);
+ for (i = 0; i < ops->length (); ++i)
+ subops[i].release ();
free (subops);
- VEC_free (oecount, heap, cvec);
+ cvec.release ();
sbitmap_free (candidates);
sbitmap_free (candidates2);
static bool
eliminate_redundant_comparison (enum tree_code opcode,
- VEC (operand_entry_t, heap) **ops,
+ vec<operand_entry_t> *ops,
unsigned int currindex,
operand_entry_t curr)
{
op2 = gimple_assign_rhs2 (def1);
/* Now look for a similar comparison in the remaining OPS. */
- for (i = currindex + 1;
- VEC_iterate (operand_entry_t, *ops, i, oe);
- i++)
+ for (i = currindex + 1; ops->iterate (i, &oe); i++)
{
tree t;
/* Now we can delete oe, as it has been subsumed by the new combined
expression t. */
- VEC_ordered_remove (operand_entry_t, *ops, i);
+ ops->ordered_remove (i);
reassociate_stats.ops_eliminated ++;
/* If t is the same as curr->op, we're done. Otherwise we must
the current entry. */
if (TREE_CODE (t) == INTEGER_CST)
{
- VEC_ordered_remove (operand_entry_t, *ops, currindex);
+ ops->ordered_remove (currindex);
add_to_ops_vec (ops, t);
}
else if (!operand_equal_p (t, curr->op, 0))
static void
optimize_ops_list (enum tree_code opcode,
- VEC (operand_entry_t, heap) **ops)
+ vec<operand_entry_t> *ops)
{
- unsigned int length = VEC_length (operand_entry_t, *ops);
+ unsigned int length = ops->length ();
unsigned int i;
operand_entry_t oe;
operand_entry_t oelast = NULL;
if (length == 1)
return;
- oelast = VEC_last (operand_entry_t, *ops);
+ oelast = ops->last ();
/* If the last two are constants, pop the constants off, merge them
and try the next two. */
if (oelast->rank == 0 && is_gimple_min_invariant (oelast->op))
{
- operand_entry_t oelm1 = VEC_index (operand_entry_t, *ops, length - 2);
+ operand_entry_t oelm1 = (*ops)[length - 2];
if (oelm1->rank == 0
&& is_gimple_min_invariant (oelm1->op)
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "Merging constants\n");
- VEC_pop (operand_entry_t, *ops);
- VEC_pop (operand_entry_t, *ops);
+ ops->pop ();
+ ops->pop ();
add_to_ops_vec (ops, folded);
reassociate_stats.constants_eliminated++;
eliminate_using_constants (opcode, ops);
oelast = NULL;
- for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe);)
+ for (i = 0; ops->iterate (i, &oe);)
{
bool done = false;
i++;
}
- length = VEC_length (operand_entry_t, *ops);
- oelast = VEC_last (operand_entry_t, *ops);
+ length = ops->length ();
+ oelast = ops->last ();
if (iterate)
optimize_ops_list (opcode, ops);
};
/* This is similar to make_range in fold-const.c, but on top of
- GIMPLE instead of trees. */
+ GIMPLE instead of trees. If EXP is non-NULL, it should be
+ an SSA_NAME and STMT argument is ignored, otherwise STMT
+ argument should be a GIMPLE_COND. */
static void
-init_range_entry (struct range_entry *r, tree exp)
+init_range_entry (struct range_entry *r, tree exp, gimple stmt)
{
int in_p;
tree low, high;
r->strict_overflow_p = false;
r->low = NULL_TREE;
r->high = NULL_TREE;
- if (TREE_CODE (exp) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (exp)))
+ if (exp != NULL_TREE
+ && (TREE_CODE (exp) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (exp))))
return;
/* Start with simply saying "EXP != 0" and then look at the code of EXP
happen, but it doesn't seem worth worrying about this. We "continue"
the outer loop when we've changed something; otherwise we "break"
the switch, which will "break" the while. */
- low = build_int_cst (TREE_TYPE (exp), 0);
+ low = exp ? build_int_cst (TREE_TYPE (exp), 0) : boolean_false_node;
high = low;
in_p = 0;
strict_overflow_p = false;
is_bool = false;
- if (TYPE_PRECISION (TREE_TYPE (exp)) == 1)
+ if (exp == NULL_TREE)
+ is_bool = true;
+ else if (TYPE_PRECISION (TREE_TYPE (exp)) == 1)
{
if (TYPE_UNSIGNED (TREE_TYPE (exp)))
is_bool = true;
while (1)
{
- gimple stmt;
enum tree_code code;
tree arg0, arg1, exp_type;
tree nexp;
location_t loc;
- if (TREE_CODE (exp) != SSA_NAME)
- break;
+ if (exp != NULL_TREE)
+ {
+ if (TREE_CODE (exp) != SSA_NAME
+ || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (exp))
+ break;
- stmt = SSA_NAME_DEF_STMT (exp);
- if (!is_gimple_assign (stmt))
- break;
+ stmt = SSA_NAME_DEF_STMT (exp);
+ if (!is_gimple_assign (stmt))
+ break;
+
+ code = gimple_assign_rhs_code (stmt);
+ arg0 = gimple_assign_rhs1 (stmt);
+ arg1 = gimple_assign_rhs2 (stmt);
+ exp_type = TREE_TYPE (exp);
+ }
+ else
+ {
+ code = gimple_cond_code (stmt);
+ arg0 = gimple_cond_lhs (stmt);
+ arg1 = gimple_cond_rhs (stmt);
+ exp_type = boolean_type_node;
+ }
- code = gimple_assign_rhs_code (stmt);
- arg0 = gimple_assign_rhs1 (stmt);
if (TREE_CODE (arg0) != SSA_NAME)
break;
- arg1 = gimple_assign_rhs2 (stmt);
- exp_type = TREE_TYPE (exp);
loc = gimple_location (stmt);
switch (code)
{
case BIT_NOT_EXPR:
- if (TREE_CODE (TREE_TYPE (exp)) == BOOLEAN_TYPE)
+ if (TREE_CODE (TREE_TYPE (exp)) == BOOLEAN_TYPE
+ /* Ensure the range is either +[-,0], +[0,0],
+ -[-,0], -[0,0] or +[1,-], +[1,1], -[1,-] or
+ -[1,1]. If it is e.g. +[-,-] or -[-,-]
+ or similar expression of unconditional true or
+ false, it should not be negated. */
+ && ((high && integer_zerop (high))
+ || (low && integer_onep (low))))
{
in_p = !in_p;
exp = arg0;
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
- true if the range merge has been successful. */
+ 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.
+ In that case, whether an op is BIT_AND_EXPR or BIT_IOR_EXPR is found in
+ oe->rank. */
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, heap) **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)
{
- tree op = VEC_index (operand_entry_t, *ops, range->idx)->op;
- location_t loc = gimple_location (SSA_NAME_DEF_STMT (op));
- tree tem = build_range_check (loc, TREE_TYPE (op), exp, in_p, low, high);
+ operand_entry_t oe = (*ops)[range->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;
+ 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, ", ");
fprintf (dump_file, "\n");
}
- if (opcode == BIT_IOR_EXPR)
+ if (opcode == BIT_IOR_EXPR
+ || (opcode == ERROR_MARK && oe->rank == BIT_IOR_EXPR))
tem = invert_truthvalue_loc (loc, tem);
- tem = fold_convert_loc (loc, TREE_TYPE (op), tem);
- gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (op));
- tem = force_gimple_operand_gsi (&gsi, tem, true, NULL_TREE, true,
- GSI_SAME_STMT);
+ tem = fold_convert_loc (loc, optype, tem);
+ gsi = gsi_for_stmt (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)
+ {
+ 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_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);
+ }
+ 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));
- VEC_index (operand_entry_t, *ops, range->idx)->op = tem;
+ oe->op = tem;
range->exp = exp;
range->low = low;
range->high = high;
range->in_p = in_p;
range->strict_overflow_p = false;
- for (range = otherrange; range < otherrange + count; range++)
+ for (i = 0; i < count; i++)
{
- VEC_index (operand_entry_t, *ops, range->idx)->op = error_mark_node;
+ 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. */
+ if (opcode == ERROR_MARK)
+ {
+ if (oe->op)
+ oe->op = build_int_cst (TREE_TYPE (oe->op),
+ oe->rank == BIT_IOR_EXPR ? 0 : 1);
+ else
+ oe->op = (oe->rank == BIT_IOR_EXPR
+ ? boolean_false_node : boolean_true_node);
+ }
+ else
+ oe->op = error_mark_node;
range->exp = NULL_TREE;
}
return true;
}
-/* 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. */
+/* Optimize X == CST1 || X == CST2
+ if popcount (CST1 ^ CST2) == 1 into
+ (X & ~(CST1 ^ CST2)) == (CST1 & ~(CST1 ^ CST2)).
+ Similarly for ranges. E.g.
+ X != 2 && X != 3 && X != 10 && X != 11
+ will be transformed by the previous optimization into
+ !((X - 2U) <= 1U || (X - 10U) <= 1U)
+ and this loop can transform that into
+ !(((X & ~8) - 2U) <= 1U). */
-static void
-optimize_range_tests (enum tree_code opcode,
- VEC (operand_entry_t, heap) **ops)
+static bool
+optimize_range_tests_xor (enum tree_code opcode, tree type,
+ tree lowi, tree lowj, tree highi, tree highj,
+ vec<operand_entry_t> *ops,
+ struct range_entry *rangei,
+ struct range_entry *rangej)
{
- unsigned int length = VEC_length (operand_entry_t, *ops), i, j, first;
- operand_entry_t oe;
- struct range_entry *ranges;
- bool any_changes = false;
-
- if (length == 1)
- return;
-
- ranges = XNEWVEC (struct range_entry, length);
- for (i = 0; i < length; i++)
- {
- ranges[i].idx = i;
- init_range_entry (ranges + i, VEC_index (operand_entry_t, *ops, i)->op);
- /* For | invert it now, we will invert it again before emitting
- the optimized expression. */
- if (opcode == BIT_IOR_EXPR)
- ranges[i].in_p = !ranges[i].in_p;
- }
-
- qsort (ranges, length, sizeof (*ranges), range_entry_cmp);
- for (i = 0; i < length; i++)
- if (ranges[i].exp != NULL_TREE && TREE_CODE (ranges[i].exp) == SSA_NAME)
- break;
+ tree lowxor, highxor, tem, exp;
+ /* 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;
+ if (!integer_pow2p (lowxor))
+ return false;
+ highxor = fold_binary (BIT_XOR_EXPR, type, highi, highj);
+ if (!tree_int_cst_equal (lowxor, highxor))
+ return false;
- /* Try to merge ranges. */
- for (first = i; i < length; i++)
- {
- tree low = ranges[i].low;
- tree high = ranges[i].high;
- int in_p = ranges[i].in_p;
- bool strict_overflow_p = ranges[i].strict_overflow_p;
- int update_fail_count = 0;
+ tem = fold_build1 (BIT_NOT_EXPR, type, lowxor);
+ 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, NULL, 1, opcode, ops, exp,
+ NULL, rangei->in_p, lowj, highj,
+ rangei->strict_overflow_p
+ || rangej->strict_overflow_p))
+ return true;
+ return false;
+}
- for (j = i + 1; j < length; j++)
- {
- if (ranges[i].exp != ranges[j].exp)
- break;
- if (!merge_ranges (&in_p, &low, &high, in_p, low, high,
- ranges[j].in_p, ranges[j].low, ranges[j].high))
- break;
- strict_overflow_p |= ranges[j].strict_overflow_p;
- }
+/* Optimize X == CST1 || X == CST2
+ if popcount (CST2 - CST1) == 1 into
+ ((X - CST1) & ~(CST2 - CST1)) == 0.
+ Similarly for ranges. E.g.
+ X == 43 || X == 76 || X == 44 || X == 78 || X == 77 || X == 46
+ || X == 75 || X == 45
+ will be transformed by the previous optimization into
+ (X - 43U) <= 3U || (X - 75U) <= 3U
+ and this loop can transform that into
+ ((X - 43U) & ~(75U - 43U)) <= 3U. */
+static bool
+optimize_range_tests_diff (enum tree_code opcode, tree type,
+ tree lowi, tree lowj, tree highi, tree highj,
+ vec<operand_entry_t> *ops,
+ struct range_entry *rangei,
+ struct range_entry *rangej)
+{
+ tree tem1, tem2, mask;
+ /* Check highi - lowi == highj - lowj. */
+ tem1 = fold_binary (MINUS_EXPR, type, highi, lowi);
+ if (tem1 == NULL_TREE || TREE_CODE (tem1) != INTEGER_CST)
+ return false;
+ tem2 = fold_binary (MINUS_EXPR, type, highj, lowj);
+ if (!tree_int_cst_equal (tem1, tem2))
+ return false;
+ /* Check popcount (lowj - lowi) == 1. */
+ tem1 = fold_binary (MINUS_EXPR, type, lowj, lowi);
+ if (tem1 == NULL_TREE || TREE_CODE (tem1) != INTEGER_CST)
+ return false;
+ if (!integer_pow2p (tem1))
+ return false;
- if (j == i + 1)
- continue;
+ type = unsigned_type_for (type);
+ tem1 = fold_convert (type, tem1);
+ tem2 = fold_convert (type, tem2);
+ lowi = fold_convert (type, lowi);
+ mask = fold_build1 (BIT_NOT_EXPR, type, tem1);
+ tem1 = fold_binary (MINUS_EXPR, type,
+ 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, NULL, 1, opcode, ops, tem1,
+ NULL, rangei->in_p, lowj, tem2,
+ rangei->strict_overflow_p
+ || rangej->strict_overflow_p))
+ return true;
+ return false;
+}
- if (update_range_test (ranges + i, ranges + i + 1, j - i - 1, opcode,
- ops, ranges[i].exp, in_p, low, high,
- strict_overflow_p))
- {
- i = j - 1;
- any_changes = true;
- }
- /* Avoid quadratic complexity if all merge_ranges calls would succeed,
- while update_range_test would fail. */
- else if (update_fail_count == 64)
- i = j - 1;
- else
- ++update_fail_count;
- }
+/* It does some common checks for function optimize_range_tests_xor and
+ optimize_range_tests_diff.
+ If OPTIMIZE_XOR is TRUE, it calls optimize_range_tests_xor.
+ Else it calls optimize_range_tests_diff. */
- /* Optimize X == CST1 || X == CST2
- if popcount (CST1 ^ CST2) == 1 into
- (X & ~(CST1 ^ CST2)) == (CST1 & ~(CST1 ^ CST2)).
- Similarly for ranges. E.g.
- X != 2 && X != 3 && X != 10 && X != 11
- will be transformed by the above loop into
- (X - 2U) <= 1U && (X - 10U) <= 1U
- and this loop can transform that into
- ((X & ~8) - 2U) <= 1U. */
+static bool
+optimize_range_tests_1 (enum tree_code opcode, int first, int length,
+ bool optimize_xor, vec<operand_entry_t> *ops,
+ struct range_entry *ranges)
+{
+ int i, j;
+ bool any_changes = false;
for (i = first; i < length; i++)
{
- tree lowi, highi, lowj, highj, type, lowxor, highxor, tem, exp;
+ tree lowi, highi, lowj, highj, type, tem;
if (ranges[i].exp == NULL_TREE || ranges[i].in_p)
continue;
continue;
for (j = i + 1; j < length && j < i + 64; j++)
{
- if (ranges[j].exp == NULL_TREE)
- continue;
- if (ranges[i].exp != ranges[j].exp)
- break;
- if (ranges[j].in_p)
+ bool changes;
+ if (ranges[i].exp != ranges[j].exp || ranges[j].in_p)
continue;
lowj = ranges[j].low;
if (lowj == NULL_TREE)
highj = ranges[j].high;
if (highj == NULL_TREE)
highj = TYPE_MAX_VALUE (type);
+ /* Check lowj > highi. */
tem = fold_binary (GT_EXPR, boolean_type_node,
lowj, highi);
if (tem == NULL_TREE || !integer_onep (tem))
continue;
- lowxor = fold_binary (BIT_XOR_EXPR, type, lowi, lowj);
- if (lowxor == NULL_TREE || TREE_CODE (lowxor) != INTEGER_CST)
- continue;
- gcc_checking_assert (!integer_zerop (lowxor));
- tem = fold_binary (MINUS_EXPR, type, lowxor,
- build_int_cst (type, 1));
- if (tem == NULL_TREE)
- continue;
- tem = fold_binary (BIT_AND_EXPR, type, lowxor, tem);
- if (tem == NULL_TREE || !integer_zerop (tem))
- continue;
- highxor = fold_binary (BIT_XOR_EXPR, type, highi, highj);
- if (!tree_int_cst_equal (lowxor, highxor))
- continue;
- tem = fold_build1 (BIT_NOT_EXPR, type, lowxor);
- exp = fold_build2 (BIT_AND_EXPR, type, ranges[i].exp, tem);
- lowj = fold_build2 (BIT_AND_EXPR, type, lowi, tem);
- highj = fold_build2 (BIT_AND_EXPR, type, highi, tem);
- if (update_range_test (ranges + i, ranges + j, 1, opcode, ops, exp,
- ranges[i].in_p, lowj, highj,
- ranges[i].strict_overflow_p
- || ranges[j].strict_overflow_p))
+ if (optimize_xor)
+ changes = optimize_range_tests_xor (opcode, type, lowi, lowj,
+ highi, highj, ops,
+ ranges + i, ranges + j);
+ else
+ changes = optimize_range_tests_diff (opcode, type, lowi, lowj,
+ highi, highj, ops,
+ ranges + i, ranges + j);
+ if (changes)
{
any_changes = true;
break;
}
}
}
+ return any_changes;
+}
- if (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)
{
- j = 0;
- FOR_EACH_VEC_ELT (operand_entry_t, *ops, i, oe)
+ 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))
{
- if (oe->op == error_mark_node)
- continue;
- else if (i != j)
- VEC_replace (operand_entry_t, *ops, j, oe);
- j++;
+ *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)
+ {
+ 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 (low), bias);
+ if (totallowp)
+ {
+ *totallowp = tbias;
+ exp = TREE_OPERAND (exp, 0);
+ STRIP_NOPS (exp);
+ return exp;
+ }
+ else if (!tree_int_cst_lt (totallow, tbias))
+ return NULL_TREE;
+ bias -= wi::to_widest (totallow);
+ if (wi::ges_p (bias, 0) && wi::lts_p (bias, prec - max))
+ {
+ *mask = wi::lshift (*mask, bias);
+ exp = TREE_OPERAND (exp, 0);
+ STRIP_NOPS (exp);
+ return exp;
+ }
+ }
}
- VEC_truncate (operand_entry_t, *ops, j);
}
+ 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;
- XDELETEVEC (ranges);
+ *mask = wi::lshift (*mask, wi::to_widest (tem));
+ return exp;
}
-/* Return true if OPERAND is defined by a PHI node which uses the LHS
- of STMT in it's operands. This is also known as a "destructive
- update" operation. */
+/* 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
-is_phi_for_stmt (gimple stmt, tree operand)
+optimize_range_tests_to_bit_test (enum tree_code opcode, int first, int length,
+ vec<operand_entry_t> *ops,
+ struct range_entry *ranges)
{
- gimple def_stmt;
- tree lhs;
- use_operand_p arg_p;
- ssa_op_iter i;
-
- if (TREE_CODE (operand) != SSA_NAME)
- return false;
-
- lhs = gimple_assign_lhs (stmt);
-
- def_stmt = SSA_NAME_DEF_STMT (operand);
- if (gimple_code (def_stmt) != GIMPLE_PHI)
- return false;
-
- FOR_EACH_PHI_ARG (arg_p, def_stmt, i, SSA_OP_USE)
- if (lhs == USE_FROM_PTR (arg_p))
- return true;
- return false;
-}
+ int i, j;
+ bool any_changes = false;
+ int prec = GET_MODE_BITSIZE (word_mode);
+ auto_vec<struct range_entry *, 64> candidates;
-/* Remove def stmt of VAR if VAR has zero uses and recurse
- on rhs1 operand if so. */
+ for (i = first; i < length - 2; i++)
+ {
+ tree lowi, highi, lowj, highj, type;
-static void
-remove_visited_stmt_chain (tree var)
-{
+ 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 OPCODE is ERROR_MARK, optimize_range_tests is called from within
+ maybe_optimize_range_tests for inter-bb range optimization.
+ In that case if oe->op is NULL, oe->id is bb->index whose
+ GIMPLE_COND is && or ||ed into the test, and oe->rank says
+ the actual opcode. */
+
+static bool
+optimize_range_tests (enum tree_code opcode,
+ vec<operand_entry_t> *ops)
+{
+ unsigned int length = ops->length (), i, j, first;
+ operand_entry_t oe;
+ struct range_entry *ranges;
+ bool any_changes = false;
+
+ if (length == 1)
+ return false;
+
+ ranges = XNEWVEC (struct range_entry, length);
+ for (i = 0; i < length; i++)
+ {
+ oe = (*ops)[i];
+ ranges[i].idx = i;
+ init_range_entry (ranges + i, oe->op,
+ oe->op ? NULL :
+ last_stmt (BASIC_BLOCK_FOR_FN (cfun, oe->id)));
+ /* For | invert it now, we will invert it again before emitting
+ the optimized expression. */
+ if (opcode == BIT_IOR_EXPR
+ || (opcode == ERROR_MARK && oe->rank == BIT_IOR_EXPR))
+ ranges[i].in_p = !ranges[i].in_p;
+ }
+
+ qsort (ranges, length, sizeof (*ranges), range_entry_cmp);
+ for (i = 0; i < length; i++)
+ if (ranges[i].exp != NULL_TREE && TREE_CODE (ranges[i].exp) == SSA_NAME)
+ break;
+
+ /* Try to merge ranges. */
+ for (first = i; i < length; i++)
+ {
+ tree low = ranges[i].low;
+ tree high = ranges[i].high;
+ int in_p = ranges[i].in_p;
+ bool strict_overflow_p = ranges[i].strict_overflow_p;
+ int update_fail_count = 0;
+
+ for (j = i + 1; j < length; j++)
+ {
+ if (ranges[i].exp != ranges[j].exp)
+ break;
+ if (!merge_ranges (&in_p, &low, &high, in_p, low, high,
+ ranges[j].in_p, ranges[j].low, ranges[j].high))
+ break;
+ strict_overflow_p |= ranges[j].strict_overflow_p;
+ }
+
+ if (j == i + 1)
+ continue;
+
+ 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;
+ }
+ /* Avoid quadratic complexity if all merge_ranges calls would succeed,
+ while update_range_test would fail. */
+ else if (update_fail_count == 64)
+ i = j - 1;
+ else
+ ++update_fail_count;
+ }
+
+ any_changes |= optimize_range_tests_1 (opcode, first, length, true,
+ ops, ranges);
+
+ 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)
+ {
+ j = 0;
+ FOR_EACH_VEC_ELT (*ops, i, oe)
+ {
+ if (oe->op == error_mark_node)
+ continue;
+ else if (i != j)
+ (*ops)[j] = oe;
+ j++;
+ }
+ ops->truncate (j);
+ }
+
+ XDELETEVEC (ranges);
+ return any_changes;
+}
+
+/* Return true if STMT is a cast like:
+ <bb N>:
+ ...
+ _123 = (int) _234;
+
+ <bb M>:
+ # _345 = PHI <_123(N), 1(...), 1(...)>
+ where _234 has bool type, _123 has single use and
+ bb N has a single successor M. This is commonly used in
+ the last block of a range test. */
+
+static bool
+final_range_test_p (gimple stmt)
+{
+ basic_block bb, rhs_bb;
+ edge e;
+ tree lhs, rhs;
+ use_operand_p use_p;
+ gimple use_stmt;
+
+ if (!gimple_assign_cast_p (stmt))
+ return false;
+ bb = gimple_bb (stmt);
+ if (!single_succ_p (bb))
+ return false;
+ e = single_succ_edge (bb);
+ if (e->flags & EDGE_COMPLEX)
+ return false;
+
+ lhs = gimple_assign_lhs (stmt);
+ rhs = gimple_assign_rhs1 (stmt);
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+ || TREE_CODE (rhs) != SSA_NAME
+ || TREE_CODE (TREE_TYPE (rhs)) != BOOLEAN_TYPE)
+ return false;
+
+ /* Test whether lhs is consumed only by a PHI in the only successor bb. */
+ if (!single_imm_use (lhs, &use_p, &use_stmt))
+ return false;
+
+ if (gimple_code (use_stmt) != GIMPLE_PHI
+ || gimple_bb (use_stmt) != e->dest)
+ return false;
+
+ /* And that the rhs is defined in the same loop. */
+ rhs_bb = gimple_bb (SSA_NAME_DEF_STMT (rhs));
+ if (rhs_bb == NULL
+ || !flow_bb_inside_loop_p (loop_containing_stmt (stmt), rhs_bb))
+ return false;
+
+ return true;
+}
+
+/* Return true if BB is suitable basic block for inter-bb range test
+ optimization. If BACKWARD is true, BB should be the only predecessor
+ of TEST_BB, and *OTHER_BB is either NULL and filled by the routine,
+ or compared with to find a common basic block to which all conditions
+ branch to if true resp. false. If BACKWARD is false, TEST_BB should
+ be the only predecessor of BB. */
+
+static bool
+suitable_cond_bb (basic_block bb, basic_block test_bb, basic_block *other_bb,
+ bool backward)
+{
+ edge_iterator ei, ei2;
+ edge e, e2;
+ gimple stmt;
+ gphi_iterator gsi;
+ bool other_edge_seen = false;
+ bool is_cond;
+
+ if (test_bb == bb)
+ return false;
+ /* Check last stmt first. */
+ stmt = last_stmt (bb);
+ if (stmt == NULL
+ || (gimple_code (stmt) != GIMPLE_COND
+ && (backward || !final_range_test_p (stmt)))
+ || gimple_visited_p (stmt)
+ || stmt_could_throw_p (stmt)
+ || *other_bb == bb)
+ return false;
+ is_cond = gimple_code (stmt) == GIMPLE_COND;
+ if (is_cond)
+ {
+ /* If last stmt is GIMPLE_COND, verify that one of the succ edges
+ goes to the next bb (if BACKWARD, it is TEST_BB), and the other
+ to *OTHER_BB (if not set yet, try to find it out). */
+ if (EDGE_COUNT (bb->succs) != 2)
+ return false;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
+ return false;
+ if (e->dest == test_bb)
+ {
+ if (backward)
+ continue;
+ else
+ return false;
+ }
+ if (e->dest == bb)
+ return false;
+ if (*other_bb == NULL)
+ {
+ FOR_EACH_EDGE (e2, ei2, test_bb->succs)
+ if (!(e2->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
+ return false;
+ else if (e->dest == e2->dest)
+ *other_bb = e->dest;
+ if (*other_bb == NULL)
+ return false;
+ }
+ if (e->dest == *other_bb)
+ other_edge_seen = true;
+ else if (backward)
+ return false;
+ }
+ if (*other_bb == NULL || !other_edge_seen)
+ return false;
+ }
+ else if (single_succ (bb) != *other_bb)
+ return false;
+
+ /* Now check all PHIs of *OTHER_BB. */
+ e = find_edge (bb, *other_bb);
+ e2 = find_edge (test_bb, *other_bb);
+ for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&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),
+ gimple_phi_arg_def (phi, e2->dest_idx), 0))
+ {
+ /* Otherwise, if one of the blocks doesn't end with GIMPLE_COND,
+ one of the PHIs should have the lhs of the last stmt in
+ that block as PHI arg and that PHI should have 0 or 1
+ corresponding to it in all other range test basic blocks
+ considered. */
+ if (!is_cond)
+ {
+ if (gimple_phi_arg_def (phi, e->dest_idx)
+ == gimple_assign_lhs (stmt)
+ && (integer_zerop (gimple_phi_arg_def (phi, e2->dest_idx))
+ || integer_onep (gimple_phi_arg_def (phi,
+ e2->dest_idx))))
+ continue;
+ }
+ else
+ {
+ gimple test_last = last_stmt (test_bb);
+ if (gimple_code (test_last) != GIMPLE_COND
+ && gimple_phi_arg_def (phi, e2->dest_idx)
+ == gimple_assign_lhs (test_last)
+ && (integer_zerop (gimple_phi_arg_def (phi, e->dest_idx))
+ || integer_onep (gimple_phi_arg_def (phi, e->dest_idx))))
+ continue;
+ }
+
+ return false;
+ }
+ }
+ return true;
+}
+
+/* Return true if BB doesn't have side-effects that would disallow
+ range test optimization, all SSA_NAMEs set in the bb are consumed
+ in the bb and there are no PHIs. */
+
+static bool
+no_side_effect_bb (basic_block bb)
+{
+ gimple_stmt_iterator gsi;
+ gimple last;
+
+ if (!gimple_seq_empty_p (phi_nodes (bb)))
+ return false;
+ last = last_stmt (bb);
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple stmt = gsi_stmt (gsi);
+ tree lhs;
+ imm_use_iterator imm_iter;
+ use_operand_p use_p;
+
+ if (is_gimple_debug (stmt))
+ continue;
+ if (gimple_has_side_effects (stmt))
+ return false;
+ if (stmt == last)
+ return true;
+ if (!is_gimple_assign (stmt))
+ return false;
+ lhs = gimple_assign_lhs (stmt);
+ if (TREE_CODE (lhs) != SSA_NAME)
+ return false;
+ if (gimple_assign_rhs_could_trap_p (stmt))
+ return false;
+ FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
+ {
+ gimple use_stmt = USE_STMT (use_p);
+ if (is_gimple_debug (use_stmt))
+ continue;
+ if (gimple_bb (use_stmt) != bb)
+ return false;
+ }
+ }
+ return false;
+}
+
+/* If VAR is set by CODE (BIT_{AND,IOR}_EXPR) which is reassociable,
+ return true and fill in *OPS recursively. */
+
+static bool
+get_ops (tree var, enum tree_code code, vec<operand_entry_t> *ops,
+ struct loop *loop)
+{
+ gimple stmt = SSA_NAME_DEF_STMT (var);
+ tree rhs[2];
+ int i;
+
+ if (!is_reassociable_op (stmt, code, loop))
+ return false;
+
+ rhs[0] = gimple_assign_rhs1 (stmt);
+ rhs[1] = gimple_assign_rhs2 (stmt);
+ gimple_set_visited (stmt, true);
+ for (i = 0; i < 2; i++)
+ if (TREE_CODE (rhs[i]) == SSA_NAME
+ && !get_ops (rhs[i], code, ops, loop)
+ && has_single_use (rhs[i]))
+ {
+ operand_entry_t oe = (operand_entry_t) pool_alloc (operand_entry_pool);
+
+ oe->op = rhs[i];
+ oe->rank = code;
+ oe->id = 0;
+ oe->count = 1;
+ ops->safe_push (oe);
+ }
+ return true;
+}
+
+/* Find the ops that were added by get_ops starting from VAR, see if
+ they were changed during update_range_test and if yes, create new
+ stmts. */
+
+static tree
+update_ops (tree var, enum tree_code code, vec<operand_entry_t> ops,
+ unsigned int *pidx, struct loop *loop)
+{
+ gimple stmt = SSA_NAME_DEF_STMT (var);
+ tree rhs[4];
+ int i;
+
+ if (!is_reassociable_op (stmt, code, loop))
+ return NULL;
+
+ rhs[0] = gimple_assign_rhs1 (stmt);
+ rhs[1] = gimple_assign_rhs2 (stmt);
+ rhs[2] = rhs[0];
+ rhs[3] = rhs[1];
+ for (i = 0; i < 2; i++)
+ if (TREE_CODE (rhs[i]) == SSA_NAME)
+ {
+ rhs[2 + i] = update_ops (rhs[i], code, ops, pidx, loop);
+ if (rhs[2 + i] == NULL_TREE)
+ {
+ if (has_single_use (rhs[i]))
+ rhs[2 + i] = ops[(*pidx)++]->op;
+ else
+ rhs[2 + i] = rhs[i];
+ }
+ }
+ if ((rhs[2] != rhs[0] || rhs[3] != rhs[1])
+ && (rhs[2] != rhs[1] || rhs[3] != rhs[0]))
+ {
+ gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
+ 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);
+ }
+ return var;
+}
+
+/* Structure to track the initial value passed to get_ops and
+ the range in the ops vector for each basic block. */
+
+struct inter_bb_range_test_entry
+{
+ tree op;
+ unsigned int first_idx, last_idx;
+};
+
+/* Inter-bb range test optimization. */
+
+static void
+maybe_optimize_range_tests (gimple stmt)
+{
+ basic_block first_bb = gimple_bb (stmt);
+ basic_block last_bb = first_bb;
+ basic_block other_bb = NULL;
+ basic_block bb;
+ edge_iterator ei;
+ edge e;
+ auto_vec<operand_entry_t> ops;
+ auto_vec<inter_bb_range_test_entry> bbinfo;
+ bool any_changes = false;
+
+ /* Consider only basic blocks that end with GIMPLE_COND or
+ a cast statement satisfying final_range_test_p. All
+ but the last bb in the first_bb .. last_bb range
+ should end with GIMPLE_COND. */
+ if (gimple_code (stmt) == GIMPLE_COND)
+ {
+ if (EDGE_COUNT (first_bb->succs) != 2)
+ return;
+ }
+ else if (final_range_test_p (stmt))
+ other_bb = single_succ (first_bb);
+ else
+ return;
+
+ if (stmt_could_throw_p (stmt))
+ return;
+
+ /* As relative ordering of post-dominator sons isn't fixed,
+ maybe_optimize_range_tests can be called first on any
+ bb in the range we want to optimize. So, start searching
+ backwards, if first_bb can be set to a predecessor. */
+ while (single_pred_p (first_bb))
+ {
+ basic_block pred_bb = single_pred (first_bb);
+ if (!suitable_cond_bb (pred_bb, first_bb, &other_bb, true))
+ break;
+ if (!no_side_effect_bb (first_bb))
+ break;
+ first_bb = pred_bb;
+ }
+ /* If first_bb is last_bb, other_bb hasn't been computed yet.
+ Before starting forward search in last_bb successors, find
+ out the other_bb. */
+ if (first_bb == last_bb)
+ {
+ other_bb = NULL;
+ /* As non-GIMPLE_COND last stmt always terminates the range,
+ if forward search didn't discover anything, just give up. */
+ if (gimple_code (stmt) != GIMPLE_COND)
+ return;
+ /* Look at both successors. Either it ends with a GIMPLE_COND
+ and satisfies suitable_cond_bb, or ends with a cast and
+ other_bb is that cast's successor. */
+ FOR_EACH_EDGE (e, ei, first_bb->succs)
+ if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
+ || e->dest == first_bb)
+ return;
+ else if (single_pred_p (e->dest))
+ {
+ stmt = last_stmt (e->dest);
+ if (stmt
+ && gimple_code (stmt) == GIMPLE_COND
+ && EDGE_COUNT (e->dest->succs) == 2)
+ {
+ if (suitable_cond_bb (first_bb, e->dest, &other_bb, true))
+ break;
+ else
+ other_bb = NULL;
+ }
+ else if (stmt
+ && final_range_test_p (stmt)
+ && find_edge (first_bb, single_succ (e->dest)))
+ {
+ other_bb = single_succ (e->dest);
+ if (other_bb == first_bb)
+ other_bb = NULL;
+ }
+ }
+ if (other_bb == NULL)
+ return;
+ }
+ /* Now do the forward search, moving last_bb to successor bbs
+ that aren't other_bb. */
+ while (EDGE_COUNT (last_bb->succs) == 2)
+ {
+ FOR_EACH_EDGE (e, ei, last_bb->succs)
+ if (e->dest != other_bb)
+ break;
+ if (e == NULL)
+ break;
+ if (!single_pred_p (e->dest))
+ break;
+ if (!suitable_cond_bb (e->dest, last_bb, &other_bb, false))
+ break;
+ if (!no_side_effect_bb (e->dest))
+ break;
+ last_bb = e->dest;
+ }
+ if (first_bb == last_bb)
+ return;
+ /* Here basic blocks first_bb through last_bb's predecessor
+ end with GIMPLE_COND, all of them have one of the edges to
+ other_bb and another to another block in the range,
+ all blocks except first_bb don't have side-effects and
+ last_bb ends with either GIMPLE_COND, or cast satisfying
+ final_range_test_p. */
+ for (bb = last_bb; ; bb = single_pred (bb))
+ {
+ enum tree_code code;
+ tree lhs, rhs;
+ inter_bb_range_test_entry bb_ent;
+
+ bb_ent.op = NULL_TREE;
+ bb_ent.first_idx = ops.length ();
+ bb_ent.last_idx = bb_ent.first_idx;
+ e = find_edge (bb, other_bb);
+ stmt = last_stmt (bb);
+ gimple_set_visited (stmt, true);
+ if (gimple_code (stmt) != GIMPLE_COND)
+ {
+ use_operand_p use_p;
+ gimple phi;
+ edge e2;
+ unsigned int d;
+
+ lhs = gimple_assign_lhs (stmt);
+ rhs = gimple_assign_rhs1 (stmt);
+ gcc_assert (bb == last_bb);
+
+ /* stmt is
+ _123 = (int) _234;
+
+ followed by:
+ <bb M>:
+ # _345 = PHI <_123(N), 1(...), 1(...)>
+
+ or 0 instead of 1. If it is 0, the _234
+ range test is anded together with all the
+ other range tests, if it is 1, it is ored with
+ them. */
+ single_imm_use (lhs, &use_p, &phi);
+ gcc_assert (gimple_code (phi) == GIMPLE_PHI);
+ e2 = find_edge (first_bb, other_bb);
+ d = e2->dest_idx;
+ gcc_assert (gimple_phi_arg_def (phi, e->dest_idx) == lhs);
+ if (integer_zerop (gimple_phi_arg_def (phi, d)))
+ code = BIT_AND_EXPR;
+ else
+ {
+ gcc_checking_assert (integer_onep (gimple_phi_arg_def (phi, d)));
+ code = BIT_IOR_EXPR;
+ }
+
+ /* If _234 SSA_NAME_DEF_STMT is
+ _234 = _567 | _789;
+ (or &, corresponding to 1/0 in the phi arguments,
+ push into ops the individual range test arguments
+ of the bitwise or resp. and, recursively. */
+ if (!get_ops (rhs, code, &ops,
+ loop_containing_stmt (stmt))
+ && has_single_use (rhs))
+ {
+ /* Otherwise, push the _234 range test itself. */
+ operand_entry_t oe
+ = (operand_entry_t) pool_alloc (operand_entry_pool);
+
+ oe->op = rhs;
+ oe->rank = code;
+ oe->id = 0;
+ oe->count = 1;
+ ops.safe_push (oe);
+ bb_ent.last_idx++;
+ }
+ else
+ bb_ent.last_idx = ops.length ();
+ bb_ent.op = rhs;
+ bbinfo.safe_push (bb_ent);
+ continue;
+ }
+ /* Otherwise stmt is GIMPLE_COND. */
+ code = gimple_cond_code (stmt);
+ lhs = gimple_cond_lhs (stmt);
+ rhs = gimple_cond_rhs (stmt);
+ if (TREE_CODE (lhs) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+ && ((code != EQ_EXPR && code != NE_EXPR)
+ || rhs != boolean_false_node
+ /* Either push into ops the individual bitwise
+ or resp. and operands, depending on which
+ edge is other_bb. */
+ || !get_ops (lhs, (((e->flags & EDGE_TRUE_VALUE) == 0)
+ ^ (code == EQ_EXPR))
+ ? BIT_AND_EXPR : BIT_IOR_EXPR, &ops,
+ loop_containing_stmt (stmt))))
+ {
+ /* Or push the GIMPLE_COND stmt itself. */
+ operand_entry_t oe
+ = (operand_entry_t) pool_alloc (operand_entry_pool);
+
+ oe->op = NULL;
+ oe->rank = (e->flags & EDGE_TRUE_VALUE)
+ ? BIT_IOR_EXPR : BIT_AND_EXPR;
+ /* oe->op = NULL signs that there is no SSA_NAME
+ for the range test, and oe->id instead is the
+ basic block number, at which's end the GIMPLE_COND
+ is. */
+ oe->id = bb->index;
+ oe->count = 1;
+ ops.safe_push (oe);
+ bb_ent.op = NULL;
+ bb_ent.last_idx++;
+ }
+ else if (ops.length () > bb_ent.first_idx)
+ {
+ bb_ent.op = lhs;
+ bb_ent.last_idx = ops.length ();
+ }
+ bbinfo.safe_push (bb_ent);
+ if (bb == first_bb)
+ break;
+ }
+ if (ops.length () > 1)
+ any_changes = optimize_range_tests (ERROR_MARK, &ops);
+ if (any_changes)
+ {
+ unsigned int idx;
+ /* update_ops relies on has_single_use predicates returning the
+ same values as it did during get_ops earlier. Additionally it
+ never removes statements, only adds new ones and it should walk
+ from the single imm use and check the predicate already before
+ making those changes.
+ On the other side, the handling of GIMPLE_COND directly can turn
+ previously multiply used SSA_NAMEs into single use SSA_NAMEs, so
+ it needs to be done in a separate loop afterwards. */
+ for (bb = last_bb, idx = 0; ; bb = single_pred (bb), idx++)
+ {
+ if (bbinfo[idx].first_idx < bbinfo[idx].last_idx
+ && bbinfo[idx].op != NULL_TREE)
+ {
+ tree new_op;
+
+ stmt = last_stmt (bb);
+ new_op = update_ops (bbinfo[idx].op,
+ (enum tree_code)
+ ops[bbinfo[idx].first_idx]->rank,
+ ops, &bbinfo[idx].first_idx,
+ loop_containing_stmt (stmt));
+ if (new_op == NULL_TREE)
+ {
+ gcc_assert (bb == last_bb);
+ new_op = ops[bbinfo[idx].first_idx++]->op;
+ }
+ if (bbinfo[idx].op != new_op)
+ {
+ imm_use_iterator iter;
+ use_operand_p use_p;
+ gimple use_stmt, cast_stmt = NULL;
+
+ FOR_EACH_IMM_USE_STMT (use_stmt, iter, bbinfo[idx].op)
+ if (is_gimple_debug (use_stmt))
+ continue;
+ else if (gimple_code (use_stmt) == GIMPLE_COND
+ || gimple_code (use_stmt) == GIMPLE_PHI)
+ FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
+ SET_USE (use_p, new_op);
+ else if (gimple_assign_cast_p (use_stmt))
+ cast_stmt = use_stmt;
+ else
+ gcc_unreachable ();
+ if (cast_stmt)
+ {
+ gcc_assert (bb == last_bb);
+ tree lhs = gimple_assign_lhs (cast_stmt);
+ tree new_lhs = make_ssa_name (TREE_TYPE (lhs));
+ enum tree_code rhs_code
+ = gimple_assign_rhs_code (cast_stmt);
+ 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 (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);
+ gsi_insert_before (&gsi, g, GSI_SAME_STMT);
+ FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
+ if (is_gimple_debug (use_stmt))
+ continue;
+ else if (gimple_code (use_stmt) == GIMPLE_COND
+ || gimple_code (use_stmt) == GIMPLE_PHI)
+ FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
+ SET_USE (use_p, new_lhs);
+ else
+ gcc_unreachable ();
+ }
+ }
+ }
+ if (bb == first_bb)
+ break;
+ }
+ for (bb = last_bb, idx = 0; ; bb = single_pred (bb), idx++)
+ {
+ if (bbinfo[idx].first_idx < bbinfo[idx].last_idx
+ && bbinfo[idx].op == NULL_TREE
+ && ops[bbinfo[idx].first_idx]->op != NULL_TREE)
+ {
+ gcond *cond_stmt = as_a <gcond *> (last_stmt (bb));
+ if (integer_zerop (ops[bbinfo[idx].first_idx]->op))
+ gimple_cond_make_false (cond_stmt);
+ else if (integer_onep (ops[bbinfo[idx].first_idx]->op))
+ gimple_cond_make_true (cond_stmt);
+ else
+ {
+ 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 (cond_stmt);
+ }
+ if (bb == first_bb)
+ break;
+ }
+ }
+}
+
+/* Return true if OPERAND is defined by a PHI node which uses the LHS
+ of STMT in it's operands. This is also known as a "destructive
+ update" operation. */
+
+static bool
+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;
+
+ if (TREE_CODE (operand) != SSA_NAME)
+ return false;
+
+ lhs = gimple_assign_lhs (stmt);
+
+ def_stmt = SSA_NAME_DEF_STMT (operand);
+ def_phi = dyn_cast <gphi *> (def_stmt);
+ if (!def_phi)
+ return false;
+
+ FOR_EACH_PHI_ARG (arg_p, def_phi, i, SSA_OP_USE)
+ if (lhs == USE_FROM_PTR (arg_p))
+ return true;
+ return false;
+}
+
+/* Remove def stmt of VAR if VAR has zero uses and recurse
+ on rhs1 operand if so. */
+
+static void
+remove_visited_stmt_chain (tree var)
+{
gimple stmt;
gimple_stmt_iterator gsi;
{
var = gimple_assign_rhs1 (stmt);
gsi = gsi_for_stmt (stmt);
- gsi_remove (&gsi, true);
+ reassoc_remove_stmt (&gsi);
release_defs (stmt);
}
else
cases, but it is unlikely to be worth it. */
static void
-swap_ops_for_binary_stmt (VEC(operand_entry_t, heap) * ops,
+swap_ops_for_binary_stmt (vec<operand_entry_t> ops,
unsigned int opindex, gimple stmt)
{
operand_entry_t oe1, oe2, oe3;
- oe1 = VEC_index (operand_entry_t, ops, opindex);
- oe2 = VEC_index (operand_entry_t, ops, opindex + 1);
- oe3 = VEC_index (operand_entry_t, ops, opindex + 2);
+ oe1 = ops[opindex];
+ oe2 = ops[opindex + 1];
+ oe3 = ops[opindex + 2];
if ((oe1->rank == oe2->rank
&& oe2->rank != oe3->rank)
oe2->op = oe1->op;
oe2->rank = oe1->rank;
oe1->op = temp.op;
- oe1->rank= temp.rank;
+ oe1->rank = temp.rank;
}
}
+/* If definition of RHS1 or RHS2 dominates STMT, return the later of those
+ two definitions, otherwise return STMT. */
+
+static inline gimple
+find_insert_point (gimple stmt, tree rhs1, tree rhs2)
+{
+ if (TREE_CODE (rhs1) == SSA_NAME
+ && reassoc_stmt_dominates_stmt_p (stmt, SSA_NAME_DEF_STMT (rhs1)))
+ stmt = SSA_NAME_DEF_STMT (rhs1);
+ if (TREE_CODE (rhs2) == SSA_NAME
+ && reassoc_stmt_dominates_stmt_p (stmt, SSA_NAME_DEF_STMT (rhs2)))
+ stmt = SSA_NAME_DEF_STMT (rhs2);
+ return stmt;
+}
+
/* Recursively rewrite our linearized statements so that the operators
match those in OPS[OPINDEX], putting the computation in rank
- order. */
+ order. Return new lhs. */
-static void
+static tree
rewrite_expr_tree (gimple stmt, unsigned int opindex,
- VEC(operand_entry_t, heap) * ops, bool moved)
+ vec<operand_entry_t> ops, bool changed)
{
tree rhs1 = gimple_assign_rhs1 (stmt);
tree rhs2 = gimple_assign_rhs2 (stmt);
+ tree lhs = gimple_assign_lhs (stmt);
operand_entry_t oe;
- /* If we have three operands left, then we want to make sure the ones
- that get the double binary op are chosen wisely. */
- if (opindex + 3 == VEC_length (operand_entry_t, ops))
- swap_ops_for_binary_stmt (ops, opindex, stmt);
-
/* 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
would have never called this function, and the tail recursion
rewrites them one at a time. */
- if (opindex + 2 == VEC_length (operand_entry_t, ops))
+ if (opindex + 2 == ops.length ())
{
operand_entry_t oe1, oe2;
- oe1 = VEC_index (operand_entry_t, ops, opindex);
- oe2 = VEC_index (operand_entry_t, ops, opindex + 1);
+ oe1 = ops[opindex];
+ oe2 = ops[opindex + 1];
if (rhs1 != oe1->op || rhs2 != oe2->op)
{
+ gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
+ unsigned int uid = gimple_uid (stmt);
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Transforming ");
print_gimple_stmt (dump_file, stmt, 0, 0);
}
- gimple_assign_set_rhs1 (stmt, oe1->op);
- gimple_assign_set_rhs2 (stmt, oe2->op);
- update_stmt (stmt);
+ if (changed)
+ {
+ gimple insert_point = find_insert_point (stmt, oe1->op, oe2->op);
+ lhs = make_ssa_name (TREE_TYPE (lhs));
+ stmt
+ = 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))
+ gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
+ else
+ insert_stmt_after (stmt, insert_point);
+ }
+ else
+ {
+ gcc_checking_assert (find_insert_point (stmt, oe1->op, oe2->op)
+ == stmt);
+ gimple_assign_set_rhs1 (stmt, oe1->op);
+ gimple_assign_set_rhs2 (stmt, oe2->op);
+ update_stmt (stmt);
+ }
+
if (rhs1 != oe1->op && rhs1 != oe2->op)
remove_visited_stmt_chain (rhs1);
print_gimple_stmt (dump_file, stmt, 0, 0);
}
}
- return;
+ return lhs;
}
/* If we hit here, we should have 3 or more ops left. */
- gcc_assert (opindex + 2 < VEC_length (operand_entry_t, ops));
+ gcc_assert (opindex + 2 < ops.length ());
/* Rewrite the next operator. */
- oe = VEC_index (operand_entry_t, ops, opindex);
+ oe = ops[opindex];
- if (oe->op != rhs2)
- {
- if (!moved)
- {
- gimple_stmt_iterator gsinow, gsirhs1;
- gimple stmt1 = stmt, stmt2;
- unsigned int count;
-
- gsinow = gsi_for_stmt (stmt);
- count = VEC_length (operand_entry_t, ops) - opindex - 2;
- while (count-- != 0)
- {
- stmt2 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt1));
- gsirhs1 = gsi_for_stmt (stmt2);
- gsi_move_before (&gsirhs1, &gsinow);
- gsi_prev (&gsinow);
- stmt1 = stmt2;
- }
- moved = true;
- }
+ /* Recurse on the LHS of the binary operator, which is guaranteed to
+ be the non-leaf side. */
+ tree new_rhs1
+ = rewrite_expr_tree (SSA_NAME_DEF_STMT (rhs1), opindex + 1, ops,
+ changed || oe->op != rhs2);
+ if (oe->op != rhs2 || new_rhs1 != rhs1)
+ {
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Transforming ");
print_gimple_stmt (dump_file, stmt, 0, 0);
}
- gimple_assign_set_rhs2 (stmt, oe->op);
- update_stmt (stmt);
+ /* If changed is false, this is either opindex == 0
+ or all outer rhs2's were equal to corresponding oe->op,
+ and powi_result is NULL.
+ That means lhs is equivalent before and after reassociation.
+ Otherwise ensure the old lhs SSA_NAME is not reused and
+ create a new stmt as well, so that any debug stmts will be
+ properly adjusted. */
+ if (changed)
+ {
+ gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
+ unsigned int uid = gimple_uid (stmt);
+ gimple insert_point = find_insert_point (stmt, 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))
+ gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
+ else
+ insert_stmt_after (stmt, insert_point);
+ }
+ else
+ {
+ gcc_checking_assert (find_insert_point (stmt, new_rhs1, oe->op)
+ == stmt);
+ gimple_assign_set_rhs1 (stmt, new_rhs1);
+ gimple_assign_set_rhs2 (stmt, oe->op);
+ update_stmt (stmt);
+ }
if (dump_file && (dump_flags & TDF_DETAILS))
{
print_gimple_stmt (dump_file, stmt, 0, 0);
}
}
- /* Recurse on the LHS of the binary operator, which is guaranteed to
- be the non-leaf side. */
- rewrite_expr_tree (SSA_NAME_DEF_STMT (rhs1), opindex + 1, ops, moved);
+ return lhs;
}
/* Find out how many cycles we need to compute statements chain.
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,
- VEC(operand_entry_t, heap) * ops)
+rewrite_expr_tree_parallel (gassign *stmt, int width,
+ vec<operand_entry_t> ops)
{
enum tree_code opcode = gimple_assign_rhs_code (stmt);
- int op_num = VEC_length (operand_entry_t, ops);
+ int op_num = ops.length ();
int stmt_num = op_num - 1;
gimple *stmts = XALLOCAVEC (gimple, stmt_num);
int op_index = op_num - 1;
if (ready_stmts_end > stmt_index)
op2 = gimple_assign_lhs (stmts[stmt_index++]);
else if (op_index >= 0)
- op2 = VEC_index (operand_entry_t, ops, op_index--)->op;
+ op2 = ops[op_index--]->op;
else
{
gcc_assert (stmt_index < i);
{
if (op_index > 1)
swap_ops_for_binary_stmt (ops, op_index - 2, NULL);
- op2 = VEC_index (operand_entry_t, ops, op_index--)->op;
- op1 = VEC_index (operand_entry_t, ops, op_index--)->op;
+ op2 = ops[op_index--]->op;
+ op1 = ops[op_index--]->op;
}
/* If we emit the last statement then we should put
static void
linearize_expr (gimple stmt)
{
- gimple_stmt_iterator gsinow, gsirhs;
+ gimple_stmt_iterator gsi;
gimple binlhs = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
gimple binrhs = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
+ gimple oldbinrhs = binrhs;
enum tree_code rhscode = gimple_assign_rhs_code (stmt);
gimple newbinrhs = NULL;
struct loop *loop = loop_containing_stmt (stmt);
+ tree lhs = gimple_assign_lhs (stmt);
gcc_assert (is_reassociable_op (binlhs, rhscode, loop)
&& is_reassociable_op (binrhs, rhscode, loop));
- gsinow = gsi_for_stmt (stmt);
- gsirhs = gsi_for_stmt (binrhs);
- gsi_move_before (&gsirhs, &gsinow);
+ gsi = gsi_for_stmt (stmt);
gimple_assign_set_rhs2 (stmt, gimple_assign_rhs1 (binrhs));
- gimple_assign_set_rhs1 (binrhs, gimple_assign_lhs (binlhs));
+ 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));
if (TREE_CODE (gimple_assign_rhs2 (stmt)) == SSA_NAME)
newbinrhs = SSA_NAME_DEF_STMT (gimple_assign_rhs2 (stmt));
}
reassociate_stats.linearized++;
- update_stmt (binrhs);
- update_stmt (binlhs);
update_stmt (stmt);
+ gsi = gsi_for_stmt (oldbinrhs);
+ reassoc_remove_stmt (&gsi);
+ release_defs (oldbinrhs);
+
gimple_set_visited (stmt, true);
gimple_set_visited (binlhs, true);
gimple_set_visited (binrhs, true);
transform b_3 + b_4 into a_5 = -b_3 + -b_4. */
static tree
-negate_value (tree tonegate, gimple_stmt_iterator *gsi)
+negate_value (tree tonegate, gimple_stmt_iterator *gsip)
{
- gimple negatedefstmt= NULL;
+ gimple negatedefstmt = NULL;
tree resultofnegate;
+ gimple_stmt_iterator gsi;
+ unsigned int uid;
/* If we are trying to negate a name, defined by an add, negate the
add operands instead. */
&& has_single_use (gimple_assign_lhs (negatedefstmt))
&& gimple_assign_rhs_code (negatedefstmt) == PLUS_EXPR)
{
- gimple_stmt_iterator gsi;
tree rhs1 = gimple_assign_rhs1 (negatedefstmt);
tree rhs2 = gimple_assign_rhs2 (negatedefstmt);
+ tree lhs = gimple_assign_lhs (negatedefstmt);
+ gimple g;
gsi = gsi_for_stmt (negatedefstmt);
rhs1 = negate_value (rhs1, &gsi);
- gimple_assign_set_rhs1 (negatedefstmt, rhs1);
gsi = gsi_for_stmt (negatedefstmt);
rhs2 = negate_value (rhs2, &gsi);
- gimple_assign_set_rhs2 (negatedefstmt, rhs2);
- update_stmt (negatedefstmt);
- return gimple_assign_lhs (negatedefstmt);
+ gsi = gsi_for_stmt (negatedefstmt);
+ lhs = make_ssa_name (TREE_TYPE (lhs));
+ gimple_set_visited (negatedefstmt, true);
+ 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;
}
tonegate = fold_build1 (NEGATE_EXPR, TREE_TYPE (tonegate), tonegate);
- resultofnegate = force_gimple_operand_gsi (gsi, tonegate, true,
+ resultofnegate = force_gimple_operand_gsi (gsip, tonegate, true,
NULL_TREE, true, GSI_SAME_STMT);
+ gsi = *gsip;
+ uid = gimple_uid (gsi_stmt (gsi));
+ for (gsi_prev (&gsi); !gsi_end_p (gsi); gsi_prev (&gsi))
+ {
+ gimple stmt = gsi_stmt (gsi);
+ if (gimple_uid (stmt) != 0)
+ break;
+ gimple_set_uid (stmt, uid);
+ }
return resultofnegate;
}
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);
return false;
*exponent = real_to_integer (&c);
- real_from_integer (&cint, VOIDmode, *exponent,
- *exponent < 0 ? -1 : 0, 0);
+ real_from_integer (&cint, VOIDmode, *exponent, SIGNED);
if (!real_identical (&c, &cint))
return false;
*base = gimple_call_arg (stmt, 0);
arg1 = gimple_call_arg (stmt, 1);
- if (!host_integerp (arg1, 0))
+ if (!tree_fits_shwi_p (arg1))
return false;
- *exponent = TREE_INT_CST_LOW (arg1);
+ *exponent = tree_to_shwi (arg1);
break;
default:
Place the operands of the expression tree in the vector named OPS. */
static void
-linearize_expr_tree (VEC(operand_entry_t, heap) **ops, gimple stmt,
+linearize_expr_tree (vec<operand_entry_t> *ops, gimple stmt,
bool is_associative, bool set_visited)
{
tree binlhs = gimple_assign_rhs1 (stmt);
print_gimple_stmt (dump_file, stmt, 0, 0);
}
- swap_tree_operands (stmt,
- gimple_assign_rhs1_ptr (stmt),
- gimple_assign_rhs2_ptr (stmt));
+ swap_ssa_operands (stmt,
+ gimple_assign_rhs1_ptr (stmt),
+ gimple_assign_rhs2_ptr (stmt));
update_stmt (stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
unsigned int i = 0;
tree negate;
- FOR_EACH_VEC_ELT (tree, plus_negates, i, negate)
+ FOR_EACH_VEC_ELT (plus_negates, i, negate)
{
gimple user = get_single_immediate_use (negate);
to force the negated operand to the RHS of the PLUS_EXPR. */
if (gimple_assign_rhs1 (user) == negate)
{
- swap_tree_operands (user,
- gimple_assign_rhs1_ptr (user),
- gimple_assign_rhs2_ptr (user));
+ swap_ssa_operands (user,
+ gimple_assign_rhs1_ptr (user),
+ gimple_assign_rhs2_ptr (user));
}
/* Now transform the PLUS_EXPR into a MINUS_EXPR and replace
plus_negates vector. */
gimple feed = SSA_NAME_DEF_STMT (negate);
tree a = gimple_assign_rhs1 (feed);
- tree rhs2 = gimple_assign_rhs2 (user);
- gimple_stmt_iterator gsi = gsi_for_stmt (feed), gsi2;
- gimple_replace_lhs (feed, negate);
- gimple_assign_set_rhs_with_ops (&gsi, PLUS_EXPR, a, rhs2);
- update_stmt (gsi_stmt (gsi));
- gsi2 = gsi_for_stmt (user);
- gimple_assign_set_rhs_with_ops (&gsi2, NEGATE_EXPR, negate, NULL);
- update_stmt (gsi_stmt (gsi2));
- gsi_move_before (&gsi, &gsi2);
- VEC_safe_push (tree, heap, plus_negates,
- gimple_assign_lhs (gsi_stmt (gsi2)));
+ 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)));
+ 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);
+ user = gsi_stmt (gsi2);
+ update_stmt (user);
+ reassoc_remove_stmt (&gsi);
+ release_defs (feed);
+ plus_negates.safe_push (gimple_assign_lhs (user));
}
else
{
we want to break up k = t - q, but we won't until we've transformed q
= b - r, which won't be broken up until we transform b = c - d.
- En passant, clear the GIMPLE visited flag on every statement. */
+ En passant, clear the GIMPLE visited flag on every statement
+ and set UIDs within each basic block. */
static void
break_up_subtract_bb (basic_block bb)
{
gimple_stmt_iterator gsi;
basic_block son;
+ unsigned int uid = 1;
for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
gimple stmt = gsi_stmt (gsi);
gimple_set_visited (stmt, false);
+ gimple_set_uid (stmt, uid++);
if (!is_gimple_assign (stmt)
|| !can_reassociate_p (gimple_assign_lhs (stmt)))
}
else if (gimple_assign_rhs_code (stmt) == NEGATE_EXPR
&& can_reassociate_p (gimple_assign_rhs1 (stmt)))
- VEC_safe_push (tree, heap, plus_negates, gimple_assign_lhs (stmt));
+ plus_negates.safe_push (gimple_assign_lhs (stmt));
}
for (son = first_dom_son (CDI_DOMINATORS, bb);
son;
typedef struct repeat_factor_d repeat_factor, *repeat_factor_t;
typedef const struct repeat_factor_d *const_repeat_factor_t;
-DEF_VEC_O (repeat_factor);
-DEF_VEC_ALLOC_O (repeat_factor, heap);
-static VEC (repeat_factor, heap) *repeat_factor_vec;
+static vec<repeat_factor> repeat_factor_vec;
/* Used for sorting the repeat factor vector. Sort primarily by
ascending occurrence count, secondarily by descending rank. */
SSA name representing the value of the replacement sequence. */
static tree
-attempt_builtin_powi (gimple stmt, VEC(operand_entry_t, heap) **ops)
+attempt_builtin_powi (gimple stmt, vec<operand_entry_t> *ops)
{
unsigned i, j, vec_len;
int ii;
return NULL_TREE;
/* Allocate the repeated factor vector. */
- repeat_factor_vec = VEC_alloc (repeat_factor, heap, 10);
+ repeat_factor_vec.create (10);
/* Scan the OPS vector for all SSA names in the product and build
up a vector of occurrence counts for each factor. */
- FOR_EACH_VEC_ELT (operand_entry_t, *ops, i, oe)
+ FOR_EACH_VEC_ELT (*ops, i, oe)
{
if (TREE_CODE (oe->op) == SSA_NAME)
{
- FOR_EACH_VEC_ELT (repeat_factor, repeat_factor_vec, j, rf1)
+ FOR_EACH_VEC_ELT (repeat_factor_vec, j, rf1)
{
if (rf1->factor == oe->op)
{
}
}
- if (j >= VEC_length (repeat_factor, repeat_factor_vec))
+ if (j >= repeat_factor_vec.length ())
{
rfnew.factor = oe->op;
rfnew.rank = oe->rank;
rfnew.count = oe->count;
rfnew.repr = NULL_TREE;
- VEC_safe_push (repeat_factor, heap, repeat_factor_vec, &rfnew);
+ repeat_factor_vec.safe_push (rfnew);
}
}
}
/* Sort the repeated factor vector by (a) increasing occurrence count,
and (b) decreasing rank. */
- VEC_qsort (repeat_factor, repeat_factor_vec, compare_repeat_factors);
+ repeat_factor_vec.qsort (compare_repeat_factors);
/* It is generally best to combine as many base factors as possible
into a product before applying __builtin_powi to the result.
t5 = t3 * t4
result = t5 * y */
- vec_len = VEC_length (repeat_factor, repeat_factor_vec);
+ vec_len = repeat_factor_vec.length ();
/* Repeatedly look for opportunities to create a builtin_powi call. */
while (true)
it if the minimum occurrence count for its factors is at
least 2, or just use this cached product as our next
multiplicand if the minimum occurrence count is 1. */
- FOR_EACH_VEC_ELT (repeat_factor, repeat_factor_vec, j, rf1)
+ FOR_EACH_VEC_ELT (repeat_factor_vec, j, rf1)
{
if (rf1->repr && rf1->count > 0)
break;
fputs ("Multiplying by cached product ", dump_file);
for (elt = j; elt < vec_len; elt++)
{
- rf = VEC_index (repeat_factor, repeat_factor_vec, elt);
+ rf = &repeat_factor_vec[elt];
print_generic_expr (dump_file, rf->factor, 0);
if (elt < vec_len - 1)
fputs (" * ", dump_file);
dump_file);
for (elt = j; elt < vec_len; elt++)
{
- rf = VEC_index (repeat_factor, repeat_factor_vec, elt);
+ rf = &repeat_factor_vec[elt];
print_generic_expr (dump_file, rf->factor, 0);
if (elt < vec_len - 1)
fputs (" * ", dump_file);
vector whose occurrence count is at least 2. If no such
factor exists, there are no builtin_powi opportunities
remaining. */
- FOR_EACH_VEC_ELT (repeat_factor, repeat_factor_vec, j, rf1)
+ FOR_EACH_VEC_ELT (repeat_factor_vec, j, rf1)
{
if (rf1->count >= 2)
break;
fputs ("Building __builtin_pow call for (", dump_file);
for (elt = j; elt < vec_len; elt++)
{
- rf = VEC_index (repeat_factor, repeat_factor_vec, elt);
+ rf = &repeat_factor_vec[elt];
print_generic_expr (dump_file, rf->factor, 0);
if (elt < vec_len - 1)
fputs (" * ", dump_file);
{
tree op1, op2;
- rf1 = VEC_index (repeat_factor, repeat_factor_vec, ii);
- rf2 = VEC_index (repeat_factor, repeat_factor_vec, ii + 1);
+ rf1 = &repeat_factor_vec[ii];
+ rf2 = &repeat_factor_vec[ii + 1];
/* Init the last factor's representative to be itself. */
if (!rf2->repr)
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;
/* Form a call to __builtin_powi for the maximum product
just formed, raised to the power obtained earlier. */
- rf1 = VEC_index (repeat_factor, repeat_factor_vec, j);
+ rf1 = &repeat_factor_vec[j];
iter_result = make_temp_ssa_name (type, NULL, "reassocpow");
pow_stmt = gimple_build_call (powi_fndecl, 2, rf1->repr,
build_int_cst (integer_type_node,
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);
unsigned k = power;
unsigned n;
- rf1 = VEC_index (repeat_factor, repeat_factor_vec, i);
+ rf1 = &repeat_factor_vec[i];
rf1->count -= power;
- FOR_EACH_VEC_ELT_REVERSE (operand_entry_t, *ops, n, oe)
+ FOR_EACH_VEC_ELT_REVERSE (*ops, n, oe)
{
if (oe->op == rf1->factor)
{
if (oe->count <= k)
{
- VEC_ordered_remove (operand_entry_t, *ops, n);
+ ops->ordered_remove (n);
k -= oe->count;
if (k == 0)
remaining occurrence count of 0 or 1, and those with a count of 1
don't have cached representatives. Re-sort the ops vector and
clean up. */
- VEC_qsort (operand_entry_t, *ops, sort_by_operand_rank);
- VEC_free (repeat_factor, heap, repeat_factor_vec);
+ ops->qsort (sort_by_operand_rank);
+ repeat_factor_vec.release ();
/* Return the final product computed herein. Note that there may
still be some elements with single occurrence count left in OPS;
{
gimple_stmt_iterator gsi;
basic_block son;
+ gimple stmt = last_stmt (bb);
+
+ if (stmt && !gimple_visited_p (stmt))
+ maybe_optimize_range_tests (stmt);
for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
{
- gimple stmt = gsi_stmt (gsi);
+ stmt = gsi_stmt (gsi);
if (is_gimple_assign (stmt)
&& !stmt_could_throw_p (stmt))
reassociations. */
if (has_zero_uses (gimple_get_lhs (stmt)))
{
- gsi_remove (&gsi, true);
+ reassoc_remove_stmt (&gsi);
release_defs (stmt);
/* We might end up removing the last stmt above which
places the iterator to the end of the sequence.
if (associative_tree_code (rhs_code))
{
- VEC(operand_entry_t, heap) *ops = NULL;
+ auto_vec<operand_entry_t> ops;
tree powi_result = NULL_TREE;
/* There may be no immediate uses left by the time we
gimple_set_visited (stmt, true);
linearize_expr_tree (&ops, stmt, true, true);
- VEC_qsort (operand_entry_t, ops, sort_by_operand_rank);
+ ops.qsort (sort_by_operand_rank);
optimize_ops_list (rhs_code, &ops);
if (undistribute_ops_list (rhs_code, &ops,
loop_containing_stmt (stmt)))
{
- VEC_qsort (operand_entry_t, ops, sort_by_operand_rank);
+ ops.qsort (sort_by_operand_rank);
optimize_ops_list (rhs_code, &ops);
}
/* If the operand vector is now empty, all operands were
consumed by the __builtin_powi optimization. */
- if (VEC_length (operand_entry_t, ops) == 0)
+ if (ops.length () == 0)
transform_stmt_to_copy (&gsi, stmt, powi_result);
- else if (VEC_length (operand_entry_t, ops) == 1)
+ else if (ops.length () == 1)
{
- tree last_op = VEC_last (operand_entry_t, ops)->op;
+ tree last_op = ops.last ()->op;
if (powi_result)
transform_stmt_to_multiply (&gsi, stmt, last_op,
}
else
{
- enum machine_mode mode = TYPE_MODE (TREE_TYPE (lhs));
- int ops_num = VEC_length (operand_entry_t, ops);
+ 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 (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file,
"Width = %d was chosen for reassociation\n", width);
if (width > 1
- && VEC_length (operand_entry_t, ops) > 3)
- rewrite_expr_tree_parallel (stmt, width, ops);
+ && ops.length () > 3)
+ rewrite_expr_tree_parallel (as_a <gassign *> (stmt),
+ width, ops);
else
- rewrite_expr_tree (stmt, 0, ops, false);
+ {
+ /* When there are three operands left, we want
+ to make sure the ones that get the double
+ binary op are chosen wisely. */
+ int len = ops.length ();
+ if (len >= 3)
+ swap_ops_for_binary_stmt (ops, len - 3, stmt);
+
+ new_lhs = rewrite_expr_tree (stmt, 0, ops,
+ powi_result != NULL);
+ }
/* If we combined some repeated factors into a
__builtin_powi call, multiply that result by the
reassociated operands. */
if (powi_result)
{
- gimple mul_stmt;
- tree type = TREE_TYPE (gimple_get_lhs (stmt));
+ gimple mul_stmt, lhs_stmt = SSA_NAME_DEF_STMT (lhs);
+ tree type = TREE_TYPE (lhs);
tree target_ssa = make_temp_ssa_name (type, NULL,
"reassocpow");
- gimple_set_lhs (stmt, target_ssa);
- update_stmt (stmt);
- mul_stmt = gimple_build_assign_with_ops (MULT_EXPR, lhs,
- powi_result,
- target_ssa);
+ gimple_set_lhs (lhs_stmt, target_ssa);
+ update_stmt (lhs_stmt);
+ if (lhs != new_lhs)
+ target_ssa = new_lhs;
+ 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);
}
}
-
- VEC_free (operand_entry_t, heap, ops);
}
}
}
reassociate_bb (son);
}
-void dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops);
-void debug_ops_vector (VEC (operand_entry_t, heap) *ops);
+/* 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);
/* Dump the operand entry vector OPS to FILE. */
void
-dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops)
+dump_ops_vector (FILE *file, vec<operand_entry_t> ops)
{
operand_entry_t oe;
unsigned int i;
- FOR_EACH_VEC_ELT (operand_entry_t, ops, i, oe)
+ FOR_EACH_VEC_ELT (ops, i, oe)
{
fprintf (file, "Op %d -> rank: %d, tree: ", i, oe->rank);
print_generic_expr (file, oe->op, 0);
/* Dump the operand entry vector OPS to STDERR. */
DEBUG_FUNCTION void
-debug_ops_vector (VEC (operand_entry_t, heap) *ops)
+debug_ops_vector (vec<operand_entry_t> ops)
{
dump_ops_vector (stderr, ops);
}
static void
do_reassoc (void)
{
- break_up_subtract_bb (ENTRY_BLOCK_PTR);
- reassociate_bb (EXIT_BLOCK_PTR);
+ break_up_subtract_bb (ENTRY_BLOCK_PTR_FOR_FN (cfun));
+ reassociate_bb (EXIT_BLOCK_PTR_FOR_FN (cfun));
}
/* Initialize the reassociation pass. */
{
int i;
long rank = 2;
- int *bbs = XNEWVEC (int, n_basic_blocks - NUM_FIXED_BLOCKS);
+ int *bbs = XNEWVEC (int, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
/* Find the loops, so that we can prevent moving calculations in
them. */
/* Reverse RPO (Reverse Post Order) will give us something where
deeper loops come later. */
pre_and_rev_post_order_compute (NULL, bbs, false);
- bb_rank = XCNEWVEC (long, last_basic_block);
- operand_rank = pointer_map_create ();
+ bb_rank = XCNEWVEC (long, last_basic_block_for_fn (cfun));
+ operand_rank = new hash_map<tree, long>;
/* Give each default definition a distinct rank. This includes
parameters and the static chain. Walk backwards over all
}
/* Set up rank for each BB */
- for (i = 0; i < n_basic_blocks - NUM_FIXED_BLOCKS; i++)
+ for (i = 0; i < n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS; i++)
bb_rank[bbs[i]] = ++rank << 16;
free (bbs);
calculate_dominance_info (CDI_POST_DOMINATORS);
- plus_negates = NULL;
+ plus_negates = vNULL;
}
/* Cleanup after the reassociation pass, and print stats if
statistics_counter_event (cfun, "Built-in powi calls created",
reassociate_stats.pows_created);
- pointer_map_destroy (operand_rank);
+ delete operand_rank;
free_alloc_pool (operand_entry_pool);
free (bb_rank);
- VEC_free (tree, heap, plus_negates);
+ plus_negates.release ();
free_dominance_info (CDI_POST_DOMINATORS);
loop_optimizer_finalize ();
}
do_reassoc ();
repropagate_negates ();
+ branch_fixup ();
fini_reassoc ();
return 0;
}
-static bool
-gate_tree_ssa_reassoc (void)
-{
- return flag_tree_reassoc != 0;
-}
-
-struct gimple_opt_pass pass_reassoc =
-{
- {
- GIMPLE_PASS,
- "reassoc", /* name */
- gate_tree_ssa_reassoc, /* gate */
- execute_reassoc, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_TREE_REASSOC, /* tv_id */
- PROP_cfg | PROP_ssa, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_verify_ssa
- | TODO_verify_flow
- | TODO_ggc_collect /* todo_flags_finish */
- }
+namespace {
+
+const pass_data pass_data_reassoc =
+{
+ GIMPLE_PASS, /* type */
+ "reassoc", /* name */
+ OPTGROUP_NONE, /* optinfo_flags */
+ TV_TREE_REASSOC, /* tv_id */
+ ( PROP_cfg | PROP_ssa ), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_update_ssa_only_virtuals, /* todo_flags_finish */
};
+
+class pass_reassoc : public gimple_opt_pass
+{
+public:
+ pass_reassoc (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_reassoc, ctxt)
+ {}
+
+ /* opt_pass methods: */
+ opt_pass * clone () { return new pass_reassoc (m_ctxt); }
+ virtual bool gate (function *) { return flag_tree_reassoc != 0; }
+ virtual unsigned int execute (function *) { return execute_reassoc (); }
+
+}; // class pass_reassoc
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_reassoc (gcc::context *ctxt)
+{
+ return new pass_reassoc (ctxt);
+}
projects / gcc.git / blobdiff