-/* SSA-PRE for trees.
- Copyright (C) 2001-2014 Free Software Foundation, Inc.
+/* Full and partial redundancy elimination and code hoisting on SSA GIMPLE.
+ Copyright (C) 2001-2017 Free Software Foundation, Inc.
Contributed by Daniel Berlin <dan@dberlin.org> and Steven Bosscher
<stevenb@suse.de>
#include "config.h"
#include "system.h"
#include "coretypes.h"
-#include "tm.h"
+#include "backend.h"
+#include "rtl.h"
#include "tree.h"
-#include "basic-block.h"
+#include "gimple.h"
+#include "predict.h"
+#include "alloc-pool.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "cgraph.h"
#include "gimple-pretty-print.h"
-#include "tree-inline.h"
-#include "hash-table.h"
-#include "tree-ssa-alias.h"
-#include "internal-fn.h"
+#include "fold-const.h"
+#include "cfganal.h"
#include "gimple-fold.h"
#include "tree-eh.h"
-#include "gimple-expr.h"
-#include "is-a.h"
-#include "gimple.h"
#include "gimplify.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.h"
#include "tree-into-ssa.h"
-#include "expr.h"
#include "tree-dfa.h"
#include "tree-ssa.h"
-#include "tree-iterator.h"
-#include "alloc-pool.h"
-#include "obstack.h"
-#include "tree-pass.h"
-#include "flags.h"
-#include "langhooks.h"
#include "cfgloop.h"
#include "tree-ssa-sccvn.h"
#include "tree-scalar-evolution.h"
#include "params.h"
#include "dbgcnt.h"
#include "domwalk.h"
-#include "ipa-prop.h"
#include "tree-ssa-propagate.h"
+#include "ipa-utils.h"
+#include "tree-cfgcleanup.h"
+#include "langhooks.h"
+#include "alias.h"
+
+/* Even though this file is called tree-ssa-pre.c, we actually
+ implement a bit more than just PRE here. All of them piggy-back
+ on GVN which is implemented in tree-ssa-sccvn.c.
+
+ 1. Full Redundancy Elimination (FRE)
+ This is the elimination phase of GVN.
+
+ 2. Partial Redundancy Elimination (PRE)
+ This is adds computation of AVAIL_OUT and ANTIC_IN and
+ doing expression insertion to form GVN-PRE.
+
+ 3. Code hoisting
+ This optimization uses the ANTIC_IN sets computed for PRE
+ to move expressions further up than PRE would do, to make
+ multiple computations of the same value fully redundant.
+ This pass is explained below (after the explanation of the
+ basic algorithm for PRE).
+*/
/* TODO:
1. Avail sets can be shared by making an avail_find_leader that
walks up the dominator tree and looks in those avail sets.
This might affect code optimality, it's unclear right now.
+ Currently the AVAIL_OUT sets are the remaining quadraticness in
+ memory of GVN-PRE.
2. Strength reduction can be performed by anticipating expressions
we can repair later on.
3. We can do back-substitution or smarter value numbering to catch
represent the actual statement containing the expressions we care about,
and we cache the value number by putting it in the expression. */
-/* Basic algorithm
+/* Basic algorithm for Partial Redundancy Elimination:
First we walk the statements to generate the AVAIL sets, the
EXP_GEN sets, and the tmp_gen sets. EXP_GEN sets represent the
In order to make it fully redundant, we insert the expression into
the predecessors where it is not available, but is ANTIC.
+ When optimizing for size, we only eliminate the partial redundancy
+ if we need to insert in only one predecessor. This avoids almost
+ completely the code size increase that PRE usually causes.
+
For the partial anticipation case, we only perform insertion if it
is partially anticipated in some block, and fully available in all
of the predecessors.
- insert/insert_aux/do_regular_insertion/do_partial_partial_insertion
- performs these steps.
+ do_pre_regular_insertion/do_pre_partial_partial_insertion
+ performs these steps, driven by insert/insert_aux.
Fourth, we eliminate fully redundant expressions.
This is a simple statement walk that replaces redundant
calculations with the now available values. */
+/* Basic algorithm for Code Hoisting:
+
+ Code hoisting is: Moving value computations up in the control flow
+ graph to make multiple copies redundant. Typically this is a size
+ optimization, but there are cases where it also is helpful for speed.
+
+ A simple code hoisting algorithm is implemented that piggy-backs on
+ the PRE infrastructure. For code hoisting, we have to know ANTIC_OUT
+ which is effectively ANTIC_IN - AVAIL_OUT. The latter two have to be
+ computed for PRE, and we can use them to perform a limited version of
+ code hoisting, too.
+
+ For the purpose of this implementation, a value is hoistable to a basic
+ block B if the following properties are met:
+
+ 1. The value is in ANTIC_IN(B) -- the value will be computed on all
+ paths from B to function exit and it can be computed in B);
+
+ 2. The value is not in AVAIL_OUT(B) -- there would be no need to
+ compute the value again and make it available twice;
+
+ 3. All successors of B are dominated by B -- makes sure that inserting
+ a computation of the value in B will make the remaining
+ computations fully redundant;
+
+ 4. At least one successor has the value in AVAIL_OUT -- to avoid
+ hoisting values up too far;
+
+ 5. There are at least two successors of B -- hoisting in straight
+ line code is pointless.
+
+ The third condition is not strictly necessary, but it would complicate
+ the hoisting pass a lot. In fact, I don't know of any code hoisting
+ algorithm that does not have this requirement. Fortunately, experiments
+ have show that most candidate hoistable values are in regions that meet
+ this condition (e.g. diamond-shape regions).
+
+ The forth condition is necessary to avoid hoisting things up too far
+ away from the uses of the value. Nothing else limits the algorithm
+ from hoisting everything up as far as ANTIC_IN allows. Experiments
+ with SPEC and CSiBE have shown that hoisting up too far results in more
+ spilling, less benefits for code size, and worse benchmark scores.
+ Fortunately, in practice most of the interesting hoisting opportunities
+ are caught despite this limitation.
+
+ For hoistable values that meet all conditions, expressions are inserted
+ to make the calculation of the hoistable value fully redundant. We
+ perform code hoisting insertions after each round of PRE insertions,
+ because code hoisting never exposes new PRE opportunities, but PRE can
+ create new code hoisting opportunities.
+
+ The code hoisting algorithm is implemented in do_hoist_insert, driven
+ by insert/insert_aux. */
+
/* Representations of value numbers:
Value numbers are represented by a representative SSA_NAME. We
CONSTANT
};
-typedef union pre_expr_union_d
+union pre_expr_union
{
tree name;
tree constant;
vn_nary_op_t nary;
vn_reference_t reference;
-} pre_expr_union;
+};
-typedef struct pre_expr_d :
typed_noop_remove <pre_expr_d>
+typedef struct pre_expr_d :
nofree_ptr_hash <pre_expr_d>
{
enum pre_expr_kind kind;
unsigned int id;
pre_expr_union u;
/* hash_table support. */
- typedef pre_expr_d value_type;
- typedef pre_expr_d compare_type;
static inline hashval_t hash (const pre_expr_d *);
static inline int equal (const pre_expr_d *, const pre_expr_d *);
} *pre_expr;
/* Compare E1 and E1 for equality. */
inline int
-pre_expr_d::equal (const value_type *e1, const compare_type *e2)
+pre_expr_d::equal (const pre_expr_d *e1, const pre_expr_d *e2)
{
if (e1->kind != e2->kind)
return false;
/* Hash E. */
inline hashval_t
-pre_expr_d::hash (const value_type *e)
+pre_expr_d::hash (const pre_expr_d *e)
{
switch (e->kind)
{
/* Mapping from expression to id number we can use in bitmap sets. */
static vec<pre_expr> expressions;
-static hash_table <pre_expr_d> expression_to_id;
+static hash_table<pre_expr_d> *expression_to_id;
static vec<unsigned> name_to_id;
/* Allocate an expression id for EXPR. */
{
unsigned version = SSA_NAME_VERSION (PRE_EXPR_NAME (expr));
/* vec::safe_grow_cleared allocates no headroom. Avoid frequent
- re-allocations by using vec::reserve upfront. There is no
- vec::quick_grow_cleared unfortunately. */
+ re-allocations by using vec::reserve upfront. */
unsigned old_len = name_to_id.length ();
name_to_id.reserve (num_ssa_names - old_len);
- name_to_id.safe_grow_cleared (num_ssa_names);
+ name_to_id.quick_grow_cleared (num_ssa_names);
gcc_assert (name_to_id[version] == 0);
name_to_id[version] = expr->id;
}
else
{
- slot = expression_to_id.find_slot (expr, INSERT);
+ slot = expression_to_id->find_slot (expr, INSERT);
gcc_assert (!*slot);
*slot = expr;
}
}
else
{
- slot = expression_to_id.find_slot (expr, NO_INSERT);
+ slot = expression_to_id->find_slot (expr, NO_INSERT);
if (!slot)
return 0;
return ((pre_expr)*slot)->id;
expressions.release ();
}
-static alloc_pool pre_expr_pool;
+static object_allocator<pre_expr_d> pre_expr_pool ("pre_expr nodes");
/* Given an SSA_NAME NAME, get or create a pre_expr to represent it. */
if (result_id != 0)
return expression_for_id (result_id);
- result = (pre_expr) pool_alloc (pre_expr_pool);
+ result = pre_expr_pool.allocate ();
result->kind = NAME;
PRE_EXPR_NAME (result) = name;
alloc_expression_id (result);
/* A cache for value_dies_in_block_x. */
bitmap expr_dies;
+ /* The live virtual operand on successor edges. */
+ tree vop_on_exit;
+
/* True if we have visited this block during ANTIC calculation. */
unsigned int visited : 1;
- /* True we have deferred processing this block during ANTIC
- calculation until its successor is processed. */
- unsigned int deferred : 1;
-
/* True when the block contains a call that might not return. */
unsigned int contains_may_not_return_call : 1;
} *bb_value_sets_t;
#define NEW_SETS(BB) ((bb_value_sets_t) ((BB)->aux))->new_sets
#define EXPR_DIES(BB) ((bb_value_sets_t) ((BB)->aux))->expr_dies
#define BB_VISITED(BB) ((bb_value_sets_t) ((BB)->aux))->visited
-#define BB_DEFERRED(BB) ((bb_value_sets_t) ((BB)->aux))->deferred
#define BB_MAY_NOTRETURN(BB) ((bb_value_sets_t) ((BB)->aux))->contains_may_not_return_call
+#define BB_LIVE_VOP_ON_EXIT(BB) ((bb_value_sets_t) ((BB)->aux))->vop_on_exit
-/* Basic block list in postorder. */
-static int *postorder;
-static int postorder_num;
-
/* This structure is used to keep track of statistics on what
optimization PRE was able to perform. */
static struct
/* The number of inserts found due to partial anticipation */
int pa_insert;
+ /* The number of inserts made for code hoisting. */
+ int hoist_insert;
+
/* The number of new PHI nodes added by PRE. */
int phis;
} pre_stats;
static void bitmap_value_insert_into_set (bitmap_set_t, pre_expr);
static void bitmap_value_replace_in_set (bitmap_set_t, pre_expr);
static void bitmap_set_copy (bitmap_set_t, bitmap_set_t);
+static void bitmap_set_and (bitmap_set_t, bitmap_set_t);
static bool bitmap_set_contains_value (bitmap_set_t, unsigned int);
static void bitmap_insert_into_set (bitmap_set_t, pre_expr);
static void bitmap_insert_into_set_1 (bitmap_set_t, pre_expr,
/* We can add and remove elements and entries to and from sets
and hash tables, so we use alloc pools for them. */
-static alloc_pool bitmap_set_pool;
+static object_allocator<bitmap_set> bitmap_set_pool ("Bitmap sets");
static bitmap_obstack grand_bitmap_obstack;
/* Set of blocks with statements that have had their EH properties changed. */
/* A three tuple {e, pred, v} used to cache phi translations in the
phi_translate_table. */
-typedef struct expr_pred_trans_d : typed_free_remove<expr_pred_trans_d>
+typedef struct expr_pred_trans_d : free_ptr_hash<expr_pred_trans_d>
{
/* The expression. */
pre_expr e;
hashval_t hashcode;
/* hash_table support. */
- typedef expr_pred_trans_d value_type;
- typedef expr_pred_trans_d compare_type;
- static inline hashval_t hash (const value_type *);
- static inline int equal (const value_type *, const compare_type *);
+ static inline hashval_t hash (const expr_pred_trans_d *);
+ static inline int equal (const expr_pred_trans_d *, const expr_pred_trans_d *);
} *expr_pred_trans_t;
typedef const struct expr_pred_trans_d *const_expr_pred_trans_t;
}
inline int
-expr_pred_trans_d::equal (const value_type *ve1,
- const compare_type *ve2)
+expr_pred_trans_d::equal (const expr_pred_trans_d *ve1,
+ const expr_pred_trans_d *ve2)
{
basic_block b1 = ve1->pred;
basic_block b2 = ve2->pred;
/* The phi_translate_table caches phi translations for a given
expression and predecessor. */
-static hash_table <expr_pred_trans_d> phi_translate_table;
+static hash_table<expr_pred_trans_d> *phi_translate_table;
/* Add the tuple mapping from {expression E, basic block PRED} to
the phi translation table and return whether it pre-existed. */
tem.e = e;
tem.pred = pred;
tem.hashcode = hash;
- slot = phi_translate_table.find_slot_with_hash (&tem, hash, INSERT);
+ slot = phi_translate_table->find_slot_with_hash (&tem, hash, INSERT);
if (*slot)
{
*entry = *slot;
static bitmap_set_t
bitmap_set_new (void)
{
- bitmap_set_t ret = (bitmap_set_t) pool_alloc (bitmap_set_pool);
+ bitmap_set_t ret = bitmap_set_pool.allocate ();
bitmap_initialize (&ret->expressions, &grand_bitmap_obstack);
bitmap_initialize (&ret->values, &grand_bitmap_obstack);
return ret;
bitmap_iterator bi, bj;
vec<pre_expr> result;
- /* Pre-allocate roughly enough space for the array. */
- result.create (bitmap_count_bits (&set->values));
+ /* Pre-allocate enough space for the array. */
+ result.create (bitmap_count_bits (&set->expressions));
FOR_EACH_VALUE_ID_IN_SET (set, i, bi)
{
EXECUTE_IF_SET_IN_BITMAP (exprset, 0, j, bj)
{
if (bitmap_bit_p (&set->expressions, j))
- result.safe_push (expression_for_id (j));
+ result.quick_push (expression_for_id (j));
}
}
if (result_id != 0)
return expression_for_id (result_id);
- newexpr = (pre_expr) pool_alloc (pre_expr_pool);
+ newexpr = pre_expr_pool.allocate ();
newexpr->kind = CONSTANT;
PRE_EXPR_CONSTANT (newexpr) = constant;
alloc_expression_id (newexpr);
return newexpr;
}
-/* Given a value id V, find the actual tree representing the constant
- value if there is one, and return it. Return NULL if we can't find
- a constant. */
-
-static tree
-get_constant_for_value_id (unsigned int v)
-{
- if (value_id_constant_p (v))
- {
- unsigned int i;
- bitmap_iterator bi;
- bitmap exprset = value_expressions[v];
-
- EXECUTE_IF_SET_IN_BITMAP (exprset, 0, i, bi)
- {
- pre_expr expr = expression_for_id (i);
- if (expr->kind == CONSTANT)
- return PRE_EXPR_CONSTANT (expr);
- }
- }
- return NULL;
-}
-
/* Get or allocate a pre_expr for a piece of GIMPLE, and return it.
Currently only supports constants and SSA_NAMES. */
static pre_expr
vn_nary_op_lookup (t, &result);
if (result != NULL)
{
- pre_expr e = (pre_expr) pool_alloc (pre_expr_pool);
+ pre_expr e = pre_expr_pool.allocate ();
e->kind = NARY;
PRE_EXPR_NARY (e) = result;
result_id = lookup_expression_id (e);
if (result_id != 0)
{
- pool_free (pre_expr_pool, e);
+ pre_expr_pool.remove (e);
e = expression_for_id (result_id);
return e;
}
}
/* Return the folded version of T if T, when folded, is a gimple
- min_invariant. Otherwise, return T. */
+ min_invariant or an SSA name. Otherwise, return T. */
static pre_expr
fully_constant_expression (pre_expr e)
case NARY:
{
vn_nary_op_t nary = PRE_EXPR_NARY (e);
- switch (TREE_CODE_CLASS (nary->opcode))
- {
- case tcc_binary:
- case tcc_comparison:
- {
- /* We have to go from trees to pre exprs to value ids to
- constants. */
- tree naryop0 = nary->op[0];
- tree naryop1 = nary->op[1];
- tree result;
- if (!is_gimple_min_invariant (naryop0))
- {
- pre_expr rep0 = get_or_alloc_expr_for (naryop0);
- unsigned int vrep0 = get_expr_value_id (rep0);
- tree const0 = get_constant_for_value_id (vrep0);
- if (const0)
- naryop0 = fold_convert (TREE_TYPE (naryop0), const0);
- }
- if (!is_gimple_min_invariant (naryop1))
- {
- pre_expr rep1 = get_or_alloc_expr_for (naryop1);
- unsigned int vrep1 = get_expr_value_id (rep1);
- tree const1 = get_constant_for_value_id (vrep1);
- if (const1)
- naryop1 = fold_convert (TREE_TYPE (naryop1), const1);
- }
- result = fold_binary (nary->opcode, nary->type,
- naryop0, naryop1);
- if (result && is_gimple_min_invariant (result))
- return get_or_alloc_expr_for_constant (result);
- /* We might have simplified the expression to a
- SSA_NAME for example from x_1 * 1. But we cannot
- insert a PHI for x_1 unconditionally as x_1 might
- not be available readily. */
- return e;
- }
- case tcc_reference:
- if (nary->opcode != REALPART_EXPR
- && nary->opcode != IMAGPART_EXPR
- && nary->opcode != VIEW_CONVERT_EXPR)
- return e;
- /* Fallthrough. */
- case tcc_unary:
- {
- /* We have to go from trees to pre exprs to value ids to
- constants. */
- tree naryop0 = nary->op[0];
- tree const0, result;
- if (is_gimple_min_invariant (naryop0))
- const0 = naryop0;
- else
- {
- pre_expr rep0 = get_or_alloc_expr_for (naryop0);
- unsigned int vrep0 = get_expr_value_id (rep0);
- const0 = get_constant_for_value_id (vrep0);
- }
- result = NULL;
- if (const0)
- {
- tree type1 = TREE_TYPE (nary->op[0]);
- const0 = fold_convert (type1, const0);
- result = fold_unary (nary->opcode, nary->type, const0);
- }
- if (result && is_gimple_min_invariant (result))
- return get_or_alloc_expr_for_constant (result);
- return e;
- }
- default:
- return e;
- }
+ tree res = vn_nary_simplify (nary);
+ if (!res)
+ return e;
+ if (is_gimple_min_invariant (res))
+ return get_or_alloc_expr_for_constant (res);
+ if (TREE_CODE (res) == SSA_NAME)
+ return get_or_alloc_expr_for_name (res);
+ return e;
}
case REFERENCE:
{
basic_block phiblock,
basic_block block, bool *same_valid)
{
- gimple phi = SSA_NAME_DEF_STMT (vuse);
+ gimple *phi = SSA_NAME_DEF_STMT (vuse);
ao_ref ref;
edge e = NULL;
bool use_oracle;
unsigned int cnt;
/* Try to find a vuse that dominates this phi node by skipping
non-clobbering statements. */
- vuse = get_continuation_for_phi (phi, &ref, &cnt, &visited, false);
+ vuse = get_continuation_for_phi (phi, &ref, &cnt, &visited, false,
+ NULL, NULL);
if (visited)
BITMAP_FREE (visited);
}
switch (e->kind)
{
case NAME:
- return PRE_EXPR_NAME (e);
+ return VN_INFO (PRE_EXPR_NAME (e))->valnum;
case CONSTANT:
return PRE_EXPR_CONSTANT (e);
case NARY:
{
pre_expr rep = expression_for_id (i);
if (rep->kind == NAME)
- return PRE_EXPR_NAME (rep);
+ return VN_INFO (PRE_EXPR_NAME (rep))->valnum;
else if (rep->kind == CONSTANT)
return PRE_EXPR_CONSTANT (rep);
}
leader = find_leader_in_sets (op_val_id, set1, set2);
result = phi_translate (leader, set1, set2, pred, phiblock);
if (result && result != leader)
- {
- tree name = get_representative_for (result);
- if (!name)
- return NULL;
- newnary->op[i] = name;
- }
+ newnary->op[i] = get_representative_for (result);
else if (!result)
return NULL;
pre_expr constant;
unsigned int new_val_id;
+ PRE_EXPR_NARY (expr) = newnary;
+ constant = fully_constant_expression (expr);
+ PRE_EXPR_NARY (expr) = nary;
+ if (constant != expr)
+ {
+ /* For non-CONSTANTs we have to make sure we can eventually
+ insert the expression. Which means we need to have a
+ leader for it. */
+ if (constant->kind != CONSTANT)
+ {
+ unsigned value_id = get_expr_value_id (constant);
+ constant = find_leader_in_sets (value_id, set1, set2);
+ if (constant)
+ return constant;
+ }
+ else
+ return constant;
+ }
+
tree result = vn_nary_op_lookup_pieces (newnary->length,
newnary->opcode,
newnary->type,
if (result && is_gimple_min_invariant (result))
return get_or_alloc_expr_for_constant (result);
- expr = (pre_expr) pool_alloc (pre_expr_pool);
+ expr = pre_expr_pool.allocate ();
expr->kind = NARY;
expr->id = 0;
if (nary)
{
PRE_EXPR_NARY (expr) = nary;
- constant = fully_constant_expression (expr);
- if (constant != expr)
- return constant;
-
new_val_id = nary->value_id;
get_or_alloc_expression_id (expr);
}
&newnary->op[0],
result, new_val_id);
PRE_EXPR_NARY (expr) = nary;
- constant = fully_constant_expression (expr);
- if (constant != expr)
- return constant;
get_or_alloc_expression_id (expr);
}
add_to_value (new_val_id, expr);
tree newvuse = vuse;
vec<vn_reference_op_s> newoperands = vNULL;
bool changed = false, same_valid = true;
- unsigned int i, j, n;
+ unsigned int i, n;
vn_reference_op_t operand;
vn_reference_t newref;
- for (i = 0, j = 0;
- operands.iterate (i, &operand); i++, j++)
+ for (i = 0; operands.iterate (i, &operand); i++)
{
pre_expr opresult;
pre_expr leader;
}
op_val_id = VN_INFO (op[n])->value_id;
leader = find_leader_in_sets (op_val_id, set1, set2);
- if (!leader)
- break;
opresult = phi_translate (leader, set1, set2, pred, phiblock);
- if (!opresult)
- break;
- if (opresult != leader)
+ if (opresult && opresult != leader)
{
tree name = get_representative_for (opresult);
- if (!name)
- break;
changed |= name != op[n];
op[n] = name;
}
+ else if (!opresult)
+ break;
}
if (n != 3)
{
newoperands.release ();
return NULL;
}
+ if (!changed)
+ continue;
if (!newoperands.exists ())
newoperands = operands.copy ();
/* We may have changed from an SSA_NAME to a constant */
newop.op0 = op[0];
newop.op1 = op[1];
newop.op2 = op[2];
- /* If it transforms a non-constant ARRAY_REF into a constant
- one, adjust the constant offset. */
- if (newop.opcode == ARRAY_REF
- && newop.off == -1
- && TREE_CODE (op[0]) == INTEGER_CST
- && TREE_CODE (op[1]) == INTEGER_CST
- && TREE_CODE (op[2]) == INTEGER_CST)
- {
- offset_int off = ((wi::to_offset (op[0])
- - wi::to_offset (op[1]))
- * wi::to_offset (op[2]));
- if (wi::fits_shwi_p (off))
- newop.off = off.to_shwi ();
- }
- newoperands[j] = newop;
- /* If it transforms from an SSA_NAME to an address, fold with
- a preceding indirect reference. */
- if (j > 0 && op[0] && TREE_CODE (op[0]) == ADDR_EXPR
- && newoperands[j - 1].opcode == MEM_REF)
- vn_reference_fold_indirect (&newoperands, &j);
- }
- if (i != operands.length ())
- {
- newoperands.release ();
- return NULL;
+ newoperands[i] = newop;
}
+ gcc_checking_assert (i == operands.length ());
if (vuse)
{
- newvuse = translate_vuse_through_block (newoperands,
+ newvuse = translate_vuse_through_block (newoperands.exists ()
+ ? newoperands : operands,
ref->set, ref->type,
vuse, phiblock, pred,
&same_valid);
tree result = vn_reference_lookup_pieces (newvuse, ref->set,
ref->type,
- newoperands,
+ newoperands.exists ()
+ ? newoperands : operands,
&newref, VN_WALK);
if (result)
newoperands.release ();
return NULL;
}
- expr = (pre_expr) pool_alloc (pre_expr_pool);
+ expr = pre_expr_pool.allocate ();
expr->kind = REFERENCE;
expr->id = 0;
}
else
new_val_id = ref->value_id;
+ if (!newoperands.exists ())
+ newoperands = operands.copy ();
newref = vn_reference_insert_pieces (newvuse, ref->set,
ref->type,
newoperands,
result, new_val_id);
- newoperands.create (0);
+ newoperands = vNULL;
PRE_EXPR_REFERENCE (expr) = newref;
constant = fully_constant_expression (expr);
if (constant != expr)
case NAME:
{
tree name = PRE_EXPR_NAME (expr);
- gimple def_stmt = SSA_NAME_DEF_STMT (name);
+ gimple *def_stmt = SSA_NAME_DEF_STMT (name);
/* If the SSA name is defined by a PHI node in this block,
translate it. */
if (gimple_code (def_stmt) == GIMPLE_PHI
return get_or_alloc_expr_for_name (def);
}
- /* Otherwise return it unchanged - it will get cleaned if its
- value is not available in PREDs AVAIL_OUT set of expressions. */
+ /* Otherwise return it unchanged - it will get removed if its
+ value is not available in PREDs AVAIL_OUT set of expressions
+ by the subtraction of TMP_GEN. */
return expr;
}
else
/* Remove failed translations again, they cause insert
iteration to not pick up new opportunities reliably. */
- phi_translate_table.remove_elt_with_hash (slot, slot->hashcode);
+ phi_translate_table->remove_elt_with_hash (slot, slot->hashcode);
}
return phitrans;
{
tree vuse = PRE_EXPR_REFERENCE (expr)->vuse;
vn_reference_t refx = PRE_EXPR_REFERENCE (expr);
- gimple def;
+ gimple *def;
gimple_stmt_iterator gsi;
unsigned id = get_expression_id (expr);
bool res = false;
For loads/calls, we also see if the vuse is killed in this block. */
static bool
-valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr,
- basic_block block)
+valid_in_sets (bitmap_set_t set1, bitmap_set_t set2, pre_expr expr)
{
switch (expr->kind)
{
case NAME:
- return bitmap_find_leader (AVAIL_OUT (block),
- get_expr_value_id (expr)) != NULL;
+ /* By construction all NAMEs are available. Non-available
+ NAMEs are removed by subtracting TMP_GEN from the sets. */
+ return true;
case NARY:
{
unsigned int i;
PA_IN. */
static void
-dependent_clean (bitmap_set_t set1, bitmap_set_t set2, basic_block block)
+dependent_clean (bitmap_set_t set1, bitmap_set_t set2)
{
vec<pre_expr> exprs = sorted_array_from_bitmap_set (set1);
pre_expr expr;
FOR_EACH_VEC_ELT (exprs, i, expr)
{
- if (!valid_in_sets (set1, set2, expr, block))
+ if (!valid_in_sets (set1, set2, expr))
bitmap_remove_from_set (set1, expr);
}
exprs.release ();
in SET. */
static void
-clean (bitmap_set_t set, basic_block block)
+clean (bitmap_set_t set)
{
vec<pre_expr> exprs = sorted_array_from_bitmap_set (set);
pre_expr expr;
FOR_EACH_VEC_ELT (exprs, i, expr)
{
- if (!valid_in_sets (set, NULL, expr, block))
+ if (!valid_in_sets (set, NULL, expr))
bitmap_remove_from_set (set, expr);
}
exprs.release ();
{
bitmap_iterator bi;
unsigned i;
+ pre_expr to_remove = NULL;
FOR_EACH_EXPR_ID_IN_SET (set, i, bi)
{
+ /* Remove queued expr. */
+ if (to_remove)
+ {
+ bitmap_remove_from_set (set, to_remove);
+ to_remove = NULL;
+ }
+
pre_expr expr = expression_for_id (i);
if (expr->kind == REFERENCE)
{
vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
if (ref->vuse)
{
- gimple def_stmt = SSA_NAME_DEF_STMT (ref->vuse);
+ gimple *def_stmt = SSA_NAME_DEF_STMT (ref->vuse);
if (!gimple_nop_p (def_stmt)
&& ((gimple_bb (def_stmt) != block
&& !dominated_by_p (CDI_DOMINATORS,
block, gimple_bb (def_stmt)))
|| (gimple_bb (def_stmt) == block
&& value_dies_in_block_x (expr, block))))
- bitmap_remove_from_set (set, expr);
+ to_remove = expr;
}
}
else if (expr->kind == NARY)
as the available expression might be after the exit point. */
if (BB_MAY_NOTRETURN (block)
&& vn_nary_may_trap (nary))
- bitmap_remove_from_set (set, expr);
+ to_remove = expr;
}
}
+
+ /* Remove queued expr. */
+ if (to_remove)
+ bitmap_remove_from_set (set, to_remove);
}
static sbitmap has_abnormal_preds;
-/* List of blocks that may have changed during ANTIC computation and
- thus need to be iterated over. */
-
-static sbitmap changed_blocks;
-
-/* Decide whether to defer a block for a later iteration, or PHI
- translate SOURCE to DEST using phis in PHIBLOCK. Return false if we
- should defer the block, and true if we processed it. */
-
-static bool
-defer_or_phi_translate_block (bitmap_set_t dest, bitmap_set_t source,
- basic_block block, basic_block phiblock)
-{
- if (!BB_VISITED (phiblock))
- {
- bitmap_set_bit (changed_blocks, block->index);
- BB_VISITED (block) = 0;
- BB_DEFERRED (block) = 1;
- return false;
- }
- else
- phi_translate_set (dest, source, block, phiblock);
- return true;
-}
-
/* Compute the ANTIC set for BLOCK.
If succs(BLOCK) > 1 then
unsigned int bii;
edge e;
edge_iterator ei;
+ bool was_visited = BB_VISITED (block);
old = ANTIC_OUT = S = NULL;
BB_VISITED (block) = 1;
else if (single_succ_p (block))
{
basic_block succ_bb = single_succ (block);
-
- /* We trade iterations of the dataflow equations for having to
- phi translate the maximal set, which is incredibly slow
- (since the maximal set often has 300+ members, even when you
- have a small number of blocks).
- Basically, we defer the computation of ANTIC for this block
- until we have processed it's successor, which will inevitably
- have a *much* smaller set of values to phi translate once
- clean has been run on it.
- The cost of doing this is that we technically perform more
- iterations, however, they are lower cost iterations.
-
- Timings for PRE on tramp3d-v4:
- without maximal set fix: 11 seconds
- with maximal set fix/without deferring: 26 seconds
- with maximal set fix/with deferring: 11 seconds
- */
-
- if (!defer_or_phi_translate_block (ANTIC_OUT, ANTIC_IN (succ_bb),
- block, succ_bb))
- {
- changed = true;
- goto maybe_dump_sets;
- }
+ gcc_assert (BB_VISITED (succ_bb));
+ phi_translate_set (ANTIC_OUT, ANTIC_IN (succ_bb), block, succ_bb);
}
/* If we have multiple successors, we take the intersection of all of
them. Note that in the case of loop exit phi nodes, we may have
first = e->dest;
else if (BB_VISITED (e->dest))
worklist.quick_push (e->dest);
+ else
+ {
+ /* Unvisited successors get their ANTIC_IN replaced by the
+ maximal set to arrive at a maximum ANTIC_IN solution.
+ We can ignore them in the intersection operation and thus
+ need not explicitely represent that maximum solution. */
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "ANTIC_IN is MAX on %d->%d\n",
+ e->src->index, e->dest->index);
+ }
}
- /* Of multiple successors we have to have visited one already. */
- if (!first)
- {
- bitmap_set_bit (changed_blocks, block->index);
- BB_VISITED (block) = 0;
- BB_DEFERRED (block) = 1;
- changed = true;
- goto maybe_dump_sets;
- }
+ /* Of multiple successors we have to have visited one already
+ which is guaranteed by iteration order. */
+ gcc_assert (first != NULL);
- if (!gimple_seq_empty_p (phi_nodes (first)))
- phi_translate_set (ANTIC_OUT, ANTIC_IN (first), block, first);
- else
- bitmap_set_copy (ANTIC_OUT, ANTIC_IN (first));
+ phi_translate_set (ANTIC_OUT, ANTIC_IN (first), block, first);
FOR_EACH_VEC_ELT (worklist, i, bprime)
{
bitmap_value_insert_into_set (ANTIC_IN (block),
expression_for_id (bii));
- clean (ANTIC_IN (block), block);
+ clean (ANTIC_IN (block));
- if (!bitmap_set_equal (old, ANTIC_IN (block)))
- {
- changed = true;
- bitmap_set_bit (changed_blocks, block->index);
- FOR_EACH_EDGE (e, ei, block->preds)
- bitmap_set_bit (changed_blocks, e->src->index);
- }
- else
- bitmap_clear_bit (changed_blocks, block->index);
+ if (!was_visited || !bitmap_set_equal (old, ANTIC_IN (block)))
+ changed = true;
maybe_dump_sets:
if (dump_file && (dump_flags & TDF_DETAILS))
{
- if (!BB_DEFERRED (block) || BB_VISITED (block))
- {
- if (ANTIC_OUT)
- print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
+ if (ANTIC_OUT)
+ print_bitmap_set (dump_file, ANTIC_OUT, "ANTIC_OUT", block->index);
- print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
- block->index);
+ if (changed)
+ fprintf (dump_file, "[changed] ");
+ print_bitmap_set (dump_file, ANTIC_IN (block), "ANTIC_IN",
+ block->index);
- if (S)
- print_bitmap_set (dump_file, S, "S", block->index);
- }
- else
- {
- fprintf (dump_file,
- "Block %d was deferred for a future iteration.\n",
- block->index);
- }
+ if (S)
+ print_bitmap_set (dump_file, S, "S", block->index);
}
if (old)
bitmap_set_free (old);
- ANTIC_IN[BLOCK])
*/
-static bool
+static void
compute_partial_antic_aux (basic_block block,
bool block_has_abnormal_pred_edge)
{
- bool changed = false;
bitmap_set_t old_PA_IN;
bitmap_set_t PA_OUT;
edge e;
/* PA_IN[block] = PA_IN[block] - ANTIC_IN[block] */
bitmap_set_subtract_values (PA_IN (block), ANTIC_IN (block));
- dependent_clean (PA_IN (block), ANTIC_IN (block), block);
-
- if (!bitmap_set_equal (old_PA_IN, PA_IN (block)))
- {
- changed = true;
- bitmap_set_bit (changed_blocks, block->index);
- FOR_EACH_EDGE (e, ei, block->preds)
- bitmap_set_bit (changed_blocks, e->src->index);
- }
- else
- bitmap_clear_bit (changed_blocks, block->index);
+ dependent_clean (PA_IN (block), ANTIC_IN (block));
maybe_dump_sets:
if (dump_file && (dump_flags & TDF_DETAILS))
bitmap_set_free (old_PA_IN);
if (PA_OUT)
bitmap_set_free (PA_OUT);
- return changed;
}
/* Compute ANTIC and partial ANTIC sets. */
int num_iterations = 0;
basic_block block;
int i;
+ edge_iterator ei;
+ edge e;
/* If any predecessor edges are abnormal, we punt, so antic_in is empty.
We pre-build the map of blocks with incoming abnormal edges here. */
FOR_ALL_BB_FN (block, cfun)
{
- edge_iterator ei;
- edge e;
+ BB_VISITED (block) = 0;
FOR_EACH_EDGE (e, ei, block->preds)
- {
- e->flags &= ~EDGE_DFS_BACK;
- if (e->flags & EDGE_ABNORMAL)
- {
- bitmap_set_bit (has_abnormal_preds, block->index);
- break;
- }
- }
+ if (e->flags & EDGE_ABNORMAL)
+ {
+ bitmap_set_bit (has_abnormal_preds, block->index);
- BB_VISITED (block) = 0;
- BB_DEFERRED (block) = 0;
+ /* We also anticipate nothing. */
+ BB_VISITED (block) = 1;
+ break;
+ }
/* While we are here, give empty ANTIC_IN sets to each block. */
ANTIC_IN (block) = bitmap_set_new ();
- PA_IN (block) = bitmap_set_new ();
+ if (do_partial_partial)
+ PA_IN (block) = bitmap_set_new ();
}
/* At the exit block we anticipate nothing. */
BB_VISITED (EXIT_BLOCK_PTR_FOR_FN (cfun)) = 1;
- changed_blocks = sbitmap_alloc (last_basic_block_for_fn (cfun) + 1);
- bitmap_ones (changed_blocks);
+ /* For ANTIC computation we need a postorder that also guarantees that
+ a block with a single successor is visited after its successor.
+ RPO on the inverted CFG has this property. */
+ int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
+ int postorder_num = inverted_post_order_compute (postorder);
+
+ auto_sbitmap worklist (last_basic_block_for_fn (cfun) + 1);
+ bitmap_ones (worklist);
while (changed)
{
if (dump_file && (dump_flags & TDF_DETAILS))
changed = false;
for (i = postorder_num - 1; i >= 0; i--)
{
- if (bitmap_bit_p (changed_blocks, postorder[i]))
+ if (bitmap_bit_p (worklist, postorder[i]))
{
basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
- changed |= compute_antic_aux (block,
- bitmap_bit_p (has_abnormal_preds,
- block->index));
+ bitmap_clear_bit (worklist, block->index);
+ if (compute_antic_aux (block,
+ bitmap_bit_p (has_abnormal_preds,
+ block->index)))
+ {
+ FOR_EACH_EDGE (e, ei, block->preds)
+ bitmap_set_bit (worklist, e->src->index);
+ changed = true;
+ }
}
}
/* Theoretically possible, but *highly* unlikely. */
if (do_partial_partial)
{
- bitmap_ones (changed_blocks);
- mark_dfs_back_edges ();
- num_iterations = 0;
- changed = true;
- while (changed)
+ /* For partial antic we ignore backedges and thus we do not need
+ to perform any iteration when we process blocks in postorder. */
+ postorder_num = pre_and_rev_post_order_compute (NULL, postorder, false);
+ for (i = postorder_num - 1 ; i >= 0; i--)
{
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, "Starting iteration %d\n", num_iterations);
- num_iterations++;
- changed = false;
- for (i = postorder_num - 1 ; i >= 0; i--)
- {
- if (bitmap_bit_p (changed_blocks, postorder[i]))
- {
- basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
- changed
- |= compute_partial_antic_aux (block,
- bitmap_bit_p (has_abnormal_preds,
- block->index));
- }
- }
- /* Theoretically possible, but *highly* unlikely. */
- gcc_checking_assert (num_iterations < 500);
+ basic_block block = BASIC_BLOCK_FOR_FN (cfun, postorder[i]);
+ compute_partial_antic_aux (block,
+ bitmap_bit_p (has_abnormal_preds,
+ block->index));
}
- statistics_histogram_event (cfun, "compute_partial_antic iterations",
- num_iterations);
}
+
sbitmap_free (has_abnormal_preds);
- sbitmap_free (changed_blocks);
+ free (postorder);
}
switch (currop->opcode)
{
case CALL_EXPR:
- {
- tree folded, sc = NULL_TREE;
- unsigned int nargs = 0;
- tree fn, *args;
- if (TREE_CODE (currop->op0) == FUNCTION_DECL)
- fn = currop->op0;
- else
- fn = find_or_generate_expression (block, currop->op0, stmts);
- if (!fn)
- return NULL_TREE;
- if (currop->op1)
- {
- sc = find_or_generate_expression (block, currop->op1, stmts);
- if (!sc)
- return NULL_TREE;
- }
- args = XNEWVEC (tree, ref->operands.length () - 1);
- while (*operand < ref->operands.length ())
- {
- args[nargs] = create_component_ref_by_pieces_1 (block, ref,
- operand, stmts);
- if (!args[nargs])
- return NULL_TREE;
- nargs++;
- }
- folded = build_call_array (currop->type,
- (TREE_CODE (fn) == FUNCTION_DECL
- ? build_fold_addr_expr (fn) : fn),
- nargs, args);
- free (args);
- if (sc)
- CALL_EXPR_STATIC_CHAIN (folded) = sc;
- return folded;
- }
+ gcc_unreachable ();
case MEM_REF:
{
off));
baseop = build_fold_addr_expr (base);
}
- return fold_build2 (MEM_REF, currop->type, baseop, offset);
+ genop = build2 (MEM_REF, currop->type, baseop, offset);
+ MR_DEPENDENCE_CLIQUE (genop) = currop->clique;
+ MR_DEPENDENCE_BASE (genop) = currop->base;
+ REF_REVERSE_STORAGE_ORDER (genop) = currop->reverse;
+ return genop;
}
case TARGET_MEM_REF:
if (!genop1)
return NULL_TREE;
}
- return build5 (TARGET_MEM_REF, currop->type,
- baseop, currop->op2, genop0, currop->op1, genop1);
+ genop = build5 (TARGET_MEM_REF, currop->type,
+ baseop, currop->op2, genop0, currop->op1, genop1);
+
+ MR_DEPENDENCE_CLIQUE (genop) = currop->clique;
+ MR_DEPENDENCE_BASE (genop) = currop->base;
+ return genop;
}
case ADDR_EXPR:
return NULL_TREE;
tree op1 = currop->op0;
tree op2 = currop->op1;
- return fold_build3 (BIT_FIELD_REF, currop->type, genop0, op1, op2);
+ tree t = build3 (BIT_FIELD_REF, currop->type, genop0, op1, op2);
+ REF_REVERSE_STORAGE_ORDER (t) = currop->reverse;
+ return fold (t);
}
/* For array ref vn_reference_op's, operand 1 of the array ref
here as the element alignment may be not visible. See
PR43783. Simply drop the element size for constant
sizes. */
- if (tree_int_cst_equal (genop3, TYPE_SIZE_UNIT (elmt_type)))
+ if (TREE_CODE (genop3) == INTEGER_CST
+ && TREE_CODE (TYPE_SIZE_UNIT (elmt_type)) == INTEGER_CST
+ && wi::eq_p (wi::to_offset (TYPE_SIZE_UNIT (elmt_type)),
+ (wi::to_offset (genop3)
+ * vn_ref_op_align_unit (currop))))
genop3 = NULL_TREE;
else
{
- genop3 = size_binop (EXACT_DIV_EXPR, genop3,
- size_int (TYPE_ALIGN_UNIT (elmt_type)));
genop3 = find_or_generate_expression (block, genop3, stmts);
if (!genop3)
return NULL_TREE;
gimple_stmt_iterator gsi;
tree exprtype = type ? type : get_expr_type (expr);
pre_expr nameexpr;
- gimple newstmt;
+ gassign *newstmt;
switch (expr->kind)
{
- /* We may hit the NAME/CONSTANT case if we have to convert types
- that value numbering saw through. */
+ /* We may hit the NAME/CONSTANT case if we have to convert types
+ that value numbering saw through. */
case NAME:
folded = PRE_EXPR_NAME (expr);
+ if (useless_type_conversion_p (exprtype, TREE_TYPE (folded)))
+ return folded;
break;
case CONSTANT:
- folded = PRE_EXPR_CONSTANT (expr);
- break;
- case REFERENCE:
- {
- vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
- folded = create_component_ref_by_pieces (block, ref, stmts);
- if (!folded)
- return NULL_TREE;
+ {
+ folded = PRE_EXPR_CONSTANT (expr);
+ tree tem = fold_convert (exprtype, folded);
+ if (is_gimple_min_invariant (tem))
+ return tem;
+ break;
}
+ case REFERENCE:
+ if (PRE_EXPR_REFERENCE (expr)->operands[0].opcode == CALL_EXPR)
+ {
+ vn_reference_t ref = PRE_EXPR_REFERENCE (expr);
+ unsigned int operand = 1;
+ vn_reference_op_t currop = &ref->operands[0];
+ tree sc = NULL_TREE;
+ tree fn;
+ if (TREE_CODE (currop->op0) == FUNCTION_DECL)
+ fn = currop->op0;
+ else
+ fn = find_or_generate_expression (block, currop->op0, stmts);
+ if (!fn)
+ return NULL_TREE;
+ if (currop->op1)
+ {
+ sc = find_or_generate_expression (block, currop->op1, stmts);
+ if (!sc)
+ return NULL_TREE;
+ }
+ auto_vec<tree> args (ref->operands.length () - 1);
+ while (operand < ref->operands.length ())
+ {
+ tree arg = create_component_ref_by_pieces_1 (block, ref,
+ &operand, stmts);
+ if (!arg)
+ return NULL_TREE;
+ args.quick_push (arg);
+ }
+ gcall *call
+ = gimple_build_call_vec ((TREE_CODE (fn) == FUNCTION_DECL
+ ? build_fold_addr_expr (fn) : fn), args);
+ gimple_call_set_with_bounds (call, currop->with_bounds);
+ if (sc)
+ gimple_call_set_chain (call, sc);
+ tree forcedname = make_ssa_name (currop->type);
+ gimple_call_set_lhs (call, forcedname);
+ gimple_set_vuse (call, BB_LIVE_VOP_ON_EXIT (block));
+ gimple_seq_add_stmt_without_update (&forced_stmts, call);
+ folded = forcedname;
+ }
+ else
+ {
+ folded = create_component_ref_by_pieces (block,
+ PRE_EXPR_REFERENCE (expr),
+ stmts);
+ if (!folded)
+ return NULL_TREE;
+ name = make_temp_ssa_name (exprtype, NULL, "pretmp");
+ newstmt = gimple_build_assign (name, folded);
+ gimple_seq_add_stmt_without_update (&forced_stmts, newstmt);
+ gimple_set_vuse (newstmt, BB_LIVE_VOP_ON_EXIT (block));
+ folded = name;
+ }
break;
case NARY:
{
if (nary->opcode == POINTER_PLUS_EXPR)
{
if (i == 0)
- genop[i] = fold_convert (nary->type, genop[i]);
+ genop[i] = gimple_convert (&forced_stmts,
+ nary->type, genop[i]);
else if (i == 1)
- genop[i] = convert_to_ptrofftype (genop[i]);
+ genop[i] = gimple_convert (&forced_stmts,
+ sizetype, genop[i]);
}
else
- genop[i] = fold_convert (TREE_TYPE (nary->op[i]), genop[i]);
+ genop[i] = gimple_convert (&forced_stmts,
+ TREE_TYPE (nary->op[i]), genop[i]);
}
if (nary->opcode == CONSTRUCTOR)
{
for (i = 0; i < nary->length; ++i)
CONSTRUCTOR_APPEND_ELT (elts, NULL_TREE, genop[i]);
folded = build_constructor (nary->type, elts);
+ name = make_temp_ssa_name (exprtype, NULL, "pretmp");
+ newstmt = gimple_build_assign (name, folded);
+ gimple_seq_add_stmt_without_update (&forced_stmts, newstmt);
+ folded = name;
}
else
{
switch (nary->length)
{
case 1:
- folded = fold_build1 (nary->opcode, nary->type,
- genop[0]);
+ folded = gimple_build (&forced_stmts, nary->opcode, nary->type,
+ genop[0]);
break;
case 2:
- folded = fold_build2 (nary->opcode, nary->type,
- genop[0], genop[1]);
+ folded = gimple_build (&forced_stmts, nary->opcode, nary->type,
+ genop[0], genop[1]);
break;
case 3:
- folded = fold_build3 (nary->opcode, nary->type,
- genop[0], genop[1], genop[2]);
+ folded = gimple_build (&forced_stmts, nary->opcode, nary->type,
+ genop[0], genop[1], genop[2]);
break;
default:
gcc_unreachable ();
gcc_unreachable ();
}
- if (!useless_type_conversion_p (exprtype, TREE_TYPE (folded)))
- folded = fold_convert (exprtype, folded);
+ folded = gimple_convert (&forced_stmts, exprtype, folded);
- /* Force the generated expression to be a sequence of GIMPLE
- statements.
- We have to call unshare_expr because force_gimple_operand may
- modify the tree we pass to it. */
- folded = force_gimple_operand (unshare_expr (folded), &forced_stmts,
- false, NULL);
+ /* If there is nothing to insert, return the simplified result. */
+ if (gimple_seq_empty_p (forced_stmts))
+ return folded;
+ /* If we simplified to a constant return it and discard eventually
+ built stmts. */
+ if (is_gimple_min_invariant (folded))
+ {
+ gimple_seq_discard (forced_stmts);
+ return folded;
+ }
+ /* Likewise if we simplified to sth not queued for insertion. */
+ bool found = false;
+ gsi = gsi_last (forced_stmts);
+ for (; !gsi_end_p (gsi); gsi_prev (&gsi))
+ {
+ gimple *stmt = gsi_stmt (gsi);
+ tree forcedname = gimple_get_lhs (stmt);
+ if (forcedname == folded)
+ {
+ found = true;
+ break;
+ }
+ }
+ if (! found)
+ {
+ gimple_seq_discard (forced_stmts);
+ return folded;
+ }
+ gcc_assert (TREE_CODE (folded) == SSA_NAME);
/* If we have any intermediate expressions to the value sets, add them
to the value sets and chain them in the instruction stream. */
gsi = gsi_start (forced_stmts);
for (; !gsi_end_p (gsi); gsi_next (&gsi))
{
- gimple stmt = gsi_stmt (gsi);
+ gimple *stmt = gsi_stmt (gsi);
tree forcedname = gimple_get_lhs (stmt);
pre_expr nameexpr;
- if (TREE_CODE (forcedname) == SSA_NAME)
+ if (forcedname != folded)
{
- bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (forcedname));
VN_INFO_GET (forcedname)->valnum = forcedname;
VN_INFO (forcedname)->value_id = get_next_value_id ();
nameexpr = get_or_alloc_expr_for_name (forcedname);
bitmap_value_replace_in_set (NEW_SETS (block), nameexpr);
bitmap_value_replace_in_set (AVAIL_OUT (block), nameexpr);
}
+
+ bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (forcedname));
+ gimple_set_plf (stmt, NECESSARY, false);
}
gimple_seq_add_seq (stmts, forced_stmts);
}
- name = make_temp_ssa_name (exprtype, NULL, "pretmp");
- newstmt = gimple_build_assign (name, folded);
- gimple_set_plf (newstmt, NECESSARY, false);
-
- gimple_seq_add_stmt (stmts, newstmt);
- bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (name));
+ name = folded;
/* Fold the last statement. */
gsi = gsi_last (*stmts);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Inserted ");
- print_gimple_stmt (dump_file, newstmt, 0, 0);
+ print_gimple_stmt (dump_file, gsi_stmt (gsi_last (*stmts)), 0, 0);
fprintf (dump_file, " in predecessor %d (%04d)\n",
block->index, value_id);
}
edge_iterator ei;
tree type = get_expr_type (expr);
tree temp;
- gimple phi;
+ gphi *phi;
/* Make sure we aren't creating an induction variable. */
if (bb_loop_depth (block) > 0 && EDGE_COUNT (block->preds) == 2)
tree builtexpr;
bprime = pred->src;
eprime = avail[pred->dest_idx];
-
- if (eprime->kind != NAME && eprime->kind != CONSTANT)
+ builtexpr = create_expression_by_pieces (bprime, eprime,
+ &stmts, type);
+ gcc_assert (!(pred->flags & EDGE_ABNORMAL));
+ if (!gimple_seq_empty_p (stmts))
{
- builtexpr = create_expression_by_pieces (bprime, eprime,
- &stmts, type);
- gcc_assert (!(pred->flags & EDGE_ABNORMAL));
gsi_insert_seq_on_edge (pred, stmts);
- if (!builtexpr)
- {
- /* We cannot insert a PHI node if we failed to insert
- on one edge. */
- nophi = true;
- continue;
- }
- avail[pred->dest_idx] = get_or_alloc_expr_for_name (builtexpr);
insertions = true;
}
- else if (eprime->kind == CONSTANT)
- {
- /* Constants may not have the right type, fold_convert
- should give us back a constant with the right type. */
- tree constant = PRE_EXPR_CONSTANT (eprime);
- if (!useless_type_conversion_p (type, TREE_TYPE (constant)))
- {
- tree builtexpr = fold_convert (type, constant);
- if (!is_gimple_min_invariant (builtexpr))
- {
- tree forcedexpr = force_gimple_operand (builtexpr,
- &stmts, true,
- NULL);
- if (!is_gimple_min_invariant (forcedexpr))
- {
- if (forcedexpr != builtexpr)
- {
- VN_INFO_GET (forcedexpr)->valnum = PRE_EXPR_CONSTANT (eprime);
- VN_INFO (forcedexpr)->value_id = get_expr_value_id (eprime);
- }
- if (stmts)
- {
- gimple_stmt_iterator gsi;
- gsi = gsi_start (stmts);
- for (; !gsi_end_p (gsi); gsi_next (&gsi))
- {
- gimple stmt = gsi_stmt (gsi);
- tree lhs = gimple_get_lhs (stmt);
- if (TREE_CODE (lhs) == SSA_NAME)
- bitmap_set_bit (inserted_exprs,
- SSA_NAME_VERSION (lhs));
- gimple_set_plf (stmt, NECESSARY, false);
- }
- gsi_insert_seq_on_edge (pred, stmts);
- }
- avail[pred->dest_idx]
- = get_or_alloc_expr_for_name (forcedexpr);
- }
- }
- else
- avail[pred->dest_idx]
- = get_or_alloc_expr_for_constant (builtexpr);
- }
- }
- else if (eprime->kind == NAME)
+ if (!builtexpr)
{
- /* We may have to do a conversion because our value
- numbering can look through types in certain cases, but
- our IL requires all operands of a phi node have the same
- type. */
- tree name = PRE_EXPR_NAME (eprime);
- if (!useless_type_conversion_p (type, TREE_TYPE (name)))
- {
- tree builtexpr;
- tree forcedexpr;
- builtexpr = fold_convert (type, name);
- forcedexpr = force_gimple_operand (builtexpr,
- &stmts, true,
- NULL);
-
- if (forcedexpr != name)
- {
- VN_INFO_GET (forcedexpr)->valnum = VN_INFO (name)->valnum;
- VN_INFO (forcedexpr)->value_id = VN_INFO (name)->value_id;
- }
-
- if (stmts)
- {
- gimple_stmt_iterator gsi;
- gsi = gsi_start (stmts);
- for (; !gsi_end_p (gsi); gsi_next (&gsi))
- {
- gimple stmt = gsi_stmt (gsi);
- tree lhs = gimple_get_lhs (stmt);
- if (TREE_CODE (lhs) == SSA_NAME)
- bitmap_set_bit (inserted_exprs, SSA_NAME_VERSION (lhs));
- gimple_set_plf (stmt, NECESSARY, false);
- }
- gsi_insert_seq_on_edge (pred, stmts);
- }
- avail[pred->dest_idx] = get_or_alloc_expr_for_name (forcedexpr);
- }
+ /* We cannot insert a PHI node if we failed to insert
+ on one edge. */
+ nophi = true;
+ continue;
}
+ if (is_gimple_min_invariant (builtexpr))
+ avail[pred->dest_idx] = get_or_alloc_expr_for_constant (builtexpr);
+ else
+ avail[pred->dest_idx] = get_or_alloc_expr_for_name (builtexpr);
}
/* If we didn't want a phi node, and we made insertions, we still have
inserted new stuff, and thus return true. If we didn't want a phi node,
bitmap_insert_into_set (NEW_SETS (block),
newphi);
+ /* If we insert a PHI node for a conversion of another PHI node
+ in the same basic-block try to preserve range information.
+ This is important so that followup loop passes receive optimal
+ number of iteration analysis results. See PR61743. */
+ if (expr->kind == NARY
+ && CONVERT_EXPR_CODE_P (expr->u.nary->opcode)
+ && TREE_CODE (expr->u.nary->op[0]) == SSA_NAME
+ && gimple_bb (SSA_NAME_DEF_STMT (expr->u.nary->op[0])) == block
+ && INTEGRAL_TYPE_P (type)
+ && INTEGRAL_TYPE_P (TREE_TYPE (expr->u.nary->op[0]))
+ && (TYPE_PRECISION (type)
+ >= TYPE_PRECISION (TREE_TYPE (expr->u.nary->op[0])))
+ && SSA_NAME_RANGE_INFO (expr->u.nary->op[0]))
+ {
+ wide_int min, max;
+ if (get_range_info (expr->u.nary->op[0], &min, &max) == VR_RANGE
+ && !wi::neg_p (min, SIGNED)
+ && !wi::neg_p (max, SIGNED))
+ /* Just handle extension and sign-changes of all-positive ranges. */
+ set_range_info (temp,
+ SSA_NAME_RANGE_TYPE (expr->u.nary->op[0]),
+ wide_int_storage::from (min, TYPE_PRECISION (type),
+ TYPE_SIGN (type)),
+ wide_int_storage::from (max, TYPE_PRECISION (type),
+ TYPE_SIGN (type)));
+ }
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Created phi ");
-/* Perform insertion of partially redundant values.
+/* Perform insertion of partially redundant or hoistable values.
For BLOCK, do the following:
1. Propagate the NEW_SETS of the dominator into the current block.
If the block has multiple predecessors,
2c. Insert a new PHI merging the values of the predecessors.
2d. Insert the new PHI, and the new expressions, into the
NEW_SETS set.
- 3. Recursively call ourselves on the dominator children of BLOCK.
-
- Steps 1, 2a, and 3 are done by insert_aux. 2b, 2c and 2d are done by
- do_regular_insertion and do_partial_insertion.
-
+ If the block has multiple successors,
+ 3a. Iterate over the ANTIC values for the block to see if
+ any of them are good candidates for hoisting.
+ 3b. If so, insert expressions computing the values in BLOCK,
+ and add the new expressions into the NEW_SETS set.
+ 4. Recursively call ourselves on the dominator children of BLOCK.
+
+ Steps 1, 2a, and 4 are done by insert_aux. 2b, 2c and 2d are done by
+ do_pre_regular_insertion and do_partial_insertion. 3a and 3b are
+ done in do_hoist_insertion.
*/
static bool
-do_regular_insertion (basic_block block, basic_block dom)
+do_pre_regular_insertion (basic_block block, basic_block dom)
{
bool new_stuff = false;
vec<pre_expr> exprs;
pre_expr expr;
- vec<pre_expr> avail = vNULL;
+ auto_vec<pre_expr> avail;
int i;
exprs = sorted_array_from_bitmap_set (ANTIC_IN (block));
and so not come across fake pred edges. */
gcc_assert (!(pred->flags & EDGE_FAKE));
bprime = pred->src;
+ /* We are looking at ANTIC_OUT of bprime. */
eprime = phi_translate (expr, ANTIC_IN (block), NULL,
bprime, block);
break;
}
- eprime = fully_constant_expression (eprime);
vprime = get_expr_value_id (eprime);
edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime),
vprime);
tree temp = make_temp_ssa_name (get_expr_type (expr),
NULL, "pretmp");
- gimple assign = gimple_build_assign (temp,
- edoubleprime->kind == CONSTANT ? PRE_EXPR_CONSTANT (edoubleprime) : PRE_EXPR_NAME (edoubleprime));
+ gassign *assign
+ = gimple_build_assign (temp,
+ edoubleprime->kind == CONSTANT ?
+ PRE_EXPR_CONSTANT (edoubleprime) :
+ PRE_EXPR_NAME (edoubleprime));
gimple_stmt_iterator gsi = gsi_after_labels (block);
gsi_insert_before (&gsi, assign, GSI_NEW_STMT);
In this case, we know that putting it earlier will enable us to
remove the later computation. */
-
static bool
-do_partial_partial_insertion (basic_block block, basic_block dom)
+do_pre_partial_partial_insertion (basic_block block, basic_block dom)
{
bool new_stuff = false;
vec<pre_expr> exprs;
break;
}
- eprime = fully_constant_expression (eprime);
vprime = get_expr_value_id (eprime);
edoubleprime = bitmap_find_leader (AVAIL_OUT (bprime), vprime);
avail[pred->dest_idx] = edoubleprime;
return new_stuff;
}
+/* Insert expressions in BLOCK to compute hoistable values up.
+ Return TRUE if something was inserted, otherwise return FALSE.
+ The caller has to make sure that BLOCK has at least two successors. */
+
static bool
-insert_aux (basic_block block)
+do_hoist_insertion (basic_block block)
{
- basic_block son;
+ edge e;
+ edge_iterator ei;
bool new_stuff = false;
+ unsigned i;
+ gimple_stmt_iterator last;
- if (block)
- {
- basic_block dom;
- dom = get_immediate_dominator (CDI_DOMINATORS, block);
+ /* At least two successors, or else... */
+ gcc_assert (EDGE_COUNT (block->succs) >= 2);
+
+ /* Check that all successors of BLOCK are dominated by block.
+ We could use dominated_by_p() for this, but actually there is a much
+ quicker check: any successor that is dominated by BLOCK can't have
+ more than one predecessor edge. */
+ FOR_EACH_EDGE (e, ei, block->succs)
+ if (! single_pred_p (e->dest))
+ return false;
+
+ /* Determine the insertion point. If we cannot safely insert before
+ the last stmt if we'd have to, bail out. */
+ last = gsi_last_bb (block);
+ if (!gsi_end_p (last)
+ && !is_ctrl_stmt (gsi_stmt (last))
+ && stmt_ends_bb_p (gsi_stmt (last)))
+ return false;
+
+ /* Compute the set of hoistable expressions from ANTIC_IN. First compute
+ hoistable values. */
+ bitmap_set hoistable_set;
+
+ /* A hoistable value must be in ANTIC_IN(block)
+ but not in AVAIL_OUT(BLOCK). */
+ bitmap_initialize (&hoistable_set.values, &grand_bitmap_obstack);
+ bitmap_and_compl (&hoistable_set.values,
+ &ANTIC_IN (block)->values, &AVAIL_OUT (block)->values);
+
+ /* Short-cut for a common case: hoistable_set is empty. */
+ if (bitmap_empty_p (&hoistable_set.values))
+ return false;
+
+ /* Compute which of the hoistable values is in AVAIL_OUT of
+ at least one of the successors of BLOCK. */
+ bitmap_head availout_in_some;
+ bitmap_initialize (&availout_in_some, &grand_bitmap_obstack);
+ FOR_EACH_EDGE (e, ei, block->succs)
+ /* Do not consider expressions solely because their availability
+ on loop exits. They'd be ANTIC-IN throughout the whole loop
+ and thus effectively hoisted across loops by combination of
+ PRE and hoisting. */
+ if (! loop_exit_edge_p (block->loop_father, e))
+ bitmap_ior_and_into (&availout_in_some, &hoistable_set.values,
+ &AVAIL_OUT (e->dest)->values);
+ bitmap_clear (&hoistable_set.values);
+
+ /* Short-cut for a common case: availout_in_some is empty. */
+ if (bitmap_empty_p (&availout_in_some))
+ return false;
+
+ /* Hack hoitable_set in-place so we can use sorted_array_from_bitmap_set. */
+ hoistable_set.values = availout_in_some;
+ hoistable_set.expressions = ANTIC_IN (block)->expressions;
+
+ /* Now finally construct the topological-ordered expression set. */
+ vec<pre_expr> exprs = sorted_array_from_bitmap_set (&hoistable_set);
+
+ bitmap_clear (&hoistable_set.values);
+
+ /* If there are candidate values for hoisting, insert expressions
+ strategically to make the hoistable expressions fully redundant. */
+ pre_expr expr;
+ FOR_EACH_VEC_ELT (exprs, i, expr)
+ {
+ /* While we try to sort expressions topologically above the
+ sorting doesn't work out perfectly. Catch expressions we
+ already inserted. */
+ unsigned int value_id = get_expr_value_id (expr);
+ if (bitmap_set_contains_value (AVAIL_OUT (block), value_id))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file,
+ "Already inserted expression for ");
+ print_pre_expr (dump_file, expr);
+ fprintf (dump_file, " (%04d)\n", value_id);
+ }
+ continue;
+ }
+
+ /* OK, we should hoist this value. Perform the transformation. */
+ pre_stats.hoist_insert++;
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file,
+ "Inserting expression in block %d for code hoisting: ",
+ block->index);
+ print_pre_expr (dump_file, expr);
+ fprintf (dump_file, " (%04d)\n", value_id);
+ }
+
+ gimple_seq stmts = NULL;
+ tree res = create_expression_by_pieces (block, expr, &stmts,
+ get_expr_type (expr));
+
+ /* Do not return true if expression creation ultimately
+ did not insert any statements. */
+ if (gimple_seq_empty_p (stmts))
+ res = NULL_TREE;
+ else
+ {
+ if (gsi_end_p (last) || is_ctrl_stmt (gsi_stmt (last)))
+ gsi_insert_seq_before (&last, stmts, GSI_SAME_STMT);
+ else
+ gsi_insert_seq_after (&last, stmts, GSI_NEW_STMT);
+ }
+
+ /* Make sure to not return true if expression creation ultimately
+ failed but also make sure to insert any stmts produced as they
+ are tracked in inserted_exprs. */
+ if (! res)
+ continue;
+
+ new_stuff = true;
+ }
+
+ exprs.release ();
+
+ return new_stuff;
+}
+
+/* Do a dominator walk on the control flow graph, and insert computations
+ of values as necessary for PRE and hoisting. */
+
+static bool
+insert_aux (basic_block block, bool do_pre, bool do_hoist)
+{
+ basic_block son;
+ bool new_stuff = false;
+
+ if (block)
+ {
+ basic_block dom;
+ dom = get_immediate_dominator (CDI_DOMINATORS, block);
if (dom)
{
unsigned i;
bitmap_iterator bi;
- bitmap_set_t newset = NEW_SETS (dom);
+ bitmap_set_t newset;
+
+ /* First, update the AVAIL_OUT set with anything we may have
+ inserted higher up in the dominator tree. */
+ newset = NEW_SETS (dom);
if (newset)
{
/* Note that we need to value_replace both NEW_SETS, and
bitmap_value_replace_in_set (AVAIL_OUT (block), expr);
}
}
- if (!single_pred_p (block))
+
+ /* Insert expressions for partial redundancies. */
+ if (do_pre && !single_pred_p (block))
{
- new_stuff |= do_regular_insertion (block, dom);
+ new_stuff |= do_pre_regular_insertion (block, dom);
if (do_partial_partial)
- new_stuff |= do_partial_partial_insertion (block, dom);
+ new_stuff |= do_pre_partial_partial_insertion (block, dom);
}
+
+ /* Insert expressions for hoisting. */
+ if (do_hoist && EDGE_COUNT (block->succs) >= 2)
+ new_stuff |= do_hoist_insertion (block);
}
}
for (son = first_dom_son (CDI_DOMINATORS, block);
son;
son = next_dom_son (CDI_DOMINATORS, son))
{
- new_stuff |= insert_aux (son);
+ new_stuff |= insert_aux (son, do_pre, do_hoist);
}
return new_stuff;
}
-/* Perform insertion of partially redundant values. */
+/* Perform insertion of partially redundant and hoistable values. */
static void
insert (void)
num_iterations++;
if (dump_file && dump_flags & TDF_DETAILS)
fprintf (dump_file, "Starting insert iteration %d\n", num_iterations);
- new_stuff = insert_aux (ENTRY_BLOCK_PTR_FOR_FN (cfun));
+ new_stuff = insert_aux (ENTRY_BLOCK_PTR_FOR_FN (cfun), flag_tree_pre,
+ flag_code_hoisting);
/* Clear the NEW sets before the next iteration. We have already
fully propagated its contents. */
basic_block *worklist;
size_t sp = 0;
unsigned i;
+ tree name;
/* We pretend that default definitions are defined in the entry block.
This includes function arguments and the static chain decl. */
- for (i = 1; i < num_ssa_names; ++i)
+ FOR_EACH_SSA_NAME (i, name, cfun)
{
- tree name = ssa_name (i);
pre_expr e;
- if (!name
- || !SSA_NAME_IS_DEFAULT_DEF (name)
+ if (!SSA_NAME_IS_DEFAULT_DEF (name)
|| has_zero_uses (name)
|| virtual_operand_p (name))
continue;
son = next_dom_son (CDI_DOMINATORS, son))
worklist[sp++] = son;
+ BB_LIVE_VOP_ON_EXIT (ENTRY_BLOCK_PTR_FOR_FN (cfun))
+ = ssa_default_def (cfun, gimple_vop (cfun));
+
/* Loop until the worklist is empty. */
while (sp)
{
- gimple_stmt_iterator gsi;
- gimple stmt;
+ gimple *stmt;
basic_block dom;
/* Pick a block from the worklist. */
its immediate dominator. */
dom = get_immediate_dominator (CDI_DOMINATORS, block);
if (dom)
- bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
+ {
+ bitmap_set_copy (AVAIL_OUT (block), AVAIL_OUT (dom));
+ BB_LIVE_VOP_ON_EXIT (block) = BB_LIVE_VOP_ON_EXIT (dom);
+ }
/* Generate values for PHI nodes. */
- for (gsi = gsi_start_phis (block); !gsi_end_p (gsi); gsi_next (&gsi))
+ for (gphi_iterator gsi = gsi_start_phis (block); !gsi_end_p (gsi);
+ gsi_next (&gsi))
{
- tree result = gimple_phi_result (gsi_stmt (gsi));
+ tree result = gimple_phi_result (gsi.phi ());
/* We have no need for virtual phis, as they don't represent
actual computations. */
if (virtual_operand_p (result))
- continue;
+ {
+ BB_LIVE_VOP_ON_EXIT (block) = result;
+ continue;
+ }
pre_expr e = get_or_alloc_expr_for_name (result);
add_to_value (get_expr_value_id (e), e);
/* Now compute value numbers and populate value sets with all
the expressions computed in BLOCK. */
- for (gsi = gsi_start_bb (block); !gsi_end_p (gsi); gsi_next (&gsi))
+ for (gimple_stmt_iterator gsi = gsi_start_bb (block); !gsi_end_p (gsi);
+ gsi_next (&gsi))
{
ssa_op_iter iter;
tree op;
bitmap_value_insert_into_set (AVAIL_OUT (block), e);
}
+ if (gimple_vdef (stmt))
+ BB_LIVE_VOP_ON_EXIT (block) = gimple_vdef (stmt);
+
if (gimple_has_side_effects (stmt)
|| stmt_could_throw_p (stmt)
|| is_gimple_debug (stmt))
case GIMPLE_CALL:
{
vn_reference_t ref;
+ vn_reference_s ref1;
pre_expr result = NULL;
- auto_vec<vn_reference_op_s> ops;
/* We can value number only calls to real functions. */
if (gimple_call_internal_p (stmt))
continue;
- copy_reference_ops_from_call (stmt, &ops);
- vn_reference_lookup_pieces (gimple_vuse (stmt), 0,
- gimple_expr_type (stmt),
- ops, &ref, VN_NOWALK);
+ vn_reference_lookup_call (as_a <gcall *> (stmt), &ref, &ref1);
if (!ref)
continue;
|| gimple_bb (SSA_NAME_DEF_STMT
(gimple_vuse (stmt))) != block)
{
- result = (pre_expr) pool_alloc (pre_expr_pool);
+ result = pre_expr_pool.allocate ();
result->kind = REFERENCE;
result->id = 0;
PRE_EXPR_REFERENCE (result) = ref;
&& vn_nary_may_trap (nary))
continue;
- result = (pre_expr) pool_alloc (pre_expr_pool);
+ result = pre_expr_pool.allocate ();
result->kind = NARY;
result->id = 0;
PRE_EXPR_NARY (result) = nary;
case VN_REFERENCE:
{
+ tree rhs1 = gimple_assign_rhs1 (stmt);
+ alias_set_type set = get_alias_set (rhs1);
+ vec<vn_reference_op_s> operands
+ = vn_reference_operands_for_lookup (rhs1);
vn_reference_t ref;
- vn_reference_lookup (gimple_assign_rhs1 (stmt),
- gimple_vuse (stmt),
- VN_WALK, &ref);
+ vn_reference_lookup_pieces (gimple_vuse (stmt), set,
+ TREE_TYPE (rhs1),
+ operands, &ref, VN_WALK);
if (!ref)
- continue;
+ {
+ operands.release ();
+ continue;
+ }
/* If the value of the reference is not invalidated in
this block until it is computed, add the expression
to EXP_GEN. */
if (gimple_vuse (stmt))
{
- gimple def_stmt;
+ gimple *def_stmt;
bool ok = true;
def_stmt = SSA_NAME_DEF_STMT (gimple_vuse (stmt));
while (!gimple_nop_p (def_stmt)
= SSA_NAME_DEF_STMT (gimple_vuse (def_stmt));
}
if (!ok)
- continue;
+ {
+ operands.release ();
+ continue;
+ }
+ }
+
+ /* If the load was value-numbered to another
+ load make sure we do not use its expression
+ for insertion if it wouldn't be a valid
+ replacement. */
+ /* At the momemt we have a testcase
+ for hoist insertion of aligned vs. misaligned
+ variants in gcc.dg/torture/pr65270-1.c thus
+ with just alignment to be considered we can
+ simply replace the expression in the hashtable
+ with the most conservative one. */
+ vn_reference_op_t ref1 = &ref->operands.last ();
+ while (ref1->opcode != TARGET_MEM_REF
+ && ref1->opcode != MEM_REF
+ && ref1 != &ref->operands[0])
+ --ref1;
+ vn_reference_op_t ref2 = &operands.last ();
+ while (ref2->opcode != TARGET_MEM_REF
+ && ref2->opcode != MEM_REF
+ && ref2 != &operands[0])
+ --ref2;
+ if ((ref1->opcode == TARGET_MEM_REF
+ || ref1->opcode == MEM_REF)
+ && (TYPE_ALIGN (ref1->type)
+ > TYPE_ALIGN (ref2->type)))
+ ref1->type
+ = build_aligned_type (ref1->type,
+ TYPE_ALIGN (ref2->type));
+ /* TBAA behavior is an obvious part so make sure
+ that the hashtable one covers this as well
+ by adjusting the ref alias set and its base. */
+ if (ref->set == set
+ || alias_set_subset_of (set, ref->set))
+ ;
+ else if (alias_set_subset_of (ref->set, set))
+ {
+ ref->set = set;
+ if (ref1->opcode == MEM_REF)
+ ref1->op0 = fold_convert (TREE_TYPE (ref2->op0),
+ ref1->op0);
+ else
+ ref1->op2 = fold_convert (TREE_TYPE (ref2->op2),
+ ref1->op2);
+ }
+ else
+ {
+ ref->set = 0;
+ if (ref1->opcode == MEM_REF)
+ ref1->op0 = fold_convert (ptr_type_node,
+ ref1->op0);
+ else
+ ref1->op2 = fold_convert (ptr_type_node,
+ ref1->op2);
}
+ operands.release ();
- result = (pre_expr) pool_alloc (pre_expr_pool);
+ result = pre_expr_pool.allocate ();
result->kind = REFERENCE;
result->id = 0;
PRE_EXPR_REFERENCE (result) = ref;
/* Local state for the eliminate domwalk. */
-static vec<gimple> el_to_remove;
-static vec<gimple> el_to_update;
+static vec<gimple *> el_to_remove;
+static vec<gimple *> el_to_fixup;
static unsigned int el_todo;
static vec<tree> el_avail;
static vec<tree> el_avail_stack;
{
if (el_avail.length () <= SSA_NAME_VERSION (valnum))
el_avail.safe_grow_cleared (SSA_NAME_VERSION (valnum) + 1);
+ tree pushop = op;
+ if (el_avail[SSA_NAME_VERSION (valnum)])
+ pushop = el_avail[SSA_NAME_VERSION (valnum)];
+ el_avail_stack.safe_push (pushop);
el_avail[SSA_NAME_VERSION (valnum)] = op;
- el_avail_stack.safe_push (op);
}
}
static tree
eliminate_insert (gimple_stmt_iterator *gsi, tree val)
{
- tree expr = vn_get_expr_for (val);
- if (!CONVERT_EXPR_P (expr)
- && TREE_CODE (expr) != VIEW_CONVERT_EXPR)
+ gimple *stmt = gimple_seq_first_stmt (VN_INFO (val)->expr);
+ if (!is_gimple_assign (stmt)
+ || (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
+ && gimple_assign_rhs_code (stmt) != VIEW_CONVERT_EXPR
+ && gimple_assign_rhs_code (stmt) != BIT_FIELD_REF))
return NULL_TREE;
- tree op = TREE_OPERAND (expr, 0);
+ tree op = gimple_assign_rhs1 (stmt);
+ if (gimple_assign_rhs_code (stmt) == VIEW_CONVERT_EXPR
+ || gimple_assign_rhs_code (stmt) == BIT_FIELD_REF)
+ op = TREE_OPERAND (op, 0);
tree leader = TREE_CODE (op) == SSA_NAME ? eliminate_avail (op) : op;
if (!leader)
return NULL_TREE;
- tree res = make_temp_ssa_name (TREE_TYPE (val), NULL, "pretmp");
- gimple tem = gimple_build_assign (res,
- fold_build1 (TREE_CODE (expr),
- TREE_TYPE (expr), leader));
- gsi_insert_before (gsi, tem, GSI_SAME_STMT);
+ gimple_seq stmts = NULL;
+ tree res;
+ if (gimple_assign_rhs_code (stmt) == BIT_FIELD_REF)
+ res = gimple_build (&stmts, BIT_FIELD_REF,
+ TREE_TYPE (val), leader,
+ TREE_OPERAND (gimple_assign_rhs1 (stmt), 1),
+ TREE_OPERAND (gimple_assign_rhs1 (stmt), 2));
+ else
+ res = gimple_build (&stmts, gimple_assign_rhs_code (stmt),
+ TREE_TYPE (val), leader);
+ gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
VN_INFO_GET (res)->valnum = val;
if (TREE_CODE (leader) == SSA_NAME)
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "Inserted ");
- print_gimple_stmt (dump_file, tem, 0, 0);
+ print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (res), 0, 0);
}
return res;
class eliminate_dom_walker : public dom_walker
{
public:
- eliminate_dom_walker (cdi_direction direction) : dom_walker (direction) {}
+ eliminate_dom_walker (cdi_direction direction, bool do_pre_)
+ : dom_walker (direction), do_pre (do_pre_) {}
- virtual void before_dom_children (basic_block);
+ virtual edge before_dom_children (basic_block);
virtual void after_dom_children (basic_block);
+
+ bool do_pre;
};
/* Perform elimination for the basic-block B during the domwalk. */
-void
+edge
eliminate_dom_walker::before_dom_children (basic_block b)
{
- gimple_stmt_iterator gsi;
- gimple stmt;
-
/* Mark new bb. */
el_avail_stack.safe_push (NULL_TREE);
- for (gsi = gsi_start_phis (b); !gsi_end_p (gsi);)
+ /* ??? If we do nothing for unreachable blocks then this will confuse
+ tailmerging. Eventually we can reduce its reliance on SCCVN now
+ that we fully copy/constant-propagate (most) things. */
+
+ for (gphi_iterator gsi = gsi_start_phis (b); !gsi_end_p (gsi);)
{
- gimple stmt, phi = gsi_stmt (gsi);
- tree sprime = NULL_TREE, res = PHI_RESULT (phi);
- gimple_stmt_iterator gsi2;
-
- /* We want to perform redundant PHI elimination. Do so by
- replacing the PHI with a single copy if possible.
- Do not touch inserted, single-argument or virtual PHIs. */
- if (gimple_phi_num_args (phi) == 1
- || virtual_operand_p (res))
- {
- gsi_next (&gsi);
- continue;
- }
+ gphi *phi = gsi.phi ();
+ tree res = PHI_RESULT (phi);
- sprime = eliminate_avail (res);
- if (!sprime
- || sprime == res)
+ if (virtual_operand_p (res))
{
- eliminate_push_avail (res);
gsi_next (&gsi);
continue;
}
- else if (is_gimple_min_invariant (sprime))
- {
- if (!useless_type_conversion_p (TREE_TYPE (res),
- TREE_TYPE (sprime)))
- sprime = fold_convert (TREE_TYPE (res), sprime);
- }
- if (dump_file && (dump_flags & TDF_DETAILS))
+ tree sprime = eliminate_avail (res);
+ if (sprime
+ && sprime != res)
{
- fprintf (dump_file, "Replaced redundant PHI node defining ");
- print_generic_expr (dump_file, res, 0);
- fprintf (dump_file, " with ");
- print_generic_expr (dump_file, sprime, 0);
- fprintf (dump_file, "\n");
- }
-
- remove_phi_node (&gsi, false);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Replaced redundant PHI node defining ");
+ print_generic_expr (dump_file, res, 0);
+ fprintf (dump_file, " with ");
+ print_generic_expr (dump_file, sprime, 0);
+ fprintf (dump_file, "\n");
+ }
- if (inserted_exprs
- && !bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (res))
- && TREE_CODE (sprime) == SSA_NAME)
- gimple_set_plf (SSA_NAME_DEF_STMT (sprime), NECESSARY, true);
-
- if (!useless_type_conversion_p (TREE_TYPE (res), TREE_TYPE (sprime)))
- sprime = fold_convert (TREE_TYPE (res), sprime);
- stmt = gimple_build_assign (res, sprime);
- gimple_set_plf (stmt, NECESSARY, gimple_plf (phi, NECESSARY));
-
- gsi2 = gsi_after_labels (b);
- gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
- /* Queue the copy for eventual removal. */
- el_to_remove.safe_push (stmt);
- /* If we inserted this PHI node ourself, it's not an elimination. */
- if (inserted_exprs
- && bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (res)))
- pre_stats.phis--;
- else
- pre_stats.eliminations++;
- }
+ /* If we inserted this PHI node ourself, it's not an elimination. */
+ if (inserted_exprs
+ && bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (res)))
+ pre_stats.phis--;
+ else
+ pre_stats.eliminations++;
- for (gsi = gsi_start_bb (b); !gsi_end_p (gsi); gsi_next (&gsi))
- {
- tree lhs = NULL_TREE;
- tree rhs = NULL_TREE;
+ /* If we will propagate into all uses don't bother to do
+ anything. */
+ if (may_propagate_copy (res, sprime))
+ {
+ /* Mark the PHI for removal. */
+ el_to_remove.safe_push (phi);
+ gsi_next (&gsi);
+ continue;
+ }
- stmt = gsi_stmt (gsi);
+ remove_phi_node (&gsi, false);
- if (gimple_has_lhs (stmt))
- lhs = gimple_get_lhs (stmt);
+ if (inserted_exprs
+ && !bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (res))
+ && TREE_CODE (sprime) == SSA_NAME)
+ gimple_set_plf (SSA_NAME_DEF_STMT (sprime), NECESSARY, true);
- if (gimple_assign_single_p (stmt))
- rhs = gimple_assign_rhs1 (stmt);
+ if (!useless_type_conversion_p (TREE_TYPE (res), TREE_TYPE (sprime)))
+ sprime = fold_convert (TREE_TYPE (res), sprime);
+ gimple *stmt = gimple_build_assign (res, sprime);
+ /* ??? It cannot yet be necessary (DOM walk). */
+ gimple_set_plf (stmt, NECESSARY, gimple_plf (phi, NECESSARY));
- /* Lookup the RHS of the expression, see if we have an
- available computation for it. If so, replace the RHS with
- the available computation. */
- if (gimple_has_lhs (stmt)
- && TREE_CODE (lhs) == SSA_NAME
- && !gimple_has_volatile_ops (stmt))
- {
- tree sprime;
- gimple orig_stmt = stmt;
+ gimple_stmt_iterator gsi2 = gsi_after_labels (b);
+ gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
+ continue;
+ }
- sprime = eliminate_avail (lhs);
- /* If there is no usable leader mark lhs as leader for its value. */
- if (!sprime)
- eliminate_push_avail (lhs);
+ eliminate_push_avail (res);
+ gsi_next (&gsi);
+ }
+ for (gimple_stmt_iterator gsi = gsi_start_bb (b);
+ !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ tree sprime = NULL_TREE;
+ gimple *stmt = gsi_stmt (gsi);
+ tree lhs = gimple_get_lhs (stmt);
+ if (lhs && TREE_CODE (lhs) == SSA_NAME
+ && !gimple_has_volatile_ops (stmt)
/* See PR43491. Do not replace a global register variable when
it is a the RHS of an assignment. Do replace local register
variables since gcc does not guarantee a local variable will
be allocated in register.
- Do not perform copy propagation or undo constant propagation. */
- if (gimple_assign_single_p (stmt)
- && (TREE_CODE (rhs) == SSA_NAME
- || is_gimple_min_invariant (rhs)
- || (TREE_CODE (rhs) == VAR_DECL
- && is_global_var (rhs)
- && DECL_HARD_REGISTER (rhs))))
- continue;
-
+ ??? The fix isn't effective here. This should instead
+ be ensured by not value-numbering them the same but treating
+ them like volatiles? */
+ && !(gimple_assign_single_p (stmt)
+ && (TREE_CODE (gimple_assign_rhs1 (stmt)) == VAR_DECL
+ && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt))
+ && is_global_var (gimple_assign_rhs1 (stmt)))))
+ {
+ sprime = eliminate_avail (lhs);
if (!sprime)
{
/* If there is no existing usable leader but SCCVN thinks
if (val != VN_TOP
&& TREE_CODE (val) == SSA_NAME
&& VN_INFO (val)->needs_insertion
- && VN_INFO (val)->expr != NULL_TREE
+ && VN_INFO (val)->expr != NULL
&& (sprime = eliminate_insert (&gsi, val)) != NULL_TREE)
eliminate_push_avail (sprime);
}
- else if (is_gimple_min_invariant (sprime))
- {
- /* If there is no existing leader but SCCVN knows this
- value is constant, use that constant. */
- if (!useless_type_conversion_p (TREE_TYPE (lhs),
- TREE_TYPE (sprime)))
- sprime = fold_convert (TREE_TYPE (lhs), sprime);
-
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Replaced ");
- print_gimple_expr (dump_file, stmt, 0, 0);
- fprintf (dump_file, " with ");
- print_generic_expr (dump_file, sprime, 0);
- fprintf (dump_file, " in ");
- print_gimple_stmt (dump_file, stmt, 0, 0);
- }
- pre_stats.eliminations++;
- propagate_tree_value_into_stmt (&gsi, sprime);
- stmt = gsi_stmt (gsi);
- update_stmt (stmt);
- /* If we removed EH side-effects from the statement, clean
- its EH information. */
- if (maybe_clean_or_replace_eh_stmt (orig_stmt, stmt))
+ /* If this now constitutes a copy duplicate points-to
+ and range info appropriately. This is especially
+ important for inserted code. See tree-ssa-copy.c
+ for similar code. */
+ if (sprime
+ && TREE_CODE (sprime) == SSA_NAME)
+ {
+ basic_block sprime_b = gimple_bb (SSA_NAME_DEF_STMT (sprime));
+ if (POINTER_TYPE_P (TREE_TYPE (lhs))
+ && VN_INFO_PTR_INFO (lhs)
+ && ! VN_INFO_PTR_INFO (sprime))
{
- bitmap_set_bit (need_eh_cleanup,
- gimple_bb (stmt)->index);
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " Removed EH side-effects.\n");
+ duplicate_ssa_name_ptr_info (sprime,
+ VN_INFO_PTR_INFO (lhs));
+ if (b != sprime_b)
+ mark_ptr_info_alignment_unknown
+ (SSA_NAME_PTR_INFO (sprime));
}
- continue;
+ else if (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+ && VN_INFO_RANGE_INFO (lhs)
+ && ! VN_INFO_RANGE_INFO (sprime)
+ && b == sprime_b)
+ duplicate_ssa_name_range_info (sprime,
+ VN_INFO_RANGE_TYPE (lhs),
+ VN_INFO_RANGE_INFO (lhs));
}
+ /* Inhibit the use of an inserted PHI on a loop header when
+ the address of the memory reference is a simple induction
+ variable. In other cases the vectorizer won't do anything
+ anyway (either it's loop invariant or a complicated
+ expression). */
if (sprime
- && sprime != lhs
- && (rhs == NULL_TREE
- || TREE_CODE (rhs) != SSA_NAME
- || may_propagate_copy (rhs, sprime)))
+ && TREE_CODE (sprime) == SSA_NAME
+ && do_pre
+ && (flag_tree_loop_vectorize || flag_tree_parallelize_loops > 1)
+ && loop_outer (b->loop_father)
+ && has_zero_uses (sprime)
+ && bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (sprime))
+ && gimple_assign_load_p (stmt))
{
- bool can_make_abnormal_goto
- = is_gimple_call (stmt)
- && stmt_can_make_abnormal_goto (stmt);
-
- gcc_assert (sprime != rhs);
-
- /* Inhibit the use of an inserted PHI on a loop header when
- the address of the memory reference is a simple induction
- variable. In other cases the vectorizer won't do anything
- anyway (either it's loop invariant or a complicated
- expression). */
- if (flag_tree_loop_vectorize
- && gimple_assign_single_p (stmt)
- && TREE_CODE (sprime) == SSA_NAME
- && loop_outer (b->loop_father))
+ gimple *def_stmt = SSA_NAME_DEF_STMT (sprime);
+ basic_block def_bb = gimple_bb (def_stmt);
+ if (gimple_code (def_stmt) == GIMPLE_PHI
+ && def_bb->loop_father->header == def_bb)
{
- gimple def_stmt = SSA_NAME_DEF_STMT (sprime);
- basic_block def_bb = gimple_bb (def_stmt);
- if (gimple_code (def_stmt) == GIMPLE_PHI
- && b->loop_father->header == def_bb
- && has_zero_uses (sprime))
+ loop_p loop = def_bb->loop_father;
+ ssa_op_iter iter;
+ tree op;
+ bool found = false;
+ FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
{
- ssa_op_iter iter;
- tree op;
- bool found = false;
- FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE)
+ affine_iv iv;
+ def_bb = gimple_bb (SSA_NAME_DEF_STMT (op));
+ if (def_bb
+ && flow_bb_inside_loop_p (loop, def_bb)
+ && simple_iv (loop, loop, op, &iv, true))
{
- affine_iv iv;
- def_bb = gimple_bb (SSA_NAME_DEF_STMT (op));
- if (def_bb
- && flow_bb_inside_loop_p (b->loop_father,
- def_bb)
- && simple_iv (b->loop_father,
- b->loop_father, op, &iv, true))
- {
- found = true;
- break;
- }
+ found = true;
+ break;
}
- if (found)
+ }
+ if (found)
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "Not replacing ");
- print_gimple_expr (dump_file, stmt, 0, 0);
- fprintf (dump_file, " with ");
- print_generic_expr (dump_file, sprime, 0);
- fprintf (dump_file, " which would add a loop"
- " carried dependence to loop %d\n",
- b->loop_father->num);
- }
- continue;
+ fprintf (dump_file, "Not replacing ");
+ print_gimple_expr (dump_file, stmt, 0, 0);
+ fprintf (dump_file, " with ");
+ print_generic_expr (dump_file, sprime, 0);
+ fprintf (dump_file, " which would add a loop"
+ " carried dependence to loop %d\n",
+ loop->num);
}
+ /* Don't keep sprime available. */
+ sprime = NULL_TREE;
}
}
+ }
+
+ if (sprime)
+ {
+ /* If we can propagate the value computed for LHS into
+ all uses don't bother doing anything with this stmt. */
+ if (may_propagate_copy (lhs, sprime))
+ {
+ /* Mark it for removal. */
+ el_to_remove.safe_push (stmt);
+
+ /* ??? Don't count copy/constant propagations. */
+ if (gimple_assign_single_p (stmt)
+ && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
+ || gimple_assign_rhs1 (stmt) == sprime))
+ continue;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Replaced ");
+ print_gimple_expr (dump_file, stmt, 0, 0);
+ fprintf (dump_file, " with ");
+ print_generic_expr (dump_file, sprime, 0);
+ fprintf (dump_file, " in all uses of ");
+ print_gimple_stmt (dump_file, stmt, 0, 0);
+ }
+
+ pre_stats.eliminations++;
+ continue;
+ }
+
+ /* If this is an assignment from our leader (which
+ happens in the case the value-number is a constant)
+ then there is nothing to do. */
+ if (gimple_assign_single_p (stmt)
+ && sprime == gimple_assign_rhs1 (stmt))
+ continue;
+
+ /* Else replace its RHS. */
+ bool can_make_abnormal_goto
+ = is_gimple_call (stmt)
+ && stmt_can_make_abnormal_goto (stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
{
if (TREE_CODE (sprime) == SSA_NAME)
gimple_set_plf (SSA_NAME_DEF_STMT (sprime),
NECESSARY, true);
- /* We need to make sure the new and old types actually match,
- which may require adding a simple cast, which fold_convert
- will do for us. */
- if ((!rhs || TREE_CODE (rhs) != SSA_NAME)
- && !useless_type_conversion_p (gimple_expr_type (stmt),
- TREE_TYPE (sprime)))
- sprime = fold_convert (gimple_expr_type (stmt), sprime);
pre_stats.eliminations++;
+ gimple *orig_stmt = stmt;
+ if (!useless_type_conversion_p (TREE_TYPE (lhs),
+ TREE_TYPE (sprime)))
+ sprime = fold_convert (TREE_TYPE (lhs), sprime);
+ tree vdef = gimple_vdef (stmt);
+ tree vuse = gimple_vuse (stmt);
propagate_tree_value_into_stmt (&gsi, sprime);
stmt = gsi_stmt (gsi);
update_stmt (stmt);
+ if (vdef != gimple_vdef (stmt))
+ VN_INFO (vdef)->valnum = vuse;
/* If we removed EH side-effects from the statement, clean
its EH information. */
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, " Removed AB side-effects.\n");
}
+
+ continue;
}
}
+
/* If the statement is a scalar store, see if the expression
- has the same value number as its rhs. If so, the store is
- dead. */
- else if (gimple_assign_single_p (stmt)
- && !gimple_has_volatile_ops (stmt)
- && !is_gimple_reg (gimple_assign_lhs (stmt))
- && (TREE_CODE (rhs) == SSA_NAME
- || is_gimple_min_invariant (rhs)))
+ has the same value number as its rhs. If so, the store is
+ dead. */
+ if (gimple_assign_single_p (stmt)
+ && !gimple_has_volatile_ops (stmt)
+ && !is_gimple_reg (gimple_assign_lhs (stmt))
+ && (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
+ || is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
{
tree val;
- val = vn_reference_lookup (gimple_assign_lhs (stmt),
- gimple_vuse (stmt), VN_WALK, NULL);
+ tree rhs = gimple_assign_rhs1 (stmt);
+ vn_reference_t vnresult;
+ val = vn_reference_lookup (lhs, gimple_vuse (stmt), VN_WALKREWRITE,
+ &vnresult, false);
if (TREE_CODE (rhs) == SSA_NAME)
rhs = VN_INFO (rhs)->valnum;
if (val
&& operand_equal_p (val, rhs, 0))
{
- if (dump_file && (dump_flags & TDF_DETAILS))
+ /* We can only remove the later store if the former aliases
+ at least all accesses the later one does or if the store
+ was to readonly memory storing the same value. */
+ alias_set_type set = get_alias_set (lhs);
+ if (! vnresult
+ || vnresult->set == set
+ || alias_set_subset_of (set, vnresult->set))
{
- fprintf (dump_file, "Deleted redundant store ");
- print_gimple_stmt (dump_file, stmt, 0, 0);
- }
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Deleted redundant store ");
+ print_gimple_stmt (dump_file, stmt, 0, 0);
+ }
- /* Queue stmt for removal. */
- el_to_remove.safe_push (stmt);
+ /* Queue stmt for removal. */
+ el_to_remove.safe_push (stmt);
+ continue;
+ }
}
}
- /* Visit COND_EXPRs and fold the comparison with the
- available value-numbers. */
- else if (gimple_code (stmt) == GIMPLE_COND)
+
+ /* If this is a control statement value numbering left edges
+ unexecuted on force the condition in a way consistent with
+ that. */
+ if (gcond *cond = dyn_cast <gcond *> (stmt))
{
- tree op0 = gimple_cond_lhs (stmt);
- tree op1 = gimple_cond_rhs (stmt);
- tree result;
-
- if (TREE_CODE (op0) == SSA_NAME)
- op0 = VN_INFO (op0)->valnum;
- if (TREE_CODE (op1) == SSA_NAME)
- op1 = VN_INFO (op1)->valnum;
- result = fold_binary (gimple_cond_code (stmt), boolean_type_node,
- op0, op1);
- if (result && TREE_CODE (result) == INTEGER_CST)
+ if ((EDGE_SUCC (b, 0)->flags & EDGE_EXECUTABLE)
+ ^ (EDGE_SUCC (b, 1)->flags & EDGE_EXECUTABLE))
{
- if (integer_zerop (result))
- gimple_cond_make_false (stmt);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Removing unexecutable edge from ");
+ print_gimple_stmt (dump_file, stmt, 0, 0);
+ }
+ if (((EDGE_SUCC (b, 0)->flags & EDGE_TRUE_VALUE) != 0)
+ == ((EDGE_SUCC (b, 0)->flags & EDGE_EXECUTABLE) != 0))
+ gimple_cond_make_true (cond);
else
- gimple_cond_make_true (stmt);
- update_stmt (stmt);
- el_todo = TODO_cleanup_cfg;
+ gimple_cond_make_false (cond);
+ update_stmt (cond);
+ el_todo |= TODO_cleanup_cfg;
+ continue;
}
}
- /* Visit indirect calls and turn them into direct calls if
- possible. */
- if (is_gimple_call (stmt))
+
+ bool can_make_abnormal_goto = stmt_can_make_abnormal_goto (stmt);
+ bool was_noreturn = (is_gimple_call (stmt)
+ && gimple_call_noreturn_p (stmt));
+ tree vdef = gimple_vdef (stmt);
+ tree vuse = gimple_vuse (stmt);
+
+ /* If we didn't replace the whole stmt (or propagate the result
+ into all uses), replace all uses on this stmt with their
+ leaders. */
+ use_operand_p use_p;
+ ssa_op_iter iter;
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
{
- tree orig_fn = gimple_call_fn (stmt);
- tree fn;
- if (!orig_fn)
+ tree use = USE_FROM_PTR (use_p);
+ /* ??? The call code above leaves stmt operands un-updated. */
+ if (TREE_CODE (use) != SSA_NAME)
continue;
- if (TREE_CODE (orig_fn) == SSA_NAME)
- fn = VN_INFO (orig_fn)->valnum;
- else if (TREE_CODE (orig_fn) == OBJ_TYPE_REF
- && TREE_CODE (OBJ_TYPE_REF_EXPR (orig_fn)) == SSA_NAME)
+ tree sprime = eliminate_avail (use);
+ if (sprime && sprime != use
+ && may_propagate_copy (use, sprime)
+ /* We substitute into debug stmts to avoid excessive
+ debug temporaries created by removed stmts, but we need
+ to avoid doing so for inserted sprimes as we never want
+ to create debug temporaries for them. */
+ && (!inserted_exprs
+ || TREE_CODE (sprime) != SSA_NAME
+ || !is_gimple_debug (stmt)
+ || !bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (sprime))))
{
- fn = VN_INFO (OBJ_TYPE_REF_EXPR (orig_fn))->valnum;
- if (!gimple_call_addr_fndecl (fn))
- {
- fn = ipa_intraprocedural_devirtualization (stmt);
- if (fn)
- fn = build_fold_addr_expr (fn);
- }
+ propagate_value (use_p, sprime);
+ gimple_set_modified (stmt, true);
+ if (TREE_CODE (sprime) == SSA_NAME
+ && !is_gimple_debug (stmt))
+ gimple_set_plf (SSA_NAME_DEF_STMT (sprime),
+ NECESSARY, true);
}
- else
- continue;
- if (gimple_call_addr_fndecl (fn) != NULL_TREE
- && useless_type_conversion_p (TREE_TYPE (orig_fn),
- TREE_TYPE (fn)))
- {
- bool can_make_abnormal_goto
- = stmt_can_make_abnormal_goto (stmt);
- bool was_noreturn = gimple_call_noreturn_p (stmt);
+ }
- if (dump_file && (dump_flags & TDF_DETAILS))
+ /* Visit indirect calls and turn them into direct calls if
+ possible using the devirtualization machinery. */
+ if (gcall *call_stmt = dyn_cast <gcall *> (stmt))
+ {
+ tree fn = gimple_call_fn (call_stmt);
+ if (fn
+ && flag_devirtualize
+ && virtual_method_call_p (fn))
+ {
+ tree otr_type = obj_type_ref_class (fn);
+ tree instance;
+ ipa_polymorphic_call_context context (current_function_decl, fn, stmt, &instance);
+ bool final;
+
+ context.get_dynamic_type (instance, OBJ_TYPE_REF_OBJECT (fn), otr_type, stmt);
+
+ vec <cgraph_node *>targets
+ = possible_polymorphic_call_targets (obj_type_ref_class (fn),
+ tree_to_uhwi
+ (OBJ_TYPE_REF_TOKEN (fn)),
+ context,
+ &final);
+ if (dump_file)
+ dump_possible_polymorphic_call_targets (dump_file,
+ obj_type_ref_class (fn),
+ tree_to_uhwi
+ (OBJ_TYPE_REF_TOKEN (fn)),
+ context);
+ if (final && targets.length () <= 1 && dbg_cnt (devirt))
{
- fprintf (dump_file, "Replacing call target with ");
- print_generic_expr (dump_file, fn, 0);
- fprintf (dump_file, " in ");
- print_gimple_stmt (dump_file, stmt, 0, 0);
+ tree fn;
+ if (targets.length () == 1)
+ fn = targets[0]->decl;
+ else
+ fn = builtin_decl_implicit (BUILT_IN_UNREACHABLE);
+ if (dump_enabled_p ())
+ {
+ location_t loc = gimple_location_safe (stmt);
+ dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loc,
+ "converting indirect call to "
+ "function %s\n",
+ lang_hooks.decl_printable_name (fn, 2));
+ }
+ gimple_call_set_fndecl (call_stmt, fn);
+ /* If changing the call to __builtin_unreachable
+ or similar noreturn function, adjust gimple_call_fntype
+ too. */
+ if (gimple_call_noreturn_p (call_stmt)
+ && VOID_TYPE_P (TREE_TYPE (TREE_TYPE (fn)))
+ && TYPE_ARG_TYPES (TREE_TYPE (fn))
+ && (TREE_VALUE (TYPE_ARG_TYPES (TREE_TYPE (fn)))
+ == void_type_node))
+ gimple_call_set_fntype (call_stmt, TREE_TYPE (fn));
+ maybe_remove_unused_call_args (cfun, call_stmt);
+ gimple_set_modified (stmt, true);
}
+ }
+ }
- gimple_call_set_fn (stmt, fn);
- el_to_update.safe_push (stmt);
-
+ if (gimple_modified_p (stmt))
+ {
+ /* If a formerly non-invariant ADDR_EXPR is turned into an
+ invariant one it was on a separate stmt. */
+ if (gimple_assign_single_p (stmt)
+ && TREE_CODE (gimple_assign_rhs1 (stmt)) == ADDR_EXPR)
+ recompute_tree_invariant_for_addr_expr (gimple_assign_rhs1 (stmt));
+ gimple *old_stmt = stmt;
+ if (is_gimple_call (stmt))
+ {
+ /* ??? Only fold calls inplace for now, this may create new
+ SSA names which in turn will confuse free_scc_vn SSA name
+ release code. */
+ fold_stmt_inplace (&gsi);
/* When changing a call into a noreturn call, cfg cleanup
is needed to fix up the noreturn call. */
if (!was_noreturn && gimple_call_noreturn_p (stmt))
+ el_to_fixup.safe_push (stmt);
+ }
+ else
+ {
+ fold_stmt (&gsi);
+ stmt = gsi_stmt (gsi);
+ if ((gimple_code (stmt) == GIMPLE_COND
+ && (gimple_cond_true_p (as_a <gcond *> (stmt))
+ || gimple_cond_false_p (as_a <gcond *> (stmt))))
+ || (gimple_code (stmt) == GIMPLE_SWITCH
+ && TREE_CODE (gimple_switch_index (
+ as_a <gswitch *> (stmt)))
+ == INTEGER_CST))
el_todo |= TODO_cleanup_cfg;
+ }
+ /* If we removed EH side-effects from the statement, clean
+ its EH information. */
+ if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
+ {
+ bitmap_set_bit (need_eh_cleanup,
+ gimple_bb (stmt)->index);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " Removed EH side-effects.\n");
+ }
+ /* Likewise for AB side-effects. */
+ if (can_make_abnormal_goto
+ && !stmt_can_make_abnormal_goto (stmt))
+ {
+ bitmap_set_bit (need_ab_cleanup,
+ gimple_bb (stmt)->index);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " Removed AB side-effects.\n");
+ }
+ update_stmt (stmt);
+ if (vdef != gimple_vdef (stmt))
+ VN_INFO (vdef)->valnum = vuse;
+ }
- /* If we removed EH side-effects from the statement, clean
- its EH information. */
- if (maybe_clean_or_replace_eh_stmt (stmt, stmt))
- {
- bitmap_set_bit (need_eh_cleanup,
- gimple_bb (stmt)->index);
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " Removed EH side-effects.\n");
- }
-
- /* Likewise for AB side-effects. */
- if (can_make_abnormal_goto
- && !stmt_can_make_abnormal_goto (stmt))
- {
- bitmap_set_bit (need_ab_cleanup,
- gimple_bb (stmt)->index);
- if (dump_file && (dump_flags & TDF_DETAILS))
- fprintf (dump_file, " Removed AB side-effects.\n");
- }
+ /* Make new values available - for fully redundant LHS we
+ continue with the next stmt above and skip this. */
+ def_operand_p defp;
+ FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_DEF)
+ eliminate_push_avail (DEF_FROM_PTR (defp));
+ }
- /* Changing an indirect call to a direct call may
- have exposed different semantics. This may
- require an SSA update. */
- el_todo |= TODO_update_ssa_only_virtuals;
+ /* Replace destination PHI arguments. */
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, b->succs)
+ {
+ for (gphi_iterator gsi = gsi_start_phis (e->dest);
+ !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ gphi *phi = gsi.phi ();
+ use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
+ tree arg = USE_FROM_PTR (use_p);
+ if (TREE_CODE (arg) != SSA_NAME
+ || virtual_operand_p (arg))
+ continue;
+ tree sprime = eliminate_avail (arg);
+ if (sprime && may_propagate_copy (arg, sprime))
+ {
+ propagate_value (use_p, sprime);
+ if (TREE_CODE (sprime) == SSA_NAME)
+ gimple_set_plf (SSA_NAME_DEF_STMT (sprime), NECESSARY, true);
}
}
}
+ return NULL;
}
/* Make no longer available leaders no longer available. */
{
tree entry;
while ((entry = el_avail_stack.pop ()) != NULL_TREE)
- el_avail[SSA_NAME_VERSION (VN_INFO (entry)->valnum)] = NULL_TREE;
+ {
+ tree valnum = VN_INFO (entry)->valnum;
+ tree old = el_avail[SSA_NAME_VERSION (valnum)];
+ if (old == entry)
+ el_avail[SSA_NAME_VERSION (valnum)] = NULL_TREE;
+ else
+ el_avail[SSA_NAME_VERSION (valnum)] = entry;
+ }
}
/* Eliminate fully redundant computations. */
static unsigned int
-eliminate (void)
+eliminate (bool do_pre)
{
gimple_stmt_iterator gsi;
- gimple stmt;
- unsigned i;
+ gimple *stmt;
need_eh_cleanup = BITMAP_ALLOC (NULL);
need_ab_cleanup = BITMAP_ALLOC (NULL);
el_to_remove.create (0);
- el_to_update.create (0);
+ el_to_fixup.create (0);
el_todo = 0;
- el_avail.create (0);
+ el_avail.create (num_ssa_names);
el_avail_stack.create (0);
- eliminate_dom_walker (CDI_DOMINATORS).walk (cfun->cfg->x_entry_block_ptr);
+ eliminate_dom_walker (CDI_DOMINATORS,
+ do_pre).walk (cfun->cfg->x_entry_block_ptr);
el_avail.release ();
el_avail_stack.release ();
/* We cannot remove stmts during BB walk, especially not release SSA
names there as this confuses the VN machinery. The stmts ending
- up in el_to_remove are either stores or simple copies. */
- FOR_EACH_VEC_ELT (el_to_remove, i, stmt)
+ up in el_to_remove are either stores or simple copies.
+ Remove stmts in reverse order to make debug stmt creation possible. */
+ while (!el_to_remove.is_empty ())
{
- tree lhs = gimple_assign_lhs (stmt);
- tree rhs = gimple_assign_rhs1 (stmt);
- use_operand_p use_p;
- gimple use_stmt;
-
- /* If there is a single use only, propagate the equivalency
- instead of keeping the copy. */
- if (TREE_CODE (lhs) == SSA_NAME
- && TREE_CODE (rhs) == SSA_NAME
- && single_imm_use (lhs, &use_p, &use_stmt)
- && may_propagate_copy (USE_FROM_PTR (use_p), rhs))
+ stmt = el_to_remove.pop ();
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
{
- SET_USE (use_p, rhs);
- update_stmt (use_stmt);
- if (inserted_exprs
- && bitmap_bit_p (inserted_exprs, SSA_NAME_VERSION (lhs))
- && TREE_CODE (rhs) == SSA_NAME)
- gimple_set_plf (SSA_NAME_DEF_STMT (rhs), NECESSARY, true);
+ fprintf (dump_file, "Removing dead stmt ");
+ print_gimple_stmt (dump_file, stmt, 0, 0);
}
- /* If this is a store or a now unused copy, remove it. */
- if (TREE_CODE (lhs) != SSA_NAME
- || has_zero_uses (lhs))
+ tree lhs;
+ if (gimple_code (stmt) == GIMPLE_PHI)
+ lhs = gimple_phi_result (stmt);
+ else
+ lhs = gimple_get_lhs (stmt);
+
+ if (inserted_exprs
+ && TREE_CODE (lhs) == SSA_NAME)
+ bitmap_clear_bit (inserted_exprs, SSA_NAME_VERSION (lhs));
+
+ gsi = gsi_for_stmt (stmt);
+ if (gimple_code (stmt) == GIMPLE_PHI)
+ remove_phi_node (&gsi, true);
+ else
{
basic_block bb = gimple_bb (stmt);
- gsi = gsi_for_stmt (stmt);
unlink_stmt_vdef (stmt);
if (gsi_remove (&gsi, true))
bitmap_set_bit (need_eh_cleanup, bb->index);
- if (inserted_exprs
- && TREE_CODE (lhs) == SSA_NAME)
- bitmap_clear_bit (inserted_exprs, SSA_NAME_VERSION (lhs));
+ if (is_gimple_call (stmt) && stmt_can_make_abnormal_goto (stmt))
+ bitmap_set_bit (need_ab_cleanup, bb->index);
release_defs (stmt);
}
+
+ /* Removing a stmt may expose a forwarder block. */
+ el_todo |= TODO_cleanup_cfg;
}
el_to_remove.release ();
- /* We cannot update call statements with virtual operands during
- SSA walk. This might remove them which in turn makes our
- VN lattice invalid. */
- FOR_EACH_VEC_ELT (el_to_update, i, stmt)
- update_stmt (stmt);
- el_to_update.release ();
+ /* Fixup stmts that became noreturn calls. This may require splitting
+ blocks and thus isn't possible during the dominator walk. Do this
+ in reverse order so we don't inadvertedly remove a stmt we want to
+ fixup by visiting a dominating now noreturn call first. */
+ while (!el_to_fixup.is_empty ())
+ {
+ stmt = el_to_fixup.pop ();
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Fixing up noreturn call ");
+ print_gimple_stmt (dump_file, stmt, 0, 0);
+ }
+
+ if (fixup_noreturn_call (stmt))
+ el_todo |= TODO_cleanup_cfg;
+ }
+ el_to_fixup.release ();
return el_todo;
}
mark that statement necessary. Return the stmt, if it is newly
necessary. */
-static inline gimple
+static inline gimple *
mark_operand_necessary (tree op)
{
- gimple stmt;
+ gimple *stmt;
gcc_assert (op);
bitmap worklist;
unsigned i;
bitmap_iterator bi;
- gimple t;
+ gimple *t;
worklist = BITMAP_ALLOC (NULL);
EXECUTE_IF_SET_IN_BITMAP (inserted_exprs, 0, i, bi)
tree arg = PHI_ARG_DEF (t, k);
if (TREE_CODE (arg) == SSA_NAME)
{
- gimple n = mark_operand_necessary (arg);
+ gimple *n = mark_operand_necessary (arg);
if (n)
bitmap_set_bit (worklist, SSA_NAME_VERSION (arg));
}
FOR_EACH_SSA_TREE_OPERAND (use, t, iter, SSA_OP_ALL_USES)
{
- gimple n = mark_operand_necessary (use);
+ gimple *n = mark_operand_necessary (use);
if (n)
bitmap_set_bit (worklist, SSA_NAME_VERSION (use));
}
connect_infinite_loops_to_exit ();
memset (&pre_stats, 0, sizeof (pre_stats));
- postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
- postorder_num = inverted_post_order_compute (postorder);
-
alloc_aux_for_blocks (sizeof (struct bb_bitmap_sets));
- calculate_dominance_info (CDI_POST_DOMINATORS);
calculate_dominance_info (CDI_DOMINATORS);
bitmap_obstack_initialize (&grand_bitmap_obstack);
- phi_translate_table.create (5110);
- expression_to_id.create (num_ssa_names * 3);
- bitmap_set_pool = create_alloc_pool ("Bitmap sets",
- sizeof (struct bitmap_set), 30);
- pre_expr_pool = create_alloc_pool ("pre_expr nodes",
- sizeof (struct pre_expr_d), 30);
+ phi_translate_table = new hash_table<expr_pred_trans_d> (5110);
+ expression_to_id = new hash_table<pre_expr_d> (num_ssa_names * 3);
FOR_ALL_BB_FN (bb, cfun)
{
EXP_GEN (bb) = bitmap_set_new ();
static void
fini_pre ()
{
- free (postorder);
value_expressions.release ();
BITMAP_FREE (inserted_exprs);
bitmap_obstack_release (&grand_bitmap_obstack);
- free_alloc_pool (bitmap_set_pool);
- free_alloc_pool (pre_expr_pool);
- phi_translate_table.dispose ();
- expression_to_id.dispose ();
+ bitmap_set_pool.release ();
+ pre_expr_pool.release ();
+ delete phi_translate_table;
+ phi_translate_table = NULL;
+ delete expression_to_id;
+ expression_to_id = NULL;
name_to_id.release ();
free_aux_for_blocks ();
-
- free_dominance_info (CDI_POST_DOMINATORS);
}
namespace {
GIMPLE_PASS, /* type */
"pre", /* name */
OPTGROUP_NONE, /* optinfo_flags */
- true, /* has_execute */
TV_TREE_PRE, /* tv_id */
/* PROP_no_crit_edges is ensured by placing pass_split_crit_edges before
pass_pre. */
{}
/* opt_pass methods: */
- virtual bool gate (function *) { return flag_tree_pre != 0; }
+ virtual bool gate (function *)
+ { return flag_tree_pre != 0 || flag_code_hoisting != 0; }
virtual unsigned int execute (function *);
}; // class pass_pre
remove_fake_exit_edges ();
gsi_commit_edge_inserts ();
+ /* Eliminate folds statements which might (should not...) end up
+ not keeping virtual operands up-to-date. */
+ gcc_assert (!need_ssa_update_p (fun));
+
/* Remove all the redundant expressions. */
- todo |= eliminate ();
+ todo |= eliminate (true);
statistics_counter_event (fun, "Insertions", pre_stats.insertions);
statistics_counter_event (fun, "PA inserted", pre_stats.pa_insert);
+ statistics_counter_event (fun, "HOIST inserted", pre_stats.hoist_insert);
statistics_counter_event (fun, "New PHIs", pre_stats.phis);
statistics_counter_event (fun, "Eliminated", pre_stats.eliminations);
todo |= fini_eliminate ();
loop_optimizer_finalize ();
+ /* Restore SSA info before tail-merging as that resets it as well. */
+ scc_vn_restore_ssa_info ();
+
/* TODO: tail_merge_optimize may merge all predecessors of a block, in which
case we can merge the block with the remaining predecessor of the block.
It should either:
GIMPLE_PASS, /* type */
"fre", /* name */
OPTGROUP_NONE, /* optinfo_flags */
- true, /* has_execute */
TV_TREE_FRE, /* tv_id */
( PROP_cfg | PROP_ssa ), /* properties_required */
0, /* properties_provided */
memset (&pre_stats, 0, sizeof (pre_stats));
/* Remove all the redundant expressions. */
- todo |= eliminate ();
+ todo |= eliminate (false);
todo |= fini_eliminate ();
+ scc_vn_restore_ssa_info ();
free_scc_vn ();
statistics_counter_event (fun, "Insertions", pre_stats.insertions);
projects / thirdparty / gcc.git / blobdiff